Subzero: Improve LoopAnalyzer Interface

src/IceLoopAnalyzer.cpp

 //===- subzero/src/IceLoopAnalyzer.cpp - Loop Analysis --------------------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief Implements the loop analysis on the CFG.
 ///
 //===----------------------------------------------------------------------===//
 #include "IceLoopAnalyzer.h"
 
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 
+#include <algorithm>
+
 namespace Ice {
+class LoopAnalyzer {
+public:
+  LoopAnalyzer() = default;

[Jim Stichnoth, 2016/07/19 20:22:56]

Also delete or "default" the default copy ctor and assignment operator.

+  explicit LoopAnalyzer(Cfg *Func);
 
+  /// Use Tarjan's strongly connected components algorithm to identify outermost
+  /// to innermost loops. By deleting the head of the loop from the graph, inner
+  /// loops can be found. This assumes that the head node is not shared between
+  /// loops but instead all paths to the head come from 'continue' constructs.
+  ///
+  /// This only computes the loop nest depth within the function and does not
+  /// take into account whether the function was called from within a loop.
+  // TODO(ascull): this currently uses a extension of Tarjan's algorithm with
+  // is bounded linear. ncbray suggests another algorithm which is linear in
+  // practice but not bounded linear. I think it also finds dominators.
+  // http://lenx.100871.net/papers/loop-SAS.pdf
+
+  CfgVector<CfgUnorderedSet<SizeT>> getLoopBodies() { return Loops; }
+
+private:
+  void computeLoopNestDepth();
+
+  using IndexT = uint32_t;
+  static constexpr IndexT UndefinedIndex = 0;
+  static constexpr IndexT FirstDefinedIndex = 1;
+
+  // TODO(ascull): classify the other fields
+  class LoopNode {
+    LoopNode() = delete;
+    LoopNode operator=(const LoopNode &) = delete;
+
+  public:
+    explicit LoopNode(CfgNode *BB) : BB(BB) { reset(); }
+    LoopNode(const LoopNode &) = default;
+
+    void reset();
+
+    NodeList::const_iterator successorsEnd() const;
+    NodeList::const_iterator currentSuccessor() const { return Succ; }
+    void nextSuccessor() { ++Succ; }
+
+    void visit(IndexT VisitIndex) { Index = LowLink = VisitIndex; }
+    bool isVisited() const { return Index != UndefinedIndex; }
+    IndexT getIndex() const { return Index; }
+
+    void tryLink(IndexT NewLink) {
+      if (NewLink < LowLink)
+        LowLink = NewLink;
+    }
+    IndexT getLowLink() const { return LowLink; }
+
+    void setOnStack(bool NewValue = true) { OnStack = NewValue; }
+    bool isOnStack() const { return OnStack; }
+
+    void setDeleted() { Deleted = true; }
+    bool isDeleted() const { return Deleted; }
+
+    void incrementLoopNestDepth();
+    bool hasSelfEdge() const;
+
+    CfgNode *getNode() { return BB; }
+
+  private:
+    CfgNode *BB;
+    NodeList::const_iterator Succ;
+    IndexT Index;
+    IndexT LowLink;
+    bool OnStack;
+    bool Deleted = false;
+  };
+
+  using LoopNodeList = CfgVector<LoopNode>;
+  using LoopNodePtrList = CfgVector<LoopNode *>;
+
+  /// Process the node as part as part of Tarjan's algorithm and return either a
+  /// node to recurse into or nullptr when the node has been fully processed.
+  LoopNode *processNode(LoopNode &Node);
+
+  /// The function to analyze for loops.
+  Cfg *const Func;
+  /// A list of decorated nodes in the same order as Func->getNodes() which
+  /// means the node's index will also be valid in this list.
+  LoopNodeList AllNodes;
+  /// This is used as a replacement for the call stack.
+  LoopNodePtrList WorkStack;
+  /// Track which loop a node belongs to.
+  LoopNodePtrList LoopStack;
+  /// The index to assign to the next visited node.
+  IndexT NextIndex = FirstDefinedIndex;
+  /// The number of nodes which have been marked deleted. This is used to track
+  /// when the iteration should end.
+  LoopNodePtrList::size_type NumDeletedNodes = 0;
+
+  /// All the Loops, in descending order of size
+  CfgVector<CfgUnorderedSet<SizeT>> Loops;
+};
 void LoopAnalyzer::LoopNode::reset() {
   if (Deleted)
     return;
   Succ = BB->getOutEdges().begin();
   Index = LowLink = UndefinedIndex;
   OnStack = false;
 }
 
 NodeList::const_iterator LoopAnalyzer::LoopNode::successorsEnd() const {
   return BB->getOutEdges().end();
@@ skipping 104 matching lines @@
   // Reaching here means a loop has been found! It consists of the nodes on the
   // top of the stack, down until the current node being processed, Node, is
   // found.
   for (auto It = LoopStack.rbegin(); It != LoopStack.rend(); ++It) {
     (*It)->setOnStack(false);
     (*It)->incrementLoopNestDepth();
     // Remove the loop from the stack and delete the head node
     if (*It == &Node) {
       (*It)->setDeleted();
       ++NumDeletedNodes;
-      CfgVector<SizeT> LoopNodes;
+      CfgUnorderedSet<SizeT> LoopNodes;
       for (auto LoopIter = It.base() - 1; LoopIter != LoopStack.end();
            ++LoopIter) {
-        LoopNodes.push_back((*LoopIter)->getNode()->getIndex());
+        LoopNodes.insert((*LoopIter)->getNode()->getIndex());
       }
-      Loops[(*It)->getNode()->getIndex()] = LoopNodes;
+      Loops.push_back(LoopNodes);
       LoopStack.erase(It.base() - 1, LoopStack.end());
       break;
     }
   }
 
   return nullptr;
 }
+CfgVector<Loop> ComputeLoopInfo(Cfg *Func) {
+  auto LoopBodies = LoopAnalyzer(Func).getLoopBodies();
+
+  CfgVector<Loop> Loops;
+  Loops.reserve(LoopBodies.size());
+  std::sort(
+      LoopBodies.begin(), LoopBodies.end(),
+      [](const CfgUnorderedSet<SizeT> &A, const CfgUnorderedSet<SizeT> &B) {
+        return A.size() > B.size();
+      });
+  for (auto &LoopBody : LoopBodies) {
+    CfgNode *Header = nullptr;
+    bool IsSimpleLoop = true;
+    for (auto NodeIndex : LoopBody) {
+      CfgNode *Cur = Func->getNodes()[NodeIndex];
+      for (auto *Prev : Cur->getInEdges()) {
+        if (LoopBody.find(Prev->getIndex()) ==
+            LoopBody.end()) { // coming from outside
+          if (Header == nullptr) {
+            Header = Cur;
+          } else {
+            Header = nullptr;
+            IsSimpleLoop = false;
+            break;
+          }
+        }
+      }
+      if (!IsSimpleLoop) {
+        break;
+      }
+    }
+    if (!IsSimpleLoop)
+      continue; // To next potential loop
+
+    CfgNode *PreHeader = nullptr;
+    for (auto *Prev : Header->getInEdges()) {
+      if (LoopBody.find(Prev->getIndex()) == LoopBody.end()) {
+        if (PreHeader == nullptr) {
+          PreHeader = Prev;
+        } else {
+          PreHeader = nullptr;
+          break;
+        }
+      }
+    }
+
+    Loops.emplace_back(Header, PreHeader, LoopBody);
+  }
+  return Loops;
+}
 
 } // end of namespace Ice