compiler/cmm/cmm-notes

   1 Notes on new codegen (Sept 09)\r
   2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\r
   3 \r
   4 Things to do:\r
   5  - Consider module names\r
   6 \r
   7  - Top-level SRT threading is a bit ugly\r
   8 \r
   9  - Add type/newtype for CmmModule = [CmmGroup]    -- A module\r
  10                         CmmGroup  = [CmmTop]      -- A .o file\r
  11                         CmmTop    = Proc | Data   -- A procedure or data\r
  12 \r
  13  - This is a *change*: currently a CmmGroup is one function's-worth of code\r
  14    regardless of SplitObjs.   Question: can we *always* generate M.o if there\r
  15    is just one element in the list (rather than M/M1.o, M/M2.o etc)\r
  16 \r
  17    One SRT per group.\r
  18 \r
  19  - See "CAFs" below; we want to totally refactor the way SRTs are calculated\r
  20 \r
  21  - Change  \r
  22       type CmmZ = GenCmm CmmStatic CmmInfo (CmmStackInfo, CmmGraph)\r
  23    to\r
  24       type CmmZ = GenCmm CmmStatic (CmmInfo, CmmStackInfo) CmmGraph\r
  25         -- And perhaps take opportunity to prune CmmInfo?\r
  26 \r
  27  - Clarify which fields of CmmInfo are still used\r
  28  - Maybe get rid of CmmFormals arg of CmmProc in all versions?\r
  29 \r
  30  - We aren't sure whether cmmToRawCmm is actively used by the new pipeline; check\r
  31    And what does CmmBuildInfoTables do?!\r
  32 \r
  33  - Nuke CmmZipUtil, move zipPreds into ZipCfg\r
  34 \r
  35  - Pull out Areas into its own module\r
  36    Parameterise AreaMap\r
  37    Add ByteWidth = Int\r
  38    type SubArea    = (Area, ByteOff, ByteWidth) \r
  39    ByteOff should not be defined in SMRep -- that is too high up the hierarchy\r
  40    \r
  41  - SMRep should not be imported by any module in cmm/!  Make it so.\r
  42         -- ByteOff etc   ==>  CmmExpr\r
  43         -- rET_SMALL etc ==> CmmInfo\r
  44    Check that there are no other imports from codeGen in cmm/\r
  45 \r
  46  - Think about a non-flattened representation?\r
  47 \r
  48  - LastCall: \r
  49     * Use record fields for LastCall!\r
  50     * cml_ret_off should be a ByteOff\r
  51     * Split into \r
  52          LastCall (which has a successor) and\r
  53          LastJump (which does not, includes return?)\r
  54            - does not have cml_cont, cml_ret_args, cml_ret_off\r
  55          LastForeignCall \r
  56            - safe! \r
  57            - expands into save/MidForeignCall/restore/goto\r
  58            - like any LastCall, target of the call gets an info table\r
  59 \r
  60  - JD: remind self of what goes wrong if you turn off the \r
  61    liveness of the update frame\r
  62 \r
  63  - Garbage-collect http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/CPS\r
  64    moving good stuff into \r
  65    http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/NewCodeGenPipeline\r
  66 \r
  67 \r
  68  - We believe that all of CmmProcPointZ.addProcPointProtocols is dead.  What\r
  69    goes wrong if we simply never call it?\r
  70 \r
  71  - Something fishy in CmmStackLayout.hs\r
  72    * In particular, 'getAreaSize' returns an AreaMap, but we *know* the width of\r
  73         LocalRegs, so it'd be better to return FiniteMap AreaId ByteWidth\r
  74    * setSuccSPs looks fishy.  Rather than lookin in procPoints, it could\r
  75         just lookup the block in areaSize which, after all, has a binding\r
  76         for precisely successors of calls.  All other blocks (including proc\r
  77         points that are not successors of a call, we think) can be treated\r
  78         uniformly: zero-size Area, and use inSP.\r
  79 \r
  80 \r
  81  - Currently AsmCodeGen top level calls AsmCodeGen.cmmToCmm, which is a small\r
  82    C-- optimiser.  It has quite a lot of boilerplate folding code in AsmCodeGen\r
  83    (cmmBlockConFold, cmmStmtConFold, cmmExprConFold), before calling out to\r
  84    CmmOpt.  ToDo: see what optimisations are being done; and do them before\r
  85    AsmCodeGen.\r
  86 \r
  87  - Modularise the CPS pipeline; instead of ...; A;B;C; ...\r
  88                                 use  ..; ABC; ....\r
  89 \r
  90  - Most of HscMain.tryNewCodeGen does not belong in HscMain.  Instead\r
  91         if new_cg then\r
  92              StgCmm.codeGen\r
  93              processCmm  [including generating "raw" cmm]\r
  94         else\r
  95              CodeGen.codeGen\r
  96              cmmToRawCmm\r
  97 \r
  98 \r
  99  - If we stick CAF and stack liveness info on a LastCall node (not LastRet/Jump)\r
 100    then all CAF and stack liveness stuff be completed before we split\r
 101    into separate C procedures.\r
 102 \r
 103    Short term:\r
 104      compute and attach liveness into to LastCall\r
 105      right at end, split, cvt to old rep\r
 106      [must split before cvt, because old rep is not expressive enough]\r
 107 \r
 108    Longer term: \r
 109      when old rep disappears, \r
 110      move the whole splitting game into the C back end *only*\r
 111          (guided by the procpoint set)\r
 112 \r
 113       \r
 114 ----------------------------------------------------\r
 115         Modules in cmm/\r
 116 ----------------------------------------------------\r
 117 \r
 118 -------- Dead stuff ------------\r
 119 CmmProcPoint        Dead: Michael Adams\r
 120 CmmCPS              Dead: Michael Adams\r
 121 CmmCPSGen.hs        Dead: Michael Adams\r
 122 CmmBrokenBlock.hs   Dead: Michael Adams\r
 123 CmmLive.hs          Dead: Michael Adams\r
 124 CmmProcPoint.hs     Dead: Michael Adams\r
 125 Dataflow.hs         Dead: Michael Adams\r
 126 StackColor.hs       Norman?\r
 127 StackPlacements.hs  Norman?\r
 128 \r
 129 HscMain.optionallyConvertAndOrCPS\r
 130         testCmmConversion\r
 131 DynFlags:  -fconvert-to-zipper-and-back, -frun-cps, -frun-cpsz\r
 132 \r
 133 -------- Moribund stuff ------------\r
 134 CmmCvt.hs      Conversion between old and new Cmm reps\r
 135 CmmOpt.hs      Hopefully-redundant optimiser\r
 136 CmmZipUtil.hs  Only one function; move elsewhere\r
 137 \r
 138 -------- Stuff to keep ------------\r
 139 CmmCPSZ.hs                Driver for new pipeline\r
 140 \r
 141 CmmLiveZ.hs               Liveness analysis, dead code elim\r
 142 CmmProcPointZ.hs          Identifying and splitting out proc-points\r
 143 \r
 144 CmmSpillReload.hs         Save and restore across calls\r
 145 \r
 146 CmmCommonBlockElimZ.hs    Common block elim\r
 147 CmmContFlowOpt.hs         Other optimisations (branch-chain, merging)\r
 148 \r
 149 CmmBuildInfoTables.hs     New info-table \r
 150 CmmStackLayout.hs         and stack layout \r
 151 CmmCallConv.hs\r
 152 CmmInfo.hs                Defn of InfoTables, and conversion to exact layout\r
 153 \r
 154 ---------- Cmm data types --------------\r
 155 ZipCfgCmmRep.hs     Cmm instantiations of dataflow graph framework\r
 156 MkZipCfgCmm.hs      Cmm instantiations of dataflow graph framework\r
 157 \r
 158 Cmm.hs        Key module; a mix of old and new stuff\r
 159                   so needs tidying up in due course\r
 160 CmmExpr.hs\r
 161 CmmUtils.hs\r
 162 CmmLint.hs\r
 163 \r
 164 PprC.hs             Pretty print Cmm in C syntax\r
 165 PprCmm.hs           Pretty printer for Cmm\r
 166 PprCmmZ.hs          Additional stuff for zipper rep\r
 167 \r
 168 CLabel.hs     CLabel\r
 169 \r
 170 ----------  Dataflow modules --------------\r
 171    Goal: separate library; for now, separate directory\r
 172 \r
 173 MkZipCfg.hs\r
 174 ZipCfg.hs\r
 175 ZipCfgExtras.hs\r
 176 ZipDataflow.hs\r
 177 CmmTx.hs              Transactions\r
 178 OptimizationFuel.hs   Fuel\r
 179 BlockId.hs    BlockId, BlockEnv, BlockSet\r
 180 DFMonad.hs            \r
 181 \r
 182 \r
 183 ----------------------------------------------------\r
 184       Top-level structure\r
 185 ----------------------------------------------------\r
 186 \r
 187 * New codgen called in HscMain.hscGenHardCode, by calling HscMain.tryNewCodeGen, \r
 188   enabled by -fnew-codegen (Opt_TryNewCodeGen)\r
 189 \r
 190   THEN it calls CmmInfo.cmmToRawCmm to lay out the details of info tables\r
 191       type Cmm    = GenCmm CmmStatic CmmInfo     (ListGraph CmmStmt)\r
 192       type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)\r
 193 \r
 194 * HscMain.tryNewCodeGen\r
 195     - STG->Cmm:    StgCmm.codeGen (new codegen)\r
 196     - Optimise:    CmmContFlowOpt (simple optimisations, very self contained)\r
 197     - Cps convert: CmmCPSZ.protoCmmCPSZ \r
 198     - Optimise:    CmmContFlowOpt again\r
 199     - Convert:     CmmCvt.cmmOfZgraph (convert to old rep) very self contained\r
 200 \r
 201 * StgCmm.hs  The new STG -> Cmm conversion code generator\r
 202   Lots of modules StgCmmXXX\r
 203 \r
 204 \r
 205 ----------------------------------------------------\r
 206       CmmCPSZ.protoCmmCPSZ   The new pipeline\r
 207 ----------------------------------------------------\r
 208 \r
 209 CmmCPSZprotoCmmCPSZ:\r
 210    1. Do cpsTop for each procedures separately\r
 211    2. Build SRT representation; this spans multiple procedures\r
 212         (unless split-objs)\r
 213 \r
 214 cpsTop:\r
 215   * CmmCommonBlockElimZ.elimCommonBlocks:\r
 216         eliminate common blocks \r
 217 \r
 218   * CmmProcPointZ.minimalProcPointSet\r
 219         identify proc-points\r
 220         no change to graph\r
 221 \r
 222   * CmmProcPointZ.addProcPointProtocols\r
 223         something to do with the MA optimisation\r
 224         probably entirely unnecessary\r
 225 \r
 226   * Spill and reload:\r
 227      - CmmSpillReload.dualLivenessWithInsertion\r
 228        insert spills/reloads across \r
 229            LastCalls, and \r
 230            Branches to proc-points\r
 231      Now sink those reloads:\r
 232      - CmmSpillReload.insertLateReloads\r
 233      - CmmSpillReload.removeDeadAssignmentsAndReloads\r
 234 \r
 235   * CmmStackLayout.stubSlotsOnDeath\r
 236         debug only: zero out dead slots when they die\r
 237 \r
 238   * Stack layout\r
 239      - CmmStackLayout.lifeSlotAnal: \r
 240        find which sub-areas are live on entry to each block\r
 241 \r
 242      - CmmStackLayout.layout\r
 243        Lay out the stack, returning an AreaMap\r
 244          type AreaMap = FiniteMap Area ByteOff\r
 245           -- Byte offset of the oldest byte of the Area, \r
 246           -- relative to the oldest byte of the Old Area\r
 247 \r
 248      - CmmStackLayout.manifestSP\r
 249        Manifest the stack pointer\r
 250 \r
 251    * Split into separate procedures\r
 252       - CmmProcPointZ.procPointAnalysis\r
 253         Given set of proc points, which blocks are reachable from each\r
 254         Claim: too few proc-points => code duplication, but program still works??\r
 255 \r
 256       - CmmProcPointZ.splitAtProcPoints\r
 257         Using this info, split into separate procedures\r
 258 \r
 259       - CmmBuildInfoTables.setInfoTableStackMap\r
 260         Attach stack maps to each info table\r
 261 \r
 262 \r
 263 ----------------------------------------------------\r
 264         Proc-points\r
 265 ----------------------------------------------------\r
 266 \r
 267 Consider this program, which has a diamond control flow, \r
 268 with a call on one branch\r
 269  fn(p,x) {\r
 270         h()\r
 271         if b then { ... f(x) ...; q=5; goto J }\r
 272              else { ...; q=7; goto J }\r
 273      J: ..p...q...\r
 274   }\r
 275 then the join point J is a "proc-point".  So, is 'p' passed to J\r
 276 as a parameter?  Or, if 'p' was saved on the stack anyway, perhaps\r
 277 to keep it alive across the call to h(), maybe 'p' gets communicated\r
 278 to J that way. This is an awkward choice.  (We think that we currently\r
 279 never pass variables to join points via arguments.)\r
 280 \r
 281 Furthermore, there is *no way* to pass q to J in a register (other\r
 282 than a paramter register).\r
 283 \r
 284 What we want is to do register allocation across the whole caboodle.\r
 285 Then we could drop all the code that deals with the above awkward\r
 286 decisions about spilling variables across proc-points.\r
 287 \r
 288 Note that J doesn't need an info table.\r
 289 \r
 290 What we really want is for each LastCall (not LastJump/Ret) \r
 291 to have an info table.   Note that ProcPoints that are not successors\r
 292 of calls don't need an info table.\r
 293 \r
 294 Figuring out proc-points\r
 295 ~~~~~~~~~~~~~~~~~~~~~~~~\r
 296 Proc-points are identified by\r
 297 CmmProcPointZ.minimalProcPointSet/extendPPSet Although there isn't\r
 298 that much code, JD thinks that it could be done much more nicely using\r
 299 a dominator analysis, using the Dataflow Engine.\r
 300 \r
 301 ----------------------------------------------------\r
 302                 CAFs\r
 303 ----------------------------------------------------\r
 304 \r
 305 * The code for a procedure f may refer to either the *closure* \r
 306   or the *entry point* of another top-level procedure g.  \r
 307   If f is live, then so is g.  f's SRT must include g's closure.\r
 308 \r
 309 * The CLabel for the entry-point/closure reveals whether g is \r
 310   a CAF (or refers to CAFs).  See the IdLabel constructor of CLabel.\r
 311 \r
 312 * The CAF-ness of the original top-level defininions is figured out\r
 313   (by TidyPgm) before we generate C--.  This CafInfo is only set for\r
 314   top-level Ids; nested bindings stay with MayHaveCafRefs.\r
 315 \r
 316 * Currently an SRT contains (only) pointers to (top-level) closures.\r
 317 \r
 318 * Consider this Core code\r
 319         f = \x -> let g = \y -> ...x...y...h1...\r
 320                   in ...h2...g...\r
 321   and suppose that h1, h2 have IdInfo of MayHaveCafRefs.\r
 322   Therefore, so will f,  But g will not (since it's nested).\r
 323 \r
 324   This generates C-- roughly like this:\r
 325      f_closure: .word f_entry\r
 326      f_entry() [info-tbl-for-f] { ...jump g_entry...jump h2... }\r
 327      g_entry() [info-tbl-for-g] { ...jump h1... }\r
 328 \r
 329   Note that there is no top-level closure for g (only an info table).\r
 330   This fact (whether or not there is a top-level closure) is recorded\r
 331   in the InfoTable attached to the CmmProc for f, g\r
 332   INVARIANT: \r
 333      Any out-of-Group references to an IdLabel goes to\r
 334      a Proc whose InfoTable says "I have a top-level closure".\r
 335   Equivalently: \r
 336      A CmmProc whose InfoTable says "I do not have a top-level\r
 337      closure" is referred to only from its own Group.\r
 338 \r
 339 * So:   info-tbl-for-f must have an SRT that keeps h1,h2 alive\r
 340         info-tbl-for-g must have an SRT that keeps h1 (only) alive\r
 341 \r
 342   But if we just look for the free CAF refs, we get:\r
 343         f   h2 (only)\r
 344         g   h1\r
 345 \r
 346   So we need to do a transitive closure thing to flesh out \r
 347   f's keep-alive refs to include h1.\r
 348 \r
 349 * The SRT info is the C_SRT field of Cmm.ClosureTypeInfo in a\r
 350   CmmInfoTable attached to each CmmProc.  CmmCPSZ.toTops actually does\r
 351   the attaching, right at the end of the pipeline.  The C_SRT part\r
 352   gives offsets within a single, shared table of closure pointers.\r
 353 \r
 354 * DECIDED: we can generate SRTs based on the final Cmm program\r
 355   without knowledge of how it is generated.\r
 356 \r
 357 ----------------------------------------------------\r
 358                 Foreign calls\r
 359 ----------------------------------------------------\r
 360 \r
 361 See Note [Foreign calls] in ZipCfgCmmRep!  This explains that a safe\r
 362 foreign call must do this:\r
 363   save thread state\r
 364   push info table (on thread stack) to describe frame\r
 365   make call (via C stack)\r
 366   pop info table\r
 367   restore thread state\r
 368 and explains why this expansion must be done late in the day.\r
 369 \r
 370 Hence, \r
 371   - Every foreign call is represented as a middle node\r
 372 \r
 373   - *Unsafe* foreign calls are simply "fat machine instructions"\r
 374       and are passed along to the native code generator\r
 375 \r
 376   - *Safe* foreign calls are "lowered" to unsafe calls by wrapping\r
 377       them in the above save/restore sequence. This step is done\r
 378       very late in the pipeline, just before handing to the native\r
 379       code gen.   \r
 380   \r
 381       This lowering is done by BuildInfoTables.lowerSafeForeignCalls\r
 382 \r
 383 \r
 384 NEW PLAN for foreign calls:\r
 385   - Unsafe foreign calls remain as a middle node (fat machine instruction)\r
 386     Even the parameter passing is not lowered (just as machine instrs\r
 387     get arguments).\r
 388 \r
 389   - Initially, safe foreign calls appear as LastCalls with \r
 390         \r
 391 \r
 392 ----------------------------------------------------\r
 393                 Cmm representations\r
 394 ----------------------------------------------------\r
 395 \r
 396 * Cmm.hs\r
 397      The type [GenCmm d h g] represents a whole module, \r
 398         ** one list element per .o file **\r
 399         Without SplitObjs, the list has exactly one element\r
 400 \r
 401      newtype GenCmm d h g = Cmm [GenCmmTop d h g]  -- A whole .o file\r
 402      data GenCmmTop d h g\r
 403          = CmmProc h g           -- One procedure, graph d\r
 404          | CmmData <stuff> [d]   -- Initialised data, items d\r
 405 \r
 406   Old and new piplines use different representations\r
 407         (CmmCvt.hs converts between the two)\r
 408 \r
 409 \r
 410 -------------\r
 411 OLD BACK END representations (Cmm.hs):  \r
 412       type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)\r
 413                                 -- A whole module\r
 414       newtype ListGraph i = ListGraph [GenBasicBlock i]\r
 415 \r
 416       data CmmStmt = Assign | Store | Return etc -- OLD BACK END ONLY\r
 417 \r
 418 \r
 419    Once the info tables are laid out, we replace CmmInfo with [CmmStatic]\r
 420       type RawCmm    = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)\r
 421    which represents the info tables as data, that should \r
 422    immediately precede the code\r
 423   \r
 424 -------------\r
 425 NEW BACK END representations \r
 426 * Not Cmm-specific at all\r
 427     ZipCfg.hs defines  Graph, LGraph, FGraph,\r
 428                        ZHead, ZTail, ZBlock ...\r
 429 \r
 430               classes  LastNode, HavingSuccessors\r
 431 \r
 432     MkZipCfg.hs: AGraph: building graphs\r
 433 \r
 434 * ZipCfgCmmRep: instantiates ZipCfg for Cmm\r
 435       data Middle = ...CmmExpr...\r
 436       data Last = ...CmmExpr...\r
 437       type CmmGraph = Graph Middle Last\r
 438 \r
 439       type CmmZ = GenCmm CmmStatic CmmInfo (CmmStackInfo, CmmGraph)\r
 440       type CmmStackInfo = (ByteOff, Maybe ByteOff)\r
 441                 -- (SP offset on entry, update frame space = SP offset on exit)\r
 442                 -- The new codegen produces CmmZ, but once the stack is \r
 443                 -- manifested we can drop that in favour of \r
 444                 --    GenCmm CmmStatic CmmInfo CmmGraph\r
 445 \r
 446       Inside a CmmProc:\r
 447            - CLabel: used\r
 448            - CmmInfo: partly used by NEW\r
 449            - CmmFormals: not used at all  PERHAPS NOT EVEN BY OLD PIPELINE!\r
 450 \r
 451 * MkZipCfgCmm.hs: smart constructors for ZipCfgCmmRep\r
 452    Depends on (a) MkZipCfg (Cmm-independent)\r
 453               (b) ZipCfgCmmRep (Cmm-specific)\r
 454 \r
 455 -------------\r
 456 * SHARED stuff\r
 457   CmmExpr.hs defines the Cmm expression types\r
 458         - CmmExpr, CmmReg, Width, CmmLit, LocalReg, GlobalReg\r
 459         - CmmType, Width etc   (saparate module?)\r
 460         - MachOp               (separate module?)\r
 461         - Area, AreaId etc     (separate module?)\r
 462 \r
 463   BlockId.hs defines  BlockId, BlockEnv, BlockSet\r
 464 \r
 465 -------------\r
 466 \r
 467 \r
 468 -------------\r
 469 * Transactions indicate whether or not the result changes: CmmTx \r
 470      type Tx a = a -> TxRes a\r
 471      data TxRes a = TxRes ChangeFlag a\r