Datastructures API Reference

BasicBlocks

class numba_scfg.core.datastructures.basic_block.BasicBlock(name: str, _jump_targets: Tuple[str, ...] = (), backedges: Tuple[str, ...] = ())

Basic building block of an SCFG graph.

The BasicBlock class represents an atomic basic block in an SCFG.

name

The corresponding name for this block.

Type:: str

_jump_targets

Jump targets (branch destinations) for this block.

Type:: Tuple[str]

backedges

Backedges for this block.

Type:: Tuple[str]

declare_backedge(target: str) → BasicBlock

Declare one of the jump targets as a backedge of this block.

Parameters:: target (str) – The jump target that is to be declared as a backedge.
Returns:: basic_block – The resulting block.
Return type:: BasicBlock

property fallthrough: bool

Indicates whether this block has a single fallthrough jump target.

Returns:: fallthrough – True if the current block is a fallthorough block, False if it isn’t.
Return type:: bool

property is_exiting: bool

Indicates whether this block is an exiting block, i.e., it does not have any jump targets.

Returns:: is_exiting – True if the current block is an exiting block, False if it isn’t.
Return type:: bool

property jump_targets: Tuple[str, ...]

Retrieves the jump targets for this block, excluding any jump targets that are also backedges.

Returns:: jump_targets – Tuple of jump targets of this block, (exludes backedges). Ordered according to their position.
Return type:: Tuple[str]

replace_backedges(backedges: Tuple[str, ...]) → BasicBlock

Replaces back edges of this block by the given tuple.

This method replaces the back edges of the current BasicBlock. The provided back edges must be in the same order as their intended original replacements.

Parameters:: backedges (Tuple) – The new back edges tuple. Must be ordered.
Returns:: basic_block – The resulting BasicBlock.
Return type:: BasicBlock

replace_jump_targets(jump_targets: Tuple[str, ...]) → BasicBlock

Replaces jump targets of this block by the given tuple.

This method replaces the jump targets of the current BasicBlock. The provided jump targets must be in the same order as their intended original replacements.

Note that replacing jump targets will not replace the backedge tuple, so replacement for any jump targets that is declared as a backedge needs to be updated separately using replace_backedges

Parameters:: jump_targets (Tuple) – The new jump target tuple. Must be ordered.
Returns:: basic_block – The resulting BasicBlock.
Return type:: BasicBlock

class numba_scfg.core.datastructures.basic_block.PythonASTBlock(name: str, _jump_targets: Tuple[str, ...]=(), backedges: Tuple[str, ...]=(), begin: int = -1, end: int = -1, tree: List[AST] = <factory>)

The PythonASTBlock class is a subclass of the BasicBlock that represents basic blocks with Python AST.

begin

The starting line.

Type:: int

end

The ending line.

Type:: int

class numba_scfg.core.datastructures.basic_block.PythonBytecodeBlock(name: str, _jump_targets: Tuple[str, ...] = (), backedges: Tuple[str, ...] = (), begin: int = -1, end: int = -1)

The PythonBytecodeBlock class is a subclass of the BasicBlock that represents basic blocks with Python bytecode.

begin

The starting bytecode offset.

Type:: int

end

The bytecode offset immediately after the last bytecode of the block.

Type:: int

get_instructions(bcmap: Dict[int, Instruction]) → List[Instruction]

Retrieves a list of dis.Instruction objects corresponding to the instructions within the bytecode block.

In this method, The bcmap parameter is a dictionary mapping bytecode offsets to dis.Instruction objects. This method iterates over the bytecode offsets within the begin and end range, retrieves the corresponding dis.Instruction objects from bcmap, and returns a list of these instructions.

Parameters:: bcmap (Dict[int, dis.Instruction]) – Dictionary mapping bytecode offsets to dis.Instruction objects.
Returns:: out – The requested instructions according to bcmap between begin and end offsets.
Return type:: List[dis.Instruction]

class numba_scfg.core.datastructures.basic_block.RegionBlock(name: str, _jump_targets: Tuple[str, ...] = (), backedges: Tuple[str, ...] = (), kind: str | None = None, parent_region: RegionBlock | None = None, header: str | None = None, subregion: SCFG | None = None, exiting: str | None = None)

The RegionBlock is a BasicBlock that represents a region in a structured control flow graph (SCFG) object.

kind

The kind of region. Can be ‘head’, ‘tail’, ‘branch’, ‘loop’ or ‘meta’ strings.

Type:: str

parent_region

The parent region of this region as per the SCFG.

Type:: “RegionBlock”

header

The header node of the region.

Type:: str

subregion

