Tidy.hs 55.6 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, DeriveFunctor, ViewPatterns #-}
8

9 10
{-# OPTIONS_GHC -Wno-incomplete-uni-patterns #-}

11
module GHC.Iface.Tidy (
12
       mkBootModDetailsTc, tidyProgram
13
   ) where
14 15 16

#include "HsVersions.h"

17 18
import GhcPrelude

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

63
import Control.Monad
Ian Lynagh's avatar
Ian Lynagh committed
64
import Data.Function
65
import Data.List        ( sortBy, mapAccumL )
66
import Data.IORef       ( atomicModifyIORef' )
67

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

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

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
87 88
************************************************************************
*                                                                      *
89
                Plan A: simpleTidyPgm
Austin Seipp's avatar
Austin Seipp committed
90 91
*                                                                      *
************************************************************************
92 93


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

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

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

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

* Drop non-exported Ids from the TypeEnv

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

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

124 125
* 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
126
-}
127

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

134
mkBootModDetailsTc :: HscEnv -> TcGblEnv -> IO ModDetails
135
mkBootModDetailsTc hsc_env
136 137 138 139 140 141 142 143
        TcGblEnv{ tcg_exports          = exports,
                  tcg_type_env         = type_env, -- just for the Ids
                  tcg_tcs              = tcs,
                  tcg_patsyns          = pat_syns,
                  tcg_insts            = insts,
                  tcg_fam_insts        = fam_insts,
                  tcg_complete_matches = complete_sigs,
                  tcg_mod              = this_mod
144
                }
145 146
  = -- This timing isn't terribly useful since the result isn't forced, but
    -- the message is useful to locating oneself in the compilation process.
147
    Err.withTiming dflags
148 149
                   (text "CoreTidy"<+>brackets (ppr this_mod))
                   (const ()) $
150 151 152 153 154 155 156 157
    return (ModDetails { md_types         = type_env'
                       , md_insts         = insts'
                       , md_fam_insts     = fam_insts
                       , md_rules         = []
                       , md_anns          = []
                       , md_exports       = exports
                       , md_complete_sigs = complete_sigs
                       })
158
  where
159
    dflags = hsc_dflags hsc_env
160

161 162 163 164 165 166 167 168 169 170 171 172 173
    -- Find the LocalIds in the type env that are exported
    -- 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.
    --
    -- 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 = [ globaliseAndTidyBootId id
                | id <- typeEnvIds type_env
174
                , keep_it id ]
175

176
    final_tcs  = filterOut isWiredIn tcs
177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
                 -- See Note [Drop wired-in things]
    type_env1  = typeEnvFromEntities final_ids final_tcs fam_insts
    insts'     = mkFinalClsInsts type_env1 insts
    pat_syns'  = mkFinalPatSyns  type_env1 pat_syns
    type_env'  = extendTypeEnvWithPatSyns pat_syns' type_env1

    -- Default methods have their export flag set (isExportedId),
    -- but everything else doesn't (yet), because this is
    -- pre-desugaring, so we must test against the exports too.
    keep_it id | isWiredInName id_name           = False
                 -- See Note [Drop wired-in things]
               | isExportedId id                 = True
               | id_name `elemNameSet` exp_names = True
               | otherwise                       = False
               where
                 id_name = idName id

    exp_names = availsToNameSet exports

lookupFinalId :: TypeEnv -> Id -> Id
lookupFinalId type_env id
  = case lookupTypeEnv type_env (idName id) of
      Just (AnId id') -> id'
      _ -> pprPanic "lookup_final_id" (ppr id)

mkFinalClsInsts :: TypeEnv -> [ClsInst] -> [ClsInst]
mkFinalClsInsts env = map (updateClsInstDFun (lookupFinalId env))

mkFinalPatSyns :: TypeEnv -> [PatSyn] -> [PatSyn]
mkFinalPatSyns env = map (updatePatSynIds (lookupFinalId env))
207

208 209 210
extendTypeEnvWithPatSyns :: [PatSyn] -> TypeEnv -> TypeEnv
extendTypeEnvWithPatSyns tidy_patsyns type_env
  = extendTypeEnvList type_env [AConLike (PatSynCon ps) | ps <- tidy_patsyns ]
211

212 213
globaliseAndTidyBootId :: Id -> Id
-- For a LocalId with an External Name,
214
-- makes it into a GlobalId
215 216
--     * unchanged Name (might be Internal or External)
--     * unchanged details
217
--     * VanillaIdInfo (makes a conservative assumption about arity)
218
--     * BootUnfolding (see Note [Inlining and hs-boot files] in GHC.CoreToIface)
219 220 221
globaliseAndTidyBootId id
  = globaliseId id `setIdType`      tidyTopType (idType id)
                   `setIdUnfolding` BootUnfolding
222

Austin Seipp's avatar
Austin Seipp committed
223 224 225
{-
************************************************************************
*                                                                      *
226
        Plan B: tidy bindings, make TypeEnv full of IdInfo
Austin Seipp's avatar
Austin Seipp committed
227 228
*                                                                      *
************************************************************************
229

230
Plan B: include pragmas, make interfaces
231
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
232 233
* Step 1: Figure out which Ids are externally visible
          See Note [Choosing external Ids]
234

Gabor Greif's avatar
Gabor Greif committed
235
* Step 2: Gather the externally visible rules, separately from
236 237 238 239 240
          the top-level bindings.
          See Note [Finding external rules]

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

242
* Drop all Ids from the TypeEnv, and add all the External Ids from
243 244
  the bindings.  (This adds their IdInfo to the TypeEnv; and adds
  floated-out Ids that weren't even in the TypeEnv before.)
245

246 247
Note [Choosing external Ids]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Simon Marlow's avatar
Simon Marlow committed
248
See also the section "Interface stability" in the
249 250
recompilation-avoidance commentary:
  https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/recompilation-avoidance
Simon Marlow's avatar
Simon Marlow committed
251

252 253 254
First we figure out which Ids are "external" Ids.  An
"external" Id is one that is visible from outside the compilation
unit.  These are
255
  a) the user exported ones
256
  b) the ones bound to static forms
257 258
  c) ones mentioned in the unfoldings, workers, or
     rules of externally-visible ones
259

260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284
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.
285

286 287
Note [Tidy the top-level bindings]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
288 289 290
Next we traverse the bindings top to bottom.  For each *top-level*
binder

291 292
 1. Make it into a GlobalId; its IdDetails becomes VanillaGlobal,
    reflecting the fact that from now on we regard it as a global,
293
    not local, Id
294 295 296 297 298

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

299
    We use the NameCache kept in the HscEnv as the
300 301
    source of such system-wide uniques.

302
    For external Ids, use the original-name cache in the NameCache
303
    to ensure that the unique assigned is the same as the Id had
304
    in any previous compilation run.
305 306 307 308 309 310

 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

311 312 313 314 315
 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

316 317 318 319

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
320
-}
321

