X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2FcoreSyn%2FCoreSubst.lhs;h=3578037f301b132357e08f4f7d11ea42b8e102ee;hb=635952097df211953c4bd0456b37eba64c485f60;hp=cf086c8bf5053f1396b53841562c993c6e370c59;hpb=d95ce839533391e7118257537044f01cbb1d6694;p=ghc-hetmet.git diff --git a/compiler/coreSyn/CoreSubst.lhs b/compiler/coreSyn/CoreSubst.lhs index cf086c8..3578037 100644 --- a/compiler/coreSyn/CoreSubst.lhs +++ b/compiler/coreSyn/CoreSubst.lhs @@ -11,12 +11,13 @@ module CoreSubst ( Subst, TvSubstEnv, IdSubstEnv, InScopeSet, -- ** Substituting into expressions and related types - deShadowBinds, - substTy, substExpr, substSpec, substUnfolding, - lookupIdSubst, lookupTvSubst, + deShadowBinds, substSpec, substRulesForImportedIds, + substTy, substExpr, substExprSC, substBind, substBindSC, + substUnfolding, substUnfoldingSC, + substUnfoldingSource, lookupIdSubst, lookupTvSubst, substIdOcc, -- ** Operations on substitutions - emptySubst, mkEmptySubst, mkSubst, substInScope, isEmptySubst, + emptySubst, mkEmptySubst, mkSubst, mkOpenSubst, substInScope, isEmptySubst, extendIdSubst, extendIdSubstList, extendTvSubst, extendTvSubstList, extendSubst, extendSubstList, zapSubstEnv, extendInScope, extendInScopeList, extendInScopeIds, @@ -24,7 +25,10 @@ module CoreSubst ( -- ** Substituting and cloning binders substBndr, substBndrs, substRecBndrs, - cloneIdBndr, cloneIdBndrs, cloneRecIdBndrs + cloneIdBndr, cloneIdBndrs, cloneRecIdBndrs, + + -- ** Simple expression optimiser + simpleOptExpr ) where #include "HsVersions.h" @@ -32,17 +36,21 @@ module CoreSubst ( import CoreSyn import CoreFVs import CoreUtils +import OccurAnal( occurAnalyseExpr ) import qualified Type import Type ( Type, TvSubst(..), TvSubstEnv ) +import OptCoercion ( optCoercion ) import VarSet import VarEnv import Id +import Name ( Name ) import Var ( Var, TyVar, setVarUnique ) import IdInfo import Unique import UniqSupply import Maybes +import BasicTypes ( isAlwaysActive ) import Outputable import PprCore () -- Instances import FastString @@ -205,19 +213,28 @@ extendSubstList subst [] = subst extendSubstList subst ((var,rhs):prs) = extendSubstList (extendSubst subst var rhs) prs -- | Find the substitution for an 'Id' in the 'Subst' -lookupIdSubst :: Subst -> Id -> CoreExpr -lookupIdSubst (Subst in_scope ids _) v +lookupIdSubst :: SDoc -> Subst -> Id -> CoreExpr +lookupIdSubst doc (Subst in_scope ids _) v | not (isLocalId 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 $$ ppr in_scope ) + | otherwise = WARN( True, ptext (sLit "CoreSubst.lookupIdSubst") <+> ppr v $$ ppr in_scope $$ doc) Var v -- | Find the substitution for a 'TyVar' in the 'Subst' lookupTvSubst :: Subst -> TyVar -> Type lookupTvSubst (Subst _ _ tvs) v = lookupVarEnv tvs v `orElse` Type.mkTyVarTy v +-- | Simultaneously substitute for a bunch of variables +-- No left-right shadowing +-- ie the substitution for (\x \y. e) a1 a2 +-- so neither x nor y scope over a1 a2 +mkOpenSubst :: InScopeSet -> [(Var,CoreArg)] -> Subst +mkOpenSubst in_scope pairs = Subst in_scope + (mkVarEnv [(id,e) | (id, e) <- pairs, isId id]) + (mkVarEnv [(tv,ty) | (tv, Type ty) <- pairs]) + ------------------------------ isInScope :: Var -> Subst -> Bool isInScope v (Subst in_scope _ _) = v `elemInScopeSet` in_scope @@ -266,21 +283,33 @@ instance Outputable Subst where -- -- Do *not* attempt to short-cut in the case of an empty substitution! -- See Note [Extending the Subst] -substExpr :: Subst -> CoreExpr -> CoreExpr -substExpr subst expr +substExprSC :: SDoc -> Subst -> CoreExpr -> CoreExpr +substExprSC _doc subst orig_expr + | isEmptySubst subst = orig_expr + | otherwise = -- pprTrace "enter subst-expr" (doc $$ ppr orig_expr) $ + subst_expr subst orig_expr + +substExpr :: SDoc -> Subst -> CoreExpr -> CoreExpr +substExpr _doc subst orig_expr = subst_expr subst orig_expr + +subst_expr :: Subst -> CoreExpr -> CoreExpr +subst_expr subst expr = go expr where - go (Var v) = lookupIdSubst subst v + go (Var v) = lookupIdSubst (text "subst_expr") subst v go (Type ty) = Type (substTy subst ty) 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) + go (Cast e co) = Cast (go e) (optCoercion (getTvSubst subst) co) + -- Optimise coercions as we go; this is good, for example + -- in the RHS of rules, which are only substituted in + + go (Lam bndr body) = Lam bndr' (subst_expr subst' body) where (subst', bndr') = substBndr subst bndr - go (Let bind body) = Let bind' (substExpr subst' body) + go (Let bind body) = Let bind' (subst_expr subst' body) where (subst', bind') = substBind subst bind @@ -288,7 +317,7 @@ substExpr subst expr where (subst', bndr') = substBndr subst bndr - go_alt subst (con, bndrs, rhs) = (con, bndrs', substExpr subst' rhs) + go_alt subst (con, bndrs, rhs) = (con, bndrs', subst_expr subst' rhs) where (subst', bndrs') = substBndrs subst bndrs @@ -296,16 +325,32 @@ substExpr subst expr -- | Apply a substititon to an entire 'CoreBind', additionally returning an updated 'Subst' -- that should be used by subsequent substitutons. -substBind :: Subst -> CoreBind -> (Subst, CoreBind) -substBind subst (NonRec bndr rhs) = (subst', NonRec bndr' (substExpr subst rhs)) +substBind, substBindSC :: Subst -> CoreBind -> (Subst, CoreBind) + +substBindSC subst bind -- Short-cut if the substitution is empty + | not (isEmptySubst subst) + = substBind subst bind + | otherwise + = case bind of + NonRec bndr rhs -> (subst', NonRec bndr' rhs) + where + (subst', bndr') = substBndr subst bndr + Rec pairs -> (subst', Rec (bndrs' `zip` rhss')) + where + (bndrs, rhss) = unzip pairs + (subst', bndrs') = substRecBndrs subst bndrs + rhss' | isEmptySubst subst' = rhss + | otherwise = map (subst_expr subst') rhss + +substBind subst (NonRec bndr rhs) = (subst', NonRec bndr' (subst_expr subst rhs)) where (subst', bndr') = substBndr subst bndr -substBind subst (Rec pairs) = (subst', Rec pairs') +substBind subst (Rec pairs) = (subst', Rec (bndrs' `zip` rhss')) where - (subst', bndrs') = substRecBndrs subst (map fst pairs) - pairs' = bndrs' `zip` rhss' - rhss' = map (substExpr subst' . snd) pairs + (bndrs, rhss) = unzip pairs + (subst', bndrs') = substRecBndrs subst bndrs + rhss' = map (subst_expr subst') rhss \end{code} \begin{code} @@ -315,6 +360,9 @@ substBind subst (Rec pairs) = (subst', Rec pairs') -- -- (Actually, within a single /type/ there might still be shadowing, because -- 'substTy' is a no-op for the empty substitution, but that's probably OK.) +-- +-- [Aug 09] This function is not used in GHC at the moment, but seems so +-- short and simple that I'm going to leave it here deShadowBinds :: [CoreBind] -> [CoreBind] deShadowBinds binds = snd (mapAccumL substBind emptySubst binds) \end{code} @@ -338,7 +386,7 @@ preserve occ info in rules. substBndr :: Subst -> Var -> (Subst, Var) substBndr subst bndr | isTyVar bndr = substTyVarBndr subst bndr - | otherwise = substIdBndr subst subst bndr + | otherwise = substIdBndr (text "var-bndr") subst subst bndr -- | Applies 'substBndr' to a number of 'Var's, accumulating a new 'Subst' left-to-right substBndrs :: Subst -> [Var] -> (Subst, [Var]) @@ -349,18 +397,20 @@ substRecBndrs :: Subst -> [Id] -> (Subst, [Id]) substRecBndrs subst bndrs = (new_subst, new_bndrs) where -- Here's the reason we need to pass rec_subst to subst_id - (new_subst, new_bndrs) = mapAccumL (substIdBndr new_subst) subst bndrs + (new_subst, new_bndrs) = mapAccumL (substIdBndr (text "rec-bndr") new_subst) subst bndrs \end{code} \begin{code} -substIdBndr :: Subst -- ^ Substitution to use for the IdInfo +substIdBndr :: SDoc + -> 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) +substIdBndr _doc rec_subst subst@(Subst in_scope env tvs) old_id + = -- pprTrace "substIdBndr" (doc $$ ppr old_id $$ ppr in_scope) $ + (Subst (in_scope `extendInScopeSet` new_id) new_env tvs, new_id) where id1 = uniqAway in_scope old_id -- id1 is cloned if necessary id2 | no_type_change = id1 @@ -392,7 +442,7 @@ It also unconditionally zaps the OccInfo. \begin{code} -- | Very similar to 'substBndr', but it always allocates a new 'Unique' for --- each variable in its output and removes all 'IdInfo' +-- each variable in its output. It substitutes the IdInfo though. cloneIdBndr :: Subst -> UniqSupply -> Id -> (Subst, Id) cloneIdBndr subst us old_id = clone_id subst subst (old_id, uniqFromSupply us) @@ -445,8 +495,10 @@ substTyVarBndr (Subst in_scope id_env tv_env) tv -- | See 'Type.substTy' substTy :: Subst -> Type -> Type -substTy (Subst in_scope _id_env tv_env) ty - = Type.substTy (TvSubst in_scope tv_env) ty +substTy subst ty = Type.substTy (getTvSubst subst) ty + +getTvSubst :: Subst -> TvSubst +getTvSubst (Subst in_scope _id_env tv_env) = TvSubst in_scope tv_env \end{code} @@ -483,49 +535,93 @@ substIdInfo subst new_id info ------------------ -- | Substitutes for the 'Id's within an unfolding -substUnfolding :: Subst -> Unfolding -> Unfolding +substUnfolding, substUnfoldingSC :: Subst -> Unfolding -> Unfolding -- Seq'ing on the returned Unfolding is enough to cause -- all the substitutions to happen completely -substUnfolding subst unf@(InlineRule { uf_tmpl = tmpl, uf_worker = mb_wkr }) + +substUnfoldingSC subst unf -- Short-cut version + | isEmptySubst subst = unf + | otherwise = substUnfolding subst unf + +substUnfolding subst (DFunUnfolding ar con args) + = DFunUnfolding ar con (map (substExpr (text "dfun-unf") subst) args) + +substUnfolding subst unf@(CoreUnfolding { uf_tmpl = tmpl, uf_src = src }) -- Retain an InlineRule! + | not (isInlineRuleSource src) -- Always zap a CoreUnfolding, to save substitution work + = NoUnfolding + | otherwise -- But keep an InlineRule! = seqExpr new_tmpl `seq` - new_mb_wkr `seq` - unf { uf_tmpl = new_tmpl, uf_worker = new_mb_wkr } + new_src `seq` + unf { uf_tmpl = new_tmpl, uf_src = new_src } where - new_tmpl = substExpr subst tmpl - new_mb_wkr = case mb_wkr of - Nothing -> Nothing - Just w -> subst_wkr w + new_tmpl = substExpr (text "subst-unf") subst tmpl + new_src = substUnfoldingSource subst src + +substUnfolding _ unf = unf -- NoUnfolding, OtherCon + +------------------- +substUnfoldingSource :: Subst -> UnfoldingSource -> UnfoldingSource +substUnfoldingSource (Subst in_scope ids _) (InlineWrapper wkr) + | Just wkr_expr <- lookupVarEnv ids wkr + = case wkr_expr of + Var w1 -> InlineWrapper w1 + _other -> -- WARN( True, text "Interesting! CoreSubst.substWorker1:" <+> ppr wkr + -- <+> ifPprDebug (equals <+> ppr wkr_expr) ) + -- Note [Worker inlining] + InlineRule -- It's not a wrapper any more, but still inline it! + + | Just w1 <- lookupInScope in_scope wkr = InlineWrapper w1 + | otherwise = -- WARN( True, text "Interesting! CoreSubst.substWorker2:" <+> ppr wkr ) + -- This can legitimately happen. The worker has been inlined and + -- dropped as dead code, because we don't treat the UnfoldingSource + -- as an "occurrence". + -- Note [Worker inlining] + InlineRule + +substUnfoldingSource _ src = src - subst_wkr w = case lookupIdSubst subst w of - Var w1 -> Just w1 - other -> WARN( not (exprIsTrivial other), text "CoreSubst.substWorker:" <+> ppr w ) - Nothing -- Worker has got substituted away altogether - -- (This can happen if it's trivial, - -- via postInlineUnconditionally, hence warning) - -substUnfolding _ (CoreUnfolding {}) = NoUnfolding -- Discard - -- Always zap a CoreUnfolding, to save substitution work - -substUnfolding _ unf = unf -- Otherwise no substitution to do +------------------ +substIdOcc :: Subst -> Id -> Id +-- These Ids should not be substituted to non-Ids +substIdOcc subst v = case lookupIdSubst (text "substIdOcc") subst v of + Var v' -> v' + other -> pprPanic "substIdOcc" (vcat [ppr v <+> ppr other, ppr subst]) ------------------ -- | Substitutes for the 'Id's within the 'WorkerInfo' given the new function 'Id' substSpec :: Subst -> Id -> SpecInfo -> SpecInfo -substSpec subst new_fn (SpecInfo rules rhs_fvs) - = seqSpecInfo new_rules `seq` new_rules +substSpec subst new_id (SpecInfo rules rhs_fvs) + = seqSpecInfo new_spec `seq` new_spec + where + subst_ru_fn = const (idName new_id) + new_spec = SpecInfo (map (substRule subst subst_ru_fn) rules) + (substVarSet subst rhs_fvs) + +------------------ +substRulesForImportedIds :: Subst -> [CoreRule] -> [CoreRule] +substRulesForImportedIds subst rules + = map (substRule subst (\name -> name)) rules + +------------------ +substRule :: Subst -> (Name -> Name) -> CoreRule -> CoreRule + +-- The subst_ru_fn argument is applied to substitute the ru_fn field +-- of the rule: +-- - Rules for *imported* Ids never change ru_fn +-- - Rules for *local* Ids are in the IdInfo for that Id, +-- and the ru_fn field is simply replaced by the new name +-- of the Id + +substRule _ _ rule@(BuiltinRule {}) = rule +substRule subst subst_ru_fn rule@(Rule { ru_bndrs = bndrs, ru_args = args + , ru_fn = fn_name, ru_rhs = rhs }) + = rule { ru_bndrs = bndrs', + ru_fn = subst_ru_fn fn_name, + ru_args = map (substExpr (text "subst-rule" <+> ppr fn_name) subst') args, + ru_rhs = substExpr (text "subst-rule" <+> ppr fn_name) subst' rhs } 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', - 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 + (subst', bndrs') = substBndrs subst bndrs ------------------ substVarSet :: Subst -> VarSet -> VarSet @@ -533,6 +629,139 @@ substVarSet subst fvs = foldVarSet (unionVarSet . subst_fv subst) emptyVarSet fvs where subst_fv subst fv - | isId fv = exprFreeVars (lookupIdSubst subst fv) + | isId fv = exprFreeVars (lookupIdSubst (text "substVarSet") subst fv) | otherwise = Type.tyVarsOfType (lookupTvSubst subst fv) \end{code} + +Note [Worker inlining] +~~~~~~~~~~~~~~~~~~~~~~ +A worker can get sustituted away entirely. + - it might be trivial + - it might simply be very small +We do not treat an InlWrapper as an 'occurrence' in the occurence +analyser, so it's possible that the worker is not even in scope any more. + +In all all these cases we simply drop the special case, returning to +InlVanilla. The WARN is just so I can see if it happens a lot. + + +%************************************************************************ +%* * + The Very Simple Optimiser +%* * +%************************************************************************ + +\begin{code} +simpleOptExpr :: CoreExpr -> CoreExpr +-- Do simple optimisation on an expression +-- The optimisation is very straightforward: just +-- inline non-recursive bindings that are used only once, +-- or where the RHS is trivial +-- +-- The result is NOT guaranteed occurence-analysed, becuase +-- in (let x = y in ....) we substitute for x; so y's occ-info +-- may change radically + +simpleOptExpr expr + = -- pprTrace "simpleOptExpr" (ppr init_subst $$ ppr expr) + go init_subst (occurAnalyseExpr expr) + where + init_subst = mkEmptySubst (mkInScopeSet (exprFreeVars expr)) + -- It's potentially important to make a proper in-scope set + -- Consider let x = ..y.. in \y. ...x... + -- Then we should remember to clone y before substituting + -- for x. It's very unlikely to occur, because we probably + -- won't *be* substituting for x if it occurs inside a + -- lambda. + -- + -- It's a bit painful to call exprFreeVars, because it makes + -- three passes instead of two (occ-anal, and go) + + go subst (Var v) = lookupIdSubst (text "simpleOptExpr") subst v + go subst (App e1 e2) = App (go subst e1) (go subst e2) + go subst (Type ty) = Type (substTy subst ty) + go _ (Lit lit) = Lit lit + go subst (Note note e) = Note note (go subst e) + go subst (Cast e co) = Cast (go subst e) (substTy subst co) + go subst (Let bind body) = go_let subst bind body + go subst (Lam bndr body) = Lam bndr' (go subst' body) + where + (subst', bndr') = substBndr subst bndr + + go subst (Case e b ty as) = Case (go subst e) b' + (substTy subst ty) + (map (go_alt subst') as) + where + (subst', b') = substBndr subst b + + + ---------------------- + go_alt subst (con, bndrs, rhs) = (con, bndrs', go subst' rhs) + where + (subst', bndrs') = substBndrs subst bndrs + + ---------------------- + go_let subst (Rec prs) body + = Let (Rec (reverse rev_prs')) (go subst'' body) + where + (subst', bndrs') = substRecBndrs subst (map fst prs) + (subst'', rev_prs') = foldl do_pr (subst', []) (prs `zip` bndrs') + do_pr (subst, prs) ((b,r), b') = case go_bind subst b r of + Left subst' -> (subst', prs) + Right r' -> (subst, (b',r'):prs) + + go_let subst (NonRec b r) body + = case go_bind subst b r of + Left subst' -> go subst' body + Right r' -> Let (NonRec b' r') (go subst' body) + where + (subst', b') = substBndr subst b + + + ---------------------- + go_bind :: Subst -> Var -> CoreExpr -> Either Subst CoreExpr + -- (go_bind subst old_var old_rhs) + -- either extends subst with (old_var -> new_rhs) + -- or return new_rhs for a binding new_var = new_rhs + go_bind subst b r + | Type ty <- r + , isTyVar b -- let a::* = TYPE ty in + = Left (extendTvSubst subst b (substTy subst ty)) + + | isId b -- let x = e in + , safe_to_inline (idOccInfo b) || exprIsTrivial r' + , isAlwaysActive (idInlineActivation b) -- Note [Inline prag in simplOpt] + = Left (extendIdSubst subst b r') + + | otherwise + = Right r' + where + r' = go subst r + + ---------------------- + -- Unconditionally safe to inline + safe_to_inline :: OccInfo -> Bool + safe_to_inline IAmDead = True + safe_to_inline (OneOcc in_lam one_br _) = not in_lam && one_br + safe_to_inline (IAmALoopBreaker {}) = False + safe_to_inline NoOccInfo = False +\end{code} + +Note [Inline prag in simplOpt] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +If there's an INLINE/NOINLINE pragma that restricts the phase in +which the binder can be inlined, we don't inline here; after all, +we don't know what phase we're in. Here's an example + + foo :: Int -> Int -> Int + {-# INLINE foo #-} + foo m n = inner m + where + {-# INLINE [1] inner #-} + inner m = m+n + + bar :: Int -> Int + bar n = foo n 1 + +When inlining 'foo' in 'bar' we want the let-binding for 'inner' +to remain visible until Phase 1 \ No newline at end of file