Fil-C on Nix

Filnix wiki

the formal campaign

rocq/backend/TermCfg.v

# The control-flow graph of an unchecked function

The middle end's passes (promote.pl, copy.pl) run before pizlonation, on the unchecked IR, which the model has no inductive for. So they are on terms, as Pizlonate.v is, and this file gives them what cfg.pl, escape.pl and promote.pl give the Prolog ones:

  • a function's blocks taken apart (tblock);
  • its graph (term_cfg), with the successors of a branch sorted as jump_succs/2 sorts them. Cfg.v's graph keeps a jump's own order, which the validator does not depend on; these passes do, through the reverse postorder. The dominators and their intervals are Cfg.v's, which only read the graph;
  • the dominance frontiers (cfg_frontiers);
  • what an instruction and a jump read (inst_uses, jump_uses);
  • how often each temporary is defined (def_counts);
  • whether the function is in strict SSA form (strict_ssa).
From Stdlib Require Import String ZArith List Bool
From Nanofil Require Import Term Maps Semantics Cfg
From Backend Require Import Text Order Pizlonate Liveness
Import ListNotations
Open Scope string_scope
Open Scope Z_scope
Open Scope list_scope

String equality, written as Prolog's ==.

29Notation a == b ≔ String.eqba b (at level 70)

Blocks

A block block(Label, Phis, Insts, Jump) taken apart.

34Record tblock: Type ≔ mkTBlock
tb_label
 : term
its label
tb_phis
 : listterm
its phis, phi(tmp(D), K, Args)
tb_insts
 : listterm
its instructions
tb_jump
 : term
its jump

The block the term b is, if it is one.

42Definition term_blockb : term : optiontblock ≔
match b with
TAppf l; TListphis; TListinsts; j
⇒
f == "block"
→
SomemkTBlockl phis insts j
else
None
_
⇒
None

The term of the block b.

50Definition block_termb : tblock : term ≔

The name d when the term p is phi(tmp(D), K, Args).

54Definition phi_defp : term : listterm ≔
match p with
TAppf d; _; _
⇒
f == "phi"
→
else
[ ]
_
⇒
[ ]

The name d when the term p is param(K, tmp(D)).

58Definition param_defp : term : listterm ≔
match p with
TAppf _; d
⇒
f == "param"
→
else
[ ]
_
⇒
[ ]

The terms of a list term, none for any other term.

62Definition listedt : term : listterm ≔
match t with
⇒
ts
_
⇒
[ ]

The pair when the term t is A − B.

66Definition pair_partst : term : optionterm × term ≔
match t with
TAppf a; b
⇒
f == "-"
→
Somea, b
else
None
_
⇒
None

The graph

As edge_label/2: the label a jump's target t names, which is the label itself or poll(L).

73Definition target_labelt : term : term ≔
match t with
TAppf l
⇒
f == "poll"
→
l
else
t
_
⇒
t

As jump_succs(Jump, Succs): the ordset of the labels the jump j can go to. None for a term that is no jump.

78Definition jump_labelsj : term : optionnames ≔
match j with
TAppf xs
⇒
f == "goto"
→
match xs with
t
⇒
_
⇒
None
f == "branch"
→
match xs with
_; t1; t2
⇒
_
⇒
None
f == "ret" || f == "rets"
→
arity1 xs
→
Some[ ]
else
None
else
None
⇒
a == "ret" || a == "unreachable"
→
Some[ ]
else
None
_
⇒
None

As func_cfg(Blocks, Cfg): the graph of the blocks bs, whose entry is the first. Each block's predecessors are in the order of their labels, unreachable ones included. None when a jump is of no known shape or goes to a label that is no block's.

