X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2FcoreSyn%2FCoreSubst.lhs;h=321ea8fc3603a37936a9a8ea9db6983815cc956a;hb=36d207aa8c9cedbf58e739178971292048bd41d0;hp=c432d55f9468bb1d63b989d94e8218555cacd106;hpb=0065d5ab628975892cea1ec7303f968c3338cbe1;p=ghc-hetmet.git diff --git a/compiler/coreSyn/CoreSubst.lhs b/compiler/coreSyn/CoreSubst.lhs index c432d55..321ea8f 100644 --- a/compiler/coreSyn/CoreSubst.lhs +++ b/compiler/coreSyn/CoreSubst.lhs @@ -1,13 +1,16 @@ % +% (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 ( -- Substitution stuff Subst, TvSubstEnv, IdSubstEnv, InScopeSet, + deShadowBinds, substTy, substExpr, substSpec, substWorker, lookupIdSubst, lookupTvSubst, @@ -23,29 +26,23 @@ module CoreSubst ( #include "HsVersions.h" -import CoreSyn ( Expr(..), Bind(..), Note(..), CoreExpr, - 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, 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 ) +import Id +import Var ( Var, TyVar, setVarUnique ) +import IdInfo +import Unique +import UniqSupply +import Maybes import Outputable import PprCore () -- Instances -import Util ( mapAccumL ) +import Util import FastTypes \end{code} @@ -74,8 +71,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 @@ -123,20 +163,14 @@ extendTvSubstList (Subst in_scope ids tvs) prs = Subst in_scope ids (extendVarEn lookupIdSubst :: Subst -> Id -> CoreExpr lookupIdSubst (Subst in_scope ids tvs) v | not (isLocalId v) = Var v - | otherwise - = case lookupVarEnv ids v of { - Just e -> e ; - Nothing -> - 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 _ ids tvs) v = lookupVarEnv tvs v `orElse` Type.mkTyVarTy v ------------------------------ isInScope :: Var -> Subst -> Bool @@ -181,19 +215,14 @@ substExpr subst expr go (Lit lit) = Lit lit go (App fun arg) = App (go fun) (go arg) go (Note note e) = Note (go_note note) (go e) + go (Cast e co) = Cast (go e) (substTy subst co) go (Lam bndr body) = Lam bndr' (substExpr subst' body) where (subst', bndr') = substBndr subst bndr - go (Let (NonRec bndr rhs) body) = Let (NonRec bndr' (go rhs)) (substExpr subst' body) - where - (subst', bndr') = substBndr subst bndr - - go (Let (Rec pairs) body) = Let (Rec pairs') (substExpr subst' body) - where - (subst', bndrs') = substRecBndrs subst (map fst pairs) - pairs' = bndrs' `zip` rhss' - rhss' = map (substExpr subst' . snd) pairs + go (Let bind body) = Let bind' (substExpr subst' body) + where + (subst', bind') = substBind subst bind go (Case scrut bndr ty alts) = Case (go scrut) bndr' (substTy subst ty) (map (go_alt subst') alts) where @@ -203,8 +232,30 @@ substExpr subst expr where (subst', bndrs') = substBndrs subst bndrs - go_note (Coerce ty1 ty2) = Coerce (substTy subst ty1) (substTy subst ty2) go_note note = note + +substBind :: Subst -> CoreBind -> (Subst, CoreBind) +substBind subst (NonRec bndr rhs) = (subst', NonRec bndr' (substExpr subst rhs)) + where + (subst', bndr') = substBndr subst bndr + +substBind subst (Rec pairs) = (subst', Rec pairs') + where + (subst', bndrs') = substRecBndrs subst (map fst pairs) + pairs' = bndrs' `zip` rhss' + rhss' = map (substExpr subst' . snd) pairs +\end{code} + +De-shadowing the program is sometimes a useful pre-pass. It can be done simply +by running over the bindings with an empty substitution, becuase substitution +returns a result that has no-shadowing guaranteed. + +(Actually, within a single *type* there might still be shadowing, because +substType is a no-op for the empty substitution, but that's OK.) + +\begin{code} +deShadowBinds :: [CoreBind] -> [CoreBind] +deShadowBinds binds = snd (mapAccumL substBind emptySubst binds) \end{code} @@ -246,17 +297,27 @@ substIdBndr rec_subst subst@(Subst in_scope env tvs) old_id = (Subst (in_scope `extendInScopeSet` new_id) new_env tvs, new_id) where id1 = uniqAway in_scope old_id -- id1 is cloned if necessary - id2 = substIdType subst id1 -- id2 has its type zapped + id2 | no_type_change = id1 + | otherwise = setIdType id1 (substTy subst old_ty) + + old_ty = idType old_id + 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 (substIdInfo rec_subst) id2 + new_id = maybeModifyIdInfo mb_new_info id2 + mb_new_info = substIdInfo rec_subst (idInfo id2) -- Extend the substitution if the unique has changed -- See the notes with substTyVarBndr for the delVarEnv - new_env | new_id /= old_id = extendVarEnv env old_id (Var new_id) - | otherwise = delVarEnv env old_id + new_env | no_change = delVarEnv env old_id + | otherwise = extendVarEnv env old_id (Var new_id) + + 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. @@ -289,7 +350,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) id2 + new_id = maybeModifyIdInfo (substIdInfo rec_subst (idInfo old_id)) id2 new_env = extendVarEnv env old_id (Var new_id) \end{code} @@ -325,7 +386,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 - | isEmptyVarEnv tv_env || isEmptyVarSet (tyVarsOfType old_ty) = 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 @@ -389,5 +450,5 @@ substVarSet subst 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}