[turbofan] Add and use bytecode loop assigment analysis

src/compiler/bytecode-analysis.cc

 // Copyright 2016 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-analysis.h"
 
 #include "src/interpreter/bytecode-array-iterator.h"
 #include "src/interpreter/bytecode-array-random-iterator.h"
 #include "src/objects-inl.h"
 
 namespace v8 {
 namespace internal {
 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, local_count());
+  return bit_vector_->Contains(parameter_count_ + index);
+}
+
+bool BytecodeLoopAssignments::ContainsAccumulator() const {
+  // TODO(leszeks): This assumes the accumulator is always assigned. This is
+  // probably correct, but that assignment is also probably dead, so we should
+  // check liveness.
+  return true;
+}
+
 BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array,
                                    Zone* zone, bool do_liveness_analysis)
     : bytecode_array_(bytecode_array),
       do_liveness_analysis_(do_liveness_analysis),
       zone_(zone),
       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 {
 
 void UpdateInLiveness(Bytecode bytecode, BytecodeLivenessState& in_liveness,
                       const BytecodeArrayAccessor& accessor) {
   int num_operands = Bytecodes::NumberOfOperands(bytecode);
   const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode);
   AccumulatorUse accumulator_use = Bytecodes::GetAccumulatorUse(bytecode);
 
@@ skipping 102 matching lines @@
     int handler_offset =
         table->LookupRange(current_offset, &handler_context, nullptr);
 
     if (handler_offset != -1) {
       out_liveness.Union(*liveness_map.GetInLiveness(handler_offset));
       out_liveness.MarkRegisterLive(handler_context);
     }
   }
 }
 
+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();
     int current_offset = iterator.current_offset();
 
     if (bytecode == Bytecode::kJumpLoop) {
       // Every byte up to and including the last byte within the backwards jump
       // instruction is considered part of the loop, set loop end accordingly.
       int loop_end = current_offset + iterator.current_bytecode_size();
       PushLoop(iterator.GetJumpTargetOffset(), loop_end);
 
+      // Normally prefixed bytecodes are treated as if the prefix's offset was
+      // the actual bytecode's offset. However, the OSR id is the offset of the
+      // actual JumpLoop bytecode, so we need to find the location of that
+      // bytecode ignoring the prefix.

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

Michi question (not for this CL) - should we use the prefix offset for OSR
bailoutIDs instead? In most other places we treat a prefix + BC as a single
unit, with the bytecode offset being the prefix bytecode's offset. Not sure
whether this would cause compilation for other parts of OSR though.

[Michael Starzinger, 2016/12/15 13:16:57]

Acknowledged. As discussed offline: Doing this before we enter the bytecode
generator would require an additional iteration over the bytecode stream. I
think the cleanest solution (as mentioned in an earlier comment in this CL)
would be to keep passing the {BailoutId} into {BytecodeAnalysis::Analyze} as
done in this CL, but not store it in the {BytecodeGenerator} in any form.
Exposing a predicate {BytecodeAnalysis::IsOSREntryPoint(int)} would completely
encapsulate any calculation involving the OSR BailoutId in this class. I would
very much vote for going for such an interface. Doing that in a separate
follow-up CL is totally fine with me.

+      int jump_loop_offset = current_offset + iterator.current_prefix_offset();
+      is_osr_loop = (jump_loop_offset == osr_loop_end_offset);
+
+#if DEBUG
+      // Check that is_osr_loop is set iff the osr_loop_end_offset is within
+      // this bytecode.
+      if (is_osr_loop) {
+        DCHECK(current_offset <= osr_loop_end_offset &&
+               osr_loop_end_offset < loop_end);
+      } else {
+        DCHECK(current_offset > osr_loop_end_offset ||
+               osr_loop_end_offset >= loop_end);
+      }

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

Could you just pull this out into a separate helper function and DCHECK the
result of that function rather than adding a #if DEBUG block.

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

Done.

+#endif
+
+      if (is_osr_loop) {
+        loop_stack_.top().loop_info->assignments().AddAll();

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

Could you add a comment on why this is necessary

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

Done.

+      }
+
       // 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) {
+      LoopStackEntry& current_loop = loop_stack_.top();
+      LoopInfo* current_loop_info = current_loop.loop_info;
+
+      if (!is_osr_loop) {

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

Do we need this check here? If we AddAll for the OSR loop above then I think it
would still be fine to UpdateAssignements here just to simplify the code.

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

Sure, it's not performance critical I think.

+        // 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, current_loop_info->assignments(), iterator);
+      }
+
+      if (current_offset == current_loop.header_offset) {
+        loop_stack_.pop();
+        if (loop_stack_.size() > 1) {
+          // Propagate inner loop assignments to outer loop.
+          loop_stack_.top().loop_info->assignments().Union(
+              current_loop_info->assignments());
+        }
+      }
     }
 
     if (do_liveness_analysis_) {
       BytecodeLiveness& liveness = liveness_map_.InitializeLiveness(
           current_offset, bytecode_array()->register_count(), zone());
 
       UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness,
                         iterator, liveness_map_);
       liveness.in->CopyFrom(*liveness.out);
       UpdateInLiveness(bytecode, *liveness.in, iterator);
 
       next_bytecode_in_liveness = liveness.in;
     }
   }
 
   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;
 
   // At this point, every bytecode has a valid in and out liveness, except for
   // propagating liveness across back edges (i.e. JumpLoop). Subsequent liveness
   // analysis iterations can only add additional liveness bits that are pulled
   // across these back edges.
   //
   // Furthermore, a loop header's in-liveness can only change based on any
   // bytecodes *after* the loop end --  it cannot change as a result of the
@@ skipping 53 matching lines @@
     // can't change, we need only to update the out-liveness.
     UpdateOutLiveness(iterator.current_bytecode(), *header_liveness.out,
                       next_bytecode_in_liveness, iterator, liveness_map_);
   }
 
   DCHECK(LivenessIsValid());
 }
 
 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());
 
-  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);
+  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;
+
+  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 {
   auto loop_end_to_header = end_to_header_.upper_bound(offset);
   // If there is no next end => offset is not in a loop.
   if (loop_end_to_header == end_to_header_.end()) {
     return -1;
   }
   // If the header preceeds the offset, this is the loop
   //
   //   .> header  <--loop_end_to_header
   //   |
   //   |  <--offset
   //   |
   //   `- end
   if (loop_end_to_header->second <= offset) {
     return loop_end_to_header->second;
   }
   // Otherwise there is a (potentially nested) loop after this offset.
   //
   //    <--offset
   //
   //   .> header
   //   |
   //   | .> header  <--loop_end_to_header
   //   | |
   //   | `- 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(
     int offset) const {
   if (!do_liveness_analysis_) return nullptr;
 
   return liveness_map_.GetInLiveness(offset);
 }
 
 const BytecodeLivenessState* BytecodeAnalysis::GetOutLivenessFor(
@@ skipping 154 matching lines @@
     }
   }
 
   return invalid_offset == -1;
 }
 #endif
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8