Plans considering first class structs and multiple return values

[Matthijs_Kooijman1]

Hi all,

I've been implementing some stuff that uses the new structs-as-firstclass
values code. Apart from some implementation problems, I'm spotting a few
structural problems that seem non-trivial to fix.

In particular, now that structs are a first class values, the old way or
returning multiple values is a bit confusing. The old way had a variable
number of arguments to the return instruction, which could come out at the
caller end as some special aggregrate value that could be indexed using
getresult.

Now that aggregrates are first class, you should be able to simply return a
single struct and access the result in the caller using the new extractvalue
instruction.

However, both approaches define a function with a struct as a return type:
It's not possible to tell the difference between both from looking at the
function type. So, any caller cannot know for sure what to do with the
result...

Also, there is still a lot of code that assumes that having a struct return
type means you're using a multiple return statement, preventing things like

  define {i32, i32} @bar()
  {
    %res1 = insertvalue { i32, i32 } zeroinitializer, i32 1, i32 0
    %res2 = insertvalue { i32, i32 } %res1, i32 2, i32 0
    ret { i32, i32 } %res2
  }

from working (the validator currently barfs over this).

The lack of this distinction also means it is not so trivial to "add" an extra
argument to a function: If the return type is an aggregrate, should you add an
element to that aggregrate, or create a new struct containing the previous
struct and the new value? And what about functions that return void and want
an extra argument? Messy.

The main cause of this is actually the special case for returning a single
value. Instead of returning a struct with one element, you just return the
element. You could make this more consistent by making a function always
return a struct, which most of the time will just contain a single field. I'm
not sure that this is really a usable approach (or what the ABI impact is),
but it could be useful. In particular, a function returning a struct would
then be declared as returning {{i32, i32}} (to distinguish it between a
function returning two values, which would be {i32, i32}). This is also
consistent with making a void function return {}. This kind of stuff could
make a lot of code a lot more regular, but might be a bit annoying to
implemented.

Furthermore, as far as I've understood, the intention is to remove the
"multiple return value" support in favour of returning structs. I take it this
means that at least the getresult instruction will be removed, and possible
the multiple operand return as well. This would partly solve some issues, but
will completely remove the concept of returning multiple values (unless you
adopt the above approach of always returning structs, even for single values).

Additionally, the current form of the ret instruction is still useful, for
making multiple return values readable. In particular, writing
  ret i32 1, i32 2
is a lot more readable than the (functionally identical) three line return
statement above. However, to make the first class aggregrates even more
usable, it might be better to remove the multi operand return instruction and
add support for literal aggregrates. Currently, I think these are only
supported as global constants. It would be useful if the following was valid:
  ret { i32, i32 } { i32 1, i32 2 }
However, llvm-as rejects this. Interestingly, 'zeroinitializer' is a valid
operand to ret, which should be similar to '{ i32 1, i32 2 }' in that they are
both literal aggregates.

Even more, one would also like to be able to build non constant structs in a
similar manner. i.e., writing
  ret { i32, i32 } { i32 %a, i32 %b }
would be a lot more useful than the current
  ret i32 %a, i32 %b
form, since in the first form the ret instruction still has a single operand
that is easy to work with.

Perhaps if using a non-constant literal struct is not so trivial, a
instruction can be added for that instead. Ie,
  %res = buildagg i32 %a, i32 %b
  ret %res

This is still a clean way of building a struct (a lot easier to work with than
nested insertvalues IMHO) but also leaves the ret instruction simple.

Anyway, if using a literal struct as an operand would work, then the multiple
return value ret instruction can probably be removed alltogether.

I've attached a patch with some changes I made to get things working a bit,
but it's not really a decent patch yet. The changes to Andersens' pass are
plain wrong, things can break horribly when you fiddle with structs containing
pointers this way. The others prevent things from asserting and I think they
are consistent with the current state of the code, but will need change
depending on what happens to the return instruction.

Any enlightening thoughs on this issue? I'm I've put down mine in a slightly
chaotic manner, hopefully things will still get across clearly

Gr.

Matthijs

aggregrates.diff (2.38 KB)

[Dan_Gohman3]

Hi all,

I've been implementing some stuff that uses the new structs-as-firstclass
values code. Apart from some implementation problems, I'm spotting a few
structural problems that seem non-trivial to fix.

Hi, thanks for your interest!

