[PM/LoopUnswitch] Detect irreducible control flow within loops and skip unswitching non-trivial edges.

[chandlerc]

Summary

This fixes the bug pointed out in review with non-trivial unswitching.

This also provides a basis that should make it pretty easy to finish
fleshing out a routine to scan an entire function body for irreducible
control flow, but this patch remains minimal for disabling loop
unswitch.

[fhahn]

@dcaballe added a containsIrreduciableCFG function to include/llvm/Analysis/CFG.h in D40874. I do not have time to take a close look today, but it seems at least for the attached test case, containsIrreduciableCFG does the right thing.

[chandlerc]

In D45754#1071186, @fhahn wrote:

@dcaballe added a containsIrreduciableCFG function to include/llvm/Analysis/CFG.h in D40874. I do not have time to take a close look today, but it seems at least for the attached test case, containsIrreduciableCFG does the right thing.

Gah.

I looked and looked, even looked specifically in this area, and asked around, all without success at finding this. Now I'm sad I wasted time building a new one. Thanks for pointing it out.

The approaches are... surprisingly different. I computed a slightly different thing. But I think I like the approach of the existing one quite a bit more, although I'm sad about the cost. But I'm willing for us to get bug reports about the cost of this before we really start stressing.

Lemme adjust this to just call that routine. Maybe I can even call it somewhat later to minimize the cost more.

[dcaballe]

Thanks, Florian!

I looked and looked, even looked specifically in this area, and asked around, all without success at finding this. Now I'm sad I wasted time building a new one. Thanks for pointing it out.

Sorry to hear that. The same was about to happen to me but I just found that implementation in ShrinkWrap and generalized it. Glad to see it's useful somehow.

Thanks,
Diego

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

1930

typo -> complexity

[chandlerc]

Use the existing facilities and sink this past the point where we find actual
unswitch candidates. This should at least avoid the cost of the loop traversal
when there are no loop invariant conditions.

[chandlerc]

And fix typo.

[chandlerc]

OK, should be ready for review again! A much, much simpler patch now.

[fhahn]

Thanks, LGTM.

Having a single function to detect irreducible CFGs allows us to test it more widely and in case it turns out to be a bottleneck, I think there are a couple of things we can do to improve the performance. The most prominent issue is probably that we re-do work for inner loops
, when loops are processed from inner to outer loop nests.

[chandlerc]

In D45754#1072141, @fhahn wrote:

Thanks, LGTM.

Having a single function to detect irreducible CFGs allows us to test it more widely and in case it turns out to be a bottleneck, I think there are a couple of things we can do to improve the performance. The most prominent issue is probably that we re-do work for inner loops
, when loops are processed from inner to outer loop nests.

Thanks for the review, and totally agree about the tradeoffs.

[fedor.sergeev]

Ahem... sorry for checking it only now, but this does not seem to address a testcase from PR36379, so it must be a different issue.
I will put this to more testing to see if it improves anything on our workflow.

[chandlerc]

Hang off on doing more testing. I have more failures w/ non-trivial
unswitching just in the test suite, so I already have multiple
reproductions that I'm working on.

llvm/include/llvm/Analysis/LoopInfo.h

public:
   }
 
   // True if the block is a loop header node
   bool isLoopHeader(const BlockT *BB) const {
     const LoopT *L = getLoopFor(BB);
     return L && L->getHeader() == BB;
   }
 
+  /// Check whether a loop contains an irreducible control flow cycle.
+  ///
+  /// This checks whether the CFG within the loop, not counting any subloops,
+  /// contains any irreducible cycles. When this returns false all cycles in
+  /// the control flow graph of the loop will be modeled by subloop objects.
+  bool hasIrreducibleCycle(const LoopT *L) const;
+
   /// This removes the specified top-level loop from this loop info object.
   /// The loop is not deleted, as it will presumably be inserted into
   /// another loop.
   LoopT *removeLoop(iterator I) {
     assert(I != end() && "Cannot remove end iterator!");
     LoopT *L = *I;
     assert(!L->getParentLoop() && "Not a top-level loop!");
     TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));

llvm/include/llvm/Analysis/LoopInfoImpl.h

do {
       PreOrderWorklist.append(L->begin(), L->end());
       PreOrderLoops.push_back(L);
     } while (!PreOrderWorklist.empty());
   }
 
   return PreOrderLoops;
 }
 
+template <class BlockT, class LoopT>
+bool LoopInfoBase<BlockT, LoopT>::hasIrreducibleCycle(const LoopT *L) const {
+  // We simply do a naive cycle-detection algorithm, except that we skip over
+  // any cycles contained within a subloop object. Sadly, this requires
+  // a fairly complex and custom iteration model and DFS walk.
+  //
+  // If this particular iteration model of loops is more widely used, we could
+  // package this up in its own iterator type, but until then we keep it
+  // minimal and isolated here.
+  using BlockTraits = GraphTraits<BlockT *>;
+  SmallSetVector<PointerUnion<BlockT *, LoopT *>, 16> NodeStack;
+  SmallVector<typename BlockTraits::ChildIteratorType, 16> BlockItStack;
+  SmallVector<std::pair<typename LoopT::block_iterator,
+                        typename BlockTraits::ChildIteratorType>,
+              4>
+      SubloopItStack;
+
+  auto PushChildBlock = [&](BlockT *Block) {
+    auto *Subloop = getLoopFor(Block);
+    if (Subloop == L) {
+      // Simple case without a nested loop.
+      if (!NodeStack.insert({Block}))
+        return false;
+
+      BlockItStack.push_back(BlockTraits::child_begin(Block));
+      return true;
+    }
+
+    // Walk up the loop nest as far as we can.
+    while (Subloop->getParentLoop() != L)
+      Subloop = Subloop->getParentLoop();
+
+    if (!NodeStack.insert({Subloop}))
+      return false;
+
+    SubloopItStack.push_back(
+        {Subloop->block_begin(),
+         BlockTraits::child_begin(*Subloop->block_begin())});
+    return true;
+  };
+
+  PushChildBlock(L->getHeader());
+  do {
+    auto TopNode = NodeStack.back();
+    if (auto *TopBlock = TopNode.template dyn_cast<BlockT *>()) {
+      auto &ChildIt = BlockItStack.back();
+      // Skip over non-loop blocks.
+      while (ChildIt != BlockTraits::child_end(TopBlock) &&
+             (*ChildIt == L->getHeader() || !L->contains(*ChildIt)))
+        ++ChildIt;
+      // If we've finished the children, pop the stack and continue.
+      if (ChildIt == BlockTraits::child_end(TopBlock)) {
+        BlockItStack.pop_back();
+        NodeStack.pop_back();
+        continue;
+      }
+      // Grab the child we'll push and step past it.
+      BlockT *Child = *ChildIt++;
+
+      // Try te push this child block and continue the DFS. If we fail, we found
+      // a cycle.
+      if (!PushChildBlock(Child))
+        return true;
+
+      continue;
+    }
+
+    // Otherwise, we have a subloop.
+    auto *TopSubloop = TopNode.template get<LoopT *>();
+    auto &SubloopItPair = SubloopItStack.back();
+    auto &SubloopBlockIt = SubloopItPair.first;
+    auto &SubloopChildIt = SubloopItPair.second;
+
+    // Scan for an exit of the subloop into this loop.
+    for (;;) {
+      // Look for a block that has children to scan.
+      while (SubloopChildIt == BlockTraits::child_end(*SubloopBlockIt)) {
+        SubloopBlockIt++;
+        if (SubloopBlockIt == TopSubloop->block_end())
+          break;
+        SubloopChildIt = BlockTraits::child_begin(*SubloopBlockIt);
+      }
+
+      // Stop once we exhaust the blocks or find a viable exit from the subloop
+      // to the outer loop.
+      if (SubloopBlockIt == TopSubloop->block_end() ||
+          (!TopSubloop->contains(*SubloopChildIt) &&
+           *SubloopChildIt != L->getHeader() && L->contains(*SubloopChildIt)))
+        break;
+
+      ++SubloopChildIt;
+    }
+
+    // If we've exhausted the subloop, pop it and continue.
+    if (SubloopBlockIt == TopSubloop->block_end()) {
+      // All exiting edges of this subloop have been visited.
+      SubloopItStack.pop_back();
+      NodeStack.pop_back();
+      continue;
+    }
+
+    // Grab the child we'll push and step past it.
+    BlockT *Child = *SubloopChildIt++;
+
+    // Try te push this child block and continue the DFS. If we fail, we found a
+    // cycle.
+    if (!PushChildBlock(Child))
+      return true;
+  } while (!NodeStack.empty());
+
+  // No cycles found!
+  return false;
+}
+
 // Debugging
 template <class BlockT, class LoopT>
 void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {
   for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
     TopLevelLoops[i]->print(OS);
 #if 0
   for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
          E = BBMap.end(); I != E; ++I)

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC,
   Changed |= unswitchAllTrivialConditions(L, DT, LI);
 
   // If we're not doing non-trivial unswitching, we're done. We both accept
   // a parameter but also check a local flag that can be used for testing
   // a debugging.
   if (!NonTrivial && !EnableNonTrivialUnswitch)
     return Changed;
 
+  // Check if there are irreducible CFG cycles in this loop. If so, we cannot
+  // easily unswitch non-trivial edges out of the loop. Doing so might turn the
+  // irreducible control flow into reducible control flow and introduce new
+  // loops "out of thin air". If we ever discover important use cases for doing
+  // this, we can add support to loop unswitch, but it is a lot of complexit
+  // for what seems little or no real world benifit.
+  if (LI.hasIrreducibleCycle(&L))
+    return Changed;
+
   // Collect all remaining invariant branch conditions within this loop (as
   // opposed to an inner loop which would be handled when visiting that inner
   // loop).
   SmallVector<TerminatorInst *, 4> UnswitchCandidates;
   for (auto *BB : L.blocks())
     if (LI.getLoopFor(BB) == &L)
       if (auto *BI = dyn_cast<BranchInst>(BB->getTerminator()))
         if (BI->isConditional() && L.isLoopInvariant(BI->getCondition()) &&

llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll

 
 loop_exit:
   %lcssa = phi i32 [ %var_val, %loop_begin ]
   ret i32 %lcssa
 ; CHECK:       loop_exit:
 ; CHECK-NEXT:    %[[LCSSA:.*]] = phi i32 [ %[[V]], %loop_begin ]
 ; CHECK-NEXT:    ret i32 %[[LCSSA]]
 }
+
+; Negative test: we do not switch when the loop contains unstructured control
+; flows as it would significantly complicate the process as novel loops might
+; be formed, etc.
+define void @test_no_unswitch_unstructured_cfg(i1* %ptr, i1 %cond) {
+; CHECK-LABEL: @test_no_unswitch_unstructured_cfg(
+entry:
+  br label %loop_begin
+
+loop_begin:
+  br i1 %cond, label %loop_left, label %loop_right
+
+loop_left:
+  %v1 = load i1, i1* %ptr
+  br i1 %v1, label %loop_right, label %loop_merge
+
+loop_right:
+  %v2 = load i1, i1* %ptr
+  br i1 %v2, label %loop_left, label %loop_merge
+
+loop_merge:
+  %v3 = load i1, i1* %ptr
+  br i1 %v3, label %loop_latch, label %loop_exit
+
+loop_latch:
+  br label %loop_begin
+
+loop_exit:
+  ret void
+}