<p>I have an abstract-syntax tree (AST) for a language, and I'd like to use some sort of <a href="https://en.wikipedia.org/wiki/Three-address_code" rel="nofollow noreferrer">three-address code</a> (TAC) to represent the program in a linear way, before converting it to assembly.</p>
<p>How do I do this in a way that allows future optimizations? What operations does the TAC need to support for a language like C?</p>

<implementation><compilers>
How can an abstract-syntax tree be converted into linear three-address code?
CC BY-SA 4.0
2023-06-13T15:51:29.547Z
I've written a similar answer as below in https://stackoverflow.com/questions/75065177/how-exactly-to-construct-basic-blocks-for-a-compiler-using-javascript-as-an-e/75067604#75067604, but I comment to note that I think you might benefit from checking out GCC's GIMPLE output, as mentioned in that answer. This transformation can also be done quite idiomatically in certain languages, for example it's easy to rework a functional account of A-Normal Form conversion to produce labels, gotos, etc. in a list of statements before doing the "leaders" algorithm to construct a control flow graph.
Colin James
<p>Since you said &quot;language like C&quot;, let's assume your AST have both statements and expressions.</p>
<p>Expression flattening is quite simple. You can start with an unlimited number of virtual registers for your three address code, though I'd recommend to go for a more modern IR, at least something SSA-based. Initial translation steps will be the same.</p>
<p>Also assuming you already did typing pass on your higher level AST and you know the type of each expression and variable.</p>
<p>For each compound expression node (i.e., not a constant), in a depth-first order, assign a virtual register and add this assignment to the current flat list. E.g., an expression tree <code>a*b+c*d</code> can be translated as</p>
<pre><code>R101=load a
R102=load b
R103=load c
R104=load d
R105=R101*R102
R106=R103*R104
R107=R105+R106
</code></pre>
<p>And then replace the original expression location in whatever statement had it with a reference to <code>R107</code>.</p>
<p>Translating statements is simple too. Each statement translated directly to a sequence of instructions and potentially labels. E.g., an <code>if (a) then B else C</code> statement will become</p>
<pre><code>R108 = ... a ... ;; whatever the translated a expression is
brfalse R108 L100
B ;; compile B statement here
br L101
L100:
C ;; compile C statement here
L101:
</code></pre>
<p>Same for all other kinds of statements. Do not worry about excessive labels and branches, you'll get rid of them in a next pass when you detect and extract basic blocks. Once you have basic blocks you can do further simplification, like fusing basic blocks.</p>
<p>Once done, you can do your dominance analysis and do an SSA transform, which will get rid of the excessive <code>load</code> instructions as well, replacing single use variables with single assignment registers, and multiple assignment variables merged into <code>phi</code> nodes.</p>
<p>You can go further and add an Array SSA translation. Once in a nice and clean SSA, you can do a load of optimisation and analysis passes.</p>

CC BY-SA 4.0
2023-06-13T10:07:35.540Z
2023-06-13T10:07:35.540Z
SK-logic
CC BY-SA 4.0
2023-06-13T14:25:53.213Z
Thank you for the answer, there's some great information in here. What are `phi` nodes? I suspect another question might be needed to discuss constructing SSA from TAC
springogeek
CC BY-SA 4.0
2023-06-13T16:37:42.370Z
Basically, phi is a special "instruction" saying that the target register is assigned one value if control flow came from one source to here, and another from some other location. Like COMEFROM, but seriously. I recommend reading the unfinished SSA book: https://pfalcon.github.io/ssabook/latest/book.pdf - tons of useful information there.
SK-logic
CC BY-SA 4.0
2023-06-13T16:39:33.623Z
Another important and often overlooked property of SSA is that it's an equivalent of a subset of CPS, and a lot of things we can do with CPS applies to an SSA as well: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=7cb90be27017772fa441981d3d362741056efd57
SK-logic
CC BY-SA 4.0
2023-06-13T16:49:24.707Z
Also, you can take a look at an implementation of a complete SSA-based pipeline for a toy language here: https://combinatorylogic.github.io/mbase-docs/lang0.html - it covers all of the basic concepts.
SK-logic
# How can an abstract-syntax tree be converted into linear three-address code?
Posted by: username_0 on 2023-06-13
I have an abstract-syntax tree (AST) for a language, and I'd like to use some sort of [three-address code](https://en.wikipedia.org/wiki/Three-address_code) (TAC) to represent the program in a linear way, before converting it to assembly.

How do I do this in a way that allows future optimizations? What operations does the TAC need to support for a language like C?
**Tags:** implementation compilers
> **Comments:**
> **username_1**: I've written a similar answer as below in https://stackoverflow.com/questions/75065177/how-exactly-to-construct-basic-blocks-for-a-compiler-using-javascript-as-an-e/75067604#75067604, but I comment to note that I think you might benefit from checking out GCC's GIMPLE output, as mentioned in that answer. This transformation can also be done quite idiomatically in certain languages, for example it's easy to rework a functional account of A-Normal Form conversion to produce labels, gotos, etc. in a list of statements before doing the "leaders" algorithm to construct a control flow graph.  
---
## 1 answers
### Answer by username_2 on 2023-06-13. Score: 6
Since you said "language like C", let's assume your AST have both statements and expressions.
Expression flattening is quite simple. You can start with an unlimited number of virtual registers for your three address code, though I'd recommend to go for a more modern IR, at least something SSA-based. Initial translation steps will be the same.
Also assuming you already did typing pass on your higher level AST and you know the type of each expression and variable.
For each compound expression node (i.e., not a constant), in a depth-first order, assign a virtual register and add this assignment to the current flat list. E.g., an expression tree a*b+c*d can be translated as
R101=load a
R102=load b
R103=load c
R104=load d
R105=R101*R102
R106=R103*R104
R107=R105+R106

And then replace the original expression location in whatever statement had it with a reference to R107.
Translating statements is simple too. Each statement translated directly to a sequence of instructions and potentially labels. E.g., an if (a) then B else C statement will become
R108 = ... a ... ;; whatever the translated a expression is
brfalse R108 L100
B ;; compile B statement here
br L101
L100:
C ;; compile C statement here
L101:

Same for all other kinds of statements. Do not worry about excessive labels and branches, you'll get rid of them in a next pass when you detect and extract basic blocks. Once you have basic blocks you can do further simplification, like fusing basic blocks.
Once done, you can do your dominance analysis and do an SSA transform, which will get rid of the excessive load instructions as well, replacing single use variables with single assignment registers, and multiple assignment variables merged into phi nodes.
You can go further and add an Array SSA translation. Once in a nice and clean SSA, you can do a load of optimisation and analysis passes.
> **Comments:**
> **username_0** (2023-06-13): Thank you for the answer, there's some great information in here. What are `phi` nodes? I suspect another question might be needed to discuss constructing SSA from TAC  
> **username_2** (2023-06-13): Basically, phi is a special "instruction" saying that the target register is assigned one value if control flow came from one source to here, and another from some other location. Like COMEFROM, but seriously. I recommend reading the unfinished SSA book: https://pfalcon.github.io/ssabook/latest/book.pdf - tons of useful information there.  
> **username_2** (2023-06-13): Another important and often overlooked property of SSA is that it's an equivalent of a subset of CPS, and a lot of things we can do with CPS applies to an SSA as well: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=7cb90be27017772fa441981d3d362741056efd57  
> **username_2** (2023-06-13): Also, you can take a look at an implementation of a complete SSA-based pipeline for a toy language here: https://combinatorylogic.github.io/mbase-docs/lang0.html - it covers all of the basic concepts.  
---
