minivect Package

miniast Module

This module provides the AST. Subclass Context and override the various methods to allow minivect visitors over the AST, to promote and map types, etc. Subclass and override ASTBuilder‘s methods to provide alternative AST nodes or different implementations.

class minivect.miniast.UndocClassAttribute(cls)

Bases: object

Use this to document class attributes for Sphinx

minivect.miniast.make_cls(cls1, cls2)

Fuse two classes together.

class minivect.miniast.Context

Bases: object

A context that knows how to map ASTs back and forth, how to wrap nodes and types, and how to instantiate a code generator for specialization.

An opaque_node or foreign node is a node that is not from our AST, and a normal node is one that has a interface compatible with ours.

To provide custom functionality, set the following attributes, or subclass this class.

Parameters:

• astbuilder – the ASTBuilder or None
• typemapper – the minivect.minitypes.Typemapper or None for the default.

codegen_cls

The code generator class that is used to generate code. The default is minivect.codegen.CodeGen

cleanup_codegen_cls

The code generator that generates code to dispose of any garbage (e.g. intermediate object temporaries). The default is minivect.codegen.CodeGenCleanup

codewriter_cls

The code writer that the code generator writes its generated code to. This may be strings or arbitrary objects. The default is minivect.minicode.CodeWriter, which accepts arbitrary objects.

codeformatter_cls

A formatter to format the generated code.

The default is minivect.minicode.CodeFormatter, which returns a list of objects written. Set this to minivect.minicode.CodeStringFormatter to have the strings joined together.

specializer_mixin_cls

A specializer mixin class that can override or intercept functionality. This class should likely participate cooperatively in MI.

variable_resolving_mixin_cls

A specializer mixin class that resolves wrapped miniasts in a foreign AST. This is only needed if you are using NodeWrapper, which wraps a miniast somewhere at the leaves.

Use subclass CContext to get the defaults for C code generation.

final_specializer

alias of FinalSpecializer

run(ast, specializer_classes, graphviz_outfile=None, print_tree=False)

Specialize the given AST with all given specializers and return an iterable of generated code in the form of (specializer, new_ast, codewriter, code_obj)

The code_obj is the generated code (e.g. a string of C code), depending on the code formatter used.

debug_c(ast, specializer, astbuilder_cls=None)

Generate C code (for debugging)

generate_disposal_code(code, node)

Run the disposal code generator on an (sub)AST

llvm_passes()

Returns a list of LLVM optimization passes

promote_types(type1, type2)

Promote types in an arithmetic operation

getchildren(node)

Implement to allow a minivisitor.Visitor over a foreign AST.

getpos(opaque_node)

Get the position of a foreign node

gettype(opaque_node)

Get a type of a foreign node

may_error(opaque_node)

Return whether this node may result in an exception.

declare_type(type)

Return a declaration for a type

to_llvm(type)

Return an LLVM type for the given minitype

class minivect.miniast.CContext

Bases: minivect.miniast.Context

Set defaults for C code generation.

codegen_cls

alias of VectorCodegen

codewriter_cls

alias of CCodeWriter

codeformatter_cls

alias of CCodeStringFormatter

class minivect.miniast.LLVMContext

Bases: minivect.miniast.Context

Context with default for LLVM code generation

codegen_cls

alias of LLVMCodeGen

class minivect.miniast.ASTBuilder(context)

Bases: object

This class is used to build up a minivect AST. It can be used by a user from a transform or otherwise, but the important bit is that we use it in our code to build up an AST that can be overridden by the user, and which makes it convenient to build up complex ASTs concisely.

function(name, body, args, shapevar=None, posinfo=None, omp_size=None)

Create a new function.

Parameters:

• name (str) – name of the function
• args ([FunctionArgument]) – all array and scalar arguments to the function, excluding shape or position information.
• shapevar – the Variable for the total broadcast shape If None, a default of Py_ssize_t * is assumed.
• posinfo (FunctionArgument) – if given, this will be the second, third and fourth arguments to the function (filename, lineno, column).

build_function(variables, body, name=None, shapevar=None)

Convenience method for building a minivect function

funcarg(variable, *variables)

Create a (compound) function argument consisting of one or multiple argument Variables.

array_funcarg(variable)

Create an array function argument

incref(var, funcname='Py_INCREF')

Generate a Py_INCREF() statement

decref(var)

Generate a Py_DECCREF() statement

print_(*args)

Print out all arguments to stdout

funccall(func_or_pointer, args, inline=False)

Generate a call to the given function (a FuncNameNode) of minivect.minitypes.FunctionType or a pointer to a function type and the given arguments.

nditerate(body)

This node wraps the given AST expression in an NDIterate node, which will be expanded by the specializers to one or several loops.

for_(body, init, condition, step, index=None)

Create a for loop node.

Parameters:

• body – loop body
• init – assignment expression
• condition – boolean loop condition
• step – step clause (assignment expression)

