Fil-C on Nix

Filnix wiki

the formal campaign

rocq/backend/Fuse.v

Fusion, the first step of the Fil-C backend (filc_amd64.pl's fused_blocks/5): each check of the checked IR and the raw access after it, which reads the check's proof, become one instruction at one index, the access now at the checked pointer itself. A proof is then a register value and needs no frame slot. A later access under the same proof is reused, with no check; a function check fuses with its raw call.

The first version takes the checks the compiler emits without −O: check (a check_ahead is the check of its whole range), check_local and check_function. A function with a renewed, half or limit check, which only the optimizer's passes make, is refused, as is one the Prolog compiler throws on: an access without its check, or pointer arithmetic that is not a flight.

From Stdlib Require Import String ZArith List Bool
From Nanofil Require Import Term Syntax Validate Maps Cfg
From Backend Require Import Plan
Import ListNotations
Open Scope Z_scope

Before fusion

As without_locs/2 and ahead_as_check/2: the instructions is without their source positions, each check_ahead now the check of its whole range, whose early bytes are tested with the access's own.

28Definition prepared_instsis : listinst : listinst ≔
flat_map
λ i  ⇒
match i with
Loc_ _
⇒
[ ]
Letq A CheckAheadlo hi r al _ ps
⇒
Letq A Checklo hi r al ps
_
⇒
i
is

A block before fusion.

36Definition prepared_blockb : block : block ≔

Proofs that hold in every block

As temp_defs/3, its names: every definition of a temporary, the parameters ps, then each block's phis and instructions.

43Definition defined_namesps : listclass × name bs : listblock : listname ≔
mapsnd ps
++
flat_map
λ b  ⇒
map
λ p  ⇒
match p with
Phid _ _
⇒
d
++
flat_mapλi ⇒ mapfst inst_temp_defsi b_instsb
bs

The names ns counted: each maps to whether it occurs more than once.

50Definition countedns : listname : nmapbool ≔
fold_leftλm n ⇒ nm_addn nm_memn m m ns nm_empty

Whether the name n is defined more than once.

54Definition multiplem : nmapbool n : name : bool ≔
match nm_findn m with
Someb
⇒
b
None
⇒
false

As single_proofs/3: the proof q mapped to its checked pointer p for each heap check let(tmp(Q), a, check(...), [P]) where q has one definition in the function and p, if a temporary, has no more than one. Only these may be reused in another block: reloading p there gives the value that was checked.

62Definition single_proofsps : listclass × name bs : listblock : nmapvalue ≔
let multi ≔ counteddefined_namesps bs in
fold_left
λ m b  ⇒
fold_left
λ m i  ⇒
match i with
Letq A Check_ _ _ _ p :: _
⇒
multiplemulti q
→
m
else
match p with
⇒
multiplemulti n
→
m
else
nm_addq p m
_
⇒
nm_addq p m
_
⇒
m
m
bs

A block's proofs

The proofs of a block so far, as pr(ByQ, ByP): by_q maps each proof q to its checked pointer, and by_p each name n to the proofs once paired with tmp(N), so that a new definition of n drops its pairs without a scan of the others.

85Record proofs: Type ≔ mkProofs
by_q
by_p
 : nmaplistname
91Definition proofs_empty: proofs ≔

As proofs_add/3: pr with the proof q of the pointer p.

94Definition proofs_addq : name p : value pr : proofs : proofs ≔
match p with
⇒
q
::
match nm_findn by_ppr with
Someqs
⇒
qs
None
⇒
[ ]
_
⇒

As proofs_kill/3: pr once d is defined again: without d's own pair and without each pair whose pointer is tmp(D). Emission reloads the pointer from its slot, so its old proofs are of another value.

107Definition proofs_killd : name pr : proofs : proofs ≔
let by_q1 ≔ nm_removed by_qpr in
match nm_findd by_ppr with
Someqs
⇒
fold_left
λ m q  ⇒
match nm_findq m with
SomeTmpn
⇒
else
m
_
⇒
m
qs
by_q1
None
⇒
mkProofsby_q1 by_ppr

Accesses

Which protocols a fused pointer access may declare: a heap object's or a named local's.

123Inductive storage: Type ≔
|Heap
|Local

As proven_access/4 (heap) and proven_local_access/4 (local): the raw access i, which reads the proof q, as the access at the place p. A pointer access must declare a protocol of its storage: the heap's or the atomic helpers', or the local's.

129Definition proven_accessst : storage i : inst q : name p : place : optionaccess ≔
match i with
Letd k RawLoadt off Tmpq′
⇒
name_eqbq′ q
→
SomeALoadd k t off p
else
None
RawStorew off v Tmpq′
⇒
name_eqbq′ q
→
SomeAStorew off v p
else
None
_
⇒
None

As access_pointer/3, its offset: the access a is at its place plus this.

154Definition access_offseta : access : Z ≔
match a with
ALoad_ _ _ off _ | AStore_ off _ _ | ALoadPointer_ off _ _ | AStorePointeroff _ _ _
⇒
off

The proof and the offset of an access that may be reused: a non-pointer raw load or store, or a pointer load by the heap's load protocol.

163Definition reusablei : inst : optionname × Z ≔
match i with
Let_ _ RawLoad_ off Tmpq
⇒
Someq, off
RawStore_ off _ Tmpq
⇒
Someq, off
⇒
→
Someq, off
else
None
_
⇒
None

As unchecked_access/1 and implicit_flight/1, for the checked IR: an instruction that must not reach emission by itself: a raw access or call not fused with its check, a call of a pointer, or pointer arithmetic outside a flight.

176Definition not_emittedi : inst : bool ≔
match i with
Call_ Tmp_ _ | RawCall_ _ _ | RawStore_ _ _ _ | RawStorePointer_ _ _ _
⇒
true
Let_ _ RawLoad_ _ _ | Let_ _ RawLoadPointer_ _ _
⇒
true
Let_ P Add | Sub | Itop _
⇒
true
⇒
true
_
⇒
false

Whether access_check//2 can emit the check c: of the bytes from the pointer up to a positive size below 2^31, aligned to 1, 2, 4 or 8.

188Definition emitted_checkc : op : bool ≔
match c with
Check0 size _ al
⇒
0 <? size && size ≤? 2147483647 && al =? 1 || al =? 2 || al =? 4 || al =? 8
_
⇒
false

Fusing

As fused_inst/5: the instruction i fused with the one after it in rest, if it is a check, and whether that one was taken. Nothing if i is a check without its access, a check the first version does not emit, or an instruction that is not_emitted.

202Definition fused_insti : inst rest : listinst : optionfinst × bool ≔
match i with
Letq A CheckLocalx off _ _ _ as c [ ]
⇒
match rest with
next :: _
⇒
let* a ≔ proven_accessLocal next q AtLocalx off in
→
SomeFFusedc a, true
else
None
[ ]
⇒
None
Letq A c p
⇒
match rest with
next :: _
⇒
let* a ≔ proven_accessHeap next q AtValuep in
→
SomeFFusedc a, true
else
None
[ ]
⇒
None
Let_ A _ _
⇒
None
⇒
match rest with
RawCallres Tmpq′ args :: _
⇒
name_eqbq′ q
→
SomeFCallres p args, true
else
None
_
⇒
None
_
⇒
→
None
else
SomeFPlaini, false

One step of fused_insts/5: the instruction i under the block's proofs pr and the function's single proofs. An access whose proof is among them is reused, at the proof's pointer, if its offset fits 32 bits; anything else is fused_inst's.

232Definition fused_stepsingle : nmapvalue pr : proofs i : inst rest : listinst : optionfinst × bool ≔
let found ≔
match reusablei with
Someq, off
⇒
match nm_findq by_qpr with
Somep
⇒
Someq, off, p
None
⇒
match nm_findq single with
Somep
⇒
Someq, off, p
None
⇒
None
None
⇒
None
in
match found with
Someq, off, p
⇒
−2147483648 ≤? off && off ≤? 2147483647
→
let* a ≔ proven_accessHeap i q AtValuep in
SomeFReuseda, false
else
None
None
⇒

As fused_insts/5: the instructions is fused, in front of the reversed acc. Each instruction's definition first forgets the proofs it invalidates; a check then adds its own; and what the fused instruction defines, a load's destination perhaps, forgets again.

259Fixpoint fused_instssingle : nmapvalue is : listinst pr : proofs acc : listfinst : optionlistfinst ≔
match is with
[ ]
⇒
Somerev'acc
i :: rest
⇒
let pr0 ≔
match inst_def_firsti with
Somed
⇒
None
⇒
pr
in
let pr1 ≔
match i with
Letq A Check_ _ _ _ p
⇒
proofs_addq p pr0
_
⇒
pr0
in
let* r ≔ fused_stepsingle pr0 i rest in
let fi ≔ fstr in
let pr2 ≔ fold_leftλpr d ⇒ proofs_killfstd pr finst_defsfi pr1 in
match sndr, rest with
true, _ :: rest′
⇒
fused_instssingle rest′ pr2 fi :: acc
_, _
⇒
fused_instssingle rest pr2 fi :: acc

A block after fusion: its instructions are finsts.

282Record fblock: Type ≔ mkFBlock
fb_label
 : name
fb_phis
 : listphi
fb_insts
 : listfinst
fb_jump
 : jump

As fused_blocks/5: the blocks bs of a function with the parameters ps, fused. fused_blocks/5 also throws unless every cycle polls, which is the validator's to check here.

292Definition fused_blocksps : listclass × name bs : listblock : optionlistfblock ≔
let bs1 ≔ mapprepared_block bs in
let single ≔ single_proofsps bs1 in
λ b  ⇒
let* is ≔ fused_instssingle b_instsb proofs_empty [ ] in
bs1