Using AST numbering to generate IR code in SSA form

To generate IR code in SSA form from the AST, we can use an approach called AST numbering. The basic idea is that for each basic block, we store the current value of local variables written in this basic block.

Note

The implementation is based on the paper Simple and Efficient Construction of Static Single Assignment Form, by Braun et al., International Conference on CompilerConstruction 2013 (CC 2013), Springer (see http://individual.utoronto.ca/dfr/ece467/braun13.pdf). In its presented form, it only works for IR code that has a structured controlled flow. The paper also describes the necessary extensions if you need to support arbitrary control flow – for example, a goto statement.

Although it is simple, we will still need several steps. We will introduce the required data structure first, and after that, we will learn how to read and write values local to a basic block. Then, we will handle values that are used...