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]

[tree-ssa] Eliminate unnecessary gimplifications


[ This is long...  First we have some background info which got me looking
  at this problem, then some analysis of the benefits of fixing the 
  problem, issues when trying to fix the problem and finally the patch.
  Skip to whatever you find interesting. ]


While looking at some of the cases where we create a lot more RTL than
is really necessary on the tree-ssa branch, I cam across an interesting
implementation detail.

Specifically, simplify_expr does not check and see if the given expression
is already in simple form -- ie just runs the simplifiers blindly and
checks for simple form after running the simplifiers.

In addition to being potentially inefficient, it tends to create unnecessary
code.  Consider:


shit()
{
        blah ("fu", "bar", "com");
}


That results in this gimplified code:


shit ()
{
  char[3] * T.1;
  char * T.2;
  char[4] * T.3;
  char * T.4;
  char[4] * T.5;
  char * T.6;
  extern  blah;

  T.1 = "fu";
  T.2 = (char *)T.1;
  T.3 = "bar";
  T.4 = (char *)T.3;
  T.5 = "com";
  T.6 = (char *)T.5;
  blah (T.2, T.4, T.6)
}


What's terrible about this is the NOP type casts are allowed by the
predicate for argument lists.  The only reason we create the temporaries
and emit the casts in the assignments to those temporaries is because
we gimplify expressions which are already in gimple form.

Worse yet, because of the way we handle aliasing, we end up with a 
series of stores which can not be removed by DCE.  Basically anytime
we pass a string to a function, we're going to end up with useless
code DCE can not remove.  If you look at the .optimized dump you'll
see what I mean:

;; Function shit (shit)
        
shit ()
{       
  char[3] * T.1;
  char * T.2;
  char[4] * T.3;
  char * T.4;
  char[4] * T.5;
  char * T.6;
  extern  blah;

  T.2 = (char *)"fu";
  T.4 = (char *)"bar";
  T.6 = (char *)"com";
  blah ((char *)"fu", (char *)"bar", (char *)"com")
} 



T.2, T.4 and T.6 are never used, but due to our handling of aliases and
virtual operands, we can not remove them.

Sigh.



Now if we change simplify_expr to do nothing when presented with an
expression which satisfies its predicate we'll end up with something
like this after gimplification:

shit ()
{
  extern  blah;

  blah ((char *)"fu", (char *)"bar", (char *)"com")
}


Which is exactly what we want.  We didn't create any useless variables and
we didn't create any useless assignments.

Now I know Diego is revamping virtual ops and aliasing, but I think this
is still worth fixing.....  Here's why...

-----

I had speculated that such a change to avoid silly gimplifications may in
fact speed up gimplification.   In fact, using the components of cc1 + the
components of libstdc++ I see about a 10% reduction in time charged to
gimplification.

Better yet, we get reductions in the time charged to all the SSA passes
after gimplification:

  CFG construction   3.78 seconds ->  3.45 seconds
  Alias analysis     5.82 seconds ->  5.49 seconds
  PHI Insertion      2.64 seconds ->  2.57 seconds
  REWRITE into SSA   7.69 seconds ->  7.07 seconds
  SSA CCP           10.07 seconds ->  9.03 seconds
  SSA DCE            9.51 seconds ->  8.48 seconds
  SSA->Normal       16.97 seconds -> 16.02 seconds

My theory is that avoiding over-gimplification is avoiding creation of
unnecessary statements which reduces the load for all the following
SSA passes.

This theory is supported by a reduction in garbage collection time as well:

  Garbage           10.18 seconds ->  9.62 seconds

In fact I also see reductions in time spent in the RTL optimizers.  Presumably
because we're creating less crud for them to process.  For example:

  1st CSE           67.70 seconds -> 66.15 seconds
  GCSE              38.62 seconds -> 37.63 seconds
  jump               8.61 seconds ->  8.44 seconds
  trivial dead      13.06 seconds -> 12.83 seconds


Overall for my test we got an improvement of just over 10 seconds, or
about 1.3% by not gimplifying expressions which were already in gimple
form.

------

Soooo, onward to the implementation of this concept.  It was surprisingly
simple (no pun intended).

First, the mental model is that if an expression is already in gimple
form according to its predicate then we should not gimplify the expression.

