Finding the appropriate machine instructions to implement a given IR tree is the job of the instruction selection phase of a compiler.

Let us take a figure as an example:

All this phase do is to find appropriate machine instructions for each possible Tree Pattern(a fragment of an IR tree that corresponding to a machine instruction) in the IR tree.

As described in the tiger book, there are two kinds of algorithms:

1. Optimal : algorithms where no adjacent tiles can be combined into a single tile of lower cost.
2. Optimum : algorithms whose tiles sum to the lowest possible value. Dynamic programming can be used in finding this kind of algorithms.

That is, Optimal algorithms are ideal ones. Every optimum tiling is also optimal, but no vice versa.

Each RISC(Reduced Instruction Set Computer) instruction accomplishes just a small number of operations.

CISC(Complex Instruction Set Computer) have instructions that accomplish several operations each.

The algorithm for optimal tiling is called Maximal Munch. It is quite simple. Starting at the root of the tree, find the largest tile that fits. Cover the root node----and perhaps several other nodes near the root----with this tile, leaving several subtrees. Now repeat the same algorithm for each subtree.

As each tile is placed, the instruction corresponding to that tile is generated. The Maximal Munch algorithm generates the instructions in reverse order----after all, the instruction at the root is the first to be generated. but it can only execute after the other instructions have produced operand values in registers.

We use the Maximal Munch algorithm in this compiler. However, the algorithm used in my compiler is not really like the one above. Because i have already stored almost every operand values in registers in the early phases, the whole program is actually not one bit IR tree but many small ones.

This decision simplify Basic Blocks and Traces and Instruction Selection phases, but make some trees impossible to be tiled into a single Tree Pattern and generating only one instruction(more likely happens in CISCs).

Support for Maximal Munch:

• myMunch.h
• myMunch.cpp

Support for Abstract Assembly Instructions:

• AAI/myAaiBase.h
• AAI/myAaiBase.cpp
• AAI/myComputable.h
• AAI/myComputable.cpp
• AAI/myControlable.h
• AAI/myControlable.cpp
• AAI/myMovable.h
• AAI/myMovable.cpp