Using an alias analysis pass

Hello LLVMdev,

I’m using LLVM to do static analysis exclusively (without any code generation). To implement this analysis, I’m using multiple address spaces to disambiguate the purpose of the pointed memory. Since address spaces never alias in my model, I set on to implement an alias analysis pass that would exactly provide this information, as I’m seeing a couple of otherwise dead store that won’t go away. However, I’m struggling to get it to work.

Four years ago, Tobias Grosser implemented such a pass, so I based mine off his. And one year ago, Matthew O’Connor ran into a similar issue, and I tried to use the solution that worked for him. The result code is this:

namespace
{
struct AddressSpaceAliasAnalysis : public FunctionPass, public AliasAnalysis
{
static char ID;
AddressSpaceAliasAnalysis() : FunctionPass(ID) {
}

virtual bool runOnFunction(Function& f) override
{
InitializeAliasAnalysis(this, &f.getParent()->getDataLayout());
return false;
}

virtual void getAnalysisUsage(AnalysisUsage &AU) const override
{
AliasAnalysis::getAnalysisUsage(AU);
}

virtual AliasResult alias(const Location &LocA, const Location &LocB) override
{
const Value *V1 = LocA.Ptr;
const Value *V2 = LocB.Ptr;

const PointerType *PT1 = dyn_cast(V1->getType());
const PointerType *PT2 = dyn_cast(V2->getType());

// The logic here is very simple: pointers to two different address spaces
// cannot alias.
if (PT1 != nullptr && PT2 != nullptr)
{
if (PT1->getAddressSpace() != PT2->getAddressSpace())
{
return NoAlias;
}
}

return AliasAnalysis::alias(LocA, LocB);
}

virtual void getAdjustedAnalysisPointer(AnalysisID PI) override
{
if (PI == &AliasAnalysis::ID)
return (AliasAnalysis
)this;
return this;
}
};
}

// Register this pass…
char AddressSpaceAliasAnalysis::ID = 0;

static RegisterPass aasa(“asaa”, “NoAlias for pointers in different address spaces”, false, true);
static RegisterAnalysisGroup aag(aasa);

FunctionPass* createAddressSpaceAliasAnalysisPass() {
return new AddressSpaceAliasAnalysis();
}

I made it a FunctionPass instead of an ImmutablePass because InitializeAliasAnalysis now needs a DataLayout argument, and I wasn’t sure how to get that one from an ImmutablePass.

The problem: I can add the pass to a legacy::PassManager object, and the runOnFunction method is called, but alias never is, and neither is getAdjustedAnalysisPointer.

I use a PassManagerBuilder object to populate a legacy::PassManager, which I then run on my module. I tried two different approaches to insert my AA pass.

The first was to add the AA pass before calling populateModulePassManager, since the AA passes are the first ones to be added, and this would put mine first. This didn’t help: runOnFunction was called, but alias never was. Additionally, now that I moved from INITIALIZE_AG_PASS to RegisterPass<T>, trying this causes an assert to trigger with the message “No default implementation found for analysis group!”

The second was to use the EP_ModuleOptimizerEarly extension point, since it is called right after the other AA passes are added. This makes my pass the last AA pass to be added. Same result: runOnFunction was called, but alias never was.

So what am I missing? How can I use my alias analysis pass?

Félix

Hello LLVMdev,

I’m using LLVM to do static analysis exclusively (without any code
generation). To implement this analysis, I’m using multiple address spaces
to disambiguate the purpose of the pointed memory. Since address spaces
never alias in my model, I set on to implement an alias analysis pass that
would exactly provide this information, as I’m seeing a couple of otherwise
dead store that won’t go away. However, I’m struggling to get it to work.

Four years ago, Tobias Grosser implemented such a pass, so I based mine off
his. And one year ago, Matthew O’Connor ran into a similar issue, and I
tried to use the solution that worked for him. The result code is this:

namespace
{
struct AddressSpaceAliasAnalysis : public FunctionPass, public AliasAnalysis
{
static char ID;
AddressSpaceAliasAnalysis() : FunctionPass(ID) {
}

virtual bool runOnFunction(Function& f) override
{
InitializeAliasAnalysis(this, &f.getParent()->getDataLayout());
return false;
}

virtual void getAnalysisUsage(AnalysisUsage &AU) const override
{
AliasAnalysis::getAnalysisUsage(AU);
}

virtual AliasResult alias(const Location &LocA, const Location &LocB)
override
{
const Value *V1 = LocA.Ptr;
const Value *V2 = LocB.Ptr;

const PointerType *PT1 = dyn_cast<const PointerType>(V1->getType());
const PointerType *PT2 = dyn_cast<const PointerType>(V2->getType());

// The logic here is very simple: pointers to two different address spaces
// cannot alias.
if (PT1 != nullptr && PT2 != nullptr)
{
if (PT1->getAddressSpace() != PT2->getAddressSpace())
{
return NoAlias;
}
}

return AliasAnalysis::alias(LocA, LocB);
}

virtual void *getAdjustedAnalysisPointer(AnalysisID PI) override
{
if (PI == &AliasAnalysis::ID)
return (AliasAnalysis*)this;
return this;
}
};
}

