TidyPgm.hs 62.5 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
module TidyPgm (
10
       mkBootModDetailsTc, tidyProgram
11
   ) where
12 13 14

#include "HsVersions.h"

15 16
import GhcPrelude

Simon Marlow's avatar
Simon Marlow committed
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
Simon Peyton Jones's avatar
Simon Peyton Jones committed
42
import Type             ( tidyTopType )
Joachim Breitner's avatar
Joachim Breitner committed
43
import Demand           ( appIsBottom, isTopSig, isBottomingSig )
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 49
import Avail
import IfaceEnv
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 Packages( isDllName )
57
import HscTypes
Simon Marlow's avatar
Simon Marlow committed
58 59
import Maybes
import UniqSupply
60
import Outputable
61
import Util( filterOut )
62
import qualified ErrUtils as Err
Simon Marlow's avatar
Simon Marlow committed
63

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

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

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

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


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

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

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

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

* Drop non-exported Ids from the TypeEnv

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

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

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

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

Simon Marlow's avatar
Simon Marlow committed
135
mkBootModDetailsTc :: HscEnv -> TcGblEnv -> IO ModDetails
136
mkBootModDetailsTc hsc_env
137 138 139 140 141 142 143 144
        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
Simon Marlow's avatar
Simon Marlow committed
145
                }
146 147 148 149 150
  = -- 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 ()) $
151 152 153 154 155 156 157 158
    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
                       })
159
  where
160
    dflags = hsc_dflags hsc_env
161

162 163 164 165 166 167 168 169 170 171 172 173 174
    -- 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
175
                , keep_it id ]
176

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 207
    final_tcs  = filterOut (isWiredInName . getName) tcs
                 -- 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))
208

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 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

312 313 314 315 316 317
 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
318 319 320 321 322


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
323
-}
324

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

344 345 346 347
  = 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
348
              ; expose_all = gopt Opt_ExposeAllUnfoldings  dflags
349
              ; print_unqual = mkPrintUnqualified dflags rdr_env
350
              ; implicit_binds = concatMap getImplicitBinds tcs
351
              }
352

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

359
        ; (tidy_env, tidy_binds)
360
                 <- tidyTopBinds hsc_env mod unfold_env tidy_occ_env trimmed_binds
361

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

374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399
              -- 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)
                             , not (isWiredInName (getName id))
                             ]   -- See Note [Drop wired-in things]

              ; final_tcs      = filterOut (isWiredInName . getName) tcs
                                 -- 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]
400
                all_tidy_binds = implicit_binds ++ tidy_binds'
401 402

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

413
        ; endPassIO hsc_env print_unqual CoreTidy all_tidy_binds tidy_rules
414

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

422 423
          -- Print one-line size info
        ; let cs = coreBindsStats tidy_binds
424 425 426 427 428 429
        ; 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) )
430

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

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

453
--------------------------
454 455 456 457 458 459 460 461 462 463 464
trimId :: Id -> Id
trimId id
  | not (isImplicitId id)
  = id `setIdInfo` vanillaIdInfo
  | otherwise
  = id

{- 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.
465

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

    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
478

479 480 481 482
    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
483

484
    However #7445 shows that even without TemplateHaskell, using
485 486
    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
487

488 489 490 491 492
    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.
493

Austin Seipp's avatar
Austin Seipp committed
494 495
************************************************************************
*                                                                      *
496
        Implicit bindings
Austin Seipp's avatar
Austin Seipp committed
497 498
*                                                                      *
************************************************************************
499 500 501

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

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
513 514 515 516 517
[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.]

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

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

529 530
  - 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
531
    the sense of chooseExternalIds); else the Ids mentioned in *their*
532
    RHSs will be treated as external and you get an interface file
533
    saying      a18 = <blah>
534
    but nothing referring to a18 (because the implicit Id is the
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
535
    one that does, and implicit Ids don't appear in interface files).
536 537 538 539

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

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
541 542 543
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.
544
See Note [Data constructor workers] in CorePrep.
Austin Seipp's avatar
Austin Seipp committed
545
-}
546

