[patch] Fix PR/13430 (compile time hog in bb-reorder.c)

Josef Zlomek zlomj9am@artax.karlin.mff.cuni.cz
Sat Dec 20 13:01:00 GMT 2003


Hello,

PR/13430 is a compile time hog when compiling a large function with large
computed jump (many edges going from the computed jump).
The first invocation of bb-reorder copied the block containing the computed jump
into many places because the block is cheaper than a jump.
The later passes (expecially the second invocation of bb-reorder) must then go
through a quadratic number of edges.
This patch causes that blocks which have many successors (> 8) are never copied.

Bootstrapped/regtested i686 and x86-64.
OK?

Josef

2003-12-20  Josef Zlomek  <zlomekj@suse.cz>

	* bb-reorder.c (copy_bb_p): Do not allow block with many successors to
	be copied.
	(find_traces_1_round): Surround check for fake edges by
	#ifdef ENABLE_CHECKING #endif.

Index: bb-reorder.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bb-reorder.c,v
retrieving revision 1.61
diff -c -3 -p -r1.61 bb-reorder.c
*** bb-reorder.c	11 Dec 2003 00:20:35 -0000	1.61
--- bb-reorder.c	19 Dec 2003 14:53:14 -0000
*************** copy_bb_p (basic_block bb, int code_may_
*** 1000,1005 ****
--- 1002,1009 ----
    int size = 0;
    int max_size = uncond_jump_length;
    rtx insn;
+   int n_succ;
+   edge e;
  
    if (!bb->frequency)
      return false;
*************** copy_bb_p (basic_block bb, int code_may_
*** 1007,1012 ****
--- 1011,1025 ----
      return false;
    if (!cfg_layout_can_duplicate_bb_p (bb))
      return false;
+ 
+   /* Avoid duplicating blocks which have many successors (PR/13430).  */
+   n_succ = 0;
+   for (e = bb->succ; e; e = e->succ_next)
+     {
+       n_succ++;
+       if (n_succ > 8)
+ 	return false;
+     }
  
    if (code_may_grow && maybe_hot_bb_p (bb))
      max_size *= 8;
*************** find_traces_1_round (int branch_th, int 
*** 414,421 ****
--- 414,423 ----
  	  /* Select the successor that will be placed after BB.  */
  	  for (e = bb->succ; e; e = e->succ_next)
  	    {
+ #ifdef ENABLE_CHECKING
  	      if (e->flags & EDGE_FAKE)
  		abort ();
+ #endif
  
  	      if (e->dest == EXIT_BLOCK_PTR)
  		continue;



More information about the Gcc-patches mailing list