loop-analysis.cc 14.4 KB
Newer Older
1
// Copyright 2014 the V8 project authors. All rights reserved.
2 3 4 5
// 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"
6 7

#include "src/compiler/graph.h"
8
#include "src/compiler/node.h"
9
#include "src/compiler/node-marker.h"
10
#include "src/compiler/node-properties.h"
11 12 13 14 15 16
#include "src/zone.h"

namespace v8 {
namespace internal {
namespace compiler {

17 18 19
#define OFFSET(x) ((x)&0x1f)
#define BIT(x) (1u << OFFSET(x))
#define INDEX(x) ((x) >> 5)
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

// Temporary information for each node during marking.
struct NodeInfo {
  Node* node;
  NodeInfo* next;       // link in chaining loop members
};


// Temporary loop info needed during traversal and building the loop tree.
struct LoopInfo {
  Node* header;
  NodeInfo* header_list;
  NodeInfo* body_list;
  LoopTree::Loop* loop;
};


// 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.
class LoopFinderImpl {
 public:
  LoopFinderImpl(Graph* graph, LoopTree* loop_tree, Zone* zone)
54 55
      : zone_(zone),
        end_(graph->end()),
56 57
        queue_(zone),
        queued_(graph, 2),
58
        info_(graph->NodeCount(), {nullptr, nullptr}, zone),
59
        loops_(zone),
60
        loop_num_(graph->NodeCount(), -1, zone),
61
        loop_tree_(loop_tree),
62 63 64 65
        loops_found_(0),
        width_(0),
        backward_(nullptr),
        forward_(nullptr) {}
66 67 68 69 70 71 72 73 74 75 76

  void Run() {
    PropagateBackward();
    PropagateForward();
    FinishLoopTree();
  }

  void Print() {
    // Print out the results.
    for (NodeInfo& ni : info_) {
      if (ni.node == nullptr) continue;
77 78 79 80 81
      for (int i = 1; i <= loops_found_; i++) {
        int index = ni.node->id() * width_ + INDEX(i);
        bool marked_forward = forward_[index] & BIT(i);
        bool marked_backward = backward_[index] & BIT(i);
        if (marked_forward && marked_backward) {
82
          PrintF("X");
83
        } else if (marked_forward) {
84
          PrintF("/");
85
        } else if (marked_backward) {
86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
          PrintF("\\");
        } else {
          PrintF(" ");
        }
      }
      PrintF(" #%d:%s\n", ni.node->id(), ni.node->op()->mnemonic());
    }

    int i = 0;
    for (LoopInfo& li : loops_) {
      PrintF("Loop %d headed at #%d\n", i, li.header->id());
      i++;
    }

    for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
      PrintLoop(loop);
    }
  }

 private:
106
  Zone* zone_;
107 108 109 110 111
  Node* end_;
  NodeDeque queue_;
  NodeMarker<bool> queued_;
  ZoneVector<NodeInfo> info_;
  ZoneVector<LoopInfo> loops_;
112
  ZoneVector<int> loop_num_;
113
  LoopTree* loop_tree_;
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
  int loops_found_;
  int width_;
  uint32_t* backward_;
  uint32_t* forward_;

  int num_nodes() {
    return static_cast<int>(loop_tree_->node_to_loop_num_.size());
  }

  // Tb = Tb | (Fb - loop_filter)
  bool PropagateBackwardMarks(Node* from, Node* to, int loop_filter) {
    if (from == to) return false;
    uint32_t* fp = &backward_[from->id() * width_];
    uint32_t* tp = &backward_[to->id() * width_];
    bool change = false;
    for (int i = 0; i < width_; i++) {
      uint32_t mask = i == INDEX(loop_filter) ? ~BIT(loop_filter) : 0xFFFFFFFF;
      uint32_t prev = tp[i];
      uint32_t next = prev | (fp[i] & mask);
      tp[i] = next;
      if (!change && (prev != next)) change = true;
    }
    return change;
  }

  // Tb = Tb | B
  bool SetBackwardMark(Node* to, int loop_num) {
    uint32_t* tp = &backward_[to->id() * width_ + INDEX(loop_num)];
    uint32_t prev = tp[0];
    uint32_t next = prev | BIT(loop_num);
    tp[0] = next;
    return next != prev;
  }

  // Tf = Tf | B
  bool SetForwardMark(Node* to, int loop_num) {
    uint32_t* tp = &forward_[to->id() * width_ + INDEX(loop_num)];
    uint32_t prev = tp[0];
    uint32_t next = prev | BIT(loop_num);
    tp[0] = next;
    return next != prev;
  }

  // Tf = Tf | (Ff & Tb)
  bool PropagateForwardMarks(Node* from, Node* to) {
    if (from == to) return false;
    bool change = false;
    int findex = from->id() * width_;
    int tindex = to->id() * width_;
    for (int i = 0; i < width_; i++) {
      uint32_t marks = backward_[tindex + i] & forward_[findex + i];
      uint32_t prev = forward_[tindex + i];
      uint32_t next = prev | marks;
      forward_[tindex + i] = next;
      if (!change && (prev != next)) change = true;
    }
    return change;
  }

  bool IsInLoop(Node* node, int loop_num) {
    int offset = node->id() * width_ + INDEX(loop_num);
    return backward_[offset] & forward_[offset] & BIT(loop_num);
  }
177 178 179

  // Propagate marks backward from loop headers.
  void PropagateBackward() {
180 181 182
    ResizeBackwardMarks();
    SetBackwardMark(end_, 0);
    Queue(end_);
183 184 185

    while (!queue_.empty()) {
      Node* node = queue_.front();
186
      info(node);
187 188 189
      queue_.pop_front();
      queued_.Set(node, false);

190
      int loop_num = -1;
191 192 193
      // Setup loop headers first.
      if (node->opcode() == IrOpcode::kLoop) {
        // found the loop node first.
194
        loop_num = CreateLoopInfo(node);
195
      } else if (NodeProperties::IsPhi(node)) {
196 197
        // found a phi first.
        Node* merge = node->InputAt(node->InputCount() - 1);
198
        if (merge->opcode() == IrOpcode::kLoop) {
199
          loop_num = CreateLoopInfo(merge);
200
        }
201 202
      }

203 204 205 206 207 208 209 210 211
      // Propagate marks backwards from this node.
      for (int i = 0; i < node->InputCount(); i++) {
        Node* input = node->InputAt(i);
        if (loop_num > 0 && i != kAssumedLoopEntryIndex) {
          // Only propagate the loop mark on backedges.
          if (SetBackwardMark(input, loop_num)) Queue(input);
        } else {
          // Entry or normal edge. Propagate all marks except loop_num.
          if (PropagateBackwardMarks(node, input, loop_num)) Queue(input);
212 213 214 215 216
        }
      }
    }
  }

217 218 219 220 221 222 223
  // Make a new loop if necessary for the given node.
  int CreateLoopInfo(Node* node) {
    int loop_num = LoopNum(node);
    if (loop_num > 0) return loop_num;

    loop_num = ++loops_found_;
    if (INDEX(loop_num) >= width_) ResizeBackwardMarks();
224 225 226 227

    // Create a new loop.
    loops_.push_back({node, nullptr, nullptr, nullptr});
    loop_tree_->NewLoop();
228 229
    SetBackwardMark(node, loop_num);
    loop_tree_->node_to_loop_num_[node->id()] = loop_num;
230 231 232

    // Setup loop mark for phis attached to loop header.
    for (Node* use : node->uses()) {
233
      if (NodeProperties::IsPhi(use)) {
234
        info(use);  // create the NodeInfo
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252
        SetBackwardMark(use, loop_num);
        loop_tree_->node_to_loop_num_[use->id()] = loop_num;
      }
    }

    return loop_num;
  }

  void ResizeBackwardMarks() {
    int new_width = width_ + 1;
    int max = num_nodes();
    uint32_t* new_backward = zone_->NewArray<uint32_t>(new_width * max);
    memset(new_backward, 0, new_width * max * sizeof(uint32_t));
    if (width_ > 0) {  // copy old matrix data.
      for (int i = 0; i < max; i++) {
        uint32_t* np = &new_backward[i * new_width];
        uint32_t* op = &backward_[i * width_];
        for (int j = 0; j < width_; j++) np[j] = op[j];
253 254
      }
    }
255 256 257 258 259 260 261 262
    width_ = new_width;
    backward_ = new_backward;
  }