Furthermore, as far as I've understood, the intention is to remove the
"multiple return value" support in favour of returning structs. I take it this
means that at least the getresult instruction will be removed, and possible
the multiple operand return as well. This would partly solve some issues, but
will completely remove the concept of returning multiple values (unless you
adopt the above approach of always returning structs, even for single values).

Yes, the intention is that getresult will be removed once first-class
aggregates are a ready replacement. This won't leave LLVM missing the
concept of returning multiple values; a struct can be thought of as
a container for multiple values.

Additionally, the current form of the ret instruction is still useful, for
making multiple return values readable. In particular, writing
  ret i32 1, i32 2
is a lot more readable than the (functionally identical) three line return
statement above. However, to make the first class aggregrates even more
usable, it might be better to remove the multi operand return instruction and
add support for literal aggregrates. Currently, I think these are only
supported as global constants. It would be useful if the following was valid:
  ret { i32, i32 } { i32 1, i32 2 }

I think this form should be valid once first-class struct support is more
complete. If it's not accepted today it may be a conflict with the current
multiple-return-value syntax, or it may be a bug.

Even more, one would also like to be able to build non constant structs in a
similar manner. i.e., writing
  ret { i32, i32 } { i32 %a, i32 %b }
would be a lot more useful than the current
  ret i32 %a, i32 %b
form, since in the first form the ret instruction still has a single operand
that is easy to work with.

The current design will have it looking like this:

        %t0 = insertvalue { i32, i32 } undef, i32 %a, 0
        %t1 = insertvalue { i32, i32 } %t0, i32 %b, 1
        ret { i32, i32 } %t1

once first-class structs take over from the current multiple-return-value
support. It's significantly more syntax, but it's a significantly simpler
IR schema.

Perhaps if using a non-constant literal struct is not so trivial, a
instruction can be added for that instead. Ie,
  %res = buildagg i32 %a, i32 %b
  ret %res

This is still a clean way of building a struct (a lot easier to work with than
nested insertvalues IMHO) but also leaves the ret instruction simple.

This looks nice, and I wouldn't rule out doing it in the future, but it
gets a little awkward in the case of nested aggregates. For the moment,
I'd like to stick with just one way to build aggregates; insertvalue is
sufficient to do everything needed, even if it isn't the prettiest.

Anyway, if using a literal struct as an operand would work, then the multiple
return value ret instruction can probably be removed alltogether.

I've attached a patch with some changes I made to get things working a bit,
but it's not really a decent patch yet. The changes to Andersens' pass are
plain wrong, things can break horribly when you fiddle with structs containing
pointers this way. The others prevent things from asserting and I think they
are consistent with the current state of the code, but will need change
depending on what happens to the return instruction.

Thanks for this patch and the several others! As I mentioned before,
insertelement and extractelement are about to be significantly changed,
for constant indices. Once that's in, I'll be happy to work with you to
revise these patches accordingly and integrate them.

Dan

[Matthijs_Kooijman1]

Hi Dan,

Yes, the intention is that getresult will be removed once first-class
aggregates are a ready replacement. This won't leave LLVM missing the
concept of returning multiple values; a struct can be thought of as
a container for multiple values.

I'm not saying we don't have some way of modeling multiple return values, I'm
sayin the explicit concept disappears. We can use a struct return type to
create a function that effectively returns multiple values, but that is still
a function returning a single value: A struct. In particular, it will be
impossible to distinguish between a function returning a single struct and a
function returning multiple values.

I'm not sure this is a big problem, but it makes adding a return value to a
function harder. I'm not sure this is really a problem though. Would adding a
function attribute returns_multiple or something like that be useful?
returns_multiple would mean to interpret the returned struct as multiple
return values and in particular forbids to use the resulting value in any way
but as an operand to extractvalue. The main goal of this is to make
adding/removing an argument easier, because you only need to modify the
extractvalues. On the other hand, this limitation sounds a lot like the
current getresult approach and might not be all to useful.

> Additionally, the current form of the ret instruction is still
> useful, for
> making multiple return values readable. In particular, writing
> ret i32 1, i32 2
> is a lot more readable than the (functionally identical) three line
> return
> statement above. However, to make the first class aggregrates even
> more
> usable, it might be better to remove the multi operand return
> instruction and
> add support for literal aggregrates. Currently, I think these are only
> supported as global constants. It would be useful if the following
> was valid:
> ret { i32, i32 } { i32 1, i32 2 }

I think this form should be valid once first-class struct support is more
complete. If it's not accepted today it may be a conflict with the current
multiple-return-value syntax, or it may be a bug.

It doesn't seem to be accepted by llvm-as. I think you might be able to build
this in memory, since a ConstantStruct is just a Value*.

> Even more, one would also like to be able to build non constant structs
> in a similar manner. i.e., writing
> ret { i32, i32 } { i32 %a, i32 %b }
> would be a lot more useful than the current
> ret i32 %a, i32 %b
> form, since in the first form the ret instruction still has a single
> operand that is easy to work with.

The current design will have it looking like this:

        %t0 = insertvalue { i32, i32 } undef, i32 %a, 0
        %t1 = insertvalue { i32, i32 } %t0, i32 %b, 1
        ret { i32, i32 } %t1

once first-class structs take over from the current multiple-return- value
support. It's significantly more syntax, but it's a significantly simpler
IR schema.

On the other hand, anyone looking to support multiple return values but other
(potentially complicated) uses for first class structs would have a harder
time trying to find out what these nested insertvalues actually do. The main
difference here is that using insertvalue you can do something like:

  %a = phi { i32, i32 } [ %a.0, %foo ], [ %a.1, %bar ]
  %b = insertvalue { i32, i32 } %a, i32 0, 0

which you can't do directly using a literal { } or buildagg kind of
instruction. OTOH, you can still do things like this using nested structs
then, so having a builddag will probably not improve things much.

Anyhow, so much for my blabbering of incoherent thoughts. I think that simply
using insertvalue for now and not having an explicit multiple return function
attribute should work fine.

Whenever I want to add a function argument, I will just let it return a struct
of two elements (current value and the new value).

I'll also add a feature to the sretpromotion pass that flattens out nested
struct return types as much as possible, without having to reconstruct structs
at the caller end (ie, preserver struct types that are used in any way other
than extractvalue in any caller and flatten out all other elements). Would
this be the right place for that? Or should sretpromotion really only take
care of promotion sret pointer arguments to multiple return values, and have
second pass for flattening them out? A problem of that seems to be that it is
hard for sretpromotion to simply add return values, since it doesn't know
whether to add to the existing struct return type (if any) or create a new
struct return type. I guess integrating these two passes makes the most sense,
then.

I guess the argumentpromotion pass also needs to be adapted to promote first
class struct arguments (probably handle them identical to how byval
pointer-to-struct are handled now), but I don't currently have need of that.

Lastly, I'll modify IPConstProp and DeadArgElim to properly handle multiple
return values and do constprop/removal on each of them individually, instead
of only working when all of them are constant/dead as is done currently.

I'm also thinking of adding a transformation that makes return values dead if
they only return an unmodified argument, this can probably go into
DeadArgElim.

Gr.

Matthijs

[Dan_Gohman3]

Hi Dan,

Yes, the intention is that getresult will be removed once first-class
aggregates are a ready replacement. This won't leave LLVM missing the
concept of returning multiple values; a struct can be thought of as
a container for multiple values.

I'm not saying we don't have some way of modeling multiple return values, I'm
sayin the explicit concept disappears. We can use a struct return type to
create a function that effectively returns multiple values, but that is still
a function returning a single value: A struct. In particular, it will be
impossible to distinguish between a function returning a single struct and a
function returning multiple values.

I'm not sure this is a big problem, but it makes adding a return value to a
function harder. I'm not sure this is really a problem though. Would adding a
function attribute returns_multiple or something like that be useful?
returns_multiple would mean to interpret the returned struct as multiple
return values and in particular forbids to use the resulting value in any way
but as an operand to extractvalue. The main goal of this is to make
adding/removing an argument easier, because you only need to modify the
extractvalues. On the other hand, this limitation sounds a lot like the
current getresult approach and might not be all to useful.

The requirement to update all callers' call instructions when a callee
gets a new return value is also present in the current MRV-mechanism
with getresult. It's not been a problem we've worried about so far.
Can you give some background about what kinds of things you're thinking
about for this?

Additionally, the current form of the ret instruction is still
useful, for
making multiple return values readable. In particular, writing
  ret i32 1, i32 2
is a lot more readable than the (functionally identical) three line
return
statement above. However, to make the first class aggregrates even
more
usable, it might be better to remove the multi operand return
instruction and
add support for literal aggregrates. Currently, I think these are only
supported as global constants. It would be useful if the following
was valid:
  ret { i32, i32 } { i32 1, i32 2 }

