[interpreter] Use VisitForTest for loop conditions

src/compiler/bytecode-loop-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-loop-analysis.h"
 
 #include "src/compiler/bytecode-branch-analysis.h"
 #include "src/interpreter/bytecode-array-iterator.h"
 #include "src/objects-inl.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 BytecodeLoopAnalysis::BytecodeLoopAnalysis(
     Handle<BytecodeArray> bytecode_array,
     const BytecodeBranchAnalysis* branch_analysis, Zone* zone)
     : bytecode_array_(bytecode_array),
       branch_analysis_(branch_analysis),
       zone_(zone),

[Michael Starzinger, 2016/08/18 13:24:28]

nit: Could we add sensible initializations of both fields,
"found_current_backedge_" as well as "current_loop_offset_" here?

[klaasb, 2016/08/18 13:50:11]

Done.

       backedge_to_header_(zone),
       loop_header_to_parent_(zone) {}
 
 void BytecodeLoopAnalysis::Analyze() {
   current_loop_offset_ = -1;
   interpreter::BytecodeArrayIterator iterator(bytecode_array());
   while (!iterator.done()) {
     interpreter::Bytecode bytecode = iterator.current_bytecode();
     int current_offset = iterator.current_offset();
     if (branch_analysis_->backward_branches_target(current_offset)) {
       AddLoopEntry(current_offset);
     } else if (interpreter::Bytecodes::IsJump(bytecode)) {
       AddBranch(current_offset, iterator.GetJumpTargetOffset());
     }
     iterator.Advance();
   }
 }
 
 void BytecodeLoopAnalysis::AddLoopEntry(int entry_offset) {
+  if (found_current_backedge_) {
+    // We assume that all backedges of a loop must occur together and before
+    // another loop entry or an outer loop backedge.

[Jarin, 2016/08/18 12:49:50]

Could you explain how you guard against the assumption being violated? (I have
convinced myself the DCHECK on line 60 somehow does the job, but it would be
good to have a coherent argument here.)

[klaasb, 2016/08/18 13:38:01]

The combination of the DCHECKs on 58, 60 and 63 does it.
When we encounter a backedge, we are either still searching and finding
backedges of the current loop (63), or we need to have found at least one back
edge to the current loop (58) and thus the backedge must target the parent loop
(60), which also guarantees that we found the (first) backedge of the parent.

Assuming there could be a backedge out of order with a backedge to the parent
loop, then 63 would fail, as target_offset > current_loop_offset_.

After setting the current_loop_offset_ at loop entry, we can only encounter a
backedge to the current loop (63) or parent loop (60) and 58 checks that if it
goes to the parent loop, we actually ended the current loop.

Only in the case of a sibling loop do we enter the branch here and then
resetting found_current_backedge to false guarantees failure for invalid
backedges at 58/63. I moved line 48 to the branch to have it at the actually
relevant place.

I've also expanded this comment to summarize the argument above.

+    // Thus here, the current loop actually ended before.
+    current_loop_offset_ = loop_header_to_parent_[current_loop_offset_];
+  }
   loop_header_to_parent_[entry_offset] = current_loop_offset_;
   current_loop_offset_ = entry_offset;
+  found_current_backedge_ = false;
 }
 
 void BytecodeLoopAnalysis::AddBranch(int origin_offset, int target_offset) {
-  // If this is a backedge, record it and update the current loop to the parent.
+  // If this is a backedge, record it.
   if (target_offset < origin_offset) {
     backedge_to_header_[origin_offset] = target_offset;
-    // Check that we are finishing the current loop. This assumes that
-    // there is one backedge for each loop.
-    DCHECK_EQ(target_offset, current_loop_offset_);
-    current_loop_offset_ = loop_header_to_parent_[target_offset];
+    // Check whether this is actually a backedge of the outer loop and we have
+    // already finished the current loop.
+    if (target_offset < current_loop_offset_) {
+      DCHECK(found_current_backedge_);
+      int parent_offset = loop_header_to_parent_[current_loop_offset_];
+      DCHECK_EQ(target_offset, parent_offset);
+      current_loop_offset_ = parent_offset;
+    } else {
+      DCHECK_EQ(target_offset, current_loop_offset_);
+      found_current_backedge_ = true;
+    }
   }
 }
 
 int BytecodeLoopAnalysis::GetLoopOffsetFor(int offset) const {
   auto next_backedge = backedge_to_header_.lower_bound(offset);
   // If there is no next backedge => offset is not in a loop.
   if (next_backedge == backedge_to_header_.end()) {
     return -1;
   }
   // If the header preceeds the offset, it is the backedge of the containing
   // loop.
   if (next_backedge->second <= offset) {
     return next_backedge->second;
   }
   // Otherwise there is a nested loop after this offset. We just return the
   // parent of the next nested loop.
   return loop_header_to_parent_.upper_bound(offset)->second;
 }
 
 int BytecodeLoopAnalysis::GetParentLoopFor(int header_offset) const {
   auto parent = loop_header_to_parent_.find(header_offset);
   DCHECK(parent != loop_header_to_parent_.end());
   return parent->second;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8