-- * Properties of expressions
exprType, coreAltType, coreAltsType,
- exprIsDupable, exprIsTrivial, exprIsCheap, exprIsExpandable,
+ exprIsDupable, exprIsTrivial, exprIsBottom,
+ exprIsCheap, exprIsExpandable, exprIsCheap', CheapAppFun,
exprIsHNF, exprOkForSpeculation, exprIsBig, exprIsConLike,
rhsIsStatic, isCheapApp, isExpandableApp,
-- * Equality
cheapEqExpr, eqExpr, eqExprX,
+ -- * Eta reduction
+ tryEtaReduce,
+
-- * Manipulating data constructors and types
applyTypeToArgs, applyTypeToArg,
dataConOrigInstPat, dataConRepInstPat, dataConRepFSInstPat
import VarEnv
import VarSet
import Name
-import Module
-#if mingw32_TARGET_OS
-import Packages
-#endif
import Literal
import DataCon
import PrimOp
where
ty = exprType rhs
free_tvs = tyVarsOfType ty
- bad_binder b = isTyVar b && b `elemVarSet` free_tvs
+ bad_binder b = isTyCoVar b && b `elemVarSet` free_tvs
coreAltsType :: [CoreAlt] -> Type
-- ^ Returns the type of the first alternative, which should be the same as for all alternatives
we are doing here. It's not too expensive, I think.
\begin{code}
-mkPiType :: Var -> Type -> Type
+mkPiType :: EvVar -> Type -> Type
-- ^ Makes a @(->)@ type or a forall type, depending
-- on whether it is given a type variable or a term variable.
-mkPiTypes :: [Var] -> Type -> Type
+mkPiTypes :: [EvVar] -> Type -> Type
-- ^ 'mkPiType' for multiple type or value arguments
mkPiType v ty
\begin{code}
-- | Wrap the given expression in the coercion, dropping identity coercions and coalescing nested coercions
mkCoerceI :: CoercionI -> CoreExpr -> CoreExpr
-mkCoerceI IdCo e = e
+mkCoerceI (IdCo _) e = e
mkCoerceI (ACo co) e = mkCoerce co e
-- | Wrap the given expression in the coercion safely, coalescing nested coercions
exprIsTrivial _ = False
\end{code}
+exprIsBottom is a very cheap and cheerful function; it may return
+False for bottoming expressions, but it never costs much to ask.
+See also CoreArity.exprBotStrictness_maybe, but that's a bit more
+expensive.
+
+\begin{code}
+exprIsBottom :: CoreExpr -> Bool
+exprIsBottom e
+ = go 0 e
+ where
+ go n (Var v) = isBottomingId v && n >= idArity v
+ go n (App e a) | isTypeArg a = go n e
+ | otherwise = go (n+1) e
+ go n (Note _ e) = go n e
+ go n (Cast e _) = go n e
+ go n (Let _ e) = go n e
+ go _ _ = False
+\end{code}
+
%************************************************************************
%* *
\begin{code}
exprIsDupable :: CoreExpr -> Bool
-exprIsDupable (Type _) = True
-exprIsDupable (Var _) = True
-exprIsDupable (Lit lit) = litIsDupable lit
-exprIsDupable (Note _ e) = exprIsDupable e
-exprIsDupable (Cast e _) = exprIsDupable e
-exprIsDupable expr
- = go expr 0
+exprIsDupable e
+ = isJust (go dupAppSize e)
where
- go (Var _) _ = True
- go (App f a) n_args = n_args < dupAppSize
- && exprIsDupable a
- && go f (n_args+1)
- go _ _ = False
+ go :: Int -> CoreExpr -> Maybe Int
+ go n (Type {}) = Just n
+ go n (Var {}) = decrement n
+ go n (Note _ e) = go n e
+ go n (Cast e _) = go n e
+ go n (App f a) | Just n' <- go n a = go n' f
+ go n (Lit lit) | litIsDupable lit = decrement n
+ go _ _ = Nothing
+
+ decrement :: Int -> Maybe Int
+ decrement 0 = Nothing
+ decrement n = Just (n-1)
dupAppSize :: Int
-dupAppSize = 4 -- Size of application we are prepared to duplicate
+dupAppSize = 8 -- Size of term we are prepared to duplicate
+ -- This is *just* big enough to make test MethSharing
+ -- inline enough join points. Really it should be
+ -- smaller, and could be if we fixed Trac #4960.
\end{code}
%************************************************************************
exprIsExpandable :: CoreExpr -> Bool
exprIsExpandable = exprIsCheap' isExpandableApp -- See Note [CONLIKE pragma] in BasicTypes
-
-exprIsCheap' :: (Id -> Int -> Bool) -> CoreExpr -> Bool
+type CheapAppFun = Id -> Int -> Bool
+exprIsCheap' :: CheapAppFun -> CoreExpr -> Bool
exprIsCheap' _ (Lit _) = True
exprIsCheap' _ (Type _) = True
exprIsCheap' _ (Var _) = True
= go other_expr []
where
-- Accumulate value arguments, then decide
+ go (Cast e _) val_args = go e val_args
go (App f a) val_args | isRuntimeArg a = go f (a:val_args)
| otherwise = go f val_args
go (Var _) [] = True -- Just a type application of a variable
-- (f t1 t2 t3) counts as WHNF
go (Var f) args
- = case idDetails f of
+ = case idDetails f of
RecSelId {} -> go_sel args
ClassOpId {} -> go_sel args
PrimOpId op -> go_primop op args
-- BUT: Take care with (sel d x)! The (sel d) might be cheap, but
-- there's no guarantee that (sel d x) will be too. Hence (n_val_args == 1)
-isCheapApp :: Id -> Int -> Bool
+isCheapApp :: CheapAppFun
isCheapApp fn n_val_args
= isDataConWorkId fn
|| n_val_args < idArity fn
-isExpandableApp :: Id -> Int -> Bool
+isExpandableApp :: CheapAppFun
isExpandableApp fn n_val_args
= isConLikeId fn
|| n_val_args < idArity fn
--
-- * Safe /not/ to evaluate even if normal order would do so
--
+-- It is usually called on arguments of unlifted type, but not always
+-- In particular, Simplify.rebuildCase calls it on lifted types
+-- when a 'case' is a plain 'seq'. See the example in
+-- Note [exprOkForSpeculation: case expressions] below
+--
-- Precisely, it returns @True@ iff:
--
-- * The expression guarantees to terminate,
exprOkForSpeculation :: CoreExpr -> Bool
exprOkForSpeculation (Lit _) = True
exprOkForSpeculation (Type _) = True
- -- Tick boxes are *not* suitable for speculation
-exprOkForSpeculation (Var v) = isUnLiftedType (idType v)
- && not (isTickBoxOp v)
+
+exprOkForSpeculation (Var v)
+ | isTickBoxOp v = False -- Tick boxes are *not* suitable for speculation
+ | otherwise = isUnLiftedType (idType v) -- c.f. the Var case of exprIsHNF
+ || isDataConWorkId v -- Nullary constructors
+ || idArity v > 0 -- Functions
+ || isEvaldUnfolding (idUnfolding v) -- Let-bound values
+
exprOkForSpeculation (Note _ e) = exprOkForSpeculation e
exprOkForSpeculation (Cast e _) = exprOkForSpeculation e
-- Often there is a literal divisor, and this
-- can get rid of a thunk in an inner looop
+ | DataToTagOp <- op -- See Note [dataToTag speculation]
+ = True
+
| otherwise
= primOpOkForSpeculation op &&
all exprOkForSpeculation args
-- A bit conservative: we don't really need
-- to care about lazy arguments, but this is easy
- spec_ok (DFunId new_type) _ = not new_type
+ spec_ok (DFunId _ new_type) _ = not new_type
-- DFuns terminate, unless the dict is implemented with a newtype
-- in which case they may not
Note [exprOkForSpeculation: case expressions]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-
It's always sound for exprOkForSpeculation to return False, and we
don't want it to take too long, so it bales out on complicated-looking
terms. Notably lets, which can be stacked very deeply; and in any
so any lets will have been floated away.
However, we keep going on case-expressions. An example like this one
-showed up in DPH code:
+showed up in DPH code (Trac #3717):
foo :: Int -> Int
foo 0 = 0
foo n = (if n < 5 then 1 else 2) `seq` foo (n-1)
\ (ww :: GHC.Prim.Int#) ->
case ww of ds {
__DEFAULT -> case (case <# ds 5 of _ {
- GHC.Bool.False -> lvl1;
- GHC.Bool.True -> lvl})
+ GHC.Types.False -> lvl1;
+ GHC.Types.True -> lvl})
of _ { __DEFAULT ->
T.$wfoo (GHC.Prim.-# ds_XkE 1) };
0 -> 0
The inner case is redundant, and should be nuked.
+Note [dataToTag speculation]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Is this OK?
+ f x = let v::Int# = dataToTag# x
+ in ...
+We say "yes", even though 'x' may not be evaluated. Reasons
+
+ * dataToTag#'s strictness means that its argument often will be
+ evaluated, but FloatOut makes that temporarily untrue
+ case x of y -> let v = dataToTag# y in ...
+ -->
+ case x of y -> let v = dataToTag# x in ...
+ Note that we look at 'x' instead of 'y' (this is to improve
+ floating in FloatOut). So Lint complains.
+
+ Moreover, it really *might* improve floating to let the
+ v-binding float out
+
+ * CorePrep makes sure dataToTag#'s argument is evaluated, just
+ before code gen. Until then, it's not guaranteed
+
%************************************************************************
%* *
noteSize (CoreNote s) = s `seq` 1 -- hdaume: core annotations
varSize :: Var -> Int
-varSize b | isTyVar b = 1
+varSize b | isTyCoVar b = 1
| otherwise = seqType (idType b) `seq`
megaSeqIdInfo (idInfo b) `seq`
1
= fromIntegral (lookupVarEnv env v `orElse` hashName (idName v))
\end{code}
+
+%************************************************************************
+%* *
+ Eta reduction
+%* *
+%************************************************************************
+
+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.
+
+* Note [Arity care]: 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. Otherwise we will
+ eta-reduce
+ f = \x. f x
+ to
+ f = f
+ Which might change a terminiating program (think (f `seq` e)) to a
+ non-terminating one. So we check for being a loop breaker first.
+
+ 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 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...))
+ The type checker can insert these eta-expanded versions,
+ with both type and dictionary lambdas; hence the slightly
+ ad-hoc isDictId
+
+* Never *reduce* arity. For example
+ f = \xy. g x y
+ Then if h has arity 1 we don't want to eta-reduce because then
+ f's arity would decrease, and that is bad
+
+These delicacies are why we don't use exprIsTrivial and exprIsHNF here.
+Alas.
+
+Note [Eta reduction with casted arguments]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Consider
+ (\(x:t3). f (x |> g)) :: t3 -> t2
+ where
+ f :: t1 -> t2
+ g :: t3 ~ t1
+This should be eta-reduced to
+
+ f |> (sym g -> t2)
+
+So we need to accumulate a coercion, pushing it inward (past
+variable arguments only) thus:
+ f (x |> co_arg) |> co --> (f |> (sym co_arg -> co)) x
+ f (x:t) |> co --> (f |> (t -> co)) x
+ f @ a |> co --> (f |> (forall a.co)) @ a
+ f @ (g:t1~t2) |> co --> (f |> (t1~t2 => co)) @ (g:t1~t2)
+These are the equations for ok_arg.
+
+It's true that we could also hope to eta reduce these:
+ (\xy. (f x |> g) y)
+ (\xy. (f x y) |> g)
+But the simplifier pushes those casts outwards, so we don't
+need to address that here.
+
+\begin{code}
+tryEtaReduce :: [Var] -> CoreExpr -> Maybe CoreExpr
+tryEtaReduce bndrs body
+ = go (reverse bndrs) body (IdCo (exprType body))
+ where
+ incoming_arity = count isId bndrs
+
+ go :: [Var] -- Binders, innermost first, types [a3,a2,a1]
+ -> CoreExpr -- Of type tr
+ -> CoercionI -- Of type tr ~ ts
+ -> Maybe CoreExpr -- Of type a1 -> a2 -> a3 -> ts
+ -- See Note [Eta reduction with casted arguments]
+ -- for why we have an accumulating coercion
+ go [] fun co
+ | ok_fun fun = Just (mkCoerceI co fun)
+
+ go (b : bs) (App fun arg) co
+ | Just co' <- ok_arg b arg co
+ = go bs fun co'
+
+ go _ _ _ = Nothing -- Failure!
+
+ ---------------
+ -- 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 = fun_arity fun >= incoming_arity
+
+ ---------------
+ fun_arity fun -- See Note [Arity care]
+ | isLocalId fun && isLoopBreaker (idOccInfo fun) = 0
+ | otherwise = idArity fun
+
+ ---------------
+ ok_lam v = isTyCoVar v || isDictId v
+
+ ---------------
+ ok_arg :: Var -- Of type bndr_t
+ -> CoreExpr -- Of type arg_t
+ -> CoercionI -- Of kind (t1~t2)
+ -> Maybe CoercionI -- Of type (arg_t -> t1 ~ bndr_t -> t2)
+ -- (and similarly for tyvars, coercion args)
+ -- See Note [Eta reduction with casted arguments]
+ ok_arg bndr (Type ty) co
+ | Just tv <- getTyVar_maybe ty
+ , bndr == tv = Just (mkForAllTyCoI tv co)
+ ok_arg bndr (Var v) co
+ | bndr == v = Just (mkFunTyCoI (IdCo (idType bndr)) co)
+ ok_arg bndr (Cast (Var v) co_arg) co
+ | bndr == v = Just (mkFunTyCoI (ACo (mkSymCoercion co_arg)) co)
+ -- The simplifier combines multiple casts into one,
+ -- so we can have a simple-minded pattern match here
+ ok_arg _ _ _ = Nothing
+\end{code}
+
+
%************************************************************************
%* *
\subsection{Determining non-updatable right-hand-sides}
-- | This function is called only on *top-level* right-hand sides.
-- Returns @True@ if the RHS can be allocated statically in the output,
-- with no thunks involved at all.
-rhsIsStatic :: PackageId -> CoreExpr -> Bool
+rhsIsStatic :: (Name -> Bool) -> CoreExpr -> Bool
-- It's called (i) in TidyPgm.hasCafRefs to decide if the rhs is, or
-- refers to, CAFs; (ii) in CoreToStg to decide whether to put an
-- update flag on it and (iii) in DsExpr to decide how to expand
--
-- c) don't look through unfolding of f in (f x).
-rhsIsStatic _this_pkg rhs = is_static False rhs
+rhsIsStatic _is_dynamic_name rhs = is_static False rhs
where
is_static :: Bool -- True <=> in a constructor argument; must be atomic
-> CoreExpr -> Bool
- is_static False (Lam b e) = isRuntimeVar b || is_static False e
-
- is_static _ (Note (SCC _) _) = False
- is_static in_arg (Note _ e) = is_static in_arg e
- is_static in_arg (Cast e _) = is_static in_arg e
+ is_static False (Lam b e) = isRuntimeVar b || is_static False e
+ is_static in_arg (Note n e) = notSccNote n && is_static in_arg e
+ is_static in_arg (Cast e _) = is_static in_arg e
is_static _ (Lit lit)
= case lit of
where
go (Var f) n_val_args
#if mingw32_TARGET_OS
- | not (isDllName _this_pkg (idName f))
+ | not (_is_dynamic_name (idName f))
#endif
= saturated_data_con f n_val_args
|| (in_arg && n_val_args == 0)
-- x = D# (1.0## /## 2.0##)
-- can't float because /## can fail.
- go (Note (SCC _) _) _ = False
- go (Note _ f) n_val_args = go f n_val_args
- go (Cast e _) n_val_args = go e n_val_args
-
- go _ _ = False
+ go (Note n f) n_val_args = notSccNote n && go f n_val_args
+ go (Cast e _) n_val_args = go e n_val_args
+ go _ _ = False
saturated_data_con f n_val_args
= case isDataConWorkId_maybe f of