TidyPgm.lhs 55 KB
Newer Older
Simon Marlow's avatar
Simon Marlow committed
1

2 3 4 5 6
% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
%
\section{Tidying up Core}

\begin{code}
7 8 9
module TidyPgm (
       mkBootModDetailsTc, tidyProgram, globaliseAndTidyId
   ) where
10 11 12

#include "HsVersions.h"

Simon Marlow's avatar
Simon Marlow committed
13
import TcRnTypes
Simon Marlow's avatar
Simon Marlow committed
14
import DynFlags
15
import CoreSyn
Simon Marlow's avatar
Simon Marlow committed
16 17 18
import CoreUnfold
import CoreFVs
import CoreTidy
19
import CoreMonad
20
import CorePrep
Simon Marlow's avatar
Simon Marlow committed
21
import CoreUtils
22
import Literal
23
import Rules
24
import CoreArity        ( exprArity, exprBotStrictness_maybe )
25 26
import VarEnv
import VarSet
27
import Var
Simon Marlow's avatar
Simon Marlow committed
28 29 30
import Id
import IdInfo
import InstEnv
31
import FamInstEnv
Simon Peyton Jones's avatar
Simon Peyton Jones committed
32
import Type             ( tidyTopType )
33
import Demand           ( appIsBottom, isTopSig, isBottomingSig )
Simon Marlow's avatar
Simon Marlow committed
34
import BasicTypes
35
import Name hiding (varName)
Simon Marlow's avatar
Simon Marlow committed
36 37
import NameSet
import NameEnv
38 39
import Avail
import IfaceEnv
40 41
import TcEnv
import TcRnMonad
Simon Marlow's avatar
Simon Marlow committed
42 43
import DataCon
import TyCon
44
import Class
45
import Module
46
import Packages( isDllName )
47
import HscTypes
Simon Marlow's avatar
Simon Marlow committed
48 49
import Maybes
import UniqSupply
50
import ErrUtils (Severity(..))
51
import Outputable
Ian Lynagh's avatar
Ian Lynagh committed
52
import FastBool hiding ( fastOr )
53
import SrcLoc
54
import Util
55
import FastString
56
import qualified ErrUtils as Err
Simon Marlow's avatar
Simon Marlow committed
57

58
import Control.Monad
Ian Lynagh's avatar
Ian Lynagh committed
59
import Data.Function
60
import Data.List        ( sortBy )
61
import Data.IORef       ( atomicModifyIORef )
62 63 64
\end{code}


65 66 67
Constructing the TypeEnv, Instances, Rules, VectInfo from which the
ModIface is constructed, and which goes on to subsequent modules in
--make mode.
68 69 70 71 72 73 74 75

Most of the interface file is obtained simply by serialising the
TypeEnv.  One important consequence is that if the *interface file*
has pragma info if and only if the final TypeEnv does. This is not so
important for *this* module, but it's essential for ghc --make:
subsequent compilations must not see (e.g.) the arity if the interface
file does not contain arity If they do, they'll exploit the arity;
then the arity might change, but the iface file doesn't change =>
76
recompilation does not happen => disaster.
77 78 79 80 81 82 83

For data types, the final TypeEnv will have a TyThing for the TyCon,
plus one for each DataCon; the interface file will contain just one
data type declaration, but it is de-serialised back into a collection
of TyThings.

%************************************************************************
84 85 86
%*                                                                      *
                Plan A: simpleTidyPgm
%*                                                                      *
87 88 89
%************************************************************************


90
Plan A: mkBootModDetails: omit pragmas, make interfaces small
91 92 93
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Ignore the bindings

94 95
* Drop all WiredIn things from the TypeEnv
        (we never want them in interface files)
96 97

* Retain all TyCons and Classes in the TypeEnv, to avoid
98 99
        having to find which ones are mentioned in the
        types of exported Ids
100 101

* Trim off the constructors of non-exported TyCons, both
102
        from the TyCon and from the TypeEnv
103 104 105

* Drop non-exported Ids from the TypeEnv

106
* Tidy the types of the DFunIds of Instances,
107 108 109 110 111 112 113 114
  make them into GlobalIds, (they already have External Names)
  and add them to the TypeEnv

* Tidy the types of the (exported) Ids in the TypeEnv,
  make them into GlobalIds (they already have External Names)

* Drop rules altogether

115
* Tidy the bindings, to ensure that the Caf and Arity
116
  information is correct for each top-level binder; the
117 118
  code generator needs it. And to ensure that local names have
  distinct OccNames in case of object-file splitting
119 120 121 122

\begin{code}
-- This is Plan A: make a small type env when typechecking only,
-- or when compiling a hs-boot file, or simply when not using -O
123 124 125
--
-- We don't look at the bindings at all -- there aren't any
-- for hs-boot files
126

Simon Marlow's avatar
Simon Marlow committed
127
mkBootModDetailsTc :: HscEnv -> TcGblEnv -> IO ModDetails
128
mkBootModDetailsTc hsc_env
Simon Marlow's avatar
Simon Marlow committed
129
        TcGblEnv{ tcg_exports   = exports,
130 131
                  tcg_type_env  = type_env, -- just for the Ids
                  tcg_tcs       = tcs,
Simon Marlow's avatar
Simon Marlow committed
132 133 134
                  tcg_insts     = insts,
                  tcg_fam_insts = fam_insts
                }
