Messy decompilation of add with carry

[rimwall]

Context:

• I have not written a processor spec, so have a rudimentary understanding of the various files
• I'm using the M32R processor spec from here: https://github.com/ripnet/ghidra-m32r
• It generally works fine, but the Ghidra decompiler output for ADDX (add with carry) seems to be very messy
• I'm wondering how I fix this - for example the sh2 processor bundled with Ghidra has a clean decompilation of add with carry
• I tried changing the M32R *.sinc definition to be similar to the sh2 definition (and re-compiling the language), but that didn't help

The M32R *.sinc definition is:

:ADDX	Rdest, Rsrc				is op1=0 & Rdest; op3=9 & Rsrc {
	local tmp = Rdest + Rsrc;
	local tmp2 = tmp + zext($(C));
	$(C) = (carry(Rdest, Rsrc) | carry(tmp, tmp2));
	CBR = zext(carry(Rdest, Rsrc) | carry(tmp, tmp2));
	Rdest = Rdest + Rsrc + CBR;
}

The Ghidra disassembler is clean...

                   LAB_0004e560                                    XREF[1]:     0004e548(j)  
        0004e560 a0 9d d6 24     LDUB       R0,@DAT_00805624                                 = ??
        0004e564 50 5a           SLLI       R0,#0x1a
        0004e566 00 90           ADDX       R0,R0
        0004e568 7d 05           BNC        LAB_0004e57c

...but the decompiler output is messy...

      uVar1 = (uint)DAT_00805624 * 0x4000000;
      uVar4 = (uint)DAT_00805624 * 0x8000000;
      if ((byte)(CARRY4(uVar1,uVar1) | CARRY4(uVar4,uVar4 + ((DAT_00804885 & 1) != 0))) == 0) {

Any help greatly appreciated!

[GhidorahRex]

I'm not familiar with the processor, but the description in the software manual looks pretty straight-forward. I think the description here is incorrect.

ADDX adds Rsrc and C to Rdest, and puts the result in Rdest.
The condition bit (C) is set when the addition result cannot be represented by a 32-bit unsigned integer; otherwise it is cleared.

This constructor here doesn't look right at all. CBR is based on the carry of the complete operation, but somehow it's being added at the end of the instruction. It should probably work better if you replaced the last line with Rdest = tmp2;. Also, the carry flag should probably be based on logical or, not bitwise or, although in theory it shouldn't matter.

Here's how I would re-write the operation:

:ADDX	Rdest, Rsrc				is op1=0 & Rdest; op3=9 & Rsrc {
	local tmp = Rdest + Rsrc;
	local tmp2 = tmp + zext($(C));
	$(C) = carry(Rdest, Rsrc) || carry(tmp, tmp2);
	Rdest = tmp2;
}

[rimwall]

Hi, thanks, much appreciated, I gave it a go, the decompiler output is different, but unfortunately still messy...

diassembly:

        0005dec8 a0  9d  d6  20    LDUB       R0,@DAT_00805620                                 = ??
        0005decc 50  59           SLLI       R0,#0x19
        0005dece 00  90           ADDX       R0,R0

decompiler:

  uVar3 = (uint)DAT_00805620 * 0x2000000;
  uVar2 = (uint)DAT_00805620 * 0x4000000;
  bVar6 = CARRY4(uVar3,uVar3) || CARRY4(uVar2,uVar2 + (in_PSW & 1));

An sh4 example looks like this...

disassembly:

        00002380 45  11           cmp/pz     r5
        00002382 e5  00           mov        #0x0 ,r5
        00002384 30  5e           addc       r5,r0

decomplier:

param_1 = (-1 < param_1) + 0x7fffffff;

Could it have something to do with the way the flag is defined?

In m32r it's like this...

define register offset=0x40 size=4 [ PSW CBR SPI SPU CR4 CR5 BPC FPSR PC];

@define C		"PSW[0,1]"	

In superH4 it's like this...

# SR component register fields (pseudo)
define register offset=1536 size=1 [
	MD    RB    BL    FD    M     Q     IMASK S     T
];

@define T_FLAG  "T"

...and...

:addc M_0t,N_0t             is OP_0=0x3 & N_0t & M_0t & OP_1=0xe {
	local Tcopy:4 = zext($(T_FLAG));
	$(T_FLAG) = carry( N_0t, M_0t );
	local result:4 = N_0t + M_0t;
	$(T_FLAG) = $(T_FLAG) || carry( result, Tcopy );
	N_0t = result + Tcopy;	
}

(I tried duplicating the 5 calculation steps above in the M32R file, but got the same messy decomplier output)

Thanks again!

[GhidorahRex]

You could definitely try redefining the flag - you'll have to re-import the binary since register changes are messy without an upgrade script - you might want to just import a copy to test with if you've done significant work already. We usually recommend using individual pseudo-registers for flags unless absolutely necessary, since the IN_PSW & 1 part is pretty ugly. That might show up in superH (not SH4) binaries if ADDC is present too, but I'm not sure.

For this processor, that should work absolutely fine, with the exception of having to add a bit of extra work to CLRPSW and SETPSW to update the flags, and probably needing macros for packing and unpacking PSW whenever it's read or written with MVTC and MVFC. Although if those instructions aren't of concern to you at the moment, you can just test the change to the register:

define register offset=0x80 size=1 [ C ];
@define C "C"

[rimwall]

Thanks again. I tried a different C define, but still messy...

disassembly:

        000048a0 a1 cd fd 7c     LD         R1,@fp(DAT_00807d7c)                             = ??
        000048a4 22 91           LDUB       R2,@R1
        000048a6 52 5e           SLLI       R2,#0x1e
        000048a8 02 92           ADDX       R2,R2
        000048aa 7d 03           BNC        LAB_000048b4

decompiler:

  uVar6 = (uint)*DAT_00807d7c * 0x40000000;
  uVar4 = (uint)*DAT_00807d7c * -0x80000000;
  uVar1 = uVar4 + in_C;
  bVar2 = CARRY4(uVar6,uVar6);
  bVar3 = CARRY4(uVar4,uVar1);
  uVar7 = bVar2 || bVar3;
  if (bVar2 || bVar3) {

Kinda stuck for ideas on what to try next. Might just have to live with it. Ironically, for ADDX, I find it easier to read the diassembler output than the decomplier output... the above example is just testing whether the lowest bit at 0x807d7c is set.

[mumbel]

Honestly don't recall ever seeing a carry instruction in any of the day to day RE I do, just from implementing SLEIGH, so I don't know how bad that really looks in terms of the PCODE output from an instruction, or if the high pcode/decompiler cleans up a lot. I have sometimes wondered if the {s}carry could be 3 operand functions and see if it could be handled better in PCODE without having to calculate the carry to see if that generates a carry with either of the initial operands.

[GhidorahRex]

carry(input1,input2)||carry(result,cflag) is how we typically represent the carry operation for add-with-carry. There's only a couple processors where we don't use that for I'm suspicious of. I haven't gone through all the steps to show that those are right or wrong however.

@rimwall Your code looks like it doesn't know what the input carry flag is. Perhaps the decompiler could do some simplification if it knew that it was 0 or 1 coming in. If it's just testing if the lowest bit was set, the carry flag should be set to 1 here?

[rimwall]

As a follow up, I have figured out the following:

• this issue arises where the code is testing the nth bit of a byte (where n = 7 (highest) to 0 (lowest)). Let's assume the byte is in R0.
• to perform the test, the code first does a SLLI on R0 to move the nth bit into the highest position (bit31). For example, to test bit0 the instruction would be SLLI R0, #0x1f
• the next instruction is an ADDX with itself. In this example ADDX R0, R0. If the carry flag gets set, the code has determined that the nth bit was set. Conversely, if the carry flag doesn't get set, the code has determined that the nth bit was not set. This approach effectively ignores the incoming value of the carry flag because the carry flag (in bit0) is too far below the bits being tested to affect the result (after the SLLI the bits being tested sit in bit positions 31 to 24) .

I have tried to implement this in the M32R language based on the following example from the language docs. However, I can't seem to get it to work:

Example from the language docs:

7.4.7. Advanced Constraints
:xor r1,r2 is opcode=0xcd & r1 & r2 { r1 = r1 ^ r2; }
:clr r1    is opcode=0xcd & r1 & r1=r2 { r1 = 0; }
The above example illustrates a situation that does come up occasionally. A processor uses an exclusive-or instruction to clear a register
by setting both operands of the instruction to the same register. The first line in the example illustrates such an instruction. However, 
processor documentation stipulates, and analysts prefer, that, in this case, the disassembler should print a pseudo-instruction clr. The
distinguishing feature of clr from xor is that the two fields, specifying the two register inputs to xor, are equal. The easiest way to specify
this special case is with the general constraint, “r1 = r2”, as in the second line of the example. The SLEIGH compiler will implement this by
enumerating all the cases where r1 equals r2, creating as many states as there are registers. But the specification itself, at least, remains
compact.

The changes I have made to the m32r.sinc file are as follows. I had to introduce a "_B" series of alternate fields so that the equality Rdest_B=Rsrc_B was within the same token - it would not compile if the equality acted on two tokens on either side of a concatenation operator (;).

define token data16 (16)
	imm16	= (0,15)
	rel16	= (0,15) signed
	simm16	= (0,15) signed
	Rdest_B = (0,3)
	op1_B   = (4,7)
	Rsrc_B  = (8,11)
	op3_B   = (12,15)
;

attach variables [ Rdest_B Rsrc_B ] [ R0 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 FP R14 SP];

:ADDX	Rdest_B, Rsrc_B				is op1_B=0 & Rdest_B & op3_B=9 & Rsrc_B {
	local tmp = Rdest_B + Rsrc_B;
	local tmp2 = tmp + zext($(C));
	$(C) = carry(Rdest_B, Rsrc_B) || carry(tmp, tmp2);
	Rdest_B = tmp2;
	CBR = zext($(C));
}


:TST31 Rdest_B 				is op1_B=0 & Rdest_B & op3_B=9 & Rdest_B=Rsrc_B {
	$(C) = (Rdest_B[31,1] == 1);
}

Updated files here: https://github.com/rimwall/ghidra-m32r

The above changes compile ok. However, Ghidra is unable to disassemble the instruction. The example below with a value of 0x00 0x90 should disassemble to TST31 R0. But Ghidra doesn't recognise the bit pattern. What am I doing wrong?

[rimwall]

Aha! figured it out. Will post solution shortly

[rimwall]

Just had the token bits swapped round. Correct definition is:

define token data16 (16)
	imm16	= (0,15)
	rel16	= (0,15) signed
	simm16	= (0,15) signed
	Rdest_B = (8,11)
	op1_B   = (12,15)
	Rsrc_B  = (0,3)
	op3_B   = (4,7)
;

And changed the instruction logic to the following to make the decomplier much cleaner:

:TSTb31 Rdest_B is op1_B=0 & Rdest_B & Rdest_B=Rsrc_B & op3_B=9 {
	local tmp = Rdest_B & (1 << 31);
	$(C) = (tmp != 0);
	CBR = zext(tmp != 0);
}

Now it works and is much more readable!

Messy decompilation problem solved.

[fenugrec]

Now it works and is much more readable!

Cool ! can you paste an example ?

[rimwall]

Sure.

Before:

After:

Note that this approach is specific to the compiler approach for the code that I'm working with. Because that compiler seems to do bit testing of a byte via a SLLI Rx, #imm8 followed by an ADDX Rx, Rx. I don't know why the compiler wasn't using the BTST instruction. Fortunately, the compiler wasn't producing ADDX Rx, Rx in any other circumstances, so this approach works for the code I'm working with. It is possible that other compilers would generate ADDX Rx, Rx where the bottom bit of Rx cannot be guaranteed to be zero. In which case the added instruction TSTb31 would result in disassembly and decompilation errors.

In the code I'm working on, Rx is never used after the ADDX, but I've improved the TSTb31 instruction just in case:

:TSTb31 Rdest_B is op1_B=0 & Rdest_B & Rdest_B=Rsrc_B & op3_B=9 {
	local tmp = Rdest_B & (1 << 31);
	Rdest_B = Rdest_B << 1;
	$(C) = (tmp != 0);
	CBR = zext(tmp != 0);
}