2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4 \section{Tidying up Core}
8 tidyCorePgm, tidyExpr, tidyCoreExpr,
12 #include "HsVersions.h"
14 import CmdLineOpts ( DynFlags, DynFlag(..), opt_OmitInterfacePragmas )
16 import CoreUnfold ( noUnfolding, mkTopUnfolding, okToUnfoldInHiFile )
17 import CoreFVs ( ruleSomeFreeVars, exprSomeFreeVars )
18 import CoreLint ( showPass, endPass )
21 import Var ( Id, Var )
22 import Id ( idType, idInfo, idName, isExportedId,
23 idSpecialisation, idUnique, isDataConWrapId,
24 mkVanillaGlobal, isLocalId, isRecordSelector,
25 setIdUnfolding, hasNoBinding, mkUserLocal,
26 idNewDemandInfo, setIdNewDemandInfo
28 import IdInfo {- loads of stuff -}
29 import NewDemand ( isBottomingSig, topSig, isStrictDmd )
30 import Name ( getOccName, nameOccName, globaliseName, setNameOcc,
31 localiseName, isGlobalName, setNameUnique
33 import NameEnv ( filterNameEnv )
34 import OccName ( TidyOccEnv, initTidyOccEnv, tidyOccName )
35 import Type ( tidyTopType, tidyType, tidyTyVar )
36 import Module ( Module, moduleName )
37 import HscTypes ( PersistentCompilerState( pcs_PRS ),
38 PersistentRenamerState( prsOrig ),
39 NameSupply( nsNames, nsUniqs ),
40 TypeEnv, extendTypeEnvList,
41 ModDetails(..), TyThing(..)
43 import FiniteMap ( lookupFM, addToFM )
44 import Maybes ( maybeToBool, orElse )
45 import ErrUtils ( showPass )
46 import SrcLoc ( noSrcLoc )
47 import UniqFM ( mapUFM )
48 import UniqSupply ( splitUniqSupply, uniqFromSupply )
49 import List ( partition )
50 import Util ( mapAccumL )
56 %************************************************************************
58 \subsection{What goes on}
60 %************************************************************************
66 Step 1: Figure out external Ids
67 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
68 First we figure out which Ids are "external" Ids. An
69 "external" Id is one that is visible from outside the compilation
71 a) the user exported ones
72 b) ones mentioned in the unfoldings, workers,
73 or rules of externally-visible ones
74 This exercise takes a sweep of the bindings bottom to top. Actually,
75 in Step 2 we're also going to need to know which Ids should be
76 exported with their unfoldings, so we produce not an IdSet but an
80 Step 2: Tidy the program
81 ~~~~~~~~~~~~~~~~~~~~~~~~
82 Next we traverse the bindings top to bottom. For each *top-level*
85 1. Make it into a GlobalId
87 2. Give it a system-wide Unique.
88 [Even non-exported things need system-wide Uniques because the
89 byte-code generator builds a single Name->BCO symbol table.]
91 We use the NameSupply kept in the PersistentRenamerState as the
92 source of such system-wide uniques.
94 For external Ids, use the original-name cache in the NameSupply
95 to ensure that the unique assigned is the same as the Id had
96 in any previous compilation run.
98 3. If it's an external Id, make it have a global Name and vice versa.
99 This is used by the code generator to decide whether
100 to make the label externally visible
102 4. Give external Ids a "tidy" occurrence name. This means
103 we can print them in interface files without confusing
104 "x" (unique 5) with "x" (unique 10).
106 5. Give it its UTTERLY FINAL IdInfo; in ptic,
107 * Its IdDetails becomes VanillaGlobal, reflecting the fact that
108 from now on we regard it as a global, not local, Id
110 * its unfolding, if it should have one
112 * its arity, computed from the number of visible lambdas
114 * its CAF info, computed from what is free in its RHS
117 Finally, substitute these new top-level binders consistently
118 throughout, including in unfoldings. We also tidy binders in
119 RHSs, so that they print nicely in interfaces.
122 tidyCorePgm :: DynFlags -> Module
123 -> PersistentCompilerState
124 -> CgInfoEnv -- Information from the back end,
125 -- to be splatted into the IdInfo
127 -> IO (PersistentCompilerState, ModDetails)
129 tidyCorePgm dflags mod pcs cg_info_env
130 (ModDetails { md_types = env_tc, md_insts = insts_tc,
131 md_binds = binds_in, md_rules = orphans_in })
132 = do { showPass dflags "Tidy Core"
134 ; let ext_ids = findExternalSet binds_in orphans_in
135 ; let ext_rules = findExternalRules binds_in orphans_in ext_ids
137 -- We also make sure to avoid any exported binders. Consider
138 -- f{-u1-} = 1 -- Local decl
140 -- f{-u2-} = 2 -- Exported decl
142 -- The second exported decl must 'get' the name 'f', so we
143 -- have to put 'f' in the avoids list before we get to the first
144 -- decl. tidyTopId then does a no-op on exported binders.
145 ; let prs = pcs_PRS pcs
146 orig_ns = prsOrig prs
148 init_tidy_env = (orig_ns, initTidyOccEnv avoids, emptyVarEnv)
149 avoids = [getOccName bndr | bndr <- bindersOfBinds binds_in,
150 isGlobalName (idName bndr)]
152 ; let ((orig_ns', occ_env, subst_env), tidy_binds)
153 = mapAccumL (tidyTopBind mod ext_ids cg_info_env)
154 init_tidy_env binds_in
156 ; let tidy_rules = tidyIdRules (occ_env,subst_env) ext_rules
158 ; let prs' = prs { prsOrig = orig_ns' }
159 pcs' = pcs { pcs_PRS = prs' }
161 ; let final_ids = [ id | bind <- tidy_binds
162 , id <- bindersOf bind
163 , isGlobalName (idName id)]
165 -- Dfuns are local Ids that might have
166 -- changed their unique during tidying
167 ; let lookup_dfun_id id = lookupVarEnv subst_env id `orElse`
168 pprPanic "lookup_dfun_id" (ppr id)
171 ; let tidy_type_env = mkFinalTypeEnv env_tc final_ids
172 tidy_dfun_ids = map lookup_dfun_id insts_tc
174 ; let tidy_details = ModDetails { md_types = tidy_type_env,
175 md_rules = tidy_rules,
176 md_insts = tidy_dfun_ids,
177 md_binds = tidy_binds }
179 ; endPass dflags "Tidy Core" Opt_D_dump_simpl tidy_binds
181 ; return (pcs', tidy_details)
184 tidyCoreExpr :: CoreExpr -> IO CoreExpr
185 tidyCoreExpr expr = return (tidyExpr emptyTidyEnv expr)
189 %************************************************************************
191 \subsection{Write a new interface file}
193 %************************************************************************
196 mkFinalTypeEnv :: TypeEnv -- From typechecker
200 mkFinalTypeEnv type_env final_ids
201 = extendTypeEnvList (filterNameEnv keep_it type_env)
204 -- The competed type environment is gotten from
205 -- a) keeping the types and classes
206 -- b) removing all Ids,
207 -- c) adding Ids with correct IdInfo, including unfoldings,
208 -- gotten from the bindings
209 -- From (c) we keep only those Ids with Global names;
210 -- the CoreTidy pass makes sure these are all and only
211 -- the externally-accessible ones
212 -- This truncates the type environment to include only the
213 -- exported Ids and things needed from them, which saves space
215 -- However, we do keep things like constructors, which should not appear
216 -- in interface files, because they are needed by importing modules when
217 -- using the compilation manager
219 -- We keep "hasNoBinding" Ids, notably constructor workers,
220 -- because they won't appear in the bindings from which final_ids are derived!
221 keep_it (AnId id) = hasNoBinding id -- Remove all Ids except constructor workers
222 keep_it other = True -- Keep all TyCons and Classes
226 findExternalRules :: [CoreBind]
227 -> [IdCoreRule] -- Orphan rules
228 -> IdEnv a -- Ids that are exported, so we need their rules
230 -- The complete rules are gotten by combining
231 -- a) the orphan rules
232 -- b) rules embedded in the top-level Ids
233 findExternalRules binds orphan_rules ext_ids
234 | opt_OmitInterfacePragmas = []
236 = orphan_rules ++ local_rules
238 local_rules = [ (id, rule)
239 | id <- bindersOfBinds binds,
240 id `elemVarEnv` ext_ids,
241 rule <- rulesRules (idSpecialisation id),
242 not (isBuiltinRule rule)
243 -- We can't print builtin rules in interface files
244 -- Since they are built in, an importing module
245 -- will have access to them anyway
249 %************************************************************************
251 \subsection{Step 1: finding externals}
253 %************************************************************************
256 findExternalSet :: [CoreBind] -> [IdCoreRule]
257 -> IdEnv Bool -- In domain => external
258 -- Range = True <=> show unfolding
259 -- Step 1 from the notes above
260 findExternalSet binds orphan_rules
261 = foldr find init_needed binds
263 orphan_rule_ids :: IdSet
264 orphan_rule_ids = unionVarSets [ ruleSomeFreeVars isLocalId rule
265 | (_, rule) <- orphan_rules]
266 init_needed :: IdEnv Bool
267 init_needed = mapUFM (\_ -> False) orphan_rule_ids
268 -- The mapUFM is a bit cheesy. It is a cheap way
269 -- to turn the set of orphan_rule_ids, which we use to initialise
270 -- the sweep, into a mapping saying 'don't expose unfolding'
271 -- (When we come to the binding site we may change our mind, of course.)
273 find (NonRec id rhs) needed
274 | need_id needed id = addExternal (id,rhs) needed
276 find (Rec prs) needed = find_prs prs needed
278 -- For a recursive group we have to look for a fixed point
280 | null needed_prs = needed
281 | otherwise = find_prs other_prs new_needed
283 (needed_prs, other_prs) = partition (need_pr needed) prs
284 new_needed = foldr addExternal needed needed_prs
286 -- The 'needed' set contains the Ids that are needed by earlier
287 -- interface file emissions. If the Id isn't in this set, and isn't
288 -- exported, there's no need to emit anything
289 need_id needed_set id = id `elemVarEnv` needed_set || isExportedId id
290 need_pr needed_set (id,rhs) = need_id needed_set id
292 addExternal :: (Id,CoreExpr) -> IdEnv Bool -> IdEnv Bool
293 -- The Id is needed; extend the needed set
294 -- with it and its dependents (free vars etc)
295 addExternal (id,rhs) needed
296 = extendVarEnv (foldVarSet add_occ needed new_needed_ids)
299 add_occ id needed = extendVarEnv needed id False
300 -- "False" because we don't know we need the Id's unfolding
301 -- We'll override it later when we find the binding site
303 new_needed_ids | opt_OmitInterfacePragmas = emptyVarSet
304 | otherwise = worker_ids `unionVarSet`
305 unfold_ids `unionVarSet`
309 dont_inline = isNeverInlinePrag (inlinePragInfo idinfo)
310 loop_breaker = isLoopBreaker (occInfo idinfo)
311 bottoming_fn = isBottomingSig (newStrictnessInfo idinfo `orElse` topSig)
312 spec_ids = rulesRhsFreeVars (specInfo idinfo)
313 worker_info = workerInfo idinfo
315 -- Stuff to do with the Id's unfolding
316 -- The simplifier has put an up-to-date unfolding
317 -- in the IdInfo, but the RHS will do just as well
318 unfolding = unfoldingInfo idinfo
319 rhs_is_small = not (neverUnfold unfolding)
321 -- We leave the unfolding there even if there is a worker
322 -- In GHCI the unfolding is used by importers
323 -- When writing an interface file, we omit the unfolding
324 -- if there is a worker
325 show_unfold = not bottoming_fn && -- Not necessary
328 rhs_is_small && -- Small enough
329 okToUnfoldInHiFile rhs -- No casms etc
331 unfold_ids | show_unfold = exprSomeFreeVars isLocalId rhs
332 | otherwise = emptyVarSet
334 worker_ids = case worker_info of
335 HasWorker work_id _ -> unitVarSet work_id
336 otherwise -> emptyVarSet
340 %************************************************************************
342 \subsection{Step 2: top-level tidying}
344 %************************************************************************
348 type TopTidyEnv = (NameSupply, TidyOccEnv, VarEnv Var)
350 -- TopTidyEnv: when tidying we need to know
351 -- * ns: The NameSupply, containing a unique supply and any pre-ordained Names.
352 -- These may have arisen because the
353 -- renamer read in an interface file mentioning M.$wf, say,
354 -- and assigned it unique r77. If, on this compilation, we've
355 -- invented an Id whose name is $wf (but with a different unique)
356 -- we want to rename it to have unique r77, so that we can do easy
357 -- comparisons with stuff from the interface file
359 -- * occ_env: The TidyOccEnv, which tells us which local occurrences
362 -- * subst_env: A Var->Var mapping that substitutes the new Var for the old
367 tidyTopBind :: Module
368 -> IdEnv Bool -- Domain = Ids that should be external
369 -- True <=> their unfolding is external too
371 -> TopTidyEnv -> CoreBind
372 -> (TopTidyEnv, CoreBind)
374 tidyTopBind mod ext_ids cg_info_env top_tidy_env (NonRec bndr rhs)
375 = ((orig,occ,subst) , NonRec bndr' rhs')
377 ((orig,occ,subst), bndr')
378 = tidyTopBinder mod ext_ids cg_info_env rec_tidy_env rhs' top_tidy_env bndr
379 rec_tidy_env = (occ,subst)
380 rhs' = tidyExpr rec_tidy_env rhs
382 tidyTopBind mod ext_ids cg_info_env top_tidy_env (Rec prs)
383 = (final_env, Rec prs')
385 (final_env@(_,occ,subst), prs') = mapAccumL do_one top_tidy_env prs
386 rec_tidy_env = (occ,subst)
388 do_one top_tidy_env (bndr,rhs)
389 = ((orig,occ,subst), (bndr',rhs'))
391 ((orig,occ,subst), bndr')
392 = tidyTopBinder mod ext_ids cg_info_env
393 rec_tidy_env rhs' top_tidy_env bndr
395 rhs' = tidyExpr rec_tidy_env rhs
397 tidyTopBinder :: Module -> IdEnv Bool
399 -> TidyEnv -> CoreExpr
400 -- The TidyEnv is used to tidy the IdInfo
401 -- The expr is the already-tided RHS
402 -- Both are knot-tied: don't look at them!
403 -> TopTidyEnv -> Id -> (TopTidyEnv, Id)
404 -- NB: tidyTopBinder doesn't affect the unique supply
406 tidyTopBinder mod ext_ids cg_info_env tidy_env rhs
407 env@(ns2, occ_env2, subst_env2) id
409 | isDataConWrapId id -- Don't tidy constructor wrappers
410 = (env, id) -- The Id is stored in the TyCon, so it would be bad
411 -- if anything changed
413 -- HACK ALERT: we *do* tidy record selectors. Reason: they mention error
414 -- messages, which may be floated out:
415 -- x_field pt = case pt of
417 -- Pol _ _ -> error "buggle wuggle"
418 -- The error message will be floated out so we'll get
419 -- lvl5 = error "buggle wuggle"
420 -- x_field pt = case pt of
424 -- When this happens, it's vital that the Id exposed to importing modules
425 -- (by ghci) mentions lvl5 in its unfolding, not the un-tidied version.
427 -- What about the Id in the TyCon? It probably shouldn't be in the TyCon at
428 -- all, but in any case it will have the error message inline so it won't matter.
431 | isRecordSelector id -- We can't use the "otherwise" case, because that
432 -- forgets the IdDetails, which forgets that this is
433 -- a record selector, which confuses an importing module
434 = (env, id `setIdUnfolding` unfold_info)
437 -- This function is the heart of Step 2
438 -- The second env is the one to use for the IdInfo
439 -- It's necessary because when we are dealing with a recursive
440 -- group, a variable late in the group might be mentioned
441 -- in the IdInfo of one early in the group
443 -- The rhs is already tidied
445 = ((orig_env', occ_env', subst_env'), id')
447 (orig_env', occ_env', name') = tidyTopName mod ns2 occ_env2
450 ty' = tidyTopType (idType id)
451 cg_info = lookupCgInfo cg_info_env name'
452 idinfo' = tidyIdInfo tidy_env is_external unfold_info cg_info id
454 id' = mkVanillaGlobal name' ty' idinfo'
455 subst_env' = extendVarEnv subst_env2 id id'
457 maybe_external = lookupVarEnv ext_ids id
458 is_external = maybeToBool maybe_external
460 -- Expose an unfolding if ext_ids tells us to
461 show_unfold = maybe_external `orElse` False
462 unfold_info | show_unfold = mkTopUnfolding rhs
463 | otherwise = noUnfolding
466 tidyIdInfo tidy_env is_external unfold_info cg_info id
467 | opt_OmitInterfacePragmas || not is_external
468 -- No IdInfo if the Id isn't external, or if we don't have -O
471 `setNewStrictnessInfo` newStrictnessInfo core_idinfo
472 -- Keep strictness; it's used by CorePrep
477 `setNewStrictnessInfo` newStrictnessInfo core_idinfo
478 `setInlinePragInfo` inlinePragInfo core_idinfo
479 `setUnfoldingInfo` unfold_info
480 `setWorkerInfo` tidyWorker tidy_env (workerInfo core_idinfo)
481 -- NB: we throw away the Rules
482 -- They have already been extracted by findExternalRules
484 core_idinfo = idInfo id
487 -- This is where we set names to local/global based on whether they really are
488 -- externally visible (see comment at the top of this module). If the name
489 -- was previously local, we have to give it a unique occurrence name if
490 -- we intend to globalise it.
491 tidyTopName mod ns occ_env external name
492 | global && internal = (ns, occ_env, localiseName name)
494 | global && external = (ns, occ_env, name)
495 -- Global names are assumed to have been allocated by the renamer,
496 -- so they already have the "right" unique
497 -- And it's a system-wide unique too
499 | local && internal = (ns { nsUniqs = us2 }, occ_env', unique_name)
500 -- Even local, internal names must get a unique occurrence, because
501 -- if we do -split-objs we globalise the name later, in the code generator
503 -- Similarly, we must make sure it has a system-wide Unique, because
504 -- the byte-code generator builds a system-wide Name->BCO symbol table
506 | local && external = case lookupFM ns_names key of
507 Just orig -> (ns, occ_env', orig)
508 Nothing -> (ns { nsUniqs = us2, nsNames = ns_names' }, occ_env', global_name)
509 -- If we want to globalise a currently-local name, check
510 -- whether we have already assigned a unique for it.
511 -- If so, use it; if not, extend the table
514 global = isGlobalName name
516 internal = not external
518 (occ_env', occ') = tidyOccName occ_env (nameOccName name)
519 key = (moduleName mod, occ')
520 ns_names = nsNames ns
521 ns_uniqs = nsUniqs ns
522 (us1, us2) = splitUniqSupply ns_uniqs
523 unique_name = setNameUnique (setNameOcc name occ') (uniqFromSupply us1)
524 global_name = globaliseName unique_name mod
525 ns_names' = addToFM ns_names key global_name
528 ------------ Worker --------------
529 tidyWorker tidy_env (HasWorker work_id wrap_arity)
530 = HasWorker (tidyVarOcc tidy_env work_id) wrap_arity
531 tidyWorker tidy_env other
534 ------------ Rules --------------
535 tidyIdRules :: TidyEnv -> [IdCoreRule] -> [IdCoreRule]
536 tidyIdRules env [] = []
537 tidyIdRules env ((fn,rule) : rules)
538 = tidyRule env rule =: \ rule ->
539 tidyIdRules env rules =: \ rules ->
540 ((tidyVarOcc env fn, rule) : rules)
542 tidyRule :: TidyEnv -> CoreRule -> CoreRule
543 tidyRule env rule@(BuiltinRule _) = rule
544 tidyRule env (Rule name vars tpl_args rhs)
545 = tidyBndrs env vars =: \ (env', vars) ->
546 map (tidyExpr env') tpl_args =: \ tpl_args ->
547 (Rule name vars tpl_args (tidyExpr env' rhs))
550 %************************************************************************
552 \subsection{Step 2: inner tidying
554 %************************************************************************
559 -> (TidyEnv, CoreBind)
561 tidyBind env (NonRec bndr rhs)
562 = tidyBndrWithRhs env (bndr,rhs) =: \ (env', bndr') ->
563 (env', NonRec bndr' (tidyExpr env' rhs))
565 tidyBind env (Rec prs)
566 = mapAccumL tidyBndrWithRhs env prs =: \ (env', bndrs') ->
567 map (tidyExpr env') (map snd prs) =: \ rhss' ->
568 (env', Rec (zip bndrs' rhss'))
571 tidyExpr env (Var v) = Var (tidyVarOcc env v)
572 tidyExpr env (Type ty) = Type (tidyType env ty)
573 tidyExpr env (Lit lit) = Lit lit
574 tidyExpr env (App f a) = App (tidyExpr env f) (tidyExpr env a)
575 tidyExpr env (Note n e) = Note (tidyNote env n) (tidyExpr env e)
577 tidyExpr env (Let b e)
578 = tidyBind env b =: \ (env', b') ->
579 Let b' (tidyExpr env' e)
581 tidyExpr env (Case e b alts)
582 = tidyBndr env b =: \ (env', b) ->
583 Case (tidyExpr env e) b (map (tidyAlt env') alts)
585 tidyExpr env (Lam b e)
586 = tidyBndr env b =: \ (env', b) ->
587 Lam b (tidyExpr env' e)
590 tidyAlt env (con, vs, rhs)
591 = tidyBndrs env vs =: \ (env', vs) ->
592 (con, vs, tidyExpr env' rhs)
594 tidyNote env (Coerce t1 t2) = Coerce (tidyType env t1) (tidyType env t2)
595 tidyNote env note = note
599 %************************************************************************
601 \subsection{Tidying up non-top-level binders}
603 %************************************************************************
606 tidyVarOcc (_, var_env) v = case lookupVarEnv var_env v of
610 -- tidyBndr is used for lambda and case binders
611 tidyBndr :: TidyEnv -> Var -> (TidyEnv, Var)
613 | isTyVar var = tidyTyVar env var
614 | otherwise = tidyId env var
616 tidyBndrs :: TidyEnv -> [Var] -> (TidyEnv, [Var])
617 tidyBndrs env vars = mapAccumL tidyBndr env vars
619 -- tidyBndrWithRhs is used for let binders
620 tidyBndrWithRhs :: TidyEnv -> (Id, CoreExpr) -> (TidyEnv, Var)
621 tidyBndrWithRhs env (id,rhs)
622 = add_dmd_info (tidyId env id)
624 -- We add demand info for let(rec) binders, because
625 -- that's what tells CorePrep to generate a case instead of a thunk
626 add_dmd_info (env,new_id)
627 | isStrictDmd dmd_info = (env, setIdNewDemandInfo new_id dmd_info)
628 | otherwise = (env, new_id)
629 dmd_info = idNewDemandInfo id
631 tidyId :: TidyEnv -> Id -> (TidyEnv, Id)
632 tidyId env@(tidy_env, var_env) id
633 = -- Non-top-level variables
635 -- Give the Id a fresh print-name, *and* rename its type
636 -- The SrcLoc isn't important now,
637 -- though we could extract it from the Id
639 -- All local Ids now have the same IdInfo, which should save some
641 (tidy_env', occ') = tidyOccName tidy_env (getOccName id)
642 ty' = tidyType (tidy_env,var_env) (idType id)
643 id' = mkUserLocal occ' (idUnique id) ty' noSrcLoc
644 var_env' = extendVarEnv var_env id id'
646 ((tidy_env', var_env'), id')