This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

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:33) From: Radu Grigore Subject: Re: [Caml-list] Re: paralell assignment problem
```On Tue, 08 Feb 2005 09:12:32 -0800 (PST), skaller
<skaller@users.sourceforge.net> wrote:

> However it isn't clear (to me) that just picking an arbitrary
> assignment to split into two using a temporary
> actually minimises the number of temporaries.

I'm mildly convinced that it works.

Imagine a graph where an arrow is drawn from A to B only if A appears
in the expression to be assigned to B. You can imagine the process of
introducing temporaries as marking a few edges in this graph so that
you break all cycles. One marked edge = one temporary. But since no
identifier appears more than once on the left side, in this graph the
in-degree is at most 1 and each node is part of at most one cycle.
>From this it follows that each marked edge breaks at most one cycle.
Since all your temporaries break at least one cycle the algorithm
should work.

--
regards,