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

[Jeff Law <law at redhat dot com>]

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

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