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

10 files changed, 214 insertions, 10 deletions

diff --git a/testsuite/tests/simplCore/should_compile/T3234.stderr b/testsuite/tests/simplCore/should_compile/T3234.stderr
index c3591d02fe..d317991925 100644
--- a/testsuite/tests/simplCore/should_compile/T3234.stderr
+++ b/testsuite/tests/simplCore/should_compile/T3234.stderr
@@ -10,7 +10,7 @@
 
 
 ==================== Grand total simplifier statistics ====================
-Total ticks:     45
+Total ticks:     46
 
 14 PreInlineUnconditionally
   1 n
@@ -37,7 +37,7 @@ Total ticks:     45
   1 foldr/single
   1 unpack
   1 unpack-list
-1 LetFloatFromLet 1
+2 LetFloatFromLet 2
 22 BetaReduction
   1 a
   1 b
diff --git a/testsuite/tests/simplCore/should_compile/T3717.stderr b/testsuite/tests/simplCore/should_compile/T3717.stderr
index 374533605e..f7fa084ef0 100644
--- a/testsuite/tests/simplCore/should_compile/T3717.stderr
+++ b/testsuite/tests/simplCore/should_compile/T3717.stderr
@@ -1,6 +1,33 @@
 
 ==================== Tidy Core ====================
-Result size of Tidy Core = {terms: 22, types: 10, coercions: 0}
+Result size of Tidy Core = {terms: 32, types: 13, coercions: 0}
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+T3717.$trModule2 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 30 20}]
+T3717.$trModule2 = TrNameS "main"#
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+T3717.$trModule1 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 40 20}]
+T3717.$trModule1 = TrNameS "T3717"#
+
+-- RHS size: {terms: 3, types: 0, coercions: 0}
+T3717.$trModule :: Module
+[GblId[ReflectionId],
+ Caf=NoCafRefs,
+ Str=DmdType m,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 30}]
+T3717.$trModule = Module T3717.$trModule2 T3717.$trModule1
 
 Rec {
 -- RHS size: {terms: 10, types: 2, coercions: 0}
diff --git a/testsuite/tests/simplCore/should_compile/T3772.stdout b/testsuite/tests/simplCore/should_compile/T3772.stdout
index e74fa39cb5..1ef8c79002 100644
--- a/testsuite/tests/simplCore/should_compile/T3772.stdout
+++ b/testsuite/tests/simplCore/should_compile/T3772.stdout
@@ -1,6 +1,6 @@
 
 ==================== Tidy Core ====================
-Result size of Tidy Core = {terms: 26, types: 11, coercions: 0}
+Result size of Tidy Core = {terms: 36, types: 14, coercions: 0}
 
 Rec {
 -- RHS size: {terms: 10, types: 2, coercions: 0}
@@ -26,5 +26,32 @@ foo =
     }
     }
 
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+T3772.$trModule1 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 40 20}]
+T3772.$trModule1 = TrNameS "T3772"#
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+T3772.$trModule2 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 30 20}]
+T3772.$trModule2 = TrNameS "main"#
+
+-- RHS size: {terms: 3, types: 0, coercions: 0}
+T3772.$trModule :: Module
+[GblId[ReflectionId],
+ Caf=NoCafRefs,
+ Str=DmdType m,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 30}]
+T3772.$trModule = Module T3772.$trModule2 T3772.$trModule1
+
 
 
diff --git a/testsuite/tests/simplCore/should_compile/T4908.stderr b/testsuite/tests/simplCore/should_compile/T4908.stderr
index 6ad89470bb..334935ddd4 100644
--- a/testsuite/tests/simplCore/should_compile/T4908.stderr
+++ b/testsuite/tests/simplCore/should_compile/T4908.stderr
@@ -1,6 +1,33 @@
 
 ==================== Tidy Core ====================