322
tidyProgram :: HscEnv -> ModGuts -> IO (CgGuts, ModDetails)
323 324
tidyProgram hsc_env  (ModGuts { mg_module    = mod
                              , mg_exports   = exports
325
                              , mg_rdr_env   = rdr_env
326
                              , mg_tcs       = tcs
327
                              , mg_insts     = cls_insts
328 329
                              , mg_fam_insts = fam_insts
                              , mg_binds     = binds
cactus's avatar
cactus committed
330
                              , mg_patsyns   = patsyns
331 332
                              , mg_rules     = imp_rules
                              , mg_anns      = anns
333
                              , mg_complete_sigs = complete_sigs
334
                              , mg_deps      = deps
335
                              , mg_foreign   = foreign_stubs
336
                              , mg_foreign_files = foreign_files
337
                              , mg_hpc_info  = hpc_info
338
                              , mg_modBreaks = modBreaks
339 340
                              })

341
  = Err.withTiming dflags
342 343 344
                   (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
345
              ; expose_all = gopt Opt_ExposeAllUnfoldings  dflags
346
              ; print_unqual = mkPrintUnqualified dflags rdr_env
347
              ; implicit_binds = concatMap getImplicitBinds tcs
348
              }
349

350
        ; (unfold_env, tidy_occ_env)
351
              <- chooseExternalIds hsc_env mod omit_prags expose_all
352
                                   binds implicit_binds imp_rules
