Structs as first class values.

Hi,

I'm trying to implement structs as first class values. If I assemble

; ModuleID = 't0022.s.bc'
target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
target triple = "i386-pc-linux-gnu"
         %struct.foo = type { i32, i32, i32 }

define %struct.foo @main() nounwind {
entry:
         %foo = alloca %struct.foo ; <%struct.foo*> [#uses=1]
         %"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0]
         br label %return

return: ; preds = %entry
         %t = load %struct.foo* %foo ; <%struct.foo> [#uses=1]
         ret %struct.foo %t
}

It assembles without complaint.

If I do llc I get an assert:

x86:
Return operand #2 has unhandled type i32
llc[0x8b5981e]
...

arm:
llc: /home/rich/llvm-trunk-new/lib/VMCore/ValueTypes.cpp:109: static llvm::MVT llvm::MVT::getMVT(const llvm::Type*, bool): Assertion `0 && "Unknown type!"' failed.
...

My questions are:

  Is this supposed to work? (I understand it may be a work in progress.)
  Is the LLVM well formed at the source level?

-Rich

Hi,

I'm trying to implement structs as first class values. If I assemble

It assembles without complaint.

Yep, the code looks fine.

If I do llc I get an assert:

My questions are:

Is this supposed to work? (I understand it may be a work in progress.)

Yes, that is supposed to work in theory. In practice, most targets only support returning up to two values in registers. Eventually, we want the code generator to support returning excess return values on the stack, but we don't have that code yet.

Is the LLVM well formed at the source level?

Yep, this is just a limitation of the current code generators. Prior to first-class aggregate support, we did have MRV support, which has the same limitation so far.

-Chris

Chris Lattner wrote:

I'm sure the implementation will take the same approach, but it won't necessarily be ABI compatible. I don't know enough to say at this point... it may end up being ABI compatible or not depending on implementation details.

-Chris

Chris Lattner wrote:

I'm sure the implementation will take the same approach, but it won't necessarily be ABI compatible. I don't know enough to say at this point... it may end up being ABI compatible or not depending on implementation details.

Hi Chris,

I was thinking about my problem and thought that there might be a good interim solution. I would like not to clutter my front end with stuff that will go away. How about a pass that runs before code generation that changes functions returning structs to void functions with the return pointer first parameter?

I've not written an LLVM pass (yet), and I'd I'd like to get my feet wet. Does this seem like a reasonable (temporary) solution to this problem?

-Rich

Hi Rich,

I was thinking about my problem and thought that there might be a good
interim solution. I would like not to clutter my front end with stuff
that will go away. How about a pass that runs before code generation
that changes functions returning structs to void functions with the
return pointer first parameter?

On this topic, you should look at the StructRetPromotion pass
(lib/Transforms/IPO/StructRetPromotion.cpp). This pass does exactly the
opposite of what you propose: It transforms return pointers in the first
parameter to first class returns.

This pass only operates on internal functions, though, so it does not have to
deal with ABI issues. If you want to support the C ABI (which requires a
pointer in the first argument to return any struct AFAIK), you might be better
off generating such code in your frontend. Any internal function can then be
simplified by the sretpromotion pass (perhaps it could be modified to take an
option for the maximum number of elements to put in the real return struct?)

Not sure how to go about this exactly, but perhaps this helps a bit.

Gr.

Matthijs

This is not the same on all architectures. For x86-64, for example, structs
are returned through the hidden first argument except if they are small
enough, in which case they are returned in registers.

I'm rather worried about Chris' statements regarding ABI compliance. This
is a very important issue for us and I would guess most commercial vendors.
We absolutely must be able to interoperate with third-party libraries.

Yes, we can implement the functionality ourselves but better that we have
one community-owned implementation than a bunch of private forks.

I'm hoping we can collectively discuss some of this at the dev meeting.

                                             -Dave

Matthijs Kooijman wrote:

On this topic, you should look at the StructRetPromotion pass
(lib/Transforms/IPO/StructRetPromotion.cpp). This pass does exactly the
opposite of what you propose: It transforms return pointers in the first
parameter to first class returns.

This pass only operates on internal functions, though, so it does not have to
deal with ABI issues. If you want to support the C ABI (which requires a
pointer in the first argument to return any struct AFAIK), you might be better
off generating such code in your frontend. Any internal function can then be
simplified by the sretpromotion pass (perhaps it could be modified to take an
option for the maximum number of elements to put in the real return struct?)

Hi Matthijs,

Thanks for the pointer. It was the first time I looked at an LLVM pass closely. Very nice and simple!

I think I will have my frontend pass the pointer. I can always back it out when return values are handled. Although it might be fun to try to implement a StructRetDemotion pass. :wink:

-Rich

David, I'm not sure I follow. It is, of course, very important for us that llvm-gcc generate ABI compliant code on x86-64. I'm just saying that if struct-return does not provide the ABI required for a specific source construct that another lowering would be needed.

In the case of X86-64, llvm-gcc does use aggregate return (for the interesting cases which return things in registers) and it does do the right thing. However, returning a {i64, i64, i64, i64} by value and having it automatically be returned "by pointer" is less interesting, as we already have a direct way to handle that (and llvm-gcc already produces it).

AFAIK, llvm-gcc/g++ does an *extremely* good job of matching the X86-64 ABI on mainline.

-Chris

David, I'm not sure I follow. It is, of course, very important for us
that llvm-gcc generate ABI compliant code on x86-64. I'm just saying
that if struct-return does not provide the ABI required for a specific
source construct that another lowering would be needed.

Ah, ok. I misunderstood your statement.

In the case of X86-64, llvm-gcc does use aggregate return (for the
interesting cases which return things in registers) and it does do the

I don't follow. By "aggregate return" do you mean "structs as first class
values?" That is, llvm-gcc generates a return of a struct by value?

right thing. However, returning a {i64, i64, i64, i64} by value and
having it automatically be returned "by pointer" is less interesting,

What do you mean by "less interesting?"

as we already have a direct way to handle that (and llvm-gcc already
produces it).

So by, "direct way," you mean, "by using llvm-gcc?" Unfortunately, that
doesn't work for everyone. It seems to me that target-specific issues
like ABI compatibility should be handled by llvm directly.

AFAIK, llvm-gcc/g++ does an *extremely* good job of matching the
X86-64 ABI on mainline.

But that's all implemented within llvm-gcc. LLVM codegen right now
does not implement the ABI correctly.

Apologies if I've misunderstood things again. I'm trying to get clarity on
this issue.

                                         -Dave

In the case of X86-64, llvm-gcc does use aggregate return (for the
interesting cases which return things in registers) and it does do the

I don't follow. By "aggregate return" do you mean "structs as first class
values?" That is, llvm-gcc generates a return of a struct by value?

Yes, consider:

struct foo { double X; long Y; };
struct foo test(double *P1, long *P2) {
   struct foo F;
   F.X = *P1;
   F.Y = *P2;
   return F;
}

we compile this to:

  %struct.foo = type { double, i64 }

define %struct.foo @test(double* %P1, i64* %P2) nounwind {
entry:
  load double* %P1, align 8 ; <double>:0 [#uses=1]
  load i64* %P2, align 8 ; <i64>:1 [#uses=1]
  %mrv3 = insertvalue %struct.foo undef, double %0, 0 ; <%struct.foo> [#uses=1]
  %mrv4 = insertvalue %struct.foo %mrv3, i64 %1, 1 ; <%struct.foo> [#uses=1]
  ret %struct.foo %mrv4
}

which was previously (before first class aggregates got enabled yesterday):

define %struct.foo @test(double* %P1, i64* %P2) nounwind {
entry:
  load double* %P1, align 8 ; <double>:0 [#uses=1]
  load i64* %P2, align 8 ; <i64>:1 [#uses=1]
  ret double %0, i64 %1
}

and both produce this machine code:

_test:
  movq (%rsi), %rax
  movsd (%rdi), %xmm0
  ret

right thing. However, returning a {i64, i64, i64, i64} by value and
having it automatically be returned "by pointer" is less interesting,

What do you mean by "less interesting?"

There are already other ways to handle this, rather than returning the entire aggregate by value. For example, we compile:

struct foo { double X; long Y, Z; };
struct foo test(double *P1, long *P2) {
   struct foo F;
   F.X = *P1;
   F.Y = *P2;
   return F;
}

into:

  %struct.foo = type { double, i64, i64 }
define void @test(%struct.foo* noalias sret %agg.result, double* %P1, i64* %P2) nounwind {
entry:
  load double* %P1, align 8 ; <double>:0 [#uses=1]
  load i64* %P2, align 8 ; <i64>:1 [#uses=1]
  getelementptr %struct.foo* %agg.result, i32 0, i32 0 ; <double*>:2 [#uses=1]
  store double %0, double* %2, align 8
  getelementptr %struct.foo* %agg.result, i32 0, i32 1 ; <i64*>:3 [#uses=1]
  store i64 %1, i64* %3, align 8
  ret void
}

which has no first class aggregates. When the struct is very large (e.g. containing an array) you REALLY REALLY do not want to use first-class aggregate return, you want to return explicitly by pointer so the memcpy is explicit in the IR.

AFAIK, llvm-gcc/g++ does an *extremely* good job of matching the
X86-64 ABI on mainline.

But that's all implemented within llvm-gcc. LLVM codegen right now
does not implement the ABI correctly.

Getting the ABI right requires the front-end to do target-specific work. Without exposing the entire C (and every other language) type through to the code generator, there is no good solution for this. We are working to incrementally improve things though. Thinking the code generator will just magically handle all your ABI issues for you is wishful thinking :slight_smile:

-Chris

and both produce this machine code:

_test:
  movq (%rsi), %rax
  movsd (%rdi), %xmm0
  ret

Ok, that's good.

>> right thing. However, returning a {i64, i64, i64, i64} by value and
>> having it automatically be returned "by pointer" is less interesting,
>
> What do you mean by "less interesting?"

There are already other ways to handle this, rather than returning the
entire aggregate by value. For example, we compile:

struct foo { double X; long Y, Z; };
struct foo test(double *P1, long *P2) {
   struct foo F;
   F.X = *P1;
   F.Y = *P2;
   return F;
}

into:

  %struct.foo = type { double, i64, i64 }
define void @test(%struct.foo* noalias sret %agg.result, double* %P1,
i64* %P2) nounwind {
entry:
  load double* %P1, align 8 ; <double>:0 [#uses=1]
  load i64* %P2, align 8 ; <i64>:1 [#uses=1]
  getelementptr %struct.foo* %agg.result, i32 0, i32 0 ; <double*>:2
[#uses=1]
  store double %0, double* %2, align 8
  getelementptr %struct.foo* %agg.result, i32 0, i32 1 ; <i64*>:3
[#uses=1]
  store i64 %1, i64* %3, align 8
  ret void
}

which has no first class aggregates. When the struct is very large
(e.g. containing an array) you REALLY REALLY do not want to use first-
class aggregate return, you want to return explicitly by pointer so
the memcpy is explicit in the IR.

Ok, I see what you mean. llvm-gcc does the transformation to the hidden
pointer argument.

I'm still not sure this is good. If I hand-write LLVM IR that returns a large
struct by value, the generated code should be correct. It's not right
now AFAIK. If you want to make the memcpy explicit, we could do the
l;owering in a separate pass. That's fine with me, as long as it's
handled by LLVM so it produces correct code.

>> AFAIK, llvm-gcc/g++ does an *extremely* good job of matching the
>> X86-64 ABI on mainline.
>
> But that's all implemented within llvm-gcc. LLVM codegen right now
> does not implement the ABI correctly.

Getting the ABI right requires the front-end to do target-specific
work. Without exposing the entire C (and every other language) type
through to the code generator, there is no good solution for this. We
are working to incrementally improve things though. Thinking the code
generator will just magically handle all your ABI issues for you is
wishful thinking :slight_smile:

I never said anything about magic. You don't need "the entire C (and every
other language) type." What you need is something that tells the code
generator what ABI to use and possibly what the source language was.
It should be possible to then define how each LLVM IR type maps onto the ABI.

                                                        -Dave

David, you're missing something here. There is a many to one mapping of C to LLVM types. From the LLVM type you can't judge what the input type was. You can't just see that an llvm return type is {double,i64} and assign to xmm/gpr. It works in this case, but not in the general case.

For example, in this case:

struct x {
   double x;
   float f;
   int i;
};

struct x foo(float *F, int *I) {
   struct x y;
   y.x = *F;
   y.f = *F;
   y.i = *I;
   return y;
}

llvm-gcc produces:

  ret { double, i64 } %mrv5

to get the right ABI. There is not enough information in the llvm ir to do this without the front-end's help. Again, there is a many to one mapping from C type to LLVM type and not all C types that map onto the same llvm type are supposed to be handled the same way.

-Chris

One concrete example is that some ABIs say that _Complex double is returned differently than struct { double r,i; }.

-Chris

Yes, that's a good point and something I had been missing.

I know that the divide between responsibilities of frontends and
backends is an endless debate. I tend to side with those who
advocate for putting as much of the target-specific stuff into the
backend as possible. That argument would lead me down the
road of advocating for attributes or some other mechanism to
tag types with source information so the backend could do what
needs to be done.

I'm not sure I want to get into that argument. At lerast not right now. :slight_smile:
We're doing some things to fix this on our end., It would just be nice
if not everyone had to do the same thing over and over to accomplish
the same goal.

                                              -Dave

I totally agree, but don't know the right way to do it. Lets talk about this in person next week!

-Chris

Ok. I'll do some hard thinking about this before then.

                                          -Dave

I work with David Greene and I've been looking into the x86-64 ABI.
Right now I'm working with the 2.3 release of LLVM and LLVM-GCC 4.2/2.3
(binary release for linux). I'm unable to replicate the results you
posted here - I'm getting wildly different output. I wonder what I'm
doing wrong. I suspect it has something to do with my not being able to
pass it the -m64 or --64 options, I get

"sorry, unimplemented: 64-bit mode not compiled in"

I want to make sure I'm using the same options and roughly the same
version to make sure I'm on the same page. I'm running on 64 bit SUSE
linux. Can you tell me what options to llvm-gcc you used and how you
built that llvm-gcc (i.e. do I need to build an llvm-gcc from source to
support 64bit mode?) Thanks!

    -Tony S.

Chris Lattner wrote:

Hi Tony,