Fast way to get a valid imm num for arm mov?

Question

Arm mov has a limitation that the immediates must be an 8bit rotated by a multiple of 2, we can write:

mov ip, #0x5000

But we cannot write that:

mov ip, #0x5001

The 0x5000 can be split as 0x5000 + 1, my means, the sum of a valid immediate number and a small number.

So for a given 32bit number, how to find the closest valid immediate number fast? Like this:

uint32 find_imm(uint32 src, bool less_than_src) {
...
}

// x is 0x5000
uint32 x = find_imm(0x5001, true);

Answer 1

There is not a straightforward rule or function for finding ways to construct values. Once a value exceeds what can be loaded easily from immediate values, you usually load it by defining it in the data section and loading it from memory, rather than constructing it from immediate values.

If you do want to construct a value from two immediate values, you must consider a variety of operations, including:

• Adding two immediates.
• Subtracting two immediates.
• Multiplying two immediates.
• More esoteric instructions, such as some of the “SIMD” instructions that split 32-bit registers into multiple lanes.

If you must go to three immediate values, there are more combinations. One can find some patterns in the possibilities that reduce the search, but some portion of it remains a “brute force” search. Generally, there is no point in using complicated instructions sequences, since you can simply load the data from a prepared location in memory.

The ARM assembler has an instruction form to assist this:

LDR Rd, =const

When the assembler sees this, it places the const value in the literal pool and generates an instruction to load the value from the pool. If you are using a different assembler, it might not have the same instruction form, but you can write the necessary code manually.

Answer 2

It is quite simple, look at the distance between the ones. 0x5001 = 0b101000000000001. 15 significant digits, so it will take you two instructions at 8 bits of immediate per. Also remember to put a rotate in your test, if there are enough zeros 0x80000001 and you rotate that around 0x88000000 or 0x00000003 that is only two significant digits from a distance between the ones measurement. So take the immediate, perform a distance between the ones type test, rotate one step, perform the test again, and repeat until all the possible (counter-)rotations have happened and go with one of the ones with the smallest number of instructions/immediates.

gnu as already does this and gas is open source so you can just go get their code if you prefer. When you use the load address trick:

ldr rd,=const

If that const can be resolved in a single move immediate instruction then it encodes it as a

mov rd,#const

if it cant then it tries to find a location to put the word and encodes it as a pc relative load:

ldr rd,[pc,#offset]
...
.word const