[LLVMdev] alias information on machine instructions

[Dan Gohman]

On Tue, Jul 24, 2007 at 10:09:11AM +0200, Florian Brandner wrote:
> Dan Gohman wrote:
>> I tried out your patch on x86 and it didn't appear to need any special changes.
>
> it might be needed to look at the addressing modes of a load/store to
> get the right offset. but i think it should work, if the lowering does
> not rewrite loads/stores into custom DAG nodes.

FWIW, I just tried a complex address example on x86 and it looks like it
does work.

define i32 @foo(i32* %base, i32 %i) {
  %a = getelementptr i32* %base, i32 %i
  %b = getelementptr i32* %a, i32 19
  %c = load i32* %b
  %d = add i32 %c, 1
  ret i32 %d
}

In -print-machineinstrs, this comes out as:

     %reg1027 = ADD32rm %reg1024, %reg1026, 4, %reg1025, 76 SV:1[b]

Initially I was thinking it might get a+76 instead of b, however I don't
think that's necessary, or even desirable for alias analysis.

>> For the [??], it looks like the IsFrameIndex isn't getting set for the first
>> instruction there.
>
> yes, this needs to be added for each target. for our target i've
> modified the loadRegFromStackSlot and storeRegToStackSlot methods to add
> information on the frame index:
>   BuildMI(MB, MBI, TII.get(STORE_REG_IMM)).addReg(framePointer)
>       .addFrameIndex(FrameIndex).addReg(SrcReg).addSVOp(FrameIndex);

I added this to the x86 target (in addFrameReference in
X86InstrBuilder.h), though it still misses some cases.

For example, loads of parameters from the stack are loads with NULL
SrcValues, and they have FrameIndex operands. When
SelectionDAG::getTargetSrcValue sees them, it currently just passes on the
NULL SrcValue; it doesn't notice the FrameIndex operand.

I think getTargetSrcValue needs to check if the address of a load or
store is a FrameIndexSDNode operand.

>> I'm curious why you added a new node kind, TargetSrcValue, instead of just
>> using the existing SRCVALUE.
>
> this is needed to ensure that the lowering pass does not rewrite them. i
> don't know if this is actually done, but anyway i wanted to be on the
> safe side.

Ok. I think it's safe. At a quick glance, I don't see any code that lowers
it, and SRCVALUE should never contribute directly to an instruction, so it
shouldn't need to be lowered.

>>
>>> +    else if (MRO.SrcValue && !MRO.SrcValue->getName().empty())
>>> +      OS << "[" << MRO.SrcValue->getName() << "]";
>>
>> This code should also print the SVOffset value.
>
> this was meant for debugging purpose only, but yes it would be helpful
> to print the offset.

Thanks. Debugging purposes are one of the reasons I'm interested in this :-).

And actually, I have several more specific requests for the code in
MachineInstr.cpp, now that I've looked at it a little more.

The SVOperand printing should be under 'if (getNumSVOperands() > 0)' so that
we don't see SV: printed for instructions that don't have any memory
operands. Don't print the value of getNumSVOperands() itself; it's easy to
see how many operands there are because they're all printed. And it'll
almost always just be 1. And lastly, please change the " SV:" to ", SV:" so
that it's consistent with the rest of the (comma-separated) operands.

> this leads to a question on how to query the alias analysis. when i have
> a look at the alias set tracker, it seems that only the value and the
> size of the type is relevant for the query. but when i look at the
> DAGCombiner an "overlap" is calculated from the type size, the offset
> and an other offset. how is this supposed to work?

It looks like that second offset being added into the size arguments in
DAGCominer's AliasAnalysis query is bogus, actually...

> the arguments of the "alias" function are named "V1Size" and "V2Size",
> so it would make sense to pass the size only?

It looks like you need to first extend the SVOperand struct to include the
size of the memory reference, because I don't think that can be easily
deduced otherwise.

Then your MachineInstr-level alias test can do something similar to what
DAGCombiner::isAlias does, minus the FindBaseOffset stuff.
 - If the bases are the same, the query can be answered by simply examining
   the offsets and sizes.
 - Otherwise, query the AliasAnalysis, using each reference's offset+size
   for its size argument. This is over-conservative, but the previous check
   should protect it in most cases.

Dan

-- 
Dan Gohman, Cray Inc.