optimizationcompiler-constructioncontrol-flow-graphintermediate-codetac

How to handle function calls in a control flow graph with basic blocks


I have been building the middle end of a compiler and I was wondering how I should handle function calls inside the flow graphs.

So as an example lets just look at the following three address code

LABEL label0
a = 1
b = 2
c = a + b
IF c == g GOTO label1 ELSE GOTO label2
LABEL label1
d = c + 0
CALL func0 (d -> y)
GOTO label0
LABEL label2
e = 8
f = 600
g = e + f
CALL func0 (a -> y)
CALL func1
END
FUNC LABEL func0
PRINT y
RETURN
FUNC LABEL func1
result = "PROGRAM IS COMPLETE"
PRINT result
RETURN

The first step is to break this into basic blocks like the following

block1:
LABEL label0
a = 1
b = 2
c = a + b
IF c == g GOTO label1 ELSE GOTO label2

block2:
LABEL label1
d = c + 0
CALL func0 (d -> y)

block3:
GOTO label0

block4:
LABEL label2
e = 8
f = 600
g = e + f
CALL func0 (a -> y)

block5:
CALL func1

block6:
END

block7:
FUNC LABEL func0
PRINT y
RETURN

block8:
FUNC LABEL func1
result = "PROGRAM IS COMPLETE"
PRINT result
RETURN

Here I assumed function calls should be treated as Jumps and therefore they should force a new block to start just like the GOTO or the if-jump statement does.

Afterwards I nest the basic block structure inside of my flow graph structure. And in that structure, I define all the connections. Like block1 should be connected to block2 and block4. Also block3 should connect to block1. I also connect block5 to block8 because of the Call. I connect block4 to block7 and block2 to block7 because of their respective calls. For the return jumps I connect block7 to block5 and block3 and I connect block8 to block6.

I guess my question is am I on the right track by integrating function calls and returns into the flow graph and treating them as jumps or am I supposed to ignore CALL statements when breaking up the instructions into basic blocks and just process the function body blocks as their own sub flow graphs.


Solution

  • For languages without exceptions calls are usually not treated as jumps when you construct a control flow graph. From the callees perspective a function call is an atomic single-entry, single-exit regions as any other instruction. The call itself can not force a change in control flow.