[GHC] #14088: Allow users to omit `forall`

[GHC]

#14088: Allow users to omit `forall`
-------------------------------------+-------------------------------------
        Reporter:  Iceland_jack      |                Owner:  (none)
            Type:  feature request   |               Status:  closed
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.1
      Resolution:  wontfix           |             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 Krzysztof Gogolewski <krz.gogolewski@…>):

 In [changeset:"08b3db7e670d7a142244466f1722cb48ab82f1f5/ghc"
 08b3db7e/ghc]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="08b3db7e670d7a142244466f1722cb48ab82f1f5"
 Use an accumulator version of tyCoVarsOfType

 Summary:
 This is part 1 from #14880: factor out a worker for the tyCoVarsOf...
 family of
 function, implementing them in terms of VarSet, but with accumulator-style
 (like in `FV`) built in, and with the same kind of pre-insert lookup; this
 has shown to perform better than either FV or plain VarSet in this
 particular
 scenario.

 Original notes from simonpj:

 In TyCoRep we now have tyCoVarsOfType implemented

 1) Using FV -- this is the baseline version in GHC today

 2) Using VarSets via unionVarSet

 3) Using VarSets in accumulator-style

 In this patch (3) is enabled.

 When compiling perf/compiler/T5631 we get

          Compiler allocs
    (1)   1,144M
    (2)   1,175M
    (3)   1,142M

 The key new insight in (3) is this:

   ty_co_vars_of_type (TyVarTy v) is acc
     | v `elemVarSet` is  = acc
     | v `elemVarSet` acc = acc   <---- NB!
     | otherwise          = ty_co_vars_of_type (tyVarKind v) is
 (extendVarSet acc v)

 Notice the second line! If the variable is already in the
 accumulator, don't re-add it.  This makes big difference.
 Without it, allocation is 1,169M or so.

 One cause is that we only take the free vars of its kind once;
 that problem will go away when we do the main part of #14088 and
 close over kinds /afterwards/.  But still, another cause is perhaps
 that every insert into a set overwrites the previous item, and so
 allocates a new path to the item; it's not a no-op even if the
 item is there already.

 Why use (3) rather than (1)?  Becuase it just /has/ to
 be better;

 * FV carries around an InterestingVarFun, which does nothing
   useful here, but is tested at every variable

 * FV carries around a [Var] for the deterministic version.

 For this very hot operation (finding free vars) I think it
 makes sense to have speical purpose code.

 On the way I also simplified the (less used) coVarsOfType/Co family
 to use FV, by making serious use of the InterestingVarFun!

 Test Plan: validate, nofib

 Reviewers: simonpj, bgamari

 Reviewed By: simonpj

 Subscribers: rwbarton, carter

 GHC Trac Issues: #14880

 Differential Revision: https://phabricator.haskell.org/D5141
 }}}

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