compiler: Introduce and use RoughMap for instance environmentswip/roughmap-mp

Here we introduce a new data structure, RoughMap, inspired by the
previous `RoughTc` matching mechanism for checking instance matches.
This allows [Fam]InstEnv to be implemented as a trie indexed by these
RoughTc signatures, reducing the complexity of instance lookup and
FamInstEnv merging (done during the family instance conflict test)
from O(n) to O(log n).

The critical performance improvement currently realised by this patch is
in instance matching. In particular the RoughMap mechanism allows us to
discount many potential instances which will never match for constraints
involving type variables (see Note [Matching a RoughMap]). In realistic
code bases matchInstEnv was accounting for 50% of typechecker time due
to redundant work checking instances when simplifying instance contexts
when deriving instances. With this patch the cost is significantly
reduced.

The larger constants in InstEnv creation do mean that a few small
tests regress in allocations slightly. However, the runtime of T19703 is
reduced by a factor of 4. Moreover, the compilation time of the Cabal
library is slightly improved.

A couple of test cases are included which demonstrate significant
improvements in compile time with this patch.

This unfortunately does not fix the testcase provided in #19703 but does
fix #20933

-------------------------
Metric Decrease:
    T12425
Metric Increase:
    T13719
    T9872a
    T9872d
    hard_hole_fits
-------------------------

Co-authored-by: Matthew Pickering <matthewtpickering@gmail.com>

33 files changed, 270 insertions, 178 deletions

diff --git a/testsuite/tests/annotations/should_fail/annfail10.stderr b/testsuite/tests/annotations/should_fail/annfail10.stderr
index fae9f514ff..9a0272ccb1 100644
--- a/testsuite/tests/annotations/should_fail/annfail10.stderr
+++ b/testsuite/tests/annotations/should_fail/annfail10.stderr
@@ -21,6 +21,6 @@ annfail10.hs:9:11: error:
         instance Num Integer -- Defined in ‘GHC.Num’
         instance Num Double -- Defined in ‘GHC.Float’
         ...plus three others
