[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 383 matching lines @@
   int output_poke_end = output_poke_start + output_poke_count;
   return StateValuesAreUpToDate(&parameters_state_values_, 0, parameter_count(),
                                 output_poke_start, output_poke_end) &&
          StateValuesAreUpToDate(&registers_state_values_, register_base(),
                                 register_count(), output_poke_start,
                                 output_poke_end) &&
          StateValuesAreUpToDate(&accumulator_state_values_, accumulator_base(),
                                 1, output_poke_start, output_poke_end);
 }
 
+void BytecodeGraphBuilder::Environment::PrepareForLoopExit(Node* loop) {

[Michael Starzinger, 2016/07/29 08:54:46]

nit: Can we move this up a few functions close to "PerpareForLoop" and
"PrepareForOsr"?

[Jarin, 2016/07/29 11:36:46]

Done.

+  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 environmnent values.

[Michael Starzinger, 2016/07/29 08:58:21]

Is it OK not to handle "context_" here?

[Jarin, 2016/07/29 11:36:46]

Not ok, great catch! (Well, not ok if we want to account for all loop exiting
values, which was my goal.)

+  for (size_t i = 0; i < values()->size(); i++) {
+    Node* rename =
+        graph()->NewNode(common()->LoopExitValue(), (*values())[i], loop_exit);

[Michael Starzinger, 2016/07/29 08:54:46]

nit: Just "values_[i]".

[Jarin, 2016/07/29 11:36:46]

Done.

+    (*values())[i] = rename;

[Michael Starzinger, 2016/07/29 08:54:45]

nit: Just "values_[i]".

[Jarin, 2016/07/29 11:36:46]

Done.

+  }
+
+  // Rename the effect.

[Michael Starzinger, 2016/07/29 08:54:46]

nit: Can we handle the effect before the values, just to keep it in sync with
other methods?

[Jarin, 2016/07/29 11:36:46]

Done.

+  Node* effect_rename = graph()->NewNode(common()->LoopExitEffect(),
+                                         GetEffectDependency(), loop_exit);
+  UpdateEffectDependency(effect_rename);
+}
+
 BytecodeGraphBuilder::BytecodeGraphBuilder(Zone* local_zone,
                                            CompilationInfo* info,
                                            JSGraph* jsgraph)
     : local_zone_(local_zone),
       jsgraph_(jsgraph),
       bytecode_array_(handle(info->shared_info()->bytecode_array())),
       exception_handler_table_(
           handle(HandlerTable::cast(bytecode_array()->handler_table()))),
       feedback_vector_(handle(info->closure()->feedback_vector())),
       frame_state_function_info_(common()->CreateFrameStateFunctionInfo(
@@ skipping 86 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 522 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 296 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 125 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 218 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