Fil-C on Nix

Filnix wiki

the formal campaign

rocq/backend/IrTerm.v

The checked IR back as Prolog terms: the encoders of the syntax of Syntax.v, the inverse of Transport.v's decoders, so that the backend can print an instruction as the very term the Prolog compiler printed it as (nanofilabi − termsFILE).

Each encoder writes the one term its decoder reads its value from: when the decoder reads a term t as x, the encoder writes x as t, and the decoder reads that as x again. No decoder reads one value from two terms, so there is no spelling to choose.

The encoders are total, but not every value of the syntax has a term. What is written for a value that no term decodes to:

  • To of a label that is itself poll(L) is written poll(L), which reads back as Poll of L (enc_target);
  • a RawStore of width p is written raw_store(p, ...), which the decoder refuses: a pointer store is raw_store_pointer (enc_inst);
  • ExtF, FloatToInt and IntToFloat at a class ir.pl has no such op for are written as terms that are not ops, which the decoder refuses (enc_op).

The examples at the end check both directions, by computation, on terms the Prolog compiler printed for nanofil/tests/filc.

From Stdlib Require Import String ZArith List
From Nanofil Require Import Term Syntax Validate Transport
Import ListNotations
Open Scope string_scope
Open Scope Z_scope

Values and the small tables

As ir.pl writes the temporary named d: tmp(D).

35Definition enc_tmpd : name : term ≔
TApp"tmp" d

As ir.pl writes a value: tmp(N), const(N) or global(S).

38Definition enc_valuev : value : term ≔
match v with
⇒
TApp"const" TIntn
⇒
TApp"global" s

As ir.pl writes the rights of an access: read or write.

46Definition enc_rightsr : rights : term ≔
match r with
⇒
"read"
⇒
"write"

As ir.pl writes the bound a half check tests: upper or lower.

51Definition enc_boundb : bound : term ≔
match b with
⇒
"upper"
⇒
"lower"

As ir.pl writes a narrow integer type: sw, uw, sh, uh, sb or ub.

56Definition enc_narrowt : narrow : term ≔
match t with
⇒
"sw"
⇒
"uw"
⇒
"sh"
⇒
"uh"
⇒
"sb"
⇒
"ub"

As ir.pl writes the type of a raw load: l, s, d, x, or a narrow type.

63Definition enc_load_typet : load_type : term ≔
match t with

As ir.pl writes a comparison's Cond: eq, ne, the signed and unsigned integer orders sle to ugt, the float orders le lt ge gt, o (ordered) or uo (unordered).

75Definition enc_condc : cond : term ≔
match c with
⇒
"eq"
⇒
"ne"
⇒
"sle"
⇒
"slt"
⇒
"sge"
⇒
"sgt"
⇒
"ule"
⇒
"ult"
⇒
"uge"
⇒
"ugt"
⇒
"le"
⇒
"lt"
⇒
"ge"
⇒
"gt"
⇒
"o"
⇒
"uo"

As ir.pl writes one memory effect of a raw pointer load or store: aux_read, lower_resolve, address_read, atomic_read, aux_ensure, lower_barrier, rooted_reload, lower_write, address_write or atomic_write.

88Definition enc_effecte : effect : term ≔
match e with
⇒
"aux_read"
⇒
"lower_resolve"
⇒
"address_read"
⇒
"atomic_read"
⇒
"aux_ensure"
⇒
"lower_barrier"
⇒
"rooted_reload"
⇒
"lower_write"
⇒
"address_write"
⇒
"atomic_write"

As ir.pl writes the Effects of a raw pointer load or store: the list of its effects, in order.

99Definition enc_effectses : listeffect : term ≔

As ir.pl writes the width of a store: b, h, w, l, p, s, d or x.

103Definition enc_widthw : width : term ≔
match w with
⇒
"b"
⇒
"h"
⇒
"w"
⇒
"l"
⇒
"p"
⇒
"s"
⇒
"d"
⇒
"x"

