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 */
23 package org.graalvm.compiler.lir.alloc.lsra;
24
25 import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
26 import static org.graalvm.compiler.lir.LIRValueUtil.isJavaConstant;
27 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
28 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
29 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
30 import static jdk.vm.ci.code.ValueUtil.isIllegal;
31
32 import java.util.Collections;
33 import java.util.EnumSet;
34 import java.util.List;
35
36 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
37 import org.graalvm.compiler.debug.Debug;
38 import org.graalvm.compiler.debug.Indent;
39 import org.graalvm.compiler.lir.ConstantValue;
40 import org.graalvm.compiler.lir.InstructionValueProcedure;
41 import org.graalvm.compiler.lir.LIRFrameState;
42 import org.graalvm.compiler.lir.LIRInstruction;
43 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
44 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
45 import org.graalvm.compiler.lir.StandardOp;
46 import org.graalvm.compiler.lir.StandardOp.MoveOp;
47 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp;
48 import org.graalvm.compiler.lir.Variable;
49 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
50 import org.graalvm.compiler.lir.phases.AllocationPhase;
51
52 import jdk.vm.ci.code.TargetDescription;
53 import jdk.vm.ci.meta.AllocatableValue;
54 import jdk.vm.ci.meta.Value;
55
56 /**
57 * Phase 7: Assign register numbers back to LIR.
58 */
59 public class LinearScanAssignLocationsPhase extends AllocationPhase {
60
61 protected final LinearScan allocator;
62
63 public LinearScanAssignLocationsPhase(LinearScan allocator) {
64 this.allocator = allocator;
65 }
66
67 @Override
68 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
69 assignLocations();
70 }
71
72 /**
73 * Assigns the allocated location for an LIR instruction operand back into the instruction.
74 *
75 * @param op current {@link LIRInstruction}
76 * @param operand an LIR instruction operand
77 * @param mode the usage mode for {@code operand} by the instruction
78 * @return the location assigned for the operand
79 */
80 protected Value colorLirOperand(LIRInstruction op, Variable operand, OperandMode mode) {
81 int opId = op.id();
82 Interval interval = allocator.intervalFor(operand);
83 assert interval != null : "interval must exist";
84
85 if (opId != -1) {
86 if (DetailedAsserts.getValue()) {
87 AbstractBlockBase<?> block = allocator.blockForId(opId);
88 if (block.getSuccessorCount() <= 1 && opId == allocator.getLastLirInstructionId(block)) {
89 /*
90 * Check if spill moves could have been appended at the end of this block, but
91 * before the branch instruction. So the split child information for this branch
92 * would be incorrect.
93 */
94 LIRInstruction instr = allocator.getLIR().getLIRforBlock(block).get(allocator.getLIR().getLIRforBlock(block).size() - 1);
95 if (instr instanceof StandardOp.JumpOp) {
96 if (allocator.getBlockData(block).liveOut.get(allocator.operandNumber(operand))) {
97 assert false : String.format(
98 "can't get split child for the last branch of a block because the information would be incorrect (moves are inserted before the branch in resolveDataFlow) block=%s, instruction=%s, operand=%s",
99 block, instr, operand);
100 }
101 }
102 }
103 }
104
105 /*
106 * Operands are not changed when an interval is split during allocation, so search the
107 * right interval here.
108 */
109 interval = allocator.splitChildAtOpId(interval, opId, mode);
110 }
111
112 if (isIllegal(interval.location()) && interval.canMaterialize()) {
113 assert mode != OperandMode.DEF;
114 return new ConstantValue(interval.kind(), interval.getMaterializedValue());
115 }
116 return interval.location();
117 }
118
119 /**
120 * @param op
121 * @param operand
122 * @param valueMode
123 * @param flags
124 * @see InstructionValueProcedure#doValue(LIRInstruction, Value, OperandMode, EnumSet)
125 */
126 private Value debugInfoProcedure(LIRInstruction op, Value operand, OperandMode valueMode, EnumSet<OperandFlag> flags) {
127 if (isVirtualStackSlot(operand)) {
128 return operand;
129 }
130 int tempOpId = op.id();
131 OperandMode mode = OperandMode.USE;
132 AbstractBlockBase<?> block = allocator.blockForId(tempOpId);
133 if (block.getSuccessorCount() == 1 && tempOpId == allocator.getLastLirInstructionId(block)) {
134 /*
135 * Generating debug information for the last instruction of a block. If this instruction
136 * is a branch, spill moves are inserted before this branch and so the wrong operand
137 * would be returned (spill moves at block boundaries are not considered in the live
138 * ranges of intervals).
139 *
140 * Solution: use the first opId of the branch target block instead.
141 */
142 final LIRInstruction instr = allocator.getLIR().getLIRforBlock(block).get(allocator.getLIR().getLIRforBlock(block).size() - 1);
143 if (instr instanceof StandardOp.JumpOp) {
144 if (allocator.getBlockData(block).liveOut.get(allocator.operandNumber(operand))) {
145 tempOpId = allocator.getFirstLirInstructionId(block.getSuccessors()[0]);
146 mode = OperandMode.DEF;
147 }
148 }
149 }
150
151 /*
152 * Get current location of operand. The operand must be live because debug information is
153 * considered when building the intervals if the interval is not live, colorLirOperand will
154 * cause an assert on failure.
155 */
156 Value result = colorLirOperand(op, (Variable) operand, mode);
157 assert !allocator.hasCall(tempOpId) || isStackSlotValue(result) || isJavaConstant(result) || !allocator.isCallerSave(result) : "cannot have caller-save register operands at calls";
158 return result;
159 }
160
161 private void computeDebugInfo(final LIRInstruction op, LIRFrameState info) {
162 info.forEachState(op, this::debugInfoProcedure);
163 }
164
165 private void assignLocations(List<LIRInstruction> instructions) {
166 int numInst = instructions.size();
167 boolean hasDead = false;
168
169 for (int j = 0; j < numInst; j++) {
170 final LIRInstruction op = instructions.get(j);
171 if (op == null) {
172 /*
173 * this can happen when spill-moves are removed in eliminateSpillMoves
174 */
175 hasDead = true;
176 } else if (assignLocations(op)) {
177 instructions.set(j, null);
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 /**
189 * Assigns the operand of an {@link LIRInstruction}.
190 *
191 * @param op The {@link LIRInstruction} that should be colored.
192 * @return {@code true} if the instruction should be deleted.
193 */
194 protected boolean assignLocations(LIRInstruction op) {
195 assert op != null;
196
197 InstructionValueProcedure assignProc = (inst, operand, mode, flags) -> isVariable(operand) ? colorLirOperand(inst, (Variable) operand, mode) : operand;
198 // remove useless moves
199 if (op instanceof MoveOp) {
200 AllocatableValue result = ((MoveOp) op).getResult();
201 if (isVariable(result) && allocator.isMaterialized(result, op.id(), OperandMode.DEF)) {
202 /*
203 * This happens if a materializable interval is originally not spilled but then
204 * kicked out in LinearScanWalker.splitForSpilling(). When kicking out such an
205 * interval this move operation was already generated.
206 */
207 return true;
208 }
209 }
210
211 op.forEachInput(assignProc);
212 op.forEachAlive(assignProc);
213 op.forEachTemp(assignProc);
214 op.forEachOutput(assignProc);
215
216 // compute reference map and debug information
217 op.forEachState((inst, state) -> computeDebugInfo(inst, state));
218
219 // remove useless moves
220 if (op instanceof ValueMoveOp) {
221 ValueMoveOp move = (ValueMoveOp) op;
222 if (move.getInput().equals(move.getResult())) {
223 return true;
224 }
225 }
226 return false;
227 }
228
229 @SuppressWarnings("try")
230 private void assignLocations() {
231 try (Indent indent = Debug.logAndIndent("assign locations")) {
232 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
233 try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) {
234 assignLocations(allocator.getLIR().getLIRforBlock(block));
235 }
236 }
237 }
238 }
239 }