never executed always true always false
    1 {-# LANGUAGE GADTs #-}
    2 
    3 module GHC.Driver.GenerateCgIPEStub (generateCgIPEStub) where
    4 
    5 import qualified Data.Map.Strict as Map
    6 import Data.Maybe (catMaybes, listToMaybe)
    7 import GHC.Cmm
    8 import GHC.Cmm.CLabel (CLabel)
    9 import GHC.Cmm.Dataflow (Block, C, O)
   10 import GHC.Cmm.Dataflow.Block (blockSplit, blockToList)
   11 import GHC.Cmm.Dataflow.Collections (mapToList)
   12 import GHC.Cmm.Dataflow.Label (Label)
   13 import GHC.Cmm.Info.Build (emptySRT)
   14 import GHC.Cmm.Pipeline (cmmPipeline)
   15 import GHC.Cmm.Utils (toBlockList)
   16 import GHC.Data.Maybe (firstJusts)
   17 import GHC.Data.Stream (Stream, liftIO)
   18 import qualified GHC.Data.Stream as Stream
   19 import GHC.Driver.Env (hsc_dflags)
   20 import GHC.Driver.Flags (GeneralFlag (Opt_InfoTableMap))
   21 import GHC.Driver.Session (gopt, targetPlatform)
   22 import GHC.Plugins (HscEnv, NonCaffySet)
   23 import GHC.Prelude
   24 import GHC.Runtime.Heap.Layout (isStackRep)
   25 import GHC.Settings (Platform, platformUnregisterised)
   26 import GHC.StgToCmm.Monad (getCmm, initC, runC)
   27 import GHC.StgToCmm.Prof (initInfoTableProv)
   28 import GHC.StgToCmm.Types (CgInfos (..), ModuleLFInfos)
   29 import GHC.Types.IPE (InfoTableProvMap (provInfoTables), IpeSourceLocation)
   30 import GHC.Types.Tickish (GenTickish (SourceNote))
   31 import GHC.Unit.Types (Module)
   32 
   33 {-
   34 Note [Stacktraces from Info Table Provenance Entries (IPE based stack unwinding)]
   35 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   36 
   37 Stacktraces can be created from return frames as they are pushed to stack for every case scrutinee.
   38 But to make them readable / meaningful, one needs to know the source location of each return frame.
   39 
   40 Every return frame has a distinct info table and thus a distinct code pointer (for tables next to
   41 code) or at least a distict address itself. Info Table Provernance Entries (IPE) are searchable by
   42 this pointer and contain a source location.
   43 
   44 The info table / info table code pointer to source location map is described in:
   45 Note [Mapping Info Tables to Source Positions]
   46 
   47 To be able to lookup IPEs for return frames one needs to emit them during compile time. This is done
   48 by `generateCgIPEStub`.
   49 
   50 This leads to the question: How to figure out the source location of a return frame?
   51 
   52 While the lookup algorithms for registerised and unregisterised builds differ in details, they have in
   53 common that we want to lookup the `CmmNode.CmmTick` (containing a `SourceNote`) that is nearest
   54 (before) the usage of the return frame's label. (Which label and label type is used differs between
   55 these two use cases.)
   56 
   57 Registerised
   58 ~~~~~~~~~~~~~
   59 
   60 Let's consider this example:
   61 ```
   62  Main.returnFrame_entry() { //  [R2]
   63          { info_tbls: [(c18g,
   64                         label: block_c18g_info
   65                         rep: StackRep []
   66                         srt: Just GHC.CString.unpackCString#_closure),
   67                        (c18r,
   68                         label: Main.returnFrame_info
   69                         rep: HeapRep static { Fun {arity: 1 fun_type: ArgSpec 5} }
   70                         srt: Nothing)]
   71            stack_info: arg_space: 8
   72          }
   73      {offset
   74 
   75       [...]
   76 
   77        c18u: // global
   78            //tick src<Main.hs:(7,1)-(16,15)>
   79            I64[Hp - 16] = sat_s16B_info;
   80            P64[Hp] = _s16r::P64;
   81            _c17j::P64 = Hp - 16;
   82            //tick src<Main.hs:8:25-39>
   83            I64[Sp - 8] = c18g;
   84            R3 = _c17j::P64;
   85            R2 = GHC.IO.Unsafe.unsafePerformIO_closure;
   86            R1 = GHC.Base.$_closure;
   87            Sp = Sp - 8;
   88            call stg_ap_pp_fast(R3,
   89                                R2,
   90                                R1) returns to c18g, args: 8, res: 8, upd: 8;
   91 ```
   92 
   93 The return frame `block_c18g_info` has the label `c18g` which is used in the call to `stg_ap_pp_fast`
   94 (`returns to c18g`) as continuation (`cml_cont`). The source location we're after, is the nearest
   95 `//tick` before the call (`//tick src<Main.hs:8:25-39>`).
   96 
   97 In code the Cmm program is represented as a Hoopl graph. Hoopl distinguishes nodes by defining if they
   98 are open or closed on entry (one can fallthrough to them from the previous instruction) and if they are
   99 open or closed on exit (one can fallthrough from them to the next node).
  100 
  101 Please refer to the paper "Hoopl: A Modular, Reusable Library for Dataflow Analysis and Transformation"
  102 for a detailed explanation.
  103 
  104 Here we use the fact, that calls (represented by `CmmNode.CmmCall`) are always closed on exit
  105 (`CmmNode O C`, `O` means open, `C` closed). In other words, they are always at the end of a block.
  106 
  107 So, given a stack represented info table (likely representing a return frame, but this isn't completely
  108 sure as there are e.g. update frames, too) with it's label (`c18g` in the example above) and a `CmmGraph`:
  109   - Look at the end of every block, if it's a `CmmNode.CmmCall` returning to the continuation with the
  110     label of the return frame.
  111   - If there's such a call, lookup the nearest `CmmNode.CmmTick` by traversing the middle part of the block
  112     backwards (from end to beginning).
  113   - Take the first `CmmNode.CmmTick` that contains a `Tickish.SourceNote` and return it's payload as
  114     `IpeSourceLocation`. (There are other `Tickish` constructors like `ProfNote` or `HpcTick`, these are
  115     ignored.)
  116 
  117 Unregisterised
  118 ~~~~~~~~~~~~~
  119 
  120 In unregisterised builds there is no return frame / continuation label in calls. The continuation (i.e. return
  121 frame) is set in an explicit Cmm assignment. Thus the tick lookup algorithm has to be slightly different.
  122 
  123 ```
  124  sat_s16G_entry() { //  [R1]
  125          { info_tbls: [(c18O,
  126                         label: sat_s16G_info
  127                         rep: HeapRep { Thunk }
  128                         srt: Just _u18Z_srt)]
  129            stack_info: arg_space: 0
  130          }
  131      {offset
  132        c18O: // global
  133            _s16G::P64 = R1;
  134            if ((Sp + 8) - 40 < SpLim) (likely: False) goto c18P; else goto c18Q;
  135        c18P: // global
  136            R1 = _s16G::P64;
  137            call (stg_gc_enter_1)(R1) args: 8, res: 0, upd: 8;
  138        c18Q: // global
  139            I64[Sp - 16] = stg_upd_frame_info;
  140            P64[Sp - 8] = _s16G::P64;
  141            //tick src<Main.hs:20:9-13>
  142            I64[Sp - 24] = block_c18M_info;
  143            R1 = GHC.Show.$fShow[]_closure;
  144            P64[Sp - 32] = GHC.Show.$fShowChar_closure;
  145            Sp = Sp - 32;
  146            call stg_ap_p_fast(R1) args: 16, res: 8, upd: 24;
  147      }
  148  },
  149  _blk_c18M() { //  [R1]
  150          { info_tbls: [(c18M,
  151                         label: block_c18M_info
  152                         rep: StackRep []
  153                         srt: Just System.IO.print_closure)]
  154            stack_info: arg_space: 0
  155          }
  156      {offset
  157        c18M: // global
  158            _s16F::P64 = R1;
  159            R1 = System.IO.print_closure;
  160            P64[Sp] = _s16F::P64;
  161            call stg_ap_p_fast(R1) args: 32, res: 0, upd: 24;
  162      }
  163  },
  164 ```
  165 
  166 In this example we have to lookup `//tick src<Main.hs:20:9-13>` for the return frame `c18M`.
  167 Notice, that this cannot be done with the `Label` `c18M`, but with the `CLabel` `block_c18M_info`
  168 (`label: block_c18M_info` is actually a `CLabel`).
  169 
  170 The find the tick:
  171   - Every `Block` is checked from top (first) to bottom (last) node for an assignment like
  172    `I64[Sp - 24] = block_c18M_info;`. The lefthand side is actually ignored.
  173   - If such an assignment is found the search is over, because the payload (content of
  174     `Tickish.SourceNote`, represented as `IpeSourceLocation`) of last visited tick is always
  175     remembered in a `Maybe`.
  176 -}
  177 
  178 generateCgIPEStub :: HscEnv -> Module -> InfoTableProvMap -> Stream IO CmmGroupSRTs (NonCaffySet, ModuleLFInfos) -> Stream IO CmmGroupSRTs CgInfos
  179 generateCgIPEStub hsc_env this_mod denv s = do
  180   let dflags = hsc_dflags hsc_env
  181       platform = targetPlatform dflags
  182   cgState <- liftIO initC
  183 
  184   -- Collect info tables, but only if -finfo-table-map is enabled, otherwise labeledInfoTablesWithTickishes is empty.
  185   let collectFun = if gopt Opt_InfoTableMap dflags then collect platform else collectNothing
  186   (labeledInfoTablesWithTickishes, (nonCaffySet, moduleLFInfos)) <- Stream.mapAccumL_ collectFun [] s
  187 
  188   -- Yield Cmm for Info Table Provenance Entries (IPEs)
  189   let denv' = denv {provInfoTables = Map.fromList (map (\(_, i, t) -> (cit_lbl i, t)) labeledInfoTablesWithTickishes)}
  190       ((ipeStub, ipeCmmGroup), _) = runC dflags this_mod cgState $ getCmm (initInfoTableProv (map sndOfTriple labeledInfoTablesWithTickishes) denv' this_mod)
  191 
  192   (_, ipeCmmGroupSRTs) <- liftIO $ cmmPipeline hsc_env (emptySRT this_mod) ipeCmmGroup
  193   Stream.yield ipeCmmGroupSRTs
  194 
  195   return CgInfos {cgNonCafs = nonCaffySet, cgLFInfos = moduleLFInfos, cgIPEStub = ipeStub}
  196   where
  197     collect :: Platform -> [(Label, CmmInfoTable, Maybe IpeSourceLocation)] -> CmmGroupSRTs -> IO ([(Label, CmmInfoTable, Maybe IpeSourceLocation)], CmmGroupSRTs)
  198     collect platform acc cmmGroupSRTs = do
  199       let labelsToInfoTables = collectInfoTables cmmGroupSRTs
  200           labelsToInfoTablesToTickishes = map (\(l, i) -> (l, i, lookupEstimatedTick platform cmmGroupSRTs l i)) labelsToInfoTables
  201       return (acc ++ labelsToInfoTablesToTickishes, cmmGroupSRTs)
  202 
  203     collectNothing :: [a] -> CmmGroupSRTs -> IO ([a], CmmGroupSRTs)
  204     collectNothing _ cmmGroupSRTs = pure ([], cmmGroupSRTs)
  205 
  206     sndOfTriple :: (a, b, c) -> b
  207     sndOfTriple (_, b, _) = b
  208 
  209     collectInfoTables :: CmmGroupSRTs -> [(Label, CmmInfoTable)]
  210     collectInfoTables cmmGroup = concat $ catMaybes $ map extractInfoTables cmmGroup
  211 
  212     extractInfoTables :: GenCmmDecl RawCmmStatics CmmTopInfo CmmGraph -> Maybe [(Label, CmmInfoTable)]
  213     extractInfoTables (CmmProc h _ _ _) = Just $ mapToList (info_tbls h)
  214     extractInfoTables _ = Nothing
  215 
  216     lookupEstimatedTick :: Platform -> CmmGroupSRTs -> Label -> CmmInfoTable -> Maybe IpeSourceLocation
  217     lookupEstimatedTick platform cmmGroup infoTableLabel infoTable = do
  218       -- All return frame info tables are stack represented, though not all stack represented info
  219       -- tables have to be return frames.
  220       if (isStackRep . cit_rep) infoTable
  221         then do
  222           let findFun =
  223                 if platformUnregisterised platform
  224                   then findCmmTickishForForUnregistered (cit_lbl infoTable)
  225                   else findCmmTickishForRegistered infoTableLabel
  226               blocks = concatMap toBlockList (graphs cmmGroup)
  227           firstJusts $ map findFun blocks
  228         else Nothing
  229     graphs :: CmmGroupSRTs -> [CmmGraph]
  230     graphs = foldl' go []
  231       where
  232         go :: [CmmGraph] -> GenCmmDecl d h CmmGraph -> [CmmGraph]
  233         go acc (CmmProc _ _ _ g) = g : acc
  234         go acc _ = acc
  235 
  236     findCmmTickishForRegistered :: Label -> Block CmmNode C C -> Maybe IpeSourceLocation
  237     findCmmTickishForRegistered label block = do
  238       let (_, middleBlock, endBlock) = blockSplit block
  239 
  240       isCallWithReturnFrameLabel endBlock label
  241       lastTickInBlock middleBlock
  242       where
  243         isCallWithReturnFrameLabel :: CmmNode O C -> Label -> Maybe ()
  244         isCallWithReturnFrameLabel (CmmCall _ (Just l) _ _ _ _) clabel | l == clabel = Just ()
  245         isCallWithReturnFrameLabel _ _ = Nothing
  246 
  247         lastTickInBlock block =
  248           listToMaybe $
  249             catMaybes $
  250               map maybeTick $ (reverse . blockToList) block
  251 
  252         maybeTick :: CmmNode O O -> Maybe IpeSourceLocation
  253         maybeTick (CmmTick (SourceNote span name)) = Just (span, name)
  254         maybeTick _ = Nothing
  255 
  256     findCmmTickishForForUnregistered :: CLabel -> Block CmmNode C C -> Maybe IpeSourceLocation
  257     findCmmTickishForForUnregistered cLabel block = do
  258       let (_, middleBlock, _) = blockSplit block
  259       find cLabel (blockToList middleBlock) Nothing
  260       where
  261         find :: CLabel -> [CmmNode O O] -> Maybe IpeSourceLocation -> Maybe IpeSourceLocation
  262         find label (b : blocks) lastTick = case b of
  263           (CmmStore _ (CmmLit (CmmLabel l))) -> if label == l then lastTick else find label blocks lastTick
  264           (CmmTick (SourceNote span name)) -> find label blocks $ Just (span, name)
  265           _ -> find label blocks lastTick
  266         find _ [] _ = Nothing