LLVM  6.0.0svn
ScalarEvolutionAliasAnalysis.cpp
Go to the documentation of this file.
1 //===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===//
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 //
10 // This file defines the ScalarEvolutionAliasAnalysis pass, which implements a
11 // simple alias analysis implemented in terms of ScalarEvolution queries.
12 //
13 // This differs from traditional loop dependence analysis in that it tests
14 // for dependencies within a single iteration of a loop, rather than
15 // dependencies between different iterations.
16 //
17 // ScalarEvolution has a more complete understanding of pointer arithmetic
18 // than BasicAliasAnalysis' collection of ad-hoc analyses.
19 //
20 //===----------------------------------------------------------------------===//
21 
23 using namespace llvm;
24 
26  const MemoryLocation &LocB) {
27  // If either of the memory references is empty, it doesn't matter what the
28  // pointer values are. This allows the code below to ignore this special
29  // case.
30  if (LocA.Size == 0 || LocB.Size == 0)
31  return NoAlias;
32 
33  // This is SCEVAAResult. Get the SCEVs!
34  const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
35  const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
36 
37  // If they evaluate to the same expression, it's a MustAlias.
38  if (AS == BS)
39  return MustAlias;
40 
41  // If something is known about the difference between the two addresses,
42  // see if it's enough to prove a NoAlias.
43  if (SE.getEffectiveSCEVType(AS->getType()) ==
44  SE.getEffectiveSCEVType(BS->getType())) {
45  unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
46  APInt ASizeInt(BitWidth, LocA.Size);
47  APInt BSizeInt(BitWidth, LocB.Size);
48 
49  // Compute the difference between the two pointers.
50  const SCEV *BA = SE.getMinusSCEV(BS, AS);
51 
52  // Test whether the difference is known to be great enough that memory of
53  // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
54  // are non-zero, which is special-cased above.
55  if (ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
56  (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
57  return NoAlias;
58 
59  // Folding the subtraction while preserving range information can be tricky
60  // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
61  // and try again to see if things fold better that way.
62 
63  // Compute the difference between the two pointers.
64  const SCEV *AB = SE.getMinusSCEV(AS, BS);
65 
66  // Test whether the difference is known to be great enough that memory of
67  // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
68  // are non-zero, which is special-cased above.
69  if (BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
70  (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
71  return NoAlias;
72  }
73 
74  // If ScalarEvolution can find an underlying object, form a new query.
75  // The correctness of this depends on ScalarEvolution not recognizing
76  // inttoptr and ptrtoint operators.
77  Value *AO = GetBaseValue(AS);
78  Value *BO = GetBaseValue(BS);
79  if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
80  if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
81  AO ? +MemoryLocation::UnknownSize : LocA.Size,
82  AO ? AAMDNodes() : LocA.AATags),
83  MemoryLocation(BO ? BO : LocB.Ptr,
84  BO ? +MemoryLocation::UnknownSize : LocB.Size,
85  BO ? AAMDNodes() : LocB.AATags)) == NoAlias)
86  return NoAlias;
87 
88  // Forward the query to the next analysis.
89  return AAResultBase::alias(LocA, LocB);
90 }
91 
92 /// Given an expression, try to find a base value.
93 ///
94 /// Returns null if none was found.
95 Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
96  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
97  // In an addrec, assume that the base will be in the start, rather
98  // than the step.
99  return GetBaseValue(AR->getStart());
100  } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
101  // If there's a pointer operand, it'll be sorted at the end of the list.
102  const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
103  if (Last->getType()->isPointerTy())
104  return GetBaseValue(Last);
105  } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
106  // This is a leaf node.
107  return U->getValue();
108  }
109  // No Identified object found.
110  return nullptr;
111 }
112 
113 AnalysisKey SCEVAA::Key;
114 
117 }
118 
119 char SCEVAAWrapperPass::ID = 0;
121  "ScalarEvolution-based Alias Analysis", false, true)
124  "ScalarEvolution-based Alias Analysis", false, true)
125 
127  return new SCEVAAWrapperPass();
128 }
129 
132 }
133 
135  Result.reset(
136  new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
137  return false;
138 }
139 
141  AU.setPreservesAll();
143 }
The two locations precisely alias each other.
Definition: AliasAnalysis.h:91
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
scev ScalarEvolution based Alias Analysis
The main scalar evolution driver.
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
F(f)
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
This is the interface for a SCEV-based alias analysis.
A simple alias analysis implementation that uses ScalarEvolution to answer queries.
This node represents a polynomial recurrence on the trip count of the specified loop.
FunctionPass * createSCEVAAWrapperPass()
Creates an instance of SCEVAAWrapperPass.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:79
Represent the analysis usage information of a pass.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa", "ScalarEvolution-based Alias Analysis", false, true) INITIALIZE_PASS_END(SCEVAAWrapperPass
SCEVAAResult(ScalarEvolution &SE)
void initializeSCEVAAWrapperPassPass(PassRegistry &)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
const AMDGPUAS & AS
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
SCEVAAResult run(Function &F, FunctionAnalysisManager &AM)
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
Legacy wrapper pass to provide the SCEVAAResult object.
Type * getType() const
Return the LLVM type of this SCEV expression.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:642
Class for arbitrary precision integers.
Definition: APInt.h:69
This node represents an addition of some number of SCEVs.
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1202
void setPreservesAll()
Set by analyses that do not transform their input at all.
Analysis pass that exposes the ScalarEvolution for a function.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
Basic Alias true
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
This class represents an analyzed expression in the program.
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM Value Representation.
Definition: Value.h:73
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
A container for analyses that lazily runs them and caches their results.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
uint64_t Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known...