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