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 */
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 private final LIR lir;
107 private final FrameMapBuilderTool frameMapBuilder;
108 private final StackInterval[] stackSlotMap;
109 private final PriorityQueue<StackInterval> unhandled;
110 private final PriorityQueue<StackInterval> active;
111 private final AbstractBlockBase<?>[] sortedBlocks;
112 private final int maxOpId;
113
114 @SuppressWarnings("try")
115 private Allocator(LIR lir, FrameMapBuilderTool frameMapBuilder) {
116 this.lir = lir;
117 this.frameMapBuilder = frameMapBuilder;
118 this.stackSlotMap = new StackInterval[frameMapBuilder.getNumberOfStackSlots()];
119 this.sortedBlocks = lir.getControlFlowGraph().getBlocks();
120
121 // insert by from
122 this.unhandled = new PriorityQueue<>((a, b) -> a.from() - b.from());
123 // insert by to
124 this.active = new PriorityQueue<>((a, b) -> a.to() - b.to());
125
126 try (DebugCloseable t = NumInstTimer.start()) {
127 // step 1: number instructions
128 this.maxOpId = numberInstructions(lir, sortedBlocks);
129 }
130 }
131
132 @SuppressWarnings("try")
133 private void allocate() {
134 Debug.dump(Debug.INFO_LOG_LEVEL, lir, "After StackSlot numbering");
135
136 long currentFrameSize = StackSlotAllocatorUtil.allocatedFramesize.isEnabled() ? frameMapBuilder.getFrameMap().currentFrameSize() : 0;
137 EconomicSet<LIRInstruction> usePos;
138 // step 2: build intervals
139 try (Scope s = Debug.scope("StackSlotAllocationBuildIntervals"); Indent indent = Debug.logAndIndent("BuildIntervals"); DebugCloseable t = BuildIntervalsTimer.start()) {
140 usePos = buildIntervals();
141 }
142 // step 3: verify intervals
143 if (Debug.isEnabled()) {
144 try (DebugCloseable t = VerifyIntervalsTimer.start()) {
145 assert verifyIntervals();
146 }
147 }
148 if (Debug.isDumpEnabled(Debug.INFO_LOG_LEVEL)) {
149 dumpIntervals("Before stack slot allocation");
150 }
151 // step 4: allocate stack slots
152 try (DebugCloseable t = AllocateSlotsTimer.start()) {
153 allocateStackSlots();
154 }
155 if (Debug.isDumpEnabled(Debug.INFO_LOG_LEVEL)) {
156 dumpIntervals("After stack slot allocation");
157 }
158
159 // step 5: assign stack slots
160 try (DebugCloseable t = AssignSlotsTimer.start()) {
161 assignStackSlots(usePos);
162 }
163 Debug.dump(Debug.INFO_LOG_LEVEL, lir, "After StackSlot assignment");
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();
186 for (int j = 0; j < numInst; j++) {
187 LIRInstruction op = instructions.get(j);
188 op.setId(opId);
189
190 index++;
191 opId += 2; // numbering of lirOps by two
192 }
193 }
194 assert (index << 1) == opId : "must match: " + (index << 1);
195 return opId - 2;
196 }
197
198 // ====================
199 // step 2: build intervals
200 // ====================
201
202 private EconomicSet<LIRInstruction> buildIntervals() {
203 return new FixPointIntervalBuilder(lir, stackSlotMap, maxOpId()).build();
204 }
205
206 // ====================
207 // step 3: verify intervals
208 // ====================
209
210 private boolean verifyIntervals() {
211 for (StackInterval interval : stackSlotMap) {
212 if (interval != null) {
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_LOG_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_LOG_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:
289 return SlotSize.Size8;
290 default:
291 return SlotSize.Illegal;
292 }
293 }
294
295 private EnumMap<SlotSize, Deque<StackSlot>> freeSlots;
296
297 /**
298 * @return The list of free stack slots for {@code size} or {@code null} if there is none.
299 */
300 private Deque<StackSlot> getOrNullFreeSlots(SlotSize size) {
301 if (freeSlots == null) {
302 return null;
303 }
304 return freeSlots.get(size);
305 }
306
307 /**
308 * @return the list of free stack slots for {@code size}. If there is none a list is
309 * created.
310 */
311 private Deque<StackSlot> getOrInitFreeSlots(SlotSize size) {
312 assert size != SlotSize.Illegal;
313 Deque<StackSlot> freeList;
314 if (freeSlots != null) {
315 freeList = freeSlots.get(size);
316 } else {
317 freeSlots = new EnumMap<>(SlotSize.class);
318 freeList = null;
319 }
320 if (freeList == null) {
321 freeList = new ArrayDeque<>();
322 freeSlots.put(size, freeList);
323 }
324 assert freeList != null;
325 return freeList;
326 }
327
328 /**
329 * Gets a free stack slot for {@code slot} or {@code null} if there is none.
330 */
331 private StackSlot findFreeSlot(SimpleVirtualStackSlot slot) {
332 assert slot != null;
333 SlotSize size = forKind(slot.getValueKind());
334 if (size == SlotSize.Illegal) {
335 return null;
336 }
337 Deque<StackSlot> freeList = getOrNullFreeSlots(size);
338 if (freeList == null) {
339 return null;
340 }
341 return freeList.pollLast();
342 }
343
344 /**
345 * Adds a stack slot to the list of free slots.
346 */
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
410 public Value doValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
411 if (isVirtualStackSlot(value)) {
412 VirtualStackSlot slot = asVirtualStackSlot(value);
413 StackInterval interval = get(slot);
414 assert interval != null;
415 return interval.location();
416 }
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.INFO_LOG_LEVEL, new StackIntervalDumper(Arrays.copyOf(stackSlotMap, stackSlotMap.length)), label);
438 }
439
440 }
441 }