Fix bugs in Scheduler hoisting and RPO loop bounds computations.

src/compiler/scheduler.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include <deque>
 #include <queue>
 
 #include "src/compiler/scheduler.h"
 
 #include "src/compiler/graph.h"
@@ skipping 543 matching lines @@
           }
           stack_depth--;
         }
       }
     }
 
     // Construct the final order from the list.
     BasicBlockVector* final_order = schedule_->rpo_order();
     order->Serialize(final_order);
 
-    // Compute the correct loop header for every block and set the correct loop
-    // ends.
+    // Compute the correct loop headersand set the correct loop ends.

[Michael Starzinger, 2014/10/24 13:36:43]

nit: Missing space.

[titzer, 2014/10/24 13:41:45]

Done.

     LoopInfo* current_loop = NULL;
     BasicBlock* current_header = NULL;
     int loop_depth = 0;
     for (BasicBlockVectorIter i = final_order->begin(); i != final_order->end();
          ++i) {
       BasicBlock* current = *i;
+
+      // Finish the previous loop(s) if we just exited them.
+      while (current_header != NULL &&
+             current->rpo_number() >= current_header->loop_end()) {
+        DCHECK(current_header->IsLoopHeader());
+        DCHECK(current_loop != NULL);
+        current_loop = current_loop->prev;
+        current_header = current_loop == NULL ? NULL : current_loop->header;
+        --loop_depth;
+      }
       current->set_loop_header(current_header);
+
+      // Push a new loop onto the stack if this loop is a loop header.
       if (current->IsLoopHeader()) {
         loop_depth++;
         current_loop = &loops[current->loop_end()];
         BlockList* end = current_loop->end;
         current->set_loop_end(end == NULL
                                   ? static_cast<int>(final_order->size())
                                   : end->block->rpo_number());
         current_header = current_loop->header;
         Trace("B%d is a loop header, increment loop depth to %d\n",
               current->id().ToInt(), loop_depth);
-      } else {
-        while (current_header != NULL &&
-               current->rpo_number() >= current_header->loop_end()) {
-          DCHECK(current_header->IsLoopHeader());
-          DCHECK(current_loop != NULL);
-          current_loop = current_loop->prev;
-          current_header = current_loop == NULL ? NULL : current_loop->header;
-          --loop_depth;
-        }
       }
+
       current->set_loop_depth(loop_depth);
+
       if (current->loop_header() == NULL) {
         Trace("B%d is not in a loop (depth == %d)\n", current->id().ToInt(),
               current->loop_depth());
       } else {
         Trace("B%d has loop header B%d, (depth == %d)\n", current->id().ToInt(),
               current->loop_header()->id().ToInt(), current->loop_depth());
       }
     }
 
     // Compute the assembly order (non-deferred code first, deferred code
@@ skipping 144 matching lines @@
         bool membership = loops[j].members->Contains(bid.ToInt());
         bool range = loops[j].header->LoopContains(block);
         os << (membership ? " |" : "  ");
         os << (range ? "x" : " ");
       }
       os << "  B" << bid << ": ";
       if (block->loop_end() >= 0) {
         os << " range: [" << block->rpo_number() << ", " << block->loop_end()
            << ")";
       }
+      if (block->loop_header() != NULL) {
+        os << " header: B" << block->loop_header()->id();
+      }
+      if (block->loop_depth() > 0) {
+        os << " depth: " << block->loop_depth();
+      }
       os << "\n";
     }
   }
 
   void VerifySpecialRPO(int num_loops, LoopInfo* loops,
                         BasicBlockVector* order) {
     DCHECK(order->size() > 0);
     DCHECK((*order)[0]->id().ToInt() == 0);  // entry should be first.
 
     for (int i = 0; i < num_loops; i++) {
       LoopInfo* loop = &loops[i];
       BasicBlock* header = loop->header;
 
       DCHECK(header != NULL);
       DCHECK(header->rpo_number() >= 0);
       DCHECK(header->rpo_number() < static_cast<int>(order->size()));
       DCHECK(header->loop_end() >= 0);
       DCHECK(header->loop_end() <= static_cast<int>(order->size()));
       DCHECK(header->loop_end() > header->rpo_number());
+      DCHECK(header->loop_header() != header);
 
       // Verify the start ... end list relationship.
       int links = 0;
       BlockList* l = loop->start;
       DCHECK(l != NULL && l->block == header);
       bool end_found;
       while (true) {
         if (l == NULL || l == loop->end) {
           end_found = (loop->end == l);
           break;
@@ skipping 279 matching lines @@
     DCHECK_NOT_NULL(block);
 
     int min_rpo = scheduler_->GetData(node)->minimum_block_->rpo_number();
     Trace("Schedule late of #%d:%s is B%d at loop depth %d, minimum_rpo = %d\n",
           node->id(), node->op()->mnemonic(), block->id().ToInt(),
           block->loop_depth(), min_rpo);
 
     // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
     // into enclosing loop pre-headers until they would preceed their
     // ScheduleEarly position.
-    BasicBlock* hoist_block = block;
+    BasicBlock* hoist_block = GetPreHeader(block);
     while (hoist_block != NULL && hoist_block->rpo_number() >= min_rpo) {
-      if (hoist_block->loop_depth() < block->loop_depth()) {
-        block = hoist_block;
-        Trace("  hoisting #%d:%s to block %d\n", node->id(),
-              node->op()->mnemonic(), block->id().ToInt());
-      }
-      // Try to hoist to the pre-header of the loop header.
-      hoist_block = hoist_block->loop_header();
-      if (hoist_block != NULL) {
-        BasicBlock* pre_header = hoist_block->dominator();
-        DCHECK(pre_header == NULL ||
-               *hoist_block->predecessors_begin() == pre_header);
-        Trace(
-            "  hoist to pre-header B%d of loop header B%d, depth would be %d\n",
-            pre_header->id().ToInt(), hoist_block->id().ToInt(),
-            pre_header->loop_depth());
-        hoist_block = pre_header;
-      }
+      Trace("  hoisting #%d:%s to block %d\n", node->id(),
+            node->op()->mnemonic(), hoist_block->id().ToInt());
+      DCHECK_LT(hoist_block->loop_depth(), block->loop_depth());
+      block = hoist_block;
+      hoist_block = GetPreHeader(hoist_block);
     }
 
     ScheduleNode(block, node);
   }
 
+  BasicBlock* GetPreHeader(BasicBlock* block) {

[Michael Starzinger, 2014/10/24 13:36:43]

nit: Please make this private (i.e. move it down two lines).

[titzer, 2014/10/24 13:41:45]

Done.

+    if (block->IsLoopHeader()) {
+      return block->dominator();
+    } else if (block->loop_header() != NULL) {
+      return block->loop_header()->dominator();
+    } else {
+      return NULL;
+    }
+  }
+
  private:
   BasicBlock* GetCommonDominatorOfUses(Node* node) {
     BasicBlock* block = NULL;
     Node::Uses uses = node->uses();
     for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) {
       BasicBlock* use_block = GetBlockForUse(i.edge());
       block = block == NULL ? use_block : use_block == NULL
                                               ? block
                                               : scheduler_->GetCommonDominator(
                                                     block, use_block);
@@ skipping 167 matching lines @@
   start->ReplaceInput(NodeProperties::FirstControlIndex(start), block_start);
 
   Trace("  Connecting floating control start %d:%s to %d:%s\n", start->id(),
         start->op()->mnemonic(), block_start->id(),
         block_start->op()->mnemonic());
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8