[ignition] Rewrite reverse iterator as random iterator

[ignition] Rewrite reverse iterator as random iterator

This allows us to optimise the bytecode liveness analysis to jump
directly to previously seen indices. The analysis is optimised to store
a stack of loop ends (JumpLoop bytecode indices), and iterate through
these indices directly rather than looping through the bytecode array to
find them.

Committed: https://crrev.com/b9d930735ae8268fb95fd3a11681d587eb30e585
Cr-Commit-Position: refs/heads/master@{#41485}

[Leszek Swirski, 2016-11-28 16:45:23]

The CQ bit was checked by leszeks@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-11-28 16:45:29]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Leszek Swirski, 2016-11-28 16:46:39]

leszeks@chromium.org changed reviewers:
+ rmcilroy@chromium.org

[Leszek Swirski, 2016-11-28 16:46:39]

Hi Ross,

As discussed, a random access iterator and the corresponding liveness analysis
improvements. LMKWYT.

[commit-bot: I haz the power, 2016-11-28 17:10:29]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-11-28 17:10:30]

Dry run: This issue passed the CQ dry run.

[rmcilroy, 2016-11-29 12:09:32]

LGTM

https://codereview.chromium.org/2536653003/diff/1/src/interpreter/bytecode-ar...
File src/interpreter/bytecode-array-random-iterator.h (right):

https://codereview.chromium.org/2536653003/diff/1/src/interpreter/bytecode-ar...
src/interpreter/bytecode-array-random-iterator.h:57: bool Valid() const;
nit IsValid

https://codereview.chromium.org/2536653003/diff/1/test/unittests/interpreter/...
File test/unittests/interpreter/bytecode-array-random-iterator-unittest.cc
(right):

https://codereview.chromium.org/2536653003/diff/1/test/unittests/interpreter/...
test/unittests/interpreter/bytecode-array-random-iterator-unittest.cc:287: 
nit - could you add a random access iteration test please

[Leszek Swirski, 2016-11-29 14:57:13]

The CQ bit was checked by leszeks@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-11-29 14:57:20]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Leszek Swirski, 2016-11-29 15:04:53]

Hi Jaro,

Could you take a look at the src/compiler parts of this CL please?

[Leszek Swirski, 2016-11-29 15:05:35]

https://codereview.chromium.org/2536653003/diff/1/src/interpreter/bytecode-ar...
File src/interpreter/bytecode-array-random-iterator.h (right):

https://codereview.chromium.org/2536653003/diff/1/src/interpreter/bytecode-ar...
src/interpreter/bytecode-array-random-iterator.h:57: bool Valid() const;
On 2016/11/29 12:09:32, rmcilroy wrote:
> nit IsValid

Done.

https://codereview.chromium.org/2536653003/diff/1/test/unittests/interpreter/...
File test/unittests/interpreter/bytecode-array-random-iterator-unittest.cc
(right):

https://codereview.chromium.org/2536653003/diff/1/test/unittests/interpreter/...
test/unittests/interpreter/bytecode-array-random-iterator-unittest.cc:287: 
On 2016/11/29 12:09:32, rmcilroy wrote:
> nit - could you add a random access iteration test please

Done. I went a bit mad with tests here, the Ctrl, C and V keys on my keyboard
are worn out now.

[Leszek Swirski, 2016-11-29 15:06:02]

leszeks@chromium.org changed reviewers:
+ jarin@chromium.org

[Leszek Swirski, 2016-11-29 15:06:03]

Hi Jaro,

Could you take a look at the src/compiler parts of this CL please?

[commit-bot: I haz the power, 2016-11-29 15:22:53]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-11-29 15:22:54]

Dry run: This issue passed the CQ dry run.

[Jarin, 2016-11-30 06:05:22]

lgtm. Thanks!

[Leszek Swirski, 2016-12-05 12:13:26]

The CQ bit was checked by leszeks@chromium.org

[Leszek Swirski, 2016-12-05 12:13:26]

The patchset sent to the CQ was uploaded after l-g-t-m from
rmcilroy@chromium.org
Link to the patchset: https://codereview.chromium.org/2536653003/#ps20001
(title: "Rename Valid to IsValid and add so many more tests")

[commit-bot: I haz the power, 2016-12-05 12:13:35]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-12-05 12:39:01]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-12-05 12:39:02]

Failed to apply patch for src/compiler/bytecode-analysis.cc:
While running git apply --index -p1;
  error: patch failed: src/compiler/bytecode-analysis.cc:151
  error: src/compiler/bytecode-analysis.cc: patch does not apply

Patch:       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
e1d425b8d8dfd04e49ed38bbfcbc344bcf897b8f..a68d124ce95108aac4634390f491bd70c29f4628
100644
--- a/src/compiler/bytecode-analysis.cc
+++ b/src/compiler/bytecode-analysis.cc
@@ -5,7 +5,7 @@
 #include "src/compiler/bytecode-analysis.h"
 
 #include "src/interpreter/bytecode-array-iterator.h"
-#include "src/interpreter/bytecode-array-reverse-iterator.h"
+#include "src/interpreter/bytecode-array-random-iterator.h"
 #include "src/objects-inl.h"
 
 namespace v8 {
@@ -20,6 +20,7 @@ BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray>
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),
       liveness_map_(bytecode_array->length(), zone) {}
