path: root/compiler/cmm/cmm-notes

Notes on new codegen (Sept 09)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Things to do:
 - Consider module names

 - Top-level SRT threading is a bit ugly

 - Add type/newtype for CmmModule = [CmmGroup]    -- A module
                        CmmGroup  = [CmmTop]      -- A .o file
                        CmmTop    = Proc | Data   -- A procedure or data

 - This is a *change*: currently a CmmGroup is one function's-worth of code
   regardless of SplitObjs.   Question: can we *always* generate M.o if there
   is just one element in the list (rather than M/M1.o, M/M2.o etc)

   One SRT per group.

 - See "CAFs" below; we want to totally refactor the way SRTs are calculated

 - Change  
      type CmmZ = GenCmm CmmStatic CmmInfo (CmmStackInfo, CmmGraph)
   to
      type CmmZ = GenCmm CmmStatic (CmmInfo, CmmStackInfo) CmmGraph
	-- And perhaps take opportunity to prune CmmInfo?

 - Clarify which fields of CmmInfo are still used
 - Maybe get rid of CmmFormals arg of CmmProc in all versions?

 - We aren't sure whether cmmToRawCmm is actively used by the new pipeline; check
   And what does CmmBuildInfoTables do?!

 - Nuke CmmZipUtil, move zipPreds into ZipCfg

 - Pull out Areas into its own module
   Parameterise AreaMap
   Add ByteWidth = Int
   type SubArea    = (Area, ByteOff, ByteWidth) 
   ByteOff should not be defined in SMRep -- that is too high up the hierarchy
   
 - SMRep should not be imported by any module in cmm/!  Make it so.
	-- ByteOff etc   ==>  CmmExpr
        -- rET_SMALL etc ==> CmmInfo
   Check that there are no other imports from codeGen in cmm/

 - Think about a non-flattened representation?

 - LastCall: 
    * Use record fields for LastCall!
    * cml_ret_off should be a ByteOff
    * Split into 
         LastCall (which has a successor) and
         LastJump (which does not, includes return?)
	   - does not have cml_cont, cml_ret_args, cml_ret_off
	 LastForeignCall 
           - safe! 
           - expands into save/MidForeignCall/restore/goto
	   - like any LastCall, target of the call gets an info table

 - JD: remind self of what goes wrong if you turn off the 
   liveness of the update frame

 - Garbage-collect http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/CPS
   moving good stuff into 
   http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/NewCodeGenPipeline


 - We believe that all of CmmProcPointZ.addProcPointProtocols is dead.  What
   goes wrong if we simply never call it?

 - Something fishy in CmmStackLayout.hs
   * In particular, 'getAreaSize' returns an AreaMap, but we *know* the width of
	LocalRegs, so it'd be better to return FiniteMap AreaId ByteWidth
   * setSuccSPs looks fishy.  Rather than lookin in procPoints, it could
	just lookup the block in areaSize which, after all, has a binding
	for precisely successors of calls.  All other blocks (including proc
        points that are not successors of a call, we think) can be treated
        uniformly: zero-size Area, and use inSP.


 - Currently AsmCodeGen top level calls AsmCodeGen.cmmToCmm, which is a small
   C-- optimiser.  It has quite a lot of boilerplate folding code in AsmCodeGen
   (cmmBlockConFold, cmmStmtConFold, cmmExprConFold), before calling out to
   CmmOpt.  ToDo: see what optimisations are being done; and do them before
   AsmCodeGen.

 - Modularise the CPS pipeline; instead of ...; A;B;C; ...
                                use  ..; ABC; ....

 - Most of HscMain.tryNewCodeGen does not belong in HscMain.  Instead
	if new_cg then
             StgCmm.codeGen
             processCmm  [including generating "raw" cmm]
        else
             CodeGen.codeGen
             cmmToRawCmm


 - If we stick CAF and stack liveness info on a LastCall node (not LastRet/Jump)
   then all CAF and stack liveness stuff be completed before we split
   into separate C procedures.

   Short term:
     compute and attach liveness into to LastCall
     right at end, split, cvt to old rep
     [must split before cvt, because old rep is not expressive enough]

   Longer term: 
     when old rep disappears, 
     move the whole splitting game into the C back end *only*
	 (guided by the procpoint set)

      
