control_flow Package

control_flow Package

block Module

cfstats Module

class numba.control_flow.cfstats.Argument(lhs, rhs, entry)

Bases: numba.control_flow.cfstats.NameAssignment

class numba.control_flow.cfstats.AttributeAssignment(assmnt)

Bases: object

Assignment to some attribute. We need to detect assignments in the constructor of extension types.

class numba.control_flow.cfstats.ExceptionDescr(entry_point, finally_enter=None, finally_exit=None)

Bases: object

Exception handling helper.

entry_point ControlBlock Exception handling entry point finally_enter ControlBlock Normal finally clause entry point finally_exit ControlBlock Normal finally clause exit point

class numba.control_flow.cfstats.LoopDescr(next_block, loop_block)

Bases: object

class numba.control_flow.cfstats.NameAssignment(lhs, rhs, entry, assignment_node, warn_unused=True)

Bases: object

infer_type(scope)

is_assignment = True

type_dependencies(scope)

class numba.control_flow.cfstats.NameDeletion(lhs, entry)

Bases: numba.control_flow.cfstats.NameAssignment

class numba.control_flow.cfstats.NameReference(node, entry)

Bases: object

class numba.control_flow.cfstats.PhiNode(block, variable)

Bases: numba.nodes.basenodes.Node

add(block, assmnt)

add_incoming_block(block)

entry

find_incoming()

class numba.control_flow.cfstats.StatementDescr

Bases: object

is_assignment = False

class numba.control_flow.cfstats.Uninitialized

Bases: object

control_flow Module

Control flow for the AST backend.

Adapted from Cython/Compiler/FlowControl.py

class numba.control_flow.control_flow.AssignmentList

class numba.control_flow.control_flow.ControlBlock(id, label='empty', have_code=True, is_expr=False, is_exit=False, pos=None, is_fabricated=False)

Bases: numba.nodes.cfnodes.LowLevelBasicBlockNode

Control flow graph node. Sequence of assignments and name references. This is simultaneously an AST node.

children set of children nodes parents set of parent nodes positions set of position markers

stats list of block statements gen dict of assignments generated by this block bound set of entries that are definitely bounded in this block

Example:

a = 1 b = a + c # ‘c’ is already bounded or exception here

stats = [Assignment(a), NameReference(a), NameReference(c),

Assignment(b)]

gen = {Entry(a): Assignment(a), Entry(b): Assignment(b)} bound = set([Entry(a), Entry(c)])

add_child(block)

delete(flow)

Delete a block from the cfg.

detach()

Detach block from parents and children.

empty()

reparent(new_block)

Re-parent all children to the new block

class numba.control_flow.control_flow.ControlFlow(env, source_descr)

Bases: object

Control-flow graph.

entry_point ControlBlock entry point for this graph exit_point ControlBlock normal exit point block ControlBlock current block blocks set children nodes entries set tracked entries loops list stack for loop descriptors exceptions list stack for exception descriptors

add_exit(exit_block)

Add an exit block after visiting the body

compute_dominance_frontier()

Compute the dominance frontier for all blocks. This indicates for each block where dominance stops in the CFG. We use this as the place to insert Φ functions, since at the dominance frontier there are multiple control flow paths to the block, which means multiple variable definitions can reach there.

compute_dominators()

Compute the dominators for the CFG, i.e. for each basic block the set of basic blocks that dominate that block. This mean from the entry block to that block must go through the blocks in the dominator set.

dominators(x) = {x} ∪ (∩ dominators(y) for y ∈ preds(x))

exit_block(parent=None, **kwargs)

Create a floating exit block. This can later be added to self.blocks. This is useful to ensure topological order.

immediate_dominator(x)

The dominator of x that is dominated by all other dominators of x. This is the block that has the largest dominator set.

initialize()

Set initial state, map assignments to bits.

initialize_sets()

Set initial state, run after SSA. There is only ever one live definition of a variable in a block, so we can simply track input and output definitions as the Variable/Entry they came as.

is_listcomp_var(name)

is_tracked(entry)

map_one(istate, entry)

Map the bitstate of a variable to the definitions it represents

mark_argument(lhs, rhs, entry)

mark_assignment(lhs, rhs, entry, assignment, warn_unused=True)

mark_deletion(node, entry)

mark_position(node)

Mark position, will be used to draw graph nodes.

mark_reference(node, entry)

newblock(parent=None, **kwargs)

Create floating block linked to parent if given. Does NOT set the current block to the new block.

nextblock(parent=None, **kwargs)

Create child block linked to current or parent if given. Sets the current block to the new block.

normalize()

Delete unreachable and orphan blocks.

reaching_definitions()

Per-block reaching definitions analysis.

rename_assignments(block)

update_for_ssa(ast, symbol_table)

1. Compute phi nodes

   for each variable v

   1. insert empty phi nodes in dominance frontier of each block that defines v
   2. this phi defines a new assignment in each block in which it is inserted, so propagate (recursively)

2. Reaching definitions

   Set block-local symbol table for each block. This is a rudimentary form of reaching definitions, but we can do it in a single pass because all assignments are known (since we inserted the phi functions, which also count as assignments). This means the output set is known up front for each block and never changes. After setting all output sets, we can compute the input sets in a single pass:

   1. compute output sets for each block
   2. compute input sets for each block

3. Update phis with incoming variables. The incoming variables are last assignments of the predecessor blocks in the CFG.

class numba.control_flow.control_flow.ControlFlowAnalysis(context, func, ast, allow_rebind_args, env, **kwargs)

Bases: numba.visitors.NumbaTransformer

Control flow analysis pass that builds the CFG and injects the blocks into the AST (but not all blocks are injected).

The CFG must be build in topological DFS order, e.g. the ‘if’ condition block must precede the clauses and the clauses must precede the exit.

exit_block(exit_block, node)

function_level = 0

graphviz = False

gv_ctx = None

handle_inner_function(node)

Create assignment code for inner functions and mark the assignment

initialize_symtab(allow_rebind_args)

Populate the symbol table with variables and set their renaming status.

Variables appearing in locals, or arguments typed through the ‘jit’ decorator are not renameable.

mark_assignment(lhs, rhs=None, assignment=None, warn_unused=True)

mark_position(node)

Mark position if DOT output is enabled.

render_gv(node)

set_default_directives()

Set some defaults for warnings

source_descr = None

visit(node)

visit_Assign(node)

visit_AugAssign(node)

Inplace assignment.

Resolve a += b to a = a + b. Set ‘inplace_op’ attribute of the Assign node so later stages may recognize inplace assignment.

Do this now, so that we can correctly mark the RHS reference.

visit_Break(node)

visit_Continue(node)

visit_DictComp(node)

visit_For(node)

visit_FunctionDef(node)

visit_GeneratorExp(node)

visit_If(node)

visit_ImportFrom(node)

visit_ListComp(node)

Rewrite list comprehensions to the equivalent for loops.

AST syntax:

ListComp(expr elt, comprehension* generators) comprehension = (expr target, expr iter, expr* ifs)

‘ifs’ represent a chain of ANDs

visit_MaybeUnusedNode(node)

visit_Name(old_node)

visit_Print(node)

visit_Raise(node)

visit_Return(node)

visit_SetComp(node)

visit_Suite(node)

visit_While(node)

visit_With(node)

visit_arg(old_node, lineno, col_offset)

class numba.control_flow.control_flow.ExitBlock(id, label='empty', have_code=True, is_expr=False, is_exit=False, pos=None, is_fabricated=False)

Bases: numba.control_flow.control_flow.ControlBlock

Non-empty exit point block.

empty()

class numba.control_flow.control_flow.FuncDefExprNode(**kwargs)