@@ -151,21 +152,17 @@ void BytecodeAnalysis::Analyze() {
 
   BitVector* next_bytecode_in_liveness = nullptr;
 
-  // 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()) {
+  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) {
       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;
+      // 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();
@@ -211,69 +208,48 @@ void BytecodeAnalysis::Analyze() {
   // 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).
+  //
+  // Equivalently, we can queue up loop ends from back to front, and pass over
+  // the loops in that order, as this preserves both the bottom-to-top and
+  // outer-to-inner requirements.
 
-  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;
+  for (int loop_end_index : loop_end_index_queue_) {
+    iterator.GoToIndex(loop_end_index);
 
     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();
 
-      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);
-        next_bytecode_in_liveness = end_liveness.in;
-
-        // Advance into the loop body.
-        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();
-            }
-          }
+    Liveness& header_liveness = liveness_map_.GetLiveness(header_offset);
+    Liveness& end_liveness = liveness_map_.GetLiveness(end_offset);
 
-          int current_offset = iterator.current_offset();
-          Liveness& liveness = liveness_map_.GetLiveness(current_offset);
+    if (!end_liveness.out->UnionIsChanged(*header_liveness.in)) {
+      // Only update the loop body if the loop end liveness changed.
+      continue;
+    }
+    end_liveness.in->CopyFrom(*end_liveness.out);
+    next_bytecode_in_liveness = end_liveness.in;
 
-          UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness,
-                            iterator, liveness_map_);
-          liveness.in->CopyFrom(*liveness.out);
-          UpdateInLiveness(bytecode, *liveness.in, iterator);
+    // Advance into the loop body.
+    --iterator;
+    for (; iterator.current_offset() > header_offset; --iterator) {
+      Bytecode bytecode = iterator.current_bytecode();
 
-          next_bytecode_in_liveness = liveness.in;
-        }
-        // 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,
-                          next_bytecode_in_liveness, iterator, liveness_map_);
-      }
+      int current_offset = iterator.current_offset();
+      Liveness& liveness = liveness_map_.GetLiveness(current_offset);
+
+      UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness,
+                        iterator, liveness_map_);
+      liveness.in->CopyFrom(*liveness.out);
+      UpdateInLiveness(bytecode, *liveness.in, iterator);
 
-      // Keep the iterator going so that we can find other loops.
+      next_bytecode_in_liveness = liveness.in;
     }
+    // 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.
+    UpdateOutLiveness(iterator.current_bytecode(), *header_liveness.out,
+                      next_bytecode_in_liveness, iterator, liveness_map_);
   }
 
   DCHECK(LivenessIsValid());
@@ -373,7 +349,7 @@ std::ostream&
BytecodeAnalysis::PrintLivenessTo(std::ostream& os) const {
 
 #if DEBUG
 bool BytecodeAnalysis::LivenessIsValid() {
-  BytecodeArrayReverseIterator iterator(bytecode_array(), zone());
+  BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
 
   BitVector previous_liveness(bytecode_array()->register_count() + 1, zone());
 
@@ -383,7 +359,7 @@ bool BytecodeAnalysis::LivenessIsValid() {
   BitVector* next_bytecode_in_liveness = nullptr;
 
   // Ensure that there are no liveness changes if we iterate one more time.
-  for (iterator.Reset(); !iterator.done(); iterator.Advance()) {
+  for (iterator.GoToEnd(); iterator.IsValid(); --iterator) {
     Bytecode bytecode = iterator.current_bytecode();
 
     int current_offset = iterator.current_offset();

[Leszek Swirski, 2016-12-05 12:41:23]

The CQ bit was checked by leszeks@chromium.org

[Leszek Swirski, 2016-12-05 12:41:23]

The patchset sent to the CQ was uploaded after l-g-t-m from jarin@chromium.org,
rmcilroy@chromium.org
Link to the patchset: https://codereview.chromium.org/2536653003/#ps40001
(title: "Rebase")

[commit-bot: I haz the power, 2016-12-05 12:41:35]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-12-05 13:03:07]

CQ is committing da patch.

Bot data: {"patchset_id": 40001, "attempt_start_ts": 1480941683212640,
"parent_rev": "e1d84d259971e31d354d2d51626451f828045c9f", "commit_rev":
"4d90ca37e673b147962c3156e38dab6049f1667d"}

[commit-bot: I haz the power, 2016-12-05 13:03:13]

Committed patchset #3 (id:40001)

[commit-bot: I haz the power, 2016-12-05 13:03:55]

Description was changed from

==========
[ignition] Rewrite reverse iterator as random iterator

This allows us to optimise the bytecode liveness analysis to jump
directly to previously seen indices. The analysis is optimised to store
a stack of loop ends (JumpLoop bytecode indices), and iterate through
these indices directly rather than looping through the bytecode array to
find them.
==========

to

==========
[ignition] Rewrite reverse iterator as random iterator

This allows us to optimise the bytecode liveness analysis to jump
directly to previously seen indices. The analysis is optimised to store
a stack of loop ends (JumpLoop bytecode indices), and iterate through
these indices directly rather than looping through the bytecode array to
find them.

Committed: https://crrev.com/b9d930735ae8268fb95fd3a11681d587eb30e585
Cr-Commit-Position: refs/heads/master@{#41485}
==========

[commit-bot: I haz the power, 2016-12-05 13:03:56]

Patchset 3 (id:??) landed as
https://crrev.com/b9d930735ae8268fb95fd3a11681d587eb30e585
Cr-Commit-Position: refs/heads/master@{#41485}