Least-Cost Instruction Selection in DAGs is NP-Complete

Producing least-cost instruction selections for dags by finding pattern "matches" (or "covers" or "parses") is NP-complete. The trivial proof follows by reducing satisfiability to it. Build a dag for the formula you want satisfied. Then, have the following rules (all with unit cost):

True: VARIABLE False: VARIABLE False: not(True) True: not(False) True: or(True,True) True: or(True,False) True: or(False,True) False: or(False,False) True: and(True,True) False: and(True,False) False: and(False,True) False: and(False,False)

If you can derive a cover of the dag that reduces to True with a cost exactly equal to the number of nodes, then the formula is satisfiable. Otherwise it is not.

Unless you have a different model of optimality, this proves optimal DAG code generation is NP-complete. Note that it does not rely on the usual complication of (1) number of registers, or (2) asymmetrical instructions.