compiler: Introduce and use RoughMap for instance environments

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>

17 files changed, 141 insertions, 139 deletions

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’