diff mbox

[RFC,PR61839] Convert CST BINOP COND_EXPR to COND_EXPR ? (CST BINOP 1) : (CST BINOP 0)

Message ID ea3a3dae-3729-f92d-7991-3038c41635c6@linaro.org
State New
Headers show

Commit Message

Kugan Vivekanandarajah Aug. 12, 2016, 3:19 a.m. UTC
Hi Richard,


On 11/08/16 20:04, Richard Biener wrote:
> On Thu, Aug 11, 2016 at 6:11 AM, kugan

> <kugan.vivekanandarajah@linaro.org> wrote:


[SNIP]

>

> +two_valued_val_range_p (tree var, tree *a, tree *b)

> +{

> +  value_range *vr = get_value_range (var);

> +  if ((vr->type != VR_RANGE

> +       && vr->type != VR_ANTI_RANGE)

> +      || !range_int_cst_p (vr))

> +    return false;

>

> range_int_cst_p checks for vr->type == VR_RANGE so the anti-range handling

> doesn't ever trigger - which means you should add a testcase for it as well.


Fixed it. I have also added a testcase.

>

>

> +    {

> +      *a = TYPE_MIN_VALUE (TREE_TYPE (var));

> +      *b = TYPE_MAX_VALUE (TREE_TYPE (var));

>

> note that for pointer types this doesn't work, please also use

> vrp_val_min/max for

> consistency.  I think you want to add a INTEGRAL_TYPE_P (TREE_TYPE (var))

> to the guard of two_valued_val_range_p.

>

> +      /* First canonicalize to simplify tests.  */

> +      if (commutative_tree_code (rhs_code)

> +         && TREE_CODE (rhs2) == INTEGER_CST)

> +       std::swap (rhs1, rhs2);

>

> note that this doesn't really address my comment - if you just want to handle

> commutative ops then simply look for the constant in the second place rather

> than the first which is the canonical operand order.  But even for

> non-commutative

> operations we might want to apply this optimization - and then for both cases,

> rhs1 or rhs2 being constant.  Like x / 5 and 5 / x.

>

> Note that you can rely on int_const_binop returning NULL_TREE for "invalid"

> ops like x % 0 or x / 0, so no need to explicitely guard this here.


Sorry, I misunderstood you. I have changed it now. I also added 
test-case to check this.

Bootstrapped and regression tested on x86_64-linux-gnu with no new 
regressions. Is this OK for trunk now?

Thanks,
Kugan

gcc/testsuite/ChangeLog:

2016-08-12  Kugan Vivekanandarajah  <kuganv@linaro.org>

	PR tree-optimization/61839
	* gcc.dg/tree-ssa/pr61839_1.c: New test.
	* gcc.dg/tree-ssa/pr61839_2.c: New test.
	* gcc.dg/tree-ssa/pr61839_3.c: New test.
	* gcc.dg/tree-ssa/pr61839_4.c: New test.

gcc/ChangeLog:

2016-08-12  Kugan Vivekanandarajah  <kuganv@linaro.org>

	PR tree-optimization/61839
	* tree-vrp.c (two_valued_val_range_p): New.
	(simplify_stmt_using_ranges): Convert CST BINOP VAR where VAR is
	two-valued to VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2).
	Also Convert VAR BINOP CST where VAR is two-valued to
	VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST).

Comments

Kugan Vivekanandarajah Aug. 19, 2016, 8:17 a.m. UTC | #1
Ping?

https://gcc.gnu.org/ml/gcc-patches/2016-08/msg00987.html

Thanks,
Kugan

On 12 August 2016 at 13:19, kugan <kugan.vivekanandarajah@linaro.org> wrote:
> Hi Richard,

>

>

> On 11/08/16 20:04, Richard Biener wrote:

>>

>> On Thu, Aug 11, 2016 at 6:11 AM, kugan

>> <kugan.vivekanandarajah@linaro.org> wrote:

