TidyPgm.hs

{-
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998

\section{Tidying up Core}
-}

{-# LANGUAGE CPP, ViewPatterns #-}

module TidyPgm (
       mkBootModDetailsTc, tidyProgram, globaliseAndTidyId
   ) where

#include "HsVersions.h"

import TcRnTypes
import DynFlags
import CoreSyn
import CoreUnfold
import CoreFVs
import CoreTidy
import CoreMonad
import CorePrep
import CoreUtils        (rhsIsStatic)
import CoreStats        (coreBindsStats, CoreStats(..))
import CoreLint
import Literal
import Rules
import PatSyn
import ConLike
import CoreArity        ( exprArity, exprBotStrictness_maybe )
import StaticPtrTable
import VarEnv
import VarSet
import Var
import Id
import MkId             ( mkDictSelRhs )
import IdInfo
import InstEnv
import FamInstEnv
import Type             ( tidyTopType )
import Demand           ( appIsBottom, isTopSig, isBottomingSig )
import BasicTypes
import Name hiding (varName)
import NameSet
import NameEnv
import NameCache
import Avail
import IfaceEnv
import TcEnv
import TcRnMonad
import DataCon
import TyCon
import Class
import Module
import Packages( isDllName )
import HscTypes
import Maybes
import UniqSupply
import ErrUtils (Severity(..))
import Outputable
import UniqDFM
import SrcLoc
import qualified ErrUtils as Err

import Control.Monad
import Data.Function
import Data.List        ( sortBy )
import Data.IORef       ( atomicModifyIORef' )

{-
Constructing the TypeEnv, Instances, Rules, VectInfo from which the
ModIface is constructed, and which goes on to subsequent modules in
--make mode.

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 =>
recompilation does not happen => disaster.

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.

************************************************************************
*                                                                      *
                Plan A: simpleTidyPgm
*                                                                      *
************************************************************************


Plan A: mkBootModDetails: omit pragmas, make interfaces small
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Ignore the bindings

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

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

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

* Drop non-exported Ids from the TypeEnv

* Tidy the types of the DFunIds of Instances,
  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

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

* If this an hsig file, drop the instances altogether too (they'll
  get pulled in by the implicit module import.
-}

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

mkBootModDetailsTc :: HscEnv -> TcGblEnv -> IO ModDetails
mkBootModDetailsTc hsc_env
        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_mod       = this_mod
                }
  = -- 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
              ; pat_syns'  = map (tidyPatSynIds   globaliseAndTidyId) pat_syns
              ; type_env1  = mkBootTypeEnv (availsToNameSet exports)
                                           (typeEnvIds type_env) tcs fam_insts
              ; type_env2  = extendTypeEnvWithPatSyns pat_syns' type_env1
              ; dfun_ids   = map instanceDFunId insts'
              ; type_env'  = extendTypeEnvWithIds type_env2 dfun_ids
              }
        ; return (ModDetails { md_types     = type_env'
                             , md_insts     = insts'
                             , md_fam_insts = fam_insts
                             , md_rules     = []
                             , md_anns      = []
                             , md_exports   = exports
                             , md_vect_info = noVectInfo
                             })
        }
  where
    dflags = hsc_dflags hsc_env

mkBootTypeEnv :: NameSet -> [Id] -> [TyCon] -> [FamInst] -> TypeEnv
mkBootTypeEnv exports ids tcs fam_insts
  = tidyTypeEnv True $
       typeEnvFromEntities final_ids tcs fam_insts
  where
        -- 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 = [ (if isLocalId id then globaliseAndTidyId id
                                   else id)
                        `setIdUnfolding` BootUnfolding
                | id <- ids
                , keep_it id ]

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



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

