7 ms·
ARM immediate value encoding
- stephencanon 13y agoThe 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 when writing assembly. Worth noting: thumb-2 immediates have a different (and even more interesting) encoding scheme. arm64 immediates are pretty interesting too (there the set of representable immediates is different depending on the instruction domain).
- marcosdumay 13y agoHonestly, 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.
- userbinator 13y ago> 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?
- stephencanon 13y agoSimilar, 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.
- jmpe 13y agoMSP430?
- teh_klev 13y agoIf the reply link is missing on a comment (it does that after the comments get to a certain depth of nesting) then click on the comment's "link" and you'll get a text box you can reply into.
- jmpe 13y agoNot sure why you're telling me this, I suggested MSP430 to the parent post as an answer for the ISA he was looking for.
- teh_klev 13y agoAh ok, theatrus2 was the only mention of MSP430 in the discussion under userbinator and in the absence of a "How about " in front of "MSP430?" I assumed you meant "What's a MSP 430?" in reply to theatrus2....but then I should've checked the comment times :)
- theatrus2 13y agoThe MSP430 has a constant generator register, which depending on the access mode used will generate offsets and zero. I'm sure there are a few others.
- userbinator 13y agoThat's the scheme. Although probably MSP430 took its inspiration from the one I had in mind since I was thinking of an 8-bit MCU from the early 80s - might've been Motorola.
- Symmetry 13y agoDo you know a good place for finding out more about the arm64 encoding?
- stephencanon 13y agoARM's reference manual (http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0487a.b/index.html http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc....). You need to create a (free?) account with ARM to download it. Of course, the document has been out for long enough that I'm sure it's available elsewhere for those truly paranoid about creating accounts.
- sbanach 13y agoSo arm compilers must prefer to, for example, XOR with 0x10000000 rather than AND with 0xEFFFFFFF?
- stephencanon 13y agoAND with 0xefffffff would become BIC ("bit clear", aka "and not") with 0x10000000. But yes, the basic idea of your comment is correct. Fortunately, compilers are quite good at this sort of thing.
- cnvogel 13y agoAnd if you need something like ~(byte << N) for any purpose there's still MVN (move-not). MVN r0, #0x10000000 ; ro = 0xefffffff Oh, the joy :-).
- stephencanon 13y agoCMN is the real gem. It's an endless source of bugs in the time between when compiler writers discover it and when they figure out how it actually sets flags. ARM would have done well to provide a "here's how you actually use this instruction" guide in the architecture reference manual.
- asveikau 13y agoAside from this kind of trick, I have not worked with a ton of ARM assembly but what I find is very frequently compilers will just put values in the text section close to where they are used and refer to them with some PC-relative thing, rather than using immediate values as often as they might on x86. I have seen this on other RISC platforms as well.
- thrownaway2424 13y agoWouldn't that require the pc-relative address to fit into this immediate scheme?
- AshleysBrain 13y agoVery cool and clever scheme. But what happens to immediates that can't be encoded that way?
- Tuna-Fish 13y agoYou have to place them in a constant pool and load them.
- ColinWright 13y agoAs others have said, that's not the case. All constants can be constructed by ORing together a small collection of expressible constants. With a little ingenuity "most" require very few instructions to build. FWIW, I have written real-time radar processing embedded software, and rarely had to resort to stored constants.
- stephencanon 13y agoThere are a few options for producing other values: 1. load them from a constant pool in memory (often this is put nearly inline in the instruction stream so that it can be addressed via a small constant offset from PC). If your code doesn't saturate the LSU locally, this is usually the best option. 2. assemble them via bitwise or arithmetic combinations of literals that you can represent (or already in-register values that you know something about). If you can do it with just a few operations, and the LSU is otherwise occupied, you should do this instead. This is also preferred on some limited cores that can dual-issue logical and arithmetic ops but not LSU ops. 3. in recent revisions of the instruction set, there are a pair of instructions MOVW and MOVT; MOVW conjures a 16b immediate, and MOVT sets the high 16b, so with these two instructions you can conjure any 32b value. There is a bit of subtlety to choosing the correct approach. Some assemblers provide a "conjure this value" pseudo-operation where the assembler will choose what it thinks is the best option to materialize a constant; that way the programmer doesn't need to worry about these details. This looks something like the following: LDR R0, =0xff0000ff the assembler might actually stash the constant somewhere and generate a load instruction, or it might instead do: MOV R0, 0xff000000 ORR R0, R0, 0x000000ff and assemble the value via a couple instructions with immediates.
- chewxy 13y agoHoly crap. ARM's encoding makes so much sense... compared to what I have waded through at sandpile.org.
- wolfgke 13y agoThe x86 encoding actually makes sense once you begin to write its instructions using octal instead of hexadecimal numbers: http://www.dabo.de/ccc99/www.camp.ccc.de/radio/help.txt http://www.dabo.de/ccc99/www.camp.ccc.de/radio/help.txt (this isn't mentioned in the Intel or AMD docs).
- userbinator 13y agoIf 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.
- chris_overseas 13y agoSure 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 - this means that there are only (2^12)/4 = 1024 unique values that are representable in total.
- Dylan16807 13y agoYou 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.
- stephencanon 13y agoAnything of the form 0x0000nn00 is representable, as it has at most eight contiguous non-zero bits starting at an even bit position (i.e. these values are 0x000000nn rotated right by 24). Maybe you're wondering how a rotation of 24 can be encoded in four bits? To get the rotation amount, you double the value of the four-bit field. Only even rotation counts are representable.
- userbinator 13y agoThanks, overlooked that detail. Very interesting encoding scheme.
- notinreallife 13y agoTHAT Barrel Shifter, son!
- wreegab 13y agoI was left with one question after reading the article: the purpose of the condition field in the instruction.
- pointernil 13y agohttp://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0068b/Chdehgih.html 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
- duhast 13y agoFrom 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.
- stephencanon 13y agoIn 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<100; i++) { if (a[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 < 100) BLT loop // continue loop 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.
- lectrick 13y agoThis 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).
- fidotron 13y agoThese days if what you're writing is in C then you should really know the behaviour of the architecture underneath. ARM really isn't that hard if you're already thinking like a low level programmer. Things like MIPS were (better) designed for being targeted from higher level languages, but the consequence is a much messier machine language. It's always struck me as amusing that the conventional view is MIPS is minimal, when ARM is really much more so, but it's from outside the Berkeley/Stanford RISC bubble so didn't really get on to their radars for some time.
- TorKlingberg 13y agoThere is lots of C code that is written to be portable, and trusts the compiler to generate optimized assembly. But those are probably ok with spending a couple of extra cycles for some immediate values.
- deadsy 13y agoThe Tensilica guys took this thing an extra step. ie- profile real code to find out what constants are most typically used, enumerate the top n constants, encode the constant with 0..n-1 in the immediate instruction - the immediate value is a hardware based lookup. You can still do arbitrary immediates with longer instructions but you can apparently get some nice code size reductions using this technique.
- fidotron 13y agoThe flipside of that is that the scheme described here will take less silicon, fewer transistors and thus . . . use less power, if you happen to optimise the code appropriately. Code size reductions are good, but for power purposes it is a case of balancing them against decoding complexity.
- eckzow 13y agoThumb-2 immediate encoding is even more gleeful--in addition to allowing rotation, it also allows for spaced repetition of any 8-bit pattern (common in low level hack patterns, like from [1]) to be encoded in single instructions. For those interested, check out page 122 of the ARMv7-M architecture reference manual[2]: // ThumbExpandImm_C() // ================== (bits(32), bit) ThumbExpandImm_C(bits(12) imm12, bit carry_in) if imm12<11:10> == ’00’ then case imm12<9:8> of when ’00’ imm32 = ZeroExtend(imm12<7:0>, 32); when ’01’ if imm12<7:0> == ’00000000’ then UNPREDICTABLE; imm32 = ’00000000’ : imm12<7:0> : ’00000000’ : imm12<7:0>; when ’10’ if imm12<7:0> == ’00000000’ then UNPREDICTABLE; imm32 = imm12<7:0> : ’00000000’ : imm12<7:0> : ’00000000’; when ’11’ if imm12<7:0> == ’00000000’ then UNPREDICTABLE; imm32 = imm12<7:0> : imm12<7:0> : imm12<7:0> : imm12<7:0>; carry_out = carry_in; else unrotated_value = ZeroExtend(’1’:imm12<6:0>, 32); (imm32, carry_out) = ROR_C(unrotated_value, UInt(imm12<11:7>)); return (imm32, carry_out) [1] http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html (worth a read on its own if you're into this kind of thing) [2] http://web.eecs.umich.edu/~prabal/teaching/eecs373-f10/readings/ARMv7-M_ARM.pdf http://web.eecs.umich.edu/~prabal/teaching/eecs373-f10/readi... (no-registration link)
- gumby 13y agoI love that the author described the ARM as "elegant, pragmatic, and quirky." It reminds me of Gordon Bell's PCP-6/PDP-10 architecture, but applied to the RISC rather than CISC philosophy. (well, the PDP-10 was pretty RISC for its day and gave us things like BLT, hence bitblit).
- thrownaway2424 13y agoArticle begins by praising RISC as "elegant" and "a good design decision", goes on to describe limitations of RISC immediate values.
- talideon 13y agoYou're being a little disingenuous. It describes the ARM architecture as 'elegant', and 1/4 of the way through the article describes the common use of fixed length instructions in various RISC architectures as 'a good design', and explains why this is mostly a win. And then it explains how the ARM manages to encode a wide range of useful immediate values using a very elegant and simple scheme. In all my years coding in ARM assembly language, the range of immediate values it supported was rarely if ever an issue.
- caprad 13y agoWhy is this cool and clever? It still only encodes 12 bits of data, it is just different to using the normal 12 bits of data. Is this a more useful subset? I am guessing it is so, since they went to this trouble.
- rbanffy 13y agoIt can generate 4096 different slightly useful 32-bit values. For others, you may assemble them using a variety of methods.
- tasty_freeze 13y agoIt generates fewer than 4096 unique values, as some values map to the same thing. The most obvious being that 0 shifted any number of places produces 0, but also 0x10 shifted left 0 is the same as 0x04 shifted left 2 is the same as 0x01 shifted left 4.
- rbanffy 13y agoMakes sense. Well... It produces less than 4096 interesting 32-bit values.
- tasty_freeze 13y agoThis encoding is nice given that they've already paid the price of having the 32b barrel shifter, but it was a non-obvious choice to have the barrel shifter to begin with. Most instructions don't benefit from the optional rotate, but they pay the price in the encoding and in the data path. Interestingly, the website uses svg for illustrations, IE 8 and under be damned.
- ggchappell 13y agoI agree that this clever and useful, but I get the feeling that it could have been more so. I haven't done much assembly in a while, but I was heavily into it once upon a time, and I recall that values with lots of 1s were useful. There is not quick way to generate those here. This means that we can write a single instruction to set any single bit using an inclusive OR and the proper immediate value, but we cannot write a single instruction to clear any single bit. The reason I think a bit more cleverness might have helped is that there are so many values with multiple encodings. Anything where the 8-bit value ends with 0 has a different encoding as well. For example, a rotation of 0000 and an 8-bit value of 00000100 gives the same result as a rotation of 1111 and an 8-bit value of 00000001 (right?). Perhaps some of the redundant instructions could have been used to represent things ending in lots of 1s? Regardless, an interesting and informative post. :-)
- tlb 13y agoYou can get trailing ones by subtracting 1: 0x01000000 - 1 = 0x00ffffff so you can generate any number of trailing ones with 2 instructions.
- eckzow 13y agoClearing an arbitrary bit actually is supported (as mentioned in the article: "you can set, clear, or toggle any bit with one instruction"). The specific details require you to dig a bit past explaining just the immediate encoding, but in the clearing case there's a dedicated instruction for clearing the bit specified by the immediate: BIC - Bit Clear (immediate) performs a bitwise AND of a register value and the complement of an immediate value, and writes the result to the destination register. As I mentioned in my other post, zero-rotation encodings are gamed out as well (to allow byte repetition).
- ggchappell 13y ago> BIC - Bit Clear (immediate) Ah, didn't catch that.
- renox 13y agoNice but somewhat obsolete I think: AFAIK the ARMv8 (64bit) ISA is different..