Module lutmap 

Mapping logic onto K-input LUTs for depth, the way an FPGA’s synthesis sees how deep a circuit is.

An Xag holds the logic as two-input AND and XOR nodes over inputs, each edge plain or complemented, built with structural hashing and constant folding. map rebuilds it with every wide associative gate balanced for LUTs, then covers it with LUTs of at most k inputs:

• a supergate is a maximal tree of AND nodes joined by plain edges, or of XOR nodes, whose inner nodes feed nothing else and lie in one group (an instance of the design). It is rebuilt from its leaves k at a time, the earliest-arriving first, so an AND or a parity of n inputs is ⌈log_k n⌉ LUT levels deep, where the balanced binary tree a netlist hands over allows no better than ⌈log₂ n / ⌊log₂ k⌋⌉;
• every node keeps its best CUTS cuts of at most k leaves, ranked by arrival and then size (priority cuts: Mishchenko, Cho, Chatterjee & Brayton, Combinational and sequential mapping with priority cuts, 2007), and its level is its best cut’s arrival, one more than its latest leaf’s;
• the cover takes each required node’s best cut as a LUT, from the outputs back.

Structs

Lut

A LUT of the cover: its root node and its leaves, nodes of the balanced network.

Mapping

A network mapped onto LUTs.

Xag

An AND-XOR graph: node 0 is the constant, and every node’s fanins come before it.

Enums

Gate

A node of an Xag.

Constants

CUTS

How many cuts each node keeps.

FALSE

MAX_K

The largest LUT map maps to.

TRUE

Functions

complemented

function

The truth table of root over leaves (at most six): bit i of the table is the root’s value when leaf j holds bit j of i. Every path from the root down must end at a leaf, as a cut’s do.

map

Map xag onto LUTs of at most k inputs (2 ≤ k ≤ MAX_K), its supergates confined to groups (one entry a node), covering the nodes outputs read.

node

Type Aliases

Lit

A node and whether the edge to it is complemented: node << 1 | complemented.