Switch conversion: support any ax + b transformation (PR tree-optimization/84436).

2018-10-24  Martin Liska  <mliska@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.
2018-10-24  Martin Liska  <mliska@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.

From-SVN: r265463

1 files changed, 72 insertions, 15 deletions

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;