Take into account range info to optimize range tests into bit tests

The patch is aimed at addressing the following two issues:

  1. In order to protect the shift operation from undefinedness, the
new bit test is guarded with a new test, but this new test uses the
range of the bit test values, not that of the shift operation so,
if the input is in the range of the shift operation but not of the
bit test values, then the subsequent VRP pass cannot eliminate the
new test.  Moreover changing the new test to use the range of the
shift operation, instead of that of the bit test values, in the
general case would pessimize the cases which are in between.

  2. If the new test can be eliminated, then it becomes profitable
to do the optimization into a bit test for one fewer comparison in
the source code.

Therefore the patch changes optimize_range_tests_to_bit_test to use
the range info of the input in order to eliminate the new test.

gcc/ChangeLog:
	* tree-ssa-reassoc.c (dump_range_entry): New function.
	(debug_range_entry): New debug function.
	(update_range_test): Invoke dump_range_entry for dumping.
	(optimize_range_tests_to_bit_test): Merge the entry test in the
	bit test when possible and lower the profitability threshold.

gcc/ada/ChangeLog:
	* exp_ch4.adb (Expand_Set_Membership): Expand the membership test
	using left associativity instead of right associativity.

gcc/testsuite/ChangeLog:
	* gnat.dg/opt86_pkg.ads: New helper.
	* gnat.dg/opt86a.adb: New test.
	* gnat.dg/opt86b.adb: Likewise.
	* gnat.dg/opt86c.adb: Likewise.

1 files changed, 86 insertions, 30 deletions

diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 2e67987..d06b693 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -2416,6 +2416,32 @@ struct range_entry
   unsigned int idx, next;
 };
 
+void dump_range_entry (FILE *file, struct range_entry *r);
+void debug_range_entry (struct range_entry *r);
+
+/* Dump the range entry R to FILE, skipping its expression if SKIP_EXP.  */
+
+void
+dump_range_entry (FILE *file, struct range_entry *r, bool skip_exp)
+{
+  if (!skip_exp)
+    print_generic_expr (file, r->exp);
+  fprintf (file, " %c[", r->in_p ? '+' : '-');
+  print_generic_expr (file, r->low);
+  fputs (", ", file);
+  print_generic_expr (file, r->high);
+  fputc (']', file);
+}
+
+/* Dump the range entry R to STDERR.  */
+
+DEBUG_FUNCTION void
+debug_range_entry (struct range_entry *r)
+{
+  dump_range_entry (stderr, r, false);
+  fputc ('\n', stderr);
+}
+
 /* This is similar to make_range in fold-const.c, but on top of
    GIMPLE instead of trees.  If EXP is non-NULL, it should be
    an SSA_NAME and STMT argument is ignored, otherwise STMT
@@ -2730,12 +2756,7 @@ update_range_test (struct range_entry *range, struct range_entry *otherrange,
     {
       struct range_entry *r;
       fprintf (dump_file, "Optimizing range tests ");
-      print_generic_expr (dump_file, range->exp);
-      fprintf (dump_file, " %c[", range->in_p ? '+' : '-');
-      print_generic_expr (dump_file, range->low);
-      fprintf (dump_file, ", ");
-      print_generic_expr (dump_file, range->high);
-      fprintf (dump_file, "]");
+      dump_range_entry (dump_file, range, false);
       for (i = 0; i < count; i++)
 	{
 	  if (otherrange)
@@ -2747,15 +2768,13 @@ update_range_test (struct range_entry *range, struct range_entry *otherrange,
 	      && TREE_CODE (r->exp) == SSA_NAME)
 	    {
 	      fprintf (dump_file, " and ");
-	      print_generic_expr (dump_file, r->exp);
+	      dump_range_entry (dump_file, r, false);
 	    }
 	  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);
-	  fprintf (dump_file, "]");
+	    {
+	      fprintf (dump_file, " and");
+	      dump_range_entry (dump_file, r, true);
+	    }
 	}
       fprintf (dump_file, "\n into ");
       print_generic_expr (dump_file, tem);
@@ -3121,7 +3140,7 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length,
   int prec = GET_MODE_BITSIZE (word_mode);
   auto_vec<struct range_entry *, 64> candidates;
 
-  for (i = first; i < length - 2; i++)
+  for (i = first; i < length - 1; i++)
     {
       tree lowi, highi, lowj, highj, type;
 
@@ -3184,8 +3203,32 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length,
 	  candidates.safe_push (&ranges[j]);
 	}
 
-      /* If we need otherwise 3 or more comparisons, use a bit test.  */
-      if (candidates.length () >= 2)
+      /* If every possible relative value of the expression is a valid shift
+	 amount, then we can merge the entry test in the bit test.  In this
+	 case, if we would need otherwise 2 or more comparisons, then use
+	 the bit test; in the other cases, the threshold is 3 comparisons.  */
+      wide_int min, max;
+      bool entry_test_needed;
+      if (TREE_CODE (exp) == SSA_NAME
+	  && get_range_info (exp, &min, &max) == VR_RANGE
+	  && wi::leu_p (max - min, prec - 1))
+	{
+	  wide_int ilowi = wi::to_wide (lowi);
+	  if (wi::lt_p (min, ilowi, TYPE_SIGN (TREE_TYPE (lowi))))
+	    {
+	      lowi = wide_int_to_tree (TREE_TYPE (lowi), min);
+	      mask = wi::lshift (mask, ilowi - min);
+	    }
+	  else if (wi::gt_p (min, ilowi, TYPE_SIGN (TREE_TYPE (lowi))))
+	    {
+	      lowi = wide_int_to_tree (TREE_TYPE (lowi), min);
+	      mask = wi::lrshift (mask, min - ilowi);
+	    }
+	  entry_test_needed = false;
+	}
+      else
+	entry_test_needed = true;
+      if (candidates.length () >= (entry_test_needed ? 2 : 1))
 	{
 	  tree high = wide_int_to_tree (TREE_TYPE (lowi),
 					wi::to_widest (lowi)
@@ -3224,10 +3267,16 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length,
 		}
 	    }
 
