compiler-construction - 计算一组指令的依赖图

Question

在一系列可能的指令中:

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]

我想计算最终看起来像这样的依赖图:

这样做的有效算法是什么？

我目前的实现是这样的:

• 运行所有指令并生成last_seen 数组。

  答:1 ,乙:[2]，C: [3],D: [4]

• 对于每条指令，当且仅当是赋值:

  • 分成左和右部分

  • 生成新的node(left)。

  • 对于 right 中的每个标识符:制作新的 edge(left, last_seen[right])

Answer 1

在 Steven Muchnick 的高级编译器设计和实现一书中 Advanced Compiler Design and Implementation , 算法 9.6 提出了一种为基本 block 调度构建依赖 DAG 的方法。它还考虑了不同操作之间的延迟(以便稍后可以根据一些启发式选择指令)。

    #= 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

算法首先需要检查冲突(即DAG中已经存在的指令)如果没有冲突，我们将节点 j 添加到 DAG 的根。否则，如果存在冲突，我们为每个冲突 k 在 k 和 j 之间添加一条边。一些延迟函数给出了标签。

这个方法的时间复杂度是O(N²)