1  using ARMeilleure.IntermediateRepresentation;
  2  using System;
  3  using System.Collections.Generic;
  4  using System.Diagnostics;
  5  
  6  namespace ARMeilleure.Translation
  7  {
  8      class ControlFlowGraph
  9      {
 10          private BasicBlock[] _postOrderBlocks;
 11          private int[] _postOrderMap;
 12  
 13          public int LocalsCount { get; private set; }
 14          public BasicBlock Entry { get; private set; }
 15          public IntrusiveList<BasicBlock> Blocks { get; }
 16          public BasicBlock[] PostOrderBlocks => _postOrderBlocks;
 17          public int[] PostOrderMap => _postOrderMap;
 18  
 19          public ControlFlowGraph(BasicBlock entry, IntrusiveList<BasicBlock> blocks, int localsCount)
 20          {
 21              Entry = entry;
 22              Blocks = blocks;
 23              LocalsCount = localsCount;
 24  
 25              Update();
 26          }
 27  
 28          public Operand AllocateLocal(OperandType type)
 29          {
 30              Operand result = Operand.Factory.Local(type);
 31  
 32              result.NumberLocal(++LocalsCount);
 33  
 34              return result;
 35          }
 36  
 37          public void UpdateEntry(BasicBlock newEntry)
 38          {
 39              newEntry.AddSuccessor(Entry);
 40  
 41              Entry = newEntry;
 42              Blocks.AddFirst(newEntry);
 43              Update();
 44          }
 45  
 46          public void Update()
 47          {
 48              RemoveUnreachableBlocks(Blocks);
 49  
 50              var visited = new HashSet<BasicBlock>();
 51              var blockStack = new Stack<BasicBlock>();
 52  
 53              Array.Resize(ref _postOrderBlocks, Blocks.Count);
 54              Array.Resize(ref _postOrderMap, Blocks.Count);
 55  
 56              visited.Add(Entry);
 57              blockStack.Push(Entry);
 58  
 59              int index = 0;
 60  
 61              while (blockStack.TryPop(out BasicBlock block))
 62              {
 63                  bool visitedNew = false;
 64  
 65                  for (int i = 0; i < block.SuccessorsCount; i++)
 66                  {
 67                      BasicBlock succ = block.GetSuccessor(i);
 68  
 69                      if (visited.Add(succ))
 70                      {
 71                          blockStack.Push(block);
 72                          blockStack.Push(succ);
 73  
 74                          visitedNew = true;
 75  
 76                          break;
 77                      }
 78                  }
 79  
 80                  if (!visitedNew)
 81                  {
 82                      PostOrderMap[block.Index] = index;
 83  
 84                      PostOrderBlocks[index++] = block;
 85                  }
 86              }
 87          }
 88  
 89          private void RemoveUnreachableBlocks(IntrusiveList<BasicBlock> blocks)
 90          {
 91              var visited = new HashSet<BasicBlock>();
 92              var workQueue = new Queue<BasicBlock>();
 93  
 94              visited.Add(Entry);
 95              workQueue.Enqueue(Entry);
 96  
 97              while (workQueue.TryDequeue(out BasicBlock block))
 98              {
 99                  Debug.Assert(block.Index != -1, "Invalid block index.");
100  
101                  for (int i = 0; i < block.SuccessorsCount; i++)
102                  {
103                      BasicBlock succ = block.GetSuccessor(i);
104  
105                      if (visited.Add(succ))
106                      {
107                          workQueue.Enqueue(succ);
108                      }
109                  }
110              }
111  
112              if (visited.Count < blocks.Count)
113              {
114                  // Remove unreachable blocks and renumber.
115                  int index = 0;
116  
117                  for (BasicBlock block = blocks.First; block != null;)
118                  {
119                      BasicBlock nextBlock = block.ListNext;
120  
121                      if (!visited.Contains(block))
122                      {
123                          while (block.SuccessorsCount > 0)
124                          {
125                              block.RemoveSuccessor(index: block.SuccessorsCount - 1);
126                          }
127  
128                          blocks.Remove(block);
129                      }
130                      else
131                      {
132                          block.Index = index++;
133                      }
134  
135                      block = nextBlock;
136                  }
137              }
138          }
139  
140          public BasicBlock SplitEdge(BasicBlock predecessor, BasicBlock successor)
141          {
142              BasicBlock splitBlock = new(Blocks.Count);
143  
144              for (int i = 0; i < predecessor.SuccessorsCount; i++)
145              {
146                  if (predecessor.GetSuccessor(i) == successor)
147                  {
148                      predecessor.SetSuccessor(i, splitBlock);
149                  }
150              }
151  
152              if (splitBlock.Predecessors.Count == 0)
153              {
154                  throw new ArgumentException("Predecessor and successor are not connected.");
155              }
156  
157              splitBlock.AddSuccessor(successor);
158  
159              Blocks.AddBefore(successor, splitBlock);
160  
161              return splitBlock;
162          }
163      }
164  }