Fil-C on Nix

Filnix wiki

the formal campaign

rocq/backend/Layout.v

Where a function's plan lives below %rbp, and the names its code uses: filc_amd64.pl's layout/4, its function context, its labels and abi_symbol/3, with the short ways to write a line that the emission (Emit.v and the files it calls) is built from.

Emission is total: where the Prolog compiler would fail or reach a form this port does not have yet, the code holds a todo line, which is not an instruction. The driver emits no function that has one.

From Stdlib Require Import String ZArith List Bool
From Nanofil Require Import Term Syntax Maps
From Backend Require Import Text Asm Plan PlanTerm
Import ListNotations
Open Scope string_scope
Open Scope Z_scope
Open Scope list_scope

Lines

20Definition insop suffix : string os : listoperand : line ≔
Insop Somesuffix os
21Definition ins0op : string os : listoperand : line ≔
Insop None os
22Definition regr : string : operand ≔
23Definition immn : Z : operand ≔
24Definition memd : Z b : string : operand ≔
25Definition rips : string : operand ≔
26Definition syms : string : operand ≔
27Definition plts : string : operand ≔
28Definition gotpcrels : string : operand ≔
29Definition labels : string : line ≔
30Definition quad_syms : string : line ≔
31Definition quad_intn : Z : line ≔

The mnemonic of a todo line.

34Definition todo_op: string ≔
"todo"

A place in the code for what, which this port does not emit: a form not ported yet, or one the Prolog compiler has no code for (a slot the frame lacks, a class an operation does not take).

39Definition todowhat : string : listline ≔

Whether a line is a todo.

42Definition is_todol : line : bool ≔
match l with
Insop None _
⇒
_
⇒
false

The first thing lines leave undone, if any.

49Fixpoint first_todols : listline : optionstring ≔
match ls with
[ ]
⇒
None
l :: ls′
⇒
→
match l with
⇒
Somewhat
_
⇒
Some""
else

Names

The text of a name as format's ¬w writes it: an atom or an integer as it is, anything else in canonical form.

65Fixpoint name_textt : term : string ≔
match t with
⇒
a
TAppf args
⇒
f ++ "(" ++ String.concat"," mapname_text args ++ ")"
⇒
"[" ++ String.concat"," mapname_text xs ++ "]"

As abi_symbol/3: the names under which code finds a function f or a global: its implementation for the signature sig and the public alias of it, its getter, its function object, its data object and aux array.

77Definition impl_symbolsig : Z f : string : string ≔
"pizlonatedFIP" ++ decimalsig ++ "_" ++ f
79Definition entry_symbolsig : sigref f : string : string ≔
match sig with
⇒
"pizlonatedFI" ++ decimaln ++ "_" ++ f
⇒
"pizlonatedFIN" ++ decimalr ++ "_" ++ decimala ++ "_" ++ f
84Definition getter_symbolf : string : string ≔
"pizlonated_" ++ f
85Definition function_object_symbolf : string : string ≔
"pizlonatedFO_" ++ f
86Definition data_object_symbolf : string : string ≔
"pizlonatedDO_" ++ f
87Definition data_aux_symbolf : string : string ≔
"pizlonatedDA_" ++ f

As struct_field/3: the offsets of the thread's fields and of a function object's.

91Definition thread_stack_limit: Z ≔
0
92Definition thread_state: Z ≔
8
93Definition thread_top_frame: Z ≔
16
94Definition thread_cc_inline_buffer: Z ≔
128
95Definition thread_cc_inline_aux_buffer: Z ≔
384
96Definition thread_cc_outline_buffer: Z ≔
640
97Definition thread_cc_outline_aux_buffer: Z ≔
648
98Definition thread_cc_outline_size: Z ≔
656
99Definition function_object_fast_entry: Z ≔
0
100Definition function_object_generic_entry: Z ≔
8
101Definition function_object_signature: Z ≔
16

The frame

n rounded up to a multiple of 16.

106Definition sixteen: Z ≔
16
107Definition fifteen: Z ≔
15
108Definition eight: Z ≔
8
109Definition round16n : Z : Z ≔
n + fifteen / sixteen × sixteen

Where a named local is: its payload at -payload(%rbp), 16 aligned, and its aux, a count and then a lower for each word, at -aux(%rbp).

114Record local_slot: Type ≔ mkLocalSlot
ls_payload
 : Z
ls_aux
 : Z
ls_size
 : Z
ls_padded
 : Z

As ctx(f(Name, Ret, Slots, Blocks), Size, FrameBase, Labels, _): what the code of a function reads of it. A slot's number n means -n(%rbp). The frame record the collector walks is at -base(%rbp): its parent, its origin, then lowers[ ].

125Record ctx: Type ≔ mkCtx
cx_name
 : string
the function's name, the stem of its labels
cx_slots
 : nmapZ
each key's slot, by key_term
cx_localseach named local, by its name
cx_size
 : Z
the bytes subtracted from %rsp
cx_base
 : Z
cx_phis
 : nmaplistphi
each block's phis, by its label

As plain_slot/3: place one payload key after off bytes.

