Mercurial > hg > graal-jvmci-8
comparison graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2653:7c8ad40c1f88
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; |