for_range_upwards(body, upper, lower=None, step=None)

Create a single upwards for loop, typically used from a specializer to replace an NDIterate node.

Parameters:

• body – the loop body
• upper – expression specifying an upper bound

omp_for(for_node, if_clause)

Annotate the for loop with an OpenMP parallel for clause.

Parameters:if_clause – the expression node that determines whether the parallel section is executed or whether it is executed sequentially (to avoid synchronization overhead)

pragma_for(for_node)

Annotate the for loop with pragmas.

stats(*statements)

Wrap a bunch of statements in an AST node.

expr_stat(expr)

Turn an expression into a statement

expr(stats=(), expr=None)

Evaluate a bunch of statements before evaluating an expression.

if_(cond, body)

If statement

if_else_expr(cond, lhs, rhs)

If/else expression, resulting in lhs if cond else rhs

promote(dst_type, node)

Promote or demote the node to the given dst_type

binop(type, op, lhs, rhs)

Binary operation on two nodes.

Parameters:

• type – the result type of the expression
• op (str) – binary operator

add(lhs, rhs, result_type=None, op='+')

Shorthand for the + binop. Filters out adding 0 constants.

mul(lhs, rhs, result_type=None, op='*')

Shorthand for the * binop. Filters out multiplication with 1 constants.

min(lhs, rhs)

Returns min(lhs, rhs) expression.

Note

Make lhs and rhs temporaries if they should only be evaluated once.

index(pointer, index, dest_pointer_type=None)

Index a pointer with the given index node.

Parameters:dest_pointer_type – if given, cast the result (after adding the index) to the destination type and dereference.

index_multiple(pointer, indices, dest_pointer_type=None)

Same as index(), but accepts multiple indices. This is useful e.g. after multiplication of the indices with the strides.

assign_expr(node, value, may_reorder=False)

Create an assignment expression assigning value to node

assign(node, value, may_reorder=False)

Assignment statement

dereference(pointer)

Dereference a pointer

unop(type, operator, operand)

Unary operation. type indicates the result type of the expression.

coerce_to_temp(expr)

Coerce the given expression to a temporary

temp(type, name=None)

Allocate a temporary of a given type

constant(value, type=None)

Create a constant from a Python value. If type is not given, it is inferred (or it will raise a minivect.minierror.InferTypeError).

variable(type, name)

Create a variable with a name and type. Variables may refer to function arguments, functions, etc.

resolved_variable(array_type, name, element)

Creates a node that keeps the array operand information such as the original array type, but references an actual element in the array.

Parameters:

• type – original array type
• name – original array’s name
• element – arbitrary expression that resolves some element in the array

cast(node, dest_type)

Cast node to the given destination type

return_(result)

Return a result

data_pointer(variable)

Return the data pointer of an array variable

shape_index(index, function)

Index the shape of the array operands with integer index

extent(variable, index, function)

Index the shape of a specific variable with integer index

stridesvar(variable)

Return the strides variable for the given array operand

stride(variable, index)

Return the stride of array operand variable at integer index

sizeof(type)

Return the expression sizeof(type)

jump(label)

Jump to a label

jump_target(label)

Return a target that can be jumped to given a label. The label is shared between the jumpers and the target.

label(name)

Return a label with a name

raise_exc(posinfo, exc_var, msg_val, fmt_args)

Raise an exception given the positional information (see the posinfo method), the exception type (PyExc_*), a formatted message string and a list of values to be used for the format string.

posinfo(posvars)

Return position information given a list of position variables (filename, lineno, column). This can be used for raising exceptions.

error_handler(node)

Wrap the given node, which may raise exceptions, in an error handler. An error handler allows the code to clean up before propagating the error, and finally returning an error indicator from the function.

wrap(opaque_node, specialize_node_callback, **kwds)

Wrap a node and type and return a NodeWrapper node. This node will have to be handled by the caller in a code generator. The specialize_node_callback is called when the NodeWrapper is specialized by a Specializer.

vector_variable(variable, size)

Return a vector variable for a data pointer variable

vector_load(data_pointer, size)

Load a SIMD vector of size size given an array operand variable

vector_store(data_pointer, vector_expr)

Store a SIMD vector of size size

vector_binop(operator, lhs, rhs)

Perform a binary SIMD operation between two operands of the same type

class minivect.miniast.DynamicArgumentASTBuilder(context)

Bases: minivect.miniast.ASTBuilder

Create a function with a dynamic number of arguments. This means the signature looks like

func(int *shape, float *data[n_ops], int *strides[n_ops])

To create minivect kernels supporting this signature, set the astbuilder_cls attribute of Context to this class.

stridesvar(variable)

Return the strides variable for the given array operand

class minivect.miniast.Position(filename, line, col)

Bases: object

Each node has a position which is an instance of this type.

class minivect.miniast.Node(pos, **kwds)

Bases: minivect.miniutils.ComparableObjectMixin

