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 asjump_succs/2sorts 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).
String equality, written as Prolog's ==.
Blocks
A block block(Label, Phis, Insts, Jump) taken apart.
| 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.
The term of the block b.
The name d when the term p is phi(tmp(D), K, Args).
The name d when the term p is param(K, tmp(D)).
The terms of a list term, none for any other term.
The pair when the term t is A − B.
The graph
As edge_label/2: the label a jump's target t names, which is the label itself or poll(L).
As jump_succs(Jump, Succs): the ordset of the labels the jump j can go to. None for a term that is no jump.
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.
The labels of the graph g that the entry reaches, as a set.
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.
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).
Uses
As temps(Values, Names): the ordset of the names of the temporaries among the values vs.
The value when the term a is arg(K, V).
The value when the term p is Reg − V, an input of an asm_fixed.
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.
As jump_uses(Jump, Uses): the ordset of the temporaries the jump j reads.
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.
As def_counts(Func, Counts): how many definitions each temporary has, among the params, the phis and the instructions of the blocks bs.
Whether some temporary of the function has two definitions.
Strict SSA
The terms of xs, each with its position from n.
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.
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.
Functions
As ir.pl's setjmp_func/1: some block of bs calls setjmp.
Whether the instruction i is a local_alloc(Name, Size).
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.