Re: [PATCH PR71437/V2]Simplify cond with assertions in threading

[Bin.Cheng]

On Fri, Feb 17, 2017 at 3:40 AM, Jeff Law  wrote:
> On 02/14/2017 03:05 AM, Bin Cheng wrote:
>>
>> Hi,
>> This is the second try fixing PR71437.  The old version patch tried to fix
>> issue in VRP but it requires further non-trivial change in VRP,
>> specifically, to better support variable value ranges.  This is not
>> appropriate at stage 4.  Alternatively, this patch tries to fix issue by
>> improving threading.  It additionally simplifies condition by using
>> assertion conditions.
>>
>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>
>> Thanks,
>> bin
>>
>> 2017-02-13  Bin Cheng  
>>
>> PR tree-optimization/71437
>> * tree-ssa-loop-niter.c (tree_simplify_using_condition): Only
>> expand condition if new parameter says so.  Also change it to
>> global.
>> * tree-ssa-loop-niter.h (tree_simplify_using_condition): New
>> declaration.
>> * tree-ssa-threadedge.c (tree-ssa-loop-niter.h): New include file.
>> (simplify_control_stmt_condition_1): Simplify condition using
>> assert conditions.
>>
>> gcc/testsuite/ChangeLog
>> 2017-02-13  Bin Cheng  
>>
>> PR tree-optimization/71437
>> * gcc.dg/tree-ssa/pr71437.c: New test.
>>
> So following up.  We're not going to get anywhere using the ranges in VRP.
> As Bin noted in the V1 patch, VRP prefers a useless range with constant
> bounds when a symbolic range would be better.  Thus the callbacks into VRP
> are doomed to failure.
>
> Bin's patch works around this by using the ASSERT_EXPRs to recover the
> symbolic range.  So it's a bit of a hack, but not a terrible one.  If we
> want to continue this path, we might still look for ways to avoid
> simplify_using_condition.
>
> One idea would be to go ahead and record the equivalence from the
> ASSERT_EXPR into the expression hash table and use the expression hash table
> to simplify the condition.  We didn't have that ability in the past, but
> should now after the refactorings from last year.
>
> It's slightly related to some ideas I've got around tackling 78496.
>
> I'm in/out of the office for until the 27th semi-randomly.  I'll try to poke
> at this while on the road.
Thanks for helping, I will hold this patch and let you work out a
generic fix in threading.

Thanks,
bin
>
> Jeff
>
>

Re: [PATCH PR71437/V2]Simplify cond with assertions in threading

[Jeff Law]

On 02/14/2017 03:05 AM, Bin Cheng wrote:

Hi,
This is the second try fixing PR71437.  The old version patch tried to fix 
issue in VRP but it requires further non-trivial change in VRP, specifically, 
to better support variable value ranges.  This is not appropriate at stage 4.  
Alternatively, this patch tries to fix issue by improving threading.  It 
additionally simplifies condition by using assertion conditions.

Bootstrap and test on x86_64 and AArch64.  Is it OK?

Thanks,
bin

2017-02-13  Bin Cheng  

PR tree-optimization/71437
* tree-ssa-loop-niter.c (tree_simplify_using_condition): Only
expand condition if new parameter says so.  Also change it to
global.
* tree-ssa-loop-niter.h (tree_simplify_using_condition): New
declaration.
* tree-ssa-threadedge.c (tree-ssa-loop-niter.h): New include file.
(simplify_control_stmt_condition_1): Simplify condition using
assert conditions.

gcc/testsuite/ChangeLog
2017-02-13  Bin Cheng  

PR tree-optimization/71437
* gcc.dg/tree-ssa/pr71437.c: New test.

So following up.  We're not going to get anywhere using the ranges in 
VRP.  As Bin noted in the V1 patch, VRP prefers a useless range with 
constant bounds when a symbolic range would be better.  Thus the 
callbacks into VRP are doomed to failure.


