Home | History | Annotate | Download | only in compiler 
      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/compiler/graph.h"
     10 #include "src/compiler/node.h"
     11 #include "src/zone-containers.h"
     12 
     13 namespace v8 {
     14 namespace internal {
     15 namespace compiler {
     16 
     17 // TODO(titzer): don't assume entry edges have a particular index.
     18 static const int kAssumedLoopEntryIndex = 0;  // assume loops are entered here.
     19 
     20 class LoopFinderImpl;
     21 
     22 typedef base::iterator_range<Node**> NodeRange;
     23 
     24 // Represents a tree of loops in a graph.
     25 class LoopTree : public ZoneObject {
     26  public:
     27   LoopTree(size_t num_nodes, Zone* zone)
     28       : zone_(zone),
     29         outer_loops_(zone),
     30         all_loops_(zone),
     31         node_to_loop_num_(static_cast<int>(num_nodes), -1, zone),
     32         loop_nodes_(zone) {}
     33 
     34   // Represents a loop in the tree of loops, including the header nodes,
     35   // the body, and any nested loops.
     36   class Loop {
     37    public:
     38     Loop* parent() const { return parent_; }
     39     const ZoneVector<Loop*>& children() const { return children_; }
     40     size_t HeaderSize() const { return body_start_ - header_start_; }
     41     size_t BodySize() const { return body_end_ - body_start_; }
     42     size_t TotalSize() const { return body_end_ - header_start_; }
     43     size_t depth() const { return static_cast<size_t>(depth_); }
     44 
     45    private:
     46     friend class LoopTree;
     47     friend class LoopFinderImpl;
     48 
     49     explicit Loop(Zone* zone)
     50         : parent_(nullptr),
     51           depth_(0),
     52           children_(zone),
     53           header_start_(-1),
     54           body_start_(-1),
     55           body_end_(-1) {}
     56     Loop* parent_;
     57     int depth_;
     58     ZoneVector<Loop*> children_;
     59     int header_start_;
     60     int body_start_;
     61     int body_end_;
     62   };
     63 
     64   // Return the innermost nested loop, if any, that contains {node}.
     65   Loop* ContainingLoop(Node* node) {
     66     if (node->id() >= node_to_loop_num_.size()) return nullptr;
     67     int num = node_to_loop_num_[node->id()];
     68     return num > 0 ? &all_loops_[num - 1] : nullptr;
     69   }
     70 
     71   // Check if the {loop} contains the {node}, either directly or by containing
     72   // a nested loop that contains {node}.
     73   bool Contains(Loop* loop, Node* node) {
     74     for (Loop* c = ContainingLoop(node); c != nullptr; c = c->parent_) {
     75       if (c == loop) return true;
     76     }
     77     return false;
     78   }
     79 
     80   // Return the list of outer loops.
     81   const ZoneVector<Loop*>& outer_loops() const { return outer_loops_; }
     82 
     83   // Return the unique loop number for a given loop. Loop numbers start at {1}.
     84   int LoopNum(Loop* loop) const {
     85     return 1 + static_cast<int>(loop - &all_loops_[0]);
     86   }
     87 
     88   // Return a range which can iterate over the header nodes of {loop}.
     89   NodeRange HeaderNodes(Loop* loop) {
     90     return NodeRange(&loop_nodes_[0] + loop->header_start_,
     91                      &loop_nodes_[0] + loop->body_start_);
     92   }
     93 
     94   // Return the header control node for a loop.
     95   Node* HeaderNode(Loop* loop);
     96 
     97   // Return a range which can iterate over the body nodes of {loop}.
     98   NodeRange BodyNodes(Loop* loop) {
     99     return NodeRange(&loop_nodes_[0] + loop->body_start_,
    100                      &loop_nodes_[0] + loop->body_end_);
    101   }
    102 
    103   // Return a range which can iterate over the nodes of {loop}.
    104   NodeRange LoopNodes(Loop* loop) {
    105     return NodeRange(&loop_nodes_[0] + loop->header_start_,
    106                      &loop_nodes_[0] + loop->body_end_);
    107   }
    108 
    109   // Return the node that represents the control, i.e. the loop node itself.
    110   Node* GetLoopControl(Loop* loop) {
    111     // TODO(turbofan): make the loop control node always first?
    112     for (Node* node : HeaderNodes(loop)) {
    113       if (node->opcode() == IrOpcode::kLoop) return node;
    114     }
    115     UNREACHABLE();
    116     return nullptr;
    117   }
    118 
    119  private:
    120   friend class LoopFinderImpl;
    121 
    122   Loop* NewLoop() {
    123     all_loops_.push_back(Loop(zone_));
    124     Loop* result = &all_loops_.back();
    125     return result;
    126   }
    127 
    128   void SetParent(Loop* parent, Loop* child) {
    129     if (parent != nullptr) {
    130       parent->children_.push_back(child);
    131       child->parent_ = parent;
    132       child->depth_ = parent->depth_ + 1;
    133     } else {
    134       outer_loops_.push_back(child);
    135     }
    136   }
    137 
    138   Zone* zone_;
    139   ZoneVector<Loop*> outer_loops_;
    140   ZoneVector<Loop> all_loops_;
    141   ZoneVector<int> node_to_loop_num_;
    142   ZoneVector<Node*> loop_nodes_;
    143 };
    144 
    145 class LoopFinder {
    146  public:
    147   // Build a loop tree for the entire graph.
    148   static LoopTree* BuildLoopTree(Graph* graph, Zone* temp_zone);
    149 };
    150 
    151 
    152 }  // namespace compiler
    153 }  // namespace internal
    154 }  // namespace v8
    155 
    156 #endif  // V8_COMPILER_LOOP_ANALYSIS_H_
    157