English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
paralell assignment problem
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-02-08 (18:32)
From: Marcin 'Qrczak' Kowalczyk <qrczak@k...>
Subject: Re: [Caml-list] paralell assignment problem
skaller <skaller@users.sourceforge.net> writes:

> fun ack(x:int,y:int):int =>
>   if x == 0 then y + 1
>   elif y == 0 then ack(x-1, 1)
>   else ack(x-1, ack(x, y-1))
>   endif
> ;
> No temporaries are needed in either tail call,
> and either order of assignment will work.
> But my actual code created 2 temporaries for each
> tail call, unnecessarily.

In the implementation of my language Kogut which targets C, on the
level I assign argument values to parameter slots (global variables),
expressions have already been processed into sequences of statements,
such that the remaining expressions contain only variables, constants,
and simple operations which don't call unknown code, don't have side
effects, don't depend on the time when they are evaluated, and can
actually be transformed into C expressions, not C statements. On this
level it's clear what expressions depend on which virtual registers.

I don't bother with finding the optimal assignment - I just make an
easy choice way which generates quite good result in most cases:

Positions are generally assigned in order. For each position, if the
target of the assignment is used among later source expressions, then
a C temporary is introduced and the temporary is assigned from the
source expression; otherwise the target is assigned directly (unless
it's the same as the source, in which case the assignment is skipped).
At the end all temporaries are assigned to their targets.

Sometimes this generates more temporaries than would be possible
with a different order, but I don't care. The C compiler must
still introduce a temporary register for moving between two global
variables, so maybe it would generate the same code even if all
values were passed through temporaries; I've heard gcc is pretty
good in propagating copies.

   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/