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