# devito.ir.iet package¶

## devito.ir.iet.analysis module¶

A collection of algorithms to analyze and decorate Iteration in an Iteration/Expression tree. Decoration comes in the form of IterationProperty objects, attached to Iterations in the Iteration/Expression tree. The algorithms perform actual data dependence analysis.

devito.ir.iet.analysis.iet_analyze(iet)[source]

Attach IterationProperty to Iteration objects within nodes. The recognized IterationProperty decorators are listed in nodes.IterationProperty._KNOWN.

## devito.ir.iet.nodes module¶

The Iteration/Expression Tree (IET) hierarchy.

class devito.ir.iet.nodes.Node[source]
args

Arguments used to construct the Node.

args_frozen

Arguments used to construct the Node that cannot be traversed.

ccode

Generate C code.

This is a shorthand for

from devito.ir.iet import CGen
CGen().visit(self)

children

Return the traversable children.

defines

Return all Symbol objects defined by this Node.

free_symbols

Return all Symbol objects used by this Node.

functions

Return all AbstractFunction objects used by this Node.

is_Block = False
is_Call = False
is_Callable = False
is_Element = False
is_Expression = False
is_ExpressionBundle = False

_traversable. The traversable fields of the Node; that is, fields walked over by a Visitor. All arguments in __init__ whose name appears in this list are treated as traversable fields.

is_ForeignExpression = False
is_HaloSpot = False
is_Increment = False
is_Iteration = False
is_IterationFold = False
is_List = False
is_Node = True
is_Section = False
view

Generate a representation of the Iteration/Expression tree rooted in self.

class devito.ir.iet.nodes.Block(header=None, body=None, footer=None)[source]

A sequence of nodes, wrapped in a block {…}.

defines

Return all Symbol objects defined by this Node.

free_symbols

Return all Symbol objects used by this Node.

functions

Return all AbstractFunction objects used by this Node.

is_Block = True
class devito.ir.iet.nodes.Denormals(header=None, body=None, footer=None)[source]

Macros to make sure denormal numbers are flushed in hardware.

class devito.ir.iet.nodes.Expression(expr)[source]

A node encapsulating a SymPy equation.

defines

Return any symbols an Expression may define.

dimensions
dtype
free_symbols

Return all Symbol objects used by this Expression.

functions

Return all AbstractFunction objects used by this Node.

is_Expression = True
is_scalar

Return True if a scalar expression, False otherwise.

is_scalar_assign

Return True if a scalar, non-increment expression

is_tensor

Return True if a tensor expression, False otherwise.

output

Return the symbol written by this Expression.

write

Return the function written by this Expression.

class devito.ir.iet.nodes.Element(element)[source]

A generic node in an Iteration/Expression tree. Can be a comment, a statement, …

is_Element = True
class devito.ir.iet.nodes.Callable(name, body, retval, parameters=None, prefix=('static', 'inline'))[source]

A node representing a callable function.

Parameters: name – The name of the callable. body – A Node or an iterable of Node objects representing the body of the callable. retval – The type of the value returned by the callable. parameters – An iterable of AbstractFunctions in input to the callable, or None if the callable takes no parameter. prefix – An iterable of qualifiers to prepend to the callable declaration. The default value is (‘static’, ‘inline’).
is_Callable = True
class devito.ir.iet.nodes.Call(name, params=None)[source]

A function call.

defines

Return all Symbol objects defined by this Call.

free_symbols

Return all Symbol objects used by this Call.

functions

Return all Symbol objects used by this Call.

is_Call = True
class devito.ir.iet.nodes.Conditional(condition, then_body, else_body=None)[source]

A node to express if-then-else blocks.

Parameters: condition – A SymPy expression representing the if condition. then_body – Single or iterable of Node objects defining the body of the ‘then’ part of the if-then-else. else_body – (Optional) Single or iterable of Node objects defining the body of the ‘else’ part of the if-then-else.
defines

Return all Symbol objects defined by this Node.

free_symbols

Return all Symbol objects used by this Node.

functions

Return all AbstractFunction objects used by this Node.

is_Conditional = True
class devito.ir.iet.nodes.Iteration(nodes, dimension, limits, index=None, offsets=None, direction=None, properties=None, pragmas=None, uindices=None)[source]

Implement a for-loop over nodes.

Parameters: nodes – Single or list of Node objects defining the loop body. dimension – Dimension object over which to iterate. limits – Limits for the iteration space, either the loop size or a tuple of the form (start, finish, stepping). index – Symbol to be used as iteration variable. offsets – A 2-tuple of start and end offsets to honour in the loop. direction – The IterationDirection of the Iteration. Defaults to Forward. properties – A bag of IterationProperty objects, decorating the Iteration (sequential, parallel, vectorizable, …). pragmas – A bag of pragmas attached to this Iteration. uindices – a bag of DerivedDimensions with dimension as root parent, representing additional Iteration variables with unbounded extreme (hence the “unbounded indices”, shortened as “uindices”).
bounds(start=None, finish=None)[source]

