compiler/cmm/cmm-notes

   1 Notes on new codegen (Sept 09)\r
   2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\r
   3 \r
   4 Things to do:\r
   5  - Top-level SRT threading is a bit ugly\r
   6 \r
   7  - Add type/newtype for CmmModule = [CmmGroup]    -- A module\r
   8                         CmmGroup  = [CmmTop]      -- A .o file\r
   9                         CmmTop    = Proc | Data   -- A procedure or data\r
  10 \r
  11  - This is a *change*: currently a CmmGroup is one function's-worth of code\r
  12    regardless of SplitObjs.   Question: can we *always* generate M.o if there\r
  13    is just one element in the list (rather than M/M1.o, M/M2.o etc)\r
  14 \r
  15  - Change  \r
  16       type CmmZ = GenCmm CmmStatic CmmInfo (CmmStackInfo, CmmGraph)\r
  17    to\r
  18       type CmmZ = GenCmm CmmStatic (CmmInfo, CmmStackInfo) CmmGraph\r
  19         -- And perhaps take opportunity to prune CmmInfo?\r
  20 \r
  21  - Clarify which fields of CmmInfo are still used\r
  22  - Maybe get rid of CmmFormals arg of CmmProc in all versions?\r
  23 \r
  24  - We aren't sure whether cmmToRawCmm is actively used by the new pipeline; check\r
  25    And what does CmmBuildInfoTables do?!\r
  26 \r
  27  - Nuke CmmZipUtil, move zipPreds into ZipCfg\r
  28 \r
  29  - Pull out Areas into its own module\r
  30    Parameterise AreaMap\r
  31    Add ByteWidth = Int\r
  32    type SubArea    = (Area, ByteOff, ByteWidth) \r
  33    ByteOff should not be defined in SMRep -- that is too high up the hierarchy\r
  34    \r
  35  - Think about a non-flattened representation?\r
  36 \r
  37  - LastCall: \r
  38     * Use record fields for LastCall!\r
  39     * cml_ret_off should be a ByteOff\r
  40     * Split into \r
  41          LastCall (which has a successor) and\r
  42          LastJump (which does not, includes return?)\r
  43            - does not have cml_cont, cml_ret_args, cml_ret_off\r
  44          LastForeignCall \r
  45            - safe! \r
  46            - expands into save/MidForeignCall/restore/goto\r
  47            - like any LastCall, target of the call gets an info table\r
  48 \r
  49  - JD: remind self of what goes wrong if you turn off the \r
  50    liveness of the update frame\r
  51 \r
  52  - Garbage-collect http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/CPS\r
  53    moving good stuff into \r
  54    http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/NewCodeGenPipeline\r
  55 \r
  56 \r
  57  - We believe that all of CmmProcPointZ.addProcPointProtocols is dead.  What\r
  58    goes wrong if we simply never call it?\r
  59 \r
  60  - Something fishy in CmmStackLayout.hs\r
  61    * In particular, 'getAreaSize' returns an AreaMap, but we *know* the width of\r
  62         LocalRegs, so it'd be better to return FiniteMap AreaId ByteWidth\r
  63    * setSuccSPs looks fishy.  Rather than lookin in procPoints, it could\r
  64         just lookup the block in areaSize which, after all, has a binding\r
  65         for precisely successors of calls.  All other blocks (including proc\r
  66         points that are not successors of a call, we think) can be treated\r
  67         uniformly: zero-size Area, and use inSP.\r
  68 \r
  69 Dead files\r
  70 ~~~~~~~~~~\r
  71 CmmProcPoint (Michael Adams)\r
  72 CmmCPS (ditto)\r
  73 HscMain.optionallyConvertAndOrCPS\r
  74         testCmmConversion\r
  75 DynFlags:  -fconvert-to-zipper-and-back, -frun-cps, -frun-cpsz\r
  76 \r
  77 Proc-points\r
  78 ~~~~~~~~~~~~\r
  79 Consider this program, which has a diamond control flow, \r
  80 with a call on one branch\r
  81  fn(p,x) {\r
  82         h()\r
  83         if b then { ... f(x) ...; q=5; goto J }\r
  84              else { ...; q=7; goto J }\r
  85      J: ..p...q...\r
  86   }\r
  87 then the join point J is a "proc-point".  So, is 'p' passed to J\r
  88 as a parameter?  Or, if 'p' was saved on the stack anyway, perhaps\r
  89 to keep it alive across the call to h(), maybe 'p' gets communicated\r
  90 to J that way. This is an awkward choice.  (We think that we currently\r
  91 never pass variables to join points via arguments.)\r
  92 \r
  93 Furthermore, there is *no way* to pass q to J in a register (other\r
  94 than a paramter register).\r
  95 \r
  96 What we want is to do register allocation across the whole caboodle.\r
  97 Then we could drop all the code that deals with the above awkward\r
  98 decisions about spilling variables across proc-points.\r
  99 \r
 100 Note that J doesn't need an info table.\r
 101 \r
 102 What we really want is for each Block to have an optional info table.\r
 103 To do that, we need to be polymorphic over first nodes.\r
 104 \r
 105 Figuring out proc-points\r
 106 ~~~~~~~~~~~~~~~~~~~~~~~~\r
 107 Proc-points are identified by\r
 108 CmmProcPointZ.minimalProcPointSet/extendPPSet Although there isn't\r
 109 that much code, JD thinks that it could be done much more nicely using\r
 110 a dominator analysis, using the Dataflow Engine.\r
 111 \r
 112 ----------------------------------------------------\r
 113       Top-level structure\r
 114 ----------------------------------------------------\r
 115 \r
 116 * New codgen called in HscMain.hscGenHardCode, by calling HscMain.tryNewCodeGen, \r
 117   enabled by -fnew-codegen (Opt_TryNewCodeGen)\r
 118 \r
 119   THEN it calls CmmInfo.cmmToRawCmm to lay out the details of info tables\r
 120       type Cmm    = GenCmm CmmStatic CmmInfo     (ListGraph CmmStmt)\r
 121       type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)\r
 122 \r
 123 * HscMain.tryNewCodeGen\r
 124     - STG->Cmm:    StgCmm.codeGen (new codegen)\r
 125     - Optimise:    CmmContFlowOpt (simple optimisations, very self contained)\r
 126     - Cps convert: CmmCPSZ.protoCmmCPSZ \r
 127     - Optimise:    CmmContFlowOpt again\r
 128     - Convert:     CmmCvt.cmmOfZgraph (convert to old rep) very self contained\r
 129 \r
 130 * StgCmm.hs  The new STG -> Cmm conversion code generator\r
 131   Lots of modules StgCmmXXX\r
 132 \r
 133 \r
 134 ----------------------------------------------------\r
 135       CmmCPSZ.protoCmmCPSZ   The new pipeline\r
 136 ----------------------------------------------------\r
 137 \r
 138 CmmCPSZprotoCmmCPSZ:\r
 139    1. Do cpsTop for each procedures separately\r
 140    2. Build SRT representation; this spans multiple procedures\r
 141         (unless split-objs)\r
 142 \r
 143 cpsTop:\r
 144   * CmmCommonBlockElimZ.elimCommonBlocks:\r
 145         eliminate common blocks \r
 146 \r
 147   * CmmProcPointZ.minimalProcPointSet\r
 148         identify proc-points\r
 149 \r
 150   * CmmProcPointZ.addProcPointProtocols\r
 151         something to do with the MA optimisation\r
 152         probably entirely unnecessary\r
 153 \r
 154 \r
 155   * Spill and reload:\r
 156      - CmmSpillReload.dualLivenessWithInsertion\r
 157        insert spills/reloads across \r
 158            LastCalls, and \r
 159            Branches to proc-points\r
 160      Now sink those reloads:\r
 161      - CmmSpillReload.insertLateReloads\r
 162      - CmmSpillReload.removeDeadAssignmentsAndReloads\r
 163 \r
 164   * CmmStackLayout.stubSlotsOnDeath\r
 165         debug only: zero out dead slots when they die\r
 166 \r
 167   * Stack layout\r
 168      - CmmStackLayout.lifeSlotAnal: \r
 169        find which sub-areas are live on entry to each block\r
 170 \r
 171      - CmmStackLayout.layout\r
 172        Lay out the stack, returning an AreaMap\r
 173          type AreaMap    = FiniteMap Area ByteOff\r
 174           -- Byte offset of the oldest byte of the Area, \r
 175           -- relative to the oldest byte of the Old Area\r
 176 \r
 177      - CmmStackLayout.manifestSP\r
 178        Manifest the stack pointer\r
 179 \r
 180    * Split into separate procedures\r
 181       - CmmProcPointZ.procPointAnalysis\r
 182         Given set of proc points, which blocks are reachable from each\r
 183 \r
 184       - CmmProcPointZ.splitAtProcPoints\r
 185         Using this info, split into separate procedures\r
 186 \r
 187 ----------------------------------------------------\r
 188                 CAFs\r
 189 ----------------------------------------------------\r
 190 \r
 191 * The code for a procedure f may refer to either the *closure* \r
 192   or the *entry point* of another top-level procedure g.  \r
 193   If f is live, then so is g.  f's SRT must include g's closure.\r
 194 \r
 195 * The CLabel for the entry-point/closure reveals whether g is \r
 196   a CAF (or refers to CAFs).  See the IdLabell constructor of CLabel.\r
 197 \r
 198 * The CAF-ness of the original top-level defininions is figured out\r
 199   (by TidyPgm) before we generate C--.  This CafInfo is only set for\r
 200   top-level Ids; nested bindings stay with NoCafRefs.\r
 201 \r
 202 * Currently an SRT contains (only) pointers to (top-level) closures.\r
 203 \r
 204 * Consider this Core code\r
 205         f = \x -> let g = \y -> ...x...y...h1...\r
 206                   in ...h2...g...\r
 207   and suppose that h1, h2 have IdInfo of MayHaveCafRefs.\r
 208   Therefore, so will f,  But g will not (since it's nested).\r
 209 \r
 210   This generates C-- roughly like this:\r
 211      f_closure: .word f_entry\r
 212      f_entry() [info-tbl-for-f] { ...jump g_entry...jump h2... }\r
 213      g_entry() [info-tbl-for-g] { ...jump h1 }\r
 214 \r
 215   Note that there is no top-level closure for g (only an info table).\r
 216   So:   info-tbl-for-f must have an SRT that keeps h1,h2 alive\r
 217         info-tbl-for-g must have an SRT that keeps h1 (only) alive\r
 218 \r
 219   But if we just look for the free CAF refs, we get:\r
 220         f   h2 (only)\r
 221         g   h1\r
 222 \r
 223   So we need to do a transitive closure thing to flesh out \r
 224   f's keep-alive refs to include h1.\r
 225 \r
 226 * The SRT info is the C_SRT field of Cmm.ClosureTypeInfo in a\r
 227   CmmInfoTable attached to each CmmProc.  CmmCPSZ.toTops actually does\r
 228   the attaching, right at the end of the pipeline.  The C_SRT part\r
 229   gives offsets within a single, shared table of closure pointers.\r
 230 \r
 231 ----------------------------------------------------\r
 232                 Foreign calls\r
 233 ----------------------------------------------------\r
 234 \r
 235 See Note [Foreign calls] in ZipCfgCmmRep!  This explains that a safe\r
 236 foreign call must do this:\r
 237   save thread state\r
 238   push info table (on thread stack) to describe frame\r
 239   make call (via C stack)\r
 240   pop info table\r
 241   restore thread state\r
 242 and explains why this expansion must be done late in the day.\r
 243 \r
 244 Hence, \r
 245   - Every foreign call is represented as a middle node\r
 246 \r
 247   - *Unsafe* foreign calls are simply "fat machine instructions"\r
 248       and are passed along to the native code generator\r
 249 \r
 250   - *Safe* foreign calls are "lowered" to unsafe calls by wrapping\r
 251       them in the above save/restore sequence. This step is done\r
 252       very late in the pipeline, just before handing to the native\r
 253       code gen.   \r
 254   \r
 255       This lowering is done by BuildInfoTables.lowerSafeForeignCalls\r
 256 \r
 257 \r
 258 NEW PLAN for foreign calls:\r
 259   - Unsafe foreign calls remain as a middle node (fat machine instruction)\r
 260     Even the parameter passing is not lowered (just as machine instrs\r
 261     get arguments).\r
 262 \r
 263   - Initially, safe foreign calls appear as LastCalls with \r
 264         \r
 265 \r
 266 ----------------------------------------------------\r
 267                 Cmm representations\r
 268 ----------------------------------------------------\r
 269 \r
 270 * Cmm.hs\r
 271      The type [GenCmm d h g] represents a whole module, \r
 272         ** one list element per .o file **\r
 273         Without SplitObjs, the list has exactly one element\r
 274 \r
 275      newtype GenCmm d h g = Cmm [GenCmmTop d h g]  -- A whole .o file\r
 276      data GenCmmTop d h g\r
 277          = CmmProc h g           -- One procedure, graph d\r
 278          | CmmData <stuff> [d]   -- Initialised data, items d\r
 279 \r
 280   Old and new piplines use different representations\r
 281         (CmmCvt.hs converts between the two)\r
 282 \r
 283 \r
 284 -------------\r
 285 OLD BACK END representations (Cmm.hs):  \r
 286       type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)\r
 287                                 -- A whole module\r
 288       newtype ListGraph i = ListGraph [GenBasicBlock i]\r
 289 \r
 290       data CmmStmt = Assign | Store | Return etc -- OLD BACK END ONLY\r
 291 \r
 292 \r
 293    Once the info tables are laid out, we replace CmmInfo with [CmmStatic]\r
 294       type RawCmm    = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)\r
 295    which represents the info tables as data, that should \r
 296    immediately precede the code\r
 297   \r
 298 -------------\r
 299 NEW BACK END representations \r
 300 * Not Cmm-specific at all\r
 301     ZipCfg.hs defines  Graph, LGraph, FGraph,\r
 302                        ZHead, ZTail, ZBlock ...\r
 303 \r
 304               classes  LastNode, HavingSuccessors\r
 305 \r
 306     MkZipCfg.hs: AGraph: building graphs\r
 307 \r
 308 * ZipCfgCmmRep: instantiates ZipCfg for Cmm\r
 309       data Middle = ...CmmExpr...\r
 310       data Last = ...CmmExpr...\r
 311       type CmmGraph = Graph Middle Last\r
 312 \r
 313       type CmmZ = GenCmm CmmStatic CmmInfo (CmmStackInfo, CmmGraph)\r
 314       type CmmStackInfo = (ByteOff, Maybe ByteOff)\r
 315                 -- (SP offset on entry, update frame space = SP offset on exit)\r
 316                 -- The new codegen produces CmmZ, but once the stack is \r
 317                 -- manifested we can drop that in favour of \r
 318                 --    GenCmm CmmStatic CmmInfo CmmGraph\r
 319 \r
 320       Inside a CmmProc:\r
 321            - CLabel: used\r
 322            - CmmInfo: partly used by NEW\r
 323            - CmmFormals: not used at all  PERHAPS NOT EVEN BY OLD PIPELINE!\r
 324 \r
 325 * MkZipCfgCmm.hs: smart constructors for ZipCfgCmmRep\r
 326    Depends on (a) MkZipCfg (Cmm-independent)\r
 327               (b) ZipCfgCmmRep (Cmm-specific)\r
 328 \r
 329 -------------\r
 330 * SHARED stuff\r
 331   CmmExpr.hs defines the Cmm expression types\r
 332         - CmmExpr, CmmReg, Width, CmmLit, LocalReg, GlobalReg\r
 333         - CmmType, Width etc   (saparate module?)\r
 334         - MachOp               (separate module?)\r
 335         - Area, AreaId etc     (separate module?)\r
 336 \r
 337   BlockId.hs defines  BlockId, BlockEnv, BlockSet\r
 338 \r
 339 -------------\r
 340 \r
 341 \r
 342 -------------\r
 343 * Transactions indicate whether or not the result changes: CmmTx \r
 344      type Tx a = a -> TxRes a\r
 345      data TxRes a = TxRes ChangeFlag a\r