547 548 549 550 551
getImplicitBinds :: TyCon -> [CoreBind]
getImplicitBinds tc = cls_binds ++ getTyConImplicitBinds tc
  where
    cls_binds = maybe [] getClassImplicitBinds (tyConClass_maybe tc)

552
getTyConImplicitBinds :: TyCon -> [CoreBind]
553 554 555
getTyConImplicitBinds tc
  | isNewTyCon tc = []  -- See Note [Compulsory newtype unfolding] in MkId
  | otherwise     = map get_defn (mapMaybe dataConWrapId_maybe (tyConDataCons tc))
556 557

getClassImplicitBinds :: Class -> [CoreBind]
558 559 560
getClassImplicitBinds cls
  = [ NonRec op (mkDictSelRhs cls val_index)
    | (op, val_index) <- classAllSelIds cls `zip` [0..] ]
561 562 563

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

Austin Seipp's avatar
Austin Seipp committed
565 566 567
{-
************************************************************************
*                                                                      *
568
\subsection{Step 1: finding externals}
Austin Seipp's avatar
Austin Seipp committed
569 570
*                                                                      *
************************************************************************
571

572
See Note [Choosing external Ids].
Austin Seipp's avatar
Austin Seipp committed
573
-}
574 575

type UnfoldEnv  = IdEnv (Name{-new name-}, Bool {-show unfolding-})
576 577
  -- 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
578
  -- visible in the interface file.
Simon Marlow's avatar
Simon Marlow committed
579 580
  --
  -- Bool => expose unfolding or not.
581 582 583

chooseExternalIds :: HscEnv
                  -> Module
584
                  -> Bool -> Bool
585
                  -> [CoreBind]
586 587
                  -> [CoreBind]
                  -> [CoreRule]
588
                  -> IO (UnfoldEnv, TidyOccEnv)
589
                  -- Step 1 from the notes above
590

591
chooseExternalIds hsc_env mod omit_prags expose_all binds implicit_binds imp_id_rules
592 593 594
  = 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 }
595
 where
596
  nc_var = hsc_NC hsc_env
597

598
  -- init_ext_ids is the initial list of Ids that should be
599
  -- externalised.  It serves as the starting point for finding a
600 601
  -- deterministic, tidy, renaming for all external Ids in this
  -- module.
602
  --
603
  -- It is sorted, so that it has a deterministic order (i.e. it's the
604 605 606
  -- 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
607
  init_ext_ids   = sortBy (compare `on` getOccName) $ filter is_external binders
608

609 610
  -- 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
611
  -- See Note [Which rules to expose]
612
  is_external id = isExportedId id || id `elemVarSet` rule_rhs_vars
613

614
  rule_rhs_vars  = mapUnionVarSet ruleRhsFreeVars imp_id_rules
615

616
  binders          = map fst $ flattenBinds binds
617
  implicit_binders = bindersOfBinds implicit_binds
618
  binder_set       = mkVarSet binders
619

620
  avoids   = [getOccName name | bndr <- binders ++ implicit_binders,
621
                                let name = idName bndr,
622
                                isExternalName name ]
623 624 625 626 627 628
                -- 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.
629 630
                -- In particular, the set of binders doesn't include
                -- implicit Ids at this stage.
631

632 633 634 635 636 637 638 639
        -- 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.
640 641 642
  init_occ_env = initTidyOccEnv avoids


Gabor Greif's avatar
Gabor Greif committed
643
  search :: [(Id,Id)]    -- The work-list: (external id, referring id)
644
                         -- Make a tidy, external Name for the external id,
645 646
                         --   add it to the UnfoldEnv, and do the same for the
                         --   transitive closure of Ids it refers to
647 648
                         -- The referring id is used to generate a tidy
                         ---  name for the external id
649 650 651 652 653 654
         -> 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)