-	  tree tem = build_range_check (loc, optype, unshare_expr (exp),
-					false, lowi, high);
-	  if (tem == NULL_TREE || is_gimple_val (tem))
-	    continue;
+	  tree tem;
+	  if (entry_test_needed)
+	    {
+	      tem = build_range_check (loc, optype, unshare_expr (exp),
+				       false, lowi, high);
+	      if (tem == NULL_TREE || is_gimple_val (tem))
+		continue;
+	    }
+	  else
+	    tem = NULL_TREE;
 	  tree etype = unsigned_type_for (TREE_TYPE (exp));
 	  exp = fold_build2_loc (loc, MINUS_EXPR, etype,
 				 fold_convert_loc (loc, etype, exp),
@@ -3248,27 +3297,34 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length,
 	     split when it is running.  So, temporarily emit a code
 	     with BIT_IOR_EXPR instead of &&, and fix it up in
 	     branch_fixup.  */
-	  gimple_seq seq;
-	  tem = force_gimple_operand (tem, &seq, true, NULL_TREE);
-	  gcc_assert (TREE_CODE (tem) == SSA_NAME);
-	  gimple_set_visited (SSA_NAME_DEF_STMT (tem), true);
+	  gimple_seq seq = NULL;
+	  if (tem)
+	    {
+	      tem = force_gimple_operand (tem, &seq, true, NULL_TREE);
+	      gcc_assert (TREE_CODE (tem) == SSA_NAME);
+	      gimple_set_visited (SSA_NAME_DEF_STMT (tem), true);
+	    }
 	  gimple_seq seq2;
 	  exp = force_gimple_operand (exp, &seq2, true, NULL_TREE);
 	  gimple_seq_add_seq_without_update (&seq, seq2);
 	  gcc_assert (TREE_CODE (exp) == SSA_NAME);
 	  gimple_set_visited (SSA_NAME_DEF_STMT (exp), true);
-	  gimple *g = gimple_build_assign (make_ssa_name (optype),
-					   BIT_IOR_EXPR, tem, exp);
-	  gimple_set_location (g, loc);
-	  gimple_seq_add_stmt_without_update (&seq, g);
-	  exp = gimple_assign_lhs (g);
+	  if (tem)
+	    {
+	      gimple *g = gimple_build_assign (make_ssa_name (optype),
+					       BIT_IOR_EXPR, tem, exp);
+	      gimple_set_location (g, loc);
+	      gimple_seq_add_stmt_without_update (&seq, g);
+	      exp = gimple_assign_lhs (g);
+	    }
 	  tree val = build_zero_cst (optype);
 	  if (update_range_test (&ranges[i], NULL, candidates.address (),
 				 candidates.length (), opcode, ops, exp,
 				 seq, false, val, val, strict_overflow_p))
 	    {
 	      any_changes = true;
-	      reassoc_branch_fixups.safe_push (tem);
+	      if (tem)
+		reassoc_branch_fixups.safe_push (tem);
 	    }
 	  else
 	    gimple_seq_discard (seq);