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