From caab37632257b7b002da791d6372ab9136e0d54f Mon Sep 17 00:00:00 2001 From: Jakub Jelinek Date: Tue, 26 Sep 2017 15:58:11 +0200 Subject: [PATCH] re PR middle-end/35691 (Missed (a == 0) && (b == 0) into (a|(typeof(a)(b)) == 0 when the types don't match) 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. From-SVN: r253201 --- gcc/ChangeLog | 8 ++ gcc/testsuite/ChangeLog | 6 ++ gcc/testsuite/gcc.dg/pr35691-5.c | 125 +++++++++++++++++++++++++++ gcc/testsuite/gcc.dg/pr35691-6.c | 72 ++++++++++++++++ gcc/tree-ssa-reassoc.c | 141 ++++++++++++++++++++++++++++++- 5 files changed, 351 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/pr35691-5.c create mode 100644 gcc/testsuite/gcc.dg/pr35691-6.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 73823fc5e2b..71d8a309f62 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2017-09-26 Jakub Jelinek + + 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. + 2017-09-26 Richard Biener PR tree-optimization/82321 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 53927551619..77ac3d1fa0f 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2017-09-26 Jakub Jelinek + + PR middle-end/35691 + * gcc.dg/pr35691-5.c: New test. + * gcc.dg/pr35691-6.c: New test. + 2017-09-26 Richard Biener PR tree-optimization/82321 diff --git a/gcc/testsuite/gcc.dg/pr35691-5.c b/gcc/testsuite/gcc.dg/pr35691-5.c new file mode 100644 index 00000000000..1cde0283b5d --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr35691-5.c @@ -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; +} diff --git a/gcc/testsuite/gcc.dg/pr35691-6.c b/gcc/testsuite/gcc.dg/pr35691-6.c new file mode 100644 index 00000000000..b45bbb8a2ad --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr35691-6.c @@ -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; +} diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index 2fb6aef51d7..b2d0f57e644 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -2379,7 +2379,16 @@ update_range_test (struct range_entry *range, struct range_entry *otherrange, 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 tree_code opcode, int first, int length, 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 *ops, + struct range_entry *ranges) +{ + int i; + unsigned int b; + bool any_changes = false; + auto_vec buckets; + auto_vec chains; + auto_vec 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 opcode, 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); -- 2.30.2