{-
************************************************************************
*                                                                      *
        Plan B: tidy bindings, make TypeEnv full of IdInfo
*                                                                      *
************************************************************************

Plan B: include pragmas, make interfaces
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Figure out which Ids are externally visible

* Tidy the bindings, externalising appropriate Ids

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

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

See also the section "Interface stability" in the
RecompilationAvoidance commentary:
  http://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/RecompilationAvoidance

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

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.

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

 1. Make it into a GlobalId; its IdDetails becomes VanillaGlobal,
    reflecting the fact that from now on we regard it as a global,
    not local, Id

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

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

    For external Ids, use the original-name cache in the NameCache
    to ensure that the unique assigned is the same as the Id had
    in any previous compilation run.

 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

 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


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

tidyProgram :: HscEnv -> ModGuts -> IO (CgGuts, ModDetails)
tidyProgram hsc_env  (ModGuts { mg_module    = mod
                              , mg_exports   = exports
                              , mg_rdr_env   = rdr_env
                              , mg_tcs       = tcs
                              , mg_insts     = cls_insts
                              , mg_fam_insts = fam_insts
                              , mg_binds     = binds
                              , mg_patsyns   = patsyns
                              , mg_rules     = imp_rules
                              , mg_vect_info = vect_info
                              , mg_anns      = anns
                              , mg_deps      = deps
                              , mg_foreign   = foreign_stubs
                              , mg_hpc_info  = hpc_info
                              , mg_modBreaks = modBreaks
                              })

  = Err.withTiming (pure dflags)
                   (text "CoreTidy"<+>brackets (ppr mod))
                   (const ()) $
    do  { let { omit_prags = gopt Opt_OmitInterfacePragmas dflags
              ; expose_all = gopt Opt_ExposeAllUnfoldings  dflags
              ; print_unqual = mkPrintUnqualified dflags rdr_env
              }

        ; let { type_env = typeEnvFromEntities [] tcs fam_insts

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

        ; (unfold_env, tidy_occ_env)
              <- chooseExternalIds hsc_env mod omit_prags expose_all
                                   binds implicit_binds imp_rules (vectInfoVar vect_info)
        ; let { (trimmed_binds, trimmed_rules)
                    = findExternalRules omit_prags binds imp_rules unfold_env }

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

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

              ; tidy_cls_insts = map (tidyClsInstDFun (tidyVarOcc tidy_env)) cls_insts
                -- 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
                -- tidy_cls_insts.  Similarly the Ids inside a PatSyn.

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

              ; tidy_vect_info = tidyVectInfo tidy_env vect_info

                -- 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
              ; tidy_patsyns = map (tidyPatSynIds (tidyVarOcc tidy_env)) patsyns
              ; type_env2    = extendTypeEnvWithPatSyns tidy_patsyns type_env1

              ; tidy_type_env = tidyTypeEnv omit_prags type_env2
              }
          -- 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'

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

        ; endPassIO hsc_env print_unqual CoreTidy all_tidy_binds tidy_rules

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

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

        ; return (CgGuts { cg_module   = mod,
                           cg_tycons   = alg_tycons,
                           cg_binds    = all_tidy_binds,
                           cg_foreign  = foreign_stubs `appendStubC`
                                         spt_init_code,
                           cg_dep_pkgs = map fst $ dep_pkgs deps,
                           cg_hpc_info = hpc_info,
                           cg_modBreaks = modBreaks },

                   ModDetails { md_types     = tidy_type_env,
                                md_rules     = tidy_rules,
                                md_insts     = tidy_cls_insts,
                                md_vect_info = tidy_vect_info,
                                md_fam_insts = fam_insts,
                                md_exports   = exports,
                                md_anns      = anns      -- are already tidy
                              })
        }
  where
    dflags = hsc_dflags hsc_env

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

-- The competed 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]

tidyTypeEnv omit_prags type_env
 = let
        type_env1 = filterNameEnv (not . isWiredInName . getName) type_env
          -- (1) remove wired-in things
        type_env2 | omit_prags = mapNameEnv trimThing type_env1
                  | otherwise  = type_env1
          -- (2) trimmed if necessary
    in
    type_env2

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

trimThing other_thing
  = other_thing

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

