Given the following program:
gcd(a, b) [
1: LABEL start
2: IF a
3: LABEL swap
4: t := a
5: a := b
6: b := t
7: LABEL next
8: z := 0
9: b := b mod a
10: IF b = z THEN end ELSE start
11: LABEL end
12: RETURN a
]
a) Show succ, gen and kill for every instruction in the program.
b) Calculate in and out for every instruction in the program. Show the iteration as
in Fig. 8.4.
c) Draw the interference graph for a,b,t and z.
d) Make a three-colouring of the interference graph. Show the stack as in Fig. 8.6.
e) Attempt, instead, a two-colouring of the graph. Select variables for spill, do the
spill-transformation as shown in Sect. 8.5 and redo the complete register allocation process on the transformed program. If necessary, repeat the process until
register allocation is successful.