[new-regalloc] Dataflow too slow...

[Michael Matz]

Hi,

On Sat, 3 Feb 2001, Daniel Berlin wrote:
> >
> > I used a simple worklist algorithm for this to get the ball rolling.
> > The usual solution to impove the performance is to order the blocks
> > with a depth first search.  This was on my todo list.
> 
> I did this as well, i forgot to mention.
> I use flow_compute_depth_first_order to get the dfs ordering, and then
> have it pick the first block on the worklist, in order of dfs order
> IE
> for (i=0; i < n_basic_blocks; i++)
>   if (TEST_BIT (worklist, dfs_order[i])
>      return dfs_order[i];

In order to reach (the best possible) O(N+2) with N == maximal number of
backedges in a acyclic path, one needs to use reverse completion order
(the second argument of flow_depth_first_order_compute), _not_ DFS order.

Additionally df.* shouldn't use (s)bitmap's at all for worklists, but
instead normal arrays as queues.


Ciao,
Michael.