[LLVMdev] Plans considering first class structs and multiple return values

[Matthijs Kooijman]

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>