X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2FsimplCore%2FSimplUtils.lhs;h=6ce29a2562755448a27d7761e4b411933f6b15cb;hb=41676ec859d1332d4c4ec56c9ea8b0aa9cedf606;hp=9bc78267c09003cd12ddde3c39057fe68e444af0;hpb=58e45ee86bbda3f24a4caf41c0aea7a6b787367e;p=ghc-hetmet.git diff --git a/compiler/simplCore/SimplUtils.lhs b/compiler/simplCore/SimplUtils.lhs index 9bc7826..6ce29a2 100644 --- a/compiler/simplCore/SimplUtils.lhs +++ b/compiler/simplCore/SimplUtils.lhs @@ -49,8 +49,7 @@ import Id import Var ( isCoVar ) import NewDemand import SimplMonad -import Type ( Type, funArgTy, mkForAllTys, mkTyVarTys, - splitTyConApp_maybe, tyConAppArgs ) +import Type hiding( substTy ) import TyCon import DataCon import Unify ( dataConCannotMatch ) @@ -96,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 @@ -157,10 +154,10 @@ 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 @@ -303,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. @@ -419,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 @@ -427,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 @@ -436,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} @@ -591,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 @@ -844,12 +785,14 @@ mkLam bndrs body ; mkLam' dflags bndrs body } where mkLam' :: DynFlags -> [OutBndr] -> OutExpr -> SimplM OutExpr - mkLam' dflags bndrs (Cast body@(Lam _ _) co) + mkLam' dflags bndrs (Cast body co) + | not (any bad bndrs) -- Note [Casts and lambdas] - = do { lam <- mkLam' dflags (bndrs ++ bndrs') body' + = do { lam <- mkLam' dflags bndrs body ; return (mkCoerce (mkPiTypes bndrs co) lam) } - where - (bndrs',body') = collectBinders body + where + co_vars = tyVarsOfType co + bad bndr = isCoVar bndr && bndr `elemVarSet` co_vars mkLam' dflags bndrs body | dopt Opt_DoEtaReduction dflags, @@ -877,9 +820,26 @@ 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. - +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 @@ -899,48 +859,90 @@ and cancel with some other cast. %************************************************************************ %* * -\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 @@ -955,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