Download backend/wasm/Wasm/SimCtl.lean from Snapkitty/ai-free: direct link, hf CLI and curl.
- Browser
- Download file 7.52 kB
-
https://huggingface.co/Snapkitty/ai-free/resolve/main/backend/wasm/Wasm/SimCtl.lean
- Command line
-
hf download hf://Snapkitty/ai-free/backend/wasm/Wasm/SimCtl.lean
-
curl -L -o SimCtl.lean https://huggingface.co/Snapkitty/ai-free/resolve/main/backend/wasm/Wasm/SimCtl.lean
7.52 kB
| import Wasm.SimMem | |
| /-! | |
| # Wasm.SimCtl | |
| Control flow: `jmp`, `branch`, `call`, `ret` (and its `returnUnderflow` exit 5), `halt`, and the | |
| bad-pc stub (exit 4). Each leaves the next IR index on the operand stack, which the dispatch loop | |
| stores into the `pc` global. | |
| -/ | |
| namespace WordDialect | |
| namespace Wasm | |
| section Sim | |
| variable {c : Cfg} {s : State 64} {w : WState} {fs : Funcs} | |
| theorem sim_jmp (n k t : Nat) (hs : Rel0 c s w) (hst : w.stack = []) : | |
| Sim1 c fs (lowerInstr c.layout n k (.jmp t)) s w (min t n) := | |
| ⟨_, run_finish (min t n), hs.setStack _, by simp [hst]⟩ | |
| theorem sim_branch (n k t : Nat) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {cv : W} | |
| {d : List W} (hd : s.dstack = cv :: d) : | |
| Sim1 c fs (lowerInstr c.layout n k (.branch t)) { s with dstack := d } w | |
| (if Word.isTrue cv then min t n else k + 1) := by | |
| have hlen : s.dstack.length = d.length + 1 := by simp [hd] | |
| have hX := sp_lt hg hs | |
| have hcap := hs.capD | |
| have hr0 : w.mem.read64 (c.dEnd - 8 * s.dstack.length) = some cv := by | |
| have := hs.stack 0 cv (by simp [hd]); simpa using this | |
| have hsp8 : ofN (c.dEnd - 8 * s.dstack.length) + 8#32 = ofN (c.dEnd - 8 * s.dstack.length + 8) := | |
| ofN_add _ _ | |
| have e2 : c.dEnd - 8 * s.dstack.length + 8 = c.dEnd - 8 * (s.dstack.length - 1) := by omega | |
| have el : execL ([i32c (min t n), i32c (k + 1)] ++ ldS 0 ++ [.i64const 0#64, .i64ne, .select] ++ spAdd 8) w = | |
| some { w with stack := [.i32 (ofN (if Word.isTrue cv then min t n else k + 1))], | |
| globals := setG w.globals spG (.i32 (ofN (c.dEnd - 8 * (s.dstack.length - 1)))) } := by | |
| rw [← e2] | |
| by_cases hc : cv = 0#64 | |
| · simp [ldS, spAdd, execL, stepI, cmp64, bin32, hs.sp, ofN_toNat hX, hr0, bool32, hc, i32c, hsp8, | |
| Word.isTrue, hst] | |
| exact ⟨rfl, rfl⟩ | |
| · simp [ldS, spAdd, execL, stepI, cmp64, bin32, hs.sp, ofN_toNat hX, hr0, bool32, hc, i32c, hsp8, | |
| Word.isTrue, hst] | |
| exact ⟨rfl, rfl⟩ | |
| have rl := run_of_execL (fs := fs) (by simp [ldS, spAdd, WI.isCtl, i32c]) el | |
| have hrel := adj_sp hg hs (n := 1) (by simp [hd]) | |
| have e3 : ({ s with dstack := s.dstack.drop 1 } : State 64) = { s with dstack := d } := by simp [hd] | |
| rw [e3] at hrel | |
| refine ⟨_, ?_, hrel.setStack _, rfl⟩ | |
| have := run_append _ (uf1_pass (fs := fs) hg hs hd) rl | |
| simpa [lowerInstr, List.append_assoc] using this | |
| theorem sim_call (n k t : Nat) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) | |
| (hfit : c.rBase + 8 * (s.rstack.length + 1) ≤ c.rEnd) : | |
| Sim1 c fs (lowerInstr c.layout n k (.call t)) { s with rstack := (k + 1) :: s.rstack } w (min t n) := by | |
| have hcap := hs.capR | |
| have hrE := hg.rEnd_le | |
| have hsz := hg.msize_lt | |
| have hlt : c.rEnd - 8 * (s.rstack.length + 1) < 2 ^ 32 := by omega | |
| have hsub : ofN (c.rEnd - 8 * s.rstack.length) - 8#32 = ofN (c.rEnd - 8 * (s.rstack.length + 1)) := by | |
| have : (8#32 : W32) = ofN 8 := rfl | |
| rw [this, ofN_sub (by omega)] | |
| congr 1 | |
| obtain ⟨m', hm'⟩ : ∃ m', w.mem.write64 (c.rEnd - 8 * (s.rstack.length + 1)) (BitVec.ofNat 64 (k + 1)) = some m' := | |
| write64_some (by rw [hs.size]; omega) | |
| have el : execL [.globalGet rpG, i32c 8, .i32sub, .globalSet rpG, .globalGet rpG, i64c (k + 1), .i64store 0, | |
| i32c (min t n)] w = | |
| some { w with mem := m', stack := [.i32 (ofN (min t n))], | |
| globals := setG w.globals rpG (.i32 (ofN (c.rEnd - 8 * (s.rstack.length + 1)))) } := by | |
| simp [execL, stepI, bin32, hs.rp, i32c, i64c, hsub, setG, ofN_toNat hlt, hm', hst] | |
| exact ⟨rfl, rfl⟩ | |
| have rl := run_of_execL (fs := fs) (by simp [WI.isCtl, i32c, i64c]) el | |
| refine ⟨_, ?_, (push_rs hg hs hfit hm').setStack _, rfl⟩ | |
| simpa [lowerInstr] using run_append _ (ovfR_pass (fs := fs) hg hs hfit) rl | |
| theorem sim_call_ovf (n k t : Nat) (hg : Geom c) (hs : Rel0 c s w) | |
| (h : ¬ c.rBase + 8 * (s.rstack.length + 1) ≤ c.rEnd) : | |
| Run fs (lowerInstr c.layout n k (.call t)) w (.exit 6) := by | |
| have := run_append_abrupt (fs := fs) _ (ovfR_trap hg hs h) | |
| (b := [.globalGet rpG, i32c 8, .i32sub, .globalSet rpG, .globalGet rpG, i64c (k + 1), .i64store 0, | |
| i32c (min t n)]) trivial | |
| simpa [lowerInstr] using this | |
| theorem ret_split (L : Layout) : lowerInstr L n k .ret = | |
| [.globalGet rpG, i32c L.rEnd, .i32eq] ++ [.ite [.exitTrap 5]] ++ | |
| [.globalGet rpG, .i64load 0, .i32wrap, .globalGet rpG, i32c 8, .i32add, .globalSet rpG] := rfl | |
| theorem sim_ret (n k : Nat) (hg : Geom c) (hs : Rel0 c s w) (hst : w.stack = []) {a : Nat} | |
| {rs : List Nat} (hr : s.rstack = a :: rs) (ha : a < 2 ^ 32) : | |
| Sim1 c fs (lowerInstr c.layout n k .ret) { s with rstack := rs } w a := by | |
| have hcap := hs.capR | |
| rw [hr] at hcap | |
| simp only [List.length_cons] at hcap | |
| have hrE := hg.rEnd_le | |
| have hsz := hg.msize_lt | |
| have hX : c.rEnd - 8 * (rs.length + 1) < 2 ^ 32 := by omega | |
| have hE : c.rEnd < 2 ^ 32 := by omega | |
| have hrp : w.globals rpG = .i32 (ofN (c.rEnd - 8 * (rs.length + 1))) := by | |
| have := hs.rp; rw [hr] at this; simpa using this | |
| have hne : ofN (c.rEnd - 8 * (rs.length + 1)) ≠ ofN c.rEnd := by | |
| intro h; have := ofN_inj hX hE h; omega | |
| have hr0 : w.mem.read64 (c.rEnd - 8 * (rs.length + 1)) = some (BitVec.ofNat 64 a) := by | |
| have := hs.rs 0 a (by simp [hr]); rw [hr] at this; simpa using this | |
| have e1 : execL [.globalGet rpG, i32c c.layout.rEnd, .i32eq] w = some { w with stack := [.i32 0#32] } := by | |
| simp [execL, stepI, hrp, i32c, Cfg.layout, bool32, hst] | |
| exact hne | |
| have r1 := run_of_execL (fs := fs) (by simp [WI.isCtl, i32c]) e1 | |
| have r2 := run_ite_false (fs := fs) (thn := [.exitTrap 5]) (w := { w with stack := [.i32 0#32] }) (r := []) rfl | |
| have hsp8 : ofN (c.rEnd - 8 * (rs.length + 1)) + 8#32 = ofN (c.rEnd - 8 * rs.length) := by | |
| rw [show (8#32 : W32) = ofN 8 from rfl, ofN_add]; congr 1; omega | |
| have hwrap : BitVec.setWidth 32 (BitVec.ofNat 64 a) = ofN a := by | |
| apply BitVec.eq_of_toNat_eq | |
| have : a < 2 ^ 64 := by omega | |
| simp [ofN, BitVec.toNat_setWidth, Nat.mod_eq_of_lt this] | |
| have e3 : execL [.globalGet rpG, .i64load 0, .i32wrap, .globalGet rpG, i32c 8, .i32add, .globalSet rpG] | |
| { { w with stack := [.i32 0#32] } with stack := [] } = | |
| some { w with stack := [.i32 (ofN a)], globals := setG w.globals rpG (.i32 (ofN (c.rEnd - 8 * rs.length))) } := by | |
| simp [execL, stepI, bin32, hrp, ofN_toNat hX, hr0, i32c, hsp8, hwrap] | |
| unfold setG; rfl | |
| have r3 := run_of_execL (fs := fs) (by simp [WI.isCtl, i32c]) e3 | |
| refine ⟨_, ?_, (pop_rs hs hr).setStack _, rfl⟩ | |
| rw [ret_split] | |
| exact run_append _ (run_append _ r1 r2) r3 | |
| theorem sim_ret_trap (n k : Nat) (hs : Rel0 c s w) (hst : w.stack = []) (hr : s.rstack = []) : | |
| Run fs (lowerInstr c.layout n k .ret) w (.exit 5) := by | |
| have hrp : w.globals rpG = .i32 (ofN c.rEnd) := by | |
| have := hs.rp; rw [hr] at this; simpa using this | |
| have e1 : execL [.globalGet rpG, i32c c.layout.rEnd, .i32eq] w = some { w with stack := [.i32 1#32] } := by | |
| simp [execL, stepI, hrp, i32c, Cfg.layout, bool32, hst, ofN] | |
| have r1 := run_of_execL (fs := fs) (by simp [WI.isCtl, i32c]) e1 | |
| have r2 := run_ite_exit (fs := fs) (w := { w with stack := [.i32 1#32] }) (r := []) (c := 1#32) (k := 5) | |
| rfl (by decide) | |
| rw [ret_split] | |
| exact run_append_abrupt _ (run_append _ r1 r2) trivial | |
| theorem sim_halt (n k : Nat) : Run fs (lowerInstr c.layout n k .halt) w (.halted w) := | |
| .consAbrupt .exitHalt trivial | |
| theorem sim_stub : Run fs [.exitTrap 4] w (.exit 4) := | |
| .consAbrupt .exitTrap trivial | |
| end Sim | |
| end Wasm | |
| end WordDialect | |