--- /dev/null
+Profiling Implementation Notes -- June/July/Sept 1994
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Simon and Will
+
+Pre-code-generator-ish
+~~~~~~~~~~~~~~~~~~~~~~
+
+* Automagic insertion of _sccs_ on...
+
+ - If -auto is specified, add _scc_ on each *exported* top-level definition.
+ NB this includes CAFs. Done by addAutoCostCentres (Core-to-Core pass).
+
+ - If -auto-all is specified, add _scc_ on *all* top-level definitions.
+ Done by same pass.
+
+ - Always: just before code generation of module M, onto any CAF
+ which hasn't already got an explicit cost centre attached, pin
+ "AllCAFs-M".
+
+ Done by finalStgMassageForProfiling (final STG-to-STG pass)
+
+ Only the one-off costs of evaluating the CAFs will be attributed
+ to the AllCAFs-M cost centre. We hope that these costs will be
+ small; since the _scc_s are introduced automatically it's
+ confusing to attribute any significant costs to them. However if
+ there *are* significant one-off costs we'd better know about it.
+
+ Why so late in the compilation process? We aren't *absolutely*
+ sure what is and isn't a CAF until *just* before code generation.
+ So we don't want to mark them as such until then.
+
+ - Individual DICTs
+
+ We do it in the desugarer, because that's the *only* point at
+ which we *know* exactly what bindings are introduced by
+ overloading. NB should include bindings for selected methods, eg
+
+ f d = let op = _scc_ DICT op_sel d in
+ ...op...op...op
+
+ The DICT CC ensures that:
+ (a) [minor] that the selection cost is separately attributed
+ (b) [major] that the cost of executing op is attributed to
+ its call site, eg
+
+ ...(scc "a" op)...(scc "b" op)...(scc "c" op)...
+
+* Automagic "boxing" of higher-order args:
+
+ finalStgMassageForProfiling (final STG-to-STG pass)
+
+ This (as well as CAF stuff above) is really quite separate
+ from the other business of finalStgMassageForProfiling
+ (collecting up CostCentres that need to be
+ declared/registered).
+
+ But throwing it all into the pot together means that we don't
+ have to have Yet Another STG Syntax Walker.
+
+ Furthermore, these "boxes" are really just let-bindings that
+ many other parts of the compiler will happily substitute away!
+ Doing them at the very last instant prevents this.
+
+ A down side of doing these so late is that we get lots of
+ "let"s, which if generated earlier and not substituted away,
+ could be floated outwards. Having them floated outwards would
+ lessen the chance of skewing profiling results (because of
+ gratuitous "let"s added by the compiler into the inner loop of
+ some program...). The allocation itself will be attributed to
+ profiling overhead; the only thing which'll be skewed is time measurement.
+
+ So if we have, post-boxing-higher-order-args...
+
+ _scc_ "foo" ( let f' = [f] \ [] f
+ in
+ map f' xs )
+
+ ... we want "foo" to be put in the thunk for "f'", but we want the
+ allocation cost (heap census stuff) to be attr to OVERHEAD.
+
+ As an example of what could be improved
+ f = _scc_ "f" (g h)
+ To save dynamic allocation, we could have a static closure for h:
+ h_inf = _scc_ "f" h
+ f = _scc_ "f" (g h_inf)
+
+
+
+
+
+Code generator-ish
+~~~~~~~~~~~~~~~~~~
+
+(1) _Entry_ code for a closure *usually* sets CC from the closure,
+ at the fast entry point
+
+ Exceptions:
+
+ (a) Top-level subsumed functions (i.e., w/ no _scc_ on them)
+
+ Refrain from setting CC from the closure
+
+ (b) Constructors
+
+ Again, refrain. (This is *new*)
+
+ Reasons: (i) The CC will be zapped very shortly by the restore
+ of the enclosing CC when we return to the eval'ing "case".
+ (ii) Any intervening updates will indirect to this existing
+ constructor (...mumble... new update mechanism... mumble...)
+
+(2) "_scc_ cc expr"
+
+ Set current CC to "cc".
+ No later "restore" of the previous CC is reqd.
+
+(3) "case e of { ...alts... }" expression (eval)
+
+ Save CC before eval'ing scrutinee
+ Restore CC at the start of the case-alternative(s)
+
+(4) _Updates_ : updatee gets current CC
+
+ (???? not sure this is OK yet 94/07/04)
+
+ Reasons:
+
+ * Constructors : want to be insensitive to return-in-heap vs
+ return-in-regs. For example,
+
+ f x = _scc_ "f" (x, x)
+
+ The pair (x,x) would get CC of "f" if returned-in-heap;
+ therefore, updatees should get CC of "f".
+
+ * PAPs : Example:
+
+ f x = _scc_ "f" (let g = \ y -> ... in g)
+
+ At the moment of update (updatePAP?), CC is "f", which
+ is what we want to set it to if the "updatee" is entered
+
+ When we enter the PAP ("please put the arguments back so I can
+ use them"), we restore the setup as at the moment the
+ arg-satisfaction check failed.
+
+ Be careful! UPDATE_PAP is called from the arg-satis check,
+ which is before the fast entry point. So the cost centre
+ won't yet have been set from the closure which has just
+ been entered. Solution: in UPDATE_PAP see if the cost centre inside
+ the function closure which is being entered is "SUB"; if so, use
+ the current cost centre to update the updatee; otherwise use that
+ inside the function closure. (See the computation of cc_pap
+ in rule 16_l for lexical semantics.)
+
+
+(5) CAFs
+
+CAFs get their own cost centre. Ie
+
+ x = e
+is transformed to
+ x = _scc_ "CAF:x" e
+
+Or sometimes we lump all the CAFs in a module together.
+(Reporting issue or code-gen issue?)
+
+
+
+Hybrid stuff
+~~~~~~~~~~~~
+
+The problem:
+
+ f = _scc_ "CAF:f" (let g = \xy -> ...
+ in (g,g))
+
+Now, g has cost-centre "CAF:f", and is returned as part of
+the result. So whenever the function embedded in the result
+is called, the costs will accumulate to "CAF:f". This is
+particularly (de)pressing for dictionaries, which contain lots
+of functions.
+
+Solution:
+
+ A. Whenever in case (1) above we would otherwise "set the CC from the
+ closure", we *refrain* from doing so if
+ (a) the closure is a function, not a thunk; and
+ (b) the cost-centre in the closure is a CAF cost centre.
+
+ B. Whenever we enter a thunk [at least, one which might return a function]
+ we save the current cost centre in the update frame. Then, UPDATE_PAP
+ restores the saved cost centre from the update frame iff the cost
+ centre at the point of update (cc_pap in (4) above) is a CAF cost centre.
+
+ It isn't necessary to save and possibly-restore the cost centre for
+ thunks which will certainly return a constructor, because the
+ cost centre is about to be restored anyway by the enclosing case.
+
+Both A and B are runtime tests. For A, consider:
+
+ f = _scc_ "CAF:f" (g 2)
+
+ h y = _scc_ "h" g (y+y)
+
+ g x = let w = \p -> ...
+ in (w,w)
+
+
+Now, in the call to g from h, the cost-centre on w will be "h", and
+indeed all calls to the result of the call should be attributed to
+"h".
+
+ ... _scc_ "x1" (let (t,_) = h 2 in t 3) ...
+
+ Costs of executing (w 3) attributed to "h".
+
+But in the call to g from f, the cost-centre on w will be
+"CAF:f", and calls to w should be attributed to the call site.
+
+ ..._scc_ "x2" (let (t,_) = f in t 3)...
+
+ Costs of executing (w 3) attributed to "x2".
+
+
+ Remaining problem
+
+Consider
+
+ _scc_ "CAF:f" (if expensive then g 2 else g 3)
+
+where g is a function with arity 2. In theory we should
+restore the enclosing cost centre once we've reduced to
+(g 2) or (g 3). In practice this is pretty tiresome; and pretty rare.
+
+A quick fix: given (_scc_ "CAF" e) where e might be function-valued
+(in practice we usually know, because CAF sccs are top level), transform to
+
+ _scc_ "CAF" (let f = e in f)
+
+
+
+
+
+============
+
+scc cc x ===> x
+
+ UNLESS
+
+(a) cc is a user-defined, non-dup'd cost
+ centre (so we care about entry counts)
+
+OR
+
+(b) cc is not a CAF/DICT cost centre and x is top-level subsumed
+ function.
+ [If x is lambda/let bound it'll have a cost centre
+ attached dynamically.]
+
+ To repeat, the transformation is OK if
+ x is a not top-level subsumed function
+ OR
+ cc is a CAF/DICT cost centre and x is a top-level
+ subsumed function
+
+
+
+(scc cc e) x ===> (scc cc e x)
+
+ OK????? IFF
+
+cc is not CAF/DICT --- remains to be proved!!!!!!
+True for lex
+False for eval
+Can we tell which in hybrid?
+
+eg Is this ok?
+
+ (scc "f" (scc "CAF" (\x.b))) y ==> (scc "f" (scc "CAF" (\x.b) y))
+
+
+\x -> (scc cc e) ===> (scc cc \x->e)
+
+ OK IFF cc is not CAF/DICT
+
+
+scc cc1 (scc cc2 e)) ===> scc cc2 e
+
+ IFF not interested in cc1's entry count
+ AND cc2 is not CAF/DICT
+
+(scc cc1 ... (scc cc2 e) ...) ===> (scc cc1 ... e ...)
+
+ IFF cc2 is CAF/DICT
+ AND e is a lambda not appearing as the RHS of a let
+ OR
+ e is a variable not bound to SUB
+
+
projects / ghc-hetmet.git / blobdiff