Patchwork [tree-optimization] : Improve handling of conditional-branches on targets with high branch costs

login
register
mail settings
Submitter Kai Tietz
Date Oct. 14, 2011, 7:43 p.m.
Message ID <CAEwic4Y4gZEeZ+Hz1x6UKuMTTGR_j4Nq+kC0zo7T3z_eHDbYDg@mail.gmail.com>
Download mbox | patch
Permalink /patch/119911/
State New
Headers show

Comments

Kai Tietz - Oct. 14, 2011, 7:43 p.m.
Hello,

So I committed the gimplify patch separate.  And here is the remaining
fold-const patch.
The important tests here are in gcc.dg/tree-ssa/builtin-expect[1-4].c, which
cover the one special-case for branching. Also tree-ssa/20040204-1.c covers
tests for branching code (on targets having high-engough BRANCH_COST and no
special-casing - like MIPS, S/390, and AVR.

ChangeLog

2011-10-14  Kai Tietz  <ktietz@redhat.com>

	* fold-const.c (simple_operand_p_2): New function.
	(fold_truthop): Rename to
	(fold_truth_andor_1): function name.
	Additionally remove branching creation for logical and/or.
	(fold_truth_andor): Handle branching creation for logical and/or here.

Bootstrapped and regression-tested for all languages plus Ada and
Obj-C++ on x86_64-pc-linux-gnu.
Ok for apply?

Regards,
Kai

 static tree extract_muldiv (tree, tree, enum tree_code, tree, bool *);
@@ -3500,7 +3500,7 @@ optimize_bit_field_compare (location_t l
   return lhs;
 }
 
-/* Subroutine for fold_truthop: decode a field reference.
+/* Subroutine for fold_truth_andor_1: decode a field reference.

    If EXP is a comparison reference, we return the innermost reference.

@@ -3668,7 +3668,7 @@ sign_bit_p (tree exp, const_tree val)
   return NULL_TREE;
 }

-/* Subroutine for fold_truthop: determine if an operand is simple enough
+/* Subroutine for fold_truth_andor_1: determine if an operand is simple enough
    to be evaluated unconditionally.  */

 static int
@@ -3678,7 +3678,7 @@ simple_operand_p (const_tree exp)
   STRIP_NOPS (exp);

   return (CONSTANT_CLASS_P (exp)
-	  || TREE_CODE (exp) == SSA_NAME
+  	  || TREE_CODE (exp) == SSA_NAME
 	  || (DECL_P (exp)
 	      && ! TREE_ADDRESSABLE (exp)
 	      && ! TREE_THIS_VOLATILE (exp)
@@ -3692,6 +3692,46 @@ simple_operand_p (const_tree exp)
 		 registers aren't expensive.  */
 	      && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
 }
+
+/* Subroutine for fold_truth_andor: determine if an operand is simple enough
+   to be evaluated unconditionally.
+   I addition to simple_operand_p, we assume that comparisons and logic-not
+   operations are simple, if their operands are simple, too.  */
+
+static bool
+simple_operand_p_2 (tree exp)
+{
+  enum tree_code code;
+
+  /* Strip any conversions that don't change the machine mode.  */
+  STRIP_NOPS (exp);
+
+  code = TREE_CODE (exp);
+
+  if (TREE_CODE_CLASS (code) == tcc_comparison)
+    return (!tree_could_trap_p (exp)
+	    && simple_operand_p_2 (TREE_OPERAND (exp, 0))
+	    && simple_operand_p_2 (TREE_OPERAND (exp, 1)));
+
+  if (TREE_SIDE_EFFECTS (exp)
+      || tree_could_trap_p (exp))
+    return false;
+
+  switch (code)
+    {
+    case SSA_NAME:
+      return true;
+    case TRUTH_NOT_EXPR:
+      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
+    case BIT_NOT_EXPR:
+      if (TREE_CODE (TREE_TYPE (exp)) != BOOLEAN_TYPE)
+	return false;
+      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
+    default:
+      return simple_operand_p (exp);
+    }
+}
+
 
 /* The following functions are subroutines to fold_range_test and allow it to
    try to change a logical combination of comparisons into a range test.
@@ -4888,7 +4928,7 @@ fold_range_test (location_t loc, enum tr
   return 0;
 }
 
-/* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
+/* Subroutine for fold_truth_andor_1: C is an INTEGER_CST interpreted as a P
    bit value.  Arrange things so the extra bits will be set to zero if and
    only if C is signed-extended to its full width.  If MASK is nonzero,
    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
@@ -5025,8 +5065,8 @@ merge_truthop_with_opposite_arm (locatio
    We return the simplified tree or 0 if no optimization is possible.  */

 static tree
-fold_truthop (location_t loc, enum tree_code code, tree truth_type,
-	      tree lhs, tree rhs)
+fold_truth_andor_1 (location_t loc, enum tree_code code, tree truth_type,
+		    tree lhs, tree rhs)
 {
   /* If this is the "or" of two comparisons, we can do something if
      the comparisons are NE_EXPR.  If this is the "and", we can do something
@@ -5054,8 +5094,6 @@ fold_truthop (location_t loc, enum tree_
   tree lntype, rntype, result;
   HOST_WIDE_INT first_bit, end_bit;
   int volatilep;
-  tree orig_lhs = lhs, orig_rhs = rhs;
-  enum tree_code orig_code = code;

   /* Start by getting the comparison codes.  Fail if anything is volatile.
      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
@@ -5119,8 +5157,7 @@ fold_truthop (location_t loc, enum tree_
   /* If the RHS can be evaluated unconditionally and its operands are
      simple, it wins to evaluate the RHS unconditionally on machines
      with expensive branches.  In this case, this isn't a comparison
-     that can be merged.  Avoid doing this if the RHS is a floating-point
-     comparison since those can trap.  */
+     that can be merged.  */

   if (BRANCH_COST (optimize_function_for_speed_p (cfun),
 		   false) >= 2
@@ -5149,13 +5186,6 @@ fold_truthop (location_t loc, enum tree_
 			   build2 (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
 				   ll_arg, rl_arg),
 			   build_int_cst (TREE_TYPE (ll_arg), 0));
-
-      if (LOGICAL_OP_NON_SHORT_CIRCUIT)
-	{
-	  if (code != orig_code || lhs != orig_lhs || rhs != orig_rhs)
-	    return build2_loc (loc, code, truth_type, lhs, rhs);
-	  return NULL_TREE;
-	}
     }

   /* See if the comparisons can be merged.  Then get all the parameters for
@@ -8380,13 +8410,49 @@ fold_truth_andor (location_t loc, enum t
      lhs is another similar operation, try to merge its rhs with our
      rhs.  Then try to merge our lhs and rhs.  */
   if (TREE_CODE (arg0) == code
-      && 0 != (tem = fold_truthop (loc, code, type,
-				   TREE_OPERAND (arg0, 1), arg1)))
+      && 0 != (tem = fold_truth_andor_1 (loc, code, type,
+					 TREE_OPERAND (arg0, 1), arg1)))
     return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem);

-  if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
+  if ((tem = fold_truth_andor_1 (loc, code, type, arg0, arg1)) != 0)
     return tem;

+  if ((code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR)
+      && (BRANCH_COST (optimize_function_for_speed_p (cfun),
+		       false) >= 2)
+      && LOGICAL_OP_NON_SHORT_CIRCUIT
+      && simple_operand_p_2 (arg1))
+    {
+      enum tree_code ncode = (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR
+						       : TRUTH_OR_EXPR);
+
+      /* Transform ((A AND-IF B) AND-IF C) into (A AND-IF (B AND C)),
+         or ((A OR-IF B) OR-IF C) into (A OR-IF (B OR C))
+         We don't want to pack more than two leafs to a non-IF AND/OR
+         expression.
+         If tree-code of left-hand operand isn't an AND/OR-IF code and not
+         equal to CODE, then we don't want to add right-hand operand.
+         If the inner right-hand side of left-hand operand has side-effects,
+         or isn't simple, then we can't add to it, as otherwise we might
+         destroy if-sequence.  */
+      if (TREE_CODE (arg0) == code
+      	  /* Needed for sequence points to handle trappings, and
+      	     side-effects.  */
+      	  && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
+       {
+         tem = fold_build2_loc (loc, ncode, type, TREE_OPERAND (arg0, 1),
+				arg1);
+         return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
+				 tem);
+       }
+     /* Transform (A AND-IF B) into (A AND B), or (A OR-IF B)
+        into (A OR B).
+        For sequence point consistancy, we need to check for trapping, and
+        side-effects.  */
+     else if (simple_operand_p_2 (arg0))
+       return fold_build2_loc (loc, ncode, type, arg0, arg1);
+    }
+
   return NULL_TREE;
 }
