Feature Request: Add `INT_ROTATE` PCode operation

[LukeSerne]

Is your feature request related to a problem? Please describe.
While reverse engineering a PowerPC program, I regularly come across the rlwinm instruction. This instruction (documented on page 501 of 6xx_pem.pdf) can perform a bit-rotate followed by a binary AND. This instruction is quite heavily used, for example for bit-rotating an integer, extracting bits from a bitfield and bit-shifting an integer. Additionally, the instruction frequently features in compiler optimisations to avoid branches.

Unfortunately, the current pcode implementation of this instruction uses a combination of INT_OR, INT_SUB, INT_LEFT and INT_RIGHT. While this is functionally correct, when the instruction is used as part of a larger structure that can be optimised, the decompiler often fails to recognise the rotate and thus the opportunity for optimisation.

I noticed bit-rotation is quite a common operation across the architectures currently supported by Ghidra. For instance, PowerPC has rlwinm, ARM has ror, x86 has ROR, MIPS32 has ROTR, z80 has RL and 68k has ROR. While many architectures include separate instructions for left-rotate and right-rotate, only one rotate instruction is necessary, since the other instruction can be modeled by negating the shift amount. Most of these architectures have several not just one, but several instructions that perform a bit rotate. As such, this new PCode instruction would be widely applicable.

Additionally, having a separate instruction for bit rotation allows multiple decompiler rules to simplify patterns involving bit rotations without each having to attempt to recognise the relatively complex structure that arises from the sequence. Then, there could be a single rule to convert the sequence of shifts to the new rotate instruction, which avoids several different rules having to detect bit-rotations. This would avoid code duplication, and it would also be more efficient.

Finally, INT_ROTATE(x, y) is arguably much clearer to human analysts than the equivalent (x << y) | (x >> (32 - y)), especially if x and y are more complicated expressions.

Describe the solution you'd like
I would like a new PCode op to be added, that takes 2 varnodes as parameters. I propose the name INT_ROTATE( V, n ). The first parameter is the value being rotated, and the second varnode specifies the rotation amount. This would be equivalent to (V << n) | (V >> (8 * |V| - n)), where |V| denotes the size of the varnode V in bytes.

Describe alternatives you've considered
An alternative is to not introduce this new PCode operation, and let the decompiler rules that need to deal with bit rotations just detect those cases themselves. However, I think that will lead to code duplication and less efficient decompilation. The decompiled output will also be harder to understand for analysts whenever bit rotations are not simplified away.

Additional context
An example of some PowerPC instructions that Ghidra currently struggles to simplify:

7c 00 00 34     cntlzw     r0, r0
38 60 00 01     li         r3, 0x1
5c 63 07 fe     rlwnm      r3, r3, r0, 0x1f, 0x1f
4e 80 00 20     blr

