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 } 127 zone()128 Zone* zone() const { return zone_; } 129 130 private: 131 friend class LoopFinderImpl; 132 NewLoop()133 Loop* NewLoop() { 134 all_loops_.push_back(Loop(zone_)); 135 Loop* result = &all_loops_.back(); 136 return result; 137 } 138 SetParent(Loop * parent,Loop * child)139 void SetParent(Loop* parent, Loop* child) { 140 if (parent != nullptr) { 141 parent->children_.push_back(child); 142 child->parent_ = parent; 143 child->depth_ = parent->depth_ + 1; 144 } else { 145 outer_loops_.push_back(child); 146 } 147 } 148 149 Zone* zone_; 150 ZoneVector<Loop*> outer_loops_; 151 ZoneVector<Loop> all_loops_; 152 ZoneVector<int> node_to_loop_num_; 153 ZoneVector<Node*> loop_nodes_; 154 }; 155 156 class V8_EXPORT_PRIVATE LoopFinder { 157 public: 158 // Build a loop tree for the entire graph. 159 static LoopTree* BuildLoopTree(Graph* graph, Zone* temp_zone); 160 }; 161 162 163 } // namespace compiler 164 } // namespace internal 165 } // namespace v8 166 167 #endif // V8_COMPILER_LOOP_ANALYSIS_H_ 168