Track object file dependencies for TH accurately (#20604)

`hscCompileCoreExprHook` is changed to return a list of `Module`s required
by a splice. These modules are accumulated in the TcGblEnv (tcg_th_needed_mods).
Dependencies on the object files of these modules are recording in the
interface.

The data structures in `LoaderState` are replaced with more efficient versions
to keep track of all the information required. The
MultiLayerModulesTH_Make allocations increase slightly but runtime is
faster.

Fixes #20604

-------------------------
Metric Increase:
    MultiLayerModulesTH_Make
-------------------------

28 files changed, 365 insertions, 199 deletions

diff --git a/compiler/GHC.hs b/compiler/GHC.hs
index 6fa90108b7..4d31ae1e3a 100644
--- a/compiler/GHC.hs
+++ b/compiler/GHC.hs
@@ -856,7 +856,7 @@ setInteractiveDynFlags dflags = do
 
     -- Initialise (load) plugins in the interactive environment with the new
     -- DynFlags
-    plugin_env <- liftIO $ flip initializePlugins Nothing $ mkInteractiveHscEnv $
+    plugin_env <- liftIO $ initializePlugins $ mkInteractiveHscEnv $
                     hsc_env0 { hsc_IC = ic0 { ic_dflags = dflags'' }}
 
     -- Update both plugins cache and DynFlags in the interactive context.
diff --git a/compiler/GHC/Driver/Hooks.hs b/compiler/GHC/Driver/Hooks.hs
index ae00340d54..7978a5049d 100644
--- a/compiler/GHC/Driver/Hooks.hs
+++ b/compiler/GHC/Driver/Hooks.hs
@@ -72,6 +72,7 @@ import GHC.Data.Bag
 
 import qualified Data.Kind
 import System.Process
+import GHC.Linker.Types
 
 {-
 ************************************************************************
@@ -134,16 +135,15 @@ data Hooks = Hooks
   , tcForeignExportsHook   :: !(Maybe ([LForeignDecl GhcRn]
             -> TcM (LHsBinds GhcTc, [LForeignDecl GhcTc], Bag GlobalRdrElt)))
   , hscFrontendHook        :: !(Maybe (ModSummary -> Hsc FrontendResult))
-  , hscCompileCoreExprHook ::
-               !(Maybe (HscEnv -> (SrcSpan, Maybe ModuleNameWithIsBoot) -> CoreExpr -> IO ForeignHValue))
+  , hscCompileCoreExprHook :: !(Maybe (HscEnv -> SrcSpan -> CoreExpr -> IO (ForeignHValue, [Linkable], PkgsLoaded)))
   , ghcPrimIfaceHook       :: !(Maybe ModIface)
   , runPhaseHook           :: !(Maybe PhaseHook)
   , runMetaHook            :: !(Maybe (MetaHook TcM))
   , linkHook               :: !(Maybe (GhcLink -> DynFlags -> Bool
                                          -> HomePackageTable -> IO SuccessFlag))
   , runRnSpliceHook        :: !(Maybe (HsSplice GhcRn -> RnM (HsSplice GhcRn)))
-  , getValueSafelyHook     :: !(Maybe (HscEnv -> Maybe ModuleNameWithIsBoot -> Name -> Type
-                                         -> IO (Either Type HValue)))
+  , getValueSafelyHook     :: !(Maybe (HscEnv -> Name -> Type
+                                         -> IO (Either Type (HValue, [Linkable], PkgsLoaded))))
   , createIservProcessHook :: !(Maybe (CreateProcess -> IO ProcessHandle))
   , stgToCmmHook           :: !(Maybe (StgToCmmConfig -> InfoTableProvMap -> [TyCon] -> CollectedCCs
                                  -> [CgStgTopBinding] -> HpcInfo -> Stream IO CmmGroup ModuleLFInfos))
diff --git a/compiler/GHC/Driver/Main.hs b/compiler/GHC/Driver/Main.hs
index d0d29a83e7..fc9b96f2e7 100644
--- a/compiler/GHC/Driver/Main.hs
+++ b/compiler/GHC/Driver/Main.hs
@@ -1552,7 +1552,7 @@ hscSimplify' plugins ds_result = do
     hsc_env <- getHscEnv
     hsc_env_with_plugins <- if null plugins -- fast path
         then return hsc_env
-        else liftIO $ flip initializePlugins (Just $ mg_mnwib ds_result)
+        else liftIO $ initializePlugins
                     $ hscUpdateFlags (\dflags -> foldr addPluginModuleName dflags plugins)
                       hsc_env
     {-# SCC "Core2Core" #-}
@@ -1955,7 +1955,7 @@ hscParsedStmt hsc_env stmt = runInteractiveHsc hsc_env $ do
   -- for linking, else we try to link 'main' and can't find it.
   -- Whereas the linker already knows to ignore 'interactive'
   let src_span = srcLocSpan interactiveSrcLoc
-  hval <- liftIO $ hscCompileCoreExpr hsc_env (src_span, Nothing) ds_expr
+  (hval,_,_) <- liftIO $ hscCompileCoreExpr hsc_env src_span ds_expr
 
   return $ Just (ids, hval, fix_env)
 
@@ -2052,10 +2052,10 @@ hscParsedDecls hsc_env decls = runInteractiveHsc hsc_env $ do
                                 stg_binds data_tycons mod_breaks
 
     let src_span = srcLocSpan interactiveSrcLoc
-    _ <- liftIO $ loadDecls interp hsc_env (src_span, Nothing) cbc
+    _ <- liftIO $ loadDecls interp hsc_env src_span cbc
 
     {- Load static pointer table entries -}
-    liftIO $ hscAddSptEntries hsc_env Nothing (cg_spt_entries tidy_cg)
+    liftIO $ hscAddSptEntries hsc_env (cg_spt_entries tidy_cg)
 
     let tcs = filterOut isImplicitTyCon (mg_tcs simpl_mg)
         patsyns = mg_patsyns simpl_mg
@@ -2080,12 +2080,13 @@ hscParsedDecls hsc_env decls = runInteractiveHsc hsc_env $ do
 
 -- | Load the given static-pointer table entries into the interpreter.
 -- See Note [Grand plan for static forms] in "GHC.Iface.Tidy.StaticPtrTable".
-hscAddSptEntries :: HscEnv -> Maybe ModuleNameWithIsBoot -> [SptEntry] -> IO ()
-hscAddSptEntries hsc_env mnwib entries = do
+hscAddSptEntries :: HscEnv -> [SptEntry] -> IO ()
+hscAddSptEntries hsc_env entries = do
     let interp = hscInterp hsc_env
     let add_spt_entry :: SptEntry -> IO ()
         add_spt_entry (SptEntry i fpr) = do
-            val <- loadName interp hsc_env mnwib (idName i)
+            -- These are only names from the current module
+            (val, _, _) <- loadName interp hsc_env (idName i)
             addSptEntry interp fpr val
     mapM_ add_spt_entry entries
 
@@ -2195,13 +2196,13 @@ hscParseThingWithLocation source linenumber parser str = do
 %*                                                                      *
 %********************************************************************* -}
 
-hscCompileCoreExpr :: HscEnv -> (SrcSpan, Maybe ModuleNameWithIsBoot) -> CoreExpr -> IO ForeignHValue
+hscCompileCoreExpr :: HscEnv -> SrcSpan -> CoreExpr -> IO (ForeignHValue, [Linkable], PkgsLoaded)
 hscCompileCoreExpr hsc_env loc expr =
   case hscCompileCoreExprHook (hsc_hooks hsc_env) of
       Nothing -> hscCompileCoreExpr' hsc_env loc expr
       Just h  -> h                   hsc_env loc expr
 
-hscCompileCoreExpr' :: HscEnv -> (SrcSpan, Maybe ModuleNameWithIsBoot) -> CoreExpr -> IO ForeignHValue
+hscCompileCoreExpr' :: HscEnv -> SrcSpan -> CoreExpr -> IO (ForeignHValue, [Linkable], PkgsLoaded)
 hscCompileCoreExpr' hsc_env srcspan ds_expr
     = do { {- Simplify it -}
            -- Question: should we call SimpleOpt.simpleOptExpr here instead?
@@ -2240,10 +2241,10 @@ hscCompileCoreExpr' hsc_env srcspan ds_expr
                      [] Nothing
 
            {- load it -}
-         ; fv_hvs <- loadDecls (hscInterp hsc_env) hsc_env srcspan bcos
+         ; (fv_hvs, mods_needed, units_needed) <- loadDecls (hscInterp hsc_env) hsc_env srcspan bcos
            {- Get the HValue for the root -}
          ; return (expectJust "hscCompileCoreExpr'"
-              $ lookup (idName binding_id) fv_hvs) }
+              $ lookup (idName binding_id) fv_hvs, mods_needed, units_needed) }
 
 
 {- **********************************************************************
diff --git a/compiler/GHC/Driver/Make.hs b/compiler/GHC/Driver/Make.hs
index a46ae37279..6023d3a914 100644
--- a/compiler/GHC/Driver/Make.hs
+++ b/compiler/GHC/Driver/Make.hs
@@ -1166,16 +1166,15 @@ upsweep_mod hsc_env mHscMessage old_hmi summary mod_index nmods =  do
   -- This function only does anything if the linkable produced is a BCO, which only happens with the
   -- bytecode backend, no need to guard against the backend type additionally.
   addSptEntries (hscUpdateHPT (\hpt -> addToHpt hpt (ms_mod_name summary) hmi) hsc_env)
-                (ms_mnwib summary)
                 (hm_linkable hmi)
 
   return hmi
 
 -- | Add the entries from a BCO linkable to the SPT table, see
 -- See Note [Grand plan for static forms] in GHC.Iface.Tidy.StaticPtrTable.
-addSptEntries :: HscEnv -> ModuleNameWithIsBoot -> Maybe Linkable -> IO ()
-addSptEntries hsc_env mnwib mlinkable =
-  hscAddSptEntries hsc_env (Just mnwib)
+addSptEntries :: HscEnv -> Maybe Linkable -> IO ()
+addSptEntries hsc_env mlinkable =
+  hscAddSptEntries hsc_env
      [ spt
      | Just linkable <- [mlinkable]
      , unlinked <- linkableUnlinked linkable
@@ -2523,7 +2522,7 @@ runPipelines _ _ _ [] = return ()
 runPipelines n_job orig_hsc_env mHscMessager all_pipelines = do
   liftIO $ label_self "main --make thread"
 
-  plugins_hsc_env <- initializePlugins orig_hsc_env Nothing
+  plugins_hsc_env <- initializePlugins orig_hsc_env
   case n_job of
     1 -> runSeqPipelines plugins_hsc_env mHscMessager all_pipelines
     _n -> runParPipelines n_job plugins_hsc_env mHscMessager all_pipelines
diff --git a/compiler/GHC/Driver/Pipeline.hs b/compiler/GHC/Driver/Pipeline.hs
index 56e188395e..ab1fb9f76f 100644
--- a/compiler/GHC/Driver/Pipeline.hs
+++ b/compiler/GHC/Driver/Pipeline.hs
@@ -238,7 +238,7 @@ compileOne' mHscMessage
                addFilesToClean tmpfs TFL_GhcSession $
                    [ml_obj_file $ ms_location summary]
 
-   plugin_hsc_env <- initializePlugins hsc_env (Just (ms_mnwib summary))
+   plugin_hsc_env <- initializePlugins hsc_env
    let pipe_env = mkPipeEnv NoStop input_fn pipelineOutput
    status <- hscRecompStatus mHscMessage plugin_hsc_env upd_summary
                 mb_old_iface mb_old_linkable (mod_index, nmods)
diff --git a/compiler/GHC/Driver/Pipeline/Execute.hs b/compiler/GHC/Driver/Pipeline/Execute.hs
index 6bc9df7c6f..c0c7b5d338 100644
--- a/compiler/GHC/Driver/Pipeline/Execute.hs
+++ b/compiler/GHC/Driver/Pipeline/Execute.hs
@@ -671,7 +671,7 @@ runHscPhase pipe_env hsc_env0 input_fn src_flavour = do
   -- run the compiler!
   let msg :: Messager
       msg hsc_env _ what _ = oneShotMsg (hsc_logger hsc_env) what
-  plugin_hsc_env' <- initializePlugins hsc_env (Just $ ms_mnwib mod_summary)
+  plugin_hsc_env' <- initializePlugins hsc_env
 
   -- Need to set the knot-tying mutable variable for interface
   -- files. See GHC.Tc.Utils.TcGblEnv.tcg_type_env_var.
diff --git a/compiler/GHC/Driver/Plugins.hs b/compiler/GHC/Driver/Plugins.hs
index 4fbbd5ce32..9afb556311 100644
--- a/compiler/GHC/Driver/Plugins.hs
+++ b/compiler/GHC/Driver/Plugins.hs
@@ -79,6 +79,8 @@ import Data.List (sort)
 import qualified Data.Semigroup
 
 import Control.Monad
+import GHC.Linker.Types
+import GHC.Types.Unique.DFM
 
 -- | Command line options gathered from the -PModule.Name:stuff syntax
 -- are given to you as this type
@@ -269,10 +271,13 @@ data Plugins = Plugins
       -- The purpose of this field is to cache the plugins so they
       -- don't have to be loaded each time they are needed.  See
       -- 'GHC.Runtime.Loader.initializePlugins'.
+  , loadedPluginDeps :: !([Linkable], PkgsLoaded)
+  -- ^ The object files required by the loaded plugins
+  -- See Note [Plugin dependencies]
   }
 
 emptyPlugins :: Plugins
-emptyPlugins = Plugins [] []
+emptyPlugins = Plugins [] [] ([], emptyUDFM)
 
 
 pluginsWithArgs :: Plugins -> [PluginWithArgs]
diff --git a/compiler/GHC/HsToCore.hs b/compiler/GHC/HsToCore.hs
index 0a210e0871..78d43b164f 100644
--- a/compiler/GHC/HsToCore.hs
+++ b/compiler/GHC/HsToCore.hs
@@ -213,9 +213,10 @@ deSugar hsc_env
         ; used_th <- readIORef tc_splice_used
         ; dep_files <- readIORef dependent_files
         ; safe_mode <- finalSafeMode dflags tcg_env
+        ; (needed_mods, needed_pkgs) <- readIORef (tcg_th_needed_deps tcg_env)
 
-        ; usages <- mkUsageInfo hsc_env mod hsc_src (imp_mods imports) used_names
-                      dep_files merged
+        ; usages <- mkUsageInfo hsc_env mod (imp_mods imports) used_names
+                      dep_files merged needed_mods needed_pkgs
         -- id_mod /= mod when we are processing an hsig, but hsigs
         -- never desugared and compiled (there's no code!)
         -- Consequently, this should hold for any ModGuts that make
diff --git a/compiler/GHC/HsToCore/Usage.hs b/compiler/GHC/HsToCore/Usage.hs
index fbde84deda..2ef692c241 100644
--- a/compiler/GHC/HsToCore/Usage.hs
+++ b/compiler/GHC/HsToCore/Usage.hs
@@ -37,9 +37,9 @@ import Data.Map (Map)
 import qualified Data.Map as Map
 
 import GHC.Linker.Types
-import GHC.Linker.Loader ( getLoaderState )
-import GHC.Types.SourceFile
 import GHC.Unit.Finder
+import GHC.Types.Unique.DFM
+import GHC.Driver.Plugins
 
 {- Note [Module self-dependency]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
@@ -63,14 +63,14 @@ its dep_orphs. This was the cause of #14128.
 mkUsedNames :: TcGblEnv -> NameSet
 mkUsedNames TcGblEnv{ tcg_dus = dus } = allUses dus
 
-mkUsageInfo :: HscEnv -> Module -> HscSource -> ImportedMods -> NameSet -> [FilePath]
-            -> [(Module, Fingerprint)] -> IO [Usage]
-mkUsageInfo hsc_env this_mod src dir_imp_mods used_names dependent_files merged
+mkUsageInfo :: HscEnv -> Module -> ImportedMods -> NameSet -> [FilePath]
+            -> [(Module, Fingerprint)] -> [Linkable] -> PkgsLoaded -> IO [Usage]
+mkUsageInfo hsc_env this_mod dir_imp_mods used_names dependent_files merged needed_links needed_pkgs
   = do
     eps <- hscEPS hsc_env
     hashes <- mapM getFileHash dependent_files
     -- Dependencies on object files due to TH and plugins
-    object_usages <- mkObjectUsage (eps_PIT eps) hsc_env (GWIB (moduleName this_mod) (hscSourceToIsBoot src))
+    object_usages <- mkObjectUsage (eps_PIT eps) hsc_env needed_links needed_pkgs
     let mod_usages = mk_mod_usage_info (eps_PIT eps) hsc_env this_mod
                                        dir_imp_mods used_names
         usages = mod_usages ++ [ UsageFile { usg_file_path = f
@@ -124,24 +124,38 @@ One way to improve this is to either:
     of the module and the implementation hashes of its dependencies, and then
     compare implementation hashes for recompilation. Creation of implementation
     hashes is however potentially expensive.
+
+    A serious issue with the interface hash idea is that if you include an
+    interface hash, that hash also needs to depend on the hash of its
+    dependencies. Therefore, if any of the transitive dependencies of a modules
+    gets updated then you need to recompile the module in case the interface
+    hash has changed irrespective if the module uses TH or not.
+
+    This is important to maintain the invariant that the information in the
+    interface file is always up-to-date.
+
+
+    See #20790 (comment 3)
+-}
+
+{-
+Note [Object File Dependencies]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+In addition to the Note [Plugin dependencies] above, for TH we also need to record
+the hashes of object files that the TH code is required to load. These are
+calculated by the loader in `getLinkDeps` and are accumulated in each individual
+`TcGblEnv`, in `tcg_th_needed_deps`. We read this just before compute the UsageInfo
+to inject the appropriate dependencies.
 -}
 
 -- | Find object files corresponding to the transitive closure of given home
 -- modules and direct object files for pkg dependencies
-mkObjectUsage :: PackageIfaceTable -> HscEnv -> ModuleNameWithIsBoot -> IO [Usage]
-mkObjectUsage pit hsc_env mnwib = do
-  case hsc_interp hsc_env of
-      Just interp -> do
-        mps <- getLoaderState interp
-        case mps of
-          Just ps -> do
-            let ls = fromMaybe [] $ Map.lookup mnwib (module_deps ps)
-                ds = hs_objs_loaded ps
-            concat <$> sequence (map linkableToUsage ls ++ map librarySpecToUsage ds)
-          Nothing -> return []
-      Nothing -> return []
-
-
+mkObjectUsage :: PackageIfaceTable -> HscEnv -> [Linkable] -> PkgsLoaded -> IO [Usage]
+mkObjectUsage pit hsc_env th_links_needed th_pkgs_needed = do
+      let ls = ordNubOn linkableModule  (th_links_needed ++ plugins_links_needed)
+          ds = concatMap loaded_pkg_hs_objs $ eltsUDFM (plusUDFM th_pkgs_needed plugin_pkgs_needed) -- TODO possibly record loaded_pkg_non_hs_objs as well
+          (plugins_links_needed, plugin_pkgs_needed) = loadedPluginDeps $ hsc_plugins hsc_env
+      concat <$> sequence (map linkableToUsage ls ++ map librarySpecToUsage ds)
   where
     linkableToUsage (LM _ m uls) = mapM (unlinkedToUsage m) uls
 
diff --git a/compiler/GHC/Iface/Make.hs b/compiler/GHC/Iface/Make.hs
index c0471cd413..19739ff3e3 100644
--- a/compiler/GHC/Iface/Make.hs
+++ b/compiler/GHC/Iface/Make.hs
@@ -211,6 +211,7 @@ mkIfaceTc hsc_env safe_mode mod_details mod_summary
           let hpc_info = emptyHpcInfo other_hpc_info
           used_th <- readIORef tc_splice_used
           dep_files <- (readIORef dependent_files)
+          (needed_links, needed_pkgs) <- readIORef (tcg_th_needed_deps tc_result)
           -- Do NOT use semantic module here; this_mod in mkUsageInfo
           -- is used solely to decide if we should record a dependency
           -- or not.  When we instantiate a signature, the semantic
@@ -218,8 +219,8 @@ mkIfaceTc hsc_env safe_mode mod_details mod_summary
           -- but if you pass that in here, we'll decide it's the local
           -- module and does not need to be recorded as a dependency.
           -- See Note [Identity versus semantic module]
-          usages <- mkUsageInfo hsc_env this_mod hsc_src (imp_mods imports) used_names
-                      dep_files merged
+          usages <- mkUsageInfo hsc_env this_mod (imp_mods imports) used_names
+                      dep_files merged needed_links needed_pkgs
 
           (doc_hdr', doc_map, arg_map) <- extractDocs tc_result
 
diff --git a/compiler/GHC/Linker/Loader.hs b/compiler/GHC/Linker/Loader.hs
index 046ec5ffd7..7ac5fffab1 100644
--- a/compiler/GHC/Linker/Loader.hs
+++ b/compiler/GHC/Linker/Loader.hs
@@ -29,8 +29,6 @@ module GHC.Linker.Loader
    , withExtendedLoadedEnv
    , extendLoadedEnv
    , deleteFromLoadedEnv
-   -- * Misc
-   , extendLoadedPkgs
    )
 where
 
@@ -66,6 +64,7 @@ import GHC.Types.Name
 import GHC.Types.Name.Env
 import GHC.Types.SrcLoc
 import GHC.Types.Unique.DSet
+import GHC.Types.Unique.DFM
 
 import GHC.Utils.Outputable
 import GHC.Utils.Panic
@@ -88,7 +87,6 @@ import GHC.Unit.State as Packages
 import qualified GHC.Data.ShortText as ST
 import qualified GHC.Data.Maybe as Maybes
 import GHC.Data.FastString
-import GHC.Data.List.SetOps
 
 import GHC.Linker.MacOS
 import GHC.Linker.Dynamic
@@ -98,9 +96,10 @@ import GHC.Linker.Types
 import Control.Monad
 
 import qualified Data.Set as Set
+import qualified Data.Map as M
 import Data.Char (isSpace)
 import Data.IORef
-import Data.List (intercalate, isPrefixOf, isSuffixOf, nub, partition, find)
+import Data.List (intercalate, isPrefixOf, isSuffixOf, nub, partition)
 import Data.Maybe
 import Control.Concurrent.MVar
 import qualified Control.Monad.Catch as MC
@@ -115,14 +114,14 @@ import System.Win32.Info (getSystemDirectory)
 #endif
 
 import GHC.Utils.Exception
-import qualified Data.Map as M
-import Data.Either (partitionEithers)
 
 import GHC.Unit.Module.Graph
 import GHC.Types.SourceFile
 import GHC.Utils.Misc
 import GHC.Iface.Load
 import GHC.Unit.Home
+import Data.Either
+import Control.Applicative
 
 uninitialised :: a
 uninitialised = panic "Loader not initialised"
@@ -147,11 +146,8 @@ emptyLoaderState = LoaderState
    { closure_env = emptyNameEnv
    , itbl_env    = emptyNameEnv
    , pkgs_loaded = init_pkgs
-   , bcos_loaded = []
-   , objs_loaded = []
-   , hs_objs_loaded = []
-   , non_hs_objs_loaded = []
-   , module_deps = M.empty
+   , bcos_loaded = emptyModuleEnv
+   , objs_loaded = emptyModuleEnv
    , temp_sos = []
    }
   -- Packages that don't need loading, because the compiler
@@ -159,12 +155,7 @@ emptyLoaderState = LoaderState
   --
   -- The linker's symbol table is populated with RTS symbols using an
   -- explicit list.  See rts/Linker.c for details.
-  where init_pkgs = [rtsUnitId]
-
-extendLoadedPkgs :: Interp -> [UnitId] -> IO ()
-extendLoadedPkgs interp pkgs =
-  modifyLoaderState_ interp $ \s ->
-      return s{ pkgs_loaded = pkgs ++ pkgs_loaded s }
+  where init_pkgs = unitUDFM rtsUnitId (LoadedPkgInfo rtsUnitId [] [] emptyUniqDSet)
 
 extendLoadedEnv :: Interp -> [(Name,ForeignHValue)] -> IO ()
 extendLoadedEnv interp new_bindings =
@@ -183,21 +174,21 @@ deleteFromLoadedEnv interp to_remove =
 -- | Load the module containing the given Name and get its associated 'HValue'.
 --
 -- Throws a 'ProgramError' if loading fails or the name cannot be found.
-loadName :: Interp -> HscEnv -> Maybe ModuleNameWithIsBoot -> Name -> IO ForeignHValue
-loadName interp hsc_env mnwib name = do
+loadName :: Interp -> HscEnv -> Name -> IO (ForeignHValue, [Linkable], PkgsLoaded)
+loadName interp hsc_env name = do
   initLoaderState interp hsc_env
   modifyLoaderState interp $ \pls0 -> do
-    pls <- if not (isExternalName name)
-       then return pls0
+    (pls, links, pkgs) <- if not (isExternalName name)
+       then return (pls0, [], emptyUDFM)
        else do
-         (pls', ok) <- loadDependencies interp hsc_env pls0 (noSrcSpan, mnwib)
-                          [nameModule name]
+         (pls', ok, links, pkgs) <- loadDependencies interp hsc_env pls0 noSrcSpan
+                                      [nameModule name]
          if failed ok
            then throwGhcExceptionIO (ProgramError "")
-           else return pls'
+           else return (pls', links, pkgs)
 
     case lookupNameEnv (closure_env pls) name of
-      Just (_,aa) -> return (pls,aa)
+      Just (_,aa) -> return (pls,(aa, links, pkgs))
       Nothing     -> assertPpr (isExternalName name) (ppr name) $
                      do let sym_to_find = nameToCLabel name "closure"
                         m <- lookupClosure interp (unpackFS sym_to_find)
@@ -205,14 +196,15 @@ loadName interp hsc_env mnwib name = do
                           Just hvref -> mkFinalizedHValue interp hvref
                           Nothing -> linkFail "GHC.Linker.Loader.loadName"
                                        (unpackFS sym_to_find)
-                        return (pls,r)
+                        return (pls,(r, links, pkgs))
 
 loadDependencies
   :: Interp
   -> HscEnv
   -> LoaderState
-  -> (SrcSpan, Maybe ModuleNameWithIsBoot) -> [Module]
-  -> IO (LoaderState, SuccessFlag)
+  -> SrcSpan
+  -> [Module]
+  -> IO (LoaderState, SuccessFlag, [Linkable], PkgsLoaded) -- ^ returns the set of linkables required
 loadDependencies interp hsc_env pls span needed_mods = do
 --   initLoaderState (hsc_dflags hsc_env) dl
    let dflags = hsc_dflags hsc_env
@@ -220,20 +212,23 @@ loadDependencies interp hsc_env pls span needed_mods = do
    -- the "normal" way, i.e. no non-std ways like profiling or ticky-ticky.
    -- So here we check the build tag: if we're building a non-standard way
    -- then we need to find & link object files built the "normal" way.
-   maybe_normal_osuf <- checkNonStdWay dflags interp (fst span)
+   maybe_normal_osuf <- checkNonStdWay dflags interp span
 
    -- Find what packages and linkables are required
-   (lnks, all_lnks, pkgs) <- getLinkDeps hsc_env pls
-                               maybe_normal_osuf (fst span) needed_mods
-
-   let pls1 =
-        case snd span of
-          Just mn -> pls { module_deps = M.insertWith (++) mn all_lnks (module_deps pls) }
-          Nothing -> pls
+   (lnks, all_lnks, pkgs, this_pkgs_needed)
+      <- getLinkDeps hsc_env pls
+           maybe_normal_osuf span needed_mods
 
    -- Link the packages and modules required
-   pls2 <- loadPackages' interp hsc_env pkgs pls1
-   loadModules interp hsc_env pls2 lnks
+   pls1 <- loadPackages' interp hsc_env pkgs pls
+   (pls2, succ) <- loadModuleLinkables interp hsc_env pls1 lnks
+   let this_pkgs_loaded = udfmRestrictKeys all_pkgs_loaded $ getUniqDSet trans_pkgs_needed
+       all_pkgs_loaded = pkgs_loaded pls2
+       trans_pkgs_needed = unionManyUniqDSets (this_pkgs_needed : [ loaded_pkg_trans_deps pkg
+                                                                  | pkg_id <- uniqDSetToList this_pkgs_needed
+                                                                  , Just pkg <- [lookupUDFM all_pkgs_loaded pkg_id]
+                                                                  ])
+   return (pls2, succ, all_lnks, this_pkgs_loaded)
 
 
 -- | Temporarily extend the loaded env.
@@ -266,9 +261,9 @@ showLoaderState interp = do
   ls <- readMVar (loader_state (interpLoader interp))
   let docs = case ls of
         Nothing  -> [ text "Loader not initialised"]
-        Just pls -> [ text "Pkgs:" <+> ppr (pkgs_loaded pls)
-                    , text "Objs:" <+> ppr (objs_loaded pls)
-                    , text "BCOs:" <+> ppr (bcos_loaded pls)
+        Just pls -> [ text "Pkgs:" <+> ppr (map loaded_pkg_uid $ eltsUDFM $ pkgs_loaded pls)
+                    , text "Objs:" <+> ppr (moduleEnvElts $ objs_loaded pls)
+                    , text "BCOs:" <+> ppr (moduleEnvElts $ bcos_loaded pls)
                     ]
 
   return $ withPprStyle defaultDumpStyle
@@ -588,7 +583,7 @@ preloadLib interp hsc_env lib_paths framework_paths pls lib_spec = do
 -- Raises an IO exception ('ProgramError') if it can't find a compiled
 -- version of the dependents to load.
 --
-loadExpr :: Interp -> HscEnv -> (SrcSpan, Maybe ModuleNameWithIsBoot) -> UnlinkedBCO -> IO ForeignHValue
+loadExpr :: Interp -> HscEnv -> SrcSpan -> UnlinkedBCO -> IO ForeignHValue
 loadExpr interp hsc_env span root_ul_bco = do
   -- Initialise the linker (if it's not been done already)
   initLoaderState interp hsc_env
@@ -596,7 +591,7 @@ loadExpr interp hsc_env span root_ul_bco = do
   -- Take lock for the actual work.
   modifyLoaderState interp $ \pls0 -> do
     -- Load the packages and modules required
-    (pls, ok) <- loadDependencies interp hsc_env pls0 span needed_mods
+    (pls, ok, _, _) <- loadDependencies interp hsc_env pls0 span needed_mods
     if failed ok
       then throwGhcExceptionIO (ProgramError "")
       else do
@@ -691,7 +686,9 @@ getLinkDeps :: HscEnv
             -> Maybe FilePath                   -- replace object suffixes?
             -> SrcSpan                          -- for error messages
             -> [Module]                         -- If you need these
-            -> IO ([Linkable], [Linkable], [UnitId])     -- ... then link these first
+            -> IO ([Linkable], [Linkable], [UnitId], UniqDSet UnitId)     -- ... then link these first
+            -- The module and package dependencies for the needed modules are returned.
+            -- See Note [Object File Dependencies]
 -- Fails with an IO exception if it can't find enough files
 
 getLinkDeps hsc_env pls replace_osuf span mods
@@ -708,16 +705,16 @@ getLinkDeps hsc_env pls replace_osuf span mods
                               emptyUniqDSet emptyUniqDSet;
             else do
               (pkgs, mmods) <- unzip <$> mapM get_mod_info all_home_mods
-              return (catMaybes mmods, Set.toList (Set.unions (init_pkg_set : pkgs)))
+              return (catMaybes mmods, unionManyUniqDSets (init_pkg_set : pkgs))
 
       ; let
         -- 2.  Exclude ones already linked
         --      Main reason: avoid findModule calls in get_linkable
-            (mods_needed, mods_got) = partitionEithers (map split_mods mods_s)
-            pkgs_needed = pkgs_s `minusList` pkgs_loaded pls
+            (mods_needed, links_got) = partitionEithers (map split_mods mods_s)
+            pkgs_needed = eltsUDFM $ getUniqDSet pkgs_s `minusUDFM` pkgs_loaded pls
 
             split_mods mod =
-                let is_linked = find ((== mod) . (linkableModule)) (objs_loaded pls ++ bcos_loaded pls)
+                let is_linked = findModuleLinkable_maybe (objs_loaded pls) mod <|> findModuleLinkable_maybe (bcos_loaded pls) mod
                 in case is_linked of
                      Just linkable -> Right linkable
                      Nothing -> Left mod
@@ -728,7 +725,7 @@ getLinkDeps hsc_env pls replace_osuf span mods
       ; let { osuf = objectSuf dflags }
       ; lnks_needed <- mapM (get_linkable osuf) mods_needed
 
-      ; return (lnks_needed, mods_got ++ lnks_needed, pkgs_needed) }
+      ; return (lnks_needed, links_got ++ lnks_needed, pkgs_needed, pkgs_s) }
   where
     dflags = hsc_dflags hsc_env
     mod_graph = hsc_mod_graph hsc_env
@@ -741,7 +738,7 @@ getLinkDeps hsc_env pls replace_osuf span mods
 
     -- It is also a matter of correctness to use the module graph so that dependencies between home units
     -- is resolved correctly.
-    make_deps_loop :: (Set.Set UnitId, Set.Set NodeKey) -> [ModNodeKeyWithUid] -> (Set.Set UnitId, Set.Set NodeKey)
+    make_deps_loop :: (UniqDSet UnitId, Set.Set NodeKey) -> [ModNodeKeyWithUid] -> (UniqDSet UnitId, Set.Set NodeKey)
     make_deps_loop found [] = found
     make_deps_loop found@(found_units, found_mods) (nk:nexts)
       | NodeKey_Module nk `Set.member` found_mods = make_deps_loop found nexts
@@ -755,10 +752,10 @@ getLinkDeps hsc_env pls replace_osuf span mods
               in make_deps_loop (found_units, deps `Set.union` found_mods) (todo_boot_mods ++ nexts)
             Nothing ->
               let (ModNodeKeyWithUid _ uid) = nk
-              in make_deps_loop (uid `Set.insert` found_units, found_mods) nexts
+              in make_deps_loop (addOneToUniqDSet found_units uid, found_mods) nexts
 
     mkNk m = ModNodeKeyWithUid (GWIB (moduleName m) NotBoot) (moduleUnitId m)
-    (init_pkg_set, all_deps) = make_deps_loop (Set.empty, Set.empty) $ map mkNk (filterOut isInteractiveModule mods)
+    (init_pkg_set, all_deps) = make_deps_loop (emptyUniqDSet, Set.empty) $ map mkNk (filterOut isInteractiveModule mods)
 
     all_home_mods = [with_uid | NodeKey_Module with_uid <- Set.toList all_deps]
 
@@ -770,7 +767,7 @@ getLinkDeps hsc_env pls replace_osuf span mods
                       HsBootFile -> link_boot_mod_error (mi_module iface)
                       _ -> return $ Just (mi_module iface)
 
-          in (dep_direct_pkgs (mi_deps iface),) <$>  mmod
+          in (mkUniqDSet $ Set.toList $ dep_direct_pkgs (mi_deps iface),) <$>  mmod
         Nothing ->
           let err = text "getLinkDeps: Home module not loaded" <+> ppr (gwib_mod gwib) <+> ppr uid
           in throwGhcExceptionIO (ProgramError (showSDoc dflags err))
@@ -786,9 +783,9 @@ getLinkDeps hsc_env pls replace_osuf span mods
     follow_deps :: [Module]             -- modules to follow
                 -> UniqDSet Module         -- accum. module dependencies
                 -> UniqDSet UnitId          -- accum. package dependencies
-                -> IO ([Module], [UnitId]) -- result
+                -> IO ([Module], UniqDSet UnitId) -- result
     follow_deps []     acc_mods acc_pkgs
-        = return (uniqDSetToList acc_mods, uniqDSetToList acc_pkgs)
+        = return (uniqDSetToList acc_mods, acc_pkgs)
     follow_deps (mod:mods) acc_mods acc_pkgs
         = do
           mb_iface <- initIfaceCheck (text "getLinkDeps") hsc_env $
@@ -892,14 +889,13 @@ getLinkDeps hsc_env pls replace_osuf span mods
             adjust_ul _ l@(BCOs {}) = return l
 
 
-
 {- **********************************************************************
 
               Loading a Decls statement
 
   ********************************************************************* -}
 
-loadDecls :: Interp -> HscEnv -> (SrcSpan, Maybe ModuleNameWithIsBoot) -> CompiledByteCode -> IO [(Name, ForeignHValue)]
+loadDecls :: Interp -> HscEnv -> SrcSpan -> CompiledByteCode -> IO ([(Name, ForeignHValue)], [Linkable], PkgsLoaded)
 loadDecls interp hsc_env span cbc@CompiledByteCode{..} = do
     -- Initialise the linker (if it's not been done already)
     initLoaderState interp hsc_env
@@ -907,7 +903,7 @@ loadDecls interp hsc_env span cbc@CompiledByteCode{..} = do
     -- Take lock for the actual work.
     modifyLoaderState interp $ \pls0 -> do
       -- Link the packages and modules required
-      (pls, ok) <- loadDependencies interp hsc_env pls0 span needed_mods
+      (pls, ok, links_needed, units_needed) <- loadDependencies interp hsc_env pls0 span needed_mods
       if failed ok
         then throwGhcExceptionIO (ProgramError "")
         else do
@@ -921,7 +917,7 @@ loadDecls interp hsc_env span cbc@CompiledByteCode{..} = do
           nms_fhvs <- makeForeignNamedHValueRefs interp new_bindings
           let pls2 = pls { closure_env = extendClosureEnv ce nms_fhvs
                          , itbl_env    = ie }
-          return (pls2, nms_fhvs)
+          return (pls2, (nms_fhvs, links_needed, units_needed))
   where
     free_names = uniqDSetToList $
       foldr (unionUniqDSets . bcoFreeNames) emptyUniqDSet bc_bcos
@@ -942,11 +938,11 @@ loadDecls interp hsc_env span cbc@CompiledByteCode{..} = do
 
   ********************************************************************* -}
 
-loadModule :: Interp -> HscEnv -> Maybe ModuleNameWithIsBoot -> Module -> IO ()
-loadModule interp hsc_env mnwib mod = do
+loadModule :: Interp -> HscEnv -> Module -> IO ()
+loadModule interp hsc_env mod = do
   initLoaderState interp hsc_env
   modifyLoaderState_ interp $ \pls -> do
-    (pls', ok) <- loadDependencies interp hsc_env pls (noSrcSpan, mnwib) [mod]
+    (pls', ok, _, _) <- loadDependencies interp hsc_env pls noSrcSpan [mod]
     if failed ok
       then throwGhcExceptionIO (ProgramError "could not load module")
       else return pls'
@@ -959,8 +955,8 @@ loadModule interp hsc_env mnwib mod = do
 
   ********************************************************************* -}
 
-loadModules :: Interp -> HscEnv -> LoaderState -> [Linkable] -> IO (LoaderState, SuccessFlag)
-loadModules interp hsc_env pls linkables
+loadModuleLinkables :: Interp -> HscEnv -> LoaderState -> [Linkable] -> IO (LoaderState, SuccessFlag)
+loadModuleLinkables interp hsc_env pls linkables
   = mask_ $ do  -- don't want to be interrupted by ^C in here
 
         let (objs, bcos) = partition isObjectLinkable
@@ -989,14 +985,10 @@ partitionLinkable li
                            li {linkableUnlinked=li_uls_bco}]
             _ -> [li]
 
-findModuleLinkable_maybe :: [Linkable] -> Module -> Maybe Linkable
-findModuleLinkable_maybe lis mod
-   = case [LM time nm us | LM time nm us <- lis, nm == mod] of
-        []   -> Nothing
-        [li] -> Just li
-        _    -> pprPanic "findModuleLinkable" (ppr mod)
+findModuleLinkable_maybe :: LinkableSet -> Module -> Maybe Linkable
+findModuleLinkable_maybe = lookupModuleEnv
 
-linkableInSet :: Linkable -> [Linkable] -> Bool
+linkableInSet :: Linkable -> LinkableSet -> Bool
 linkableInSet l objs_loaded =
   case findModuleLinkable_maybe objs_loaded (linkableModule l) of
         Nothing -> False
@@ -1100,7 +1092,7 @@ dynLoadObjs interp hsc_env pls@LoaderState{..} objs = do
     -- link all "loaded packages" so symbols in those can be resolved
     -- Note: We are loading packages with local scope, so to see the
     -- symbols in this link we must link all loaded packages again.
-    linkDynLib logger tmpfs dflags2 unit_env objs pkgs_loaded
+    linkDynLib logger tmpfs dflags2 unit_env objs (loaded_pkg_uid <$> eltsUDFM pkgs_loaded)
 
     -- if we got this far, extend the lifetime of the library file
     changeTempFilesLifetime tmpfs TFL_GhcSession [soFile]
@@ -1111,9 +1103,9 @@ dynLoadObjs interp hsc_env pls@LoaderState{..} objs = do
   where
     msg = "GHC.Linker.Loader.dynLoadObjs: Loading temp shared object failed"
 
-rmDupLinkables :: [Linkable]    -- Already loaded
+rmDupLinkables :: LinkableSet    -- Already loaded
                -> [Linkable]    -- New linkables
-               -> ([Linkable],  -- New loaded set (including new ones)
+               -> (LinkableSet,  -- New loaded set (including new ones)
                    [Linkable])  -- New linkables (excluding dups)
 rmDupLinkables already ls
   = go already [] ls
@@ -1121,7 +1113,7 @@ rmDupLinkables already ls
     go already extras [] = (already, extras)
     go already extras (l:ls)
         | linkableInSet l already = go already     extras     ls
-        | otherwise               = go (l:already) (l:extras) ls
+        | otherwise               = go (extendModuleEnv already (linkableModule l) l) (l:extras) ls
 
 {- **********************************************************************
 
@@ -1232,9 +1224,9 @@ unload interp hsc_env linkables
 
         let logger = hsc_logger hsc_env
         debugTraceMsg logger 3 $
-          text "unload: retaining objs" <+> ppr (objs_loaded new_pls)
+          text "unload: retaining objs" <+> ppr (moduleEnvElts $ objs_loaded new_pls)
         debugTraceMsg logger 3 $
-          text "unload: retaining bcos" <+> ppr (bcos_loaded new_pls)
+          text "unload: retaining bcos" <+> ppr (moduleEnvElts $ bcos_loaded new_pls)
         return ()
 
 unload_wkr
@@ -1250,32 +1242,32 @@ unload_wkr interp keep_linkables pls@LoaderState{..}  = do
   -- we're unloading some code.  -fghci-leak-check with the tests in
   -- testsuite/ghci can detect space leaks here.
 
-  let (objs_to_keep, bcos_to_keep) = partition isObjectLinkable keep_linkables
+  let (objs_to_keep', bcos_to_keep') = partition isObjectLinkable keep_linkables
+      objs_to_keep = mkLinkableSet objs_to_keep'
+      bcos_to_keep = mkLinkableSet bcos_to_keep'
 
       discard keep l = not (linkableInSet l keep)
 
       (objs_to_unload, remaining_objs_loaded) =
-         partition (discard objs_to_keep) objs_loaded
+         partitionModuleEnv (discard objs_to_keep) objs_loaded
       (bcos_to_unload, remaining_bcos_loaded) =
-         partition (discard bcos_to_keep) bcos_loaded
+         partitionModuleEnv (discard bcos_to_keep) bcos_loaded
+
+      linkables_to_unload = moduleEnvElts objs_to_unload ++ moduleEnvElts bcos_to_unload
 
-  mapM_ unloadObjs objs_to_unload
-  mapM_ unloadObjs bcos_to_unload
+  mapM_ unloadObjs linkables_to_unload
 
   -- If we unloaded any object files at all, we need to purge the cache
   -- of lookupSymbol results.
-  when (not (null (objs_to_unload ++
-                   filter (not . null . linkableObjs) bcos_to_unload))) $
+  when (not (null (filter (not . null . linkableObjs) linkables_to_unload))) $
     purgeLookupSymbolCache interp
 
-  let !bcos_retained = mkModuleSet $ map linkableModule remaining_bcos_loaded
-
-      -- Note that we want to remove all *local*
+  let -- Note that we want to remove all *local*
       -- (i.e. non-isExternal) names too (these are the
       -- temporary bindings from the command line).
       keep_name :: (Name, a) -> Bool
       keep_name (n,_) = isExternalName n &&
-                        nameModule n `elemModuleSet` bcos_retained
+                        nameModule n `elemModuleEnv` remaining_bcos_loaded
 
       itbl_env'     = filterNameEnv keep_name itbl_env
       closure_env'  = filterNameEnv keep_name closure_env
@@ -1350,25 +1342,29 @@ loadPackages interp hsc_env new_pkgs = do
 
 loadPackages' :: Interp -> HscEnv -> [UnitId] -> LoaderState -> IO LoaderState
 loadPackages' interp hsc_env new_pks pls = do
-    (pkgs', hs_objs, non_hs_objs) <- link (pkgs_loaded pls) new_pks
+    pkgs' <- link (pkgs_loaded pls) new_pks
     return $! pls { pkgs_loaded = pkgs'
-                  , hs_objs_loaded = hs_objs ++ hs_objs_loaded pls
-                  , non_hs_objs_loaded = non_hs_objs ++ non_hs_objs_loaded pls }
+                  }
   where
-     link :: [UnitId] -> [UnitId] -> IO ([UnitId], [LibrarySpec], [LibrarySpec])
+     link :: PkgsLoaded -> [UnitId] -> IO PkgsLoaded
      link pkgs new_pkgs =
-         foldM link_one (pkgs, [],[]) new_pkgs
+         foldM link_one pkgs new_pkgs
 
-     link_one (pkgs, acc_hs, acc_non_hs) new_pkg
-        | new_pkg `elem` pkgs   -- Already linked
-        = return (pkgs, acc_hs, acc_non_hs)
+     link_one pkgs new_pkg
+        | new_pkg `elemUDFM` pkgs   -- Already linked
+        = return pkgs
 
         | Just pkg_cfg <- lookupUnitId (hsc_units hsc_env) new_pkg
-        = do {  -- Link dependents first
-               (pkgs', hs_cls', extra_cls') <- link pkgs (unitDepends pkg_cfg)
+        = do { let deps = unitDepends pkg_cfg
+               -- Link dependents first
+             ; pkgs' <- link pkgs deps
                 -- Now link the package itself
              ; (hs_cls, extra_cls) <- loadPackage interp hsc_env pkg_cfg
-             ; return (new_pkg : pkgs', acc_hs ++ hs_cls ++ hs_cls', acc_non_hs ++ extra_cls ++ extra_cls') }
+             ; let trans_deps = unionManyUniqDSets [ addOneToUniqDSet (loaded_pkg_trans_deps loaded_pkg_info) dep_pkg
+                                                   | dep_pkg <- deps
+                                                   , Just loaded_pkg_info <- pure (lookupUDFM pkgs' dep_pkg)
+                                                   ]
+             ; return (addToUDFM pkgs' new_pkg (LoadedPkgInfo new_pkg hs_cls extra_cls trans_deps)) }
 
         | otherwise
         = throwGhcExceptionIO (CmdLineError ("unknown package: " ++ unpackFS (unitIdFS new_pkg)))
diff --git a/compiler/GHC/Linker/Types.hs b/compiler/GHC/Linker/Types.hs
index 17bb46feb9..040b7f8deb 100644
--- a/compiler/GHC/Linker/Types.hs
+++ b/compiler/GHC/Linker/Types.hs
@@ -11,6 +11,9 @@ module GHC.Linker.Types
    , LoaderState (..)
    , uninitializedLoader
    , Linkable(..)
+   , LinkableSet
+   , mkLinkableSet
+   , unionLinkableSet
    , Unlinked(..)
    , SptEntry(..)
    , isObjectLinkable
@@ -21,11 +24,13 @@ module GHC.Linker.Types
    , isInterpretable
    , byteCodeOfObject
    , LibrarySpec(..)
+   , LoadedPkgInfo(..)
+   , PkgsLoaded
    )
 where
 
 import GHC.Prelude
-import GHC.Unit                ( UnitId, Module, ModuleNameWithIsBoot )
+import GHC.Unit                ( UnitId, Module )
 import GHC.ByteCode.Types      ( ItblEnv, CompiledByteCode )
 import GHC.Fingerprint.Type    ( Fingerprint )
 import GHCi.RemoteTypes        ( ForeignHValue )
@@ -40,7 +45,9 @@ import GHC.Utils.Panic
 import Control.Concurrent.MVar
 import Data.Time               ( UTCTime )
 import Data.Maybe
-import qualified Data.Map as M
+import GHC.Unit.Module.Env
+import GHC.Types.Unique.DSet
+import GHC.Types.Unique.DFM
 
 
 {- **********************************************************************
@@ -75,19 +82,15 @@ data LoaderState = LoaderState
         -- module in the image is replaced, the itbl_env must be updated
         -- appropriately.
 
-    , bcos_loaded :: ![Linkable]
+    , bcos_loaded :: !LinkableSet
         -- ^ The currently loaded interpreted modules (home package)
 
-    , objs_loaded :: ![Linkable]
+    , objs_loaded :: !LinkableSet
         -- ^ And the currently-loaded compiled modules (home package)
 
-    , pkgs_loaded :: ![UnitId]
+    , pkgs_loaded :: !PkgsLoaded
         -- ^ The currently-loaded packages; always object code
-        -- Held, as usual, in dependency order; though I am not sure if
-        -- that is really important
-    , hs_objs_loaded :: ![LibrarySpec]
-    , non_hs_objs_loaded :: ![LibrarySpec]
-    , module_deps :: M.Map ModuleNameWithIsBoot [Linkable]
+        -- haskell libraries, system libraries, transitive dependencies
 
     , temp_sos :: ![(FilePath, String)]
         -- ^ We need to remember the name of previous temporary DLL/.so
@@ -98,6 +101,23 @@ uninitializedLoader :: IO Loader
 uninitializedLoader = Loader <$> newMVar Nothing
 
 type ClosureEnv = NameEnv (Name, ForeignHValue)
+type PkgsLoaded = UniqDFM UnitId LoadedPkgInfo
+
+data LoadedPkgInfo
+  = LoadedPkgInfo
+  { loaded_pkg_uid         :: !UnitId
+  , loaded_pkg_hs_objs     :: ![LibrarySpec]
+  , loaded_pkg_non_hs_objs :: ![LibrarySpec]
+  , loaded_pkg_trans_deps  :: UniqDSet UnitId
+  }
+
+instance Outputable LoadedPkgInfo where
+  ppr (LoadedPkgInfo uid hs_objs non_hs_objs trans_deps) =
+    vcat [ppr uid
+         , ppr hs_objs
+         , ppr non_hs_objs
+         , ppr trans_deps ]
+
 
 -- | Information we can use to dynamically link modules into the compiler
 data Linkable = LM {
@@ -111,6 +131,18 @@ data Linkable = LM {
     -- INVARIANT: A valid linkable always has at least one 'Unlinked' item.
  }
 
+type LinkableSet = ModuleEnv Linkable
+
+mkLinkableSet :: [Linkable] -> LinkableSet
+mkLinkableSet ls = mkModuleEnv [(linkableModule l, l) | l <- ls]
+
+unionLinkableSet :: LinkableSet -> LinkableSet -> LinkableSet
+unionLinkableSet = plusModuleEnv_C go
+  where
+    go l1 l2
+      | linkableTime l1 > linkableTime l2 = l1
+      | otherwise = l2
+
 instance Outputable Linkable where
   ppr (LM when_made mod unlinkeds)
      = (text "LinkableM" <+> parens (text (show when_made)) <+> ppr mod)
diff --git a/compiler/GHC/Runtime/Eval.hs b/compiler/GHC/Runtime/Eval.hs
index 5c2f6ff6cc..b4bf25b9b3 100644
--- a/compiler/GHC/Runtime/Eval.hs
+++ b/compiler/GHC/Runtime/Eval.hs
@@ -1278,13 +1278,13 @@ obtainTermFromVal hsc_env _bound _force _ty _x = case interpInstance interp of
 
 obtainTermFromId :: HscEnv -> Int -> Bool -> Id -> IO Term
 obtainTermFromId hsc_env bound force id =  do
-  hv <- Loader.loadName (hscInterp hsc_env) hsc_env Nothing (varName id)
+  (hv, _, _) <- Loader.loadName (hscInterp hsc_env) hsc_env (varName id)
   cvObtainTerm hsc_env bound force (idType id) hv
 
 -- Uses RTTI to reconstruct the type of an Id, making it less polymorphic
 reconstructType :: HscEnv -> Int -> Id -> IO (Maybe Type)
 reconstructType hsc_env bound id = do
-  hv <- Loader.loadName (hscInterp hsc_env) hsc_env Nothing (varName id)
+  (hv, _, _) <- Loader.loadName (hscInterp hsc_env) hsc_env (varName id)
   cvReconstructType hsc_env bound (idType id) hv
 
 mkRuntimeUnkTyVar :: Name -> Kind -> TyVar
diff --git a/compiler/GHC/Runtime/Loader.hs b/compiler/GHC/Runtime/Loader.hs
index 3803bc39fe..393573fd24 100644
--- a/compiler/GHC/Runtime/Loader.hs
+++ b/compiler/GHC/Runtime/Loader.hs
@@ -65,14 +65,16 @@ import GHC.Utils.Exception
 import Control.Monad     ( unless )
 import Data.Maybe        ( mapMaybe )
 import Unsafe.Coerce     ( unsafeCoerce )
-import GHC.Unit.Types (ModuleNameWithIsBoot)
+import GHC.Linker.Types
+import GHC.Types.Unique.DFM
+import Data.List (unzip4)
 
 -- | Loads the plugins specified in the pluginModNames field of the dynamic
 -- flags. Should be called after command line arguments are parsed, but before
 -- actual compilation starts. Idempotent operation. Should be re-called if
 -- pluginModNames or pluginModNameOpts changes.
-initializePlugins :: HscEnv -> Maybe ModuleNameWithIsBoot -> IO HscEnv
-initializePlugins hsc_env mnwib
+initializePlugins :: HscEnv -> IO HscEnv
+initializePlugins hsc_env
     -- plugins not changed
   | loaded_plugins <- loadedPlugins (hsc_plugins hsc_env)
   , map lpModuleName loaded_plugins == reverse (pluginModNames dflags)
@@ -80,8 +82,8 @@ initializePlugins hsc_env mnwib
   , all same_args loaded_plugins
   = return hsc_env -- no need to reload plugins FIXME: doesn't take static plugins into account
   | otherwise
-  = do loaded_plugins <- loadPlugins hsc_env mnwib
-       let plugins' = (hsc_plugins hsc_env) { loadedPlugins = loaded_plugins }
+  = do (loaded_plugins, links, pkgs) <- loadPlugins hsc_env
+       let plugins' = (hsc_plugins hsc_env) { loadedPlugins = loaded_plugins, loadedPluginDeps = (links, pkgs) }
        let hsc_env' = hsc_env { hsc_plugins = plugins' }
        withPlugins (hsc_plugins hsc_env') driverPlugin hsc_env'
   where
@@ -90,12 +92,14 @@ initializePlugins hsc_env mnwib
     argumentsForPlugin p = map snd . filter ((== lpModuleName p) . fst)
     dflags = hsc_dflags hsc_env
 
-loadPlugins :: HscEnv -> Maybe ModuleNameWithIsBoot -> IO [LoadedPlugin]
-loadPlugins hsc_env mnwib
+loadPlugins :: HscEnv -> IO ([LoadedPlugin], [Linkable], PkgsLoaded)
+loadPlugins hsc_env
   = do { unless (null to_load) $
            checkExternalInterpreter hsc_env
-       ; plugins <- mapM loadPlugin to_load
-       ; return $ zipWith attachOptions to_load plugins }
+       ; plugins_with_deps <- mapM loadPlugin to_load
+       ; let (plugins, ifaces, links, pkgs) = unzip4 plugins_with_deps
+       ; return (zipWith attachOptions to_load (zip plugins ifaces), concat links, foldl' plusUDFM emptyUDFM pkgs)
+       }
   where
     dflags  = hsc_dflags hsc_env
     to_load = reverse $ pluginModNames dflags
@@ -105,14 +109,16 @@ loadPlugins hsc_env mnwib
       where
         options = [ option | (opt_mod_nm, option) <- pluginModNameOpts dflags
                             , opt_mod_nm == mod_nm ]
-    loadPlugin = loadPlugin' (mkVarOcc "plugin") pluginTyConName hsc_env mnwib
+    loadPlugin = loadPlugin' (mkVarOcc "plugin") pluginTyConName hsc_env
 
 
-loadFrontendPlugin :: HscEnv -> ModuleName -> IO FrontendPlugin
+loadFrontendPlugin :: HscEnv -> ModuleName -> IO (FrontendPlugin, [Linkable], PkgsLoaded)
 loadFrontendPlugin hsc_env mod_name = do
     checkExternalInterpreter hsc_env
-    fst <$> loadPlugin' (mkVarOcc "frontendPlugin") frontendPluginTyConName
-                hsc_env Nothing mod_name
+    (plugin, _iface, links, pkgs)
+      <- loadPlugin' (mkVarOcc "frontendPlugin") frontendPluginTyConName
+           hsc_env mod_name
+    return (plugin, links, pkgs)
 
 -- #14335
 checkExternalInterpreter :: HscEnv -> IO ()
@@ -121,8 +127,8 @@ checkExternalInterpreter hsc_env = case interpInstance <$> hsc_interp hsc_env of
     -> throwIO (InstallationError "Plugins require -fno-external-interpreter")
   _ -> pure ()
 
-loadPlugin' :: OccName -> Name -> HscEnv -> Maybe ModuleNameWithIsBoot -> ModuleName -> IO (a, ModIface)
-loadPlugin' occ_name plugin_name hsc_env mnwib mod_name
+loadPlugin' :: OccName -> Name -> HscEnv -> ModuleName -> IO (a, ModIface, [Linkable], PkgsLoaded)
+loadPlugin' occ_name plugin_name hsc_env mod_name
   = do { let plugin_rdr_name = mkRdrQual mod_name occ_name
              dflags = hsc_dflags hsc_env
        ; mb_name <- lookupRdrNameInModuleForPlugins hsc_env mod_name
@@ -136,7 +142,7 @@ loadPlugin' occ_name plugin_name hsc_env mnwib mod_name
             Just (name, mod_iface) ->
 
      do { plugin_tycon <- forceLoadTyCon hsc_env plugin_name
-        ; eith_plugin <- getValueSafely hsc_env mnwib name (mkTyConTy plugin_tycon)
+        ; eith_plugin <- getValueSafely hsc_env name (mkTyConTy plugin_tycon)
         ; case eith_plugin of
             Left actual_type ->
                 throwGhcExceptionIO (CmdLineError $
@@ -147,7 +153,7 @@ loadPlugin' occ_name plugin_name hsc_env mnwib mod_name
                           , text "did not have the type"
                           , text "GHC.Plugins.Plugin"
                           , text "as required"])
-            Right plugin -> return (plugin, mod_iface) } } }
+            Right (plugin, links, pkgs) -> return (plugin, mod_iface, links, pkgs) } } }
 
 
 -- | Force the interfaces for the given modules to be loaded. The 'SDoc' parameter is used
@@ -192,23 +198,23 @@ forceLoadTyCon hsc_env con_name = do
 -- * If the Name does not exist in the module
 -- * If the link failed
 
-getValueSafely :: HscEnv -> Maybe ModuleNameWithIsBoot -> Name -> Type -> IO (Either Type a)
-getValueSafely hsc_env mnwib val_name expected_type = do
+getValueSafely :: HscEnv -> Name -> Type -> IO (Either Type (a, [Linkable], PkgsLoaded))
+getValueSafely hsc_env val_name expected_type = do
   eith_hval <- case getValueSafelyHook hooks of
-    Nothing -> getHValueSafely interp hsc_env mnwib val_name expected_type
-    Just h  -> h                      hsc_env mnwib val_name expected_type
+    Nothing -> getHValueSafely interp hsc_env val_name expected_type
+    Just h  -> h                      hsc_env val_name expected_type
   case eith_hval of
     Left actual_type -> return (Left actual_type)
-    Right hval -> do
+    Right (hval, links, pkgs) -> do
       value <- lessUnsafeCoerce logger "getValueSafely" hval
-      return (Right value)
+      return (Right (value, links, pkgs))
   where
     interp = hscInterp hsc_env
     logger = hsc_logger hsc_env
     hooks  = hsc_hooks hsc_env
 
-getHValueSafely :: Interp -> HscEnv -> Maybe ModuleNameWithIsBoot -> Name -> Type -> IO (Either Type HValue)
-getHValueSafely interp hsc_env mnwib val_name expected_type = do
+getHValueSafely :: Interp -> HscEnv -> Name -> Type -> IO (Either Type (HValue, [Linkable], PkgsLoaded))
+getHValueSafely interp hsc_env val_name expected_type = do
     forceLoadNameModuleInterface hsc_env (text "contains a name used in an invocation of getHValueSafely") val_name
     -- Now look up the names for the value and type constructor in the type environment
     mb_val_thing <- lookupType hsc_env val_name
@@ -221,13 +227,14 @@ getHValueSafely interp hsc_env mnwib val_name expected_type = do
              then do
                 -- Link in the module that contains the value, if it has such a module
                 case nameModule_maybe val_name of
-                    Just mod -> do loadModule interp hsc_env mnwib mod
+                    Just mod -> do loadModule interp hsc_env mod
                                    return ()
                     Nothing ->  return ()
                 -- Find the value that we just linked in and cast it given that we have proved it's type
                 hval <- do
-                  v <- loadName interp hsc_env mnwib val_name
-                  wormhole interp v
+                  (v, links, pkgs) <- loadName interp hsc_env val_name
+                  hv <- wormhole interp v
+                  return (hv, links, pkgs)
                 return (Right hval)
              else return (Left (idType id))
         Just val_thing -> throwCmdLineErrorS dflags $ wrongTyThingError val_name val_thing
diff --git a/compiler/GHC/Tc/Gen/Splice.hs b/compiler/GHC/Tc/Gen/Splice.hs
index 7264f2232a..f2efb93f2d 100644
--- a/compiler/GHC/Tc/Gen/Splice.hs
+++ b/compiler/GHC/Tc/Gen/Splice.hs
@@ -1011,13 +1011,12 @@ runMeta' show_code ppr_hs run_and_convert expr
 
         -- Compile and link it; might fail if linking fails
         ; src_span <- getSrcSpanM
-        ; mnwib <- getMnwib
         ; traceTc "About to run (desugared)" (ppr ds_expr)
         ; either_hval <- tryM $ liftIO $
-                         GHC.Driver.Main.hscCompileCoreExpr hsc_env (src_span, Just mnwib) ds_expr
+                         GHC.Driver.Main.hscCompileCoreExpr hsc_env src_span ds_expr
         ; case either_hval of {
             Left exn   -> fail_with_exn "compile and link" exn ;
-            Right hval -> do
+            Right (hval, needed_mods, needed_pkgs) -> do
 
         {       -- Coerce it to Q t, and run it
 
@@ -1031,6 +1030,7 @@ runMeta' show_code ppr_hs run_and_convert expr
                 --
                 -- See Note [Exceptions in TH]
           let expr_span = getLocA expr
+        ; recordThNeededRuntimeDeps needed_mods needed_pkgs
         ; either_tval <- tryAllM $
                          setSrcSpan expr_span $ -- Set the span so that qLocation can
                                                 -- see where this splice is
diff --git a/compiler/GHC/Tc/Types.hs b/compiler/GHC/Tc/Types.hs
index e1f0400e44..b49bc718cd 100644
--- a/compiler/GHC/Tc/Types.hs
+++ b/compiler/GHC/Tc/Types.hs
@@ -175,6 +175,7 @@ import GHCi.RemoteTypes
 
 import qualified Language.Haskell.TH as TH
 import GHC.Driver.Env.KnotVars
+import GHC.Linker.Types
 
 -- | A 'NameShape' is a substitution on 'Name's that can be used
 -- to refine the identities of a hole while we are renaming interfaces
@@ -521,6 +522,10 @@ data TcGblEnv
           --
           -- Splices disable recompilation avoidance (see #481)
 
+        tcg_th_needed_deps :: TcRef ([Linkable], PkgsLoaded),
+          -- ^ The set of runtime dependencies required by this module
+          -- See Note [Object File Dependencies]
+
         tcg_dfun_n  :: TcRef OccSet,
           -- ^ Allows us to choose unique DFun names.
 
diff --git a/compiler/GHC/Tc/Utils/Monad.hs b/compiler/GHC/Tc/Utils/Monad.hs
index ca2915e8fa..72670e6b06 100644
--- a/compiler/GHC/Tc/Utils/Monad.hs
+++ b/compiler/GHC/Tc/Utils/Monad.hs
@@ -58,7 +58,7 @@ module GHC.Tc.Utils.Monad(
   getRdrEnvs, getImports,
   getFixityEnv, extendFixityEnv, getRecFieldEnv,
   getDeclaredDefaultTys,
-  addDependentFiles, getMnwib,
+  addDependentFiles,
 
   -- * Error management
   getSrcSpanM, setSrcSpan, setSrcSpanA, addLocM, addLocMA, inGeneratedCode,
@@ -116,7 +116,7 @@ module GHC.Tc.Utils.Monad(
   emitNamedTypeHole, IsExtraConstraint(..), emitAnonTypeHole,
 
   -- * Template Haskell context
-  recordThUse, recordThSpliceUse,
+  recordThUse, recordThSpliceUse, recordThNeededRuntimeDeps,
   keepAlive, getStage, getStageAndBindLevel, setStage,
   addModFinalizersWithLclEnv,
 
@@ -222,6 +222,8 @@ import {-# SOURCE #-} GHC.Tc.Utils.Env    ( tcInitTidyEnv )
 
 import qualified Data.Map as Map
 import GHC.Driver.Env.KnotVars
+import GHC.Linker.Types
+import GHC.Types.Unique.DFM
 
 {-
 ************************************************************************
@@ -263,6 +265,7 @@ initTc hsc_env hsc_src keep_rn_syntax mod loc do_this
         th_state_var         <- newIORef Map.empty ;
         th_remote_state_var  <- newIORef Nothing ;
         th_docs_var          <- newIORef Map.empty ;
+        th_needed_deps_var   <- newIORef ([], emptyUDFM) ;
         next_wrapper_num     <- newIORef emptyModuleEnv ;
         let {
              -- bangs to avoid leaking the env (#19356)
@@ -311,6 +314,7 @@ initTc hsc_env hsc_src keep_rn_syntax mod loc do_this
                 tcg_ann_env        = emptyAnnEnv,
                 tcg_th_used        = th_var,
                 tcg_th_splice_used = th_splice_var,
+                tcg_th_needed_deps = th_needed_deps_var,
                 tcg_exports        = [],
                 tcg_imports        = emptyImportAvails,
                 tcg_used_gres     = used_gre_var,
@@ -963,11 +967,6 @@ getSrcSpanM :: TcRn SrcSpan
         -- Avoid clash with Name.getSrcLoc
 getSrcSpanM = do { env <- getLclEnv; return (RealSrcSpan (tcl_loc env) Strict.Nothing) }
 
-getMnwib :: TcRn ModuleNameWithIsBoot
-getMnwib = do
-  gbl_env <- getGblEnv
-  return $ GWIB (moduleName $ tcg_mod gbl_env) (hscSourceToIsBoot (tcg_src gbl_env))
-
 -- See Note [Error contexts in generated code]
 inGeneratedCode :: TcRn Bool
 inGeneratedCode = tcl_in_gen_code <$> getLclEnv
@@ -2010,6 +2009,15 @@ recordThUse = do { env <- getGblEnv; writeTcRef (tcg_th_used env) True }
 recordThSpliceUse :: TcM ()
 recordThSpliceUse = do { env <- getGblEnv; writeTcRef (tcg_th_splice_used env) True }
 
+recordThNeededRuntimeDeps :: [Linkable] -> PkgsLoaded -> TcM ()
+recordThNeededRuntimeDeps new_links new_pkgs
+  = do { env <- getGblEnv
+       ; updTcRef (tcg_th_needed_deps env) $ \(needed_links, needed_pkgs) ->
+           let links = new_links ++ needed_links
+               !pkgs = plusUDFM needed_pkgs new_pkgs
+               in (links, pkgs)
+       }
+
 keepAlive :: Name -> TcRn ()     -- Record the name in the keep-alive set
 keepAlive name
   = do { env <- getGblEnv
diff --git a/compiler/GHC/Types/Basic.hs b/compiler/GHC/Types/Basic.hs
index 2ba185c25e..ccb660e130 100644
--- a/compiler/GHC/Types/Basic.hs
+++ b/compiler/GHC/Types/Basic.hs
@@ -1211,6 +1211,12 @@ instance Outputable (DefMethSpec ty) where
 
 data SuccessFlag = Succeeded | Failed
 
+instance Semigroup SuccessFlag where
+  Failed <> _ = Failed
+  _ <> Failed = Failed
+  _ <> _      = Succeeded
+
+
 instance Outputable SuccessFlag where
     ppr Succeeded = text "Succeeded"
     ppr Failed    = text "Failed"
diff --git a/compiler/GHC/Types/Unique/DFM.hs b/compiler/GHC/Types/Unique/DFM.hs
index 4b0f5e545d..c8e63d333a 100644
--- a/compiler/GHC/Types/Unique/DFM.hs
+++ b/compiler/GHC/Types/Unique/DFM.hs
@@ -57,6 +57,7 @@ module GHC.Types.Unique.DFM (
         listToUDFM, listToUDFM_Directly,
         udfmMinusUFM, ufmMinusUDFM,
         partitionUDFM,
+        udfmRestrictKeys,
         anyUDFM, allUDFM,
         pprUniqDFM, pprUDFM,
 
@@ -310,6 +311,9 @@ filterUDFM_Directly p (UDFM m i) = UDFM (M.filterWithKey p' m) i
   where
   p' k (TaggedVal v _) = p (getUnique k) v
 
+udfmRestrictKeys :: UniqDFM key elt -> UniqDFM key elt2 -> UniqDFM key elt
+udfmRestrictKeys (UDFM a i) (UDFM b _) = UDFM (M.restrictKeys a (M.keysSet b)) i
+
 -- | Converts `UniqDFM` to a list, with elements in deterministic order.
 -- It's O(n log n) while the corresponding function on `UniqFM` is O(n).
 udfmToList :: UniqDFM key elt -> [(Unique, elt)]
diff --git a/compiler/GHC/Unit/Module/Deps.hs b/compiler/GHC/Unit/Module/Deps.hs
index 0bab72763b..0da8a06979 100644
--- a/compiler/GHC/Unit/Module/Deps.hs
+++ b/compiler/GHC/Unit/Module/Deps.hs
@@ -52,10 +52,13 @@ import Data.Bifunctor
 data Dependencies = Deps
    { dep_direct_mods :: Set (UnitId, ModuleNameWithIsBoot)
       -- ^ All home-package modules which are directly imported by this one.
+      -- This may include modules from other units when using multiple home units
 
    , dep_direct_pkgs :: Set UnitId
       -- ^ All packages directly imported by this module
       -- I.e. packages to which this module's direct imports belong.
+      -- Does not include other home units when using multiple home units.
+      -- Modules from these units will go in `dep_direct_mods`
 
    , dep_plugin_pkgs :: Set UnitId
       -- ^ All units needed for plugins
diff --git a/compiler/GHC/Unit/Module/Env.hs b/compiler/GHC/Unit/Module/Env.hs
index a69c865aef..0c8016e17e 100644
--- a/compiler/GHC/Unit/Module/Env.hs
+++ b/compiler/GHC/Unit/Module/Env.hs
@@ -7,6 +7,7 @@ module GHC.Unit.Module.Env
    , extendModuleEnvList_C, plusModuleEnv_C
    , delModuleEnvList, delModuleEnv, plusModuleEnv, lookupModuleEnv
    , lookupWithDefaultModuleEnv, mapModuleEnv, mkModuleEnv, emptyModuleEnv
+   , partitionModuleEnv
    , moduleEnvKeys, moduleEnvElts, moduleEnvToList
    , unitModuleEnv, isEmptyModuleEnv
    , extendModuleEnvWith, filterModuleEnv
@@ -19,7 +20,8 @@ module GHC.Unit.Module.Env
    , emptyModuleSet, mkModuleSet, moduleSetElts
    , extendModuleSet, extendModuleSetList, delModuleSet
    , elemModuleSet, intersectModuleSet, minusModuleSet, unionModuleSet
-   , unitModuleSet
+   , unitModuleSet, isEmptyModuleSet
+   , unionManyModuleSets
 
      -- * InstalledModuleEnv
    , InstalledModuleEnv
@@ -56,6 +58,9 @@ import GHC.Utils.Outputable
 -- | A map keyed off of 'Module's
 newtype ModuleEnv elt = ModuleEnv (Map NDModule elt)
 
+instance Outputable a => Outputable (ModuleEnv a) where
+  ppr (ModuleEnv m) = ppr m
+
 {-
 Note [ModuleEnv performance and determinism]
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
@@ -76,6 +81,9 @@ newtype NDModule = NDModule { unNDModule :: Module }
   deriving Eq
   -- A wrapper for Module with faster nondeterministic Ord.
   -- Don't export, See [ModuleEnv performance and determinism]
+  --
+instance Outputable NDModule where
+  ppr (NDModule a) = ppr a
 
 instance Ord NDModule where
   compare (NDModule (Module p1 n1)) (NDModule (Module p2 n2)) =
@@ -130,6 +138,11 @@ lookupWithDefaultModuleEnv (ModuleEnv e) x m =
 mapModuleEnv :: (a -> b) -> ModuleEnv a -> ModuleEnv b
 mapModuleEnv f (ModuleEnv e) = ModuleEnv (Map.mapWithKey (\_ v -> f v) e)
 
+partitionModuleEnv :: (a -> Bool) -> ModuleEnv a -> (ModuleEnv a, ModuleEnv a)
+partitionModuleEnv f (ModuleEnv e) = (ModuleEnv a, ModuleEnv b)
+  where
+    (a,b) = Map.partition f e
+
 mkModuleEnv :: [(Module, a)] -> ModuleEnv a
 mkModuleEnv xs = ModuleEnv (Map.fromList [(NDModule k, v) | (k,v) <- xs])
 
@@ -170,6 +183,9 @@ extendModuleSetList s ms = foldl' (coerce . flip Set.insert) s ms
 emptyModuleSet :: ModuleSet
 emptyModuleSet = Set.empty
 
+isEmptyModuleSet :: ModuleSet -> Bool
+isEmptyModuleSet = Set.null
+
 moduleSetElts :: ModuleSet -> [Module]
 moduleSetElts = sort . coerce . Set.toList
 
@@ -188,6 +204,9 @@ delModuleSet = coerce (flip Set.delete)
 unionModuleSet :: ModuleSet -> ModuleSet -> ModuleSet
 unionModuleSet = coerce Set.union
 
+unionManyModuleSets :: [ModuleSet] -> ModuleSet
+unionManyModuleSets = coerce (Set.unions :: [Set NDModule] -> Set NDModule)
+
 unitModuleSet :: Module -> ModuleSet
 unitModuleSet = coerce Set.singleton
 
diff --git a/docs/users_guide/separate_compilation.rst b/docs/users_guide/separate_compilation.rst
index ec33cddcd4..c43dcc1f2c 100644
--- a/docs/users_guide/separate_compilation.rst
+++ b/docs/users_guide/separate_compilation.rst
@@ -705,6 +705,24 @@ beautiful sight!
 
 You can read about :ghc-wiki:`how all this works <commentary/compiler/recompilation-avoidance>` in the GHC commentary.
 
+Recompilation for Template Haskell and Plugins
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Recompilation checking gets a bit more complicated when using Template Haskell or
+plugins. Both these features execute code at compile time and so if any of the
+executed code changes then it's necessary to recompile the module. Consider the
+top-level splice::
+
+  main = $(foo bar [| () |])
+
+When the module is compiled ``foo bar [| () |]`` will be evaluated and the resulting
+code placed into the program. The dependencies of the expression are calculated
+and stored during module compilation. When the interface file is written, additional
+dependencies are created on the object file dependencies of the expression. For instance,
+if ``foo`` is from module ``A`` and ``bar`` is from module ``B``, the module will
+now depend on ``A.o`` and ``B.o``, if either of these change then the module will
+be recompiled.
+
 .. _mutual-recursion:
 
 How to compile mutually recursive modules
diff --git a/ghc/Main.hs b/ghc/Main.hs
index cb701e24e2..3cb71b77e8 100644
--- a/ghc/Main.hs
+++ b/ghc/Main.hs
@@ -1056,7 +1056,7 @@ dumpUnitsSimple hsc_env = putMsg (hsc_logger hsc_env) (pprUnitsSimple (hsc_units
 doFrontend :: ModuleName -> [(String, Maybe Phase)] -> Ghc ()
 doFrontend modname srcs = do
     hsc_env <- getSession
-    frontend_plugin <- liftIO $ loadFrontendPlugin hsc_env modname
+    (frontend_plugin, _pkgs, _deps) <- liftIO $ loadFrontendPlugin hsc_env modname -- TODO do these need to recorded?
     frontend frontend_plugin
       (reverse $ frontendPluginOpts (hsc_dflags hsc_env)) srcs
 
diff --git a/testsuite/tests/driver/T20604/A.hs b/testsuite/tests/driver/T20604/A.hs
new file mode 100644
index 0000000000..60c4445820
--- /dev/null
+++ b/testsuite/tests/driver/T20604/A.hs
@@ -0,0 +1,4 @@
+{-# LANGUAGE TemplateHaskell #-}
+module A where
+
+x = $([| True |])
diff --git a/testsuite/tests/driver/T20604/A1.hs b/testsuite/tests/driver/T20604/A1.hs
new file mode 100644
index 0000000000..24009b444c
--- /dev/null
+++ b/testsuite/tests/driver/T20604/A1.hs
@@ -0,0 +1,3 @@
+module A1 where
+
+import A
diff --git a/testsuite/tests/driver/T20604/Makefile b/testsuite/tests/driver/T20604/Makefile
new file mode 100644
index 0000000000..53c3446611
--- /dev/null
+++ b/testsuite/tests/driver/T20604/Makefile
@@ -0,0 +1,16 @@
+TOP=../../..
+include $(TOP)/mk/boilerplate.mk
+include $(TOP)/mk/test.mk
+
+clean:
+	rm -f *.o
+	rm -f *.hi
+	rm -f *.dyn_o
+	rm -f *.dyn_hi
+
+T20604: clean
+	'$(TEST_HC)' $(TEST_HC_OPTS) A1 -v0
+	echo "A1"
+	'$(TEST_HC)' $(TEST_HC_OPTS) --show-iface A1.hi | grep addDependentFile || :
+	echo "A"
+	'$(TEST_HC)' $(TEST_HC_OPTS) --show-iface A.hi | grep addDependentFile || :
diff --git a/testsuite/tests/driver/T20604/T20604.stdout b/testsuite/tests/driver/T20604/T20604.stdout
new file mode 100644
index 0000000000..864f215cb3
--- /dev/null
+++ b/testsuite/tests/driver/T20604/T20604.stdout
@@ -0,0 +1,11 @@
+A1
+A
+addDependentFile "/home/matt/ghc-numa/_build/stage1/lib/../lib/x86_64-linux-ghc-9.3.20220210/libHSghc-prim-0.8.0-ghc9.3.20220210.so" 9f60cabb62a3305daa26440cde34be2b
+addDependentFile "/home/matt/ghc-numa/_build/stage1/lib/../lib/x86_64-linux-ghc-9.3.20220210/libHSghc-bignum-1.3-ghc9.3.20220210.so" 5da53b9a870ae800132527a10de182ef
+addDependentFile "/home/matt/ghc-numa/_build/stage1/lib/../lib/x86_64-linux-ghc-9.3.20220210/libHSbase-4.16.0.0-ghc9.3.20220210.so" ed1808d3e2f7368d81345094adfea50f
+addDependentFile "/home/matt/ghc-numa/_build/stage1/lib/../lib/x86_64-linux-ghc-9.3.20220210/libHSfilepath-1.4.2.1-ghc9.3.20220210.so" 08b9514f12122be71c467bddf9edf99b
+addDependentFile "/home/matt/ghc-numa/_build/stage1/lib/../lib/x86_64-linux-ghc-9.3.20220210/libHSghc-boot-th-9.3-ghc9.3.20220210.so" 165417fb87110cd768173641e96854d7
+addDependentFile "/home/matt/ghc-numa/_build/stage1/lib/../lib/x86_64-linux-ghc-9.3.20220210/libHSarray-0.5.4.0-ghc9.3.20220210.so" 267bb3b9d1d59920b08f6d81ddb1f5f4
+addDependentFile "/home/matt/ghc-numa/_build/stage1/lib/../lib/x86_64-linux-ghc-9.3.20220210/libHSdeepseq-1.4.7.0-ghc9.3.20220210.so" 4d4f1682b257ae7674e1dc6b84f1f8ae
+addDependentFile "/home/matt/ghc-numa/_build/stage1/lib/../lib/x86_64-linux-ghc-9.3.20220210/libHSpretty-1.1.3.6-ghc9.3.20220210.so" dd0fddaebe5d06357fe1748efefd1705
+addDependentFile "/home/matt/ghc-numa/_build/stage1/lib/../lib/x86_64-linux-ghc-9.3.20220210/libHStemplate-haskell-2.18.0.0-ghc9.3.20220210.so" 72cdf17fd485c6bb49e684730a0a55b6
diff --git a/testsuite/tests/driver/T20604/all.T b/testsuite/tests/driver/T20604/all.T
new file mode 100644
index 0000000000..290da3ec53
--- /dev/null
+++ b/testsuite/tests/driver/T20604/all.T
@@ -0,0 +1,13 @@
+def normalise_paths(s):
+  res = []
+  for line in s.splitlines():
+    lib_name = re.search(r'(HS[a-z-]+)-', line)
+    if lib_name:
+      res.append(lib_name.group(0))
+    else:
+      res.append(line)
+  return '\n'.join(res)
+
+
+test('T20604', [extra_files(['A.hs', 'A1.hs'])
+               , normalise_fun(normalise_paths)], makefile_test, [])