Why do the reverse binder swap transformation?

[Simon Peyton Jones]

Consider

f x = letrec go y = case x of z { (a,b) -> ...(expensive z)... }
        in ...

If we do the reverse binder-swap we get

f x = letrec go y = case x of z { (a,b) -> ...(expensive x)... }
        in ...

and now we can float out:

f x = let t = expensive x
        in letrec go y = case x of z { (a,b) -> ...(t)... }
        in ...

Now (expensive x) is computed once, rather than once each time around the
'go' loop..

Would you like to elaborate the Note to explain this better?

Simon


On Fri, 14 Jul 2023 at 16:30, Rodrigo Mesquita <rodrigo.m.mesquita at gmail.com>
wrote:

> Dear GHC devs,
>
> I’m wondering about the reverse binder swap transformation, the one in
> which we substitute occurrences of the case binder by occurrences of the
> scrutinee (when the scrut. is a variable):
>
>         case x of z { r -> e }
>         ===>
>         case x of z { r -> e[x/z] }
>
> My question is: why do we do this transformation? An example in which this
> transformation is beneficial would be great too.
>
> The Note I’ve found about it, Note [Binder-swap during float-out], wasn’t
> entirely clear to me:
>
>         4. Note [Binder-swap during float-out]
>            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>            In the expression
>                 case x of wild { p -> ...wild... }
>            we substitute x for wild in the RHS of the case alternatives:
>                 case x of wild { p -> ...x... }
>            This means that a sub-expression involving x is not "trapped"
> inside the RHS.
>            And it's not inconvenient because we already have a
> substitution.
>
>           Note that this is EXACTLY BACKWARDS from the what the simplifier
> does.
>           The simplifier tries to get rid of occurrences of x, in favour
> of wild,
>           in the hope that there will only be one remaining occurrence of
> x, namely
>           the scrutinee of the case, and we can inline it.
>
> Many thanks,
> Rodrigo
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20230714/cbba933c/attachment.html>