[llvm-dev] Loop distribute / versioning to remove control flow

[Florian Hahn via llvm-dev]

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