IR-code

The purpose of an intermediate representation (IR) of a program is to decouple the implementation of a front-end from the implementation of a back-end. That is, front ends generate IR-code, optimizers optimize this code and lastly backends transform it into machine code or something else.

A good IR has several characteristics:

  • It should be simple enough for front-ends to generate code.
  • It should be rich enough to exploit the target instructions best.

The IR in the ppci.ir module has the following properties:

  • It is static single assignment form. Meaning a value can only be assigned once, and is then never changed. This has several advantages.
  • It contains only basic types. Structures, arrays and void types are not represented.

Top level structure

The IR-code is implemented in the ir package.

class ppci.ir.Module(name)

Container unit for variables and functions.

add_variable(variable)

Add a variable to this module

functions

Get all functions of this module

variables

Get all variables of this module

class ppci.ir.Variable(name, amount)

Global variable, reserves room in the data area. Has name and size

class ppci.ir.SubRoutine(name)

Base class of function and procedure. These two differ in that a function returns a value, where as a procedure does not.

Design trade-off: In C, a void type is introduced to permit functions that return nothing (void). This seems somewhat artificial, but keeps things simple for the users. In pascal, the procedure and function types are explicit, and the void type is not needed. This is also the approach taken here.

So instead of a Function and Call types, we have Function, Procedure, FunctionCall and ProcedureCall types.

add_block(block)

Add a block to this function

remove_block(block)

Remove a block from this function

class ppci.ir.Procedure(name)

A procedure definition that does not return a value

class ppci.ir.Function(name, return_ty)

Represents a function.

class ppci.ir.Block(name)

Uninterrupted sequence of instructions. A block is properly terminated if its last instruction is a FinalInstruction.

add_instruction(instruction)

Add an instruction to the end of this block

is_closed

Determine whether this block is propert terminated

is_empty

Determines whether the block is empty or not

predecessors

Return all predecessing blocks

remove_instruction(instruction)

Remove instruction from block

successors

Get the direct successors of this block

Types

Only simple types are available.

ppci.ir.ptr

Pointer type

ppci.ir.i64

Signed 64-bit type

ppci.ir.i32

Signed 32-bit type

ppci.ir.i16

Signed 16-bit type

ppci.ir.i8

Signed 8-bit type

ppci.ir.u64

Unsigned 64-bit type

ppci.ir.u32

Unsigned 32-bit type

ppci.ir.u16

Unsigned 16-bit type

ppci.ir.u8 = u8

Unsigned 8-bit type

ppci.ir.f64

64-bit floating point type

ppci.ir.f32

32-bit floating point type

Instructions

The following instructions are available.

Memory instructions

class ppci.ir.Load(address, name, ty, volatile=False)

Load a value from memory

class ppci.ir.Store(value, address, volatile=False)

Store a value into memory

class ppci.ir.Alloc(name, amount)

Allocates space on the stack. The type of this value is a ptr

Data instructions

class ppci.ir.Const(value, name, ty)

Represents a constant value

class ppci.ir.Binop(a, operation, b, name, ty)

Generic binary operation

class ppci.ir.Cast(value, name, ty)

Base type conversion instruction

Control flow instructions

class ppci.ir.ProcedureCall(function_name, arguments)

Call a procedure with some arguments

class ppci.ir.FunctionCall(function_name, arguments, name, ty)

Call a function with some arguments and a return value

class ppci.ir.Jump(target)

Jump statement to another block within the same function

class ppci.ir.CJump(a, cond, b, lab_yes, lab_no)

Conditional jump to true or false labels.

class ppci.ir.Return(result)

This instruction returns a value and exits the function.

class ppci.ir.Exit

Instruction that exits the procedure.

Other

class ppci.ir.Phi(name, ty)

Imaginary phi instruction to make SSA possible.

class ppci.ir.Undefined(name, ty)

Undefined value, this value must never be used.

Abstract instruction classes

There are some abstract instructions, which cannot be used directly but serve as base classes for other instructions.

class ppci.ir.Instruction

Base class for all instructions that go into a basic block

function

Return the function this instruction is part of

class ppci.ir.Value(name, ty)

An instruction that results in a value has a type and a name

is_used

Determine whether this value is used anywhere

class ppci.ir.FinalInstruction

Final instruction in a basic block

Uml