The atom signed or unsigned. No term of the IR holds it: it is written only in the terms of enc_op that are not ops.

111Definition enc_signednesssg : signedness : term ≔
match sg with
⇒
"signed"
⇒
"unsigned"

Ops

As ir.pl writes a check or one of its reuse forms of the name f: f(Lo, Hi, Rights, Align).

118Definition enc_check4f : string lo hi : Z r : rights al : Z : term ≔

As ir.pl writes an Op: an atom such as add or ptoi, or a compound such as cmp(Cond, K), ext(T), alloc(Align), check(Lo, Hi, Rights, Align), check_ahead(Lo, Hi, Rights, Align, AHi), half_check(Bound, Lo, Hi, Rights, Align), span_test(Lo, Hi), limit(Size), check_local(Name, Off, Bytes, Rights, Align), raw_load(T, Off) or raw_load_pointer(Off, Effects).

A float widening is ext(s) or ext(d), naming its source class; a float to an integer is stosi, stoui, dtosi, dtoui, xtosi or xtoui, and an integer to a float swtof, uwtof, sltof or ultof. Those are all the conversions ir.pl has. At any other class ExtF k is written ext(K), and FloatToInt k sg and IntToFloat k sg are written float_to_int(K, Sg) and int_to_float(K, Sg), Sg being signed or unsigned: none of them is an op, and the decoder refuses each.

137Definition enc_opo : op : term ≔
match o with
⇒
TAtom"add"
⇒
TAtom"sub"
⇒
TAtom"mul"
⇒
TAtom"div"
⇒
TAtom"udiv"
⇒
TAtom"rem"
⇒
TAtom"urem"
⇒
TAtom"and"
⇒
TAtom"or"
⇒
TAtom"xor"
⇒
TAtom"sar"
⇒
TAtom"shr"
⇒
TAtom"shl"
⇒
TAtom"neg"
⇒
TAtom"copy"
⇒
TAtom"ptoi"
⇒
TAtom"itop"
Cmpc k
⇒
⇒
TApp"ext" eclassk
⇒
TAtom"truncd"
⇒
TAtom"truncx"
⇒
match k, sg with
⇒
TAtom"stosi"
⇒
TAtom"dtosi"
_, _
⇒
TApp"float_to_int" eclassk; enc_signednesssg
⇒
match k, sg with
⇒
TAtom"swtof"
⇒
TAtom"uwtof"
⇒
TAtom"sltof"
⇒
TAtom"ultof"
_, _
⇒
TApp"int_to_float" eclassk; enc_signednesssg
⇒
TAtom"cast"
⇒
TApp"alloc" TIntal
Checklo hi r al
⇒
enc_check4"check" lo hi r al
CheckAheadlo hi r al ahi
⇒
TApp"check_ahead" TIntlo; TInthi; enc_rightsr; TIntal; TIntahi
Renewlo hi r al
⇒
enc_check4"renew" lo hi r al
RenewHulllo hi r al
⇒
enc_check4"renew_hull" lo hi r al
HalfCheckb lo hi r al
⇒
TApp"half_check" enc_boundb; TIntlo; TInthi; enc_rightsr; TIntal
⇒
TApp"span_test" TIntlo; TInthi
RenewIflo hi r al
⇒
enc_check4"renew_if" lo hi r al
Limitsize
⇒
TApp"limit" TIntsize
CheckLimitlo hi r al
⇒
enc_check4"check_limit" lo hi r al
CheckLocalx off bytes r al
⇒
TApp"check_local" x; TIntoff; TIntbytes; enc_rightsr; TIntal
⇒
TAtom"check_function"
RawLoadt off
⇒
TApp"raw_load" enc_load_typet; TIntoff
⇒
TApp"raw_load_pointer" TIntoff; enc_effectses
⇒
TAtom"va_args"
⇒
TAtom"va_arg"

Instructions

As ir.pl writes an argument of a flight: address(V), or the value itself.

