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