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 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 (!isa<SCEVCouldNotCompute>(BA) &&
61  ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
62  (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
63  return AliasResult::NoAlias;
64 
65  // Folding the subtraction while preserving range information can be tricky
66  // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
67  // and try again to see if things fold better that way.
68 
69  // Compute the difference between the two pointers.
70  const SCEV *AB = SE.getMinusSCEV(AS, BS);
71 
72  // Test whether the difference is known to be great enough that memory of
73  // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
74  // are non-zero, which is special-cased above.
75  if (!isa<SCEVCouldNotCompute>(AB) &&
76  BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
77  (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
78  return AliasResult::NoAlias;
79  }
80 
81  // If ScalarEvolution can find an underlying object, form a new query.
82  // The correctness of this depends on ScalarEvolution not recognizing
83  // inttoptr and ptrtoint operators.
84  Value *AO = GetBaseValue(AS);
85  Value *BO = GetBaseValue(BS);
86  if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
87  if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
89  : LocA.Size,
90  AO ? AAMDNodes() : LocA.AATags),
91  MemoryLocation(BO ? BO : LocB.Ptr,
93  : LocB.Size,
94  BO ? AAMDNodes() : LocB.AATags),
95  AAQI) == AliasResult::NoAlias)
96  return AliasResult::NoAlias;
97 
98  // Forward the query to the next analysis.
99  return AAResultBase::alias(LocA, LocB, AAQI);
100 }
101 
102 /// Given an expression, try to find a base value.
103 ///
104 /// Returns null if none was found.
105 Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
106  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
107  // In an addrec, assume that the base will be in the start, rather
108  // than the step.
109  return GetBaseValue(AR->getStart());
110  } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
111  // If there's a pointer operand, it'll be sorted at the end of the list.
112  const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
113  if (Last->getType()->isPointerTy())
114  return GetBaseValue(Last);
115  } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
116  // This is a leaf node.
117  return U->getValue();
118  }
119  // No Identified object found.
120  return nullptr;
121 }
122 
125  // We don't care if this analysis itself is preserved, it has no state. But
126  // we need to check that the analyses it depends on have been.
127  return Inv.invalidate<ScalarEvolutionAnalysis>(Fn, PA);
128 }
129 
130 AnalysisKey SCEVAA::Key;
131 
134 }
135 
136 char SCEVAAWrapperPass::ID = 0;
138  "ScalarEvolution-based Alias Analysis", false, true)
141  "ScalarEvolution-based Alias Analysis", false, true)
142 
144  return new SCEVAAWrapperPass();
145 }
146 
149 }
150 
152  Result.reset(
153  new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
154  return false;
155 }
156 
158  AU.setPreservesAll();
160 }
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:2036
llvm
---------------------— PointerInfo ------------------------------------—
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:3949
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:779
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:684
llvm::APInt::ule
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1075
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
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:3939
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:147
llvm::SCEVAA::run
SCEVAAResult run(Function &F, FunctionAnalysisManager &AM)
Definition: ScalarEvolutionAliasAnalysis.cpp:132
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
aa
scev aa
Definition: ScalarEvolutionAliasAnalysis.cpp:140
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:375
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:369
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2066
llvm::MemoryLocation::UnknownSize
@ UnknownSize
Definition: MemoryLocation.h:214
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:666
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:4066
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:917
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:4199
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:530
llvm::createSCEVAAWrapperPass
FunctionPass * createSCEVAAWrapperPass()
Creates an instance of SCEVAAWrapperPass.
Definition: ScalarEvolutionAliasAnalysis.cpp:143
ScalarEvolutionAliasAnalysis.h
llvm::SCEVAAResult::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Definition: ScalarEvolutionAliasAnalysis.cpp:123
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:151
llvm::SCEVAddExpr
This node represents an addition of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:260
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:157
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1815
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:37