I think this form should be valid once first-class struct support is more
complete. If it's not accepted today it may be a conflict with the current
multiple-return-value syntax, or it may be a bug.

It doesn't seem to be accepted by llvm-as. I think you might be able to build
this in memory, since a ConstantStruct is just a Value*.

Ok. I'll look into this after some more of the basics of
first-class aggregates are in place.

Even more, one would also like to be able to build non constant structs
in a similar manner. i.e., writing
  ret { i32, i32 } { i32 %a, i32 %b }
would be a lot more useful than the current
  ret i32 %a, i32 %b
form, since in the first form the ret instruction still has a single
operand that is easy to work with.

The current design will have it looking like this:

       %t0 = insertvalue { i32, i32 } undef, i32 %a, 0
       %t1 = insertvalue { i32, i32 } %t0, i32 %b, 1
       ret { i32, i32 } %t1

once first-class structs take over from the current multiple-return- value
support. It's significantly more syntax, but it's a significantly simpler
IR schema.

On the other hand, anyone looking to support multiple return values but other
(potentially complicated) uses for first class structs would have a harder
time trying to find out what these nested insertvalues actually do. The main
difference here is that using insertvalue you can do something like:

  %a = phi { i32, i32 } [ %a.0, %foo ], [ %a.1, %bar ]
  %b = insertvalue { i32, i32 } %a, i32 0, 0

which you can't do directly using a literal { } or buildagg kind of
instruction. OTOH, you can still do things like this using nested structs
then, so having a builddag will probably not improve things much.

Anyhow, so much for my blabbering of incoherent thoughts. I think that simply
using insertvalue for now and not having an explicit multiple return function
attribute should work fine.

Ok. And as I mentioned before, we can add buildagg (maybe with a
different name ;-)) later if we find it would be of significant
use or convenience. In any case, I'm glad to have someone with a
different perspective thinking about this feature :-).

Whenever I want to add a function argument, I will just let it return a struct
of two elements (current value and the new value).

I'll also add a feature to the sretpromotion pass that flattens out nested
struct return types as much as possible, without having to reconstruct structs
at the caller end (ie, preserver struct types that are used in any way other
than extractvalue in any caller and flatten out all other elements). Would
this be the right place for that? Or should sretpromotion really only take
care of promotion sret pointer arguments to multiple return values, and have
second pass for flattening them out? A problem of that seems to be that it is
hard for sretpromotion to simply add return values, since it doesn't know
whether to add to the existing struct return type (if any) or create a new
struct return type. I guess integrating these two passes makes the most sense,
then.

I'm not sure what you're saying here. What do you mean by flattening out
nested structs? If you mean moving all the members in nested structs to
be members of a single non-nested struct, that doesn't really buy
anything, because extractvalue and insertvalue can index directly into
nested structs.

I guess the argumentpromotion pass also needs to be adapted to promote first
class struct arguments (probably handle them identical to how byval
pointer-to-struct are handled now), but I don't currently have need of that.

Lastly, I'll modify IPConstProp and DeadArgElim to properly handle multiple
return values and do constprop/removal on each of them individually, instead
of only working when all of them are constant/dead as is done currently.

I'm also thinking of adding a transformation that makes return values dead if
they only return an unmodified argument, this can probably go into
DeadArgElim.

Sounds interesting. One thing to keep in mind here is the tradeoff
between teaching existing optimizations special things about
aggregate values, versus having a separate pass that just promotes
first-class aggregate arguments to a bunch of individual
non-aggregate arguments. The latter would let many existing passes
achieve many of the same results as the former without having to be
burdened with special aggregate knowledge, which would be nice.
But it might be less aggressive in some cases.

Dan

[Matthijs_Kooijman1]

Hi Dan,

The requirement to update all callers' call instructions when a callee
gets a new return value is also present in the current MRV-mechanism
with getresult. It's not been a problem we've worried about so far.

I didn't mean you can get away without updating your calllers, I'm just saying
it could be a bit easier.

Can you give some background about what kinds of things you're thinking
about for this?

For example, when I have a function returning {i32, i32} and I want to add
another i32 to that. If this was a function that simply returns two i32
values, any caller will only use extractvalue on the result to get the
seperate values (since the struct as a whole has no meaning). In this case, I
can make the function return {i32, i32, i32}, add an extra extractvalue in
each caller and be done.

