Mercurial > hg > graal-compiler

comparison graal/GraalCompiler/src/com/sun/c1x/alloc/RegisterVerifier.java @ 2509:16b9a8b5ad39

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }