Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

ARM immediate value encoding

alisdair.mcdiarmid.org

Post reply on HN
Print view View original

21–30 of 71 posts

Re: ARM immediate value encoding

#23

Post by lectrick »

This is clever. However...

The problem as I see it with this sort of cleverness is that it's difficult to optimize to this. It leads to quite variable best-case and worst-case scenarios and general unpredictability. As, say, a C programmer and not a compiler designer, you might unintentionally pick lots of values that won't fit into the "immediate" scheme (worst-case). Or you might force your design to use numbers that DO fit into this scheme (best-case, but a bleed of lower-level design decisions affecting higher-level design decisions).

Re: ARM immediate value encoding

#24

Post by pointernil »

wreegab wrote: post #22

I was left with one question after reading the article: the purpose of the condition field in the instruction.

http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc....

"Almost all ARM instructions can include an optional condition code. An instruction with a condition code is only executed if the condition code flags in the CPSR meet the specified condition. The condition codes that you can use are shown in Table 4.2."

f.e. execute this instruction only if the previous instruction resulted in a negative number

Re: ARM immediate value encoding

#25

Post by duhast »

wreegab wrote: post #22

I was left with one question after reading the article: the purpose of the condition field in the instruction.

From one of data sheets:

In ARM state, all instructions are conditionally executed according to the state of the CPSR condition codes and the instruction’s condition field. This field (bits 31:28) determines the circumstances under which an instruction is to be executed. If the state of the C, N, Z and V flags fulfils the conditions encoded by the field, the instruction is executed, otherwise it is ignored.

When condition is set the mnemonic of instruction is extended with one of suffixes like EQ, NE, CS, CC etc.

Re: ARM immediate value encoding

#26

Post by stephencanon »

wreegab wrote: post #22

I was left with one question after reading the article: the purpose of the condition field in the instruction.

In the ARM instruction encoding, every arithmetic and logical instruction is "conditional". The destination register is either updated or not depending on the four bit condition field and the state of the condition flags in the processor.

As a simple contrived example, consider the following C code:

    int a[100], b[100], count;
    ...
    for (int i=0; i b[i]) count++;
    }
without conditional execution, one might compile this to code that uses a branch to either increment count or not; on ARM it would be more idiomatic to use conditional execution. Here's a very literal translation as an example (not tested, apologies for any inadvertent errors):

    // setup: a in R0, b in R1, count in R2, i in R3.
    loop: LDR   R4, [R0, R3, LSL #2] // load a[i]
          LDR   R5, [R1, R3, LSL #2] // load b[i]
          CMP   R4, R5               // if a[i] > b[i]
          ADDGT R2, R2, #1           //     count++
          ADD   R3, R3, #1           // i++
          CMP   R3, #100             // if (i
The fourth instruction, ADDGT, is conditional. Count is only updated with the result of the addition if the "greater than" condition is satisfied (the flags were set by the preceding instruction). To be more precise, all of the instructions here are conditional, it's just that for most of them the condition field is 1110, meaning "always".

Many instructions also have an "S" bit, which toggles whether or not they update the flags on which conditional execution depends. Taken together, these two features allow a clever assembly programmer to do some really clever things (but historically not too much effort has been directed at getting compilers to make really clever use of these features).

For low-power parts, this is a cute trick, as it allows a programmer to avoid stressing a limited branch predictor with lots of small branches. It does add some complication to the implementation however, especially when you get into designs that retire multiple instructions per cycle or support out-of-order execution, as conditional execution basically adds additional dependencies to every instruction.

Re: ARM immediate value encoding

#28

Post by userbinator »

marcosdumay wrote: post #9
stephencanon wrote: post #2

The set of representable ARM immediates is really nice. It's wonderfully useful for writing soft-float and math library routines, where you have very common values with just some high-order bits set: 0x3f800000 // encoding of 1.0f The set of immediate encodings, together with "shifts for free on most operations" (which are closely related features, as the OP points out), went a long way toward preserving my sanity wh…

Honestly, with so few bits, I was expecting it to be a lookup table. (Yep, I've never wrote ARM assembly.) But then, this way you have a nice set of imediates (as you said), and can set any value at all with at most 3 instructions at the rare case you need something different.

> I was expecting it to be a lookup table.

There's one ISA I've worked with before that does have -2, -1, 0, 1, 2, and some other "commonly used constants" like powers of 2 encoded specially in the immediate. I think it was an 8-bit, but I can't remember exactly which one. Anyone know what I'm referring to?

Re: ARM immediate value encoding

#29

Post by Dylan16807 »

chris_overseas wrote: post #12
userbinator wrote: post #10

If I've interpreted this correctly, it means that all values between 256 and 65535 can't be encoded this way since they all have the form 0x0000nn00 with a nonzero nn, and those are the bits that can't be gotten to from rotating.

Sure they can, by setting the rotate bits to 0xC (1100). Have a play with the interactive widget near the bottom of the article. Interestingly, there is some redundancy with this encoding meaning you can't represent a full 2^12 unique values. Eg 0x1 could be represented by 0x1 and 0x0 in the rotate field, 0x4 with 0x1 in the rotate field, 0x10 with 0x2, or 0x40 with 0x3. The same applies for every other combination -…

You didn't do that math right. Out of every 256 values at a particular offset, only a quarter of them are under 64 and can be encoded with rotate+1.

Doing a quick brute force test, it appears that there are 3073 unique values. I suppose that makes sense. Each new rotate introduces 192 new values that have at least one of the new bits set, and 192 * 16 = 3072. Then you have the number 0.

Re: ARM immediate value encoding

#30

Post by stephencanon »

userbinator wrote: post #28
marcosdumay wrote: post #9

Earlier quoted context omitted.

Honestly, with so few bits, I was expecting it to be a lookup table. (Yep, I've never wrote ARM assembly.) But then, this way you have a nice set of imediates (as you said), and can set any value at all with at most 3 instructions at the rare case you need something different.

> I was expecting it to be a lookup table. There's one ISA I've worked with before that does have -2, -1, 0, 1, 2, and some other "commonly used constants" like powers of 2 encoded specially in the immediate. I think it was an 8-bit, but I can't remember exactly which one. Anyone know what I'm referring to?

Similar, but not what you're thinking of: the x87 instruction set has instructions to push the values 1.0, lb(10), lb(e), pi, lg(2), ln(2), and 0.0.
Post reply on HN