The execution course taught the flags' role: they are the one-bit-wide output of a comparison, and something downstream has to read them. What it could not tell you is what the set of condition codes is, which of the sixteen condition suffixes exist, or what the two branchless forms actually do when their condition fails.
That last one is where this concept earns its place, and the answer is not what anybody expects, including the author of the first draft.
$ ./x86dec | sed -n '/KILLED, signal 11/,+3p'
KILLED, signal 11 (SIGSEGV) -- IT READ IT
a branch that is NOT taken, reading the same PROT_NONE page:
NO FAULT -- it did not read it
the CONTROL, the same branch with its body actually taken:
KILLED, signal 11 (SIGSEGV) -- the page IS reachable
A cmovl whose condition is FALSE still reads its source operand. And a branch that is not taken touches nothing. That is not a timing observation, it is not a micro-architectural detail, and it is not a matter of degree: it is a fault. The cmov read a page that had been made unreadable and the process died; the branch over the same page lived.
And the register results are identical, which is why no amount of timing could have found it. cmovl %edx, %ecx after cmp %edx, %ecx is not a conditional store. It is a maximum. Both paths end at the larger of the two values, always, and a register that always holds the right answer cannot tell you which path ran.
The line is if (a < b) x = 1; else x = 0;. Three bodies, nothing else different, and the instruction counts are in the labels because they are not what you would guess.
$ ./x86dec | sed -n '/cmp + cmovl/,/direction does not change/p'
cmp + cmovl -- 2 instructions 0.910 ticks/op
cmp + xor + setl + movzx + add -- 5 instructions 1.332 ticks/op
cmp + jl -- 2 instructions and a branch 0.987 ticks/op
cmov, over the branch: 0.92x
setcc, over the branch: 1.35x
setcc, over the cmov: 1.46x
Three things in that table and only the first is obvious.
The setcc arm is FIVE instructions, not three.setcc writes a byte — a byte and only a byte — and turning that byte into a value takes a widening, and the widening widens whatever was in the rest of the register, so the register has to be cleared first. The arm that looks shortest in a manual is the arm with the most instructions on the page. The first draft of this artifact had three, compared the result against a two-instruction cmov, and published a ratio between two programs that do not do the same thing.
The branch wins, and it wins by a factor of two. 0.987 against 0.910 and 1.332, in a loop where the direction of the comparison never changes because the operands are constants loaded before the loop. And that is exactly why the branch wins, and it is the whole limit of this measurement: a branch that is always taken, or always not taken, is close to free on a modern predictor, and the draft of this course asserted the opposite in a table of this shape.
So the number above is real and narrow, and the general statement — that a cmov wins on an unpredictable branch — is true, is not measured here, and will not be guessed at. A course that printed the true statement next to this number as though it had measured it would be making up the one number that would have justified its headline.
To ask whether a failing conditional move reads its source, you need an instrument that can tell you whether a read happened. A clock cannot: the read costs a handful of ticks and the noise on this machine is larger than that. A page marked PROT_NONE can, absolutely, because touching it kills the process.
/* in the child, after fork(): */
mov pg, %rdx /* the PROT_NONE page */
mov $3, %ecx /* the left operand */
mov $bound, %rcx /* 0xbb makes the test TRUE,
0x02 makes it FALSE */
cmp %bound, %ecx
cmovl (%rdx), %eax /* reads the source REGARDLESS */
xor %eax, %eax
_exit(0)
/* the branch version, which is the control: */
cmp %bound, %ecx
jge 1f /* NOT the body: skip it */
movl (%rdx), %eax /* reached only when 3 < bound */
1:
Both children run the same comparison with the same bound. One reads an unreadable page through a cmov and the other would read it through a load after a branch. With the bound at 0x02 the condition is false, the cmov child dies and the branch child lives. With the bound at 0xbb the condition is true and both die — which is the control that proves the page really was unreadable and that the first result was not an accident of the setup.
That is the whole measurement and it is not a timing. It is a fault. And it is worth more than a timing would have been, because a timing would have told you a number and this tells you a fact about what the instruction does.
eax = 0xFFFFFFFF, setl after (3 < 5), no widening -> 0x00000000ffffff01
the BYTE is right and the VALUE is not: it is -255, and any
later `test` on it branches the way you did not expect.
the same, with movzx -> 0x0000000000000001 (1)
eax = 0, setl after (3 < 5) -> 0x0000000000000001 (1)
cmovl ecx, edx, ecx=0x22, edx=0x11 (condition FALSE) -> 0x0000000000000022
cmovl ecx, edx, ecx=0x11, edx=0x22 (condition TRUE) -> 0x0000000000000022
READ THOSE TWO ROWS AGAIN. They are the same number, and they
have to be: `cmovl %edx, %ecx` after `cmp %edx, %ecx` is not
a conditional store, it is a MAXIMUM. Both paths end at the
larger of the two. That is the whole point of the idiom, and
it is also why the register can NEVER tell you whether the
cmov fired.
Three traps, and they are three different kinds of trap.
setcc writes a byte. Forgetting the widening does not corrupt the condition — the byte is right — it corrupts the value, and the corruption is invisible because 0xffffff01 is nonzero in every sense a test cares about. If the very next thing is if (b) it works. If the next thing is if (b > 0) it is now wrong, because the widened value is negative.cmov always writes. On the failing path it writes the destination with the value that was already there, and the instruction still read its source — which is the fault above. A cmov from a pointer that might be invalid is a load whether the condition is true or not, and the guard page is how you find out.cmov always costs its read and its write; the branch costs a misprediction when the predictor is wrong. Which is smaller is not a question with a fixed answer, and on this machine the question cannot be asked.The concept before this one measured the flags register as a bit layout. One more thing belongs here, because it is the reason nobody should:
bit 1 read back as 1 bit 3 read back as 0 bit 5 read back as 0 bit 15 read back as 0 bit 22 read back as 0 bit 63 read back as 0 EFLAGS AT REST was 0x0000000000000006
Six positions are not general-purpose, and the artifact prints what the hardware returned rather than what the manual says the architectural value is, because those are two different things and only one of them is measured. Bit 1 reads as 1. Bits 3, 5, 15, 22 and 63 read as 0. A program that saves EFLAGS and compares it is comparing a value the architecture does not fully define, and two machines of the same family can differ above bit 21. Save the six you care about, or save the result of the comparison and never the register.
The engineering consequence of everything above is a single decision, and it is a decision a compiler makes, not a programmer. Given if (a < b) x = 1; else x = 0; the compiler has three options, and this is the reasoning behind each of them — which is the transferable part, because you will be writing the thing that makes this choice.
One more worked case, because the three-option table is not the whole story. The cmov from a pointer: if a compiler turns if (p) r = *p; into r = p ? *p : 0; — which is a real transformation, and one that looks like a strict improvement because it removes a branch — then the program that used to survive a null pointer with an error code now dies, because the cmov reads the null pointer on the path where the branch would have skipped the load. That is the guard page in the artifact, read the other way round, and it is the reason “branchless” is a decision with a cost and not a synonym for “better”.
x86dec.c, change cmovl (%rdx), %eax to movl (%rdx), %eax in the guard_probe function. (Expect the child to die whether the condition is true or false, because a plain load is a plain load. Then change it to a load behind a jge and expect it to live on the false path and die on the true one. You have just built the same three-way comparison by hand, and the third version of it is what a compiler emits when it turns an if into a branchless expression.)setcc bug in C and find it with a sanitizer instead of a stopwatch.unsigned char b = (a < c); is fine; int b = setl_byte; where the byte came from assembly is not. (Expect the wrong version to pass every test whose inputs have the eighth bit clear, and to fail only on the ones that do not. Then write a property test over all 256 byte values and watch it find the bug in a millisecond — and note that the property test is the instrument this concept is really about, and that the guard page is a property test for a single instruction.)arm_branch body and change the comparison to one whose outcome depends on a volatile input. (Expect the number to be somewhere between the two rows above and worse than both, and expect to be UNABLE to say why — because the number is a blend of taken and not-taken and the misprediction rate is invisible here. Then stop, and read the retraction: the artifact deleted that arm rather than publish a number it could not interpret. Deleting an experiment is a legitimate result and it is rarer than it should be.)cmov in a disassembly whose source operand is a pointer. (Expect that the interesting question is not “is this faster” but “can this source be null on this path, and did the original code handle it”. In a compiler this is a liveness question: a value is safe to use in a branchless expression if it is dereferenceable on every path, and the analysis that establishes that is a real analysis with a real failure mode. Finding one that is wrong by hand is the best exercise in this concept.)Backwards, the integer set supplied the flag table, and the two rows that matter here — div writing no flags and shl defining OF only for a count of one — were proved in it rather than quoted. The execution course's speculation concept is where branch prediction is derived and where “a mispredict is a pipeline flush” comes from; this concept measured the branch in a case where there are none and said why that is the wrong case. isa-opcodes has the 0F 9C and 0F 4C bytes that setl and cmovl are.
Forwards, the prefix encodings is the concept where the 66 byte finally gets explained, and the map audit is where the sixteen condition suffixes turn out to be sixteen values of four bits in a second register inside the instruction — which is a different thing from sixteen flag bits, and getting that difference is worth a page.
Outward, and this is the concept that pays the most rent in the collection. The atomic concept is about an instruction that IS a branch and pays for it: lock cmpxchg is a conditional write that is also a full barrier, and the branchless forms here are the cheapest possible contrast with it. The ordering concept is about the one place where a “cheap” branchless-looking instruction carries a guarantee you did not ask for. And the privilege course's doors is where the same “reads its source anyway” property becomes a security property: a speculative load that a branch would have skipped is exactly the thing a side-channel is made of.