[turbofan] Add and use bytecode loop assigment analysis

src/compiler/bytecode-graph-builder.cc

 // Copyright 2015 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 "src/compiler/bytecode-graph-builder.h"
 
 #include "src/ast/ast.h"
 #include "src/ast/scopes.h"
 #include "src/compilation-info.h"
 #include "src/compiler/compiler-source-position-table.h"
@@ skipping 50 matching lines @@
 
   // Control dependency tracked by this environment.
   Node* GetControlDependency() const { return control_dependency_; }
   void UpdateControlDependency(Node* dependency) {
     control_dependency_ = dependency;
   }
 
   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 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);
   void UpdateStateValuesWithCache(Node** state_values, Node** values,
                                   int count);
 
   int RegisterToValuesIndex(interpreter::Register the_register) const;
 
   Zone* zone() const { return builder_->local_zone(); }
   Graph* graph() const { return builder_->graph(); }
@@ skipping 151 matching lines @@
   }
 }
 
 void BytecodeGraphBuilder::Environment::RecordAfterState(
     Node* node, FrameStateAttachmentMode mode) {
   if (mode == FrameStateAttachmentMode::kAttachFrameState) {
     builder()->PrepareFrameState(node, OutputFrameStateCombine::Ignore());
   }
 }
 
-
-BytecodeGraphBuilder::Environment*
-BytecodeGraphBuilder::Environment::CopyForLoop() {
-  PrepareForLoop();
+BytecodeGraphBuilder::Environment* BytecodeGraphBuilder::Environment::Copy() {
   return new (zone()) Environment(this);
 }
 
-BytecodeGraphBuilder::Environment*
-BytecodeGraphBuilder::Environment::CopyForOsrEntry() {
-  return new (zone()) Environment(this);
-}
-
-BytecodeGraphBuilder::Environment*
-BytecodeGraphBuilder::Environment::CopyForConditional() {
-  return new (zone()) Environment(this);
-}
-
 
 void BytecodeGraphBuilder::Environment::Merge(
     BytecodeGraphBuilder::Environment* other) {
   // Create a merge of the control dependencies of both environments and update
   // the current environment's control dependency accordingly.
   Node* control = builder()->MergeControl(GetControlDependency(),
                                           other->GetControlDependency());
   UpdateControlDependency(control);
 
   // Create a merge of the effect dependencies of both environments and update
   // the current environment's effect dependency accordingly.
   Node* effect = builder()->MergeEffect(GetEffectDependency(),
                                         other->GetEffectDependency(), control);
   UpdateEffectDependency(effect);
 
   // Introduce Phi nodes for values that have differing input at merge points,
   // potentially extending an existing Phi node if possible.
   context_ = builder()->MergeValue(context_, other->context_, control);
   for (size_t i = 0; i < values_.size(); i++) {
     values_[i] = builder()->MergeValue(values_[i], other->values_[i], control);
   }
 }
 
-
-void BytecodeGraphBuilder::Environment::PrepareForLoop() {
+void BytecodeGraphBuilder::Environment::PrepareForLoop(
+    const BytecodeLoopAssignments& assignments) {
   // Create a control node for the loop header.
   Node* control = builder()->NewLoop();
 
   // Create a Phi for external effects.
   Node* effect = builder()->NewEffectPhi(1, GetEffectDependency(), control);
   UpdateEffectDependency(effect);
 
-  // Assume everything in the loop is updated.
+  // Create Phis for any values that may be updated by the end of the loop.
   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.
   Node* terminate = builder()->graph()->NewNode(
       builder()->common()->Terminate(), effect, control);
   builder()->exit_controls_.push_back(terminate);
 }
 
 void BytecodeGraphBuilder::Environment::PrepareForOsrEntry() {
   DCHECK_EQ(IrOpcode::kLoop, GetControlDependency()->opcode());
@@ skipping 44 matching lines @@
   }
   DCHECK_EQ((*state_values)->InputCount(), count);
   for (int i = 0; i < count; i++) {
     if ((*state_values)->InputAt(i) != values[i]) {
       return true;
     }
   }
   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();
 
   // Create the loop exit node.
   Node* loop_exit = graph()->NewNode(common()->LoopExit(), control, loop);
   UpdateControlDependency(loop_exit);
 
   // Rename the effect.
   Node* effect_rename = graph()->NewNode(common()->LoopExitEffect(),
                                          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 if they were assigned in the loop.
+  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;
   }
 }
 
 void BytecodeGraphBuilder::Environment::UpdateStateValues(Node** state_values,
                                                           Node** values,
                                                           int count) {
   if (StateValuesRequireUpdate(state_values, values, count)) {
     const Operator* op = common()->StateValues(count);
     (*state_values) = graph()->NewNode(op, count, values);
   }
@@ skipping 194 matching lines @@
 
     Node* frame_state_after = environment()->Checkpoint(
         bailout_id, combine, has_exception, liveness_after);
     NodeProperties::ReplaceFrameStateInput(node, frame_state_after);
   }
 }
 
 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());
   set_bytecode_iterator(&iterator);
   SourcePositionTableIterator source_position_iterator(
       bytecode_array()->source_position_table());
 
   if (FLAG_trace_environment_liveness) {
     OFStream of(stdout);
 
     bytecode_analysis.PrintLivenessTo(of);
   }
 
   BuildOSRNormalEntryPoint();
 
   for (; !iterator.done(); iterator.Advance()) {
     int current_offset = iterator.current_offset();
     UpdateCurrentSourcePosition(&source_position_iterator, current_offset);
     EnterAndExitExceptionHandlers(current_offset);
     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 &&
           iterator.current_bytecode() == interpreter::Bytecode::kStackCheck) {
         stack_check = true;
         continue;
       }
 
       switch (iterator.current_bytecode()) {
 #define BYTECODE_CASE(name, ...)       \
@@ skipping 206 matching lines @@
   // the same scope as the variable itself has no way of shadowing it.
   for (uint32_t d = 0; d < depth; d++) {
     Node* extension_slot =
         NewNode(javascript()->LoadContext(d, Context::EXTENSION_INDEX, false));
 
     Node* check_no_extension =
         NewNode(javascript()->StrictEqual(CompareOperationHint::kAny),
                 extension_slot, jsgraph()->TheHoleConstant());
 
     NewBranch(check_no_extension);
-    Environment* true_environment = environment()->CopyForConditional();
+    Environment* true_environment = environment()->Copy();
 
     {
       NewIfFalse();
       // If there is an extension, merge into the slow path.
       if (slow_environment == nullptr) {
         slow_environment = environment();
         NewMerge();
       } else {
         slow_environment->Merge(environment());
       }
@@ skipping 1025 matching lines @@
   if (it != merge_environments_.end()) {
     if (environment() != nullptr) {
       it->second->Merge(environment());
     }
     set_environment(it->second);
   }
 }
 
 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();
   }
 }
 
 void BytecodeGraphBuilder::MergeIntoSuccessorEnvironment(int target_offset) {
   BuildLoopExitsForBranch(target_offset);
   Environment*& merge_environment = merge_environments_[target_offset];
   if (merge_environment == nullptr) {
     // Append merge nodes to the environment. We may merge here with another
     // environment. So add a place holder for merge nodes. We may add redundant
     // but will be eliminated in a later pass.
     // TODO(mstarzinger): Be smarter about this!
     NewMerge();
     merge_environment = environment();
   } else {
     merge_environment->Merge(environment());
   }
   set_environment(nullptr);
 }
 
 void BytecodeGraphBuilder::MergeControlToLeaveFunction(Node* exit) {
   exit_controls_.push_back(exit);
   set_environment(nullptr);
 }
 
 void BytecodeGraphBuilder::BuildOSRLoopEntryPoint(int current_offset) {
+  DCHECK(bytecode_analysis()->IsLoopHeader(current_offset));
+
   if (!osr_ast_id_.IsNone() && osr_loop_offset_ == current_offset) {
     // 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);
   }
 }
 
 void BytecodeGraphBuilder::BuildOSRNormalEntryPoint() {
   if (!osr_ast_id_.IsNone()) {
     // For OSR add an {OsrNormalEntry} as the the top-level environment start.
     // It will be replaced with {Dead} by the OSR deconstruction.
     NewNode(common()->OsrNormalEntry());
     // Translate the offset of the jump instruction to the jump target offset of
     // that instruction so that the derived BailoutId points to the loop header.
@@ skipping 10 matching lines @@
     BuildLoopExitsUntilLoop(
         bytecode_analysis()->GetLoopOffsetFor(target_offset));
   }
 }
 
 void BytecodeGraphBuilder::BuildLoopExitsUntilLoop(int loop_offset) {
   int origin_offset = bytecode_iterator().current_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();
   }
 }
 
 void BytecodeGraphBuilder::BuildLoopExitsForFunctionExit() {
   BuildLoopExitsUntilLoop(-1);
 }
 
 void BytecodeGraphBuilder::BuildJump() {
   MergeIntoSuccessorEnvironment(bytecode_iterator().GetJumpTargetOffset());
 }
 
 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);
   NewIfFalse();
 }
 
 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);
   NewIfTrue();
 }
 
 void BytecodeGraphBuilder::BuildJumpIfEqual(Node* comperand) {
   Node* accumulator = environment()->LookupAccumulator();
   Node* condition =
       NewNode(javascript()->StrictEqual(CompareOperationHint::kAny),
@@ skipping 117 matching lines @@
     }
     // Update the current effect dependency for effect-producing nodes.
     if (result->op()->EffectOutputCount() > 0) {
       environment()->UpdateEffectDependency(result);
     }
     // Add implicit exception continuation for throwing nodes.
     if (!result->op()->HasProperty(Operator::kNoThrow) && inside_handler) {
       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);
       Node* context = environment()->LookupRegister(context_register);
       environment()->UpdateControlDependency(on_exception);
       environment()->UpdateEffectDependency(on_exception);
       environment()->BindAccumulator(on_exception);
       environment()->SetContext(context);
       MergeIntoSuccessorEnvironment(handler_offset);
       set_environment(success_env);
@@ skipping 94 matching lines @@
         it->source_position().ScriptOffset(), start_position_.InliningId()));
     it->Advance();
   } else {
     DCHECK_GT(it->code_offset(), offset);
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8