API Reference

Public API

OptimizingIR.OpType
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)
source
OptimizingIR.VariableType
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
source
OptimizingIR.addinstruction!Function
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.

source
OptimizingIR.addinput!Function
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).

source
OptimizingIR.addoutput!Function
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.

source
OptimizingIR.assign!Function
assign!(bb::BasicBlock, lhs::Variable, rhs::AbstractValue)

Assigns the value rhs to variable lhs.

source
OptimizingIR.compileFunction
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)
source
OptimizingIR.has_symbolFunction
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.

source

Internals

OptimizingIR.AbstractValueType
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.

source
OptimizingIR.PureInstructionType

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.

source
OptimizingIR.ImpureInstructionType

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.

source
OptimizingIR.try_on_add_instruction_passesFunction
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
source
OptimizingIR.LookupTableType

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.

source