[gcc r11-5836] PR tree-optimization/96344

[gcc r11-5836] PR tree-optimization/96344

[Eric Botcazou]

https://gcc.gnu.org/g:ffd961fc053419bc1eb37792c18ec98e7c3bc364

commit r11-5836-gffd961fc053419bc1eb37792c18ec98e7c3bc364
Author: Eric Botcazou <ebotcazou@adacore.com>
Date:   Tue Dec 8 08:57:46 2020 +0100

    PR tree-optimization/96344
    
    The very recent addition of the if_to_switch pass has partially disabled
    the optimization added back in June to optimize_range_tests_to_bit_test,
    as witnessed by the 3 new failures in the gnat.dg testsuite.  It turns out
    that both tree-ssa-reassoc.c and tree-switch-conversion.c can turn things
    into bit tests so the optimization is added to bit_test_cluster::emit too.
    
    The patch also contains a secondary optimization, whereby the full bit-test
    sequence is sent to the folder before being gimplified in case there is only
    one test, so that the optimal sequence (bt + jc on x86) can be emitted like
    with optimize_range_tests_to_bit_test.
    
    gcc/ChangeLog:
            PR tree-optimization/96344
            * tree-switch-conversion.c (bit_test_cluster::emit): Compute the
            range only if an entry test is necessary.  Merge the entry test in
            the bit test when possible.  Use PREC local variable consistently.
            When there is only one test, do a single gimplification at the end.

Diff:
---
 gcc/tree-switch-conversion.c | 60 +++++++++++++++++++++++++++++++++-----------
 1 file changed, 46 insertions(+), 14 deletions(-)

diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index a87a2a3cd15..989bd7710d1 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -1511,7 +1511,6 @@ bit_test_cluster::emit (tree index_expr, tree index_type,
 
   tree minval = get_low ();
   tree maxval = get_high ();
-  tree range = int_const_binop (MINUS_EXPR, maxval, minval);
   unsigned HOST_WIDE_INT bt_range = get_range (minval, maxval);
 
   /* Go through all case labels, and collect the case labels, profile
@@ -1550,11 +1549,38 @@ bit_test_cluster::emit (tree index_expr, tree index_type,
 
   qsort (test, count, sizeof (*test), case_bit_test::cmp);
 
+  /* If every possible relative value of the index expression is a valid shift
+     amount, then we can merge the entry test in the bit test.  */
+  wide_int min, max;
+  bool entry_test_needed;
+  if (TREE_CODE (index_expr) == SSA_NAME
+      && get_range_info (index_expr, &min, &max) == VR_RANGE
+      && wi::leu_p (max - min, prec - 1))
+    {
+      wide_int iminval = wi::to_wide (minval);
+      tree minval_type = TREE_TYPE (minval);
+      if (wi::lt_p (min, iminval, TYPE_SIGN (minval_type)))
+	{
+	  minval = wide_int_to_tree (minval_type, min);
+	  for (i = 0; i < count; i++)
+	    test[i].mask = wi::lshift (test[i].mask, iminval - min);
+	}
+      else if (wi::gt_p (min, iminval, TYPE_SIGN (minval_type)))
+	{
+	  minval = wide_int_to_tree (minval_type, min);
+	  for (i = 0; i < count; i++)
+	    test[i].mask = wi::lrshift (test[i].mask, min - iminval);
+	}
+      maxval = wide_int_to_tree (minval_type, max);
+      entry_test_needed = false;
+    }
+  else
+    entry_test_needed = true;
+
   /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
      the minval subtractions, but it might make the mask constants more
      expensive.  So, compare the costs.  */
-  if (compare_tree_int (minval, 0) > 0
-      && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
+  if (compare_tree_int (minval, 0) > 0 && compare_tree_int (maxval, prec) < 0)
     {
       int cost_diff;
       HOST_WIDE_INT m = tree_to_uhwi (minval);
@@ -1577,7 +1603,6 @@ bit_test_cluster::emit (tree index_expr, tree index_type,
 	  for (i = 0; i < count; i++)
 	    test[i].mask = wi::lshift (test[i].mask, m);
 	  minval = build_zero_cst (TREE_TYPE (minval));
-	  range = maxval;
 	}
     }
 
@@ -1593,8 +1618,9 @@ bit_test_cluster::emit (tree index_expr, tree index_type,
 				  /*simple=*/true, NULL_TREE,
 				  /*before=*/true, GSI_SAME_STMT);
 
-  if (m_handles_entire_switch)
+  if (m_handles_entire_switch && entry_test_needed)
     {
+      tree range = int_const_binop (MINUS_EXPR, maxval, minval);
       /* if (idx > range) goto default */
       range
 	= force_gimple_operand_gsi (&gsi,
@@ -1608,16 +1634,22 @@ bit_test_cluster::emit (tree index_expr, tree index_type,
       gsi = gsi_last_bb (new_bb);
     }
 
-  /* csui = (1 << (word_mode) idx) */
-  csui = make_ssa_name (word_type_node);
   tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
 		     fold_convert (word_type_node, idx));
-  tmp = force_gimple_operand_gsi (&gsi, tmp,
-				  /*simple=*/false, NULL_TREE,
-				  /*before=*/true, GSI_SAME_STMT);
-  shift_stmt = gimple_build_assign (csui, tmp);
-  gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
-  update_stmt (shift_stmt);
+
+  /* csui = (1 << (word_mode) idx) */
+  if (count > 1)
+    {
+      csui = make_ssa_name (word_type_node);
+      tmp = force_gimple_operand_gsi (&gsi, tmp,
+				     /*simple=*/false, NULL_TREE,
+				     /*before=*/true, GSI_SAME_STMT);
+      shift_stmt = gimple_build_assign (csui, tmp);
+      gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
+      update_stmt (shift_stmt);
+    }
+  else
+    csui = tmp;
 
   profile_probability prob = profile_probability::always ();
 
@@ -1630,10 +1662,10 @@ bit_test_cluster::emit (tree index_expr, tree index_type,
       bt_range -= test[k].bits;
       tmp = wide_int_to_tree (word_type_node, test[k].mask);
       tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
+      tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
       tmp = force_gimple_operand_gsi (&gsi, tmp,
 				      /*simple=*/true, NULL_TREE,
 				      /*before=*/true, GSI_SAME_STMT);
-      tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
       basic_block new_bb
 	= hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb, prob);
       gsi = gsi_last_bb (new_bb);