Refactoring and optimization on CPU translation (#661)

* Refactoring and optimization on CPU translation

* Remove now unused property

* Rename ilBlock -> block (local)

* Change equality comparison on RegisterMask for consistency

Co-Authored-By: gdkchan <gab.dark.100@gmail.com>

* Add back the aggressive inlining attribute to the Synchronize method

* Implement IEquatable on the Register struct

* Fix identation

1 files changed, 124 insertions, 78 deletions

diff --git a/ChocolArm64/Decoders/Decoder.cs b/ChocolArm64/Decoders/Decoder.cs
index 6b5d79f0..6a95bc28 100644
--- a/ChocolArm64/Decoders/Decoder.cs
+++ b/ChocolArm64/Decoders/Decoder.cs
@@ -19,11 +19,11 @@ namespace ChocolArm64.Decoders
             _opActivators = new ConcurrentDictionary<Type, OpActivator>();
         }
 
-        public static Block DecodeBasicBlock(MemoryManager memory, long start, ExecutionMode mode)
+        public static Block[] DecodeBasicBlock(MemoryManager memory, ulong address, ExecutionMode mode)
         {
-            Block block = new Block(start);
+            Block block = new Block(address);
 
-            FillBlock(memory, mode, block);
+            FillBlock(memory, mode, block, ulong.MaxValue);
 
             OpCode64 lastOp = block.GetLastOp();
 
@@ -35,140 +35,186 @@ namespace ChocolArm64.Decoders
                 //(which indicates that the block is a loop that jumps back to the start), and the
                 //other possible case is a jump somewhere on the middle of the block, which is
                 //also a loop, but in this case we need to split the block in half.
-                if (op.Imm == start)
+                if ((ulong)op.Imm == address)
                 {
                     block.Branch = block;
                 }
-                else if ((ulong)op.Imm > (ulong)start &&
-                         (ulong)op.Imm < (ulong)block.EndPosition)
+                else if ((ulong)op.Imm > address &&
+                         (ulong)op.Imm < block.EndAddress)
                 {
-                    Block botBlock = new Block(op.Imm);
+                    Block rightBlock = new Block((ulong)op.Imm);
 
-                    int botBlockIndex = 0;
+                    block.Split(rightBlock);
 
-                    long currPosition = start;
+                    return new Block[] { block, rightBlock };
+                }
+            }
 
-                    while ((ulong)currPosition < (ulong)op.Imm)
-                    {
-                        currPosition += block.OpCodes[botBlockIndex++].OpCodeSizeInBytes;
-                    }
+            return new Block[] { block };
+        }
 
-                    botBlock.OpCodes.AddRange(block.OpCodes);
+        public static Block[] DecodeSubroutine(MemoryManager memory, ulong address, ExecutionMode mode)
+        {
+            List<Block> blocks = new List<Block>();
 
-                    botBlock.OpCodes.RemoveRange(0, botBlockIndex);
+            Queue<Block> workQueue = new Queue<Block>();
 
-                    block.OpCodes.RemoveRange(botBlockIndex, block.OpCodes.Count - botBlockIndex);
+            Dictionary<ulong, Block> visited = new Dictionary<ulong, Block>();
 
-                    botBlock.EndPosition = block.EndPosition;
+            Block GetBlock(ulong blkAddress)
+            {
+                if (!visited.TryGetValue(blkAddress, out Block block))
+                {
+                    block = new Block(blkAddress);
 
-                    block.EndPosition = op.Imm;
+                    workQueue.Enqueue(block);
 
-                    botBlock.Branch = botBlock;
-                    block.Next      = botBlock;
+                    visited.Add(blkAddress, block);
                 }
-            }
-
-            return block;
-        }
 
-        public static Block DecodeSubroutine(MemoryManager memory, long start, ExecutionMode mode)
-        {
-            Dictionary<long, Block> visited    = new Dictionary<long, Block>();
-            Dictionary<long, Block> visitedEnd = new Dictionary<long, Block>();
+                return block;
+            }
 
-            Queue<Block> blocks = new Queue<Block>();
+            GetBlock(address);
 
-            Block Enqueue(long position)
+            while (workQueue.TryDequeue(out Block currBlock))
             {
-                if (!visited.TryGetValue(position, out Block output))
+                //Check if the current block is inside another block.
+                if (BinarySearch(blocks, currBlock.Address, out int nBlkIndex))
                 {
-                    output = new Block(position);
+                    Block nBlock = blocks[nBlkIndex];
 
-                    blocks.Enqueue(output);
+                    if (nBlock.Address == currBlock.Address)
+                    {
+                        throw new InvalidOperationException("Found duplicate block address on the list.");
+                    }
+
+                    nBlock.Split(currBlock);
+
+                    blocks.Insert(nBlkIndex + 1, currBlock);
 
-                    visited.Add(position, output);
+                    continue;
                 }
 
-                return output;
-            }
+                //If we have a block after the current one, set the limit address.
+                ulong limitAddress = ulong.MaxValue;
 
-            Block entry = Enqueue(start);
+                if (nBlkIndex != blocks.Count)
+                {
+                    Block nBlock = blocks[nBlkIndex];
 
-            while (blocks.Count > 0)
-            {
-                Block current = blocks.Dequeue();
+                    int nextIndex = nBlkIndex + 1;
+
+                    if (nBlock.Address < currBlock.Address && nextIndex < blocks.Count)
+                    {
+                        limitAddress = blocks[nextIndex].Address;
+                    }
+                    else if (nBlock.Address > currBlock.Address)
+                    {
+                        limitAddress = blocks[nBlkIndex].Address;
+                    }
+                }
 
-                FillBlock(memory, mode, current);
+                FillBlock(memory, mode, currBlock, limitAddress);
 
-                //Set child blocks. "Branch" is the block the branch instruction
-                //points to (when taken), "Next" is the block at the next address,
-                //executed when the branch is not taken. For Unconditional Branches
-                //(except BL/BLR that are sub calls) or end of executable, Next is null.
-                if (current.OpCodes.Count > 0)
+                if (currBlock.OpCodes.Count != 0)
                 {
-                    OpCode64 lastOp = current.GetLastOp();
+                    //Set child blocks. "Branch" is the block the branch instruction
+                    //points to (when taken), "Next" is the block at the next address,
+                    //executed when the branch is not taken. For Unconditional Branches
+                    //(except BL/BLR that are sub calls) or end of executable, Next is null.
+                    OpCode64 lastOp = currBlock.GetLastOp();
 
                     bool isCall = IsCall(lastOp);
 
                     if (lastOp is IOpCodeBImm op && !isCall)
                     {
-                        current.Branch = Enqueue(op.Imm);
+                        currBlock.Branch = GetBlock((ulong)op.Imm);
                     }
 
                     if (!IsUnconditionalBranch(lastOp) || isCall)
                     {
-                        current.Next = Enqueue(current.EndPosition);
+                        currBlock.Next = GetBlock(currBlock.EndAddress);
                     }
                 }
 
-                //If we have on the graph two blocks with the same end position,
-                //then we need to split the bigger block and have two small blocks,
-                //the end position of the bigger "Current" block should then be == to
-                //the position of the "Smaller" block.
-                while (visitedEnd.TryGetValue(current.EndPosition, out Block smaller))
+                //Insert the new block on the list (sorted by address).
+                if (blocks.Count != 0)
                 {
-                    if (current.Position > smaller.Position)
-                    {
-                        Block temp = smaller;
+                    Block nBlock = blocks[nBlkIndex];
 
-                        smaller = current;
-                        current = temp;
-                    }
+                    blocks.Insert(nBlkIndex + (nBlock.Address < currBlock.Address ? 1 : 0), currBlock);
+                }
+                else
+                {
+                    blocks.Add(currBlock);
+                }
+            }
 
-                    current.EndPosition = smaller.Position;
-                    current.Next        = smaller;
-                    current.Branch      = null;
+            return blocks.ToArray();
+        }
+
+        private static bool BinarySearch(List<Block> blocks, ulong address, out int index)
+        {
+            index = 0;
+
+            int left  = 0;
+            int right = blocks.Count - 1;
+
+            while (left <= right)
+            {
+                int size = right - left;
 
-                    current.OpCodes.RemoveRange(
-                        current.OpCodes.Count - smaller.OpCodes.Count,
-                        smaller.OpCodes.Count);
+                int middle = left + (size >> 1);
 
-                    visitedEnd[smaller.EndPosition] = smaller;
+                Block block = blocks[middle];
+
+                index = middle;
+
+                if (address >= block.Address && address < block.EndAddress)
+                {
+                    return true;
                 }
 
-                visitedEnd.Add(current.EndPosition, current);
+                if (address < block.Address)
+                {
+                    right = middle - 1;
+                }
+                else
+                {
+                    left = middle + 1;
+                }
             }
 
-            return entry;
+            return false;
         }
 
-        private static void FillBlock(MemoryManager memory, ExecutionMode mode, Block block)
+        private static void FillBlock(
+            MemoryManager memory,
+            ExecutionMode mode,
+            Block         block,
+            ulong         limitAddress)
         {
-            long position = block.Position;
+            ulong address = block.Address;
 
             OpCode64 opCode;
 
             do
             {
-                opCode = DecodeOpCode(memory, position, mode);
+                if (address >= limitAddress)
+                {
+                    break;
+                }
+
+                opCode = DecodeOpCode(memory, address, mode);
 
                 block.OpCodes.Add(opCode);
 
-                position += opCode.OpCodeSizeInBytes;
+                address += (ulong)opCode.OpCodeSizeInBytes;
             }
             while (!(IsBranch(opCode) || IsException(opCode)));
 
-            block.EndPosition = position;
+            block.EndAddress = address;
         }
 
         private static bool IsBranch(OpCode64 opCode)
@@ -269,9 +315,9 @@ namespace ChocolArm64.Decoders
                    opCode.Emitter == InstEmit.Und;
         }
 
-        public static OpCode64 DecodeOpCode(MemoryManager memory, long position, ExecutionMode mode)
+        public static OpCode64 DecodeOpCode(MemoryManager memory, ulong address, ExecutionMode mode)
         {
-            int opCode = memory.ReadInt32(position);
+            int opCode = memory.ReadInt32((long)address);
 
             Inst inst;
 
@@ -291,11 +337,11 @@ namespace ChocolArm64.Decoders
                 }
             }
 
-            OpCode64 decodedOpCode = new OpCode64(Inst.Undefined, position, opCode);
+            OpCode64 decodedOpCode = new OpCode64(Inst.Undefined, (long)address, opCode);
 
             if (inst.Type != null)
             {
-                decodedOpCode = MakeOpCode(inst.Type, inst, position, opCode);
+                decodedOpCode = MakeOpCode(inst.Type, inst, (long)address, opCode);
             }
 
             return decodedOpCode;