diff --git a/llvm/include/llvm/Analysis/LoopInfo.h b/llvm/include/llvm/Analysis/LoopInfo.h --- a/llvm/include/llvm/Analysis/LoopInfo.h +++ b/llvm/include/llvm/Analysis/LoopInfo.h @@ -962,6 +962,12 @@ return L && L->getHeader() == BB; } + /// Return the top-level loops. + const std::vector &getTopLevelLoops() const { return TopLevelLoops; } + + /// Return the top-level loops. + std::vector &getTopLevelLoopsVector() { return TopLevelLoops; } + /// 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. diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -151,6 +151,7 @@ void initializeFEntryInserterPass(PassRegistry&); void initializeFinalizeISelPass(PassRegistry&); void initializeFinalizeMachineBundlesPass(PassRegistry&); +void initializeFixIrreduciblePass(PassRegistry &); void initializeFlattenCFGPassPass(PassRegistry&); void initializeFloat2IntLegacyPassPass(PassRegistry&); void initializeForceFunctionAttrsLegacyPassPass(PassRegistry&); diff --git a/llvm/include/llvm/LinkAllPasses.h b/llvm/include/llvm/LinkAllPasses.h --- a/llvm/include/llvm/LinkAllPasses.h +++ b/llvm/include/llvm/LinkAllPasses.h @@ -231,6 +231,7 @@ (void) llvm::createHardwareLoopsPass(); (void) llvm::createInjectTLIMappingsLegacyPass(); (void) llvm::createUnifyLoopExitsPass(); + (void) llvm::createFixIrreduciblePass(); (void)new llvm::IntervalPartition(); (void)new llvm::ScalarEvolutionWrapperPass(); diff --git a/llvm/include/llvm/Transforms/Utils.h b/llvm/include/llvm/Transforms/Utils.h --- a/llvm/include/llvm/Transforms/Utils.h +++ b/llvm/include/llvm/Transforms/Utils.h @@ -134,6 +134,13 @@ // exit blocks. // FunctionPass *createUnifyLoopExitsPass(); + +//===----------------------------------------------------------------------===// +// +// FixIrreducible - Convert each SCC with irreducible control-flow +// into a natural loop. +// +FunctionPass *createFixIrreduciblePass(); } #endif diff --git a/llvm/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp b/llvm/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp --- a/llvm/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp +++ b/llvm/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp @@ -864,6 +864,7 @@ addPass(&AMDGPUUnifyDivergentExitNodesID); if (!LateCFGStructurize) { if (EnableStructurizerWorkarounds) { + addPass(createFixIrreduciblePass()); addPass(createUnifyLoopExitsPass()); } addPass(createStructurizeCFGPass(true)); // true -> SkipUniformRegions diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp --- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -1173,9 +1173,10 @@ for (auto In : Incoming) { auto Branch = cast(In->getTerminator()); + auto Condition = Branch->isConditional() ? Branch->getCondition() : nullptr; + BasicBlock *Succ0 = Branch->getSuccessor(0); BasicBlock *Succ1 = nullptr; - Succ0 = Outgoing.count(Succ0) ? Succ0 : nullptr; if (Branch->isUnconditional()) { @@ -1194,7 +1195,12 @@ BranchInst::Create(FirstGuardBlock, In); } } - +#ifndef NDEBUG + // Branch no longer contains any information about the input CFG, + // and in fact, it was erased if both successors are in the set of + // outgoing blocks. + Branch = nullptr; +#endif // NDEBUG assert(Succ0 || Succ1); // Optimization: Consider an incoming block A with both successors @@ -1205,7 +1211,6 @@ // control must reach Succ1, which means that the predicate for // Succ1 is always true. bool OneSuccessorDone = false; - auto Condition = Branch->getCondition(); for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) { auto Out = Outgoing[i]; auto Phi = GuardPredicates[Out]; diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -19,6 +19,7 @@ EntryExitInstrumenter.cpp EscapeEnumerator.cpp Evaluator.cpp + FixIrreducible.cpp FlattenCFG.cpp FunctionComparator.cpp FunctionImportUtils.cpp diff --git a/llvm/lib/Transforms/Utils/FixIrreducible.cpp b/llvm/lib/Transforms/Utils/FixIrreducible.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/Utils/FixIrreducible.cpp @@ -0,0 +1,307 @@ +//===- FixIrreducible.cpp - Convert irreducible control-flow into loops ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// 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. +// +// 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 function CreateControlFlowHub, which +// takes a set of incoming blocks (the predecessors) and outgoing blocks (the +// headers). The function also moves every PHINode in an outgoing block to the +// hub. Since the hub dominates all the outgoing blocks, each such PHINode +// continues to dominate its uses. Since every header in an SCC has at least two +// predecessors, every value used in the header (or later) but defined in a +// predecessor (or earlier) is represented by a PHINode in a header. Hence the +// above handling of PHINodes is sufficient and no further processing is +// required to restore SSA. +// +// Limitation: The pass cannot handle switch statements and indirect +// branches. Both must be lowered to plain branches first. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/SCCIterator.h" +#include "llvm/Analysis/LoopIterator.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/Transforms/Utils.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" + +#define DEBUG_TYPE "fix-irreducible" + +using namespace llvm; + +namespace { +struct FixIrreducible : public FunctionPass { + static char ID; + FixIrreducible() : FunctionPass(ID) { + initializeFixIrreduciblePass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequiredID(LowerSwitchID); + AU.addRequired(); + AU.addRequired(); + AU.addPreservedID(LowerSwitchID); + AU.addPreserved(); + AU.addPreserved(); + } + + bool runOnFunction(Function &F); +}; +} // namespace + +char FixIrreducible::ID = 0; + +FunctionPass *llvm::createFixIrreduciblePass() { return new FixIrreducible(); } + +INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible", + "Convert irreducible control-flow into natural loops", + false /* Only looks at CFG */, false /* Analysis Pass */) +INITIALIZE_PASS_DEPENDENCY(LowerSwitch) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_END(FixIrreducible, "fix-irreducible", + "Convert irreducible control-flow into natural loops", + false /* Only looks at CFG */, false /* Analysis Pass */) + +// 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, + SetVector &Blocks, + SetVector &Headers) { + auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector() + : LI.getTopLevelLoopsVector(); + // Partition the candidate loops into two ranges. The first part + // contains loops that are not children of the new loop. The second + // part contains children that need to be moved to the new loop. + auto FirstChild = + std::partition(CandidateLoops.begin(), CandidateLoops.end(), [&](Loop *L) { + return L == NewLoop || Blocks.count(L->getHeader()) == 0; + }); + for (auto II = FirstChild, IE = CandidateLoops.end(); II != IE; ++II) { + auto Child = *II; + LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName() + << "\n"); + // 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()) { + LI.changeLoopFor(BB, NewLoop); + LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName() + << "\n"); + } + LI.destroy(Child); + LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n"); + continue; + } + + if (ParentLoop) { + LLVM_DEBUG(dbgs() << "removed child loop from parent\n"); + ParentLoop->removeChildLoop(Child); + } + LLVM_DEBUG(dbgs() << "added child loop to new loop\n"); + NewLoop->addChildLoop(Child); + } + CandidateLoops.erase(FirstChild, CandidateLoops.end()); +} + +// 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 &Blocks, + SetVector &Headers) { +#ifndef NDEBUG + // All headers are part of the SCC + for (auto H : Headers) { + assert(Blocks.count(H)); + } +#endif + + SetVector 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. + SmallVector GuardBlocks; + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); + CreateControlFlowHub(&DTU, GuardBlocks, Predecessors, Headers, "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(); + if (ParentLoop) { + ParentLoop->addChildLoop(NewLoop); + } else { + LI.addTopLevelLoop(NewLoop); + } + + // Add the guard blocks to the new loop. The first guard block is + // the head of all the backedges, and it is the first to be inserted + // in the loop. This ensures that it is recognized as the + // 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: " << G->getName() << "\n"); + NewLoop->addBasicBlockToLoop(G, LI); + } + + // 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() + << "\n"); + LI.changeLoopFor(BB, NewLoop); + } else { + LLVM_DEBUG(dbgs() << "added block from child: " << BB->getName() << "\n"); + } + } + LLVM_DEBUG(dbgs() << "header for new loop: " + << NewLoop->getHeader()->getName() << "\n"); + + reconnectChildLoops(LI, ParentLoop, NewLoop, Blocks, Headers); + + NewLoop->verifyLoop(); + if (ParentLoop) { + ParentLoop->verifyLoop(); + } +#if defined(EXPENSIVE_CHECKS) + LI.verify(DT); +#endif // EXPENSIVE_CHECKS +} + +// Enable the graph traits required for traversing a Loop body. +template <> struct GraphTraits : LoopBodyTraits {}; + +// Overloaded wrappers to go with the function template below. +BasicBlock *unwrapBlock(BasicBlock *B) { return B; } +BasicBlock *unwrapBlock(LoopBodyTraits::NodeRef &N) { return N.second; } + +static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Function *F, + SetVector &Blocks, + SetVector &Headers) { + createNaturalLoopInternal(LI, DT, nullptr, Blocks, Headers); +} + +static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Loop &L, + SetVector &Blocks, + SetVector &Headers) { + createNaturalLoopInternal(LI, DT, &L, Blocks, Headers); +} + +// Convert irreducible SCCs; Graph G may be a Function* or a Loop&. +template +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 Blocks; + LLVM_DEBUG(dbgs() << "Found SCC:"); + for (auto N : *Scc) { + auto BB = unwrapBlock(N); + LLVM_DEBUG(dbgs() << " " << BB->getName()); + Blocks.insert(BB); + } + 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 Headers; + LLVM_DEBUG(dbgs() << "Found headers:"); + for (auto BB : reverse(Blocks)) { + for (const auto P : predecessors(BB)) { + if (!Blocks.count(P)) { + LLVM_DEBUG(dbgs() << " " << BB->getName()); + Headers.insert(BB); + break; + } + } + } + LLVM_DEBUG(dbgs() << "\n"); + + 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; + } + return Changed; +} + +bool FixIrreducible::runOnFunction(Function &F) { + LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: " + << F.getName() << "\n"); + auto &LI = getAnalysis().getLoopInfo(); + auto &DT = getAnalysis().getDomTree(); + + bool Changed = false; + SmallVector 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. + for (auto L : LI) { + WorkList.push_back(L); + } + + while (!WorkList.empty()) { + auto L = WorkList.back(); + WorkList.pop_back(); + 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()); + } + + return Changed; +} diff --git a/llvm/lib/Transforms/Utils/UnifyLoopExits.cpp b/llvm/lib/Transforms/Utils/UnifyLoopExits.cpp --- a/llvm/lib/Transforms/Utils/UnifyLoopExits.cpp +++ b/llvm/lib/Transforms/Utils/UnifyLoopExits.cpp @@ -183,7 +183,7 @@ #if defined(EXPENSIVE_CHECKS) assert(DT.verify(DominatorTree::VerificationLevel::Full)); #else - assert(DT.verify(DominatorTree::VerificationLevel::Full)); + assert(DT.verify(DominatorTree::VerificationLevel::Fast)); #endif // EXPENSIVE_CHECKS L->verifyLoop(); diff --git a/llvm/lib/Transforms/Utils/Utils.cpp b/llvm/lib/Transforms/Utils/Utils.cpp --- a/llvm/lib/Transforms/Utils/Utils.cpp +++ b/llvm/lib/Transforms/Utils/Utils.cpp @@ -40,6 +40,7 @@ initializeStripGCRelocatesPass(Registry); initializePredicateInfoPrinterLegacyPassPass(Registry); initializeInjectTLIMappingsLegacyPass(Registry); + initializeFixIrreduciblePass(Registry); initializeUnifyLoopExitsPass(Registry); } diff --git a/llvm/test/Transforms/FixIrreducible/basic.ll b/llvm/test/Transforms/FixIrreducible/basic.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/FixIrreducible/basic.ll @@ -0,0 +1,268 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -fix-irreducible -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: br label [[IRR_GUARD:%.*]] +; CHECK: left: +; 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 [[IRR_GUARD]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: [[Z:%.*]] = phi i32 [ [[L]], [[LEFT:%.*]] ], [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ] +; CHECK-NEXT: ret i32 [[Z]] +; CHECK: irr.guard: +; CHECK-NEXT: [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[LEFT]] ] +; CHECK-NEXT: [[L_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ] +; CHECK-NEXT: [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[L]], [[LEFT]] ] +; CHECK-NEXT: br i1 [[GUARD_LEFT]], label [[LEFT]], label [[RIGHT]] +; +entry: + br i1 %PredEntry, label %left, label %right + +left: + %L.phi = phi i32 [%X, %entry], [%R.phi, %right] + %L = add i32 %L.phi, 1 + br i1 %PredLeft, label %right, label %exit + +right: + %R.phi = phi i32 [%Y, %entry], [%L, %left] + br i1 %PredRight, label %left, label %exit + +exit: + %Z = phi i32 [%L, %left], [%R.phi, %right] + ret i32 %Z +} + +define i32 @feedback_loop(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) { +; CHECK-LABEL: @feedback_loop( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[IRR_GUARD:%.*]] +; CHECK: left: +; CHECK-NEXT: br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] +; CHECK: right: +; CHECK-NEXT: br i1 [[PREDRIGHT:%.*]], label [[IRR_GUARD]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: [[Z:%.*]] = phi i32 [ [[L_PHI_MOVED:%.*]], [[LEFT:%.*]] ], [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ] +; CHECK-NEXT: ret i32 [[Z]] +; CHECK: irr.guard: +; CHECK-NEXT: [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[LEFT]] ] +; CHECK-NEXT: [[L_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ] +; CHECK-NEXT: [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ] +; CHECK-NEXT: br i1 [[GUARD_LEFT]], label [[LEFT]], label [[RIGHT]] +; +entry: + br i1 %PredEntry, label %left, label %right + +left: + %L.phi = phi i32 [%X, %entry], [%R.phi, %right] + br i1 %PredLeft, label %right, label %exit + +right: + %R.phi = phi i32 [%Y, %entry], [%L.phi, %left] + br i1 %PredRight, label %left, label %exit + +exit: + %Z = phi i32 [%L.phi, %left], [%R.phi, %right] + ret i32 %Z +} + +define i32 @multiple_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) { +; CHECK-LABEL: @multiple_predecessors( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[PREDB_INV:%.*]] = xor i1 [[PREDB:%.*]], true +; CHECK-NEXT: br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]] +; CHECK: A: +; CHECK-NEXT: [[A_INC:%.*]] = add i32 [[X:%.*]], 1 +; CHECK-NEXT: br label [[IRR_GUARD:%.*]] +; CHECK: B: +; CHECK-NEXT: br label [[IRR_GUARD]] +; CHECK: C: +; CHECK-NEXT: br i1 [[PREDC:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] +; CHECK: D: +; 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 i32 [[RET]] +; CHECK: irr.guard: +; CHECK-NEXT: [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ [[PREDB_INV]], [[B]] ], [ [[PREDA:%.*]], [[A]] ], [ false, [[C]] ] +; CHECK-NEXT: [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[Y:%.*]], [[B]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ] +; CHECK-NEXT: [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ [[Y]], [[B]] ], [ [[A_INC]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ] +; CHECK-NEXT: br i1 [[GUARD_C]], label [[C]], label [[D]] +; +entry: + br i1 %PredEntry, label %A, label %B + +A: + %A.inc = add i32 %X, 1 + br i1 %PredA, label %C, label %D + +B: + br i1 %PredB, label %D, label %C + +C: + %C.phi = phi i32 [%X, %A], [%Y, %B], [%D.inc, %D] + br i1 %PredC, label %D, label %exit + +D: + %D.phi = phi i32 [%A.inc, %A], [%Y, %B], [%C.phi, %C] + %D.inc = add i32 %D.phi, 1 + br i1 %PredD, label %exit, label %C + +exit: + %ret = phi i32 [%C.phi, %C], [%D.inc, %D] + ret i32 %ret +} + +define i32 @separate_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) { +; CHECK-LABEL: @separate_predecessors( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]] +; CHECK: A: +; CHECK-NEXT: [[A_INC:%.*]] = add i32 [[X:%.*]], 1 +; CHECK-NEXT: br label [[IRR_GUARD:%.*]] +; CHECK: B: +; CHECK-NEXT: br label [[IRR_GUARD]] +; CHECK: C: +; 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 [[IRR_GUARD]] +; CHECK: exit: +; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_INC]], [[D:%.*]] ] +; CHECK-NEXT: ret i32 [[RET]] +; CHECK: irr.guard: +; CHECK-NEXT: [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ true, [[A]] ], [ false, [[C]] ], [ false, [[B]] ] +; CHECK-NEXT: [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ], [ undef, [[B]] ] +; CHECK-NEXT: [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ undef, [[A]] ], [ [[C_PHI_MOVED]], [[C]] ], [ [[Y:%.*]], [[B]] ] +; CHECK-NEXT: br i1 [[GUARD_C]], label [[C]], label [[D]] +; +entry: + br i1 %PredEntry, label %A, label %B + +A: + %A.inc = add i32 %X, 1 + br label %C + +B: + br label %D + +C: + %C.phi = phi i32 [%X, %A], [%D.inc, %D] + br i1 %PredC, label %exit, label %D + +D: + %D.phi = phi i32 [%Y, %B], [%C.phi, %C] + %D.inc = add i32 %D.phi, 1 + br i1 %PredD, label %exit, label %C + +exit: + %ret = phi i32 [%C.phi, %C], [%D.inc, %D] + ret i32 %ret +} + +define void @four_headers(i1 %PredEntry, i1 %PredX, i1 %PredY, i1 %PredD) { +; CHECK-LABEL: @four_headers( +; CHECK-NEXT: entry: +; 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 [[IRR_GUARD]] +; CHECK: B: +; CHECK-NEXT: br label [[IRR_GUARD]] +; CHECK: C: +; CHECK-NEXT: br label [[IRR_GUARD]] +; CHECK: D: +; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]] +; CHECK: exit: +; CHECK-NEXT: ret void +; CHECK: irr.guard: +; 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_B]], label [[B]], label [[IRR_GUARD2:%.*]] +; CHECK: irr.guard2: +; CHECK-NEXT: br i1 [[GUARD_C]], label [[C]], label [[D]] +; +entry: + br i1 %PredEntry, label %X, label %Y + +X: + br i1 %PredX, label %A, label %B + +Y: + br i1 %PredY, label %C, label %D + +A: + br label %B + +B: + br label %C + +C: + br label %D + +D: + br i1 %PredD, label %exit, label %A + +exit: + ret void +} + +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: br label [[IRR_GUARD:%.*]] +; CHECK: A: +; 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: br label [[D:%.*]] +; CHECK: D: +; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[E:%.*]] +; CHECK: E: +; CHECK-NEXT: br label [[IRR_GUARD]] +; CHECK: exit: +; CHECK-NEXT: ret i32 [[B_PHI_MOVED]] +; CHECK: irr.guard: +; CHECK-NEXT: [[GUARD_A:%.*]] = phi i1 [ true, [[E]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[A:%.*]] ] +; CHECK-NEXT: [[A_PHI_MOVED]] = phi i32 [ [[C_INC]], [[E]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[A_PHI_MOVED]], [[A]] ] +; CHECK-NEXT: [[B_PHI_MOVED]] = phi i32 [ undef, [[E]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[A_INC]], [[A]] ] +; CHECK-NEXT: br i1 [[GUARD_A]], label [[A]], label [[B:%.*]] +; +entry: + br i1 %PredEntry, label %A, label %B + +A: + %A.phi = phi i32 [%X, %entry], [%C.inc, %E] + %A.inc = add i32 %A.phi, 1 + br label %B + +B: + %B.phi = phi i32 [%A.inc, %A], [%Y, %entry] + br label %C + +C: + %C.inc = add i32 %B.phi, 1 + br label %D + +D: + br i1 %PredD, label %exit, label %E + +E: + br label %A + +exit: + ret i32 %B.phi +} diff --git a/llvm/test/Transforms/FixIrreducible/nested.ll b/llvm/test/Transforms/FixIrreducible/nested.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/FixIrreducible/nested.ll @@ -0,0 +1,433 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -fix-irreducible -S | FileCheck %s -check-prefix=CHECK + +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: 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 [[IRR_GUARD1]], label [[A3]] +; CHECK: A3: +; CHECK-NEXT: br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] +; CHECK: A2: +; CHECK-NEXT: br i1 [[PRED5:%.*]], label [[IRR_GUARD]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret void +; CHECK: irr.guard: +; 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_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 + +A1: + br i1 %Pred1, label %B1, label %B2 + +B1: + br i1 %Pred2, label %B2, label %A3 + +B2: + br i1 %Pred3, label %B1, label %A3 + +A3: + br i1 %Pred4, label %A2, label %exit + +A2: + br i1 %Pred5, label %A1, label %exit + +exit: + ret void +} + +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: br label [[H1:%.*]] +; CHECK: H1: +; 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 [[IRR_GUARD1]], label [[A3]] +; CHECK: A3: +; CHECK-NEXT: br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[L1:%.*]] +; CHECK: A2: +; 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_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_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED1:%.*]], [[A1]] ], [ false, [[B1:%.*]] ] +; CHECK-NEXT: br i1 [[GUARD_B1]], label [[B1]], label [[B2]] +; +entry: + br label %H1 + +H1: + br i1 %Pred0, label %A1, label %A2 + +A1: + br i1 %Pred1, label %B1, label %B2 + +B1: + br i1 %Pred2, label %B2, label %A3 + +B2: + br i1 %Pred3, label %B1, label %A3 + +A3: + br i1 %Pred4, label %A2, label %L1 + +A2: + br i1 %Pred5, label %A1, label %L1 + +L1: + br i1 %Pred6, label %exit, label %H1 + +exit: + ret void +} + +define void @loop_in_irr(i1 %Pred0, i1 %Pred1, i1 %Pred2) { +; CHECK-LABEL: @loop_in_irr( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[IRR_GUARD:%.*]] +; CHECK: A1: +; CHECK-NEXT: br label [[H1:%.*]] +; 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 [[IRR_GUARD]] +; CHECK: exit: +; CHECK-NEXT: ret void +; CHECK: irr.guard: +; 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 + +A1: + br label %H1 + +H1: + br label %L1 + +L1: + br i1 %Pred1, label %H1, label %A3 + +A3: + br i1 %Pred2, label %A2, label %exit + +A2: + br label %A1 + +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: 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 [[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:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ] +; CHECK-NEXT: br i1 [[GUARD_H1]], label [[H1:%.*]], label [[A2]] +; +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 @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: br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]] +; CHECK: H1: +; CHECK-NEXT: br label [[IRR_GUARD1:%.*]] +; CHECK: A1: +; CHECK-NEXT: br label [[IRR_GUARD1]] +; CHECK: A2: +; 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_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_GUARD]] +; CHECK: B2: +; CHECK-NEXT: br i1 [[PRED6:%.*]], label [[IRR_GUARD]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret void +; CHECK: irr.guard: +; 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_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 + +H1: + br i1 %Pred1, label %A1, label %A2 + +A1: + br label %A2 + +A2: + br i1 %Pred2, label %A1, label %L1 + +L1: + br i1 %Pred3, label %H1, label %exit + +fork1: + br i1 %Pred4, label %B1, label %B2 + +B1: + br label %H2 + +H2: + br label %L2 + +L2: + br i1 %Pred5, label %H2, label %B2 + +B2: + br i1 %Pred6, label %B1, label %exit + +exit: + ret void +} + +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: br label [[H0:%.*]] +; CHECK: H0: +; CHECK-NEXT: br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]] +; CHECK: H1: +; CHECK-NEXT: br label [[IRR_GUARD1:%.*]] +; CHECK: A1: +; CHECK-NEXT: br label [[IRR_GUARD1]] +; CHECK: A2: +; 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_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_GUARD]] +; CHECK: B2: +; 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_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_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED1:%.*]], [[H1]] ], [ false, [[A1:%.*]] ] +; CHECK-NEXT: br i1 [[GUARD_A1]], label [[A1]], label [[A2]] +; +entry: + br label %H0 + +H0: + br i1 %Pred0, label %H1, label %fork1 + +H1: + br i1 %Pred1, label %A1, label %A2 + +A1: + br label %A2 + +A2: + br i1 %Pred2, label %A1, label %L1 + +L1: + br i1 %Pred3, label %H1, label %L0 + +fork1: + br i1 %Pred4, label %B1, label %B2 + +B1: + br label %H2 + +H2: + br label %L2 + +L2: + br i1 %Pred5, label %H2, label %B2 + +B2: + br i1 %Pred6, label %B1, label %L0 + +L0: + br i1 %Pred7, label %exit, label %H0 + +exit: + ret void +} + +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: +; CHECK-NEXT: br i1 [[PRED1:%.*]], label [[IF_THEN7:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then7: +; CHECK-NEXT: br label [[IF_END16:%.*]] +; CHECK: if.else: +; CHECK-NEXT: br label [[IF_END16]] +; CHECK: if.end16: +; CHECK-NEXT: br i1 [[PRED2:%.*]], label [[WHILE_COND_PREHEADER:%.*]], label [[IF_THEN39:%.*]] +; CHECK: while.cond.preheader: +; CHECK-NEXT: br label [[WHILE_COND:%.*]] +; 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 [[WHILE_BODY63:%.*]] +; CHECK: while.body63: +; CHECK-NEXT: br i1 [[PRED5:%.*]], label [[EXIT:%.*]], label [[WHILE_COND47:%.*]] +; CHECK: while.cond47: +; CHECK-NEXT: br label [[IRR_GUARD]] +; CHECK: cond.end61: +; 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: +; CHECK-NEXT: br i1 [[PRED9:%.*]], label [[IRR_GUARD]], label [[WHILE_END76:%.*]] +; CHECK: while.end76: +; CHECK-NEXT: br label [[EXIT]] +; CHECK: if.then39: +; CHECK-NEXT: br i1 [[PRED10:%.*]], label [[EXIT]], label [[IF_END_I145:%.*]] +; CHECK: if.end.i145: +; CHECK-NEXT: br i1 [[PRED11:%.*]], label [[EXIT]], label [[IF_END8_I149:%.*]] +; CHECK: if.end8.i149: +; CHECK-NEXT: br label [[EXIT]] +; CHECK: if.then: +; CHECK-NEXT: br i1 [[PRED12:%.*]], label [[EXIT]], label [[IF_END_I:%.*]] +; CHECK: if.end.i: +; CHECK-NEXT: br i1 [[PRED13:%.*]], label [[EXIT]], label [[IF_END8_I:%.*]] +; CHECK: if.end8.i: +; CHECK-NEXT: br label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret void +; CHECK: irr.guard: +; 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 + +if.end: + br i1 %Pred1, label %if.then7, label %if.else + +if.then7: + br label %if.end16 + +if.else: + br label %if.end16 + +if.end16: + br i1 %Pred2, label %while.cond.preheader, label %if.then39 + +while.cond.preheader: + br label %while.cond + +while.cond: + br i1 %Pred3, label %cond.true49, label %lor.rhs + +cond.true49: + br i1 %Pred4, label %if.then69, label %while.body63 + +while.body63: + br i1 %Pred5, label %exit, label %while.cond47 + +while.cond47: + br i1 %Pred6, label %cond.true49, label %cond.end61 + +cond.end61: + br i1 %Pred7, label %while.body63, label %while.cond + +if.then69: + br i1 %Pred8, label %exit, label %while.cond + +lor.rhs: + br i1 %Pred9, label %cond.end61, label %while.end76 + +while.end76: + br label %exit + +if.then39: + br i1 %Pred10, label %exit, label %if.end.i145 + +if.end.i145: + br i1 %Pred11, label %exit, label %if.end8.i149 + +if.end8.i149: + br label %exit + +if.then: + br i1 %Pred12, label %exit, label %if.end.i + +if.end.i: + br i1 %Pred13, label %exit, label %if.end8.i + +if.end8.i: + br label %exit + +exit: + ret void +} diff --git a/llvm/test/Transforms/FixIrreducible/switch.ll b/llvm/test/Transforms/FixIrreducible/switch.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/FixIrreducible/switch.ll @@ -0,0 +1,43 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -fix-irreducible -S | FileCheck %s + +define void @loop_1(i32 %Value, i1 %PredEntry, i1 %PredD) { +; CHECK-LABEL: @loop_1( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[IRR_GUARD:%.*]] +; CHECK: A: +; CHECK-NEXT: br label [[IRR_GUARD]] +; CHECK: B: +; CHECK-NEXT: br label [[NODEBLOCK:%.*]] +; CHECK: NodeBlock: +; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VALUE:%.*]], 1 +; CHECK-NEXT: br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[LEAFBLOCK1:%.*]] +; CHECK: LeafBlock1: +; CHECK-NEXT: [[SWITCHLEAF2:%.*]] = icmp eq i32 [[VALUE]], 1 +; CHECK-NEXT: br i1 [[SWITCHLEAF2]], label [[IRR_GUARD]], label [[NEWDEFAULT:%.*]] +; CHECK: LeafBlock: +; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VALUE]], 0 +; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[IRR_GUARD]], label [[NEWDEFAULT]] +; CHECK: NewDefault: +; CHECK-NEXT: br label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; CHECK: irr.guard: +; 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 + +A: + br label %B + +B: + switch i32 %Value, label %exit [ + i32 0, label %A + i32 1, label %B + ] + +exit: + ret void +} diff --git a/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fix-reducible.ll b/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fix-reducible.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fix-reducible.ll @@ -0,0 +1,60 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -fix-irreducible -structurizecfg -S | FileCheck %s + +; Both B1 and B4 are headers of an irreducible cycle. But in the +; structurized version, B1 dominates B4. The program is structurized +; correctly when the irreducible cycle is fixed. + +define void @irreducible(i1 %PredEntry, i1 %PredB1, i1 %PredB2, i1 %PredB3, i1 %PredB4) +; CHECK-LABEL: @irreducible( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[PREDB2_INV:%.*]] = xor i1 [[PREDB2:%.*]], true +; CHECK-NEXT: [[PREDB1_INV:%.*]] = xor i1 [[PREDB1:%.*]], true +; CHECK-NEXT: br label [[IRR_GUARD:%.*]] +; 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 [[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 [[FLOW3:%.*]] +; CHECK: Flow2: +; CHECK-NEXT: [[TMP3:%.*]] = phi i1 [ [[TMP4:%.*]], [[FLOW3]] ], [ true, [[FLOW1]] ] +; CHECK-NEXT: br i1 [[TMP3]], label [[EXIT:%.*]], label [[IRR_GUARD]] +; CHECK: B3: +; CHECK-NEXT: br label [[FLOW3]] +; CHECK: B4: +; CHECK-NEXT: br label [[FLOW]] +; CHECK: Flow3: +; CHECK-NEXT: [[TMP4]] = phi i1 [ false, [[B3]] ], [ true, [[B2]] ] +; CHECK-NEXT: br label [[FLOW2]] +; CHECK: exit: +; CHECK-NEXT: ret void +; CHECK: irr.guard: +; CHECK-NEXT: [[GUARD_B1:%.*]] = phi i1 [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ [[PREDB3:%.*]], [[FLOW2]] ] +; CHECK-NEXT: [[TMP5:%.*]] = xor i1 [[GUARD_B1]], true +; CHECK-NEXT: br i1 [[TMP5]], label [[B4]], label [[FLOW]] +; +{ +entry: + br i1 %PredEntry, label %B1, label %B4 + +B1: + br i1 %PredB1, label %exit, label %B2 + +B2: + br i1 %PredB2, label %exit, label %B3 + +B3: + br i1 %PredB3, label %B1, label %B4 + +B4: + br i1 %PredB4, label %B2, label %exit + +exit: + ret void +} diff --git a/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll b/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll @@ -0,0 +1,186 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -fix-irreducible -unify-loop-exits -structurizecfg -S | FileCheck %s +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: [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true +; CHECK-NEXT: [[PRED1_INV:%.*]] = xor i1 [[PRED1:%.*]], true +; 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 [[FLOW18:%.*]] +; CHECK: Flow18: +; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ false, [[FLOW3:%.*]] ], [ true, [[ENTRY:%.*]] ] +; CHECK-NEXT: br i1 [[TMP0]], label [[IF_END:%.*]], label [[FLOW19:%.*]] +; CHECK: if.end: +; CHECK-NEXT: br i1 [[PRED1_INV]], label [[IF_ELSE:%.*]], label [[FLOW17:%.*]] +; CHECK: Flow17: +; 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 [[FLOW17]] +; CHECK: Flow19: +; CHECK-NEXT: br label [[EXIT:%.*]] +; CHECK: if.end16: +; CHECK-NEXT: br i1 [[PRED2_INV]], label [[IF_THEN39:%.*]], label [[FLOW15:%.*]] +; CHECK: Flow15: +; CHECK-NEXT: [[TMP2:%.*]] = phi i1 [ false, [[FLOW5:%.*]] ], [ true, [[IF_END16]] ] +; CHECK-NEXT: br i1 [[TMP2]], label [[WHILE_COND_PREHEADER:%.*]], label [[FLOW16:%.*]] +; CHECK: while.cond.preheader: +; CHECK-NEXT: br label [[WHILE_COND:%.*]] +; CHECK: Flow16: +; CHECK-NEXT: br label [[FLOW19]] +; CHECK: while.cond: +; CHECK-NEXT: br i1 [[PRED3_INV]], label [[LOR_RHS:%.*]], label [[FLOW11:%.*]] +; CHECK: Flow7: +; CHECK-NEXT: [[TMP3:%.*]] = phi i1 [ [[PRED7:%.*]], [[COND_END61:%.*]] ], [ false, [[IRR_GUARD:%.*]] ] +; CHECK-NEXT: [[TMP4:%.*]] = phi i1 [ false, [[COND_END61]] ], [ true, [[IRR_GUARD]] ] +; CHECK-NEXT: br i1 [[TMP4]], label [[COND_TRUE49:%.*]], label [[FLOW8:%.*]] +; CHECK: cond.true49: +; CHECK-NEXT: br label [[FLOW8]] +; CHECK: Flow8: +; CHECK-NEXT: [[TMP5:%.*]] = phi i1 [ false, [[COND_TRUE49]] ], [ true, [[FLOW7:%.*]] ] +; CHECK-NEXT: [[TMP6:%.*]] = phi i1 [ [[PRED4_INV]], [[COND_TRUE49]] ], [ [[TMP3]], [[FLOW7]] ] +; CHECK-NEXT: br i1 [[TMP6]], label [[WHILE_BODY63:%.*]], label [[FLOW9:%.*]] +; CHECK: while.body63: +; CHECK-NEXT: br i1 [[PRED5_INV]], label [[WHILE_COND47:%.*]], label [[FLOW10:%.*]] +; CHECK: Flow9: +; CHECK-NEXT: [[TMP7:%.*]] = phi i1 [ true, [[FLOW10]] ], [ false, [[FLOW8]] ] +; CHECK-NEXT: [[TMP8:%.*]] = phi i1 [ false, [[FLOW10]] ], [ [[TMP5]], [[FLOW8]] ] +; CHECK-NEXT: [[TMP9:%.*]] = phi i1 [ [[TMP18:%.*]], [[FLOW10]] ], [ true, [[FLOW8]] ] +; CHECK-NEXT: [[TMP10:%.*]] = xor i1 [[TMP7]], true +; CHECK-NEXT: [[TMP11:%.*]] = xor i1 [[TMP8]], true +; CHECK-NEXT: br i1 [[TMP9]], label [[LOOP_EXIT_GUARD1:%.*]], label [[IRR_GUARD]] +; CHECK: while.cond47: +; CHECK-NEXT: br label [[FLOW10]] +; CHECK: cond.end61: +; CHECK-NEXT: br label [[FLOW7]] +; CHECK: Flow13: +; CHECK-NEXT: [[TMP12:%.*]] = phi i1 [ false, [[FLOW14:%.*]] ], [ true, [[LOOP_EXIT_GUARD1]] ] +; CHECK-NEXT: [[TMP13:%.*]] = phi i1 [ [[TMP17:%.*]], [[FLOW14]] ], [ [[TMP11]], [[LOOP_EXIT_GUARD1]] ] +; CHECK-NEXT: br label [[FLOW12:%.*]] +; CHECK: if.then69: +; CHECK-NEXT: br label [[FLOW14]] +; CHECK: lor.rhs: +; CHECK-NEXT: br label [[FLOW11]] +; CHECK: while.end76: +; CHECK-NEXT: br label [[FLOW6:%.*]] +; CHECK: if.then39: +; 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 [[FLOW4:%.*]] +; CHECK: if.end8.i149: +; CHECK-NEXT: br label [[FLOW4]] +; CHECK: if.then: +; 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 [[FLOW18]] +; CHECK: Flow4: +; CHECK-NEXT: br label [[FLOW5]] +; CHECK: Flow5: +; CHECK-NEXT: br label [[FLOW15]] +; CHECK: Flow6: +; CHECK-NEXT: br label [[FLOW16]] +; CHECK: exit: +; CHECK-NEXT: ret void +; CHECK: Flow11: +; CHECK-NEXT: [[TMP14:%.*]] = phi i1 [ false, [[LOR_RHS]] ], [ true, [[WHILE_COND]] ] +; CHECK-NEXT: [[TMP15:%.*]] = phi i1 [ [[PRED9:%.*]], [[LOR_RHS]] ], [ [[PRED3]], [[WHILE_COND]] ] +; CHECK-NEXT: br i1 [[TMP15]], label [[IRR_GUARD]], label [[FLOW12]] +; CHECK: irr.guard: +; CHECK-NEXT: [[GUARD_COND_TRUE49:%.*]] = phi i1 [ [[PRED6:%.*]], [[FLOW9]] ], [ [[TMP14]], [[FLOW11]] ] +; CHECK-NEXT: [[TMP16:%.*]] = xor i1 [[GUARD_COND_TRUE49]], true +; CHECK-NEXT: br i1 [[TMP16]], label [[COND_END61]], label [[FLOW7]] +; CHECK: Flow14: +; CHECK-NEXT: [[TMP17]] = phi i1 [ [[PRED8:%.*]], [[IF_THEN69:%.*]] ], [ [[TMP11]], [[LOOP_EXIT_GUARD2:%.*]] ] +; CHECK-NEXT: br label [[FLOW13:%.*]] +; CHECK: loop.exit.guard: +; CHECK-NEXT: br i1 [[TMP19:%.*]], label [[WHILE_END76:%.*]], label [[FLOW6]] +; CHECK: Flow10: +; CHECK-NEXT: [[TMP18]] = phi i1 [ false, [[WHILE_COND47]] ], [ true, [[WHILE_BODY63]] ] +; CHECK-NEXT: br label [[FLOW9]] +; CHECK: Flow12: +; CHECK-NEXT: [[TMP19]] = phi i1 [ [[TMP12]], [[FLOW13]] ], [ true, [[FLOW11]] ] +; CHECK-NEXT: [[TMP20:%.*]] = phi i1 [ [[TMP13]], [[FLOW13]] ], [ true, [[FLOW11]] ] +; CHECK-NEXT: br i1 [[TMP20]], label [[LOOP_EXIT_GUARD:%.*]], label [[WHILE_COND]] +; CHECK: loop.exit.guard1: +; CHECK-NEXT: br i1 [[TMP11]], label [[LOOP_EXIT_GUARD2]], label [[FLOW13]] +; CHECK: loop.exit.guard2: +; CHECK-NEXT: br i1 [[TMP10]], label [[IF_THEN69]], label [[FLOW14]] +; +entry: + br i1 %Pred0, label %if.end, label %if.then + +if.end: + br i1 %Pred1, label %if.then7, label %if.else + +if.then7: + br label %if.end16 + +if.else: + br label %if.end16 + +if.end16: + br i1 %Pred2, label %while.cond.preheader, label %if.then39 + +while.cond.preheader: + br label %while.cond + +while.cond: + br i1 %Pred3, label %cond.true49, label %lor.rhs + +cond.true49: + br i1 %Pred4, label %if.then69, label %while.body63 + +while.body63: + br i1 %Pred5, label %exit, label %while.cond47 + +while.cond47: + br i1 %Pred6, label %cond.true49, label %cond.end61 + +cond.end61: + br i1 %Pred7, label %while.body63, label %while.cond + +if.then69: + br i1 %Pred8, label %exit, label %while.cond + +lor.rhs: + br i1 %Pred9, label %cond.end61, label %while.end76 + +while.end76: + br label %exit + +if.then39: + br i1 %Pred10, label %exit, label %if.end.i145 + +if.end.i145: + br i1 %Pred11, label %exit, label %if.end8.i149 + +if.end8.i149: + br label %exit + +if.then: + br i1 %Pred12, label %exit, label %if.end.i + +if.end.i: + br i1 %Pred13, label %exit, label %if.end8.i + +if.end8.i: + br label %exit + +exit: + ret void +}