Generate Typeable info at definition sites

This patch implements the idea floated in Trac #9858, namely that we
should generate type-representation information at the data type
declaration site, rather than when solving a Typeable constraint.

However, this turned out quite a bit harder than I expected. I still
think it's the right thing to do, and it's done now, but it was quite
a struggle.

See particularly

 * Note [Grand plan for Typeable] in TcTypeable (which is a new module)
 * Note [The overall promotion story] in DataCon (clarifies existing stuff)

The most painful bit was that to generate Typeable instances (ie
TyConRepName bindings) for every TyCon is tricky for types in ghc-prim
etc:

 * We need to have enough data types around to *define* a TyCon
 * Many of these types are wired-in

Also, to minimise the code generated for each data type, I wanted to
generate pure data, not CAFs with unpackCString# stuff floating about.

Performance
~~~~~~~~~~~
Three perf/compiler tests start to allocate quite a bit more. This isn't
surprising, because they all allocate zillions of data types, with
practically no other code, esp. T1969

 * T3294:   GHC allocates 110% more (filed #11030 to track this)
 * T1969:   GHC allocates 30% more
 * T4801:   GHC allocates 14% more
 * T5321FD: GHC allocates 13% more
 * T783:    GHC allocates 12% more
 * T9675:   GHC allocates 12% more
 * T5642:   GHC allocates 10% more
 * T9961:   GHC allocates 6% more

 * T9203:   Program allocates 54% less

I'm treating this as acceptable. The payoff comes in Typeable-heavy
code.

Remaining to do
~~~~~~~~~~~~~~~

 * I think that "TyCon" and "Module" are over-generic names to use for
   the runtime type representations used in GHC.Typeable. Better might be
   "TrTyCon" and "TrModule". But I have not yet done this

 * Add more info the the "TyCon" e.g. source location where it was
   defined

 * Use the new "Module" type to help with Trac Trac #10068

 * It would be possible to generate TyConRepName (ie Typeable
   instances) selectively rather than all the time. We'd need to persist
   the information in interface files. Lacking a motivating reason I have
   not done this, but it would not be difficult.

Refactoring
~~~~~~~~~~~
As is so often the case, I ended up refactoring more than I intended.
In particular

 * In TyCon, a type *family* (whether type or data) is repesented by a
   FamilyTyCon
     * a algebraic data type (including data/newtype instances) is
       represented by AlgTyCon This wasn't true before; a data family
       was represented as an AlgTyCon. There are some corresponding
       changes in IfaceSyn.

     * Also get rid of the (unhelpfully named) tyConParent.

 * In TyCon define 'Promoted', isomorphic to Maybe, used when things are
   optionally promoted; and use it elsewhere in GHC.

 * Cleanup handling of knownKeyNames

 * Each TyCon, including promoted TyCons, contains its TyConRepName, if
   it has one. This is, in effect, the name of its Typeable instance.

Requires update of the haddock submodule.

Differential Revision: https://phabricator.haskell.org/D757

7 files changed, 176 insertions, 5 deletions

diff --git a/testsuite/tests/roles/should_compile/Roles1.stderr b/testsuite/tests/roles/should_compile/Roles1.stderr
index d9f9943d63..a4beb6454d 100644
--- a/testsuite/tests/roles/should_compile/Roles1.stderr
+++ b/testsuite/tests/roles/should_compile/Roles1.stderr
@@ -21,4 +21,65 @@ Dependent packages: [base-4.8.2.0, ghc-prim-0.4.0.0,
                      integer-gmp-1.0.0.0]
 
 ==================== Typechecker ====================
+Roles1.$tcT7
+  = TyCon
+      12795488517584970699##
+      6852268802866176810##
+      Roles1.$trModule
+      (TrNameS "T7"#)
+Roles1.$tcT6
+  = TyCon
+      1052116432298682626##
+      4782516991847719023##
+      Roles1.$trModule
+      (TrNameS "T6"#)
+Roles1.$tcT5
+  = TyCon
+      10855726709479635304##
+      5574528370049939204##
+      Roles1.$trModule
+      (TrNameS "T5"#)
+Roles1.$tc'K5
+  = TyCon
+      17986294396600628264##
+      15784122741796850983##
+      Roles1.$trModule
+      (TrNameS "'K5"#)
+Roles1.$tcT4
+  = TyCon
+      5809060867006837344##
+      8795972313583150301##
+      Roles1.$trModule
+      (TrNameS "T4"#)
+Roles1.$tcT3
+  = TyCon
+      17827258502042208248##
+      10404219359416482652##
+      Roles1.$trModule
+      (TrNameS "T3"#)
+Roles1.$tcT2
+  = TyCon
+      14324923875690440398##
+      17626224477681351106##
+      Roles1.$trModule
+      (TrNameS "T2"#)
+Roles1.$tc'K2
+  = TyCon
+      17795591238510508397##
+      10155757471958311507##
+      Roles1.$trModule
+      (TrNameS "'K2"#)
+Roles1.$tcT1
+  = TyCon
+      12633763300352597178##
+      11103726621424210926##
+      Roles1.$trModule
+      (TrNameS "T1"#)
+Roles1.$tc'K1
+  = TyCon
+      1949157551035372857##
+      3576433963139282451##
+      Roles1.$trModule
+      (TrNameS "'K1"#)
+Roles1.$trModule = Module (TrNameS "main"#) (TrNameS "Roles1"#)
 
diff --git a/testsuite/tests/roles/should_compile/Roles13.stderr b/testsuite/tests/roles/should_compile/Roles13.stderr
index 5ecdd16e10..4b7b2cb18d 100644
--- a/testsuite/tests/roles/should_compile/Roles13.stderr
+++ b/testsuite/tests/roles/should_compile/Roles13.stderr
@@ -1,17 +1,62 @@
 
 ==================== Tidy Core ====================
-Result size of Tidy Core = {terms: 5, types: 9, coercions: 5}
+Result size of Tidy Core = {terms: 42, types: 18, coercions: 5}
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+a :: TrName
+[GblId, Caf=NoCafRefs, Str=DmdType]
+a = TrNameS "main"#
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+a1 :: TrName
+[GblId, Caf=NoCafRefs, Str=DmdType]
+a1 = TrNameS "Roles13"#
+
+-- RHS size: {terms: 3, types: 0, coercions: 0}
+Roles13.$trModule :: Module
+[GblId[ReflectionId], Caf=NoCafRefs, Str=DmdType]
+Roles13.$trModule = Module a a1
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+a2 :: TrName
+[GblId, Caf=NoCafRefs, Str=DmdType]
+a2 = TrNameS "Age"#
+
+-- RHS size: {terms: 5, types: 0, coercions: 0}
+Roles13.$tcAge :: TyCon
+[GblId[ReflectionId], Caf=NoCafRefs, Str=DmdType]
+Roles13.$tcAge = TyCon 0## 0## Roles13.$trModule a2
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+a3 :: TrName
+[GblId, Caf=NoCafRefs, Str=DmdType]
+a3 = TrNameS "'MkWrap"#
+
+-- RHS size: {terms: 5, types: 0, coercions: 0}
+Roles13.$tc'MkWrap :: TyCon
+[GblId[ReflectionId], Caf=NoCafRefs, Str=DmdType]
+Roles13.$tc'MkWrap = TyCon 0## 0## Roles13.$trModule a3
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+a4 :: TrName
+[GblId, Caf=NoCafRefs, Str=DmdType]
+a4 = TrNameS "Wrap"#
+
+-- RHS size: {terms: 5, types: 0, coercions: 0}
+Roles13.$tcWrap :: TyCon
+[GblId[ReflectionId], Caf=NoCafRefs, Str=DmdType]
+Roles13.$tcWrap = TyCon 0## 0## Roles13.$trModule a4
 
 -- RHS size: {terms: 2, types: 2, coercions: 0}
-a :: Wrap Age -> Wrap Age
+a5 :: Wrap Age -> Wrap Age
 [GblId, Arity=1, Caf=NoCafRefs, Str=DmdType]
-a = \ (ds :: Wrap Age) -> ds
+a5 = \ (ds :: Wrap Age) -> ds
 
 -- RHS size: {terms: 1, types: 0, coercions: 5}
 convert :: Wrap Age -> Int
 [GblId, Arity=1, Caf=NoCafRefs, Str=DmdType]
 convert =
-  a
+  a5
   `cast` (<Wrap Age>_R -> Roles13.NTCo:Wrap[0] Roles13.NTCo:Age[0]
           :: (Wrap Age -> Wrap Age) ~R# (Wrap Age -> Int))
 
diff --git a/testsuite/tests/roles/should_compile/Roles14.stderr b/testsuite/tests/roles/should_compile/Roles14.stderr
index bb61133ce0..20c0bfe7a4 100644
--- a/testsuite/tests/roles/should_compile/Roles14.stderr
+++ b/testsuite/tests/roles/should_compile/Roles14.stderr
@@ -11,4 +11,11 @@ Dependent packages: [base-4.8.2.0, ghc-prim-0.4.0.0,
                      integer-gmp-1.0.0.0]
 
 ==================== Typechecker ====================
+Roles12.$tcC2
+  = TyCon
+      4006088231579841122##
+      4783761708993822739##
+      Roles12.$trModule
+      (TrNameS "C2"#)
+Roles12.$trModule = Module (TrNameS "main"#) (TrNameS "Roles12"#)
 
diff --git a/testsuite/tests/roles/should_compile/Roles2.stderr b/testsuite/tests/roles/should_compile/Roles2.stderr
index d07314379f..35895a8ae4 100644
--- a/testsuite/tests/roles/should_compile/Roles2.stderr
+++ b/testsuite/tests/roles/should_compile/Roles2.stderr
@@ -9,4 +9,17 @@ Dependent packages: [base-4.8.2.0, ghc-prim-0.4.0.0,
                      integer-gmp-1.0.0.0]
 
 ==================== Typechecker ====================
+Roles2.$tcT2
+  = TyCon
+      5934726586329293381##
+      1923031187495159753##
+      Roles2.$trModule
+      (TrNameS "T2"#)
+Roles2.$tcT1
+  = TyCon
+      13879106829711353992##
+      15151456821588362072##
+      Roles2.$trModule
+      (TrNameS "T1"#)
+Roles2.$trModule = Module (TrNameS "main"#) (TrNameS "Roles2"#)
 
diff --git a/testsuite/tests/roles/should_compile/Roles3.stderr b/testsuite/tests/roles/should_compile/Roles3.stderr
index 6f25b63691..483b349907 100644
--- a/testsuite/tests/roles/should_compile/Roles3.stderr
+++ b/testsuite/tests/roles/should_compile/Roles3.stderr
@@ -26,4 +26,29 @@ Dependent packages: [base-4.8.2.0, ghc-prim-0.4.0.0,
                      integer-gmp-1.0.0.0]
 
 ==================== Typechecker ====================
+Roles3.$tcC4
+  = TyCon
+      12861862461396457184##
+      6389612623460961504##
+      Roles3.$trModule
+      (TrNameS "C4"#)
+Roles3.$tcC3
+  = TyCon
+      5998139369941479154##
+      6816352641934636458##
+      Roles3.$trModule
+      (TrNameS "C3"#)
+Roles3.$tcC2
+  = TyCon
+      8833962732139387711##
+      7891126688522429937##
+      Roles3.$trModule
+      (TrNameS "C2"#)
+Roles3.$tcC1
+  = TyCon
+      16242970448469140073##
+      10229725431456576413##
+      Roles3.$trModule
+      (TrNameS "C1"#)
+Roles3.$trModule = Module (TrNameS "main"#) (TrNameS "Roles3"#)
 
diff --git a/testsuite/tests/roles/should_compile/Roles4.stderr b/testsuite/tests/roles/should_compile/Roles4.stderr
index 0113869e42..2c19dd29d5 100644
--- a/testsuite/tests/roles/should_compile/Roles4.stderr
+++ b/testsuite/tests/roles/should_compile/Roles4.stderr
@@ -15,4 +15,17 @@ Dependent packages: [base-4.8.2.0, ghc-prim-0.4.0.0,
                      integer-gmp-1.0.0.0]
 
 ==================== Typechecker ====================
+Roles4.$tcC3
+  = TyCon
+      16502190608089501863##
+      13971441568961069854##
+      Roles4.$trModule
+      (TrNameS "C3"#)
+Roles4.$tcC1
+  = TyCon
+      11951908835899020229##
+      6518430686554778113##
+      Roles4.$trModule
+      (TrNameS "C1"#)
+Roles4.$trModule = Module (TrNameS "main"#) (TrNameS "Roles4"#)
 
diff --git a/testsuite/tests/roles/should_compile/T8958.stderr b/testsuite/tests/roles/should_compile/T8958.stderr
index 87c3c0058e..c62d9c43dc 100644
--- a/testsuite/tests/roles/should_compile/T8958.stderr
+++ b/testsuite/tests/roles/should_compile/T8958.stderr
@@ -1,5 +1,5 @@
 
-T8958.hs:1:31: Warning:
+T8958.hs:1:31: warning:
     -XDatatypeContexts is deprecated: It was widely considered a misfeature, and has been removed from the Haskell language.
 TYPE SIGNATURES
 TYPE CONSTRUCTORS
@@ -20,6 +20,13 @@ Dependent packages: [base-4.8.2.0, ghc-prim-0.4.0.0,
                      integer-gmp-1.0.0.0]
 
 ==================== Typechecker ====================
+T8958.$tcMap = TyCon 0## 0## T8958.$trModule (TrNameS "Map"#)
+T8958.$tc'MkMap = TyCon 0## 0## T8958.$trModule (TrNameS "'MkMap"#)
+T8958.$tcRepresentational
+  = TyCon 0## 0## T8958.$trModule (TrNameS "Representational"#)
+T8958.$tcNominal
+  = TyCon 0## 0## T8958.$trModule (TrNameS "Nominal"#)
+T8958.$trModule = Module (TrNameS "main"#) (TrNameS "T8958"#)
 AbsBinds [a] []
   {Exports: [T8958.$fRepresentationala <= $dRepresentational
                <>]