LLVM  13.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 MemoryLocation &LocB, AAQueryInfo &AAQI) {
28  // If either of the memory references is empty, it doesn't matter what the
29  // pointer values are. This allows the code below to ignore this special
30  // case.
31  if (LocA.Size.isZero() || LocB.Size.isZero())
32  return AliasResult::NoAlias;
33 
34  // This is SCEVAAResult. Get the SCEVs!
35  const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
36  const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
37 
38  // If they evaluate to the same expression, it's a MustAlias.
39  if (AS == BS)
41 
42  // If something is known about the difference between the two addresses,
43  // see if it's enough to prove a NoAlias.
44  if (SE.getEffectiveSCEVType(AS->getType()) ==
45  SE.getEffectiveSCEVType(BS->getType())) {
46  unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
47  APInt ASizeInt(BitWidth, LocA.Size.hasValue()
48  ? LocA.Size.getValue()
50  APInt BSizeInt(BitWidth, LocB.Size.hasValue()
51  ? LocB.Size.getValue()
53 
54  // Compute the difference between the two pointers.
55  const SCEV *BA = SE.getMinusSCEV(BS, AS);
56 
57  // Test whether the difference is known to be great enough that memory of
58  // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
59  // are non-zero, which is special-cased above.
60  if (ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
61  (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
62  return AliasResult::NoAlias;
63 
64  // Folding the subtraction while preserving range information can be tricky
65  // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
66  // and try again to see if things fold better that way.
67 
68  // Compute the difference between the two pointers.
69  const SCEV *AB = SE.getMinusSCEV(AS, BS);
70 
71  // Test whether the difference is known to be great enough that memory of
72  // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
73  // are non-zero, which is special-cased above.
74  if (BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
75  (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
76  return AliasResult::NoAlias;
77  }
78 
79  // If ScalarEvolution can find an underlying object, form a new query.
80  // The correctness of this depends on ScalarEvolution not recognizing
81  // inttoptr and ptrtoint operators.
82  Value *AO = GetBaseValue(AS);
83  Value *BO = GetBaseValue(BS);
84  if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
85  if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
87  : LocA.Size,
88  AO ? AAMDNodes() : LocA.AATags),
89  MemoryLocation(BO ? BO : LocB.Ptr,
91  : LocB.Size,
92  BO ? AAMDNodes() : LocB.AATags),
93  AAQI) == AliasResult::NoAlias)
94  return AliasResult::NoAlias;
95 
96  // Forward the query to the next analysis.
97  return AAResultBase::alias(LocA, LocB, AAQI);
98 }
99 
100 /// Given an expression, try to find a base value.
101 ///
102 /// Returns null if none was found.
103 Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
104  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
105  // In an addrec, assume that the base will be in the start, rather
106  // than the step.
107  return GetBaseValue(AR->getStart());
108  } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
109  // If there's a pointer operand, it'll be sorted at the end of the list.
110  const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
111  if (Last->getType()->isPointerTy())
112  return GetBaseValue(Last);
113  } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
114  // This is a leaf node.
115  return U->getValue();
116  }
117  // No Identified object found.
118  return nullptr;
119 }
120 
123  // We don't care if this analysis itself is preserved, it has no state. But
124  // we need to check that the analyses it depends on have been.
125  return Inv.invalidate<ScalarEvolutionAnalysis>(Fn, PA);
126 }
127 
128 AnalysisKey SCEVAA::Key;
129 
132 }
133 
134 char SCEVAAWrapperPass::ID = 0;
136  "ScalarEvolution-based Alias Analysis", false, true)
139  "ScalarEvolution-based Alias Analysis", false, true)
140 
142  return new SCEVAAWrapperPass();
143 }
144 
147 }
148 
150  Result.reset(
151  new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
152  return false;
153 }
154 
156  AU.setPreservesAll();
158 }
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:2105
llvm
Definition: AllocatorList.h:23
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:3858
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:769
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:217
llvm::Function
Definition: Function.h:61
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:674
llvm::APInt::ule
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1243
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
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:3848
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:651
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:145
llvm::SCEVAA::run
SCEVAAResult run(Function &F, FunctionAnalysisManager &AM)
Definition: ScalarEvolutionAliasAnalysis.cpp:130
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
aa
scev aa
Definition: ScalarEvolutionAliasAnalysis.cpp:138
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:414
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:376
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
llvm::ConstantRange::getUnsignedMax
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:370
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2135
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:656
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:3975
llvm::AAResultBase::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:1164
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
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
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:876
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
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. Minus is represented in SCEV as A+B*-1.
Definition: ScalarEvolution.cpp:4076
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:352
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:527
llvm::createSCEVAAWrapperPass
FunctionPass * createSCEVAAWrapperPass()
Creates an instance of SCEVAAWrapperPass.
Definition: ScalarEvolutionAliasAnalysis.cpp:141
llvm::MemoryLocation::UnknownSize
@ UnknownSize
Definition: MemoryLocation.h:214
ScalarEvolutionAliasAnalysis.h
llvm::SCEVAAResult::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Definition: ScalarEvolutionAliasAnalysis.cpp:121
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:149
llvm::SCEVAddExpr
This node represents an addition of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:262
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:379
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:26
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:155
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1799
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38