On Tue, 26 Sep 2017, Jakub Jelinek wrote:
> Hi!
>
> Right now we handle x == 0 && y == 0 into (x | y) == 0
> and x == -1 && y == -1 into (x & y) == -1 optimizations just in
> match.pd, where it will handle the case where the && (or || if using !=)
> is actually & (or |) and they are next to each other.
> It doesn't handle the case when we have such comparisons as part of
> a larger && or || test that is split into multiple basic blocks or
> intermixed with other comparisons.
>
> The following patch teaches optimize_range_tests to optimize even these.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
Ok.
Richard.
> 2017-09-26 Jakub Jelinek <ja...@redhat.com>
>
> PR middle-end/35691
> * tree-ssa-reassoc.c (update_range_test): Dump r->exp each time
> if it is different SSA_NAME.
> (optimize_range_tests_cmp_bitwise): New function.
> (optimize_range_tests): Call it.
>
> * gcc.dg/pr35691-5.c: New test.
> * gcc.dg/pr35691-6.c: New test.
>
> --- gcc/tree-ssa-reassoc.c.jj 2017-09-26 09:35:15.101842092 +0200
> +++ gcc/tree-ssa-reassoc.c 2017-09-26 10:18:07.600993304 +0200
> @@ -2379,7 +2379,16 @@ update_range_test (struct range_entry *r
> r = otherrange + i;
> else
> r = otherrangep[i];
> - fprintf (dump_file, " and %c[", r->in_p ? '+' : '-');
> + if (r->exp
> + && r->exp != range->exp
> + && TREE_CODE (r->exp) == SSA_NAME)
> + {
> + fprintf (dump_file, " and ");
> + print_generic_expr (dump_file, r->exp);
> + }
> + else
> + fprintf (dump_file, " and");
> + fprintf (dump_file, " %c[", r->in_p ? '+' : '-');
> print_generic_expr (dump_file, r->low);
> fprintf (dump_file, ", ");
> print_generic_expr (dump_file, r->high);
> @@ -2880,6 +2889,134 @@ optimize_range_tests_to_bit_test (enum t
> return any_changes;
> }
>
> +/* Optimize x != 0 && y != 0 && z != 0 into (x | y | z) != 0
> + and similarly x != -1 && y != -1 && y != -1 into (x & y & z) != -1. */
> +
> +static bool
> +optimize_range_tests_cmp_bitwise (enum tree_code opcode, int first, int
> length,
> + vec<operand_entry *> *ops,
> + struct range_entry *ranges)
> +{
> + int i;
> + unsigned int b;
> + bool any_changes = false;
> + auto_vec<int, 128> buckets;
> + auto_vec<int, 32> chains;
> + auto_vec<struct range_entry *, 32> candidates;
> +
> + for (i = first; i < length; i++)
> + {
> + if (ranges[i].exp == NULL_TREE
> + || TREE_CODE (ranges[i].exp) != SSA_NAME
> + || !ranges[i].in_p
> + || TYPE_PRECISION (TREE_TYPE (ranges[i].exp)) <= 1
> + || TREE_CODE (TREE_TYPE (ranges[i].exp)) == BOOLEAN_TYPE
> + || ranges[i].low == NULL_TREE
> + || ranges[i].low != ranges[i].high)
> + continue;
> +
> + bool zero_p = integer_zerop (ranges[i].low);
> + if (!zero_p && !integer_all_onesp (ranges[i].low))
> + continue;
> +
> + b = TYPE_PRECISION (TREE_TYPE (ranges[i].exp)) * 2 + !zero_p;
> + if (buckets.length () <= b)
> + buckets.safe_grow_cleared (b + 1);
> + if (chains.length () <= (unsigned) i)
> + chains.safe_grow (i + 1);
> + chains[i] = buckets[b];
> + buckets[b] = i + 1;
> + }
> +
> + FOR_EACH_VEC_ELT (buckets, b, i)
> + if (i && chains[i - 1])
> + {
> + int j, k = i;
> + for (j = chains[i - 1]; j; j = chains[j - 1])
> + {
> + gimple *gk = SSA_NAME_DEF_STMT (ranges[k - 1].exp);
> + gimple *gj = SSA_NAME_DEF_STMT (ranges[j - 1].exp);
> + if (reassoc_stmt_dominates_stmt_p (gk, gj))
> + k = j;
> + }
> + tree type1 = TREE_TYPE (ranges[k - 1].exp);
> + tree type2 = NULL_TREE;
> + bool strict_overflow_p = false;
> + candidates.truncate (0);
> + for (j = i; j; j = chains[j - 1])
> + {
> + tree type = TREE_TYPE (ranges[j - 1].exp);
> + strict_overflow_p |= ranges[j - 1].strict_overflow_p;
> + if (j == k
> + || useless_type_conversion_p (type1, type))
> + ;
> + else if (type2 == NULL_TREE
> + || useless_type_conversion_p (type2, type))
> + {
> + if (type2 == NULL_TREE)
> + type2 = type;
> + candidates.safe_push (&ranges[j - 1]);
> + }
> + }
> + unsigned l = candidates.length ();
> + for (j = i; j; j = chains[j - 1])
> + {
> + tree type = TREE_TYPE (ranges[j - 1].exp);
> + if (j == k)
> + continue;
> + if (useless_type_conversion_p (type1, type))
> + ;
> + else if (type2 == NULL_TREE
> + || useless_type_conversion_p (type2, type))
> + continue;
> + candidates.safe_push (&ranges[j - 1]);
> + }
> + gimple_seq seq = NULL;
> + tree op = NULL_TREE;
> + unsigned int id;
> + struct range_entry *r;
> + candidates.safe_push (&ranges[k - 1]);
> + FOR_EACH_VEC_ELT (candidates, id, r)
> + {
> + gimple *g;
> + if (id == 0)
> + {
> + op = r->exp;
> + continue;
> + }
> + if (id == l)
> + {
> + g = gimple_build_assign (make_ssa_name (type1), NOP_EXPR, op);
> + gimple_seq_add_stmt_without_update (&seq, g);
> + op = gimple_assign_lhs (g);
> + }
> + tree type = TREE_TYPE (r->exp);
> + tree exp = r->exp;
> + if (id >= l && !useless_type_conversion_p (type1, type))
> + {
> + g = gimple_build_assign (make_ssa_name (type1), NOP_EXPR, exp);
> + gimple_seq_add_stmt_without_update (&seq, g);
> + exp = gimple_assign_lhs (g);
> + }
> + g = gimple_build_assign (make_ssa_name (id >= l ? type1 : type2),
> + (b & 1) ? BIT_AND_EXPR : BIT_IOR_EXPR,
> + op, exp);
> + gimple_seq_add_stmt_without_update (&seq, g);
> + op = gimple_assign_lhs (g);
> + }
> + candidates.pop ();
> + if (update_range_test (&ranges[k - 1], NULL, candidates.address (),
> + candidates.length (), opcode, ops, op,
> + seq, true, ranges[k - 1].low,
> + ranges[k - 1].low, strict_overflow_p))
> + any_changes = true;
> + else
> + gimple_seq_discard (seq);
> + }
> +
> + return any_changes;
> +}
> +
> /* Attempt to optimize for signed a and b where b is known to be >= 0:
> a >= 0 && a < b into (unsigned) a < (unsigned) b
> a >= 0 && a <= b into (unsigned) a <= (unsigned) b */
> @@ -3202,6 +3339,8 @@ optimize_range_tests (enum tree_code opc
> if (lshift_cheap_p (optimize_function_for_speed_p (cfun)))
> any_changes |= optimize_range_tests_to_bit_test (opcode, first, length,
> ops, ranges);
> + any_changes |= optimize_range_tests_cmp_bitwise (opcode, first, length,
> + ops, ranges);
> any_changes |= optimize_range_tests_var_bound (opcode, first, length, ops,
> ranges);
>
> --- gcc/testsuite/gcc.dg/pr35691-5.c.jj 2017-09-26 10:47:38.507599980
> +0200
> +++ gcc/testsuite/gcc.dg/pr35691-5.c 2017-09-26 11:33:06.000000000 +0200
> @@ -0,0 +1,125 @@
> +/* PR middle-end/35691 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[xyz]1_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]1_\[0-9]*\\(D\\) \\+\\\[0,
> 0\\\] and \[xyz]1_\[0-9]*\\(D\\) \\+\\\[0, 0\\\]\[\n\r]" 1 "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[ghi]1_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[ghi]1_\[0-9]*\\(D\\) \\+\\\[0,
> 0\\\] and \[ghi]1_\[0-9]*\\(D\\) \\+\\\[0, 0\\\]\[\n\r]" 1 "reassoc1" } } */
> +
> +int
> +f1 (int x1, unsigned int y1, int z1, _Bool d, _Bool e, _Bool f, long long
> g1, unsigned long long h1, long long i1)
> +{
> + int a = x1 == 0;
> + int b = y1 == 0;
> + int c = z1 == 0;
> + int j = g1 == 0;
> + int k = h1 == 0;
> + int l = i1 == 0;
> + return a && d && j && b && e && l && f && c && k;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[xyz]2_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]2_\[0-9]*\\(D\\) \\+\\\[0,
> 0\\\] and \[xyz]2_\[0-9]*\\(D\\) \\+\\\[0, 0\\\]\[\n\r]" 1 "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[ghi]2_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and
> \[ghi]2_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and
> \[ghi]2_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1
> "reassoc1" } } */
> +
> +int
> +f2 (int x2, int y2, unsigned int z2, _Bool d, _Bool e, _Bool f, long long
> g2, unsigned long long h2, long long i2)
> +{
> + int a = x2 == 0;
> + int b = y2 == 0;
> + int c = z2 == 0;
> + int j = g2 == -1LL;
> + int k = h2 == -1ULL;
> + int l = i2 == -1LL;
> + return !a || d || !l || !b || !k || e || f || !c || !j;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[xyz]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and
> \[xyz]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and
> \[xyz]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1
> "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[ghi]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and
> \[ghi]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and
> \[ghi]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1
> "reassoc1" } } */
> +
> +int
> +f3 (unsigned int x3, int y3, int z3, _Bool d, _Bool e, _Bool f, signed char
> g3, unsigned char h3, signed char i3)
> +{
> + int a = x3 == -1U;
> + int b = y3 == -1;
> + int c = z3 == -1;
> + int j = g3 == -1;
> + int k = h3 == (unsigned char) -1U;
> + int l = i3 == -1;
> + return a && d && j && b && k && e && f && c && l;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[xyz]4_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and
> \[xyz]4_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and
> \[xyz]4_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1
> "reassoc1" } } */
> +
> +int
> +f4 (int x4, unsigned int y4, unsigned int z4, _Bool d, _Bool e, _Bool f)
> +{
> + int a = x4 == -1U;
> + int b = y4 == -1U;
> + int c = z4 == -1;
> + return !a || d || !b || e || f || !c;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[xyz]5_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]5_\[0-9]*\\(D\\) \\+\\\[0,
> 0\\\] and \[xyz]5_\[0-9]*\\(D\\) \\+\\\[0, 0\\\]\[\n\r]" 1 "reassoc1" } } */
> +
> +int
> +f5 (int x5, int y5, int z5, _Bool d, _Bool e, _Bool f)
> +{
> + int a = x5 == 0;
> + int b = y5 != 0;
> + int c = z5 != 0;
> + return a && d && !b && e && f && !c;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[xyz]6_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]6_\[0-9]*\\(D\\) \\+\\\[0,
> 0\\\] and \[xyz]6_\[0-9]*\\(D\\) \\+\\\[0, 0\\\]\[\n\r]" 1 "reassoc1" } } */
> +
> +int
> +f6 (unsigned int x6, unsigned int y6, unsigned int z6, _Bool d, _Bool e,
> _Bool f)
> +{
> + int a = x6 == 0;
> + int b = y6 != 0;
> + int c = z6 != 0;
> + return !a || d || b || e || f || c;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[xy]7_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and
> \[xy]7_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1
> "reassoc1" } } */
> +
> +int
> +f7 (int x7, int y7, int z7, _Bool d, _Bool e, _Bool f)
> +{
> + int a = x7 == -1;
> + int b = y7 != -1;
> + int c = z7 == -1;
> + return a && d && !b && e && f && !c;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[xy]8_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and
> \[xy]8_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1
> "reassoc1" } } */
> +
> +int
> +f8 (unsigned int x8, unsigned int y8, unsigned int z8, _Bool d, _Bool e,
> _Bool f)
> +{
> + int a = x8 == -1;
> + int b = y8 != -1;
> + int c = z8 == -1;
> + return !a || d || b || e || f || c;
> +}
> +
> +/* { dg-final { scan-tree-dump-not "Optimizing range tests
> \[xyz]9_\[0-9]*\\(D\\)" "reassoc1" } } */
> +
> +int
> +f9 (int x9, int y9, int z9, _Bool d, _Bool e, _Bool f)
> +{
> + int a = x9 == -1;
> + int b = y9 == -1;
> + int c = z9 == -1;
> + return a || d || b || e || f || c;
> +}
> +
> +/* { dg-final { scan-tree-dump-not "Optimizing range tests
> \[xyz]0_\[0-9]*\\(D\\)" "reassoc1" } } */
> +
> +int
> +f0 (int x0, int y0, int z0, _Bool d, _Bool e, _Bool f)
> +{
> + int a = x0 != 0;
> + int b = y0 != 0;
> + int c = z0 != 0;
> + return a && d && b && e && f && c;
> +}
> --- gcc/testsuite/gcc.dg/pr35691-6.c.jj 2017-09-26 11:26:32.129418103
> +0200
> +++ gcc/testsuite/gcc.dg/pr35691-6.c 2017-09-26 11:25:59.000000000 +0200
> @@ -0,0 +1,72 @@
> +/* PR middle-end/35691 */
> +/* { dg-do run } */
> +/* { dg-options "-O2" } */
> +
> +__attribute__((noinline, noclone)) int
> +foo (int *p, unsigned long long *q)
> +{
> + int p0 = p[0], p10 = p[10], p12 = p[12], p32 = p[32], p77 = p[77], p85 =
> p[85], p86 = p[86], p97 = p[97], p98 = p[98];
> + unsigned long long q0 = q[0], q10 = q[10], q12 = q[12], q32 = q[32], q77 =
> q[77], q85 = q[85], q86 = q[86], q97 = q[97], q98 = q[98];
> + return p0 == 0 && q0 == -1 && p10 == 0 && q10 == -1 && p12 == 0 && q12 ==
> -1
> + && p32 == 0 && q32 == -1 && p77 == 0 && q77 == -1 && p85 == 0 && q85
> == -1
> + && p86 == 0 && q86 == -1 && p97 == 0 && q97 == -1 && p98 == 0 && q98
> == -1;
> +}
> +
> +__attribute__((noinline, noclone)) int
> +bar (int *p, unsigned long long *q)
> +{
> + int p0 = p[0], p10 = p[10], p12 = p[12], p32 = p[32], p77 = p[77], p85 =
> p[85], p86 = p[86], p97 = p[97], p98 = p[98];
> + unsigned long long q0 = q[0], q10 = q[10], q12 = q[12], q32 = q[32], q77 =
> q[77], q85 = q[85], q86 = q[86], q97 = q[97], q98 = q[98];
> + return p0 != 0 | q0 != -1 | p10 != 0 | q10 != -1 | p12 != 0 | q12 != -1
> + | p32 != 0 | q32 != -1 | p77 != 0 | q77 != -1 | p85 != 0 | q85 != -1
> + | p86 != 0 | q86 != -1 | p97 != 0 | q97 != -1 | p98 != 0 | q98 != -1;
> +}
> +
> +int p[100];
> +unsigned long long q[100];
> +
> +int
> +main ()
> +{
> + int i;
> + for (i = 0; i < 100; i++)
> + {
> + p[i] = 0;
> + q[i] = -1;
> + }
> + asm volatile ("" : : "g" (p), "g" (q) : "memory");
> + if (foo (p, q) != 1 || bar (p, q) != 0)
> + __builtin_abort ();
> + for (i = 0; i < 100; i++)
> + {
> + int f1, b1, f2, b2;
> + p[i] = 1;
> + f1 = foo (p, q);
> + b1 = bar (p, q);
> + p[i] = 0;
> + q[i] = 0;
> + f2 = foo (p, q);
> + b2 = bar (p, q);
> + q[i] = -1;
> + switch (i)
> + {
> + case 0:
> + case 10:
> + case 12:
> + case 32:
> + case 77:
> + case 85:
> + case 86:
> + case 97:
> + case 98:
> + if (f1 != 0 || b1 != 1 || f2 != 0 || b2 != 1)
> + __builtin_abort ();
> + break;
> + default:
> + if (f1 != 1 || b1 != 0 || f2 != 1 || b2 != 0)
> + __builtin_abort ();
> + break;
> + }
> + }
> + return 0;
> +}
>
> Jakub
>
>
--
Richard Biener <rguent...@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB
21284 (AG Nuernberg)
