TidyPgm.hs 61.3 KB
Newer Older
Austin Seipp's avatar
Austin Seipp committed
1 2
{-
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998
Simon Marlow's avatar
Simon Marlow committed
3

4
\section{Tidying up Core}
Austin Seipp's avatar
Austin Seipp committed
5
-}
6

7
{-# LANGUAGE CPP, ViewPatterns #-}
8

9 10 11
module TidyPgm (
       mkBootModDetailsTc, tidyProgram, globaliseAndTidyId
   ) where
12 13 14

#include "HsVersions.h"

15 16
import GhcPrelude

17
import TcRnTypes
Simon Marlow's avatar
Simon Marlow committed
18
import DynFlags
19
import CoreSyn
Simon Marlow's avatar
Simon Marlow committed
20 21 22
import CoreUnfold
import CoreFVs
import CoreTidy
23
import CoreMonad
24
import CorePrep
25
import CoreUtils        (rhsIsStatic)
26
import CoreStats        (coreBindsStats, CoreStats(..))
27
import CoreSeq          (seqBinds)
28
import CoreLint
29
import Literal
30
import Rules
31 32
import PatSyn
import ConLike
33
import CoreArity        ( exprArity, exprBotStrictness_maybe )
34
import StaticPtrTable
35 36
import VarEnv
import VarSet
37
import Var
Simon Marlow's avatar
Simon Marlow committed
38
import Id
39
import MkId             ( mkDictSelRhs )
Simon Marlow's avatar
Simon Marlow committed
40 41
import IdInfo
import InstEnv
42
import FamInstEnv
Simon Peyton Jones's avatar
Simon Peyton Jones committed
43
import Type             ( tidyTopType )
44
import Demand           ( appIsBottom, isTopSig, isBottomingSig )
Simon Marlow's avatar
Simon Marlow committed
45
import BasicTypes
46
import Name hiding (varName)
Simon Marlow's avatar
Simon Marlow committed
47 48
import NameSet
import NameEnv
49
import NameCache
50 51
import Avail
import IfaceEnv
52 53
import TcEnv
import TcRnMonad
Simon Marlow's avatar
Simon Marlow committed
54 55
import DataCon
import TyCon
56
import Class
57
import Module
58
import Packages( isDllName )
59
import HscTypes
Simon Marlow's avatar
Simon Marlow committed
60 61
import Maybes
import UniqSupply
62
import Outputable
63
import qualified ErrUtils as Err
Simon Marlow's avatar
Simon Marlow committed
64

65
import Control.Monad
Ian Lynagh's avatar
Ian Lynagh committed
66
import Data.Function
67
import Data.List        ( sortBy )
68
import Data.IORef       ( atomicModifyIORef' )
69

Austin Seipp's avatar
Austin Seipp committed
70
{-
71
Constructing the TypeEnv, Instances, Rules from which the
72 73
ModIface is constructed, and which goes on to subsequent modules in
--make mode.
74 75 76 77 78 79 80 81

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 =>
82
recompilation does not happen => disaster.
83 84 85 86 87 88

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.

Austin Seipp's avatar
Austin Seipp committed
89 90
************************************************************************
*                                                                      *
91
                Plan A: simpleTidyPgm
Austin Seipp's avatar
Austin Seipp committed
92 93
*                                                                      *
************************************************************************
94 95


96
Plan A: mkBootModDetails: omit pragmas, make interfaces small
97 98 99
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Ignore the bindings

100 101
* Drop all WiredIn things from the TypeEnv
        (we never want them in interface files)
102 103

* Retain all TyCons and Classes in the TypeEnv, to avoid
104 105
        having to find which ones are mentioned in the
        types of exported Ids
106 107

* Trim off the constructors of non-exported TyCons, both
108
        from the TyCon and from the TypeEnv
109 110 111

* Drop non-exported Ids from the TypeEnv

112
* Tidy the types of the DFunIds of Instances,
113 114 115 116 117 118 119 120
  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

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

126 127
* If this an hsig file, drop the instances altogether too (they'll
  get pulled in by the implicit module import.
Austin Seipp's avatar
Austin Seipp committed
128
-}
129

130 131
-- 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
132 133 134
--
-- We don't look at the bindings at all -- there aren't any
-- for hs-boot files
135

136
mkBootModDetailsTc :: HscEnv -> TcGblEnv -> IO ModDetails
137
mkBootModDetailsTc hsc_env
138
        TcGblEnv{ tcg_exports   = exports,
139 140
                  tcg_type_env  = type_env, -- just for the Ids
                  tcg_tcs       = tcs,
141
                  tcg_patsyns   = pat_syns,
142
                  tcg_insts     = insts,
143 144
                  tcg_fam_insts = fam_insts,
                  tcg_mod       = this_mod
145
                }
146 147 148 149 150 151
  = -- This timing isn't terribly useful since the result isn't forced, but
    -- the message is useful to locating oneself in the compilation process.
    Err.withTiming (pure dflags)
                   (text "CoreTidy"<+>brackets (ppr this_mod))
                   (const ()) $
    do  { let { insts'     = map (tidyClsInstDFun globaliseAndTidyId) insts
Simon Peyton Jones's avatar
Simon Peyton Jones committed
152
              ; pat_syns'  = map (tidyPatSynIds   globaliseAndTidyId) pat_syns
153
              ; type_env1  = mkBootTypeEnv (availsToNameSet exports)
154
                                           (typeEnvIds type_env) tcs fam_insts
155
              ; type_env2  = extendTypeEnvWithPatSyns pat_syns' type_env1
156
              ; dfun_ids   = map instanceDFunId insts'
157
              ; type_env'  = extendTypeEnvWithIds type_env2 dfun_ids
158 159 160 161 162 163 164
              }
        ; return (ModDetails { md_types     = type_env'
                             , md_insts     = insts'
                             , md_fam_insts = fam_insts
                             , md_rules     = []
                             , md_anns      = []
                             , md_exports   = exports
165
                             , md_complete_sigs = []
166
                             })
167
        }
168
  where
169
    dflags = hsc_dflags hsc_env
170

171
mkBootTypeEnv :: NameSet -> [Id] -> [TyCon] -> [FamInst] -> TypeEnv
dreixel's avatar
dreixel committed
172
mkBootTypeEnv exports ids tcs fam_insts
173
  = tidyTypeEnv True $
dreixel's avatar
dreixel committed
174
       typeEnvFromEntities final_ids tcs fam_insts
175
  where
176
        -- Find the LocalIds in the type env that are exported
177 178 179 180 181 182
        -- 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.
183 184 185 186
        --
        -- Do make sure that we keep Ids that are already Global.
        -- When typechecking an .hs-boot file, the Ids come through as
        -- GlobalIds.
187 188 189
    final_ids = [ (if isLocalId id then globaliseAndTidyId id
                                   else id)
                        `setIdUnfolding` BootUnfolding
190 191
                | id <- ids
                , keep_it id ]
192 193 194 195 196

        -- 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
197 198


199 200

globaliseAndTidyId :: Id -> Id
Gabor Greif's avatar
Gabor Greif committed
201
-- Takes a LocalId with an External Name,
202
-- makes it into a GlobalId
203 204 205
--     * unchanged Name (might be Internal or External)
--     * unchanged details
--     * VanillaIdInfo (makes a conservative assumption about Caf-hood)
206
globaliseAndTidyId id
207 208 209
  = Id.setIdType (globaliseId id) tidy_type
  where
    tidy_type = tidyTopType (idType id)
210

Austin Seipp's avatar
Austin Seipp committed
211 212 213
{-
************************************************************************
*                                                                      *
214
        Plan B: tidy bindings, make TypeEnv full of IdInfo
Austin Seipp's avatar
Austin Seipp committed
215 216
*                                                                      *
************************************************************************
217

218
Plan B: include pragmas, make interfaces
219
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
220 221
* Step 1: Figure out which Ids are externally visible
          See Note [Choosing external Ids]
222

Gabor Greif's avatar
Gabor Greif committed
223
* Step 2: Gather the externally visible rules, separately from
224 225 226 227 228
          the top-level bindings.
          See Note [Finding external rules]

* Step 3: Tidy the bindings, externalising appropriate Ids
          See Note [Tidy the top-level bindings]
229

230
* Drop all Ids from the TypeEnv, and add all the External Ids from
231 232
  the bindings.  (This adds their IdInfo to the TypeEnv; and adds
  floated-out Ids that weren't even in the TypeEnv before.)
233

234 235
Note [Choosing external Ids]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Simon Marlow's avatar
Simon Marlow committed
236
See also the section "Interface stability" in the
237 238
recompilation-avoidance commentary:
  https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/recompilation-avoidance
Simon Marlow's avatar
Simon Marlow committed
239

240 241 242
First we figure out which Ids are "external" Ids.  An
"external" Id is one that is visible from outside the compilation
unit.  These are
243
  a) the user exported ones
244
  b) the ones bound to static forms
245 246
  c) ones mentioned in the unfoldings, workers, or
     rules of externally-visible ones
247

248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272
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.
273

274 275
Note [Tidy the top-level bindings]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
276 277 278
Next we traverse the bindings top to bottom.  For each *top-level*
binder

279 280
 1. Make it into a GlobalId; its IdDetails becomes VanillaGlobal,
    reflecting the fact that from now on we regard it as a global,
281
    not local, Id
282 283 284 285 286

 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.]

287
    We use the NameCache kept in the HscEnv as the
288 289
    source of such system-wide uniques.

290
    For external Ids, use the original-name cache in the NameCache
291
    to ensure that the unique assigned is the same as the Id had
292
    in any previous compilation run.
293 294 295 296 297 298

 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

299 300 301 302 303 304
 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
305 306 307 308 309


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.
Austin Seipp's avatar
Austin Seipp committed
310
-}
311

