\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,
SimplCont(..), DupFlag(..), ArgInfo(..),
contIsDupable, contResultType, contIsTrivial, contArgs, dropArgs,
countValArgs, countArgs, splitInlineCont,
- mkBoringStop, mkLazyArgStop, mkRhsStop, contIsRhsOrArg,
+ mkBoringStop, mkLazyArgStop, contIsRhsOrArg,
interestingCallContext, interestingArgContext,
interestingArg, mkArgInfo,
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 hiding( substTy )
+import Coercion ( coercionKind )
import TyCon
-import DataCon
import Unify ( dataConCannotMatch )
import VarSet
import BasicTypes
\begin{code}
data SimplCont
= Stop -- An empty context, or hole, []
- OutType -- Type of the result
CallCtxt -- True <=> There is something interesting about
-- the context, and hence the inliner
-- should be a bit keener (see interestingCallContext)
SimplCont
| StrictArg -- e C
- OutExpr OutType -- e and its type
+ OutExpr -- e
CallCtxt -- Whether *this* argument position is interesting
ArgInfo -- Whether the function at the head of e has rules, etc
SimplCont -- plus strictness flags for *further* args
}
instance Outputable SimplCont where
- ppr (Stop ty _) = ptext SLIT("Stop") <+> ppr ty
- ppr (ApplyTo dup arg se cont) = ((ptext SLIT("ApplyTo") <+> ppr dup <+> pprParendExpr arg)
+ ppr (Stop interesting) = ptext (sLit "Stop") <> brackets (ppr interesting)
+ ppr (ApplyTo dup arg _ 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) $$
+ 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 _ cont) = (ptext (sLit "Select") <+> ppr dup <+> ppr bndr) $$
(nest 4 (ppr alts)) $$ ppr cont
- ppr (CoerceIt co cont) = (ptext SLIT("CoerceIt") <+> ppr co) $$ ppr cont
+ ppr (CoerceIt co cont) = (ptext (sLit "CoerceIt") <+> ppr co) $$ ppr cont
data DupFlag = OkToDup | NoDup
instance Outputable DupFlag where
- ppr OkToDup = ptext SLIT("ok")
- ppr NoDup = ptext SLIT("nodup")
+ ppr OkToDup = ptext (sLit "ok")
+ ppr NoDup = ptext (sLit "nodup")
-------------------
-mkBoringStop :: OutType -> SimplCont
-mkBoringStop ty = Stop ty BoringCtxt
-
-mkLazyArgStop :: OutType -> CallCtxt -> SimplCont
-mkLazyArgStop ty cci = Stop ty cci
+mkBoringStop :: SimplCont
+mkBoringStop = Stop BoringCtxt
-mkRhsStop :: OutType -> SimplCont
-mkRhsStop ty = Stop ty BoringCtxt
+mkLazyArgStop :: CallCtxt -> SimplCont
+mkLazyArgStop cci = Stop cci
-------------------
-contIsRhsOrArg (Stop {}) = True
-contIsRhsOrArg (StrictBind {}) = True
-contIsRhsOrArg (StrictArg {}) = True
-contIsRhsOrArg other = False
+contIsRhsOrArg :: SimplCont -> Bool
+contIsRhsOrArg (Stop {}) = True
+contIsRhsOrArg (StrictBind {}) = True
+contIsRhsOrArg (StrictArg {}) = True
+contIsRhsOrArg _ = False
-------------------
contIsDupable :: SimplCont -> Bool
-contIsDupable (Stop {}) = True
+contIsDupable (Stop {}) = True
contIsDupable (ApplyTo OkToDup _ _ _) = True
contIsDupable (Select OkToDup _ _ _ _) = True
contIsDupable (CoerceIt _ cont) = contIsDupable cont
-contIsDupable other = False
+contIsDupable _ = False
-------------------
contIsTrivial :: SimplCont -> Bool
-contIsTrivial (Stop {}) = True
+contIsTrivial (Stop {}) = True
contIsTrivial (ApplyTo _ (Type _) _ cont) = contIsTrivial cont
-contIsTrivial (CoerceIt _ cont) = contIsTrivial cont
-contIsTrivial other = False
+contIsTrivial (CoerceIt _ cont) = contIsTrivial cont
+contIsTrivial _ = False
-------------------
-contResultType :: SimplCont -> OutType
-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
+contResultType :: SimplEnv -> OutType -> SimplCont -> OutType
+contResultType env ty cont
+ = go cont ty
+ where
+ subst_ty se ty = substTy (se `setInScope` env) ty
+
+ go (Stop {}) ty = ty
+ go (CoerceIt co cont) _ = go cont (snd (coercionKind co))
+ go (StrictBind _ bs body se cont) _ = go cont (subst_ty se (exprType (mkLams bs body)))
+ go (StrictArg fn _ _ cont) _ = go cont (funResultTy (exprType fn))
+ go (Select _ _ alts se cont) _ = go cont (subst_ty se (coreAltsType alts))
+ go (ApplyTo _ arg se cont) ty = go cont (apply_to_arg ty arg se)
+
+ apply_to_arg ty (Type ty_arg) se = applyTy ty (subst_ty se ty_arg)
+ apply_to_arg ty _ _ = funResultTy ty
-------------------
countValArgs :: SimplCont -> Int
-countValArgs (ApplyTo _ (Type ty) se cont) = countValArgs cont
-countValArgs (ApplyTo _ val_arg se cont) = 1 + countValArgs cont
-countValArgs other = 0
+countValArgs (ApplyTo _ (Type _) _ cont) = countValArgs cont
+countValArgs (ApplyTo _ _ _ cont) = 1 + countValArgs cont
+countValArgs _ = 0
countArgs :: SimplCont -> Int
-countArgs (ApplyTo _ arg se cont) = 1 + countArgs cont
-countArgs other = 0
+countArgs (ApplyTo _ _ _ cont) = 1 + countArgs cont
+countArgs _ = 0
contArgs :: SimplCont -> ([OutExpr], SimplCont)
-- Uses substitution to turn each arg into an OutExpr
-- 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
+ | Just (c1, c2) <- splitInlineCont c = Just (ApplyTo dup (Type ty) se c1, c2)
+splitInlineCont cont@(Stop {}) = Just (mkBoringStop, cont)
+splitInlineCont cont@(StrictBind {}) = Just (mkBoringStop, cont)
+splitInlineCont cont@(StrictArg {}) = Just (mkBoringStop, cont)
+splitInlineCont _ = Nothing
\end{code}
-- Lit lit -> True
-- _ -> False
-interestingArg other = True
+interestingArg _ = True
-- Consider let x = 3 in f x
-- The substitution will contain (x -> ContEx 3), and we want to
-- to say that x is an interesting argument.
-- seen (coerce f) x, where f has an INLINE prag,
-- So we have to give some motivation for inlining it
- interesting (StrictArg _ _ cci _ _) = cci
+ interesting (StrictArg _ cci _ _) = cci
interesting (StrictBind {}) = BoringCtxt
- interesting (Stop ty cci) = cci
+ interesting (Stop cci) = cci
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
-> ArgInfo
mkArgInfo fun n_val_args call_cont
+ | n_val_args < idArity fun -- Note [Unsaturated functions]
+ = ArgInfo { ai_rules = False
+ , ai_strs = vanilla_stricts
+ , ai_discs = vanilla_discounts }
+ | otherwise
= ArgInfo { ai_rules = interestingArgContext fun call_cont
- , ai_strs = arg_stricts
+ , ai_strs = add_type_str (idType fun) arg_stricts
, ai_discs = arg_discounts }
where
vanilla_discounts, arg_discounts :: [Int]
arg_discounts = case idUnfolding fun of
CoreUnfolding _ _ _ _ (UnfoldIfGoodArgs _ discounts _ _)
-> discounts ++ vanilla_discounts
- other -> vanilla_discounts
+ _ -> vanilla_discounts
vanilla_stricts, arg_stricts :: [Bool]
vanilla_stricts = repeat False
map isStrictDmd demands -- Finite => result is bottom
else
map isStrictDmd demands ++ vanilla_stricts
-
- other -> vanilla_stricts -- Not enough args, or no strictness
+ | otherwise
+ -> WARN( True, text "More demands than arity" <+> ppr fun <+> ppr (idArity fun)
+ <+> ppr n_val_args <+> ppr demands )
+ vanilla_stricts -- Not enough args, or no strictness
+
+ add_type_str :: Type -> [Bool] -> [Bool]
+ -- If the function arg types are strict, record that in the 'strictness bits'
+ -- No need to instantiate because unboxed types (which dominate the strict
+ -- types) can't instantiate type variables.
+ -- add_type_str is done repeatedly (for each call); might be better
+ -- once-for-all in the function
+ -- But beware primops/datacons with no strictness
+ add_type_str _ [] = []
+ add_type_str fun_ty strs -- Look through foralls
+ | Just (_, fun_ty') <- splitForAllTy_maybe fun_ty -- Includes coercions
+ = add_type_str fun_ty' strs
+ add_type_str fun_ty (str:strs) -- Add strict-type info
+ | Just (arg_ty, fun_ty') <- splitFunTy_maybe fun_ty
+ = (str || isStrictType arg_ty) : add_type_str fun_ty' strs
+ add_type_str _ strs
+ = strs
+
+{- Note [Unsaturated functions]
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Consider (test eyeball/inline4)
+ x = a:as
+ y = f x
+where f has arity 2. Then we do not want to inline 'x', because
+it'll just be floated out again. Even if f has lots of discounts
+on its first argument -- it must be saturated for these to kick in
+-}
interestingArgContext :: Id -> SimplCont -> Bool
-- If the argument has form (f x y), where x,y are boring,
interestingArgContext fn call_cont
= idHasRules fn || go call_cont
where
- go (Select {}) = False
- go (ApplyTo {}) = False
- go (StrictArg _ _ cci _ _) = interesting cci
- go (StrictBind {}) = False -- ??
- go (CoerceIt _ c) = go c
- go (Stop _ cci) = interesting cci
+ go (Select {}) = False
+ go (ApplyTo {}) = False
+ go (StrictArg _ cci _ _) = interesting cci
+ go (StrictBind {}) = False -- ??
+ go (CoerceIt _ c) = go c
+ go (Stop cci) = interesting cci
interesting (ArgCtxt rules _) = rules
- interesting other = False
+ interesting _ = False
\end{code}
| otherwise = case idOccInfo bndr of
IAmDead -> True -- Happens in ((\x.1) v)
OneOcc in_lam True int_cxt -> try_once in_lam int_cxt
- other -> False
+ _ -> False
where
phase = getMode env
active = case phase of
-- canInlineInLam => free vars of rhs are (Once in_lam) or Many,
-- so substituting rhs inside a lambda doesn't change the occ info.
-- Sadly, not quite the same as exprIsHNF.
- canInlineInLam (Lit l) = True
+ canInlineInLam (Lit _) = True
canInlineInLam (Lam b e) = isRuntimeVar b || canInlineInLam e
canInlineInLam (Note _ e) = canInlineInLam e
canInlineInLam _ = False
early_phase = case phase of
SimplPhase 0 _ -> False
- other -> True
+ _ -> True
-- If we don't have this early_phase test, consider
-- x = length [1,2,3]
-- The full laziness pass carefully floats all the cons cells to
-> Bool
postInlineUnconditionally env top_lvl bndr occ_info rhs unfolding
| not active = False
- | isLoopBreaker occ_info = False -- If it's a loop-breaker of any kind, dont' inline
+ | isLoopBreaker occ_info = False -- If it's a loop-breaker of any kind, don't inline
-- because it might be referred to "earlier"
| isExportedId bndr = False
| exprIsTrivial rhs = True
-- 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
+ 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
--
-- 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
+ _ -> False
-- Here's an example that we don't handle well:
-- let f = if b then Left (\x.BIG) else Right (\y.BIG)
= case getMode env of
SimplGently -> False
-- No inlining at all when doing gentle stuff,
- -- except for local things that occur once
+ -- except for local things that occur once (pre/postInlineUnconditionally)
-- The reason is that too little clean-up happens if you
-- don't inline use-once things. Also a bit of inlining is *good* for
-- full laziness; it can expose constant sub-expressions.
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
+* Regardless of whether 'f' is a value, 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...))
+ 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
| isLocalId fun = isEvaldUnfolding (idUnfolding fun)
| isDataConWorkId fun = True
| isGlobalId fun = idArity fun > 0
+ | otherwise = panic "tryEtaReduce/ok_fun_id"
ok_lam v = isTyVar v || isDictId v
We'd like to float this to
y1 = /\a. e1
y2 = /\a. e2
- x = /\a. C (y1 a) (y2 a)
+ 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
= do { uniq <- getUniqueM
; 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
+ poly_id = transferPolyIdInfo var $ -- Note [transferPolyIdInfo] in Id.lhs
+ 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!
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
+ impossible_alt _ = False
--------------------------------------------------
--------------------------------------------------
combineIdenticalAlts :: OutId -> [InAlt] -> SimplM [InAlt]
-combineIdenticalAlts case_bndr alts@((con1,bndrs1,rhs1) : con_alts)
+combineIdenticalAlts case_bndr ((_con1,bndrs1,rhs1) : con_alts)
| all isDeadBinder bndrs1, -- Remember the default
length filtered_alts < length con_alts -- alternative comes first
-- Also Note [Dead binders]
; return ((DEFAULT, [], rhs1) : filtered_alts) }
where
filtered_alts = filter keep con_alts
- keep (con,bndrs,rhs) = not (all isDeadBinder bndrs && rhs `cheapEqExpr` rhs1)
+ keep (_con,bndrs,rhs) = not (all isDeadBinder bndrs && rhs `cheapEqExpr` rhs1)
-combineIdenticalAlts case_bndr alts = return alts
+combineIdenticalAlts _ alts = return alts
-------------------------------------------------------------------------
-- Prepare the default alternative
-- 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)
+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
--------- Fill in known constructor -----------
-prepareDefault dflags env case_bndr (Just (tycon, inst_tys)) imposs_cons (Just deflt_rhs)
+prepareDefault _ _ 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.
dataConRepInstPat us con inst_tys
; return [(DataAlt con, ex_tvs ++ co_tvs ++ arg_ids, deflt_rhs)] }
- two_or_more -> return [(DEFAULT, [], deflt_rhs)]
+ _ -> return [(DEFAULT, [], deflt_rhs)]
+
+ | debugIsOn, isAlgTyCon tycon, [] <- tyConDataCons tycon
+ = pprTrace "prepareDefault" (ppr case_bndr <+> ppr tycon)
+ -- This can legitimately happen for type families
+ $ return [(DEFAULT, [], deflt_rhs)]
--------- Catch-all cases -----------
-prepareDefault dflags env 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 env case_bndr bndr_ty imposs_cons Nothing
+prepareDefault _dflags _env _case_bndr _bndr_ty _imposs_cons Nothing
= return [] -- No default branch
\end{code}
\begin{code}
-mkCase :: OutExpr -> OutId -> OutType
- -> [OutAlt] -- Increasing order
+mkCase :: OutExpr -> OutId -> [OutAlt] -- Increasing order
-> SimplM OutExpr
--------------------------------------------------
--- 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
-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")])
-
-
---------------------------------------------------
-- 2. Identity case
--------------------------------------------------
-mkCase scrut case_bndr ty alts -- Identity case
+mkCase scrut case_bndr alts -- Identity case
| all identity_alt alts
= do tick (CaseIdentity case_bndr)
return (re_cast scrut)
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
+ check_eq _ _ _ = False
arg_tys = map Type (tyConAppArgs (idType case_bndr))
re_cast scrut = case head alts of
(_,_,Cast _ co) -> Cast scrut co
- other -> scrut
+ _ -> scrut
--------------------------------------------------
-- Catch-all
--------------------------------------------------
-mkCase scrut bndr ty alts = return (Case scrut bndr ty alts)
+mkCase scrut bndr alts = return (Case scrut bndr (coreAltsType alts) alts)
\end{code}
cascade rather nicely.
\begin{code}
+bindCaseBndr :: Id -> CoreExpr -> CoreExpr -> CoreExpr
bindCaseBndr bndr rhs body
| isDeadBinder bndr = body
- | otherwise = bindNonRec bndr rhs body
+ | otherwise = bindNonRec bndr rhs body
\end{code}