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:
- Include the necessary header files and use the
llvmnamespace:#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;
- Create a structure for our pass by inheriting the
ImmutablePassandAliasAnalysisclasses:namespace { struct EverythingMustAlias : public ImmutablePass, public AliasAnalysis { - Declare the data structures and constructor:
static char ID; EverythingMustAlias() : ImmutablePass(ID) {} initializeEverythingMustAliasPass(*PassRegistry::getPassRegistry());} - Implement the
getAdjustedAnalysisPointerfunction:void *getAdjustedAnalysisPointer(const void *ID) override { if (ID == &AliasAnalysis::ID) return (AliasAnalysis*)this; return this; } - Implement the
initializePassfunction to initialize the pass:bool doInitialization(Module &M) override { DL = &M.getDataLayout(); return true; } - Implement the
aliasfunction:void *getAdjustedAnalysisPointer(const void *ID) override { if (ID == &AliasAnalysis::ID) return (AliasAnalysis*)this; return this; } }; } - Register the pass:
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(); } - Compile the pass using the
cmakeormakecommand. - Execute the test code using the
.sofile 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.