If, on the other hand, the struct currently returns a complex number, for
example (or any other struct of two elements), things get more interesting.
In particular, there will probably be callers that don't only use the
individual values, but also the struct as a whole (for example to pass the
resulting complex number to another function.

Now assume we add another i32 using the same approach as above. Then we make
the function return {i32, i32, i32}. Now assume we just modified foo and there
is some caller that does something like:

  %complex = @foo () ; {i32, i32}
  @bar ( {i32, i32 } %complex)

Then after adding an argument we get something like:

  %tmp = @foo () ; {i32, i32, i32}
  %im = extractvalue {i32, i32, i32} %tmp, 0
  %re = extractvalue {i32, i32, i32} %tmp, 1
  %c0 = insertvalue {i32, i32} undef, %im, 0
  %c1 = insertvalue {i32, i32} %c0, %re, 1
  @bar ( {i32, i32 } %c1)

Which isn't pretty code and needs quite some lines of code to generate. In
this case, we're better off creating a new struct, so a function that returns
{ {i32, i32}, i32}, which means we get something like:

  %tmp = @foo () ; { {i32, i32}, i32}
  %complex = extractvalue { {i32, i32}, i32} %tmp, 0
  @bar ( {i32, i32 } %complex)

which is a lot nicer and (a bit) easier to generate. It would be nice if, to
add an argument to a function, you wouldn't need to support both of the above
ways (since the former way is a lot better for a function that returns two
seperate i32's as I described in the first example).

However, the only way to really do this is to make all functions return a
struct, possibly of only a single element. This also requires a guarantee that
nothing special happens to the return value as a whole, but only the
individual elements are accessed through extractvalue.

Alternatively, by adding a function attribute like multiple_return, you could
making the choice between the two ways above easier.

Anyway, I don't think any of the above suggestions are really worth
implementing, I'm just trying to explain my thought process now.

In practice, I guess the second way can be used pretty much everywhere (i.e.,
to add a return values, you simply make the function return a struct of two
elements, regardless of what it returned before [with the exception of void
functions, of course...]).

This approach could possibly result in ugly nested structs like
{{{{i32},i32},i32},i32} after adding three values, for example. Considering
that adding return values is really not used anywhere except for
sretpromotion (and there not really either), this is probably not a big deal.
However, for our particular applications we like the function results to be as
flat as possible, to simplify our codegeneration.

Ok. And as I mentioned before, we can add buildagg (maybe with a
different name ;-))

Yeah, builddag is an ugly name :-p

later if we find it would be of significant use or convenience.

By then, we will probably have though our backend to read insertvalue chains,
so it won't be really necessary anymore But let's keep it in mind.

In any case, I'm glad to have someone with a different perspective thinking
about this feature :-).

> Whenever I want to add a function argument, I will just let it
> return a struct
> of two elements (current value and the new value).
>
> I'll also add a feature to the sretpromotion pass that flattens out
> nested
> struct return types as much as possible, without having to
> reconstruct structs
> at the caller end (ie, preserver struct types that are used in any
> way other
> than extractvalue in any caller and flatten out all other elements).
> Would
> this be the right place for that? Or should sretpromotion really
> only take
> care of promotion sret pointer arguments to multiple return values,
> and have
> second pass for flattening them out? A problem of that seems to be
> that it is
> hard for sretpromotion to simply add return values, since it doesn't
> know
> whether to add to the existing struct return type (if any) or create
> a new
> struct return type. I guess integrating these two passes makes the
> most sense,
> then.

I'm not sure what you're saying here. What do you mean by flattening out
nested structs? If you mean moving all the members in nested structs to
be members of a single non-nested struct, that doesn't really buy
anything, because extractvalue and insertvalue can index directly into
nested structs.

Yeah, that is what I meant. I hadn't thought about the multiple indexing, good
that you mention it. Still, for our backend, having structs flat whenever
possible will probably make things easier, not sure if that also holds for
other backends? I guess this depends a bit on what codegenerators (will) do
with (nested) struct returns, but I'm not really into that.

Reconsidering, the sretpromotion pass might not be the best place for this. It
currently promotes the special sret pointer arguments to multiple return
values (I should probably modify it to use a struct return and insertvalue
instead?). Since an sret function will, by definition, have a void return
type, the new return values will never have to be merged.

In that light, I will be probably building an internal (i.e., to our company)
pass that flattens struct return values.

