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/DenseMap.h"
18#include "llvm/ADT/Optional.h"
19#include "llvm/ADT/SmallPtrSet.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/Analysis/AliasAnalysis.h"
22#include "llvm/Analysis/AssumptionCache.h"
23#include "llvm/Analysis/MemoryLocation.h"
24#include "llvm/IR/CallSite.h"
25#include "llvm/IR/PassManager.h"
26#include "llvm/Pass.h"
27#include <algorithm>
28#include <cstdint>
29#include <memory>
30#include <utility>
31
32namespace llvm {
33
34struct AAMDNodes;
35class APInt;
36class AssumptionCache;
37class BasicBlock;
38class DataLayout;
39class DominatorTree;
40class Function;
41class GEPOperator;
42class LoopInfo;
43class PHINode;
44class SelectInst;
45class TargetLibraryInfo;
46class Value;
47
48/// This is the AA result object for the basic, local, and stateless alias
49/// analysis. It implements the AA query interface in an entirely stateless
50/// manner. As one consequence, it is never invalidated due to IR changes.
51/// While it does retain some storage, that is used as an optimization and not
52/// to preserve information from query to query. However it does retain handles
53/// to various other analyses and must be recomputed when those analyses are.
54class BasicAAResult : public AAResultBase<BasicAAResult> {
55  friend AAResultBase<BasicAAResult>;
56
57  const DataLayout &DL;
58  const TargetLibraryInfo &TLI;
59  AssumptionCache &AC;
60  DominatorTree *DT;
61  LoopInfo *LI;
62
63public:
64  BasicAAResult(const DataLayout &DL, const TargetLibraryInfo &TLI,
65                AssumptionCache &AC, DominatorTree *DT = nullptr,
66                LoopInfo *LI = nullptr)
67      : AAResultBase(), DL(DL), TLI(TLI), AC(AC), DT(DT), LI(LI) {}
68
69  BasicAAResult(const BasicAAResult &Arg)
70      : AAResultBase(Arg), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
71        LI(Arg.LI) {}
72  BasicAAResult(BasicAAResult &&Arg)
73      : AAResultBase(std::move(Arg)), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC),
74        DT(Arg.DT), LI(Arg.LI) {}
75
76  /// Handle invalidation events in the new pass manager.
77  bool invalidate(Function &F, const PreservedAnalyses &PA,
78                  FunctionAnalysisManager::Invalidator &Inv);
79
80  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
81
82  ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
83
84  ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
85
86  /// Chases pointers until we find a (constant global) or not.
87  bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal);
88
89  /// Get the location associated with a pointer argument of a callsite.
90  ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
91
92  /// Returns the behavior when calling the given call site.
93  FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
94
95  /// Returns the behavior when calling the given function. For use when the
96  /// call site is not known.
97  FunctionModRefBehavior getModRefBehavior(const Function *F);
98
99private:
100  // A linear transformation of a Value; this class represents ZExt(SExt(V,
101  // SExtBits), ZExtBits) * Scale + Offset.
102  struct VariableGEPIndex {
103    // An opaque Value - we can't decompose this further.
104    const Value *V;
105
106    // We need to track what extensions we've done as we consider the same Value
107    // with different extensions as different variables in a GEP's linear
108    // expression;
109    // e.g.: if V == -1, then sext(x) != zext(x).
110    unsigned ZExtBits;
111    unsigned SExtBits;
112
113    int64_t Scale;
114
115    bool operator==(const VariableGEPIndex &Other) const {
116      return V == Other.V && ZExtBits == Other.ZExtBits &&
117             SExtBits == Other.SExtBits && Scale == Other.Scale;
118    }
119
120    bool operator!=(const VariableGEPIndex &Other) const {
121      return !operator==(Other);
122    }
123  };
124
125  // Represents the internal structure of a GEP, decomposed into a base pointer,
126  // constant offsets, and variable scaled indices.
127  struct DecomposedGEP {
128    // Base pointer of the GEP
129    const Value *Base;
130    // Total constant offset w.r.t the base from indexing into structs
131    int64_t StructOffset;
132    // Total constant offset w.r.t the base from indexing through
133    // pointers/arrays/vectors
134    int64_t OtherOffset;
135    // Scaled variable (non-constant) indices.
136    SmallVector<VariableGEPIndex, 4> VarIndices;
137  };
138
139  /// Track alias queries to guard against recursion.
140  using LocPair = std::pair<MemoryLocation, MemoryLocation>;
141  using AliasCacheTy = SmallDenseMap<LocPair, AliasResult, 8>;
142  AliasCacheTy AliasCache;
143
144  /// Tracks phi nodes we have visited.
145  ///
146  /// When interpret "Value" pointer equality as value equality we need to make
147  /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
148  /// come from different "iterations" of a cycle and see different values for
149  /// the same "Value" pointer.
150  ///
151  /// The following example shows the problem:
152  ///   %p = phi(%alloca1, %addr2)
153  ///   %l = load %ptr
154  ///   %addr1 = gep, %alloca2, 0, %l
155  ///   %addr2 = gep  %alloca2, 0, (%l + 1)
156  ///      alias(%p, %addr1) -> MayAlias !
157  ///   store %l, ...
158  SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
159
160  /// Tracks instructions visited by pointsToConstantMemory.
161  SmallPtrSet<const Value *, 16> Visited;
162
163  static const Value *
164  GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset,
165                      unsigned &ZExtBits, unsigned &SExtBits,
166                      const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
167                      DominatorTree *DT, bool &NSW, bool &NUW);
168
169  static bool DecomposeGEPExpression(const Value *V, DecomposedGEP &Decomposed,
170      const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT);
171
172  static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
173      const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
174      uint64_t ObjectAccessSize);
175
176  /// \brief A Heuristic for aliasGEP that searches for a constant offset
177  /// between the variables.
178  ///
179  /// GetLinearExpression has some limitations, as generally zext(%x + 1)
180  /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
181  /// will therefore conservatively refuse to decompose these expressions.
182  /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
183  /// the addition overflows.
184  bool
185  constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
186                          uint64_t V1Size, uint64_t V2Size, int64_t BaseOffset,
187                          AssumptionCache *AC, DominatorTree *DT);
188
189  bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
190
191  void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
192                          const SmallVectorImpl<VariableGEPIndex> &Src);
193
194  AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
195                       const AAMDNodes &V1AAInfo, const Value *V2,
196                       uint64_t V2Size, const AAMDNodes &V2AAInfo,
197                       const Value *UnderlyingV1, const Value *UnderlyingV2);
198
199  AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
200                       const AAMDNodes &PNAAInfo, const Value *V2,
201                       uint64_t V2Size, const AAMDNodes &V2AAInfo,
202                       const Value *UnderV2);
203
204  AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
205                          const AAMDNodes &SIAAInfo, const Value *V2,
206                          uint64_t V2Size, const AAMDNodes &V2AAInfo,
207                          const Value *UnderV2);
208
209  AliasResult aliasCheck(const Value *V1, uint64_t V1Size, AAMDNodes V1AATag,
210                         const Value *V2, uint64_t V2Size, AAMDNodes V2AATag,
211                         const Value *O1 = nullptr, const Value *O2 = nullptr);
212};
213
214/// Analysis pass providing a never-invalidated alias analysis result.
215class BasicAA : public AnalysisInfoMixin<BasicAA> {
216  friend AnalysisInfoMixin<BasicAA>;
217
218  static AnalysisKey Key;
219
220public:
221  using Result = BasicAAResult;
222
223  BasicAAResult run(Function &F, FunctionAnalysisManager &AM);
224};
225
226/// Legacy wrapper pass to provide the BasicAAResult object.
227class BasicAAWrapperPass : public FunctionPass {
228  std::unique_ptr<BasicAAResult> Result;
229
230  virtual void anchor();
231
232public:
233  static char ID;
234
235  BasicAAWrapperPass();
236
237  BasicAAResult &getResult() { return *Result; }
238  const BasicAAResult &getResult() const { return *Result; }
239
240  bool runOnFunction(Function &F) override;
241  void getAnalysisUsage(AnalysisUsage &AU) const override;
242};
243
244FunctionPass *createBasicAAWrapperPass();
245
246/// A helper for the legacy pass manager to create a \c BasicAAResult object
247/// populated to the best of our ability for a particular function when inside
248/// of a \c ModulePass or a \c CallGraphSCCPass.
249BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F);
250
251/// This class is a functor to be used in legacy module or SCC passes for
252/// computing AA results for a function. We store the results in fields so that
253/// they live long enough to be queried, but we re-use them each time.
254class LegacyAARGetter {
255  Pass &P;
256  Optional<BasicAAResult> BAR;
257  Optional<AAResults> AAR;
258
259public:
260  LegacyAARGetter(Pass &P) : P(P) {}
261  AAResults &operator()(Function &F) {
262    BAR.emplace(createLegacyPMBasicAAResult(P, F));
263    AAR.emplace(createLegacyPMAAResults(P, F, *BAR));
264    return *AAR;
265  }
266};
267
268} // end namespace llvm
269
270#endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H
271