compiler/cmm/cmm-notes

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