Fil-C on Nix

Filnix wiki

the formal campaign

rocq/spikes/ListSum.v

The program both logic spikes prove, shared by them: spikes/listsum.c, which builds a linked list of n nodes on the collected heap (__builtin_alloca, which Fil-C places there), then calls sum, which walks it and adds each node's value. Its checked module is listsum_term (ListSumCode.v, checked current by spikes/code.sh).

sum is gc.ir's list walk in checked form: per node a check of the value's 8 bytes, a lower half check for the next pointer, a raw pointer load through the aux, and a poll on the back edge. listsum adds an allocation per iteration, a pointer store and a direct call. This file holds only what both spikes need: the module, its globals, its two functions and their call frames (docs/logic.md).

From Stdlib Require Import String ZArith List Bool Lia
From Nanofil Require Import Term Syntax Values Memory Runtime Ops Semantics Run Transport
From Spike Require Import ListSumCode
Import ListNotations
Open Scope Z_scope

The checked module, decoded from the fixture listsum_term.

22Definition ls_module: module ≔
Somemd
⇒
md
None
⇒
[ ]

The fixture decodes to ls_module.

26Lemma ls_decodes
Explore proof 2 tactics

Initial goal

vm_compute

⊢
SomeIFuncfn_name ≔ TAtom"sum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ P, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L3"; b_label ≔ TAtom"L3"; b_phis ≔ PhiTAtom"pr.2" L TAtom"L4", TmpTAtom"v13"; TAtom"start", Const0; PhiTAtom"pr.1" P TAtom"L4", TmpTAtom"v15"; TAtom"start", TmpTAtom"v0"; b_insts ≔ LetTAtom"v7" L Ptoi TmpTAtom"pr.1"; LetTAtom"v8" W CmpNe L TmpTAtom"v7"; Const0; b_jump ≔ JBranchTmpTAtom"v8" ToTAtom"L4" ToTAtom"L5"; b_label ≔ TAtom"L4"; b_phis ≔ [ ]; b_insts ≔ FlightTAtom"v11" Add FAddressTmpTAtom"pr.1"; FValueConst8 LowerOfTmpTAtom"pr.1"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v11"; LetTAtom"v12" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v13" L Add TmpTAtom"pr.2"; TmpTAtom"v12"; LetTAtom"chk1" A HalfCheckLower 0 8 Read 8 TmpTAtom"chk0"; TmpTAtom"pr.1"; LetTAtom"v15" P RawLoadPointer0 AuxRead; LowerResolve; AddressRead TmpTAtom"chk1"; b_jump ≔ JGotoPollTAtom"L3"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JRetTmpTAtom"pr.2"; IFuncfn_name ≔ TAtom"listsum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ W, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L4"; b_label ≔ TAtom"L4"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L5", TmpTAtom"v21"; TAtom"start", Const0; PhiTAtom"pr.1" P TAtom"L5", TmpTAtom"v12"; TAtom"start", Const0; b_insts ≔ LetTAtom"v10" W CmpSlt W TmpTAtom"pr.2"; TmpTAtom"v0"; b_jump ≔ JBranchTmpTAtom"v10" ToTAtom"L5" ToTAtom"L7"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v12" P Alloc16 Const16; LetTAtom"chk0" A Check0 8 Write 8 TmpTAtom"v12"; RawStorePointer0 TmpTAtom"pr.1" TmpTAtom"chk0" AuxEnsure; LowerBarrier; RootedReload; LowerWrite; AddressWrite; FlightTAtom"v16" Add FAddressTmpTAtom"v12"; FValueConst8 LowerOfTmpTAtom"v12"; LetTAtom"v18" L ExtSw TmpTAtom"pr.2"; LetTAtom"chk1" A HalfCheckUpper 0 8 Write 1 TmpTAtom"chk0"; TmpTAtom"v16"; RawStoreWl 0 TmpTAtom"v18" TmpTAtom"chk1"; LetTAtom"v21" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L4"; b_label ≔ TAtom"L7"; b_phis ≔ [ ]; b_insts ≔ CallCResultTAtom"v23" L GlobalTAtom"sum" ArgP TmpTAtom"pr.1"; b_jump ≔ JRetTmpTAtom"v23" = SomeIFuncfn_name ≔ TAtom"sum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ P, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L3"; b_label ≔ TAtom"L3"; b_phis ≔ PhiTAtom"pr.2" L TAtom"L4", TmpTAtom"v13"; TAtom"start", Const0; PhiTAtom"pr.1" P TAtom"L4", TmpTAtom"v15"; TAtom"start", TmpTAtom"v0"; b_insts ≔ LetTAtom"v7" L Ptoi TmpTAtom"pr.1"; LetTAtom"v8" W CmpNe L TmpTAtom"v7"; Const0; b_jump ≔ JBranchTmpTAtom"v8" ToTAtom"L4" ToTAtom"L5"; b_label ≔ TAtom"L4"; b_phis ≔ [ ]; b_insts ≔ FlightTAtom"v11" Add FAddressTmpTAtom"pr.1"; FValueConst8 LowerOfTmpTAtom"pr.1"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v11"; LetTAtom"v12" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v13" L Add TmpTAtom"pr.2"; TmpTAtom"v12"; LetTAtom"chk1" A HalfCheckLower 0 8 Read 8 TmpTAtom"chk0"; TmpTAtom"pr.1"; LetTAtom"v15" P RawLoadPointer0 AuxRead; LowerResolve; AddressRead TmpTAtom"chk1"; b_jump ≔ JGotoPollTAtom"L3"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JRetTmpTAtom"pr.2"; IFuncfn_name ≔ TAtom"listsum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ W, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L4"; b_label ≔ TAtom"L4"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L5", TmpTAtom"v21"; TAtom"start", Const0; PhiTAtom"pr.1" P TAtom"L5", TmpTAtom"v12"; TAtom"start", Const0; b_insts ≔ LetTAtom"v10" W CmpSlt W TmpTAtom"pr.2"; TmpTAtom"v0"; b_jump ≔ JBranchTmpTAtom"v10" ToTAtom"L5" ToTAtom"L7"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v12" P Alloc16 Const16; LetTAtom"chk0" A Check0 8 Write 8 TmpTAtom"v12"; RawStorePointer0 TmpTAtom"pr.1" TmpTAtom"chk0" AuxEnsure; LowerBarrier; RootedReload; LowerWrite; AddressWrite; FlightTAtom"v16" Add FAddressTmpTAtom"v12"; FValueConst8 LowerOfTmpTAtom"v12"; LetTAtom"v18" L ExtSw TmpTAtom"pr.2"; LetTAtom"chk1" A HalfCheckUpper 0 8 Write 1 TmpTAtom"chk0"; TmpTAtom"v16"; RawStoreWl 0 TmpTAtom"v18" TmpTAtom"chk1"; LetTAtom"v21" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L4"; b_label ≔ TAtom"L7"; b_phis ≔ [ ]; b_insts ≔ CallCResultTAtom"v23" L GlobalTAtom"sum" ArgP TmpTAtom"pr.1"; b_jump ≔ JRetTmpTAtom"v23"

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
vm_compute
reflexivity

The module's globals: its two functions, sum and listsum.

30Definition ls_globals: listname × ptr ≔
Someg, _
⇒
g
None
⇒
[ ]

The module's initial memory, which holds no object.

34Definition ls_mem: mem ≔
Some_, m
⇒
m
None
⇒

Laying out the module succeeds, with ls_globals and ls_mem.

Explore proof 3 tactics

Initial goal

assert H : option_mapλ_ ⇒ tt initial_memoryls_module = Somett by vm_compute ; reflexivity

H :
option_mapλ_ : listname × ptr × mem ⇒ tt initial_memoryls_module = Somett

unfold ls_globals , ls_mem

H :
option_mapλ_ : listname × ptr × mem ⇒ tt initial_memoryls_module = Somett
⊢
=
Some
Someg, _
⇒
g
None
⇒
[ ]
Some_, m
⇒
m
None
⇒

destruct initial_memoryls_module as g m | ; inversion H ; reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
assert H : option_mapλ_ ⇒ tt initial_memoryls_module = Somett by vm_compute ; reflexivity
destruct initial_memoryls_module as g m | ; inversion H ; reflexivity

The genv of the module with the free x.

47Definition ls_gefree : word → mem → optionresunit × mem : genv ≔

The function named n in the module, as find_fn finds it.

51Definition ls_fnn : string : func ≔
match find_fnls_geλ_ _ ⇒ None TAtomn with
SomeDefinedf
⇒
f
_
⇒
mkFuncTAtomn TAtom"export" RClassL [ ] [ ]

sum is a function of the core subset in the module.

58Lemma ls_find_sum
∀ free
find_fnls_gefree TAtom"sum" = SomeDefinedls_fn"sum"
Explore proof 3 tactics

Initial goal

⊢
∀free : word → mem → optionresunit × mem, find_fnls_gefree TAtom"sum" = SomeDefinedls_fn"sum"

intros free

free :
word → mem → optionresunit × mem
⊢
find_fnls_gefree TAtom"sum" = SomeDefinedls_fn"sum"

vm_compute

free :
word → mem → optionresunit × mem
⊢
SomeDefinedfn_name ≔ TAtom"sum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ P, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L3"; b_label ≔ TAtom"L3"; b_phis ≔ PhiTAtom"pr.2" L TAtom"L4", TmpTAtom"v13"; TAtom"start", Const0; PhiTAtom"pr.1" P TAtom"L4", TmpTAtom"v15"; TAtom"start", TmpTAtom"v0"; b_insts ≔ LetTAtom"v7" L Ptoi TmpTAtom"pr.1"; LetTAtom"v8" W CmpNe L TmpTAtom"v7"; Const0; b_jump ≔ JBranchTmpTAtom"v8" ToTAtom"L4" ToTAtom"L5"; b_label ≔ TAtom"L4"; b_phis ≔ [ ]; b_insts ≔ FlightTAtom"v11" Add FAddressTmpTAtom"pr.1"; FValueConst8 LowerOfTmpTAtom"pr.1"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v11"; LetTAtom"v12" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v13" L Add TmpTAtom"pr.2"; TmpTAtom"v12"; LetTAtom"chk1" A HalfCheckLower 0 8 Read 8 TmpTAtom"chk0"; TmpTAtom"pr.1"; LetTAtom"v15" P RawLoadPointer0 AuxRead; LowerResolve; AddressRead TmpTAtom"chk1"; b_jump ≔ JGotoPollTAtom"L3"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JRetTmpTAtom"pr.2" = SomeDefinedfn_name ≔ TAtom"sum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ P, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L3"; b_label ≔ TAtom"L3"; b_phis ≔ PhiTAtom"pr.2" L TAtom"L4", TmpTAtom"v13"; TAtom"start", Const0; PhiTAtom"pr.1" P TAtom"L4", TmpTAtom"v15"; TAtom"start", TmpTAtom"v0"; b_insts ≔ LetTAtom"v7" L Ptoi TmpTAtom"pr.1"; LetTAtom"v8" W CmpNe L TmpTAtom"v7"; Const0; b_jump ≔ JBranchTmpTAtom"v8" ToTAtom"L4" ToTAtom"L5"; b_label ≔ TAtom"L4"; b_phis ≔ [ ]; b_insts ≔ FlightTAtom"v11" Add FAddressTmpTAtom"pr.1"; FValueConst8 LowerOfTmpTAtom"pr.1"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v11"; LetTAtom"v12" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v13" L Add TmpTAtom"pr.2"; TmpTAtom"v12"; LetTAtom"chk1" A HalfCheckLower 0 8 Read 8 TmpTAtom"chk0"; TmpTAtom"pr.1"; LetTAtom"v15" P RawLoadPointer0 AuxRead; LowerResolve; AddressRead TmpTAtom"chk1"; b_jump ≔ JGotoPollTAtom"L3"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JRetTmpTAtom"pr.2"

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros free
vm_compute
reflexivity

listsum is a function of the core subset in the module.

62Lemma ls_find_listsum
∀ free
find_fnls_gefree TAtom"listsum" = SomeDefinedls_fn"listsum"
Explore proof 3 tactics

Initial goal

⊢
∀free : word → mem → optionresunit × mem, find_fnls_gefree TAtom"listsum" = SomeDefinedls_fn"listsum"

intros free

free :
word → mem → optionresunit × mem
⊢
find_fnls_gefree TAtom"listsum" = SomeDefinedls_fn"listsum"

vm_compute

free :
word → mem → optionresunit × mem
⊢
SomeDefinedfn_name ≔ TAtom"listsum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ W, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L4"; b_label ≔ TAtom"L4"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L5", TmpTAtom"v21"; TAtom"start", Const0; PhiTAtom"pr.1" P TAtom"L5", TmpTAtom"v12"; TAtom"start", Const0; b_insts ≔ LetTAtom"v10" W CmpSlt W TmpTAtom"pr.2"; TmpTAtom"v0"; b_jump ≔ JBranchTmpTAtom"v10" ToTAtom"L5" ToTAtom"L7"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v12" P Alloc16 Const16; LetTAtom"chk0" A Check0 8 Write 8 TmpTAtom"v12"; RawStorePointer0 TmpTAtom"pr.1" TmpTAtom"chk0" AuxEnsure; LowerBarrier; RootedReload; LowerWrite; AddressWrite; FlightTAtom"v16" Add FAddressTmpTAtom"v12"; FValueConst8 LowerOfTmpTAtom"v12"; LetTAtom"v18" L ExtSw TmpTAtom"pr.2"; LetTAtom"chk1" A HalfCheckUpper 0 8 Write 1 TmpTAtom"chk0"; TmpTAtom"v16"; RawStoreWl 0 TmpTAtom"v18" TmpTAtom"chk1"; LetTAtom"v21" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L4"; b_label ≔ TAtom"L7"; b_phis ≔ [ ]; b_insts ≔ CallCResultTAtom"v23" L GlobalTAtom"sum" ArgP TmpTAtom"pr.1"; b_jump ≔ JRetTmpTAtom"v23" = SomeDefinedfn_name ≔ TAtom"listsum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ W, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L4"; b_label ≔ TAtom"L4"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L5", TmpTAtom"v21"; TAtom"start", Const0; PhiTAtom"pr.1" P TAtom"L5", TmpTAtom"v12"; TAtom"start", Const0; b_insts ≔ LetTAtom"v10" W CmpSlt W TmpTAtom"pr.2"; TmpTAtom"v0"; b_jump ≔ JBranchTmpTAtom"v10" ToTAtom"L5" ToTAtom"L7"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v12" P Alloc16 Const16; LetTAtom"chk0" A Check0 8 Write 8 TmpTAtom"v12"; RawStorePointer0 TmpTAtom"pr.1" TmpTAtom"chk0" AuxEnsure; LowerBarrier; RootedReload; LowerWrite; AddressWrite; FlightTAtom"v16" Add FAddressTmpTAtom"v12"; FValueConst8 LowerOfTmpTAtom"v12"; LetTAtom"v18" L ExtSw TmpTAtom"pr.2"; LetTAtom"chk1" A HalfCheckUpper 0 8 Write 1 TmpTAtom"chk0"; TmpTAtom"v16"; RawStoreWl 0 TmpTAtom"v18" TmpTAtom"chk1"; LetTAtom"v21" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L4"; b_label ≔ TAtom"L7"; b_phis ≔ [ ]; b_insts ≔ CallCResultTAtom"v23" L GlobalTAtom"sum" ArgP TmpTAtom"pr.1"; b_jump ≔ JRetTmpTAtom"v23"

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros free
vm_compute
reflexivity

Block l of the function f after its first j instructions.

67Definition ls_atf : func l : string j : nat : point ≔
Someb
⇒
None
⇒

Any arguments whose first word is x start sum at its entry with x as its parameter v0.

75Lemma sum_call_frame
∀ x rest
call_framels_fn"sum" x :: rest = SomemkFramels_fn"sum" TAtom"v0", x [ ] None EnterTAtom"start" None
Explore proof 1 tactics

Initial goal

⊢
∀x : word rest : listword, call_framels_fn"sum" x :: rest = Somefr_fn ≔ ls_fn"sum"; fr_env ≔ TAtom"v0", x; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
reflexivity

Any arguments whose first word is the integer n start listsum at its entry with n as its parameter v0.

82Lemma listsum_call_frame
∀ n rest
call_framels_fn"listsum" WIntn :: rest = SomemkFramels_fn"listsum" TAtom"v0", WIntn [ ] None EnterTAtom"start" None
Explore proof 1 tactics

Initial goal

⊢
∀n : Z rest : listword, call_framels_fn"listsum" WIntn :: rest = Somefr_fn ≔ ls_fn"listsum"; fr_env ≔ TAtom"v0", WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
reflexivity