X-Git-Url: http://git.megacz.com/?p=ghc-hetmet.git;a=blobdiff_plain;f=compiler%2FsimplCore%2FSimplUtils.lhs;h=1ff6f8fbceebcd46c434d48aeb4f2d4258bd3176;hp=265ded6a52c1291419d35a693583e15d542bb0a1;hb=e9f23b4cc3df781f2fc84b48716a7779ecc8ab06;hpb=a2c92cccbdfdf295901e6c367c35bd4b2b0288e0 diff --git a/compiler/simplCore/SimplUtils.lhs b/compiler/simplCore/SimplUtils.lhs index 265ded6..1ff6f8f 100644 --- a/compiler/simplCore/SimplUtils.lhs +++ b/compiler/simplCore/SimplUtils.lhs @@ -5,68 +5,82 @@ \begin{code} module SimplUtils ( - mkLam, mkCase, + -- Rebuilding + mkLam, mkCase, prepareAlts, bindCaseBndr, -- Inlining, - preInlineUnconditionally, postInlineUnconditionally, activeInline, activeRule, - inlineMode, + preInlineUnconditionally, postInlineUnconditionally, + activeInline, activeRule, inlineMode, -- The continuation type SimplCont(..), DupFlag(..), LetRhsFlag(..), - contIsDupable, contResultType, - countValArgs, countArgs, pushContArgs, - mkBoringStop, mkLazyArgStop, mkRhsStop, contIsRhs, contIsRhsOrArg, - getContArgs, interestingCallContext, interestingArgContext, - interestingArg, isStrictType + contIsDupable, contResultType, contIsTrivial, contArgs, dropArgs, + countValArgs, countArgs, + mkBoringStop, mkLazyArgStop, mkRhsStop, contIsRhsOrArg, + interestingCallContext, interestingArgContext, + interestingArg, mkArgInfo ) where #include "HsVersions.h" import SimplEnv -import DynFlags ( SimplifierSwitch(..), SimplifierMode(..), - DynFlag(..), dopt ) -import StaticFlags ( opt_UF_UpdateInPlace, opt_SimplNoPreInlining, - opt_RulesOff ) +import DynFlags +import StaticFlags import CoreSyn -import CoreFVs ( exprFreeVars ) -import CoreUtils ( cheapEqExpr, exprType, exprIsTrivial, - etaExpand, exprEtaExpandArity, bindNonRec, mkCoerce2, - findDefault, exprOkForSpeculation, exprIsHNF, mergeAlts - ) -import Literal ( mkStringLit ) -import CoreUnfold ( smallEnoughToInline ) -import MkId ( eRROR_ID ) -import Id ( Id, idType, isDataConWorkId, idOccInfo, isDictId, - isDeadBinder, idNewDemandInfo, isExportedId, - idUnfolding, idNewStrictness, idInlinePragma, idHasRules - ) -import NewDemand ( isStrictDmd, isBotRes, splitStrictSig ) +import PprCore +import CoreFVs +import CoreUtils +import Literal +import CoreUnfold +import MkId +import Id +import NewDemand import SimplMonad -import Type ( Type, splitFunTys, dropForAlls, isStrictType, - splitTyConApp_maybe, tyConAppArgs - ) -import TyCon ( tyConDataCons_maybe ) -import DataCon ( dataConRepArity ) +import Type +import TyCon +import DataCon +import TcGadt ( dataConCanMatch ) import VarSet -import BasicTypes ( TopLevelFlag(..), isNotTopLevel, OccInfo(..), isLoopBreaker, isOneOcc, - Activation, isAlwaysActive, isActive ) -import Util ( lengthExceeds ) +import BasicTypes +import Util import Outputable +import List( nub ) \end{code} %************************************************************************ %* * -\subsection{The continuation data type} + The SimplCont type %* * %************************************************************************ +A SimplCont allows the simplifier to traverse the expression in a +zipper-like fashion. The SimplCont represents the rest of the expression, +"above" the point of interest. + +You can also think of a SimplCont as an "evaluation context", using +that term in the way it is used for operational semantics. This is the +way I usually think of it, For example you'll often see a syntax for +evaluation context looking like + C ::= [] | C e | case C of alts | C `cast` co +That's the kind of thing we are doing here, and I use that syntax in +the comments. + + +Key points: + * A SimplCont describes a *strict* context (just like + evaluation contexts do). E.g. Just [] is not a SimplCont + + * A SimplCont describes a context that *does not* bind + any variables. E.g. \x. [] is not a SimplCont + \begin{code} -data SimplCont -- Strict contexts - = Stop OutType -- Type of the result - LetRhsFlag - Bool -- True <=> There is something interesting about +data SimplCont + = Stop -- An empty context, or hole, [] + OutType -- Type of the result + LetRhsFlag + Bool -- True <=> There is something interesting about -- the context, and hence the inliner -- should be a bit keener (see interestingCallContext) -- Two cases: @@ -75,32 +89,30 @@ data SimplCont -- Strict contexts -- (b) This is an argument of a function that has RULES -- Inlining the call might allow the rule to fire - | CoerceIt OutType -- The To-type, simplified - SimplCont + | CoerceIt -- C `cast` co + OutCoercion -- The coercion simplified + SimplCont - | InlinePlease -- This continuation makes a function very - SimplCont -- keen to inline itelf + | ApplyTo -- C arg + DupFlag + InExpr SimplEnv -- The argument and its static env + SimplCont - | ApplyTo DupFlag - InExpr SimplEnv -- The argument, as yet unsimplified, - SimplCont -- and its environment + | Select -- case C of alts + DupFlag + InId [InAlt] SimplEnv -- The case binder, alts, and subst-env + SimplCont - | Select DupFlag - InId [InAlt] SimplEnv -- The case binder, alts, and subst-env - SimplCont + -- The two strict forms have no DupFlag, because we never duplicate them + | StrictBind -- (\x* \xs. e) C + InId [InBndr] -- let x* = [] in e + InExpr SimplEnv -- is a special case + SimplCont - | ArgOf LetRhsFlag -- An arbitrary strict context: the argument - -- of a strict function, or a primitive-arg fn - -- or a PrimOp - -- No DupFlag, because we never duplicate it - OutType -- arg_ty: type of the argument itself - OutType -- cont_ty: the type of the expression being sought by the context - -- f (error "foo") ==> coerce t (error "foo") - -- when f is strict - -- We need to know the type t, to which to coerce. - - (SimplEnv -> OutExpr -> SimplM FloatsWithExpr) -- What to do with the result - -- The result expression in the OutExprStuff has type cont_ty + | StrictArg -- e C + OutExpr OutType -- e and its type + (Bool,[Bool]) -- Whether the function at the head of e has rules, + SimplCont -- plus strictness flags for further args data LetRhsFlag = AnArg -- It's just an argument not a let RHS | AnRhs -- It's the RHS of a let (so please float lets out of big lambdas) @@ -111,12 +123,13 @@ instance Outputable LetRhsFlag where instance Outputable SimplCont where ppr (Stop ty is_rhs _) = ptext SLIT("Stop") <> brackets (ppr is_rhs) <+> ppr ty - ppr (ApplyTo dup arg se cont) = (ptext SLIT("ApplyTo") <+> ppr dup <+> ppr arg) $$ ppr cont - ppr (ArgOf _ _ _ _) = ptext SLIT("ArgOf...") + ppr (ApplyTo dup arg se cont) = ((ptext SLIT("ApplyTo") <+> ppr dup <+> pprParendExpr arg) $$ + nest 2 (pprSimplEnv se)) $$ ppr cont + ppr (StrictBind b _ _ _ cont) = (ptext SLIT("StrictBind") <+> ppr b) $$ ppr cont + ppr (StrictArg f _ _ cont) = (ptext SLIT("StrictArg") <+> ppr f) $$ ppr cont ppr (Select dup bndr alts se cont) = (ptext SLIT("Select") <+> ppr dup <+> ppr bndr) $$ - (nest 4 (ppr alts)) $$ ppr cont - ppr (CoerceIt ty cont) = (ptext SLIT("CoerceIt") <+> ppr ty) $$ ppr cont - ppr (InlinePlease cont) = ptext SLIT("InlinePlease") $$ ppr cont + (nest 4 (ppr alts $$ pprSimplEnv se)) $$ ppr cont + ppr (CoerceIt co cont) = (ptext SLIT("CoerceIt") <+> ppr co) $$ ppr cont data DupFlag = OkToDup | NoDup @@ -125,6 +138,7 @@ instance Outputable DupFlag where ppr NoDup = ptext SLIT("nodup") + ------------------- mkBoringStop :: OutType -> SimplCont mkBoringStop ty = Stop ty AnArg False @@ -135,13 +149,9 @@ mkLazyArgStop ty has_rules = Stop ty AnArg (canUpdateInPlace ty || has_rules) mkRhsStop :: OutType -> SimplCont mkRhsStop ty = Stop ty AnRhs (canUpdateInPlace ty) -contIsRhs :: SimplCont -> Bool -contIsRhs (Stop _ AnRhs _) = True -contIsRhs (ArgOf AnRhs _ _ _) = True -contIsRhs other = False - contIsRhsOrArg (Stop _ _ _) = True -contIsRhsOrArg (ArgOf _ _ _ _) = True +contIsRhsOrArg (StrictBind {}) = True +contIsRhsOrArg (StrictArg {}) = True contIsRhsOrArg other = False ------------------- @@ -150,32 +160,23 @@ contIsDupable (Stop _ _ _) = True contIsDupable (ApplyTo OkToDup _ _ _) = True contIsDupable (Select OkToDup _ _ _ _) = True contIsDupable (CoerceIt _ cont) = contIsDupable cont -contIsDupable (InlinePlease cont) = contIsDupable cont contIsDupable other = False ------------------- -discardableCont :: SimplCont -> Bool -discardableCont (Stop _ _ _) = False -discardableCont (CoerceIt _ cont) = discardableCont cont -discardableCont (InlinePlease cont) = discardableCont cont -discardableCont other = True - -discardCont :: SimplCont -- A continuation, expecting - -> SimplCont -- Replace the continuation with a suitable coerce -discardCont cont = case cont of - Stop to_ty is_rhs _ -> cont - other -> CoerceIt to_ty (mkBoringStop to_ty) - where - to_ty = contResultType cont +contIsTrivial :: SimplCont -> Bool +contIsTrivial (Stop _ _ _) = True +contIsTrivial (ApplyTo _ (Type _) _ cont) = contIsTrivial cont +contIsTrivial (CoerceIt _ cont) = contIsTrivial cont +contIsTrivial other = False ------------------- contResultType :: SimplCont -> OutType -contResultType (Stop to_ty _ _) = to_ty -contResultType (ArgOf _ _ to_ty _) = to_ty -contResultType (ApplyTo _ _ _ cont) = contResultType cont -contResultType (CoerceIt _ cont) = contResultType cont -contResultType (InlinePlease cont) = contResultType cont -contResultType (Select _ _ _ _ cont) = contResultType cont +contResultType (Stop to_ty _ _) = to_ty +contResultType (StrictArg _ _ _ cont) = contResultType cont +contResultType (StrictBind _ _ _ _ cont) = contResultType cont +contResultType (ApplyTo _ _ _ cont) = contResultType cont +contResultType (CoerceIt _ cont) = contResultType cont +contResultType (Select _ _ _ _ cont) = contResultType cont ------------------- countValArgs :: SimplCont -> Int @@ -187,101 +188,21 @@ countArgs :: SimplCont -> Int countArgs (ApplyTo _ arg se cont) = 1 + countArgs cont countArgs other = 0 -------------------- -pushContArgs :: SimplEnv -> [OutArg] -> SimplCont -> SimplCont --- Pushes args with the specified environment -pushContArgs env [] cont = cont -pushContArgs env (arg : args) cont = ApplyTo NoDup arg env (pushContArgs env args cont) +contArgs :: SimplCont -> ([OutExpr], SimplCont) +-- Uses substitution to turn each arg into an OutExpr +contArgs cont = go [] cont + where + go args (ApplyTo _ arg se cont) = go (substExpr se arg : args) cont + go args cont = (reverse args, cont) + +dropArgs :: Int -> SimplCont -> SimplCont +dropArgs 0 cont = cont +dropArgs n (ApplyTo _ _ _ cont) = dropArgs (n-1) cont +dropArgs n other = pprPanic "dropArgs" (ppr n <+> ppr other) \end{code} \begin{code} -getContArgs :: SwitchChecker - -> OutId -> SimplCont - -> ([(InExpr, SimplEnv, Bool)], -- Arguments; the Bool is true for strict args - SimplCont, -- Remaining continuation - Bool) -- Whether we came across an InlineCall --- getContArgs id k = (args, k', inl) --- args are the leading ApplyTo items in k --- (i.e. outermost comes first) --- augmented with demand info from the functionn -getContArgs chkr fun orig_cont - = let - -- Ignore strictness info if the no-case-of-case - -- flag is on. Strictness changes evaluation order - -- and that can change full laziness - stricts | switchIsOn chkr NoCaseOfCase = vanilla_stricts - | otherwise = computed_stricts - in - go [] stricts False orig_cont - where - ---------------------------- - - -- Type argument - go acc ss inl (ApplyTo _ arg@(Type _) se cont) - = go ((arg,se,False) : acc) ss inl cont - -- NB: don't bother to instantiate the function type - - -- Value argument - go acc (s:ss) inl (ApplyTo _ arg se cont) - = go ((arg,se,s) : acc) ss inl cont - - -- An Inline continuation - go acc ss inl (InlinePlease cont) - = go acc ss True cont - - -- We're run out of arguments, or else we've run out of demands - -- The latter only happens if the result is guaranteed bottom - -- This is the case for - -- * case (error "hello") of { ... } - -- * (error "Hello") arg - -- * f (error "Hello") where f is strict - -- etc - -- Then, especially in the first of these cases, we'd like to discard - -- the continuation, leaving just the bottoming expression. But the - -- type might not be right, so we may have to add a coerce. - go acc ss inl cont - | null ss && discardableCont cont = (reverse acc, discardCont cont, inl) - | otherwise = (reverse acc, cont, inl) - - ---------------------------- - vanilla_stricts, computed_stricts :: [Bool] - vanilla_stricts = repeat False - computed_stricts = zipWith (||) fun_stricts arg_stricts - - ---------------------------- - (val_arg_tys, _) = splitFunTys (dropForAlls (idType fun)) - arg_stricts = map isStrictType val_arg_tys ++ repeat False - -- These argument types are used as a cheap and cheerful way to find - -- unboxed arguments, which must be strict. But it's an InType - -- and so there might be a type variable where we expect a function - -- type (the substitution hasn't happened yet). And we don't bother - -- doing the type applications for a polymorphic function. - -- Hence the splitFunTys*IgnoringForAlls* - - ---------------------------- - -- If fun_stricts is finite, it means the function returns bottom - -- after that number of value args have been consumed - -- Otherwise it's infinite, extended with False - fun_stricts - = case splitStrictSig (idNewStrictness fun) of - (demands, result_info) - | not (demands `lengthExceeds` countValArgs orig_cont) - -> -- Enough args, use the strictness given. - -- For bottoming functions we used to pretend that the arg - -- is lazy, so that we don't treat the arg as an - -- interesting context. This avoids substituting - -- top-level bindings for (say) strings into - -- calls to error. But now we are more careful about - -- inlining lone variables, so its ok (see SimplUtils.analyseCont) - if isBotRes result_info then - map isStrictDmd demands -- Finite => result is bottom - else - map isStrictDmd demands ++ vanilla_stricts - - other -> vanilla_stricts -- Not enough args, or no strictness - -------------------- interestingArg :: OutExpr -> Bool -- An argument is interesting if it has *some* structure -- We are here trying to avoid unfolding a function that @@ -297,6 +218,14 @@ interestingArg (Var v) = hasSomeUnfolding (idUnfolding v) interestingArg (Type _) = False interestingArg (App fn (Type _)) = interestingArg fn interestingArg (Note _ a) = interestingArg a + +-- Idea (from Sam B); I'm not sure if it's a good idea, so commented out for now +-- interestingArg expr | isUnLiftedType (exprType expr) +-- -- Unlifted args are only ever interesting if we know what they are +-- = case expr of +-- Lit lit -> True +-- _ -> False + interestingArg other = True -- Consider let x = 3 in f x -- The substitution will contain (x -> ContEx 3), and we want to @@ -306,6 +235,7 @@ interestingArg other = True -- that x is not interesting (assuming y has no unfolding) \end{code} + Comment about interestingCallContext ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ We want to avoid inlining an expression where there can't possibly be @@ -386,13 +316,13 @@ interestingCallContext :: Bool -- False <=> no args at all interestingCallContext some_args some_val_args cont = interesting cont where - interesting (InlinePlease _) = True - interesting (Select _ _ _ _ _) = some_args - interesting (ApplyTo _ _ _ _) = True -- Can happen if we have (coerce t (f x)) y + interesting (Select {}) = some_args + interesting (ApplyTo {}) = True -- Can happen if we have (coerce t (f x)) y -- Perhaps True is a bit over-keen, but I've -- seen (coerce f) x, where f has an INLINE prag, -- So we have to give some motivaiton for inlining it - interesting (ArgOf _ _ _ _) = some_val_args + interesting (StrictArg {}) = some_val_args + interesting (StrictBind {}) = some_val_args -- ?? interesting (Stop ty _ interesting) = some_val_args && interesting interesting (CoerceIt _ cont) = interesting cont -- If this call is the arg of a strict function, the context @@ -412,6 +342,41 @@ interestingCallContext some_args some_val_args cont ------------------- +mkArgInfo :: Id + -> Int -- Number of value args + -> SimplCont -- Context of the cal + -> (Bool, [Bool]) -- Arg info +-- The arg info consists of +-- * A Bool indicating if the function has rules (recursively) +-- * A [Bool] indicating strictness for each arg +-- The [Bool] is usually infinite, but if it is finite it +-- guarantees that the function diverges after being given +-- that number of args + +mkArgInfo fun n_val_args call_cont + = (interestingArgContext fun call_cont, fun_stricts) + where + vanilla_stricts, fun_stricts :: [Bool] + vanilla_stricts = repeat False + + fun_stricts + = case splitStrictSig (idNewStrictness fun) of + (demands, result_info) + | not (demands `lengthExceeds` n_val_args) + -> -- Enough args, use the strictness given. + -- For bottoming functions we used to pretend that the arg + -- is lazy, so that we don't treat the arg as an + -- interesting context. This avoids substituting + -- top-level bindings for (say) strings into + -- calls to error. But now we are more careful about + -- inlining lone variables, so its ok (see SimplUtils.analyseCont) + if isBotRes result_info then + map isStrictDmd demands -- Finite => result is bottom + else + map isStrictDmd demands ++ vanilla_stricts + + other -> vanilla_stricts -- Not enough args, or no strictness + interestingArgContext :: Id -> SimplCont -> Bool -- If the argument has form (f x y), where x,y are boring, -- and f is marked INLINE, then we don't want to inline f. @@ -431,10 +396,10 @@ interestingArgContext :: Id -> SimplCont -> Bool interestingArgContext fn cont = idHasRules fn || go cont where - go (InlinePlease c) = go c go (Select {}) = False go (ApplyTo {}) = False - go (ArgOf {}) = True + go (StrictArg {}) = True + go (StrictBind {}) = False -- ?? go (CoerceIt _ c) = go c go (Stop _ _ interesting) = interesting @@ -709,27 +674,43 @@ our new view that inlining is like a RULE, so I'm sticking to the 'active' story for now. \begin{code} -postInlineUnconditionally :: SimplEnv -> TopLevelFlag -> OutId -> OccInfo -> OutExpr -> Unfolding -> Bool +postInlineUnconditionally + :: SimplEnv -> TopLevelFlag + -> InId -- The binder (an OutId would be fine too) + -> OccInfo -- From the InId + -> OutExpr + -> Unfolding + -> Bool postInlineUnconditionally env top_lvl bndr occ_info rhs unfolding | not active = False - | isLoopBreaker occ_info = False + | isLoopBreaker occ_info = False -- If it's a loop-breaker of any kind, dont' inline + -- because it might be referred to "earlier" | isExportedId bndr = False | exprIsTrivial rhs = True | otherwise = case occ_info of - OneOcc in_lam one_br int_cxt - -> (one_br || smallEnoughToInline unfolding) -- Small enough to dup + -- The point of examining occ_info here is that for *non-values* + -- that occur outside a lambda, the call-site inliner won't have + -- a chance (becuase it doesn't know that the thing + -- only occurs once). The pre-inliner won't have gotten + -- it either, if the thing occurs in more than one branch + -- So the main target is things like + -- let x = f y in + -- case v of + -- True -> case x of ... + -- False -> case x of ... + -- I'm not sure how important this is in practice + OneOcc in_lam one_br int_cxt -- OneOcc => no code-duplication issue + -> smallEnoughToInline unfolding -- Small enough to dup -- ToDo: consider discount on smallEnoughToInline if int_cxt is true -- - -- NB: Do we want to inline arbitrarily big things becuase - -- one_br is True? that can lead to inline cascades. But - -- preInlineUnconditionlly has dealt with all the common cases - -- so perhaps it's worth the risk. Here's an example - -- let f = if b then Left (\x.BIG) else Right (\y.BIG) - -- in \y. ....f.... - -- We can't preInlineUnconditionally because that woud invalidate - -- the occ info for b. Yet f is used just once, and duplicating - -- the case work is fine (exprIsCheap). + -- NB: Do NOT inline arbitrarily big things, even if one_br is True + -- Reason: doing so risks exponential behaviour. We simplify a big + -- expression, inline it, and simplify it again. But if the + -- very same thing happens in the big expression, we get + -- exponential cost! + -- PRINCIPLE: when we've already simplified an expression once, + -- make sure that we only inline it if it's reasonably small. && ((isNotTopLevel top_lvl && not in_lam) || -- But outside a lambda, we want to be reasonably aggressive @@ -745,28 +726,35 @@ postInlineUnconditionally env top_lvl bndr occ_info rhs unfolding -- int_cxt to prevent us inlining inside a lambda without some -- good reason. See the notes on int_cxt in preInlineUnconditionally + IAmDead -> True -- 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 ... + other -> False - -- The point here is that for *non-values* that occur - -- outside a lambda, the call-site inliner won't have - -- a chance (becuase it doesn't know that the thing - -- only occurs once). The pre-inliner won't have gotten - -- it either, if the thing occurs in more than one branch - -- So the main target is things like - -- let x = f y in - -- case v of - -- True -> case x of ... - -- False -> case x of ... - -- I'm not sure how important this is in practice + +-- Here's an example that we don't handle well: +-- let f = if b then Left (\x.BIG) else Right (\y.BIG) +-- in \y. ....case f of {...} .... +-- Here f is used just once, and duplicating the case work is fine (exprIsCheap). +-- But +-- * We can't preInlineUnconditionally because that woud invalidate +-- the occ info for b. +-- * We can't postInlineUnconditionally because the RHS is big, and +-- that risks exponential behaviour +-- * We can't call-site inline, because the rhs is big +-- Alas! + where active = case getMode env of SimplGently -> isAlwaysActive prag SimplPhase n -> isActive n prag prag = idInlinePragma bndr -activeInline :: SimplEnv -> OutId -> OccInfo -> Bool -activeInline env id occ +activeInline :: SimplEnv -> OutId -> Bool +activeInline env id = case getMode env of - SimplGently -> isOneOcc occ && isAlwaysActive prag + SimplGently -> False -- No inlining at all when doing gentle stuff, -- except for local things that occur once -- The reason is that too little clean-up happens if you @@ -799,41 +787,66 @@ activeRule env -- to work in Template Haskell when simplifying -- splices, so we get simpler code for literal strings SimplPhase n -> Just (isActive n) -\end{code} +\end{code} %************************************************************************ %* * -\subsection{Rebuilding a lambda} + Rebuilding a lambda %* * %************************************************************************ \begin{code} -mkLam :: SimplEnv -> [OutBinder] -> OutExpr -> SimplCont -> SimplM FloatsWithExpr +mkLam :: [OutBndr] -> OutExpr -> SimplM OutExpr +-- mkLam tries three things +-- a) eta reduction, if that gives a trivial expression +-- b) eta expansion [only if there are some value lambdas] + +mkLam bndrs body + = do { dflags <- getDOptsSmpl + ; mkLam' dflags bndrs body } + where + mkLam' :: DynFlags -> [OutBndr] -> OutExpr -> SimplM OutExpr + mkLam' dflags bndrs (Cast body@(Lam _ _) co) + -- Note [Casts and lambdas] + = do { lam <- mkLam' dflags (bndrs ++ bndrs') body' + ; return (mkCoerce (mkPiTypes bndrs co) lam) } + where + (bndrs',body') = collectBinders body + + mkLam' dflags bndrs body + | dopt Opt_DoEtaReduction dflags, + Just etad_lam <- tryEtaReduce bndrs body + = do { tick (EtaReduction (head bndrs)) + ; return etad_lam } + + | dopt Opt_DoLambdaEtaExpansion dflags, + any isRuntimeVar bndrs + = do { body' <- tryEtaExpansion dflags body + ; return (mkLams bndrs body') } + + | otherwise + = returnSmpl (mkLams bndrs body) \end{code} -Try three things - a) eta reduction, if that gives a trivial expression - b) eta expansion [only if there are some value lambdas] - c) floating lets out through big lambdas - [only if all tyvar lambdas, and only if this lambda - is the RHS of a let] +Note [Casts and lambdas] +~~~~~~~~~~~~~~~~~~~~~~~~ +Consider + (\x. (\y. e) `cast` g1) `cast` g2 +There is a danger here that the two lambdas look separated, and the +full laziness pass might float an expression to between the two. -\begin{code} -mkLam env bndrs body cont - = getDOptsSmpl `thenSmpl` \dflags -> - mkLam' dflags env bndrs body cont - where - mkLam' dflags env bndrs body cont - | dopt Opt_DoEtaReduction dflags, - Just etad_lam <- tryEtaReduce bndrs body - = tick (EtaReduction (head bndrs)) `thenSmpl_` - returnSmpl (emptyFloats env, etad_lam) - - | dopt Opt_DoLambdaEtaExpansion dflags, - any isRuntimeVar bndrs - = tryEtaExpansion body `thenSmpl` \ body' -> - returnSmpl (emptyFloats env, mkLams bndrs body') +So this equation in mkLam' floats the g1 out, thus: + (\x. e `cast` g1) --> (\x.e) `cast` (tx -> g1) +where x:tx. + +In general, this floats casts outside lambdas, where (I hope) they might meet +and cancel with some other cast. + + +-- c) floating lets out through big lambdas +-- [only if all tyvar lambdas, and only if this lambda +-- is the RHS of a let] {- Sept 01: I'm experimenting with getting the full laziness pass to float out past big lambdsa @@ -846,10 +859,6 @@ mkLam env bndrs body cont returnSmpl (floats, mkLams bndrs body') -} - | otherwise - = returnSmpl (emptyFloats env, mkLams bndrs body) -\end{code} - %************************************************************************ %* * @@ -863,7 +872,7 @@ We don't want to remove extra lambdas unless we are going to avoid allocating this thing altogether \begin{code} -tryEtaReduce :: [OutBinder] -> OutExpr -> Maybe OutExpr +tryEtaReduce :: [OutBndr] -> OutExpr -> Maybe OutExpr tryEtaReduce bndrs body -- We don't use CoreUtils.etaReduce, because we can be more -- efficient here: @@ -915,13 +924,13 @@ when computing arity; and etaExpand adds the coerces as necessary when actually computing the expansion. \begin{code} -tryEtaExpansion :: OutExpr -> SimplM OutExpr +tryEtaExpansion :: DynFlags -> OutExpr -> SimplM OutExpr -- There is at least one runtime binder in the binders -tryEtaExpansion body +tryEtaExpansion dflags body = getUniquesSmpl `thenSmpl` \ us -> returnSmpl (etaExpand fun_arity us body (exprType body)) where - fun_arity = exprEtaExpandArity body + fun_arity = exprEtaExpandArity dflags body \end{code} @@ -1109,25 +1118,11 @@ tryRhsTyLam env tyvars body -- Only does something if there's a let %************************************************************************ %* * -\subsection{Case absorption and identity-case elimination} + prepareAlts %* * %************************************************************************ -mkCase puts a case expression back together, trying various transformations first. - -\begin{code} -mkCase :: OutExpr -> OutId -> OutType - -> [OutAlt] -- Increasing order - -> SimplM OutExpr - -mkCase scrut case_bndr ty alts - = getDOptsSmpl `thenSmpl` \dflags -> - mkAlts dflags scrut case_bndr alts `thenSmpl` \ better_alts -> - mkCase1 scrut case_bndr ty better_alts -\end{code} - - -mkAlts tries these things: +prepareAlts tries these things: 1. If several alternatives are identical, merge them into a single DEFAULT alternative. I've occasionally seen this @@ -1182,43 +1177,93 @@ This gave rise to a horrible sequence of cases and similarly in cascade for all the join points! - +Note [Dead binders] +~~~~~~~~~~~~~~~~~~~~ +We do this *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. \begin{code} +prepareAlts :: OutExpr -> OutId -> [InAlt] -> SimplM ([AltCon], [InAlt]) +prepareAlts scrut case_bndr' alts + = do { dflags <- getDOptsSmpl + ; alts <- combineIdenticalAlts case_bndr' alts + + ; let (alts_wo_default, maybe_deflt) = findDefault alts + alt_cons = [con | (con,_,_) <- alts_wo_default] + imposs_deflt_cons = nub (imposs_cons ++ alt_cons) + -- "imposs_deflt_cons" are handled either by the context, + -- OR by a branch in this case expression. + -- Don't include DEFAULT!! + + ; default_alts <- prepareDefault dflags scrut case_bndr' mb_tc_app + imposs_deflt_cons maybe_deflt + + ; let trimmed_alts = filter possible_alt alts_wo_default + merged_alts = mergeAlts default_alts trimmed_alts + -- We need the mergeAlts in case the new default_alt + -- has turned into a constructor alternative. + -- The merge keeps the inner DEFAULT at the front, if there is one + -- and eliminates any inner_alts that are shadowed by the outer_alts + + + ; return (imposs_deflt_cons, merged_alts) } + where + mb_tc_app = splitTyConApp_maybe (idType case_bndr') + Just (_, inst_tys) = mb_tc_app + + imposs_cons = case scrut of + Var v -> otherCons (idUnfolding v) + other -> [] + + possible_alt :: CoreAlt -> Bool + possible_alt (con, _, _) | con `elem` imposs_cons = False + possible_alt (DataAlt con, _, _) = dataConCanMatch inst_tys con + possible_alt alt = True + + -------------------------------------------------- -- 1. Merge identical branches -------------------------------------------------- -mkAlts dflags scrut case_bndr alts@((con1,bndrs1,rhs1) : con_alts) +combineIdenticalAlts :: OutId -> [InAlt] -> SimplM [InAlt] + +combineIdenticalAlts case_bndr alts@((con1,bndrs1,rhs1) : con_alts) | all isDeadBinder bndrs1, -- Remember the default length filtered_alts < length con_alts -- alternative comes first - = tick (AltMerge case_bndr) `thenSmpl_` - returnSmpl better_alts + -- Also Note [Dead binders] + = do { tick (AltMerge case_bndr) + ; return ((DEFAULT, [], rhs1) : filtered_alts) } where filtered_alts = filter keep con_alts keep (con,bndrs,rhs) = not (all isDeadBinder bndrs && rhs `cheapEqExpr` rhs1) - better_alts = (DEFAULT, [], rhs1) : filtered_alts - - --------------------------------------------------- --- 2. Merge nested cases --------------------------------------------------- -mkAlts dflags scrut outer_bndr outer_alts - | dopt Opt_CaseMerge dflags, - (outer_alts_without_deflt, maybe_outer_deflt) <- findDefault outer_alts, - Just (Case (Var scrut_var) inner_bndr _ inner_alts) <- maybe_outer_deflt, - scruting_same_var scrut_var - = let - munged_inner_alts = [(con, args, munge_rhs rhs) | (con, args, rhs) <- inner_alts] - munge_rhs rhs = bindCaseBndr inner_bndr (Var outer_bndr) rhs - - new_alts = mergeAlts outer_alts_without_deflt munged_inner_alts - -- The merge keeps the inner DEFAULT at the front, if there is one - -- and eliminates any inner_alts that are shadowed by the outer_alts - in - tick (CaseMerge outer_bndr) `thenSmpl_` - returnSmpl new_alts - -- Warning: don't call mkAlts recursively! +combineIdenticalAlts case_bndr alts = return alts + +------------------------------------------------------------------------- +-- Prepare the default alternative +------------------------------------------------------------------------- +prepareDefault :: DynFlags + -> OutExpr -- Scrutinee + -> OutId -- Case binder; need just for its type. Note that as an + -- OutId, it has maximum information; this is important. + -- Test simpl013 is an example + -> Maybe (TyCon, [Type]) -- Type of scrutinee, decomposed + -> [AltCon] -- These cons can't happen when matching the default + -> Maybe InExpr -- Rhs + -> SimplM [InAlt] -- Still unsimplified + -- We use a list because it's what mergeAlts expects, + -- And becuase case-merging can cause many to show up + +------- Merge nested cases ---------- +prepareDefault dflags scrut outer_bndr bndr_ty imposs_cons (Just deflt_rhs) + | dopt Opt_CaseMerge dflags + , Case (Var scrut_var) inner_bndr _ inner_alts <- deflt_rhs + , scruting_same_var scrut_var + = do { tick (CaseMerge outer_bndr) + + ; let munge_rhs rhs = bindCaseBndr inner_bndr (Var outer_bndr) rhs + ; return [(con, args, munge_rhs rhs) | (con, args, rhs) <- inner_alts] } + -- Warning: don't call prepareAlts recursively! -- Firstly, there's no point, because inner alts have already had -- mkCase applied to them, so they won't have a case in their default -- Secondly, if you do, you get an infinite loop, because the bindCaseBndr @@ -1232,18 +1277,54 @@ mkAlts dflags scrut outer_bndr outer_alts Var outer_scrut -> \ v -> v == outer_bndr || v == outer_scrut other -> \ v -> v == outer_bndr ------------------------------------------------- --- Catch-all ------------------------------------------------- - -mkAlts dflags scrut case_bndr other_alts = returnSmpl other_alts +--------- Fill in known constructor ----------- +prepareDefault dflags scrut case_bndr (Just (tycon, inst_tys)) imposs_cons (Just deflt_rhs) + | -- This branch handles the case where we are + -- scrutinisng an algebraic data type + isAlgTyCon tycon -- It's a data type, tuple, or unboxed tuples. + , not (isNewTyCon tycon) -- We can have a newtype, if we are just doing an eval: + -- case x of { DEFAULT -> e } + -- and we don't want to fill in a default for them! + , Just all_cons <- tyConDataCons_maybe tycon + , not (null all_cons) -- This is a tricky corner case. If the data type has no constructors, + -- which GHC allows, then the case expression will have at most a default + -- alternative. We don't want to eliminate that alternative, because the + -- invariant is that there's always one alternative. It's more convenient + -- to leave + -- case x of { DEFAULT -> e } + -- as it is, rather than transform it to + -- error "case cant match" + -- which would be quite legitmate. But it's a really obscure corner, and + -- not worth wasting code on. + , let imposs_data_cons = [con | DataAlt con <- imposs_cons] -- We now know it's a data type + is_possible con = not (con `elem` imposs_data_cons) + && dataConCanMatch inst_tys con + = case filter is_possible all_cons of + [] -> return [] -- Eliminate the default alternative + -- altogether if it can't match + + [con] -> -- It matches exactly one constructor, so fill it in + do { tick (FillInCaseDefault case_bndr) + ; us <- getUniquesSmpl + ; let (ex_tvs, co_tvs, arg_ids) = + dataConRepInstPat us con inst_tys + ; return [(DataAlt con, ex_tvs ++ co_tvs ++ arg_ids, deflt_rhs)] } + + two_or_more -> return [(DEFAULT, [], deflt_rhs)] + +--------- Catch-all cases ----------- +prepareDefault dflags scrut case_bndr bndr_ty imposs_cons (Just deflt_rhs) + = return [(DEFAULT, [], deflt_rhs)] + +prepareDefault dflags scrut case_bndr bndr_ty imposs_cons Nothing + = return [] -- No default branch \end{code} ================================================================================= -mkCase1 tries these things +mkCase tries these things 1. Eliminate the case altogether if possible @@ -1256,213 +1337,66 @@ mkCase1 tries these things and similar friends. -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. - -We also make sure that we deal with this very common case: - - case e of - x -> ...x... - -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) - -Lastly, we generalise the transformation to handle this: - - case e of ===> r - True -> r - False -> r - -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. - -So the case-elimination algorithm is: - - 1. Eliminate alternatives which can't match - - 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 - - 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! - - or * [Prim cases] the scrutinee is a primitive variable - - 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.] - - -If so, then we can replace the case with one of the rhss. - -Further notes about case elimination -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Consider: test :: Integer -> IO () - test = print - -Turns out that this compiles to: - Print.test - = \ eta :: Integer - eta1 :: State# RealWorld -> - case PrelNum.< eta PrelNum.zeroInteger of wild { __DEFAULT -> - case hPutStr stdout - (PrelNum.jtos eta ($w[] @ Char)) - eta1 - of wild1 { (# new_s, a4 #) -> PrelIO.lvl23 new_s }} - -Notice the strange '<' which has no effect at all. This is a funny one. -It started like this: - -f x y = if x < 0 then jtos x - else if y==0 then "" else jtos x - -At a particular call site we have (f v 1). So we inline to get - - if v < 0 then jtos x - else if 1==0 then "" else jtos x - -Now simplify the 1==0 conditional: - - if v<0 then jtos v else jtos v - -Now common-up the two branches of the case: - - case (v<0) of DEFAULT -> jtos v - -Why don't we drop the case? Because it's strict in v. It's technically -wrong to drop even unnecessary evaluations, and in practice they -may be a result of 'seq' so we *definitely* don't want to drop those. -I don't really know how to improve this situation. - - \begin{code} +mkCase :: OutExpr -> OutId -> OutType + -> [OutAlt] -- Increasing order + -> SimplM OutExpr + -------------------------------------------------- --- 0. Check for empty alternatives +-- 1. Check for empty alternatives -------------------------------------------------- -- This isn't strictly an error. It's possible that the simplifer might "see" -- that an inner case has no accessible alternatives before it "sees" that the -- entire branch of an outer case is inaccessible. So we simply -- put an error case here insteadd -mkCase1 scrut case_bndr ty [] - = pprTrace "mkCase1: null alts" (ppr case_bndr <+> ppr scrut) $ +mkCase scrut case_bndr ty [] + = pprTrace "mkCase: null alts" (ppr case_bndr <+> ppr scrut) $ return (mkApps (Var eRROR_ID) [Type ty, Lit (mkStringLit "Impossible alternative")]) --------------------------------------------------- --- 1. Eliminate the case altogether if poss --------------------------------------------------- - -mkCase1 scrut case_bndr ty [(con,bndrs,rhs)] - -- See if we can get rid of the case altogether - -- See the extensive notes on case-elimination above - -- mkCase made sure that if all the alternatives are equal, - -- then there is now only one (DEFAULT) rhs - | all isDeadBinder bndrs, - - -- Check that the scrutinee can be let-bound instead of case-bound - exprOkForSpeculation scrut - -- OK not to evaluate it - -- This includes things like (==# a# b#)::Bool - -- so that we simplify - -- case ==# a# b# of { True -> x; False -> x } - -- to just - -- x - -- This particular example shows up in default methods for - -- comparision operations (e.g. in (>=) for Int.Int32) - || exprIsHNF scrut -- It's already evaluated - || var_demanded_later scrut -- It'll be demanded later - --- || not opt_SimplPedanticBottoms) -- Or we don't care! --- We used to allow improving termination by discarding cases, unless -fpedantic-bottoms was on, --- but that breaks badly for the dataToTag# primop, which relies on a case to evaluate --- its argument: case x of { y -> dataToTag# y } --- Here we must *not* discard the case, because dataToTag# just fetches the tag from --- the info pointer. So we'll be pedantic all the time, and see if that gives any --- other problems --- Also we don't want to discard 'seq's - = tick (CaseElim case_bndr) `thenSmpl_` - returnSmpl (bindCaseBndr case_bndr scrut rhs) - - where - -- The case binder is going to be evaluated later, - -- and the scrutinee is a simple variable - var_demanded_later (Var v) = isStrictDmd (idNewDemandInfo case_bndr) - var_demanded_later other = False - -------------------------------------------------- -- 2. Identity case -------------------------------------------------- -mkCase1 scrut case_bndr ty alts -- Identity case +mkCase scrut case_bndr ty alts -- Identity case | all identity_alt alts = tick (CaseIdentity case_bndr) `thenSmpl_` - returnSmpl (re_note scrut) + returnSmpl (re_cast scrut) where - identity_alt (con, args, rhs) = de_note rhs `cheapEqExpr` identity_rhs con args + identity_alt (con, args, rhs) = check_eq con args (de_cast rhs) - identity_rhs (DataAlt con) args = mkConApp con (arg_tys ++ map varToCoreExpr args) - identity_rhs (LitAlt lit) _ = Lit lit - identity_rhs DEFAULT _ = Var case_bndr + check_eq DEFAULT _ (Var v) = v == case_bndr + check_eq (LitAlt lit') _ (Lit lit) = lit == lit' + check_eq (DataAlt con) args rhs = rhs `cheapEqExpr` mkConApp con (arg_tys ++ varsToCoreExprs args) + || rhs `cheapEqExpr` Var case_bndr + check_eq con args rhs = False arg_tys = map Type (tyConAppArgs (idType case_bndr)) -- We've seen this: - -- case coerce T e of x { _ -> coerce T' x } - -- And we definitely want to eliminate this case! - -- So we throw away notes from the RHS, and reconstruct - -- (at least an approximation) at the other end - de_note (Note _ e) = de_note e - de_note e = e + -- case e of x { _ -> x `cast` c } + -- And we definitely want to eliminate this case, to give + -- e `cast` c + -- So we throw away the cast from the RHS, and reconstruct + -- it at the other end. All the RHS casts must be the same + -- if (all identity_alt alts) holds. + -- + -- Don't worry about nested casts, because the simplifier combines them + de_cast (Cast e _) = e + de_cast e = e + + re_cast scrut = case head alts of + (_,_,Cast _ co) -> Cast scrut co + other -> scrut - -- re_note wraps a coerce if it might be necessary - re_note scrut = case head alts of - (_,_,rhs1@(Note _ _)) -> mkCoerce2 (exprType rhs1) (idType case_bndr) scrut - other -> scrut -------------------------------------------------- -- Catch-all -------------------------------------------------- -mkCase1 scrut bndr ty alts = returnSmpl (Case scrut bndr ty alts) +mkCase scrut bndr ty alts = returnSmpl (Case scrut bndr ty alts) \end{code}