ESP32 Forum

Since Xtensa cores do not have usual FLAGS (or somwhere called status) register, which usually contains C - carry bit (for add instructions)/ B -(borrow bit for sub instructions) O - (overflow bit) S - (sign bit) etc which are affected after any integer arithmetic operation, writting of routines of 64bit arithmetic on 32bit cores which always take the same execution path (not involving any branching instruction) is quite challanging. I found that C code which involve two 64bit arrguments will always be compiled using some of those branch instructions at place where carry (in the case of addition/subtraction) has to be set to 1 or cleared to 0. It means that such routine executes differently depending on values of two arguments which are involved in addition. For example:

https://godbolt.org/z/6WfPTdh96

Is there a way to force compiler to generate "always the same execution path" code without branch instructions for 64bit arithmetic. In that example, a14 register is always preloaded with value 1. Then comparation in between a10 and a9 is performed, telling should value of a14 has to stay at 1 by skipping next instruction or it should be 0 by executing next instruction. And that makes divergent paths of execution depending on input values, because for some pair of values that SKIP is going to be performed while for other pairs skip is not performed but one extra instruction is executed. That means, execution time of routine, depends on input values which is not acceptable in critical synchronization routines which involve 64bit math.

I know I can write "by hand" such a code by replacing that part with something like:
Off course, for performance reasons, those two instructions should not appear one after another to avoid stale or lock states of srl instruction which has to wait the result of previous operation. Previous example allows us to nest them like this

(I wrote this as an example while writing this question just to illustrate the question. I didn't test it, however there is no reason of why it shouldn't work)

But, is there a way to force the compiler to generate such a non-branching code of int64 arithmetic keeping routine execution time constant and independent on input values?

Probably not.
Even if gcc knows an alternative, branchless variant of an algorithm, there's not much you can do to force it to use one algorithm or the other.

However, it seems that only recently the SALT[ U ] instruction ("Set AR if Less Than [Unsigned]") was added to the ISA (core architecture) documentation. Might be worth checking out to replace with as long as gcc isn't yet aware of that instruction.

I recommend to actually measure execution times though instead of guessing which instruction sequence would be faster. And maybe look into finding an algorithm which doesn't depend on +/- 1 clock cycle of runtime.

Edit:
You can also try 'manually' coding in 32 bits. gcc is smart enough to not generate any extra instructions for things like "(uint32_t)(u64 >> 32)" or "((uint64_t)u32)<<32".

Thanks for fast response.
Yes, sgtu on RISC-V (Store Great Than) [unsigned] is conditional MOV and if you add other 32bit targets, gcc compiler of the same C code generates code without branch instruction for all of them. The same is on RISC-V or MIPS, it uses that conditional move. On x86-32 there is borrow flag and it uses sub/sbb instructions. So BRANCH exists only on Xtensa even both LX6 and LX7 cores are also cappable of conditional mov instructions.

https://godbolt.org/z/s1sYPdE38

In Xtensa documentation about conditional MOV

The conditional move instructions shown in Table 3–19 are used for branch avoidance.

MOVEQZ RRR Conditional move if zero
MOVNEZ RRR Conditional move if non-zero
MOVLTZ RRR Conditional move if less than zero
MOVGEZ RRR Conditional move if greater than or equal to zero

but there is no explicit timing mentioned.

So why gcc doesn't use those conditional move instructions (like on other 32bit platforms) but place branch (which produce divergent path, dependent on input values)? Is there any switch in compiling to turn on usage of those conditional move instructions? Or some settings in xtensa-config.h?

djixon wrote: ↑

Sun Apr 28, 2024 11:31 pm

So why gcc doesn't use those conditional move instructions (like on other 32bit platforms) but place branch (which produce divergent path, dependent on input values)? Is there any switch in compiling to turn on usage of those conditional move instructions? Or some settings in xtensa-config.h?

In the case of "u64 - u64" there's probably no "fast" way to use the conditional move instructions because they only compare against 0.
gcc does know/use them in other cases though: https://godbolt.org/z/jhcvhK5av

P.S.: gcc's instruction cost model for both Xtensa and RISC-V in places seems to be somewhat off for the ESP32s, which makes gcc sometimes 'optimize' in the wrong direction. (https://godbolt.org/z/xKWq91jcP)

In the case of "u64 - u64" there's probably no "fast" way to use the conditional move instructions because they only compare against 0.

Well, in the case of 64 bit addition/subtraction operations, the value of the carry/borrow bit can be only 0 or 1 (depends only on lower 32 bits of both operands), so that should be an ideal case to use conditional move instruction instead those compare-and-branch which produce divergent execution paths for different operands values.

djixon wrote: ↑

Sun Jun 02, 2024 12:38 pm

In the case of "u64 - u64" there's probably no "fast" way to use the conditional move instructions because they only compare against 0.

Well, in the case of 64 bit addition/subtraction operations, the value of the carry/borrow bit can be only 0 or 1 (depends only on lower 32 bits of both operands), so that should be an ideal case to use conditional move instruction

Uhm... no.
How would one of Xtensa's conditional moves help in determining if the carry is 1 or 0?