ScalarEvolutionAliasAnalysis.cpp revision 1434dfa8cead98bd1e63411fcb9424e1d37f61ac 
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"
26using namespace llvm;
27
28namespace {
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
39    /// getAdjustedAnalysisPointer - This method is used when a pass implements
40    /// an analysis interface through multiple inheritance.  If needed, it
41    /// should override this to adjust the this pointer as needed for the
42    /// specified pass info.
43    virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
44      if (PI == &AliasAnalysis::ID)
45        return (AliasAnalysis*)this;
46      return this;
47    }
48
49  private:
50    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
51    virtual bool runOnFunction(Function &F);
52    virtual AliasResult alias(const Location &LocA, const Location &LocB);
53
54    Value *GetBaseValue(const SCEV *S);
55  };
56}  // End of anonymous namespace
57
58// Register this pass...
59char ScalarEvolutionAliasAnalysis::ID = 0;
60INITIALIZE_AG_PASS(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa",
61                   "ScalarEvolution-based Alias Analysis", false, true, false)
62
63FunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() {
64  return new ScalarEvolutionAliasAnalysis();
65}
66
67void
68ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
69  AU.addRequiredTransitive<ScalarEvolution>();
70  AU.setPreservesAll();
71  AliasAnalysis::getAnalysisUsage(AU);
72}
73
74bool
75ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) {
76  InitializeAliasAnalysis(this);
77  SE = &getAnalysis<ScalarEvolution>();
78  return false;
79}
80
81/// GetBaseValue - Given an expression, try to find a
82/// base value. Return null is none was found.
83Value *
84ScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) {
85  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
86    // In an addrec, assume that the base will be in the start, rather
87    // than the step.
88    return GetBaseValue(AR->getStart());
89  } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
90    // If there's a pointer operand, it'll be sorted at the end of the list.
91    const SCEV *Last = A->getOperand(A->getNumOperands()-1);
92    if (Last->getType()->isPointerTy())
93      return GetBaseValue(Last);
94  } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
95    // This is a leaf node.
96    return U->getValue();
97  }
98  // No Identified object found.
99  return 0;
100}
101
102AliasAnalysis::AliasResult
103ScalarEvolutionAliasAnalysis::alias(const Location &LocA,
104                                    const Location &LocB) {
105  // If either of the memory references is empty, it doesn't matter what the
106  // pointer values are. This allows the code below to ignore this special
107  // case.
108  if (LocA.Size == 0 || LocB.Size == 0)
109    return NoAlias;
110
111  // This is ScalarEvolutionAliasAnalysis. Get the SCEVs!
112  const SCEV *AS = SE->getSCEV(const_cast<Value *>(LocA.Ptr));
113  const SCEV *BS = SE->getSCEV(const_cast<Value *>(LocB.Ptr));
114
115  // If they evaluate to the same expression, it's a MustAlias.
116  if (AS == BS) return MustAlias;
117
118  // If something is known about the difference between the two addresses,
119  // see if it's enough to prove a NoAlias.
120  if (SE->getEffectiveSCEVType(AS->getType()) ==
121      SE->getEffectiveSCEVType(BS->getType())) {
122    unsigned BitWidth = SE->getTypeSizeInBits(AS->getType());
123    APInt ASizeInt(BitWidth, LocA.Size);
124    APInt BSizeInt(BitWidth, LocB.Size);
125
126    // Compute the difference between the two pointers.
127    const SCEV *BA = SE->getMinusSCEV(BS, AS);
128
129    // Test whether the difference is known to be great enough that memory of
130    // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
131    // are non-zero, which is special-cased above.
132    if (ASizeInt.ule(SE->getUnsignedRange(BA).getUnsignedMin()) &&
133        (-BSizeInt).uge(SE->getUnsignedRange(BA).getUnsignedMax()))
134      return NoAlias;
135
136    // Folding the subtraction while preserving range information can be tricky
137    // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
138    // and try again to see if things fold better that way.
139
140    // Compute the difference between the two pointers.
141    const SCEV *AB = SE->getMinusSCEV(AS, BS);
142
143    // Test whether the difference is known to be great enough that memory of
144    // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
145    // are non-zero, which is special-cased above.
146    if (BSizeInt.ule(SE->getUnsignedRange(AB).getUnsignedMin()) &&
147        (-ASizeInt).uge(SE->getUnsignedRange(AB).getUnsignedMax()))
148      return NoAlias;
149  }
150
151  // If ScalarEvolution can find an underlying object, form a new query.
152  // The correctness of this depends on ScalarEvolution not recognizing
153  // inttoptr and ptrtoint operators.
154  Value *AO = GetBaseValue(AS);
155  Value *BO = GetBaseValue(BS);
156  if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
157    if (alias(Location(AO ? AO : LocA.Ptr,
158                       AO ? +UnknownSize : LocA.Size,
159                       AO ? 0 : LocA.TBAATag),
160              Location(BO ? BO : LocB.Ptr,
161                       BO ? +UnknownSize : LocB.Size,
162                       BO ? 0 : LocB.TBAATag)) == NoAlias)
163      return NoAlias;
164
165  // Forward the query to the next analysis.
166  return AliasAnalysis::alias(LocA, LocB);
167}
168