This is the mail archive of the 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] tree-cfg.c: Speed up find_taken_edge.


Attached is a patch to speed up find_taken_edge.

Here is what's happening.

A lot of passes calls cleanup_tree_cfg.

Via the following call tree, find_taken_edge is called on every
conditional jump in the instruction stream.


Since find_taken_edge calls fold to fold a given value, we burn a lot
of cycles there.

Note that find_taken_edge won't be able to determine which edge is
taken if we pass it an expression like a > b.  It can do useful things
only when we pass it an INTEGER_CST or something that folds to an
INTEGER_CST like a == a.

The patch removes fold in find_taken_edge.  There is no point
repeatedly trying to fold conditoinals that cannot be folded.  If they
can be folded via constant/copy propagation, passes like DOM and CCP
would fold them anyway.

I should note two things.

1. When cleanup_tree_cfg is called for the first time, we can fold some
   conditions, so I created fold_cond_expr_cond to fold conditionals
   immediately before calling cleanup_tree_cfg for the first time.
   Even then COND_EXPR_CONDs that we can fold is less than 0.05% of
   all COND_EXPR_CONDs in cc1 files.  I vaguely remember C++ testcases
   had a little more foldable COND_EXPR_CONDs at this point when I
   tested this patch several months ago.  I could get this number for
   you if you are interested.

2. There are some rare cases where fold in find_taken_edge is
   useful.  TER stuffs a big conditional into COND_EXPR_COND.  Having
   more information, fold in find_taken_edge can fold the condition to
   a constant.  This only happens only a few times during the
   bootstrap. If this missed optimization bothers you, we could call
   fold_cond_expr_cond before calling cleanup_tree_cfg for the last
   time, but do note that we would be papering over missed constant
   propagation opportunities at a wrong place.

Here is a timing in seconds for five runs of ./cc1 -quiet -O2 -o

               original patched   diff%
c-common.i       18.152  18.117 -0.192%
combine.i        16.689  16.584 -0.629%
fold-const.i     37.712  37.483 -0.607%
reload1.i        13.172  13.102 -0.531%
reload.i         12.110  12.007 -0.850%
insn-attrtab.i  236.465 235.329 -0.480%

There is no difference in generated code among cc1 files with or
without this patch..

Tested on i686-pc-linux-gnu.  OK to apply?

Kazu Hirata

2005-02-20  Kazu Hirata  <>

	* tree-cfg.c (fold_cond_expr_cond): New.
	(make_edges): Call fold_cond_expr_cond.
	(find_taken_edge): Accept nothing but INTEGER_CST.
	(find_taken_edge_cond_expr): Reject INTEGER_CST other than 0
	and 1.
	(find_taken_edge_switch_expr): Remove a check for INTEGER_CST.

Index: tree-cfg.c
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.150
diff -u -d -p -r2.150 tree-cfg.c
--- tree-cfg.c	17 Feb 2005 16:19:37 -0000	2.150
+++ tree-cfg.c	20 Feb 2005 23:46:56 -0000
@@ -440,6 +440,29 @@ create_bb (void *h, void *e, basic_block
 				 Edge creation
+/* Fold COND_EXPR_COND of each COND_EXPR.  */
+static void
+fold_cond_expr_cond (void)
+  basic_block bb;
+  FOR_EACH_BB (bb)
+    {
+      tree stmt = last_stmt (bb);
+      if (stmt
+	  && TREE_CODE (stmt) == COND_EXPR)
+	{
+	  tree cond = fold (COND_EXPR_COND (stmt));
+	  if (integer_zerop (cond))
+	    COND_EXPR_COND (stmt) = integer_zero_node;
+	  else if (integer_onep (cond))
+	    COND_EXPR_COND (stmt) = integer_one_node;
+	}
+    }
 /* Join all the blocks in the flowgraph.  */
 static void
@@ -478,6 +501,9 @@ make_edges (void)
      builder inserted for completeness.  */
   remove_fake_exit_edges ();
+  /* Fold COND_EXPR_COND of each COND_EXPR.  */
+  fold_cond_expr_cond ();
   /* Clean up the graph and warn for unreachable code.  */
   cleanup_tree_cfg ();
@@ -2198,14 +2224,7 @@ find_taken_edge (basic_block bb, tree va
   gcc_assert (is_ctrl_stmt (stmt));
   gcc_assert (val);
-  /* If VAL is a predicate of the form N RELOP N, where N is an
-     SSA_NAME, we can usually determine its truth value.  */
-  if (COMPARISON_CLASS_P (val))
-    val = fold (val);
-  /* If VAL is not a constant, we can't determine which edge might
-     be taken.  */
-  if (!really_constant_p (val))
+  if (TREE_CODE (val) != INTEGER_CST)
     return NULL;
   if (TREE_CODE (stmt) == COND_EXPR)
@@ -2237,12 +2256,12 @@ find_taken_edge_cond_expr (basic_block b
     return true_edge;
   else if (integer_zerop (val))
     return false_edge;
-  else
-    return NULL;
+  gcc_unreachable ();
-/* Given a constant value VAL and the entry block BB to a SWITCH_EXPR
+/* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
    statement, determine which edge will be taken out of the block.  Return
    NULL if any edge may be taken.  */
@@ -2253,9 +2272,6 @@ find_taken_edge_switch_expr (basic_block
   basic_block dest_bb;
   edge e;
-  if (TREE_CODE (val) != INTEGER_CST)
-    return NULL;
   switch_expr = last_stmt (bb);
   taken_case = find_case_label_for_value (switch_expr, val);
   dest_bb = label_to_block (CASE_LABEL (taken_case));

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