/usr/include/llvm-3.9/llvm/Analysis/BasicAliasAnalysis.h is in llvm-3.9-dev 1:3.9.1-19ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 | //===- BasicAliasAnalysis.h - Stateless, local Alias Analysis ---*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
/// \file
/// This is the interface for LLVM's primary stateless and local alias analysis.
///
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_BASICALIASANALYSIS_H
#define LLVM_ANALYSIS_BASICALIASANALYSIS_H
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Support/ErrorHandling.h"
namespace llvm {
class AssumptionCache;
class DominatorTree;
class LoopInfo;
/// This is the AA result object for the basic, local, and stateless alias
/// analysis. It implements the AA query interface in an entirely stateless
/// manner. As one consequence, it is never invalidated. While it does retain
/// some storage, that is used as an optimization and not to preserve
/// information from query to query.
class BasicAAResult : public AAResultBase<BasicAAResult> {
friend AAResultBase<BasicAAResult>;
const DataLayout &DL;
const TargetLibraryInfo &TLI;
AssumptionCache &AC;
DominatorTree *DT;
LoopInfo *LI;
public:
BasicAAResult(const DataLayout &DL, const TargetLibraryInfo &TLI,
AssumptionCache &AC, DominatorTree *DT = nullptr,
LoopInfo *LI = nullptr)
: AAResultBase(), DL(DL), TLI(TLI), AC(AC), DT(DT), LI(LI) {}
BasicAAResult(const BasicAAResult &Arg)
: AAResultBase(Arg), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
LI(Arg.LI) {}
BasicAAResult(BasicAAResult &&Arg)
: AAResultBase(std::move(Arg)), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC),
DT(Arg.DT), LI(Arg.LI) {}
/// Handle invalidation events from the new pass manager.
///
/// By definition, this result is stateless and so remains valid.
bool invalidate(Function &, const PreservedAnalyses &) { return false; }
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
/// Chases pointers until we find a (constant global) or not.
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal);
/// Get the location associated with a pointer argument of a callsite.
ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
/// Returns the behavior when calling the given call site.
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
/// Returns the behavior when calling the given function. For use when the
/// call site is not known.
FunctionModRefBehavior getModRefBehavior(const Function *F);
private:
// A linear transformation of a Value; this class represents ZExt(SExt(V,
// SExtBits), ZExtBits) * Scale + Offset.
struct VariableGEPIndex {
// An opaque Value - we can't decompose this further.
const Value *V;
// We need to track what extensions we've done as we consider the same Value
// with different extensions as different variables in a GEP's linear
// expression;
// e.g.: if V == -1, then sext(x) != zext(x).
unsigned ZExtBits;
unsigned SExtBits;
int64_t Scale;
bool operator==(const VariableGEPIndex &Other) const {
return V == Other.V && ZExtBits == Other.ZExtBits &&
SExtBits == Other.SExtBits && Scale == Other.Scale;
}
bool operator!=(const VariableGEPIndex &Other) const {
return !operator==(Other);
}
};
// Represents the internal structure of a GEP, decomposed into a base pointer,
// constant offsets, and variable scaled indices.
struct DecomposedGEP {
// Base pointer of the GEP
const Value *Base;
// Total constant offset w.r.t the base from indexing into structs
int64_t StructOffset;
// Total constant offset w.r.t the base from indexing through
// pointers/arrays/vectors
int64_t OtherOffset;
// Scaled variable (non-constant) indices.
SmallVector<VariableGEPIndex, 4> VarIndices;
};
/// Track alias queries to guard against recursion.
typedef std::pair<MemoryLocation, MemoryLocation> LocPair;
typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
AliasCacheTy AliasCache;
/// Tracks phi nodes we have visited.
///
/// When interpret "Value" pointer equality as value equality we need to make
/// sure that the "Value" is not part of a cycle. Otherwise, two uses could
/// come from different "iterations" of a cycle and see different values for
/// the same "Value" pointer.
///
/// The following example shows the problem:
/// %p = phi(%alloca1, %addr2)
/// %l = load %ptr
/// %addr1 = gep, %alloca2, 0, %l
/// %addr2 = gep %alloca2, 0, (%l + 1)
/// alias(%p, %addr1) -> MayAlias !
/// store %l, ...
SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
/// Tracks instructions visited by pointsToConstantMemory.
SmallPtrSet<const Value *, 16> Visited;
static const Value *
GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset,
unsigned &ZExtBits, unsigned &SExtBits,
const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
DominatorTree *DT, bool &NSW, bool &NUW);
static bool DecomposeGEPExpression(const Value *V, DecomposedGEP &Decomposed,
const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT);
static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
uint64_t ObjectAccessSize);
/// \brief A Heuristic for aliasGEP that searches for a constant offset
/// between the variables.
///
/// GetLinearExpression has some limitations, as generally zext(%x + 1)
/// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
/// will therefore conservatively refuse to decompose these expressions.
/// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
/// the addition overflows.
bool
constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
uint64_t V1Size, uint64_t V2Size, int64_t BaseOffset,
AssumptionCache *AC, DominatorTree *DT);
bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
const SmallVectorImpl<VariableGEPIndex> &Src);
AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
const AAMDNodes &V1AAInfo, const Value *V2,
uint64_t V2Size, const AAMDNodes &V2AAInfo,
const Value *UnderlyingV1, const Value *UnderlyingV2);
AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
const AAMDNodes &PNAAInfo, const Value *V2,
uint64_t V2Size, const AAMDNodes &V2AAInfo);
AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
const AAMDNodes &SIAAInfo, const Value *V2,
uint64_t V2Size, const AAMDNodes &V2AAInfo);
AliasResult aliasCheck(const Value *V1, uint64_t V1Size, AAMDNodes V1AATag,
const Value *V2, uint64_t V2Size, AAMDNodes V2AATag);
};
/// Analysis pass providing a never-invalidated alias analysis result.
class BasicAA : public AnalysisInfoMixin<BasicAA> {
friend AnalysisInfoMixin<BasicAA>;
static char PassID;
public:
typedef BasicAAResult Result;
BasicAAResult run(Function &F, AnalysisManager<Function> &AM);
};
/// Legacy wrapper pass to provide the BasicAAResult object.
class BasicAAWrapperPass : public FunctionPass {
std::unique_ptr<BasicAAResult> Result;
virtual void anchor();
public:
static char ID;
BasicAAWrapperPass();
BasicAAResult &getResult() { return *Result; }
const BasicAAResult &getResult() const { return *Result; }
bool runOnFunction(Function &F) override;
void getAnalysisUsage(AnalysisUsage &AU) const override;
};
FunctionPass *createBasicAAWrapperPass();
/// A helper for the legacy pass manager to create a \c BasicAAResult object
/// populated to the best of our ability for a particular function when inside
/// of a \c ModulePass or a \c CallGraphSCCPass.
BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F);
}
#endif
|