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]

[RFC] flow.c: Speed up delete_dead_jumptables.


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.

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 ();

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.

Of course, if we start calling delete_dead_jumptables from
cleanup_cfg, the absolute saving is multiplied by roughly 5 times.
(Currently, delete_dead_jumptables is called about 400 times.
cleanup_cfg is called about 1500 times.)

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.

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.

Index: flow.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flow.c,v
retrieving revision 1.618
diff -c -d -p -r1.618 flow.c
*** flow.c	17 Feb 2005 16:19:30 -0000	1.618
--- flow.c	20 Feb 2005 01:40:18 -0000
*************** delete_noop_moves (void)
*** 823,843 ****
  void
  delete_dead_jumptables (void)
  {
!   rtx insn, next;
!   for (insn = get_insns (); insn; insn = next)
      {
!       next = NEXT_INSN (insn);
!       if (LABEL_P (insn)
! 	  && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
! 	  && JUMP_P (next)
! 	  && (GET_CODE (PATTERN (next)) == ADDR_VEC
! 	      || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
  	{
! 	  if (dump_file)
! 	    fprintf (dump_file, "Dead jumptable %i removed\n", INSN_UID (insn));
! 	  delete_insn (NEXT_INSN (insn));
! 	  delete_insn (insn);
! 	  next = NEXT_INSN (next);
  	}
      }
  }
--- 823,857 ----
  void
  delete_dead_jumptables (void)
  {
!   basic_block bb;
! 
!   /* A dead jump table does not belong to any basic block.  Scan insns
!      between two adjacent basic blocks.  */
!   FOR_EACH_BB (bb)
      {
!       rtx insn, next;
! 
!       for (insn = NEXT_INSN (BB_END (bb));
! 	   insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
! 	   insn = next)
  	{
! 	  next = NEXT_INSN (insn);
! 	  if (LABEL_P (insn)
! 	      && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
! 	      && JUMP_P (next)
! 	      && (GET_CODE (PATTERN (next)) == ADDR_VEC
! 		  || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
! 	    {
! 	      rtx label = insn, jump = next;
! 
! 	      if (dump_file)
! 		fprintf (dump_file, "Dead jumptable %i removed\n",
! 			 INSN_UID (insn));
! 
! 	      next = NEXT_INSN (next);
! 	      delete_insn (jump);
! 	      delete_insn (label);
! 	    }
  	}
      }
  }


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