135
  = do  { let dflags = hsc_dflags hsc_env
136
        ; showPass dflags CoreTidy
137

138
        ; let { insts'     = map (tidyClsInstDFun globaliseAndTidyId) insts
139
              ; dfun_ids   = map instanceDFunId insts'
140
              ; type_env1  = mkBootTypeEnv (availsToNameSet exports)
dreixel's avatar
dreixel committed
141
                                (typeEnvIds type_env) tcs fam_insts
142 143 144 145 146 147 148 149
              ; type_env'  = extendTypeEnvWithIds type_env1 dfun_ids
              }
        ; return (ModDetails { md_types     = type_env'
                             , md_insts     = insts'
                             , md_fam_insts = fam_insts
                             , md_rules     = []
                             , md_anns      = []
                             , md_exports   = exports
chak@cse.unsw.edu.au.'s avatar
chak@cse.unsw.edu.au. committed
150
                             , md_vect_info = noVectInfo
151
                             })
152
        }
153 154
  where

155
mkBootTypeEnv :: NameSet -> [Id] -> [TyCon] -> [FamInst] -> TypeEnv
dreixel's avatar
dreixel committed
156
mkBootTypeEnv exports ids tcs fam_insts
157
  = tidyTypeEnv True $
dreixel's avatar
dreixel committed
158
       typeEnvFromEntities final_ids tcs fam_insts
159
  where
160
        -- Find the LocalIds in the type env that are exported
161 162 163 164 165 166
        -- Make them into GlobalIds, and tidy their types
        --
        -- It's very important to remove the non-exported ones
        -- because we don't tidy the OccNames, and if we don't remove
        -- the non-exported ones we'll get many things with the
        -- same name in the interface file, giving chaos.
167 168 169 170 171 172 173 174
        --
        -- Do make sure that we keep Ids that are already Global.
        -- When typechecking an .hs-boot file, the Ids come through as
        -- GlobalIds.
    final_ids = [ if isLocalId id then globaliseAndTidyId id
                                  else id
                | id <- ids
                , keep_it id ]
175 176 177 178 179

        -- default methods have their export flag set, but everything
        -- else doesn't (yet), because this is pre-desugaring, so we
        -- must test both.
    keep_it id = isExportedId id || idName id `elemNameSet` exports
180 181


182 183

globaliseAndTidyId :: Id -> Id
184 185
-- Takes an LocalId with an External Name,
-- makes it into a GlobalId
186 187 188
--     * unchanged Name (might be Internal or External)
--     * unchanged details
--     * VanillaIdInfo (makes a conservative assumption about Caf-hood)
189
globaliseAndTidyId id
190 191 192
  = Id.setIdType (globaliseId id) tidy_type
  where
    tidy_type = tidyTopType (idType id)
193 194 195
\end{code}


196
%************************************************************************
197 198 199
%*                                                                      *
        Plan B: tidy bindings, make TypeEnv full of IdInfo
%*                                                                      *
200 201
%************************************************************************

202
Plan B: include pragmas, make interfaces
203 204 205 206
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Figure out which Ids are externally visible

* Tidy the bindings, externalising appropriate Ids
207

208
* Drop all Ids from the TypeEnv, and add all the External Ids from
209 210
  the bindings.  (This adds their IdInfo to the TypeEnv; and adds
  floated-out Ids that weren't even in the TypeEnv before.)
211 212 213

Step 1: Figure out external Ids
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
214 215
Note [choosing external names]

Simon Marlow's avatar
Simon Marlow committed
216 217 218 219
See also the section "Interface stability" in the
RecompilationAvoidance commentary:
  http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/RecompilationAvoidance

220 221 222
First we figure out which Ids are "external" Ids.  An
"external" Id is one that is visible from outside the compilation
unit.  These are
223
  a) the user exported ones
224
  b) ones mentioned in the unfoldings, workers,
225 226
     rules of externally-visible ones ,
     or vectorised versions of externally-visible ones
227

228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252
While figuring out which Ids are external, we pick a "tidy" OccName
for each one.  That is, we make its OccName distinct from the other
external OccNames in this module, so that in interface files and
object code we can refer to it unambiguously by its OccName.  The
OccName for each binder is prefixed by the name of the exported Id
that references it; e.g. if "f" references "x" in its unfolding, then
"x" is renamed to "f_x".  This helps distinguish the different "x"s
from each other, and means that if "f" is later removed, things that
depend on the other "x"s will not need to be recompiled.  Of course,
if there are multiple "f_x"s, then we have to disambiguate somehow; we
use "f_x0", "f_x1" etc.

As far as possible we should assign names in a deterministic fashion.
Each time this module is compiled with the same options, we should end
up with the same set of external names with the same types.  That is,
the ABI hash in the interface should not change.  This turns out to be
quite tricky, since the order of the bindings going into the tidy
phase is already non-deterministic, as it is based on the ordering of
Uniques, which are assigned unpredictably.

