1 files changed, 594 insertions, 0 deletions
diff --git a/src/ARMeilleure/IntermediateRepresentation/Operand.cs b/src/ARMeilleure/IntermediateRepresentation/Operand.cs
new file mode 100644
index 00000000..9e8de3ba
--- /dev/null
+++ b/src/ARMeilleure/IntermediateRepresentation/Operand.cs
@@ -0,0 +1,594 @@
+using ARMeilleure.CodeGen.Linking;
+using ARMeilleure.Common;
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Runtime.CompilerServices;
+
+namespace ARMeilleure.IntermediateRepresentation
+{
+    unsafe struct Operand : IEquatable<Operand>
+    {
+        internal struct Data
+        {
+            public byte Kind;
+            public byte Type;
+            public byte SymbolType;
+            public byte Padding; // Unused space.
+            public ushort AssignmentsCount;
+            public ushort AssignmentsCapacity;
+            public uint UsesCount;
+            public uint UsesCapacity;
+            public Operation* Assignments;
+            public Operation* Uses;
+            public ulong Value;
+            public ulong SymbolValue;
+        }
+
+        private Data* _data;
+
+        public OperandKind Kind
+        {
+            get => (OperandKind)_data->Kind;
+            private set => _data->Kind = (byte)value;
+        }
+
+        public OperandType Type
+        {
+            get => (OperandType)_data->Type;
+            private set => _data->Type = (byte)value;
+        }
+
+        public ulong Value
+        {
+            get => _data->Value;
+            private set => _data->Value = value;
+        }
+
+        public Symbol Symbol
+        {
+            get
+            {
+                Debug.Assert(Kind != OperandKind.Memory);
+
+                return new Symbol((SymbolType)_data->SymbolType, _data->SymbolValue);
+            }
+            private set
+            {
+                Debug.Assert(Kind != OperandKind.Memory);
+
+                if (value.Type == SymbolType.None)
+                {
+                    _data->SymbolType = (byte)SymbolType.None;
+                }
+                else
+                {
+                    _data->SymbolType = (byte)value.Type;
+                    _data->SymbolValue = value.Value;
+                }
+            }
+        }
+
+        public ReadOnlySpan<Operation> Assignments
+        {
+            get
+            {
+                Debug.Assert(Kind != OperandKind.Memory);
+
+                return new ReadOnlySpan<Operation>(_data->Assignments, _data->AssignmentsCount);
+            }
+        }
+
+        public ReadOnlySpan<Operation> Uses
+        {
+            get
+            {
+                Debug.Assert(Kind != OperandKind.Memory);
+
+                return new ReadOnlySpan<Operation>(_data->Uses, (int)_data->UsesCount);
+            }
+        }
+
+        public int UsesCount => (int)_data->UsesCount;
+        public int AssignmentsCount => _data->AssignmentsCount;
+
+        public bool Relocatable => Symbol.Type != SymbolType.None;
+
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        public Register GetRegister()
+        {
+            Debug.Assert(Kind == OperandKind.Register);
+
+            return new Register((int)Value & 0xffffff, (RegisterType)(Value >> 24));
+        }
+
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        public MemoryOperand GetMemory()
+        {
+            Debug.Assert(Kind == OperandKind.Memory);
+
+            return new MemoryOperand(this);
+        }
+
+        public int GetLocalNumber()
+        {
+            Debug.Assert(Kind == OperandKind.LocalVariable);
+
+            return (int)Value;
+        }
+
+        public byte AsByte()
+        {
+            return (byte)Value;
+        }
+
+        public short AsInt16()
+        {
+            return (short)Value;
+        }
+
+        public int AsInt32()
+        {
+            return (int)Value;
+        }
+
+        public long AsInt64()
+        {
+            return (long)Value;
+        }
+
+        public float AsFloat()
+        {
+            return BitConverter.Int32BitsToSingle((int)Value);
+        }
+
+        public double AsDouble()
+        {
+            return BitConverter.Int64BitsToDouble((long)Value);
+        }
+
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        internal ref ulong GetValueUnsafe()
+        {
+            return ref _data->Value;
+        }
+
+        internal void NumberLocal(int number)
+        {
+            if (Kind != OperandKind.LocalVariable)
+            {
+                throw new InvalidOperationException("The operand is not a local variable.");
+            }
+
+            Value = (ulong)number;
+        }
+
+        public void AddAssignment(Operation operation)
+        {
+            if (Kind == OperandKind.LocalVariable)
+            {
+                Add(operation, ref _data->Assignments, ref _data->AssignmentsCount, ref _data->AssignmentsCapacity);
+            }
+            else if (Kind == OperandKind.Memory)
+            {
+                MemoryOperand memOp = GetMemory();
+                Operand addr = memOp.BaseAddress;
+                Operand index = memOp.Index;
+
+                if (addr != default)
+                {
+                    Add(operation, ref addr._data->Assignments, ref addr._data->AssignmentsCount, ref addr._data->AssignmentsCapacity);
+                }
+
+                if (index != default)
+                {
+                    Add(operation, ref index._data->Assignments, ref index._data->AssignmentsCount, ref index._data->AssignmentsCapacity);
+                }
+            }
+        }
+
+        public void RemoveAssignment(Operation operation)
+        {
+            if (Kind == OperandKind.LocalVariable)
+            {
+                Remove(operation, ref _data->Assignments, ref _data->AssignmentsCount);
+            }
+            else if (Kind == OperandKind.Memory)
+            {
+                MemoryOperand memOp = GetMemory();
+                Operand addr = memOp.BaseAddress;
+                Operand index = memOp.Index;
+
+                if (addr != default)
+                {
+                    Remove(operation, ref addr._data->Assignments, ref addr._data->AssignmentsCount);
+                }
+
+                if (index != default)
+                {
+                    Remove(operation, ref index._data->Assignments, ref index._data->AssignmentsCount);
+                }
+            }
+        }
+
+        public void AddUse(Operation operation)
+        {
+            if (Kind == OperandKind.LocalVariable)
+            {
+                Add(operation, ref _data->Uses, ref _data->UsesCount, ref _data->UsesCapacity);
+            }
+            else if (Kind == OperandKind.Memory)
+            {
+                MemoryOperand memOp = GetMemory();
+                Operand addr = memOp.BaseAddress;
+                Operand index = memOp.Index;
+
+                if (addr != default)
+                {
+                    Add(operation, ref addr._data->Uses, ref addr._data->UsesCount, ref addr._data->UsesCapacity);
+                }
+
+                if (index != default)
+                {
+                    Add(operation, ref index._data->Uses, ref index._data->UsesCount, ref index._data->UsesCapacity);
+                }
+            }
+        }
+
+        public void RemoveUse(Operation operation)
+        {
+            if (Kind == OperandKind.LocalVariable)
+            {
+                Remove(operation, ref _data->Uses, ref _data->UsesCount);
+            }
+            else if (Kind == OperandKind.Memory)
+            {
+                MemoryOperand memOp = GetMemory();
+                Operand addr = memOp.BaseAddress;
+                Operand index = memOp.Index;
+
+                if (addr != default)
+                {
+                    Remove(operation, ref addr._data->Uses, ref addr._data->UsesCount);
+                }
+
+                if (index != default)
+                {
+                    Remove(operation, ref index._data->Uses, ref index._data->UsesCount);
+                }
+            }
+        }
+
+        public Span<Operation> GetUses(ref Span<Operation> buffer)
+        {
+            ReadOnlySpan<Operation> uses = Uses;
+
+            if (buffer.Length < uses.Length)
+            {
+                buffer = Allocators.Default.AllocateSpan<Operation>((uint)uses.Length);
+            }
+
+            uses.CopyTo(buffer);
+
+            return buffer.Slice(0, uses.Length);
+        }
+
+        private static void New<T>(ref T* data, ref ushort count, ref ushort capacity, ushort initialCapacity) where T : unmanaged
+        {
+            count = 0;
+            capacity = initialCapacity;
+            data = Allocators.References.Allocate<T>(initialCapacity);
+        }
+
+        private static void New<T>(ref T* data, ref uint count, ref uint capacity, uint initialCapacity) where T : unmanaged
+        {
+            count = 0;
+            capacity = initialCapacity;
+            data = Allocators.References.Allocate<T>(initialCapacity);
+        }
+
+        private static void Add<T>(T item, ref T* data, ref ushort count, ref ushort capacity) where T : unmanaged
+        {
+            if (count < capacity)
+            {
+                data[(uint)count++] = item;
+
+                return;
+            }
+
+            // Could not add item in the fast path, fallback onto the slow path.
+            ExpandAdd(item, ref data, ref count, ref capacity);
+
+            static void ExpandAdd(T item, ref T* data, ref ushort count, ref ushort capacity)
+            {
+                ushort newCount = checked((ushort)(count + 1));
+                ushort newCapacity = (ushort)Math.Min(capacity * 2, ushort.MaxValue);
+
+                var oldSpan = new Span<T>(data, count);
+
+                capacity = newCapacity;
+                data = Allocators.References.Allocate<T>(capacity);
+
+                oldSpan.CopyTo(new Span<T>(data, count));
+
+                data[count] = item;
+                count = newCount;
+            }
+        }
+
+        private static void Add<T>(T item, ref T* data, ref uint count, ref uint capacity) where T : unmanaged
+        {
+            if (count < capacity)
+            {
+                data[count++] = item;
+
+                return;
+            }
+
+            // Could not add item in the fast path, fallback onto the slow path.
+            ExpandAdd(item, ref data, ref count, ref capacity);
+
+            static void ExpandAdd(T item, ref T* data, ref uint count, ref uint capacity)
+            {
+                uint newCount = checked(count + 1);
+                uint newCapacity = (uint)Math.Min(capacity * 2, int.MaxValue);
+
+                if (newCapacity <= capacity)
+                {
+                    throw new OverflowException();
+                }
+
+                var oldSpan = new Span<T>(data, (int)count);
+
+                capacity = newCapacity;
+                data = Allocators.References.Allocate<T>(capacity);
+
+                oldSpan.CopyTo(new Span<T>(data, (int)count));
+
+                data[count] = item;
+                count = newCount;
+            }
+        }
+
+        private static void Remove<T>(in T item, ref T* data, ref ushort count) where T : unmanaged
+        {
+            var span = new Span<T>(data, count);
+
+            for (int i = 0; i < span.Length; i++)
+            {
+                if (EqualityComparer<T>.Default.Equals(span[i], item))
+                {
+                    if (i + 1 < count)
+                    {
+                        span.Slice(i + 1).CopyTo(span.Slice(i));
+                    }
+
+                    count--;
+
+                    return;
+                }
+            }
+        }
+
+        private static void Remove<T>(in T item, ref T* data, ref uint count) where T : unmanaged
+        {
+            var span = new Span<T>(data, (int)count);
+
+            for (int i = 0; i < span.Length; i++)
+            {
+                if (EqualityComparer<T>.Default.Equals(span[i], item))
+                {
+                    if (i + 1 < count)
+                    {
+                        span.Slice(i + 1).CopyTo(span.Slice(i));
+                    }
+
+                    count--;
+
+                    return;
+                }
+            }
+        }
+
+        public override int GetHashCode()
+        {
+            return ((ulong)_data).GetHashCode();
+        }
+
+        public bool Equals(Operand operand)
+        {
+            return operand._data == _data;
+        }
+
+        public override bool Equals(object obj)
+        {
+            return obj is Operand operand && Equals(operand);
+        }
+
+        public static bool operator ==(Operand a, Operand b)
+        {
+            return a.Equals(b);
+        }
+
+        public static bool operator !=(Operand a, Operand b)
+        {
+            return !a.Equals(b);
+        }
+
+        public static class Factory
+        {
+            private const int InternTableSize = 256;
+            private const int InternTableProbeLength = 8;
+
+            [ThreadStatic]
+            private static Data* _internTable;
+
+            private static Data* InternTable
+            {
+                get
+                {
+                    if (_internTable == null)
+                    {
+                        _internTable = (Data*)NativeAllocator.Instance.Allocate((uint)sizeof(Data) * InternTableSize);
+
+                        // Make sure the table is zeroed.
+                        new Span<Data>(_internTable, InternTableSize).Clear();
+                    }
+
+                    return _internTable;
+                }
+            }
+
+            private static Operand Make(OperandKind kind, OperandType type, ulong value, Symbol symbol = default)
+            {
+                Debug.Assert(kind != OperandKind.None);
+
+                Data* data = null;
+
+                // If constant or register, then try to look up in the intern table before allocating.
+                if (kind == OperandKind.Constant || kind == OperandKind.Register)
+                {
+                    uint hash = (uint)HashCode.Combine(kind, type, value);
+
+                    // Look in the next InternTableProbeLength slots for a match.
+                    for (uint i = 0; i < InternTableProbeLength; i++)
+                    {
+                        Operand interned = new();
+                        interned._data = &InternTable[(hash + i) % InternTableSize];
+
+                        // If slot matches the allocation request then return that slot.
+                        if (interned.Kind == kind && interned.Type == type && interned.Value == value && interned.Symbol == symbol)
+                        {
+                            return interned;
+                        }
+                        // Otherwise if the slot is not occupied, we store in that slot.
+                        else if (interned.Kind == OperandKind.None)
+                        {
+                            data = interned._data;
+
+                            break;
+                        }
+                    }
+                }
+
+                // If we could not get a slot from the intern table, we allocate somewhere else and store there.
+                if (data == null)
+                {
+                    data = Allocators.Operands.Allocate<Data>();
+                }
+
+                *data = default;
+
+                Operand result = new();
+                result._data = data;
+                result.Value = value;
+                result.Kind = kind;
+                result.Type = type;
+
+                if (kind != OperandKind.Memory)
+                {
+                    result.Symbol = symbol;
+                }
+
+                // If local variable, then the use and def list is initialized with default sizes.
+                if (kind == OperandKind.LocalVariable)
+                {
+                    New(ref result._data->Assignments, ref result._data->AssignmentsCount, ref result._data->AssignmentsCapacity, 1);
+                    New(ref result._data->Uses, ref result._data->UsesCount, ref result._data->UsesCapacity, 4);
+                }
+
+                return result;
+            }
+
+            public static Operand Const(OperandType type, long value)
+            {
+                Debug.Assert(type is OperandType.I32 or OperandType.I64);
+
+                return type == OperandType.I32 ? Const((int)value) : Const(value);
+            }
+
+            public static Operand Const(bool value)
+            {
+                return Const(value ? 1 : 0);
+            }
+
+            public static Operand Const(int value)
+            {
+                return Const((uint)value);
+            }
+
+            public static Operand Const(uint value)
+            {
+                return Make(OperandKind.Constant, OperandType.I32, value);
+            }
+
+            public static Operand Const(long value)
+            {
+                return Const(value, symbol: default);
+            }
+
+            public static Operand Const<T>(ref T reference, Symbol symbol = default)
+            {
+                return Const((long)Unsafe.AsPointer(ref reference), symbol);
+            }
+
+            public static Operand Const(long value, Symbol symbol)
+            {
+                return Make(OperandKind.Constant, OperandType.I64, (ulong)value, symbol);
+            }
+
+            public static Operand Const(ulong value)
+            {
+                return Make(OperandKind.Constant, OperandType.I64, value);
+            }
+
+            public static Operand ConstF(float value)
+            {
+                return Make(OperandKind.Constant, OperandType.FP32, (ulong)BitConverter.SingleToInt32Bits(value));
+            }
+
+            public static Operand ConstF(double value)
+            {
+                return Make(OperandKind.Constant, OperandType.FP64, (ulong)BitConverter.DoubleToInt64Bits(value));
+            }
+
+            public static Operand Label()
+            {
+                return Make(OperandKind.Label, OperandType.None, 0);
+            }
+
+            public static Operand Local(OperandType type)
+            {
+                return Make(OperandKind.LocalVariable, type, 0);
+            }
+
+            public static Operand Register(int index, RegisterType regType, OperandType type)
+            {
+                return Make(OperandKind.Register, type, (ulong)((int)regType << 24 | index));
+            }
+
+            public static Operand Undef()
+            {
+                return Make(OperandKind.Undefined, OperandType.None, 0);
+            }
+
+            public static Operand MemoryOp(
+                OperandType type,
+                Operand baseAddress,
+                Operand index = default,
+                Multiplier scale = Multiplier.x1,
+                int displacement = 0)
+            {
+                Operand result = Make(OperandKind.Memory, type, 0);
+
+                MemoryOperand memory = result.GetMemory();
+                memory.BaseAddress = baseAddress;
+                memory.Index = index;
+                memory.Scale = scale;
+                memory.Displacement = displacement;
+
+                return result;
+            }
+        }
+    }
+}
+\ No newline at end of file