[LV][LoopInfo] Add irreducible CFG detection for outer loops

[dcaballe]

Summary

Context

We are planning to introduce a series of patches that aim to extend LV for *explicit* outer loop vectorization support, using the VPlan infrastructure ---- starting from trivial outer loops and then build up functionality to deal with more complex outer loops. This can be further extended to perform outer loop auto-vectorization by additional work on legality and cost modeling, but for the sake of simplicity, that aspect is outside of the scope of this patch series. Further context in the RFC: http://lists.llvm.org/pipermail/llvm-dev/2017-December/119523.html

This patch is the first installment of Patch Series #1. Patch Series #1 focuses on bringing to LV the initial functionality to detect, construct VPlans and generate code out of them for a well limited set of trivial outer loops that have been annotated to be explicitly vectorized. In particular, Patch Series #1 will add support for explicit vectorization of trivial outer loops where:

1. inner loops are uniform, i.e., they are trivially lock-step among all vector elements and,
2. there are no branches inside the outer loop body other than a single loop latch and a zero-trip-test per inner loop.

The following loop is an example of a supported outer loop:

#pragma clang loop vectorize(enable) vectorize_width(4)
for (i=0;i<N;i++){
  // no branches here
  for (j=0;j<loop_invariant_value; j++){
    // no branches here
  }
  // no branches here
}

In order to achieve these goals, Patch Series #1 will introduce the following functionality:

1. Restrictive detection of supported loop nests, including inner loop uniformity check analysis.
2. Initial VPlan construction for outer loops.
3. VPlan-based vector code generation for outer loops.

Patch Series #1. Sub-patch #1

This patch adds support for detecting outer loops with irreducible control flow in LV. Current detection uses SCCs and only works for innermost loops. This patch adds a utility function that works on any CFG, given its RPO traversal and its LoopInfoBase. This function is a generalization of ‘isIrreducibleCFG’ from lib/CodeGen/ShrinkWrap.cpp. The code in lib/CodeGen/ShrinkWrap.cpp is also updated to use the new generic utility function.

I would appreciate your feedback.

Thanks,
Diego

[dcaballe]

Adding full context to the patch (sorry).

[dcaballe]

Ping :)

If you are OK with the proposed algorithm, I would appreciate feedback on where to refactor the 'isIrreducibleCFG' utility function for Loop and MachineLoop.
As I mentioned, LoopBase could be a good candidate. This utility function would be similar to isRecursivelyLCSSAForm implemented in Loop class.
Does it sound reasonable?

Thanks!
Diego

[fhahn]

In D40874#954567, @dcaballe wrote:

If you are OK with the proposed algorithm, I would appreciate feedback on where to refactor the 'isIrreducibleCFG' utility function for Loop and MachineLoop.
As I mentioned, LoopBase could be a good candidate. This utility function would be similar to isRecursivelyLCSSAForm implemented in Loop class.
Does it sound reasonable?

I think moving this to LoopBase makes sense, if there are multiple users for this function, rather than duplicating it. For the naming, I would call it something like containsIrreducibleCFG, to make it clear that it checks if the loop body contains irreducible CFG (also make that clear in the comment), rather than the loop itself is irreducible.

[dcaballe]

Thanks for the feedback, Florian, and sorry for the delay. I'm about to post a new version.

Diego.

[dcaballe]

The refactoring of a generic utility function to detect irreducible CFG required a little more work because the other user, ShrinkWrap (D41886), needed this functionality at Function level and not at Loop level as we need it in LV. This new patch adds such a utility function which works on any CFG given its RPO traversal and its LoopInfoBase. This function is a generalization of ‘isIrreducibleCFG’ in lib/CodeGen/ShrinkWrap.cpp. It should be generic enough to deal with any CFG in LLVM that is supported by LoopInfoBase. RPO traversal is a function parameter which would allow to reuse RPO traversals that were previously computed for other purposes.

If you are OK with this approach, there are two questions that should be discussed as part of the review:

1. Location of this utility function: I placed this function in include/llvm/Analysis/CFG.h. I would be happy to move it somewhere else if you think it’s more appropriate.
2. Removing or preserving existing SCC-based ‘hasCyclesInLoopBody’ function for inner loop cases: Since the new generic utility function works for inner and outer loops, I think that ‘hasCyclesInLoopBody’ is no longer necessary. I think that computing and traversing the SCCs of an inner loop body without back-edges (1 SCC per BasicBlock) is, at least, as expensive in practice as computing and traversing the inner loop body in RPO. I measured the compile time of both approaches in a couple of benchmarks suites and I couldn’t observe any performance difference.

D41886 updates ShrinkWrap to use this generic utility function.

Please, let me know what you think.
Thanks,
Diego.

[dcaballe]

Merging D41886 with this patch, as requested in D41886.

[dcaballe]

Ping :)
Patch #2 was also posted: D42447

[fhahn]

Thanks Diego, LGTM. Sorry for the long delay! Please wait with committing a few days, to give other people a little bit more time to voice additional concerns.

lib/Transforms/Vectorize/LoopVectorize.cpp

59 ↗

(On Diff #129972)

Can this include be removed now?

[fhahn]

Please update the commit message with the updates from your comment :)

[dcaballe]

Thanks for reviewing this patch, Florian.

• Rebasing patch to ToT and addressing the SCCIterator.h comment (good catch!)
• Updating the message in "Sub-patch #1" section so that it can be used as commit message.

Please, Florian, feel free to commit this patch whenever you think it's appropriate. I still don't have commit access.

Thanks,
Diego

[lebedev.ri]

Is this NFC?
If not, would it be possible to have some test coverage for these changes?

[dcaballe]

Yes, this is NFC. Since this is kind of a refactoring, there are already tests for the 'containsIrreducibleCFG' utility function in ShrinkWarp and LV passes.
I'm introducing more tests targeting outer loops in the subsequent patch (D42447), which starts to enable the outer loop functionality in LV.
At this point, LV skips all the outer loops so I cannot do any testing in that regard.

[• dberlin]

Hey, can you help me understand the algorithm?
I don't have a good feel for the invariants you expect going in.
It just says "it works on anything given loop info".
IE What info you expect the loopinfo to provide vs the topo ordering.

There are lots of ways to test for reducibility, and it's unclear which you are using here (and why that should be used if the loop info isn't around, for example).

To make it simple, let's take the canonical irreducible graph

A->B
A->C
B->C
C->B
C->D

     A
 /        \
B<- -> C
             |
             D

What do you expect to happen here? What do you expect the loopinfo to provide vs the RPO.

The algorithms i'm familiar with to detect irreducibility don't need the loop info:

1. T1/T2
2. Tarjan's algorithm, which is basically (this is borrowed from eric stolz)

test_dom(a,b) returns TRUE if a dominates b
push( v ) pushes v onto a reverse topologically-sorted stack


Invoke: top_sort( entry node )


top_sort( node v ) {
      mark_visited( v );
      Visit all successors s of v {
              if( mark_visited( s ) && !pushed( s ) && !test_dom( s, v ) ) {
                          Irreducible_Graph = TRUE;
                          Exit -- no need to continue now!
              }
              if( !mark_visited( s ) )
                          top_sort( s );
      }
      push( v );
}