99Definition term_cfgbs : listtblock : optioncfg ≔
match bs with
[ ]
⇒
None
entry :: _
⇒
let* pairs ≔ map_optionλb ⇒ option_mapλss ⇒ tb_labelb, ss jump_labelstb_jumpb bs in
let succs ≔ nm_of_listpairs in
let edges ≔ flat_mapλp ⇒ mapλs ⇒ s, fstp sndp pairs in
negbforallbλe ⇒ nm_memfste succs edges
→
None
else
let by_pred ≔ msortλa b ⇒ term_comparesnda sndb edges in
let preds ≔
fold_left
λ m e  ⇒
nm_addfste
snde
::
match nm_findfste m with
Someps
⇒
ps
None
⇒
[ ]
m
rev'by_pred
nm_of_listmapλb ⇒ tb_labelb, [ ] bs
in
let* r ≔ reverse_postorderSSlengthedges tb_labelentry succs nm_empty [ ] in
SomemkCfgtb_labelentry sndr succs preds

The labels of the graph g that the entry reaches, as a set.

120Definition reachedg : cfg : nmapunit ≔
nm_of_listmapλl ⇒ l, tt cfg_rpog

Dominance frontiers

As runner_frontiers/6: the map df with the label b in the frontier of every label on the path of immediate dominators from runner up to, and not including, stop. The path has at most as many labels as the graph, the fuel.

129Fixpoint runner_frontiersfuel : nat idom : nmapname stop b runner : name df : nmaplistname : optionnmaplistname ≔
match fuel with
O
⇒
None
Sfuel′
⇒
name_eqbrunner stop
→
Somedf
else
let* xs ≔ nm_findrunner df in
let* up ≔ nm_findrunner idom in
runner_frontiersfuel′ idom stop b up nm_addrunner b :: xs df

As cfg_frontiers(Cfg, Idom, DF): the dominance frontier of every reachable label, an ordset. A label with two or more reachable predecessors is in the frontier of each label on the path from each of them up to its own immediate dominator (Cooper, Harvey and Kennedy).

145Definition cfg_frontiersg : cfg idom : nmapname : optionnmapnames ≔
let fuel ≔ Slengthcfg_rpog in
let* df ≔
fold_left
λ acc b  ⇒
let* df ≔ acc in
let* ps0 ≔ nm_findb cfg_predsg in
match filterλp ⇒ nm_memp df ps0, nm_findb idom with
_ :: _ :: _ as ps, Somestop
⇒
fold_left
λ acc r  ⇒
let* d ≔ acc in
runner_frontiersfuel idom stop b r d
ps
Somedf
_, _
⇒
Somedf
Somenm_of_listmapλl ⇒ l, [ ] cfg_rpog
in
Somenm_of_listmapλl ⇒ l, nsortnames_atdf l cfg_rpog

Uses

As temps(Values, Names): the ordset of the names of the temporaries among the values vs.

165Definition tempsvs : listterm : names ≔
nsortflat_maptmp_name vs

The value when the term a is arg(K, V).

168Definition arg_valuea : term : listterm ≔
match a with
TAppf _; v
⇒
f == "arg"
→
v
else
[ ]
_
⇒
[ ]

The value when the term p is Reg − V, an input of an asm_fixed.

173Definition pair_valuep : term : listterm ≔
match pair_partsp with
Some_, v
⇒
v
None
⇒
[ ]

As inst_uses(Inst, Uses): the ordset of the temporaries the instruction i reads. None for a term cfg.pl has no clause for; the backend's own uses(I, Extra) is left out, since no unchecked function has it.

180Definition inst_usesi : term : optionnames ≔
match i with
⇒
a == "fence"
→
Some[ ]
else
None
TAppf xs
⇒
f == "let"
→
match xs with
_; _; _; TListargs
⇒
Sometempsargs
_
⇒
None
f == "flight"
→
match xs with
_; _; TListargs; lw
⇒
let vs ≔
flat_map
λ a  ⇒
match a with
TAppg p
⇒
g == "address"
→
p
g == "tmp" || g == "const"
→
a
else
[ ]
_
⇒
[ ]
args
in
Some
match lw with
TAppg p
⇒
g == "lower"
→
p :: vs
else
vs
_
⇒
vs
_
⇒
None
f == "store" || f == "atomic_store"
→
match xs with
_; v; a
⇒
Sometempsv; a
_
⇒
None
f == "access"
→
match xs with
_; a; _; _
⇒
Sometempsa
_
⇒
None
f == "touch"
→
match xs with
q
⇒
Sometempsq
_
⇒
None
f == "asm_fixed"
→
match xs with
_; TListins; _
⇒
Sometempsflat_mappair_value ins
_
⇒
None
f == "raw_store"
→
match xs with
_; _; v; a
⇒
Sometempsv; a
_
⇒
None
f == "raw_store_pointer"
→
match xs with
_; v; a; _
⇒
Sometempsv; a
_
⇒
None
f == "call" || f == "raw_call"
→
match xs with
_; g; TListargs
⇒
Sometempsg :: flat_maparg_value args
_
⇒
None
f == "loc" || f == "local_alloc"
→
arity2 xs
→
Some[ ]
else
None
f == "local_load"
→
arity5 xs
→
Some[ ]
else
None
f == "local_store"
→
match xs with
_; v; _; _
⇒
Sometempsv
_
⇒
None
else
None
_
⇒
None

As jump_uses(Jump, Uses): the ordset of the temporaries the jump j reads.

234Definition jump_usesj : term : optionnames ≔
match j with
⇒
a == "ret" || a == "unreachable"
→
Some[ ]
else
None
TAppf xs
⇒
f == "goto"
→
arity1 xs
→
Some[ ]
else
None
f == "branch"
→
match xs with
v; _; _
⇒
Sometempsv
_
⇒
None
f == "ret"
→
match xs with
v
⇒
Sometempsv
_
⇒
None
f == "rets"
→
match xs with
⇒
Sometempsvs
_
⇒
None
else
None
_
⇒
None

Definitions

The names that the instruction i defines for escape.pl's def_counts/2 and copy.pl's temp_classes/3: a let's, a call's results and the outputs of an asm_fixed.

254Definition counted_defsi : term : listterm ≔
match i with
TAppf _
⇒
f == "let" || f == "call" || f == "asm_fixed"
→
else
[ ]
_
⇒
[ ]

As def_counts(Func, Counts): how many definitions each temporary has, among the params, the phis and the instructions of the blocks bs.

264Definition def_countsparams : listterm bs : listtblock : nmapnat ≔
let count m d ≔
S
match nm_findd m with
Somen
⇒
n
None
⇒
O
in
fold_leftλm b ⇒ fold_leftλm i ⇒ fold_leftcount counted_defsi m tb_instsb fold_leftcount flat_mapphi_def tb_phisb m bs fold_leftcount flat_mapparam_def params nm_empty

Whether some temporary of the function has two definitions.

272Definition defined_twicecounts : nmapnat params : listterm bs : listtblock : bool ≔
let twice d ≔
match nm_findd counts with
Somen
⇒
Nat.ltb1 n
None
⇒
false
in
existsbtwice flat_mapparam_def params || existsbλb ⇒ existsbtwice flat_mapphi_def tb_phisb || existsbλi ⇒ existsbtwice counted_defsi tb_instsb bs

Strict SSA

The terms of xs, each with its position from n.

281Fixpoint numberedA : Type n : Z xs : listA : listZ × A ≔
match xs with
[ ]
⇒
[ ]
x :: xs′
⇒
n, x :: numberedn + 1 xs′

Whether t, read in the block l at the position n or at its end, is defined before: defs gives each temporary the block and the position of its definition, ivs the dominator intervals. It stands alone, with its types written out, because a C++ extraction cannot type a None passed to a local function.

292Definition defined_beforedefs : nmapname × Z ivs : nmapZ × Z l : name n : optionZ t : name : bool ≔
match nm_findt defs with
Somedl, dpos
⇒
→
match n with
Somen
⇒
dpos <? n
None
⇒
true
None
⇒
false

As strict_ssa(F, Counts, Cfg, Idom): every temporary has one definition, and in the blocks the entry reaches each definition dominates each use. Params and phis are defined at position 0 of their block, the instructions from 1, and the jump reads after them; a phi argument is read at the end of its predecessor, and counts only if that is reachable. A use is defined when its definition is earlier in the same block, or in a block that dominates it.

309Definition strict_ssacounts : nmapnat params : listterm bs : listtblock g : cfg idom : nmapname : bool ≔
defined_twicecounts params bs
→
false
else
match dom_intervalsg idom with
None
⇒
false
Someivs
⇒
let defs ≔ nm_of_listmapλd ⇒ d, cfg_entryg, 0 flat_mapparam_def params ++ flat_mapλb ⇒ mapλd ⇒ d, tb_labelb, 0 flat_mapphi_def tb_phisb ++ flat_mapλpi ⇒ mapλd ⇒ d, tb_labelb, fstpi inst_defssndpi numbered1 tb_instsb bs in
let reach ≔ reachedg in
forallb
λ b  ⇒
let l ≔ tb_labelb in
negbnm_meml reach
||
forallb
λ p  ⇒
match p with
TAppf _; _; TListargs
⇒
negbf == "phi"
||
forallb
λ a  ⇒
match pair_partsa with
Somepred, v
⇒
negbnm_mempred reach || forallbdefined_beforedefs ivs pred None tmp_namev
None
⇒
true
args
_
⇒
true
&&
forallb
λ pi  ⇒
match inst_usessndpi with
Someus
⇒
forallbdefined_beforedefs ivs l Somefstpi us
None
⇒
true
&&
match jump_usestb_jumpb with
Someus
⇒
forallbdefined_beforedefs ivs l SomeZ.of_natlengthtb_instsb + 1 us
None
⇒
true
bs

Functions

As ir.pl's setjmp_func/1: some block of bs calls setjmp.

354Definition calls_setjmpbs : listtblock : bool ≔
existsb
λ b  ⇒
existsb
λ i  ⇒
match i with
TAppf _; _; TAppg _; _
⇒
f == "let" && g == "setjmp"
_
⇒
false
bs

Whether the instruction i is a local_alloc(Name, Size).

362Definition is_local_alloci : term : bool ≔
match i with
TAppf _; _
⇒
f == "local_alloc"
_
⇒
false

As opt.pl's optimize_pass/3 with the pass pass, which makes of a function's name, linkage, result, params and blocks its new blocks, in filc mode or not. A checked module and one with a local object are left as they are; else the context items go, as code_items/2 drops them, and the loc markers, as legacy_context/2 drops them. None where the Prolog pass fails or throws.

372Definition pass_modulepass : bool → listterm → listtblock → optionlisttblock m : term : optionterm ≔
match m with
TAppf TListitems
⇒
negbf == "module"
→
None
||
existsb
λ it  ⇒
existsb
λ b  ⇒
match block_partsb with
Some_, insts, _
⇒
existsbis_local_alloc insts
None
⇒
false
items
→
Somem
else
let filc ≔ module_filcitems in
option_mapλits ⇒ TApp"module" TListits
λ it  ⇒
match it with
TApph xs
⇒
h == "func"
→
match xs with
name; lk; ret; TListparams; TListblocks
⇒
let* bs ≔ map_optionterm_block blocks in
let bs ≔ mapλb ⇒ mkTBlocktb_labelb tb_phisb filterλi ⇒ negbis_loci tb_instsb tb_jumpb bs in
let* bs′ ≔ passfilc params bs in
SomeTApp"func" name; lk; ret; TListparams; TListmapblock_term bs′
_
⇒
None
h == "data"
→
arity4 xs
→
Someit
else
None
h == "alias"
→
arity3 xs
→
Someit
else
None
else
None
_
⇒
None
filterλit ⇒ negbis_contextit items
_
⇒
None