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

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

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

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

#include "HsVersions.h"

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

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

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

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

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

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


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

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

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

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

* Drop non-exported Ids from the TypeEnv

112
* Tidy the types of the DFunIds of Instances,
113 114 115 116 117 118 119 120
  make them into GlobalIds, (they already have External Names)
  and add them to the TypeEnv

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

* Drop rules altogether

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

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

130 131
-- This is Plan A: make a small type env when typechecking only,
-- or when compiling a hs-boot file, or simply when not using -O
132 133 134
--
-- We don't look at the bindings at all -- there aren't any
-- for hs-boot files
135

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

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

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


200 201

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

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

219
Plan B: include pragmas, make interfaces
220 221 222 223
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Figure out which Ids are externally visible

* Tidy the bindings, externalising appropriate Ids
224

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

Step 1: Figure out external Ids
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
231 232
Note [choosing external names]

Simon Marlow's avatar
Simon Marlow committed
233 234
See also the section "Interface stability" in the
RecompilationAvoidance commentary:
235
  http://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/RecompilationAvoidance
Simon Marlow's avatar
Simon Marlow committed
236

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

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

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

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

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

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

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

 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

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


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
308
-}
309

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

329 330 331 332
  = 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
333
              ; expose_all = gopt Opt_ExposeAllUnfoldings  dflags
334
              ; print_unqual = mkPrintUnqualified dflags rdr_env
335 336
              }

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

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

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

350
        ; (tidy_env, tidy_binds)
351
                 <- tidyTopBinds hsc_env mod unfold_env tidy_occ_env trimmed_binds
352

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

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

363
              ; tidy_rules = tidyRules tidy_env trimmed_rules
364 365 366
                -- You might worry that the tidy_env contains IdInfo-rich stuff
                -- and indeed it does, but if omit_prags is on, ext_rules is
                -- empty
367

368 369
              ; tidy_vect_info = tidyVectInfo tidy_env vect_info

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

              ; tidy_type_env = tidyTypeEnv omit_prags type_env2
378 379 380 381 382 383
              }
          -- See Note [Grand plan for static forms] in StaticPtrTable.
        ; (spt_init_code, tidy_binds') <-
             sptCreateStaticBinds hsc_env mod tidy_binds
        ; let { -- See Note [Injecting implicit bindings]
                all_tidy_binds = implicit_binds ++ tidy_binds'
384 385

              -- Get the TyCons to generate code for.  Careful!  We must use
386 387 388 389 390 391 392
              -- the untidied TypeEnv here, because we need
              --  (a) implicit TyCons arising from types and classes defined
              --      in this module
              --  (b) wired-in TyCons, which are normally removed from the
              --      TypeEnv we put in the ModDetails
              --  (c) Constructors even if they are not exported (the
              --      tidied TypeEnv has trimmed these away)
393 394
              ; alg_tycons = filter isAlgTyCon (typeEnvTyCons type_env)
              }
395

396
        ; endPassIO hsc_env print_unqual CoreTidy all_tidy_binds tidy_rules
397

398 399
          -- If the endPass didn't print the rules, but ddump-rules is
          -- on, print now
400
        ; unless (dopt Opt_D_dump_simpl dflags) $
401
            Err.dumpIfSet_dyn dflags Opt_D_dump_rules
402
              (showSDoc dflags (ppr CoreTidy <+> text "rules"))
403
              (pprRulesForUser tidy_rules)
404

405 406
          -- Print one-line size info
        ; let cs = coreBindsStats tidy_binds
407
        ; when (dopt Opt_D_dump_core_stats dflags)
408
               (log_action dflags dflags NoReason SevDump noSrcSpan defaultDumpStyle
409
                          (text "Tidy size (terms,types,coercions)"
410 411 412
                           <+> ppr (moduleName mod) <> colon
                           <+> int (cs_tm cs)
                           <+> int (cs_ty cs)
413 414
                           <+> int (cs_co cs) ))

415 416 417
        ; return (CgGuts { cg_module   = mod,
                           cg_tycons   = alg_tycons,
                           cg_binds    = all_tidy_binds,
418
                           cg_foreign  = foreign_stubs `appendStubC`
419
                                         spt_init_code,
420 421
                           cg_dep_pkgs = map fst $ dep_pkgs deps,
                           cg_hpc_info = hpc_info,
422
                           cg_modBreaks = modBreaks },
423

424
                   ModDetails { md_types     = tidy_type_env,
425
                                md_rules     = tidy_rules,
426
                                md_insts     = tidy_cls_insts,
427 428
                                md_vect_info = tidy_vect_info,
                                md_fam_insts = fam_insts,
429
                                md_exports   = exports,
430 431
                                md_anns      = anns,      -- are already tidy
                                md_complete_sigs = complete_sigs
chak@cse.unsw.edu.au.'s avatar
chak@cse.unsw.edu.au. committed
432
                              })
433
        }