tidyVectInfo :: TidyEnv -> VectInfo -> VectInfo
tidyVectInfo (_, var_env) info@(VectInfo { vectInfoVar          = vars
                                         , vectInfoParallelVars = parallelVars
                                         })
  = info { vectInfoVar          = tidy_vars
         , vectInfoParallelVars = tidy_parallelVars
         }
  where
      -- we only export mappings whose domain and co-domain is exported (otherwise, the iface is
      -- inconsistent)
    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)
                          ]

    tidy_parallelVars = mkDVarSet
                          [ tidy_var
                          | var <- dVarSetElems parallelVars
                          , let tidy_var = lookup_var var
                          , isExternalId tidy_var && isExportedId tidy_var
                          ]

    lookup_var var = lookupWithDefaultVarEnv var_env var var

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

{-
Note [Don't attempt to trim data types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
For some time GHC tried to avoid exporting the data constructors
of a data type if it wasn't strictly necessary to do so; see Trac #835.
But "strictly necessary" accumulated a longer and longer list
of exceptions, and finally I gave up the battle:

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

    Stop attempting to "trim" data types in interface files

    Without -O, we previously tried to make interface files smaller
    by not including the data constructors of data types.  But
    there are a lot of exceptions, notably when Template Haskell is
    involved or, more recently, DataKinds.

    However Trac #7445 shows that even without TemplateHaskell, using
    the Data class and invoking Language.Haskell.TH.Quote.dataToExpQ
    is enough to require us to expose the data constructors.

    So I've given up on this "optimisation" -- it's probably not
    important anyway.  Now I'm simply not attempting to trim off
    the data constructors.  The gain in simplicity is worth the
    modest cost in interface file growth, which is limited to the
    bits reqd to describe those data constructors.

************************************************************************
*                                                                      *
        Implicit bindings
*                                                                      *
************************************************************************

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

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

At one time I tried injecting the implicit bindings *early*, at the
beginning of SimplCore.  But that gave rise to real difficulty,
because GlobalIds are supposed to have *fixed* IdInfo, but the
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.

Oh: two other reasons for injecting them late:

  - If implicit Ids are already in the bindings when we start TidyPgm,
    we'd have to be careful not to treat them as external Ids (in
    the sense of chooseExternalIds); else the Ids mentioned in *their*
    RHSs will be treated as external and you get an interface file
    saying      a18 = <blah>
    but nothing referring to a18 (because the implicit Id is the
    one that does, and implicit Ids don't appear in interface files).

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

There is one sort of implicit binding that is injected still later,
namely those for data constructor workers. Reason (I think): it's
really just a code generation trick.... binding itself makes no sense.
See Note [Data constructor workers] in CorePrep.
-}

getTyConImplicitBinds :: TyCon -> [CoreBind]
getTyConImplicitBinds tc = map get_defn (mapMaybe dataConWrapId_maybe (tyConDataCons tc))

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

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

{-
************************************************************************
*                                                                      *
\subsection{Step 1: finding externals}
*                                                                      *
************************************************************************

See Note [Choosing external names].
-}

type UnfoldEnv  = IdEnv (Name{-new name-}, Bool {-show unfolding-})
  -- 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
  -- visible in the interface file.
  --
  -- Bool => expose unfolding or not.

chooseExternalIds :: HscEnv
                  -> Module
                  -> Bool -> Bool
                  -> [CoreBind]
                  -> [CoreBind]
                  -> [CoreRule]
                  -> DVarEnv (Var, Var)
                  -> IO (UnfoldEnv, TidyOccEnv)
                  -- Step 1 from the notes above

chooseExternalIds hsc_env mod omit_prags expose_all binds implicit_binds imp_id_rules vect_vars
  = 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 }
 where
  nc_var = hsc_NC hsc_env

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

  -- An Id should be external if either (a) it is exported,
  -- (b) it appears in the RHS of a local rule for an imported Id, or
  -- (c) it is the vectorised version of an imported Id.
  -- See Note [Which rules to expose]
  is_external id = isExportedId id || id `elemVarSet` rule_rhs_vars
                 || id `elemVarSet` vect_var_vs

  rule_rhs_vars  = mapUnionVarSet ruleRhsFreeVars imp_id_rules
  vect_var_vs    = mkVarSet [var_v | (var, var_v) <- eltsUDFM vect_vars, isGlobalId var]

  binders          = map fst $ flattenBinds binds
  implicit_binders = bindersOfBinds implicit_binds
  binder_set       = mkVarSet binders

  avoids   = [getOccName name | bndr <- binders ++ implicit_binders,
                                let name = idName bndr,
                                isExternalName name ]
                -- 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.
                -- In particular, the set of binders doesn't include
                -- implicit Ids at this stage.

        -- 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.
  init_occ_env = initTidyOccEnv avoids


  search :: [(Id,Id)]    -- The work-list: (external id, referrring id)
                         -- Make a tidy, external Name for the external id,
                         --   add it to the UnfoldEnv, and do the same for the
                         --   transitive closure of Ids it refers to
                         -- The referring id is used to generate a tidy
                         ---  name for the external id
         -> 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)

  search ((idocc,referrer) : rest) unfold_env occ_env
    | idocc `elemVarEnv` unfold_env = search rest unfold_env occ_env
    | otherwise = do
      (occ_env', name') <- tidyTopName mod nc_var (Just referrer) occ_env idocc
      let
          (new_ids, show_unfold)
                | omit_prags = ([], False)
                | otherwise  = addExternal expose_all refined_id

                -- add vectorised version if any exists
          new_ids' = new_ids ++ maybeToList (fmap snd $ lookupDVarEnv vect_vars idocc)

                -- 'idocc' is an *occurrence*, but we need to see the
                -- unfolding in the *definition*; so look up in binder_set
          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
      --
      search (zip new_ids' (repeat referrer') ++ rest) unfold_env' occ_env'

  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'

