Reland of [ignition/turbo] Perform liveness analysis on the bytecodes

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-reverse-iterator.h"
 #include "src/objects-inl.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
+using namespace interpreter;
+
 BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array,
                                    Zone* zone)
     : bytecode_array_(bytecode_array),
       zone_(zone),
       loop_stack_(zone),
       end_to_header_(zone),
-      header_to_parent_(zone) {}
+      header_to_parent_(zone),
+      liveness_(
+          base::bits::RoundUpToPowerOfTwo32(bytecode_array->length() / 4 + 1),
+          base::KeyEqualityMatcher<int>(), ZoneAllocationPolicy(zone)) {}
+
+namespace {
+
+uint32_t OffsetHash(int offset) { return offset; }
+
+const BitVector* GetInLiveness(
+    int offset, const BytecodeAnalysis::LivenessMap& liveness_map) {
+  return liveness_map.Lookup(offset, OffsetHash(offset))->value.in;
+}
+
+const BitVector* GetOutLiveness(
+    int offset, const BytecodeAnalysis::LivenessMap& liveness_map) {
+  return liveness_map.Lookup(offset, OffsetHash(offset))->value.out;
+}
+
+template <int index, OperandType... operandTypes>
+struct LivenessHelper;
+
+template <int index, OperandType otherOperandType, OperandType... operandTypes>
+struct LivenessHelper<index, otherOperandType, operandTypes...> {
+  static void AddReads(BitVector& liveness,
+                       const BytecodeArrayAccessor& accessor) {
+    LivenessHelper<index + 1, operandTypes...>::AddReads(liveness, accessor);
+  }
+  static void KillWrites(BitVector& liveness,
+                         const BytecodeArrayAccessor& accessor) {
+    LivenessHelper<index + 1, operandTypes...>::KillWrites(liveness, accessor);
+  }
+};
+
+template <int index>
+struct LivenessHelper<index> {
+  static void AddReads(BitVector& liveness,
+                       const BytecodeArrayAccessor& accessor) {}
+  static void KillWrites(BitVector& liveness,
+                         const BytecodeArrayAccessor& accessor) {}
+};
+
+template <int index, OperandType... operandTypes>
+struct LivenessHelper<index, OperandType::kReg, operandTypes...> {
+  static void AddReads(BitVector& liveness,
+                       const BytecodeArrayAccessor& accessor) {
+    interpreter::Register r = accessor.GetRegisterOperand(index);
+    if (!r.is_parameter()) {
+      liveness.Add(r.index());
+    }
+
+    LivenessHelper<index + 1, operandTypes...>::AddReads(liveness, accessor);
+  }
+  static void KillWrites(BitVector& liveness,
+                         const BytecodeArrayAccessor& accessor) {
+    LivenessHelper<index + 1, operandTypes...>::KillWrites(liveness, accessor);
+  }
+};
+
+template <int index, OperandType... operandTypes>
+struct LivenessHelper<index, OperandType::kRegList, OperandType::kRegCount,
+                      operandTypes...> {
+  static void AddReads(BitVector& liveness,
+                       const BytecodeArrayAccessor& accessor) {
+    interpreter::Register r = accessor.GetRegisterOperand(index);
+    if (!r.is_parameter()) {
+      int count = accessor.GetRegisterCountOperand(index + 1);
+      for (int i = 0; i < count; ++i) {
+        liveness.Add(r.index() + i);
+      }
+    }
+
+    LivenessHelper<index + 2, operandTypes...>::AddReads(liveness, accessor);
+  }
+  static void KillWrites(BitVector& liveness,
+                         const BytecodeArrayAccessor& accessor) {
+    LivenessHelper<index + 2, operandTypes...>::KillWrites(liveness, accessor);
+  }
+};
+
+template <int index, OperandType otherOperandType, OperandType... operandTypes>
+struct LivenessHelper<index, OperandType::kRegList, otherOperandType,
+                      operandTypes...> {};
+
+template <int index, OperandType... operandTypes>
+struct LivenessHelper<index, OperandType::kRegPair, operandTypes...> {
+  static void AddReads(BitVector& liveness,
+                       const BytecodeArrayAccessor& accessor) {
+    interpreter::Register r = accessor.GetRegisterOperand(index);
+    if (!r.is_parameter()) {
+      liveness.Add(r.index());
+      liveness.Add(r.index() + 1);
+    }
+
+    LivenessHelper<index + 1, operandTypes...>::AddReads(liveness, accessor);
+  }
+  static void KillWrites(BitVector& liveness,
+                         const BytecodeArrayAccessor& accessor) {
+    LivenessHelper<index + 1, operandTypes...>::KillWrites(liveness, accessor);
+  }
+};
+
+template <int index, OperandType... operandTypes>
+struct LivenessHelper<index, OperandType::kRegOut, operandTypes...> {
+  static void AddReads(BitVector& liveness,
+                       const BytecodeArrayAccessor& accessor) {
+    LivenessHelper<index + 1, operandTypes...>::AddReads(liveness, accessor);
+  }
+  static void KillWrites(BitVector& liveness,
+                         const BytecodeArrayAccessor& accessor) {
+    interpreter::Register r = accessor.GetRegisterOperand(index);
+    if (!r.is_parameter()) {
+      liveness.Remove(r.index());
+    }
+
+    LivenessHelper<index + 1, operandTypes...>::KillWrites(liveness, accessor);
+  }
+};
+
+template <int index, OperandType... operandTypes>
+struct LivenessHelper<index, OperandType::kRegOutPair, operandTypes...> {
+  static void AddReads(BitVector& liveness,
+                       const BytecodeArrayAccessor& accessor) {
+    LivenessHelper<index + 1, operandTypes...>::AddReads(liveness, accessor);
+  }
+  static void KillWrites(BitVector& liveness,
+                         const BytecodeArrayAccessor& accessor) {
+    interpreter::Register r = accessor.GetRegisterOperand(index);
+    if (!r.is_parameter()) {
+      liveness.Remove(r.index());
+      liveness.Remove(r.index() + 1);
+    }
+
+    LivenessHelper<index + 1, operandTypes...>::KillWrites(liveness, accessor);
+  }
+};
+
+template <int index, OperandType... operandTypes>
+struct LivenessHelper<index, OperandType::kRegOutTriple, operandTypes...> {
+  static void AddReads(BitVector& liveness,
+                       const BytecodeArrayAccessor& accessor) {
+    LivenessHelper<index + 1, operandTypes...>::AddReads(liveness, accessor);
+  }
+  static void KillWrites(BitVector& liveness,
+                         const BytecodeArrayAccessor& accessor) {
+    interpreter::Register r = accessor.GetRegisterOperand(index);
+    if (!r.is_parameter()) {
+      liveness.Remove(r.index());
+      liveness.Remove(r.index() + 1);
+      liveness.Remove(r.index() + 2);
+    }
+
+    LivenessHelper<index + 1, operandTypes...>::KillWrites(liveness, accessor);
+  }
+};
+
+template <Bytecode bytecode, AccumulatorUse accumulatorUse,
+          OperandType... operandsTypes>

[Jarin, 2016/11/24 12:47:17]

Oh, my eyes, my eyes!

Does the heavy use of templates help anything? Is it really noticeably slower
using the methods from the Bytecodes class?

[Leszek Swirski, 2016/11/25 17:31:27]

Beauty is in the eye of the beholder ;)

