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 PhiValues; |

35 | class Value; |

36 | |

37 | /// This is the AA result object for the basic, local, and stateless alias |

38 | /// analysis. It implements the AA query interface in an entirely stateless |

39 | /// manner. As one consequence, it is never invalidated due to IR changes. |

40 | /// While it does retain some storage, that is used as an optimization and not |

41 | /// to preserve information from query to query. However it does retain handles |

42 | /// to various other analyses and must be recomputed when those analyses are. |

43 | class BasicAAResult : public AAResultBase { |

44 | const DataLayout &DL; |

45 | const Function &F; |

46 | const TargetLibraryInfo &TLI; |

47 | AssumptionCache &AC; |

48 | DominatorTree *DT; |

49 | |

50 | public: |

51 | BasicAAResult(const DataLayout &DL, const Function &F, |

52 | const TargetLibraryInfo &TLI, AssumptionCache &AC, |

53 | DominatorTree *DT = nullptr) |

54 | : DL(DL), F(F), TLI(TLI), AC(AC), DT(DT) {} |

55 | |

56 | BasicAAResult(const BasicAAResult &Arg) |

57 | : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC), |

58 | DT(Arg.DT) {} |

59 | BasicAAResult(BasicAAResult &&Arg) |

60 | : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), |

61 | AC(Arg.AC), DT(Arg.DT) {} |

62 | |

63 | /// Handle invalidation events in the new pass manager. |

64 | bool invalidate(Function &Fn, const PreservedAnalyses &PA, |

65 | FunctionAnalysisManager::Invalidator &Inv); |

66 | |

67 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |

68 | AAQueryInfo &AAQI, const Instruction *CtxI); |

69 | |

70 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |

71 | AAQueryInfo &AAQI); |

72 | |

73 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |

74 | AAQueryInfo &AAQI); |

75 | |

76 | /// Returns a bitmask that should be unconditionally applied to the ModRef |

77 | /// info of a memory location. This allows us to eliminate Mod and/or Ref |

78 | /// from the ModRef info based on the knowledge that the memory location |

79 | /// points to constant and/or locally-invariant memory. |

80 | /// |

81 | /// If IgnoreLocals is true, then this method returns NoModRef for memory |

82 | /// that points to a local alloca. |

83 | ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, |

84 | bool IgnoreLocals = false); |

85 | |

86 | /// Get the location associated with a pointer argument of a callsite. |

87 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); |

88 | |

89 | /// Returns the behavior when calling the given call site. |

90 | MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI); |

91 | |

92 | /// Returns the behavior when calling the given function. For use when the |

93 | /// call site is not known. |

94 | MemoryEffects getMemoryEffects(const Function *Fn); |

95 | |

96 | private: |

97 | struct DecomposedGEP; |

98 | |

99 | /// Tracks instructions visited by pointsToConstantMemory. |

100 | SmallPtrSet<const Value *, 16> Visited; |

101 | |

102 | static DecomposedGEP |

103 | DecomposeGEPExpression(const Value *V, const DataLayout &DL, |

104 | AssumptionCache *AC, DominatorTree *DT); |

105 | |

106 | /// A Heuristic for aliasGEP that searches for a constant offset |

107 | /// between the variables. |

108 | /// |

109 | /// GetLinearExpression has some limitations, as generally zext(%x + 1) |

110 | /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression |

111 | /// will therefore conservatively refuse to decompose these expressions. |

112 | /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if |

113 | /// the addition overflows. |

114 | bool constantOffsetHeuristic(const DecomposedGEP &GEP, LocationSize V1Size, |

115 | LocationSize V2Size, AssumptionCache *AC, |

116 | DominatorTree *DT, const AAQueryInfo &AAQI); |

117 | |

118 | bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2, |

119 | const AAQueryInfo &AAQI); |

120 | |

121 | void subtractDecomposedGEPs(DecomposedGEP &DestGEP, |

122 | const DecomposedGEP &SrcGEP, |

123 | const AAQueryInfo &AAQI); |

124 | |

125 | AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size, |

126 | const Value *V2, LocationSize V2Size, |

127 | const Value *UnderlyingV1, const Value *UnderlyingV2, |

128 | AAQueryInfo &AAQI); |

129 | |

130 | AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize, |

131 | const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI); |

132 | |

133 | AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize, |

134 | const Value *V2, LocationSize V2Size, |

135 | AAQueryInfo &AAQI); |

136 | |

137 | AliasResult aliasCheck(const Value *V1, LocationSize V1Size, const Value *V2, |

138 | LocationSize V2Size, AAQueryInfo &AAQI, |

139 | const Instruction *CtxI); |

140 | |

141 | AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size, |

142 | const Value *V2, LocationSize V2Size, |

143 | AAQueryInfo &AAQI, const Value *O1, |

144 | const Value *O2); |

145 | }; |

146 | |

147 | /// Analysis pass providing a never-invalidated alias analysis result. |

148 | class BasicAA : public AnalysisInfoMixin<BasicAA> { |

149 | friend AnalysisInfoMixin<BasicAA>; |

150 | |

151 | static AnalysisKey Key; |

152 | |

153 | public: |

154 | using Result = BasicAAResult; |

155 | |

156 | BasicAAResult run(Function &F, FunctionAnalysisManager &AM); |

157 | }; |

158 | |

159 | /// Legacy wrapper pass to provide the BasicAAResult object. |

160 | class BasicAAWrapperPass : public FunctionPass { |

161 | std::unique_ptr<BasicAAResult> Result; |

162 | |

163 | virtual void anchor(); |

164 | |

165 | public: |

166 | static char ID; |

167 | |

168 | BasicAAWrapperPass(); |

169 | |

170 | BasicAAResult &getResult() { return *Result; } |

171 | const BasicAAResult &getResult() const { return *Result; } |

172 | |

173 | bool runOnFunction(Function &F) override; |

174 | void getAnalysisUsage(AnalysisUsage &AU) const override; |

175 | }; |

176 | |

177 | FunctionPass *createBasicAAWrapperPass(); |

178 | |

179 | /// A helper for the legacy pass manager to create a \c BasicAAResult object |

180 | /// populated to the best of our ability for a particular function when inside |

181 | /// of a \c ModulePass or a \c CallGraphSCCPass. |

182 | BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F); |

183 | |

184 | /// This class is a functor to be used in legacy module or SCC passes for |

185 | /// computing AA results for a function. We store the results in fields so that |

186 | /// they live long enough to be queried, but we re-use them each time. |

187 | class LegacyAARGetter { |

188 | Pass &P; |

189 | std::optional<BasicAAResult> BAR; |

190 | std::optional<AAResults> AAR; |

191 | |

192 | public: |

193 | LegacyAARGetter(Pass &P) : P(P) {} |

194 | AAResults &operator()(Function &F) { |

195 | BAR.emplace(args: createLegacyPMBasicAAResult(P, F)); |

196 | AAR.emplace(args: createLegacyPMAAResults(P, F, BAR&: *BAR)); |

197 | return *AAR; |

198 | } |

199 | }; |

200 | |

201 | } // end namespace llvm |

202 | |

203 | #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H |

204 |