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]

[Patch] Fix for PR middle-end/38059, Compile time regression


The test gcc.dg/20020425-1.c compiles in less then 1 second on my IA64
box using GCC 4.3.1 but takes 50+ seconds using the ToT GCC.

In examining the compilation slowdown of this test I found that all the
time was being spent in the 'useless' pass of GCC which is supposed to
be a quick pass to throw out obviously useless code so that the rest
of the compiler doesn't have to analyze it and can run quicker.

20020425-1.c is a worst case test for this pass consisting of:

if (0) {} else if (0) {} else if (0) {} .....  11,000 times....

useless is changing all of the if's into 'goto else-label' which
is fine but then we wind up with this (simplified) code:

goto L1; goto L2; goto L3; L3; L2; L1

but instead of 3 goto's and label's we have thousands.

The useless pass makes a complete pass of this routine, finds the
innermost 'goto L3; L3:' and removes it, then because it made a change,
it does a complete second pass through the routine and removes 'goto L2;'.
Having made another change it does a third pass, etc, removing 1 goto
in each complete pass through the routine.

This is highly inefficient and is causing the huge compile time slowdown
for the test.  On my slow HPPA box it takes long enough to time out in
the testsuite.

While it would be possible to do this optimization more efficiently,
I decided to first see what would happen if we just removed it.

Removing it gave me the same generated code as before both on this test
and on some GCC source files I compiled because the goto optimization
being done by the useless pass was now being done by the cfg pass and
I got exactly the same code as before (modulo a few label name changes).

20020425-1.c compiles in less then 5 seconds with this change instead
of taking more then 50 seconds and the compilation speed of 'real'
files did not change much at all (+/- 0.5%) with or without optimization
turned on.

Given this I think that just removing the optimization makes more sense
then trying to re-implementing it in a more efficient manner.

The following patch was tested on IA64 HP-UX and Linux and resulted in
no regressions.

OK to checkin?


2008-11-21  Steve Ellcey  <sje@cup.hp.com>

	PR middle-end/38059
	* tree-cfg.c (struct rus_data): Remove has_label, last_was_goto,
	last_goto_gsi fields.
	(remove_useless_stmts_cond): Remove last_goto_gsi, last_was_goto.
	(remove_useless_stmts_tf): Remove last_was_goto.
	(remove_useless_stmts_tc): Ditto.
	(remove_useless_stmts_goto): Remove.
	(remove_useless_stmts_label): Remove.
	(remove_useless_stmts_1): Remove GIMPLE_LABEL case, change
	GIMPLE_GOTO case, remove last_was_goto.


Index: tree-cfg.c
===================================================================
--- tree-cfg.c	(revision 142076)
+++ tree-cfg.c	(working copy)
@@ -1479,9 +1479,6 @@ struct rus_data
   bool repeat;
   bool may_throw;
   bool may_branch;
-  bool has_label;
-  bool last_was_goto;
-  gimple_stmt_iterator last_goto_gsi;
 };
 
 
@@ -1558,8 +1555,6 @@ remove_useless_stmts_cond (gimple_stmt_i
       tree then_label = gimple_cond_true_label (stmt);
 
       gsi_replace (gsi, gimple_build_goto (then_label), false);
-      data->last_goto_gsi = *gsi;
-      data->last_was_goto = true;
       data->repeat = true;
     }
   else if (gimple_cond_false_p (stmt))
@@ -1568,8 +1563,6 @@ remove_useless_stmts_cond (gimple_stmt_i
       tree else_label = gimple_cond_false_label (stmt);
 
       gsi_replace (gsi, gimple_build_goto (else_label), false);
-      data->last_goto_gsi = *gsi;
-      data->last_was_goto = true;
       data->repeat = true;
     }
   else
@@ -1581,15 +1574,11 @@ remove_useless_stmts_cond (gimple_stmt_i
         {
           /* Goto common destination.  */
           gsi_replace (gsi, gimple_build_goto (then_label), false);
-          data->last_goto_gsi = *gsi;
-          data->last_was_goto = true;
 	  data->repeat = true;
 	}
     }
 
   gsi_next (gsi);
-
-  data->last_was_goto = false;
 }
 
 /* Helper for remove_useless_stmts_1. 
@@ -1611,7 +1600,6 @@ remove_useless_stmts_tf (gimple_stmt_ite
   save_may_throw = data->may_throw;
   data->may_branch = false;
   data->may_throw = false;
-  data->last_was_goto = false;
 
   eval_seq = gimple_try_eval (stmt);
   eval_gsi = gsi_start (eval_seq);
@@ -1621,7 +1609,6 @@ remove_useless_stmts_tf (gimple_stmt_ite
   this_may_throw = data->may_throw;
   data->may_branch |= save_may_branch;
   data->may_throw |= save_may_throw;
-  data->last_was_goto = false;
 
   cleanup_seq = gimple_try_cleanup (stmt);
   cleanup_gsi = gsi_start (cleanup_seq);
@@ -1674,7 +1661,6 @@ remove_useless_stmts_tc (gimple_stmt_ite
   /* Collect may_throw information for the body only.  */
   save_may_throw = data->may_throw;
   data->may_throw = false;
-  data->last_was_goto = false;
 
   eval_seq = gimple_try_eval (stmt);
   eval_gsi = gsi_start (eval_seq);
