Loop splitting as a special case of unswitch

Project Infrastructure LLVM Dev List Archives
1

For the example code below,
  int L = M + 10;
  for (k = 1 ; k <=L; k++) {
    dummy();
    if (k < M)
      dummy2();
  }
, we can split the loop into two parts like :

  for (k = 1 ; k != M; k++) {
    dummy();
    dummy2();
  }
  for (; k <=L; k++) {
    dummy();
  }

By splitting the loop, we can remove the conditional block in the loop and indirectly increase vectorization opportunities. If we know that a loop has a conditional branch that is always true for one part of the iteration space and false for the other, then we can split such loop into two parts. As far as I check, GCC seems to handle this already (-fsplit-loops). For me, it seem possible to handle this as a special case of the loop-unswitch. Does anyone have any opinion about this transformation?

Thanks,
Jun

2

For the example code below,
  int L = M + 10;
  for (k = 1 ; k <=L; k++) {
    dummy();
    if (k < M)
      dummy2();
  }
, we can split the loop into two parts like :

  for (k = 1 ; k != M; k++) {
    dummy();
    dummy2();
  }
  for (; k <=L; k++) {
    dummy();
  }

I believe i have reported a similar case as
https://bugs.llvm.org/show_bug.cgi?id=34364

By splitting the loop, we can remove the conditional block in the loop and indirectly increase vectorization opportunities. If we know that a loop has a conditional branch that is always true for one part of the iteration space and false for the other, then we can split such loop into two parts. As far as I check, GCC seems to handle this already (-fsplit-loops). For me, it seem possible to handle this as a special case of the loop-unswitch. Does anyone have any opinion about this transformation?

Thanks,
Jun

Roman.

3

For the example code below,
  int L = M + 10;
  for (k = 1 ; k <=L; k++) {
    dummy();
    if (k < M)
      dummy2();
  }
, we can split the loop into two parts like :

  for (k = 1 ; k != M; k++) {
    dummy();
    dummy2();
  }
  for (; k <=L; k++) {
    dummy();
  }

I believe i have reported a similar case as
34364 – missed loop peeling with condition based on induction variable

What I meant here is little different from the loop peeling mentioned in PR34364. While loop splitting remove the conditional block in the loop by breaking the loop into two parts, loop peeling take the first or last few iterations out of the loop. I think the loop splitting can cover more dynamic cases where the iteration size of each portion is unknown.

4

For the example code below,
  int L = M + 10;
  for (k = 1 ; k <=L; k++) {
    dummy();
    if (k < M)
      dummy2();
  }
, we can split the loop into two parts like :

  for (k = 1 ; k != M; k++) {
    dummy();
    dummy2();
  }
  for (; k <=L; k++) {
    dummy();
  }

I believe i have reported a similar case as
34364 – missed loop peeling with condition based on induction variable

What I meant here is little different from the loop peeling mentioned in
PR34364. While loop splitting remove the conditional block in the loop by
breaking the loop into two parts, loop peeling take the first or last few
iterations out of the loop. I think the loop splitting can cover more
dynamic cases where the iteration size of each portion is unknown.

Yes, absolutely, i'm not arguing against that at all.

Moreover, the bug i have reported is not currently being done by clang,
⚙ D31613 [LoopPeeling] Get rid of Phis that become invariant after N steps, so if the loop splitting would
be done by clang, (and would resolve that bugreport), i'd be very happy :slight_smile:

5

Take a look at the InductiveRangeCheckElimination pass in tree. It's not on by default, but if you're wiling to use a custom pass pipeline you can get this case.

Philip