rocq/backend/Pizlonate.v
# Pizlonation
As pizlonate.pl's pizlonate_module/2: from the unchecked IR to the checked IR, the form the backend compiles. Each access at a p address becomes a check, whose class a result is the proven address, and the raw access that reads it; each pure pointer operation becomes a flight; and every edge to a block at or before its source in block order becomes a poll edge. The table at the head of pizlonate.pl gives each row.
The pass is on terms, as the Prolog one is, and for the same reason: it rewrites a handful of instruction forms and leaves every other term as it is, whatever it is. So a function with an instruction the model has no constructor for is pizlonated like any other, and Transport.v's decode_module then keeps it as its checked term (IOutside), the very term Prolog gives. The unchecked stage needs no inductive of its own.
What pizlonate.pl does besides is left out, because the module the backend compiles has no context items:
- the records of where each check and poll came from (
checked_origins/4,remap_sites/3); - the origins that
legacy_context/2makes ofloc(File, Line)markers. The markers themselves are dropped here, as there.
pizlonate_module gives None where pizlonate_module/2 fails or throws: an item, block or jump of no known shape, a jump to a label no block has, or two blocks of one function with one label. The gate (tests/pizlonate.sh) holds the result to the term nanofilpizlonate − terms prints.
String equality, written as Prolog's ==.
Small terms
Whether the term t is the atom a.
Whether the list xs has n terms: the arity of a compound.
The name d when the term t is tmp(D).
The size and alignment of an access
As narrow_type/3: the bytes of the narrow integer type a.
As cas_type/1 and cas_bytes/2: the bytes a cas of type t compares and swaps.
As the first answer of access_size_align/3: a load of type x or a store of width x accesses so many bytes at an address that must be so aligned: 8 for a pointer, whose capability is in the aux word of its 8-byte slot, the width for a cas, else 1. No x has two answers.
An access and its check
A list of memory effects, as pointer_memory_effects/2 writes it.
pointer_memory_effects(load, Es).
pointer_memory_effects(store, Es).
pointer_memory_effects(local_load, Es).
pointer_memory_effects(local_store, Es).
let(tmp(Q), a, check(0, Size, Rights, Align), [A]): the check of an access of size bytes at the address a, whose proof is q.
check_inst for a size and alignment that size_align gave.
let(tmp(Q), a, check_local(X, Off, Size, Rights, Align), []): the check of an access to the local x at the offset off.
let(D, p, raw_load_pointer(0, Es), [tmp(Q)]).
raw_store_pointer(0, V, tmp(Q), Es).
let(D, K, raw_load(T, 0), [tmp(Q)]).
raw_store(W, 0, V, tmp(Q)).
As checked_access/4, a clause for each row of pizlonate.pl's table: when the instruction i is an access, its check, defining tmp(Q), and its raw access, for the fresh name q it is given. None for an instruction that is not an access.
Flights
As flight_inst/2: the flight of the pure pointer operation i, which is add or sub of an offset, a copy of a temporary or a constant, or itop, which has no lower. A copy of a symbol calls its getter and stays as it is.
Fresh names
The name d when the term r is result(tmp(D), K).
As cfg.pl's inst_def/2: the names of the temporaries the instruction i defines; a call can define several.
The text of the name n when it could be a proof's name: an atom that begins chk.
As func_temp_names/3, kept to the names a fresh one could be: of the temporaries that the function with the parameters params and the blocks defines, as a parameter, a phi or an instruction's result, those whose name begins chk.
As fresh_name/4: the name chkI for the least I from n on that is not among names, and I + 1. Each name passed over is another of names, so a fuel of their number is enough: when it is spent, every one of them has been passed over.
Instructions
Whether the instruction i is a loc(File, Line) marker.
A step of checked_insts/11, in filc mode: the count of fresh names and the instructions so far, last first, with the instruction i after them: an access as its check and raw access (checked_access), a pure pointer operation as its flight (flight_inst), and any other as it is.
Jumps
As polled_target/4: the target l of a jump from the block at the index from: poll(L) when the block l is at or before it in block order (index), and l as it is when it is later, or is a poll edge already. None for a label no block has.
As polled_jump/4: the jump j that ends the block at the index from, with a poll edge for each target at or before it, so that every cycle of the function polls.
Functions
Each block's label with its place in block order, from i on, added to m. None when a term is not a block or two blocks have one label, where list_to_assoc/2 throws.
As pizlonated_blocks/7: the blocks bs, the first at the index i in block order, their loc markers dropped when drop is set, their instructions by inst_step in filc mode and their jumps by polled_jump. n counts the fresh names, across the blocks.
As pizlonated_item/4 for the function func(Name, Linkage, Ret, Params, Blocks).
The mode and the stage of a module
As ir.pl's pointer_inst/1: the instruction i makes, stores, passes or calls through a p value, or converts one.
The blocks of the item it when it is a function.
The instructions and the jump of the term b when it is a block.
As ir.pl's pointer_item/1: the item it has class p somewhere, or is an alias, a weak function, or read-only, weak, external or thread-local data, which only filc mode models.
As ir.pl's module_mode/2: the module of the items is in filc mode when an item is a pointer_item, or a function calls a symbol that no function of the module defines. A plain module's addresses are not Fil-C pointers.
As ir.pl's module_stage/2, on terms: the module of the items is in the checked stage when a function uses a word of it.
Modules
Whether the item it is a context(Name, Records).
As pizlonated_item/4: a function by pizlonated_func, data and an alias as they are.
As pizlonate_module/2, without the context items: the module m with every check explicit and a poll on every edge to a block at or before its source. In a plain module only the polls are added. The loc markers of an unchecked module are dropped, as legacy_context/2 drops them; a checked module keeps its own.
Examples
A load: a read check of the type's size, then the raw load of the proven address.
Proof 1 step Qed
A pointer store: a write check of 8 bytes at an 8-aligned address, then the raw store with the store's effects.
Proof 1 step Qed
A pointer's offset is a flight of its address and its lower.
Proof 1 step Qed
A fresh name passes over the names the function defines.
Proof 1 step Qed
A loop: the back edge polls, the forward edge does not, and the load in a module with a pointer gets its check.