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

src/compiler/bytecode-analysis-liveness.h

Index: src/compiler/bytecode-analysis-liveness.h
diff --git a/src/compiler/bytecode-analysis-liveness.h b/src/compiler/bytecode-analysis-liveness.h
new file mode 100644
index 0000000000000000000000000000000000000000..9419b572ec3b79a66016b3f9b5fbc417e3918c57
--- /dev/null
+++ b/src/compiler/bytecode-analysis-liveness.h
@@ -0,0 +1,152 @@
+// 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.
+
+#ifndef V8_COMPILER_BYTECODE_ANALYSIS_LIVENESS_H_
+#define V8_COMPILER_BYTECODE_ANALYSIS_LIVENESS_H_
+
+#include "src/bit-vector.h"
+#include "src/compiler/bytecode-liveness-map.h"
+#include "src/interpreter/bytecode-array-accessor.h"
+#include "src/interpreter/bytecodes.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {

[Jarin, 2016/11/28 08:34:43]

Why does this stuff have to live in a header?

[rmcilroy, 2016/11/28 10:00:30]

+1. Could this not all just live in bytecode analysis.h ?

[Leszek Swirski, 2016/11/28 10:11:01]

I suppose it needn't, I moved it here while it was still full of template magic.
Moving back.

+
+using namespace interpreter;
+
+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.

[Jarin, 2016/11/28 08:34:43]

I am not sure what you are arguing for. We do want to make debugging awesome but
minimize the impact if we are not debugging . Making stuff alive for debugger
statement is ok because debugger is slow anyway (and seeing your locals is
good). Making arbitrary calls slow is not ok.

[Leszek Swirski, 2016/11/28 10:11:01]

I guess what I'm arguing is that this is a leaky abstraction -- there are a
myriad of ways in which you can break in the middle of an optimised function,
and what's happening here is that one of those ways has different behaviour to
others, which is inconsistent and possibly surprising. Indeed, we turn off the
liveness analysis in a couple of debugger tests, but not in others, because it
sometimes breaks them and sometimes doesn't.

That said, I do acknowledge that *sometimes* presenting good debug information
is better than *never*. I'm just wondering if

a) doing so at the cost of inconsistency is the right thing to do, and
b) special casing single statement liveness for a single bytecode is the right
way of doing it, vs. e.g. disabling liveness entirely for functions with
debugger statements, or even not optimising functions with debugger statements
at all.

Let me know what you think.

[Jarin, 2016/11/28 12:05:42]

I talked to Yang and he is happy not to keep variables alive for the debugger
statement.

[Leszek Swirski, 2016/11/28 14:18:51]

Ok, I'll update the relevant tests to disable liveness.

+    in_liveness.AddAll();
+    return;
+  }
+
+  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) {

[Jarin, 2016/11/28 08:34:43]

Aaaaah, no templates, beauuuuuuutiful.

[Leszek Swirski, 2016/11/28 10:11:01]

:(

+    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()) {

[Jarin, 2016/11/28 08:34:43]

Out of curiousity, do we ever have output register pair that stores into
parameters?

If not, then we could perhaps DCHECK here.

I am asking because this assumes that r not being a parameter implies r+1 is
also not a parameter, so it bakes in some assumptions about register numbering.
The DCHECK would not really fix it, but it would make it more obvious what we
expect.

[Leszek Swirski, 2016/11/28 10:11:01]

Good point, I do make the assumption that lists of registers are either entirely
parameters or entirely not. I've added DCHECKs to make sure.

+          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()) {
+          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()) {
+          in_liveness.Add(r.index());
+          in_liveness.Add(r.index() + 1);
+        }
+        break;
+      }
+      case OperandType::kRegList: {
+        interpreter::Register r = accessor.GetRegisterOperand(i);

[rmcilroy, 2016/11/28 10:00:30]

nit - maybe you could add a GetRegisterListOperand which returns a RegisterList.
You could also do this for RegPair/RegTriple and add a Add(RegList) method to
the liveness map which would simplify the code a bit.

[Leszek Swirski, 2016/11/28 11:07:22]

I'm not sure, liveness here is a raw BitVector so for this change I'd have to
wrap it in something first and then wire through the various accessors. Do you
think this is worth it?

Also, I like that the register and register count access is separated out here,
because it makes it obvious why i is incremented -- if we were to make a change
like this, I'd also want to add an operand iterator which keeps this safe.

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

I guess we are fine without it. Please add some comments somewhere though that
the accumulator is stored in the last element of the bitvector
You could keep the Register and Count parameters seperate, but construct a
RegList out of reg and count and use it for a seperate Add(RegList) (and the
pair / triple)?

Also, I agree that it's nice to make it clear why i is incremented, however it's
not super clear given the if (!r.is_parameter()). Maybe just unconditinally do
GetRegisterCountOperand(++i) but only update liveness when it's not a parameter
?

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

Done.
The wrapper class comment still stands here, I'll look into it in a separate CL.
Done.

+        i++;
+        if (!r.is_parameter()) {

[rmcilroy, 2016/11/28 10:00:30]

Same comment as Jaro above regarding parameters. Maybe you could DCHECK that if
one is a parameter then they all are?

[Leszek Swirski, 2016/11/28 11:07:22]

Done.

+          uint32_t reg_count = accessor.GetRegisterCountOperand(i);
+
+          for (uint32_t j = 0; j < reg_count; ++j) {
+            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;
+  }
+
+  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::IsJump(bytecode) || Bytecodes::IsConditionalJump(bytecode)) {

[rmcilroy, 2016/11/28 10:00:30]

Nit - just add IsUnconditionalJump in bytecodes.h

[Leszek Swirski, 2016/11/28 11:07:22]

Done, also gave me the chance to simplify it a bit.

+    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(
+        current_offset, &handler_context, nullptr);
+
+    if (handler_offset != -1) {
+      out_liveness.Union(*liveness_map.GetInLiveness(handler_offset));
+      out_liveness.Add(handler_context);
+    }
+  }
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_COMPILER_BYTECODE_ANALYSIS_LIVENESS_H_