%
+% (c) The University of Glasgow 2006
% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
%
-\section[CoreUtils]{Utility functions on @Core@ syntax}
+
+Utility functions on @Core@ syntax
\begin{code}
module CoreSubst (
emptySubst, mkEmptySubst, mkSubst, substInScope, isEmptySubst,
extendIdSubst, extendIdSubstList, extendTvSubst, extendTvSubstList,
- extendInScope, extendInScopeIds,
+ extendSubst, extendSubstList, zapSubstEnv,
+ extendInScope, extendInScopeList, extendInScopeIds,
isInScope,
-- Binders
#include "HsVersions.h"
-import CoreSyn ( Expr(..), Bind(..), Note(..), CoreExpr, CoreBind,
- CoreRule(..), hasUnfolding, noUnfolding
- )
-import CoreFVs ( exprFreeVars )
-import CoreUtils ( exprIsTrivial )
+import CoreSyn
+import CoreFVs
+import CoreUtils
-import qualified Type ( substTy, substTyVarBndr )
-import Type ( Type, tyVarsOfType, TvSubstEnv, TvSubst(..), mkTyVarTy )
+import qualified Type
+import Type ( Type, TvSubst(..), TvSubstEnv )
import VarSet
import VarEnv
-import Var ( setVarUnique, isId )
-import Id ( idType, idInfo, setIdType, maybeModifyIdInfo, isLocalId )
-import IdInfo ( IdInfo, SpecInfo(..), specInfo, setSpecInfo, isEmptySpecInfo,
- unfoldingInfo, setUnfoldingInfo, seqSpecInfo,
- WorkerInfo(..), workerExists, workerInfo, setWorkerInfo
- )
-import Unique ( Unique )
-import UniqSupply ( UniqSupply, uniqFromSupply, uniqsFromSupply )
-import Var ( Var, Id, TyVar, isTyVar )
-import Maybes ( orElse, isNothing )
+import Id
+import Var ( Var, TyVar, setVarUnique )
+import IdInfo
+import Unique
+import UniqSupply
+import Maybes
import Outputable
import PprCore () -- Instances
-import Util ( mapAccumL )
-import FastTypes
+import FastString
+
+import Data.List
\end{code}
\begin{code}
data Subst
= Subst InScopeSet -- Variables in in scope (both Ids and TyVars)
+ -- *after* applying the substitution
IdSubstEnv -- Substitution for Ids
TvSubstEnv -- Substitution for TyVars
-- - make it empty because all the free vars of the subst are fresh,
-- and hence can't possibly clash.a
--
- -- INVARIANT 2: The substitution is apply-once; see notes with
+ -- INVARIANT 2: The substitution is apply-once; see Note [Apply once] with
-- Types.TvSubstEnv
+ --
+ -- INVARIANT 3: See Note [Extending the Subst]
+
+{-
+Note [Extending the Subst]
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+For a core Subst, which binds Ids as well, we make a different choice for Ids
+than we do for TyVars.
+
+For TyVars, see Note [Extending the TvSubst] with Type.TvSubstEnv
+
+For Ids, we have a different invariant
+ The IdSubstEnv is extended *only* when the Unique on an Id changes
+ Otherwise, we just extend the InScopeSet
+
+In consequence:
+
+* In substIdBndr, we extend the IdSubstEnv only when the unique changes
+
+* If the TvSubstEnv and IdSubstEnv are both empty, substExpr does nothing
+ (Note that the above rule for substIdBndr maintains this property. If
+ the incoming envts are both empty, then substituting the type and
+ IdInfo can't change anything.)
+
+* In lookupIdSubst, we *must* look up the Id in the in-scope set, because
+ it may contain non-trivial changes. Example:
+ (/\a. \x:a. ...x...) Int
+ We extend the TvSubstEnv with [a |-> Int]; but x's unique does not change
+ so we only extend the in-scope set. Then we must look up in the in-scope
+ set when we find the occurrence of x.
+
+Why do we make a different choice for the IdSubstEnv than the TvSubstEnv?
+
+* For Ids, we change the IdInfo all the time (e.g. deleting the
+ unfolding), and adding it back later, so using the TyVar convention
+ would entail extending the substitution almost all the time
+
+* The simplifier wants to look up in the in-scope set anyway, in case it
+ can see a better unfolding from an enclosing case expression
+
+* For TyVars, only coercion variables can possibly change, and they are
+ easy to spot
+-}
type IdSubstEnv = IdEnv CoreExpr
substInScope :: Subst -> InScopeSet
substInScope (Subst in_scope _ _) = in_scope
--- zapSubstEnv :: Subst -> Subst
--- zapSubstEnv (Subst in_scope _ _) = Subst in_scope emptyVarEnv emptyVarEnv
+zapSubstEnv :: Subst -> Subst
+zapSubstEnv (Subst in_scope _ _) = Subst in_scope emptyVarEnv emptyVarEnv
-- ToDo: add an ASSERT that fvs(subst-result) is already in the in-scope set
extendIdSubst :: Subst -> Id -> CoreExpr -> Subst
extendTvSubstList :: Subst -> [(TyVar,Type)] -> Subst
extendTvSubstList (Subst in_scope ids tvs) prs = Subst in_scope ids (extendVarEnvList tvs prs)
+extendSubstList :: Subst -> [(Var,CoreArg)] -> Subst
+extendSubstList subst [] = subst
+extendSubstList subst ((var,rhs):prs) = extendSubstList (extendSubst subst var rhs) prs
+
+extendSubst :: Subst -> Var -> CoreArg -> Subst
+extendSubst (Subst in_scope ids tvs) tv (Type ty)
+ = ASSERT( isTyVar tv ) Subst in_scope ids (extendVarEnv tvs tv ty)
+extendSubst (Subst in_scope ids tvs) id expr
+ = ASSERT( isId id ) Subst in_scope (extendVarEnv ids id expr) tvs
+
lookupIdSubst :: Subst -> Id -> CoreExpr
-lookupIdSubst (Subst in_scope ids tvs) v
+lookupIdSubst (Subst in_scope ids _) v
| not (isLocalId v) = Var v
- | otherwise = case lookupVarEnv ids v of
- Just e -> e
- Nothing -> Var v
-
-{- We used to have to look up in the in-scope set,
- because GADTs were implicit in the intermediate language
- But with FC, the type of an Id does not change in its scope
- The worst that can happen if we don't look up in the in-scope set
- is that we don't propagate IdInfo as vigorously as we might.
- But that'll happen (when it's useful) in SimplEnv.substId
-
- If you put this back in, you should worry about the
- Just e -> e
- case above too!
-
- case lookupInScope in_scope v of {
- -- Watch out! Must get the Id from the in-scope set,
- -- because its type there may differ
- Just v -> Var v ;
- Nothing -> WARN( True, ptext SLIT("CoreSubst.lookupIdSubst") <+> ppr v )
- Var v
--}
+ | Just e <- lookupVarEnv ids v = e
+ | Just v' <- lookupInScope in_scope v = Var v'
+ -- Vital! See Note [Extending the Subst]
+ | otherwise = WARN( True, ptext SLIT("CoreSubst.lookupIdSubst") <+> ppr v )
+ Var v
lookupTvSubst :: Subst -> TyVar -> Type
-lookupTvSubst (Subst _ ids tvs) v = lookupVarEnv tvs v `orElse` mkTyVarTy v
+lookupTvSubst (Subst _ _ tvs) v = lookupVarEnv tvs v `orElse` Type.mkTyVarTy v
------------------------------
isInScope :: Var -> Subst -> Bool
= Subst (in_scope `extendInScopeSet` v)
(ids `delVarEnv` v) (tvs `delVarEnv` v)
+extendInScopeList :: Subst -> [Var] -> Subst
+extendInScopeList (Subst in_scope ids tvs) vs
+ = Subst (in_scope `extendInScopeSetList` vs)
+ (ids `delVarEnvList` vs) (tvs `delVarEnvList` vs)
+
extendInScopeIds :: Subst -> [Id] -> Subst
extendInScopeIds (Subst in_scope ids tvs) vs
= Subst (in_scope `extendInScopeSetList` vs)
substIdBndr :: Subst -- Substitution to use for the IdInfo
-> Subst -> Id -- Substitition and Id to transform
-> (Subst, Id) -- Transformed pair
+ -- NB: unfolding may be zapped
substIdBndr rec_subst subst@(Subst in_scope env tvs) old_id
= (Subst (in_scope `extendInScopeSet` new_id) new_env tvs, new_id)
| otherwise = setIdType id1 (substTy subst old_ty)
old_ty = idType old_id
- no_type_change = isEmptyVarEnv tvs || isEmptyVarSet (tyVarsOfType old_ty)
+ no_type_change = isEmptyVarEnv tvs ||
+ isEmptyVarSet (Type.tyVarsOfType old_ty)
-- new_id has the right IdInfo
-- The lazy-set is because we're in a loop here, with
-- rec_subst, when dealing with a mutually-recursive group
new_id = maybeModifyIdInfo mb_new_info id2
- mb_new_info = substIdInfo rec_subst (idInfo id2)
+ mb_new_info = substIdInfo rec_subst id2 (idInfo id2)
+ -- NB: unfolding info may be zapped
-- Extend the substitution if the unique has changed
-- See the notes with substTyVarBndr for the delVarEnv
new_env | no_change = delVarEnv env old_id
| otherwise = extendVarEnv env old_id (Var new_id)
- no_change = False -- id1 == old_id && isNothing mb_new_info && no_type_change
+ no_change = id1 == old_id
+ -- See Note [Extending the Subst]
+ -- *not* necessary to check mb_new_info and no_type_change
\end{code}
Now a variant that unconditionally allocates a new unique.
where
id1 = setVarUnique old_id uniq
id2 = substIdType subst id1
- new_id = maybeModifyIdInfo (substIdInfo rec_subst (idInfo old_id)) id2
+ new_id = maybeModifyIdInfo (substIdInfo rec_subst id2 (idInfo old_id)) id2
new_env = extendVarEnv env old_id (Var new_id)
\end{code}
-> (Subst in_scope' id_env tv_env', tv')
substTy :: Subst -> Type -> Type
-substTy (Subst in_scope id_env tv_env) ty
+substTy (Subst in_scope _id_env tv_env) ty
= Type.substTy (TvSubst in_scope tv_env) ty
\end{code}
\begin{code}
substIdType :: Subst -> Id -> Id
-substIdType subst@(Subst in_scope id_env tv_env) id
- | isEmptyVarEnv tv_env || isEmptyVarSet (tyVarsOfType old_ty) = id
+substIdType subst@(Subst _ _ tv_env) id
+ | isEmptyVarEnv tv_env || isEmptyVarSet (Type.tyVarsOfType old_ty) = id
| otherwise = setIdType id (substTy subst old_ty)
-- The tyVarsOfType is cheaper than it looks
-- because we cache the free tyvars of the type
old_ty = idType id
------------------
-substIdInfo :: Subst -> IdInfo -> Maybe IdInfo
+substIdInfo :: Subst -> Id -> IdInfo -> Maybe IdInfo
-- Always zaps the unfolding, to save substitution work
-substIdInfo subst info
+substIdInfo subst new_id info
| nothing_to_do = Nothing
- | otherwise = Just (info `setSpecInfo` substSpec subst old_rules
+ | otherwise = Just (info `setSpecInfo` substSpec subst new_id old_rules
`setWorkerInfo` substWorker subst old_wrkr
`setUnfoldingInfo` noUnfolding)
where
-- Seq'ing on the returned WorkerInfo is enough to cause all the
-- substitutions to happen completely
-substWorker subst NoWorker
+substWorker _ NoWorker
= NoWorker
substWorker subst (HasWorker w a)
= case lookupIdSubst subst w of
-- via postInlineUnconditionally, hence warning)
------------------
-substSpec :: Subst -> SpecInfo -> SpecInfo
+substSpec :: Subst -> Id -> SpecInfo -> SpecInfo
-substSpec subst spec@(SpecInfo rules rhs_fvs)
+substSpec subst new_fn spec@(SpecInfo rules rhs_fvs)
| isEmptySubst subst
= spec
| otherwise
= seqSpecInfo new_rules `seq` new_rules
where
+ new_name = idName new_fn
new_rules = SpecInfo (map do_subst rules) (substVarSet subst rhs_fvs)
do_subst rule@(BuiltinRule {}) = rule
do_subst rule@(Rule { ru_bndrs = bndrs, ru_args = args, ru_rhs = rhs })
- = rule { ru_bndrs = bndrs',
+ = rule { ru_bndrs = bndrs',
+ ru_fn = new_name, -- Important: the function may have changed its name!
ru_args = map (substExpr subst') args,
ru_rhs = substExpr subst' rhs }
where
(subst', bndrs') = substBndrs subst bndrs
------------------
+substVarSet :: Subst -> VarSet -> VarSet
substVarSet subst fvs
= foldVarSet (unionVarSet . subst_fv subst) emptyVarSet fvs
where
subst_fv subst fv
| isId fv = exprFreeVars (lookupIdSubst subst fv)
- | otherwise = tyVarsOfType (lookupTvSubst subst fv)
+ | otherwise = Type.tyVarsOfType (lookupTvSubst subst fv)
\end{code}
projects / ghc-hetmet.git / blobdiff