312
tidyProgram :: HscEnv -> ModGuts -> IO (CgGuts, ModDetails)
313 314
tidyProgram hsc_env  (ModGuts { mg_module    = mod
                              , mg_exports   = exports
315
                              , mg_rdr_env   = rdr_env
316
                              , mg_tcs       = tcs
317
                              , mg_insts     = cls_insts
318 319
                              , mg_fam_insts = fam_insts
                              , mg_binds     = binds
cactus's avatar
cactus committed
320
                              , mg_patsyns   = patsyns
321 322
                              , mg_rules     = imp_rules
                              , mg_anns      = anns
323
                              , mg_complete_sigs = complete_sigs
324
                              , mg_deps      = deps
325
                              , mg_foreign   = foreign_stubs
326
                              , mg_foreign_files = foreign_files
327
                              , mg_hpc_info  = hpc_info
328
                              , mg_modBreaks = modBreaks
329 330
                              })

331 332 333 334
  = Err.withTiming (pure dflags)
                   (text "CoreTidy"<+>brackets (ppr mod))
                   (const ()) $
    do  { let { omit_prags = gopt Opt_OmitInterfacePragmas dflags
ian@well-typed.com's avatar
ian@well-typed.com committed
335
              ; expose_all = gopt Opt_ExposeAllUnfoldings  dflags
336
              ; print_unqual = mkPrintUnqualified dflags rdr_env
337 338
              }

dreixel's avatar
dreixel committed
339
        ; let { type_env = typeEnvFromEntities [] tcs fam_insts
340 341 342 343 344

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

346
        ; (unfold_env, tidy_occ_env)
347
              <- chooseExternalIds hsc_env mod omit_prags expose_all
348
                                   binds implicit_binds imp_rules
Austin Seipp's avatar
Austin Seipp committed
349
        ; let { (trimmed_binds, trimmed_rules)
350
                    = findExternalRules omit_prags binds imp_rules unfold_env }
351

352
        ; (tidy_env, tidy_binds)
353
                 <- tidyTopBinds hsc_env mod unfold_env tidy_occ_env trimmed_binds
354

355
        ; let { final_ids  = [ id | id <- bindersOfBinds tidy_binds,
356
                                    isExternalName (idName id)]
357
              ; type_env1  = extendTypeEnvWithIds type_env final_ids
358

Simon Peyton Jones's avatar
Simon Peyton Jones committed
359
              ; tidy_cls_insts = map (tidyClsInstDFun (tidyVarOcc tidy_env)) cls_insts
360 361 362
                -- A DFunId will have a binding in tidy_binds, and so will now be in
                -- tidy_type_env, replete with IdInfo.  Its name will be unchanged since
                -- it was born, but we want Global, IdInfo-rich (or not) DFunId in the
363
                -- tidy_cls_insts.  Similarly the Ids inside a PatSyn.
364

365
              ; tidy_rules = tidyRules tidy_env trimmed_rules
366 367 368
                -- 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
369

370 371 372 373
                -- Tidy the Ids inside each PatSyn, very similarly to DFunIds
                -- and then override the PatSyns in the type_env with the new tidy ones
                -- This is really the only reason we keep mg_patsyns at all; otherwise
                -- they could just stay in type_env
Simon Peyton Jones's avatar
Simon Peyton Jones committed
374
              ; tidy_patsyns = map (tidyPatSynIds (tidyVarOcc tidy_env)) patsyns
375
              ; type_env2    = extendTypeEnvWithPatSyns tidy_patsyns type_env1
376 377

              ; tidy_type_env = tidyTypeEnv omit_prags type_env2
378 379
              }
          -- See Note [Grand plan for static forms] in StaticPtrTable.
380
        ; (spt_entries, tidy_binds') <-
381
             sptCreateStaticBinds hsc_env mod tidy_binds
382 383 384 385 386 387 388 389 390 391
        ; let { spt_init_code = sptModuleInitCode mod spt_entries
              ; add_spt_init_code =
                  case hscTarget dflags of
                    -- If we are compiling for the interpreter we will insert
                    -- any necessary SPT entries dynamically
                    HscInterpreted -> id
                    -- otherwise add a C stub to do so
                    _              -> (`appendStubC` spt_init_code)
              }

392 393
        ; let { -- See Note [Injecting implicit bindings]
                all_tidy_binds = implicit_binds ++ tidy_binds'
394 395

              -- Get the TyCons to generate code for.  Careful!  We must use
396 397 398 399 400 401 402
              -- 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)
403 404
              ; alg_tycons = filter isAlgTyCon (typeEnvTyCons type_env)
              }
405

406
        ; endPassIO hsc_env print_unqual CoreTidy all_tidy_binds tidy_rules
407

408 409
          -- If the endPass didn't print the rules, but ddump-rules is
          -- on, print now
410
        ; unless (dopt Opt_D_dump_simpl dflags) $
411
            Err.dumpIfSet_dyn dflags Opt_D_dump_rules
412
              (showSDoc dflags (ppr CoreTidy <+> text "rules"))
Sylvain Henry's avatar
Sylvain Henry committed
413
              (pprRulesForUser dflags tidy_rules)
414

415 416
          -- Print one-line size info
        ; let cs = coreBindsStats tidy_binds
417 418 419 420 421 422
        ; Err.dumpIfSet_dyn dflags Opt_D_dump_core_stats "Core Stats"
            (text "Tidy size (terms,types,coercions)"
             <+> ppr (moduleName mod) <> colon
             <+> int (cs_tm cs)
             <+> int (cs_ty cs)
             <+> int (cs_co cs) )
423

424 425 426
        ; return (CgGuts { cg_module   = mod,
                           cg_tycons   = alg_tycons,
                           cg_binds    = all_tidy_binds,
427
                           cg_foreign  = add_spt_init_code foreign_stubs,
428
                           cg_foreign_files = foreign_files,
429 430
                           cg_dep_pkgs = map fst $ dep_pkgs deps,
                           cg_hpc_info = hpc_info,
431 432
                           cg_modBreaks = modBreaks,
                           cg_spt_entries = spt_entries },
433

434
                   ModDetails { md_types     = tidy_type_env,
435
                                md_rules     = tidy_rules,
436
                                md_insts     = tidy_cls_insts,
437
                                md_fam_insts = fam_insts,
438
                                md_exports   = exports,
439 440
                                md_anns      = anns,      -- are already tidy
                                md_complete_sigs = complete_sigs
chak@cse.unsw.edu.au.'s avatar
chak@cse.unsw.edu.au. committed
441
                              })
442
        }
443 444
  where
    dflags = hsc_dflags hsc_env
445

446
tidyTypeEnv :: Bool       -- Compiling without -O, so omit prags
447
            -> TypeEnv -> TypeEnv
448

449
-- The completed type environment is gotten from
450 451
--      a) the types and classes defined here (plus implicit things)
--      b) adding Ids with correct IdInfo, including unfoldings,
452
--              gotten from the bindings
453
-- From (b) we keep only those Ids with External names;
454 455 456
--          the CoreTidy pass makes sure these are all and only
--          the externally-accessible ones
-- This truncates the type environment to include only the
457
-- exported Ids and things needed from them, which saves space
458 459
--
-- See Note [Don't attempt to trim data types]
460

461
tidyTypeEnv omit_prags type_env
462 463 464
 = let
        type_env1 = filterNameEnv (not . isWiredInName . getName) type_env
          -- (1) remove wired-in things
465
        type_env2 | omit_prags = mapNameEnv trimThing type_env1
466 467 468 469
                  | otherwise  = type_env1
          -- (2) trimmed if necessary
    in
    type_env2
470 471

--------------------------
472
trimThing :: TyThing -> TyThing
473
-- Trim off inessentials, for boot files and no -O
474
trimThing (AnId id)
475
   | not (isImplicitId id)
476
   = AnId (id `setIdInfo` vanillaIdInfo)
477

478
trimThing other_thing
479
  = other_thing
480 481 482 483

extendTypeEnvWithPatSyns :: [PatSyn] -> TypeEnv -> TypeEnv
extendTypeEnvWithPatSyns tidy_patsyns type_env
  = extendTypeEnvList type_env [AConLike (PatSynCon ps) | ps <- tidy_patsyns ]
484

Austin Seipp's avatar
Austin Seipp committed
485
{-
486 487 488
Note [Don't attempt to trim data types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
For some time GHC tried to avoid exporting the data constructors
489
of a data type if it wasn't strictly necessary to do so; see #835.
Austin Seipp's avatar
Austin Seipp committed
490
But "strictly necessary" accumulated a longer and longer list
Gabor Greif's avatar
typos  
Gabor Greif committed
491
of exceptions, and finally I gave up the battle:
492 493 494 495 496 497

    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
Austin Seipp's avatar
Austin Seipp committed
498

499 500 501 502
    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.
Austin Seipp's avatar
Austin Seipp committed
503

504
    However #7445 shows that even without TemplateHaskell, using
505 506
    the Data class and invoking Language.Haskell.TH.Quote.dataToExpQ
    is enough to require us to expose the data constructors.
Austin Seipp's avatar
Austin Seipp committed
507

508 509 510 511 512
    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.
513

Austin Seipp's avatar
Austin Seipp committed
514 515
************************************************************************
*                                                                      *
516
        Implicit bindings
Austin Seipp's avatar
Austin Seipp committed
517 518
*                                                                      *
************************************************************************
519 520 521

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

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
533 534 535 536 537
[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.]

538 539
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
540
because GlobalIds are supposed to have *fixed* IdInfo, but the
541 542 543
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
544
importing modules were expecting it to have arity 1 (#2844).
545 546
It's much safer just to inject them right at the end, after tidying.

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

549 550
  - 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
551
    the sense of chooseExternalIds); else the Ids mentioned in *their*
552
    RHSs will be treated as external and you get an interface file
553
    saying      a18 = <blah>
554
    but nothing referring to a18 (because the implicit Id is the
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
555
    one that does, and implicit Ids don't appear in interface files).
556 557 558 559

  - 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.
560

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
561 562 563
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.
564
See Note [Data constructor workers] in CorePrep.
Austin Seipp's avatar
Austin Seipp committed
565
-}
566

567
getTyConImplicitBinds :: TyCon -> [CoreBind]
Icelandjack's avatar
Icelandjack committed
568
getTyConImplicitBinds tc = map get_defn (mapMaybe dataConWrapId_maybe (tyConDataCons tc))
569 570

getClassImplicitBinds :: Class -> [CoreBind]
571 572 573
getClassImplicitBinds cls
  = [ NonRec op (mkDictSelRhs cls val_index)
    | (op, val_index) <- classAllSelIds cls `zip` [0..] ]
574 575 576

get_defn :: Id -> CoreBind
get_defn id = NonRec id (unfoldingTemplate (realIdUnfolding id))
577

Austin Seipp's avatar
Austin Seipp committed
578 579 580
{-
************************************************************************
*                                                                      *
581
\subsection{Step 1: finding externals}
Austin Seipp's avatar
Austin Seipp committed
582 583
*                                                                      *
************************************************************************
584

585
See Note [Choosing external Ids].
Austin Seipp's avatar
Austin Seipp committed
586
-}
587 588

type UnfoldEnv  = IdEnv (Name{-new name-}, Bool {-show unfolding-})
589 590
  -- 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
591
  -- visible in the interface file.
Simon Marlow's avatar
Simon Marlow committed
592 593
  --
  -- Bool => expose unfolding or not.
594 595 596

chooseExternalIds :: HscEnv
                  -> Module
597
                  -> Bool -> Bool
598
                  -> [CoreBind]
599 600
                  -> [CoreBind]
                  -> [CoreRule]
601
                  -> IO (UnfoldEnv, TidyOccEnv)
602
                  -- Step 1 from the notes above
603

604
chooseExternalIds hsc_env mod omit_prags expose_all binds implicit_binds imp_id_rules
605 606 607
  = 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 }
608
 where
609
  nc_var = hsc_NC hsc_env
610

611
  -- init_ext_ids is the initial list of Ids that should be
612
  -- externalised.  It serves as the starting point for finding a
613 614
  -- deterministic, tidy, renaming for all external Ids in this
  -- module.
615
  --
616
  -- It is sorted, so that it has a deterministic order (i.e. it's the
617 618 619
  -- 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
620
  init_ext_ids   = sortBy (compare `on` getOccName) $ filter is_external binders
621

622 623
  -- 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
624
  -- See Note [Which rules to expose]
625
  is_external id = isExportedId id || id `elemVarSet` rule_rhs_vars
626

627
  rule_rhs_vars  = mapUnionVarSet ruleRhsFreeVars imp_id_rules
628

629
  binders          = map fst $ flattenBinds binds
630
  implicit_binders = bindersOfBinds implicit_binds
631
  binder_set       = mkVarSet binders
632

633
  avoids   = [getOccName name | bndr <- binders ++ implicit_binders,
634
                                let name = idName bndr,
635
                                isExternalName name ]
636 637 638 639 640 641
                -- 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.
642 643
                -- In particular, the set of binders doesn't include
                -- implicit Ids at this stage.
644

645 646 647 648 649 650 651 652
        -- 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.
653 654 655
  init_occ_env = initTidyOccEnv avoids


656
  search :: [(Id,Id)]    -- The work-list: (external id, referring id)
657
                         -- Make a tidy, external Name for the external id,
658 659
                         --   add it to the UnfoldEnv, and do the same for the
                         --   transitive closure of Ids it refers to
660 661
                         -- The referring id is used to generate a tidy
                         ---  name for the external id
662 663 664 665 666 667
         -> 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)

668 669
  search ((idocc,referrer) : rest) unfold_env occ_env
    | idocc `elemVarEnv` unfold_env = search rest unfold_env occ_env
670
    | otherwise = do
671
      (occ_env', name') <- tidyTopName mod nc_var (Just referrer) occ_env idocc
672
      let
673 674
          (new_ids, show_unfold)
                | omit_prags = ([], False)
675
                | otherwise  = addExternal expose_all refined_id
676

677 678
                -- 'idocc' is an *occurrence*, but we need to see the
                -- unfolding in the *definition*; so look up in binder_set
679 680 681 682 683 684 685
          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
686
      --
687
      search (zip new_ids (repeat referrer') ++ rest) unfold_env' occ_env'
688 689 690 691 692 693 694 695 696

  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'

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

707 708 709
        -- 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
710 711

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

715 716
       || isStableSource src     -- Always expose things whose
                                 -- source is an inline rule
717

718 719 720 721
       || 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)
722 723
    show_unfolding (DFunUnfolding {}) = True
    show_unfolding _                  = False
724

Austin Seipp's avatar
Austin Seipp committed
725 726 727
{-
************************************************************************
*                                                                      *
728
               Deterministic free variables
Austin Seipp's avatar
Austin Seipp committed
729 730
*                                                                      *
************************************************************************
731

732 733 734 735
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.
736

737
See Note [Choosing external Ids]
Austin Seipp's avatar
Austin Seipp committed
738
-}
739

740 741 742
bndrFvsInOrder :: Bool -> Id -> [Id]
bndrFvsInOrder show_unfold id
  = run (dffvLetBndr show_unfold id)
743

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

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

Austin Seipp's avatar
Austin Seipp committed
754 755 756 757
instance Functor DFFV where
    fmap = liftM

instance Applicative DFFV where
758
    pure a = DFFV $ \_ st -> (st, a)
Austin Seipp's avatar
Austin Seipp committed
759 760
    (<*>) = ap

761
instance Monad DFFV where
762 763 764 765 766 767 768 769 770 771
  (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)
772 773

insert :: Var -> DFFV ()
774 775
insert v = DFFV $ \ env (set, ids) ->
           let keep_me = isLocalId v &&
776
                         not (v `elemVarSet` env) &&
777 778
                           not (v `elemVarSet` set)
           in if keep_me
779 780 781
              then ((extendVarSet set v, v:ids), ())
              else ((set,                ids),   ())

782 783

dffvExpr :: CoreExpr -> DFFV ()
784
dffvExpr (Var v)              = insert v
785 786
dffvExpr (App e1 e2)          = dffvExpr e1 >> dffvExpr e2
dffvExpr (Lam v e)            = extendScope v (dffvExpr e)
787 788
dffvExpr (Tick (Breakpoint _ ids) e) = mapM_ insert ids >> dffvExpr e
dffvExpr (Tick _other e)    = dffvExpr e
789
dffvExpr (Cast e _)           = dffvExpr e
790 791 792 793 794 795 796 797 798 799
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 ()
800
dffvBind(x,r)
801 802
  | not (isId x) = dffvExpr r
  | otherwise    = dffvLetBndr False x >> dffvExpr r
803 804
                -- Pass False because we are doing the RHS right here
                -- If you say True you'll get *exponential* behaviour!
805 806

dffvLetBndr :: Bool -> Id -> DFFV ()
807 808 809 810 811 812 813 814 815 816 817
-- 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)
818
       ; mapM_ go_rule (ruleInfoRules (ruleInfo idinfo)) }
819
  where
820 821 822 823
    idinfo = idInfo id

    go_unf (CoreUnfolding { uf_tmpl = rhs, uf_src = src })
       = case src of
824 825
           InlineRhs | vanilla_unfold -> dffvExpr rhs
                     | otherwise      -> return ()
826
           _                          -> dffvExpr rhs
827

Austin Seipp's avatar
Austin Seipp committed
828
    go_unf (DFunUnfolding { df_bndrs = bndrs, df_args = args })
829
             = extendScopeList bndrs $ mapM_ dffvExpr args
830 831 832 833 834
    go_unf _ = return ()

    go_rule (BuiltinRule {}) = return ()
    go_rule (Rule { ru_bndrs = bndrs, ru_rhs = rhs })
      = extendScopeList bndrs (dffvExpr rhs)
835

Austin Seipp's avatar
Austin Seipp committed
836 837 838
{-
************************************************************************
*                                                                      *
839
               findExternalRules
Austin Seipp's avatar
Austin Seipp committed
840 841
*                                                                      *
************************************************************************
842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874

Note [Finding external rules]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The complete rules are gotten by combining
   a) local rules for imported Ids
   b) rules embedded in the top-level Ids

There are two complications:
  * Note [Which rules to expose]
  * Note [Trimming auto-rules]

Note [Which rules to expose]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The function 'expose_rule' filters out rules that mention, on the LHS,
Ids that aren't externally visible; these rules can't fire in a client
module.

The externally-visible binders are computed (by chooseExternalIds)
assuming that all orphan rules are externalised (see init_ext_ids in
function 'search'). So in fact it's a bit conservative and we may
export more than we need.  (It's a sort of mutual recursion.)

Note [Trimming auto-rules]
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Second, with auto-specialisation we may specialise local or imported
dfuns or INLINE functions, and then later inline them.  That may leave
behind something like
   RULE "foo" forall d. f @ Int d = f_spec
where f is either local or imported, and there is no remaining
reference to f_spec except from the RULE.

Now that RULE *might* be useful to an importing module, but that is
purely speculative, and meanwhile the code is taking up space and
Simon Peyton Jones's avatar
Simon Peyton Jones committed
875 876 877 878
codegen time.  I found that binary sizes jumped by 6-10% when I
started to specialise INLINE functions (again, Note [Inline
specialisations] in Specialise).

879
So it seems better to drop the binding for f_spec, and the rule
Simon Peyton Jones's avatar
Simon Peyton Jones committed
880 881
itself, if the auto-generated rule is the *only* reason that it is
being kept alive.
882 883 884 885 886 887 888 889 890 891 892 893

(The RULE still might have been useful in the past; that is, it was
the right thing to have generated it in the first place.  See Note
[Inline specialisations] in Specialise.  But now it has served its
purpose, and can be discarded.)

So findExternalRules does this:
  * Remove all bindings that are kept alive *only* by isAutoRule rules
      (this is done in trim_binds)
  * Remove all auto rules that mention bindings that have been removed
      (this is done by filtering by keep_rule)

Simon Peyton Jones's avatar
Simon Peyton Jones committed
894
NB: if a binding is kept alive for some *other* reason (e.g. f_spec is
895 896
called in the final code), we keep the rule too.

Simon Peyton Jones's avatar
Simon Peyton Jones committed
897
This stuff is the only reason for the ru_auto field in a Rule.
Austin Seipp's avatar
Austin Seipp committed
898
-}
899 900 901 902 903 904 905 906 907 908 909