The subgraph as an independent SCFG. Note that in case of subregions the exiting node may point to blocks outside of the current SCFG object.

Type:: “SCFG”

exiting

The exiting node of the region.

Type:: str

replace_exiting(new_exiting: str) → None

This method performs a inplace replacement of the header block.

Parameters:: new_exiting (str) – The new exiting block of the region represented by the RegionBlock.

replace_header(new_header: str) → None

This method performs a inplace replacement of the header block.

Parameters:: new_header (str) – The new header block of the region represented by the RegionBlock.

class numba_scfg.core.datastructures.basic_block.SyntheticAssignment(name: str, _jump_targets: Tuple[str, ...]=(), backedges: Tuple[str, ...]=(), variable_assignment: Dict[str, int]=<factory>)

The SyntheticAssignment class represents a artificially added assignment block in a structured control flow graph (SCFG).

This block is responsible for giving variables their values, once the respective block is executed.

variable_assignment

A dictionary representing the variable assignments. It maps the variable name to the value that is is assigned when the block is executed.

Type:: dict

class numba_scfg.core.datastructures.basic_block.SyntheticBlock(name: str, _jump_targets: Tuple[str, ...] = (), backedges: Tuple[str, ...] = ()): The SyntheticBlock represents a artificially added block in a structured control flow graph (SCFG).

class numba_scfg.core.datastructures.basic_block.SyntheticBranch(name: str, _jump_targets: Tuple[str, ...]=(), backedges: Tuple[str, ...]=(), variable: str = '', branch_value_table: Dict[int, str]=<factory>)

The SyntheticBranch class represents a artificially added branch block in a structured control flow graph (SCFG).

variable

The variable on the basis of which branching will happen when the current block is executed.

Type:: str

branch_value_table

The value table maps variable values to the repective jump target to be executed on the basis of that value.

Type:: dict

replace_jump_targets(jump_targets: Tuple[str, ...]) → BasicBlock

Replaces jump targets of this block by the given tuple.

This method replaces the jump targets of the current BasicBlock. The provided jump targets must be in the same order as their intended original replacements. Additionally also updates the branch value table of the branch block.

Note that replacing jump targets will not replace the backedge tuple, so replacement for any jump targets that is declared as a backedge needs to be updated separately using replace_backedges.

Parameters:: jump_targets (Tuple) – The new jump target tuple. Must be ordered.
Returns:: basic_block – The resulting BasicBlock.
Return type:: BasicBlock

class numba_scfg.core.datastructures.basic_block.SyntheticExit(name: str, _jump_targets: Tuple[str, ...] = (), backedges: Tuple[str, ...] = ()): The SyntheticExit class represents a artificially added exit block in a structured control flow graph (SCFG).

class numba_scfg.core.datastructures.basic_block.SyntheticExitBranch(name: str, _jump_targets: Tuple[str, ...]=(), backedges: Tuple[str, ...]=(), variable: str = '', branch_value_table: Dict[int, str]=<factory>): The SyntheticExitBranch class represents a artificially added exit branch block in a structured control flow graph (SCFG).

class numba_scfg.core.datastructures.basic_block.SyntheticExitingLatch(name: str, _jump_targets: Tuple[str, ...]=(), backedges: Tuple[str, ...]=(), variable: str = '', branch_value_table: Dict[int, str]=<factory>): The SyntheticExitingLatch class represents a artificially added exiting latch block in a structured control flow graph (SCFG).

class numba_scfg.core.datastructures.basic_block.SyntheticFill(name: str, _jump_targets: Tuple[str, ...] = (), backedges: Tuple[str, ...] = ()): The SyntheticFill class represents a artificially added fill block in a structured control flow graph (SCFG).

class numba_scfg.core.datastructures.basic_block.SyntheticHead(name: str, _jump_targets: Tuple[str, ...]=(), backedges: Tuple[str, ...]=(), variable: str = '', branch_value_table: Dict[int, str]=<factory>): The SyntheticHead class represents a artificially added head block in a structured control flow graph (SCFG).

class numba_scfg.core.datastructures.basic_block.SyntheticReturn(name: str, _jump_targets: Tuple[str, ...] = (), backedges: Tuple[str, ...] = ()): The SyntheticReturn class represents a artificially added return block in a structured control flow graph (SCFG).

class numba_scfg.core.datastructures.basic_block.SyntheticTail(name: str, _jump_targets: Tuple[str, ...] = (), backedges: Tuple[str, ...] = ()): The SyntheticTail class represents a artificially added tail block in a structured control flow graph (SCFG).

ByteFlow

class numba_scfg.core.datastructures.byte_flow.ByteFlow(bc: Bytecode, scfg: SCFG)

