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

XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

devblogs.microsoft.com

Post reply on HN
Print view View original

111–120 of 231 posts

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#111

Post by dreamcompiler »

Someone wrote: post #105
NewCzech wrote: post #4

The obvious answer is that XOR is faster. To do a subtract, you have to propagate the carry bit from the least-significant bit to the most-significant bit. In XOR you don't have to do that because the output of every bit is independent of the other adjacent bits. Probably, there are ALU pipeline designs where you don't pay an explicit penalty. But not all, and so XOR is faster. Surely, someone as awesome as Raymond C…

> To do a subtract, you have to propagate the carry bit from the least-significant bit to the most-significant bit. Yes, but that need not scale linearly with the number of bits. https://en.wikipedia.org/wiki/Carry-lookahead_adder : “A carry-lookahead adder (CLA) or fast adder is a type of electronics adder used in digital logic. A carry-lookahead adder […] can be contrasted with the simpler, but usually slower, ripp…

Carry lookahead is definitely faster than ripple carry but it's not free. It requires high-fan-in gates that take up a fair amount of silicon. That silicon saves time though, so as you say almost nobody uses ripple carry any more.

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#112

Post by dbdr »

wongarsu wrote: post #104
zahlman wrote: post #83

Earlier quoted context omitted.

GP seems to think it strange that "x86" would actually not have a performance difference here. I think this might just be due to not realizing just how far back in CPU history this goes.

In a clockless cpu design you'd indeed expect xor to be faster. But in a regular CPU with a clock you either waste a bit of xor performance by making xor and sub both take the same number of ticks, or you speed up the clock enough that the speed difference between xor and sub justifies sub being at least a full tick slower The former just seems way more practical

Even if they take the same number of ticks, shouldn't xor fundamentally needing less work also mean it can be performed while drawing less power/heating less, which is just as much an improvement in the long run?

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#113

Post by LegionMammal978 »

drob518 wrote: post #101
bonzini wrote: post #96

Earlier quoted context omitted.

One byte instructions, with 8 registers as in the 8086, waste 8 opcodes which is 3% of the total. There are just five: "INC reg", "DEC reg", "PUSH reg", "POP reg", "XCHG AX, reg" (which is 7 wasted opcodes instead of 8, because "XCHG AX, AX" doubles as NOP). One-byte INC/DEC was dropped with x86-64, and PUSH/POP are almost obsolete in APX due to its addition of PUSH2/POP2, leaving only the least useful of the five in…

I’m not sure I understand what you mean by “waste 8 opcodes.”

Traditionally in x86, only the first byte is the opcode used to select the instruction, and any further bytes contain only operands. Thus, since there exist 256 possible values for the initial byte, there are at most 256 possible opcodes to represent different instructions.

So if you add a 1-byte instruction for each register to zero its value, that consumes 8 of the possible 256 opcodes, since there are 8 registers. Traditional x86 did have several groups of 1-byte instructions for common operations, but most of them were later replaced with multibyte encodings to free up space for other instructions.

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#114

Post by HarHarVeryFunny »

flohofwoe wrote: post #94
HarHarVeryFunny wrote: post #77

Earlier quoted context omitted.

The 6502 doesn't support XOR A or SUB A, and in fact doesn't have a SUB opcode at all, only SBC (subtract with carry, requiring an extra opcode to set the carry flag beforehand).

I was handwaving over the details, SBC is identical to SUB when the carry flag is clear, so it's understandable why the 6502 designers didn't waste an instruction slot. EOR and SBC still have the same cycle counts though.

Sure, in some contexts you would know that the carry flag was set or clear (depending on what you needed), and it was common to take advantage of that and not add an explicit clc or sec, although you better comment the assumption/dependency on the preceding code.

However the 6502 doesn't support reg-reg ALU operations, only reg-mem, so there simply is no xor a,a or sbc a,a support. You'd either have to do the explicit lda #0, or maybe use txa/tya if there was a free zero to be had.

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#115

Post by GuB-42 »

drob518 wrote: post #101
bonzini wrote: post #96

Earlier quoted context omitted.

One byte instructions, with 8 registers as in the 8086, waste 8 opcodes which is 3% of the total. There are just five: "INC reg", "DEC reg", "PUSH reg", "POP reg", "XCHG AX, reg" (which is 7 wasted opcodes instead of 8, because "XCHG AX, AX" doubles as NOP). One-byte INC/DEC was dropped with x86-64, and PUSH/POP are almost obsolete in APX due to its addition of PUSH2/POP2, leaving only the least useful of the five in…

I’m not sure I understand what you mean by “waste 8 opcodes.”

There are only 256 1-byte opcodes or prefixes available, if you take 8 of these to zero registers, they won't be available for other instruction, and unless you consider zeroing to be so important that they really need their 1-byte opcodes, it is redundant since you can use the 2-byte "xor reg,reg" instead, hence the "waste'.

In addition, you would need 16 opcodes, not 8, if you also wanted to cover 8 bit registers (AH/AL,...).

Special shout-out to the undocumented SALC instruction, which puts the carry flag into AL. If you know that the carry will be 0, it is a nice sizecoding trick to zero AL in 1 byte.

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#116

Post by not_a_bijection »

drfuchs wrote: post #47

Relatedly, there's a steganographic opportunity to hide info in machine code by using "XOR rax,rax" for a "zero" and "SUB rax,rax" for a "one" in your executable. Shouldn't be too hard to add a compiler feature to allow you to specify the string you want encoded into its output.

You can do better. X86 has both "op [mem], reg" and "op reg, [mem]" variants of most instructions, where "[mem]" can be a register too. So you have two ways to encode "xor eax, eax", differing by which of the operands is in the "possible memory operand" slot, the source or the destination.

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#117

Post by adrian_b »

gblargg wrote: post #81
adrian_b wrote: post #67

It should be noted that XOR is just (bitwise) subtraction modulo 2. There are many kinds of SUB instructions in the x86-64 ISA, which do subtraction modulo 2^64, modulo 2^32, modulo 2^16 or modulo 2^8. To produce a null result, any kind of subtraction can be used, and XOR is just a particular case of subtraction, it is not a different kind of operation. Unlike for bigger moduli, when operations are done modulo 2 addi…

> XOR is just a particular case of subtraction, it is not a different kind of operation. It's different in that there's no carry propagation.

That is not a property specific to XOR.

Whenever you do addition/subtraction modulo some power of two, the carry does not propagate over the boundaries that correspond to the size of the modulus.

For instance, you can make the 128-bit register XMM1 to be zero in one of the following ways:

  PXOR  XMM1, XMM1   ; Subtraction modulo 2^1
  PSUBB XMM1, XMM1   ; Subtraction modulo 2^8
  PSUBW XMM1, XMM1   ; Subtraction modulo 2^16
  PSUBD XMM1, XMM1   ; Subtraction modulo 2^32
  PSUBQ XMM1, XMM1   ; Subtraction modulo 2^64
In all these 5 instructions, the carry propagates inside chunks corresponding to the size of the modulus and the carry does not propagate between chunks.

For XOR, i.e. subtraction modulo 2^1, the size of a chunk is just 1 bit, so the propagation of the carry inside the chunk happens to do nothing.

There are no special rules for XOR, its behavior is the same as for any other subtraction, any behavior that seems special is caused by the facts that the numbers 1 (size in bits of the integer residue) and 0 (number of carry propagations inside a number having the size of the residue) are somewhat more special numbers than the other cardinal numbers.

When you do not do those 5 operations inside a single ALU, but with separate adders, the shorter is the number of bits over which the carry must propagate, the faster is the logic device. But when a single ALU does all 5, the speed of the ALU is a little slower than the slowest of those 5 (a little slower because there are additional control gates for selecting the desired operation).

The other bitwise operations are also just particular cases of more general vector operations. Each of the 3 most important bitwise operations is the 1-bit limit of 2 operations which are distinct for numbers with sizes greater than 1 bit, but which are equivalent for 1-bit numbers. While XOR is just addition or subtraction of 1-bit numbers, AND is just minimum or multiplication of 1-bit numbers, and OR is just maximum of 1-bit numbers or the 1-bit version of the function that gives the probability for 1 of 2 events to happen (i.e. difference between sum and product).

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#118

Post by not_a_bijection »

adrian_b wrote: post #67

It should be noted that XOR is just (bitwise) subtraction modulo 2. There are many kinds of SUB instructions in the x86-64 ISA, which do subtraction modulo 2^64, modulo 2^32, modulo 2^16 or modulo 2^8. To produce a null result, any kind of subtraction can be used, and XOR is just a particular case of subtraction, it is not a different kind of operation. Unlike for bigger moduli, when operations are done modulo 2 addi…

[dead]

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#119

Post by repelsteeltje »

classichasclass wrote: post #92
repelsteeltje wrote: post #45

Earlier quoted context omitted.

Yep. The XOR trick - relying on special use of opcode rather than special register - is probably related to limited number of (general purpose) registers in typical '70 era CPU design (8080, 6502, Z80, 8086).

Unfortunately, 6502 can't XOR the accumulator with itself. I don't recall if the Z80 can, and loading an immediate 0 would be most efficient on those anyway.

You're absolutely right, I stand corrected.

The 6502 gets by doing immediate load: 2 clock cycles, 2 bytes (frequently followed by single byte register transfer instruction). Out of curiosity I did a quick scan of the MOS 1.20 rom of the BBC micro:

  LDY #0 (a0 00): 38 hits
  LDX #0 (a2 00): 28 hits
  LDA #0 (a9 00): 48 hits

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#120

Post by not_a_bijection »

anematode wrote: post #5

My favorite (admittedly not super useful) trick in this domain is that sbb eax, eax breaks the dependency on the previous value of eax (just like xor and sub ) and only depends on the carry flag. arm64 is less obtuse and just gives you csetm (special case of csinv ) for this purpose.

That's even more useful because of x86's braindamanged "setcc", which only affects the lowest byte of the destination, AFAIR, and so always has to be combined with a zeroing idiom before the setcc or a zero extension after it in practice.
Post reply on HN