This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

dom1 prevents vectorization via partial loop peeling?


Hi,

I've been experimenting with some small testcases with the aim of getting the vectorizer to work on more loops. I started by compiling at -O3 the following testcase:

#define N 32

int a[N];
int b[N];

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

After copyrename3, immediately prior to dom1, the loop body looks like:

  <bb 2>:

  <bb 3>:
  # i_11 = PHI <i_9(7), 0(2)>
  _5 = a[i_11];
  _6 = i_11 & _5;
  if (_6 != 0)
    goto <bb 4>;
  else
    goto <bb 5>;

  <bb 4>:

  <bb 5>:
  # m_2 = PHI <5(4), 4(3)>
  _7 = m_2 * _5;
  b[i_11] = _7;
  i_9 = i_11 + 1;
  if (i_9 != 32)
    goto <bb 7>;
  else
    goto <bb 6>;

  <bb 7>:
  goto <bb 3>;

  <bb 6>:
  return;

dom1 then peeled part of the first loop iteration, producing:

  <bb 2>:
  goto <bb 8>;

  <bb 3>:
  # i_11 = PHI <i_9(6)>
  _5 = a[i_11];
  _6 = i_11 & _5;
  if (_6 != 0)
    goto <bb 4>;
  else
    goto <bb 5>;

  <bb 4>:

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

  <bb 6>:
  # m_2 = PHI <m_14(5), 4(8)>
  # _15 = PHI <_5(5), _10(8)>
  # i_16 = PHI <i_11(5), i_1(8)>
  _7 = m_2 * _15;
  b[i_16] = _7;
  i_9 = i_16 + 1;
  if (i_9 != 32)
    goto <bb 3>;
  else
    goto <bb 7>;

  <bb 7>:
  return;

  <bb 8>:
  # i_1 = PHI <0(2)>
  _10 = a[i_1];
  _3 = i_1 & _10;
  goto <bb 6>;


which following ivcanon, had been simplified down to:

  <bb 2>:
  _10 = a[0];
  goto <bb 6>;

  <bb 3>:
  _5 = a[i_9];
  _6 = _5 & i_9;
  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), 4(2)>
  # _15 = PHI <_5(5), _10(2)>
  # i_16 = PHI <i_9(5), 0(2)>
  # ivtmp_13 = PHI <ivtmp_3(5), 32(2)>
  _7 = m_2 * _15;
  b[i_16] = _7;
  i_9 = i_16 + 1;
  ivtmp_3 = ivtmp_13 - 1;
  if (ivtmp_3 != 0)
    goto <bb 3>;
  else
    goto <bb 7>;

  <bb 7>:
  return;

tree-if-conversion wouldn't deal with such a loop, and so the control flow made the vectorizer bail out too; resulting in scalar code (on both x86_64 and AArch64). I am currently testing a patch to tree-if-conv.c that makes it work on such a CFG, producing:

  <bb 2>:
  _10 = a[0];
  goto <bb 4>;

  <bb 3>:

  <bb 4>:
  # m_2 = PHI <m_14(3), 4(2)>
  # _15 = PHI <_5(3), _10(2)>
  # i_16 = PHI <i_9(3), 0(2)>
  # ivtmp_13 = PHI <ivtmp_3(3), 32(2)>
  _7 = m_2 * _15;
  b[i_16] = _7;
  i_9 = i_16 + 1;
  ivtmp_3 = ivtmp_13 - 1;
  _5 = a[i_9];
  _6 = _5 & i_9;
  m_14 = _6 != 0 ? 5 : 4;
  if (ivtmp_3 != 0)
    goto <bb 3>;
  else
    goto <bb 5>;

  <bb 5>:
  return;

However, this still fails to vectorize: the PHI nodes at the start of bb 4 prevent this (in vect_analyze_scalar_cycles: they look a bit like reductions, but aren't).

In contrast, a slightly-different testcase:

#define N 32

int a[N];
int b[N];

int foo ()
{
  for (int i = 0; i < N ; i++)
    {
      int cond = (a[i] & i) ? -1 : 0; // extra variable here
      int m = (cond) ? 5 : 4;
      b[i] = a[i] * m;
    }
}

after copyrename3, just before dom1, is only slightly different:

  <bb 2>:

  <bb 3>:
  # i_15 = PHI <i_10(7), 0(2)>
  _6 = a[i_15];
  _7 = i_15 & _6;
  if (_7 != 0)
    goto <bb 4>;
  else
    goto <bb 6>;

  <bb 4>:
  # m_3 = PHI <4(6), 5(3)>
  _8 = m_3 * _6;
  b[i_15] = _8;
  i_10 = i_15 + 1;
  if (i_10 != 32)
    goto <bb 7>;
  else
    goto <bb 5>;

  <bb 7>:
  goto <bb 3>;

  <bb 5>:
  return;

  <bb 6>:
  goto <bb 4>;

with bb6 being out-of-line at the end of the function, rather than bb4 falling through from just above bb5. However, this prevents dom1 from doing the partial peeling, and dom1 only changes the "goto bb7" into a "goto bb3":

  <bb 2>:

  <bb 3>:
  # i_15 = PHI <i_10(4), 0(2)>
  _6 = a[i_15];
  _7 = i_15 & _6;
  if (_7 != 0)
    goto <bb 4>;
  else
    goto <bb 6>;

  <bb 4>:
  # m_3 = PHI <4(6), 5(3)>
  _8 = m_3 * _6;
  b[i_15] = _8;
  i_10 = i_15 + 1;
  if (i_10 != 32)
    goto <bb 3>;
  else
    goto <bb 5>;

  <bb 5>:
  return;

  <bb 6>:
  goto <bb 4>;

Existing tree_if_conversion deals with this just fine, feeding into the vectorizer:

  <bb 2>:

  <bb 3>:
  # i_15 = PHI <i_10(4), 0(2)>
  # ivtmp_12 = PHI <ivtmp_1(4), 32(2)>
  _6 = a[i_15];
  _7 = _6 & i_15;
  m_3 = _7 != 0 ? 5 : 4;
  _8 = m_3 * _6;
  b[i_15] = _8;
  i_10 = i_15 + 1;
  ivtmp_1 = ivtmp_12 - 1;
  if (ivtmp_1 != 0)
    goto <bb 4>;
  else
    goto <bb 5>;

  <bb 4>:
  goto <bb 3>;

Which is vectorized OK (the only PHI is the induction variable i_15, a true scalar cycle).

So, besides the if conversion, I see two issues here:

(1) dom1 should really, in the second case, perform the same partial peeling that it does in the first testcase, if that is what it thinks is desirable. (Of course, we might want to fix that only later, as ATM that'd take us backwards).

(2) somehow, gcc should vectorize loops that have been partially peeled in that way. The only way I can really see, is to partially peel the same portion of the first (vectorization factor - 1) loop iterations too, so we can do a PHI of a whole vector at a time, and so I'm wondering if anyone can give me any pointers here - am I barking up the right tree - and is it reasonable to persuade existing vectorizer loop-peeling code (e.g. for alignment) to do this for us too, or would anyone recommend a different avenue?

Alternatively, maybe we don't want dom1 doing that sort of thing (?), but I'm inclined to think that if it's doing such optimizations, it's for a good reason ;) I guess there'll be other times where we *cannot* do partially peeling of later iterations...

Thoughts?

Thanks, Alan


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]