Changes between Initial Version and Version 1 of NestedCPR/DmdAnalIdeas

Jan 21, 2014 5:16:21 PM (6 years ago)



  • NestedCPR/DmdAnalIdeas

    v1 v1  
     1Some ideas related to #7994:
     3Here are some ideas.
     5Consider this expression `e`:
     7let f = λ x. let h = f (g1 x)
     8             in λ y.  x `seq` h (g2 y)
     9in ...f a 2..... f 3 4 ...
     11This can be rewritten to
     13let f = λ x. let h = f (g1 x)
     14             in λ y. x `seq`  h (g2 y)
     15    r = ...f a 2..... f 3 4 ...
     16in r
     18how can we analyse that to achieve the desired effect (i.e. arity 2 for `f` and hence strict in `x`, and `λ y` one-shot)?
     20We need to calculate the demand on `f` and `r` in the fix point analysis, instead of always starting with a `cleanEvalDmd` in `dmdAnalRhs`.
     22So thinking of the mutual recursion as simple recursion with a tuple, an incoming demand `d` on all of `e` is turned into an initial demand `(Abs, d)` on `(f,r)`.
     24The first iteration analyses `f` with demand `Abs` (i.e. not at all) and `r` with demand `d`, while using `botDmdType` for `f` in the environment of the analyser. Then the result of this analysis is a demand type with `{f → C(C¹(S)), r → Abs, a → Hyper }`.
     26We lub this with the demand from the outside `(Abs, d)` and re-start with `(C(C¹(S)), d)`. `f` is still as diverging in the strictness signature. But this, we will also get the demand from `f` on `f` into the result. But if we start with `C(C¹(C))` for `f`, then `f` puts that on itself! The resulting demand is thus the same (`{f → C(C¹(S)), r → Abs, a → Hyper }`), but in this pass, we will also have found out something about `f` strictness signature, which we now can consider to be `<S><L>`. Note that we were allowed to create this signature with two arguments, because the demand had two levels of calls.
     28The demand stayed the same, but the strictness signature changed. So we do another iteration. This now relaxes the demand on `a` and we obtain `{f → C(C¹(S)), r → Abs, a → S }`, with `f` strictness signature unchanged.
     30A last round and the demand put on `f` by its RHS and `r` stays the same, as well as `f` demand signature, and we have the desired results.
     33In the counter-example
     35let f = λ x. let h = f (g1 x)
     36             in λ y... map h...
     37in ...f 1 2..... f 3 4 ...
     39the second iteration would try `C(C¹(S))` on `f` as before, but it would be `C(S)` in the third run, because of the demand put on `f` by `f` itself.
     42The problem with this approach is that it is not monotone, as we update the strictness signatures. It might be `<S><L>` in one iteration (which causes `(f x)` to put a lazy demand on `x`) and `<S>` in the next (causing `(f x)` to put a strict demand on `x`). So the fixed-point iteration might not terminate...
     44Maybe it is enough to over-approximate the demand within the fixed-point iteration? I.e. if `f` has signature `<S><L>`, then `(f x)` puts a strict demand on `x`. Presumably if in the next iteration, `f` has only `<S>`, then nothing went wrong; if it then has `<L>`, we can still reduce the demand on `x`. Note that we always start from a strong demand and converge towards a weaker demand.