Mercurial > hg > truffle
comparison graal/com.oracle.max.graal.compiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2872:0341b6424579
Project renaming.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 08 Jun 2011 08:42:25 +0200 |
parents | graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java@9b8c194c1b1f |
children |
comparison
equal
deleted
inserted
replaced
2871:d704eb526603 | 2872:0341b6424579 |
---|---|
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 | |
24 package com.sun.c1x.ir; | |
25 | |
26 import java.util.*; | |
27 | |
28 import com.sun.c1x.*; | |
29 import com.sun.c1x.debug.*; | |
30 import com.sun.c1x.lir.*; | |
31 import com.sun.c1x.util.*; | |
32 import com.sun.cri.ci.*; | |
33 | |
34 public final class ComputeLinearScanOrder { | |
35 | |
36 private final int maxBlockId; // the highest blockId of a block | |
37 private int numBlocks; // total number of blocks (smaller than maxBlockId) | |
38 private int numLoops; // total number of loops | |
39 private boolean iterativeDominators; // method requires iterative computation of dominators | |
40 | |
41 List<LIRBlock> linearScanOrder; // the resulting list of blocks in correct order | |
42 | |
43 final CiBitMap visitedBlocks; // used for recursive processing of blocks | |
44 final CiBitMap activeBlocks; // used for recursive processing of blocks | |
45 final CiBitMap dominatorBlocks; // temporary BitMap used for computation of dominator | |
46 final int[] forwardBranches; // number of incoming forward branches for each block | |
47 final List<LIRBlock> loopEndBlocks; // list of all loop end blocks collected during countEdges | |
48 BitMap2D loopMap; // two-dimensional bit set: a bit is set if a block is contained in a loop | |
49 final List<LIRBlock> workList; // temporary list (used in markLoops and computeOrder) | |
50 | |
51 // accessors for visitedBlocks and activeBlocks | |
52 void initVisited() { | |
53 activeBlocks.clearAll(); | |
54 visitedBlocks.clearAll(); | |
55 } | |
56 | |
57 boolean isVisited(LIRBlock b) { | |
58 return visitedBlocks.get(b.blockID()); | |
59 } | |
60 | |
61 boolean isActive(LIRBlock b) { | |
62 return activeBlocks.get(b.blockID()); | |
63 } | |
64 | |
65 void setVisited(LIRBlock b) { | |
66 assert !isVisited(b) : "already set"; | |
67 visitedBlocks.set(b.blockID()); | |
68 } | |
69 | |
70 void setActive(LIRBlock b) { | |
71 assert !isActive(b) : "already set"; | |
72 activeBlocks.set(b.blockID()); | |
73 } | |
74 | |
75 void clearActive(LIRBlock b) { | |
76 assert isActive(b) : "not already"; | |
77 activeBlocks.clear(b.blockID()); | |
78 } | |
79 | |
80 // accessors for forwardBranches | |
81 void incForwardBranches(LIRBlock b) { | |
82 forwardBranches[b.blockID()]++; | |
83 } | |
84 | |
85 int decForwardBranches(LIRBlock b) { | |
86 return --forwardBranches[b.blockID()]; | |
87 } | |
88 | |
89 // accessors for loopMap | |
90 boolean isBlockInLoop(int loopIdx, LIRBlock b) { | |
91 return loopMap.at(loopIdx, b.blockID()); | |
92 } | |
93 | |
94 void setBlockInLoop(int loopIdx, LIRBlock b) { | |
95 loopMap.setBit(loopIdx, b.blockID()); | |
96 } | |
97 | |
98 void clearBlockInLoop(int loopIdx, int blockId) { | |
99 loopMap.clearBit(loopIdx, blockId); | |
100 } | |
101 | |
102 // accessors for final result | |
103 public List<LIRBlock> linearScanOrder() { | |
104 return linearScanOrder; | |
105 } | |
106 | |
107 public int numLoops() { | |
108 return numLoops; | |
109 } | |
110 | |
111 public ComputeLinearScanOrder(int maxBlockId, LIRBlock startBlock) { | |
112 | |
113 this.maxBlockId = maxBlockId; | |
114 visitedBlocks = new CiBitMap(maxBlockId); | |
115 activeBlocks = new CiBitMap(maxBlockId); | |
116 dominatorBlocks = new CiBitMap(maxBlockId); | |
117 forwardBranches = new int[maxBlockId]; | |
118 loopEndBlocks = new ArrayList<LIRBlock>(8); | |
119 workList = new ArrayList<LIRBlock>(8); | |
120 | |
121 splitCriticalEdges(); | |
122 | |
123 countEdges(startBlock, null); | |
124 | |
125 if (numLoops > 0) { | |
126 markLoops(); | |
127 clearNonNaturalLoops(startBlock); | |
128 assignLoopDepth(startBlock); | |
129 } | |
130 | |
131 computeOrder(startBlock); | |
132 | |
133 printBlocks(); | |
134 assert verify(); | |
135 } | |
136 | |
137 void splitCriticalEdges() { | |
138 // TODO: move critical edge splitting from IR to here | |
139 } | |
140 | |
141 /** | |
142 * Traverses the CFG to analyze block and edge info. The analysis performed is: | |
143 * | |
144 * 1. Count of total number of blocks. | |
145 * 2. Count of all incoming edges and backward incoming edges. | |
146 * 3. Number loop header blocks. | |
147 * 4. Create a list with all loop end blocks. | |
148 */ | |
149 void countEdges(LIRBlock cur, LIRBlock parent) { | |
150 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
151 TTY.println("Counting edges for block B%d%s", cur.blockID(), parent == null ? "" : " coming from B" + parent.blockID()); | |
152 } | |
153 | |
154 if (isActive(cur)) { | |
155 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
156 TTY.println("backward branch"); | |
157 } | |
158 assert isVisited(cur) : "block must be visited when block is active"; | |
159 assert parent != null : "must have parent"; | |
160 | |
161 cur.setLinearScanLoopHeader(); | |
162 parent.setLinearScanLoopEnd(); | |
163 | |
164 loopEndBlocks.add(parent); | |
165 return; | |
166 } | |
167 | |
168 // increment number of incoming forward branches | |
169 incForwardBranches(cur); | |
170 | |
171 if (isVisited(cur)) { | |
172 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
173 TTY.println("block already visited"); | |
174 } | |
175 return; | |
176 } | |
177 | |
178 numBlocks++; | |
179 setVisited(cur); | |
180 setActive(cur); | |
181 | |
182 // recursive call for all successors | |
183 int i; | |
184 for (i = cur.numberOfSux() - 1; i >= 0; i--) { | |
185 countEdges(cur.suxAt(i), cur); | |
186 } | |
187 | |
188 clearActive(cur); | |
189 | |
190 // Each loop has a unique number. | |
191 // When multiple loops are nested, assignLoopDepth assumes that the | |
192 // innermost loop has the lowest number. This is guaranteed by setting | |
193 // the loop number after the recursive calls for the successors above | |
194 // have returned. | |
195 if (cur.isLinearScanLoopHeader()) { | |
196 assert cur.loopIndex() == -1 : "cannot set loop-index twice"; | |
197 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
198 TTY.println("Block B%d is loop header of loop %d", cur.blockID(), numLoops); | |
199 } | |
200 | |
201 cur.setLoopIndex(numLoops); | |
202 numLoops++; | |
203 } | |
204 | |
205 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
206 TTY.println("Finished counting edges for block B%d", cur.blockID()); | |
207 } | |
208 } | |
209 | |
210 void markLoops() { | |
211 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
212 TTY.println("----- marking loops"); | |
213 } | |
214 | |
215 loopMap = new BitMap2D(numLoops, maxBlockId); | |
216 | |
217 for (int i = loopEndBlocks.size() - 1; i >= 0; i--) { | |
218 LIRBlock loopEnd = loopEndBlocks.get(i); | |
219 LIRBlock loopStart = loopEnd.suxAt(0); | |
220 int loopIdx = loopStart.loopIndex(); | |
221 | |
222 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
223 TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID(), loopEnd.blockID(), loopIdx); | |
224 } | |
225 assert loopEnd.isLinearScanLoopEnd() : "loop end flag must be set"; | |
226 // assert loopEnd.numberOfSux() == 1 : "incorrect number of successors"; | |
227 assert loopStart.isLinearScanLoopHeader() : "loop header flag must be set"; | |
228 assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set"; | |
229 assert workList.isEmpty() : "work list must be empty before processing"; | |
230 | |
231 // add the end-block of the loop to the working list | |
232 workList.add(loopEnd); | |
233 setBlockInLoop(loopIdx, loopEnd); | |
234 do { | |
235 LIRBlock cur = workList.remove(workList.size() - 1); | |
236 | |
237 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
238 TTY.println(" processing B%d", cur.blockID()); | |
239 } | |
240 assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list"; | |
241 | |
242 // recursive processing of all predecessors ends when start block of loop is reached | |
243 if (cur != loopStart) { | |
244 for (int j = cur.numberOfPreds() - 1; j >= 0; j--) { | |
245 LIRBlock pred = cur.predAt(j); | |
246 | |
247 if (!isBlockInLoop(loopIdx, pred)) { | |
248 // this predecessor has not been processed yet, so add it to work list | |
249 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
250 TTY.println(" pushing B%d", pred.blockID()); | |
251 } | |
252 workList.add(pred); | |
253 setBlockInLoop(loopIdx, pred); | |
254 } | |
255 } | |
256 } | |
257 } while (!workList.isEmpty()); | |
258 } | |
259 } | |
260 | |
261 // check for non-natural loops (loops where the loop header does not dominate | |
262 // all other loop blocks = loops with multiple entries). | |
263 // such loops are ignored | |
264 void clearNonNaturalLoops(LIRBlock startBlock) { | |
265 for (int i = numLoops - 1; i >= 0; i--) { | |
266 if (isBlockInLoop(i, startBlock)) { | |
267 // loop i contains the entry block of the method. | |
268 // this is not a natural loop, so ignore it | |
269 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
270 TTY.println("Loop %d is non-natural, so it is ignored", i); | |
271 } | |
272 | |
273 for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) { | |
274 clearBlockInLoop(i, blockId); | |
275 } | |
276 iterativeDominators = true; | |
277 } | |
278 } | |
279 } | |
280 | |
281 void assignLoopDepth(LIRBlock startBlock) { | |
282 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
283 TTY.println("----- computing loop-depth and weight"); | |
284 } | |
285 initVisited(); | |
286 | |
287 assert workList.isEmpty() : "work list must be empty before processing"; | |
288 workList.add(startBlock); | |
289 | |
290 do { | |
291 LIRBlock cur = workList.remove(workList.size() - 1); | |
292 | |
293 if (!isVisited(cur)) { | |
294 setVisited(cur); | |
295 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
296 TTY.println("Computing loop depth for block B%d", cur.blockID()); | |
297 } | |
298 | |
299 // compute loop-depth and loop-index for the block | |
300 assert cur.loopDepth() == 0 : "cannot set loop-depth twice"; | |
301 int i; | |
302 int loopDepth = 0; | |
303 int minLoopIdx = -1; | |
304 for (i = numLoops - 1; i >= 0; i--) { | |
305 if (isBlockInLoop(i, cur)) { | |
306 loopDepth++; | |
307 minLoopIdx = i; | |
308 } | |
309 } | |
310 cur.setLoopDepth(loopDepth); | |
311 cur.setLoopIndex(minLoopIdx); | |
312 | |
313 // append all unvisited successors to work list | |
314 for (i = cur.numberOfSux() - 1; i >= 0; i--) { | |
315 workList.add(cur.suxAt(i)); | |
316 } | |
317 } | |
318 } while (!workList.isEmpty()); | |
319 } | |
320 | |
321 int computeWeight(LIRBlock cur) { | |
322 LIRBlock singleSux = null; | |
323 if (cur.numberOfSux() == 1) { | |
324 singleSux = cur.suxAt(0); | |
325 } | |
326 | |
327 // limit loop-depth to 15 bit (only for security reason, it will never be so big) | |
328 int weight = (cur.loopDepth() & 0x7FFF) << 16; | |
329 | |
330 int curBit = 15; | |
331 | |
332 // this is necessary for the (very rare) case that two successive blocks have | |
333 // the same loop depth, but a different loop index (can happen for endless loops | |
334 // with exception handlers) | |
335 if (!cur.isLinearScanLoopHeader()) { | |
336 weight |= 1 << curBit; | |
337 } | |
338 curBit--; | |
339 | |
340 // loop end blocks (blocks that end with a backward branch) are added | |
341 // after all other blocks of the loop. | |
342 if (!cur.isLinearScanLoopEnd()) { | |
343 weight |= 1 << curBit; | |
344 } | |
345 curBit--; | |
346 | |
347 // critical edge split blocks are preferred because then they have a greater | |
348 // probability to be completely empty | |
349 //if (cur.isCriticalEdgeSplit()) { | |
350 // weight |= 1 << curBit; | |
351 //} | |
352 //curBit--; | |
353 | |
354 // exceptions should not be thrown in normal control flow, so these blocks | |
355 // are added as late as possible | |
356 // if (!(cur.end() instanceof Throw) && (singleSux == null || !(singleSux.end() instanceof Throw))) { | |
357 // weight |= 1 << curBit; | |
358 // } | |
359 // curBit--; | |
360 // if (!(cur.end() instanceof Return) && (singleSux == null || !(singleSux.end() instanceof Return))) { | |
361 // weight |= 1 << curBit; | |
362 // } | |
363 // curBit--; | |
364 | |
365 // exceptions handlers are added as late as possible | |
366 // if (!cur.isExceptionEntry()) { | |
367 // weight |= 1 << curBit; | |
368 // } | |
369 // curBit--; | |
370 | |
371 // guarantee that weight is > 0 | |
372 weight |= 1; | |
373 | |
374 assert curBit >= 0 : "too many flags"; | |
375 assert weight > 0 : "weight cannot become negative"; | |
376 | |
377 return weight; | |
378 } | |
379 | |
380 boolean readyForProcessing(LIRBlock cur) { | |
381 // Discount the edge just traveled. | |
382 // When the number drops to zero, all forward branches were processed | |
383 if (decForwardBranches(cur) != 0) { | |
384 return false; | |
385 } | |
386 | |
387 assert !linearScanOrder.contains(cur) : "block already processed (block can be ready only once)"; | |
388 assert !workList.contains(cur) : "block already in work-list (block can be ready only once)"; | |
389 return true; | |
390 } | |
391 | |
392 void sortIntoWorkList(LIRBlock cur) { | |
393 assert !workList.contains(cur) : "block already in work list"; | |
394 | |
395 int curWeight = computeWeight(cur); | |
396 | |
397 // the linearScanNumber is used to cache the weight of a block | |
398 cur.setLinearScanNumber(curWeight); | |
399 | |
400 if (C1XOptions.StressLinearScan) { | |
401 workList.add(0, cur); | |
402 return; | |
403 } | |
404 | |
405 workList.add(null); // provide space for new element | |
406 | |
407 int insertIdx = workList.size() - 1; | |
408 while (insertIdx > 0 && workList.get(insertIdx - 1).linearScanNumber() > curWeight) { | |
409 workList.set(insertIdx, workList.get(insertIdx - 1)); | |
410 insertIdx--; | |
411 } | |
412 workList.set(insertIdx, cur); | |
413 | |
414 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
415 TTY.println("Sorted B%d into worklist. new worklist:", cur.blockID()); | |
416 for (int i = 0; i < workList.size(); i++) { | |
417 TTY.println(String.format("%8d B%02d weight:%6x", i, workList.get(i).blockID(), workList.get(i).linearScanNumber())); | |
418 } | |
419 } | |
420 | |
421 for (int i = 0; i < workList.size(); i++) { | |
422 assert workList.get(i).linearScanNumber() > 0 : "weight not set"; | |
423 assert i == 0 || workList.get(i - 1).linearScanNumber() <= workList.get(i).linearScanNumber() : "incorrect order in worklist"; | |
424 } | |
425 } | |
426 | |
427 void appendBlock(LIRBlock cur) { | |
428 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
429 TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID(), cur.linearScanNumber()); | |
430 } | |
431 assert !linearScanOrder.contains(cur) : "cannot add the same block twice"; | |
432 | |
433 // currently, the linear scan order and code emit order are equal. | |
434 // therefore the linearScanNumber and the weight of a block must also | |
435 // be equal. | |
436 cur.setLinearScanNumber(linearScanOrder.size()); | |
437 linearScanOrder.add(cur); | |
438 } | |
439 | |
440 void computeOrder(LIRBlock startBlock) { | |
441 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
442 TTY.println("----- computing final block order"); | |
443 } | |
444 | |
445 // the start block is always the first block in the linear scan order | |
446 linearScanOrder = new ArrayList<LIRBlock>(numBlocks); | |
447 // appendBlock(startBlock); | |
448 | |
449 LIRBlock stdEntry = startBlock; //.suxAt(0); | |
450 | |
451 // start processing with standard entry block | |
452 assert workList.isEmpty() : "list must be empty before processing"; | |
453 | |
454 if (readyForProcessing(stdEntry)) { | |
455 sortIntoWorkList(stdEntry); | |
456 } else { | |
457 throw new CiBailout("the stdEntry must be ready for processing (otherwise, the method has no start block)"); | |
458 } | |
459 | |
460 do { | |
461 LIRBlock cur = workList.remove(workList.size() - 1); | |
462 | |
463 appendBlock(cur); | |
464 | |
465 int i; | |
466 int numSux = cur.numberOfSux(); | |
467 // changed loop order to get "intuitive" order of if- and else-blocks | |
468 for (i = 0; i < numSux; i++) { | |
469 LIRBlock sux = cur.suxAt(i); | |
470 if (readyForProcessing(sux)) { | |
471 sortIntoWorkList(sux); | |
472 } | |
473 } | |
474 } while (workList.size() > 0); | |
475 } | |
476 | |
477 public void printBlocks() { | |
478 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
479 TTY.println("----- loop information:"); | |
480 for (LIRBlock cur : linearScanOrder) { | |
481 TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID())); | |
482 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) { | |
483 TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur))); | |
484 } | |
485 TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", cur.loopIndex(), cur.loopDepth())); | |
486 } | |
487 } | |
488 | |
489 if (C1XOptions.TraceLinearScanLevel >= 1) { | |
490 TTY.println("----- linear-scan block order:"); | |
491 for (LIRBlock cur : linearScanOrder) { | |
492 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID(), cur.loopIndex(), cur.loopDepth())); | |
493 | |
494 TTY.print(cur.isLinearScanLoopHeader() ? " lh" : " "); | |
495 TTY.print(cur.isLinearScanLoopEnd() ? " le" : " "); | |
496 | |
497 TTY.print(" dom: null "); | |
498 | |
499 | |
500 if (cur.numberOfPreds() > 0) { | |
501 TTY.print(" preds: "); | |
502 for (int j = 0; j < cur.numberOfPreds(); j++) { | |
503 LIRBlock pred = cur.predAt(j); | |
504 TTY.print("B%d ", pred.blockID()); | |
505 } | |
506 } | |
507 if (cur.numberOfSux() > 0) { | |
508 TTY.print(" sux: "); | |
509 for (int j = 0; j < cur.numberOfSux(); j++) { | |
510 LIRBlock sux = cur.suxAt(j); | |
511 TTY.print("B%d ", sux.blockID()); | |
512 } | |
513 } | |
514 TTY.println(); | |
515 } | |
516 } | |
517 } | |
518 | |
519 boolean verify() { | |
520 /* assert linearScanOrder.size() == numBlocks : "wrong number of blocks in list"; | |
521 | |
522 if (C1XOptions.StressLinearScan) { | |
523 // blocks are scrambled when StressLinearScan is used | |
524 return true; | |
525 } | |
526 | |
527 // check that all successors of a block have a higher linear-scan-number | |
528 // and that all predecessors of a block have a lower linear-scan-number | |
529 // (only backward branches of loops are ignored) | |
530 int i; | |
531 for (i = 0; i < linearScanOrder.size(); i++) { | |
532 BlockBegin cur = linearScanOrder.get(i); | |
533 | |
534 assert cur.linearScanNumber() == i : "incorrect linearScanNumber"; | |
535 assert cur.linearScanNumber() >= 0 && cur.linearScanNumber() == linearScanOrder.indexOf(cur) : "incorrect linearScanNumber"; | |
536 | |
537 for (BlockBegin sux : cur.end().successors()) { | |
538 assert sux.linearScanNumber() >= 0 && sux.linearScanNumber() == linearScanOrder.indexOf(sux) : "incorrect linearScanNumber"; | |
539 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) { | |
540 assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order"; | |
541 } | |
542 if (cur.loopDepth() == sux.loopDepth()) { | |
543 assert cur.loopIndex() == sux.loopIndex() || sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index"; | |
544 } | |
545 } | |
546 | |
547 for (BlockBegin pred : cur.predecessors()) { | |
548 assert pred.linearScanNumber() >= 0 && pred.linearScanNumber() == linearScanOrder.indexOf(pred) : "incorrect linearScanNumber"; | |
549 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) { | |
550 assert cur.linearScanNumber() > pred.linearScanNumber() : "invalid order"; | |
551 } | |
552 if (cur.loopDepth() == pred.loopDepth()) { | |
553 assert cur.loopIndex() == pred.loopIndex() || cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index"; | |
554 } | |
555 | |
556 assert cur.dominator().linearScanNumber() <= pred.linearScanNumber() : "dominator must be before predecessors"; | |
557 } | |
558 | |
559 // check dominator | |
560 if (i == 0) { | |
561 assert cur.dominator() == null : "first block has no dominator"; | |
562 } else { | |
563 assert cur.dominator() != null : "all but first block must have dominator"; | |
564 } | |
565 assert cur.numberOfPreds() != 1 || cur.dominator() == cur.predAt(0) || cur.isExceptionEntry() : "Single predecessor must also be dominator"; | |
566 } | |
567 | |
568 // check that all loops are continuous | |
569 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) { | |
570 int blockIdx = 0; | |
571 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop"; | |
572 | |
573 // skip blocks before the loop | |
574 while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) { | |
575 blockIdx++; | |
576 } | |
577 // skip blocks of loop | |
578 while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) { | |
579 blockIdx++; | |
580 } | |
581 // after the first non-loop block : there must not be another loop-block | |
582 while (blockIdx < numBlocks) { | |
583 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order"; | |
584 blockIdx++; | |
585 } | |
586 } | |
587 */ | |
588 return true; | |
589 } | |
590 } |