1  using ARMeilleure.CodeGen.Linking;
  2  using ARMeilleure.Common;
  3  using System;
  4  using System.Collections.Generic;
  5  using System.Diagnostics;
  6  using System.Runtime.CompilerServices;
  7  
  8  namespace ARMeilleure.IntermediateRepresentation
  9  {
 10      unsafe struct Operand : IEquatable<Operand>
 11      {
 12          internal struct Data
 13          {
 14              public byte Kind;
 15              public byte Type;
 16              public byte SymbolType;
 17              public byte Padding; // Unused space.
 18              public ushort AssignmentsCount;
 19              public ushort AssignmentsCapacity;
 20              public uint UsesCount;
 21              public uint UsesCapacity;
 22              public Operation* Assignments;
 23              public Operation* Uses;
 24              public ulong Value;
 25              public ulong SymbolValue;
 26          }
 27  
 28          private Data* _data;
 29  
 30          public readonly OperandKind Kind
 31          {
 32              get => (OperandKind)_data->Kind;
 33              private set => _data->Kind = (byte)value;
 34          }
 35  
 36          public readonly OperandType Type
 37          {
 38              get => (OperandType)_data->Type;
 39              private set => _data->Type = (byte)value;
 40          }
 41  
 42          public readonly ulong Value
 43          {
 44              get => _data->Value;
 45              private set => _data->Value = value;
 46          }
 47  
 48          public readonly Symbol Symbol
 49          {
 50              get
 51              {
 52                  Debug.Assert(Kind != OperandKind.Memory);
 53  
 54                  return new Symbol((SymbolType)_data->SymbolType, _data->SymbolValue);
 55              }
 56              private set
 57              {
 58                  Debug.Assert(Kind != OperandKind.Memory);
 59  
 60                  if (value.Type == SymbolType.None)
 61                  {
 62                      _data->SymbolType = (byte)SymbolType.None;
 63                  }
 64                  else
 65                  {
 66                      _data->SymbolType = (byte)value.Type;
 67                      _data->SymbolValue = value.Value;
 68                  }
 69              }
 70          }
 71  
 72          public readonly ReadOnlySpan<Operation> Assignments
 73          {
 74              get
 75              {
 76                  Debug.Assert(Kind != OperandKind.Memory);
 77  
 78                  return new ReadOnlySpan<Operation>(_data->Assignments, _data->AssignmentsCount);
 79              }
 80          }
 81  
 82          public readonly ReadOnlySpan<Operation> Uses
 83          {
 84              get
 85              {
 86                  Debug.Assert(Kind != OperandKind.Memory);
 87  
 88                  return new ReadOnlySpan<Operation>(_data->Uses, (int)_data->UsesCount);
 89              }
 90          }
 91  
 92          public readonly int UsesCount => (int)_data->UsesCount;
 93          public readonly int AssignmentsCount => _data->AssignmentsCount;
 94  
 95          public readonly bool Relocatable => Symbol.Type != SymbolType.None;
 96  
 97          [MethodImpl(MethodImplOptions.AggressiveInlining)]
 98          public readonly Register GetRegister()
 99          {
100              Debug.Assert(Kind == OperandKind.Register);
101  
102              return new Register((int)Value & 0xffffff, (RegisterType)(Value >> 24));
103          }
104  
105          [MethodImpl(MethodImplOptions.AggressiveInlining)]
106          public readonly MemoryOperand GetMemory()
107          {
108              Debug.Assert(Kind == OperandKind.Memory);
109  
110              return new MemoryOperand(this);
111          }
112  
113          public readonly int GetLocalNumber()
114          {
115              Debug.Assert(Kind == OperandKind.LocalVariable);
116  
117              return (int)Value;
118          }
119  
120          public readonly byte AsByte()
121          {
122              return (byte)Value;
123          }
124  
125          public readonly short AsInt16()
126          {
127              return (short)Value;
128          }
129  
130          public readonly int AsInt32()
131          {
132              return (int)Value;
133          }
134  
135          public readonly long AsInt64()
136          {
137              return (long)Value;
138          }
139  
140          public readonly float AsFloat()
141          {
142              return BitConverter.Int32BitsToSingle((int)Value);
143          }
144  
145          public readonly double AsDouble()
146          {
147              return BitConverter.Int64BitsToDouble((long)Value);
148          }
149  
150          [MethodImpl(MethodImplOptions.AggressiveInlining)]
151          internal readonly ref ulong GetValueUnsafe()
152          {
153              return ref _data->Value;
154          }
155  
156          internal void NumberLocal(int number)
157          {
158              if (Kind != OperandKind.LocalVariable)
159              {
160                  throw new InvalidOperationException("The operand is not a local variable.");
161              }
162  
163              Value = (ulong)number;
164          }
165  
166          public readonly void AddAssignment(Operation operation)
167          {
168              if (Kind == OperandKind.LocalVariable)
169              {
170                  Add(operation, ref _data->Assignments, ref _data->AssignmentsCount, ref _data->AssignmentsCapacity);
171              }
172              else if (Kind == OperandKind.Memory)
173              {
174                  MemoryOperand memOp = GetMemory();
175                  Operand addr = memOp.BaseAddress;
176                  Operand index = memOp.Index;
177  
178                  if (addr != default)
179                  {
180                      Add(operation, ref addr._data->Assignments, ref addr._data->AssignmentsCount, ref addr._data->AssignmentsCapacity);
181                  }
182  
183                  if (index != default)
184                  {
185                      Add(operation, ref index._data->Assignments, ref index._data->AssignmentsCount, ref index._data->AssignmentsCapacity);
186                  }
187              }
188          }
189  
190          public readonly void RemoveAssignment(Operation operation)
191          {
192              if (Kind == OperandKind.LocalVariable)
193              {
194                  Remove(operation, ref _data->Assignments, ref _data->AssignmentsCount);
195              }
196              else if (Kind == OperandKind.Memory)
197              {
198                  MemoryOperand memOp = GetMemory();
199                  Operand addr = memOp.BaseAddress;
200                  Operand index = memOp.Index;
201  
202                  if (addr != default)
203                  {
204                      Remove(operation, ref addr._data->Assignments, ref addr._data->AssignmentsCount);
205                  }
206  
207                  if (index != default)
208                  {
209                      Remove(operation, ref index._data->Assignments, ref index._data->AssignmentsCount);
210                  }
211              }
212          }
213  
214          public readonly void AddUse(Operation operation)
215          {
216              if (Kind == OperandKind.LocalVariable)
217              {
218                  Add(operation, ref _data->Uses, ref _data->UsesCount, ref _data->UsesCapacity);
219              }
220              else if (Kind == OperandKind.Memory)
221              {
222                  MemoryOperand memOp = GetMemory();
223                  Operand addr = memOp.BaseAddress;
224                  Operand index = memOp.Index;
225  
226                  if (addr != default)
227                  {
228                      Add(operation, ref addr._data->Uses, ref addr._data->UsesCount, ref addr._data->UsesCapacity);
229                  }
230  
231                  if (index != default)
232                  {
233                      Add(operation, ref index._data->Uses, ref index._data->UsesCount, ref index._data->UsesCapacity);
234                  }
235              }
236          }
237  
238          public readonly void RemoveUse(Operation operation)
239          {
240              if (Kind == OperandKind.LocalVariable)
241              {
242                  Remove(operation, ref _data->Uses, ref _data->UsesCount);
243              }
244              else if (Kind == OperandKind.Memory)
245              {
246                  MemoryOperand memOp = GetMemory();
247                  Operand addr = memOp.BaseAddress;
248                  Operand index = memOp.Index;
249  
250                  if (addr != default)
251                  {
252                      Remove(operation, ref addr._data->Uses, ref addr._data->UsesCount);
253                  }
254  
255                  if (index != default)
256                  {
257                      Remove(operation, ref index._data->Uses, ref index._data->UsesCount);
258                  }
259              }
260          }
261  
262          public readonly Span<Operation> GetUses(ref Span<Operation> buffer)
263          {
264              ReadOnlySpan<Operation> uses = Uses;
265  
266              if (buffer.Length < uses.Length)
267              {
268                  buffer = Allocators.Default.AllocateSpan<Operation>((uint)uses.Length);
269              }
270  
271              uses.CopyTo(buffer);
272  
273              return buffer[..uses.Length];
274          }
275  
276          private static void New<T>(ref T* data, ref ushort count, ref ushort capacity, ushort initialCapacity) where T : unmanaged
277          {
278              count = 0;
279              capacity = initialCapacity;
280              data = Allocators.References.Allocate<T>(initialCapacity);
281          }
282  
283          private static void New<T>(ref T* data, ref uint count, ref uint capacity, uint initialCapacity) where T : unmanaged
284          {
285              count = 0;
286              capacity = initialCapacity;
287              data = Allocators.References.Allocate<T>(initialCapacity);
288          }
289  
290          private static void Add<T>(T item, ref T* data, ref ushort count, ref ushort capacity) where T : unmanaged
291          {
292              if (count < capacity)
293              {
294                  data[(uint)count++] = item;
295  
296                  return;
297              }
298  
299              // Could not add item in the fast path, fallback onto the slow path.
300              ExpandAdd(item, ref data, ref count, ref capacity);
301  
302              static void ExpandAdd(T item, ref T* data, ref ushort count, ref ushort capacity)
303              {
304                  ushort newCount = checked((ushort)(count + 1));
305                  ushort newCapacity = (ushort)Math.Min(capacity * 2, ushort.MaxValue);
306  
307                  var oldSpan = new Span<T>(data, count);
308  
309                  capacity = newCapacity;
310                  data = Allocators.References.Allocate<T>(capacity);
311  
312                  oldSpan.CopyTo(new Span<T>(data, count));
313  
314                  data[count] = item;
315                  count = newCount;
316              }
317          }
318  
319          private static void Add<T>(T item, ref T* data, ref uint count, ref uint capacity) where T : unmanaged
320          {
321              if (count < capacity)
322              {
323                  data[count++] = item;
324  
325                  return;
326              }
327  
328              // Could not add item in the fast path, fallback onto the slow path.
329              ExpandAdd(item, ref data, ref count, ref capacity);
330  
331              static void ExpandAdd(T item, ref T* data, ref uint count, ref uint capacity)
332              {
333                  uint newCount = checked(count + 1);
334                  uint newCapacity = (uint)Math.Min(capacity * 2, int.MaxValue);
335  
336                  if (newCapacity <= capacity)
337                  {
338                      throw new OverflowException();
339                  }
340  
341                  var oldSpan = new Span<T>(data, (int)count);
342  
343                  capacity = newCapacity;
344                  data = Allocators.References.Allocate<T>(capacity);
345  
346                  oldSpan.CopyTo(new Span<T>(data, (int)count));
347  
348                  data[count] = item;
349                  count = newCount;
350              }
351          }
352  
353          private static void Remove<T>(in T item, ref T* data, ref ushort count) where T : unmanaged
354          {
355              var span = new Span<T>(data, count);
356  
357              for (int i = 0; i < span.Length; i++)
358              {
359                  if (EqualityComparer<T>.Default.Equals(span[i], item))
360                  {
361                      if (i + 1 < count)
362                      {
363                          span[(i + 1)..].CopyTo(span[i..]);
364                      }
365  
366                      count--;
367  
368                      return;
369                  }
370              }
371          }
372  
373          private static void Remove<T>(in T item, ref T* data, ref uint count) where T : unmanaged
374          {
375              var span = new Span<T>(data, (int)count);
376  
377              for (int i = 0; i < span.Length; i++)
378              {
379                  if (EqualityComparer<T>.Default.Equals(span[i], item))
380                  {
381                      if (i + 1 < count)
382                      {
383                          span[(i + 1)..].CopyTo(span[i..]);
384                      }
385  
386                      count--;
387  
388                      return;
389                  }
390              }
391          }
392  
393          public readonly override int GetHashCode()
394          {
395              return ((ulong)_data).GetHashCode();
396          }
397  
398          public readonly bool Equals(Operand operand)
399          {
400              return operand._data == _data;
401          }
402  
403          public readonly override bool Equals(object obj)
404          {
405              return obj is Operand operand && Equals(operand);
406          }
407  
408          public static bool operator ==(Operand a, Operand b)
409          {
410              return a.Equals(b);
411          }
412  
413          public static bool operator !=(Operand a, Operand b)
414          {
415              return !a.Equals(b);
416          }
417  
418          public static class Factory
419          {
420              private const int InternTableSize = 256;
421              private const int InternTableProbeLength = 8;
422  
423              [ThreadStatic]
424              private static Data* _internTable;
425  
426              private static Data* InternTable
427              {
428                  get
429                  {
430                      if (_internTable == null)
431                      {
432                          _internTable = (Data*)NativeAllocator.Instance.Allocate((uint)sizeof(Data) * InternTableSize);
433  
434                          // Make sure the table is zeroed.
435                          new Span<Data>(_internTable, InternTableSize).Clear();
436                      }
437  
438                      return _internTable;
439                  }
440              }
441  
442              private static Operand Make(OperandKind kind, OperandType type, ulong value, Symbol symbol = default)
443              {
444                  Debug.Assert(kind != OperandKind.None);
445  
446                  Data* data = null;
447  
448                  // If constant or register, then try to look up in the intern table before allocating.
449                  if (kind == OperandKind.Constant || kind == OperandKind.Register)
450                  {
451                      uint hash = (uint)HashCode.Combine(kind, type, value);
452  
453                      // Look in the next InternTableProbeLength slots for a match.
454                      for (uint i = 0; i < InternTableProbeLength; i++)
455                      {
456                          Operand interned = new()
457                          {
458                              _data = &InternTable[(hash + i) % InternTableSize],
459                          };
460  
461                          // If slot matches the allocation request then return that slot.
462                          if (interned.Kind == kind && interned.Type == type && interned.Value == value && interned.Symbol == symbol)
463                          {
464                              return interned;
465                          }
466                          // Otherwise if the slot is not occupied, we store in that slot.
467                          else if (interned.Kind == OperandKind.None)
468                          {
469                              data = interned._data;
470  
471                              break;
472                          }
473                      }
474                  }
475  
476                  // If we could not get a slot from the intern table, we allocate somewhere else and store there.
477                  if (data == null)
478                  {
479                      data = Allocators.Operands.Allocate<Data>();
480                  }
481  
482                  *data = default;
483  
484                  Operand result = new()
485                  {
486                      _data = data,
487                      Value = value,
488                      Kind = kind,
489                      Type = type,
490                  };
491  
492                  if (kind != OperandKind.Memory)
493                  {
494                      result.Symbol = symbol;
495                  }
496  
497                  // If local variable, then the use and def list is initialized with default sizes.
498                  if (kind == OperandKind.LocalVariable)
499                  {
500                      New(ref result._data->Assignments, ref result._data->AssignmentsCount, ref result._data->AssignmentsCapacity, 1);
501                      New(ref result._data->Uses, ref result._data->UsesCount, ref result._data->UsesCapacity, 4);
502                  }
503  
504                  return result;
505              }
506  
507              public static Operand Const(OperandType type, long value)
508              {
509                  Debug.Assert(type is OperandType.I32 or OperandType.I64);
510  
511                  return type == OperandType.I32 ? Const((int)value) : Const(value);
512              }
513  
514              public static Operand Const(bool value)
515              {
516                  return Const(value ? 1 : 0);
517              }
518  
519              public static Operand Const(int value)
520              {
521                  return Const((uint)value);
522              }
523  
524              public static Operand Const(uint value)
525              {
526                  return Make(OperandKind.Constant, OperandType.I32, value);
527              }
528  
529              public static Operand Const(long value)
530              {
531                  return Const(value, symbol: default);
532              }
533  
534              public static Operand Const<T>(ref T reference, Symbol symbol = default)
535              {
536                  return Const((long)Unsafe.AsPointer(ref reference), symbol);
537              }
538  
539              public static Operand Const(long value, Symbol symbol)
540              {
541                  return Make(OperandKind.Constant, OperandType.I64, (ulong)value, symbol);
542              }
543  
544              public static Operand Const(ulong value)
545              {
546                  return Make(OperandKind.Constant, OperandType.I64, value);
547              }
548  
549              public static Operand ConstF(float value)
550              {
551                  return Make(OperandKind.Constant, OperandType.FP32, (ulong)BitConverter.SingleToInt32Bits(value));
552              }
553  
554              public static Operand ConstF(double value)
555              {
556                  return Make(OperandKind.Constant, OperandType.FP64, (ulong)BitConverter.DoubleToInt64Bits(value));
557              }
558  
559              public static Operand Label()
560              {
561                  return Make(OperandKind.Label, OperandType.None, 0);
562              }
563  
564              public static Operand Local(OperandType type)
565              {
566                  return Make(OperandKind.LocalVariable, type, 0);
567              }
568  
569              public static Operand Register(int index, RegisterType regType, OperandType type)
570              {
571                  return Make(OperandKind.Register, type, (ulong)((int)regType << 24 | index));
572              }
573  
574              public static Operand Undef()
575              {
576                  return Make(OperandKind.Undefined, OperandType.None, 0);
577              }
578  
579              public static Operand MemoryOp(
580                  OperandType type,
581                  Operand baseAddress,
582                  Operand index = default,
583                  Multiplier scale = Multiplier.x1,
584                  int displacement = 0)
585              {
586                  Operand result = Make(OperandKind.Memory, type, 0);
587  
588                  MemoryOperand memory = result.GetMemory();
589                  memory.BaseAddress = baseAddress;
590                  memory.Index = index;
591                  memory.Scale = scale;
592                  memory.Displacement = displacement;
593  
594                  return result;
595              }
596          }
597      }
598  }