1  using Ryujinx.Graphics.Shader.IntermediateRepresentation;
  2  using System;
  3  using System.Collections.Generic;
  4  using static Ryujinx.Graphics.Shader.StructuredIr.AstHelper;
  5  
  6  namespace Ryujinx.Graphics.Shader.StructuredIr
  7  {
  8      static class GotoElimination
  9      {
 10          // This is a modified version of the algorithm presented on the paper
 11          // "Taming Control Flow: A Structured Approach to Eliminating Goto Statements".
 12          public static void Eliminate(GotoStatement[] gotos)
 13          {
 14              for (int index = gotos.Length - 1; index >= 0; index--)
 15              {
 16                  GotoStatement stmt = gotos[index];
 17  
 18                  AstBlock gBlock = ParentBlock(stmt.Goto);
 19                  AstBlock lBlock = ParentBlock(stmt.Label);
 20  
 21                  int gLevel = Level(gBlock);
 22                  int lLevel = Level(lBlock);
 23  
 24                  if (IndirectlyRelated(gBlock, lBlock, gLevel, lLevel))
 25                  {
 26                      AstBlock drBlock = gBlock;
 27  
 28                      int drLevel = gLevel;
 29  
 30                      do
 31                      {
 32                          drBlock = drBlock.Parent;
 33  
 34                          drLevel--;
 35                      }
 36                      while (!DirectlyRelated(drBlock, lBlock, drLevel, lLevel));
 37  
 38                      MoveOutward(stmt, gLevel, drLevel);
 39  
 40                      gBlock = drBlock;
 41                      gLevel = drLevel;
 42  
 43                      if (Previous(stmt.Goto) is AstBlock elseBlock && elseBlock.Type == AstBlockType.Else)
 44                      {
 45                          // It's possible that the label was enclosed inside an else block,
 46                          // in this case we need to update the block and level.
 47                          // We also need to set the IsLoop for the case when the label is
 48                          // now before the goto, due to the newly introduced else block.
 49                          lBlock = ParentBlock(stmt.Label);
 50  
 51                          lLevel = Level(lBlock);
 52  
 53                          if (!IndirectlyRelated(elseBlock, lBlock, gLevel + 1, lLevel))
 54                          {
 55                              stmt.IsLoop = true;
 56                          }
 57                      }
 58                  }
 59  
 60                  if (DirectlyRelated(gBlock, lBlock, gLevel, lLevel))
 61                  {
 62                      if (gLevel > lLevel)
 63                      {
 64                          MoveOutward(stmt, gLevel, lLevel);
 65                      }
 66                      else
 67                      {
 68                          if (stmt.IsLoop)
 69                          {
 70                              Lift(stmt);
 71                          }
 72  
 73                          MoveInward(stmt);
 74                      }
 75                  }
 76  
 77                  gBlock = ParentBlock(stmt.Goto);
 78  
 79                  if (stmt.IsLoop)
 80                  {
 81                      EncloseDoWhile(stmt, gBlock, stmt.Label);
 82                  }
 83                  else
 84                  {
 85                      Enclose(gBlock, AstBlockType.If, stmt.Condition, Next(stmt.Goto), stmt.Label);
 86                  }
 87  
 88                  gBlock.Remove(stmt.Goto);
 89              }
 90          }
 91  
 92          private static bool IndirectlyRelated(AstBlock lBlock, AstBlock rBlock, int lLevel, int rlevel)
 93          {
 94              return !(lBlock == rBlock || DirectlyRelated(lBlock, rBlock, lLevel, rlevel));
 95          }
 96  
 97          private static bool DirectlyRelated(AstBlock lBlock, AstBlock rBlock, int lLevel, int rLevel)
 98          {
 99              // If the levels are equal, they can be either siblings or indirectly related.
100              if (lLevel == rLevel)
101              {
102                  return false;
103              }
104  
105              IAstNode block;
106              IAstNode other;
107  
108              int blockLvl, otherLvl;
109  
110              if (lLevel > rLevel)
111              {
112                  block = lBlock;
113                  blockLvl = lLevel;
114                  other = rBlock;
115                  otherLvl = rLevel;
116              }
117              else /* if (rLevel > lLevel) */
118              {
119                  block = rBlock;
120                  blockLvl = rLevel;
121                  other = lBlock;
122                  otherLvl = lLevel;
123              }
124  
125              while (blockLvl >= otherLvl)
126              {
127                  if (block == other)
128                  {
129                      return true;
130                  }
131  
132                  block = block.Parent;
133  
134                  blockLvl--;
135              }
136  
137              return false;
138          }
139  
140          private static void Lift(GotoStatement stmt)
141          {
142              AstBlock block = ParentBlock(stmt.Goto);
143  
144              AstBlock[] path = BackwardsPath(block, ParentBlock(stmt.Label));
145  
146              AstBlock loopFirstStmt = path[^1];
147  
148              if (loopFirstStmt.Type == AstBlockType.Else)
149              {
150                  loopFirstStmt = Previous(loopFirstStmt) as AstBlock;
151  
152                  if (loopFirstStmt == null || loopFirstStmt.Type != AstBlockType.If)
153                  {
154                      throw new InvalidOperationException("Found an else without a matching if.");
155                  }
156              }
157  
158              AstBlock newBlock = EncloseDoWhile(stmt, block, loopFirstStmt);
159  
160              block.Remove(stmt.Goto);
161  
162              newBlock.AddFirst(stmt.Goto);
163  
164              stmt.IsLoop = false;
165          }
166  
167          private static void MoveOutward(GotoStatement stmt, int gLevel, int lLevel)
168          {
169              AstBlock origin = ParentBlock(stmt.Goto);
170  
171              AstBlock block = origin;
172  
173              // Check if a loop is enclosing the goto, and the block that is
174              // directly related to the label is above the loop block.
175              // In that case, we need to introduce a break to get out of the loop.
176              AstBlock loopBlock = origin;
177  
178              int loopLevel = gLevel;
179  
180              while (loopLevel > lLevel)
181              {
182                  AstBlock child = loopBlock;
183  
184                  loopBlock = loopBlock.Parent;
185  
186                  loopLevel--;
187  
188                  if (child.Type == AstBlockType.DoWhile)
189                  {
190                      EncloseSingleInst(stmt, Instruction.LoopBreak);
191  
192                      block.Remove(stmt.Goto);
193  
194                      loopBlock.AddAfter(child, stmt.Goto);
195  
196                      block = loopBlock;
197                      gLevel = loopLevel;
198                  }
199              }
200  
201              // Insert ifs to skip the parts that shouldn't be executed due to the goto.
202              bool tryInsertElse = stmt.IsUnconditional && origin.Type == AstBlockType.If;
203  
204              while (gLevel > lLevel)
205              {
206                  Enclose(block, AstBlockType.If, stmt.Condition, Next(stmt.Goto));
207  
208                  block.Remove(stmt.Goto);
209  
210                  AstBlock child = block;
211  
212                  // We can't move the goto in the middle of a if and a else block, in
213                  // this case we need to move it after the else.
214                  // IsLoop may need to be updated if the label is inside the else, as
215                  // introducing a loop is the only way to ensure the else will be executed.
216                  if (Next(child) is AstBlock elseBlock && elseBlock.Type == AstBlockType.Else)
217                  {
218                      child = elseBlock;
219                  }
220  
221                  block = block.Parent;
222  
223                  block.AddAfter(child, stmt.Goto);
224  
225                  gLevel--;
226  
227                  if (tryInsertElse && child == origin)
228                  {
229                      AstBlock lBlock = ParentBlock(stmt.Label);
230  
231                      IAstNode last = block == lBlock && !stmt.IsLoop ? stmt.Label : null;
232  
233                      AstBlock newBlock = Enclose(block, AstBlockType.Else, null, Next(stmt.Goto), last);
234  
235                      if (newBlock != null)
236                      {
237                          block.Remove(stmt.Goto);
238  
239                          block.AddAfter(newBlock, stmt.Goto);
240                      }
241                  }
242              }
243          }
244  
245          private static void MoveInward(GotoStatement stmt)
246          {
247              AstBlock block = ParentBlock(stmt.Goto);
248  
249              AstBlock[] path = BackwardsPath(block, ParentBlock(stmt.Label));
250  
251              for (int index = path.Length - 1; index >= 0; index--)
252              {
253                  AstBlock child = path[index];
254                  AstBlock last = child;
255  
256                  if (child.Type == AstBlockType.If)
257                  {
258                      // Modify the if condition to allow it to be entered by the goto.
259                      if (!ContainsCondComb(child.Condition, Instruction.LogicalOr, stmt.Condition))
260                      {
261                          child.OrCondition(stmt.Condition);
262                      }
263                  }
264                  else if (child.Type == AstBlockType.Else)
265                  {
266                      // Modify the matching if condition to force the else to be entered by the goto.
267                      if (Previous(child) is not AstBlock ifBlock || ifBlock.Type != AstBlockType.If)
268                      {
269                          throw new InvalidOperationException("Found an else without a matching if.");
270                      }
271  
272                      IAstNode cond = InverseCond(stmt.Condition);
273  
274                      if (!ContainsCondComb(ifBlock.Condition, Instruction.LogicalAnd, cond))
275                      {
276                          ifBlock.AndCondition(cond);
277                      }
278  
279                      last = ifBlock;
280                  }
281  
282                  Enclose(block, AstBlockType.If, stmt.Condition, Next(stmt.Goto), last);
283  
284                  block.Remove(stmt.Goto);
285  
286                  child.AddFirst(stmt.Goto);
287  
288                  block = child;
289              }
290          }
291  
292          private static bool ContainsCondComb(IAstNode node, Instruction inst, IAstNode newCond)
293          {
294              while (node is AstOperation operation && operation.SourcesCount == 2)
295              {
296                  if (operation.Inst == inst && IsSameCond(operation.GetSource(1), newCond))
297                  {
298                      return true;
299                  }
300  
301                  node = operation.GetSource(0);
302              }
303  
304              return false;
305          }
306  
307          private static AstBlock EncloseDoWhile(GotoStatement stmt, AstBlock block, IAstNode first)
308          {
309              if (block.Type == AstBlockType.DoWhile && first == block.First)
310              {
311                  // We only need to insert the continue if we're not at the end of the loop,
312                  // or if our condition is different from the loop condition.
313                  if (Next(stmt.Goto) != null || block.Condition != stmt.Condition)
314                  {
315                      EncloseSingleInst(stmt, Instruction.LoopContinue);
316                  }
317  
318                  // Modify the do-while condition to allow it to continue.
319                  if (!ContainsCondComb(block.Condition, Instruction.LogicalOr, stmt.Condition))
320                  {
321                      block.OrCondition(stmt.Condition);
322                  }
323  
324                  return block;
325              }
326  
327              return Enclose(block, AstBlockType.DoWhile, stmt.Condition, first, stmt.Goto);
328          }
329  
330          private static void EncloseSingleInst(GotoStatement stmt, Instruction inst)
331          {
332              AstBlock block = ParentBlock(stmt.Goto);
333  
334              AstBlock newBlock = new(AstBlockType.If, stmt.Condition);
335  
336              block.AddAfter(stmt.Goto, newBlock);
337  
338              newBlock.AddFirst(new AstOperation(inst));
339          }
340  
341          private static AstBlock Enclose(
342              AstBlock block,
343              AstBlockType type,
344              IAstNode cond,
345              IAstNode first,
346              IAstNode last = null)
347          {
348              if (first == last)
349              {
350                  return null;
351              }
352  
353              if (type == AstBlockType.If)
354              {
355                  cond = InverseCond(cond);
356              }
357  
358              // Do a quick check, if we are enclosing a single block,
359              // and the block type/condition matches the one we're going
360              // to create, then we don't need a new block, we can just
361              // return the old one.
362              bool hasSingleNode = Next(first) == last;
363  
364              if (hasSingleNode && BlockMatches(first, type, cond))
365              {
366                  return first as AstBlock;
367              }
368  
369              AstBlock newBlock = new(type, cond);
370  
371              block.AddBefore(first, newBlock);
372  
373              while (first != last)
374              {
375                  IAstNode next = Next(first);
376  
377                  block.Remove(first);
378  
379                  newBlock.Add(first);
380  
381                  first = next;
382              }
383  
384              return newBlock;
385          }
386  
387          private static bool BlockMatches(IAstNode node, AstBlockType type, IAstNode cond)
388          {
389              if (node is not AstBlock block)
390              {
391                  return false;
392              }
393  
394              return block.Type == type && IsSameCond(block.Condition, cond);
395          }
396  
397          private static bool IsSameCond(IAstNode lCond, IAstNode rCond)
398          {
399              if (lCond is AstOperation lCondOp && lCondOp.Inst == Instruction.LogicalNot)
400              {
401                  if (rCond is not AstOperation rCondOp || rCondOp.Inst != lCondOp.Inst)
402                  {
403                      return false;
404                  }
405  
406                  lCond = lCondOp.GetSource(0);
407                  rCond = rCondOp.GetSource(0);
408              }
409  
410              return lCond == rCond;
411          }
412  
413          private static AstBlock ParentBlock(IAstNode node)
414          {
415              if (node is AstBlock block)
416              {
417                  return block.Parent;
418              }
419  
420              while (node is not AstBlock)
421              {
422                  node = node.Parent;
423              }
424  
425              return node as AstBlock;
426          }
427  
428          private static AstBlock[] BackwardsPath(AstBlock top, AstBlock bottom)
429          {
430              AstBlock block = bottom;
431  
432              List<AstBlock> path = new();
433  
434              while (block != top)
435              {
436                  path.Add(block);
437  
438                  block = block.Parent;
439              }
440  
441              return path.ToArray();
442          }
443  
444          private static int Level(IAstNode node)
445          {
446              int level = 0;
447  
448              while (node != null)
449              {
450                  level++;
451  
452                  node = node.Parent;
453              }
454  
455              return level;
456          }
457      }
458  }