Constant Propagation with Netlist Carpentry¶

Constant propagation is a pretty useful optimization technique where signals that are tied to fixed logic values (0 or 1) are substituted directly into the circuit. This enables the simplification of logic expressions. It also removes gates whose outputs become predetermined, reducing circuit area, power, and overall delay. Consider the following example structure:

flowchart LR
    In1([Input: 1])
    In2([Input: 0])
    Gate{{AND Gate}}
    SomeWire([SomeWire: 0])
    SubModule{{Some Submodule}}
    
    In1 --> Gate
    In2 --> Gate
    Gate --> SomeWire
    SomeWire --> SubModule

If the inputs of the AND Gate are tied to 0 and 1 respectively, it is obvious that the output will always be 0 as well. Accordingly, the AND Gate may be removed and the corresponding input of the downstream submodule instance can be tied to 0. This removes unnecessary instances and reduces circuit area and power consumption.

flowchart LR
    SomeWire((0))
    SubModule{{Some Submodule}}

    SomeWire --> SubModule

Execute the cell below to create a circuit with a module, with a similar structure as in the first graph.

In [1]:

from netlist_carpentry import Circuit, Module, Direction
from netlist_carpentry.utils.gate_lib_factory import and_gate

c = Circuit(name="c")
m = c.create_module(name="m")
submodule = Module(raw_path="Submodule")
submodule.create_port("IN", Direction.IN)

sub_inst = m.create_instance(submodule, "SubmoduleInst")
and_inst = and_gate(m, "and_inst", Y=sub_inst.ports["IN"])
and_inst.ports["A"].tie_signal(1)
and_inst.ports["B"].tie_signal(0)
dash_graph = m.show(interactive=True)
dash_graph.run()

from netlist_carpentry import Circuit, Module, Direction from netlist_carpentry.utils.gate_lib_factory import and_gate c = Circuit(name="c") m = c.create_module(name="m") submodule = Module(raw_path="Submodule") submodule.create_port("IN", Direction.IN) sub_inst = m.create_instance(submodule, "SubmoduleInst") and_inst = and_gate(m, "and_inst", Y=sub_inst.ports["IN"]) and_inst.ports["A"].tie_signal(1) and_inst.ports["B"].tie_signal(0) dash_graph = m.show(interactive=True) dash_graph.run()

Now to start the constant propagation algorithm, there are two approaches. The easiest is to execute Module.optimize, which runs a bunch of optimizations, with constant propagation being one of them. However, to only execute the constant propagation, the task can be imported directly from the corresponding module routines.opt.constant_folds, as shown in the cell below.

Info: The constant propagation is executed by the function opt_constant_propagation. However, there are other functions inside the constant_folds module. To execute all constant optimization tasks, use the function opt_constant. For simplicity, the function opt_constant_propagation is used here!

Warning: Currently, the constant propagation process is stopped whenever a submodule instance is encountered and an appropriate warning is displayed. In the future, stepping into submodule instances and continuing the propagation process might be supported.

In [ ]:

# Alternative: from netlist_carpentry.routines.opt import opt_constant
from netlist_carpentry.routines.opt.constant_folds import opt_constant_propagation

print(f"Module {m.name} now has these instances: {', '.join(inst for inst in m.instances)}")
print(f"Is Port IN of Instance {sub_inst.name} tied? {sub_inst.ports["IN"].is_tied}")
print(f"Port IN of Instance {sub_inst.name} has this driver: {sub_inst.ports["IN"].driver()}")


any_constants_propagated = opt_constant_propagation(m)
print(f"Any constants propagated? {any_constants_propagated}")
print(f"Module {m.name} now has these instances: {', '.join(inst for inst in m.instances)}")

print(f"Is Port IN of Instance {sub_inst.name} tied? {sub_inst.ports["IN"].is_tied}")
print(f"Port IN of Instance {sub_inst.name} now has this value: {sub_inst.ports["IN"].signal}")

# Alternative: from netlist_carpentry.routines.opt import opt_constant from netlist_carpentry.routines.opt.constant_folds import opt_constant_propagation print(f"Module {m.name} now has these instances: {', '.join(inst for inst in m.instances)}") print(f"Is Port IN of Instance {sub_inst.name} tied? {sub_inst.ports["IN"].is_tied}") print(f"Port IN of Instance {sub_inst.name} has this driver: {sub_inst.ports["IN"].driver()}") any_constants_propagated = opt_constant_propagation(m) print(f"Any constants propagated? {any_constants_propagated}") print(f"Module {m.name} now has these instances: {', '.join(inst for inst in m.instances)}") print(f"Is Port IN of Instance {sub_inst.name} tied? {sub_inst.ports["IN"].is_tied}") print(f"Port IN of Instance {sub_inst.name} now has this value: {sub_inst.ports["IN"].signal}")

Module m now has these instances: SubmoduleInst, and_inst
Is Port IN of Instance SubmoduleInst tied? False
Port IN of Instance SubmoduleInst has this driver: {0: PortSegment(m.and_inst.Y.0, Signal:x)}

  0%|          | 0/1 [00:00<?, ?it/s]

WARNING:   Unable to evaluate instance m.SubmoduleInst: Not implemented for INSTANCE objects by default! The problematic instance is m.SubmoduleInst!                                                   

Any constants propagated? True
Module m now has these instances: SubmoduleInst
Is Port IN of Instance SubmoduleInst tied? True
Port IN of Instance SubmoduleInst now has this value: 0

The constant propagation can also be somewhat seen as a special case of the "driverless optimization routine", but is different in its interpretation, as it reorganizes and optimizes completely valid logic (in contrast to driverless objects, which are most likely undesired). Furthermore, constant propagation checks for the behavior of the individual instances, before removing them. Accordingly, the downstream ports are tied to the value resulting from the behavioral evaluation, instead of letting them unconnected.