> I guess the argumentpromotion pass also needs to be adapted to
> promote first
> class struct arguments (probably handle them identical to how byval
> pointer-to-struct are handled now), but I don't currently have need
> of that.
>
> Lastly, I'll modify IPConstProp and DeadArgElim to properly handle
> multiple
> return values and do constprop/removal on each of them individually,
> instead
> of only working when all of them are constant/dead as is done
> currently.
>
> I'm also thinking of adding a transformation that makes return
> values dead if
> they only return an unmodified argument, this can probably go into
> DeadArgElim.

Sounds interesting. One thing to keep in mind here is the tradeoff
between teaching existing optimizations special things about
aggregate values, versus having a separate pass that just promotes
first-class aggregate arguments to a bunch of individual
non-aggregate arguments.

Promoting struct arguments to multiple seperate values is exactly what I said
that needed happening (but since I'm currently using byval struct* arguments,
which are already handled by argpromotion) I'm probably not going to change
this.

However, that will not help for return values, as the passes I mentioned
(IPConstProp and DeadArgElim) do not look at individual return values
currently, only the returned struct as a whole. I do not intend to modify the
argument propagation/elimination of these passes, for I agree that that should
be handled by running argumentpromotion first.

Thanks for your insights!

Matthijs

[clattner]

Can you give some background about what kinds of things you're thinking
about for this?

For example, when I have a function returning {i32, i32} and I want to add
another i32 to that. If this was a function that simply returns two i32
values, any caller will only use extractvalue on the result to get the
seperate values (since the struct as a whole has no meaning). In this case, I
can make the function return {i32, i32, i32}, add an extra extractvalue in
each caller and be done.

This can't really work in either case. Once created, there is no way to change the type of a Value*. Changing the result of a call from {i32, i32} to {i32, i32, i32} is just as impossible as changing it from {i32,i32} to i32. You have to create a new callinst in either case.

Then after adding an argument we get something like:

  %tmp = @foo () ; {i32, i32, i32}
  %im = extractvalue {i32, i32, i32} %tmp, 0
  %re = extractvalue {i32, i32, i32} %tmp, 1
  %c0 = insertvalue {i32, i32} undef, %im, 0
  %c1 = insertvalue {i32, i32} %c0, %re, 1
  @bar ( {i32, i32 } %c1)

Which isn't pretty code and needs quite some lines of code to generate. In
this case, we're better off creating a new struct, so a function that returns
{ {i32, i32}, i32}, which means we get something like:

  %tmp = @foo () ; { {i32, i32}, i32}
  %complex = extractvalue { {i32, i32}, i32} %tmp, 0
  @bar ( {i32, i32 } %complex)

Why would you ever want to pass multiple values as an aggregate to a call? The only thing I can think of is for ABI reasons. If you can do an ABI changing transformation (such as you propose) the first thing I'd do is expand the aggregate to pass as a series of scalars. Having argpromotion do this would be very natural.

However, the only way to really do this is to make all functions return a
struct, possibly of only a single element. This also requires a guarantee that
nothing special happens to the return value as a whole, but only the
individual elements are accessed through extractvalue.

After MRVs are working really well, I'd like to consider removing the void type:
http://nondot.org/sabre/LLVMNotes/EliminatingVoid.txt

This would make it so that calls always return a value, and 'ret' always takes a value. This would be a nice simplification to the IR I think.

Ok. And as I mentioned before, we can add buildagg (maybe with a
different name ;-))

Yeah, builddag is an ugly name :-p

later if we find it would be of significant use or convenience.

By then, we will probably have though our backend to read insertvalue chains,
so it won't be really necessary anymore But let's keep it in mind.

If you're using IRBuilder, why not just add a new CreateBuildMRV method that inserts the sequence of insertvalue's for you?

Reconsidering, the sretpromotion pass might not be the best place for this. It
currently promotes the special sret pointer arguments to multiple return
values (I should probably modify it to use a struct return and insertvalue
instead?). Since an sret function will, by definition, have a void return
type, the new return values will never have to be merged.

In that light, I will be probably building an internal (i.e., to our company)
pass that flattens struct return values.

stretpromotion was really just for testing. I expect that when MRVs work predictably 100% of the time (even if not something the ABI supports, for example) that the functionality will be pulled into the argpromotion pass.

