Mercurial > hg > truffle

comparison graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2708:4272b7af2d17

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge
author Lukas Stadler <lukas.stadler@jku.at>
date Wed, 18 May 2011 18:40:58 +0200
parents 7ed72769d51a efbdb3ea95c9
children bd85cf08720a
comparison
equal deleted inserted replaced
2707:7ed72769d51a 2708:4272b7af2d17
124 clearNonNaturalLoops(startBlock); 124 clearNonNaturalLoops(startBlock);
125 assignLoopDepth(startBlock); 125 assignLoopDepth(startBlock);
126 } 126 }
127 127
128 computeOrder(startBlock); 128 computeOrder(startBlock);
129 computeDominators();
130 129
131 printBlocks(); 130 printBlocks();
132 assert verify(); 131 assert verify();
133 } 132 }
134 133
142 */ 141 */
143 private void countEdges(final BlockBegin cur, BlockBegin parent) { 142 private void countEdges(final BlockBegin cur, BlockBegin parent) {
144 if (C1XOptions.TraceLinearScanLevel >= 3) { 143 if (C1XOptions.TraceLinearScanLevel >= 3) {
145 TTY.println("Counting edges for block B%d%s", cur.blockID, parent == null ? "" : " coming from B" + parent.blockID); 144 TTY.println("Counting edges for block B%d%s", cur.blockID, parent == null ? "" : " coming from B" + parent.blockID);
146 } 145 }
147 assert cur.dominator() == null : "dominator already initialized";
148 146
149 if (isActive(cur)) { 147 if (isActive(cur)) {
150 if (C1XOptions.TraceLinearScanLevel >= 3) { 148 if (C1XOptions.TraceLinearScanLevel >= 3) {
151 TTY.println("backward branch"); 149 TTY.println("backward branch");
152 } 150 }
218 int loopIdx = loopStart.loopIndex(); 216 int loopIdx = loopStart.loopIndex();
219 217
220 if (C1XOptions.TraceLinearScanLevel >= 3) { 218 if (C1XOptions.TraceLinearScanLevel >= 3) {
221 TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID, loopEnd.blockID, loopIdx); 219 TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID, loopEnd.blockID, loopIdx);
222 } 220 }
223 assert loopEnd.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd) : "loop end flag must be set"; 221 assert loopEnd.isLinearScanLoopEnd() : "loop end flag must be set";
224 assert loopStart.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "loop header flag must be set"; 222 assert loopStart.isLinearScanLoopHeader() : "loop header flag must be set";
225 assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set"; 223 assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set";
226 assert workList.isEmpty() : "work list must be empty before processing"; 224 assert workList.isEmpty() : "work list must be empty before processing";
227 225
228 // add the end-block of the loop to the working list 226 // add the end-block of the loop to the working list
229 workList.add(loopEnd); 227 workList.add(loopEnd);
315 }); 313 });
316 } 314 }
317 } while (!workList.isEmpty()); 315 } while (!workList.isEmpty());
318 } 316 }
319 317
320 private BlockBegin commonDominator(BlockBegin a, BlockBegin b) {
321 assert a != null && b != null : "must have input blocks";
322
323 dominatorBlocks.clearAll();
324 while (a != null) {
325 dominatorBlocks.set(a.blockID);
326 assert a.dominator() != null || a == linearScanOrder.get(0) : "dominator must be initialized";
327 a = a.dominator();
328 }
329 while (b != null && !dominatorBlocks.get(b.blockID)) {
330 assert b.dominator() != null || b == linearScanOrder.get(0) : "dominator must be initialized";
331 b = b.dominator();
332 }
333
334 assert b != null : "could not find dominator";
335 return b;
336 }
337
338 private void computeDominator(BlockBegin cur, BlockBegin parent) {
339 if (cur.dominator() == null) {
340 if (C1XOptions.TraceLinearScanLevel >= 4) {
341 TTY.println("DOM: initializing dominator of B%d to B%d", cur.blockID, parent.blockID);
342 }
343 cur.setDominator(parent);
344
345 } else if (!(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) && parent.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd))) {
346 if (C1XOptions.TraceLinearScanLevel >= 4) {
347 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);
348 }
349 assert cur.numberOfPreds() > 1 : "";
350 cur.setDominator(commonDominator(cur.dominator(), parent));
351 }
352 }
353
354 private int computeWeight(BlockBegin cur) { 318 private int computeWeight(BlockBegin cur) {
355 BlockBegin singleSux = null; 319 BlockBegin singleSux = null;
356 if (cur.numberOfSux() == 1) { 320 if (cur.numberOfSux() == 1) {
357 singleSux = cur.suxAt(0); 321 singleSux = cur.suxAt(0);
358 } 322 }
363 int curBit = 15; 327 int curBit = 15;
364 328
365 // this is necessary for the (very rare) case that two successive blocks have 329 // this is necessary for the (very rare) case that two successive blocks have
366 // the same loop depth, but a different loop index (can happen for endless loops 330 // the same loop depth, but a different loop index (can happen for endless loops
367 // with exception handlers) 331 // with exception handlers)
368 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) { 332 if (!cur.isLinearScanLoopHeader()) {
369 weight |= (1 << curBit); 333 weight |= (1 << curBit);
370 } 334 }
371 curBit--; 335 curBit--;
372 336
373 // loop end blocks (blocks that end with a backward branch) are added 337 // loop end blocks (blocks that end with a backward branch) are added
374 // after all other blocks of the loop. 338 // after all other blocks of the loop.
375 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) { 339 if (!cur.isLinearScanLoopEnd()) {
376 weight |= (1 << curBit);
377 }
378 curBit--;
379
380 // critical edge split blocks are preferred because then they have a greater
381 // probability to be completely empty
382 if (cur.isCriticalEdgeSplit()) {
383 weight |= (1 << curBit); 340 weight |= (1 << curBit);
384 } 341 }
385 curBit--; 342 curBit--;
386 343
387 // exceptions should not be thrown in normal control flow, so these blocks 344 // exceptions should not be thrown in normal control flow, so these blocks
491 final BlockBegin cur = workList.remove(workList.size() - 1); 448 final BlockBegin cur = workList.remove(workList.size() - 1);
492 appendBlock(cur); 449 appendBlock(cur);
493 450
494 cur.allSuccessorsDo(false, new BlockClosure() { 451 cur.allSuccessorsDo(false, new BlockClosure() {
495 public void apply(BlockBegin block) { 452 public void apply(BlockBegin block) {
496 computeDominator(block, cur);
497 if (readyForProcessing(block)) { 453 if (readyForProcessing(block)) {
498 sortIntoWorkList(block); 454 sortIntoWorkList(block);
499 } 455 }
500 } 456 }
501 }); 457 });
502 } while (workList.size() > 0); 458 } while (workList.size() > 0);
503 }
504
505 private boolean computeDominatorsIter() {
506 boolean changed = false;
507 int numBlocks = linearScanOrder.size();
508
509 assert linearScanOrder.get(0).dominator() == null : "must not have dominator";
510 assert linearScanOrder.get(0).numberOfPreds() == 0 : "must not have predecessors";
511 for (int i = 1; i < numBlocks; i++) {
512 BlockBegin block = linearScanOrder.get(i);
513
514 assert block.numberOfPreds() > 0;
515 BlockBegin dominator = block.predAt(0).block();
516
517 int numPreds = block.numberOfPreds();
518 for (int j = 1; j < numPreds; j++) {
519 BlockBegin curPred = block.predAt(j).block();
520 dominator = commonDominator(dominator, curPred);
521 }
522
523 if (dominator != block.dominator()) {
524 if (C1XOptions.TraceLinearScanLevel >= 4) {
525 TTY.println("DOM: updating dominator of B%d from B%d to B%d", block.blockID, block.dominator().blockID, dominator.blockID);
526 }
527 block.setDominator(dominator);
528 changed = true;
529 }
530 }
531 return changed;
532 }
533
534 private void computeDominators() {
535 if (C1XOptions.TraceLinearScanLevel >= 3) {
536 TTY.println("----- computing dominators (iterative computation required: %b)", iterativeDominators);
537 }
538
539 // iterative computation of dominators is only required for methods with non-natural loops
540 // and OSR-methods. For all other methods : the dominators computed when generating the
541 // linear scan block order are correct.
542 if (iterativeDominators) {
543 do {
544 if (C1XOptions.TraceLinearScanLevel >= 1) {
545 TTY.println("DOM: next iteration of fix-point calculation");
546 }
547 } while (computeDominatorsIter());
548 }
549
550 // check that dominators are correct
551 assert !computeDominatorsIter() : "fix point not reached";
552 } 459 }
553 460
554 public void printBlocks() { 461 public void printBlocks() {
555 if (C1XOptions.TraceLinearScanLevel >= 2) { 462 if (C1XOptions.TraceLinearScanLevel >= 2) {
556 TTY.println("----- loop information:"); 463 TTY.println("----- loop information:");
566 if (C1XOptions.TraceLinearScanLevel >= 1) { 473 if (C1XOptions.TraceLinearScanLevel >= 1) {
567 TTY.println("----- linear-scan block order:"); 474 TTY.println("----- linear-scan block order:");
568 for (BlockBegin cur : linearScanOrder) { 475 for (BlockBegin cur : linearScanOrder) {
569 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID, cur.loopIndex(), cur.loopDepth())); 476 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID, cur.loopIndex(), cur.loopDepth()));
570 477
571 TTY.print(cur.isCriticalEdgeSplit() ? " ce" : " "); 478 TTY.print(cur.isLinearScanLoopHeader() ? " lh" : " ");
572 TTY.print(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) ? " lh" : " "); 479 TTY.print(cur.isLinearScanLoopEnd() ? " le" : " ");
573 TTY.print(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd) ? " le" : " ");
574
575 if (cur.dominator() != null) {
576 TTY.print(" dom: B%d ", cur.dominator().blockID);
577 } else {
578 TTY.print(" dom: null ");
579 }
580 480
581 if (cur.numberOfPreds() > 0) { 481 if (cur.numberOfPreds() > 0) {
582 TTY.print(" preds: "); 482 TTY.print(" preds: ");
583 for (int j = 0; j < cur.numberOfPreds(); j++) { 483 for (int j = 0; j < cur.numberOfPreds(); j++) {
584 BlockBegin pred = cur.predAt(j).block(); 484 BlockBegin pred = cur.predAt(j).block();
632 assert cur.linearScanNumber() > begin.linearScanNumber() : "invalid order"; 532 assert cur.linearScanNumber() > begin.linearScanNumber() : "invalid order";
633 } 533 }
634 if (cur.loopDepth() == begin.loopDepth()) { 534 if (cur.loopDepth() == begin.loopDepth()) {
635 assert cur.loopIndex() == begin.loopIndex() || cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index"; 535 assert cur.loopIndex() == begin.loopIndex() || cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
636 } 536 }
637 537 }
638 assert cur.dominator().linearScanNumber() <= begin.linearScanNumber() : "dominator must be before predecessors";
639 }
640
641 // check dominator
642 if (i == 0) {
643 assert cur.dominator() == null : "first block has no dominator";
644 } else {
645 assert cur.dominator() != null : "all but first block must have dominator";
646 }
647 assert cur.numberOfPreds() != 1 || cur.dominator() == cur.predAt(0).block() : "Single predecessor must also be dominator";
648 } 538 }
649 539
650 // check that all loops are continuous 540 // check that all loops are continuous
651 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) { 541 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
652 int blockIdx = 0; 542 int blockIdx = 0;