LinearScanEliminateSpillMovePhase.java revision 12657:6ef01bd40ce2 
1/*
2 * Copyright (c) 2015, 2015, 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.alloc.lsra;
24
25import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
26import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
27import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
28import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization;
29import static jdk.vm.ci.code.ValueUtil.isRegister;
30
31import java.util.List;
32
33import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
34import org.graalvm.compiler.debug.Debug;
35import org.graalvm.compiler.debug.Indent;
36import org.graalvm.compiler.lir.LIRInsertionBuffer;
37import org.graalvm.compiler.lir.LIRInstruction;
38import org.graalvm.compiler.lir.StandardOp.LoadConstantOp;
39import org.graalvm.compiler.lir.StandardOp.MoveOp;
40import org.graalvm.compiler.lir.StandardOp.ValueMoveOp;
41import org.graalvm.compiler.lir.alloc.lsra.Interval.SpillState;
42import org.graalvm.compiler.lir.alloc.lsra.LinearScan.IntervalPredicate;
43import org.graalvm.compiler.lir.gen.LIRGenerationResult;
44import org.graalvm.compiler.lir.phases.AllocationPhase;
45import org.graalvm.compiler.options.NestedBooleanOptionValue;
46import org.graalvm.compiler.options.Option;
47import org.graalvm.compiler.options.OptionType;
48import org.graalvm.compiler.options.OptionValue;
49
50import jdk.vm.ci.code.TargetDescription;
51import jdk.vm.ci.meta.AllocatableValue;
52
53public class LinearScanEliminateSpillMovePhase extends AllocationPhase {
54
55    public static class Options {
56        // @formatter:off
57        @Option(help = "Enable spill move elimination.", type = OptionType.Debug)
58        public static final OptionValue<Boolean> LIROptLSRAEliminateSpillMoves = new NestedBooleanOptionValue(LIROptimization, true);
59        // @formatter:on
60    }
61
62    private static final IntervalPredicate mustStoreAtDefinition = new LinearScan.IntervalPredicate() {
63
64        @Override
65        public boolean apply(Interval i) {
66            return i.isSplitParent() && i.spillState() == SpillState.StoreAtDefinition;
67        }
68    };
69
70    protected final LinearScan allocator;
71
72    protected LinearScanEliminateSpillMovePhase(LinearScan allocator) {
73        this.allocator = allocator;
74    }
75
76    @Override
77    protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
78        eliminateSpillMoves();
79    }
80
81    /**
82     * @return the index of the first instruction that is of interest for
83     *         {@link #eliminateSpillMoves()}
84     */
85    protected int firstInstructionOfInterest() {
86        // skip the first because it is always a label
87        return 1;
88    }
89
90    // called once before assignment of register numbers
91    @SuppressWarnings("try")
92    void eliminateSpillMoves() {
93        try (Indent indent = Debug.logAndIndent("Eliminating unnecessary spill moves")) {
94
95            /*
96             * collect all intervals that must be stored after their definition. The list is sorted
97             * by Interval.spillDefinitionPos.
98             */
99            Interval interval;
100            interval = allocator.createUnhandledLists(mustStoreAtDefinition, null).first;
101            if (DetailedAsserts.getValue()) {
102                checkIntervals(interval);
103            }
104
105            LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer();
106            for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
107                try (Indent indent1 = Debug.logAndIndent("Handle %s", block)) {
108                    List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
109                    int numInst = instructions.size();
110
111                    // iterate all instructions of the block.
112                    for (int j = firstInstructionOfInterest(); j < numInst; j++) {
113                        LIRInstruction op = instructions.get(j);
114                        int opId = op.id();
115
116                        if (opId == -1) {
117                            MoveOp move = (MoveOp) op;
118                            /*
119                             * Remove move from register to stack if the stack slot is guaranteed to
120                             * be correct. Only moves that have been inserted by LinearScan can be
121                             * removed.
122                             */
123                            if (Options.LIROptLSRAEliminateSpillMoves.getValue() && canEliminateSpillMove(block, move)) {
124                                /*
125                                 * Move target is a stack slot that is always correct, so eliminate
126                                 * instruction.
127                                 */
128                                if (Debug.isLogEnabled()) {
129                                    if (move instanceof ValueMoveOp) {
130                                        ValueMoveOp vmove = (ValueMoveOp) move;
131                                        Debug.log("eliminating move from interval %d (%s) to %d (%s) in block %s", allocator.operandNumber(vmove.getInput()), vmove.getInput(),
132                                                        allocator.operandNumber(vmove.getResult()), vmove.getResult(), block);
133                                    } else {
134                                        LoadConstantOp load = (LoadConstantOp) move;
135                                        Debug.log("eliminating constant load from %s to %d (%s) in block %s", load.getConstant(), allocator.operandNumber(load.getResult()), load.getResult(), block);
136                                    }
137                                }
138
139                                // null-instructions are deleted by assignRegNum
140                                instructions.set(j, null);
141                            }
142
143                        } else {
144                            /*
145                             * Insert move from register to stack just after the beginning of the
146                             * interval.
147                             */
148                            assert interval == Interval.EndMarker || interval.spillDefinitionPos() >= opId : "invalid order";
149                            assert interval == Interval.EndMarker || (interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) : "invalid interval";
150
151                            while (interval != Interval.EndMarker && interval.spillDefinitionPos() == opId) {
152                                if (!interval.canMaterialize()) {
153                                    if (!insertionBuffer.initialized()) {
154                                        /*
155                                         * prepare insertion buffer (appended when all instructions
156                                         * in the block are processed)
157                                         */
158                                        insertionBuffer.init(instructions);
159                                    }
160
161                                    AllocatableValue fromLocation = interval.location();
162                                    AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval);
163                                    if (!fromLocation.equals(toLocation)) {
164
165                                        assert isRegister(fromLocation) : "from operand must be a register but is: " + fromLocation + " toLocation=" + toLocation + " spillState=" +
166                                                        interval.spillState();
167                                        assert isStackSlotValue(toLocation) : "to operand must be a stack slot";
168
169                                        LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation);
170                                        insertionBuffer.append(j + 1, move);
171
172                                        if (Debug.isLogEnabled()) {
173                                            Debug.log("inserting move after definition of interval %d to stack slot %s at opId %d", interval.operandNumber, interval.spillSlot(), opId);
174                                        }
175                                    }
176                                }
177                                interval = interval.next;
178                            }
179                        }
180                    } // end of instruction iteration
181
182                    if (insertionBuffer.initialized()) {
183                        insertionBuffer.finish();
184                    }
185                }
186            } // end of block iteration
187
188            assert interval == Interval.EndMarker : "missed an interval";
189        }
190    }
191
192    /**
193     * @param block The block {@code move} is located in.
194     * @param move Spill move.
195     */
196    protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) {
197        assert isVariable(move.getResult()) : "LinearScan inserts only moves to variables: " + move;
198
199        Interval curInterval = allocator.intervalFor(move.getResult());
200
201        if (!isRegister(curInterval.location()) && curInterval.alwaysInMemory()) {
202            assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location();
203            return true;
204        }
205        return false;
206    }
207
208    private static void checkIntervals(Interval interval) {
209        Interval prev = null;
210        Interval temp = interval;
211        while (temp != Interval.EndMarker) {
212            assert temp.spillDefinitionPos() > 0 : "invalid spill definition pos";
213            if (prev != null) {
214                assert temp.from() >= prev.from() : "intervals not sorted";
215                assert temp.spillDefinitionPos() >= prev.spillDefinitionPos() : "when intervals are sorted by from :  then they must also be sorted by spillDefinitionPos";
216            }
217
218            assert temp.spillSlot() != null || temp.canMaterialize() : "interval has no spill slot assigned";
219            assert temp.spillDefinitionPos() >= temp.from() : "invalid order";
220            assert temp.spillDefinitionPos() <= temp.from() + 2 : "only intervals defined once at their start-pos can be optimized";
221
222            if (Debug.isLogEnabled()) {
223                Debug.log("interval %d (from %d to %d) must be stored at %d", temp.operandNumber, temp.from(), temp.to(), temp.spillDefinitionPos());
224            }
225
226            prev = temp;
227            temp = temp.next;
228        }
229    }
230
231}
232