This corresponds to return r0 < 0 (edit: oops, it's actually return r0 <= 0 - just goes to show how tricky these expressions are for humans to understand), but ghidra currently decompiles this to:

  return (bool)(((byte)(1 << (LZCOUNT(r0) & 0x1fU))
                | (byte)(1 >> 0x20 - (LZCOUNT(r0) &
                                     0x1fU))) & 1);

While the decompiled code is functionally correct, it is nearly impossible to see that the code is testing for the sign bit of r0. The decompiler misses a few simplification steps:

1. The rotate of 1 by LZCOUNT(r0) & 0x1fU, followed by the & 1, which is then cast to a bool, can be simplified to LZCOUNT(r0) & 0x1fU == 0, since only a rotate amount of 0 can ensure a 1 bit ends up in the ones-position of the result.
2. LZCOUNT(r0) & 0x1fU can be simplified to just LZCOUNT(r0) == 0 || LZCOUNT(r0) == 32, since the varnode representing r0 is 4 bytes big, so LZCOUNT can never return a value that has any bits masked off.
3. LZCOUNT(r0) == 0 implies that r0 s>> 31 != 0, since r0 is 32 bits wide.
4. LZCOUNT(r0) == 32 implies r0 == 0, since r0 is 32 bits wide.

The decompiler can simplify r0 s>> 31 != 0 to r0 < 0 by RuleTestSign. The expression r0 < 0 || r0 == 0 is then simplified to r0 <= 0 by RuleLessEqual.

Note that step 1 would be much simpler to recognise and implement a rule for if there was a dedicated INT_ROTATE PCode instruction. There would be no need for step 2 if the semantics of INT_ROTATE were that it automatically masks the rotation amount by the number of bits in the value to be rotated, since the & 0x1f is introduced by the Pcode translation of rlwnm only because this masking is required for the rlwnm instruction. And if there is no INT_AND in the raw Pcode, there is also no need for the decompiler to simplify it away.

[ghidracadabra]

This is definitely something to consider. Do you have any insight into which PowerPC compilers emit such code (and when they would emit it)? I'm investigating which rotate-based simplifications would be worth adding to the decompiler.

[Neui]

For 32-bit PowerPC, I can get gcc to output rlwinm instructions when: Using bitfields, ANDing bits, and comparing to constant values.

Example C program (compiled object file, use PowerPC 32-bit as language):

// powerpc-eabi-gcc -O3 powerpc-bitfields.c -c -o powerpc-bitfields.o
struct bitfield {
    int a: 7;
    int b: 3;
    int c: 1;
};

int bitfield_get_a(struct bitfield *bf) {
    return bf->a;
}
int bitfield_get_b(struct bitfield *bf) {
    return bf->b;
}
int bitfield_get_c(struct bitfield *bf) {
    return bf->c;
}

void bitfield_set_a(struct bitfield *bf, int value) {
    bf->a = value;
}
void bitfield_set_b(struct bitfield *bf, int value) {
    bf->b = value;
}
void bitfield_set_c(struct bitfield *bf, int value) {
    bf->c = value;
}

_Bool is_high_bit_set(unsigned int value) {
    return value & 0x80000000u;
}
_Bool is_low_bit_set(unsigned int value) {
    return value & 0x00000001u;
}

_Bool is_zero(unsigned int value) {
    return value == 0;
}
_Bool is_one(unsigned int value) {
    return value == 1;
}
_Bool is_two(unsigned int value) {
    return value == 2;
}

_Bool is_max(unsigned int value) {
    return value == 0xFFFFFFFF;
}
_Bool is_max_1(unsigned int value) {
    return value == 0xFFFFFFFF-1;
}
_Bool is_max_2(unsigned int value) {
    return value == 0xFFFFFFFF-2;
}

_Bool is_greater_than_zero(int value) {
    return value > 0;
}
_Bool is_less_than_zero(int value) {
    return value < 0;
}

_Bool is_greater_than_one(int value) {
    return value > 1;
}
_Bool is_less_than_one(int value) {
    return value < 1;
}

_Bool is_greater_than_minusone(int value) {
    return value > -1;
}
_Bool is_less_than_minusone(int value) {
    return value < -1;
}

Assembly output

                            ;undefined bitfield_get_a()
.text:00010000  80630000        lwz         r3,0x0(r3)                              
.text:00010004  7c63ce70        srawi       r3,r3,0x19                              
.text:00010008  4e800020        blr                                                 
                            ;undefined bitfield_get_b()
.text:0001000c  80630000        lwz         r3,0x0(r3)                              
.text:00010010  54633830        rlwinm      r3,r3,0x7,0x0,0x18                      
.text:00010014  7c63ee70        srawi       r3,r3,0x1d                              
.text:00010018  4e800020        blr                                                 
                            ;undefined bitfield_get_c()
.text:0001001c  80630000        lwz         r3,0x0(r3)                              
.text:00010020  5463502a        rlwinm      r3,r3,0xa,0x0,0x15                      
.text:00010024  7c63fe70        srawi       r3,r3,0x1f                              
.text:00010028  4e800020        blr                                                 
                            ;undefined bitfield_set_a()
.text:0001002c  a1230000        lhz         r9,0x0(r3)                              
.text:00010030  5089482c        rlwimi      r9,r4,0x9,0x0,0x16                      
.text:00010034  b1230000        sth         r9,0x0(r3)                              
.text:00010038  4e800020        blr                                                 
                            ;undefined bitfield_set_b()
.text:0001003c  a1230000        lhz         r9,0x0(r3)                              
.text:00010040  508935f2        rlwimi      r9,r4,0x6,0x17,0x19                     
.text:00010044  b1230000        sth         r9,0x0(r3)                              
.text:00010048  4e800020        blr                                                 
                            ;undefined bitfield_set_c()
.text:0001004c  a1230000        lhz         r9,0x0(r3)                              
.text:00010050  50892eb4        rlwimi      r9,r4,0x5,0x1a,0x1a                     
.text:00010054  b1230000        sth         r9,0x0(r3)                              
.text:00010058  4e800020        blr                                                 
                            ;undefined is_high_bit_set()
.text:0001005c  54630ffe        rlwinm      r3,r3,0x1,0x1f,0x1f                     
.text:00010060  4e800020        blr                                                 
                            ;undefined is_low_bit_set()
.text:00010064  546307fe        rlwinm      r3,r3,0x0,0x1f,0x1f                     
.text:00010068  4e800020        blr                                                 
                            ;undefined is_zero()
.text:0001006c  7c630034        cntlzw      r3,r3                                   
.text:00010070  5463d97e        rlwinm      r3,r3,0x1b,0x5,0x1f                     
.text:00010074  4e800020        blr                                                 
                            ;undefined is_one()
.text:00010078  68630001        xori        r3,r3,0x1                               
.text:0001007c  7c630034        cntlzw      r3,r3                                   
.text:00010080  5463d97e        rlwinm      r3,r3,0x1b,0x5,0x1f                     
.text:00010084  4e800020        blr                                                 
                            ;undefined is_two()
.text:00010088  68630002        xori        r3,r3,0x2                               
.text:0001008c  7c630034        cntlzw      r3,r3                                   
.text:00010090  5463d97e        rlwinm      r3,r3,0x1b,0x5,0x1f                     
.text:00010094  4e800020        blr                                                 
                            ;undefined is_max()
.text:00010098  38630001        addi        r3,r3,0x1                               
.text:0001009c  7c630034        cntlzw      r3,r3                                   
.text:000100a0  5463d97e        rlwinm      r3,r3,0x1b,0x5,0x1f                     
.text:000100a4  4e800020        blr                                                 
                            ;undefined is_max_1()
.text:000100a8  38630002        addi        r3,r3,0x2                               
.text:000100ac  7c630034        cntlzw      r3,r3                                   
.text:000100b0  5463d97e        rlwinm      r3,r3,0x1b,0x5,0x1f                     
.text:000100b4  4e800020        blr                                                 
                            ;undefined is_max_2()
.text:000100b8  38630003        addi        r3,r3,0x3                               
.text:000100bc  7c630034        cntlzw      r3,r3                                   
.text:000100c0  5463d97e        rlwinm      r3,r3,0x1b,0x5,0x1f                     
.text:000100c4  4e800020        blr                                                 
                            ;undefined is_greater_than_zero()
.text:000100c8  3923ffff        subi        r9,r3,0x1                               
.text:000100cc  7d2318f8        nor         r3,r9,r3                                
.text:000100d0  54630ffe        rlwinm      r3,r3,0x1,0x1f,0x1f                     
.text:000100d4  4e800020        blr                                                 
                            ;undefined is_less_than_zero()
.text:000100d8  54630ffe        rlwinm      r3,r3,0x1,0x1f,0x1f                     
.text:000100dc  4e800020        blr                                                 
                            ;undefined is_greater_than_one()
.text:000100e0  3923fffe        subi        r9,r3,0x2                               
.text:000100e4  7d2318f8        nor         r3,r9,r3                                
.text:000100e8  54630ffe        rlwinm      r3,r3,0x1,0x1f,0x1f                     
.text:000100ec  4e800020        blr                                                 
                            ;undefined is_less_than_one()
.text:000100f0  3923ffff        subi        r9,r3,0x1                               
.text:000100f4  7d231b78        or          r3,r9,r3                                
.text:000100f8  54630ffe        rlwinm      r3,r3,0x1,0x1f,0x1f                     
.text:000100fc  4e800020        blr                                                 
                            ;undefined is_greater_than_minusone()
.text:00010100  7c6318f8        nor         r3,r3,r3                                
.text:00010104  54630ffe        rlwinm      r3,r3,0x1,0x1f,0x1f                     
.text:00010108  4e800020        blr                                                 
                            ;undefined is_less_than_minusone()
.text:0001010c  39230001        addi        r9,r3,0x1                               
.text:00010110  7d231838        and         r3,r9,r3                                
.text:00010114  54630ffe        rlwinm      r3,r3,0x1,0x1f,0x1f                     
.text:00010118  4e800020        blr                                                 

Note that it seems gcc doesn't use cntlzw (LZCOUNT) for the is less than 0 function, unlike what the issue opener shows, but uses them for the equal operator (which decompiles nicely).

Decompiler output (without manual modifications)

int bitfield_get_a(int *param_1)
{
  return *param_1 >> 0x19;
}

int bitfield_get_b(uint *param_1)
{
  return (int)(*param_1 << 7 | *param_1 >> 0x19) >> 0x1d;
}

int bitfield_get_c(uint *param_1)
{
  return (int)(*param_1 << 10 | *param_1 >> 0x16) >> 0x1f;
}

void bitfield_set_a(ushort *param_1,int param_2)
{
  *param_1 = (ushort)(param_2 << 9) | *param_1 & 0x1ff;
  return;
}

void bitfield_set_b(ushort *param_1,int param_2)
{
  *param_1 = (ushort)(param_2 << 6) & 0x1c0 |
             *param_1 & 0xfe3f;
  return;
}

void bitfield_set_c(ushort *param_1,int param_2)
{
  *param_1 = (ushort)(param_2 << 5) & 0x20 |
             *param_1 & 0xffdf;
  return;
}

uint is_high_bit_set(uint param_1)
{
  return param_1 >> 0x1f;
}

uint is_low_bit_set(uint param_1)
{
  return param_1 & 1;
}

bool is_zero(int param_1)
{
  return param_1 == 0;
}

bool is_one(int param_1)
{
  return param_1 == 1;
}

bool is_two(int param_1)
{
  return param_1 == 2;
}

bool is_max(int param_1)
{
  return param_1 == -1;
}

bool is_max_1(int param_1)
{
  return param_1 == -2;
}

bool is_max_2(int param_1)
{
  return param_1 == -3;
}

uint is_greater_than_zero(uint param_1)
{
  return ~(param_1 - 1 | param_1) >> 0x1f;
}

uint is_less_than_zero(uint param_1)
{
  return param_1 >> 0x1f;
}

uint is_greater_than_one(uint param_1)
{
  return ~(param_1 - 2 | param_1) >> 0x1f;
}

uint is_less_than_one(uint param_1)
{
  return (param_1 - 1 | param_1) >> 0x1f;
}

uint is_greater_than_minusone(uint param_1)
{
  return ~param_1 >> 0x1f;
}

uint is_less_than_minusone(uint param_1)
{
  return (param_1 + 1 & param_1) >> 0x1f;
}