1958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// Copyright 2014 the V8 project authors. All rights reserved. 2958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// Use of this source code is governed by a BSD-style license that can be 3958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// found in the LICENSE file. 4958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 5958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#ifndef V8_COMPILER_LOOP_ANALYSIS_H_ 6958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#define V8_COMPILER_LOOP_ANALYSIS_H_ 7958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 8958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include "src/base/iterator.h" 9958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include "src/compiler/graph.h" 10958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include "src/compiler/node.h" 11c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch#include "src/globals.h" 12f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch#include "src/zone/zone-containers.h" 13958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 14958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniernamespace v8 { 15958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniernamespace internal { 16958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniernamespace compiler { 17958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 18014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// TODO(titzer): don't assume entry edges have a particular index. 19014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstatic const int kAssumedLoopEntryIndex = 0; // assume loops are entered here. 20014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 21958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass LoopFinderImpl; 22958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 23958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniertypedef base::iterator_range<Node**> NodeRange; 24958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 25958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// Represents a tree of loops in a graph. 26958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass LoopTree : public ZoneObject { 27958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 28958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier LoopTree(size_t num_nodes, Zone* zone) 29958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : zone_(zone), 30958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier outer_loops_(zone), 31958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier all_loops_(zone), 32014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch node_to_loop_num_(static_cast<int>(num_nodes), -1, zone), 33958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier loop_nodes_(zone) {} 34958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 35958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Represents a loop in the tree of loops, including the header nodes, 36958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // the body, and any nested loops. 37958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier class Loop { 38958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 39958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Loop* parent() const { return parent_; } 40958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const ZoneVector<Loop*>& children() const { return children_; } 41958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t HeaderSize() const { return body_start_ - header_start_; } 42f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch size_t BodySize() const { return exits_start_ - body_start_; } 43f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch size_t ExitsSize() const { return exits_end_ - exits_start_; } 44f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch size_t TotalSize() const { return exits_end_ - header_start_; } 45014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t depth() const { return static_cast<size_t>(depth_); } 46958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 47958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 48958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier friend class LoopTree; 49958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier friend class LoopFinderImpl; 50958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 51958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier explicit Loop(Zone* zone) 52958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : parent_(nullptr), 53958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier depth_(0), 54958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier children_(zone), 55958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier header_start_(-1), 56958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier body_start_(-1), 57f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch exits_start_(-1), 58f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch exits_end_(-1) {} 59958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Loop* parent_; 60958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int depth_; 61958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier ZoneVector<Loop*> children_; 62958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int header_start_; 63958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int body_start_; 64f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch int exits_start_; 65f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch int exits_end_; 66958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier }; 67958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 68958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Return the innermost nested loop, if any, that contains {node}. 69958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Loop* ContainingLoop(Node* node) { 70014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (node->id() >= node_to_loop_num_.size()) return nullptr; 71014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int num = node_to_loop_num_[node->id()]; 72958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return num > 0 ? &all_loops_[num - 1] : nullptr; 73958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 74958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 75958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Check if the {loop} contains the {node}, either directly or by containing 76958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // a nested loop that contains {node}. 77958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool Contains(Loop* loop, Node* node) { 78958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier for (Loop* c = ContainingLoop(node); c != nullptr; c = c->parent_) { 79958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (c == loop) return true; 80958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 81958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return false; 82958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 83958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 84958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Return the list of outer loops. 85958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const ZoneVector<Loop*>& outer_loops() const { return outer_loops_; } 86958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 87958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Return the unique loop number for a given loop. Loop numbers start at {1}. 88958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int LoopNum(Loop* loop) const { 89958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return 1 + static_cast<int>(loop - &all_loops_[0]); 90958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 91958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 92958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Return a range which can iterate over the header nodes of {loop}. 93958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier NodeRange HeaderNodes(Loop* loop) { 94958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return NodeRange(&loop_nodes_[0] + loop->header_start_, 95958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier &loop_nodes_[0] + loop->body_start_); 96958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 97958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 98014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Return the header control node for a loop. 99014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* HeaderNode(Loop* loop); 100014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 101958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Return a range which can iterate over the body nodes of {loop}. 102958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier NodeRange BodyNodes(Loop* loop) { 103958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return NodeRange(&loop_nodes_[0] + loop->body_start_, 104f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch &loop_nodes_[0] + loop->exits_start_); 105f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 106f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 107f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Return a range which can iterate over the body nodes of {loop}. 108f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch NodeRange ExitNodes(Loop* loop) { 109f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return NodeRange(&loop_nodes_[0] + loop->exits_start_, 110f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch &loop_nodes_[0] + loop->exits_end_); 111958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 112958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 113014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Return a range which can iterate over the nodes of {loop}. 114014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch NodeRange LoopNodes(Loop* loop) { 115014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return NodeRange(&loop_nodes_[0] + loop->header_start_, 116f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch &loop_nodes_[0] + loop->exits_end_); 117014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 118014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 119014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Return the node that represents the control, i.e. the loop node itself. 120014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* GetLoopControl(Loop* loop) { 121014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // TODO(turbofan): make the loop control node always first? 122014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (Node* node : HeaderNodes(loop)) { 123014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (node->opcode() == IrOpcode::kLoop) return node; 124014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 125014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UNREACHABLE(); 126014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return nullptr; 127014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 128014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1293b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch Zone* zone() const { return zone_; } 1303b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 131958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 132958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier friend class LoopFinderImpl; 133958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 134958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Loop* NewLoop() { 135958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier all_loops_.push_back(Loop(zone_)); 136958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Loop* result = &all_loops_.back(); 137958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return result; 138958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 139958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 140958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void SetParent(Loop* parent, Loop* child) { 141958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (parent != nullptr) { 142958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier parent->children_.push_back(child); 143958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier child->parent_ = parent; 144958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier child->depth_ = parent->depth_ + 1; 145958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } else { 146958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier outer_loops_.push_back(child); 147958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 148958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 149958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 150958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Zone* zone_; 151958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier ZoneVector<Loop*> outer_loops_; 152958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier ZoneVector<Loop> all_loops_; 153014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<int> node_to_loop_num_; 154958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier ZoneVector<Node*> loop_nodes_; 155958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier}; 156958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 157c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdochclass V8_EXPORT_PRIVATE LoopFinder { 158958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 159958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Build a loop tree for the entire graph. 160958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier static LoopTree* BuildLoopTree(Graph* graph, Zone* temp_zone); 161958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier}; 162958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 163014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 164958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace compiler 165958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace internal 166958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace v8 167958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 168958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#endif // V8_COMPILER_LOOP_ANALYSIS_H_ 169