dom.py

   1 "Adhoc/optimized routines for dominators."
   2
   3 def intersect(g, i, j):
   4     finger1 = i
   5     finger2 = j
   6     while finger1 != finger2:
   7         while -g[finger1]["postno"] > -g[finger2]["postno"]:
   8             finger1 = g[finger1]["idom"]
   9         while -g[finger2]["postno"] > -g[finger1]["postno"]:
  10             finger2 = g[finger2]["idom"]
  11     return finger1
  12
  13
  14 # Cooper 9.5.2
  15 def compute_idom(g):
  16     for n, info in g.nodes_props():
  17         info["idom"] = None
  18
  19     entry = g.entry()
  20     g[entry]["idom"] = entry
  21     changed = True
  22     while changed:
  23         changed = False
  24         it = iter(g.iter_rev_postorder())
  25         # Skip root
  26         next(it)
  27         for n in it:
  28             preds_rpo = sorted([(-g[p]["postno"], p) for p in g.pred(n)])
  29             new_idom = preds_rpo[0][1]
  30             for _, p in preds_rpo[1:]:
  31                 if g[p]["idom"] is not None:
  32                     new_idom = intersect(g, p, new_idom)
  33             if g[n]["idom"] != new_idom:
  34                 g[n]["idom"] = new_idom
  35                 changed = True
  36
  37     g[entry]["idom"] = None