8000 Update NarrowingPass documentation comment. by copybara-service[bot] · Pull Request #5521 · google/xls · GitHub
[go: up one dir, main page]

Skip to content
Draft
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2,605 changes: 1,374 additions & 1,231 deletions docs_src/passes_list.md

Large diffs are not rendered by default.

192 changes: 77 additions & 115 deletions xls/passes/bit_slice_simplification_pass.h
Original file line number Diff line number Diff line change
Expand Up @@ -29,126 +29,88 @@ namespace xls {
//
// Note: What follows was generated by the Gemini LLM. Not human verified.
//
// The `BitSliceSimplificationPass` is a crucial optimization pass that targets
// and simplifies operations related to bit manipulation: `bit_slice`,
// `dynamic_bit_slice`, and `bit_slice_update`. The overarching goal is to
// reduce logical complexity, enhance hardware efficiency, and generate cleaner
// IR by eliminating redundancies and transforming patterns into more canonical
// forms that are easier for hardware synthesis tools to process.
//
// The pass employs a combination of local pattern matching and advanced query
// engine analysis (utilizing `LazyTernaryQueryEngine` or
// `PartialInfoQueryEngine` for higher optimization levels) to identify and
// capitalize on simplification opportunities.
//
// Key simplifications performed by this pass include:
//
// 1. **Simplifying `BitSlice` Operations**:
// * **Full-Width Slices**: A `bit_slice` that extracts the entire bit
// width of its operand (e.g., `bit_slice(x, start=0, width=N)`) is a
// no-operation and is directly replaced by its operand `x`.
//
// * **Consecutive `BitSlice` Operations**: Nested `bit_slice` operations
// (e.g., `bit_slice(bit_slice(x, s0, w0), s1, w1)`) are collapsed into
// a single `bit_slice(x, s0 + s1, w1)`, effectively combining the
// slicing operations.
//
// * **Hoisting `BitSlice` above `Concat`**: A `bit_slice` of a `concat`
// operation can often be rewritten as a `concat` of smaller
// `bit_slice`s of the original `concat` operands. This allows for more
// precise extraction of relevant bits and can eliminate unnecessary
// concatenations.
//
// * **Hoisting `BitSlice` above Bitwise/Arithmetic Operations**: If a
// `bit_slice` is the *sole consumer* of a bitwise operation (e.g.,
// `and`, `or`, `xor`) or targets the low bits of an arithmetic
// operation (e.g., `add`, `sub`, `neg`), the `bit_slice` can be pushed
// down into the operands. This transforms `bit_slice(op(A, B), ...)`
// into `op(bit_slice(A, ...), bit_slice(B, ...))`, reducing the width
// of the intermediate `op` result.
//
// * **Hoisting `BitSlice` above `SignExt`**: Handles various cases where
// a `bit_slice` operates on a `sign_ext` operation. It simplifies this
// by transforming it into a direct slice of the original value or a
// `sign_ext` of a smaller slice, depending on where the slice falls
// relative to the sign bit of the extended value.
//
// * **Hoisting `BitSlice` above Shifts and Decodes**: If all users of a
// shift or decode operation are bit-slices entirely contained within a
// larger slice, the `bit_slice` can be hoisted above the shift/decode.
// This effectively performs the shift/decode on a smaller bit-width
// operand, reducing computation.
//
// * **Hoisting `BitSlice` above Selects**: If all users of a `select` (or
// `one_hot_select`/`priority_select`) are bit-slices entirely contained
// within a larger slice, the `bit_slice` can be hoisted above the
// `select`. This results in the `select` operating on smaller, sliced
// operands, which can reduce the multiplexer complexity.
//
// 2. **Simplifying `DynamicBitSlice` Operations**:
// * **Out-of-Bounds Slices**: A `dynamic_bit_slice` whose start index is
// provably out of bounds (meaning it attempts to slice entirely beyond
// the operand's bit width) is replaced with a literal zero, as no data
// can be extracted.
//
// * **Literal Start Index**: A `dynamic_bit_slice` with a known constant
// start index is converted into a static `bit_slice` operation. This
// eliminates dynamic addressing logic in the hardware.
//
// * **Hoisting `DynamicBitSlice` above `Select` of Literals**: If the
// start index of a `dynamic_bit_slice` is the result of a `select`
// operation where all the cases are literal constant values, the
// `dynamic_bit_slice` can be hoisted. This replaces the original
// `select` with a new `select` whose cases are static `bit_slice`
// operations, each corresponding to one of the literal start indices.
// The `BitSliceSimplificationPass` optimizes `bit_slice`, `dynamic_bit_slice`,
// and `bit_slice_update` operations in the IR. It combines local pattern
// matching with a `UnionQueryEngine` (pairing `StatelessQueryEngine` with
// `PartialInfoQueryEngine` when `opt_level >= 3`, or `LazyTernaryQueryEngine`
// at lower optimization levels).
//
// The pass first visits nodes in reverse topological order to simplify
// `dynamic_bit_slice` and `bit_slice_update` nodes, and then processes all
// static `bit_slice` nodes via a worklist until reaching a fixed point:
//
// 1. **Simplifying `DynamicBitSlice` Operations**:
// * **Out-of-Bounds Start**: If `MinUnsignedValue(start)` is at least the
// bit width of `to_slice`, replaces the slice with a zero `literal`.
// * **Constant Start Index**: Converts a `dynamic_bit_slice` with a
// statically known `start` into a static `bit_slice` (zero-extending if
// the slice extends past the MSB of `to_slice`).
// * **Lifting through Select of Literals**: If `start` is produced by a
// tree of `sel`, `priority_sel`, or one-hot `one_hot_sel` nodes whose
// leaves are known constants, lifts the slice into the select tree so
// each leaf becomes a static `bit_slice`:
//
// ```
// // Original IR
// start1: bits[32] = literal(value=5)
// start2: bits[32] = literal(value=25)
// p: bits[32] = select(x, cases=[start1, start2])
// q: bits[45] = dynamic_bit_slice(to_slice, p, width=45)
//
// // Optimized IR (conceptually)
// slice1: bits[45] = bit_slice(to_slice, start=5, width=45)
// slice2: bits[45] = bit_slice(to_slice, start=25, width=45)
// q: bits[45] = select(x, cases=[slice1, slice2])
// s0: bits[32] = literal(value=5)
// s1: bits[32] = literal(value=25)
// start: bits[32] = sel(p, cases=[s0, s1])
// ret q: bits[16] = dynamic_bit_slice(x, start, width=16)
//
// // Optimized IR
// slice0: bits[16] = bit_slice(x, start=5, width=16)
// slice1: bits[16] = bit_slice(x, start=25, width=16)
// ret q: bits[16] = sel(p, cases=[slice0, slice1])
// ```
//
// * **Scaled Dynamic Bit Slices**: Optimizes `dynamic_bit_slice`
// operations where the start index is a known multiple of the slice
// width. This involves conceptually treating the `to_slice` operand as
// an array of smaller bit elements and then using a `select` operation
// to choose the correct element from this conceptual array.
//
// 3. **Simplifying `BitSliceUpdate` Operations**:
// * **Out-of-Bounds Updates**: A `bit_slice_update` whose start index is
// provably out of bounds is replaced by its `to_update` operand, as it
// would have no effect on the target bit vector.
//
// * **Literal Start Index**: A `bit_slice_update` with a known constant
// start index is replaced by an equivalent `concat` and `bit_slice`
// structure. This eliminates the need for dynamic update logic in the
// hardware.
//
// * **Hoisting `BitSliceUpdate` above `Select` of Literals**: Similar to
// `DynamicBitSlice` with `select` of literals, if the start index of a
// `bit_slice_update` is derived from a `select` of literals, the
// `bit_slice_update` can be hoisted, resulting in static
// `bit_slice_update` operations for each case of the original `select`.
//
// * **Scaled Bit Slice Updates**: Optimizes `bit_slice_update` operations
// where the start index is a known multiple of the update value's
// width. This involves converting the `to_update` operand into an
// array of smaller bit elements, performing an `array_update` on this
// conceptual array, and then flattening the result back into a bit
// vector using `concat`.
//
// The pass operates in a worklist-driven fashion, particularly for `bit_slice`
// nodes, ensuring that simplifications are iteratively applied until a fixed
// point is reached. This comprehensive approach guarantees a thorough
// optimization of bit manipulation logic, crucial for high-quality hardware
// generation.
// * **Scaled Start Index**: When `start` is a known multiple of `width`
// (either because `width` is a power of two and `start` has enough low
// zero bits, or `start` is a non-overflowing `umul(idx, width)`),
// partitions `to_slice` into `width`-bit chunks and replaces the
// `dynamic_bit_slice` with a `sel` indexed by the unscaled `idx` (with
// a zero default if out-of-bounds indices are possible).
//
// 2. **Simplifying `BitSliceUpdate` Operations**:
// * **Out-of-Bounds Start**: If `MinUnsignedValue(start)` is at least the
// width of `to_update`, replaces the operation with `to_update`.
// * **Constant Start Index**: Replaces a `bit_slice_update` with a known
// constant `start` with a `concat` of `bit_slice`s of `to_update` and
// `update_value`.
// * **Lifting through Select of Literals**: If `start` is a select tree
// of known constants, lifts the `bit_slice_update` into the leaves as
// static `concat`/`bit_slice` updates.
// * **Scaled Start Index**: When `start` is a known multiple of the
// `update_value` width, slices `to_update` into an `array` of chunks,
// applies `array_update` using the unscaled index, and flattens the
// updated elements back into a bit vector with `concat`.
//
// 3. **Simplifying Static `BitSlice` Operations**:
// * **Full-Width Slice**: Replaces `bit_slice(x, start=0,
// width=width(x))` with `x`.
// * **Collapsed Nested Slices**: Combines
// `bit_slice(bit_slice(x, s0, w0), s1, w1)` into
// `bit_slice(x, s0 + s1, w1)`.
// * **Hoisting above `Concat` (when `NarrowingEnabled(opt_level)` is
// true, at `opt_level >= 2`)**: Rewrites `bit_slice(concat(...))` as a
// `concat` of only the overlapping operands (slicing boundary operands
// as needed).
// * **Pushing into Single-Use Bitwise and Low-Bit Arithmetic Operations
// (when `NarrowingEnabled(opt_level)` is true)**: If a `bit_slice` is
// the sole user of a bitwise operation, or extracts the low bits
// (`start == 0`) of a single-use `add`, `sub`, or `neg`, pushes the
// `bit_slice` into the operands so the operation runs at the narrower
// width.
// * **Hoisting above `SignExt` (when `NarrowingEnabled(opt_level)` is
// true)**: Simplifies `bit_slice(sign_ext(x))` to a direct slice of `x`
// (if within `x`), or for a single-use `sign_ext`, to a `sign_ext` of a
// slice of `x`'s top bits or sign bit.
// * **Narrowing Shifts, `Decode`, and Selects**: When all users of an
// operation are `bit_slice`s contained within a dominating `bit_slice`,
// hoists the slice above `shll` (when `start == 0`), `shrl`/`shra`
// (when slicing the MSBs), `decode` (when `start == 0`), or
// `sel`/`priority_sel`/`one_hot_sel` (when
// `NarrowingEnabled(opt_level)` is true), and rewrites all sibling
// slice users to slice from the narrowed operation.
class BitSliceSimplificationPass : public OptimizationFunctionBasePass {
public:
static constexpr std::string_view kName = "bitslice_simp";
Expand Down
93 changes: 78 additions & 15 deletions xls/passes/conditional_specialization_pass.h
Original file line number Diff line number Diff line change
Expand Up @@ -31,30 +31,93 @@ namespace xls {
//
// Note: What follows was generated by the Gemini LLM. Not human verified.
//
// For example, consider the following IR:
// The `ConditionalSpecializationPass` propagates contextual value constraints
// (`ConditionSet`, storing up to 64 `Condition{Node*, PartialInformation}`
// entries combining ternary bit vectors and `IntervalSet` ranges) backward
// through the IR graph in reverse topological order and uses those assumptions
// to specialize operands and state reads.
//
// ```
// fn f(a: bits[1], b: bits[31], z: bits[32]) -> bits[32] {
// concat: bits[32] = concat(a, b)
// ret sel.2: bits[32] = sel(a, cases=[z, concat])
// }
// ```
// **How it Works**:
//
// 1. **No-Op `next_value` Removal (`EliminateNoopNext`)**:
// When `options.eliminate_noop_next` is true, any `next_value` operation
// whose value is a `state_read` of the exact same `StateElement` is
// replaced with `()` and removed before analysis begins.
//
// 2. **Query Engine Configuration (`use_bdd`)**:
// The pass uses a `UnionQueryEngine` containing a `StatelessQueryEngine`
// and, when `use_bdd` is enabled (`cond_spec(Bdd)` / `cond_spec(true)`),
// the shared `BddQueryEngine` for stronger Boolean implication analysis.
//
// 3. **Seeding and Propagating Conditions (`ConditionMap`,
// `ImpliedConditionCache`)**:
// * **Edge Conditions**: Contextual assumptions are seeded on specific
// operand edges:
// * `sel`: Along `case[i]`, assumes `selector == i`.
// * `one_hot_sel`: Along `case[i]`, assumes bit `i` of `selector` is
// `1`.
// * `priority_sel`: Along `case[i]`, assumes bit `i` of `selector` is
// `1` and bits `0..i-1` are `0`; along `default`, assumes
// `selector == 0`.
// * `array_update`: Along the `update_value` edge, assumes each
// non-literal index is in bounds `[0, array_size)`.
// * Conditional `send` and `next_value`: Along the `data` / `value`
// edge, assumes `predicate == 1`.
// * `and`, `nand`, `or`, `nor`: When analyzing one operand edge,
// assumes all other operands are not equal to the absorbing value
// (`0` for `and`/`nand`, all-ones for `or`/`nor`).
// * **Implied Conditions**: Each seeded `Condition` is expanded via
// `ImpliedConditionCache` by lifting known bits and ranges backward
// through `not`, `and`, `or`, `nand`, `nor`, `eq`, and `ne`.
// * **Intersection Across Users**: For a node without implicit uses
// (excluding `invoke`, side-effecting ops other than `state_read`, and
// nodes used as a `state_read` predicate), its node `ConditionSet` is
// the intersection (`MeetWith`) of the edge condition sets across all
// of its users. For a `state_read`, its conditions are further
// intersected with the intersection of conditions across the
// `next_value` nodes for that state element.
//
// In the `sel` operation, the selector is `a`. When considering `case[1]` (the
// `concat` operation), we know that `a` must have the value `1`. Therefore, the
// `concat(a, b)` can be simplified to `concat(1, b)`. The pass will transform
// the `sel` to:
// 4. **Specializing Nodes and Operands**:
// * **Predicating Unconditional `state_read`s**: When
// `options.optimize_for_best_case_throughput` is enabled, if an
// unconditional `state_read` has a non-empty `ConditionSet` (meaning it
// is only needed when those conditions hold), the pass synthesizes a
// matching predicate (`CheckMatch`) from non-dependent conditions and
// attaches it via `SetPredicate`.
// * **Folding Implied Constant Operands**: Using a query engine
// specialized with the edge's `ConditionSet` (`SpecializeGiven`), if an
// operand's value is uniquely implied (`ImpliedNodeValue`), the operand
// is replaced with a `literal` (or the entire `and`/`nand`/`or`/`nor`
// node is replaced with a constant if the implied operand value is
// absorbing).
// * **Bypassing Ancestor Selects and Bitwise Operations**: If an operand
// is a `sel`, `priority_sel`, `one_hot_sel`, `and`, `or`, or `xor`, the
// pass walks up the operand chain as long as the edge conditions imply
// which branch of a select is active or imply that all but one operand
// of a bitwise op equal the identity element (`~0` for `and`, `0` for
// `or`/`xor`), rewiring the user directly to the active branch or
// non-identity input.
//
// Example:
//
// ```
// sel.2: bits[32] = sel(a, cases=[z, concat(literal(1), b)])
// fn f(a: bits[1], b: bits[31], z: bits[32]) -> bits[32] {
// concat.1: bits[32] = concat(a, b)
// ret sel.2: bits[32] = sel(a, cases=[z, concat.1])
// }
// ```
//
// Along the `case[1]` edge of `sel.2`, `a` is known to be `1`. If `concat.1`
// has no other users, the condition `a == 1` propagates to `concat.1` and
// specializes its first operand to a literal `1`:
//
// This optimization applies to `sel`, `priority_sel`, and `one_hot_sel`. It can
// also use Binary Decision Diagrams (BDDs) for more powerful analysis of the
// conditions.
// ```
// fn f(a: bits[1], b: bits[31], z: bits[32]) -> bits[32] {
// lit_1: bits[1] = literal(value=1)
// concat.1: bits[32] = concat(lit_1, b)
// ret sel.2: bits[32] = sel(a, cases=[z, concat.1])
// }
// ```
class ConditionalSpecializationPass : public OptimizationFunctionBasePass {
public:
static constexpr std::string_view kName = "cond_spec";
Expand Down
Loading
Loading
0