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: 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: 39 Loop* parent() const { return parent_; } 40 const ZoneVector<Loop*>& children() const { return children_; } 41 size_t HeaderSize() const { return body_start_ - header_start_; } 42 size_t BodySize() const { return exits_start_ - body_start_; } 43 size_t ExitsSize() const { return exits_end_ - exits_start_; } 44 size_t TotalSize() const { return exits_end_ - header_start_; } 45 size_t depth() const { return static_cast<size_t>(depth_); } 46 47 private: 48 friend class LoopTree; 49 friend class LoopFinderImpl; 50 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}. 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}. 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. 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}. 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}. 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}. 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}. 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}. 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. 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 129 Zone* zone() const { return zone_; } 130 131 private: 132 friend class LoopFinderImpl; 133 134 Loop* NewLoop() { 135 all_loops_.push_back(Loop(zone_)); 136 Loop* result = &all_loops_.back(); 137 return result; 138 } 139 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
