3 * Kill dead code assignArguments, argumentsSize in CmmCallConv.
\r
4 Bake in ByteOff to ParamLocation and ArgumentFormat
\r
5 CmmActuals -> [CmmActual] similary CmmFormals
\r
7 * Possible refactoring: Nuke AGraph in favour of
\r
8 mkIfThenElse :: Expr -> Graph -> Graph -> FCode Graph
\r
10 mkIfThenElse :: HasUniques m => Expr -> Graph -> Graph -> m Graph
\r
11 (Remmber that the .cmm file parser must use this function)
\r
13 or parameterise FCode over its envt; the CgState part seem useful for both
\r
15 * Move top and tail calls to runCmmContFlowOpts from HscMain to CmmCps.cpsTop
\r
16 (and rename the latter!)
\r
18 * "Remove redundant reloads" in CmmSpillReload should be redundant; since
\r
19 insertLateReloads is now gone, every reload is reloading a live variable.
\r
22 * Sink and inline S(RegSlot(x)) = e in precisely the same way that we
\r
23 sink and inline x = e
\r
25 * Stack layout is very like register assignment: find non-conflicting assigments.
\r
26 In particular we can use colouring or linear scan (etc).
\r
28 We'd fine-grain interference (on a word by word basis) to get maximum overlap.
\r
29 But that may make very big interference graphs. So linear scan might be
\r
32 NB: linear scan does on-the-fly live range splitting.
\r
34 * When stubbing dead slots be careful not to write into an area that
\r
35 overlaps with an area that's in use. So stubbing needs to *follow*
\r
41 In CmmNode, consider spliting CmmCall into two: call and jump
\r
43 Notes on new codegen (Aug 10)
\r
44 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\r
47 - We insert spills for variables before the stack check! This is the reason for
\r
48 some fishy code in StgCmmHeap.entryHeapCheck where we are doing some strange
\r
49 things to fix up the stack pointer before GC calls/jumps.
\r
51 The reason spills are inserted before the sp check is that at the entry to a
\r
52 function we always store the parameters passed in registers to local variables.
\r
53 The spill pass simply inserts spills at variable definitions. We instead should
\r
54 sink the spills so that we can avoid spilling them on branches that never
\r
57 This will fix the spill before stack check problem but only really as a side
\r
58 effect. A 'real fix' probably requires making the spiller know about sp checks.
\r
60 EZY: I don't understand this comment. David Terei, can you clarify?
\r
62 - Proc points pass all arguments on the stack, adding more code and
\r
63 slowing down things a lot. We either need to fix this or even better
\r
64 would be to get rid of proc points.
\r
66 - CmmInfo.cmmToRawCmm uses Old.Cmm, so it is called after converting Cmm.Cmm to
\r
67 Old.Cmm. We should abstract it to work on both representations, it needs only to
\r
68 convert a CmmInfoTable to [CmmStatic].
\r
70 - The MkGraph currenty uses a different semantics for <*> than Hoopl. Maybe
\r
71 we could convert codeGen/StgCmm* clients to the Hoopl's semantics?
\r
72 It's all deeply unsatisfactory.
\r
74 - Improve performance of Hoopl.
\r
76 A nofib comparison of -fasm vs -fnewcodegen nofib compilation parameters
\r
77 (using the same ghc-cmm branch +libraries compiled by the old codegenerator)
\r
78 is at http://fox.auryn.cz/msrc/0517_hoopl/32bit.oldghcoldgen.oldghchoopl.txt
\r
79 - the code produced is 10.9% slower, the compilation is +118% slower!
\r
81 The same comparison with ghc-head with zip representation is at
\r
82 http://fox.auryn.cz/msrc/0517_hoopl/32bit.oldghcoldgen.oldghczip.txt
\r
83 - the code produced is 11.7% slower, the compilation is +78% slower.
\r
85 When compiling nofib, ghc-cmm + libraries compiled with -fnew-codegen
\r
86 is 23.7% slower (http://fox.auryn.cz/msrc/0517_hoopl/32bit.oldghcoldgen.hooplghcoldgen.txt).
\r
87 When compiling nofib, ghc-head + libraries compiled with -fnew-codegen
\r
88 is 31.4% slower (http://fox.auryn.cz/msrc/0517_hoopl/32bit.oldghcoldgen.zipghcoldgen.txt).
\r
90 So we generate a bit better code, but it takes us longer!
\r
92 EZY: Also importantly, Hoopl uses dramatically more memory than the
\r
95 - Are all blockToNodeList and blockOfNodeList really needed? Maybe we could
\r
96 splice blocks instead?
\r
98 In the CmmContFlowOpt.blockConcat, using Dataflow seems too clumsy. Still,
\r
99 a block catenation function would be probably nicer than blockToNodeList
\r
100 / blockOfNodeList combo.
\r
102 - lowerSafeForeignCall seems too lowlevel. Just use Dataflow. After that
\r
103 delete splitEntrySeq from HooplUtils.
\r
105 - manifestSP seems to touch a lot of the graph representation. It is
\r
106 also slow for CmmSwitch nodes O(block_nodes * switch_statements).
\r
107 Maybe rewrite manifestSP to use Dataflow?
\r
109 - Sort out Label, LabelMap, LabelSet versus BlockId, BlockEnv, BlockSet
\r
110 dichotomy. Mostly this means global replace, but we also need to make
\r
111 Label an instance of Outputable (probably in the Outputable module).
\r
113 - NB that CmmProcPoint line 283 has a hack that works around a GADT-related
\r
116 - SDM (2010-02-26) can we remove the Foreign constructor from Convention?
\r
117 Reason: we never generate code for a function with the Foreign
\r
118 calling convention, and the code for calling foreign calls is generated
\r
120 - AsmCodeGen has a generic Cmm optimiser; move this into new pipeline
\r
121 EZY (2011-04-16): The mini-inliner has been generalized and ported,
\r
122 but the constant folding and other optimizations need to still be
\r
125 - AsmCodeGen has post-native-cg branch eliminator (shortCutBranches);
\r
126 we ultimately want to share this with the Cmm branch eliminator.
\r
128 - At the moment, references to global registers like Hp are "lowered"
\r
129 late (in CgUtils.fixStgRegisters). We should do this early, in the
\r
130 new native codegen, much in the way that we lower calling conventions.
\r
131 Might need to be a bit sophisticated about aliasing.
\r
133 - Question: currently we lift procpoints to become separate
\r
134 CmmProcs. Do we still want to do this?
\r
136 NB: and advantage of continuing to do this is that
\r
137 we can do common-proc elimination!
\r
139 - Move to new Cmm rep:
\r
140 * Make native CG consume New Cmm;
\r
141 * Convert Old Cmm->New Cmm to keep old path alive
\r
142 * Produce New Cmm when reading in .cmm files
\r
144 - Consider module names
\r
146 - Top-level SRT threading is a bit ugly
\r
148 - Add type/newtype for CmmModule = [CmmGroup] -- A module
\r
149 CmmGroup = [CmmTop] -- A .o file
\r
150 CmmTop = Proc | Data -- A procedure or data
\r
152 - This is a *change*: currently a CmmGroup is one function's-worth of code
\r
153 regardless of SplitObjs. Question: can we *always* generate M.o if there
\r
154 is just one element in the list (rather than M/M1.o, M/M2.o etc)
\r
158 - See "CAFs" below; we want to totally refactor the way SRTs are calculated
\r
160 - Pull out Areas into its own module
\r
161 Parameterise AreaMap (note there are type synonyms in CmmStackLayout!)
\r
162 Add ByteWidth = Int
\r
163 type SubArea = (Area, ByteOff, ByteWidth)
\r
164 ByteOff should not be defined in SMRep -- that is too high up the hierarchy
\r
166 - SMRep should not be imported by any module in cmm/! Make it so.
\r
167 -- ByteOff etc ==> CmmExpr
\r
168 -- rET_SMALL etc ==> CmmInfo
\r
169 Check that there are no other imports from codeGen in cmm/
\r
171 - If you eliminate a label by branch chain elimination,
\r
172 what happens if there's an Area associated with that label?
\r
174 - Think about a non-flattened representation?
\r
177 * Use record fields for LastCall!
\r
178 * cml_ret_off should be a ByteOff
\r
180 LastCall (which has a successor) and
\r
181 LastJump (which does not, includes return?)
\r
182 - does not have cml_cont, cml_ret_args, cml_ret_off
\r
185 - expands into save/MidForeignCall/restore/goto
\r
186 - like any LastCall, target of the call gets an info table
\r
188 - JD: remind self of what goes wrong if you turn off the
\r
189 liveness of the update frame
\r
191 - Garbage-collect http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/CPS
\r
192 moving good stuff into
\r
193 http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/NewCodeGenPipeline
\r
196 - We believe that all of CmmProcPoint.addProcPointProtocols is dead. What
\r
197 goes wrong if we simply never call it?
\r
199 - Something fishy in CmmStackLayout.hs
\r
200 * In particular, 'getAreaSize' returns an AreaMap, but we *know* the width of
\r
201 LocalRegs, so it'd be better to return FiniteMap AreaId ByteWidth
\r
202 * setSuccSPs looks fishy. Rather than lookin in procPoints, it could
\r
203 just lookup the block in areaSize which, after all, has a binding
\r
204 for precisely successors of calls. All other blocks (including proc
\r
205 points that are not successors of a call, we think) can be treated
\r
206 uniformly: zero-size Area, and use inSP.
\r
209 - Currently AsmCodeGen top level calls AsmCodeGen.cmmToCmm, which is a small
\r
210 C-- optimiser. It has quite a lot of boilerplate folding code in AsmCodeGen
\r
211 (cmmBlockConFold, cmmStmtConFold, cmmExprConFold), before calling out to
\r
212 CmmOpt. ToDo: see what optimisations are being done; and do them before
\r
215 - Modularise the CPS pipeline; instead of ...; A;B;C; ...
\r
218 - Most of HscMain.tryNewCodeGen does not belong in HscMain. Instead
\r
221 processCmm [including generating "raw" cmm]
\r
227 - If we stick CAF and stack liveness info on a LastCall node (not LastRet/Jump)
\r
228 then all CAF and stack liveness stuff be completed before we split
\r
229 into separate C procedures.
\r
232 compute and attach liveness into to LastCall
\r
233 right at end, split, cvt to old rep
\r
234 [must split before cvt, because old rep is not expressive enough]
\r
237 when old rep disappears,
\r
238 move the whole splitting game into the C back end *only*
\r
239 (guided by the procpoint set)
\r
241 ----------------------------------------------------
\r
243 ----------------------------------------------------
\r
245 -------- Testing stuff ------------
\r
246 HscMain.optionallyConvertAndOrCPS
\r
248 DynFlags: -fconvert-to-zipper-and-back, -frun-cpsz
\r
250 -------- Moribund stuff ------------
\r
251 OldCmm.hs Definition of flowgraph of old representation
\r
252 OldCmmUtil.hs Utilites that operates mostly on on CmmStmt
\r
253 OldPprCmm.hs Pretty print for CmmStmt, GenBasicBlock and ListGraph
\r
254 CmmCvt.hs Conversion between old and new Cmm reps
\r
255 CmmOpt.hs Hopefully-redundant optimiser
\r
257 -------- Stuff to keep ------------
\r
258 CmmCPS.hs Driver for new pipeline
\r
260 CmmLive.hs Liveness analysis, dead code elim
\r
261 CmmProcPoint.hs Identifying and splitting out proc-points
\r
263 CmmSpillReload.hs Save and restore across calls
\r
265 CmmCommonBlockElim.hs Common block elim
\r
266 CmmContFlowOpt.hs Other optimisations (branch-chain, merging)
\r
268 CmmBuildInfoTables.hs New info-table
\r
269 CmmStackLayout.hs and stack layout
\r
271 CmmInfo.hs Defn of InfoTables, and conversion to exact byte layout
\r
273 ---------- Cmm data types --------------
\r
274 Cmm.hs Cmm instantiations of dataflow graph framework
\r
275 MkGraph.hs Interface for building Cmm for codeGen/Stg*.hs modules
\r
277 CmmDecl.hs Shared Cmm types of both representations
\r
278 CmmExpr.hs Type of Cmm expression
\r
279 CmmType.hs Type of Cmm types and their widths
\r
280 CmmMachOp.hs MachOp type and accompanying utilities
\r
285 PprC.hs Pretty print Cmm in C syntax
\r
286 PprCmm.hs Pretty printer for CmmGraph.
\r
287 PprCmmDecl.hs Pretty printer for common Cmm types.
\r
288 PprCmmExpr.hs Pretty printer for Cmm expressions.
\r
291 BlockId.hs BlockId, BlockEnv, BlockSet
\r
293 ----------------------------------------------------
\r
294 Top-level structure
\r
295 ----------------------------------------------------
\r
297 * New codgen called in HscMain.hscGenHardCode, by calling HscMain.tryNewCodeGen,
\r
298 enabled by -fnew-codegen (Opt_TryNewCodeGen)
\r
300 THEN it calls CmmInfo.cmmToRawCmm to lay out the details of info tables
\r
301 type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)
\r
302 type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)
\r
304 * HscMain.tryNewCodeGen
\r
305 - STG->Cmm: StgCmm.codeGen (new codegen)
\r
306 - Optimise: CmmContFlowOpt (simple optimisations, very self contained)
\r
307 - Cps convert: CmmCPS.protoCmmCPS
\r
308 - Optimise: CmmContFlowOpt again
\r
309 - Convert: CmmCvt.cmmOfZgraph (convert to old rep) very self contained
\r
311 * StgCmm.hs The new STG -> Cmm conversion code generator
\r
312 Lots of modules StgCmmXXX
\r
315 ----------------------------------------------------
\r
316 CmmCPS.protoCmmCPS The new pipeline
\r
317 ----------------------------------------------------
\r
319 CmmCPS.protoCmmCPS:
\r
320 1. Do cpsTop for each procedures separately
\r
321 2. Build SRT representation; this spans multiple procedures
\r
322 (unless split-objs)
\r
325 * CmmCommonBlockElim.elimCommonBlocks:
\r
326 eliminate common blocks
\r
328 * CmmProcPoint.minimalProcPointSet
\r
329 identify proc-points
\r
332 * CmmProcPoint.addProcPointProtocols
\r
333 something to do with the MA optimisation
\r
334 probably entirely unnecessary
\r
336 * Spill and reload:
\r
337 - CmmSpillReload.dualLivenessWithInsertion
\r
338 insert spills/reloads across
\r
340 Branches to proc-points
\r
341 Now sink those reloads (and other instructions):
\r
342 - CmmSpillReload.rewriteAssignments
\r
343 - CmmSpillReload.removeDeadAssignmentsAndReloads
\r
345 * CmmStackLayout.stubSlotsOnDeath
\r
346 debug only: zero out dead slots when they die
\r
349 - CmmStackLayout.lifeSlotAnal:
\r
350 find which sub-areas are live on entry to each block
\r
352 - CmmStackLayout.layout
\r
353 Lay out the stack, returning an AreaMap
\r
354 type AreaMap = FiniteMap Area ByteOff
\r
355 -- Byte offset of the oldest byte of the Area,
\r
356 -- relative to the oldest byte of the Old Area
\r
358 - CmmStackLayout.manifestSP
\r
359 Manifest the stack pointer
\r
361 * Split into separate procedures
\r
362 - CmmProcPoint.procPointAnalysis
\r
363 Given set of proc points, which blocks are reachable from each
\r
364 Claim: too few proc-points => code duplication, but program still works??
\r
366 - CmmProcPoint.splitAtProcPoints
\r
367 Using this info, split into separate procedures
\r
369 - CmmBuildInfoTables.setInfoTableStackMap
\r
370 Attach stack maps to each info table
\r
373 ----------------------------------------------------
\r
375 ----------------------------------------------------
\r
377 Consider this program, which has a diamond control flow,
\r
378 with a call on one branch
\r
381 if b then { ... f(x) ...; q=5; goto J }
\r
382 else { ...; q=7; goto J }
\r
385 then the join point J is a "proc-point". So, is 'p' passed to J
\r
386 as a parameter? Or, if 'p' was saved on the stack anyway, perhaps
\r
387 to keep it alive across the call to h(), maybe 'p' gets communicated
\r
388 to J that way. This is an awkward choice. (We think that we currently
\r
389 never pass variables to join points via arguments.)
\r
391 Furthermore, there is *no way* to pass q to J in a register (other
\r
392 than a parameter register).
\r
394 What we want is to do register allocation across the whole caboodle.
\r
395 Then we could drop all the code that deals with the above awkward
\r
396 decisions about spilling variables across proc-points.
\r
398 Note that J doesn't need an info table.
\r
400 What we really want is for each LastCall (not LastJump/Ret)
\r
401 to have an info table. Note that ProcPoints that are not successors
\r
402 of calls don't need an info table.
\r
404 Figuring out proc-points
\r
405 ~~~~~~~~~~~~~~~~~~~~~~~~
\r
406 Proc-points are identified by
\r
407 CmmProcPoint.minimalProcPointSet/extendPPSet Although there isn't
\r
408 that much code, JD thinks that it could be done much more nicely using
\r
409 a dominator analysis, using the Dataflow Engine.
\r
411 ----------------------------------------------------
\r
413 ----------------------------------------------------
\r
415 * The code for a procedure f may refer to either the *closure*
\r
416 or the *entry point* of another top-level procedure g.
\r
417 If f is live, then so is g. f's SRT must include g's closure.
\r
419 * The CLabel for the entry-point/closure reveals whether g is
\r
420 a CAF (or refers to CAFs). See the IdLabel constructor of CLabel.
\r
422 * The CAF-ness of the original top-level defininions is figured out
\r
423 (by TidyPgm) before we generate C--. This CafInfo is only set for
\r
424 top-level Ids; nested bindings stay with MayHaveCafRefs.
\r
426 * Currently an SRT contains (only) pointers to (top-level) closures.
\r
428 * Consider this Core code
\r
429 f = \x -> let g = \y -> ...x...y...h1...
\r
431 and suppose that h1, h2 have IdInfo of MayHaveCafRefs.
\r
432 Therefore, so will f, But g will not (since it's nested).
\r
434 This generates C-- roughly like this:
\r
435 f_closure: .word f_entry
\r
436 f_entry() [info-tbl-for-f] { ...jump g_entry...jump h2... }
\r
437 g_entry() [info-tbl-for-g] { ...jump h1... }
\r
439 Note that there is no top-level closure for g (only an info table).
\r
440 This fact (whether or not there is a top-level closure) is recorded
\r
441 in the InfoTable attached to the CmmProc for f, g
\r
443 Any out-of-Group references to an IdLabel goes to
\r
444 a Proc whose InfoTable says "I have a top-level closure".
\r
446 A CmmProc whose InfoTable says "I do not have a top-level
\r
447 closure" is referred to only from its own Group.
\r
449 * So: info-tbl-for-f must have an SRT that keeps h1,h2 alive
\r
450 info-tbl-for-g must have an SRT that keeps h1 (only) alive
\r
452 But if we just look for the free CAF refs, we get:
\r
456 So we need to do a transitive closure thing to flesh out
\r
457 f's keep-alive refs to include h1.
\r
459 * The SRT info is the C_SRT field of Cmm.ClosureTypeInfo in a
\r
460 CmmInfoTable attached to each CmmProc. CmmCPS.toTops actually does
\r
461 the attaching, right at the end of the pipeline. The C_SRT part
\r
462 gives offsets within a single, shared table of closure pointers.
\r
464 * DECIDED: we can generate SRTs based on the final Cmm program
\r
465 without knowledge of how it is generated.
\r
467 ----------------------------------------------------
\r
469 ----------------------------------------------------
\r
471 See Note [Foreign calls] in CmmNode! This explains that a safe
\r
472 foreign call must do this:
\r
474 push info table (on thread stack) to describe frame
\r
475 make call (via C stack)
\r
477 restore thread state
\r
478 and explains why this expansion must be done late in the day.
\r
481 - Every foreign call is represented as a middle node
\r
483 - *Unsafe* foreign calls are simply "fat machine instructions"
\r
484 and are passed along to the native code generator
\r
486 - *Safe* foreign calls are "lowered" to unsafe calls by wrapping
\r
487 them in the above save/restore sequence. This step is done
\r
488 very late in the pipeline, just before handing to the native
\r
491 This lowering is done by BuildInfoTables.lowerSafeForeignCalls
\r
494 NEW PLAN for foreign calls:
\r
495 - Unsafe foreign calls remain as a middle node (fat machine instruction)
\r
496 Even the parameter passing is not lowered (just as machine instrs
\r
499 - Initially, safe foreign calls appear as LastCalls with
\r
502 ----------------------------------------------------
\r
503 Cmm representations
\r
504 ----------------------------------------------------
\r
507 The type [GenCmm d h g] represents a whole module,
\r
508 ** one list element per .o file **
\r
509 Without SplitObjs, the list has exactly one element
\r
511 newtype GenCmm d h g = Cmm [GenCmmTop d h g] -- A whole .o file
\r
512 data GenCmmTop d h g
\r
513 = CmmProc h g -- One procedure, graph d
\r
514 | CmmData <stuff> [d] -- Initialised data, items d
\r
516 Old and new piplines use different representations
\r
517 (CmmCvt.hs converts between the two)
\r
521 OLD BACK END representations (OldCmm.hs):
\r
522 type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)
\r
524 newtype ListGraph i = ListGraph [GenBasicBlock i]
\r
526 data CmmStmt = Assign | Store | Return etc -- OLD BACK END ONLY
\r
529 Once the info tables are laid out, we replace CmmInfo with [CmmStatic]
\r
530 type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)
\r
531 which represents the info tables as data, that should
\r
532 immediately precede the code
\r
535 NEW BACK END representations
\r
536 * Uses Hoopl library, a zero-boot package
\r
537 * CmmNode defines a node of a flow graph.
\r
538 * Cmm defines CmmGraph, CmmTop, Cmm
\r
539 - CmmGraph is a closed/closed graph + an entry node.
\r
541 data CmmGraph = CmmGraph { g_entry :: BlockId
\r
542 , g_graph :: Graph CmmNode C C }
\r
544 - CmmTop is a top level chunk, specialization of GenCmmTop from CmmDecl.hs
\r
545 with CmmGraph as a flow graph.
\r
546 - Cmm is a collection of CmmTops.
\r
548 type Cmm = GenCmm CmmStatic CmmTopInfo CmmGraph
\r
549 type CmmTop = GenCmmTop CmmStatic CmmTopInfo CmmGraph
\r
551 - CmmTop uses CmmTopInfo, which is a CmmInfoTable and CmmStackInfo
\r
553 data CmmTopInfo = TopInfo {info_tbl :: CmmInfoTable, stack_info :: CmmStackInfo}
\r
557 data CmmStackInfo = StackInfo {arg_space :: ByteOff, updfr_space :: Maybe ByteOff}
\r
559 * arg_space = SP offset on entry
\r
560 * updfr_space space = SP offset on exit
\r
561 Once the staci is manifested, we could drom CmmStackInfo, ie. get
\r
562 GenCmm CmmStatic CmmInfoTable CmmGraph, but we do not do that currently.
\r
565 * MkGraph.hs: smart constructors for Cmm.hs
\r
566 Beware, the CmmAGraph defined here does not use AGraph from Hoopl,
\r
567 as CmmAGraph can be opened or closed at exit, See the notes in that module.
\r
571 CmmDecl.hs - GenCmm and GenCmmTop types
\r
572 CmmExpr.hs - defines the Cmm expression types
\r
573 - CmmExpr, CmmReg, CmmLit, LocalReg, GlobalReg
\r
574 - Area, AreaId etc (separate module?)
\r
575 CmmType.hs - CmmType, Width etc (saparate module?)
\r
576 CmmMachOp.hs - MachOp and CallishMachOp types
\r
578 BlockId.hs defines BlockId, BlockEnv, BlockSet
\r