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

src/IceCfg.cpp

 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 44 matching lines @@
 
 Cfg::~Cfg() { assert(ICE_TLS_GET_FIELD(CurrentCfg) == nullptr); }
 
 void Cfg::setError(const IceString &Message) {
   HasError = true;
   ErrorMessage = Message;
 }
 
 CfgNode *Cfg::makeNode() {
   SizeT LabelIndex = Nodes.size();
   CfgNode *Node = CfgNode::create(this, LabelIndex);

[Jim Stichnoth, 2015/09/01 22:17:37]

May want to document here that LoopNestDepth may not be valid if makeNode() runs
after computeLoopNestDepth().

[ascull, 2015/09/03 19:52:37]

Done.

   Nodes.push_back(Node);
   return Node;
 }
 
 void Cfg::swapNodes(NodeList &NewNodes) {
   Nodes.swap(NewNodes);
   for (SizeT I = 0, NumNodes = getNumNodes(); I < NumNodes; ++I)
     Nodes[I]->resetIndex(I);
 }
 
@@ skipping 379 matching lines @@
 
 // Compute the stack frame layout.
 void Cfg::genFrame() {
   TimerMarker T(TimerStack::TT_genFrame, this);
   getTarget()->addProlog(Entry);
   for (CfgNode *Node : Nodes)
     if (Node->getHasReturn())
       getTarget()->addEpilog(Node);
 }
 
-// This is a lightweight version of live-range-end calculation.  Marks
-// the last use of only those variables whose definition and uses are
-// completely with a single block.  It is a quick single pass and
-// doesn't need to iterate until convergence.
+// Use Tarjn's strongly connected components algorithm to identify outermost to

[jvoung (off chromium), 2015/09/01 18:56:18]

Tarjan's

[ascull, 2015/09/03 19:52:37]

Done.

+// 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 Cfg::computeLoopNestDepth() {

[Jim Stichnoth, 2015/09/01 22:17:37]

Add a TimerMarker here (and add a new marker type in IceTimerTree.def).

[ascull, 2015/09/03 19:52:37]

Done.

+  using index_t = uint32_t;

[Jim Stichnoth, 2015/09/01 22:17:37]

Type names should be capitalized per LLVM coding style.

[ascull, 2015/09/03 19:52:37]

Done.

+  constexpr index_t UndefinedIndex = 0;
+
+  struct LoopNode {

[Jim Stichnoth, 2015/09/01 22:17:37]

I think if you are defining methods, you should call it a class instead of
struct.

[ascull, 2015/09/03 19:52:37]

Done.

+    LoopNode() = delete;
+    LoopNode operator=(const LoopNode &) = delete;
+
+    explicit LoopNode(CfgNode *BB) : BB(BB) {}
+    LoopNode(const LoopNode &) = default;
+
+    void reset() {
+      Succ = BB->getOutEdges().begin();
+      Index = LowLink = UndefinedIndex;
+      OnStack = false;
+    }
+
+    void visit(index_t VisitIndex) { Index = LowLink = VisitIndex; }
+    bool isVisited() const { return Index != UndefinedIndex; }
+
+    void setDeleted() { deleted = true; }
+    bool isDeleted() const { return deleted; }
+
+    CfgNode *BB;
+    NodeList::const_iterator Succ;

[Jim Stichnoth, 2015/09/01 22:17:37]

Initialize members in the ctor or in the same way as "deleted"

[ascull, 2015/09/03 19:52:37]

Done.

+    index_t Index;
+    index_t LowLink;
+    bool OnStack;
+    bool deleted = false;

[jvoung (off chromium), 2015/09/01 18:56:17]

capitalize deleted to follow code style

[ascull, 2015/09/03 19:52:37]

Done.

+  };
+
+  // Create a collection of decorated nodes in the same order as Nodes which
+  // means the node's index will be valid.
+  std::vector<LoopNode, CfgLocalAllocator<LoopNode>> AllNodes;
+  // This is used as a replacement for the call stack
+  std::vector<LoopNode *, CfgLocalAllocator<LoopNode *>> WorkStack;
+  // Track which loop a node belongs to
+  std::vector<LoopNode *, CfgLocalAllocator<LoopNode *>> LoopStack;
+
+  // Allocate memory ahead of time. This is why a vector is used instead of a
+  // stack which doesn not support reserving (or bulk erasure used below).

[jvoung (off chromium), 2015/09/01 18:56:18]

doesn -> doesn't

[ascull, 2015/09/03 19:52:37]

Done.

+  AllNodes.reserve(Nodes.size());
+  WorkStack.reserve(Nodes.size());
+  LoopStack.reserve(Nodes.size());
+
+  // Load in initial data
+  for (CfgNode *Node : Nodes)
+    AllNodes.emplace_back(Node);
+
+  size_t NumDeletedNodes = 0;

[Jim Stichnoth, 2015/09/01 22:17:37]

SizeT

or, if you object to that,
std::vector<LoopNode, CfgLocalAllocator<LoopNode>>::size_type
:)

[ascull, 2015/09/03 19:52:37]

Done.

