Skip to content

Commit bfa401e

Browse files
gburgessivgburgessiv
committedJul 6, 2016
[CFLAA] Split into Anders+Steens analysis.
StratifiedSets (as implemented) is very fast, but its accuracy is also limited. If we take a more aggressive andersens-like approach, we can be way more accurate, but we'll also end up being slower. So, we've decided to split CFLAA into CFLSteensAA and CFLAndersAA. Long-term, we want to end up in a place where CFLSteens is queried first; if it can provide an answer, great (since queries are basically map lookups). Otherwise, we'll fall back to CFLAnders, BasicAA, etc. This patch splits everything out so we can try to do something like that when we get a reasonable CFLAnders implementation. Patch by Jia Chen. Differential Revision: http://reviews.llvm.org/D21910 llvm-svn: 274589
1 parent 69898e6 commit bfa401e

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

47 files changed

+367
-165
lines changed
 

‎llvm/include/llvm/Analysis/CFLAndersAliasAnalysis.h

+74
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
//=- CFLAndersAliasAnalysis.h - Unification-based Alias Analysis ---*- C++-*-=//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
/// \file
10+
/// This is the interface for LLVM's inclusion-based alias analysis
11+
/// implemented with CFL graph reachability.
12+
///
13+
//===----------------------------------------------------------------------===//
14+
15+
#ifndef LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H
16+
#define LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H
17+
18+
#include "llvm/Analysis/AliasAnalysis.h"
19+
#include "llvm/IR/Function.h"
20+
#include "llvm/Pass.h"
21+
22+
namespace llvm {
23+
24+
class CFLAndersAAResult : public AAResultBase<CFLAndersAAResult> {
25+
friend AAResultBase<CFLAndersAAResult>;
26+
27+
public:
28+
explicit CFLAndersAAResult();
29+
30+
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
31+
// Dummy implementation
32+
return AAResultBase::alias(LocA, LocB);
33+
}
34+
};
35+
36+
/// Analysis pass providing a never-invalidated alias analysis result.
37+
///
38+
/// FIXME: We really should refactor CFL to use the analysis more heavily, and
39+
/// in particular to leverage invalidation to trigger re-computation.
40+
class CFLAndersAA : public AnalysisInfoMixin<CFLAndersAA> {
41+
friend AnalysisInfoMixin<CFLAndersAA>;
42+
static char PassID;
43+
44+
public:
45+
typedef CFLAndersAAResult Result;
46+
47+
CFLAndersAAResult run(Function &F, AnalysisManager<Function> &AM);
48+
};
49+
50+
/// Legacy wrapper pass to provide the CFLAndersAAResult object.
51+
class CFLAndersAAWrapperPass : public ImmutablePass {
52+
std::unique_ptr<CFLAndersAAResult> Result;
53+
54+
public:
55+
static char ID;
56+
57+
CFLAndersAAWrapperPass();
58+
59+
CFLAndersAAResult &getResult() { return *Result; }
60+
const CFLAndersAAResult &getResult() const { return *Result; }
61+
62+
void initializePass() override;
63+
void getAnalysisUsage(AnalysisUsage &AU) const override;
64+
};
65+
66+
//===--------------------------------------------------------------------===//
67+
//
68+
// createCFLAndersAAWrapperPass - This pass implements a set-based approach to
69+
// alias analysis.
70+
//
71+
ImmutablePass *createCFLAndersAAWrapperPass();
72+
}
73+
74+
#endif

‎llvm/include/llvm/Analysis/CFLAliasAnalysis.h renamed to ‎llvm/include/llvm/Analysis/CFLSteensAliasAnalysis.h

+27-27
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
//===- CFLAliasAnalysis.h - CFL-Based Alias Analysis Interface ---*- C++ -*-==//
1+
//=- CFLSteensAliasAnalysis.h - Unification-based Alias Analysis ---*- C++-*-=//
22
//
33
// The LLVM Compiler Infrastructure
44
//
@@ -7,12 +7,13 @@
77
//
88
//===----------------------------------------------------------------------===//
99
/// \file
10-
/// This is the interface for LLVM's primary stateless and local alias analysis.
10+
/// This is the interface for LLVM's unification-based alias analysis
11+
/// implemented with CFL graph reachability.
1112
///
1213
//===----------------------------------------------------------------------===//
1314

14-
#ifndef LLVM_ANALYSIS_CFLALIASANALYSIS_H
15-
#define LLVM_ANALYSIS_CFLALIASANALYSIS_H
15+
#ifndef LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
16+
#define LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
1617

1718
#include "llvm/ADT/DenseMap.h"
1819
#include "llvm/ADT/None.h"
@@ -28,14 +29,14 @@ namespace llvm {
2829

2930
class TargetLibraryInfo;
3031

31-
class CFLAAResult : public AAResultBase<CFLAAResult> {
32-
friend AAResultBase<CFLAAResult>;
32+
class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
33+
friend AAResultBase<CFLSteensAAResult>;
3334
class FunctionInfo;
3435

3536
public:
36-
explicit CFLAAResult(const TargetLibraryInfo &);
37-
CFLAAResult(CFLAAResult &&Arg);
38-
~CFLAAResult();
37+
explicit CFLSteensAAResult(const TargetLibraryInfo &);
38+
CFLSteensAAResult(CFLSteensAAResult &&Arg);
39+
~CFLSteensAAResult();
3940

4041
/// Handle invalidation events from the new pass manager.
4142
///
@@ -59,10 +60,9 @@ class CFLAAResult : public AAResultBase<CFLAAResult> {
5960

6061
// Comparisons between global variables and other constants should be
6162
// handled by BasicAA.
62-
// TODO: ConstantExpr handling -- CFLAA may report NoAlias when comparing
63-
// a GlobalValue and ConstantExpr, but every query needs to have at least
64-
// one Value tied to a Function, and neither GlobalValues nor ConstantExprs
65-
// are.
63+
// CFLSteensAA may report NoAlias when comparing a GlobalValue and
64+
// ConstantExpr, but every query needs to have at least one Value tied to a
65+
// Function, and neither GlobalValues nor ConstantExprs are.
6666
if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
6767
return AAResultBase::alias(LocA, LocB);
6868

@@ -85,7 +85,7 @@ class CFLAAResult : public AAResultBase<CFLAAResult> {
8585

8686
private:
8787
struct FunctionHandle final : public CallbackVH {
88-
FunctionHandle(Function *Fn, CFLAAResult *Result)
88+
FunctionHandle(Function *Fn, CFLSteensAAResult *Result)
8989
: CallbackVH(Fn), Result(Result) {
9090
assert(Fn != nullptr);
9191
assert(Result != nullptr);
@@ -95,7 +95,7 @@ class CFLAAResult : public AAResultBase<CFLAAResult> {
9595
void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
9696

9797
private:
98-
CFLAAResult *Result;
98+
CFLSteensAAResult *Result;
9999

100100
void removeSelfFromCache() {
101101
assert(Result != nullptr);
@@ -122,38 +122,38 @@ class CFLAAResult : public AAResultBase<CFLAAResult> {
122122
///
123123
/// FIXME: We really should refactor CFL to use the analysis more heavily, and
124124
/// in particular to leverage invalidation to trigger re-computation of sets.
125-
class CFLAA : public AnalysisInfoMixin<CFLAA> {
126-
friend AnalysisInfoMixin<CFLAA>;
125+
class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
126+
friend AnalysisInfoMixin<CFLSteensAA>;
127127
static char PassID;
128128

129129
public:
130-
typedef CFLAAResult Result;
130+
typedef CFLSteensAAResult Result;
131131

132-
CFLAAResult run(Function &F, AnalysisManager<Function> &AM);
132+
CFLSteensAAResult run(Function &F, AnalysisManager<Function> &AM);
133133
};
134134

135-
/// Legacy wrapper pass to provide the CFLAAResult object.
136-
class CFLAAWrapperPass : public ImmutablePass {
137-
std::unique_ptr<CFLAAResult> Result;
135+
/// Legacy wrapper pass to provide the CFLSteensAAResult object.
136+
class CFLSteensAAWrapperPass : public ImmutablePass {
137+
std::unique_ptr<CFLSteensAAResult> Result;
138138

139139
public:
140140
static char ID;
141141

142-
CFLAAWrapperPass();
142+
CFLSteensAAWrapperPass();
143143

144-
CFLAAResult &getResult() { return *Result; }
145-
const CFLAAResult &getResult() const { return *Result; }
144+
CFLSteensAAResult &getResult() { return *Result; }
145+
const CFLSteensAAResult &getResult() const { return *Result; }
146146

147147
void initializePass() override;
148148
void getAnalysisUsage(AnalysisUsage &AU) const override;
149149
};
150150

151151
//===--------------------------------------------------------------------===//
152152
//
153-
// createCFLAAWrapperPass - This pass implements a set-based approach to
153+
// createCFLSteensAAWrapperPass - This pass implements a set-based approach to
154154
// alias analysis.
155155
//
156-
ImmutablePass *createCFLAAWrapperPass();
156+
ImmutablePass *createCFLSteensAAWrapperPass();
157157
}
158158

159159
#endif

0 commit comments

Comments
 (0)