API Reference

Op(f::Function;
        pure::Bool=false,
        commutative::Bool=false,
        hasleftidentity::Bool=false,
        hasrightidentity::Bool=false,
        identity_element::T=NULL_IDENTITY_ELEMENT,
        mutable_arg=nothing)

Defines a basic instruction with optimization annotations.

Arguments

• f is a Julia function to be executed by the Op.

• pure: marks the function as pure (true) or impure (false) .

• commutative: marks the Op as commutative.

• hasleftidentity: marks the Op as having an identity when operating from the left, which means that f(I, v) = v, where I is the identity_element.

• hasrightidentity: marks the Op as having an identity when operating from the right, which means that f(v, I) = v, where I is the identity_element.

• mutable_arg: either nothing, or the index or tuple of indexes of the arguments that need to be mutable.

Purity

A function is considered pure if its return value is the same for the same arguments, and has no side-effects.

Operations marked as pure are suitable for Value-Numbering optimization.

When marked as impure, all optimization passes are disabled.

Examples

# this Op allows using `+` as a pure, commutative function. Sets 0 as identity element.
const OP_SUM = OIR.Op(+, pure=true, commutative=true, hasleftidentity=true, hasrightidentity=true, identity_element=0)

# `-` as a pure function. Identity is zero but only `x - 0 = x` case is checked.
const OP_SUB = OIR.Op(-, pure=true, hasrightidentity=true, identity_element=0)

# `*` as pure commutative function. Sets 1 as identity element.
const OP_MUL = OIR.Op(*, pure=true, commutative=true, hasleftidentity=true, hasrightidentity=true, identity_element=1)

# `/` as a pure function. Identity is checked to the right: `a / 1 = a`.
const OP_DIV = OIR.Op(/, pure=true, hasrightidentity=true, identity_element=1)

# power function
const OP_POW = OIR.Op(^, pure=true, hasrightidentity=true, identity_element=1)

# an Op that uses an arbitrary Julia function
foreign_fun(a, b, c) = a^3 + b^2 + c
const OP_FOREIGN_FUN = OIR.Op(foreign_fun, pure=true)

# An Op that is impure: every time we run `zeros` a different Array is returned.
const OP_ZEROS = OIR.Op(zeros)

Variable{M<:Mutability}

Creates a variable identified by a symbol that can be either mutable or immutable.

Alias

For convenience, the following constants are defined in the package:

const MutableVariable = Variable{Mutable}
const ImmutableVariable = Variable{Immutable}

Examples

m = OptimizingIR.MutableVariable(:varmut) # a mutable variable
im = OptimizingIR.ImmutableVariable(:varimut) # an immutable variable

call(op, args...) :: LinearInstruction

Creates an instruction as a call to operation op with arguments args.

Internally, it returns either a OptimizingIR.PureInstruction or an OptimizingIR.ImpureInstruction.

addinstruction!(b::BasicBlock, instruction::LinearInstruction) :: ImmutableValue

Pushes an instruction to a basic block. Returns the value that represents the result after the execution of the instruction.

addinput!(b::BasicBlock, iv::ImmutableVariable) :: Int

Registers iv as an input variable of the function. Returns the index of this variable in the tuple of inputs (function arguments).

addoutput!(b::BasicBlock, iv::Variable) :: Int

Registers iv as an output variable of the function. Returns the index of this variable in the tuple of returned values.

assign!(bb::BasicBlock, lhs::Variable, rhs::AbstractValue)

Assigns the value rhs to variable lhs.

constant(val) :: Const

Creates a constant value.

compile(::Type{T}, program::Program) where {T<:AbstractMachine}

Compiles the IR to a Julia function. It returns a function or a callable object (functor).

const OIR = OptimizingIR
bb = OIR.BasicBlock()
# (...) add instructions to basic block
finterpreter = OIR.compile(OIR.BasicBlockInterpreter, bb)
fnative = OIR.compile(OIR.Native, bb)

has_symbol(bb::BasicBlock, sym::Symbol) :: Bool

Returns true if there is any variable (input, local or output) defined that is identified by the symbol sym.

generate_unique_variable_symbol(bb::BasicBlock) :: Symbol

OptimizingIR's version of Base.gensym.

Returns a new symbol for which OptimizingIR.has_symbol is false.

AbstractValue{M<:Mutability}

A value can be marked as either Mutable or Immutable.

An immutable value can be assigned only once. A mutable value can be assigned more than once.

A PureInstruction is a call to an operation that always returns the same value if the same arguments are passed to the instruction. It is suitable for memoization, in the sense that it can be optimized in the Value-Number algorithm inside a Basic Block.

An instruction is considered pure if its call has an pure Op and all of its arguments are immutable.

An ImpureInstruction is a call to an operation that not always returns the same value if the same arguments are passed to the instruction. It is not suitable for memoization, and the Value-Number optimization must be disabled for this call.

An instruction is considered impure if its call has an impure Op, or if onde of its arguments is mutable.

Marking as mutable avoids Value-Numbering for this call.

A pointer to an instruction that computes a value.

try_on_add_instruction_passes(program, instruction) :: Union{Nothing, ImmutableValue}

Tries to apply all optimization passes available while running addinstruction!:

function addinstruction!(b::BasicBlock, instruction::LinearInstruction) :: ImmutableValue

    result = try_on_add_instruction_passes(b, instruction)
    if result !== nothing
        return result
    end

    # (...)
end

Generic struct for a lookup table that stores an ordered list of distinct elements.

• element is stored in entries vector at index i.

• index[element] retrieves the index i.

Use addentry! to add items to the table. It the table already has the item, addentry! will return the existing item's index.

Constant value to be encoded directly into the IR. The address is the value itself.

Sets which optimizations are allowed to an Op.

Used to compile to a function that is interpreted when executed.

Used to compile to a function to machine code.