Author: Alexey Bataev Date: 2024-08-26T08:09:35-04:00 New Revision: 5153817e36dbaaf6800a5befb8c7a54363840e81
URL: https://github.com/llvm/llvm-project/commit/5153817e36dbaaf6800a5befb8c7a54363840e81 DIFF: https://github.com/llvm/llvm-project/commit/5153817e36dbaaf6800a5befb8c7a54363840e81.diff LOG: Revert "[FixIrreducible] Use CycleInfo instead of a custom SCC traversal (#10…" This reverts commit fa4cc9ddd58eb9fef2497e678873ff3b495340a3. Added: Modified: llvm/include/llvm/ADT/GenericCycleInfo.h llvm/lib/Transforms/Utils/FixIrreducible.cpp llvm/test/CodeGen/AMDGPU/llc-pipeline.ll llvm/test/Transforms/FixIrreducible/basic.ll llvm/test/Transforms/FixIrreducible/bug45623.ll llvm/test/Transforms/FixIrreducible/nested.ll llvm/test/Transforms/FixIrreducible/switch.ll llvm/test/Transforms/FixIrreducible/unreachable.ll llvm/test/Transforms/StructurizeCFG/workarounds/needs-fix-reducible.ll llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll Removed: ################################################################################ diff --git a/llvm/include/llvm/ADT/GenericCycleInfo.h b/llvm/include/llvm/ADT/GenericCycleInfo.h index 8c2fa0490e638a..55034844d30b0d 100644 --- a/llvm/include/llvm/ADT/GenericCycleInfo.h +++ b/llvm/include/llvm/ADT/GenericCycleInfo.h @@ -107,13 +107,6 @@ template <typename ContextT> class GenericCycle { return is_contained(Entries, Block); } - /// \brief Replace all entries with \p Block as single entry. - void setSingleEntry(BlockT *Block) { - assert(contains(Block)); - Entries.clear(); - Entries.push_back(Block); - } - /// \brief Return whether \p Block is contained in the cycle. bool contains(const BlockT *Block) const { return Blocks.contains(Block); } @@ -199,16 +192,11 @@ template <typename ContextT> class GenericCycle { //@{ using const_entry_iterator = typename SmallVectorImpl<BlockT *>::const_iterator; - const_entry_iterator entry_begin() const { return Entries.begin(); } - const_entry_iterator entry_end() const { return Entries.end(); } + size_t getNumEntries() const { return Entries.size(); } iterator_range<const_entry_iterator> entries() const { - return llvm::make_range(entry_begin(), entry_end()); + return llvm::make_range(Entries.begin(), Entries.end()); } - using const_reverse_entry_iterator = - typename SmallVectorImpl<BlockT *>::const_reverse_iterator; - const_reverse_entry_iterator entry_rbegin() const { return Entries.rbegin(); } - const_reverse_entry_iterator entry_rend() const { return Entries.rend(); } //@} Printable printEntries(const ContextT &Ctx) const { @@ -267,6 +255,12 @@ template <typename ContextT> class GenericCycleInfo { /// the subtree. void moveTopLevelCycleToNewParent(CycleT *NewParent, CycleT *Child); + /// Assumes that \p Cycle is the innermost cycle containing \p Block. + /// \p Block will be appended to \p Cycle and all of its parent cycles. + /// \p Block will be added to BlockMap with \p Cycle and + /// BlockMapTopLevel with \p Cycle's top level parent cycle. + void addBlockToCycle(BlockT *Block, CycleT *Cycle); + public: GenericCycleInfo() = default; GenericCycleInfo(GenericCycleInfo &&) = default; @@ -284,12 +278,6 @@ template <typename ContextT> class GenericCycleInfo { unsigned getCycleDepth(const BlockT *Block) const; CycleT *getTopLevelParentCycle(BlockT *Block); - /// Assumes that \p Cycle is the innermost cycle containing \p Block. - /// \p Block will be appended to \p Cycle and all of its parent cycles. - /// \p Block will be added to BlockMap with \p Cycle and - /// BlockMapTopLevel with \p Cycle's top level parent cycle. - void addBlockToCycle(BlockT *Block, CycleT *Cycle); - /// Methods for debug and self-test. //@{ void verifyCycleNest(bool VerifyFull = false) const; diff --git a/llvm/lib/Transforms/Utils/FixIrreducible.cpp b/llvm/lib/Transforms/Utils/FixIrreducible.cpp index 67fb806d3eae54..cdd4b36d2d9ebf 100644 --- a/llvm/lib/Transforms/Utils/FixIrreducible.cpp +++ b/llvm/lib/Transforms/Utils/FixIrreducible.cpp @@ -6,66 +6,50 @@ // //===----------------------------------------------------------------------===// // -// INPUT CFG: The blocks H and B form an irreducible cycle with two headers. +// An irreducible SCC is one which has multiple "header" blocks, i.e., blocks +// with control-flow edges incident from outside the SCC. This pass converts a +// irreducible SCC into a natural loop by applying the following transformation: +// +// 1. Collect the set of headers H of the SCC. +// 2. Collect the set of predecessors P of these headers. These may be inside as +// well as outside the SCC. +// 3. Create block N and redirect every edge from set P to set H through N. +// +// This converts the SCC into a natural loop with N as the header: N is the only +// block with edges incident from outside the SCC, and all backedges in the SCC +// are incident on N, i.e., for every backedge, the head now dominates the tail. +// +// INPUT CFG: The blocks A and B form an irreducible loop with two headers. // // Entry // / \ // v v -// H ----> B +// A ----> B // ^ /| // `----' | // v // Exit // -// OUTPUT CFG: Converted to a natural loop with a new header N. +// OUTPUT CFG: Edges incident on A and B are now redirected through a +// new block N, forming a natural loop consisting of N, A and B. // // Entry // | // v -// N <---. -// / \ \ -// / \ | -// v v / -// H --> B --' +// .---> N <---. +// / / \ \ +// | / \ | +// \ v v / +// `-- A B --' // | // v // Exit // -// To convert an irreducible cycle C to a natural loop L: -// -// 1. Add a new node N to C. -// 2. Redirect all external incoming edges through N. -// 3. Redirect all edges incident on header H through N. -// -// This is sufficient to ensure that: -// -// a. Every closed path in C also exists in L, with the modification that any -// path passing through H now passes through N before reaching H. -// b. Every external path incident on any entry of C is now incident on N and -// then redirected to the entry. -// -// Thus, L is a strongly connected component dominated by N, and hence L is a -// natural loop with header N. -// -// When an irreducible cycle C with header H is transformed into a loop, the -// following invariants hold: -// -// 1. No new subcycles are "discovered" in the set (C-H). The only internal -// edges that are redirected by the transform are incident on H. Any subcycle -// S in (C-H), already existed prior to this transform, and is already in the -// list of children for this cycle C. -// -// 2. Subcycles of C are not modified by the transform. For some subcycle S of -// C, edges incident on the entries of S are either internal to C, or they -// are now redirected through N, which is outside of S. So the list of -// entries to S does not change. Since the transform only adds a block -// outside S, and redirects edges that are not internal to S, the list of -// blocks in S does not change. -// -// 3. Similarly, any natural loop L included in C is not affected, with one -// exception: L is "destroyed" by the transform iff its header is H. The -// backedges of such a loop are now redirected to N instead, and hence the -// body of this loop gets merged into the new loop with header N. +// The transformation is applied to every maximal SCC that is not already +// recognized as a loop. The pass operates on all maximal SCCs found in the +// function body outside of any loop, as well as those found inside each loop, +// including inside any newly created loops. This ensures that any SCC hidden +// inside a maximal SCC is also transformed. // // The actual transformation is handled by the ControlFlowHub, which redirects // specified control flow edges through a set of guard blocks. This also moves @@ -83,9 +67,8 @@ #include "llvm/Transforms/Utils/FixIrreducible.h" #include "llvm/ADT/SCCIterator.h" -#include "llvm/Analysis/CycleAnalysis.h" #include "llvm/Analysis/DomTreeUpdater.h" -#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopIterator.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Transforms/Utils.h" @@ -105,9 +88,8 @@ struct FixIrreducible : public FunctionPass { void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired<DominatorTreeWrapperPass>(); - AU.addRequired<CycleInfoWrapperPass>(); + AU.addRequired<LoopInfoWrapperPass>(); AU.addPreserved<DominatorTreeWrapperPass>(); - AU.addPreserved<CycleInfoWrapperPass>(); AU.addPreserved<LoopInfoWrapperPass>(); } @@ -131,14 +113,16 @@ INITIALIZE_PASS_END(FixIrreducible, "fix-irreducible", // When a new loop is created, existing children of the parent loop may now be // fully inside the new loop. Reconnect these as children of the new loop. static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop, - BasicBlock *OldHeader) { + SetVector<BasicBlock *> &Blocks, + SetVector<BasicBlock *> &Headers) { auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector() : LI.getTopLevelLoopsVector(); - // Any candidate is a child iff its header is owned by the new loop. Move all - // the children to a new vector. + // The new loop cannot be its own child, and any candidate is a + // child iff its header is owned by the new loop. Move all the + // children to a new vector. auto FirstChild = std::partition( CandidateLoops.begin(), CandidateLoops.end(), [&](Loop *L) { - return NewLoop == L || !NewLoop->contains(L->getHeader()); + return L == NewLoop || !Blocks.contains(L->getHeader()); }); SmallVector<Loop *, 8> ChildLoops(FirstChild, CandidateLoops.end()); CandidateLoops.erase(FirstChild, CandidateLoops.end()); @@ -146,9 +130,10 @@ static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop, for (Loop *Child : ChildLoops) { LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName() << "\n"); - // A child loop whose header was the old cycle header gets destroyed since - // its backedges are removed. - if (Child->getHeader() == OldHeader) { + // TODO: A child loop whose header is also a header in the current + // SCC gets destroyed since its backedges are removed. That may + // not be necessary if we can retain such backedges. + if (Headers.count(Child->getHeader())) { for (auto *BB : Child->blocks()) { if (LI.getLoopFor(BB) != Child) continue; @@ -173,18 +158,63 @@ static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop, } } -static void updateLoopInfo(LoopInfo &LI, Cycle &C, - ArrayRef<BasicBlock *> GuardBlocks) { - // The parent loop is a natural loop L mapped to the cycle header H as long as - // H is not also the header of L. In the latter case, L is destroyed and we - // seek its parent instead. - BasicBlock *CycleHeader = C.getHeader(); - Loop *ParentLoop = LI.getLoopFor(CycleHeader); - if (ParentLoop && ParentLoop->getHeader() == CycleHeader) - ParentLoop = ParentLoop->getParentLoop(); +// Given a set of blocks and headers in an irreducible SCC, convert it into a +// natural loop. Also insert this new loop at its appropriate place in the +// hierarchy of loops. +static void createNaturalLoopInternal(LoopInfo &LI, DominatorTree &DT, + Loop *ParentLoop, + SetVector<BasicBlock *> &Blocks, + SetVector<BasicBlock *> &Headers) { +#ifndef NDEBUG + // All headers are part of the SCC + for (auto *H : Headers) { + assert(Blocks.count(H)); + } +#endif + + SetVector<BasicBlock *> Predecessors; + for (auto *H : Headers) { + for (auto *P : predecessors(H)) { + Predecessors.insert(P); + } + } + + LLVM_DEBUG( + dbgs() << "Found predecessors:"; + for (auto P : Predecessors) { + dbgs() << " " << P->getName(); + } + dbgs() << "\n"); + + // Redirect all the backedges through a "hub" consisting of a series + // of guard blocks that manage the flow of control from the + // predecessors to the headers. + ControlFlowHub CHub; + for (BasicBlock *P : Predecessors) { + auto *Branch = cast<BranchInst>(P->getTerminator()); + BasicBlock *Succ0 = Branch->getSuccessor(0); + Succ0 = Headers.count(Succ0) ? Succ0 : nullptr; + BasicBlock *Succ1 = + Branch->isUnconditional() ? nullptr : Branch->getSuccessor(1); + Succ1 = Succ1 && Headers.count(Succ1) ? Succ1 : nullptr; + CHub.addBranch(P, Succ0, Succ1); + + LLVM_DEBUG(dbgs() << "Added branch: " << P->getName() << " -> " + << (Succ0 ? Succ0->getName() : "") << " " + << (Succ1 ? Succ1->getName() : "") << "\n"); + } + + SmallVector<BasicBlock *, 8> GuardBlocks; + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); + CHub.finalize(&DTU, GuardBlocks, "irr"); +#if defined(EXPENSIVE_CHECKS) + assert(DT.verify(DominatorTree::VerificationLevel::Full)); +#else + assert(DT.verify(DominatorTree::VerificationLevel::Fast)); +#endif // Create a new loop from the now-transformed cycle - auto *NewLoop = LI.AllocateLoop(); + auto NewLoop = LI.AllocateLoop(); if (ParentLoop) { ParentLoop->addChildLoop(NewLoop); } else { @@ -197,11 +227,12 @@ static void updateLoopInfo(LoopInfo &LI, Cycle &C, // header. Since the new loop is already in LoopInfo, the new blocks // are also propagated up the chain of parent loops. for (auto *G : GuardBlocks) { - LLVM_DEBUG(dbgs() << "added guard block to loop: " << G->getName() << "\n"); + LLVM_DEBUG(dbgs() << "added guard block: " << G->getName() << "\n"); NewLoop->addBasicBlockToLoop(G, LI); } - for (auto *BB : C.blocks()) { + // Add the SCC blocks to the new loop. + for (auto *BB : Blocks) { NewLoop->addBlockEntry(BB); if (LI.getLoopFor(BB) == ParentLoop) { LLVM_DEBUG(dbgs() << "moved block from parent: " << BB->getName() @@ -214,161 +245,129 @@ static void updateLoopInfo(LoopInfo &LI, Cycle &C, LLVM_DEBUG(dbgs() << "header for new loop: " << NewLoop->getHeader()->getName() << "\n"); - reconnectChildLoops(LI, ParentLoop, NewLoop, C.getHeader()); + reconnectChildLoops(LI, ParentLoop, NewLoop, Blocks, Headers); - LLVM_DEBUG(dbgs() << "Verify new loop.\n"; NewLoop->print(dbgs())); NewLoop->verifyLoop(); if (ParentLoop) { - LLVM_DEBUG(dbgs() << "Verify parent loop.\n"; ParentLoop->print(dbgs())); ParentLoop->verifyLoop(); } +#if defined(EXPENSIVE_CHECKS) + LI.verify(DT); +#endif // EXPENSIVE_CHECKS } -// Given a set of blocks and headers in an irreducible SCC, convert it into a -// natural loop. Also insert this new loop at its appropriate place in the -// hierarchy of loops. -static bool fixIrreducible(Cycle &C, CycleInfo &CI, DominatorTree &DT, - LoopInfo *LI) { - if (C.isReducible()) - return false; - LLVM_DEBUG(dbgs() << "Processing cycle:\n" << CI.print(&C) << "\n";); +namespace llvm { +// Enable the graph traits required for traversing a Loop body. +template <> struct GraphTraits<Loop> : LoopBodyTraits {}; +} // namespace llvm - ControlFlowHub CHub; - SetVector<BasicBlock *> Predecessors; +// Overloaded wrappers to go with the function template below. +static BasicBlock *unwrapBlock(BasicBlock *B) { return B; } +static BasicBlock *unwrapBlock(LoopBodyTraits::NodeRef &N) { return N.second; } - // Redirect internal edges incident on the header. - BasicBlock *Header = C.getHeader(); - for (BasicBlock *P : predecessors(Header)) { - if (C.contains(P)) - Predecessors.insert(P); - } - - for (BasicBlock *P : Predecessors) { - auto *Branch = cast<BranchInst>(P->getTerminator()); - // Exactly one of the two successors is the header. - BasicBlock *Succ0 = Branch->getSuccessor(0) == Header ? Header : nullptr; - BasicBlock *Succ1 = Succ0 ? nullptr : Header; - if (!Succ0) - assert(Branch->getSuccessor(1) == Header); - assert(Succ0 || Succ1); - CHub.addBranch(P, Succ0, Succ1); +static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Function *F, + SetVector<BasicBlock *> &Blocks, + SetVector<BasicBlock *> &Headers) { + createNaturalLoopInternal(LI, DT, nullptr, Blocks, Headers); +} - LLVM_DEBUG(dbgs() << "Added internal branch: " << P->getName() << " -> " - << (Succ0 ? Succ0->getName() : "") << " " - << (Succ1 ? Succ1->getName() : "") << "\n"); - } +static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Loop &L, + SetVector<BasicBlock *> &Blocks, + SetVector<BasicBlock *> &Headers) { + createNaturalLoopInternal(LI, DT, &L, Blocks, Headers); +} - // Redirect external incoming edges. This includes the edges on the header. - Predecessors.clear(); - for (BasicBlock *E : C.entries()) { - for (BasicBlock *P : predecessors(E)) { - if (!C.contains(P)) - Predecessors.insert(P); +// Convert irreducible SCCs; Graph G may be a Function* or a Loop&. +template <class Graph> +static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G) { + bool Changed = false; + for (auto Scc = scc_begin(G); !Scc.isAtEnd(); ++Scc) { + if (Scc->size() < 2) + continue; + SetVector<BasicBlock *> Blocks; + LLVM_DEBUG(dbgs() << "Found SCC:"); + for (auto N : *Scc) { + auto BB = unwrapBlock(N); + LLVM_DEBUG(dbgs() << " " << BB->getName()); + Blocks.insert(BB); } - } - - for (BasicBlock *P : Predecessors) { - auto *Branch = cast<BranchInst>(P->getTerminator()); - BasicBlock *Succ0 = Branch->getSuccessor(0); - Succ0 = C.contains(Succ0) ? Succ0 : nullptr; - BasicBlock *Succ1 = - Branch->isUnconditional() ? nullptr : Branch->getSuccessor(1); - Succ1 = Succ1 && C.contains(Succ1) ? Succ1 : nullptr; - CHub.addBranch(P, Succ0, Succ1); - - LLVM_DEBUG(dbgs() << "Added external branch: " << P->getName() << " -> " - << (Succ0 ? Succ0->getName() : "") << " " - << (Succ1 ? Succ1->getName() : "") << "\n"); - } - - // Redirect all the backedges through a "hub" consisting of a series - // of guard blocks that manage the flow of control from the - // predecessors to the headers. - SmallVector<BasicBlock *> GuardBlocks; - - // Minor optimization: The cycle entries are discovered in an order that is - // the opposite of the order in which these blocks appear as branch targets. - // This results in a lot of condition inversions in the control flow out of - // the new ControlFlowHub, which can be mitigated if the orders match. So we - // reverse the entries when adding them to the hub. - SetVector<BasicBlock *> Entries; - Entries.insert(C.entry_rbegin(), C.entry_rend()); - - DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); - CHub.finalize(&DTU, GuardBlocks, "irr"); -#if defined(EXPENSIVE_CHECKS) - assert(DT.verify(DominatorTree::VerificationLevel::Full)); -#else - assert(DT.verify(DominatorTree::VerificationLevel::Fast)); -#endif - - // If we are updating LoopInfo, do that now before modifying the cycle. This - // ensures that the first guard block is the header of a new natural loop. - if (LI) - updateLoopInfo(*LI, C, GuardBlocks); + LLVM_DEBUG(dbgs() << "\n"); + + // Minor optimization: The SCC blocks are usually discovered in an order + // that is the opposite of the order in which these blocks appear as branch + // targets. This results in a lot of condition inversions in the control + // flow out of the new ControlFlowHub, which can be mitigated if the orders + // match. So we discover the headers using the reverse of the block order. + SetVector<BasicBlock *> Headers; + LLVM_DEBUG(dbgs() << "Found headers:"); + for (auto *BB : reverse(Blocks)) { + for (const auto P : predecessors(BB)) { + // Skip unreachable predecessors. + if (!DT.isReachableFromEntry(P)) + continue; + if (!Blocks.count(P)) { + LLVM_DEBUG(dbgs() << " " << BB->getName()); + Headers.insert(BB); + break; + } + } + } + LLVM_DEBUG(dbgs() << "\n"); - for (auto *G : GuardBlocks) { - LLVM_DEBUG(dbgs() << "added guard block to cycle: " << G->getName() - << "\n"); - CI.addBlockToCycle(G, &C); + if (Headers.size() == 1) { + assert(LI.isLoopHeader(Headers.front())); + LLVM_DEBUG(dbgs() << "Natural loop with a single header: skipped\n"); + continue; + } + createNaturalLoop(LI, DT, G, Blocks, Headers); + Changed = true; } - C.setSingleEntry(GuardBlocks[0]); - - C.verifyCycle(); - if (Cycle *Parent = C.getParentCycle()) - Parent->verifyCycle(); - - LLVM_DEBUG(dbgs() << "Finished one cycle:\n"; CI.print(dbgs());); - return true; + return Changed; } -static bool FixIrreducibleImpl(Function &F, CycleInfo &CI, DominatorTree &DT, - LoopInfo *LI) { +static bool FixIrreducibleImpl(Function &F, LoopInfo &LI, DominatorTree &DT) { LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: " << F.getName() << "\n"); assert(hasOnlySimpleTerminator(F) && "Unsupported block terminator."); bool Changed = false; - for (Cycle *TopCycle : CI.toplevel_cycles()) { - for (Cycle *C : depth_first(TopCycle)) { - Changed |= fixIrreducible(*C, CI, DT, LI); - } + SmallVector<Loop *, 8> WorkList; + + LLVM_DEBUG(dbgs() << "visiting top-level\n"); + Changed |= makeReducible(LI, DT, &F); + + // Any SCCs reduced are now already in the list of top-level loops, so simply + // add them all to the worklist. + append_range(WorkList, LI); + + while (!WorkList.empty()) { + auto L = WorkList.pop_back_val(); + LLVM_DEBUG(dbgs() << "visiting loop with header " + << L->getHeader()->getName() << "\n"); + Changed |= makeReducible(LI, DT, *L); + // Any SCCs reduced are now already in the list of child loops, so simply + // add them all to the worklist. + WorkList.append(L->begin(), L->end()); } - if (!Changed) - return false; - -#if defined(EXPENSIVE_CHECKS) - CI.verify(); - if (LI) { - LI.verify(DT); - } -#endif // EXPENSIVE_CHECKS - - return true; + return Changed; } bool FixIrreducible::runOnFunction(Function &F) { - auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); - LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; - auto &CI = getAnalysis<CycleInfoWrapperPass>().getResult(); + auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); - return FixIrreducibleImpl(F, CI, DT, LI); + return FixIrreducibleImpl(F, LI, DT); } PreservedAnalyses FixIrreduciblePass::run(Function &F, FunctionAnalysisManager &AM) { - auto *LI = AM.getCachedResult<LoopAnalysis>(F); - auto &CI = AM.getResult<CycleAnalysis>(F); + auto &LI = AM.getResult<LoopAnalysis>(F); auto &DT = AM.getResult<DominatorTreeAnalysis>(F); - - if (!FixIrreducibleImpl(F, CI, DT, LI)) + if (!FixIrreducibleImpl(F, LI, DT)) return PreservedAnalyses::all(); - PreservedAnalyses PA; PA.preserve<LoopAnalysis>(); - PA.preserve<CycleAnalysis>(); PA.preserve<DominatorTreeAnalysis>(); return PA; } diff --git a/llvm/test/CodeGen/AMDGPU/llc-pipeline.ll b/llvm/test/CodeGen/AMDGPU/llc-pipeline.ll index 29e8ebdafb5871..57575f786152bd 100644 --- a/llvm/test/CodeGen/AMDGPU/llc-pipeline.ll +++ b/llvm/test/CodeGen/AMDGPU/llc-pipeline.ll @@ -67,9 +67,8 @@ ; GCN-O0-NEXT: Uniformity Analysis ; GCN-O0-NEXT: Unify divergent function exit nodes ; GCN-O0-NEXT: Dominator Tree Construction -; GCN-O0-NEXT: Cycle Info Analysis -; GCN-O0-NEXT: Convert irreducible control-flow into natural loops ; GCN-O0-NEXT: Natural Loop Information +; GCN-O0-NEXT: Convert irreducible control-flow into natural loops ; GCN-O0-NEXT: Fixup each natural loop to have a single exit block ; GCN-O0-NEXT: Post-Dominator Tree Construction ; GCN-O0-NEXT: Dominance Frontier Construction @@ -261,9 +260,8 @@ ; GCN-O1-NEXT: Post-Dominator Tree Construction ; GCN-O1-NEXT: Unify divergent function exit nodes ; GCN-O1-NEXT: Dominator Tree Construction -; GCN-O1-NEXT: Cycle Info Analysis -; GCN-O1-NEXT: Convert irreducible control-flow into natural loops ; GCN-O1-NEXT: Natural Loop Information +; GCN-O1-NEXT: Convert irreducible control-flow into natural loops ; GCN-O1-NEXT: Fixup each natural loop to have a single exit block ; GCN-O1-NEXT: Post-Dominator Tree Construction ; GCN-O1-NEXT: Dominance Frontier Construction @@ -558,9 +556,8 @@ ; GCN-O1-OPTS-NEXT: Post-Dominator Tree Construction ; GCN-O1-OPTS-NEXT: Unify divergent function exit nodes ; GCN-O1-OPTS-NEXT: Dominator Tree Construction -; GCN-O1-OPTS-NEXT: Cycle Info Analysis -; GCN-O1-OPTS-NEXT: Convert irreducible control-flow into natural loops ; GCN-O1-OPTS-NEXT: Natural Loop Information +; GCN-O1-OPTS-NEXT: Convert irreducible control-flow into natural loops ; GCN-O1-OPTS-NEXT: Fixup each natural loop to have a single exit block ; GCN-O1-OPTS-NEXT: Post-Dominator Tree Construction ; GCN-O1-OPTS-NEXT: Dominance Frontier Construction @@ -867,9 +864,8 @@ ; GCN-O2-NEXT: Post-Dominator Tree Construction ; GCN-O2-NEXT: Unify divergent function exit nodes ; GCN-O2-NEXT: Dominator Tree Construction -; GCN-O2-NEXT: Cycle Info Analysis -; GCN-O2-NEXT: Convert irreducible control-flow into natural loops ; GCN-O2-NEXT: Natural Loop Information +; GCN-O2-NEXT: Convert irreducible control-flow into natural loops ; GCN-O2-NEXT: Fixup each natural loop to have a single exit block ; GCN-O2-NEXT: Post-Dominator Tree Construction ; GCN-O2-NEXT: Dominance Frontier Construction @@ -1190,9 +1186,8 @@ ; GCN-O3-NEXT: Post-Dominator Tree Construction ; GCN-O3-NEXT: Unify divergent function exit nodes ; GCN-O3-NEXT: Dominator Tree Construction -; GCN-O3-NEXT: Cycle Info Analysis -; GCN-O3-NEXT: Convert irreducible control-flow into natural loops ; GCN-O3-NEXT: Natural Loop Information +; GCN-O3-NEXT: Convert irreducible control-flow into natural loops ; GCN-O3-NEXT: Fixup each natural loop to have a single exit block ; GCN-O3-NEXT: Post-Dominator Tree Construction ; GCN-O3-NEXT: Dominance Frontier Construction diff --git a/llvm/test/Transforms/FixIrreducible/basic.ll b/llvm/test/Transforms/FixIrreducible/basic.ll index 7f81e89bc5f5b4..30591c80c5559d 100644 --- a/llvm/test/Transforms/FixIrreducible/basic.ll +++ b/llvm/test/Transforms/FixIrreducible/basic.ll @@ -1,27 +1,24 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt < %s -fix-irreducible --verify-loop-info -S | FileCheck %s -; RUN: opt < %s -passes='fix-irreducible,verify<loops>' -S | FileCheck %s -; RUN: opt < %s -passes='verify<loops>,fix-irreducible,verify<loops>' -S | FileCheck %s +; RUN: opt < %s -passes='fix-irreducible,verify<loops>' -S | FileCheck %s -check-prefix=CHECK define i32 @basic(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) { ; CHECK-LABEL: @basic( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true ; CHECK-NEXT: br label [[IRR_GUARD:%.*]] ; CHECK: left: -; CHECK-NEXT: [[L_PHI:%.*]] = phi i32 [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ], [ [[L_PHI_MOVED:%.*]], [[IRR_GUARD]] ] -; CHECK-NEXT: [[L:%.*]] = add i32 [[L_PHI]], 1 +; CHECK-NEXT: [[L:%.*]] = add i32 [[L_PHI_MOVED:%.*]], 1 ; CHECK-NEXT: br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] ; CHECK: right: -; CHECK-NEXT: br i1 [[PREDRIGHT:%.*]], label [[LEFT:%.*]], label [[EXIT]] +; CHECK-NEXT: br i1 [[PREDRIGHT:%.*]], label [[IRR_GUARD]], label [[EXIT]] ; CHECK: exit: -; CHECK-NEXT: [[Z:%.*]] = phi i32 [ [[L]], [[LEFT]] ], [ [[R_PHI_MOVED]], [[RIGHT]] ] +; CHECK-NEXT: [[Z:%.*]] = phi i32 [ [[L]], [[LEFT:%.*]] ], [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ] ; CHECK-NEXT: ret i32 [[Z]] ; CHECK: irr.guard: -; CHECK-NEXT: [[L_PHI_MOVED]] = phi i32 [ [[L_PHI_MOVED]], [[LEFT]] ], [ [[X:%.*]], [[ENTRY:%.*]] ] -; CHECK-NEXT: [[R_PHI_MOVED]] = phi i32 [ [[L]], [[LEFT]] ], [ [[Y:%.*]], [[ENTRY]] ] -; CHECK-NEXT: [[GUARD_RIGHT:%.*]] = phi i1 [ true, [[LEFT]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ] -; CHECK-NEXT: br i1 [[GUARD_RIGHT]], label [[RIGHT]], label [[LEFT]] +; CHECK-NEXT: [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY:%.*]] ], [ [[L]], [[LEFT]] ] +; CHECK-NEXT: [[L_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ] +; CHECK-NEXT: [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY]] ], [ false, [[LEFT]] ] +; CHECK-NEXT: br i1 [[GUARD_LEFT]], label [[LEFT]], label [[RIGHT]] ; entry: br i1 %PredEntry, label %left, label %right @@ -43,21 +40,19 @@ exit: define i32 @feedback_loop(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) { ; CHECK-LABEL: @feedback_loop( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true ; CHECK-NEXT: br label [[IRR_GUARD:%.*]] ; CHECK: left: -; CHECK-NEXT: [[L_PHI:%.*]] = phi i32 [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ], [ [[L_PHI_MOVED:%.*]], [[IRR_GUARD]] ] ; CHECK-NEXT: br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] ; CHECK: right: -; CHECK-NEXT: br i1 [[PREDRIGHT:%.*]], label [[LEFT:%.*]], label [[EXIT]] +; CHECK-NEXT: br i1 [[PREDRIGHT:%.*]], label [[IRR_GUARD]], label [[EXIT]] ; CHECK: exit: -; CHECK-NEXT: [[Z:%.*]] = phi i32 [ [[L_PHI]], [[LEFT]] ], [ [[R_PHI_MOVED]], [[RIGHT]] ] +; CHECK-NEXT: [[Z:%.*]] = phi i32 [ [[L_PHI_MOVED:%.*]], [[LEFT:%.*]] ], [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ] ; CHECK-NEXT: ret i32 [[Z]] ; CHECK: irr.guard: -; CHECK-NEXT: [[L_PHI_MOVED]] = phi i32 [ [[L_PHI_MOVED]], [[LEFT]] ], [ [[X:%.*]], [[ENTRY:%.*]] ] -; CHECK-NEXT: [[R_PHI_MOVED]] = phi i32 [ [[L_PHI]], [[LEFT]] ], [ [[Y:%.*]], [[ENTRY]] ] -; CHECK-NEXT: [[GUARD_RIGHT:%.*]] = phi i1 [ true, [[LEFT]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ] -; CHECK-NEXT: br i1 [[GUARD_RIGHT]], label [[RIGHT]], label [[LEFT]] +; CHECK-NEXT: [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY:%.*]] ], [ [[L_PHI_MOVED]], [[LEFT]] ] +; CHECK-NEXT: [[L_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ] +; CHECK-NEXT: [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY]] ], [ false, [[LEFT]] ] +; CHECK-NEXT: br i1 [[GUARD_LEFT]], label [[LEFT]], label [[RIGHT]] ; entry: br i1 %PredEntry, label %left, label %right @@ -86,18 +81,17 @@ define i32 @multiple_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC ; CHECK: B: ; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: C: -; CHECK-NEXT: br i1 [[PREDC:%.*]], label [[D:%.*]], label [[EXIT:%.*]] +; CHECK-NEXT: br i1 [[PREDC:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] ; CHECK: D: -; CHECK-NEXT: [[D_PHI:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_PHI_MOVED:%.*]], [[IRR_GUARD]] ] -; CHECK-NEXT: [[D_INC:%.*]] = add i32 [[D_PHI]], 1 +; CHECK-NEXT: [[D_INC:%.*]] = add i32 [[D_PHI_MOVED:%.*]], 1 ; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT]], label [[IRR_GUARD]] ; CHECK: exit: -; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED]], [[C]] ], [ [[D_INC]], [[D]] ] +; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_INC]], [[D:%.*]] ] ; CHECK-NEXT: ret i32 [[RET]] ; CHECK: irr.guard: -; CHECK-NEXT: [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ [[Y:%.*]], [[B]] ], [ [[A_INC]], [[A]] ] -; CHECK-NEXT: [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[Y]], [[B]] ], [ [[X]], [[A]] ] -; CHECK-NEXT: [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ [[PREDB_INV]], [[B]] ], [ [[PREDA:%.*]], [[A]] ] +; CHECK-NEXT: [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ [[Y:%.*]], [[B]] ], [ [[A_INC]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ] +; CHECK-NEXT: [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[Y]], [[B]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ] +; CHECK-NEXT: [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ [[PREDB_INV]], [[B]] ], [ [[PREDA:%.*]], [[A]] ], [ false, [[C]] ] ; CHECK-NEXT: br i1 [[GUARD_C]], label [[C]], label [[D]] ; entry: @@ -134,19 +128,18 @@ define i32 @separate_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC ; CHECK: B: ; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: C: -; CHECK-NEXT: [[C_PHI:%.*]] = phi i32 [ [[D_INC:%.*]], [[D:%.*]] ], [ [[C_PHI_MOVED:%.*]], [[IRR_GUARD]] ] ; CHECK-NEXT: br i1 [[PREDC:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]] ; CHECK: D: -; CHECK-NEXT: [[D_INC]] = add i32 [[D_PHI_MOVED:%.*]], 1 -; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT]], label [[C:%.*]] +; CHECK-NEXT: [[D_INC:%.*]] = add i32 [[D_PHI_MOVED:%.*]], 1 +; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT]], label [[IRR_GUARD]] ; CHECK: exit: -; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[C_PHI]], [[C]] ], [ [[D_INC]], [[D]] ] +; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_INC]], [[D:%.*]] ] ; CHECK-NEXT: ret i32 [[RET]] ; CHECK: irr.guard: -; CHECK-NEXT: [[C_PHI_MOVED]] = phi i32 [ [[C_PHI_MOVED]], [[C]] ], [ poison, [[B]] ], [ [[X]], [[A]] ] -; CHECK-NEXT: [[D_PHI_MOVED]] = phi i32 [ [[C_PHI]], [[C]] ], [ [[Y:%.*]], [[B]] ], [ poison, [[A]] ] -; CHECK-NEXT: [[GUARD_D:%.*]] = phi i1 [ true, [[C]] ], [ true, [[B]] ], [ false, [[A]] ] -; CHECK-NEXT: br i1 [[GUARD_D]], label [[D]], label [[C]] +; CHECK-NEXT: [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ poison, [[A]] ], [ [[C_PHI_MOVED]], [[C]] ], [ [[Y:%.*]], [[B]] ] +; CHECK-NEXT: [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ], [ poison, [[B]] ] +; CHECK-NEXT: [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ true, [[A]] ], [ false, [[C]] ], [ false, [[B]] ] +; CHECK-NEXT: br i1 [[GUARD_C]], label [[C]], label [[D]] ; entry: br i1 %PredEntry, label %A, label %B @@ -175,31 +168,30 @@ exit: define void @four_headers(i1 %PredEntry, i1 %PredX, i1 %PredY, i1 %PredD) { ; CHECK-LABEL: @four_headers( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[PREDY_INV:%.*]] = xor i1 [[PREDY:%.*]], true ; CHECK-NEXT: br i1 [[PREDENTRY:%.*]], label [[X:%.*]], label [[Y:%.*]] ; CHECK: X: ; CHECK-NEXT: br label [[IRR_GUARD:%.*]] ; CHECK: Y: ; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: A: -; CHECK-NEXT: br label [[B:%.*]] +; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: B: -; CHECK-NEXT: br label [[C:%.*]] +; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: C: ; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: D: -; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[A:%.*]] +; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]] ; CHECK: exit: ; CHECK-NEXT: ret void ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_D:%.*]] = phi i1 [ true, [[C]] ], [ [[PREDY_INV]], [[Y]] ], [ false, [[X]] ] -; CHECK-NEXT: [[GUARD_C:%.*]] = phi i1 [ false, [[C]] ], [ true, [[Y]] ], [ false, [[X]] ] -; CHECK-NEXT: [[GUARD_A:%.*]] = phi i1 [ false, [[C]] ], [ false, [[Y]] ], [ [[PREDX:%.*]], [[X]] ] -; CHECK-NEXT: br i1 [[GUARD_D]], label [[D:%.*]], label [[IRR_GUARD1:%.*]] +; CHECK-NEXT: [[GUARD_A:%.*]] = phi i1 [ true, [[D:%.*]] ], [ [[PREDX:%.*]], [[X]] ], [ false, [[A:%.*]] ], [ false, [[B:%.*]] ], [ false, [[Y]] ], [ false, [[C:%.*]] ] +; CHECK-NEXT: [[GUARD_B:%.*]] = phi i1 [ false, [[D]] ], [ true, [[X]] ], [ true, [[A]] ], [ false, [[B]] ], [ false, [[Y]] ], [ false, [[C]] ] +; CHECK-NEXT: [[GUARD_C:%.*]] = phi i1 [ false, [[D]] ], [ false, [[X]] ], [ false, [[A]] ], [ true, [[B]] ], [ [[PREDY:%.*]], [[Y]] ], [ false, [[C]] ] +; CHECK-NEXT: br i1 [[GUARD_A]], label [[A]], label [[IRR_GUARD1:%.*]] ; CHECK: irr.guard1: -; CHECK-NEXT: br i1 [[GUARD_C]], label [[C]], label [[IRR_GUARD2:%.*]] +; CHECK-NEXT: br i1 [[GUARD_B]], label [[B]], label [[IRR_GUARD2:%.*]] ; CHECK: irr.guard2: -; CHECK-NEXT: br i1 [[GUARD_A]], label [[A]], label [[B]] +; CHECK-NEXT: br i1 [[GUARD_C]], label [[C]], label [[D]] ; entry: br i1 %PredEntry, label %X, label %Y @@ -229,28 +221,26 @@ exit: define i32 @hidden_nodes(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) { ; CHECK-LABEL: @hidden_nodes( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true ; CHECK-NEXT: br label [[IRR_GUARD:%.*]] ; CHECK: A: -; CHECK-NEXT: [[A_PHI:%.*]] = phi i32 [ [[C_INC:%.*]], [[E:%.*]] ], [ [[A_PHI_MOVED:%.*]], [[IRR_GUARD]] ] -; CHECK-NEXT: [[A_INC:%.*]] = add i32 [[A_PHI]], 1 +; CHECK-NEXT: [[A_INC:%.*]] = add i32 [[A_PHI_MOVED:%.*]], 1 ; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: B: ; CHECK-NEXT: br label [[C:%.*]] ; CHECK: C: -; CHECK-NEXT: [[C_INC]] = add i32 [[B_PHI_MOVED:%.*]], 1 +; CHECK-NEXT: [[C_INC:%.*]] = add i32 [[B_PHI_MOVED:%.*]], 1 ; CHECK-NEXT: br label [[D:%.*]] ; CHECK: D: -; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[E]] +; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[E:%.*]] ; CHECK: E: -; CHECK-NEXT: br label [[A:%.*]] +; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: exit: ; CHECK-NEXT: ret i32 [[B_PHI_MOVED]] ; CHECK: irr.guard: -; CHECK-NEXT: [[A_PHI_MOVED]] = phi i32 [ [[A_PHI_MOVED]], [[A]] ], [ [[X:%.*]], [[ENTRY:%.*]] ] -; CHECK-NEXT: [[B_PHI_MOVED]] = phi i32 [ [[A_INC]], [[A]] ], [ [[Y:%.*]], [[ENTRY]] ] -; CHECK-NEXT: [[GUARD_B:%.*]] = phi i1 [ true, [[A]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ] -; CHECK-NEXT: br i1 [[GUARD_B]], label [[B:%.*]], label [[A]] +; CHECK-NEXT: [[B_PHI_MOVED]] = phi i32 [ poison, [[E]] ], [ [[Y:%.*]], [[ENTRY:%.*]] ], [ [[A_INC]], [[A:%.*]] ] +; CHECK-NEXT: [[A_PHI_MOVED]] = phi i32 [ [[C_INC]], [[E]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[A_PHI_MOVED]], [[A]] ] +; CHECK-NEXT: [[GUARD_A:%.*]] = phi i1 [ true, [[E]] ], [ [[PREDENTRY:%.*]], [[ENTRY]] ], [ false, [[A]] ] +; CHECK-NEXT: br i1 [[GUARD_A]], label [[A]], label [[B:%.*]] ; entry: br i1 %PredEntry, label %A, label %B diff --git a/llvm/test/Transforms/FixIrreducible/bug45623.ll b/llvm/test/Transforms/FixIrreducible/bug45623.ll index beddc967ebb0b6..c78b593e9319b1 100644 --- a/llvm/test/Transforms/FixIrreducible/bug45623.ll +++ b/llvm/test/Transforms/FixIrreducible/bug45623.ll @@ -1,7 +1,6 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt < %s -fix-irreducible --verify-loop-info -S | FileCheck %s ; RUN: opt < %s -passes='fix-irreducible,verify<loops>' -S | FileCheck %s -; RUN: opt < %s -passes='verify<loops>,fix-irreducible,verify<loops>' -S | FileCheck %s define dso_local void @tre_tnfa_run_backtrack() { ; CHECK-LABEL: @tre_tnfa_run_backtrack( @@ -14,7 +13,7 @@ define dso_local void @tre_tnfa_run_backtrack() { ; CHECK: if.then250: ; CHECK-NEXT: br label [[FOR_COND264:%.*]] ; CHECK: for.cond264: -; CHECK-NEXT: br i1 undef, label [[FOR_BODY267:%.*]], label [[BACKTRACK:%.*]] +; CHECK-NEXT: br i1 undef, label [[FOR_BODY267:%.*]], label [[IRR_GUARD]] ; CHECK: for.body267: ; CHECK-NEXT: br label [[FOR_COND264]] ; CHECK: if.end275: @@ -24,7 +23,7 @@ define dso_local void @tre_tnfa_run_backtrack() { ; CHECK: for.body345: ; CHECK-NEXT: br label [[FOR_COND342]] ; CHECK: for.end580: -; CHECK-NEXT: br label [[BACKTRACK]] +; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: backtrack: ; CHECK-NEXT: br i1 undef, label [[IF_THEN595:%.*]], label [[IF_ELSE629:%.*]] ; CHECK: if.then595: @@ -38,8 +37,8 @@ define dso_local void @tre_tnfa_run_backtrack() { ; CHECK: if.else629: ; CHECK-NEXT: br label [[RETRY]] ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_WHILE_BODY248:%.*]] = phi i1 [ true, [[FOR_END626]] ], [ undef, [[RETRY]] ] -; CHECK-NEXT: br i1 [[GUARD_WHILE_BODY248]], label [[WHILE_BODY248:%.*]], label [[BACKTRACK]] +; CHECK-NEXT: [[GUARD_BACKTRACK:%.*]] = phi i1 [ true, [[FOR_END580]] ], [ true, [[FOR_COND264]] ], [ undef, [[RETRY]] ], [ false, [[FOR_END626]] ] +; CHECK-NEXT: br i1 [[GUARD_BACKTRACK]], label [[BACKTRACK:%.*]], label [[WHILE_BODY248:%.*]] ; entry: br label %retry diff --git a/llvm/test/Transforms/FixIrreducible/nested.ll b/llvm/test/Transforms/FixIrreducible/nested.ll index 0cc6b473d62f69..1665bbf9930287 100644 --- a/llvm/test/Transforms/FixIrreducible/nested.ll +++ b/llvm/test/Transforms/FixIrreducible/nested.ll @@ -1,32 +1,29 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt < %s -fix-irreducible --verify-loop-info -S | FileCheck %s ; RUN: opt < %s -passes='fix-irreducible,verify<loops>' -S | FileCheck %s -; RUN: opt < %s -passes='verify<loops>,fix-irreducible,verify<loops>' -S | FileCheck %s define void @nested_irr_top_level(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5) { ; CHECK-LABEL: @nested_irr_top_level( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[PRED1_INV:%.*]] = xor i1 [[PRED1:%.*]], true -; CHECK-NEXT: [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true ; CHECK-NEXT: br label [[IRR_GUARD:%.*]] ; CHECK: A1: ; CHECK-NEXT: br label [[IRR_GUARD1:%.*]] ; CHECK: B1: ; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[A3:%.*]] ; CHECK: B2: -; CHECK-NEXT: br i1 [[PRED3:%.*]], label [[B1:%.*]], label [[A3]] +; CHECK-NEXT: br i1 [[PRED3:%.*]], label [[IRR_GUARD1]], label [[A3]] ; CHECK: A3: ; CHECK-NEXT: br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] ; CHECK: A2: -; CHECK-NEXT: br i1 [[PRED5:%.*]], label [[A1:%.*]], label [[EXIT]] +; CHECK-NEXT: br i1 [[PRED5:%.*]], label [[IRR_GUARD]], label [[EXIT]] ; CHECK: exit: ; CHECK-NEXT: ret void ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_A2:%.*]] = phi i1 [ true, [[A3]] ], [ [[PRED0_INV]], [[ENTRY:%.*]] ] -; CHECK-NEXT: br i1 [[GUARD_A2]], label [[A2:%.*]], label [[A1]] +; CHECK-NEXT: [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ] +; CHECK-NEXT: br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]] ; CHECK: irr.guard1: -; CHECK-NEXT: [[GUARD_B2:%.*]] = phi i1 [ true, [[B1]] ], [ [[PRED1_INV]], [[A1]] ] -; CHECK-NEXT: br i1 [[GUARD_B2]], label [[B2:%.*]], label [[B1]] +; CHECK-NEXT: [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED1:%.*]], [[A1]] ], [ false, [[B1:%.*]] ] +; CHECK-NEXT: br i1 [[GUARD_B1]], label [[B1]], label [[B2]] ; entry: br i1 %Pred0, label %A1, label %A2 @@ -53,8 +50,6 @@ exit: define void @nested_irr_in_loop(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6) { ; CHECK-LABEL: @nested_irr_in_loop( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[PRED1_INV:%.*]] = xor i1 [[PRED1:%.*]], true -; CHECK-NEXT: [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true ; CHECK-NEXT: br label [[H1:%.*]] ; CHECK: H1: ; CHECK-NEXT: br label [[IRR_GUARD:%.*]] @@ -63,21 +58,21 @@ define void @nested_irr_in_loop(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 % ; CHECK: B1: ; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[A3:%.*]] ; CHECK: B2: -; CHECK-NEXT: br i1 [[PRED3:%.*]], label [[B1:%.*]], label [[A3]] +; CHECK-NEXT: br i1 [[PRED3:%.*]], label [[IRR_GUARD1]], label [[A3]] ; CHECK: A3: ; CHECK-NEXT: br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[L1:%.*]] ; CHECK: A2: -; CHECK-NEXT: br i1 [[PRED5:%.*]], label [[A1:%.*]], label [[L1]] +; CHECK-NEXT: br i1 [[PRED5:%.*]], label [[IRR_GUARD]], label [[L1]] ; CHECK: L1: ; CHECK-NEXT: br i1 [[PRED6:%.*]], label [[EXIT:%.*]], label [[H1]] ; CHECK: exit: ; CHECK-NEXT: ret void ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_A2:%.*]] = phi i1 [ true, [[A3]] ], [ [[PRED0_INV]], [[H1]] ] -; CHECK-NEXT: br i1 [[GUARD_A2]], label [[A2:%.*]], label [[A1]] +; CHECK-NEXT: [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[H1]] ], [ false, [[A3]] ] +; CHECK-NEXT: br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]] ; CHECK: irr.guard1: -; CHECK-NEXT: [[GUARD_B2:%.*]] = phi i1 [ true, [[B1]] ], [ [[PRED1_INV]], [[A1]] ] -; CHECK-NEXT: br i1 [[GUARD_B2]], label [[B2:%.*]], label [[B1]] +; CHECK-NEXT: [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED1:%.*]], [[A1]] ], [ false, [[B1:%.*]] ] +; CHECK-NEXT: br i1 [[GUARD_B1]], label [[B1]], label [[B2]] ; entry: br label %H1 @@ -110,7 +105,6 @@ exit: define void @loop_in_irr(i1 %Pred0, i1 %Pred1, i1 %Pred2) { ; CHECK-LABEL: @loop_in_irr( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true ; CHECK-NEXT: br label [[IRR_GUARD:%.*]] ; CHECK: A1: ; CHECK-NEXT: br label [[H1:%.*]] @@ -121,12 +115,12 @@ define void @loop_in_irr(i1 %Pred0, i1 %Pred1, i1 %Pred2) { ; CHECK: A3: ; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] ; CHECK: A2: -; CHECK-NEXT: br label [[A1:%.*]] +; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: exit: ; CHECK-NEXT: ret void ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_A2:%.*]] = phi i1 [ true, [[A3]] ], [ [[PRED0_INV]], [[ENTRY:%.*]] ] -; CHECK-NEXT: br i1 [[GUARD_A2]], label [[A2:%.*]], label [[A1]] +; CHECK-NEXT: [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ] +; CHECK-NEXT: br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]] ; entry: br i1 %Pred0, label %A1, label %A2 @@ -150,65 +144,26 @@ exit: ret void } -define void @loop_in_irr_shared_entry(i1 %Pred0, i1 %Pred1, i1 %Pred2) { -; CHECK-LABEL: @loop_in_irr_shared_entry( -; CHECK-NEXT: entry: -; CHECK-NEXT: [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true -; CHECK-NEXT: br label [[IRR_GUARD:%.*]] -; CHECK: H1: -; CHECK-NEXT: br label [[L1:%.*]] -; CHECK: L1: -; CHECK-NEXT: br i1 [[PRED1:%.*]], label [[H1:%.*]], label [[A3:%.*]] -; CHECK: A3: -; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] -; CHECK: A2: -; CHECK-NEXT: br label [[H1]] -; CHECK: exit: -; CHECK-NEXT: ret void -; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_A2:%.*]] = phi i1 [ true, [[A3]] ], [ [[PRED0_INV]], [[ENTRY:%.*]] ] -; CHECK-NEXT: br i1 [[GUARD_A2]], label [[A2:%.*]], label [[H1]] -; -entry: - br i1 %Pred0, label %H1, label %A2 - -H1: - br label %L1 - -L1: - br i1 %Pred1, label %H1, label %A3 - -A3: - br i1 %Pred2, label %A2, label %exit - -A2: - br label %H1 - -exit: - ret void -} - define void @loop_in_irr_shared_header(i1 %Pred0, i1 %Pred1, i1 %Pred2) { ; CHECK-LABEL: @loop_in_irr_shared_header( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true ; CHECK-NEXT: br label [[IRR_GUARD:%.*]] ; CHECK: H1: ; CHECK-NEXT: br label [[L1:%.*]] ; CHECK: L1: ; CHECK-NEXT: br i1 [[PRED1:%.*]], label [[IRR_GUARD]], label [[A3:%.*]] ; CHECK: A3: -; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[A2:%.*]], label [[EXIT:%.*]] +; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] ; CHECK: A2: ; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: exit: ; CHECK-NEXT: ret void ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_H1:%.*]] = phi i1 [ true, [[A2]] ], [ true, [[L1]] ], [ [[PRED0_INV]], [[ENTRY:%.*]] ] +; CHECK-NEXT: [[GUARD_H1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ true, [[L1]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ] ; CHECK-NEXT: br i1 [[GUARD_H1]], label [[H1:%.*]], label [[A2]] ; entry: - br i1 %Pred0, label %A2, label %H1 + br i1 %Pred0, label %H1, label %A2 H1: br label %L1 @@ -226,81 +181,36 @@ exit: ret void } -define void @loop_irr_loop_shared_header(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3) { -; CHECK-LABEL: @loop_irr_loop_shared_header( -; CHECK-NEXT: entry: -; CHECK-NEXT: [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true -; CHECK-NEXT: br label [[H2:%.*]] -; CHECK: H2: -; CHECK-NEXT: br label [[IRR_GUARD:%.*]] -; CHECK: H1: -; CHECK-NEXT: br i1 [[PRED1:%.*]], label [[A3:%.*]], label [[IRR_GUARD]] -; CHECK: A3: -; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[A2:%.*]], label [[L2:%.*]] -; CHECK: A2: -; CHECK-NEXT: br label [[IRR_GUARD]] -; CHECK: L2: -; CHECK-NEXT: br i1 [[PRED3:%.*]], label [[H2]], label [[EXIT:%.*]] -; CHECK: exit: -; CHECK-NEXT: ret void -; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_H1:%.*]] = phi i1 [ true, [[A2]] ], [ true, [[H1:%.*]] ], [ [[PRED0_INV]], [[H2]] ] -; CHECK-NEXT: br i1 [[GUARD_H1]], label [[H1]], label [[A2]] -; -entry: - br label %H2 - -H2: - br i1 %Pred0, label %A2, label %H1 - -H1: - br i1 %Pred1, label %A3, label %H1 - -A3: - br i1 %Pred2, label %A2, label %L2 - -A2: - br label %H1 - -L2: - br i1 %Pred3, label %H2, label %exit - -exit: - ret void -} - define void @siblings_top_level(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6) { ; CHECK-LABEL: @siblings_top_level( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[PRED4_INV:%.*]] = xor i1 [[PRED4:%.*]], true -; CHECK-NEXT: [[PRED1_INV:%.*]] = xor i1 [[PRED1:%.*]], true ; CHECK-NEXT: br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]] ; CHECK: H1: -; CHECK-NEXT: br label [[IRR_GUARD:%.*]] +; CHECK-NEXT: br label [[IRR_GUARD1:%.*]] ; CHECK: A1: -; CHECK-NEXT: br label [[IRR_GUARD]] +; CHECK-NEXT: br label [[IRR_GUARD1]] ; CHECK: A2: -; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[A1:%.*]], label [[L1:%.*]] +; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[L1:%.*]] ; CHECK: L1: ; CHECK-NEXT: br i1 [[PRED3:%.*]], label [[H1]], label [[EXIT:%.*]] ; CHECK: fork1: -; CHECK-NEXT: br label [[IRR_GUARD1:%.*]] +; CHECK-NEXT: br label [[IRR_GUARD:%.*]] ; CHECK: B1: ; CHECK-NEXT: br label [[H2:%.*]] ; CHECK: H2: ; CHECK-NEXT: br label [[L2:%.*]] ; CHECK: L2: -; CHECK-NEXT: br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD1]] +; CHECK-NEXT: br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD]] ; CHECK: B2: -; CHECK-NEXT: br i1 [[PRED6:%.*]], label [[B1:%.*]], label [[EXIT]] +; CHECK-NEXT: br i1 [[PRED6:%.*]], label [[IRR_GUARD]], label [[EXIT]] ; CHECK: exit: ; CHECK-NEXT: ret void ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_A2:%.*]] = phi i1 [ true, [[A1]] ], [ [[PRED1_INV]], [[H1]] ] -; CHECK-NEXT: br i1 [[GUARD_A2]], label [[A2:%.*]], label [[A1]] +; CHECK-NEXT: [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED4:%.*]], [[FORK1]] ], [ false, [[L2]] ] +; CHECK-NEXT: br i1 [[GUARD_B1]], label [[B1:%.*]], label [[B2]] ; CHECK: irr.guard1: -; CHECK-NEXT: [[GUARD_B2:%.*]] = phi i1 [ true, [[L2]] ], [ [[PRED4_INV]], [[FORK1]] ] -; CHECK-NEXT: br i1 [[GUARD_B2]], label [[B2:%.*]], label [[B1]] +; CHECK-NEXT: [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED1:%.*]], [[H1]] ], [ false, [[A1:%.*]] ] +; CHECK-NEXT: br i1 [[GUARD_A1]], label [[A1]], label [[A2]] ; entry: br i1 %Pred0, label %H1, label %fork1 @@ -339,39 +249,37 @@ exit: define void @siblings_in_loop(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6, i1 %Pred7) { ; CHECK-LABEL: @siblings_in_loop( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[PRED4_INV:%.*]] = xor i1 [[PRED4:%.*]], true -; CHECK-NEXT: [[PRED1_INV:%.*]] = xor i1 [[PRED1:%.*]], true ; CHECK-NEXT: br label [[H0:%.*]] ; CHECK: H0: ; CHECK-NEXT: br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]] ; CHECK: H1: -; CHECK-NEXT: br label [[IRR_GUARD:%.*]] +; CHECK-NEXT: br label [[IRR_GUARD1:%.*]] ; CHECK: A1: -; CHECK-NEXT: br label [[IRR_GUARD]] +; CHECK-NEXT: br label [[IRR_GUARD1]] ; CHECK: A2: -; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[A1:%.*]], label [[L1:%.*]] +; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[L1:%.*]] ; CHECK: L1: ; CHECK-NEXT: br i1 [[PRED3:%.*]], label [[H1]], label [[L0:%.*]] ; CHECK: fork1: -; CHECK-NEXT: br label [[IRR_GUARD1:%.*]] +; CHECK-NEXT: br label [[IRR_GUARD:%.*]] ; CHECK: B1: ; CHECK-NEXT: br label [[H2:%.*]] ; CHECK: H2: ; CHECK-NEXT: br label [[L2:%.*]] ; CHECK: L2: -; CHECK-NEXT: br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD1]] +; CHECK-NEXT: br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD]] ; CHECK: B2: -; CHECK-NEXT: br i1 [[PRED6:%.*]], label [[B1:%.*]], label [[L0]] +; CHECK-NEXT: br i1 [[PRED6:%.*]], label [[IRR_GUARD]], label [[L0]] ; CHECK: L0: ; CHECK-NEXT: br i1 [[PRED7:%.*]], label [[EXIT:%.*]], label [[H0]] ; CHECK: exit: ; CHECK-NEXT: ret void ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_A2:%.*]] = phi i1 [ true, [[A1]] ], [ [[PRED1_INV]], [[H1]] ] -; CHECK-NEXT: br i1 [[GUARD_A2]], label [[A2:%.*]], label [[A1]] +; CHECK-NEXT: [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED4:%.*]], [[FORK1]] ], [ false, [[L2]] ] +; CHECK-NEXT: br i1 [[GUARD_B1]], label [[B1:%.*]], label [[B2]] ; CHECK: irr.guard1: -; CHECK-NEXT: [[GUARD_B2:%.*]] = phi i1 [ true, [[L2]] ], [ [[PRED4_INV]], [[FORK1]] ] -; CHECK-NEXT: br i1 [[GUARD_B2]], label [[B2:%.*]], label [[B1]] +; CHECK-NEXT: [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED1:%.*]], [[H1]] ], [ false, [[A1:%.*]] ] +; CHECK-NEXT: br i1 [[GUARD_A1]], label [[A1]], label [[A2]] ; entry: br label %H0 @@ -413,8 +321,8 @@ exit: ret void } -define void @irr_in_irr_shared_entry(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6, i1 %Pred7, i1 %Pred8, i1 %Pred9, i1 %Pred10, i1 %Pred11, i1 %Pred12, i1 %Pred13) { -; CHECK-LABEL: @irr_in_irr_shared_entry( +define void @irreducible_mountain_bug(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6, i1 %Pred7, i1 %Pred8, i1 %Pred9, i1 %Pred10, i1 %Pred11, i1 %Pred12, i1 %Pred13) { +; CHECK-LABEL: @irreducible_mountain_bug( ; CHECK-NEXT: entry: ; CHECK-NEXT: br i1 [[PRED0:%.*]], label [[IF_END:%.*]], label [[IF_THEN:%.*]] ; CHECK: if.end: @@ -430,13 +338,13 @@ define void @irr_in_irr_shared_entry(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, ; CHECK: while.cond: ; CHECK-NEXT: br i1 [[PRED3:%.*]], label [[IRR_GUARD:%.*]], label [[LOR_RHS:%.*]] ; CHECK: cond.true49: -; CHECK-NEXT: br i1 [[PRED4:%.*]], label [[IF_THEN69:%.*]], label [[IRR_GUARD1:%.*]] +; CHECK-NEXT: br i1 [[PRED4:%.*]], label [[IF_THEN69:%.*]], label [[WHILE_BODY63:%.*]] ; CHECK: while.body63: ; CHECK-NEXT: br i1 [[PRED5:%.*]], label [[EXIT:%.*]], label [[WHILE_COND47:%.*]] ; CHECK: while.cond47: -; CHECK-NEXT: br i1 [[PRED6:%.*]], label [[COND_TRUE49:%.*]], label [[IRR_GUARD]] +; CHECK-NEXT: br label [[IRR_GUARD]] ; CHECK: cond.end61: -; CHECK-NEXT: br i1 [[PRED7:%.*]], label [[IRR_GUARD1]], label [[WHILE_COND]] +; CHECK-NEXT: br i1 [[PRED7:%.*]], label [[WHILE_BODY63]], label [[WHILE_COND]] ; CHECK: if.then69: ; CHECK-NEXT: br i1 [[PRED8:%.*]], label [[EXIT]], label [[WHILE_COND]] ; CHECK: lor.rhs: @@ -458,11 +366,8 @@ define void @irr_in_irr_shared_entry(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, ; CHECK: exit: ; CHECK-NEXT: ret void ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_COND_END61:%.*]] = phi i1 [ true, [[WHILE_COND47]] ], [ true, [[LOR_RHS]] ], [ false, [[WHILE_COND]] ] -; CHECK-NEXT: br i1 [[GUARD_COND_END61]], label [[COND_END61:%.*]], label [[IRR_GUARD1]] -; CHECK: irr.guard1: -; CHECK-NEXT: [[GUARD_WHILE_BODY63:%.*]] = phi i1 [ true, [[COND_TRUE49]] ], [ true, [[COND_END61]] ], [ false, [[IRR_GUARD]] ] -; CHECK-NEXT: br i1 [[GUARD_WHILE_BODY63]], label [[WHILE_BODY63:%.*]], label [[COND_TRUE49]] +; CHECK-NEXT: [[GUARD_COND_TRUE49:%.*]] = phi i1 [ [[PRED6:%.*]], [[WHILE_COND47]] ], [ true, [[WHILE_COND]] ], [ false, [[LOR_RHS]] ] +; CHECK-NEXT: br i1 [[GUARD_COND_TRUE49]], label [[COND_TRUE49:%.*]], label [[COND_END61:%.*]] ; entry: br i1 %Pred0, label %if.end, label %if.then diff --git a/llvm/test/Transforms/FixIrreducible/switch.ll b/llvm/test/Transforms/FixIrreducible/switch.ll index 4d3d9498b284d2..f648b597b84695 100644 --- a/llvm/test/Transforms/FixIrreducible/switch.ll +++ b/llvm/test/Transforms/FixIrreducible/switch.ll @@ -1,12 +1,10 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt < %s -lowerswitch -fix-irreducible --verify-loop-info -S | FileCheck %s ; RUN: opt < %s -passes='lower-switch,fix-irreducible,verify<loops>' -S | FileCheck %s -; RUN: opt < %s -passes='lower-switch,verify<loops>,fix-irreducible,verify<loops>' -S | FileCheck %s define void @loop_1(i32 %Value, i1 %PredEntry, i1 %PredD) { ; CHECK-LABEL: @loop_1( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true ; CHECK-NEXT: br label [[IRR_GUARD:%.*]] ; CHECK: A: ; CHECK-NEXT: br label [[IRR_GUARD]] @@ -20,12 +18,12 @@ define void @loop_1(i32 %Value, i1 %PredEntry, i1 %PredD) { ; CHECK-NEXT: br i1 [[SWITCHLEAF2]], label [[IRR_GUARD]], label [[EXIT:%.*]] ; CHECK: LeafBlock: ; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VALUE]], 0 -; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[A:%.*]], label [[EXIT]] +; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[IRR_GUARD]], label [[EXIT]] ; CHECK: exit: ; CHECK-NEXT: ret void ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_B:%.*]] = phi i1 [ true, [[LEAFBLOCK1]] ], [ true, [[A]] ], [ [[PREDENTRY_INV]], [[ENTRY:%.*]] ] -; CHECK-NEXT: br i1 [[GUARD_B]], label [[B:%.*]], label [[A]] +; CHECK-NEXT: [[GUARD_A:%.*]] = phi i1 [ true, [[LEAFBLOCK]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[LEAFBLOCK1]] ], [ false, [[A:%.*]] ] +; CHECK-NEXT: br i1 [[GUARD_A]], label [[A]], label [[B:%.*]] ; entry: br i1 %PredEntry, label %A, label %B diff --git a/llvm/test/Transforms/FixIrreducible/unreachable.ll b/llvm/test/Transforms/FixIrreducible/unreachable.ll index cc9a29b2a8d711..e61bd2b5a0ae45 100644 --- a/llvm/test/Transforms/FixIrreducible/unreachable.ll +++ b/llvm/test/Transforms/FixIrreducible/unreachable.ll @@ -1,7 +1,6 @@ ; NOTE: Do not autogenerate ; RUN: opt < %s -fix-irreducible --verify-loop-info -S | FileCheck %s ; RUN: opt < %s -passes='fix-irreducible,verify<loops>' -S | FileCheck %s -; RUN: opt < %s -passes='verify<loops>,fix-irreducible,verify<loops>' -S | FileCheck %s ; CHECK-LABEL: @unreachable( ; CHECK: entry: diff --git a/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fix-reducible.ll b/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fix-reducible.ll index d09d7454793bbf..172a0da8d2d4bc 100644 --- a/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fix-reducible.ll +++ b/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fix-reducible.ll @@ -9,49 +9,37 @@ define void @irreducible(i1 %PredEntry, i1 %PredB1, i1 %PredB2, i1 %PredB3, i1 % ; CHECK-LABEL: @irreducible( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[PREDB2_INV:%.*]] = xor i1 [[PREDB2:%.*]], true -; CHECK-NEXT: [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true +; CHECK-NEXT: [[PREDB1_INV:%.*]] = xor i1 [[PREDB1:%.*]], true ; CHECK-NEXT: br label [[IRR_GUARD:%.*]] -; CHECK: Flow4: -; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ true, [[B3:%.*]] ], [ undef, [[B2:%.*]] ] -; CHECK-NEXT: [[TMP1:%.*]] = phi i1 [ [[PREDB3:%.*]], [[B3]] ], [ true, [[B2]] ] -; CHECK-NEXT: [[TMP2:%.*]] = phi i1 [ [[PREDB3]], [[B3]] ], [ false, [[B2]] ] -; CHECK-NEXT: br label [[FLOW3:%.*]] +; CHECK: Flow: +; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ [[PREDB4:%.*]], [[B4:%.*]] ], [ false, [[IRR_GUARD]] ] +; CHECK-NEXT: [[TMP1:%.*]] = phi i1 [ false, [[B4]] ], [ true, [[IRR_GUARD]] ] +; CHECK-NEXT: br i1 [[TMP1]], label [[B1:%.*]], label [[FLOW1:%.*]] ; CHECK: B1: -; CHECK-NEXT: br label [[FLOW5:%.*]] -; CHECK: Flow2: -; CHECK-NEXT: [[TMP3:%.*]] = phi i1 [ [[TMP9:%.*]], [[FLOW5]] ], [ [[TMP11:%.*]], [[FLOW:%.*]] ] -; CHECK-NEXT: [[TMP4:%.*]] = phi i1 [ [[TMP10:%.*]], [[FLOW5]] ], [ [[TMP12:%.*]], [[FLOW]] ] -; CHECK-NEXT: [[TMP5:%.*]] = phi i1 [ [[TMP7:%.*]], [[FLOW5]] ], [ true, [[FLOW]] ] -; CHECK-NEXT: br i1 true, label [[FLOW6:%.*]], label [[FLOW]] +; CHECK-NEXT: br label [[FLOW1]] +; CHECK: Flow1: +; CHECK-NEXT: [[TMP2:%.*]] = phi i1 [ [[PREDB1_INV]], [[B1]] ], [ [[TMP0]], [[FLOW:%.*]] ] +; CHECK-NEXT: br i1 [[TMP2]], label [[B2:%.*]], label [[FLOW2:%.*]] ; CHECK: B2: -; CHECK-NEXT: br i1 [[PREDB2_INV]], label [[B3]], label [[FLOW4:%.*]] -; CHECK: Flow3: -; CHECK-NEXT: [[TMP6:%.*]] = phi i1 [ [[TMP0]], [[FLOW4]] ], [ undef, [[IRR_GUARD1:%.*]] ] -; CHECK-NEXT: [[TMP7]] = phi i1 [ [[TMP1]], [[FLOW4]] ], [ true, [[IRR_GUARD1]] ] -; CHECK-NEXT: [[TMP8:%.*]] = phi i1 [ [[TMP2]], [[FLOW4]] ], [ true, [[IRR_GUARD1]] ] -; CHECK-NEXT: br i1 [[TMP8]], label [[B1:%.*]], label [[FLOW5]] +; CHECK-NEXT: br i1 [[PREDB2_INV]], label [[B3:%.*]], label [[FLOW3:%.*]] +; CHECK: Flow2: +; CHECK-NEXT: [[TMP3:%.*]] = phi i1 [ [[TMP5:%.*]], [[FLOW3]] ], [ undef, [[FLOW1]] ] +; CHECK-NEXT: [[TMP4:%.*]] = phi i1 [ [[TMP6:%.*]], [[FLOW3]] ], [ true, [[FLOW1]] ] +; CHECK-NEXT: br i1 [[TMP4]], label [[EXIT:%.*]], label [[IRR_GUARD]] ; CHECK: B3: -; CHECK-NEXT: br label [[FLOW4]] +; CHECK-NEXT: br label [[FLOW3]] ; CHECK: B4: ; CHECK-NEXT: br label [[FLOW]] -; CHECK: Flow5: -; CHECK-NEXT: [[TMP9]] = phi i1 [ undef, [[B1]] ], [ [[TMP6]], [[FLOW3]] ] -; CHECK-NEXT: [[TMP10]] = phi i1 [ true, [[B1]] ], [ undef, [[FLOW3]] ] -; CHECK-NEXT: br label [[FLOW2:%.*]] -; CHECK: Flow6: -; CHECK-NEXT: br i1 [[TMP5]], label [[EXIT:%.*]], label [[IRR_GUARD]] +; CHECK: Flow3: +; CHECK-NEXT: [[TMP5]] = phi i1 [ [[PREDB3:%.*]], [[B3]] ], [ undef, [[B2]] ] +; CHECK-NEXT: [[TMP6]] = phi i1 [ false, [[B3]] ], [ true, [[B2]] ] +; CHECK-NEXT: br label [[FLOW2]] ; CHECK: exit: ; CHECK-NEXT: ret void ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_B4:%.*]] = phi i1 [ [[PREDENTRY_INV]], [[ENTRY:%.*]] ], [ [[TMP3]], [[FLOW6]] ] -; CHECK-NEXT: br i1 [[GUARD_B4]], label [[B4:%.*]], label [[FLOW]] -; CHECK: Flow: -; CHECK-NEXT: [[TMP11]] = phi i1 [ [[TMP3]], [[FLOW2]] ], [ undef, [[B4]] ], [ undef, [[IRR_GUARD]] ] -; CHECK-NEXT: [[TMP12]] = phi i1 [ [[TMP4]], [[FLOW2]] ], [ true, [[B4]] ], [ false, [[IRR_GUARD]] ] -; CHECK-NEXT: [[TMP13:%.*]] = phi i1 [ false, [[FLOW2]] ], [ [[PREDB4:%.*]], [[B4]] ], [ true, [[IRR_GUARD]] ] -; CHECK-NEXT: br i1 [[TMP13]], label [[IRR_GUARD1]], label [[FLOW2]] -; CHECK: irr.guard1: -; CHECK-NEXT: br i1 [[TMP12]], label [[B2]], label [[FLOW3]] +; CHECK-NEXT: [[GUARD_B1:%.*]] = phi i1 [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ [[TMP3]], [[FLOW2]] ] +; CHECK-NEXT: [[GUARD_B1_INV:%.*]] = xor i1 [[GUARD_B1]], true +; CHECK-NEXT: br i1 [[GUARD_B1_INV]], label [[B4]], label [[FLOW]] ; { entry: diff --git a/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll b/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll index 912beed6b2eed3..f588d3fe7cef3e 100644 --- a/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll +++ b/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll @@ -8,138 +8,126 @@ define void @irreducible_mountain_bug(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3 ; CHECK-NEXT: [[PRED2_INV:%.*]] = xor i1 [[PRED2:%.*]], true ; CHECK-NEXT: [[PRED3_INV:%.*]] = xor i1 [[PRED3:%.*]], true ; CHECK-NEXT: [[PRED5_INV:%.*]] = xor i1 [[PRED5:%.*]], true +; CHECK-NEXT: [[PRED4_INV:%.*]] = xor i1 [[PRED4:%.*]], true ; CHECK-NEXT: [[PRED10_INV:%.*]] = xor i1 [[PRED10:%.*]], true ; CHECK-NEXT: [[PRED11_INV:%.*]] = xor i1 [[PRED11:%.*]], true ; CHECK-NEXT: [[PRED12_INV:%.*]] = xor i1 [[PRED12:%.*]], true ; CHECK-NEXT: [[PRED13_INV:%.*]] = xor i1 [[PRED13:%.*]], true -; CHECK-NEXT: br i1 [[PRED0_INV]], label [[IF_THEN:%.*]], label [[FLOW22:%.*]] -; CHECK: Flow22: -; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ false, [[FLOW5:%.*]] ], [ true, [[ENTRY:%.*]] ] -; CHECK-NEXT: br i1 [[TMP0]], label [[IF_END:%.*]], label [[FLOW23:%.*]] +; CHECK-NEXT: br i1 [[PRED0_INV]], label [[IF_THEN:%.*]], label [[FLOW19:%.*]] +; CHECK: Flow19: +; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ false, [[FLOW3:%.*]] ], [ true, [[ENTRY:%.*]] ] +; CHECK-NEXT: br i1 [[TMP0]], label [[IF_END:%.*]], label [[FLOW20:%.*]] ; CHECK: if.end: -; CHECK-NEXT: br i1 [[PRED1_INV]], label [[IF_ELSE:%.*]], label [[FLOW21:%.*]] -; CHECK: Flow21: +; CHECK-NEXT: br i1 [[PRED1_INV]], label [[IF_ELSE:%.*]], label [[FLOW18:%.*]] +; CHECK: Flow18: ; CHECK-NEXT: [[TMP1:%.*]] = phi i1 [ false, [[IF_ELSE]] ], [ true, [[IF_END]] ] ; CHECK-NEXT: br i1 [[TMP1]], label [[IF_THEN7:%.*]], label [[IF_END16:%.*]] ; CHECK: if.then7: ; CHECK-NEXT: br label [[IF_END16]] ; CHECK: if.else: -; CHECK-NEXT: br label [[FLOW21]] -; CHECK: Flow23: +; CHECK-NEXT: br label [[FLOW18]] +; CHECK: Flow20: ; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: if.end16: -; CHECK-NEXT: br i1 [[PRED2_INV]], label [[IF_THEN39:%.*]], label [[FLOW19:%.*]] -; CHECK: Flow19: -; CHECK-NEXT: [[TMP2:%.*]] = phi i1 [ false, [[FLOW7:%.*]] ], [ true, [[IF_END16]] ] -; CHECK-NEXT: br i1 [[TMP2]], label [[WHILE_COND_PREHEADER:%.*]], label [[FLOW20:%.*]] +; CHECK-NEXT: br i1 [[PRED2_INV]], label [[IF_THEN39:%.*]], label [[FLOW16:%.*]] +; CHECK: Flow16: +; CHECK-NEXT: [[TMP2:%.*]] = phi i1 [ false, [[FLOW5:%.*]] ], [ true, [[IF_END16]] ] +; CHECK-NEXT: br i1 [[TMP2]], label [[WHILE_COND_PREHEADER:%.*]], label [[FLOW17:%.*]] ; CHECK: while.cond.preheader: ; CHECK-NEXT: br label [[WHILE_COND:%.*]] -; CHECK: Flow20: -; CHECK-NEXT: br label [[FLOW23]] +; CHECK: Flow17: +; CHECK-NEXT: br label [[FLOW20]] ; CHECK: while.cond: -; CHECK-NEXT: br i1 [[PRED3_INV]], label [[LOR_RHS:%.*]], label [[FLOW15:%.*]] -; CHECK: Flow10: -; CHECK-NEXT: [[TMP3:%.*]] = phi i1 [ false, [[WHILE_COND47:%.*]] ], [ true, [[WHILE_BODY63:%.*]] ] -; CHECK-NEXT: [[TMP4:%.*]] = phi i1 [ [[PRED6:%.*]], [[WHILE_COND47]] ], [ false, [[WHILE_BODY63]] ] -; CHECK-NEXT: br label [[FLOW9:%.*]] +; CHECK-NEXT: br i1 [[PRED3_INV]], label [[LOR_RHS:%.*]], label [[FLOW12:%.*]] +; CHECK: Flow7: +; CHECK-NEXT: [[TMP3:%.*]] = phi i1 [ false, [[COND_END61:%.*]] ], [ undef, [[IRR_GUARD:%.*]] ] +; CHECK-NEXT: [[TMP4:%.*]] = phi i1 [ true, [[COND_END61]] ], [ undef, [[IRR_GUARD]] ] +; CHECK-NEXT: [[TMP5:%.*]] = phi i1 [ [[PRED7:%.*]], [[COND_END61]] ], [ false, [[IRR_GUARD]] ] +; CHECK-NEXT: [[TMP6:%.*]] = phi i1 [ false, [[COND_END61]] ], [ true, [[IRR_GUARD]] ] +; CHECK-NEXT: br i1 [[TMP6]], label [[COND_TRUE49:%.*]], label [[FLOW8:%.*]] ; CHECK: cond.true49: -; CHECK-NEXT: br label [[FLOW11:%.*]] +; CHECK-NEXT: br label [[FLOW8]] +; CHECK: Flow8: +; CHECK-NEXT: [[TMP7:%.*]] = phi i1 [ false, [[COND_TRUE49]] ], [ [[TMP3]], [[FLOW7:%.*]] ] +; CHECK-NEXT: [[TMP8:%.*]] = phi i1 [ false, [[COND_TRUE49]] ], [ [[TMP4]], [[FLOW7]] ] +; CHECK-NEXT: [[TMP9:%.*]] = phi i1 [ [[PRED4_INV]], [[COND_TRUE49]] ], [ [[TMP5]], [[FLOW7]] ] +; CHECK-NEXT: br i1 [[TMP9]], label [[WHILE_BODY63:%.*]], label [[FLOW9:%.*]] ; CHECK: while.body63: -; CHECK-NEXT: br i1 [[PRED5_INV]], label [[WHILE_COND47]], label [[FLOW10:%.*]] +; CHECK-NEXT: br i1 [[PRED5_INV]], label [[WHILE_COND47:%.*]], label [[FLOW10:%.*]] ; CHECK: Flow9: -; CHECK-NEXT: [[TMP5:%.*]] = phi i1 [ [[TMP3]], [[FLOW10]] ], [ undef, [[IRR_GUARD1:%.*]] ] -; CHECK-NEXT: [[TMP6:%.*]] = phi i1 [ false, [[FLOW10]] ], [ undef, [[IRR_GUARD1]] ] -; CHECK-NEXT: [[TMP7:%.*]] = phi i1 [ true, [[FLOW10]] ], [ undef, [[IRR_GUARD1]] ] -; CHECK-NEXT: [[TMP8:%.*]] = phi i1 [ true, [[FLOW10]] ], [ undef, [[IRR_GUARD1]] ] -; CHECK-NEXT: [[TMP9:%.*]] = phi i1 [ [[TMP4]], [[FLOW10]] ], [ true, [[IRR_GUARD1]] ] -; CHECK-NEXT: br i1 [[TMP9]], label [[COND_TRUE49:%.*]], label [[FLOW11]] +; CHECK-NEXT: [[TMP10:%.*]] = phi i1 [ [[TMP22:%.*]], [[FLOW10]] ], [ undef, [[FLOW8]] ] +; CHECK-NEXT: [[TMP11:%.*]] = phi i1 [ true, [[FLOW10]] ], [ [[TMP7]], [[FLOW8]] ] +; CHECK-NEXT: [[TMP12:%.*]] = phi i1 [ false, [[FLOW10]] ], [ [[TMP8]], [[FLOW8]] ] +; CHECK-NEXT: [[TMP13:%.*]] = phi i1 [ false, [[FLOW10]] ], [ undef, [[FLOW8]] ] +; CHECK-NEXT: [[TMP14:%.*]] = phi i1 [ [[TMP23:%.*]], [[FLOW10]] ], [ true, [[FLOW8]] ] +; CHECK-NEXT: [[DOTINV11:%.*]] = xor i1 [[TMP11]], true +; CHECK-NEXT: [[DOTINV:%.*]] = xor i1 [[TMP12]], true +; CHECK-NEXT: br i1 [[TMP14]], label [[LOOP_EXIT_GUARD1:%.*]], label [[IRR_GUARD]] ; CHECK: while.cond47: ; CHECK-NEXT: br label [[FLOW10]] ; CHECK: cond.end61: -; CHECK-NEXT: br label [[FLOW12:%.*]] -; CHECK: Flow17: -; CHECK-NEXT: [[TMP10:%.*]] = phi i1 [ [[TMP19:%.*]], [[FLOW18:%.*]] ], [ undef, [[LOOP_EXIT_GUARD2:%.*]] ] -; CHECK-NEXT: [[TMP11:%.*]] = phi i1 [ [[TMP20:%.*]], [[FLOW18]] ], [ [[DOTINV:%.*]], [[LOOP_EXIT_GUARD2]] ] -; CHECK-NEXT: br label [[FLOW16:%.*]] +; CHECK-NEXT: br label [[FLOW7]] +; CHECK: Flow14: +; CHECK-NEXT: [[TMP15:%.*]] = phi i1 [ [[TMP20:%.*]], [[FLOW15:%.*]] ], [ undef, [[LOOP_EXIT_GUARD1]] ] +; CHECK-NEXT: [[TMP16:%.*]] = phi i1 [ [[TMP21:%.*]], [[FLOW15]] ], [ [[DOTINV]], [[LOOP_EXIT_GUARD1]] ] +; CHECK-NEXT: br label [[FLOW13:%.*]] ; CHECK: if.then69: -; CHECK-NEXT: br label [[FLOW18]] -; CHECK: lor.rhs: ; CHECK-NEXT: br label [[FLOW15]] +; CHECK: lor.rhs: +; CHECK-NEXT: br label [[FLOW12]] ; CHECK: while.end76: -; CHECK-NEXT: br label [[FLOW8:%.*]] +; CHECK-NEXT: br label [[FLOW6:%.*]] ; CHECK: if.then39: -; CHECK-NEXT: br i1 [[PRED10_INV]], label [[IF_END_I145:%.*]], label [[FLOW7]] +; CHECK-NEXT: br i1 [[PRED10_INV]], label [[IF_END_I145:%.*]], label [[FLOW5]] ; CHECK: if.end.i145: -; CHECK-NEXT: br i1 [[PRED11_INV]], label [[IF_END8_I149:%.*]], label [[FLOW6:%.*]] +; CHECK-NEXT: br i1 [[PRED11_INV]], label [[IF_END8_I149:%.*]], label [[FLOW4:%.*]] ; CHECK: if.end8.i149: -; CHECK-NEXT: br label [[FLOW6]] +; CHECK-NEXT: br label [[FLOW4]] ; CHECK: if.then: -; CHECK-NEXT: br i1 [[PRED12_INV]], label [[IF_END_I:%.*]], label [[FLOW5]] +; CHECK-NEXT: br i1 [[PRED12_INV]], label [[IF_END_I:%.*]], label [[FLOW3]] ; CHECK: if.end.i: ; CHECK-NEXT: br i1 [[PRED13_INV]], label [[IF_END8_I:%.*]], label [[FLOW:%.*]] ; CHECK: if.end8.i: ; CHECK-NEXT: br label [[FLOW]] ; CHECK: Flow: +; CHECK-NEXT: br label [[FLOW3]] +; CHECK: Flow3: +; CHECK-NEXT: br label [[FLOW19]] +; CHECK: Flow4: ; CHECK-NEXT: br label [[FLOW5]] ; CHECK: Flow5: -; CHECK-NEXT: br label [[FLOW22]] +; CHECK-NEXT: br label [[FLOW16]] ; CHECK: Flow6: -; CHECK-NEXT: br label [[FLOW7]] -; CHECK: Flow7: -; CHECK-NEXT: br label [[FLOW19]] -; CHECK: Flow8: -; CHECK-NEXT: br label [[FLOW20]] +; CHECK-NEXT: br label [[FLOW17]] ; CHECK: exit: ; CHECK-NEXT: ret void -; CHECK: Flow15: -; CHECK-NEXT: [[TMP12:%.*]] = phi i1 [ true, [[LOR_RHS]] ], [ undef, [[WHILE_COND]] ] -; CHECK-NEXT: [[TMP13:%.*]] = phi i1 [ true, [[LOR_RHS]] ], [ false, [[WHILE_COND]] ] -; CHECK-NEXT: [[TMP14:%.*]] = phi i1 [ [[PRED9:%.*]], [[LOR_RHS]] ], [ true, [[WHILE_COND]] ] -; CHECK-NEXT: br i1 [[TMP14]], label [[IRR_GUARD:%.*]], label [[FLOW16]] -; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_COND_END61:%.*]] = phi i1 [ [[TMP28:%.*]], [[FLOW13:%.*]] ], [ [[TMP13]], [[FLOW15]] ] -; CHECK-NEXT: br i1 [[GUARD_COND_END61]], label [[COND_END61:%.*]], label [[FLOW12]] ; CHECK: Flow12: -; CHECK-NEXT: [[TMP15:%.*]] = phi i1 [ false, [[COND_END61]] ], [ undef, [[IRR_GUARD]] ] -; CHECK-NEXT: [[TMP16:%.*]] = phi i1 [ true, [[COND_END61]] ], [ undef, [[IRR_GUARD]] ] -; CHECK-NEXT: [[TMP17:%.*]] = phi i1 [ true, [[COND_END61]] ], [ false, [[IRR_GUARD]] ] -; CHECK-NEXT: [[TMP18:%.*]] = phi i1 [ [[PRED7:%.*]], [[COND_END61]] ], [ true, [[IRR_GUARD]] ] -; CHECK-NEXT: br i1 [[TMP18]], label [[IRR_GUARD1]], label [[FLOW13]] -; CHECK: irr.guard1: -; CHECK-NEXT: [[GUARD_WHILE_BODY63:%.*]] = phi i1 [ [[TMP23:%.*]], [[FLOW11]] ], [ [[TMP17]], [[FLOW12]] ] -; CHECK-NEXT: br i1 [[GUARD_WHILE_BODY63]], label [[WHILE_BODY63]], label [[FLOW9]] -; CHECK: Flow18: -; CHECK-NEXT: [[TMP19]] = phi i1 [ false, [[IF_THEN69:%.*]] ], [ [[TMP31:%.*]], [[LOOP_EXIT_GUARD3:%.*]] ] -; CHECK-NEXT: [[TMP20]] = phi i1 [ [[PRED8:%.*]], [[IF_THEN69]] ], [ [[DOTINV]], [[LOOP_EXIT_GUARD3]] ] -; CHECK-NEXT: br label [[FLOW17:%.*]] +; CHECK-NEXT: [[TMP17:%.*]] = phi i1 [ true, [[LOR_RHS]] ], [ undef, [[WHILE_COND]] ] +; CHECK-NEXT: [[TMP18:%.*]] = phi i1 [ false, [[LOR_RHS]] ], [ true, [[WHILE_COND]] ] +; CHECK-NEXT: [[TMP19:%.*]] = phi i1 [ [[PRED9:%.*]], [[LOR_RHS]] ], [ [[PRED3]], [[WHILE_COND]] ] +; CHECK-NEXT: br i1 [[TMP19]], label [[IRR_GUARD]], label [[FLOW13]] +; CHECK: irr.guard: +; CHECK-NEXT: [[GUARD_COND_TRUE49:%.*]] = phi i1 [ [[TMP10]], [[FLOW9]] ], [ [[TMP18]], [[FLOW12]] ] +; CHECK-NEXT: [[GUARD_COND_TRUE49_INV:%.*]] = xor i1 [[GUARD_COND_TRUE49]], true +; CHECK-NEXT: br i1 [[GUARD_COND_TRUE49_INV]], label [[COND_END61]], label [[FLOW7]] +; CHECK: Flow15: +; CHECK-NEXT: [[TMP20]] = phi i1 [ false, [[IF_THEN69:%.*]] ], [ [[TMP13]], [[LOOP_EXIT_GUARD2:%.*]] ] +; CHECK-NEXT: [[TMP21]] = phi i1 [ [[PRED8:%.*]], [[IF_THEN69]] ], [ [[DOTINV]], [[LOOP_EXIT_GUARD2]] ] +; CHECK-NEXT: br label [[FLOW14:%.*]] ; CHECK: loop.exit.guard: -; CHECK-NEXT: br i1 [[TMP21:%.*]], label [[WHILE_END76:%.*]], label [[FLOW8]] -; CHECK: Flow16: -; CHECK-NEXT: [[TMP21]] = phi i1 [ [[TMP10]], [[FLOW17]] ], [ [[TMP12]], [[FLOW15]] ] -; CHECK-NEXT: [[TMP22:%.*]] = phi i1 [ [[TMP11]], [[FLOW17]] ], [ true, [[FLOW15]] ] -; CHECK-NEXT: br i1 [[TMP22]], label [[LOOP_EXIT_GUARD:%.*]], label [[WHILE_COND]] -; CHECK: loop.exit.guard2: -; CHECK-NEXT: br i1 [[DOTINV]], label [[LOOP_EXIT_GUARD3]], label [[FLOW17]] -; CHECK: loop.exit.guard3: -; CHECK-NEXT: br i1 [[DOTINV14:%.*]], label [[IF_THEN69]], label [[FLOW18]] -; CHECK: Flow11: -; CHECK-NEXT: [[TMP23]] = phi i1 [ true, [[COND_TRUE49]] ], [ undef, [[FLOW9]] ] -; CHECK-NEXT: [[TMP24:%.*]] = phi i1 [ true, [[COND_TRUE49]] ], [ [[TMP5]], [[FLOW9]] ] -; CHECK-NEXT: [[TMP25:%.*]] = phi i1 [ false, [[COND_TRUE49]] ], [ [[TMP6]], [[FLOW9]] ] -; CHECK-NEXT: [[TMP26:%.*]] = phi i1 [ false, [[COND_TRUE49]] ], [ [[TMP7]], [[FLOW9]] ] -; CHECK-NEXT: [[TMP27:%.*]] = phi i1 [ [[PRED4:%.*]], [[COND_TRUE49]] ], [ true, [[FLOW9]] ] -; CHECK-NEXT: br i1 [[TMP27]], label [[LOOP_EXIT_GUARD4:%.*]], label [[IRR_GUARD1]] +; CHECK-NEXT: br i1 [[TMP24:%.*]], label [[WHILE_END76:%.*]], label [[FLOW6]] +; CHECK: Flow10: +; CHECK-NEXT: [[TMP22]] = phi i1 [ [[PRED6:%.*]], [[WHILE_COND47]] ], [ undef, [[WHILE_BODY63]] ] +; CHECK-NEXT: [[TMP23]] = phi i1 [ false, [[WHILE_COND47]] ], [ true, [[WHILE_BODY63]] ] +; CHECK-NEXT: br label [[FLOW9]] ; CHECK: Flow13: -; CHECK-NEXT: [[TMP28]] = phi i1 [ [[TMP8]], [[LOOP_EXIT_GUARD4]] ], [ undef, [[FLOW12]] ] -; CHECK-NEXT: [[TMP29:%.*]] = phi i1 [ [[TMP26]], [[LOOP_EXIT_GUARD4]] ], [ [[TMP15]], [[FLOW12]] ] -; CHECK-NEXT: [[TMP30:%.*]] = phi i1 [ [[TMP25]], [[LOOP_EXIT_GUARD4]] ], [ [[TMP16]], [[FLOW12]] ] -; CHECK-NEXT: [[TMP31]] = phi i1 [ [[TMP6]], [[LOOP_EXIT_GUARD4]] ], [ undef, [[FLOW12]] ] -; CHECK-NEXT: [[TMP32:%.*]] = phi i1 [ [[TMP24]], [[LOOP_EXIT_GUARD4]] ], [ true, [[FLOW12]] ] -; CHECK-NEXT: [[DOTINV14]] = xor i1 [[TMP29]], true -; CHECK-NEXT: [[DOTINV]] = xor i1 [[TMP30]], true -; CHECK-NEXT: br i1 [[TMP32]], label [[LOOP_EXIT_GUARD2]], label [[IRR_GUARD]] -; CHECK: loop.exit.guard4: -; CHECK-NEXT: br label [[FLOW13]] +; CHECK-NEXT: [[TMP24]] = phi i1 [ [[TMP15]], [[FLOW14]] ], [ [[TMP17]], [[FLOW12]] ] +; CHECK-NEXT: [[TMP25:%.*]] = phi i1 [ [[TMP16]], [[FLOW14]] ], [ true, [[FLOW12]] ] +; CHECK-NEXT: br i1 [[TMP25]], label [[LOOP_EXIT_GUARD:%.*]], label [[WHILE_COND]] +; CHECK: loop.exit.guard1: +; CHECK-NEXT: br i1 [[DOTINV]], label [[LOOP_EXIT_GUARD2]], label [[FLOW14]] +; CHECK: loop.exit.guard2: +; CHECK-NEXT: br i1 [[DOTINV11]], label [[IF_THEN69]], label [[FLOW15]] ; entry: br i1 %Pred0, label %if.end, label %if.then _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
