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