Fil-C on Nix

Filnix wiki

the formal campaign

rocq/backend/Abi.v

Fil-C ABI lowering (filc_abi.pl's lower_function/4 and lower_thunks/2): the plan of a checked function, before any register or frame offset is chosen. Its frame names payload slots, ordered roots and aliases; a call, a getter or a return becomes a list of ABI actions in the place of the instruction it lowers; and the function's public object says how a generic caller reaches it.

Fast words split a pointer into its address and its lower; generic cells are one eightbyte a value. registers or buffer(N) is the return protocol. Nothing here knows a native location.

The first version shares the frame's pools and gives every temporary and phi a slot of its own kind, as the Prolog compiler does without −O; it has no setjmp sites.

From Stdlib Require Import String ZArith List Bool
From Nanofil Require Import Term Syntax Validate Maps Cfg Transport
From Backend Require Import Order Plan Fuse Liveness FrameSlots
Import ListNotations
Open Scope Z_scope
Open Scope list_scope

Signatures

As class_digit/2: the digit of a word of the class k in a signature: 0 for an integer, 7 for a pointer, 1 and 2 for the floats. Other classes have none.

30Definition class_digitk : class : optionZ ≔
match k with
W | L
⇒
Some0
⇒
Some7
⇒
Some1
⇒
Some2
_
⇒
None

As bijective_value/2: the digits ds, the first the least, as a number in bijective base 11.

41Fixpoint bijective_valueds : listZ : Z ≔
match ds with
[ ]
⇒
0
d :: ds′
⇒
d + 1 + 11 × bijective_valueds′

As never_signature/1: the signature no function object has, for more than 16 argument words. A call with it always goes generic.

50Definition never_signature: Z ≔
18446744073709551615

As ret_kinds/2: the classes a function of the return type r returns.

54Definition ret_kindsr : ret_type : optionlistclass ≔
match r with
⇒
Some[ ]
⇒
Someks
⇒
match k with
W | L | P | Single | Double
⇒
Somek
_
⇒
None

As word_codes/3: the bijective values of the return digits and of the argument digits of a function returning r on parameters of the classes ks.

67Definition word_codesr : ret_type ks : listclass : optionZ × Z ≔
let* rks ≔ ret_kindsr in
let* rds ≔ all_someclass_digit rks in

As signature/3: Fil-C's fast-call signature number, 1 + R + 133 * A, or the never_signature for more than 16 arguments. It names private bodies.

76Definition signaturer : ret_type ks : listclass : optionZ ≔
let* c ≔ word_codesr ks in
Some
Zlengthks ≤? 16
→
1 + fstc + 133 × sndc

As return_protocol/2: how a function of the return type r returns: through a buffer if more than two integer words come back, a pointer being two. Float words return in registers of their own.

84Definition return_protocolr : ret_type : optionprotocol ≔
let* ks ≔ ret_kindsr in
let* ns ≔
λ k  ⇒
match k with
⇒
Some2
W | L
⇒
Some1
⇒
Some0
_
⇒
None
ks
in
let n ≔ fold_leftZ.add ns 0 in
Some
n >? 2
→

As result_ret/2: the return type a call reading the result r expects.

97Definition result_retr : call_result : ret_type ≔
match r with
⇒
RTuplemapsnd rs

Symbols

What a call needs of a function the module defines: its linkage, its own signature if it has one, and whether it is variadic.

109Record fentry: Type ≔ mkFentry
fe_linkage
 : term
fe_sig
 : optionZ
fe_variadic
 : bool

As module_symbols/2: a module's functions and data by name, the first of a name, and the names it declares weak.

117Record symbols: Type ≔ mkSymbols
sy_funcs
sy_data
sy_weak
 : nmapunit

The fentry of a function outside the core subset, read off its term t.

125Definition outside_entryt : term : optionfentry ≔
let* sg ≔ term_sigt in
134Definition module_symbolsmd : module : symbols ≔
fold_left
λ sy it  ⇒
let func ≔
λ n fe  ⇒
in
match it with
⇒
match outside_entryt with
Somefe
⇒
funcn fe
None
⇒
sy
⇒
sy
IDatan lk _ _
⇒
IAlias_ _ _
⇒
sy
md

Whether the term t is the atom a.

156Definition is_atoma : string t : term : bool ≔
match t with
⇒
String.eqba b
_
⇒
false

As weak_defined/2: the module defines the name n with linkage weak or ro(weak), so another object's definition may replace it.

162Definition weak_definedsy : symbols n : name : bool ≔
match nm_findn sy_funcssy with
Somefe
⇒
None
⇒
false
||
match nm_findn sy_datasy with
SomeLWeak
⇒
true
SomeLRol
⇒
is_atom"weak" l
_
⇒
false

As direct_target/4: what a direct call of f at the call-site signature sig invokes: the private body, under the callee's own signature, if the module defines f, not variadic and not weak; else the weak thunk of f and sig.

177Definition direct_targetsy : symbols f : name sig : sigref : optioncall_target ≔
match nm_findf sy_funcssy with
Somefe
⇒
negbfe_variadicfe && negbweak_definedsy f
→
let* s ≔ fe_sigfe in
else
SomeTEntryf sig
None
⇒
SomeTEntryf sig

As getter_target/3: the getter of the symbol s: this module's if it defines s and not weakly, a weak one, which may give null, if it declares s weak, else an external one.

189Definition getter_targetsy : symbols s : name : getter ≔

Frames

The standard order of two N − K pairs, a temporary and its class.

199Definition temp_comparea b : name × class : Datatypes.comparison ≔
match term_comparefsta fstb with

The destination of a phi and its class.

206Definition phi_destp : phi : name × class ≔
match p with
Phid k _
⇒
d, k

As storage_keys/3: storage(Pool, I) for i from 0 up to n.

209Definition storage_keysp : pool n : Z : listkey ≔
mapλi ⇒ KStoragep Z.of_nati seq0 Z.to_natn

As body_params/3: the parameters of the private body of f: a variadic function's has the hidden pointer to the promoted packet last.

215Definition body_paramsf : func : listclass × name ≔

As frame/6: the frame of a body with the parameters ps and the fused blocks bs, returning by ret; with it, the payload keys a setjmp would snapshot and the number of named locals.

The plain keys are the slots of the pools, a shadow for each phi, thread, aux, the return buffer if there is one, and the named locals. The roots are the lowers of the pointer slots and of the pointer phis' shadows, then the stack auxes of the locals, the last root group, as the collector's origin says.

227Definition frame_ofps : listclass × name bs : listfblock ret : protocol : optionframe × listkey × Z ≔
let phis ≔ flat_mapλb ⇒ mapphi_dest fb_phisb bs in
let temps ≔ sorttemp_compare mapλp ⇒ sndp, fstp ps ++ flat_mapλb ⇒ mapphi_dest fb_phisb ++ flat_mapfinst_defs fb_instsb bs in
let shadows ≔ sorttemp_compare phis in
let* sl ≔ temp_slotsps bs temps in
let pointers ≔ storage_keysPoolPointer sl_pointerssl in
let aliases ≔
flat_map
λ a  ⇒
match snda with
in
let locals ≔
flat_map
λ b  ⇒
flat_map
λ i  ⇒
match i with
⇒
x, size
_
⇒
[ ]
bs
in
let plain ≔
++
pointers
++
++
mapλs ⇒ KShadowfsts shadows
++
++
match ret with
++
mapλl ⇒ KLocalfstl sndl locals
in
let roots ≔
mapKLower pointers
++
flat_map
λ s  ⇒
match snds with
_
⇒
[ ]
shadows
++
mapλl ⇒ KStackAuxfstl locals
in
let payload ≔ mapKShadow nsortmapfst shadows ++ mapKTmp nsortmapfst temps in
SomemkFrameplain roots aliases, payload, Zlengthlocals

Words and cells

As fast_params/2: the words a body receives for the parameters ps: a pointer is its address and its lower, both at l.

268Definition fast_paramsps : listclass × name : listword ≔
flat_map
λ p  ⇒
match fstp with
ps

As fast_args/2: the words of a fast call's arguments.

275Definition fast_argsargs : listarg : listword ≔
flat_map
λ a  ⇒
match a with
args

As payload_class/2: the class of a value's data word in a generic packet.

283Definition payload_classk : class : class ≔
match k with
⇒
_
⇒
k

The elements of xs, each with its index from i.

286Fixpoint indexedX : Type i : Z xs : listX : listZ × X ≔
match xs with
[ ]
⇒
[ ]
x :: xs′
⇒
i, x :: indexedi + 1 xs′

As generic_args/2: the cells of a generic call's arguments, one a value, a pointer's with its lower.

294Definition generic_argsargs : listarg : listcell ≔
map
λ ia  ⇒
match sndia with
Argk v
⇒
match k with
⇒
_
⇒
None
indexed0 args

As generic_params/2: the words a generic packet holds for parameters of the classes ks: a pointer's data and aux, another value's data.

303Definition generic_paramsks : listclass : listword ≔
flat_map
λ ik  ⇒
match sndik with
⇒
WfL SrcDatafstik; WfL SrcAuxfstik
k
⇒
Wfk SrcDatafstik

As result_tos/2: the results a call reads.

310Definition result_tosr : call_result : listname × class ≔
match r with
⇒
[ ]
⇒
d, k
⇒
rs

Whether k is a float class a register returns: s or d.

318Definition returned_floatk : class : bool ≔
match k with
⇒
true
_
⇒
false

As fast_result/2: the return protocol and the channels of a fast call's result r. One float has a channel of its own; a tuple with a float names each slot's class; anything else is integer words, a pointer two.

325Definition fast_resultr : call_result : optionprotocol × channels ≔
let* ret ≔ return_protocolresult_retr in
let split ≔
λ d : name × class  ⇒
match sndd with
⇒
KTmpfstd; KLowerKTmpfstd
_
⇒
KTmpfstd
in
Some
ret
match r with
⇒
else
ChSlotssplitd, k
⇒
existsbλd ⇒ returned_floatsndd rs
→
flat_map
λ d  ⇒
match sndd with
⇒
L, KTmpfstd; L, KLowerKTmpfstd
k
⇒
k, KTmpfstd
rs
else
ChSlotsflat_mapsplit rs

As generic_result/2: the bytes a generic call's result r needs and the cells it comes back in.

347Definition generic_resultr : call_result : Z × listcell ≔
let tos ≔ result_tosr in
8 × Zlengthtos
map
λ id  ⇒
match sndid with
d, k
⇒
match k with
_
⇒
None
indexed0 tos

Instructions

As call_signature/3: the signature of a call reading r on the arguments args.

359Definition call_signaturer : call_result args : listarg : optionZ ≔

As call_symbol_signature/4: the signature in the name of the weak thunk a direct call goes through. Every call of more than 16 words has the never signature, so its thunk is named by the whole word list.

366Definition call_symbol_signaturer : call_result args : listarg : optionsigref ≔
let* s ≔ call_signaturer args in
→
let* c ≔ word_codesresult_retr maparg_class args in
SomeSigNeverfstc sndc
else

As small_copy/5: the inline filter of a call of f that is a memcpy or memmove of a constant 1 to 16 bytes, if the module defines neither: the emitter may test for the common case in front of the unchanged call.

376Definition small_copysy : symbols f : name r : call_result args : listarg : optionaction ≔
match args with
⇒
is_atom"memcpy" f || is_atom"memmove" f && 1 ≤? n && n ≤? 16
&&
match r with
⇒
true
_
⇒
false
&&
&&
→
SomeACopyFilterd s n r
else
None
_
⇒
None

As lower_inst/4: the fused instruction i lowered. A direct call invokes its target's fast entry; a call of a checked function pointer dispatches on the signature, fast or generic; a symbol's address comes from its getter; va_args and va_arg read the promoted packet; a local's declaration initializes it. Every other instruction passes through.

395Definition lower_instsy : symbols i : finst : optionpinst ≔
match i with
⇒
let* sig ≔ call_symbol_signaturer args in
let* target ≔ direct_targetsy f sig in
let* res ≔ fast_resultr in
let call ≔ AOrigin; AReserveResultfstres; AInvoketarget fstres fast_argsargs; AResultfstres sndres; AReleaseResultfstres in
Some
match small_copysy f r args with
Somefilter
⇒
filter :: call ++ ACopyJoin
None
⇒
call
FCallr p args
⇒
let* sig ≔ call_signaturer args in
let* res ≔ fast_resultr in
let g ≔ generic_resultr in
SomePAbiAOrigin; AReserveResultfstres; ADispatchp sig fstres fast_argsargs sndres 8 × Zlengthargs generic_argsargs fstg sndg; AReleaseResultfstres
⇒
let* size ≔
match k with
⇒
Some16
⇒
Some4
L | P | Double
⇒
Some8
_
⇒
None
in
SomePAbiAOrigin; AConsumeVak p size d
_
⇒
SomePInsti

As lower_jump/4: the jump j of a function returning r by the protocol ret. A return's values are in place before the roots are popped, and no safepoint comes between.

432Definition lower_jumpr : ret_type ret : protocol j : jump : pjump ≔
match j with
⇒
⇒
match r, ret with
⇒
let ws ≔ fast_argsmapλkv ⇒ Argfstkv sndkv combineks vs in
Zlengthks =? Zlengthvs && Zlengthws =? n
→
else
_, _
⇒
_
⇒
450Definition lower_blocksy : symbols r : ret_type ret : protocol b : fblock : optionpblock ≔

Public objects

As adapter_return/2: how an adapter turns the fast result of a function returning r into a generic packet. The void result is one zero word.

The words zeroed are the aux of each cell that holds no pointer, whatever else comes back: tuple([l, s]) zeroes aux(0) and aux(1), so no stale aux word of the caller's reaches a result read as a pointer.

465Definition adapter_returnr : ret_type : optionadapter_result ≔
let* ret ≔ return_protocolr in
let* ks ≔ ret_kindsr in
let channel ≔
match ks with
[ ]
⇒
_
⇒
existsbreturned_float ks
→
in
let copies ≔
map
λ w  ⇒
match w with
Wf_ s
⇒
s
in
let zeros ≔
match ks with
[ ]
⇒
_
⇒
flat_map
λ ik  ⇒
→
[ ]
else
SrcAuxfstik
in
SomemkAdapterResultret channel 8 × Z.max1 Zlengthks copies zeros

As public_object/3: the public object of the function f: a fast entry under its signature and a generic adapter, or, for a variadic function, a generic entry that promotes the incoming packet.

486Definition public_objectf : func : optionobject ≔
let ks ≔ mapfst fn_paramsf in
let need ≔ 8 × Zlengthks in
let* res ≔ adapter_returnfn_retf in

The plan of a function

As lower_function/4 of the function f after fused_blocks/5: its plan, with sy the symbols of its module. Nothing if the function is outside what the first version lowers.

500Definition lower_functionsy : symbols f : func : optionplan ≔
let* sig ≔ signaturefn_retf mapfst fn_paramsf in
let* ret ≔ return_protocolfn_retf in
let body ≔ body_paramsf in
let* fr ≔ frame_ofbody bs ret in
let* blocks ≔ all_somelower_blocksy fn_retf ret bs in
let* obj ≔ public_objectf in
SomemkPlanfn_namef fn_linkagef fn_retf sig fstfstfr ret fast_paramsbody sndfstfr blocks obj sndfr

Thunks

A direct call that goes through a weak thunk: the callee, the signature in the thunk's name, and the call's return type and argument classes.

516Record thunk_call: Type ≔ mkThunkCall
tc_name
 : name
tc_sig
 : sigref
tc_ret
tc_classes
 : listclass

A signature in a symbol as its term: the number, or never(R-A).

525Definition sigref_terms : sigref : term ≔
match s with
⇒
TApp"never" TApp"-" TIntr; TInta

As t(F, Sig, Ret, Ks), the term lower_thunks/2 sorts thunk calls by.

533Definition thunk_call_termc : thunk_call : term ≔

The thunk call of a direct call of f returning r on arguments of the classes ks, if its target is a thunk and it has a signature.

538Definition thunk_call_ofsy : symbols f : name r : ret_type ks : listclass : listthunk_call ≔
let implemented ≔
match nm_findf sy_funcssy with
Somefe
⇒
negbfe_variadicfe && negbweak_definedsy f
None
⇒
false
in
implemented
→
[ ]
else
match signaturer ks with
Somes
⇒
→
match word_codesr ks with
Somec
⇒
mkThunkCallf SigNeverfstc sndc r ks
None
⇒
[ ]
None
⇒
[ ]

The return type the term t of a call's result expects: void, result(_, K) or tuple([result(_, K), ...]).

558Definition term_result_rett : term : optionret_type ≔
let class_of ≔
λ r  ⇒
match r with
TApp"result" _; k
⇒
_
⇒
None
in
match t with
TAtom"void"
⇒
SomeRVoid
TApp"tuple" TListrs
⇒
let* ks ≔ all_someclass_of rs in
SomeRTupleks
_
⇒
let* k ≔ class_oft in
SomeRClassk

The thunk calls among the instruction terms of a function outside the core subset, whose term is t: its direct calls, call(Res, global(F), Args), as lower_thunks/2 reads them.

569Definition outside_thunk_callssy : symbols t : term : listthunk_call ≔
match t with
TApp"func" _; _; _; _; TListbs
⇒
flat_map
λ b  ⇒
match b with
TApp"block" _; _; TListis; _
⇒
flat_map
λ i  ⇒
match i with
TApp"call" res; TApp"global" f; TListargs
⇒
match term_result_retres, all_someλa ⇒ match a with TApp"arg" k; _ ⇒ dclassk | _ ⇒ None end args with
Somer, Someks
⇒
thunk_call_ofsy f r ks
_, _
⇒
[ ]
_
⇒
[ ]
is
_
⇒
[ ]
bs
_
⇒
[ ]

The thunk calls of a module: those of every direct call in it.

596Definition module_thunk_callssy : symbols md : module : listthunk_call ≔
flat_map
λ it  ⇒
match it with
⇒
flat_map
λ b  ⇒
flat_map
λ i  ⇒
match i with
_
⇒
[ ]
_
⇒
[ ]
md

As one_per_symbol/2: of the sorted calls cs, the first of each symbol and signature.

613Fixpoint one_per_symbolcs : listterm × thunk_call : listthunk_call ≔
match cs with
[ ]
⇒
[ ]
_, c :: cs′
⇒
c
::
match cs′ with

As thunk_cells/4: the generic cells of a thunk for parameters of the classes ks, the value i from the fast word w the thunk saved; a pointer takes two words.

630Fixpoint thunk_cellsks : listclass i w : Z : listcell ≔
match ks with
[ ]
⇒
[ ]
P :: ks′
⇒
Celli L CellSavedw SomeCellSavedw + 1 :: thunk_cellsks′ i + 1 w + 2
k :: ks′
⇒
Celli k CellSavedw None :: thunk_cellsks′ i + 1 w + 1

As lower_thunk/3: the plan of the weak thunk for the call c. It is weak if the callee is declared weak, since its getter may be null; local if this module defines the callee with local linkage, so that the thunk never merges with another object's; else strong.

642Definition lower_thunksy : symbols c : thunk_call : optionthunk ≔
let f ≔ tc_namec in
let local_data ≔
match nm_findf sy_datasy with
SomeLLocal
⇒
true
SomeLRol | SomeLTlsl
⇒
is_atom"local" l
_
⇒
false
in
let ref ≔
match nm_findf sy_funcssy with
Somefe
⇒
None
⇒
false
→
local_data
→
in
let ks ≔ tc_classesc in
let* res ≔ adapter_returntc_retc in
let* rks ≔ ret_kindstc_retc in
SomemkThunkf ref tc_sigc fast_paramsmapλik ⇒ sndik, TIntfstik indexed0 ks thunk_cellsks 0 0 8 × Zlengthks res 8 × Zlengthrks

As lower_thunks/2: the plans of the weak thunks the module md needs, one for each symbol and signature of a direct call to a function it does not implement, in the standard order of t(F, Sig, Ret, Ks).

667Definition lower_thunkssy : symbols md : module : optionlistthunk ≔
let calls ≔ mapλc ⇒ thunk_call_termc, c module_thunk_callssy md in