Skip to content

Support for weight-dependent rewrite rules with dynamic cost calculation #359

@xxzh12

Description

@xxzh12

I am working on combinational logic optimization using the egg framework and need to implement rewrite rules where newly generated gates inherit weights computed from the weights of input gates that were matched during rewriting. The optimization objective is to minimize the total weight sum, meaning gates of the same type may have different weights depending on their derivation history.

Use Case Example:
For a rewrite rule INV(AND(x y)) -> NAND(x,y), if the matched INV gate has weight 5 and the AND gate has weight 10, the resulting NAND gate should have weight (5+10)/2 = 7.5. However, other NAND gates in the circuit may have different weights based on their own derivation paths.
Current Approach and Challenge:
I am considering using analysis to maintain weight information for each enode. However, I cannot determine how to access all matched gates (enodes) during rule application to retrieve their weights. Currently, I can only access the root matched enode (matched_id corresponding to the AND gate in the example), but I also need access to the INV gate's weight.
Question:
What would be the recommended approach to:
Access all matched enodes in a pattern during rule application?
Retrieve their associated weights from the analysis?
Compute and assign weights to newly created enodes based on the matched pattern?

Any guidance on extending the pattern matching mechanism or alternative approaches would be greatly appreciated.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions