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