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

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 ea5d71a7da1c0cefdcb2d4c5ad4296353d82901b..43c2718d17ece04b797c2435f87bf4353c773ed0 100644
--- a/src/compiler/bytecode-analysis.cc
+++ b/src/compiler/bytecode-analysis.cc
@@ -4,6 +4,7 @@
 
 #include "src/compiler/bytecode-analysis.h"
 
+#include "src/interpreter/bytecode-array-iterator.h"
 #include "src/interpreter/bytecode-array-reverse-iterator.h"
 #include "src/objects-inl.h"
 
@@ -11,30 +12,278 @@ namespace v8 {
 namespace internal {
 namespace compiler {
 
+using namespace interpreter;
+
 BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array,
-                                   Zone* zone)
+                                   Zone* zone, bool do_liveness_analysis)
     : bytecode_array_(bytecode_array),
+      do_liveness_analysis_(do_liveness_analysis),
       zone_(zone),
       loop_stack_(zone),
       end_to_header_(zone),
-      header_to_parent_(zone) {}
+      header_to_parent_(zone),
+      liveness_map_(bytecode_array->length(), zone) {}
+
+namespace {
+
+void UpdateInLiveness(Bytecode bytecode, BitVector& in_liveness,
+                      const BytecodeArrayAccessor& accessor) {
+  if (bytecode == Bytecode::kDebugger) {
+    // TODO(leszeks): Do we really need to keep everything alive for a debugger
+    // bytecode? Other ways of breaking the debugger here (such as a debugger
+    // statement in a called function) won't keep locals alive.
+    in_liveness.AddAll();
+    return;
+  }

[rmcilroy, 2016/11/28 15:16:37]

I guess you can drop this now?

[Leszek Swirski, 2016/11/28 16:31:11]

Done.

+
+  int num_operands = Bytecodes::NumberOfOperands(bytecode);
+  const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode);
+  AccumulatorUse accumulator_use = Bytecodes::GetAccumulatorUse(bytecode);
+
+  if (accumulator_use == AccumulatorUse::kWrite) {
+    in_liveness.Remove(in_liveness.length() - 1);
+  }
+  for (int i = 0; i < num_operands; ++i) {
+    switch (operand_types[i]) {
+      case OperandType::kRegOut: {
+        interpreter::Register r = accessor.GetRegisterOperand(i);
+        if (!r.is_parameter()) {
+          in_liveness.Remove(r.index());
+        }
+        break;
+      }
+      case OperandType::kRegOutPair: {
+        interpreter::Register r = accessor.GetRegisterOperand(i);
+        if (!r.is_parameter()) {
+          DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
+          in_liveness.Remove(r.index());
+          in_liveness.Remove(r.index() + 1);
+        }
+        break;
+      }
+      case OperandType::kRegOutTriple: {
+        interpreter::Register r = accessor.GetRegisterOperand(i);
+        if (!r.is_parameter()) {
+          DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
+          DCHECK(!interpreter::Register(r.index() + 2).is_parameter());
+          in_liveness.Remove(r.index());
+          in_liveness.Remove(r.index() + 1);
+          in_liveness.Remove(r.index() + 2);
+        }
+        break;
+      }
+      default:
+        DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i]));
+        break;
+    }
+  }
+
+  if (accumulator_use == AccumulatorUse::kRead) {
+    in_liveness.Add(in_liveness.length() - 1);
+  }
+  for (int i = 0; i < num_operands; ++i) {
+    switch (operand_types[i]) {
+      case OperandType::kReg: {
+        interpreter::Register r = accessor.GetRegisterOperand(i);
+        if (!r.is_parameter()) {
+          in_liveness.Add(r.index());
+        }
+        break;
+      }
+      case OperandType::kRegPair: {
+        interpreter::Register r = accessor.GetRegisterOperand(i);
+        if (!r.is_parameter()) {
+          DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
+          in_liveness.Add(r.index());
+          in_liveness.Add(r.index() + 1);
+        }
+        break;
+      }
+      case OperandType::kRegList: {
+        interpreter::Register r = accessor.GetRegisterOperand(i);
+        i++;
+        if (!r.is_parameter()) {
+          uint32_t reg_count = accessor.GetRegisterCountOperand(i);
+
+          for (uint32_t j = 0; j < reg_count; ++j) {
+            DCHECK(!interpreter::Register(r.index() + j).is_parameter());
+            in_liveness.Add(r.index() + j);
+          }
+        }
+      }
+      default:
+        DCHECK(!Bytecodes::IsRegisterInputOperandType(operand_types[i]));
+        break;
+    }
+  }
+}
+
+void UpdateOutLiveness(Bytecode bytecode, BitVector& out_liveness,
+                       const BytecodeArrayAccessor& accessor,
+                       const BytecodeLivenessMap& liveness_map) {
+  if (bytecode == Bytecode::kDebugger) {
+    // TODO(leszeks): Do we really need to keep everything alive for a debugger
+    // bytecode? Other ways of breaking the debugger here (such as a debugger
+    // statement in a called function) won't keep locals alive.
+    out_liveness.AddAll();
+    return;
+  }

[rmcilroy, 2016/11/28 15:16:37]

ditto

[Leszek Swirski, 2016/11/28 16:31:11]

Done.

+
+  int current_offset = accessor.current_offset();
+  const Handle<BytecodeArray>& bytecode_array = accessor.bytecode_array();
+
+  // Update from jump target (if any). Skip loops, we update these manually in
+  // the liveness iterations.
+  if (Bytecodes::IsForwardJump(bytecode)) {
+    int target_offset = accessor.GetJumpTargetOffset();
+    out_liveness.Union(*liveness_map.GetInLiveness(target_offset));
+  }
+
+  // Update from next bytecode (unless this is an unconditional jump).
+  if (!Bytecodes::IsUnconditionalJump(bytecode)) {
+    int next_offset = current_offset + accessor.current_bytecode_size();
+    if (next_offset < bytecode_array->length()) {
+      out_liveness.Union(*liveness_map.GetInLiveness(next_offset));
+    }
+  }
+
+  // Update from exception handler (if any).
+  if (!interpreter::Bytecodes::IsWithoutExternalSideEffects(bytecode)) {
+    int handler_context;
+    int handler_offset = bytecode_array->LookupRangeInHandlerTable(

[rmcilroy, 2016/11/28 15:16:37]

(side thought) - I wonder if this ends up being expensive to do every time.
Might be worth investigating whether we can cache handler table information or
access it more efficiently in a followup CL? 

[Leszek Swirski, 2016/11/28 16:31:11]

Yes, I've got this in the back of my head as one of the "easy" speedups we could
look at -- I didn't focus on it in this CL because exceptions tend to be slower
anyway. I'll add a TODO.

+        current_offset, &handler_context, nullptr);
+
+    if (handler_offset != -1) {
+      out_liveness.Union(*liveness_map.GetInLiveness(handler_offset));
+      out_liveness.Add(handler_context);
+    }
+  }
+}
+
+}  // namespace
 
 void BytecodeAnalysis::Analyze() {
   loop_stack_.push(-1);
 
-  interpreter::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()) {
+  // The last JumpLoop that we haven't done a guaranteed valid liveness pass
+  // over. See the below wall of text for a more thorough explanation.
+  int last_invalid_jumploop_offset = -1;
+
+  BytecodeArrayReverseIterator iterator(bytecode_array(), zone());
+  for (; !iterator.done(); iterator.Advance()) {
+    Bytecode bytecode = iterator.current_bytecode();
+    int current_offset = iterator.current_offset();
+
+    if (bytecode == Bytecode::kJumpLoop) {
+      PushLoop(iterator.GetJumpTargetOffset(), current_offset);
+
+      // Save the last offset so that we can do another pass later.
+      if (last_invalid_jumploop_offset == -1) {
+        last_invalid_jumploop_offset = current_offset;
+      }
+    } else if (current_offset == loop_stack_.top()) {
       loop_stack_.pop();
     }
-    iterator.Advance();
+
+    if (do_liveness_analysis_) {
+      // The liveness vector had bits for the liveness of the registers, and one
+      // more bit for the liveness of the accumulator.
+      Liveness& liveness = liveness_map_.InitializeLiveness(
+          current_offset, bytecode_array()->register_count() + 1, zone());
+
+      UpdateOutLiveness(bytecode, *liveness.out, iterator, liveness_map_);
+      liveness.in->CopyFrom(*liveness.out);
+      UpdateInLiveness(bytecode, *liveness.in, iterator);
+    }
   }
 
   DCHECK_EQ(loop_stack_.size(), 1u);
   DCHECK_EQ(loop_stack_.top(), -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
+  // JumpLoop liveness being updated, as the only liveness bits than can be
+  // added to the loop body are those of the loop header.
+  //
+  // So, if we know that the liveness of bytecodes after a loop header won't
+  // change (e.g. because there are no loops in them, or we have already ensured
+  // those loops are valid), we can safely update the loop end and pass over the
+  // loop body, and then never have to pass over that loop end again, because we
+  // have shown that its target, the loop header, can't change from the entries
+  // after the loop, and can't change from any loop body pass.
+  //
+  // This means that in a pass, we can iterate backwards over the bytecode
+  // array, process any loops that we encounter, and on subsequent passes we can
+  // skip processing those loops (though we still have to process inner loops).
+
+  while (last_invalid_jumploop_offset != -1) {
+    // TODO(leszeks): We shouldn't need to iterate here, we should just have a
+    // random access iterator.
+    iterator.Reset();
+    while (last_invalid_jumploop_offset < iterator.current_offset()) {
+      iterator.Advance();
+    }
+    last_invalid_jumploop_offset = -1;
+
+    DCHECK_EQ(iterator.current_bytecode(), Bytecode::kJumpLoop);
+
+    for (; !iterator.done(); iterator.Advance()) {
+      Bytecode bytecode = iterator.current_bytecode();
+      if (bytecode != Bytecode::kJumpLoop) {
+        // Skip bytecodes until we hit a jumploop. This check isn't needed for

[rmcilroy, 2016/11/28 15:16:37]

nit - JumpLoop

[Leszek Swirski, 2016/11/28 16:31:11]

Done.

+        // the first loop we see (thanks to saving its offset), but it is for
+        // subsequent ones we want to process on this pass.
+        continue;
+      }
+
+      int header_offset = iterator.GetJumpTargetOffset();
+      int end_offset = iterator.current_offset();
+
+      Liveness& header_liveness = liveness_map_.GetLiveness(header_offset);
+      Liveness& end_liveness = liveness_map_.GetLiveness(end_offset);
+
+      if (end_liveness.out->UnionIsChanged(*header_liveness.in)) {
+        // Only update the loop body if the loop end liveness changed.
+        end_liveness.in->CopyFrom(*end_liveness.out);
+
+        // Go past loop end.

[rmcilroy, 2016/11/28 15:16:37]

nit - comment is slightly confusing. How about "Advance into the loop body"?

[Leszek Swirski, 2016/11/28 16:31:11]

Done.

+        iterator.Advance();
+        for (; iterator.current_offset() > header_offset; iterator.Advance()) {
+          bytecode = iterator.current_bytecode();
+          if (bytecode == Bytecode::kJumpLoop) {
+            // We can't validate this loop at the moment because we can't
+            // guarantee that its header is valid yet. Save it for later.
+            if (last_invalid_jumploop_offset == -1) {
+              last_invalid_jumploop_offset = iterator.current_offset();
+            }
+          }
+
+          int current_offset = iterator.current_offset();
+          Liveness& liveness = liveness_map_.GetLiveness(current_offset);
+
+          UpdateOutLiveness(bytecode, *liveness.out, iterator, liveness_map_);
+          liveness.in->CopyFrom(*liveness.out);
+          UpdateInLiveness(bytecode, *liveness.in, iterator);
+        }
+        // Now we are at the loop header. Since the in-liveness of the header
+        // can't change, we need only to update the out-liveness.
+        bytecode = iterator.current_bytecode();
+        UpdateOutLiveness(bytecode, *header_liveness.out, iterator,
+                          liveness_map_);
+      }
+
+      // Keep the iterator going so that we can find other loops.

[rmcilroy, 2016/11/28 15:16:37]

As mentioned offline, I'm not super keen on the last_invalid_jumploop_offset and
keeping going to find other loops. Once you add a random access iterator (as a
followup CL), it would be good to keep a stack of JumpLoop offsets found in the
first pass, and just do the second pass on each of those loops in backwards
order. 

[Leszek Swirski, 2016/11/28 16:31:11]

Yup, follow-up CL incoming, I just need to make sure that the random access code
doesn't regress anything (it shouldn't, but I still need to check).

+    }
+  }
+
+  DCHECK(LivenessIsValid());
 }
 
 void BytecodeAnalysis::PushLoop(int loop_header, int loop_end) {
@@ -92,6 +341,163 @@ int BytecodeAnalysis::GetParentLoopFor(int header_offset) const {
   return header_to_parent_.find(header_offset)->second;
 }
 
+const BitVector* BytecodeAnalysis::GetInLivenessFor(int offset) const {
+  if (!do_liveness_analysis_) return nullptr;
+
+  return liveness_map_.GetInLiveness(offset);
+}
+
+const BitVector* BytecodeAnalysis::GetOutLivenessFor(int offset) const {
+  if (!do_liveness_analysis_) return nullptr;
+
+  return liveness_map_.GetOutLiveness(offset);
+}
+
+std::ostream& BytecodeAnalysis::PrintLivenessTo(std::ostream& os) const {
+  interpreter::BytecodeArrayIterator iterator(bytecode_array());
+
+  for (; !iterator.done(); iterator.Advance()) {
+    int current_offset = iterator.current_offset();
+
+    const BitVector* in_liveness = GetInLivenessFor(current_offset);
+    const BitVector* out_liveness = GetOutLivenessFor(current_offset);
+
+    for (int i = 0; i < in_liveness->length(); ++i) {
+      os << (in_liveness->Contains(i) ? "L" : ".");
+    }
+    os << " -> ";
+
+    for (int i = 0; i < out_liveness->length(); ++i) {
+      os << (out_liveness->Contains(i) ? "L" : ".");
+    }
+
+    os << " | " << current_offset << ": ";
+    iterator.PrintTo(os) << std::endl;
+  }
+
+  return os;
+}
+
+#if DEBUG
+bool BytecodeAnalysis::LivenessIsValid() {
+  BytecodeArrayReverseIterator iterator(bytecode_array(), zone());
+
+  BitVector previous_liveness(bytecode_array()->register_count() + 1, zone());
+
+  int invalid_offset = -1;
+  int which_invalid = -1;
+
+  // Ensure that there are no liveness changes if we iterate one more time.
+  for (iterator.Reset(); !iterator.done(); iterator.Advance()) {
+    Bytecode bytecode = iterator.current_bytecode();
+
+    int current_offset = iterator.current_offset();
+
+    Liveness& liveness = liveness_map_.GetLiveness(current_offset);
+
+    previous_liveness.CopyFrom(*liveness.out);
+
+    UpdateOutLiveness(bytecode, *liveness.out, iterator, liveness_map_);
+    // UpdateOutLiveness skips kJumpLoop, so we update it manually.
+    if (bytecode == Bytecode::kJumpLoop) {
+      int target_offset = iterator.GetJumpTargetOffset();
+      liveness.out->Union(*liveness_map_.GetInLiveness(target_offset));
+    }
+
+    if (!liveness.out->Equals(previous_liveness)) {
+      // Reset the invalid liveness.
+      liveness.out->CopyFrom(previous_liveness);
+      invalid_offset = current_offset;
+      which_invalid = 1;
+      break;
+    }
+
+    previous_liveness.CopyFrom(*liveness.in);
+
+    liveness.in->CopyFrom(*liveness.out);
+    UpdateInLiveness(bytecode, *liveness.in, iterator);
+
+    if (!liveness.in->Equals(previous_liveness)) {
+      // Reset the invalid liveness.
+      liveness.in->CopyFrom(previous_liveness);
+      invalid_offset = current_offset;
+      which_invalid = 0;
+      break;
+    }
+  }
+
+  if (invalid_offset != -1) {
+    OFStream of(stderr);
+    of << "Invalid liveness:" << std::endl;
+
+    // Dump the bytecode, annotated with the liveness and marking loops.
+
+    int loop_indent = 0;
+
+    BytecodeArrayIterator forward_iterator(bytecode_array());
+    for (; !forward_iterator.done(); forward_iterator.Advance()) {
+      int current_offset = forward_iterator.current_offset();
+      BitVector* in_liveness = liveness_map_.GetInLiveness(current_offset);
+      BitVector* out_liveness = liveness_map_.GetOutLiveness(current_offset);
+
+      for (int i = 0; i < in_liveness->length(); ++i) {
+        of << (in_liveness->Contains(i) ? 'L' : '.');
+      }
+
+      of << " | ";
+
+      for (int i = 0; i < out_liveness->length(); ++i) {
+        of << (out_liveness->Contains(i) ? 'L' : '.');
+      }
+
+      of << " : " << current_offset << " : ";
+
+      // Draw loop back edges by indentin everything between loop headers and
+      // jump loop instructions.
+      if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) {
+        loop_indent--;
+      }
+      for (int i = 0; i < loop_indent; ++i) {
+        of << " | ";
+      }
+      if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) {
+        of << " `-" << current_offset;
+      } else if (IsLoopHeader(current_offset)) {
+        of << " .>" << current_offset;
+        loop_indent++;

[rmcilroy, 2016/11/28 15:16:37]

Could you share code with PrintLivenessTo here?

[Leszek Swirski, 2016/11/28 16:31:11]

I potentially could, but there's some additional machinery here to  highlight
the incorrect liveness vector, and to draw loops, which I'm not super keen on
adding to 'PrintLivenessTo', since I'd have to hide them behind parameters.

I'd be more tempted to merge both this and 'PrintLivenessTo' with
BytecodeArray::Disassemble, and have a single bytecode printing mega-function
that can annotate statements with liveness, draw loops, maybe  draw forward
jumps, and whatever else we dream of. But I'd rather punt that to another CL.

+      }
+      forward_iterator.PrintTo(of) << std::endl;
+
+      if (current_offset == invalid_offset) {
+        // Underline the invalid liveness.
+        if (which_invalid == 0) {
+          for (int i = 0; i < in_liveness->length(); ++i) {
+            of << '^';
+          }
+        } else {
+          for (int i = 0; i < in_liveness->length() + 3; ++i) {
+            of << ' ';
+          }
+          for (int i = 0; i < out_liveness->length(); ++i) {
+            of << '^';
+          }
+        }
+
+        // Make sure to draw the loop indentation marks on this additional line.
+        of << " : " << current_offset << " : ";
+        for (int i = 0; i < loop_indent; ++i) {
+          of << " | ";
+        }
+
+        of << std::endl;
+      }
+    }
+  }
+
+  return invalid_offset == -1;
+}
+#endif
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8