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