Remove bogus assertion
[ghc.git] / compiler / profiling / NOTES
1 Profiling Implementation Notes -- June/July/Sept 1994
2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3
4 Simon and Will
5
6 Pre-code-generator-ish
7 ~~~~~~~~~~~~~~~~~~~~~~
8
9 * Automagic insertion of _sccs_ on...
10
11   - If -fprof-auto-exported is specified, add _scc_ on each *exported* top-level definition. 
12     NB this includes CAFs.  Done by addAutoCostCentres (Core-to-Core pass).
13
14   - If -fprof-auto-top is specified, add _scc_ on *all* top-level definitions.
15     Done by same pass.
16
17   - If -fprof-auto is specified, add _scc_ on *all* definitions.
18
19   - Always: just before code generation of module M, onto any CAF
20     which hasn't already got an explicit cost centre attached, pin
21     "AllCAFs-M".
22
23     Done by finalStgMassageForProfiling (final STG-to-STG pass)
24
25     Only the one-off costs of evaluating the CAFs will be attributed
26     to the AllCAFs-M cost centre.  We hope that these costs will be
27     small; since the _scc_s are introduced automatically it's
28     confusing to attribute any significant costs to them.  However if
29     there *are* significant one-off costs we'd better know about it.
30
31     Why so late in the compilation process?  We aren't *absolutely*
32     sure what is and isn't a CAF until *just* before code generation.
33     So we don't want to mark them as such until then.
34
35   - Individual DICTs
36
37     We do it in the desugarer, because that's the *only* point at
38     which we *know* exactly what bindings are introduced by
39     overloading.  NB should include bindings for selected methods, eg
40
41         f d = let op = _scc_ DICT op_sel d in
42               ...op...op...op
43
44     The DICT CC ensures that:
45     (a) [minor] that the selection cost is separately attributed
46     (b) [major] that the cost of executing op is attributed to
47         its call site, eg
48
49         ...(scc "a" op)...(scc "b" op)...(scc "c" op)...
50
51 * Automagic "boxing" of higher-order args:
52
53         finalStgMassageForProfiling (final STG-to-STG pass)
54
55         This (as well as CAF stuff above) is really quite separate
56         from the other business of finalStgMassageForProfiling
57         (collecting up CostCentres that need to be
58         declared/registered).
59         
60         But throwing it all into the pot together means that we don't
61         have to have Yet Another STG Syntax Walker.
62
63         Furthermore, these "boxes" are really just let-bindings that
64         many other parts of the compiler will happily substitute away!
65         Doing them at the very last instant prevents this.
66
67         A down side of doing these so late is that we get lots of
68         "let"s, which if generated earlier and not substituted away,
69         could be floated outwards.  Having them floated outwards would
70         lessen the chance of skewing profiling results (because of
71         gratuitous "let"s added by the compiler into the inner loop of
72         some program...).  The allocation itself will be attributed to
73         profiling overhead; the only thing which'll be skewed is time measurement.
74
75         So if we have, post-boxing-higher-order-args...
76
77             _scc_ "foo" ( let f' = [f] \ [] f
78                           in
79                           map f' xs )
80
81         ... we want "foo" to be put in the thunk for "f'", but we want the
82         allocation cost (heap census stuff) to be attr to OVERHEAD.
83
84         As an example of what could be improved
85                 f = _scc_ "f" (g h)
86         To save dynamic allocation, we could have a static closure for h:
87                 h_inf = _scc_ "f" h
88                 f = _scc_ "f" (g h_inf)
89         
90
91         
92
93
94 Code generator-ish
95 ~~~~~~~~~~~~~~~~~~
96
97 (1) _Entry_ code for a closure *usually* sets CC from the closure,
98                  at the fast entry point
99
100     Exceptions:
101
102     (a) Top-level subsumed functions (i.e., w/ no _scc_ on them)
103
104         Refrain from setting CC from the closure
105
106     (b) Constructors
107
108         Again, refrain.  (This is *new*)
109         
110         Reasons: (i) The CC will be zapped very shortly by the restore
111         of the enclosing CC when we return to the eval'ing "case".
112         (ii) Any intervening updates will indirect to this existing
113         constructor (...mumble... new update mechanism... mumble...)
114
115 (2) "_scc_ cc expr"
116
117     Set current CC to "cc".  
118     No later "restore" of the previous CC is reqd.
119
120 (3) "case e of { ...alts... }" expression (eval)
121
122     Save CC before eval'ing scrutinee
123     Restore CC at the start of the case-alternative(s)
124
125 (4) _Updates_ : updatee gets current CC
126
127     (???? not sure this is OK yet 94/07/04)
128
129     Reasons:
130
131     * Constructors : want to be insensitive to return-in-heap vs
132         return-in-regs.  For example,
133
134         f x = _scc_ "f" (x, x)
135
136         The pair (x,x) would get CC of "f" if returned-in-heap;
137         therefore, updatees should get CC of "f".
138
139     * PAPs : Example:
140
141         f x = _scc_ "f" (let g = \ y -> ... in g)
142
143         At the moment of update (updatePAP?), CC is "f", which
144         is what we want to set it to if the "updatee" is entered
145
146         When we enter the PAP ("please put the arguments back so I can
147         use them"), we restore the setup as at the moment the
148         arg-satisfaction check failed.
149
150         Be careful!  UPDATE_PAP is called from the arg-satis check,
151         which is before the fast entry point.  So the cost centre
152         won't yet have been set from the closure which has just
153         been entered.  Solution: in UPDATE_PAP see if the cost centre inside
154         the function closure which is being entered is "SUB"; if so, use
155         the current cost centre to update the updatee; otherwise use that
156         inside the function closure.  (See the computation of cc_pap
157         in rule 16_l for lexical semantics.)
158
159
160 (5) CAFs
161
162 CAFs get their own cost centre.  Ie
163
164                         x = e
165 is transformed to
166                         x = _scc_ "CAF:x" e
167
168 Or sometimes we lump all the CAFs in a module together.
169 (Reporting issue or code-gen issue?)
170
171
172
173 Hybrid stuff
174 ~~~~~~~~~~~~
175
176 The problem:
177
178   f = _scc_ "CAF:f" (let g = \xy -> ...
179                    in (g,g))
180
181 Now, g has cost-centre "CAF:f", and is returned as part of
182 the result.  So whenever the function embedded in the result
183 is called, the costs will accumulate to "CAF:f".  This is
184 particularly (de)pressing for dictionaries, which contain lots
185 of functions.
186
187 Solution: 
188
189   A.  Whenever in case (1) above we would otherwise "set the CC from the
190   closure", we *refrain* from doing so if 
191         (a) the closure is a function, not a thunk; and
192         (b) the cost-centre in the closure is a CAF cost centre.
193
194   B.  Whenever we enter a thunk [at least, one which might return a function]
195   we save the current cost centre in the update frame.  Then, UPDATE_PAP
196   restores the saved cost centre from the update frame iff the cost
197   centre at the point of update (cc_pap in (4) above) is a CAF cost centre.
198
199   It isn't necessary to save and possibly-restore the cost centre for
200   thunks which will certainly return a constructor, because the 
201   cost centre is about to be restored anyway by the enclosing case.
202
203 Both A and B are runtime tests.  For A, consider:
204
205   f = _scc_ "CAF:f" (g 2)
206
207   h y = _scc_ "h" g (y+y)
208
209   g x = let w = \p -> ...
210         in (w,w)
211
212
213 Now, in the call to g from h, the cost-centre on w will be "h", and
214 indeed all calls to the result of the call should be attributed to
215 "h".  
216
217   ... _scc_ "x1" (let (t,_) = h 2 in t 3) ...
218
219   Costs of executing (w 3) attributed to "h".
220
221 But in the call to g from f, the cost-centre on w will be
222 "CAF:f", and calls to w should be attributed to the call site.
223
224   ..._scc_ "x2" (let (t,_) = f in t 3)...
225
226   Costs of executing (w 3) attributed to "x2".
227
228
229         Remaining problem
230
231 Consider
232
233         _scc_ "CAF:f" (if expensive then g 2 else g 3)
234
235 where g is a function with arity 2.  In theory we should
236 restore the enclosing cost centre once we've reduced to
237 (g 2) or (g 3).  In practice this is pretty tiresome; and pretty rare.
238
239 A quick fix: given (_scc_ "CAF" e) where e might be function-valued
240 (in practice we usually know, because CAF sccs are top level), transform to
241
242         _scc_ "CAF" (let f = e in f)
243
244
245
246
247
248 ============
249
250 scc cc x  ===>   x
251
252   UNLESS
253
254 (a)  cc is a user-defined, non-dup'd cost 
255      centre (so we care about entry counts)
256
257 OR
258
259 (b) cc is not a CAF/DICT cost centre and x is top-level subsumed
260      function.
261         [If x is lambda/let bound it'll have a cost centre
262          attached dynamically.]
263
264         To repeat, the transformation is OK if 
265                 x is a not top-level subsumed function
266         OR      
267                 cc is a CAF/DICT cost centre and x is a top-level
268                 subsumed function
269
270
271
272 (scc cc e) x  ===>  (scc cc e x)
273
274         OK????? IFF
275
276 cc is not CAF/DICT  --- remains to be proved!!!!!!
277 True for lex
278 False for eval
279 Can we tell which in hybrid?
280
281 eg  Is this ok?
282
283         (scc "f" (scc "CAF" (\x.b))) y ==>   (scc "f" (scc "CAF" (\x.b) y))
284
285
286 \x -> (scc cc e)    ===>   (scc cc \x->e)
287
288         OK IFF cc is not CAF/DICT
289
290
291 scc cc1 (scc cc2 e))   ===>  scc cc2 e
292
293         IFF not interested in cc1's entry count
294         AND cc2 is not CAF/DICT
295
296 (scc cc1 ... (scc cc2 e) ...)   ===>  (scc cc1 ... e ...)
297
298         IFF cc2 is CAF/DICT
299         AND e is a lambda not appearing as the RHS of a let
300             OR
301             e is a variable not bound to SUB
302
303