[PATCH][PR tree-optimization/64823] Handle threading through blocks with PHIs, but no statements

[PATCH][PR tree-optimization/64823] Handle threading through blocks with PHIs, but no statements

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 1097 bytes --]


Generally a block with PHIs, but no statements will be optimized away; 
however, if the sole successor is a loop header, then such blocks will 
not be optimized away.

We want to be able to thread through those blocks as sometimes we will 
be able to thread from outside the loop to the loop exit, thus bypassing 
the loop entirely on one or more paths.

It's also important to thread these cases so avoid false positive 
warnings, such as the one found in the testcase for this PR.

Basically three things need to happen to fix this PR.  First, the 
routine that determines what blocks are potentially threadable needs to 
be aware of this slightly special case.

Second, the threading code did not distinguish between a block with no 
statements and a block where we did not process all the statements.

Finally, VRP has a biglet in that it'll ICE if we have a potentially 
threadable block with no statements.

This patch addresses all three issues and fixes the false positive 
warning from this PR.

Bootstrapped & regression tested on x86_64-unknown-linux-gnu and 
installed on the trunk.


[-- Attachment #2: P2 --]
[-- Type: text/plain, Size: 4704 bytes --]

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index f36e16c..a574c2b 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,12 @@
 2015-02-13  Jeff Law  <law@redhat.com>
 
+	PR tree-optimization/64823
+	* tree-vrp.c (identify_jump_threads): Handle blocks with no statements.
+	* tree-ssa-threadedge.c (potentially_threadable_block): Allow
+	threading through blocks with PHIs, but no statements.
+	(thread_through_normal_block): Distinguish between blocks where
+	we did not process all the statements and blocks with no statements.
+
 	PR rtl-optimization/47477
 	* match.pd (convert (plus/minus (convert @0) (convert @1): New
 	simplifier to narrow arithmetic.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 2fe9698..f700bb1 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,8 @@
 2015-02-13  Jeff Law  <law@redhat.com>
 
+	PR tree-optimization/64823
+	gcc.dg/uninit-20.c: New test.
+
 	PR rtl-optimization/47477
 	* gcc.dg/tree-ssa/pr47477.c: New test.
 
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 4f83991..7187d06 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -110,6 +110,15 @@ potentially_threadable_block (basic_block bb)
 {
   gimple_stmt_iterator gsi;
 
+  /* Special case.  We can get blocks that are forwarders, but are
+     not optimized away because they forward from outside a loop
+     to the loop header.   We want to thread through them as we can
+     sometimes thread to the loop exit, which is obviously profitable. 
+     the interesting case here is when the block has PHIs.  */
+  if (gsi_end_p (gsi_start_nondebug_bb (bb))
+      && !gsi_end_p (gsi_start_phis (bb)))
+    return true;
+  
   /* If BB has a single successor or a single predecessor, then
      there is no threading opportunity.  */
   if (single_succ_p (bb) || single_pred_p (bb))
@@ -1281,16 +1290,32 @@ thread_through_normal_block (edge e,
     = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify,
 							*backedge_seen_p);
 
-  /* If we didn't look at all the statements, the most likely reason is
-     there were too many and thus duplicating this block is not profitable.
+  /* There's two reasons STMT might be null, and distinguishing
+     between them is important.
 
-     Also note if we do not look at all the statements, then we may not
-     have invalidated equivalences that are no longer valid if we threaded
-     around a loop.  Thus we must signal to our caller that this block
-     is not suitable for use as a joiner in a threading path.  */
+     First the block may not have had any statements.  For example, it
+     might have some PHIs and unconditionally transfer control elsewhere.
+     Such blocks are suitable for jump threading, particularly as a
+     joiner block.
+
+     The second reason would be if we did not process all the statements
+     in the block (because there were too many to make duplicating the
+     block profitable.   If we did not look at all the statements, then
+     we may not have invalidated everything needing invalidation.  Thus
+     we must signal to our caller that this block is not suitable for
+     use as a joiner in a threading path.  */
   if (!stmt)
-    return -1;
+    {
+      /* First case.  The statement simply doesn't have any instructions, but
+	 does have PHIs.  */
+      if (gsi_end_p (gsi_start_nondebug_bb (e->dest))
+	  && !gsi_end_p (gsi_start_phis (e->dest)))
+	return 0;
 
+      /* Second case.  */
+      return -1;
+    }
+  
   /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
      will be taken.  */
   if (gimple_code (stmt) == GIMPLE_COND
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index dad1830..7367684 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10181,8 +10181,15 @@ identify_jump_threads (void)
       /* We're basically looking for a switch or any kind of conditional with
 	 integral or pointer type arguments.  Note the type of the second
 	 argument will be the same as the first argument, so no need to
-	 check it explicitly.  */
-      if (gimple_code (last) == GIMPLE_SWITCH
+	 check it explicitly. 
+
+	 We also handle the case where there are no statements in the
+	 block.  This come up with forwarder blocks that are not
+	 optimized away because they lead to a loop header.  But we do
+	 want to thread through them as we can sometimes thread to the
+	 loop exit which is obviously profitable.  */
+      if (!last
+	  || gimple_code (last) == GIMPLE_SWITCH
 	  || (gimple_code (last) == GIMPLE_COND
       	      && TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
 	      && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))

Re: [PATCH][PR tree-optimization/64823] Handle threading through blocks with PHIs, but no statements

[Jeff Law]

On 02/13/15 23:12, Jack Howarth wrote:
> This also breaks the bootstrap on x86_64-apple-darwin14 due to a
> similar stage 2/3 comparison failure.
Thanks.  I'm pretty sure I've got the root cause of both of these 
failures.  There's a gsi_last_bb in some existing code that really needs 
to be changed into gsi_last_nondebug_bb.

It didn't matter before because a block ending in debug statements was 
never considered potentially threadable by VRP.  However it matters with 
my change because we're allowing threading through such blocks.  Strange 
that it didn't show up in my tests.  But it's definitely a real issue.

Jeff

Re: [PATCH][PR tree-optimization/64823] Handle threading through blocks with PHIs, but no statements

[Jack Howarth]

This also breaks the bootstrap on x86_64-apple-darwin14 due to a
similar stage 2/3 comparison failure.

On Fri, Feb 13, 2015 at 6:01 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Fri, Feb 13, 2015 at 1:11 PM, Jeff Law <law@redhat.com> wrote:
>> This time with the right patch file.
>>
>> commit 48087ce0b383457b5919cbcc2ce1a5e1aaa264c3
>> Author: Jeff Law <law@redhat.com>
>> Date:   Fri Feb 13 14:08:06 2015 -0700
>>
>>         PR tree-optimization/64823
>>         * tree-vrp.c (identify_jump_threads): Handle blocks with no
>> statements.
>>         * tree-ssa-threadedge.c (potentially_threadable_block): Allow
>>         threading through blocks with PHIs, but no statements.
>>         (thread_through_normal_block): Distinguish between blocks where
>>         we did not process all the statements and blocks with no statements.
>>
>>         PR tree-optimization/64823
>>         gcc.dg/uninit-20.c: New test.
>>
>
> This caused:
>
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65060
>
>
> --
> H.J.

Re: [PATCH][PR tree-optimization/64823] Handle threading through blocks with PHIs, but no statements

[H.J. Lu]

On Fri, Feb 13, 2015 at 1:11 PM, Jeff Law <law@redhat.com> wrote:
> This time with the right patch file.
>
> commit 48087ce0b383457b5919cbcc2ce1a5e1aaa264c3
> Author: Jeff Law <law@redhat.com>
> Date:   Fri Feb 13 14:08:06 2015 -0700
>
>         PR tree-optimization/64823
>         * tree-vrp.c (identify_jump_threads): Handle blocks with no
> statements.
>         * tree-ssa-threadedge.c (potentially_threadable_block): Allow
>         threading through blocks with PHIs, but no statements.
>         (thread_through_normal_block): Distinguish between blocks where
>         we did not process all the statements and blocks with no statements.
>
>         PR tree-optimization/64823
>         gcc.dg/uninit-20.c: New test.
>

This caused:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65060


-- 
H.J.

[PATCH][PR tree-optimization/64823] Handle threading through blocks with PHIs, but no statements

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 37 bytes --]

This time with the right patch file.

[-- Attachment #2: P --]
[-- Type: text/plain, Size: 5961 bytes --]

commit 48087ce0b383457b5919cbcc2ce1a5e1aaa264c3
Author: Jeff Law <law@redhat.com>
Date:   Fri Feb 13 14:08:06 2015 -0700

    	PR tree-optimization/64823
    	* tree-vrp.c (identify_jump_threads): Handle blocks with no statements.
    	* tree-ssa-threadedge.c (potentially_threadable_block): Allow
    	threading through blocks with PHIs, but no statements.
    	(thread_through_normal_block): Distinguish between blocks where
    	we did not process all the statements and blocks with no statements.
    
    	PR tree-optimization/64823
    	gcc.dg/uninit-20.c: New test.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index f36e16c..a574c2b 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,12 @@
 2015-02-13  Jeff Law  <law@redhat.com>
 
+	PR tree-optimization/64823
+	* tree-vrp.c (identify_jump_threads): Handle blocks with no statements.
+	* tree-ssa-threadedge.c (potentially_threadable_block): Allow
+	threading through blocks with PHIs, but no statements.
+	(thread_through_normal_block): Distinguish between blocks where
+	we did not process all the statements and blocks with no statements.
+
 	PR rtl-optimization/47477
 	* match.pd (convert (plus/minus (convert @0) (convert @1): New
 	simplifier to narrow arithmetic.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 2fe9698..f700bb1 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,8 @@
 2015-02-13  Jeff Law  <law@redhat.com>
 
+	PR tree-optimization/64823
+	gcc.dg/uninit-20.c: New test.
+
 	PR rtl-optimization/47477
 	* gcc.dg/tree-ssa/pr47477.c: New test.
 
diff --git a/gcc/testsuite/gcc.dg/uninit-20.c b/gcc/testsuite/gcc.dg/uninit-20.c
new file mode 100644
index 0000000..12001ae
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-20.c
@@ -0,0 +1,18 @@
+/* Spurious uninitialized variable warnings, from gdb */
+/* { dg-do compile } */
+/* { dg-options "-O2 -Wuninitialized" } */
+struct os { struct o *o; };
+struct o { struct o *next; struct os *se; };
+void f(struct o *o){
+  struct os *s;
+  if(o) s = o->se;
+  while(o && s == o->se){
+    s++; // here `o' is non-zero and thus s is initialized
+    s == o->se  // `?' is essential, `if' does not trigger the warning
+      ? (o = o->next, o ? s = o->se : 0)
+      : 0;
+  }
+}
+
+
+
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 4f83991..7187d06 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -110,6 +110,15 @@ potentially_threadable_block (basic_block bb)
 {
   gimple_stmt_iterator gsi;
 
+  /* Special case.  We can get blocks that are forwarders, but are
+     not optimized away because they forward from outside a loop
+     to the loop header.   We want to thread through them as we can
+     sometimes thread to the loop exit, which is obviously profitable. 
+     the interesting case here is when the block has PHIs.  */
+  if (gsi_end_p (gsi_start_nondebug_bb (bb))
+      && !gsi_end_p (gsi_start_phis (bb)))
+    return true;
+  
   /* If BB has a single successor or a single predecessor, then
      there is no threading opportunity.  */
   if (single_succ_p (bb) || single_pred_p (bb))
@@ -1281,16 +1290,32 @@ thread_through_normal_block (edge e,
     = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify,
 							*backedge_seen_p);
 
-  /* If we didn't look at all the statements, the most likely reason is
-     there were too many and thus duplicating this block is not profitable.
+  /* There's two reasons STMT might be null, and distinguishing
+     between them is important.
 
-     Also note if we do not look at all the statements, then we may not
-     have invalidated equivalences that are no longer valid if we threaded
-     around a loop.  Thus we must signal to our caller that this block
-     is not suitable for use as a joiner in a threading path.  */
+     First the block may not have had any statements.  For example, it
+     might have some PHIs and unconditionally transfer control elsewhere.
+     Such blocks are suitable for jump threading, particularly as a
+     joiner block.
+
+     The second reason would be if we did not process all the statements
+     in the block (because there were too many to make duplicating the
+     block profitable.   If we did not look at all the statements, then
+     we may not have invalidated everything needing invalidation.  Thus
+     we must signal to our caller that this block is not suitable for
+     use as a joiner in a threading path.  */
   if (!stmt)
-    return -1;
+    {
+      /* First case.  The statement simply doesn't have any instructions, but
+	 does have PHIs.  */
+      if (gsi_end_p (gsi_start_nondebug_bb (e->dest))
+	  && !gsi_end_p (gsi_start_phis (e->dest)))
+	return 0;
 
+      /* Second case.  */
+      return -1;
+    }
+  
   /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
      will be taken.  */
   if (gimple_code (stmt) == GIMPLE_COND
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index dad1830..7367684 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10181,8 +10181,15 @@ identify_jump_threads (void)
       /* We're basically looking for a switch or any kind of conditional with
 	 integral or pointer type arguments.  Note the type of the second
 	 argument will be the same as the first argument, so no need to
-	 check it explicitly.  */
-      if (gimple_code (last) == GIMPLE_SWITCH
+	 check it explicitly. 
+
+	 We also handle the case where there are no statements in the
+	 block.  This come up with forwarder blocks that are not
+	 optimized away because they lead to a loop header.  But we do
+	 want to thread through them as we can sometimes thread to the
+	 loop exit which is obviously profitable.  */
+      if (!last
+	  || gimple_code (last) == GIMPLE_SWITCH
 	  || (gimple_code (last) == GIMPLE_COND
       	      && TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
 	      && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))