LLVM 19.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 // Compute the difference between the two pointers.
65 const SCEV *BA = SE.getMinusSCEV(BS, AS);
66
67 // Test whether the difference is known to be great enough that memory of
68 // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
69 // are non-zero, which is special-cased above.
70 if (!isa<SCEVCouldNotCompute>(BA) &&
71 ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
72 (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
74
75 // Folding the subtraction while preserving range information can be tricky
76 // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
77 // and try again to see if things fold better that way.
78
79 // Compute the difference between the two pointers.
80 const SCEV *AB = SE.getMinusSCEV(AS, BS);
81
82 // Test whether the difference is known to be great enough that memory of
83 // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
84 // are non-zero, which is special-cased above.
85 if (!isa<SCEVCouldNotCompute>(AB) &&
86 BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
87 (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
89 }
90
91 // If ScalarEvolution can find an underlying object, form a new query.
92 // The correctness of this depends on ScalarEvolution not recognizing
93 // inttoptr and ptrtoint operators.
94 Value *AO = GetBaseValue(AS);
95 Value *BO = GetBaseValue(BS);
96 if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
97 if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
99 : LocA.Size,
100 AO ? AAMDNodes() : LocA.AATags),
101 MemoryLocation(BO ? BO : LocB.Ptr,
103 : LocB.Size,
104 BO ? AAMDNodes() : LocB.AATags),
105 AAQI, nullptr) == AliasResult::NoAlias)
107
109}
110
111/// Given an expression, try to find a base value.
112///
113/// Returns null if none was found.
114Value *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
139AnalysisKey SCEVAA::Key;
140
143}
144
145char SCEVAAWrapperPass::ID = 0;
147 "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}
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:59
#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:76
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1122
The possible results of an alias query.
Definition: AliasAnalysis.h:81
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
@ MustAlias
The two locations precisely alias each other.
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:387
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:405
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
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:311
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:109
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.
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:26