simplify.pl
A cheap middle end (docs/perf.md item 8), run after copy propagation on unchecked IR in strict SSA form: simplify_module/2 folds constants, simplifies booleans and identities, numbers pure values, folds constant branches, removes unreachable blocks and dead pure definitions, and merges straight-line blocks. Selected with --simplify=full.
What it may change
Only values and control flow that no memory access, call or trap observes. Every load, store, call, alloc, division, va_arg, cas and fence stays, in its order, with its arguments' values: a removed or rewritten definition is pure (pure_op/2: no memory, no effect, no native trap), so no check is added, removed or moved, and no trap changes its time or reason. Constant operations are evaluated by the interpreter's own alu/4, so a folded value is the one the IR's semantics gives (a division by zero is 0, as Fil-C's is since deluge); one that would be undefined (an invalid float conversion) is left alone. Pollchecks are not in unchecked IR: pizlonation adds one on every edge to a block at or before its source, so every cycle of the result still polls.
Rules
| Rewrite | When |
|---|---|
Op(c1, c2) to its value | integer Op of w or l constants, its value defined |
x + 0, x - 0, x | 0, x ^ 0, x << 0, x * 1, x & ~0 to x; x * 0, x & 0, x - x, x ^ x to 0 | integer classes; a shift count is read modulo the width |
x * 2^k to x << k, x udiv 2^k to x >> k, x urem 2^k to x & (2^k - 1) | integer classes |
a constant first operand of add, mul, and, or, xor or an integer cmp second | the backends encode an immediate second operand |
b != 0, b == 1, extT of a boolean b (0 or 1) to b | the result's class has an equal boolean |
extT2 of a loadT or extT value x to x | every T is a T2, and the result's class is x's |
(a C b) == 0 to a C' b | C an integer condition, C' its negation |
branchb ≡ 0, L1, L2 to branchb, L2, L1 | b a boolean |
| a pure operation already computed in a dominating block to that value | same class, operation and operands (commutative operands in either order) |
branchc, L1, L2 to goto | c constant, or L1 = L2 |
Then blocks no longer reachable go, with their phi edges; copies and trivial phis go (copy.pl), up to three rounds while branches fold; pure definitions nobody uses go; a block whose only predecessor jumps to it is appended to that predecessor; and an empty block that only jumps on, whose predecessors do not already reach its successor, is bypassed, its phis moved into the successor's.
Functions that are not in strict SSA form, and functions that call setjmp, are left alone. Source contexts follow: instruction sites are re-indexed, sites of removed blocks, instructions and phis go, and the values keep their records as history.
M is M0 with each strict SSA function simplified.
The cut leaves no choicepoint per function (promote_item/4).
F is the function F0 simplified as the header says, and Records its context: sites re-indexed, those of removed blocks, instructions and phis dropped, and removed values kept as history. F0 not in strict SSA form, or calling setjmp, is left alone.
fold, remove the replaced definitions (copy.pl's substitution) and the unreachable blocks; again, up to N rounds, while a branch folded (its successor's phis may have become constant). Each rewrite keeps strict SSA, so later rounds need not check it again.
F is F0 without the phis whose operands, other than the phi itself, are one value, which replaces it. A pruned edge or a bypassed block leaves these; one pass, following replacements by other such phis (copy.pl's copy_reps/4: after pruning every phi is reachable, so strict SSA rules out cycles among them).
Folding: a walk of the dominator tree
The state st(Reps, Bools, Defs, Out, Folded) is threaded through the walk; Avail, the pure values computed in the dominating blocks, is passed down only, so it is scoped to the subtree.
| Part | Is |
|---|---|
| Reps | assoc Temp -> the value that replaces it (a same-class temp or a w/l constant) |
| Bools | assoc Temp -> K-Temp pairs equal to it, each 0 or 1 |
| Defs | assoc Temp -> cmp(Cond, K, A, B) for an integer comparison, not(B) for B == 0 of a boolean B, or narrow(T) for a load or extension of narrow type T |
| Out | assoc Label -> the rewritten block |
| Folded | true once a branch became a goto |
A phi whose operands, other than itself, are one value is that value; its operands from blocks not yet visited are not substituted yet, so this is conservative, and copy.pl finds the rest.
what the kept definition D = Op(Args) tells later rewrites.
Simplification of one operation
simplified(+K, +Op, +Args, +Cx, +Bools, +Defs, -R): R is value(V), the operation is V read at class K (a copy), or op(Op1, Args1), an equivalent operation. Args have the replacements applied.
algebraic identities of integer operations at class K; a constant operand is second.
a comparison of a boolean with 0 or 1, or of a value with itself.
E is a temp of class K among Eq.
Op is pure, and Key identifies its value: commutative integer operands in a fixed order. A pointer plus or minus a constant (a field's address) is numbered only within its block L: recomputing it is one add the backend folds into the access, while sharing it down the dominator tree keeps a pointer and its capability live across the function. In bzip2's BZ2_decompress that cost 20% more cycles for 4% fewer instructions (docs/perf.md, item 8).
Op reads no memory, has no effect and does not trap natively, so its definition can be removed or shared. (A float_to_int whose value is undefined is ub in the interpreter, which refinement allows to disappear; Fil-C does not trap there.)
Unreachable blocks
F is F0 without its unreachable blocks, and each phi without the operands of edges that no longer exist.
Rs is Rs0 without the sites of the blocks Labels and the phis Phis.
Dead pure definitions
F is F0 without the pure definitions and phis whose values nothing that stays uses, transitively.
Merging blocks
Both rewrites below run over the blocks in order once, with Index (assoc Label -> block) and Preds (assoc Label -> the labels of its incoming edges, one per jump target) kept current.
F is F0 with each empty block that only jumps on bypassed, then each block whose only predecessor ends in a goto to it appended to that predecessor. Merged is true if a block went.
assoc Temp -> how many operands read it.
M is m(Index, Preds, Uses, Bypassed, DeadPhis). E, empty, not the entry, ending in goto(T), goes when each predecessor P reaches it once, by a plain edge, and does not reach T already, and E's phis are read only by T's operands from E. Each P then jumps to T, and T's operand from E becomes, for each P, that operand with E's phis read as their operands from P: a value read there was defined in a block dominating E, so it dominates each P.
S has no phis or at most 64 incoming edges. Rewriting a join's phis is linear in its edges, so each block merged into a dispatch loop's header would otherwise cost the whole header, quadratic over its cases.
T's phis read tmp(D) N times, all as operands from E.
A is a(Index, Preds, Moves, JumpOf). While B ends in goto(T), T is not the entry, has no phis and B is its only predecessor, T's instructions and jump follow B's. Moves: T -> B-Offset, T's instructions now in B after Offset others; JumpOf: B -> the label whose jump B now ends with.
S's edges from T come from B.
an appended block's instruction sites follow it, a holder's jump site is that of the block whose jump it now has, and the sites of bypassed blocks and their phis go.