Bird Programming Language: Part 1

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Anonymus.x86
{
	public abstract class x86DataPosition
	{
		public x86Architecture Arch;
		public int Size;

		public x86DataPosition(x86Architecture Arch, int Size)
		{
			this.Arch = Arch;
			this.Size = Size;
		}

		public virtual x86DataPosition Extract()
		{
			return this;
		}

		public virtual x86RegList GetRegs()
		{
			return new x86RegList(0);
		}

		public abstract bool IsEqual(x86DataPosition Pos, bool Size = true);
		public abstract x86DataPosition Copy(int Size = -1);
	}

	public class x86SSERegPosition : x86DataPosition
	{
		public int Index;

		public x86SSERegPosition(x86Architecture Arch, int Index)
			: base(Arch, -1)
		{
			this.Index = Index;
		}

		public override string ToString()
		{
			return "xmm" + Index.ToString();
		}

		public override bool IsEqual(x86DataPosition Pos, bool Size = true)
		{
			var SSEReg = Pos as x86SSERegPosition;
			return SSEReg != null && SSEReg.Index == Index;
		}

		public override x86DataPosition Copy(int Size = -1)
		{
			return new x86SSERegPosition(Arch, Index);
		}
	}

	public class x86FPRegPosition : x86DataPosition
	{
		public int Index;

		public x86FPRegPosition(x86Architecture Arch, int Index)
			: base(Arch, -1)
		{
			this.Index = Index;
		}

		public override string ToString()
		{
			return "st" + Index.ToString();
		}

		public override bool IsEqual(x86DataPosition Pos, bool Size = true)
		{
			var FPReg = Pos as x86FPRegPosition;
			return FPReg != null && FPReg.Index == Index;
		}

		public override x86DataPosition Copy(int Size = -1)
		{
			return new x86FPRegPosition(Arch, Index);
		}
	}

	public abstract class x86PostCalcedPosition : x86DataPosition
	{
		public ExpressionNode AssignNode;

		public abstract x86DataPosition Position { get; }

		public x86PostCalcedPosition(x86Architecture Arch, ExpressionNode AssignNode, int Size)
			: base(Arch, Size)
		{
			this.AssignNode = AssignNode;
		}

		public override bool IsEqual(x86DataPosition Pos, bool Size = true)
		{
			var VarPos = Position as x86DataPosition;
			return VarPos.IsEqual(Pos, Size);
		}

		public override string ToString()
		{
			throw new Exception("ERROR");
		}
	}

	public class x86AssignVarPos : x86PostCalcedPosition
	{
		public Variable AssignVar;
		
		public x86AssignVarPos(x86Architecture Arch, Variable AssignVar, ExpressionNode AssignNode)
			: base(Arch, AssignNode, AssignVar.Type.Size)
		{
			this.AssignVar = AssignVar;
		}

		public override x86DataPosition  Position
		{
			get { return AssignVar.ArchData as x86DataPosition; }
		}

		public override x86DataPosition Copy(int Size = -1)
		{
			if (Size == -1) Size = this.Size;
			return new x86AssignVarPos(Arch, AssignVar, AssignNode);
		}
	}

	public class x86LinkedNodePosition : x86PostCalcedPosition
	{
		public LinkedExprNode LNode;

		public x86LinkedNodePosition(x86Architecture Arch, LinkedExprNode LNode)
			: base(Arch, LNode.Node, LNode.Node.Type.Size)
		{
			this.LNode = LNode;
		}

		public override x86DataPosition  Position
		{
			get
			{
				var Data = LNode.ArchData as x86LinkedNodeData;
				return Data.Position;
			}
		}

		public override x86DataPosition Copy(int Size = -1)
		{
			if (Size == -1) Size = this.Size;
			return new x86LinkedNodePosition(Arch, LNode);
		}
	}

	public abstract class x86SplitablePosition : x86DataPosition
	{
		public int Offset;

		public virtual int AllOffset
		{
			get { return Offset; }
		}

		public abstract x86DataPosition GetPart(int Offset, int Size);

		public x86SplitablePosition(x86Architecture Arch, int Size, int Offset)
			: base(Arch, Size)
		{
			this.Offset = Offset;
		}

		public x86DataPosition[] Split(int Size)
		{
			var Count = (this.Size - 1) / Size + 1;
			var Ret = new x86DataPosition[Count];

			for (var i = 0; i < Count; i++)
			{
				var Offset = i * Size;

				if (Offset + Size > this.Size)
					Ret[i] = GetPart(Offset, this.Size - Offset);
				else Ret[i] = GetPart(Offset, Size);
			}

			return Ret;
		}
	}

	public class x86ConstPosition : x86SplitablePosition
	{
		public ConstData Data;

		public ConstDataType Type
		{
			get { return Data.Type; }
		}

		public ulong Unsigned
		{
			get { return Data.GetUnsigned(Offset, Size); }
		}

		public long Signed
		{
			get { return Data.GetSigned(Offset, Size); }
		}

		public double Double
		{
			get { return Data.DoubleData; }
		}

		public x86ConstPosition(x86Architecture Arch, int Size, ConstData Data, int Offset)
			: base(Arch, Size, Offset)
		{
			this.Data = Data;
		}

		public override x86DataPosition GetPart(int Offset, int Size)
		{
			return new x86ConstPosition(Arch, Size, Data, this.Offset + Offset);
		}

		public override string ToString()
		{
			if (Data.Type == ConstDataType.Signed)
				return Signed.ToString();
			else return Unsigned.ToString();
		}

		public override bool IsEqual(x86DataPosition Pos, bool Size = true)
		{
			var ConstPos = Pos as x86ConstPosition;
			return ConstPos != null && ConstPos.Offset == Offset &&
				   (!Size || ConstPos.Size == this.Size) && ConstPos.Data.IsEqual(Data);
		}

		public override x86DataPosition Copy(int Size = -1)
		{
			if (Size == -1) Size = this.Size;
			return new x86ConstPosition(Arch, Size, Data, Offset);
		}
	}

	public class x86RegPosition : x86DataPosition
	{
		public int Index;
		public bool HighBytes;

		public x86RegPosition(x86Architecture Arch, int Size, int Index, bool HighBytes = false)
			: base(Arch, Size)
		{
			this.Index = Index;
			this.HighBytes = HighBytes;
		}

		public override string ToString()
		{
			return x86Architecture.RegStr(Index, Size, HighBytes);
		}

		public override bool IsEqual(x86DataPosition Pos, bool Size = true)
		{
			var RegPos = Pos as x86RegPosition;
			return RegPos != null && RegPos.Index == Index &&
				(!Size || RegPos.Size == this.Size);
		}

		public override x86DataPosition Copy(int Size = -1)
		{
			if (Size == -1) Size = this.Size;
			return new x86RegPosition(Arch, Size, Index, HighBytes);
		}

		public override x86RegList GetRegs()
		{
			var Ret = new x86RegList(Arch.RegCount);
			if (HighBytes) Ret.SetUsed(Index, Size * 2);
			else Ret.SetUsed(Index, Size);
			return Ret;
		} 
	}

	public class x86MemPosition : x86SplitablePosition
	{
		public bool Ref;
		public string Name;
		public int Align;

		public x86MemPosition(x86Architecture Arch, int Size, string Name,
			int Offset, bool Ref = true, int Align = 1) : base(Arch, Size, Offset)
		{
			this.Name = Name;
			this.Ref = Ref;
			this.Align = Align;
		}

		public override string ToString()
		{
			var O = AllOffset;

			String Str;
			if (O == 0) Str = Name;
			else Str = Name + " + " + O.ToString();

			if (Ref)
			{
				var T = x86Architecture.GetTypeString(Size);
				return T + "[" + Str + "]";
			}

			return Str;
		}

		public override x86DataPosition GetPart(int Offset, int Size)
		{
			return new x86MemPosition(Arch, Size, Name, this.Offset + Offset);
		}

		public override bool IsEqual(x86DataPosition Pos, bool Size = true)
		{
			var MemPos = Pos as x86MemPosition;
			return MemPos != null && MemPos.Offset == Offset &&
				   (!Size || MemPos.Size == this.Size) && MemPos.Name == Name;
		}

		public override x86DataPosition Copy(int Size = -1)
		{
			if (Size == -1) Size = this.Size;
			return new x86MemPosition(Arch, Size, Name, Offset, Ref);
		}
	}

	public class x86IndexPosition : x86MemPosition
	{
		public x86Compiler Compiler;
		public x86DataPosition Ptr;
		public x86DataPosition TmpReg;
		public string str_Offset;

		public x86IndexPosition(x86Compiler Compiler, int Size, int Offset,
			string str_Offset, x86DataPosition Ptr, x86DataPosition TmpReg)
			: base(Compiler.Arch, Size, null, Offset)
		{
			this.Ptr = Ptr;
			this.TmpReg = TmpReg;
			this.Compiler = Compiler;
			this.str_Offset = str_Offset;
		}

		public override x86DataPosition Extract()
		{
			var P = Ptr;
			if (P is x86MemPosition)
			{
				Compiler.Append("\tmov " + TmpReg + ", " + P + "\n");
				P = TmpReg;
			}

			if (str_Offset == null) Name = P.ToString();
			else Name = P.ToString() + " + " + str_Offset;
			return new x86MemPosition(Arch, Size, Name, Offset);
		}

		public override string ToString()
		{
			var P = Ptr;
			if (P is x86MemPosition)
			{
				Compiler.Append("\tmov " + TmpReg + ", " + P + "\n");
				P = TmpReg;
			}

			if (str_Offset == null) Name = P.ToString();
			else Name = P.ToString() + " + " + str_Offset;
			return base.ToString();
		}

		public override x86DataPosition Copy(int Size = -1)
		{
			return new x86IndexPosition(Compiler, Size, Offset, str_Offset, Ptr, TmpReg);
		}

		public override x86DataPosition GetPart(int Offset, int Size)
		{
			return new x86IndexPosition(Compiler, Size, this.Offset + Offset, str_Offset, Ptr, TmpReg);
		}

		public override bool IsEqual(x86DataPosition Pos, bool Size = true)
		{
			var IPos = Pos as x86IndexPosition;
			if (IPos == null) return false;
			return base.IsEqual(Pos, Size) && Ptr.IsEqual(IPos.Ptr) &&
				TmpReg.IsEqual(IPos.TmpReg) && str_Offset == IPos.str_Offset;
		}
	}

	public class x86StackPosition : x86MemPosition
	{
		public x86FuncScopeNode FuncScope;
		public bool FuncParam;

		public override int AllOffset
		{
			get { return base.AllOffset + StackOffset; }
		}

		public int StackOffset
		{
			get
			{
                var Data = FuncScope.ArchData as x86FuncContainerData;
                var Ret = Data.FuncCallPushed;
                if (FuncParam) Ret += Data.PushedBytes + Data.StackAlloc + 4;
				return Ret;
			}
		}

		public x86StackPosition(x86FuncScopeNode FuncScope, int Size, int Offset, bool FuncParam)
			: base(FuncScope.Arch, Size, "esp", Offset)
		{
			this.FuncScope = FuncScope;
			this.FuncParam = FuncParam;
		}

		public override x86DataPosition GetPart(int Offset, int Size)
		{
			return new x86StackPosition(FuncScope, Size, this.Offset + Offset, FuncParam);
		}

		public override x86DataPosition Copy(int Size = -1)
		{
			if (Size == -1) Size = this.Size;
			return new x86StackPosition(FuncScope, Size, Offset, FuncParam);
		}

		public override bool IsEqual(x86DataPosition Pos, bool Size = true)
		{
			var StackPos = Pos as x86StackPosition;
			if (StackPos == null) return false;

			return StackPos.FuncParam == FuncParam && base.IsEqual(Pos, Size);
		}
	}

	public class x86MultiPosition : x86SplitablePosition
	{
		public x86DataPosition[] Positions;

		public x86MultiPosition(x86Architecture Arch, int Size, x86DataPosition[] Positions)
			: base(Arch, Size, 0)
		{
			this.Positions = Positions;
		}

		public override x86DataPosition Copy(int Size = -1)
		{
			if (Size < Positions[0].Size)
				return Positions[0].Copy(Size);

			var Count = Size / Positions[0].Size;
			var Arr = new x86DataPosition[Count];
			for (var i = 0; i < Count; i++)
				Arr[i] = Positions[i].Copy();

			return new x86MultiPosition(Arch, Size, Arr);
		}

		public override x86DataPosition GetPart(int Offset, int Size)
		{
			if (Offset % Size != 0) throw new Exception("ERROR");

			var Ret = Positions[Offset / Size];
			if (Ret.Size != Size) throw new Exception("ERROR");
			return Ret;
		}

		public override bool IsEqual(x86DataPosition Pos, bool Size = true)
		{
			var MultiPos = Pos as x86MultiPosition;
			if (MultiPos == null) return false;

			var MinLen = Positions.Length;
			if (MinLen != MultiPos.Positions.Length)
			{
				if (!Size)
				{
					if (MinLen > MultiPos.Positions.Length)
						MinLen = MultiPos.Positions.Length;
				}
				else
				{
					return false;
				}
			}

			for (var i = 0; i < MinLen; i++)
				if (!Positions[i].IsEqual(MultiPos.Positions[i]))
					return false;

			return true;
		}

		public override string ToString()
		{
			throw new Exception("ERROR");
		}

		public bool HasMemPart()
		{
			foreach (var e in Positions)
				if (e is x86MemPosition) return true;

			return false;
		}

		public override x86RegList GetRegs()
		{
			var Ret = new x86RegList(Arch.RegCount);
			foreach (var Pos in Positions)
			{
				if (Pos is x86RegPosition)
				{
					var RPos = Pos as x86RegPosition;
					if (RPos.HighBytes) Ret.SetUsed(RPos.Index, RPos.Size * 2);
					else Ret.SetUsed(RPos.Index, RPos.Size);
				}
				else if (Pos is x86MultiPosition)
				{
					var MPos = Pos as x86MultiPosition;
					var Regs = MPos.GetRegs();
					if (Regs != null) Ret.SetUsed(Regs);
				}
			}

			return Ret;
		}
	}

	public class x86DataAllocator
	{
		public IdContainer Container;
		public CompilerState State;
		public x86Architecture Arch;
		public x86FuncScopeNode Func;

		public x86RegList UsedRegs;
		public x86SSERegList SSERegs;
		public int StackAlloc = 0;

		public x86DataAllocator(IdContainer Container, bool AllocRegsLists = true)
		{
			this.Container = Container;
			this.State = Container.State;
			this.Arch = State.Arch as x86Architecture;
			this.Func = Container.FuncScope as x86FuncScopeNode;

			if (AllocRegsLists)
			{
				UsedRegs = new x86RegList(Arch.RegCount);
				SSERegs = new x86SSERegList(Arch.RegSize * 2);
			}
		}

        public void Set(x86DataAllocator Allocator)
        {
            UsedRegs.Set(Allocator.UsedRegs);
            SSERegs.Set(Allocator.SSERegs);
            StackAlloc = Allocator.StackAlloc;
        }

        public void SetUsed(x86DataPosition Pos)
        {
            if (Pos is x86RegPosition)
            {
                var RPos = Pos as x86RegPosition;
                if (RPos.Size == 1 && RPos.HighBytes)
                    UsedRegs.SetUsed(RPos.Index, 2);
                else UsedRegs.SetUsed(RPos.Index, RPos.Size);
            }
            else if (Pos is x86SSERegPosition)
            {
                var SSEPos = Pos as x86SSERegPosition;
                SSERegs.SetUsed(SSEPos.Index);
            }
            else if (Pos is x86MemPosition)
            {
                var MPos = Pos as x86MemPosition;
                var New = MPos.Offset + MPos.Size;
                if (StackAlloc < New) StackAlloc = New;
            }
			else if (Pos is x86MultiPosition)
			{
				var MPos = Pos as x86MultiPosition;
				foreach (var e in MPos.Positions)
					SetUsed(e);
			}
			else
			{
				throw new Exception("ERROR");
			}
        }

        public bool IsFree(x86DataPosition Pos)
        {
            if (Pos is x86RegPosition)
            {
                var RPos = Pos as x86RegPosition;
                if (RPos.Size == 1 && RPos.HighBytes)
                    return UsedRegs[RPos.Index] < 2;
                else return UsedRegs[RPos.Index] == 0;
            }
            else if (Pos is x86SSERegPosition)
            {
                var SSEPos = Pos as x86SSERegPosition;
                return !SSERegs[SSEPos.Index];
            }
            else if (Pos is x86MemPosition)
            {
                var MPos = Pos as x86MemPosition;
                return StackAlloc <= MPos.Offset;
			}
			else if (Pos is x86MultiPosition)
			{
				var MPos = Pos as x86MultiPosition;
				foreach (var e in MPos.Positions)
					if (!IsFree(e)) return false;

				return true;
			}
            else
            {
                throw new Exception("ERROR");
            }
        }

        public void SetUsed(x86DataAllocator Allocator)
        {
            UsedRegs.SetUsed(Allocator.UsedRegs);
            SSERegs.SetUsed(Allocator.SSERegs);
            if (StackAlloc < Allocator.StackAlloc)
                StackAlloc = Allocator.StackAlloc;
        }

		public void Reset()
		{
			StackAlloc = 0;
			for (var i = 0; i < UsedRegs.Size; i++)
				UsedRegs[i] = 0;
			
			for (var i = 0; i < SSERegs.Size; i++)
				SSERegs[i] = false;
		}

		public int GetUsedRegSize(int Index)
		{
			var Data = Func.ArchData as x86FuncContainerData;
			var UsedByParams = Data.UsedByParams;

			var Ret = UsedRegs[Index];
			if (UsedByParams != null && UsedByParams[Index] > Ret)
				Ret = UsedByParams[Index];

			return Ret;
		}

		public bool RegAvaiable()
		{
			for (var i = 0; i < UsedRegs.Size; i++)
				if (GetUsedRegSize(i) == 0) return true;

			return false;
		}

		public bool SSERegAvaiable()
		{
			for (var i = 0; i < UsedRegs.Size; i++)
				if (!SSERegs[i]) return true;

			return false;
		}

		public static int[] RegAllocSequence = new int[] { 0, 2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
		public static bool[] HasOneByteReg = new bool[] { true, true, true, true };

        public x86DataPosition Alloc(Type T, x86RegList CantBe = null)
        {
            return Alloc(T.Size, Arch.GetAlign(T), x86Architecture.TypePos(T), CantBe);
        }

		public x86DataPosition Alloc(int Size, int Align, x86DataCalcPos DataCalcPos = x86DataCalcPos.GRegMem,
			x86RegList CantBe = null)
		{
			if (Size % 16 == 0 && DataCalcPos.HasFlag(x86DataCalcPos.SSEReg) && SSERegAvaiable())
			{
				if (Size == 16)
				{
					for (var i = 0; i < SSERegs.Size; i++)
						if (!SSERegs[i]) return new x86SSERegPosition(Arch, i);
				}

				return AllocMultiPos(Size, Align, DataCalcPos, CantBe, 16);
			}
			
			if (Size > Arch.RegSize && DataCalcPos.HasFlag(x86DataCalcPos.GeneralReg) && RegAvaiable())
				return AllocMultiPos(Size, Align, DataCalcPos, CantBe, Arch.RegSize);

			if (DataCalcPos.HasFlag(x86DataCalcPos.GeneralReg) && Size <= Arch.RegSize)
			{
				if (Size == 1)
				{
					foreach (var i in RegAllocSequence)
						if (i < UsedRegs.Size && Arch.RegExists(i, 1, true) &&
							GetUsedRegSize(i) == 1 && (CantBe == null || CantBe[i] < 2))
						{
							UsedRegs.SetUsed(i, 2);
							return new x86RegPosition(Arch, 1, i, true);
						}
				}

				foreach (var i in RegAllocSequence)
					if (i < UsedRegs.Size && Arch.RegExists(i, Size, false) &&
						GetUsedRegSize(i) == 0 && (CantBe == null || CantBe[i] == 0))
					{
						UsedRegs.SetUsed(i, Size);
						return new x86RegPosition(Arch, Size, i);
					}
			}

			if (DataCalcPos.HasFlag(x86DataCalcPos.Memory))
			{
				var P = Helper.AdjustVarPos(StackAlloc, Align);
				StackAlloc = P + Size;

				return new x86StackPosition(Func, Size, P, false);
			}

			return null;
		}

		private x86DataPosition AllocMultiPos(int Size, int Align, x86DataCalcPos DataCalcPos, x86RegList CantBe, int PartSize)
		{
			var Count = Size / PartSize;
			var Positions = new x86DataPosition[Count];

			for (var i = 0; i < Count; i++)
				Positions[i] = Alloc(Arch.RegSize, Align, DataCalcPos, CantBe);

			return new x86MultiPosition(Arch, Size, Positions);
		}

		public x86DataAllocator Copy()
		{
			var Ret = new x86DataAllocator(Container, false);
			Ret.UsedRegs = UsedRegs.Copy();
			Ret.SSERegs = SSERegs.Copy();
			Ret.StackAlloc = StackAlloc;
			return Ret;
		}
	}

	public class x86SSERegList
	{
		public bool[] UsedRegs;

		public x86SSERegList(int Size)
		{
			UsedRegs = new bool[Size];
		}

		public int Size
		{
			get { return UsedRegs.Length; }
		}

		public bool this[int Pos]
		{
			get { return UsedRegs[Pos]; }
			set { UsedRegs[Pos] = value; }
		}

        public void SetUsed(int Index)
		{
			UsedRegs[Index] = true;
		}

        public void SetUsed(x86SSERegList Lst)
        {
            for (var i = 0; i < Lst.Size; i++)
                if (Lst[i]) UsedRegs[i] = true;
        }

        public x86SSERegList Union(x86SSERegList Other)
		{
			var s = Size;
			if (s < Other.Size) s = Other.Size;
			var Ret = new x86SSERegList(s);

			for (var i = 0; i < s; i++)
				if (i < Size && this[i]) Ret[i] = true;
				else if (i < Other.Size && Other[i]) Ret[i] = true;

			return Ret;
		}

		public x86SSERegList Copy()
		{
			var Ret = new x86SSERegList(Size);
			for (var i = 0; i < Size; i++)
				Ret[i] = this[i];

			return Ret;
		}

		public bool Contains(int Index)
		{
			return this[Index];
		}

        public void Set(x86SSERegList List)
        {
            if (List.Size != Size)
                throw new Exception("ERROR");

            for (var i = 0; i < Size; i++)
                UsedRegs[i] = List[i];
        }
	}

	public class x86RegList
	{
		public int[] UsedRegs;

		public x86RegList(int Size)
		{
			UsedRegs = new int[Size];
		}

		public int Size
		{
			get { return UsedRegs.Length; }
		}

		public int this[int Pos]
		{
			get { return UsedRegs[Pos]; }
			set { UsedRegs[Pos] = value; }
		}

        public void SetUsed(int Index, int Size)
		{
			if (UsedRegs[Index] < Size)
				UsedRegs[Index] = Size;
		}

        public void SetUsed(x86RegList Lst)
		{
			for (var i = 0; i < Lst.Size; i++)
                SetUsed(i, Lst[i]);
		}

		public x86RegList Union(x86RegList Other)
		{
			var s = Size;
			if (s < Other.Size) s = Other.Size;
			var Ret = new x86RegList(s);

			for (var i = 0; i < s; i++)
			{
				if (i < Size && i < Other.Size)
					Ret[i] = this[i] > Other[i] ? this[i] : Other[i];
				else if (i < Size) Ret[i] = this[i];
				else if (i < Other.Size) Ret[i] = Other[i];
				else throw new Exception("ERROR");
			}

			return Ret;
		}

		public x86RegList Copy()
		{
			var Ret = new x86RegList(Size);
			for (var i = 0; i < Size; i++)
				Ret[i] = this[i];

			return Ret;
		}

		public bool Contains(int Index)
		{
			return this[Index] > 0;
		}

        public void Set(x86RegList List)
        {
            if (List.Size != Size)
                throw new Exception("ERROR");

            for (var i = 0; i < Size; i++)
                UsedRegs[i] = List[i];
        }
	}

}