API Reference
Public API
OptimizingIR.Op
— TypeOp(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 theOp
.pure
: marks the function as pure (true
) or impure (false
) .commutative
: marks theOp
as commutative.hasleftidentity
: marks theOp
as having an identity when operating from the left, which means thatf(I, v) = v
, whereI
is theidentity_element
.hasrightidentity
: marks theOp
as having an identity when operating from the right, which means thatf(v, I) = v
, whereI
is theidentity_element
.mutable_arg
: eithernothing
, 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)
OptimizingIR.Variable
— TypeVariable{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
OptimizingIR.call
— Functioncall(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
.
OptimizingIR.addinstruction!
— Functionaddinstruction!(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.
OptimizingIR.addinput!
— Functionaddinput!(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).
OptimizingIR.addoutput!
— Functionaddoutput!(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.
OptimizingIR.assign!
— Functionassign!(bb::BasicBlock, lhs::Variable, rhs::AbstractValue)
Assigns the value rhs
to variable lhs
.
OptimizingIR.constant
— Functionconstant(val) :: Const
Creates a constant value.
OptimizingIR.compile
— Functioncompile(::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)
OptimizingIR.has_symbol
— Functionhas_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
.
OptimizingIR.generate_unique_variable_symbol
— Functiongenerate_unique_variable_symbol(bb::BasicBlock) :: Symbol
OptimizingIR's version of Base.gensym
.
Returns a new symbol for which OptimizingIR.has_symbol
is false
.
Internals
OptimizingIR.AbstractValue
— TypeAbstractValue{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.
OptimizingIR.PureInstruction
— TypeA 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.
OptimizingIR.ImpureInstruction
— TypeAn 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.
OptimizingIR.SSAValue
— TypeA pointer to an instruction that computes a value.
OptimizingIR.try_on_add_instruction_passes
— Functiontry_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
OptimizingIR.LookupTable
— TypeGeneric struct for a lookup table that stores an ordered list of distinct elements.
element
is stored inentries
vector at indexi
.index[element]
retrieves the indexi
.
Use addentry!
to add items to the table. It the table already has the item, addentry!
will return the existing item's index.
OptimizingIR.Const
— TypeConstant value to be encoded directly into the IR. The address is the value itself.
OptimizingIR.OptimizationRule
— TypeSets which optimizations are allowed to an Op
.
OptimizingIR.BasicBlockInterpreter
— TypeUsed to compile to a function that is interpreted when executed.
OptimizingIR.Native
— TypeUsed to compile to a function to machine code.