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>

2 files changed, 10 insertions, 8 deletions

diff --git a/compiler/GHC/Iface/Make.hs b/compiler/GHC/Iface/Make.hs
index 2893e3857c..129da7c014 100644
--- a/compiler/GHC/Iface/Make.hs
+++ b/compiler/GHC/Iface/Make.hs
@@ -282,7 +282,7 @@ mkIface_ hsc_env
           -- See Note [Deterministic UniqFM] in GHC.Types.Unique.DFM for more details.
         warns       = src_warns
         iface_rules = map coreRuleToIfaceRule rules
-        iface_insts = map instanceToIfaceInst $ fixSafeInstances safe_mode insts
+        iface_insts = map instanceToIfaceInst $ fixSafeInstances safe_mode (instEnvElts insts)
         iface_fam_insts = map famInstToIfaceFamInst fam_insts
         trust_info  = setSafeMode safe_mode
         annotations = map mkIfaceAnnotation anns
@@ -700,7 +700,9 @@ instanceToIfaceInst (ClsInst { is_dfun = dfun_id, is_flag = oflag
     IfaceClsInst { ifDFun     = idName dfun_id
                  , ifOFlag    = oflag
                  , ifInstCls  = cls_name
-                 , ifInstTys  = ifaceRoughMatchTcs rough_tcs
+                 , ifInstTys  = ifaceRoughMatchTcs $ tail rough_tcs
+                   -- N.B. Drop the class name from the rough match template
+                   --      It is put back by GHC.Core.InstEnv.mkImportedInstance
                  , ifInstOrph = orph }
 
 --------------------------
@@ -728,8 +730,8 @@ famInstToIfaceFamInst (FamInst { fi_axiom    = axiom,
 ifaceRoughMatchTcs :: [RoughMatchTc] -> [Maybe IfaceTyCon]
 ifaceRoughMatchTcs tcs = map do_rough tcs
   where
-    do_rough OtherTc     = Nothing
-    do_rough (KnownTc n) = Just (toIfaceTyCon_name n)
+    do_rough RM_WildCard     = Nothing
+    do_rough (RM_KnownTc n) = Just (toIfaceTyCon_name n)
 
 --------------------------
 coreRuleToIfaceRule :: CoreRule -> IfaceRule
diff --git a/compiler/GHC/Iface/Tidy.hs b/compiler/GHC/Iface/Tidy.hs
index 28c2cbc54d..b1a079205e 100644
--- a/compiler/GHC/Iface/Tidy.hs
+++ b/compiler/GHC/Iface/Tidy.hs
@@ -192,7 +192,7 @@ mkBootModDetailsTc logger
     final_tcs  = filterOut isWiredIn tcs
                  -- See Note [Drop wired-in things]
     type_env'  = typeEnvFromEntities final_ids final_tcs pat_syns fam_insts
-    insts'     = mkFinalClsInsts type_env' insts
+    insts'     = mkFinalClsInsts type_env' $ mkInstEnv insts
 
     -- Default methods have their export flag set (isExportedId),
     -- but everything else doesn't (yet), because this is
@@ -213,8 +213,8 @@ lookupFinalId type_env id
       Just (AnId id') -> id'
       _ -> pprPanic "lookup_final_id" (ppr id)
 
-mkFinalClsInsts :: TypeEnv -> [ClsInst] -> [ClsInst]
-mkFinalClsInsts env = map (updateClsInstDFun (lookupFinalId env))
+mkFinalClsInsts :: TypeEnv -> InstEnv -> InstEnv
+mkFinalClsInsts env = updateClsInstDFuns (lookupFinalId env)
 
 globaliseAndTidyBootId :: Id -> Id
 -- For a LocalId with an External Name,
@@ -419,7 +419,7 @@ tidyProgram hsc_env  (ModGuts { mg_module           = mod
               ; final_tcs      = filterOut isWiredIn tcs
                                  -- See Note [Drop wired-in things]
               ; tidy_type_env  = typeEnvFromEntities final_ids final_tcs patsyns fam_insts
-              ; tidy_cls_insts = mkFinalClsInsts tidy_type_env cls_insts
+              ; tidy_cls_insts = mkFinalClsInsts tidy_type_env $ mkInstEnv cls_insts
               ; tidy_rules     = tidyRules tidy_env trimmed_rules
 
               ; -- See Note [Injecting implicit bindings]