-Result size of Tidy Core = {terms: 54, types: 38, coercions: 0}
+Result size of Tidy Core = {terms: 64, types: 41, coercions: 0}
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+T4908.$trModule2 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 30 20}]
+T4908.$trModule2 = TrNameS "main"#
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+T4908.$trModule1 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 40 20}]
+T4908.$trModule1 = TrNameS "T4908"#
+
+-- RHS size: {terms: 3, types: 0, coercions: 0}
+T4908.$trModule :: Module
+[GblId[ReflectionId],
+ Caf=NoCafRefs,
+ Str=DmdType m,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 30}]
+T4908.$trModule = Module T4908.$trModule2 T4908.$trModule1
 
 Rec {
 -- RHS size: {terms: 19, types: 5, coercions: 0}
diff --git a/testsuite/tests/simplCore/should_compile/T4930.stderr b/testsuite/tests/simplCore/should_compile/T4930.stderr
index 552c8a8ddc..9f71161d14 100644
--- a/testsuite/tests/simplCore/should_compile/T4930.stderr
+++ b/testsuite/tests/simplCore/should_compile/T4930.stderr
@@ -1,6 +1,33 @@
 
 ==================== Tidy Core ====================
-Result size of Tidy Core = {terms: 35, types: 14, coercions: 0}
+Result size of Tidy Core = {terms: 45, types: 17, coercions: 0}
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+T4930.$trModule2 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 30 20}]
+T4930.$trModule2 = TrNameS "main"#
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+T4930.$trModule1 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 40 20}]
+T4930.$trModule1 = TrNameS "T4930"#
+
+-- RHS size: {terms: 3, types: 0, coercions: 0}
+T4930.$trModule :: Module
+[GblId[ReflectionId],
+ Caf=NoCafRefs,
+ Str=DmdType m,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 30}]
+T4930.$trModule = Module T4930.$trModule2 T4930.$trModule1
 
 Rec {
 -- RHS size: {terms: 23, types: 6, coercions: 0}
diff --git a/testsuite/tests/simplCore/should_compile/T7360.stderr b/testsuite/tests/simplCore/should_compile/T7360.stderr
index f7979075ac..1cd13301f9 100644
--- a/testsuite/tests/simplCore/should_compile/T7360.stderr
+++ b/testsuite/tests/simplCore/should_compile/T7360.stderr
@@ -1,6 +1,6 @@
 
 ==================== Tidy Core ====================
-Result size of Tidy Core = {terms: 36, types: 29, coercions: 0}
+Result size of Tidy Core = {terms: 55, types: 34, coercions: 0}
 
 -- RHS size: {terms: 6, types: 3, coercions: 0}
 T7360.$WFoo3 [InlPrag=INLINE] :: Int -> Foo
@@ -17,6 +17,51 @@ T7360.$WFoo3 =
   \ (dt [Occ=Once!] :: Int) ->
     case dt of _ [Occ=Dead] { I# dt [Occ=Once] -> T7360.Foo3 dt }
 
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+T7360.$trModule2 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 30 20}]
+T7360.$trModule2 = TrNameS "main"#
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+T7360.$trModule1 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 40 20}]
+T7360.$trModule1 = TrNameS "T7360"#
+
+-- RHS size: {terms: 3, types: 0, coercions: 0}
+T7360.$trModule :: Module
+[GblId[ReflectionId],
+ Caf=NoCafRefs,
+ Str=DmdType m,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 30}]
+T7360.$trModule = Module T7360.$trModule2 T7360.$trModule1
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+T7360.$tcFoo1 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 30 20}]
+T7360.$tcFoo1 = TrNameS "Foo"#
+
+-- RHS size: {terms: 5, types: 0, coercions: 0}
+T7360.$tcFoo :: TyCon
+[GblId[ReflectionId],
+ Caf=NoCafRefs,
+ Str=DmdType m,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 50}]
+T7360.$tcFoo = TyCon 0## 0## T7360.$trModule T7360.$tcFoo1
+
 -- RHS size: {terms: 5, types: 2, coercions: 0}
 fun1 [InlPrag=NOINLINE] :: Foo -> ()
 [GblId, Arity=1, Caf=NoCafRefs, Str=DmdType <S,1*U>]