434 435
  where
    dflags = hsc_dflags hsc_env
436

437
tidyTypeEnv :: Bool       -- Compiling without -O, so omit prags
438
            -> TypeEnv -> TypeEnv
439

440
-- The competed type environment is gotten from
441 442
--      a) the types and classes defined here (plus implicit things)
--      b) adding Ids with correct IdInfo, including unfoldings,
443
--              gotten from the bindings
444
-- From (b) we keep only those Ids with External names;
445 446 447
--          the CoreTidy pass makes sure these are all and only
--          the externally-accessible ones
-- This truncates the type environment to include only the
448
-- exported Ids and things needed from them, which saves space
449 450
--
-- See Note [Don't attempt to trim data types]
451

452
tidyTypeEnv omit_prags type_env
453 454 455
 = let
        type_env1 = filterNameEnv (not . isWiredInName . getName) type_env
          -- (1) remove wired-in things
456
        type_env2 | omit_prags = mapNameEnv trimThing type_env1
457 458 459 460
                  | otherwise  = type_env1
          -- (2) trimmed if necessary
    in
    type_env2
461 462

--------------------------
463
trimThing :: TyThing -> TyThing
464
-- Trim off inessentials, for boot files and no -O
465
trimThing (AnId id)
466
   | not (isImplicitId id)
467
   = AnId (id `setIdInfo` vanillaIdInfo)
468

469
trimThing other_thing
470
  = other_thing
471 472 473 474

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

476
tidyVectInfo :: TidyEnv -> VectInfo -> VectInfo
477
tidyVectInfo (_, var_env) info@(VectInfo { vectInfoVar          = vars
478
                                         , vectInfoParallelVars = parallelVars
479 480
                                         })
  = info { vectInfoVar          = tidy_vars
481
         , vectInfoParallelVars = tidy_parallelVars
482
         }
483
  where
484 485
      -- we only export mappings whose domain and co-domain is exported (otherwise, the iface is
      -- inconsistent)
niteria's avatar
niteria committed
486 487 488 489 490 491 492 493
    tidy_vars = mkDVarEnv [ (tidy_var, (tidy_var, tidy_var_v))
                          | (var, var_v) <- eltsUDFM vars
                          , let tidy_var   = lookup_var var
                                tidy_var_v = lookup_var var_v
                          , isExternalId tidy_var   && isExportedId tidy_var
                          , isExternalId tidy_var_v && isExportedId tidy_var_v
                          , isDataConWorkId var || not (isImplicitId var)
                          ]
494

niteria's avatar
niteria committed
495 496 497 498 499 500
    tidy_parallelVars = mkDVarSet
                          [ tidy_var
                          | var <- dVarSetElems parallelVars
                          , let tidy_var = lookup_var var
                          , isExternalId tidy_var && isExportedId tidy_var
                          ]
501

502
    lookup_var var = lookupWithDefaultVarEnv var_env var var
Austin Seipp's avatar
Austin Seipp committed
503

504 505
    -- We need to make sure that all names getting into the iface version of 'VectInfo' are
    -- external; otherwise, 'MkIface' will bomb out.
506
    isExternalId = isExternalName . idName
507

Austin Seipp's avatar
Austin Seipp committed
508
{-
509 510 511 512
Note [Don't attempt to trim data types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
For some time GHC tried to avoid exporting the data constructors
of a data type if it wasn't strictly necessary to do so; see Trac #835.
Austin Seipp's avatar
Austin Seipp committed
513
But "strictly necessary" accumulated a longer and longer list
Gabor Greif's avatar
typos  
Gabor Greif committed
514
of exceptions, and finally I gave up the battle:
515 516 517 518 519 520

    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
521

522 523 524 525
    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
526

527 528 529
    However Trac #7445 shows that even without TemplateHaskell, using
    the Data class and invoking Language.Haskell.TH.Quote.dataToExpQ
    is enough to require us to expose the data constructors.
Austin Seipp's avatar
Austin Seipp committed
530

531 532 533 534 535
    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.
536

Austin Seipp's avatar
Austin Seipp committed
537 538
************************************************************************
*                                                                      *
539
        Implicit bindings
Austin Seipp's avatar
Austin Seipp committed
540 541
*                                                                      *
************************************************************************
542 543 544

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

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
556 557 558 559 560
[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.]

561 562
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
563
because GlobalIds are supposed to have *fixed* IdInfo, but the
564 565 566 567 568 569
simplifier and other core-to-core passes mess with IdInfo all the
time.  The straw that broke the camels back was when a class selector
got the wrong arity -- ie the simplifier gave it arity 2, whereas
importing modules were expecting it to have arity 1 (Trac #2844).
It's much safer just to inject them right at the end, after tidying.

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

572 573
  - 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
574
    the sense of chooseExternalIds); else the Ids mentioned in *their*
575
    RHSs will be treated as external and you get an interface file
576
    saying      a18 = <blah>
577
    but nothing referring to a18 (because the implicit Id is the
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
578
    one that does, and implicit Ids don't appear in interface files).
579 580 581 582

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

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
584 585 586
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.
587
See Note [Data constructor workers] in CorePrep.
Austin Seipp's avatar
Austin Seipp committed
588
-}
589

590
getTyConImplicitBinds :: TyCon -> [CoreBind]
Icelandjack's avatar
Icelandjack committed
591
getTyConImplicitBinds tc = map get_defn (mapMaybe dataConWrapId_maybe (tyConDataCons tc))
592 593

getClassImplicitBinds :: Class -> [CoreBind]
594 595 596
getClassImplicitBinds cls
  = [ NonRec op (mkDictSelRhs cls val_index)
    | (op, val_index) <- classAllSelIds cls `zip` [0..] ]
597 598 599

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

Austin Seipp's avatar
Austin Seipp committed
601 602 603
{-
************************************************************************
*                                                                      *
604
\subsection{Step 1: finding externals}
Austin Seipp's avatar
Austin Seipp committed
605 606
*                                                                      *
************************************************************************
607

608
See Note [Choosing external names].
Austin Seipp's avatar
Austin Seipp committed
609
-}
610 611

type UnfoldEnv  = IdEnv (Name{-new name-}, Bool {-show unfolding-})
612 613
  -- 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
614
  -- visible in the interface file.
Simon Marlow's avatar
Simon Marlow committed
615 616
  --
  -- Bool => expose unfolding or not.
617 618 619

chooseExternalIds :: HscEnv
                  -> Module
620
                  -> Bool -> Bool
621
                  -> [CoreBind]
622 623
                  -> [CoreBind]
                  -> [CoreRule]
niteria's avatar
niteria committed
624
                  -> DVarEnv (Var, Var)
625
                  -> IO (UnfoldEnv, TidyOccEnv)
626
                  -- Step 1 from the notes above
627

628
chooseExternalIds hsc_env mod omit_prags expose_all binds implicit_binds imp_id_rules vect_vars
629 630 631
  = 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 }
632
 where
633
  nc_var = hsc_NC hsc_env
634

635 636
  -- init_ext_ids is the intial list of Ids that should be
  -- externalised.  It serves as the starting point for finding a
637 638
  -- deterministic, tidy, renaming for all external Ids in this
  -- module.
639
  --
640 641 642 643
  -- It is sorted, so that it has adeterministic order (i.e. it's the
  -- same list every time this module is compiled), in contrast to the
  -- bindings, which are ordered non-deterministically.
  init_work_list = zip init_ext_ids init_ext_ids
644
  init_ext_ids   = sortBy (compare `on` getOccName) $ filter is_external binders
645

646 647
  -- 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
648
  -- (c) it is the vectorised version of an imported Id.
649
  -- See Note [Which rules to expose]
650 651
  is_external id = isExportedId id || id `elemVarSet` rule_rhs_vars
                 || id `elemVarSet` vect_var_vs
652

653
  rule_rhs_vars  = mapUnionVarSet ruleRhsFreeVars imp_id_rules
niteria's avatar
niteria committed
654
  vect_var_vs    = mkVarSet [var_v | (var, var_v) <- eltsUDFM vect_vars, isGlobalId var]
655

656
  binders          = map fst $ flattenBinds binds
657
  implicit_binders = bindersOfBinds implicit_binds
658
  binder_set       = mkVarSet binders
659

660
  avoids   = [getOccName name | bndr <- binders ++ implicit_binders,
661
                                let name = idName bndr,
662
                                isExternalName name ]
663 664 665 666 667 668
                -- 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.
669 670
                -- In particular, the set of binders doesn't include
                -- implicit Ids at this stage.
671

672 673 674 675 676 677 678 679
        -- 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.
680 681 682
  init_occ_env = initTidyOccEnv avoids


683
  search :: [(Id,Id)]    -- The work-list: (external id, referrring id)
684
                         -- Make a tidy, external Name for the external id,
685 686
                         --   add it to the UnfoldEnv, and do the same for the
                         --   transitive closure of Ids it refers to
687 688
                         -- The referring id is used to generate a tidy
                         ---  name for the external id
689 690 691 692 693 694
         -> 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)

695 696
  search ((idocc,referrer) : rest) unfold_env occ_env
    | idocc `elemVarEnv` unfold_env = search rest unfold_env occ_env
697
    | otherwise = do
698
      (occ_env', name') <- tidyTopName mod nc_var (Just referrer) occ_env idocc
699
      let
700 701
          (new_ids, show_unfold)
                | omit_prags = ([], False)
702
                | otherwise  = addExternal expose_all refined_id
703

704
                -- add vectorised version if any exists
niteria's avatar
niteria committed
705
          new_ids' = new_ids ++ maybeToList (fmap snd $ lookupDVarEnv vect_vars idocc)
Austin Seipp's avatar
Austin Seipp committed
706

707 708
                -- 'idocc' is an *occurrence*, but we need to see the
                -- unfolding in the *definition*; so look up in binder_set
709 710 711 712 713 714 715
          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
716
      --
717
      search (zip new_ids' (repeat referrer') ++ rest) unfold_env' occ_env'