3. (another variant of tarjan's) Build a DFST, remove the back edges, see if the result is acylic.

It's true you can use loop info, but given the dom test is O(1) i'm not sure why it's worth computing to test irreducibility, especially if you are doing an RPO computation anyway.
Can you help me understand the algorithm being used here and why?

[dcaballe]

Hi Daniel,

thanks for the detailed response!

The main goal of this patch is to extend the current irreducibility detection in LV, based on SCCs explicitly built for that purpose, to work on outer loops. We found the algorithm in ShrinkWrap and decided to generalize it to promote and reuse existing code in LLVM instead of re-implementing a LV-specific version.

can you help me understand the algorithm?
IE What info you expect the loopinfo to provide vs the topo ordering.

LoopInfo analysis is “indirectly” computing CFG irreducibility by detecting irreducible loops and leaving them out of the loop forest. In the proposed algorithm, LoopInfo provides information about (already computed) reducible loop backedges. When a backedge is found during the CFG traversal, the algorithm checks that the backedge is one of the reducible backedges in LoopInfo. Otherwise, the CFG is irreducible. This logic is in function 'isProperBackedge'.

What do you expect to happen here? What do you expect the loopinfo to provide vs the RPO.

For this example, LoopInfo wouln't contain any loop, so the algorithm will return that the CFG is irreducible when checking the B <- -> C backedge.

It's true you can use loop info, but given the dom test is O(1) i'm not sure why it's worth computing to test irreducibility, especially if you are doing an RPO computation anyway.

Please, note that this patch is not intended to provide the best irreducibility algorithm for any arbitrary client. In both ShrinkWrap and LV, LoopInfo is an already required analysis. The rationale behind the proposed algorithm is that we don't want to compute irreducibility detection again when this information is already available in LoopInfo. This keeps the algorithm simple. I agree that the current documentation in 'containsIrreducibleCFG' might be confusing. Computing LoopInfo from scratch only to determine the irreducibility of a CFG might not be the best approach but if it's already computed, which is the case in ShrinkWrap and LV, I don't see why this approach is worse than using DT. I can improve the documentation in that regard.

Please, also note that the proposed algorithm also allows to reuse an existing RPO traversal, which is also important in terms of performance.

If a more generic algorithm is necessary for more general cases, I would suggest addressing that in a different patch. However, I think there is no silver bullet here. For a DT-based implementation one could argue that LoopInfo could be available and DT could have been invalidated and would need to be recomputed.

Pinging @qcolombet, the original author of this algorithm in ShrinkWrap, in case he wants to provide further information.

Does it sound reasonable?

Thanks,
Diego

[• dberlin]

Thanks, that is very helpful. It's much more likely that Dominator info is up to date than loop info, but it's not worth getting into here. The only thing I request is that you update the comments to suggest this only probably makes sense to use if loopinfo is computed already, and please just add your description of how it works with the example to the comments.

[fhahn]

In D40874#1013415, @dcaballe wrote:

Please, Florian, feel free to commit this patch whenever you think it's appropriate. I still don't have commit access.

Can do, but probably not before Monday.

[hsaito]

In D40874#1015810, @fhahn wrote:

In D40874#1013415, @dcaballe wrote:

Please, Florian, feel free to commit this patch whenever you think it's appropriate. I still don't have commit access.

Can do, but probably not before Monday.

Thanks, Florian, Daniel, and all. Diego will update the comments in the latter half of next week when he comes back from vacation. Sorry for the delay.
In the meantime, please look at D42447, the next patch in the series, if you haven't.

Thanks,
Hideki

[dcaballe]

Improving documentation of utility function 'containsIrreducibleCFG'.

Thanks, Daniel/Florian/Hideki.
Daniel, please, let me know if the new documentation addresses your concerns.

Thanks,
Diego

[• dberlin]

Looks good to me, thanks so much for the updates!

[dcaballe]

Thank you, Daniel!
OK, Florian, feel free to commit it whenever you have time. Thanks.

Diego

[dcaballe]

Thanks, Florian!

llvm/trunk/include/llvm/Analysis/CFG.h

 /// Determine whether there is a path from at least one block in Worklist to
 /// StopBB within a single function. Returns false only if we can prove that
 /// once any block in 'Worklist' has been reached then 'StopBB' can not be
 /// executed. Conservatively returns true.
 bool isPotentiallyReachableFromMany(SmallVectorImpl<BasicBlock *> &Worklist,
                                     BasicBlock *StopBB,
                                     const DominatorTree *DT = nullptr,
                                     const LoopInfo *LI = nullptr);
+
+/// \brief Return true if the control flow in \p RPOTraversal is irreducible.
+///
+/// This is a generic implementation to detect CFG irreducibility based on loop
+/// info analysis. It can be used for any kind of CFG (Loop, MachineLoop,
+/// Function, MachineFunction, etc.) by providing an RPO traversal (\p
+/// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility
+/// function is only recommended when loop info analysis is available. If loop
+/// info analysis isn't available, please, don't compute it explicitly for this
+/// purpose. There are more efficient ways to detect CFG irreducibility that
+/// don't require recomputing loop info analysis (e.g., T1/T2 or Tarjan's
+/// algorithm).
+///
+/// Requirements:
+///   1) GraphTraits must be implemented for NodeT type. It is used to access
+///      NodeT successors.
+//    2) \p RPOTraversal must be a valid reverse post-order traversal of the
+///      target CFG with begin()/end() iterator interfaces.
+///   3) \p LI must be a valid LoopInfoBase that contains up-to-date loop
+///      analysis information of the CFG.
+///
+/// This algorithm uses the information about reducible loop back-edges already
+/// computed in \p LI. When a back-edge is found during the RPO traversal, the
+/// algorithm checks whether the back-edge is one of the reducible back-edges in
+/// loop info. If it isn't, the CFG is irreducible. For example, for the CFG
+/// below (canonical irreducible graph) loop info won't contain any loop, so the
+/// algorithm will return that the CFG is irreducible when checking the B <-
+/// -> C back-edge.
+///
+/// (A->B, A->C, B->C, C->B, C->D)
+///    A
+///  /   \
+/// B<- ->C
+///       |
+///       D
+///
+template <class NodeT, class RPOTraversalT, class LoopInfoT,
+          class GT = GraphTraits<NodeT>>
+bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) {
+  /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge
+  /// according to LI. I.e., check if there exists a loop that contains Src and
+  /// where Dst is the loop header.
+  auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
+    for (const auto *Lp = LI.getLoopFor(Src); Lp; Lp = Lp->getParentLoop()) {
+      if (Lp->getHeader() == Dst)
+        return true;
+    }
+    return false;
+  };
+
+  SmallPtrSet<NodeT, 32> Visited;
+  for (NodeT Node : RPOTraversal) {
+    Visited.insert(Node);
+    for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) {
+      // Succ hasn't been visited yet
+      if (!Visited.count(Succ))
+        continue;
+      // We already visited Succ, thus Node->Succ must be a backedge. Check that
+      // the head matches what we have in the loop information. Otherwise, we
+      // have an irreducible graph.
+      if (!isProperBackedge(Node, Succ))
+        return true;
+    }
+  }
+
+  return false;
+}
 } // End llvm namespace
 
 #endif

llvm/trunk/include/llvm/Analysis/LoopIterator.h

public:
   }
 
   void clear() {
     PostNumbers.clear();
     PostBlocks.clear();
   }
 };
 
+/// Wrapper class to LoopBlocksDFS that provides a standard begin()/end()
+/// interface for the DFS reverse post-order traversal of blocks in a loop body.
+class LoopBlocksRPO {
+private:
+  LoopBlocksDFS DFS;
+
+public:
+  LoopBlocksRPO(Loop *Container) : DFS(Container) {}
+
+  /// Traverse the loop blocks and store the DFS result.
+  void perform(LoopInfo *LI) {
+    DFS.perform(LI);
+  }
+
+  /// Reverse iterate over the cached postorder blocks.
+  LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); }
+  LoopBlocksDFS::RPOIterator end() const { return DFS.endRPO(); }
+};
+
 /// Specialize po_iterator_storage to record postorder numbers.
 template<> class po_iterator_storage<LoopBlocksTraversal, true> {
   LoopBlocksTraversal &LBT;
 public:
   po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
   // These functions are defined below.
   bool insertEdge(Optional<BasicBlock *> From, BasicBlock *To);
   void finishPostorder(BasicBlock *BB);

llvm/trunk/lib/CodeGen/ShrinkWrap.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
if (Save && Restore &&
           Restore = nullptr;
           break;
         }
       }
     }
   }
 }
 
-/// Check whether the edge (\p SrcBB, \p DestBB) is a backedge according to MLI.
-/// I.e., check if it exists a loop that contains SrcBB and where DestBB is the
-/// loop header.
-static bool isProperBackedge(const MachineLoopInfo &MLI,
-                             const MachineBasicBlock *SrcBB,
-                             const MachineBasicBlock *DestBB) {
-  for (const MachineLoop *Loop = MLI.getLoopFor(SrcBB); Loop;
-       Loop = Loop->getParentLoop()) {
-    if (Loop->getHeader() == DestBB)
-      return true;
-  }
-  return false;
-}
-
-/// Check if the CFG of \p MF is irreducible.
-static bool isIrreducibleCFG(const MachineFunction &MF,
-                             const MachineLoopInfo &MLI) {
-  const MachineBasicBlock *Entry = &*MF.begin();
-  ReversePostOrderTraversal<const MachineBasicBlock *> RPOT(Entry);
-  BitVector VisitedBB(MF.getNumBlockIDs());
-  for (const MachineBasicBlock *MBB : RPOT) {
-    VisitedBB.set(MBB->getNumber());
-    for (const MachineBasicBlock *SuccBB : MBB->successors()) {
-      if (!VisitedBB.test(SuccBB->getNumber()))
-        continue;
-      // We already visited SuccBB, thus MBB->SuccBB must be a backedge.
-      // Check that the head matches what we have in the loop information.
-      // Otherwise, we have an irreducible graph.
-      if (!isProperBackedge(MLI, MBB, SuccBB))
-        return true;
-    }
-  }
-  return false;
-}
-
 bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()) || MF.empty() || !isShrinkWrapEnabled(MF))
     return false;
 
   DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
 
   init(MF);
 
-  if (isIrreducibleCFG(MF, *MLI)) {
+  ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
+  if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *MLI)) {
     // If MF is irreducible, a block may be in a loop without
     // MachineLoopInfo reporting it. I.e., we may use the
     // post-dominance property in loops, which lead to incorrect
     // results. Moreover, we may miss that the prologue and
     // epilogue are not in the same loop, leading to unbalanced
     // construction/deconstruction of the stack frame.
     DEBUG(dbgs() << "Irreducible CFGs are not supported yet\n");
     return false;

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
-#include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/DemandedBits.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"

 }
 
 namespace {
 
 class LoopVectorizationRequirements;
 
 } // end anonymous namespace
 
-/// Returns true if the given loop body has a cycle, excluding the loop
-/// itself.
-static bool hasCyclesInLoopBody(const Loop &L) {
-  if (!L.empty())
-    return true;
-
-  for (const auto &SCC :
-       make_range(scc_iterator<Loop, LoopBodyTraits>::begin(L),
-                  scc_iterator<Loop, LoopBodyTraits>::end(L))) {
-    if (SCC.size() > 1) {
-      DEBUG(dbgs() << "LVL: Detected a cycle in the loop body:\n");
-      DEBUG(L.dump());
-      return true;
-    }
-  }
-  return false;
-}
-
 /// A helper function for converting Scalar types to vector types.
 /// If the incoming type is void, we return void. If the VF is 1, we return
 /// the scalar type.
 static Type *ToVectorTy(Type *Scalar, unsigned VF) {
   if (Scalar->isVoidTy() || VF == 1)
     return Scalar;
   return VectorType::get(Scalar, VF);
 }
private:
   Instruction *UnsafeAlgebraInst = nullptr;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter &ORE;
 };
 
 } // end anonymous namespace
 
-static void addAcyclicInnerLoop(Loop &L, SmallVectorImpl<Loop *> &V) {
+static void addAcyclicInnerLoop(Loop &L, LoopInfo &LI,
+                                SmallVectorImpl<Loop *> &V) {
   if (L.empty()) {
-    if (!hasCyclesInLoopBody(L))
+    LoopBlocksRPO RPOT(&L);
+    RPOT.perform(&LI);
+    if (!containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
       V.push_back(&L);
     return;
   }
   for (Loop *InnerL : L)
-    addAcyclicInnerLoop(*InnerL, V);
+    addAcyclicInnerLoop(*InnerL, LI, V);
 }
 
 namespace {
 
 /// The LoopVectorize Pass.
 struct LoopVectorize : public FunctionPass {
   /// Pass identification, replacement for typeid
   static char ID;
for (auto &L : *LI)
     Changed |= simplifyLoop(L, DT, LI, SE, AC, false /* PreserveLCSSA */);
 
   // Build up a worklist of inner-loops to vectorize. This is necessary as
   // the act of vectorizing or partially unrolling a loop creates new loops
   // and can invalidate iterators across the loops.
   SmallVector<Loop *, 8> Worklist;
 
   for (Loop *L : *LI)
-    addAcyclicInnerLoop(*L, Worklist);
+    addAcyclicInnerLoop(*L, *LI, Worklist);
 
   LoopsAnalyzed += Worklist.size();
 
   // Now walk the identified inner loops.
   while (!Worklist.empty()) {
     Loop *L = Worklist.pop_back_val();
 
     // For the inner loops we actually process, form LCSSA to simplify the