[ignition] Replace branch+loop analysis with a single pass

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),
-      current_loop_offset_(-1),
-      found_current_backedge_(false),
-      backedge_to_header_(zone),
-      loop_header_to_parent_(zone) {}
-
-void BytecodeLoopAnalysis::Analyze() {
-  current_loop_offset_ = -1;
-  found_current_backedge_ = false;
-  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.
-    // This is guaranteed by the invariants from AddBranch, such that every
-    // backedge must either go to the current loop or be the first of the
-    // backedges to the parent loop.
-    // Thus here, the current loop actually ended before and we have a loop
-    // with the same parent.
-    current_loop_offset_ = loop_header_to_parent_[current_loop_offset_];
-    found_current_backedge_ = false;
-  }
-  loop_header_to_parent_[entry_offset] = current_loop_offset_;
-  current_loop_offset_ = entry_offset;
-}
-
-void BytecodeLoopAnalysis::AddBranch(int origin_offset, int target_offset) {
-  // If this is a backedge, record it.
-  if (target_offset < origin_offset) {
-    backedge_to_header_[origin_offset] = 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