Thus if a predicate returns true for an expression which is not in gimple
form, then that predicate is buggy.  Surprisingly my tests to date have
only found a couple bogus predicates:

  is_simple_stmt -- this is the mother of all bogus predicates.  It always
  returns 1.  I haven't tried to fix this one yet.

  is_simple_constructor -- this predicate returned nonzero when presented
  with a constructor for a static object.  That's incorrect as we need
  to at least examine certain static objects (for things like label addresses).

  is_simple_addr_expr_arg -- this predicate returned nonzero when 
  presented with the address of a label -- we need to run such expressions
  through the gimplifier to ensure that we mark such labels as special.


That's it.  Wow.  That was a *very* pleasant surprise.  I was expecting to
run into all kinds of interesting problems.



Enjoy.

	* gimplify.c (simplify_expr): Avoid gimplifying expressions which
	are already in gimple form.
	* tree-simple.c (is_simple_constructor): No longer treat TREE_STATIC
	constructors specially.
	(is_simple_addr_expr_arg): If we're taking the address of a label
	for the first time, then the ADDR_EXPR is not in gimple form.
	

Index: gimplify.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/gimplify.c,v
retrieving revision 1.1.2.42
diff -c -3 -p -r1.1.2.42 gimplify.c
*** gimplify.c	21 May 2003 15:33:26 -0000	1.1.2.42
--- gimplify.c	23 May 2003 14:15:56 -0000
*************** simplify_expr (expr_p, pre_p, post_p, si
*** 341,346 ****
--- 341,360 ----
    if (*expr_p == NULL_TREE)
      return 1;
  
+   /* Go ahead and strip type nops before we test our predicate.  */
+   STRIP_MAIN_TYPE_NOPS (*expr_p);
+ 
+   /* Avoid gimplifying an expression that is already in gimple form
+      according to our predicate.
+ 
+      Unfortunately the predicate is_simple_stmt always returns
+      true, regardless of the structure of the underlying tree, so
+      if that is our predicate, then we bypass this test and 
+      force gimplification of the expression.  FIXME, someone
+      should fix is_simple_stmt.  */
+   if (simple_test_f != is_simple_stmt && (*simple_test_f) (*expr_p))
+     return 1;
+ 
    saved_input_filename = NULL;	/* [GIMPLE] Avoid uninitialized use warning.  
*/
    saved_lineno = -1;		/* [GIMPLE] Avoid uninitialized use warning.  */
  
Index: tree-simple.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-simple.c,v
retrieving revision 1.1.4.34
diff -c -3 -p -r1.1.4.34 tree-simple.c
*** tree-simple.c	13 May 2003 19:45:00 -0000	1.1.4.34
--- tree-simple.c	23 May 2003 14:15:56 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 180,186 ****
  
     This is an extension to SIMPLE.  Perhaps CONSTRUCTORs should be
     eliminated entirely?  */
!    
  int
  is_simple_constructor (t)
       tree t;
--- 180,186 ----
  
     This is an extension to SIMPLE.  Perhaps CONSTRUCTORs should be
     eliminated entirely?  */
! 
  int
  is_simple_constructor (t)
       tree t;
*************** is_simple_constructor (t)
*** 190,197 ****
    if (TREE_CODE (t) != CONSTRUCTOR)
      return 0;
  
!   if (TREE_STATIC (t))
!     return 1;
  
    for (elt_list = CONSTRUCTOR_ELTS (t); elt_list;
         elt_list = TREE_CHAIN (elt_list))
--- 190,198 ----
    if (TREE_CODE (t) != CONSTRUCTOR)
      return 0;
  
!   /* We used to return nonzero if TREE_STATIC (t) was set.  This
!      is wrong as we want to look inside constructors for static
!      variables for things like label addresses.  */
  
    for (elt_list = CONSTRUCTOR_ELTS (t); elt_list;
         elt_list = TREE_CHAIN (elt_list))
*************** int
*** 566,571 ****
--- 567,577 ----
  is_simple_addr_expr_arg (t)
       tree t;
  {
+   /* If we're taking the address of a label for the first time, then
+      this expression is not in gimple form.  */
+   if (TREE_CODE (t) == LABEL_DECL && ! FORCED_LABEL (t))
+     return 0;
+ 
    return (is_simple_varname (t) || is_simple_call_expr (t));
  }
  








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