Module narrow 

Width narrowing: arithmetic redone at the width the program actually uses.

The lowering rule set is written at an opcode and a width together, so add.i8 and add.i32 are two rules and the machine can be asked to add two bytes as easily as two words. C never asks it to. The integer promotions say the operands of an arithmetic operator go to int first, so char a, b; a + b is an int addition of two sign extended bytes, and the front end is right to write it that way because that is what the language says the expression means.

That leaves the promoted form as the only form, and on x86-64 it is often the wrong one. A byte compare against a byte is a cmpb, and two movsbl are not needed to reach it. A byte add whose result is stored back into a char throws away every bit the promotion computed. The promoted shape exists because C says so and not because the machine wants it. This is issue 375.

The two shapes

A truncation of arithmetic. The low bits of a sum, a difference, a product, a bitwise operation or a shift by a constant depend only on the low bits of what went into it, so trunc.i8 (add.i32 (sext a) (sext b)) is add.i8 a b and the two extensions are left with nothing reading them. That is the arithmetic half, and it is what char c = a + b; is.

A comparison of extensions. Sign extension is an order isomorphism onto its image under both readings of the bits, so a comparison of two of them at any predicate is the same comparison of what they extended. Zero extension is one under the unsigned reading and is not one under the signed reading, since it takes a negative byte to a positive word, so it carries the equalities and the unsigned predicates over and not the signed ones. That is what char a, b; a < b is.

Both are written so that one side may be a constant instead, because if (c == 'x') is the common case and the constant is representable at the narrow width whenever the comparison is not already decided.

Why it always pays

Neither shape is applied unless every leaf it reaches narrows for nothing. A leaf is what an extension extended, which is already the narrow value, or a constant, which is written down again. So the rewrite replaces a wide operation, its extensions and the truncation with one narrow operation and never leaves a widening behind to pay for a narrowing. Everything in between is required to have exactly one reader, which is the operation above it, so the whole subtree it replaces is dead the moment it is replaced.

That is the whole profitability argument, and it is deliberately a structural one rather than a cost model. A pass whose payoff has to be estimated is a pass whose payoff can be wrong.

What it does not narrow

Not a divide or a remainder. char a = -128, b = -1; char c = a / b; is well defined in C: the division happens at int, gives 128, and the conversion back to char is what makes it minus 128 again. The same division at one byte is the overflow case that raises on this machine, so narrowing it turns a program that works into a program that dies. It needs a range that says the operands miss that one pair, and ranges are the analysis this pass does not have.

Not a shift by a value. char c; c <<= n; shifts at int, so a count of twenty is a defined shift whose low eight bits are zero, and the same count at one byte is poison. A shift by a constant below the narrow width has neither problem and is narrowed.

Not a signed operation’s overflow flags. A sum that could not overflow at four bytes can overflow at one, so nsw and nuw do not come along. Dropping them is a refinement in the safe direction: it makes the operation more defined rather than less.

What is left for the analysis

The width here is the one the truncation names. A real demanded bits analysis would let it shrink further, so that (x & 0xff) + 1 narrows on the strength of the mask rather than on the strength of a truncation that is not written, and so that a value read at three widths is narrowed to the widest of them rather than to none. That is the first box of issue 375 and it wants the analysis manager, which wants the dominator tree, which is the next thing to build.

Structs

Narrow

The pass. It holds nothing, because the width it narrows to is the one the truncation names.