LLVM  9.0.0svn
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 
22 using namespace llvm;
23 
25  const MemoryLocation &LocB) {
26  // If either of the memory references is empty, it doesn't matter what the
27  // pointer values are. This allows the code below to ignore this special
28  // case.
29  if (LocA.Size.isZero() || LocB.Size.isZero())
30  return NoAlias;
31 
32  // This is SCEVAAResult. Get the SCEVs!
33  const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
34  const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
35 
36  // If they evaluate to the same expression, it's a MustAlias.
37  if (AS == BS)
38  return MustAlias;
39 
40  // If something is known about the difference between the two addresses,
41  // see if it's enough to prove a NoAlias.
42  if (SE.getEffectiveSCEVType(AS->getType()) ==
43  SE.getEffectiveSCEVType(BS->getType())) {
44  unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
45  APInt ASizeInt(BitWidth, LocA.Size.hasValue()
46  ? LocA.Size.getValue()
48  APInt BSizeInt(BitWidth, LocB.Size.hasValue()
49  ? LocB.Size.getValue()
51 
52  // Compute the difference between the two pointers.
53  const SCEV *BA = SE.getMinusSCEV(BS, AS);
54 
55  // Test whether the difference is known to be great enough that memory of
56  // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
57  // are non-zero, which is special-cased above.
58  if (ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
59  (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
60  return NoAlias;
61 
62  // Folding the subtraction while preserving range information can be tricky
63  // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
64  // and try again to see if things fold better that way.
65 
66  // Compute the difference between the two pointers.
67  const SCEV *AB = SE.getMinusSCEV(AS, BS);
68 
69  // Test whether the difference is known to be great enough that memory of
70  // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
71  // are non-zero, which is special-cased above.
72  if (BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
73  (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
74  return NoAlias;
75  }
76 
77  // If ScalarEvolution can find an underlying object, form a new query.
78  // The correctness of this depends on ScalarEvolution not recognizing
79  // inttoptr and ptrtoint operators.
80  Value *AO = GetBaseValue(AS);
81  Value *BO = GetBaseValue(BS);
82  if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
83  if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
84  AO ? LocationSize::unknown() : LocA.Size,
85  AO ? AAMDNodes() : LocA.AATags),
86  MemoryLocation(BO ? BO : LocB.Ptr,
87  BO ? LocationSize::unknown() : LocB.Size,
88  BO ? AAMDNodes() : LocB.AATags)) == NoAlias)
89  return NoAlias;
90 
91  // Forward the query to the next analysis.
92  return AAResultBase::alias(LocA, LocB);
93 }
94 
95 /// Given an expression, try to find a base value.
96 ///
97 /// Returns null if none was found.
98 Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
99  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
100  // In an addrec, assume that the base will be in the start, rather
101  // than the step.
102  return GetBaseValue(AR->getStart());
103  } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
104  // If there's a pointer operand, it'll be sorted at the end of the list.
105  const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
106  if (Last->getType()->isPointerTy())
107  return GetBaseValue(Last);
108  } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
109  // This is a leaf node.
110  return U->getValue();
111  }
112  // No Identified object found.
113  return nullptr;
114 }
115 
116 AnalysisKey SCEVAA::Key;
117 
120 }
121 
122 char SCEVAAWrapperPass::ID = 0;
124  "ScalarEvolution-based Alias Analysis", false, true)
127  "ScalarEvolution-based Alias Analysis", false, true)
128 
130  return new SCEVAAWrapperPass();
131 }
132 
135 }
136 
138  Result.reset(
139  new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
140  return false;
141 }
142 
144  AU.setPreservesAll();
146 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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...
static constexpr LocationSize unknown()
scev ScalarEvolution based Alias Analysis
The main scalar evolution driver.
The two locations do not alias at all.
Definition: AliasAnalysis.h:83
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
F(f)
block Block Frequency true
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
This is the interface for a SCEV-based alias analysis.
A simple alias analysis implementation that uses ScalarEvolution to answer queries.
This node represents a polynomial recurrence on the trip count of the specified loop.
FunctionPass * createSCEVAAWrapperPass()
Creates an instance of SCEVAAWrapperPass.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:77
uint64_t getValue() const
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:223
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Represent the analysis usage information of a pass.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa", "ScalarEvolution-based Alias Analysis", false, true) INITIALIZE_PASS_END(SCEVAAWrapperPass
SCEVAAResult(ScalarEvolution &SE)
void initializeSCEVAAWrapperPassPass(PassRegistry &)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known...
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.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
SCEVAAResult run(Function &F, FunctionAnalysisManager &AM)
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
The two locations precisely alias each other.
Definition: AliasAnalysis.h:89
Legacy wrapper pass to provide the SCEVAAResult object.
Type * getType() const
Return the LLVM type of this SCEV expression.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:643
Class for arbitrary precision integers.
Definition: APInt.h:69
This node represents an addition of some number of SCEVs.
void setPreservesAll()
Set by analyses that do not transform their input at all.
Analysis pass that exposes the ScalarEvolution for a function.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
This class represents an analyzed expression in the program.
bool isZero() const
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM Value Representation.
Definition: Value.h:72
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool hasValue() const
A container for analyses that lazily runs them and caches their results.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70