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:

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"
⇒
TAtom"sqrt"
⇒
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"
Setjmpkind
⇒
TApp"setjmp" TAtommatch kind with SjSetjmp ⇒ "setjmp" | SjUnderscore ⇒ "_setjmp" | SjSig ⇒ "sigsetjmp" end

Instructions

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

196Definition enc_flight_arga : flight_arg : term ≔
match a with

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

203Definition 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).

211Definition 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)]).

216Definition 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).

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

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

228Definition 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), loc(File, Line) or touch(tmp(Q)).

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.

240Definition 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
⇒
TApp"touch" enc_tmpq

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.

263Definition 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.

272Definition 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.

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

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

287Definition 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.

297Definition 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.

302Definition 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.

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

Both rights are read back.

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

Both bounds are read back.

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

Every narrow type is read back.

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

Every load type is read back.

322Example 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.

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

Every effect is read back.

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

Every width is read back.

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

Every value is read back.

338Example 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.

381Example 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.

387Example 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.

396Example 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.

404Example 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.

412Example 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.

421Example 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.

428Example 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.

435Example 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.

442Example 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.

449Example 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.

456Example 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.

464Example 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.

474Example 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.

482Example 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.

489Example 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.

496Example 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.

505Example 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.

515Example 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.

524Example 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.

533Example 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.

538Example 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.

543Example 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.

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

goto(end): a plain goto.

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

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

558Example 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.

562Example 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.

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

unreachable.

572Example 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.

577Example 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