ByteFlow class.

The ByteFlow class represents the bytecode and its relation with corresponding structured control flow graph (SCFG).

bc

The dis.Bytecode object representing the bytecode.

Type:: dis.Bytecode

scfg

The SCFG object representing the control flow of the bytecode.

Type:: SCFG

static from_bytecode(code: Callable) → ByteFlow

Creates a ByteFlow object from the given python function.

This method uses dis.Bytecode to parse the bytecode generated from the given Python function. It returns a ByteFlow object with the corresponding bytecode and SCFG.

Parameters:: code (Python Function) – The Python Function from which ByteFlow is to be generated.
Returns:: byteflow – The resulting ByteFlow object.
Return type:: ByteFlow

FlowInfo

class numba_scfg.core.datastructures.flow_info.FlowInfo(block_offsets: Set[int] = <factory>, jump_insts: Dict[int, ~typing.Tuple[int, ...]]=<factory>, last_offset: int = 0)

The FlowInfo class is responsible for converting bytecode into a ByteFlow object.

block_offsets

A set that marks the starting offsets of basic blocks in the bytecode.

Type:: Set[int]

jump_insts

A dictionary that contains jump instructions and their target offsets.

Type:: Dict[int, Tuple[int, …]]

last_offset

The offset of the last bytecode instruction.

Type:: int

build_basicblocks(end_offset: int | None = None) → SCFG

Builds a graph of basic blocks based on the flow information.

It creates a structured control flow graph (SCFG) object, assigns names to the blocks, and defines the block boundaries, jump targets, and backedges. It returns an SCFG object representing the control flow graph.

Parameters:: end_offset (int) – The byte offset of the last instruction.
Returns:: scfg – SCFG object corresponding to the bytecode contained within the current FlowInfo object.
Return type:: SCFG

static from_bytecode(bc: Bytecode) → FlowInfo

Static method that builds the structured control flow graph (SCFG) from the given dis.Bytecode object bc.

This method analyzes the bytecode instructions, marks the start of basic blocks, and records jump instructions and their target offsets. It builds the structured control flow graph (SCFG) from the given dis.Bytecode object and returns a FlowInfo object.

Parameters:: bc (dis.Bytecode) – Bytecode from which flowinfo is to be constructed.
Returns:: flowinfo – FlowInfo object representing the given bytecode.
Return type:: FlowInfo

SCFG classes

class numba_scfg.core.datastructures.scfg.AbstractGraphView

Abstract Graph View class.

The AbstractGraphView class serves as a template for graph views.

class numba_scfg.core.datastructures.scfg.ConcealedRegionView(scfg: SCFG)

Concealed Region View class.

The ConcealedRegionView represents a view of a SCFG where regions are “concealed” and treated as a single block.

Parameters:: scfg (SCFG) – The SCFG for which to instantiate the view.

scfg

The SCFG that the concealed region view is based on.

Type:: SCFG

region_view_iterator(head: str | None = None) → Iterator[str]

Region View Iterator.

This iterator is region aware, which means that regions are “concealed” and act as though they were a single block.

Parameters:: head (str, optional) – The head block (or region) from which to start iterating. If None is given, will discover the head automatically.
Returns:: blocks – An iterator over blocks (or regions)
Return type:: iter of str

class numba_scfg.core.datastructures.scfg.NameGenerator(kinds: dict[str, int]=<factory>)

Unique Name Generator.

The NameGenerator class is responsible for generating unique names for blocks, regions, and variables within the SCFG.

kinds

A dictionary that keeps track of the current index for each kind of name.

Type:: dict[str, int]

new_block_name(kind: str) → str

Generate a new unique name for a block of the specified kind.

This method checks if the given string ‘kind’ already exists in the kinds dictionary attribute. If it exists, the respective index is incremented, if it doesn’t then a new index (starting from zero) is asigned to the given kind. This ensures that the given name is unique by a combination of it’s kind and it’s index. It returns the generated name.

Parameters:: kind (str) – The kind of block for which name is being generated.
Returns:: name – Unique name for the given kind of block.
Return type:: str

new_region_name(kind: str) → str

Generate a new unique name for a region of the specified kind.

This method checks if the given string ‘kind’ already exists in the kinds dictionary attribute. If it exists, the respective index is incremented, if it doesn’t then a new index (starting from zero) is asigned to the given kind. This ensures that the given name is unique by a combination of it’s kind and it’s index. It returns the generated name.

Parameters:: kind (str) – The kind of region for which name is being generated.
Returns:: name – Unique name for the given kind of region.
Return type:: str

new_var_name(kind: str) → str

Generate a new unique name for a variable of the specified kind.

This method checks if the given string ‘kind’ already exists in the kinds dictionary attribute. If it exists, the respective index is incremented, if it doesn’t then a new index (starting from zero) is asigned to the given kind. This ensures that the given name is unique by a combination of it’s kind and it’s index. It returns the generated name.

Parameters:: kind (str) – The kind of variable for which name is being generated.
Returns:: name – Unique name for the given kind of variable.
Return type:: str

class numba_scfg.core.datastructures.scfg.SCFG(graph: MutableMapping[str, ~numba_scfg.core.datastructures.basic_block.BasicBlock]=<factory>, name_gen: NameGenerator = <factory>)

SCFG (Structured Control Flow Graph) class.

The SCFG class represents a map of names to blocks within the control flow graph.

graph

A dictionary that maps names to corresponding BasicBlock objects within the control flow graph.

Type:: Dict[str, BasicBlock]

name_gen

A NameGenerator object that provides unique names for blocks, regions, and variables.

Type:: NameGenerator

add_block(basic_block: BasicBlock) → None

Adds a BasicBlock object to the control flow graph.

Parameters:: basic_block (BasicBlock) – The basic_block parameter represents the block to be added.

static bcmap_from_bytecode(bc: Bytecode) → Dict[int, Instruction]

Static method that creates a bytecode map from a dis.Bytecode object.

Parameters:: bc (dis.Bytecode) – The ByteCode object to be converted.
Returns:: bcmap – The corresponding dictionary that maps bytecode offsets to instruction objects.
Return type:: Dict

compute_scc() → List[Set[str]]

Computes the strongly connected components (SCC) of the current SCFG.

This method of SCFG computes the strongly connected components of the graph using Tarjan’s algorithm. The implementation is at the scc function from the numba_scfg.networkx_vendored.scc module. It returns a list of sets, where each set represents an SCC in the graph. SCCs are useful for detecting loops in the graph.

Returns:: components – A list of sets of strongly connected components/BasicBlocks.
Return type:: List[Set[str]]

property concealed_region_view: ConcealedRegionView

A property that returns a ConcealedRegionView object, representing a concealed view of the control flow graph.

Returns:: region_view – A concealed view of the current SCFG.
Return type:: ConcealedRegionView

exclude_blocks(exclude_blocks: Set[str]) → Iterator[str]

Returns an iterator over the blocks in the SCFG with exclusions.

Returns an iterator over all nodes (blocks) in the control flow graph that are not present in the exclude_blocks set. It filters out the excluded blocks and yields the remaining blocks.

Parameters:: exclude_blocks (Set[str]) – Set of blocks to be excluded.
Returns:: blocks – An iterator over blocks (or regions) over the given SCFG with the specified blocks excluded.
Return type:: Iterator[str]

find_exiting_and_exits(subgraph: Set[str]) → Tuple[List[str], List[str]]

Finds exiting and exit blocks in a given subgraph.

Existing blocks are blocks inside the subgraph that have edges to blocks outside of the subgraph. Exit blocks are blocks outside the subgraph that have incoming edges from within the subgraph. Exiting blocks point to exits and exits and pointed to by exiting blocks.

Parameters:: subgraph (Set[str]) – The subgraph for which exit and exiting blocks are to be computed.
Returns:: (exiting, exits) – A tuple consisting of two entries the set of exiting blocks and set of exit blocks respectively.
Return type:: Tuple[Set[str], Set[str]]

find_head() → str

Finds the head block of the SCFG.

Assuming the SCFG is closed, this will find the block that no other blocks are pointing to.

Returns:: head – Name of the head block of the graph.
Return type:: str

find_headers_and_entries(subgraph: Set[str]) → Tuple[List[str], List[str]]

Finds entries and headers in a given subgraph.

Entries are blocks outside the subgraph that have an edge pointing to the subgraph headers. Headers are blocks that are part of the strongly connected subset and that have incoming edges from outside the subgraph. Entries point to headers and headers are pointed to by entries.

Parameters:: subgraph (Set[str]) – The subgraph for which headers and entries are to be computed.
Returns:: (headers, entries) – A tuple consisting of two entries the set of header blocks and set of entry blocks respectively.
Return type:: Tuple[Set[str], Set[str]]

static from_dict(graph_dict: Dict[str, Dict[str, List[str]]]) → Tuple[SCFG, Dict[str, str]]

Static method that creates an SCFG object from a dictionary representation.

This method takes a dictionary (graph_dict) representing the control flow graph and returns an SCFG object and a dictionary of block names. The input dictionary should have block indices as keys and dictionaries of block attributes as values.

Internally forwards the graph_dict to SCFGIO.from_dict() helper method.

