# REP60 Implicit Cast Elision
**Status**: `✅ DONE`
## What is this
Due to type-safety and legalization reasons, the clift code generated by the decompilation pipeline often includes many casts that cannot be optimized away.
However, many of such casts could be omitted when emitting C code from clift, because the C language would implicitly perform such casts according to the language rules, even if they are not emitted explicitly as casts by the backend.
Below you can find a few examples, where we assume the C implementation has an `int` with size 32-bits.
This is important because while clift only has explicitly-sized integer types, C doesn't, and the size of an `int` depends on the implementation.
In the remainder of this document we always assume `int` is 32-bits and `long` (and `long long`) is 64-bits.
1. ```c
uint8_t x;
(int32_t)(uint32_t)x;
// the uint32_t cast could be silenced, because the C language
// would do that implicitly, so it could be emitted in C as
(int32_t)x;
```
2. ```c
uint8_t x;
uint8_t a;
uint8_t b;
uint8_t c;
x = a / (b + c);
// gets legalized to
x = (uint8_t)(
((uint32_t)a)
/
(uint32_t)(uint8_t)((uint32_t)b + (uint32_t)c)
);
// but we would still like to emit it in C as
x = a / (b + c);
```
This REP designs an algorithm for implicit cast elision, that can mark the casts with an `IsImplicit` attribute so that the C backend knows it can skip printing them.
## Why is this important
It's important because we want to keep the number of casts we emit C low, for readability, without changing the semantic.
## Preliminary considerations
### On legalization
All the rest of the document assumes we're dealing with legalized clift IR and guarantees that we never generate illegal IR from that.
The latter property is trivial, given that the transformations are only adding `IsImplicit` attributes to the casts.
### On notation
Using C to make examples is nice because it's faster to write than clift, and it's not bound to clift syntax, so everyone reading this document can follow.
But unfortunately C casts only show the target type, while casts on clift are types both on the operand and on the result type.
In the rest of this document I'll occasionally use a special function-like notation for casts in C, with explicit types as part of the name.
This allows for writing C-like code without losing the precision of clift types.
Example:
```c
i32_to_u32(x); // for a clift bitcast
u32_to_u64(x); // for a clift zero extension
i32_to_i64(x); // for a clift sign extension
i64_to_i32(x); // for a clift truncation (same for unsigned)
```
In clift, also operators are typed (e.g. we have signed-32-bits add and unsigned-64-bits add).
We don't have this in C, so I will occasionally annotate operators with a suffix to clarify what bit-size and signedness where it's relevant.
Example:
```c
uint8_t x, y, z;
// Both the assignment and the add are unsigned.
// The assignment is 8-bit wide.
// The add is 32-bit wide.
x =_u8 u32_to_u8(u8_to_u32(y) +_u32 u8_to_u32(z))
```
### On scalar and primitive kinds
Clift has several types, but here we're dealing only with casts that involve only integer types.
Primitive clift integers get printed in C in various ways. But in the `primitives.h` that is required for recompilation, we `typedef` all integer primitives that are not `Signed` to the equivalent `uint*_t` and the `Signed` integer primitives to `int*_t`, always taking size in consideration.
This means that the rest of the conversation here can only focus on `unsigned` vs `signed` and nothing else, because whenever we add one of the other primitive integers in the mix it just falls back to `unsigned` and the rest of the logic and the reasoning is the same.
### Separation of concerns with *cast elimination* and *cast collapsing*
There are some situations where a cast che be eliminated entirely, without marking with the `IsImplicit` attribute.
Example 1 above is one.
Another example are consecutive bitcasts of any kind.
These cases should not be handled by implicit cast elision.
Instead, they should be enforced by a dedicated optimization, that is already part of [REP52](https://pad.rev.ng/hSR934hwSYGpk02fQjSKJA).
The rest of this document just assumes that such casts have been removed/collapsed by a separate optimization that we don't deal with here.
This likely means that, among other optimizations layed out in REP52, *Cast elimination* and *Cast collapsing* should become part of *canonicalization*.
They are both cheap, local and converge quickly.
In this way in this REP we can concern ourselves only with canonical IR, which reduces the number of corner cases we have to deal with.
### About `TargetCImplementation` vs `TargetABI`
As of now, throughout the `revng` codebase we extensively use the `TargetCImplementation`.
That concept should be replaced by the concept of `TargetABI` as described in [REP34](https://pad.rev.ng/1OQ7Z42KQuenwdj0q3aioA#) that has only been partly implemented.
The rest of the design talks about `TargetABI` as if it was already implemented, but in order to implement this REP it is necessary to first implement the missing pieces of REP34, namely
1. Ditching `TargetCImplementation` in favor of `TargetABI`
2. The `Clifter`, **only in function bodies** needs to stop mindlessly importing pointer types using the `PointerSize` of the input binary architecture, and use the pointer size dictated by LLVM's `DataLayout`, that we can assume is set to the largest pointer size among the `model::Architecture`s in the input binary (for now it's just one, but whenever we switch to multi binary this will continue to hold). More details in [REP34's section about the Clifter](https://pad.rev.ng/1OQ7Z42KQuenwdj0q3aioA#Clifter)
3. `Legalization` should attach to an attribute to the Clift `mlir.module` that embeds the `TargetABI` so that it's possible for Implicit Cast Elision to use that without looking at the Model.
These tasks are part of the *Roadmap* section of this REP at the end of this document.
### Design goals
* Try to keep the algorithm simple and local as possible, without having to look at uses.
* In particular, try to avoid dataflow analysis.
* If it helps keeping the algorithm simple, explicitly strive to target casts that were emitted by *legalization* and not necessarily the most general cases.
## Design
### Problem statement
The underlying problem we're trying to solve here is caused by the fact that clift does not have overloaded operators, while C has them.
For instance, `+` in clift is strongly typed, and all operand and result type are guaranteed to always have the same type. So `+` is never just `+` in clift, but its `+_i32` or `+_u64` (and others) depending on the case.
In C, instead, `+` is overloaded. The language, depending on the context, decides how to resolve the overload to `+_i32` or `+_u64` or what have you.
When emitting C from clift, as long and we don't mark any cast as implicit all the operators are guaranteed to have their overload resolution converge to the same operator we have on clift.
The very moment we start marking casts as implicit on operands, the overload resolution could change, thus yielding a semantic difference.
So the algorithm we use to decide if a cast can be marked implicit relies on the same reasoning.
### Algorithm
This algorithm goal is to mark the casts on operands of `ExpressionOp`s to be implicit, if it's possible to do so without changing the semantics. Other type of operations are not considered.
For each `ExpressionOp` we need to define a function, that we call *overload resolutor*.
The *overload resolutor* for an `ExpressionOp` takes a number of input types equal to the number of operands, and returns the result type of overload resolution on that operand.
For example, given an `AddOp` (or any other binary arithmetic operator), assuming we are given a `TargetABI`, the function applies the rules of the C standard to figure out if the C overload resolution would pick e.g. `+_i32`, `+_u64` or what else.
On the other hand, given a `ReturnOp`, its overload resolutor is constant, and always returns the return type the parent function. This reflects the fact that, in C, a statement such as `return X;` always implicitly casts `X` to the function return type, no matter what's the type of `X`.
Other notable examples are e.g. `?` where the overload resolutor of the first operand always implicitly casts to `bool` (`uint8_t` in clift), or calls, where each actual argument being passed to the callee is casted to the type of the formal argument of the callee.
The same reasoning we do for `?` applies for `YieldOp` that are yielding an integer in a boolean evaluated context, i.e. basically just in conditions of `IfOp`.
In this case, the matching will have to be a tad more convoluted, because it's not enough to match the `YieldOp`, but the parent operation of the region we're yielding from will have to be taken into consideration. This is necessary to be able to elide casts to booleans in `if` conditions.
So, to determine if we can omit casts on operands for an `ExpressionOp`, we can use that `ExpressionOp`'s *overload resolutor*, to reason about what would happen if some of the casts on the operands are made implicit.
We start from the *target overload*, which is the overload we want to get picked in C even if we make some casts implicit. On clift, it's obvious what's the *target overload* because clift doesn't have operator overload and the "picked overload" is always uniquely determined by the common type of all the operands and the result.
Then we start iterating on each operand.
For each operand that is a cast, we skip through all the implicit casts.
If we find a non-implicit cast, we consider it for making it implicit.
To know the answer, we call the *overload resolutor* replacing the type of the n-th operand with the operand type of the non-implicit cast operand we are looking at.
If the *overload resolutor* still picks the *target overload*, we mark the cast as implicit, because we've just proved that making the cast implicit would not change semantc. Then proceed with the next operand.
Otherwise, if the *overload resolutor* picks an overload that is different than the *target overload*, making the cast implicit would change the semantic. So we don't mark it as implicit and move on to the next operand of `ExpressionOp`.
To put this in pseudocode:
```c++
auto OverloadResolutor = getOverloadResolutor(ExpressionOp);
clift::IntegerType TargetOverload = Expression.getResult().getType();
SmallVector<clift::IntegerType> OperandTypes;
for (mlir::Value Op : Espression.operands())
OperandTypes.push_back(skipImplicitCasts(Op.getType()));
for (auto &[Operand, Index] : llvm::enumerate(Expression.operands()) {
bool MarkedAsImplicit = false;
clift::CastOp Cast = dyn_cast<CastOp>(skipImplicitCasts(Operand));
while (Cast) {
revng_assert(not Cast.IsImplicit());
// This is the new operand type if we'd mark also Cast as implicit
clift::IntegerType SourceType = Cast.getOperand(0).getType();
std::swap(SourceType, OperandTypes.at(Index));
if (TargetOverload != OverloadResolutor(OperandTypes)) {
// The newly picked overload is not the same, swap back
// and go to the next operand
std::swap(SourceType, OperandTypes.at(Index));
break;
}
// Othwerise the swap is final, and we mark Cast as implicit.
// We also look at the operand of the cast that we just made implicit,
// to see if it's also a cast that could be made implicit.
markAsImplicit(Cast);
Cast = dyn_cast<CastOp>(skipImplicitCasts(Cast.getOperand(0)));
}
}
```
**Note:** this algorithm is sensible to the order of visitation of the operands. Changing what operand is condidered first can change the result. In the examples below there are notes to show when this can happen in practice.
### Successfull Example
Here's a typical pattern of casts that could be emitted by `Legalization`.
```c=
uint8_t x;
uint8_t a;
uint8_t b;
uint8_t c;
x=_u8 u32_to_u8( // <--- 4. implicit
u8_to_u32(a) // <--- 3. implicit
/_u32
(
u8_to_u32(b) // <--- 1. implicit
+_u32
u8_to_u32(c) // <--- 2. implicit
)
);
```
1. We start from the innermost `+_32`, at line 10.
* The `u8_to_u32(c)` cast at line 9 is marked implicit, because the sum is 32-bits, and the other operand is 32 bits, so marking it implicit doesn't change overload resolution.
* The `u8_to_u32(c)` cast at line 11 is marked implicit, because the sum is 32-bits. The other operand is now `uint8_t` because the cast at line 9 has been marked implicit. However, the overload resolutor for the addition can never yield `+_u8` even if both operands are `uint8_t`, because in the C implementation we're considering there isn't a 8-bits add, just an `int`-sized add (which we are assuming is 32-bits). So, overload resolution doesn't change and we can mark implicit also this cast.
3. Then we look at the `/_u32` at line 7. The `u8_to_u32(a)` cast at line 6 is marked implicit, because the division is 32-bits, and the other operand is also 32 bits, so marking the cast implicit does not change the overload resolution
4. Then we look at the assignment `=_u8` at line 5. Here we can also make the cast implicit because overload resolution of the assigmnet is dictated by the LHS that is also 8-bits.
so in practice this gets printed in C as:
```c
x = a / (b + c);
```
### Example where order or evaluation of operands affects the result
Here's a typical pattern of casts that could be emitted by `Legalization`.
```c=
uint64_t x;
uint32_t a;
uint32_t b;
x =_u64 (
u32_to_u64(a) // <--- 1. implicit
+_u64
u32_to_u64(b) // <--- 2. not implicit
);
```
In this test, the cast at line 8 is not marked as implicit because the operand at line 6 is considered first.
Given that the first operand has already been marked as implicit, marking also the second would change the overload resolution to `+_u32`.
If the algorithm considered the second operand first, it would have marked the other operand as implicit.
### Tests
This should be tested with `lit` and `FileCheck` on clift code.
## Roadmap
* [x] Extend collapsing to handle extend-then-truncate, to fold them into a single cast that just extends to the truncated value, or just truncates directly. This is in line with the general principle of [separation of concerns mentioned above](https://pad.rev.ng/TEeNUrauSsOGTpf6ErnpJw?both#Separation-of-concerns-with-cast-elimination-and-cast-collapsing).
* [x] Ensure that both *cast elimination* and *cast collapsing* from [REP52](https://pad.rev.ng/hSR934hwSYGpk02fQjSKJA) always run before implicit cast elision.
* [ ] Drop `TargetCImplementation` and replace it with `TargetABI` as explained in [REP34](https://pad.rev.ng/1OQ7Z42KQuenwdj0q3aioA#Clifter)
* [ ] In the `Clifter`, only in function bodies, ensure the pointer size is taken from `llvm::DataLayout`.
* [ ] In `Legalization`, attach an attribute to the `mlir.module` that embeds the `TargetABI`
* [x] Implement the oracle for overload resolution of operators
* [x] Implement the algorithm for deciding if a cast can be made implicit.
* [ ] In `verify` for casts
* [ ] if the `TargetABI` attribute is not set, don't accept any implicit cast (verification fails)
* [ ] if the `TargetABI` attribute is set, use the same logic of the *overload resolutor* to check each implicit cast. if using that logic that implici cast preserves semantics, then verify passes, otherwise it fails
* [ ] Test test test
## Discussion on rationale: global analysis that we want to avoid and solve via `TypeShrinking` instead
Note that currently `TypeShrinking` might emit some code that, given a certain target ABI, turns out to use operations that are not available in C (e.g., 8-bits add). This will lead to the following code:
```c
uint8_t x;
uint8_t a;
uint8_t b;
uint8_t c;
// all the following casts are emitted by legalization
// from an expression such as x =_u8 a /_u8 (b +_u8 c))
// that also turns the 8bit adds to 32bit adds
x =_u8 u32_to_u8( // implicit because x is u8
u8_to_u32(a) // implicit because RHS of add is u32
/_u32
u8_to_u32( // not implicit because LHS of outer add is made implicit, so u8
u32_to_u8( // not implicit
u8_to_u32(b) // <- implicit because RHS of add is u32
+_u32
// implicit because LHS of add is implicit but overload resolution still resolves to +_u32
// v
u8_to_u32(c)
)
)
);
```
However, this is not something that implicit cast elisions should address.
Instead, `TypeShrinking` should be prevented to emit such things, given a `TargetABI`.
This is similar to what LLVM does, disabling certain changes to the IR (`git grep -i isLegalInteger -- llvm/lib/Transforms/InstCombine/`).
If this is done, what we would actually see on clift is:
```c
// on clift
x =_u8 u32_to_u8( // <-- implicit because x is u8
u8_to_u32(a) // <-- implicit because RHS of add is u32
/_u32
// u8_to_u32( // <-- not emitted by legalization
// u32_to_u8( // <-- not emitted by legalization
u8_to_u32(b) // <-- implicit because RHS of add is u32
+_u32
// implicit because LHS of add is implicit but overload resolution still resolves to +_u32
// v
u8_to_u32(c)
//)
//)
);
// on C
x = a / (b + c)
```
It is true that in principle we might leave some other opportunities on the table, but they are going to be very rare and the whole thing is much simpler.
Also, if we do things properly in type shrinking, we should be able to promote also `a`, `b` and `c` to `uint32_t`, which then removes all the casts.
For this reason, global reasoning that tries to handle more complex examples but requires a full dataflow analysis is deemed out of scope.
## Open points
* I think at the moment legalization tries to be smart about boolean casts in boolean-tested contexts. should we avoid that?
* This document only deals with integer casts. Should we extend that to enums? Typedefs of integers? Or perhaps to non-integer primitives?
## Misc
* decay - `clift.decay`
* bitcast: any input/output types, but `verify` requires same size - `clift.bitcast`
* canonicalize should rewrite any int-to-int bitcast as an integer cast
* emitted in C as `bit_cast`
* c-style casts:
* integer casts: input/output types must be integer - `clift.intcast`
* if the size of operands is the same -> bitcast semantic
* if result size > operand size -> extend semantic (sign- or zero-extend depending on signedness of operand)
* if result size < operand size -> trunc semantic
* pointer casts
* ptr-to-int, int-to-ptr - `clift.intptrcast`
* pointer_extend, pointer_truncate - `clift.ptr_resize`
* ptr-to-ptr <- reinterpret - `clift.ptrcast`
* convert -> perhaps drop