[PATCH/RFC] Make loop-header-copying more aggressive, rerun before tree-if-conversion

[PATCH/RFC] Make loop-header-copying more aggressive, rerun before tree-if-conversion

[Alan Lawrence]

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

This example which I wrote to test ifconversion, currently fails to if-convert 
or vectorize:

int foo ()
{
   for (int i = 0; i < 32 ; i++)
     {
       int m = (a[i] & i) ? 5 : 4;
       b[i] = a[i] * m;
     }
}

...because jump-threading in dom1 rearranged the loop into a form that neither 
if-conversion nor vectorization would attempt. Discussion at 
https://gcc.gnu.org/ml/gcc/2015-04/msg00343.html lead to the suggestion that I 
should rerun loop-header copying (an earlier attempt to fix ifconversion, 
https://gcc.gnu.org/ml/gcc-patches/2015-04/msg01743.html, still did not enable 
vectorization.)

This patch does so (and makes slightly less conservative, to tackle the example 
above). I found I had to make this a separate pass, so that the phi nodes were 
cleaned up at the end of the pass before running tree_if_conversion. Also at 
this stage in the compiler (inside loop opts) it was not possible to run 
loop_optimizer_init+finalize, or other loop_optimizer data structures needed 
later would be deleted; hence, I have two nearly-but-not-quite-identical passes, 
the new "ch_vect" avoiding the init/finalize. I tried to tackle this with some 
C++ subclassing, which removes the duplication, but the result feels a little 
ugly; suggestions for any neater approach welcome.

This patch causes failure of the scan-tree-dump of dom2 in gcc.dg/ssa/pr21417.c. 
This looks for jump-threading to perform an optimization, but no longer finds 
the expected line in the log - as the loop-header-copying phase has already done 
an equivalent transformation *before* dom2. The final CFG is thus in the desired 
form, but I'm not sure how to determine this (scanning the CFG itself is very 
difficult, well beyond what we can do with regex, requiring looking at multiple 
lines and basic blocks). Can anyone advise? [The test issue can be worked around 
by preserving the old do_while_p logic for the first header-copying pass, and 
using the new logic only for the second, but this is more awkward inside the 
compiler, which feels wrong.]

Besides the new vect-ifcvt-11.c, the testsuite actually has a couple of other 
examples where this patch enables (undesired!) vectorization. I've dealt with 
these, but for the record:
	* gcc.dg/vect/slp-perm-7.c: the initialization loop in main, contained a check 
that input[i] < 200; this was already optimized out (because input[i] was set to 
i%256, where i<N with N #defined to 16), but that loop was not vectorized because:
/work/alalaw01/oban/srcfsf/gcc/gcc/testsuite/gcc.dg/vect/slp-perm-7.c:54:3: 
note: not vectorized: latch block not empty.
/work/alalaw01/oban/srcfsf/gcc/gcc/testsuite/gcc.dg/vect/slp-perm-7.c:54:3: 
note: bad loop form.

	* gcc.dg/vect/vect-strided-a-u16-i4.c: the main1() function has three loops; 
the first (initialization) has an 'if (y) abort() /* Avoid vectorization.  */'. 
However, the 'volatile int y = 0' this was meant to reference, is actually 
shadowed by a local non-volatile; the test is thus peeled off and absent from 
the body of the loop. The loop only avoided vectorization because of non-empty 
latch and bad loop form, as previous.

With this patch, both those loops now have good form, hence I have fixed both to 
check a global volatile to prevent these extraneous parts from being vectorized.

Tested with bootstrap + check-gcc on x86_64 and AArch64 (linux). As noted above, 
this causes a spurious PASS->FAIL of a scan-tree-dump test, which I'm unsure how 
to fix, but no other regressions.

gcc/ChangeLog:

	* tree-pass.h (make_pass_ch_vect): New.
	* passes.def: Add pass_ch_vect just before pass_if_conversion.

	* tree-ssa-loop-ch.c (do_while_loop_p): For single-exit loops,
	look for blocks with exit edge and code after them.
	(pass_data_ch_vect, class pass_ch_vect, make_pass_ch_vect): New.
	(class pass_ch): Extend pass_ch_vect.
	(pass_ch::execute): Move all but loop_optimizer_init/finalize to...
	(pass_ch_vect::execute): ...here.

	* tree-ssa-loop.c (pass_tree_loop_init::execute): Add flags
	LOOPS_HAVE_PREHEADERS and LOOPS_HAVE_SIMPLE_LATCHES.

gcc/testsuite/ChangeLog:

	* gcc.dg/vect/slp-perm-7.c (zero): New.
	(main): Test zero rather than input[i], to avoid vectorization.
	* gcc.dg/vect/vect-strided-a-u16-i4.c (main1): Narrow scope of x,y,z,w.
	of unsigned
	* gcc.dg/vect/vect-ifcvt-11.c: New.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: rerun-loop-ch.patch --]
[-- Type: text/x-patch; name=rerun-loop-ch.patch, Size: 7848 bytes --]

diff --git a/gcc/passes.def b/gcc/passes.def
index 1d598b2..87cfe2a 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -247,6 +247,7 @@ along with GCC; see the file COPYING3.  If not see
 	  PUSH_INSERT_PASSES_WITHIN (pass_parallelize_loops)
 	      NEXT_PASS (pass_expand_omp_ssa);
 	  POP_INSERT_PASSES ()
+	  NEXT_PASS (pass_ch_vect);
 	  NEXT_PASS (pass_if_conversion);
 	  /* pass_vectorize must immediately follow pass_if_conversion.
 	     Please do not add any other passes in between.  */
diff --git a/gcc/testsuite/gcc.dg/vect/slp-perm-7.c b/gcc/testsuite/gcc.dg/vect/slp-perm-7.c
index 6291096..e0ec55a 100644
--- a/gcc/testsuite/gcc.dg/vect/slp-perm-7.c
+++ b/gcc/testsuite/gcc.dg/vect/slp-perm-7.c
@@ -20,6 +20,8 @@
 
 #define N 16
 
+volatile int zero = 0;
+
 /* SLP with load permutation and loop-based vectorization.  */
 void foo (int *__restrict__ pInput, int *__restrict__ pOutput,
           int *__restrict__ pInput2, int *__restrict__ pOutput2)
@@ -57,7 +59,7 @@ int main (int argc, const char* argv[])
       input2[i] = i%256;
       output[i] = 0;
       output2[i] = 0;
-      if (input[i] > 200)
+      if (zero) /* Avoid vectorization.  */
         abort ();
     }
 
