1  using ARMeilleure.IntermediateRepresentation;
 2  using System.Diagnostics;
 3  
 4  namespace ARMeilleure.Translation
 5  {
 6      static class Dominance
 7      {
 8          // Those methods are an implementation of the algorithms on "A Simple, Fast Dominance Algorithm".
 9          // https://www.cs.rice.edu/~keith/EMBED/dom.pdf
10          public static void FindDominators(ControlFlowGraph cfg)
11          {
12              BasicBlock Intersect(BasicBlock block1, BasicBlock block2)
13              {
14                  while (block1 != block2)
15                  {
16                      while (cfg.PostOrderMap[block1.Index] < cfg.PostOrderMap[block2.Index])
17                      {
18                          block1 = block1.ImmediateDominator;
19                      }
20  
21                      while (cfg.PostOrderMap[block2.Index] < cfg.PostOrderMap[block1.Index])
22                      {
23                          block2 = block2.ImmediateDominator;
24                      }
25                  }
26  
27                  return block1;
28              }
29  
30              cfg.Entry.ImmediateDominator = cfg.Entry;
31  
32              Debug.Assert(cfg.Entry == cfg.PostOrderBlocks[^1]);
33  
34              bool modified;
35  
36              do
37              {
38                  modified = false;
39  
40                  for (int blkIndex = cfg.PostOrderBlocks.Length - 2; blkIndex >= 0; blkIndex--)
41                  {
42                      BasicBlock block = cfg.PostOrderBlocks[blkIndex];
43  
44                      BasicBlock newIDom = null;
45  
46                      foreach (BasicBlock predecessor in block.Predecessors)
47                      {
48                          if (predecessor.ImmediateDominator != null)
49                          {
50                              if (newIDom != null)
51                              {
52                                  newIDom = Intersect(predecessor, newIDom);
53                              }
54                              else
55                              {
56                                  newIDom = predecessor;
57                              }
58                          }
59                      }
60  
61                      if (block.ImmediateDominator != newIDom)
62                      {
63                          block.ImmediateDominator = newIDom;
64  
65                          modified = true;
66                      }
67                  }
68              }
69              while (modified);
70          }
71  
72          public static void FindDominanceFrontiers(ControlFlowGraph cfg)
73          {
74              for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext)
75              {
76                  if (block.Predecessors.Count < 2)
77                  {
78                      continue;
79                  }
80  
81                  for (int pBlkIndex = 0; pBlkIndex < block.Predecessors.Count; pBlkIndex++)
82                  {
83                      BasicBlock current = block.Predecessors[pBlkIndex];
84  
85                      while (current != block.ImmediateDominator)
86                      {
87                          current.DominanceFrontiers.Add(block);
88  
89                          current = current.ImmediateDominator;
90                      }
91                  }
92              }
93          }
94      }
95  }