Parameters:

graph_dict (dict) – The input dictionary from which the SCFG is to be constructed.

Returns:

scfg (SCFG) – The corresponding SCFG created using the dictionary representation.
block_dict (Dict[str, str]) – Dictionary of block names in YAML string corresponding to their representation/unique name IDs in the SCFG.

static from_yaml(yaml_string: str) → Tuple[SCFG, Dict[str, str]]

Static method that creates an SCFG object from a YAML representation.

This method takes a YAML string representing the control flow graph and returns an SCFG object and a dictionary of block names in YAML string corresponding to their representation/unique name IDs in the SCFG.

Internally forwards the yaml_string to SCFGIO.from_yaml() helper method.

Parameters:

yaml (str) – The input YAML string from which the SCFG is to be constructed.

Returns:

scfg (SCFG) – The corresponding SCFG created using the YAML representation.
block_dict (Dict[str, str]) – Dictionary of block names in YAML string corresponding to their representation/unique name IDs in the SCFG.

insert_SyntheticExit(new_name: str, predecessors: List[str], successors: List[str]) → None: Inserts a synthetic exit block into the SCFG. Parameters same as insert_block method.

See also

numba_scfg.core.datastructures.scfg.SCFG.insert_block

insert_SyntheticFill(new_name: str, predecessors: List[str], successors: List[str]) → None: Inserts a synthetic fill block into the SCFG. Parameters same as insert_block method.

See also

numba_scfg.core.datastructures.scfg.SCFG.insert_block

insert_SyntheticReturn(new_name: str, predecessors: List[str], successors: List[str]) → None: Inserts a synthetic return block into the SCFG. Parameters same as insert_block method.

See also

numba_scfg.core.datastructures.scfg.SCFG.insert_block

insert_SyntheticTail(new_name: str, predecessors: List[str], successors: List[str]) → None: Inserts a synthetic tail block into the SCFG. Parameters same as insert_block method.

See also

numba_scfg.core.datastructures.scfg.SCFG.insert_block

insert_block(new_name: str, predecessors: List[str], successors: List[str], block_type: type[SyntheticBlock]) → None

Inserts a new synthetic block into the SCFG between the given successors and predecessors.

This method inserts a new block between the specified successor and predecessor blocks. Edges between all the pairs of sucessor and predecessor blocks are replaced by edges going through the newly added block. (i.e. all outgoing edges from predecessors pointing to successor blocks, point towards the newly aded block and all incoming edges towards the successors originating from a predecessor, now originate from the newly added block instead).

Parameters:

new_name (str) – The name of the newly created block.
predecessors (List[str]) – The list of names of BasicBlock that act as predecessors for the block to be inserted.
successors (List[str]) – The list of names of BasicBlock that act as successors for the block to be inserted.
block_type (SyntheticBlock) – The type/class of the newly created block.

insert_block_and_control_blocks(new_name: str, predecessors: List[str], successors: List[str]) → None: Inserts a new block along with control blocks into the SCFG. This method is used for branching assignments. Parameters same as insert_block method.

See also

numba_scfg.core.datastructures.scfg.SCFG.insert_block

is_reachable_dfs(begin: str, end: str) → bool

Checks if the end block is reachable from the begin block in the SCFG.

This method performs a depth-first search (DFS) traversal from the begin block, following the edges of the graph. Returns True if the end block is reachable, and False otherwise.

Parameters:

begin (str) – The name of starting block for traversal.
end (str) – The name of end block for the traversal.

Returns:

result – True if the end block is reachable from begin block and False otherwise.

Return type:

bool

iter_subregions() → Generator[RegionBlock, SCFG, None]: Iterate over all subregions of this CFG.

join_returns() → None

Close the CFG.

A closed CFG is a CFG with a unique entry and exit node that have no predescessors and no successors respectively. Transformation is applied in-place.

join_tails_and_exits(tails: List[str], exits: List[str]) → Tuple[str, str]

Joins the tails and exits of the SCFG.

Parameters:

tails (List[str]) – The list of names of BasicBlock that act as tails in the SCFG.
exits (List[str]) – The list of names of BasicBlock that act as exits in the SCFG.

Returns:

solo_tail_name (str) – The name of the unique tail block in the modified SCFG.
solo_exit_name (str) – the name of the unique exit block in the modified SCFG.

remove_blocks(names: Set[str]) → None

Removes a BasicBlock object from the control flow graph.

Parameters:: names (Set[str]) – The set of names of BasicBlocks to be removed from the graph.

render() → None: Alias for view().

restructure_branch() → None

Apply BRANCH RESTRUCTURING transform.

