X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2FsimplCore%2FSimplUtils.lhs;h=6ce29a2562755448a27d7761e4b411933f6b15cb;hb=8f47436d4941e7871569e47bf8c2f5a6180bdbd5;hp=fbe5f18b892c1c84c06cd3f4cbc065dcf384fedd;hpb=6f074a37a1546391632863898da3c32bbb7995df;p=ghc-hetmet.git diff --git a/compiler/simplCore/SimplUtils.lhs b/compiler/simplCore/SimplUtils.lhs index fbe5f18..6ce29a2 100644 --- a/compiler/simplCore/SimplUtils.lhs +++ b/compiler/simplCore/SimplUtils.lhs @@ -4,9 +4,16 @@ \section[SimplUtils]{The simplifier utilities} \begin{code} +{-# OPTIONS -w #-} +-- The above warning supression flag is a temporary kludge. +-- While working on this module you are encouraged to remove it and fix +-- any warnings in the module. See +-- http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#Warnings +-- for details + module SimplUtils ( -- Rebuilding - mkLam, mkCase, + mkLam, mkCase, prepareAlts, bindCaseBndr, -- Inlining, preInlineUnconditionally, postInlineUnconditionally, @@ -15,11 +22,13 @@ module SimplUtils ( -- The continuation type SimplCont(..), DupFlag(..), LetRhsFlag(..), contIsDupable, contResultType, contIsTrivial, contArgs, dropArgs, - countValArgs, countArgs, + countValArgs, countArgs, splitInlineCont, mkBoringStop, mkLazyArgStop, mkRhsStop, contIsRhsOrArg, interestingCallContext, interestingArgContext, - interestingArg, isStrictBndr, mkArgInfo + interestingArg, mkArgInfo, + + abstractFloats ) where #include "HsVersions.h" @@ -28,22 +37,27 @@ import SimplEnv import DynFlags import StaticFlags import CoreSyn +import qualified CoreSubst import PprCore import CoreFVs import CoreUtils import Literal import CoreUnfold import MkId +import Name import Id +import Var ( isCoVar ) import NewDemand import SimplMonad -import Type +import Type hiding( substTy ) import TyCon import DataCon +import Unify ( dataConCannotMatch ) import VarSet import BasicTypes import Util import Outputable +import List( nub ) \end{code} @@ -81,10 +95,8 @@ data SimplCont Bool -- True <=> There is something interesting about -- the context, and hence the inliner -- should be a bit keener (see interestingCallContext) - -- Two cases: - -- (a) This is the RHS of a thunk whose type suggests - -- that update-in-place would be possible - -- (b) This is an argument of a function that has RULES + -- Specifically: + -- This is an argument of a function that has RULES -- Inlining the call might allow the rule to fire | CoerceIt -- C `cast` co @@ -121,12 +133,12 @@ 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 <+> pprParendExpr arg) $$ - nest 2 (pprSimplEnv se)) $$ ppr cont + 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 $$ pprSimplEnv se)) $$ ppr cont + (nest 4 (ppr alts)) $$ ppr cont ppr (CoerceIt co cont) = (ptext SLIT("CoerceIt") <+> ppr co) $$ ppr cont data DupFlag = OkToDup | NoDup @@ -142,19 +154,20 @@ mkBoringStop :: OutType -> SimplCont mkBoringStop ty = Stop ty AnArg False mkLazyArgStop :: OutType -> Bool -> SimplCont -mkLazyArgStop ty has_rules = Stop ty AnArg (canUpdateInPlace ty || has_rules) +mkLazyArgStop ty has_rules = Stop ty AnArg has_rules mkRhsStop :: OutType -> SimplCont -mkRhsStop ty = Stop ty AnRhs (canUpdateInPlace ty) +mkRhsStop ty = Stop ty AnRhs False -contIsRhsOrArg (Stop _ _ _) = True -contIsRhsOrArg (StrictBind {}) = True -contIsRhsOrArg (StrictArg {}) = True -contIsRhsOrArg other = False +------------------- +contIsRhsOrArg (Stop {}) = True +contIsRhsOrArg (StrictBind {}) = True +contIsRhsOrArg (StrictArg {}) = True +contIsRhsOrArg other = False ------------------- contIsDupable :: SimplCont -> Bool -contIsDupable (Stop _ _ _) = True +contIsDupable (Stop {}) = True contIsDupable (ApplyTo OkToDup _ _ _) = True contIsDupable (Select OkToDup _ _ _ _) = True contIsDupable (CoerceIt _ cont) = contIsDupable cont @@ -162,7 +175,7 @@ contIsDupable other = False ------------------- contIsTrivial :: SimplCont -> Bool -contIsTrivial (Stop _ _ _) = True +contIsTrivial (Stop {}) = True contIsTrivial (ApplyTo _ (Type _) _ cont) = contIsTrivial cont contIsTrivial (CoerceIt _ cont) = contIsTrivial cont contIsTrivial other = False @@ -197,6 +210,26 @@ 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) + +-------------------- +splitInlineCont :: SimplCont -> Maybe (SimplCont, SimplCont) +-- Returns Nothing if the continuation should dissolve an InlineMe Note +-- Return Just (c1,c2) otherwise, +-- where c1 is the continuation to put inside the InlineMe +-- and c2 outside + +-- Example: (__inline_me__ (/\a. e)) ty +-- Here we want to do the beta-redex without dissolving the InlineMe +-- See test simpl017 (and Trac #1627) for a good example of why this is important + +splitInlineCont (ApplyTo dup (Type ty) se c) + | Just (c1, c2) <- splitInlineCont c = Just (ApplyTo dup (Type ty) se c1, c2) +splitInlineCont cont@(Stop ty _ _) = Just (mkBoringStop ty, cont) +splitInlineCont cont@(StrictBind bndr _ _ se _) = Just (mkBoringStop (substTy se (idType bndr)), cont) +splitInlineCont cont@(StrictArg _ fun_ty _ _) = Just (mkBoringStop (funArgTy fun_ty), cont) +splitInlineCont other = Nothing + -- NB: the calculation of the type for mkBoringStop is an annoying + -- duplication of the same calucation in mkDupableCont \end{code} @@ -216,6 +249,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 @@ -259,62 +300,25 @@ applies when x is bound to a lambda expression. Hence contIsInteresting looks for case expressions with just a single default case. + \begin{code} -interestingCallContext :: Bool -- False <=> no args at all - -> Bool -- False <=> no value args - -> SimplCont -> Bool - -- The "lone-variable" case is important. I spent ages - -- messing about with unsatisfactory varaints, but this is nice. - -- The idea is that if a variable appear all alone - -- as an arg of lazy fn, or rhs Stop - -- as scrutinee of a case Select - -- as arg of a strict fn ArgOf - -- then we should not inline it (unless there is some other reason, - -- e.g. is is the sole occurrence). We achieve this by making - -- interestingCallContext return False for a lone variable. - -- - -- Why? At least in the case-scrutinee situation, turning - -- let x = (a,b) in case x of y -> ... - -- into - -- let x = (a,b) in case (a,b) of y -> ... - -- and thence to - -- let x = (a,b) in let y = (a,b) in ... - -- is bad if the binding for x will remain. - -- - -- Another example: I discovered that strings - -- were getting inlined straight back into applications of 'error' - -- because the latter is strict. - -- s = "foo" - -- f = \x -> ...(error s)... - - -- Fundamentally such contexts should not ecourage inlining because - -- the context can ``see'' the unfolding of the variable (e.g. case or a RULE) - -- so there's no gain. - -- - -- However, even a type application or coercion isn't a lone variable. - -- Consider - -- case $fMonadST @ RealWorld of { :DMonad a b c -> c } - -- We had better inline that sucker! The case won't see through it. - -- - -- For now, I'm treating treating a variable applied to types - -- in a *lazy* context "lone". The motivating example was - -- f = /\a. \x. BIG - -- g = /\a. \y. h (f a) - -- There's no advantage in inlining f here, and perhaps - -- a significant disadvantage. Hence some_val_args in the Stop case - -interestingCallContext some_args some_val_args cont +interestingCallContext :: SimplCont -> CallContInfo +interestingCallContext cont = interesting cont where - interesting (Select {}) = some_args - interesting (ApplyTo {}) = True -- Can happen if we have (coerce t (f x)) y + interesting (Select _ bndr _ _ _) + | isDeadBinder bndr = CaseCont + | otherwise = InterestingCont + + interesting (ApplyTo {}) = InterestingCont + -- 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 (StrictArg {}) = some_val_args - interesting (StrictBind {}) = some_val_args -- ?? - interesting (Stop ty _ interesting) = some_val_args && interesting - interesting (CoerceIt _ cont) = interesting cont + -- So we have to give some motivation for inlining it + interesting (StrictArg {}) = InterestingCont + interesting (StrictBind {}) = InterestingCont + interesting (Stop ty _ yes) = if yes then InterestingCont else BoringCont + interesting (CoerceIt _ cont) = interesting cont -- If this call is the arg of a strict function, the context -- is a bit interesting. If we inline here, we may get useful -- evaluation information to avoid repeated evals: e.g. @@ -375,7 +379,9 @@ interestingArgContext :: Id -> SimplCont -> Bool -- where g has rules, then we *do* want to inline f, in case it -- exposes a rule that might fire. Similarly, if the context is -- h (g (f x x)) --- where h has rules, then we do want to inline f. +-- where h has rules, then we do want to inline f; hence the +-- call_cont argument to interestingArgContext +-- -- The interesting_arg_ctxt flag makes this happen; if it's -- set, the inliner gets just enough keener to inline f -- regardless of how boring f's arguments are, if it's marked INLINE @@ -383,8 +389,8 @@ interestingArgContext :: Id -> SimplCont -> Bool -- The alternative would be to *always* inline an INLINE function, -- regardless of how boring its context is; but that seems overkill -- For example, it'd mean that wrapper functions were always inlined -interestingArgContext fn cont - = idHasRules fn || go cont +interestingArgContext fn call_cont + = idHasRules fn || go call_cont where go (Select {}) = False go (ApplyTo {}) = False @@ -392,27 +398,6 @@ interestingArgContext fn cont go (StrictBind {}) = False -- ?? go (CoerceIt _ c) = go c go (Stop _ _ interesting) = interesting - -------------------- -canUpdateInPlace :: Type -> Bool --- Consider let x = in ... --- If returns an explicit constructor, we might be able --- to do update in place. So we treat even a thunk RHS context --- as interesting if update in place is possible. We approximate --- this by seeing if the type has a single constructor with a --- small arity. But arity zero isn't good -- we share the single copy --- for that case, so no point in sharing. - -canUpdateInPlace ty - | not opt_UF_UpdateInPlace = False - | otherwise - = case splitTyConApp_maybe ty of - Nothing -> False - Just (tycon, _) -> case tyConDataCons_maybe tycon of - Just [dc] -> arity == 1 || arity == 2 - where - arity = dataConRepArity dc - other -> False \end{code} @@ -547,7 +532,7 @@ y's occurrence info, which breaks the invariant. It matters: y might have a BIG rhs, which will now be dup'd at every occurrenc of x. -Evne RHSs labelled InlineMe aren't caught here, because there might be +Even RHSs labelled InlineMe aren't caught here, because there might be no benefit from inlining at the call site. [Sept 01] Don't unconditionally inline a top-level thing, because that @@ -764,10 +749,11 @@ activeInline env id where prag = idInlinePragma id -activeRule :: SimplEnv -> Maybe (Activation -> Bool) +activeRule :: DynFlags -> SimplEnv -> Maybe (Activation -> Bool) -- Nothing => No rules at all -activeRule env - | opt_RulesOff = Nothing +activeRule dflags env + | not (dopt Opt_RewriteRules dflags) + = Nothing -- Rewriting is off | otherwise = case getMode env of SimplGently -> Just isAlwaysActive @@ -777,7 +763,7 @@ 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} %************************************************************************ @@ -792,10 +778,22 @@ mkLam :: [OutBndr] -> OutExpr -> SimplM OutExpr -- a) eta reduction, if that gives a trivial expression -- b) eta expansion [only if there are some value lambdas] +mkLam [] body + = return body mkLam bndrs body = do { dflags <- getDOptsSmpl ; mkLam' dflags bndrs body } where + mkLam' :: DynFlags -> [OutBndr] -> OutExpr -> SimplM OutExpr + mkLam' dflags bndrs (Cast body co) + | not (any bad bndrs) + -- Note [Casts and lambdas] + = do { lam <- mkLam' dflags bndrs body + ; return (mkCoerce (mkPiTypes bndrs co) lam) } + where + co_vars = tyVarsOfType co + bad bndr = isCoVar bndr && bndr `elemVarSet` co_vars + mkLam' dflags bndrs body | dopt Opt_DoEtaReduction dflags, Just etad_lam <- tryEtaReduce bndrs body @@ -811,6 +809,38 @@ mkLam bndrs body = returnSmpl (mkLams bndrs body) \end{code} +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. + +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: + \x. e `cast` co ===> (\x. e) `cast` (tx -> co) + /\a. e `cast` co ===> (/\a. e) `cast` (/\a. co) + /\g. e `cast` co ===> (/\g. e) `cast` (/\g. co) + (if not (g `in` co)) + +Notice that it works regardless of 'e'. Originally it worked only +if 'e' was itself a lambda, but in some cases that resulted in +fruitless iteration in the simplifier. A good example was when +compiling Text.ParserCombinators.ReadPrec, where we had a definition +like (\x. Get `cast` g) +where Get is a constructor with nonzero arity. Then mkLam eta-expanded +the Get, and the next iteration eta-reduced it, and then eta-expanded +it again. + +Note also the side condition for the case of coercion binders. +It does not make sense to transform + /\g. e `cast` g ==> (/\g.e) `cast` (/\g.g) +because the latter is not well-kinded. + -- c) floating lets out through big lambdas -- [only if all tyvar lambdas, and only if this lambda -- is the RHS of a let] @@ -829,48 +859,90 @@ mkLam bndrs body %************************************************************************ %* * -\subsection{Eta expansion and reduction} + Eta reduction %* * %************************************************************************ -We try for eta reduction here, but *only* if we get all the -way to an exprIsTrivial expression. -We don't want to remove extra lambdas unless we are going -to avoid allocating this thing altogether +Note [Eta reduction conditions] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +We try for eta reduction here, but *only* if we get all the way to an +trivial expression. We don't want to remove extra lambdas unless we +are going to avoid allocating this thing altogether. + +There are some particularly delicate points here: + +* Eta reduction is not valid in general: + \x. bot /= bot + This matters, partly for old-fashioned correctness reasons but, + worse, getting it wrong can yield a seg fault. Consider + f = \x.f x + h y = case (case y of { True -> f `seq` True; False -> False }) of + True -> ...; False -> ... + + If we (unsoundly) eta-reduce f to get f=f, the strictness analyser + says f=bottom, and replaces the (f `seq` True) with just + (f `cast` unsafe-co). BUT, as thing stand, 'f' got arity 1, and it + *keeps* arity 1 (perhaps also wrongly). So CorePrep eta-expands + the definition again, so that it does not termninate after all. + Result: seg-fault because the boolean case actually gets a function value. + See Trac #1947. + + So it's important to to the right thing. + +* We need to be careful if we just look at f's arity. Currently (Dec07), + f's arity is visible in its own RHS (see Note [Arity robustness] in + SimplEnv) so we must *not* trust the arity when checking that 'f' is + a value. Instead, look at the unfolding. + + However for GlobalIds we can look at the arity; and for primops we + must, since they have no unfolding. + +* Regardless of whether 'f' is a vlaue, we always want to + reduce (/\a -> f a) to f + This came up in a RULE: foldr (build (/\a -> g a)) + did not match foldr (build (/\b -> ...something complex...)) + The type checker can insert these eta-expanded versions, + with both type and dictionary lambdas; hence the slightly + ad-hoc isDictId + +These delicacies are why we don't use exprIsTrivial and exprIsHNF here. +Alas. \begin{code} tryEtaReduce :: [OutBndr] -> OutExpr -> Maybe OutExpr tryEtaReduce bndrs body - -- We don't use CoreUtils.etaReduce, because we can be more - -- efficient here: - -- (a) we already have the binders - -- (b) we can do the triviality test before computing the free vars = go (reverse bndrs) body where go (b : bs) (App fun arg) | ok_arg b arg = go bs fun -- Loop round go [] fun | ok_fun fun = Just fun -- Success! go _ _ = Nothing -- Failure! - ok_fun fun = exprIsTrivial fun - && not (any (`elemVarSet` (exprFreeVars fun)) bndrs) - && (exprIsHNF fun || all ok_lam bndrs) + -- Note [Eta reduction conditions] + ok_fun (App fun (Type ty)) + | not (any (`elemVarSet` tyVarsOfType ty) bndrs) + = ok_fun fun + ok_fun (Var fun_id) + = not (fun_id `elem` bndrs) + && (ok_fun_id fun_id || all ok_lam bndrs) + ok_fun _fun = False + + ok_fun_id fun + | isLocalId fun = isEvaldUnfolding (idUnfolding fun) + | isDataConWorkId fun = True + | isGlobalId fun = idArity fun > 0 + ok_lam v = isTyVar v || isDictId v - -- The exprIsHNF is because eta reduction is not - -- valid in general: \x. bot /= bot - -- So we need to be sure that the "fun" is a value. - -- - -- However, we always want to reduce (/\a -> f a) to f - -- This came up in a RULE: foldr (build (/\a -> g a)) - -- did not match foldr (build (/\b -> ...something complex...)) - -- The type checker can insert these eta-expanded versions, - -- with both type and dictionary lambdas; hence the slightly - -- ad-hoc isDictTy ok_arg b arg = varToCoreExpr b `cheapEqExpr` arg \end{code} - Try eta expansion for RHSs +%************************************************************************ +%* * + Eta expansion +%* * +%************************************************************************ + We go for: f = \x1..xn -> N ==> f = \x1..xn y1..ym -> N y1..ym @@ -885,6 +957,16 @@ where (in both cases) * N is a NORMAL FORM (i.e. no redexes anywhere) wanting a suitable number of extra args. +The biggest reason for doing this is for cases like + + f = \x -> case x of + True -> \y -> e1 + False -> \y -> e2 + +Here we want to get the lambdas together. A good exmaple is the nofib +program fibheaps, which gets 25% more allocation if you don't do this +eta-expansion. + We may have to sandwich some coerces between the lambdas to make the types work. exprEtaExpandArity looks through coerces when computing arity; and etaExpand adds the coerces as necessary when @@ -907,8 +989,35 @@ tryEtaExpansion dflags body %* * %************************************************************************ -tryRhsTyLam tries this transformation, when the big lambda appears as -the RHS of a let(rec) binding: +Note [Floating and type abstraction] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Consider this: + x = /\a. C e1 e2 +We'd like to float this to + y1 = /\a. e1 + y2 = /\a. e2 + x = /\a. C (y1 a) (y2 a) +for the usual reasons: we want to inline x rather vigorously. + +You may think that this kind of thing is rare. But in some programs it is +common. For example, if you do closure conversion you might get: + + data a :-> b = forall e. (e -> a -> b) :$ e + + f_cc :: forall a. a :-> a + f_cc = /\a. (\e. id a) :$ () + +Now we really want to inline that f_cc thing so that the +construction of the closure goes away. + +So I have elaborated simplLazyBind to understand right-hand sides that look +like + /\ a1..an. body + +and treat them specially. The real work is done in SimplUtils.abstractFloats, +but there is quite a bit of plumbing in simplLazyBind as well. + +The same transformation is good when there are lets in the body: /\abc -> let(rec) x = e in b ==> @@ -930,25 +1039,6 @@ let-floating. This optimisation is CRUCIAL in eliminating the junk introduced by desugaring mutually recursive definitions. Don't eliminate it lightly! -So far as the implementation is concerned: - - Invariant: go F e = /\tvs -> F e - - Equalities: - go F (Let x=e in b) - = Let x' = /\tvs -> F e - in - go G b - where - G = F . Let x = x' tvs - - go F (Letrec xi=ei in b) - = Letrec {xi' = /\tvs -> G ei} - in - go G b - where - G = F . Let {xi = xi' tvs} - [May 1999] If we do this transformation *regardless* then we can end up with some pretty silly stuff. For example, @@ -970,43 +1060,34 @@ and is of the form If we abstract this wrt the tyvar we then can't do the case inline as we would normally do. +That's why the whole transformation is part of the same process that +floats let-bindings and constructor arguments out of RHSs. In particular, +it is guarded by the doFloatFromRhs call in simplLazyBind. -\begin{code} -{- Trying to do this in full laziness - -tryRhsTyLam :: SimplEnv -> [OutTyVar] -> OutExpr -> SimplM FloatsWithExpr --- Call ensures that all the binders are type variables - -tryRhsTyLam env tyvars body -- Only does something if there's a let - | not (all isTyVar tyvars) - || not (worth_it body) -- inside a type lambda, - = returnSmpl (emptyFloats env, body) -- and a WHNF inside that - - | otherwise - = go env (\x -> x) body +\begin{code} +abstractFloats :: [OutTyVar] -> SimplEnv -> OutExpr -> SimplM ([OutBind], OutExpr) +abstractFloats main_tvs body_env body + = ASSERT( notNull body_floats ) + do { (subst, float_binds) <- mapAccumLSmpl abstract empty_subst body_floats + ; return (float_binds, CoreSubst.substExpr subst body) } where - worth_it e@(Let _ _) = whnf_in_middle e - worth_it e = False - - whnf_in_middle (Let (NonRec x rhs) e) | isUnLiftedType (idType x) = False - whnf_in_middle (Let _ e) = whnf_in_middle e - whnf_in_middle e = exprIsCheap e - - main_tyvar_set = mkVarSet tyvars - - go env fn (Let bind@(NonRec var rhs) body) - | exprIsTrivial rhs - = go env (fn . Let bind) body - - go env fn (Let (NonRec var rhs) body) - = mk_poly tyvars_here var `thenSmpl` \ (var', rhs') -> - addAuxiliaryBind env (NonRec var' (mkLams tyvars_here (fn rhs))) $ \ env -> - go env (fn . Let (mk_silly_bind var rhs')) body - + main_tv_set = mkVarSet main_tvs + body_floats = getFloats body_env + empty_subst = CoreSubst.mkEmptySubst (seInScope body_env) + + abstract :: CoreSubst.Subst -> OutBind -> SimplM (CoreSubst.Subst, OutBind) + abstract subst (NonRec id rhs) + = do { (poly_id, poly_app) <- mk_poly tvs_here id + ; let poly_rhs = mkLams tvs_here rhs' + subst' = CoreSubst.extendIdSubst subst id poly_app + ; return (subst', (NonRec poly_id poly_rhs)) } where - - tyvars_here = varSetElems (main_tyvar_set `intersectVarSet` exprSomeFreeVars isTyVar rhs) + rhs' = CoreSubst.substExpr subst rhs + tvs_here | any isCoVar main_tvs = main_tvs -- Note [Abstract over coercions] + | otherwise + = varSetElems (main_tv_set `intersectVarSet` exprSomeFreeVars isTyVar rhs') + -- Abstract only over the type variables free in the rhs -- wrt which the new binding is abstracted. But the naive -- approach of abstract wrt the tyvars free in the Id's type @@ -1023,28 +1104,34 @@ tryRhsTyLam env tyvars body -- Only does something if there's a let -- abstracting wrt *all* the tyvars. We'll see if that -- gives rise to problems. SLPJ June 98 - go env fn (Let (Rec prs) body) - = mapAndUnzipSmpl (mk_poly tyvars_here) vars `thenSmpl` \ (vars', rhss') -> - let - gn body = fn (foldr Let body (zipWith mk_silly_bind vars rhss')) - pairs = vars' `zip` [mkLams tyvars_here (gn rhs) | rhs <- rhss] - in - addAuxiliaryBind env (Rec pairs) $ \ env -> - go env gn body + abstract subst (Rec prs) + = do { (poly_ids, poly_apps) <- mapAndUnzipSmpl (mk_poly tvs_here) ids + ; let subst' = CoreSubst.extendSubstList subst (ids `zip` poly_apps) + poly_rhss = [mkLams tvs_here (CoreSubst.substExpr subst' rhs) | rhs <- rhss] + ; return (subst', Rec (poly_ids `zip` poly_rhss)) } where - (vars,rhss) = unzip prs - tyvars_here = varSetElems (main_tyvar_set `intersectVarSet` exprsSomeFreeVars isTyVar (map snd prs)) - -- See notes with tyvars_here above - - go env fn body = returnSmpl (emptyFloats env, fn body) - - mk_poly tyvars_here var - = getUniqueSmpl `thenSmpl` \ uniq -> - let - poly_name = setNameUnique (idName var) uniq -- Keep same name - poly_ty = mkForAllTys tyvars_here (idType var) -- But new type of course - poly_id = mkLocalId poly_name poly_ty - + (ids,rhss) = unzip prs + -- For a recursive group, it's a bit of a pain to work out the minimal + -- set of tyvars over which to abstract: + -- /\ a b c. let x = ...a... in + -- letrec { p = ...x...q... + -- q = .....p...b... } in + -- ... + -- Since 'x' is abstracted over 'a', the {p,q} group must be abstracted + -- over 'a' (because x is replaced by (poly_x a)) as well as 'b'. + -- Since it's a pain, we just use the whole set, which is always safe + -- + -- If you ever want to be more selective, remember this bizarre case too: + -- x::a = x + -- Here, we must abstract 'x' over 'a'. + tvs_here = main_tvs + + mk_poly tvs_here var + = do { uniq <- getUniqueSmpl + ; let poly_name = setNameUnique (idName var) uniq -- Keep same name + poly_ty = mkForAllTys tvs_here (idType var) -- But new type of course + poly_id = mkLocalId poly_name poly_ty + ; return (poly_id, mkTyApps (Var poly_id) (mkTyVarTys tvs_here)) } -- In the olden days, it was crucial to copy the occInfo of the original var, -- because we were looking at occurrence-analysed but as yet unsimplified code! -- In particular, we mustn't lose the loop breakers. BUT NOW we are looking @@ -1057,10 +1144,17 @@ tryRhsTyLam env tyvars body -- Only does something if there's a let -- where x* has an INLINE prag on it. Now, once x* is inlined, -- the occurrences of x' will be just the occurrences originally -- pinned on x. - in - returnSmpl (poly_id, mkTyApps (Var poly_id) (mkTyVarTys tyvars_here)) +\end{code} + +Note [Abstract over coercions] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +If a coercion variable (g :: a ~ Int) is free in the RHS, then so is the +type variable a. Rather than sort this mess out, we simply bale out and abstract +wrt all the type variables if any of them are coercion variables. + + +Historical note: if you use let-bindings instead of a substitution, beware of this: - mk_silly_bind var rhs = NonRec var (Note InlineMe rhs) -- Suppose we start with: -- -- x = /\ a -> let g = G in E @@ -1080,31 +1174,14 @@ tryRhsTyLam env tyvars body -- Only does something if there's a let -- Solution: put an INLINE note on g's RHS, so that poly_g seems -- to appear many times. (NB: mkInlineMe eliminates -- such notes on trivial RHSs, so do it manually.) --} -\end{code} %************************************************************************ %* * -\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 @@ -1159,68 +1236,161 @@ 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 :: SimplEnv -> OutExpr -> OutId -> [InAlt] -> SimplM ([AltCon], [InAlt]) +prepareAlts env 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 non-DEFAULT branch in this case expression. + + ; default_alts <- prepareDefault dflags env case_bndr' mb_tc_app + imposs_deflt_cons maybe_deflt + + ; let trimmed_alts = filterOut impossible_alt alts_wo_default + merged_alts = mergeAlts trimmed_alts default_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 interleaves the alternatives in the right order + + ; 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 -> [] + + impossible_alt :: CoreAlt -> Bool + impossible_alt (con, _, _) | con `elem` imposs_cons = True + impossible_alt (DataAlt con, _, _) = dataConCannotMatch inst_tys con + impossible_alt alt = False + + -------------------------------------------------- -- 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 + -> SimplEnv + -> 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 env outer_bndr bndr_ty imposs_cons (Just deflt_rhs) + | dopt Opt_CaseMerge dflags + , Case (Var inner_scrut_var) inner_bndr _ inner_alts <- deflt_rhs + , DoneId inner_scrut_var' <- substId env inner_scrut_var + -- Remember, inner_scrut_var is an InId, but outer_bndr is an OutId + , inner_scrut_var' == outer_bndr + -- NB: the substId means that if the outer scrutinee was a + -- variable, and inner scrutinee is the same variable, + -- then inner_scrut_var' will be outer_bndr + -- via the magic of simplCaseBinder + = 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, + not (con `elem` imposs_cons) ] + -- NB: filter out any imposs_cons. Example: + -- case x of + -- A -> e1 + -- DEFAULT -> case x of + -- A -> e2 + -- B -> e3 + -- When we merge, we must ensure that e1 takes + -- precedence over e2 as the value for A! + } + -- 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 -- in munge_rhs may put a case into the DEFAULT branch! - where - -- We are scrutinising the same variable if it's - -- the outer case-binder, or if the outer case scrutinises a variable - -- (and it's the same). Testing both allows us not to replace the - -- outer scrut-var with the outer case-binder (Simplify.simplCaseBinder). - scruting_same_var = case scrut of - 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 env 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 + impossible con = con `elem` imposs_data_cons || dataConCannotMatch inst_tys con + = case filterOut impossible 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 env case_bndr bndr_ty imposs_cons (Just deflt_rhs) + = return [(DEFAULT, [], deflt_rhs)] + +prepareDefault dflags env 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 @@ -1233,192 +1403,41 @@ 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) $ - return (mkApps (Var eRROR_ID) +mkCase scrut case_bndr ty [] + = pprTrace "mkCase: null alts" (ppr case_bndr <+> ppr scrut) $ + return (mkApps (Var rUNTIME_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_cast scrut) where - identity_alt (con, args, rhs) = de_cast rhs `cheapEqExpr` mk_id_rhs con args + identity_alt (con, args, rhs) = check_eq con args (de_cast rhs) - mk_id_rhs (DataAlt con) args = mkConApp con (arg_tys ++ varsToCoreExprs args) - mk_id_rhs (LitAlt lit) _ = Lit lit - mk_id_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)) @@ -1443,7 +1462,7 @@ mkCase1 scrut case_bndr ty alts -- Identity case -------------------------------------------------- -- 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}