Richard Guenther - Oct. 17, 2011, 10:38 a.m.
On Fri, Oct 14, 2011 at 9:43 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Hello,
>
> So I committed the gimplify patch separate.  And here is the remaining
> fold-const patch.
> The important tests here are in gcc.dg/tree-ssa/builtin-expect[1-4].c, which
> cover the one special-case for branching. Also tree-ssa/20040204-1.c covers
> tests for branching code (on targets having high-engough BRANCH_COST and no
> special-casing - like MIPS, S/390, and AVR.
>
> ChangeLog
>
> 2011-10-14  Kai Tietz  <ktietz@redhat.com>
>
>        * fold-const.c (simple_operand_p_2): New function.
>        (fold_truthop): Rename to
>        (fold_truth_andor_1): function name.
>        Additionally remove branching creation for logical and/or.
>        (fold_truth_andor): Handle branching creation for logical and/or here.
>
> Bootstrapped and regression-tested for all languages plus Ada and
> Obj-C++ on x86_64-pc-linux-gnu.
> Ok for apply?

Ok with ...

> Regards,
> Kai
>
> Index: gcc/gcc/fold-const.c
> ===================================================================
> --- gcc.orig/gcc/fold-const.c
> +++ gcc/gcc/fold-const.c
> @@ -112,13 +112,13 @@ static tree decode_field_reference (loca
>  static int all_ones_mask_p (const_tree, int);
>  static tree sign_bit_p (tree, const_tree);
>  static int simple_operand_p (const_tree);
> +static bool simple_operand_p_2 (tree);
>  static tree range_binop (enum tree_code, tree, tree, int, tree, int);
>  static tree range_predecessor (tree);
>  static tree range_successor (tree);
>  static tree fold_range_test (location_t, enum tree_code, tree, tree, tree);
>  static tree fold_cond_expr_with_comparison (location_t, tree, tree,
> tree, tree);
>  static tree unextend (tree, int, int, tree);
> -static tree fold_truthop (location_t, enum tree_code, tree, tree, tree);
>  static tree optimize_minmax_comparison (location_t, enum tree_code,
>                                        tree, tree, tree);
>  static tree extract_muldiv (tree, tree, enum tree_code, tree, bool *);
> @@ -3500,7 +3500,7 @@ optimize_bit_field_compare (location_t l
>   return lhs;
>  }
>
> -/* Subroutine for fold_truthop: decode a field reference.
> +/* Subroutine for fold_truth_andor_1: decode a field reference.
>
>    If EXP is a comparison reference, we return the innermost reference.
>
> @@ -3668,7 +3668,7 @@ sign_bit_p (tree exp, const_tree val)
>   return NULL_TREE;
>  }
>
> -/* Subroutine for fold_truthop: determine if an operand is simple enough
> +/* Subroutine for fold_truth_andor_1: determine if an operand is simple enough
>    to be evaluated unconditionally.  */
>
>  static int
> @@ -3678,7 +3678,7 @@ simple_operand_p (const_tree exp)
>   STRIP_NOPS (exp);
>
>   return (CONSTANT_CLASS_P (exp)
> -         || TREE_CODE (exp) == SSA_NAME
> +         || TREE_CODE (exp) == SSA_NAME
>          || (DECL_P (exp)
>              && ! TREE_ADDRESSABLE (exp)
>              && ! TREE_THIS_VOLATILE (exp)
> @@ -3692,6 +3692,46 @@ simple_operand_p (const_tree exp)
>                 registers aren't expensive.  */
>              && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
>  }
> +
> +/* Subroutine for fold_truth_andor: determine if an operand is simple enough
> +   to be evaluated unconditionally.
> +   I addition to simple_operand_p, we assume that comparisons and logic-not
> +   operations are simple, if their operands are simple, too.  */
> +
> +static bool
> +simple_operand_p_2 (tree exp)
> +{
> +  enum tree_code code;
> +
> +  /* Strip any conversions that don't change the machine mode.  */
> +  STRIP_NOPS (exp);
> +
> +  code = TREE_CODE (exp);
> +
> +  if (TREE_CODE_CLASS (code) == tcc_comparison)
> +    return (!tree_could_trap_p (exp)
> +           && simple_operand_p_2 (TREE_OPERAND (exp, 0))
> +           && simple_operand_p_2 (TREE_OPERAND (exp, 1)));

recurse with simple_operand_p.

> +
> +  if (TREE_SIDE_EFFECTS (exp)
> +      || tree_could_trap_p (exp))

Move this check before the tcc_comparison check and remove the
then redundant tree_could_trap_p check there.

> +    return false;
> +
> +  switch (code)
> +    {
> +    case SSA_NAME:
> +      return true;

Do not handle here, it's handled in simple_operand_p.

> +    case TRUTH_NOT_EXPR:
> +      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
> +    case BIT_NOT_EXPR:
> +      if (TREE_CODE (TREE_TYPE (exp)) != BOOLEAN_TYPE)
> +       return false;

Remove the BIT_NOT_EXPR handling.  Thus, simply change this switch
to

if (code == TRUTH_NOT_EXPR)
  return simple_operand_p_2 (TREE_OPERAND (exp, 0));

return simple_operand_p (exp);

> +      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
> +    default:
> +      return simple_operand_p (exp);
> +    }
> +}
> +
>
>  /* The following functions are subroutines to fold_range_test and allow it to
>    try to change a logical combination of comparisons into a range test.
> @@ -4888,7 +4928,7 @@ fold_range_test (location_t loc, enum tr
>   return 0;
>  }
>
> -/* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
> +/* Subroutine for fold_truth_andor_1: C is an INTEGER_CST interpreted as a P
>    bit value.  Arrange things so the extra bits will be set to zero if and
>    only if C is signed-extended to its full width.  If MASK is nonzero,
>    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
> @@ -5025,8 +5065,8 @@ merge_truthop_with_opposite_arm (locatio
>    We return the simplified tree or 0 if no optimization is possible.  */
>
>  static tree
> -fold_truthop (location_t loc, enum tree_code code, tree truth_type,
> -             tree lhs, tree rhs)
> +fold_truth_andor_1 (location_t loc, enum tree_code code, tree truth_type,
> +                   tree lhs, tree rhs)
>  {
>   /* If this is the "or" of two comparisons, we can do something if
>      the comparisons are NE_EXPR.  If this is the "and", we can do something
> @@ -5054,8 +5094,6 @@ fold_truthop (location_t loc, enum tree_
>   tree lntype, rntype, result;
>   HOST_WIDE_INT first_bit, end_bit;
>   int volatilep;
> -  tree orig_lhs = lhs, orig_rhs = rhs;
> -  enum tree_code orig_code = code;
>
>   /* Start by getting the comparison codes.  Fail if anything is volatile.
>      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
> @@ -5119,8 +5157,7 @@ fold_truthop (location_t loc, enum tree_
>   /* If the RHS can be evaluated unconditionally and its operands are
>      simple, it wins to evaluate the RHS unconditionally on machines
>      with expensive branches.  In this case, this isn't a comparison
> -     that can be merged.  Avoid doing this if the RHS is a floating-point
> -     comparison since those can trap.  */
> +     that can be merged.  */
>
>   if (BRANCH_COST (optimize_function_for_speed_p (cfun),
>                   false) >= 2
> @@ -5149,13 +5186,6 @@ fold_truthop (location_t loc, enum tree_
>                           build2 (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
>                                   ll_arg, rl_arg),
>                           build_int_cst (TREE_TYPE (ll_arg), 0));
> -
> -      if (LOGICAL_OP_NON_SHORT_CIRCUIT)
> -       {
> -         if (code != orig_code || lhs != orig_lhs || rhs != orig_rhs)
> -           return build2_loc (loc, code, truth_type, lhs, rhs);
> -         return NULL_TREE;
> -       }
>     }
>
>   /* See if the comparisons can be merged.  Then get all the parameters for
> @@ -8380,13 +8410,49 @@ fold_truth_andor (location_t loc, enum t
>      lhs is another similar operation, try to merge its rhs with our
>      rhs.  Then try to merge our lhs and rhs.  */
>   if (TREE_CODE (arg0) == code
> -      && 0 != (tem = fold_truthop (loc, code, type,
> -                                  TREE_OPERAND (arg0, 1), arg1)))
> +      && 0 != (tem = fold_truth_andor_1 (loc, code, type,
> +                                        TREE_OPERAND (arg0, 1), arg1)))
>     return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem);
>
> -  if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
> +  if ((tem = fold_truth_andor_1 (loc, code, type, arg0, arg1)) != 0)
>     return tem;
>
> +  if ((code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR)
> +      && (BRANCH_COST (optimize_function_for_speed_p (cfun),
> +                      false) >= 2)
> +      && LOGICAL_OP_NON_SHORT_CIRCUIT
> +      && simple_operand_p_2 (arg1))
> +    {
> +      enum tree_code ncode = (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR
> +                                                      : TRUTH_OR_EXPR);
> +
> +      /* Transform ((A AND-IF B) AND-IF C) into (A AND-IF (B AND C)),
> +         or ((A OR-IF B) OR-IF C) into (A OR-IF (B OR C))
> +         We don't want to pack more than two leafs to a non-IF AND/OR
> +         expression.
> +         If tree-code of left-hand operand isn't an AND/OR-IF code and not
> +         equal to CODE, then we don't want to add right-hand operand.
> +         If the inner right-hand side of left-hand operand has side-effects,
> +         or isn't simple, then we can't add to it, as otherwise we might
> +         destroy if-sequence.  */
> +      if (TREE_CODE (arg0) == code
> +         /* Needed for sequence points to handle trappings, and
> +            side-effects.  */
> +         && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
> +       {
> +         tem = fold_build2_loc (loc, ncode, type, TREE_OPERAND (arg0, 1),
> +                               arg1);
> +         return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
> +                                tem);
> +       }

I see you insist on this change.  Let me explain again.  You do this
for ((A AND-IF B) AND-IF C) but you don't do this for
((A AND-IF B) AND C).  Why?  That is what doesn't make sense ot me.
Thus omit this hunk.

Ok with the above changes.

Thanks,
Richard.

> +     /* Transform (A AND-IF B) into (A AND B), or (A OR-IF B)
> +        into (A OR B).
> +        For sequence point consistancy, we need to check for trapping, and
> +        side-effects.  */
> +     else if (simple_operand_p_2 (arg0))
> +       return fold_build2_loc (loc, ncode, type, arg0, arg1);
> +    }
> +
>   return NULL_TREE;
>  }
>
Kai Tietz - Oct. 17, 2011, 10:59 a.m.
2011/10/17 Richard Guenther <richard.guenther@gmail.com>:
> On Fri, Oct 14, 2011 at 9:43 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> Hello,
>>
>> So I committed the gimplify patch separate.  And here is the remaining
>> fold-const patch.
>> The important tests here are in gcc.dg/tree-ssa/builtin-expect[1-4].c, which
>> cover the one special-case for branching. Also tree-ssa/20040204-1.c covers
>> tests for branching code (on targets having high-engough BRANCH_COST and no
>> special-casing - like MIPS, S/390, and AVR.
>>
>> ChangeLog
>>
>> 2011-10-14  Kai Tietz  <ktietz@redhat.com>
>>
>>        * fold-const.c (simple_operand_p_2): New function.
>>        (fold_truthop): Rename to
>>        (fold_truth_andor_1): function name.
>>        Additionally remove branching creation for logical and/or.
>>        (fold_truth_andor): Handle branching creation for logical and/or here.
>>
>> Bootstrapped and regression-tested for all languages plus Ada and
>> Obj-C++ on x86_64-pc-linux-gnu.
>> Ok for apply?
>
> Ok with ...
>
>> Regards,
>> Kai
>>
>> Index: gcc/gcc/fold-const.c
>> ===================================================================
>> --- gcc.orig/gcc/fold-const.c
>> +++ gcc/gcc/fold-const.c
>> @@ -112,13 +112,13 @@ static tree decode_field_reference (loca
>>  static int all_ones_mask_p (const_tree, int);
>>  static tree sign_bit_p (tree, const_tree);
>>  static int simple_operand_p (const_tree);
>> +static bool simple_operand_p_2 (tree);
>>  static tree range_binop (enum tree_code, tree, tree, int, tree, int);
>>  static tree range_predecessor (tree);
>>  static tree range_successor (tree);
>>  static tree fold_range_test (location_t, enum tree_code, tree, tree, tree);
>>  static tree fold_cond_expr_with_comparison (location_t, tree, tree,
>> tree, tree);
>>  static tree unextend (tree, int, int, tree);
>> -static tree fold_truthop (location_t, enum tree_code, tree, tree, tree);
>>  static tree optimize_minmax_comparison (location_t, enum tree_code,
>>                                        tree, tree, tree);
>>  static tree extract_muldiv (tree, tree, enum tree_code, tree, bool *);
>> @@ -3500,7 +3500,7 @@ optimize_bit_field_compare (location_t l
>>   return lhs;
>>  }
>>
>> -/* Subroutine for fold_truthop: decode a field reference.
>> +/* Subroutine for fold_truth_andor_1: decode a field reference.
>>
>>    If EXP is a comparison reference, we return the innermost reference.
>>
>> @@ -3668,7 +3668,7 @@ sign_bit_p (tree exp, const_tree val)
>>   return NULL_TREE;
>>  }
>>
>> -/* Subroutine for fold_truthop: determine if an operand is simple enough
>> +/* Subroutine for fold_truth_andor_1: determine if an operand is simple enough
>>    to be evaluated unconditionally.  */
>>
>>  static int
>> @@ -3678,7 +3678,7 @@ simple_operand_p (const_tree exp)
>>   STRIP_NOPS (exp);
>>
>>   return (CONSTANT_CLASS_P (exp)
>> -         || TREE_CODE (exp) == SSA_NAME
>> +         || TREE_CODE (exp) == SSA_NAME
>>          || (DECL_P (exp)
>>              && ! TREE_ADDRESSABLE (exp)
>>              && ! TREE_THIS_VOLATILE (exp)
>> @@ -3692,6 +3692,46 @@ simple_operand_p (const_tree exp)
>>                 registers aren't expensive.  */
>>              && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
>>  }
>> +
>> +/* Subroutine for fold_truth_andor: determine if an operand is simple enough
>> +   to be evaluated unconditionally.
>> +   I addition to simple_operand_p, we assume that comparisons and logic-not
>> +   operations are simple, if their operands are simple, too.  */
>> +
>> +static bool
>> +simple_operand_p_2 (tree exp)
>> +{
>> +  enum tree_code code;
>> +
>> +  /* Strip any conversions that don't change the machine mode.  */
>> +  STRIP_NOPS (exp);
>> +
>> +  code = TREE_CODE (exp);
>> +
>> +  if (TREE_CODE_CLASS (code) == tcc_comparison)
>> +    return (!tree_could_trap_p (exp)
>> +           && simple_operand_p_2 (TREE_OPERAND (exp, 0))
>> +           && simple_operand_p_2 (TREE_OPERAND (exp, 1)));
>
> recurse with simple_operand_p.

No, as this again would reject simple operations and additionally
wouldn't check for trapping.

>> +
>> +  if (TREE_SIDE_EFFECTS (exp)
>> +      || tree_could_trap_p (exp))
>
> Move this check before the tcc_comparison check and remove the
> then redundant tree_could_trap_p check there.

Ok

>> +    return false;
>> +
>> +  switch (code)
>> +    {
>> +    case SSA_NAME:
>> +      return true;
>
> Do not handle here, it's handled in simple_operand_p.

Well, was more a short-cut here.

>> +    case TRUTH_NOT_EXPR:
>> +      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>> +    case BIT_NOT_EXPR:
>> +      if (TREE_CODE (TREE_TYPE (exp)) != BOOLEAN_TYPE)
>> +       return false;
>
> Remove the BIT_NOT_EXPR handling.  Thus, simply change this switch
> to

Why should we reject simple ~X operations from gimplified code here?
I admit that from FE-code we won't see that, as always an integer-cast
is done for foo (_Bool x) { ... if (~x) ... }, but from
gimplified-code this is the general description of an boolean-typed !=
0?

> if (code == TRUTH_NOT_EXPR)
>  return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>
> return simple_operand_p (exp);
>
>> +      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>> +    default:
>> +      return simple_operand_p (exp);
>> +    }
>> +}
>> +
>>
>>  /* The following functions are subroutines to fold_range_test and allow it to
>>    try to change a logical combination of comparisons into a range test.
>> @@ -4888,7 +4928,7 @@ fold_range_test (location_t loc, enum tr
>>   return 0;
>>  }
>>
>> -/* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
>> +/* Subroutine for fold_truth_andor_1: C is an INTEGER_CST interpreted as a P
>>    bit value.  Arrange things so the extra bits will be set to zero if and
>>    only if C is signed-extended to its full width.  If MASK is nonzero,
>>    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
>> @@ -5025,8 +5065,8 @@ merge_truthop_with_opposite_arm (locatio
>>    We return the simplified tree or 0 if no optimization is possible.  */
>>
>>  static tree
>> -fold_truthop (location_t loc, enum tree_code code, tree truth_type,
>> -             tree lhs, tree rhs)
>> +fold_truth_andor_1 (location_t loc, enum tree_code code, tree truth_type,
>> +                   tree lhs, tree rhs)
>>  {
>>   /* If this is the "or" of two comparisons, we can do something if
>>      the comparisons are NE_EXPR.  If this is the "and", we can do something
>> @@ -5054,8 +5094,6 @@ fold_truthop (location_t loc, enum tree_
>>   tree lntype, rntype, result;
>>   HOST_WIDE_INT first_bit, end_bit;
>>   int volatilep;
>> -  tree orig_lhs = lhs, orig_rhs = rhs;
>> -  enum tree_code orig_code = code;
>>
>>   /* Start by getting the comparison codes.  Fail if anything is volatile.
>>      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
>> @@ -5119,8 +5157,7 @@ fold_truthop (location_t loc, enum tree_
>>   /* If the RHS can be evaluated unconditionally and its operands are
>>      simple, it wins to evaluate the RHS unconditionally on machines
>>      with expensive branches.  In this case, this isn't a comparison
>> -     that can be merged.  Avoid doing this if the RHS is a floating-point
>> -     comparison since those can trap.  */
>> +     that can be merged.  */
>>
>>   if (BRANCH_COST (optimize_function_for_speed_p (cfun),
>>                   false) >= 2
>> @@ -5149,13 +5186,6 @@ fold_truthop (location_t loc, enum tree_
>>                           build2 (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
>>                                   ll_arg, rl_arg),
>>                           build_int_cst (TREE_TYPE (ll_arg), 0));
>> -
>> -      if (LOGICAL_OP_NON_SHORT_CIRCUIT)
>> -       {
>> -         if (code != orig_code || lhs != orig_lhs || rhs != orig_rhs)
>> -           return build2_loc (loc, code, truth_type, lhs, rhs);
>> -         return NULL_TREE;
>> -       }
>>     }
>>
>>   /* See if the comparisons can be merged.  Then get all the parameters for
>> @@ -8380,13 +8410,49 @@ fold_truth_andor (location_t loc, enum t
>>      lhs is another similar operation, try to merge its rhs with our
>>      rhs.  Then try to merge our lhs and rhs.  */
>>   if (TREE_CODE (arg0) == code
>> -      && 0 != (tem = fold_truthop (loc, code, type,
>> -                                  TREE_OPERAND (arg0, 1), arg1)))
>> +      && 0 != (tem = fold_truth_andor_1 (loc, code, type,
>> +                                        TREE_OPERAND (arg0, 1), arg1)))
>>     return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem);
>>
>> -  if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
>> +  if ((tem = fold_truth_andor_1 (loc, code, type, arg0, arg1)) != 0)
>>     return tem;
>>
>> +  if ((code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR)
>> +      && (BRANCH_COST (optimize_function_for_speed_p (cfun),
>> +                      false) >= 2)
>> +      && LOGICAL_OP_NON_SHORT_CIRCUIT
>> +      && simple_operand_p_2 (arg1))
>> +    {
>> +      enum tree_code ncode = (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR
>> +                                                      : TRUTH_OR_EXPR);
>> +
>> +      /* Transform ((A AND-IF B) AND-IF C) into (A AND-IF (B AND C)),
>> +         or ((A OR-IF B) OR-IF C) into (A OR-IF (B OR C))
>> +         We don't want to pack more than two leafs to a non-IF AND/OR
>> +         expression.
>> +         If tree-code of left-hand operand isn't an AND/OR-IF code and not
>> +         equal to CODE, then we don't want to add right-hand operand.
>> +         If the inner right-hand side of left-hand operand has side-effects,
>> +         or isn't simple, then we can't add to it, as otherwise we might
>> +         destroy if-sequence.  */
>> +      if (TREE_CODE (arg0) == code
>> +         /* Needed for sequence points to handle trappings, and
>> +            side-effects.  */
>> +         && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
>> +       {
>> +         tem = fold_build2_loc (loc, ncode, type, TREE_OPERAND (arg0, 1),
>> +                               arg1);
>> +         return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
>> +                                tem);
>> +       }
>
> I see you insist on this change.  Let me explain again.  You do this
> for ((A AND-IF B) AND-IF C) but you don't do this for
> ((A AND-IF B) AND C).  Why?  That is what doesn't make sense ot me.
> Thus omit this hunk.

Well, first ((A AND-IF B) AND C) would be an ill sequence,  as AND is
associative. So we would simply break sequence points for && and ||.
If left-hand operand is an AND/OR-IF then outer operand has to always
an ?-IF operation, too.  Only case we can associate to is for (A
AND-IF B) AND-IF C to ((A AND-IF (B AND C), if B and C have no
side-effects.

> Ok with the above changes.
>
> Thanks,
> Richard.

Regards,
Kai
Richard Guenther - Oct. 17, 2011, 11:18 a.m.
On Mon, Oct 17, 2011 at 12:59 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2011/10/17 Richard Guenther <richard.guenther@gmail.com>:
>> On Fri, Oct 14, 2011 at 9:43 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>> Hello,
>>>
>>> So I committed the gimplify patch separate.  And here is the remaining
>>> fold-const patch.
>>> The important tests here are in gcc.dg/tree-ssa/builtin-expect[1-4].c, which
>>> cover the one special-case for branching. Also tree-ssa/20040204-1.c covers
>>> tests for branching code (on targets having high-engough BRANCH_COST and no
>>> special-casing - like MIPS, S/390, and AVR.
>>>
>>> ChangeLog
>>>
>>> 2011-10-14  Kai Tietz  <ktietz@redhat.com>
>>>
>>>        * fold-const.c (simple_operand_p_2): New function.
>>>        (fold_truthop): Rename to
>>>        (fold_truth_andor_1): function name.
>>>        Additionally remove branching creation for logical and/or.
>>>        (fold_truth_andor): Handle branching creation for logical and/or here.
>>>
>>> Bootstrapped and regression-tested for all languages plus Ada and
>>> Obj-C++ on x86_64-pc-linux-gnu.
>>> Ok for apply?
>>
>> Ok with ...
>>
>>> Regards,
>>> Kai
>>>
>>> Index: gcc/gcc/fold-const.c
>>> ===================================================================
>>> --- gcc.orig/gcc/fold-const.c
>>> +++ gcc/gcc/fold-const.c
>>> @@ -112,13 +112,13 @@ static tree decode_field_reference (loca
>>>  static int all_ones_mask_p (const_tree, int);
>>>  static tree sign_bit_p (tree, const_tree);
>>>  static int simple_operand_p (const_tree);
>>> +static bool simple_operand_p_2 (tree);
>>>  static tree range_binop (enum tree_code, tree, tree, int, tree, int);
>>>  static tree range_predecessor (tree);
>>>  static tree range_successor (tree);
>>>  static tree fold_range_test (location_t, enum tree_code, tree, tree, tree);
>>>  static tree fold_cond_expr_with_comparison (location_t, tree, tree,
>>> tree, tree);
>>>  static tree unextend (tree, int, int, tree);
>>> -static tree fold_truthop (location_t, enum tree_code, tree, tree, tree);
>>>  static tree optimize_minmax_comparison (location_t, enum tree_code,
>>>                                        tree, tree, tree);
>>>  static tree extract_muldiv (tree, tree, enum tree_code, tree, bool *);
>>> @@ -3500,7 +3500,7 @@ optimize_bit_field_compare (location_t l
>>>   return lhs;
>>>  }
>>>
>>> -/* Subroutine for fold_truthop: decode a field reference.
>>> +/* Subroutine for fold_truth_andor_1: decode a field reference.
>>>
>>>    If EXP is a comparison reference, we return the innermost reference.
>>>
>>> @@ -3668,7 +3668,7 @@ sign_bit_p (tree exp, const_tree val)
>>>   return NULL_TREE;
>>>  }
>>>
>>> -/* Subroutine for fold_truthop: determine if an operand is simple enough
>>> +/* Subroutine for fold_truth_andor_1: determine if an operand is simple enough
>>>    to be evaluated unconditionally.  */
>>>
>>>  static int
>>> @@ -3678,7 +3678,7 @@ simple_operand_p (const_tree exp)
>>>   STRIP_NOPS (exp);
>>>
>>>   return (CONSTANT_CLASS_P (exp)
>>> -         || TREE_CODE (exp) == SSA_NAME
>>> +         || TREE_CODE (exp) == SSA_NAME
>>>          || (DECL_P (exp)
>>>              && ! TREE_ADDRESSABLE (exp)
>>>              && ! TREE_THIS_VOLATILE (exp)
>>> @@ -3692,6 +3692,46 @@ simple_operand_p (const_tree exp)
>>>                 registers aren't expensive.  */
>>>              && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
>>>  }
>>> +
>>> +/* Subroutine for fold_truth_andor: determine if an operand is simple enough
>>> +   to be evaluated unconditionally.
>>> +   I addition to simple_operand_p, we assume that comparisons and logic-not
>>> +   operations are simple, if their operands are simple, too.  */
>>> +
>>> +static bool
>>> +simple_operand_p_2 (tree exp)
>>> +{
>>> +  enum tree_code code;
>>> +
>>> +  /* Strip any conversions that don't change the machine mode.  */
>>> +  STRIP_NOPS (exp);
>>> +
>>> +  code = TREE_CODE (exp);
>>> +
>>> +  if (TREE_CODE_CLASS (code) == tcc_comparison)
>>> +    return (!tree_could_trap_p (exp)
>>> +           && simple_operand_p_2 (TREE_OPERAND (exp, 0))
>>> +           && simple_operand_p_2 (TREE_OPERAND (exp, 1)));
>>
>> recurse with simple_operand_p.
>
> No, as this again would reject simple operations and additionally
> wouldn't check for trapping.

?  Your code allows arbitrarily complex expressions.  Also
tree_could_trap_p obviously extents to operands.

>
>>> +
>>> +  if (TREE_SIDE_EFFECTS (exp)
>>> +      || tree_could_trap_p (exp))
>>
>> Move this check before the tcc_comparison check and remove the
>> then redundant tree_could_trap_p check there.
>
> Ok
>
>>> +    return false;
>>> +
>>> +  switch (code)
>>> +    {
>>> +    case SSA_NAME:
>>> +      return true;
>>
>> Do not handle here, it's handled in simple_operand_p.
>
> Well, was more a short-cut here.
>
>>> +    case TRUTH_NOT_EXPR:
>>> +      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>>> +    case BIT_NOT_EXPR:
>>> +      if (TREE_CODE (TREE_TYPE (exp)) != BOOLEAN_TYPE)
>>> +       return false;
>>
>> Remove the BIT_NOT_EXPR handling.  Thus, simply change this switch
>> to
>
> Why should we reject simple ~X operations from gimplified code here?

Because this is FE triggered code.  From gimple you won't ever see
such complex expressions (never even the TRUTH_AND*_EXPR variants).

> I admit that from FE-code we won't see that, as always an integer-cast
> is done for foo (_Bool x) { ... if (~x) ... }, but from
> gimplified-code this is the general description of an boolean-typed !=
> 0?
>
>> if (code == TRUTH_NOT_EXPR)
>>  return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>>
>> return simple_operand_p (exp);
>>
>>> +      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>>> +    default:
>>> +      return simple_operand_p (exp);
>>> +    }
>>> +}
>>> +
>>>
>>>  /* The following functions are subroutines to fold_range_test and allow it to
>>>    try to change a logical combination of comparisons into a range test.
>>> @@ -4888,7 +4928,7 @@ fold_range_test (location_t loc, enum tr
>>>   return 0;
>>>  }
>>>
>>> -/* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
>>> +/* Subroutine for fold_truth_andor_1: C is an INTEGER_CST interpreted as a P
>>>    bit value.  Arrange things so the extra bits will be set to zero if and
>>>    only if C is signed-extended to its full width.  If MASK is nonzero,
>>>    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
>>> @@ -5025,8 +5065,8 @@ merge_truthop_with_opposite_arm (locatio
>>>    We return the simplified tree or 0 if no optimization is possible.  */
>>>
>>>  static tree
>>> -fold_truthop (location_t loc, enum tree_code code, tree truth_type,
>>> -             tree lhs, tree rhs)
>>> +fold_truth_andor_1 (location_t loc, enum tree_code code, tree truth_type,
>>> +                   tree lhs, tree rhs)
>>>  {
>>>   /* If this is the "or" of two comparisons, we can do something if
>>>      the comparisons are NE_EXPR.  If this is the "and", we can do something
>>> @@ -5054,8 +5094,6 @@ fold_truthop (location_t loc, enum tree_
>>>   tree lntype, rntype, result;
>>>   HOST_WIDE_INT first_bit, end_bit;
>>>   int volatilep;
>>> -  tree orig_lhs = lhs, orig_rhs = rhs;
>>> -  enum tree_code orig_code = code;
>>>
>>>   /* Start by getting the comparison codes.  Fail if anything is volatile.
>>>      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
>>> @@ -5119,8 +5157,7 @@ fold_truthop (location_t loc, enum tree_
>>>   /* If the RHS can be evaluated unconditionally and its operands are
>>>      simple, it wins to evaluate the RHS unconditionally on machines
>>>      with expensive branches.  In this case, this isn't a comparison
>>> -     that can be merged.  Avoid doing this if the RHS is a floating-point
>>> -     comparison since those can trap.  */
>>> +     that can be merged.  */
>>>
>>>   if (BRANCH_COST (optimize_function_for_speed_p (cfun),
>>>                   false) >= 2
>>> @@ -5149,13 +5186,6 @@ fold_truthop (location_t loc, enum tree_
>>>                           build2 (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
>>>                                   ll_arg, rl_arg),
>>>                           build_int_cst (TREE_TYPE (ll_arg), 0));
>>> -
>>> -      if (LOGICAL_OP_NON_SHORT_CIRCUIT)
>>> -       {
>>> -         if (code != orig_code || lhs != orig_lhs || rhs != orig_rhs)
>>> -           return build2_loc (loc, code, truth_type, lhs, rhs);
>>> -         return NULL_TREE;
>>> -       }
>>>     }
>>>
>>>   /* See if the comparisons can be merged.  Then get all the parameters for
>>> @@ -8380,13 +8410,49 @@ fold_truth_andor (location_t loc, enum t
>>>      lhs is another similar operation, try to merge its rhs with our
>>>      rhs.  Then try to merge our lhs and rhs.  */
>>>   if (TREE_CODE (arg0) == code
>>> -      && 0 != (tem = fold_truthop (loc, code, type,
>>> -                                  TREE_OPERAND (arg0, 1), arg1)))
>>> +      && 0 != (tem = fold_truth_andor_1 (loc, code, type,
>>> +                                        TREE_OPERAND (arg0, 1), arg1)))
>>>     return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem);
>>>
>>> -  if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
>>> +  if ((tem = fold_truth_andor_1 (loc, code, type, arg0, arg1)) != 0)
>>>     return tem;
>>>
>>> +  if ((code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR)
>>> +      && (BRANCH_COST (optimize_function_for_speed_p (cfun),
>>> +                      false) >= 2)
>>> +      && LOGICAL_OP_NON_SHORT_CIRCUIT
>>> +      && simple_operand_p_2 (arg1))
>>> +    {
>>> +      enum tree_code ncode = (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR
>>> +                                                      : TRUTH_OR_EXPR);
>>> +
>>> +      /* Transform ((A AND-IF B) AND-IF C) into (A AND-IF (B AND C)),
>>> +         or ((A OR-IF B) OR-IF C) into (A OR-IF (B OR C))
>>> +         We don't want to pack more than two leafs to a non-IF AND/OR
>>> +         expression.
>>> +         If tree-code of left-hand operand isn't an AND/OR-IF code and not
>>> +         equal to CODE, then we don't want to add right-hand operand.
>>> +         If the inner right-hand side of left-hand operand has side-effects,
>>> +         or isn't simple, then we can't add to it, as otherwise we might
>>> +         destroy if-sequence.  */
>>> +      if (TREE_CODE (arg0) == code
>>> +         /* Needed for sequence points to handle trappings, and
>>> +            side-effects.  */
>>> +         && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
>>> +       {
>>> +         tem = fold_build2_loc (loc, ncode, type, TREE_OPERAND (arg0, 1),
>>> +                               arg1);
>>> +         return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
>>> +                                tem);
>>> +       }
>>
>> I see you insist on this change.  Let me explain again.  You do this
>> for ((A AND-IF B) AND-IF C) but you don't do this for
>> ((A AND-IF B) AND C).  Why?  That is what doesn't make sense ot me.
>> Thus omit this hunk.
>
> Well, first ((A AND-IF B) AND C) would be an ill sequence,  as AND is
> associative. So we would simply break sequence points for && and ||.
> If left-hand operand is an AND/OR-IF then outer operand has to always
> an ?-IF operation, too.

Why?  It's something like (ptr && *ptr) & x.  Whether you evaluate
x or (ptr && *ptr) first does not matter.  But you have to check
whether ptr is non-null before dereferencing it.  So it's clearly not
ill-formed.  You may argue the transform is pointless and we should
associate the & instead.  Do you?

  Only case we can associate to is for (A
> AND-IF B) AND-IF C to ((A AND-IF (B AND C), if B and C have no
> side-effects.
>
>> Ok with the above changes.
>>
>> Thanks,
>> Richard.
>
> Regards,
> Kai
>
Kai Tietz - Oct. 17, 2011, 11:31 a.m.
2011/10/17 Richard Guenther <richard.guenther@gmail.com>:
> On Mon, Oct 17, 2011 at 12:59 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> 2011/10/17 Richard Guenther <richard.guenther@gmail.com>:
>>> On Fri, Oct 14, 2011 at 9:43 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>> Hello,
>>>>
>>>> So I committed the gimplify patch separate.  And here is the remaining
>>>> fold-const patch.
>>>> The important tests here are in gcc.dg/tree-ssa/builtin-expect[1-4].c, which
>>>> cover the one special-case for branching. Also tree-ssa/20040204-1.c covers
>>>> tests for branching code (on targets having high-engough BRANCH_COST and no
>>>> special-casing - like MIPS, S/390, and AVR.
>>>>
>>>> ChangeLog
>>>>
>>>> 2011-10-14  Kai Tietz  <ktietz@redhat.com>
>>>>
>>>>        * fold-const.c (simple_operand_p_2): New function.
>>>>        (fold_truthop): Rename to
>>>>        (fold_truth_andor_1): function name.
>>>>        Additionally remove branching creation for logical and/or.
>>>>        (fold_truth_andor): Handle branching creation for logical and/or here.
>>>>
>>>> Bootstrapped and regression-tested for all languages plus Ada and
>>>> Obj-C++ on x86_64-pc-linux-gnu.
>>>> Ok for apply?
>>>
>>> Ok with ...
>>>
>>>> Regards,
>>>> Kai
>>>>
>>>> Index: gcc/gcc/fold-const.c
>>>> ===================================================================
>>>> --- gcc.orig/gcc/fold-const.c
>>>> +++ gcc/gcc/fold-const.c
>>>> @@ -112,13 +112,13 @@ static tree decode_field_reference (loca
>>>>  static int all_ones_mask_p (const_tree, int);
>>>>  static tree sign_bit_p (tree, const_tree);
>>>>  static int simple_operand_p (const_tree);
>>>> +static bool simple_operand_p_2 (tree);
>>>>  static tree range_binop (enum tree_code, tree, tree, int, tree, int);
>>>>  static tree range_predecessor (tree);
>>>>  static tree range_successor (tree);
>>>>  static tree fold_range_test (location_t, enum tree_code, tree, tree, tree);
>>>>  static tree fold_cond_expr_with_comparison (location_t, tree, tree,
>>>> tree, tree);
>>>>  static tree unextend (tree, int, int, tree);
>>>> -static tree fold_truthop (location_t, enum tree_code, tree, tree, tree);
>>>>  static tree optimize_minmax_comparison (location_t, enum tree_code,
>>>>                                        tree, tree, tree);
>>>>  static tree extract_muldiv (tree, tree, enum tree_code, tree, bool *);
>>>> @@ -3500,7 +3500,7 @@ optimize_bit_field_compare (location_t l
>>>>   return lhs;
>>>>  }
>>>>
>>>> -/* Subroutine for fold_truthop: decode a field reference.
>>>> +/* Subroutine for fold_truth_andor_1: decode a field reference.
>>>>
>>>>    If EXP is a comparison reference, we return the innermost reference.
>>>>
>>>> @@ -3668,7 +3668,7 @@ sign_bit_p (tree exp, const_tree val)
>>>>   return NULL_TREE;
>>>>  }
>>>>
>>>> -/* Subroutine for fold_truthop: determine if an operand is simple enough
>>>> +/* Subroutine for fold_truth_andor_1: determine if an operand is simple enough
>>>>    to be evaluated unconditionally.  */
>>>>
>>>>  static int
>>>> @@ -3678,7 +3678,7 @@ simple_operand_p (const_tree exp)
>>>>   STRIP_NOPS (exp);
>>>>
>>>>   return (CONSTANT_CLASS_P (exp)
>>>> -         || TREE_CODE (exp) == SSA_NAME
>>>> +         || TREE_CODE (exp) == SSA_NAME
>>>>          || (DECL_P (exp)
>>>>              && ! TREE_ADDRESSABLE (exp)
>>>>              && ! TREE_THIS_VOLATILE (exp)
>>>> @@ -3692,6 +3692,46 @@ simple_operand_p (const_tree exp)
>>>>                 registers aren't expensive.  */
>>>>              && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
>>>>  }
>>>> +
>>>> +/* Subroutine for fold_truth_andor: determine if an operand is simple enough
>>>> +   to be evaluated unconditionally.
>>>> +   I addition to simple_operand_p, we assume that comparisons and logic-not
>>>> +   operations are simple, if their operands are simple, too.  */
>>>> +
>>>> +static bool
>>>> +simple_operand_p_2 (tree exp)
>>>> +{
>>>> +  enum tree_code code;
>>>> +
>>>> +  /* Strip any conversions that don't change the machine mode.  */
>>>> +  STRIP_NOPS (exp);
>>>> +
>>>> +  code = TREE_CODE (exp);
>>>> +
>>>> +  if (TREE_CODE_CLASS (code) == tcc_comparison)
>>>> +    return (!tree_could_trap_p (exp)
>>>> +           && simple_operand_p_2 (TREE_OPERAND (exp, 0))
>>>> +           && simple_operand_p_2 (TREE_OPERAND (exp, 1)));
>>>
>>> recurse with simple_operand_p.
>>
>> No, as this again would reject simple operations and additionally
>> wouldn't check for trapping.
>
> ?  Your code allows arbitrarily complex expressions.  Also
> tree_could_trap_p obviously extents to operands.

Ah, ok. I wasn't aware that it walks into tree.

>>
>>>> +
>>>> +  if (TREE_SIDE_EFFECTS (exp)
>>>> +      || tree_could_trap_p (exp))
>>>
>>> Move this check before the tcc_comparison check and remove the
>>> then redundant tree_could_trap_p check there.
>>
>> Ok
>>
>>>> +    return false;
>>>> +
>>>> +  switch (code)
>>>> +    {
>>>> +    case SSA_NAME:
>>>> +      return true;
>>>
>>> Do not handle here, it's handled in simple_operand_p.
>>
>> Well, was more a short-cut here.
>>
>>>> +    case TRUTH_NOT_EXPR:
>>>> +      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>>>> +    case BIT_NOT_EXPR:
>>>> +      if (TREE_CODE (TREE_TYPE (exp)) != BOOLEAN_TYPE)
>>>> +       return false;
>>>
>>> Remove the BIT_NOT_EXPR handling.  Thus, simply change this switch
>>> to
>>
>> Why should we reject simple ~X operations from gimplified code here?
>
> Because this is FE triggered code.  From gimple you won't ever see
> such complex expressions (never even the TRUTH_AND*_EXPR variants).

Hmm, I thought we might see such thing in fold and/or.  But well, you
might be right.

>> I admit that from FE-code we won't see that, as always an integer-cast
>> is done for foo (_Bool x) { ... if (~x) ... }, but from
>> gimplified-code this is the general description of an boolean-typed !=
>> 0?
>>
>>> if (code == TRUTH_NOT_EXPR)
>>>  return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>>>
>>> return simple_operand_p (exp);
>>>
>>>> +      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>>>> +    default:
>>>> +      return simple_operand_p (exp);
>>>> +    }
>>>> +}
>>>> +
>>>>
>>>>  /* The following functions are subroutines to fold_range_test and allow it to
>>>>    try to change a logical combination of comparisons into a range test.
>>>> @@ -4888,7 +4928,7 @@ fold_range_test (location_t loc, enum tr
>>>>   return 0;
>>>>  }
>>>>
>>>> -/* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
>>>> +/* Subroutine for fold_truth_andor_1: C is an INTEGER_CST interpreted as a P
>>>>    bit value.  Arrange things so the extra bits will be set to zero if and
>>>>    only if C is signed-extended to its full width.  If MASK is nonzero,
>>>>    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
>>>> @@ -5025,8 +5065,8 @@ merge_truthop_with_opposite_arm (locatio
>>>>    We return the simplified tree or 0 if no optimization is possible.  */
>>>>
>>>>  static tree
>>>> -fold_truthop (location_t loc, enum tree_code code, tree truth_type,
>>>> -             tree lhs, tree rhs)
>>>> +fold_truth_andor_1 (location_t loc, enum tree_code code, tree truth_type,
>>>> +                   tree lhs, tree rhs)
>>>>  {
>>>>   /* If this is the "or" of two comparisons, we can do something if
>>>>      the comparisons are NE_EXPR.  If this is the "and", we can do something
>>>> @@ -5054,8 +5094,6 @@ fold_truthop (location_t loc, enum tree_
>>>>   tree lntype, rntype, result;
>>>>   HOST_WIDE_INT first_bit, end_bit;
>>>>   int volatilep;
>>>> -  tree orig_lhs = lhs, orig_rhs = rhs;
>>>> -  enum tree_code orig_code = code;
>>>>
>>>>   /* Start by getting the comparison codes.  Fail if anything is volatile.
>>>>      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
>>>> @@ -5119,8 +5157,7 @@ fold_truthop (location_t loc, enum tree_
>>>>   /* If the RHS can be evaluated unconditionally and its operands are
>>>>      simple, it wins to evaluate the RHS unconditionally on machines
>>>>      with expensive branches.  In this case, this isn't a comparison
>>>> -     that can be merged.  Avoid doing this if the RHS is a floating-point
>>>> -     comparison since those can trap.  */
>>>> +     that can be merged.  */
>>>>
>>>>   if (BRANCH_COST (optimize_function_for_speed_p (cfun),
>>>>                   false) >= 2
>>>> @@ -5149,13 +5186,6 @@ fold_truthop (location_t loc, enum tree_
>>>>                           build2 (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
>>>>                                   ll_arg, rl_arg),
>>>>                           build_int_cst (TREE_TYPE (ll_arg), 0));
>>>> -
>>>> -      if (LOGICAL_OP_NON_SHORT_CIRCUIT)
>>>> -       {
>>>> -         if (code != orig_code || lhs != orig_lhs || rhs != orig_rhs)
>>>> -           return build2_loc (loc, code, truth_type, lhs, rhs);
>>>> -         return NULL_TREE;
>>>> -       }
>>>>     }
>>>>
>>>>   /* See if the comparisons can be merged.  Then get all the parameters for
>>>> @@ -8380,13 +8410,49 @@ fold_truth_andor (location_t loc, enum t
>>>>      lhs is another similar operation, try to merge its rhs with our
>>>>      rhs.  Then try to merge our lhs and rhs.  */
>>>>   if (TREE_CODE (arg0) == code
>>>> -      && 0 != (tem = fold_truthop (loc, code, type,
>>>> -                                  TREE_OPERAND (arg0, 1), arg1)))
>>>> +      && 0 != (tem = fold_truth_andor_1 (loc, code, type,
>>>> +                                        TREE_OPERAND (arg0, 1), arg1)))
>>>>     return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem);
>>>>
>>>> -  if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
>>>> +  if ((tem = fold_truth_andor_1 (loc, code, type, arg0, arg1)) != 0)
>>>>     return tem;
>>>>
>>>> +  if ((code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR)
>>>> +      && (BRANCH_COST (optimize_function_for_speed_p (cfun),
>>>> +                      false) >= 2)
>>>> +      && LOGICAL_OP_NON_SHORT_CIRCUIT
>>>> +      && simple_operand_p_2 (arg1))
>>>> +    {
>>>> +      enum tree_code ncode = (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR
>>>> +                                                      : TRUTH_OR_EXPR);
>>>> +
>>>> +      /* Transform ((A AND-IF B) AND-IF C) into (A AND-IF (B AND C)),
>>>> +         or ((A OR-IF B) OR-IF C) into (A OR-IF (B OR C))
>>>> +         We don't want to pack more than two leafs to a non-IF AND/OR
>>>> +         expression.
>>>> +         If tree-code of left-hand operand isn't an AND/OR-IF code and not
>>>> +         equal to CODE, then we don't want to add right-hand operand.
>>>> +         If the inner right-hand side of left-hand operand has side-effects,
>>>> +         or isn't simple, then we can't add to it, as otherwise we might
>>>> +         destroy if-sequence.  */
>>>> +      if (TREE_CODE (arg0) == code
>>>> +         /* Needed for sequence points to handle trappings, and
>>>> +            side-effects.  */
>>>> +         && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
>>>> +       {
>>>> +         tem = fold_build2_loc (loc, ncode, type, TREE_OPERAND (arg0, 1),
>>>> +                               arg1);
>>>> +         return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
>>>> +                                tem);
>>>> +       }
>>>
>>> I see you insist on this change.  Let me explain again.  You do this
>>> for ((A AND-IF B) AND-IF C) but you don't do this for
>>> ((A AND-IF B) AND C).  Why?  That is what doesn't make sense ot me.
>>> Thus omit this hunk.
>>
>> Well, first ((A AND-IF B) AND C) would be an ill sequence,  as AND is
>> associative. So we would simply break sequence points for && and ||.
>> If left-hand operand is an AND/OR-IF then outer operand has to always
>> an ?-IF operation, too.
>
> Why?  It's something like (ptr && *ptr) & x.  Whether you evaluate
> x or (ptr && *ptr) first does not matter.  But you have to check
> whether ptr is non-null before dereferencing it.  So it's clearly not
> ill-formed.  You may argue the transform is pointless and we should
> associate the & instead.  Do you?

well, if you are explict writing such thing as binary-and, it would be
associative anyway and code doesn't change here anything.  Binary and
!= logical and. The point about if we see something as (A TRUTH-IF B)
TRUTH B), we don't want to change it at all.  The outer if for this
already checks that this operation is just to be used on TRUTH-IF.  To
modify a TRUTH to a TRUTH is pretty point-less, isn't it?  If we would
allow to sink the case (A TRUTH-IF B) TRUTH C to (A TRUTH-IF (B TRUTH
C)), which might be of some intererest, but still would change
association rule here from point of C specification.  By C standard
each ||,&& is treated as a separate sequence-point.  Only in case that
previous and next &&/|| operand have no side-effects, we can apply to
them associative law.  Or do I read C-spec here wrong?

Regards,
Kai
Richard Guenther - Oct. 17, 2011, 11:42 a.m.
On Mon, Oct 17, 2011 at 1:31 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2011/10/17 Richard Guenther <richard.guenther@gmail.com>:
>> On Mon, Oct 17, 2011 at 12:59 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>> 2011/10/17 Richard Guenther <richard.guenther@gmail.com>:
>>>> On Fri, Oct 14, 2011 at 9:43 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>>> Hello,
>>>>>
>>>>> So I committed the gimplify patch separate.  And here is the remaining
>>>>> fold-const patch.
>>>>> The important tests here are in gcc.dg/tree-ssa/builtin-expect[1-4].c, which
>>>>> cover the one special-case for branching. Also tree-ssa/20040204-1.c covers
>>>>> tests for branching code (on targets having high-engough BRANCH_COST and no
>>>>> special-casing - like MIPS, S/390, and AVR.
>>>>>
>>>>> ChangeLog
>>>>>
>>>>> 2011-10-14  Kai Tietz  <ktietz@redhat.com>
>>>>>
>>>>>        * fold-const.c (simple_operand_p_2): New function.
>>>>>        (fold_truthop): Rename to
>>>>>        (fold_truth_andor_1): function name.
>>>>>        Additionally remove branching creation for logical and/or.
>>>>>        (fold_truth_andor): Handle branching creation for logical and/or here.
>>>>>
>>>>> Bootstrapped and regression-tested for all languages plus Ada and
>>>>> Obj-C++ on x86_64-pc-linux-gnu.
>>>>> Ok for apply?
>>>>
>>>> Ok with ...
>>>>
>>>>> Regards,
>>>>> Kai
>>>>>
>>>>> Index: gcc/gcc/fold-const.c
>>>>> ===================================================================
>>>>> --- gcc.orig/gcc/fold-const.c
>>>>> +++ gcc/gcc/fold-const.c
>>>>> @@ -112,13 +112,13 @@ static tree decode_field_reference (loca
>>>>>  static int all_ones_mask_p (const_tree, int);
>>>>>  static tree sign_bit_p (tree, const_tree);
>>>>>  static int simple_operand_p (const_tree);
>>>>> +static bool simple_operand_p_2 (tree);
>>>>>  static tree range_binop (enum tree_code, tree, tree, int, tree, int);
>>>>>  static tree range_predecessor (tree);
>>>>>  static tree range_successor (tree);
>>>>>  static tree fold_range_test (location_t, enum tree_code, tree, tree, tree);
>>>>>  static tree fold_cond_expr_with_comparison (location_t, tree, tree,
>>>>> tree, tree);
>>>>>  static tree unextend (tree, int, int, tree);
>>>>> -static tree fold_truthop (location_t, enum tree_code, tree, tree, tree);
>>>>>  static tree optimize_minmax_comparison (location_t, enum tree_code,
>>>>>                                        tree, tree, tree);
>>>>>  static tree extract_muldiv (tree, tree, enum tree_code, tree, bool *);
>>>>> @@ -3500,7 +3500,7 @@ optimize_bit_field_compare (location_t l
>>>>>   return lhs;
>>>>>  }
>>>>>
>>>>> -/* Subroutine for fold_truthop: decode a field reference.
>>>>> +/* Subroutine for fold_truth_andor_1: decode a field reference.
>>>>>
>>>>>    If EXP is a comparison reference, we return the innermost reference.
>>>>>
>>>>> @@ -3668,7 +3668,7 @@ sign_bit_p (tree exp, const_tree val)
>>>>>   return NULL_TREE;
>>>>>  }
>>>>>
>>>>> -/* Subroutine for fold_truthop: determine if an operand is simple enough
>>>>> +/* Subroutine for fold_truth_andor_1: determine if an operand is simple enough
>>>>>    to be evaluated unconditionally.  */
>>>>>
>>>>>  static int
>>>>> @@ -3678,7 +3678,7 @@ simple_operand_p (const_tree exp)
>>>>>   STRIP_NOPS (exp);
>>>>>
>>>>>   return (CONSTANT_CLASS_P (exp)
>>>>> -         || TREE_CODE (exp) == SSA_NAME
>>>>> +         || TREE_CODE (exp) == SSA_NAME
>>>>>          || (DECL_P (exp)
>>>>>              && ! TREE_ADDRESSABLE (exp)
>>>>>              && ! TREE_THIS_VOLATILE (exp)
>>>>> @@ -3692,6 +3692,46 @@ simple_operand_p (const_tree exp)
>>>>>                 registers aren't expensive.  */
>>>>>              && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
>>>>>  }
>>>>> +
>>>>> +/* Subroutine for fold_truth_andor: determine if an operand is simple enough
>>>>> +   to be evaluated unconditionally.
>>>>> +   I addition to simple_operand_p, we assume that comparisons and logic-not
>>>>> +   operations are simple, if their operands are simple, too.  */
>>>>> +
>>>>> +static bool
>>>>> +simple_operand_p_2 (tree exp)
>>>>> +{
>>>>> +  enum tree_code code;
>>>>> +
>>>>> +  /* Strip any conversions that don't change the machine mode.  */
>>>>> +  STRIP_NOPS (exp);
>>>>> +
>>>>> +  code = TREE_CODE (exp);
>>>>> +
>>>>> +  if (TREE_CODE_CLASS (code) == tcc_comparison)
>>>>> +    return (!tree_could_trap_p (exp)
>>>>> +           && simple_operand_p_2 (TREE_OPERAND (exp, 0))
>>>>> +           && simple_operand_p_2 (TREE_OPERAND (exp, 1)));
>>>>
>>>> recurse with simple_operand_p.
>>>
>>> No, as this again would reject simple operations and additionally
>>> wouldn't check for trapping.
>>
>> ?  Your code allows arbitrarily complex expressions.  Also
>> tree_could_trap_p obviously extents to operands.
>
> Ah, ok. I wasn't aware that it walks into tree.
>
>>>
>>>>> +
>>>>> +  if (TREE_SIDE_EFFECTS (exp)
>>>>> +      || tree_could_trap_p (exp))
>>>>
>>>> Move this check before the tcc_comparison check and remove the
>>>> then redundant tree_could_trap_p check there.
>>>
>>> Ok
>>>
>>>>> +    return false;
>>>>> +
>>>>> +  switch (code)
>>>>> +    {
>>>>> +    case SSA_NAME:
>>>>> +      return true;
>>>>
>>>> Do not handle here, it's handled in simple_operand_p.
>>>
>>> Well, was more a short-cut here.
>>>
>>>>> +    case TRUTH_NOT_EXPR:
>>>>> +      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>>>>> +    case BIT_NOT_EXPR:
>>>>> +      if (TREE_CODE (TREE_TYPE (exp)) != BOOLEAN_TYPE)
>>>>> +       return false;
>>>>
>>>> Remove the BIT_NOT_EXPR handling.  Thus, simply change this switch
>>>> to
>>>
>>> Why should we reject simple ~X operations from gimplified code here?
>>
>> Because this is FE triggered code.  From gimple you won't ever see
>> such complex expressions (never even the TRUTH_AND*_EXPR variants).
>
> Hmm, I thought we might see such thing in fold and/or.  But well, you
> might be right.
>
>>> I admit that from FE-code we won't see that, as always an integer-cast
>>> is done for foo (_Bool x) { ... if (~x) ... }, but from
>>> gimplified-code this is the general description of an boolean-typed !=
>>> 0?
>>>
>>>> if (code == TRUTH_NOT_EXPR)
>>>>  return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>>>>
>>>> return simple_operand_p (exp);
>>>>
>>>>> +      return simple_operand_p_2 (TREE_OPERAND (exp, 0));
>>>>> +    default:
>>>>> +      return simple_operand_p (exp);
>>>>> +    }
>>>>> +}
>>>>> +
>>>>>
>>>>>  /* The following functions are subroutines to fold_range_test and allow it to
>>>>>    try to change a logical combination of comparisons into a range test.
>>>>> @@ -4888,7 +4928,7 @@ fold_range_test (location_t loc, enum tr
>>>>>   return 0;
>>>>>  }
>>>>>
>>>>> -/* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
>>>>> +/* Subroutine for fold_truth_andor_1: C is an INTEGER_CST interpreted as a P
>>>>>    bit value.  Arrange things so the extra bits will be set to zero if and
>>>>>    only if C is signed-extended to its full width.  If MASK is nonzero,
>>>>>    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
>>>>> @@ -5025,8 +5065,8 @@ merge_truthop_with_opposite_arm (locatio
>>>>>    We return the simplified tree or 0 if no optimization is possible.  */
>>>>>
>>>>>  static tree
>>>>> -fold_truthop (location_t loc, enum tree_code code, tree truth_type,
>>>>> -             tree lhs, tree rhs)
>>>>> +fold_truth_andor_1 (location_t loc, enum tree_code code, tree truth_type,
>>>>> +                   tree lhs, tree rhs)
>>>>>  {
>>>>>   /* If this is the "or" of two comparisons, we can do something if
>>>>>      the comparisons are NE_EXPR.  If this is the "and", we can do something
>>>>> @@ -5054,8 +5094,6 @@ fold_truthop (location_t loc, enum tree_
>>>>>   tree lntype, rntype, result;
>>>>>   HOST_WIDE_INT first_bit, end_bit;
>>>>>   int volatilep;
>>>>> -  tree orig_lhs = lhs, orig_rhs = rhs;
>>>>> -  enum tree_code orig_code = code;
>>>>>
>>>>>   /* Start by getting the comparison codes.  Fail if anything is volatile.
>>>>>      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
>>>>> @@ -5119,8 +5157,7 @@ fold_truthop (location_t loc, enum tree_
>>>>>   /* If the RHS can be evaluated unconditionally and its operands are
>>>>>      simple, it wins to evaluate the RHS unconditionally on machines
>>>>>      with expensive branches.  In this case, this isn't a comparison
>>>>> -     that can be merged.  Avoid doing this if the RHS is a floating-point
>>>>> -     comparison since those can trap.  */
>>>>> +     that can be merged.  */
>>>>>
>>>>>   if (BRANCH_COST (optimize_function_for_speed_p (cfun),
>>>>>                   false) >= 2
>>>>> @@ -5149,13 +5186,6 @@ fold_truthop (location_t loc, enum tree_
>>>>>                           build2 (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
>>>>>                                   ll_arg, rl_arg),
>>>>>                           build_int_cst (TREE_TYPE (ll_arg), 0));
>>>>> -
>>>>> -      if (LOGICAL_OP_NON_SHORT_CIRCUIT)
>>>>> -       {
>>>>> -         if (code != orig_code || lhs != orig_lhs || rhs != orig_rhs)
>>>>> -           return build2_loc (loc, code, truth_type, lhs, rhs);
>>>>> -         return NULL_TREE;
>>>>> -       }
>>>>>     }
>>>>>
>>>>>   /* See if the comparisons can be merged.  Then get all the parameters for
>>>>> @@ -8380,13 +8410,49 @@ fold_truth_andor (location_t loc, enum t
>>>>>      lhs is another similar operation, try to merge its rhs with our
>>>>>      rhs.  Then try to merge our lhs and rhs.  */
>>>>>   if (TREE_CODE (arg0) == code
>>>>> -      && 0 != (tem = fold_truthop (loc, code, type,
>>>>> -                                  TREE_OPERAND (arg0, 1), arg1)))
>>>>> +      && 0 != (tem = fold_truth_andor_1 (loc, code, type,
>>>>> +                                        TREE_OPERAND (arg0, 1), arg1)))
>>>>>     return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem);
>>>>>
>>>>> -  if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
>>>>> +  if ((tem = fold_truth_andor_1 (loc, code, type, arg0, arg1)) != 0)
>>>>>     return tem;
>>>>>
>>>>> +  if ((code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR)
>>>>> +      && (BRANCH_COST (optimize_function_for_speed_p (cfun),
>>>>> +                      false) >= 2)
>>>>> +      && LOGICAL_OP_NON_SHORT_CIRCUIT
>>>>> +      && simple_operand_p_2 (arg1))
>>>>> +    {
>>>>> +      enum tree_code ncode = (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR
>>>>> +                                                      : TRUTH_OR_EXPR);
>>>>> +
>>>>> +      /* Transform ((A AND-IF B) AND-IF C) into (A AND-IF (B AND C)),
>>>>> +         or ((A OR-IF B) OR-IF C) into (A OR-IF (B OR C))
>>>>> +         We don't want to pack more than two leafs to a non-IF AND/OR
>>>>> +         expression.
>>>>> +         If tree-code of left-hand operand isn't an AND/OR-IF code and not
>>>>> +         equal to CODE, then we don't want to add right-hand operand.
>>>>> +         If the inner right-hand side of left-hand operand has side-effects,
>>>>> +         or isn't simple, then we can't add to it, as otherwise we might
>>>>> +         destroy if-sequence.  */
>>>>> +      if (TREE_CODE (arg0) == code
>>>>> +         /* Needed for sequence points to handle trappings, and
>>>>> +            side-effects.  */
>>>>> +         && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
>>>>> +       {
>>>>> +         tem = fold_build2_loc (loc, ncode, type, TREE_OPERAND (arg0, 1),
>>>>> +                               arg1);
>>>>> +         return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
>>>>> +                                tem);
>>>>> +       }
>>>>
>>>> I see you insist on this change.  Let me explain again.  You do this
>>>> for ((A AND-IF B) AND-IF C) but you don't do this for
>>>> ((A AND-IF B) AND C).  Why?  That is what doesn't make sense ot me.
>>>> Thus omit this hunk.
>>>
>>> Well, first ((A AND-IF B) AND C) would be an ill sequence,  as AND is
>>> associative. So we would simply break sequence points for && and ||.
>>> If left-hand operand is an AND/OR-IF then outer operand has to always
>>> an ?-IF operation, too.
>>
>> Why?  It's something like (ptr && *ptr) & x.  Whether you evaluate
>> x or (ptr && *ptr) first does not matter.  But you have to check
>> whether ptr is non-null before dereferencing it.  So it's clearly not
>> ill-formed.  You may argue the transform is pointless and we should
>> associate the & instead.  Do you?
>
> well, if you are explict writing such thing as binary-and, it would be
> associative anyway and code doesn't change here anything.  Binary and
> != logical and. The point about if we see something as (A TRUTH-IF B)
> TRUTH B), we don't want to change it at all.  The outer if for this
> already checks that this operation is just to be used on TRUTH-IF.  To
> modify a TRUTH to a TRUTH is pretty point-less, isn't it?  If we would
> allow to sink the case (A TRUTH-IF B) TRUTH C to (A TRUTH-IF (B TRUTH
> C)), which might be of some intererest, but still would change
> association rule here from point of C specification.  By C standard
> each ||,&& is treated as a separate sequence-point.  Only in case that
> previous and next &&/|| operand have no side-effects, we can apply to
> them associative law.  Or do I read C-spec here wrong?

Certainly if for (A TRUTH-IF B) TRUTH-IF C it is valid to associate
it as A TRUTH-IF (B IF C) then it is valid to do the same for
(A TRUTH-IF B) IF C.

> Regards,
> Kai
>
Kai Tietz - Oct. 17, 2011, 12:22 p.m.
Ok, I see.  This might be profitable to do that.  So fold_truth_op
hunk looks like this

@@ -5149,13 +5176,6 @@ fold_truthop (location_t loc, enum tree_
 			   build2 (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
 				   ll_arg, rl_arg),
 			   build_int_cst (TREE_TYPE (ll_arg), 0));
-
-      if (LOGICAL_OP_NON_SHORT_CIRCUIT)
-	{
-	  if (code != orig_code || lhs != orig_lhs || rhs != orig_rhs)
-	    return build2_loc (loc, code, truth_type, lhs, rhs);
-	  return NULL_TREE;
-	}
     }

   /* See if the comparisons can be merged.  Then get all the parameters for
@@ -8380,13 +8400,77 @@ fold_truth_andor (location_t loc, enum t
      lhs is another similar operation, try to merge its rhs with our
      rhs.  Then try to merge our lhs and rhs.  */
   if (TREE_CODE (arg0) == code
-      && 0 != (tem = fold_truthop (loc, code, type,
-				   TREE_OPERAND (arg0, 1), arg1)))
+      && 0 != (tem = fold_truth_andor_1 (loc, code, type,
+					 TREE_OPERAND (arg0, 1), arg1)))
     return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem);

-  if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
+  if ((tem = fold_truth_andor_1 (loc, code, type, arg0, arg1)) != 0)
     return tem;

+  if ((BRANCH_COST (optimize_function_for_speed_p (cfun),
+		    false) >= 2)
+      && LOGICAL_OP_NON_SHORT_CIRCUIT
+      && simple_operand_p_2 (arg1))
+    {
+      enum tree_code ncode;
+
+      if (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR)
+        {
+	  ncode = (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
+
+	  /* Transform ((A AND-IF B) AND-IF C) into (A AND-IF (B AND C)),
+	     or ((A OR-IF B) OR-IF C) into (A OR-IF (B OR C))
+	     We don't want to pack more than two leafs to a non-IF AND/OR
+	     expression.
+	     If tree-code of left-hand operand isn't an AND/OR-IF code and not
+	     equal to CODE, then we don't want to add right-hand operand.
+	     If the inner right-hand side of left-hand operand has
+	     side-effects, or isn't simple, then we can't add to it,
+	     as otherwise we might destroy if-sequence.  */
+	  if (TREE_CODE (arg0) == code
+	      /* Needed for sequence points to handle trappings, and
+		 side-effects.  */
+	      && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
+	    {
+	      tem = fold_build2_loc (loc, ncode, type, TREE_OPERAND (arg0, 1),
+				     arg1);
+	      return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
+				      tem);
+	    }
+	  /* Transform (A AND-IF B) into (A AND B), or (A OR-IF B)
+	     into (A OR B).
+	     For sequence point consistancy, we need to check for trapping,
+	     and side-effects.  */
+	  else if (simple_operand_p_2 (arg0))
+	    return fold_build2_loc (loc, ncode, type, arg0, arg1);
+	}
+      else
+        {
+	  ncode = (code == TRUTH_AND_EXPR ? TRUTH_ANDIF_EXPR
+					  : TRUTH_ORIF_EXPR);
+	  /* Transform ((A AND-IF B) AND C) into (A AND-IF (B AND C)),
+	     or ((A OR-IF B) OR C) into (A OR-IF (B OR C))
+	     We don't want to pack more than two leafs to a non-IF AND/OR
+	     expression.
+	     If tree-code of left-hand operand isn't an AND/OR-IF code and not
+	     equal to NCODE, then we don't want to add right-hand operand.
+	     If the inner right-hand side of left-hand operand has
+	     side-effects, or isn't simple, then we can't add to it,
+	     as otherwise we might destroy if-sequence.  */
+	  if (TREE_CODE (arg0) == ncode
+	      /* Needed for sequence points to handle trappings, and
+		 side-effects.  */
+	      && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
+	    {
+	      tem = fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 1),
+				     arg1);
+	      return fold_build2_loc (loc, ncode, type,
+				      TREE_OPERAND (arg0, 0), tem);
+	    }
+	}
+
+    }
+
   return NULL_TREE;
 }

Ok, with other changes you mentioned?

Regards,
Kai
Richard Guenther - Oct. 17, 2011, 1:01 p.m.
On Mon, Oct 17, 2011 at 2:22 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Ok, I see.  This might be profitable to do that.  So fold_truth_op
> hunk looks like this
>
> @@ -5149,13 +5176,6 @@ fold_truthop (location_t loc, enum tree_
>                           build2 (BIT_IOR_EXPR, TREE_TYPE (ll_arg),
>                                   ll_arg, rl_arg),
>                           build_int_cst (TREE_TYPE (ll_arg), 0));
> -
> -      if (LOGICAL_OP_NON_SHORT_CIRCUIT)
> -       {
> -         if (code != orig_code || lhs != orig_lhs || rhs != orig_rhs)
> -           return build2_loc (loc, code, truth_type, lhs, rhs);
> -         return NULL_TREE;
> -       }
>     }
>
>   /* See if the comparisons can be merged.  Then get all the parameters for
> @@ -8380,13 +8400,77 @@ fold_truth_andor (location_t loc, enum t
>      lhs is another similar operation, try to merge its rhs with our
>      rhs.  Then try to merge our lhs and rhs.  */
>   if (TREE_CODE (arg0) == code
> -      && 0 != (tem = fold_truthop (loc, code, type,
> -                                  TREE_OPERAND (arg0, 1), arg1)))
> +      && 0 != (tem = fold_truth_andor_1 (loc, code, type,
> +                                        TREE_OPERAND (arg0, 1), arg1)))
>     return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem);
>
> -  if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
> +  if ((tem = fold_truth_andor_1 (loc, code, type, arg0, arg1)) != 0)
>     return tem;
>
> +  if ((BRANCH_COST (optimize_function_for_speed_p (cfun),
> +                   false) >= 2)
> +      && LOGICAL_OP_NON_SHORT_CIRCUIT
> +      && simple_operand_p_2 (arg1))
> +    {
> +      enum tree_code ncode;
> +
> +      if (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR)
> +        {
> +         ncode = (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
> +
> +         /* Transform ((A AND-IF B) AND-IF C) into (A AND-IF (B AND C)),
> +            or ((A OR-IF B) OR-IF C) into (A OR-IF (B OR C))
> +            We don't want to pack more than two leafs to a non-IF AND/OR
> +            expression.
> +            If tree-code of left-hand operand isn't an AND/OR-IF code and not
> +            equal to CODE, then we don't want to add right-hand operand.
> +            If the inner right-hand side of left-hand operand has
> +            side-effects, or isn't simple, then we can't add to it,
> +            as otherwise we might destroy if-sequence.  */
> +         if (TREE_CODE (arg0) == code
> +             /* Needed for sequence points to handle trappings, and
> +                side-effects.  */
> +             && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
> +           {
> +             tem = fold_build2_loc (loc, ncode, type, TREE_OPERAND (arg0, 1),
> +                                    arg1);
> +             return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
> +                                     tem);
> +           }
> +         /* Transform (A AND-IF B) into (A AND B), or (A OR-IF B)
> +            into (A OR B).
> +            For sequence point consistancy, we need to check for trapping,
> +            and side-effects.  */
> +         else if (simple_operand_p_2 (arg0))
> +           return fold_build2_loc (loc, ncode, type, arg0, arg1);
> +       }
> +      else
> +        {
> +         ncode = (code == TRUTH_AND_EXPR ? TRUTH_ANDIF_EXPR
> +                                         : TRUTH_ORIF_EXPR);
> +         /* Transform ((A AND-IF B) AND C) into (A AND-IF (B AND C)),
> +            or ((A OR-IF B) OR C) into (A OR-IF (B OR C))
> +            We don't want to pack more than two leafs to a non-IF AND/OR
> +            expression.
> +            If tree-code of left-hand operand isn't an AND/OR-IF code and not
> +            equal to NCODE, then we don't want to add right-hand operand.
> +            If the inner right-hand side of left-hand operand has
> +            side-effects, or isn't simple, then we can't add to it,
> +            as otherwise we might destroy if-sequence.  */
> +         if (TREE_CODE (arg0) == ncode
> +             /* Needed for sequence points to handle trappings, and
> +                side-effects.  */
> +             && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
> +           {
> +             tem = fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 1),
> +                                    arg1);
> +             return fold_build2_loc (loc, ncode, type,
> +                                     TREE_OPERAND (arg0, 0), tem);
> +           }
> +       }
> +
> +    }
> +
>   return NULL_TREE;
>  }
>
> Ok, with other changes you mentioned?

This can be done without so much code duplication.

> Regards,
> Kai
>
Kai Tietz - Oct. 17, 2011, 1:36 p.m.
Sure,

Is simplier and also handles (A T[-IF] (B T-IF C) -> (A T B) T-IF C
case, which can happen by framing in conditions.

@@ -8380,13 +8400,65 @@ fold_truth_andor (location_t loc, enum t
      lhs is another similar operation, try to merge its rhs with our
      rhs.  Then try to merge our lhs and rhs.  */
   if (TREE_CODE (arg0) == code
-      && 0 != (tem = fold_truthop (loc, code, type,
-				   TREE_OPERAND (arg0, 1), arg1)))
+      && 0 != (tem = fold_truth_andor_1 (loc, code, type,
+					 TREE_OPERAND (arg0, 1), arg1)))
     return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem);

-  if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
+  if ((tem = fold_truth_andor_1 (loc, code, type, arg0, arg1)) != 0)
     return tem;

+  if ((BRANCH_COST (optimize_function_for_speed_p (cfun),
+		    false) >= 2)
+      && LOGICAL_OP_NON_SHORT_CIRCUIT)
+    {
+      enum tree_code ncode, icode;
+
+      ncode = (code == TRUTH_ANDIF_EXPR || code == TRUTH_AND_EXPR)
+	      ? TRUTH_AND_EXPR : TRUTH_OR_EXPR;
+      icode = ncode == TRUTH_AND_EXPR ? TRUTH_ANDIF_EXPR : TRUTH_ORIF_EXPR;
+
+      /* Transform ((A AND-IF B) AND[-IF] C) into (A AND-IF (B AND C)),
+	 or ((A OR-IF B) OR[-IF] C) into (A OR-IF (B OR C))
+	 We don't want to pack more than two leafs to a non-IF AND/OR
+	 expression.
+	 If tree-code of left-hand operand isn't an AND/OR-IF code and not
+	 equal to IF-CODE, then we don't want to add right-hand operand.
+	 If the inner right-hand side of left-hand operand has
+	 side-effects, or isn't simple, then we can't add to it,
+	 as otherwise we might destroy if-sequence.  */
+      if (TREE_CODE (arg0) == icode
+	  && simple_operand_p_2 (arg1)
+	  /* Needed for sequence points to handle trappings, and
+	     side-effects.  */
+	  && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
+	{
+	  tem = fold_build2_loc (loc, ncode, type, TREE_OPERAND (arg0, 1),
+				 arg1);
+	  return fold_build2_loc (loc, icode, type, TREE_OPERAND (arg0, 0),
+				  tem);
+	}
+	/* Same as abouve but for (A AND[-IF] (B AND-IF C)) -> ((A AND B) AND-IF C),
+	   or (A OR[-IF] (B OR-IF C) -> ((A OR B) OR-IF C).  */
+      else if (TREE_CODE (arg1) == icode
+	  && simple_operand_p_2 (arg0)
+	  /* Needed for sequence points to handle trappings, and
+	     side-effects.  */
+	  && simple_operand_p_2 (TREE_OPERAND (arg1, 0)))
+	{
+	  tem = fold_build2_loc (loc, ncode, type,
+				 arg0, TREE_OPERAND (arg1, 0));
+	  return fold_build2_loc (loc, icode, type, tem,
+				  TREE_OPERAND (arg1, 1));
+	}
+      /* Transform (A AND-IF B) into (A AND B), or (A OR-IF B)
+	 into (A OR B).
+	 For sequence point consistancy, we need to check for trapping,
+	 and side-effects.  */
+      else if (code == icode && simple_operand_p_2 (arg0)
+               && simple_operand_p_2 (arg1))
+	return fold_build2_loc (loc, ncode, type, arg0, arg1);
+    }
+
   return NULL_TREE;
 }

Regards,
Kai
Richard Guenther - Oct. 17, 2011, 2:38 p.m.
On Mon, Oct 17, 2011 at 3:36 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Sure,
>
> Is simplier and also handles (A T[-IF] (B T-IF C) -> (A T B) T-IF C
> case, which can happen by framing in conditions.
>
> @@ -8380,13 +8400,65 @@ fold_truth_andor (location_t loc, enum t
>      lhs is another similar operation, try to merge its rhs with our
>      rhs.  Then try to merge our lhs and rhs.  */
>   if (TREE_CODE (arg0) == code
> -      && 0 != (tem = fold_truthop (loc, code, type,
> -                                  TREE_OPERAND (arg0, 1), arg1)))
> +      && 0 != (tem = fold_truth_andor_1 (loc, code, type,
> +                                        TREE_OPERAND (arg0, 1), arg1)))
>     return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem);
>
> -  if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
> +  if ((tem = fold_truth_andor_1 (loc, code, type, arg0, arg1)) != 0)
>     return tem;
>
> +  if ((BRANCH_COST (optimize_function_for_speed_p (cfun),
> +                   false) >= 2)
> +      && LOGICAL_OP_NON_SHORT_CIRCUIT)
> +    {
> +      enum tree_code ncode, icode;
> +
> +      ncode = (code == TRUTH_ANDIF_EXPR || code == TRUTH_AND_EXPR)
> +             ? TRUTH_AND_EXPR : TRUTH_OR_EXPR;
> +      icode = ncode == TRUTH_AND_EXPR ? TRUTH_ANDIF_EXPR : TRUTH_ORIF_EXPR;
> +
> +      /* Transform ((A AND-IF B) AND[-IF] C) into (A AND-IF (B AND C)),
> +        or ((A OR-IF B) OR[-IF] C) into (A OR-IF (B OR C))
> +        We don't want to pack more than two leafs to a non-IF AND/OR
> +        expression.
> +        If tree-code of left-hand operand isn't an AND/OR-IF code and not
> +        equal to IF-CODE, then we don't want to add right-hand operand.
> +        If the inner right-hand side of left-hand operand has
> +        side-effects, or isn't simple, then we can't add to it,
> +        as otherwise we might destroy if-sequence.  */
> +      if (TREE_CODE (arg0) == icode
> +         && simple_operand_p_2 (arg1)
> +         /* Needed for sequence points to handle trappings, and
> +            side-effects.  */
> +         && simple_operand_p_2 (TREE_OPERAND (arg0, 1)))
> +       {
> +         tem = fold_build2_loc (loc, ncode, type, TREE_OPERAND (arg0, 1),
> +                                arg1);
> +         return fold_build2_loc (loc, icode, type, TREE_OPERAND (arg0, 0),
> +                                 tem);
> +       }
> +       /* Same as abouve but for (A AND[-IF] (B AND-IF C)) -> ((A AND B) AND-IF C),
> +          or (A OR[-IF] (B OR-IF C) -> ((A OR B) OR-IF C).  */
> +      else if (TREE_CODE (arg1) == icode
> +         && simple_operand_p_2 (arg0)
> +         /* Needed for sequence points to handle trappings, and
> +            side-effects.  */
> +         && simple_operand_p_2 (TREE_OPERAND (arg1, 0)))
> +       {
> +         tem = fold_build2_loc (loc, ncode, type,
> +                                arg0, TREE_OPERAND (arg1, 0));
> +         return fold_build2_loc (loc, icode, type, tem,
> +                                 TREE_OPERAND (arg1, 1));
> +       }
> +      /* Transform (A AND-IF B) into (A AND B), or (A OR-IF B)
> +        into (A OR B).
> +        For sequence point consistancy, we need to check for trapping,
> +        and side-effects.  */
> +      else if (code == icode && simple_operand_p_2 (arg0)
> +               && simple_operand_p_2 (arg1))
> +       return fold_build2_loc (loc, ncode, type, arg0, arg1);
> +    }
> +
>   return NULL_TREE;
>  }

Ok with the rest of the changes I requested.

Richard.

> Regards,
> Kai
>

Patch

Index: gcc/gcc/fold-const.c
===================================================================
--- gcc.orig/gcc/fold-const.c
+++ gcc/gcc/fold-const.c
@@ -112,13 +112,13 @@  static tree decode_field_reference (loca
 static int all_ones_mask_p (const_tree, int);
 static tree sign_bit_p (tree, const_tree);
 static int simple_operand_p (const_tree);
+static bool simple_operand_p_2 (tree);
 static tree range_binop (enum tree_code, tree, tree, int, tree, int);
 static tree range_predecessor (tree);
 static tree range_successor (tree);
 static tree fold_range_test (location_t, enum tree_code, tree, tree, tree);
 static tree fold_cond_expr_with_comparison (location_t, tree, tree,
tree, tree);
 static tree unextend (tree, int, int, tree);
-static tree fold_truthop (location_t, enum tree_code, tree, tree, tree);
 static tree optimize_minmax_comparison (location_t, enum tree_code,
 					tree, tree, tree);