using System.Text; using Translator.Core.Ir; namespace Translator.Core.Translation; public interface ICanonicalIrProvider { bool TryGet(uint entryPoint, out IrFunction function); } /// /// Bounded, deterministic canonical SSA ownership for a translation wave. Each /// graph is immediately encoded to numeric opcodes and interned string IDs, so /// the discovery object graph can be collected without repeating front-end work. /// public sealed class CanonicalIrStore : ICanonicalIrProvider { public const int FormatVersion = 1; private readonly object _gate = new(); private readonly Dictionary _entries = new(); public int Count { get { lock (_gate) return _entries.Count; } } public void Put(uint entryPoint, IrFunction ssaFunction) { var encoded = CanonicalIrBinaryCodec.Encode(ssaFunction); lock (_gate) { _entries[entryPoint] = encoded; } } public void Remove(uint entryPoint) { lock (_gate) { _entries.Remove(entryPoint); } } public bool TryGet(uint entryPoint, out IrFunction function) { byte[]? encoded; lock (_gate) _entries.TryGetValue(entryPoint, out encoded); if (encoded is null) { function = null!; return false; } function = CanonicalIrBinaryCodec.Decode(encoded); return true; } } internal static class CanonicalIrBinaryCodec { private static readonly byte[] Magic = "MKWSSA01"u8.ToArray(); private enum Op : byte { Assign, Binary, Load, Store, Call, IndirectCall, SetCrField, Phi, Branch, Jump, IndirectJump, JumpTable, Return, Comment, TracePpc, Undefined } // Reused per thread so encoding doesn't regrow (and re-fault) a fresh buffer per function. [ThreadStatic] private static MemoryStream? _encodeStream; public static byte[] Encode(IrFunction function) { var strings = BuildStringTable(function); var ids = strings.Select((value, index) => (value, index)) .ToDictionary(static pair => pair.value, static pair => pair.index, StringComparer.Ordinal); var stream = _encodeStream ??= new MemoryStream(); stream.SetLength(0); using var writer = new BinaryWriter(stream, Encoding.UTF8, leaveOpen: true); writer.Write(Magic); WriteVarUInt(writer, (uint)CanonicalIrStore.FormatVersion); WriteVarUInt(writer, checked((uint)strings.Count)); foreach (var value in strings) { var bytes = Encoding.UTF8.GetBytes(value); WriteVarUInt(writer, checked((uint)bytes.Length)); writer.Write(bytes); } WriteId(writer, ids, function.Name); WriteId(writer, ids, function.EntryLabel); WriteVarUInt(writer, checked((uint)function.Blocks.Count)); foreach (var block in function.Blocks) { WriteId(writer, ids, block.Label); WriteVarUInt(writer, checked((uint)block.Instructions.Count)); foreach (var instruction in block.Instructions) WriteInstruction(writer, ids, instruction); } writer.Flush(); return stream.ToArray(); } public static IrFunction Decode(ReadOnlySpan encoded) => Decode(encoded.ToArray()); public static IrFunction Decode(byte[] encoded) { using var stream = new MemoryStream(encoded, writable: false); using var reader = new BinaryReader(stream, Encoding.UTF8, leaveOpen: true); if (!reader.ReadBytes(Magic.Length).SequenceEqual(Magic) || ReadVarUInt(reader) != CanonicalIrStore.FormatVersion) throw new InvalidDataException("Unsupported canonical SSA function payload."); var stringCount = CheckedCount(ReadVarUInt(reader)); var strings = new string[stringCount]; for (var i = 0; i < strings.Length; i++) { var length = CheckedCount(ReadVarUInt(reader)); var bytes = reader.ReadBytes(length); if (bytes.Length != length) throw new EndOfStreamException(); strings[i] = Encoding.UTF8.GetString(bytes); } string Id() => strings[CheckedIndex(ReadVarUInt(reader), strings.Length)]; var name = Id(); var entry = Id(); var blocks = new IrBasicBlock[CheckedCount(ReadVarUInt(reader))]; for (var blockIndex = 0; blockIndex < blocks.Length; blockIndex++) { var label = Id(); var instructions = new IrInstruction[CheckedCount(ReadVarUInt(reader))]; for (var instructionIndex = 0; instructionIndex < instructions.Length; instructionIndex++) instructions[instructionIndex] = ReadInstruction(reader, strings); blocks[blockIndex] = new IrBasicBlock(label, instructions); } if (stream.Position != stream.Length) throw new InvalidDataException("Canonical SSA function payload has trailing data."); return new IrFunction(name, entry, blocks); } private static List BuildStringTable(IrFunction function) { var result = new List(); var seen = new HashSet(StringComparer.Ordinal); void Add(string? value) { if (value is not null && seen.Add(value)) result.Add(value); } void Value(IrValue value) { Add(value.RegisterName); if (value.Kind is not ("register" or "const")) Add(value.Kind); } Add(function.Name); Add(function.EntryLabel); foreach (var block in function.Blocks) { Add(block.Label); foreach (var instruction in block.Instructions) { switch (instruction) { case IrAssign x: Add(x.Destination); Value(x.Value); break; case IrBinary x: Add(x.Destination); Value(x.Left); Value(x.Right); Add(x.Op); break; case IrLoad x: Add(x.Destination); Add(x.Address.Base); break; case IrStore x: Add(x.Address.Base); Value(x.Source); break; case IrCall x: Add(x.Destination); Add(x.Target); foreach (var v in x.Arguments) Value(v); break; case IrIndirectCall x: Add(x.Destination); Value(x.Target); foreach (var v in x.Arguments) Value(v); break; case IrSetCrField x: Value(x.Left); Value(x.Right); break; case IrPhi x: Add(x.Destination); foreach (var pair in x.Sources.OrderBy(static p => p.Key, StringComparer.Ordinal)) { Add(pair.Key); Add(pair.Value); } break; case IrBranch x: Add(x.Condition); Add(x.TrueLabel); Add(x.FalseLabel); Add(x.ConditionRegister); break; case IrJump x: Add(x.TargetLabel); break; case IrIndirectJump x: Value(x.Target); break; case IrJumpTable x: Add(x.Selector); foreach (var item in x.Cases) Add(item.TargetLabel); break; case IrReturn x: if (x.Value is not null) Value(x.Value); break; case IrComment x: Add(x.Text); break; case IrTracePpc x: Add(x.Disassembly); Add(x.RawHex); break; case IrUndefined x: Add(x.Disassembly); Add(x.Reason); break; default: throw new InvalidDataException($"Instruction {instruction.GetType().Name} is not valid in canonical front-end SSA."); } } } return result; } private static void WriteInstruction(BinaryWriter writer, IReadOnlyDictionary ids, IrInstruction instruction) { void Id(string value) => WriteId(writer, ids, value); void Value(IrValue value) => WriteValue(writer, ids, value); void Values(IReadOnlyList values) { WriteVarUInt(writer, checked((uint)values.Count)); foreach (var value in values) Value(value); } switch (instruction) { case IrAssign x: writer.Write((byte)Op.Assign); Id(x.Destination); Value(x.Value); break; case IrBinary x: writer.Write((byte)Op.Binary); Id(x.Destination); Value(x.Left); Value(x.Right); Id(x.Op); break; case IrLoad x: writer.Write((byte)Op.Load); Id(x.Destination); WriteAddress(writer, ids, x.Address); WriteVarInt(writer, x.SizeBytes); break; case IrStore x: writer.Write((byte)Op.Store); WriteAddress(writer, ids, x.Address); Value(x.Source); WriteVarInt(writer, x.SizeBytes); break; case IrCall x: writer.Write((byte)Op.Call); Id(x.Destination); Id(x.Target); Values(x.Arguments); break; case IrIndirectCall x: writer.Write((byte)Op.IndirectCall); Id(x.Destination); Value(x.Target); Values(x.Arguments); break; case IrSetCrField x: writer.Write((byte)Op.SetCrField); WriteVarInt(writer, x.FieldIndex); Value(x.Left); Value(x.Right); writer.Write(x.IsUnsigned); break; case IrPhi x: writer.Write((byte)Op.Phi); Id(x.Destination); var sources = x.Sources.OrderBy(static pair => pair.Key, StringComparer.Ordinal).ToArray(); WriteVarUInt(writer, checked((uint)sources.Length)); foreach (var pair in sources) { Id(pair.Key); Id(pair.Value); } break; case IrBranch x: writer.Write((byte)Op.Branch); Id(x.Condition); Id(x.TrueLabel); Id(x.FalseLabel); Id(x.ConditionRegister); break; case IrJump x: writer.Write((byte)Op.Jump); Id(x.TargetLabel); break; case IrIndirectJump x: writer.Write((byte)Op.IndirectJump); Value(x.Target); break; case IrJumpTable x: writer.Write((byte)Op.JumpTable); Id(x.Selector); WriteVarUInt(writer, checked((uint)x.Cases.Count)); foreach (var item in x.Cases) { writer.Write(item.TargetAddress); Id(item.TargetLabel); } break; case IrReturn x: writer.Write((byte)Op.Return); writer.Write(x.Value is not null); if (x.Value is not null) Value(x.Value); break; case IrComment x: writer.Write((byte)Op.Comment); Id(x.Text); break; case IrTracePpc x: writer.Write((byte)Op.TracePpc); writer.Write(x.Address); Id(x.Disassembly); Id(x.RawHex); break; case IrUndefined x: writer.Write((byte)Op.Undefined); writer.Write(x.Address); writer.Write(x.RawInstruction); Id(x.Disassembly); writer.Write(x.Reason is not null); if (x.Reason is not null) Id(x.Reason); break; default: throw new InvalidDataException($"Instruction {instruction.GetType().Name} is not valid in canonical front-end SSA."); } } private static IrInstruction ReadInstruction(BinaryReader reader, IReadOnlyList strings) { string Id() => strings[CheckedIndex(ReadVarUInt(reader), strings.Count)]; IrValue Value() => ReadValue(reader, strings); IrValue[] Values() { var values = new IrValue[CheckedCount(ReadVarUInt(reader))]; for (var i = 0; i < values.Length; i++) values[i] = Value(); return values; } return (Op)reader.ReadByte() switch { Op.Assign => new IrAssign(Id(), Value()), Op.Binary => new IrBinary(Id(), Value(), Value(), Id()), Op.Load => new IrLoad(Id(), ReadAddress(reader, strings), ReadVarInt(reader)), Op.Store => new IrStore(ReadAddress(reader, strings), Value(), ReadVarInt(reader)), Op.Call => new IrCall(Id(), Id(), Values()), Op.IndirectCall => new IrIndirectCall(Id(), Value(), Values()), Op.SetCrField => new IrSetCrField(ReadVarInt(reader), Value(), Value(), reader.ReadBoolean()), Op.Phi => ReadPhi(reader, strings), Op.Branch => new IrBranch(Id(), Id(), Id(), Id()), Op.Jump => new IrJump(Id()), Op.IndirectJump => new IrIndirectJump(Value()), Op.JumpTable => ReadJumpTable(reader, strings), Op.Return => new IrReturn(reader.ReadBoolean() ? Value() : null), Op.Comment => new IrComment(Id()), Op.TracePpc => new IrTracePpc(reader.ReadUInt32(), Id(), Id()), Op.Undefined => ReadUndefined(reader, strings), var op => throw new InvalidDataException($"Unknown canonical SSA opcode {(byte)op}.") }; } private static IrPhi ReadPhi(BinaryReader reader, IReadOnlyList strings) { string Id() => strings[CheckedIndex(ReadVarUInt(reader), strings.Count)]; var destination = Id(); var count = CheckedCount(ReadVarUInt(reader)); var sources = new Dictionary(count, StringComparer.Ordinal); for (var i = 0; i < count; i++) sources.Add(Id(), Id()); return new IrPhi(destination, sources); } private static IrJumpTable ReadJumpTable(BinaryReader reader, IReadOnlyList strings) { string Id() => strings[CheckedIndex(ReadVarUInt(reader), strings.Count)]; var selector = Id(); var cases = new IrJumpTableCase[CheckedCount(ReadVarUInt(reader))]; for (var i = 0; i < cases.Length; i++) cases[i] = new IrJumpTableCase(reader.ReadUInt32(), Id()); return new IrJumpTable(selector, cases); } private static IrUndefined ReadUndefined(BinaryReader reader, IReadOnlyList strings) { string Id() => strings[CheckedIndex(ReadVarUInt(reader), strings.Count)]; var address = reader.ReadUInt32(); var raw = reader.ReadUInt32(); var disassembly = Id(); return new IrUndefined(address, raw, disassembly, reader.ReadBoolean() ? Id() : null); } private static void WriteValue(BinaryWriter writer, IReadOnlyDictionary ids, IrValue value) { if (value.Kind == "register") { writer.Write((byte)0); WriteId(writer, ids, value.RegisterName!); } else if (value.Kind == "const") { writer.Write((byte)1); writer.Write(value.Constant!.Value); } else { writer.Write((byte)2); WriteId(writer, ids, value.Kind); writer.Write(value.RegisterName is not null); if (value.RegisterName is not null) WriteId(writer, ids, value.RegisterName); writer.Write(value.Constant.HasValue); if (value.Constant.HasValue) writer.Write(value.Constant.Value); } } private static IrValue ReadValue(BinaryReader reader, IReadOnlyList strings) { string Id() => strings[CheckedIndex(ReadVarUInt(reader), strings.Count)]; return reader.ReadByte() switch { 0 => IrValue.Register(Id()), 1 => IrValue.Imm(reader.ReadInt64()), 2 => new IrValue(Id(), reader.ReadBoolean() ? Id() : null, reader.ReadBoolean() ? reader.ReadInt64() : null), var kind => throw new InvalidDataException($"Unknown canonical SSA value kind {kind}.") }; } private static void WriteAddress(BinaryWriter writer, IReadOnlyDictionary ids, IrAddress address) { WriteId(writer, ids, address.Base); WriteVarInt(writer, address.Offset); } private static IrAddress ReadAddress(BinaryReader reader, IReadOnlyList strings) => new(strings[CheckedIndex(ReadVarUInt(reader), strings.Count)], ReadVarInt(reader)); private static void WriteId(BinaryWriter writer, IReadOnlyDictionary ids, string value) => WriteVarUInt(writer, checked((uint)ids[value])); private static int CheckedCount(uint value) => value <= 16_000_000 ? checked((int)value) : throw new InvalidDataException("Canonical SSA count is unreasonable."); private static int CheckedIndex(uint value, int count) => value < count ? checked((int)value) : throw new InvalidDataException("Canonical SSA string ID is out of range."); private static void WriteVarInt(BinaryWriter writer, int value) => WriteVarUInt(writer, unchecked((uint)((value << 1) ^ (value >> 31)))); private static int ReadVarInt(BinaryReader reader) { var value = ReadVarUInt(reader); return unchecked((int)((value >> 1) ^ (uint)-(int)(value & 1))); } private static void WriteVarUInt(BinaryWriter writer, uint value) { while (value >= 0x80) { writer.Write((byte)(value | 0x80)); value >>= 7; } writer.Write((byte)value); } private static uint ReadVarUInt(BinaryReader reader) { uint value = 0; for (var shift = 0; shift <= 28; shift += 7) { var next = reader.ReadByte(); value |= (uint)(next & 0x7F) << shift; if ((next & 0x80) == 0) return value; } throw new InvalidDataException("Canonical SSA varint is too long."); } }