From 54539fa8b3a3b8875b4e3d8b0737c66052a0edcd Mon Sep 17 00:00:00 2001 From: Philip Reames Date: Mon, 20 Mar 2023 08:44:15 -0700 Subject: [PATCH] [LSR/LFTR] Move two utilities to common code for reuse [nfc] We're working on a transform in LSR which is essentiall an inverse of LFTR (in certain sub-cases). Move utilties so that they can be reused. --- llvm/include/llvm/Analysis/ValueTracking.h | 11 +++++ llvm/include/llvm/Transforms/Utils/LoopUtils.h | 5 +++ llvm/lib/Analysis/ValueTracking.cpp | 44 ++++++++++++++++++ llvm/lib/Transforms/Scalar/IndVarSimplify.cpp | 62 +------------------------- llvm/lib/Transforms/Utils/LoopUtils.cpp | 13 ++++++ 5 files changed, 75 insertions(+), 60 deletions(-) diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h index 51ee3ad..23be9d9 100644 --- a/llvm/include/llvm/Analysis/ValueTracking.h +++ b/llvm/include/llvm/Analysis/ValueTracking.h @@ -797,6 +797,17 @@ bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC = nullptr, const DominatorTree *DT = nullptr, unsigned Depth = 0); +/// Return true if undefined behavior would provable be executed on the path to +/// OnPathTo if Root produced a posion result. Note that this doesn't say +/// anything about whether OnPathTo is actually executed or whether Root is +/// actually poison. This can be used to assess whether a new use of Root can +/// be added at a location which is control equivalent with OnPathTo (such as +/// immediately before it) without introducing UB which didn't previously +/// exist. Note that a false result conveys no information. +bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root, + Instruction *OnPathTo, + DominatorTree *DT); + /// Specific patterns of select instructions we can match. enum SelectPatternFlavor { SPF_UNKNOWN = 0, diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h index d63bee6..2c84135 100644 --- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -175,6 +175,11 @@ bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, bool, bool AllowSpeculation); +/// Return true if the induction variable \p IV in a Loop whose latch is +/// \p LatchBlock would become dead if the exit test \p Cond were removed. +/// Conservatively returns false if analysis is insufficient. +bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond); + /// This function deletes dead loops. The caller of this function needs to /// guarantee that the loop is infact dead. /// The function requires a bunch or prerequisites to be present: diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index 905b4ac..628a124 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -6091,6 +6091,50 @@ bool llvm::isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC, return ::isGuaranteedNotToBeUndefOrPoison(V, AC, CtxI, DT, Depth, true); } +/// Return true if undefined behavior would provable be executed on the path to +/// OnPathTo if Root produced a posion result. Note that this doesn't say +/// anything about whether OnPathTo is actually executed or whether Root is +/// actually poison. This can be used to assess whether a new use of Root can +/// be added at a location which is control equivalent with OnPathTo (such as +/// immediately before it) without introducing UB which didn't previously +/// exist. Note that a false result conveys no information. +bool llvm::mustExecuteUBIfPoisonOnPathTo(Instruction *Root, + Instruction *OnPathTo, + DominatorTree *DT) { + // Basic approach is to assume Root is poison, propagate poison forward + // through all users we can easily track, and then check whether any of those + // users are provable UB and must execute before out exiting block might + // exit. + + // The set of all recursive users we've visited (which are assumed to all be + // poison because of said visit) + SmallSet KnownPoison; + SmallVector Worklist; + Worklist.push_back(Root); + while (!Worklist.empty()) { + const Instruction *I = Worklist.pop_back_val(); + + // If we know this must trigger UB on a path leading our target. + if (mustTriggerUB(I, KnownPoison) && DT->dominates(I, OnPathTo)) + return true; + + // If we can't analyze propagation through this instruction, just skip it + // and transitive users. Safe as false is a conservative result. + if (I != Root && !any_of(I->operands(), [&KnownPoison](const Use &U) { + return KnownPoison.contains(U) && propagatesPoison(U); + })) + continue; + + if (KnownPoison.insert(I).second) + for (const User *User : I->users()) + Worklist.push_back(cast(User)); + } + + // Might be non-UB, or might have a path we couldn't prove must execute on + // way to exiting bb. + return false; +} + OverflowResult llvm::computeOverflowForSignedAdd(const AddOperator *Add, const DataLayout &DL, AssumptionCache *AC, diff --git a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp index 1f79db7..0f784a8 100644 --- a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -750,50 +750,6 @@ static bool needsLFTR(Loop *L, BasicBlock *ExitingBB) { return Phi != getLoopPhiForCounter(IncV, L); } -/// Return true if undefined behavior would provable be executed on the path to -/// OnPathTo if Root produced a posion result. Note that this doesn't say -/// anything about whether OnPathTo is actually executed or whether Root is -/// actually poison. This can be used to assess whether a new use of Root can -/// be added at a location which is control equivalent with OnPathTo (such as -/// immediately before it) without introducing UB which didn't previously -/// exist. Note that a false result conveys no information. -static bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root, - Instruction *OnPathTo, - DominatorTree *DT) { - // Basic approach is to assume Root is poison, propagate poison forward - // through all users we can easily track, and then check whether any of those - // users are provable UB and must execute before out exiting block might - // exit. - - // The set of all recursive users we've visited (which are assumed to all be - // poison because of said visit) - SmallSet KnownPoison; - SmallVector Worklist; - Worklist.push_back(Root); - while (!Worklist.empty()) { - const Instruction *I = Worklist.pop_back_val(); - - // If we know this must trigger UB on a path leading our target. - if (mustTriggerUB(I, KnownPoison) && DT->dominates(I, OnPathTo)) - return true; - - // If we can't analyze propagation through this instruction, just skip it - // and transitive users. Safe as false is a conservative result. - if (I != Root && !any_of(I->operands(), [&KnownPoison](const Use &U) { - return KnownPoison.contains(U) && propagatesPoison(U); - })) - continue; - - if (KnownPoison.insert(I).second) - for (const User *User : I->users()) - Worklist.push_back(cast(User)); - } - - // Might be non-UB, or might have a path we couldn't prove must execute on - // way to exiting bb. - return false; -} - /// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils /// down to checking that all operands are constant and listing instructions /// that may hide undef. @@ -836,20 +792,6 @@ static bool hasConcreteDef(Value *V) { return hasConcreteDefImpl(V, Visited, 0); } -/// Return true if this IV has any uses other than the (soon to be rewritten) -/// loop exit test. -static bool AlmostDeadIV(PHINode *Phi, BasicBlock *LatchBlock, Value *Cond) { - int LatchIdx = Phi->getBasicBlockIndex(LatchBlock); - Value *IncV = Phi->getIncomingValue(LatchIdx); - - for (User *U : Phi->users()) - if (U != Cond && U != IncV) return false; - - for (User *U : IncV->users()) - if (U != Cond && U != Phi) return false; - return true; -} - /// Return true if the given phi is a "counter" in L. A counter is an /// add recurance (of integer or pointer type) with an arbitrary start, and a /// step of 1. Note that L must have exactly one latch. @@ -940,9 +882,9 @@ static PHINode *FindLoopCounter(Loop *L, BasicBlock *ExitingBB, const SCEV *Init = AR->getStart(); - if (BestPhi && !AlmostDeadIV(BestPhi, LatchBlock, Cond)) { + if (BestPhi && !isAlmostDeadIV(BestPhi, LatchBlock, Cond)) { // Don't force a live loop counter if another IV can be used. - if (AlmostDeadIV(Phi, LatchBlock, Cond)) + if (isAlmostDeadIV(Phi, LatchBlock, Cond)) continue; // Prefer to count-from-zero. This is a more "canonical" counter form. It diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp index 7df8651..1c58370 100644 --- a/llvm/lib/Transforms/Utils/LoopUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -466,6 +466,19 @@ llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) { return Worklist; } +bool llvm::isAlmostDeadIV(PHINode *PN, BasicBlock *LatchBlock, Value *Cond) { + int LatchIdx = PN->getBasicBlockIndex(LatchBlock); + Value *IncV = PN->getIncomingValue(LatchIdx); + + for (User *U : PN->users()) + if (U != Cond && U != IncV) return false; + + for (User *U : IncV->users()) + if (U != Cond && U != PN) return false; + return true; +} + + void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA) { assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!"); -- 2.7.4