1  using Ryujinx.Graphics.Shader.IntermediateRepresentation;
  2  using System;
  3  using System.Collections.Generic;
  4  using System.Linq;
  5  
  6  namespace Ryujinx.Graphics.Shader.Decoders
  7  {
  8      class PushOpInfo
  9      {
 10          public InstOp Op { get; }
 11          public Dictionary<Block, Operand> Consumers;
 12  
 13          public PushOpInfo(InstOp op)
 14          {
 15              Op = op;
 16              Consumers = new Dictionary<Block, Operand>();
 17          }
 18      }
 19  
 20      readonly struct SyncTarget
 21      {
 22          public PushOpInfo PushOpInfo { get; }
 23          public int PushOpId { get; }
 24  
 25          public SyncTarget(PushOpInfo pushOpInfo, int pushOpId)
 26          {
 27              PushOpInfo = pushOpInfo;
 28              PushOpId = pushOpId;
 29          }
 30      }
 31  
 32      class Block
 33      {
 34          public ulong Address { get; set; }
 35          public ulong EndAddress { get; set; }
 36  
 37          public List<Block> Predecessors { get; }
 38          public List<Block> Successors { get; }
 39  
 40          public List<InstOp> OpCodes { get; }
 41          public List<PushOpInfo> PushOpCodes { get; }
 42          public Dictionary<ulong, SyncTarget> SyncTargets { get; }
 43  
 44          public Block(ulong address)
 45          {
 46              Address = address;
 47  
 48              Predecessors = new List<Block>();
 49              Successors = new List<Block>();
 50  
 51              OpCodes = new List<InstOp>();
 52              PushOpCodes = new List<PushOpInfo>();
 53              SyncTargets = new Dictionary<ulong, SyncTarget>();
 54          }
 55  
 56          public void Split(Block rightBlock)
 57          {
 58              int splitIndex = BinarySearch(OpCodes, rightBlock.Address);
 59  
 60              if (OpCodes[splitIndex].Address < rightBlock.Address)
 61              {
 62                  splitIndex++;
 63              }
 64  
 65              int splitCount = OpCodes.Count - splitIndex;
 66              if (splitCount <= 0)
 67              {
 68                  throw new ArgumentException("Can't split at right block address.");
 69              }
 70  
 71              rightBlock.EndAddress = EndAddress;
 72              rightBlock.Successors.AddRange(Successors);
 73              rightBlock.Predecessors.Add(this);
 74  
 75              EndAddress = rightBlock.Address;
 76  
 77              Successors.Clear();
 78              Successors.Add(rightBlock);
 79  
 80              // Move ops.
 81              rightBlock.OpCodes.AddRange(OpCodes.GetRange(splitIndex, splitCount));
 82  
 83              OpCodes.RemoveRange(splitIndex, splitCount);
 84  
 85              // Update push consumers that points to this block.
 86              foreach (SyncTarget syncTarget in SyncTargets.Values)
 87              {
 88                  PushOpInfo pushOpInfo = syncTarget.PushOpInfo;
 89  
 90                  Operand local = pushOpInfo.Consumers[this];
 91                  pushOpInfo.Consumers.Remove(this);
 92                  pushOpInfo.Consumers.Add(rightBlock, local);
 93              }
 94  
 95              foreach ((ulong key, SyncTarget value) in SyncTargets)
 96              {
 97                  rightBlock.SyncTargets.Add(key, value);
 98              }
 99  
100              SyncTargets.Clear();
101  
102              // Move push ops.
103              for (int i = 0; i < PushOpCodes.Count; i++)
104              {
105                  if (PushOpCodes[i].Op.Address >= rightBlock.Address)
106                  {
107                      int count = PushOpCodes.Count - i;
108                      rightBlock.PushOpCodes.AddRange(PushOpCodes.Skip(i));
109                      PushOpCodes.RemoveRange(i, count);
110                      break;
111                  }
112              }
113          }
114  
115          private static int BinarySearch(List<InstOp> opCodes, ulong address)
116          {
117              int left = 0;
118              int middle = 0;
119              int right = opCodes.Count - 1;
120  
121              while (left <= right)
122              {
123                  int size = right - left;
124  
125                  middle = left + (size >> 1);
126  
127                  InstOp opCode = opCodes[middle];
128  
129                  if (address == opCode.Address)
130                  {
131                      break;
132                  }
133  
134                  if (address < opCode.Address)
135                  {
136                      right = middle - 1;
137                  }
138                  else
139                  {
140                      left = middle + 1;
141                  }
142              }
143  
144              return middle;
145          }
146  
147          public InstOp GetLastOp()
148          {
149              if (OpCodes.Count != 0)
150              {
151                  return OpCodes[^1];
152              }
153  
154              return default;
155          }
156  
157          public bool HasNext()
158          {
159              InstOp lastOp = GetLastOp();
160              return OpCodes.Count != 0 && !Decoder.IsUnconditionalBranch(ref lastOp);
161          }
162  
163          public void AddPushOp(InstOp op)
164          {
165              PushOpCodes.Add(new PushOpInfo(op));
166          }
167      }
168  }