Base class for AST nodes.

may_error(context)

Return whether something may go wrong and we need to jump to an error handler.

class minivect.miniast.ExprNode(pos, type, **kwds)

Bases: minivect.miniast.Node

Base class for expressions. Each node has a type.

class minivect.miniast.FunctionNode(pos, name, body, arguments, scalar_arguments, shape, posinfo, error_value, success_value, omp_size)

Bases: minivect.miniast.Node

Function node. error_value and success_value are returned in case of exceptions and success respectively.

shape

the broadcast shape for all operands

ndim

the ndim of the total broadcast’ shape

arguments

all array arguments

scalar arguments

all non-array arguments

posinfo

the position variables we can write to in case of an exception

omp_size

the threshold of minimum data size needed before starting a parallel section. May be overridden at any time before specialization time.

class minivect.miniast.FuncCallNode(pos, type, **kwds)

Bases: minivect.miniast.ExprNode

Call a function given a pointer or its name (FuncNameNode)

class minivect.miniast.FuncNameNode(pos, type, **kwds)

Bases: minivect.miniast.ExprNode

Load an external function by its name.

class minivect.miniast.ReturnNode(pos, operand)

Bases: minivect.miniast.Node

Return an operand

class minivect.miniast.RaiseNode(pos, posinfo, exc_var, msg_val, fmt_args)

Bases: minivect.miniast.Node

Raise a Python exception. The callee must hold the GIL.

class minivect.miniast.PositionInfoNode(pos, **kwds)

Bases: minivect.miniast.Node

Node that holds a position of where an error occurred. This position needs to be returned to the callee if the callee supports it.

class minivect.miniast.FunctionArgument(pos, variable, variables)

Bases: minivect.miniast.ExprNode

Argument to the FunctionNode. Array arguments contain multiple actual arguments, e.g. the data and stride pointer.

variable

some argument to the function (array or otherwise)

variables

the actual variables this operand should be unpacked into

class minivect.miniast.ArrayFunctionArgument(pos, type, data_pointer, strides_pointer, **kwargs)

Bases: minivect.miniast.ExprNode

Array operand to the function

class minivect.miniast.PrintNode(pos, **kwds)

Bases: minivect.miniast.Node

Print node for some arguments

class minivect.miniast.NDIterate(pos, body)

Bases: minivect.miniast.Node

Iterate in N dimensions. See ASTBuilder.nditerate

class minivect.miniast.ForNode(pos, init, condition, step, body, index=None)

Bases: minivect.miniast.Node

A for loop, see ASTBuilder.for_

class minivect.miniast.IfNode(pos, **kwds)

Bases: minivect.miniast.Node

An ‘if’ statement, see A for loop, see ASTBuilder.if_

class minivect.miniast.StatListNode(pos, statements)

Bases: minivect.miniast.Node

A node to wrap multiple statements, see ASTBuilder.stats

class minivect.miniast.ExprStatNode(pos, **kwds)

Bases: minivect.miniast.Node

Turn an expression into a statement, see ASTBuilder.expr_stat

class minivect.miniast.NodeWrapper(pos, type, opaque_node, specialize_node_callback, **kwds)

Bases: minivect.miniast.ExprNode

Adapt an opaque node to provide a consistent interface. This has to be handled by the user’s specializer. See ASTBuilder.wrap

class minivect.miniast.BinaryOperationNode(pos, type, lhs, rhs, **kwds)

Bases: minivect.miniast.ExprNode

Base class for binary operations

class minivect.miniast.BinopNode(pos, type, operator, lhs, rhs, **kwargs)

Bases: minivect.miniast.BinaryOperationNode

Node for binary operations

class minivect.miniast.SingleOperandNode(pos, type, operand, **kwargs)

Bases: minivect.miniast.ExprNode

Base class for operations with one operand

class minivect.miniast.Variable(pos, type, name, **kwargs)

Bases: minivect.miniast.ExprNode

Represents use of a function argument in the function.

class minivect.miniast.ArrayAttribute(pos, type, arrayvar)

Bases: minivect.miniast.Variable

Denotes an attribute of array operands, e.g. the data or stride pointers

class minivect.miniast.DataPointer(pos, type, arrayvar)

Bases: minivect.miniast.ArrayAttribute

Reference to the start of an array operand

class minivect.miniast.StridePointer(pos, type, arrayvar)

Bases: minivect.miniast.ArrayAttribute

Reference to the stride pointer of an array variable operand

class minivect.miniast.TempNode(pos, type, name, **kwargs)

Bases: minivect.miniast.Variable

A temporary of a certain type

class minivect.miniast.OpenMPLoopNode(pos, **kwds)

Bases: minivect.miniast.Node

Execute a loop in parallel.

class minivect.miniast.OpenMPConditionalNode(pos, **kwds)

Bases: minivect.miniast.Node

Execute if_body if _OPENMP, otherwise execute else_body.

class minivect.miniast.PragmaForLoopNode(pos, **kwds)

Bases: minivect.miniast.Node

Generate compiler-specific pragmas to aid things like SIMDization.

class minivect.miniast.ErrorHandler(pos, **kwds)

Bases: minivect.miniast.Node

A node to handle errors. If there is an error handler in the outer scope, the specializer will first make this error handler generate disposal code for the wrapped AST body, and then jump to the error label of the parent error handler. At the outermost (function) level, the error handler simply returns an error indication.

error_label

point to jump to in case of an error

cleanup_label

point to jump to in the normal case

It generates the following:

  error_var = 0;
  ...
  goto cleanup;
error:
  error_var = 1;
cleanup:
  ...
  if (error_var)
      goto outer_error_label;

class minivect.miniast.JumpNode(pos, label)

Bases: minivect.miniast.Node

A jump to a jump target

class minivect.miniast.JumpTargetNode(pos, label)

Bases: minivect.miniast.JumpNode

A point to jump to

class minivect.miniast.LabelNode(pos, name)

Bases: minivect.miniast.ExprNode

A goto label or memory address that we can jump to

class minivect.miniast.NoopExpr(pos, type, **kwds)

Bases: minivect.miniast.ExprNode

Do nothing expression

class minivect.miniast.VectorLoadNode(pos, type, operand, **kwargs)

Bases: minivect.miniast.SingleOperandNode

Load a SIMD vector

class minivect.miniast.VectorStoreNode(pos, type, operator, lhs, rhs, **kwargs)

Bases: minivect.miniast.BinopNode

Store a SIMD vector

class minivect.miniast.VectorBinopNode(pos, type, operator, lhs, rhs, **kwargs)

Bases: minivect.miniast.BinopNode

Binary operation on SIMD vectors

class minivect.miniast.VectorUnopNode(pos, type, operand, **kwargs)

Bases: minivect.miniast.SingleOperandNode

Unary operation on SIMD vectors

class minivect.miniast.ConstantVectorNode(pos, type, **kwds)

Bases: minivect.miniast.ExprNode

Load the constant into the vector register

specializers Module

Specializers for various sorts of data layouts and memory alignments.

These specializers operate on a copy of the simplified array expression representation (i.e., one with an NDIterate node). This node is replaced with one or several ForNode nodes in a specialized order.

For auto-tuning code for tile size and OpenMP size, see https://github.com/markflorisson88/cython/blob/_array_expressions/Cython/Utility/Vector.pyx

class minivect.specializers.ASTMapper(context)

Bases: minivect.minivisitor.VisitorTransform

Base class to map foreign ASTs onto a minivect AST, or vice-versa. This sets the current node’s position in the astbuilder for each node that is being visited, to make it easy to build new AST nodes without passing in source position information everywhere.

map_type(opaque_node, **kwds)

Return a mapped type for the foreign node.

class minivect.specializers.BaseSpecializer(context)

Bases: minivect.specializers.ASTMapper

Base class for specialization. Does not perform any specialization itself.

get_type(type)

Resolve the type to the dtype of the array if an array type

init_pending_stats(node)

Allow modifications while visiting some descendant of this node This happens especially while variables are resolved, which calls compute_inner_dim_pointer()

handle_pending_stats(node)

Handle any pending statements that need to be inserted further up in the AST.

fuse_omp_stats(node)

Fuse consecutive OpenMPConditionalNodes.

class minivect.specializers.Specializer(context, specialization_name=None)

Bases: minivect.specializers.BaseSpecializer

Base class for most specializers, provides some basic functionality for subclasses. Implement visit_* methods to specialize nodes to some pattern.

Implements implementations to handle errors and cleanups, adds a return statement to the function and can insert debug print statements if context.debug is set to a true value.

visit_FunctionNode(node)

Handle a FunctionNode. Sets node.total_shape to the product of the shape, wraps the function’s body in a minivect.miniast.ErrorHandler if needed and adds a return statement.

omp_for(node)

Insert an OpenMP for loop with an ‘if’ clause that checks to see whether the total data size exceeds the given OpenMP auto-tuned size. The caller needs to adjust the size, set in the FunctionNode’s ‘omp_size’ attribute, depending on the number of computations.

class minivect.specializers.FinalSpecializer(context, previous_specializer)

Bases: minivect.specializers.BaseSpecializer

Perform any final specialization and optimizations. The initial specializer is concerned with specializing for the given data layouts, whereas this specializer is concerned with any rewriting of the AST to support fundamental operations.

run_optimizations(node)

Run any optimizations on the AST. Currently only loop-invariant code motion is implemented when broadcasting information is present.

visit_Variable(node)

Process variables, which includes arrays and scalars. For arrays, this means retrieving the element from the array. Performs strength reduction for index calculation of array variables.

element_location(data_pointer, for_node, inner_contig, is_contig, tiled, variable)

Return the element in the array for the current index set

handle_vector_variable(variable, data_pointer, for_node, inner_contig, is_contig)

Same as element_location, except for Vector variables

compute_temp_strides(variable, handle_inner_dim, tiled=False)

Compute the temporary strides needed for the strength reduction. These should be small constants, so division should be fast. We could use char * instead of element_type *, but it’s nicer to avoid the casts.

compute_data_pointer(variable, argument_data_pointer, handle_inner_dim, tiled)

Compute the data pointer for the dimension the variable is located in (the loop level). This involves generating a strength reduction in each outer dimension.

Variables referring to the same array may be found on different loop levels.

visit_PositionInfoNode(node)

Replace with the setting of positional source information in case of an error.

visit_RaiseNode(node)

Generate a call to PyErr_Format() to set an exception.

visit_ErrorHandler(node)

See miniast.ErrorHandler for an explanation of what this needs to do.

class minivect.specializers.OrderedSpecializer(context, specialization_name=None)

Bases: minivect.specializers.Specializer

Specializer that understands C and Fortran data layout orders.

compute_total_shape(node)

Compute the product of the shape (entire length of array output). Sets the total shape as attribute of the function (total_shape).

loop_order(order, ndim=None)

Returns arguments to (x)range() to process something in C or Fortran order.

order_indices(indices)

Put the indices of the for loops in the right iteration order. The loops were build backwards (Fortran order), so for C we need to reverse them.

Note: the indices are always ordered on the dimension they index

ordered_loop(node, result_indices, lower=None, upper=None, step=None, loop_order=None)

Return a ForNode ordered in C or Fortran order.

class minivect.specializers.CanVectorizeVisitor(context)

Bases: minivect.minivisitor.TreeVisitor

Determines whether we can vectorize a given expression. Currently only support arithmetic on floats and doubles.

minivect.specializers.visit_if_should_vectorize(func)

Visits the given method if we are vectorizing, otherwise visit the superclass’ method of VectorizingSpecialization

class minivect.specializers.VectorizingSpecializer(context, specialization_name=None)

Bases: minivect.specializers.Specializer

Generate explicitly vectorized code if supported.

Parameters:vector_size – number of 32-bit operands in the vector

can_vectorize_visitor

alias of CanVectorizeVisitor

fixup_loop(i, N, body, elements_per_vector)

Generate a loop to fix up any remaining elements that didn’t fit into our SIMD vectors.

process_inner_forloop(node, original_expression, step=None)

Process an inner loop, adjusting the step accordingly and injecting any temporary assignments where necessary. Returns the fixup loop, needed when the data size is not a multiple of the vector size.

Parameters:original_expression – original, unmodified, array expression ( the body of the NDIterate node)

class minivect.specializers.StridedCInnerContigSpecializer(context, specialization_name=None)

Bases: minivect.specializers.OrderedSpecializer

Specialize on the first or last dimension being contiguous (depending on the ‘order’ attribute).

visit_NDIterate(node)

Replace this node with ordered loops and a direct index into a temporary data pointer in the contiguous dimension.

strided_indices()

Return the list of strided indices for this order

contig_index()

The contiguous index

class minivect.specializers.StridedFortranInnerContigSpecializer(context, specialization_name=None)

Bases: minivect.specializers.StridedCInnerContigSpecializer

Specialize on the first dimension being contiguous.

class minivect.specializers.StrengthReducingStridedSpecializer(context, specialization_name=None)

Bases: minivect.specializers.StridedCInnerContigSpecializer

Specialize on strided operands. If some operands are contiguous in the dimension compatible with the order we are specializing for (the first if Fortran, the last if C), then perform a direct index into a temporary date pointer. For strided operands, perform strength reduction in the inner dimension by adding the stride to the data pointer in each iteration.

matching_contiguity(type)

Check whether the array operand for the given type can be directly indexed.

strength_reduce_inner_dimension(outer_loop, inner_loop)

Reduce the strength of strided array operands in the inner dimension, by adding the stride to the temporary pointer.

class minivect.specializers.StrengthReducingStridedFortranSpecializer(context, specialization_name=None)

Bases: minivect.specializers.StridedFortranInnerContigSpecializer, minivect.specializers.StrengthReducingStridedSpecializer

Specialize on Fortran order for strided operands and apply strength reduction in the inner dimension.

minivect.specializers.StridedSpecializer

alias of StrengthReducingStridedSpecializer

minivect.specializers.StridedFortranSpecializer

alias of StrengthReducingStridedFortranSpecializer

class minivect.specializers.ContigSpecializer(context, specialization_name=None)

Bases: minivect.specializers.OrderedSpecializer

Specialize on all specializations being contiguous (all F or all C).

visit_NDIterate(node)

Generate a single ForNode over the total data size.

class minivect.specializers.CTiledStridedSpecializer(context, specialization_name=None)

Bases: minivect.specializers.StrengthReducingStridedSpecializer

