On 10/23/18 12:20 PM, Richard Biener wrote:
> On Tue, Oct 23, 2018 at 10:37 AM Martin Liška <mli...@suse.cz> wrote:
>>
>> On 10/22/18 4:25 PM, Jakub Jelinek wrote:
>>> On Mon, Oct 22, 2018 at 04:08:53PM +0200, Martin Liška wrote:
>>>> Very valid question. I hope as long as I calculate the linear function
>>>> values in wide_int (get via wi::to_wide (switch_element)), then it should
>>>> overflow in the same way as original tree type arithmetic. I have a
>>>> test-case with
>>>> overflow: gcc/testsuite/gcc.dg/tree-ssa/pr84436-4.c.
>>>>
>>>> Do you have any {over,under)flowing test-cases that I should add to
>>>> test-suite?
>>>
>>> I'm worried that the calculation you emit into the code could invoke UB at
>>> runtime, even if there was no UB in the original code, and later GCC passes
>>> would optimize with the assumption that UB doesn't occur.
>>> E.g. if the multiplication overflows for one or more of the valid values in
>>> the switch and then the addition adds a negative value so that the end
>>> result is actually representable.
>>
>> In order to address that I verified that neither of (a * x) and (a * x) + b
>> {over,under}flow
>> in case of TYPE_OVERFLOW_UNDEFINED (type) is true.
>>
>> Hope it's way how to properly make it safe?
>
> Hmm, if the default: case is unreachable maybe. But I guess Jakub was
> suggesting to do the linear function compute in an unsigned type?
>
> + /* Let's try to find any linear function a.x + y that can apply to
>
> a * x?
Yep.
>
> + given values. 'a' can be calculated as follows:
>
> + tree t = TREE_TYPE (m_index_expr);
>
> so unsigned_type_for (TREE_TYPE ...)
>
> + tree tmp = make_ssa_name (t);
> + tree value = fold_build2_loc (loc, MULT_EXPR, t,
> + wide_int_to_tree (t, coeff_a),
> + m_index_expr);
> +
>
> + gsi_insert_before (&gsi, gimple_build_assign (tmp, value),
> GSI_SAME_STMT);
> + value = fold_build2_loc (loc, PLUS_EXPR, t,
> + tmp, wide_int_to_tree (t, coeff_b));
> + tree tmp2 = make_ssa_name (t);
> + gsi_insert_before (&gsi, gimple_build_assign (tmp2, value),
> + GSI_SAME_STMT);
> + load = gimple_build_assign (name, NOP_EXPR, fold_convert (t, tmp2));
>
> before the unsigned_type_for that NOP_EXPR would be always redundant.
>
> Please also use
>
> gimple_seq seq = NULL;
> tree tmp = gimple_build (&seq, MULT_EXPR, type, ...);
> tree tmp2 = gimple_build (&seq, PLUS_EXPR, type, ...);
> tree tmp3 = gimple_convert (&seq, TREE_TYPE (m_index_expr), tmp2);
> gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
> load = gimple_build_assign (name, tmp3);
>
> not sure why you need the extra assignment at the end, not enough
> context in the patch.
Thanks for the hint. I did that and tested the patch. It looks fine.
Martin
>
> Richard.
>
>
>> Martin
>>
>>>
>>> Jakub
>>>
>>
>From 81b29b5ba12f043d091b81805116793af4a98442 Mon Sep 17 00:00:00 2001
From: marxin <mli...@suse.cz>
Date: Thu, 11 Oct 2018 12:37:37 +0200
Subject: [PATCH] Switch conversion: support any ax + b transformation (PR
tree-optimization/84436).
gcc/ChangeLog:
2018-10-11 Martin Liska <mli...@suse.cz>
PR tree-optimization/84436
* tree-switch-conversion.c (switch_conversion::contains_same_values_p):
Remove.
(switch_conversion::contains_linear_function_p): New.
(switch_conversion::build_one_array): Support linear
transformation on input.
* tree-switch-conversion.h (struct switch_conversion): Add
contains_linear_function_p declaration.
gcc/testsuite/ChangeLog:
2018-10-11 Martin Liska <mli...@suse.cz>
PR tree-optimization/84436
* gcc.dg/tree-ssa/pr84436-1.c: New test.
* gcc.dg/tree-ssa/pr84436-2.c: New test.
* gcc.dg/tree-ssa/pr84436-3.c: New test.
* gcc.dg/tree-ssa/pr84436-4.c: New test.
* gcc.dg/tree-ssa/pr84436-5.c: New test.
---
gcc/testsuite/gcc.dg/tree-ssa/pr84436-1.c | 36 ++++++++++
gcc/testsuite/gcc.dg/tree-ssa/pr84436-2.c | 67 +++++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/pr84436-3.c | 24 +++++++
gcc/testsuite/gcc.dg/tree-ssa/pr84436-4.c | 38 ++++++++++
gcc/testsuite/gcc.dg/tree-ssa/pr84436-5.c | 38 ++++++++++
gcc/tree-switch-conversion.c | 87 +++++++++++++++++++----
gcc/tree-switch-conversion.h | 10 +--
7 files changed, 281 insertions(+), 19 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr84436-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr84436-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr84436-3.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr84436-4.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr84436-5.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr84436-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr84436-1.c
new file mode 100644
index 00000000000..a045b44c2b9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr84436-1.c
@@ -0,0 +1,36 @@
+/* PR tree-optimization/84436 */
+/* { dg-options "-O2 -fdump-tree-switchconv -fdump-tree-optimized" } */
+/* { dg-do run } */
+
+int
+__attribute__ ((noipa))
+foo (int how)
+{
+ switch (how) {
+ case 2: how = 205; break; /* how = 100 * index + 5 */
+ case 3: how = 305; break;
+ case 4: how = 405; break;
+ case 5: how = 505; break;
+ case 6: how = 605; break;
+ }
+ return how;
+}
+
+int main()
+{
+ if (foo (2) != 205)
+ __builtin_abort ();
+
+ if (foo (6) != 605)
+ __builtin_abort ();
+
+ if (foo (123) != 123)
+ __builtin_abort ();
+
+ return 0;
+}
+
+
+/* { dg-final { scan-tree-dump-times "100 \\*" 1 "switchconv" } } */
+/* { dg-final { scan-tree-dump-times ".* \\+ 5" 1 "switchconv" } } */
+/* { dg-final { scan-tree-dump-not "switch" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr84436-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr84436-2.c
new file mode 100644
index 00000000000..c34027a08b9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr84436-2.c
@@ -0,0 +1,67 @@
+/* PR tree-optimization/84436 */
+/* { dg-options "-O2 -fdump-tree-switchconv -fdump-tree-optimized" } */
+
+char
+lowerit(char a)
+{
+ switch (a)
+ {
+ default:
+ return a;
+ case 'A':
+ return 'a';
+ case 'B':
+ return 'b';
+ case 'C':
+ return 'c';
+ case 'D':
+ return 'd';
+ case 'E':
+ return 'e';
+ case 'F':
+ return 'f';
+ case 'G':
+ return 'g';
+ case 'H':
+ return 'h';
+ case 'I':
+ return 'i';
+ case 'J':
+ return 'j';
+ case 'K':
+ return 'k';
+ case 'L':
+ return 'l';
+ case 'M':
+ return 'm';
+ case 'N':
+ return 'n';
+ case 'O':
+ return 'o';
+ case 'P':
+ return 'p';
+ case 'Q':
+ return 'q';
+ case 'R':
+ return 'r';
+ case 'S':
+ return 's';
+ case 'T':
+ return 't';
+ case 'U':
+ return 'u';
+ case 'V':
+ return 'v';
+ case 'W':
+ return 'w';
+ case 'X':
+ return 'x';
+ case 'Y':
+ return 'y';
+ case 'Z':
+ return 'z';
+ }
+}
+
+/* { dg-final { scan-tree-dump-times "a_.*\\+ 32" 1 "switchconv" } } */
+/* { dg-final { scan-tree-dump-not "switch" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr84436-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr84436-3.c
new file mode 100644
index 00000000000..87937f30ab1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr84436-3.c
@@ -0,0 +1,24 @@
+/* PR tree-optimization/84436 */
+/* { dg-options "-O2 -fdump-tree-switchconv -fdump-tree-optimized" } */
+
+enum a { b, c, d };
+int e;
+void h(enum a);
+
+void f() {
+ enum a g;
+ switch (e) {
+ case '1':
+ g = b;
+ break;
+ case '2':
+ g = c;
+ break;
+ case '3':
+ g = d;
+ }
+ h(g);
+}
+
+/* { dg-final { scan-tree-dump-times ".* \\+ 4294967247" 1 "switchconv" } } */
+/* { dg-final { scan-tree-dump-not "switch" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr84436-4.c b/gcc/testsuite/gcc.dg/tree-ssa/pr84436-4.c
new file mode 100644
index 00000000000..979250edd1c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr84436-4.c
@@ -0,0 +1,38 @@
+/* PR tree-optimization/84436 */
+/* { dg-options "-O2 -fdump-tree-switchconv -fdump-tree-optimized" } */
+/* { dg-do run } */
+
+enum E
+{
+ A, B, C,
+};
+
+int
+__attribute__ ((noipa))
+foo(enum E e)
+{
+ switch (e)
+ {
+ case A: return 0;
+ case B: return 1;
+ case C: return 2;
+ }
+
+ return -1;
+}
+
+int main()
+{
+ if (foo (A) != 0)
+ __builtin_abort ();
+
+ if (foo (B) != 1)
+ __builtin_abort ();
+
+ if (foo (C) != 2)
+ __builtin_abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "switch" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr84436-5.c b/gcc/testsuite/gcc.dg/tree-ssa/pr84436-5.c
new file mode 100644
index 00000000000..3f9e2245e84
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr84436-5.c
@@ -0,0 +1,38 @@
+/* PR tree-optimization/84436 */
+/* { dg-options "-O2 -fdump-tree-switchconv -fdump-tree-optimized" } */
+/* { dg-do run } */
+
+char
+__attribute__ ((noipa))
+foo (char how)
+{
+ switch (how) {
+ case -4: how = 96; break;
+ case -3: how = -120; break;
+ case -2: how = -80; break;
+ case -1: how = -40; break;
+ case 0: how = 0; break;
+ case 1: how = 40; break;
+ }
+ return how;
+}
+
+int main()
+{
+ if (foo (-4) != 96)
+ __builtin_abort ();
+
+ if (foo (-3) != -120)
+ __builtin_abort ();
+
+ if (foo (0) != 0)
+ __builtin_abort ();
+
+ if (foo (123) != 123)
+ __builtin_abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "40 *\\*" 1 "switchconv" } } */
+/* { dg-final { scan-tree-dump-not "switch" "optimized" } } */
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index ac2aa585257..e65552edea5 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -44,6 +44,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
#include "gimplify.h"
#include "gimple-iterator.h"
#include "gimplify-me.h"
+#include "gimple-fold.h"
#include "tree-cfg.h"
#include "cfgloop.h"
#include "alloc-pool.h"
@@ -439,25 +440,63 @@ switch_conversion::build_constructors ()
}
}
-/* If all values in the constructor vector are the same, return the value.
- Otherwise return NULL_TREE. Not supposed to be called for empty
- vectors. */
+/* If all values in the constructor vector are products of a linear function
+ a * x + b, then return true. When true, COEFF_A and COEFF_B and
+ coefficients of the linear function. Note that equal values are special
+ case of a linear function with a and b equal to zero. */
-tree
-switch_conversion::contains_same_values_p (vec<constructor_elt, va_gc> *vec)
+bool
+switch_conversion::contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
+ wide_int *coeff_a,
+ wide_int *coeff_b)
{
unsigned int i;
- tree prev = NULL_TREE;
constructor_elt *elt;
+ gcc_assert (vec->length () >= 2);
+
+ /* Let's try to find any linear function a * x + y that can apply to
+ given values. 'a' can be calculated as follows:
+
+ a = (y2 - y1) / (x2 - x1) where x2 - x1 = 1 (consecutive case indices)
+ a = y2 - y1
+
+ and
+
+ b = y2 - a * x2
+
+ */
+
+ tree elt0 = (*vec)[0].value;
+ tree elt1 = (*vec)[1].value;
+
+ if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST)
+ return false;
+
+ wide_int range_min = wi::to_wide (fold_convert (TREE_TYPE (elt0),
+ m_range_min));
+ wide_int y1 = wi::to_wide (elt0);
+ wide_int y2 = wi::to_wide (elt1);
+ wide_int a = y2 - y1;
+ wide_int b = y2 - a * (range_min + 1);
+
+ /* Verify that all values fulfill the linear function. */
FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
{
- if (!prev)
- prev = elt->value;
- else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
- return NULL_TREE;
+ if (TREE_CODE (elt->value) != INTEGER_CST)
+ return false;
+
+ wide_int value = wi::to_wide (elt->value);
+ if (a * range_min + b != value)
+ return false;
+
+ ++range_min;
}
- return prev;
+
+ *coeff_a = a;
+ *coeff_b = b;
+
+ return true;
}
/* Return type which should be used for array elements, either TYPE's
@@ -551,7 +590,7 @@ void
switch_conversion::build_one_array (int num, tree arr_index_type,
gphi *phi, tree tidx)
{
- tree name, cst;
+ tree name;
gimple *load;
gimple_stmt_iterator gsi = gsi_for_stmt (m_switch);
location_t loc = gimple_location (m_switch);
@@ -561,9 +600,27 @@ switch_conversion::build_one_array (int num, tree arr_index_type,
name = copy_ssa_name (PHI_RESULT (phi));
m_target_inbound_names[num] = name;
- cst = contains_same_values_p (m_constructors[num]);
- if (cst)
- load = gimple_build_assign (name, cst);
+ wide_int coeff_a, coeff_b;
+ bool linear_p = contains_linear_function_p (m_constructors[num], &coeff_a,
+ &coeff_b);
+ if (linear_p)
+ {
+ if (dump_file && coeff_a.to_uhwi () > 0)
+ fprintf (dump_file, "Linear transformation with A = %" PRId64
+ " and B = %" PRId64 "\n", coeff_a.to_shwi (),
+ coeff_b.to_shwi ());
+
+ tree t = unsigned_type_for (TREE_TYPE (m_index_expr));
+ gimple_seq seq = NULL;
+ tree tmp = gimple_convert (&seq, t, m_index_expr);
+ tree tmp2 = gimple_build (&seq, MULT_EXPR, t,
+ wide_int_to_tree (t, coeff_a), tmp);
+ tree tmp3 = gimple_build (&seq, PLUS_EXPR, t, tmp2,
+ wide_int_to_tree (t, coeff_b));
+ tree tmp4 = gimple_convert (&seq, TREE_TYPE (name), tmp3);
+ gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
+ load = gimple_build_assign (name, tmp4);
+ }
else
{
tree array_type, ctor, decl, value_type, fetch, default_type;
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index 37ed2193724..ceee75017d9 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -733,10 +733,12 @@ struct switch_conversion
order of phi nodes. */
void build_constructors ();
- /* If all values in the constructor vector are the same, return the value.
- Otherwise return NULL_TREE. Not supposed to be called for empty
- vectors. */
- tree contains_same_values_p (vec<constructor_elt, va_gc> *vec);
+ /* If all values in the constructor vector are products of a linear function
+ a * x + b, then return true. When true, COEFF_A and COEFF_B and
+ coefficients of the linear function. Note that equal values are special
+ case of a linear function with a and b equal to zero. */
+ bool contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
+ wide_int *coeff_a, wide_int *coeff_b);
/* Return type which should be used for array elements, either TYPE's
main variant or, for integral types, some smaller integral type
--
2.19.0
