Add a CFL Alias Analysis implementation
authorHal Finkel <hfinkel@anl.gov>
Tue, 2 Sep 2014 21:43:13 +0000 (21:43 +0000)
committerHal Finkel <hfinkel@anl.gov>
Tue, 2 Sep 2014 21:43:13 +0000 (21:43 +0000)
commitbf301d5670dd2f014604d87267ea06436911cbf0
tree8b58f622fb786e07813ae1fc3313fe11312b7e65
parenta2e22cd4cdd8f3c3ff5c888c82d98b3836e97a3a
Add a CFL Alias Analysis implementation

This provides an implementation of CFL alias analysis (including some
supporting data structures). Currently, we don't have any extremely fancy
features, sans some interprocedural analysis (i.e. no field sensitivity, etc.),
and we do best sitting behind BasicAA + TBAA. In such a configuration, we take
~0.6-0.8% of total compile time, and give ~7-8% NoAlias responses to queries
TBAA and BasicAA couldn't answer when bootstrapping LLVM. In testing this on
other projects, we've seen up to 10.5% of queries dropped by BasicAA+TBAA
answered with NoAlias by this algorithm.

Patch by George Burgess IV (with minor modifications by me -- mostly adapting
some BasicAA tests), thanks!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@216970 91177308-0d34-0410-b5e6-96231b3b80d8
15 files changed:
include/llvm/Analysis/Passes.h
include/llvm/InitializePasses.h
include/llvm/LinkAllPasses.h
lib/Analysis/Analysis.cpp
lib/Analysis/CFLAliasAnalysis.cpp [new file with mode: 0644]
lib/Analysis/CMakeLists.txt
lib/Analysis/StratifiedSets.h [new file with mode: 0644]
test/Analysis/CFLAliasAnalysis/const-expr-gep.ll [new file with mode: 0644]
test/Analysis/CFLAliasAnalysis/constant-over-index.ll [new file with mode: 0644]
test/Analysis/CFLAliasAnalysis/empty.ll [new file with mode: 0644]
test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll [new file with mode: 0644]
test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll [new file with mode: 0644]
test/Analysis/CFLAliasAnalysis/must-and-partial.ll [new file with mode: 0644]
test/Analysis/CFLAliasAnalysis/phi-and-select.ll [new file with mode: 0644]
test/Analysis/CFLAliasAnalysis/simple.ll [new file with mode: 0644]