| // Copyright 2014 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "src/compiler/loop-analysis.h" |
| |
| #include "src/compiler/graph.h" |
| #include "src/compiler/node-marker.h" |
| #include "src/compiler/node-properties.h" |
| #include "src/compiler/node.h" |
| #include "src/zone/zone.h" |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| #define OFFSET(x) ((x)&0x1F) |
| #define BIT(x) (1u << OFFSET(x)) |
| #define INDEX(x) ((x) >> 5) |
| |
| // Temporary information for each node during marking. |
| struct NodeInfo { |
| Node* node; |
| NodeInfo* next; // link in chaining loop members |
| }; |
| |
| |
| // Temporary loop info needed during traversal and building the loop tree. |
| struct TempLoopInfo { |
| Node* header; |
| NodeInfo* header_list; |
| NodeInfo* exit_list; |
| NodeInfo* body_list; |
| LoopTree::Loop* loop; |
| }; |
| |
| |
| // Encapsulation of the loop finding algorithm. |
| // ----------------------------------------------------------------------------- |
| // Conceptually, the contents of a loop are those nodes that are "between" the |
| // loop header and the backedges of the loop. Graphs in the soup of nodes can |
| // form improper cycles, so standard loop finding algorithms that work on CFGs |
| // aren't sufficient. However, in valid TurboFan graphs, all cycles involve |
| // either a {Loop} node or a phi. The {Loop} node itself and its accompanying |
| // phis are treated together as a set referred to here as the loop header. |
| // This loop finding algorithm works by traversing the graph in two directions, |
| // first from nodes to their inputs, starting at {end}, then in the reverse |
| // direction, from nodes to their uses, starting at loop headers. |
| // 1 bit per loop per node per direction are required during the marking phase. |
| // To handle nested loops correctly, the algorithm must filter some reachability |
| // marks on edges into/out-of the loop header nodes. |
| class LoopFinderImpl { |
| public: |
| LoopFinderImpl(Graph* graph, LoopTree* loop_tree, Zone* zone) |
| : zone_(zone), |
| end_(graph->end()), |
| queue_(zone), |
| queued_(graph, 2), |
| info_(graph->NodeCount(), {nullptr, nullptr}, zone), |
| loops_(zone), |
| loop_num_(graph->NodeCount(), -1, zone), |
| loop_tree_(loop_tree), |
| loops_found_(0), |
| width_(0), |
| backward_(nullptr), |
| forward_(nullptr) {} |
| |
| void Run() { |
| PropagateBackward(); |
| PropagateForward(); |
| FinishLoopTree(); |
| } |
| |
| void Print() { |
| // Print out the results. |
| for (NodeInfo& ni : info_) { |
| if (ni.node == nullptr) continue; |
| for (int i = 1; i <= loops_found_; i++) { |
| int index = ni.node->id() * width_ + INDEX(i); |
| bool marked_forward = forward_[index] & BIT(i); |
| bool marked_backward = backward_[index] & BIT(i); |
| if (marked_forward && marked_backward) { |
| PrintF("X"); |
| } else if (marked_forward) { |
| PrintF(">"); |
| } else if (marked_backward) { |
| PrintF("<"); |
| } else { |
| PrintF(" "); |
| } |
| } |
| PrintF(" #%d:%s\n", ni.node->id(), ni.node->op()->mnemonic()); |
| } |
| |
| int i = 0; |
| for (TempLoopInfo& li : loops_) { |
| PrintF("Loop %d headed at #%d\n", i, li.header->id()); |
| i++; |
| } |
| |
| for (LoopTree::Loop* loop : loop_tree_->outer_loops_) { |
| PrintLoop(loop); |
| } |
| } |
| |
| private: |
| Zone* zone_; |
| Node* end_; |
| NodeDeque queue_; |
| NodeMarker<bool> queued_; |
| ZoneVector<NodeInfo> info_; |
| ZoneVector<TempLoopInfo> loops_; |
| ZoneVector<int> loop_num_; |
| LoopTree* loop_tree_; |
| int loops_found_; |
| int width_; |
| uint32_t* backward_; |
| uint32_t* forward_; |
| |
| int num_nodes() { |
| return static_cast<int>(loop_tree_->node_to_loop_num_.size()); |
| } |
| |
| // Tb = Tb | (Fb - loop_filter) |
| bool PropagateBackwardMarks(Node* from, Node* to, int loop_filter) { |
| if (from == to) return false; |
| uint32_t* fp = &backward_[from->id() * width_]; |
| uint32_t* tp = &backward_[to->id() * width_]; |
| bool change = false; |
| for (int i = 0; i < width_; i++) { |
| uint32_t mask = i == INDEX(loop_filter) ? ~BIT(loop_filter) : 0xFFFFFFFF; |
| uint32_t prev = tp[i]; |
| uint32_t next = prev | (fp[i] & mask); |
| tp[i] = next; |
| if (!change && (prev != next)) change = true; |
| } |
| return change; |
| } |
| |
| // Tb = Tb | B |
| bool SetBackwardMark(Node* to, int loop_num) { |
| uint32_t* tp = &backward_[to->id() * width_ + INDEX(loop_num)]; |
| uint32_t prev = tp[0]; |
| uint32_t next = prev | BIT(loop_num); |
| tp[0] = next; |
| return next != prev; |
| } |
| |
| // Tf = Tf | B |
| bool SetForwardMark(Node* to, int loop_num) { |
| uint32_t* tp = &forward_[to->id() * width_ + INDEX(loop_num)]; |
| uint32_t prev = tp[0]; |
| uint32_t next = prev | BIT(loop_num); |
| tp[0] = next; |
| return next != prev; |
| } |
| |
| // Tf = Tf | (Ff & Tb) |
| bool PropagateForwardMarks(Node* from, Node* to) { |
| if (from == to) return false; |
| bool change = false; |
| int findex = from->id() * width_; |
| int tindex = to->id() * width_; |
| for (int i = 0; i < width_; i++) { |
| uint32_t marks = backward_[tindex + i] & forward_[findex + i]; |
| uint32_t prev = forward_[tindex + i]; |
| uint32_t next = prev | marks; |
| forward_[tindex + i] = next; |
| if (!change && (prev != next)) change = true; |
| } |
| return change; |
| } |
| |
| bool IsInLoop(Node* node, int loop_num) { |
| int offset = node->id() * width_ + INDEX(loop_num); |
| return backward_[offset] & forward_[offset] & BIT(loop_num); |
| } |
| |
| // Propagate marks backward from loop headers. |
| void PropagateBackward() { |
| ResizeBackwardMarks(); |
| SetBackwardMark(end_, 0); |
| Queue(end_); |
| |
| while (!queue_.empty()) { |
| Node* node = queue_.front(); |
| info(node); |
| queue_.pop_front(); |
| queued_.Set(node, false); |
| |
| int loop_num = -1; |
| // Setup loop headers first. |
| if (node->opcode() == IrOpcode::kLoop) { |
| // found the loop node first. |
| loop_num = CreateLoopInfo(node); |
| } else if (NodeProperties::IsPhi(node)) { |
| // found a phi first. |
| Node* merge = node->InputAt(node->InputCount() - 1); |
| if (merge->opcode() == IrOpcode::kLoop) { |
| loop_num = CreateLoopInfo(merge); |
| } |
| } else if (node->opcode() == IrOpcode::kLoopExit) { |
| // Intentionally ignore return value. Loop exit node marks |
| // are propagated normally. |
| CreateLoopInfo(node->InputAt(1)); |
| } else if (node->opcode() == IrOpcode::kLoopExitValue || |
| node->opcode() == IrOpcode::kLoopExitEffect) { |
| Node* loop_exit = NodeProperties::GetControlInput(node); |
| // Intentionally ignore return value. Loop exit node marks |
| // are propagated normally. |
| CreateLoopInfo(loop_exit->InputAt(1)); |
| } |
| |
| // Propagate marks backwards from this node. |
| for (int i = 0; i < node->InputCount(); i++) { |
| Node* input = node->InputAt(i); |
| if (IsBackedge(node, i)) { |
| // Only propagate the loop mark on backedges. |
| if (SetBackwardMark(input, loop_num)) Queue(input); |
| } else { |
| // Entry or normal edge. Propagate all marks except loop_num. |
| if (PropagateBackwardMarks(node, input, loop_num)) Queue(input); |
| } |
| } |
| } |
| } |
| |
| // Make a new loop if necessary for the given node. |
| int CreateLoopInfo(Node* node) { |
| DCHECK_EQ(IrOpcode::kLoop, node->opcode()); |
| int loop_num = LoopNum(node); |
| if (loop_num > 0) return loop_num; |
| |
| loop_num = ++loops_found_; |
| if (INDEX(loop_num) >= width_) ResizeBackwardMarks(); |
| |
| // Create a new loop. |
| loops_.push_back({node, nullptr, nullptr, nullptr, nullptr}); |
| loop_tree_->NewLoop(); |
| SetLoopMarkForLoopHeader(node, loop_num); |
| return loop_num; |
| } |
| |
| void SetLoopMark(Node* node, int loop_num) { |
| info(node); // create the NodeInfo |
| SetBackwardMark(node, loop_num); |
| loop_tree_->node_to_loop_num_[node->id()] = loop_num; |
| } |
| |
| void SetLoopMarkForLoopHeader(Node* node, int loop_num) { |
| DCHECK_EQ(IrOpcode::kLoop, node->opcode()); |
| SetLoopMark(node, loop_num); |
| for (Node* use : node->uses()) { |
| if (NodeProperties::IsPhi(use)) { |
| SetLoopMark(use, loop_num); |
| } |
| |
| // Do not keep the loop alive if it does not have any backedges. |
| if (node->InputCount() <= 1) continue; |
| |
| if (use->opcode() == IrOpcode::kLoopExit) { |
| SetLoopMark(use, loop_num); |
| for (Node* exit_use : use->uses()) { |
| if (exit_use->opcode() == IrOpcode::kLoopExitValue || |
| exit_use->opcode() == IrOpcode::kLoopExitEffect) { |
| SetLoopMark(exit_use, loop_num); |
| } |
| } |
| } |
| } |
| } |
| |
| void ResizeBackwardMarks() { |
| int new_width = width_ + 1; |
| int max = num_nodes(); |
| uint32_t* new_backward = zone_->NewArray<uint32_t>(new_width * max); |
| memset(new_backward, 0, new_width * max * sizeof(uint32_t)); |
| if (width_ > 0) { // copy old matrix data. |
| for (int i = 0; i < max; i++) { |
| uint32_t* np = &new_backward[i * new_width]; |
| uint32_t* op = &backward_[i * width_]; |
| for (int j = 0; j < width_; j++) np[j] = op[j]; |
| } |
| } |
| width_ = new_width; |
| backward_ = new_backward; |
| } |
| |
| void ResizeForwardMarks() { |
| int max = num_nodes(); |
| forward_ = zone_->NewArray<uint32_t>(width_ * max); |
| memset(forward_, 0, width_ * max * sizeof(uint32_t)); |
| } |
| |
| // Propagate marks forward from loops. |
| void PropagateForward() { |
| ResizeForwardMarks(); |
| for (TempLoopInfo& li : loops_) { |
| SetForwardMark(li.header, LoopNum(li.header)); |
| Queue(li.header); |
| } |
| // Propagate forward on paths that were backward reachable from backedges. |
| while (!queue_.empty()) { |
| Node* node = queue_.front(); |
| queue_.pop_front(); |
| queued_.Set(node, false); |
| for (Edge edge : node->use_edges()) { |
| Node* use = edge.from(); |
| if (!IsBackedge(use, edge.index())) { |
| if (PropagateForwardMarks(node, use)) Queue(use); |
| } |
| } |
| } |
| } |
| |
| bool IsLoopHeaderNode(Node* node) { |
| return node->opcode() == IrOpcode::kLoop || NodeProperties::IsPhi(node); |
| } |
| |
| bool IsLoopExitNode(Node* node) { |
| return node->opcode() == IrOpcode::kLoopExit || |
| node->opcode() == IrOpcode::kLoopExitValue || |
| node->opcode() == IrOpcode::kLoopExitEffect; |
| } |
| |
| bool IsBackedge(Node* use, int index) { |
| if (LoopNum(use) <= 0) return false; |
| if (NodeProperties::IsPhi(use)) { |
| return index != NodeProperties::FirstControlIndex(use) && |
| index != kAssumedLoopEntryIndex; |
| } else if (use->opcode() == IrOpcode::kLoop) { |
| return index != kAssumedLoopEntryIndex; |
| } |
| DCHECK(IsLoopExitNode(use)); |
| return false; |
| } |
| |
| int LoopNum(Node* node) { return loop_tree_->node_to_loop_num_[node->id()]; } |
| |
| NodeInfo& info(Node* node) { |
| NodeInfo& i = info_[node->id()]; |
| if (i.node == nullptr) i.node = node; |
| return i; |
| } |
| |
| void Queue(Node* node) { |
| if (!queued_.Get(node)) { |
| queue_.push_back(node); |
| queued_.Set(node, true); |
| } |
| } |
| |
| void AddNodeToLoop(NodeInfo* node_info, TempLoopInfo* loop, int loop_num) { |
| if (LoopNum(node_info->node) == loop_num) { |
| if (IsLoopHeaderNode(node_info->node)) { |
| node_info->next = loop->header_list; |
| loop->header_list = node_info; |
| } else { |
| DCHECK(IsLoopExitNode(node_info->node)); |
| node_info->next = loop->exit_list; |
| loop->exit_list = node_info; |
| } |
| } else { |
| node_info->next = loop->body_list; |
| loop->body_list = node_info; |
| } |
| } |
| |
| void FinishLoopTree() { |
| DCHECK(loops_found_ == static_cast<int>(loops_.size())); |
| DCHECK(loops_found_ == static_cast<int>(loop_tree_->all_loops_.size())); |
| |
| // Degenerate cases. |
| if (loops_found_ == 0) return; |
| if (loops_found_ == 1) return FinishSingleLoop(); |
| |
| for (int i = 1; i <= loops_found_; i++) ConnectLoopTree(i); |
| |
| size_t count = 0; |
| // Place the node into the innermost nested loop of which it is a member. |
| for (NodeInfo& ni : info_) { |
| if (ni.node == nullptr) continue; |
| |
| TempLoopInfo* innermost = nullptr; |
| int innermost_index = 0; |
| int pos = ni.node->id() * width_; |
| // Search the marks word by word. |
| for (int i = 0; i < width_; i++) { |
| uint32_t marks = backward_[pos + i] & forward_[pos + i]; |
| |
| for (int j = 0; j < 32; j++) { |
| if (marks & (1u << j)) { |
| int loop_num = i * 32 + j; |
| if (loop_num == 0) continue; |
| TempLoopInfo* loop = &loops_[loop_num - 1]; |
| if (innermost == nullptr || |
| loop->loop->depth_ > innermost->loop->depth_) { |
| innermost = loop; |
| innermost_index = loop_num; |
| } |
| } |
| } |
| } |
| if (innermost == nullptr) continue; |
| |
| // Return statements should never be found by forward or backward walk. |
| CHECK(ni.node->opcode() != IrOpcode::kReturn); |
| |
| AddNodeToLoop(&ni, innermost, innermost_index); |
| count++; |
| } |
| |
| // Serialize the node lists for loops into the loop tree. |
| loop_tree_->loop_nodes_.reserve(count); |
| for (LoopTree::Loop* loop : loop_tree_->outer_loops_) { |
| SerializeLoop(loop); |
| } |
| } |
| |
| // Handle the simpler case of a single loop (no checks for nesting necessary). |
| void FinishSingleLoop() { |
| // Place nodes into the loop header and body. |
| TempLoopInfo* li = &loops_[0]; |
| li->loop = &loop_tree_->all_loops_[0]; |
| loop_tree_->SetParent(nullptr, li->loop); |
| size_t count = 0; |
| for (NodeInfo& ni : info_) { |
| if (ni.node == nullptr || !IsInLoop(ni.node, 1)) continue; |
| |
| // Return statements should never be found by forward or backward walk. |
| CHECK(ni.node->opcode() != IrOpcode::kReturn); |
| |
| AddNodeToLoop(&ni, li, 1); |
| count++; |
| } |
| |
| // Serialize the node lists for the loop into the loop tree. |
| loop_tree_->loop_nodes_.reserve(count); |
| SerializeLoop(li->loop); |
| } |
| |
| // Recursively serialize the list of header nodes and body nodes |
| // so that nested loops occupy nested intervals. |
| void SerializeLoop(LoopTree::Loop* loop) { |
| int loop_num = loop_tree_->LoopNum(loop); |
| TempLoopInfo& li = loops_[loop_num - 1]; |
| |
| // Serialize the header. |
| loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size()); |
| for (NodeInfo* ni = li.header_list; ni != nullptr; ni = ni->next) { |
| loop_tree_->loop_nodes_.push_back(ni->node); |
| loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num; |
| } |
| |
| // Serialize the body. |
| loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size()); |
| for (NodeInfo* ni = li.body_list; ni != nullptr; ni = ni->next) { |
| loop_tree_->loop_nodes_.push_back(ni->node); |
| loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num; |
| } |
| |
| // Serialize nested loops. |
| for (LoopTree::Loop* child : loop->children_) SerializeLoop(child); |
| |
| // Serialize the exits. |
| loop->exits_start_ = static_cast<int>(loop_tree_->loop_nodes_.size()); |
| for (NodeInfo* ni = li.exit_list; ni != nullptr; ni = ni->next) { |
| loop_tree_->loop_nodes_.push_back(ni->node); |
| loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num; |
| } |
| |
| loop->exits_end_ = static_cast<int>(loop_tree_->loop_nodes_.size()); |
| } |
| |
| // Connect the LoopTree loops to their parents recursively. |
| LoopTree::Loop* ConnectLoopTree(int loop_num) { |
| TempLoopInfo& li = loops_[loop_num - 1]; |
| if (li.loop != nullptr) return li.loop; |
| |
| NodeInfo& ni = info(li.header); |
| LoopTree::Loop* parent = nullptr; |
| for (int i = 1; i <= loops_found_; i++) { |
| if (i == loop_num) continue; |
| if (IsInLoop(ni.node, i)) { |
| // recursively create potential parent loops first. |
| LoopTree::Loop* upper = ConnectLoopTree(i); |
| if (parent == nullptr || upper->depth_ > parent->depth_) { |
| parent = upper; |
| } |
| } |
| } |
| li.loop = &loop_tree_->all_loops_[loop_num - 1]; |
| loop_tree_->SetParent(parent, li.loop); |
| return li.loop; |
| } |
| |
| void PrintLoop(LoopTree::Loop* loop) { |
| for (int i = 0; i < loop->depth_; i++) PrintF(" "); |
| PrintF("Loop depth = %d ", loop->depth_); |
| int i = loop->header_start_; |
| while (i < loop->body_start_) { |
| PrintF(" H#%d", loop_tree_->loop_nodes_[i++]->id()); |
| } |
| while (i < loop->exits_start_) { |
| PrintF(" B#%d", loop_tree_->loop_nodes_[i++]->id()); |
| } |
| while (i < loop->exits_end_) { |
| PrintF(" E#%d", loop_tree_->loop_nodes_[i++]->id()); |
| } |
| PrintF("\n"); |
| for (LoopTree::Loop* child : loop->children_) PrintLoop(child); |
| } |
| }; |
| |
| |
| LoopTree* LoopFinder::BuildLoopTree(Graph* graph, Zone* zone) { |
| LoopTree* loop_tree = |
| new (graph->zone()) LoopTree(graph->NodeCount(), graph->zone()); |
| LoopFinderImpl finder(graph, loop_tree, zone); |
| finder.Run(); |
| if (FLAG_trace_turbo_loop) { |
| finder.Print(); |
| } |
| return loop_tree; |
| } |
| |
| |
| Node* LoopTree::HeaderNode(Loop* loop) { |
| Node* first = *HeaderNodes(loop).begin(); |
| if (first->opcode() == IrOpcode::kLoop) return first; |
| DCHECK(IrOpcode::IsPhiOpcode(first->opcode())); |
| Node* header = NodeProperties::GetControlInput(first); |
| DCHECK_EQ(IrOpcode::kLoop, header->opcode()); |
| return header; |
| } |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |