[llvm-dev] Loop identification

Krzysztof Parzyszek via llvm-dev llvm-dev at lists.llvm.org
Mon Jan 16 06:14:01 PST 2017

The polynomial multiplication discussed below is actually exactly 
that---it converts a loop into a single intrinsic that performs 
polynomial multiplication.  The polynomials are over {0, 1}, i.e. the 
coefficients are bits, and a 32-bit integer can represent a polynomial 
of degree 31. Hexagon (among other architectures) has an instruction 
that takes two such inputs (to integers representing polynomials) and 
produces their polynomial product.

Generally, target-specific passes run after all target-independent 
passes.  This may be a problem for loop idiom recognition, since all the 
target-independent optimizations may transform the loop in a way that 
makes the idiom recognition harder.  The PassManagerBuilder supports the 
concept of insertion points, where extra passes could be added, and I'm 
hoping that an insertion point could be added at the place where the 
target-independent idiom recognition pass runs, which would help both 
you and me (with the polynomial multiplication, and few other things, 
which are not yet in the trunk).


On 1/16/2017 2:23 AM, Catello Cioffi wrote:
> The result in the example I made doesn't need to be exactly like that;
> that is I want to recognize the inner loop and translate it into a
> machine instruction. I thought that translating it into an intrinsic
> could be easier but it seems not.
> What I was thinking to do is to modify the Mips backend adding a Loop
> Pass or a Function Pass. Do you think that this could work?
> 2017-01-14 23:57 GMT+01:00 Krzysztof Parzyszek via llvm-dev
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>:
>     On 1/13/2017 7:08 PM, Hal Finkel wrote:
>         This is integer multiplication or floating-point multiplication?
>         If it
>         is integer multiplication, I'd expect that using SCEV would be the
>         easiest way to recognize the relevant patterns. SCEV is supposed to
>         understand all of the unobfuscation tricks.
>         Do these instructions contain an implicit loop (of runtime trip
>         count)
>         or are you trying to match loops of some fixed trip count?
>     It's binary polynomial multiplication. The loops are usually with a
>     compile-time constant iteration count.
>     I posted a specific patch with that code:
>     https://reviews.llvm.org/D28694 <https://reviews.llvm.org/D28694>
>     -Krzysztof
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>     <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>

Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

More information about the llvm-dev mailing list