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