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