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