1 /* |
|
2 * Copyright (c) 2015, 2017, 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 |
|
24 |
|
25 package org.graalvm.compiler.lir.alloc.trace.lsra; |
|
26 |
|
27 import static jdk.vm.ci.code.ValueUtil.isRegister; |
|
28 import static org.graalvm.compiler.lir.LIRValueUtil.asVariable; |
|
29 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue; |
|
30 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable; |
|
31 |
|
32 import java.util.ArrayList; |
|
33 |
|
34 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig; |
|
35 import org.graalvm.compiler.core.common.alloc.Trace; |
|
36 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult; |
|
37 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; |
|
38 import org.graalvm.compiler.debug.Assertions; |
|
39 import org.graalvm.compiler.debug.DebugContext; |
|
40 import org.graalvm.compiler.debug.Indent; |
|
41 import org.graalvm.compiler.lir.LIRInsertionBuffer; |
|
42 import org.graalvm.compiler.lir.LIRInstruction; |
|
43 import org.graalvm.compiler.lir.LIRInstruction.OperandMode; |
|
44 import org.graalvm.compiler.lir.StandardOp.LoadConstantOp; |
|
45 import org.graalvm.compiler.lir.StandardOp.MoveOp; |
|
46 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp; |
|
47 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.SpillState; |
|
48 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.IntervalPredicate; |
|
49 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan; |
|
50 import org.graalvm.compiler.lir.gen.LIRGenerationResult; |
|
51 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory; |
|
52 |
|
53 import jdk.vm.ci.code.TargetDescription; |
|
54 import jdk.vm.ci.meta.AllocatableValue; |
|
55 |
|
56 final class TraceLinearScanEliminateSpillMovePhase extends TraceLinearScanAllocationPhase { |
|
57 |
|
58 private static final IntervalPredicate spilledIntervals = new TraceLinearScanPhase.IntervalPredicate() { |
|
59 |
|
60 @Override |
|
61 public boolean apply(TraceInterval i) { |
|
62 return i.isSplitParent() && SpillState.IN_MEMORY.contains(i.spillState()); |
|
63 } |
|
64 }; |
|
65 |
|
66 @Override |
|
67 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, Trace trace, MoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig, |
|
68 TraceBuilderResult traceBuilderResult, TraceLinearScan allocator) { |
|
69 boolean shouldEliminateSpillMoves = shouldEliminateSpillMoves(traceBuilderResult, allocator); |
|
70 eliminateSpillMoves(allocator, shouldEliminateSpillMoves, traceBuilderResult, lirGenRes); |
|
71 } |
|
72 |
|
73 private static boolean shouldEliminateSpillMoves(TraceBuilderResult traceBuilderResult, TraceLinearScan allocator) { |
|
74 return !traceBuilderResult.incomingSideEdges(traceBuilderResult.getTraceForBlock(allocator.blockAt(0))); |
|
75 } |
|
76 |
|
77 // called once before assignment of register numbers |
|
78 @SuppressWarnings("try") |
|
79 private static void eliminateSpillMoves(TraceLinearScan allocator, boolean shouldEliminateSpillMoves, TraceBuilderResult traceBuilderResult, LIRGenerationResult res) { |
|
80 DebugContext debug = allocator.getDebug(); |
|
81 try (Indent indent = debug.logAndIndent("Eliminating unnecessary spill moves: Trace%d", traceBuilderResult.getTraceForBlock(allocator.blockAt(0)).getId())) { |
|
82 allocator.sortIntervalsBySpillPos(); |
|
83 |
|
84 /* |
|
85 * collect all intervals that must be stored after their definition. The list is sorted |
|
86 * by Interval.spillDefinitionPos. |
|
87 */ |
|
88 TraceInterval interval = allocator.createUnhandledListBySpillPos(spilledIntervals); |
|
89 if (Assertions.detailedAssertionsEnabled(allocator.getOptions())) { |
|
90 checkIntervals(debug, interval); |
|
91 } |
|
92 if (debug.isLogEnabled()) { |
|
93 try (Indent indent2 = debug.logAndIndent("Sorted intervals")) { |
|
94 for (TraceInterval i = interval; i != null; i = i.next) { |
|
95 debug.log("%5d: %s", i.spillDefinitionPos(), i); |
|
96 } |
|
97 } |
|
98 } |
|
99 |
|
100 LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer(); |
|
101 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { |
|
102 try (Indent indent1 = debug.logAndIndent("Handle %s", block)) { |
|
103 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); |
|
104 int numInst = instructions.size(); |
|
105 |
|
106 int lastOpId = -1; |
|
107 // iterate all instructions of the block. |
|
108 for (int j = 0; j < numInst; j++) { |
|
109 LIRInstruction op = instructions.get(j); |
|
110 int opId = op.id(); |
|
111 try (Indent indent2 = debug.logAndIndent("%5d %s", opId, op)) { |
|
112 |
|
113 if (opId == -1) { |
|
114 MoveOp move = MoveOp.asMoveOp(op); |
|
115 /* |
|
116 * Remove move from register to stack if the stack slot is |
|
117 * guaranteed to be correct. Only moves that have been inserted by |
|
118 * LinearScan can be removed. |
|
119 */ |
|
120 if (shouldEliminateSpillMoves && canEliminateSpillMove(allocator, block, move, lastOpId)) { |
|
121 /* |
|
122 * Move target is a stack slot that is always correct, so |
|
123 * eliminate instruction. |
|
124 */ |
|
125 if (debug.isLogEnabled()) { |
|
126 if (ValueMoveOp.isValueMoveOp(op)) { |
|
127 ValueMoveOp vmove = ValueMoveOp.asValueMoveOp(op); |
|
128 debug.log("eliminating move from interval %s to %s in block %s", vmove.getInput(), vmove.getResult(), block); |
|
129 } else { |
|
130 LoadConstantOp load = LoadConstantOp.asLoadConstantOp(op); |
|
131 debug.log("eliminating constant load from %s to %s in block %s", load.getConstant(), load.getResult(), |
|
132 block); |
|
133 } |
|
134 } |
|
135 |
|
136 // null-instructions are deleted by assignRegNum |
|
137 instructions.set(j, null); |
|
138 } |
|
139 |
|
140 } else { |
|
141 lastOpId = opId; |
|
142 /* |
|
143 * Insert move from register to stack just after the beginning of |
|
144 * the interval. |
|
145 */ |
|
146 // assert interval == TraceInterval.EndMarker || |
|
147 // interval.spillDefinitionPos() >= opId : "invalid order"; |
|
148 assert interval == TraceInterval.EndMarker || (interval.isSplitParent() && SpillState.IN_MEMORY.contains(interval.spillState())) : "invalid interval"; |
|
149 |
|
150 while (interval != TraceInterval.EndMarker && interval.spillDefinitionPos() == opId) { |
|
151 debug.log("handle %s", interval); |
|
152 if (!interval.canMaterialize() && interval.spillState() != SpillState.StartInMemory) { |
|
153 |
|
154 AllocatableValue fromLocation = interval.getSplitChildAtOpId(opId, OperandMode.DEF).location(); |
|
155 AllocatableValue toLocation = allocator.canonicalSpillOpr(interval); |
|
156 if (!fromLocation.equals(toLocation)) { |
|
157 |
|
158 if (!insertionBuffer.initialized()) { |
|
159 /* |
|
160 * prepare insertion buffer (appended when all |
|
161 * instructions in the block are processed) |
|
162 */ |
|
163 insertionBuffer.init(instructions); |
|
164 } |
|
165 |
|
166 assert isRegister(fromLocation) : "from operand must be a register but is: " + fromLocation + " toLocation=" + toLocation + " spillState=" + |
|
167 interval.spillState(); |
|
168 assert isStackSlotValue(toLocation) : "to operand must be a stack slot"; |
|
169 |
|
170 LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation); |
|
171 insertionBuffer.append(j + 1, move); |
|
172 move.setComment(res, "TraceLSRAEliminateSpillMove: spill def pos"); |
|
173 |
|
174 if (debug.isLogEnabled()) { |
|
175 debug.log("inserting move after definition of interval %d to stack slot %s at opId %d", interval.operandNumber, interval.spillSlot(), opId); |
|
176 } |
|
177 } |
|
178 } |
|
179 interval = interval.next; |
|
180 } |
|
181 } |
|
182 } |
|
183 } // end of instruction iteration |
|
184 |
|
185 if (insertionBuffer.initialized()) { |
|
186 insertionBuffer.finish(); |
|
187 } |
|
188 } |
|
189 } // end of block iteration |
|
190 |
|
191 assert interval == TraceInterval.EndMarker : "missed an interval"; |
|
192 } |
|
193 } |
|
194 |
|
195 /** |
|
196 * @param allocator |
|
197 * @param block The block {@code move} is located in. |
|
198 * @param move Spill move. |
|
199 * @param lastOpId The id of last "normal" instruction before the spill move. (Spill moves have |
|
200 * no valid opId but -1.) |
|
201 */ |
|
202 private static boolean canEliminateSpillMove(TraceLinearScan allocator, AbstractBlockBase<?> block, MoveOp move, int lastOpId) { |
|
203 assert ((LIRInstruction) move).id() == -1 : "Not a spill move: " + move; |
|
204 assert isVariable(move.getResult()) : "LinearScan inserts only moves to variables: " + move; |
|
205 assert lastOpId >= 0 : "Invalid lastOpId: " + lastOpId; |
|
206 |
|
207 TraceInterval curInterval = allocator.intervalFor(asVariable(move.getResult())); |
|
208 |
|
209 if (!isRegister(curInterval.location()) && curInterval.inMemoryAt(lastOpId) && !isPhiResolutionMove(allocator, move)) { |
|
210 /* Phi resolution moves cannot be removed because they define the value. */ |
|
211 // TODO (je) check if the comment is still valid! |
|
212 assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location(); |
|
213 return true; |
|
214 } |
|
215 return false; |
|
216 } |
|
217 |
|
218 /** |
|
219 * Checks if a (spill or split) move is a Phi resolution move. |
|
220 * |
|
221 * A spill or split move connects a split parent or a split child with another split child. |
|
222 * Therefore the destination of the move is always a split child. Phi resolution moves look like |
|
223 * spill moves (i.e. {@link LIRInstruction#id() id} is {@code 0}, but they define a new |
|
224 * variable. As a result the destination interval is a split parent. |
|
225 */ |
|
226 private static boolean isPhiResolutionMove(TraceLinearScan allocator, MoveOp move) { |
|
227 assert ((LIRInstruction) move).id() == -1 : "Not a spill move: " + move; |
|
228 TraceInterval curInterval = allocator.intervalFor(asVariable(move.getResult())); |
|
229 return curInterval.isSplitParent(); |
|
230 } |
|
231 |
|
232 private static void checkIntervals(DebugContext debug, TraceInterval interval) { |
|
233 TraceInterval prev = null; |
|
234 TraceInterval temp = interval; |
|
235 while (temp != TraceInterval.EndMarker) { |
|
236 assert temp.spillDefinitionPos() >= 0 : "invalid spill definition pos " + temp; |
|
237 if (prev != null) { |
|
238 // assert temp.from() >= prev.from() : "intervals not sorted"; |
|
239 assert temp.spillDefinitionPos() >= prev.spillDefinitionPos() : "when intervals are sorted by from : then they must also be sorted by spillDefinitionPos"; |
|
240 } |
|
241 |
|
242 assert temp.spillSlot() != null || temp.canMaterialize() : "interval has no spill slot assigned"; |
|
243 assert temp.spillDefinitionPos() >= temp.from() : "invalid order"; |
|
244 // assert temp.spillDefinitionPos() <= temp.from() + 2 : |
|
245 // "only intervals defined once at their start-pos can be optimized"; |
|
246 |
|
247 if (debug.isLogEnabled()) { |
|
248 debug.log("interval %d (from %d to %d) must be stored at %d", temp.operandNumber, temp.from(), temp.to(), temp.spillDefinitionPos()); |
|
249 } |
|
250 |
|
251 prev = temp; |
|
252 temp = temp.next; |
|
253 } |
|
254 } |
|
255 |
|
256 } |
|