Instruction selection

The instruction selection phase takes care of scheduling and instruction selection. The output of this phase is a one frame per function with a flat list of abstract machine instructions.

To select instruction, a tree rewrite system is used. This is also called bottom up rewrite generator (BURG). See pyburg.

Instruction selector.

This part of the compiler takes in a DAG (directed acyclic graph) of instructions and selects the proper target instructions.

Selecting instructions from a DAG is a NP-complete problem. The simplest strategy is to split the DAG into a forest of trees and match these trees.

Another solution may be: PBQP (Partitioned Boolean Quadratic Programming)

The selection process creates operations in a selection DAG. The possible operations are listed in the below table:

operation	types	description
ADD(c0,c1)	I,U	Add its operands
SUB(c0,c1)	I,U	Substracts c1 from c0
MUL(c0,c1)	I,U	Multiplies c0 by c1
DIV(c0,c1)	I,U	Divides c0 by c1
OR(c0,c1)	I,U	Bitwise or
AND(c0,c1)	I,U	Bitwise and
XOR(c0,c1)	I,U	Bitwise exclusive or
LDR(c0)	I,U	Load from memory
STR(c0,c1)	I,U	Store value c1 at memory address c0
FPREL	U	Frame pointer relative location
CONST	I,U	Constant value
REG	I,U	Value in a specific register
JMP	I,U	Jump to a label
CJMP	I,U	Conditional jump to a label

…

Memory move operations:

• STRI64(REGI32[rax], CONSTI32[1])
• MOVB()

class ppci.codegen.instructionselector.InstructionContext(frame, arch)

Usable to patterns when emitting code

emit(instruction)

Abstract instruction emitter proxy

move(dst, src)

Generate move

new_label()

Generate a new unique label

new_reg(cls)

Generate a new temporary of a given class

class ppci.codegen.instructionselector.InstructionSelector1(arch, sgraph_builder, weights=(1, 1, 1))

Instruction selector which takes in a DAG and puts instructions into a frame.

This one does selection and scheduling combined.

gen_tree(context, tree)

Generate code from a tree

inline_asm(context, tree)

Run assembler on inline assembly code.

memcp()

Invoke memcpy arch function

munch_trees(context, trees)

Consume a dag and match it using the matcher to the frame. DAG matching is NP-complete.

The simplest strategy is to split the dag into a forest of trees. Then, the DAG is reduced to only trees, which can be matched.

A different approach is use 0-1 programming, like the NOLTIS algo.

TODO: implement different strategies.

select(ir_function: ppci.ir.SubRoutine, frame, reporter)

Select instructions of function into a frame

class ppci.codegen.instructionselector.TreeSelector(sys)

Tree matcher that can match a tree and generate instructions

apply_rules(context, tree, goal)

Apply all selected instructions to the tree

burm_label(tree)

Label all nodes in the tree bottom up

gen(context, tree)

Generate code for a given tree. The tree will be tiled with patterns and the corresponding code will be emitted

kids(tree, rule)

Determine the kid trees for a rule

nts(rule)

Get the open ends of this rules pattern