diff --git a/testsuite/tests/simplCore/should_compile/T8274.stdout b/testsuite/tests/simplCore/should_compile/T8274.stdout
index 35f2412bc4..6c0e36f8f9 100644
--- a/testsuite/tests/simplCore/should_compile/T8274.stdout
+++ b/testsuite/tests/simplCore/should_compile/T8274.stdout
@@ -1,2 +1,10 @@
+T8274.$trModule2 = TrNameS "main"#
+T8274.$trModule1 = TrNameS "T8274"#
+T8274.$tcP1 = TrNameS "P"#
+    11095028091707994303##
+    9476557054198009608##
+T8274.$tcN1 = TrNameS "N"#
+    7479687563082171902##
+    17616649989360543185##
 p = T8274.Positives 42# 4.23# 4.23## '4'# 4##
 n = T8274.Negatives -4# -4.0# -4.0##
diff --git a/testsuite/tests/simplCore/should_compile/T9400.stderr b/testsuite/tests/simplCore/should_compile/T9400.stderr
index 5216d1ed5f..3bc95e42cc 100644
--- a/testsuite/tests/simplCore/should_compile/T9400.stderr
+++ b/testsuite/tests/simplCore/should_compile/T9400.stderr
@@ -1,6 +1,21 @@
 
 ==================== Tidy Core ====================
-Result size of Tidy Core = {terms: 23, types: 16, coercions: 0}
+Result size of Tidy Core = {terms: 33, types: 19, coercions: 0}
+
+-- 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 "T9400"#
+
+-- RHS size: {terms: 3, types: 0, coercions: 0}
+T9400.$trModule :: Module
+[GblId[ReflectionId], Caf=NoCafRefs, Str=DmdType]
+T9400.$trModule = Module a a1
 
 -- RHS size: {terms: 22, types: 14, coercions: 0}
 main :: IO ()
diff --git a/testsuite/tests/simplCore/should_compile/rule2.stderr b/testsuite/tests/simplCore/should_compile/rule2.stderr
index 082f9aa134..da97b8859c 100644
--- a/testsuite/tests/simplCore/should_compile/rule2.stderr
+++ b/testsuite/tests/simplCore/should_compile/rule2.stderr
@@ -10,13 +10,14 @@
 
 
 ==================== Grand total simplifier statistics ====================
-Total ticks:     12
+Total ticks:     13
 
 2 PreInlineUnconditionally
   1 f
   1 lvl
 1 UnfoldingDone 1 Roman.bar
 1 RuleFired 1 foo/bar
+1 LetFloatFromLet 1
 1 EtaReduction 1 ds
 7 BetaReduction
   1 f
diff --git a/testsuite/tests/simplCore/should_compile/spec-inline.stderr b/testsuite/tests/simplCore/should_compile/spec-inline.stderr
index 392d4fba73..7ae0e9c920 100644
--- a/testsuite/tests/simplCore/should_compile/spec-inline.stderr
+++ b/testsuite/tests/simplCore/should_compile/spec-inline.stderr
@@ -1,6 +1,33 @@
 
 ==================== Tidy Core ====================
-Result size of Tidy Core = {terms: 162, types: 61, coercions: 0}
+Result size of Tidy Core = {terms: 172, types: 64, coercions: 0}
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+Roman.$trModule2 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 30 20}]
+Roman.$trModule2 = TrNameS "main"#
+
+-- RHS size: {terms: 2, types: 0, coercions: 0}
+Roman.$trModule1 :: TrName
+[GblId,
+ Caf=NoCafRefs,
+ Str=DmdType m1,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 40 20}]
+Roman.$trModule1 = TrNameS "Roman"#
+
+-- RHS size: {terms: 3, types: 0, coercions: 0}
+Roman.$trModule :: Module
+[GblId[ReflectionId],
+ Caf=NoCafRefs,
+ Str=DmdType m,
+ Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
+         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 30}]
+Roman.$trModule = Module Roman.$trModule2 Roman.$trModule1
 
 -- RHS size: {terms: 2, types: 1, coercions: 0}
 Roman.foo3 :: Int