Performs the operation to restructure branch constructs using the algorithm BRANCH RESTRUCTURING from section 4.2 of Bahmann2015. It applies an in-place restructuring operation to both the main SCFG and any subregions within it.

restructure_loop() → None

Apply LOOP RESTRUCTURING transform.

Performs the operation to restructure loop constructs using the algorithm LOOP RESTRUCTURING from section 4.1 of Bahmann2015. It applies an in-place restructuring operation to both the main SCFG and any subregions within it.

to_dict() → Dict[str, Dict[str, Any]]

Converts the SCFG object to a dictionary representation.

This method returns a dictionary representing the control flow graph. It iterates over the graph dictionary and generates a dictionary entry for each block, including jump targets and backedges if present.

Internally calls the SCFGIO.to_dict() helper method on current SCFG object.

Returns:: graph_dict – A dictionary representing the SCFG.
Return type:: Dict[Dict[…]]

to_yaml() → str

Converts the SCFG object to a YAML string representation.

The method returns a YAML string representing the control flow graph. It iterates over the graph dictionary and generates YAML entries for each block, including jump targets and backedges.

Internally calls the SCFGIO.to_yaml() helper method on current SCFG object.

Returns:: yaml – A YAML string representing the SCFG.
Return type:: str

view(name: str | None = None) → None

View the current SCFG as a external PDF file.

This method internally creates a SCFGRenderer corresponding to the current state of SCFG and calls it’s view method to view the graph as a graphviz generated external PDF file.

Parameters:: name (str) – Name to be given to the external graphviz generated PDF file.

class numba_scfg.core.datastructures.scfg.SCFGIO

Helper class for SCFG object transformation to and from various other formats. Currently supports YAML and dictionary format.

static extract_block_info(blocks: Dict[str, Dict[str, Any]], current_name: str, block_ref_dict: Dict[str, str], edges: Dict[str, List[str]], backedges: Dict[str, List[str]]) → Tuple[Dict[str, Any], str, Tuple[str, ...], Tuple[str, ...]]

Helper method to extract information from various components of an SCFG graph.

Parameters:

blocks (Dict[str, dict]) – Dictionary containing all the blocks info
current_name (str) – Name of the block whose information is to be extracted.
block_ref_dict (Dict[str, str]) – Dictionary of block names in YAML string corresponding to their representation/unique name IDs in the SCFG.
edges (Dict[str, list[str]]) – Dictionary representing the edges of the graph.
backedges (Dict[str, list[str]]) – Dictionary representing the backedges of the graph.

Returns:

block_info (Dict[str, Any]) – Dictionary containing information about the block.
block_type (str) – String representing the type of block.
block_edges (List[str]) – List of edges of the requested block.
block_backedges (List[str]) – List of backedges of the requested block.

static find_outer_graph(graph_dict: Dict[str, Dict[str, Any]]) → Set[str]

Helper method to find the outermost graph components of an SCFG object. (i.e. Components that aren’t contained in any other region)

Parameters:: graph_dict (dict) – The input dictionary from which the SCFG is to be constructed.
Returns:: outer_blocks – Set of all the block names that lie in the outer most graph or aren’t a part of any region.
Return type:: set[str]

static from_dict(graph_dict: Dict[str, Dict[str, Any]]) → Tuple[SCFG, Dict[str, str]]

Static method that creates an SCFG object from a dictionary representation.

This method takes a dictionary (graph_dict) representing the control flow graph and returns an SCFG object and a dictionary of block names. The input dictionary should have block indices as keys and dictionaries of block attributes as values.

Parameters:

graph_dict (dict) – The input dictionary from which the SCFG is to be constructed.

Returns:

scfg (SCFG) – The corresponding SCFG created using the dictionary representation.
block_ref_dict (Dict[str, str]) – Dictionary of block names in YAML string corresponding to their representation/unique name IDs in the SCFG.

static from_yaml(yaml_string: str) → Tuple[SCFG, Dict[str, str]]

Static helper method that creates an SCFG object from a YAML representation.

This method takes a YAML string representing the control flow graph and returns an SCFG object and a dictionary of block names in YAML string corresponding to their representation/unique name IDs in the SCFG.

Parameters:

yaml (str) – The input YAML string from which the SCFG is to be constructed.

Returns:

scfg (SCFG) – The corresponding SCFG created using the YAML representation.
block_dict (Dict[str, str]) – Dictionary of block names in YAML string corresponding to their representation/unique name IDs in the SCFG.

static make_scfg(graph_dict: Dict[str, Dict[str, Any]], curr_heads: Set[str], block_ref_dict: Dict[str, str], name_gen: NameGenerator, exiting: str | None = None) → SCFG

