too much let-floating
simonpj at microsoft.com
Mon Jun 4 07:31:34 EDT 2007
| 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.
Matching on a 'let' that's outside a lambda is potentially even more extreme; the example above was only 2-way sharing.
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.
More information about the Glasgow-haskell-users