alias.pl
Address expressions for milestone 5: alias_facts/2 writes each address of a strict SSA function as a base plus a constant offset. The facts are not a no-alias or bounds proof.
Address facts
A fact addrClass, Base, Offset says the address is Base + Offset modulo 2^64, with Offset the signed 64-bit representative. In class p the capability is also the base's.
| Base | Names |
|---|---|
allocTemp | the current execution of that alloc's SSA definition, not all its loop iterations |
paramTemp | a parameter |
symbolName | a symbol |
valueTemp | an opaque SSA value: a load, call, cast, phi, or any other computed value |
Only same-class copies and additions and subtractions of a constant are followed. A w copy is not an address alias, even when its operand was an l.
What the facts do not say
Different bases may alias: parameters, symbols and opaque values need not name different objects. These facts alone justify neither removing a bounds check nor moving an access or allocation across control flow.
Facts is the assoc Temp -> addr(Class, Base, Offset), for the l/p values of Func if it is in strict SSA form, and otherwise empty. Base is alloc(Temp), param(Temp), symbol(Name), or value(Temp) for an opaque SSA value (including loads, calls, casts and phis). A missing fact means unknown, e.g. a cycle in unreachable code with no base to start from.
temp D of address class K is a parameter (param), an instruction (let(Op, Args)) or opaque.
as address_base/5, for an instruction.
as ins_base/6, for Op of Kind. An alloc and the copy of a symbol start their own bases, an add, sub or copy that offsets an address (address_offset/5) starts none, and every other instruction starts a value base.
as kind_base/7, for D a copy of V.
Source computes the same-class temp S plus Delta.
Facts is Facts0 with the addresses derived, directly or not, from Pending, the list of S-Addr whose users are still to be derived. Every derived definition has one source, so a definition is reached only once its source is known, regardless of layout. Phis are roots rather than followed around their cycles: they select a value from an earlier dynamic execution.
the user D of Edge has the address Addr plus Delta, in Facts and in front of Pending0. The offset wraps modulo 2^64 to its signed 64-bit representative.