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:
LoopTree(size_t num_nodes,Zone * zone)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:
parent()38     Loop* parent() const { return parent_; }
children()39     const ZoneVector<Loop*>& children() const { return children_; }
HeaderSize()40     size_t HeaderSize() const { return body_start_ - header_start_; }
BodySize()41     size_t BodySize() const { return body_end_ - body_start_; }
TotalSize()42     size_t TotalSize() const { return body_end_ - header_start_; }
depth()43     size_t depth() const { return static_cast<size_t>(depth_); }
44 
45    private:
46     friend class LoopTree;
47     friend class LoopFinderImpl;
48 
Loop(Zone * zone)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}.
ContainingLoop(Node * 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}.
Contains(Loop * loop,Node * 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.
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}.
LoopNum(Loop * loop)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}.
HeaderNodes(Loop * 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}.
BodyNodes(Loop * 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}.
LoopNodes(Loop * 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.
GetLoopControl(Loop * loop)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 
NewLoop()122   Loop* NewLoop() {
123     all_loops_.push_back(Loop(zone_));
124     Loop* result = &all_loops_.back();
125     return result;
126   }
127 
SetParent(Loop * parent,Loop * child)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