chromium/v8/src/compiler/turboshaft/analyzer-iterator.h

// Copyright 2023 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_TURBOSHAFT_ANALYZER_ITERATOR_H_
#define V8_COMPILER_TURBOSHAFT_ANALYZER_ITERATOR_H_

#include "src/base/logging.h"
#include "src/compiler/turboshaft/graph.h"
#include "src/compiler/turboshaft/index.h"
#include "src/compiler/turboshaft/loop-finder.h"
#include "src/compiler/turboshaft/operations.h"
#include "src/compiler/turboshaft/sidetable.h"

namespace v8::internal::compiler::turboshaft {

// AnalyzerIterator provides methods to iterate forward a Graph in a way that is
// efficient for the SnapshotTable: blocks that are close in the graphs will be
// visited somewhat consecutively (which means that the SnapshotTable shouldn't
// have to travel far).
//
// To understand why this is important, consider the following graph:
//
//                          B1 <------
//                          |\       |
//                          | \      |
//                          |  v     |
//                          |   B27---
//                          v
//                          B2 <------
//                          |\       |
//                          | \      |
//                          |  v     |
//                          |   B26---
//                          v
//                          B3 <------
//                          |\       |
//                          | \      |
//                          |  v     |
//                          |   B25---
//                          v
//                         ...
//
// If we iterate its blocks in increasing ID order, then we'll visit B1, B2,
// B3... and only afterwards will we visit the Backedges. If said backedges can
// update the loop headers snapshots, then when visiting B25, we'll decide to
// revisit starting from B3, and will revisit everything after, then same thing
// for B26 after which we'll start over from B2 (and thus even revisit B3 and
// B25), etc, leading to a quadratic (in the number of blocks) analysis.
//
// Instead, the visitation order offered by AnalyzerIterator is a BFS in the
// dominator tree (ie, after visiting a node, AnalyzerIterator visit the nodes
// it dominates), with an subtlety for loops: when a node dominates multiple
// nodes, successors that are in the same loop as the current node are visited
// before nodes that are in outer loops.
// In the example above, the visitation order would thus be B1, B27, B2, B26,
// B3, B25.
//
// The MarkLoopForRevisit method can be used when visiting a backedge to
// instruct AnalyzerIterator that the loop to which this backedge belongs should
// be revisited. All of the blocks of this loop will then be revisited.
//
// Implementation details for revisitation of loops:
//
// In order to avoid visiting loop exits (= blocks whose dominator is in a loop
// but which aren't themselves in the loop) multiple times, the stack of Blocks
// to visit contains pairs of "block, generation". Additionally, we have a
// global {current_generation_} counter, which is incremented when we revisit a
// loop. When visiting a block, we record in {visited_} that it has been visited
// at {current_generation_}. When we pop a block from the stack and its
// "generation" field is less than what is recorded in {visited_}, then we skip
// it. On the other hand, if its "generation" field is greater than the one
// recorded in {visited_}, it means that we've revisited a loop since the last
// time we visited this block, so we should revisit it as well.

class V8_EXPORT_PRIVATE AnalyzerIterator { … };

}  // namespace v8::internal::compiler::turboshaft

#endif  // V8_COMPILER_TURBOSHAFT_ANALYZER_ITERATOR_H_