Return the start and end points of the Iteration if the limits are available (either statically known or provided through start/ finish). None is used as a placeholder in the returned 2-tuple if a limit is unknown.

defines

Return any symbols defined in the Iteration header.

dimensions

Return all Dimension objects used in the Iteration header.

end(finish=None)[source]

Return the end point of the Iteration if the upper limit is known, None otherwise.

extent(start=None, finish=None)[source]

Return the number of iterations executed if the limits are known, None otherwise.

free_symbols

Return all Symbol objects used in the header of this Iteration.

functions

Return all Function objects used in the Iteration header.

is_Affine
is_Elementizable
is_Iteration = True
is_Parallel
is_ParallelAtomic
is_ParallelRelaxed
is_Remainder
is_Sequential
is_Vectorizable
is_Wrappable
retag(tag_value=None)[source]

Create a new Iteration object which is identical to self, except for the tag. If provided, tag_value is used as new tag; otherwise, an internally generated tag is used.

start(start=None)[source]

Return the start point of the Iteration if the lower limit is known, None otherwise.

symbolic_bounds

Return a 2-tuple representing the symbolic bounds of the object.

symbolic_end

Return the symbolic end of the Iteration.

symbolic_extent

Return the symbolic extent of the Iteration.

symbolic_incr

Return the symbolic increment of the Iteration.

symbolic_start

Return the symbolic start of the Iteration.

tag
write

Return all Function objects written to in this Iteration

class devito.ir.iet.nodes.List(header=None, body=None, footer=None)[source]

A sequence of nodes.

is_List = True
class devito.ir.iet.nodes.LocalExpression(expr)[source]

A node encapsulating a SymPy equation which also defines its LHS.

defines

Return any symbols an LocalExpression may define.

class devito.ir.iet.nodes.TimedList(timer, lname, body)[source]

Wrap a Node with C-level timers.

free_symbols

Return all Symbol objects used by this Node.

name
timer
class devito.ir.iet.nodes.MetaCall(root, local)

Bases: tuple

Metadata for Callables. root is a pointer to the callable Iteration/Expression tree. local is a boolean indicating whether the definition of the callable is known or not.

local

Alias for field number 1

root

Alias for field number 0

class devito.ir.iet.nodes.ArrayCast(function)[source]

A node encapsulating a cast of a raw C pointer to a multi-dimensional array.

defines

Return the base symbol an ArrayCast defines.

free_symbols

Return the symbols required to perform an ArrayCast.

This includes the AbstractFunction object that defines the data, as well as the dimension sizes.

functions

Return all Function objects used by this ArrayCast

class devito.ir.iet.nodes.ForeignExpression(expr, dtype, **kwargs)[source]

A node representing a SymPy FunctionFromPointer expression.

dtype
is_ForeignExpression = True
is_Increment

bool(x) -> bool

Returns True when the argument x is true, False otherwise. The builtins True and False are the only two instances of the class bool. The class bool is a subclass of the class int, and cannot be subclassed.

is_scalar

Return True if a scalar expression, False otherwise.

is_tensor

Return True if a tensor expression, False otherwise.

output

Return the symbol written by this Expression.

write

Return the function written by this Expression.

class devito.ir.iet.nodes.Section(name, body=None)[source]

A sequence of nodes.

Functionally, a Section is identical to a List; that is, they generate the same code (i.e., their body). However, a Section should be used to define sub-trees that, for some reasons, have a relevance within the IET (e.g., groups of statements that logically represent the same computation unit).

is_Sequence = True
roots
class devito.ir.iet.nodes.HaloSpot(halo_scheme, body=None, properties=None)[source]
fmapper
is_HaloSpot = True
is_Redundant
mask
class devito.ir.iet.nodes.IterationTree[source]

Bases: tuple

Represent a sequence of nested :class:Iterations.

inner
root
class devito.ir.iet.nodes.ExpressionBundle(shape, ops, traffic, body=None)[source]

A sequence of :class:Expressions.

exprs
is_ExpressionBundle = True
class devito.ir.iet.nodes.Increment(expr)[source]

A node representing a += increment.

is_Increment = True

## devito.ir.iet.properties module¶

devito.ir.iet.properties.AFFINE = affine

All Indexeds' access functions using the Iteration dimension d are affine in d. Further, the Iteration does not contain any Indexed varying in d used to indirectly access some other Indexed.

devito.ir.iet.properties.ELEMENTAL = elemental

