image.png
根据上图中的结论，PDT 可以由 Reversed CFG 求 Dominance Tree 而得。

给出一个 CFG:

  1. from graphviz import Digraph
  2. from IPython.display import Image
  4. code = """
  5. 0 Start
  6. 1 A
  7. 2 B
  8. 3 C
  9. 4 D
  10. 5 E
  11. 6 F
  12. 7 End
  13. """
  14. buggy_nos = [14]
  15. buggy_nos = [ str(a) for a in buggy_nos ]
  17. gz=Digraph("CFG",'comment',None,None,'png',None,"UTF-8",
  18.            {'rankdir':'TB'},
  19.            {'color':'black','fontcolor':'black','fontname':'FangSong','fontsize':'12','style':'rounded','shape':'box'},
  20.            {'color':'#999999','fontcolor':'#888888','fontsize':'10','fontname':'FangSong'},None,False)
  22. for line in code.strip().split("\n"):
  23.     # print("ll:", line)
  24.     l_num, l_code = line.split(" ", 1)
  25.     if l_code.strip() == '{' or l_code.strip() == '}':
  26.         continue
  27.     if l_code == 'End' or l_code == 'Start':
  28.         l_text = l_code
  29.     else:
  30.         l_text = l_code
  31.     if l_num in buggy_nos:
  32.         gz.node( l_num, l_text, {'color':'red','fontcolor':'red'})
  33.     else:
  34.         gz.node( l_num, l_text )
  37. CFG_edges = [[0, 1], [1, 2], [1, 3], [2, 4], [3, 4], [4, 5], [5, 6], [6, 7], [6, 5]]
  38. for a, b in CFG_edges:
  39.     gz.edge( str(a), str(b))
  40. # print(gz.source)
  41. gz.view()
  42. Image("CFG.gv.png")

输出：
image.png

生成 PDT：

  1. gz=Digraph("PDT",'comment',None,None,'png',None,"UTF-8",
  2.            {'rankdir':'TB'},
  3.            {'color':'black','fontcolor':'black','fontname':'FangSong','fontsize':'12','style':'rounded','shape':'box'},
  4.            {'color':'#999999','fontcolor':'#888888','fontsize':'10','fontname':'FangSong'},None,False)
  6. for line in code.strip().split("\n"):
  7.     # print("ll:", line)
  8.     l_num, l_code = line.split(" ", 1)
  9.     if l_code.strip() == '{' or l_code.strip() == '}':
  10.         continue
  11.     if l_code == 'End' or l_code == 'Start':
  12.         l_text = l_code
  13.     else:
  14.         l_text = l_code
  15.     if l_num in buggy_nos:
  16.         gz.node( l_num, l_text, {'color':'red','fontcolor':'red'})
  17.     else:
  18.         gz.node( l_num, l_text )
  21. reversed_cfg_edges = []
  22. for row in CFG_edges:
  23.     reversed_cfg_edges.append( [row[1], row[0]] )
  25. G = nx.DiGraph()
  26. G.add_edges_from(reversed_cfg_edges)
  27. start = reversed_cfg_edges[0][0]
  28. for edge in reversed_cfg_edges:
  29.     for node in edge:
  30.         if node >= start:
  31.             start = node
  32. edgelist = sorted(nx.immediate_dominators(G, start).items())
  33. edgelist = [list(x) for x in edgelist]
  34. for a, b in edgelist:
  35.     gz.edge( str(b), str(a))
  36. # print(gz.source)
  37. gz.view()
  38. Image("PDT.gv.png")

得到的 PDT 为：

image.png