3

Which operators in C language would result in assembly commands such as sal, shl, sar or shr for example?

  • 1
    Hi and welcome to RE.SE. Given the role optimizers play during the transformation of source code to binary, this is a rather tough question which will be hard to answer unless you also provide details on the compiler (and version) you're interested in. Now my guess is also that these are the usual IA-32 mnemonics, but you may also want to indicate the ISA. – 0xC0000022L Feb 1 at 12:57
4

First it should be noted that there are so many architectures out there, each with its own instruction set. Here I assume you mean x86 (and you should indeed tag the proper architecture as 0xC0000022L said above). Most parts of the below answer would apply to other architectures as well, but they may use different mnemonics or lack some mentioned instructions

SAL and SHL are the same. They're simply aliases to the same opcode because shifting left always fill the vacant bits with 0s. In C << will do a shift left, and whether the shift instruction is printed as SAL or SHL depends on the compiler/disassembler

OTOH there are 2 versions of right shift because you can fill the bits that were shifted out with zero (logical shift) or the high bit of the old value (arithmetic shift). SAR does an arithmetic shift and SHR does a logical shift. In C the operator for right shifting is >>, but the rule depends on the signness of the type:

  • A right shift on an unsigned type is always a logical shift, therefore SHR will be used
  • A right shift on a signed type is implementation defined, i.e. the compiler can choose to do an arithmetic or a logical shift. However almost all modern compilers will do an arithmetic shift (SAR) on signed types (otherwise doing arithmetic shift would be too tricky/clumsy). Some compilers may have an option to select the right shift variant though

Per the C99 standard, section 6.5.7:

The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 × 2E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 × 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.


However there are a lot of other operations that can produce a shift instruction, and various cases that shift operators don't produce a shift instruction

It's less common to see << and >> that are not compiled to a shift instruction, but compilers may optimize x << 1 to x += x and you'll see things like ADD eax, eax, LEA ecx, [eax + eax] or LEA ecx, [eax*2] instead. Of course an output like MUL x, 2 is also possible on a hypothetical architecture without shift, or where shift is slower than multiplication

Compilers are also able to transform complex statements like (x << 1) + (x << 4) + (x << 13) into simpler ones such as a single multiplication by 8210, no more shifts.
Or GCC recognizes (a ^ b) + (a & b) + (a & b) as well as its the inverse condition (a + b) - (a & b) - (a & b) and optimize them to a + b and a ^ b respectively, so it's possible (in the future) that they'll be able to convert the equivalents (a ^ b) + ((a & b) << 1) and (a + b) - ((a & b) << 1) into ADD and XOR without any shifts at all.
See them in action

For the other case there are various examples:

  • Multiplication by a power of 2 is done by a left shift. On x86 there exists the more versatile LEA instruction, so for exponent ⩽ 8 the choice between LEA and SHL depends on the compiler. Array arithmetic also need a lot of multiplication, so a shift is also usually used
  • Multiplication by many other constants can also be optimized to a series of ADD/SUB and shifts if that's faster than the MUL instruction itself. Again in x86 occasionally LEA is used instead of shifts
  • Division by a power of 2 is done by a right shift. For unsigned types it's a simple logical shift. For signed types it's an arithmetic shift followed by some other shifts and ADDs to correct the result (since division rounds towards zero, and arithmetic right shift rounds towards -inf)
  • Division by constants will be optimized into a multiplication by the corresponding multiplicative inverse, which may involve some shifts to round the result
  • Clang even emits an SHR for checking the high bits while doing a division by a non-constant if tuning for microarchitectures from Sandy Bridge onward
  • Bitfield accesses of course need to use a lot of shifts in architectures without efficient bitfield manipulation like x86. See demo
  • ...

Here are some illustrations for the mul/div examples. You can easily see that x*15 is replaced by x*16 - x and x*33 is done by x*32 + x, i.e. (x << 4) - x and (x << 5) + x. Besides, x*8 is optimized to lea eax, [0+rdi*8] or shl edi, 3 depending on the compiler. The mnemonics SAL and SHL are also freely chosen by the compiler

I've also put some non-x86 compilers for comparison, because they don't have LEA but may have other shift-related instructions or different shift capabilities beside the normal shift instructions. You can change between various x86 as well as non-x86 compilers to see the differences between their outputs. Another example that combines multiple things I've said above:

struct bitfield {
    int x: 10;
    int y: 12;
    int z: 10;
};

int f(bitfield b)
{
    int i = b.x*65;
    int j = b.y/25;
    int k = b.z/8;
    return (i << j) + (k >> j);
}

That compiles to

f(bitfield):
        mov     eax, edi
        mov     edx, edi
        sar     edi, 22
        sal     eax, 10
        sal     edx, 6
        sar     eax, 20
        sar     dx, 6
        imul    ecx, eax, 5243
        sar     ax, 15
        sar     ecx, 17
        sub     ecx, eax
        movsx   eax, dx
        mov     edx, eax
        movsx   ecx, cx
        sal     edx, 6
        add     edx, eax
        lea     eax, [rdi+7]
        sal     edx, cl
        test    di, di
        cmovns  eax, edi
        sar     ax, 3
        cwde
        sar     eax, cl
        add     eax, edx
        ret

You can open the Godbolt link to see which instruction corresponds to which line of code in color

In summary: Compilers nowadays are really smart and can output "surprising" results to a normal people. They can emit a shift instruction for pretty much any operators in C. With an optimizing compiler, all bets are off

See also

3
int main (void){
    unsigned int    uin =  0x1000;
    signed int      sin = -0x1000;
   return (uin<<8)+(uin>>8)+(sin<<8)+(sin>>8);   
}

compiled and linked with

cl /Zi /W4 /Od /analyze /nologo salsaar.cpp /link /release

disassembled

:\>cdb -c "uf salsaar!main;q" salsaar.exe | grep -A 20 Reading
0:000> cdb: Reading initial command 'uf salsaar!main;q'
salsaar!main:
01121000 55              push    ebp
01121001 8bec            mov     ebp,esp
01121003 83ec08          sub     esp,8
01121006 c745fc00100000  mov     dword ptr [ebp-4],1000h
0112100d c745f800f0ffff  mov     dword ptr [ebp-8],0FFFFF000h
01121014 8b45fc          mov     eax,dword ptr [ebp-4]
01121017 c1e008          shl     eax,8
0112101a 8b4dfc          mov     ecx,dword ptr [ebp-4]
0112101d c1e908          shr     ecx,8
01121020 03c1            add     eax,ecx
01121022 8b55f8          mov     edx,dword ptr [ebp-8]
01121025 c1e208          shl     edx,8
01121028 03c2            add     eax,edx
0112102a 8b4df8          mov     ecx,dword ptr [ebp-8]
0112102d c1f908          sar     ecx,8
01121030 03c1            add     eax,ecx
01121032 8be5            mov     esp,ebp
01121034 5d              pop     ebp
01121035 c3              ret

note shl and sal are both same (opcodes are same and work same ) shr and sar are not same due to signed unsigned diffferences

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.