egraphs-good / eggcc

MIT License
42 stars 8 forks source link

Add `BeforeWrite` semantics #400

Closed rtjoa closed 5 months ago

rtjoa commented 6 months ago

Adds semantics for BeforeWrite, which allows us to delete writes that are shadowed by future writes. image Example:

; As there are no writes in the second argument of outer-write,
; the assumption can go to both children. Otherwise it would only go
; to the second argument.
(Write
  (Snd (Write addr x) addr)
  y)
~~>
(Write
  (BeforeWrite addr
    (Snd (Write addr x) addr))
  (BeforeWrite addr
    y))

; As there are no writes in the second argument of (Snd (Write addr x)) addr,
; the first assumption can go to both children.
(BeforeWrite addr
  (Snd (Write addr x) addr))
~~>
(Snd
  (BeforeWrite addr (Write addr x))
  (BeforeWrite addr addr))

; We detected a shadowed write (as both write to the same address)!
(BeforeWrite addr (Write addr x))
~~>
(Empty)
oflatt commented 5 months ago

Closing for now