Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 17 | // TODO(titzer): don't assume entry edges have a particular index. |
| 18 | static const int kAssumedLoopEntryIndex = 0; // assume loops are entered here. |
| 19 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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: |
| 27 | LoopTree(size_t num_nodes, Zone* zone) |
| 28 | : zone_(zone), |
| 29 | outer_loops_(zone), |
| 30 | all_loops_(zone), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 31 | node_to_loop_num_(static_cast<int>(num_nodes), -1, zone), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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: |
| 38 | Loop* parent() const { return parent_; } |
| 39 | const ZoneVector<Loop*>& children() const { return children_; } |
| 40 | size_t HeaderSize() const { return body_start_ - header_start_; } |
| 41 | size_t BodySize() const { return body_end_ - body_start_; } |
| 42 | size_t TotalSize() const { return body_end_ - header_start_; } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 43 | size_t depth() const { return static_cast<size_t>(depth_); } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 44 | |
| 45 | private: |
| 46 | friend class LoopTree; |
| 47 | friend class LoopFinderImpl; |
| 48 | |
| 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}. |
| 65 | Loop* ContainingLoop(Node* node) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 66 | if (node->id() >= node_to_loop_num_.size()) return nullptr; |
| 67 | int num = node_to_loop_num_[node->id()]; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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}. |
| 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. |
| 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}. |
| 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}. |
| 89 | NodeRange HeaderNodes(Loop* loop) { |
| 90 | return NodeRange(&loop_nodes_[0] + loop->header_start_, |
| 91 | &loop_nodes_[0] + loop->body_start_); |
| 92 | } |
| 93 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 94 | // Return the header control node for a loop. |
| 95 | Node* HeaderNode(Loop* loop); |
| 96 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 97 | // Return a range which can iterate over the body nodes of {loop}. |
| 98 | NodeRange BodyNodes(Loop* loop) { |
| 99 | return NodeRange(&loop_nodes_[0] + loop->body_start_, |
| 100 | &loop_nodes_[0] + loop->body_end_); |
| 101 | } |
| 102 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 103 | // Return a range which can iterate over the nodes of {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. |
| 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 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 119 | Zone* zone() const { return zone_; } |
| 120 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 121 | private: |
| 122 | friend class LoopFinderImpl; |
| 123 | |
| 124 | Loop* NewLoop() { |
| 125 | all_loops_.push_back(Loop(zone_)); |
| 126 | Loop* result = &all_loops_.back(); |
| 127 | return result; |
| 128 | } |
| 129 | |
| 130 | void SetParent(Loop* parent, Loop* child) { |
| 131 | if (parent != nullptr) { |
| 132 | parent->children_.push_back(child); |
| 133 | child->parent_ = parent; |
| 134 | child->depth_ = parent->depth_ + 1; |
| 135 | } else { |
| 136 | outer_loops_.push_back(child); |
| 137 | } |
| 138 | } |
| 139 | |
| 140 | Zone* zone_; |
| 141 | ZoneVector<Loop*> outer_loops_; |
| 142 | ZoneVector<Loop> all_loops_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 143 | ZoneVector<int> node_to_loop_num_; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 144 | ZoneVector<Node*> loop_nodes_; |
| 145 | }; |
| 146 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 147 | class LoopFinder { |
| 148 | public: |
| 149 | // Build a loop tree for the entire graph. |
| 150 | static LoopTree* BuildLoopTree(Graph* graph, Zone* temp_zone); |
| 151 | }; |
| 152 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 153 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 154 | } // namespace compiler |
| 155 | } // namespace internal |
| 156 | } // namespace v8 |
| 157 | |
| 158 | #endif // V8_COMPILER_LOOP_ANALYSIS_H_ |