+Notes on new codegen (Sept 09)\r
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\r
+\r
+Things to do:\r
+ - Top-level SRT threading is a bit ugly\r
+\r
+ - Add type/newtype for CmmModule = [CmmGroup] -- A module\r
+ CmmGroup = [CmmTop] -- A .o file\r
+ CmmTop = Proc | Data -- A procedure or data\r
+\r
+ - This is a *change*: currently a CmmGroup is one function's-worth of code\r
+ regardless of SplitObjs. Question: can we *always* generate M.o if there\r
+ is just one element in the list (rather than M/M1.o, M/M2.o etc)\r
+\r
+ - Change \r
+ type CmmZ = GenCmm CmmStatic CmmInfo (CmmStackInfo, CmmGraph)\r
+ to\r
+ type CmmZ = GenCmm CmmStatic (CmmInfo, CmmStackInfo) CmmGraph\r
+ -- And perhaps take opportunity to prune CmmInfo?\r
+\r
+ - Clarify which fields of CmmInfo are still used\r
+ - Maybe get rid of CmmFormals arg of CmmProc in all versions?\r
+\r
+ - We aren't sure whether cmmToRawCmm is actively used by the new pipeline; check\r
+ And what does CmmBuildInfoTables do?!\r
+\r
+ - Nuke CmmZipUtil, move zipPreds into ZipCfg\r
+\r
+ - Pull out Areas into its own module\r
+ Parameterise AreaMap\r
+ Add ByteWidth = Int\r
+ type SubArea = (Area, ByteOff, ByteWidth) \r
+ ByteOff should not be defined in SMRep -- that is too high up the hierarchy\r
+ \r
+ - Think about a non-flattened representation?\r
+\r
+ - LastCall: \r
+ * Use record fields for LastCall!\r
+ * cml_ret_off should be a ByteOff\r
+ * Split into \r
+ LastCall (which has a successor) and\r
+ LastJump (which does not, includes return?)\r
+ - does not have cml_cont, cml_ret_args, cml_ret_off\r
+ LastForeignCall \r
+ - safe! \r
+ - expands into save/MidForeignCall/restore/goto\r
+ - like any LastCall, target of the call gets an info table\r
+\r
+ - JD: remind self of what goes wrong if you turn off the \r
+ liveness of the update frame\r
+\r
+ - Garbage-collect http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/CPS\r
+ moving good stuff into \r
+ http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/NewCodeGenPipeline\r
+\r
+\r
+ - We believe that all of CmmProcPointZ.addProcPointProtocols is dead. What\r
+ goes wrong if we simply never call it?\r
+\r
+ - Something fishy in CmmStackLayout.hs\r
+ * In particular, 'getAreaSize' returns an AreaMap, but we *know* the width of\r
+ LocalRegs, so it'd be better to return FiniteMap AreaId ByteWidth\r
+ * setSuccSPs looks fishy. Rather than lookin in procPoints, it could\r
+ just lookup the block in areaSize which, after all, has a binding\r
+ for precisely successors of calls. All other blocks (including proc\r
+ points that are not successors of a call, we think) can be treated\r
+ uniformly: zero-size Area, and use inSP.\r
+\r
+Dead files\r
+~~~~~~~~~~\r
+CmmProcPoint (Michael Adams)\r
+CmmCPS (ditto)\r
+HscMain.optionallyConvertAndOrCPS\r
+ testCmmConversion\r
+DynFlags: -fconvert-to-zipper-and-back, -frun-cps, -frun-cpsz\r
+\r
+Proc-points\r
+~~~~~~~~~~~~\r
+Consider this program, which has a diamond control flow, \r
+with a call on one branch\r
+ fn(p,x) {\r
+ h()\r
+ if b then { ... f(x) ...; q=5; goto J }\r
+ else { ...; q=7; goto J }\r
+ J: ..p...q...\r
+ }\r
+then the join point J is a "proc-point". So, is 'p' passed to J\r
+as a parameter? Or, if 'p' was saved on the stack anyway, perhaps\r
+to keep it alive across the call to h(), maybe 'p' gets communicated\r
+to J that way. This is an awkward choice. (We think that we currently\r
+never pass variables to join points via arguments.)\r
+\r
+Furthermore, there is *no way* to pass q to J in a register (other\r
+than a paramter register).\r
+\r
+What we want is to do register allocation across the whole caboodle.\r
+Then we could drop all the code that deals with the above awkward\r
+decisions about spilling variables across proc-points.\r
+\r
+Note that J doesn't need an info table.\r
+\r
+What we really want is for each Block to have an optional info table.\r
+To do that, we need to be polymorphic over first nodes.\r
+\r
+Figuring out proc-points\r
+~~~~~~~~~~~~~~~~~~~~~~~~\r
+Proc-points are identified by\r
+CmmProcPointZ.minimalProcPointSet/extendPPSet Although there isn't\r
+that much code, JD thinks that it could be done much more nicely using\r
+a dominator analysis, using the Dataflow Engine.\r
+\r
+----------------------------------------------------\r
+ Top-level structure\r
+----------------------------------------------------\r
+\r
+* New codgen called in HscMain.hscGenHardCode, by calling HscMain.tryNewCodeGen, \r
+ enabled by -fnew-codegen (Opt_TryNewCodeGen)\r
+\r
+ THEN it calls CmmInfo.cmmToRawCmm to lay out the details of info tables\r
+ type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)\r
+ type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)\r
+\r
+* HscMain.tryNewCodeGen\r
+ - STG->Cmm: StgCmm.codeGen (new codegen)\r
+ - Optimise: CmmContFlowOpt (simple optimisations, very self contained)\r
+ - Cps convert: CmmCPSZ.protoCmmCPSZ \r
+ - Optimise: CmmContFlowOpt again\r
+ - Convert: CmmCvt.cmmOfZgraph (convert to old rep) very self contained\r
+\r
+* StgCmm.hs The new STG -> Cmm conversion code generator\r
+ Lots of modules StgCmmXXX\r
+\r
+\r
+----------------------------------------------------\r
+ CmmCPSZ.protoCmmCPSZ The new pipeline\r
+----------------------------------------------------\r
+\r
+CmmCPSZprotoCmmCPSZ:\r
+ 1. Do cpsTop for each procedures separately\r
+ 2. Build SRT representation; this spans multiple procedures\r
+ (unless split-objs)\r
+\r
+cpsTop:\r
+ * CmmCommonBlockElimZ.elimCommonBlocks:\r
+ eliminate common blocks \r
+\r
+ * CmmProcPointZ.minimalProcPointSet\r
+ identify proc-points\r
+\r
+ * CmmProcPointZ.addProcPointProtocols\r
+ something to do with the MA optimisation\r
+ probably entirely unnecessary\r
+\r
+\r
+ * Spill and reload:\r
+ - CmmSpillReload.dualLivenessWithInsertion\r
+ insert spills/reloads across \r
+ LastCalls, and \r
+ Branches to proc-points\r
+ Now sink those reloads:\r
+ - CmmSpillReload.insertLateReloads\r
+ - CmmSpillReload.removeDeadAssignmentsAndReloads\r
+\r
+ * CmmStackLayout.stubSlotsOnDeath\r
+ debug only: zero out dead slots when they die\r
+\r
+ * Stack layout\r
+ - CmmStackLayout.lifeSlotAnal: \r
+ find which sub-areas are live on entry to each block\r
+\r
+ - CmmStackLayout.layout\r
+ Lay out the stack, returning an AreaMap\r
+ type AreaMap = FiniteMap Area ByteOff\r
+ -- Byte offset of the oldest byte of the Area, \r
+ -- relative to the oldest byte of the Old Area\r
+\r
+ - CmmStackLayout.manifestSP\r
+ Manifest the stack pointer\r
+\r
+ * Split into separate procedures\r
+ - CmmProcPointZ.procPointAnalysis\r
+ Given set of proc points, which blocks are reachable from each\r
+\r
+ - CmmProcPointZ.splitAtProcPoints\r
+ Using this info, split into separate procedures\r
+\r
+----------------------------------------------------\r
+ CAFs\r
+----------------------------------------------------\r
+\r
+* The code for a procedure f may refer to either the *closure* \r
+ or the *entry point* of another top-level procedure g. \r
+ If f is live, then so is g. f's SRT must include g's closure.\r
+\r
+* The CLabel for the entry-point/closure reveals whether g is \r
+ a CAF (or refers to CAFs). See the IdLabell constructor of CLabel.\r
+\r
+* The CAF-ness of the original top-level defininions is figured out\r
+ (by TidyPgm) before we generate C--. This CafInfo is only set for\r
+ top-level Ids; nested bindings stay with NoCafRefs.\r
+\r
+* Currently an SRT contains (only) pointers to (top-level) closures.\r
+\r
+* Consider this Core code\r
+ f = \x -> let g = \y -> ...x...y...h1...\r
+ in ...h2...g...\r
+ and suppose that h1, h2 have IdInfo of MayHaveCafRefs.\r
+ Therefore, so will f, But g will not (since it's nested).\r
+\r
+ This generates C-- roughly like this:\r
+ f_closure: .word f_entry\r
+ f_entry() [info-tbl-for-f] { ...jump g_entry...jump h2... }\r
+ g_entry() [info-tbl-for-g] { ...jump h1 }\r
+\r
+ Note that there is no top-level closure for g (only an info table).\r
+ So: info-tbl-for-f must have an SRT that keeps h1,h2 alive\r
+ info-tbl-for-g must have an SRT that keeps h1 (only) alive\r
+\r
+ But if we just look for the free CAF refs, we get:\r
+ f h2 (only)\r
+ g h1\r
+\r
+ So we need to do a transitive closure thing to flesh out \r
+ f's keep-alive refs to include h1.\r
+\r
+* The SRT info is the C_SRT field of Cmm.ClosureTypeInfo in a\r
+ CmmInfoTable attached to each CmmProc. CmmCPSZ.toTops actually does\r
+ the attaching, right at the end of the pipeline. The C_SRT part\r
+ gives offsets within a single, shared table of closure pointers.\r
+\r
+----------------------------------------------------\r
+ Foreign calls\r
+----------------------------------------------------\r
+\r
+See Note [Foreign calls] in ZipCfgCmmRep! This explains that a safe\r
+foreign call must do this:\r
+ save thread state\r
+ push info table (on thread stack) to describe frame\r
+ make call (via C stack)\r
+ pop info table\r
+ restore thread state\r
+and explains why this expansion must be done late in the day.\r
+\r
+Hence, \r
+ - Every foreign call is represented as a middle node\r
+\r
+ - *Unsafe* foreign calls are simply "fat machine instructions"\r
+ and are passed along to the native code generator\r
+\r
+ - *Safe* foreign calls are "lowered" to unsafe calls by wrapping\r
+ them in the above save/restore sequence. This step is done\r
+ very late in the pipeline, just before handing to the native\r
+ code gen. \r
+ \r
+ This lowering is done by BuildInfoTables.lowerSafeForeignCalls\r
+\r
+\r
+NEW PLAN for foreign calls:\r
+ - Unsafe foreign calls remain as a middle node (fat machine instruction)\r
+ Even the parameter passing is not lowered (just as machine instrs\r
+ get arguments).\r
+\r
+ - Initially, safe foreign calls appear as LastCalls with \r
+ \r
+\r
+----------------------------------------------------\r
+ Cmm representations\r
+----------------------------------------------------\r
+\r
+* Cmm.hs\r
+ The type [GenCmm d h g] represents a whole module, \r
+ ** one list element per .o file **\r
+ Without SplitObjs, the list has exactly one element\r
+\r
+ newtype GenCmm d h g = Cmm [GenCmmTop d h g] -- A whole .o file\r
+ data GenCmmTop d h g\r
+ = CmmProc h g -- One procedure, graph d\r
+ | CmmData <stuff> [d] -- Initialised data, items d\r
+\r
+ Old and new piplines use different representations\r
+ (CmmCvt.hs converts between the two)\r
+\r
+\r
+-------------\r
+OLD BACK END representations (Cmm.hs): \r
+ type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)\r
+ -- A whole module\r
+ newtype ListGraph i = ListGraph [GenBasicBlock i]\r
+\r
+ data CmmStmt = Assign | Store | Return etc -- OLD BACK END ONLY\r
+\r
+\r
+ Once the info tables are laid out, we replace CmmInfo with [CmmStatic]\r
+ type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)\r
+ which represents the info tables as data, that should \r
+ immediately precede the code\r
+ \r
+-------------\r
+NEW BACK END representations \r
+* Not Cmm-specific at all\r
+ ZipCfg.hs defines Graph, LGraph, FGraph,\r
+ ZHead, ZTail, ZBlock ...\r
+\r
+ classes LastNode, HavingSuccessors\r
+\r
+ MkZipCfg.hs: AGraph: building graphs\r
+\r
+* ZipCfgCmmRep: instantiates ZipCfg for Cmm\r
+ data Middle = ...CmmExpr...\r
+ data Last = ...CmmExpr...\r
+ type CmmGraph = Graph Middle Last\r
+\r
+ type CmmZ = GenCmm CmmStatic CmmInfo (CmmStackInfo, CmmGraph)\r
+ type CmmStackInfo = (ByteOff, Maybe ByteOff)\r
+ -- (SP offset on entry, update frame space = SP offset on exit)\r
+ -- The new codegen produces CmmZ, but once the stack is \r
+ -- manifested we can drop that in favour of \r
+ -- GenCmm CmmStatic CmmInfo CmmGraph\r
+\r
+ Inside a CmmProc:\r
+ - CLabel: used\r
+ - CmmInfo: partly used by NEW\r
+ - CmmFormals: not used at all PERHAPS NOT EVEN BY OLD PIPELINE!\r
+\r
+* MkZipCfgCmm.hs: smart constructors for ZipCfgCmmRep\r
+ Depends on (a) MkZipCfg (Cmm-independent)\r
+ (b) ZipCfgCmmRep (Cmm-specific)\r
+\r
+-------------\r
+* SHARED stuff\r
+ CmmExpr.hs defines the Cmm expression types\r
+ - CmmExpr, CmmReg, Width, CmmLit, LocalReg, GlobalReg\r
+ - CmmType, Width etc (saparate module?)\r
+ - MachOp (separate module?)\r
+ - Area, AreaId etc (separate module?)\r
+\r
+ BlockId.hs defines BlockId, BlockEnv, BlockSet\r
+\r
+-------------\r
+\r
+\r
+-------------\r
+* Transactions indicate whether or not the result changes: CmmTx \r
+ type Tx a = a -> TxRes a\r
+ data TxRes a = TxRes ChangeFlag a\r
projects / ghc-hetmet.git / commitdiff