loop-analysis.h 8.71 KB
Newer Older
1 2 3 4 5 6 7 8
// 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.

#ifndef V8_COMPILER_LOOP_ANALYSIS_H_
#define V8_COMPILER_LOOP_ANALYSIS_H_

#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 13 14
#include "src/compiler/node-marker.h"
#include "src/compiler/node-origin-table.h"
#include "src/compiler/node-properties.h"
15
#include "src/compiler/node.h"
16
#include "src/zone/zone-containers.h"
17 18 19

namespace v8 {
namespace internal {
20 21 22

class TickCounter;

23 24
namespace compiler {

25 26 27
// TODO(titzer): don't assume entry edges have a particular index.
static const int kAssumedLoopEntryIndex = 0;  // assume loops are entered here.

28 29
class LoopFinderImpl;

30
using NodeRange = base::iterator_range<Node**>;
31 32 33 34 35 36 37 38

// Represents a tree of loops in a graph.
class LoopTree : public ZoneObject {
 public:
  LoopTree(size_t num_nodes, Zone* zone)
      : zone_(zone),
        outer_loops_(zone),
        all_loops_(zone),
39
        node_to_loop_num_(static_cast<int>(num_nodes), -1, zone),
40 41 42 43 44 45 46 47
        loop_nodes_(zone) {}

  // Represents a loop in the tree of loops, including the header nodes,
  // the body, and any nested loops.
  class Loop {
   public:
    Loop* parent() const { return parent_; }
    const ZoneVector<Loop*>& children() const { return children_; }
48 49 50 51 52
    uint32_t HeaderSize() const { return body_start_ - header_start_; }
    uint32_t BodySize() const { return exits_start_ - body_start_; }
    uint32_t ExitsSize() const { return exits_end_ - exits_start_; }
    uint32_t TotalSize() const { return exits_end_ - header_start_; }
    uint32_t depth() const { return depth_; }
53 54 55 56 57 58 59 60 61 62 63

   private:
    friend class LoopTree;
    friend class LoopFinderImpl;

    explicit Loop(Zone* zone)
        : parent_(nullptr),
          depth_(0),
          children_(zone),
          header_start_(-1),
          body_start_(-1),
64 65
          exits_start_(-1),
          exits_end_(-1) {}
66 67 68 69 70
    Loop* parent_;
    int depth_;
    ZoneVector<Loop*> children_;
    int header_start_;
    int body_start_;
71 72
    int exits_start_;
    int exits_end_;
73 74 75 76
  };

  // Return the innermost nested loop, if any, that contains {node}.
  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 80 81 82 83
    return num > 0 ? &all_loops_[num - 1] : nullptr;
  }

  // Check if the {loop} contains the {node}, either directly or by containing
  // a nested loop that contains {node}.
84
  bool Contains(const Loop* loop, Node* node) {
85 86 87 88 89 90 91 92 93
    for (Loop* c = ContainingLoop(node); c != nullptr; c = c->parent_) {
      if (c == loop) return true;
    }
    return false;
  }

  // Return the list of outer loops.
  const ZoneVector<Loop*>& outer_loops() const { return outer_loops_; }

94 95 96 97 98 99 100 101 102 103 104
  // Return a new vector containing the inner loops.
  ZoneVector<const Loop*> inner_loops() const {
    ZoneVector<const Loop*> inner_loops(zone_);
    for (const Loop& loop : all_loops_) {
      if (loop.children().empty()) {
        inner_loops.push_back(&loop);
      }
    }
    return inner_loops;
  }

105
  // Return the unique loop number for a given loop. Loop numbers start at {1}.
106
  int LoopNum(const Loop* loop) const {
107 108 109 110
    return 1 + static_cast<int>(loop - &all_loops_[0]);
  }

  // Return a range which can iterate over the header nodes of {loop}.
111
  NodeRange HeaderNodes(const Loop* loop) {
112 113 114 115
    return NodeRange(&loop_nodes_[0] + loop->header_start_,
                     &loop_nodes_[0] + loop->body_start_);
  }

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 123 124 125
                     &loop_nodes_[0] + loop->exits_start_);
  }

  // Return a range which can iterate over the body nodes of {loop}.
126
  NodeRange ExitNodes(const Loop* loop) {
127 128
    return NodeRange(&loop_nodes_[0] + loop->exits_start_,
                     &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 140 141 142 143 144 145
    // TODO(turbofan): make the loop control node always first?
    for (Node* node : HeaderNodes(loop)) {
      if (node->opcode() == IrOpcode::kLoop) return node;
    }
    UNREACHABLE();
  }

146 147
  Zone* zone() const { return zone_; }

148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
 private:
  friend class LoopFinderImpl;

  Loop* NewLoop() {
    all_loops_.push_back(Loop(zone_));
    Loop* result = &all_loops_.back();
    return result;
  }

  void SetParent(Loop* parent, Loop* child) {
    if (parent != nullptr) {
      parent->children_.push_back(child);
      child->parent_ = parent;
      child->depth_ = parent->depth_ + 1;
    } else {
      outer_loops_.push_back(child);
    }
  }

  Zone* zone_;
  ZoneVector<Loop*> outer_loops_;
  ZoneVector<Loop> all_loops_;
170
  ZoneVector<int> node_to_loop_num_;
171 172 173
  ZoneVector<Node*> loop_nodes_;
};

174
class V8_EXPORT_PRIVATE LoopFinder {
175 176
 public:
  // Build a loop tree for the entire graph.
177 178
  static LoopTree* BuildLoopTree(Graph* graph, TickCounter* tick_counter,
                                 Zone* temp_zone);
179 180

  static bool HasMarkedExits(LoopTree* loop_tree_, const LoopTree::Loop* loop);
181

182
#if V8_ENABLE_WEBASSEMBLY
183 184 185 186 187 188
  // Find all nodes in the loop headed by {loop_header} if it contains no nested
  // loops.
  // Assumption: *if* this loop has no nested loops, all exits from the loop are
  // marked with LoopExit, LoopExitEffect, LoopExitValue, or End nodes.
  // Returns {nullptr} if
  // 1) the loop size (in graph nodes) exceeds {max_size},
189 190
  // 2) {calls_are_large} and a function call is found in the loop, excluding
  //    calls to a set of wasm builtins,
191 192
  // 3) a nested loop is found in the loop.
  static ZoneUnorderedSet<Node*>* FindSmallInnermostLoopFromHeader(
193
      Node* loop_header, Zone* zone, size_t max_size, bool calls_are_large);
194
#endif
195 196
};

197 198 199 200
// Copies a range of nodes any number of times.
class NodeCopier {
 public:
  // {max}: The maximum number of nodes that this copier will track, including
201
  //        the original nodes and all copies.
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221
  // {p}: A vector that holds the original nodes and all copies.
  // {copy_count}: How many times the nodes should be copied.
  NodeCopier(Graph* graph, uint32_t max, NodeVector* p, uint32_t copy_count)
      : node_map_(graph, max), copies_(p), copy_count_(copy_count) {
    DCHECK_GT(copy_count, 0);
  }

  // Returns the mapping of {node} in the {copy_index}'th copy, or {node} itself
  // if it is not present in the mapping. The copies are 0-indexed.
  Node* map(Node* node, uint32_t copy_index);

  // Helper version of {map} for one copy.
  V8_INLINE Node* map(Node* node) { return map(node, 0); }

  // Insert a new mapping from {original} to {new_copies} into the copier.
  void Insert(Node* original, const NodeVector& new_copies);

  // Helper version of {Insert} for one copy.
  void Insert(Node* original, Node* copy);

222 223 224
  template <typename InputIterator>
  void CopyNodes(Graph* graph, Zone* tmp_zone_, Node* dead,
                 base::iterator_range<InputIterator> nodes,
225
                 SourcePositionTable* source_positions,
226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249
                 NodeOriginTable* node_origins) {
    // Copy all the nodes first.
    for (Node* original : nodes) {
      SourcePositionTable::Scope position(
          source_positions, source_positions->GetSourcePosition(original));
      NodeOriginTable::Scope origin_scope(node_origins, "copy nodes", original);
      node_map_.Set(original, copies_->size() + 1);
      copies_->push_back(original);
      for (uint32_t copy_index = 0; copy_index < copy_count_; copy_index++) {
        Node* copy = graph->CloneNode(original);
        copies_->push_back(copy);
      }
    }

    // Fix inputs of the copies.
    for (Node* original : nodes) {
      for (uint32_t copy_index = 0; copy_index < copy_count_; copy_index++) {
        Node* copy = map(original, copy_index);
        for (int i = 0; i < copy->InputCount(); i++) {
          copy->ReplaceInput(i, map(original->InputAt(i), copy_index));
        }
      }
    }
  }
250 251 252 253 254 255 256 257 258 259 260

  bool Marked(Node* node) { return node_map_.Get(node) > 0; }

 private:
  // Maps a node to its index in the {copies_} vector.
  NodeMarker<size_t> node_map_;
  // The vector which contains the mapped nodes.
  NodeVector* copies_;
  // How many copies of the nodes should be generated.
  const uint32_t copy_count_;
};
261

262 263 264 265 266
}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_LOOP_ANALYSIS_H_