Compute the loop nest depth of each CfgNode and weight Variables by it.

src/IceLoopAnalyzer.h

+//===- subzero/src/IceLoopAnalyzer.h - Loop Analysis ------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief This analysis identifies loops in the CFG.
+//===----------------------------------------------------------------------===//
+
+#ifndef SUBZERO_SRC_ICELOOPANALYZER_H
+#define SUBZERO_SRC_ICELOOPANALYZER_H
+
+#include "IceDefs.h"
+
+namespace Ice {
+
+/// Analyze a function's CFG for loops. The CFG must not change during the
+/// lifetime of this object.
+class LoopAnalyzer {
+  LoopAnalyzer() = delete;
+  LoopAnalyzer(const LoopAnalyzer &) = delete;
+  LoopAnalyzer &operator=(const LoopAnalyzer &) = delete;
+
+public:
+  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.
+  void computeLoopNestDepth();
+
+private:
+  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();
+
+  private:
+    CfgNode *BB;
+    NodeList::const_iterator Succ;
+    IndexT Index;
+    IndexT LowLink;
+    bool OnStack;
+    bool Deleted = false;
+  };
+
+  using LoopNodeList = std::vector<LoopNode, CfgLocalAllocator<LoopNode>>;
+  using LoopNodePtrList =
+      std::vector<LoopNode *, CfgLocalAllocator<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 fuction 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;
+};
+
+} // end of namespace Ice
+
+#endif //  SUBZERO_SRC_ICELOOPANALYZER_H