[LLVMdev] Shifts that use only 5 LSBs.

[Daniel M Gessel]

On Dec 16, 2008, at 7:57 PM, Eli Friedman wrote:
> On Tue, Dec 16, 2008 at 3:36 PM, Daniel M Gessel <gessel at apple.com>  
> wrote:
>> I'm working on a Target that only uses the 5 lsbs of the shift  
>> amount.
>
> Okay, that's quite common... x86 is the same.
>

Thanks - yes, I'd heard rumors that x86 operates the same way.

>> I only have 32 bit registers, no 64 bit, so 64 bit math is emulated,
>> LLVM doing the transformations whenever I can get it to.
>
> x86 is the same.

Ah, maybe I should try my test below on x86, and see what happens.  
It'll take me a bit as I'm not familiar with x86 assembly code.
>
>> I think I'm seeing a case where it ultimately looks like a standard
>> multiword shift (from e.g. Hacker's Delight) is being inline expanded
>> that assumes at least 6 bits of the shift is paid attention to (i.e.
>> it looks like it assumes x >> 32 == 0 if x is 32 bits, but for me x  
>> >>
>> 32 == x).
>>
>> (A) What does LLVM assume about "shift width"?
>
> "If op2 is (statically or dynamically) negative or equal to or larger
> than the number of bits in op1, the result is undefined."  See
> http://llvm.org/docs/LangRef.html#i_shl.  Roughly, that means that
> "lshr i32 %x, 32" is allowed to return any arbitrary value.  If you
> need consistent behavior, you should explicitly mask the shift amount
> in the front-end.

The problem here is that it looks like LLVM is introducing an  
expansion that assumes 32 bit shifts use more than 5 bits of the shift  
value.

I created a simple test function:

u64 mebbe_shift( u64 x, int test )
{
	if( test )
		x <<= 2;
	return x;
}

I compile using clang, opt, and llc.

I get something that, converted from my assembler to hasty psuedo-C:

u64 mebbe_shift( u64 x, int test )
{
	int amt = test ? 2 : 0;

	x.hi = x.hi << amt  |  x.lo >> (32 - amt);
	x.lo <<= amt;

	return x;
}

My Target doesn't explicitly do any of these kinds of expansions or  
transformations, so it seems to me it's somewhere in LLVM that this is  
happening.

I'll investigate further.

Thanks,

Dan

P.S. what i'd like to get, for performance on my target, is something  
like:


u64 mebbe_shift( u64 x, int test )
{
	y.hi = x.hi << 2  |  x.lo >> 30;
	y.lo = x.lo << 2;

	x.hi = test ? y.hi : x.hi;
	x.lo = test ? y.lo : x.lo;

	return x;
}

Shifts are expensive but selects are cheap.

But I'd be happy to just understand where things are going wrong for  
now.


>
>
> -Eli
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20081216/0ab3557e/attachment.html>