[turbofan] Add and use bytecode loop assigment analysis

src/compiler/bytecode-analysis.cc

Index: src/compiler/bytecode-analysis.cc
diff --git a/src/compiler/bytecode-analysis.cc b/src/compiler/bytecode-analysis.cc
index 539f760c6cdb1fdcc6485a38cebc09daab56bf4f..1770d4ebeea7da5b3279690c0f3bbe33a926ee39 100644
--- a/src/compiler/bytecode-analysis.cc
+++ b/src/compiler/bytecode-analysis.cc
@@ -14,6 +14,66 @@ namespace compiler {
 
 using namespace interpreter;
 
+BytecodeLoopAssignments::BytecodeLoopAssignments(int parameter_count,
+                                                 int register_count, Zone* zone)
+    : parameter_count_(parameter_count),
+      bit_vector_(new (zone)
+                      BitVector(parameter_count + register_count, zone)) {}
+
+void BytecodeLoopAssignments::Add(interpreter::Register r) {
+  if (r.is_parameter()) {
+    bit_vector_->Add(r.ToParameterIndex(parameter_count_));
+  } else {
+    bit_vector_->Add(parameter_count_ + r.index());
+  }
+}
+
+void BytecodeLoopAssignments::AddPair(interpreter::Register r) {
+  if (r.is_parameter()) {
+    DCHECK(interpreter::Register(r.index() + 1).is_parameter());
+    bit_vector_->Add(r.ToParameterIndex(parameter_count_));
+    bit_vector_->Add(r.ToParameterIndex(parameter_count_) + 1);
+  } else {
+    DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
+    bit_vector_->Add(parameter_count_ + r.index());
+    bit_vector_->Add(parameter_count_ + r.index() + 1);
+  }
+}
+
+void BytecodeLoopAssignments::AddTriple(interpreter::Register r) {
+  if (r.is_parameter()) {
+    DCHECK(interpreter::Register(r.index() + 1).is_parameter());
+    DCHECK(interpreter::Register(r.index() + 2).is_parameter());
+    bit_vector_->Add(r.ToParameterIndex(parameter_count_));
+    bit_vector_->Add(r.ToParameterIndex(parameter_count_) + 1);
+    bit_vector_->Add(r.ToParameterIndex(parameter_count_) + 2);
+  } else {
+    DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
+    DCHECK(!interpreter::Register(r.index() + 2).is_parameter());
+    bit_vector_->Add(parameter_count_ + r.index());
+    bit_vector_->Add(parameter_count_ + r.index() + 1);
+    bit_vector_->Add(parameter_count_ + r.index() + 2);
+  }
+}
+
+void BytecodeLoopAssignments::AddAll() { bit_vector_->AddAll(); }
+
+void BytecodeLoopAssignments::Union(const BytecodeLoopAssignments& other) {
+  bit_vector_->Union(*other.bit_vector_);
+}
+
+bool BytecodeLoopAssignments::ContainsParameter(int index) const {
+  DCHECK_GE(index, 0);
+  DCHECK_LT(index, parameter_count_);
+  return bit_vector_->Contains(index);
+}
+
+bool BytecodeLoopAssignments::ContainsLocal(int index) const {
+  DCHECK_GE(index, 0);
+  DCHECK_LT(index, bit_vector_->length() - parameter_count_);
+  return bit_vector_->Contains(parameter_count_ + index);
+}
+
 BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array,
                                    Zone* zone, bool do_liveness_analysis)
     : bytecode_array_(bytecode_array),
@@ -22,7 +82,7 @@ BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array,
       loop_stack_(zone),
       loop_end_index_queue_(zone),
       end_to_header_(zone),
-      header_to_parent_(zone),
+      header_to_info_(zone),
       liveness_map_(bytecode_array->length(), zone) {}
 
 namespace {
@@ -145,13 +205,43 @@ void UpdateOutLiveness(Bytecode bytecode, BytecodeLivenessState& out_liveness,
   }
 }
 
+void UpdateAssignments(Bytecode bytecode, BytecodeLoopAssignments& assignments,
+                       const BytecodeArrayAccessor& accessor) {
+  int num_operands = Bytecodes::NumberOfOperands(bytecode);
+  const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode);
+
+  for (int i = 0; i < num_operands; ++i) {
+    switch (operand_types[i]) {
+      case OperandType::kRegOut: {
+        assignments.Add(accessor.GetRegisterOperand(i));
+        break;
+      }
+      case OperandType::kRegOutPair: {
+        assignments.AddPair(accessor.GetRegisterOperand(i));
+        break;
+      }
+      case OperandType::kRegOutTriple: {
+        assignments.AddTriple(accessor.GetRegisterOperand(i));
+        break;
+      }
+      default:
+        DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i]));
+        break;
+    }
+  }
+}
+
 }  // namespace
 
-void BytecodeAnalysis::Analyze() {
-  loop_stack_.push(-1);
+void BytecodeAnalysis::Analyze(BailoutId osr_bailout_id) {
+  loop_stack_.push({-1, nullptr});
 
   BytecodeLivenessState* next_bytecode_in_liveness = nullptr;
 
+  bool is_osr_loop = false;
+  int osr_loop_end_offset =
+      osr_bailout_id.IsNone() ? -1 : osr_bailout_id.ToInt();
+
   BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
   for (iterator.GoToEnd(); iterator.IsValid(); --iterator) {
     Bytecode bytecode = iterator.current_bytecode();
@@ -163,12 +253,34 @@ void BytecodeAnalysis::Analyze() {
       int loop_end = current_offset + iterator.current_bytecode_size();
       PushLoop(iterator.GetJumpTargetOffset(), loop_end);
 
+      is_osr_loop = (current_offset == osr_loop_end_offset);
+      if (is_osr_loop) {
+        loop_stack_.top().loop_info->assignments().AddAll();
+      }
+
       // Save the index so that we can do another pass later.
       if (do_liveness_analysis_) {
         loop_end_index_queue_.push_back(iterator.current_index());
       }
-    } else if (current_offset == loop_stack_.top()) {
-      loop_stack_.pop();
+    } else {
+      if (loop_stack_.size() > 1 && !is_osr_loop) {
+        // TODO(leszeks): Ideally, we'd only set values that were assigned in
+        // the loop *and* are live when the loop exits. However, this requires
+        // tracking the out-liveness of *all* loop exits, which is not
+        // information we currently have.
+        UpdateAssignments(bytecode, loop_stack_.top().loop_info->assignments(),
+                          iterator);
+      }
+
+      if (current_offset == loop_stack_.top().header_offset) {
+        LoopStackEntry entry = loop_stack_.top();
+        loop_stack_.pop();
+        if (loop_stack_.size() > 1) {
+          // Propagate inner loop assignments to outer loop.
+          loop_stack_.top().loop_info->assignments().Union(
+              entry.loop_info->assignments());
+        }
+      }
     }
 
     if (do_liveness_analysis_) {
@@ -185,7 +297,7 @@ void BytecodeAnalysis::Analyze() {
   }
 
   DCHECK_EQ(loop_stack_.size(), 1u);
-  DCHECK_EQ(loop_stack_.top(), -1);
+  DCHECK_EQ(loop_stack_.top().header_offset, -1);
 
   if (!do_liveness_analysis_) return;
 
@@ -259,18 +371,24 @@ void BytecodeAnalysis::Analyze() {
 
 void BytecodeAnalysis::PushLoop(int loop_header, int loop_end) {
   DCHECK(loop_header < loop_end);
-  DCHECK(loop_stack_.top() < loop_header);
+  DCHECK(loop_stack_.top().header_offset < loop_header);
   DCHECK(end_to_header_.find(loop_end) == end_to_header_.end());
-  DCHECK(header_to_parent_.find(loop_header) == header_to_parent_.end());
+  DCHECK(header_to_info_.find(loop_header) == header_to_info_.end());
+
+  int parent_offset = loop_stack_.top().header_offset;
+
+  end_to_header_.insert({loop_end, loop_header});
+  auto it = header_to_info_.insert(
+      {loop_header, LoopInfo(parent_offset, bytecode_array_->parameter_count(),
+                             bytecode_array_->register_count(), zone_)});
+  // Get the loop info pointer from the output of insert.
+  LoopInfo* loop_info = &it.first->second;
 
-  end_to_header_.insert(ZoneMap<int, int>::value_type(loop_end, loop_header));
-  header_to_parent_.insert(
-      ZoneMap<int, int>::value_type(loop_header, loop_stack_.top()));
-  loop_stack_.push(loop_header);
+  loop_stack_.push({loop_header, loop_info});
 }
 
 bool BytecodeAnalysis::IsLoopHeader(int offset) const {
-  return header_to_parent_.find(offset) != header_to_parent_.end();
+  return header_to_info_.find(offset) != header_to_info_.end();
 }
 
 int BytecodeAnalysis::GetLoopOffsetFor(int offset) const {
@@ -300,16 +418,16 @@ int BytecodeAnalysis::GetLoopOffsetFor(int offset) const {
   //   | `- end
   //   |
   //   `- end
-  // We just return the parent of the next loop header (might be -1).
-  DCHECK(header_to_parent_.upper_bound(offset) != header_to_parent_.end());
+  // We just return the parent of the next loop (might be -1).
+  DCHECK(header_to_info_.upper_bound(offset) != header_to_info_.end());
 
-  return header_to_parent_.upper_bound(offset)->second;
+  return header_to_info_.upper_bound(offset)->second.parent_offset();
 }
 
-int BytecodeAnalysis::GetParentLoopFor(int header_offset) const {
+const LoopInfo& BytecodeAnalysis::GetLoopInfoFor(int header_offset) const {
   DCHECK(IsLoopHeader(header_offset));
 
-  return header_to_parent_.find(header_offset)->second;
+  return header_to_info_.find(header_offset)->second;
 }
 
 const BytecodeLivenessState* BytecodeAnalysis::GetInLivenessFor(