PATCH: fix PR tree-optimization/39874

[Richard Guenther]

On Tue, Jun 1, 2010 at 2:32 AM, Sandra Loosemore
<sandra@codesourcery.com> wrote:
> This patch adds some more sophisticated logic for simplifying logical AND
> and OR expressions to fix PR39874, one of the sub-cases of PR28685.
>
> The test case illustrates the problem:
>
> void func();
> void test(char *signature)
> {
>  char ch = signature[0];
>  if (ch == 15 || ch == 3)
>  {
>    if (ch == 15) func();
>  }
> }
>
> Here, the ifcombine pass was being too stupid to optimize away the outer
> "if" because it was relying on combine_comparisons only to detect when it
> can do that.  So, the basic idea of my patch is to provide better logic for
> optimizing logical ANDs and ORs in the ifcombine pass.  I recently added a
> patch to tree_ssa_reassoc that also used combine_comparisons for a similar
> purpose to fix another one of the PR28685 sub-cases, and my new functions
> can apply there as well.
>
> This patch didn't really start out being quite this complicated, but once I
> got started I figured I might as well add all the usual boolean identities
> and comparison simplifications.  Much of this duplicates simplifications
> that are performed on trees in fold-const.c, but my code deals with gimple
> representations and simplifications that can be performed by
> copy-propagating SSA variables.  (E.g., in the example above, the "ch == 15"
> expression is PRE'ed coming into the ifcombine pass.)
>
> This patch passed 3-stage bootstrap and testing on native x86_64 Linux.  I
> also tested on ARM Linux, and ran SPEC benchmarks on ARM to make sure this
> wasn't accidentally un-optimizing something else.  OK to check in?

+                           fold_convert (TREE_TYPE (expr), integer_zero_node));

use build_int_cst (TREE_TYPE (expr), 0).

+/* Check to see if a boolean expression OP0 is logically equivalent to the
+   comparison (OP1 CODE OP2).  Check for various identities involving
+   SSA_NAMEs.  */
+
+static bool
+same_bool_comparison_p (const_tree op0, enum tree_code code,
+                       const_tree op1, const_tree op2)

I think op0 is an unfortunate name, 'expr' would be better.

+      if (is_gimple_assign (s = SSA_NAME_DEF_STMT (op0)))
+       {

please move the assignment before the if ().

+  /* If op1 is of the form (name != 0) or (name == 0), and the definition
+     of name is a comparison, recurse.  */
+  if (TREE_CODE (op1) == SSA_NAME
+      && TREE_TYPE (op1) == boolean_type_node
+      && is_gimple_assign (s = SSA_NAME_DEF_STMT (op1))

likewise.

Instead of testing for equality to boolean_type_node please
replace the checks with a check for TREE_CODE (TREE_TYPE (op1)) == BOOLEAN_TYPE.

+  if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op2) == INTEGER_CST)
+    return operand_equal_p (op1, op2, 0);

tree_int_cst_equal ()

you fall back to operand_equal_p later, so why not do that test
here first like

  if (operand_equal_p (op1, op2, 0))
    return true;

and fall back to return false?

+      if ((code2 == NE_EXPR && integer_zerop (op2b))
+         || (code2 == EQ_EXPR && integer_nonzerop (op2b)))

I see this pattern in multiple places - as you check for
BOOLEAN_TYPE on var and later do an equality comparison
with op2a you know that that also has BOOLEAN_TYPE and
thus we should have canonicalized bool == 1 to plain bool
by fold.

+      /* maybe_fold_and_comparisons and maybe_fold_or_comparisons
+        always give us a boolean_type_node value back.  If the original
+        BIT_AND_EXPR or BIT_IOR_EXPR was of a wider integer type,
+        we need to convert.  */
+      t = fold_convert (TREE_TYPE (curr->op), t);

guard this with if (!useless_type_conversion_p (TREE_TYPE (curr->op),
TREE_TYPE (t))

Overall the patch is large and it feels like it duplicates a lot of
code from fold-const (but indeed in a better way, without building
trees all the time).  Please give others the chance to review it (I
know I get distracted after a while when looking at large patches like
this ... ;)).

Thus - the patch is ok if nobody dares to give it another look within a week.

Thanks,
Richard.

> -Sandra
>
>
> 2010-05-31  Sandra Loosemore  <sandra@codesourcery.com>
>
>        PR tree-optimization/39874
>        PR middle-end/28685
>
>        gcc/
>        * gimple.h (maybe_fold_and_comparisons, maybe_fold_or_comparisons):
>        Declare.
>        * gimple-fold.c (canonicalize_bool, same_bool_comparison_p,
>        same_bool_result_p): New.
>        (and_var_with_comparison, and_var_with_comparison_1,
>        and_comparisons_1, and_comparisons, maybe_fold_and_comparisons): New.
>        (or_var_with_comparison, or_var_with_comparison_1,
>        or_comparisons_1, or_comparisons, maybe_fold_or_comparisons): New.
>        * tree-ssa-reassoc.c (eliminate_redundant_comparison): Use
>        maybe_fold_and_comparisons or maybe_fold_or_comparisons instead
>        of combine_comparisons.
>        * tree-ssa-ifcombine.c (ifcombine_ifandif, ifcombine_iforif):
> Likewise.
>
>        gcc/testsuite/
>        * gcc.dg/pr39874.c: New file.
>