diff --git a/gcc/testsuite/gcc.dg/vect/vect-ifcvt-11.c b/gcc/testsuite/gcc.dg/vect/vect-ifcvt-11.c
new file mode 100644
index 0000000..53b139d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-ifcvt-11.c
@@ -0,0 +1,37 @@
+/* { dg-require-effective-target vect_condition } */
+/* { dg-require-effective-target vect_int } */
+
+#include "tree-vect.h"
+
+#define N 16
+
+extern void abort(void);
+
+int A[N] = {36, 39, 42, 45, 43, 32, 21, 12, 23, 34, 45, 56, 67, 78, 81, 11};
+int B[N] = {144,195,210,225,172,128,105,60, 92, 136,225,280,268,390,324,55};
+
+__attribute__((noinline))
+void foo ()
+{
+  for (int i = 0; i < N; i++)
+    {
+      int m = (A[i] & i) ? 5 : 4;
+      A[i] = A[i] * m;
+    }
+}
+
+int main ()
+{
+
+  check_vect ();
+  foo ();
+  /* check results:  */
+  for (int i = 0; i < N; i++)
+    if (A[i] != B[i])
+      abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-strided-a-u16-i4.c b/gcc/testsuite/gcc.dg/vect/vect-strided-a-u16-i4.c
index 68114a6..0656fb7 100644
--- a/gcc/testsuite/gcc.dg/vect/vect-strided-a-u16-i4.c
+++ b/gcc/testsuite/gcc.dg/vect/vect-strided-a-u16-i4.c
@@ -21,7 +21,6 @@ main1 ()
   s *ptr = arr;
   s res[N];
   int i;
-  unsigned short x, y, z, w;
 
   for (i = 0; i < N; i++)
     {
@@ -35,6 +34,7 @@ main1 ()
 
   for (i = 0; i < N; i++)
     {
+      unsigned short x, y, z, w;
       x = ptr->b - ptr->a;
       y = ptr->d - ptr->c;
       res[i].c = x + y;
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index bc8763d..cb0f986 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -379,6 +379,7 @@ extern gimple_opt_pass *make_pass_loop_prefetch (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_iv_optimize (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_tree_loop_done (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_ch (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_ch_vect (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_ccp (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_phi_only_cprop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_build_ssa (gcc::context *ctxt);
diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c
index c6441b8..0fb7155 100644
--- a/gcc/tree-ssa-loop-ch.c
+++ b/gcc/tree-ssa-loop-ch.c
@@ -140,6 +140,29 @@ do_while_loop_p (struct loop *loop)
       && gimple_code (stmt) == GIMPLE_COND)
     return false;
 
+  /* Leave anything with multiple exits, given it satisfies the above.  */
+  if (!single_exit (loop))
+    return true;
+
+  /* If any block in the loop has an exit edge, and code after it, it is
+     not a do-while loop.  */
+  basic_block *body = get_loop_body (loop);
+  for (unsigned i = 0; i < loop->num_nodes; i++)
+    {
+      bool block_has_exit = false, block_precedes_code = false;
+      edge_iterator ei;
+      edge e;
+      FOR_EACH_EDGE (e, ei, body[i]->succs)
+	if (loop_exit_edge_p (loop, e))
+	  block_has_exit = true;
+	else if (e->dest != loop->header
+		 && e->dest != loop->latch)
+	  block_precedes_code = true;
+      if (block_has_exit && block_precedes_code)
+        return false;
+    }
+  free (body);
+
   return true;
 }
 
@@ -162,21 +185,48 @@ const pass_data pass_data_ch =
   0, /* todo_flags_finish */
 };
 
-class pass_ch : public gimple_opt_pass
+const pass_data pass_data_ch_vect =
+{
+  GIMPLE_PASS, /* type */
+  "ch_vect", /* name */
+  OPTGROUP_LOOP, /* optinfo_flags */
+  TV_TREE_CH, /* tv_id */
+  ( PROP_cfg | PROP_ssa ), /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_ch_vect : public gimple_opt_pass
 {
 public:
-  pass_ch (gcc::context *ctxt)
-    : gimple_opt_pass (pass_data_ch, ctxt)
+  pass_ch_vect (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_ch_vect, ctxt)
   {}
 
   /* opt_pass methods: */
   virtual bool gate (function *) { return flag_tree_ch != 0; }
   virtual unsigned int execute (function *);
+protected:
+  pass_ch_vect (const pass_data data, gcc::context *ctxt)
+    : gimple_opt_pass (data, ctxt)
+  {}
+}; // class pass_ch_vect
 
+/* Adds a call to loop_optimizer_init before it executes,
+   and loop_optimizer_finalize after.  */
+class pass_ch : public pass_ch_vect
+{
+public:
+  pass_ch (gcc::context *ctxt) : pass_ch_vect (pass_data_ch, ctxt)
+  {}
+
+  virtual unsigned int execute (function *);
 }; // class pass_ch
 
 unsigned int
-pass_ch::execute (function *fun)
+pass_ch_vect::execute (function *fun)
 {
   struct loop *loop;
   basic_block header;
@@ -186,13 +236,8 @@ pass_ch::execute (function *fun)
   unsigned bbs_size;
   bool changed = false;
 
-  loop_optimizer_init (LOOPS_HAVE_PREHEADERS
-		       | LOOPS_HAVE_SIMPLE_LATCHES);
   if (number_of_loops (fun) <= 1)
-    {
-      loop_optimizer_finalize ();
       return 0;
-    }
 
   bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
   copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
@@ -296,17 +341,35 @@ pass_ch::execute (function *fun)
       changed = true;
     }
 
-  update_ssa (TODO_update_ssa);
+  if (changed)
+    update_ssa (TODO_update_ssa);
   free (bbs);
   free (copied_bbs);
 
-  loop_optimizer_finalize ();
   return changed ? TODO_cleanup_cfg : 0;
 }
 
+unsigned int
+pass_ch::execute (function *fun)
+{
+  loop_optimizer_init (LOOPS_HAVE_PREHEADERS
+		       | LOOPS_HAVE_SIMPLE_LATCHES);
+
+  unsigned int res = pass_ch_vect::execute (fun);
+
+  loop_optimizer_finalize ();
+  return res;
+}
+
 } // anon namespace
 
 gimple_opt_pass *
+make_pass_ch_vect (gcc::context *ctxt)
+{
+  return new pass_ch_vect (ctxt);
+}
+
+gimple_opt_pass *
 make_pass_ch (gcc::context *ctxt)
 {
   return new pass_ch (ctxt);
diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c
index ccb8f97..a5029bb 100644
--- a/gcc/tree-ssa-loop.c
+++ b/gcc/tree-ssa-loop.c
@@ -234,7 +234,9 @@ unsigned int
 pass_tree_loop_init::execute (function *fun ATTRIBUTE_UNUSED)
 {
   loop_optimizer_init (LOOPS_NORMAL
-		       | LOOPS_HAVE_RECORDED_EXITS);
+		       | LOOPS_HAVE_RECORDED_EXITS
+		       | LOOPS_HAVE_PREHEADERS
+		       | LOOPS_HAVE_SIMPLE_LATCHES);
   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 
   /* We might discover new loops, e.g. when turning irreducible

Re: [PATCH/RFC] Make loop-header-copying more aggressive, rerun before tree-if-conversion

[Jeff Law]

On 05/22/2015 09:42 AM, Alan Lawrence wrote:
>
> This patch does so (and makes slightly less conservative, to tackle the
> example above). I found I had to make this a separate pass, so that the
> phi nodes were cleaned up at the end of the pass before running
> tree_if_conversion. Also at this stage in the compiler (inside loop
> opts) it was not possible to run loop_optimizer_init+finalize, or other
> loop_optimizer data structures needed later would be deleted; hence, I
> have two nearly-but-not-quite-identical passes, the new "ch_vect"
> avoiding the init/finalize. I tried to tackle this with some C++
> subclassing, which removes the duplication, but the result feels a
> little ugly; suggestions for any neater approach welcome.
What PHI node cleanup needs to be done?  I don't doubt something's 
needed, but would like to understand the cleanup -- depending on what 
needs to be done, it may be the case that we can cleanup on-the-fly or 
it may point at a general issue we should be resolving prior to running 
tree_if_conversion.


>
> This patch causes failure of the scan-tree-dump of dom2 in
> gcc.dg/ssa/pr21417.c. This looks for jump-threading to perform an
> optimization, but no longer finds the expected line in the log - as the
> loop-header-copying phase has already done an equivalent transformation
> *before* dom2. The final CFG is thus in the desired form, but I'm not
> sure how to determine this (scanning the CFG itself is very difficult,
> well beyond what we can do with regex, requiring looking at multiple
> lines and basic blocks). Can anyone advise? [The test issue can be
> worked around by preserving the old do_while_p logic for the first
> header-copying pass, and using the new logic only for the second, but
> this is more awkward inside the compiler, which feels wrong.]
Don't we have a flag to turn off loop header copying?  If so, does 
adding that flag to the test "fix" it without resorting to something 
gross like preserving the old logic for the first pass and new logic for 
the second pass.

The refactoring to deal with being able to call into this without 
reinitializing the loop optimizer doesn't seem terrible to me.  One 
could argue that the loop optimizer init bits could become a property 
and managed by the pass manager.  I'm not sure that really simplifies 
anything though.

My biggest worry would be cases where data initialized by 
loop_optimizer_init gets invalidated by the header copying.  Have you 
looked at all at that possibility?  I don't have anything specific in 
mind to point you at -- just a general concern.

>
> Besides the new vect-ifcvt-11.c, the testsuite actually has a couple of
> other examples where this patch enables (undesired!) vectorization. I've
> dealt with these, but for the record:
Presumably undesired is within the scope of the testsuite, not 
necessarily in terms of the code we generate for real user code :-)

Overall it doesn't look bad to me...  Convince me it's safe WRT the 
loop_optimizer_init issue above and we'll have a clear path forward.

jeff

Re: [PATCH/RFC] Make loop-header-copying more aggressive, rerun before tree-if-conversion

[Alan Lawrence]

Jeff Law wrote:
> On 05/22/2015 09:42 AM, Alan Lawrence wrote:
>> This patch does so (and makes slightly less conservative, to tackle the
>> example above). I found I had to make this a separate pass, so that the
>> phi nodes were cleaned up at the end of the pass before running
>> tree_if_conversion.
> What PHI node cleanup needs to be done?  I don't doubt something's 
> needed, but would like to understand the cleanup -- depending on what 
> needs to be done, it may be the case that we can cleanup on-the-fly or 
> it may point at a general issue we should be resolving prior to running 
> tree_if_conversion.

If I change pass_ch_vect to return 0 rather than TODO_update_cfg, my testcase gives:

foo ()
{
   int m;
   int i;
   unsigned int ivtmp_3;
   int _5;
   int _6;
   int _7;
   int _10;
   int _12;
   unsigned int ivtmp_13;
   int _15;
   unsigned int ivtmp_19;
   int _20;
   unsigned int ivtmp_23;
   unsigned int ivtmp_27;

   <bb 2>:
   _10 = A[0];

   <bb 8>:
   # m_11 = PHI <4(2)>
   # _12 = PHI <_10(2)>
   # i_1 = PHI <0(2)>
   # ivtmp_19 = PHI <16(2)>
   _20 = m_11 * _12;
   A[i_1] = _20;
   i_22 = i_1 + 1;
   ivtmp_23 = ivtmp_19 - 1;
   if (ivtmp_23 != 0)
     goto <bb 9>;
   else
     goto <bb 7>;

   <bb 9>:

   <bb 3>:
   # i_26 = PHI <i_9(10), i_22(9)>
   # ivtmp_27 = PHI <ivtmp_13(10), ivtmp_23(9)>
   _5 = A[i_26];
   _6 = _5 & i_26;
   if (_6 != 0)
     goto <bb 5>;
   else
     goto <bb 4>;

   <bb 4>:

   <bb 5>:
   # m_14 = PHI <5(3), 4(4)>

   <bb 6>:
   # m_2 = PHI <m_14(5)>
   # _15 = PHI <_5(5)>
   # i_16 = PHI <i_26(5)>
   # ivtmp_3 = PHI <ivtmp_27(5)>
   _7 = m_2 * _15;
   A[i_16] = _7;
   i_9 = i_16 + 1;
   ivtmp_13 = ivtmp_3 - 1;
   if (ivtmp_13 != 0)
     goto <bb 10>;
   else
     goto <bb 7>;

   <bb 10>:
   goto <bb 3>;

   <bb 7>:
   return;

}

if-conversion then bails out in if_convertible_phi_p, with a phi (whose result 
is a virtual operand, specifically an SSA name) used as operand to another phi 
("Difficult to handle this virtual phi" in tree-if-conv.c): see m_2, i_16. 
Returning TODO_update_cfg, causes merging of blocks 2 and 8, and blocks 5 and 6, 
giving instead:

foo ()
{
   int m;
   int i;
   int _5;
   int _6;
   int _7;
   int _10;
   unsigned int ivtmp_13;
   int _20;
   unsigned int ivtmp_23;
   unsigned int ivtmp_27;

   <bb 2>:
   _10 = A[0];
   _20 = _10 * 4;
   A[0] = _20;
   i_22 = 1;
   ivtmp_23 = 15;
   if (ivtmp_23 != 0)
     goto <bb 3>;
   else
     goto <bb 8>;

   <bb 3>:

   <bb 4>:
   # i_26 = PHI <i_9(7), i_22(3)>
   # ivtmp_27 = PHI <ivtmp_13(7), ivtmp_23(3)>
   _5 = A[i_26];
   _6 = _5 & i_26;
   if (_6 != 0)
     goto <bb 6>;
   else
     goto <bb 5>;

   <bb 5>:

   <bb 6>:
   # m_14 = PHI <5(4), 4(5)>
   _7 = _5 * m_14;
   A[i_26] = _7;
   i_9 = i_26 + 1;
   ivtmp_13 = ivtmp_27 + 4294967295;
   if (ivtmp_13 != 0)
     goto <bb 7>;
   else
     goto <bb 8>;

   <bb 7>:
   goto <bb 4>;

   <bb 8>:
   return;

}

and one can see that the troublesome phi's are gone.

> Don't we have a flag to turn off loop header copying?  If so, does 
> adding that flag to the test "fix" it  without resorting to something
> gross like preserving the old logic for the first pass and new logic for 
> the second pass.

Ah, yes, thanks, -fno-tree-ch works. In fact here the problem was caused by the 
second pass, which following Richard's suggestion, I've now gated with 
-ftree-vectorize also - which is turned off by default at -O2, so the test is 
passing without changes.

However, it turns out I was implicitly using different logic in the two passes: 
the 'if (!single_exit(loop)) return true' always bailed out in the first 
pass_ch, as single_exit-ness is not known in the absence of 
LOOPS_HAVE_RECORDED_EXITS, so the first pass_ch was still using the original 
logic anyway! I've now had to refactor the two classes to allow different code 
anyway, which makes the distinction clear.

(I also tried a more complicated version of do_while_loop_p that computed it's 
own single_exit criteria to have that in the first pass; this gave more test 
failures, which are fixable, but it's not really the purpose of this patch to do 
additional header-copying when we are not vectorizing.)

> My biggest worry would be cases where data initialized by 
> loop_optimizer_init gets invalidated by the header copying.  Have you 
> looked at all at that possibility?  I don't have anything specific in 
> mind to point you at -- just a general concern.

Well, this code from tree-ssa-loop-ch.c appears to update the preheader and loop 
latch (I've verified with printf's that loop->latch, loop->header, 
loop_preheader_edge(loop) and loop_latch_edge(loop) are all sensible after this):

/* Ensure that the latch and the preheader is simple (we know that they
	 are not now, since there was the loop exit condition.  */
       split_edge (loop_preheader_edge (loop));
       split_edge (loop_latch_edge (loop));

and I think the exit edges don't change (they get cloned outside the loop). The 
one remaining worry might be irreducible code, but I believe this should have 
been removed by the stage pass_ch_vect runs: I've also run an entire bootstrap + 
testsuite with both (a) an assertion in pass_ch_vect::process_loop_p that none 
of the blocks in the loop are BB_IRREDUCIBLE, and (b) a call to 
verify_loop_structure at the end of pass_ch_base::copy_headers.

I agree this isn't (/cannot be) totally definitive, so if you are not 
sufficiently reassured - would you be if I called loop_optimizer_init 
(LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS) at the end of pass_ch_vect, redoing 
the setup done in pass_tree_loop_init::execute?

Patch v2 at https://gcc.gnu.org/ml/gcc-patches/2015-06/msg01355.html .

Thanks for the review!

--Alan

Re: [PATCH/RFC] Make loop-header-copying more aggressive, rerun before tree-if-conversion

[Jeff Law]

On 06/19/2015 11:38 AM, Alan Lawrence wrote:
> Jeff Law wrote:
>> On 05/22/2015 09:42 AM, Alan Lawrence wrote:
>>> This patch does so (and makes slightly less conservative, to tackle the
>>> example above). I found I had to make this a separate pass, so that the
>>> phi nodes were cleaned up at the end of the pass before running
>>> tree_if_conversion.
>> What PHI node cleanup needs to be done?  I don't doubt something's
>> needed, but would like to understand the cleanup -- depending on what
>> needs to be done, it may be the case that we can cleanup on-the-fly or
>> it may point at a general issue we should be resolving prior to
>> running tree_if_conversion.
>
> If I change pass_ch_vect to return 0 rather than TODO_update_cfg, my
> testcase gives:
Thanks.  Does running the phi-only propagator after the loop header 
copying help?  At first glance it would seem that it ought to propagate 
the values of those degenerate PHIs then eliminate those PHIs.

It was written to cleanup after jump threading which has a tendency to 
create very similar code to what you've shown below and to do so very 
quickly.


/* A very simple pass to eliminate degenerate PHI nodes from the
    IL.  This is meant to be fast enough to be able to be run several
    times in the optimization pipeline.

    Certain optimizations, particularly those which duplicate blocks
    or remove edges from the CFG can create or expose PHIs which are
    trivial copies or constant initializations.

    While we could pick up these optimizations in DOM or with the
    combination of copy-prop and CCP, those solutions are far too
    heavy-weight for our needs.

    This implementation has two phases so that we can efficiently
    eliminate the first order degenerate PHIs and second order
    degenerate PHIs.

    The first phase performs a dominator walk to identify and eliminate
    the vast majority of the degenerate PHIs.  When a degenerate PHI
    is identified and eliminated any affected statements or PHIs
    are put on a worklist.

    The second phase eliminates degenerate PHIs and trivial copies
    or constant initializations using the worklist.  This is how we
    pick up the secondary optimization opportunities with minimal
    cost.  */

> I agree this isn't (/cannot be) totally definitive, so if you are not
> sufficiently reassured - would you be if I called loop_optimizer_init
> (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS) at the end of pass_ch_vect,
> redoing the setup done in pass_tree_loop_init::execute?
As I mentioned, I didn't have anything specific in mind, just a general 
concern.   No way to be totally definitive here.  I think you've done 
suitable due diligence.


>
> Patch v2 at https://gcc.gnu.org/ml/gcc-patches/2015-06/msg01355.html .
Thanks.  It's in the queue again.  Two weeks of PTO has made that queue 
much deeper than I'd like, but I'm making progress :-)

jeff

Re: [PATCH/RFC] Make loop-header-copying more aggressive, rerun before tree-if-conversion

[Alan Lawrence]

Jeff Law wrote:
> Thanks.  Does running the phi-only propagator after the loop header 
> copying help?  At first glance it would seem that it ought to propagate 
> the values of those degenerate PHIs then eliminate those PHIs.
> 
> It was written to cleanup after jump threading which has a tendency to 
> create very similar code to what you've shown below and to do so very 
> quickly.

Thanks for the tip - this fixes up some examples, but not at all. Other examples 
require also a call to rewrite_into_loop_closed_ssa and recomputing 
dominators...maybe I can get everything to work with all of those, but my 
feeling is to keep it as a pass: if the first pass_ch justifies being a pass in 
its own right, then surely a *more aggressive* version of that, does too...

Re: [PATCH/RFC] Make loop-header-copying more aggressive, rerun before tree-if-conversion

[Jeff Law]

On 06/30/2015 10:04 AM, Alan Lawrence wrote:
> Jeff Law wrote:
>> Thanks.  Does running the phi-only propagator after the loop header
>> copying help?  At first glance it would seem that it ought to
>> propagate the values of those degenerate PHIs then eliminate those PHIs.
>>
>> It was written to cleanup after jump threading which has a tendency to
>> create very similar code to what you've shown below and to do so very
>> quickly.
>
> Thanks for the tip - this fixes up some examples, but not at all. Other
> examples require also a call to rewrite_into_loop_closed_ssa and
> recomputing dominators...maybe I can get everything to work with all of
> those, but my feeling is to keep it as a pass: if the first pass_ch
> justifies being a pass in its own right, then surely a *more aggressive*
> version of that, does too...
Works for me.  Thanks for investigating.

jeff

Re: [PATCH/RFC] Make loop-header-copying more aggressive, rerun before tree-if-conversion

[Richard Biener]

On Fri, May 22, 2015 at 5:42 PM, Alan Lawrence <alan.lawrence@arm.com> wrote:
> This example which I wrote to test ifconversion, currently fails to
> if-convert or vectorize:
>
> int foo ()
> {
>   for (int i = 0; i < 32 ; i++)
>     {
>       int m = (a[i] & i) ? 5 : 4;
>       b[i] = a[i] * m;
>     }
> }
>
> ...because jump-threading in dom1 rearranged the loop into a form that
> neither if-conversion nor vectorization would attempt. Discussion at
> https://gcc.gnu.org/ml/gcc/2015-04/msg00343.html lead to the suggestion that
> I should rerun loop-header copying (an earlier attempt to fix ifconversion,
> https://gcc.gnu.org/ml/gcc-patches/2015-04/msg01743.html, still did not
> enable vectorization.)
>
> This patch does so (and makes slightly less conservative, to tackle the
> example above). I found I had to make this a separate pass, so that the phi
> nodes were cleaned up at the end of the pass before running
> tree_if_conversion. Also at this stage in the compiler (inside loop opts) it
> was not possible to run loop_optimizer_init+finalize, or other
> loop_optimizer data structures needed later would be deleted; hence, I have
> two nearly-but-not-quite-identical passes, the new "ch_vect" avoiding the
> init/finalize. I tried to tackle this with some C++ subclassing, which
> removes the duplication, but the result feels a little ugly; suggestions for
> any neater approach welcome.
>
> This patch causes failure of the scan-tree-dump of dom2 in
> gcc.dg/ssa/pr21417.c. This looks for jump-threading to perform an
> optimization, but no longer finds the expected line in the log - as the
> loop-header-copying phase has already done an equivalent transformation
> *before* dom2. The final CFG is thus in the desired form, but I'm not sure
> how to determine this (scanning the CFG itself is very difficult, well
> beyond what we can do with regex, requiring looking at multiple lines and
> basic blocks). Can anyone advise? [The test issue can be worked around by
> preserving the old do_while_p logic for the first header-copying pass, and
> using the new logic only for the second, but this is more awkward inside the
> compiler, which feels wrong.]
>
> Besides the new vect-ifcvt-11.c, the testsuite actually has a couple of
> other examples where this patch enables (undesired!) vectorization. I've
> dealt with these, but for the record:
>         * gcc.dg/vect/slp-perm-7.c: the initialization loop in main,
> contained a check that input[i] < 200; this was already optimized out
> (because input[i] was set to i%256, where i<N with N #defined to 16), but
> that loop was not vectorized because:
> /work/alalaw01/oban/srcfsf/gcc/gcc/testsuite/gcc.dg/vect/slp-perm-7.c:54:3:
> note: not vectorized: latch block not empty.
> /work/alalaw01/oban/srcfsf/gcc/gcc/testsuite/gcc.dg/vect/slp-perm-7.c:54:3:
> note: bad loop form.
>
>         * gcc.dg/vect/vect-strided-a-u16-i4.c: the main1() function has
> three loops; the first (initialization) has an 'if (y) abort() /* Avoid
> vectorization.  */'. However, the 'volatile int y = 0' this was meant to
> reference, is actually shadowed by a local non-volatile; the test is thus
> peeled off and absent from the body of the loop. The loop only avoided
> vectorization because of non-empty latch and bad loop form, as previous.
>
> With this patch, both those loops now have good form, hence I have fixed
> both to check a global volatile to prevent these extraneous parts from being
> vectorized.
>
> Tested with bootstrap + check-gcc on x86_64 and AArch64 (linux). As noted
> above, this causes a spurious PASS->FAIL of a scan-tree-dump test, which I'm
> unsure how to fix, but no other regressions.

Apart from Jeffs comment - the usual fix for the undesired
vectorization is to put
a __asm__ volatile (""); in the loop.

+  /* If any block in the loop has an exit edge, and code after it, it is
+     not a do-while loop.  */
+  basic_block *body = get_loop_body (loop);
+  for (unsigned i = 0; i < loop->num_nodes; i++)

wouldn't it be easier to verify that the predecessor of the loop latch
contains the (only) loop exit?

Like

   e = single_exit (loop);
   if (!e)
     return true;

   if (single_exit (loop)->pred != single_pred (loop->latch))
     return false;

?  In fact I think that even for multiple exists we want the latch predecessor
have an exit (though the vectorizer or if-conversion don't deal with that).

Note that single_exit () only works when the loop state has
LOOPS_HAVE_RECORDED_EXITS
thus it might be easier to simply check

  FOR_EACH_EDGE (... single_pred (loop->latch)->succs ..)
     if (e->dest == loop->latch)
       ;
     else
       break;
  if (!e || !loop_exit_edge_p (loop, e))
    return true;

which should work always.

Coding-style wise, can you please move the "common" pass_ch_vect::execute out
of the pass_ch_vect class?

  unsigned int res = pass_ch_vect::execute (fun);

looks ugly, as well as deriving pass_ch from pass_ch_vect.  I think pass_ch_vect
should be only executed if flag_tree_loop_vectorize is enabled.

   loop_optimizer_init (LOOPS_NORMAL
-                      | LOOPS_HAVE_RECORDED_EXITS);
+                      | LOOPS_HAVE_RECORDED_EXITS
+                      | LOOPS_HAVE_PREHEADERS
+                      | LOOPS_HAVE_SIMPLE_LATCHES);

already included in LOOPS_NORMAL.

Thanks,
Richard.

> gcc/ChangeLog:
>
>         * tree-pass.h (make_pass_ch_vect): New.
>         * passes.def: Add pass_ch_vect just before pass_if_conversion.
>
>         * tree-ssa-loop-ch.c (do_while_loop_p): For single-exit loops,
>         look for blocks with exit edge and code after them.
>         (pass_data_ch_vect, class pass_ch_vect, make_pass_ch_vect): New.
>         (class pass_ch): Extend pass_ch_vect.
>         (pass_ch::execute): Move all but loop_optimizer_init/finalize to...
>         (pass_ch_vect::execute): ...here.
>
>         * tree-ssa-loop.c (pass_tree_loop_init::execute): Add flags
>         LOOPS_HAVE_PREHEADERS and LOOPS_HAVE_SIMPLE_LATCHES.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/vect/slp-perm-7.c (zero): New.
>         (main): Test zero rather than input[i], to avoid vectorization.
>         * gcc.dg/vect/vect-strided-a-u16-i4.c (main1): Narrow scope of
> x,y,z,w.
>         of unsigned
>         * gcc.dg/vect/vect-ifcvt-11.c: New.
>

Re: [PATCH/RFC] Make loop-header-copying more aggressive, rerun before tree-if-conversion

[Alan Lawrence]

Richard Biener wrote:
> Apart from Jeffs comment - the usual fix for the undesired
> vectorization is to put
> a __asm__ volatile (""); in the loop.

In vect-strided-a-u16-i4.c, narrowing the scope of the declaration seemed to 
preserve the original intent. I've been able to drop the other testsuite changes.

> +  /* If any block in the loop has an exit edge, and code after it, it is
> +     not a do-while loop.  */
> +  basic_block *body = get_loop_body (loop);
> +  for (unsigned i = 0; i < loop->num_nodes; i++)
> 
> wouldn't it be easier to verify that the predecessor of the loop latch
> contains the (only) loop exit?

It's not guaranteed that the loop latch has only one predecessor. The testsuite 
contains quite a few examples, e.g. gcc.c-torture/compile/20011114.c (at -O3). 
However, I've found a simpler (and equivalent) test, as we have the unique exit 
edge and it's source already.

> Note that single_exit () only works when the loop state has
> LOOPS_HAVE_RECORDED_EXITS

Hah, thanks - didn't realize that. So using single_exit_p did make pass_ch 
behave differently from pass_ch_vect. I've restored the original code for the 
original pass_ch...

 > I think pass_ch_vect
 > should be only executed if flag_tree_loop_vectorize is enabled.

...agreed; and handling loop->force_vectorize and loop->dont_vectorize properly 
required splitting the two phases up more anyway, so I've used clearly-different 
predicates in each.

> Coding-style wise, can you please move the "common" pass_ch_vect::execute out
> of the pass_ch_vect class?

Yes, I've done some reorg, introducing a third base class with the common 
execute bits calling a virtual method returning bool.

>    loop_optimizer_init (LOOPS_NORMAL
> -                      | LOOPS_HAVE_RECORDED_EXITS);
> +                      | LOOPS_HAVE_RECORDED_EXITS
> +                      | LOOPS_HAVE_PREHEADERS
> +                      | LOOPS_HAVE_SIMPLE_LATCHES);
> 
> already included in LOOPS_NORMAL.

So it is. Thanks!

TYVM for the review - I've posted a v2 at 
https://gcc.gnu.org/ml/gcc-patches/2015-06/msg01355.html .

Cheers, Alan