paralell assignment problem
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Radu Grigore <radugrigore@g...> 
Subject:  Re: [Camllist] 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 indegree 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, radu http://rgrig.idilis.ro/