Generate tiled code for the last two (C) or first two (F) dimensions. The blocksize may be overridden through the get_blocksize method, in a specializer subclass or mixin (see miniast.Context.specializer_mixin_cls).

get_blocksize()

Get the tile size. Override in subclasses to provide e.g. parametric tiling.

tiled_order()

Tile in the last two dimensions

set_dims(tiled_loops)

Set the ‘dim’ attributes of the tiling and controlling loops

class minivect.specializers.FTiledStridedSpecializer(context, specialization_name=None)

Bases: minivect.specializers.StrengthReducingStridedFortranSpecializer, minivect.specializers.CTiledStridedSpecializer

Tile in Fortran order

tiled_order()

Tile in the first two dimensions

minivect.specializers.create_vectorized_specializers(specializer_cls)

Creates Vectorizing specializer classes from the given specializer for SSE and AVX.

minivect.specializers.sp

alias of FTiledStridedSpecializer

optimize Module

minivect.optimize.admissible(broadcasting_tuple, n_loops)

Check for admissibility. Indicates whether partial hoisting is the most efficient thing to perform. See also partially_hoistable()

minivect.optimize.partially_hoistable(broadcasting_tuple, n_loops)

This function indicates, when admissible() returns false, whether an expression is partially hoistable. This means the caller must establish whether repeated computation or an array temporary will be more beneficial.

If the expression is a variable, there is no repeaetd computation, and it should be hoisted as far as possible.

class minivect.optimize.HoistBroadcastingExpressions(context)

Bases: minivect.specializers.BaseSpecializer

This transform hoists out part of sub-expressions which are broadcasting. There are two cases:

1. We can hoist out the sub-expression and store it in a scalar for broadcasting
2. We have to hoist the sub-expression out entirely and store it in a temporary array

As an alternative to 2), we could swap axes to return to situation 1), i.e. reorder the element-wise traversal order. We do not choose this option, since the loop order is tailored to cache-friendliness.

We determine where to hoist sub-expression to based on broadcasting information. Each type has a broadcasting tuple with a true/false value for each dimension, specifying whether it will broadcast in that dimension (i.e. broadcasting is not optional in that dimension).

We make the following observations:

1. Trailing truth values mean we can hoist the sub-expression out just before the first truth value in the consecutive sequence of truth values

   Example (False, True, True):

   A[:, None, None] * A[:, None, None] * B[:, :, :]

   becomes:

   for i in shape[0]:
       temp = A[i, 0, 0] * A[i, 0, 0]
       for j in shape[1]:
           for k in shape[2]:
               temp * B[i, j, k]
   

2. If not all consecutive leading values are false, we have to assign to a temporary array (i.e., hoist out all the way)

   Example (True, True, False):

   A[None, None, :] * A[None, None, :] * B[:, :, :]

   becomes:

   allocate temp
   
   for k in shape[2]:
       temp[k] = A[0, 0, k] * A[0, 0, k]
   
   for i in shape[0]:
       for j in shape[1]:
           for k in shape[2]:
               temp[k] * B[i, j, k]
   
   deallocate temp

More generally, if the index sequence of array A is not an admissible prefix of the total index sequence, we have situation 2). For instance, (True, False, True) would mean we could hoist out the expression one level, but we would still have repeated computation. What we could do in this case, in addition to 2), is reduce indexing overhead, i.e. generate:

for j in shape[1]:
    temp[j] = A[0, j, 0] * A[0, j, 0]

for i in shape[0]:
    for j in shape[1]:
        temp_scalar = temp[j]
        for k in shape[2]:
            temp_scalar * B[i, j, k]

This is bonus points.

make_temp(node)

Not implemented yet

type_promoter Module

Promote and demote values of differing types in a minivect AST. This is run before code generation. In LLVM types need to be equivalent for binary operations.

class minivect.type_promoter.TypePromoter(context)

Bases: minivect.minivisitor.GenericTransform

Promote and demote values of differing types.

minitypes Module

This module provides a minimal type system, and ways to promote types, as well as ways to convert to an LLVM type system. A set of predefined types are defined. Types may be sliced to turn them into array types, in the same way as the memoryview syntax.

>>> char
char
>>> int8[:, :, :]
int8[:, :, :]
>>> int8.signed
True
>>> uint8
uint8
>>> uint8.signed
False

>>> char.pointer()
char *
>>> int_[:, ::1]
int[:, ::1]
>>> int_[::1, :]
int[::1, :]
>>> double[:, ::1, :]
Traceback (most recent call last):
   ...
InvalidTypeSpecification: Step may only be provided once, and only in the first or last dimension.

class minivect.minitypes.struct(fields=None, name=None, readonly=False, packed=False, **kwargs)

Bases: minivect.minitypes.Type

Create a struct type. Fields may be ordered or unordered. Unordered fields will be ordered from big types to small types (for better alignment).

