[v8-dev] [v8] r24877 committed - Fix bugs in Scheduler hoisting and RPO loop bounds computations....

codesite-noreply via v8-dev Fri, 24 Oct 2014 06:58:25 -0700

Revision: 24877
Author:   [email protected]
Date:     Fri Oct 24 13:57:32 2014 UTC
Log:      Fix bugs in Scheduler hoisting and RPO loop bounds computations.


[email protected]
BUG=

Review URL: https://codereview.chromium.org/677683002
https://code.google.com/p/v8/source/detail?r=24877

Modified:
 /branches/bleeding_edge/src/compiler/scheduler.cc
 /branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc

=======================================

--- /branches/bleeding_edge/src/compiler/scheduler.cc Fri Oct 24 12:32:422014 UTC+++ /branches/bleeding_edge/src/compiler/scheduler.cc Fri Oct 24 13:57:322014 UTC

@@ -562,15 +562,26 @@
     BasicBlockVector* final_order = schedule_->rpo_order();
     order->Serialize(final_order);

- // Compute the correct loop header for every block and set the correctloop

-    // ends.
+    // Compute the correct loop headers and set the correct loop ends.
     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()];
@@ -581,17 +592,10 @@
         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());
@@ -756,6 +760,12 @@

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";
     }
   }
@@ -775,6 +785,7 @@
       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;
@@ -1074,31 +1085,29 @@

// Hoist nodes out of loops if possible. Nodes can be hoistediteratively

     // 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 wouldbe %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);
   }

  private:
+  BasicBlock* GetPreHeader(BasicBlock* block) {
+    if (block->IsLoopHeader()) {
+      return block->dominator();
+    } else if (block->loop_header() != NULL) {
+      return block->loop_header()->dominator();
+    } else {
+      return NULL;
+    }
+  }
+
   BasicBlock* GetCommonDominatorOfUses(Node* node) {
     BasicBlock* block = NULL;
     Node::Uses uses = node->uses();
=======================================

--- /branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc Fri Oct24 13:48:02 2014 UTC+++ /branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc Fri Oct24 13:57:32 2014 UTC

@@ -24,12 +24,47 @@
 using namespace v8::internal::compiler;

 // TODO(titzer): pull RPO tests out to their own file.
+static void CheckRPONumbers(BasicBlockVector* order, size_t expected,
+                            bool loops_allowed) {
+  CHECK(expected == order->size());
+  for (int i = 0; i < static_cast<int>(order->size()); i++) {
+    CHECK(order->at(i)->rpo_number() == i);
+    if (!loops_allowed) {
+      CHECK_LT(order->at(i)->loop_end(), 0);
+      CHECK_EQ(NULL, order->at(i)->loop_header());
+    }
+  }
+}
+
+
+static void CheckLoop(BasicBlockVector* order, BasicBlock** blocks,
+                      int body_size) {
+  BasicBlock* header = blocks[0];
+  CHECK_GT(header->loop_end(), 0);
+  CHECK_EQ(body_size, (header->loop_end() - header->rpo_number()));
+  for (int i = 0; i < body_size; i++) {
+    int num = blocks[i]->rpo_number();
+    CHECK(num >= header->rpo_number() && num < header->loop_end());
+    CHECK(header->LoopContains(blocks[i]));
+    CHECK(header->IsLoopHeader() || blocks[i]->loop_header() == header);
+  }
+  if (header->rpo_number() > 0) {
+    CHECK_NE(order->at(header->rpo_number() - 1)->loop_header(), header);
+  }
+  if (header->loop_end() < static_cast<int>(order->size())) {
+    CHECK_NE(order->at(header->loop_end())->loop_header(), header);
+  }
+}
+
+
 struct TestLoop {
   int count;
   BasicBlock** nodes;
   BasicBlock* header() { return nodes[0]; }
   BasicBlock* last() { return nodes[count - 1]; }
   ~TestLoop() { delete[] nodes; }
+
+  void Check(BasicBlockVector* order) { CheckLoop(order, nodes, count); }
 };


@@ -46,29 +81,6 @@
   schedule->AddSuccessorForTesting(loop->nodes[count - 1], loop->nodes[0]);
   return loop;
 }
-
-
-static void CheckRPONumbers(BasicBlockVector* order, size_t expected,
-                            bool loops_allowed) {
-  CHECK(expected == order->size());
-  for (int i = 0; i < static_cast<int>(order->size()); i++) {
-    CHECK(order->at(i)->rpo_number() == i);
-    if (!loops_allowed) CHECK_LT(order->at(i)->loop_end(), 0);
-  }
-}
-
-
-static void CheckLoopContains(BasicBlock** blocks, int body_size) {
-  BasicBlock* header = blocks[0];
-  CHECK_GT(header->loop_end(), 0);
-  CHECK_EQ(body_size, (header->loop_end() - header->rpo_number()));
-  for (int i = 0; i < body_size; i++) {
-    int num = blocks[i]->rpo_number();
-    CHECK(num >= header->rpo_number() && num < header->loop_end());
-    CHECK(header->LoopContains(blocks[i]));
-    CHECK(header->IsLoopHeader() || blocks[i]->loop_header() == header);
-  }
-}


 static int GetScheduledNodeCount(Schedule* schedule) {
@@ -167,7 +179,7 @@