Make foldl's inline phased, and see what happens? Presumably the reason it doesn't have a phase limit yet is that it never participated in any fusion before, so there was never a reason to not just inline. Other than that it seems like: reverse xs => rewrite build (\c n -> foldl (noinlineFlip c) n xs) => inline foldl (noinlineFlip (:)) [] xs => rewrite reverse xs where I assume you need a special flip which may or may not exist in these modules already. On Fri, Aug 15, 2014 at 12:46 PM, David Feuer <david.feuer@gmail.com> wrote:

Yes, but I'm not sure how to do that, especially because foldl doesn't have the phased NOINLINE that foldr does. On Aug 15, 2014 12:45 PM, "Dan Doel" <dan.doel@gmail.com> wrote:

...

Isn't this kind of thing fixed for other functions by rewriting back into the direct recursive definition if no fusion happens?

On Fri, Aug 15, 2014 at 11:41 AM, David Feuer <david.feuer@gmail.com> wrote:

...

I'm having trouble when it doesn't fuse—it ends up with duplicate bindings at the top level, because build gets inlined n times, and the result lifted out. Nothing's *wrong* with the code, except that there are multiple copies of it. On Aug 15, 2014 10:58 AM, "GHC" <ghc-devs@haskell.org> wrote:

...

#9434: GHC.List.reverse does not fuse

-------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: | Version: 7.9 libraries/base | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: |

-------------------------------------+-------------------------------------

Comment (by simonpj):

Great. Just check that when fusion ''doesn't'' take place, the result is good. And do a `nofib` comparison for good luck. Then submit a patch.

Thanks for doing all this work on fusion, David.

Simon

-- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9434#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

I'm working on it, based on a discussion with Dan Doel. That said, Haskell's supposed to be anti-pattern, and rewrite/transform/write-back is definitely a pattern—and a somewhat painful one. Aside from having to use forms that can be matched on (intentionally blinding the inliner) there's the unfortunate fact that the written-back forms have to be hand-written recursive definitions. That's what made me think about a CSE-like cleanup pass, despite not knowing nearly enough to be able to write it myself just yet. I wouldn't want full CSE, but rather just to merge identical top-level lambda forms, which I *think* should avoid potential performance issues caused by full CSE. Some challenges relating to the idea: 1. It would be very nice if named forms were given preference. So if there are two copies of \foo -> bar, and the programmer has named one of them baz, then they should ideally be merged to baz, rather than to quux17. No, I have no idea what might be involved. 2. In a sufficiently large module, compilation speed could theoretically be a problem. I don't think this is likely, however, especially since distinct expressions usually diverge fairly high in their syntax trees. 3. If there are a *lot* of copies of some functions, the copies could make the Core harder to read. I would conjecture that this will not happen often. On Aug 17, 2014 6:13 PM, "Simon Peyton Jones" <simonpj@microsoft.com> wrote:

Well, I’d *much* rather avoid creating the duplication in the first place, than to create and try to CSE it away. Others have suggested ways of doing so, following the pattern of existing RULES.

Simon

*From:* David Feuer [mailto:david.feuer@gmail.com] *Sent:* 15 August 2014 16:41 *To:* ghc-devs; Simon Peyton Jones *Subject:* Re: [GHC] #9434: GHC.List.reverse does not fuse

I'm having trouble when it doesn't fuse—it ends up with duplicate bindings at the top level, because build gets inlined n times, and the result lifted out. Nothing's *wrong* with the code, except that there are multiple copies of it.

On Aug 15, 2014 10:58 AM, "GHC" <ghc-devs@haskell.org> wrote:

#9434: GHC.List.reverse does not fuse -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: | Version: 7.9 libraries/base | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+-------------------------------------

Comment (by simonpj):

Great. Just check that when fusion ''doesn't'' take place, the result is good. And do a `nofib` comparison for good luck. Then submit a patch.

Thanks for doing all this work on fusion, David.

Simon

-- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9434#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler