X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2FcoreSyn%2FCoreSubst.lhs;h=a229b8c4e986496c41732ed22cd41bdb93d8d723;hb=841e81e28f8cc711f624fdca122219a5bbde2fae;hp=4f92b1a001808f9a17c2fcbb2c86fe5c449eca69;hpb=d2ce0f52d42edf32bb9f13796e6ba6edba8bd516;p=ghc-hetmet.git diff --git a/compiler/coreSyn/CoreSubst.lhs b/compiler/coreSyn/CoreSubst.lhs index 4f92b1a..a229b8c 100644 --- a/compiler/coreSyn/CoreSubst.lhs +++ b/compiler/coreSyn/CoreSubst.lhs @@ -20,15 +20,16 @@ module CoreSubst ( emptySubst, mkEmptySubst, mkSubst, mkOpenSubst, substInScope, isEmptySubst, extendIdSubst, extendIdSubstList, extendTvSubst, extendTvSubstList, extendSubst, extendSubstList, zapSubstEnv, - extendInScope, extendInScopeList, extendInScopeIds, - isInScope, + addInScopeSet, extendInScope, extendInScopeList, extendInScopeIds, + isInScope, setInScope, + delBndr, delBndrs, -- ** Substituting and cloning binders substBndr, substBndrs, substRecBndrs, cloneIdBndr, cloneIdBndrs, cloneRecIdBndrs, -- ** Simple expression optimiser - simpleOptPgm, simpleOptExpr + simpleOptPgm, simpleOptExpr, simpleOptExprWith ) where #include "HsVersions.h" @@ -116,12 +117,14 @@ For Ids, we have a different invariant In consequence: -* In substIdBndr, we extend the IdSubstEnv only when the unique changes +* If the TvSubstEnv and IdSubstEnv are both empty, substExpr would be a + no-op, so substExprSC ("short cut") does nothing. + + However, substExpr still goes ahead and substitutes. Reason: we may + want to replace existing Ids with new ones from the in-scope set, to + avoid space leaks. -* 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 substIdBndr, we extend the IdSubstEnv only when the unique changes * In lookupIdSubst, we *must* look up the Id in the in-scope set, because it may contain non-trivial changes. Example: @@ -131,7 +134,7 @@ In consequence: set when we find the occurrence of x. * The requirement to look up the Id in the in-scope set means that we - must NOT take no-op short cut in the case the substitution is empty. + must NOT take no-op short cut when the IdSubst is empty. We must still look up every Id in the in-scope set. * (However, we don't need to do so for expressions found in the IdSubst @@ -230,6 +233,17 @@ lookupIdSubst doc (Subst in_scope ids _) v lookupTvSubst :: Subst -> TyVar -> Type lookupTvSubst (Subst _ _ tvs) v = lookupVarEnv tvs v `orElse` Type.mkTyVarTy v +delBndr :: Subst -> Var -> Subst +delBndr (Subst in_scope tvs ids) v + | isId v = Subst in_scope tvs (delVarEnv ids v) + | otherwise = Subst in_scope (delVarEnv tvs v) ids + +delBndrs :: Subst -> [Var] -> Subst +delBndrs (Subst in_scope tvs ids) vs + = Subst in_scope (delVarEnvList tvs vs_tv) (delVarEnvList ids vs_id) + where + (vs_id, vs_tv) = partition isId vs + -- | Simultaneously substitute for a bunch of variables -- No left-right shadowing -- ie the substitution for (\x \y. e) a1 a2 @@ -243,7 +257,14 @@ mkOpenSubst in_scope pairs = Subst in_scope isInScope :: Var -> Subst -> Bool isInScope v (Subst in_scope _ _) = v `elemInScopeSet` in_scope --- | Add the 'Var' to the in-scope set: as a side effect, removes any existing substitutions for it +-- | Add the 'Var' to the in-scope set, but do not remove +-- any existing substitutions for it +addInScopeSet :: Subst -> VarSet -> Subst +addInScopeSet (Subst in_scope ids tvs) vs + = Subst (in_scope `extendInScopeSetSet` vs) ids tvs + +-- | Add the 'Var' to the in-scope set: as a side effect, +-- and remove any existing substitutions for it extendInScope :: Subst -> Var -> Subst extendInScope (Subst in_scope ids tvs) v = Subst (in_scope `extendInScopeSet` v) @@ -261,6 +282,9 @@ extendInScopeIds :: Subst -> [Id] -> Subst extendInScopeIds (Subst in_scope ids tvs) vs = Subst (in_scope `extendInScopeSetList` vs) (ids `delVarEnvList` vs) tvs + +setInScope :: Subst -> InScopeSet -> Subst +setInScope (Subst _ ids tvs) in_scope = Subst in_scope ids tvs \end{code} Pretty printing, for debugging only @@ -305,13 +329,12 @@ subst_expr 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) - | isIdentityCoercion co' = go e - | otherwise = Cast (go e) co' - where - co' = 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 (Cast e co) = Cast (go e) (optCoercion (getTvSubst subst) co) + -- Do not optimise even identity coercions + -- Reason: substitution applies to the LHS of RULES, and + -- if you "optimise" an identity coercion, you may + -- lose a binder. We optimise the LHS of rules at + -- construction time go (Lam bndr body) = Lam bndr' (subst_expr subst' body) where @@ -551,13 +574,15 @@ substUnfoldingSC subst unf -- Short-cut version | otherwise = substUnfolding subst unf substUnfolding subst (DFunUnfolding ar con args) - = DFunUnfolding ar con (map (substExpr (text "dfun-unf") subst) args) + = DFunUnfolding ar con (map subst_arg args) + where + subst_arg = fmap (substExpr (text "dfun-unf") subst) substUnfolding subst unf@(CoreUnfolding { uf_tmpl = tmpl, uf_src = src }) -- Retain an InlineRule! - | not (isInlineRuleSource src) -- Always zap a CoreUnfolding, to save substitution work + | not (isStableSource src) -- Zap an unstable unfolding, to save substitution work = NoUnfolding - | otherwise -- But keep an InlineRule! + | otherwise -- But keep a stable one! = seqExpr new_tmpl `seq` new_src `seq` unf { uf_tmpl = new_tmpl, uf_src = new_src } @@ -576,7 +601,7 @@ substUnfoldingSource (Subst in_scope ids _) (InlineWrapper wkr) _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! + InlineStable -- 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 ) @@ -584,7 +609,7 @@ substUnfoldingSource (Subst in_scope ids _) (InlineWrapper wkr) -- dropped as dead code, because we don't treat the UnfoldingSource -- as an "occurrence". -- Note [Worker inlining] - InlineRule + InlineStable substUnfoldingSource _ src = src @@ -631,7 +656,9 @@ substRule subst subst_ru_fn rule@(Rule { ru_bndrs = bndrs, ru_args = args then subst_ru_fn fn_name else 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 } + ru_rhs = simpleOptExprWith subst' rhs } + -- Do simple optimisation on RHS, in case substitution lets + -- you improve it. The real simplifier never gets to look at it. where (subst', bndrs') = substBndrs subst bndrs @@ -676,7 +703,7 @@ simpleOptExpr :: CoreExpr -> CoreExpr simpleOptExpr expr = -- pprTrace "simpleOptExpr" (ppr init_subst $$ ppr expr) - simple_opt_expr init_subst (occurAnalyseExpr expr) + simpleOptExprWith init_subst expr where init_subst = mkEmptySubst (mkInScopeSet (exprFreeVars expr)) -- It's potentially important to make a proper in-scope set @@ -689,6 +716,9 @@ simpleOptExpr expr -- It's a bit painful to call exprFreeVars, because it makes -- three passes instead of two (occ-anal, and go) +simpleOptExprWith :: Subst -> InExpr -> OutExpr +simpleOptExprWith subst expr = simple_opt_expr subst (occurAnalyseExpr expr) + ---------------------- simpleOptPgm :: DynFlags -> [CoreBind] -> [CoreRule] -> IO ([CoreBind], [CoreRule]) simpleOptPgm dflags binds rules @@ -697,7 +727,8 @@ simpleOptPgm dflags binds rules ; return (reverse binds', substRulesForImportedIds subst' rules) } where - occ_anald_binds = occurAnalysePgm binds rules + occ_anald_binds = occurAnalysePgm Nothing {- No rules active -} + rules binds (subst', binds') = foldl do_one (emptySubst, []) occ_anald_binds do_one (subst, binds') bind @@ -721,7 +752,7 @@ simple_opt_expr subst expr = go expr where go (Var v) = lookupIdSubst (text "simpleOptExpr") subst v - go (App e1 e2) = App (go e1) (go e2) + go (App e1 e2) = simple_app subst e1 [go e2] go (Type ty) = Type (substTy subst ty) go (Lit lit) = Lit lit go (Note note e) = Note note (go e) @@ -730,9 +761,10 @@ simple_opt_expr subst expr where co' = substTy subst co - go (Let bind body) = maybeLet mb_bind (simple_opt_expr subst' body) - where - (subst', mb_bind) = simple_opt_bind subst bind + go (Let bind body) = case simple_opt_bind subst bind of + (subst', Nothing) -> simple_opt_expr subst' body + (subst', Just bind) -> Let bind (simple_opt_expr subst' body) + go lam@(Lam {}) = go_lam [] subst lam go (Case e b ty as) = Case (go e) b' (substTy subst ty) (map (go_alt subst') as) @@ -759,54 +791,70 @@ simple_opt_expr subst expr e' = simple_opt_expr subst e ---------------------- +-- simple_app collects arguments for beta reduction +simple_app :: Subst -> InExpr -> [OutExpr] -> CoreExpr +simple_app subst (App e1 e2) as + = simple_app subst e1 (simple_opt_expr subst e2 : as) +simple_app subst (Lam b e) (a:as) + = case maybe_substitute subst b a of + Just ext_subst -> simple_app ext_subst e as + Nothing -> Let (NonRec b2 a) (simple_app subst' e as) + where + (subst', b') = subst_opt_bndr subst b + b2 = add_info subst' b b' +simple_app subst e as + = foldl App (simple_opt_expr subst e) as + +---------------------- simple_opt_bind :: Subst -> CoreBind -> (Subst, Maybe CoreBind) simple_opt_bind subst (Rec prs) = (subst'', Just (Rec (reverse rev_prs'))) where (subst', bndrs') = subst_opt_bndrs subst (map fst prs) (subst'', rev_prs') = foldl do_pr (subst', []) (prs `zip` bndrs') - do_pr (subst, prs) ((b,r), b') = case simple_opt_pair subst b r of - Left subst' -> (subst', prs) - Right r' -> (subst, (b2,r'):prs) - where - b2 = add_info subst b b' + do_pr (subst, prs) ((b,r), b') + = case maybe_substitute subst b r2 of + Just subst' -> (subst', prs) + Nothing -> (subst, (b2,r2):prs) + where + b2 = add_info subst b b' + r2 = simple_opt_expr subst r simple_opt_bind subst (NonRec b r) - = case simple_opt_pair subst b r of - Left ext_subst -> (ext_subst, Nothing) - Right r' -> (subst', Just (NonRec b2 r')) - where - (subst', b') = subst_opt_bndr subst b - b2 = add_info subst' b b' + = case maybe_substitute subst b r' of + Just ext_subst -> (ext_subst, Nothing) + Nothing -> (subst', Just (NonRec b2 r')) + where + r' = simple_opt_expr subst r + (subst', b') = subst_opt_bndr subst b + b2 = add_info subst' b b' ---------------------- -simple_opt_pair :: Subst -> InVar -> InExpr -> Either Subst OutExpr - -- (simple_opt_pair subst in_var in_rhs) +maybe_substitute :: Subst -> InVar -> OutExpr -> Maybe Subst + -- (maybe_substitute subst in_var out_rhs) -- either extends subst with (in_var -> out_rhs) - -- or return out_rhs for a binding out_var = out_rhs -simple_opt_pair subst b r + -- or returns Nothing +maybe_substitute subst b r | Type ty <- r -- let a::* = TYPE ty in = ASSERT( isTyCoVar b ) - Left (extendTvSubst subst b (substTy subst ty)) + Just (extendTvSubst subst b ty) | isId b -- let x = e in , safe_to_inline (idOccInfo b) , isAlwaysActive (idInlineActivation b) -- Note [Inline prag in simplOpt] , not (isStableUnfolding (idUnfolding b)) , not (isExportedId b) - = Left (extendIdSubst subst b r') + = Just (extendIdSubst subst b r) | otherwise - = Right r' + = Nothing where - r' = simple_opt_expr subst r - -- Unconditionally safe to inline safe_to_inline :: OccInfo -> Bool safe_to_inline (IAmALoopBreaker {}) = False safe_to_inline IAmDead = True - safe_to_inline (OneOcc in_lam one_br _) = (not in_lam && one_br) || exprIsTrivial r' - safe_to_inline NoOccInfo = exprIsTrivial r' + safe_to_inline (OneOcc in_lam one_br _) = (not in_lam && one_br) || exprIsTrivial r + safe_to_inline NoOccInfo = exprIsTrivial r ---------------------- subst_opt_bndr :: Subst -> InVar -> (Subst, OutVar) @@ -851,11 +899,6 @@ add_info subst old_bndr new_bndr | otherwise = maybeModifyIdInfo mb_new_info new_bndr where mb_new_info = substIdInfo subst new_bndr (idInfo old_bndr) - ----------------------- -maybeLet :: Maybe CoreBind -> CoreExpr -> CoreExpr -maybeLet Nothing e = e -maybeLet (Just b) e = Let b e \end{code} Note [Inline prag in simplOpt]