718 719 720 721 722 723 724 725 726

  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'

727
addExternal :: Bool -> Id -> ([Id], Bool)
728
addExternal expose_all id = (new_needed_ids, show_unfold)
729
  where
730
    new_needed_ids = bndrFvsInOrder show_unfold id
731
    idinfo         = idInfo id
732
    show_unfold    = show_unfolding (unfoldingInfo idinfo)
733
    never_active   = isNeverActive (inlinePragmaActivation (inlinePragInfo idinfo))
734
    loop_breaker   = isStrongLoopBreaker (occInfo idinfo)
735
    bottoming_fn   = isBottomingSig (strictnessInfo idinfo)
736

737 738 739
        -- 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
740 741

    show_unfolding (CoreUnfolding { uf_src = src, uf_guidance = guidance })
742 743
       =  expose_all         -- 'expose_all' says to expose all
                             -- unfoldings willy-nilly
744

745 746
       || isStableSource src     -- Always expose things whose
                                 -- source is an inline rule
747

748 749 750 751
       || 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)
752 753
    show_unfolding (DFunUnfolding {}) = True
    show_unfolding _                  = False
754

Austin Seipp's avatar
Austin Seipp committed
755 756 757
{-
************************************************************************
*                                                                      *
758
               Deterministic free variables
Austin Seipp's avatar
Austin Seipp committed
759 760
*                                                                      *
************************************************************************
761

762 763 764 765
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.
766

767
See Note [Choosing external names]
Austin Seipp's avatar
Austin Seipp committed
768
-}
769

