Question: Compilers often reorder source code for efficiency reasons. For example, x = 3 y = 4 z = x + y could be reordered as

 Compilers often reorder source code for efficiency reasons. For example, x

Compilers often reorder source code for efficiency reasons. For example, x = 3 y = 4 z = x + y could be reordered as y = 4 x = 3 z = x + y but could not be reordered as x = 3 z = x + y y = 4 because z = x + y has a dependency on y = 4, i.e., y = 4 must be executed before z = x + y can be executed. One way to find a reordering of code is to build a dependency graph of the source code, and then do a topological sort on the graph. For example, the dependency graph of the above codelooks like Given the code below, build a dependency graph with the vertices labeled with the line of code, and run a topological sort. Assume that the for loop of lines 5-7 of the DFS procedure considers the verticesin alphabetical order, and assume that each adjacency list is ordered alphabetically. Your answer willinclude both the graph labeled with discovery and finish times, as well as a new ordering for the code. a = 3 b = a c = 4 d = a e = d - a f = b + c + e

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!