Sounds interesting. One thing to keep in mind here is the tradeoff
between teaching existing optimizations special things about
aggregate values, versus having a separate pass that just promotes
first-class aggregate arguments to a bunch of individual
non-aggregate arguments.

Promoting struct arguments to multiple seperate values is exactly what I said
that needed happening (but since I'm currently using byval struct* arguments,
which are already handled by argpromotion) I'm probably not going to change
this.

In general, I think that all the optimizers should try to rip apart MRVs when possible and focus on optimizing scalars. This is not generally possible for return values, because there is no other way to return multiple values, but it is possible for arguments to calls.

-Chris

[clattner]

Furthermore, as far as I've understood, the intention is to remove the
"multiple return value" support in favour of returning structs.

Yep.

I
take it this
means that at least the getresult instruction will be removed, and
possible
the multiple operand return as well. This would partly solve some
issues, but
will completely remove the concept of returning multiple values
(unless you
adopt the above approach of always returning structs, even for
single values).

Yes, the intention is that getresult will be removed once first-class
aggregates are a ready replacement. This won't leave LLVM missing the
concept of returning multiple values; a struct can be thought of as
a container for multiple values.

Right.

Additionally, the current form of the ret instruction is still
useful, for
making multiple return values readable. In particular, writing
  ret i32 1, i32 2
is a lot more readable than the (functionally identical) three line
return
statement above. However, to make the first class aggregrates even
more
usable, it might be better to remove the multi operand return
instruction and
add support for literal aggregrates. Currently, I think these are only
supported as global constants. It would be useful if the following
was valid:
  ret { i32, i32 } { i32 1, i32 2 }

I think this form should be valid once first-class struct support is
more
complete. If it's not accepted today it may be a conflict with the
current
multiple-return-value syntax, or it may be a bug.

Right. Returning a ConstantStruct should be legal, and not a real problem.

Even more, one would also like to be able to build non constant
structs in a
similar manner. i.e., writing
  ret { i32, i32 } { i32 %a, i32 %b }
would be a lot more useful than the current
  ret i32 %a, i32 %b
form, since in the first form the ret instruction still has a single
operand
that is easy to work with.

The current design will have it looking like this:

       %t0 = insertvalue { i32, i32 } undef, i32 %a, 0
       %t1 = insertvalue { i32, i32 } %t0, i32 %b, 1
       ret { i32, i32 } %t1

once first-class structs take over from the current multiple-return-
value
support. It's significantly more syntax, but it's a significantly
simpler
IR schema.

Agreed. Thanks to both of you for working on this!

-Chris

[Matthijs_Kooijman1]

Hi Chris,

>> Can you give some background about what kinds of things you're
>> thinking
>> about for this?
> For example, when I have a function returning {i32, i32} and I want
> to add
> another i32 to that. If this was a function that simply returns two
> i32
> values, any caller will only use extractvalue on the result to get the
> seperate values (since the struct as a whole has no meaning). In
> this case, I
> can make the function return {i32, i32, i32}, add an extra
> extractvalue in
> each caller and be done.

This can't really work in either case. Once created, there is no way
to change the type of a Value*. Changing the result of a call from
{i32, i32} to {i32, i32, i32} is just as impossible as changing it
from {i32,i32} to i32. You have to create a new callinst in either
case.

By "Changing the return type", I meant "Create a new function with a changed
return type and updating all calls". The argument still holds, that this is
easier to do in some cases than others.

> { {i32, i32}, i32}, which means we get something like:
>
> %tmp = @foo () ; { {i32, i32}, i32}
> %complex = extractvalue { {i32, i32}, i32} %tmp, 0
> @bar ( {i32, i32 } %complex)

Why would you ever want to pass multiple values as an aggregate to a
call? The only thing I can think of is for ABI reasons. If you can
do an ABI changing transformation (such as you propose) the first
thing I'd do is expand the aggregate to pass as a series of scalars.
Having argpromotion do this would be very natural.

I was just using @bar to show that the complex struct is used as-is somewhere,
so it can't be broken up completely. In this particular case, it could be that
@foo() is internal (and thus can be changed) but @bar is external and has to
be kept unchanged.

Anyway, it was just an example.

In practice, just taking whatever the function is returning now, and put that
into a struct together with whatever you want to add and then letting other
passes make something pretty out of the resulting extractvalue/insertvalue
forest will work just fine.

After MRVs are working really well, I'd like to consider removing the
void type:
http://nondot.org/sabre/LLVMNotes/EliminatingVoid.txt

