1aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull//===- subzero/src/IceLoopAnalyzer.cpp - Loop Analysis --------------------===// 2aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull// 3aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull// The Subzero Code Generator 4aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull// 5aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull// This file is distributed under the University of Illinois Open Source 6aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull// License. See LICENSE.TXT for details. 7aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull// 8aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull//===----------------------------------------------------------------------===// 9aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull/// 10aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull/// \file 1192a6e5b08ec68e7076d637ebc680da2fcc346a00Jim Stichnoth/// \brief Implements the loop analysis on the CFG. 12aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull/// 13aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull//===----------------------------------------------------------------------===// 14aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull#include "IceLoopAnalyzer.h" 15aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 16aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull#include "IceCfg.h" 17aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull#include "IceCfgNode.h" 18aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 19adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee#include <algorithm> 20adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 21aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scullnamespace Ice { 22adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjeeclass LoopAnalyzer { 23adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjeepublic: 24adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee explicit LoopAnalyzer(Cfg *Func); 25adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 26adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// Use Tarjan's strongly connected components algorithm to identify outermost 27adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// to innermost loops. By deleting the head of the loop from the graph, inner 28adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// loops can be found. This assumes that the head node is not shared between 29adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// loops but instead all paths to the head come from 'continue' constructs. 30adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// 31adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// This only computes the loop nest depth within the function and does not 32adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// take into account whether the function was called from within a loop. 33adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee // TODO(ascull): this currently uses a extension of Tarjan's algorithm with 34adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee // is bounded linear. ncbray suggests another algorithm which is linear in 35adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee // practice but not bounded linear. I think it also finds dominators. 36adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee // http://lenx.100871.net/papers/loop-SAS.pdf 37adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 38adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee CfgVector<CfgUnorderedSet<SizeT>> getLoopBodies() { return Loops; } 39adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 40adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjeeprivate: 41adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopAnalyzer() = delete; 42adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopAnalyzer(const LoopAnalyzer &) = delete; 43adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopAnalyzer &operator=(const LoopAnalyzer &) = delete; 44adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee void computeLoopNestDepth(); 45adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 46adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee using IndexT = uint32_t; 47adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee static constexpr IndexT UndefinedIndex = 0; 48adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee static constexpr IndexT FirstDefinedIndex = 1; 49adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 50adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee // TODO(ascull): classify the other fields 51adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee class LoopNode { 52adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopNode() = delete; 53adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopNode operator=(const LoopNode &) = delete; 54adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 55adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee public: 56adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee explicit LoopNode(CfgNode *BB) : BB(BB) { reset(); } 57adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopNode(const LoopNode &) = default; 58adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 59adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee void reset(); 60adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 61adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee NodeList::const_iterator successorsEnd() const; 62adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee NodeList::const_iterator currentSuccessor() const { return Succ; } 63adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee void nextSuccessor() { ++Succ; } 64adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 65adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee void visit(IndexT VisitIndex) { Index = LowLink = VisitIndex; } 66adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee bool isVisited() const { return Index != UndefinedIndex; } 67adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee IndexT getIndex() const { return Index; } 68adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 69adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee void tryLink(IndexT NewLink) { 70adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee if (NewLink < LowLink) 71adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LowLink = NewLink; 72adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } 73adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee IndexT getLowLink() const { return LowLink; } 74adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 75adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee void setOnStack(bool NewValue = true) { OnStack = NewValue; } 76adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee bool isOnStack() const { return OnStack; } 77adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 78adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee void setDeleted() { Deleted = true; } 79adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee bool isDeleted() const { return Deleted; } 80adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 81adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee void incrementLoopNestDepth(); 82adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee bool hasSelfEdge() const; 83aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 84adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee CfgNode *getNode() { return BB; } 85adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 86adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee private: 87adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee CfgNode *BB; 88adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee NodeList::const_iterator Succ; 89adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee IndexT Index; 90adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee IndexT LowLink; 91adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee bool OnStack; 92adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee bool Deleted = false; 93adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee }; 94adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 95adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee using LoopNodeList = CfgVector<LoopNode>; 96adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee using LoopNodePtrList = CfgVector<LoopNode *>; 97adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 98adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// Process the node as part as part of Tarjan's algorithm and return either a 99adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// node to recurse into or nullptr when the node has been fully processed. 100adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopNode *processNode(LoopNode &Node); 101adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 102adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// The function to analyze for loops. 103adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee Cfg *const Func; 104adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// A list of decorated nodes in the same order as Func->getNodes() which 105adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// means the node's index will also be valid in this list. 106adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopNodeList AllNodes; 107adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// This is used as a replacement for the call stack. 108adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopNodePtrList WorkStack; 109adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// Track which loop a node belongs to. 110adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopNodePtrList LoopStack; 111adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// The index to assign to the next visited node. 112adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee IndexT NextIndex = FirstDefinedIndex; 113adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// The number of nodes which have been marked deleted. This is used to track 114adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// when the iteration should end. 115adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopNodePtrList::size_type NumDeletedNodes = 0; 116adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 117adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee /// All the Loops, in descending order of size 118adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee CfgVector<CfgUnorderedSet<SizeT>> Loops; 119adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee}; 120aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scullvoid LoopAnalyzer::LoopNode::reset() { 121aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull if (Deleted) 122aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull return; 123aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull Succ = BB->getOutEdges().begin(); 124aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull Index = LowLink = UndefinedIndex; 125aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull OnStack = false; 126aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull} 127aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 128aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew ScullNodeList::const_iterator LoopAnalyzer::LoopNode::successorsEnd() const { 129aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull return BB->getOutEdges().end(); 130aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull} 131aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 132aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scullvoid LoopAnalyzer::LoopNode::incrementLoopNestDepth() { 133aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull BB->incrementLoopNestDepth(); 134aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull} 135aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 136f49b2396547a7cf3b8a9b5198f62cbc545c2572cJim Stichnothbool LoopAnalyzer::LoopNode::hasSelfEdge() const { 137f49b2396547a7cf3b8a9b5198f62cbc545c2572cJim Stichnoth for (CfgNode *Succ : BB->getOutEdges()) { 138f49b2396547a7cf3b8a9b5198f62cbc545c2572cJim Stichnoth if (Succ == BB) 139f49b2396547a7cf3b8a9b5198f62cbc545c2572cJim Stichnoth return true; 140f49b2396547a7cf3b8a9b5198f62cbc545c2572cJim Stichnoth } 141f49b2396547a7cf3b8a9b5198f62cbc545c2572cJim Stichnoth return false; 142f49b2396547a7cf3b8a9b5198f62cbc545c2572cJim Stichnoth} 143f49b2396547a7cf3b8a9b5198f62cbc545c2572cJim Stichnoth 1448f98cdd255a1e1f07032e660d928a69a4ebece5bJim StichnothLoopAnalyzer::LoopAnalyzer(Cfg *Fn) : Func(Fn) { 145aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull const NodeList &Nodes = Func->getNodes(); 146aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 147aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // Allocate memory ahead of time. This is why a vector is used instead of a 148aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // stack which doesn't support reserving (or bulk erasure used below). 149aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull AllNodes.reserve(Nodes.size()); 150aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull WorkStack.reserve(Nodes.size()); 151aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull LoopStack.reserve(Nodes.size()); 152aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 153aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // Create the LoopNodes from the function's CFG 154aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull for (CfgNode *Node : Nodes) 155aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull AllNodes.emplace_back(Node); 156f47d520c1a91bb029d73a5a5f7c0e416ed763f23Manasij Mukherjee computeLoopNestDepth(); 157aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull} 158aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 159aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scullvoid LoopAnalyzer::computeLoopNestDepth() { 160aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull assert(AllNodes.size() == Func->getNodes().size()); 161aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull assert(NextIndex == FirstDefinedIndex); 162aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull assert(NumDeletedNodes == 0); 163aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 164aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull while (NumDeletedNodes < AllNodes.size()) { 165aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // Prepare to run Tarjan's 166aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull for (LoopNode &Node : AllNodes) 167aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull Node.reset(); 168aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 169aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull assert(WorkStack.empty()); 170aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull assert(LoopStack.empty()); 171aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 172aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull for (LoopNode &Node : AllNodes) { 173aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull if (Node.isDeleted() || Node.isVisited()) 174aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull continue; 175aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 176aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull WorkStack.push_back(&Node); 177aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 178aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull while (!WorkStack.empty()) { 179aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull LoopNode &WorkNode = *WorkStack.back(); 180aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull if (LoopNode *Succ = processNode(WorkNode)) 181aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull WorkStack.push_back(Succ); 182aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull else 183aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull WorkStack.pop_back(); 184aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull } 185aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull } 186aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull } 187aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull} 188aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 189aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew ScullLoopAnalyzer::LoopNode * 190aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew ScullLoopAnalyzer::processNode(LoopAnalyzer::LoopNode &Node) { 191aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull if (!Node.isVisited()) { 192aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull Node.visit(NextIndex++); 193aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull LoopStack.push_back(&Node); 194aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull Node.setOnStack(); 195aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull } else { 196aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // Returning to a node after having recursed into Succ so continue 197aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // iterating through successors after using the Succ.LowLink value that was 198aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // computed in the recursion. 199aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull LoopNode &Succ = AllNodes[(*Node.currentSuccessor())->getIndex()]; 200aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull Node.tryLink(Succ.getLowLink()); 201aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull Node.nextSuccessor(); 202aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull } 203aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 204aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // Visit the successors and recurse into unvisited nodes. The recursion could 205aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // cause the iteration to be suspended but it will resume as the stack is 206aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // unwound. 207aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull auto SuccEnd = Node.successorsEnd(); 208aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull for (; Node.currentSuccessor() != SuccEnd; Node.nextSuccessor()) { 209aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull LoopNode &Succ = AllNodes[(*Node.currentSuccessor())->getIndex()]; 210aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 211aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull if (Succ.isDeleted()) 212aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull continue; 213aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 214aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull if (!Succ.isVisited()) 215aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull return &Succ; 216aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull else if (Succ.isOnStack()) 217aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull Node.tryLink(Succ.getIndex()); 218aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull } 219aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 220aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull if (Node.getLowLink() != Node.getIndex()) 221aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull return nullptr; 222aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 223aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // Single node means no loop in the CFG 224aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull if (LoopStack.back() == &Node) { 225aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull LoopStack.back()->setOnStack(false); 226f49b2396547a7cf3b8a9b5198f62cbc545c2572cJim Stichnoth if (Node.hasSelfEdge()) 227f49b2396547a7cf3b8a9b5198f62cbc545c2572cJim Stichnoth LoopStack.back()->incrementLoopNestDepth(); 228aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull LoopStack.back()->setDeleted(); 229aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull ++NumDeletedNodes; 230aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull LoopStack.pop_back(); 231aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull return nullptr; 232aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull } 233aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 23457e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // Reaching here means a loop has been found! It consists of the nodes on the 23557e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // top of the stack, down until the current node being processed, Node, is 23657e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // found. 237aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull for (auto It = LoopStack.rbegin(); It != LoopStack.rend(); ++It) { 238aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull (*It)->setOnStack(false); 239aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull (*It)->incrementLoopNestDepth(); 240aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull // Remove the loop from the stack and delete the head node 241aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull if (*It == &Node) { 242aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull (*It)->setDeleted(); 243aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull ++NumDeletedNodes; 244adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee CfgUnorderedSet<SizeT> LoopNodes; 245f47d520c1a91bb029d73a5a5f7c0e416ed763f23Manasij Mukherjee for (auto LoopIter = It.base() - 1; LoopIter != LoopStack.end(); 246f47d520c1a91bb029d73a5a5f7c0e416ed763f23Manasij Mukherjee ++LoopIter) { 247adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopNodes.insert((*LoopIter)->getNode()->getIndex()); 248f47d520c1a91bb029d73a5a5f7c0e416ed763f23Manasij Mukherjee } 249adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee Loops.push_back(LoopNodes); 250aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull LoopStack.erase(It.base() - 1, LoopStack.end()); 251aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull break; 252aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull } 253aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull } 254aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 255aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull return nullptr; 256aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull} 257adf352bcfc24b22b75945ed45b1024943af3a690Manasij MukherjeeCfgVector<Loop> ComputeLoopInfo(Cfg *Func) { 258adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee auto LoopBodies = LoopAnalyzer(Func).getLoopBodies(); 259adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 260adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee CfgVector<Loop> Loops; 261adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee Loops.reserve(LoopBodies.size()); 262adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee std::sort( 263adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopBodies.begin(), LoopBodies.end(), 264adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee [](const CfgUnorderedSet<SizeT> &A, const CfgUnorderedSet<SizeT> &B) { 265adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee return A.size() > B.size(); 266adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee }); 267adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee for (auto &LoopBody : LoopBodies) { 268adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee CfgNode *Header = nullptr; 269adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee bool IsSimpleLoop = true; 270adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee for (auto NodeIndex : LoopBody) { 271adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee CfgNode *Cur = Func->getNodes()[NodeIndex]; 272adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee for (auto *Prev : Cur->getInEdges()) { 273adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee if (LoopBody.find(Prev->getIndex()) == 274adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee LoopBody.end()) { // coming from outside 275adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee if (Header == nullptr) { 276adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee Header = Cur; 277adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } else { 278adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee Header = nullptr; 279adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee IsSimpleLoop = false; 280adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee break; 281adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } 282adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } 283adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } 284adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee if (!IsSimpleLoop) { 285adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee break; 286adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } 287adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } 288adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee if (!IsSimpleLoop) 289adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee continue; // To next potential loop 290adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 291adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee CfgNode *PreHeader = nullptr; 292adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee for (auto *Prev : Header->getInEdges()) { 293adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee if (LoopBody.find(Prev->getIndex()) == LoopBody.end()) { 294adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee if (PreHeader == nullptr) { 295adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee PreHeader = Prev; 296adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } else { 297adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee PreHeader = nullptr; 298adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee break; 299adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } 300adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } 301adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } 302adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee 303adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee Loops.emplace_back(Header, PreHeader, LoopBody); 304adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee } 305adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee return Loops; 306adf352bcfc24b22b75945ed45b1024943af3a690Manasij Mukherjee} 307aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull 308aa6c109366408d066c4ac9e22c8c0ded6d18092fAndrew Scull} // end of namespace Ice 309