thr3ads.net - llvm dev - [llvm-dev] Problem with wrong DomTree in BasicAA / ValueTracking [Jan 2021]

If this information is useful, please help other people find it:
Share via:

Nikita Popov via llvm-dev

2021-Jan-05 19:11 UTC

[llvm-dev] Problem with wrong DomTree in BasicAA / ValueTracking

On Mon, Jan 4, 2021 at 9:52 PM Björn Pettersson A <
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://reviews.llvm.org/rGb21840751278128ef6942074ae89ea63c9c6ac58 , as
> we started to see miscompiles after that commit and after
> https://reviews.llvm.org/rGa3614a31c46a41b76fd6a6c6b30b353bc4131b94 .
> 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://lists.llvm.org/pipermail/llvm-dev/2020-November/146923.html.

Regards,
Nikita
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210105/ac6271d7/attachment.html>

Björn Pettersson A via llvm-dev

2021-Jan-06 00:20 UTC

head link

[llvm-dev] Problem with wrong DomTree in BasicAA / ValueTracking

> -----Original Message-----
> From: Nikita Popov <nikita.ppv at gmail.com>
> Sent: den 5 januari 2021 20:12
> To: Björn Pettersson A <bjorn.a.pettersson at ericsson.com>
> Cc: llvm-dev <llvm-dev at lists.llvm.org>; Mikael Holmén
> <mikael.holmen at ericsson.com>; 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: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%2Freviews.llvm.org%2FrGb21840751278128ef694207
> 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%2Freviews.llvm.org%2FrGa3614a31c46a41b76fd6a6c
> 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%2Flists.llvm.org%2Fpipermail%2Fllvm-
> dev%2F2020-November%2F146923.html.
> 
> Regards,
> Nikita
Here is an attempt to fix the problem: https://reviews.llvm.org/D94138

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 dev - Jan 2021 - Problem with wrong DomTree in BasicAA / ValueTracking

[llvm-dev] Problem with wrong DomTree in BasicAA / ValueTracking

[llvm-dev] Problem with wrong DomTree in BasicAA / ValueTracking