655 656
  search ((idocc,referrer) : rest) unfold_env occ_env
    | idocc `elemVarEnv` unfold_env = search rest unfold_env occ_env
657
    | otherwise = do
658
      (occ_env', name') <- tidyTopName mod nc_var (Just referrer) occ_env idocc
659
      let
660 661
          (new_ids, show_unfold)
                | omit_prags = ([], False)
662
                | otherwise  = addExternal expose_all refined_id
663

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

  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'

684
addExternal :: Bool -> Id -> ([Id], Bool)
685
addExternal expose_all id = (new_needed_ids, show_unfold)
686
  where
687
    new_needed_ids = bndrFvsInOrder show_unfold id
688
    idinfo         = idInfo id
689
    show_unfold    = show_unfolding (unfoldingInfo idinfo)
690
    never_active   = isNeverActive (inlinePragmaActivation (inlinePragInfo idinfo))
691
    loop_breaker   = isStrongLoopBreaker (occInfo idinfo)
692
    bottoming_fn   = isBottomingSig (strictnessInfo idinfo)
693

694 695 696
        -- 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
697 698

    show_unfolding (CoreUnfolding { uf_src = src, uf_guidance = guidance })
699 700
       =  expose_all         -- 'expose_all' says to expose all
                             -- unfoldings willy-nilly
701

702 703
       || isStableSource src     -- Always expose things whose
                                 -- source is an inline rule
704

705 706 707 708
       || 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)
709 710
    show_unfolding (DFunUnfolding {}) = True
    show_unfolding _                  = False
711

Austin Seipp's avatar
Austin Seipp committed
712 713 714
{-
************************************************************************
*                                                                      *
715
               Deterministic free variables
Austin Seipp's avatar
Austin Seipp committed
716 717
*                                                                      *
************************************************************************
718

719 720 721 722
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.
723

724
See Note [Choosing external Ids]
Austin Seipp's avatar
Austin Seipp committed
725
-}
726

727 728 729
bndrFvsInOrder :: Bool -> Id -> [Id]
bndrFvsInOrder show_unfold id
  = run (dffvLetBndr show_unfold id)
730

731 732 733 734
run :: DFFV () -> [Id]
run (DFFV m) = case m emptyVarSet (emptyVarSet, []) of
                 ((_,ids),_) -> ids

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

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

746
instance Monad DFFV where
747 748 749 750 751 752 753 754 755 756
  (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)
757 758

insert :: Var -> DFFV ()
759 760
insert v = DFFV $ \ env (set, ids) ->
           let keep_me = isLocalId v &&
761
                         not (v `elemVarSet` env) &&
762 763
                           not (v `elemVarSet` set)
           in if keep_me
764 765 766
              then ((extendVarSet set v, v:ids), ())
              else ((set,                ids),   ())

767 768

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

dffvLetBndr :: Bool -> Id -> DFFV ()
792 793 794 795 796 797 798 799 800 801 802
-- 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)
803
       ; mapM_ go_rule (ruleInfoRules (ruleInfo idinfo)) }
804
  where
805 806 807 808
    idinfo = idInfo id

    go_unf (CoreUnfolding { uf_tmpl = rhs, uf_src = src })
       = case src of
809 810
           InlineRhs | vanilla_unfold -> dffvExpr rhs
                     | otherwise      -> return ()
811
           _                          -> dffvExpr rhs
812

Austin Seipp's avatar
Austin Seipp committed
813
    go_unf (DFunUnfolding { df_bndrs = bndrs, df_args = args })
814
             = extendScopeList bndrs $ mapM_ dffvExpr args
815 816 817 818 819
    go_unf _ = return ()

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

Austin Seipp's avatar
Austin Seipp committed
821 822 823
{-
************************************************************************
*                                                                      *
824
               findExternalRules
Austin Seipp's avatar
Austin Seipp committed
825 826
*                                                                      *
************************************************************************