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/Passes.h"
23#include "llvm/Analysis/AliasAnalysis.h"
24#include "llvm/Analysis/ScalarEvolutionExpressions.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(nullptr) {
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    void *getAdjustedAnalysisPointer(AnalysisID PI) override {
47      if (PI == &AliasAnalysis::ID)
48        return (AliasAnalysis*)this;
49      return this;
50    }
51
52  private:
53    void getAnalysisUsage(AnalysisUsage &AU) const override;
54    bool runOnFunction(Function &F) override;
55    AliasResult alias(const Location &LocA, const Location &LocB) override;
56
57    Value *GetBaseValue(const SCEV *S);
58  };
59}  // End of anonymous namespace
60
61// Register this pass...
62char ScalarEvolutionAliasAnalysis::ID = 0;
63INITIALIZE_AG_PASS_BEGIN(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa",
64                   "ScalarEvolution-based Alias Analysis", false, true, false)
65INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
66INITIALIZE_AG_PASS_END(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa",
67                    "ScalarEvolution-based Alias Analysis", false, true, false)
68
69FunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() {
70  return new ScalarEvolutionAliasAnalysis();
71}
72
73void
74ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
75  AU.addRequiredTransitive<ScalarEvolution>();
76  AU.setPreservesAll();
77  AliasAnalysis::getAnalysisUsage(AU);
78}
79
80bool
81ScalarEvolutionAliasAnalysis::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.
89Value *
90ScalarEvolutionAliasAnalysis::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 nullptr;
106}
107
108AliasAnalysis::AliasResult
109ScalarEvolutionAliasAnalysis::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 ? nullptr : LocA.TBAATag),
166              Location(BO ? BO : LocB.Ptr,
167                       BO ? +UnknownSize : LocB.Size,
168                       BO ? nullptr : LocB.TBAATag)) == NoAlias)
169      return NoAlias;
170
171  // Forward the query to the next analysis.
172  return AliasAnalysis::alias(LocA, LocB);
173}
174