llvm dev - Feb 2018 - Loop splitting as a special case of unswitch

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

On Fri, Feb 23, 2018 at 12:15 AM, Jun Lim via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> 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.
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On 2018-02-22 16:21, Roman Lebedev wrote:
> On Fri, Feb 23, 2018 at 12:15 AM, Jun Lim via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>> 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

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.

> 
>> 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.
> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 
Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm 
Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a 
Linux Foundation Collaborative Project.

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

On 02/22/2018 01:15 PM, Jun Lim via llvm-dev wrote:
> 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
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev