Mercurial > hg > truffle

comparison graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java @ 10920:9802c478a26c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
author Bernhard Urban <bernhard.urban@jku.at>
date Thu, 01 Aug 2013 17:23:30 +0200
parents 2cf0785957fb
children b73121a215f7
comparison
equal deleted inserted replaced
10919:2cf0785957fb 10920:9802c478a26c
382 printNode(n); 382 printNode(n);
383 } 383 }
384 } 384 }
385 } 385 }
386 TTY.print("\n\n"); 386 TTY.print("\n\n");
387 TTY.flush();
387 } 388 }
388 } 389 }
389 390
390 private static void printNode(Node n) { 391 private static void printNode(Node n) {
391 TTY.print("%s", n); 392 TTY.print("%s", n);
399 } else if (n instanceof FloatingReadNode) { 400 } else if (n instanceof FloatingReadNode) {
400 FloatingReadNode frn = (FloatingReadNode) n; 401 FloatingReadNode frn = (FloatingReadNode) n;
401 TTY.print(" // from %s", frn.location().getLocationIdentity()); 402 TTY.print(" // from %s", frn.location().getLocationIdentity());
402 TTY.print(", lastAccess: %s", frn.lastLocationAccess()); 403 TTY.print(", lastAccess: %s", frn.lastLocationAccess());
403 TTY.print(", object: %s", frn.object()); 404 TTY.print(", object: %s", frn.object());
405 } else if (n instanceof GuardNode) {
406 TTY.print(", guard: %s", ((GuardNode) n).getGuard());
404 } 407 }
405 TTY.print("\n"); 408 TTY.print("\n");
406 } 409 }
407 410
408 public ControlFlowGraph getCFG() { 411 public ControlFlowGraph getCFG() {
472 case EARLIEST: 475 case EARLIEST:
473 block = earliestBlock(node); 476 block = earliestBlock(node);
474 break; 477 break;
475 case LATEST: 478 case LATEST:
476 case LATEST_OUT_OF_LOOPS: 479 case LATEST_OUT_OF_LOOPS:
477 if (memsched == MemoryScheduling.OPTIMAL && node instanceof FloatingReadNode) { 480 if (memsched == MemoryScheduling.OPTIMAL && node instanceof FloatingReadNode && ((FloatingReadNode) node).location().getLocationIdentity() != FINAL_LOCATION) {
478 block = optimalBlock((FloatingReadNode) node, strategy); 481 block = optimalBlock((FloatingReadNode) node, strategy);
479 } else { 482 } else {
480 block = latestBlock(node, strategy); 483 block = latestBlock(node, strategy);
481 } 484 if (block == null) {
482 if (block == null) { 485 block = earliestBlock(node);
483 block = earliestBlock(node); 486 } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) {
484 } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) { 487 // schedule at the latest position possible in the outermost loop possible
485 // schedule at the latest position possible in the outermost loop possible 488 Block earliestBlock = earliestBlock(node);
486 Block earliestBlock = earliestBlock(node); 489 Block before = block;
487 Block before = block; 490 block = scheduleOutOfLoops(node, block, earliestBlock);
488 block = scheduleOutOfLoops(node, block, earliestBlock); 491 if (!earliestBlock.dominates(block)) {
489 if (!earliestBlock.dominates(block)) { 492 throw new SchedulingError("%s: Graph cannot be scheduled : inconsistent for %s, %d usages, (%s needs to dominate %s (before %s))", node.graph(), node,
490 throw new SchedulingError("%s: Graph cannot be scheduled : inconsistent for %s, %d usages, (%s needs to dominate %s (before %s))", node.graph(), node, node.usages().count(), 493 node.usages().count(), earliestBlock, block, before);
491 earliestBlock, block, before); 494 }
492 } 495 }
493 } 496 }
494 break; 497 break;
495 default: 498 default:
496 throw new GraalInternalError("unknown scheduling strategy"); 499 throw new GraalInternalError("unknown scheduling strategy");
497 } 500 }
501 assert earliestBlock(node).dominates(block) : "node " + node + " in block " + block + " is not dominated by earliest " + earliestBlock(node);
498 cfg.getNodeToBlock().set(node, block); 502 cfg.getNodeToBlock().set(node, block);
499 blockToNodesMap.get(block).add(node); 503 blockToNodesMap.get(block).add(node);
500 } 504 }
501 505
502 // assign floating read to block according to kill maps 506 /**
507 * this method tries to find the latest position for a read, by taking the information gathered
508 * by {@link NewMemoryScheduleClosure} into account.
509 *
510 * The idea is to iterate the dominator tree starting with the latest schedule of the read.
511 *
512 * <pre>
513 * U upperbound block, defined by last access location of the floating read
514 * &#9650;
515 * E earliest block
516 * &#9650;
517 * O optimal block, first block that contains a kill of the read's location
518 * &#9650;
519 * L latest block
520 * </pre>
521 *
522 * i.e. <code>upperbound `dom` earliest `dom` optimal `dom` latest</code>. However, there're
523 * cases where <code>earliest `dom` optimal</code> is not true, because the position is
524 * (impliclitly) bounded by an anchor of the read's guard. In such cases, the earliest schedule
525 * is taken.
526 *
527 */
503 private Block optimalBlock(FloatingReadNode n, SchedulingStrategy strategy) { 528 private Block optimalBlock(FloatingReadNode n, SchedulingStrategy strategy) {
504 assert memsched == MemoryScheduling.OPTIMAL; 529 assert memsched == MemoryScheduling.OPTIMAL;
505 530
506 LocationIdentity locid = n.location().getLocationIdentity(); 531 LocationIdentity locid = n.location().getLocationIdentity();
507 if (locid == FINAL_LOCATION) { 532 assert locid != FINAL_LOCATION;
508 return latestBlock(n, strategy); 533
509 }
510 Node upperBound = n.lastLocationAccess(); 534 Node upperBound = n.lastLocationAccess();
511 Block upperBoundBlock = forKillLocation(upperBound); 535 Block upperBoundBlock = forKillLocation(upperBound);
512 Block earliestBlock = earliestBlock(n); 536 Block earliestBlock = earliestBlock(n);
513 assert upperBoundBlock.dominates(earliestBlock) : "upper bound (" + upperBoundBlock + ") should dominate earliest (" + earliestBlock + ")"; 537 assert upperBoundBlock.dominates(earliestBlock) : "upper bound (" + upperBoundBlock + ") should dominate earliest (" + earliestBlock + ")";
514 538
515 Block currentBlock = latestBlock(n, strategy); 539 Block currentBlock = latestBlock(n, strategy);
516 assert currentBlock != null && earliestBlock.dominates(currentBlock) : "earliest (" + earliestBlock + ") should dominate latest block (" + currentBlock + ")"; 540 assert currentBlock != null && earliestBlock.dominates(currentBlock) : "earliest (" + earliestBlock + ") should dominate latest block (" + currentBlock + ")";
517 Block previousBlock = currentBlock; 541 Block previousBlock = currentBlock;
518 542
543 if (dumpSchedule) {
544 TTY.print("processing %s (accessing %s): latest %s, earliest %s, upper bound %s (%s)\n", n, locid, currentBlock, earliestBlock, upperBoundBlock, upperBound);
545 }
546
519 int iterations = 0; 547 int iterations = 0;
520 // iterate the dominator tree until the last kill matches or reaching a upper bound 548 // iterate the dominator tree
521 while (true) { 549 while (true) {
522 iterations++; 550 iterations++;
551 assert earliestBlock.dominates(previousBlock) : "iterations: " + iterations;
523 Node lastKill = blockToKillMap.get(currentBlock).get(locid); 552 Node lastKill = blockToKillMap.get(currentBlock).get(locid);
553 boolean isAtEarliest = earliestBlock == previousBlock && previousBlock != currentBlock;
524 554
525 if (lastKill.equals(upperBound)) { 555 if (lastKill.equals(upperBound)) {
526 // assign node to the block which kills the location 556 // assign node to the block which kills the location
527 557
528 if (previousBlock.getBeginNode() instanceof MergeNode) { 558 boolean outOfLoop = false;
529 // merges kill locations right at the beginning of a block 559
560 // schedule read out of the loop if possible, in terms of killMaps and earliest
561 // schedule
562 if (currentBlock != earliestBlock && previousBlock != earliestBlock) {
563 assert earliestBlock.dominates(currentBlock);
564 Block t = currentBlock;
565 while (t.getLoop() != null && t.getDominator() != null && earliestBlock.dominates(t)) {
566 Block dom = t.getDominator();
567 if (dom.getLoopDepth() < currentBlock.getLoopDepth() && blockToKillMap.get(dom).get(locid) == upperBound && earliestBlock.dominates(dom)) {
568 printIterations(iterations, "moved out of loop, from " + currentBlock + " to " + dom);
569 previousBlock = currentBlock = dom;
570 outOfLoop = true;
571 }
572 t = dom;
573 }
574 }
575
576 if (!outOfLoop && previousBlock.getBeginNode() instanceof MergeNode) {
577 // merges kill locations right at the beginning of a block. if a merge is the
578 // killing node, we assign it to the dominating node.
579
530 MergeNode merge = (MergeNode) previousBlock.getBeginNode(); 580 MergeNode merge = (MergeNode) previousBlock.getBeginNode();
531 if (getMergeToKillMap().get(merge).containsKey(locid)) { 581 Node killer = getMergeToKillMap().get(merge).get(locid);
532 printIterations(iterations, "kill by merge"); 582
583 if (killer != null && killer == merge) {
584 // check if we violate earliest schedule condition
585 if (isAtEarliest) {
586 printIterations(iterations, "earliest bound in merge: " + earliestBlock);
587 return earliestBlock;
588 }
589 printIterations(iterations, "kill by merge: " + currentBlock);
533 return currentBlock; 590 return currentBlock;
534 } 591 }
535 } 592 }
536 593
537 printIterations(iterations, "regular kill"); 594 // current block matches last access, that means the previous (dominated) block
595 // kills the location, therefore schedule read to previous block.
596 printIterations(iterations, "regular kill: " + previousBlock);
538 return previousBlock; 597 return previousBlock;
539 } 598 }
540 599
541 if (upperBoundBlock == currentBlock) { // reached upper bound 600 if (isAtEarliest) {
542 printIterations(iterations, "upper bound"); 601 printIterations(iterations, "earliest bound: " + earliestBlock);
543 return currentBlock; 602 return earliestBlock;
544 } 603 }
545 604
546 if (earliestBlock == currentBlock) { // reached earliest block 605 if (upperBoundBlock == currentBlock) {
547 printIterations(iterations, "earliest block"); 606 printIterations(iterations, "upper bound: " + currentBlock + ", previous: " + previousBlock);
548 return currentBlock; 607 return currentBlock;
549 } 608 }
550 609
551 previousBlock = currentBlock; 610 previousBlock = currentBlock;
552 currentBlock = currentBlock.getDominator(); 611 currentBlock = currentBlock.getDominator();
554 } 613 }
555 } 614 }
556 615
557 private void printIterations(int iterations, String desc) { 616 private void printIterations(int iterations, String desc) {
558 if (dumpSchedule) { 617 if (dumpSchedule) {
559 TTY.print("\niterations: %d, %s\n\n", iterations, desc); 618 TTY.print("iterations: %d, %s\n", iterations, desc);
560 } 619 }
561 } 620 }
562 621
563 /** 622 /**
564 * Calculates the last block that the given node could be scheduled in, i.e., the common 623 * Calculates the last block that the given node could be scheduled in, i.e., the common
586 } 645 }
587 cdbc.apply(cfg.getNodeToBlock().get(usage)); 646 cdbc.apply(cfg.getNodeToBlock().get(usage));
588 } 647 }
589 } 648 }
590 649
591 assert cdbc.block == null || earliestBlock(node).dominates(cdbc.block) : "failed to find correct latest schedule for " + node; 650 assert cdbc.block == null || earliestBlock(node).dominates(cdbc.block) : "failed to find correct latest schedule for " + node + ". cdbc: " + cdbc.block + ", earliest: " + earliestBlock(node);
592 return cdbc.block; 651 return cdbc.block;
593 } 652 }
594 653
595 /** 654 /**
596 * A closure that will calculate the common dominator of all blocks passed to its 655 * A closure that will calculate the common dominator of all blocks passed to its