Helper method for building a single ‘level’ of the hierarchical structure in an SCFG graph at a time. Recursively calls itself to build the entire graph.

Parameters:

graph_dict (dict) – The input dictionary from which the SCFG is to be constructed.
curr_heads (set) – The set of blocks to start iterating from.
block_ref_dict (Dict[str, str]) – Dictionary of block names in YAML string corresponding to their representation/unique name IDs in the SCFG.
name_gen (NameGenerator) – The corresponding NameGenerator object for the SCFG object to be created.
exiting (str) – The exiting node for the current region being iterated.

Returns:

scfg – The corresponding SCFG created using the dictionary representation.

Return type:

SCFG

static to_dict(scfg: SCFG) → Dict[str, Dict[str, Any]]

Helper method to convert the SCFG object to a dictionary representation.

This method returns a dictionary representing the control flow graph. It iterates over the graph dictionary and generates a dictionary entry for each block, including jump targets and backedges if present.

Parameters:: scfg (SCFG) – The SCFG object to be transformed.
Returns:: graph_dict – A dictionary representing the SCFG.
Return type:: Dict[Dict[…]]

static to_yaml(scfg: SCFG) → str

Helper method to convert the SCFG object to a YAML string representation.

The method returns a YAML string representing the control flow graph. It iterates over the graph dictionary and generates YAML entries for each block, including jump targets and backedges.

Parameters:: scfg (SCFG) – The SCFG object to be transformed.
Returns:: yaml – A YAML string representing the SCFG.
Return type:: str

AST Transforms

numba_scfg.core.datastructures.ast_transforms.AST2SCFG(code: str | list[FunctionDef] | Callable[[...], Any]) → SCFG: Transform Python function into an SCFG.

class numba_scfg.core.datastructures.ast_transforms.AST2SCFGTransformer

The AST2SCFGTransformer class is responsible for transforming code in the form of a Python Abstract Syntax Tree (AST) into CFG/SCFG.

add_block(index: int) → None: Create block, add to CFG and set as current_block.

codegen(tree: list[type[AST]] | list[stmt]) → None

Recursively transform from a list of AST nodes.

The function is called ‘codegen’ as it generates an intermediary representation (IR) from an abstract syntax tree (AST). The name was chosen to honour the compiler writing tradition, where this type of recursive function is commonly called ‘codegen’.

handle_ast_node(node: type[AST] | stmt) → None: Dispatch an AST node to handle.

handle_bool_op(node: BoolOp) → Name: Handle boolean operations (and/or). Returns an ast.Name representing the result variable.

handle_expression(node: Any) → Any: Recursively handle expression nodes and their subexpressions. Returns the processed expression.

handle_for(node: For) → None

Handle for statement.

The Python ‘for’ statement needs to be decomposed into a series of equivalent Python statements, since the semantics of the statement can not be represented in the control flow graph (CFG) formalism of blocks with directed edges. We note that the for-loop in Python is effectively syntactic sugar for a generalised c-style while-loop. To our advantage, this while-loop can indeed be represented using the blocks and directed edges of the CFG formalism and allows us to transform the Python for-loop construct. This docstring explains the decomposition from for- into while-loop.

Remember that the for-loop has a target variable that will be assigned, an iterator to iterate over, a loop body and an else clause. The AST node has the following signature:

ast.For(target, iter, body, orelse, type_comment)

Remember also that Python for-loops can have an else-branch, that is executed upon regular loop conclusion:

def function(a: int) -> None:
    c = 0
    for i in range(10):
        c += i
        if i == a:
            i = 420  # set i arbitrarily
            break    # early exit, break from loop, bypass else
    else:
        c += 1       # loop conclusion, i.e. not hit break
return c, i

So, effectively, to decompose the for-loop, we need to setup the iterator by calling ‘iter(iter)’ and assign it to a variable, initialize the target variable to be None and then check if the iterator has a next value. If it does, we need to assign that value to the target variable, enter the body and then check the iterator again and again and again.. until there are no items left, at which point we execute the else-branch.

The Python for-loop usually waits for the iterator to raise a StopIteration exception to determine when the iteration has concluded. However, it is possible to use the ‘next()’ method with a second argument to avoid exception handling here. We do this so we don’t need to rely on being able to transform exceptions as part of this transformer:

i = next(iter, "__sentinel__")
if i != "__sentinel__":
    ...

Lastly, it is important to also remember that the target variable escapes the scope of the for loop:

>>> for i in range(1):
...     print("hello loop")
...
hello loop
>>> i
0
>>>

So, to summarize: we want to decompose a Python for loop into a while loop with some assignments and he target variable must escape the scope.

Consider again the following function:

def function(a: int) -> None:
    c = 0
    for i in range(10):
        c += i
        if i == a:
            i = 420
            break
    else:
        c += 1
    return c, i

This will be decomposed as the following construct that can be encoded using the available block and edge primitives of the CFG:

def function(a: int) -> None:
    c = 0
    __iterator_1__ = iter(range(10))  ## setup iterator
    i = None                          ## assign target, i
    while True:                       # loop until we break
        __iter_last_1__ = i           ## backup value of i
        i = next(__iterator_1__, '__sentinel__')  ## get next i
        if i != '__sentinel__':       ## regular iteration
            c += i                    # add to accumulator
            if i == a:                # check for early exit
                i = 420               # set i to some wild value
                break                 # early exit break while True
        else:                         # for-else clause
            i == __iter_last_1__      ## restore value of i
            c += 1                    # execute code in for-else
            break                     # exit break while True
    return c, i

The above is actually a full Python source reconstruction. In the implementation below, it is only necessary to emit some of the special assignments (marked above with a #-prefix above) into the blocks of the CFG. All of the control-flow inside the function will be represented by the directed edges of the CFG.

The first two assignments are for the pre-header:

__iterator_1__ = iter(range(10)) ## setup iterator

i = None ## assign target, i

The next three is for the header, the predicate determines the end of the loop.

__iter_last_1__ = i           ## backup value of i

i = next(__iterator_1__, '__sentinel__') ## get next i

if i != '__sentinel__':       ## regular iteration

And lastly, one assignment in the for-else clause

i == __iter_last_1__      ## restore value of i

We modify the pre-header, the header and the else blocks with appropriate Python statements in the following implementation. The Python code is injected by generating Python source using f-strings and then using the unparse() function of the ast module to then use the ‘codegen’ method of this transformer to emit the required ast.AST objects into the blocks of the CFG.

Lastly the important thing to observe is that we can not ignore the else clause, since this must contain the reset of the variable i, which will have been set to __sentinel__. This reset is required such that the target variable i will escape the scope of the for-loop.

handle_function_def(node: FunctionDef) → None: Handle a function definition.

handle_if(node: If) → None: Handle if statement.

handle_while(node: While) → None: Handle while statement.

render() → None

Render the CFG contained in this transformer as a SCFG.

Useful for debugging purposes, set a breakpoint and then render to view intermediary results.

seal_block(default_index: int) → None: Seal the current block by setting the jump_targets.

transform() → None: Transform Python function stored as self.code.

transform_to_ASTCFG() → ASTCFG: Generate ASTCFG from Python function.

transform_to_SCFG() → SCFG: Generate SCFG from Python function.

class numba_scfg.core.datastructures.ast_transforms.ASTCFG

A CFG consisting of WritableASTBlocks.

convert_blocks() → MutableMapping[str, Any]: Convert WritableASTBlocks to PythonASTBlocks.

prune_empty() → set[WritableASTBlock]: Prune empty blocks from the CFG.

prune_noops() → set[type[AST]]: Prune no-op instructions from the CFG.

prune_unreachable() → set[WritableASTBlock]: Prune unreachable blocks from the CFG.

to_SCFG() → SCFG: Convert ASTCFG to SCFG

to_dict() → dict[str, dict[str, object]]: Convert ASTCFG to simple dict based data structure.

class numba_scfg.core.datastructures.ast_transforms.LoopIndices(head: int, exit: int): Structure to hold the head and exit block indices of a loop.

numba_scfg.core.datastructures.ast_transforms.SCFG2AST(code: str | list[FunctionDef] | Callable[[...], Any], scfg: SCFG) → FunctionDef: Transform SCFG with PythonASTBlocks into an AST FunctionDef defined in code.

class numba_scfg.core.datastructures.ast_transforms.WritableASTBlock(name: str, instructions: list[AST] | None = None, jump_targets: list[str] | None = None)

A basic block containing Python AST that can be written to.

The recursive AST -> CFG algorithm requires a basic block that can be written to.

is_break() → bool: Check if the last instruction is a break statement.

is_continue() → bool: Check if the last instruction is a continue statement.

is_instruction(instruction: type[AST]) → bool: Check if the last instruction is of a certain type.

is_return() → bool: Check if the last instruction is a return statement.

seal_inside_loop(head_index: int, exit_index: int, default_index: int) → None: Seal the block by setting the jump targets based on the last instruction and taking into account that this block is nested in a loop.

seal_outside_loop(index: int) → None: Seal the block by setting the jump targets based on the last instruction.

set_jump_targets(*indices: int) → None: Set jump targets for the block.