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