135Definition plain_slotst : nmapZ × nmaplocal_slot × Z k : key : nmapZ × nmaplocal_slot × Z ≔
let 'slots, locals, off ≔ st in
match k with
KLocalx size
⇒
let padded ≔ round16size in
let payload ≔ round16off + padded in
let aux ≔ payload + padded + eight in
slots, nm_addx mkLocalSlotpayload aux size padded locals, aux
⇒
nm_addkey_termk off + sixteen slots, locals, off + sixteen
_
⇒
nm_addkey_termk off + eight slots, locals, off + eight

As lower_slot/4: the root k is lowersi.

149Definition lower_slotbase : Z st : nmapZ × Z k : key : nmapZ × Z ≔
let 'slots, i ≔ st in
nm_addkey_termk base − sixteen − eight × i slots, i + 1

As layout/4 and function_ctx/8: the context of a plan. An alias whose key has no slot gets none.

155Definition plan_ctxp : plan : ctx ≔
let fr ≔ pl_framep in
let 'slots1, locals, plain_bytes ≔ fold_leftplain_slot fr_plainfr nm_empty, nm_empty, 0 in
let base ≔ plain_bytes + sixteen + eight × Zlengthfr_rootsfr in
let 'slots2, _ ≔ fold_leftlower_slotbase fr_rootsfr slots1, 0 in
let slots ≔
fold_left
λ m a  ⇒
match nm_findkey_termsnda slots2 with
Someoff
⇒
nm_addkey_termfsta off m
None
⇒
m
slots2
in
mkCtxname_textpl_namep slots locals round16base base nm_of_listmapλb ⇒ pb_labelb, pb_phisb pl_blocksp
171Definition slotcx : ctx k : key : optionZ ≔

The lines f gives for k's slot.

174Definition with_slotcx : ctx k : key f : Z → listline : listline ≔
match slotcx k with
Someoff
⇒
foff
None
⇒
todo"no slot"

As reg_slot_store//3: the store of the register r into k's slot.

182Definition slot_storecx : ctx r : string k : key : listline ≔
with_slotcx k λoff ⇒ ins"mov" "q" regr; mem−off "rbp"

As slot_reg_load//3: the load of k's slot into the register r.

187Definition slot_loadcx : ctx k : key r : string : listline ≔
with_slotcx k λoff ⇒ ins"mov" "q" mem−off "rbp"; regr

Labels

As special_label/3: a label shared by the whole function.

193Definition special_labelcx : ctx tag : string : string ≔
".L" ++ cx_namecx ++ ".." ++ tag
197Definition block_labelcx : ctx l : name : string ≔
".L" ++ cx_namecx ++ "." ++ name_textl

As local_label/5: a label inside the code of the instruction index of a block, or of its jump.

202Definition local_labelcx : ctx block : name index tag : string : string ≔
".L" ++ cx_namecx ++ "." ++ name_textblock ++ ".." ++ index ++ "." ++ tag

As origin_label/3: the frame's origin, which is c at calls and n at pollchecks and checks.

207Definition origin_labelname which : string : string ≔
".L" ++ name ++ "..origin_" ++ which

Registers and values

As reg_name/3: the name of the short register r at a class, as integers have it; a float's bits travel in the same registers.

214Definition reg64r : string : string ≔
→
"rax"
→
"rcx"
→
"rdx"
→
"rsi"
→
"rdi"
else
r
218Definition reg32r : string : string ≔
→
"eax"
→
"ecx"
→
"edx"
→
"esi"
→
"edi"
else
r ++ "d"

Whether a class is 32 bits wide in a register, or 64; nothing for the classes with no register form.

225Definition class_halfk : class : optionbool ≔
match k with
⇒
Sometrue
⇒
Somefalse
_
⇒
None
232Definition reg_namer : string half : bool : string ≔
half
→
else

As att_suffix/2 at a class.

235Definition class_suffixhalf : bool : string ≔
half
→
"l"
else
"q"
237Definition two32: Z ≔
4294967296
238Definition two63: Z ≔
9223372036854775808
239Definition two64: Z ≔
18446744073709551616

As amd64.pl's load//4: the code that puts the value v, read at the class k, in the short register r. A global's address is the same at every class.

244Definition loadcx : ctx v : value k : class r : string : listline ≔
match v, class_halfk with
Globalg, _
⇒
_, None
⇒
todo"load class"
Tmpn, Somehalf
⇒
with_slotcx KTmpn λoff ⇒ ins"mov" class_suffixhalf mem−off "rbp"; regreg_namer half
Constn, Somehalf
⇒
half
→
ins"mov" "l" immn mod two32; regreg32r
else
let u ≔ n mod two64 in
ins"movabs" "q" immif u ≥? two63 then u − two64 else u; regreg64r

As lower_reg_load//3: the lower of a p value into the register r: its root's, or 0 for a constant.

259Definition lower_loadcx : ctx v : value r : string : listline ≔
match v with
⇒
ins"mov" "q" imm0; regr
⇒
todo"lower of a global"

As flight_load//2: a p value's address into %rax and its lower into %rcx.

268Definition flight_loadcx : ctx v : value : listline ≔
loadcx v L "a" ++ lower_loadcx v "rcx"

