On optimal extraction of combinational logic and don't care sets from hardware description languages

The authors describe efficient polynomial algorithms for the extraction of topologically minimal multilevel Boolean equations and don't care conditions from the C-based hardware description language CHDL, which has control constructs switch, if-then-else, and go-to. They show that significant savings in CPU cost, area cost, and robustness may be obtained by applying these algorithms as a preprocessing step before using higher cost minimization tools such as BOLD or misII. The approach is based on a control-flow-graph construct with embedded set-use-graph information. The algorithms parse a CHDL description into a directed, nonseries parallel control flow graph. In cases where the graph is also acyclic, graph search and decomposition algorithms are used to derive a Boolean network representing the implied combinational logic. The derived equations are topologically irredundant in the sense that the topological identities are associated with the fork, and join nodes of the control flow graph are accounted for in the code generation. Without this feature, multilevel logic optimizers would have to flatten the control expressions down to primary inputs to discover these identities. >