[esil] flag updates for three address instructions

[ekiwi]

tl;dr: current flag update behavior for ESIL (update only on = or cmp) seems to make it difficult to implement three address instructions.

Example

Let's look at the ADD (register) instruction from the ARMv7 instruction set. Most encodings (A1, T1 and T3) support Rd, Rn and Rm to be independently specified. This requires the use of the + and = instructions for the ESIL translation, e.g.:

> rasm2 -a arm 'add r1, r2, r3' | rasm2 -a arm -E -
r3,r2,+,r1,=

If one source and the destination register are the same, the += instruction is used in the translation:

> rasm2 -a arm 'add r1, r1, r2' | rasm2 -a arm -E -
r2,r1,+=

Let's compare this with the semantically equivalent instruction add r1, r2, r1:

> rasm2 -a arm 'add r1, r2, r1' | rasm2 -a arm -E -
r1,r2,+,r1,=

On the first look, r2,r1,+= (esil_addeq) and r1,r2,+,r1,= (esil_add followed by esil_eq) seem to do the same thing. For the simple add instruction that is actually true.

Updating Flags

However, if we want to implement the adds instruction which updates the ARM status flags (carry C, negative N, overflow V and zero Z), we will notice that there is an important difference between calling esil_addeq and esil_add followed by esil_eq (all functions are found in libr/anal/esil.c).

src,dest,+= updates the cur and old values that are used to calculate ESIL's built in flags ($c31, $s, $o, $z etc.) like this (from esil_addeq):

esil->old = d;       // d is the value of the destination register
esil->cur = d + s;   // s is the source value

src,dest,= however does the following (from esil_eq):

esil->cur = num2;  // num2 is the source value
esil->old = num;   // num is the old destination value

Problems

1.) it is very confusing that r2,r1,+= and r1,r2,+,r1,= are not semantically equivalent in ESIL
2.) if we do not use a combined binop and assignment instruction (+=, -=, /= etc.) there does not seem to be straight forward way to access the overflow or carry flags [0]

[0]: $s and $z only depend on the result, so they can be calculated from esil->cur only, which is the same for both instruction sequences.

Solution?

In general I would suggest that flags should be updated whenever a binary (+, -, ...) or unary (++, !, ...) operation is performed, not when a register is assigned.
This would allow for r2,r1,+= and r1,r2,+,r1,= to have the same semantics.

However, I can see that this would cause some problems with movs like instructions. Thus one might have to update the flags on = as well. In this case we would end up with ESIL translations like: r1,r2,+,$c,C,=,$s,N,=,$o,V,=,$z,Z,=,r1,= or r1,r2,+,$c,C,=,$o,V,=,r1,=,$s,N,=,$z,Z,=.

Also, changing such a fundamental thing as how the flags are updated would probably introduce a lot of new bugs in stable ESIL translators. I have mostly looked at the ARM translator which is in dire need of repair, but I think that other implementations are actually a lot more complete and well tested.

I would love to hear your ideas on how to implement flag updates for three address instructions in ESIL.

[condret]

If I remember correctly r1,r2,+,r1,= and r2,r1,+= have the same semantics. Both put the old value of r1 into esil->old and the new value into esil->old. Don't use $c, for example use $c31 instead, which checks if a carry from bit 31 happened, assuming the esil->cur is the result of an addition or a similar operation. Use $b32 for carry-flag, when you do subtraction, it checks if there was a borrow from bit 32.
why was it made like this?
To be ready for the future. Some architectures like Z80 have a half-carry flag, which can be checked with $c3 for 8-bit dst and $c7 for 16-bit dst. I strongly believe, that there are CPUs out there, that have very weird carry-checks ($c23 maybe), and we need the esil-design to support them all, by just creating a plugin, and not rewriting esil all the time

[ekiwi]

If I remember correctly r1,r2,+,r1,= and r2,r1,+= have the same semantics. Both put the old value of r1 into esil->old and the new value into esil->old.

Yes you are right, I picked a bad example.

Let's focus on adds r1, r2, r3 which is currently translated to: r3,r2,+,r1,=,$z,zf,=

How should we update the missing flags (V, C and N) in this case?

Don't use $c, for example use $c31 instead, which checks if a carry from bit 31 happened, assuming the esil->cur is the result of an addition or a similar operation

Ah sorry, I simplified a bit too much by writing $c instead of $c31.
The problem still stands: $c31 will only be correct if esil->cur is the result of an addition and if esil->old contains one of the operands of the addition. This does not seem to be the case for r3,r2,+,r1,=. (In this case esil->old will contain the old value of r1 which is unrelated to the addition)

[condret]

this is hard, maybe a design flaw. I need to think about it. One solution would be r3,r1,=,r3,r2,+,r1,=. The problem with your approach for this problem is, that esil breaks, when you do tricks with the stack for what ever reason r2,r1,+=,r2,r3,+,%c31,cf,=,r3,=. I really need to think about this for a few days

[ekiwi]

I really need to think about this for a few days

Great. I am looking forward to hearing your thoughts.

Btw. the current ESIL semantics already need to disable updating cur/old when assigning flag registers:

if (ret && r_anal_esil_get_parm_type (esil, src) != R_ANAL_ESIL_PARM_INTERNAL) { //necessary for some flag-things
	esil->cur = num2;
	esil->old = num;
	esil->lastsz = esil_internal_sizeof_reg (esil, dst);
}

This might be worth considering when trying to come up with a solution to the problem we are trying to solve.

[condret]

uhm, afaik, esil does not update old and cur if you read from internal flags, or does it?

Well, on my todo-list is a new abstract esil, aesil, that has no specific registers. this requires easier data-flow analysis given by the data-structures, that esil uses. That would possibly fix your problem. Radeco already provides SSA-esil, which results in the same. Creating new esil-specs therefore might be pointless work. For now I highly suggest going for r3,r1,=,r3,r2,+,r1,=, since it does the correct computation. Yep, I agree, this could be better, but the outcome of changing this, might break the support for other CPUs. Esil is intended to support them all, and it does that so far so good. Not sure if this is my final position to this.

[condret]

here is an idea: Esil provides this functionallity of setting custom-ops, not just for adding new operations. You can also override operations, if this is required for some reason. This might be the case here, since this wouldn't affect other plugins. Every anal-plugin has a .esil_init and a .esil_fini, which get called on init and fini of esil. Replace the ops in the .esil_init and it should do what you want. .esil_fini must be set, bc esil_init allows allocating custom data-structures, and we want ppl not to forget freeing them.

If this does not cause any problems for this plugin, then we can discuss making this change default behaviour.

[condret]

ok, so, I looked at the data-sheet, and I'm pretty sure, that we don't need to change esil parser for this, just generate more sophisticated esil expressions in the arm plugin