Implement IR v2.0

[ironcev]

Motivation

Our current IR implementation has several hindering issues, most of them coming from how we deal with pointers and aggregates in the IR. The purpose of this tracking issue is to explain the current problems and their impact, list the agreed solution steps, and track their implementation.

Terminology

To disambiguate the term pointer, in the remaining part of this description we will consistently use the following terminology:

• Pointer for the IR TypeContent::Pointer
• raw pointer for the Sway raw_ptr type
• reference for the Sway &T type
• pointer as a synonym for both raw pointers and references.

Current Issues

• Pointer is conceptually seen as an equivalent for an aggregate type. It is assumed that whenever we encounter a Pointer in IR, it represents an aggregate. This assumption makes it impossible to formulate references and raw pointers as Pointers. (They are currently modeled as u64 which leads to various other issues explained below.) It also represents a semantic issue, because Pointers are not treated as values. E.g., in the compile_expression_to_value every pointer will be turned into a load, assuming that the Pointer itself cannot be a value, and that the value must be behind the Pointer.
• ptr_to_int does not check if the input argument is a Pointer. Anything can be turned into u64 and, later on, turned back into a Pointer by using int_to_ptr. This is a severe issue that led to a serious misuse, in which we pair ptr_to_int + int_to_ptr to obtain Pointers to SSA registers! Having "Pointers" to SSA registers is semantically wrong and makes the generated IR being semantically wrong for the most of the optimization pipeline, until it reaches demotion passes, which promote those SSA registers into memory making the previously obtained Pointers valid. Having semantically invalid IR all the way down to the final demotion steps is an issue in itself, but it also harms optimizations that usually bail out when encountering ptr_to_int instructions.
• Aggregates can be manipulated only in memory via get_elem_ptr since we don't have LLVM equivalents of insert/extractelement (which would allow us to manipulate aggregates in SSA registers). This restriction on its own is not an issue. The issue is that we generate IR where aggregates are stored in SSA registers, and then use the ptr_to_int + int_to_ptr pairs described above to obtain a Pointer to SSA register (not memory!) containing the aggregate. The aggregate is then manipulated via get_elem_ptr as if it is in memory. Essentially, we have a semantically wrong mixture of get_elem_ptr and store and load attempting to simulate insert/extractvalue.
• It is not possible to take a reference to a non-aggregate function argument. Taking a reference to an aggregate function argument "works" but only by chance. It "works" because of the reasons explained above. We misuse the ptr_to_int + int_to_ptr pairs on an SSA function argument value (!!) generating essentially a semantically wrong IR, that gets "fixed" after the arg-demotion pass.
• Raw pointers and references are represented as u64s and not Pointers. This causes several issues. The use of ptr_to_int immediately marks pointees as escaping and hinders possible optimizations, because they do not necessarily need to escape the function scope. It also makes escape analysis difficult and in a general case impossible. E.g., every u64 argument or return value might actually be a pointer, and the only way to figure that out would be to check the usages. In a general case, even the local usage must not reveal that a u64 value passed around is actually a pointer. E.g., if a raw_ptr or a &T is passed as an argument and just forwarded to other functions, it will not be possible to spot, by just looking at the current function IR, that those u64 arguments actually represent pointers. Having pointers represented as u64 also makes writing optimizations harder to reason about and more error-prone. Current situation in IR optimizations is a paradoxical one. We strip the information about pointers away, by turning them into u64, and then try to recognize certain IR code patterns that would reveal to us, that those u64s are actually pointers.
• The IR depends on demotion passes to become semantically valid. The reasons are described above.
• Specifically, handling constants is problematic and also relies on the const-demotion pass. This makes it impossible to take pointers on global constants in a semantically correct way. It also generates semantically invalid IR if the constants are aggregates whose elements are accessed. When obtaining a pointer to a global constant, we should always get the same address, no matter in which function the pointer is taken. The way we currently deal with global constants, and with constants in general, breaks this semantics. Although we can add global constants to a Module via add_global_constant, those constants are, later on, not retrieved in IR as Pointers to global constants but rather as Values of ValueDatum::Constant. This essentially causes issues conceptually the same as those explained in the above points. Until we reach the const-demotion pass, all constants are SSA values.
• We don't have a clear separation between general IR generation and optimization logic and those parts that are VM specific. E.g., the VM-independent logic of demotion passes, is currently mixed with either hardcoded FuelVM register size assumptions or directly depends on calling, e.g., FuelVM specific target_fuel module.

Agreed Solution

We were discussing several possibilities to solve the above issues. E.g., to introduce insert/extract_value instructions and shift their lowering to ASM, etc. The goal was to come up with an always consistent IR code that is simple to reason about, while being pragmatic when it comes to implementation costs of the IR restructuring.

We've decided to do the following:

• Aggregate manipulation will still be possible only via get_elem_ptr. But the aggregates will be guaranteed to be in memory in order to be manipulated.
• The inital IR will have all expressions compiled to memory. mem2reg will turn them into SSA values, as it is now. This will ensure that all aggregates consistently stay in memory until they reach the SROA pass (or promotion passes which we can add in the future). Essentially, we are moving from having aggregates in registers and demoting them, to having them in memory and promoting them.
• IR validator will check that ptr_to_int is used only on Pointers. This will forbid any misuse. Also, once we represent pointers as Pointers (see below), we do not expect to have ptr_to_int to be used so prominently at all.
• Function arguments will be copied to function locals and the use of arguments in the function body will be replaced with the use of locals. This will ensure proper taking of pointers to function arguments. Clearly, if no pointers are taken, optimization passes will remove the local copies of arguments and use the original arguments directly.
• Raw pointers and references will be represented as Pointers. It will be possible to take __addr_of on an arbitrary type, and not only an aggregates as it is now.
• A new operation get_global_const will be introduced to access global constants. It will return a Pointer to the constant similarly to get_local and get_config. A promotion pass can still promote a global constant if there are no pointers taken to it, and if the promotion is valuable (e.g., having a constant that fits into an immediate value).
• A very simple framework will be introduced to separate the general part of the optimization passes from VM-specific details like the register size or demotion logic.

The impact of the planned changes on the IR is significant, both in the semantics and implementation, and spread throughout the whole IR code base. This, IMO, justifies "branding" the planned changes as IR v2.0. Better code-names are welcome 😄