Bin's patch works around this by using the ASSERT_EXPRs to recover the 
symbolic range.  So it's a bit of a hack, but not a terrible one.  If we 
want to continue this path, we might still look for ways to avoid 
simplify_using_condition.


One idea would be to go ahead and record the equivalence from the 
ASSERT_EXPR into the expression hash table and use the expression hash 
table to simplify the condition.  We didn't have that ability in the 
past, but should now after the refactorings from last year.


It's slightly related to some ideas I've got around tackling 78496.

I'm in/out of the office for until the 27th semi-randomly.  I'll try to 
poke at this while on the road.


Jeff

Re: [PATCH PR71437/V2]Simplify cond with assertions in threading

[Jeff Law]

On 02/16/2017 04:55 AM, Richard Biener wrote:

On Tue, Feb 14, 2017 at 11:05 AM, Bin Cheng  wrote:

Hi,
This is the second try fixing PR71437.  The old version patch tried to fix 
issue in VRP but it requires further non-trivial change in VRP, specifically, 
to better support variable value ranges.  This is not appropriate at stage 4.  
Alternatively, this patch tries to fix issue by improving threading.  It 
additionally simplifies condition by using assertion conditions.

Bootstrap and test on x86_64 and AArch64.  Is it OK?


Hmm.  So I'm not a big fan of tree_simplify_using_condition ;)  The
case in question for the PR
was an equivalent assert to the condition?  Thus basically
tree_simplify_using_condition (x <= 52, x <= 25)?

+  if (is_gimple_assign (def0)
+ && TREE_CODE (gimple_assign_rhs1 (def0)) == ASSERT_EXPR)

gimple_assign_rhs_code (def0) == ASSERT_EXPR

As you add a parameter to tree_simplify_using_condition you can as well fold
it into tree_simplify_using_condition_1.  And ideally I'd like to see us pass in
a decomposed toplevel expression to avoid

+ tree res = fold_build2 (cond_code, boolean_type_node,
+ assert_op0, assert_op1);

but I'm not sure that will work out ;)

So, in the end I wonder if we can fix this in threading w/o usign
tree_simplify_using_conditon
(the main issue with it I have is the extensive tree building it does).
Given that we've got a callback into VRP simplifiers, I'd think we ought 
to be able to avoid tree_simplify_using_condition.


jeff

Re: [PATCH PR71437/V2]Simplify cond with assertions in threading

[Jeff Law]

On 02/14/2017 03:05 AM, Bin Cheng wrote:

Hi,
This is the second try fixing PR71437.  The old version patch tried to fix 
issue in VRP but it requires further non-trivial change in VRP, specifically, 
to better support variable value ranges.  This is not appropriate at stage 4.  
Alternatively, this patch tries to fix issue by improving threading.  It 
additionally simplifies condition by using assertion conditions.

Bootstrap and test on x86_64 and AArch64.  Is it OK?

Thanks,
bin

2017-02-13  Bin Cheng  

PR tree-optimization/71437
* tree-ssa-loop-niter.c (tree_simplify_using_condition): Only
expand condition if new parameter says so.  Also change it to
global.
* tree-ssa-loop-niter.h (tree_simplify_using_condition): New
declaration.
* tree-ssa-threadedge.c (tree-ssa-loop-niter.h): New include file.
(simplify_control_stmt_condition_1): Simplify condition using
assert conditions.

gcc/testsuite/ChangeLog
2017-02-13  Bin Cheng  

PR tree-optimization/71437
* gcc.dg/tree-ssa/pr71437.c: New test.

Looking at this code for the first time in a long time, I wonder if the 
handling of ASSERT_EXPRs ought to move into the callback provided by 
VRP.  The code here has become rather convoluted.


Given I want to remove the instances of the threader called by VRP that 
cleanup may not be worth the effort.  Not sure.  Punting that decition 
to gcc-8.


I'm a bit surprised that this isn't detected by the callback into VRP. 
I'll take a peek at that next week.


Jeff

Re: [PATCH PR71437/V2]Simplify cond with assertions in threading

[Richard Biener]

On Tue, Feb 14, 2017 at 11:05 AM, Bin Cheng  wrote:
> Hi,
> This is the second try fixing PR71437.  The old version patch tried to fix 
> issue in VRP but it requires further non-trivial change in VRP, specifically, 
> to better support variable value ranges.  This is not appropriate at stage 4. 
>  Alternatively, this patch tries to fix issue by improving threading.  It 
> additionally simplifies condition by using assertion conditions.
>
> Bootstrap and test on x86_64 and AArch64.  Is it OK?

Hmm.  So I'm not a big fan of tree_simplify_using_condition ;)  The
case in question for the PR
was an equivalent assert to the condition?  Thus basically
tree_simplify_using_condition (x <= 52, x <= 25)?

+  if (is_gimple_assign (def0)
+ && TREE_CODE (gimple_assign_rhs1 (def0)) == ASSERT_EXPR)

gimple_assign_rhs_code (def0) == ASSERT_EXPR

As you add a parameter to tree_simplify_using_condition you can as well fold
it into tree_simplify_using_condition_1.  And ideally I'd like to see us pass in
a decomposed toplevel expression to avoid

+ tree res = fold_build2 (cond_code, boolean_type_node,
+ assert_op0, assert_op1);

but I'm not sure that will work out ;)

So, in the end I wonder if we can fix this in threading w/o usign
tree_simplify_using_conditon
(the main issue with it I have is the extensive tree building it does).

Richard.

> Thanks,
> bin
>
> 2017-02-13  Bin Cheng  
>
> PR tree-optimization/71437
> * tree-ssa-loop-niter.c (tree_simplify_using_condition): Only
> expand condition if new parameter says so.  Also change it to
> global.
> * tree-ssa-loop-niter.h (tree_simplify_using_condition): New
> declaration.
> * tree-ssa-threadedge.c (tree-ssa-loop-niter.h): New include file.
> (simplify_control_stmt_condition_1): Simplify condition using
> assert conditions.
>
> gcc/testsuite/ChangeLog
> 2017-02-13  Bin Cheng  
>
> PR tree-optimization/71437
> * gcc.dg/tree-ssa/pr71437.c: New test.

[PATCH PR71437/V2]Simplify cond with assertions in threading

[Bin Cheng]

Hi,
This is the second try fixing PR71437.  The old version patch tried to fix 
issue in VRP but it requires further non-trivial change in VRP, specifically, 
to better support variable value ranges.  This is not appropriate at stage 4.  
Alternatively, this patch tries to fix issue by improving threading.  It 
additionally simplifies condition by using assertion conditions.

Bootstrap and test on x86_64 and AArch64.  Is it OK?

Thanks,
bin

2017-02-13  Bin Cheng  

PR tree-optimization/71437
* tree-ssa-loop-niter.c (tree_simplify_using_condition): Only
expand condition if new parameter says so.  Also change it to
global.
* tree-ssa-loop-niter.h (tree_simplify_using_condition): New
declaration.
* tree-ssa-threadedge.c (tree-ssa-loop-niter.h): New include file.
(simplify_control_stmt_condition_1): Simplify condition using
assert conditions.

gcc/testsuite/ChangeLog
2017-02-13  Bin Cheng  

PR tree-optimization/71437
* gcc.dg/tree-ssa/pr71437.c: New test.diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71437.c 
b/gcc/testsuite/gcc.dg/tree-ssa/pr71437.c
new file mode 100644
index 000..66a5405
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71437.c
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-ffast-math -O3 -fdump-tree-vrp1-details" } */
+
+int I = 50, J = 50;
+int S, L;
+const int *pL;
+const int *pS;
+
+void bar (float, float);
+
+void foo (int K)
+{
+  int k, i, j;
+  static float LD, SD;
+  for (k = 0 ; k < K; k++)
+{
+for( i = 0 ; i < ( I - 1 ) ; i++ )
+{
+if( ( L < pL[i+1] ) && ( L >= pL[i] ) )
+  break ;
+}
+
+if( i == ( I - 1 ) )
+  L = pL[i] ;
+LD = (float)( L - pL[i] ) /
+(float)( pL[i + 1] - pL[i] ) ;
+
+for( j = 0 ; j < ( J-1 ) ; j++ )
+{
+if( ( S < pS[j+1] ) && ( S >= pS[j] ) )
+  break ;
+}
+
+if( j == ( J - 1 ) )
+  S = pS[j] ;
+SD = (float)( S - pS[j] ) /
+ (float)( pS[j + 1] - pS[j] ) ;
+
+   bar (LD, SD);
+}
+}
+/* { dg-final { scan-tree-dump-times "Threaded jump " 2 "vrp1" } } */
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index efcf3ed..52baad1 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -2057,12 +2057,14 @@ tree_simplify_using_condition_1 (tree cond, tree expr)
Wrapper around tree_simplify_using_condition_1 that ensures that chains
of simple operations in definitions of ssa names in COND are expanded,
so that things like casts or incrementing the value of the bound before
-   the loop do not cause us to fail.  */
+   the loop do not cause us to fail.  COND is expanded before simplifying
+   if EXPAND is true.  */
 
-static tree
-tree_simplify_using_condition (tree cond, tree expr)
+tree
+tree_simplify_using_condition (tree cond, tree expr, bool expand)
 {
-  cond = expand_simple_operations (cond);
+  if (expand)
+cond = expand_simple_operations (cond);
 
   return tree_simplify_using_condition_1 (cond, expr);
 }
diff --git a/gcc/tree-ssa-loop-niter.h b/gcc/tree-ssa-loop-niter.h
index b009857..4e572df 100644
--- a/gcc/tree-ssa-loop-niter.h
+++ b/gcc/tree-ssa-loop-niter.h
@@ -21,6 +21,7 @@ along with GCC; see the file COPYING3.  If not see
 #define GCC_TREE_SSA_LOOP_NITER_H
 
 extern tree expand_simple_operations (tree, tree = NULL);
+extern tree tree_simplify_using_condition (tree, tree, bool = true);
 extern tree simplify_using_initial_conditions (struct loop *, tree);
 extern bool loop_only_exit_p (const struct loop *, const_edge);
 extern bool number_of_iterations_exit (struct loop *, edge,
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 4949bfa..fa2891d 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -30,6 +30,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "cfgloop.h"
 #include "gimple-iterator.h"
 #include "tree-cfg.h"
+#include "tree-ssa-loop-niter.h"
 #include "tree-ssa-threadupdate.h"
 #include "params.h"
 #include "tree-ssa-scopedtables.h"
@@ -561,6 +562,46 @@ simplify_control_stmt_condition_1 (edge e,
   if (limit == 0)
 return NULL_TREE;
 
+  /* Simplify condition using assertion conditions.  */
+  if (handle_dominating_asserts
+  && TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
+{
+  tree assert_op0 = op0, assert_op1 = op1;
+  tree assert_cond0 = NULL_TREE, assert_cond1 = NULL_TREE;
+  gimple *def0 = SSA_NAME_DEF_STMT (op0), *def1 = SSA_NAME_DEF_STMT (op1);
+
+  if (is_gimple_assign (def0)
+ && TREE_CODE (gimple_assign_rhs1 (def0)) == ASSERT_EXPR)
+   {
+ assert_op0 = TREE_OPERAND (gimple_assign_rhs1 (def0), 0);
+ assert_cond0 = TREE_OPERAND (gimple_assign_rhs1 (def0), 1);
+   }
+  if (is_gimple_assign (def1)
+ &&