Unfortunately, as much as I love template stuff like this, both you and Ross
(f2f) don't, and I can't justify it in terms of performance because it doesn't
seem to make a difference. Removed.

+void UpdateLiveness(BytecodeAnalysis::Liveness liveness,
+                    const BytecodeArrayAccessor& accessor,
+                    const BytecodeAnalysis::LivenessMap& liveness_map) {
+  int current_offset = accessor.current_offset();
+  const Handle<BytecodeArray>& bytecode_array = accessor.bytecode_array();
+
+  BitVector& in_liveness = *liveness.in;
+  BitVector& out_liveness = *liveness.out;
+
+  if (Bytecodes::IsJump(bytecode)) {
+    int target_offset = accessor.GetJumpTargetOffset();
+    out_liveness.Union(*GetInLiveness(target_offset, liveness_map));
+  }
+
+  if (!Bytecodes::IsJump(bytecode) || Bytecodes::IsConditionalJump(bytecode)) {
+    int next_offset = current_offset + accessor.current_bytecode_size();
+    if (next_offset < bytecode_array->length()) {
+      out_liveness.Union(*GetInLiveness(next_offset, liveness_map));
+    }
+  }
+
+  if (!interpreter::Bytecodes::IsWithoutExternalSideEffects(bytecode)) {
+    int handler_context;
+    int handler_offset = bytecode_array->LookupRangeInHandlerTable(
+        current_offset, &handler_context, nullptr);
+
+    if (handler_offset != -1) {
+      out_liveness.Union(*GetInLiveness(handler_offset, liveness_map));
+      out_liveness.Add(handler_context);
+    }
+  }
+
+  in_liveness.CopyFrom(out_liveness);
+
+  if (accumulatorUse == AccumulatorUse::kWrite) {
+    in_liveness.Remove(in_liveness.length() - 1);
+  }
+  LivenessHelper<0, operandsTypes...>::KillWrites(in_liveness, accessor);
+
+  if (accumulatorUse == AccumulatorUse::kRead) {
+    in_liveness.Add(in_liveness.length() - 1);
+  }
+  LivenessHelper<0, operandsTypes...>::AddReads(in_liveness, accessor);
+}
+}  // namespace
+
+BytecodeAnalysis::Liveness::Liveness(int size, Zone* zone)
+    : in(new (zone) BitVector(size, zone)),
+      out(new (zone) BitVector(size, zone)) {}
 
 void BytecodeAnalysis::Analyze() {
   loop_stack_.push(-1);
 
-  interpreter::BytecodeArrayReverseIterator iterator(bytecode_array(), zone());
+  BytecodeArrayReverseIterator iterator(bytecode_array(), zone());
   while (!iterator.done()) {
-    interpreter::Bytecode bytecode = iterator.current_bytecode();
-    if (bytecode == interpreter::Bytecode::kJumpLoop) {
-      PushLoop(iterator.GetJumpTargetOffset(), iterator.current_offset());
-    } else if (iterator.current_offset() == loop_stack_.top()) {
+    Bytecode bytecode = iterator.current_bytecode();
+    int current_offset = iterator.current_offset();
+
+    if (bytecode == Bytecode::kJumpLoop) {
+      PushLoop(iterator.GetJumpTargetOffset(), current_offset);
+    } else if (current_offset == loop_stack_.top()) {
       loop_stack_.pop();
     }
+
+    liveness_.LookupOrInsert(
+        current_offset, OffsetHash(current_offset),
+        [&]() {
+          return Liveness(bytecode_array()->register_count() + 1, zone());
+        },
+        ZoneAllocationPolicy(zone()));
+
     iterator.Advance();
   }
 
   DCHECK_EQ(loop_stack_.size(), 1u);
   DCHECK_EQ(loop_stack_.top(), -1);
+
+  // Hoist previous_in_liveness out of the loop so that we don't trash the zone
+  // with allocations.
+  BitVector previous_in_liveness(bytecode_array()->register_count() + 1,
+                                 zone());
+
+  bool liveness_changed = true;
+  while (liveness_changed) {
+    liveness_changed = false;
+    iterator.Reset();
+    while (!iterator.done()) {
+      Liveness current_liveness =
+          liveness_
+              .Lookup(iterator.current_offset(),
+                      OffsetHash(iterator.current_offset()))
+              ->value;
+      previous_in_liveness.CopyFrom(*current_liveness.in);
+
+      switch (iterator.current_bytecode()) {
+#define CASE(NAME, ...)                                                        \
+  case Bytecode::k##NAME: {                                                    \
+    UpdateLiveness<Bytecode::k##NAME, __VA_ARGS__>(current_liveness, iterator, \
+                                                   liveness_);                 \
+    break;                                                                     \
+  }
+
+        BYTECODE_LIST(CASE)
+#undef CASE
+      }
+
+      if (!liveness_changed &&
+          !current_liveness.in->Equals(previous_in_liveness)) {
+        liveness_changed = true;
+      }
+
+      iterator.Advance();
+    }
+  }
 }
 
 void BytecodeAnalysis::PushLoop(int loop_header, int loop_end) {
   DCHECK(loop_header < loop_end);
   DCHECK(loop_stack_.top() < loop_header);
   DCHECK(end_to_header_.find(loop_end) == end_to_header_.end());
   DCHECK(header_to_parent_.find(loop_header) == header_to_parent_.end());
 
   end_to_header_.insert(ZoneMap<int, int>::value_type(loop_end, loop_header));
   header_to_parent_.insert(
@@ skipping 37 matching lines @@
 
   return header_to_parent_.upper_bound(offset)->second;
 }
 
 int BytecodeAnalysis::GetParentLoopFor(int header_offset) const {
   DCHECK(IsLoopHeader(header_offset));
 
   return header_to_parent_.find(header_offset)->second;
 }
 
+const BitVector* BytecodeAnalysis::GetInLivenessFor(int offset) const {
+  return GetInLiveness(offset, liveness_);
+}
+
+const BitVector* BytecodeAnalysis::GetOutLivenessFor(int offset) const {
+  return GetOutLiveness(offset, liveness_);
+}
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8