[committed][PATCH] Change order of processing blocks/threads in tree-ssa-threadupdate.c

[committed][PATCH] Change order of processing blocks/threads in tree-ssa-threadupdate.c

[Jeff Law]

With my local patches to remove jump threading from VRP I was seeing a
fairly obvious jump threading path left in the CFG after DOM.  This
missed jump thread ultimately caused a false positive uninitialized warning.

Interestingly enough when I looked at the dumps it appeared DOM was
finding the appropriate threads, the threads weren't being cancelled and
we weren't doing any undesirable duplications for joiners.

What was happening is we had these two jump threading paths

  A: (190, 192) (192, 194)
  B: (192, 194) (194, 202)

These are simple jump threading paths.  No joiners or empty block skipping.

The key here is that the target edge of path A is the starting edge of
path B and that path A starts at a block with a smaller index.  There's
a variety of reasons, mostly due to limitations in the duplication and
ssa updating code that may prevent this from being a single jump
threading path.  Anyway...

So we process A first.  That creates a duplicate of 192, removes the
control statement in the duplicate and wires the duplicate to reach 194.
 But note that we already know that if we traverse 192->194, then we
must reach 202.  So this new edge 192'->194 is actually threadable too,
but we're not going to see it until the next DOM pass.

Obviously we'd prefer to just DTRT and not leave the jump thread in the
IL.  That's easily accomplished by handling non-loop jump threads in a
post-order traversal

When we do that, we'll first handle thread path B which will redirect
the 192->194 edge to 192->194' and the right things "just happen" when
we process thread path A and we avoid the false positive uninit warning.


Bootstrapped and regression tested on x86_64.  Wstringop-truncation is
ping-ponging, but not due to this patch AFAICT.  Also verified by visual
inspection that the first DOM pass fully threaded the code in question
when using a local branch that has my removal of threading from tree-vrp
patches installed and bootstrapping that branch.

Installing on the trunk.

Jeff

Re: [committed][PATCH] Change order of processing blocks/threads in tree-ssa-threadupdate.c

[Aldy Hernandez]

On 11/14/2017 10:46 PM, Jeff Law wrote:
> With my local patches to remove jump threading from VRP I was seeing a
> fairly obvious jump threading path left in the CFG after DOM.  This
> missed jump thread ultimately caused a false positive uninitialized warning.

This wouldn't be uninit-pred-[68]* or some such, which I also trigger 
when messing around with the backwards threader ??.

> ping-ponging, but not due to this patch AFAICT.  Also verified by visual
> inspection that the first DOM pass fully threaded the code in question
> when using a local branch that has my removal of threading from tree-vrp
> patches installed and bootstrapping that branch.

If DOM dumps the threads to the dump file you may want to bake that test 
with some GIMPLE FE test.

> Installing on the trunk.

You forgot to attach the patch :).

Aldy

Re: [committed][PATCH] Change order of processing blocks/threads in tree-ssa-threadupdate.c

[Jeff Law]

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

On 11/15/2017 12:57 AM, Aldy Hernandez wrote:
> 
> 
> On 11/14/2017 10:46 PM, Jeff Law wrote:
>> With my local patches to remove jump threading from VRP I was seeing a
>> fairly obvious jump threading path left in the CFG after DOM.  This
>> missed jump thread ultimately caused a false positive uninitialized
>> warning.
> 
> This wouldn't be uninit-pred-[68]* or some such, which I also trigger
> when messing around with the backwards threader ??.
Nope.  It was expand_expr_real_1 from expr.c.  That's also why there
wasn't a testcase included.  Culling that down to something reasonable
was going to be, umm, painful.

There's a slight chance it'd help the case you're referring to, but I
doubt it.

> 
>> ping-ponging, but not due to this patch AFAICT.  Also verified by visual
>> inspection that the first DOM pass fully threaded the code in question
>> when using a local branch that has my removal of threading from tree-vrp
>> patches installed and bootstrapping that branch.
> 
> If DOM dumps the threads to the dump file you may want to bake that test
> with some GIMPLE FE test.
> 
>> Installing on the trunk.
> 
> You forgot to attach the patch :).
Seems like I botched both submissions from that night.  I blame nyquil.


Jeff

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

commit b0915eb6736b70306ccc4f8498aeb25c77c29c7f
Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Wed Nov 15 03:45:03 2017 +0000

            * tree-ssa-threadupdate.c (thread_through_all_blocks): Thread
            blocks is post order.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@254752 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 9cba109ec59..c404eb8e5a7 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,8 @@
+2017-11-14  Jeff Law  <law@redhat.com>
+
+	* tree-ssa-threadupdate.c (thread_through_all_blocks): Thread
+	blocks is post order.
+
 2017-11-15  Alexandre Oliva <aoliva@redhat.com>
 
 	* dumpfile.h (TDF_COMPARE_DEBUG): New.
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 3d3aeab2a66..045905eceb7 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2174,7 +2174,6 @@ thread_through_all_blocks (bool may_peel_loop_headers)
 {
   bool retval = false;
   unsigned int i;
-  bitmap_iterator bi;
   struct loop *loop;
   auto_bitmap threaded_blocks;
 
@@ -2278,14 +2277,33 @@ thread_through_all_blocks (bool may_peel_loop_headers)
 
   initialize_original_copy_tables ();
 
-  /* First perform the threading requests that do not affect
-     loop structure.  */
-  EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi)
-    {
-      basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
+  /* The order in which we process jump threads can be important.
+
+     Consider if we have two jump threading paths A and B.  If the
+     target edge of A is the starting edge of B and we thread path A
+     first, then we create an additional incoming edge into B->dest that
+     we can not discover as a jump threading path on this iteration.
+
+     If we instead thread B first, then the edge into B->dest will have
+     already been redirected before we process path A and path A will
+     natually, with no further work, target the redirected path for B.
 
-      if (EDGE_COUNT (bb->preds) > 0)
-	retval |= thread_block (bb, true);
+     An post-order is sufficient here.  Compute the ordering first, then
+     process the blocks.  */
+  if (!bitmap_empty_p (threaded_blocks))
+    {
+      int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+      unsigned int postorder_num = post_order_compute (postorder, false, false);
+      for (unsigned int i = 0; i < postorder_num; i++)
+	{
+	  unsigned int indx = postorder[i];
+	  if (bitmap_bit_p (threaded_blocks, indx))
+	    {
+	      basic_block bb = BASIC_BLOCK_FOR_FN (cfun, indx);
+	      retval |= thread_block (bb, true);
+	    }
+	}
+      free (postorder);
     }
 
   /* Then perform the threading through loop headers.  We start with the