Compute the dependency graph for a set of instructions

user_1952857 0
Viewed 160

In a sequence of possible instructions:

1: A[i] = B[i]
2: B[i] = A[i] + D[i - 1]
3: C[i] = A[i] - D[i - 1]
4: D[i] = B[i] + C[i]

I want to compute the dependency graph that will end up looking like:

enter image description here

What would be an efficient algorithm for doing so?

My current implementation looks like this:

  • Run through all of the instructions and generate last_seen array.

    A: 1, B: [2], C: [3], D: [4]

  • For every instruction iff is assignment:

    • Split into left and right parts

    • Generate new node(left).

    • for every identifier in right: make new edge(left, last_seen[right])

compiler-construction
1 Answers

In the book advanced compiler design and implementation by Steven Muchnick Advanced Compiler Design and Implementation, algorithm 9.6 presents a method for constructing a dependence DAG for basic block scheduling. It also considers latencies between the different operations (So that instructions later can be selected according to some heuristic).

    #= Pseudocode of the build dag procedure (Some simplified ICAN notation)=# 
Build_dag(numberOfInstructions, Instructions)
    begin 
         DAG = {Nodes =  {}, Edges = {}, Label = {}, Roots{}}
         Conflicts = A set of integers representing conflicts
         j, k #= Integers for indexing=#
         for j in 1 to numberOfInstructions
              D.Nodes ∪= {j}
              Conflicts = {}
              for k = 1 to j - 1
                  if Conflict between Instructions[k] and Instructions[j]
                      Conflicts ∪= {k}
                  end
              end
              if isEmpty(Conflicts)
                  DAG.Roots ∪= {j}
              else 
                 for each k in Conflicts
                     DAG.Edges ∪= {k->j} #=Adds an edge between node k and node j=#
                     DAG.Label(k, j) = Latency(Instructions[k], 1, Instructions[j], IssueLatency + 1)
                 end
              end
          end
      return DAG
end

The algorithm first need to check conflicts (that is, instructions already present in the DAG) If there is no conflict, we add node j to the roots of the DAG. Otherwise, we add an edge between k and j for each conflict k if there is a conflict. Some Latency function gives the label.

The time complexity of this method is O(N²)

user_38531750
Related