LLVM  14.0.0git
ScalarEvolutionAliasAnalysis.cpp
Go to the documentation of this file.
1 //===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the ScalarEvolutionAliasAnalysis pass, which implements a
10 // simple alias analysis implemented in terms of ScalarEvolution queries.
11 //
12 // This differs from traditional loop dependence analysis in that it tests
13 // for dependencies within a single iteration of a loop, rather than
14 // dependencies between different iterations.
15 //
16 // ScalarEvolution has a more complete understanding of pointer arithmetic
17 // than BasicAliasAnalysis' collection of ad-hoc analyses.
18 //
19 //===----------------------------------------------------------------------===//
20 
23 #include "llvm/InitializePasses.h"
24 using namespace llvm;
25 
27  const SCEV *A, const SCEV *B) {
28  if (SE.getEffectiveSCEVType(A->getType()) !=
29  SE.getEffectiveSCEVType(B->getType()))
30  return false;
31 
33 }
34 
36  const MemoryLocation &LocB, AAQueryInfo &AAQI) {
37  // If either of the memory references is empty, it doesn't matter what the
38  // pointer values are. This allows the code below to ignore this special
39  // case.
40  if (LocA.Size.isZero() || LocB.Size.isZero())
41  return AliasResult::NoAlias;
42 
43  // This is SCEVAAResult. Get the SCEVs!
44  const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
45  const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
46 
47  // If they evaluate to the same expression, it's a MustAlias.
48  if (AS == BS)
50 
51  // If something is known about the difference between the two addresses,
52  // see if it's enough to prove a NoAlias.
53  if (canComputePointerDiff(SE, AS, BS)) {
54  unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
55  APInt ASizeInt(BitWidth, LocA.Size.hasValue()
56  ? LocA.Size.getValue()
58  APInt BSizeInt(BitWidth, LocB.Size.hasValue()
59  ? LocB.Size.getValue()
61 
62  // Compute the difference between the two pointers.
63  const SCEV *BA = SE.getMinusSCEV(BS, AS);
64 
65  // Test whether the difference is known to be great enough that memory of
66  // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
67  // are non-zero, which is special-cased above.
68  if (!isa<SCEVCouldNotCompute>(BA) &&
69  ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
70  (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
71  return AliasResult::NoAlias;
72 
73  // Folding the subtraction while preserving range information can be tricky
74  // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
75  // and try again to see if things fold better that way.
76 
77  // Compute the difference between the two pointers.
78  const SCEV *AB = SE.getMinusSCEV(AS, BS);
79 
80  // Test whether the difference is known to be great enough that memory of
81  // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
82  // are non-zero, which is special-cased above.
83  if (!isa<SCEVCouldNotCompute>(AB) &&
84  BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
85  (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
86  return AliasResult::NoAlias;
87  }
88 
89  // If ScalarEvolution can find an underlying object, form a new query.
90  // The correctness of this depends on ScalarEvolution not recognizing
91  // inttoptr and ptrtoint operators.
92  Value *AO = GetBaseValue(AS);
93  Value *BO = GetBaseValue(BS);
94  if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
95  if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
97  : LocA.Size,
98  AO ? AAMDNodes() : LocA.AATags),
99  MemoryLocation(BO ? BO : LocB.Ptr,
101  : LocB.Size,
102  BO ? AAMDNodes() : LocB.AATags),
103  AAQI) == AliasResult::NoAlias)
104  return AliasResult::NoAlias;
105 
106  // Forward the query to the next analysis.
107  return AAResultBase::alias(LocA, LocB, AAQI);
108 }
109 
110 /// Given an expression, try to find a base value.
111 ///
112 /// Returns null if none was found.
113 Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
114  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
115  // In an addrec, assume that the base will be in the start, rather
116  // than the step.
117  return GetBaseValue(AR->getStart());
118  } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
119  // If there's a pointer operand, it'll be sorted at the end of the list.
120  const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
121  if (Last->getType()->isPointerTy())
122  return GetBaseValue(Last);
123  } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
124  // This is a leaf node.
125  return U->getValue();
126  }
127  // No Identified object found.
128  return nullptr;
129 }
130 
133  // We don't care if this analysis itself is preserved, it has no state. But
134  // we need to check that the analyses it depends on have been.
135  return Inv.invalidate<ScalarEvolutionAnalysis>(Fn, PA);
136 }
137 
138 AnalysisKey SCEVAA::Key;
139 
142 }
143 
144 char SCEVAAWrapperPass::ID = 0;
146  "ScalarEvolution-based Alias Analysis", false, true)
149  "ScalarEvolution-based Alias Analysis", false, true)
150 
152  return new SCEVAAWrapperPass();
153 }
154 
157 }
158 
160  Result.reset(
161  new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
162  return false;
163 }
164 
166  AU.setPreservesAll();
168 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2118
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
llvm::ScalarEvolution::getEffectiveSCEVType
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...
Definition: ScalarEvolution.cpp:4214
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:783
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:217
llvm::Function
Definition: Function.h:62
llvm::AnalysisManager::Invalidator::invalidate
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
Definition: PassManager.h:688
llvm::APInt::ule
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1083
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
llvm::ScalarEvolution::getTypeSizeInBits
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
Definition: ScalarEvolution.cpp:4204
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:651
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1886
ScalarEvolution.h
llvm::MemoryLocation::Size
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
Definition: MemoryLocation.h:226
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa", "ScalarEvolution-based Alias Analysis", false, true) INITIALIZE_PASS_END(SCEVAAWrapperPass
llvm::SCEVAAWrapperPass::SCEVAAWrapperPass
SCEVAAWrapperPass()
Definition: ScalarEvolutionAliasAnalysis.cpp:155
llvm::SCEVAA::run
SCEVAAResult run(Function &F, FunctionAnalysisManager &AM)
Definition: ScalarEvolutionAliasAnalysis.cpp:140
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
aa
scev aa
Definition: ScalarEvolutionAliasAnalysis.cpp:148
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:458
llvm::MemoryLocation::AATags
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
Definition: MemoryLocation.h:230
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::ConstantRange::getUnsignedMin
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:413
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LocationSize::getValue
uint64_t getValue() const
Definition: MemoryLocation.h:158
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::ConstantRange::getUnsignedMax
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:407
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2148
llvm::MemoryLocation::UnknownSize
@ UnknownSize
Definition: MemoryLocation.h:214
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:670
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4339
llvm::AAResultBase::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:1218
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:77
llvm::SCEVAAWrapperPass
Legacy wrapper pass to provide the SCEVAAResult object.
Definition: ScalarEvolutionAliasAnalysis.h:55
llvm::LocationSize::hasValue
bool hasValue() const
Definition: MemoryLocation.h:155
llvm::LocationSize::isZero
bool isZero() const
Definition: MemoryLocation.h:170
llvm::ScalarEvolution::instructionCouldExistWitthOperands
bool instructionCouldExistWitthOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
Definition: ScalarEvolution.cpp:4229
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::ScalarEvolution::getUnsignedRange
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
Definition: ScalarEvolution.h:953
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::initializeSCEVAAWrapperPassPass
void initializeSCEVAAWrapperPassPass(PassRegistry &)
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
llvm::AliasResult::MustAlias
@ MustAlias
The two locations precisely alias each other.
Definition: AliasAnalysis.h:106
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::ScalarEvolution::getMinusSCEV
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
Definition: ScalarEvolution.cpp:4471
canComputePointerDiff
static bool canComputePointerDiff(ScalarEvolution &SE, const SCEV *A, const SCEV *B)
Definition: ScalarEvolutionAliasAnalysis.cpp:26
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::SCEVAAWrapperPass::ID
static char ID
Definition: ScalarEvolutionAliasAnalysis.h:59
llvm::LocationSize::beforeOrAfterPointer
constexpr static LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:129
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:342
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::SCEVUnknown
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
Definition: ScalarEvolutionExpressions.h:571
llvm::createSCEVAAWrapperPass
FunctionPass * createSCEVAAWrapperPass()
Creates an instance of SCEVAAWrapperPass.
Definition: ScalarEvolutionAliasAnalysis.cpp:151
ScalarEvolutionAliasAnalysis.h
llvm::SCEVAAResult::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Definition: ScalarEvolutionAliasAnalysis.cpp:131
llvm::SCEVAAWrapperPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: ScalarEvolutionAliasAnalysis.cpp:159
llvm::SCEVAddExpr
This node represents an addition of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:257
llvm::SCEVAAResult
A simple alias analysis implementation that uses ScalarEvolution to answer queries.
Definition: ScalarEvolutionAliasAnalysis.h:26
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:381
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::SCEVAAResult::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: ScalarEvolutionAliasAnalysis.cpp:35
llvm::SCEVAAWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: ScalarEvolutionAliasAnalysis.cpp:165
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38