[GHC] #13032: Redundant forcing of Given dictionaries
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 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: -------------------------------------+------------------------------------- If you look at the test case for #13025 you'll see code like {{{ f :: (a~~b) => a -> b -> Bool f d x y = case HEq_sc d of (cobox :: a ~# b) -> True }}} From the Given dictionary `(a~~b)`, the contraint solver generates a given binding, just in case {{{ (cobox :: a~# b) = HEq_sc d }}} But because `cobox` is a ''coercion'' we evaluate this binding strictly, and so the desugarer produces the case expression above. Most redundant Given bindings are let-bound and hence discarded quickly by the occurrence analyser, but GHC doesn't discard cases (termination worries). So the task here is to remove the redundant Given in some way. (Of course, if the equality is actually used, we need to keep it.) NB: See `Note [The equality types story]` in `TysPrim` for the meanagerie of equality types. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 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 goldfire): How can we know, though, that the equality isn't bottom? The "simple optimizer" used to indeed throw such `case`s away, but then #11230 was reported, and I wrote 1722fa106e10e63160bb2322e2ccb830fd5b9ab3. So we should proceed carefully here. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 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): Let's leave aside the deferred-type-error case for now. Other than that, I claim that '''every evidence variable should be non- bottom''', and so * Can be evaluated strictly, and/or * Its evaluation can be discarded if its payload is not required This is true even of recursively-defined dictionaries; see `Note [Recursive superclasses]` in `TcInstDcls`. (A recursively-defined dictionary may be infinite, so you can't evaluate it hyper-strictly, but it should not be bottom.) But dictionaries still ''can'' be defined recursively (unlike say unboxed values). Now, I believe all this is true of the programs generated by source Haskell, but nothing in Core checks this invariant; and in Core you could certainly declare a bottom dictionary `(let d = d in ...)`. I don't know how to make it a statically-checkable invariant of Core, but I expect that it'd be possible to make a decent conservative approximation that was enough to capture the programs generated from source Haskell. There's even an old flag `-fdicts-strict` that I would like to get back to, which flirted with using call-by-value for evidence variables; c.f. #2436 That leaves deferred type errors. But let's not allow the tail to wag the dog. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 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 vagarenko): * cc: vagarenko (added) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 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 mpickering): * cc: mpickering (added) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 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 Iceland_jack): * cc: Iceland_jack (added) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:5> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 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 Simon Peyton Jones <simonpj@…>): In [changeset:"954cbc7c106a20639960f55ebb85c5c972652d41/ghc" 954cbc7c/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="954cbc7c106a20639960f55ebb85c5c972652d41" Drop dead Given bindings in setImplicationStatus Trac #13032 pointed out that we sometimes generate unused bindings for Givens, and (worse still) we can't always discard them later (we don't drop a case binding unless we can prove that the scrutinee is non-bottom. It looks as if this may be a major reason for the performace problems in #14338 (see comment:29). This patch fixes the problem at source, by pruning away all the dead Givens. See Note [Delete dead Given evidence bindings] Remarkably, compiler allocation falls by 23% in perf/compiler/T12227! I have not confirmed whether this change actualy helps with }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:6> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: fixed | 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 simonpj): * status: new => closed * resolution: => fixed Comment: This patch fixes the problem at source. Hooray! -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:7> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: | typecheck/should_compile/T13032 Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * testcase: => typecheck/should_compile/T13032 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: | typecheck/should_compile/T13032 Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): The test case for this ticket is unfortunate, because it fails with a DEBUG compiler (which prints out desugared code before the simple- optimizer). I don't see an easy way to fix; do you? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:9> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: | typecheck/should_compile/T13032 Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): I fixed the test case by suppressing the extra `-ddump-ds` output when `-dno-debug-output` is enabled. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:10> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: | typecheck/should_compile/T13032 Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):
I fixed the test case by suppressing the extra -ddump-ds output when -dno-debug-output is enabled.
OK. Actually it's very unsavoury that the DEBUG build changes the behaviour of `-ddump-ds`. I think it'd be better to add a flag `-ddump- ds-preopt` or something like that. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:11> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13032: Redundant forcing of Given dictionaries -------------------------------------+------------------------------------- Reporter: simonpj | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: | typecheck/should_compile/T13032 Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Simon Peyton Jones <simonpj@…>): In [changeset:"efce943ca20b55b18f948681e6b44fd892dbddd2/ghc" efce943c/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="efce943ca20b55b18f948681e6b44fd892dbddd2" Add -ddump-ds-preopt This allows you to see the output immediately after desugaring but before any optimisation. I've wanted this for some time, but I was triggered into action by Trac #13032 comment:9. Interestingly, the change means that with -dcore-lint we will now Lint the output before the very simple optimiser; and this showed up Trac #14749. But that's not the fault of -ddump-ds-preopt! }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13032#comment:12> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC