[turbofan] Add and use bytecode loop assigment analysis

src/compiler/bytecode-graph-builder.cc

Index: src/compiler/bytecode-graph-builder.cc
diff --git a/src/compiler/bytecode-graph-builder.cc b/src/compiler/bytecode-graph-builder.cc
index 1ca0b7ec8645223c974af7462d7f29158f0b1462..13e0be2ae3f173615403fdfb4060087150a4cf03 100644
--- a/src/compiler/bytecode-graph-builder.cc
+++ b/src/compiler/bytecode-graph-builder.cc
@@ -68,17 +68,16 @@ class BytecodeGraphBuilder::Environment : public ZoneObject {
   Node* Context() const { return context_; }
   void SetContext(Node* new_context) { context_ = new_context; }
 
-  Environment* CopyForConditional();
-  Environment* CopyForLoop();
-  Environment* CopyForOsrEntry();
+  Environment* Copy();
   void Merge(Environment* other);
-  void PrepareForOsrEntry();
 
-  void PrepareForLoopExit(Node* loop);
+  void PrepareForOsrEntry();
+  void PrepareForLoop(const BytecodeLoopAssignments& assignments);
+  void PrepareForLoopExit(Node* loop,
+                          const BytecodeLoopAssignments& assignments);
 
  private:
   explicit Environment(const Environment* copy);
-  void PrepareForLoop();
 
   bool StateValuesRequireUpdate(Node** state_values, Node** values, int count);
   void UpdateStateValues(Node** state_values, Node** values, int count);
@@ -250,20 +249,7 @@ void BytecodeGraphBuilder::Environment::RecordAfterState(
   }
 }
 
-
-BytecodeGraphBuilder::Environment*
-BytecodeGraphBuilder::Environment::CopyForLoop() {
-  PrepareForLoop();
-  return new (zone()) Environment(this);
-}
-
-BytecodeGraphBuilder::Environment*
-BytecodeGraphBuilder::Environment::CopyForOsrEntry() {
-  return new (zone()) Environment(this);
-}
-
-BytecodeGraphBuilder::Environment*
-BytecodeGraphBuilder::Environment::CopyForConditional() {
+BytecodeGraphBuilder::Environment* BytecodeGraphBuilder::Environment::Copy() {
   return new (zone()) Environment(this);
 }
 
@@ -290,8 +276,8 @@ void BytecodeGraphBuilder::Environment::Merge(
   }
 }
 
-
-void BytecodeGraphBuilder::Environment::PrepareForLoop() {
+void BytecodeGraphBuilder::Environment::PrepareForLoop(
+    const BytecodeLoopAssignments& assignments) {
   // Create a control node for the loop header.
   Node* control = builder()->NewLoop();
 
@@ -299,11 +285,23 @@ void BytecodeGraphBuilder::Environment::PrepareForLoop() {
   Node* effect = builder()->NewEffectPhi(1, GetEffectDependency(), control);
   UpdateEffectDependency(effect);
 
-  // Assume everything in the loop is updated.
+  // Create Phis for any updated values
   context_ = builder()->NewPhi(1, context_, control);
-  int size = static_cast<int>(values()->size());
-  for (int i = 0; i < size; i++) {
-    values()->at(i) = builder()->NewPhi(1, values()->at(i), control);
+  for (int i = 0; i < parameter_count(); i++) {
+    if (assignments.ContainsParameter(i)) {
+      values_[i] = builder()->NewPhi(1, values_[i], control);
+    }
+  }
+  for (int i = 0; i < register_count(); i++) {
+    if (assignments.ContainsLocal(i)) {
+      int index = register_base() + i;
+      values_[index] = builder()->NewPhi(1, values_[index], control);
+    }
+  }
+
+  if (assignments.ContainsAccumulator()) {
+    values_[accumulator_base()] =
+        builder()->NewPhi(1, values_[accumulator_base()], control);
   }
 
   // Connect to the loop end.
@@ -368,7 +366,8 @@ bool BytecodeGraphBuilder::Environment::StateValuesRequireUpdate(
   return false;
 }
 
-void BytecodeGraphBuilder::Environment::PrepareForLoopExit(Node* loop) {
+void BytecodeGraphBuilder::Environment::PrepareForLoopExit(
+    Node* loop, const BytecodeLoopAssignments& assignments) {
   DCHECK_EQ(loop->opcode(), IrOpcode::kLoop);
 
   Node* control = GetControlDependency();
@@ -382,15 +381,30 @@ void BytecodeGraphBuilder::Environment::PrepareForLoopExit(Node* loop) {
                                          GetEffectDependency(), loop_exit);
   UpdateEffectDependency(effect_rename);
 
-  // TODO(jarin) We should also rename context here. However, uncoditional
+  // TODO(jarin) We should also rename context here. However, unconditional
   // renaming confuses global object and native context specialization.
   // We should only rename if the context is assigned in the loop.
 
-  // Rename the environmnent values.
-  for (size_t i = 0; i < values_.size(); i++) {
-    Node* rename =
-        graph()->NewNode(common()->LoopExitValue(), values_[i], loop_exit);
-    values_[i] = rename;
+  // Rename the environment values.

[rmcilroy, 2016/12/14 10:27:55]

nit - ...values, if they were assigned in the loop.

[Leszek Swirski, 2016/12/14 14:42:19]

Done.

+  for (int i = 0; i < parameter_count(); i++) {
+    if (assignments.ContainsParameter(i)) {
+      Node* rename =
+          graph()->NewNode(common()->LoopExitValue(), values_[i], loop_exit);
+      values_[i] = rename;
+    }
+  }
+  for (int i = 0; i < register_count(); i++) {
+    if (assignments.ContainsLocal(i)) {
+      Node* rename = graph()->NewNode(common()->LoopExitValue(),
+                                      values_[register_base() + i], loop_exit);
+      values_[register_base() + i] = rename;
+    }
+  }
+
+  if (assignments.ContainsAccumulator()) {
+    Node* rename = graph()->NewNode(common()->LoopExitValue(),
+                                    values_[accumulator_base()], loop_exit);
+    values_[accumulator_base()] = rename;
   }
 }
 
@@ -605,7 +619,7 @@ void BytecodeGraphBuilder::PrepareFrameState(Node* node,
 void BytecodeGraphBuilder::VisitBytecodes(bool stack_check) {
   BytecodeAnalysis bytecode_analysis(bytecode_array(), local_zone(),
                                      FLAG_analyze_environment_liveness);
-  bytecode_analysis.Analyze();
+  bytecode_analysis.Analyze(osr_ast_id_);
   set_bytecode_analysis(&bytecode_analysis);
 
   interpreter::BytecodeArrayIterator iterator(bytecode_array());
@@ -628,7 +642,6 @@ void BytecodeGraphBuilder::VisitBytecodes(bool stack_check) {
     SwitchToMergeEnvironment(current_offset);
     if (environment() != nullptr) {
       BuildLoopHeaderEnvironment(current_offset);
-      BuildOSRLoopEntryPoint(current_offset);
 
       // Skip the first stack check if stack_check is false
       if (!stack_check &&
@@ -855,7 +868,7 @@ BytecodeGraphBuilder::Environment* BytecodeGraphBuilder::CheckContextExtensions(
                 extension_slot, jsgraph()->TheHoleConstant());
 
     NewBranch(check_no_extension);
-    Environment* true_environment = environment()->CopyForConditional();
+    Environment* true_environment = environment()->Copy();
 
     {
       NewIfFalse();
@@ -1901,9 +1914,17 @@ void BytecodeGraphBuilder::SwitchToMergeEnvironment(int current_offset) {
 
 void BytecodeGraphBuilder::BuildLoopHeaderEnvironment(int current_offset) {
   if (bytecode_analysis()->IsLoopHeader(current_offset)) {
-    // Add loop header and store a copy so we can connect merged back
-    // edge inputs to the loop header.
-    merge_environments_[current_offset] = environment()->CopyForLoop();
+    const LoopInfo& loop_info =
+        bytecode_analysis()->GetLoopInfoFor(current_offset);
+
+    // Add loop header.
+    environment()->PrepareForLoop(loop_info.assignments());
+
+    BuildOSRLoopEntryPoint(current_offset);
+
+    // Store a copy of the environment so we can connect merged back edge inputs
+    // to the loop header.
+    merge_environments_[current_offset] = environment()->Copy();
   }
 }
 
@@ -1929,13 +1950,14 @@ void BytecodeGraphBuilder::MergeControlToLeaveFunction(Node* exit) {
 }
 
 void BytecodeGraphBuilder::BuildOSRLoopEntryPoint(int current_offset) {
+  DCHECK(bytecode_analysis()->IsLoopHeader(current_offset));
+
   if (!osr_ast_id_.IsNone() && osr_loop_offset_ == current_offset) {

[Michael Starzinger, 2016/12/12 13:16:09]

This essentially duplicates the translation of the "osr_ast_id" into a
bytecode-offset within the analysis and here. Since we need to have it available
inside the analysis and pass the "osr_ast_id" value already, would it be
possible to just expose a {BytecodeAnalysis::IsOSREntryPoint(int)} predicate?
That way the translation is fully done inside the analysis and doesn't need to
be duplicated. We can then remove the {osr_loop_offset} field. WDYT?

[Leszek Swirski, 2016/12/13 13:52:34]

I can do this, but it's not quite the code duplication that you're implying as
one is calculating the loop end offset, and the other is calculating the loop
header offset. Do you mind if I punt this to another CL, just to avoid
additional complication in this one?

[Michael Starzinger, 2016/12/13 14:11:39]

Acknowledged. Works for me.

     // For OSR add a special {OsrLoopEntry} node into the current loop header.
     // It will be turned into a usable entry by the OSR deconstruction.
-    Environment* loop_env = merge_environments_[current_offset];
-    Environment* osr_env = loop_env->CopyForOsrEntry();
+    Environment* osr_env = environment()->Copy();
     osr_env->PrepareForOsrEntry();
-    loop_env->Merge(osr_env);
+    environment()->Merge(osr_env);
   }
 }
 
@@ -1966,8 +1988,10 @@ void BytecodeGraphBuilder::BuildLoopExitsUntilLoop(int loop_offset) {
   int current_loop = bytecode_analysis()->GetLoopOffsetFor(origin_offset);
   while (loop_offset < current_loop) {
     Node* loop_node = merge_environments_[current_loop]->GetControlDependency();
-    environment()->PrepareForLoopExit(loop_node);
-    current_loop = bytecode_analysis()->GetParentLoopFor(current_loop);
+    const LoopInfo& loop_info =
+        bytecode_analysis()->GetLoopInfoFor(current_loop);
+    environment()->PrepareForLoopExit(loop_node, loop_info.assignments());
+    current_loop = loop_info.parent_offset();
   }
 }
 
@@ -1981,7 +2005,7 @@ void BytecodeGraphBuilder::BuildJump() {
 
 void BytecodeGraphBuilder::BuildJumpIf(Node* condition) {
   NewBranch(condition);
-  Environment* if_false_environment = environment()->CopyForConditional();
+  Environment* if_false_environment = environment()->Copy();
   NewIfTrue();
   MergeIntoSuccessorEnvironment(bytecode_iterator().GetJumpTargetOffset());
   set_environment(if_false_environment);
@@ -1990,7 +2014,7 @@ void BytecodeGraphBuilder::BuildJumpIf(Node* condition) {
 
 void BytecodeGraphBuilder::BuildJumpIfNot(Node* condition) {
   NewBranch(condition);
-  Environment* if_true_environment = environment()->CopyForConditional();
+  Environment* if_true_environment = environment()->Copy();
   NewIfFalse();
   MergeIntoSuccessorEnvironment(bytecode_iterator().GetJumpTargetOffset());
   set_environment(if_true_environment);
@@ -2128,7 +2152,7 @@ Node* BytecodeGraphBuilder::MakeNode(const Operator* op, int value_input_count,
       int handler_offset = exception_handlers_.top().handler_offset_;
       int context_index = exception_handlers_.top().context_register_;
       interpreter::Register context_register(context_index);
-      Environment* success_env = environment()->CopyForConditional();
+      Environment* success_env = environment()->Copy();
       const Operator* op = common()->IfException();
       Node* effect = environment()->GetEffectDependency();
       Node* on_exception = graph()->NewNode(op, effect, result);