addExternal :: Bool -> Id -> ([Id], Bool)
addExternal expose_all id = (new_needed_ids, show_unfold)
  where
    new_needed_ids = bndrFvsInOrder show_unfold id
    idinfo         = idInfo id
    show_unfold    = show_unfolding (unfoldingInfo idinfo)
    never_active   = isNeverActive (inlinePragmaActivation (inlinePragInfo idinfo))
    loop_breaker   = isStrongLoopBreaker (occInfo idinfo)
    bottoming_fn   = isBottomingSig (strictnessInfo idinfo)

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

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

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

       || 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)
    show_unfolding (DFunUnfolding {}) = True
    show_unfolding _                  = False

{-
************************************************************************
*                                                                      *
               Deterministic free variables
*                                                                      *
************************************************************************

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.

See Note [Choosing external names]
-}

bndrFvsInOrder :: Bool -> Id -> [Id]
bndrFvsInOrder show_unfold id
  = run (dffvLetBndr show_unfold id)

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

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

instance Functor DFFV where
    fmap = liftM

instance Applicative DFFV where
    pure a = DFFV $ \_ st -> (st, a)
    (<*>) = ap

instance Monad DFFV where
  (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)

insert :: Var -> DFFV ()
insert v = DFFV $ \ env (set, ids) ->
           let keep_me = isLocalId v &&
                         not (v `elemVarSet` env) &&
                           not (v `elemVarSet` set)
           in if keep_me
              then ((extendVarSet set v, v:ids), ())
              else ((set,                ids),   ())


dffvExpr :: CoreExpr -> DFFV ()
dffvExpr (Var v)              = insert v
dffvExpr (App e1 e2)          = dffvExpr e1 >> dffvExpr e2
dffvExpr (Lam v e)            = extendScope v (dffvExpr e)
dffvExpr (Tick (Breakpoint _ ids) e) = mapM_ insert ids >> dffvExpr e
dffvExpr (Tick _other e)    = dffvExpr e
dffvExpr (Cast e _)           = dffvExpr e
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 ()
dffvBind(x,r)
  | not (isId x) = dffvExpr r
  | otherwise    = dffvLetBndr False x >> dffvExpr r
                -- Pass False because we are doing the RHS right here
                -- If you say True you'll get *exponential* behaviour!

dffvLetBndr :: Bool -> Id -> DFFV ()