search

egraphs-good / eggcc

MIT License
42 stars 8 forks source link

Extend egglog to support richer cost functions #366

Open oflatt opened 7 months ago

oflatt commented 7 months ago

We need richer cost functions for extraction in eggcc. For example, assume nodes should not take the context into account for the cost. Loops should multiply the cost of children somehow.

This is a difficult change. Perhaps we can make something like this work?

(function DoWhile (Expr Expr) Expr :cost (+ c1 (* c2 5)))

We could also have an analysis that figures out how many times a loop iterates and use it in the cost function:

(function LoopIterationCount (Expr) i64)
(function DoWhile (Expr Expr) Expr :cost (+ c1 (* c2 (LoopIterationCount (DoWhile c1 c2)))))
oflatt commented 7 months ago

Alternatively, yihong has suggested we use egglog rule-based extraction, and we don't need to change egglog's implementation