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"
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:
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
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
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)
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
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
| 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 }
_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 )
-- dropped as dead code, because we don't treat the UnfoldingSource
-- as an "occurrence".
-- Note [Worker inlining]
- InlineRule
+ InlineStable
substUnfoldingSource _ src = src
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
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
-- 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
; 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
= 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)
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)
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 <body>
= ASSERT( isTyCoVar b )
- Left (extendTvSubst subst b (substTy subst ty))
+ Just (extendTvSubst subst b ty)
| isId b -- let x = e in <body>
, 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)
| 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]