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