[GHC] #13032: Redundant forcing of Given dictionaries

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

[GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
#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
_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
#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
_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#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
_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #13032: Redundant forcing of Given dictionaries

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets