Loop distribute / versioning to remove control flow

Project Infrastructure LLVM Dev List Archives
1

Hi,

Florian has been working on loop peeling to remove control flow from loop bodies in https://reviews.llvm.org/D43876. For larger constants or other loop invariant bounds, such like:

for (unsigned i = 0; i; i < 1000; ++i) {
if (i < M)

… something
else
… something else
}

The loop could be split into two, like so:

Min = min(1000, M);
unsigned i;
for (i = 0; i; i < Min; ++i) {
… something
}

for (; i; i < 1000; ++i) {
… something else
}

Both loop distribute and versioning are designed to analyze memory and enable vectorization, but is there much preventing them from being able to split loops to remove control-flow instead? If this seems feasible, could someone give some advice on what would be needed?

Thanks,

sam

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

2

Hi,

Hi,

Florian has been working on loop peeling to remove control flow from loop bodies in ⚙ D43876 [LoopUnroll] Peel off iterations if it makes conditions true/false.. For larger constants or other loop invariant bounds, such like:

for (unsigned i = 0; i; i < 1000; ++i) {
if (i < M)
... something
else
... something else
}

The loop could be split into two, like so:

Min = min(1000, M);
unsigned i;
for (i = 0; i; i < Min; ++i) {
... something
}

for (; i; i < 1000; ++i) {
... something else
}
> Both loop distribute and versioning are designed to analyze memory and
enable vectorization, but is there much preventing them from being able to split loops to remove control-flow instead? If this seems feasible, could someone give some advice on what would be needed?

Splitting the loops that way should be okay, as it should not change the iteration space. But I think to eliminate the condition in the second loop, we need to know that the induction variable does not wrap.

The InductiveRangeCheckElimination pass already implements splitting loops with range checks of the form

  len = known positive
  for (unsigned i = 0; i; i < 1000; ++i) {
     if (i <= 0 && i < len)
     ... something
     else
     ... something else
  }

That might be good starting point.

Cheers,
Florian