However, there are certain aspects of the tree language that do not correspond exactly with machine languages, and some aspects of the IR interface interfere with compile-time optimization analyses.

All this phase do is to rewrite IR code into an equivalent tree without any mismatches or side-effects. As a practice, the result code is usually organized into Blocks.

Note : if already eliminated the mismatches and side-effects in the former phases, the rewrite is not necessary(as my compiler do).

• To eliminate mismatches between IR and real machine language(since IR is an abstraction, to describe all possible machine languages mismatches often exists).
• To do traces(see sections below).
• many kinds of analysis and optimization algorithms run faster on (relatively few) basic blocks than on(relatively many) individual statements.

A basic block is a sequence of statements that is always entered at the beginning and exited at the end, that is:

• The first statement is a label definition.
• The last statement is a jump statement(conditional or unconditional).
• There are no other label definitions or jump statements.

Because basic blocks start with a label definition and ends with a jump, given a program made up of basic blocks, the following job can be easily done:

• analyzing the control flow of the program.
• blocks can be ordered in any order, and the result of executing the program will be the same.

A trace is a sequence of statements(blocks) that could be consecutively executed during the execution of the program. It can include conditional branches. A program has many different, overlapping traces.

In this step, we arrange that many of the unconditional jump statements are immediately followed by their target label. So that we can delete these jumps without any bad results.

We generate traces with following algorithm:

For some applications of traces, it is important that any frequently executed sequence of instructions(such as the body of a loop) should occupy its own trace. This helps not only to minimize the number of unconditional jumps, but also may help with other kinds of optimization such as register allocation and instruction scheduling.

To keep the simplicity of later phases in this compiler, we choose to flatten the ordered blocks into linear statements.

• myCanonical.h
• myCanonical.cpp