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

6 commit comments

Comments
 (6)

hyperlyz commented on Aug 17, 2020

@hyperlyz
hyperlyz
on Aug 17, 2020

I am not familiar with the CFLSteensAA. Sorry, I want ask you one quesiton. Hope you give me some advice.

I want use CFLSteensAAResult to make interprocedural queries, but currently cannot support direct query.
How do I solve this problem? Thanks.
image

fhahn commented on Aug 17, 2020

@fhahn
fhahn
on Aug 17, 2020
Contributor

It looks like this is not supported by the current implementation and would require some extra work to support it.

hyperlyz commented on Aug 18, 2020

@hyperlyz
hyperlyz
on Aug 18, 2020

It looks like this is not supported by the current implementation and would require some extra work to support it.

I have consulted several information related to CFLSteensAA, from which I find that the current implementation supports interprocedural alias analysis.
Is my conclusion correct? Should I do some extra work to support interprocedural queries?
Do you have any idea to support it?
Thank you very much for your timely response.

gburgessiv commented on Aug 18, 2020

@gburgessiv
gburgessiv
on Aug 18, 2020
MemberAuthor

Thanks for the comment!

CFLSteens is interprocedural in a different way: it'll look into callees to figure out what what the callees are doing, rather than relying only on function attributes on the callee, as non-interprocedural AAs do. It does not support queries of Values that sit in different functions.

hyperlyz commented on Aug 19, 2020

@hyperlyz
hyperlyz
on Aug 19, 2020

Thanks for the comment!

CFLSteens is interprocedural in a different way: it'll look into callees to figure out what what the callees are doing, rather than relying only on function attributes on the callee, as non-interprocedural AAs do. It does not support queries of Values that sit in different functions.

SteensAA is a context-insensitive and flow-insensitive method, so CFLSteensAA may be a interprocedural AA. Do you have any idea to improve it?
Besides, CFLAndersAA's implementation on the query method does not have the assertion that "interprocedural queries not supported". Can I use it to solve the interprocedural problem?
LLVM have any directly available AAs for interprocedural queries?

Thanks you again for the timely response!

gburgessiv commented on Aug 19, 2020

@gburgessiv
gburgessiv
on Aug 19, 2020
MemberAuthor

Do you have any idea to improve it?

CFLAA hasn't been on my (or anyone's, probably) radar for years. I don't know of anywhere where LLVM would try to perform these queries; without a pressing use-case, I don't think adding any complexity to support interproc queries is an improvement in any real sense.

Can I use it to solve the interprocedural problem?

I don't think we ever intended CFLAnders to be used in this way. You can try, but I don't expect it to produce useful results out of the box.

LLVM have any directly available AAs for interprocedural queries?

I doubt it, since like said above, I don't think users of that kind of functionality exist in LLVM.

Please sign in to comment.