Add support for producing position-independent executables
[ghc.git] / compiler / cmm / cmm-notes
1 More notes (Aug 11)\r
2 ~~~~~~~~~~~~~~~~~~\r
3 * CmmInfo.cmmToRawCmm expands info tables to their representations\r
4   (needed for .cmm files as well as the code generators)\r
5 \r
6 * Why is FCode a lazy monad?  That makes it inefficient.\r
7   We want laziness to get code out one procedure at a time,\r
8   but not at the instruction level.\r
9   UPDATE (31/5/2016): FCode is strict since 09afcc9b.\r
10 \r
11 Things we did\r
12   * Remove CmmCvt.graphToZgraph (Conversion from old to new Cmm reps)\r
13   * Remove HscMain.optionallyConvertAndOrCPS (converted old Cmm to\r
14     new, ran pipeline, and converted back)\r
15   * Remove CmmDecl. Put its types in Cmm.  Import Cmm into OldCmm\r
16     so it can get those types.\r
17 \r
18 \r
19 More notes (June 11)\r
20 ~~~~~~~~~~~~~~~~~~~~\r
21 \r
22 * In CmmContFlowOpts.branchChainElim, can a single block be the\r
23   successor of two calls?\r
24 \r
25 * Check in ClosureInfo:\r
26      -- NB: Results here should line up with the results of SMRep.rtsClosureType\r
27 \r
28 More notes (May 11)\r
29 ~~~~~~~~~~~~~~~~~~~\r
30 In CmmNode, consider spliting CmmCall into two: call and jump\r
31 \r
32 Notes on new codegen (Aug 10)\r
33 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\r
34 \r
35 Things to do:\r
36  - Proc points pass all arguments on the stack, adding more code and\r
37    slowing down things a lot. We either need to fix this or even better\r
38    would be to get rid of proc points.\r
39 \r
40  - Sort out Label, LabelMap, LabelSet versus BlockId, BlockEnv, BlockSet\r
41    dichotomy. Mostly this means global replace, but we also need to make\r
42    Label an instance of Outputable (probably in the Outputable module).\r
43 \r
44    EZY: We should use Label, since that's the terminology Hoopl uses.\r
45 \r
46  - AsmCodeGen has a generic Cmm optimiser; move this into new pipeline\r
47    EZY (2011-04-16): The mini-inliner has been generalized and ported,\r
48    but the constant folding and other optimizations need to still be\r
49    ported.\r
50 \r
51  - AsmCodeGen has post-native-cg branch eliminator (shortCutBranches);\r
52    we ultimately want to share this with the Cmm branch eliminator.\r
53 \r
54  - At the moment, references to global registers like Hp are "lowered" \r
55    late (in CgUtils.fixStgRegisters). We should do this early, in the\r
56         new native codegen, much in the way that we lower calling conventions.\r
57         Might need to be a bit sophisticated about aliasing.\r
58 \r
59  - Move to new Cmm rep:\r
60      * Make native CG consume New Cmm; \r
61      * Convert Old Cmm->New Cmm to keep old path alive\r
62      * Produce New Cmm when reading in .cmm files\r
63 \r
64  - Top-level SRT threading is a bit ugly\r
65 \r
66  - See "CAFs" below; we want to totally refactor the way SRTs are calculated\r
67 \r
68  - Garbage-collect http://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/CPS\r
69    moving good stuff into \r
70    http://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/NewCodeGenPipeline\r
71 \r
72  - Currently AsmCodeGen top level calls AsmCodeGen.cmmToCmm, which is a small\r
73    C-- optimiser.  It has quite a lot of boilerplate folding code in AsmCodeGen\r
74    (cmmBlockConFold, cmmStmtConFold, cmmExprConFold), before calling out to\r
75    CmmOpt.  ToDo: see what optimisations are being done; and do them before\r
76    AsmCodeGen.\r
77 \r
78  - If we stick CAF and stack liveness info on a LastCall node (not LastRet/Jump)\r
79    then all CAF and stack liveness stuff be completed before we split\r
80    into separate C procedures.\r
81 \r
82    Short term:\r
83      compute and attach liveness into LastCall\r
84      right at end, split, cvt to old rep\r
85      [must split before cvt, because old rep is not expressive enough]\r
86 \r
87    Longer term: \r
88      when old rep disappears, \r
89      move the whole splitting game into the C back end *only*\r
90          (guided by the procpoint set)\r
91 \r
92 ----------------------------------------------------\r
93         Modules in codeGen/\r
94 ----------------------------------------------------\r
95 \r
96 \r
97 ------- Shared ---------\r
98 Bitmap.hs\r
99 SMRep.lhs\r
100 \r
101 CmmParse.y\r
102 CgExtCode.hs   used in CmmParse.y\r
103 \r
104 ------- New codegen ---------\r
105 \r
106 StgCmm.hs\r
107 StgCmmBind.hs\r
108 StgCmmClosure.hs     (corresponds to old ClosureInfo)\r
109 StgCmmCon.hs\r
110 StgCmmEnv.hs\r
111 StgCmmExpr.hs\r
112 StgCmmForeign.hs\r
113 StgCmmHeap.hs\r
114 StgCmmHpc.hs\r
115 StgCmmLayout.hs\r
116 StgCmmMonad.hs\r
117 StgCmmPrim.hs\r
118 StgCmmProf.hs\r
119 StgCmmTicky.hs\r
120 StgCmmUtils.hs\r
121 \r
122 ------- Old codegen (moribund) ---------\r
123 CodeGen.lhs\r
124 CgBindery.lhs\r
125 CgCallConv.hs\r
126 CgCase.lhs\r
127 CgClosure.lhs\r
128 CgCon.lhs\r
129 CgExpr.lhs\r
130 CgLetNoEscape.lhs\r
131 CgForeignCall.hs\r
132 CgHeapery.lhs\r
133 CgHpc.hs\r
134 CgInfoTbls.hs\r
135 CgMonad.lhs\r
136 CgParallel.hs\r
137 CgPrimOp.hs\r
138 CgProf.hs\r
139 CgStackery.lhs\r
140 CgTailCall.lhs\r
141 CgTicky.hs\r
142 CgUtils.hs\r
143 ClosureInfo.lhs\r
144 \r
145 ----------------------------------------------------\r
146         Modules in cmm/\r
147 ----------------------------------------------------\r
148 \r
149 -------- Moribund stuff ------------\r
150 OldCmm.hs      Definition of flowgraph of old representation\r
151                Imports some data types from (new) Cmm\r
152 OldCmmUtil.hs  Utilites that operates mostly on on CmmStmt\r
153 OldPprCmm.hs   Pretty print for CmmStmt, GenBasicBlock and ListGraph\r
154 CmmOpt.hs      Hopefully-redundant optimiser\r
155 \r
156 -------- Stuff to keep ------------\r
157 CmmPipeline.hs            Driver for new pipeline\r
158 \r
159 CmmLive.hs                Liveness analysis, dead code elim\r
160 CmmProcPoint.hs           Identifying and splitting out proc-points\r
161 \r
162 CmmSpillReload.hs         Save and restore across calls\r
163 \r
164 CmmCommonBlockElim.hs     Common block elim\r
165 CmmContFlowOpt.hs         Other optimisations (branch-chain, merging)\r
166 \r
167 CmmBuildInfoTables.hs     New info-table \r
168 CmmStackLayout.hs         and stack layout \r
169 CmmCallConv.hs\r
170 CmmInfo.hs                Defn of InfoTables, and conversion to exact byte layout\r
171 \r
172 ---------- Cmm data types --------------\r
173 Cmm.hs              Cmm instantiations of dataflow graph framework\r
174   CmmExpr.hs        Type of Cmm expression\r
175   CmmType.hs        Type of Cmm types and their widths\r
176   CmmMachOp.hs      MachOp type and accompanying utilities\r
177 \r
178 PprCmm.hs           Pretty printer for Cmm\r
179   PprCmmExpr.hs     Pretty printer for CmmExpr\r
180 \r
181 MkGraph.hs          Interface for building Cmm for codeGen/Stg*.hs modules\r
182 \r
183 CmmUtils.hs\r
184 CmmLint.hs\r
185 \r
186 PprC.hs             Pretty print Cmm in C syntax\r
187 \r
188 CLabel.hs           CLabel\r
189 BlockId.hs          BlockId, BlockEnv, BlockSet\r
190 \r
191 \r
192 ----------------------------------------------------\r
193         Proc-points\r
194 ----------------------------------------------------\r
195 \r
196 Consider this program, which has a diamond control flow, \r
197 with a call on one branch\r
198  fn(p,x) {\r
199         h()\r
200         if b then { ... f(x) ...; q=5; goto J }\r
201              else { ...; q=7; goto J }\r
202      J: ..p...q...\r
203   }\r
204 then the join point J is a "proc-point".  So, is 'p' passed to J\r
205 as a parameter?  Or, if 'p' was saved on the stack anyway, perhaps\r
206 to keep it alive across the call to h(), maybe 'p' gets communicated\r
207 to J that way. This is an awkward choice.  (We think that we currently\r
208 never pass variables to join points via arguments.)\r
209 \r
210 Furthermore, there is *no way* to pass q to J in a register (other\r
211 than a parameter register).\r
212 \r
213 What we want is to do register allocation across the whole caboodle.\r
214 Then we could drop all the code that deals with the above awkward\r
215 decisions about spilling variables across proc-points.\r
216 \r
217 Note that J doesn't need an info table.\r
218 \r
219 What we really want is for each LastCall (not LastJump/Ret) \r
220 to have an info table.   Note that ProcPoints that are not successors\r
221 of calls don't need an info table.\r
222 \r
223 Figuring out proc-points\r
224 ~~~~~~~~~~~~~~~~~~~~~~~~\r
225 Proc-points are identified by\r
226 CmmProcPoint.minimalProcPointSet/extendPPSet Although there isn't\r
227 that much code, JD thinks that it could be done much more nicely using\r
228 a dominator analysis, using the Dataflow Engine.\r
229 \r
230 ----------------------------------------------------\r
231                 CAFs\r
232 ----------------------------------------------------\r
233 \r
234 * The code for a procedure f may refer to either the *closure* \r
235   or the *entry point* of another top-level procedure g.  \r
236   If f is live, then so is g.  f's SRT must include g's closure.\r
237 \r
238 * The CLabel for the entry-point/closure reveals whether g is \r
239   a CAF (or refers to CAFs).  See the IdLabel constructor of CLabel.\r
240 \r
241 * The CAF-ness of the original top-level defininions is figured out\r
242   (by TidyPgm) before we generate C--.  This CafInfo is only set for\r
243   top-level Ids; nested bindings stay with MayHaveCafRefs.\r
244 \r
245 * Currently an SRT contains (only) pointers to (top-level) closures.\r
246 \r
247 * Consider this Core code\r
248         f = \x -> let g = \y -> ...x...y...h1...\r
249                   in ...h2...g...\r
250   and suppose that h1, h2 have IdInfo of MayHaveCafRefs.\r
251   Therefore, so will f,  But g will not (since it's nested).\r
252 \r
253   This generates C-- roughly like this:\r
254      f_closure: .word f_entry\r
255      f_entry() [info-tbl-for-f] { ...jump g_entry...jump h2... }\r
256      g_entry() [info-tbl-for-g] { ...jump h1... }\r
257 \r
258   Note that there is no top-level closure for g (only an info table).\r
259   This fact (whether or not there is a top-level closure) is recorded\r
260   in the InfoTable attached to the CmmProc for f, g\r
261   INVARIANT: \r
262      Any out-of-Group references to an IdLabel goes to\r
263      a Proc whose InfoTable says "I have a top-level closure".\r
264   Equivalently: \r
265      A CmmProc whose InfoTable says "I do not have a top-level\r
266      closure" is referred to only from its own Group.\r
267 \r
268 * So:   info-tbl-for-f must have an SRT that keeps h1,h2 alive\r
269         info-tbl-for-g must have an SRT that keeps h1 (only) alive\r
270 \r
271   But if we just look for the free CAF refs, we get:\r
272         f   h2 (only)\r
273         g   h1\r
274 \r
275   So we need to do a transitive closure thing to flesh out \r
276   f's keep-alive refs to include h1.\r
277 \r
278 * The SRT info is the C_SRT field of Cmm.ClosureTypeInfo in a\r
279   CmmInfoTable attached to each CmmProc.  CmmPipeline.toTops actually does\r
280   the attaching, right at the end of the pipeline.  The C_SRT part\r
281   gives offsets within a single, shared table of closure pointers.\r
282 \r
283 * DECIDED: we can generate SRTs based on the final Cmm program\r
284   without knowledge of how it is generated.\r
285 \r