1 //===- BasicAliasAnalysis.h - Stateless, local Alias Analysis ---*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 /// This is the interface for LLVM's primary stateless and local alias analysis.
10 ///
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ANALYSIS_BASICALIASANALYSIS_H
14 #define LLVM_ANALYSIS_BASICALIASANALYSIS_H
15 
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/Analysis/AliasAnalysis.h"
18 #include "llvm/IR/PassManager.h"
19 #include "llvm/Pass.h"
20 #include <memory>
21 #include <utility>
22 
23 namespace llvm {
24 
25 class AssumptionCache;
26 class DataLayout;
27 class DominatorTree;
28 class Function;
29 class GEPOperator;
30 class PHINode;
31 class SelectInst;
32 class TargetLibraryInfo;
33 class Value;
34 
35 /// This is the AA result object for the basic, local, and stateless alias
36 /// analysis. It implements the AA query interface in an entirely stateless
37 /// manner. As one consequence, it is never invalidated due to IR changes.
38 /// While it does retain some storage, that is used as an optimization and not
39 /// to preserve information from query to query. However it does retain handles
40 /// to various other analyses and must be recomputed when those analyses are.
41 class BasicAAResult : public AAResultBase {
42   const DataLayout &DL;
43   const Function &F;
44   const TargetLibraryInfo &TLI;
45   AssumptionCache &AC;
46   /// Use getDT() instead of accessing this member directly, in order to
47   /// respect the AAQI.UseDominatorTree option.
48   DominatorTree *DT_;
49 
getDT(const AAQueryInfo & AAQI)50   DominatorTree *getDT(const AAQueryInfo &AAQI) const {
51     return AAQI.UseDominatorTree ? DT_ : nullptr;
52   }
53 
54 public:
55   BasicAAResult(const DataLayout &DL, const Function &F,
56                 const TargetLibraryInfo &TLI, AssumptionCache &AC,
57                 DominatorTree *DT = nullptr)
DL(DL)58       : DL(DL), F(F), TLI(TLI), AC(AC), DT_(DT) {}
59 
BasicAAResult(const BasicAAResult & Arg)60   BasicAAResult(const BasicAAResult &Arg)
61       : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
62         DT_(Arg.DT_) {}
BasicAAResult(BasicAAResult && Arg)63   BasicAAResult(BasicAAResult &&Arg)
64       : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI),
65         AC(Arg.AC), DT_(Arg.DT_) {}
66 
67   /// Handle invalidation events in the new pass manager.
68   bool invalidate(Function &Fn, const PreservedAnalyses &PA,
69                   FunctionAnalysisManager::Invalidator &Inv);
70 
71   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
72                     AAQueryInfo &AAQI, const Instruction *CtxI);
73 
74   ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
75                            AAQueryInfo &AAQI);
76 
77   ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
78                            AAQueryInfo &AAQI);
79 
80   /// Returns a bitmask that should be unconditionally applied to the ModRef
81   /// info of a memory location. This allows us to eliminate Mod and/or Ref
82   /// from the ModRef info based on the knowledge that the memory location
83   /// points to constant and/or locally-invariant memory.
84   ///
85   /// If IgnoreLocals is true, then this method returns NoModRef for memory
86   /// that points to a local alloca.
87   ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI,
88                                bool IgnoreLocals = false);
89 
90   /// Get the location associated with a pointer argument of a callsite.
91   ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
92 
93   /// Returns the behavior when calling the given call site.
94   MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI);
95 
96   /// Returns the behavior when calling the given function. For use when the
97   /// call site is not known.
98   MemoryEffects getMemoryEffects(const Function *Fn);
99 
100 private:
101   struct DecomposedGEP;
102 
103   /// Tracks instructions visited by pointsToConstantMemory.
104   SmallPtrSet<const Value *, 16> Visited;
105 
106   static DecomposedGEP
107   DecomposeGEPExpression(const Value *V, const DataLayout &DL,
108                          AssumptionCache *AC, DominatorTree *DT);
109 
110   /// A Heuristic for aliasGEP that searches for a constant offset
111   /// between the variables.
112   ///
113   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
114   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
115   /// will therefore conservatively refuse to decompose these expressions.
116   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
117   /// the addition overflows.
118   bool constantOffsetHeuristic(const DecomposedGEP &GEP, LocationSize V1Size,
119                                LocationSize V2Size, AssumptionCache *AC,
120                                DominatorTree *DT, const AAQueryInfo &AAQI);
121 
122   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2,
123                                      const AAQueryInfo &AAQI);
124 
125   void subtractDecomposedGEPs(DecomposedGEP &DestGEP,
126                               const DecomposedGEP &SrcGEP,
127                               const AAQueryInfo &AAQI);
128 
129   AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
130                        const Value *V2, LocationSize V2Size,
131                        const Value *UnderlyingV1, const Value *UnderlyingV2,
132                        AAQueryInfo &AAQI);
133 
134   AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
135                        const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
136 
137   AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
138                           const Value *V2, LocationSize V2Size,
139                           AAQueryInfo &AAQI);
140 
141   AliasResult aliasCheck(const Value *V1, LocationSize V1Size, const Value *V2,
142                          LocationSize V2Size, AAQueryInfo &AAQI,
143                          const Instruction *CtxI);
144 
145   AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
146                                   const Value *V2, LocationSize V2Size,
147                                   AAQueryInfo &AAQI, const Value *O1,
148                                   const Value *O2);
149 };
150 
151 /// Analysis pass providing a never-invalidated alias analysis result.
152 class BasicAA : public AnalysisInfoMixin<BasicAA> {
153   friend AnalysisInfoMixin<BasicAA>;
154 
155   static AnalysisKey Key;
156 
157 public:
158   using Result = BasicAAResult;
159 
160   BasicAAResult run(Function &F, FunctionAnalysisManager &AM);
161 };
162 
163 /// Legacy wrapper pass to provide the BasicAAResult object.
164 class BasicAAWrapperPass : public FunctionPass {
165   std::unique_ptr<BasicAAResult> Result;
166 
167   virtual void anchor();
168 
169 public:
170   static char ID;
171 
172   BasicAAWrapperPass();
173 
getResult()174   BasicAAResult &getResult() { return *Result; }
getResult()175   const BasicAAResult &getResult() const { return *Result; }
176 
177   bool runOnFunction(Function &F) override;
178   void getAnalysisUsage(AnalysisUsage &AU) const override;
179 };
180 
181 FunctionPass *createBasicAAWrapperPass();
182 
183 } // end namespace llvm
184 
185 #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H
186