<p>A newbie here! I'm implementing my current compiler in Haskell and at the moment I'm trying to do the translation of AST to Basic Blocks. Based on the book &quot;Advanced Compiler Design and Implementation&quot;, if I got it correctly, I
should be doing CFG next after constructing basic blocks.</p>
<p>I have the below data structure for my basic blocks. <code>Primitives</code> are supposed to be things that are just values and don't do anything (Binary operations are there because I do naive constant folding on them so they're as simple as possible) and <code>Instructions</code> are, well, instructions (I'm gonna expand them).</p>
<pre class="lang-hs prettyprint-override"><code>data Primitive
  = Const Value
  | Temp Label
  | BinOp Operator Primitive Primitive

data Instruction
  = None
  | Return Primitive
  | Move Label Primitive

newtype BasicBlock = BasicBlock [Instruction]
</code></pre>
<p>I'm trying to translate AST to basic blocks then to CFG at the moment, but hit this wall of subroutine calls. They might return values like expressions, but also they do something, like instructions. I want to know <strong>how subroutie calls are dealt with generally during translation of AST to basic blocks</strong>?</p>

<control-flow><haskell><control-flow-graph>
What to do with subroutine calls when translating Abstract Syntax Tree to Control Flow Graph?
CC BY-SA 4.0
2024-04-27T07:26:40.587Z
Function calls would not generally be highly relevant at this stage — it’s just a statement or expression like any other, to be dealt with come evaluation or code generation time, and calling conventions mostly aren’t relevant until then (but that could depend on how many later phases you’re going to have). It seems like all expressions must be in your “Primitive” class and non-expressions in “Instruction”, but you’ve figured that out already. Could you [edit] in some detail about why/what you’re having to deal with now?
Michael Homer
CC BY-SA 4.0
2024-04-27T07:51:11.813Z
Thank you for you feedback. I'm trying to just translate case by case and this question (more like a problem) came up. I updated the question. I hope it's more clear now. @MichaelHomer
NotAlfred
CC BY-SA 4.0
2024-04-27T08:22:14.507Z
I *think* I’ve taken your intended meaning in this answer, but tell me if I’ve missed it and I’ll try to clarify the question further.
Michael Homer
<p>The calling convention isn’t <em>generally</em> relevant at this stage, although if this is almost the final phase you might do something about it here. This also depends a little on what you mean by “calling convention”.</p>
<p>If we imagine there are local variables created on demand and accessed through <code>Temp x</code>, we can have the function-call Instruction put the return value into one of those. This might be defined like <code>Call Function [Primitive] Label</code>. If you had a statement like <code>z = f(x) + 1</code>, this might result in (presuming <code>x</code>, <code>y</code>, <code>z</code> are pre-existing Labels and Value aliases Int):</p>
<pre class="lang-haskell prettyprint-override"><code>BasicBlock [
    Call f [Temp x] y
    Move z (BinOp Plus (Temp y) (Const 1))
]
</code></pre>
<p>In this way, the function calls that “do something” are always Instructions, and accessing their return values is always through a side-effect-free Primitive. These return-value temporaries can be treated like other variables for the purposes of register allocation, cleanup, lifetimes, and so on.</p>
<hr />
<p>It’s possible to arrange things to pass arguments some other way (e.g. on a stack) and depending on the direction you want to go this may get closer to handling a calling convention in this phase, but it’s not an essential element right now, and probably I don’t recommend it your first time through. More, smaller phases are generally easier to wrap your head around, just more code to write.</p>
<p>It’s also defensible to have what amount to “Expression” and “Statement” categories at this stage still. In this case, you’d have function calls be expressions, and a wrapper Statement to discard the return value of a function call that wasn’t used. This can still be treated as a basic block element for as long as they’re all linear. You may find that easier for the moment, but at some stage things will get complicated enough that you need to break it down further anyway.</p>
<p>The approach you want to take here may depend on what you’re planning to do in the next phases, and what sort of machine your compilation target is. My suggestion is to use something like the above-the-line version if this is the path your book is following, but you might find exploring other options helps to solidify your thinking around it too.</p>

CC BY-SA 4.0
2024-04-27T08:21:33.137Z
2024-04-27T08:21:33.137Z
Michael Homer
CC BY-SA 4.0
2024-04-27T08:29:49.877Z
So in summary I just have to have another instruction for `Call` that takes the value from the function expression? or did I get it wrong?
NotAlfred
CC BY-SA 4.0
2024-04-27T08:39:48.347Z
Given the overall structure you’ve described (Primitives that don’t “do” anything, Instructions that do, functions that both do things and have return values), you’d have a Call *instruction* that as well as identifying the function and its arguments also takes a “destination” local variable/register for the return value to be stored in. There would be a Primitive for accessing that value afterwards. Later compilation steps might transform that to a different structure when you generate the actual code.
Michael Homer
# What to do with subroutine calls when translating Abstract Syntax Tree to Control Flow Graph?
Posted by: username_0 on 2024-04-27
A newbie here! I'm implementing my current compiler in Haskell and at the moment I'm trying to do the translation of AST to Basic Blocks. Based on the book "Advanced Compiler Design and Implementation", if I got it correctly, I
should be doing CFG next after constructing basic blocks.
I have the below data structure for my basic blocks. Primitives are supposed to be things that are just values and don't do anything (Binary operations are there because I do naive constant folding on them so they're as simple as possible) and Instructions are, well, instructions (I'm gonna expand them).
data Primitive
  = Const Value
  | Temp Label
  | BinOp Operator Primitive Primitive

data Instruction
  = None
  | Return Primitive
  | Move Label Primitive

newtype BasicBlock = BasicBlock [Instruction]

I'm trying to translate AST to basic blocks then to CFG at the moment, but hit this wall of subroutine calls. They might return values like expressions, but also they do something, like instructions. I want to know how subroutie calls are dealt with generally during translation of AST to basic blocks?
**Tags:** control-flow haskell control-flow-graph
> **Comments:**
> **username_1**: Function calls would not generally be highly relevant at this stage — it’s just a statement or expression like any other, to be dealt with come evaluation or code generation time, and calling conventions mostly aren’t relevant until then (but that could depend on how many later phases you’re going to have). It seems like all expressions must be in your “Primitive” class and non-expressions in “Instruction”, but you’ve figured that out already. Could you [edit] in some detail about why/what you’re having to deal with now?  
> **username_0**: Thank you for you feedback. I'm trying to just translate case by case and this question (more like a problem) came up. I updated the question. I hope it's more clear now. @MichaelHomer  
> **username_1**: I *think* I’ve taken your intended meaning in this answer, but tell me if I’ve missed it and I’ll try to clarify the question further.  
---
## 1 answers
### Answer by username_1 on 2024-04-27. Score: 2 | Accepted answer
The calling convention isn’t generally relevant at this stage, although if this is almost the final phase you might do something about it here. This also depends a little on what you mean by “calling convention”.
If we imagine there are local variables created on demand and accessed through Temp x, we can have the function-call Instruction put the return value into one of those. This might be defined like Call Function [Primitive] Label. If you had a statement like z = f(x) + 1, this might result in (presuming x, y, z are pre-existing Labels and Value aliases Int):
BasicBlock [
    Call f [Temp x] y
    Move z (BinOp Plus (Temp y) (Const 1))
]

In this way, the function calls that “do something” are always Instructions, and accessing their return values is always through a side-effect-free Primitive. These return-value temporaries can be treated like other variables for the purposes of register allocation, cleanup, lifetimes, and so on.

It’s possible to arrange things to pass arguments some other way (e.g. on a stack) and depending on the direction you want to go this may get closer to handling a calling convention in this phase, but it’s not an essential element right now, and probably I don’t recommend it your first time through. More, smaller phases are generally easier to wrap your head around, just more code to write.
It’s also defensible to have what amount to “Expression” and “Statement” categories at this stage still. In this case, you’d have function calls be expressions, and a wrapper Statement to discard the return value of a function call that wasn’t used. This can still be treated as a basic block element for as long as they’re all linear. You may find that easier for the moment, but at some stage things will get complicated enough that you need to break it down further anyway.
The approach you want to take here may depend on what you’re planning to do in the next phases, and what sort of machine your compilation target is. My suggestion is to use something like the above-the-line version if this is the path your book is following, but you might find exploring other options helps to solidify your thinking around it too.
> **Comments:**
> **username_0** (2024-04-27): So in summary I just have to have another instruction for `Call` that takes the value from the function expression? or did I get it wrong?  
> **username_1** (2024-04-27): Given the overall structure you’ve described (Primitives that don’t “do” anything, Instructions that do, functions that both do things and have return values), you’d have a Call *instruction* that as well as identifying the function and its arguments also takes a “destination” local variable/register for the return value to be stored in. There would be a Primitive for accessing that value afterwards. Later compilation steps might transform that to a different structure when you generate the actual code.  
---
