<div dir="ltr">(Post)DominatorWrapperPass implement domtree verification in (Post)DominatorTreeWrapperPass::verifyAnalysis when expensive checks are enabled or `--verify-dom-info` is passed.<br>I don't know under what exact conditions verifyAnalysis is actually checked though, so I'm not sure if that'd work in those cases.<br><br>-Jakub<br><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jan 5, 2021 at 7:20 PM Björn Pettersson A via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">> -----Original Message-----<br>
> From: Nikita Popov <<a href="mailto:nikita.ppv@gmail.com" target="_blank">nikita.ppv@gmail.com</a>><br>
> Sent: den 5 januari 2021 20:12<br>
> To: Björn Pettersson A <<a href="mailto:bjorn.a.pettersson@ericsson.com" target="_blank">bjorn.a.pettersson@ericsson.com</a>><br>
> Cc: llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>; Mikael Holmén<br>
> <<a href="mailto:mikael.holmen@ericsson.com" target="_blank">mikael.holmen@ericsson.com</a>>; <a href="mailto:jay.foad@amd.com" target="_blank">jay.foad@amd.com</a><br>
> Subject: Re: Problem with wrong DomTree in BasicAA / ValueTracking<br>
> <br>
> On Mon, Jan 4, 2021 at 9:52 PM Björn Pettersson A<br>
> <mailto:<a href="mailto:bjorn.a.pettersson@ericsson.com" target="_blank">bjorn.a.pettersson@ericsson.com</a>> wrote:<br>
> Hi llvm-dev!<br>
> <br>
> By adding some checks that the dominator tree is correct in<br>
> BasicAliasAnalysis and ValueTracking, such as below, a number of lit<br>
> tests are failing.<br>
> <br>
> I stumbled upon this problem when analyzing some miscompiles for our OOT<br>
> target, but I think this also indicates that there could be similar<br>
> problems in-tree.<br>
> <br>
> <br>
> Here are some examples of checks that I've played around with:<br>
> <br>
> <br>
> diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp<br>
> b/llvm/lib/Analysis/BasicAliasAnalysis.cpp<br>
> index a0da8b7347ea..adb4b6908ada 100644<br>
> --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp<br>
> +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp<br>
> @@ -1099,6 +1099,8 @@ AliasResult BasicAAResult::aliasGEP(<br>
> const GEPOperator *GEP1, LocationSize V1Size, const AAMDNodes<br>
> &V1AAInfo,<br>
> const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo,<br>
> const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo<br>
> &AAQI) {<br>
> + if (DT)<br>
> + DT->verify();<br>
> DecomposedGEP DecompGEP1 = DecomposeGEPExpression(GEP1, DL, &AC, DT);<br>
> DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V2, DL, &AC, DT);<br>
> <br>
> @@ -1699,6 +1701,8 @@ AliasResult BasicAAResult::aliasCheck(const Value<br>
> *V1, LocationSize V1Size,<br>
> /// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).<br>
> bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,<br>
> const Value *V2) {<br>
> + if (DT)<br>
> + DT->verify();<br>
> if (V != V2)<br>
> return false;<br>
> <br>
> diff --git a/llvm/lib/Analysis/ValueTracking.cpp<br>
> b/llvm/lib/Analysis/ValueTracking.cpp<br>
> index 303240d03c72..dc2918a0f895 100644<br>
> --- a/llvm/lib/Analysis/ValueTracking.cpp<br>
> +++ b/llvm/lib/Analysis/ValueTracking.cpp<br>
> @@ -257,6 +257,8 @@ KnownBits llvm::computeKnownBits(const Value *V,<br>
> const APInt &DemandedElts,<br>
> const DominatorTree *DT,<br>
> OptimizationRemarkEmitter *ORE,<br>
> bool UseInstrInfo) {<br>
> + if (DT)<br>
> + DT->verify();<br>
> return ::computeKnownBits(<br>
> V, DemandedElts, Depth,<br>
> Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo, ORE));<br>
> @@ -266,6 +268,8 @@ bool llvm::haveNoCommonBitsSet(const Value *LHS,<br>
> const Value *RHS,<br>
> const DataLayout &DL, AssumptionCache<br>
> *AC,<br>
> const Instruction *CxtI, const<br>
> DominatorTree *DT,<br>
> bool UseInstrInfo) {<br>
> + if (DT)<br>
> + DT->verify();<br>
> assert(LHS->getType() == RHS->getType() &&<br>
> "LHS and RHS should have the same type");<br>
> assert(LHS->getType()->isIntOrIntVectorTy() &&<br>
> @@ -393,6 +397,8 @@ unsigned llvm::ComputeNumSignBits(const Value *V,<br>
> const DataLayout &DL,<br>
> unsigned Depth, AssumptionCache *AC,<br>
> const Instruction *CxtI,<br>
> const DominatorTree *DT, bool<br>
> UseInstrInfo) {<br>
> + if (DT)<br>
> + DT->verify();<br>
> return ::ComputeNumSignBits(<br>
> V, Depth, Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo));<br>
> }<br>
> @@ -548,6 +554,8 @@ bool llvm::isAssumeLikeIntrinsic(const Instruction<br>
> *I) {<br>
> bool llvm::isValidAssumeForContext(const Instruction *Inv,<br>
> const Instruction *CxtI,<br>
> const DominatorTree *DT) {<br>
> + if (DT)<br>
> + DT->verify();<br>
> // There are two restrictions on the use of an assume:<br>
> // 1. The assume must dominate the context (or the control flow must<br>
> // reach the assume whenever it reaches the context).<br>
> @@ -2071,6 +2079,8 @@ static bool isGEPKnownNonNull(const GEPOperator<br>
> *GEP, unsigned Depth,<br>
> static bool isKnownNonNullFromDominatingCondition(const Value *V,<br>
> const Instruction<br>
> *CtxI,<br>
> const DominatorTree<br>
> *DT) {<br>
> + if (DT)<br>
> + DT->verify();<br>
> if (isa<Constant>(V))<br>
> return false;<br>
> <br>
> <br>
> <br>
> <br>
> My current suspicion has been that the LegacyPassManager is calculating<br>
> the "last user" incorrectly sometimes, ending up freeing the<br>
> DominatorTree/BasicAliasAnalysis passes before the last use. If that is<br>
> true, then it still is a bit scary that there are stale pointers (?) to<br>
> an invalid BasicAA/DominatorTree being used later.<br>
> <br>
> One thing that strengthens the suspicion is that if we tell the pass<br>
> manager that the chained analyses used by AliasAnalysis and<br>
> BasicAliasAnalysis are "transitive", then the above problem with faulty<br>
> DominatorTrees aren't seen any longer.<br>
> <br>
> Here is the patch I've played around with to make sure DT is correct:<br>
> diff --git a/llvm/lib/Analysis/AliasAnalysis.cpp<br>
> b/llvm/lib/Analysis/AliasAnalysis.cpp<br>
> index f5b62ef06a23..fae7a84332fd 100644<br>
> --- a/llvm/lib/Analysis/AliasAnalysis.cpp<br>
> +++ b/llvm/lib/Analysis/AliasAnalysis.cpp<br>
> @@ -883,8 +883,8 @@ bool AAResultsWrapperPass::runOnFunction(Function &F)<br>
> {<br>
> <br>
> void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {<br>
> AU.setPreservesAll();<br>
> - AU.addRequired<BasicAAWrapperPass>();<br>
> - AU.addRequired<TargetLibraryInfoWrapperPass>();<br>
> + AU.addRequiredTransitive<BasicAAWrapperPass>();<br>
> + AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();<br>
> <br>
> // We also need to mark all the alias analysis passes we will<br>
> potentially<br>
> // probe in runOnFunction as used here to ensure the legacy pass<br>
> manager<br>
> diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp<br>
> b/llvm/lib/Analysis/BasicAliasAnalysis.cpp<br>
> index f9275daf1224..a0da8b7347ea 100644<br>
> --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp<br>
> +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp<br>
> @@ -1875,9 +1875,9 @@ bool BasicAAWrapperPass::runOnFunction(Function &F)<br>
> {<br>
> <br>
> void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {<br>
> AU.setPreservesAll();<br>
> - AU.addRequired<AssumptionCacheTracker>();<br>
> - AU.addRequired<DominatorTreeWrapperPass>();<br>
> - AU.addRequired<TargetLibraryInfoWrapperPass>();<br>
> + AU.addRequiredTransitive<AssumptionCacheTracker>();<br>
> + AU.addRequiredTransitive<DominatorTreeWrapperPass>();<br>
> + AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();<br>
> AU.addUsedIfAvailable<PhiValuesWrapperPass>();<br>
> }<br>
> <br>
> <br>
> <br>
> <br>
> There is however some problems with such a fix. Because then the<br>
> following tests hits assertions when setting up the pipeline:<br>
> LLVM :: CodeGen/Hexagon/bug15515-shuffle.ll<br>
> LLVM :: CodeGen/Hexagon/const-pool-tf.ll<br>
> LLVM :: CodeGen/Hexagon/glob-align-volatile.ll<br>
> LLVM :: CodeGen/Hexagon/loop-idiom/lcssa.ll<br>
> LLVM :: CodeGen/Hexagon/loop-idiom/pmpy-mod.ll<br>
> LLVM :: Transforms/GVNHoist/hoist-mssa.ll<br>
> LLVM :: Transforms/GVNHoist/hoist-newgvn.ll<br>
> LLVM :: Transforms/GVNHoist/hoist-pr20242.ll<br>
> LLVM :: Transforms/GVNHoist/hoist-pr28933.ll<br>
> LLVM :: Transforms/GVNHoist/hoist-recursive-geps.ll<br>
> LLVM :: Transforms/SimplifyCFG/Hexagon/disable-lookup-table.ll<br>
> LLVM :: Transforms/SimplifyCFG/Hexagon/switch-to-lookup-table.ll<br>
> <br>
> <br>
> So maybe addRequiredTransitive isn't supposed to be used like that?<br>
> <br>
> Or there is something bad with GVNHoist and Hexagon?<br>
> <br>
> <br>
> I haven't looked any closer at Hexagon, but looked a bit at GVNHoist<br>
> without really finding anything weird (comparing it with other passes<br>
> that require AAResults). The assert can be seen if applying the patch<br>
> above and then running<br>
> <br>
> opt -gvn-hoist -gvn-hoist -S /dev/null<br>
> <br>
> and it says<br>
> <br>
> opt: ../lib/IR/LegacyPassManager.cpp:607: void<br>
> llvm::PMTopLevelManager::setLastUser(ArrayRef<llvm::Pass *>, llvm::Pass<br>
> *): Assertion `AnalysisPass && "Expected analysis pass to exist."'<br>
> failed.<br>
> <br>
> <br>
> Afaict the pass that it fails to find is 'Basic Alias Analysis (stateless<br>
> AA impl)'. But I do not understand why.<br>
> <br>
> <br>
> <br>
> Anyone who knows more about addRequiredTransitive, or how one is supposed<br>
> to tell the pass manager about nested analysis pass/group dependencies?<br>
> <br>
> <br>
> PS. This problem has been mentioned a bit in<br>
> <a href="https://protect2.fireeye.com/v1/url?k=5400acdc-0b9b95d9-5400ec47-" rel="noreferrer" target="_blank">https://protect2.fireeye.com/v1/url?k=5400acdc-0b9b95d9-5400ec47-</a><br>
> 86959e472243-78bbd2731c415dae&q=1&e=48bab85e-516e-4e51-8593-<br>
> c5dd8bf6bd72&u=https%3A%2F%<a href="http://2Freviews.llvm.org" rel="noreferrer" target="_blank">2Freviews.llvm.org</a>%2FrGb21840751278128ef694207<br>
> 4ae89ea63c9c6ac58 , as we started to see miscompiles after that commit<br>
> and after <a href="https://protect2.fireeye.com/v1/url?k=4515e9d7-1a8ed0d2-" rel="noreferrer" target="_blank">https://protect2.fireeye.com/v1/url?k=4515e9d7-1a8ed0d2-</a><br>
> 4515a94c-86959e472243-23e5ef273912aa94&q=1&e=48bab85e-516e-4e51-8593-<br>
> c5dd8bf6bd72&u=https%3A%2F%<a href="http://2Freviews.llvm.org" rel="noreferrer" target="_blank">2Freviews.llvm.org</a>%2FrGa3614a31c46a41b76fd6a6c<br>
> 6b30b353bc4131b94 . Those commits seem to have exposed the problem with<br>
> faulty dominator trees a bit more after adding more usage of the<br>
> sometimes faulty DT.<br>
> <br>
> I'm not familiar enough with the pass manager to say something meaningful<br>
> here, but the addRequiredTransitive() issue sounds similar to what is<br>
> discussed in <a href="https://protect2.fireeye.com/v1/url?k=1a01bd60-459a8465-" rel="noreferrer" target="_blank">https://protect2.fireeye.com/v1/url?k=1a01bd60-459a8465-</a><br>
> 1a01fdfb-86959e472243-a43f1a78ef0808a5&q=1&e=48bab85e-516e-4e51-8593-<br>
> c5dd8bf6bd72&u=https%3A%2F%<a href="http://2Flists.llvm.org" rel="noreferrer" target="_blank">2Flists.llvm.org</a>%2Fpipermail%2Fllvm-<br>
> dev%2F2020-November%2F146923.html.<br>
> <br>
> Regards,<br>
> Nikita<br>
<br>
Here is an attempt to fix the problem: <a href="https://reviews.llvm.org/D94138" rel="noreferrer" target="_blank">https://reviews.llvm.org/D94138</a><br>
<br>
Would be nice to add some verifiers (or expensive checks?) to detect<br>
when the DT is wrong, but not really sure how. Calling verify()<br>
every time DominatorTree is used is perhaps a bit costly.<br>
But it might also be that the pass manager should make sure that<br>
this can't happen by invalidating things better when a pass isn't<br>
preserved or when it is removed.<br>
<br>
/Björn<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div>Jakub Kuderski</div></div>