-        ...plus 19 instances involving out-of-scope types
+        ...plus one instance involving out-of-scope types
         (use -fprint-potential-instances to see them all)
     • In the annotation: {-# ANN f 1 #-}
diff --git a/testsuite/tests/backpack/should_fail/bkpfail28.stderr b/testsuite/tests/backpack/should_fail/bkpfail28.stderr
index 7e90a61af7..a3ae2f9c28 100644
--- a/testsuite/tests/backpack/should_fail/bkpfail28.stderr
+++ b/testsuite/tests/backpack/should_fail/bkpfail28.stderr
@@ -9,20 +9,20 @@
 bkpfail28.bkp:19:13: error:
     • Overlapping instances for Show (K a) arising from a use of ‘show’
       Matching instances:
-        instance [safe] Show a => Show (K a)
-          -- Defined at bkpfail28.bkp:12:18
         instance [safe] Read a => Show (K a)
           -- Defined at bkpfail28.bkp:12:18
+        instance [safe] Show a => Show (K a)
+          -- Defined at bkpfail28.bkp:12:18
     • In the expression: show
       In an equation for ‘f’: f = show
 
 bkpfail28.bkp:21:13: error:
     • Overlapping instances for Show (K a) arising from a use of ‘show’
       Matching instances:
-        instance [safe] Show a => Show (K a)
-          -- Defined at bkpfail28.bkp:12:18
         instance [safe] Read a => Show (K a)
           -- Defined at bkpfail28.bkp:12:18
+        instance [safe] Show a => Show (K a)
+          -- Defined at bkpfail28.bkp:12:18
     • In the expression: show
       In an equation for ‘g’: g = show
   [3 of 4] Instantiating p
diff --git a/testsuite/tests/count-deps/CountDepsAst.stdout b/testsuite/tests/count-deps/CountDepsAst.stdout
index f6956a5213..3963c5eda9 100644
--- a/testsuite/tests/count-deps/CountDepsAst.stdout
+++ b/testsuite/tests/count-deps/CountDepsAst.stdout
@@ -1,4 +1,4 @@
-Found 279 Language.Haskell.Syntax module dependencies
+Found 280 Language.Haskell.Syntax module dependencies
 GHC.Builtin.Names
 GHC.Builtin.PrimOps
 GHC.Builtin.PrimOps.Ids
@@ -43,6 +43,7 @@ GHC.Core.PatSyn
 GHC.Core.Ppr
 GHC.Core.Predicate
 GHC.Core.Reduction
+GHC.Core.RoughMap
 GHC.Core.Rules
 GHC.Core.Seq
 GHC.Core.SimpleOpt
diff --git a/testsuite/tests/count-deps/CountDepsParser.stdout b/testsuite/tests/count-deps/CountDepsParser.stdout
index fd2910dc92..c86fb84f86 100644
--- a/testsuite/tests/count-deps/CountDepsParser.stdout
+++ b/testsuite/tests/count-deps/CountDepsParser.stdout
@@ -1,4 +1,4 @@
-Found 285 GHC.Parser module dependencies
+Found 286 GHC.Parser module dependencies
 GHC.Builtin.Names
 GHC.Builtin.PrimOps
 GHC.Builtin.PrimOps.Ids
@@ -43,6 +43,7 @@ GHC.Core.PatSyn
 GHC.Core.Ppr
 GHC.Core.Predicate
 GHC.Core.Reduction
+GHC.Core.RoughMap
 GHC.Core.Rules
 GHC.Core.Seq
 GHC.Core.SimpleOpt
diff --git a/testsuite/tests/driver/implicit-dyn-too/implicit-dyn-too.stdout b/testsuite/tests/driver/implicit-dyn-too/implicit-dyn-too.stdout
index f50bfcd98f..af7ea64403 100644
--- a/testsuite/tests/driver/implicit-dyn-too/implicit-dyn-too.stdout
+++ b/testsuite/tests/driver/implicit-dyn-too/implicit-dyn-too.stdout
@@ -1,3 +1,4 @@
 [1 of 2] Compiling QuasiExpr        ( QuasiExpr.hs, QuasiExpr.o, QuasiExpr.dyn_o )
 [2 of 2] Compiling QuasiQuote       ( QuasiQuote.hs, QuasiQuote.o, QuasiQuote.dyn_o )
 [1 of 2] Compiling QuasiExpr        ( QuasiExpr.hs, QuasiExpr.o, QuasiExpr.dyn_o ) [Missing dynamic object file]
+[2 of 2] Compiling QuasiQuote       ( QuasiQuote.hs, QuasiQuote.o, QuasiQuote.dyn_o ) [QuasiExpr[TH] changed]
diff --git a/testsuite/tests/ghci/T16793/T16793.stdout b/testsuite/tests/ghci/T16793/T16793.stdout
index e20747293e..c5489cb76c 100644
--- a/testsuite/tests/ghci/T16793/T16793.stdout
+++ b/testsuite/tests/ghci/T16793/T16793.stdout
@@ -1,9 +1,9 @@
-instance Eq Int -- Defined in ‘GHC.Classes’
-instance Ord Int -- Defined in ‘GHC.Classes’
+instance Bounded Int -- Defined in ‘GHC.Enum’
+instance Read Int -- Defined in ‘GHC.Read’
 instance Enum Int -- Defined in ‘GHC.Enum’
+instance Integral Int -- Defined in ‘GHC.Real’
 instance Num Int -- Defined in ‘GHC.Num’
 instance Real Int -- Defined in ‘GHC.Real’
 instance Show Int -- Defined in ‘GHC.Show’
-instance Read Int -- Defined in ‘GHC.Read’
-instance Bounded Int -- Defined in ‘GHC.Enum’
-instance Integral Int -- Defined in ‘GHC.Real’
+instance Eq Int -- Defined in ‘GHC.Classes’
+instance Ord Int -- Defined in ‘GHC.Classes’
diff --git a/testsuite/tests/ghci/T18060/T18060.stdout b/testsuite/tests/ghci/T18060/T18060.stdout
index e60b6346a4..f6a4ebb43d 100644
--- a/testsuite/tests/ghci/T18060/T18060.stdout
+++ b/testsuite/tests/ghci/T18060/T18060.stdout
@@ -2,11 +2,11 @@ type (->) :: * -> * -> *
 type (->) = FUN 'Many :: * -> * -> *
   	-- Defined in ‘GHC.Types’
 infixr -1 ->
+instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
+instance Semigroup b => Semigroup (a -> b) -- Defined in ‘GHC.Base’
 instance Applicative ((->) r) -- Defined in ‘GHC.Base’
 instance Functor ((->) r) -- Defined in ‘GHC.Base’
 instance Monad ((->) r) -- Defined in ‘GHC.Base’
-instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
-instance Semigroup b => Semigroup (a -> b) -- Defined in ‘GHC.Base’
 type (~) :: forall k. k -> k -> Constraint
 class (a ~ b) => (~) a b
   	-- Defined in ‘GHC.Types’
diff --git a/testsuite/tests/ghci/scripts/T10963.stderr b/testsuite/tests/ghci/scripts/T10963.stderr
index 23b18b29cc..c02729750c 100644
--- a/testsuite/tests/ghci/scripts/T10963.stderr
+++ b/testsuite/tests/ghci/scripts/T10963.stderr
@@ -7,6 +7,6 @@
         instance Num Integer -- Defined in ‘GHC.Num’
         instance Num Double -- Defined in ‘GHC.Float’
         ...plus three others
-        ...plus 8 instances involving out-of-scope types
+        ...plus one instance involving out-of-scope types
         (use -fprint-potential-instances to see them all)
     • In the expression: foo
diff --git a/testsuite/tests/ghci/scripts/T12550.stdout b/testsuite/tests/ghci/scripts/T12550.stdout
index a0449406f1..48a1b8e11c 100644
--- a/testsuite/tests/ghci/scripts/T12550.stdout
+++ b/testsuite/tests/ghci/scripts/T12550.stdout
@@ -23,26 +23,18 @@ class Functor f where
   (<$) ∷ ∀ a b. a → f b → f a
   {-# MINIMAL fmap #-}
   	-- Defined in ‘GHC.Base’
-instance Functor V1 -- Defined in ‘GHC.Generics’
-instance Functor (URec Char) -- Defined in ‘GHC.Generics’
-instance Functor (URec Double) -- Defined in ‘GHC.Generics’
-instance Functor (URec Float) -- Defined in ‘GHC.Generics’
-instance Functor (URec Int) -- Defined in ‘GHC.Generics’
-instance Functor (URec Word) -- Defined in ‘GHC.Generics’
-instance Functor U1 -- Defined in ‘GHC.Generics’
-instance ∀ (f ∷ ★ → ★). Functor f ⇒ Functor (Rec1 f)
-  -- Defined in ‘GHC.Generics’
-instance Functor Par1 -- Defined in ‘GHC.Generics’
-instance ∀ i (c ∷ Meta) (f ∷ ★ → ★). Functor f ⇒ Functor (M1 i c f)
-  -- Defined in ‘GHC.Generics’
-instance ∀ i c. Functor (K1 i c) -- Defined in ‘GHC.Generics’
-instance ∀ (f ∷ ★ → ★).
-         (Generic1 f, Functor (Rep1 f)) ⇒
-         Functor (Generically1 f)
-  -- Defined in ‘GHC.Generics’
+instance ∀ a. Functor ((,) a) -- Defined in ‘GHC.Base’
+instance ∀ a b. Functor ((,,) a b) -- Defined in ‘GHC.Base’
+instance ∀ a b c. Functor ((,,,) a b c) -- Defined in ‘GHC.Base’
+instance ∀ r. Functor ((->) r) -- Defined in ‘GHC.Base’
+instance Functor IO -- Defined in ‘GHC.Base’
+instance Functor Maybe -- Defined in ‘GHC.Base’
+instance Functor Solo -- Defined in ‘GHC.Base’
+instance Functor [] -- Defined in ‘GHC.Base’
+instance ∀ a. Functor (Either a) -- Defined in ‘Data.Either’
 instance ∀ (f ∷ ★ → ★) (g ∷ ★ → ★).
          (Functor f, Functor g) ⇒
-         Functor (f :.: g)
+         Functor (f :*: g)
   -- Defined in ‘GHC.Generics’
 instance ∀ (f ∷ ★ → ★) (g ∷ ★ → ★).
          (Functor f, Functor g) ⇒
@@ -50,17 +42,25 @@ instance ∀ (f ∷ ★ → ★) (g ∷ ★ → ★).
   -- Defined in ‘GHC.Generics’
 instance ∀ (f ∷ ★ → ★) (g ∷ ★ → ★).
          (Functor f, Functor g) ⇒
-         Functor (f :*: g)
+         Functor (f :.: g)
   -- Defined in ‘GHC.Generics’
-instance ∀ a. Functor (Either a) -- Defined in ‘Data.Either’
-instance Functor [] -- Defined in ‘GHC.Base’
-instance Functor Solo -- Defined in ‘GHC.Base’
-instance Functor Maybe -- Defined in ‘GHC.Base’
-instance Functor IO -- Defined in ‘GHC.Base’
-instance ∀ r. Functor ((->) r) -- Defined in ‘GHC.Base’
-instance ∀ a b c. Functor ((,,,) a b c) -- Defined in ‘GHC.Base’
-instance ∀ a b. Functor ((,,) a b) -- Defined in ‘GHC.Base’
-instance ∀ a. Functor ((,) a) -- Defined in ‘GHC.Base’
+instance ∀ (f ∷ ★ → ★).
+         (Generic1 f, Functor (Rep1 f)) ⇒
+         Functor (Generically1 f)
+  -- Defined in ‘GHC.Generics’
+instance ∀ i c. Functor (K1 i c) -- Defined in ‘GHC.Generics’
+instance ∀ i (c ∷ Meta) (f ∷ ★ → ★). Functor f ⇒ Functor (M1 i c f)
+  -- Defined in ‘GHC.Generics’
+instance Functor Par1 -- Defined in ‘GHC.Generics’
+instance ∀ (f ∷ ★ → ★). Functor f ⇒ Functor (Rec1 f)
+  -- Defined in ‘GHC.Generics’
+instance Functor U1 -- Defined in ‘GHC.Generics’
+instance Functor (URec Char) -- Defined in ‘GHC.Generics’
+instance Functor (URec Double) -- Defined in ‘GHC.Generics’
+instance Functor (URec Float) -- Defined in ‘GHC.Generics’
+instance Functor (URec Int) -- Defined in ‘GHC.Generics’
+instance Functor (URec Word) -- Defined in ‘GHC.Generics’
+instance Functor V1 -- Defined in ‘GHC.Generics’
 datatypeName
   ∷ ∀ d k1 (t ∷ ★ → (k1 → ★) → k1 → ★) (f ∷ k1 → ★) (a ∷ k1).
     Datatype d ⇒
diff --git a/testsuite/tests/ghci/scripts/T4175.stdout b/testsuite/tests/ghci/scripts/T4175.stdout
index d15ebb4ce1..7b7423ec6e 100644
--- a/testsuite/tests/ghci/scripts/T4175.stdout
+++ b/testsuite/tests/ghci/scripts/T4175.stdout
@@ -1,9 +1,9 @@
 type A :: * -> * -> *
 type family A a b
   	-- Defined at T4175.hs:8:1
-type instance A (Maybe a) a = a 	-- Defined at T4175.hs:10:15
-type instance A Int Int = () 	-- Defined at T4175.hs:9:15
 type instance A (B a) b = () 	-- Defined at T4175.hs:11:15
+type instance A Int Int = () 	-- Defined at T4175.hs:9:15
+type instance A (Maybe a) a = a 	-- Defined at T4175.hs:10:15
 type B :: * -> *
 data family B a
   	-- Defined at T4175.hs:13:1
@@ -15,8 +15,8 @@ class C a where
   type D :: * -> * -> *
   type family D a b
   	-- Defined at T4175.hs:17:5
-type instance D () () = Bool 	-- Defined at T4175.hs:23:10
 type instance D Int () = String 	-- Defined at T4175.hs:20:10
+type instance D () () = Bool 	-- Defined at T4175.hs:23:10
 type E :: * -> *
 type family E a where
     E () = Bool
@@ -26,47 +26,47 @@ type () :: *
 data () = ()
   	-- Defined in ‘GHC.Tuple’
 instance [safe] C () -- Defined at T4175.hs:22:10
-instance Eq () -- Defined in ‘GHC.Classes’
 instance Monoid () -- Defined in ‘GHC.Base’
-instance Ord () -- Defined in ‘GHC.Classes’
 instance Semigroup () -- Defined in ‘GHC.Base’
+instance Bounded () -- Defined in ‘GHC.Enum’
 instance Enum () -- Defined in ‘GHC.Enum’
-instance Show () -- Defined in ‘GHC.Show’
+instance Eq () -- Defined in ‘GHC.Classes’
+instance Ord () -- Defined in ‘GHC.Classes’
 instance Read () -- Defined in ‘GHC.Read’
-instance Bounded () -- Defined in ‘GHC.Enum’
+instance Show () -- Defined in ‘GHC.Show’
 data instance B () = MkB 	-- Defined at T4175.hs:14:15
-type instance D () () = Bool 	-- Defined at T4175.hs:23:10
 type instance D Int () = String 	-- Defined at T4175.hs:20:10
+type instance D () () = Bool 	-- Defined at T4175.hs:23:10
 type Maybe :: * -> *
 data Maybe a = Nothing | Just a
   	-- Defined in ‘GHC.Maybe’
+instance Traversable Maybe -- Defined in ‘Data.Traversable’
+instance Foldable Maybe -- Defined in ‘Data.Foldable’
 instance Applicative Maybe -- Defined in ‘GHC.Base’
-instance Eq a => Eq (Maybe a) -- Defined in ‘GHC.Maybe’
 instance Functor Maybe -- Defined in ‘GHC.Base’
+instance MonadFail Maybe -- Defined in ‘Control.Monad.Fail’
 instance Monad Maybe -- Defined in ‘GHC.Base’
 instance Semigroup a => Monoid (Maybe a) -- Defined in ‘GHC.Base’
-instance Ord a => Ord (Maybe a) -- Defined in ‘GHC.Maybe’
 instance Semigroup a => Semigroup (Maybe a)
   -- Defined in ‘GHC.Base’
-instance Show a => Show (Maybe a) -- Defined in ‘GHC.Show’
-instance MonadFail Maybe -- Defined in ‘Control.Monad.Fail’
+instance Eq a => Eq (Maybe a) -- Defined in ‘GHC.Maybe’
+instance Ord a => Ord (Maybe a) -- Defined in ‘GHC.Maybe’
 instance Read a => Read (Maybe a) -- Defined in ‘GHC.Read’
-instance Foldable Maybe -- Defined in ‘Data.Foldable’
-instance Traversable Maybe -- Defined in ‘Data.Traversable’
+instance Show a => Show (Maybe a) -- Defined in ‘GHC.Show’
 type instance A (Maybe a) a = a 	-- Defined at T4175.hs:10:15
 type Int :: *
 data Int = GHC.Types.I# GHC.Prim.Int#
   	-- Defined in ‘GHC.Types’
 instance [safe] C Int -- Defined at T4175.hs:19:10
-instance Eq Int -- Defined in ‘GHC.Classes’
-instance Ord Int -- Defined in ‘GHC.Classes’
-instance Enum Int -- Defined in ‘GHC.Enum’
+instance Integral Int -- Defined in ‘GHC.Real’
 instance Num Int -- Defined in ‘GHC.Num’
 instance Real Int -- Defined in ‘GHC.Real’
-instance Show Int -- Defined in ‘GHC.Show’
-instance Read Int -- Defined in ‘GHC.Read’
 instance Bounded Int -- Defined in ‘GHC.Enum’
-instance Integral Int -- Defined in ‘GHC.Real’
+instance Enum Int -- Defined in ‘GHC.Enum’
+instance Eq Int -- Defined in ‘GHC.Classes’
+instance Ord Int -- Defined in ‘GHC.Classes’
+instance Read Int -- Defined in ‘GHC.Read’
+instance Show Int -- Defined in ‘GHC.Show’
 type instance A Int Int = () 	-- Defined at T4175.hs:9:15
 type instance D Int () = String 	-- Defined at T4175.hs:20:10
 type Z :: * -> Constraint
diff --git a/testsuite/tests/ghci/scripts/T7627.stdout b/testsuite/tests/ghci/scripts/T7627.stdout
index 0bc51c87b5..a304546e0f 100644
--- a/testsuite/tests/ghci/scripts/T7627.stdout
+++ b/testsuite/tests/ghci/scripts/T7627.stdout
@@ -1,14 +1,14 @@
 type () :: *
 data () = ()
   	-- Defined in ‘GHC.Tuple’
-instance Eq () -- Defined in ‘GHC.Classes’
 instance Monoid () -- Defined in ‘GHC.Base’
-instance Ord () -- Defined in ‘GHC.Classes’
 instance Semigroup () -- Defined in ‘GHC.Base’
+instance Bounded () -- Defined in ‘GHC.Enum’
+instance Read () -- Defined in ‘GHC.Read’
 instance Enum () -- Defined in ‘GHC.Enum’
 instance Show () -- Defined in ‘GHC.Show’
-instance Read () -- Defined in ‘GHC.Read’
-instance Bounded () -- Defined in ‘GHC.Enum’
+instance Eq () -- Defined in ‘GHC.Classes’
+instance Ord () -- Defined in ‘GHC.Classes’
 type (##) :: GHC.Types.ZeroBitType
 data (##) = (##)
   	-- Defined in ‘GHC.Prim’
@@ -19,21 +19,21 @@ data (##) = (##)
 type (,) :: * -> * -> *
 data (,) a b = (,) a b
   	-- Defined in ‘GHC.Tuple’
-instance Monoid a => Applicative ((,) a) -- Defined in ‘GHC.Base’
-instance (Eq a, Eq b) => Eq (a, b) -- Defined in ‘GHC.Classes’
-instance Functor ((,) a) -- Defined in ‘GHC.Base’
-instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
+instance Traversable ((,) a) -- Defined in ‘Data.Traversable’
 instance (Monoid a, Monoid b) => Monoid (a, b)
   -- Defined in ‘GHC.Base’
-instance (Ord a, Ord b) => Ord (a, b) -- Defined in ‘GHC.Classes’
 instance (Semigroup a, Semigroup b) => Semigroup (a, b)
   -- Defined in ‘GHC.Base’
-instance (Show a, Show b) => Show (a, b) -- Defined in ‘GHC.Show’
-instance (Read a, Read b) => Read (a, b) -- Defined in ‘GHC.Read’
 instance Foldable ((,) a) -- Defined in ‘Data.Foldable’
-instance Traversable ((,) a) -- Defined in ‘Data.Traversable’
 instance (Bounded a, Bounded b) => Bounded (a, b)
   -- Defined in ‘GHC.Enum’
+instance (Eq a, Eq b) => Eq (a, b) -- Defined in ‘GHC.Classes’
+instance (Ord a, Ord b) => Ord (a, b) -- Defined in ‘GHC.Classes’
+instance (Read a, Read b) => Read (a, b) -- Defined in ‘GHC.Read’
+instance (Show a, Show b) => Show (a, b) -- Defined in ‘GHC.Show’
+instance Monoid a => Applicative ((,) a) -- Defined in ‘GHC.Base’
+instance Functor ((,) a) -- Defined in ‘GHC.Base’
+instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
 type (#,#) :: *
               -> *
               -> TYPE
diff --git a/testsuite/tests/ghci/scripts/T8469.stdout b/testsuite/tests/ghci/scripts/T8469.stdout
index 7cad316fee..8442b050be 100644
--- a/testsuite/tests/ghci/scripts/T8469.stdout
+++ b/testsuite/tests/ghci/scripts/T8469.stdout
@@ -1,12 +1,12 @@
 type Int :: *
 data Int = GHC.Types.I# GHC.Prim.Int#
   	-- Defined in ‘GHC.Types’
-instance Eq Int -- Defined in ‘GHC.Classes’
-instance Ord Int -- Defined in ‘GHC.Classes’
+instance Bounded Int -- Defined in ‘GHC.Enum’
+instance Read Int -- Defined in ‘GHC.Read’
 instance Enum Int -- Defined in ‘GHC.Enum’
+instance Integral Int -- Defined in ‘GHC.Real’
 instance Num Int -- Defined in ‘GHC.Num’
 instance Real Int -- Defined in ‘GHC.Real’
 instance Show Int -- Defined in ‘GHC.Show’
-instance Read Int -- Defined in ‘GHC.Read’
-instance Bounded Int -- Defined in ‘GHC.Enum’
-instance Integral Int -- Defined in ‘GHC.Real’
+instance Eq Int -- Defined in ‘GHC.Classes’
+instance Ord Int -- Defined in ‘GHC.Classes’
diff --git a/testsuite/tests/ghci/scripts/T8535.stdout b/testsuite/tests/ghci/scripts/T8535.stdout
index 5786372e9d..c6625fbcb8 100644
--- a/testsuite/tests/ghci/scripts/T8535.stdout
+++ b/testsuite/tests/ghci/scripts/T8535.stdout
@@ -2,8 +2,8 @@ type (->) :: * -> * -> *
 type (->) = FUN 'Many :: * -> * -> *
   	-- Defined in ‘GHC.Types’
 infixr -1 ->
+instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
+instance Semigroup b => Semigroup (a -> b) -- Defined in ‘GHC.Base’
 instance Applicative ((->) r) -- Defined in ‘GHC.Base’
 instance Functor ((->) r) -- Defined in ‘GHC.Base’
 instance Monad ((->) r) -- Defined in ‘GHC.Base’
-instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
-instance Semigroup b => Semigroup (a -> b) -- Defined in ‘GHC.Base’
diff --git a/testsuite/tests/ghci/scripts/T8674.stdout b/testsuite/tests/ghci/scripts/T8674.stdout
index 7d7beeb1cd..f8175e9c75 100644
--- a/testsuite/tests/ghci/scripts/T8674.stdout
+++ b/testsuite/tests/ghci/scripts/T8674.stdout
@@ -1,6 +1,6 @@
 type Sing :: forall k. k -> *
 data family Sing a
   	-- Defined at T8674.hs:4:1
-data instance Sing Bool = SBool 	-- Defined at T8674.hs:6:15
 data instance forall k (a :: [k]). Sing a = SNil
   	-- Defined at T8674.hs:5:15
+data instance Sing Bool = SBool 	-- Defined at T8674.hs:6:15
diff --git a/testsuite/tests/ghci/scripts/T9881.stdout b/testsuite/tests/ghci/scripts/T9881.stdout
index 45e3de396a..c779c1fa47 100644
--- a/testsuite/tests/ghci/scripts/T9881.stdout
+++ b/testsuite/tests/ghci/scripts/T9881.stdout
@@ -4,17 +4,17 @@ data Data.ByteString.Lazy.ByteString
   | Data.ByteString.Lazy.Internal.Chunk {-# UNPACK #-}Data.ByteString.ByteString
                                         Data.ByteString.Lazy.ByteString
   	-- Defined in ‘Data.ByteString.Lazy.Internal’
-instance Eq Data.ByteString.Lazy.ByteString
-  -- Defined in ‘Data.ByteString.Lazy.Internal’
 instance Monoid Data.ByteString.Lazy.ByteString
   -- Defined in ‘Data.ByteString.Lazy.Internal’
-instance Ord Data.ByteString.Lazy.ByteString
+instance Read Data.ByteString.Lazy.ByteString
   -- Defined in ‘Data.ByteString.Lazy.Internal’
 instance Semigroup Data.ByteString.Lazy.ByteString
   -- Defined in ‘Data.ByteString.Lazy.Internal’
 instance Show Data.ByteString.Lazy.ByteString
   -- Defined in ‘Data.ByteString.Lazy.Internal’
-instance Read Data.ByteString.Lazy.ByteString
+instance Eq Data.ByteString.Lazy.ByteString
+  -- Defined in ‘Data.ByteString.Lazy.Internal’
+instance Ord Data.ByteString.Lazy.ByteString
   -- Defined in ‘Data.ByteString.Lazy.Internal’
 
 type Data.ByteString.ByteString :: *
@@ -23,15 +23,15 @@ data Data.ByteString.ByteString
                                                  GHC.Word.Word8)
                                 {-# UNPACK #-}Int
   	-- Defined in ‘Data.ByteString.Internal’
-instance Eq Data.ByteString.ByteString
-  -- Defined in ‘Data.ByteString.Internal’
 instance Monoid Data.ByteString.ByteString
   -- Defined in ‘Data.ByteString.Internal’
-instance Ord Data.ByteString.ByteString
+instance Read Data.ByteString.ByteString
   -- Defined in ‘Data.ByteString.Internal’
 instance Semigroup Data.ByteString.ByteString
   -- Defined in ‘Data.ByteString.Internal’
 instance Show Data.ByteString.ByteString
   -- Defined in ‘Data.ByteString.Internal’
-instance Read Data.ByteString.ByteString
+instance Eq Data.ByteString.ByteString
+  -- Defined in ‘Data.ByteString.Internal’
+instance Ord Data.ByteString.ByteString
   -- Defined in ‘Data.ByteString.Internal’
diff --git a/testsuite/tests/ghci/scripts/ghci008.stdout b/testsuite/tests/ghci/scripts/ghci008.stdout
index 3f62f3f7f2..925ec3874f 100644
--- a/testsuite/tests/ghci/scripts/ghci008.stdout
+++ b/testsuite/tests/ghci/scripts/ghci008.stdout
@@ -38,7 +38,7 @@ class (RealFrac a, Floating a) => RealFloat a where
               encodeFloat, isNaN, isInfinite, isDenormalized, isNegativeZero,
               isIEEE #-}
   	-- Defined in ‘GHC.Float’
-instance RealFloat Float -- Defined in ‘GHC.Float’
 instance RealFloat Double -- Defined in ‘GHC.Float’
-base-4.13.0.0:Data.OldList.isPrefixOf :: Eq a => [a] -> [a] -> Bool
-  	-- Defined in ‘base-4.13.0.0:Data.OldList’
+instance RealFloat Float -- Defined in ‘GHC.Float’
+base-4.16.0.0:Data.OldList.isPrefixOf :: Eq a => [a] -> [a] -> Bool
+  	-- Defined in ‘base-4.16.0.0:Data.OldList’
diff --git a/testsuite/tests/ghci/scripts/ghci011.stdout b/testsuite/tests/ghci/scripts/ghci011.stdout
index 35f4b9fda2..10fd9bc264 100644
--- a/testsuite/tests/ghci/scripts/ghci011.stdout
+++ b/testsuite/tests/ghci/scripts/ghci011.stdout
@@ -1,44 +1,44 @@
 type [] :: * -> *
 data [] a = [] | a : [a]
   	-- Defined in ‘GHC.Types’
-instance Applicative [] -- Defined in ‘GHC.Base’
-instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
-instance Functor [] -- Defined in ‘GHC.Base’
-instance Monad [] -- Defined in ‘GHC.Base’
 instance Monoid [a] -- Defined in ‘GHC.Base’
-instance Ord a => Ord [a] -- Defined in ‘GHC.Classes’
 instance Semigroup [a] -- Defined in ‘GHC.Base’
-instance Show a => Show [a] -- Defined in ‘GHC.Show’
-instance MonadFail [] -- Defined in ‘Control.Monad.Fail’
-instance Read a => Read [a] -- Defined in ‘GHC.Read’
 instance Foldable [] -- Defined in ‘Data.Foldable’
 instance Traversable [] -- Defined in ‘Data.Traversable’
+instance Read a => Read [a] -- Defined in ‘GHC.Read’
+instance Show a => Show [a] -- Defined in ‘GHC.Show’
+instance Applicative [] -- Defined in ‘GHC.Base’
+instance Functor [] -- Defined in ‘GHC.Base’
+instance MonadFail [] -- Defined in ‘Control.Monad.Fail’
+instance Monad [] -- Defined in ‘GHC.Base’
+instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
+instance Ord a => Ord [a] -- Defined in ‘GHC.Classes’
 type () :: *
 data () = ()
   	-- Defined in ‘GHC.Tuple’
-instance Eq () -- Defined in ‘GHC.Classes’
 instance Monoid () -- Defined in ‘GHC.Base’
-instance Ord () -- Defined in ‘GHC.Classes’
 instance Semigroup () -- Defined in ‘GHC.Base’
-instance Enum () -- Defined in ‘GHC.Enum’
-instance Show () -- Defined in ‘GHC.Show’
 instance Read () -- Defined in ‘GHC.Read’
 instance Bounded () -- Defined in ‘GHC.Enum’
+instance Enum () -- Defined in ‘GHC.Enum’
+instance Ord () -- Defined in ‘GHC.Classes’
+instance Show () -- Defined in ‘GHC.Show’
+instance Eq () -- Defined in ‘GHC.Classes’
 type (,) :: * -> * -> *
 data (,) a b = (,) a b
   	-- Defined in ‘GHC.Tuple’
-instance Monoid a => Applicative ((,) a) -- Defined in ‘GHC.Base’
-instance (Eq a, Eq b) => Eq (a, b) -- Defined in ‘GHC.Classes’
-instance Functor ((,) a) -- Defined in ‘GHC.Base’
-instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
+instance Traversable ((,) a) -- Defined in ‘Data.Traversable’
 instance (Monoid a, Monoid b) => Monoid (a, b)
   -- Defined in ‘GHC.Base’
-instance (Ord a, Ord b) => Ord (a, b) -- Defined in ‘GHC.Classes’
 instance (Semigroup a, Semigroup b) => Semigroup (a, b)
   -- Defined in ‘GHC.Base’
-instance (Show a, Show b) => Show (a, b) -- Defined in ‘GHC.Show’
-instance (Read a, Read b) => Read (a, b) -- Defined in ‘GHC.Read’
 instance Foldable ((,) a) -- Defined in ‘Data.Foldable’
-instance Traversable ((,) a) -- Defined in ‘Data.Traversable’
 instance (Bounded a, Bounded b) => Bounded (a, b)
   -- Defined in ‘GHC.Enum’
+instance (Eq a, Eq b) => Eq (a, b) -- Defined in ‘GHC.Classes’
+instance (Ord a, Ord b) => Ord (a, b) -- Defined in ‘GHC.Classes’
+instance (Read a, Read b) => Read (a, b) -- Defined in ‘GHC.Read’
+instance (Show a, Show b) => Show (a, b) -- Defined in ‘GHC.Show’
+instance Monoid a => Applicative ((,) a) -- Defined in ‘GHC.Base’
+instance Functor ((,) a) -- Defined in ‘GHC.Base’
+instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
diff --git a/testsuite/tests/ghci/scripts/ghci020.stdout b/testsuite/tests/ghci/scripts/ghci020.stdout
index 5786372e9d..c6625fbcb8 100644
--- a/testsuite/tests/ghci/scripts/ghci020.stdout
+++ b/testsuite/tests/ghci/scripts/ghci020.stdout
@@ -2,8 +2,8 @@ type (->) :: * -> * -> *
 type (->) = FUN 'Many :: * -> * -> *
   	-- Defined in ‘GHC.Types’
 infixr -1 ->
+instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
+instance Semigroup b => Semigroup (a -> b) -- Defined in ‘GHC.Base’
 instance Applicative ((->) r) -- Defined in ‘GHC.Base’
 instance Functor ((->) r) -- Defined in ‘GHC.Base’
 instance Monad ((->) r) -- Defined in ‘GHC.Base’
-instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
-instance Semigroup b => Semigroup (a -> b) -- Defined in ‘GHC.Base’
diff --git a/testsuite/tests/ghci/scripts/ghci044.stderr b/testsuite/tests/ghci/scripts/ghci044.stderr
index 716f46e12e..668388dea8 100644
--- a/testsuite/tests/ghci/scripts/ghci044.stderr
+++ b/testsuite/tests/ghci/scripts/ghci044.stderr
@@ -2,7 +2,7 @@
 <interactive>:9:1: error:
     • Overlapping instances for C [Int] arising from a use of ‘f’
       Matching instances:
-        instance [safe] C [Int] -- Defined at <interactive>:6:10
         instance [safe] C a => C [a] -- Defined at <interactive>:8:10
+        instance [safe] C [Int] -- Defined at <interactive>:6:10
     • In the expression: f [4 :: Int]
       In an equation for ‘it’: it = f [4 :: Int]
diff --git a/testsuite/tests/ghci/scripts/ghci064.stdout b/testsuite/tests/ghci/scripts/ghci064.stdout
index b3437226ca..2d1bb17423 100644
--- a/testsuite/tests/ghci/scripts/ghci064.stdout
+++ b/testsuite/tests/ghci/scripts/ghci064.stdout
@@ -1,47 +1,49 @@
+instance Foldable Maybe -- Defined in ‘Data.Foldable’
+instance Traversable Maybe -- Defined in ‘Data.Traversable’
 instance GHC.Base.Alternative Maybe -- Defined in ‘GHC.Base’
 instance Applicative Maybe -- Defined in ‘GHC.Base’
 instance Functor Maybe -- Defined in ‘GHC.Base’
-instance Monad Maybe -- Defined in ‘GHC.Base’
-instance GHC.Base.MonadPlus Maybe -- Defined in ‘GHC.Base’
 instance MonadFail Maybe -- Defined in ‘Control.Monad.Fail’
-instance Foldable Maybe -- Defined in ‘Data.Foldable’
-instance Traversable Maybe -- Defined in ‘Data.Traversable’
-instance Eq w => Eq (Maybe w) -- Defined in ‘GHC.Maybe’
+instance GHC.Base.MonadPlus Maybe -- Defined in ‘GHC.Base’
+instance Monad Maybe -- Defined in ‘GHC.Base’
+instance GHC.Generics.SingKind w => GHC.Generics.SingKind (Maybe w)
+  -- Defined in ‘GHC.Generics’
 instance Semigroup w => Monoid (Maybe w) -- Defined in ‘GHC.Base’
-instance Ord w => Ord (Maybe w) -- Defined in ‘GHC.Maybe’
 instance Semigroup w => Semigroup (Maybe w)
   -- Defined in ‘GHC.Base’
-instance Show w => Show (Maybe w) -- Defined in ‘GHC.Show’
-instance Read w => Read (Maybe w) -- Defined in ‘GHC.Read’
 instance GHC.Generics.Generic (Maybe w)
   -- Defined in ‘GHC.Generics’
-instance GHC.Generics.SingKind w => GHC.Generics.SingKind (Maybe w)
-  -- Defined in ‘GHC.Generics’
-instance Eq w => Eq [w] -- Defined in ‘GHC.Classes’
+instance Read w => Read (Maybe w) -- Defined in ‘GHC.Read’
+instance Ord w => Ord (Maybe w) -- Defined in ‘GHC.Maybe’
+instance Show w => Show (Maybe w) -- Defined in ‘GHC.Show’
+instance Eq w => Eq (Maybe w) -- Defined in ‘GHC.Maybe’
 instance Monoid [w] -- Defined in ‘GHC.Base’
-instance Ord w => Ord [w] -- Defined in ‘GHC.Classes’
 instance Semigroup [w] -- Defined in ‘GHC.Base’
-instance Show w => Show [w] -- Defined in ‘GHC.Show’
 instance Read w => Read [w] -- Defined in ‘GHC.Read’
 instance GHC.Generics.Generic [w] -- Defined in ‘GHC.Generics’
+instance Eq w => Eq [w] -- Defined in ‘GHC.Classes’
+instance Ord w => Ord [w] -- Defined in ‘GHC.Classes’
+instance Show w => Show [w] -- Defined in ‘GHC.Show’
 instance [safe] MyShow w => MyShow [w]
   -- Defined at ghci064.hs:8:10
+instance GHC.Generics.Generic [T] -- Defined in ‘GHC.Generics’
 instance Monoid [T] -- Defined in ‘GHC.Base’
 instance Semigroup [T] -- Defined in ‘GHC.Base’
-instance GHC.Generics.Generic [T] -- Defined in ‘GHC.Generics’
-instance [safe] MyShow [T] -- Defined at ghci064.hs:16:10
 instance [safe] MyShow [T] -- Defined at ghci064.hs:8:10
-instance Eq Bool -- Defined in ‘GHC.Classes’
-instance Ord Bool -- Defined in ‘GHC.Classes’
-instance Enum Bool -- Defined in ‘GHC.Enum’
-instance Show Bool -- Defined in ‘GHC.Show’
-instance Read Bool -- Defined in ‘GHC.Read’
-instance Bounded Bool -- Defined in ‘GHC.Enum’
-instance GHC.Generics.Generic Bool -- Defined in ‘GHC.Generics’
-instance GHC.Ix.Ix Bool -- Defined in ‘GHC.Ix’
+instance [safe] MyShow [T] -- Defined at ghci064.hs:16:10
 instance GHC.Generics.SingKind Bool -- Defined in ‘GHC.Generics’
+instance Foreign.Storable.Storable Bool
+  -- Defined in ‘Foreign.Storable’
+instance GHC.Generics.Generic Bool -- Defined in ‘GHC.Generics’
 instance GHC.Bits.Bits Bool -- Defined in ‘GHC.Bits’
 instance GHC.Bits.FiniteBits Bool -- Defined in ‘GHC.Bits’
-instance Functor ((,) Int) -- Defined in ‘GHC.Base’
-instance Foldable ((,) Int) -- Defined in ‘Data.Foldable’
+instance GHC.Ix.Ix Bool -- Defined in ‘GHC.Ix’
+instance Bounded Bool -- Defined in ‘GHC.Enum’
+instance Enum Bool -- Defined in ‘GHC.Enum’
+instance Eq Bool -- Defined in ‘GHC.Classes’
+instance Ord Bool -- Defined in ‘GHC.Classes’
+instance Read Bool -- Defined in ‘GHC.Read’
+instance Show Bool -- Defined in ‘GHC.Show’
 instance Traversable ((,) Int) -- Defined in ‘Data.Traversable’
+instance Foldable ((,) Int) -- Defined in ‘Data.Foldable’
+instance Functor ((,) Int) -- Defined in ‘GHC.Base’
diff --git a/testsuite/tests/ghci/should_run/T10145.stdout b/testsuite/tests/ghci/should_run/T10145.stdout
index 5786372e9d..c6625fbcb8 100644
--- a/testsuite/tests/ghci/should_run/T10145.stdout
+++ b/testsuite/tests/ghci/should_run/T10145.stdout
@@ -2,8 +2,8 @@ type (->) :: * -> * -> *
 type (->) = FUN 'Many :: * -> * -> *
   	-- Defined in ‘GHC.Types’
 infixr -1 ->
+instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
+instance Semigroup b => Semigroup (a -> b) -- Defined in ‘GHC.Base’
 instance Applicative ((->) r) -- Defined in ‘GHC.Base’
 instance Functor ((->) r) -- Defined in ‘GHC.Base’
 instance Monad ((->) r) -- Defined in ‘GHC.Base’
-instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
-instance Semigroup b => Semigroup (a -> b) -- Defined in ‘GHC.Base’
diff --git a/testsuite/tests/ghci/should_run/T18594.stdout b/testsuite/tests/ghci/should_run/T18594.stdout
index d3219de45e..1c6c93ad7a 100644
--- a/testsuite/tests/ghci/should_run/T18594.stdout
+++ b/testsuite/tests/ghci/should_run/T18594.stdout
@@ -2,11 +2,11 @@ type (->) :: * -> * -> *
 type (->) = FUN 'Many :: * -> * -> *
   	-- Defined in ‘GHC.Types’
 infixr -1 ->
+instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
+instance Semigroup b => Semigroup (a -> b) -- Defined in ‘GHC.Base’
 instance Applicative ((->) r) -- Defined in ‘GHC.Base’
 instance Functor ((->) r) -- Defined in ‘GHC.Base’
 instance Monad ((->) r) -- Defined in ‘GHC.Base’
-instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
-instance Semigroup b => Semigroup (a -> b) -- Defined in ‘GHC.Base’
 type Type :: *
 type Type = TYPE LiftedRep
   	-- Defined in ‘GHC.Types’
diff --git a/testsuite/tests/perf/compiler/InstanceMatching.stderr b/testsuite/tests/perf/compiler/InstanceMatching.stderr
new file mode 100644
index 0000000000..f4e978cf2e
--- /dev/null
+++ b/testsuite/tests/perf/compiler/InstanceMatching.stderr
@@ -0,0 +1,5 @@
+
+Match.hs:1006:1: error:
+    • No instance for (Show (F001 a)) arising from a use of ‘showsPrec’
+    • In the first argument of ‘(.)’, namely ‘(showsPrec 11 b1)’
+      In the second argument of ‘(.)’, namely
diff --git a/testsuite/tests/perf/compiler/Makefile b/testsuite/tests/perf/compiler/Makefile
index 0011c70710..33d2878db7 100644
--- a/testsuite/tests/perf/compiler/Makefile
+++ b/testsuite/tests/perf/compiler/Makefile
@@ -28,3 +28,8 @@ MultiLayerModulesTH_Make_Prep:
 MultiLayerModulesTH_OneShot_Prep: MultiLayerModulesTH_Make_Prep
 	$(CP) MultiLayerModules.hs MultiLayerModulesTH_OneShot.hs
 
+# Type family skolems
+InstanceMatching:
+	./genMatchingTest 0
+	'$(TEST_HC)' $(TEST_HC_OPTS) -fno-code -fwrite-interface Defs.hs
+
diff --git a/testsuite/tests/perf/compiler/all.T b/testsuite/tests/perf/compiler/all.T
index 4136572419..532db501e6 100644
--- a/testsuite/tests/perf/compiler/all.T
+++ b/testsuite/tests/perf/compiler/all.T
@@ -282,6 +282,7 @@ test('MultiLayerModules',
      multimod_compile,
      ['MultiLayerModules', '-v0'])
 
+
 # MultiLayerModules flip flops by 2.5%, depending on the
 # number of modules within GHC (#19293). Just widen the
 # acceptance window until we figured out how to fix it.
@@ -334,6 +335,30 @@ test('MultiLayerModulesDefsGhci',
      ghci_script,
      ['MultiLayerModulesDefsGhci.script'])
 
+test('InstanceMatching',
+     [ collect_compiler_stats('bytes allocated',3),
+       pre_cmd('$MAKE -s --no-print-directory InstanceMatching'),
+       extra_files(['genMatchingTest']),
+       compile_timeout_multiplier(5),
+       grep_errmsg('F001')],
+     multimod_compile_fail,
+     ['Match', '-fno-code -fwrite-interface -v0'])
+
+# This module stresses the KnownTC and NoKnownTC (skolem variable) cases
+test('InstanceMatching1',
+     [ collect_compiler_stats('bytes allocated',3),
+       pre_cmd('./genMatchingTest 1'),
+       extra_files(['genMatchingTest']),
+       compile_timeout_multiplier(5)
+       # this is _a lot_
+       # but this test has been failing every now and then,
+       # especially on i386. Let's just give it some room
+       # to complete successfully reliably everywhere.
+     ],
+     multimod_compile,
+     ['Defs', '-fno-code -fwrite-interface -v0'])
+
+
 test('MultiLayerModulesNoCode',
      [ collect_compiler_residency(15),
        pre_cmd('./genMultiLayerModulesNoCode'),
@@ -558,7 +583,7 @@ test('hard_hole_fits', # Testing multiple hole-fits with lots in scope for #1687
 test('T16875',  # Testing one hole-fit with a lot in scope for #16875
      collect_compiler_stats('bytes allocated', 2),
      compile, ['-fdefer-type-errors -fno-max-valid-hole-fits -package ghc'])
-test ('T20261', 
+test ('T20261',
       [collect_compiler_stats('all')],
       compile,
       [''])
diff --git a/testsuite/tests/perf/compiler/genMatchingTest b/testsuite/tests/perf/compiler/genMatchingTest
new file mode 100755
index 0000000000..9356d9028a
--- /dev/null
+++ b/testsuite/tests/perf/compiler/genMatchingTest
@@ -0,0 +1,52 @@
+#!/usr/bin/env bash
+# Generate a module with N data types and instances
+DEFS=10000
+MATCHES=500
+MODE=$1
+echo "module Defs where" > Defs.hs;
+for i in $(seq -w 1 $DEFS); do
+  echo "data T$i a = T$i a deriving Show" >> Defs.hs;
+done
+
+echo "{-# LANGUAGE TypeFamilies #-}" > Match.hs
+echo "{-# LANGUAGE StandaloneDeriving #-}" >> Match.hs
+echo "{-# LANGUAGE EmptyDataDecls #-}" >> Match.hs
+echo "module Match where" >> Match.hs
+echo "import Defs" >> Match.hs
+
+if [ $MODE -eq 0 ]; then
+  for i in $(seq -w 1 $MATCHES); do
+    echo "type family F$i a where" >> Match.hs;
+  done
+  echo "data T a = T" >> Match.hs
+  for i in $(seq -w 1 $MATCHES); do
+    echo "       (F$i a)" >> Match.hs;
+  done
+  echo "deriving instance Show (T a)" >> Match.hs;
+fi
+#elif [ $MODE -eq 1 ]; then
+#  echo "data T " >> Match.hs
+#    for i in $(seq -w 1 $MATCHES); do
+#      echo "       a$i" >> Match.hs;
+#    done
+#    echo "       = T " >> Match.hs
+#    for i in $(seq -w 1 $MATCHES); do
+#      echo "       a$i" >> Match.hs;
+#    done
+#    echo "deriving instance Show (T" >> Match.hs
+#    for i in $(seq -w 1 $MATCHES); do
+#      echo "       a$i" >> Match.hs;
+#    done
+#    echo "    )" >> Match.hs;
+#else
+#  for i in $(seq -w 1 $MATCHES); do
+#    echo "data F$i a" >> Match.hs;
+#  done
+#  echo "data T a = T" >> Match.hs
+#  for i in $(seq -w 1 $MATCHES); do
+#    echo "       (F$i a)" >> Match.hs;
+#  done
+#  echo "deriving instance Show (T a)" >> Match.hs;
+#
+#fi
+
diff --git a/testsuite/tests/th/T11629.hs b/testsuite/tests/th/T11629.hs
index 4fcc093823..11373fd4cb 100644
--- a/testsuite/tests/th/T11629.hs
+++ b/testsuite/tests/th/T11629.hs
@@ -37,7 +37,7 @@ do
   ty1 <- [t| C True |]
   ty2 <- [t| C 'False |]
   ClassI _ insts <- reify ''C
-  let [ty1', ty2'] = map getType insts
+  let [ty2', ty1'] = map getType insts
 
   when (ty1 /= ty1') $ failMsg "A" ty1 ty1'
   when (ty2 /= ty2') $ failMsg "B" ty2 ty2'
diff --git a/testsuite/tests/th/T17296.stderr b/testsuite/tests/th/T17296.stderr
index 4a6f1ac3bd..f103f7986a 100644
--- a/testsuite/tests/th/T17296.stderr
+++ b/testsuite/tests/th/T17296.stderr
@@ -1,19 +1,19 @@
 data family T17296.Foo1 :: * -> *
-data instance T17296.Foo1 GHC.Types.Bool = T17296.Foo1Bool
 data instance forall (a_0 :: *). T17296.Foo1 (GHC.Maybe.Maybe a_0)
+data instance T17296.Foo1 GHC.Types.Bool = T17296.Foo1Bool
 
 data family T17296.Foo2 :: k_0 -> *
-data instance T17296.Foo2 GHC.Types.Bool = T17296.Foo2Bool
-data instance forall (a_1 :: *). T17296.Foo2 (GHC.Maybe.Maybe a_1 :: *)
-data instance T17296.Foo2 :: GHC.Types.Char -> *
 data instance T17296.Foo2 :: (GHC.Types.Char -> GHC.Types.Char) ->
                              *
+data instance T17296.Foo2 :: GHC.Types.Char -> *
+data instance forall (a_1 :: *). T17296.Foo2 (GHC.Maybe.Maybe a_1 :: *)
+data instance T17296.Foo2 GHC.Types.Bool = T17296.Foo2Bool
 
 data family T17296.Foo3 :: k_0
-data instance T17296.Foo3 :: *
-data instance T17296.Foo3 GHC.Types.Bool = T17296.Foo3Bool
-data instance forall (a_1 :: *). T17296.Foo3 (GHC.Maybe.Maybe a_1 :: *)
 data instance T17296.Foo3 :: GHC.Types.Char -> *
 data instance T17296.Foo3 :: (GHC.Types.Char -> GHC.Types.Char) ->
                              *
+data instance forall (a_1 :: *). T17296.Foo3 (GHC.Maybe.Maybe a_1 :: *)
+data instance T17296.Foo3 GHC.Types.Bool = T17296.Foo3Bool
+data instance T17296.Foo3 :: *
 
diff --git a/testsuite/tests/th/T1835.stdout b/testsuite/tests/th/T1835.stdout
index 7d34ae01f0..5b21c0352c 100644
--- a/testsuite/tests/th/T1835.stdout
+++ b/testsuite/tests/th/T1835.stdout
@@ -1,8 +1,8 @@
 class GHC.Classes.Eq a_0 => Main.MyClass (a_0 :: *)
-instance GHC.Classes.Ord a_1 => Main.MyClass (Main.Quux2 a_1)
-instance GHC.Classes.Eq a_2 => Main.MyClass (Main.Quux a_2)
-instance Main.MyClass Main.Baz
 instance Main.MyClass Main.Foo
+instance Main.MyClass Main.Baz
+instance GHC.Classes.Eq a_1 => Main.MyClass (Main.Quux a_1)
+instance GHC.Classes.Ord a_2 => Main.MyClass (Main.Quux2 a_2)
 True
 True
 True
diff --git a/testsuite/tests/th/T8953.stderr b/testsuite/tests/th/T8953.stderr
index d87acef442..ba19e035b9 100644
--- a/testsuite/tests/th/T8953.stderr
+++ b/testsuite/tests/th/T8953.stderr
@@ -1,16 +1,16 @@
 type family T8953.Poly (a_0 :: k_1) :: *
-type instance forall (x_2 :: GHC.Types.Bool). T8953.Poly (x_2 :: GHC.Types.Bool) = GHC.Types.Int
-type instance forall (k_3 :: *)
-                     (x_4 :: GHC.Maybe.Maybe k_3). T8953.Poly (x_4 :: GHC.Maybe.Maybe k_3) = GHC.Types.Double
+type instance forall (k_2 :: *)
+                     (x_3 :: GHC.Maybe.Maybe k_2). T8953.Poly (x_3 :: GHC.Maybe.Maybe k_2) = GHC.Types.Double
+type instance forall (x_4 :: GHC.Types.Bool). T8953.Poly (x_4 :: GHC.Types.Bool) = GHC.Types.Int
 type family T8953.Silly :: k_0 -> *
-type instance T8953.Silly = (Data.Proxy.Proxy :: * -> *)
 type instance T8953.Silly = (Data.Proxy.Proxy :: (* -> *) -> *)
+type instance T8953.Silly = (Data.Proxy.Proxy :: * -> *)
 T8953.a :: Data.Proxy.Proxy (Data.Proxy.Proxy :: * -> *)
 T8953.b :: Data.Proxy.Proxy (Data.Proxy.Proxy :: (* -> *) -> *)
 type T8953.StarProxy (a_0 :: *) = Data.Proxy.Proxy a_0
 class T8953.PC (a_0 :: k_1)
-instance T8953.PC (a_2 :: *)
-instance T8953.PC (Data.Proxy.Proxy :: (k_3 -> *) -> *)
+instance T8953.PC (Data.Proxy.Proxy :: (k_2 -> *) -> *)
+instance T8953.PC (a_3 :: *)
 type family T8953.F (a_0 :: *) :: k_1
 type instance T8953.F GHC.Types.Char = T8953.G (T8953.T1 :: * ->
                                                             (* -> *) -> *)
diff --git a/testsuite/tests/th/TH_reifyDecl1.stderr b/testsuite/tests/th/TH_reifyDecl1.stderr
index c9b295ec83..2c1ee67d88 100644
--- a/testsuite/tests/th/TH_reifyDecl1.stderr
+++ b/testsuite/tests/th/TH_reifyDecl1.stderr
@@ -35,8 +35,8 @@ data family TH_reifyDecl1.DF2 (a_0 :: *) :: *
 data instance TH_reifyDecl1.DF2 GHC.Types.Bool
     = TH_reifyDecl1.DBool
 data family TH_reifyDecl1.DF3 (a_0 :: k_1) :: *
-data instance forall (a_2 :: *). TH_reifyDecl1.DF3 (a_2 :: *)
-    = TH_reifyDecl1.DF3Bool
-data instance forall (b_3 :: * ->
-                             *). TH_reifyDecl1.DF3 (b_3 :: * -> *)
+data instance forall (b_2 :: * ->
+                             *). TH_reifyDecl1.DF3 (b_2 :: * -> *)
     = TH_reifyDecl1.DF3Char
+data instance forall (a_3 :: *). TH_reifyDecl1.DF3 (a_3 :: *)
+    = TH_reifyDecl1.DF3Bool
diff --git a/testsuite/tests/typecheck/should_fail/T5095.stderr b/testsuite/tests/typecheck/should_fail/T5095.stderr
index 27784f8250..083551cc5f 100644
--- a/testsuite/tests/typecheck/should_fail/T5095.stderr
+++ b/testsuite/tests/typecheck/should_fail/T5095.stderr
@@ -5,9 +5,9 @@ T5095.hs:9:11: error:
         instance [overlappable] Show a => Eq a -- Defined at T5095.hs:5:31
       Potentially matching instances:
         instance Eq Ordering -- Defined in ‘GHC.Classes’
-        instance Eq a => Eq (Maybe a) -- Defined in ‘GHC.Maybe’
-        ...plus 24 others
-        ...plus six instances involving out-of-scope types
+        instance Eq Integer -- Defined in ‘GHC.Num.Integer’
+        ...plus 23 others
+        ...plus four instances involving out-of-scope types
         (use -fprint-potential-instances to see them all)
       (The choice depends on the instantiation of ‘a’
        To pick the first instance above, use IncoherentInstances
diff --git a/testsuite/tests/typecheck/should_fail/tcfail118.stderr b/testsuite/tests/typecheck/should_fail/tcfail118.stderr
index 098af79736..705a68d87a 100644
--- a/testsuite/tests/typecheck/should_fail/tcfail118.stderr
+++ b/testsuite/tests/typecheck/should_fail/tcfail118.stderr
@@ -1,8 +1,8 @@
 
-tcfail118.hs:10:29:
-    Overlapping instances for Eq Foo
-      arising from the first field of ‘Bar’ (type ‘Foo’)
-    Matching instances:
-      instance Eq Foo -- Defined at tcfail118.hs:11:25
-      instance Eq Foo -- Defined at tcfail118.hs:13:10
-    When deriving the instance for (Eq Bar)
+tcfail118.hs:10:29: error:
+    • Overlapping instances for Eq Foo
+        arising from the first field of ‘Bar’ (type ‘Foo’)
+      Matching instances:
+        instance Eq Foo -- Defined at tcfail118.hs:13:10
+        instance Eq Foo -- Defined at tcfail118.hs:11:25
+    • When deriving the instance for (Eq Bar)