1 /* 2 * Copyright (c) 2009, 2012, 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.asRegister; 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.alloc.trace.lsra.TraceLinearScanPhase.isVariableOrRegister; 29 30 import java.util.ArrayList; 31 import java.util.EnumSet; 32 33 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 34 import org.graalvm.compiler.core.common.cfg.BlockMap; 35 import org.graalvm.compiler.debug.Debug; 36 import org.graalvm.compiler.debug.Debug.Scope; 37 import org.graalvm.compiler.debug.GraalError; 38 import org.graalvm.compiler.debug.Indent; 39 import org.graalvm.compiler.lir.InstructionValueConsumer; 40 import org.graalvm.compiler.lir.LIRInstruction; 41 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag; 42 import org.graalvm.compiler.lir.LIRInstruction.OperandMode; 43 import org.graalvm.compiler.lir.Variable; 44 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan; 45 46 import jdk.vm.ci.code.Register; 47 import jdk.vm.ci.meta.Value; 48 49 /** 50 */ 51 final class RegisterVerifier { 52 53 TraceLinearScan allocator; 54 ArrayList<AbstractBlockBase<?>> workList; // all blocks that must be processed 55 BlockMap<TraceInterval[]> savedStates; // saved information of previous check 56 57 // simplified access to methods of LinearScan 58 TraceInterval intervalAt(Variable operand) { 59 return allocator.intervalFor(operand); 60 } 61 62 // currently, only registers are processed 63 int stateSize() { 64 return allocator.numRegisters(); 65 } 66 67 // accessors 68 TraceInterval[] stateForBlock(AbstractBlockBase<?> block) { 69 return savedStates.get(block); 70 } 71 72 void setStateForBlock(AbstractBlockBase<?> block, TraceInterval[] savedState) { 73 savedStates.put(block, savedState); 74 } 75 76 void addToWorkList(AbstractBlockBase<?> block) { 77 if (!workList.contains(block)) { 78 workList.add(block); 79 } 80 } 81 82 RegisterVerifier(TraceLinearScan allocator) { 83 this.allocator = allocator; 84 workList = new ArrayList<>(16); 85 this.savedStates = new BlockMap<>(allocator.getLIR().getControlFlowGraph()); 86 87 } 88 89 @SuppressWarnings("try") 90 void verify(AbstractBlockBase<?> start) { 91 try (Scope s = Debug.scope("RegisterVerifier")) { 92 // setup input registers (method arguments) for first block 93 TraceInterval[] inputState = new TraceInterval[stateSize()]; 94 setStateForBlock(start, inputState); 95 addToWorkList(start); 96 97 // main loop for verification 98 do { 99 AbstractBlockBase<?> block = workList.get(0); 100 workList.remove(0); 101 102 processBlock(block); 103 } while (!workList.isEmpty()); 104 } 105 } 106 107 @SuppressWarnings("try") 108 private void processBlock(AbstractBlockBase<?> block) { 109 try (Indent indent = Debug.logAndIndent("processBlock B%d", block.getId())) { 110 // must copy state because it is modified 111 TraceInterval[] inputState = copy(stateForBlock(block)); 112 113 try (Indent indent2 = Debug.logAndIndent("Input-State of intervals:")) { 114 printState(inputState); 115 } 116 117 // process all operations of the block 118 processOperations(block, inputState); 119 120 try (Indent indent2 = Debug.logAndIndent("Output-State of intervals:")) { 121 printState(inputState); 122 } 123 124 // iterate all successors 125 for (AbstractBlockBase<?> succ : block.getSuccessors()) { 126 processSuccessor(succ, inputState); 127 } 128 } 129 } 130 131 protected void printState(TraceInterval[] inputState) { 132 for (int i = 0; i < stateSize(); i++) { 133 Register reg = allocator.getRegisters().get(i); 134 assert reg.number == i; 135 if (inputState[i] != null) { 136 Debug.log(" %6s %4d -- %s", reg, inputState[i].operandNumber, inputState[i]); 137 } else { 138 Debug.log(" %6s __", reg); 139 } 140 } 141 } 142 143 private void processSuccessor(AbstractBlockBase<?> block, TraceInterval[] inputState) { 144 TraceInterval[] savedState = stateForBlock(block); 145 146 if (savedState != null) { 147 // this block was already processed before. 148 // check if new inputState is consistent with savedState 149 150 boolean savedStateCorrect = true; 151 for (int i = 0; i < stateSize(); i++) { 152 if (inputState[i] != savedState[i]) { 153 // current inputState and previous savedState assume a different 154 // interval in this register . assume that this register is invalid 155 if (savedState[i] != null) { 156 // invalidate old calculation only if it assumed that 157 // register was valid. when the register was already invalid, 158 // then the old calculation was correct. 159 savedStateCorrect = false; 160 savedState[i] = null; 161 162 Debug.log("processSuccessor B%d: invalidating slot %d", block.getId(), i); 163 } 164 } 165 } 166 167 if (savedStateCorrect) { 168 // already processed block with correct inputState 169 Debug.log("processSuccessor B%d: previous visit already correct", block.getId()); 170 } else { 171 // must re-visit this block 172 Debug.log("processSuccessor B%d: must re-visit because input state changed", block.getId()); 173 addToWorkList(block); 174 } 175 176 } else { 177 // block was not processed before, so set initial inputState 178 Debug.log("processSuccessor B%d: initial visit", block.getId()); 179 180 setStateForBlock(block, copy(inputState)); 181 addToWorkList(block); 182 } 183 } 184 185 static TraceInterval[] copy(TraceInterval[] inputState) { 186 return inputState.clone(); 187 } 188 189 static void statePut(TraceInterval[] inputState, Value location, TraceInterval interval) { 190 if (location != null && isRegister(location)) { 191 Register reg = asRegister(location); 192 int regNum = reg.number; 193 if (interval != null) { 194 Debug.log("%s = v%d", reg, interval.operandNumber); 195 } else if (inputState[regNum] != null) { 196 Debug.log("%s = null", reg); 197 } 198 199 inputState[regNum] = interval; 200 } 201 } 202 203 static boolean checkState(AbstractBlockBase<?> block, LIRInstruction op, TraceInterval[] inputState, Value operand, Value reg, TraceInterval interval) { 204 if (reg != null && isRegister(reg)) { 205 if (inputState[asRegister(reg).number] != interval) { 206 throw new GraalError( 207 "Error in register allocation: operation (%s) in block %s expected register %s (operand %s) to contain the value of interval %s but data-flow says it contains interval %s", 208 op, block, reg, operand, interval, inputState[asRegister(reg).number]); 209 } 210 } 211 return true; 212 } 213 214 void processOperations(AbstractBlockBase<?> block, final TraceInterval[] inputState) { 215 ArrayList<LIRInstruction> ops = allocator.getLIR().getLIRforBlock(block); 216 InstructionValueConsumer useConsumer = new InstructionValueConsumer() { 217 218 @Override 219 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { 220 // we skip spill moves inserted by the spill position optimization 221 if (isVariableOrRegister(operand) && allocator.isProcessed(operand) && op.id() != TraceLinearScanPhase.DOMINATOR_SPILL_MOVE_ID) { 222 TraceInterval interval = intervalAt(asVariable(operand)); 223 if (op.id() != -1) { 224 interval = interval.getSplitChildAtOpId(op.id(), mode); 225 } 226 227 assert checkState(block, op, inputState, allocator.getOperand(interval), interval.location(), interval.splitParent()); 228 } 229 } 230 }; 231 232 InstructionValueConsumer defConsumer = (op, operand, mode, flags) -> { 233 if (isVariableOrRegister(operand) && allocator.isProcessed(operand)) { 234 TraceInterval interval = intervalAt(asVariable(operand)); 235 if (op.id() != -1) { 236 interval = interval.getSplitChildAtOpId(op.id(), mode); 237 } 238 239 statePut(inputState, interval.location(), interval.splitParent()); 240 } 241 }; 242 243 // visit all instructions of the block 244 for (int i = 0; i < ops.size(); i++) { 245 final LIRInstruction op = ops.get(i); 246 247 if (Debug.isLogEnabled()) { 248 Debug.log("%s", op.toStringWithIdPrefix()); 249 } 250 251 // check if input operands are correct 252 op.visitEachInput(useConsumer); 253 // invalidate all caller save registers at calls 254 if (op.destroysCallerSavedRegisters()) { 255 for (Register r : allocator.getRegisterAllocationConfig().getRegisterConfig().getCallerSaveRegisters()) { 256 statePut(inputState, r.asValue(), null); 257 } 258 } 259 op.visitEachAlive(useConsumer); 260 // set temp operands (some operations use temp operands also as output operands, so 261 // can't set them null) 262 op.visitEachTemp(defConsumer); 263 // set output operands 264 op.visitEachOutput(defConsumer); 265 } 266 } 267 }