Mercurial > hg > graal-compiler

comparison graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.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/ir/ComputeLinearScanOrder.java@9ec15d6914ca
children a384fac3fd34
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
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.util.*;
31 import com.sun.cri.ci.*;
32
33 /**
34 * @author Thomas Wuerthinger
35 *
36 */
37 public final class ComputeLinearScanOrder {
38
39 private final int maxBlockId; // the highest blockId of a block
40 private int numBlocks; // total number of blocks (smaller than maxBlockId)
41 private int numLoops; // total number of loops
42 private boolean iterativeDominators; // method requires iterative computation of dominators
43
44 List<BlockBegin> linearScanOrder; // the resulting list of blocks in correct order
45
46 final CiBitMap visitedBlocks; // used for recursive processing of blocks
47 final CiBitMap activeBlocks; // used for recursive processing of blocks
48 final CiBitMap dominatorBlocks; // temporary BitMap used for computation of dominator
49 final int[] forwardBranches; // number of incoming forward branches for each block
50 final List<BlockBegin> loopEndBlocks; // list of all loop end blocks collected during countEdges
51 BitMap2D loopMap; // two-dimensional bit set: a bit is set if a block is contained in a loop
52 final List<BlockBegin> workList; // temporary list (used in markLoops and computeOrder)
53
54 // accessors for visitedBlocks and activeBlocks
55 void initVisited() {
56 activeBlocks.clearAll();
57 visitedBlocks.clearAll();
58 }
59
60 boolean isVisited(BlockBegin b) {
61 return visitedBlocks.get(b.blockID);
62 }
63
64 boolean isActive(BlockBegin b) {
65 return activeBlocks.get(b.blockID);
66 }
67
68 void setVisited(BlockBegin b) {
69 assert !isVisited(b) : "already set";
70 visitedBlocks.set(b.blockID);
71 }
72
73 void setActive(BlockBegin b) {
74 assert !isActive(b) : "already set";
75 activeBlocks.set(b.blockID);
76 }
77
78 void clearActive(BlockBegin b) {
79 assert isActive(b) : "not already";
80 activeBlocks.clear(b.blockID);
81 }
82
83 // accessors for forwardBranches
84 void incForwardBranches(BlockBegin b) {
85 forwardBranches[b.blockID]++;
86 }
87
88 int decForwardBranches(BlockBegin b) {
89 return --forwardBranches[b.blockID];
90 }
91
92 // accessors for loopMap
93 boolean isBlockInLoop(int loopIdx, BlockBegin b) {
94 return loopMap.at(loopIdx, b.blockID);
95 }
96
97 void setBlockInLoop(int loopIdx, BlockBegin b) {
98 loopMap.setBit(loopIdx, b.blockID);
99 }
100
101 void clearBlockInLoop(int loopIdx, int blockId) {
102 loopMap.clearBit(loopIdx, blockId);
103 }
104
105 // accessors for final result
106 public List<BlockBegin> linearScanOrder() {
107 return linearScanOrder;
108 }
109
110 public int numLoops() {
111 return numLoops;
112 }
113
114 public ComputeLinearScanOrder(int maxBlockId, BlockBegin startBlock) {
115
116 this.maxBlockId = maxBlockId;
117 visitedBlocks = new CiBitMap(maxBlockId);
118 activeBlocks = new CiBitMap(maxBlockId);
119 dominatorBlocks = new CiBitMap(maxBlockId);
120 forwardBranches = new int[maxBlockId];
121 loopEndBlocks = new ArrayList<BlockBegin>(8);
122 workList = new ArrayList<BlockBegin>(8);
123
124 splitCriticalEdges();
125
126 countEdges(startBlock, null);
127
128 if (numLoops > 0) {
129 markLoops();
130 clearNonNaturalLoops(startBlock);
131 assignLoopDepth(startBlock);
132 }
133
134 computeOrder(startBlock);
135 computeDominators();
136
137 printBlocks();
138 assert verify();
139 }
140
141 void splitCriticalEdges() {
142 // TODO: move critical edge splitting from IR to here
143 }
144
145 /**
146 * Traverses the CFG to analyze block and edge info. The analysis performed is:
147 *
148 * 1. Count of total number of blocks.
149 * 2. Count of all incoming edges and backward incoming edges.
150 * 3. Number loop header blocks.
151 * 4. Create a list with all loop end blocks.
152 */
153 void countEdges(BlockBegin cur, BlockBegin parent) {
154 if (C1XOptions.TraceLinearScanLevel >= 3) {
155 TTY.println("Counting edges for block B%d%s", cur.blockID, parent == null ? "" : " coming from B" + parent.blockID);
156 }
157 assert cur.dominator() == null : "dominator already initialized";
158
159 if (isActive(cur)) {
160 if (C1XOptions.TraceLinearScanLevel >= 3) {
161 TTY.println("backward branch");
162 }
163 assert isVisited(cur) : "block must be visited when block is active";
164 assert parent != null : "must have parent";
165
166 cur.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader);
167 cur.setBlockFlag(BlockBegin.BlockFlag.BackwardBranchTarget);
168
169 parent.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd);
170
171 // When a loop header is also the start of an exception handler, then the backward branch is
172 // an exception edge. Because such edges are usually critical edges which cannot be split, the
173 // loop must be excluded here from processing.
174 if (cur.checkBlockFlag(BlockBegin.BlockFlag.ExceptionEntry)) {
175 // Make sure that dominators are correct in this weird situation
176 iterativeDominators = true;
177 return;
178 }
179 // assert parent.numberOfSux() == 1 && parent.suxAt(0) == cur : "loop end blocks must have one successor (critical edges are split)";
180
181 loopEndBlocks.add(parent);
182 return;
183 }
184
185 // increment number of incoming forward branches
186 incForwardBranches(cur);
187
188 if (isVisited(cur)) {
189 if (C1XOptions.TraceLinearScanLevel >= 3) {
190 TTY.println("block already visited");
191 }
192 return;
193 }
194
195 numBlocks++;
196 setVisited(cur);
197 setActive(cur);
198
199 // recursive call for all successors
200 int i;
201 for (i = cur.numberOfSux() - 1; i >= 0; i--) {
202 countEdges(cur.suxAt(i), cur);
203 }
204 for (i = cur.numberOfExceptionHandlers() - 1; i >= 0; i--) {
205 countEdges(cur.exceptionHandlerAt(i), cur);
206 }
207
208 clearActive(cur);
209
210 // Each loop has a unique number.
211 // When multiple loops are nested, assignLoopDepth assumes that the
212 // innermost loop has the lowest number. This is guaranteed by setting
213 // the loop number after the recursive calls for the successors above
214 // have returned.
215 if (cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
216 assert cur.loopIndex() == -1 : "cannot set loop-index twice";
217 if (C1XOptions.TraceLinearScanLevel >= 3) {
218 TTY.println("Block B%d is loop header of loop %d", cur.blockID, numLoops);
219 }
220
221 cur.setLoopIndex(numLoops);
222 numLoops++;
223 }
224
225 if (C1XOptions.TraceLinearScanLevel >= 3) {
226 TTY.println("Finished counting edges for block B%d", cur.blockID);
227 }
228 }
229
230 void markLoops() {
231 if (C1XOptions.TraceLinearScanLevel >= 3) {
232 TTY.println("----- marking loops");
233 }
234
235 loopMap = new BitMap2D(numLoops, maxBlockId);
236
237 for (int i = loopEndBlocks.size() - 1; i >= 0; i--) {
238 BlockBegin loopEnd = loopEndBlocks.get(i);
239 BlockBegin loopStart = loopEnd.suxAt(0);
240 int loopIdx = loopStart.loopIndex();
241
242 if (C1XOptions.TraceLinearScanLevel >= 3) {
243 TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID, loopEnd.blockID, loopIdx);
244 }
245 assert loopEnd.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd) : "loop end flag must be set";
246 // assert loopEnd.numberOfSux() == 1 : "incorrect number of successors";
247 assert loopStart.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "loop header flag must be set";
248 assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set";
249 assert workList.isEmpty() : "work list must be empty before processing";
250
251 // add the end-block of the loop to the working list
252 workList.add(loopEnd);
253 setBlockInLoop(loopIdx, loopEnd);
254 do {
255 BlockBegin cur = workList.remove(workList.size() - 1);
256
257 if (C1XOptions.TraceLinearScanLevel >= 3) {
258 TTY.println(" processing B%d", cur.blockID);
259 }
260 assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list";
261
262 // recursive processing of all predecessors ends when start block of loop is reached
263 if (cur != loopStart && !cur.checkBlockFlag(BlockBegin.BlockFlag.OsrEntry)) {
264 for (int j = cur.numberOfPreds() - 1; j >= 0; j--) {
265 BlockBegin pred = cur.predAt(j);
266
267 if (!isBlockInLoop(loopIdx, pred)) {
268 // this predecessor has not been processed yet, so add it to work list
269 if (C1XOptions.TraceLinearScanLevel >= 3) {
270 TTY.println(" pushing B%d", pred.blockID);
271 }
272 workList.add(pred);
273 setBlockInLoop(loopIdx, pred);
274 }
275 }
276 }
277 } while (!workList.isEmpty());
278 }
279 }
280
281 // check for non-natural loops (loops where the loop header does not dominate
282 // all other loop blocks = loops with multiple entries).
283 // such loops are ignored
284 void clearNonNaturalLoops(BlockBegin startBlock) {
285 for (int i = numLoops - 1; i >= 0; i--) {
286 if (isBlockInLoop(i, startBlock)) {
287 // loop i contains the entry block of the method.
288 // this is not a natural loop, so ignore it
289 if (C1XOptions.TraceLinearScanLevel >= 2) {
290 TTY.println("Loop %d is non-natural, so it is ignored", i);
291 }
292
293 for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) {
294 clearBlockInLoop(i, blockId);
295 }
296 iterativeDominators = true;
297 }
298 }
299 }
300
301 void assignLoopDepth(BlockBegin startBlock) {
302 if (C1XOptions.TraceLinearScanLevel >= 3) {
303 TTY.println("----- computing loop-depth and weight");
304 }
305 initVisited();
306
307 assert workList.isEmpty() : "work list must be empty before processing";
308 workList.add(startBlock);
309
310 do {
311 BlockBegin cur = workList.remove(workList.size() - 1);
312
313 if (!isVisited(cur)) {
314 setVisited(cur);
315 if (C1XOptions.TraceLinearScanLevel >= 4) {
316 TTY.println("Computing loop depth for block B%d", cur.blockID);
317 }
318
319 // compute loop-depth and loop-index for the block
320 assert cur.loopDepth() == 0 : "cannot set loop-depth twice";
321 int i;
322 int loopDepth = 0;
323 int minLoopIdx = -1;
324 for (i = numLoops - 1; i >= 0; i--) {
325 if (isBlockInLoop(i, cur)) {
326 loopDepth++;
327 minLoopIdx = i;
328 }
329 }
330 cur.setLoopDepth(loopDepth);
331 cur.setLoopIndex(minLoopIdx);
332
333 // append all unvisited successors to work list
334 for (i = cur.numberOfSux() - 1; i >= 0; i--) {
335 workList.add(cur.suxAt(i));
336 }
337 for (i = cur.numberOfExceptionHandlers() - 1; i >= 0; i--) {
338 workList.add(cur.exceptionHandlerAt(i));
339 }
340 }
341 } while (!workList.isEmpty());
342 }
343
344 BlockBegin commonDominator(BlockBegin a, BlockBegin b) {
345 assert a != null && b != null : "must have input blocks";
346
347 dominatorBlocks.clearAll();
348 while (a != null) {
349 dominatorBlocks.set(a.blockID);
350 assert a.dominator() != null || a == linearScanOrder.get(0) : "dominator must be initialized";
351 a = a.dominator();
352 }
353 while (b != null && !dominatorBlocks.get(b.blockID)) {
354 assert b.dominator() != null || b == linearScanOrder.get(0) : "dominator must be initialized";
355 b = b.dominator();
356 }
357
358 assert b != null : "could not find dominator";
359 return b;
360 }
361
362 void computeDominator(BlockBegin cur, BlockBegin parent) {
363 if (cur.dominator() == null) {
364 if (C1XOptions.TraceLinearScanLevel >= 4) {
365 TTY.println("DOM: initializing dominator of B%d to B%d", cur.blockID, parent.blockID);
366 }
367 if (cur.isExceptionEntry()) {
368 assert parent.dominator() != null;
369 cur.setDominator(parent.dominator());
370 } else {
371 cur.setDominator(parent);
372 }
373
374 } else if (!(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) && parent.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd))) {
375 if (C1XOptions.TraceLinearScanLevel >= 4) {
376 TTY.println("DOM: computing dominator of B%d: common dominator of B%d and B%d is B%d", cur.blockID, parent.blockID, cur.dominator().blockID, commonDominator(cur.dominator(), parent).blockID);
377 }
378 assert cur.numberOfPreds() > 1 : "";
379 cur.setDominator(commonDominator(cur.dominator(), parent));
380 }
381 }
382
383 int computeWeight(BlockBegin cur) {
384 BlockBegin singleSux = null;
385 if (cur.numberOfSux() == 1) {
386 singleSux = cur.suxAt(0);
387 }
388
389 // limit loop-depth to 15 bit (only for security reason, it will never be so big)
390 int weight = (cur.loopDepth() & 0x7FFF) << 16;
391
392 int curBit = 15;
393
394 // this is necessary for the (very rare) case that two successive blocks have
395 // the same loop depth, but a different loop index (can happen for endless loops
396 // with exception handlers)
397 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
398 weight |= (1 << curBit);
399 }
400 curBit--;
401
402 // loop end blocks (blocks that end with a backward branch) are added
403 // after all other blocks of the loop.
404 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) {
405 weight |= (1 << curBit);
406 }
407 curBit--;
408
409 // critical edge split blocks are preferred because then they have a greater
410 // probability to be completely empty
411 if (cur.isCriticalEdgeSplit()) {
412 weight |= (1 << curBit);
413 }
414 curBit--;
415
416 // exceptions should not be thrown in normal control flow, so these blocks
417 // are added as late as possible
418 if (!(cur.end() instanceof Throw) && (singleSux == null || !(singleSux.end() instanceof Throw))) {
419 weight |= (1 << curBit);
420 }
421 curBit--;
422 if (!(cur.end() instanceof Return) && (singleSux == null || !(singleSux.end() instanceof Return))) {
423 weight |= (1 << curBit);
424 }
425 curBit--;
426
427 // exceptions handlers are added as late as possible
428 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.ExceptionEntry)) {
429 weight |= (1 << curBit);
430 }
431 curBit--;
432
433 // guarantee that weight is > 0
434 weight |= 1;
435
436 assert curBit >= 0 : "too many flags";
437 assert weight > 0 : "weight cannot become negative";
438
439 return weight;
440 }
441
442 boolean readyForProcessing(BlockBegin cur) {
443 // Discount the edge just traveled.
444 // When the number drops to zero, all forward branches were processed
445 if (decForwardBranches(cur) != 0) {
446 return false;
447 }
448
449 assert !linearScanOrder.contains(cur) : "block already processed (block can be ready only once)";
450 assert !workList.contains(cur) : "block already in work-list (block can be ready only once)";
451 return true;
452 }
453
454 void sortIntoWorkList(BlockBegin cur) {
455 assert !workList.contains(cur) : "block already in work list";
456
457 int curWeight = computeWeight(cur);
458
459 // the linearScanNumber is used to cache the weight of a block
460 cur.setLinearScanNumber(curWeight);
461
462 if (C1XOptions.StressLinearScan) {
463 workList.add(0, cur);
464 return;
465 }
466
467 workList.add(null); // provide space for new element
468
469 int insertIdx = workList.size() - 1;
470 while (insertIdx > 0 && workList.get(insertIdx - 1).linearScanNumber() > curWeight) {
471 workList.set(insertIdx, workList.get(insertIdx - 1));
472 insertIdx--;
473 }
474 workList.set(insertIdx, cur);
475
476 if (C1XOptions.TraceLinearScanLevel >= 3) {
477 TTY.println("Sorted B%d into worklist. new worklist:", cur.blockID);
478 for (int i = 0; i < workList.size(); i++) {
479 TTY.println(String.format("%8d B%02d weight:%6x", i, workList.get(i).blockID, workList.get(i).linearScanNumber()));
480 }
481 }
482
483 for (int i = 0; i < workList.size(); i++) {
484 assert workList.get(i).linearScanNumber() > 0 : "weight not set";
485 assert i == 0 || workList.get(i - 1).linearScanNumber() <= workList.get(i).linearScanNumber() : "incorrect order in worklist";
486 }
487 }
488
489 void appendBlock(BlockBegin cur) {
490 if (C1XOptions.TraceLinearScanLevel >= 3) {
491 TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID, cur.linearScanNumber());
492 }
493 assert !linearScanOrder.contains(cur) : "cannot add the same block twice";
494
495 // currently, the linear scan order and code emit order are equal.
496 // therefore the linearScanNumber and the weight of a block must also
497 // be equal.
498 cur.setLinearScanNumber(linearScanOrder.size());
499 linearScanOrder.add(cur);
500 }
501
502 void computeOrder(BlockBegin startBlock) {
503 if (C1XOptions.TraceLinearScanLevel >= 3) {
504 TTY.println("----- computing final block order");
505 }
506
507 // the start block is always the first block in the linear scan order
508 linearScanOrder = new ArrayList<BlockBegin>(numBlocks);
509 appendBlock(startBlock);
510
511 assert startBlock.end() instanceof Base : "start block must end with Base-instruction";
512 BlockBegin stdEntry = ((Base) startBlock.end()).standardEntry();
513 BlockBegin osrEntry = ((Base) startBlock.end()).osrEntry();
514
515 BlockBegin suxOfOsrEntry = null;
516 if (osrEntry != null) {
517 // special handling for osr entry:
518 // ignore the edge between the osr entry and its successor for processing
519 // the osr entry block is added manually below
520 assert osrEntry.numberOfSux() == 1 : "osr entry must have exactly one successor";
521 assert osrEntry.suxAt(0).numberOfPreds() >= 2 : "sucessor of osr entry must have two predecessors (otherwise it is not present in normal control flow)";
522
523 suxOfOsrEntry = osrEntry.suxAt(0);
524 decForwardBranches(suxOfOsrEntry);
525
526 computeDominator(osrEntry, startBlock);
527 iterativeDominators = true;
528 }
529 computeDominator(stdEntry, startBlock);
530
531 // start processing with standard entry block
532 assert workList.isEmpty() : "list must be empty before processing";
533
534 if (readyForProcessing(stdEntry)) {
535 sortIntoWorkList(stdEntry);
536 } else {
537 throw new CiBailout("the stdEntry must be ready for processing (otherwise, the method has no start block)");
538 }
539
540 do {
541 BlockBegin cur = workList.remove(workList.size() - 1);
542
543 if (cur == suxOfOsrEntry) {
544 // the osr entry block is ignored in normal processing : it is never added to the
545 // work list. Instead : it is added as late as possible manually here.
546 appendBlock(osrEntry);
547 computeDominator(cur, osrEntry);
548 }
549 appendBlock(cur);
550
551 int i;
552 int numSux = cur.numberOfSux();
553 // changed loop order to get "intuitive" order of if- and else-blocks
554 for (i = 0; i < numSux; i++) {
555 BlockBegin sux = cur.suxAt(i);
556 computeDominator(sux, cur);
557 if (readyForProcessing(sux)) {
558 sortIntoWorkList(sux);
559 }
560 }
561 numSux = cur.numberOfExceptionHandlers();
562 for (i = 0; i < numSux; i++) {
563 BlockBegin sux = cur.exceptionHandlerAt(i);
564 computeDominator(sux, cur);
565 if (readyForProcessing(sux)) {
566 sortIntoWorkList(sux);
567 }
568 }
569 } while (workList.size() > 0);
570 }
571
572 boolean computeDominatorsIter() {
573 boolean changed = false;
574 int numBlocks = linearScanOrder.size();
575
576 assert linearScanOrder.get(0).dominator() == null : "must not have dominator";
577 assert linearScanOrder.get(0).numberOfPreds() == 0 : "must not have predecessors";
578 for (int i = 1; i < numBlocks; i++) {
579 BlockBegin block = linearScanOrder.get(i);
580
581 assert block.numberOfPreds() > 0;
582 BlockBegin dominator = block.predAt(0);
583 if (block.isExceptionEntry()) {
584 dominator = dominator.dominator();
585 }
586
587 int numPreds = block.numberOfPreds();
588 for (int j = 1; j < numPreds; j++) {
589 BlockBegin curPred = block.predAt(j);
590 if (block.isExceptionEntry()) {
591 curPred = curPred.dominator();
592 }
593 dominator = commonDominator(dominator, curPred);
594 }
595
596 if (dominator != block.dominator()) {
597 if (C1XOptions.TraceLinearScanLevel >= 4) {
598 TTY.println("DOM: updating dominator of B%d from B%d to B%d", block.blockID, block.dominator().blockID, dominator.blockID);
599 }
600 block.setDominator(dominator);
601 changed = true;
602 }
603 }
604 return changed;
605 }
606
607 void computeDominators() {
608 if (C1XOptions.TraceLinearScanLevel >= 3) {
609 TTY.println("----- computing dominators (iterative computation reqired: %b)", iterativeDominators);
610 }
611
612 // iterative computation of dominators is only required for methods with non-natural loops
613 // and OSR-methods. For all other methods : the dominators computed when generating the
614 // linear scan block order are correct.
615 if (iterativeDominators) {
616 do {
617 if (C1XOptions.TraceLinearScanLevel >= 1) {
618 TTY.println("DOM: next iteration of fix-point calculation");
619 }
620 } while (computeDominatorsIter());
621 }
622
623 // check that dominators are correct
624 assert !computeDominatorsIter() : "fix point not reached";
625 }
626
627 public void printBlocks() {
628 if (C1XOptions.TraceLinearScanLevel >= 2) {
629 TTY.println("----- loop information:");
630 for (BlockBegin cur : linearScanOrder) {
631 TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID));
632 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
633 TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur)));
634 }
635 TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", cur.loopIndex(), cur.loopDepth()));
636 }
637 }
638
639 if (C1XOptions.TraceLinearScanLevel >= 1) {
640 TTY.println("----- linear-scan block order:");
641 for (BlockBegin cur : linearScanOrder) {
642 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID, cur.loopIndex(), cur.loopDepth()));
643
644 TTY.print(cur.isExceptionEntry() ? " ex" : " ");
645 TTY.print(cur.isCriticalEdgeSplit() ? " ce" : " ");
646 TTY.print(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) ? " lh" : " ");
647 TTY.print(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd) ? " le" : " ");
648
649 if (cur.dominator() != null) {
650 TTY.print(" dom: B%d ", cur.dominator().blockID);
651 } else {
652 TTY.print(" dom: null ");
653 }
654
655 if (cur.numberOfPreds() > 0) {
656 TTY.print(" preds: ");
657 for (int j = 0; j < cur.numberOfPreds(); j++) {
658 BlockBegin pred = cur.predAt(j);
659 TTY.print("B%d ", pred.blockID);
660 }
661 }
662 if (cur.numberOfSux() > 0) {
663 TTY.print(" sux: ");
664 for (int j = 0; j < cur.numberOfSux(); j++) {
665 BlockBegin sux = cur.suxAt(j);
666 TTY.print("B%d ", sux.blockID);
667 }
668 }
669 if (cur.numberOfExceptionHandlers() > 0) {
670 TTY.print(" ex: ");
671 for (int j = 0; j < cur.numberOfExceptionHandlers(); j++) {
672 BlockBegin ex = cur.exceptionHandlerAt(j);
673 TTY.print("B%d ", ex.blockID);
674 }
675 }
676 TTY.println();
677 }
678 }
679 }
680
681 boolean verify() {
682 assert linearScanOrder.size() == numBlocks : "wrong number of blocks in list";
683
684 if (C1XOptions.StressLinearScan) {
685 // blocks are scrambled when StressLinearScan is used
686 return true;
687 }
688
689 // check that all successors of a block have a higher linear-scan-number
690 // and that all predecessors of a block have a lower linear-scan-number
691 // (only backward branches of loops are ignored)
692 int i;
693 for (i = 0; i < linearScanOrder.size(); i++) {
694 BlockBegin cur = linearScanOrder.get(i);
695
696 assert cur.linearScanNumber() == i : "incorrect linearScanNumber";
697 assert cur.linearScanNumber() >= 0 && cur.linearScanNumber() == linearScanOrder.indexOf(cur) : "incorrect linearScanNumber";
698
699 for (BlockBegin sux : cur.end().successors()) {
700 assert sux.linearScanNumber() >= 0 && sux.linearScanNumber() == linearScanOrder.indexOf(sux) : "incorrect linearScanNumber";
701 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) {
702 assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order";
703 }
704 if (cur.loopDepth() == sux.loopDepth()) {
705 assert cur.loopIndex() == sux.loopIndex() || sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
706 }
707 }
708
709 for (BlockBegin pred : cur.predecessors()) {
710 assert pred.linearScanNumber() >= 0 && pred.linearScanNumber() == linearScanOrder.indexOf(pred) : "incorrect linearScanNumber";
711 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
712 assert cur.linearScanNumber() > pred.linearScanNumber() : "invalid order";
713 }
714 if (cur.loopDepth() == pred.loopDepth()) {
715 assert cur.loopIndex() == pred.loopIndex() || cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
716 }
717
718 assert cur.dominator().linearScanNumber() <= pred.linearScanNumber() : "dominator must be before predecessors";
719 }
720
721 // check dominator
722 if (i == 0) {
723 assert cur.dominator() == null : "first block has no dominator";
724 } else {
725 assert cur.dominator() != null : "all but first block must have dominator";
726 }
727 assert cur.numberOfPreds() != 1 || cur.dominator() == cur.predAt(0) || cur.isExceptionEntry() : "Single predecessor must also be dominator";
728 }
729
730 // check that all loops are continuous
731 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
732 int blockIdx = 0;
733 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop";
734
735 // skip blocks before the loop
736 while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
737 blockIdx++;
738 }
739 // skip blocks of loop
740 while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
741 blockIdx++;
742 }
743 // after the first non-loop block : there must not be another loop-block
744 while (blockIdx < numBlocks) {
745 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order";
746 blockIdx++;
747 }
748 }
749
750 return true;
751 }
752 }