>>> struct([('a', int_), ('b', float_)], name='Foo') # ordered struct
struct Foo { int a, float b }
>>> struct(a=int_, b=float_, name='Foo') # unordered struct
struct Foo { float b, int a }
>>> struct(a=int32, b=int32, name='Foo') # unordered struct
struct Foo { int32 a, int32 b }

>>> struct(a=complex128, b=complex64, c=struct(f1=double, f2=double, f3=int32))
struct { struct { double f1, double f2, int32 f3 } c, complex128 a, complex64 b }

minivisitor Module

Adapted from Cython/Compiler/Visitor.py, see this module for detailed explanations.

class minivect.minivisitor.TreeVisitor(context)

Bases: object

Non-mutating visitor. Subclass and implement visit_MyNode methods. A user can traverse a foreign AST by implementing minivect.miniast.Context.getchildren

visit(obj, *args)

Visit a single child.

visitchildren(parent, attrs=None)

Visits the children of the given node.

class minivect.minivisitor.VisitorTransform(context)

Bases: minivect.minivisitor.TreeVisitor

Mutating transform. Each attribute is replaced by the result of the corresponding visit_MyNode method.

class minivect.minivisitor.GenericVisitor(context)

Bases: minivect.minivisitor.TreeVisitor

Generic visitor that automatically visits children

class minivect.minivisitor.GenericTransform(context)

Bases: minivect.minivisitor.VisitorTransform, minivect.minivisitor.GenericVisitor

Generic transform that automatically visits children

class minivect.minivisitor.MayErrorVisitor(context)

Bases: minivect.minivisitor.TreeVisitor

Determine whether code generated by an AST can raise exceptions.

class minivect.minivisitor.PrintTree(context)

Bases: minivect.minivisitor.TreeVisitor

Print an AST, see also minivect.miniast.Node.print_tree.

miniutils Module

Miscellaneous (convenience) utilities.

minivect.miniutils.specialize(context, specializer_cls, ast, print_tree=False)

Specialize an AST with given specializer and compile

class minivect.miniutils.MiniFunction(context, specializer, variables, expr, name=None)

Bases: object

Convenience class to compile a function using LLVM and to invoke the function with ctypes given numpy arrays as input.

class minivect.miniutils.ComparableObjectMixin

Bases: object

Make sure subclasses implement comparison and hashing methods

codegen Module

Code generator module. Subclass CodeGen to implement a code generator as a visitor.

class minivect.codegen.CodeGen(context, codewriter)

Bases: minivect.minivisitor.TreeVisitor

Base class for code generators written as visitors.

class minivect.codegen.CodeGenCleanup(context, codewriter)

Bases: minivect.codegen.CodeGen

Perform cleanup for all nodes. This is invoked from an appropriate clean- up point from an minivect.miniast.ErrorHandler. Recursion should hence stop at ErrorHandler nodes, since an ErrorHandler descendant should handle its own descendants.

Users of minivect should subclass this to DECREF object temporaries, etc.

minivect.codegen.format_specifier(node, astbuilder)

Return a printf() format specifier for the type of the given AST node

class minivect.codegen.CCodeGen(context, codewriter)

Bases: minivect.codegen.CodeGen

Generates C code from an AST, needs a minivect.minicode.CCodeWriter. To use the vectorized specializations, use the VectorCodeGen below.

put_intel_pragmas(code)

Insert Intel compiler specific pragmas. See “A Guide to Vectorization with Intel(R) C++ Compilers”.

class minivect.codegen.VectorCodegen(context, codewriter)

Bases: minivect.codegen.CCodeGen

Generate C code for vectorized ASTs. As a subclass of CCodeGen, can write C code for any minivect AST.

llvm_codegen Module

Generate LLVM code for a minivect AST.

class minivect.llvm_codegen.LLVMCodeGen(context, codewriter)

Bases: minivect.codegen.CodeGen

Generate LLVM code for a minivect AST.

Takes a regular minivect.minicode.CodeWriter to which it writes the LLVM function and a ctypes function.

append_basic_block(name='unamed')

append a basic block and keep track of it

optimize()

Run llvm optimizations on the generated LLVM code

add_arguments(function)

Insert function arguments into the symtab

visit_OpenMPConditionalNode(node)

OpenMP is not yet implemented, only process the ‘else’ directives.

visit_ForNode(node)

Implements simple for loops with iternode as range, xrange

visit_PromotionNode(node)

Handle promotions as inserted by minivect.type_promoter.TypePromoter

init_comparisons()

Define binary operation LLVM instructions. Do this in a function in case llvm-py is not installed.

ctypes_conversion Module

Convert a minivect type to a ctypes type and an llvm function to a ctypes function.

minivect.ctypes_conversion.convert_to_ctypes(type)

Convert the minitype to a ctypes type

