[turbofan] Fix bug in OSR deconstruction.

src/compiler/osr.cc

Index: src/compiler/osr.cc
diff --git a/src/compiler/osr.cc b/src/compiler/osr.cc
index b7cd7ec93f919791d32ea0ee48bb15857cd55b52..c55a27e2a7bb7751bc2f7134b3a5223e5ccd5baf 100644
--- a/src/compiler/osr.cc
+++ b/src/compiler/osr.cc
@@ -26,6 +26,18 @@ OsrHelper::OsrHelper(CompilationInfo* info)
                         info->osr_expr_stack_height()) {}
 
 
+#ifdef DEBUG
+#define TRACE_COND (FLAG_trace_turbo_graph && FLAG_trace_osr)
+#else
+#define TRACE_COND false
+#endif
+
+#define TRACE(...)         \
+  if (TRACE_COND) do {     \

[Michael Starzinger, 2015/03/17 16:30:04]

nit: Shouldn't the if-statement go into the do-while-false?

[titzer, 2015/03/17 16:41:29]

Done.

+      PrintF(__VA_ARGS__); \
+  } while (false)
+
+
 // Peel outer loops and rewire the graph so that control reduction can
 // produce a properly formed graph.
 static void PeelOuterLoopsForOsr(Graph* graph, CommonOperatorBuilder* common,
@@ -44,6 +56,9 @@ static void PeelOuterLoopsForOsr(Graph* graph, CommonOperatorBuilder* common,
     NodeVector* mapping =
         new (stuff) NodeVector(original_count, sentinel, tmp_zone);
     copies.push_back(mapping);
+    TRACE("OsrDuplication #%zu, depth %zu, header #%d:%s\n", copies.size(),
+          loop->depth(), loop_tree->HeaderNode(loop)->id(),
+          loop_tree->HeaderNode(loop)->op()->mnemonic());
 
     // Prepare the mapping for OSR values and the OSR loop entry.
     mapping->at(osr_normal_entry->id()) = dead;
@@ -54,6 +69,8 @@ static void PeelOuterLoopsForOsr(Graph* graph, CommonOperatorBuilder* common,
          outer = outer->parent()) {
       for (Node* node : loop_tree->HeaderNodes(outer)) {
         mapping->at(node->id()) = dead;
+        TRACE(" ---- #%d:%s -> dead (header)\n", node->id(),
+              node->op()->mnemonic());
       }
     }
 
@@ -82,71 +99,132 @@ static void PeelOuterLoopsForOsr(Graph* graph, CommonOperatorBuilder* common,
         NodeProperties::SetBounds(copy, NodeProperties::GetBounds(orig));
       }
       mapping->at(orig->id()) = copy;
+      TRACE(" copy #%d:%s -> #%d\n", orig->id(), orig->op()->mnemonic(),
+            copy->id());
     }
 
     // Fix missing inputs.
-    for (size_t i = 0; i < all.live.size(); i++) {
-      Node* orig = all.live[i];
+    for (Node* orig : all.live) {
       Node* copy = mapping->at(orig->id());
       for (int j = 0; j < copy->InputCount(); j++) {
-        Node* input = copy->InputAt(j);
-        if (input == sentinel)
+        if (copy->InputAt(j) == sentinel) {
           copy->ReplaceInput(j, mapping->at(orig->InputAt(j)->id()));
+        }
       }
     }
 
-    // Construct the transfer from the previous graph copies to the new copy.
+    // Construct the entry into this loop from previous copies.
+
+    // Gather the live loop header nodes, {loop_header} first.
     Node* loop_header = loop_tree->HeaderNode(loop);
-    NodeVector* previous =
-        copies.size() > 1 ? copies[copies.size() - 2] : nullptr;
-    const int backedges = loop_header->op()->ControlInputCount() - 1;
-    if (backedges == 1) {
-      // Simple case. Map the incoming edges to the loop to the previous copy.
-      for (Node* node : loop_tree->HeaderNodes(loop)) {
-        if (!all.IsLive(node)) continue;  // dead phi hanging off loop.
+    NodeVector header_nodes(tmp_zone);
+    header_nodes.reserve(loop->HeaderSize());
+    header_nodes.push_back(loop_header);  // put the loop header first.
+    for (Node* node : loop_tree->HeaderNodes(loop)) {
+      if (node != loop_header && all.IsLive(node)) {
+        header_nodes.push_back(node);
+      }
+    }
+
+    // Gather backedges from the previous copies of the inner loops of {loop}.
+    NodeVectorVector backedges(tmp_zone);
+    TRACE("Gathering backedges...\n");
+    for (int i = 1; i < loop_header->InputCount(); i++) {
+      if (TRACE_COND) {
+        Node* control = loop_header->InputAt(i);
+        size_t incoming_depth = 0;
+        for (int j = 0; j < control->op()->ControlInputCount(); j++) {
+          Node* k = NodeProperties::GetControlInput(control, j);
+          incoming_depth =
+              std::max(incoming_depth, loop_tree->ContainingLoop(k)->depth());
+        }
+
+        TRACE(" edge @%d #%d:%s, incoming depth %zu\n", i, control->id(),
+              control->op()->mnemonic(), incoming_depth);
+      }
+
+      for (int pos = static_cast<int>(copies.size()) - 1; pos >= 0; pos--) {
+        backedges.push_back(NodeVector(tmp_zone));
+        backedges.back().reserve(header_nodes.size());
+
+        NodeVector* previous_map = pos > 0 ? copies[pos - 1] : nullptr;
+
+        for (Node* node : header_nodes) {
+          Node* input = node->InputAt(i);
+          if (previous_map) input = previous_map->at(input->id());
+          backedges.back().push_back(input);
+          TRACE("   node #%d:%s(@%d) = #%d:%s\n", node->id(),
+                node->op()->mnemonic(), i, input->id(),
+                input->op()->mnemonic());
+        }
+      }
+    }
+
+    int backedge_count = static_cast<int>(backedges.size());
+    if (backedge_count == 1) {
+      // Simple case of single backedge, therefore a single entry.
+      int index = 0;
+      for (Node* node : header_nodes) {
         Node* copy = mapping->at(node->id());
-        Node* backedge = node->InputAt(1);
-        if (previous) backedge = previous->at(backedge->id());
-        copy->ReplaceInput(0, backedge);
+        Node* input = backedges[0][index];
+        copy->ReplaceInput(0, input);
+        TRACE(" header #%d:%s(0) => #%d:%s\n", copy->id(),
+              copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
+        index++;
       }
     } else {
-      // Complex case. Multiple backedges. Introduce a merge for incoming edges.
-      tmp_inputs.clear();
-      for (int i = 0; i < backedges; i++) {
-        Node* backedge = loop_header->InputAt(i + 1);
-        if (previous) backedge = previous->at(backedge->id());
-        tmp_inputs.push_back(backedge);
-      }
-      Node* merge =
-          graph->NewNode(common->Merge(backedges), backedges, &tmp_inputs[0]);
-      for (Node* node : loop_tree->HeaderNodes(loop)) {
-        if (!all.IsLive(node)) continue;  // dead phi hanging off loop.
+      // Complex case of multiple backedges from previous copies requires
+      // merging the backedges to create the entry into the loop header.
+      Node* merge = nullptr;
+      int index = 0;
+      for (Node* node : header_nodes) {
+        // Gather edge inputs into {tmp_inputs}.
+        tmp_inputs.clear();
+        for (int edge = 0; edge < backedge_count; edge++) {
+          tmp_inputs.push_back(backedges[edge][index]);
+        }
         Node* copy = mapping->at(node->id());
+        Node* input;
         if (node == loop_header) {
-          // The entry to the loop is the merge.
+          // Create the merge for the entry into the loop header.
+          input = merge = graph->NewNode(common->Merge(backedge_count),
+                                         backedge_count, &tmp_inputs[0]);
           copy->ReplaceInput(0, merge);
         } else {
-          // Merge inputs to the phi at the loop entry.
-          tmp_inputs.clear();
-          for (int i = 0; i < backedges; i++) {
-            Node* backedge = node->InputAt(i + 1);
-            if (previous) backedge = previous->at(backedge->id());
-            tmp_inputs.push_back(backedge);
-          }
+          // Create a phi that merges values at entry into the loop header.
+          DCHECK_NOT_NULL(merge);
+          DCHECK(IrOpcode::IsPhiOpcode(node->opcode()));
           tmp_inputs.push_back(merge);
-          Node* phi =
-              graph->NewNode(common->ResizeMergeOrPhi(node->op(), backedges),
-                             backedges + 1, &tmp_inputs[0]);
+          Node* phi = input = graph->NewNode(
+              common->ResizeMergeOrPhi(node->op(), backedge_count),
+              backedge_count + 1, &tmp_inputs[0]);
           copy->ReplaceInput(0, phi);
         }
+
+        // Print the merge.
+        if (TRACE_COND) {
+          TRACE(" header #%d:%s(0) => #%d:%s(", copy->id(),
+                copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
+          for (size_t i = 0; i < tmp_inputs.size(); i++) {
+            if (i > 0) TRACE(", ");
+            Node* input = tmp_inputs[i];
+            TRACE("#%d:%s", input->id(), input->op()->mnemonic());
+          }
+          TRACE(")\n");
+        }
+
+        index++;
       }
     }
   }
 
   // Kill the outer loops in the original graph.
+  TRACE("Killing outer loop headers...\n");
   for (LoopTree::Loop* outer = osr_loop->parent(); outer;
        outer = outer->parent()) {
-    loop_tree->HeaderNode(outer)->ReplaceUses(dead);
+    Node* loop_header = loop_tree->HeaderNode(outer);
+    loop_header->ReplaceUses(dead);
+    TRACE(" ---- #%d:%s\n", loop_header->id(), loop_header->op()->mnemonic());
   }
 
   // Merge the ends of the graph copies.