Module phiopt 

If-conversion, the part of it that turns a diamond into a select.

Design: spec/optimizer/22-phiopt-and-if-conversion.md. A block ends in a two way branch, each arm works out a value and does nothing else, and the two arms meet again at a block that takes that value as a parameter. The branch is not deciding what the program does, it is deciding which of two numbers to keep, and select says that directly. Section 22.2 asks for the shape matcher and five transformations built on it, and the shape matcher plus the first, the second, the third and half of the fourth of them is what is here.

This is the highest variance transformation in the compiler and the document says so in its third paragraph. Removing a mispredicted branch is worth about twenty cycles. Removing a perfectly predicted one costs whatever the arm that is no longer skipped costs, and no static analysis tells the two apart reliably. So the cost rule below is written to be argued with rather than to be right, and section 42’s measurement of the pass on and off at -O2 is the only honest evaluation there is.

The shape

A head block ending in br_if, and a join block both arms reach. Each side of the branch is either a block of its own that does nothing but work out values and jump to the join, or the join itself. That gives three shapes and the pass takes all three: the diamond where both sides have a block, and the two triangles where one side goes straight to the join because the arm was empty and simplify-cfg already took it out.

What replaces it is one block. Everything the arms worked out moves into the head, a select is built for each of the join’s parameters the two sides disagree about, and the head jumps to the join carrying them. The arms are then unreachable and go, and the join is left for simplify-cfg to merge upward when nothing else arrives at it.

The value the condition already settled

Section 22.2’s second transformation, value_replacement. x = (a == b) ? b : a is x = a, because the only way to arrive at the join carrying b is along the edge where a and b are the same number. No select is written, the branch goes with the rest of them, and whichever arm was only there to work the other value out is left with nothing in it.

What answers this is document 10’s relational oracle, which is what section 22.2 says it needs and this is its first caller in the compiler. The question is put as Ranges::compare at the arm rather than as a range lookup, because the fact wanted is about two values rather than about either one of them, and section 10.3 is where that distinction is made.

The branch has to be on an equality, and that gate is the difference between a cheap pass and an expensive one. Section 22.7 already names this query as the expensive part of the pass. What the oracle records is what a dominating edge established between two values, and the edge out of a br_if establishes something about two values only when the branch is on a comparison of them, so a branch on x < n cannot answer whether two other values are equal and asking is a query with nothing at the end of it. GCC gates the same way, on EQ_EXPR and NE_EXPR.

One thing this does that the select cannot is a value whose type has no select at all. A pointer is the case: p == q ? q : p used to keep its branch, because a select of two pointers is a term nothing lowers, and it is now one move, because nothing has to be chosen. The width refusal below is therefore asked after this rather than before it.

It is one deep, in the same sense the factoring below is. What the join is handed is what gets asked about, so a == b ? b + c : a + c factors to one add over a select and the select stays, because what the oracle would have to know is that b + c and a + c are equal rather than that a and b are. Asking about the factored operand instead is the change that would take it, and it is left for when something measures a use for it.

The operation both arms did

Section 22.2’s third transformation, factor_out_conditional_operation. When the two sides worked out their answers the same way from different operands, cond ? f(a) : f(b), the select goes under the operation rather than over it and the answer is f(cond ? a : b). One operation where there were two, and the same one select either way.

It is structural and not a rewrite rule for the reason section 22.2 gives about all five: the two fs are in different blocks and no pattern spans blocks. By the time they are in one block the arms have already been hoisted and the select already written, and undoing that is a larger rewrite than never writing it.

The two operations have to match in everything but one operand. The opcode and the operand count obviously. The flags, because those are what the optimizer is licensed to assume and one copy written under the union of two sets of assumptions would be claiming on one path something only the other path established. Whatever else the instruction carries, which for a comparison is the predicate, since two predicates are two different questions. And exactly one operand position apart, because two positions apart needs two selects and one operation, which is what one select and two operations already cost.

Agreeing in every position is allowed and is the case where no select is written at all. Both arms working out the same thing from the same operands is what a common subexpression that nothing has numbered looks like from here, and one copy of it serves both sides.

The operation has to be worked out in the arm and read only by the arm’s jump to the join. The first because an operation to stop writing is one this has to be able to find. The second because the one copy that replaces the two is written after the arms have gone, and a second reader inside the arm would have been left pointing at an instruction that is no longer in any block.

Only the value the join takes is asked about, so a chain both arms share is factored one deep. total += (long long)(i * 2) against total += (long long)(i + 1) has three operations in each arm, the outermost pair factors, the sign extensions under them are the same operation on different operands and would factor too, and they are not looked at because nothing hands them to the join. Doing it to a depth would mean factoring what the select then reads, which is the same function called on what it just produced, and it is left for when something asks for it.

