loop-analysis.cc | Explore in Territory

// Copyright 2014 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/loop-analysis.h"

#include "src/codegen/tick-counter.h"
#include "src/compiler/all-nodes.h"
#include "src/compiler/common-operator.h"
#include "src/compiler/graph.h"
#include "src/compiler/node-marker.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/node.h"
#include "src/zone/zone.h"

namespace v8 {
namespace internal {

class TickCounter;

namespace compiler {

#define OFFSET(x) …
#define BIT(x) …
#define INDEX(x) …

// Temporary information for each node during marking.
struct NodeInfo { … };


// Temporary loop info needed during traversal and building the loop tree.
struct TempLoopInfo { … };

// Encapsulation of the loop finding algorithm.
// -----------------------------------------------------------------------------
// Conceptually, the contents of a loop are those nodes that are "between" the
// loop header and the backedges of the loop. Graphs in the soup of nodes can
// form improper cycles, so standard loop finding algorithms that work on CFGs
// aren't sufficient. However, in valid TurboFan graphs, all cycles involve
// either a {Loop} node or a phi. The {Loop} node itself and its accompanying
// phis are treated together as a set referred to here as the loop header.
// This loop finding algorithm works by traversing the graph in two directions,
// first from nodes to their inputs, starting at {end}, then in the reverse
// direction, from nodes to their uses, starting at loop headers.
// 1 bit per loop per node per direction are required during the marking phase.
// To handle nested loops correctly, the algorithm must filter some reachability
// marks on edges into/out-of the loop header nodes.
// Note: this algorithm assumes there are no unreachable loop header nodes
// (including loop phis).
class LoopFinderImpl { … };

LoopTree* LoopFinder::BuildLoopTree(Graph* graph, TickCounter* tick_counter,
                                    Zone* zone) { … }

#if V8_ENABLE_WEBASSEMBLY
// static
ZoneUnorderedSet<Node*>* LoopFinder::FindSmallInnermostLoopFromHeader(
    Node* loop_header, AllNodes& all_nodes, Zone* zone, size_t max_size,
    Purpose purpose) { … }
#endif  // V8_ENABLE_WEBASSEMBLY

bool LoopFinder::HasMarkedExits(LoopTree* loop_tree,
                                const LoopTree::Loop* loop) { … }

Node* LoopTree::HeaderNode(const Loop* loop) { … }

Node* NodeCopier::map(Node* node, uint32_t copy_index) { … }

void NodeCopier::Insert(Node* original, const NodeVector& new_copies) { … }

void NodeCopier::Insert(Node* original, Node* copy) { … }

}  // namespace compiler
}  // namespace internal
}  // namespace v8
chromium/v8/src/compiler/loop-analysis.cc