----------------------------------------------------
	Modules in cmm/
----------------------------------------------------

-------- Dead stuff ------------
CmmProcPoint        Dead: Michael Adams
CmmCPS              Dead: Michael Adams
CmmCPSGen.hs        Dead: Michael Adams
CmmBrokenBlock.hs   Dead: Michael Adams
CmmLive.hs          Dead: Michael Adams
CmmProcPoint.hs     Dead: Michael Adams
Dataflow.hs         Dead: Michael Adams
StackColor.hs       Norman?
StackPlacements.hs  Norman?

HscMain.optionallyConvertAndOrCPS
        testCmmConversion
DynFlags:  -fconvert-to-zipper-and-back, -frun-cps, -frun-cpsz

-------- Moribund stuff ------------
CmmCvt.hs      Conversion between old and new Cmm reps
CmmOpt.hs      Hopefully-redundant optimiser
CmmZipUtil.hs  Only one function; move elsewhere

-------- Stuff to keep ------------
CmmCPSZ.hs	          Driver for new pipeline

CmmLiveZ.hs	          Liveness analysis, dead code elim
CmmProcPointZ.hs          Identifying and splitting out proc-points

CmmSpillReload.hs         Save and restore across calls

CmmCommonBlockElimZ.hs    Common block elim
CmmContFlowOpt.hs         Other optimisations (branch-chain, merging)

CmmBuildInfoTables.hs     New info-table 
CmmStackLayout.hs         and stack layout 
CmmCallConv.hs
CmmInfo.hs                Defn of InfoTables, and conversion to exact layout

---------- Cmm data types --------------
ZipCfgCmmRep.hs	    Cmm instantiations of dataflow graph framework
MkZipCfgCmm.hs      Cmm instantiations of dataflow graph framework

Cmm.hs	      Key module; a mix of old and new stuff
                  so needs tidying up in due course
CmmExpr.hs
CmmUtils.hs
CmmLint.hs

PprC.hs	            Pretty print Cmm in C syntax
PprCmm.hs	    Pretty printer for Cmm
PprCmmZ.hs	    Additional stuff for zipper rep

CLabel.hs     CLabel

----------  Dataflow modules --------------
   Goal: separate library; for now, separate directory

MkZipCfg.hs
ZipCfg.hs
ZipCfgExtras.hs
ZipDataflow.hs
CmmTx.hs	      Transactions
OptimizationFuel.hs   Fuel
BlockId.hs    BlockId, BlockEnv, BlockSet
DFMonad.hs	      


----------------------------------------------------
      Top-level structure
----------------------------------------------------

* New codgen called in HscMain.hscGenHardCode, by calling HscMain.tryNewCodeGen, 
  enabled by -fnew-codegen (Opt_TryNewCodeGen)

  THEN it calls CmmInfo.cmmToRawCmm to lay out the details of info tables
      type Cmm    = GenCmm CmmStatic CmmInfo     (ListGraph CmmStmt)
      type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)

* HscMain.tryNewCodeGen
    - STG->Cmm:    StgCmm.codeGen (new codegen)
    - Optimise:    CmmContFlowOpt (simple optimisations, very self contained)
    - Cps convert: CmmCPSZ.protoCmmCPSZ 
    - Optimise:    CmmContFlowOpt again
    - Convert:     CmmCvt.cmmOfZgraph (convert to old rep) very self contained

* StgCmm.hs  The new STG -> Cmm conversion code generator
  Lots of modules StgCmmXXX


----------------------------------------------------
      CmmCPSZ.protoCmmCPSZ   The new pipeline
----------------------------------------------------

CmmCPSZprotoCmmCPSZ:
   1. Do cpsTop for each procedures separately
   2. Build SRT representation; this spans multiple procedures
	(unless split-objs)

cpsTop:
  * CmmCommonBlockElimZ.elimCommonBlocks:
	eliminate common blocks 

  * CmmProcPointZ.minimalProcPointSet
	identify proc-points
        no change to graph

  * CmmProcPointZ.addProcPointProtocols
	something to do with the MA optimisation
        probably entirely unnecessary

  * Spill and reload:
     - CmmSpillReload.dualLivenessWithInsertion
       insert spills/reloads across 
	   LastCalls, and 
	   Branches to proc-points
     Now sink those reloads:
     - CmmSpillReload.insertLateReloads
     - CmmSpillReload.removeDeadAssignmentsAndReloads

  * CmmStackLayout.stubSlotsOnDeath
	debug only: zero out dead slots when they die

  * Stack layout
     - CmmStackLayout.lifeSlotAnal: 
       find which sub-areas are live on entry to each block

     - CmmStackLayout.layout
       Lay out the stack, returning an AreaMap
         type AreaMap = FiniteMap Area ByteOff
          -- Byte offset of the oldest byte of the Area, 
          -- relative to the oldest byte of the Old Area

     - CmmStackLayout.manifestSP
       Manifest the stack pointer

   * Split into separate procedures
      - CmmProcPointZ.procPointAnalysis
        Given set of proc points, which blocks are reachable from each
        Claim: too few proc-points => code duplication, but program still works??

      - CmmProcPointZ.splitAtProcPoints
	Using this info, split into separate procedures

      - CmmBuildInfoTables.setInfoTableStackMap
	Attach stack maps to each info table


----------------------------------------------------
	Proc-points
----------------------------------------------------

Consider this program, which has a diamond control flow, 
with a call on one branch
 fn(p,x) {
        h()
	if b then { ... f(x) ...; q=5; goto J }
             else { ...; q=7; goto J }
     J: ..p...q...
  }
then the join point J is a "proc-point".  So, is 'p' passed to J
as a parameter?  Or, if 'p' was saved on the stack anyway, perhaps
to keep it alive across the call to h(), maybe 'p' gets communicated
to J that way. This is an awkward choice.  (We think that we currently
never pass variables to join points via arguments.)

Furthermore, there is *no way* to pass q to J in a register (other
than a paramter register).

What we want is to do register allocation across the whole caboodle.
Then we could drop all the code that deals with the above awkward
decisions about spilling variables across proc-points.

Note that J doesn't need an info table.

What we really want is for each LastCall (not LastJump/Ret) 
to have an info table.   Note that ProcPoints that are not successors
of calls don't need an info table.

Figuring out proc-points
~~~~~~~~~~~~~~~~~~~~~~~~
Proc-points are identified by
CmmProcPointZ.minimalProcPointSet/extendPPSet Although there isn't
that much code, JD thinks that it could be done much more nicely using
a dominator analysis, using the Dataflow Engine.

----------------------------------------------------
		CAFs
----------------------------------------------------

* The code for a procedure f may refer to either the *closure* 
  or the *entry point* of another top-level procedure g.  
  If f is live, then so is g.  f's SRT must include g's closure.

* The CLabel for the entry-point/closure reveals whether g is 
  a CAF (or refers to CAFs).  See the IdLabel constructor of CLabel.

* The CAF-ness of the original top-level defininions is figured out
  (by TidyPgm) before we generate C--.  This CafInfo is only set for
  top-level Ids; nested bindings stay with MayHaveCafRefs.

* Currently an SRT contains (only) pointers to (top-level) closures.

* Consider this Core code
	f = \x -> let g = \y -> ...x...y...h1...
                  in ...h2...g...
  and suppose that h1, h2 have IdInfo of MayHaveCafRefs.
  Therefore, so will f,  But g will not (since it's nested).

  This generates C-- roughly like this:
     f_closure: .word f_entry
     f_entry() [info-tbl-for-f] { ...jump g_entry...jump h2... }
     g_entry() [info-tbl-for-g] { ...jump h1... }

  Note that there is no top-level closure for g (only an info table).
  This fact (whether or not there is a top-level closure) is recorded
  in the InfoTable attached to the CmmProc for f, g
  INVARIANT: 
     Any out-of-Group references to an IdLabel goes to
     a Proc whose InfoTable says "I have a top-level closure".
  Equivalently: 
     A CmmProc whose InfoTable says "I do not have a top-level
     closure" is referred to only from its own Group.

* So:   info-tbl-for-f must have an SRT that keeps h1,h2 alive
        info-tbl-for-g must have an SRT that keeps h1 (only) alive

  But if we just look for the free CAF refs, we get:
	f   h2 (only)
        g   h1

  So we need to do a transitive closure thing to flesh out 
  f's keep-alive refs to include h1.

* The SRT info is the C_SRT field of Cmm.ClosureTypeInfo in a
  CmmInfoTable attached to each CmmProc.  CmmCPSZ.toTops actually does
  the attaching, right at the end of the pipeline.  The C_SRT part
  gives offsets within a single, shared table of closure pointers.

* DECIDED: we can generate SRTs based on the final Cmm program
  without knowledge of how it is generated.

----------------------------------------------------
		Foreign calls
----------------------------------------------------

See Note [Foreign calls] in ZipCfgCmmRep!  This explains that a safe
foreign call must do this:
  save thread state
  push info table (on thread stack) to describe frame
  make call (via C stack)
  pop info table
  restore thread state
and explains why this expansion must be done late in the day.

Hence, 
  - Every foreign call is represented as a middle node

  - *Unsafe* foreign calls are simply "fat machine instructions"
      and are passed along to the native code generator

  - *Safe* foreign calls are "lowered" to unsafe calls by wrapping
      them in the above save/restore sequence. This step is done
      very late in the pipeline, just before handing to the native
      code gen.   
  
      This lowering is done by BuildInfoTables.lowerSafeForeignCalls


NEW PLAN for foreign calls:
  - Unsafe foreign calls remain as a middle node (fat machine instruction)
    Even the parameter passing is not lowered (just as machine instrs
    get arguments).

  - Initially, safe foreign calls appear as LastCalls with 
	

----------------------------------------------------
		Cmm representations
----------------------------------------------------

* Cmm.hs
     The type [GenCmm d h g] represents a whole module, 
	** one list element per .o file **
	Without SplitObjs, the list has exactly one element

     newtype GenCmm d h g = Cmm [GenCmmTop d h g]  -- A whole .o file
     data GenCmmTop d h g
         = CmmProc h g           -- One procedure, graph d
         | CmmData <stuff> [d]   -- Initialised data, items d

  Old and new piplines use different representations
  	(CmmCvt.hs converts between the two)


-------------
OLD BACK END representations (Cmm.hs):  
      type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)
				-- A whole module
      newtype ListGraph i = ListGraph [GenBasicBlock i]

      data CmmStmt = Assign | Store | Return etc -- OLD BACK END ONLY


   Once the info tables are laid out, we replace CmmInfo with [CmmStatic]
      type RawCmm    = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)
   which represents the info tables as data, that should 
   immediately precede the code
  
-------------
NEW BACK END representations 
* Not Cmm-specific at all
    ZipCfg.hs defines  Graph, LGraph, FGraph,
                       ZHead, ZTail, ZBlock ...

              classes  LastNode, HavingSuccessors

    MkZipCfg.hs: AGraph: building graphs

* ZipCfgCmmRep: instantiates ZipCfg for Cmm
      data Middle = ...CmmExpr...
      data Last = ...CmmExpr...
      type CmmGraph = Graph Middle Last

      type CmmZ = GenCmm CmmStatic CmmInfo (CmmStackInfo, CmmGraph)
      type CmmStackInfo = (ByteOff, Maybe ByteOff)
                -- (SP offset on entry, update frame space = SP offset on exit)
		-- The new codegen produces CmmZ, but once the stack is 
		-- manifested we can drop that in favour of 
		--    GenCmm CmmStatic CmmInfo CmmGraph

      Inside a CmmProc:
	   - CLabel: used
	   - CmmInfo: partly used by NEW
           - CmmFormals: not used at all  PERHAPS NOT EVEN BY OLD PIPELINE!

* MkZipCfgCmm.hs: smart constructors for ZipCfgCmmRep
   Depends on (a) MkZipCfg (Cmm-independent)
   	      (b) ZipCfgCmmRep (Cmm-specific)

-------------
* SHARED stuff
  CmmExpr.hs defines the Cmm expression types
	- CmmExpr, CmmReg, Width, CmmLit, LocalReg, GlobalReg
	- CmmType, Width etc   (saparate module?)
	- MachOp               (separate module?)
	- Area, AreaId etc     (separate module?)

  BlockId.hs defines  BlockId, BlockEnv, BlockSet

-------------


-------------
* Transactions indicate whether or not the result changes: CmmTx 
     type Tx a = a -> TxRes a
     data TxRes a = TxRes ChangeFlag a