Abstract over free variable traversals

12 files changed, 490 insertions, 464 deletions

diff --git a/compiler/coreSyn/CoreFVs.hs b/compiler/coreSyn/CoreFVs.hs
index 9f0ac44d4d..20c803e906 100644
--- a/compiler/coreSyn/CoreFVs.hs
+++ b/compiler/coreSyn/CoreFVs.hs
@@ -6,6 +6,7 @@ Taken quite directly from the Peyton Jones/Lester paper.
 -}
 
 {-# LANGUAGE CPP #-}
+{-# OPTIONS_GHC -ddump-to-file -ddump-simpl -ddump-stg -dsuppress-ticks #-}
 
 -- | A module concerned with finding the free variables of an expression.
 module CoreFVs (
@@ -20,6 +21,7 @@ module CoreFVs (
         exprsFreeIdsList,
         exprsFreeVars,
         exprsFreeVarsList,
+        exprFVs,
         bindFreeVars,
         mkExprInScopeSet,
 
@@ -39,8 +41,6 @@ module CoreFVs (
         rulesFreeVarsDSet,
         ruleLhsFreeIds, ruleLhsFreeIdsList,
 
-        expr_fvs,
-
         -- * Orphan names
         orphNamesOfType, orphNamesOfCo, orphNamesOfAxiom,
         orphNamesOfTypes, orphNamesOfCoCon,
@@ -65,10 +65,11 @@ import GhcPrelude
 import CoreSyn
 import Id
 import IdInfo
-import NameSet
+import NameSet hiding (unitFV)
 import UniqSet
 import Unique (Uniquable (..))
 import Name
+import VarEnv
 import VarSet
 import Var
 import Type
@@ -82,7 +83,7 @@ import Maybes( orElse )
 import Util
 import BasicTypes( Activation )
 import Outputable
-import FV
+import FV hiding ( noFVs )
 
 {-
 ************************************************************************
@@ -115,7 +116,7 @@ mkExprInScopeSet e = mkInScopeSet $ fvVarSet $ exprFVs e
 -- returning a composable FV computation. See Note [FV naming conventions] in FV
 -- for why export it.
 exprFVs :: CoreExpr -> FV
-exprFVs = filterFV isLocalVar . expr_fvs
+exprFVs = localFVs . expr_fvs
 
 -- | Find all locally-defined free Ids or type variables in an expression
 -- returning a deterministic set.
@@ -169,10 +170,10 @@ exprsFreeVarsList = fvVarList . exprsFVs
 
 -- | Find all locally defined free Ids in a binding group
 bindFreeVars :: CoreBind -> VarSet
-bindFreeVars (NonRec b r) = fvVarSet $ filterFV isLocalVar $ rhs_fvs (b,r)
-bindFreeVars (Rec prs)    = fvVarSet $ filterFV isLocalVar $
+bindFreeVars (NonRec b r) = localFvVarSet $ rhs_fvs (b,r)
+bindFreeVars (Rec prs)    = localFvVarSet $
                                 addBndrs (map fst prs)
-                                     (mapUnionFV rhs_fvs prs)
+                                     (foldMap rhs_fvs prs)
 
 -- | Finds free variables in an expression selected by a predicate
 exprSomeFreeVars :: InterestingVarFun   -- ^ Says which 'Var's are interesting
@@ -245,60 +246,55 @@ exprsSomeFreeVarsDSet fv_cand e =
 --                          | otherwise                    = set
 --      SLPJ Feb06
 
-addBndr :: CoreBndr -> FV -> FV
-addBndr bndr fv fv_cand in_scope acc
-  = (varTypeTyCoFVs bndr `unionFV`
+addBndr :: FreeVarStrategy fv => CoreBndr -> fv -> fv
+addBndr bndr fv
+  = typeFVs (varType bndr) `unionFV` bindVar bndr fv
         -- Include type variables in the binder's type
         --      (not just Ids; coercion variables too!)
-     FV.delFV bndr fv) fv_cand in_scope acc
 
-addBndrs :: [CoreBndr] -> FV -> FV
+addBndrs :: FreeVarStrategy fv => [CoreBndr] -> fv -> fv
 addBndrs bndrs fv = foldr addBndr fv bndrs
 
-expr_fvs :: CoreExpr -> FV
-expr_fvs (Type ty) fv_cand in_scope acc =
-  tyCoFVsOfType ty fv_cand in_scope acc
-expr_fvs (Coercion co) fv_cand in_scope acc =
-  tyCoFVsOfCo co fv_cand in_scope acc
-expr_fvs (Var var) fv_cand in_scope acc = FV.unitFV var fv_cand in_scope acc
-expr_fvs (Lit _) fv_cand in_scope acc = emptyFV fv_cand in_scope acc
-expr_fvs (Tick t expr) fv_cand in_scope acc =
-  (tickish_fvs t `unionFV` expr_fvs expr) fv_cand in_scope acc
-expr_fvs (App fun arg) fv_cand in_scope acc =
-  (expr_fvs fun `unionFV` expr_fvs arg) fv_cand in_scope acc
-expr_fvs (Lam bndr body) fv_cand in_scope acc =
-  addBndr bndr (expr_fvs body) fv_cand in_scope acc
-expr_fvs (Cast expr co) fv_cand in_scope acc =
-  (expr_fvs expr `unionFV` tyCoFVsOfCo co) fv_cand in_scope acc
-
-expr_fvs (Case scrut bndr ty alts) fv_cand in_scope acc
-  = (expr_fvs scrut `unionFV` tyCoFVsOfType ty `unionFV` addBndr bndr
-      (mapUnionFV alt_fvs alts)) fv_cand in_scope acc
+expr_fvs :: FreeVarStrategy fv => CoreExpr -> fv
+expr_fvs (Type ty) = typeFVs ty
+expr_fvs (Coercion co) = coFVs co
+expr_fvs (Var var) = FV.unitFV var
+expr_fvs (Lit _) = mempty
+expr_fvs (Tick t expr) = tickish_fvs t `unionFV` expr_fvs expr
+expr_fvs (App fun arg) = expr_fvs fun `unionFV` expr_fvs arg
+expr_fvs (Lam bndr body) = addBndr bndr (expr_fvs body)
+expr_fvs (Cast expr co) = expr_fvs expr `unionFV` coFVs co
+
+expr_fvs (Case scrut bndr ty alts)
+  = expr_fvs scrut `unionFV` typeFVs ty `unionFV` addBndr bndr (foldMap alt_fvs alts)
   where
     alt_fvs (_, bndrs, rhs) = addBndrs bndrs (expr_fvs rhs)
 
-expr_fvs (Let (NonRec bndr rhs) body) fv_cand in_scope acc
-  = (rhs_fvs (bndr, rhs) `unionFV` addBndr bndr (expr_fvs body))
-      fv_cand in_scope acc
+expr_fvs (Let (NonRec bndr rhs) body)
+  = rhs_fvs (bndr, rhs) `unionFV` addBndr bndr (expr_fvs body)
 
-expr_fvs (Let (Rec pairs) body) fv_cand in_scope acc
+expr_fvs (Let (Rec pairs) body)
   = addBndrs (map fst pairs)
-             (mapUnionFV rhs_fvs pairs `unionFV` expr_fvs body)
-               fv_cand in_scope acc
+             (foldMap rhs_fvs pairs `unionFV` expr_fvs body)
+{-# SPECIALISE expr_fvs :: CoreExpr -> FV #-}
+{-# SPECIALISE expr_fvs :: CoreExpr -> NonDetFV #-}
+{-# SPECIALISE expr_fvs :: CoreExpr -> LocalFV #-}
+{-# SPECIALISE expr_fvs :: CoreExpr -> LocalNonDetFV #-}
+{-# SPECIALISE expr_fvs :: CoreExpr -> NoFVs #-}
 
 ---------
-rhs_fvs :: (Id, CoreExpr) -> FV
-rhs_fvs (bndr, rhs) = expr_fvs rhs `unionFV`
-                      bndrRuleAndUnfoldingFVs bndr
-        -- Treat any RULES as extra RHSs of the binding
+rhs_fvs :: FreeVarStrategy fv => (Id, CoreExpr) -> fv
+rhs_fvs (bndr, rhs)
+  = expr_fvs rhs `unionFV` bndrRuleAndUnfoldingFVs bndr
+    -- Treat any RULES as extra RHSs of the binding
 
 ---------
-exprs_fvs :: [CoreExpr] -> FV
-exprs_fvs exprs = mapUnionFV expr_fvs exprs
+exprs_fvs :: FreeVarStrategy fv => [CoreExpr] -> fv
+exprs_fvs exprs = foldMap expr_fvs exprs
 
-tickish_fvs :: Tickish Id -> FV
-tickish_fvs (Breakpoint _ ids) = FV.mkFVs ids
-tickish_fvs _ = emptyFV
+tickish_fvs :: FreeVarStrategy fv => Tickish Id -> fv
+tickish_fvs (Breakpoint _ ids) = foldMap FV.unitFV ids
+tickish_fvs _ = mempty
 
 {-
 ************************************************************************
@@ -449,7 +445,7 @@ orphNamesOfFamInst fam_inst = orphNamesOfAxiom (famInstAxiom fam_inst)
 ruleRhsFreeVars :: CoreRule -> VarSet
 ruleRhsFreeVars (BuiltinRule {}) = noFVs
 ruleRhsFreeVars (Rule { ru_fn = _, ru_bndrs = bndrs, ru_rhs = rhs })
-  = fvVarSet $ filterFV isLocalVar $ addBndrs bndrs (expr_fvs rhs)
+  = localFvVarSet $ addBndrs bndrs (expr_fvs rhs)
       -- See Note [Rule free var hack]
 
 -- | Those variables free in the both the left right hand sides of a rule
@@ -465,7 +461,7 @@ ruleFVs (Rule { ru_fn = _do_not_include
                   -- See Note [Rule free var hack]
               , ru_bndrs = bndrs
               , ru_rhs = rhs, ru_args = args })
-  = filterFV isLocalVar $ addBndrs bndrs (exprs_fvs (rhs:args))
+  = localFVs $ addBndrs bndrs (exprs_fvs (rhs:args))
 
 -- | Those variables free in the both the left right hand sides of rules
 -- returned as FV computation
@@ -489,7 +485,7 @@ idRuleRhsVars is_active id
       = delOneFromUniqSet_Directly fvs (getUnique fn)
             -- Note [Rule free var hack]
       where
-        fvs = fvVarSet $ filterFV isLocalVar $ addBndrs bndrs (expr_fvs rhs)
+        fvs = localFvVarSet $ addBndrs bndrs (expr_fvs rhs)
     get_fvs _ = noFVs
 
 -- | Those variables free in the right hand side of several rules
@@ -499,19 +495,19 @@ rulesFreeVars rules = mapUnionVarSet ruleFreeVars rules
 ruleLhsFreeIds :: CoreRule -> VarSet
 -- ^ This finds all locally-defined free Ids on the left hand side of a rule
 -- and returns them as a non-deterministic set
-ruleLhsFreeIds = fvVarSet . ruleLhsFVIds
+ruleLhsFreeIds = nonDetFVSet . ruleLhsFVIds
 
 ruleLhsFreeIdsList :: CoreRule -> [Var]
 -- ^ This finds all locally-defined free Ids on the left hand side of a rule
 -- and returns them as a determinisitcally ordered list
 ruleLhsFreeIdsList = fvVarList . ruleLhsFVIds
 
-ruleLhsFVIds :: CoreRule -> FV
+ruleLhsFVIds :: FreeVarStrategy fv => CoreRule -> fv
 -- ^ This finds all locally-defined free Ids on the left hand side of a rule
 -- and returns an FV computation
 ruleLhsFVIds (BuiltinRule {}) = emptyFV
 ruleLhsFVIds (Rule { ru_bndrs = bndrs, ru_args = args })
-  = filterFV isLocalId $ addBndrs bndrs (exprs_fvs args)
+  = localFVs $ addBndrs bndrs (exprs_fvs args)
 
 {-
 Note [Rule free var hack]  (Not a hack any more)
@@ -642,17 +638,17 @@ idFVs id = ASSERT( isId id)
 bndrRuleAndUnfoldingVarsDSet :: Id -> DVarSet
 bndrRuleAndUnfoldingVarsDSet id = fvDVarSet $ bndrRuleAndUnfoldingFVs id
 
-bndrRuleAndUnfoldingFVs :: Id -> FV
+bndrRuleAndUnfoldingFVs :: FreeVarStrategy fv => Id -> fv
 bndrRuleAndUnfoldingFVs id
   | isId id   = idRuleFVs id `unionFV` idUnfoldingFVs id
-  | otherwise = emptyFV
+  | otherwise = mempty
 
 idRuleVars ::Id -> VarSet  -- Does *not* include CoreUnfolding vars
 idRuleVars id = fvVarSet $ idRuleFVs id
 
-idRuleFVs :: Id -> FV
+idRuleFVs :: FreeVarStrategy fv => Id -> fv
 idRuleFVs id = ASSERT( isId id)
-  FV.mkFVs (dVarSetElems $ ruleInfoFreeVars (idSpecialisation id))
+  foldMap unitFV (dVarSetElems $ ruleInfoFreeVars (idSpecialisation id))
 
 idUnfoldingVars :: Id -> VarSet
 -- Produce free vars for an unfolding, but NOT for an ordinary
@@ -662,20 +658,20 @@ idUnfoldingVars :: Id -> VarSet
 -- we might get out-of-scope variables
 idUnfoldingVars id = fvVarSet $ idUnfoldingFVs id
 
-idUnfoldingFVs :: Id -> FV
-idUnfoldingFVs id = stableUnfoldingFVs (realIdUnfolding id) `orElse` emptyFV
+idUnfoldingFVs :: FreeVarStrategy fv => Id -> fv
+idUnfoldingFVs id = stableUnfoldingFVs (realIdUnfolding id) `orElse` mempty
 
 stableUnfoldingVars :: Unfolding -> Maybe VarSet
 stableUnfoldingVars unf = fvVarSet `fmap` stableUnfoldingFVs unf
 
-stableUnfoldingFVs :: Unfolding -> Maybe FV
+stableUnfoldingFVs :: FreeVarStrategy fv => Unfolding -> Maybe fv
 stableUnfoldingFVs unf
   = case unf of
       CoreUnfolding { uf_tmpl = rhs, uf_src = src }
          | isStableSource src
-         -> Just (filterFV isLocalVar $ expr_fvs rhs)
+         -> Just (localFVs $ expr_fvs rhs)
       DFunUnfolding { df_bndrs = bndrs, df_args = args }
-         -> Just (filterFV isLocalVar $ FV.delFVs (mkVarSet bndrs) $ exprs_fvs args)
+         -> Just (localFVs $ foldr bindVar (exprs_fvs args) bndrs)
             -- DFuns are top level, so no fvs from types of bndrs
       _other -> Nothing
 
diff --git a/compiler/coreSyn/CoreSubst.hs b/compiler/coreSyn/CoreSubst.hs
index afb8946426..0e2cf61f89 100644
--- a/compiler/coreSyn/CoreSubst.hs
+++ b/compiler/coreSyn/CoreSubst.hs
@@ -54,6 +54,7 @@ import PrelNames
 import VarSet
 import VarEnv
 import Id
+import FV
 import Name     ( Name )
 import Var
 import IdInfo
@@ -698,11 +699,13 @@ substRule subst subst_ru_fn rule@(Rule { ru_bndrs = bndrs, ru_args = args
 ------------------
 substDVarSet :: Subst -> DVarSet -> DVarSet
 substDVarSet subst fvs
-  = mkDVarSet $ fst $ foldr (subst_fv subst) ([], emptyVarSet) $ dVarSetElems fvs
+  = let FVAccum vars _ = foldr (subst_fv subst) emptyFVAccum $ dVarSetElems fvs
+    in mkDVarSet vars
   where
+  subst_fv :: Subst -> Var -> FVAccum -> FVAccum
   subst_fv subst fv acc
-     | isId fv = expr_fvs (lookupIdSubst (text "substDVarSet") subst fv) isLocalVar emptyVarSet $! acc
-     | otherwise = tyCoFVsOfType (lookupTCvSubst subst fv) (const True) emptyVarSet $! acc
+     | isId fv = (runFV $ exprFVs (lookupIdSubst (text "substDVarSet") subst fv)) isLocalVar emptyVarSet $! acc
+     | otherwise = (runFV $ tyCoFVsOfType (lookupTCvSubst subst fv)) (const True) emptyVarSet $! acc
 
 ------------------
 substTickish :: Subst -> Tickish Id -> Tickish Id
diff --git a/compiler/ghc.cabal.in b/compiler/ghc.cabal.in
index 7fd83c9d8b..03989ce57e 100644
--- a/compiler/ghc.cabal.in
+++ b/compiler/ghc.cabal.in
@@ -553,6 +553,7 @@ Library
         Fingerprint
         FiniteMap
         FV
+        FreeVarStrategy
         GraphBase
         GraphColor
         GraphOps
diff --git a/compiler/simplCore/SetLevels.hs b/compiler/simplCore/SetLevels.hs
index a3a5944031..0fbdccd61e 100644
--- a/compiler/simplCore/SetLevels.hs
+++ b/compiler/simplCore/SetLevels.hs
@@ -100,6 +100,7 @@ import FastString
 import UniqDFM
 import FV
 import Data.Maybe
+import Data.Foldable
 import MonadUtils       ( mapAccumLM )
 
 {-
@@ -1204,8 +1205,8 @@ lvlBind env (AnnRec pairs)
         -- Finding the free vars of the binding group is annoying
     bind_fvs = ((unionDVarSets [ freeVarsOf rhs | (_, rhs) <- pairs])
                 `unionDVarSet`
-                (fvDVarSet $ unionsFV [ idFVs bndr
-                                      | (bndr, (_,_)) <- pairs]))
+                (fvDVarSet $ fold [ idFVs bndr
+                                  | (bndr, (_,_)) <- pairs]))
                `delDVarSetList`
                 bndrs
 
diff --git a/compiler/types/TyCoFVs.hs b/compiler/types/TyCoFVs.hs
index eefd68f145..970ab0561e 100644
--- a/compiler/types/TyCoFVs.hs
+++ b/compiler/types/TyCoFVs.hs
@@ -1,3 +1,5 @@
+{-# OPTIONS_GHC -ddump-to-file -ddump-simpl -ddump-stg -dsuppress-ticks #-}
+
 module TyCoFVs
   (
         tyCoVarsOfType, tyCoVarsOfTypeDSet, tyCoVarsOfTypes, tyCoVarsOfTypesDSet,
@@ -11,7 +13,8 @@ module TyCoFVs
         tyCoVarsOfCo, tyCoVarsOfCos,
         tyCoVarsOfCoDSet,
         tyCoFVsOfCo, tyCoFVsOfCos,
-        tyCoVarsOfCoList, tyCoVarsOfProv,
+        tyCoVarsOfCoList,
+        typeFVs, coFVs,
         almostDevoidCoVarOfCo,
         injectiveVarsOfType, injectiveVarsOfTypes,
         invisibleVarsOfType, invisibleVarsOfTypes,
@@ -40,6 +43,8 @@ import VarEnv
 import Util
 import Panic
 
+import Data.Semigroup ((<>))
+
 {-
 %************************************************************************
 %*                                                                      *
@@ -53,10 +58,10 @@ import Panic
 The family of functions tyCoVarsOfType, tyCoVarsOfTypes etc, returns
 a VarSet that is closed over the types of its variables.  More precisely,
   if    S = tyCoVarsOfType( t )
-  and   (a:k) is in S
+  and   (a::k) is in S
   then  tyCoVarsOftype( k ) is a subset of S
 
-Example: The tyCoVars of this ((a:* -> k) Int) is {a, k}.
+Example: The tyCoVars of this (((a::Type) -> k) Int) is {a, k}.
 
 We could /not/ close over the kinds of the variable occurrences, and
 instead do so at call sites, but it seems that we always want to do
@@ -172,100 +177,26 @@ kind are free.
 
 tyCoVarsOfType :: Type -> TyCoVarSet
 -- See Note [Free variables of types]
-tyCoVarsOfType ty = ty_co_vars_of_type ty emptyVarSet emptyVarSet
+tyCoVarsOfType ty = nonDetFVSet (typeFVs ty)
 
-tyCoVarsOfTypes :: [Type] -> TyCoVarSet
-tyCoVarsOfTypes tys = ty_co_vars_of_types tys emptyVarSet emptyVarSet
 
-ty_co_vars_of_type :: Type -> TyCoVarSet -> TyCoVarSet -> TyCoVarSet
-ty_co_vars_of_type (TyVarTy v) is acc
-  | v `elemVarSet` is  = acc
-  | v `elemVarSet` acc = acc
-  | otherwise          = ty_co_vars_of_type (tyVarKind v)
-                            emptyVarSet  -- See Note [Closing over free variable kinds]
-                            (extendVarSet acc v)
-
-ty_co_vars_of_type (TyConApp _ tys)   is acc = ty_co_vars_of_types tys is acc
-ty_co_vars_of_type (LitTy {})         _  acc = acc
-ty_co_vars_of_type (AppTy fun arg)    is acc = ty_co_vars_of_type fun is (ty_co_vars_of_type arg is acc)
-ty_co_vars_of_type (FunTy _ arg res)  is acc = ty_co_vars_of_type arg is (ty_co_vars_of_type res is acc)
-ty_co_vars_of_type (ForAllTy (Bndr tv _) ty) is acc = ty_co_vars_of_type (varType tv) is $
-                                                      ty_co_vars_of_type ty (extendVarSet is tv) acc
-ty_co_vars_of_type (CastTy ty co)     is acc = ty_co_vars_of_type ty is (ty_co_vars_of_co co is acc)
-ty_co_vars_of_type (CoercionTy co)    is acc = ty_co_vars_of_co co is acc
-
-ty_co_vars_of_types :: [Type] -> TyCoVarSet -> TyCoVarSet -> TyCoVarSet
-ty_co_vars_of_types []       _  acc = acc
-ty_co_vars_of_types (ty:tys) is acc = ty_co_vars_of_type ty is (ty_co_vars_of_types tys is acc)
+tyCoVarsOfTypes :: [Type] -> TyCoVarSet
+tyCoVarsOfTypes tys = nonDetFVSet $ mconcat $ fmap typeFVs tys
 
 tyCoVarsOfCo :: Coercion -> TyCoVarSet
 -- See Note [Free variables of types]
-tyCoVarsOfCo co = ty_co_vars_of_co co emptyVarSet emptyVarSet
-
-tyCoVarsOfCos :: [Coercion] -> TyCoVarSet
-tyCoVarsOfCos cos = ty_co_vars_of_cos cos emptyVarSet emptyVarSet
-
-
-ty_co_vars_of_co :: Coercion -> TyCoVarSet -> TyCoVarSet -> TyCoVarSet
-ty_co_vars_of_co (Refl ty)            is acc = ty_co_vars_of_type ty is acc
-ty_co_vars_of_co (GRefl _ ty mco)     is acc = ty_co_vars_of_type ty is $
-                                               ty_co_vars_of_mco mco is acc
-ty_co_vars_of_co (TyConAppCo _ _ cos) is acc = ty_co_vars_of_cos cos is acc
-ty_co_vars_of_co (AppCo co arg)       is acc = ty_co_vars_of_co co is $
-                                               ty_co_vars_of_co arg is acc
-ty_co_vars_of_co (ForAllCo tv kind_co co) is acc = ty_co_vars_of_co kind_co is $
-                                                   ty_co_vars_of_co co (extendVarSet is tv) acc
-ty_co_vars_of_co (FunCo _ co1 co2)    is acc = ty_co_vars_of_co co1 is $
-                                               ty_co_vars_of_co co2 is acc
-ty_co_vars_of_co (CoVarCo v)          is acc = ty_co_vars_of_co_var v is acc
-ty_co_vars_of_co (HoleCo h)           is acc = ty_co_vars_of_co_var (coHoleCoVar h) is acc
-    -- See Note [CoercionHoles and coercion free variables]
-ty_co_vars_of_co (AxiomInstCo _ _ cos) is acc = ty_co_vars_of_cos cos is acc
-ty_co_vars_of_co (UnivCo p _ t1 t2)    is acc = ty_co_vars_of_prov p is $
-                                                ty_co_vars_of_type t1 is $
-                                                ty_co_vars_of_type t2 is acc
-ty_co_vars_of_co (SymCo co)          is acc = ty_co_vars_of_co co is acc
-ty_co_vars_of_co (TransCo co1 co2)   is acc = ty_co_vars_of_co co1 is $
-                                              ty_co_vars_of_co co2 is acc
-ty_co_vars_of_co (NthCo _ _ co)      is acc = ty_co_vars_of_co co is acc
-ty_co_vars_of_co (LRCo _ co)         is acc = ty_co_vars_of_co co is acc
-ty_co_vars_of_co (InstCo co arg)     is acc = ty_co_vars_of_co co is $
-                                              ty_co_vars_of_co arg is acc
-ty_co_vars_of_co (KindCo co)         is acc = ty_co_vars_of_co co is acc
-ty_co_vars_of_co (SubCo co)          is acc = ty_co_vars_of_co co is acc
-ty_co_vars_of_co (AxiomRuleCo _ cs)  is acc = ty_co_vars_of_cos cs is acc
-
-ty_co_vars_of_mco :: MCoercion -> TyCoVarSet -> TyCoVarSet -> TyCoVarSet
-ty_co_vars_of_mco MRefl    _is acc = acc
-ty_co_vars_of_mco (MCo co) is  acc = ty_co_vars_of_co co is acc
-
-ty_co_vars_of_co_var :: CoVar -> TyCoVarSet -> TyCoVarSet -> TyCoVarSet
-ty_co_vars_of_co_var v is acc
-  | v `elemVarSet` is  = acc
-  | v `elemVarSet` acc = acc
-  | otherwise          = ty_co_vars_of_type (varType v)
-                            emptyVarSet  -- See Note [Closing over free variable kinds]
-                            (extendVarSet acc v)
+tyCoVarsOfCo co = nonDetFVSet (coFVs co)
 
-ty_co_vars_of_cos :: [Coercion] -> TyCoVarSet -> TyCoVarSet -> TyCoVarSet
-ty_co_vars_of_cos []       _  acc = acc
-ty_co_vars_of_cos (co:cos) is acc = ty_co_vars_of_co co is (ty_co_vars_of_cos cos is acc)
 
-tyCoVarsOfProv :: UnivCoProvenance -> TyCoVarSet
-tyCoVarsOfProv prov = ty_co_vars_of_prov prov emptyVarSet emptyVarSet
+tyCoVarsOfCos :: [Coercion] -> TyCoVarSet
+tyCoVarsOfCos cos = nonDetFVSet (cosFVs cos)
 
-ty_co_vars_of_prov :: UnivCoProvenance -> TyCoVarSet -> TyCoVarSet -> TyCoVarSet
-ty_co_vars_of_prov (PhantomProv co)    is acc = ty_co_vars_of_co co is acc
-ty_co_vars_of_prov (ProofIrrelProv co) is acc = ty_co_vars_of_co co is acc
-ty_co_vars_of_prov UnsafeCoerceProv    _  acc = acc
-ty_co_vars_of_prov (PluginProv _)      _  acc = acc
 
 -- | Generates an in-scope set from the free variables in a list of types
 -- and a list of coercions
 mkTyCoInScopeSet :: [Type] -> [Coercion] -> InScopeSet
 mkTyCoInScopeSet tys cos
-  = mkInScopeSet (ty_co_vars_of_types tys emptyVarSet $
-                  ty_co_vars_of_cos   cos emptyVarSet emptyVarSet)
+  = mkInScopeSet (nonDetFVSet $ foldMap typeFVs tys <> cosFVs cos)
 
 -- | `tyCoFVsOfType` that returns free variables of a type in a deterministic
 -- set. For explanation of why using `VarSet` is not deterministic see
@@ -384,37 +315,55 @@ exactTyCoVarsOfTypes tys = mapUnionVarSet exactTyCoVarsOfType tys
 -- See Note [FV eta expansion] in FV for explanation.
 tyCoFVsOfType :: Type -> FV
 -- See Note [Free variables of types]
-tyCoFVsOfType (TyVarTy v)        f bound_vars (acc_list, acc_set)
-  | not (f v) = (acc_list, acc_set)
-  | v `elemVarSet` bound_vars = (acc_list, acc_set)
-  | v `elemVarSet` acc_set = (acc_list, acc_set)
-  | otherwise = tyCoFVsOfType (tyVarKind v) f
-                               emptyVarSet   -- See Note [Closing over free variable kinds]
-                               (v:acc_list, extendVarSet acc_set v)
-tyCoFVsOfType (TyConApp _ tys)   f bound_vars acc = tyCoFVsOfTypes tys f bound_vars acc
-tyCoFVsOfType (LitTy {})         f bound_vars acc = emptyFV f bound_vars acc
-tyCoFVsOfType (AppTy fun arg)    f bound_vars acc = (tyCoFVsOfType fun `unionFV` tyCoFVsOfType arg) f bound_vars acc
-tyCoFVsOfType (FunTy _ arg res)  f bound_vars acc = (tyCoFVsOfType arg `unionFV` tyCoFVsOfType res) f bound_vars acc
-tyCoFVsOfType (ForAllTy bndr ty) f bound_vars acc = tyCoFVsBndr bndr (tyCoFVsOfType ty)  f bound_vars acc
-tyCoFVsOfType (CastTy ty co)     f bound_vars acc = (tyCoFVsOfType ty `unionFV` tyCoFVsOfCo co) f bound_vars acc
-tyCoFVsOfType (CoercionTy co)    f bound_vars acc = tyCoFVsOfCo co f bound_vars acc
-
-tyCoFVsBndr :: TyCoVarBinder -> FV -> FV
--- Free vars of (forall b. <thing with fvs>)
-tyCoFVsBndr (Bndr tv _) fvs = tyCoFVsVarBndr tv fvs
-
-tyCoFVsVarBndrs :: [Var] -> FV -> FV
+tyCoFVsOfType = typeFVs
+
+typeFVs :: FreeVarStrategy m => Type -> m
+typeFVs (TyVarTy v)        = unitFV v
+typeFVs (TyConApp _ tys)   = foldMap typeFVs tys
+typeFVs (LitTy {})         = mempty
+typeFVs (AppTy fun arg)    = typeFVs fun <> typeFVs arg
+typeFVs (FunTy _ arg res)  = typeFVs arg <> typeFVs res
+typeFVs (ForAllTy bndr ty) = tyCoFVsBndr bndr (typeFVs ty)
+typeFVs (CastTy ty co)     = typeFVs ty <> coFVs co
+typeFVs (CoercionTy co)    = coFVs co
+{-# SPECIALISE typeFVs :: Type -> FV #-}
+{-# SPECIALISE typeFVs :: Type -> NonDetFV #-}
+{-# SPECIALISE typeFVs :: Type -> LocalFV #-}
+{-# SPECIALISE typeFVs :: Type -> LocalNonDetFV #-}
+{-# SPECIALISE typeFVs :: Type -> NoFVs #-}
+
+-- | Free vars of (forall b. <thing with fvs>)
+tyCoFVsBndr :: FreeVarStrategy m => TyCoVarBinder -> m -> m
+tyCoFVsBndr (Bndr tv _) = tyCoFVsVarBndr tv
+{-# SPECIALISE tyCoFVsBndr :: TyCoVarBinder -> FV -> FV #-}
+{-# SPECIALISE tyCoFVsBndr :: TyCoVarBinder -> NonDetFV -> NonDetFV #-}
+{-# SPECIALISE tyCoFVsBndr :: TyCoVarBinder -> LocalFV -> LocalFV #-}
+{-# SPECIALISE tyCoFVsBndr :: TyCoVarBinder -> LocalNonDetFV -> LocalNonDetFV #-}
+{-# SPECIALISE tyCoFVsBndr :: TyCoVarBinder -> NoFVs -> NoFVs #-}
+
+tyCoFVsVarBndrs :: FreeVarStrategy m => [Var] -> m -> m
 tyCoFVsVarBndrs vars fvs = foldr tyCoFVsVarBndr fvs vars
+{-# SPECIALISE tyCoFVsVarBndrs :: [Var] -> FV -> FV #-}
+{-# SPECIALISE tyCoFVsVarBndrs :: [Var] -> NonDetFV -> NonDetFV #-}
+{-# SPECIALISE tyCoFVsVarBndrs :: [Var] -> LocalFV -> LocalFV #-}
+{-# SPECIALISE tyCoFVsVarBndrs :: [Var] -> LocalNonDetFV -> LocalNonDetFV #-}
+{-# SPECIALISE tyCoFVsVarBndrs :: [Var] -> NoFVs -> NoFVs #-}
 
-tyCoFVsVarBndr :: Var -> FV -> FV
+
+tyCoFVsVarBndr :: FreeVarStrategy m => Var -> m -> m
 tyCoFVsVarBndr var fvs
-  = tyCoFVsOfType (varType var)   -- Free vars of its type/kind
-    `unionFV` delFV var fvs       -- Delete it from the thing-inside
+  = typeFVs (varType var)   -- Free vars of its type/kind
+    <> bindVar var fvs       -- Delete it from the thing-inside
+{-# SPECIALISE tyCoFVsVarBndr :: Var -> FV -> FV #-}
+{-# SPECIALISE tyCoFVsVarBndr :: Var -> NonDetFV -> NonDetFV #-}
+{-# SPECIALISE tyCoFVsVarBndr :: Var -> LocalFV -> LocalFV #-}
+{-# SPECIALISE tyCoFVsVarBndr :: Var -> LocalNonDetFV -> LocalNonDetFV #-}
+{-# SPECIALISE tyCoFVsVarBndr :: Var -> NoFVs -> NoFVs #-}
+
 
-tyCoFVsOfTypes :: [Type] -> FV
+tyCoFVsOfTypes :: FreeVarStrategy m => [Type] -> m
 -- See Note [Free variables of types]
-tyCoFVsOfTypes (ty:tys) fv_cand in_scope acc = (tyCoFVsOfType ty `unionFV` tyCoFVsOfTypes tys) fv_cand in_scope acc
-tyCoFVsOfTypes []       fv_cand in_scope acc = emptyFV fv_cand in_scope acc
+tyCoFVsOfTypes = foldMap typeFVs
 
 -- | Get a deterministic set of the vars free in a coercion
 tyCoVarsOfCoDSet :: Coercion -> DTyCoVarSet
@@ -425,10 +374,6 @@ tyCoVarsOfCoList :: Coercion -> [TyCoVar]
 -- See Note [Free variables of types]
 tyCoVarsOfCoList co = fvVarList $ tyCoFVsOfCo co
 
-tyCoFVsOfMCo :: MCoercion -> FV
-tyCoFVsOfMCo MRefl    = emptyFV
-tyCoFVsOfMCo (MCo co) = tyCoFVsOfCo co
-
 tyCoVarsOfCosSet :: CoVarEnv Coercion -> TyCoVarSet
 tyCoVarsOfCosSet cos = tyCoVarsOfCos $ nonDetEltsUFM cos
   -- It's OK to use nonDetEltsUFM here because we immediately forget the
@@ -437,48 +382,58 @@ tyCoVarsOfCosSet cos = tyCoVarsOfCos $ nonDetEltsUFM cos
 tyCoFVsOfCo :: Coercion -> FV
 -- Extracts type and coercion variables from a coercion
 -- See Note [Free variables of types]
-tyCoFVsOfCo (Refl ty) fv_cand in_scope acc
-  = tyCoFVsOfType ty fv_cand in_scope acc
-tyCoFVsOfCo (GRefl _ ty mco) fv_cand in_scope acc
-  = (tyCoFVsOfType ty `unionFV` tyCoFVsOfMCo mco) fv_cand in_scope acc
-tyCoFVsOfCo (TyConAppCo _ _ cos) fv_cand in_scope acc = tyCoFVsOfCos cos fv_cand in_scope acc
-tyCoFVsOfCo (AppCo co arg) fv_cand in_scope acc
-  = (tyCoFVsOfCo co `unionFV` tyCoFVsOfCo arg) fv_cand in_scope acc
-tyCoFVsOfCo (ForAllCo tv kind_co co) fv_cand in_scope acc
-  = (tyCoFVsVarBndr tv (tyCoFVsOfCo co) `unionFV` tyCoFVsOfCo kind_co) fv_cand in_scope acc
-tyCoFVsOfCo (FunCo _ co1 co2)    fv_cand in_scope acc
-  = (tyCoFVsOfCo co1 `unionFV` tyCoFVsOfCo co2) fv_cand in_scope acc
-tyCoFVsOfCo (CoVarCo v) fv_cand in_scope acc
-  = tyCoFVsOfCoVar v fv_cand in_scope acc
-tyCoFVsOfCo (HoleCo h) fv_cand in_scope acc
-  = tyCoFVsOfCoVar (coHoleCoVar h) fv_cand in_scope acc
-    -- See Note [CoercionHoles and coercion free variables]
-tyCoFVsOfCo (AxiomInstCo _ _ cos) fv_cand in_scope acc = tyCoFVsOfCos cos fv_cand in_scope acc
-tyCoFVsOfCo (UnivCo p _ t1 t2) fv_cand in_scope acc
-  = (tyCoFVsOfProv p `unionFV` tyCoFVsOfType t1
-                     `unionFV` tyCoFVsOfType t2) fv_cand in_scope acc
-tyCoFVsOfCo (SymCo co)          fv_cand in_scope acc = tyCoFVsOfCo co fv_cand in_scope acc
-tyCoFVsOfCo (TransCo co1 co2)   fv_cand in_scope acc = (tyCoFVsOfCo co1 `unionFV` tyCoFVsOfCo co2) fv_cand in_scope acc
-tyCoFVsOfCo (NthCo _ _ co)      fv_cand in_scope acc = tyCoFVsOfCo co fv_cand in_scope acc
-tyCoFVsOfCo (LRCo _ co)         fv_cand in_scope acc = tyCoFVsOfCo co fv_cand in_scope acc
-tyCoFVsOfCo (InstCo co arg)     fv_cand in_scope acc = (tyCoFVsOfCo co `unionFV` tyCoFVsOfCo arg) fv_cand in_scope acc
-tyCoFVsOfCo (KindCo co)         fv_cand in_scope acc = tyCoFVsOfCo co fv_cand in_scope acc
-tyCoFVsOfCo (SubCo co)          fv_cand in_scope acc = tyCoFVsOfCo co fv_cand in_scope acc
-tyCoFVsOfCo (AxiomRuleCo _ cs)  fv_cand in_scope acc = tyCoFVsOfCos cs fv_cand in_scope acc
-
-tyCoFVsOfCoVar :: CoVar -> FV
-tyCoFVsOfCoVar v fv_cand in_scope acc
-  = (unitFV v `unionFV` tyCoFVsOfType (varType v)) fv_cand in_scope acc
-
-tyCoFVsOfProv :: UnivCoProvenance -> FV
-tyCoFVsOfProv UnsafeCoerceProv    fv_cand in_scope acc = emptyFV fv_cand in_scope acc
-tyCoFVsOfProv (PhantomProv co)    fv_cand in_scope acc = tyCoFVsOfCo co fv_cand in_scope acc
-tyCoFVsOfProv (ProofIrrelProv co) fv_cand in_scope acc = tyCoFVsOfCo co fv_cand in_scope acc
-tyCoFVsOfProv (PluginProv _)      fv_cand in_scope acc = emptyFV fv_cand in_scope acc
+tyCoFVsOfCo = coFVs
 
 tyCoFVsOfCos :: [Coercion] -> FV
-tyCoFVsOfCos []       fv_cand in_scope acc = emptyFV fv_cand in_scope acc
-tyCoFVsOfCos (co:cos) fv_cand in_scope acc = (tyCoFVsOfCo co `unionFV` tyCoFVsOfCos cos) fv_cand in_scope acc
+tyCoFVsOfCos = cosFVs
+
+cosFVs :: FreeVarStrategy m => [Coercion] -> m
+cosFVs cos = mconcat $ fmap coFVs cos
+
+coFVs :: FreeVarStrategy m => Coercion -> m
+coFVs (Refl ty) = typeFVs ty
+coFVs (GRefl _ ty mco) = typeFVs ty <> mcoFVs mco
+coFVs (CoVarCo cv) = unitFV cv
+coFVs (TyConAppCo _ _ cos) = cosFVs cos
+coFVs (AppCo co arg) = coFVs co <> coFVs arg
+coFVs (ForAllCo tv kind_co co) = tyCoFVsVarBndr tv (coFVs co) <> coFVs kind_co
+coFVs (FunCo _ co1 co2) = coFVs co1 <> coFVs co2
+coFVs (HoleCo hole) = coholeFV hole
+coFVs (AxiomInstCo _ _ cos) = cosFVs cos
+coFVs (UnivCo p _ t1 t2) = provFVs p <> typeFVs t1 <> typeFVs t2
+coFVs (SymCo co) = coFVs co
+coFVs (TransCo co1 co2) = coFVs co1 <> coFVs co2
+coFVs (NthCo _ _ co) = coFVs co
+coFVs (LRCo _ co) = coFVs co
+coFVs (InstCo co arg) = coFVs co <> coFVs arg
+coFVs (KindCo co) = coFVs co
+coFVs (SubCo co) = coFVs co
+coFVs (AxiomRuleCo _ cos) = cosFVs cos
+{-# SPECIALISE coFVs :: Coercion -> FV #-}
+{-# SPECIALISE coFVs :: Coercion -> NonDetFV #-}
+{-# SPECIALISE coFVs :: Coercion -> LocalFV #-}
+{-# SPECIALISE coFVs :: Coercion -> LocalNonDetFV #-}
+{-# SPECIALISE coFVs :: Coercion -> NoFVs #-}
+
+mcoFVs :: FreeVarStrategy m => MCoercion -> m
+mcoFVs MRefl = mempty
+mcoFVs (MCo co) = coFVs co
+{-# SPECIALISE mcoFVs :: MCoercion -> FV #-}
+{-# SPECIALISE mcoFVs :: MCoercion -> NonDetFV #-}
+{-# SPECIALISE mcoFVs :: MCoercion -> LocalFV #-}
+{-# SPECIALISE mcoFVs :: MCoercion -> LocalNonDetFV #-}
+{-# SPECIALISE mcoFVs :: MCoercion -> NoFVs #-}
+
+provFVs :: FreeVarStrategy m => UnivCoProvenance -> m
+provFVs (PhantomProv co)    = coFVs co
+provFVs (ProofIrrelProv co) = coFVs co
+provFVs UnsafeCoerceProv    = mempty
+provFVs (PluginProv _)      = mempty
+{-# SPECIALISE provFVs :: UnivCoProvenance -> FV #-}
+{-# SPECIALISE provFVs :: UnivCoProvenance -> NonDetFV #-}
+{-# SPECIALISE provFVs :: UnivCoProvenance -> LocalFV #-}
+{-# SPECIALISE provFVs :: UnivCoProvenance -> LocalNonDetFV #-}
+{-# SPECIALISE provFVs :: UnivCoProvenance -> NoFVs #-}
 
 
 ------------- Extracting the CoVars of a type or coercion -----------
@@ -501,20 +456,17 @@ See #14880.
 
 -}
 
-getCoVarSet :: FV -> CoVarSet
-getCoVarSet fv = snd (fv isCoVar emptyVarSet ([], emptyVarSet))
-
 coVarsOfType :: Type -> CoVarSet
-coVarsOfType ty = getCoVarSet (tyCoFVsOfType ty)
+coVarsOfType ty = nonDetCoFVSet (typeFVs ty)
 
 coVarsOfTypes :: [Type] -> TyCoVarSet
-coVarsOfTypes tys = getCoVarSet (tyCoFVsOfTypes tys)
+coVarsOfTypes tys = nonDetCoFVSet (mconcat $ fmap typeFVs tys)
 
 coVarsOfCo :: Coercion -> CoVarSet
-coVarsOfCo co = getCoVarSet (tyCoFVsOfCo co)
+coVarsOfCo co = nonDetCoFVSet (coFVs co)
 
 coVarsOfCos :: [Coercion] -> CoVarSet
-coVarsOfCos cos = getCoVarSet (tyCoFVsOfCos cos)
+coVarsOfCos cos = nonDetCoFVSet (cosFVs cos)
 
 ----- Whether a covar is /Almost Devoid/ in a type or coercion ----
 
@@ -648,12 +600,12 @@ injectiveVarsOfType look_under_tfs = go
       case tyConInjectivityInfo tc of
         Injective inj
           |  look_under_tfs || not (isTypeFamilyTyCon tc)
-          -> mapUnionFV go $
+          -> foldMap go $
              filterByList (inj ++ repeat True) tys
                          -- Oversaturated arguments to a tycon are
                          -- always injective, hence the repeat True
         _ -> emptyFV
-    go (ForAllTy (Bndr tv _) ty) = go (tyVarKind tv) `unionFV` delFV tv (go ty)
+    go (ForAllTy (Bndr tv _) ty) = go (tyVarKind tv) <> delFV tv (go ty)
     go LitTy{}                   = emptyFV
     go (CastTy ty _)             = go ty
     go CoercionTy{}              = emptyFV
@@ -668,11 +620,9 @@ injectiveVarsOfType look_under_tfs = go
 -- * Ignoring the non-injective fields of a 'TyConApp'
 --
 -- See @Note [When does a tycon application need an explicit kind signature?]@.
-injectiveVarsOfTypes :: Bool -- ^ look under injective type families?
-                             -- See Note [Coverage condition for injective type families]
-                             -- in FamInst.
-                     -> [Type] -> FV
-injectiveVarsOfTypes look_under_tfs = mapUnionFV (injectiveVarsOfType look_under_tfs)
+injectiveVarsOfTypes :: Bool -> [Type] -> FV
+injectiveVarsOfTypes look_under_tfs tys =
+    mapUnionFV (injectiveVarsOfType look_under_tfs) tys
 
 
 ------------- Invisible vars -----------------
@@ -710,18 +660,7 @@ invisibleVarsOfTypes = mapUnionFV invisibleVarsOfType
 -- | Returns True if this type has no free variables. Should be the same as
 -- isEmptyVarSet . tyCoVarsOfType, but faster in the non-forall case.
 noFreeVarsOfType :: Type -> Bool
-noFreeVarsOfType (TyVarTy _)      = False
-noFreeVarsOfType (AppTy t1 t2)    = noFreeVarsOfType t1 && noFreeVarsOfType t2
-noFreeVarsOfType (TyConApp _ tys) = all noFreeVarsOfType tys
-noFreeVarsOfType ty@(ForAllTy {}) = isEmptyVarSet (tyCoVarsOfType ty)
-noFreeVarsOfType (FunTy _ t1 t2)  = noFreeVarsOfType t1 && noFreeVarsOfType t2
-noFreeVarsOfType (LitTy _)        = True
-noFreeVarsOfType (CastTy ty co)   = noFreeVarsOfType ty && noFreeVarsOfCo co
-noFreeVarsOfType (CoercionTy co)  = noFreeVarsOfCo co
-
-noFreeVarsOfMCo :: MCoercion -> Bool
-noFreeVarsOfMCo MRefl    = True
-noFreeVarsOfMCo (MCo co) = noFreeVarsOfCo co
+noFreeVarsOfType t = noFVs (typeFVs t)
 
 noFreeVarsOfTypes :: [Type] -> Bool
 noFreeVarsOfTypes = all noFreeVarsOfType
@@ -729,34 +668,7 @@ noFreeVarsOfTypes = all noFreeVarsOfType
 -- | Returns True if this coercion has no free variables. Should be the same as
 -- isEmptyVarSet . tyCoVarsOfCo, but faster in the non-forall case.
 noFreeVarsOfCo :: Coercion -> Bool
-noFreeVarsOfCo (Refl ty)              = noFreeVarsOfType ty
-noFreeVarsOfCo (GRefl _ ty co)        = noFreeVarsOfType ty && noFreeVarsOfMCo co
-noFreeVarsOfCo (TyConAppCo _ _ args)  = all noFreeVarsOfCo args
-noFreeVarsOfCo (AppCo c1 c2)          = noFreeVarsOfCo c1 && noFreeVarsOfCo c2
-noFreeVarsOfCo co@(ForAllCo {})       = isEmptyVarSet (tyCoVarsOfCo co)
-noFreeVarsOfCo (FunCo _ c1 c2)        = noFreeVarsOfCo c1 && noFreeVarsOfCo c2
-noFreeVarsOfCo (CoVarCo _)            = False
-noFreeVarsOfCo (HoleCo {})            = True    -- I'm unsure; probably never happens
-noFreeVarsOfCo (AxiomInstCo _ _ args) = all noFreeVarsOfCo args
-noFreeVarsOfCo (UnivCo p _ t1 t2)     = noFreeVarsOfProv p &&
-                                        noFreeVarsOfType t1 &&
-                                        noFreeVarsOfType t2
-noFreeVarsOfCo (SymCo co)             = noFreeVarsOfCo co
-noFreeVarsOfCo (TransCo co1 co2)      = noFreeVarsOfCo co1 && noFreeVarsOfCo co2
-noFreeVarsOfCo (NthCo _ _ co)         = noFreeVarsOfCo co
-noFreeVarsOfCo (LRCo _ co)            = noFreeVarsOfCo co
-noFreeVarsOfCo (InstCo co1 co2)       = noFreeVarsOfCo co1 && noFreeVarsOfCo co2
-noFreeVarsOfCo (KindCo co)            = noFreeVarsOfCo co
-noFreeVarsOfCo (SubCo co)             = noFreeVarsOfCo co
-noFreeVarsOfCo (AxiomRuleCo _ cs)     = all noFreeVarsOfCo cs
-
--- | Returns True if this UnivCoProv has no free variables. Should be the same as
--- isEmptyVarSet . tyCoVarsOfProv, but faster in the non-forall case.
-noFreeVarsOfProv :: UnivCoProvenance -> Bool
-noFreeVarsOfProv UnsafeCoerceProv    = True
-noFreeVarsOfProv (PhantomProv co)    = noFreeVarsOfCo co
-noFreeVarsOfProv (ProofIrrelProv co) = noFreeVarsOfCo co
-noFreeVarsOfProv (PluginProv {})     = True
+noFreeVarsOfCo co = noFVs (coFVs co)
 
 {-
 %************************************************************************
diff --git a/compiler/types/TyCoFVs.hs-boot b/compiler/types/TyCoFVs.hs-boot
new file mode 100644
index 0000000000..87273545b9
--- /dev/null
+++ b/compiler/types/TyCoFVs.hs-boot
@@ -0,0 +1,7 @@
+module TyCoFVs where
+
+import TyCoRep (Type)
+import FreeVarStrategy
+
+typeFVs :: FreeVarStrategy m => Type -> m
+
diff --git a/compiler/types/TyCoRep.hs-boot b/compiler/types/TyCoRep.hs-boot
index 0050dcd26b..c1c2320406 100644
--- a/compiler/types/TyCoRep.hs-boot
+++ b/compiler/types/TyCoRep.hs-boot
@@ -6,6 +6,7 @@ import {-# SOURCE #-} Var( Var, ArgFlag, AnonArgFlag )
 data Type
 data TyThing
 data Coercion
+data CoercionHole
 data UnivCoProvenance
 data TyLit
 data TyCoBinder
@@ -20,4 +21,6 @@ type MCoercionN = MCoercion
 mkFunTy   :: AnonArgFlag -> Type -> Type -> Type
 mkForAllTy :: Var -> ArgFlag -> Type -> Type
 
+coHoleCoVar :: CoercionHole -> Var
+
 instance Data Type  -- To support Data instances in CoAxiom
diff --git a/compiler/utils/FV.hs b/compiler/utils/FV.hs
index 6d0dc2b2ab..debb1c9880 100644
--- a/compiler/utils/FV.hs
+++ b/compiler/utils/FV.hs
@@ -1,201 +1,290 @@
-{-
-(c) Bartosz Nitka, Facebook 2015
-
-Utilities for efficiently and deterministically computing free variables.
-
--}
-
+{-# OPTIONS_GHC -ddump-to-file -ddump-simpl -ddump-stg -dsuppress-ticks #-}
+{-# LANGUAGE MultiWayIf #-}
 {-# LANGUAGE BangPatterns #-}
+{-# LANGUAGE GeneralizedNewtypeDeriving #-}
+{-# LANGUAGE ScopedTypeVariables #-}
 
-module FV (
-        -- * Deterministic free vars computations
-        FV, InterestingVarFun,
-
-        -- * Running the computations
-        fvVarListVarSet, fvVarList, fvVarSet, fvDVarSet,
-
-        -- ** Manipulating those computations
-        unitFV,
-        emptyFV,
-        mkFVs,
-        unionFV,
-        unionsFV,
-        delFV,
-        delFVs,
-        filterFV,
-        mapUnionFV,
-    ) where
+module FV
+  ( -- | An abstraction over free variable computations
+    FreeVarStrategy(..)
+    -- * Are there any free variables at all?
+  , NoFVs, noFVs
+    -- * Deterministic free variable computation
+  , FV
+  , fvVarListVarSet
+  , fvVarList
+  , fvDVarSet
+  , fvVarSet
+  , filterFV
+  , InterestingVarFun
+  , emptyFV
+  , delFV
+  , delFVs
+  , unionFV, mapUnionFV, mkFVs
+    -- ** Internal
+  , runFV, FVAccum(..), emptyFVAccum
+    -- * Non-deterministic free variable computation
+  , NonDetFV
+  , nonDetFVSet
+    -- * Non-deterministic free coercion variable computation
+  , NonDetCoFV
+  , nonDetCoFVSet
+    -- * Filtered free variable computations
+  , FilteredFV
+    -- ** Filtered to local variables
+  , LocalFV
+  , LocalNonDetFV
+  , localFVs
+  , localFvVarSet
+  ) where
 
 import GhcPrelude
+import GHC.Exts (oneShot)
 
+import FreeVarStrategy
+
+import {-# SOURCE #-} TyCoRep (coHoleCoVar)
+import {-# SOURCE #-} TyCoFVs (typeFVs)
 import Var
 import VarSet
 
--- | Predicate on possible free variables: returns @True@ iff the variable is
--- interesting
-type InterestingVarFun = Var -> Bool
+import Data.Proxy
+import Data.Semigroup (Semigroup((<>)))
 
--- Note [Deterministic FV]
--- ~~~~~~~~~~~~~~~~~~~~~~~
--- When computing free variables, the order in which you get them affects
--- the results of floating and specialization. If you use UniqFM to collect
--- them and then turn that into a list, you get them in nondeterministic
--- order as described in Note [Deterministic UniqFM] in UniqDFM.
-
--- A naive algorithm for free variables relies on merging sets of variables.
--- Merging costs O(n+m) for UniqFM and for UniqDFM there's an additional log
--- factor. It's cheaper to incrementally add to a list and use a set to check
--- for duplicates.
-type FV = InterestingVarFun
-             -- Used for filtering sets as we build them
-          -> VarSet
-             -- Locally bound variables
-          -> ([Var], VarSet)
-             -- List to preserve ordering and set to check for membership,
-             -- so that the list doesn't have duplicates
-             -- For explanation of why using `VarSet` is not deterministic see
-             -- Note [Deterministic UniqFM] in UniqDFM.
-          -> ([Var], VarSet)
-
--- Note [FV naming conventions]
--- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--- To get the performance and determinism that FV provides, FV computations
--- need to built up from smaller FV computations and then evaluated with
--- one of `fvVarList`, `fvDVarSet`, `fvVarListVarSet`. That means the functions
--- returning FV need to be exported.
+
+--------------------------------------------------------------------------------
+-- Checking for empty free variable sets
+--------------------------------------------------------------------------------
+
+-- | A free variables traversal that checks whether the free variable set is empty.
 --
--- The conventions are:
+-- Note that this does *not* account for variables free in the type/kind of
+-- variable occurrences.
+newtype NoFVs = NoFVs (VarSet -> Bool)
+
+instance Monoid NoFVs where
+  mempty = NoFVs $ const True
+  {-# INLINE mempty #-}
+
+instance Semigroup NoFVs where
+  NoFVs f <> NoFVs g = NoFVs $ oneShot $ \in_scope -> f in_scope && g in_scope
+  {-# INLINE (<>) #-}
+
+instance FreeVarStrategy NoFVs where
+  coholeFV _hole = mempty
+  unitFV v = NoFVs $ \in_scope -> v `elemVarSet` in_scope
+  bindVar tv (NoFVs f) = NoFVs $ \in_scope -> f $! extendVarSet in_scope tv
+
+  {-# INLINE coholeFV #-}
+  {-# INLINE unitFV #-}
+  {-# INLINE bindVar #-}
+
+noFVs :: NoFVs -> Bool
+noFVs (NoFVs f) = f emptyVarSet
+
+
+--------------------------------------------------------------------------------
+-- Non-deterministic free variable sets
+--------------------------------------------------------------------------------
+
+-- | A free variables traversal that produces a non-deterministic 'TyCoVarSet'.
 --
--- a) non-deterministic functions:
---   * a function that returns VarSet
---       e.g. `tyVarsOfType`
--- b) deterministic functions:
---   * a worker that returns FV
---       e.g. `tyFVsOfType`
---   * a function that returns [Var]
---       e.g. `tyVarsOfTypeList`
---   * a function that returns DVarSet
---       e.g. `tyVarsOfTypeDSet`
+-- As described in Note [Closing over free variables kinds] this closes over
+-- the free variables of type variables' kinds.
+newtype NonDetFV = NonDetFV { runNonDetFV :: TyCoVarSet -> TyCoVarSet -> TyCoVarSet }
+
+instance Monoid NonDetFV where
+  mempty = NonDetFV $ \_ acc -> acc
+  {-# INLINE mempty #-}
+  mconcat xs = NonDetFV $ oneShot $ \is -> oneShot $ \acc0 ->
+    foldl' (\acc f -> runNonDetFV f is acc) acc0 xs
+  {-# INLINE mconcat #-}
+
+instance Semigroup NonDetFV where
+  NonDetFV f <> NonDetFV g = NonDetFV $ oneShot $ \is -> oneShot $ \acc -> f is $! (g is $! acc)
+  {-# INLINE (<>) #-}
+
+instance FreeVarStrategy NonDetFV where
+  coholeFV hole = unitFV $ coHoleCoVar hole
+  unitFV v = NonDetFV $ oneShot $ \is -> oneShot $ \acc ->
+    if | v `elemVarSet` is  -> acc
+       | v `elemVarSet` acc -> acc
+       | otherwise          -> runNonDetFV (typeFVs (varType v)) emptyVarSet $! extendVarSet acc v
+  bindVar v (NonDetFV f) = NonDetFV $ oneShot $ \is -> oneShot $ \acc -> (f $! extendVarSet is v) $! acc
+
+  {-# INLINE coholeFV #-}
+  {-# INLINE unitFV #-}
+  {-# INLINE bindVar #-}
+
+nonDetFVSet :: NonDetFV -> TyCoVarSet
+nonDetFVSet (NonDetFV f) = f emptyVarSet emptyVarSet
+
+
+--------------------------------------------------------------------------------
+-- Non-deterministic free coercion variable sets
+--------------------------------------------------------------------------------
+
+-- | A free coercion variables traversal that produces a non-deterministic
+-- 'CoVarSet'.
+newtype NonDetCoFV = NonDetCoFV { runNonDetCoFV :: CoVarSet -> CoVarSet -> CoVarSet }
+
+instance Monoid NonDetCoFV where
+  mempty = NonDetCoFV $ \_ acc -> acc
+  {-# INLINE mempty #-}
+
+instance Semigroup NonDetCoFV where
+  NonDetCoFV f <> NonDetCoFV g = NonDetCoFV $ oneShot $ \is -> oneShot $ \acc -> f is $! (g is $! acc)
+  {-# INLINE (<>) #-}
+
+instance FreeVarStrategy NonDetCoFV where
+  coholeFV hole = unitFV $ coHoleCoVar hole
+  unitFV v = NonDetCoFV $ \is acc ->
+    if | not (isCoVar v)    -> acc
+       | v `elemVarSet` is  -> acc
+       | v `elemVarSet` acc -> acc
+       | otherwise          -> runNonDetCoFV (typeFVs (varType v)) emptyVarSet $! extendVarSet acc v
+  bindVar v (NonDetCoFV f) = NonDetCoFV $ oneShot $ \is -> oneShot $ \acc -> (f $! extendVarSet is v) $! acc
+
+  {-# INLINE coholeFV #-}
+  {-# INLINE unitFV #-}
+  {-# INLINE bindVar #-}
+
+nonDetCoFVSet :: NonDetCoFV -> CoVarSet
+nonDetCoFVSet (NonDetCoFV f) = f emptyVarSet emptyVarSet
+
+
+--------------------------------------------------------------------------------
+-- Deterministic free variable sets
+--------------------------------------------------------------------------------
+
+type InterestingVarFun = Var -> Bool
+
+data FVAccum = FVAccum ![Var] !VarSet
+
+emptyFVAccum :: FVAccum
+emptyFVAccum = FVAccum [] emptyVarSet
+
+-- | A free variables traversal that produces a deterministic 'DVarSet
 --
--- Where tyVarsOfType, tyVarsOfTypeList, tyVarsOfTypeDSet are implemented
--- in terms of the worker evaluated with fvVarSet, fvVarList, fvDVarSet
--- respectively.
-
--- | Run a free variable computation, returning a list of distinct free
--- variables in deterministic order and a non-deterministic set containing
--- those variables.
-fvVarListVarSet :: FV ->  ([Var], VarSet)
-fvVarListVarSet fv = fv (const True) emptyVarSet ([], emptyVarSet)
-
--- | Run a free variable computation, returning a list of distinct free
--- variables in deterministic order.
+-- As described in Note [Closing over free variables kinds] this closes over
+-- the free variables of type variables' kinds.
+newtype FV = FV { runFV :: InterestingVarFun -> TyCoVarSet -> FVAccum -> FVAccum }
+
+instance Monoid FV where
+  mempty = FV $ \_ _ acc -> acc
+  {-# INLINE mempty #-}
+
+instance Semigroup FV where
+  f <> g = FV $ oneShot $ \fv_cand -> oneShot $ \in_scope -> oneShot $ \acc ->
+    runFV f fv_cand in_scope $! (runFV g fv_cand in_scope $! acc)
+  {-# INLINE (<>) #-}
+
+whenIsInteresting :: Var -> FV -> FV
+whenIsInteresting var f = FV $ oneShot g
+  where
+    g fv_cand in_scope acc@(FVAccum _have have_set)
+      | not (fv_cand var)          = acc
+      | var `elemVarSet` in_scope  = acc
+      | var `elemVarSet` have_set  = acc
+      | otherwise                  = runFV f fv_cand in_scope acc
+
+instance FreeVarStrategy FV where
+  coholeFV hole = unitFV $ coHoleCoVar hole
+  unitFV var = whenIsInteresting var $ typeFVs (varType var) <> add_fv var
+    where
+      add_fv :: Var -> FV
+      add_fv var = FV $ oneShot $ \_fv_cand -> oneShot $ \_in_scope -> oneShot $ \(FVAccum have have_set) ->
+        let !in_scope' = extendVarSet have_set var
+         in FVAccum (var : have) in_scope'
+  bindVar tv (FV f) = FV $ \fv_cand in_scope acc ->
+    let !in_scope' = extendVarSet in_scope tv
+     in f fv_cand in_scope' acc
+
+  {-# INLINE coholeFV #-}
+  {-# INLINE unitFV #-}
+  {-# INLINE bindVar #-}
+
+fvVarListVarSet :: FV -> ([Var], VarSet)
+fvVarListVarSet (FV fv) =
+  case fv (const True) emptyVarSet (FVAccum [] emptyVarSet) of
+    FVAccum have have_set -> (have, have_set)
+
 fvVarList :: FV -> [Var]
 fvVarList = fst . fvVarListVarSet
 
--- | Run a free variable computation, returning a deterministic set of free
--- variables. Note that this is just a wrapper around the version that
--- returns a deterministic list. If you need a list you should use
--- `fvVarList`.
 fvDVarSet :: FV -> DVarSet
-fvDVarSet = mkDVarSet . fst . fvVarListVarSet
+fvDVarSet fv = mkDVarSet $ fst $ fvVarListVarSet fv
 
--- | Run a free variable computation, returning a non-deterministic set of
--- free variables. Don't use if the set will be later converted to a list
--- and the order of that list will impact the generated code.
 fvVarSet :: FV -> VarSet
 fvVarSet = snd . fvVarListVarSet
 
--- Note [FV eta expansion]
--- ~~~~~~~~~~~~~~~~~~~~~~~
--- Let's consider an eta-reduced implementation of freeVarsOf using FV:
---
--- freeVarsOf (App a b) = freeVarsOf a `unionFV` freeVarsOf b
---
--- If GHC doesn't eta-expand it, after inlining unionFV we end up with
---
--- freeVarsOf = \x ->
---   case x of
---     App a b -> \fv_cand in_scope acc ->
---       freeVarsOf a fv_cand in_scope $! freeVarsOf b fv_cand in_scope $! acc
---
--- which has to create a thunk, resulting in more allocations.
---
--- On the other hand if it is eta-expanded:
---
--- freeVarsOf (App a b) fv_cand in_scope acc =
---   (freeVarsOf a `unionFV` freeVarsOf b) fv_cand in_scope acc
---
--- after inlining unionFV we have:
---
--- freeVarsOf = \x fv_cand in_scope acc ->
---   case x of
---     App a b ->
---       freeVarsOf a fv_cand in_scope $! freeVarsOf b fv_cand in_scope $! acc
---
--- which saves allocations.
---
--- GHC when presented with knowledge about all the call sites, correctly
--- eta-expands in this case. Unfortunately due to the fact that freeVarsOf gets
--- exported to be composed with other functions, GHC doesn't have that
--- information and has to be more conservative here.
---
--- Hence functions that get exported and return FV need to be manually
--- eta-expanded. See also #11146.
-
--- | Add a variable - when free, to the returned free variables.
--- Ignores duplicates and respects the filtering function.
-unitFV :: Id -> FV
-unitFV var fv_cand in_scope acc@(have, haveSet)
-  | var `elemVarSet` in_scope = acc
-  | var `elemVarSet` haveSet = acc
-  | fv_cand var = (var:have, extendVarSet haveSet var)
-  | otherwise = acc
-{-# INLINE unitFV #-}
+-- | Filter a free variable computation.
+filterFV :: InterestingVarFun -> FV -> FV
+filterFV fv_cand2 (FV fv) = FV $ \fv_cand1 in_scope acc ->
+  fv (\v -> fv_cand1 v && fv_cand2 v) in_scope acc
+{-# INLINE filterFV #-}
 
 -- | Return no free variables.
-emptyFV :: FV
-emptyFV _ _ acc = acc
+emptyFV :: FreeVarStrategy fv => fv
+emptyFV = mempty
 {-# INLINE emptyFV #-}
 
--- | Union two free variable computations.
-unionFV :: FV -> FV -> FV
-unionFV fv1 fv2 fv_cand in_scope acc =
-  fv1 fv_cand in_scope $! fv2 fv_cand in_scope $! acc
-{-# INLINE unionFV #-}
-
 -- | Mark the variable as not free by putting it in scope.
 delFV :: Var -> FV -> FV
-delFV var fv fv_cand !in_scope acc =
-  fv fv_cand (extendVarSet in_scope var) acc
+delFV = bindVar
 {-# INLINE delFV #-}
 
 -- | Mark many free variables as not free.
 delFVs :: VarSet -> FV -> FV
-delFVs vars fv fv_cand !in_scope acc =
+delFVs vars (FV fv) = FV $ \fv_cand !in_scope acc ->
   fv fv_cand (in_scope `unionVarSet` vars) acc
 {-# INLINE delFVs #-}
 
--- | Filter a free variable computation.
-filterFV :: InterestingVarFun -> FV -> FV
-filterFV fv_cand2 fv fv_cand1 in_scope acc =
-  fv (\v -> fv_cand1 v && fv_cand2 v) in_scope acc
-{-# INLINE filterFV #-}
-
--- | Map a free variable computation over a list and union the results.
 mapUnionFV :: (a -> FV) -> [a] -> FV
-mapUnionFV _f [] _fv_cand _in_scope acc = acc
-mapUnionFV f (a:as) fv_cand in_scope acc =
-  mapUnionFV f as fv_cand in_scope $! f a fv_cand in_scope $! acc
-{-# INLINABLE mapUnionFV #-}
-
--- | Union many free variable computations.
-unionsFV :: [FV] -> FV
-unionsFV fvs fv_cand in_scope acc = mapUnionFV id fvs fv_cand in_scope acc
-{-# INLINE unionsFV #-}
-
--- | Add multiple variables - when free, to the returned free variables.
--- Ignores duplicates and respects the filtering function.
+mapUnionFV = foldMap
+
+unionFV :: FreeVarStrategy fv => fv -> fv -> fv
+unionFV = (<>)
+
 mkFVs :: [Var] -> FV
-mkFVs vars fv_cand in_scope acc =
-  mapUnionFV unitFV vars fv_cand in_scope acc
-{-# INLINE mkFVs #-}
+mkFVs = foldMap unitFV
+
+--------------------------------------------------------------------------------
+-- Filtered free variable sets
+--------------------------------------------------------------------------------
+
+-- | A free variable traversal filtered by a statically known "is interesting"
+-- predicate (namely 'fvIsInteresting').
+newtype FilteredFV pred fv = FilteredFV { runFilteredFV :: fv }
+                          deriving (Monoid, Semigroup)
+
+class FVFilterPred pred where
+  fvIsInteresting :: Proxy pred -> InterestingVarFun
+
+instance (FreeVarStrategy fv, Monoid fv, FVFilterPred pred) => FreeVarStrategy (FilteredFV pred fv) where
+  coholeFV = FilteredFV . coholeFV
+  unitFV v
+    | fvIsInteresting proxy v = FilteredFV (unitFV v)
+    | otherwise = mempty
+    where proxy = Proxy :: Proxy pred
+  bindVar v fv = FilteredFV (bindVar v (runFilteredFV fv))
+
+  {-# INLINE coholeFV #-}
+  {-# INLINE unitFV #-}
+  {-# INLINE bindVar #-}
+
+-- | A 'FVFilterPred' selecting locally defined 'Id's and 'TyVar's.
+data LocalVars
+
+instance FVFilterPred LocalVars where
+  fvIsInteresting _ = isLocalVar
+
+
+type LocalFV = FilteredFV LocalVars FV
+type LocalNonDetFV = FilteredFV LocalVars NonDetFV
+
+localFVs :: FilteredFV LocalVars fv -> fv
+localFVs = runFilteredFV
+
+localFvVarSet :: LocalNonDetFV -> VarSet
+localFvVarSet = nonDetFVSet . runFilteredFV
diff --git a/compiler/utils/FreeVarStrategy.hs b/compiler/utils/FreeVarStrategy.hs
new file mode 100644
index 0000000000..1a1565413d
--- /dev/null
+++ b/compiler/utils/FreeVarStrategy.hs
@@ -0,0 +1,14 @@
+module FreeVarStrategy (FreeVarStrategy(..)) where
+
+import {-# SOURCE #-} TyCoRep (CoercionHole)
+
+import Var
+
+import Data.Monoid (Monoid)
+
+class Monoid m => FreeVarStrategy m where
+  -- | Introduce a free 'CohercionHole'.
+  coholeFV  :: CoercionHole -> m
+  -- | Introduce a free variable (and any free variables of its type/kind).
+  unitFV   :: Var -> m
+  bindVar :: Var -> m -> m
diff --git a/testsuite/tests/simplCore/should_compile/T4908.stderr b/testsuite/tests/simplCore/should_compile/T4908.stderr
index 62f300e962..7e1b69dde0 100644
--- a/testsuite/tests/simplCore/should_compile/T4908.stderr
+++ b/testsuite/tests/simplCore/should_compile/T4908.stderr
@@ -49,18 +49,18 @@ T4908.$trModule
 
 Rec {
 -- RHS size: {terms: 19, types: 5, coercions: 0, joins: 0/0}
-T4908.f_$s$wf [Occ=LoopBreaker] :: Int -> Int# -> Int# -> Bool
+T4908.f_$s$wf [Occ=LoopBreaker] :: Int# -> Int -> Int# -> Bool
 [GblId,
  Arity=3,
  Caf=NoCafRefs,
- Str=<L,A><L,1*U><S,1*U>,
+ Str=<S,1*U><L,A><L,1*U>,
  Unf=OtherCon []]
 T4908.f_$s$wf
-  = \ (sc :: Int) (sc1 :: Int#) (sc2 :: Int#) ->
-      case sc2 of ds {
+  = \ (sc :: Int#) (sc1 :: Int) (sc2 :: Int#) ->
+      case sc of ds {
         __DEFAULT ->
-          case sc1 of ds1 {
-            __DEFAULT -> T4908.f_$s$wf sc ds1 (-# ds 1#);
+          case sc2 of ds1 {
+            __DEFAULT -> T4908.f_$s$wf (-# ds 1#) sc1 ds1;
             0# -> GHC.Types.True
           };
         0# -> GHC.Types.True
@@ -82,7 +82,7 @@ T4908.$wf
           case w of { (a, b) ->
           case b of { I# ds1 ->
           case ds1 of ds2 {
-            __DEFAULT -> T4908.f_$s$wf a ds2 (-# ds 1#);
+            __DEFAULT -> T4908.f_$s$wf (-# ds 1#) a ds2;
             0# -> GHC.Types.True
           }
           }
@@ -107,8 +107,8 @@ f = \ (w :: Int) (w1 :: (Int, Int)) ->
 
 ------ Local rules for imported ids --------
 "SC:$wf0" [2]
-    forall (sc :: Int) (sc1 :: Int#) (sc2 :: Int#).
-      T4908.$wf sc2 (sc, GHC.Types.I# sc1)
+    forall (sc :: Int#) (sc1 :: Int) (sc2 :: Int#).
+      T4908.$wf sc (sc1, GHC.Types.I# sc2)
       = T4908.f_$s$wf sc sc1 sc2
 
 
diff --git a/testsuite/tests/simplCore/should_compile/spec-inline.stderr b/testsuite/tests/simplCore/should_compile/spec-inline.stderr
index 07b04c215e..fede0fec98 100644
--- a/testsuite/tests/simplCore/should_compile/spec-inline.stderr
+++ b/testsuite/tests/simplCore/should_compile/spec-inline.stderr
@@ -62,19 +62,19 @@ Rec {
 -- RHS size: {terms: 40, types: 5, coercions: 0, joins: 0/0}
 Roman.foo_$s$wgo [Occ=LoopBreaker]
   :: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int#
-[GblId, Arity=2, Caf=NoCafRefs, Str=<L,A><L,U>, Unf=OtherCon []]
+[GblId, Arity=2, Caf=NoCafRefs, Str=<L,U><L,A>, Unf=OtherCon []]
 Roman.foo_$s$wgo
   = \ (sc :: GHC.Prim.Int#) (sc1 :: GHC.Prim.Int#) ->
-      case GHC.Prim.<=# sc1 0# of {
+      case GHC.Prim.<=# sc 0# of {
         __DEFAULT ->
-          case GHC.Prim.<# sc1 100# of {
+          case GHC.Prim.<# sc 100# of {
             __DEFAULT ->
-              case GHC.Prim.<# sc1 500# of {
+              case GHC.Prim.<# sc 500# of {
                 __DEFAULT ->
-                  Roman.foo_$s$wgo (GHC.Prim.*# 14# sc) (GHC.Prim.-# sc1 1#);
-                1# -> Roman.foo_$s$wgo (GHC.Prim.*# 7# sc) (GHC.Prim.-# sc1 3#)
+                  Roman.foo_$s$wgo (GHC.Prim.-# sc 1#) (GHC.Prim.*# 14# sc1);
+                1# -> Roman.foo_$s$wgo (GHC.Prim.-# sc 3#) (GHC.Prim.*# 7# sc1)
               };
-            1# -> Roman.foo_$s$wgo sc (GHC.Prim.-# sc1 2#)
+            1# -> Roman.foo_$s$wgo (GHC.Prim.-# sc 2#) sc1
           };
         1# -> 0#
       }
@@ -95,7 +95,7 @@ Roman.$wgo
         Just x ->
           case x of { GHC.Types.I# ipv ->
           case w of {
-            Nothing -> Roman.foo_$s$wgo (GHC.Prim.*# 7# ipv) 10#;
+            Nothing -> Roman.foo_$s$wgo 10# (GHC.Prim.*# 7# ipv);
             Just n ->
               case n of { GHC.Types.I# x2 ->
               case GHC.Prim.<=# x2 0# of {
@@ -104,10 +104,10 @@ Roman.$wgo
                     __DEFAULT ->
                       case GHC.Prim.<# x2 500# of {
                         __DEFAULT ->
-                          Roman.foo_$s$wgo (GHC.Prim.*# 14# ipv) (GHC.Prim.-# x2 1#);
-                        1# -> Roman.foo_$s$wgo (GHC.Prim.*# 7# ipv) (GHC.Prim.-# x2 3#)
+                          Roman.foo_$s$wgo (GHC.Prim.-# x2 1#) (GHC.Prim.*# 14# ipv);
+                        1# -> Roman.foo_$s$wgo (GHC.Prim.-# x2 3#) (GHC.Prim.*# 7# ipv)
                       };
-                    1# -> Roman.foo_$s$wgo ipv (GHC.Prim.-# x2 2#)
+                    1# -> Roman.foo_$s$wgo (GHC.Prim.-# x2 2#) ipv
                   };
                 1# -> 0#
               }
@@ -167,15 +167,15 @@ foo :: Int -> Int
 foo
   = \ (n :: Int) ->
       case n of { GHC.Types.I# ipv ->
-      case Roman.foo_$s$wgo 6# ipv of ww { __DEFAULT -> GHC.Types.I# ww }
+      case Roman.foo_$s$wgo ipv 6# of ww { __DEFAULT -> GHC.Types.I# ww }
       }
 
 
 ------ Local rules for imported ids --------
 "SC:$wgo0" [2]
     forall (sc :: GHC.Prim.Int#) (sc1 :: GHC.Prim.Int#).
-      Roman.$wgo (GHC.Maybe.Just @ Int (GHC.Types.I# sc1))
-                 (GHC.Maybe.Just @ Int (GHC.Types.I# sc))
+      Roman.$wgo (GHC.Maybe.Just @ Int (GHC.Types.I# sc))
+                 (GHC.Maybe.Just @ Int (GHC.Types.I# sc1))
       = Roman.foo_$s$wgo sc sc1
 
 
diff --git a/utils/haddock b/utils/haddock
-Subproject f4298e24044cf01890ff6a257d387ee9a7f13d8
+Subproject ca01a0469eed01cc454336a47a223a73ef5db43