Module select_hoist 

select_hoist — a decision fabric’s selects hoisted out of its arithmetic: every select an add, a shift or a compare reads is cofactored away, so the fabric becomes arithmetic over its inputs, compares of that arithmetic, and one tree of selects over the compares’ outcomes.

decision_fabric_from_source if-converts a decision into a chain: a compare picks a value, the value feeds a sum, the sum feeds the next compare, so the decision’s depth is every carry chain along the chain in series. For any pure f, f(p ? t : e) = p ? f(t) : f(e): f can compute on both arms at once, before p is known. Applied until no select is read by anything but another select’s arm (the Shannon expansion of the fabric on its predicates), every carry chain reads only inputs and other carry chains, and the decisions resolve in one tree of selects after them.

Predicates are canonical, x < y (signed) or x = y: >, ≥, ≤ and ≠ swap the operands or the arms. A predicate decided on a path is decided wherever it recurs on that path, and so are its converses (x < y makes y < x and x = y false). Nodes are hash-consed, so cofactors that meet again are one node. Once no select feeds arithmetic, the tree is rebuilt with its predicates ordered by when they arrive (the depth of their compares, in the units of op_delay), the latest at the root: a late compare drives the select next to the output instead of passing through the whole tree.

The pass takes a datapath width, as the carry-save lowering does. Constants are width-bit words: a fold or a constant compare is the one at that width, so the pass at a narrow width is the pass at 64 bits restricted to it, and our SAT can check it exhaustively there. Shifts never fold: a shift count past the width means different things at different widths.

Constants

HOIST_NODE_LIMIT

The nodes a hoisted fabric may grow to before the pass refuses it: an expansion that would outgrow this many is one whose predicates do not collapse, and the fabric is better left as it is.

Functions

hoist_selects

df with every select its arithmetic or compares read cofactored away and its tree of selects ordered latest predicate first, at datapath width width (64 on silicon; narrower so our SAT can check the pass exhaustively). Refused when df holds a cell with no combinational form (a functional unit, a memory or heap tile), or when the expansion outgrows HOIST_NODE_LIMIT.

reads_a_select

Whether arithmetic or a compare of df reads a select’s value: what hoist_selects leaves none of.