digraph "classes_foo" {
charset="utf-8"
rankdir=BT
"0" [label="{Alloc|amount\l|}", shape="record"];
"1" [label="{Binop|a\la : property\lb\lb : property\loperation\lops : list\l|}", shape="record"];
"2" [label="{Block|first_instruction\lfunction : NoneType\linstructions : list\lis_closed\lis_empty\lis_entry\lis_used\llast_instruction\lname\lphis\lpredecessors\lreferences : set\lsuccessors\l|add_instruction()\lchange_target()\ldelete()\ldump()\linsert_instruction()\lremove_instruction()\lreplace_incoming()\l}", shape="record"];
"3" [label="{CJump|a\la : property\lb\lb : property\lcond\lconditions : list\llab_no\llab_no : property\llab_yes\llab_yes : property\l|}", shape="record"];
"4" [label="{Cast|src\lsrc : property\l|}", shape="record"];
"5" [label="{Const|value\l|}", shape="record"];
"6" [label="{Exit|targets : list\l|}", shape="record"];
"7" [label="{Expression|\l|}", shape="record"];
"8" [label="{FinalInstruction|\l|}", shape="record"];
"9" [label="{Function|return_ty\l|}", shape="record"];
"10" [label="{FunctionCall|arguments\lfunction_name\l|replace_use()\l}", shape="record"];
"11" [label="{Instruction|block : NoneType\lfunction\lis_terminator\lposition\luses : set\l|add_use()\ldel_use()\ldelete()\lremove_from_block()\lreplace_use()\l}", shape="record"];
"12" [label="{Jump|target\ltarget : property\l|}", shape="record"];
"13" [label="{JumpBase|targets\l|change_target()\ldelete()\lset_target_block()\l}", shape="record"];
"14" [label="{LiteralData|data\l|}", shape="record"];
"15" [label="{Load|address\laddress : property\lvolatile : bool\l|}", shape="record"];
"16" [label="{Module|functions\lname\lvariables\l|add_function()\ladd_variable()\lstats()\l}", shape="record"];
"17" [label="{Parameter|\l|}", shape="record"];
"18" [label="{Phi|inputs : dict\l|del_incoming()\lget_value()\lreplace_use()\lset_incoming()\l}", shape="record"];
"19" [label="{Procedure|\l|}", shape="record"];
"20" [label="{ProcedureCall|arguments\lfunction_name\l|replace_use()\l}", shape="record"];
"21" [label="{Return|result\lresult : property\ltargets : list\l|}", shape="record"];
"22" [label="{Store|address\laddress : property\lvalue\lvalue : property\lvolatile : bool\l|}", shape="record"];
"23" [label="{SubRoutine|arguments : list\lblock_names\lblocks : list\ldefined_names : set\lentry : NoneType\llogger : RootLogger, NoneType\lname\lunique_counter : int\l|add_block()\ladd_parameter()\lcalc_reachable_blocks()\ldelete_unreachable()\ldump()\lmake_unique_name()\lnum_instructions()\lremove_block()\l}", shape="record"];
"24" [label="{Typ|name\l|}", shape="record"];
"25" [label="{Undefined|\l|}", shape="record"];
"26" [label="{Value|is_used\lname\lty\luse_count\lused_by : set\l|add_user()\ldel_user()\lreplace_by()\lused_in_blocks()\l}", shape="record"];
"27" [label="{Variable|amount\l|}", shape="record"];
"0" -> "7" [arrowhead="empty", arrowtail="none"];
"1" -> "7" [arrowhead="empty", arrowtail="none"];
"3" -> "13" [arrowhead="empty", arrowtail="none"];
"4" -> "7" [arrowhead="empty", arrowtail="none"];
"5" -> "7" [arrowhead="empty", arrowtail="none"];
"6" -> "8" [arrowhead="empty", arrowtail="none"];
"7" -> "26" [arrowhead="empty", arrowtail="none"];
"8" -> "11" [arrowhead="empty", arrowtail="none"];
"9" -> "23" [arrowhead="empty", arrowtail="none"];
"10" -> "7" [arrowhead="empty", arrowtail="none"];
"12" -> "13" [arrowhead="empty", arrowtail="none"];
"13" -> "8" [arrowhead="empty", arrowtail="none"];
"14" -> "7" [arrowhead="empty", arrowtail="none"];
"15" -> "26" [arrowhead="empty", arrowtail="none"];
"17" -> "7" [arrowhead="empty", arrowtail="none"];
"18" -> "26" [arrowhead="empty", arrowtail="none"];
"19" -> "23" [arrowhead="empty", arrowtail="none"];
"20" -> "11" [arrowhead="empty", arrowtail="none"];
"21" -> "8" [arrowhead="empty", arrowtail="none"];
"22" -> "11" [arrowhead="empty", arrowtail="none"];
"25" -> "26" [arrowhead="empty", arrowtail="none"];
"26" -> "11" [arrowhead="empty", arrowtail="none"];
"27" -> "7" [arrowhead="empty", arrowtail="none"];
}