>

>

> [SNIP]

>

>>

>> +two_valued_val_range_p (tree var, tree *a, tree *b)

>> +{

>> +  value_range *vr = get_value_range (var);

>> +  if ((vr->type != VR_RANGE

>> +       && vr->type != VR_ANTI_RANGE)

>> +      || !range_int_cst_p (vr))

>> +    return false;

>>

>> range_int_cst_p checks for vr->type == VR_RANGE so the anti-range handling

>> doesn't ever trigger - which means you should add a testcase for it as

>> well.

>

>

> Fixed it. I have also added a testcase.

>

>>

>>

>> +    {

>> +      *a = TYPE_MIN_VALUE (TREE_TYPE (var));

>> +      *b = TYPE_MAX_VALUE (TREE_TYPE (var));

>>

>> note that for pointer types this doesn't work, please also use

>> vrp_val_min/max for

>> consistency.  I think you want to add a INTEGRAL_TYPE_P (TREE_TYPE (var))

>> to the guard of two_valued_val_range_p.

>>

>> +      /* First canonicalize to simplify tests.  */

>> +      if (commutative_tree_code (rhs_code)

>> +         && TREE_CODE (rhs2) == INTEGER_CST)

>> +       std::swap (rhs1, rhs2);

>>

>> note that this doesn't really address my comment - if you just want to

>> handle

>> commutative ops then simply look for the constant in the second place

>> rather

>> than the first which is the canonical operand order.  But even for

>> non-commutative

>> operations we might want to apply this optimization - and then for both

>> cases,

>> rhs1 or rhs2 being constant.  Like x / 5 and 5 / x.

>>

>> Note that you can rely on int_const_binop returning NULL_TREE for

>> "invalid"

>> ops like x % 0 or x / 0, so no need to explicitely guard this here.

>

>

> Sorry, I misunderstood you. I have changed it now. I also added test-case to

> check this.

>

> Bootstrapped and regression tested on x86_64-linux-gnu with no new

> regressions. Is this OK for trunk now?

>

> Thanks,

> Kugan

>

> gcc/testsuite/ChangeLog:

>

> 2016-08-12  Kugan Vivekanandarajah  <kuganv@linaro.org>

>

>         PR tree-optimization/61839

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

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

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

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

>

> gcc/ChangeLog:

>

> 2016-08-12  Kugan Vivekanandarajah  <kuganv@linaro.org>

>

>         PR tree-optimization/61839

>         * tree-vrp.c (two_valued_val_range_p): New.

>         (simplify_stmt_using_ranges): Convert CST BINOP VAR where VAR is

>         two-valued to VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2).

>         Also Convert VAR BINOP CST where VAR is two-valued to

>         VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST).
diff mbox

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_1.c
index e69de29..9f8168a 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_1.c
@@ -0,0 +1,44 @@ 
+/* PR tree-optimization/61839.  */
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-optimized" } */
+/* { dg-require-effective-target int32plus } */
+
+__attribute__ ((noinline))
+int foo ()
+{
+  int a = -1;
+  volatile unsigned b = 1U;
+  int c = 1;
+  c = (a + 972195718) >> (1LU <= b);
+  if (c == 486097858)
+    ;
+  else
+    __builtin_abort ();
+  return 0;
+}
+
+__attribute__ ((noinline))
+int bar ()
+{
+  int a = -1;
+  volatile unsigned b = 1U;
+  int c = 1;
+  c = (a + 972195718) >> (b ? 2 : 3);
+  if (c == 243048929)
+    ;
+  else
+    __builtin_abort ();
+  return 0;
+}
+
+int main ()
+{
+  foo ();
+  bar ();
+}
+
+/* Scan for c = 972195717) >> [0, 1] in function foo.  */
+/* { dg-final { scan-tree-dump-times "486097858 : 972195717" 1  "vrp1" } } */
+/* Scan for c = 972195717) >> [2, 3] in function bar.  */
+/* { dg-final { scan-tree-dump-times "243048929 : 121524464" 2  "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "486097858" 0  "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
index e69de29..ffa00a7 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
@@ -0,0 +1,54 @@ 
+/* PR tree-optimization/61839.  */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-require-effective-target int32plus } */
+
+__attribute__ ((noinline))
+int foo ()
+{
+  int a = -1;
+  volatile unsigned b = 1U;
+  int c = 1;
+  c = (a + 972195718) / (b ? 1 : 0);
+  if (c == 972195717)
+    ;
+  else
+    __builtin_abort ();
+  return 0;
+}
+
+__attribute__ ((noinline))
+int bar ()
+{
+  int a = -1;
+  volatile unsigned b = 1U;
+  int c = 1;
+  c = (a + 972195718) % (b ? 1 : 0);
+  if (c == 972195717)
+    ;
+  else
+    __builtin_abort ();
+  return 0;
+}
+
+__attribute__ ((noinline))
+int bar2 ()
+{
+  int a = -1;
+  volatile unsigned b = 1U;
+  int c = 1;
+  c = (a + 972195716) % (b ? 1 : 2);
+  if (c == 972195715)
+    ;
+  else
+    __builtin_abort ();
+  return 0;
+}
+
+
+/* Dont optimize 972195717 / 0 in function foo.  */
+/* { dg-final { scan-tree-dump-times "972195717 / _" 1  "vrp1" } } */
+/* Dont optimize 972195717 % 0 in function bar.  */
+/* { dg-final { scan-tree-dump-times "972195717 % _" 1 "vrp1" } } */
+/* Optimize in function bar2.  */
+/* { dg-final { scan-tree-dump-times "972195715 % _" 0 "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_3.c
index e69de29..5ceb073 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_3.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_3.c
@@ -0,0 +1,26 @@ 
+/* PR tree-optimization/61839.  */
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-optimized" } */
+
+__attribute__ ((noinline))
+int foo (int a, unsigned b)
+{
+  int c = 1;
+  b =  a ? 12 : 13;
+  c = b << 8;
+  if (c == 3072)
+    ;
+  else
+    __builtin_abort ();
+  return 0;
+}
+
+int main ()
+{
+  volatile unsigned b = 1U;
+  foo (-1, b);
+}
+
+/* Scan for c [12, 13] << 8 in function foo.  */
+/* { dg-final { scan-tree-dump-times "3072 : 3328" 2  "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "3072" 0  "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_4.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_4.c
index e69de29..5c026c8 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_4.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_4.c
@@ -0,0 +1,28 @@ 
+/* PR tree-optimization/61839.  */
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-optimized" } */
+/* { dg-require-effective-target int32plus } */
+
+__attribute__ ((noinline))
+int foo (int a, unsigned b)
+{
+  unsigned c = 1;
+  if (b >= 1 && b <= ((unsigned)(-1) - 1))
+    return 0;
+  c = b >> 4;
+  if (c == 268435455)
+    ;
+  else
+    __builtin_abort ();
+  return 0;
+}
+
+int main ()
+{
+  volatile unsigned b = (unsigned)(-1);
+  foo (-1, b);
+}
+
+/* Scan for ~[1, 4294967294] >> 4 in function foo.  */
+/* { dg-final { scan-tree-dump-times "0 : 268435455" 1  "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "268435455" 0  "optimized" } } */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 7c7ad91..837d768 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10004,6 +10004,40 @@  simplify_internal_call_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
   return true;
 }
 
