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