The Iteration can be pulled out to an elemental function.

class devito.ir.iet.properties.HaloSpotProperty(name, val=None)[source]

A HaloSpot decorator.

class devito.ir.iet.properties.IterationProperty(name, val=None)[source]

An Iteration decorator.

devito.ir.iet.properties.PARALLEL = parallel

The Iteration can be executed in parallel w/o need for synchronization.

devito.ir.iet.properties.PARALLEL_IF_ATOMIC = parallel_if_atomic

The Iteration can be executed in parallel as long as all increments are guaranteed to be atomic.

devito.ir.iet.properties.REDUNDANT = redundant

The HaloSpot is redundant given that some other HaloSpots already take care of updating the data accessed in the sub-tree.

devito.ir.iet.properties.REMAINDER = remainder

The Iteration implements a remainder/peeler loop.

devito.ir.iet.properties.SEQUENTIAL = sequential

The Iteration is inherently serial, i.e., its iterations cannot run in parallel.

devito.ir.iet.properties.VECTOR = vector-dim

The Iteration can be SIMD-vectorized.

devito.ir.iet.properties.WRAPPABLE = wrappable

The Iteration implements modulo buffered iteration and its expressions are so that one or more buffer slots can be dropped without affecting correctness. For example, u[t+1, …] = f(u[t, …], u[t-1, …]) –> u[t-1, …] = f(u[t, …], u[t-1, …]).

devito.ir.iet.properties.ntags()[source]
devito.ir.iet.properties.tagger(i)[source]

## devito.ir.iet.scheduler module¶

devito.ir.iet.scheduler.iet_build(stree)[source]

Create an Iteration/Expression tree (IET) from a ScheduleTree. The nodes in the returned IET are decorated with properties deriving from data dependence analysis.

devito.ir.iet.scheduler.iet_insert_C_decls(iet, func_table=None)[source]

Given an Iteration/Expression tree iet, build a new tree with the necessary symbol declarations. Declarations are placed as close as possible to the first symbol use.

Parameters: iet – The input Iteration/Expression tree. func_table – (Optional) a mapper from callable names within iet to :class:Callables.

## devito.ir.iet.utils module¶

devito.ir.iet.utils.filter_iterations(tree, key=<function <lambda>>, stop=<function <lambda>>)[source]

Given an iterable of Iteration objects, return a new list containing all items such that key(o) is True.

This function accepts an optional argument stop. This may be either a lambda function, specifying a stop criterium, or any of the following special keywords:

* 'any': Return as soon as key(o) is False and at least one
item has been collected.
* 'asap': Return as soon as at least one item has been collected and
all items for which key(o) is False have been encountered.


It is useful to specify a stop criterium when one is searching the first Iteration in an Iteration/Expression tree for which a given property does not hold.

devito.ir.iet.utils.retrieve_iteration_tree(node, mode='normal')[source]

Return a list of all Iteration sub-trees rooted in node. For example, given the Iteration tree:

Iteration i
expr0
Iteration j
Iteraion k
expr1
Iteration p
expr2


Return the list:

[(Iteration i, Iteration j, Iteration k), (Iteration i, Iteration p)]

Parameters: node – The searched Iteration/Expression tree. mode – Accepted values are ‘normal’ (default) and ‘superset’, in which case iteration trees that are subset of larger iteration trees are dropped.
devito.ir.iet.utils.compose_nodes(nodes, retrieve=False)[source]

Build an Iteration/Expression tree by nesting the nodes in nodes.

devito.ir.iet.utils.derive_parameters(nodes, drop_locals=False)[source]

Derive all input parameters (function call arguments) from an IET by collecting all symbols not defined in the tree itself.

## devito.ir.iet.visitors module¶

Visitor hierarchy to inspect and/or create IETs.

The main Visitor class is adapted from https://github.com/coneoproject/COFFEE.

class devito.ir.iet.visitors.FindNodes(match, mode='type')[source]

Bases: devito.ir.iet.visitors.Visitor

classmethod default_retval()[source]

A method that returns an object to use to populate return values.

If your visitor combines values in a tree-walk, it may be useful to provide a object to combine the results into. default_retval() may be defined by the visitor to be called to provide an empty object of appropriate type.

rules = {'scope': <function FindNodes.<lambda> at 0x1142eca60>, 'type': <function FindNodes.<lambda> at 0x1142ec9d8>}
visit_Node(o, ret=None)[source]
visit_object(o, ret=None)[source]
visit_tuple(o, ret=None)[source]
class devito.ir.iet.visitors.FindSections[source]

Bases: devito.ir.iet.visitors.Visitor

classmethod default_retval()[source]

A method that returns an object to use to populate return values.

