llvm dev - Mar 2018 - Loop distribute / versioning to remove control flow

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


Sam Parker

Compilation Tools Engineer | Arm

. . . . . . . . . . . . . . . . . . . . . . . . . . .

Arm.com

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180309/a12895d3/attachment.html>

Hi,

On 09/03/2018 09:51, Sam Parker wrote:
> 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?
> 
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