Simon Peyton Jones pushed to branch wip/T26724 at Glasgow Haskell Compiler / GHC

Commits:

• e4cb1494
  by Simon Peyton Jones at 2026-01-06T20:56:11+00:00

  Try harder to keep the substitution empty
  
  Avoid unnecessary cloning of varaibles in the Simplifier.
  
  Addresses #26724,
  
  See Note [Keeping the substitution empty]
  
  There are a few big wins -- see below
  
  Metrics: compile_time/bytes allocated
  -------------------------------------
                                           Baseline
                      Test    Metric          value      New value Change
  ----------------------------------------------------------------------------
  CoOpt_Singletons(normal) ghc/alloc    721,544,088    692,174,216  -4.1% GOOD
       LargeRecord(normal) ghc/alloc  1,268,031,157  1,265,168,448  -0.2%
            T14766(normal) ghc/alloc    918,218,533    688,432,296 -25.0% GOOD
            T15703(normal) ghc/alloc    318,103,629    306,638,016  -3.6% GOOD
            T17836(normal) ghc/alloc    419,174,584    418,400,824  -0.2%
            T18478(normal) ghc/alloc    471,042,976    470,261,376  -0.2%
            T20261(normal) ghc/alloc    573,387,162    563,663,336  -1.7%
            T24984(normal) ghc/alloc     87,832,666     87,636,168  -0.2%
            T25196(optasm) ghc/alloc  1,103,284,040  1,101,376,992  -0.2%
    hard_hole_fits(normal) ghc/alloc    224,981,413    224,608,208  -0.2%
  
                 geo. mean                                          -0.3%
                 minimum                                           -25.0%
                 maximum                                            +0.1%
  
  Metric Decrease:
      CoOpt_Singletons
      T14766
      T15703
  

2 changed files:

• compiler/GHC/Core/Subst.hs
• compiler/GHC/Core/TyCo/Subst.hs

Changes:

     old_ty = idType old_id

     old_w = idMult old_id

-    no_type_change = (isEmptyVarEnv tvs && isEmptyVarEnv cvs) ||

+    no_type_change = isEmptyTCvSubst subst ||

                      (noFreeVarsOfType old_ty && noFreeVarsOfType old_w)

+                     -- isEmptyTCvSubst: see Note [Keeping the substitution empty]

+                     --                  in GHC.Core.TyCo.Subst

         -- new_id has the right IdInfo

         -- The lazy-set is because we're in a loop here, with

     -- Assertion check that we are not capturing something in the substitution

     old_ki = tyVarKind old_var

-    no_kind_change = noFreeVarsOfType old_ki -- verify that kind is closed

+    no_kind_change = isEmptyTCvSubst subst || noFreeVarsOfType old_ki

+                     -- isEmptyTCvSubst: see Note [Keeping the substitution empty]

     no_change = no_kind_change && (new_var == old_var)

         -- no_change means that the new_var is identical in

         -- all respects to the old_var (same unique, same kind)

     (Subst (in_scope `extendInScopeSet` new_var) idenv tenv new_cenv, new_var)

   where

     new_co         = mkCoVarCo new_var

-    no_kind_change = noFreeVarsOfTypes [t1, t2]

+    no_kind_change = isEmptyTCvSubst subst || noFreeVarsOfTypes [t1, t2]

+                     -- isEmptyTCvSubst: see Note [Keeping the substitution empty]

     no_change      = new_var == old_var && no_kind_change

     new_cenv | no_change = delVarEnv cenv old_var

 substTyCoBndr subst (Named (Bndr tv vis)) = (subst', Named (Bndr tv' vis))

                                           where

                                             (subst', tv') = substVarBndr subst tv

+

+{- Note [Keeping the substitution empty]

+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

+A very common situation is where we run over a term doing no cloning,

+no substitution, nothing.  In that case the TCvSubst till be empty, and

+it is /very/ valuable to /keep/ it empty:

+

+* It's wasted effort to build up an identity substitution mapping

+  [x:->x, y:->y].

+

+* When we come to a binder, if the incoming substitution is empty,

+  we can avoid substituting its type; and that in turn may mean that

+  the binder itself does not change and we don't need to extend the

+  substitution.

+

+* In the Simplifier we substitute over both types and coercions.

+  If the substitution is empty, this is a no-op -- but only if it

+  is empty!

+-}