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

src/IceLoopAnalyzer.h

Index: src/IceLoopAnalyzer.h
diff --git a/src/IceLoopAnalyzer.h b/src/IceLoopAnalyzer.h
new file mode 100644
index 0000000000000000000000000000000000000000..8b599da7d98eed49db13556464bf8b2b44fd9581
--- /dev/null
+++ b/src/IceLoopAnalyzer.h
@@ -0,0 +1,113 @@
+//===- 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 the functions CFG for loops. The CFG must not change during the

[Jim Stichnoth, 2015/09/03 21:35:09]

Drop the word "functions", or at least change to "function's".

[ascull, 2015/09/03 22:47:13]

Done.

+/// lifetine of this object.

[Jim Stichnoth, 2015/09/03 21:35:09]

lifetime

[ascull, 2015/09/03 22:47:13]

Done.

+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), Deleted(false) {}

[Jim Stichnoth, 2015/09/03 21:35:09]

Use "bool Deleted = false;" below instead of "Deleted(false)" here.

[ascull, 2015/09/03 22:47:13]

Done.

+    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;

[Jim Stichnoth, 2015/09/03 21:35:09]

Make sure Succ/Index/LowLink/OnStack get initialized in the ctor.

[ascull, 2015/09/03 22:47:13]

Done.

[Jim Stichnoth, 2015/09/03 23:23:30]

I don't see this in the latest patchset.  To be clear, I think something like
this could be done:

explicit LoopNode(CfgNode *BB) : BB(BB), Succ(BB->getOutEdges().begin()) {}
...
IndexT Index = 0;
IndexT LowLink = 0;
bool OnStack = false;
bool Delete = false;

(maybe it's OK to ignore Succ initialization due to its complexity)

[ascull, 2015/09/04 00:23:51]

I call reset() in the constructor which initialized them. Is that ok or do they
need to be more strictly initialized?

[Jim Stichnoth, 2015/09/04 00:47:26]

Ah, sorry, I missed the reset() call.

+    IndexT Index;
+    IndexT LowLink;
+    bool OnStack;
+    bool Deleted;
+  };
+
+  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 *Func;

[Jim Stichnoth, 2015/09/03 21:35:09]

Maybe Cfg *const Func;

[ascull, 2015/09/03 22:47:13]

Done.

+  /// 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;

[Jim Stichnoth, 2015/09/03 21:35:09]

Initialize NextIndex in the ctor

[ascull, 2015/09/03 22:47:13]

Done.

+  /// The number of nodes which have been marked deleted. This is used to track
+  /// when the iteration should end.
+  LoopNodePtrList::size_type NumDeletedNodes;
+};
+
+} // end of namespace Ice
+
+#endif //  SUBZERO_SRC_ICELOOPANALYZER_H