To name things in a stable way, we do a depth-first-search of the
bindings, starting from the exports sorted by name.  This way, as long
as the bindings themselves are deterministic (they sometimes aren't!),
the order in which they are presented to the tidying phase does not
affect the names we assign.
253 254 255 256 257 258

Step 2: Tidy the program
~~~~~~~~~~~~~~~~~~~~~~~~
Next we traverse the bindings top to bottom.  For each *top-level*
binder

259 260
 1. Make it into a GlobalId; its IdDetails becomes VanillaGlobal,
    reflecting the fact that from now on we regard it as a global,
261
    not local, Id
262 263 264 265 266

 2. Give it a system-wide Unique.
    [Even non-exported things need system-wide Uniques because the
    byte-code generator builds a single Name->BCO symbol table.]

267
    We use the NameCache kept in the HscEnv as the
268 269
    source of such system-wide uniques.

270
    For external Ids, use the original-name cache in the NameCache
271
    to ensure that the unique assigned is the same as the Id had
272
    in any previous compilation run.
273 274 275 276 277 278

 3. Rename top-level Ids according to the names we chose in step 1.
    If it's an external Id, make it have a External Name, otherwise
    make it have an Internal Name.  This is used by the code generator
    to decide whether to make the label externally visible

279 280 281 282 283 284
 4. Give it its UTTERLY FINAL IdInfo; in ptic,
        * its unfolding, if it should have one

        * its arity, computed from the number of visible lambdas

        * its CAF info, computed from what is free in its RHS
285 286 287 288 289 290 291


Finally, substitute these new top-level binders consistently
throughout, including in unfoldings.  We also tidy binders in
RHSs, so that they print nicely in interfaces.

\begin{code}
292
tidyProgram :: HscEnv -> ModGuts -> IO (CgGuts, ModDetails)
293 294
tidyProgram hsc_env  (ModGuts { mg_module    = mod
                              , mg_exports   = exports
295
                              , mg_tcs       = tcs
296 297 298 299 300 301
                              , mg_insts     = insts
                              , mg_fam_insts = fam_insts
                              , mg_binds     = binds
                              , mg_rules     = imp_rules
                              , mg_vect_info = vect_info
                              , mg_anns      = anns
302
                              , mg_deps      = deps
303 304
                              , mg_foreign   = foreign_stubs
                              , mg_hpc_info  = hpc_info
305
                              , mg_modBreaks = modBreaks
306 307 308
                              })

  = do  { let { dflags     = hsc_dflags hsc_env
ian@well-typed.com's avatar
ian@well-typed.com committed
309 310
              ; omit_prags = gopt Opt_OmitInterfacePragmas dflags
              ; expose_all = gopt Opt_ExposeAllUnfoldings  dflags
311
              }
312
        ; showPass dflags CoreTidy
313

dreixel's avatar
dreixel committed
314
        ; let { type_env = typeEnvFromEntities [] tcs fam_insts
315 316 317 318 319

              ; implicit_binds
                  = concatMap getClassImplicitBinds (typeEnvClasses type_env) ++
                    concatMap getTyConImplicitBinds (typeEnvTyCons type_env)
              }
320

321
        ; (unfold_env, tidy_occ_env)
322
              <- chooseExternalIds hsc_env mod omit_prags expose_all
323
                                   binds implicit_binds imp_rules (vectInfoVar vect_info)
324
        ; let { ext_rules = findExternalRules omit_prags binds imp_rules unfold_env }
325 326 327
                -- Glom together imp_rules and rules currently attached to binders
                -- Then pick just the ones we need to expose
                -- See Note [Which rules to expose]
328

329
        ; (tidy_env, tidy_binds)
330
                 <- tidyTopBinds hsc_env mod unfold_env tidy_occ_env binds
331

332
        ; let { final_ids  = [ id | id <- bindersOfBinds tidy_binds,
333
                                    isExternalName (idName id)]
334

335
              ; tidy_type_env = tidyTypeEnv omit_prags
336 337
                                      (extendTypeEnvWithIds type_env final_ids)

338
              ; tidy_insts    = map (tidyClsInstDFun (lookup_dfun tidy_type_env)) insts
339 340 341 342 343
                -- A DFunId will have a binding in tidy_binds, and so
                -- will now be in final_env, replete with IdInfo
                -- Its name will be unchanged since it was born, but
                -- we want Global, IdInfo-rich (or not) DFunId in the
                -- tidy_insts
344

345 346 347 348
              ; tidy_rules = tidyRules tidy_env ext_rules
                -- You might worry that the tidy_env contains IdInfo-rich stuff
                -- and indeed it does, but if omit_prags is on, ext_rules is
                -- empty
349

350 351
              ; tidy_vect_info = tidyVectInfo tidy_env vect_info

352 353
              -- See Note [Injecting implicit bindings]
              ; all_tidy_binds = implicit_binds ++ tidy_binds
354

355 356 357 358 359 360 361 362
              -- get the TyCons to generate code for.  Careful!  We must use
              -- the untidied TypeEnv here, because we need
              --  (a) implicit TyCons arising from types and classes defined
              --      in this module
              --  (b) wired-in TyCons, which are normally removed from the
              --      TypeEnv we put in the ModDetails
              --  (c) Constructors even if they are not exported (the
              --      tidied TypeEnv has trimmed these away)
363 364
              ; alg_tycons = filter isAlgTyCon (typeEnvTyCons type_env)
              }
365

366
        ; endPass hsc_env CoreTidy all_tidy_binds tidy_rules
367

368 369
          -- If the endPass didn't print the rules, but ddump-rules is
          -- on, print now
370
        ; unless (dopt Opt_D_dump_simpl dflags) $
371 372 373
            Err.dumpIfSet_dyn dflags Opt_D_dump_rules
              (showSDoc dflags (ppr CoreTidy <+> ptext (sLit "rules")))
              (pprRulesForUser tidy_rules)
374

375 376
          -- Print one-line size info
        ; let cs = coreBindsStats tidy_binds
377
        ; when (dopt Opt_D_dump_core_stats dflags)
Ian Lynagh's avatar
Ian Lynagh committed
378
               (log_action dflags dflags SevDump noSrcSpan defaultDumpStyle
379
                          (ptext (sLit "Tidy size (terms,types,coercions)")
380 381 382
                           <+> ppr (moduleName mod) <> colon
                           <+> int (cs_tm cs)
                           <+> int (cs_ty cs)
383 384
                           <+> int (cs_co cs) ))

385 386 387 388
        ; return (CgGuts { cg_module   = mod,
                           cg_tycons   = alg_tycons,
                           cg_binds    = all_tidy_binds,
                           cg_foreign  = foreign_stubs,
389 390
                           cg_dep_pkgs = map fst $ dep_pkgs deps,
                           cg_hpc_info = hpc_info,
391
                           cg_modBreaks = modBreaks },
392

393
                   ModDetails { md_types     = tidy_type_env,
394 395
                                md_rules     = tidy_rules,
                                md_insts     = tidy_insts,
396 397
                                md_vect_info = tidy_vect_info,
                                md_fam_insts = fam_insts,
398 399
                                md_exports   = exports,
                                md_anns      = anns      -- are already tidy
chak@cse.unsw.edu.au.'s avatar
chak@cse.unsw.edu.au. committed
400
                              })
401
        }
402

Simon Marlow's avatar
Simon Marlow committed
403
lookup_dfun :: TypeEnv -> Var -> Id
404 405
lookup_dfun type_env dfun_id
  = case lookupTypeEnv type_env (idName dfun_id) of
406 407
        Just (AnId dfun_id') -> dfun_id'
        _other -> pprPanic "lookup_dfun" (ppr dfun_id)
408

409
--------------------------
410
tidyTypeEnv :: Bool       -- Compiling without -O, so omit prags
411
            -> TypeEnv -> TypeEnv
412

413
-- The competed type environment is gotten from
414 415
--      a) the types and classes defined here (plus implicit things)
--      b) adding Ids with correct IdInfo, including unfoldings,
416
--              gotten from the bindings
417
-- From (b) we keep only those Ids with External names;
418 419 420
--          the CoreTidy pass makes sure these are all and only
--          the externally-accessible ones
-- This truncates the type environment to include only the
421
-- exported Ids and things needed from them, which saves space
422 423
--
-- See Note [Don't attempt to trim data types]
424

425
tidyTypeEnv omit_prags type_env
426 427 428
 = let
        type_env1 = filterNameEnv (not . isWiredInName . getName) type_env
          -- (1) remove wired-in things
429
        type_env2 | omit_prags = mapNameEnv trimThing type_env1
430 431 432 433
                  | otherwise  = type_env1
          -- (2) trimmed if necessary
    in
    type_env2
434 435

--------------------------
436
trimThing :: TyThing -> TyThing
437
-- Trim off inessentials, for boot files and no -O
438
trimThing (AnId id)
439
   | not (isImplicitId id)
440
   = AnId (id `setIdInfo` vanillaIdInfo)
441

442
trimThing other_thing
443
  = other_thing
444 445
\end{code}

446 447
\begin{code}
tidyVectInfo :: TidyEnv -> VectInfo -> VectInfo
448
tidyVectInfo (_, var_env) info@(VectInfo { vectInfoVar          = vars
449
                                         , vectInfoParallelVars = parallelVars
450 451
                                         })
  = info { vectInfoVar          = tidy_vars
452
         , vectInfoParallelVars = tidy_parallelVars
453
         }
454
  where
455 456
      -- we only export mappings whose domain and co-domain is exported (otherwise, the iface is
      -- inconsistent)
457 458 459 460
    tidy_vars = mkVarEnv [ (tidy_var, (tidy_var, tidy_var_v))
                         | (var, var_v) <- varEnvElts vars
                         , let tidy_var   = lookup_var var
                               tidy_var_v = lookup_var var_v
461 462
                         , isExternalId tidy_var   && isExportedId tidy_var
                         , isExternalId tidy_var_v && isExportedId tidy_var_v
463
                         , isDataConWorkId var || not (isImplicitId var)
464 465
                         ]

466
    tidy_parallelVars = mkVarSet [ tidy_var
467
                                 | var <- varSetElems parallelVars
468
                                 , let tidy_var = lookup_var var
469 470
                                 , isExternalId tidy_var && isExportedId tidy_var
                                 ]
471

472
    lookup_var var = lookupWithDefaultVarEnv var_env var var
473
    
474 475
    -- We need to make sure that all names getting into the iface version of 'VectInfo' are
    -- external; otherwise, 'MkIface' will bomb out.
476
    isExternalId = isExternalName . idName
477 478
\end{code}

479 480 481 482 483
Note [Don't attempt to trim data types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
For some time GHC tried to avoid exporting the data constructors
of a data type if it wasn't strictly necessary to do so; see Trac #835.
But "strictly necessary" accumulated a longer and longer list 
Gabor Greif's avatar
typos  
Gabor Greif committed
484
of exceptions, and finally I gave up the battle:
485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505

    commit 9a20e540754fc2af74c2e7392f2786a81d8d5f11
    Author: Simon Peyton Jones <simonpj@microsoft.com>
    Date:   Thu Dec 6 16:03:16 2012 +0000

    Stop attempting to "trim" data types in interface files
    
    Without -O, we previously tried to make interface files smaller
    by not including the data constructors of data types.  But
    there are a lot of exceptions, notably when Template Haskell is
    involved or, more recently, DataKinds.
    
    However Trac #7445 shows that even without TemplateHaskell, using
    the Data class and invoking Language.Haskell.TH.Quote.dataToExpQ
    is enough to require us to expose the data constructors.
    
    So I've given up on this "optimisation" -- it's probably not
    important anyway.  Now I'm simply not attempting to trim off
    the data constructors.  The gain in simplicity is worth the
    modest cost in interface file growth, which is limited to the
    bits reqd to describe those data constructors.
506

507
%************************************************************************
508 509 510
%*                                                                      *
        Implicit bindings
%*                                                                      *
511 512 513 514 515 516 517
%************************************************************************

Note [Injecting implicit bindings]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We inject the implict bindings right at the end, in CoreTidy.
Some of these bindings, notably record selectors, are not
constructed in an optimised form.  E.g. record selector for
518
        data T = MkT { x :: {-# UNPACK #-} !Int }
519
Then the unfolding looks like
520
        x = \t. case t of MkT x1 -> let x = I# x1 in x
521 522 523 524 525
This generates bad code unless it's first simplified a bit.  That is
why CoreUnfold.mkImplicitUnfolding uses simleExprOpt to do a bit of
optimisation first.  (Only matters when the selector is used curried;
eg map x ys.)  See Trac #2070.

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
526 527 528 529 530
[Oct 09: in fact, record selectors are no longer implicit Ids at all,
because we really do want to optimise them properly. They are treated
much like any other Id.  But doing "light" optimisation on an implicit
Id still makes sense.]

531 532
At one time I tried injecting the implicit bindings *early*, at the
beginning of SimplCore.  But that gave rise to real difficulty,
Gabor Greif's avatar
typos  
Gabor Greif committed
533
because GlobalIds are supposed to have *fixed* IdInfo, but the
534 535 536 537 538 539
simplifier and other core-to-core passes mess with IdInfo all the
time.  The straw that broke the camels back was when a class selector
got the wrong arity -- ie the simplifier gave it arity 2, whereas
importing modules were expecting it to have arity 1 (Trac #2844).
It's much safer just to inject them right at the end, after tidying.

540
Oh: two other reasons for injecting them late:
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
541

542 543 544
  - If implicit Ids are already in the bindings when we start TidyPgm,
    we'd have to be careful not to treat them as external Ids (in
    the sense of findExternalIds); else the Ids mentioned in *their*
545
    RHSs will be treated as external and you get an interface file
546
    saying      a18 = <blah>
547
    but nothing refererring to a18 (because the implicit Id is the
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
548
    one that does, and implicit Ids don't appear in interface files).
549 550 551 552

  - More seriously, the tidied type-envt will include the implicit
    Id replete with a18 in its unfolding; but we won't take account
    of a18 when computing a fingerprint for the class; result chaos.
553

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
554 555 556 557
There is one sort of implicit binding that is injected still later,
namely those for data constructor workers. Reason (I think): it's
really just a code generation trick.... binding itself makes no sense.
See CorePrep Note [Data constructor workers].
558 559

\begin{code}
560 561 562 563 564 565 566 567
getTyConImplicitBinds :: TyCon -> [CoreBind]
getTyConImplicitBinds tc = map get_defn (mapCatMaybes dataConWrapId_maybe (tyConDataCons tc))

getClassImplicitBinds :: Class -> [CoreBind]
getClassImplicitBinds cls = map get_defn (classAllSelIds cls)

get_defn :: Id -> CoreBind
get_defn id = NonRec id (unfoldingTemplate (realIdUnfolding id))
568 569 570
\end{code}


571
%************************************************************************
572
%*                                                                      *
573
\subsection{Step 1: finding externals}
574
%*                                                                      *
575 576
%************************************************************************

577
See Note [Choosing external names].
578

579
\begin{code}
580
type UnfoldEnv  = IdEnv (Name{-new name-}, Bool {-show unfolding-})
581 582
  -- Maps each top-level Id to its new Name (the Id is tidied in step 2)
  -- The Unique is unchanged.  If the new Name is external, it will be
583
  -- visible in the interface file.
Simon Marlow's avatar
Simon Marlow committed
584 585
  --
  -- Bool => expose unfolding or not.
586 587 588

chooseExternalIds :: HscEnv
                  -> Module
589
                  -> Bool -> Bool
590
                  -> [CoreBind]
591 592 593
                  -> [CoreBind]
                  -> [CoreRule]
                  -> VarEnv (Var, Var)
594
                  -> IO (UnfoldEnv, TidyOccEnv)
595
                  -- Step 1 from the notes above
596

597
chooseExternalIds hsc_env mod omit_prags expose_all binds implicit_binds imp_id_rules vect_vars
598 599 600
  = do { (unfold_env1,occ_env1) <- search init_work_list emptyVarEnv init_occ_env
       ; let internal_ids = filter (not . (`elemVarEnv` unfold_env1)) binders
       ; tidy_internal internal_ids unfold_env1 occ_env1 }
601
 where
602
  nc_var = hsc_NC hsc_env
603

604 605
  -- init_ext_ids is the intial list of Ids that should be
  -- externalised.  It serves as the starting point for finding a
606 607
  -- deterministic, tidy, renaming for all external Ids in this
  -- module.
608
  --
609 610 611 612 613 614 615
  -- It is sorted, so that it has adeterministic order (i.e. it's the
  -- same list every time this module is compiled), in contrast to the
  -- bindings, which are ordered non-deterministically.
  init_work_list = zip init_ext_ids init_ext_ids
  init_ext_ids   = sortBy (compare `on` getOccName) $
                   filter is_external binders

616 617 618
  -- An Id should be external if either (a) it is exported,
  -- (b) it appears in the RHS of a local rule for an imported Id, or
  -- (c) it is the vectorised version of an imported Id
619
  -- See Note [Which rules to expose]
620 621 622
  is_external id = isExportedId id || id `elemVarSet` rule_rhs_vars || id `elemVarSet` vect_var_vs
  rule_rhs_vars  = foldr (unionVarSet . ruleRhsFreeVars) emptyVarSet imp_id_rules
  vect_var_vs    = mkVarSet [var_v | (var, var_v) <- nameEnvElts vect_vars, isGlobalId var]
623 624

  binders          = bindersOfBinds binds
625
  implicit_binders = bindersOfBinds implicit_binds
626
  binder_set       = mkVarSet binders
627

628
  avoids   = [getOccName name | bndr <- binders ++ implicit_binders,
629
                                let name = idName bndr,
630
                                isExternalName name ]
631 632 633 634 635 636
                -- In computing our "avoids" list, we must include
                --      all implicit Ids
                --      all things with global names (assigned once and for
                --                                      all by the renamer)
                -- since their names are "taken".
                -- The type environment is a convenient source of such things.
637 638
                -- In particular, the set of binders doesn't include
                -- implicit Ids at this stage.
639

640 641 642 643 644 645 646 647
        -- We also make sure to avoid any exported binders.  Consider
        --      f{-u1-} = 1     -- Local decl
        --      ...
        --      f{-u2-} = 2     -- Exported decl
        --
        -- The second exported decl must 'get' the name 'f', so we
        -- have to put 'f' in the avoids list before we get to the first
        -- decl.  tidyTopId then does a no-op on exported binders.
648 649 650
  init_occ_env = initTidyOccEnv avoids


651
  search :: [(Id,Id)]    -- The work-list: (external id, referrring id)
652
                         -- Make a tidy, external Name for the external id,
653 654
                         --   add it to the UnfoldEnv, and do the same for the
                         --   transitive closure of Ids it refers to
655 656
                         -- The referring id is used to generate a tidy
                         ---  name for the external id
657 658 659 660 661 662
         -> UnfoldEnv    -- id -> (new Name, show_unfold)
         -> TidyOccEnv   -- occ env for choosing new Names
         -> IO (UnfoldEnv, TidyOccEnv)

  search [] unfold_env occ_env = return (unfold_env, occ_env)

663 664
  search ((idocc,referrer) : rest) unfold_env occ_env
    | idocc `elemVarEnv` unfold_env = search rest unfold_env occ_env
665
    | otherwise = do
666
      (occ_env', name') <- tidyTopName mod nc_var (Just referrer) occ_env idocc
667
      let
668 669
          (new_ids, show_unfold)
                | omit_prags = ([], False)
670
                | otherwise  = addExternal expose_all refined_id
671

672 673 674
                -- add vectorised version if any exists
          new_ids' = new_ids ++ maybeToList (fmap snd $ lookupVarEnv vect_vars idocc)
          
675 676
                -- 'idocc' is an *occurrence*, but we need to see the
                -- unfolding in the *definition*; so look up in binder_set
677 678 679 680 681 682 683
          refined_id = case lookupVarSet binder_set idocc of
                         Just id -> id
                         Nothing -> WARN( True, ppr idocc ) idocc

          unfold_env' = extendVarEnv unfold_env idocc (name',show_unfold)
          referrer' | isExportedId refined_id = refined_id
                    | otherwise               = referrer
684
      --
685
      search (zip new_ids' (repeat referrer') ++ rest) unfold_env' occ_env'
686 687 688 689 690 691 692 693 694

  tidy_internal :: [Id] -> UnfoldEnv -> TidyOccEnv
                -> IO (UnfoldEnv, TidyOccEnv)
  tidy_internal []       unfold_env occ_env = return (unfold_env,occ_env)
  tidy_internal (id:ids) unfold_env occ_env = do
      (occ_env', name') <- tidyTopName mod nc_var Nothing occ_env id
      let unfold_env' = extendVarEnv unfold_env id (name',False)
      tidy_internal ids unfold_env' occ_env'

695
addExternal :: Bool -> Id -> ([Id], Bool)
696
addExternal expose_all id = (new_needed_ids, show_unfold)
697
  where
698
    new_needed_ids = bndrFvsInOrder show_unfold id
699
    idinfo         = idInfo id
700
    show_unfold    = show_unfolding (unfoldingInfo idinfo)
701
    never_active   = isNeverActive (inlinePragmaActivation (inlinePragInfo idinfo))
702
    loop_breaker   = isStrongLoopBreaker (occInfo idinfo)
703
    bottoming_fn   = isBottomingSig (strictnessInfo idinfo)
704

705 706 707
        -- Stuff to do with the Id's unfolding
        -- We leave the unfolding there even if there is a worker
        -- In GHCi the unfolding is used by importers
708 709

    show_unfolding (CoreUnfolding { uf_src = src, uf_guidance = guidance })
710 711
       =  expose_all         -- 'expose_all' says to expose all
                             -- unfoldings willy-nilly
712

713 714
       || isStableSource src     -- Always expose things whose
                                 -- source is an inline rule
715

716 717 718 719
       || not (bottoming_fn      -- No need to inline bottom functions
           || never_active       -- Or ones that say not to
           || loop_breaker       -- Or that are loop breakers
           || neverUnfoldGuidance guidance)
720 721 722
    show_unfolding (DFunUnfolding {}) = True
    show_unfolding _                  = False
\end{code}
723

724
%************************************************************************
725
%*                                                                      *
726
               Deterministic free variables
727
%*                                                                      *
728
%************************************************************************
729

730 731 732 733
We want a deterministic free-variable list.  exprFreeVars gives us
a VarSet, which is in a non-deterministic order when converted to a
list.  Hence, here we define a free-variable finder that returns
the free variables in the order that they are encountered.
734

735
See Note [Choosing external names]
736

737 738 739 740
\begin{code}
bndrFvsInOrder :: Bool -> Id -> [Id]
bndrFvsInOrder show_unfold id
  = run (dffvLetBndr show_unfold id)
741

742 743 744 745
run :: DFFV () -> [Id]
run (DFFV m) = case m emptyVarSet (emptyVarSet, []) of
                 ((_,ids),_) -> ids

746 747
newtype DFFV a
  = DFFV (VarSet              -- Envt: non-top-level things that are in scope
748
                              -- we don't want to record these as free vars
749
      -> (VarSet, [Var])      -- Input State: (set, list) of free vars so far
750
      -> ((VarSet,[Var]),a))  -- Output state
751 752

instance Monad DFFV where
753 754 755 756 757 758 759 760 761 762 763
  return a = DFFV $ \_ st -> (st, a)
  (DFFV m) >>= k = DFFV $ \env st ->
    case m env st of
       (st',a) -> case k a of
                     DFFV f -> f env st'

extendScope :: Var -> DFFV a -> DFFV a
extendScope v (DFFV f) = DFFV (\env st -> f (extendVarSet env v) st)

extendScopeList :: [Var] -> DFFV a -> DFFV a
extendScopeList vs (DFFV f) = DFFV (\env st -> f (extendVarSetList env vs) st)
764 765

insert :: Var -> DFFV ()
766 767
insert v = DFFV $ \ env (set, ids) ->
           let keep_me = isLocalId v &&
768
                         not (v `elemVarSet` env) &&
769 770
                           not (v `elemVarSet` set)
           in if keep_me
771 772 773
              then ((extendVarSet set v, v:ids), ())
              else ((set,                ids),   ())

774 775

dffvExpr :: CoreExpr -> DFFV ()
776
dffvExpr (Var v)              = insert v
777 778
dffvExpr (App e1 e2)          = dffvExpr e1 >> dffvExpr e2
dffvExpr (Lam v e)            = extendScope v (dffvExpr e)
779 780
dffvExpr (Tick (Breakpoint _ ids) e) = mapM_ insert ids >> dffvExpr e
dffvExpr (Tick _other e)    = dffvExpr e
781
dffvExpr (Cast e _)           = dffvExpr e
782 783 784 785 786 787 788 789 790 791
dffvExpr (Let (NonRec x r) e) = dffvBind (x,r) >> extendScope x (dffvExpr e)
dffvExpr (Let (Rec prs) e)    = extendScopeList (map fst prs) $
                                (mapM_ dffvBind prs >> dffvExpr e)
dffvExpr (Case e b _ as)      = dffvExpr e >> extendScope b (mapM_ dffvAlt as)
dffvExpr _other               = return ()

dffvAlt :: (t, [Var], CoreExpr) -> DFFV ()
dffvAlt (_,xs,r) = extendScopeList xs (dffvExpr r)

dffvBind :: (Id, CoreExpr) -> DFFV ()
792
dffvBind(x,r)
793 794
  | not (isId x) = dffvExpr r
  | otherwise    = dffvLetBndr False x >> dffvExpr r
795 796
                -- Pass False because we are doing the RHS right here
                -- If you say True you'll get *exponential* behaviour!
797 798

dffvLetBndr :: Bool -> Id -> DFFV ()
799 800 801 802 803 804 805 806 807 808 809 810
-- Gather the free vars of the RULES and unfolding of a binder
-- We always get the free vars of a *stable* unfolding, but
-- for a *vanilla* one (InlineRhs), the flag controls what happens:
--   True <=> get fvs of even a *vanilla* unfolding
--   False <=> ignore an InlineRhs
-- For nested bindings (call from dffvBind) we always say "False" because
--       we are taking the fvs of the RHS anyway
-- For top-level bindings (call from addExternal, via bndrFvsInOrder)
--       we say "True" if we are exposing that unfolding
dffvLetBndr vanilla_unfold id
  = do { go_unf (unfoldingInfo idinfo)
       ; mapM_ go_rule (specInfoRules (specInfo idinfo)) }
811
  where
812 813 814 815
    idinfo = idInfo id

    go_unf (CoreUnfolding { uf_tmpl = rhs, uf_src = src })
       = case src of
816 817
           InlineRhs | vanilla_unfold -> dffvExpr rhs
                     | otherwise      -> return ()
818
           _                          -> dffvExpr rhs
819

820 821
    go_unf (DFunUnfolding { df_bndrs = bndrs, df_args = args }) 
             = extendScopeList bndrs $ mapM_ dffvExpr args
822 823 824 825 826
    go_unf _ = return ()

    go_rule (BuiltinRule {}) = return ()
    go_rule (Rule { ru_bndrs = bndrs, ru_rhs = rhs })
      = extendScopeList bndrs (dffvExpr rhs)
827 828 829
\end{code}


830
%************************************************************************
831
%*                                                                      *
832
               tidyTopName
833
%*                                                                      *
834 835
%************************************************************************

836
This is where we set names to local/global based on whether they really are
837 838 839
externally visible (see comment at the top of this module).  If the name
was previously local, we have to give it a unique occurrence name if
we intend to externalise it.
840 841 842

\begin{code}
tidyTopName :: Module -> IORef NameCache -> Maybe Id -> TidyOccEnv
843
            -> Id -> IO (TidyOccEnv, Name)
844 845 846 847
tidyTopName mod nc_var maybe_ref occ_env id
  | global && internal = return (occ_env, localiseName name)

  | global && external = return (occ_env, name)
848 849 850
        -- Global names are assumed to have been allocated by the renamer,
        -- so they already have the "right" unique
        -- And it's a system-wide unique too
851 852 853 854

  -- Now we get to the real reason that all this is in the IO Monad:
  -- we have to update the name cache in a nice atomic fashion

855
  | local  && internal = do { new_local_name <- atomicModifyIORef nc_var mk_new_local
856 857 858 859 860 861
                            ; return (occ_env', new_local_name) }
        -- Even local, internal names must get a unique occurrence, because
        -- if we do -split-objs we externalise the name later, in the code generator
        --
        -- Similarly, we must make sure it has a system-wide Unique, because
        -- the byte-code generator builds a system-wide Name->BCO symbol table
862

863
  | local  && external = do { new_external_name <- atomicModifyIORef nc_var mk_new_external
864
                            ; return (occ_env', new_external_name) }
865 866 867

  | otherwise = panic "tidyTopName"
  where
868
    name        = idName id
869
    external    = isJust maybe_ref
870 871 872 873
    global      = isExternalName name
    local       = not global
    internal    = not external
    loc         = nameSrcSpan name
874 875 876

    old_occ     = nameOccName name
    new_occ
877
      | Just ref <- maybe_ref, ref /= id =
878
          mkOccName (occNameSpace old_occ) $
879 880 881 882 883 884 885 886 887 888 889 890 891 892 893
             let
                 ref_str = occNameString (getOccName ref)
                 occ_str = occNameString old_occ
             in
             case occ_str of
               '$':'w':_ -> occ_str
                  -- workers: the worker for a function already
                  -- includes the occname for its parent, so there's
                  -- no need to prepend the referrer.
               _other | isSystemName name -> ref_str
                      | otherwise         -> ref_str ++ '_' : occ_str
                  -- If this name was system-generated, then don't bother
                  -- to retain its OccName, just use the referrer.  These
                  -- system-generated names will become "f1", "f2", etc. for
                  -- a referrer "f".
894 895 896 897
      | otherwise = old_occ

    (occ_env', occ') = tidyOccName occ_env new_occ

898
    mk_new_local nc = (nc { nsUniqs = us }, mkInternalName uniq occ' loc)
899 900
                    where
                      (uniq, us) = takeUniqFromSupply (nsUniqs nc)
901 902

    mk_new_external nc = allocateGlobalBinder nc mod occ' loc
903 904 905 906 907 908
        -- If we want to externalise a currently-local name, check
        -- whether we have already assigned a unique for it.
        -- If so, use it; if not, extend the table.
        -- All this is done by allcoateGlobalBinder.
        -- This is needed when *re*-compiling a module in GHCi; we must
        -- use the same name for externally-visible things as we did before.
909 910
\end{code}

911
\begin{code}
912
findExternalRules :: Bool       -- Omit pragmas
913
                  -> [CoreBind]
914 915 916
                  -> [CoreRule] -- Local rules for imported fns
                  -> UnfoldEnv  -- Ids that are exported, so we need their rules
                  -> [CoreRule]
917
  -- The complete rules are gotten by combining
918 919
  --    a) local rules for imported Ids
  --    b) rules embedded in the top-level Ids
920 921 922
findExternalRules omit_prags binds imp_id_rules unfold_env
  | omit_prags = []
  | otherwise  = filterOut internal_rule (imp_id_rules ++ local_rules)
923 924
  where
    local_rules  = [ rule
925
                   | id <- bindersOfBinds binds,
926
                     external_id id,
927 928
                     rule <- idCoreRules id
                   ]