\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, prepareAlts, bindCaseBndr,
-- The continuation type
SimplCont(..), DupFlag(..), LetRhsFlag(..),
contIsDupable, contResultType, contIsTrivial, contArgs, dropArgs,
- countValArgs, countArgs,
+ countValArgs, countArgs, splitInlineCont,
mkBoringStop, mkLazyArgStop, mkRhsStop, contIsRhsOrArg,
interestingCallContext, interestingArgContext,
- interestingArg, mkArgInfo
+ interestingArg, mkArgInfo,
+
+ abstractFloats
) where
#include "HsVersions.h"
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 )
mkRhsStop :: OutType -> SimplCont
mkRhsStop ty = Stop ty AnRhs (canUpdateInPlace ty)
-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
-------------------
contIsTrivial :: SimplCont -> Bool
-contIsTrivial (Stop _ _ _) = True
+contIsTrivial (Stop {}) = True
contIsTrivial (ApplyTo _ (Type _) _ cont) = contIsTrivial cont
contIsTrivial (CoerceIt _ cont) = contIsTrivial cont
contIsTrivial other = False
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}
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
-- 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@(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,
(\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
%* *
%************************************************************************
-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
==>
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,
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
-- 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
-- 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
-- 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}
%************************************************************************
%* *
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
+prepareAlts :: SimplEnv -> OutExpr -> OutId -> [InAlt] -> SimplM ([AltCon], [InAlt])
+prepareAlts env scrut case_bndr' alts
= do { dflags <- getDOptsSmpl
; alts <- combineIdenticalAlts case_bndr' alts
-- EITHER by the context,
-- OR by a non-DEFAULT branch in this case expression.
- ; default_alts <- prepareDefault dflags scrut case_bndr' mb_tc_app
+ ; default_alts <- prepareDefault dflags env case_bndr' mb_tc_app
imposs_deflt_cons maybe_deflt
; let trimmed_alts = filterOut impossible_alt alts_wo_default
-- Prepare the default alternative
-------------------------------------------------------------------------
prepareDefault :: DynFlags
- -> OutExpr -- Scrutinee
+ -> 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
-- 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)
+prepareDefault dflags env 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
+ , 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
-- 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
+
--------- Fill in known constructor -----------
-prepareDefault dflags scrut case_bndr (Just (tycon, inst_tys)) imposs_cons (Just deflt_rhs)
+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.
two_or_more -> return [(DEFAULT, [], deflt_rhs)]
--------- Catch-all cases -----------
-prepareDefault dflags scrut case_bndr bndr_ty imposs_cons (Just deflt_rhs)
+prepareDefault dflags env case_bndr bndr_ty imposs_cons (Just deflt_rhs)
= return [(DEFAULT, [], deflt_rhs)]
-prepareDefault dflags scrut case_bndr bndr_ty imposs_cons Nothing
+prepareDefault dflags env case_bndr bndr_ty imposs_cons Nothing
= return [] -- No default branch
\end{code}
projects / ghc-hetmet.git / blobdiff