<p>I'm beginning to read Appel's book <a href="https://rads.stackoverflow.com/amzn/click/com/B00D2WQ9B2" rel="noreferrer" rel="nofollow noreferrer">Modern Compiler Implementation in C</a>. The book is about 25 years old, so maybe it's not so &quot;modern&quot; anymore, I don't know. I'm skimming the book and it seems like there are multiple different IRs (intermediate representations) used in the example compiler. At first, in chapter 7, he introduces something called &quot;IR trees&quot;. In the next few chapters he rearranges them in ways to to create &quot;basic blocks&quot;, and then do instruction selection and register allocation. But it's not until way later in chapter 19 that he gets into SSA (static single assignment) form.</p>
<p>I'm relatively new to the topic and I wasn't expecting this. I thought there would be a phase after the AST and type checking that created SSA IR, and that SSA would be used for instruction selection and register allocation. Is that also possible? Is that more common in modern compilers?</p>

<compilers><intermediate-representation><static-single-assignment>
Can you, should you, go straight from AST to SSA?
<p>You can go from AST to a &quot;sea of nodes&quot; as I've heard it called.</p>
<p>There each operation has a direct pointer to the inputs it uses. However it requires an explicit order between memory operations and other side effects. That order also requires you to account for branches. The &quot;memory to register&quot; pass is mostly the same principle of replacing loads of local variables with copies of the input of the previous store based on the explicit order between the load and store.</p>
<p>That way you have a partial order between the operations instead of the total order a basic block implies.</p>

CC BY-SA 4.0
2023-07-25T12:52:18.263Z
2023-07-25T12:52:18.263Z
ratchet freak
CC BY-SA 4.0
2023-07-25T21:40:39.517Z
Compilers that use SSA-based back ends seem to have trouble accommodating situations where a write and read might sometimes access the same object, but sometimes access different objects, when it would seem like a 1990s "sea of nodes" implementations would have no problem.  Is that a limitation of SSA, or just of some particular tools that use that form?
supercat
<p>You can, of course, but it's not ideal.</p>
<p>Your source AST is likely very high level. It may have a lot of redundancy due to syntax sugar in your source language. It needs all the expression nodes to be type-annotated. It needs all the identifiers to be resolved.</p>
<p>The most convenient approach is to do a sequence of very small AST rewrites, each doing one simple thing and nothing else. Before you get to a stage where SSA is useful, you can do a lot of other passes.</p>

CC BY-SA 4.0
2023-07-27T10:04:53.903Z
2023-07-27T10:04:53.903Z
SK-logic
<p>You can go straight from an AST to pretty much any IR.</p>
<p>If you were using a dominance frontier algorithm, such as Cytron's algorithm, then it would probably be easier if you flattened the AST first. However, this is not needed with more modern algorithms such as <a href="https://compilers.cs.uni-saarland.de/projects/ssaconstr/" rel="noreferrer">Braun <em>et al</em></a>.</p>
<p>Using SSA form for instruction selection is perfectly feasible, however you can't really &quot;do&quot; register allocation without knowing the lifetimes of temporaries, which means having something resembling a linear ordering for the final instructions.</p>
<p>A typical modern approach is:</p>
<ol>
<li>A pass for machine-specific lowering and combining (e.g. strength reduction, div/rem combining, etc).</li>
<li>Instruction selection in SSA form, output is a tiling of the SSA graph.</li>
<li>Instruction scheduling, which means turning the graph of tiles into a linear order. You would typically use A* search, taking things like instruction latencies and register pressure into account.</li>
<li>Register allocation.</li>
<li>Procedure prolog/epilog generation. (Why here? Because this requires knowing if any caller-save registers were used, or if any variables were spilled.)</li>
</ol>

CC BY-SA 4.0
2023-07-25T13:21:19.270Z
2023-07-25T13:21:19.270Z
Pseudonym
CC BY-SA 4.0
2023-07-25T15:33:12.523Z
Do you recommend any books that give a tour of this modern approach? Or maybe it's better described in various papers like the one you linked, or just buried in LLVM source code. I'm trying to build a compiler as I read stuff. I have the Dragon Book and Appel's at the moment.
Rob N
CC BY-SA 4.0
2023-07-26T04:44:42.317Z
@RobN I don't know of a single book, but this is a good start. https://pfalcon.github.io/ssabook/latest/book-full.pdf
Pseudonym
# Can you, should you, go straight from AST to SSA?
Posted by: username_0 on 2023-07-25
I'm beginning to read Appel's book [Modern Compiler Implementation in C](https://rads.stackoverflow.com/amzn/click/com/B00D2WQ9B2). The book is about 25 years old, so maybe it's not so "modern" anymore, I don't know. I'm skimming the book and it seems like there are multiple different IRs (intermediate representations) used in the example compiler. At first, in chapter 7, he introduces something called "IR trees". In the next few chapters he rearranges them in ways to to create "basic blocks", and then do instruction selection and register allocation. But it's not until way later in chapter 19 that he gets into SSA (static single assignment) form.

I'm relatively new to the topic and I wasn't expecting this. I thought there would be a phase after the AST and type checking that created SSA IR, and that SSA would be used for instruction selection and register allocation. Is that also possible? Is that more common in modern compilers?
**Tags:** compilers intermediate-representation static-single-assignment
---
## 3 answers
### Answer by username_4 on 2023-07-25. Score: 11 | Accepted answer
You can go straight from an AST to pretty much any IR.

If you were using a dominance frontier algorithm, such as Cytron's algorithm, then it would probably be easier if you flattened the AST first. However, this is not needed with more modern algorithms such as [Braun *et al*](https://compilers.cs.uni-saarland.de/projects/ssaconstr/).

Using SSA form for instruction selection is perfectly feasible, however you can't really "do" register allocation without knowing the lifetimes of temporaries, which means having something resembling a linear ordering for the final instructions.

A typical modern approach is:

1. A pass for machine-specific lowering and combining (e.g. strength reduction, div/rem combining, etc).
2. Instruction selection in SSA form, output is a tiling of the SSA graph.
3. Instruction scheduling, which means turning the graph of tiles into a linear order. You would typically use A\* search, taking things like instruction latencies and register pressure into account.
4. Register allocation.
5. Procedure prolog/epilog generation. (Why here? Because this requires knowing if any caller-save registers were used, or if any variables were spilled.)
> **Comments:**
> **username_0** (2023-07-25): Do you recommend any books that give a tour of this modern approach? Or maybe it's better described in various papers like the one you linked, or just buried in LLVM source code. I'm trying to build a compiler as I read stuff. I have the Dragon Book and Appel's at the moment.  
> **username_4** (2023-07-26): @RobN I don't know of a single book, but this is a good start. https://pfalcon.github.io/ssabook/latest/book-full.pdf  
---
### Answer by username_1 on 2023-07-25. Score: 3
You can go from AST to a "sea of nodes" as I've heard it called.

There each operation has a direct pointer to the inputs it uses. However it requires an explicit order between memory operations and other side effects. That order also requires you to account for branches. The "memory to register" pass is mostly the same principle of replacing loads of local variables with copies of the input of the previous store based on the explicit order between the load and store.

That way you have a partial order between the operations instead of the total order a basic block implies.
> **Comments:**
> **username_2** (2023-07-25): Compilers that use SSA-based back ends seem to have trouble accommodating situations where a write and read might sometimes access the same object, but sometimes access different objects, when it would seem like a 1990s "sea of nodes" implementations would have no problem.  Is that a limitation of SSA, or just of some particular tools that use that form?  
---
### Answer by username_3 on 2023-07-27. Score: 3
You can, of course, but it's not ideal.

Your source AST is likely very high level. It may have a lot of redundancy due to syntax sugar in your source language. It needs all the expression nodes to be type-annotated. It needs all the identifiers to be resolved.

The most convenient approach is to do a sequence of very small AST rewrites, each doing one simple thing and nothing else. Before you get to a stage where SSA is useful, you can do a lot of other passes.
---
