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