setLevels,
Level(..), tOP_LEVEL,
+ LevelledBind, LevelledExpr,
incMinorLvl, ltMajLvl, ltLvl, isTopLvl, isInlineCtxt
) where
import CoreSyn
import CmdLineOpts ( FloatOutSwitches(..) )
-import CoreUtils ( exprType, exprIsTrivial, exprIsBottom, mkPiTypes )
+import CoreUtils ( exprType, exprIsTrivial, exprIsCheap, mkPiTypes )
import CoreFVs -- all of it
import Subst
-import Id ( Id, idType, mkSysLocal, isOneShotLambda, zapDemandIdInfo,
+import Id ( Id, idType, mkSysLocalUnencoded,
+ isOneShotLambda, zapDemandIdInfo,
idSpecialisation, idWorkerInfo, setIdInfo
)
import IdInfo ( workerExists, vanillaIdInfo, )
import Type ( isUnLiftedType, Type )
import BasicTypes ( TopLevelFlag(..) )
import UniqSupply
-import Util ( sortLt, isSingleton, count )
+import Util ( sortLe, isSingleton, count )
import Outputable
+import FastString
\end{code}
%************************************************************************
lvlMFE False ctxt_lvl env arg `thenLvl` \ arg' ->
returnLvl (App fun' arg')
where
- lvl_fun (_, AnnCase _ _ _) = lvlMFE True ctxt_lvl env fun
+-- gaw 2004
+ lvl_fun (_, AnnCase _ _ _ _) = lvlMFE True ctxt_lvl env fun
lvl_fun other = lvlExpr ctxt_lvl env fun
-- We don't do MFE on partial applications generally,
-- but we do if the function is big and hairy, like a case
-- but not nearly so much now non-recursive newtypes are transparent.
-- [See SetLevels rev 1.50 for a version with this approach.]
+lvlExpr ctxt_lvl env (_, AnnLet (AnnNonRec bndr rhs) body)
+ | isUnLiftedType (idType bndr)
+ -- Treat unlifted let-bindings (let x = b in e) just like (case b of x -> e)
+ -- That is, leave it exactly where it is
+ -- We used to float unlifted bindings too (e.g. to get a cheap primop
+ -- outside a lambda (to see how, look at lvlBind in rev 1.58)
+ -- but an unrelated change meant that these unlifed bindings
+ -- could get to the top level which is bad. And there's not much point;
+ -- unlifted bindings are always cheap, and so hardly worth floating.
+ = lvlExpr ctxt_lvl env rhs `thenLvl` \ rhs' ->
+ lvlExpr incd_lvl env' body `thenLvl` \ body' ->
+ returnLvl (Let (NonRec bndr' rhs') body')
+ where
+ incd_lvl = incMinorLvl ctxt_lvl
+ bndr' = TB bndr incd_lvl
+ env' = extendLvlEnv env [bndr']
+
lvlExpr ctxt_lvl env (_, AnnLet bind body)
= lvlBind NotTopLevel ctxt_lvl env bind `thenLvl` \ (bind', new_env) ->
lvlExpr ctxt_lvl new_env body `thenLvl` \ body' ->
returnLvl (Let bind' body')
-lvlExpr ctxt_lvl env (_, AnnCase expr case_bndr alts)
+-- gaw 2004
+lvlExpr ctxt_lvl env (_, AnnCase expr case_bndr ty alts)
= lvlMFE True ctxt_lvl env expr `thenLvl` \ expr' ->
let
alts_env = extendCaseBndrLvlEnv env expr' case_bndr incd_lvl
in
mapLvl (lvl_alt alts_env) alts `thenLvl` \ alts' ->
- returnLvl (Case expr' (case_bndr, incd_lvl) alts')
+ returnLvl (Case expr' (TB case_bndr incd_lvl) ty alts')
where
incd_lvl = incMinorLvl ctxt_lvl
= lvlMFE True incd_lvl new_env rhs `thenLvl` \ rhs' ->
returnLvl (con, bs', rhs')
where
- bs' = [ (b, incd_lvl) | b <- bs ]
+ bs' = [ TB b incd_lvl | b <- bs ]
new_env = extendLvlEnv alts_env bs'
\end{code}
@lvlMFE@ is just like @lvlExpr@, except that it might let-bind
the expression, so that it can itself be floated.
+[NOTE: unlifted MFEs]
+We don't float unlifted MFEs, which potentially loses big opportunites.
+For example:
+ \x -> f (h y)
+where h :: Int -> Int# is expensive. We'd like to float the (h y) outside
+the \x, but we don't because it's unboxed. Possible solution: box it.
+
\begin{code}
lvlMFE :: Bool -- True <=> strict context [body of case or let]
-> Level -- Level of innermost enclosing lambda/tylam
lvlMFE strict_ctxt ctxt_lvl env (_, AnnType ty)
= returnLvl (Type ty)
+
lvlMFE strict_ctxt ctxt_lvl env ann_expr@(fvs, _)
- | isUnLiftedType ty -- Can't let-bind it
+ | isUnLiftedType ty -- Can't let-bind it; see [NOTE: unlifted MFEs]
|| isInlineCtxt ctxt_lvl -- Don't float out of an __inline__ context
+ || exprIsTrivial expr -- Never float if it's trivial
|| not good_destination
- || exprIsTrivial expr -- Is trivial
- || (strict_ctxt && exprIsBottom expr) -- Strict context and is bottom
- -- e.g. \x -> error "foo"
- -- No gain from floating this
= -- Don't float it out
lvlExpr ctxt_lvl env ann_expr
| otherwise -- Float it out!
= lvlFloatRhs abs_vars dest_lvl env ann_expr `thenLvl` \ expr' ->
newLvlVar "lvl" abs_vars ty `thenLvl` \ var ->
- returnLvl (Let (NonRec (var,dest_lvl) expr')
+ returnLvl (Let (NonRec (TB var dest_lvl) expr')
(mkVarApps (Var var) abs_vars))
where
expr = deAnnotate ann_expr
dest_lvl = destLevel env fvs (isFunction ann_expr)
abs_vars = abstractVars dest_lvl env fvs
- good_destination = dest_lvl `ltMajLvl` ctxt_lvl -- Escapes a value lambda
- || (isTopLvl dest_lvl -- Goes to the top
- && floatConsts env
- && not strict_ctxt) -- or from a strict context
-- A decision to float entails let-binding this thing, and we only do
-- that if we'll escape a value lambda, or will go to the top level.
- --
- -- Beware:
- -- concat = /\ a -> foldr ..a.. (++) []
- -- was getting turned into
- -- concat = /\ a -> lvl a
- -- lvl = /\ a -> foldr ..a.. (++) []
- -- which is pretty stupid. Hence the strict_ctxt test
- --
- -- We are keen to float something to the top level, even if it does not
- -- escape a lambda, because then it needs no allocation. But it's controlled
- -- by a flag, because doing this too early loses opportunities for RULES
- -- which (needless to say) are important in some nofib programs
- -- (gcd is an example).
+ good_destination
+ | dest_lvl `ltMajLvl` ctxt_lvl -- Escapes a value lambda
+ = not (exprIsCheap expr) || isTopLvl dest_lvl
+ -- Even if it escapes a value lambda, we only
+ -- float if it's not cheap (unless it'll get all the
+ -- way to the top). I've seen cases where we
+ -- float dozens of tiny free expressions, which cost
+ -- more to allocate than to evaluate.
+ -- NB: exprIsCheap is also true of bottom expressions, which
+ -- is good; we don't want to share them
+ --
+ -- It's only Really Bad to float a cheap expression out of a
+ -- strict context, because that builds a thunk that otherwise
+ -- would never be built. So another alternative would be to
+ -- add
+ -- || (strict_ctxt && not (exprIsBottom expr))
+ -- to the condition above. We should really try this out.
+
+ | otherwise -- Does not escape a value lambda
+ = isTopLvl dest_lvl -- Only float if we are going to the top level
+ && floatConsts env -- and the floatConsts flag is on
+ && not strict_ctxt -- Don't float from a strict context
+ -- We are keen to float something to the top level, even if it does not
+ -- escape a lambda, because then it needs no allocation. But it's controlled
+ -- by a flag, because doing this too early loses opportunities for RULES
+ -- which (needless to say) are important in some nofib programs
+ -- (gcd is an example).
+ --
+ -- Beware:
+ -- concat = /\ a -> foldr ..a.. (++) []
+ -- was getting turned into
+ -- concat = /\ a -> lvl a
+ -- lvl = /\ a -> foldr ..a.. (++) []
+ -- which is pretty stupid. Hence the strict_ctxt test
\end{code}
-> LvlM (LevelledBind, LevelEnv)
lvlBind top_lvl ctxt_lvl env (AnnNonRec bndr rhs@(rhs_fvs,_))
- | isInlineCtxt ctxt_lvl -- Don't do anything inside InlineMe
+ | isInlineCtxt ctxt_lvl -- Don't do anything inside InlineMe
= lvlExpr ctxt_lvl env rhs `thenLvl` \ rhs' ->
- returnLvl (NonRec (bndr, ctxt_lvl) rhs', env)
+ returnLvl (NonRec (TB bndr ctxt_lvl) rhs', env)
| null abs_vars
= -- No type abstraction; clone existing binder
lvlExpr dest_lvl env rhs `thenLvl` \ rhs' ->
cloneVar top_lvl env bndr ctxt_lvl dest_lvl `thenLvl` \ (env', bndr') ->
- returnLvl (NonRec (bndr', dest_lvl) rhs', env')
+ returnLvl (NonRec (TB bndr' dest_lvl) rhs', env')
| otherwise
= -- Yes, type abstraction; create a new binder, extend substitution, etc
lvlFloatRhs abs_vars dest_lvl env rhs `thenLvl` \ rhs' ->
newPolyBndrs dest_lvl env abs_vars [bndr] `thenLvl` \ (env', [bndr']) ->
- returnLvl (NonRec (bndr', dest_lvl) rhs', env')
+ returnLvl (NonRec (TB bndr' dest_lvl) rhs', env')
where
bind_fvs = rhs_fvs `unionVarSet` idFreeVars bndr
abs_vars = abstractVars dest_lvl env bind_fvs
-
- dest_lvl | isUnLiftedType (idType bndr) = destLevel env bind_fvs False `maxLvl` Level 1 0
- | otherwise = destLevel env bind_fvs (isFunction rhs)
- -- Hack alert! We do have some unlifted bindings, for cheap primops, and
- -- it is ok to float them out; but not to the top level. If they would otherwise
- -- go to the top level, we pin them inside the topmost lambda
+ dest_lvl = destLevel env bind_fvs (isFunction rhs)
\end{code}
lvlBind top_lvl ctxt_lvl env (AnnRec pairs)
| isInlineCtxt ctxt_lvl -- Don't do anything inside InlineMe
= mapLvl (lvlExpr ctxt_lvl env) rhss `thenLvl` \ rhss' ->
- returnLvl (Rec ((bndrs `zip` repeat ctxt_lvl) `zip` rhss'), env)
+ returnLvl (Rec ([TB b ctxt_lvl | b <- bndrs] `zip` rhss'), env)
| null abs_vars
= cloneRecVars top_lvl env bndrs ctxt_lvl dest_lvl `thenLvl` \ (new_env, new_bndrs) ->
mapLvl (lvlExpr ctxt_lvl new_env) rhss `thenLvl` \ new_rhss ->
- returnLvl (Rec ((new_bndrs `zip` repeat dest_lvl) `zip` new_rhss), new_env)
+ returnLvl (Rec ([TB b dest_lvl | b <- new_bndrs] `zip` new_rhss), new_env)
| isSingleton pairs && count isId abs_vars > 1
= -- Special case for self recursion where there are
in
lvlExpr body_lvl body_env rhs_body `thenLvl` \ new_rhs_body ->
newPolyBndrs dest_lvl env abs_vars [bndr] `thenLvl` \ (poly_env, [poly_bndr]) ->
- returnLvl (Rec [((poly_bndr,dest_lvl), mkLams abs_vars_w_lvls $
- mkLams new_lam_bndrs $
- Let (Rec [((new_bndr,rhs_lvl), mkLams new_lam_bndrs new_rhs_body)])
- (mkVarApps (Var new_bndr) lam_bndrs))],
+ returnLvl (Rec [(TB poly_bndr dest_lvl,
+ mkLams abs_vars_w_lvls $
+ mkLams new_lam_bndrs $
+ Let (Rec [(TB new_bndr rhs_lvl, mkLams new_lam_bndrs new_rhs_body)])
+ (mkVarApps (Var new_bndr) lam_bndrs))],
poly_env)
| otherwise -- Non-null abs_vars
= newPolyBndrs dest_lvl env abs_vars bndrs `thenLvl` \ (new_env, new_bndrs) ->
mapLvl (lvlFloatRhs abs_vars dest_lvl new_env) rhss `thenLvl` \ new_rhss ->
- returnLvl (Rec ((new_bndrs `zip` repeat dest_lvl) `zip` new_rhss), new_env)
+ returnLvl (Rec ([TB b dest_lvl | b <- new_bndrs] `zip` new_rhss), new_env)
where
(bndrs,rhss) = unzip pairs
%************************************************************************
\begin{code}
-lvlLamBndrs :: Level -> [CoreBndr] -> (Level, [(CoreBndr, Level)])
+lvlLamBndrs :: Level -> [CoreBndr] -> (Level, [TaggedBndr Level])
-- Compute the levels for the binders of a lambda group
-- The binders returned are exactly the same as the ones passed,
-- but they are now paired with a level
| isId bndr && -- Go to the next major level if this is a value binder,
not bumped_major && -- and we havn't already gone to the next level (one jump per group)
not (isOneShotLambda bndr) -- and it isn't a one-shot lambda
- = go new_lvl True ((bndr,new_lvl) : rev_lvld_bndrs) bndrs
+ = go new_lvl True (TB bndr new_lvl : rev_lvld_bndrs) bndrs
| otherwise
- = go old_lvl bumped_major ((bndr,old_lvl) : rev_lvld_bndrs) bndrs
+ = go old_lvl bumped_major (TB bndr old_lvl : rev_lvld_bndrs) bndrs
where
new_lvl = incMajorLvl old_lvl
floatConsts :: LevelEnv -> Bool
floatConsts (FloatOutSw _ float_consts, _, _, _) = float_consts
-extendLvlEnv :: LevelEnv -> [(Var,Level)] -> LevelEnv
+extendLvlEnv :: LevelEnv -> [TaggedBndr Level] -> LevelEnv
-- Used when *not* cloning
extendLvlEnv (float_lams, lvl_env, subst, id_env) prs
= (float_lams,
foldl del_subst subst prs,
foldl del_id id_env prs)
where
- add_lvl env (v,l) = extendVarEnv env v l
- del_subst env (v,_) = extendInScope env v
- del_id env (v,_) = delVarEnv env v
+ add_lvl env (TB v l) = extendVarEnv env v l
+ del_subst env (TB v _) = extendInScope env v
+ del_id env (TB v _) = delVarEnv env v
-- We must remove any clone for this variable name in case of
-- shadowing. This bit me in the following case
-- (in nofib/real/gg/Spark.hs):
extendCaseBndrLvlEnv (float_lams, lvl_env, subst, id_env) (Var scrut_var) case_bndr lvl
= (float_lams,
extendVarEnv lvl_env case_bndr lvl,
- extendSubst subst case_bndr (DoneEx (Var scrut_var)),
+ extendIdSubst subst case_bndr (DoneEx (Var scrut_var)),
extendVarEnv id_env case_bndr ([scrut_var], Var scrut_var))
extendCaseBndrLvlEnv env scrut case_bndr lvl
- = extendLvlEnv env [(case_bndr,lvl)]
+ = extendLvlEnv env [TB case_bndr lvl]
extendPolyLvlEnv dest_lvl (float_lams, lvl_env, subst, id_env) abs_vars bndr_pairs
= (float_lams,
foldl add_id id_env bndr_pairs)
where
add_lvl env (v,v') = extendVarEnv env v' dest_lvl
- add_subst env (v,v') = extendSubst env v (DoneEx (mkVarApps (Var v') abs_vars))
+ add_subst env (v,v') = extendIdSubst env v (DoneEx (mkVarApps (Var v') abs_vars))
add_id env (v,v') = extendVarEnv env v ((v':abs_vars), mkVarApps (Var v') abs_vars)
extendCloneLvlEnv lvl (float_lams, lvl_env, _, id_env) new_subst bndr_pairs
-- whose level is greater than the destination level
-- These are the ones we are going to abstract out
abstractVars dest_lvl env fvs
- = uniq (sortLt lt [var | fv <- varSetElems fvs, var <- absVarsOf dest_lvl env fv])
+ = uniq (sortLe le [var | fv <- varSetElems fvs, var <- absVarsOf dest_lvl env fv])
where
-- Sort the variables so we don't get
-- mixed-up tyvars and Ids; it's just messy
- v1 `lt` v2 = case (isId v1, isId v2) of
+ v1 `le` v2 = case (isId v1, isId v2) of
(True, False) -> False
(False, True) -> True
- other -> v1 < v2 -- Same family
+ other -> v1 <= v2 -- Same family
uniq :: [Var] -> [Var]
-- Remove adjacent duplicates; the sort will have brought them together
in
returnLvl (extendPolyLvlEnv dest_lvl env abs_vars (bndrs `zip` new_bndrs), new_bndrs)
where
- mk_poly_bndr bndr uniq = mkSysLocal (_PK_ str) uniq poly_ty
+ mk_poly_bndr bndr uniq = mkSysLocalUnencoded (mkFastString str) uniq poly_ty
where
str = "poly_" ++ occNameUserString (getOccName bndr)
poly_ty = mkPiTypes abs_vars (idType bndr)
-> LvlM Id
newLvlVar str vars body_ty
= getUniqueUs `thenLvl` \ uniq ->
- returnUs (mkSysLocal (_PK_ str) uniq (mkPiTypes vars body_ty))
+ returnUs (mkSysLocalUnencoded (mkFastString str) uniq (mkPiTypes vars body_ty))
-- The deeply tiresome thing is that we have to apply the substitution
-- to the rules inside each Id. Grr. But it matters.