189Definition enc_flight_arga : flight_arg : term ≔
match a with

As ir.pl writes a flight's Lower: none or lower(V).

196Definition enc_flight_lowerlw : flight_lower : term ≔
match lw with

As ir.pl writes one result of a call, the temporary d of class k: result(tmp(D), K).

204Definition enc_resultr : name × class : term ≔
TApp"result" enc_tmpfstr; eclasssndr

As ir.pl writes a call's Res: void, result(tmp(D), K), or tuple([result(tmp(D1), K1), result(tmp(D2), K2)]).

209Definition enc_call_resultr : call_result : term ≔
match r with
⇒
TAtom"void"
⇒
TApp"tuple" TListmapenc_result rs

As ir.pl writes a call's argument, the class first: arg(K, V).

217Definition enc_arga : arg : term ≔
match a with
Argk v
⇒

As ir.pl writes a call's arguments: the list of them.

221Definition enc_argsargs : listarg : term ≔
TListmapenc_arg args

As ir.pl writes an instruction: let(tmp(D), K, Op, Args), flight(tmp(D), Op, Args, Lower), raw_store(Width, Off, Value, Addr), raw_store_pointer(Off, Value, Addr, Effects), call(Res, Callee, Args), raw_call(Res, Callee, Args), local_alloc(Name, Size) or loc(File, Line).

A RawStore of the width Wp is written raw_store(p, ...), which is not an instruction of the IR (a pointer store is raw_store_pointer) and which the decoder refuses.

233Definition enc_insti : inst : term ≔
match i with
Letd k o args
⇒
Flightd o args lw
⇒
RawStorew off v a
⇒
TApp"raw_store" enc_widthw; TIntoff; enc_valuev; enc_valuea
RawStorePointeroff v a es
⇒
TApp"raw_store_pointer" TIntoff; enc_valuev; enc_valuea; enc_effectses
Callr callee args
⇒
RawCallr callee args
⇒
TApp"raw_call" enc_call_resultr; enc_valuecallee; enc_argsargs
⇒
TApp"local_alloc" x; TIntsize
Locfile line
⇒
TApp"loc" file; TIntline

Jumps and phis

As ir.pl writes a jump's target: the label L, or poll(L) for a poll edge. A label is any ground term, and one that is itself poll(L) cannot be told from a poll edge to L: To of it is written poll(L), which the decoder reads as Poll of L. The decoder never gives such a To.

255Definition enc_targett : target : term ≔
match t with
⇒
l
⇒
TApp"poll" l

As ir.pl writes the jump that ends a block: goto(L), branch(V, L1, L2), ret(V), rets([V1, V2]), ret or unreachable.

264Definition enc_jumpj : jump : term ≔
match j with
JBranchv t1 t2
⇒
⇒
TApp"rets" TListmapenc_value vs
⇒
TAtom"unreachable"

As ir.pl writes one pair of a phi, a predecessor's label and the value for the edge from it: Pred − Value.

276Definition enc_pairp : name × value : term ≔
TApp"-" fstp; enc_valuesndp

As ir.pl writes a phi: phi(tmp(D), K, [Pred-Value]).

279Definition enc_phip : phi : term ≔
match p with
Phid k pairs
⇒
TApp"phi" enc_tmpd; eclassk; TListmapenc_pair pairs

Examples

The decoder dec reads the term t, and the encoder enc writes what it read as t again. Then dec also reads what enc wrote as the same value, since that is t: one statement checks both directions.

289Definition writes_backX : Type dec : term → optionX enc : X → term t : term : Prop ≔
option_mapenc dect = Somet

The decoder dec reads back each value of xs from the term the encoder enc writes for it.

294Definition reads_backX : Type dec : term → optionX enc : X → term xs : listX : Prop ≔
mapλx ⇒ decencx xs = mapSome xs

Every class is read back from eclass's atom for it.

