Mercurial > hg > graal-jvmci-8

comparison graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2653:7c8ad40c1f88

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
No need for stateAfter on volatile field loads.
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Wed, 11 May 2011 15:11:33 +0200
parents 6d19b4f476db
children 4a6518c4d17d
comparison
equal deleted inserted replaced
2652:6d19b4f476db 2653:7c8ad40c1f88
50 final List<BlockBegin> loopEndBlocks; // list of all loop end blocks collected during countEdges 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 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) 52 final List<BlockBegin> workList; // temporary list (used in markLoops and computeOrder)
53 53
54 // accessors for visitedBlocks and activeBlocks 54 // accessors for visitedBlocks and activeBlocks
55 void initVisited() { 55 private void initVisited() {
56 activeBlocks.clearAll(); 56 activeBlocks.clearAll();
57 visitedBlocks.clearAll(); 57 visitedBlocks.clearAll();
58 } 58 }
59 59
60 boolean isVisited(BlockBegin b) { 60 private boolean isVisited(BlockBegin b) {
61 return visitedBlocks.get(b.blockID); 61 return visitedBlocks.get(b.blockID);
62 } 62 }
63 63
64 boolean isActive(BlockBegin b) { 64 private boolean isActive(BlockBegin b) {
65 return activeBlocks.get(b.blockID); 65 return activeBlocks.get(b.blockID);
66 } 66 }
67 67
68 void setVisited(BlockBegin b) { 68 private void setVisited(BlockBegin b) {
69 assert !isVisited(b) : "already set"; 69 assert !isVisited(b) : "already set";
70 visitedBlocks.set(b.blockID); 70 visitedBlocks.set(b.blockID);
71 } 71 }
72 72
73 void setActive(BlockBegin b) { 73 private void setActive(BlockBegin b) {
74 assert !isActive(b) : "already set"; 74 assert !isActive(b) : "already set";
75 activeBlocks.set(b.blockID); 75 activeBlocks.set(b.blockID);
76 } 76 }
77 77
78 void clearActive(BlockBegin b) { 78 private void clearActive(BlockBegin b) {
79 assert isActive(b) : "not already"; 79 assert isActive(b) : "not already";
80 activeBlocks.clear(b.blockID); 80 activeBlocks.clear(b.blockID);
81 } 81 }
82 82
83 // accessors for forwardBranches 83 // accessors for forwardBranches
84 void incForwardBranches(BlockBegin b) { 84 private void incForwardBranches(BlockBegin b) {
85 forwardBranches[b.blockID]++; 85 forwardBranches[b.blockID]++;
86 } 86 }
87 87
88 int decForwardBranches(BlockBegin b) { 88 private int decForwardBranches(BlockBegin b) {
89 return --forwardBranches[b.blockID]; 89 return --forwardBranches[b.blockID];
90 } 90 }
91 91
92 // accessors for loopMap 92 // accessors for loopMap
93 boolean isBlockInLoop(int loopIdx, BlockBegin b) { 93 private boolean isBlockInLoop(int loopIdx, BlockBegin b) {
94 return loopMap.at(loopIdx, b.blockID); 94 return loopMap.at(loopIdx, b.blockID);
95 } 95 }
96 96
97 void setBlockInLoop(int loopIdx, BlockBegin b) { 97 private void setBlockInLoop(int loopIdx, BlockBegin b) {
98 loopMap.setBit(loopIdx, b.blockID); 98 loopMap.setBit(loopIdx, b.blockID);
99 } 99 }
100 100
101 void clearBlockInLoop(int loopIdx, int blockId) { 101 private void clearBlockInLoop(int loopIdx, int blockId) {
102 loopMap.clearBit(loopIdx, blockId); 102 loopMap.clearBit(loopIdx, blockId);
103 } 103 }
104 104
105 // accessors for final result 105 // accessors for final result
106 public List<BlockBegin> linearScanOrder() { 106 public List<BlockBegin> linearScanOrder() {
119 dominatorBlocks = new CiBitMap(maxBlockId); 119 dominatorBlocks = new CiBitMap(maxBlockId);
120 forwardBranches = new int[maxBlockId]; 120 forwardBranches = new int[maxBlockId];
121 loopEndBlocks = new ArrayList<BlockBegin>(8); 121 loopEndBlocks = new ArrayList<BlockBegin>(8);
122 workList = new ArrayList<BlockBegin>(8); 122 workList = new ArrayList<BlockBegin>(8);
123 123
124 splitCriticalEdges();
125
126 countEdges(startBlock, null); 124 countEdges(startBlock, null);
127 125
128 if (numLoops > 0) { 126 if (numLoops > 0) {
129 markLoops(); 127 markLoops();
130 clearNonNaturalLoops(startBlock); 128 clearNonNaturalLoops(startBlock);
134 computeOrder(startBlock); 132 computeOrder(startBlock);
135 computeDominators(); 133 computeDominators();
136 134
137 printBlocks(); 135 printBlocks();
138 assert verify(); 136 assert verify();
139 }
140
141 void splitCriticalEdges() {
142 // TODO: move critical edge splitting from IR to here
143 } 137 }
144 138
145 /** 139 /**
146 * Traverses the CFG to analyze block and edge info. The analysis performed is: 140 * Traverses the CFG to analyze block and edge info. The analysis performed is:
147 * 141 *
148 * 1. Count of total number of blocks. 142 * 1. Count of total number of blocks.
149 * 2. Count of all incoming edges and backward incoming edges. 143 * 2. Count of all incoming edges and backward incoming edges.
150 * 3. Number loop header blocks. 144 * 3. Number loop header blocks.
151 * 4. Create a list with all loop end blocks. 145 * 4. Create a list with all loop end blocks.
152 */ 146 */
153 void countEdges(BlockBegin cur, BlockBegin parent) { 147 private void countEdges(BlockBegin cur, BlockBegin parent) {
154 if (C1XOptions.TraceLinearScanLevel >= 3) { 148 if (C1XOptions.TraceLinearScanLevel >= 3) {
155 TTY.println("Counting edges for block B%d%s", cur.blockID, parent == null ? "" : " coming from B" + parent.blockID); 149 TTY.println("Counting edges for block B%d%s", cur.blockID, parent == null ? "" : " coming from B" + parent.blockID);
156 } 150 }
157 assert cur.dominator() == null : "dominator already initialized"; 151 assert cur.dominator() == null : "dominator already initialized";
158 152
174 if (cur.checkBlockFlag(BlockBegin.BlockFlag.ExceptionEntry)) { 168 if (cur.checkBlockFlag(BlockBegin.BlockFlag.ExceptionEntry)) {
175 // Make sure that dominators are correct in this weird situation 169 // Make sure that dominators are correct in this weird situation
176 iterativeDominators = true; 170 iterativeDominators = true;
177 return; 171 return;
178 } 172 }
179 // assert parent.numberOfSux() == 1 && parent.suxAt(0) == cur : "loop end blocks must have one successor (critical edges are split)";
180 173
181 loopEndBlocks.add(parent); 174 loopEndBlocks.add(parent);
182 return; 175 return;
183 } 176 }
184 177
225 if (C1XOptions.TraceLinearScanLevel >= 3) { 218 if (C1XOptions.TraceLinearScanLevel >= 3) {
226 TTY.println("Finished counting edges for block B%d", cur.blockID); 219 TTY.println("Finished counting edges for block B%d", cur.blockID);
227 } 220 }
228 } 221 }
229 222
230 void markLoops() { 223 private void markLoops() {
231 if (C1XOptions.TraceLinearScanLevel >= 3) { 224 if (C1XOptions.TraceLinearScanLevel >= 3) {
232 TTY.println("----- marking loops"); 225 TTY.println("----- marking loops");
233 } 226 }
234 227
235 loopMap = new BitMap2D(numLoops, maxBlockId); 228 loopMap = new BitMap2D(numLoops, maxBlockId);
241 234
242 if (C1XOptions.TraceLinearScanLevel >= 3) { 235 if (C1XOptions.TraceLinearScanLevel >= 3) {
243 TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID, loopEnd.blockID, loopIdx); 236 TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID, loopEnd.blockID, loopIdx);
244 } 237 }
245 assert loopEnd.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd) : "loop end flag must be set"; 238 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"; 239 assert loopStart.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "loop header flag must be set";
248 assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set"; 240 assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set";
249 assert workList.isEmpty() : "work list must be empty before processing"; 241 assert workList.isEmpty() : "work list must be empty before processing";
250 242
251 // add the end-block of the loop to the working list 243 // add the end-block of the loop to the working list
279 } 271 }
280 272
281 // check for non-natural loops (loops where the loop header does not dominate 273 // check for non-natural loops (loops where the loop header does not dominate
282 // all other loop blocks = loops with multiple entries). 274 // all other loop blocks = loops with multiple entries).
283 // such loops are ignored 275 // such loops are ignored
284 void clearNonNaturalLoops(BlockBegin startBlock) { 276 private void clearNonNaturalLoops(BlockBegin startBlock) {
285 for (int i = numLoops - 1; i >= 0; i--) { 277 for (int i = numLoops - 1; i >= 0; i--) {
286 if (isBlockInLoop(i, startBlock)) { 278 if (isBlockInLoop(i, startBlock)) {
287 // loop i contains the entry block of the method. 279 // loop i contains the entry block of the method.
288 // this is not a natural loop, so ignore it 280 // this is not a natural loop, so ignore it
289 if (C1XOptions.TraceLinearScanLevel >= 2) { 281 if (C1XOptions.TraceLinearScanLevel >= 2) {
296 iterativeDominators = true; 288 iterativeDominators = true;
297 } 289 }
298 } 290 }
299 } 291 }
300 292
301 void assignLoopDepth(BlockBegin startBlock) { 293 private void assignLoopDepth(BlockBegin startBlock) {
302 if (C1XOptions.TraceLinearScanLevel >= 3) { 294 if (C1XOptions.TraceLinearScanLevel >= 3) {
303 TTY.println("----- computing loop-depth and weight"); 295 TTY.println("----- computing loop-depth and weight");
304 } 296 }
305 initVisited(); 297 initVisited();
306 298
339 } 331 }
340 } 332 }
341 } while (!workList.isEmpty()); 333 } while (!workList.isEmpty());
342 } 334 }
343 335
344 BlockBegin commonDominator(BlockBegin a, BlockBegin b) { 336 private BlockBegin commonDominator(BlockBegin a, BlockBegin b) {
345 assert a != null && b != null : "must have input blocks"; 337 assert a != null && b != null : "must have input blocks";
346 338
347 dominatorBlocks.clearAll(); 339 dominatorBlocks.clearAll();
348 while (a != null) { 340 while (a != null) {
349 dominatorBlocks.set(a.blockID); 341 dominatorBlocks.set(a.blockID);
357 349
358 assert b != null : "could not find dominator"; 350 assert b != null : "could not find dominator";
359 return b; 351 return b;
360 } 352 }
361 353
362 void computeDominator(BlockBegin cur, BlockBegin parent) { 354 private void computeDominator(BlockBegin cur, BlockBegin parent) {
363 if (cur.dominator() == null) { 355 if (cur.dominator() == null) {
364 if (C1XOptions.TraceLinearScanLevel >= 4) { 356 if (C1XOptions.TraceLinearScanLevel >= 4) {
365 TTY.println("DOM: initializing dominator of B%d to B%d", cur.blockID, parent.blockID); 357 TTY.println("DOM: initializing dominator of B%d to B%d", cur.blockID, parent.blockID);
366 } 358 }
367 if (cur.isExceptionEntry()) { 359 if (cur.isExceptionEntry()) {
378 assert cur.numberOfPreds() > 1 : ""; 370 assert cur.numberOfPreds() > 1 : "";
379 cur.setDominator(commonDominator(cur.dominator(), parent)); 371 cur.setDominator(commonDominator(cur.dominator(), parent));
380 } 372 }
381 } 373 }
382 374
383 int computeWeight(BlockBegin cur) { 375 private int computeWeight(BlockBegin cur) {
384 BlockBegin singleSux = null; 376 BlockBegin singleSux = null;
385 if (cur.numberOfSux() == 1) { 377 if (cur.numberOfSux() == 1) {
386 singleSux = cur.suxAt(0); 378 singleSux = cur.suxAt(0);
387 } 379 }
388 380
437 assert weight > 0 : "weight cannot become negative"; 429 assert weight > 0 : "weight cannot become negative";
438 430
439 return weight; 431 return weight;
440 } 432 }
441 433
442 boolean readyForProcessing(BlockBegin cur) { 434 private boolean readyForProcessing(BlockBegin cur) {
443 // Discount the edge just traveled. 435 // Discount the edge just traveled.
444 // When the number drops to zero, all forward branches were processed 436 // When the number drops to zero, all forward branches were processed
445 if (decForwardBranches(cur) != 0) { 437 if (decForwardBranches(cur) != 0) {
446 return false; 438 return false;
447 } 439 }
449 assert !linearScanOrder.contains(cur) : "block already processed (block can be ready only once)"; 441 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)"; 442 assert !workList.contains(cur) : "block already in work-list (block can be ready only once)";
451 return true; 443 return true;
452 } 444 }
453 445
454 void sortIntoWorkList(BlockBegin cur) { 446 private void sortIntoWorkList(BlockBegin cur) {
455 assert !workList.contains(cur) : "block already in work list"; 447 assert !workList.contains(cur) : "block already in work list";
456 448
457 int curWeight = computeWeight(cur); 449 int curWeight = computeWeight(cur);
458 450
459 // the linearScanNumber is used to cache the weight of a block 451 // the linearScanNumber is used to cache the weight of a block
484 assert workList.get(i).linearScanNumber() > 0 : "weight not set"; 476 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"; 477 assert i == 0 || workList.get(i - 1).linearScanNumber() <= workList.get(i).linearScanNumber() : "incorrect order in worklist";
486 } 478 }
487 } 479 }
488 480
489 void appendBlock(BlockBegin cur) { 481 private void appendBlock(BlockBegin cur) {
490 if (C1XOptions.TraceLinearScanLevel >= 3) { 482 if (C1XOptions.TraceLinearScanLevel >= 3) {
491 TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID, cur.linearScanNumber()); 483 TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID, cur.linearScanNumber());
492 } 484 }
493 assert !linearScanOrder.contains(cur) : "cannot add the same block twice"; 485 assert !linearScanOrder.contains(cur) : "cannot add the same block twice";
494 486
497 // be equal. 489 // be equal.
498 cur.setLinearScanNumber(linearScanOrder.size()); 490 cur.setLinearScanNumber(linearScanOrder.size());
499 linearScanOrder.add(cur); 491 linearScanOrder.add(cur);
500 } 492 }
501 493
502 void computeOrder(BlockBegin startBlock) { 494 private void computeOrder(BlockBegin startBlock) {
503 if (C1XOptions.TraceLinearScanLevel >= 3) { 495 if (C1XOptions.TraceLinearScanLevel >= 3) {
504 TTY.println("----- computing final block order"); 496 TTY.println("----- computing final block order");
505 } 497 }
506 498
507 // the start block is always the first block in the linear scan order 499 // the start block is always the first block in the linear scan order
545 } 537 }
546 } 538 }
547 } while (workList.size() > 0); 539 } while (workList.size() > 0);
548 } 540 }
549 541
550 boolean computeDominatorsIter() { 542 private boolean computeDominatorsIter() {
551 boolean changed = false; 543 boolean changed = false;
552 int numBlocks = linearScanOrder.size(); 544 int numBlocks = linearScanOrder.size();
553 545
554 assert linearScanOrder.get(0).dominator() == null : "must not have dominator"; 546 assert linearScanOrder.get(0).dominator() == null : "must not have dominator";
555 assert linearScanOrder.get(0).numberOfPreds() == 0 : "must not have predecessors"; 547 assert linearScanOrder.get(0).numberOfPreds() == 0 : "must not have predecessors";
580 } 572 }
581 } 573 }
582 return changed; 574 return changed;
583 } 575 }
584 576
585 void computeDominators() { 577 private void computeDominators() {
586 if (C1XOptions.TraceLinearScanLevel >= 3) { 578 if (C1XOptions.TraceLinearScanLevel >= 3) {
587 TTY.println("----- computing dominators (iterative computation reqired: %b)", iterativeDominators); 579 TTY.println("----- computing dominators (iterative computation required: %b)", iterativeDominators);
588 } 580 }
589 581
590 // iterative computation of dominators is only required for methods with non-natural loops 582 // iterative computation of dominators is only required for methods with non-natural loops
591 // and OSR-methods. For all other methods : the dominators computed when generating the 583 // and OSR-methods. For all other methods : the dominators computed when generating the
592 // linear scan block order are correct. 584 // linear scan block order are correct.
654 TTY.println(); 646 TTY.println();
655 } 647 }
656 } 648 }
657 } 649 }
658 650
659 boolean verify() { 651 private boolean verify() {
660 assert linearScanOrder.size() == numBlocks : "wrong number of blocks in list"; 652 assert linearScanOrder.size() == numBlocks : "wrong number of blocks in list";
661 653
662 if (C1XOptions.StressLinearScan) { 654 if (C1XOptions.StressLinearScan) {
663 // blocks are scrambled when StressLinearScan is used 655 // blocks are scrambled when StressLinearScan is used
664 return true; 656 return true;