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 package org.graalvm.compiler.lir.alloc.trace.lsra;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue;
26 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
27 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
28 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
29 import static org.graalvm.compiler.lir.alloc.trace.TraceRegisterAllocationPhase.Options.TraceRAshareSpillInformation;
30 import static jdk.vm.ci.code.ValueUtil.isIllegal;
31 import static jdk.vm.ci.code.ValueUtil.isRegister;
32
33 import java.util.Collections;
34 import java.util.EnumSet;
35 import java.util.List;
36
37 import org.graalvm.compiler.core.common.alloc.Trace;
38 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
39 import org.graalvm.compiler.debug.Debug;
40 import org.graalvm.compiler.debug.GraalError;
41 import org.graalvm.compiler.debug.Indent;
42 import org.graalvm.compiler.lir.ConstantValue;
43 import org.graalvm.compiler.lir.InstructionValueProcedure;
44 import org.graalvm.compiler.lir.LIRFrameState;
45 import org.graalvm.compiler.lir.LIRInstruction;
46 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
47 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
48 import org.graalvm.compiler.lir.StandardOp;
49 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
50 import org.graalvm.compiler.lir.StandardOp.LabelOp;
51 import org.graalvm.compiler.lir.StandardOp.MoveOp;
52 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp;
53 import org.graalvm.compiler.lir.Variable;
54 import org.graalvm.compiler.lir.alloc.trace.ShadowedRegisterValue;
55 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
56 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
57 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
58
59 import jdk.vm.ci.code.RegisterValue;
60 import jdk.vm.ci.code.StackSlot;
61 import jdk.vm.ci.code.TargetDescription;
62 import jdk.vm.ci.meta.AllocatableValue;
63 import jdk.vm.ci.meta.Value;
64
65 /**
66 * Specialization of {@link org.graalvm.compiler.lir.alloc.lsra.LinearScanAssignLocationsPhase} that
67 * inserts {@link ShadowedRegisterValue}s to describe {@link RegisterValue}s that are also available
68 * on the {@link StackSlot stack}.
69 */
70 final class TraceLinearScanAssignLocationsPhase extends TraceLinearScanAllocationPhase {
71
72 @Override
73 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, Trace trace, TraceLinearScanAllocationContext context) {
74 TraceLinearScan allocator = context.allocator;
75 MoveFactory spillMoveFactory = context.spillMoveFactory;
76 new Assigner(allocator, spillMoveFactory).assignLocations();
77 }
78
79 private static final class Assigner {
80 private final TraceLinearScan allocator;
81 private final MoveFactory spillMoveFactory;
82
83 private Assigner(TraceLinearScan allocator, MoveFactory spillMoveFactory) {
84 this.allocator = allocator;
85 this.spillMoveFactory = spillMoveFactory;
86 }
87
88 /**
89 * Assigns the allocated location for an LIR instruction operand back into the instruction.
90 *
91 * @param op current {@link LIRInstruction}
92 * @param operand an LIR instruction operand
93 * @param mode the usage mode for {@code operand} by the instruction
94 * @return the location assigned for the operand
95 */
96 private Value colorLirOperand(LIRInstruction op, Variable operand, OperandMode mode) {
97 int opId = op.id();
98 TraceInterval interval = allocator.intervalFor(operand);
99 assert interval != null : "interval must exist";
100
101 if (opId != -1) {
102 /*
103 * Operands are not changed when an interval is split during allocation, so search
104 * the right interval here.
105 */
106 interval = allocator.splitChildAtOpId(interval, opId, mode);
107 }
108
109 if (isIllegal(interval.location()) && interval.canMaterialize()) {
110 if (op instanceof LabelOp) {
111 /*
112 * Spilled materialized value in a LabelOp (i.e. incoming): no need for move
113 * resolution so we can ignore it.
114 */
115 return Value.ILLEGAL;
116 }
117 assert mode != OperandMode.DEF;
118 return new ConstantValue(interval.kind(), interval.getMaterializedValue());
119 }
120 return interval.location();
121 }
122
123 /**
124 * @param op
125 * @param operand
126 * @param valueMode
127 * @param flags
128 * @see InstructionValueProcedure#doValue(LIRInstruction, Value, OperandMode, EnumSet)
146 final LIRInstruction instr = allocator.getLIR().getLIRforBlock(block).get(allocator.getLIR().getLIRforBlock(block).size() - 1);
147 if (instr instanceof StandardOp.JumpOp) {
148 throw GraalError.unimplemented("DebugInfo on jumps are not supported!");
149 }
150 }
151
152 /*
153 * Get current location of operand. The operand must be live because debug information
154 * is considered when building the intervals if the interval is not live,
155 * colorLirOperand will cause an assert on failure.
156 */
157 Value result = colorLirOperand(op, (Variable) operand, mode);
158 assert !allocator.hasCall(tempOpId) || isStackSlotValue(result) || isConstantValue(result) || !allocator.isCallerSave(result) : "cannot have caller-save register operands at calls";
159 return result;
160 }
161
162 private void computeDebugInfo(final LIRInstruction op, LIRFrameState info) {
163 info.forEachState(op, this::debugInfoProcedure);
164 }
165
166 private void assignLocations(List<LIRInstruction> instructions) {
167 int numInst = instructions.size();
168 boolean hasDead = false;
169
170 for (int j = 0; j < numInst; j++) {
171 final LIRInstruction op = instructions.get(j);
172 if (op == null) {
173 /*
174 * this can happen when spill-moves are removed in eliminateSpillMoves
175 */
176 hasDead = true;
177 } else if (assignLocations(op, instructions, j)) {
178 hasDead = true;
179 }
180 }
181
182 if (hasDead) {
183 // Remove null values from the list.
184 instructions.removeAll(Collections.singleton(null));
185 }
186 }
187
188 private final InstructionValueProcedure assignProc = new InstructionValueProcedure() {
189 @Override
190 public Value doValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
191 if (isVariable(value)) {
192 return colorLirOperand(instruction, (Variable) value, mode);
193 }
194 return value;
195 }
196 };
197
198 /**
199 * Assigns the operand of an {@link LIRInstruction}.
200 *
201 * @param op The {@link LIRInstruction} that should be colored.
202 * @param j The index of {@code op} in the {@code instructions} list.
203 * @param instructions The instructions of the current block.
204 * @return {@code true} if the instruction was deleted.
205 */
206 private boolean assignLocations(LIRInstruction op, List<LIRInstruction> instructions, int j) {
207 assert op != null && instructions.get(j) == op;
208 if (TraceRAshareSpillInformation.getValue()) {
209 if (op instanceof BlockEndOp) {
210 ((BlockEndOp) op).forEachOutgoingValue(colorOutgoingIncomingValues);
211 } else if (op instanceof LabelOp) {
212 ((LabelOp) op).forEachIncomingValue(colorOutgoingIncomingValues);
213 }
214 }
215
216 // remove useless moves
217 if (op instanceof MoveOp) {
218 AllocatableValue result = ((MoveOp) op).getResult();
219 if (isVariable(result) && allocator.isMaterialized(result, op.id(), OperandMode.DEF)) {
220 /*
221 * This happens if a materializable interval is originally not spilled but then
222 * kicked out in LinearScanWalker.splitForSpilling(). When kicking out such an
223 * interval this move operation was already generated.
224 */
225 instructions.set(j, null);
226 return true;
227 }
228 }
229
230 op.forEachInput(assignProc);
231 op.forEachAlive(assignProc);
232 op.forEachTemp(assignProc);
233 op.forEachOutput(assignProc);
234
235 // compute reference map and debug information
236 op.forEachState((inst, state) -> computeDebugInfo(inst, state));
237
238 // remove useless moves
239 if (op instanceof ValueMoveOp) {
240 ValueMoveOp move = (ValueMoveOp) op;
241 if (move.getInput().equals(move.getResult())) {
242 instructions.set(j, null);
243 return true;
244 }
245 if (isStackSlotValue(move.getInput()) && isStackSlotValue(move.getResult())) {
246 // rewrite stack to stack moves
247 instructions.set(j, spillMoveFactory.createStackMove(move.getResult(), move.getInput()));
248 return true;
249 }
250 }
251 return false;
252 }
253
254 @SuppressWarnings("try")
255 private void assignLocations() {
256 try (Indent indent = Debug.logAndIndent("assign locations")) {
257 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
258 try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) {
259 assignLocations(allocator.getLIR().getLIRforBlock(block));
260 }
261 }
262 }
263 }
264
265 private final InstructionValueProcedure colorOutgoingIncomingValues = new InstructionValueProcedure() {
266
267 @Override
268 public Value doValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
269 if (isVariable(value)) {
270 TraceInterval interval = allocator.intervalFor(value);
271 assert interval != null : "interval must exist";
272 interval = allocator.splitChildAtOpId(interval, instruction.id(), mode);
273
274 if (interval.inMemoryAt(instruction.id()) && isRegister(interval.location())) {
275 return new ShadowedRegisterValue((RegisterValue) interval.location(), interval.spillSlot());
276 }
277 }
278 return value;
279 }
280 };
281 }
282 }
|
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 package org.graalvm.compiler.lir.alloc.trace.lsra;
24
25 import static jdk.vm.ci.code.ValueUtil.isIllegal;
26 import static jdk.vm.ci.code.ValueUtil.isRegister;
27 import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue;
28 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
29 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
30 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
31
32 import java.util.ArrayList;
33 import java.util.Collections;
34 import java.util.EnumSet;
35
36 import org.graalvm.compiler.core.common.alloc.Trace;
37 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
38 import org.graalvm.compiler.debug.Debug;
39 import org.graalvm.compiler.debug.GraalError;
40 import org.graalvm.compiler.debug.Indent;
41 import org.graalvm.compiler.lir.ConstantValue;
42 import org.graalvm.compiler.lir.InstructionValueProcedure;
43 import org.graalvm.compiler.lir.LIRFrameState;
44 import org.graalvm.compiler.lir.LIRInstruction;
45 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
46 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
47 import org.graalvm.compiler.lir.StandardOp;
48 import org.graalvm.compiler.lir.StandardOp.LabelOp;
49 import org.graalvm.compiler.lir.StandardOp.MoveOp;
50 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp;
51 import org.graalvm.compiler.lir.Variable;
52 import org.graalvm.compiler.lir.alloc.trace.GlobalLivenessInfo;
53 import org.graalvm.compiler.lir.alloc.trace.ShadowedRegisterValue;
54 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
55 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
56 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
57
58 import jdk.vm.ci.code.RegisterValue;
59 import jdk.vm.ci.code.StackSlot;
60 import jdk.vm.ci.code.TargetDescription;
61 import jdk.vm.ci.meta.AllocatableValue;
62 import jdk.vm.ci.meta.Value;
63
64 /**
65 * Specialization of {@link org.graalvm.compiler.lir.alloc.lsra.LinearScanAssignLocationsPhase} that
66 * inserts {@link ShadowedRegisterValue}s to describe {@link RegisterValue}s that are also available
67 * on the {@link StackSlot stack}.
68 */
69 final class TraceLinearScanAssignLocationsPhase extends TraceLinearScanAllocationPhase {
70
71 @Override
72 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, Trace trace, TraceLinearScanAllocationContext context) {
73 TraceLinearScan allocator = context.allocator;
74 MoveFactory spillMoveFactory = context.spillMoveFactory;
75 new Assigner(allocator, spillMoveFactory).assign();
76 }
77
78 private static final class Assigner {
79 private final TraceLinearScan allocator;
80 private final MoveFactory spillMoveFactory;
81
82 private Assigner(TraceLinearScan allocator, MoveFactory spillMoveFactory) {
83 this.allocator = allocator;
84 this.spillMoveFactory = spillMoveFactory;
85 }
86
87 /**
88 * Assigns the allocated location for an LIR instruction operand back into the instruction.
89 *
90 * @param op current {@link LIRInstruction}
91 * @param operand an LIR instruction operand
92 * @param mode the usage mode for {@code operand} by the instruction
93 * @return the location assigned for the operand
94 */
95 private Value colorLirOperand(LIRInstruction op, Variable operand, OperandMode mode) {
96 int opId = op.id();
97 TraceInterval interval = allocator.intervalFor(operand);
98 assert interval != null : "interval must exist";
99
100 if (opId != -1) {
101 /*
102 * Operands are not changed when an interval is split during allocation, so search
103 * the right interval here.
104 */
105 interval = allocator.splitChildAtOpId(interval, opId, mode);
106 }
107
108 return getLocation(op, interval, mode);
109 }
110
111 private static Value getLocation(LIRInstruction op, TraceInterval interval, OperandMode mode) {
112 if (isIllegal(interval.location()) && interval.canMaterialize()) {
113 if (op instanceof LabelOp) {
114 /*
115 * Spilled materialized value in a LabelOp (i.e. incoming): no need for move
116 * resolution so we can ignore it.
117 */
118 return Value.ILLEGAL;
119 }
120 assert mode != OperandMode.DEF;
121 return new ConstantValue(interval.kind(), interval.getMaterializedValue());
122 }
123 return interval.location();
124 }
125
126 /**
127 * @param op
128 * @param operand
129 * @param valueMode
130 * @param flags
131 * @see InstructionValueProcedure#doValue(LIRInstruction, Value, OperandMode, EnumSet)
149 final LIRInstruction instr = allocator.getLIR().getLIRforBlock(block).get(allocator.getLIR().getLIRforBlock(block).size() - 1);
150 if (instr instanceof StandardOp.JumpOp) {
151 throw GraalError.unimplemented("DebugInfo on jumps are not supported!");
152 }
153 }
154
155 /*
156 * Get current location of operand. The operand must be live because debug information
157 * is considered when building the intervals if the interval is not live,
158 * colorLirOperand will cause an assert on failure.
159 */
160 Value result = colorLirOperand(op, (Variable) operand, mode);
161 assert !allocator.hasCall(tempOpId) || isStackSlotValue(result) || isConstantValue(result) || !allocator.isCallerSave(result) : "cannot have caller-save register operands at calls";
162 return result;
163 }
164
165 private void computeDebugInfo(final LIRInstruction op, LIRFrameState info) {
166 info.forEachState(op, this::debugInfoProcedure);
167 }
168
169 @SuppressWarnings("try")
170 private void assignBlock(AbstractBlockBase<?> block) {
171 try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) {
172 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
173 handleBlockBegin(block, instructions);
174 int numInst = instructions.size();
175 boolean hasDead = false;
176
177 for (int j = 0; j < numInst; j++) {
178 final LIRInstruction op = instructions.get(j);
179 if (op == null) {
180 /*
181 * this can happen when spill-moves are removed in eliminateSpillMoves
182 */
183 hasDead = true;
184 } else if (assignLocations(op, instructions, j)) {
185 hasDead = true;
186 }
187 }
188 handleBlockEnd(block, instructions);
189
190 if (hasDead) {
191 // Remove null values from the list.
192 instructions.removeAll(Collections.singleton(null));
193 }
194 }
195 }
196
197 private void handleBlockBegin(AbstractBlockBase<?> block, ArrayList<LIRInstruction> instructions) {
198 if (allocator.hasInterTracePredecessor(block)) {
199 /* Only materialize the locations array if there is an incoming inter-trace edge. */
200 assert instructions.equals(allocator.getLIR().getLIRforBlock(block));
201 GlobalLivenessInfo li = allocator.getGlobalLivenessInfo();
202 LIRInstruction instruction = instructions.get(0);
203 OperandMode mode = OperandMode.DEF;
204 int[] live = li.getBlockIn(block);
205 Value[] values = calculateBlockBoundaryValues(instruction, live, mode);
206 li.setInLocations(block, values);
207 }
208 }
209
210 private void handleBlockEnd(AbstractBlockBase<?> block, ArrayList<LIRInstruction> instructions) {
211 if (allocator.hasInterTraceSuccessor(block)) {
212 /* Only materialize the locations array if there is an outgoing inter-trace edge. */
213 assert instructions.equals(allocator.getLIR().getLIRforBlock(block));
214 GlobalLivenessInfo li = allocator.getGlobalLivenessInfo();
215 LIRInstruction instruction = instructions.get(instructions.size() - 1);
216 OperandMode mode = OperandMode.USE;
217 int[] live = li.getBlockOut(block);
218 Value[] values = calculateBlockBoundaryValues(instruction, live, mode);
219 li.setOutLocations(block, values);
220 }
221 }
222
223 private Value[] calculateBlockBoundaryValues(LIRInstruction instruction, int[] live, OperandMode mode) {
224 Value[] values = new Value[live.length];
225 for (int i = 0; i < live.length; i++) {
226 TraceInterval interval = allocator.intervalFor(live[i]);
227 Value val = valueAtBlockBoundary(instruction, interval, mode);
228 values[i] = val;
229 }
230 return values;
231 }
232
233 private static Value valueAtBlockBoundary(LIRInstruction instruction, TraceInterval interval, OperandMode mode) {
234 if (mode == OperandMode.DEF && interval == null) {
235 // not needed in this trace
236 return Value.ILLEGAL;
237 }
238 assert interval != null : "interval must exist";
239 TraceInterval splitInterval = interval.getSplitChildAtOpIdOrNull(instruction.id(), mode);
240 if (splitInterval == null) {
241 assert mode == OperandMode.DEF : String.format("Not split child at %d for interval %s", instruction.id(), interval);
242 // not needed in this branch
243 return Value.ILLEGAL;
244 }
245
246 if (splitInterval.inMemoryAt(instruction.id()) && isRegister(splitInterval.location())) {
247 return new ShadowedRegisterValue((RegisterValue) splitInterval.location(), splitInterval.spillSlot());
248 }
249 return getLocation(instruction, splitInterval, mode);
250 }
251
252 private final InstructionValueProcedure assignProc = new InstructionValueProcedure() {
253 @Override
254 public Value doValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
255 if (isVariable(value)) {
256 return colorLirOperand(instruction, (Variable) value, mode);
257 }
258 return value;
259 }
260 };
261
262 /**
263 * Assigns the operand of an {@link LIRInstruction}.
264 *
265 * @param op The {@link LIRInstruction} that should be colored.
266 * @param j The index of {@code op} in the {@code instructions} list.
267 * @param instructions The instructions of the current block.
268 * @return {@code true} if the instruction was deleted.
269 */
270 private boolean assignLocations(LIRInstruction op, ArrayList<LIRInstruction> instructions, int j) {
271 assert op != null && instructions.get(j) == op;
272
273 // remove useless moves
274 if (op instanceof MoveOp) {
275 AllocatableValue result = ((MoveOp) op).getResult();
276 if (isVariable(result) && allocator.isMaterialized(result, op.id(), OperandMode.DEF)) {
277 /*
278 * This happens if a materializable interval is originally not spilled but then
279 * kicked out in LinearScanWalker.splitForSpilling(). When kicking out such an
280 * interval this move operation was already generated.
281 */
282 instructions.set(j, null);
283 return true;
284 }
285 }
286
287 op.forEachInput(assignProc);
288 op.forEachAlive(assignProc);
289 op.forEachTemp(assignProc);
290 op.forEachOutput(assignProc);
291
292 // compute reference map and debug information
293 op.forEachState((inst, state) -> computeDebugInfo(inst, state));
294
295 // remove useless moves
296 if (op instanceof ValueMoveOp) {
297 ValueMoveOp move = (ValueMoveOp) op;
298 if (move.getInput().equals(move.getResult())) {
299 instructions.set(j, null);
300 return true;
301 }
302 if (isStackSlotValue(move.getInput()) && isStackSlotValue(move.getResult())) {
303 // rewrite stack to stack moves
304 instructions.set(j, spillMoveFactory.createStackMove(move.getResult(), move.getInput()));
305 }
306 }
307 return false;
308 }
309
310 @SuppressWarnings("try")
311 private void assign() {
312 try (Indent indent = Debug.logAndIndent("assign locations")) {
313 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
314 assignBlock(block);
315 }
316 }
317 }
318 }
319 }
|