[turbofan] Generate loop exits in the bytecode graph builder.

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/compiler/bytecode-branch-analysis.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/operator-properties.h"
 #include "src/interpreter/bytecodes.h"
@@ skipping 44 matching lines @@
   }
 
   Node* Context() const { return context_; }
   void SetContext(Node* new_context) { context_ = new_context; }
 
   Environment* CopyForConditional() const;
   Environment* CopyForLoop();
   void Merge(Environment* other);
   void PrepareForOsr();
 
+  void PrepareForLoopExit(Node* loop);
+
  private:
   explicit Environment(const Environment* copy);
   void PrepareForLoop();
   bool StateValuesAreUpToDate(Node** state_values, int offset, int count,
                               int output_poke_start, int output_poke_end);
   bool StateValuesRequireUpdate(Node** state_values, int offset, int count);
   void UpdateStateValues(Node** state_values, int offset, int count);
 
   int RegisterToValuesIndex(interpreter::Register the_register) const;
 
@@ skipping 315 matching lines @@
   DCHECK_LE(static_cast<size_t>(offset + count), values()->size());
   Node** env_values = (count == 0) ? nullptr : &values()->at(offset);
   for (int i = 0; i < count; i++) {
     if ((*state_values)->InputAt(i) != env_values[i]) {
       return true;
     }
   }
   return false;
 }
 
+void BytecodeGraphBuilder::Environment::PrepareForLoopExit(Node* loop) {
+  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);
+
+  // Rename the current context.
+  context_ = graph()->NewNode(common()->LoopExitValue(), context_, loop_exit);
+
+  // 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;
+  }
+}
 
 void BytecodeGraphBuilder::Environment::UpdateStateValues(Node** state_values,
                                                           int offset,
                                                           int count) {
   if (StateValuesRequireUpdate(state_values, offset, count)) {
     const Operator* op = common()->StateValues(count);
     (*state_values) = graph()->NewNode(op, count, &values()->at(offset));
   }
 }
 
