Tree building

From IR-code a tree is generated which can be used to select instructions.

IR to DAG

The process of instruction selection is preceeded by the creation of a selection DAG (directed acyclic graph). The dagger take ir-code as input and produces such a dag for instruction selection.

A DAG represents the logic (computation) of a single basic block.

To do selection with tree matching, the DAG is then splitted into a series of tree patterns. This is often referred to as a forest of trees.

class ppci.codegen.irdag.FunctionInfo(frame)

Keeps track of global function data when generating code for part of a functions.

class ppci.codegen.irdag.Operation(op, ty)

A single operation with a type

class ppci.codegen.irdag.SelectionGraphBuilder(arch)

Create a selectiongraph from a function for instruction selection

block_to_sgraph(ir_block: ppci.ir.Block, function_info)

Create dag (directed acyclic graph) from a basic block.

The resulting dag can be used for instruction selection.

build(ir_function: ppci.ir.SubRoutine, function_info, debug_db)

Create a selection graph for the given function.

Selection graph is divided into groups for each basic block.

copy_phis_of_successors(ir_block)

When a terminator instruction is encountered, handle the copy of phi values into the expected virtual register

do_address_of(node)

Process ir.AddressOf instruction

do_alloc(node)

Process the alloc instruction

do_binop(node)

Visit a binary operator and create a DAG node

do_c_jump(node)

Process conditional jump into dag

do_cast(node)

Create a cast of type

do_const(node)

Process constant instruction

do_copy_blob(node)

Create a memcpy node.

do_function_call(node)

Transform a function call

do_inline_asm(node)

Create selection graph node for inline asm code.

This is a little weird, as we really do not need to select any instructions, but this special node will be filtered later on.

do_literal_data(node)

Literal data is stored after a label

do_load(node)

Create dag node for load operation

do_phi(node)

Refer to the correct copy of the phi node

do_procedure_call(node)

Transform a procedure call

do_return(node)

Move result into result register and jump to epilog

do_store(node)

Create a DAG node for the store operation

do_undefined(node)

Create node for undefined value.

do_unop(node)

Visit an unary operator and create a DAG node

get_address(ir_address)

Determine address for load or store.

new_node(name, ty, *args, value=None)

Create a new selection graph node, and add it to the graph

new_vreg(ty)

Generate a new temporary fitting for the given type

ppci.codegen.irdag.depth_first_order(function)

Return blocks in depth first search order

ppci.codegen.irdag.make_map(cls)

Add an attribute to the class that is a map of ir types to handler functions. For example if a function is called do_phi it will be registered into f_map under key ir.Phi.

ppci.codegen.irdag.prepare_function_info(arch, function_info, ir_function)

Fill function info with labels for all basic blocks

DAG splitting into trees.

The selection dag is splitted into trees by this module.

class ppci.codegen.dagsplit.DagSplitter(arch)

Class that splits a DAG into a forest of trees.

This series is sorted such that data dependencies are met. The trees can henceforth be used to match trees.

assign_vregs(sgraph, function_info)

Give vreg values to values that cross block boundaries

check_vreg(node, frame)

Determine whether node outputs need a virtual register

get_reg_class(data_flow)

Determine the register class suited for this data flow line

make_op(op, typ)

Construct a string opcode from an operation and a type

make_trees(nodes, tail_node)

Create a tree from a list of sorted nodes.

split_into_trees(sgraph, ir_function, function_info, debug_db)

Split a forest of trees into a sorted series of trees for each block.

ppci.codegen.dagsplit.topological_sort_modified(nodes, start)

Modified topological sort, start at the end and work back