[llvm-dev] Loop identification

[Hal Finkel via llvm-dev]

On 01/13/2017 10:19 AM, Krzysztof Parzyszek via llvm-dev wrote:
> Hi Catello,
>
> LLVM does have a "loop idiom recognition" pass which, in principle, 
> does exactly that kind of a thing: it recognizes loops that perform 
> memcpy/memset operations. It does not recognize any target-specific 
> idioms though and there isn't really much in it that would make such 
> recognition easier. We have some cases like yours on Hexagon, where we 
> want to replace certain loops with Hexagon-specific intrinsics, and 
> the way we do it is that we have (in our own compiler) a separate pass 
> that runs at around the same time, but which does "Hexagon-specific 
> loop idiom recognition". That pass is not present in llvm.org, mostly 
> because it hooks up a target specific pass in a way that is not 
> "officially supported".
>
> If LLVM supported adding such target-specific passes at that point in 
> the optimization pipeline, you could just write your own pass and plug 
> it in there.

This certainly seems like a reasonable thing to support, but the 
question is: Why should your pass run early in the mid-level optimizer 
(i.e. in the part of the pipeline we generally consider 
canonicalization) instead of as an early IR pass in the backend? Adding 
IR-level passes early in the backend is well supported. There are plenty 
of potential answers here for why earlier is better (e.g. affecting 
inlining decisions, idioms might be significantly more difficult to 
recognize after vectorization, etc.) but I think we need to discuss the 
use case.

  -Hal

>
> -Krzysztof
>
>
> On 1/13/2017 9:45 AM, Catello Cioffi via llvm-dev wrote:
>> Good afternoon,
>>
>> I'm working on modifying the Mips backend in order to add new
>> functionalities. I've successfully implemented the intrinsics, but I
>> want to recognize a pattern like this:
>>
>> int seq[max];
>> int cnt = 0;
>>
>> for (int i = 0; i < max; i++)
>> {
>>    for (int j = 0; i < 16; i++)
>>    {
>>        char hn = (seq[i] & (3<<(j*2)) >> (j*2);
>>        if (hn == 2)
>>           {
>>              cnt++;
>>           }
>>    }
>> }
>>
>>
>> and transform it into something like:
>>
>> int seq[max];
>> int cnt = 0;
>>
>> for (int i = 0; i < max; i++)
>> {
>>   cnt += intrinsic(seq[i], 2);
>> }
>>
>> Do you know what I can use to transform the loop? Or if exists something
>> similar in LLVM?
>>
>> Thanks,
>>
>> Catello
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory