1/* 2 * Copyright (c) 2014, 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23package org.graalvm.compiler.lir.stackslotalloc; 24 25import static org.graalvm.compiler.debug.DebugContext.BASIC_LEVEL; 26import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot; 27import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot; 28import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization; 29 30import java.util.ArrayDeque; 31import java.util.ArrayList; 32import java.util.Arrays; 33import java.util.Deque; 34import java.util.EnumMap; 35import java.util.EnumSet; 36import java.util.PriorityQueue; 37 38import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 39import org.graalvm.compiler.debug.DebugCloseable; 40import org.graalvm.compiler.debug.DebugContext; 41import org.graalvm.compiler.debug.Indent; 42import org.graalvm.compiler.debug.TimerKey; 43import org.graalvm.compiler.lir.LIR; 44import org.graalvm.compiler.lir.LIRInstruction; 45import org.graalvm.compiler.lir.LIRInstruction.OperandFlag; 46import org.graalvm.compiler.lir.LIRInstruction.OperandMode; 47import org.graalvm.compiler.lir.ValueProcedure; 48import org.graalvm.compiler.lir.VirtualStackSlot; 49import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool; 50import org.graalvm.compiler.lir.framemap.SimpleVirtualStackSlot; 51import org.graalvm.compiler.lir.framemap.VirtualStackSlotRange; 52import org.graalvm.compiler.lir.gen.LIRGenerationResult; 53import org.graalvm.compiler.lir.phases.AllocationPhase; 54import org.graalvm.compiler.options.NestedBooleanOptionKey; 55import org.graalvm.compiler.options.Option; 56import org.graalvm.compiler.options.OptionType; 57import org.graalvm.util.EconomicSet; 58 59import jdk.vm.ci.code.StackSlot; 60import jdk.vm.ci.code.TargetDescription; 61import jdk.vm.ci.meta.Value; 62import jdk.vm.ci.meta.ValueKind; 63 64/** 65 * Linear Scan {@link StackSlotAllocatorUtil stack slot allocator}. 66 * <p> 67 * <b>Remark:</b> The analysis works under the assumption that a stack slot is no longer live after 68 * its last usage. If an {@link LIRInstruction instruction} transfers the raw address of the stack 69 * slot to another location, e.g. a registers, and this location is referenced later on, the 70 * {@link org.graalvm.compiler.lir.LIRInstruction.Use usage} of the stack slot must be marked with 71 * the {@link OperandFlag#UNINITIALIZED}. Otherwise the stack slot might be reused and its content 72 * destroyed. 73 */ 74public final class LSStackSlotAllocator extends AllocationPhase { 75 76 public static class Options { 77 // @formatter:off 78 @Option(help = "Use linear scan stack slot allocation.", type = OptionType.Debug) 79 public static final NestedBooleanOptionKey LIROptLSStackSlotAllocator = new NestedBooleanOptionKey(LIROptimization, true); 80 // @formatter:on 81 } 82 83 private static final TimerKey MainTimer = DebugContext.timer("LSStackSlotAllocator"); 84 private static final TimerKey NumInstTimer = DebugContext.timer("LSStackSlotAllocator[NumberInstruction]"); 85 private static final TimerKey BuildIntervalsTimer = DebugContext.timer("LSStackSlotAllocator[BuildIntervals]"); 86 private static final TimerKey VerifyIntervalsTimer = DebugContext.timer("LSStackSlotAllocator[VerifyIntervals]"); 87 private static final TimerKey AllocateSlotsTimer = DebugContext.timer("LSStackSlotAllocator[AllocateSlots]"); 88 private static final TimerKey AssignSlotsTimer = DebugContext.timer("LSStackSlotAllocator[AssignSlots]"); 89 90 @Override 91 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) { 92 allocateStackSlots((FrameMapBuilderTool) lirGenRes.getFrameMapBuilder(), lirGenRes); 93 lirGenRes.buildFrameMap(); 94 } 95 96 @SuppressWarnings("try") 97 public static void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res) { 98 if (builder.getNumberOfStackSlots() > 0) { 99 try (DebugCloseable t = MainTimer.start(res.getLIR().getDebug())) { 100 new Allocator(res.getLIR(), builder).allocate(); 101 } 102 } 103 } 104 105 private static final class Allocator { 106 107 private final LIR lir; 108 private final DebugContext debug; 109 private final FrameMapBuilderTool frameMapBuilder; 110 private final StackInterval[] stackSlotMap; 111 private final PriorityQueue<StackInterval> unhandled; 112 private final PriorityQueue<StackInterval> active; 113 private final AbstractBlockBase<?>[] sortedBlocks; 114 private final int maxOpId; 115 116 @SuppressWarnings("try") 117 private Allocator(LIR lir, FrameMapBuilderTool frameMapBuilder) { 118 this.lir = lir; 119 this.debug = lir.getDebug(); 120 this.frameMapBuilder = frameMapBuilder; 121 this.stackSlotMap = new StackInterval[frameMapBuilder.getNumberOfStackSlots()]; 122 this.sortedBlocks = lir.getControlFlowGraph().getBlocks(); 123 124 // insert by from 125 this.unhandled = new PriorityQueue<>((a, b) -> a.from() - b.from()); 126 // insert by to 127 this.active = new PriorityQueue<>((a, b) -> a.to() - b.to()); 128 129 try (DebugCloseable t = NumInstTimer.start(debug)) { 130 // step 1: number instructions 131 this.maxOpId = numberInstructions(lir, sortedBlocks); 132 } 133 } 134 135 @SuppressWarnings("try") 136 private void allocate() { 137 debug.dump(DebugContext.VERBOSE_LEVEL, lir, "After StackSlot numbering"); 138 139 boolean allocationFramesizeEnabled = StackSlotAllocatorUtil.allocatedFramesize.isEnabled(debug); 140 long currentFrameSize = allocationFramesizeEnabled ? frameMapBuilder.getFrameMap().currentFrameSize() : 0; 141 EconomicSet<LIRInstruction> usePos; 142 // step 2: build intervals 143 try (DebugContext.Scope s = debug.scope("StackSlotAllocationBuildIntervals"); Indent indent = debug.logAndIndent("BuildIntervals"); DebugCloseable t = BuildIntervalsTimer.start(debug)) { 144 usePos = buildIntervals(); 145 } 146 // step 3: verify intervals 147 if (debug.areScopesEnabled()) { 148 try (DebugCloseable t = VerifyIntervalsTimer.start(debug)) { 149 assert verifyIntervals(); 150 } 151 } 152 if (debug.isDumpEnabled(DebugContext.VERBOSE_LEVEL)) { 153 dumpIntervals("Before stack slot allocation"); 154 } 155 // step 4: allocate stack slots 156 try (DebugCloseable t = AllocateSlotsTimer.start(debug)) { 157 allocateStackSlots(); 158 } 159 if (debug.isDumpEnabled(DebugContext.VERBOSE_LEVEL)) { 160 dumpIntervals("After stack slot allocation"); 161 } 162 163 // step 5: assign stack slots 164 try (DebugCloseable t = AssignSlotsTimer.start(debug)) { 165 assignStackSlots(usePos); 166 } 167 if (allocationFramesizeEnabled) { 168 StackSlotAllocatorUtil.allocatedFramesize.add(debug, frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize); 169 } 170 } 171 172 // ==================== 173 // step 1: number instructions 174 // ==================== 175 176 /** 177 * Numbers all instructions in all blocks. 178 * 179 * @return The id of the last operation. 180 */ 181 private static int numberInstructions(LIR lir, AbstractBlockBase<?>[] sortedBlocks) { 182 int opId = 0; 183 int index = 0; 184 for (AbstractBlockBase<?> block : sortedBlocks) { 185 186 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block); 187 188 int numInst = instructions.size(); 189 for (int j = 0; j < numInst; j++) { 190 LIRInstruction op = instructions.get(j); 191 op.setId(opId); 192 193 index++; 194 opId += 2; // numbering of lirOps by two 195 } 196 } 197 assert (index << 1) == opId : "must match: " + (index << 1); 198 return opId - 2; 199 } 200 201 // ==================== 202 // step 2: build intervals 203 // ==================== 204 205 private EconomicSet<LIRInstruction> buildIntervals() { 206 return new FixPointIntervalBuilder(lir, stackSlotMap, maxOpId()).build(); 207 } 208 209 // ==================== 210 // step 3: verify intervals 211 // ==================== 212 213 private boolean verifyIntervals() { 214 for (StackInterval interval : stackSlotMap) { 215 if (interval != null) { 216 assert interval.verify(maxOpId()); 217 } 218 } 219 return true; 220 } 221 222 // ==================== 223 // step 4: allocate stack slots 224 // ==================== 225 226 @SuppressWarnings("try") 227 private void allocateStackSlots() { 228 // create unhandled lists 229 for (StackInterval interval : stackSlotMap) { 230 if (interval != null) { 231 unhandled.add(interval); 232 } 233 } 234 235 for (StackInterval current = activateNext(); current != null; current = activateNext()) { 236 try (Indent indent = debug.logAndIndent("allocate %s", current)) { 237 allocateSlot(current); 238 } 239 } 240 241 } 242 243 private void allocateSlot(StackInterval current) { 244 VirtualStackSlot virtualSlot = current.getOperand(); 245 final StackSlot location; 246 if (virtualSlot instanceof VirtualStackSlotRange) { 247 // No reuse of ranges (yet). 248 VirtualStackSlotRange slotRange = (VirtualStackSlotRange) virtualSlot; 249 location = frameMapBuilder.getFrameMap().allocateStackSlots(slotRange.getSlots(), slotRange.getObjects()); 250 StackSlotAllocatorUtil.virtualFramesize.add(debug, frameMapBuilder.getFrameMap().spillSlotRangeSize(slotRange.getSlots())); 251 StackSlotAllocatorUtil.allocatedSlots.increment(debug); 252 } else { 253 assert virtualSlot instanceof SimpleVirtualStackSlot : "Unexpected VirtualStackSlot type: " + virtualSlot; 254 StackSlot slot = findFreeSlot((SimpleVirtualStackSlot) virtualSlot); 255 if (slot != null) { 256 /* 257 * Free stack slot available. Note that we create a new one because the kind 258 * might not match. 259 */ 260 location = StackSlot.get(current.kind(), slot.getRawOffset(), slot.getRawAddFrameSize()); 261 StackSlotAllocatorUtil.reusedSlots.increment(debug); 262 debug.log(BASIC_LEVEL, "Reuse stack slot %s (reallocated from %s) for virtual stack slot %s", location, slot, virtualSlot); 263 } else { 264 // Allocate new stack slot. 265 location = frameMapBuilder.getFrameMap().allocateSpillSlot(virtualSlot.getValueKind()); 266 StackSlotAllocatorUtil.virtualFramesize.add(debug, frameMapBuilder.getFrameMap().spillSlotSize(virtualSlot.getValueKind())); 267 StackSlotAllocatorUtil.allocatedSlots.increment(debug); 268 debug.log(BASIC_LEVEL, "New stack slot %s for virtual stack slot %s", location, virtualSlot); 269 } 270 } 271 debug.log("Allocate location %s for interval %s", location, current); 272 current.setLocation(location); 273 } 274 275 private enum SlotSize { 276 Size1, 277 Size2, 278 Size4, 279 Size8, 280 Illegal; 281 } 282 283 private SlotSize forKind(ValueKind<?> kind) { 284 switch (frameMapBuilder.getFrameMap().spillSlotSize(kind)) { 285 case 1: 286 return SlotSize.Size1; 287 case 2: 288 return SlotSize.Size2; 289 case 4: 290 return SlotSize.Size4; 291 case 8: 292 return SlotSize.Size8; 293 default: 294 return SlotSize.Illegal; 295 } 296 } 297 298 private EnumMap<SlotSize, Deque<StackSlot>> freeSlots; 299 300 /** 301 * @return The list of free stack slots for {@code size} or {@code null} if there is none. 302 */ 303 private Deque<StackSlot> getOrNullFreeSlots(SlotSize size) { 304 if (freeSlots == null) { 305 return null; 306 } 307 return freeSlots.get(size); 308 } 309 310 /** 311 * @return the list of free stack slots for {@code size}. If there is none a list is 312 * created. 313 */ 314 private Deque<StackSlot> getOrInitFreeSlots(SlotSize size) { 315 assert size != SlotSize.Illegal; 316 Deque<StackSlot> freeList; 317 if (freeSlots != null) { 318 freeList = freeSlots.get(size); 319 } else { 320 freeSlots = new EnumMap<>(SlotSize.class); 321 freeList = null; 322 } 323 if (freeList == null) { 324 freeList = new ArrayDeque<>(); 325 freeSlots.put(size, freeList); 326 } 327 assert freeList != null; 328 return freeList; 329 } 330 331 /** 332 * Gets a free stack slot for {@code slot} or {@code null} if there is none. 333 */ 334 private StackSlot findFreeSlot(SimpleVirtualStackSlot slot) { 335 assert slot != null; 336 SlotSize size = forKind(slot.getValueKind()); 337 if (size == SlotSize.Illegal) { 338 return null; 339 } 340 Deque<StackSlot> freeList = getOrNullFreeSlots(size); 341 if (freeList == null) { 342 return null; 343 } 344 return freeList.pollLast(); 345 } 346 347 /** 348 * Adds a stack slot to the list of free slots. 349 */ 350 private void freeSlot(StackSlot slot) { 351 SlotSize size = forKind(slot.getValueKind()); 352 if (size == SlotSize.Illegal) { 353 return; 354 } 355 getOrInitFreeSlots(size).addLast(slot); 356 } 357 358 /** 359 * Gets the next unhandled interval and finishes handled intervals. 360 */ 361 private StackInterval activateNext() { 362 if (unhandled.isEmpty()) { 363 return null; 364 } 365 StackInterval next = unhandled.poll(); 366 // finish handled intervals 367 for (int id = next.from(); activePeekId() < id;) { 368 finished(active.poll()); 369 } 370 debug.log("active %s", next); 371 active.add(next); 372 return next; 373 } 374 375 /** 376 * Gets the lowest {@link StackInterval#to() end position} of all active intervals. If there 377 * is none {@link Integer#MAX_VALUE} is returned. 378 */ 379 private int activePeekId() { 380 StackInterval first = active.peek(); 381 if (first == null) { 382 return Integer.MAX_VALUE; 383 } 384 return first.to(); 385 } 386 387 /** 388 * Finishes {@code interval} by adding its location to the list of free stack slots. 389 */ 390 private void finished(StackInterval interval) { 391 StackSlot location = interval.location(); 392 debug.log("finished %s (freeing %s)", interval, location); 393 freeSlot(location); 394 } 395 396 // ==================== 397 // step 5: assign stack slots 398 // ==================== 399 400 private void assignStackSlots(EconomicSet<LIRInstruction> usePos) { 401 for (LIRInstruction op : usePos) { 402 op.forEachInput(assignSlot); 403 op.forEachAlive(assignSlot); 404 op.forEachState(assignSlot); 405 406 op.forEachTemp(assignSlot); 407 op.forEachOutput(assignSlot); 408 } 409 } 410 411 ValueProcedure assignSlot = new ValueProcedure() { 412 @Override 413 public Value doValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { 414 if (isVirtualStackSlot(value)) { 415 VirtualStackSlot slot = asVirtualStackSlot(value); 416 StackInterval interval = get(slot); 417 assert interval != null; 418 return interval.location(); 419 } 420 return value; 421 } 422 }; 423 424 // ==================== 425 // 426 // ==================== 427 428 /** 429 * Gets the highest instruction id. 430 */ 431 private int maxOpId() { 432 return maxOpId; 433 } 434 435 private StackInterval get(VirtualStackSlot stackSlot) { 436 return stackSlotMap[stackSlot.getId()]; 437 } 438 439 private void dumpIntervals(String label) { 440 debug.dump(DebugContext.VERBOSE_LEVEL, new StackIntervalDumper(Arrays.copyOf(stackSlotMap, stackSlotMap.length)), label); 441 } 442 443 } 444} 445