298Example class_reads_back: ∀k, dclasseclassk = Somek
Proof 2 steps Qed
intros k
destruct k ; reflexivity

Both rights are read back.

302Example rights_reads_back: ∀r, drightsenc_rightsr = Somer
Proof 2 steps Qed
intros r
destruct r ; reflexivity

Both bounds are read back.

306Example bound_reads_back: ∀b, dboundenc_boundb = Someb
Proof 2 steps Qed
intros b
destruct b ; reflexivity

Every narrow type is read back.

310Example narrow_reads_back: ∀t, dnarrowenc_narrowt = Somet
Proof 2 steps Qed
intros t
destruct t ; reflexivity

Every load type is read back.

314Example load_type_reads_back: ∀t, dload_typeenc_load_typet = Somet
Proof 3 steps Qed
intros t
destruct t as | | | | n ; try reflexivity
destruct n ; reflexivity

Every condition is read back.

318Example cond_reads_back: ∀c, dcondenc_condc = Somec
Proof 2 steps Qed
intros c
destruct c ; reflexivity

Every effect is read back.

322Example effect_reads_back: ∀e, deffectenc_effecte = Somee
Proof 2 steps Qed
intros e
destruct e ; reflexivity

Every width is read back.

326Example width_reads_back: ∀w, dwidthenc_widthw = Somew
Proof 2 steps Qed
intros w
destruct w ; reflexivity

Every value is read back.

330Example value_reads_back: ∀v, dvalueenc_valuev = Somev
Proof 2 steps Qed
intros v
destruct v ; reflexivity

The two effect lists of a pointer load, and the empty one.

Proof 1 step Qed
reflexivity

Every op that is an atom, the float conversions among them.

Proof 1 step Qed
reflexivity

Every op that is a compound, one or two of each.

Proof 1 step Qed
reflexivity

The conversions ir.pl does not have are refused, each one.

Proof 1 step Qed
reflexivity

A raw store of a pointer is refused, and a label poll(l) reads back as a poll edge.

373Example no_such_term: dinstenc_instRawStoreWp 0 Const0 TmpTAtom"q" = None ∧ dtargetenc_targetToTApp"poll" TAtom"l" = SomePollTAtom"l"
Proof 1 step Qed
split ; reflexivity

let(tmp(chk0), a, check(0, 8, write, 1), [tmp(p)]): a check.

379Example term_let_check: writes_backdinst enc_inst TApp"let" TApp"tmp" TAtom"chk0"; TAtom"a"; TApp"check" TInt0; TInt8; TAtom"write"; TInt1; TListTApp"tmp" TAtom"p"
Proof 1 step Qed
reflexivity

let(tmp(chk0), a, check_local(x, 0, 1, read, 1), []): a check of a named local, which reads no argument.

388Example term_let_check_local: writes_backdinst enc_inst TApp"let" TApp"tmp" TAtom"chk0"; TAtom"a"; TApp"check_local" TAtom"x"; TInt0; TInt1; TAtom"read"; TInt1; TList[ ]
Proof 1 step Qed
reflexivity

let(tmp(a), l, raw_load(sb, 0), [tmp(chk3)]): a raw load.

396Example term_let_raw_load: writes_backdinst enc_inst TApp"let" TApp"tmp" TAtom"a"; TAtom"l"; TApp"raw_load" TAtom"sb"; TInt0; TListTApp"tmp" TAtom"chk3"
Proof 1 step Qed
reflexivity

let(tmp(back), p, raw_load_pointer(0, [aux_read, lower_resolve, address_read]), [tmp(chk2)]): a raw pointer load.

404Example term_let_raw_load_pointer: writes_backdinst enc_inst TApp"let" TApp"tmp" TAtom"back"; TAtom"p"; TApp"raw_load_pointer" TInt0; TListTAtom"aux_read"; TAtom"lower_resolve"; TAtom"address_read"; TListTApp"tmp" TAtom"chk2"
Proof 1 step Qed
reflexivity

