1 /*
2 * Copyright (c) 2015, 2016, 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 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)
129 */
130 private Value debugInfoProcedure(LIRInstruction op, Value operand, OperandMode valueMode, EnumSet<OperandFlag> flags) {
131 if (isVirtualStackSlot(operand)) {
132 return operand;
133 }
134 int tempOpId = op.id();
135 OperandMode mode = OperandMode.USE;
136 AbstractBlockBase<?> block = allocator.blockForId(tempOpId);
137 if (block.getSuccessorCount() == 1 && tempOpId == allocator.getLastLirInstructionId(block)) {
138 /*
139 * Generating debug information for the last instruction of a block. If this
140 * instruction is a branch, spill moves are inserted before this branch and so the
141 * wrong operand would be returned (spill moves at block boundaries are not
142 * considered in the live ranges of intervals).
143 *
144 * Solution: use the first opId of the branch target block instead.
145 */
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 }