+
+  while (NumDeletedNodes < AllNodes.size()) {
+    // Prepare to run Tarjan's
+    index_t NextIndex = 1;

[jvoung (off chromium), 2015/09/01 18:56:18]

nit: How about UndefinedIndex + 1, to ensure the initial value is different?  1
is fine too.

[ascull, 2015/09/03 19:52:37]

Done.

+    for (LoopNode &Node : AllNodes)
+      Node.reset();

[jvoung (off chromium), 2015/09/01 18:56:18]

Wonder if you should add an Ice timer for this whole function to profile it.
Tarjan's is O(V+E), but this resets some number of times depending on the loop
nesting.

[ascull, 2015/09/03 19:52:37]

Done.

+
+    assert(WorkStack.empty());
+    assert(LoopStack.empty());
+
+    for (LoopNode &Node : AllNodes) {
+      if (Node.isDeleted() || Node.isVisited())
+        continue;
+
+      WorkStack.push_back(&Node);
+
+    continue_work_loop:
+      while (!WorkStack.empty()) {
+        LoopNode &WorkNode = *WorkStack.back();
+        WorkStack.pop_back();
+
+        if (!WorkNode.isVisited()) {
+          WorkNode.visit(NextIndex++);
+          LoopStack.push_back(&WorkNode);
+          WorkNode.OnStack = true;
+        } else {
+          // Returning to a node after having recursed into Succ so continue
+          // iterating through successors after using the Succ.LowLink value
+          // that was computed in the recursion.
+          LoopNode &Succ = AllNodes[(*WorkNode.Succ)->getIndex()];
+          WorkNode.LowLink = std::min(WorkNode.LowLink, Succ.LowLink);
+          ++WorkNode.Succ;
+        }
+
+        // Visit the successors and recurse into unvisited nodes. The recursion
+        // could cause the iteration to be suspended but it will resume as the
+        // stack is unwound.
+        auto SuccEnd = WorkNode.BB->getOutEdges().end();
+        for (; WorkNode.Succ != SuccEnd; ++WorkNode.Succ) {
+          LoopNode &Succ = AllNodes[(*WorkNode.Succ)->getIndex()];
+
+          if (Succ.isDeleted())
+            continue;
+
+          if (!Succ.isVisited()) {
+            WorkStack.insert(WorkStack.end(), {&WorkNode, &Succ});
+            goto continue_work_loop; // continue outer loop

[jvoung (off chromium), 2015/09/01 18:56:18]

You might be able to get away without a goto, if you make the loop body a
function, and then return; instead of goto.

Not sure how many parameters you'll have to pass around though, so that may be
messy. On the other hand, the loop body is pretty deeply nested so that may be a
reason to separate it out into a function.

[ascull, 2015/09/03 19:52:37]

I refactored the loop stuff out into it's own class and made this change in the
process.

+          } else if (Succ.OnStack) {
+            WorkNode.LowLink = std::min(WorkNode.LowLink, Succ.Index);
+          }
+        }
+
+        // Check for a loop being closed
+        if (WorkNode.LowLink == WorkNode.Index) {
+          // Single node loops mean no loop in a pure CFG. After lowering there
+          // may be reentrancy but we ignore that here.

[jvoung (off chromium), 2015/09/01 18:56:18]

What do you mean by reentrancy here? Branches from local labels?

[ascull, 2015/09/03 19:52:37]

That is what I meant, although it isn't a useful comment any more as this
analysis take place before lowering.

+          if (LoopStack.back() == &WorkNode) {
+            LoopStack.back()->OnStack = false;
+            LoopStack.back()->setDeleted();
+            ++NumDeletedNodes;
+            LoopStack.pop_back();
+            continue;
+          }
+
+          // 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, WorkNode, is found.
+          for (auto It = LoopStack.rbegin(); It != LoopStack.rend(); ++It) {
+            (*It)->OnStack = false;
+            (*It)->BB->incrementLoopNestDepth();
+            // Remove the loop from the stack and delete the head node
+            if (*It == &WorkNode) {
+              (*It)->setDeleted();
+              ++NumDeletedNodes;
+              LoopStack.erase(It.base() - 1, LoopStack.end());
+              break;
+            }
+          }
+        }
+      }
+    }
+  }
+}
+
+// This is a lightweight version of live-range-end calculation.  Marks the last
+// use of only those variables whose definition and uses are completely with a
+// single block.  It is a quick single pass and doesn't need to iterate until
+// convergence.
 void Cfg::livenessLightweight() {
   TimerMarker T(TimerStack::TT_livenessLightweight, this);
   getVMetadata()->init(VMK_Uses);
   for (CfgNode *Node : Nodes)
     Node->livenessLightweight();
 }
 
 void Cfg::liveness(LivenessMode Mode) {
   TimerMarker T(TimerStack::TT_liveness, this);
   Live.reset(new Liveness(this, Mode));
@@ skipping 120 matching lines @@
             Str << " live range " << Var->getLiveRange() << "\n";
           }
         }
       }
     }
   }
   return Valid;
 }
 
 void Cfg::contractEmptyNodes() {
-  // If we're decorating the asm output with register liveness info,
-  // this information may become corrupted or incorrect after
-  // contracting nodes that contain only redundant assignments.  As
-  // such, we disable this pass when DecorateAsm is specified.  This
-  // may make the resulting code look more branchy, but it should have
-  // no effect on the register assignments.
+  // If we're decorating the asm output with register liveness info, this
+  // information may become corrupted or incorrect after contracting nodes that
+  // contain only redundant assignments. As such, we disable this pass when
+  // DecorateAsm is specified. This may make the resulting code look more
+  // branchy, but it should have no effect on the register assignments.
   if (Ctx->getFlags().getDecorateAsm())
     return;
   for (CfgNode *Node : Nodes) {
     Node->contractIfEmpty();
   }
 }
 
 void Cfg::doBranchOpt() {
   TimerMarker T(TimerStack::TT_doBranchOpt, this);
   for (auto I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
@@ skipping 146 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice