Home | History | Annotate | Download | only in Analysis 
      1 //===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file defines the ScalarEvolutionAliasAnalysis pass, which implements a
     11 // simple alias analysis implemented in terms of ScalarEvolution queries.
     12 //
     13 // This differs from traditional loop dependence analysis in that it tests
     14 // for dependencies within a single iteration of a loop, rather than
     15 // dependencies between different iterations.
     16 //
     17 // ScalarEvolution has a more complete understanding of pointer arithmetic
     18 // than BasicAliasAnalysis' collection of ad-hoc analyses.
     19 //
     20 //===----------------------------------------------------------------------===//
     21 
     22 #include "llvm/Analysis/AliasAnalysis.h"
     23 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
     24 #include "llvm/Analysis/Passes.h"
     25 #include "llvm/Pass.h"
     26 using namespace llvm;
     27 
     28 namespace {
     29   /// ScalarEvolutionAliasAnalysis - This is a simple alias analysis
     30   /// implementation that uses ScalarEvolution to answer queries.
     31   class ScalarEvolutionAliasAnalysis : public FunctionPass,
     32                                        public AliasAnalysis {
     33     ScalarEvolution *SE;
     34 
     35   public:
     36     static char ID; // Class identification, replacement for typeinfo
     37     ScalarEvolutionAliasAnalysis() : FunctionPass(ID), SE(0) {
     38       initializeScalarEvolutionAliasAnalysisPass(
     39         *PassRegistry::getPassRegistry());
     40     }
     41 
     42     /// getAdjustedAnalysisPointer - This method is used when a pass implements
     43     /// an analysis interface through multiple inheritance.  If needed, it
     44     /// should override this to adjust the this pointer as needed for the
     45     /// specified pass info.
     46     virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
     47       if (PI == &AliasAnalysis::ID)
     48         return (AliasAnalysis*)this;
     49       return this;
     50     }
     51 
     52   private:
     53     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
     54     virtual bool runOnFunction(Function &F);
     55     virtual AliasResult alias(const Location &LocA, const Location &LocB);
     56 
     57     Value *GetBaseValue(const SCEV *S);
     58   };
     59 }  // End of anonymous namespace
     60 
     61 // Register this pass...
     62 char ScalarEvolutionAliasAnalysis::ID = 0;
     63 INITIALIZE_AG_PASS_BEGIN(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa",
     64                    "ScalarEvolution-based Alias Analysis", false, true, false)
     65 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
     66 INITIALIZE_AG_PASS_END(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa",
     67                     "ScalarEvolution-based Alias Analysis", false, true, false)
     68 
     69 FunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() {
     70   return new ScalarEvolutionAliasAnalysis();
     71 }
     72 
     73 void
     74 ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
     75   AU.addRequiredTransitive<ScalarEvolution>();
     76   AU.setPreservesAll();
     77   AliasAnalysis::getAnalysisUsage(AU);
     78 }
     79 
     80 bool
     81 ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) {
     82   InitializeAliasAnalysis(this);
     83   SE = &getAnalysis<ScalarEvolution>();
     84   return false;
     85 }
     86 
     87 /// GetBaseValue - Given an expression, try to find a
     88 /// base value. Return null is none was found.
     89 Value *
     90 ScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) {
     91   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
     92     // In an addrec, assume that the base will be in the start, rather
     93     // than the step.
     94     return GetBaseValue(AR->getStart());
     95   } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
     96     // If there's a pointer operand, it'll be sorted at the end of the list.
     97     const SCEV *Last = A->getOperand(A->getNumOperands()-1);
     98     if (Last->getType()->isPointerTy())
     99       return GetBaseValue(Last);
    100   } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
    101     // This is a leaf node.
    102     return U->getValue();
    103   }
    104   // No Identified object found.
    105   return 0;
    106 }
    107 
    108 AliasAnalysis::AliasResult
    109 ScalarEvolutionAliasAnalysis::alias(const Location &LocA,
    110                                     const Location &LocB) {
    111   // If either of the memory references is empty, it doesn't matter what the
    112   // pointer values are. This allows the code below to ignore this special
    113   // case.
    114   if (LocA.Size == 0 || LocB.Size == 0)
    115     return NoAlias;
    116 
    117   // This is ScalarEvolutionAliasAnalysis. Get the SCEVs!
    118   const SCEV *AS = SE->getSCEV(const_cast<Value *>(LocA.Ptr));
    119   const SCEV *BS = SE->getSCEV(const_cast<Value *>(LocB.Ptr));
    120 
    121   // If they evaluate to the same expression, it's a MustAlias.
    122   if (AS == BS) return MustAlias;
    123 
    124   // If something is known about the difference between the two addresses,
    125   // see if it's enough to prove a NoAlias.
    126   if (SE->getEffectiveSCEVType(AS->getType()) ==
    127       SE->getEffectiveSCEVType(BS->getType())) {
    128     unsigned BitWidth = SE->getTypeSizeInBits(AS->getType());
    129     APInt ASizeInt(BitWidth, LocA.Size);
    130     APInt BSizeInt(BitWidth, LocB.Size);
    131 
    132     // Compute the difference between the two pointers.
    133     const SCEV *BA = SE->getMinusSCEV(BS, AS);
    134 
    135     // Test whether the difference is known to be great enough that memory of
    136     // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
    137     // are non-zero, which is special-cased above.
    138     if (ASizeInt.ule(SE->getUnsignedRange(BA).getUnsignedMin()) &&
    139         (-BSizeInt).uge(SE->getUnsignedRange(BA).getUnsignedMax()))
    140       return NoAlias;
    141 
    142     // Folding the subtraction while preserving range information can be tricky
    143     // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
    144     // and try again to see if things fold better that way.
    145 
    146     // Compute the difference between the two pointers.
    147     const SCEV *AB = SE->getMinusSCEV(AS, BS);
    148 
    149     // Test whether the difference is known to be great enough that memory of
    150     // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
    151     // are non-zero, which is special-cased above.
    152     if (BSizeInt.ule(SE->getUnsignedRange(AB).getUnsignedMin()) &&
    153         (-ASizeInt).uge(SE->getUnsignedRange(AB).getUnsignedMax()))
    154       return NoAlias;
    155   }
    156 
    157   // If ScalarEvolution can find an underlying object, form a new query.
    158   // The correctness of this depends on ScalarEvolution not recognizing
    159   // inttoptr and ptrtoint operators.
    160   Value *AO = GetBaseValue(AS);
    161   Value *BO = GetBaseValue(BS);
    162   if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
    163     if (alias(Location(AO ? AO : LocA.Ptr,
    164                        AO ? +UnknownSize : LocA.Size,
    165                        AO ? 0 : LocA.TBAATag),
    166               Location(BO ? BO : LocB.Ptr,
    167                        BO ? +UnknownSize : LocB.Size,
    168                        BO ? 0 : LocB.TBAATag)) == NoAlias)
    169       return NoAlias;
    170 
    171   // Forward the query to the next analysis.
    172   return AliasAnalysis::alias(LocA, LocB);
    173 }
    174