b394bc33f6ee25db1318e5b57824c0a9ed767ed3
[oota-llvm.git] / include / llvm / Analysis / BasicAliasAnalysis.h
1 //===- BasicAliasAnalysis.h - Stateless, local Alias Analysis ---*- C++ -*-===//
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 /// \file
10 /// This is the interface for LLVM's primary stateless and local alias analysis.
11 ///
12 //===----------------------------------------------------------------------===//
13
14 #ifndef LLVM_ANALYSIS_BASICALIASANALYSIS_H
15 #define LLVM_ANALYSIS_BASICALIASANALYSIS_H
16
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/Analysis/AliasAnalysis.h"
19 #include "llvm/Analysis/AssumptionCache.h"
20 #include "llvm/Analysis/TargetLibraryInfo.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/IR/GetElementPtrTypeIterator.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/IR/LLVMContext.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/Pass.h"
27 #include "llvm/Support/ErrorHandling.h"
28
29 namespace llvm {
30
31 /// BasicAliasAnalysis - This is the primary alias analysis implementation.
32 struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis {
33   static char ID; // Class identification, replacement for typeinfo
34
35 #ifndef NDEBUG
36   static const Function *getParent(const Value *V) {
37     if (const Instruction *inst = dyn_cast<Instruction>(V))
38       return inst->getParent()->getParent();
39
40     if (const Argument *arg = dyn_cast<Argument>(V))
41       return arg->getParent();
42
43     return nullptr;
44   }
45
46   static bool notDifferentParent(const Value *O1, const Value *O2) {
47
48     const Function *F1 = getParent(O1);
49     const Function *F2 = getParent(O2);
50
51     return !F1 || !F2 || F1 == F2;
52   }
53 #endif
54
55   BasicAliasAnalysis() : ImmutablePass(ID) {
56     initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry());
57   }
58
59   bool doInitialization(Module &M) override;
60
61   void getAnalysisUsage(AnalysisUsage &AU) const override {
62     AU.addRequired<AliasAnalysis>();
63     AU.addRequired<AssumptionCacheTracker>();
64     AU.addRequired<TargetLibraryInfoWrapperPass>();
65   }
66
67   AliasResult alias(const MemoryLocation &LocA,
68                     const MemoryLocation &LocB) override {
69     assert(AliasCache.empty() && "AliasCache must be cleared after use!");
70     assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
71            "BasicAliasAnalysis doesn't support interprocedural queries.");
72     AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
73                                    LocB.Size, LocB.AATags);
74     // AliasCache rarely has more than 1 or 2 elements, always use
75     // shrink_and_clear so it quickly returns to the inline capacity of the
76     // SmallDenseMap if it ever grows larger.
77     // FIXME: This should really be shrink_to_inline_capacity_and_clear().
78     AliasCache.shrink_and_clear();
79     VisitedPhiBBs.clear();
80     return Alias;
81   }
82
83   ModRefInfo getModRefInfo(ImmutableCallSite CS,
84                            const MemoryLocation &Loc) override;
85
86   ModRefInfo getModRefInfo(ImmutableCallSite CS1,
87                            ImmutableCallSite CS2) override;
88
89   /// pointsToConstantMemory - Chase pointers until we find a (constant
90   /// global) or not.
91   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) override;
92
93   /// Get the location associated with a pointer argument of a callsite.
94   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) override;
95
96   /// getModRefBehavior - Return the behavior when calling the given
97   /// call site.
98   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) override;
99
100   /// getModRefBehavior - Return the behavior when calling the given function.
101   /// For use when the call site is not known.
102   FunctionModRefBehavior getModRefBehavior(const Function *F) override;
103
104   /// getAdjustedAnalysisPointer - This method is used when a pass implements
105   /// an analysis interface through multiple inheritance.  If needed, it
106   /// should override this to adjust the this pointer as needed for the
107   /// specified pass info.
108   void *getAdjustedAnalysisPointer(const void *ID) override {
109     if (ID == &AliasAnalysis::ID)
110       return (AliasAnalysis *)this;
111     return this;
112   }
113
114 private:
115   enum ExtensionKind { EK_NotExtended, EK_SignExt, EK_ZeroExt };
116
117   struct VariableGEPIndex {
118     const Value *V;
119     ExtensionKind Extension;
120     int64_t Scale;
121
122     bool operator==(const VariableGEPIndex &Other) const {
123       return V == Other.V && Extension == Other.Extension &&
124              Scale == Other.Scale;
125     }
126
127     bool operator!=(const VariableGEPIndex &Other) const {
128       return !operator==(Other);
129     }
130   };
131
132   // AliasCache - Track alias queries to guard against recursion.
133   typedef std::pair<MemoryLocation, MemoryLocation> LocPair;
134   typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
135   AliasCacheTy AliasCache;
136
137   /// \brief Track phi nodes we have visited. When interpret "Value" pointer
138   /// equality as value equality we need to make sure that the "Value" is not
139   /// part of a cycle. Otherwise, two uses could come from different
140   /// "iterations" of a cycle and see different values for the same "Value"
141   /// pointer.
142   /// The following example shows the problem:
143   ///   %p = phi(%alloca1, %addr2)
144   ///   %l = load %ptr
145   ///   %addr1 = gep, %alloca2, 0, %l
146   ///   %addr2 = gep  %alloca2, 0, (%l + 1)
147   ///      alias(%p, %addr1) -> MayAlias !
148   ///   store %l, ...
149   SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
150
151   // Visited - Track instructions visited by pointsToConstantMemory.
152   SmallPtrSet<const Value *, 16> Visited;
153
154   static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
155                                     ExtensionKind &Extension,
156                                     const DataLayout &DL, unsigned Depth,
157                                     AssumptionCache *AC, DominatorTree *DT);
158
159   static const Value *
160   DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
161                          SmallVectorImpl<VariableGEPIndex> &VarIndices,
162                          bool &MaxLookupReached, const DataLayout &DL,
163                          AssumptionCache *AC, DominatorTree *DT);
164
165   /// \brief Check whether two Values can be considered equivalent.
166   ///
167   /// In addition to pointer equivalence of \p V1 and \p V2 this checks
168   /// whether they can not be part of a cycle in the value graph by looking at
169   /// all visited phi nodes an making sure that the phis cannot reach the
170   /// value. We have to do this because we are looking through phi nodes (That
171   /// is we say noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
172   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
173
174   /// \brief Dest and Src are the variable indices from two decomposed
175   /// GetElementPtr instructions GEP1 and GEP2 which have common base
176   /// pointers.  Subtract the GEP2 indices from GEP1 to find the symbolic
177   /// difference between the two pointers.
178   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
179                           const SmallVectorImpl<VariableGEPIndex> &Src);
180
181   // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP
182   // instruction against another.
183   AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
184                        const AAMDNodes &V1AAInfo, const Value *V2,
185                        uint64_t V2Size, const AAMDNodes &V2AAInfo,
186                        const Value *UnderlyingV1, const Value *UnderlyingV2);
187
188   // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI
189   // instruction against another.
190   AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
191                        const AAMDNodes &PNAAInfo, const Value *V2,
192                        uint64_t V2Size, const AAMDNodes &V2AAInfo);
193
194   /// aliasSelect - Disambiguate a Select instruction against another value.
195   AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
196                           const AAMDNodes &SIAAInfo, const Value *V2,
197                           uint64_t V2Size, const AAMDNodes &V2AAInfo);
198
199   AliasResult aliasCheck(const Value *V1, uint64_t V1Size, AAMDNodes V1AATag,
200                          const Value *V2, uint64_t V2Size, AAMDNodes V2AATag);
201 };
202
203 //===--------------------------------------------------------------------===//
204 //
205 // createBasicAliasAnalysisPass - This pass implements the stateless alias
206 // analysis.
207 //
208 ImmutablePass *createBasicAliasAnalysisPass();
209
210 }
211
212 #endif