%
-% (c) The AQUA Project, Glasgow University, 1993-1996
+% (c) The AQUA Project, Glasgow University, 1993-1998
%
\section[Simplify]{The main module of the simplifier}
\begin{code}
-#include "HsVersions.h"
-
-module Simplify ( simplTopBinds, simplExpr, simplBind ) where
+module Simplify ( simplExpr, simplBind ) where
-IMP_Ubiq(){-uitous-}
-IMPORT_DELOOPER(SmplLoop) -- paranoia checking
+#include "HsVersions.h"
-import BinderInfo
-import CmdLineOpts ( SimplifierSwitch(..) )
-import ConFold ( completePrim )
-import CostCentre ( isSccCountCostCentre, cmpCostCentre )
+import CmdLineOpts ( switchIsOn, opt_SccProfilingOn,
+ opt_NoPreInlining, opt_DictsStrict, opt_D_dump_inlinings,
+ SimplifierSwitch(..)
+ )
+import SimplMonad
+import SimplUtils ( mkCase, etaCoreExpr, etaExpandCount, findAlt, mkRhsTyLam,
+ simplBinder, simplBinders, simplIds, findDefault
+ )
+import Var ( TyVar, mkSysTyVar, tyVarKind )
+import VarEnv
+import VarSet
+import Id ( Id, idType,
+ getIdUnfolding, setIdUnfolding,
+ getIdSpecialisation, setIdSpecialisation,
+ getIdDemandInfo, setIdDemandInfo,
+ getIdArity, setIdArity,
+ setInlinePragma, getInlinePragma, idMustBeINLINEd,
+ idWantsToBeINLINEd
+ )
+import IdInfo ( InlinePragInfo(..), OccInfo(..),
+ ArityInfo, atLeastArity, arityLowerBound, unknownArity
+ )
+import Demand ( Demand, isStrict, wwLazy )
+import Const ( isWHNFCon, conOkForAlt )
+import ConFold ( cleverMkPrimApp )
+import PrimOp ( PrimOp )
+import DataCon ( DataCon, dataConNumInstArgs, dataConStrictMarks, dataConSig, dataConArgTys )
+import Const ( Con(..) )
+import MagicUFs ( applyMagicUnfoldingFun )
+import Name ( isExported, isLocallyDefined )
import CoreSyn
-import CoreUtils ( coreExprType, nonErrorRHSs, maybeErrorApp,
- unTagBinders, squashableDictishCcExpr,
- manifestlyWHNF
+import CoreUnfold ( Unfolding(..), UnfoldingGuidance(..),
+ mkUnfolding, smallEnoughToInline,
+ isEvaldUnfolding
)
-import Id ( idType, idWantsToBeINLINEd,
- getIdDemandInfo, addIdDemandInfo,
- GenId{-instance NamedThing-}
+import CoreUtils ( IdSubst, SubstCoreExpr(..),
+ cheapEqExpr, exprIsDupable, exprIsWHNF, exprIsTrivial,
+ coreExprType, exprIsCheap, substExpr,
+ FormSummary(..), mkFormSummary, whnfOrBottom
)
-import IdInfo ( willBeDemanded, DemandInfo )
-import Literal ( isNoRepLit )
+import SpecEnv ( lookupSpecEnv, isEmptySpecEnv, substSpecEnv )
+import CostCentre ( isSubsumedCCS, currentCCS, isEmptyCC )
+import Type ( Type, mkTyVarTy, mkTyVarTys, isUnLiftedType, fullSubstTy, applyTys,
+ mkFunTy, splitFunTys, splitTyConApp_maybe, funResultTy )
+import TyCon ( isDataTyCon, tyConDataCons, tyConClass_maybe, tyConArity, isDataTyCon )
+import TysPrim ( realWorldStatePrimTy )
+import PrelVals ( realWorldPrimId )
+import BasicTypes ( StrictnessMark(..) )
import Maybes ( maybeToBool )
-import Name ( isLocallyDefined )
-import PprStyle ( PprStyle(..) )
-import PprType ( GenType{-instance Outputable-} )
-import Pretty ( ppAbove )
-import PrimOp ( primOpOkForSpeculation, PrimOp(..) )
-import SimplCase ( simplCase, bindLargeRhs )
-import SimplEnv
-import SimplMonad
-import SimplVar ( completeVar )
-import SimplUtils
-import Type ( mkTyVarTy, mkTyVarTys, mkAppTy,
- splitFunTy, getFunTy_maybe, eqTy
- )
-import TysWiredIn ( realWorldStateTy )
-import Util ( isSingleton, zipEqual, panic, pprPanic, assertPanic )
+import Util ( zipWithEqual, stretchZipEqual )
+import PprCore
+import Outputable
\end{code}
-The controlling flags, and what they do
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-
-passes:
-------
--fsimplify = run the simplifier
--ffloat-inwards = runs the float lets inwards pass
--ffloat = runs the full laziness pass
- (ToDo: rename to -ffull-laziness)
--fupdate-analysis = runs update analyser
--fstrictness = runs strictness analyser
--fsaturate-apps = saturates applications (eta expansion)
-
-options:
--------
--ffloat-past-lambda = OK to do full laziness.
- (ToDo: remove, as the full laziness pass is
- useless without this flag, therefore
- it is unnecessary. Just -ffull-laziness
- should be kept.)
-
--ffloat-lets-ok = OK to float lets out of lets if the enclosing
- let is strict or if the floating will expose
- a WHNF [simplifier].
-
--ffloat-primops-ok = OK to float out of lets cases whose scrutinee
- is a primop that cannot fail [simplifier].
-
--fcode-duplication-ok = allows the previous option to work on cases with
- multiple branches [simplifier].
-
--flet-to-case = does let-to-case transformation [simplifier].
-
--fcase-of-case = does case of case transformation [simplifier].
-
--fpedantic-bottoms = does not allow:
- case x of y -> e ===> e[x/y]
- (which may turn bottom into non-bottom)
-
-
- NOTES ON INLINING
- ~~~~~~~~~~~~~~~~~
-
-Inlining is one of the delicate aspects of the simplifier. By
-``inlining'' we mean replacing an occurrence of a variable ``x'' by
-the RHS of x's definition. Thus
-
- let x = e in ...x... ===> let x = e in ...e...
-
-We have two mechanisms for inlining:
-
-1. Unconditional. The occurrence analyser has pinned an (OneOcc
-FunOcc NoDupDanger NotInsideSCC n) flag on the variable, saying ``it's
-certainly safe to inline this variable, and to drop its binding''.
-(...Umm... if n <= 1; if n > 1, it is still safe, provided you are
-happy to be duplicating code...) When it encounters such a beast, the
-simplifer binds the variable to its RHS (in the id_env) and continues.
-It doesn't even look at the RHS at that stage. It also drops the
-binding altogether.
-
-2. Conditional. In all other situations, the simplifer simplifies
-the RHS anyway, and keeps the new binding. It also binds the new
-(cloned) variable to a ``suitable'' UnfoldingDetails in the UnfoldEnv.
-
-Here, ``suitable'' might mean NoUnfoldingDetails (if the occurrence
-info is ManyOcc and the RHS is not a manifest HNF, or UnfoldAlways (if
-the variable has an INLINE pragma on it). The idea is that anything
-in the UnfoldEnv is safe to use, but also has an enclosing binding if
-you decide not to use it.
-
-Head normal forms
-~~~~~~~~~~~~~~~~~
-We *never* put a non-HNF unfolding in the UnfoldEnv except in the
-INLINE-pragma case.
-
-At one time I thought it would be OK to put non-HNF unfoldings in for
-variables which occur only once [if they got inlined at that
-occurrence the RHS of the binding would become dead, so no duplication
-would occur]. But consider:
-@
- let x = <expensive>
- f = \y -> ...y...y...y...
- in f x
-@
-Now, it seems that @x@ appears only once, but even so it is NOT safe
-to put @x@ in the UnfoldEnv, because @f@ will be inlined, and will
-duplicate the references to @x@.
-
-Because of this, the "unconditional-inline" mechanism above is the
-only way in which non-HNFs can get inlined.
-
-INLINE pragmas
-~~~~~~~~~~~~~~
-
-When a variable has an INLINE pragma on it --- which includes wrappers
-produced by the strictness analyser --- we treat it rather carefully.
-
-For a start, we are careful not to substitute into its RHS, because
-that might make it BIG, and the user said "inline exactly this", not
-"inline whatever you get after inlining other stuff inside me". For
-example
-
- let f = BIG
- in {-# INLINE y #-} y = f 3
- in ...y...y...
-
-Here we don't want to substitute BIG for the (single) occurrence of f,
-because then we'd duplicate BIG when we inline'd y. (Exception:
-things in the UnfoldEnv with UnfoldAlways flags, which originated in
-other INLINE pragmas.)
-
-So, we clean out the UnfoldEnv of all GenForm inlinings before
-going into such an RHS.
-
-What about imports? They don't really matter much because we only
-inline relatively small things via imports.
-We augment the the UnfoldEnv with UnfoldAlways guidance if there's an
-INLINE pragma. We also do this for the RHSs of recursive decls,
-before looking at the recursive decls. That way we achieve the effect
-of inlining a wrapper in the body of its worker, in the case of a
-mutually-recursive worker/wrapper split.
+The guts of the simplifier is in this module, but the driver
+loop for the simplifier is in SimplPgm.lhs.
%************************************************************************
%* *
%************************************************************************
-At the top level things are a little different.
-
- * No cloning (not allowed for exported Ids, unnecessary for the others)
-
- * No floating. Case floating is obviously out. Let floating is
- theoretically OK, but dangerous because of space leaks.
- The long-distance let-floater lifts these lets.
-
\begin{code}
-simplTopBinds :: SimplEnv -> [InBinding] -> SmplM [OutBinding]
+simplExpr :: CoreExpr -> SimplCont -> SimplM CoreExpr
-simplTopBinds env [] = returnSmpl []
+simplExpr (Note InlineCall (Var v)) cont
+ = simplVar True v cont
--- Dead code is now discarded by the occurrence analyser,
+simplExpr (Var v) cont
+ = simplVar False v cont
-simplTopBinds env (NonRec binder@(in_id, occ_info) rhs : binds)
- | inlineUnconditionally ok_to_dup_code occ_info
- = let
- new_env = extendIdEnvWithInlining env env binder rhs
- in
- simplTopBinds new_env binds
- where
- ok_to_dup_code = switchIsSet env SimplOkToDupCode
+simplExpr (Con (PrimOp op) args) cont
+ = mapSmpl simplArg args `thenSmpl` \ args' ->
+ rebuild (cleverMkPrimApp op args') cont
-simplTopBinds env (NonRec binder@(in_id,occ_info) rhs : binds)
- = -- No cloning necessary at top level
- -- Process the binding
- simplRhsExpr env binder rhs `thenSmpl` \ rhs' ->
- let
- new_env = case rhs' of
- Var v -> extendIdEnvWithAtom env binder (VarArg v)
- Lit i | not (isNoRepLit i) -> extendIdEnvWithAtom env binder (LitArg i)
- other -> extendUnfoldEnvGivenRhs env binder in_id rhs'
- in
- -- Process the other bindings
- simplTopBinds new_env binds `thenSmpl` \ binds' ->
+simplExpr (Con con@(DataCon _) args) cont
+ = simplConArgs args $ \ args' ->
+ rebuild (Con con args') cont
- -- Glue together and return ...
- -- We leave it to susequent occurrence analysis to throw away
- -- an unused atom binding. This localises the decision about
- -- discarding top-level bindings.
- returnSmpl (NonRec in_id rhs' : binds')
+simplExpr expr@(Con con@(Literal _) args) cont
+ = ASSERT( null args )
+ rebuild expr cont
+
+simplExpr (App fun arg) cont
+ = getSubstEnv `thenSmpl` \ se ->
+ simplExpr fun (ApplyTo NoDup arg se cont)
+
+simplExpr (Case scrut bndr alts) cont
+ = getSubstEnv `thenSmpl` \ se ->
+ simplExpr scrut (Select NoDup bndr alts se cont)
+
+simplExpr (Note (Coerce to from) e) cont
+ | to == from = simplExpr e cont
+ | otherwise = getSubstEnv `thenSmpl` \ se ->
+ simplExpr e (CoerceIt NoDup to se cont)
+
+-- hack: we only distinguish subsumed cost centre stacks for the purposes of
+-- inlining. All other CCCSs are mapped to currentCCS.
+simplExpr (Note (SCC cc) e) cont
+ = setEnclosingCC currentCCS $
+ simplExpr e Stop `thenSmpl` \ e ->
+ rebuild (mkNote (SCC cc) e) cont
+
+simplExpr (Note note e) cont
+ = simplExpr e Stop `thenSmpl` \ e' ->
+ rebuild (mkNote note e') cont
+
+-- Let to case, but only if the RHS isn't a WHNF
+simplExpr (Let (NonRec bndr rhs) body) cont
+ = getSubstEnv `thenSmpl` \ se ->
+ simplBeta bndr rhs se body cont
+
+simplExpr (Let bind body) cont
+ = (simplBind bind $
+ simplExpr body cont) `thenSmpl` \ (binds', e') ->
+ returnSmpl (mkLets binds' e')
+
+-- Type-beta reduction
+simplExpr expr@(Lam bndr body) cont@(ApplyTo _ (Type ty_arg) arg_se body_cont)
+ = ASSERT( isTyVar bndr )
+ tick BetaReduction `thenSmpl_`
+ setSubstEnv arg_se (simplType ty_arg) `thenSmpl` \ ty' ->
+ extendTySubst bndr ty' $
+ simplExpr body body_cont
+
+-- Ordinary beta reduction
+simplExpr expr@(Lam bndr body) cont@(ApplyTo _ arg arg_se body_cont)
+ = tick BetaReduction `thenSmpl_`
+ simplBeta bndr' arg arg_se body body_cont
+ where
+ bndr' = zapLambdaBndr bndr body body_cont
-simplTopBinds env (Rec pairs : binds)
- = simplRecursiveGroup env triples `thenSmpl` \ (bind', new_env) ->
+simplExpr (Lam bndr body) cont
+ = simplBinder bndr $ \ bndr' ->
+ simplExpr body Stop `thenSmpl` \ body' ->
+ rebuild (Lam bndr' body') cont
- -- Process the other bindings
- simplTopBinds new_env binds `thenSmpl` \ binds' ->
- -- Glue together and return
- returnSmpl (bind' : binds')
- where
- triples = [(id, (binder, rhs)) | (binder@(id,_), rhs) <- pairs]
- -- No cloning necessary at top level
+simplExpr (Type ty) cont
+ = ASSERT( case cont of { Stop -> True; other -> False } )
+ simplType ty `thenSmpl` \ ty' ->
+ returnSmpl (Type ty')
\end{code}
-%************************************************************************
-%* *
-\subsection[Simplify-simplExpr]{The main function: simplExpr}
-%* *
-%************************************************************************
-
+---------------------------------
\begin{code}
-simplExpr :: SimplEnv
- -> InExpr -> [OutArg]
- -> SmplM OutExpr
+simplArg :: InArg -> SimplM OutArg
+simplArg arg = simplExpr arg Stop
\end{code}
-The expression returned has the same meaning as the input expression
-applied to the specified arguments.
-
-
-Variables
-~~~~~~~~~
-Check if there's a macro-expansion, and if so rattle on. Otherwise do
-the more sophisticated stuff.
+---------------------------------
+simplConArgs makes sure that the arguments all end up being atomic.
+That means it may generate some Lets, hence the
\begin{code}
-simplExpr env (Var v) args
- = case (lookupId env v) of
- Nothing -> let
- new_v = simplTyInId env v
- in
- completeVar env new_v args
-
- Just info ->
- case info of
- ItsAnAtom (LitArg lit) -- A boring old literal
- -- Paranoia check for args empty
- -> case args of
- [] -> returnSmpl (Lit lit)
- other -> panic "simplExpr:coVar"
-
- ItsAnAtom (VarArg var) -- More interesting! An id!
- -- No need to substitute the type env here,
- -- because we already have!
- -> completeVar env var args
-
- InlineIt id_env ty_env in_expr -- A macro-expansion
- -> simplExpr (replaceInEnvs env (ty_env, id_env)) in_expr args
+simplConArgs :: [InArg] -> ([OutArg] -> SimplM CoreExpr) -> SimplM CoreExpr
+simplConArgs [] thing_inside
+ = thing_inside []
+
+simplConArgs (arg:args) thing_inside
+ = switchOffInlining (simplArg arg) `thenSmpl` \ arg' ->
+ -- Simplify the RHS with inlining switched off, so that
+ -- only absolutely essential things will happen.
+
+ simplConArgs args $ \ args' ->
+
+ -- If the argument ain't trivial, then let-bind it
+ if exprIsTrivial arg' then
+ thing_inside (arg' : args')
+ else
+ newId (coreExprType arg') $ \ arg_id ->
+ thing_inside (Var arg_id : args') `thenSmpl` \ res ->
+ returnSmpl (bindNonRec arg_id arg' res)
\end{code}
-Literals
-~~~~~~~~
-
+---------------------------------
\begin{code}
-simplExpr env (Lit l) [] = returnSmpl (Lit l)
-#ifdef DEBUG
-simplExpr env (Lit l) _ = panic "simplExpr:Lit with argument"
-#endif
+simplType :: InType -> SimplM OutType
+simplType ty
+ = getTyEnv `thenSmpl` \ (ty_subst, in_scope) ->
+ returnSmpl (fullSubstTy ty_subst in_scope ty)
\end{code}
-Primitive applications are simple.
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-
-NB: Prim expects an empty argument list! (Because it should be
-saturated and not higher-order. ADR)
\begin{code}
-simplExpr env (Prim op prim_args) args
- = ASSERT (null args)
- let
- prim_args' = [simplArg env prim_arg | prim_arg <- prim_args]
- op' = simpl_op op
- in
- completePrim env op' prim_args'
+-- Find out whether the lambda is saturated,
+-- if not zap the over-optimistic info in the binder
+
+zapLambdaBndr bndr body body_cont
+ | isTyVar bndr || safe_info || definitely_saturated 20 body body_cont
+ -- The "20" is to catch pathalogical cases with bazillions of arguments
+ -- because we are using an n**2 algorithm here
+ = bndr -- No need to zap
+ | otherwise
+ = setInlinePragma (setIdDemandInfo bndr wwLazy)
+ safe_inline_prag
+
where
- -- PrimOps just need any types in them renamed.
+ inline_prag = getInlinePragma bndr
+ demand = getIdDemandInfo bndr
- simpl_op (CCallOp label is_asm may_gc arg_tys result_ty)
- = let
- arg_tys' = map (simplTy env) arg_tys
- result_ty' = simplTy env result_ty
- in
- CCallOp label is_asm may_gc arg_tys' result_ty'
+ safe_info = is_safe_inline_prag && not (isStrict demand)
- simpl_op other_op = other_op
-\end{code}
+ is_safe_inline_prag = case inline_prag of
+ ICanSafelyBeINLINEd StrictOcc nalts -> False
+ ICanSafelyBeINLINEd LazyOcc nalts -> False
+ other -> True
-Constructor applications
-~~~~~~~~~~~~~~~~~~~~~~~~
-Nothing to try here. We only reuse constructors when they appear as the
-rhs of a let binding (see completeLetBinding).
+ safe_inline_prag = case inline_prag of
+ ICanSafelyBeINLINEd _ nalts
+ -> ICanSafelyBeINLINEd InsideLam nalts
+ other -> inline_prag
-\begin{code}
-simplExpr env (Con con con_args) args
- = ASSERT( null args )
- returnSmpl (Con con [simplArg env con_arg | con_arg <- con_args])
+ definitely_saturated 0 _ _ = False -- Too expensive to find out
+ definitely_saturated n (Lam _ body) (ApplyTo _ _ _ cont) = definitely_saturated (n-1) body cont
+ definitely_saturated n (Lam _ _) other_cont = False
+ definitely_saturated n _ _ = True
\end{code}
+%************************************************************************
+%* *
+\subsection{Variables}
+%* *
+%************************************************************************
-Applications are easy too:
-~~~~~~~~~~~~~~~~~~~~~~~~~~
-Just stuff 'em in the arg stack
-
+Coercions
+~~~~~~~~~
\begin{code}
-simplExpr env (App fun arg) args
- = simplExpr env fun (simplArg env arg : args)
-\end{code}
+simplVar inline_call var cont
+ = getValEnv `thenSmpl` \ (id_subst, in_scope) ->
+ case lookupVarEnv id_subst var of
+ Just (Done e)
+ -> zapSubstEnv (simplExpr e cont)
+
+ Just (SubstMe e ty_subst id_subst)
+ -> setSubstEnv (ty_subst, id_subst) (simplExpr e cont)
+
+ Nothing -> let
+ var' = case lookupVarSet in_scope var of
+ Just v' -> v'
+ Nothing ->
+#ifdef DEBUG
+ if isLocallyDefined var && not (idMustBeINLINEd var) then
+ -- Not in scope
+ pprTrace "simplVar:" (ppr var) var
+ else
+#endif
+ var
+ in
+ getSwitchChecker `thenSmpl` \ sw_chkr ->
+ completeVar sw_chkr in_scope inline_call var' cont
+
+completeVar sw_chkr in_scope inline_call var cont
+ | maybeToBool maybe_magic_result
+ = tick MagicUnfold `thenSmpl_`
+ magic_result
+
+ -- Look for existing specialisations before trying inlining
+ | maybeToBool maybe_specialisation
+ = tick SpecialisationDone `thenSmpl_`
+ setSubstEnv (spec_bindings, emptyVarEnv) (
+ -- See note below about zapping the substitution here
+
+ simplExpr spec_template remaining_cont
+ )
-Type lambdas
-~~~~~~~~~~~~
+ -- Don't actually inline the scrutinee when we see
+ -- case x of y { .... }
+ -- and x has unfolding (C a b). Why not? Because
+ -- we get a silly binding y = C a b. If we don't
+ -- inline knownCon can directly substitute x for y instead.
+ | has_unfolding && is_case_scrutinee && unfolding_is_constr
+ = knownCon (Var var) con con_args cont
+
+ -- Look for an unfolding. There's a binding for the
+ -- thing, but perhaps we want to inline it anyway
+ | has_unfolding && (inline_call || ok_to_inline)
+ = getEnclosingCC `thenSmpl` \ encl_cc ->
+ if must_be_unfolded || costCentreOk encl_cc (coreExprCc unf_template)
+ then -- OK to unfold
+
+ tickUnfold var `thenSmpl_` (
+
+ zapSubstEnv $
+ -- The template is already simplified, so don't re-substitute.
+ -- This is VITAL. Consider
+ -- let x = e in
+ -- let y = \z -> ...x... in
+ -- \ x -> ...y...
+ -- We'll clone the inner \x, adding x->x' in the id_subst
+ -- Then when we inline y, we must *not* replace x by x' in
+ -- the inlined copy!!
+#ifdef DEBUG
+ if opt_D_dump_inlinings then
+ pprTrace "Inlining:" (ppr var <+> ppr unf_template) $
+ simplExpr unf_template cont
+ else
+#endif
+ simplExpr unf_template cont
+ )
+ else
+#ifdef DEBUG
+ pprTrace "Inlining disallowed due to CC:\n" (ppr encl_cc <+> ppr unf_template <+> ppr (coreExprCc unf_template)) $
+#endif
+ -- Can't unfold because of bad cost centre
+ rebuild (Var var) cont
-We only eta-reduce a type lambda if all type arguments in the body can
-be eta-reduced. This requires us to collect up all tyvar parameters so
-we can pass them all to @mkTyLamTryingEta@.
+ | inline_call -- There was an InlineCall note, but we didn't inline!
+ = rebuild (Note InlineCall (Var var)) cont
-\begin{code}
-simplExpr env (Lam (TyBinder tyvar) body) (TyArg ty : args)
- = -- ASSERT(not (isPrimType ty))
- let
- new_env = extendTyEnv env tyvar ty
- in
- tick TyBetaReduction `thenSmpl_`
- simplExpr new_env body args
+ | otherwise
+ = rebuild (Var var) cont
-simplExpr env tylam@(Lam (TyBinder tyvar) body) []
- = do_tylambdas env [] tylam
where
- do_tylambdas env tyvars' (Lam (TyBinder tyvar) body)
- = -- Clone the type variable
- cloneTyVarSmpl tyvar `thenSmpl` \ tyvar' ->
- let
- new_env = extendTyEnv env tyvar (mkTyVarTy tyvar')
- in
- do_tylambdas new_env (tyvar':tyvars') body
-
- do_tylambdas env tyvars' body
- = simplExpr env body [] `thenSmpl` \ body' ->
- returnSmpl (
- (if switchIsSet env SimplDoEtaReduction
- then mkTyLamTryingEta
- else mkTyLam) (reverse tyvars') body'
- )
-
-#ifdef DEBUG
-simplExpr env (Lam (TyBinder _) _) (_ : _)
- = panic "simplExpr:TyLam with non-TyArg"
-#endif
-\end{code}
+ unfolding = getIdUnfolding var
+
+ ---------- Magic unfolding stuff
+ maybe_magic_result = case unfolding of
+ MagicUnfolding _ magic_fn -> applyMagicUnfoldingFun magic_fn
+ cont
+ other -> Nothing
+ Just magic_result = maybe_magic_result
+
+ ---------- Unfolding stuff
+ has_unfolding = case unfolding of
+ CoreUnfolding _ _ _ -> True
+ other -> False
+
+ -- overrides cost-centre business
+ must_be_unfolded = case getInlinePragma var of
+ IMustBeINLINEd -> True
+ _ -> False
+
+ CoreUnfolding form guidance unf_template = unfolding
+
+ unfolding_is_constr = case unf_template of
+ Con con _ -> conOkForAlt con
+ other -> False
+ Con con con_args = unf_template
+
+ ---------- Specialisation stuff
+ ty_args = initial_ty_args cont
+ remaining_cont = drop_ty_args cont
+ maybe_specialisation = lookupSpecEnv (ppr var) (getIdSpecialisation var) ty_args
+ Just (spec_bindings, spec_template) = maybe_specialisation
+
+ initial_ty_args (ApplyTo _ (Type ty) (ty_subst,_) cont)
+ = fullSubstTy ty_subst in_scope ty : initial_ty_args cont
+ -- Having to do the substitution here is a bit of a bore
+ initial_ty_args other_cont = []
+
+ drop_ty_args (ApplyTo _ (Type _) _ cont) = drop_ty_args cont
+ drop_ty_args other_cont = other_cont
+
+ ---------- Switches
+ ok_to_inline = okToInline essential_unfoldings_only is_case_scrutinee var form guidance cont
+ essential_unfoldings_only = switchIsOn sw_chkr EssentialUnfoldingsOnly
+
+ is_case_scrutinee = case cont of
+ Select _ _ _ _ _ -> True
+ other -> False
+
+----------- costCentreOk
+-- costCentreOk checks that it's ok to inline this thing
+-- The time it *isn't* is this:
+--
+-- f x = let y = E in
+-- scc "foo" (...y...)
+--
+-- Here y has a "current cost centre", and we can't inline it inside "foo",
+-- regardless of whether E is a WHNF or not.
+
+costCentreOk ccs_encl cc_rhs
+ = not opt_SccProfilingOn
+ || isSubsumedCCS ccs_encl -- can unfold anything into a subsumed scope
+ || not (isEmptyCC cc_rhs) -- otherwise need a cc on the unfolding
+\end{code}
-Ordinary lambdas
-~~~~~~~~~~~~~~~~
+%************************************************************************
+%* *
+\subsection{Bindings}
+%* *
+%************************************************************************
\begin{code}
-simplExpr env (Lam (ValBinder binder) body) args
- | null leftover_binders
- = -- The lambda is saturated (or over-saturated)
- tick BetaReduction `thenSmpl_`
- simplExpr env_for_enough_args body leftover_args
-
- | otherwise
- = -- Too few args to saturate the lambda
- ASSERT( null leftover_args )
+simplBind :: CoreBind -> SimplM a -> SimplM ([CoreBind], a)
- (if not (null args) -- ah, we must've gotten rid of some...
- then tick BetaReduction
- else returnSmpl (panic "BetaReduction")
- ) `thenSmpl_`
+simplBind (NonRec bndr rhs) thing_inside
+ = simplTopRhs bndr rhs `thenSmpl` \ (binds, rhs', arity, in_scope) ->
+ setInScope in_scope $
+ completeBindNonRec (bndr `setIdArity` arity) rhs' thing_inside `thenSmpl` \ (maybe_bind, res) ->
+ let
+ binds' = case maybe_bind of
+ Just (bndr,rhs) -> binds ++ [NonRec bndr rhs]
+ Nothing -> binds
+ in
+ returnSmpl (binds', res)
- simplLam env_for_too_few_args leftover_binders body
- 0 {- Guaranteed applied to at least 0 args! -}
+simplBind (Rec pairs) thing_inside
+ = simplIds (map fst pairs) $ \ bndrs' ->
+ -- NB: bndrs' don't have unfoldings or spec-envs
+ -- We add them as we go down, using simplPrags
+ go (pairs `zip` bndrs') `thenSmpl` \ (pairs', thing') ->
+ returnSmpl ([Rec pairs'], thing')
where
- (binder_args_pairs, leftover_binders, leftover_args) = collect_val_args binder args
-
- env_for_enough_args = extendIdEnvWithAtomList env binder_args_pairs
-
- env_for_too_few_args = extendIdEnvWithAtomList env zapped_binder_args_pairs
-
- -- Since there aren't enough args the binders we are cancelling with
- -- the args supplied are, in effect, ocurring inside a lambda.
- -- So we modify their occurrence info to reflect this fact.
- -- Example: (\ x y z -> e) p q
- -- ==> (\z -> e[p/x, q/y])
- -- but we should behave as if x and y are marked "inside lambda".
- -- The occurrence analyser does not mark them so itself because then we
- -- do badly on the very common case of saturated lambdas applications:
- -- (\ x y z -> e) p q r
- -- ==> e[p/x, q/y, r/z]
- --
- zapped_binder_args_pairs = [ ((id, markDangerousToDup occ_info), arg)
- | ((id, occ_info), arg) <- binder_args_pairs ]
-
- collect_val_args :: InBinder -- Binder
- -> [OutArg] -- Arguments
- -> ([(InBinder,OutArg)], -- Binder,arg pairs (ToDo: a maybe?)
- [InBinder], -- Leftover binders (ToDo: a maybe)
- [OutArg]) -- Leftover args
-
- -- collect_val_args strips off the leading ValArgs from
- -- the current arg list, returning them along with the
- -- depleted list
- collect_val_args binder [] = ([], [binder], [])
- collect_val_args binder (arg : args) | isValArg arg
- = ([(binder,arg)], [], args)
-
-#ifdef DEBUG
- collect_val_args _ (other_val_arg : _) = panic "collect_val_args"
- -- TyArg should never meet a Lam
-#endif
+ go [] = thing_inside `thenSmpl` \ res ->
+ returnSmpl ([], res)
+
+ go (((bndr, rhs), bndr') : pairs)
+ = simplTopRhs bndr rhs `thenSmpl` \ (rhs_binds, rhs', arity, in_scope) ->
+ setInScope in_scope $
+ completeBindRec bndr (bndr' `setIdArity` arity)
+ rhs' (go pairs) `thenSmpl` \ (pairs', res) ->
+ returnSmpl (flatten rhs_binds pairs', res)
+
+ flatten (NonRec b r : binds) prs = (b,r) : flatten binds prs
+ flatten (Rec prs1 : binds) prs2 = prs1 ++ flatten binds prs2
+ flatten [] prs = prs
+
+
+completeBindRec bndr bndr' rhs' thing_inside
+ | postInlineUnconditionally bndr etad_rhs
+ -- NB: a loop breaker never has postInlineUnconditionally True
+ -- and non-loop-breakers only have *forward* references
+ = tick PostInlineUnconditionally `thenSmpl_`
+ extendIdSubst bndr (Done etad_rhs) thing_inside
+
+ | otherwise
+ = -- Here's the only difference from completeBindNonRec: we
+ -- don't do simplBinder first, because we've already
+ -- done simplBinder on the recursive binders
+ simplPrags bndr bndr' etad_rhs `thenSmpl` \ bndr'' ->
+ modifyInScope bndr'' $
+ thing_inside `thenSmpl` \ (pairs, res) ->
+ returnSmpl ((bndr'', etad_rhs) : pairs, res)
+ where
+ etad_rhs = etaCoreExpr rhs'
\end{code}
-Let expressions
-~~~~~~~~~~~~~~~
+%************************************************************************
+%* *
+\subsection{Right hand sides}
+%* *
+%************************************************************************
+
+simplRhs basically just simplifies the RHS of a let(rec).
+It does two important optimisations though:
+
+ * It floats let(rec)s out of the RHS, even if they
+ are hidden by big lambdas
-\begin{code}
-simplExpr env (Let bind body) args
+ * It does eta expansion
-{- OMIT this; it's a pain to do at the other sites wehre simplBind is called,
- and it doesn't seem worth retaining the ability to not float applications
- into let/case
+\begin{code}
+simplTopRhs :: InId -> InExpr
+ -> SimplM ([OutBind], OutExpr, ArityInfo, InScopeEnv)
+simplTopRhs bndr rhs
+ = getSubstEnv `thenSmpl` \ bndr_se ->
+ simplRhs bndr bndr_se rhs
+
+simplRhs :: InId -> SubstEnv -> InExpr
+ -> SimplM ([OutBind], OutExpr, ArityInfo, InScopeEnv)
+
+simplRhs bndr bndr_se rhs
+ | idWantsToBeINLINEd bndr -- Don't inline in the RHS of something that has an
+ -- inline pragma. But be careful that the InScopeEnv that
+ -- we return does still have inlinings on!
+ = switchOffInlining (simplExpr rhs Stop) `thenSmpl` \ rhs' ->
+ getInScope `thenSmpl` \ in_scope ->
+ returnSmpl ([], rhs', unknownArity, in_scope)
+
+ | float_exposes_hnf rhs
+ = mkRhsTyLam rhs `thenSmpl` \ rhs' ->
+ -- Swizzle the inner lets past the big lambda (if any)
+ float rhs'
- | switchIsSet env SimplNoLetFromApp
- = simplBind env bind (\env -> simplExpr env body [])
- (computeResultType env body []) `thenSmpl` \ let_expr' ->
- returnSmpl (mkGenApp let_expr' args)
+ | otherwise
+ = finish rhs
+ where
+ float (Let bind body) = tick LetFloatFromLet `thenSmpl_`
+ simplBind bind (float body) `thenSmpl` \ (binds1, (binds2, body', arity, in_scope)) ->
+ returnSmpl (binds1 ++ binds2, body', arity, in_scope)
+ float body = finish body
- | otherwise -- No float from application
--}
- = simplBind env bind (\env -> simplExpr env body args)
- (computeResultType env body args)
-\end{code}
+ finish rhs = simplRhs2 bndr bndr_se rhs `thenSmpl` \ (rhs', arity) ->
+ getInScope `thenSmpl` \ in_scope ->
+ returnSmpl ([], rhs', arity, in_scope)
-Case expressions
-~~~~~~~~~~~~~~~~
+ float_exposes_hnf (Lam b e) | isTyVar b
+ = float_exposes_hnf e -- Ignore leading big lambdas
+ float_exposes_hnf (Let _ e) = try e -- Now look for nested lets
+ float_exposes_hnf e = False -- Don't bother if no lets!
-\begin{code}
-simplExpr env expr@(Case scrut alts) args
- = simplCase env scrut alts (\env rhs -> simplExpr env rhs args)
- (computeResultType env expr args)
+ try (Let _ e) = try e
+ try e = exprIsWHNF e
\end{code}
+---------------------------------------------------------
+ Try eta expansion for RHSs
+
+We need to pass in the substitution environment for the RHS, because
+it might be different to the current one (see simplBeta, as called
+from simplExpr for an applied lambda). The binder needs to
-Coercions
-~~~~~~~~~
\begin{code}
-simplExpr env (Coerce coercion ty body) args
- = simplCoerce env coercion ty body args
-\end{code}
+simplRhs2 bndr bndr_se rhs
+ = getSwitchChecker `thenSmpl` \ sw_chkr ->
+ simplBinders tyvars $ \ tyvars' ->
+ simplBinders ids $ \ ids' ->
+
+ if switchIsOn sw_chkr SimplDoLambdaEtaExpansion
+ && not (null ids) -- Prevent eta expansion for both thunks
+ -- (would lose sharing) and variables (nothing gained).
+ -- To see why we ignore it for thunks, consider
+ -- let f = lookup env key in (f 1, f 2)
+ -- We'd better not eta expand f just because it is
+ -- always applied!
+ && not (null extra_arg_tys)
+ then
+ tick EtaExpansion `thenSmpl_`
+ setSubstEnv bndr_se (mapSmpl simplType extra_arg_tys)
+ `thenSmpl` \ extra_arg_tys' ->
+ newIds extra_arg_tys' $ \ extra_bndrs' ->
+ simplExpr body (mk_cont extra_bndrs') `thenSmpl` \ body' ->
+ returnSmpl ( mkLams tyvars'
+ $ mkLams ids'
+ $ mkLams extra_bndrs' body',
+ atLeastArity (no_of_ids + no_of_extras))
+ else
+ simplExpr body Stop `thenSmpl` \ body' ->
+ returnSmpl ( mkLams tyvars'
+ $ mkLams ids' body',
+ atLeastArity no_of_ids)
+ where
+ (tyvars, ids, body) = collectTyAndValBinders rhs
+ no_of_ids = length ids
-Set-cost-centre
-~~~~~~~~~~~~~~~
+ potential_extra_arg_tys :: [InType] -- NB: InType
+ potential_extra_arg_tys = case splitFunTys (applyTys (idType bndr) (mkTyVarTys tyvars)) of
+ (arg_tys, _) -> drop no_of_ids arg_tys
-1) Eliminating nested sccs ...
-We must be careful to maintain the scc counts ...
+ extra_arg_tys :: [InType]
+ extra_arg_tys = take no_extras_wanted potential_extra_arg_tys
+ no_of_extras = length extra_arg_tys
-\begin{code}
-simplExpr env (SCC cc1 (SCC cc2 expr)) args
- | not (isSccCountCostCentre cc2) && case cmpCostCentre cc1 cc2 of { EQ_ -> True; _ -> False }
- -- eliminate inner scc if no call counts and same cc as outer
- = simplExpr env (SCC cc1 expr) args
-
- | not (isSccCountCostCentre cc2) && not (isSccCountCostCentre cc1)
- -- eliminate outer scc if no call counts associated with either ccs
- = simplExpr env (SCC cc2 expr) args
-\end{code}
-
-2) Moving sccs inside lambdas ...
-
-\begin{code}
-simplExpr env (SCC cc (Lam binder@(ValBinder _) body)) args
- | not (isSccCountCostCentre cc)
- -- move scc inside lambda only if no call counts
- = simplExpr env (Lam binder (SCC cc body)) args
-
-simplExpr env (SCC cc (Lam binder body)) args
- -- always ok to move scc inside type/usage lambda
- = simplExpr env (Lam binder (SCC cc body)) args
-\end{code}
+ no_extras_wanted = -- Use information about how many args the fn is applied to
+ (arity - no_of_ids) `max`
-3) Eliminating dict sccs ...
+ -- See if the body could obviously do with more args
+ etaExpandCount body `max`
-\begin{code}
-simplExpr env (SCC cc expr) args
- | squashableDictishCcExpr cc expr
- -- eliminate dict cc if trivial dict expression
- = simplExpr env expr args
-\end{code}
+ -- Finally, see if it's a state transformer, in which
+ -- case we eta-expand on principle! This can waste work,
+ -- but usually doesn't
+ case potential_extra_arg_tys of
+ [ty] | ty == realWorldStatePrimTy -> 1
+ other -> 0
-4) Moving arguments inside the body of an scc ...
-This moves the cost of doing the application inside the scc
-(which may include the cost of extracting methods etc)
+ arity = arityLowerBound (getIdArity bndr)
-\begin{code}
-simplExpr env (SCC cost_centre body) args
- = let
- new_env = setEnclosingCC env (EnclosingCC cost_centre)
- in
- simplExpr new_env body args `thenSmpl` \ body' ->
- returnSmpl (SCC cost_centre body')
+ mk_cont [] = Stop
+ mk_cont (b:bs) = ApplyTo OkToDup (Var b) emptySubstEnv (mk_cont bs)
\end{code}
+
%************************************************************************
%* *
-\subsection{Simplify RHS of a Let/Letrec}
+\subsection{Binding}
%* *
%************************************************************************
-simplRhsExpr does arity-expansion. That is, given:
+\begin{code}
+simplBeta :: InId -- Binder
+ -> InExpr -> SubstEnv -- Arg, with its subst-env
+ -> InExpr -> SimplCont -- Lambda body
+ -> SimplM OutExpr
+#ifdef DEBUG
+simplBeta bndr rhs rhs_se body cont
+ | isTyVar bndr
+ = pprPanic "simplBeta" ((ppr bndr <+> ppr rhs) $$ ppr cont)
+#endif
+
+simplBeta bndr rhs rhs_se body cont
+ | (isStrict (getIdDemandInfo bndr) || is_dict bndr)
+ && not (exprIsWHNF rhs)
+ = tick Let2Case `thenSmpl_`
+ getSubstEnv `thenSmpl` \ body_se ->
+ setSubstEnv rhs_se $
+ simplExpr rhs (Select NoDup bndr [(DEFAULT, [], body)] body_se cont)
- * a right hand side /\ tyvars -> \a1 ... an -> e
- * the information (stored in BinderInfo) that the function will always
- be applied to at least k arguments
+ | preInlineUnconditionally bndr && not opt_NoPreInlining
+ = tick PreInlineUnconditionally `thenSmpl_`
+ case rhs_se of { (ty_subst, id_subst) ->
+ extendIdSubst bndr (SubstMe rhs ty_subst id_subst) $
+ simplExpr body cont }
-it transforms the rhs to
+ | otherwise
+ = getSubstEnv `thenSmpl` \ bndr_se ->
+ setSubstEnv rhs_se (simplRhs bndr bndr_se rhs)
+ `thenSmpl` \ (floats, rhs', arity, in_scope) ->
+ setInScope in_scope $
+ completeBindNonRecE (bndr `setIdArity` arity) rhs' (
+ simplExpr body cont
+ ) `thenSmpl` \ body' ->
+ returnSmpl (mkLets floats body')
+ where
+ -- Return true only for dictionary types where the dictionary
+ -- has more than one component (else we risk poking on the component
+ -- of a newtype dictionary)
+ is_dict bndr
+ | not opt_DictsStrict = False
+ | otherwise
+ = case splitTyConApp_maybe (idType bndr) of
+ Nothing -> False
+ Just (tycon,tys) -> maybeToBool (tyConClass_maybe tycon) &&
+ length tys == tyConArity tycon &&
+ isDataTyCon tycon
+\end{code}
- /\tyvars -> \a1 ... an b(n+1) ... bk -> (e b(n+1) ... bk)
-This is a Very Good Thing!
+The completeBindNonRec family
+ - deals only with Ids, not TyVars
+ - take an already-simplified RHS
+ - always produce let bindings
+
+They do *not* attempt to do let-to-case. Why? Because
+they are used for top-level bindings, and in many situations where
+the "rhs" is known to be a WHNF (so let-to-case is inappropriate).
\begin{code}
-simplRhsExpr
- :: SimplEnv
- -> InBinder
- -> InExpr
- -> SmplM OutExpr
-
-simplRhsExpr env binder@(id,occ_info) rhs
- | dont_eta_expand rhs
- = simplExpr rhs_env rhs []
-
- | otherwise -- Have a go at eta expansion
- = -- Deal with the big lambda part
- mapSmpl cloneTyVarSmpl tyvars `thenSmpl` \ tyvars' ->
+completeBindNonRec :: InId -- Binder
+ -> OutExpr -- Simplified RHS
+ -> SimplM a -- Thing inside
+ -> SimplM (Maybe (OutId, OutExpr), a)
+completeBindNonRec bndr rhs thing_inside
+ | isDeadBinder bndr -- This happens; for example, the case_bndr during case of
+ -- known constructor: case (a,b) of x { (p,q) -> ... }
+ -- Here x isn't mentioned in the RHS, so we don't want to
+ -- create the (dead) let-binding let x = (a,b) in ...
+ = thing_inside `thenSmpl` \ res ->
+ returnSmpl (Nothing,res)
+
+ | postInlineUnconditionally bndr etad_rhs
+ = tick PostInlineUnconditionally `thenSmpl_`
+ extendIdSubst bndr (Done etad_rhs) (
+ thing_inside `thenSmpl` \ res ->
+ returnSmpl (Nothing,res)
+ )
+
+ | otherwise -- Note that we use etad_rhs here
+ -- This gives maximum chance for a remaining binding
+ -- to be zapped by the indirection zapper in OccurAnal
+ = simplBinder bndr $ \ bndr' ->
+ simplPrags bndr bndr' etad_rhs `thenSmpl` \ bndr'' ->
+ modifyInScope bndr'' $
+ thing_inside `thenSmpl` \ res ->
+ returnSmpl (Just (bndr'', etad_rhs), res)
+ where
+ etad_rhs = etaCoreExpr rhs
+
+completeBindNonRecE :: InId -> OutExpr -> SimplM OutExpr -> SimplM OutExpr
+completeBindNonRecE bndr rhs thing_inside
+ = completeBindNonRec bndr rhs thing_inside `thenSmpl` \ (maybe_bind, body) ->
+ returnSmpl (case maybe_bind of
+ Nothing -> body
+ Just (bndr, rhs) -> bindNonRec bndr rhs body)
+
+-- (simplPrags old_bndr new_bndr new_rhs) does two things
+-- (a) it attaches the new unfolding to new_bndr
+-- (b) it grabs the SpecEnv from old_bndr, applies the current
+-- substitution to it, and attaches it to new_bndr
+-- The assumption is that new_bndr, which is produced by simplBinder
+-- has no unfolding or specenv.
+
+simplPrags old_bndr new_bndr new_rhs
+ | isEmptySpecEnv spec_env
+ = returnSmpl (bndr_w_unfolding)
+
+ | otherwise
+ = getSimplBinderStuff `thenSmpl` \ (ty_subst, id_subst, in_scope, us) ->
let
- lam_env = extendTyEnvList rhs_env (zipEqual "simplRhsExpr" tyvars (mkTyVarTys tyvars'))
+ spec_env' = substSpecEnv ty_subst in_scope (subst_val id_subst) spec_env
in
- -- Deal with the little lambda part
- -- Note that we call simplLam even if there are no binders, in case
- -- it can do arity expansion.
- simplLam lam_env binders body min_no_of_args `thenSmpl` \ lambda' ->
-
- -- Put it back together
- returnSmpl (
- (if switchIsSet env SimplDoEtaReduction
- then mkTyLamTryingEta
- else mkTyLam) tyvars' lambda'
- )
+ returnSmpl (bndr_w_unfolding `setIdSpecialisation` spec_env')
where
- -- Note from ANDY:
- -- If you say {-# INLINE #-} then you get what's coming to you;
- -- you are saying inline the rhs, please.
- -- we might want a {-# INLINE UNSIMPLIFIED #-} option.
- rhs_env | simplIdWantsToBeINLINEd id env = filterUnfoldEnvForInlines env
- | otherwise = env
-
- (uvars, tyvars, binders, body) = collectBinders rhs
-
- min_no_of_args | not (null binders) && -- It's not a thunk
- switchIsSet env SimplDoArityExpand -- Arity expansion on
- = getBinderInfoArity occ_info - length binders
-
- | otherwise -- Not a thunk
- = 0 -- Play safe!
-
- -- dont_eta_expand prevents eta expansion in silly situations.
- -- For example, consider the defn
- -- x = y
- -- It would be silly to eta expand the "y", because it would just
- -- get eta-reduced back to y. Furthermore, if this was a top level defn,
- -- and x was exported, then the defn won't be eliminated, so this
- -- silly expand/reduce cycle will happen every time, which makes the
- -- simplifier loop!.
- -- The solution is to not even try eta expansion unless the rhs looks
- -- non-trivial.
- dont_eta_expand (Lit _) = True
- dont_eta_expand (Var _) = True
- dont_eta_expand (Con _ _) = True
- dont_eta_expand (App f a)
- | notValArg a = dont_eta_expand f
- dont_eta_expand (Lam x b)
- | notValBinder x = dont_eta_expand b
- dont_eta_expand _ = False
-\end{code}
+ bndr_w_unfolding = new_bndr `setIdUnfolding` mkUnfolding new_rhs
+ spec_env = getIdSpecialisation old_bndr
+ subst_val id_subst ty_subst in_scope expr
+ = substExpr ty_subst id_subst in_scope expr
+\end{code}
-%************************************************************************
-%* *
-\subsection{Simplify a lambda abstraction}
-%* *
-%************************************************************************
+\begin{code}
+preInlineUnconditionally :: InId -> Bool
+ -- Examines a bndr to see if it is used just once in a
+ -- completely safe way, so that it is safe to discard the binding
+ -- inline its RHS at the (unique) usage site, REGARDLESS of how
+ -- big the RHS might be. If this is the case we don't simplify
+ -- the RHS first, but just inline it un-simplified.
+ --
+ -- This is much better than first simplifying a perhaps-huge RHS
+ -- and then inlining and re-simplifying it.
+ --
+ -- NB: we don't even look at the RHS to see if it's trivial
+ -- We might have
+ -- x = y
+ -- where x is used many times, but this is the unique occurrence
+ -- of y. We should NOT inline x at all its uses, because then
+ -- we'd do the same for y -- aargh! So we must base this
+ -- pre-rhs-simplification decision solely on x's occurrences, not
+ -- on its rhs.
+preInlineUnconditionally bndr
+ = case getInlinePragma bndr of
+ ICanSafelyBeINLINEd InsideLam _ -> False
+ ICanSafelyBeINLINEd not_in_lam True -> True -- Not inside a lambda,
+ -- one occurrence ==> safe!
+ other -> False
+
+
+postInlineUnconditionally :: InId -> OutExpr -> Bool
+ -- Examines a (bndr = rhs) binding, AFTER the rhs has been simplified
+ -- It returns True if it's ok to discard the binding and inline the
+ -- RHS at every use site.
+
+ -- NOTE: This isn't our last opportunity to inline.
+ -- We're at the binding site right now, and
+ -- we'll get another opportunity when we get to the ocurrence(s)
+
+postInlineUnconditionally bndr rhs
+ | isExported bndr
+ = False
+ | otherwise
+ = case getInlinePragma bndr of
+ IAmALoopBreaker -> False
+ IMustNotBeINLINEd -> False
+ IAmASpecPragmaId -> False -- Don't discard SpecPrag Ids
+
+ ICanSafelyBeINLINEd InsideLam one_branch -> exprIsTrivial rhs
+ -- Don't inline even WHNFs inside lambdas; this
+ -- isn't the last chance; see NOTE above.
+
+ ICanSafelyBeINLINEd not_in_lam one_branch -> one_branch || exprIsDupable rhs
+
+ other -> exprIsTrivial rhs -- Duplicating is *free*
+ -- NB: Even IWantToBeINLINEd and IMustBeINLINEd are ignored here
+ -- Why? Because we don't even want to inline them into the
+ -- RHS of constructor arguments. See NOTE above
+
+inlineCase bndr scrut
+ = case getInlinePragma bndr of
+ -- Not expecting IAmALoopBreaker etc; this is a case binder!
+
+ ICanSafelyBeINLINEd StrictOcc one_branch
+ -> one_branch || exprIsDupable scrut
+ -- This case is the entire reason we distinguish StrictOcc from LazyOcc
+ -- We want eliminate the "case" only if we aren't going to
+ -- build a thunk instead, and that's what StrictOcc finds
+ -- For example:
+ -- case (f x) of y { DEFAULT -> g y }
+ -- Here we DO NOT WANT:
+ -- g (f x)
+ -- *even* if g is strict. We want to avoid constructing the
+ -- thunk for (f x)! So y gets a LazyOcc.
+
+ other -> exprIsTrivial scrut -- Duplication is free
+ && ( isUnLiftedType (idType bndr)
+ || scrut_is_evald_var -- So dropping the case won't change termination
+ || isStrict (getIdDemandInfo bndr)) -- It's going to get evaluated later, so again
+ -- termination doesn't change
+ where
+ -- Check whether or not scrut is known to be evaluted
+ -- It's not going to be a visible value (else the previous
+ -- blob would apply) so we just check the variable case
+ scrut_is_evald_var = case scrut of
+ Var v -> isEvaldUnfolding (getIdUnfolding v)
+ other -> False
+\end{code}
-Simplify (\binders -> body) trying eta expansion and reduction, given that
-the abstraction will always be applied to at least min_no_of_args.
+okToInline is used at call sites, so it is a bit more generous.
+It's a very important function that embodies lots of heuristics.
\begin{code}
-simplLam env binders body min_no_of_args
- | not (switchIsSet env SimplDoLambdaEtaExpansion) || -- Bale out if eta expansion off
- null potential_extra_binder_tys || -- or ain't a function
- no_of_extra_binders == 0 -- or no extra binders needed
- = cloneIds env binders `thenSmpl` \ binders' ->
- let
- new_env = extendIdEnvWithClones env binders binders'
- in
- simplExpr new_env body [] `thenSmpl` \ body' ->
- returnSmpl (
- (if switchIsSet new_env SimplDoEtaReduction
- then mkValLamTryingEta
- else mkValLam) binders' body'
- )
+okToInline :: Bool -- True <-> essential unfoldings only
+ -> Bool -- Case scrutinee
+ -> Id -- The Id
+ -> FormSummary -- The thing is WHNF or bottom;
+ -> UnfoldingGuidance
+ -> SimplCont
+ -> Bool -- True <=> inline it
+
+-- A non-WHNF can be inlined if it doesn't occur inside a lambda,
+-- and occurs exactly once or
+-- occurs once in each branch of a case and is small
+--
+-- If the thing is in WHNF, there's no danger of duplicating work,
+-- so we can inline if it occurs once, or is small
- | otherwise -- Eta expansion possible
- = tick EtaExpansion `thenSmpl_`
- cloneIds env binders `thenSmpl` \ binders' ->
- let
- new_env = extendIdEnvWithClones env binders binders'
- in
- newIds extra_binder_tys `thenSmpl` \ extra_binders' ->
- simplExpr new_env body (map VarArg extra_binders') `thenSmpl` \ body' ->
- returnSmpl (
- (if switchIsSet new_env SimplDoEtaReduction
- then mkValLamTryingEta
- else mkValLam) (binders' ++ extra_binders') body'
- )
+okToInline essential_unfoldings_only is_case_scrutinee id form guidance cont
+ | essential_unfoldings_only
+ = idMustBeINLINEd id
+ -- If "essential_unfoldings_only" is true we do no inlinings at all,
+ -- EXCEPT for things that absolutely have to be done
+ -- (see comments with idMustBeINLINEd)
+ | otherwise
+ = case getInlinePragma id of
+ IAmDead -> pprTrace "okToInline: dead" (ppr id) False
+
+ IAmASpecPragmaId -> False
+ IMustNotBeINLINEd -> False
+ IAmALoopBreaker -> False
+
+ IMustBeINLINEd -> True
+
+ IWantToBeINLINEd -> True --some_benefit -- Even INLINE pragmas don't *always*
+ -- cause inlining
+
+ ICanSafelyBeINLINEd inside_lam one_branch
+ -> --pprTrace "inline (occurs once): " (ppr id <+> ppr small_enough <+> ppr one_branch <+> ppr whnf <+> ppr some_benefit <+> ppr not_inside_lam) $
+ (small_enough || one_branch) &&
+ ((whnf && some_benefit) || not_inside_lam)
+
+ where
+ not_inside_lam = case inside_lam of {InsideLam -> False; other -> True}
+
+ other -> --pprTrace "inline: " (ppr id <+> ppr small_enough <+> ppr whnf <+> ppr some_benefit) $
+ whnf && small_enough && some_benefit
+ -- We could consider using exprIsCheap here,
+ -- as in postInlineUnconditionally, but unlike the latter we wouldn't
+ -- necessarily eliminate a thunk; and the "form" doesn't tell
+ -- us that.
where
- (potential_extra_binder_tys, res_ty)
- = splitFunTy (simplTy env (coreExprType (unTagBinders body)))
- -- Note: it's possible that simplLam will be applied to something
- -- with a forall type. Eg when being applied to the rhs of
- -- let x = wurble
- -- where wurble has a forall-type, but no big lambdas at the top.
- -- We could be clever an insert new big lambdas, but we don't bother.
-
- extra_binder_tys = take no_of_extra_binders potential_extra_binder_tys
-
- no_of_extra_binders = -- First, use the info about how many args it's
- -- always applied to in its scope
- min_no_of_args
-
- -- Next, try seeing if there's a lambda hidden inside
- -- something cheap
- `max`
- etaExpandCount body
-
- -- Finally, see if it's a state transformer, in which
- -- case we eta-expand on principle! This can waste work,
- -- but usually doesn't
- `max`
- case potential_extra_binder_tys of
- [ty] | ty `eqTy` realWorldStateTy -> 1
- other -> 0
-
+ whnf = whnfOrBottom form
+ small_enough = smallEnoughToInline id arg_evals is_case_scrutinee guidance
+ val_args = get_val_args cont
+ arg_evals = map is_evald val_args
+
+ some_benefit = contIsInteresting cont
+
+ is_evald (Var v) = isEvaldUnfolding (getIdUnfolding v)
+ is_evald (Con con _) = isWHNFCon con
+ is_evald other = False
+
+ get_val_args (ApplyTo _ arg _ cont)
+ | isValArg arg = arg : get_val_args cont
+ | otherwise = get_val_args cont
+ get_val_args other = []
+
+contIsInteresting :: SimplCont -> Bool
+contIsInteresting Stop = False
+contIsInteresting (Select _ _ [(DEFAULT,_,_)] _ _) = False
+contIsInteresting (ApplyTo _ (Type _) _ cont) = contIsInteresting cont
+contIsInteresting _ = True
\end{code}
+Comment about some_benefit above
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+We want to avoid inlining an expression where there can't possibly be
+any gain, such as in an argument position. Hence, if the continuation
+is interesting (eg. a case scrutinee, application etc.) then we
+inline, otherwise we don't.
-%************************************************************************
-%* *
-\subsection[Simplify-coerce]{Coerce expressions}
-%* *
-%************************************************************************
+Previously some_benefit used to return True only if the variable was
+applied to some value arguments. This didn't work:
-\begin{code}
--- (coerce (case s of p -> r)) args ==> case s of p -> (coerce r) args
-simplCoerce env coercion ty expr@(Case scrut alts) args
- = simplCase env scrut alts (\env rhs -> simplCoerce env coercion ty rhs args)
- (computeResultType env expr args)
-
--- (coerce (let defns in b)) args ==> let defns' in (coerce b) args
-simplCoerce env coercion ty (Let bind body) args
- = simplBind env bind (\env -> simplCoerce env coercion ty body args)
- (computeResultType env body args)
-
--- Default case
-simplCoerce env coercion ty expr args
- = simplExpr env expr [] `thenSmpl` \ expr' ->
- returnSmpl (mkGenApp (mkCoerce coercion (simplTy env ty) expr') args)
- where
+ let x = _coerce_ (T Int) Int (I# 3) in
+ case _coerce_ Int (T Int) x of
+ I# y -> ....
- -- Try cancellation; we do this "on the way up" because
- -- I think that's where it'll bite best
- mkCoerce (CoerceIn con1) ty1 (Coerce (CoerceOut con2) ty2 body) | con1 == con2 = body
- mkCoerce (CoerceOut con1) ty1 (Coerce (CoerceIn con2) ty2 body) | con1 == con2 = body
- mkCoerce coercion ty body = Coerce coercion ty body
-\end{code}
+we want to inline x, but can't see that it's a constructor in a case
+scrutinee position, and some_benefit is False.
+
+Another example:
+dMonadST = _/\_ t -> :Monad (g1 _@_ t, g2 _@_ t, g3 _@_ t)
+
+.... case dMonadST _@_ x0 of (a,b,c) -> ....
+
+we'd really like to inline dMonadST here, but we *don't* want to
+inline if the case expression is just
+
+ case x of y { DEFAULT -> ... }
+
+since we can just eliminate this case instead (x is in WHNF). Similar
+applies when x is bound to a lambda expression. Hence
+contIsInteresting looks for case expressions with just a single
+default case.
%************************************************************************
%* *
-\subsection[Simplify-let]{Let-expressions}
+\subsection{The main rebuilder}
%* *
%************************************************************************
\begin{code}
-simplBind :: SimplEnv
- -> InBinding
- -> (SimplEnv -> SmplM OutExpr)
- -> OutType
- -> SmplM OutExpr
-\end{code}
+-------------------------------------------------------------------
+rebuild :: OutExpr -> SimplCont -> SimplM OutExpr
-When floating cases out of lets, remember this:
+rebuild expr cont
+ = tick LeavesExamined `thenSmpl_`
+ getSwitchChecker `thenSmpl` \ chkr ->
+ do_rebuild chkr expr (mkFormSummary expr) cont
- let x* = case e of alts
- in <small expr>
+---------------------------------------------------------
+-- Stop continuation
-where x* is sure to be demanded or e is a cheap operation that cannot
-fail, e.g. unboxed addition. Here we should be prepared to duplicate
-<small expr>. A good example:
+do_rebuild sw_chkr expr form Stop = returnSmpl expr
- let x* = case y of
- p1 -> build e1
- p2 -> build e2
- in
- foldr c n x*
-==>
- case y of
- p1 -> foldr c n (build e1)
- p2 -> foldr c n (build e2)
-NEW: We use the same machinery that we use for case-of-case to
-*always* do case floating from let, that is we let bind and abstract
-the original let body, and let the occurrence analyser later decide
-whether the new let should be inlined or not. The example above
-becomes:
+---------------------------------------------------------
+-- Coerce continuation
-==>
- let join_body x' = foldr c n x'
- in case y of
- p1 -> let x* = build e1
- in join_body x*
- p2 -> let x* = build e2
- in join_body x*
+do_rebuild sw_chkr expr form (CoerceIt _ to_ty se cont)
+ = setSubstEnv se $
+ simplType to_ty `thenSmpl` \ to_ty' ->
+ do_rebuild sw_chkr (mk_coerce to_ty' expr) form cont
+ where
+ mk_coerce to_ty' (Note (Coerce _ from_ty) expr) = Note (Coerce to_ty' from_ty) expr
+ mk_coerce to_ty' expr = Note (Coerce to_ty' (coreExprType expr)) expr
-note that join_body is a let-no-escape.
-In this particular example join_body will later be inlined,
-achieving the same effect.
-ToDo: check this is OK with andy
+---------------------------------------------------------
+-- Dealing with
+-- * case (error "hello") of { ... }
+-- ToDo: deal with
+-- * (error "Hello") arg
-\begin{code}
--- Dead code is now discarded by the occurrence analyser,
+do_rebuild sw_chkr expr BottomForm cont@(Select _ _ _ _ _)
+ = tick CaseOfError `thenSmpl_`
+ getInScope `thenSmpl` \ in_scope ->
+ let
+ (cont', result_ty) = find_result_ty in_scope cont
+ in
+ do_rebuild sw_chkr (mkNote (Coerce result_ty expr_ty) expr) BottomForm cont'
+ where
+ expr_ty = coreExprType expr
+ find_result_ty in_scope (ApplyTo _ _ _ cont)
+ = (cont, funResultTy expr_ty)
+ find_result_ty in_scope (Select _ _ ((_,_,rhs1):_) (ty_subst,_) cont)
+ = (cont, fullSubstTy ty_subst in_scope (coreExprType rhs1))
+
+
+---------------------------------------------------------
+-- Ordinary application
+
+do_rebuild sw_chkr expr form cont@(ApplyTo _ _ _ _)
+ = go expr cont
+ where -- This loop just saves repeated calculation of mkFormSummary
+ go e (ApplyTo _ arg se cont) = setSubstEnv se (simplArg arg) `thenSmpl` \ arg' ->
+ go (App e arg') cont
+ go e cont = do_rebuild sw_chkr e (mkFormSummary e) cont
+
+
+---------------------------------------------------------
+-- Case of known constructor or literal
+
+do_rebuild sw_chkr expr@(Con con args) form cont@(Select _ _ _ _ _)
+ | conOkForAlt con -- Knocks out PrimOps and NoRepLits
+ = knownCon expr con args cont
+
+---------------------------------------------------------
+-- Case of other value (e.g. a partial application or lambda)
+-- Turn it back into a let
+
+do_rebuild sw_chkr expr ValueForm (Select _ bndr ((DEFAULT, bs, rhs):alts) se cont)
+ = ASSERT( null bs && null alts )
+ tick Case2Let `thenSmpl_`
+ setSubstEnv se (
+ completeBindNonRecE bndr expr $
+ simplExpr rhs cont
+ )
-simplBind env (NonRec binder@(id,occ_info) rhs) body_c body_ty
- | inlineUnconditionally ok_to_dup occ_info
- = body_c (extendIdEnvWithInlining env env binder rhs)
--- Try let-to-case
--- It's important to try let-to-case before floating. Consider
---
--- let a*::Int = case v of {p1->e1; p2->e2}
--- in b
---
--- (The * means that a is sure to be demanded.)
--- If we do case-floating first we get this:
---
--- let k = \a* -> b
--- in case v of
--- p1-> let a*=e1 in k a
--- p2-> let a*=e2 in k a
---
--- Now watch what happens if we do let-to-case first:
---
--- case (case v of {p1->e1; p2->e2}) of
--- Int a# -> let a*=I# a# in b
--- ===>
--- let k = \a# -> let a*=I# a# in b
--- in case v of
--- p1 -> case e1 of I# a# -> k a#
--- p1 -> case e1 of I# a# -> k a#
---
--- The latter is clearly better. (Remember the reboxing let-decl
--- for a is likely to go away, because after all b is strict in a.)
-
- | will_be_demanded &&
- try_let_to_case &&
- type_ok_for_let_to_case rhs_ty &&
- not (manifestlyWHNF rhs)
- -- note: no "manifestlyBottom rhs" in there... (comment below)
- = tick Let2Case `thenSmpl_`
- mkIdentityAlts rhs_ty `thenSmpl` \ id_alts ->
- simplCase env rhs id_alts (\env rhs -> done_float env rhs body_c) body_ty
- {-
- We do not do let to case for WHNFs, e.g.
-
- let x = a:b in ...
- =/=>
- case a:b of x in ...
-
- as this is less efficient.
- but we don't mind doing let-to-case for "bottom", as that
- will
- allow us to remove more dead code, if anything:
- let x = error in ...
- ===>
- case error of x -> ...
- ===>
- error
-
- Notice that let to case occurs only if x is used strictly in
- its body (obviously).
- -}
-
- | (will_be_demanded && not no_float) ||
- always_float_let_from_let ||
- floatExposesHNF float_lets float_primops ok_to_dup rhs
- = try_float env rhs body_c
+---------------------------------------------------------
+-- Case of something else; eliminating the case altogether
+-- See the extensive notes on case-elimination below
- | otherwise
- = done_float env rhs body_c
+do_rebuild sw_chkr scrut form (Select _ bndr alts se cont)
+ | switchIsOn sw_chkr SimplDoCaseElim
+ && all (cheapEqExpr rhs1) other_rhss
+ && inlineCase bndr scrut
+ && all binders_unused alts
+ = -- Get rid of the case altogether
+ -- Remember to bind the binder though!
+ tick CaseElim `thenSmpl_`
+ setSubstEnv se (
+ extendIdSubst bndr (Done scrut) $
+ simplExpr rhs1 cont
+ )
where
- will_be_demanded = willBeDemanded (getIdDemandInfo id)
- rhs_ty = idType id
-
- float_lets = switchIsSet env SimplFloatLetsExposingWHNF
- float_primops = switchIsSet env SimplOkToFloatPrimOps
- ok_to_dup = switchIsSet env SimplOkToDupCode
- always_float_let_from_let = switchIsSet env SimplAlwaysFloatLetsFromLets
- try_let_to_case = switchIsSet env SimplLetToCase
- no_float = switchIsSet env SimplNoLetFromStrictLet
-
- -------------------------------------------
- done_float env rhs body_c
- = simplRhsExpr env binder rhs `thenSmpl` \ rhs' ->
- completeLet env binder rhs' body_c body_ty
-
- ---------------------------------------
- try_float env (Let bind rhs) body_c
- = tick LetFloatFromLet `thenSmpl_`
- simplBind env (fix_up_demandedness will_be_demanded bind)
- (\env -> try_float env rhs body_c) body_ty
-
- try_float env (Case scrut alts) body_c
- | will_be_demanded || (float_primops && is_cheap_prim_app scrut)
- = tick CaseFloatFromLet `thenSmpl_`
-
- -- First, bind large let-body if necessary
- if no_need_to_bind_large_body then
- simplCase env scrut alts (\env rhs -> try_float env rhs body_c) body_ty
- else
- bindLargeRhs env [binder] body_ty body_c `thenSmpl` \ (extra_binding, new_body) ->
- let
- body_c' = \env -> simplExpr env new_body []
- in
- simplCase env scrut alts
- (\env rhs -> try_float env rhs body_c')
- body_ty `thenSmpl` \ case_expr ->
-
- returnSmpl (Let extra_binding case_expr)
- where
- no_need_to_bind_large_body
- = ok_to_dup || isSingleton (nonErrorRHSs alts)
-
- try_float env other_rhs body_c = done_float env other_rhs body_c
-\end{code}
+ (rhs1:other_rhss) = [rhs | (_,_,rhs) <- alts]
-Letrec expressions
-~~~~~~~~~~~~~~~~~~
+ binders_unused (_, bndrs, _) = all isDeadBinder bndrs
-Simplify each RHS, float any let(recs) from the RHSs (if let-floating is
-on and it'll expose a HNF), and bang the whole resulting mess together
-into a huge letrec.
-1. Any "macros" should be expanded. The main application of this
-macro-expansion is:
- letrec
- f = ....g...
- g = ....f...
- in
- ....f...
+---------------------------------------------------------
+-- Case of something else
-Here we would like the single call to g to be inlined.
+do_rebuild sw_chkr scrut form (Select _ case_bndr alts se cont)
+ = -- Prepare the continuation and case alternatives
+ prepareCaseAlts (splitTyConApp_maybe (idType case_bndr))
+ scrut_cons alts `thenSmpl` \ better_alts ->
+ prepareCaseCont better_alts cont $ \ cont' ->
+
+ -- Set the new subst-env in place (before dealing with the case binder)
+ setSubstEnv se $
+
+ -- Deal with the case binder
+ simplBinder case_bndr $ \ case_bndr' ->
-We can spot this easily, because g will be tagged as having just one
-occurrence. The "inlineUnconditionally" predicate is just what we want.
-
-A worry: could this lead to non-termination? For example:
-
- letrec
- f = ...g...
- g = ...f...
- h = ...h...
- in
- ..h..
+ -- Deal with variable scrutinee
+ substForVarScrut scrut case_bndr' $ \ zap_occ_info ->
+ let
+ case_bndr'' = zap_occ_info case_bndr'
+ in
-Here, f and g call each other (just once) and neither is used elsewhere.
-But it's OK:
+ -- Deal with the case alternaatives
+ simplAlts zap_occ_info scrut_cons case_bndr'' better_alts cont' `thenSmpl` \ alts' ->
-* the occurrence analyser will drop any (sub)-group that isn't used at
- all.
+ getSwitchChecker `thenSmpl` \ sw_chkr ->
+ mkCase sw_chkr scrut case_bndr'' alts'
+ where
+ -- scrut_cons tells what constructors the scrutinee can't possibly match
+ scrut_cons = case scrut of
+ Var v -> case getIdUnfolding v of
+ OtherCon cons -> cons
+ other -> []
+ other -> []
+\end{code}
-* If the group is used outside itself (ie in the "in" part), then there
- can't be a cyle.
+Blob of helper functions for the "case-of-something-else" situation.
-** IMPORTANT: check that NewOccAnal has the property that a group of
- bindings like the above has f&g dropped.! ***
+\begin{code}
+knownCon expr con args (Select _ bndr alts se cont)
+ = tick KnownBranch `thenSmpl_`
+ setSubstEnv se (
+ case findAlt con alts of
+ (DEFAULT, bs, rhs) -> ASSERT( null bs )
+ completeBindNonRecE bndr expr $
+ simplExpr rhs cont
+
+ (Literal lit, bs, rhs) -> ASSERT( null bs )
+ extendIdSubst bndr (Done expr) $
+ -- Unconditionally substitute, because expr must
+ -- be a variable or a literal. It can't be a
+ -- NoRep literal because they don't occur in
+ -- case patterns.
+ simplExpr rhs cont
+
+ (DataCon dc, bs, rhs) -> completeBindNonRecE bndr expr $
+ extend bs real_args $
+ simplExpr rhs cont
+ where
+ real_args = drop (dataConNumInstArgs dc) args
+ )
+ where
+ extend [] [] thing_inside = thing_inside
+ extend (b:bs) (arg:args) thing_inside = extendIdSubst b (Done arg) $
+ extend bs args thing_inside
+\end{code}
+\begin{code}
+prepareCaseCont [alt] cont thing_inside = thing_inside cont
+prepareCaseCont alts cont thing_inside = mkDupableCont cont thing_inside
+\end{code}
-2. We'd also like to pull out any top-level let(rec)s from the
-rhs of the defns:
+substForVarScrut checks whether the scrutinee is a variable, v.
+If so, try to eliminate uses of v in the RHSs in favour of case_bndr;
+that way, there's a chance that v will now only be used once, and hence inlined.
- letrec
- f = let h = ... in \x -> ....h...f...h...
- in
- ...f...
-====>
- letrec
- h = ...
- f = \x -> ....h...f...h...
- in
- ...f...
+If we do this, then we have to nuke any occurrence info (eg IAmDead)
+in the case binder, because the case-binder now effectively occurs
+whenever v does. AND we have to do the same for the pattern-bound
+variables! Example:
-But floating cases is less easy? (Don't for now; ToDo?)
+ (case x of { (a,b) -> a }) (case x of { (p,q) -> q })
+Here, b and p are dead. But when we move the argment inside the first
+case RHS, and eliminate the second case, we get
-3. We'd like to arrange that the RHSs "know" about members of the
-group that are bound to constructors. For example:
+ case x or { (a,b) -> a b
- let rec
- d.Eq = (==,/=)
- f a b c d = case d.Eq of (h,_) -> let x = (a,b); y = (c,d) in not (h x y)
- /= a b = unpack tuple a, unpack tuple b, call f
- in d.Eq
+Urk! b is alive! Reason: the scrutinee was a variable, and case elimination
+happened. Hence the zap_occ_info function returned by substForVarScrut
-here, by knowing about d.Eq in f's rhs, one could get rid of
-the case (and break out the recursion completely).
-[This occurred with more aggressive inlining threshold (4),
-nofib/spectral/knights]
+\begin{code}
+substForVarScrut (Var v) case_bndr' thing_inside
+ | isLocallyDefined v -- No point for imported things
+ = modifyInScope (v `setIdUnfolding` mkUnfolding (Var case_bndr')
+ `setInlinePragma` IMustBeINLINEd) $
+ -- We could extend the substitution instead, but it would be
+ -- a hack because then the substitution wouldn't be idempotent
+ -- any more.
+ thing_inside (\ bndr -> bndr `setInlinePragma` NoInlinePragInfo)
+
+substForVarScrut other_scrut case_bndr' thing_inside
+ = thing_inside (\ bndr -> bndr) -- NoOp on bndr
+\end{code}
-How to do it?
- 1: we simplify constructor rhss first.
- 2: we record the "known constructors" in the environment
- 3: we simplify the other rhss, with the knowledge about the constructors
+prepareCaseAlts does two things:
+1. Remove impossible alternatives
+2. If the DEFAULT alternative can match only one possible constructor,
+ then make that constructor explicit.
+ e.g.
+ case e of x { DEFAULT -> rhs }
+ ===>
+ case e of x { (a,b) -> rhs }
+ where the type is a single constructor type. This gives better code
+ when rhs also scrutinises x or e.
\begin{code}
-simplBind env (Rec pairs) body_c body_ty
- = -- Do floating, if necessary
- (if float_lets || always_float_let_from_let
- then
- mapSmpl float pairs `thenSmpl` \ floated_pairs_s ->
- returnSmpl (concat floated_pairs_s)
- else
- returnSmpl pairs
- ) `thenSmpl` \ floated_pairs ->
- let
- binders = map fst floated_pairs
- in
- cloneIds env binders `thenSmpl` \ ids' ->
- let
- env_w_clones = extendIdEnvWithClones env binders ids'
- triples = zipEqual "simplBind" ids' floated_pairs
- in
+prepareCaseAlts (Just (tycon, inst_tys)) scrut_cons alts
+ | isDataTyCon tycon
+ = case (findDefault filtered_alts, missing_cons) of
+
+ ((alts_no_deflt, Just rhs), [data_con]) -- Just one missing constructor!
+ -> tick FillInCaseDefault `thenSmpl_`
+ let
+ (_,_,ex_tyvars,_,_,_) = dataConSig data_con
+ in
+ getUniquesSmpl (length ex_tyvars) `thenSmpl` \ tv_uniqs ->
+ let
+ ex_tyvars' = zipWithEqual "simpl_alt" mk tv_uniqs ex_tyvars
+ mk uniq tv = mkSysTyVar uniq (tyVarKind tv)
+ in
+ newIds (dataConArgTys
+ data_con
+ (inst_tys ++ mkTyVarTys ex_tyvars')) $ \ bndrs ->
+ returnSmpl ((DataCon data_con, ex_tyvars' ++ bndrs, rhs) : alts_no_deflt)
+
+ other -> returnSmpl filtered_alts
+ where
+ -- Filter out alternatives that can't possibly match
+ filtered_alts = case scrut_cons of
+ [] -> alts
+ other -> [alt | alt@(con,_,_) <- alts, not (con `elem` scrut_cons)]
- simplRecursiveGroup env_w_clones triples `thenSmpl` \ (binding, new_env) ->
+ missing_cons = [data_con | data_con <- tyConDataCons tycon,
+ not (data_con `elem` handled_data_cons)]
+ handled_data_cons = [data_con | DataCon data_con <- scrut_cons] ++
+ [data_con | (DataCon data_con, _, _) <- filtered_alts]
- body_c new_env `thenSmpl` \ body' ->
+-- The default case
+prepareCaseAlts _ scrut_cons alts
+ = returnSmpl alts -- Functions
- returnSmpl (Let binding body')
+----------------------
+simplAlts zap_occ_info scrut_cons case_bndr'' alts cont'
+ = mapSmpl simpl_alt alts
where
- ------------ Floating stuff -------------------
-
- float_lets = switchIsSet env SimplFloatLetsExposingWHNF
- always_float_let_from_let = switchIsSet env SimplAlwaysFloatLetsFromLets
-
- float (binder,rhs)
- = let
- pairs_s = float_pair (binder,rhs)
- in
- case pairs_s of
- [_] -> returnSmpl pairs_s
- more_than_one
- -> tickN LetFloatFromLet (length pairs_s - 1) `thenSmpl_`
- -- It's important to increment the tick counts if we
- -- do any floating. A situation where this turns out
- -- to be important is this:
- -- Float in produces:
- -- letrec x = let y = Ey in Ex
- -- in B
- -- Now floating gives this:
- -- letrec x = Ex
- -- y = Ey
- -- in B
- --- We now want to iterate once more in case Ey doesn't
- -- mention x, in which case the y binding can be pulled
- -- out as an enclosing let(rec), which in turn gives
- -- the strictness analyser more chance.
- returnSmpl pairs_s
-
- float_pairs pairs = concat (map float_pair pairs)
-
- float_pair (binder, rhs)
- | always_float_let_from_let ||
- floatExposesHNF True False False rhs
- = (binder,rhs') : pairs'
-
- | otherwise
- = [(binder,rhs)]
- where
- (pairs', rhs') = do_float rhs
-
- -- Float just pulls out any top-level let(rec) bindings
- do_float :: InExpr -> ([(InBinder,InExpr)], InExpr)
- do_float (Let (Rec pairs) body) = (float_pairs pairs ++ pairs', body')
- where
- (pairs', body') = do_float body
- do_float (Let (NonRec id rhs) body) = (float_pair (id,rhs) ++ pairs', body')
- where
- (pairs', body') = do_float body
- do_float other = ([], other)
-
-simplRecursiveGroup env triples
- = -- Toss out all the dead pairs? No, there shouldn't be any!
- -- Dead code is discarded by the occurrence analyser
- let
- -- Separate the live triples into "inline"able and
- -- "ordinary" We're paranoid about duplication!
- (inline_triples, ordinary_triples)
- = partition is_inline_triple triples
+ inst_tys' = case splitTyConApp_maybe (idType case_bndr'') of
+ Just (tycon, inst_tys) -> inst_tys
+
+ -- handled_cons is all the constructors that are dealt
+ -- with, either by being impossible, or by there being an alternative
+ handled_cons = scrut_cons ++ [con | (con,_,_) <- alts, con /= DEFAULT]
+
+ simpl_alt (DEFAULT, _, rhs)
+ = modifyInScope (case_bndr'' `setIdUnfolding` OtherCon handled_cons) $
+ simplExpr rhs cont' `thenSmpl` \ rhs' ->
+ returnSmpl (DEFAULT, [], rhs')
+
+ simpl_alt (con, vs, rhs)
+ = -- Deal with the case-bound variables
+ -- Mark the ones that are in ! positions in the data constructor
+ -- as certainly-evaluated
+ simplBinders (add_evals con vs) $ \ vs' ->
+
+ -- Bind the case-binder to (Con args)
+ -- In the default case we record the constructors it *can't* be.
+ -- We take advantage of any OtherCon info in the case scrutinee
+ let
+ con_app = Con con (map Type inst_tys' ++ map varToCoreExpr vs')
+ in
+ modifyInScope (case_bndr'' `setIdUnfolding` mkUnfolding con_app) $
+ simplExpr rhs cont' `thenSmpl` \ rhs' ->
+ returnSmpl (con, vs', rhs')
+
+
+ -- add_evals records the evaluated-ness of the bound variables of
+ -- a case pattern. This is *important*. Consider
+ -- data T = T !Int !Int
+ --
+ -- case x of { T a b -> T (a+1) b }
+ --
+ -- We really must record that b is already evaluated so that we don't
+ -- go and re-evaluated it when constructing the result.
- is_inline_triple (_, ((_,occ_info),_))
- = inlineUnconditionally False {-not ok_to_dup-} occ_info
+ add_evals (DataCon dc) vs = stretchZipEqual add_eval vs (dataConStrictMarks dc)
+ add_evals other_con vs = vs
- -- Now add in the inline_pairs info (using "env_w_clones"),
- -- so that we will save away suitably-clone-laden envs
- -- inside the InlineIts...).
+ add_eval v m | isTyVar v = Nothing
+ | otherwise = case m of
+ MarkedStrict -> Just (zap_occ_info v `setIdUnfolding` OtherCon [])
+ NotMarkedStrict -> Just (zap_occ_info v)
+\end{code}
- -- NOTE ALSO that we tie a knot here, because the
- -- saved-away envs must also include these very inlinings
- -- (they aren't stored anywhere else, and a late one might
- -- be used in an early one).
- env_w_inlinings = foldl add_inline env inline_triples
+Case elimination [see the code above]
+~~~~~~~~~~~~~~~~
+Start with a simple situation:
+
+ case x# of ===> e[x#/y#]
+ y# -> e
+
+(when x#, y# are of primitive type, of course). We can't (in general)
+do this for algebraic cases, because we might turn bottom into
+non-bottom!
+
+Actually, we generalise this idea to look for a case where we're
+scrutinising a variable, and we know that only the default case can
+match. For example:
+\begin{verbatim}
+ case x of
+ 0# -> ...
+ other -> ...(case x of
+ 0# -> ...
+ other -> ...) ...
+\end{code}
+Here the inner case can be eliminated. This really only shows up in
+eliminating error-checking code.
- add_inline env (id', (binder,rhs))
- = extendIdEnvWithInlining env env_w_inlinings binder rhs
+We also make sure that we deal with this very common case:
- -- Separate the remaining bindings into the ones which
- -- need to be dealt with first (the "early" ones)
- -- and the others (the "late" ones)
- (early_triples, late_triples)
- = partition is_early_triple ordinary_triples
+ case e of
+ x -> ...x...
- is_early_triple (_, (_, Con _ _)) = True
- is_early_triple (i, _ ) = idWantsToBeINLINEd i
- in
- -- Process the early bindings first
- mapSmpl (do_one_binding env_w_inlinings) early_triples `thenSmpl` \ early_triples' ->
+Here we are using the case as a strict let; if x is used only once
+then we want to inline it. We have to be careful that this doesn't
+make the program terminate when it would have diverged before, so we
+check that
+ - x is used strictly, or
+ - e is already evaluated (it may so if e is a variable)
- -- Now further extend the environment to record our knowledge
- -- about the form of the binders bound in the constructor bindings
- let
- env_w_early_info = foldr add_early_info env_w_inlinings early_triples'
- add_early_info (binder, (id', rhs')) env = extendUnfoldEnvGivenRhs env binder id' rhs'
- in
- -- Now process the non-constructor bindings
- mapSmpl (do_one_binding env_w_early_info) late_triples `thenSmpl` \ late_triples' ->
+Lastly, we generalise the transformation to handle this:
- -- Phew! We're done
- let
- binding = Rec (map snd early_triples' ++ map snd late_triples')
- in
- returnSmpl (binding, env_w_early_info)
- where
+ case e of ===> r
+ True -> r
+ False -> r
- do_one_binding env (id', (binder,rhs))
- = simplRhsExpr env binder rhs `thenSmpl` \ rhs' ->
- returnSmpl (binder, (id', rhs'))
-\end{code}
+We only do this for very cheaply compared r's (constructors, literals
+and variables). If pedantic bottoms is on, we only do it when the
+scrutinee is a PrimOp which can't fail.
+We do it *here*, looking at un-simplified alternatives, because we
+have to check that r doesn't mention the variables bound by the
+pattern in each alternative, so the binder-info is rather useful.
-@completeLet@ looks at the simplified post-floating RHS of the
-let-expression, and decides what to do. There's one interesting
-aspect to this, namely constructor reuse. Consider
-@
- f = \x -> case x of
- (y:ys) -> y:ys
- [] -> ...
-@
-Is it a good idea to replace the rhs @y:ys@ with @x@? This depends a
-bit on the compiler technology, but in general I believe not. For
-example, here's some code from a real program:
-@
-const.Int.max.wrk{-s2516-} =
- \ upk.s3297# upk.s3298# ->
- let {
- a.s3299 :: Int
- _N_ {-# U(P) #-}
- a.s3299 = I#! upk.s3297#
- } in
- case (const.Int._tagCmp.wrk{-s2513-} upk.s3297# upk.s3298#) of {
- _LT -> I#! upk.s3298#
- _EQ -> a.s3299
- _GT -> a.s3299
- }
-@
-The a.s3299 really isn't doing much good. We'd be better off inlining
-it. (Actually, let-no-escapery means it isn't as bad as it looks.)
-
-So the current strategy is to inline all known-form constructors, and
-only do the reverse (turn a constructor application back into a
-variable) when we find a let-expression:
-@
- let x = C a1 .. an
- in
- ... (let y = C a1 .. an in ...) ...
-@
-where it is always good to ditch the binding for y, and replace y by
-x. That's just what completeLetBinding does.
+So the case-elimination algorithm is:
-\begin{code}
-completeLet
- :: SimplEnv
- -> InBinder
- -> OutExpr -- The simplified RHS
- -> (SimplEnv -> SmplM OutExpr) -- Body handler
- -> OutType -- Type of body
- -> SmplM OutExpr
-
-completeLet env binder new_rhs body_c body_ty
- -- See if RHS is an atom, or a reusable constructor
- | maybeToBool maybe_atomic_rhs
- = let
- new_env = extendIdEnvWithAtom env binder rhs_atom
- in
- tick atom_tick_type `thenSmpl_`
- body_c new_env
- where
- maybe_atomic_rhs :: Maybe (OutArg, TickType)
- maybe_atomic_rhs = exprToAtom env new_rhs
- -- If the RHS is atomic, we return Just (atom, tick type)
- -- otherwise Nothing
- Just (rhs_atom, atom_tick_type) = maybe_atomic_rhs
-
-completeLet env binder@(id,_) new_rhs body_c body_ty
- -- Maybe the rhs is an application of error, and sure to be demanded
- | will_be_demanded &&
- maybeToBool maybe_error_app
- = tick CaseOfError `thenSmpl_`
- returnSmpl retyped_error_app
- where
- will_be_demanded = willBeDemanded (getIdDemandInfo id)
- maybe_error_app = maybeErrorApp new_rhs (Just body_ty)
- Just retyped_error_app = maybe_error_app
-
-{-
-completeLet env binder (Coerce coercion ty rhs) body_c body_ty
- -- Rhs is a coercion
- | maybeToBool maybe_atomic_coerce_rhs
- = tick tick_type `thenSmpl_`
- complete_coerce env rhs_atom rhs
- where
- maybe_atomic_coerce_rhs = exprToAtom env rhs
- Just (rhs_atom, tick_type) = maybe_atomic_coerce_rhs
-
- returnSmpl (CoerceForm coercion rhs_atom, env)
- Nothing
- newId (coreExprType rhs) `thenSmpl` \ inner_id ->
-
- complete_coerce env atom rhs
- = cloneId env binder `thenSmpl` \ id' ->
- let
- env1 = extendIdEnvWithClone env binder id'
- new_env = extendUnfoldEnvGivenFormDetails env1 id' (CoerceForm coercion rhs_atom)
- in
- body_c new_env `thenSmpl` \ body' ->
- returnSmpl (Let (NonRec id' (Coerce coercion ty rhs) body')
--}
-
-completeLet env binder new_rhs body_c body_ty
- -- The general case
- = cloneId env binder `thenSmpl` \ id' ->
- let
- env1 = extendIdEnvWithClone env binder id'
- new_env = extendUnfoldEnvGivenRhs env1 binder id' new_rhs
- in
- body_c new_env `thenSmpl` \ body' ->
- returnSmpl (Let (NonRec id' new_rhs) body')
-\end{code}
+ 1. Eliminate alternatives which can't match
-%************************************************************************
-%* *
-\subsection[Simplify-atoms]{Simplifying atoms}
-%* *
-%************************************************************************
+ 2. Check whether all the remaining alternatives
+ (a) do not mention in their rhs any of the variables bound in their pattern
+ and (b) have equal rhss
-\begin{code}
-simplArg :: SimplEnv -> InArg -> OutArg
+ 3. Check we can safely ditch the case:
+ * PedanticBottoms is off,
+ or * the scrutinee is an already-evaluated variable
+ or * the scrutinee is a primop which is ok for speculation
+ -- ie we want to preserve divide-by-zero errors, and
+ -- calls to error itself!
-simplArg env (LitArg lit) = LitArg lit
-simplArg env (TyArg ty) = TyArg (simplTy env ty)
+ or * [Prim cases] the scrutinee is a primitive variable
-simplArg env (VarArg id)
- | isLocallyDefined id
- = case lookupId env id of
- Just (ItsAnAtom atom) -> atom
- Just (InlineIt _ _ _) -> pprPanic "simplArg InLineIt:" (ppAbove (ppr PprDebug id) (pprSimplEnv env))
- Nothing -> VarArg id -- Must be an uncloned thing
+ or * [Alg cases] the scrutinee is a variable and
+ either * the rhs is the same variable
+ (eg case x of C a b -> x ===> x)
+ or * there is only one alternative, the default alternative,
+ and the binder is used strictly in its scope.
+ [NB this is helped by the "use default binder where
+ possible" transformation; see below.]
- | otherwise
- = -- Not locally defined, so no change
- VarArg id
-\end{code}
+If so, then we can replace the case with one of the rhss.
-\begin{code}
-exprToAtom env (Var var)
- = Just (VarArg var, AtomicRhs)
-
-exprToAtom env (Lit lit)
- | not (isNoRepLit lit)
- = Just (LitArg lit, AtomicRhs)
-
-exprToAtom env (Con con con_args)
- | switchIsSet env SimplReuseCon
- -- Look out for
- -- let v = C args
- -- in
- --- ...(let w = C same-args in ...)...
- -- Then use v instead of w. This may save
- -- re-constructing an existing constructor.
- = case (lookForConstructor env con con_args) of
- Nothing -> Nothing
- Just var -> Just (VarArg var, ConReused)
-
-exprToAtom env other
- = Nothing
-\end{code}
%************************************************************************
%* *
-\subsection[Simplify-quickies]{Some local help functions}
+\subsection{Duplicating continuations}
%* *
%************************************************************************
-
\begin{code}
--- fix_up_demandedness switches off the willBeDemanded Info field
--- for bindings floated out of a non-demanded let
-fix_up_demandedness True {- Will be demanded -} bind
- = bind -- Simple; no change to demand info needed
-fix_up_demandedness False {- May not be demanded -} (NonRec binder rhs)
- = NonRec (un_demandify binder) rhs
-fix_up_demandedness False {- May not be demanded -} (Rec pairs)
- = Rec [(un_demandify binder, rhs) | (binder,rhs) <- pairs]
-
-un_demandify (id, occ_info) = (id `addIdDemandInfo` noInfo, occ_info)
-
-is_cheap_prim_app (Prim op _) = primOpOkForSpeculation op
-is_cheap_prim_app other = False
-
-computeResultType :: SimplEnv -> InExpr -> [OutArg] -> OutType
-computeResultType env expr args
- = go expr_ty' args
- where
- expr_ty = coreExprType (unTagBinders expr)
- expr_ty' = simplTy env expr_ty
-
- go ty [] = ty
- go ty (TyArg ty_arg : args) = go (mkAppTy ty ty_arg) args
- go ty (a:args) | isValArg a = case (getFunTy_maybe ty) of
- Just (_, res_ty) -> go res_ty args
- Nothing -> panic "computeResultType"
-\end{code}
+mkDupableCont :: SimplCont
+ -> (SimplCont -> SimplM CoreExpr)
+ -> SimplM CoreExpr
+mkDupableCont cont thing_inside
+ | contIsDupable cont
+ = thing_inside cont
+
+mkDupableCont (CoerceIt _ ty se cont) thing_inside
+ = mkDupableCont cont $ \ cont' ->
+ thing_inside (CoerceIt OkToDup ty se cont')
+
+mkDupableCont (ApplyTo _ arg se cont) thing_inside
+ = mkDupableCont cont $ \ cont' ->
+ setSubstEnv se (simplExpr arg Stop) `thenSmpl` \ arg' ->
+ if exprIsDupable arg' then
+ thing_inside (ApplyTo OkToDup arg' emptySubstEnv cont')
+ else
+ newId (coreExprType arg') $ \ bndr ->
+ thing_inside (ApplyTo OkToDup (Var bndr) emptySubstEnv cont') `thenSmpl` \ res ->
+ returnSmpl (bindNonRec bndr arg' res)
+
+mkDupableCont (Select _ case_bndr alts se cont) thing_inside
+ = tick CaseOfCase `thenSmpl_` (
+ mkDupableCont cont $ \ cont' ->
+
+ setSubstEnv se (
+ simplBinder case_bndr $ \ case_bndr' ->
+ mapAndUnzipSmpl (mkDupableAlt case_bndr' cont') alts `thenSmpl` \ (alt_binds_s, alts') ->
+ returnSmpl (concat alt_binds_s, case_bndr', alts')
+ ) `thenSmpl` \ (alt_binds, case_bndr', alts') ->
+
+ extendInScopes [b | NonRec b _ <- alt_binds] $
+ thing_inside (Select OkToDup case_bndr' alts' emptySubstEnv Stop) `thenSmpl` \ res ->
+ returnSmpl (mkLets alt_binds res)
+ )
+mkDupableAlt :: OutId -> SimplCont -> InAlt -> SimplM ([CoreBind], CoreAlt)
+mkDupableAlt case_bndr' cont alt@(con, bndrs, rhs)
+ = simplBinders bndrs $ \ bndrs' ->
+ simplExpr rhs cont `thenSmpl` \ rhs' ->
+ if exprIsDupable rhs' then
+ -- It's small, so don't bother to let-bind it
+ returnSmpl ([], (con, bndrs', rhs'))
+ else
+ -- It's big, so let-bind it
+ let
+ rhs_ty' = coreExprType rhs'
+ used_bndrs' = filter (not . isDeadBinder) (case_bndr' : bndrs')
+ in
+ ( if null used_bndrs' && isUnLiftedType rhs_ty'
+ then newId realWorldStatePrimTy $ \ rw_id ->
+ returnSmpl ([rw_id], [varToCoreExpr realWorldPrimId])
+ else
+ returnSmpl (used_bndrs', map varToCoreExpr used_bndrs')
+ )
+ `thenSmpl` \ (final_bndrs', final_args) ->
+
+ -- If we try to lift a primitive-typed something out
+ -- for let-binding-purposes, we will *caseify* it (!),
+ -- with potentially-disastrous strictness results. So
+ -- instead we turn it into a function: \v -> e
+ -- where v::State# RealWorld#. The value passed to this function
+ -- is realworld#, which generates (almost) no code.
+
+ -- There's a slight infelicity here: we pass the overall
+ -- case_bndr to all the join points if it's used in *any* RHS,
+ -- because we don't know its usage in each RHS separately
+
+ newId (foldr (mkFunTy . idType) rhs_ty' final_bndrs') $ \ join_bndr ->
+ returnSmpl ([NonRec join_bndr (mkLams final_bndrs' rhs')],
+ (con, bndrs', mkApps (Var join_bndr) final_args))
+\end{code}
projects / ghc-hetmet.git / blobdiff