egraphs-good / eggcc

MIT License
42 stars 8 forks source link

[Tree unique] Simplify loops to not have inputs #248

Closed oflatt closed 8 months ago

oflatt commented 8 months ago

It turns out that loop inputs are unnecessary, and we can just use Let. So this rule removes inputs from loops. For the first iteration, the argument in the loop refer to the argument outside the loop.

For example, the following loop:

(Loop (Id 1)
  (Add (Num 1) (Num 2))
   some_loop_body)

Can be expressed as

(Let (Id 2)
  (Add (Num 1) (Num 2))
    (Loop (Id 1) some_loop_body))

In general, the following rule holds:

(rule ((Loop inputs outputs))
      ((let new-id (i64-fresh!))
       (union (Loop inputs outputs)
              (NewLet new-id inputs (Loop (Arg new-id) outputs)))))
oflatt commented 8 months ago

Converting this to a draft- I think we should consider it in the future but not implement it right now.

oflatt commented 8 months ago

Closing, I think it's more natural for loops to have inputs like other operators