001/*
002 * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.lir.stackslotalloc;
024
025import static com.oracle.graal.lir.phases.LIRPhase.Options.*;
026import static jdk.internal.jvmci.code.ValueUtil.*;
027
028import java.util.*;
029import java.util.function.*;
030
031import jdk.internal.jvmci.code.*;
032import com.oracle.graal.debug.*;
033import com.oracle.graal.debug.Debug.*;
034import jdk.internal.jvmci.meta.*;
035import jdk.internal.jvmci.options.*;
036
037import com.oracle.graal.compiler.common.alloc.*;
038import com.oracle.graal.compiler.common.cfg.*;
039import com.oracle.graal.lir.*;
040import com.oracle.graal.lir.LIRInstruction.OperandFlag;
041import com.oracle.graal.lir.LIRInstruction.OperandMode;
042import com.oracle.graal.lir.framemap.*;
043import com.oracle.graal.lir.gen.*;
044import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
045import com.oracle.graal.lir.phases.*;
046
047/**
048 * Linear Scan {@link StackSlotAllocator}.
049 * <p>
050 * <b>Remark:</b> The analysis works under the assumption that a stack slot is no longer live after
051 * its last usage. If an {@link LIRInstruction instruction} transfers the raw address of the stack
052 * slot to another location, e.g. a registers, and this location is referenced later on, the
053 * {@link com.oracle.graal.lir.LIRInstruction.Use usage} of the stack slot must be marked with the
054 * {@link OperandFlag#UNINITIALIZED}. Otherwise the stack slot might be reused and its content
055 * destroyed.
056 */
057public final class LSStackSlotAllocator extends AllocationPhase implements StackSlotAllocator {
058
059    public static class Options {
060        // @formatter:off
061        @Option(help = "Use linear scan stack slot allocation.", type = OptionType.Debug)
062        public static final NestedBooleanOptionValue LIROptLSStackSlotAllocator = new NestedBooleanOptionValue(LIROptimization, true);
063        // @formatter:on
064    }
065
066    private static final DebugTimer MainTimer = Debug.timer("LSStackSlotAllocator");
067    private static final DebugTimer NumInstTimer = Debug.timer("LSStackSlotAllocator[NumberInstruction]");
068    private static final DebugTimer BuildIntervalsTimer = Debug.timer("LSStackSlotAllocator[BuildIntervals]");
069    private static final DebugTimer VerifyIntervalsTimer = Debug.timer("LSStackSlotAllocator[VerifyIntervals]");
070    private static final DebugTimer AllocateSlotsTimer = Debug.timer("LSStackSlotAllocator[AllocateSlots]");
071    private static final DebugTimer AssignSlotsTimer = Debug.timer("LSStackSlotAllocator[AssignSlots]");
072
073    @Override
074    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory,
075                    RegisterAllocationConfig registerAllocationConfig) {
076        lirGenRes.buildFrameMap(this);
077    }
078
079    public void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res) {
080        if (builder.getNumberOfStackSlots() > 0) {
081            try (DebugCloseable t = MainTimer.start()) {
082                new Allocator(res.getLIR(), builder).allocate();
083            }
084        }
085    }
086
087    private static final class Allocator {
088        private final LIR lir;
089        private final FrameMapBuilderTool frameMapBuilder;
090        private final StackInterval[] stackSlotMap;
091        private final PriorityQueue<StackInterval> unhandled;
092        private final PriorityQueue<StackInterval> active;
093        private final List<? extends AbstractBlockBase<?>> sortedBlocks;
094        private final int maxOpId;
095
096        private Allocator(LIR lir, FrameMapBuilderTool frameMapBuilder) {
097            this.lir = lir;
098            this.frameMapBuilder = frameMapBuilder;
099            this.stackSlotMap = new StackInterval[frameMapBuilder.getNumberOfStackSlots()];
100            this.sortedBlocks = lir.getControlFlowGraph().getBlocks();
101
102            // insert by from
103            this.unhandled = new PriorityQueue<>((a, b) -> a.from() - b.from());
104            // insert by to
105            this.active = new PriorityQueue<>((a, b) -> a.to() - b.to());
106
107            try (DebugCloseable t = NumInstTimer.start()) {
108                // step 1: number instructions
109                this.maxOpId = numberInstructions(lir, sortedBlocks);
110            }
111        }
112
113        private void allocate() {
114            Debug.dump(lir, "After StackSlot numbering");
115
116            long currentFrameSize = StackSlotAllocator.allocatedFramesize.isEnabled() ? frameMapBuilder.getFrameMap().currentFrameSize() : 0;
117            Set<LIRInstruction> usePos;
118            // step 2: build intervals
119            try (Scope s = Debug.scope("StackSlotAllocationBuildIntervals"); Indent indent = Debug.logAndIndent("BuildIntervals"); DebugCloseable t = BuildIntervalsTimer.start()) {
120                usePos = buildIntervals();
121            }
122            // step 3: verify intervals
123            if (Debug.isEnabled()) {
124                try (DebugCloseable t = VerifyIntervalsTimer.start()) {
125                    verifyIntervals();
126                }
127            }
128            if (Debug.isDumpEnabled()) {
129                dumpIntervals("Before stack slot allocation");
130            }
131            // step 4: allocate stack slots
132            try (DebugCloseable t = AllocateSlotsTimer.start()) {
133                allocateStackSlots();
134            }
135            if (Debug.isDumpEnabled()) {
136                dumpIntervals("After stack slot allocation");
137            }
138
139            // step 5: assign stack slots
140            try (DebugCloseable t = AssignSlotsTimer.start()) {
141                assignStackSlots(usePos);
142            }
143            Debug.dump(lir, "After StackSlot assignment");
144            if (StackSlotAllocator.allocatedFramesize.isEnabled()) {
145                StackSlotAllocator.allocatedFramesize.add(frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize);
146            }
147        }
148
149        // ====================
150        // step 1: number instructions
151        // ====================
152
153        /**
154         * Numbers all instructions in all blocks.
155         *
156         * @return The id of the last operation.
157         */
158        private static int numberInstructions(LIR lir, List<? extends AbstractBlockBase<?>> sortedBlocks) {
159            int opId = 0;
160            int index = 0;
161            for (AbstractBlockBase<?> block : sortedBlocks) {
162
163                List<LIRInstruction> instructions = lir.getLIRforBlock(block);
164
165                int numInst = instructions.size();
166                for (int j = 0; j < numInst; j++) {
167                    LIRInstruction op = instructions.get(j);
168                    op.setId(opId);
169
170                    index++;
171                    opId += 2; // numbering of lirOps by two
172                }
173            }
174            assert (index << 1) == opId : "must match: " + (index << 1);
175            return opId - 2;
176        }
177
178        // ====================
179        // step 2: build intervals
180        // ====================
181
182        private Set<LIRInstruction> buildIntervals() {
183            return new FixPointIntervalBuilder(lir, stackSlotMap, maxOpId()).build();
184        }
185
186        // ====================
187        // step 3: verify intervals
188        // ====================
189
190        private void verifyIntervals() {
191            forEachInterval(interval -> {
192                assert interval.verify(maxOpId());
193            });
194        }
195
196        // ====================
197        // step 4: allocate stack slots
198        // ====================
199
200        private void allocateStackSlots() {
201            // create unhandled lists
202            forEachInterval(unhandled::add);
203
204            for (StackInterval current = activateNext(); current != null; current = activateNext()) {
205                try (Indent indent = Debug.logAndIndent("allocate %s", current)) {
206                    allocateSlot(current);
207                }
208            }
209
210        }
211
212        private void allocateSlot(StackInterval current) {
213            VirtualStackSlot virtualSlot = current.getOperand();
214            final StackSlot location;
215            if (virtualSlot instanceof VirtualStackSlotRange) {
216                // No reuse of ranges (yet).
217                VirtualStackSlotRange slotRange = (VirtualStackSlotRange) virtualSlot;
218                location = frameMapBuilder.getFrameMap().allocateStackSlots(slotRange.getSlots(), slotRange.getObjects());
219                StackSlotAllocator.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotRangeSize(slotRange.getSlots()));
220                StackSlotAllocator.allocatedSlots.increment();
221            } else {
222                assert virtualSlot instanceof SimpleVirtualStackSlot : "Unexpected VirtualStackSlot type: " + virtualSlot;
223                StackSlot slot = findFreeSlot((SimpleVirtualStackSlot) virtualSlot);
224                if (slot != null) {
225                    /*
226                     * Free stack slot available. Note that we create a new one because the kind
227                     * might not match.
228                     */
229                    location = StackSlot.get(current.kind(), slot.getRawOffset(), slot.getRawAddFrameSize());
230                    StackSlotAllocator.reusedSlots.increment();
231                    Debug.log(1, "Reuse stack slot %s (reallocated from %s) for virtual stack slot %s", location, slot, virtualSlot);
232                } else {
233                    // Allocate new stack slot.
234                    location = frameMapBuilder.getFrameMap().allocateSpillSlot(virtualSlot.getLIRKind());
235                    StackSlotAllocator.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotSize(virtualSlot.getLIRKind()));
236                    StackSlotAllocator.allocatedSlots.increment();
237                    Debug.log(1, "New stack slot %s for virtual stack slot %s", location, virtualSlot);
238                }
239            }
240            Debug.log("Allocate location %s for interval %s", location, current);
241            current.setLocation(location);
242        }
243
244        private static enum SlotSize {
245            Size1,
246            Size2,
247            Size4,
248            Size8,
249            Illegal;
250        }
251
252        private SlotSize forKind(LIRKind kind) {
253            switch (frameMapBuilder.getFrameMap().spillSlotSize(kind)) {
254                case 1:
255                    return SlotSize.Size1;
256                case 2:
257                    return SlotSize.Size2;
258                case 4:
259                    return SlotSize.Size4;
260                case 8:
261                    return SlotSize.Size8;
262                default:
263                    return SlotSize.Illegal;
264            }
265        }
266
267        private EnumMap<SlotSize, Deque<StackSlot>> freeSlots;
268
269        /**
270         * @return The list of free stack slots for {@code size} or {@code null} if there is none.
271         */
272        private Deque<StackSlot> getOrNullFreeSlots(SlotSize size) {
273            if (freeSlots == null) {
274                return null;
275            }
276            return freeSlots.get(size);
277        }
278
279        /**
280         * @return the list of free stack slots for {@code size}. If there is none a list is
281         *         created.
282         */
283        private Deque<StackSlot> getOrInitFreeSlots(SlotSize size) {
284            assert size != SlotSize.Illegal;
285            Deque<StackSlot> freeList;
286            if (freeSlots != null) {
287                freeList = freeSlots.get(size);
288            } else {
289                freeSlots = new EnumMap<>(SlotSize.class);
290                freeList = null;
291            }
292            if (freeList == null) {
293                freeList = new ArrayDeque<>();
294                freeSlots.put(size, freeList);
295            }
296            assert freeList != null;
297            return freeList;
298        }
299
300        /**
301         * Gets a free stack slot for {@code slot} or {@code null} if there is none.
302         */
303        private StackSlot findFreeSlot(SimpleVirtualStackSlot slot) {
304            assert slot != null;
305            SlotSize size = forKind(slot.getLIRKind());
306            if (size == SlotSize.Illegal) {
307                return null;
308            }
309            Deque<StackSlot> freeList = getOrNullFreeSlots(size);
310            if (freeList == null) {
311                return null;
312            }
313            return freeList.pollLast();
314        }
315
316        /**
317         * Adds a stack slot to the list of free slots.
318         */
319        private void freeSlot(StackSlot slot) {
320            SlotSize size = forKind(slot.getLIRKind());
321            if (size == SlotSize.Illegal) {
322                return;
323            }
324            getOrInitFreeSlots(size).addLast(slot);
325        }
326
327        /**
328         * Gets the next unhandled interval and finishes handled intervals.
329         */
330        private StackInterval activateNext() {
331            if (unhandled.isEmpty()) {
332                return null;
333            }
334            StackInterval next = unhandled.poll();
335            // finish handled intervals
336            for (int id = next.from(); activePeekId() < id;) {
337                finished(active.poll());
338            }
339            Debug.log("active %s", next);
340            active.add(next);
341            return next;
342        }
343
344        /**
345         * Gets the lowest {@link StackInterval#to() end position} of all active intervals. If there
346         * is none {@link Integer#MAX_VALUE} is returned.
347         */
348        private int activePeekId() {
349            StackInterval first = active.peek();
350            if (first == null) {
351                return Integer.MAX_VALUE;
352            }
353            return first.to();
354        }
355
356        /**
357         * Finishes {@code interval} by adding its location to the list of free stack slots.
358         */
359        private void finished(StackInterval interval) {
360            StackSlot location = interval.location();
361            Debug.log("finished %s (freeing %s)", interval, location);
362            freeSlot(location);
363        }
364
365        // ====================
366        // step 5: assign stack slots
367        // ====================
368
369        private void assignStackSlots(Set<LIRInstruction> usePos) {
370            for (LIRInstruction op : usePos) {
371                op.forEachInput(assignSlot);
372                op.forEachAlive(assignSlot);
373                op.forEachState(assignSlot);
374
375                op.forEachTemp(assignSlot);
376                op.forEachOutput(assignSlot);
377            }
378        }
379
380        ValueProcedure assignSlot = new ValueProcedure() {
381            public Value doValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
382                if (isVirtualStackSlot(value)) {
383                    VirtualStackSlot slot = asVirtualStackSlot(value);
384                    StackInterval interval = get(slot);
385                    assert interval != null;
386                    return interval.location();
387                }
388                return value;
389            }
390        };
391
392        // ====================
393        //
394        // ====================
395
396        /**
397         * Gets the highest instruction id.
398         */
399        private int maxOpId() {
400            return maxOpId;
401        }
402
403        private StackInterval get(VirtualStackSlot stackSlot) {
404            return stackSlotMap[stackSlot.getId()];
405        }
406
407        private void forEachInterval(Consumer<StackInterval> proc) {
408            for (StackInterval interval : stackSlotMap) {
409                if (interval != null) {
410                    proc.accept(interval);
411                }
412            }
413        }
414
415        private void dumpIntervals(String label) {
416            Debug.dump(stackSlotMap, label);
417        }
418
419    }
420}