llvm/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp

   1 //===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines the ScalarEvolutionAliasAnalysis pass, which implements a
  10 // simple alias analysis implemented in terms of ScalarEvolution queries.
  11 //
  12 // This differs from traditional loop dependence analysis in that it tests
  13 // for dependencies within a single iteration of a loop, rather than
  14 // dependencies between different iterations.
  15 //
  16 // ScalarEvolution has a more complete understanding of pointer arithmetic
  17 // than BasicAliasAnalysis' collection of ad-hoc analyses.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
  22 #include "llvm/Analysis/ScalarEvolution.h"
  23 #include "llvm/InitializePasses.h"
  24 using namespace llvm;
  25
  26 AliasResult SCEVAAResult::alias(const MemoryLocation &LocA,
  27                                 const MemoryLocation &LocB, AAQueryInfo &AAQI) {
  28   // If either of the memory references is empty, it doesn't matter what the
  29   // pointer values are. This allows the code below to ignore this special
  30   // case.
  31   if (LocA.Size.isZero() || LocB.Size.isZero())
  32     return AliasResult::NoAlias;
  33
  34   // This is SCEVAAResult. Get the SCEVs!
  35   const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
  36   const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
  37
  38   // If they evaluate to the same expression, it's a MustAlias.
  39   if (AS == BS)
  40     return AliasResult::MustAlias;
  41
  42   // If something is known about the difference between the two addresses,
  43   // see if it's enough to prove a NoAlias.
  44   if (SE.getEffectiveSCEVType(AS->getType()) ==
  45       SE.getEffectiveSCEVType(BS->getType())) {
  46     unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
  47     APInt ASizeInt(BitWidth, LocA.Size.hasValue()
  48                                  ? LocA.Size.getValue()
  49                                  : MemoryLocation::UnknownSize);
  50     APInt BSizeInt(BitWidth, LocB.Size.hasValue()
  51                                  ? LocB.Size.getValue()
  52                                  : MemoryLocation::UnknownSize);
  53
  54     // Compute the difference between the two pointers.
  55     const SCEV *BA = SE.getMinusSCEV(BS, AS);
  56
  57     // Test whether the difference is known to be great enough that memory of
  58     // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
  59     // are non-zero, which is special-cased above.
  60     if (!isa<SCEVCouldNotCompute>(BA) &&
  61         ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
  62         (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
  63       return AliasResult::NoAlias;
  64
  65     // Folding the subtraction while preserving range information can be tricky
  66     // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
  67     // and try again to see if things fold better that way.
  68
  69     // Compute the difference between the two pointers.
  70     const SCEV *AB = SE.getMinusSCEV(AS, BS);
  71
  72     // Test whether the difference is known to be great enough that memory of
  73     // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
  74     // are non-zero, which is special-cased above.
  75     if (!isa<SCEVCouldNotCompute>(AB) &&
  76         BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
  77         (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
  78       return AliasResult::NoAlias;
  79   }
  80
  81   // If ScalarEvolution can find an underlying object, form a new query.
  82   // The correctness of this depends on ScalarEvolution not recognizing
  83   // inttoptr and ptrtoint operators.
  84   Value *AO = GetBaseValue(AS);
  85   Value *BO = GetBaseValue(BS);
  86   if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
  87     if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
  88                              AO ? LocationSize::beforeOrAfterPointer()
  89                                 : LocA.Size,
  90                              AO ? AAMDNodes() : LocA.AATags),
  91               MemoryLocation(BO ? BO : LocB.Ptr,
  92                              BO ? LocationSize::beforeOrAfterPointer()
  93                                 : LocB.Size,
  94                              BO ? AAMDNodes() : LocB.AATags),
  95               AAQI) == AliasResult::NoAlias)
  96       return AliasResult::NoAlias;
  97
  98   // Forward the query to the next analysis.
  99   return AAResultBase::alias(LocA, LocB, AAQI);
 100 }
 101
 102 /// Given an expression, try to find a base value.
 103 ///
 104 /// Returns null if none was found.
 105 Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
 106   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
 107     // In an addrec, assume that the base will be in the start, rather
 108     // than the step.
 109     return GetBaseValue(AR->getStart());
 110   } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
 111     // If there's a pointer operand, it'll be sorted at the end of the list.
 112     const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
 113     if (Last->getType()->isPointerTy())
 114       return GetBaseValue(Last);
 115   } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
 116     // This is a leaf node.
 117     return U->getValue();
 118   }
 119   // No Identified object found.
 120   return nullptr;
 121 }
 122
 123 bool SCEVAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA,
 124                               FunctionAnalysisManager::Invalidator &Inv) {
 125   // We don't care if this analysis itself is preserved, it has no state. But
 126   // we need to check that the analyses it depends on have been.
 127   return Inv.invalidate<ScalarEvolutionAnalysis>(Fn, PA);
 128 }
 129
 130 AnalysisKey SCEVAA::Key;
 131
 132 SCEVAAResult SCEVAA::run(Function &F, FunctionAnalysisManager &AM) {
 133   return SCEVAAResult(AM.getResult<ScalarEvolutionAnalysis>(F));
 134 }
 135
 136 char SCEVAAWrapperPass::ID = 0;
 137 INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa",
 138                       "ScalarEvolution-based Alias Analysis", false, true)
 139 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 140 INITIALIZE_PASS_END(SCEVAAWrapperPass, "scev-aa",
 141                     "ScalarEvolution-based Alias Analysis", false, true)
 142
 143 FunctionPass *llvm::createSCEVAAWrapperPass() {
 144   return new SCEVAAWrapperPass();
 145 }
 146
 147 SCEVAAWrapperPass::SCEVAAWrapperPass() : FunctionPass(ID) {
 148   initializeSCEVAAWrapperPassPass(*PassRegistry::getPassRegistry());
 149 }
 150
 151 bool SCEVAAWrapperPass::runOnFunction(Function &F) {
 152   Result.reset(
 153       new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
 154   return false;
 155 }
 156
 157 void SCEVAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 158   AU.setPreservesAll();
 159   AU.addRequired<ScalarEvolutionWrapperPass>();
 160 }