1  using Ryujinx.Graphics.Shader.IntermediateRepresentation;
  2  using System.Collections.Generic;
  3  
  4  namespace Ryujinx.Graphics.Shader.Translation
  5  {
  6      class ControlFlowGraph
  7      {
  8          public BasicBlock[] Blocks { get; }
  9          public BasicBlock[] PostOrderBlocks { get; }
 10          public int[] PostOrderMap { get; }
 11  
 12          public ControlFlowGraph(BasicBlock[] blocks)
 13          {
 14              Blocks = blocks;
 15  
 16              HashSet<BasicBlock> visited = new();
 17  
 18              Stack<BasicBlock> blockStack = new();
 19  
 20              List<BasicBlock> postOrderBlocks = new(blocks.Length);
 21  
 22              PostOrderMap = new int[blocks.Length];
 23  
 24              visited.Add(blocks[0]);
 25  
 26              blockStack.Push(blocks[0]);
 27  
 28              while (blockStack.TryPop(out BasicBlock block))
 29              {
 30                  if (block.Next != null && visited.Add(block.Next))
 31                  {
 32                      blockStack.Push(block);
 33                      blockStack.Push(block.Next);
 34                  }
 35                  else if (block.Branch != null && visited.Add(block.Branch))
 36                  {
 37                      blockStack.Push(block);
 38                      blockStack.Push(block.Branch);
 39                  }
 40                  else
 41                  {
 42                      PostOrderMap[block.Index] = postOrderBlocks.Count;
 43  
 44                      postOrderBlocks.Add(block);
 45                  }
 46              }
 47  
 48              PostOrderBlocks = postOrderBlocks.ToArray();
 49          }
 50  
 51          public static ControlFlowGraph Create(Operation[] operations)
 52          {
 53              Dictionary<Operand, BasicBlock> labels = new();
 54  
 55              List<BasicBlock> blocks = new();
 56  
 57              BasicBlock currentBlock = null;
 58  
 59              void NextBlock(BasicBlock nextBlock)
 60              {
 61                  if (currentBlock != null && !EndsWithUnconditionalInst(currentBlock.GetLastOp()))
 62                  {
 63                      currentBlock.Next = nextBlock;
 64                  }
 65  
 66                  currentBlock = nextBlock;
 67              }
 68  
 69              void NewNextBlock()
 70              {
 71                  BasicBlock block = new(blocks.Count);
 72  
 73                  blocks.Add(block);
 74  
 75                  NextBlock(block);
 76              }
 77  
 78              bool needsNewBlock = true;
 79  
 80              for (int index = 0; index < operations.Length; index++)
 81              {
 82                  Operation operation = operations[index];
 83  
 84                  if (operation.Inst == Instruction.MarkLabel)
 85                  {
 86                      Operand label = operation.Dest;
 87  
 88                      if (labels.TryGetValue(label, out BasicBlock nextBlock))
 89                      {
 90                          nextBlock.Index = blocks.Count;
 91  
 92                          blocks.Add(nextBlock);
 93  
 94                          NextBlock(nextBlock);
 95                      }
 96                      else
 97                      {
 98                          NewNextBlock();
 99  
100                          labels.Add(label, currentBlock);
101                      }
102                  }
103                  else
104                  {
105                      if (needsNewBlock)
106                      {
107                          NewNextBlock();
108                      }
109  
110                      currentBlock.Operations.AddLast(operation);
111                  }
112  
113                  needsNewBlock = operation.Inst == Instruction.Branch ||
114                                  operation.Inst == Instruction.BranchIfTrue ||
115                                  operation.Inst == Instruction.BranchIfFalse;
116  
117                  if (needsNewBlock)
118                  {
119                      Operand label = operation.Dest;
120  
121                      if (!labels.TryGetValue(label, out BasicBlock branchBlock))
122                      {
123                          branchBlock = new BasicBlock();
124  
125                          labels.Add(label, branchBlock);
126                      }
127  
128                      currentBlock.Branch = branchBlock;
129                  }
130              }
131  
132              // Remove unreachable blocks.
133              bool hasUnreachable;
134  
135              do
136              {
137                  hasUnreachable = false;
138  
139                  for (int blkIndex = 1; blkIndex < blocks.Count; blkIndex++)
140                  {
141                      BasicBlock block = blocks[blkIndex];
142  
143                      if (block.Predecessors.Count == 0)
144                      {
145                          block.Next = null;
146                          block.Branch = null;
147                          blocks.RemoveAt(blkIndex--);
148                          hasUnreachable = true;
149                      }
150                      else
151                      {
152                          block.Index = blkIndex;
153                      }
154                  }
155              } while (hasUnreachable);
156  
157              return new ControlFlowGraph(blocks.ToArray());
158          }
159  
160          private static bool EndsWithUnconditionalInst(INode node)
161          {
162              if (node is Operation operation)
163              {
164                  switch (operation.Inst)
165                  {
166                      case Instruction.Branch:
167                      case Instruction.Discard:
168                      case Instruction.Return:
169                          return true;
170                  }
171              }
172  
173              return false;
174          }
175      }
176  }