6
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – Michael Homer
    Commented Apr 27 at 7:26
  • $\begingroup$ 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 $\endgroup$
    – NotAlfred
    Commented Apr 27 at 7:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael Homer
    Commented Apr 27 at 8:22

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – NotAlfred
    Commented Apr 27 at 8:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael Homer
    Commented Apr 27 at 8:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .