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: 15855 [3.4/4.0 Regression] g++ crash with -O2 and -O3 on inputfile


Tee hee hee.  

This bug exposes a lot of issues with the SSA analysis, optimization
and checking code.  I wouldn't be terribly surprised if we can't address
all the issues before GCC 4.0.

On my box, the clearest loser is the alias analysis checking which gets
charged to SSA verification -- I'm not attacking that problem yet.

I will however take a stab at some sillyness in the alias analysis 
code.

compute_flow_insensitive_aliasing has code like:

      for (j = 0; j < ai->num_addressable_vars; j++)
        {
          struct alias_map_d *v_map;
          var_ann_t v_ann;
          tree var;
          bool tag_stored_p, var_stored_p;
          
          v_map = ai->addressable_vars[j];
          var = v_map->var;
          v_ann = var_ann (var);

          /* Skip memory tags and variables that have never been
             written to.  We also need to check if the variables are
             call-clobbered because they may be overwritten by
             function calls.  */
          tag_stored_p = bitmap_bit_p (ai->written_vars, tag_ann->uid)
                         || is_call_clobbered (tag);
          var_stored_p = bitmap_bit_p (ai->written_vars, v_ann->uid)
                         || is_call_clobbered (var);


What's important to note here is that we're randomly accessing
elements in the sparse bitmap instead of visiting them in order.

Access to random elements in our sparse bitmaps can be expensive
as we have to walk a list to find the bitmap word with the right
bit in it.   OUCH.  Reversing the bitmap & call-clobbered test
helps significantly.

Before this patch:

 tree alias analysis   :  15.96 (12%) usr
 TOTAL                 : 137.46


After this patch:
 tree alias analysis   :   6.65 ( 5%) usr
 TOTAL                 : 126.80

Not a bad start.


Bootstrapped and regression tested on i686-pc-linux-gnu.


	* tree-ssa-alias.c (compute_flow_insensitive_aliasing): Reduce
	the number of queries to random elements in the ai->written_vars
	bitmap.


Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.56
diff -c -p -r2.56 tree-ssa-alias.c
*** tree-ssa-alias.c	24 Nov 2004 14:46:23 -0000	2.56
--- tree-ssa-alias.c	25 Nov 2004 00:26:19 -0000
*************** compute_flow_insensitive_aliasing (struc
*** 921,931 ****
  	  /* Skip memory tags and variables that have never been
  	     written to.  We also need to check if the variables are
  	     call-clobbered because they may be overwritten by
! 	     function calls.  */
! 	  tag_stored_p = bitmap_bit_p (ai->written_vars, tag_ann->uid)
! 			 || is_call_clobbered (tag);
! 	  var_stored_p = bitmap_bit_p (ai->written_vars, v_ann->uid)
! 			 || is_call_clobbered (var);
  	  if (!tag_stored_p && !var_stored_p)
  	    continue;
  	     
--- 921,936 ----
  	  /* Skip memory tags and variables that have never been
  	     written to.  We also need to check if the variables are
  	     call-clobbered because they may be overwritten by
! 	     function calls.
! 
! 	     Note this is effectively random accessing elements in
! 	     the sparse bitset, which can be highly inefficient.
! 	     So we first check the call_clobbered status of the
! 	     tag and variable before querying the bitmap.  */
! 	  tag_stored_p = is_call_clobbered (tag)
! 			 || bitmap_bit_p (ai->written_vars, tag_ann->uid);
! 	  var_stored_p = is_call_clobbered (var)
! 			 || bitmap_bit_p (ai->written_vars, v_ann->uid);
  	  if (!tag_stored_p && !var_stored_p)
  	    continue;
  	     

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