Module schedule 

Putting the instructions of a block in the order that finishes soonest.

Design: spec/optimizer/38-scheduling-and-layout.md sections 38.1, 38.6 and 38.7.

Every instruction in a block is going to run, in some order, and the orders that compute the same thing are the ones that keep each instruction behind the ones it reads from. Among those orders, one finishes before the others, because the machine does not answer every instruction in one cycle: a multiply takes three, a load takes five, and an instruction that reads what one of them wrote cannot start until it is done. Putting independent work in those cycles rather than waiting is the whole of this pass.

The algorithm, and where it comes from

A list scheduler, which is gcc/haifa-sched.cc’s. Build a graph of what depends on what, take the instructions whose dependences are all satisfied, choose one, repeat. Everything a scheduler is is in how it chooses, and gcc/haifa-sched.cc:55 writes that out as a list of eight tiebreaks. Section 38.1 goes through them and says which are rucc’s: one, two, six, seven and eight. Three, four and five are about moving instructions between blocks and about moving them where they might not have run, and this pass does neither.

So what this pass chooses by is five numbers in that order:

1. The longest path from here to the end of the run, in cycles. This is the criterion, and the other four are for when it ties. An instruction on the critical path delays everything behind it by exactly as much as it is delayed, and one that is not on it is free until it is.
2. How many more registers are live after it than before. Section 38.1 quotes gcc/haifa-sched.cc:87 on what this is for: “if an operation requires that constants be loaded into registers, it is certainly desirable to load those constants as early as necessary, but no earlier”. An instruction that writes a register and reads nothing that dies is one whose value now has to be kept somewhere, and hoisting it to the top of a block because it depends on nothing is the classic way a scheduler makes a function worse.
3. Whether it reads what the instruction just scheduled wrote. It does not have to, since the graph would have stopped it if it were not allowed, but one that does will wait and one that does not will not.
4. How many instructions depend on it. Scheduling one of these makes more work available to choose from later, which is what keeps the ready list from running dry.
5. Where it was to start with. This is not a heuristic. It is what makes the output a function of the input, and it has to be a position rather than anything that comes out of a hash map, for the reason spec/10-backend.md gives about a compiler whose output moves between runs.

Why it runs after the registers are handed out

Section 38.6 decides it: “One scheduler, after allocation, before the layout freeze.” The argument section 38.7 makes for that placement is the one that matters here. The dominant way a scheduler makes a program worse is by holding more values live at once than there are registers, so the allocator spills, and the spill costs more than the latency the schedule hid. After allocation that cannot happen: every value is already in a register, no reordering this pass can make changes which register anything is in, and nothing is left that could decide to spill.

What it costs is that the registers are the constraint instead. Before allocation a value is written once, so the only dependence between two instructions is that one reads what the other wrote. Afterwards the same register holds a dozen different values over a block, so an instruction that writes one has to stay behind everything that reads what was in it, and those orderings are real even though no value passes between the two instructions. That is most of what the graph below is made of, and it is why this pass finds less to do than one before allocation would.

How much less has now been measured, and the honest answer is almost all of it. Five programs built with this on and with it off, best of five runs each, on a six core Xeon with gcc 16 as the reference:

program    off    on   accurate   gcc-16 -O2
ilp         75    75     78          60
serial     213   212    215          58
mem         47    49     49          40
fp         271   267    266         108
branchy    119   122    121          81

Milliseconds, and the run to run spread on this machine is a few of them, so every column here is the same column. That is the measurement section 38.8 asked for and it says this pass is currently worth nothing on these five programs. Two reasons, and the first is the one above: by the time this runs the registers have been handed out, so the same register holds a dozen values over a block and the anti and output edges that creates pin most of the order in place. The second is that the gap to gcc is not a scheduling gap. A factor of three and a half on serial and two and a half on fp is work gcc did before it got anywhere near an instruction order, and no permutation of the instructions rucc emits closes it.

The pass stays, at -O2 and above, for what it costs rather than for what it currently returns: it is sound, it is cheap, and it is the thing that has to exist before the latencies in rucc_target::TimingInsts mean anything at all. The column worth watching is accurate, which is the same model told to believe its own unit counts, and which is slightly worse on the one program with real instruction level parallelism in it. That is the model being wrong about units in exactly the way rucc_target::TimingInsts::accurate says it is, and it is why x86-64 answers false.

What the graph is made of

Four kinds of edge, and the first three are gcc/sched-deps.cc’s REG_DEP_TRUE, REG_DEP_OUTPUT and REG_DEP_ANTI over registers:

• One instruction reads a register another wrote, so it waits for the value.
• Two instructions write the same register, so they stay in order or the register ends up holding the wrong one of them.
• One instruction writes a register another read, so the read stays in front of the write.

The fourth is the condition state, which on this kind of machine is a register nobody named. It is not in an operand vector, so the three kinds above do not see it, and the target says which instructions write it and which read it. Getting this wrong is a miscompile and the failure looks like a target description that forgot a clobber, which section 38.7 says is the same root cause as every other missing-clobber bug.

Memory, and why it is one chain

Every instruction that touches memory or computes an address stays in the order it was in, relative to every other one. That is stronger than it has to be. gcc/haifa-sched.cc:71 is candid about the trade: “only if we can be certain that memory references are not part of the data dependency graph… can we move operations past memory references. To first approximation, reads can be done independently, while writes introduce dependencies.”

rucc cannot take the first approximation here. Machine IR does not carry volatile, which crate::copies says at length: a read the program insisted on and an ordinary one are the same instruction with the same operands by the time this runs. So two reads are not interchangeable either, and the only safe answer at this level is to leave the accesses in the order they arrived in. That is also the answer crate::combine gives, for the same reason and through the same question to the target.

Address computation is in the chain as well, and not because an address is a memory access. It is because the stack pointer moves without saying so. A push and a pop change it and name it in no operand, so an address counted from it means different things on either side of one, and anything that carries an addressing mode is something that could be counted from it. Putting them all in one chain costs a little freedom around lea and needs no new question of the target.

What nothing moves across

A call, because what a call does to memory and to the registers a convention does not preserve is not in its operands. An instruction the target does not describe, on the same reasoning backwards. An instruction the target describes as doing something the timing model does not cover, which is Unit::Fixed: a fence, a trap, a landing pad, the padding a patcher was promised. And an instruction that carries a frame rule, because those rules say what the unwinder should believe at each address in the prologue and the epilogue, and an instruction that moves takes its rule with it to an address where it is not true.

The last instruction of a block, as well, along with whatever the caller has pinned. What a block leaves on is the last thing in it by the time crate::layout runs, and the layout is what turns the arms of a block into jumps, so a block whose condition is not at the end of it is a block the layout cannot write. What the caller pins is the comparison the layout is going to fuse with that condition, since the two have to stay next to each other for the fusion to happen and nothing here would otherwise keep them there.

Each of those splits the block into runs, and a run is scheduled on its own with everything before and after it left where it was. A block with no barrier in it is one run.

The bound

READY instructions are considered at each step and no more, which is gcc/params.opt:761’s max-sched-ready-insns, Init(100), and section 38.8 asks for the same bound for the same reason: choosing is linear in the ready list and the ready list can be as long as the block. LONGEST is the second half of it, a run this pass will not build a graph for at all, because building one is quadratic in the worst case and a block of several thousand machine instructions is a generated table rather than something anybody is waiting on.

What makes it correct

The order this writes is a topological order of the graph, and nothing else about the pass is load bearing. The timing model chooses among the orders the graph allows and cannot choose one it does not allow, so a model that is wrong about every number produces a slower program and not a different one, which is what spec 10.5 says the right failure mode is. What has to be right is the graph, and what makes the graph right is that every edge the machine needs is in it.

Structs

Scheduled

What one function came to.

Constants

LONGEST

The longest run of instructions this will schedule.

READY

How many instructions are looked at when choosing the next one.

Functions

insts

Puts each block’s instructions in the order the machine finishes soonest.