LLVM 20.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
25using 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 const Instruction *) {
39 // If either of the memory references is empty, it doesn't matter what the
40 // pointer values are. This allows the code below to ignore this special
41 // case.
42 if (LocA.Size.isZero() || LocB.Size.isZero())
44
45 // This is SCEVAAResult. Get the SCEVs!
46 const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
47 const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
48
49 // If they evaluate to the same expression, it's a MustAlias.
50 if (AS == BS)
52
53 // If something is known about the difference between the two addresses,
54 // see if it's enough to prove a NoAlias.
55 if (canComputePointerDiff(SE, AS, BS)) {
56 unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
57 APInt ASizeInt(BitWidth, LocA.Size.hasValue()
58 ? static_cast<uint64_t>(LocA.Size.getValue())
60 APInt BSizeInt(BitWidth, LocB.Size.hasValue()
61 ? static_cast<uint64_t>(LocB.Size.getValue())
63
64 // Firstly, try to convert the two pointers into ptrtoint expressions to
65 // handle two pointers with different pointer bases.
66 // Either both pointers are used with ptrtoint or neither, so we can't end
67 // up with a ptr + int mix.
68 const SCEV *AInt =
70 const SCEV *BInt =
72 if (!isa<SCEVCouldNotCompute>(AInt) && !isa<SCEVCouldNotCompute>(BInt)) {
73 AS = AInt;
74 BS = BInt;
75 }
76
77 // Compute the difference between the two pointers.
78 const SCEV *BA = SE.getMinusSCEV(BS, AS);
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>(BA) &&
84 ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
85 (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
87
88 // Folding the subtraction while preserving range information can be tricky
89 // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
90 // and try again to see if things fold better that way.
91
92 // Compute the difference between the two pointers.
93 const SCEV *AB = SE.getMinusSCEV(AS, BS);
94
95 // Test whether the difference is known to be great enough that memory of
96 // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
97 // are non-zero, which is special-cased above.
98 if (!isa<SCEVCouldNotCompute>(AB) &&
99 BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
100 (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
102 }
103
104 // If ScalarEvolution can find an underlying object, form a new query.
105 // The correctness of this depends on ScalarEvolution not recognizing
106 // inttoptr and ptrtoint operators.
107 Value *AO = GetBaseValue(AS);
108 Value *BO = GetBaseValue(BS);
109 if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
110 if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
112 : LocA.Size,
113 AO ? AAMDNodes() : LocA.AATags),
114 MemoryLocation(BO ? BO : LocB.Ptr,
116 : LocB.Size,
117 BO ? AAMDNodes() : LocB.AATags),
118 AAQI, nullptr) == AliasResult::NoAlias)
120
122}
123
124/// Given an expression, try to find a base value.
125///
126/// Returns null if none was found.
127Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
128 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
129 // In an addrec, assume that the base will be in the start, rather
130 // than the step.
131 return GetBaseValue(AR->getStart());
132 } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
133 // If there's a pointer operand, it'll be sorted at the end of the list.
134 const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
135 if (Last->getType()->isPointerTy())
136 return GetBaseValue(Last);
137 } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
138 // This is a leaf node.
139 return U->getValue();
140 }
141 // No Identified object found.
142 return nullptr;
143}
144
147 // We don't care if this analysis itself is preserved, it has no state. But
148 // we need to check that the analyses it depends on have been.
149 return Inv.invalidate<ScalarEvolutionAnalysis>(Fn, PA);
150}
151
152AnalysisKey SCEVAA::Key;
153
156}
157
158char SCEVAAWrapperPass::ID = 0;
160 "ScalarEvolution-based Alias Analysis", false, true)
164
166 return new SCEVAAWrapperPass();
167}
168
171}
172
174 Result.reset(
175 new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
176 return false;
177}
178
180 AU.setPreservesAll();
182}
basic Basic Alias true
block Block Frequency Analysis
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define F(x, y, z)
Definition: MD5.cpp:55
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:57
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
static bool canComputePointerDiff(ScalarEvolution &SE, const SCEV *A, const SCEV *B)
This is the interface for a SCEV-based alias analysis.
This class stores info we want to provide to or retain within an alias query.
Class for arbitrary precision integers.
Definition: APInt.h:78
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1128
The possible results of an alias query.
Definition: AliasAnalysis.h:77
@ MayAlias
The two locations may or may not alias.
Definition: AliasAnalysis.h:98
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:95
@ MustAlias
The two locations precisely alias each other.
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:292
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:310
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:310
bool hasValue() const
static constexpr LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
TypeSize getValue() const
bool isZero() const
Representation for a specific memory location.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
const Value * Ptr
The address of the start of the location.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
A simple alias analysis implementation that uses ScalarEvolution to answer queries.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI, const Instruction *CtxI)
Legacy wrapper pass to provide the SCEVAAResult object.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
SCEVAAResult run(Function &F, FunctionAnalysisManager &AM)
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
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.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
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...
bool instructionCouldExistWithOperands(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...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
FunctionPass * createSCEVAAWrapperPass()
Creates an instance of SCEVAAWrapperPass.
void initializeSCEVAAWrapperPassPass(PassRegistry &)
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:760
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:28