alias analysis in backend

Hi,

I would like to implement alias analysis in my backend. I would like to for example get the result that two stack-accesses with different offsets (indexes), would return noAlias. However, I’m somewhat confused as there is no notion of offset for the Location object.

I would also like to call ScheduleDAGInstr::buildSchedGraph() with this AliasAnalysis and have MIsNeedsChainEdge() return false in this case.

What should I do? Adding a MemoryOperand to such an instruction seems right, but it doesn’t seem to fit quite. What Value would be referenced? BasicAliasAnalysis returns MustAlias for the same Value, e g ‘Stack’.

Should I implement a target AliasAnalysis, perhaps derived from BasicAliasAnalysis, and make it required for my pass that will be using it?

If not, could I make this work with BasicAliasAnalysis by adding the right memory operands?

Thanks,

Jonas Paulsson

From: "Jonas Paulsson" <jonas.paulsson@ericsson.com>
To: llvmdev@cs.uiuc.edu
Sent: Tuesday, April 16, 2013 11:24:36 AM
Subject: [LLVMdev] alias analysis in backend

Hi,

I would like to implement alias analysis in my backend. I would like
to for example get the result that two stack-accesses with different
offsets (indexes), would return noAlias. However, I’m somewhat
confused as there is no notion of offset for the Location object.

I would also like to call ScheduleDAGInstr::buildSchedGraph() with
this AliasAnalysis and have MIsNeedsChainEdge() return false in this
case.

What should I do? Adding a MemoryOperand to such an instruction seems
right, but it doesn’t seem to fit quite. What Value would be
referenced?

I think that they should have pseudo-source values, see: include/llvm/CodeGen/PseudoSourceValue.h

I was under the impression that different pseudo source values from different frame indices already have this no-alias property. If they don't, then this seems like a nice general improvement that would benefit all backends.

-Hal

Hi Hal,

Thanks. How about a symbol with two different immediate offsets - the Value* would be the same, right? I don't see how AliasAnalysis::Location would handle this... And BasicAliasAnalysis does

if (V1 == V2) return MustAlias;

, so I'm not sure how this would be done .. ?

/Jonas

From: "Jonas Paulsson" <jonas.paulsson@ericsson.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: llvmdev@cs.uiuc.edu
Sent: Wednesday, April 17, 2013 12:22:49 AM
Subject: RE: [LLVMdev] alias analysis in backend

Hi Hal,

Thanks. How about a symbol with two different immediate offsets - the
Value* would be the same, right? I don't see how
AliasAnalysis::Location would handle this... And BasicAliasAnalysis
does

if (V1 == V2) return MustAlias;

, so I'm not sure how this would be done .. ?

If you run with -enable-misched -enable-aa-sched-mi

then you'll get this logic from the end of MIsNeedChainEdge:

  // The following interface to AA is fashioned after DAGCombiner::isAlias
  // and operates with MachineMemOperand offset with some important
  // assumptions:
  // - LLVM fundamentally assumes flat address spaces.
  // - MachineOperand offset can *only* result from legalization and
  // cannot affect queries other than the trivial case of overlap
  // checking.
  // - These offsets never wrap and never step outside
  // of allocated objects.
  // - There should never be any negative offsets here.
  //
...

  int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset());
  int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() - MinOffset;
  int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() - MinOffset;

  AliasAnalysis::AliasResult AAResult = AA->alias(
  AliasAnalysis::Location(MMOa->getValue(), Overlapa,
                          MMOa->getTBAAInfo()),
  AliasAnalysis::Location(MMOb->getValue(), Overlapb,
                          MMOb->getTBAAInfo()));

  return (AAResult != AliasAnalysis::NoAlias);

-Hal

From: "Jonas Paulsson" <jonas.paulsson@ericsson.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: llvmdev@cs.uiuc.edu
Sent: Wednesday, April 17, 2013 12:22:49 AM
Subject: RE: [LLVMdev] alias analysis in backend

Hi Hal,

Thanks. How about a symbol with two different immediate offsets - the
Value* would be the same, right? I don't see how
AliasAnalysis::Location would handle this... And BasicAliasAnalysis
does

if (V1 == V2) return MustAlias;

, so I'm not sure how this would be done .. ?

If you run with -enable-misched -enable-aa-sched-mi

then you'll get this logic from the end of MIsNeedChainEdge:

// The following interface to AA is fashioned after DAGCombiner::isAlias
// and operates with MachineMemOperand offset with some important
// assumptions:
// - LLVM fundamentally assumes flat address spaces.
// - MachineOperand offset can *only* result from legalization and
// cannot affect queries other than the trivial case of overlap
// checking.
// - These offsets never wrap and never step outside
// of allocated objects.
// - There should never be any negative offsets here.
//
...

int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset());
int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() - MinOffset;
int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() - MinOffset;

AliasAnalysis::AliasResult AAResult = AA->alias(
AliasAnalysis::Location(MMOa->getValue(), Overlapa,
                         MMOa->getTBAAInfo()),
AliasAnalysis::Location(MMOb->getValue(), Overlapb,
                         MMOb->getTBAAInfo()));

return (AAResult != AliasAnalysis::NoAlias);

This conservatively compensates for loads/stores that were split into narrower accesses during lowering, so doesn't help Jonas.

The MachineMemOperand offset is used differently for FixedFrameIndices, but we don't currently special case it here to disambiguate them. The general problem is that we don't have a CodeGen-level alias analysis API yet. It looks like this particular case could be fixed with an easy patch though, unless I'm missing something.

-Andy

From: "Andrew Trick" <atrick@apple.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Jonas Paulsson" <jonas.paulsson@ericsson.com>, llvmdev@cs.uiuc.edu
Sent: Thursday, April 18, 2013 2:33:52 AM
Subject: Re: [LLVMdev] alias analysis in backend

>> From: "Jonas Paulsson" <jonas.paulsson@ericsson.com>
>> To: "Hal Finkel" <hfinkel@anl.gov>
>> Cc: llvmdev@cs.uiuc.edu
>> Sent: Wednesday, April 17, 2013 12:22:49 AM
>> Subject: RE: [LLVMdev] alias analysis in backend
>>
>> Hi Hal,
>>
>> Thanks. How about a symbol with two different immediate offsets -
>> the
>> Value* would be the same, right? I don't see how
>> AliasAnalysis::Location would handle this... And
>> BasicAliasAnalysis
>> does
>>
>> if (V1 == V2) return MustAlias;
>>
>> , so I'm not sure how this would be done .. ?
>
> If you run with -enable-misched -enable-aa-sched-mi
>
> then you'll get this logic from the end of MIsNeedChainEdge:
>
> // The following interface to AA is fashioned after
> DAGCombiner::isAlias
> // and operates with MachineMemOperand offset with some important
> // assumptions:
> // - LLVM fundamentally assumes flat address spaces.
> // - MachineOperand offset can *only* result from legalization
> and
> // cannot affect queries other than the trivial case of
> overlap
> // checking.
> // - These offsets never wrap and never step outside
> // of allocated objects.
> // - There should never be any negative offsets here.
> //
> ...
>
> int64_t MinOffset = std::min(MMOa->getOffset(),
> MMOb->getOffset());
> int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() -
> MinOffset;
> int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() -
> MinOffset;
>
> AliasAnalysis::AliasResult AAResult = AA->alias(
> AliasAnalysis::Location(MMOa->getValue(), Overlapa,
> MMOa->getTBAAInfo()),
> AliasAnalysis::Location(MMOb->getValue(), Overlapb,
> MMOb->getTBAAInfo()));
>
> return (AAResult != AliasAnalysis::NoAlias);

This conservatively compensates for loads/stores that were split into
narrower accesses during lowering, so doesn't help Jonas.

The MachineMemOperand offset is used differently for
FixedFrameIndices, but we don't currently special case it here to
disambiguate them.

Thanks, I did not understand that. I thought that each different stack slot had its own frame index, or does that only apply to callee-saved and spill slots?

-Hal

From: “Andrew Trick” <atrick@apple.com>
To: “Hal Finkel” <hfinkel@anl.gov>
Cc: “Jonas Paulsson” <jonas.paulsson@ericsson.com>, llvmdev@cs.uiuc.edu
Sent: Thursday, April 18, 2013 2:33:52 AM
Subject: Re: [LLVMdev] alias analysis in backend

From: “Jonas Paulsson” <jonas.paulsson@ericsson.com>
To: “Hal Finkel” <hfinkel@anl.gov>
Cc: llvmdev@cs.uiuc.edu
Sent: Wednesday, April 17, 2013 12:22:49 AM
Subject: RE: [LLVMdev] alias analysis in backend

Hi Hal,

Thanks. How about a symbol with two different immediate offsets -
the
Value* would be the same, right? I don’t see how
AliasAnalysis::Location would handle this… And
BasicAliasAnalysis
does

if (V1 == V2) return MustAlias;

, so I’m not sure how this would be done … ?

If you run with -enable-misched -enable-aa-sched-mi

then you’ll get this logic from the end of MIsNeedChainEdge:

// The following interface to AA is fashioned after
DAGCombiner::isAlias
// and operates with MachineMemOperand offset with some important
// assumptions:
// - LLVM fundamentally assumes flat address spaces.
// - MachineOperand offset can only result from legalization
and
// cannot affect queries other than the trivial case of
overlap
// checking.
// - These offsets never wrap and never step outside
// of allocated objects.
// - There should never be any negative offsets here.
//

int64_t MinOffset = std::min(MMOa->getOffset(),
MMOb->getOffset());
int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() -
MinOffset;
int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() -
MinOffset;

AliasAnalysis::AliasResult AAResult = AA->alias(
AliasAnalysis::Location(MMOa->getValue(), Overlapa,
MMOa->getTBAAInfo()),
AliasAnalysis::Location(MMOb->getValue(), Overlapb,
MMOb->getTBAAInfo()));

return (AAResult != AliasAnalysis::NoAlias);

This conservatively compensates for loads/stores that were split into
narrower accesses during lowering, so doesn’t help Jonas.

The MachineMemOperand offset is used differently for
FixedFrameIndices, but we don’t currently special case it here to
disambiguate them.

Thanks, I did not understand that. I thought that each different stack slot had its own frame index, or does that only apply to callee-saved and spill slots?

They certainly have their own index. I think the question is where we disambiguate those slots.

I know others have worked on the inverse of this problem (PR12205). Akira? They may remember the details.

I don’t normally see raw frame or stack indices since I’m scheduling before regalloc and PEI. Things from the stack are usually arguments or allocas, so they naturally have distinct values.

Jonas, it might help to post a test case and/or file a bug.

-Andy