+/* Return true if VAR is a two-valued variable.  Set a and b with the
+   two-values when it is true.  Return false otherwise.  */
+
+static bool
+two_valued_val_range_p (tree var, tree *a, tree *b)
+{
+  value_range *vr = get_value_range (var);
+  if ((vr->type != VR_RANGE
+       && vr->type != VR_ANTI_RANGE)
+      || TREE_CODE (vr->min) != INTEGER_CST
+      || TREE_CODE (vr->max) != INTEGER_CST)
+    return false;
+
+  if (vr->type == VR_RANGE
+      && wi::sub (vr->max, vr->min) == 1)
+    {
+      *a = vr->min;
+      *b = vr->max;
+      return true;
+    }
+
+  /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */
+  if (vr->type == VR_ANTI_RANGE
+      && wi::sub (vr->min, wi::min_value (TREE_TYPE (var))) == 1
+      && wi::sub (wi::max_value (TREE_TYPE (var)), vr->max) == 1)
+    {
+      *a = vrp_val_min (TREE_TYPE (var));
+      *b = vrp_val_max (TREE_TYPE (var));
+      return true;
+    }
+
+  return false;
+}
+
 /* Simplify STMT using ranges if possible.  */
 
 static bool
@@ -10014,6 +10048,68 @@  simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
     {
       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
       tree rhs1 = gimple_assign_rhs1 (stmt);
+      tree rhs2 = gimple_assign_rhs2 (stmt);
+      tree lhs = gimple_assign_lhs (stmt);
+      tree val1 = NULL_TREE, val2 = NULL_TREE;
+      use_operand_p use_p;
+      gimple *use_stmt;
+
+      /* Convert:
+	 LHS = CST BINOP VAR
+	 Where VAR is two-valued and LHS is used in GIMPLE_COND only
+	 To:
+	 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
+
+	 Also handles:
+	 LHS = VAR BINOP CST
+	 Where VAR is two-valued and LHS is used in GIMPLE_COND only
+	 To:
+	 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
+
+      if (TREE_CODE_CLASS (rhs_code) == tcc_binary
+	  && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+	  && ((TREE_CODE (rhs1) == INTEGER_CST
+	       && TREE_CODE (rhs2) == SSA_NAME)
+	      || (TREE_CODE (rhs2) == INTEGER_CST
+		  && TREE_CODE (rhs1) == SSA_NAME))
+	  && single_imm_use (lhs, &use_p, &use_stmt)
+	  && gimple_code (use_stmt) == GIMPLE_COND)
+
+	{
+	  tree new_rhs1 = NULL_TREE;
+	  tree new_rhs2 = NULL_TREE;
+	  tree cmp_var = NULL_TREE;
+
+	  if (TREE_CODE (rhs2) == SSA_NAME
+	      && two_valued_val_range_p (rhs2, &val1, &val2))
+	    {
+	      /* Optimize RHS1 OP [VAL1, VAL2].  */
+	      new_rhs1 = int_const_binop (rhs_code, rhs1, val1);
+	      new_rhs2 = int_const_binop (rhs_code, rhs1, val2);
+	      cmp_var = rhs2;
+	    }
+	  else if (TREE_CODE (rhs1) == SSA_NAME
+		   && two_valued_val_range_p (rhs1, &val1, &val2))
+	    {
+	      /* Optimize [VAL1, VAL2] OP RHS2.  */
+	      new_rhs1 = int_const_binop (rhs_code, val1, rhs2);
+	      new_rhs2 = int_const_binop (rhs_code, val2, rhs2);
+	      cmp_var = rhs1;
+	    }
+
+	  /* If we could not find two-vals or the optimzation is invalid as
+	     in divide by zero, new_rhs1 / new_rhs will be NULL_TREE.  */
+	  if (new_rhs1 && new_rhs2)
+	    {
+	      tree cond = build2 (EQ_EXPR, TREE_TYPE (cmp_var), cmp_var, val1);
+	      gimple_assign_set_rhs_with_ops (gsi,
+					      COND_EXPR, cond,
+					      new_rhs1,
+					      new_rhs2);
+	      update_stmt (gsi_stmt (*gsi));
+	      return true;
+	    }
+	}
 
       switch (rhs_code)
 	{