Re: call-with-values inliner

[Jamison Hope <jrh at theptrgroup dot com>]

On Dec 9, 2014, at 2:12 AM, Per Bothner <per@bothner.com> wrote:

> On 12/08/2014 11:04 AM, Jamison Hope wrote:
>> Here's an optimization for call-with-values when the producer and
>> consumer are both lambda expressions and the consumer lambda takes a
>> fixed number of arguments.
> 
> Great minds think alike - I've also been working on this problem.
> (An earlier draft of the "conditional bindings" from my prior email
> used call/cc with call-with-values, so it needed good optimization.
> However, I ended up using BlockExp instead, which is simpler - though
> I did find some bugs in the BlockExp implementation.)
> 
> I'll have to look at your suggestions and patch later, though
> at first glance it looks reasonable.
> 
> I've also been pondering how to handle multiple value types.
> One way is using parameterised types - see attached patch.
> 
> Another way is with a subclass of OccurrenceType, with a fixed set of
> item types.  That can be useful for representing a low-overhead tuple
> - e.g. within a method one can push multiple values of the JVM stack.
> You can't return multiple values from a method with way, but if a multi-valued
> function method is inlined (for example floor/ or values itself) then the
> values can be pushed on the JVM stack - and then call-values-values
> and related functions can cheaply pass them along.

That sounds promising.

Another optimization I thought about but didn't pursue was to determine
which values are actually needed, and only get() those, rather than all
of the values.  For example, in

(let-values (((root rem) (exact-integer-sqrt n))) rem)

which expands to something like:

(call-with-values (lambda () (exact-integer-sqrt n))
                  (lambda (rt rm) rm)))

My patch turns that into

...
(let ((rt (vals:get 0))
      (rm (vals:get 1)))
  rm)
...

But it really doesn't need to get/bind the first value at all.  How do
you determine whether a particular argument is referenced within a
lambda's body?  For this kind of inlining, it seems like it could be
useful to cull unneeded elements from a lambda's parameter list (or a
let's bindings) -- and simultaneously from the surrounding ApplyExp.

In your OccurrenceType scenario, the equivalent would be to skip over
pushing elements to the stack which will never be needed.

In general you would have to be careful not to optimize away calls with
side effects, but in this case it would be safe.

> Still pondering how to get the pieces together -including how to relate the
> "boxed" type (i.e. Chained or some other Values) and the "unboxed" type
> (just a series of values).
> -- 
> 	--Per Bothner
> per@bothner.com   http://per.bothner.com/
> <Values.patch>

--
Jamison Hope
The PTR Group
www.theptrgroup.com