Austin Seipp's avatar
Austin Seipp committed
353
        ; let { (trimmed_binds, trimmed_rules)
354
                    = findExternalRules omit_prags binds imp_rules unfold_env }
355

356
        ; (tidy_env, tidy_binds)
357
                 <- tidyTopBinds hsc_env unfold_env tidy_occ_env trimmed_binds
358

359
          -- See Note [Grand plan for static forms] in StaticPtrTable.
360
        ; (spt_entries, tidy_binds') <-
361
             sptCreateStaticBinds hsc_env mod tidy_binds
362 363 364 365 366 367 368 369 370
        ; 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)

371 372 373 374 375 376 377 378 379 380 381 382 383 384
              -- The completed type environment is gotten from
              --      a) the types and classes defined here (plus implicit things)
              --      b) adding Ids with correct IdInfo, including unfoldings,
              --              gotten from the bindings
              -- From (b) we keep only those Ids with External names;
              --          the CoreTidy pass makes sure these are all and only
              --          the externally-accessible ones
              -- This truncates the type environment to include only the
              -- exported Ids and things needed from them, which saves space
              --
              -- See Note [Don't attempt to trim data types]
              ; final_ids  = [ if omit_prags then trimId id else id
                             | id <- bindersOfBinds tidy_binds
                             , isExternalName (idName id)
385
                             , not (isWiredIn id)
386 387
                             ]   -- See Note [Drop wired-in things]

388
              ; final_tcs      = filterOut isWiredIn tcs
389 390 391 392 393 394 395 396
                                 -- See Note [Drop wired-in things]
              ; type_env       = typeEnvFromEntities final_ids final_tcs fam_insts
              ; tidy_cls_insts = mkFinalClsInsts type_env cls_insts
              ; tidy_patsyns   = mkFinalPatSyns  type_env patsyns
              ; tidy_type_env  = extendTypeEnvWithPatSyns tidy_patsyns type_env
              ; tidy_rules     = tidyRules tidy_env trimmed_rules

              ; -- See Note [Injecting implicit bindings]
397
                all_tidy_binds = implicit_binds ++ tidy_binds'
398 399

              -- Get the TyCons to generate code for.  Careful!  We must use
400
              -- the untidied TyCons here, because we need
401 402 403 404 405 406
              --  (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)
407
              ; alg_tycons = filter isAlgTyCon tcs
408
              }
409

410
        ; endPassIO hsc_env print_unqual CoreTidy all_tidy_binds tidy_rules
411

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

420 421
          -- Print one-line size info
        ; let cs = coreBindsStats tidy_binds
422
        ; Err.dumpIfSet_dyn dflags Opt_D_dump_core_stats "Core Stats"
Sylvain Henry's avatar
Sylvain Henry committed
423
            Err.FormatText
424 425 426 427 428
            (text "Tidy size (terms,types,coercions)"
             <+> ppr (moduleName mod) <> colon
             <+> int (cs_tm cs)
             <+> int (cs_ty cs)
             <+> int (cs_co cs) )
429

430 431 432
        ; return (CgGuts { cg_module   = mod,
                           cg_tycons   = alg_tycons,
                           cg_binds    = all_tidy_binds,
433
                           cg_foreign  = add_spt_init_code foreign_stubs,
434
                           cg_foreign_files = foreign_files,
435 436
                           cg_dep_pkgs = map fst $ dep_pkgs deps,
                           cg_hpc_info = hpc_info,
437 438
                           cg_modBreaks = modBreaks,
                           cg_spt_entries = spt_entries },
439

440
                   ModDetails { md_types     = tidy_type_env,
441
                                md_rules     = tidy_rules,
442
                                md_insts     = tidy_cls_insts,
443
                                md_fam_insts = fam_insts,
444
                                md_exports   = exports,
445 446
                                md_anns      = anns,      -- are already tidy
                                md_complete_sigs = complete_sigs
chak@cse.unsw.edu.au.'s avatar
chak@cse.unsw.edu.au. committed
447
                              })
448
        }
449 450
  where
    dflags = hsc_dflags hsc_env
451

452
--------------------------
453 454 455 456
trimId :: Id -> Id
trimId id
  | not (isImplicitId id)
  = id `setIdInfo` vanillaIdInfo
457
       `setIdUnfolding` unfolding
458 459
  | otherwise
  = id
