1// Copyright 2014 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_COMPILER_LOOP_ANALYSIS_H_
6#define V8_COMPILER_LOOP_ANALYSIS_H_
7
8#include "src/base/iterator.h"
9#include "src/common/globals.h"
10#include "src/compiler/compiler-source-position-table.h"
11#include "src/compiler/graph.h"
12#include "src/compiler/node-marker.h"
13#include "src/compiler/node-origin-table.h"
14#include "src/compiler/node-properties.h"
15#include "src/compiler/node.h"
16#include "src/zone/zone-containers.h"
17
18namespace v8 {
19namespace internal {
20
21class TickCounter;
22
23namespace compiler {
24
25// TODO(titzer): don't assume entry edges have a particular index.
26static const int kAssumedLoopEntryIndex = 0;  // assume loops are entered here.
27
28class LoopFinderImpl;
29
30using NodeRange = base::iterator_range<Node**>;
31
32// Represents a tree of loops in a graph.
33class LoopTree : public ZoneObject {
34 public:
35  LoopTree(size_t num_nodes, Zone* zone)
36      : zone_(zone),
37        outer_loops_(zone),
38        all_loops_(zone),
39        node_to_loop_num_(static_cast<int>(num_nodes), -1, zone),
40        loop_nodes_(zone) {}
41
42  // Represents a loop in the tree of loops, including the header nodes,
43  // the body, and any nested loops.
44  class Loop {
45   public:
46    Loop* parent() const { return parent_; }
47    const ZoneVector<Loop*>& children() const { return children_; }
48    uint32_t HeaderSize() const { return body_start_ - header_start_; }
49    uint32_t BodySize() const { return exits_start_ - body_start_; }
50    uint32_t ExitsSize() const { return exits_end_ - exits_start_; }
51    uint32_t TotalSize() const { return exits_end_ - header_start_; }
52    uint32_t depth() const { return depth_; }
53
54   private:
55    friend class LoopTree;
56    friend class LoopFinderImpl;
57
58    explicit Loop(Zone* zone)
59        : parent_(nullptr),
60          depth_(0),
61          children_(zone),
62          header_start_(-1),
63          body_start_(-1),
64          exits_start_(-1),
65          exits_end_(-1) {}
66    Loop* parent_;
67    int depth_;
68    ZoneVector<Loop*> children_;
69    int header_start_;
70    int body_start_;
71    int exits_start_;
72    int exits_end_;
73  };
74
75  // Return the innermost nested loop, if any, that contains {node}.
76  Loop* ContainingLoop(Node* node) {
77    if (node->id() >= node_to_loop_num_.size()) return nullptr;
78    int num = node_to_loop_num_[node->id()];
79    return num > 0 ? &all_loops_[num - 1] : nullptr;
80  }
81
82  // Check if the {loop} contains the {node}, either directly or by containing
83  // a nested loop that contains {node}.
84  bool Contains(const Loop* loop, Node* node) {
85    for (Loop* c = ContainingLoop(node); c != nullptr; c = c->parent_) {
86      if (c == loop) return true;
87    }
88    return false;
89  }
90
91  // Return the list of outer loops.
92  const ZoneVector<Loop*>& outer_loops() const { return outer_loops_; }
93
94  // Return a new vector containing the inner loops.
95  ZoneVector<const Loop*> inner_loops() const {
96    ZoneVector<const Loop*> inner_loops(zone_);
97    for (const Loop& loop : all_loops_) {
98      if (loop.children().empty()) {
99        inner_loops.push_back(&loop);
100      }
101    }
102    return inner_loops;
103  }
104
105  // Return the unique loop number for a given loop. Loop numbers start at {1}.
106  int LoopNum(const Loop* loop) const {
107    return 1 + static_cast<int>(loop - &all_loops_[0]);
108  }
109
110  // Return a range which can iterate over the header nodes of {loop}.
111  NodeRange HeaderNodes(const Loop* loop) {
112    return NodeRange(&loop_nodes_[0] + loop->header_start_,
113                     &loop_nodes_[0] + loop->body_start_);
114  }
115
116  // Return the header control node for a loop.
117  Node* HeaderNode(const Loop* loop);
118
119  // Return a range which can iterate over the body nodes of {loop}.
120  NodeRange BodyNodes(const Loop* loop) {
121    return NodeRange(&loop_nodes_[0] + loop->body_start_,
122                     &loop_nodes_[0] + loop->exits_start_);
123  }
124
125  // Return a range which can iterate over the body nodes of {loop}.
126  NodeRange ExitNodes(const Loop* loop) {
127    return NodeRange(&loop_nodes_[0] + loop->exits_start_,
128                     &loop_nodes_[0] + loop->exits_end_);
129  }
130
131  // Return a range which can iterate over the nodes of {loop}.
132  NodeRange LoopNodes(const Loop* loop) {
133    return NodeRange(&loop_nodes_[0] + loop->header_start_,
134                     &loop_nodes_[0] + loop->exits_end_);
135  }
136
137  // Return the node that represents the control, i.e. the loop node itself.
138  Node* GetLoopControl(const Loop* loop) {
139    // TODO(turbofan): make the loop control node always first?
140    for (Node* node : HeaderNodes(loop)) {
141      if (node->opcode() == IrOpcode::kLoop) return node;
142    }
143    UNREACHABLE();
144  }
145
146  Zone* zone() const { return zone_; }
147
148 private:
149  friend class LoopFinderImpl;
150
151  Loop* NewLoop() {
152    all_loops_.push_back(Loop(zone_));
153    Loop* result = &all_loops_.back();
154    return result;
155  }
156
157  void SetParent(Loop* parent, Loop* child) {
158    if (parent != nullptr) {
159      parent->children_.push_back(child);
160      child->parent_ = parent;
161      child->depth_ = parent->depth_ + 1;
162    } else {
163      outer_loops_.push_back(child);
164    }
165  }
166
167  Zone* zone_;
168  ZoneVector<Loop*> outer_loops_;
169  ZoneVector<Loop> all_loops_;
170  ZoneVector<int> node_to_loop_num_;
171  ZoneVector<Node*> loop_nodes_;
172};
173
174class V8_EXPORT_PRIVATE LoopFinder {
175 public:
176  // Build a loop tree for the entire graph.
177  static LoopTree* BuildLoopTree(Graph* graph, TickCounter* tick_counter,
178                                 Zone* temp_zone);
179
180  static bool HasMarkedExits(LoopTree* loop_tree_, const LoopTree::Loop* loop);
181
182#if V8_ENABLE_WEBASSEMBLY
183  // Find all nodes in the loop headed by {loop_header} if it contains no nested
184  // loops.
185  // Assumption: *if* this loop has no nested loops, all exits from the loop are
186  // marked with LoopExit, LoopExitEffect, LoopExitValue, or End nodes.
187  // Returns {nullptr} if
188  // 1) the loop size (in graph nodes) exceeds {max_size},
189  // 2) {calls_are_large} and a function call is found in the loop, excluding
190  //    calls to a set of wasm builtins,
191  // 3) a nested loop is found in the loop.
192  static ZoneUnorderedSet<Node*>* FindSmallInnermostLoopFromHeader(
193      Node* loop_header, Zone* zone, size_t max_size, bool calls_are_large);
194#endif
195};
196
197// Copies a range of nodes any number of times.
198class NodeCopier {
199 public:
200  // {max}: The maximum number of nodes that this copier will track, including
201  //        the original nodes and all copies.
202  // {p}: A vector that holds the original nodes and all copies.
203  // {copy_count}: How many times the nodes should be copied.
204  NodeCopier(Graph* graph, uint32_t max, NodeVector* p, uint32_t copy_count)
205      : node_map_(graph, max), copies_(p), copy_count_(copy_count) {
206    DCHECK_GT(copy_count, 0);
207  }
208
209  // Returns the mapping of {node} in the {copy_index}'th copy, or {node} itself
210  // if it is not present in the mapping. The copies are 0-indexed.
211  Node* map(Node* node, uint32_t copy_index);
212
213  // Helper version of {map} for one copy.
214  V8_INLINE Node* map(Node* node) { return map(node, 0); }
215
216  // Insert a new mapping from {original} to {new_copies} into the copier.
217  void Insert(Node* original, const NodeVector& new_copies);
218
219  // Helper version of {Insert} for one copy.
220  void Insert(Node* original, Node* copy);
221
222  template <typename InputIterator>
223  void CopyNodes(Graph* graph, Zone* tmp_zone_, Node* dead,
224                 base::iterator_range<InputIterator> nodes,
225                 SourcePositionTable* source_positions,
226                 NodeOriginTable* node_origins) {
227    // Copy all the nodes first.
228    for (Node* original : nodes) {
229      SourcePositionTable::Scope position(
230          source_positions, source_positions->GetSourcePosition(original));
231      NodeOriginTable::Scope origin_scope(node_origins, "copy nodes", original);
232      node_map_.Set(original, copies_->size() + 1);
233      copies_->push_back(original);
234      for (uint32_t copy_index = 0; copy_index < copy_count_; copy_index++) {
235        Node* copy = graph->CloneNode(original);
236        copies_->push_back(copy);
237      }
238    }
239
240    // Fix inputs of the copies.
241    for (Node* original : nodes) {
242      for (uint32_t copy_index = 0; copy_index < copy_count_; copy_index++) {
243        Node* copy = map(original, copy_index);
244        for (int i = 0; i < copy->InputCount(); i++) {
245          copy->ReplaceInput(i, map(original->InputAt(i), copy_index));
246        }
247      }
248    }
249  }
250
251  bool Marked(Node* node) { return node_map_.Get(node) > 0; }
252
253 private:
254  // Maps a node to its index in the {copies_} vector.
255  NodeMarker<size_t> node_map_;
256  // The vector which contains the mapped nodes.
257  NodeVector* copies_;
258  // How many copies of the nodes should be generated.
259  const uint32_t copy_count_;
260};
261
262}  // namespace compiler
263}  // namespace internal
264}  // namespace v8
265
266#endif  // V8_COMPILER_LOOP_ANALYSIS_H_
267