too much let-floating

[Duncan Coutts]

On Mon, 2007-06-04 at 12:31 +0100, Simon Peyton-Jones wrote:
> | This is a bit disappointing of course, so how do we fix it. There are
> | two possibilities as far as I can see. Either don't let float it, or
> | have the rule matcher look through the indirection.
> 
> This is a tricky one.  One possibility would be to postpone full
> laziness until later in the optimisation pipeline.  But then some
> useful sharing isn't as easily accessible.  For example, if you look
> in DynFlags, where the main pass structure is defined, you'll see:
> 
>         -- Don't inline anything till full laziness has bitten
>         -- In particular, inlining wrappers inhibits floating
>         -- e.g. ...(case f x of ...)...
>         --  ==> ...(case (case x of I# x# -> fw x#) of ...)...
>         --  ==> ...(case x of I# x# -> case fw x# of ...)...
>         -- and now the redex (f x) isn't floatable any more
>         -- Similarly, don't apply any rules until after full
>         -- laziness.  Notably, list fusion can prevent floating.
> 
> Making the rule matcher look through lets could be possible.  Maybe
> even on a rule-by-rule basis.  But consider
>         f x = let xs = map expensive [1..x]
>                 in (sum xs, prod xs)
> If you are prepared to duplicate xs, you can fuse with both 'sum' and
> 'product'.  But duplicating 'xs' duplicates an arbitrarily large
> computation. Are you sure you want that?  The beauty of the "only
> match when the subexpression is literally there" idea is that you
> *know* it's the unique occurrence.

No, I don't want to duplicate. But in my example the let var was only
used once, so there was no sharing problem. So in this 

> Matching on a 'let' that's outside a lambda is potentially even more
> extreme; the example above was only 2-way sharing.

So instead of having the rule matcher do some kind of on the fly let
inlining, it should not have been floated out in the first place. So if
the let was indeed originally outside the lambda then inlining it adds
more allocation, but if we choose not to let-float it then we're not
making the program worse, we're just missing an opportunity to reduce
allocation. But if we can identify a good reason not to let float it
(like it appearing in a rule) then we can avoid thinking about
duplicating let bound things.

> I think you might be on solider ground if you declare that some
> functions are "cheap enough to duplicate"; in this case your 'write'
> function.  But even then you need to take care:
>         let x = cheap_fun a b in \y. ....(foo x)....
> Now a rule (foo (cheap_fun p q)) might perhaps match.  But what if 'a'
> or 'b' was expensive?!  Then we'd prefer that the defn of x looked
> like
>         let a = <a-code>; b = <b-code>; x = cheap_fun a b
>         in \y. ...
> But now it's less easy to match rules like (foo (cheap_fun (g x) (h y)))
> 
> Nevertheless, my nose tells me that promising that a function is cheap
> may be the most robust way forward.


Yes, but I'm not sure this case is really one where we're dealing with
duplicating a cheap thing. We're just not let-floating something that
could be let-floated.

In my original example, once we get to a later phase of compilation, the
let bound thing does get inlined again. Once the bind and write
functions get inlined, lots of case expressions appear and then it
becomes obvious that it'd be beneficial to inline, and ghc does so. And
as I say, it was only used in one place. So the frustrating thing is
that it is let-floated *only* for the one phase where I need it not to
be floated so I can rule match on it :-).

So how about the idea of taking the rule pattern into account when
deciding to let-float? In this case it should be clear that the benefits
of let floating are pretty marginal, so I'd guess it just needs a little
extra nudge to decide that this case isn't beneficial to float out. That
is, my guess is that we'd not loose many beneficial let-floatings by
taking the presence of a rule into account. But that's only a guess.

Duncan