Re: [PATCH] Optimize a >= 0 && a < b if VR info says b >= 0 (PR tree-optimization/77664)

2016-10-07 Thread Richard Biener 
On Thu, 6 Oct 2016, Jakub Jelinek wrote:

> Hi!
> 
> For signed a, if we see a >= 0 && a < b and from VR know that b >= 0,
> we can optimize those 2 comparisons into one unsigned -
> (unsigned) a < (unsigned) b.  Similarly for a < 0 || a > b (and also
> for a <= b in the first and a >= b in the second).
> 
> The patch implements it in the reassoc optimize_range_tests optimization,
> so that it can handle even comparisons that aren't adjacent in the && or ||
> or & or | conditions, and can handle the conditions across multiple bbs as
> well.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Ok.

Thanks,
Richard.

> 2016-10-06  Jakub Jelinek  
> 
>   PR tree-optimization/77664
>   * tree-ssa-reassoc.c (update_range_test): Also clear low and high
>   for the other ranges.
>   (optimize_range_tests_diff): Fix up formatting.
>   (optimize_range_tests_var_bound): New function.
>   (optimize_range_tests): Use it.
> 
>   * gcc.dg/tree-ssa/pr77664.c: New test.
>   * gcc.dg/pr77664.c: New test.
> 
> --- gcc/tree-ssa-reassoc.c.jj 2016-10-05 17:01:28.724673717 +0200
> +++ gcc/tree-ssa-reassoc.c2016-10-06 13:34:08.872512318 +0200
> @@ -2428,6 +2428,8 @@ update_range_test (struct range_entry *r
>else
>   oe->op = error_mark_node;
>range->exp = NULL_TREE;
> +  range->low = NULL_TREE;
> +  range->high = NULL_TREE;
>  }
>return true;
>  }
> @@ -2485,10 +2487,10 @@ optimize_range_tests_xor (enum tree_code
> ((X - 43U) & ~(75U - 43U)) <= 3U.  */
>  static bool
>  optimize_range_tests_diff (enum tree_code opcode, tree type,
> - tree lowi, tree lowj, tree highi, tree highj,
> - vec *ops,
> - struct range_entry *rangei,
> - struct range_entry *rangej)
> +tree lowi, tree lowj, tree highi, tree highj,
> +vec *ops,
> +struct range_entry *rangei,
> +struct range_entry *rangej)
>  {
>tree tem1, tem2, mask;
>/* Check highi - lowi == highj - lowj.  */
> @@ -2829,6 +2831,197 @@ optimize_range_tests_to_bit_test (enum t
>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  */
> +
> +static bool
> +optimize_range_tests_var_bound (enum tree_code opcode, int first, int length,
> + vec *ops,
> + struct range_entry *ranges)
> +{
> +  int i;
> +  bool any_changes = false;
> +  hash_map *map = NULL;
> +
> +  for (i = first; i < length; i++)
> +{
> +  if (ranges[i].exp == NULL_TREE || !ranges[i].in_p)
> + continue;
> +
> +  tree type = TREE_TYPE (ranges[i].exp);
> +  if (!INTEGRAL_TYPE_P (type)
> +   || TYPE_UNSIGNED (type)
> +   || ranges[i].low == NULL_TREE
> +   || !integer_zerop (ranges[i].low)
> +   || ranges[i].high != NULL_TREE)
> + continue;
> +  /* EXP >= 0 here.  */
> +  if (map == NULL)
> + map = new hash_map ;
> +  map->put (ranges[i].exp, i);
> +}
> +
> +  if (map == NULL)
> +return false;
> +
> +  for (i = 0; i < length; i++)
> +{
> +  if (ranges[i].low == NULL_TREE
> +   || ranges[i].high == NULL_TREE
> +   || !integer_zerop (ranges[i].low)
> +   || !integer_zerop (ranges[i].high))
> + continue;
> +
> +  gimple *stmt;
> +  tree_code ccode;
> +  tree rhs1, rhs2;
> +  if (ranges[i].exp)
> + {
> +   stmt = SSA_NAME_DEF_STMT (ranges[i].exp);
> +   if (!is_gimple_assign (stmt))
> + continue;
> +   ccode = gimple_assign_rhs_code (stmt);
> +   rhs1 = gimple_assign_rhs1 (stmt);
> +   rhs2 = gimple_assign_rhs2 (stmt);
> + }
> +  else
> + {
> +   operand_entry *oe = (*ops)[ranges[i].idx];
> +   stmt = last_stmt (BASIC_BLOCK_FOR_FN (cfun, oe->id));
> +   if (gimple_code (stmt) != GIMPLE_COND)
> + continue;
> +   ccode = gimple_cond_code (stmt);
> +   rhs1 = gimple_cond_lhs (stmt);
> +   rhs2 = gimple_cond_rhs (stmt);
> + }
> +
> +  if (TREE_CODE (rhs1) != SSA_NAME
> +   || rhs2 == NULL_TREE
> +   || TREE_CODE (rhs2) != SSA_NAME)
> + continue;
> +
> +  switch (ccode)
> + {
> + case GT_EXPR:
> + case GE_EXPR:
> +   if (!ranges[i].in_p)
> + std::swap (rhs1, rhs2);
> +   ccode = swap_tree_comparison (ccode);
> +   break;
> + case LT_EXPR:
> + case LE_EXPR:
> +   if (ranges[i].in_p)
> + std::swap (rhs1, rhs2);
> +   break;
> + default:
> +   continue;
> + }
> +
> +  int *idx = map->get (rhs1);
> +  if (idx == NULL)
> + continue;
> +
> +  wide_int nz = get_nonzero_bits (rhs2);
> +  if (wi::neg_p (nz))
> +

Re: [PATCH] Optimize a >= 0 && a < b if VR info says b >= 0 (PR tree-optimization/77664)

2016-10-06 Thread Jakub Jelinek 
On Thu, Oct 06, 2016 at 11:55:00PM +0200, Marc Glisse wrote:
> On Thu, 6 Oct 2016, Jakub Jelinek wrote:
> 
> >For signed a, if we see a >= 0 && a < b and from VR know that b >= 0,
> >we can optimize those 2 comparisons into one unsigned -
> >(unsigned) a < (unsigned) b.  Similarly for a < 0 || a > b (and also
> >for a <= b in the first and a >= b in the second).
> 
> I guess that the slightly more general:
> X >= A && X < B where we know that A <= B
> --> (unsigned)X - (unsigned)A < (unsigned)B - (unsigned)A
> 
> generates too many operations and does not gain anything? 

Yeah, I think replacing 2 comparisons and one && with 2 subtractions and one
comparison isn't a clear win.
For constant A and B the reassoc optimize_range_tests of course handles it
for a long time already.

> The case where A
> and B are constants seems to be handled by ifcombine, currently.

Jakub

Re: [PATCH] Optimize a >= 0 && a < b if VR info says b >= 0 (PR tree-optimization/77664)

2016-10-06 Thread Marc Glisse 

On Thu, 6 Oct 2016, Jakub Jelinek wrote:


For signed a, if we see a >= 0 && a < b and from VR know that b >= 0,
we can optimize those 2 comparisons into one unsigned -
(unsigned) a < (unsigned) b.  Similarly for a < 0 || a > b (and also
for a <= b in the first and a >= b in the second).


I guess that the slightly more general:
X >= A && X < B where we know that A <= B
--> (unsigned)X - (unsigned)A < (unsigned)B - (unsigned)A

generates too many operations and does not gain anything? The case where A 
and B are constants seems to be handled by ifcombine, currently.


--
Marc Glisse

[PATCH] Optimize a >= 0 && a < b if VR info says b >= 0 (PR tree-optimization/77664)

2016-10-06 Thread Jakub Jelinek 
Hi!

For signed a, if we see a >= 0 && a < b and from VR know that b >= 0,
we can optimize those 2 comparisons into one unsigned -
(unsigned) a < (unsigned) b.  Similarly for a < 0 || a > b (and also
for a <= b in the first and a >= b in the second).

The patch implements it in the reassoc optimize_range_tests optimization,
so that it can handle even comparisons that aren't adjacent in the && or ||
or & or | conditions, and can handle the conditions across multiple bbs as
well.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2016-10-06  Jakub Jelinek  

PR tree-optimization/77664
* tree-ssa-reassoc.c (update_range_test): Also clear low and high
for the other ranges.
(optimize_range_tests_diff): Fix up formatting.
(optimize_range_tests_var_bound): New function.
(optimize_range_tests): Use it.

* gcc.dg/tree-ssa/pr77664.c: New test.
* gcc.dg/pr77664.c: New test.

--- gcc/tree-ssa-reassoc.c.jj   2016-10-05 17:01:28.724673717 +0200
+++ gcc/tree-ssa-reassoc.c  2016-10-06 13:34:08.872512318 +0200
@@ -2428,6 +2428,8 @@ update_range_test (struct range_entry *r
   else
oe->op = error_mark_node;
   range->exp = NULL_TREE;
+  range->low = NULL_TREE;
+  range->high = NULL_TREE;
 }
   return true;
 }
@@ -2485,10 +2487,10 @@ optimize_range_tests_xor (enum tree_code
((X - 43U) & ~(75U - 43U)) <= 3U.  */
 static bool
 optimize_range_tests_diff (enum tree_code opcode, tree type,
-   tree lowi, tree lowj, tree highi, tree highj,
-   vec *ops,
-   struct range_entry *rangei,
-   struct range_entry *rangej)
+  tree lowi, tree lowj, tree highi, tree highj,
+  vec *ops,
+  struct range_entry *rangei,
+  struct range_entry *rangej)
 {
   tree tem1, tem2, mask;
   /* Check highi - lowi == highj - lowj.  */
@@ -2829,6 +2831,197 @@ optimize_range_tests_to_bit_test (enum t
   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  */
+
+static bool
+optimize_range_tests_var_bound (enum tree_code opcode, int first, int length,
+   vec *ops,
+   struct range_entry *ranges)
+{
+  int i;
+  bool any_changes = false;
+  hash_map *map = NULL;
+
+  for (i = first; i < length; i++)
+{
+  if (ranges[i].exp == NULL_TREE || !ranges[i].in_p)
+   continue;
+
+  tree type = TREE_TYPE (ranges[i].exp);
+  if (!INTEGRAL_TYPE_P (type)
+ || TYPE_UNSIGNED (type)
+ || ranges[i].low == NULL_TREE
+ || !integer_zerop (ranges[i].low)
+ || ranges[i].high != NULL_TREE)
+   continue;
+  /* EXP >= 0 here.  */
+  if (map == NULL)
+   map = new hash_map ;
+  map->put (ranges[i].exp, i);
+}
+
+  if (map == NULL)
+return false;
+
+  for (i = 0; i < length; i++)
+{
+  if (ranges[i].low == NULL_TREE
+ || ranges[i].high == NULL_TREE
+ || !integer_zerop (ranges[i].low)
+ || !integer_zerop (ranges[i].high))
+   continue;
+
+  gimple *stmt;
+  tree_code ccode;
+  tree rhs1, rhs2;
+  if (ranges[i].exp)
+   {
+ stmt = SSA_NAME_DEF_STMT (ranges[i].exp);
+ if (!is_gimple_assign (stmt))
+   continue;
+ ccode = gimple_assign_rhs_code (stmt);
+ rhs1 = gimple_assign_rhs1 (stmt);
+ rhs2 = gimple_assign_rhs2 (stmt);
+   }
+  else
+   {
+ operand_entry *oe = (*ops)[ranges[i].idx];
+ stmt = last_stmt (BASIC_BLOCK_FOR_FN (cfun, oe->id));
+ if (gimple_code (stmt) != GIMPLE_COND)
+   continue;
+ ccode = gimple_cond_code (stmt);
+ rhs1 = gimple_cond_lhs (stmt);
+ rhs2 = gimple_cond_rhs (stmt);
+   }
+
+  if (TREE_CODE (rhs1) != SSA_NAME
+ || rhs2 == NULL_TREE
+ || TREE_CODE (rhs2) != SSA_NAME)
+   continue;
+
+  switch (ccode)
+   {
+   case GT_EXPR:
+   case GE_EXPR:
+ if (!ranges[i].in_p)
+   std::swap (rhs1, rhs2);
+ ccode = swap_tree_comparison (ccode);
+ break;
+   case LT_EXPR:
+   case LE_EXPR:
+ if (ranges[i].in_p)
+   std::swap (rhs1, rhs2);
+ break;
+   default:
+ continue;
+   }
+
+  int *idx = map->get (rhs1);
+  if (idx == NULL)
+   continue;
+
+  wide_int nz = get_nonzero_bits (rhs2);
+  if (wi::neg_p (nz))
+   continue;
+
+  /* We have EXP < RHS2 or EXP <= RHS2 where EXP >= 0
+and RHS2 is known to be RHS2 >= 0.  */
+  tree utype = unsigned_type_for (TREE_TYPE (rhs1));
+
+  enum warn_strict_overflow_code wc =