[PATCH] Hoist loop invariant statements containing data refs with zero-step during loop-versioning in vectorization.

[Cong Hou]

During loop versioning in vectorization, the alias check guarantees
that any load of a data reference with zero-step is a loop invariant,
which can be hoisted outside of the loop. After hoisting the load
statement, there may exist more loop invariant statements. This patch
tries to find all those statements and hoists them before the loop.

An example is shown below:


for (i = 0; i < N; ++i)
  a[i] = *b + 1;


After loop versioning the loop to be vectorized is guarded by

if (b + 1 < a && a + N < b)

which means there is no aliasing between *b and a[i]. The GIMPLE code
of the loop body is:

  <bb 5>:
  # i_18 = PHI <0(4), i_29(6)>
  # ivtmp_22 = PHI <10000(4), ivtmp_30(6)>
  _23 = (long unsigned int) i_18;
  _24 = _23 * 4;
  _25 = a_6(D) + _24;
  _26 = *b_8(D);                =====> loop invariant
  _27 = _26 + 1;                =====> loop invariant
  *_25 = _27;
  i_29 = i_18 + 1;
  ivtmp_30 = ivtmp_22 - 1;
  if (ivtmp_30 != 0)
    goto <bb 6>;
  else
    goto <bb 21>;


After hoisting loop invariant statements:


  _26 = *b_8(D);
  _27 = _26 + 1;

  <bb 5>:
  # i_18 = PHI <0(4), i_29(6)>
  # ivtmp_22 = PHI <10000(4), ivtmp_30(6)>
  _23 = (long unsigned int) i_18;
  _24 = _23 * 4;
  _25 = a_6(D) + _24;
  *_25 = _27;
  i_29 = i_18 + 1;
  ivtmp_30 = ivtmp_22 - 1;
  if (ivtmp_30 != 0)
    goto <bb 6>;
  else
    goto <bb 21>;


This patch is related to the bug report
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58508


thanks,
Cong

diff --git gcc/testsuite/gcc.dg/vect/pr58508.c 
gcc/testsuite/gcc.dg/vect/pr58508.c
new file mode 100644
index 0000000..cb22b50
--- /dev/null
+++ gcc/testsuite/gcc.dg/vect/pr58508.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-vectorize -fdump-tree-vect-details" } */
+
+
+/* The GCC vectorizer generates loop versioning for the following loop
+   since there may exist aliasing between A and B.  The predicate checks
+   if A may alias with B across all iterations.  Then for the loop in
+   the true body, we can assert that *B is a loop invariant so that
+   we can hoist the load of *B before the loop body.  */
+
+void foo (int* a, int* b)
+{
+  int i;
+  for (i = 0; i < 100000; ++i)
+    a[i] = *b + 1;
+}
+
+
+/* { dg-final { scan-tree-dump-times "hoist" 2 "vect" } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */