X-Git-Url: http://git.megacz.com/?p=ghc-hetmet.git;a=blobdiff_plain;f=compiler%2FcoreSyn%2FCoreSubst.lhs;h=adeeaddfb225c0cf5242f2a3b806a941231be8cb;hp=6eecc27c9daf2c74738b02d5fa2760ffebcfa694;hb=e4417dcd4679da9c6b18c02ff667199c572bed89;hpb=49c98d143c382a1341e1046f5ca00819a25691ba diff --git a/compiler/coreSyn/CoreSubst.lhs b/compiler/coreSyn/CoreSubst.lhs index 6eecc27..adeeadd 100644 --- a/compiler/coreSyn/CoreSubst.lhs +++ b/compiler/coreSyn/CoreSubst.lhs @@ -16,7 +16,8 @@ module CoreSubst ( emptySubst, mkEmptySubst, mkSubst, substInScope, isEmptySubst, extendIdSubst, extendIdSubstList, extendTvSubst, extendTvSubstList, - extendInScope, extendInScopeIds, + extendSubst, extendSubstList, zapSubstEnv, + extendInScope, extendInScopeList, extendInScopeIds, isInScope, -- Binders @@ -42,8 +43,9 @@ import UniqSupply import Maybes import Outputable import PprCore () -- Instances -import Util -import FastTypes +import FastString + +import Data.List \end{code} @@ -56,6 +58,7 @@ import FastTypes \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 @@ -71,8 +74,51 @@ data Subst -- - 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 @@ -101,8 +147,8 @@ mkSubst in_scope tvs ids = Subst in_scope ids tvs 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 @@ -117,34 +163,27 @@ extendTvSubst (Subst in_scope ids tvs) v r = Subst in_scope ids (extendVarEnv tv 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` Type.mkTyVarTy v +lookupTvSubst (Subst _ _ tvs) v = lookupVarEnv tvs v `orElse` Type.mkTyVarTy v ------------------------------ isInScope :: Var -> Subst -> Bool @@ -155,6 +194,11 @@ extendInScope (Subst in_scope ids tvs) v = 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) @@ -266,6 +310,7 @@ substRecBndrs subst bndrs 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) @@ -282,14 +327,17 @@ substIdBndr rec_subst subst@(Subst in_scope env tvs) old_id -- 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. @@ -322,7 +370,7 @@ clone_id rec_subst subst@(Subst in_scope env tvs) (old_id, uniq) 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} @@ -344,7 +392,7 @@ substTyVarBndr (Subst in_scope id_env tv_env) tv -> (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} @@ -357,7 +405,7 @@ substTy (Subst in_scope id_env tv_env) ty \begin{code} substIdType :: Subst -> Id -> Id -substIdType subst@(Subst in_scope id_env tv_env) 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 @@ -367,11 +415,11 @@ substIdType subst@(Subst in_scope id_env tv_env) id 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 @@ -387,7 +435,7 @@ substWorker :: Subst -> WorkerInfo -> WorkerInfo -- 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 @@ -398,25 +446,28 @@ substWorker subst (HasWorker w a) -- 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