LLVM  15.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 
24 #include "llvm/InitializePasses.h"
25 using namespace llvm;
26 
28  const SCEV *A, const SCEV *B) {
29  if (SE.getEffectiveSCEVType(A->getType()) !=
30  SE.getEffectiveSCEVType(B->getType()))
31  return false;
32 
34 }
35 
37  const MemoryLocation &LocB, AAQueryInfo &AAQI) {
38  // If either of the memory references is empty, it doesn't matter what the
39  // pointer values are. This allows the code below to ignore this special
40  // case.
41  if (LocA.Size.isZero() || LocB.Size.isZero())
42  return AliasResult::NoAlias;
43 
44  // This is SCEVAAResult. Get the SCEVs!
45  const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
46  const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
47 
48  // If they evaluate to the same expression, it's a MustAlias.
49  if (AS == BS)
51 
52  // If something is known about the difference between the two addresses,
53  // see if it's enough to prove a NoAlias.
54  if (canComputePointerDiff(SE, AS, BS)) {
55  unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
56  APInt ASizeInt(BitWidth, LocA.Size.hasValue()
57  ? LocA.Size.getValue()
59  APInt BSizeInt(BitWidth, LocB.Size.hasValue()
60  ? LocB.Size.getValue()
62 
63  // Compute the difference between the two pointers.
64  const SCEV *BA = SE.getMinusSCEV(BS, AS);
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 (!isa<SCEVCouldNotCompute>(BA) &&
70  ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
71  (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
72  return AliasResult::NoAlias;
73 
74  // Folding the subtraction while preserving range information can be tricky
75  // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
76  // and try again to see if things fold better that way.
77 
78  // Compute the difference between the two pointers.
79  const SCEV *AB = SE.getMinusSCEV(AS, BS);
80 
81  // Test whether the difference is known to be great enough that memory of
82  // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
83  // are non-zero, which is special-cased above.
84  if (!isa<SCEVCouldNotCompute>(AB) &&
85  BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
86  (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
87  return AliasResult::NoAlias;
88  }
89 
90  // If ScalarEvolution can find an underlying object, form a new query.
91  // The correctness of this depends on ScalarEvolution not recognizing
92  // inttoptr and ptrtoint operators.
93  Value *AO = GetBaseValue(AS);
94  Value *BO = GetBaseValue(BS);
95  if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
96  if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
98  : LocA.Size,
99  AO ? AAMDNodes() : LocA.AATags),
100  MemoryLocation(BO ? BO : LocB.Ptr,
102  : LocB.Size,
103  BO ? AAMDNodes() : LocB.AATags),
104  AAQI) == AliasResult::NoAlias)
105  return AliasResult::NoAlias;
106 
107  // Forward the query to the next analysis.
108  return AAResultBase::alias(LocA, LocB, AAQI);
109 }
110 
111 /// Given an expression, try to find a base value.
112 ///
113 /// Returns null if none was found.
114 Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
115  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
116  // In an addrec, assume that the base will be in the start, rather
117  // than the step.
118  return GetBaseValue(AR->getStart());
119  } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
120  // If there's a pointer operand, it'll be sorted at the end of the list.
121  const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
122  if (Last->getType()->isPointerTy())
123  return GetBaseValue(Last);
124  } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
125  // This is a leaf node.
126  return U->getValue();
127  }
128  // No Identified object found.
129  return nullptr;
130 }
131 
134  // We don't care if this analysis itself is preserved, it has no state. But
135  // we need to check that the analyses it depends on have been.
136  return Inv.invalidate<ScalarEvolutionAnalysis>(Fn, PA);
137 }
138 
139 AnalysisKey SCEVAA::Key;
140 
143 }
144 
145 char SCEVAAWrapperPass::ID = 0;
147  "ScalarEvolution-based Alias Analysis", false, true)
150  "ScalarEvolution-based Alias Analysis", false, true)
151 
153  return new SCEVAAWrapperPass();
154 }
155 
158 }
159 
161  Result.reset(
162  new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
163  return false;
164 }
165 
167  AU.setPreservesAll();
169 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2125
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:4308
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:780
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:218
llvm::Function
Definition: Function.h:60
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:685
llvm::APInt::ule
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1100
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
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:4298
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:652
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:227
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:156
llvm::SCEVAA::run
SCEVAAResult run(Function &F, FunctionAnalysisManager &AM)
Definition: ScalarEvolutionAliasAnalysis.cpp:141
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
aa
scev aa
Definition: ScalarEvolutionAliasAnalysis.cpp:149
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:462
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:231
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::ConstantRange::getUnsignedMin
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:431
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LocationSize::getValue
uint64_t getValue() const
Definition: MemoryLocation.h:159
false
Definition: StackSlotColoring.cpp:141
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:425
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2155
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:667
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:4405
llvm::AAResultBase::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:1222
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::SCEVAAWrapperPass
Legacy wrapper pass to provide the SCEVAAResult object.
Definition: ScalarEvolutionAliasAnalysis.h:56
llvm::LocationSize::hasValue
bool hasValue() const
Definition: MemoryLocation.h:156
llvm::LocationSize::isZero
bool isZero() const
Definition: MemoryLocation.h:171
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:4323
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:69
llvm::ScalarEvolution::getUnsignedRange
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
Definition: ScalarEvolution.h:948
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:4513
canComputePointerDiff
static bool canComputePointerDiff(ScalarEvolution &SE, const SCEV *A, const SCEV *B)
Definition: ScalarEvolutionAliasAnalysis.cpp:27
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:60
llvm::LocationSize::beforeOrAfterPointer
constexpr static LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:130
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:152
ScalarEvolutionAliasAnalysis.h
llvm::SCEVAAResult::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Definition: ScalarEvolutionAliasAnalysis.cpp:132
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:160
ScalarEvolutionExpressions.h
llvm::SCEVAddExpr
This node represents an addition of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:257
llvm::MemoryLocation::UnknownSize
@ UnknownSize
Definition: MemoryLocation.h:215
llvm::SCEVAAResult
A simple alias analysis implementation that uses ScalarEvolution to answer queries.
Definition: ScalarEvolutionAliasAnalysis.h:27
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:392
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
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:36
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:166
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210