If your visitor combines values in a tree-walk, it may be useful to provide a object to combine the results into. default_retval() may be defined by the visitor to be called to provide an empty object of appropriate type.

visit_Call(o, ret=None, queue=None)
visit_Element(o, ret=None, queue=None)
visit_Expression(o, ret=None, queue=None)[source]
visit_Iteration(o, ret=None, queue=None)[source]
visit_Node(o, ret=None, queue=None)[source]
visit_tuple(o, ret=None, queue=None)[source]
class devito.ir.iet.visitors.FindSymbols(mode='symbolics')[source]

Bases: devito.ir.iet.visitors.Visitor

classmethod default_retval()[source]

A method that returns an object to use to populate return values.

If your visitor combines values in a tree-walk, it may be useful to provide a object to combine the results into. default_retval() may be defined by the visitor to be called to provide an empty object of appropriate type.

rules = {'defines': <function FindSymbols.<lambda> at 0x1142ec6a8>, 'free-symbols': <function FindSymbols.<lambda> at 0x1142ec620>, 'symbolics': <function FindSymbols.<lambda> at 0x1142ec598>}
visit_ArrayCast(o)
visit_Block(o)
visit_Call(o)
visit_Conditional(o)
visit_Expression(o)[source]
visit_Iteration(o)[source]
visit_tuple(o)[source]
class devito.ir.iet.visitors.MapExpressions[source]

Map Expression and Call objects in the Iteration/Expression tree to their respective section.

visit_Call(o, ret=None, queue=None)[source]
visit_Element(o, ret=None, queue=None)
visit_Expression(o, ret=None, queue=None)
class devito.ir.iet.visitors.IsPerfectIteration[source]

Bases: devito.ir.iet.visitors.Visitor

Return True if an Iteration defines a perfect loop nest, False otherwise.

visit_Conditional(o, found=False, **kwargs)[source]
visit_Iteration(o, found=False, nomore=False)[source]
visit_Node(o, found=False, **kwargs)[source]
visit_object(o, **kwargs)[source]
visit_tuple(o, **kwargs)[source]
class devito.ir.iet.visitors.XSubs(mapper=None, replacer=None)[source]

Transformer that performs substitutions on Expressions in a given tree, akin to SymPy's subs.

Parameters: mapper – (Optional) dictionary defining the substitutions. replacer – (Optional) a function to perform the substitution. Defaults to SymPy’s subs.
visit_Expression(o)[source]
devito.ir.iet.visitors.printAST(node, verbose=True)[source]
class devito.ir.iet.visitors.CGen[source]

Bases: devito.ir.iet.visitors.Visitor

Return a representation of the Iteration/Expression tree as a :module:cgen tree.

visit_ArrayCast(o)[source]

Build cgen type casts for an AbstractFunction.

visit_Block(o)[source]
visit_Call(o)[source]
visit_Callable(o)[source]
visit_Conditional(o)[source]
visit_Element(o)[source]
visit_Expression(o)[source]
visit_ForeignExpression(o)[source]
visit_Increment(o)[source]
visit_Iteration(o)[source]
visit_List(o)[source]
visit_LocalExpression(o)[source]
visit_Operator(o)[source]
visit_tuple(o)[source]
class devito.ir.iet.visitors.Transformer(mapper={}, nested=False)[source]

Bases: devito.ir.iet.visitors.Visitor

Given an Iteration/Expression tree T and a mapper from nodes in T to a set of new nodes L, M : N –> L, build a new Iteration/Expression tree T’ where a node n in N is replaced with M[n].

In the special case in which M[n] is None, n is dropped from T’.

In the special case in which M[n] is an iterable of nodes, n is “extended” by pre-pending to its body the nodes in M[n].

visit_Node(o, **kwargs)[source]
visit_Operator(o, **kwargs)[source]
visit_list(o, **kwargs)
visit_object(o, **kwargs)[source]
visit_tuple(o, **kwargs)[source]
class devito.ir.iet.visitors.FindAdjacent(match)[source]

Bases: devito.ir.iet.visitors.Visitor

classmethod default_retval()[source]

A method that returns an object to use to populate return values.

If your visitor combines values in a tree-walk, it may be useful to provide a object to combine the results into. default_retval() may be defined by the visitor to be called to provide an empty object of appropriate type.

handler(o, parent=None, ret=None)[source]
visit_Node(o, parent=None, ret=None)[source]
visit_object(o, parent=None, ret=None)[source]
visit_tuple(o, parent=None, ret=None)[source]
class devito.ir.iet.visitors.MapIteration[source]

Map each Iteration object in the Iteration/Expression tree to the enclosed Expression and Call objects.

visit_Call(o, ret=None, queue=None)[source]
visit_Element(o, ret=None, queue=None)
visit_Expression(o, ret=None, queue=None)