llvm dev - Jun 2008 - [LLVMdev] Plans considering first class structs and multiple return values

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080602/13705efc/attachment.sig>

On Jun 2, 2008, at 1:03 PM, Matthijs Kooijman wrote:
>> 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

Hi Chris,

On Sat, Jun 07, 2008 at 02:59:03PM -0700, Chris Lattner
wrote:
> On Jun 2, 2008, at 1:03 PM, Matthijs Kooijman wrote:
> >> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080609/845b4de8/attachment.sig>