460 461 462 463 464 465
  where
    unfolding
      | isCompulsoryUnfolding (idUnfolding id)
      = idUnfolding id
      | otherwise
      = noUnfolding
466 467 468 469 470

{- Note [Drop wired-in things]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We never put wired-in TyCons or Ids in an interface file.
They are wired-in, so the compiler knows about them already.
471

472 473 474
Note [Don't attempt to trim data types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
For some time GHC tried to avoid exporting the data constructors
475
of a data type if it wasn't strictly necessary to do so; see #835.
Austin Seipp's avatar
Austin Seipp committed
476
But "strictly necessary" accumulated a longer and longer list
Gabor Greif's avatar
typos  
Gabor Greif committed
477
of exceptions, and finally I gave up the battle:
478 479 480 481 482 483

    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
484

485 486 487 488
    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
489

490
    However #7445 shows that even without TemplateHaskell, using
491 492
    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
493

494 495 496 497 498
    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.
499

Austin Seipp's avatar
Austin Seipp committed
500 501
************************************************************************
*                                                                      *
502
        Implicit bindings
Austin Seipp's avatar
Austin Seipp committed
503 504
*                                                                      *
************************************************************************
505 506 507

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

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
519 520 521 522 523
[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.]

524 525
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
526
because GlobalIds are supposed to have *fixed* IdInfo, but the
527 528 529
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
530
importing modules were expecting it to have arity 1 (#2844).
531 532
It's much safer just to inject them right at the end, after tidying.

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

535
  - If implicit Ids are already in the bindings when we start tidying,
536
    we'd have to be careful not to treat them as external Ids (in
537
    the sense of chooseExternalIds); else the Ids mentioned in *their*
538
    RHSs will be treated as external and you get an interface file
539
    saying      a18 = <blah>
540
    but nothing referring to a18 (because the implicit Id is the
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
541
    one that does, and implicit Ids don't appear in interface files).
542 543 544 545

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

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
547 548 549
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.
550
See Note [Data constructor workers] in CorePrep.
Austin Seipp's avatar
Austin Seipp committed
551
-}
552

553 554 555 556 557
getImplicitBinds :: TyCon -> [CoreBind]
getImplicitBinds tc = cls_binds ++ getTyConImplicitBinds tc
  where
    cls_binds = maybe [] getClassImplicitBinds (tyConClass_maybe tc)

558
getTyConImplicitBinds :: TyCon -> [CoreBind]
559 560 561
getTyConImplicitBinds tc
  | isNewTyCon tc = []  -- See Note [Compulsory newtype unfolding] in MkId
  | otherwise     = map get_defn (mapMaybe dataConWrapId_maybe (tyConDataCons tc))
562 563

getClassImplicitBinds :: Class -> [CoreBind]
564 565 566
getClassImplicitBinds cls
  = [ NonRec op (mkDictSelRhs cls val_index)
    | (op, val_index) <- classAllSelIds cls `zip` [0..] ]
567 568 569

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

Austin Seipp's avatar
Austin Seipp committed
571 572 573
{-
************************************************************************
*                                                                      *
574
\subsection{Step 1: finding externals}
Austin Seipp's avatar
Austin Seipp committed
575 576
*                                                                      *
************************************************************************
577

578
See Note [Choosing external Ids].
Austin Seipp's avatar
Austin Seipp committed
579
-}
580 581

type UnfoldEnv  = IdEnv (Name{-new name-}, Bool {-show unfolding-})
582 583
  -- 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
584
  -- visible in the interface file.
Simon Marlow's avatar
Simon Marlow committed
585 586
  --
  -- Bool => expose unfolding or not.
587 588 589

chooseExternalIds :: HscEnv
                  -> Module
590
                  -> Bool -> Bool
591
                  -> [CoreBind]
592 593
                  -> [CoreBind]
                  -> [CoreRule]
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
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
  -- init_ext_ids is the initial list of Ids that should be
605
  -- externalised.  It serves as the starting point for finding a
606 607
  -- deterministic, tidy, renaming for all external Ids in this
  -- module.
608
  --
609
  -- It is sorted, so that it has a deterministic order (i.e. it's the
610 611 612
  -- 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
613
  init_ext_ids   = sortBy (compare `on` getOccName) $ filter is_external binders
614

615 616
  -- 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
617
  -- See Note [Which rules to expose]
618
  is_external id = isExportedId id || id `elemVarSet` rule_rhs_vars
619

620
  rule_rhs_vars  = mapUnionVarSet ruleRhsFreeVars imp_id_rules
621

622
  binders          = map fst $ flattenBinds binds
623
  implicit_binders = bindersOfBinds implicit_binds
624
  binder_set       = mkVarSet binders
625

626
  avoids   = [getOccName name | bndr <- binders ++ implicit_binders,
627
                                let name = idName bndr,
628
                                isExternalName name ]
629 630 631 632 633 634
                -- 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.
635 636
                -- In particular, the set of binders doesn't include
                -- implicit Ids at this stage.
637

638 639 640 641 642 643 644 645
        -- 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.
646 647 648
  init_occ_env = initTidyOccEnv avoids


649
  search :: [(Id,Id)]    -- The work-list: (external id, referring id)
650
                         -- Make a tidy, external Name for the external id,
651 652
                         --   add it to the UnfoldEnv, and do the same for the
                         --   transitive closure of Ids it refers to
653 654
                         -- The referring id is used to generate a tidy
                         ---  name for the external id
655 656 657 658 659 660
         -> 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)

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

670 671
                -- 'idocc' is an *occurrence*, but we need to see the
                -- unfolding in the *definition*; so look up in binder_set
672 673 674 675 676 677 678
          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
679
      --
680
      search (zip new_ids (repeat referrer') ++ rest) unfold_env' occ_env'
681 682 683 684 685 686 687 688 689

  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'

690
addExternal :: Bool -> Id -> ([Id], Bool)
691
addExternal expose_all id = (new_needed_ids, show_unfold)
692
  where
693
    new_needed_ids = bndrFvsInOrder show_unfold id
694
    idinfo         = idInfo id
695
    show_unfold    = show_unfolding (unfoldingInfo idinfo)
696
    never_active   = isNeverActive (inlinePragmaActivation (inlinePragInfo idinfo))
697
    loop_breaker   = isStrongLoopBreaker (occInfo idinfo)
698
    bottoming_fn   = isBottomingSig (strictnessInfo idinfo)
699

700 701 702
        -- 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
703 704

    show_unfolding (CoreUnfolding { uf_src = src, uf_guidance = guidance })
705 706
       =  expose_all         -- 'expose_all' says to expose all
                             -- unfoldings willy-nilly
707

708 709
       || isStableSource src     -- Always expose things whose
                                 -- source is an inline rule
710

711 712 713 714
       || 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)
715 716
    show_unfolding (DFunUnfolding {}) = True
    show_unfolding _                  = False
717

Austin Seipp's avatar
Austin Seipp committed
718 719 720
{-
************************************************************************
*                                                                      *
721
               Deterministic free variables
Austin Seipp's avatar
Austin Seipp committed
722 723
*                                                                      *
************************************************************************
724

725 726 727 728
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.
729

730
See Note [Choosing external Ids]
Austin Seipp's avatar
Austin Seipp committed
731
-}
732

733 734 735
bndrFvsInOrder :: Bool -> Id -> [Id]
bndrFvsInOrder show_unfold id
  = run (dffvLetBndr show_unfold id)
736

737 738 739 740
run :: DFFV () -> [Id]
run (DFFV m) = case m emptyVarSet (emptyVarSet, []) of
                 ((_,ids),_) -> ids

741 742
newtype DFFV a
  = DFFV (VarSet              -- Envt: non-top-level things that are in scope
743
                              -- we don't want to record these as free vars
744
      -> (VarSet, [Var])      -- Input State: (set, list) of free vars so far
745
      -> ((VarSet,[Var]),a))  -- Output state
746
    deriving (Functor)
Austin Seipp's avatar
Austin Seipp committed
747 748

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

752
instance Monad DFFV where
753 754 755 756 757 758 759 760 761 762
  (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)
763 764

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

773 774

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

dffvLetBndr :: Bool -> Id -> DFFV ()
798 799 800 801 802 803 804 805 806 807 808
-- 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)
809
       ; mapM_ go_rule (ruleInfoRules (ruleInfo idinfo)) }
810
  where
811 812 813 814
    idinfo = idInfo id

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

Austin Seipp's avatar
Austin Seipp committed
819
    go_unf (DFunUnfolding { df_bndrs = bndrs, df_args = args })
820
             = extendScopeList bndrs $ mapM_ dffvExpr args
821 822 823 824 825
    go_unf _ = return ()

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

Austin Seipp's avatar
Austin Seipp committed
827 828 829
{-
************************************************************************
*                                                                      *
830
               findExternalRules
Austin Seipp's avatar
Austin Seipp committed
831 832
*                                                                      *
************************************************************************
833 834 835 836 837 838 839 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

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
866 867 868 869
codegen time.  I found that binary sizes jumped by 6-10% when I
started to specialise INLINE functions (again, Note [Inline
specialisations] in Specialise).

870
So it seems better to drop the binding for f_spec, and the rule
Simon Peyton Jones's avatar
Simon Peyton Jones committed
871 872
itself, if the auto-generated rule is the *only* reason that it is
being kept alive.
873 874 875 876 877 878 879 880 881 882 883 884

(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
885
NB: if a binding is kept alive for some *other* reason (e.g. f_spec is
886 887
called in the final code), we keep the rule too.

Simon Peyton Jones's avatar
Simon Peyton Jones committed
888
This stuff is the only reason for the ru_auto field in a Rule.
Austin Seipp's avatar
Austin Seipp committed
889
-}
890 891 892 893 894 895 896 897 898 899 900

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
901
    imp_user_rule_fvs = mapUnionVarSet user_rule_rhs_fvs imp_rules
902 903 904 905 906 907 908 909 910 911 912

    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
913
        -- LHS: we have already filtered out rules that mention internal Ids
914 915 916 917 918 919 920 921 922
        --     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
923
        | otherwise  = all is_external_id (ruleLhsFreeIdsList rule)
924 925 926 927 928 929 930 931 932 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
                -- 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

958 959
         needed_fvs'   = needed_fvs                                   `unionVarSet`
                         mapUnionVarSet idUnfoldingVars   bndrs       `unionVarSet`
960
                              -- Ignore type variables in the type of bndrs
961 962
                         mapUnionVarSet exprFreeVars      rhss        `unionVarSet`
                         mapUnionVarSet user_rule_rhs_fvs local_rules
963 964 965 966 967 968 969 970
            -- 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
971 972 973
{-
************************************************************************
*                                                                      *
974
               tidyTopName
Austin Seipp's avatar
Austin Seipp committed
975 976
*                                                                      *
************************************************************************
977

978
This is where we set names to local/global based on whether they really are
979 980 981
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
982
-}
983 984

tidyTopName :: Module -> IORef NameCache -> Maybe Id -> TidyOccEnv
985
            -> Id -> IO (TidyOccEnv, Name)
986 987 988 989
tidyTopName mod nc_var maybe_ref occ_env id
  | global && internal = return (occ_env, localiseName name)

  | global && external = return (occ_env, name)
990 991 992
        -- 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
993 994 995 996

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

997
  | local  && internal = do { new_local_name <- atomicModifyIORef' nc_var mk_new_local
998 999 1000 1001 1002 1003
                            ; 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
1004

1005
  | local  && external = do { new_external_name <- atomicModifyIORef' nc_var mk_new_external
1006
                            ; return (occ_env', new_external_name) }
1007 1008 1009

  | otherwise = panic "tidyTopName"
  where
1010
    name        = idName id
1011
    external    = isJust maybe_ref
1012 1013 1014 1015
    global      = isExternalName name
    local       = not global
    internal    = not external
    loc         = nameSrcSpan name
1016 1017

    old_occ     = nameOccName name
Simon Peyton Jones's avatar
Simon Peyton Jones committed
1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036
    new_occ | Just ref <- maybe_ref
            , ref /= id
            = mkOccName (occNameSpace old_occ) $
                   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".
            | otherwise = old_occ
1037 1038 1039

    (occ_env', occ') = tidyOccName occ_env new_occ

1040
    mk_new_local nc = (nc { nsUniqs = us }, mkInternalName uniq occ' loc)
1041 1042
                    where
                      (uniq, us) = takeUniqFromSupply (nsUniqs nc)
1