Mercurial > hg > graal-compiler
comparison graal/GraalCompiler/src/com/sun/c1x/alloc/RegisterVerifier.java @ 2509:16b9a8b5ad39
Renamings Runtime=>GraalRuntime and Compiler=>GraalCompiler
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 27 Apr 2011 11:50:44 +0200 |
parents | graal/Compiler/src/com/sun/c1x/alloc/RegisterVerifier.java@9ec15d6914ca |
children | 4a36a0bd6d18 |
comparison
equal
deleted
inserted
replaced
2508:fea94949e0a2 | 2509:16b9a8b5ad39 |
---|---|
1 /* | |
2 * Copyright (c) 2009, 2011, 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 com.sun.c1x.alloc; | |
24 | |
25 import java.util.*; | |
26 | |
27 import com.sun.c1x.*; | |
28 import com.sun.c1x.debug.*; | |
29 import com.sun.c1x.ir.*; | |
30 import com.sun.c1x.lir.*; | |
31 import com.sun.c1x.util.*; | |
32 import com.sun.cri.ci.*; | |
33 | |
34 /** | |
35 * | |
36 * @author Thomas Wuerthinger | |
37 */ | |
38 final class RegisterVerifier { | |
39 | |
40 LinearScan allocator; | |
41 List<BlockBegin> workList; // all blocks that must be processed | |
42 ArrayMap<Interval[]> savedStates; // saved information of previous check | |
43 | |
44 // simplified access to methods of LinearScan | |
45 C1XCompilation compilation() { | |
46 return allocator.compilation; | |
47 } | |
48 | |
49 Interval intervalAt(CiValue operand) { | |
50 return allocator.intervalFor(operand); | |
51 } | |
52 | |
53 // currently, only registers are processed | |
54 int stateSize() { | |
55 return allocator.operands.maxRegisterNumber() + 1; | |
56 } | |
57 | |
58 // accessors | |
59 Interval[] stateForBlock(BlockBegin block) { | |
60 return savedStates.get(block.blockID); | |
61 } | |
62 | |
63 void setStateForBlock(BlockBegin block, Interval[] savedState) { | |
64 savedStates.put(block.blockID, savedState); | |
65 } | |
66 | |
67 void addToWorkList(BlockBegin block) { | |
68 if (!workList.contains(block)) { | |
69 workList.add(block); | |
70 } | |
71 } | |
72 | |
73 RegisterVerifier(LinearScan allocator) { | |
74 this.allocator = allocator; | |
75 workList = new ArrayList<BlockBegin>(16); | |
76 this.savedStates = new ArrayMap<Interval[]>(); | |
77 | |
78 } | |
79 | |
80 void verify(BlockBegin start) { | |
81 // setup input registers (method arguments) for first block | |
82 Interval[] inputState = new Interval[stateSize()]; | |
83 CiCallingConvention args = compilation().frameMap().incomingArguments(); | |
84 for (int n = 0; n < args.locations.length; n++) { | |
85 CiValue operand = args.locations[n]; | |
86 if (operand.isRegister()) { | |
87 CiValue reg = operand; | |
88 Interval interval = intervalAt(reg); | |
89 inputState[reg.asRegister().number] = interval; | |
90 } | |
91 } | |
92 | |
93 setStateForBlock(start, inputState); | |
94 addToWorkList(start); | |
95 | |
96 // main loop for verification | |
97 do { | |
98 BlockBegin block = workList.get(0); | |
99 workList.remove(0); | |
100 | |
101 processBlock(block); | |
102 } while (!workList.isEmpty()); | |
103 } | |
104 | |
105 void processBlock(BlockBegin block) { | |
106 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
107 TTY.println(); | |
108 TTY.println("processBlock B%d", block.blockID); | |
109 } | |
110 | |
111 // must copy state because it is modified | |
112 Interval[] inputState = copy(stateForBlock(block)); | |
113 | |
114 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
115 TTY.println("Input-State of intervals:"); | |
116 TTY.print(" "); | |
117 for (int i = 0; i < stateSize(); i++) { | |
118 if (inputState[i] != null) { | |
119 TTY.print(" %4d", inputState[i].operandNumber); | |
120 } else { | |
121 TTY.print(" __"); | |
122 } | |
123 } | |
124 TTY.println(); | |
125 TTY.println(); | |
126 } | |
127 | |
128 // process all operations of the block | |
129 processOperations(block.lir(), inputState); | |
130 | |
131 // iterate all successors | |
132 for (BlockBegin succ : block.end().successors()) { | |
133 processSuccessor(succ, inputState); | |
134 } | |
135 } | |
136 | |
137 void processXhandler(ExceptionHandler xhandler, Interval[] inputState) { | |
138 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
139 TTY.println("processXhandler B%d", xhandler.entryBlock().blockID); | |
140 } | |
141 | |
142 // must copy state because it is modified | |
143 inputState = copy(inputState); | |
144 | |
145 if (xhandler.entryCode() != null) { | |
146 processOperations(xhandler.entryCode(), inputState); | |
147 } | |
148 processSuccessor(xhandler.entryBlock(), inputState); | |
149 } | |
150 | |
151 void processSuccessor(BlockBegin block, Interval[] inputState) { | |
152 Interval[] savedState = stateForBlock(block); | |
153 | |
154 if (savedState != null) { | |
155 // this block was already processed before. | |
156 // check if new inputState is consistent with savedState | |
157 | |
158 boolean savedStateCorrect = true; | |
159 for (int i = 0; i < stateSize(); i++) { | |
160 if (inputState[i] != savedState[i]) { | |
161 // current inputState and previous savedState assume a different | |
162 // interval in this register . assume that this register is invalid | |
163 if (savedState[i] != null) { | |
164 // invalidate old calculation only if it assumed that | |
165 // register was valid. when the register was already invalid, | |
166 // then the old calculation was correct. | |
167 savedStateCorrect = false; | |
168 savedState[i] = null; | |
169 | |
170 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
171 TTY.println("processSuccessor B%d: invalidating slot %d", block.blockID, i); | |
172 } | |
173 } | |
174 } | |
175 } | |
176 | |
177 if (savedStateCorrect) { | |
178 // already processed block with correct inputState | |
179 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
180 TTY.println("processSuccessor B%d: previous visit already correct", block.blockID); | |
181 } | |
182 } else { | |
183 // must re-visit this block | |
184 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
185 TTY.println("processSuccessor B%d: must re-visit because input state changed", block.blockID); | |
186 } | |
187 addToWorkList(block); | |
188 } | |
189 | |
190 } else { | |
191 // block was not processed before, so set initial inputState | |
192 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
193 TTY.println("processSuccessor B%d: initial visit", block.blockID); | |
194 } | |
195 | |
196 setStateForBlock(block, copy(inputState)); | |
197 addToWorkList(block); | |
198 } | |
199 } | |
200 | |
201 Interval[] copy(Interval[] inputState) { | |
202 return inputState.clone(); | |
203 } | |
204 | |
205 void statePut(Interval[] inputState, CiValue location, Interval interval) { | |
206 if (location != null && location.isRegister()) { | |
207 CiRegister reg = location.asRegister(); | |
208 int regNum = reg.number; | |
209 if (interval != null) { | |
210 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
211 TTY.println(" %s = %s", reg, interval.operand); | |
212 } | |
213 } else if (inputState[regNum] != null) { | |
214 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
215 TTY.println(" %s = null", reg); | |
216 } | |
217 } | |
218 | |
219 inputState[regNum] = interval; | |
220 } | |
221 } | |
222 | |
223 boolean checkState(Interval[] inputState, CiValue reg, Interval interval) { | |
224 if (reg != null && reg.isRegister()) { | |
225 if (inputState[reg.asRegister().number] != interval) { | |
226 throw new CiBailout("!! Error in register allocation: register " + reg + " does not contain interval " + interval.operand + " but interval " + inputState[reg.asRegister().number]); | |
227 } | |
228 } | |
229 return true; | |
230 } | |
231 | |
232 void processOperations(LIRList ops, Interval[] inputState) { | |
233 // visit all instructions of the block | |
234 for (int i = 0; i < ops.length(); i++) { | |
235 LIRInstruction op = ops.at(i); | |
236 | |
237 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
238 TTY.println(op.toStringWithIdPrefix()); | |
239 } | |
240 | |
241 // check if input operands are correct | |
242 int n = op.operandCount(LIRInstruction.OperandMode.Input); | |
243 for (int j = 0; j < n; j++) { | |
244 CiValue operand = op.operandAt(LIRInstruction.OperandMode.Input, j); | |
245 if (allocator.isProcessed(operand)) { | |
246 Interval interval = intervalAt(operand); | |
247 if (op.id != -1) { | |
248 interval = interval.getSplitChildAtOpId(op.id, LIRInstruction.OperandMode.Input, allocator); | |
249 } | |
250 | |
251 assert checkState(inputState, interval.location(), interval.splitParent()); | |
252 } | |
253 } | |
254 | |
255 // invalidate all caller save registers at calls | |
256 if (op.hasCall) { | |
257 for (CiRegister r : allocator.compilation.registerConfig.getCallerSaveRegisters()) { | |
258 statePut(inputState, r.asValue(), null); | |
259 } | |
260 } | |
261 | |
262 // process xhandler before output and temp operands | |
263 List<ExceptionHandler> xhandlers = op.exceptionEdges(); | |
264 n = xhandlers.size(); | |
265 for (int k = 0; k < n; k++) { | |
266 processXhandler(xhandlers.get(k), inputState); | |
267 } | |
268 | |
269 // set temp operands (some operations use temp operands also as output operands, so can't set them null) | |
270 n = op.operandCount(LIRInstruction.OperandMode.Temp); | |
271 for (int j = 0; j < n; j++) { | |
272 CiValue operand = op.operandAt(LIRInstruction.OperandMode.Temp, j); | |
273 if (allocator.isProcessed(operand)) { | |
274 Interval interval = intervalAt(operand); | |
275 assert interval != null : "Could not find interval for operand " + operand; | |
276 if (op.id != -1) { | |
277 interval = interval.getSplitChildAtOpId(op.id, LIRInstruction.OperandMode.Temp, allocator); | |
278 } | |
279 | |
280 statePut(inputState, interval.location(), interval.splitParent()); | |
281 } | |
282 } | |
283 | |
284 // set output operands | |
285 n = op.operandCount(LIRInstruction.OperandMode.Output); | |
286 for (int j = 0; j < n; j++) { | |
287 CiValue operand = op.operandAt(LIRInstruction.OperandMode.Output, j); | |
288 if (allocator.isProcessed(operand)) { | |
289 Interval interval = intervalAt(operand); | |
290 if (op.id != -1) { | |
291 interval = interval.getSplitChildAtOpId(op.id, LIRInstruction.OperandMode.Output, allocator); | |
292 } | |
293 | |
294 statePut(inputState, interval.location(), interval.splitParent()); | |
295 } | |
296 } | |
297 } | |
298 } | |
299 } |