Index: llvm/include/llvm/Analysis/LoopInfo.h =================================================================== --- llvm/include/llvm/Analysis/LoopInfo.h +++ llvm/include/llvm/Analysis/LoopInfo.h @@ -693,6 +693,13 @@ 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. Index: llvm/include/llvm/Analysis/LoopInfoImpl.h =================================================================== --- llvm/include/llvm/Analysis/LoopInfoImpl.h +++ llvm/include/llvm/Analysis/LoopInfoImpl.h @@ -557,6 +557,120 @@ return PreOrderLoops; } +template +bool LoopInfoBase::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; + SmallSetVector, 16> NodeStack; + SmallVector BlockItStack; + SmallVector, + 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()) { + 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(); + 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 void LoopInfoBase::print(raw_ostream &OS) const { Index: llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp =================================================================== --- llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp +++ llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp @@ -1923,6 +1923,15 @@ 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). Index: llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll =================================================================== --- llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll +++ llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll @@ -2350,3 +2350,33 @@ ; 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 +}