// Register this pass...
char AddressSpaceAliasAnalysis::ID = 0;

static RegisterPass<AddressSpaceAliasAnalysis> aasa("asaa", "NoAlias for
pointers in different address spaces", false, true);
static RegisterAnalysisGroup<AliasAnalysis> aag(aasa);

FunctionPass* createAddressSpaceAliasAnalysisPass() {
return new AddressSpaceAliasAnalysis();
}

I made it a FunctionPass instead of an ImmutablePass because
InitializeAliasAnalysis now needs a DataLayout argument, and I wasn’t sure
how to get that one from an ImmutablePass.

See CFLAliasAnalysis.cpp. You can get the datalayout from
doInitialization from the module.

The problem: I can add the pass to a `legacy::PassManager` object, and the
`runOnFunction` method is called, but `alias` never is, and neither is
`getAdjustedAnalysisPointer`.

I use a `PassManagerBuilder` object to populate a `legacy::PassManager`,
which I then run on my module. I tried two different approaches to insert my
AA pass.

The first was to add the AA pass before calling `populateModulePassManager`,
since the AA passes are the first ones to be added, and this would put mine
first. This didn’t help: `runOnFunction` was called, but `alias` never was.

Okay, so without seeing what passes you are adding, i can't say why
alias was never called.

You need to ensure you are adding the pass in the right order.
The first pass added to AA is the last pass queried (IE it's reverse order)

Search the codebase for UseCFLAA

I made it a FunctionPass instead of an ImmutablePass because
InitializeAliasAnalysis now needs a DataLayout argument, and I wasn’t sure
how to get that one from an ImmutablePass.

See CFLAliasAnalysis.cpp. You can get the datalayout from
doInitialization from the module.

This is also what NoAA does, but given that it’s a bit special, I wasn’t sure if it was desirable.

I returned to that, and with the RegisterPass change, this appears to work as expected, so problem solved?

The first was to add the AA pass before calling populateModulePassManager,
since the AA passes are the first ones to be added, and this would put mine
first. This didn’t help: runOnFunction was called, but alias never was.

Okay, so without seeing what passes you are adding, i can’t say why
alias was never called.

You need to ensure you are adding the pass in the right order.
The first pass added to AA is the last pass queried (IE it’s reverse order)

I figured that the last pass added has precedence a the comment that says that TBAA is added before Basic AA so that Basic AA wins in case of a disagreement, but since that it didn’t work, I tried the other way too.

For future reference, PassManagerBuilder creates the following AA passes:

if ([UseCFLAA](http://llvm.org/docs/doxygen/html/PassManagerBuilder_8cpp.html#a4e59132007f4c97b2a808df5fedf9584))
  PM.[add](http://llvm.org/docs/doxygen/html/classllvm_1_1legacy_1_1PassManagerBase.html#a2ce2eacfa52640d3a2feb2d46d561b85)([createCFLAliasAnalysisPass](http://llvm.org/docs/doxygen/html/namespacellvm.html#aa497e235b2414fe9e942c308aa6edcb6)());
PM.[add](http://llvm.org/docs/doxygen/html/classllvm_1_1legacy_1_1PassManagerBase.html#a2ce2eacfa52640d3a2feb2d46d561b85)([createTypeBasedAliasAnalysisPass](http://llvm.org/docs/doxygen/html/namespacellvm.html#a022323238327ae5edae5d42398e0325f)());
PM.[add](http://llvm.org/docs/doxygen/html/classllvm_1_1legacy_1_1PassManagerBase.html#a2ce2eacfa52640d3a2feb2d46d561b85)([createScopedNoAliasAAPass](http://llvm.org/docs/doxygen/html/namespacellvm.html#ad81266aaa6ff7606ad771dc5e451592b)());
PM.[add](http://llvm.org/docs/doxygen/html/classllvm_1_1legacy_1_1PassManagerBase.html#a2ce2eacfa52640d3a2feb2d46d561b85)([createBasicAliasAnalysisPass](http://llvm.org/docs/doxygen/html/namespacellvm.html#ab81115c38e816dea4cb563ca24faed96)());

Thanks for your help.

Félix