Exponential behaviour in typeKind, unifyTys etc

In Trac #11371 Bartosz found some very suspicious performance behaviour. Specifically:

• See comment 42 of #11371, which says that liftCoMatch and promoteCoercion is responsible for a significant fraction of all compiler allocation. Why so expensive? Especially since only used from OptCoercion.
• There are two comments in Unify saying

ty_co_match_app menv subst ty1a ty1b co2a co2b
  = do { -- TODO (RAE): Remove this exponential behavior.
         subst1 <- ty_co_match menv subst  ki1a ki2a ki_ki_co ki_ki_co

and

unify_ty_app ty1a ty1b ty2a ty2b
  = do { -- TODO (RAE): Remove this exponential behavior.
         let ki1a = typeKind ty1a
             ki2a = typeKind ty2a
       ; unify_ty ki1a ki2a (mkNomReflCo liftedTypeKind)

NB: ty_co_match_app is also called from liftCoMatch.

Trac metadata

Trac field	Value
Version	7.10.3
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture