llvm dev - Jan 2010 - [LLVMdev] [PATCH] Emit rbit, clz on ARM for __builtin_ctz

Hi,

On ARMv6T2 this turns cttz into rbit, clz instead of the 4 instruction sequence
it is now.

I'm not sure if adding RBIT to ARMISD and doing this optimization in the
legalize pass is the best option, but the only better way I could think of doing
it was to add a bitreverse intrinsic to llvm ir, which itself might not be the
best option since bitreverse probably isn't too common.

Other targets that I know of that could potentially benefit from this
optimization being global (that have a clz and bitreverse instruction but not
ctz) are AVR32 and C64x, neither of which llvm has backends for yet.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: llvm-ctz-arm.diff
Type: application/octet-stream
Size: 5160 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100115/9da482e2/attachment.obj>

On Jan 14, 2010, at 10:13 PM, David Conrad wrote:
> Hi,
>
> On ARMv6T2 this turns cttz into rbit, clz instead of the 4  
> instruction sequence it is now.
>
> I'm not sure if adding RBIT to ARMISD and doing this optimization in  
> the legalize pass is the best option, but the only better way I  
> could think of doing it was to add a bitreverse intrinsic to llvm  
> ir, which itself might not be the best option since bitreverse  
> probably isn't too common.
I haven't looked at the patch in detail, but this approach makes sense  
to me.
> Other targets that I know of that could potentially benefit from  
> this optimization being global (that have a clz and bitreverse  
> instruction but not ctz) are AVR32 and C64x, neither of which llvm  
> has backends for yet.
When/if another target wants this, we could add a ISD::RBIT operation,  
it doesn't need to be added at the llvm ir level,

-Chris

On 15 Jan 2010, at 18:03, Chris Lattner wrote:
> On Jan 14, 2010, at 10:13 PM, David Conrad wrote:
> 
>> Other targets that I know of that could potentially benefit from  
>> this optimization being global (that have a clz and bitreverse  
>> instruction but not ctz) are AVR32 and C64x, neither of which llvm  
>> has backends for yet.
> 
> When/if another target wants this, we could add a ISD::RBIT operation,  
> it doesn't need to be added at the llvm ir level,
The XCore also has ctlz and bitreverse instructions and not cttz. At the moment
in the XCore backend cttz is marked as legal and expanded to this pair of
instructions in a pattern in the InstrInfo.td.

-- 
Richard Osborne | XMOS
http://www.xmos.com

On Fri, Jan 15, 2010 at 6:03 PM, Chris Lattner <clattner at apple.com>
wrote:
>
> On Jan 14, 2010, at 10:13 PM, David Conrad wrote:
>
>> Hi,
>>
>> On ARMv6T2 this turns cttz into rbit, clz instead of the 4
>> instruction sequence it is now.
>>
>> I'm not sure if adding RBIT to ARMISD and doing this optimization
in
>> the legalize pass is the best option, but the only better way I
>> could think of doing it was to add a bitreverse intrinsic to llvm
>> ir, which itself might not be the best option since bitreverse
>> probably isn't too common.
>
> I haven't looked at the patch in detail, but this approach makes sense
> to me.
>
>> Other targets that I know of that could potentially benefit from
>> this optimization being global (that have a clz and bitreverse
>> instruction but not ctz) are AVR32 and C64x, neither of which llvm
>> has backends for yet.
>
> When/if another target wants this, we could add a ISD::RBIT operation,
> it doesn't need to be added at the llvm ir level,
Bit reversal turns up in most FFT algorithms, so it wouldn't hurt to
be able to add an instcombine that recognizes it, etc.

deep

On Jan 15, 2010, at 10:03 AM, Chris Lattner wrote:
> 
> When/if another target wants this, we could add a ISD::RBIT operation,  
> it doesn't need to be added at the llvm ir level,
Blackfin can add with backwards carry, essentially doing

(rbit (add (rbit a), (rbit b)))

This is used for FFTs.

I wasn't hoping to be able to pattern-match something so complicated.