As flight_store//2: the pointer in %rax and %rcx into the temporary d and its root.

273Definition flight_storecx : ctx d : name : listline ≔
slot_storecx "rax" KTmpd ++ slot_storecx "rcx" KLowerKTmpd

As origin_store//2: the store of the c or n origin into the frame record.

278Definition origin_storecx : ctx which : string : listline ≔
ins"lea" "q" riporigin_labelcx_namecx which; reg"rax"; ins"mov" "q" reg"rax"; memeight − cx_basecx "rbp"

As to_xmm//3 and from_xmm//3: a float's bits between the short register r and an xmm register.

284Definition xmm_movek : class : string ≔
match k with
⇒
"movd"
_
⇒
"movq"
285Definition to_xmmk : class r x : string : listline ≔
ins0xmm_movek regreg_namer match k with Single ⇒ true | _ ⇒ false end; regx
287Definition from_xmmk : class x r : string : listline ≔
ins0xmm_movek regx; regreg_namer match k with Single ⇒ true | _ ⇒ false end

As target_form/2: the bytes of stack a buffered return of n words takes around a call.

292Definition buffer_bytesn : Z : Z ≔

More operands

D(%B,%I).

297Definition mem_indexd : Z b i : string : operand ≔

S+N(%rip).

300Definition rip_pluss : string n : Z : operand ≔

*O, the target of an indirect call.

304Definition indo : operand : operand ≔

The fast convention

As form_short_regs/2: the integer registers that carry a call's words, by the return's protocol. A buffered return's buffer takes %rdx's place.

311Definition form_short_regsr : protocol : liststring ≔
match r with
⇒
"d"; "c"; "r8"; "r9"
⇒
"c"; "r8"; "r9"

Where a word of a call travels.

318Inductive location: Type ≔
|LocReg
r : string
the short register r
|LocXmm
x : string
an xmm register
|LocStack
i : Z
the stack word i, at 8i(%rsp) at the call
324Definition float_classk : class : bool ≔
match k with
⇒
true
_
⇒
false
327Definition xmm_regi : Z : string ≔
"xmm" ++ decimali

The register of a word of a returned tuple: gpr(G) or xmm(K, X).

331Inductive result_reg: Type ≔
|RrGpr
g : string
|RrXmm
k : class x : string

As result_registers/4: integer words in the registers gs in order, float words in xs. A float word with no xmm register left takes an integer one, as the second clause gives it; nothing if the integer ones run out.

339Fixpoint result_registersks : listclass gs xs : liststring : optionlistresult_reg ≔
match ks with
[ ]
⇒
Some[ ]
k :: ks′
⇒
match if float_classk then xs else [ ] with
x :: xs′
⇒
option_mapconsRrXmmk x result_registersks′ gs xs′
[ ]
⇒
match gs with
g :: gs′
⇒
option_mapconsRrGprg result_registersks′ gs′ xs
[ ]
⇒
None

A tuple's third float word has no xmm register and takes an integer one.

355Example result_registers_floats: result_registersDouble; L; Double; Double "rdx"; "rcx" "xmm0"; "xmm1" = SomeRrXmmDouble "xmm0"; RrGpr"rdx"; RrXmmDouble "xmm1"; RrGpr"rcx"
Proof 1 step Qed
reflexivity

As bank_locations/7: each class's location, then the count of stack words and of xmm registers.

362Fixpoint bank_locationsks : listclass rs : liststring x s : Z : listlocation × Z × Z ≔
match ks with
[ ]
⇒
[ ], s, x
k :: ks′
⇒
→
x <? eight
→
let 'ls, ns, nx ≔ bank_locationsks′ rs x + 1 s in
LocXmmxmm_regx :: ls, ns, nx
else
let 'ls, ns, nx ≔ bank_locationsks′ rs x s + 1 in
LocStacks :: ls, ns, nx
else
match rs with
r :: rs′
⇒
let 'ls, ns, nx ≔ bank_locationsks′ rs′ x s in
LocRegr :: ls, ns, nx
[ ]
⇒
let 'ls, ns, nx ≔ bank_locationsks′ [ ] x s + 1 in
LocStacks :: ls, ns, nx
381Definition word_classw : word : class ≔
match w with
Wfk _
⇒
k
384Definition typed_locationsws : listword r : protocol : listlocation × Z × Z ≔

As stack_bytes/2: n stack words keep %rsp 16 aligned.

388Definition stack_bytesn : Z : Z ≔
n + 1 / 2 × sixteen

Check kinds

As k(Size, Write, Align): what an access check tests, which names its failure block and its origin.

394Record check_kind: Type ≔ mkKind
ck_size
 : Z
ck_write
 : bool
ck_align
 : Z
396Definition kind_textk : check_kind : string ≔
++
"."
++
→
"1"
else
"0"
++
400Definition check_fail_labelcx : ctx k : check_kind : string ≔
".L" ++ cx_namecx ++ "..fail." ++ kind_textk
402Definition check_origin_labelname : string k : check_kind : string ≔
".L" ++ name ++ "..chk." ++ kind_textk