[GHC] #14684: combineIdenticalAlts is only partially implemented
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- combineIdenticalAlts commons up branches of case expressions which have the same RHS. However, it is not fully implemented so opportunities to common up branches are missed. For very big case expressions in might impact compilation time but it could be something which is enabled by `-O2`. For example, the `C` and `D` case for `foo` are not commened up but the `A` and `B` case in `foo2` are. {{{ module Foo where data T = A | B | C | D foo x = case x of A -> 0 B -> 1 C -> 2 D -> 2 foo2 x = case x of A -> 2 B -> 2 C -> 0 D -> 1 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by AndreasK): * cc: AndreasK (added) Comment: I think the only way to make -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): In `CoreUtils`, `Note [Combine identical alternatives]` acknowledges this problem, saying {{{ To avoid an expensive test, we just merge branches equal to the *first* alternative; this picks up the common cases a) all branches equal b) some branches equal to the DEFAULT (which occurs first) }}} And indeed you are right that it'd be better to combine {{{ foo x = case x of ==> foo x = case x of A -> 0 DEFAULT -> 2 B -> 1 A -> 0 C -> 2 B -> 1 D -> 2 }}} (Reminder: in Core the DEFAULT alternative always comes first, if it exists.) Fortunately, we now have `TrieMap.CoreMap`, an efficient finite map whose keys are `CoreExprs`. Using this I think we can efficiently ask (as we iterate oover the alternatives) "have I seen this RHS in an earlier alternative?". More advanced: find the RHS that occurs most often. Take care that in the common case the RHSs are (a) large and (b) different, then the test does not exhaustively traverse the RHSs; just looks far enough to establish they are different. This a nice well-contained task, if someone would like to have a go. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by mpickering): * keywords: => newcomer Comment: I'll mark it for a newcomer as it is well-specified now and should be a good introduction to the code base. If anyone wants to take it on then feel free to ask for help on #ghc. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by sjakobi): I'm giving this ticket a try. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by sjakobi): * owner: (none) => sjakobi -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4419 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * differential: => Phab:D4419 * milestone: => 8.6.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented
-------------------------------------+-------------------------------------
Reporter: mpickering | Owner: sjakobi
Type: bug | Status: new
Priority: normal | Milestone: 8.6.1
Component: Compiler | Version: 8.2.2
Resolution: | Keywords: newcomer
Operating System: Unknown/Multiple | Architecture:
| Unknown/Multiple
Type of failure: None/Unknown | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s): Phab:D4419
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by Ben Gamari
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4419 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): It's invisible in the message above, but I think this commit is only on branch `wip/T14684`. Is that what you intended? Or did you mean to commit to HEAD? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4419 Wiki Page: | -------------------------------------+------------------------------------- Comment (by sjakobi): Replying to [comment:8 simonpj]:
It's invisible in the message above, but I think this commit is only on branch `wip/T14684`. Is that what you intended? Or did you mean to commit to HEAD?
Fortunately, we now have `TrieMap.CoreMap`, an efficient finite map whose keys are `CoreExprs`. Using this I think we can efficiently ask (as we iterate oover the alternatives) "have I seen this RHS in an earlier alternative?". More advanced: find the RHS that occurs most often. Take care that in the common case the RHSs are (a) large and (b) different,
We agreed that the new most-common-RHS code should be moved into `-O2` before it can land in `master`. BTW, regarding [comment:2 your comment above]: then the test does not exhaustively traverse the RHSs; just looks far enough to establish they are different. In the common case you describe, my code will still insert every alternative into the `CoreMap`. I haven't been able to find a less expensive way to establish that the alternatives are all different, but I'd love to hear about any ideas! I have also found `CSE.combineAlts`: {{{ {- Note [Combine case alternatives] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ combineAlts is just a more heavyweight version of the use of combineIdenticalAlts in SimplUtils.prepareAlts. The basic idea is to transform DEFAULT -> e1 K x -> e1 W y z -> e2 ===> DEFAULT -> e1 W y z -> e2 In the simplifier we use cheapEqExpr, because it is called a lot. But here in CSE we use the full eqExpr. After all, two alternatives usually differ near the root, so it probably isn't expensive to compare the full alternative. It seems like the same kind of thing that CSE is supposed to be doing, which is why I put it here. }}} Should `combineAlts` get the same optimization as `combineIdenticalAlts`? Might `combineAlts` even be the ''better'' place to apply the optimization? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4542 Wiki Page: | -------------------------------------+------------------------------------- Changes (by sjakobi): * differential: Phab:D4419 => Phab:D4542 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4542 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):
Should combineAlts get the same optimization as combineIdenticalAlts? Might combineAlts even be the better place to apply the optimization?
Actually I think you are right -- CSE probably would be a better place. And then (because it doesn't happen all the time), you can probably do this stuff regardless of -O2. (Having a flag might still be good just so you can switch it on and off at will.) I added some comments to Phab which will be useful either way. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4542 Wiki Page: | -------------------------------------+------------------------------------- Changes (by sjakobi): * cc: dfeuer (added) Comment: Replying to [comment:11 simonpj]: Thanks for your comments, Simon! I realized that if I apply the combine-most-common-alts optimization ''only'' in `CSE.combineAlts`, we'd get "suboptimal" results in cases like this: {{{#!hs case x of A -> 1 B -> 1 C -> 2 D -> 2 E -> 2 }}} Here, `combineIdenticalAlts` (which in my understanding runs first) would combine the `A` and `B` alts, defeating `CSE.combineAlts` which could combine `C`, `D` and `E`. I'm not sure if this warrants doing the optimization in both places with `-O2`. ------------- I also noticed that unlike `combineIdenticalAlts` `CSE.combineAlts` doesn't combine the ticks of the identical alts. Would you, David, happen to know why this is permissible in this case? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4542 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):
Here, combineIdenticalAlts (which in my understanding runs first) would combine the A and B alts, defeating CSE.combineAlts which could combine C, D and E.
But that would introduce a nasty phase-ordering problem. Instead, maybe `CSE.combineAlts` should transform {{{ case x of DEFAULT -> 1 C -> 2 D -> 2 E -> 2 }}} (which the user might have written) into {{{ case x of DEFAULT -> 2 A -> 1 B -> 1 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4542 Wiki Page: | -------------------------------------+------------------------------------- Comment (by sjakobi): Replying to [comment:13 simonpj]: Expanding the `DEFAULT` case before recombining the alts is an interesting idea. I'm wondering though if we'd recreate alts that may have been excluded (by the programmer or optimization steps) based on information that isn't available in `CSE`. At worst we'd still just recreate the same `DEFAULT` alt, so I believe no pessimisation is possible. The design I currently have in mind involves largely imitating `SimplUtils.prepareAlts` to 1. detect which constructors are impossible and should not be considered when expanding the `DEFAULT`. 2. use a variant of `refineDefaultAlt` to expand the `DEFAULT` alt into alts using the remaining possible constructors. Does this sound right? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4542 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):
I'm wondering though if we'd recreate alts that may have been excluded (by the programmer or optimization steps) based on information that isn't available in CSE.
Good point. Let's not be over-elaborate. My suggestion: * Try doing it all in `CSE.combineAlts`, as you suggest in comment:9 * Switch off `combineIdenticalAlts` altogether * Do not try the clever stuff suggested in comment:13 for the reasons you mention If we can get away with doing this only in CSE, that'd be an advantage, I think. Less duplication of effort. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer, CSE Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4542 Wiki Page: | -------------------------------------+------------------------------------- Changes (by sjakobi): * keywords: newcomer => newcomer, CSE -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14684: combineIdenticalAlts is only partially implemented -------------------------------------+------------------------------------- Reporter: mpickering | Owner: sjakobi Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: newcomer, CSE Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4542 Wiki Page: | -------------------------------------+------------------------------------- Comment (by sjakobi): As I haven't made any progress with this in a while, and as I'm not sure I'll make any soon, I'm recording where I'm currently stuck: While `combineIdenticalAlts` uses {{{ cheapEqExpr' :: (Tickish Id -> Bool) -> Expr b -> Expr b -> Bool }}} `CSE.combineAlts` uses {{{ eqExpr :: InScopeSet -> CoreExpr -> CoreExpr -> Bool }}} What I haven't figured out, is how to translate the use of `eqExpr` into using a `CoreMap` where `CoreExpr`s end up as the same key if they are equal according to `eqExpr in_scope`. I wanted to look at how the rest of `CSE` uses `CoreMap`s, but I didn't get around to that yet. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14684#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC