speeding up liveness analysis ideas.

speeding up liveness analysis ideas.

[Jan Hubicka]

Hi,
Not only on Brad's testcase we spend very important amount of time in the
liveness analysis.  This is relatively sad score and I think we should try
to improve it.  It is also interesting that the times appears to be considerably
worse in the current code than they was in 3.0 times and I don't recall any
important change to the code possibly responsible for that.

Here are several assorted ideas what I think can help

1) Use df.c module to find the references and uses - we currently spend
quite a lot of time in mark_set_1 and for_each_rtx modules.  Discovering all
uses/sets at once before relaxation process can be good idea...
2) Reverse topological order the blocks for relaxation progress
   - this should help any iterative dataflow..
3) Avoid the global liveness rebuild in optimize_for_mode_switching.

This is dificult because it do use commit_edge_insertions that basically
does arbitary modifications of the CFG and makes it dificult to track down
all modified blocks to locally re-examine.

I think I can get this done at lower level.  If I create new BB flag BB_MODIFIED
and clear it at the begginig of pass and make emit_insn/remove_insn familly to
set this flag, I can get the information for lowlevel.
Then I can easilly prepare the bitmap of blocks to update.  The if converison
and cfg_cleanup can benefit from this infrastructure.

Other alternative is to do it at higher level in the CFG manipulation routines,
so there can be made difference between local and global transformation
so we don't need to rerun the relaxation progress (or know whether the
pass can do global changes from it's overall design).  But I am not quite
sure how many places would need modification then.

Also why the local update is cheaper - if we rerun relaxation and we do only
local updates it should use exactly one iteration.  Is the local update
basically designed to catch the bugs?

What do you think?  Does that make sense?

Honza

Re: speeding up liveness analysis ideas.

[Daniel Berlin]

On Saturday, October 20, 2001, at 07:23  AM, Jan Hubicka wrote:

> Hi,
> Not only on Brad's testcase we spend very important amount of time in 
> the
> liveness analysis.  This is relatively sad score and I think we should 
> try
> to improve it.  It is also interesting that the times appears to be 
> considerably
> worse in the current code than they was in 3.0 times and I don't recall 
> any
> important change to the code possibly responsible for that.
>
>
It could just be bad bitmap set/clear ordering or something.
In fact, it's likely the cause if you are correct in that there have 
been few changes to the code.
Just changing the number/spread across blocks of registers would have a 
significant impact on the speed of the bitmap operations.
Once they fall out of the current bitmap element, it's linear.

> Here are several assorted ideas what I think can help
>
> 1) Use df.c module to find the references and uses - we currently spend
> quite a lot of time in mark_set_1 and for_each_rtx modules.  
> Discovering all
> uses/sets at once before relaxation process can be good idea...
Yup.

> 2) Reverse topological order the blocks for relaxation progress
>    - this should help any iterative dataflow..
Yup.