# REP70: Local Value Type Refinement
###### tags: `clift` `vma` `types`
**Status:** `✅ DONE`
**PRs**: none yet
## What is this?
In Clift, we have lots of local variables and expressions with very poor types:
* Primitives: `generic*_t`, `pointer_or_number*t`, `number*_t`
* Arrays of bytes
* Opaque struct types
These are ugly to read, and tend to introduce noisy casts, that cannot be made implicit or otherwise optimized away.
This REP describes an heuristic that can be used to aggressively select more specific types for local variable and expressions, and to rewrite the Clift as such.
The goal is to change the IR so that it has:
* more local variables with more specific types (primary goal)
* ideally less casts (secondary goal)
## Caveats
### Size
Neither the heuristic for deciding the type, nor the transformation we perform at this stage, need to worry about the size of types.
The size will be taken care by other analyses that we have in our pipeline, and the IR we generate as a result of those analyses will just have types of the proper sizes.
The heuristic we apply at this stage for refining the type of an expression ignores that size, because the transformation just preserves such sizes.
### Variables and Values with "fixed" fixed type
There are some `mlir::Value`s used in clift functions whose types need to be kept fixed by this.
They are:
* functions
* globals
* arguments
* stack
The only one that is peculiar is `stack` because that's a local variable. The analysis will have to detect it and treat it differently than any other local variable thanks to its `handle` or its metadata stack type metadata.
### Function types
We don't care about function types at all here, since they are not value types.
### `const`
This document ignores `const`-ness on purpose, because the heuristic for deciding the *type kind* just reasons about the `const`-unqualified types. The rewrite logic will rewrite the IR using the *type kind* decided by the heuristic, but preserving the `const`-ness as it was originally on the input operations.
### Refinement vs cast reduction
The fact that the primary goal is type refinement and reducing the number of casts is only secondary means that we'll be adopting a greedy heuristic for type propagation.
Simple, single sweep, linear time with the number of operation in a function.
## Design
The transformation is designed as function-level analysis + transformation.
* The analysis has the goal to "discover" the real *type kind* for each expression and local variable in a clift function. It does it in an opinionated way, trying to refine as much as possible the type kind of each value.
* The transformation takes the result of the analysis and rewrites big chunks of dataflow in a clift function's body, so that the newly rewrited clift code has the actual types that the analysis decided.
### Partial order of types kinds
The analysis relies on a partial order imposed on the set of clift types such that `unwrapped_isa<ValueType>` and `not unwrapped_isa<PointerType>` (basically all types except `void`, function types, pointer types, and their typedefs).
```graphviz
digraph {
rankdir = BT
node [margin="0.4,0.1",shape=box,fontname=monospace]
bytearray[label="opaque_type?"]
bytearray->struct;
bytearray->union;
bytearray->generic;
struct[label="struct"]
tdstruct1[label="typedef\nstruct_1"]
tdstruct2[label="typedef\nstruct_2"]
struct->tdstruct1
struct->tdstruct2
union[label="union"]
tdunion1[label="typedef\nunion_1"]
tdunion2[label="typedef\nunion_2"]
union->tdunion1
union->tdunion2
generic[label="generic"]
tdgeneric1[label="typedef\ngeneric_1"]
tdgeneric2[label="typedef\ngeneric_2"]
generic->tdgeneric1
generic->tdgeneric2
tdgeneric1->pon
tdgeneric2->pon
pon[label="pointer_or_number"]
tdpon1[label="typedef\npointer_or_number_1"]
tdpon2[label="typedef\npointer_or_number_2"]
pon->tdpon1
pon->tdpon2
tdpon1->n
tdpon2->n
n[label="number"]
tdn1[label="typedef number_1"]
tdn2[label="typedef number_2"]
n->tdn1
n->tdn2
tdn1->u
tdn2->u
tdn1->s
tdn2->s
u[label="unsigned"]
uenum1[label="unsigned\nenum 1"]
uenum2[label="unsigned\nenum 2"]
tdu1[label="typedef\nunsigned 1"]
tdu2[label="typedef\nunsigned 2"]
u->uenum1
u->uenum2
u->tdu1
u->tdu2
s[label="signed"]
senum1[label="signed\nenum 1"]
senum2[label="signed\nenum 2"]
tds1[label="typedef\nsigned 1"]
tds2[label="typedef\nsigned 2"]
s->senum1
s->senum2
s->tds1
s->tds2
}
```
### Heuristic for type refinement
The heuristic for type refinement is pretty simple.
It needs to populate a map with a type kind from the set above for each operation in the clift function.
Some operations have a fixed type that cannot be refined because otherwise it would go out of sync with the model (see above).
Some operations have strong signedness semantics (signed/unsigned comparison, zext, sext, sdiv, udiv, srem, urem, perhaps others). These also have a fixed type that cannot be changed because it would change semantic.
For each value with fixed type T, we visit its uses, and for each use with fixed type, we visit the used value.
Basically, for each value with fixed type T, we visit its uses and their operands. For each such use or operand X we do the following
* if it's in the set of values with fixed types described above, we *don't refine and backtrack the visit*
* we take its type T1 and compare it with T
* if it's not comparable with T, we *don't refine and backtrack the visit*
* if it's comparable with T, we set type of X in the type refinement map to to the `max(T1, T)` according to the ordering described above
* if `max(T, T1) == T` we recur the visit on the unvisited neighbors (uses and operands) of X
* otherwise `max(T, T1) == T1`, there is nothing to upgrade or discover if we keep going so we backtrackt the visit
#### Type-information flow graph
A directed type information flow graph is formed based on data-flow by creation of edges from uses to their users. Note that this graph is conceptual, and does not need to be explicitly materialised.
1. Create nodes for:
* Each function parameter. (fixed type)
* The function return value. (fixed type)
* Global variables. (fixed type)
* Each local variable. (fixed type if marked with an attribute)
* Each expression operation.
2. Create edges to expression operands from their usees.
3. Invert the direction of any edge representing the first operand of an assignment (data flows *to* the operand).
4. Remove nodes representing bitcast operations and connect together their incoming and outgoing edges.
Implementation note: before running refinement and EFA until fixed point, a marker attribute is introduced for local variables with non-opaque type.
Starting from nodes with fixed type, the graph is visited in both directions in such a way that whenever any nodes reached in the forward direction remain unvisited, no nodes reached only in the reverse direction are visited.
:::warning
* [name=fez] this is more complex than just treating the graph as undirected without distinguishing forward and backward propagation. we should have motivating examples for this, that show that this additional complexity is beneficial in real world cases.
:::
```cpp
// Value might be enough, but if more information is needed,
// a struct or tuple can be used.
using NodeRef = mlir::Value;
// Get users of the specified node in the flow graph.
// This presents special behaviour for e.g. assignment and locals.
Range auto getFlowGraphUsers(NodeRef);
// Get usees of the specified node in the flow graph.
// This presents special behaviour for e.g. assignment and locals.
// N.d.Fez: 'usees' is really weird. I'd just to 'used' or 'uses'
Range auto getFlowGraphUsees(NodeRef);
// Most refined type for any node.
// All nodes whose type can change are represented by `mlir::Value`.
map<NodeRef, Type> NodeType;
set<NodeRef> ForwardQueue;
set<NodeRef> ReverseQueue; // N.d.Fez s/Reverse/Backward/g
// Collect all users of fixed nodes in ForwardQueue.
// Collect all usees of fixed nodes in ReverseQueue.
while (not (ForwardQueue.empty() and ReverseQueue.empty())) {
// Pick the higher priority queue:
auto &Q = ForwardQueue.empty() ? ReverseQueue : ForwardQueue;
auto N = Q.pop();
auto T = NodeType.try_emplace(N, N.type()).first->second;
// Visit users (not usees)
for (auto U : getFlowGraphUsers(N)) {
auto [I, Inserted] = NodeType.try_emplace(U);
if (Inserted or isMoreRefined(T, I->second)) {
I->second = T;
ForwardQueue.insert(U);
}
}
// Visit usees (not users)
for (auto U : getFlowGraphUsees(N)) {
auto [I, Inserted] = NodeType.try_emplace(U);
if (Inserted or isMoreRefined(T, I->second)) {
I->second = T;
ReverseQueue.insert(U, T);
}
}
}
```
Everything must be deterministic, otherwise different runs of the same algorithm on the same clift code may converge to a different solution depending which values, operands or uses we visit first.
#### Why prefer forward propagation?
Picking a single direction produces more predictable results.
This is a simplified example. Here we can see how, if both flow directions are considered equal, the variable `y` can be unpredictably refined as either `int32_t` or `uint32_t`.
```c
int32_t f(uint32_t x) {
generic32_t y = x;
return y;
}
```
In larger examples it is likely that a small change in typing may cause unpredictable changes in the typing of many variables.
### Transformation
After the heuristic terminates, we have a map that tells us the type kind of each local variable and expression in our clift function.
We start from the `mlir::Value`s whose type hasn't been changed by the type refinement heuristic, and we rewrite first the local variables, and then all the expressions whose type changed.
Each node whose type has changed (an entry exists in the `NodeType` map) is visited. The visit order has no significance.
```cpp
// Returns the type of a use-def relation, accounting for
// changes to-be-applied based on the heuristic result.
mlir::Type getUseType(NodeRef Usee, NodeRef User);
// Creates a bit-cast operation between the usee and user,
// converting to the specified new type.
// If a bit-cast already exists in between, its type can be changed instead.
void insertCastBetween(NodeRef Usee, NodeRef User, mlir::Type NewType);
for (auto [Node, Type] : NodeType) {
// Visit users (not usees)
for (auto U : getUsersIgnoringBitCasts(Node)) {
auto UseType = getUseType(U, Node);
if (UseType != Type)
insertCastBetween(U, Node, UseType);
}
// Visit usees (not users)
for (auto U : getUseesIgnoringBitCasts(Node)) {
auto UseType = getUseType(Node, U);
if (UseType != Type)
insertCastBetween(Node, U, UseType);
}
Node.setType(Type);
}
```
#### Example 1
```c
// Current backend output
_ABI(SystemV_x86_64) int8_t *fmt_u(typedef_101 x, int8_t *s) {
generic64_t var_0 = (generic64_t) s;
if ((generic64_t) x) {
generic64_t var_1 = 0UL;
generic64_t var_2 = x;
generic64_t var_3;
generic64_t var_4;
do {
var_3 = var_2;
var_4 = (generic64_t) ((uint8_t *) s + 0xFFFFFFFFFFFFFFFFUL) - var_1;
var_2 = var_3 / 10UL;
*(generic8_t *) var_4 = (generic8_t) (var_3 % 10UL) | (generic8_t) 48U;
var_1 = var_1 + 1UL;
} while (!(generic8_t) (var_3 < 10UL));
var_0 = var_4;
}
return (int8_t *) var_0;
}
// After refinement
_ABI(SystemV_x86_64) int8_t *fmt_u(typedef_101 x, int8_t *s) {
int8_t *var_0 = s;
if ((generic64_t) x) {
generic64_t var_1 = 0UL;
typedef_101 var_2 = x;
typedef_101 var_3;
int8_t *var_4;
do {
var_3 = var_2;
var_4 = (int8_t *) ((uint8_t *) s + 0xFFFFFFFFFFFFFFFFUL) - var_1;
var_2 = var_3 / 10UL;
*(generic8_t *) var_4 = (generic8_t) (var_3 % 10UL) | (generic8_t) 48U;
var_1 = var_1 + 1UL;
} while (!(generic8_t) (var_3 < 10UL));
var_0 = var_4;
}
return var_0;
}
// After refinement and optimisation
_ABI(SystemV_x86_64) int8_t *fmt_u(typedef_101 x, int8_t *s) {
int8_t *var_0 = s;
if ((generic64_t) x) {
generic64_t var_1 = 0UL;
typedef_101 var_2 = x;
typedef_101 var_3;
int8_t *var_4;
do {
var_3 = var_2;
var_4 = (int8_t *) ((uint8_t *) s + 0xFFFFFFFFFFFFFFFFUL) - var_1;
var_2 = var_3 / 10UL;
*var_4 = (generic8_t) (var_3 % 10UL) | (generic8_t) 48U;
var_1 = var_1 + 1UL;
} while (!(generic8_t) (var_3 < 10UL));
var_0 = var_4;
}
return var_0;
}
```
#### Example 2
```c
// Current backend output
_ABI(SystemV_x86_64) int32_t __lockfile(FILE_2 *f) {
generic32_t var_0 = *(generic32_t *) ((uint8_t *) *(generic64_t *) NULL + 56UL);
generic32_t var_1 = *(generic32_t *) &f->lock;
generic32_t var_2 = 0U;
if (var_1 != var_0) {
generic32_t var_3 = var_1 ? var_1 : var_0;
f->lock = var_3;
var_2 = 1U;
if (var_1) {
generic32_t var_4 = var_1;
do {
__wait(&f->lock, &f->waiters, var_4, 1);
var_4 = *(generic32_t *) &f->lock;
generic32_t var_5 = var_4 ? var_4 : var_0;
f->lock = var_5;
} while (var_4);
var_2 = 1U;
}
}
return var_2;
}
// After refinement
_ABI(SystemV_x86_64) int32_t __lockfile(FILE_2 *f) {
typedef_384 var_0 = *(generic32_t *) ((uint8_t *) *(generic64_t *) NULL + 56UL);
typedef_384 var_1 = f->lock;
int32_t var_2 = 0U;
if (var_1 != var_0) {
typedef_384 var_3 = var_1 ? var_1 : var_0;
f->lock = var_3;
var_2 = 1U;
if (var_1) {
typedef_384 var_4 = var_1;
do {
__wait(&f->lock, &f->waiters, var_4, 1);
var_4 = f->lock;
typedef_384 var_5 = var_4 ? var_4 : var_0;
f->lock = var_5;
} while (var_4);
var_2 = 1U;
}
}
return var_2;
}
```
### Pipeline integration
From the standpoint of the pipeline, we want this transform to run at fixed point with `EmitFieldAccesses`, because we expect them to interact positively to progressively discover more types and progressively enable more type traversals to be solved better by `EmitFieldAccesses`.
The rewrite described here shouldn't rewrite field accesses and array accesses operations, nor any other operations that would change semantic in a rewrite (think sign extension vs zero extension, or signed comparison vs unsigned comparison).
### Tests
* Type refinement should be unit tested in isolation
* We should also unit test simple cases where this new transform and emit field accesses run at fixed point.
## Roadmap
* [ ] Implement type refinement
* [ ] Unit tests
* [ ] Implement type punning transformations
* [ ] Integrate in the pipeline, ensuring that `EmitFieldAccesses` and the new pass run at fixed-point.
* [ ] Unit test the scenario where they run at fixed point.
## Open points
* Type information flow in operations such as comparisons and the right operand of a shift. There is no type information flow between the operand and the result, but does the use have a "fixed"-type influence on that operand?
* ok to split the node
* ok to make the split part fixed
* Type information flow in expression regions of statements, such as in control flow conditions. Introducing a boolean type and explicit boolean-test operations would simplify this.
* control flow conditions are *not* treated as fixed type boolean nodes for now
* we only have advantages from treating them as booleans if we have first-class-citizen boolean types both on the model *and* in clift, and we can promote a local variable's type to e.g. `bool64_t`.
* suspend discussion on clift 1-bit booleans for now, but very likely to be needed for C QA reasons very soon
```c
void f(generic64_t x, generic64_t y) {
bool64_t z = x == y;
if (z)
do_something();
}
```
* Type information flow through casts other than bit-casts, such as integer extensions and truncations?
* trunc, sign ext, zero ext
* for now treat them as if they don't propagate anything
* let's think about it and try to do something sensible only if the output sucks
* in the long term, handling them will be made obsolete by the new type recovery and type shrinking
* decay, conversion don't matter
* bitcast is already handled
`-2` - `0xfffffffffffffffe` - `0xfffffffe`
```c
generic32_t f(int64_t x) {
generic32_t y = x;
// should we refine to: int32_t y = x;
return y + y;
}
```
```c
int32_t f(generic64_t x) {
generic64_t y = x + x;
// should we refine to: int64_t y = x + x;
return y;
}
```
```graphviz
digraph {
x -> cast
cast -> y
cast [label="(int32_t)"]
}
```
```c
generic64_t f () {
generic64_t x;
generic64_t y;
g(y);
(int64_t)x << -1;
return (int64_t)x >> y;
}
```
```graphviz
digraph {
x -> ">>"
y -> ">>-RHS";
">>" -> return
}
```
```graphviz
digraph {
x -> "<<"
y
"<<" -> user
}
```