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 package org.graalvm.compiler.lir.stackslotalloc;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot;
26 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
27 import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization;
28
29 import java.util.ArrayDeque;
30 import java.util.ArrayList;
31 import java.util.Arrays;
32 import java.util.Deque;
33 import java.util.EnumMap;
34 import java.util.EnumSet;
35 import java.util.PriorityQueue;
36
37 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
38 import org.graalvm.compiler.debug.Debug;
39 import org.graalvm.compiler.debug.Debug.Scope;
40 import org.graalvm.compiler.debug.DebugCloseable;
41 import org.graalvm.compiler.debug.DebugTimer;
42 import org.graalvm.compiler.debug.Indent;
43 import org.graalvm.compiler.lir.LIR;
44 import org.graalvm.compiler.lir.LIRInstruction;
45 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
46 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
47 import org.graalvm.compiler.lir.ValueProcedure;
48 import org.graalvm.compiler.lir.VirtualStackSlot;
49 import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool;
50 import org.graalvm.compiler.lir.framemap.SimpleVirtualStackSlot;
51 import org.graalvm.compiler.lir.framemap.VirtualStackSlotRange;
52 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
53 import org.graalvm.compiler.lir.phases.AllocationPhase;
54 import org.graalvm.compiler.options.NestedBooleanOptionKey;
55 import org.graalvm.compiler.options.Option;
56 import org.graalvm.compiler.options.OptionType;
57 import org.graalvm.util.EconomicSet;
58
59 import jdk.vm.ci.code.StackSlot;
60 import jdk.vm.ci.code.TargetDescription;
61 import jdk.vm.ci.meta.Value;
62 import 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 */
74 public 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 DebugTimer MainTimer = Debug.timer("LSStackSlotAllocator");
84 private static final DebugTimer NumInstTimer = Debug.timer("LSStackSlotAllocator[NumberInstruction]");
85 private static final DebugTimer BuildIntervalsTimer = Debug.timer("LSStackSlotAllocator[BuildIntervals]");
86 private static final DebugTimer VerifyIntervalsTimer = Debug.timer("LSStackSlotAllocator[VerifyIntervals]");
87 private static final DebugTimer AllocateSlotsTimer = Debug.timer("LSStackSlotAllocator[AllocateSlots]");
88 private static final DebugTimer AssignSlotsTimer = Debug.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()) {
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 FrameMapBuilderTool frameMapBuilder;
109 private final StackInterval[] stackSlotMap;
110 private final PriorityQueue<StackInterval> unhandled;
111 private final PriorityQueue<StackInterval> active;
112 private final AbstractBlockBase<?>[] sortedBlocks;
113 private final int maxOpId;
114
115 @SuppressWarnings("try")
116 private Allocator(LIR lir, FrameMapBuilderTool frameMapBuilder) {
117 this.lir = lir;
118 this.frameMapBuilder = frameMapBuilder;
119 this.stackSlotMap = new StackInterval[frameMapBuilder.getNumberOfStackSlots()];
120 this.sortedBlocks = lir.getControlFlowGraph().getBlocks();
121
122 // insert by from
123 this.unhandled = new PriorityQueue<>((a, b) -> a.from() - b.from());
124 // insert by to
125 this.active = new PriorityQueue<>((a, b) -> a.to() - b.to());
126
127 try (DebugCloseable t = NumInstTimer.start()) {
128 // step 1: number instructions
129 this.maxOpId = numberInstructions(lir, sortedBlocks);
130 }
131 }
132
133 @SuppressWarnings("try")
134 private void allocate() {
135 Debug.dump(Debug.VERBOSE_LEVEL, lir, "After StackSlot numbering");
136
137 long currentFrameSize = StackSlotAllocatorUtil.allocatedFramesize.isEnabled() ? frameMapBuilder.getFrameMap().currentFrameSize() : 0;
138 EconomicSet<LIRInstruction> usePos;
139 // step 2: build intervals
140 try (Scope s = Debug.scope("StackSlotAllocationBuildIntervals"); Indent indent = Debug.logAndIndent("BuildIntervals"); DebugCloseable t = BuildIntervalsTimer.start()) {
141 usePos = buildIntervals();
142 }
143 // step 3: verify intervals
144 if (Debug.isEnabled()) {
145 try (DebugCloseable t = VerifyIntervalsTimer.start()) {
146 assert verifyIntervals();
147 }
148 }
149 if (Debug.isDumpEnabled(Debug.VERBOSE_LEVEL)) {
150 dumpIntervals("Before stack slot allocation");
151 }
152 // step 4: allocate stack slots
153 try (DebugCloseable t = AllocateSlotsTimer.start()) {
154 allocateStackSlots();
155 }
156 if (Debug.isDumpEnabled(Debug.VERBOSE_LEVEL)) {
157 dumpIntervals("After stack slot allocation");
158 }
159
160 // step 5: assign stack slots
161 try (DebugCloseable t = AssignSlotsTimer.start()) {
162 assignStackSlots(usePos);
163 }
164 if (StackSlotAllocatorUtil.allocatedFramesize.isEnabled()) {
165 StackSlotAllocatorUtil.allocatedFramesize.add(frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize);
166 }
167 }
168
169 // ====================
170 // step 1: number instructions
171 // ====================
172
173 /**
174 * Numbers all instructions in all blocks.
175 *
176 * @return The id of the last operation.
177 */
178 private static int numberInstructions(LIR lir, AbstractBlockBase<?>[] sortedBlocks) {
179 int opId = 0;
180 int index = 0;
181 for (AbstractBlockBase<?> block : sortedBlocks) {
182
183 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
184
185 int numInst = instructions.size();
213 assert interval.verify(maxOpId());
214 }
215 }
216 return true;
217 }
218
219 // ====================
220 // step 4: allocate stack slots
221 // ====================
222
223 @SuppressWarnings("try")
224 private void allocateStackSlots() {
225 // create unhandled lists
226 for (StackInterval interval : stackSlotMap) {
227 if (interval != null) {
228 unhandled.add(interval);
229 }
230 }
231
232 for (StackInterval current = activateNext(); current != null; current = activateNext()) {
233 try (Indent indent = Debug.logAndIndent("allocate %s", current)) {
234 allocateSlot(current);
235 }
236 }
237
238 }
239
240 private void allocateSlot(StackInterval current) {
241 VirtualStackSlot virtualSlot = current.getOperand();
242 final StackSlot location;
243 if (virtualSlot instanceof VirtualStackSlotRange) {
244 // No reuse of ranges (yet).
245 VirtualStackSlotRange slotRange = (VirtualStackSlotRange) virtualSlot;
246 location = frameMapBuilder.getFrameMap().allocateStackSlots(slotRange.getSlots(), slotRange.getObjects());
247 StackSlotAllocatorUtil.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotRangeSize(slotRange.getSlots()));
248 StackSlotAllocatorUtil.allocatedSlots.increment();
249 } else {
250 assert virtualSlot instanceof SimpleVirtualStackSlot : "Unexpected VirtualStackSlot type: " + virtualSlot;
251 StackSlot slot = findFreeSlot((SimpleVirtualStackSlot) virtualSlot);
252 if (slot != null) {
253 /*
254 * Free stack slot available. Note that we create a new one because the kind
255 * might not match.
256 */
257 location = StackSlot.get(current.kind(), slot.getRawOffset(), slot.getRawAddFrameSize());
258 StackSlotAllocatorUtil.reusedSlots.increment();
259 Debug.log(Debug.BASIC_LEVEL, "Reuse stack slot %s (reallocated from %s) for virtual stack slot %s", location, slot, virtualSlot);
260 } else {
261 // Allocate new stack slot.
262 location = frameMapBuilder.getFrameMap().allocateSpillSlot(virtualSlot.getValueKind());
263 StackSlotAllocatorUtil.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotSize(virtualSlot.getValueKind()));
264 StackSlotAllocatorUtil.allocatedSlots.increment();
265 Debug.log(Debug.BASIC_LEVEL, "New stack slot %s for virtual stack slot %s", location, virtualSlot);
266 }
267 }
268 Debug.log("Allocate location %s for interval %s", location, current);
269 current.setLocation(location);
270 }
271
272 private enum SlotSize {
273 Size1,
274 Size2,
275 Size4,
276 Size8,
277 Illegal;
278 }
279
280 private SlotSize forKind(ValueKind<?> kind) {
281 switch (frameMapBuilder.getFrameMap().spillSlotSize(kind)) {
282 case 1:
283 return SlotSize.Size1;
284 case 2:
285 return SlotSize.Size2;
286 case 4:
287 return SlotSize.Size4;
288 case 8:
347 private void freeSlot(StackSlot slot) {
348 SlotSize size = forKind(slot.getValueKind());
349 if (size == SlotSize.Illegal) {
350 return;
351 }
352 getOrInitFreeSlots(size).addLast(slot);
353 }
354
355 /**
356 * Gets the next unhandled interval and finishes handled intervals.
357 */
358 private StackInterval activateNext() {
359 if (unhandled.isEmpty()) {
360 return null;
361 }
362 StackInterval next = unhandled.poll();
363 // finish handled intervals
364 for (int id = next.from(); activePeekId() < id;) {
365 finished(active.poll());
366 }
367 Debug.log("active %s", next);
368 active.add(next);
369 return next;
370 }
371
372 /**
373 * Gets the lowest {@link StackInterval#to() end position} of all active intervals. If there
374 * is none {@link Integer#MAX_VALUE} is returned.
375 */
376 private int activePeekId() {
377 StackInterval first = active.peek();
378 if (first == null) {
379 return Integer.MAX_VALUE;
380 }
381 return first.to();
382 }
383
384 /**
385 * Finishes {@code interval} by adding its location to the list of free stack slots.
386 */
387 private void finished(StackInterval interval) {
388 StackSlot location = interval.location();
389 Debug.log("finished %s (freeing %s)", interval, location);
390 freeSlot(location);
391 }
392
393 // ====================
394 // step 5: assign stack slots
395 // ====================
396
397 private void assignStackSlots(EconomicSet<LIRInstruction> usePos) {
398 for (LIRInstruction op : usePos) {
399 op.forEachInput(assignSlot);
400 op.forEachAlive(assignSlot);
401 op.forEachState(assignSlot);
402
403 op.forEachTemp(assignSlot);
404 op.forEachOutput(assignSlot);
405 }
406 }
407
408 ValueProcedure assignSlot = new ValueProcedure() {
409 @Override
417 return value;
418 }
419 };
420
421 // ====================
422 //
423 // ====================
424
425 /**
426 * Gets the highest instruction id.
427 */
428 private int maxOpId() {
429 return maxOpId;
430 }
431
432 private StackInterval get(VirtualStackSlot stackSlot) {
433 return stackSlotMap[stackSlot.getId()];
434 }
435
436 private void dumpIntervals(String label) {
437 Debug.dump(Debug.VERBOSE_LEVEL, new StackIntervalDumper(Arrays.copyOf(stackSlotMap, stackSlotMap.length)), label);
438 }
439
440 }
441 }
|
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 package org.graalvm.compiler.lir.stackslotalloc;
24
25 import static org.graalvm.compiler.debug.DebugContext.BASIC_LEVEL;
26 import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot;
27 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
28 import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization;
29
30 import java.util.ArrayDeque;
31 import java.util.ArrayList;
32 import java.util.Arrays;
33 import java.util.Deque;
34 import java.util.EnumMap;
35 import java.util.EnumSet;
36 import java.util.PriorityQueue;
37
38 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
39 import org.graalvm.compiler.debug.DebugCloseable;
40 import org.graalvm.compiler.debug.DebugContext;
41 import org.graalvm.compiler.debug.Indent;
42 import org.graalvm.compiler.debug.TimerKey;
43 import org.graalvm.compiler.lir.LIR;
44 import org.graalvm.compiler.lir.LIRInstruction;
45 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
46 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
47 import org.graalvm.compiler.lir.ValueProcedure;
48 import org.graalvm.compiler.lir.VirtualStackSlot;
49 import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool;
50 import org.graalvm.compiler.lir.framemap.SimpleVirtualStackSlot;
51 import org.graalvm.compiler.lir.framemap.VirtualStackSlotRange;
52 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
53 import org.graalvm.compiler.lir.phases.AllocationPhase;
54 import org.graalvm.compiler.options.NestedBooleanOptionKey;
55 import org.graalvm.compiler.options.Option;
56 import org.graalvm.compiler.options.OptionType;
57 import org.graalvm.util.EconomicSet;
58
59 import jdk.vm.ci.code.StackSlot;
60 import jdk.vm.ci.code.TargetDescription;
61 import jdk.vm.ci.meta.Value;
62 import 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 */
74 public 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();
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:
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
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 }
|