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