>>> from minitypes import *
>>> assert convert_to_ctypes(int32) == ctypes.c_int32
>>> assert convert_to_ctypes(int64) == ctypes.c_int64
>>> assert convert_to_ctypes(uint32) == ctypes.c_uint32
>>> assert convert_to_ctypes(uint64) == ctypes.c_uint64
>>> assert convert_to_ctypes(short) == ctypes.c_short
>>> assert convert_to_ctypes(int_) == ctypes.c_int
>>> assert convert_to_ctypes(long_) == ctypes.c_long
>>> assert convert_to_ctypes(float_) == ctypes.c_float
>>> assert convert_to_ctypes(double) == ctypes.c_double
>>> #convert_to_ctypes(complex64)
>>> #convert_to_ctypes(complex128)
>>> #convert_to_ctypes(complex256)

minivect.ctypes_conversion.convert_from_ctypes(type)

Convert a ctypes type to a minitype

minivect.ctypes_conversion.get_ctypes_func(func, llvm_func, llvm_execution_engine, context)

Get a ctypes function from an llvm function

minivect.ctypes_conversion.get_data_pointer(numpy_array, array_type)

Get a ctypes typed data pointer for the numpy array with type array_type

minivect.ctypes_conversion.get_pointer(context, llvm_func)

Get a pointer to the LLVM function (int)

minicode Module

Code writers and formatters. Subclass CodeWriter to suit the needs of a certain code generator backend.

class minivect.minicode.CodeWriter(context, buffer=None)

Bases: object

Write code as objects for later assembly.

loop_levels

CodeWriter objects just before the start of each loop

tiled_loop_levels

same as loop_levels, but takes into account tiled loop patterns

cleanup_levels

CodeWriter objects just after the end of each loop

declaration_levels

same as loop_levels, but a valid insertion point for C89 declarations

insertion_point()

Create an insertion point for the code writer. Any code written to this insertion point (later on) is inserted in the output code at the point where this method was called.

put_label(label)

Insert a label in the code

put_goto(label)

Jump to a label. Implement in subclasses

class minivect.minicode.CCodeWriter(context, buffer=None, proto_code=None)

Bases: minivect.minicode.CodeWriter

Code writer to write C code. Has both a prototype buffer and an implementation buffer. The prototype buffer will contain the C prototypes, and the implementation buffer the actual function code.

put_label(label)

Insert a C label

put_goto(label)

Jump to (goto) a label

putln(s)

Write a code string as a line. Also performs indentation

mangle(s)

Mangle symbol names

minivect.minicode.sub_tempita(s, context, file=None, name=None)

Run the tempita template engine on string the given string.

class minivect.minicode.TempitaCodeWriter(context, buffer=None)

Bases: minivect.minicode.CodeWriter

Code writer which supports writing Tempita strings. See http://pythonpaste.org/tempita/ for documentation on Tempita.

class minivect.minicode.CodeFormatter

Bases: object

Default code formatting, which returns the formatted code as a list of objects (the ones written to the minivect.codegen.CodeWriter)

class minivect.minicode.CodeStringFormatter

Bases: minivect.minicode.CodeFormatter

Format code as strings

class minivect.minicode.CCodeStringFormatter

Bases: minivect.minicode.CodeStringFormatter

Format the prototype and code implementation

graphviz Module

Visitor to generate a Graphviz .dot file with an AST representation.

class minivect.graphviz.GraphvizGenerator(context, name, node_color=None, edge_color=None, node_fontcolor=None, edge_fontcolor=None)

Bases: minivect.minivisitor.PrintTree

Render a minivect AST as a graphviz tree.

create_node(node)

Create a graphviz node from the miniast node

add_node(pydot_node)

Add a pydot node to the graph and set its colors

add_edge(source, dest, edge_label=None)

Add an edge between two pydot nodes and set the colors

visit_Node(node, pydot_node=None)

Visit children and add edges to their Graphviz nodes.

visit_FunctionNode(node)

Create a graphviz graph

xmldumper Module

Convert a miniast to an XML document using ElementTree. This allows us to write XPath unit tests, or just serialize the AST.

minierror Module

Define some errors that may be raised by the compiler.

exception minivect.minierror.Error

Bases: exceptions.Exception

Base exception class

exception minivect.minierror.InferTypeError

Bases: minivect.minierror.Error

Raised when types of values cannot be inferred

exception minivect.minierror.UnmappableTypeError

Bases: minivect.minierror.Error

Raised when a type cannot be mapped

exception minivect.minierror.UnpromotableTypeError

Bases: minivect.minierror.Error

Raised when the compiler does not know how to promote two types.

exception minivect.minierror.UnmappableFormatSpecifierError

Bases: minivect.minierror.Error

Raised when a type cannot be mapped to a (printf) format specifier

exception minivect.minierror.InvalidTypeSpecification

Bases: minivect.minierror.Error

Raised when a type is sliced incorrectly.

exception minivect.minierror.CompileError(node, msg)

Bases: minivect.minierror.Error

Raised for miscellaneous errors