A constant operand is not refused and the reason is that it was measured and it goes both ways. An operation with a constant in it takes that constant as an immediate, so factoring turns two free immediates into a select between two values that have to be in registers, and on product + 2 against product + 1 outside a loop that costs five bytes. On total += 1 against total += 1000 inside one it saves fourteen, because the constants were being rematerialized every iteration anyway. Over the corpus, refusing every constant operand trades thirty two bytes of win for twenty two bytes of loss, which is ten bytes across 1453 programs and is not worth a rule.

The store both arms made

Section 22.2’s fourth transformation, conditional store replacement, in the half of it that needs no proof. When both arms store to the same place, if (c) *p = a; else *p = b; becomes *p = c ? a : b, and the branch goes with the rest of them.

Half, and which half is the whole point. Section 22.6 calls the other half the worst bug in the document, because a store made on a path that was not going to make one writes memory the program was not going to write. The load modify store form GCC uses, reading the location and writing back what it read on the path that had no store, is not a no-op: it is a write, so it races with another thread writing the same bytes, and it faults if the page is read only. What would license it is knowing the location is written whatever happens, which is the predicate section 22.6 asks for and which nothing here can answer yet.

When both arms store to the same address, that predicate is discharged by the shape itself and nothing has to be proved. One store before and one store after, to the same address, of a value the program was going to write there on one path or the other. Nothing new is written, nothing is written twice, and the order of that store against everything else in the function is where it was. So this is the case that goes in, and the one armed case is refused by name rather than by falling through the effects check, so that -fopt-info-all says which of the two it was.

What has to match beyond the address is the access itself: the flags, and the alignment, size, aliasing node and restrict scope that a store carries alongside them, because the one store written below carries one of each and two that disagree have no single answer to carry. The address has to be the same value rather than a provably equal one, which is the strong form of the question and is the only form available without an alias analysis. It also settles where the address comes from: neither arm dominates the other, so a value both of them name is worked out at or above the head, and the one store is written where it is available.

The same value rather than the same address is also where most of what this does not catch goes, so the two refusals are counted separately and say which. if (x > 128) q[i] = 128; else q[i] = x; works q + i out twice, once in each arm, and two instructions that compute the same address are two values, so this walks away from a diamond whose two stores go to the same place by any reading a person would give it. What fixes that is document 16’s value numbering turning the two into one, not anything about memory, and hoisting the address by hand into int *p = &q[i]; is enough to get the fold today.

volatile and atomic are refused. volatile because section 22.6 says never, and the reason is not that the flags fail to match: how many accesses there are and what order they come in are both observable, and a value that arrives through a select is a different program from one that arrives through a branch. Atomic for the ordering rather than the access, since a store with an order on it is a fence as much as a write.

What a select is built for

Two sides disagree about a parameter when they hand the join different values, and also when they hand it different values that are the same number. The second half is there because the corpus has eight diamonds whose two arms both work out the same constant, in separate instructions that nothing has hash consed into one, and the tier six rule select(c, x, x) -> x does not reach them for exactly the same reason: two operands that are not one value do not match a pattern that writes one name twice. What would reach them is document 12.1’s hash consing or document 16’s value numbering, and until one of those exists the cheap question is worth asking here, where the alternative is a select this pass wrote itself between two sevens.

Why moving an arm’s work into the head is safe

Because the arm has exactly one predecessor, which is the head. That is checked, and it is the whole of the argument in both directions.

Downward: an instruction in the arm reads values that dominate the arm, and the head dominates the arm too, so every one of them is available where the instruction is going. Upward: nothing outside the arm can read what the arm defines except by the arm’s own jump, since the arm dominates only itself, and that jump’s arguments are exactly what the selects are built out of. An arm with two predecessors would break both halves at once, which is why the check is on the predecessor count and not on the shape of the graph around it.

The loop rules that spec/optimizer/23-jump-threading.md needs are not needed here, and the reason is worth writing down rather than leaving as an absence. No edge is added, so no loop gains a second way in and no loop can become irreducible. An arm cannot be a loop header, since a header has a back edge and this arm has one predecessor and it is not itself. An arm can be a latch, and then the head becomes the latch instead, which keeps the single latch property document 07.3 wants rather than spoiling it. The one shape that would matter is a join that only its own arms reach, which is a region unreachable from the entry, and the pass asks whether the head is reachable before it looks at anything.

What it refuses, and every one of them is section 22.6

An arm that does something. The predicate is rucc_ir::Opcode::has_effects, which is what dead code elimination deletes an instruction under, so an arm this pass will hoist is an arm whose instructions could have been deleted outright had nothing read them. A call, a volatile access and a load are all effects by that answer, which closes the second and sixth failures in section 22.6 with one question. The one exception is the pair of stores above, which is the one effect this pass moves and is allowed to because moving it does not change what happens.

A store the other side does not match. That is the first failure in section 22.6 and it gets a reason of its own rather than the general one, because it is a different answer rather than a stricter one: the transformation exists, it is section 22.2’s fourth, and what is missing is the proof that the location is written whatever happens.

An arm that divides. Division is not an effect, because nothing observes it and dead code elimination is right to delete one, but it traps, and a trap on a path that did not have one is section 22.6’s third failure. The exception is a divisor that is a constant which is neither zero nor minus one, which cannot trap and is most of the divisions real code contains.

A value the two sides disagree about whose type has no select. The IR names a select at eight, sixteen, thirty two and sixty four bit integers and at nothing else, so producing one of any other type would build a term the back end has no rule for. That is an invisible gap rather than a wrong answer, and the producer is the side that has to avoid it. It is asked after the condition has had its say, because a value nothing has to choose between needs no select and so does not need one that can be lowered.

A branch that is already decided. Section 22.6 does not list this one and the corpus found it, on a program whose source says if (1). simplify-cfg runs after this pass and turns a decided branch into a jump, and then the arm that cannot run is deleted whole and its work with it. Converting first replaces a branch that costs nothing at run time with a select that costs something, and it keeps alive the work in the arm that never ran, because the fold that would undo it is select(1, a, b) -> a and that rule does not exist yet. The case cost twenty eight bytes of .text and a multiply that could not happen.

The question is put to simplify_cfg::taken rather than answered again here, for the reason that function’s own documentation gives: two answers about when a branch is decided would be two compilers. It matters in this case rather than being tidiness. The condition on if (1) is not a constant, it is icmp ne 1, 0, and fold leaves that standing on purpose, because nothing lowers an i1 by itself and folding one would turn working code into code that does not build, which is issue 352. taken reads the answer off without leaving anything standing, since the branch that was the comparison’s only reader goes at the same time.

The cost rule

Section 22.2 states it and this implements it without softening it.

Both arms empty of instructions: convert, always. The select replaces a branch with one operation that reads two values which already exist, and there is no machine where that is worse. Nothing about predictability enters, because there is nothing being speculated.

What is factored does not count as work. Both arms did the operation, one of them was always going to do it, and afterwards one copy of it runs whichever way the branch would have gone, so nothing is being speculated. A diamond whose arms factor away entirely converts on the same terms as a diamond with empty arms, and one that factors down to two instructions is judged on the two rather than on what it started as.

Arms with work left in them: up to heuristics::PHIOPT_ARM_INSTRUCTIONS instructions each, and only when the branch probability is within heuristics::PHIOPT_UNPREDICTABLE_MARGIN_PERCENT of even by document 11’s estimate. A branch the estimate calls one sided keeps its branch, because if the estimate is right the branch is free and the arm is not.

The estimate is usually a guess and the guess is often wrong, which section 22.6 lists as the failure with no defence. Note where that leaves an unpredicted branch: document 11 answers even and says it is guessing, even is inside the margin, so a branch nothing is known about is treated as unpredictable and converted. That is the aggressive reading and it is deliberate, since the alternative is a pass that fires on almost nothing and measures nothing.

It is also, today, the only reading, and that is worth saying rather than leaving to be discovered. Every static predictor in document 11 that gives a one sided answer keys on something one arm of the branch does and the other does not: one arm never comes back, one arm calls something cold, one arm leaves the loop, one arm returns a negative number. A diamond has neither of those, because both of its arms fall through to the same block, so the predictors that could refuse a conversion here are exactly the ones a diamond cannot trip. What is left is the branch condition itself, which is __builtin_expect at ninety percent and the pointer heuristic at seventy, and only the first of those is outside the margin. __builtin_expect is dropped in the front end today, so until it is wired the probability half of the rule refuses nothing at all. The check is here rather than deferred because leaving it out would mean the measurement never showed that, and because the day the hint is wired is the day it starts mattering.

Which level, and how many times

Every level that optimizes, which is section 22.2’s -O1 and above.

Once. Section 22.7 asks for two instances at -O2, one before the loop pipeline and one after, because the loop passes make diamonds. There is no loop pipeline yet, so the second instance would be a second walk over every function to find the shapes the first one already took, and it belongs in the change that adds the passes it exists to clean up after.

Section 22.2 also wants a peephole run after this one, so that the rule set can answer what the select becomes: select(c, a, a) is a, select(c, 1, 0) is zext(c), and the min, max and abs recognitions are all rules rather than code here. Those rules are tier six of spec/optimizer/13-rewrite-rules.md and none of them are written, so the run that would fire them is not in the pipeline yet either. It goes in with them.

Structs

PhiOpt

The pass.