@@ -1704,7 +1690,6 @@ remove_useless_stmts_tc (gimple_stmt_ite
   this_may_throw = true;
   cleanup_gsi = gsi_start (cleanup_seq);
   stmt = gsi_stmt (cleanup_gsi);
-  data->last_was_goto = false;
 
   switch (gimple_code (stmt))
     {
@@ -1717,7 +1702,6 @@ remove_useless_stmts_tc (gimple_stmt_ite
 	     propagate exceptions past this point.  */
 	  if (gimple_catch_types (stmt) == NULL)
 	    this_may_throw = false;
-	  data->last_was_goto = false;
           handler_seq = gimple_catch_handler (stmt);
           handler_gsi = gsi_start (handler_seq);
 	  remove_useless_stmts_1 (&handler_gsi, data);
@@ -1799,61 +1783,6 @@ remove_useless_stmts_bind (gimple_stmt_i
     gsi_next (gsi);
 }
 
-/* Helper for remove_useless_stmts_1.  Handle GIMPLE_GOTO statements.  */
-
-static void
-remove_useless_stmts_goto (gimple_stmt_iterator *gsi, struct rus_data *data)
-{
-  gimple stmt = gsi_stmt (*gsi);
-
-  tree dest = gimple_goto_dest (stmt);
-
-  data->may_branch = true;
-  data->last_was_goto = false;
-
-  /* Record iterator for last goto expr, so that we can delete it if unnecessary.  */
-  if (TREE_CODE (dest) == LABEL_DECL)
-    {
-      data->last_goto_gsi = *gsi;
-      data->last_was_goto = true;
-    }
-
-  gsi_next(gsi);
-}
-
-/* Helper for remove_useless_stmts_1.  Handle GIMPLE_LABEL statements.  */
-
-static void
-remove_useless_stmts_label (gimple_stmt_iterator *gsi, struct rus_data *data)
-{
-  gimple stmt = gsi_stmt (*gsi);
-
-  tree label = gimple_label_label (stmt);
-
-  data->has_label = true;
-
-  /* We do want to jump across non-local label receiver code.  */
-  if (DECL_NONLOCAL (label))
-    data->last_was_goto = false;
-
-  else if (data->last_was_goto
-           && gimple_goto_dest (gsi_stmt (data->last_goto_gsi)) == label)
-    {
-      /* Replace the preceding GIMPLE_GOTO statement with
-         a GIMPLE_NOP, which will be subsequently removed.
-         In this way, we avoid invalidating other iterators
-         active on the statement sequence.  */
-      gsi_replace(&data->last_goto_gsi, gimple_build_nop(), false);
-      data->last_was_goto = false;
-      data->repeat = true;
-    }
-
-  /* ??? Add something here to delete unused labels.  */
-
-  gsi_next (gsi);
-}
-
-
 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
 
 void
@@ -1895,17 +1824,13 @@ remove_useless_stmts_1 (gimple_stmt_iter
           break;
 
         case GIMPLE_GOTO:
-          remove_useless_stmts_goto (gsi, data);
-          break;
-
-        case GIMPLE_LABEL:
-          remove_useless_stmts_label (gsi, data);
+	  data->may_branch = true;
+ 	  gsi_next(gsi);
           break;
 
         case GIMPLE_ASSIGN:
           fold_stmt (gsi);
           stmt = gsi_stmt (*gsi);
-          data->last_was_goto = false;
           if (stmt_could_throw_p (stmt))
             data->may_throw = true;
           gsi_next (gsi);
@@ -1913,14 +1838,12 @@ remove_useless_stmts_1 (gimple_stmt_iter
 
         case GIMPLE_ASM:
           fold_stmt (gsi);
-          data->last_was_goto = false;
           gsi_next (gsi);
           break;
 
         case GIMPLE_CALL:
           fold_stmt (gsi);
           stmt = gsi_stmt (*gsi);
-          data->last_was_goto = false;
           if (is_gimple_call (stmt))
             notice_special_calls (stmt);
 
@@ -1937,7 +1860,6 @@ remove_useless_stmts_1 (gimple_stmt_iter
 
         case GIMPLE_RETURN:
           fold_stmt (gsi);
-          data->last_was_goto = false;
           data->may_branch = true;
           gsi_next (gsi);
           break;
@@ -1969,7 +1891,6 @@ remove_useless_stmts_1 (gimple_stmt_iter
             gimple_stmt_iterator pre_body_gsi = gsi_start (pre_body_seq);
 
             remove_useless_stmts_1 (&pre_body_gsi, data);
-	    data->last_was_goto = false;
           }
           /* FALLTHROUGH */
         case GIMPLE_OMP_CRITICAL:
@@ -1984,7 +1905,6 @@ remove_useless_stmts_1 (gimple_stmt_iter
             gimple_stmt_iterator body_gsi = gsi_start (body_seq);
 
             remove_useless_stmts_1 (&body_gsi, data);
-	    data->last_was_goto = false;
 	    gsi_next (gsi);
           }
           break;
@@ -2000,7 +1920,6 @@ remove_useless_stmts_1 (gimple_stmt_iter
             gimple_stmt_iterator bind_gsi = gsi_start (bind_seq);
 
             remove_useless_stmts_1 (&bind_gsi, data);
-	    data->last_was_goto = false;
 	    gsi_next (gsi);
           }
           break;
@@ -2011,14 +1930,12 @@ remove_useless_stmts_1 (gimple_stmt_iter
 	     during alias computation otherwise.  */
 	  if (!optimize)
 	    {
-	      data->last_was_goto = false;
 	      gsi_remove (gsi, false);
 	      break;
 	    }
 	  /* Fallthru.  */
 
         default:
-          data->last_was_goto = false;
           gsi_next (gsi);
           break;
         }


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