#9136: Constant folding in Core could be better --------------------------------------------+------------------------------ Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Comment (by simonpj): You could do that in `PrelRules` too. Yes, being able to do it in source code would be cool, but it all requires more syntax, a story about what predicates are allowed, etc etc, and it is far from obvious where to stop. The advantage of `PrelRules` is that you can do anything! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better --------------------------------------------+------------------------------ Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Comment (by nomeata): Care to explain? `(x +# y) -# z = x +# (y -# z)` looks very much like rewriting to me, and rewrite rules are a powerful mechanism for that. And if we were able to specify that declaratively in source code, instead of letting the compiler grow and grow, even better, I’d say. Also note that constant folding is also done with (built-in, more powerful) RULES already. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better --------------------------------------------+------------------------------ Reporter: simonpj | Owner: nomeata Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Changes (by nomeata): * owner: => nomeata Comment: I couldn’t resist to get started on this, so branch `wip/T9136` contains a test case ([changeset:d4081919/ghc]) and a first implementation for `+` ([changeset:115fd8b043/ghc]). Not polished and complete yet, and not yet validated, but it goes in the right direction I think. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better --------------------------------------------+------------------------------ Reporter: simonpj | Owner: nomeata Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Comment (by carter): One concern if have off hand: couldn't this sort of optimization change how a program under/overflows? I can't think of an example off hand, but could that happen? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better --------------------------------------------+------------------------------ Reporter: simonpj | Owner: nomeata Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Comment (by nomeata): Refactored the code; no more transformation `x -# (Lit n)` to `x +# (Lit -n)` unless it is required to combine some literals. This yields prettier Core and this way it validates without having to update test result core output. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better --------------------------------------------+------------------------------ Reporter: simonpj | Owner: nomeata Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Comment (by carter): @nomeata .... so I thought a bit about your reply... and part of my concern stems from the fact that the wrapping behavior of Int in GHC is actually a choice of "undefined" behavior by the various Haskell language standards. Point being, while wrap around is "folklore behavior", its actually deemed undefined by the standard. And it constitutes moving that undefined "folklore" into being a strong assumption in ghc. how would GCC come into play? theres no peephole optimization by the system assembler level in -fasm to my knowledge. most of the examples i've seen where arithmetic optimization makes a HUGE win are in the context of heavy bit fiddling sequences (I have some example that are 40 instructions long in -fasm, but optimized to NOOP on -fllvm), and various sophisticated array indexing computations. If nofib doesn't show a measurable difference and theres no motivating example program that shows a strong win.. I'd argue its not worth adding the rules. I'm happy to share some more interesting examples, but I'm not sure if they actually can be handled by a rewrite rules discipline. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better --------------------------------------------+------------------------------ Reporter: simonpj | Owner: nomeata Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Comment (by nomeata): @SPJ: Since you opened the ticket I guess it’s your call whether you think this is worth it, even if nofib shows no measurable improvement. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better --------------------------------------------+------------------------------ Reporter: simonpj | Owner: nomeata Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Comment (by simonpj): I had a look and the patch seemed broadly OK, through rather under- commented. Notably the parameters to the key function, whose name I now forget, and a user-readable version of the rewrite that each block of code performs. Care is needed to be sure that the rewrites really are semantics preserving, given that overflow may happen. It's probably ok because the types involved do wrap-around, but that very point needs a careful `Note` in the code. By all means extend it further, but please do document it well. One thing to bear in mind is that these rewrite rules are tried for every single expression `(op a b)`, where `op` is (say) `Int#` addition, and every single iteration of the simplifier. So it needs to fail fast if it ends up doing nothing. An alternative would be an entirely separate pass, which can then be as expensive as you like. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

@Joachim: is this patchset still in limbo? If there's no measurable

#9136: Constant folding in Core could be better -------------------------------------+------------------------------------- Reporter: simonpj | Owner: nomeata Type: bug | Status: infoneeded Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by nomeata): performance impact, but it improves code and doesn't hurt performance, I don't see why you cannot merge it. Compiler code complexity would be one reason to not merge it. Other than that I mostly forgot about this... and so I’m not sure about the completeness of my work (and it needs more comments, as always). I’ll eventually return to it, but without high priority. Just leave it assigned to me. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: infoneeded Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by nomeata): * owner: nomeata => Comment: Given the general doubt about these changes, I’ll unassign this ticket. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: infoneeded Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by maoe): * cc: maoe (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:22 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: infoneeded Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2858 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"fea04defa64871caab6339ff3fc5511a272f37c7/ghc" fea04de/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="fea04defa64871caab6339ff3fc5511a272f37c7" Enhanced constant folding Until now GHC only supported basic constant folding (lit op lit, expr op 0, etc.). This patch uses laws of +/-/* (associativity, commutativity, distributivity) to support some constant folding into nested expressions. Examples of new transformations: - simple nesting: (10 + x) + 10 becomes 20 + x - deep nesting: 5 + x + (y + (z + (t + 5))) becomes 10 + (x + (y + (z + t))) - distribution: (5 + x) * 6 becomes 30 + 6*x - simple factorization: 5 + x + (x + (x + (x + 5))) becomes 10 + (4 *x) - siblings: (5 + 4*x) - (3*x + 2) becomes 3 + x Test Plan: validate Reviewers: simonpj, austin, bgamari Reviewed By: bgamari Subscribers: thomie GHC Trac Issues: #9136 Differential Revision: https://phabricator.haskell.org/D2858 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:24 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2858 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: infoneeded => patch * milestone: => 8.6.1 Comment: Oh dear, yes, excellent point; I dropped the ball on this. I'll re-merge for 8.6. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:26 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2858 Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): Merged for 8.6. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:28 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9136: Constant folding in Core could be better -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2858 Wiki Page: | -------------------------------------+------------------------------------- Comment (by spacekitteh): Do these rules fire for floating point operations? Because they are neither associative nor distributive. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9136#comment:30 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler