c_lower.pl
Lowering from C to IR (milestone 4b), in the style of cproc: it turns the parsed translation unit into an IR module for the Fil-C backend.
Every local variable and parameter lives in an alloc'd object, and the allocs are hoisted into the entry block; with -O, promote turns them into temporaries. Pointers are class p, so the output is a Fil-C module.
Expressions are lowered from c_types' typed trees (elaborate/3). The tree says what each expression is and what its operands are converted to, and the elaborator has checked C's constraints, so lowering only translates: lower//3 for values, place//3 for objects and functions.
A narrow integer (char, short, bool) is always held sign- or zero-extended to 32 bits in a w, so conversions only extend when the source type has values the target cannot represent.
Values
| Value | Is |
|---|---|
vValue, Type | an rvalue: Value is an IR value, Type a C type |
lvAddr, Type | an object at Addr, a p value: an lvalue, or a member of a struct rvalue |
fdCallee, Type | a function designator; Callee is an IR value, globalSymbol for a named function |
State
The lowering nonterminals describe a one-element list holding the state, accessed through the semicontext nonterminals state//1 and state//2 and called with phrase/3 at the entry points. The state is stEnv, Cur, Insts, Blocks, N, Labels, Cases, Allocs:
| Field | Is |
|---|---|
| Env | the c_types environment eOrds, Tags, Defs, Next |
| Cur | curLabel, Phis, the open block, or none after a jump; dead code then opens an unreachable block |
| Insts, Blocks | reversed instructions and blocks, temporarily paired with origin IDs |
| Allocs | buildRevAllocs, ActiveOrigins, OriginCounter, RevRecords, Indexes; independent of executable names |
| N | the counter for fresh temporaries and labels |
| Labels | an assoc from C goto labels to IR labels |
| Cases | the enclosing switch's caseValue, Label and defaultLabel |
The context argument Ctx is ctxFunction, ReturnType, Break, Continue, Loc, where Break and Continue are someLabel, or none outside a loop or switch.
The environment
Besides what c_types keeps there, the environment's Defs hold:
gdefSymbol: a global definition;litSymbol: a string literal;deferredSymbol: a static inline function, lowered only if something refers to it.
Next numbers string and compound literals as well as struct ids.
Variable names
| Name | Is |
|---|---|
| State0, State | st/8 terms |
| Env0 ... Env | the environment |
| Ctx | the context |
| Loc | a source location |
| R | a v, lv or fd value term; Value0 is one before conversion |
| V | an IR value |
| L-prefixed names | IR labels |
| Ebs | eightbytes, ebOffset, Bytes, Class |
| S0 ... S | sEnv, Chunks, End in the static initializer predicates |
Module is the IR module of the top-level Items from c_parse: module(Funcs) with the functions followed by the data of every global and string literal. Throws a semantic error for C that nanofil cannot lower.
C99 6.7.4: an inline body is an external definition unless ALL file-scope declarations are inline without extern. Inspect the whole translation unit: even a declaration after the body changes emission.
GNU inline reverses the C99 rule: an extern inline body is never the external definition, while a plain inline body is. The parser retains both spellings in the balanced tokens of specifier and suffix attrs.
with_used_inlines(+Funcs0, +Env0, -Items): Items is Funcs0, then every deferred static inline function they refer to, directly or through one another, then the global data. A static inline function is lowered only if something refers to it, as clang emits it only then; headers are full of ones nanofil cannot lower. Lowering one can refer to more, so this iterates until no new symbol turns up.
some function or data item of Items refers to symbol Sym (nondet, with repeats).
Func is the deferred inline function Sym, lowered in the scope it was defined in.
Environment
Env is Env0 with Key defined as Value.
Id is Env0's next number, which Env has moved past.
Top level
Funcs are the IR functions a top-level item defines now (a static inline is deferred).
throw a semantic error unless Expr is a nonzero constant.
Env binds the d/5 declaration Decl of a function or of an object with static storage, and defines the object unless it is an extern without an initializer.
Definitions of globals live in the environment's Defs under gdef(Symbol), string literals under lit(Symbol); both survive block scopes. A tentative definition (no initializer) does not replace one with an initializer.
string literal term Str can initialize an array of ElemType, and Elems are its elements. Str is str(Bytes) for a char array, or wstr(WideType, Values) for an integer array of its element's size.
Sym is a fresh symbol that Env defines as a file-scope compound literal, an unnamed static object.
Data are the data items of every global definition and string literal.
Data are the data items of the global definitions whose symbols are not in Done. Initializers can define more globals (file-scope compound literals), so this repeats until there are no new ones; Done lists the symbols already emitted.
Data is the data item of global definition G.
Functions
Func is the IR function for the definition of Name with body Body.
Class is the IR return class of a function returning RetType.
Params are the hidden parameters of a function returning RetType. A struct over 16 bytes is returned through a pointer the caller passes first, as clang does; the function itself returns nothing.
Names are the parameter names, each some(Name) or none, from the function's own declarator: the outermost func, since declarator types are built outermost first.
Params are the IR parameters, and each named one is stored into a local. A struct or union comes in one word per eightbyte.
and param_local(+Name, +Type, +P)//: a named parameter of Type, which came in as the words Values (eightbytes Ebs) or the temporary P, is stored into a local it is bound to; an unnamed one is dropped.
one fresh parameter per eightbyte; Values are their temporaries.
end the body; falling off the end returns as a bare return would.
State primitives
S is the state. state(-S0, +S)//: the state is S0 and becomes S. The semicontext of the one-element state list.
A zero-offset field or partial access is not the whole C object.
Keep the operation and resolved binding, not recursive typed trees.
append Inst with its active typed origin. These private wrappers disappear before c_module/2 returns; they are never IR.
end the current block with Jump.
begin block Label, falling through from a live current block.
begin block Label, reached only by jumps.
Label is the current block's label.
Label is the IR label of C label Name, made on first use.
Addr points at a new local object of Type, an alloc in the entry block.
Context
, switch_ctx(+Ctx0, +LBreak, -Ctx): Ctx is Ctx0 inside a loop or switch whose break jumps to LBreak and continue to LCont.
Statements
A lexical prepass gives each statement-expression boundary its AST path. Gotos may stay inside or leave boundaries, never enter one (including a sibling). Case dispatch must originate inside the same boundary. Keeping this separate from emission also checks forward gotos and unevaluated code.
Visit leaves before matching compound shapes: on Trealla an atom built by atom_chars/2 (e.g. the field name "label") can unify with label/2. Recursing into its unbound "body" would then grow regions indefinitely.
lower statement Stmt, an at(Loc, S) term; stmt_//2 lowers S itself.
Declaration and loop helpers update the enclosing source context.
a jump to the break or continue Target, some(Label); none is semantic error Error at Loc.
, local_decl(+Decl, +Ctx)//: lower block-scope declarations. Functions and extern objects are global, a static object is a global with a function-qualified name, anything else is a local slot.
throw a semantic error unless Type is a type a local object Name can have.
complete_array(+Type0, +Init, -Type, +Loc, +Env, +Whole): Type is Type0 with the size of an array of unknown size taken from its initializer Init, counting the entries each element takes with brace elision: {1, 2, 3, 4} is two elements of a struct {int a, b}. Whole is whole when an entry may be a struct expression that initializes a struct element whole (locals), none otherwise.
entry value V initializes a slot of type Type by itself, so no braces were elided. The final cut makes this semidet: the alternatives can overlap.
the switch dispatch, one comparison per case, then a jump to the default or LEnd.
compare Value with each case value of Pairs in turn, then jump to LDefault.
W is a w value that is nonzero exactly when scalar Value is.
Initializers
An initializer means its leaves: the assignments it makes to parts of an object, in the order C performs them, a later one overriding what an earlier one wrote.
zero(Off, Type) clear the object of Type at Off; a braced
list or a string literal first clears what
it initializes
val(Off, Type, N) the integer N, an element of a string literal
expr(Off, Type, Expr) the value of the expression Expr, converted
to Type: a scalar, or (locals) a whole structOffsets are from the start of the object. A local object stores its leaves; a static one turns them into data chunks. The walk over the entries also gives an array of unknown size its length (complete_array/6).
Leaves are what Init assigns to an object of Type. C = c(Env, Whole, Loc), with Whole as for complete_array/6.
the leaves of Init for the object of Type at Off. A scalar may be braced.
a val leaf for each of Values, consecutive elements of Type and Size from Off.
slots(+Type, +I, +Off, +Entries0, -Entries, +Max0, -Max, +C)//: the leaves of aggregate Type at Off from Entries0, the next undesignated entry going to slot I; a designator moves to its slot. Entries is what is left when the slots run out. Max is the larger of Max0 and one past the last slot initialized.
the leaves of entry value V for the slot of Type at Off. Either V initializes the slot by itself, or the slot's braces were elided and it takes the entries it needs from [V|Entries0], up to the next designator, which belongs to the enclosing list.
the undesignated entry for slot I of aggregate Type initializes the SlotType at Off. An array of unknown size has every slot; a union has only its first member.
designator Desig of aggregate Type names its slot I, the SlotType at Off; any member of a union.
Pre is the longest prefix of Entries without a designator, Post the rest. The final cut commits to the first split found, which ends Pre just before the first designator (or at the end).
initialize the local object of Type at Addr from Init, storing its leaves.
clear the whole object, since allocs are hoisted and a local inside a loop must be reinitialized on every pass.
zero Off..Size with the widest stores the alignment allows; bytes below Off are done. The cut in the second clause commits to the widest store that fits.
Expressions
GNU statement expressions load/decay their last expression before the block scope closes. A label on that statement does not hide its value.
R is the object or function an identifier bound to Binding designates. A global's address is copied into a temporary.
P points at member Field, of Type, of the struct or union at Addr.
R is v(V, Type), the value of Expr, arrays decayed, lvalues loaded, lowered from its typed tree (c_types' elaborate/3). Full expressions are judged first (judged//2), which diagnoses one that cannot be typed.
lower(+XV, +Ctx, -R)//: R is v(V, Type), the value whose typed tree is XV. Types are unqualified, as code generation has them; a type name the source writes (a cast's, va_arg's, sizeof's) is read again by type_name/4, which refuses one nanofil does not support.
R is Value0 converted to Type, as assignment and casts convert, the elaborator having judged that they may: to void it is nothing, a struct or union stays its address.
R is the value of type U stored at Addr: a struct or union stands for its address.
R, of pointer type T, points at the object or function P. A function's address is copied into a temp; setjmp's has none, since it is an intrinsic.
place(+X, +Ctx, -P)//: P is lv(Addr, Type), the object that typed tree X designates, or fd(Callee, Type) for a function.
A compound literal is an unnamed local, initialized where it appears.
An object is read and written through its place: lv(Addr, Type), or bits(Addr, Type, Pos, W), a bit-field of W bits from bit Pos of the Type at Addr. A bit-field is read by shifting it to the bottom of its unit, extended by its type's sign, and written by merging it into the unit; its value has its promoted type (bitfield_promotion/3).
R is the value, of type U, of the object at place P.
R is the scalar value at place P.
store Value0, converted, at place P; R is the value stored.
R is the W-bit field at the top of V, of T's class, moved down and extended as T's sign says, of the bit-field's promoted type.
V is the scalar of Type loaded from Addr.
Class and load Op hold a scalar of Type: an integer narrower than 8 bytes is loaded extended into a w.
store value V of Type at Addr; a struct or union V is the address of the value, copied.
R is the value of a call of builtin Name, which no declaration shadows, on source arguments Args.
The generic builtins do NOT use the usual arithmetic conversions. Keep the exact result in two l limbs, then compare it with the stored value extended back to two limbs. 128 bits suffice for all supported integer operands (at most 64 bits), including unsigned 64-bit products.
Extension to l must explicitly truncate a w value first: int_convert can reuse an l temp after a cast to int, as w consumers ignore its top.
Size is sizeof(TypeName).
Type is the type TypeName names, as lowering uses it: a variably modified one (an array of non-constant size anywhere inside) is rejected, since its size expressions would have to be evaluated, side effects and all.
throw a semantic error if nanofil does not support Type (c_types' unsupported_type/3).
Conversions
R is v(V1, To), scalar Value0 = v(V, From) converted to scalar type To (or void). Callers check that the types are scalar first.
Float-to-integer instructions produce a full w/l; normalize narrow C destinations afterward, without ever routing an unsigned result via signed.
V1 is integer V of type From converted to type To, extended where the representation changes.
R is Value0, the value of Expr, converted to To as by assignment: a return value, an initializer or a builtin's argument. c_types' assigned/4 judges that it may be.
Operators
R is unary operator Op applied to Value0, converted as unary_operand/3 says.
R is binary operator Op applied to the values VA and VB, converted as binary_operands/6 says.
R, of type T, is Op applied to VA converted to CA and VB converted to CB. Pointer arithmetic scales by the element size. Direct ordered comparisons are essential: !(a < b) is not a >= b when either operand is NaN.
R is P + I or P - I, I scaled by the element size.
R is A - B in elements.
R is XA && XB (land) or XA || XB (lor), a phi of 0/1 over the short-circuit edges.
start block LJoin; R is the ?: result there, a phi of VA from LA and VB from LB.
Calls
A call (6.5.2.2) lowers from its tree, whose callee and arguments the elaborator has checked: the callee is a function, the arguments fit its arity and each converts to its parameter as by assignment.
Callee is the IR callee of function pointer XF: the function itself when XF is a function designator decayed, else a temp holding the pointer.
R is the result of calling Callee with IRArgs; setjmp and its kin are intrinsics.
IRArgs pass the arguments whose trees are XArgs. A struct argument goes as one word per eightbyte; arguments past the prototype get the default promotions.
R is the result of a call returning a struct: its words land in a fresh local, or the callee writes the local through the sret pointer.
V is call result V0 of Type, a narrow one re-extended: nothing guarantees the callee did.
Struct values
A struct or union rvalue is v(Addr, T): Addr points at storage holding the value, a variable's or a temporary's. Copies, arguments and returns go an eightbyte at a time (eb(Offset, Bytes, Class)): class p if a pointer starts there, so its capability is copied with load(p) and store(p, ...), else l, with a short last eightbyte moved in 4-, 2- and 1-byte pieces. A value of at most 16 bytes is passed as one word per eightbyte, as clang does; a larger return goes through an sret pointer.
Ebs are the eightbytes of Type.
Offs0-Offs is the difference list of the offsets, from Base, where Type holds pointers.
Ebs are the eightbytes in which a struct or union argument of Type is passed.
Shape is how a struct or union of Type is returned: sret, or words(Eightbytes).
copy the object of Type at Src to Dst, an eightbyte at a time.
Pieces are N bytes from offset Off as p(Offset, Bytes, Load, Store), widest first. The cut after the member commits to the widest piece that fits.
Words are the words of the value at Addr, one per eightbyte.
W is Acc0 (none at first) or'd with each of Pieces loaded from P and shifted into place.
store Words, one per eightbyte, into the object at Addr.
Static initializers
static_items(+Type, +Init, +Loc, +Env0, -Env, -Items): the data items of a global of type Type. Each leaf of Init becomes a chunk chunk(Offset, Bytes, Item), a later one replacing an earlier one at the same offset, then the gaps are zero-filled. A pointer is item(p, sym(S, Off)); string literals in initializers become data of their own.
ByOffset maps Chunk's offset to Chunk, replacing any earlier one there.
Items are the items of Chunks, sorted by offset, with zero(N) filling the gaps from Pos to Size.
Chunk holds integer V of Type at Off.
static_leaf(+Loc, +Leaf, +S0, -S): S = s(Env, Chunks, End) adds the chunk of Leaf to the reversed Chunks of S0; End is where the chunks end so far. A zero leaf drops the chunks it covers, which only a designator that goes back can have made.
Chunks adds to Chunks0 the byte at offset Byte with its bits of the W-bit field V, starting at bit Start, merged into the bits an earlier bit-field put there.
Chunk holds the constant value of Expr, of scalar Type, at Off.
address_constant(+XV, +Loc, +Env0, -Env, -R): the value tree XV is an address constant (C11 6.6p9), R = sym(Symbol, Offset), or a null pointer, R = null. It is the address of a static object or a function, perhaps cast, plus or minus an integer constant; string literals and compound literals become data of their own.
R is address constant R0 plus (add) or minus (sub) K elements of type Elem.
typed tree X designates a static object or a function at R = sym(Symbol, Offset).
member Field of struct or union SUType has Type and offset Off.