770 771 772
bndrFvsInOrder :: Bool -> Id -> [Id]
bndrFvsInOrder show_unfold id
  = run (dffvLetBndr show_unfold id)
773

774 775 776 777
run :: DFFV () -> [Id]
run (DFFV m) = case m emptyVarSet (emptyVarSet, []) of
                 ((_,ids),_) -> ids

778 779
newtype DFFV a
  = DFFV (VarSet              -- Envt: non-top-level things that are in scope
780
                              -- we don't want to record these as free vars
781
      -> (VarSet, [Var])      -- Input State: (set, list) of free vars so far
782
      -> ((VarSet,[Var]),a))  -- Output state
783

Austin Seipp's avatar
Austin Seipp committed
784 785 786 787
instance Functor DFFV where
    fmap = liftM

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

791
instance Monad DFFV where
792 793 794 795 796 797 798 799 800 801
  (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)
802 803

insert :: Var -> DFFV ()
804 805
insert v = DFFV $ \ env (set, ids) ->
           let keep_me = isLocalId v &&
806
                         not (v `elemVarSet` env) &&
807 808
                           not (v `elemVarSet` set)
           in if keep_me
809 810 811
              then ((extendVarSet set v, v:ids), ())
              else ((set,                ids),   ())

812 813

dffvExpr :: CoreExpr -> DFFV ()
814
dffvExpr (Var v)              = insert v
815 816
dffvExpr (App e1 e2)          = dffvExpr e1 >> dffvExpr e2
dffvExpr (Lam v e)            = extendScope v (dffvExpr e)
817 818
dffvExpr (Tick (Breakpoint _ ids) e) = mapM_ insert ids >> dffvExpr e
dffvExpr (Tick _other e)    = dffvExpr e
819
dffvExpr (Cast e _)           = dffvExpr e
820 821 822 823 824 825 826 827 828 829
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 ()
830
dffvBind(x,r)
831 832
  | not (isId x) = dffvExpr r
  | otherwise    = dffvLetBndr False x >> dffvExpr r
833 834
                -- Pass False because we are doing the RHS right here
                -- If you say True you'll get *exponential* behaviour!
835 836

dffvLetBndr :: Bool -> Id -> DFFV ()
837 838 839 840 841 842 843