Feature: Reference values by instructions

[julian-hartl]

Feature Proposal: Reference values by instructions

Background

Currently, a value, that is produced by an instruction, is called a virtual register or abbreviatedvreg and has its own data structure. However, this seems unnecessary due to the fact that the intermediate representation is in ssa form, meaning that each variable is defined exactly once and therefore by exactly one instruction.

Objective

The objective is to remove unnecessary mappings from virtual registers to their defining instructions, reduce complexity and make the ir more intuitive.

Proposed Solution

New terminology

Value

The solution is relatively straight forward. We need to replace every use of a virtual register by its defining instruction. However, we can't simply just replace every use of VReg with InstrId because basic block arguments are virtual registers, but they are not defined by an instruction. Therefore we need to introduce a new type called Value. It could look something like this:

enum Value {
    Instr(InstrId),
    BBArg(BBArgId)
}

Grammar for a value

There won't actually be a grammar rule for a value, because a value can either be an instruction id or a basic block argument id.

Grammar InstrId

InstrId -> '%' (Identifier | UnsignedNumber)

This will allow numerical, but also alphabetical symbols for instruction ids.

Grammar BBArgId

BBArgId -> '$' (Identifier | UnsignedNumber)

Basic Block Labels

To ensure consistency in naming things, we should also allow naming basic block labels.

Grammar for Basic Block Labels

BBLabel -> Identifier | ('bb' UnsignedNumber)

Implicitly defined values

If values are defined by instructions, every instruction should produce a value. This means that a value produced by an instruction does not need to be assigned a specific identifier, but it can be inferred from its linear position in the program. The same goes for basic block arguments. E.g.

func i32 @src(i32) {
bb0(i32):
  add i32 $0, 1;
  add i32 %0, 8;
  ret i32 %1;  
}

would be a valid program with implicitly defined values. This is nice for brevity and compactness of programs, but it can make them hard to read. The program from above could be rewritten as:

func i32 @src(i32) {
bb0(i32 x):
  b = add i32 %x, 1;
  %1 = add i32 %b, 8;
  ret i32 %1;  
}

Note that the second defined value still has the index 1 and not 0 as another instruction was defined previously. This makes it really easy to parse programs in text form, because we can just take the numerical identifier and convert it into an index.

Detailed Implementation Steps

• Step 1: Description of the first step.
• Step 2: Description of the second step.
• Step 3: Description of the third step.
• Add more steps as necessary.

Potential Challenges and Considerations

• Basic block arguments: Basic block arguments are not directly produced by instructions and can therefore not be referenced by one. However, it would make sense to introduce a separate new type called BasicBlockArgument that stores additional information, such as the type.