Coverage Report

Created: 2018-07-19 03:59

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