Alias analysis is a technique by which we get to know whether two pointers point to the same location—that is, whether the same location can be accessed in more ways than one. By getting the results of this analysis, you can decide about further optimizations, such as common subexpression elimination. There are different ways and algorithms to perform alias analysis. In this recipe, we will not deal with these algorithms, but we will see how LLVM provides the infrastructure to write your own alias analysis pass. In this recipe, we will write an alias analysis pass to see how to get started with writing such a pass. We will not make use of any specific algorithm, but will return the MustAlias
response in every case of the analysis.
Write the test code that will be the input for alias analysis. Here, we will take the testcode.c
file used in the previous recipe as the test code.
Make the necessary Makefile
changes, make changes to register the pass by adding entries for the pass in llvm/lib/Analysis/Analysis.cpp llvm/include/llvm/InitializePasses.h
, llvm/include/llvm/LinkAllPasses.h
, llvm/include/llvm/Analysis/Passes.h
and create a file in llvm_source_dir/lib/Analysis/ named EverythingMustAlias.cpp
that will contain the source code for our pass.
Do the following steps:
llvm
namespace:#include "llvm/Pass.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" using namespace llvm;
ImmutablePass
and AliasAnalysis
classes:namespace { struct EverythingMustAlias : public ImmutablePass, public AliasAnalysis {
static char ID; EverythingMustAlias() : ImmutablePass(ID) {} initializeEverythingMustAliasPass(*PassRegistry::getPassRegistry());}
getAdjustedAnalysisPointer
function:void *getAdjustedAnalysisPointer(const void *ID) override { if (ID == &AliasAnalysis::ID) return (AliasAnalysis*)this; return this; }
initializePass
function to initialize the pass:bool doInitialization(Module &M) override { DL = &M.getDataLayout(); return true; }
alias
function:void *getAdjustedAnalysisPointer(const void *ID) override { if (ID == &AliasAnalysis::ID) return (AliasAnalysis*)this; return this; } }; }
char EverythingMustAlias::ID = 0; INITIALIZE_AG_PASS(EverythingMustAlias, AliasAnalysis, "must-aa", "Everything Alias (always returns 'must' alias)", true, true, true) ImmutablePass *llvm::createEverythingMustAliasPass() { return new EverythingMustAlias(); }
cmake
or make
command..so
file that is formed after compiling the pass:$ opt -must-aa -aa-eval -disable-output testcode.bc ===== Alias Analysis Evaluator Report ===== 10 Total Alias Queries Performed 0 no alias responses (0.0%) 0 may alias responses (0.0%) 0 partial alias responses (0.0%) 10 must alias responses (100.0%) Alias Analysis Evaluator Pointer Alias Summary: 0%/0%/0%/100% Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!
The AliasAnalysis
class gives the interface that the various alias analysis implementations should support. It exports the AliasResult
and ModRefResult
enums, representing the results of the alias
and modref
query respectively.
The alias
method is used to check whether two memory objects are pointing to the same location or not. It takes two memory objects as the input and returns MustAlias
, PartialAlias
, MayAlias
, or NoAlias
as appropriate.
The getModRefInfo
method returns the information on whether the execution of an instruction can read or modify a memory location. The pass in the preceding example works by returning the value MustAlias
for every set of two pointers, as we have implemented it that way. Here, we have inherited the ImmutablePasses
class, which suits our pass, as it is a very basic pass. We have inherited the AliasAnalysis
pass, which provides the interface for our implementation.
The getAdjustedAnalysisPointer
function is used when a pass implements an analysis interface through multiple inheritance. If needed, it should override this to adjust the pointer as required for the specified pass information.
The initializePass
function is used to initialize the pass that contains the InitializeAliasAnalysis
method, which should contain the actual implementation of the alias analysis.
The getAnalysisUsage
method is used to declare any dependency on other passes by explicitly calling the AliasAnalysis::getAnalysisUsage
method.
The alias
method is used to determine whether two memory objects alias each other or not. It takes two memory objects as the input and returns the MustAlias
, PartialAlias
, MayAlias
, or NoAlias
responses as appropriate.
The code following the alias
method is meant for registering the pass. Finally, when we use this pass over the test code, we get 10 MustAlias
responses (100.0%
) as the result, as implemented in our pass.
For a more detailed insight into LLVM alias analysis, refer to http://llvm.org/docs/AliasAnalysis.html.
3.12.162.37