Coverage Report

Created: 2017-10-03 07:32

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