IR Design ‐ Instructions

This is part of the series that discusses what you must think about when deciding how to represent IRs.

• Part 1 - Virtual Registers

Linear IR

The discussion here is primarily for linear Intermediate Representations. By linear we mean that the instructions are organized into sequences that are logically executed one after the other. This is in contrast to graph IRs where instructions are organized as a graph and the order of execution is not sufficiently defined by the graph.

Organize Instructions Into Basic Blocks

For many algorithms we need to operate on the control flow graph. It is important to organize the instructions into Basic Blocks, where each BB encapsulates instructions that are executed sequentially. The final instruction in the BB must a jump to some other BB.

Control Flow Graph

The Basic Blocks should contain links to predecessor and successor BBs - this forms the Control Flow graph. The links are driven by the jump instructions that terminate each BB.

Instruction Operands

Instructions deal with values, some of those may be Virtual Registers, some Constants, and even Basic Blocks, for example in jump Instructions. We therefore create a type called Operand that represents values handled by an Instruction. Operands can have different subtypes (in an OO design, or an Operand can be a union or sumtype in non-OO languages) - where each subtype is for a specific type of value.

Instructions Define and Use Registers

From the optimization point of view, it is important to model the Instruction in such a way that we can easily handle following requirements:

• Does the instruction define a Register - i.e. assigns a value to it?
• Does it use Registers defined by other instructions
• Replace a register that is defined
• Replace a specific use of a Register - or replace all uses - a Register may be replaced by another Register or by something else such as a Constant.

Whether an Instruction defines a Register and/or uses Values including Registers depends on the Instruction type. So each Instruction type sets its own requirements, however, all Instructions satisfy the interface requirements above, so that the optimizer can treat each instruction uniformly.

Phis Are Special

Phi instructions also define a Register and use one or more Registers, but Phis do not have the same semantics as other instructions in many situations, such as when computing Liveness. So a consideration is how to model Phi instructions, whether they obey the general interface or have their own specialized interface. In EeZee language we give Phi instructions their own interface, which is similar to the general instruction but ensures that Phis cannot be erroneously manipulated by the optimizer. This has a trade off because there are scenarios where Phis do not require the special treatment.

Instructions Can Be Replaced

The optimizer must be able to:

• Identify an instruction
• Replace it with a new Instruction

Thus every Instruction must have an identity.