@@ skipping 145 matching lines @@
   int const input_count = static_cast<int>(exit_controls_.size());
   Node** const inputs = &exit_controls_.front();
   Node* end = graph()->NewNode(common()->End(input_count), input_count, inputs);
   graph()->SetEnd(end);
 
   return true;
 }
 
 void BytecodeGraphBuilder::VisitBytecodes() {
   BytecodeBranchAnalysis analysis(bytecode_array(), local_zone());
+  BytecodeLoopAnalysis loop_analysis(bytecode_array(), &analysis, local_zone());
   analysis.Analyze();
+  loop_analysis.Analyze();
   set_branch_analysis(&analysis);
+  set_loop_analysis(&loop_analysis);
   interpreter::BytecodeArrayIterator iterator(bytecode_array());
   set_bytecode_iterator(&iterator);
   while (!iterator.done()) {
     int current_offset = iterator.current_offset();
     EnterAndExitExceptionHandlers(current_offset);
     SwitchToMergeEnvironment(current_offset);
     if (environment() != nullptr) {
       BuildLoopHeaderEnvironment(current_offset);
 
       switch (iterator.current_bytecode()) {
@@ skipping 529 matching lines @@
 }
 
 void BytecodeGraphBuilder::BuildThrow() {
   FrameStateBeforeAndAfter states(this);
   Node* value = environment()->LookupAccumulator();
   Node* call = NewNode(javascript()->CallRuntime(Runtime::kThrow), value);
   environment()->BindAccumulator(call, &states);
 }
 
 void BytecodeGraphBuilder::VisitThrow() {
+  BuildLoopExitsForFunctionExit();
   BuildThrow();
   Node* call = environment()->LookupAccumulator();
   Node* control = NewNode(common()->Throw(), call);
   MergeControlToLeaveFunction(control);
 }
 
 void BytecodeGraphBuilder::VisitReThrow() {
+  BuildLoopExitsForFunctionExit();
   Node* value = environment()->LookupAccumulator();
   Node* call = NewNode(javascript()->CallRuntime(Runtime::kReThrow), value);
   Node* control = NewNode(common()->Throw(), call);
   MergeControlToLeaveFunction(control);
 }
 
 void BytecodeGraphBuilder::BuildBinaryOp(const Operator* js_op) {
   FrameStateBeforeAndAfter states(this);
   Node* left =
       environment()->LookupRegister(bytecode_iterator().GetRegisterOperand(0));
@@ skipping 292 matching lines @@
 void BytecodeGraphBuilder::VisitOsrPoll() {
   // TODO(4764): This should be moved into the {VisitBytecodes} once we merge
   // the polling with existing bytecode. This will also guarantee that we are
   // not missing the OSR entry point, which we wouldn't catch right now.
   if (osr_ast_id_.ToInt() == bytecode_iterator().current_offset()) {
     environment()->PrepareForOsr();
   }
 }
 
 void BytecodeGraphBuilder::VisitReturn() {
+  BuildLoopExitsForFunctionExit();
   Node* control =
       NewNode(common()->Return(), environment()->LookupAccumulator());
   MergeControlToLeaveFunction(control);
 }
 
 void BytecodeGraphBuilder::VisitDebugger() {
   FrameStateBeforeAndAfter states(this);
   Node* call =
       NewNode(javascript()->CallRuntime(Runtime::kHandleDebuggerStatement));
   environment()->BindAccumulator(call, &states);
@@ skipping 126 matching lines @@
 
 void BytecodeGraphBuilder::BuildLoopHeaderEnvironment(int current_offset) {
   if (branch_analysis()->backward_branches_target(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();
   }
 }
 
 void BytecodeGraphBuilder::MergeIntoSuccessorEnvironment(int target_offset) {
+  BuildLoopExitsForBranch(target_offset);
   if (merge_environments_[target_offset] == 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_environments_[target_offset] = environment();
   } else {
     merge_environments_[target_offset]->Merge(environment());
   }
   set_environment(nullptr);
 }
 
 void BytecodeGraphBuilder::MergeControlToLeaveFunction(Node* exit) {
   exit_controls_.push_back(exit);
   set_environment(nullptr);
 }
 
+void BytecodeGraphBuilder::BuildLoopExitsForBranch(int target_offset) {
+  int origin_offset = bytecode_iterator().current_offset();
+  // Only build loop exits for forward edges.
+  if (target_offset > origin_offset) {
+    BuildLoopExitsUntilLoop(loop_analysis()->GetLoopOffsetFor(target_offset));
+  }
+}
+
+void BytecodeGraphBuilder::BuildLoopExitsUntilLoop(int loop_offset) {
+  int origin_offset = bytecode_iterator().current_offset();
+  int current_loop = loop_analysis()->GetLoopOffsetFor(origin_offset);
+  while (loop_offset < current_loop) {
+    Node* loop_node = merge_environments_[current_loop]->GetControlDependency();
+    environment()->PrepareForLoopExit(loop_node);
+    current_loop = loop_analysis()->GetParentLoopFor(current_loop);
+  }
+}
+
+void BytecodeGraphBuilder::BuildLoopExitsForFunctionExit() {
+  BuildLoopExitsUntilLoop(-1);
+}
+
 void BytecodeGraphBuilder::BuildJump() {
   MergeIntoSuccessorEnvironment(bytecode_iterator().GetJumpTargetOffset());
 }
 
 
 void BytecodeGraphBuilder::BuildConditionalJump(Node* condition) {
   NewBranch(condition);
   Environment* if_false_environment = environment()->CopyForConditional();
   NewIfTrue();
   MergeIntoSuccessorEnvironment(bytecode_iterator().GetJumpTargetOffset());
@@ skipping 214 matching lines @@
     // Phi does not exist yet, introduce one.
     value = NewPhi(inputs, value, control);
     value->ReplaceInput(inputs - 1, other);
   }
   return value;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8