[Haskell-cafe] Re: Properties of optimizer rule application?

[Henning Thielemann]

On Mon, 21 Jan 2008, Simon Peyton-Jones wrote:

> | Recently I found that specialisation interacts in an unexpected way with
> | explicit RULES (and with inlining). I used a function multiple times and
> | this seemed to make GHC specialising this function (although I did not
> | used a SPECIALISE pragma) to the particular type. But then this function
> | was no longer available for fusion.
>
> Yes, specialisation generates new RULES.  These new rules apply all the
> time, so they may rewrite your call to f before your fusion rules run.
> This is a bad thing.  Really, specialisation should generate rules for a
> particular phase 'spec', and you should be able to add your fusion rules
> to precede or follow 'spec'.

One could also make RULES and INLINE confluent with SPECIALISE by
generated specialised RULES and INLINE rules.

> | Summarized I think it is not only required to have better control over the
> | phases of the optimizer but to have a clear unifying concept of several
> | kinds of program transformations, namely SPECIALISE, INLINE, RULES.
>
> I can hardly argue with a "clear unifying concept".  But I'm not quite
> sure what you mean.  Here's a stab.  You could put this on the wiki and
> refine it with help from this end.
>
> * SPECIALISE generates a rule
> * RULES specifies a rule
> * INLINE is just like a rule (lhs = rhs)
>
> The latter two can be controlled to some extend by the "phase" mechanism.  The first should be.
>
>
> Did you mean more than that?

Yes, this and more. Today

* SPECIALISE has no phase control and is applied conditionally
* RULES has phase control and is applied unconditionally
* INLINE has phase control and is applied conditionally depending on some cost measure,
     INLINE disables application of RULES within the function definition body,
     although it is not granted that the function is always inlined

Phase control for SPECIALISE would be one way to greater uniformity. Is it
sufficient to restrict specialisation to one phase? Shall rules and
specialisations be controlled by costs? I don't know.

  I learnt in this thread, that there are two ways to resolve conflicts:
 1. Make rules confluent, that is, merge what fits together
 2. Assign to different phases, that is, keep things separated, that cannot be merged.
  It seems to me that establishing confluence is to be prefered, because
if two rules are active only in separate phases they cannot be applied
alternatedly multiple times. Thus an improved optimizer should somehow
support making fusion systems confluent, that consists of all three kinds
of rules.