[Haskell-cafe] Properties of optimizer rule application?

[Henning Thielemann]

On Wed, 16 Jan 2008, Simon Peyton-Jones wrote:

> GHC has one main mechanism for controlling the application of rules,
> namely simplifier "phases".  You can say "apply this rule only after
> phase N" or "apply this rule only before phase N".  Similarly for INLINE
> pragmas.  The manual describes this in detail.

Indeed. But since it does not mention the number of phases, nor the number
of iterations per phase, nor what actually is performed per iteration,
this appeared to me to be an internal issue of GHC which should not be
relied on.

> I urge against relying on "top-down" or "bottom-up" guarantees, because
> they are fragile: if you miss a single opportunity to apply rule A, then
> rule B may kick in; but a later inlining or other simplification might
> make rule A applicable.  Phases are the way to go.

I see.

> That said, GHC has much too rigid a notion of phases at the moment.
> There are precisely 3, namely 2 then 1 then 0, and that does not give enough control.

What about the 'gentle' phase in the dump ?

> Really we should let you give arbitrary names to phases, express
> constraints (A must be before B), and run a constraint solver to map
> phase names to a linear ordering.

Sounds like a topological sort. Reminds me on precedence control of infix
operators.

It seems to me that you have something more sophisticated already in mind.
What you sketch would allow application specific code to defer
optimization rules from the standard libraries. E.g. I could write rules
for lists that are designed for my application and that can be applied
without interference from Data.List. When no more of my rules can be
applied, then Data.List rules can fuse the rest.


It's interesting how to integrate this in the Haskell language. When you
want to state "phase A before phase B" you may have to refer to phases
defined in other modules. You have to be able to import them from other
modules, and you cannot use the regular 'import' syntax, since phase
identifiers are not part of Haskell language. Maybe you must enclose those
imports in pragmas, too. You need new module dependency checking, since
more dependencies can be introduced when optimization is switched on or
you have to restrict phase import to modules that are imported anyway.

{-# RULES
  import qualified Data.List as List
  #-}

> There's scope for an intern project here.

I could take the opportunity.