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 }