ai-free / backend /wasm /Wasm /SimAlu.lean
SNAPKITTYWEST's picture
October 2026 main drop: mirror from GitHub
f5deffb verified
Raw History Blame Contribute Delete
9.76 kB
import Wasm.Guard
/-!
# Wasm.SimAlu
Simulation of the binary operations: the generic `sim_binop` (operand guard, two loads, the
operation, a store into the second slot, pop one) and its instantiations.
-/
namespace WordDialect
namespace Wasm
section Sim
variable {c : Cfg} {s : State 64} {w : WState} {fs : Funcs}
theorem run_finish {u : WState} (nxt : Nat) :
Run fs [i32c nxt] u (.normal { u with stack := .i32 (ofN nxt) :: u.stack }) :=
run_of_execL (by simp [WI.isCtl, i32c]) (by simp [execL, stepI, i32c, ofN])
theorem ctl_binBody {op : List WI} (hctl : ∀ i ∈ op, i.isCtl = false) :
∀ i ∈ binBody op, i.isCtl = false := by
intro i hi
simp only [binBody, ldS, spAdd, List.mem_append, List.mem_cons, List.mem_nil_iff, or_false] at hi
rcases hi with ((((hi | hi | hi) | hi | hi) | hi) | hi) | hi | hi | hi | hi
all_goals first | exact hctl i ‹_› | (subst_vars; rfl)
/-- Core of every instruction shaped `uf 2; <body>; next`: the body (given as an execution fact)
overwrites the second slot with `y` and pops one. -/
theorem sim_bin_core (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {a b : W} {d : List W} {pre : List WI}
(hpre : Run fs pre w (.normal w))
(hd : s.dstack = b :: a :: d) {B : List WI} {y : W} (hctlB : ∀ i ∈ B, i.isCtl = false)
(hB : ∀ m', w.mem.write64 (c.dEnd - 8 * s.dstack.length + 8) y = some m' →
execL B w = some { w with mem := m', globals := setG w.globals spG (.i32 (ofN (c.dEnd - 8 * s.dstack.length + 8))) })
(nxt : Nat) :
∃ w', Run fs (pre ++ (B ++ [i32c nxt])) w (.normal w') ∧
Rel0 c { s with dstack := y :: d } w' ∧ w'.stack = [.i32 (ofN nxt)] := by
have hlen : s.dstack.length = d.length + 2 := by simp [hd]
have hk : 2 ≤ s.dstack.length := by omega
have hcap := hs.capD
obtain ⟨m', hm'⟩ : ∃ m', w.mem.write64 (c.dEnd - 8 * s.dstack.length + 8) y = some m' :=
write64_some (by rw [hs.size]; have := hg.dEnd_le; omega)
have hbR := run_of_execL (fs := fs) hctlB (hB m' hm')
have hrel1 := wr_stack hg hs (j := 1) (by omega) (v := y) (m' := m') (by simpa using hm')
have hrel2 := adj_sp hg hrel1 (n := 1) (by simp [hd])
have e3 : ({ { s with dstack := s.dstack.set 1 y } with dstack := ({ s with dstack := s.dstack.set 1 y } : State 64).dstack.drop 1 } : State 64) = { s with dstack := y :: d } := by
simp [hd]
rw [e3] at hrel2
have e2 : c.dEnd - 8 * s.dstack.length + 8 = c.dEnd - 8 * (s.dstack.length - 1) := by omega
rw [e2] at hbR
refine ⟨_, run_append _ hpre (run_append _ hbR (run_finish nxt)), ?_, ?_⟩
· refine Rel0.congr (hrel2.setStack []) rfl ?_ ?_ ?_
· simp [setG, spG, List.length_set]
· simp [setG, spG, rpG]
· simp [setG, spG, apG]
· simp [hst]
theorem sim_binop (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {a b : W} {d : List W} {pre : List WI}
(hpre : Run fs pre w (.normal w))
(hd : s.dstack = b :: a :: d) {op : List WI} (hctl : ∀ i ∈ op, i.isCtl = false) {y : W}
(hop : ∀ (u : WState) (r : List Val), u.stack = .i64 b :: .i64 a :: r →
execL op u = some { u with stack := .i64 y :: r }) (nxt : Nat) :
∃ w', Run fs (pre ++ (binBody op ++ [i32c nxt])) w (.normal w') ∧
Rel0 c { s with dstack := y :: d } w' ∧ w'.stack = [.i32 (ofN nxt)] := by
have hlen : s.dstack.length = d.length + 2 := by simp [hd]
have hX := sp_lt hg hs
have hr1 : w.mem.read64 (c.dEnd - 8 * s.dstack.length + 8) = some a := by
have := hs.stack 1 a (by simp [hd]); simpa using this
have hr0 : w.mem.read64 (c.dEnd - 8 * s.dstack.length) = some b := by
have := hs.stack 0 b (by simp [hd]); simpa using this
refine sim_bin_core hg hs hst hpre hd (ctl_binBody hctl) ?_ nxt
intro m' hm'
have hsp8 : ofN (c.dEnd - 8 * s.dstack.length) + ofN 8 = ofN (c.dEnd - 8 * s.dstack.length + 8) :=
ofN_add _ _
have hpre : execL ([.globalGet spG] ++ ldS 8 ++ ldS 0) w = some { w with stack := .i64 b :: .i64 a :: .i32 (ofN (c.dEnd - 8 * s.dstack.length)) :: w.stack } := by
simp [ldS, execL, stepI, hs.sp, ofN_toNat hX, hr0, hr1]
have hop' := hop { w with stack := .i64 b :: .i64 a :: .i32 (ofN (c.dEnd - 8 * s.dstack.length)) :: w.stack } (.i32 (ofN (c.dEnd - 8 * s.dstack.length)) :: w.stack) rfl
have hstore : execL [.i64store 8] { w with stack := .i64 y :: .i32 (ofN (c.dEnd - 8 * s.dstack.length)) :: w.stack } = some { w with mem := m' } := by
simp [execL, stepI, ofN_toNat hX, hm']
have hadd : execL (spAdd 8) { w with mem := m' } = some { w with mem := m', globals := setG w.globals spG (.i32 (ofN (c.dEnd - 8 * s.dstack.length + 8))) } := by
have hsp8' : ofN (c.dEnd - 8 * s.dstack.length) + 8#32 = ofN (c.dEnd - 8 * s.dstack.length + 8) := hsp8
simp [spAdd, execL, stepI, bin32, hs.sp, i32c]
unfold setG
rw [hsp8']
simp only [binBody, execL_append, hpre, Option.bind_some, hop', hstore, hadd]
theorem uf2_pass (hg : Geom c) (hs : Rel0 c s w) {b a : W} {d : List W} (hd : s.dstack = b :: a :: d) :
Run fs (uf c.layout 2) w (.normal w) :=
uf_pass hg hs (k := 2) (by omega) (by simp [hd])
/-- Conclusion shared by every instruction simulation. -/
abbrev Sim1 (c : Cfg) (fs : Funcs) (body : List WI) (s' : State 64) (w : WState) (nxt : Nat) : Prop :=
∃ w', Run fs body w (.normal w') ∧ Rel0 c s' w' ∧ w'.stack = [.i32 (ofN nxt)]
macro "hop_tac" : tactic =>
`(tactic| (intro u r h; simp [execL, stepI, bin64, cmp64, bool32, Word.rotl, Word.rotr, Word.ofBool, WordDialect.Cond.eval, cmpOp, h]))
theorem sim_add (n k : Nat) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {a b : W} {d : List W}
(hd : s.dstack = b :: a :: d) :
Sim1 c fs (lowerInstr c.layout n k .add) { s with dstack := (a + b) :: d } w (k + 1) := by
have := sim_binop (fs := fs) hg hs hst (uf2_pass hg hs hd) hd (op := [.i64add]) (by simp [WI.isCtl]) (y := a + b) (by hop_tac) (k + 1)
simpa [lowerInstr, binOp, List.append_assoc] using this
theorem sim_sub (n k : Nat) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {a b : W} {d : List W}
(hd : s.dstack = b :: a :: d) :
Sim1 c fs (lowerInstr c.layout n k .sub) { s with dstack := (a - b) :: d } w (k + 1) := by
have := sim_binop (fs := fs) hg hs hst (uf2_pass hg hs hd) hd (op := [.i64sub]) (by simp [WI.isCtl]) (y := a - b) (by hop_tac) (k + 1)
simpa [lowerInstr, binOp, List.append_assoc] using this
theorem sim_mul (n k : Nat) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {a b : W} {d : List W}
(hd : s.dstack = b :: a :: d) :
Sim1 c fs (lowerInstr c.layout n k .mul) { s with dstack := (a * b) :: d } w (k + 1) := by
have := sim_binop (fs := fs) hg hs hst (uf2_pass hg hs hd) hd (op := [.i64mul]) (by simp [WI.isCtl]) (y := a * b) (by hop_tac) (k + 1)
simpa [lowerInstr, binOp, List.append_assoc] using this
theorem sim_and (n k : Nat) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {a b : W} {d : List W}
(hd : s.dstack = b :: a :: d) :
Sim1 c fs (lowerInstr c.layout n k .and) { s with dstack := (a &&& b) :: d } w (k + 1) := by
have := sim_binop (fs := fs) hg hs hst (uf2_pass hg hs hd) hd (op := [.i64and]) (by simp [WI.isCtl]) (y := a &&& b) (by hop_tac) (k + 1)
simpa [lowerInstr, binOp, List.append_assoc] using this
theorem sim_or (n k : Nat) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {a b : W} {d : List W}
(hd : s.dstack = b :: a :: d) :
Sim1 c fs (lowerInstr c.layout n k .or) { s with dstack := (a ||| b) :: d } w (k + 1) := by
have := sim_binop (fs := fs) hg hs hst (uf2_pass hg hs hd) hd (op := [.i64or]) (by simp [WI.isCtl]) (y := a ||| b) (by hop_tac) (k + 1)
simpa [lowerInstr, binOp, List.append_assoc] using this
theorem sim_xor (n k : Nat) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {a b : W} {d : List W}
(hd : s.dstack = b :: a :: d) :
Sim1 c fs (lowerInstr c.layout n k .xor) { s with dstack := (a ^^^ b) :: d } w (k + 1) := by
have := sim_binop (fs := fs) hg hs hst (uf2_pass hg hs hd) hd (op := [.i64xor]) (by simp [WI.isCtl]) (y := a ^^^ b) (by hop_tac) (k + 1)
simpa [lowerInstr, binOp, List.append_assoc] using this
theorem sim_rotl (n k : Nat) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {a b : W} {d : List W}
(hd : s.dstack = b :: a :: d) :
Sim1 c fs (lowerInstr c.layout n k .rotl) { s with dstack := Word.rotl a b :: d } w (k + 1) := by
have := sim_binop (fs := fs) hg hs hst (uf2_pass hg hs hd) hd (op := [.i64rotl]) (by simp [WI.isCtl]) (y := Word.rotl a b) (by hop_tac) (k + 1)
simpa [lowerInstr, binOp, List.append_assoc] using this
theorem sim_rotr (n k : Nat) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {a b : W} {d : List W}
(hd : s.dstack = b :: a :: d) :
Sim1 c fs (lowerInstr c.layout n k .rotr) { s with dstack := Word.rotr a b :: d } w (k + 1) := by
have := sim_binop (fs := fs) hg hs hst (uf2_pass hg hs hd) hd (op := [.i64rotr]) (by simp [WI.isCtl]) (y := Word.rotr a b) (by hop_tac) (k + 1)
simpa [lowerInstr, binOp, List.append_assoc] using this
theorem ext_bool (v : Bool) : BitVec.setWidth 64 (bool32 v) = Word.ofBool v := by
cases v <;> simp [bool32, Word.ofBool]
theorem sim_cmp (n k : Nat) (cd : WordDialect.Cond) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = [])
{a b : W} {d : List W} (hd : s.dstack = b :: a :: d) :
Sim1 c fs (lowerInstr c.layout n k (.cmp cd)) { s with dstack := Word.ofBool (cd.eval a b) :: d } w (k + 1) := by
have := sim_binop (fs := fs) hg hs hst (uf2_pass hg hs hd) hd (op := [cmpOp cd, .i64extu]) (by cases cd <;> simp [cmpOp, WI.isCtl])
(y := Word.ofBool (cd.eval a b)) (by intro u r h; cases cd <;> simp [execL, stepI, bin64, cmp64, ext_bool, WordDialect.Cond.eval, cmpOp, h]) (k + 1)
simpa [lowerInstr, binOp, List.append_assoc] using this
end Sim
end Wasm
end WordDialect