[LLVMdev] Frame index arithmetic

Mark Muir mark.i.r.muir at gmail.com
Tue Jan 19 04:27:43 PST 2010

>> I'm trying something cunning/crazy with the stack - implementing it in a type of memory that can only be addressed via immediates.
>> I've got this mostly working. However, I came across a problem which I've been unable to work around: lowering the IR (even without any optimisations enabled) often requires the pattern:
>> 	i32 = FrameIndex <n>
>> It isn't appropriate to do this with the proposed stack memory - it doesn't make sense to move the address into a register, as it isn't possible to move that back to the domain of an immediate. So I conditionally disabled this instruction. But that leads to most programs failing to select the above pattern.
> Sounds like your load / store address selection routine isn't working like what you expected. 

Thanks for the reply. Unfortunately, this doesn't seem to be the problem.

I have the following definition for the frameIndex:

  def frameIndex : Operand<i32>,
    ComplexPattern<i32 /*valueType*/, 1 /*numOperands*/,
                   "SelectFrameIndex" /*selectFunction*/,
                   [frameindex] /*rootNodes*/> {
    let PrintMethod = "printFrameIndexOperand";
    let MIOperandInfo = (ops GPR);

And the following selection code:

  SelectFrameIndex(SDValue Op, SDValue N, SDValue& Address) {
    if (FrameIndexSDNode* FIN = dyn_cast<FrameIndexSDNode>(N)) {
      Address = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
      return true;
    return false;

In light of your comment, I tried extending this method to only allow cases where Op is ISD::LOAD or ISD::STORE. I found this made no difference to the behaviour. That was surprising, so I added code to print out each instruction seen by that method. And it turns out that all the operations were loads or stores anyway. So it must be later on that the conversion happens, which turns the operation into some form of indirect addressing.

To further explore the example I gave in my original email, I have an instruction matching the pattern:

  [(set GPR:$dst, (select GPR:$sel, immOrGPR:$a, immOrGPR:$b))]

The target-independent IR (as shown in the original message):

> define i32 @foo(i32 %cond, i32 %a, i32 %b) nounwind {
> entry:
>   %retval = alloca i32                            ; <i32*> [#uses=2]
>   %cond.addr = alloca i32                         ; <i32*> [#uses=2]
>   %a.addr = alloca i32                            ; <i32*> [#uses=2]
>   %b.addr = alloca i32                            ; <i32*> [#uses=2]
>   store i32 %cond, i32* %cond.addr
>   store i32 %a, i32* %a.addr
>   store i32 %b, i32* %b.addr
>   %tmp = load i32* %cond.addr                     ; <i32> [#uses=1]
>   %tobool = icmp ne i32 %tmp, 0                   ; <i1> [#uses=1]
>   %tmp1 = load i32* %a.addr                       ; <i32> [#uses=1]
>   %tmp2 = load i32* %b.addr                       ; <i32> [#uses=1]
>   %cond3 = select i1 %tobool, i32 %tmp1, i32 %tmp2 ; <i32> [#uses=1]

To me seems to be doing what I want - i.e. storing arguments 'a' and 'b' into local stack slots, then selecting between the values stored in those stack slots. This appears to be what is seen during selection - SelectFrameIndex(), as indicated above.

The normal debug output from the back-end shows that the target-independent IR gets lowered to a select between the addresses of the two argument stack slots, rather than their values. That's a nice optimisation in general, but isn't allowed here, hence leading to the:

  LLVM ERROR: Cannot yet select: 0x1811798: i32 = FrameIndex <3>

What transforms are performed during selection? I think this is where I should be looking, but I'm a bit lost.

Any help would be greatly appreciated.

- Mark

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100119/c3e5d2dd/attachment.html>

More information about the llvm-dev mailing list