001/*
002 * Copyright (c) 2015, 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.alloc.lsra;
024
025import static com.oracle.graal.compiler.common.cfg.AbstractControlFlowGraph.*;
026import static jdk.internal.jvmci.code.ValueUtil.*;
027
028import java.util.*;
029
030import jdk.internal.jvmci.code.*;
031import com.oracle.graal.debug.*;
032import jdk.internal.jvmci.meta.*;
033
034import com.oracle.graal.compiler.common.alloc.*;
035import com.oracle.graal.compiler.common.cfg.*;
036import com.oracle.graal.lir.*;
037import com.oracle.graal.lir.LIRInstruction.OperandMode;
038import com.oracle.graal.lir.alloc.lsra.Interval.SpillState;
039import com.oracle.graal.lir.gen.*;
040import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
041import com.oracle.graal.lir.phases.*;
042
043public final class LinearScanOptimizeSpillPositionPhase extends AllocationPhase {
044
045    private static final DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition");
046    private static final DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability");
047
048    private final LinearScan allocator;
049
050    LinearScanOptimizeSpillPositionPhase(LinearScan allocator) {
051        this.allocator = allocator;
052    }
053
054    @Override
055    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory,
056                    RegisterAllocationConfig registerAllocationConfig) {
057        optimizeSpillPosition();
058        allocator.printIntervals("After optimize spill position");
059    }
060
061    private void optimizeSpillPosition() {
062        try (Indent indent0 = Debug.logAndIndent("OptimizeSpillPositions")) {
063            LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.getLIR().linearScanOrder().size()];
064            for (Interval interval : allocator.intervals()) {
065                optimizeInterval(insertionBuffers, interval);
066            }
067            for (LIRInsertionBuffer insertionBuffer : insertionBuffers) {
068                if (insertionBuffer != null) {
069                    assert insertionBuffer.initialized() : "Insertion buffer is nonnull but not initialized!";
070                    insertionBuffer.finish();
071                }
072            }
073        }
074    }
075
076    private void optimizeInterval(LIRInsertionBuffer[] insertionBuffers, Interval interval) {
077        if (interval == null || !interval.isSplitParent() || interval.spillState() != SpillState.SpillInDominator) {
078            return;
079        }
080        AbstractBlockBase<?> defBlock = allocator.blockForId(interval.spillDefinitionPos());
081        AbstractBlockBase<?> spillBlock = null;
082        Interval firstSpillChild = null;
083        try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) {
084            for (Interval splitChild : interval.getSplitChildren()) {
085                if (isStackSlotValue(splitChild.location())) {
086                    if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) {
087                        firstSpillChild = splitChild;
088                    } else {
089                        assert firstSpillChild.from() < splitChild.from();
090                    }
091                    // iterate all blocks where the interval has use positions
092                    for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) {
093                        if (dominates(defBlock, splitBlock)) {
094                            Debug.log("Split interval %s, block %s", splitChild, splitBlock);
095                            if (spillBlock == null) {
096                                spillBlock = splitBlock;
097                            } else {
098                                spillBlock = commonDominator(spillBlock, splitBlock);
099                                assert spillBlock != null;
100                            }
101                        }
102                    }
103                }
104            }
105            if (spillBlock == null) {
106                Debug.log("not spill interval found");
107                // no spill interval
108                interval.setSpillState(SpillState.StoreAtDefinition);
109                return;
110            }
111            Debug.log(3, "Spill block candidate (initial): %s", spillBlock);
112            // move out of loops
113            if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) {
114                spillBlock = moveSpillOutOfLoop(defBlock, spillBlock);
115            }
116            Debug.log(3, "Spill block candidate (after loop optimizaton): %s", spillBlock);
117
118            /*
119             * The spill block is the begin of the first split child (aka the value is on the
120             * stack).
121             *
122             * The problem is that if spill block has more than one predecessor, the values at the
123             * end of the predecessors might differ. Therefore, we would need a spill move in all
124             * predecessors. To avoid this we spill in the dominator.
125             */
126            assert firstSpillChild != null;
127            if (!defBlock.equals(spillBlock) && spillBlock.equals(allocator.blockForId(firstSpillChild.from()))) {
128                AbstractBlockBase<?> dom = spillBlock.getDominator();
129                if (Debug.isLogEnabled()) {
130                    Debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom);
131                }
132                spillBlock = dom;
133            }
134            if (defBlock.equals(spillBlock)) {
135                Debug.log(3, "Definition is the best choice: %s", defBlock);
136                // definition is the best choice
137                interval.setSpillState(SpillState.StoreAtDefinition);
138                return;
139            }
140            assert dominates(defBlock, spillBlock);
141            betterSpillPos.increment();
142            if (Debug.isLogEnabled()) {
143                Debug.log("Better spill position found (Block %s)", spillBlock);
144            }
145
146            if (defBlock.probability() <= spillBlock.probability()) {
147                Debug.log(3, "Definition has lower probability %s (%f) is lower than spill block %s (%f)", defBlock, defBlock.probability(), spillBlock, spillBlock.probability());
148                // better spill block has the same probability -> do nothing
149                interval.setSpillState(SpillState.StoreAtDefinition);
150                return;
151            }
152
153            LIRInsertionBuffer insertionBuffer = insertionBuffers[spillBlock.getId()];
154            if (insertionBuffer == null) {
155                insertionBuffer = new LIRInsertionBuffer();
156                insertionBuffers[spillBlock.getId()] = insertionBuffer;
157                insertionBuffer.init(allocator.getLIR().getLIRforBlock(spillBlock));
158            }
159            int spillOpId = allocator.getFirstLirInstructionId(spillBlock);
160            // insert spill move
161            AllocatableValue fromLocation = interval.getSplitChildAtOpId(spillOpId, OperandMode.DEF, allocator).location();
162            AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval);
163            LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation);
164            Debug.log(3, "Insert spill move %s", move);
165            move.setId(LinearScan.DOMINATOR_SPILL_MOVE_ID);
166            /*
167             * We can use the insertion buffer directly because we always insert at position 1.
168             */
169            insertionBuffer.append(1, move);
170
171            betterSpillPosWithLowerProbability.increment();
172            interval.setSpillDefinitionPos(spillOpId);
173        }
174    }
175
176    /**
177     * Iterate over all {@link AbstractBlockBase blocks} of an interval.
178     */
179    private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> {
180
181        Range range;
182        AbstractBlockBase<?> block;
183
184        public IntervalBlockIterator(Interval interval) {
185            range = interval.first();
186            block = allocator.blockForId(range.from);
187        }
188
189        public AbstractBlockBase<?> next() {
190            AbstractBlockBase<?> currentBlock = block;
191            int nextBlockIndex = block.getLinearScanNumber() + 1;
192            if (nextBlockIndex < allocator.sortedBlocks().size()) {
193                block = allocator.sortedBlocks().get(nextBlockIndex);
194                if (range.to <= allocator.getFirstLirInstructionId(block)) {
195                    range = range.next;
196                    if (range == Range.EndMarker) {
197                        block = null;
198                    } else {
199                        block = allocator.blockForId(range.from);
200                    }
201                }
202            } else {
203                block = null;
204            }
205            return currentBlock;
206        }
207
208        public boolean hasNext() {
209            return block != null;
210        }
211    }
212
213    private Iterable<AbstractBlockBase<?>> blocksForInterval(Interval interval) {
214        return new Iterable<AbstractBlockBase<?>>() {
215            public Iterator<AbstractBlockBase<?>> iterator() {
216                return new IntervalBlockIterator(interval);
217            }
218        };
219    }
220
221    private static AbstractBlockBase<?> moveSpillOutOfLoop(AbstractBlockBase<?> defBlock, AbstractBlockBase<?> spillBlock) {
222        int defLoopDepth = defBlock.getLoopDepth();
223        for (AbstractBlockBase<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) {
224            assert block != null : "spill block not dominated by definition block?";
225            if (block.getLoopDepth() <= defLoopDepth) {
226                assert block.getLoopDepth() == defLoopDepth : "Cannot spill an interval outside of the loop where it is defined!";
227                return block;
228            }
229        }
230        return defBlock;
231    }
232}