1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
//===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the ScalarEvolutionAliasAnalysis pass, which implements a
// simple alias analysis implemented in terms of ScalarEvolution queries.
//
// ScalarEvolution has a more complete understanding of pointer arithmetic
// than BasicAliasAnalysis' collection of ad-hoc analyses.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Pass.h"
#include "llvm/Support/Compiler.h"
using namespace llvm;
namespace {
/// ScalarEvolutionAliasAnalysis - This is a simple alias analysis
/// implementation that uses ScalarEvolution to answer queries.
class VISIBILITY_HIDDEN ScalarEvolutionAliasAnalysis : public FunctionPass,
public AliasAnalysis {
ScalarEvolution *SE;
public:
static char ID; // Class identification, replacement for typeinfo
ScalarEvolutionAliasAnalysis() : FunctionPass(&ID), SE(0) {}
private:
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
virtual bool runOnFunction(Function &F);
virtual AliasResult alias(const Value *V1, unsigned V1Size,
const Value *V2, unsigned V2Size);
Value *GetUnderlyingIdentifiedObject(const SCEV *S);
};
} // End of anonymous namespace
// Register this pass...
char ScalarEvolutionAliasAnalysis::ID = 0;
static RegisterPass<ScalarEvolutionAliasAnalysis>
X("scev-aa", "ScalarEvolution-based Alias Analysis", false, true);
// Declare that we implement the AliasAnalysis interface
static RegisterAnalysisGroup<AliasAnalysis> Y(X);
FunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() {
return new ScalarEvolutionAliasAnalysis();
}
void
ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequiredTransitive<ScalarEvolution>();
AU.setPreservesAll();
AliasAnalysis::getAnalysisUsage(AU);
}
bool
ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) {
InitializeAliasAnalysis(this);
SE = &getAnalysis<ScalarEvolution>();
return false;
}
/// GetUnderlyingIdentifiedObject - Given an expression, try to find an
/// "identified object" (see AliasAnalysis::isIdentifiedObject) base
/// value. Return null is none was found.
Value *
ScalarEvolutionAliasAnalysis::GetUnderlyingIdentifiedObject(const SCEV *S) {
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
// In an addrec, assume that the base will be in the start, rather
// than the step.
return GetUnderlyingIdentifiedObject(AR->getStart());
} else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
// If there's a pointer operand, it'll be sorted at the end of the list.
const SCEV *Last = A->getOperand(A->getNumOperands()-1);
if (isa<PointerType>(Last->getType()))
return GetUnderlyingIdentifiedObject(Last);
} else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
// Determine if we've found an Identified object.
Value *V = U->getValue();
if (isIdentifiedObject(V))
return V;
}
// No Identified object found.
return 0;
}
AliasAnalysis::AliasResult
ScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize,
const Value *B, unsigned BSize) {
// This is ScalarEvolutionAliasAnalysis. Get the SCEVs!
const SCEV *AS = SE->getSCEV(const_cast<Value *>(A));
const SCEV *BS = SE->getSCEV(const_cast<Value *>(B));
// If they evaluate to the same expression, it's a MustAlias.
if (AS == BS) return MustAlias;
// If something is known about the difference between the two addresses,
// see if it's enough to prove a NoAlias.
if (SE->getEffectiveSCEVType(AS->getType()) ==
SE->getEffectiveSCEVType(BS->getType())) {
unsigned BitWidth = SE->getTypeSizeInBits(AS->getType());
APInt AI(BitWidth, ASize);
const SCEV *BA = SE->getMinusSCEV(BS, AS);
if (AI.ule(SE->getUnsignedRange(BA).getUnsignedMin())) {
APInt BI(BitWidth, BSize);
const SCEV *AB = SE->getMinusSCEV(AS, BS);
if (BI.ule(SE->getUnsignedRange(AB).getUnsignedMin()))
return NoAlias;
}
}
// If ScalarEvolution can find an underlying object, form a new query.
// The correctness of this depends on ScalarEvolution not recognizing
// inttoptr and ptrtoint operators.
Value *AO = GetUnderlyingIdentifiedObject(AS);
Value *BO = GetUnderlyingIdentifiedObject(BS);
if ((AO && AO != A) || (BO && BO != B))
if (alias(AO ? AO : A, AO ? ~0u : ASize,
BO ? BO : B, BO ? ~0u : BSize) == NoAlias)
return NoAlias;
// Forward the query to the next analysis.
return AliasAnalysis::alias(A, ASize, B, BSize);
}
|
