* [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676) @ 2019-01-04 22:49 Jakub Jelinek 2019-01-05 8:51 ` Richard Biener 0 siblings, 1 reply; 5+ messages in thread From: Jakub Jelinek @ 2019-01-04 22:49 UTC (permalink / raw) To: Richard Biener, Jeff Law; +Cc: gcc-patches Hi! The following patch adds an optimization, if we know certain SSA_NAME has two possible values and have GIMPLE_COND EQ_EXPR/NE_EXPR of that SSA_NAME with one of the two values and PHI which has two adjacent constants, we can optimize it into addition or subtraction. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? The pr15826.c change is just a small change on what is present in GIMPLE with this patch, previously (from the bugzilla apparently only on some targets) we had a (_Bool) cast and now we have & 1, which effectively results in exactly the same expansion. 2019-01-04 Jakub Jelinek <jakub@redhat.com> PR tree-optimization/88676 * tree-ssa-phiopt.c (two_value_replacement): New function. (tree_ssa_phiopt_worker): Call it. * gcc.dg/tree-ssa/pr88676.c: New test. * gcc.dg/pr88676.c: New test. * gcc.dg/tree-ssa/pr15826.c: Just verify there is no goto, allow &. --- gcc/tree-ssa-phiopt.c.jj 2019-01-01 12:37:17.716965779 +0100 +++ gcc/tree-ssa-phiopt.c 2019-01-04 13:55:26.293746657 +0100 @@ -48,6 +48,8 @@ along with GCC; see the file COPYING3. #include "case-cfn-macros.h" static unsigned int tree_ssa_phiopt_worker (bool, bool, bool); +static bool two_value_replacement (basic_block, basic_block, edge, gphi *, + tree, tree); static bool conditional_replacement (basic_block, basic_block, edge, edge, gphi *, tree, tree); static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree, @@ -332,8 +334,11 @@ tree_ssa_phiopt_worker (bool do_store_el } /* Do the replacement of conditional if it can be done. */ - if (!early_p - && conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) + if (two_value_replacement (bb, bb1, e2, phi, arg0, arg1)) + cfgchanged = true; + else if (!early_p + && conditional_replacement (bb, bb1, e1, e2, phi, + arg0, arg1)) cfgchanged = true; else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; @@ -572,6 +577,118 @@ factor_out_conditional_conversion (edge return newphi; } +/* Optimize + # x_5 in range [cst1, cst2] where cst2 = cst1 + 1 + if (x_5 op cstN) # where op is == or != and N is 1 or 2 + goto bb3; + else + goto bb4; + bb3: + bb4: + # r_6 = PHI<cst3(2), cst4(3)> # where cst3 == cst4 + 1 or cst4 == cst3 + 1 + + to r_6 = x_5 + (min (cst3, cst4) - cst1) or + r_6 = (min (cst3, cst4) + cst1) - x_5 depending on op, N and which + of cst3 and cst4 is smaller. */ + +static bool +two_value_replacement (basic_block cond_bb, basic_block middle_bb, + edge e1, gphi *phi, tree arg0, tree arg1) +{ + /* Only look for adjacent integer constants. */ + if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0)) + || !INTEGRAL_TYPE_P (TREE_TYPE (arg1)) + || TREE_CODE (arg0) != INTEGER_CST + || TREE_CODE (arg1) != INTEGER_CST + || (tree_int_cst_lt (arg0, arg1) + ? wi::to_widest (arg0) + 1 != wi::to_widest (arg1) + : wi::to_widest (arg1) + 1 != wi::to_widest (arg1))) + return false; + + if (!empty_block_p (middle_bb)) + return false; + + gimple *stmt = last_stmt (cond_bb); + tree lhs = gimple_cond_lhs (stmt); + tree rhs = gimple_cond_rhs (stmt); + + if (TREE_CODE (lhs) != SSA_NAME + || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)) + || TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE + || TREE_CODE (rhs) != INTEGER_CST) + return false; + + switch (gimple_cond_code (stmt)) + { + case EQ_EXPR: + case NE_EXPR: + break; + default: + return false; + } + + wide_int min, max; + if (get_range_info (lhs, &min, &max) != VR_RANGE + || min + 1 != max + || (wi::to_wide (rhs) != min + && wi::to_wide (rhs) != max)) + return false; + + /* We need to know which is the true edge and which is the false + edge so that we know when to invert the condition below. */ + edge true_edge, false_edge; + extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); + if ((gimple_cond_code (stmt) == EQ_EXPR) + ^ (wi::to_wide (rhs) == max) + ^ (e1 == false_edge)) + std::swap (arg0, arg1); + + tree type; + if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE (arg0))) + { + if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE + || !TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg0))) + type = TREE_TYPE (lhs); + else + type = TREE_TYPE (arg0); + } + else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION (TREE_TYPE (arg0))) + type = TREE_TYPE (lhs); + else + type = TREE_TYPE (arg0); + if (!TYPE_OVERFLOW_WRAPS (type)) + type = unsigned_type_for (type); + + tree m = fold_convert (type, wide_int_to_tree (TREE_TYPE (lhs), min)); + enum tree_code code; + if (tree_int_cst_lt (arg0, arg1)) + { + code = PLUS_EXPR; + m = int_const_binop (MINUS_EXPR, fold_convert (type, arg0), m); + } + else + { + code = MINUS_EXPR; + m = int_const_binop (PLUS_EXPR, fold_convert (type, arg0), m); + } + + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + if (!useless_type_conversion_p (type, TREE_TYPE (lhs))) + lhs = gimplify_build1 (&gsi, NOP_EXPR, type, lhs); + tree new_rhs; + if (code == PLUS_EXPR) + new_rhs = gimplify_build2 (&gsi, PLUS_EXPR, type, lhs, m); + else + new_rhs = gimplify_build2 (&gsi, MINUS_EXPR, type, m, lhs); + if (!useless_type_conversion_p (TREE_TYPE (arg0), type)) + new_rhs = gimplify_build1 (&gsi, NOP_EXPR, TREE_TYPE (arg0), new_rhs); + + replace_phi_edge_with_variable (cond_bb, e1, phi, new_rhs); + + /* Note that we optimized this PHI. */ + return true; +} + /* The function conditional_replacement does the main work of doing the conditional replacement. Return true if the replacement is done. Otherwise return false. --- gcc/testsuite/gcc.dg/tree-ssa/pr88676.c.jj 2019-01-04 14:20:59.659542587 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/pr88676.c 2019-01-04 14:25:38.122965795 +0100 @@ -0,0 +1,133 @@ +/* PR tree-optimization/88676 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-not " = PHI <" "optimized" } } */ + +void bar (int, int, int); + +__attribute__((noipa)) int +f1 (unsigned x) +{ + int r; + if (x >= 2) + __builtin_unreachable (); + switch (x) + { + case 0: + r = 1; + break; + case 1: + r = 2; + break; + default: + r = 0; + break; + } + return r; +} + +__attribute__((noipa)) void +f2 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 98) + y = 115; + else + y = 116; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f3 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 98) + y = 115; + else + y = 116; + bar (x, y, 115); +} + +__attribute__((noipa)) void +f4 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 99) + y = 115; + else + y = 116; + bar (x, y, 115); +} + +__attribute__((noipa)) void +f5 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 99) + y = 115; + else + y = 116; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f6 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 98) + y = 116; + else + y = 115; + bar (x, y, 115); +} + +__attribute__((noipa)) void +f7 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 98) + y = 116; + else + y = 115; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f8 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 99) + y = 116; + else + y = 115; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f9 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 99) + y = 116; + else + y = 115; + bar (x, y, 115); +} + +__attribute__((noipa)) int +f10 (int x) +{ + x = (x & 1) + 36; + if (x == 36) + return 85; + else + return 84; +} --- gcc/testsuite/gcc.dg/pr88676.c.jj 2019-01-04 14:29:55.821731065 +0100 +++ gcc/testsuite/gcc.dg/pr88676.c 2019-01-04 14:29:39.048006694 +0100 @@ -0,0 +1,48 @@ +/* PR tree-optimization/88676 */ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +#include "tree-ssa/pr88676.c" + +__attribute__((noipa)) void +bar (int x, int y, int z) +{ + if (z != 115 && z != 116) + __builtin_abort (); + if (x == 98) + { + if (y != z) + __builtin_abort (); + } + else if (x != 99) + __builtin_abort (); + else if (z == 115) + { + if (y != 116) + __builtin_abort (); + } + else if (y != 115) + __builtin_abort (); +} + +int +main () +{ + if (f1 (0) != 1 || f1 (1) != 2) + __builtin_abort (); + int i; + for (i = -12; i < 12; i++) + { + f2 (i); + f3 (i); + f4 (i); + f5 (i); + f6 (i); + f7 (i); + f8 (i); + f9 (i); + if (f10 (i) != ((i & 1) ? 84 : 85)) + __builtin_abort (); + } + return 0; +} --- gcc/testsuite/gcc.dg/tree-ssa/pr15826.c.jj 2016-02-27 07:41:54.377920386 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/pr15826.c 2019-01-04 23:41:36.300566686 +0100 @@ -33,4 +33,4 @@ andrew (struct s *p) return i; } -/* { dg-final { scan-tree-dump-times " & | goto " 0 "optimized" } } */ +/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */ Jakub ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676) 2019-01-04 22:49 [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676) Jakub Jelinek @ 2019-01-05 8:51 ` Richard Biener 2019-01-05 12:18 ` [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676, take 2) Jakub Jelinek 0 siblings, 1 reply; 5+ messages in thread From: Richard Biener @ 2019-01-05 8:51 UTC (permalink / raw) To: Jakub Jelinek, Jeff Law; +Cc: gcc-patches On January 4, 2019 11:49:45 PM GMT+01:00, Jakub Jelinek <jakub@redhat.com> wrote: >Hi! > >The following patch adds an optimization, if we know certain SSA_NAME >has two possible values and have GIMPLE_COND EQ_EXPR/NE_EXPR of that >SSA_NAME with one of the two values and PHI which has two adjacent >constants, we can optimize it into addition or subtraction. > >Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? > >The pr15826.c change is just a small change on what is present in >GIMPLE >with this patch, previously (from the bugzilla apparently only on some >targets) we had a (_Bool) cast and now we have & 1, which effectively >results in exactly the same expansion. > >2019-01-04 Jakub Jelinek <jakub@redhat.com> > > PR tree-optimization/88676 > * tree-ssa-phiopt.c (two_value_replacement): New function. > (tree_ssa_phiopt_worker): Call it. > > * gcc.dg/tree-ssa/pr88676.c: New test. > * gcc.dg/pr88676.c: New test. > * gcc.dg/tree-ssa/pr15826.c: Just verify there is no goto, > allow &. > >--- gcc/tree-ssa-phiopt.c.jj 2019-01-01 12:37:17.716965779 +0100 >+++ gcc/tree-ssa-phiopt.c 2019-01-04 13:55:26.293746657 +0100 >@@ -48,6 +48,8 @@ along with GCC; see the file COPYING3. > #include "case-cfn-macros.h" > > static unsigned int tree_ssa_phiopt_worker (bool, bool, bool); >+static bool two_value_replacement (basic_block, basic_block, edge, >gphi *, >+ tree, tree); > static bool conditional_replacement (basic_block, basic_block, > edge, edge, gphi *, tree, tree); >static gphi *factor_out_conditional_conversion (edge, edge, gphi *, >tree, tree, >@@ -332,8 +334,11 @@ tree_ssa_phiopt_worker (bool do_store_el > } > > /* Do the replacement of conditional if it can be done. */ >- if (!early_p >- && conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) >+ if (two_value_replacement (bb, bb1, e2, phi, arg0, arg1)) >+ cfgchanged = true; >+ else if (!early_p >+ && conditional_replacement (bb, bb1, e1, e2, phi, >+ arg0, arg1)) > cfgchanged = true; > else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) > cfgchanged = true; >@@ -572,6 +577,118 @@ factor_out_conditional_conversion (edge > return newphi; > } > >+/* Optimize >+ # x_5 in range [cst1, cst2] where cst2 = cst1 + 1 >+ if (x_5 op cstN) # where op is == or != and N is 1 or 2 >+ goto bb3; >+ else >+ goto bb4; >+ bb3: >+ bb4: >+ # r_6 = PHI<cst3(2), cst4(3)> # where cst3 == cst4 + 1 or cst4 == >cst3 + 1 >+ >+ to r_6 = x_5 + (min (cst3, cst4) - cst1) or >+ r_6 = (min (cst3, cst4) + cst1) - x_5 depending on op, N and which >+ of cst3 and cst4 is smaller. */ >+ >+static bool >+two_value_replacement (basic_block cond_bb, basic_block middle_bb, >+ edge e1, gphi *phi, tree arg0, tree arg1) >+{ >+ /* Only look for adjacent integer constants. */ >+ if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0)) >+ || !INTEGRAL_TYPE_P (TREE_TYPE (arg1)) >+ || TREE_CODE (arg0) != INTEGER_CST >+ || TREE_CODE (arg1) != INTEGER_CST >+ || (tree_int_cst_lt (arg0, arg1) >+ ? wi::to_widest (arg0) + 1 != wi::to_widest (arg1) >+ : wi::to_widest (arg1) + 1 != wi::to_widest (arg1))) >+ return false; >+ >+ if (!empty_block_p (middle_bb)) >+ return false; >+ >+ gimple *stmt = last_stmt (cond_bb); >+ tree lhs = gimple_cond_lhs (stmt); >+ tree rhs = gimple_cond_rhs (stmt); >+ >+ if (TREE_CODE (lhs) != SSA_NAME >+ || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)) >+ || TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE >+ || TREE_CODE (rhs) != INTEGER_CST) >+ return false; >+ >+ switch (gimple_cond_code (stmt)) >+ { >+ case EQ_EXPR: >+ case NE_EXPR: >+ break; >+ default: >+ return false; >+ } >+ >+ wide_int min, max; >+ if (get_range_info (lhs, &min, &max) != VR_RANGE >+ || min + 1 != max >+ || (wi::to_wide (rhs) != min >+ && wi::to_wide (rhs) != max)) >+ return false; >+ >+ /* We need to know which is the true edge and which is the false >+ edge so that we know when to invert the condition below. */ >+ edge true_edge, false_edge; >+ extract_true_false_edges_from_block (cond_bb, &true_edge, >&false_edge); >+ if ((gimple_cond_code (stmt) == EQ_EXPR) >+ ^ (wi::to_wide (rhs) == max) >+ ^ (e1 == false_edge)) >+ std::swap (arg0, arg1); >+ >+ tree type; >+ if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE >(arg0))) >+ { >+ if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE >+ || !TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg0))) >+ type = TREE_TYPE (lhs); >+ else >+ type = TREE_TYPE (arg0); This misses some comments. Presumably you want to avoid arithmetic with bool types (or generally non-mode precision types!?). >+ } >+ else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION >(TREE_TYPE (arg0))) >+ type = TREE_TYPE (lhs); >+ else >+ type = TREE_TYPE (arg0); >+ if (!TYPE_OVERFLOW_WRAPS (type)) >+ type = unsigned_type_for (type); Would doing this unconditionally simplify things? I think "optimizing" the - fwrapv case isn't worth it. >+ >+ tree m = fold_convert (type, wide_int_to_tree (TREE_TYPE (lhs), >min)); >+ enum tree_code code; >+ if (tree_int_cst_lt (arg0, arg1)) >+ { >+ code = PLUS_EXPR; >+ m = int_const_binop (MINUS_EXPR, fold_convert (type, arg0), m); >+ } >+ else >+ { >+ code = MINUS_EXPR; >+ m = int_const_binop (PLUS_EXPR, fold_convert (type, arg0), m); >+ } Delay wide-int to tree conversion until here. >+ >+ gimple_stmt_iterator gsi = gsi_for_stmt (stmt); >+ if (!useless_type_conversion_p (type, TREE_TYPE (lhs))) >+ lhs = gimplify_build1 (&gsi, NOP_EXPR, type, lhs); >+ tree new_rhs; >+ if (code == PLUS_EXPR) >+ new_rhs = gimplify_build2 (&gsi, PLUS_EXPR, type, lhs, m); >+ else >+ new_rhs = gimplify_build2 (&gsi, MINUS_EXPR, type, m, lhs); >+ if (!useless_type_conversion_p (TREE_TYPE (arg0), type)) >+ new_rhs = gimplify_build1 (&gsi, NOP_EXPR, TREE_TYPE (arg0), >new_rhs); >+ >+ replace_phi_edge_with_variable (cond_bb, e1, phi, new_rhs); >+ >+ /* Note that we optimized this PHI. */ >+ return true; >+} >+ >/* The function conditional_replacement does the main work of doing >the > conditional replacement. Return true if the replacement is done. > Otherwise return false. >--- gcc/testsuite/gcc.dg/tree-ssa/pr88676.c.jj 2019-01-04 >14:20:59.659542587 +0100 >+++ gcc/testsuite/gcc.dg/tree-ssa/pr88676.c 2019-01-04 >14:25:38.122965795 +0100 >@@ -0,0 +1,133 @@ >+/* PR tree-optimization/88676 */ >+/* { dg-do compile } */ >+/* { dg-options "-O2 -fdump-tree-optimized" } */ >+/* { dg-final { scan-tree-dump-not " = PHI <" "optimized" } } */ >+ >+void bar (int, int, int); >+ >+__attribute__((noipa)) int >+f1 (unsigned x) >+{ >+ int r; >+ if (x >= 2) >+ __builtin_unreachable (); >+ switch (x) >+ { >+ case 0: >+ r = 1; >+ break; >+ case 1: >+ r = 2; >+ break; >+ default: >+ r = 0; >+ break; >+ } >+ return r; >+} >+ >+__attribute__((noipa)) void >+f2 (int x) >+{ >+ int y; >+ x = (x & 1) + 98; >+ if (x != 98) >+ y = 115; >+ else >+ y = 116; >+ bar (x, y, 116); >+} >+ >+__attribute__((noipa)) void >+f3 (int x) >+{ >+ int y; >+ x = (x & 1) + 98; >+ if (x == 98) >+ y = 115; >+ else >+ y = 116; >+ bar (x, y, 115); >+} >+ >+__attribute__((noipa)) void >+f4 (int x) >+{ >+ int y; >+ x = (x & 1) + 98; >+ if (x != 99) >+ y = 115; >+ else >+ y = 116; >+ bar (x, y, 115); >+} >+ >+__attribute__((noipa)) void >+f5 (int x) >+{ >+ int y; >+ x = (x & 1) + 98; >+ if (x == 99) >+ y = 115; >+ else >+ y = 116; >+ bar (x, y, 116); >+} >+ >+__attribute__((noipa)) void >+f6 (int x) >+{ >+ int y; >+ x = (x & 1) + 98; >+ if (x != 98) >+ y = 116; >+ else >+ y = 115; >+ bar (x, y, 115); >+} >+ >+__attribute__((noipa)) void >+f7 (int x) >+{ >+ int y; >+ x = (x & 1) + 98; >+ if (x == 98) >+ y = 116; >+ else >+ y = 115; >+ bar (x, y, 116); >+} >+ >+__attribute__((noipa)) void >+f8 (int x) >+{ >+ int y; >+ x = (x & 1) + 98; >+ if (x != 99) >+ y = 116; >+ else >+ y = 115; >+ bar (x, y, 116); >+} >+ >+__attribute__((noipa)) void >+f9 (int x) >+{ >+ int y; >+ x = (x & 1) + 98; >+ if (x == 99) >+ y = 116; >+ else >+ y = 115; >+ bar (x, y, 115); >+} >+ >+__attribute__((noipa)) int >+f10 (int x) >+{ >+ x = (x & 1) + 36; >+ if (x == 36) >+ return 85; >+ else >+ return 84; >+} >--- gcc/testsuite/gcc.dg/pr88676.c.jj 2019-01-04 14:29:55.821731065 >+0100 >+++ gcc/testsuite/gcc.dg/pr88676.c 2019-01-04 14:29:39.048006694 +0100 >@@ -0,0 +1,48 @@ >+/* PR tree-optimization/88676 */ >+/* { dg-do run } */ >+/* { dg-options "-O2" } */ >+ >+#include "tree-ssa/pr88676.c" >+ >+__attribute__((noipa)) void >+bar (int x, int y, int z) >+{ >+ if (z != 115 && z != 116) >+ __builtin_abort (); >+ if (x == 98) >+ { >+ if (y != z) >+ __builtin_abort (); >+ } >+ else if (x != 99) >+ __builtin_abort (); >+ else if (z == 115) >+ { >+ if (y != 116) >+ __builtin_abort (); >+ } >+ else if (y != 115) >+ __builtin_abort (); >+} >+ >+int >+main () >+{ >+ if (f1 (0) != 1 || f1 (1) != 2) >+ __builtin_abort (); >+ int i; >+ for (i = -12; i < 12; i++) >+ { >+ f2 (i); >+ f3 (i); >+ f4 (i); >+ f5 (i); >+ f6 (i); >+ f7 (i); >+ f8 (i); >+ f9 (i); >+ if (f10 (i) != ((i & 1) ? 84 : 85)) >+ __builtin_abort (); >+ } >+ return 0; >+} >--- gcc/testsuite/gcc.dg/tree-ssa/pr15826.c.jj 2016-02-27 >07:41:54.377920386 +0100 >+++ gcc/testsuite/gcc.dg/tree-ssa/pr15826.c 2019-01-04 >23:41:36.300566686 +0100 >@@ -33,4 +33,4 @@ andrew (struct s *p) > return i; > } > >-/* { dg-final { scan-tree-dump-times " & | goto " 0 "optimized" } } */ >+/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */ > > Jakub ^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676, take 2) 2019-01-05 8:51 ` Richard Biener @ 2019-01-05 12:18 ` Jakub Jelinek 2019-01-06 10:33 ` Jakub Jelinek 2019-01-07 8:10 ` Richard Biener 0 siblings, 2 replies; 5+ messages in thread From: Jakub Jelinek @ 2019-01-05 12:18 UTC (permalink / raw) To: Richard Biener; +Cc: Jeff Law, gcc-patches On Sat, Jan 05, 2019 at 09:51:31AM +0100, Richard Biener wrote: > >+ if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE > >(arg0))) > >+ { > >+ if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE > >+ || !TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg0))) > >+ type = TREE_TYPE (lhs); > >+ else > >+ type = TREE_TYPE (arg0); > > This misses some comments. Presumably you want to avoid arithmetic with bool types (or generally non-mode precision types!?). Just for bool because the weird semantics it has. And do as few conversions as possible. > >+ } > >+ else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION > >(TREE_TYPE (arg0))) > >+ type = TREE_TYPE (lhs); > >+ else > >+ type = TREE_TYPE (arg0); > >+ if (!TYPE_OVERFLOW_WRAPS (type)) > >+ type = unsigned_type_for (type); > > Would doing this unconditionally simplify things? I think "optimizing" the - fwrapv case isn't worth it. I've originally meant to do it only if really needed but then got lazy. > >+ tree m = fold_convert (type, wide_int_to_tree (TREE_TYPE (lhs), > >min)); > >+ enum tree_code code; > >+ if (tree_int_cst_lt (arg0, arg1)) > >+ { > >+ code = PLUS_EXPR; > >+ m = int_const_binop (MINUS_EXPR, fold_convert (type, arg0), m); > >+ } > >+ else > >+ { > >+ code = MINUS_EXPR; > >+ m = int_const_binop (PLUS_EXPR, fold_convert (type, arg0), m); > >+ } > > Delay wide-int to tree conversion until here. But by doing these computations on wide-int properly it appears it isn't that hard to do. Essentially, after conversion to type, lhs is known to be in [min, min+1] range and we either want to perform lhs + a or a - lhs. If it is in signed type, we need to verify it doesn't overflow, so if a is non-negative, make sure (min+1) + a doesn't overflow and if a is negative, make sure min + a doesn't overflow. Similarly, for a - lhs case, if min (and min+1) are non-negative, make sure a - (min+1) doesn't overflow, and if min is negative (min+1 in that case could be negative or 0), make sure a - min doesn't overflow. Ok for trunk if it passes bootstrap/regtest? I guess I should add more testcases that test these corner cases, the boundary cases of overflowing/not overflowing and different precisions of the two types. 2019-01-05 Jakub Jelinek <jakub@redhat.com> PR tree-optimization/88676 * tree-ssa-phiopt.c (two_value_replacement): New function. (tree_ssa_phiopt_worker): Call it. * gcc.dg/tree-ssa/pr88676.c: New test. * gcc.dg/pr88676.c: New test. * gcc.dg/tree-ssa/pr15826.c: Just verify there is no goto, allow &. --- gcc/tree-ssa-phiopt.c.jj 2019-01-04 18:53:11.315322371 +0100 +++ gcc/tree-ssa-phiopt.c 2019-01-05 13:04:38.185082743 +0100 @@ -48,6 +48,8 @@ along with GCC; see the file COPYING3. #include "case-cfn-macros.h" static unsigned int tree_ssa_phiopt_worker (bool, bool, bool); +static bool two_value_replacement (basic_block, basic_block, edge, gphi *, + tree, tree); static bool conditional_replacement (basic_block, basic_block, edge, edge, gphi *, tree, tree); static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree, @@ -332,8 +334,11 @@ tree_ssa_phiopt_worker (bool do_store_el } /* Do the replacement of conditional if it can be done. */ - if (!early_p - && conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) + if (two_value_replacement (bb, bb1, e2, phi, arg0, arg1)) + cfgchanged = true; + else if (!early_p + && conditional_replacement (bb, bb1, e1, e2, phi, + arg0, arg1)) cfgchanged = true; else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; @@ -572,6 +577,142 @@ factor_out_conditional_conversion (edge return newphi; } +/* Optimize + # x_5 in range [cst1, cst2] where cst2 = cst1 + 1 + if (x_5 op cstN) # where op is == or != and N is 1 or 2 + goto bb3; + else + goto bb4; + bb3: + bb4: + # r_6 = PHI<cst3(2), cst4(3)> # where cst3 == cst4 + 1 or cst4 == cst3 + 1 + + to r_6 = x_5 + (min (cst3, cst4) - cst1) or + r_6 = (min (cst3, cst4) + cst1) - x_5 depending on op, N and which + of cst3 and cst4 is smaller. */ + +static bool +two_value_replacement (basic_block cond_bb, basic_block middle_bb, + edge e1, gphi *phi, tree arg0, tree arg1) +{ + /* Only look for adjacent integer constants. */ + if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0)) + || !INTEGRAL_TYPE_P (TREE_TYPE (arg1)) + || TREE_CODE (arg0) != INTEGER_CST + || TREE_CODE (arg1) != INTEGER_CST + || (tree_int_cst_lt (arg0, arg1) + ? wi::to_widest (arg0) + 1 != wi::to_widest (arg1) + : wi::to_widest (arg1) + 1 != wi::to_widest (arg1))) + return false; + + if (!empty_block_p (middle_bb)) + return false; + + gimple *stmt = last_stmt (cond_bb); + tree lhs = gimple_cond_lhs (stmt); + tree rhs = gimple_cond_rhs (stmt); + + if (TREE_CODE (lhs) != SSA_NAME + || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)) + || TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE + || TREE_CODE (rhs) != INTEGER_CST) + return false; + + switch (gimple_cond_code (stmt)) + { + case EQ_EXPR: + case NE_EXPR: + break; + default: + return false; + } + + wide_int min, max; + if (get_range_info (lhs, &min, &max) != VR_RANGE + || min + 1 != max + || (wi::to_wide (rhs) != min + && wi::to_wide (rhs) != max)) + return false; + + /* We need to know which is the true edge and which is the false + edge so that we know when to invert the condition below. */ + edge true_edge, false_edge; + extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); + if ((gimple_cond_code (stmt) == EQ_EXPR) + ^ (wi::to_wide (rhs) == max) + ^ (e1 == false_edge)) + std::swap (arg0, arg1); + + tree type; + if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE (arg0))) + { + /* Avoid performing the arithmetics in bool type which has different + semantics, otherwise prefer unsigned types from the two with + the same precision. */ + if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE + || !TYPE_UNSIGNED (TREE_TYPE (arg0))) + type = TREE_TYPE (lhs); + else + type = TREE_TYPE (arg0); + } + else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION (TREE_TYPE (arg0))) + type = TREE_TYPE (lhs); + else + type = TREE_TYPE (arg0); + + min = wide_int::from (min, TYPE_PRECISION (type), + TYPE_SIGN (TREE_TYPE (lhs))); + wide_int a = wide_int::from (wi::to_wide (arg0), TYPE_PRECISION (type), + TYPE_SIGN (TREE_TYPE (arg0))); + enum tree_code code; + wi::overflow_type ovf; + if (tree_int_cst_lt (arg0, arg1)) + { + code = PLUS_EXPR; + a -= min; + if (!TYPE_UNSIGNED (type)) + { + /* lhs is known to be in range [min, min+1] and we want to add a + to it. Check if that operation can overflow for those 2 values + and if yes, force unsigned type. */ + wi::add (min + (wi::neg_p (a) ? 0 : 1), a, SIGNED, &ovf); + if (ovf) + type = unsigned_type_for (type); + } + } + else + { + code = MINUS_EXPR; + a += min; + if (!TYPE_UNSIGNED (type)) + { + /* lhs is known to be in range [min, min+1] and we want to subtract + it from a. Check if that operation can overflow for those 2 + values and if yes, force unsigned type. */ + wi::sub (a, min + (wi::neg_p (min) ? 0 : 1), SIGNED, &ovf); + if (ovf) + type = unsigned_type_for (type); + } + } + + tree arg = wide_int_to_tree (type, a); + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + if (!useless_type_conversion_p (type, TREE_TYPE (lhs))) + lhs = gimplify_build1 (&gsi, NOP_EXPR, type, lhs); + tree new_rhs; + if (code == PLUS_EXPR) + new_rhs = gimplify_build2 (&gsi, PLUS_EXPR, type, lhs, arg); + else + new_rhs = gimplify_build2 (&gsi, MINUS_EXPR, type, arg, lhs); + if (!useless_type_conversion_p (TREE_TYPE (arg0), type)) + new_rhs = gimplify_build1 (&gsi, NOP_EXPR, TREE_TYPE (arg0), new_rhs); + + replace_phi_edge_with_variable (cond_bb, e1, phi, new_rhs); + + /* Note that we optimized this PHI. */ + return true; +} + /* The function conditional_replacement does the main work of doing the conditional replacement. Return true if the replacement is done. Otherwise return false. --- gcc/testsuite/gcc.dg/tree-ssa/pr88676.c.jj 2019-01-05 12:25:32.463958539 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/pr88676.c 2019-01-05 12:25:32.463958539 +0100 @@ -0,0 +1,133 @@ +/* PR tree-optimization/88676 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-not " = PHI <" "optimized" } } */ + +void bar (int, int, int); + +__attribute__((noipa)) int +f1 (unsigned x) +{ + int r; + if (x >= 2) + __builtin_unreachable (); + switch (x) + { + case 0: + r = 1; + break; + case 1: + r = 2; + break; + default: + r = 0; + break; + } + return r; +} + +__attribute__((noipa)) void +f2 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 98) + y = 115; + else + y = 116; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f3 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 98) + y = 115; + else + y = 116; + bar (x, y, 115); +} + +__attribute__((noipa)) void +f4 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 99) + y = 115; + else + y = 116; + bar (x, y, 115); +} + +__attribute__((noipa)) void +f5 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 99) + y = 115; + else + y = 116; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f6 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 98) + y = 116; + else + y = 115; + bar (x, y, 115); +} + +__attribute__((noipa)) void +f7 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 98) + y = 116; + else + y = 115; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f8 (int x) +{ + int y; + x = (x & 1) + 98; + if (x != 99) + y = 116; + else + y = 115; + bar (x, y, 116); +} + +__attribute__((noipa)) void +f9 (int x) +{ + int y; + x = (x & 1) + 98; + if (x == 99) + y = 116; + else + y = 115; + bar (x, y, 115); +} + +__attribute__((noipa)) int +f10 (int x) +{ + x = (x & 1) + 36; + if (x == 36) + return 85; + else + return 84; +} --- gcc/testsuite/gcc.dg/pr88676.c.jj 2019-01-05 12:25:32.463958539 +0100 +++ gcc/testsuite/gcc.dg/pr88676.c 2019-01-05 12:25:32.463958539 +0100 @@ -0,0 +1,48 @@ +/* PR tree-optimization/88676 */ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +#include "tree-ssa/pr88676.c" + +__attribute__((noipa)) void +bar (int x, int y, int z) +{ + if (z != 115 && z != 116) + __builtin_abort (); + if (x == 98) + { + if (y != z) + __builtin_abort (); + } + else if (x != 99) + __builtin_abort (); + else if (z == 115) + { + if (y != 116) + __builtin_abort (); + } + else if (y != 115) + __builtin_abort (); +} + +int +main () +{ + if (f1 (0) != 1 || f1 (1) != 2) + __builtin_abort (); + int i; + for (i = -12; i < 12; i++) + { + f2 (i); + f3 (i); + f4 (i); + f5 (i); + f6 (i); + f7 (i); + f8 (i); + f9 (i); + if (f10 (i) != ((i & 1) ? 84 : 85)) + __builtin_abort (); + } + return 0; +} --- gcc/testsuite/gcc.dg/tree-ssa/pr15826.c.jj 2016-02-27 07:41:54.377920386 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/pr15826.c 2019-01-05 12:25:32.463958539 +0100 @@ -33,4 +33,4 @@ andrew (struct s *p) return i; } -/* { dg-final { scan-tree-dump-times " & | goto " 0 "optimized" } } */ +/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */ Jakub ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676, take 2) 2019-01-05 12:18 ` [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676, take 2) Jakub Jelinek @ 2019-01-06 10:33 ` Jakub Jelinek 2019-01-07 8:10 ` Richard Biener 1 sibling, 0 replies; 5+ messages in thread From: Jakub Jelinek @ 2019-01-06 10:33 UTC (permalink / raw) To: Richard Biener; +Cc: Jeff Law, gcc-patches On Sat, Jan 05, 2019 at 01:17:47PM +0100, Jakub Jelinek wrote: > Ok for trunk if it passes bootstrap/regtest? FYI, it passed bootstrap/regtest on x86_64-linux and i686-linux. Jakub ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676, take 2) 2019-01-05 12:18 ` [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676, take 2) Jakub Jelinek 2019-01-06 10:33 ` Jakub Jelinek @ 2019-01-07 8:10 ` Richard Biener 1 sibling, 0 replies; 5+ messages in thread From: Richard Biener @ 2019-01-07 8:10 UTC (permalink / raw) To: Jakub Jelinek; +Cc: Jeff Law, gcc-patches On Sat, 5 Jan 2019, Jakub Jelinek wrote: > On Sat, Jan 05, 2019 at 09:51:31AM +0100, Richard Biener wrote: > > >+ if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE > > >(arg0))) > > >+ { > > >+ if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE > > >+ || !TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg0))) > > >+ type = TREE_TYPE (lhs); > > >+ else > > >+ type = TREE_TYPE (arg0); > > > > This misses some comments. Presumably you want to avoid arithmetic with bool types (or generally non-mode precision types!?). > > Just for bool because the weird semantics it has. And do as few conversions > as possible. > > > >+ } > > >+ else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION > > >(TREE_TYPE (arg0))) > > >+ type = TREE_TYPE (lhs); > > >+ else > > >+ type = TREE_TYPE (arg0); > > >+ if (!TYPE_OVERFLOW_WRAPS (type)) > > >+ type = unsigned_type_for (type); > > > > Would doing this unconditionally simplify things? I think "optimizing" the - fwrapv case isn't worth it. > > I've originally meant to do it only if really needed but then got lazy. > > > >+ tree m = fold_convert (type, wide_int_to_tree (TREE_TYPE (lhs), > > >min)); > > >+ enum tree_code code; > > >+ if (tree_int_cst_lt (arg0, arg1)) > > >+ { > > >+ code = PLUS_EXPR; > > >+ m = int_const_binop (MINUS_EXPR, fold_convert (type, arg0), m); > > >+ } > > >+ else > > >+ { > > >+ code = MINUS_EXPR; > > >+ m = int_const_binop (PLUS_EXPR, fold_convert (type, arg0), m); > > >+ } > > > > Delay wide-int to tree conversion until here. > > But by doing these computations on wide-int properly it appears it isn't > that hard to do. > > Essentially, after conversion to type, lhs is known to be in [min, min+1] > range and we either want to perform lhs + a or a - lhs. > If it is in signed type, we need to verify it doesn't overflow, so if > a is non-negative, make sure (min+1) + a doesn't overflow and if a > is negative, make sure min + a doesn't overflow. Similarly, for > a - lhs case, if min (and min+1) are non-negative, make sure a - (min+1) > doesn't overflow, and if min is negative (min+1 in that case could be > negative or 0), make sure a - min doesn't overflow. > > Ok for trunk if it passes bootstrap/regtest? OK. Thanks, Richard. > I guess I should add more testcases that test these corner cases, > the boundary cases of overflowing/not overflowing and different precisions > of the two types. > > 2019-01-05 Jakub Jelinek <jakub@redhat.com> > > PR tree-optimization/88676 > * tree-ssa-phiopt.c (two_value_replacement): New function. > (tree_ssa_phiopt_worker): Call it. > > * gcc.dg/tree-ssa/pr88676.c: New test. > * gcc.dg/pr88676.c: New test. > * gcc.dg/tree-ssa/pr15826.c: Just verify there is no goto, > allow &. > > --- gcc/tree-ssa-phiopt.c.jj 2019-01-04 18:53:11.315322371 +0100 > +++ gcc/tree-ssa-phiopt.c 2019-01-05 13:04:38.185082743 +0100 > @@ -48,6 +48,8 @@ along with GCC; see the file COPYING3. > #include "case-cfn-macros.h" > > static unsigned int tree_ssa_phiopt_worker (bool, bool, bool); > +static bool two_value_replacement (basic_block, basic_block, edge, gphi *, > + tree, tree); > static bool conditional_replacement (basic_block, basic_block, > edge, edge, gphi *, tree, tree); > static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree, > @@ -332,8 +334,11 @@ tree_ssa_phiopt_worker (bool do_store_el > } > > /* Do the replacement of conditional if it can be done. */ > - if (!early_p > - && conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) > + if (two_value_replacement (bb, bb1, e2, phi, arg0, arg1)) > + cfgchanged = true; > + else if (!early_p > + && conditional_replacement (bb, bb1, e1, e2, phi, > + arg0, arg1)) > cfgchanged = true; > else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) > cfgchanged = true; > @@ -572,6 +577,142 @@ factor_out_conditional_conversion (edge > return newphi; > } > > +/* Optimize > + # x_5 in range [cst1, cst2] where cst2 = cst1 + 1 > + if (x_5 op cstN) # where op is == or != and N is 1 or 2 > + goto bb3; > + else > + goto bb4; > + bb3: > + bb4: > + # r_6 = PHI<cst3(2), cst4(3)> # where cst3 == cst4 + 1 or cst4 == cst3 + 1 > + > + to r_6 = x_5 + (min (cst3, cst4) - cst1) or > + r_6 = (min (cst3, cst4) + cst1) - x_5 depending on op, N and which > + of cst3 and cst4 is smaller. */ > + > +static bool > +two_value_replacement (basic_block cond_bb, basic_block middle_bb, > + edge e1, gphi *phi, tree arg0, tree arg1) > +{ > + /* Only look for adjacent integer constants. */ > + if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0)) > + || !INTEGRAL_TYPE_P (TREE_TYPE (arg1)) > + || TREE_CODE (arg0) != INTEGER_CST > + || TREE_CODE (arg1) != INTEGER_CST > + || (tree_int_cst_lt (arg0, arg1) > + ? wi::to_widest (arg0) + 1 != wi::to_widest (arg1) > + : wi::to_widest (arg1) + 1 != wi::to_widest (arg1))) > + return false; > + > + if (!empty_block_p (middle_bb)) > + return false; > + > + gimple *stmt = last_stmt (cond_bb); > + tree lhs = gimple_cond_lhs (stmt); > + tree rhs = gimple_cond_rhs (stmt); > + > + if (TREE_CODE (lhs) != SSA_NAME > + || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)) > + || TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE > + || TREE_CODE (rhs) != INTEGER_CST) > + return false; > + > + switch (gimple_cond_code (stmt)) > + { > + case EQ_EXPR: > + case NE_EXPR: > + break; > + default: > + return false; > + } > + > + wide_int min, max; > + if (get_range_info (lhs, &min, &max) != VR_RANGE > + || min + 1 != max > + || (wi::to_wide (rhs) != min > + && wi::to_wide (rhs) != max)) > + return false; > + > + /* We need to know which is the true edge and which is the false > + edge so that we know when to invert the condition below. */ > + edge true_edge, false_edge; > + extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); > + if ((gimple_cond_code (stmt) == EQ_EXPR) > + ^ (wi::to_wide (rhs) == max) > + ^ (e1 == false_edge)) > + std::swap (arg0, arg1); > + > + tree type; > + if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE (arg0))) > + { > + /* Avoid performing the arithmetics in bool type which has different > + semantics, otherwise prefer unsigned types from the two with > + the same precision. */ > + if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE > + || !TYPE_UNSIGNED (TREE_TYPE (arg0))) > + type = TREE_TYPE (lhs); > + else > + type = TREE_TYPE (arg0); > + } > + else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION (TREE_TYPE (arg0))) > + type = TREE_TYPE (lhs); > + else > + type = TREE_TYPE (arg0); > + > + min = wide_int::from (min, TYPE_PRECISION (type), > + TYPE_SIGN (TREE_TYPE (lhs))); > + wide_int a = wide_int::from (wi::to_wide (arg0), TYPE_PRECISION (type), > + TYPE_SIGN (TREE_TYPE (arg0))); > + enum tree_code code; > + wi::overflow_type ovf; > + if (tree_int_cst_lt (arg0, arg1)) > + { > + code = PLUS_EXPR; > + a -= min; > + if (!TYPE_UNSIGNED (type)) > + { > + /* lhs is known to be in range [min, min+1] and we want to add a > + to it. Check if that operation can overflow for those 2 values > + and if yes, force unsigned type. */ > + wi::add (min + (wi::neg_p (a) ? 0 : 1), a, SIGNED, &ovf); > + if (ovf) > + type = unsigned_type_for (type); > + } > + } > + else > + { > + code = MINUS_EXPR; > + a += min; > + if (!TYPE_UNSIGNED (type)) > + { > + /* lhs is known to be in range [min, min+1] and we want to subtract > + it from a. Check if that operation can overflow for those 2 > + values and if yes, force unsigned type. */ > + wi::sub (a, min + (wi::neg_p (min) ? 0 : 1), SIGNED, &ovf); > + if (ovf) > + type = unsigned_type_for (type); > + } > + } > + > + tree arg = wide_int_to_tree (type, a); > + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); > + if (!useless_type_conversion_p (type, TREE_TYPE (lhs))) > + lhs = gimplify_build1 (&gsi, NOP_EXPR, type, lhs); > + tree new_rhs; > + if (code == PLUS_EXPR) > + new_rhs = gimplify_build2 (&gsi, PLUS_EXPR, type, lhs, arg); > + else > + new_rhs = gimplify_build2 (&gsi, MINUS_EXPR, type, arg, lhs); > + if (!useless_type_conversion_p (TREE_TYPE (arg0), type)) > + new_rhs = gimplify_build1 (&gsi, NOP_EXPR, TREE_TYPE (arg0), new_rhs); > + > + replace_phi_edge_with_variable (cond_bb, e1, phi, new_rhs); > + > + /* Note that we optimized this PHI. */ > + return true; > +} > + > /* The function conditional_replacement does the main work of doing the > conditional replacement. Return true if the replacement is done. > Otherwise return false. > --- gcc/testsuite/gcc.dg/tree-ssa/pr88676.c.jj 2019-01-05 12:25:32.463958539 +0100 > +++ gcc/testsuite/gcc.dg/tree-ssa/pr88676.c 2019-01-05 12:25:32.463958539 +0100 > @@ -0,0 +1,133 @@ > +/* PR tree-optimization/88676 */ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > +/* { dg-final { scan-tree-dump-not " = PHI <" "optimized" } } */ > + > +void bar (int, int, int); > + > +__attribute__((noipa)) int > +f1 (unsigned x) > +{ > + int r; > + if (x >= 2) > + __builtin_unreachable (); > + switch (x) > + { > + case 0: > + r = 1; > + break; > + case 1: > + r = 2; > + break; > + default: > + r = 0; > + break; > + } > + return r; > +} > + > +__attribute__((noipa)) void > +f2 (int x) > +{ > + int y; > + x = (x & 1) + 98; > + if (x != 98) > + y = 115; > + else > + y = 116; > + bar (x, y, 116); > +} > + > +__attribute__((noipa)) void > +f3 (int x) > +{ > + int y; > + x = (x & 1) + 98; > + if (x == 98) > + y = 115; > + else > + y = 116; > + bar (x, y, 115); > +} > + > +__attribute__((noipa)) void > +f4 (int x) > +{ > + int y; > + x = (x & 1) + 98; > + if (x != 99) > + y = 115; > + else > + y = 116; > + bar (x, y, 115); > +} > + > +__attribute__((noipa)) void > +f5 (int x) > +{ > + int y; > + x = (x & 1) + 98; > + if (x == 99) > + y = 115; > + else > + y = 116; > + bar (x, y, 116); > +} > + > +__attribute__((noipa)) void > +f6 (int x) > +{ > + int y; > + x = (x & 1) + 98; > + if (x != 98) > + y = 116; > + else > + y = 115; > + bar (x, y, 115); > +} > + > +__attribute__((noipa)) void > +f7 (int x) > +{ > + int y; > + x = (x & 1) + 98; > + if (x == 98) > + y = 116; > + else > + y = 115; > + bar (x, y, 116); > +} > + > +__attribute__((noipa)) void > +f8 (int x) > +{ > + int y; > + x = (x & 1) + 98; > + if (x != 99) > + y = 116; > + else > + y = 115; > + bar (x, y, 116); > +} > + > +__attribute__((noipa)) void > +f9 (int x) > +{ > + int y; > + x = (x & 1) + 98; > + if (x == 99) > + y = 116; > + else > + y = 115; > + bar (x, y, 115); > +} > + > +__attribute__((noipa)) int > +f10 (int x) > +{ > + x = (x & 1) + 36; > + if (x == 36) > + return 85; > + else > + return 84; > +} > --- gcc/testsuite/gcc.dg/pr88676.c.jj 2019-01-05 12:25:32.463958539 +0100 > +++ gcc/testsuite/gcc.dg/pr88676.c 2019-01-05 12:25:32.463958539 +0100 > @@ -0,0 +1,48 @@ > +/* PR tree-optimization/88676 */ > +/* { dg-do run } */ > +/* { dg-options "-O2" } */ > + > +#include "tree-ssa/pr88676.c" > + > +__attribute__((noipa)) void > +bar (int x, int y, int z) > +{ > + if (z != 115 && z != 116) > + __builtin_abort (); > + if (x == 98) > + { > + if (y != z) > + __builtin_abort (); > + } > + else if (x != 99) > + __builtin_abort (); > + else if (z == 115) > + { > + if (y != 116) > + __builtin_abort (); > + } > + else if (y != 115) > + __builtin_abort (); > +} > + > +int > +main () > +{ > + if (f1 (0) != 1 || f1 (1) != 2) > + __builtin_abort (); > + int i; > + for (i = -12; i < 12; i++) > + { > + f2 (i); > + f3 (i); > + f4 (i); > + f5 (i); > + f6 (i); > + f7 (i); > + f8 (i); > + f9 (i); > + if (f10 (i) != ((i & 1) ? 84 : 85)) > + __builtin_abort (); > + } > + return 0; > +} > --- gcc/testsuite/gcc.dg/tree-ssa/pr15826.c.jj 2016-02-27 07:41:54.377920386 +0100 > +++ gcc/testsuite/gcc.dg/tree-ssa/pr15826.c 2019-01-05 12:25:32.463958539 +0100 > @@ -33,4 +33,4 @@ andrew (struct s *p) > return i; > } > > -/* { dg-final { scan-tree-dump-times " & | goto " 0 "optimized" } } */ > +/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */ > > > Jakub > > -- Richard Biener <rguenther@suse.de> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg) ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2019-01-07 8:10 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-01-04 22:49 [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676) Jakub Jelinek 2019-01-05 8:51 ` Richard Biener 2019-01-05 12:18 ` [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676, take 2) Jakub Jelinek 2019-01-06 10:33 ` Jakub Jelinek 2019-01-07 8:10 ` Richard Biener
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).