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