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