import CoreSyn
-import CoreUtils ( exprType, exprIsTrivial, exprIsBottom, mkPiType )
+import CoreUtils ( exprType, exprIsTrivial, exprIsBottom, mkPiTypes )
import CoreFVs -- all of it
import Subst
-import Id ( Id, idType, idFreeTyVars, mkSysLocal, isOneShotLambda, modifyIdInfo,
+import Id ( Id, idType, mkSysLocal, isOneShotLambda, zapDemandIdInfo,
idSpecialisation, idWorkerInfo, setIdInfo
)
-import IdInfo ( workerExists, vanillaIdInfo, demandInfo, setDemandInfo )
-import Var ( Var, setVarUnique )
+import IdInfo ( workerExists, vanillaIdInfo, )
+import Var ( Var )
import VarSet
import VarEnv
import Name ( getOccName )
import OccName ( occNameUserString )
import Type ( isUnLiftedType, Type )
import BasicTypes ( TopLevelFlag(..) )
-import Demand ( isStrict, wwLazy )
import UniqSupply
import Util ( sortLt, isSingleton, count )
import Outputable
%************************************************************************
\begin{code}
-data Level = Level Int -- Level number of enclosing lambdas
+data Level = InlineCtxt -- A level that's used only for
+ -- the context parameter ctxt_lvl
+ | Level Int -- Level number of enclosing lambdas
Int -- Number of big-lambda and/or case expressions between
-- here and the nearest enclosing lambda
\end{code}
That's meant to be the level number of the enclosing binder in the
final (floated) program. If the level number of a sub-expression is
less than that of the context, then it might be worth let-binding the
-sub-expression so that it will indeed float. This context level starts
-at @Level 0 0@.
+sub-expression so that it will indeed float.
+
+If you can float to level @Level 0 0@ worth doing so because then your
+allocation becomes static instead of dynamic. We always start with
+context @Level 0 0@. @InlineCtxt@ very similar to @Level 0 0@, but is
+used for one purpose: to say "don't float anything out of here".
+That's exactly what we want for the body of an INLINE, where we don't
+want to float anything out at all. See notes with lvlMFE below.
+
\begin{code}
type LevelledExpr = TaggedExpr Level
-type LevelledArg = TaggedArg Level
type LevelledBind = TaggedBind Level
-tOP_LEVEL = Level 0 0
+tOP_LEVEL = Level 0 0
+iNLINE_CTXT = InlineCtxt
incMajorLvl :: Level -> Level
+incMajorLvl InlineCtxt = Level 1 0
incMajorLvl (Level major minor) = Level (major+1) 0
incMinorLvl :: Level -> Level
+incMinorLvl InlineCtxt = Level 0 1
incMinorLvl (Level major minor) = Level major (minor+1)
maxLvl :: Level -> Level -> Level
+maxLvl InlineCtxt l2 = l2
+maxLvl l1 InlineCtxt = l1
maxLvl l1@(Level maj1 min1) l2@(Level maj2 min2)
| (maj1 > maj2) || (maj1 == maj2 && min1 > min2) = l1
| otherwise = l2
ltLvl :: Level -> Level -> Bool
+ltLvl any_lvl InlineCtxt = False
+ltLvl InlineCtxt (Level _ _) = True
ltLvl (Level maj1 min1) (Level maj2 min2)
= (maj1 < maj2) || (maj1 == maj2 && min1 < min2)
ltMajLvl :: Level -> Level -> Bool
-- Tells if one level belongs to a difft *lambda* level to another
- -- But it returns True regardless if l1 is the top level
- -- We always like to float to the top!
-ltMajLvl (Level 0 0) _ = True
+ltMajLvl any_lvl InlineCtxt = False
+ltMajLvl InlineCtxt (Level maj2 _) = 0 < maj2
ltMajLvl (Level maj1 _) (Level maj2 _) = maj1 < maj2
isTopLvl :: Level -> Bool
isTopLvl (Level 0 0) = True
-isTopLvl other = False
+isTopLvl other = False
+
+isInlineCtxt :: Level -> Bool
+isInlineCtxt InlineCtxt = True
+isInlineCtxt other = False
instance Outputable Level where
+ ppr InlineCtxt = text "<INLINE>"
ppr (Level maj min) = hcat [ char '<', int maj, char ',', int min, char '>' ]
+
+instance Eq Level where
+ InlineCtxt == InlineCtxt = True
+ (Level maj1 min1) == (Level maj2 min2) = maj1==maj2 && min1==min2
+ l1 == l2 = False
\end{code}
+
%************************************************************************
%* *
\subsection{Main level-setting code}
-- but we do if the function is big and hairy, like a case
lvlExpr ctxt_lvl env (_, AnnNote InlineMe expr)
- -- Don't float anything out of an InlineMe
- = lvlExpr tOP_LEVEL env expr `thenLvl` \ expr' ->
+-- Don't float anything out of an InlineMe; hence the iNLINE_CTXT
+ = lvlExpr iNLINE_CTXT env expr `thenLvl` \ expr' ->
returnLvl (Note InlineMe expr')
lvlExpr ctxt_lvl env (_, AnnNote note expr)
|| 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
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 && not strict_ctxt) -- Goes to the top
+ good_destination = dest_lvl `ltMajLvl` ctxt_lvl -- Escapes a value lambda
+ || (isTopLvl dest_lvl -- Goes to the top
+ && not (isInlineCtxt ctxt_lvl) -- Don't float out of an __inline__ context
+ && 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.
- -- But beware
+ -- But beware (a):
+ -- x = __inline__ (f (g y))
+ -- Here we don't want to float the (g y); otherwise it'll get outside the
+ -- __inline__ envelope, and may never get inlined
+ --
+ -- Also beware (b):
-- concat = /\ a -> foldr ..a.. (++) []
-- was getting turned into
-- concat = /\ a -> lvl a
lvlBind top_lvl ctxt_lvl env (AnnNonRec bndr rhs@(rhs_fvs,_))
| null abs_vars
= -- No type abstraction; clone existing binder
- lvlExpr ctxt_lvl env rhs `thenLvl` \ rhs' ->
+ 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')
\begin{code}
lvlBind top_lvl ctxt_lvl env (AnnRec pairs)
| null abs_vars
- = cloneVars top_lvl env bndrs ctxt_lvl dest_lvl `thenLvl` \ (new_env, new_bndrs) ->
+ = 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)
(mkVarApps (Var new_bndr) lam_bndrs))],
poly_env)
- | otherwise
+ | 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)
\end{code}
\begin{code}
-abstractVars :: Level -> LevelEnv -> VarSet -> [Var]
- -- Find the variables in fvs, free vars of the target expresion,
- -- whose level is less than than the supplied 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])
- 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
- (True, False) -> False
- (False, True) -> True
- other -> v1 < v2 -- Same family
- uniq :: [Var] -> [Var]
- -- Remove adjacent duplicates; the sort will have brought them together
- uniq (v1:v2:vs) | v1 == v2 = uniq (v2:vs)
- | otherwise = v1 : uniq (v2:vs)
- uniq vs = vs
-
-- Destintion level is the max Id level of the expression
-- (We'll abstract the type variables, if any.)
destLevel :: LevelEnv -> VarSet -> Bool -> Level
-- extendCaseBndrLvlEnv adds the mapping case-bndr->scrut-var if it can
-- (see point 4 of the module overview comment)
+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)),
+ extendVarEnv id_env case_bndr ([scrut_var], Var scrut_var))
+
extendCaseBndrLvlEnv env scrut case_bndr lvl
- = case scrut of
- Var v -> extendCloneLvlEnv lvl env [(case_bndr, v)]
- other -> extendLvlEnv env [(case_bndr,lvl)]
+ = extendLvlEnv env [(case_bndr,lvl)]
extendPolyLvlEnv dest_lvl (float_lams, lvl_env, subst, id_env) abs_vars bndr_pairs
= (float_lams,
add_subst env (v,v') = extendSubst 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, subst, id_env) bndr_pairs
+extendCloneLvlEnv lvl (float_lams, lvl_env, _, id_env) new_subst bndr_pairs
= (float_lams,
foldl add_lvl lvl_env bndr_pairs,
- foldl add_subst subst bndr_pairs,
+ new_subst,
foldl add_id id_env bndr_pairs)
where
add_lvl env (v,v') = extendVarEnv env v' lvl
- add_subst env (v,v') = extendSubst env v (DoneEx (Var v'))
add_id env (v,v') = extendVarEnv env v ([v'], Var v')
Just (_, expr) -> expr
other -> Var v
+abstractVars :: Level -> LevelEnv -> VarSet -> [Var]
+ -- Find the variables in fvs, free vars of the target expresion,
+ -- 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])
+ 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
+ (True, False) -> False
+ (False, True) -> True
+ other -> v1 < v2 -- Same family
+
+ uniq :: [Var] -> [Var]
+ -- Remove adjacent duplicates; the sort will have brought them together
+ uniq (v1:v2:vs) | v1 == v2 = uniq (v2:vs)
+ | otherwise = v1 : uniq (v2:vs)
+ uniq vs = vs
+
absVarsOf :: Level -> LevelEnv -> Var -> [Var]
- -- If f is free in the exression, and f maps to poly_f a b c in the
+ -- If f is free in the expression, and f maps to poly_f a b c in the
-- current substitution, then we must report a b c as candidate type
-- variables
absVarsOf dest_lvl (_, lvl_env, _, id_env) v
| isId v
- = [final_av | av <- lookup_avs v, abstract_me av, final_av <- add_tyvars av]
+ = [zap av2 | av1 <- lookup_avs v, av2 <- add_tyvars av1, abstract_me av2]
| otherwise
= if abstract_me v then [v] else []
Just (abs_vars, _) -> abs_vars
Nothing -> [v]
- -- We are going to lambda-abstract, so nuke any IdInfo,
- -- and add the tyvars of the Id
- add_tyvars v | isId v = zap v : varSetElems (idFreeTyVars v)
+ add_tyvars v | isId v = v : varSetElems (idFreeTyVars v)
| otherwise = [v]
- zap v = WARN( workerExists (idWorkerInfo v)
- || not (isEmptyCoreRules (idSpecialisation v)),
- text "absVarsOf: discarding info on" <+> ppr v )
- setIdInfo v vanillaIdInfo
+ -- We are going to lambda-abstract, so nuke any IdInfo,
+ -- and add the tyvars of the Id (if necessary)
+ zap v | isId v = WARN( workerExists (idWorkerInfo v) ||
+ not (isEmptyCoreRules (idSpecialisation v)),
+ text "absVarsOf: discarding info on" <+> ppr v )
+ setIdInfo v vanillaIdInfo
+ | otherwise = v
\end{code}
\begin{code}
\begin{code}
newPolyBndrs dest_lvl env abs_vars bndrs
- = getUniquesUs (length bndrs) `thenLvl` \ uniqs ->
+ = getUniquesUs `thenLvl` \ uniqs ->
let
new_bndrs = zipWith mk_poly_bndr bndrs uniqs
in
mk_poly_bndr bndr uniq = mkSysLocal (_PK_ str) uniq poly_ty
where
str = "poly_" ++ occNameUserString (getOccName bndr)
- poly_ty = foldr mkPiType (idType bndr) abs_vars
+ poly_ty = mkPiTypes abs_vars (idType bndr)
newLvlVar :: String
-> LvlM Id
newLvlVar str vars body_ty
= getUniqueUs `thenLvl` \ uniq ->
- returnUs (mkSysLocal (_PK_ str) uniq (foldr mkPiType body_ty vars))
+ returnUs (mkSysLocal (_PK_ 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.
cloneVar :: TopLevelFlag -> LevelEnv -> Id -> Level -> Level -> LvlM (LevelEnv, Id)
cloneVar TopLevel env v ctxt_lvl dest_lvl
= returnUs (env, v) -- Don't clone top level things
-cloneVar NotTopLevel env v ctxt_lvl dest_lvl
+cloneVar NotTopLevel env@(_,_,subst,_) v ctxt_lvl dest_lvl
= ASSERT( isId v )
- getUniqueUs `thenLvl` \ uniq ->
+ getUs `thenLvl` \ us ->
let
- v' = setVarUnique v uniq
- v'' = subst_id_info env ctxt_lvl dest_lvl v'
- env' = extendCloneLvlEnv dest_lvl env [(v,v'')]
+ (subst', v1) = substAndCloneId subst us v
+ v2 = zap_demand ctxt_lvl dest_lvl v1
+ env' = extendCloneLvlEnv dest_lvl env subst' [(v,v2)]
in
- returnUs (env', v'')
+ returnUs (env', v2)
-cloneVars :: TopLevelFlag -> LevelEnv -> [Id] -> Level -> Level -> LvlM (LevelEnv, [Id])
-cloneVars TopLevel env vs ctxt_lvl dest_lvl
+cloneRecVars :: TopLevelFlag -> LevelEnv -> [Id] -> Level -> Level -> LvlM (LevelEnv, [Id])
+cloneRecVars TopLevel env vs ctxt_lvl dest_lvl
= returnUs (env, vs) -- Don't clone top level things
-cloneVars NotTopLevel env vs ctxt_lvl dest_lvl
+cloneRecVars NotTopLevel env@(_,_,subst,_) vs ctxt_lvl dest_lvl
= ASSERT( all isId vs )
- getUniquesUs (length vs) `thenLvl` \ uniqs ->
+ getUs `thenLvl` \ us ->
let
- vs' = zipWith setVarUnique vs uniqs
- vs'' = map (subst_id_info env' ctxt_lvl dest_lvl) vs'
- env' = extendCloneLvlEnv dest_lvl env (vs `zip` vs'')
+ (subst', vs1) = substAndCloneRecIds subst us vs
+ vs2 = map (zap_demand ctxt_lvl dest_lvl) vs1
+ env' = extendCloneLvlEnv dest_lvl env subst' (vs `zip` vs2)
in
- returnUs (env', vs'')
+ returnUs (env', vs2)
-subst_id_info (_, _, subst, _) ctxt_lvl dest_lvl v
- = modifyIdInfo (\info -> substIdInfo subst info (zap_dmd info)) v
- where
-- VERY IMPORTANT: we must zap the demand info
-- if the thing is going to float out past a lambda
- zap_dmd info
- | float_past_lam && isStrict (demandInfo info)
- = setDemandInfo info wwLazy
- | otherwise
- = info
-
- float_past_lam = ctxt_lvl `ltMajLvl` dest_lvl
+zap_demand dest_lvl ctxt_lvl id
+ | ctxt_lvl == dest_lvl = id -- Stays put
+ | otherwise = zapDemandIdInfo id -- Floats out
\end{code}