Coverage Report

Created: 2018-11-13 17:19

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