Re: [PATCH][middle-end/88784] Middle end is missing some optimizations about unsigned

[Li Jia He <helijia@linux.ibm.com>]

[-- Attachment #1: Type: text/plain, Size: 5271 bytes --]



On 2019/7/1 3:30 PM, Richard Biener wrote:
> On Fri, 28 Jun 2019, Andrew Pinski wrote:
> 
>> On Thu, Jun 27, 2019 at 9:55 PM Li Jia He <helijia@linux.ibm.com> wrote:
>>>
>>>
>>>
>>> On 2019/6/27 11:48 PM, Jeff Law wrote:
>>>> On 6/27/19 12:11 AM, Li Jia He wrote:
>>>>> Hi,
>>>>>
>>>>> According to the optimizable case described by Qi Feng on
>>>>> issue 88784, we can combine the cases into the following:
>>>>>
>>>>> 1. x >  y  &&  x != XXX_MIN  -->   x > y
>>>>> 2. x >  y  &&  x == XXX_MIN  -->   false
>>>>> 3. x <= y  &&  x == XXX_MIN  -->   x == XXX_MIN
>>>>>
>>>>> 4. x <  y  &&  x != XXX_MAX  -->   x < y
>>>>> 5. x <  y  &&  x == XXX_MAX  -->   false
>>>>> 6. x >= y  &&  x == XXX_MAX  -->   x == XXX_MAX
>>>>>
>>>>> 7. x >  y  ||  x != XXX_MIN  -->   x != XXX_MIN
>>>>> 8. x <= y  ||  x != XXX_MIN  -->   true
>>>>> 9. x <= y  ||  x == XXX_MIN  -->   x <= y
>>>>>
>>>>> 10. x <  y  ||  x != XXX_MAX  -->   x != UXXX_MAX
>>>>> 11. x >= y  ||  x != XXX_MAX  -->   true
>>>>> 12. x >= y  ||  x == XXX_MAX  -->   x >= y
>>>>>
>>>>> Note: XXX_MIN represents the minimum value of type x.
>>>>>         XXX_MAX represents the maximum value of type x.
>>>>>
>>>>> Here we don't need to care about whether the operation is
>>>>> signed or unsigned.  For example, in the below equation:
>>>>>
>>>>> 'x >  y  &&  x != XXX_MIN  -->   x > y'
>>>>>
>>>>> If the x type is signed int and XXX_MIN is INT_MIN, we can
>>>>> optimize it to 'x > y'.  However, if the type of x is unsigned
>>>>> int and XXX_MIN is 0, we can still optimize it to 'x > y'.
>>>>>
>>>>> The regression testing for the patch was done on GCC mainline on
>>>>>
>>>>>       powerpc64le-unknown-linux-gnu (Power 9 LE)
>>>>>
>>>>> with no regressions.  Is it OK for trunk ?
>>>>>
>>>>> Thanks,
>>>>> Lijia He
>>>>>
>>>>> gcc/ChangeLog
>>>>>
>>>>> 2019-06-27  Li Jia He  <helijia@linux.ibm.com>
>>>>>           Qi Feng  <ffengqi@linux.ibm.com>
>>>>>
>>>>>       PR middle-end/88784
>>>>>       * gimple-fold.c (and_comparisons_contain_equal_operands): New function.
>>>>>       (and_comparisons_1): Use and_comparisons_contain_equal_operands.
>>>>>       (or_comparisons_contain_equal_operands): New function.
>>>>>       (or_comparisons_1): Use or_comparisons_contain_equal_operands.
>>>> Would this be better done via match.pd?  ISTM this transformation would
>>>> be well suited for that framework.
>>>
>>> Hi, Jeff
>>>
>>> I did this because of the following test case:
>>> `
>>> _Bool comp(unsigned x, unsigned y)
>>> {
>>>     return x > y && x != 0;
>>> }
>>> `
>>> The gimple file dumped on the power platform is:
>>> `
>>> comp (unsigned int x, unsigned int y)
>>> {
>>>     _Bool D.2837;
>>>     int iftmp.0;
>>>
>>>     if (x > y) goto <D.2841>; else goto <D.2839>;
>>>     <D.2841>:
>>>     if (x != 0) goto <D.2842>; else goto <D.2839>;
>>>     <D.2842>:
>>>     iftmp.0 = 1;
>>>     goto <D.2840>;
>>>     <D.2839>:
>>>     iftmp.0 = 0;
>>>     <D.2840>:
>>>     D.2837 = (_Bool) iftmp.0;
>>>     return D.2837;
>>> }
>>> `
>>> However, the gimple file dumped on x86 is
>>> `
>>> comp (unsigned int x, unsigned int y)
>>> {
>>>     _Bool D.2837;
>>>
>>>     _1 = x > y;
>>>     _2 = x != 0;
>>>     _3 = _1 & _2;
>>>     _4 = (int) _3;
>>>     D.2837 = (_Bool) _4;
>>>     return D.2837;
>>> }
>>> `
>>>
>>> The reason for the inconsistency between these two behaviors is param
>>> logical-op-non-short-circuit.  If we add the pattern to the match.pd
>>> file, we can only optimize the situation in which the statement is in
>>> the same basic block (logical-op-non-short-circuit=1, x86).  But for
>>> a cross-basic block (logical-op-non-short-circuit=0, power), match.pd
>>> can't handle this situation.
>>>
>>> Another reason is that I found out maybe_fold_and_comparisons and
>>> maybe_fold_or_comparisons are not only called by ifcombine pass but
>>> also by reassoc pass. Using this method can basically unify param
>>> logical-op-non-short-circuit=0 or 1.
>>
>>
>> As mentioned before ifcombine pass should be using gimple-match
>> instead of fold_build.  Try converting ifcombine over to gimple-match
>> infrastructure and add these to match.pd.
> 
> Yes, I mentioned that in the PR.  The issue is that at the moment
> to combine x > y with x <= y you'd have to build GENERIC trees
> for both or temporary GIMPLE assign with a SSA def (and then feed
> that into the GENERIC or GIMPLE match.pd path).

Hi,

I did some experimentation using ‘temporary GIMPLE with a SSA def (and 
then feed that into the GIMPLE match.pd path’.  Could we consider the 
code in the attachment(I did a test and the code took effect)?

Thanks,
Lijia He

> 
> maybe_fold_and/or_comparisons handle two exploded binary expressions
> while the current match.pd entries handle at most one exploded one
> (the outermost then, either AND or OR).  But it would be definitely
> doable to auto-generate maybe_fold_and/or_comparisons from match.pd
> patterns which is what I'd ultimatively suggest to do (in some more
> generalized form maybe).  Either with a separate genmatch invocation
> or as part of the --gimple processing (not sure what is more feasible
> here).
> 
> I told Li Jia He that I don't expect him to do this work.
> 
> Note I didn't review the actual patch yet.
> 
> Thanks,
> Richard.
> 

[-- Attachment #2: match.diff --]
[-- Type: text/plain, Size: 5980 bytes --]

diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index dfb31a02078..9974b491626 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -5789,6 +5789,12 @@ and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
   return NULL_TREE;
 }
 
+static tree
+do_valueize (tree t)
+{
+  return t;
+}
+
 /* Try to simplify the AND of two comparisons, specified by
    (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
    If this can be simplified to a single expression (without requiring
@@ -5800,11 +5806,39 @@ tree
 maybe_fold_and_comparisons (enum tree_code code1, tree op1a, tree op1b,
 			    enum tree_code code2, tree op2a, tree op2b)
 {
-  tree t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
+  tree t1 = fold_build2 (code1, boolean_type_node, op1a, op1b);
+  tree t2 = fold_build2 (code2, boolean_type_node, op2a, op2b);
+
+  tree new_lhs1 = make_ssa_name (TREE_TYPE (t1));
+  tree new_lhs2 = make_ssa_name (TREE_TYPE (t2));
+
+  gassign *gassign1 = gimple_build_assign (new_lhs1, t1);
+  gassign *gassign2 = gimple_build_assign (new_lhs2, t2);
+
+  tree t = gimple_simplify (TRUTH_AND_EXPR, boolean_type_node,
+			    gimple_assign_lhs (gassign1),
+			    gimple_assign_lhs (gassign2), NULL, do_valueize);
+
+  if (!t)
+    {
+      t = gimple_simplify (TRUTH_AND_EXPR, boolean_type_node,
+			   gimple_assign_lhs (gassign2),
+			   gimple_assign_lhs (gassign1), NULL, do_valueize);
+    }
+
   if (t)
-    return t;
-  else
-    return and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
+    {
+      gimple *def = SSA_NAME_DEF_STMT (t);
+
+      if (!is_gimple_assign (def)
+	  || TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
+	return NULL_TREE;
+
+      return fold_build2 (gimple_assign_rhs_code (def), boolean_type_node,
+			  gimple_assign_rhs1 (def), gimple_assign_rhs2 (def));
+    }
+
+  return NULL_TREE;
 }
 
 /* Helper function for or_comparisons_1:  try to simplify the OR of the
diff --git a/gcc/match.pd b/gcc/match.pd
index f8e35e96d22..21a147d0ff1 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1859,6 +1859,101 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     { wide_int_to_tree (type, (wi::to_wide (@1)
 			       & (bitpos / BITS_PER_UNIT))); }))))
 
+/* x >  y  &&  x != XXX_MIN  -->  x > y  */
+(for and (truth_and bit_and)
+ (simplify
+  (and:c (gt:c@3 @0 @1) (ne @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && (wi::eq_p (wi::to_wide (@2), wi::min_value (TREE_TYPE (@2)))))
+    @3)))
+
+/* x >  y  &&  x == XXX_MIN  -->  false  */
+(for and (truth_and bit_and)
+ (simplify
+  (and:c (gt:c @0 @1) (eq @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && (wi::eq_p (wi::to_wide (@2), wi::min_value (TREE_TYPE (@2)))))
+    { boolean_false_node; })))
+
+/* x <=  y  &&  x == XXX_MIN  -->  x == XXX_MIN  */
+(for and (truth_and bit_and)
+ (simplify
+  (and:c (le:c @0 @1) (eq@3 @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && (wi::eq_p (wi::to_wide (@2), wi::min_value (TREE_TYPE (@2)))))
+    @3)))
+
+/* x <  y  &&  x != XXX_MAX  -->  x < y  */
+(for and (truth_and bit_and)
+ (simplify
+  (and:c (lt:c@3 @0 @1) (ne @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && (wi::eq_p (wi::to_wide (@2), wi::max_value (TREE_TYPE (@2)))))
+    @3)))
+
+/* x <  y  &&  x == XXX_MAX  -->  false  */
+(for and (truth_and bit_and)
+ (simplify
+  (and:c (lt:c @0 @1) (eq @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && (wi::eq_p (wi::to_wide (@2), wi::max_value (TREE_TYPE (@2)))))
+    { boolean_false_node; })))
+
+/* x >=  y  &&  x == XXX_MAX  -->  x == XXX_MAX  */
+(for and (truth_and bit_and)
+ (simplify
+  (and:c (ge:c @0 @1) (eq@3 @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && (wi::eq_p (wi::to_wide (@2), wi::max_value (TREE_TYPE (@2)))))
+    @3)))
+
+/* x >  y  ||  x != XXX_MIN   -->  x != XXX_MIN  */
+(for or (truth_or bit_ior)
+ (simplify
+  (or:c (gt:c @0 @1) (ne@3 @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && wi::eq_p (wi::to_wide (@2), wi::min_value (TREE_TYPE (@2))))
+    @3)))
+
+/* x <=  y  ||  x != XXX_MIN   -->  true  */
+(for or (truth_or bit_ior)
+ (simplify
+  (or:c (le:c @0 @1) (ne @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && wi::eq_p (wi::to_wide (@2), wi::min_value (TREE_TYPE (@2))))
+    { boolean_true_node; })))
+
+/* x <=  y  ||  x == XXX_MIN   -->  x <= y  */
+(for or (truth_or bit_ior)
+ (simplify
+  (or:c (le:c@3 @0 @1) (eq @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && wi::eq_p (wi::to_wide (@2), wi::min_value (TREE_TYPE (@2))))
+    @3)))
+
+/* x <  y  ||  x != XXX_MAX   -->  x != XXX_MAX  */
+(for or (truth_or bit_ior)
+ (simplify
+  (or:c (lt:c @0 @1) (ne@3 @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && wi::eq_p (wi::to_wide (@2), wi::max_value (TREE_TYPE (@2))))
+    @3)))
+
+/* x >=  y  ||  x != XXX_MAX   -->  true  */
+(for or (truth_or bit_ior)
+ (simplify
+  (or:c (ge:c @0 @1) (ne @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && wi::eq_p (wi::to_wide (@2), wi::max_value (TREE_TYPE (@2))))
+    { boolean_true_node; })))
+
+/* x >=  y  ||  x == XXX_MAX   -->  x >= y  */
+(for or (truth_or bit_ior)
+ (simplify
+  (or:c (ge:c@3 @0 @1) (eq @0 INTEGER_CST@2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE(@1))
+       && wi::eq_p (wi::to_wide (@2), wi::max_value (TREE_TYPE (@2))))
+    @3)))
 
 /* We can't reassociate at all for saturating types.  */
 (if (!TYPE_SATURATING (type))