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
23namespace llvm {
24
25class AssumptionCache;
26class DataLayout;
27class DominatorTree;
28class Function;
29class GEPOperator;
30class PHINode;
31class SelectInst;
32class TargetLibraryInfo;
33class 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.
41class 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
50  DominatorTree *getDT(const AAQueryInfo &AAQI) const {
51    return AAQI.UseDominatorTree ? DT_ : nullptr;
52  }
53
54public:
55  BasicAAResult(const DataLayout &DL, const Function &F,
56                const TargetLibraryInfo &TLI, AssumptionCache &AC,
57                DominatorTree *DT = nullptr)
58      : DL(DL), F(F), TLI(TLI), AC(AC), DT_(DT) {}
59
60  BasicAAResult(const BasicAAResult &Arg)
61      : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
62        DT_(Arg.DT_) {}
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
100private:
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.
152class BasicAA : public AnalysisInfoMixin<BasicAA> {
153  friend AnalysisInfoMixin<BasicAA>;
154
155  static AnalysisKey Key;
156
157public:
158  using Result = BasicAAResult;
159
160  BasicAAResult run(Function &F, FunctionAnalysisManager &AM);
161};
162
163/// Legacy wrapper pass to provide the BasicAAResult object.
164class BasicAAWrapperPass : public FunctionPass {
165  std::unique_ptr<BasicAAResult> Result;
166
167  virtual void anchor();
168
169public:
170  static char ID;
171
172  BasicAAWrapperPass();
173
174  BasicAAResult &getResult() { return *Result; }
175  const BasicAAResult &getResult() const { return *Result; }
176
177  bool runOnFunction(Function &F) override;
178  void getAnalysisUsage(AnalysisUsage &AU) const override;
179};
180
181FunctionPass *createBasicAAWrapperPass();
182
183} // end namespace llvm
184
185#endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H
186