This would make it so that calls always return a value, and 'ret'
always takes a value. This would be a nice simplification to the IR I
think.

Doing this will make functions returning a single value stand out even more,
since a function returning 0 or more than 1 values will always return a
struct, while a function returning 1 value will just return that value. Don't
think this is really a problem, though.

If you're using IRBuilder, why not just add a new CreateBuildMRV
method that inserts the sequence of insertvalue's for you?

Hmm, that would actually make sense I guess. I'm not currently using
IRBuilder, but I might move some code into there.

stretpromotion was really just for testing. I expect that when MRVs
work predictably 100% of the time (even if not something the ABI
supports, for example) that the functionality will be pulled into the
argpromotion pass.

Will sretpromotion still be needed? If the frontends would generate functions
returning a struct directly instead of using an sret argument, sret could
perhaps be removed alltogether? Though I guess there is an ABI difference
between using sret and returning a structure directly?

Gr.

Matthijs

[Duncan_Sands]

Hi,

Will sretpromotion still be needed? If the frontends would generate functions
returning a struct directly instead of using an sret argument, sret could
perhaps be removed alltogether? Though I guess there is an ABI difference
between using sret and returning a structure directly?

right, there's an ABI difference. Also you can't return variable sized structs
using MRV support (I don't know if gcc really supports this, but some pieces of
code inside gcc mention functions returning variable sized objects).

Ciao,

Duncan.

[Devang_Patel1]

Plus it is not a good idea to pass very large structs using MRV.

[Marc_de_Kruijf]

Hi, I'm really interested in this effort. What is its status? Is any
of it in svn yet? (I only see the insert/extract value instructions
so far... nothing w.r.t. creating a first-class struct/array). Can I
do anything to help?

Marc

[Dan_Gohman3]

Hello,

The basic infrastructure is in place. You can create first-class
structs/arrays using sequences of insertvalue.

For example, this:

   %t0 = insertvalue { i32, i32 } undef, i32 %a, 0
   %t1 = insertvalue { i32, i32 } %t0, i32 %b, 1

creates the value with %a and %b as member values. Other ways to
produce aggregate values are loads, function arguments, function
return values, and literal constants.

It's all pretty new and hasn't seen much exposure, so one of
the things it needs right now is for people to try it out and
see how it goes.

There is work yet to be done in several of the optimization
components. And codegen can't yet handle aggregate return
values larger than what fits in designated return value
registers. I'm planning to have LLVM auto-upgrade the
multiple-return-value constructs that exist in LLVM 2.3,
which should give it quite a bit of exposure, though that
probably won't happen for a while.

And while I'm here, I want to emphasize that this feature does
not completely solve the problem of C-oriented ABI-compliant
passing/returning of structs. That's a complicated problem, and
unfortunately it is beyond the immediate scope of this feature.

Dan

[Marc_de_Kruijf]

For example, this:

  %t0 = insertvalue { i32, i32 } undef, i32 %a, 0
  %t1 = insertvalue { i32, i32 } %t0, i32 %b, 1

creates the value with %a and %b as member values.

Is there anyway to do it using the C++ API? It seems I need an
instance of the aggregate type to pass into InsertValueInst::Create().
What is the API equivalent of "undef"?

Marc

[Eli_Friedman1]

UndefValue::get(const Type*), in Constants.h.

-Eli

[Matthijs_Kooijman_In]

Hi Marc,

there a few examples of this in the code, have look at BuildSubAggregate in
lib/Analysis/ValueTracking.cpp for example (there's quite some code around it
and it's recursive, which doesn't make this the best example, but it should
help).

The interesting parts look something like this:

Value *Undef = UndefValue::get(IndexedType);
Value *T0 = lvm::InsertValueInst::Create(To, V, Idxs.begin(),
                                         Idxs.end(), "tmp", InsertBefore);
Value *T1 = lvm::InsertValueInst::Create(To, V, Idxs2.begin(),
                                         Idxs2.end(), "tmp", InsertBefore);

Gr.

Matthijs

[fweimer]

* Duncan Sands:

right, there's an ABI difference. Also you can't return variable sized structs
using MRV support (I don't know if gcc really supports this, but some pieces of
code inside gcc mention functions returning variable sized objects).

At one point, the MIPS back end supported returning variably-sized
structs with an elevated stack pointer (the goal was to remove the need
for Ada's secondary stack), but that has been removed since then.