This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [RFC] flow.c: Speed up delete_dead_jumptables.


On Mon, 2005-02-21 at 12:14 -0500, Kazu Hirata wrote:
> Hi,
> 
> Attached is a patch to speed up delete_dead_jumptables by scanning
> insns that do not belong to any basic block.  Note that jump tables do
> not belong to any basic block.
Good insight.

> 
> I think we have up-to-date CFG at all call sites of
> delete_dead_jumptables, but I am not 100% sure.  By up-to-date, I mean
> that BB_HEAD and BB_END are indeed what they are supposed to be for
> each basic block.  If you are a CFG expert and help me determine if
> all the following places have up-to-date CFG, that would be greately
> appreciated.
> 
> cfgcleanup.c:2137:      delete_dead_jumptables ();
> cfglayout.c:620:  delete_dead_jumptables ();
> flow.c:445:  delete_dead_jumptables ();
We build the CFG before we run any of the RTL optimizers, then maintain
it through the compilation, with the exception of the RTL loop
optimizer.

So I think what you need to verify is that we can't call
delete_dead_jumptables from the point where the loop optimizer
starts mucking things up until it calls find_basic_blocks to
rebuild the CFG.

Given that the loop optimizer trashes the CFG, we can probably safely
assume that it doesn't call cleanup_cfg :-)  cleanup_cfg would be 
working with a garbage CFG.

I'm pretty sure the cfglayout code is safe.  It certainly seems to know
that ADDR_VEC/ADDR_VEC_DIFF insns don't appear within basic blocks, but
instead appear after them.  And I think that code would break horribly
if the block head/end were out of date.

Similarly, if life_analysis was presented with an invalid CFG (ie,
out of date head/tail pointers), I don't see how it could possibly
work correctly.


> 
> The problem is that the improvement is so small.
> 
> Even for a large file like insn-attrtab.i, the running time of
> delete_dead_jumptables goes down from 48.9ms to 36.5ms.  Yes, 25%
> improvement but in milliseconds.
Even so, just scanning between blocks is clearly more efficient than
scanning the full insn chain.   The test you'd want to use would be
one which has lots of insns in its blocks -- insn-attrtab.i doesn't
really have that property - insn-attrtab.i has lots of blocks with a
small number of insns in them.


> One more problem.  I don't feel confident even after usual bootstrap
> and regtesting.  Dead jump tables are becoming extremely rare because
> most constant propagation opportunities are taken at tree level.
True, but you're depending on a well known property of RTL, namely that
jump tables are not associated with any block -- they appear strictly
inbetween blocks.


> Another thing I have briefly thought about is to disable folding of
> jump-table based conditional jumps as they are rarely folded at RTL
> level.  Yes, we do have a missed optimization (and an ICE) like PR
> 20017, but how often do we make jump tables dead at RTL level?  At
> least, we never do while compiling cc1-i files.
> 
> Tested on i686-pc-linux-gnu.  Any comments?
> 
> Kazu Hirata
> 
> 2005-02-20  Kazu Hirata  <kazu@cs.umass.edu>
> 
> 	* flow.c (delete_dead_jumptables): Speed up by scanning insns
> 	that do not belong to any basic block.
Looks good to me.



jeff



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]