Add a new JIT compiler for CPU code (#693)

* Start of the ARMeilleure project

* Refactoring around the old IRAdapter, now renamed to PreAllocator

* Optimize the LowestBitSet method

* Add CLZ support and fix CLS implementation

* Add missing Equals and GetHashCode overrides on some structs, misc small tweaks

* Implement the ByteSwap IR instruction, and some refactoring on the assembler

* Implement the DivideUI IR instruction and fix 64-bits IDIV

* Correct constant operand type on CSINC

* Move division instructions implementation to InstEmitDiv

* Fix destination type for the ConditionalSelect IR instruction

* Implement UMULH and SMULH, with new IR instructions

* Fix some issues with shift instructions

* Fix constant types for BFM instructions

* Fix up new tests using the new V128 struct

* Update tests

* Move DIV tests to a separate file

* Add support for calls, and some instructions that depends on them

* Start adding support for SIMD & FP types, along with some of the related ARM instructions

* Fix some typos and the divide instruction with FP operands

* Fix wrong method call on Clz_V

* Implement ARM FP & SIMD move instructions, Saddlv_V, and misc. fixes

* Implement SIMD logical instructions and more misc. fixes

* Fix PSRAD x86 instruction encoding, TRN, UABD and UABDL implementations

* Implement float conversion instruction, merge in LDj3SNuD fixes, and some other misc. fixes

* Implement SIMD shift instruction and fix Dup_V

* Add SCVTF and UCVTF (vector, fixed-point) variants to the opcode table

* Fix check with tolerance on tester

* Implement FP & SIMD comparison instructions, and some fixes

* Update FCVT (Scalar) encoding on the table to support the Half-float variants

* Support passing V128 structs, some cleanup on the register allocator, merge LDj3SNuD fixes

* Use old memory access methods, made a start on SIMD memory insts support, some fixes

* Fix float constant passed to functions, save and restore non-volatile XMM registers, other fixes

* Fix arguments count with struct return values, other fixes

* More instructions

* Misc. fixes and integrate LDj3SNuD fixes

* Update tests

* Add a faster linear scan allocator, unwinding support on windows, and other changes

* Update Ryujinx.HLE

* Update Ryujinx.Graphics

* Fix V128 return pointer passing, RCX is clobbered

* Update Ryujinx.Tests

* Update ITimeZoneService

* Stop using GetFunctionPointer as that can't be called from native code, misc. fixes and tweaks

* Use generic GetFunctionPointerForDelegate method and other tweaks

* Some refactoring on the code generator, assert on invalid operations and use a separate enum for intrinsics

* Remove some unused code on the assembler

* Fix REX.W prefix regression on float conversion instructions, add some sort of profiler

* Add hardware capability detection

* Fix regression on Sha1h and revert Fcm** changes

* Add SSE2-only paths on vector extract and insert, some refactoring on the pre-allocator

* Fix silly mistake introduced on last commit on CpuId

* Generate inline stack probes when the stack allocation is too large

* Initial support for the System-V ABI

* Support multiple destination operands

* Fix SSE2 VectorInsert8 path, and other fixes

* Change placement of XMM callee save and restore code to match other compilers

* Rename Dest to Destination and Inst to Instruction

* Fix a regression related to calls and the V128 type

* Add an extra space on comments to match code style

* Some refactoring

* Fix vector insert FP32 SSE2 path

* Port over the ARM32 instructions

* Avoid memory protection races on JIT Cache

* Another fix on VectorInsert FP32 (thanks to LDj3SNuD

* Float operands don't need to use the same register when VEX is supported

* Add a new register allocator, higher quality code for hot code (tier up), and other tweaks

* Some nits, small improvements on the pre allocator

* CpuThreadState is gone

* Allow changing CPU emulators with a config entry

* Add runtime identifiers on the ARMeilleure project

* Allow switching between CPUs through a config entry (pt. 2)

* Change win10-x64 to win-x64 on projects

* Update the Ryujinx project to use ARMeilleure

* Ensure that the selected register is valid on the hybrid allocator

* Allow exiting on returns to 0 (should fix test regression)

* Remove register assignments for most used variables on the hybrid allocator

* Do not use fixed registers as spill temp

* Add missing namespace and remove unneeded using

* Address PR feedback

* Fix types, etc

* Enable AssumeStrictAbiCompliance by default

* Ensure that Spill and Fill don't load or store any more than necessary

9 files changed, 2173 insertions, 0 deletions

diff --git a/ARMeilleure/CodeGen/RegisterAllocators/AllocationResult.cs b/ARMeilleure/CodeGen/RegisterAllocators/AllocationResult.cs
new file mode 100644
index 00000000..94ac6991
--- /dev/null
+++ b/ARMeilleure/CodeGen/RegisterAllocators/AllocationResult.cs
@@ -0,0 +1,19 @@
+namespace ARMeilleure.CodeGen.RegisterAllocators
+{
+    struct AllocationResult
+    {
+        public int IntUsedRegisters { get; }
+        public int VecUsedRegisters { get; }
+        public int SpillRegionSize  { get; }
+
+        public AllocationResult(
+            int intUsedRegisters,
+            int vecUsedRegisters,
+            int spillRegionSize)
+        {
+            IntUsedRegisters = intUsedRegisters;
+            VecUsedRegisters = vecUsedRegisters;
+            SpillRegionSize  = spillRegionSize;
+        }
+    }
+}
\ No newline at end of file
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/CopyResolver.cs b/ARMeilleure/CodeGen/RegisterAllocators/CopyResolver.cs
new file mode 100644
index 00000000..65901e80
--- /dev/null
+++ b/ARMeilleure/CodeGen/RegisterAllocators/CopyResolver.cs
@@ -0,0 +1,246 @@
+using ARMeilleure.IntermediateRepresentation;
+using System;
+using System.Collections.Generic;
+
+namespace ARMeilleure.CodeGen.RegisterAllocators
+{
+    class CopyResolver
+    {
+        private class ParallelCopy
+        {
+            private struct Copy
+            {
+                public Register Dest   { get; }
+                public Register Source { get; }
+
+                public OperandType Type { get; }
+
+                public Copy(Register dest, Register source, OperandType type)
+                {
+                    Dest   = dest;
+                    Source = source;
+                    Type   = type;
+                }
+            }
+
+            private List<Copy> _copies;
+
+            public int Count => _copies.Count;
+
+            public ParallelCopy()
+            {
+                _copies = new List<Copy>();
+            }
+
+            public void AddCopy(Register dest, Register source, OperandType type)
+            {
+                _copies.Add(new Copy(dest, source, type));
+            }
+
+            public void Sequence(List<Operation> sequence)
+            {
+                Dictionary<Register, Register> locations = new Dictionary<Register, Register>();
+                Dictionary<Register, Register> sources   = new Dictionary<Register, Register>();
+
+                Dictionary<Register, OperandType> types = new Dictionary<Register, OperandType>();
+
+                Queue<Register> pendingQueue = new Queue<Register>();
+                Queue<Register> readyQueue   = new Queue<Register>();
+
+                foreach (Copy copy in _copies)
+                {
+                    locations[copy.Source] = copy.Source;
+                    sources[copy.Dest]     = copy.Source;
+                    types[copy.Dest]       = copy.Type;
+
+                    pendingQueue.Enqueue(copy.Dest);
+                }
+
+                foreach (Copy copy in _copies)
+                {
+                    // If the destination is not used anywhere, we can assign it immediately.
+                    if (!locations.ContainsKey(copy.Dest))
+                    {
+                        readyQueue.Enqueue(copy.Dest);
+                    }
+                }
+
+                while (pendingQueue.TryDequeue(out Register current))
+                {
+                    Register copyDest;
+                    Register origSource;
+                    Register copySource;
+
+                    while (readyQueue.TryDequeue(out copyDest))
+                    {
+                        origSource = sources[copyDest];
+                        copySource = locations[origSource];
+
+                        OperandType type = types[copyDest];
+
+                        EmitCopy(sequence, GetRegister(copyDest, type), GetRegister(copySource, type));
+
+                        locations[origSource] = copyDest;
+
+                        if (origSource == copySource && sources.ContainsKey(origSource))
+                        {
+                            readyQueue.Enqueue(origSource);
+                        }
+                    }
+
+                    copyDest   = current;
+                    origSource = sources[copyDest];
+                    copySource = locations[origSource];
+
+                    if (copyDest != copySource)
+                    {
+                        OperandType type = types[copyDest];
+
+                        type = type.IsInteger() ? OperandType.I64 : OperandType.V128;
+
+                        EmitXorSwap(sequence, GetRegister(copyDest, type), GetRegister(copySource, type));
+
+                        locations[origSource] = copyDest;
+
+                        Register swapOther = copySource;
+
+                        if (copyDest != locations[sources[copySource]])
+                        {
+                            // Find the other swap destination register.
+                            // To do that, we search all the pending registers, and pick
+                            // the one where the copy source register is equal to the
+                            // current destination register being processed (copyDest).
+                            foreach (Register pending in pendingQueue)
+                            {
+                                // Is this a copy of pending <- copyDest?
+                                if (copyDest == locations[sources[pending]])
+                                {
+                                    swapOther = pending;
+
+                                    break;
+                                }
+                            }
+                        }
+
+                        // The value that was previously at "copyDest" now lives on
+                        // "copySource" thanks to the swap, now we need to update the
+                        // location for the next copy that is supposed to copy the value
+                        // that used to live on "copyDest".
+                        locations[sources[swapOther]] = copySource;
+                    }
+                }
+            }
+
+            private static void EmitCopy(List<Operation> sequence, Operand x, Operand y)
+            {
+                sequence.Add(new Operation(Instruction.Copy, x, y));
+            }
+
+            private static void EmitXorSwap(List<Operation> sequence, Operand x, Operand y)
+            {
+                sequence.Add(new Operation(Instruction.BitwiseExclusiveOr, x, x, y));
+                sequence.Add(new Operation(Instruction.BitwiseExclusiveOr, y, y, x));
+                sequence.Add(new Operation(Instruction.BitwiseExclusiveOr, x, x, y));
+            }
+        }
+
+        private Queue<Operation> _fillQueue  = new Queue<Operation>();
+        private Queue<Operation> _spillQueue = new Queue<Operation>();
+
+        private ParallelCopy _parallelCopy;
+
+        public bool HasCopy { get; private set; }
+
+        public CopyResolver()
+        {
+            _fillQueue  = new Queue<Operation>();
+            _spillQueue = new Queue<Operation>();
+
+            _parallelCopy = new ParallelCopy();
+        }
+
+        public void AddSplit(LiveInterval left, LiveInterval right)
+        {
+            if (left.Local != right.Local)
+            {
+                throw new ArgumentException("Intervals of different variables are not allowed.");
+            }
+
+            OperandType type = left.Local.Type;
+
+            if (left.IsSpilled && !right.IsSpilled)
+            {
+                // Move from the stack to a register.
+                AddSplitFill(left, right, type);
+            }
+            else if (!left.IsSpilled && right.IsSpilled)
+            {
+                // Move from a register to the stack.
+                AddSplitSpill(left, right, type);
+            }
+            else if (!left.IsSpilled && !right.IsSpilled && left.Register != right.Register)
+            {
+                // Move from one register to another.
+                AddSplitCopy(left, right, type);
+            }
+            else if (left.SpillOffset != right.SpillOffset)
+            {
+                // This would be the stack-to-stack move case, but this is not supported.
+                throw new ArgumentException("Both intervals were spilled.");
+            }
+        }
+
+        private void AddSplitFill(LiveInterval left, LiveInterval right, OperandType type)
+        {
+            Operand register = GetRegister(right.Register, type);
+
+            Operand offset = new Operand(left.SpillOffset);
+
+            _fillQueue.Enqueue(new Operation(Instruction.Fill, register, offset));
+
+            HasCopy = true;
+        }
+
+        private void AddSplitSpill(LiveInterval left, LiveInterval right, OperandType type)
+        {
+            Operand offset = new Operand(right.SpillOffset);
+
+            Operand register = GetRegister(left.Register, type);
+
+            _spillQueue.Enqueue(new Operation(Instruction.Spill, null, offset, register));
+
+            HasCopy = true;
+        }
+
+        private void AddSplitCopy(LiveInterval left, LiveInterval right, OperandType type)
+        {
+            _parallelCopy.AddCopy(right.Register, left.Register, type);
+
+            HasCopy = true;
+        }
+
+        public Operation[] Sequence()
+        {
+            List<Operation> sequence = new List<Operation>();
+
+            while (_spillQueue.TryDequeue(out Operation spillOp))
+            {
+                sequence.Add(spillOp);
+            }
+
+            _parallelCopy.Sequence(sequence);
+
+            while (_fillQueue.TryDequeue(out Operation fillOp))
+            {
+                sequence.Add(fillOp);
+            }
+
+            return sequence.ToArray();
+        }
+
+        private static Operand GetRegister(Register reg, OperandType type)
+        {
+            return new Operand(reg.Index, reg.Type, type);
+        }
+    }
+}
\ No newline at end of file
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs
new file mode 100644
index 00000000..9a827420
--- /dev/null
+++ b/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs
@@ -0,0 +1,382 @@
+using ARMeilleure.Common;
+using ARMeilleure.IntermediateRepresentation;
+using ARMeilleure.Translation;
+using System.Collections.Generic;
+using System.Diagnostics;
+
+using static ARMeilleure.IntermediateRepresentation.OperandHelper;
+
+namespace ARMeilleure.CodeGen.RegisterAllocators
+{
+    class HybridAllocator : IRegisterAllocator
+    {
+        private const int RegistersCount = 16;
+        private const int MaxIROperands  = 4;
+
+        private struct BlockInfo
+        {
+            public bool HasCall { get; }
+
+            public int IntFixedRegisters { get; }
+            public int VecFixedRegisters { get; }
+
+            public BlockInfo(bool hasCall, int intFixedRegisters, int vecFixedRegisters)
+            {
+                HasCall           = hasCall;
+                IntFixedRegisters = intFixedRegisters;
+                VecFixedRegisters = vecFixedRegisters;
+            }
+        }
+
+        private class LocalInfo
+        {
+            public int Uses     { get; set; }
+            public int UseCount { get; set; }
+
+            public bool PreAllocated { get; set; }
+            public int  Register     { get; set; }
+            public int  SpillOffset  { get; set; }
+
+            public int Sequence { get; set; }
+
+            public Operand Temp { get; set; }
+
+            public OperandType Type { get; }
+
+            private int _first;
+            private int _last;
+
+            public bool IsBlockLocal => _first == _last;
+
+            public LocalInfo(OperandType type, int uses)
+            {
+                Uses = uses;
+                Type = type;
+
+                _first = -1;
+                _last  = -1;
+            }
+
+            public void SetBlockIndex(int blkIndex)
+            {
+                if (_first == -1 || blkIndex < _first)
+                {
+                    _first = blkIndex;
+                }
+
+                if (_last == -1 || blkIndex > _last)
+                {
+                    _last = blkIndex;
+                }
+            }
+        }
+
+        public AllocationResult RunPass(
+            ControlFlowGraph cfg,
+            StackAllocator stackAlloc,
+            RegisterMasks regMasks)
+        {
+            int intUsedRegisters = 0;
+            int vecUsedRegisters = 0;
+
+            int intFreeRegisters = regMasks.IntAvailableRegisters;
+            int vecFreeRegisters = regMasks.VecAvailableRegisters;
+
+            BlockInfo[] blockInfo = new BlockInfo[cfg.Blocks.Count];
+
+            List<LocalInfo> locInfo = new List<LocalInfo>();
+
+            for (int index = cfg.PostOrderBlocks.Length - 1; index >= 0; index--)
+            {
+                BasicBlock block = cfg.PostOrderBlocks[index];
+
+                int intFixedRegisters = 0;
+                int vecFixedRegisters = 0;
+
+                bool hasCall = false;
+
+                foreach (Node node in block.Operations)
+                {
+                    if (node is Operation operation && operation.Instruction == Instruction.Call)
+                    {
+                        hasCall = true;
+                    }
+
+                    for (int srcIndex = 0; srcIndex < node.SourcesCount; srcIndex++)
+                    {
+                        Operand source = node.GetSource(srcIndex);
+
+                        if (source.Kind == OperandKind.LocalVariable)
+                        {
+                            locInfo[source.AsInt32() - 1].SetBlockIndex(block.Index);
+                        }
+                    }
+
+                    for (int dstIndex = 0; dstIndex < node.DestinationsCount; dstIndex++)
+                    {
+                        Operand dest = node.GetDestination(dstIndex);
+
+                        if (dest.Kind == OperandKind.LocalVariable)
+                        {
+                            LocalInfo info;
+
+                            if (dest.Value != 0)
+                            {
+                                info = locInfo[dest.AsInt32() - 1];
+                            }
+                            else
+                            {
+                                dest.NumberLocal(locInfo.Count + 1);
+
+                                info = new LocalInfo(dest.Type, UsesCount(dest));
+
+                                locInfo.Add(info);
+                            }
+
+                            info.SetBlockIndex(block.Index);
+                        }
+                        else if (dest.Kind == OperandKind.Register)
+                        {
+                            if (dest.Type.IsInteger())
+                            {
+                                intFixedRegisters |= 1 << dest.GetRegister().Index;
+                            }
+                            else
+                            {
+                                vecFixedRegisters |= 1 << dest.GetRegister().Index;
+                            }
+                        }
+                    }
+                }
+
+                blockInfo[block.Index] = new BlockInfo(hasCall, intFixedRegisters, vecFixedRegisters);
+            }
+
+            int sequence = 0;
+
+            for (int index = cfg.PostOrderBlocks.Length - 1; index >= 0; index--)
+            {
+                BasicBlock block = cfg.PostOrderBlocks[index];
+
+                BlockInfo blkInfo = blockInfo[block.Index];
+
+                int intLocalFreeRegisters = intFreeRegisters & ~blkInfo.IntFixedRegisters;
+                int vecLocalFreeRegisters = vecFreeRegisters & ~blkInfo.VecFixedRegisters;
+
+                int intCallerSavedRegisters = blkInfo.HasCall ? regMasks.IntCallerSavedRegisters : 0;
+                int vecCallerSavedRegisters = blkInfo.HasCall ? regMasks.VecCallerSavedRegisters : 0;
+
+                int intSpillTempRegisters = SelectSpillTemps(
+                    intCallerSavedRegisters & ~blkInfo.IntFixedRegisters,
+                    intLocalFreeRegisters);
+                int vecSpillTempRegisters = SelectSpillTemps(
+                    vecCallerSavedRegisters & ~blkInfo.VecFixedRegisters,
+                    vecLocalFreeRegisters);
+
+                intLocalFreeRegisters &= ~(intSpillTempRegisters | intCallerSavedRegisters);
+                vecLocalFreeRegisters &= ~(vecSpillTempRegisters | vecCallerSavedRegisters);
+
+                for (LinkedListNode<Node> llNode = block.Operations.First; llNode != null; llNode = llNode.Next)
+                {
+                    Node node = llNode.Value;
+
+                    int intLocalUse = 0;
+                    int vecLocalUse = 0;
+
+                    for (int srcIndex = 0; srcIndex < node.SourcesCount; srcIndex++)
+                    {
+                        Operand source = node.GetSource(srcIndex);
+
+                        if (source.Kind != OperandKind.LocalVariable)
+                        {
+                            continue;
+                        }
+
+                        LocalInfo info = locInfo[source.AsInt32() - 1];
+
+                        info.UseCount++;
+
+                        Debug.Assert(info.UseCount <= info.Uses);
+
+                        if (info.Register != -1)
+                        {
+                            node.SetSource(srcIndex, Register(info.Register, source.Type.ToRegisterType(), source.Type));
+
+                            if (info.UseCount == info.Uses && !info.PreAllocated)
+                            {
+                                if (source.Type.IsInteger())
+                                {
+                                    intLocalFreeRegisters |= 1 << info.Register;
+                                }
+                                else
+                                {
+                                    vecLocalFreeRegisters |= 1 << info.Register;
+                                }
+                            }
+                        }
+                        else
+                        {
+                            Operand temp = info.Temp;
+
+                            if (temp == null || info.Sequence != sequence)
+                            {
+                                temp = source.Type.IsInteger()
+                                    ? GetSpillTemp(source, intSpillTempRegisters, ref intLocalUse)
+                                    : GetSpillTemp(source, vecSpillTempRegisters, ref vecLocalUse);
+
+                                info.Sequence = sequence;
+                                info.Temp     = temp;
+                            }
+
+                            node.SetSource(srcIndex, temp);
+
+                            Operation fillOp = new Operation(Instruction.Fill, temp, Const(info.SpillOffset));
+
+                            block.Operations.AddBefore(llNode, fillOp);
+                        }
+                    }
+
+                    int intLocalAsg = 0;
+                    int vecLocalAsg = 0;
+
+                    for (int dstIndex = 0; dstIndex < node.DestinationsCount; dstIndex++)
+                    {
+                        Operand dest = node.GetDestination(dstIndex);
+
+                        if (dest.Kind != OperandKind.LocalVariable)
+                        {
+                            continue;
+                        }
+
+                        LocalInfo info = locInfo[dest.AsInt32() - 1];
+
+                        if (info.UseCount == 0 && !info.PreAllocated)
+                        {
+                            int mask = dest.Type.IsInteger()
+                                ? intLocalFreeRegisters
+                                : vecLocalFreeRegisters;
+
+                            if (info.IsBlockLocal && mask != 0)
+                            {
+                                int selectedReg = BitUtils.LowestBitSet(mask);
+
+                                info.Register = selectedReg;
+
+                                if (dest.Type.IsInteger())
+                                {
+                                    intLocalFreeRegisters &= ~(1 << selectedReg);
+                                    intUsedRegisters      |=   1 << selectedReg;
+                                }
+                                else
+                                {
+                                    vecLocalFreeRegisters &= ~(1 << selectedReg);
+                                    vecUsedRegisters      |=   1 << selectedReg;
+                                }
+                            }
+                            else
+                            {
+                                info.Register    = -1;
+                                info.SpillOffset = stackAlloc.Allocate(dest.Type.GetSizeInBytes());
+                            }
+                        }
+
+                        info.UseCount++;
+
+                        Debug.Assert(info.UseCount <= info.Uses);
+
+                        if (info.Register != -1)
+                        {
+                            node.SetDestination(dstIndex, Register(info.Register, dest.Type.ToRegisterType(), dest.Type));
+                        }
+                        else
+                        {
+                            Operand temp = info.Temp;
+
+                            if (temp == null || info.Sequence != sequence)
+                            {
+                                temp = dest.Type.IsInteger()
+                                    ? GetSpillTemp(dest, intSpillTempRegisters, ref intLocalAsg)
+                                    : GetSpillTemp(dest, vecSpillTempRegisters, ref vecLocalAsg);
+
+                                info.Sequence = sequence;
+                                info.Temp     = temp;
+                            }
+
+                            node.SetDestination(dstIndex, temp);
+
+                            Operation spillOp = new Operation(Instruction.Spill, null, Const(info.SpillOffset), temp);
+
+                            llNode = block.Operations.AddAfter(llNode, spillOp);
+                        }
+                    }
+
+                    sequence++;
+
+                    intUsedRegisters |= intLocalAsg | intLocalUse;
+                    vecUsedRegisters |= vecLocalAsg | vecLocalUse;
+                }
+            }
+
+            return new AllocationResult(intUsedRegisters, vecUsedRegisters, stackAlloc.TotalSize);
+        }
+
+        private static int SelectSpillTemps(int mask0, int mask1)
+        {
+            int selection = 0;
+            int count     = 0;
+
+            while (count < MaxIROperands && mask0 != 0)
+            {
+                int mask = mask0 & -mask0;
+
+                selection |= mask;
+
+                mask0 &= ~mask;
+
+                count++;
+            }
+
+            while (count < MaxIROperands && mask1 != 0)
+            {
+                int mask = mask1 & -mask1;
+
+                selection |= mask;
+
+                mask1 &= ~mask;
+
+                count++;
+            }
+
+            Debug.Assert(count == MaxIROperands, "No enough registers for spill temps.");
+
+            return selection;
+        }
+
+        private static Operand GetSpillTemp(Operand local, int freeMask, ref int useMask)
+        {
+            int selectedReg = BitUtils.LowestBitSet(freeMask & ~useMask);
+
+            useMask |= 1 << selectedReg;
+
+            return Register(selectedReg, local.Type.ToRegisterType(), local.Type);
+        }
+
+        private static int UsesCount(Operand local)
+        {
+            return local.Assignments.Count + local.Uses.Count;
+        }
+
+        private static IEnumerable<BasicBlock> Successors(BasicBlock block)
+        {
+            if (block.Next != null)
+            {
+                yield return block.Next;
+            }
+
+            if (block.Branch != null)
+            {
+                yield return block.Branch;
+            }
+        }
+    }
+}
\ No newline at end of file
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/IRegisterAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/IRegisterAllocator.cs
new file mode 100644
index 00000000..8f236c25
--- /dev/null
+++ b/ARMeilleure/CodeGen/RegisterAllocators/IRegisterAllocator.cs
@@ -0,0 +1,12 @@
+using ARMeilleure.Translation;
+
+namespace ARMeilleure.CodeGen.RegisterAllocators
+{
+    interface IRegisterAllocator
+    {
+        AllocationResult RunPass(
+            ControlFlowGraph cfg,
+            StackAllocator stackAlloc,
+            RegisterMasks regMasks);
+    }
+}
\ No newline at end of file
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs
new file mode 100644
index 00000000..6d5ecc14
--- /dev/null
+++ b/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs
@@ -0,0 +1,1019 @@
+using ARMeilleure.Common;
+using ARMeilleure.IntermediateRepresentation;
+using ARMeilleure.Translation;
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+
+namespace ARMeilleure.CodeGen.RegisterAllocators
+{
+    // Based on:
+    // "Linear Scan Register Allocation for the Java(tm) HotSpot Client Compiler".
+    // http://www.christianwimmer.at/Publications/Wimmer04a/Wimmer04a.pdf
+    class LinearScanAllocator : IRegisterAllocator
+    {
+        private const int InstructionGap     = 2;
+        private const int InstructionGapMask = InstructionGap - 1;
+
+        private const int RegistersCount = 16;
+
+        private HashSet<int> _blockEdges;
+
+        private LiveRange[] _blockRanges;
+
+        private BitMap[] _blockLiveIn;
+
+        private List<LiveInterval> _intervals;
+
+        private LiveInterval[] _parentIntervals;
+
+        private List<LinkedListNode<Node>> _operationNodes;
+
+        private int _operationsCount;
+
+        private class AllocationContext
+        {
+            public RegisterMasks Masks { get; }
+
+            public StackAllocator StackAlloc { get; }
+
+            public BitMap Active   { get; }
+            public BitMap Inactive { get; }
+
+            public int IntUsedRegisters { get; set; }
+            public int VecUsedRegisters { get; set; }
+
+            public AllocationContext(StackAllocator stackAlloc, RegisterMasks masks, int intervalsCount)
+            {
+                StackAlloc = stackAlloc;
+                Masks      = masks;
+
+                Active   = new BitMap(intervalsCount);
+                Inactive = new BitMap(intervalsCount);
+            }
+
+            public void MoveActiveToInactive(int bit)
+            {
+                Move(Active, Inactive, bit);
+            }
+
+            public void MoveInactiveToActive(int bit)
+            {
+                Move(Inactive, Active, bit);
+            }
+
+            private static void Move(BitMap source, BitMap dest, int bit)
+            {
+                source.Clear(bit);
+
+                dest.Set(bit);
+            }
+        }
+
+        public AllocationResult RunPass(
+            ControlFlowGraph cfg,
+            StackAllocator stackAlloc,
+            RegisterMasks regMasks)
+        {
+            NumberLocals(cfg);
+
+            AllocationContext context = new AllocationContext(stackAlloc, regMasks, _intervals.Count);
+
+            BuildIntervals(cfg, context);
+
+            for (int index = 0; index < _intervals.Count; index++)
+            {
+                LiveInterval current = _intervals[index];
+
+                if (current.IsEmpty)
+                {
+                    continue;
+                }
+
+                if (current.IsFixed)
+                {
+                    context.Active.Set(index);
+
+                    if (current.Register.Type == RegisterType.Integer)
+                    {
+                        context.IntUsedRegisters |= 1 << current.Register.Index;
+                    }
+                    else /* if (interval.Register.Type == RegisterType.Vector) */
+                    {
+                        context.VecUsedRegisters |= 1 << current.Register.Index;
+                    }
+
+                    continue;
+                }
+
+                AllocateInterval(context, current, index);
+            }
+
+            for (int index = RegistersCount * 2; index < _intervals.Count; index++)
+            {
+                if (!_intervals[index].IsSpilled)
+                {
+                    ReplaceLocalWithRegister(_intervals[index]);
+                }
+            }
+
+            InsertSplitCopies();
+            InsertSplitCopiesAtEdges(cfg);
+
+            return new AllocationResult(
+                context.IntUsedRegisters,
+                context.VecUsedRegisters,
+                context.StackAlloc.TotalSize);
+        }
+
+        private void AllocateInterval(AllocationContext context, LiveInterval current, int cIndex)
+        {
+            // Check active intervals that already ended.
+            foreach (int iIndex in context.Active)
+            {
+                LiveInterval interval = _intervals[iIndex];
+
+                if (interval.GetEnd() < current.GetStart())
+                {
+                    context.Active.Clear(iIndex);
+                }
+                else if (!interval.Overlaps(current.GetStart()))
+                {
+                    context.MoveActiveToInactive(iIndex);
+                }
+            }
+
+            // Check inactive intervals that already ended or were reactivated.
+            foreach (int iIndex in context.Inactive)
+            {
+                LiveInterval interval = _intervals[iIndex];
+
+                if (interval.GetEnd() < current.GetStart())
+                {
+                    context.Inactive.Clear(iIndex);
+                }
+                else if (interval.Overlaps(current.GetStart()))
+                {
+                    context.MoveInactiveToActive(iIndex);
+                }
+            }
+
+            if (!TryAllocateRegWithoutSpill(context, current, cIndex))
+            {
+                AllocateRegWithSpill(context, current, cIndex);
+            }
+        }
+
+        private bool TryAllocateRegWithoutSpill(AllocationContext context, LiveInterval current, int cIndex)
+        {
+            RegisterType regType = current.Local.Type.ToRegisterType();
+
+            int availableRegisters = context.Masks.GetAvailableRegisters(regType);
+
+            int[] freePositions = new int[RegistersCount];
+
+            for (int index = 0; index < RegistersCount; index++)
+            {
+                if ((availableRegisters & (1 << index)) != 0)
+                {
+                    freePositions[index] = int.MaxValue;
+                }
+            }
+
+            foreach (int iIndex in context.Active)
+            {
+                LiveInterval interval = _intervals[iIndex];
+
+                if (interval.Register.Type == regType)
+                {
+                    freePositions[interval.Register.Index] = 0;
+                }
+            }
+
+            foreach (int iIndex in context.Inactive)
+            {
+                LiveInterval interval = _intervals[iIndex];
+
+                if (interval.Register.Type == regType)
+                {
+                    int overlapPosition = interval.GetOverlapPosition(current);
+
+                    if (overlapPosition != LiveInterval.NotFound && freePositions[interval.Register.Index] > overlapPosition)
+                    {
+                        freePositions[interval.Register.Index] = overlapPosition;
+                    }
+                }
+            }
+
+            int selectedReg = GetHighestValueIndex(freePositions);
+
+            int selectedNextUse = freePositions[selectedReg];
+
+            // Intervals starts and ends at odd positions, unless they span an entire
+            // block, in this case they will have ranges at a even position.
+            // When a interval is loaded from the stack to a register, we can only
+            // do the split at a odd position, because otherwise the split interval
+            // that is inserted on the list to be processed may clobber a register
+            // used by the instruction at the same position as the split.
+            // The problem only happens when a interval ends exactly at this instruction,
+            // because otherwise they would interfere, and the register wouldn't be selected.
+            // When the interval is aligned and the above happens, there's no problem as
+            // the instruction that is actually with the last use is the one
+            // before that position.
+            selectedNextUse &= ~InstructionGapMask;
+
+            if (selectedNextUse <= current.GetStart())
+            {
+                return false;
+            }
+            else if (selectedNextUse < current.GetEnd())
+            {
+                Debug.Assert(selectedNextUse > current.GetStart(), "Trying to split interval at the start.");
+
+                LiveInterval splitChild = current.Split(selectedNextUse);
+
+                if (splitChild.UsesCount != 0)
+                {
+                    Debug.Assert(splitChild.GetStart() > current.GetStart(), "Split interval has an invalid start position.");
+
+                    InsertInterval(splitChild);
+                }
+                else
+                {
+                    Spill(context, splitChild);
+                }
+            }
+
+            current.Register = new Register(selectedReg, regType);
+
+            if (regType == RegisterType.Integer)
+            {
+                context.IntUsedRegisters |= 1 << selectedReg;
+            }
+            else /* if (regType == RegisterType.Vector) */
+            {
+                context.VecUsedRegisters |= 1 << selectedReg;
+            }
+
+            context.Active.Set(cIndex);
+
+            return true;
+        }
+
+        private void AllocateRegWithSpill(AllocationContext context, LiveInterval current, int cIndex)
+        {
+            RegisterType regType = current.Local.Type.ToRegisterType();
+
+            int availableRegisters = context.Masks.GetAvailableRegisters(regType);
+
+            int[] usePositions     = new int[RegistersCount];
+            int[] blockedPositions = new int[RegistersCount];
+
+            for (int index = 0; index < RegistersCount; index++)
+            {
+                if ((availableRegisters & (1 << index)) != 0)
+                {
+                    usePositions[index] = int.MaxValue;
+
+                    blockedPositions[index] = int.MaxValue;
+                }
+            }
+
+            void SetUsePosition(int index, int position)
+            {
+                usePositions[index] = Math.Min(usePositions[index], position);
+            }
+
+            void SetBlockedPosition(int index, int position)
+            {
+                blockedPositions[index] = Math.Min(blockedPositions[index], position);
+
+                SetUsePosition(index, position);
+            }
+
+            foreach (int iIndex in context.Active)
+            {
+                LiveInterval interval = _intervals[iIndex];
+
+                if (!interval.IsFixed && interval.Register.Type == regType)
+                {
+                    int nextUse = interval.NextUseAfter(current.GetStart());
+
+                    if (nextUse != -1)
+                    {
+                        SetUsePosition(interval.Register.Index, nextUse);
+                    }
+                }
+            }
+
+            foreach (int iIndex in context.Inactive)
+            {
+                LiveInterval interval = _intervals[iIndex];
+
+                if (!interval.IsFixed && interval.Register.Type == regType && interval.Overlaps(current))
+                {
+                    int nextUse = interval.NextUseAfter(current.GetStart());
+
+                    if (nextUse != -1)
+                    {
+                        SetUsePosition(interval.Register.Index, nextUse);
+                    }
+                }
+            }
+
+            foreach (int iIndex in context.Active)
+            {
+                LiveInterval interval = _intervals[iIndex];
+
+                if (interval.IsFixed && interval.Register.Type == regType)
+                {
+                    SetBlockedPosition(interval.Register.Index, 0);
+                }
+            }
+
+            foreach (int iIndex in context.Inactive)
+            {
+                LiveInterval interval = _intervals[iIndex];
+
+                if (interval.IsFixed && interval.Register.Type == regType)
+                {
+                    int overlapPosition = interval.GetOverlapPosition(current);
+
+                    if (overlapPosition != LiveInterval.NotFound)
+                    {
+                        SetBlockedPosition(interval.Register.Index, overlapPosition);
+                    }
+                }
+            }
+
+            int selectedReg = GetHighestValueIndex(usePositions);
+
+            int currentFirstUse = current.FirstUse();
+
+            Debug.Assert(currentFirstUse >= 0, "Current interval has no uses.");
+
+            if (usePositions[selectedReg] < currentFirstUse)
+            {
+                // All intervals on inactive and active are being used before current,
+                // so spill the current interval.
+                Debug.Assert(currentFirstUse > current.GetStart(), "Trying to spill a interval currently being used.");
+
+                LiveInterval splitChild = current.Split(currentFirstUse);
+
+                Debug.Assert(splitChild.GetStart() > current.GetStart(), "Split interval has an invalid start position.");
+
+                InsertInterval(splitChild);
+
+                Spill(context, current);
+            }
+            else if (blockedPositions[selectedReg] > current.GetEnd())
+            {
+                // Spill made the register available for the entire current lifetime,
+                // so we only need to split the intervals using the selected register.
+                current.Register = new Register(selectedReg, regType);
+
+                SplitAndSpillOverlappingIntervals(context, current);
+
+                context.Active.Set(cIndex);
+            }
+            else
+            {
+                // There are conflicts even after spill due to the use of fixed registers
+                // that can't be spilled, so we need to also split current at the point of
+                // the first fixed register use.
+                current.Register = new Register(selectedReg, regType);
+
+                int splitPosition = blockedPositions[selectedReg] & ~InstructionGapMask;
+
+                Debug.Assert(splitPosition > current.GetStart(), "Trying to split a interval at a invalid position.");
+
+                LiveInterval splitChild = current.Split(splitPosition);
+
+                if (splitChild.UsesCount != 0)
+                {
+                    Debug.Assert(splitChild.GetStart() > current.GetStart(), "Split interval has an invalid start position.");
+
+                    InsertInterval(splitChild);
+                }
+                else
+                {
+                    Spill(context, splitChild);
+                }
+
+                SplitAndSpillOverlappingIntervals(context, current);
+
+                context.Active.Set(cIndex);
+            }
+        }
+
+        private static int GetHighestValueIndex(int[] array)
+        {
+            int higuest = array[0];
+
+            if (higuest == int.MaxValue)
+            {
+                return 0;
+            }
+
+            int selected = 0;
+
+            for (int index = 1; index < array.Length; index++)
+            {
+                int current = array[index];
+
+                if (higuest < current)
+                {
+                    higuest  = current;
+                    selected = index;
+
+                    if (current == int.MaxValue)
+                    {
+                        break;
+                    }
+                }
+            }
+
+            return selected;
+        }
+
+        private void SplitAndSpillOverlappingIntervals(AllocationContext context, LiveInterval current)
+        {
+            foreach (int iIndex in context.Active)
+            {
+                LiveInterval interval = _intervals[iIndex];
+
+                if (!interval.IsFixed && interval.Register == current.Register)
+                {
+                    SplitAndSpillOverlappingInterval(context, current, interval);
+
+                    context.Active.Clear(iIndex);
+                }
+            }
+
+            foreach (int iIndex in context.Inactive)
+            {
+                LiveInterval interval = _intervals[iIndex];
+
+                if (!interval.IsFixed && interval.Register == current.Register && interval.Overlaps(current))
+                {
+                    SplitAndSpillOverlappingInterval(context, current, interval);
+
+                    context.Inactive.Clear(iIndex);
+                }
+            }
+        }
+
+        private void SplitAndSpillOverlappingInterval(
+            AllocationContext context,
+            LiveInterval      current,
+            LiveInterval      interval)
+        {
+            // If there's a next use after the start of the current interval,
+            // we need to split the spilled interval twice, and re-insert it
+            // on the "pending" list to ensure that it will get a new register
+            // on that use position.
+            int nextUse = interval.NextUseAfter(current.GetStart());
+
+            LiveInterval splitChild;
+
+            if (interval.GetStart() < current.GetStart())
+            {
+                splitChild = interval.Split(current.GetStart());
+            }
+            else
+            {
+                splitChild = interval;
+            }
+
+            if (nextUse != -1)
+            {
+                Debug.Assert(nextUse > current.GetStart(), "Trying to spill a interval currently being used.");
+
+                if (nextUse > splitChild.GetStart())
+                {
+                    LiveInterval right = splitChild.Split(nextUse);
+
+                    Spill(context, splitChild);
+
+                    splitChild = right;
+                }
+
+                InsertInterval(splitChild);
+            }
+            else
+            {
+                Spill(context, splitChild);
+            }
+        }
+
+        private void InsertInterval(LiveInterval interval)
+        {
+            Debug.Assert(interval.UsesCount != 0, "Trying to insert a interval without uses.");
+            Debug.Assert(!interval.IsEmpty,       "Trying to insert a empty interval.");
+            Debug.Assert(!interval.IsSpilled,     "Trying to insert a spilled interval.");
+
+            int startIndex = RegistersCount * 2;
+
+            int insertIndex = _intervals.BinarySearch(startIndex, _intervals.Count - startIndex, interval, null);
+
+            if (insertIndex < 0)
+            {
+                insertIndex = ~insertIndex;
+            }
+
+            _intervals.Insert(insertIndex, interval);
+        }
+
+        private void Spill(AllocationContext context, LiveInterval interval)
+        {
+            Debug.Assert(!interval.IsFixed,       "Trying to spill a fixed interval.");
+            Debug.Assert(interval.UsesCount == 0, "Trying to spill a interval with uses.");
+
+            // We first check if any of the siblings were spilled, if so we can reuse
+            // the stack offset. Otherwise, we allocate a new space on the stack.
+            // This prevents stack-to-stack copies being necessary for a split interval.
+            if (!interval.TrySpillWithSiblingOffset())
+            {
+                interval.Spill(context.StackAlloc.Allocate(interval.Local.Type));
+            }
+        }
+
+        private void InsertSplitCopies()
+        {
+            Dictionary<int, CopyResolver> copyResolvers = new Dictionary<int, CopyResolver>();
+
+            CopyResolver GetCopyResolver(int position)
+            {
+                CopyResolver copyResolver = new CopyResolver();
+
+                if (copyResolvers.TryAdd(position, copyResolver))
+                {
+                    return copyResolver;
+                }
+
+                return copyResolvers[position];
+            }
+
+            foreach (LiveInterval interval in _intervals.Where(x => x.IsSplit))
+            {
+                LiveInterval previous = interval;
+
+                foreach (LiveInterval splitChild in interval.SplitChilds())
+                {
+                    int splitPosition = splitChild.GetStart();
+
+                    if (!_blockEdges.Contains(splitPosition) && previous.GetEnd() == splitPosition)
+                    {
+                        GetCopyResolver(splitPosition).AddSplit(previous, splitChild);
+                    }
+
+                    previous = splitChild;
+                }
+            }
+
+            foreach (KeyValuePair<int, CopyResolver> kv in copyResolvers)
+            {
+                CopyResolver copyResolver = kv.Value;
+
+                if (!copyResolver.HasCopy)
+                {
+                    continue;
+                }
+
+                int splitPosition = kv.Key;
+
+                LinkedListNode<Node> node = GetOperationNode(splitPosition);
+
+                Operation[] sequence = copyResolver.Sequence();
+
+                node = node.List.AddBefore(node, sequence[0]);
+
+                for (int index = 1; index < sequence.Length; index++)
+                {
+                    node = node.List.AddAfter(node, sequence[index]);
+                }
+            }
+        }
+
+        private void InsertSplitCopiesAtEdges(ControlFlowGraph cfg)
+        {
+            int blocksCount = cfg.Blocks.Count;
+
+            bool IsSplitEdgeBlock(BasicBlock block)
+            {
+                return block.Index >= blocksCount;
+            }
+
+            for (LinkedListNode<BasicBlock> node = cfg.Blocks.First; node != null; node = node.Next)
+            {
+                BasicBlock block = node.Value;
+
+                if (IsSplitEdgeBlock(block))
+                {
+                    continue;
+                }
+
+                bool hasSingleOrNoSuccessor = block.Next == null || block.Branch == null;
+
+                foreach (BasicBlock successor in Successors(block))
+                {
+                    int succIndex = successor.Index;
+
+                    // If the current node is a split node, then the actual successor node
+                    // (the successor before the split) should be right after it.
+                    if (IsSplitEdgeBlock(successor))
+                    {
+                        succIndex = Successors(successor).First().Index;
+                    }
+
+                    CopyResolver copyResolver = new CopyResolver();
+
+                    foreach (int iIndex in _blockLiveIn[succIndex])
+                    {
+                        LiveInterval interval = _parentIntervals[iIndex];
+
+                        if (!interval.IsSplit)
+                        {
+                            continue;
+                        }
+
+                        int lEnd   = _blockRanges[block.Index].End - 1;
+                        int rStart = _blockRanges[succIndex].Start;
+
+                        LiveInterval left  = interval.GetSplitChild(lEnd);
+                        LiveInterval right = interval.GetSplitChild(rStart);
+
+                        if (left != null && right != null && left != right)
+                        {
+                            copyResolver.AddSplit(left, right);
+                        }
+                    }
+
+                    if (!copyResolver.HasCopy)
+                    {
+                        continue;
+                    }
+
+                    Operation[] sequence = copyResolver.Sequence();
+
+                    if (hasSingleOrNoSuccessor)
+                    {
+                        foreach (Operation operation in sequence)
+                        {
+                            block.Append(operation);
+                        }
+                    }
+                    else if (successor.Predecessors.Count == 1)
+                    {
+                        LinkedListNode<Node> prependNode = successor.Operations.AddFirst(sequence[0]);
+
+                        for (int index = 1; index < sequence.Length; index++)
+                        {
+                            Operation operation = sequence[index];
+
+                            prependNode = successor.Operations.AddAfter(prependNode, operation);
+                        }
+                    }
+                    else
+                    {
+                        // Split the critical edge.
+                        BasicBlock splitBlock = cfg.SplitEdge(block, successor);
+
+                        foreach (Operation operation in sequence)
+                        {
+                            splitBlock.Append(operation);
+                        }
+                    }
+                }
+            }
+        }
+
+        private void ReplaceLocalWithRegister(LiveInterval current)
+        {
+            Operand register = GetRegister(current);
+
+            foreach (int usePosition in current.UsePositions())
+            {
+                Node operation = GetOperationNode(usePosition).Value;
+
+                for (int index = 0; index < operation.SourcesCount; index++)
+                {
+                    Operand source = operation.GetSource(index);
+
+                    if (source == current.Local)
+                    {
+                        operation.SetSource(index, register);
+                    }
+                }
+
+                for (int index = 0; index < operation.DestinationsCount; index++)
+                {
+                    Operand dest = operation.GetDestination(index);
+
+                    if (dest == current.Local)
+                    {
+                        operation.SetDestination(index, register);
+                    }
+                }
+            }
+        }
+
+        private static Operand GetRegister(LiveInterval interval)
+        {
+            Debug.Assert(!interval.IsSpilled, "Spilled intervals are not allowed.");
+
+            return new Operand(
+                interval.Register.Index,
+                interval.Register.Type,
+                interval.Local.Type);
+        }
+
+        private LinkedListNode<Node> GetOperationNode(int position)
+        {
+            return _operationNodes[position / InstructionGap];
+        }
+
+        private void NumberLocals(ControlFlowGraph cfg)
+        {
+            _operationNodes = new List<LinkedListNode<Node>>();
+
+            _intervals = new List<LiveInterval>();
+
+            for (int index = 0; index < RegistersCount; index++)
+            {
+                _intervals.Add(new LiveInterval(new Register(index, RegisterType.Integer)));
+                _intervals.Add(new LiveInterval(new Register(index, RegisterType.Vector)));
+            }
+
+            HashSet<Operand> visited = new HashSet<Operand>();
+
+            _operationsCount = 0;
+
+            for (int index = cfg.PostOrderBlocks.Length - 1; index >= 0; index--)
+            {
+                BasicBlock block = cfg.PostOrderBlocks[index];
+
+                for (LinkedListNode<Node> node = block.Operations.First; node != null; node = node.Next)
+                {
+                    _operationNodes.Add(node);
+
+                    Node operation = node.Value;
+
+                    foreach (Operand dest in Destinations(operation))
+                    {
+                        if (dest.Kind == OperandKind.LocalVariable && visited.Add(dest))
+                        {
+                            dest.NumberLocal(_intervals.Count);
+
+                            _intervals.Add(new LiveInterval(dest));
+                        }
+                    }
+                }
+
+                _operationsCount += block.Operations.Count * InstructionGap;
+
+                if (block.Operations.Count == 0)
+                {
+                    // Pretend we have a dummy instruction on the empty block.
+                    _operationNodes.Add(null);
+
+                    _operationsCount += InstructionGap;
+                }
+            }
+
+            _parentIntervals = _intervals.ToArray();
+        }
+
+        private void BuildIntervals(ControlFlowGraph cfg, AllocationContext context)
+        {
+            _blockRanges = new LiveRange[cfg.Blocks.Count];
+
+            int mapSize = _intervals.Count;
+
+            BitMap[] blkLiveGen  = new BitMap[cfg.Blocks.Count];
+            BitMap[] blkLiveKill = new BitMap[cfg.Blocks.Count];
+
+            // Compute local live sets.
+            foreach (BasicBlock block in cfg.Blocks)
+            {
+                BitMap liveGen  = new BitMap(mapSize);
+                BitMap liveKill = new BitMap(mapSize);
+
+                foreach (Node node in block.Operations)
+                {
+                    foreach (Operand source in Sources(node))
+                    {
+                        int id = GetOperandId(source);
+
+                        if (!liveKill.IsSet(id))
+                        {
+                            liveGen.Set(id);
+                        }
+                    }
+
+                    foreach (Operand dest in Destinations(node))
+                    {
+                        liveKill.Set(GetOperandId(dest));
+                    }
+                }
+
+                blkLiveGen [block.Index] = liveGen;
+                blkLiveKill[block.Index] = liveKill;
+            }
+
+            // Compute global live sets.
+            BitMap[] blkLiveIn  = new BitMap[cfg.Blocks.Count];
+            BitMap[] blkLiveOut = new BitMap[cfg.Blocks.Count];
+
+            for (int index = 0; index < cfg.Blocks.Count; index++)
+            {
+                blkLiveIn [index] = new BitMap(mapSize);
+                blkLiveOut[index] = new BitMap(mapSize);
+            }
+
+            bool modified;
+
+            do
+            {
+                modified = false;
+
+                for (int index = 0; index < cfg.PostOrderBlocks.Length; index++)
+                {
+                    BasicBlock block = cfg.PostOrderBlocks[index];
+
+                    BitMap liveOut = blkLiveOut[block.Index];
+
+                    foreach (BasicBlock successor in Successors(block))
+                    {
+                        if (liveOut.Set(blkLiveIn[successor.Index]))
+                        {
+                            modified = true;
+                        }
+                    }
+
+                    BitMap liveIn = blkLiveIn[block.Index];
+
+                    liveIn.Set  (liveOut);
+                    liveIn.Clear(blkLiveKill[block.Index]);
+                    liveIn.Set  (blkLiveGen [block.Index]);
+                }
+            }
+            while (modified);
+
+            _blockLiveIn = blkLiveIn;
+
+            _blockEdges = new HashSet<int>();
+
+            // Compute lifetime intervals.
+            int operationPos = _operationsCount;
+
+            for (int index = 0; index < cfg.PostOrderBlocks.Length; index++)
+            {
+                BasicBlock block = cfg.PostOrderBlocks[index];
+
+                // We handle empty blocks by pretending they have a dummy instruction,
+                // because otherwise the block would have the same start and end position,
+                // and this is not valid.
+                int instCount = Math.Max(block.Operations.Count, 1);
+
+                int blockStart = operationPos - instCount * InstructionGap;
+                int blockEnd   = operationPos;
+
+                _blockRanges[block.Index] = new LiveRange(blockStart, blockEnd);
+
+                _blockEdges.Add(blockStart);
+
+                BitMap liveOut = blkLiveOut[block.Index];
+
+                foreach (int id in liveOut)
+                {
+                    _intervals[id].AddRange(blockStart, blockEnd);
+                }
+
+                if (block.Operations.Count == 0)
+                {
+                    operationPos -= InstructionGap;
+
+                    continue;
+                }
+
+                foreach (Node node in BottomOperations(block))
+                {
+                    operationPos -= InstructionGap;
+
+                    foreach (Operand dest in Destinations(node))
+                    {
+                        LiveInterval interval = _intervals[GetOperandId(dest)];
+
+                        interval.SetStart(operationPos + 1);
+                        interval.AddUsePosition(operationPos + 1);
+                    }
+
+                    foreach (Operand source in Sources(node))
+                    {
+                        LiveInterval interval = _intervals[GetOperandId(source)];
+
+                        interval.AddRange(blockStart, operationPos + 1);
+                        interval.AddUsePosition(operationPos);
+                    }
+
+                    if (node is Operation operation && operation.Instruction == Instruction.Call)
+                    {
+                        AddIntervalCallerSavedReg(context.Masks.IntCallerSavedRegisters, operationPos, RegisterType.Integer);
+                        AddIntervalCallerSavedReg(context.Masks.VecCallerSavedRegisters, operationPos, RegisterType.Vector);
+                    }
+                }
+            }
+        }
+
+        private void AddIntervalCallerSavedReg(int mask, int operationPos, RegisterType regType)
+        {
+            while (mask != 0)
+            {
+                int regIndex = BitUtils.LowestBitSet(mask);
+
+                Register callerSavedReg = new Register(regIndex, regType);
+
+                LiveInterval interval = _intervals[GetRegisterId(callerSavedReg)];
+
+                interval.AddRange(operationPos + 1, operationPos + InstructionGap);
+
+                mask &= ~(1 << regIndex);
+            }
+        }
+
+        private static int GetOperandId(Operand operand)
+        {
+            if (operand.Kind == OperandKind.LocalVariable)
+            {
+                return operand.AsInt32();
+            }
+            else if (operand.Kind == OperandKind.Register)
+            {
+                return GetRegisterId(operand.GetRegister());
+            }
+            else
+            {
+                throw new ArgumentException($"Invalid operand kind \"{operand.Kind}\".");
+            }
+        }
+
+        private static int GetRegisterId(Register register)
+        {
+            return (register.Index << 1) | (register.Type == RegisterType.Vector ? 1 : 0);
+        }
+
+        private static IEnumerable<BasicBlock> Successors(BasicBlock block)
+        {
+            if (block.Next != null)
+            {
+                yield return block.Next;
+            }
+
+            if (block.Branch != null)
+            {
+                yield return block.Branch;
+            }
+        }
+
+        private static IEnumerable<Node> BottomOperations(BasicBlock block)
+        {
+            LinkedListNode<Node> node = block.Operations.Last;
+
+            while (node != null && !(node.Value is PhiNode))
+            {
+                yield return node.Value;
+
+                node = node.Previous;
+            }
+        }
+
+        private static IEnumerable<Operand> Destinations(Node node)
+        {
+            for (int index = 0; index < node.DestinationsCount; index++)
+            {
+                yield return node.GetDestination(index);
+            }
+        }
+
+        private static IEnumerable<Operand> Sources(Node node)
+        {
+            for (int index = 0; index < node.SourcesCount; index++)
+            {
+                Operand source = node.GetSource(index);
+
+                if (IsLocalOrRegister(source.Kind))
+                {
+                    yield return source;
+                }
+            }
+        }
+
+        private static bool IsLocalOrRegister(OperandKind kind)
+        {
+            return kind == OperandKind.LocalVariable ||
+                   kind == OperandKind.Register;
+        }
+    }
+}
\ No newline at end of file
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/LiveInterval.cs b/ARMeilleure/CodeGen/RegisterAllocators/LiveInterval.cs
new file mode 100644
index 00000000..18858a76
--- /dev/null
+++ b/ARMeilleure/CodeGen/RegisterAllocators/LiveInterval.cs
@@ -0,0 +1,390 @@
+using ARMeilleure.IntermediateRepresentation;
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+
+namespace ARMeilleure.CodeGen.RegisterAllocators
+{
+    class LiveInterval : IComparable<LiveInterval>
+    {
+        public const int NotFound = -1;
+
+        private LiveInterval _parent;
+
+        private SortedSet<int> _usePositions;
+
+        public int UsesCount => _usePositions.Count;
+
+        private List<LiveRange> _ranges;
+
+        private SortedList<int, LiveInterval> _childs;
+
+        public bool IsSplit => _childs.Count != 0;
+
+        public Operand Local { get; }
+
+        public Register Register { get; set; }
+
+        public int SpillOffset { get; private set; }
+
+        public bool IsSpilled => SpillOffset != -1;
+        public bool IsFixed { get; }
+
+        public bool IsEmpty => _ranges.Count == 0;
+
+        public LiveInterval(Operand local = null, LiveInterval parent = null)
+        {
+            Local   = local;
+            _parent = parent ?? this;
+
+            _usePositions = new SortedSet<int>();
+
+            _ranges = new List<LiveRange>();
+
+            _childs = new SortedList<int, LiveInterval>();
+
+            SpillOffset = -1;
+        }
+
+        public LiveInterval(Register register) : this()
+        {
+            IsFixed  = true;
+            Register = register;
+        }
+
+        public void SetStart(int position)
+        {
+            if (_ranges.Count != 0)
+            {
+                Debug.Assert(position != _ranges[0].End);
+
+                _ranges[0] = new LiveRange(position, _ranges[0].End);
+            }
+            else
+            {
+                _ranges.Add(new LiveRange(position, position + 1));
+            }
+        }
+
+        public int GetStart()
+        {
+            if (_ranges.Count == 0)
+            {
+                throw new InvalidOperationException("Empty interval.");
+            }
+
+            return _ranges[0].Start;
+        }
+
+        public void SetEnd(int position)
+        {
+            if (_ranges.Count != 0)
+            {
+                int lastIdx = _ranges.Count - 1;
+
+                Debug.Assert(position != _ranges[lastIdx].Start);
+
+                _ranges[lastIdx] = new LiveRange(_ranges[lastIdx].Start, position);
+            }
+            else
+            {
+                _ranges.Add(new LiveRange(position, position + 1));
+            }
+        }
+
+        public int GetEnd()
+        {
+            if (_ranges.Count == 0)
+            {
+                throw new InvalidOperationException("Empty interval.");
+            }
+
+            return _ranges[_ranges.Count - 1].End;
+        }
+
+        public void AddRange(int start, int end)
+        {
+            if (start >= end)
+            {
+                throw new ArgumentException("Invalid range start position " + start + ", " + end);
+            }
+
+            int index = _ranges.BinarySearch(new LiveRange(start, end));
+
+            if (index >= 0)
+            {
+                // New range insersects with an existing range, we need to remove
+                // all the intersecting ranges before adding the new one.
+                // We also extend the new range as needed, based on the values of
+                // the existing ranges being removed.
+                int lIndex = index;
+                int rIndex = index;
+
+                while (lIndex > 0 && _ranges[lIndex - 1].End >= start)
+                {
+                    lIndex--;
+                }
+
+                while (rIndex + 1 < _ranges.Count && _ranges[rIndex + 1].Start <= end)
+                {
+                    rIndex++;
+                }
+
+                if (start > _ranges[lIndex].Start)
+                {
+                    start = _ranges[lIndex].Start;
+                }
+
+                if (end < _ranges[rIndex].End)
+                {
+                    end = _ranges[rIndex].End;
+                }
+
+                _ranges.RemoveRange(lIndex, (rIndex - lIndex) + 1);
+
+                InsertRange(lIndex, start, end);
+            }
+            else
+            {
+                InsertRange(~index, start, end);
+            }
+        }
+
+        private void InsertRange(int index, int start, int end)
+        {
+            // Here we insert a new range on the ranges list.
+            // If possible, we extend an existing range rather than inserting a new one.
+            // We can extend an existing range if any of the following conditions are true:
+            // - The new range starts right after the end of the previous range on the list.
+            // - The new range ends right before the start of the next range on the list.
+            // If both cases are true, we can extend either one. We prefer to extend the
+            // previous range, and then remove the next one, but theres no specific reason
+            // for that, extending either one will do.
+            int? extIndex = null;
+
+            if (index > 0 && _ranges[index - 1].End == start)
+            {
+                start = _ranges[index - 1].Start;
+
+                extIndex = index - 1;
+            }
+
+            if (index < _ranges.Count && _ranges[index].Start == end)
+            {
+                end = _ranges[index].End;
+
+                if (extIndex.HasValue)
+                {
+                    _ranges.RemoveAt(index);
+                }
+                else
+                {
+                    extIndex = index;
+                }
+            }
+
+            if (extIndex.HasValue)
+            {
+                _ranges[extIndex.Value] = new LiveRange(start, end);
+            }
+            else
+            {
+                _ranges.Insert(index, new LiveRange(start, end));
+            }
+        }
+
+        public void AddUsePosition(int position)
+        {
+            _usePositions.Add(position);
+        }
+
+        public bool Overlaps(int position)
+        {
+            return _ranges.BinarySearch(new LiveRange(position, position + 1)) >= 0;
+        }
+
+        public bool Overlaps(LiveInterval other)
+        {
+            foreach (LiveRange range in other._ranges)
+            {
+                if (_ranges.BinarySearch(range) >= 0)
+                {
+                    return true;
+                }
+            }
+
+            return false;
+        }
+
+        public int GetOverlapPosition(LiveInterval other)
+        {
+            foreach (LiveRange range in other._ranges)
+            {
+                int overlapIndex = _ranges.BinarySearch(range);
+
+                if (overlapIndex >= 0)
+                {
+                    // It's possible that we have multiple overlaps within a single interval,
+                    // in this case, we pick the one with the lowest start position, since
+                    // we return the first overlap position.
+                    while (overlapIndex > 0 && _ranges[overlapIndex - 1].End > range.Start)
+                    {
+                        overlapIndex--;
+                    }
+
+                    LiveRange overlappingRange = _ranges[overlapIndex];
+
+                    return overlappingRange.Start;
+                }
+            }
+
+            return NotFound;
+        }
+
+        public IEnumerable<LiveInterval> SplitChilds()
+        {
+            return _childs.Values;
+        }
+
+        public IEnumerable<int> UsePositions()
+        {
+            return _usePositions;
+        }
+
+        public int FirstUse()
+        {
+            if (_usePositions.Count == 0)
+            {
+                return NotFound;
+            }
+
+            return _usePositions.First();
+        }
+
+        public int NextUseAfter(int position)
+        {
+            foreach (int usePosition in _usePositions)
+            {
+                if (usePosition >= position)
+                {
+                    return usePosition;
+                }
+            }
+
+            return NotFound;
+        }
+
+        public LiveInterval Split(int position)
+        {
+            LiveInterval right = new LiveInterval(Local, _parent);
+
+            int splitIndex = 0;
+
+            for (; splitIndex < _ranges.Count; splitIndex++)
+            {
+                LiveRange range = _ranges[splitIndex];
+
+                if (position > range.Start && position <= range.End)
+                {
+                    right._ranges.Add(new LiveRange(position, range.End));
+
+                    range = new LiveRange(range.Start, position);
+
+                    _ranges[splitIndex++] = range;
+
+                    break;
+                }
+
+                if (range.Start >= position)
+                {
+                    break;
+                }
+            }
+
+            if (splitIndex < _ranges.Count)
+            {
+                int count = _ranges.Count - splitIndex;
+
+                right._ranges.AddRange(_ranges.GetRange(splitIndex, count));
+
+                _ranges.RemoveRange(splitIndex, count);
+            }
+
+            foreach (int usePosition in _usePositions.Where(x => x >= position))
+            {
+                right._usePositions.Add(usePosition);
+            }
+
+            _usePositions.RemoveWhere(x => x >= position);
+
+            Debug.Assert(_ranges.Count != 0, "Left interval is empty after split.");
+
+            Debug.Assert(right._ranges.Count != 0, "Right interval is empty after split.");
+
+            AddSplitChild(right);
+
+            return right;
+        }
+
+        private void AddSplitChild(LiveInterval child)
+        {
+            Debug.Assert(!child.IsEmpty, "Trying to insert a empty interval.");
+
+            _parent._childs.Add(child.GetStart(), child);
+        }
+
+        public LiveInterval GetSplitChild(int position)
+        {
+            if (Overlaps(position))
+            {
+                return this;
+            }
+
+            foreach (LiveInterval splitChild in _childs.Values)
+            {
+                if (splitChild.Overlaps(position))
+                {
+                    return splitChild;
+                }
+            }
+
+            return null;
+        }
+
+        public bool TrySpillWithSiblingOffset()
+        {
+            foreach (LiveInterval splitChild in _parent._childs.Values)
+            {
+                if (splitChild.IsSpilled)
+                {
+                    Spill(splitChild.SpillOffset);
+
+                    return true;
+                }
+            }
+
+            return false;
+        }
+
+        public void Spill(int offset)
+        {
+            SpillOffset = offset;
+        }
+
+        public int CompareTo(LiveInterval other)
+        {
+            if (_ranges.Count == 0 || other._ranges.Count == 0)
+            {
+                return _ranges.Count.CompareTo(other._ranges.Count);
+            }
+
+            return _ranges[0].Start.CompareTo(other._ranges[0].Start);
+        }
+
+        public override string ToString()
+        {
+            return string.Join("; ", _ranges);
+        }
+    }
+}
\ No newline at end of file
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/LiveRange.cs b/ARMeilleure/CodeGen/RegisterAllocators/LiveRange.cs
new file mode 100644
index 00000000..b5faeffd
--- /dev/null
+++ b/ARMeilleure/CodeGen/RegisterAllocators/LiveRange.cs
@@ -0,0 +1,31 @@
+using System;
+
+namespace ARMeilleure.CodeGen.RegisterAllocators
+{
+    struct LiveRange : IComparable<LiveRange>
+    {
+        public int Start { get; }
+        public int End   { get; }
+
+        public LiveRange(int start, int end)
+        {
+            Start = start;
+            End   = end;
+        }
+
+        public int CompareTo(LiveRange other)
+        {
+            if (Start < other.End && other.Start < End)
+            {
+                return 0;
+            }
+
+            return Start.CompareTo(other.Start);
+        }
+
+        public override string ToString()
+        {
+            return $"[{Start}, {End}[";
+        }
+    }
+}
\ No newline at end of file
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/RegisterMasks.cs b/ARMeilleure/CodeGen/RegisterAllocators/RegisterMasks.cs
new file mode 100644
index 00000000..9652224e
--- /dev/null
+++ b/ARMeilleure/CodeGen/RegisterAllocators/RegisterMasks.cs
@@ -0,0 +1,47 @@
+using ARMeilleure.IntermediateRepresentation;
+using System;
+
+namespace ARMeilleure.CodeGen.RegisterAllocators
+{
+    struct RegisterMasks
+    {
+        public int IntAvailableRegisters   { get; }
+        public int VecAvailableRegisters   { get; }
+        public int IntCallerSavedRegisters { get; }
+        public int VecCallerSavedRegisters { get; }
+        public int IntCalleeSavedRegisters { get; }
+        public int VecCalleeSavedRegisters { get; }
+
+        public RegisterMasks(
+            int intAvailableRegisters,
+            int vecAvailableRegisters,
+            int intCallerSavedRegisters,
+            int vecCallerSavedRegisters,
+            int intCalleeSavedRegisters,
+            int vecCalleeSavedRegisters)
+        {
+            IntAvailableRegisters   = intAvailableRegisters;
+            VecAvailableRegisters   = vecAvailableRegisters;
+            IntCallerSavedRegisters = intCallerSavedRegisters;
+            VecCallerSavedRegisters = vecCallerSavedRegisters;
+            IntCalleeSavedRegisters = intCalleeSavedRegisters;
+            VecCalleeSavedRegisters = vecCalleeSavedRegisters;
+        }
+
+        public int GetAvailableRegisters(RegisterType type)
+        {
+            if (type == RegisterType.Integer)
+            {
+                return IntAvailableRegisters;
+            }
+            else if (type == RegisterType.Vector)
+            {
+                return VecAvailableRegisters;
+            }
+            else
+            {
+                throw new ArgumentException($"Invalid register type \"{type}\".");
+            }
+        }
+    }
+}
\ No newline at end of file
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/StackAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/StackAllocator.cs
new file mode 100644
index 00000000..a6233d6e
--- /dev/null
+++ b/ARMeilleure/CodeGen/RegisterAllocators/StackAllocator.cs
@@ -0,0 +1,27 @@
+using ARMeilleure.Common;
+using ARMeilleure.IntermediateRepresentation;
+using System;
+
+namespace ARMeilleure.CodeGen.RegisterAllocators
+{
+    class StackAllocator
+    {
+        private int _offset;
+
+        public int TotalSize => _offset;
+
+        public int Allocate(OperandType type)
+        {
+            return Allocate(type.GetSizeInBytes());
+        }
+
+        public int Allocate(int sizeInBytes)
+        {
+            int offset = _offset;
+
+            _offset += sizeInBytes;
+
+            return offset;
+        }
+    }
+}
\ No newline at end of file