Getelementptr woes

[Vladimir_Prus]

Hello,
I'm having problems with the following LLVM instruction

  %tmp.0.i = call int (sbyte*, ...)*
        %printf( sbyte* getelementptr ([11 x sbyte]* %.str_1, long 0, ......

The first argument in function call,

    sbyte* getelementptr ([11 x sbyte]* %.str_1.....

appears to be ConstantExpression*, and my backend does not support
ConstantExpression yet.

I probable can implement that, and getelementptr instruction too, but I wonder
if I need to. Looking at X86 backend, I see it does some smart things, like
folding getelementptr into instruction which uses it, and using 'lea' asm
instruction to perform addressing.

On my target, neither of this is possible -- there's just no such fancy
addressing modes.

So I wonder if I can away by writing two passes which work on LLVM level.
The first pass would extract all ConstantExpr* operands from instructions and
move them into separate instructions. E.g. the example above would become:

  %tmp.1 = sbyte* getelementptr ([11 x sbyte]* %.str_1, ..........
  %tmp.0.i = call int (sbyte*, ...)*
        %printf(%tmp.1 , .........

The second pass would convert getelementptr into casts and pointer arithmetic.

As a result, my backend would not care about both ConstantExpr and getelement
ptr, both of which look scary. The biggest advantage is any target which does
not have fancy addressing modes can just use those two passes.

I've started to sketch such passes already, but would be intetested to know
what you think.

TIA,
Volodya

[clattner]

I'm having problems with the following LLVM instruction

  %tmp.0.i = call int (sbyte*, ...)*
        %printf( sbyte* getelementptr ([11 x sbyte]* %.str_1, long 0, ......

The first argument in function call,

    sbyte* getelementptr ([11 x sbyte]* %.str_1.....

appears to be ConstantExpression*, and my backend does not support
ConstantExpression yet.

Ok.

I probable can implement that, and getelementptr instruction too, but I
wonder if I need to. Looking at X86 backend, I see it does some smart
things, like folding getelementptr into instruction which uses it, and
using 'lea' asm instruction to perform addressing. On my target, neither
of this is possible -- there's just no such fancy addressing modes.

Sure. Regardless of whether you do fancy folding or not, you should still
handle constant expressions (see below). Constant expressions exist for a
couple of important reasons and they aren't too horrible to handle
correctly. Also, ConstantExprs come in several different variaties,
not just getelementptr ones.

So I wonder if I can away by writing two passes which work on LLVM level.
The first pass would extract all ConstantExpr* operands from instructions and
move them into separate instructions. E.g. the example above would become:

  %tmp.1 = sbyte* getelementptr ([11 x sbyte]* %.str_1, ..........
  %tmp.0.i = call int (sbyte*, ...)*
        %printf(%tmp.1 , .........

While this is feasible and possible, I really wouldn't recommend it. Take
a look at how the X86 backend handles this stuff. For shift instructions,
for example, we have:

void ISel::visitShiftInst(ShiftInst &I) {
  MachineBasicBlock::iterator IP = BB->end();
  emitShiftOperation(BB, IP, I.getOperand(0), I.getOperand(1),
                     I.getOpcode() == Instruction::Shl, I.getType(),
                     getReg(I));
}

Basically all of the code for emitting shift instructions is in the
emitShiftOperation which takes two Value* operands to shift and a virtual
register (the last operand) to set to the result of the shift.

Because of this pattern, emitShiftOperation is used by the constant
expression support routines (see copyConstantToRegister) to codegen shift
constant expressions as well as shift instructions themselves.

I don't think this is TOO completely horrible to support constant
expressions in general, though it can (and will be in the future)
certainly be improved.

The second pass would convert getelementptr into casts and pointer
arithmetic.

This is something else I would not recommend. The X86 "simple"
instruction selector is not really simple anymore, so it's not a good
model to follow for how to emit GEP instructions in a straight-forward
way. Try taking a look at the emitGEPOperation method (line 3211) of
revision 175 of X86/InstSelectSimple.cpp though. This version is from
before the various address optimizations were implemented. Here's a
direct link:
http://llvm.cs.uiuc.edu/cvsweb/cvsweb.cgi/llvm/lib/Target/X86/InstSelectSimple.cpp?rev=1.175

To expand out a getelementptr into code it basically just walks through
the indices turning them into the appropriate scale and add as
appropriate. It's quite a bit simpler and cleaner to just implement
support for this instead of hacking it into casts and pointer arithmetic.

Note that getelementptr has been generalized a bit since the code in r175.
We now support pointer and array indices of int/uint/long/ulong type,
where before we just supported long. Also, the type of the structure
index is uint, where before it was ubyte.

As a result, my backend would not care about both ConstantExpr and
getelement ptr, both of which look scary. The biggest advantage is any
target which does not have fancy addressing modes can just use those two
passes.

I think that is a much better idea to just implement direct support for
these. It will make your code generator more efficient and more
straight-foward. Future codegen improvements will make it *MUCH* less
painful to add support for these, so the two extra passes have limited
long-term potential.

Hopefully I can just dispell some of the scariness of constantexpr and
getelementptr. If you have any questions about the above, feel free to
ask of course.

-Chris

[Vladimir_Prus]

Chris Lattner wrote:

> So I wonder if I can away by writing two passes which work on LLVM level.
> The first pass would extract all ConstantExpr* operands from instructions
> and move them into separate instructions. E.g. the example above would
> become:
>
> %tmp.1 = sbyte* getelementptr ([11 x sbyte]* %.str_1, ..........
> %tmp.0.i = call int (sbyte*, ...)*
> %printf(%tmp.1 , .........

While this is feasible and possible, I really wouldn't recommend it. Take
a look at how the X86 backend handles this stuff. For shift instructions,
for example, we have:

void ISel::visitShiftInst(ShiftInst &I) {
  MachineBasicBlock::iterator IP = BB->end();
  emitShiftOperation(BB, IP, I.getOperand(0), I.getOperand(1),
                     I.getOpcode() == Instruction::Shl, I.getType(),
                     getReg(I));
}

Basically all of the code for emitting shift instructions is in the
emitShiftOperation which takes two Value* operands to shift and a virtual
register (the last operand) to set to the result of the shift.

Because of this pattern, emitShiftOperation is used by the constant
expression support routines (see copyConstantToRegister) to codegen shift
constant expressions as well as shift instructions themselves.

But I'd still have to write copyConstantToRegister for my backend, which is
code duplication. What I'm trying to avoid is making by backend a blatant
copy-paste.

I don't think this is TOO completely horrible to support constant
expressions in general, though it can (and will be in the future)
certainly be improved.

Ok, I've another idea. I wonder if it's possible to create
'BasicInstructionSelector'. It would have a bunch of pure virtual methods
like emitShiftOperation and
1. Visitors for each operations, written just like above
2. Handling for constant expressions.

So, individual backend would have to implement only emitShiftOperation and
other emit* methods.

> The second pass would convert getelementptr into casts and pointer
> arithmetic.

This is something else I would not recommend. The X86 "simple"
instruction selector is not really simple anymore, so it's not a good
model to follow for how to emit GEP instructions in a straight-forward
way. Try taking a look at the emitGEPOperation method (line 3211) of
revision 175 of X86/InstSelectSimple.cpp though. This version is from
before the various address optimizations were implemented. Here's a
direct link:
http://llvm.cs.uiuc.edu/cvsweb/cvsweb.cgi/llvm/lib/Target/X86/InstSelectSim
ple.cpp?rev=1.175

To expand out a getelementptr into code it basically just walks through
the indices turning them into the appropriate scale and add as
appropriate. It's quite a bit simpler and cleaner to just implement
support for this instead of hacking it into casts and pointer arithmetic.

Uhm... the code runs from line 2311 till line 2433 so I naturally don't want
to copy-paste it And the only target-specific parts are instruction
codes. There should be some way to abstract this.... gotta try further.

- Volodya

[clattner]

Chris Lattner wrote:
> Because of this pattern, emitShiftOperation is used by the constant
> expression support routines (see copyConstantToRegister) to codegen shift
> constant expressions as well as shift instructions themselves.

But I'd still have to write copyConstantToRegister for my backend, which is
code duplication. What I'm trying to avoid is making by backend a blatant
copy-paste.

I realize this. As you have noticed there are _several_ instances of
code duplication currently required in the instruction selectors. There
is a mid-term plan to fix this, but it's probably not going to happen for
a couple of months. If you'd like me to discuss my plans, I can certainly
do so.

If you really want to implement a ConstantExpr lowering pass, I guess
that's ok, and in-line with the other lowering passes we have. You're
right that the other code generators in progress would benefit from it as
well.

> I don't think this is TOO completely horrible to support constant
> expressions in general, though it can (and will be in the future)
> certainly be improved.

Ok, I've another idea. I wonder if it's possible to create
'BasicInstructionSelector'. It would have a bunch of pure virtual methods
like emitShiftOperation and
1. Visitors for each operations, written just like above
2. Handling for constant expressions.

So, individual backend would have to implement only emitShiftOperation and
other emit* methods.

Hrm, there is a flaw in your logic: you're assuming that the current form
of instruction selection is basically the right one and just needs to be
cleaned up. Unfortunately that is not the case. In the medium term we
want to move to an optimal pattern matching instruction selector and a
more structured lowering mechanism.

What we *want* is for the *instrinfo.td files to contain a code pattern
for each instruction and have the instruction selector autogenerated from
that. The idea is to make instruction selection just like the rest of the
back end: the user describes the *target*, not hooks for a particular
algorithm to call into.

If you're interested in working on the longer term stuff, please let me
know. This is clearly the right direction to go to, but we are a way from
it. OTOH, if you'd like to work on a "basic instruction selector" with
callbacks, that is also cool, but it may be obsoleted in a few months.

> > The second pass would convert getelementptr into casts and pointer
> > arithmetic.
> To expand out a getelementptr into code it basically just walks through
> the indices turning them into the appropriate scale and add as
> appropriate. It's quite a bit simpler and cleaner to just implement
> support for this instead of hacking it into casts and pointer arithmetic.
>
>

Uhm... the code runs from line 2311 till line 2433 so I naturally don't want
to copy-paste it And the only target-specific parts are instruction
codes. There should be some way to abstract this.... gotta try further.

Yes I agree. See above.

-Chris