Optimizer phase ordering

An approach to tackle the phase ordering problem is the CoSy compiler
framework which has been developed from 1990-95 in the Esprit project
COMPARE.


Andy Glew writes:


> Ideally, the optimizations would not be invoked in a "phase order",
> but would instead be invoked with a particular scope (subtree, trace,
> hyperblock). Some optimizations might place constraints on the scopes
> they accept - truly global optimizations might require full program
> scope.


In CoSy one can define 'interaction schemes' between phases.
>From them parts of the compiler are generated which call/supervise the
phases. Phases can be written on arbitrary parts of the intermediate
representation. Conflicts between phases (writing the same data, etc)
are described by a side effect description language, called fSDL.
>From this specification the access to the intermediate representation
functions are generated depending on the interaction of the phases.


> One thing I have tried to encourage compiler folk to do is to make the
> back-end recursive or reentrant - have every optimization read in and
> write out the same intermediate form, along with arbitrarily
> extensible (typed) annotations.


We at the University of Karlsruhe have improved our code generator BEG
for that. The generated backends can access both low level
intermediate representation as well as assembler representation.
Generated backends are reentrant so that they can run as parallel
processes.


> Optimizations should not be done in place, but should be done in a
> manner such that they can be easily backed out. Thus, a particular
> optimization module suggests an optimization, but the framework may
> evaluate several different optimizations, and only take one.


This is called 'speculative interaction' of phases. The side effect
specification of fSDL allows to find out those parts of the data that
has to be 'shadowed', i.e. duplicated to avoid conflicts. After the
speculativism selector phases have to select best versions and copy
them back.


> Optimizations should be continuation structured. At various places,
> optimization modules may execute "call backs" to the framework, with
> queries like "is this code frequently executed?" - the framework
> should have the option of saving a continuation, and changing its mind
> if, as a result of other decisions, the answer changes.


Phases can be called at arbitrary places in the compiler, there are also
server phases which provide global services.


> Actually, it just occurred to me that what I have described is really
> a transaction processing paradigm - structure optimizations as
> transactions, perform optimistic concurrency control, commit them if
> assumptions haven't changed, back them out if it has.


Yes, CoSy is a kind of transaction oriented, however everything is in
shared memory, to be fast.


> Point is, individual optimizing modules should control the policy -
> the framework should.
> Simple phase ordering, as is seen in most compilers, is just, of
> course, an extremely naive framework.


The specification of interactions and the generation of the
supervising code can be influenced that all phases are executed
sequentially. Or in parallel with processes/threads.


> Setting up such a framework does take a lot of work, and has some cost
> in compile time. The problem is, at any point in time such a general
> framework will probably only deliver results similar to an ad-hoc
> backend structure - where "ad-hoc" means that the structure has been
> carefully crafted to support the current state of the art. It is only
> over time that the flexible structure would show its advantage, by
> being able to incorporate new optimizations more easily.


Yes, unfortunately COMPARE had a lot of problems with it, but it starts
to work now. In some months there will be systems which you can buy,
and probably also a cheap research version. If you are interested, contact


info@ace.nl


CoSy is described in


@Inproceedings{alt.94a,
    Author = {Alt, M. and A\3mann, U. and van~Someren, H.},
    Title = "{Cosy Compiler Phase Embedding with the CoSy Compiler Model}",
    BookTitle = {Compiler Construction, Lecture Notes in Computer Science 786},
    Year = {1994},
    Editor = {Fritzson, P. A.},
    Pages = {278--293},
    Publisher = {Springer},
    Month = {April}
}




Best regards
Uwe
--
Uwe Assmann
Universit"at Karlsruhe
Institut f"ur Programm- und Datenstrukturen (IPD)
Vincenz-Priessnitz-Str. 3, 76128 Karlsruhe, GERMANY
Email: assmann@informatik.uni-karlsruhe.de Tel.: +721/6086087
--

Return to the comp.compilers page.
Search the comp.compilers archives again.