let(tmp(c), w, cmp(eq, w), [tmp(k), const(1)]): a comparison.

413Example term_let_cmp: writes_backdinst enc_inst TApp"let" TApp"tmp" TAtom"c"; TAtom"w"; TApp"cmp" TAtom"eq"; TAtom"w"; TListTApp"tmp" TAtom"k"; TApp"const" TInt1
Proof 1 step Qed
reflexivity

let(tmp(b), d, ext(s), [tmp(a)]): a float widening.

420Example term_let_ext_float: writes_backdinst enc_inst TApp"let" TApp"tmp" TAtom"b"; TAtom"d"; TApp"ext" TAtom"s"; TListTApp"tmp" TAtom"a"
Proof 1 step Qed
reflexivity

let(tmp(kl), l, ext(sw), [tmp(k)]): an integer extension.

427Example term_let_ext_narrow: writes_backdinst enc_inst TApp"let" TApp"tmp" TAtom"kl"; TAtom"l"; TApp"ext" TAtom"sw"; TListTApp"tmp" TAtom"k"
Proof 1 step Qed
reflexivity

let(tmp(r), w, dtosi, [tmp(b)]): a float to an integer.

434Example term_let_float_to_int: writes_backdinst enc_inst TApp"let" TApp"tmp" TAtom"r"; TAtom"w"; TAtom"dtosi"; TListTApp"tmp" TAtom"b"
Proof 1 step Qed
reflexivity

let(tmp(base), p, copy, [global(g)]): a symbol's address.

441Example term_let_copy_global: writes_backdinst enc_inst TApp"let" TApp"tmp" TAtom"base"; TAtom"p"; TAtom"copy"; TListTApp"global" TAtom"g"
Proof 1 step Qed
reflexivity

raw_store(l, 0, const(-2), tmp(chk0)): a raw store.

448Example term_raw_store: writes_backdinst enc_inst TApp"raw_store" TAtom"l"; TInt0; TApp"const" TInt−2; TApp"tmp" TAtom"chk0"
Proof 1 step Qed
reflexivity

raw_store_pointer(0, tmp(obj), tmp(chk1), [aux_ensure, lower_barrier, rooted_reload, lower_write, address_write]): a raw pointer store.

456Example term_raw_store_pointer: writes_backdinst enc_inst TApp"raw_store_pointer" TInt0; TApp"tmp" TAtom"obj"; TApp"tmp" TAtom"chk1"; TListTAtom"aux_ensure"; TAtom"lower_barrier"; TAtom"rooted_reload"; TAtom"lower_write"; TAtom"address_write"
Proof 1 step Qed
reflexivity

flight(tmp(q), add, [address(tmp(p)), const(8)], lower(tmp(p))): a flight with a lower.

466Example term_flight_lower: writes_backdinst enc_inst TApp"flight" TApp"tmp" TAtom"q"; TAtom"add"; TListTApp"address" TApp"tmp" TAtom"p"; TApp"const" TInt8; TApp"lower" TApp"tmp" TAtom"p"
Proof 1 step Qed
reflexivity

flight(tmp(f), copy, [tmp(i)], none): a flight without one.

474Example term_flight_none: writes_backdinst enc_inst TApp"flight" TApp"tmp" TAtom"f"; TAtom"copy"; TListTApp"tmp" TAtom"i"; TAtom"none"
Proof 1 step Qed
reflexivity

call(void, global(churn), []): a call with no result.

481Example term_call_void: writes_backdinst enc_inst TApp"call" TAtom"void"; TApp"global" TAtom"churn"; TList[ ]
Proof 1 step Qed
reflexivity

call(result(tmp(p), p), global(make), [arg(l, tmp(v))]): a call with one result.

488Example term_call_result: writes_backdinst enc_inst TApp"call" TApp"result" TApp"tmp" TAtom"p"; TAtom"p"; TApp"global" TAtom"make"; TListTApp"arg" TAtom"l"; TApp"tmp" TAtom"v"
Proof 1 step Qed
reflexivity

call(tuple([result(tmp(c), l), result(tmp(d), l)]), global(two), [arg(l, tmp(a))]): a call with a tuple of results.

497Example term_call_tuple: writes_backdinst enc_inst TApp"call" TApp"tuple" TListTApp"result" TApp"tmp" TAtom"c"; TAtom"l"; TApp"result" TApp"tmp" TAtom"d"; TAtom"l"; TApp"global" TAtom"two"; TListTApp"arg" TAtom"l"; TApp"tmp" TAtom"a"
Proof 1 step Qed
reflexivity

raw_call(result(tmp(a), s), tmp(chk0), [arg(s, const(1069547520))]): a call of a proven function.

507Example term_raw_call_result: writes_backdinst enc_inst TApp"raw_call" TApp"result" TApp"tmp" TAtom"a"; TAtom"s"; TApp"tmp" TAtom"chk0"; TListTApp"arg" TAtom"s"; TApp"const" TInt1069547520
Proof 1 step Qed
reflexivity

raw_call(tuple([result(tmp(g), l), result(tmp(h), l)]), tmp(chk2), [arg(l, tmp(x))]): one with a tuple of results.

516Example term_raw_call_tuple: writes_backdinst enc_inst TApp"raw_call" TApp"tuple" TListTApp"result" TApp"tmp" TAtom"g"; TAtom"l"; TApp"result" TApp"tmp" TAtom"h"; TAtom"l"; TApp"tmp" TAtom"chk2"; TListTApp"arg" TAtom"l"; TApp"tmp" TAtom"x"
Proof 1 step Qed
reflexivity

local_alloc(x, 13): a named local.

525Example term_local_alloc: writes_backdinst enc_inst TApp"local_alloc" TAtom"x"; TInt13
Proof 1 step Qed
reflexivity

loc('basic.c', 12): a source position.

530Example term_loc: writes_backdinst enc_inst TApp"loc" TAtom"basic.c"; TInt12
Proof 1 step Qed
reflexivity

branch(tmp(c), poll(fill), sum): a branch, one edge polling.

535Example term_branch_poll: writes_backdjump enc_jump TApp"branch" TApp"tmp" TAtom"c"; TApp"poll" TAtom"fill"; TAtom"sum"
Proof 1 step Qed
reflexivity

goto(poll(loop)): a goto that polls.

541Example term_goto_poll: writes_backdjump enc_jump TApp"goto" TApp"poll" TAtom"loop"
Proof 1 step Qed
reflexivity

goto(end): a plain goto.

546Example term_goto_plain: writes_backdjump enc_jump TApp"goto" TAtom"end"
Proof 1 step Qed
reflexivity

ret(const(1)): a return of one value.

550Example term_ret_value: writes_backdjump enc_jump TApp"ret" TApp"const" TInt1
Proof 1 step Qed
reflexivity

rets([tmp(n), tmp(m)]): a return of a tuple.

554Example term_rets_tuple: writes_backdjump enc_jump TApp"rets" TListTApp"tmp" TAtom"n"; TApp"tmp" TAtom"m"
Proof 1 step Qed
reflexivity

ret: a return from a void function.

560Example term_ret_void: writes_backdjump enc_jump TAtom"ret"
Proof 1 step Qed
reflexivity

unreachable.

564Example term_unreachable: writes_backdjump enc_jump TAtom"unreachable"
Proof 1 step Qed
reflexivity

phi(tmp(i), w, [start-const(0), fill-tmp(i1)]): a phi of two edges.

569Example term_phi_pairs: writes_backdphi enc_phi TApp"phi" TApp"tmp" TAtom"i"; TAtom"w"; TListTApp"-" TAtom"start"; TApp"const" TInt0; TApp"-" TAtom"fill"; TApp"tmp" TAtom"i1"
Proof 1 step Qed
reflexivity