##### number of registers

for the code below

a=b+c

c=a+b

d=b+c

e=d-b

a=e+b

___ number of registers to be allocated by the graph coloring algorithm?

for the code below

a=b+c

c=a+b

d=b+c

e=d-b

a=e+b

___ number of registers to be allocated by the graph coloring algorithm?

Minimum 2 register needed

I think, only 2 registers are needed at any time.

Form a graph such that the vertices are a,b,c,d,e. There will be an edge in between the vertices if there is a binary operation in between them. This simply means that if there is an operation between 2 variables they cannot be in the same register, hence they cannot have the same color. So putting an edge in between them reduces the problem to graph coloring problem.

so that's good for ohne statement, how to draw for all of them a=b+c, and say c=a+b?

For a=b+c draw three nodes and connect (b,c). Then for c=a+b connect (a,b). So it forms a bipartite graph. So two colors required for coloring. Hence we can say that 2 registers are good enough for these operations.

In the register way

take b and c in a register. Add b+c and put it in c. Now perform a+b but a is in c. So it is just c+b and then put the result in c or b.

## Pages