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][2nd try] Fix PR26900, number of iterations improvement


This is an updated patch for PR26900, which does no longer rely on
the fix for PR26898.  It introduces a new function, compare_conditions
to tree-ssa-loop-niter.c which can infer the following relations between
two conditions:

 - if COND1 is true, if then COND2 is also true
 - if COND1 is true, if then !COND2 is also true

which is what # of iterations analysis queries during comparing exit
condition with dominating conditions that are true.

Bootstrapped and regtested on x86_64-unknown-linux-gnu.

Ok for mainline?

Any idea for a better name of the function?  Should it be in another place
like fold-const.c or tree.c?  Note that for some reason we now need a
patch to teach fold_binary to fold i1D.1521_6 - -1 to i1D.1521_6 + 1, I
will produce such shortly (and then add the testcase for PR26900).

Thanks,
Richard.


2006-03-30  Richard Guenther  <rguenther@suse.de>

	PR middle-end/26900
	* tree-ssa-loop-niter.c (compare_conditions): New function.
	(tree_simplify_using_condition_1): Use it.

Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c	(revision 112530)
--- tree-ssa-loop-niter.c	(working copy)
*************** expand_simple_operations (tree expr)
*** 764,769 ****
--- 764,857 ----
    return expand_simple_operations (e);
  }
  
+ /* Given two comparisons COND1 and COND2 figure out if either
+    COND2 is always true if COND1 is true or if COND2 is always false
+    if COND1 is true.  Returns boolean_true_node in the first case,
+    boolean_false_node in the second one and NULL_TREE, if we cannot
+    prove either of the relations.  */
+ 
+ static tree
+ compare_conditions (tree cond1, tree cond2)
+ {
+   tree lhs1, lhs2, rhs1, rhs2;
+ 
+   /* Only handle comparisons.  */
+   if (!COMPARISON_CLASS_P (cond1)
+       || !COMPARISON_CLASS_P (cond2))
+     return NULL_TREE;
+ 
+   /* Canonicalize to SSA_NAME CMP Y.  */
+   lhs1 = TREE_OPERAND (cond1, 0);
+   rhs1 = TREE_OPERAND (cond1, 1);
+   if (TREE_CODE (lhs1) != SSA_NAME
+       && TREE_CODE (rhs1) == SSA_NAME)
+     {
+       cond1 = build2 (swap_tree_comparison (TREE_CODE (cond1)),
+ 		      boolean_type_node, rhs1, lhs1);
+       lhs1 = TREE_OPERAND (cond1, 0);
+       rhs1 = TREE_OPERAND (cond1, 1);
+     }
+   lhs2 = TREE_OPERAND (cond2, 0);
+   rhs2 = TREE_OPERAND (cond2, 1);
+   if (TREE_CODE (lhs2) != SSA_NAME
+       && TREE_CODE (rhs2) == SSA_NAME)
+     {
+       cond2 = build2 (swap_tree_comparison (TREE_CODE (cond2)),
+ 		      boolean_type_node, rhs2, lhs2);
+       lhs2 = TREE_OPERAND (cond2, 0);
+       rhs2 = TREE_OPERAND (cond2, 1);
+     }
+ 
+   /* If lhs are not SSA_NAME, bail out.  */
+   if (TREE_CODE (lhs1) != SSA_NAME
+       || TREE_CODE (lhs2) != SSA_NAME)
+     return NULL_TREE;
+ 
+   /* Canonicalize to (possibly) the same SSA_NAME on the lhs of both
+      conditions.  */
+   if (lhs1 != lhs2
+       && TREE_CODE (rhs2) == SSA_NAME)
+     {
+       cond2 = build2 (swap_tree_comparison (TREE_CODE (cond2)),
+ 		      boolean_type_node, rhs2, lhs2);
+       lhs2 = TREE_OPERAND (cond2, 0);
+       rhs2 = TREE_OPERAND (cond2, 1);
+     }
+   /* If there is a constant on the rhs we can move it
+      to the rhs without caring for overflow as we only use the new
+      condition to compare it against the other one.  Any other
+      garbage we produce will also fail the comparison tests below.  */
+   else if (lhs1 != lhs2
+            && (TREE_CODE (rhs2) == PLUS_EXPR
+ 	       || TREE_CODE (rhs2) == MINUS_EXPR))
+     {
+       cond2 = build2 (swap_tree_comparison (TREE_CODE (cond2)),
+ 		      boolean_type_node,
+ 		      TREE_OPERAND (rhs2, 0),
+ 		      fold_build2 (TREE_CODE (rhs2) == PLUS_EXPR
+ 				   ? MINUS_EXPR : PLUS_EXPR,
+ 				   TREE_TYPE (lhs2),
+ 				   lhs2, TREE_OPERAND (rhs2, 1)));
+       lhs2 = TREE_OPERAND (cond2, 0);
+       rhs2 = TREE_OPERAND (cond2, 1);
+     }
+ 
+   /* Verify that now both lhs and rhs are equal.  */
+   if (lhs1 != lhs2
+       || !operand_equal_p (rhs1, rhs2, 0))
+     return NULL_TREE;
+ 
+   /* Same condition, cond2 is true if cond1 is true.  */
+   if (TREE_CODE (cond1) == TREE_CODE (cond2))
+     return boolean_true_node;
+ 
+   /* Negated condition, !cond2 is true if cond1 is true.  */
+   if (TREE_CODE (cond1) == invert_tree_comparison (TREE_CODE (cond2), false))
+     return boolean_false_node;
+ 
+   return NULL_TREE;
+ }
+ 
  /* Tries to simplify EXPR using the condition COND.  Returns the simplified
     expression (or EXPR unchanged, if no simplification was possible).  */
  
*************** tree_simplify_using_condition_1 (tree co
*** 858,863 ****
--- 946,955 ----
  
    te = expand_simple_operations (expr);
  
+   e = compare_conditions (cond, te);
+   if (e)
+     return e;
+ 
    /* Check whether COND ==> EXPR.  */
    notcond = invert_truthvalue (cond);
    e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);


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