findExternalRules :: Bool       -- Omit pragmas
                  -> [CoreBind]
                  -> [CoreRule] -- Local rules for imported fns
                  -> UnfoldEnv  -- Ids that are exported, so we need their rules
                  -> ([CoreBind], [CoreRule])
-- See Note [Finding external rules]
findExternalRules omit_prags binds imp_id_rules unfold_env
  = (trimmed_binds, filter keep_rule all_rules)
  where
    imp_rules         = filter expose_rule imp_id_rules
910
    imp_user_rule_fvs = mapUnionVarSet user_rule_rhs_fvs imp_rules
911 912 913 914 915 916 917 918 919 920 921

    user_rule_rhs_fvs rule | isAutoRule rule = emptyVarSet
                           | otherwise       = ruleRhsFreeVars rule

    (trimmed_binds, local_bndrs, _, all_rules) = trim_binds binds

    keep_rule rule = ruleFreeVars rule `subVarSet` local_bndrs
        -- Remove rules that make no sense, because they mention a
        -- local binder (on LHS or RHS) that we have now discarded.
        -- (NB: ruleFreeVars only includes LocalIds)
        --
Gabor Greif's avatar
Gabor Greif committed
922
        -- LHS: we have already filtered out rules that mention internal Ids
923 924 925 926 927 928 929 930 931
        --     on LHS but that isn't enough because we might have by now
        --     discarded a binding with an external Id. (How?
        --     chooseExternalIds is a bit conservative.)
        --
        -- RHS: the auto rules that might mention a binder that has
        --      been discarded; see Note [Trimming auto-rules]

    expose_rule rule
        | omit_prags = False
niteria's avatar
niteria committed
932
        | otherwise  = all is_external_id (ruleLhsFreeIdsList rule)
933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966
                -- Don't expose a rule whose LHS mentions a locally-defined
                -- Id that is completely internal (i.e. not visible to an
                -- importing module).  NB: ruleLhsFreeIds only returns LocalIds.
                -- See Note [Which rules to expose]

    is_external_id id = case lookupVarEnv unfold_env id of
                          Just (name, _) -> isExternalName name
                          Nothing        -> False

    trim_binds :: [CoreBind]
               -> ( [CoreBind]   -- Trimmed bindings
                  , VarSet       -- Binders of those bindings
                  , VarSet       -- Free vars of those bindings + rhs of user rules
                                 -- (we don't bother to delete the binders)
                  , [CoreRule])  -- All rules, imported + from the bindings
    -- This function removes unnecessary bindings, and gathers up rules from
    -- the bindings we keep.  See Note [Trimming auto-rules]
    trim_binds []  -- Base case, start with imp_user_rule_fvs
       = ([], emptyVarSet, imp_user_rule_fvs, imp_rules)

    trim_binds (bind:binds)
       | any needed bndrs    -- Keep binding
       = ( bind : binds', bndr_set', needed_fvs', local_rules ++ rules )
       | otherwise           -- Discard binding altogether
       = stuff
       where
         stuff@(binds', bndr_set, needed_fvs, rules)
                       = trim_binds binds
         needed bndr   = isExportedId bndr || bndr `elemVarSet` needed_fvs

         bndrs         = bindersOf  bind
         rhss          = rhssOfBind bind
         bndr_set'     = bndr_set `extendVarSetList` bndrs

967 968
         needed_fvs'   = needed_fvs                                   `unionVarSet`
                         mapUnionVarSet idUnfoldingVars   bndrs       `unionVarSet`
969
                              -- Ignore type variables in the type of bndrs
970 971
                         mapUnionVarSet exprFreeVars      rhss        `unionVarSet`
                         mapUnionVarSet user_rule_rhs_fvs local_rules
972 973 974 975 976 977 978 979
            -- In needed_fvs', we don't bother to delete binders from the fv set

         local_rules  = [ rule
                        | id <- bndrs
                        , is_external_id id   -- Only collect rules for external Ids
                        , rule <- idCoreRules id
                        , expose_rule rule ]  -- and ones that can fire in a client

Austin Seipp's avatar
Austin Seipp committed
980 981 982
{-
************************************************************************
*                                                                      *
983
               tidyTopName
Austin Seipp's avatar
Austin Seipp committed
984 985
*                                                                      *
************************************************************************
986

987
This is where we set names to local/global based on whether they really are
988 989 990
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.
Austin Seipp's avatar
Austin Seipp committed
991
-}
992 993

tidyTopName :: Module -> IORef NameCache -> Maybe Id -> TidyOccEnv
994
            -> Id -> IO (TidyOccEnv, Name)
995 996 997 998
tidyTopName mod nc_var maybe_ref occ_env id
  | global && internal = return (occ_env, localiseName name)

  | global && external = return (occ_env, name)
999 1000 1001
        -- 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
1002 1003 1004 1005