Module bits 

Taking out a conversion whose bits nothing reads.

Design: spec/optimizer/37-machine-level-optimization.md section 37.4.

A register is one register at every width, and what says how much of it is in play is the instruction naming it. movzbl %sil, %edi writes thirty two bits of rdi and reads eight of rsi, and if the only thing that ever reads rdi is a movb, then the twenty four bits the widening worked out are bits nobody ever looks at. What is left of the widening once those bits are taken away is a copy of eight bits into a register, which is what the instruction after it was going to read anyway, so the widening goes and its readers read its source instead.

That is the bit group liveness of gcc/ext-dce.cc at the width this compiler needs it at. Liveness answers whether a register is read at all, this answers how much of it is read, and the second question is the first one asked per group of bits rather than per register. Section 37.4 says to build this one of the two passes it offers, because it is more general than compare elimination and because the analysis is the liveness the allocator already computes with a number on it.

Where the conversions come from

Not from code anybody wrote. C promotes nearly every operand of nearly every expression to int before doing anything with it, so a program that adds two chars widens both of them, adds at thirty two bits and stores eight, and the front end writes every one of those conversions out because each of them is in the language’s own description of what the program means. crate::widths and tier four of the rewrite rules take the ones that are two instructions next to each other in the same block. What is left for this pass is the ones that are not: a conversion in one block whose readers are in another, and a conversion the selector itself wrote because the machine instruction it picked wanted its operand at a width the value did not arrive at.

What it finds, measured

Both directions of conversion are in scope and only one of them turns up, which was not what was expected and is worth writing down rather than rounding off. Over the 1916 programs of tamnd/rucc-corpus at -O2 this takes out 970 instructions and puts back 45, and not one of the 7040 widenings in that assembly is among them: the count of movz and movs is the same before and after. What goes is 469 movl, 259 movw and 242 movb between registers, which are the narrowings, and the 45 that come back are movq, which is the allocator wanting a plain copy where a narrowing had been doing that job as well as its own.

That is tier four of the rewrite rules having already been through the corpus. A widening the rules could not reach is one whose upper bits some reader really does read, and there is nothing here for a bit counter to find in it. A narrowing is the other way round: the machine writes one where a value is put in a register at a width, and whether the bits above it matter is a question about every reader of the result rather than about the pair, which is the question only this pass asks.

2091 bytes of .text over the corpus, 76 programs smaller and two larger by a byte each, and 2048 bytes off SQLite’s amalgamation at -O2. The two that grow are an eight bit division, where every narrowing that goes was also the move that got the answer out of the register the division fixes, so the allocator writes a full width copy of the same pair in its place. Nine of the ten are the same length either way and the tenth is movb %dl, %bl becoming movq %rdx, %rbx, which is the one byte: the byte names of those two registers need no prefix and the sixty four bit move needs the one that says so.

The analysis

One number per register, which is how many of its low bits anything reads. It starts at none and grows, so a register nothing has been seen to read yet is one whose answer is still being worked out rather than one nothing reads.

Three things raise it. An instruction reading a register raises it to the width that instruction names the operand at, which is rucc_target::BitInsts::width and is the target’s answer rather than this pass’s. An edge carrying a register into a block raises it to whatever the parameter it arrives as needs, which is what carries the answer across a block boundary and is the whole reason this finds anything the rules do not. And an instruction that copies the low bits of its source raises its source only as far as its own result is read, since the bits of the source above that are bits it puts nowhere anything reads.

The last of those is what makes the answer a fixpoint rather than a walk: a chain of conversions passes the number back along itself, and how far it passes depends on a number the same pass is still working out. It only ever grows and it is bounded by the widest operand on the machine, so it settles.

What it will not do

An operand the target’s description does not name at a width. An address register, an operand of an opcode written as no instruction at all, and an opcode from somewhere other than this target all answer that they read everything, which is section 37.7’s warning honoured by construction: a store reads every bit of the value it stores because the description says the operand is as wide as the store is, and anything the description is silent about is treated as reading the lot rather than as reading nothing.

A physical register on either side. Machine IR is in SSA form until the allocator has run, so a virtual register is written once and the register a reader would be sent to instead still holds what it held. A physical one is not: the frame pointer and the stack pointer are already physical here and a call writes every register it is allowed to, so sending a reader to one of those would be sending it to whatever happened to be there.

A conversion whose result is read as wide as it is written. That is a widening whose upper bits somebody does read, which is the whole instruction doing its job.

A conversion whose result nothing reads at all. That is an instruction that computes something nobody wants, which is dead code rather than dead bits, and taking it out here would be this pass answering a question it was not asked and reporting a number that says it found widenings it had not. What this is about is a register something reads less of than was put in it.

How the rewrite is made

One conversion at a time, as a set of changes crate::changes either takes or turns down. The set is the readers sent to the source and the conversion taken out, and those two are worth nothing apart: a reader left behind reads a register nothing writes any more. So the set is where the question is asked, and a reader this pass failed to find is a set that is refused rather than a function with a hole in it.

The readers an edge holds are in the set the same way. A conversion in one block whose reader is in another is the case this pass is here for, and the argument the edge carries is how the value gets there, so sending it somewhere else is half of what taking the conversion out means.

Where it runs

After selection and before allocation, which is the window where the machine instructions exist and the registers are still virtual. Section 37.6 puts it third in the group that runs there, after combining and if-conversion and before compare elimination and addressing-mode folding, and that is where crate::pipeline calls it.

Functions

dead

Takes out every conversion whose result nothing reads above the width of its source, and gives back how many.