From fbad5fdc03d90988999b54eb630a9d509098d58d Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Wed, 12 Oct 2022 18:14:06 +0700 Subject: [PATCH] [NFC] Perform all legality checks for non-trivial unswitch in one function They have been scattered over the code. For better structuring, perform them in one place. Potential CT drop is possible because we collect exit blocks twice, but it's small price to pay for much better code structure. --- llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp | 85 +++++++++++------------ 1 file changed, 41 insertions(+), 44 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp index fa570ad..89d5591 100644 --- a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp +++ b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp @@ -2057,8 +2057,8 @@ void visitDomSubTree(DominatorTree &DT, BasicBlock *BB, CallableT Callable) { static void unswitchNontrivialInvariants( Loop &L, Instruction &TI, ArrayRef Invariants, - SmallVectorImpl &ExitBlocks, IVConditionInfo &PartialIVInfo, - DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, + IVConditionInfo &PartialIVInfo, DominatorTree &DT, LoopInfo &LI, + AssumptionCache &AC, function_ref)> UnswitchCB, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, function_ref DestroyLoopCB) { @@ -2139,6 +2139,8 @@ static void unswitchNontrivialInvariants( // furthest up our loopnest which can be mutated, which we will use below to // update things. Loop *OuterExitL = &L; + SmallVector ExitBlocks; + L.getUniqueExitBlocks(ExitBlocks); for (auto *ExitBB : ExitBlocks) { Loop *NewOuterExitL = LI.getLoopFor(ExitBB); if (!NewOuterExitL) { @@ -2584,10 +2586,9 @@ static InstructionCost computeDomSubtreeCost( /// /// It also makes all relevant DT and LI updates, so that all structures are in /// valid state after this transform. -static BranchInst * -turnGuardIntoBranch(IntrinsicInst *GI, Loop &L, - SmallVectorImpl &ExitBlocks, - DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU) { +static BranchInst *turnGuardIntoBranch(IntrinsicInst *GI, Loop &L, + DominatorTree &DT, LoopInfo &LI, + MemorySSAUpdater *MSSAU) { SmallVector DTUpdates; LLVM_DEBUG(dbgs() << "Turning " << *GI << " into a branch.\n"); BasicBlock *CheckBB = GI->getParent(); @@ -2614,9 +2615,6 @@ turnGuardIntoBranch(IntrinsicInst *GI, Loop &L, CheckBI->getSuccessor(1)->setName("deopt"); BasicBlock *DeoptBlock = CheckBI->getSuccessor(1); - // We now have a new exit block. - ExitBlocks.push_back(CheckBI->getSuccessor(1)); - if (MSSAU) MSSAU->moveAllAfterSpliceBlocks(CheckBB, GuardedBlock, GI); @@ -2827,7 +2825,7 @@ struct NonTrivialUnswitchCandidate { }; } // end anonymous namespace. -static bool isSafeToClone(const Loop &L) { +static bool isSafeForNoNTrivialUnswitching(Loop &L, LoopInfo &LI) { if (!L.isSafeToClone()) return false; for (auto *BB : L.blocks()) @@ -2840,6 +2838,33 @@ static bool isSafeToClone(const Loop &L) { return false; } } + + // Check if there are irreducible CFG cycles in this loop. If so, we cannot + // easily unswitch non-trivial edges out of the loop. Doing so might turn the + // irreducible control flow into reducible control flow and introduce new + // loops "out of thin air". If we ever discover important use cases for doing + // this, we can add support to loop unswitch, but it is a lot of complexity + // for what seems little or no real world benefit. + LoopBlocksRPO RPOT(&L); + RPOT.perform(&LI); + if (containsIrreducibleCFG(RPOT, LI)) + return false; + + SmallVector ExitBlocks; + L.getUniqueExitBlocks(ExitBlocks); + // We cannot unswitch if exit blocks contain a cleanuppad/catchswitch + // instruction as we don't know how to split those exit blocks. + // FIXME: We should teach SplitBlock to handle this and remove this + // restriction. + for (auto *ExitBB : ExitBlocks) { + auto *I = ExitBB->getFirstNonPHI(); + if (isa(I) || isa(I)) { + LLVM_DEBUG(dbgs() << "Cannot unswitch because of cleanuppad/catchswitch " + "in exit block\n"); + return false; + } + } + return true; } @@ -3007,33 +3032,6 @@ static bool unswitchBestCondition( PartialIVCondBranch, L, LI, AA, MSSAU)) return false; - // Check if there are irreducible CFG cycles in this loop. If so, we cannot - // easily unswitch non-trivial edges out of the loop. Doing so might turn the - // irreducible control flow into reducible control flow and introduce new - // loops "out of thin air". If we ever discover important use cases for doing - // this, we can add support to loop unswitch, but it is a lot of complexity - // for what seems little or no real world benefit. - LoopBlocksRPO RPOT(&L); - RPOT.perform(&LI); - if (containsIrreducibleCFG(RPOT, LI)) - return false; - - SmallVector ExitBlocks; - L.getUniqueExitBlocks(ExitBlocks); - - // We cannot unswitch if exit blocks contain a cleanuppad/catchswitch - // instruction as we don't know how to split those exit blocks. - // FIXME: We should teach SplitBlock to handle this and remove this - // restriction. - for (auto *ExitBB : ExitBlocks) { - auto *I = ExitBB->getFirstNonPHI(); - if (isa(I) || isa(I)) { - LLVM_DEBUG(dbgs() << "Cannot unswitch because of cleanuppad/catchswitch " - "in exit block\n"); - return false; - } - } - LLVM_DEBUG( dbgs() << "Considering " << UnswitchCandidates.size() << " non-trivial loop invariant conditions for unswitching.\n"); @@ -3054,14 +3052,13 @@ static bool unswitchBestCondition( // If the best candidate is a guard, turn it into a branch. if (isGuard(Best.TI)) - Best.TI = turnGuardIntoBranch(cast(Best.TI), L, ExitBlocks, - DT, LI, MSSAU); + Best.TI = + turnGuardIntoBranch(cast(Best.TI), L, DT, LI, MSSAU); LLVM_DEBUG(dbgs() << " Unswitching non-trivial (cost = " << Best.Cost << ") terminator: " << *Best.TI << "\n"); - unswitchNontrivialInvariants(L, *Best.TI, Best.Invariants, ExitBlocks, - PartialIVInfo, DT, LI, AC, UnswitchCB, SE, MSSAU, - DestroyLoopCB); + unswitchNontrivialInvariants(L, *Best.TI, Best.Invariants, PartialIVInfo, DT, + LI, AC, UnswitchCB, SE, MSSAU, DestroyLoopCB); return true; } @@ -3137,8 +3134,8 @@ unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, return false; } - // Skip non-trivial unswitching for loops that cannot be cloned. - if (!isSafeToClone(L)) + // Perform legality checks. + if (!isSafeForNoNTrivialUnswitching(L, LI)) return false; // For non-trivial unswitching, because it often creates new loops, we rely on -- 2.7.4