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/compiler/bytecode-analysis-liveness.h"
+#include "src/interpreter/bytecode-array-iterator.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)
+                                   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) {}
 
 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_) {
+      Liveness& liveness = liveness_map_.InitializeLiveness(
+          current_offset, bytecode_array()->register_count() + 1, zone());

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

nit - add a comment that the + 1 is for the accumulator. Another option - add
methods to liveness_map explicitly for the accumulator, since it should always
be being accessed independently of the registers - that way there wouldn't be an
implicit assumption that register_count() is the accumulator - WDYT?

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

Added a comment. As with another reply, adding methods for this sort of thing
would require a wrapper around the liveness BitVector, so I don't know if it's
worth doing.

+
+      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 pass update the loop end and

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

nit - "pass update the loop end" seems like it's missing a word.

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

Done -- it was too many words rather than too few.

+  // 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
+        // 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.
+        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.

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

I am wondering whether it really matters that the header is not fully correct.

The header definitely contains all the contributions of this loop, and you have
already added the contributions of the outer loops. As a result, I cannot see
what new information can be added by another pass.

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

The problem is, I need to add this new liveness information to the loop header
before I can read it for the JumpLoop, and I can't simply force-update the
target of the JumpLoop because that's not necessarily the Jump that jumps out of
the loop (plus, there can be breaks inside the loop too) -- and we can't simply
force-add these additional liveness bits to the JumpLoop, because they may have
been killed as part of the loop header. Consider

1: do {
2:   x1 = r1;
2:   x2 = r2;
3:   do {
4:     r1 = y;
5:     break;
6:   } while(true);
7: } while(true);

r1 should be live at 2, 4 and 5, but should be dead at 1, 3 and 6, while r2 is
live throughout. On the second pass, we first need to add the liveness in 7
(propagated from 2) to 5,4 and 3, before we can process the liveness of 6 (which
makes r2 live but keeps r1 dead).

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

You are right. It is unfortunate that it has to be so complicated, but it seems
unavoidable.

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

Since this was quite a tricky example, I've added a test case for it. It's not
impossible that there's still a way to optimise things here.

[Jarin, 2016/11/28 19:47:20]

Thanks!

+            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.
+    }
+  }
+
+  DCHECK(LivenessIsValid());
 }
 
 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 {
+  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);
+}
+
+#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++;
+      }
+      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