Redundancy of x86 Machine Code (2009)

https://www.strchr.com/machine_code_redundancy

by akkartik • 8 years ago

46 12 8 years ago

Two distinct opcode extensions for SAL/SHL

How those came about is pretty straightforward:

    SHR - shift right with zero-fill
    SAR - shift right with sign-fill
    SHL - shift left with zero-fill
    SAL - shift left with sign-fill

Of course, the sign-fill hardware is useless for left shift, so we effectively have two opcodes doing the same thing. The Z80 has a similar instruction, except that it, more oddly, always inserts a 1 in the LSB.

JdeBP• 8 years ago

VHDL has an arithmetic shift that duplicates in the LSB.

DSMan195276• 8 years ago

This is a small note, but IIRC that instruction on the z80 is actually undocumented. It's easy to tell what it should be though since all the shifts are the same opcode except for two bits representing the direction and type (arithmetic/logical). But that would be why the behavior is so weird - it's just whatever happens in the CPU when both those settings happen to be set.

0xcde4c3db2• 8 years ago

In a similar vein, some processors have encodings for branch conditions that work out along the lines of:

Branch if zero

Branch if nonzero

Branch if less than zero

Branch if greater than zero

Branch if greater than or equal to zero

Branch if less than or equal to zero

Branch always

Branch never (actually documented on the Motorola 68HC11, I believe)

userbinator2• 8 years ago

Branch never (actually documented on the Motorola 68HC11, I believe)

The early ARM cores which have conditional execution of all instructions had a corresponding "never" condition, but in the later revisions they decided that 16 million different NOP instructions was not a good use of opcode space and reused that as an extension for new instructions.

baobrien• 8 years ago

I'm not sure about other RISC ISAs, but on RISC-V, register-to-register moves are encoded as "ADDI rd, rs, 0". That is, add 0 (immediate) to rs and store in rd. Canonical NOPs are "ADDI x0, x0, 0", where x0 is the hardwired-zero register.

pcwalton• 8 years ago

That's a typical RISCism, going back at least to MIPS. Among popular recent ISAs, AArch64 uses a zero register.

0xcde4c3db2• 8 years ago

MIPS does similar things, except that the NOP is "sll r0, r0, 0", i.e. left-shift the hardwired zero register by zero, and store the result in r0. They presumably chose this over the many other "store in R0" instructions because it encodes to 0x00000000.

js2• 8 years ago

Related, "mov is Turing-complete":

http://www.cl.cam.ac.uk/%7Esd601/papers/mov.pdf

xelxebar• 8 years ago

Christopher Domas implemented this idea in his one instruction compiler, the M/o/Vfuscator:

https://github.com/xoreaxeaxeax/movfuscator

Here's a really nifty talk he gives about it:

https://www.youtube.com/watch?v=R7EEoWg6Ekk

doomlaser• 8 years ago

which led to this, posted on HN a few days ago, branchless Doom: https://news.ycombinator.com/item?id=16218872

"The mov-only DOOM renders approximately one frame every 7 hours, so playing this version requires somewhat increased patience."

Redundancy of x86 Machine Code (2009)

Related Stories