Bases: numba.nodes.basenodes.Node

Wraps an inner function node until the closure code kicks in.

debug Module

delete_cfnode Module

class numba.control_flow.delete_cfnode.DeleteStatement(flow)

Bases: numba.visitors.NumbaVisitor

Delete a (compound) statement that contains basic blocks. The statement must be at the start of the entry block.

idom: the immediate dominator of

visit_ControlBlock(node)

visit_For(node)

visit_If(node)

visit_Name(node)

visit_While(node)

graphviz Module

class numba.control_flow.graphviz.GV(name, flow)

Bases: object

Graphviz DOT renderer.

format_phis(block)

render(fp, ctx, annotate_defs=False)

class numba.control_flow.graphviz.GVContext

Bases: object

Graphviz subgraph object.

add(child)

escape(text)

extract_sources(block)

nodeid(block)

render(fp, name, annotate_defs=False)

Render graphviz dot graph

numba.control_flow.graphviz.get_png_output_name(dot_output)

numba.control_flow.graphviz.render_gv(node, gv_ctx, flow, current_directives)

numba.control_flow.graphviz.write_dotfile(current_directives, dot_output, gv_ctx)

numba.control_flow.graphviz.write_image(dot_output)

reaching Module

class numba.control_flow.reaching.CFWarner(message_collection, directives)

Bases: object

Generate control flow related warnings.

check_uninitialized(references)

Find uninitialized references and cf-hints

warn_unreachable(node)

Generate a warning for unreachable code

warn_unused_entries(flow)

Generate warnings for unused variables or arguments. This is issues when an argument or variable is unused entirely in the function.

warn_unused_result(assignments)

Warn about unused variable definitions. This is issued for individual definitions, e.g.

i = 0 # this definition generates a warning i = 1 print i

numba.control_flow.reaching.allow_null(node)

numba.control_flow.reaching.check_definitions(env, flow, warner)

ssa Module

numba.control_flow.ssa.handle_phis(flow)

Update all our phi nodes after translation is done and all Variables have their llvm values set.

numba.control_flow.ssa.iter_phi_vars(flow)

Iterate over all phi nodes

numba.control_flow.ssa.iter_phis(flow)

Iterate over all phi nodes

numba.control_flow.ssa.kill_phi(block, phi)

numba.control_flow.ssa.kill_unused_phis(cfg)

Used before running type inference.

Kill phis which are not referenced. We need to do this bottom-up, i.e. in reverse topological dominator-tree order, since in SSA a definition always lexically precedes a reference.

This is important, since it kills any unnecessary promotions (e.g. ones to object, which LLVM wouldn’t be able to optimize out).

TODO: Kill phi cycles, or do reachability analysis before inserting phis.

numba.control_flow.ssa.process_incoming(phi_node)

Add all incoming phis to the phi instruction.

Handle promotions by using the promoted value from the incoming block. E.g.

bb0: if C: bb1: x = 2

else:

bb2: x = 2.0

bb3: x = phi(x_bb1, x_bb2)

has a promotion for ‘x’ in basic block 1 (from int to float).

numba.control_flow.ssa.specialize_phi(node)

numba.control_flow.ssa.specialize_ssa(funcdef)

Handle phi nodes:

1. Handle incoming variables which are not initialized. Set incoming_variable.uninitialized_value to a constant ‘bad’ value (e.g. 0xbad for integers, NaN for floats, NULL for objects)

2. Handle incoming variables which need promotions. An incoming variable needs a promotion if it has a different type than the the phi. The promotion happens in each ancestor block that defines the variable which reaches us.

   Promotions are set separately in the symbol table, since the ancestor may not be our immediate parent, we cannot introduce a rename and look up the latest version since there may be multiple different promotions. So during codegen, we first check whether incoming_type == phi_type, and otherwise we look up the promotion in the parent block or an ancestor.

Subpackages