  void ResizeForwardMarks() {
    int max = num_nodes();
    forward_ = zone_->NewArray<uint32_t>(width_ * max);
    memset(forward_, 0, width_ * max * sizeof(uint32_t));
263 264 265 266
  }

  // Propagate marks forward from loops.
  void PropagateForward() {
267
    ResizeForwardMarks();
268
    for (LoopInfo& li : loops_) {
269 270
      SetForwardMark(li.header, LoopNum(li.header));
      Queue(li.header);
271 272 273 274 275 276 277 278
    }
    // Propagate forward on paths that were backward reachable from backedges.
    while (!queue_.empty()) {
      Node* node = queue_.front();
      queue_.pop_front();
      queued_.Set(node, false);
      for (Edge edge : node->use_edges()) {
        Node* use = edge.from();
279 280
        if (!IsBackedge(use, edge)) {
          if (PropagateForwardMarks(node, use)) Queue(use);
281 282 283 284 285
        }
      }
    }
  }

286 287
  bool IsBackedge(Node* use, Edge& edge) {
    if (LoopNum(use) <= 0) return false;
288
    if (edge.index() == kAssumedLoopEntryIndex) return false;
289
    if (NodeProperties::IsPhi(use)) {
290 291 292 293 294
      return !NodeProperties::IsControlEdge(edge);
    }
    return true;
  }

295 296
  int LoopNum(Node* node) { return loop_tree_->node_to_loop_num_[node->id()]; }

297 298 299 300 301 302
  NodeInfo& info(Node* node) {
    NodeInfo& i = info_[node->id()];
    if (i.node == nullptr) i.node = node;
    return i;
  }

303 304
  void Queue(Node* node) {
    if (!queued_.Get(node)) {
305 306 307 308 309 310
      queue_.push_back(node);
      queued_.Set(node, true);
    }
  }

  void FinishLoopTree() {
311 312 313
    DCHECK(loops_found_ == static_cast<int>(loops_.size()));
    DCHECK(loops_found_ == static_cast<int>(loop_tree_->all_loops_.size()));

314
    // Degenerate cases.
315 316
    if (loops_found_ == 0) return;
    if (loops_found_ == 1) return FinishSingleLoop();
317

318
    for (int i = 1; i <= loops_found_; i++) ConnectLoopTree(i);
319 320 321 322

    size_t count = 0;
    // Place the node into the innermost nested loop of which it is a member.
    for (NodeInfo& ni : info_) {
323
      if (ni.node == nullptr) continue;
324 325

      LoopInfo* innermost = nullptr;
326 327 328 329 330 331 332 333 334 335 336 337 338 339 340
      int innermost_index = 0;
      int pos = ni.node->id() * width_;
      // Search the marks word by word.
      for (int i = 0; i < width_; i++) {
        uint32_t marks = backward_[pos + i] & forward_[pos + i];
        for (int j = 0; j < 32; j++) {
          if (marks & (1u << j)) {
            int loop_num = i * 32 + j;
            if (loop_num == 0) continue;
            LoopInfo* loop = &loops_[loop_num - 1];
            if (innermost == nullptr ||
                loop->loop->depth_ > innermost->loop->depth_) {
              innermost = loop;
              innermost_index = loop_num;
            }
341 342 343
          }
        }
      }
344 345
      if (innermost == nullptr) continue;
      if (LoopNum(ni.node) == innermost_index) {
346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369
        ni.next = innermost->header_list;
        innermost->header_list = &ni;
      } else {
        ni.next = innermost->body_list;
        innermost->body_list = &ni;
      }
      count++;
    }

    // Serialize the node lists for loops into the loop tree.
    loop_tree_->loop_nodes_.reserve(count);
    for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
      SerializeLoop(loop);
    }
  }

  // Handle the simpler case of a single loop (no checks for nesting necessary).
  void FinishSingleLoop() {
    // Place nodes into the loop header and body.
    LoopInfo* li = &loops_[0];
    li->loop = &loop_tree_->all_loops_[0];
    loop_tree_->SetParent(nullptr, li->loop);
    size_t count = 0;
    for (NodeInfo& ni : info_) {
370 371
      if (ni.node == nullptr || !IsInLoop(ni.node, 1)) continue;
      if (LoopNum(ni.node) == 1) {
372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388
        ni.next = li->header_list;
        li->header_list = &ni;
      } else {
        ni.next = li->body_list;
        li->body_list = &ni;
      }
      count++;
    }

    // Serialize the node lists for the loop into the loop tree.
    loop_tree_->loop_nodes_.reserve(count);
    SerializeLoop(li->loop);
  }

  // Recursively serialize the list of header nodes and body nodes
  // so that nested loops occupy nested intervals.
  void SerializeLoop(LoopTree::Loop* loop) {
389
    int loop_num = loop_tree_->LoopNum(loop);
390 391 392 393 394 395
    LoopInfo& li = loops_[loop_num - 1];

    // Serialize the header.
    loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
    for (NodeInfo* ni = li.header_list; ni != nullptr; ni = ni->next) {
      loop_tree_->loop_nodes_.push_back(ni->node);
396
      loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
397 398 399 400 401 402
    }

    // Serialize the body.
    loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
    for (NodeInfo* ni = li.body_list; ni != nullptr; ni = ni->next) {
      loop_tree_->loop_nodes_.push_back(ni->node);
403
      loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
404 405 406 407 408 409 410 411 412
    }

    // Serialize nested loops.
    for (LoopTree::Loop* child : loop->children_) SerializeLoop(child);

    loop->body_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
  }

  // Connect the LoopTree loops to their parents recursively.
413
  LoopTree::Loop* ConnectLoopTree(int loop_num) {
414 415 416 417 418
    LoopInfo& li = loops_[loop_num - 1];
    if (li.loop != nullptr) return li.loop;

    NodeInfo& ni = info(li.header);
    LoopTree::Loop* parent = nullptr;
419
    for (int i = 1; i <= loops_found_; i++) {
420
      if (i == loop_num) continue;
421
      if (IsInLoop(ni.node, i)) {
422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460
        // recursively create potential parent loops first.
        LoopTree::Loop* upper = ConnectLoopTree(i);
        if (parent == nullptr || upper->depth_ > parent->depth_) {
          parent = upper;
        }
      }
    }
    li.loop = &loop_tree_->all_loops_[loop_num - 1];
    loop_tree_->SetParent(parent, li.loop);
    return li.loop;
  }

  void PrintLoop(LoopTree::Loop* loop) {
    for (int i = 0; i < loop->depth_; i++) PrintF("  ");
    PrintF("Loop depth = %d ", loop->depth_);
    int i = loop->header_start_;
    while (i < loop->body_start_) {
      PrintF(" H#%d", loop_tree_->loop_nodes_[i++]->id());
    }
    while (i < loop->body_end_) {
      PrintF(" B#%d", loop_tree_->loop_nodes_[i++]->id());
    }
    PrintF("\n");
    for (LoopTree::Loop* child : loop->children_) PrintLoop(child);
  }
};


LoopTree* LoopFinder::BuildLoopTree(Graph* graph, Zone* zone) {
  LoopTree* loop_tree =
      new (graph->zone()) LoopTree(graph->NodeCount(), graph->zone());
  LoopFinderImpl finder(graph, loop_tree, zone);
  finder.Run();
  if (FLAG_trace_turbo_graph) {
    finder.Print();
  }
  return loop_tree;
}

461 462 463 464 465 466 467 468 469 470

Node* LoopTree::HeaderNode(Loop* loop) {
  Node* first = *HeaderNodes(loop).begin();
  if (first->opcode() == IrOpcode::kLoop) return first;
  DCHECK(IrOpcode::IsPhiOpcode(first->opcode()));
  Node* header = NodeProperties::GetControlInput(first);
  DCHECK_EQ(IrOpcode::kLoop, header->opcode());
  return header;
}

471 472 473
}  // namespace compiler
}  // namespace internal
}  // namespace v8