Implement speculative translation on the CPU (#515)

* Implement speculative translation on the cpu, and change the way how branches to unknown or untranslated addresses works

* Port t0opt changes and other cleanups

* Change namespace from translation related classes to ChocolArm64.Translation, other minor tweaks

* Fix typo

* Translate higher quality code for indirect jumps aswell, and on some cases that were missed when lower quality (tier 0) code was available

* Remove debug print

* Remove direct argument passing optimization, and enable tail calls for BR instructions

* Call delegates directly with Callvirt rather than calling Execute, do not emit calls for tier 0 code

* Remove unused property

* Rename argument on ArmSubroutine delegate

1 files changed, 56 insertions, 17 deletions

diff --git a/ChocolArm64/Decoders/Decoder.cs b/ChocolArm64/Decoders/Decoder.cs
index 2b195412..6b5d79f0 100644
--- a/ChocolArm64/Decoders/Decoder.cs
+++ b/ChocolArm64/Decoders/Decoder.cs
@@ -25,14 +25,53 @@ namespace ChocolArm64.Decoders
 
             FillBlock(memory, mode, block);
 
+            OpCode64 lastOp = block.GetLastOp();
+
+            if (IsBranch(lastOp) && !IsCall(lastOp) && lastOp is IOpCodeBImm op)
+            {
+                //It's possible that the branch on this block lands on the middle of the block.
+                //This is more common on tight loops. In this case, we can improve the codegen
+                //a bit by changing the CFG and either making the branch point to the same block
+                //(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)
+                {
+                    block.Branch = block;
+                }
+                else if ((ulong)op.Imm > (ulong)start &&
+                         (ulong)op.Imm < (ulong)block.EndPosition)
+                {
+                    Block botBlock = new Block(op.Imm);
+
+                    int botBlockIndex = 0;
+
+                    long currPosition = start;
+
+                    while ((ulong)currPosition < (ulong)op.Imm)
+                    {
+                        currPosition += block.OpCodes[botBlockIndex++].OpCodeSizeInBytes;
+                    }
+
+                    botBlock.OpCodes.AddRange(block.OpCodes);
+
+                    botBlock.OpCodes.RemoveRange(0, botBlockIndex);
+
+                    block.OpCodes.RemoveRange(botBlockIndex, block.OpCodes.Count - botBlockIndex);
+
+                    botBlock.EndPosition = block.EndPosition;
+
+                    block.EndPosition = op.Imm;
+
+                    botBlock.Branch = botBlock;
+                    block.Next      = botBlock;
+                }
+            }
+
             return block;
         }
 
-        public static Block DecodeSubroutine(
-            TranslatorCache cache,
-            MemoryManager   memory,
-            long            start,
-            ExecutionMode   mode)
+        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>();
@@ -67,23 +106,16 @@ namespace ChocolArm64.Decoders
                 //(except BL/BLR that are sub calls) or end of executable, Next is null.
                 if (current.OpCodes.Count > 0)
                 {
-                    bool hasCachedSub = false;
-
                     OpCode64 lastOp = current.GetLastOp();
 
-                    if (lastOp is IOpCodeBImm op)
+                    bool isCall = IsCall(lastOp);
+
+                    if (lastOp is IOpCodeBImm op && !isCall)
                     {
-                        if (op.Emitter == InstEmit.Bl)
-                        {
-                            hasCachedSub = cache.HasSubroutine(op.Imm);
-                        }
-                        else
-                        {
-                            current.Branch = Enqueue(op.Imm);
-                        }
+                        current.Branch = Enqueue(op.Imm);
                     }
 
-                    if (!IsUnconditionalBranch(lastOp) || hasCachedSub)
+                    if (!IsUnconditionalBranch(lastOp) || isCall)
                     {
                         current.Next = Enqueue(current.EndPosition);
                     }
@@ -223,6 +255,13 @@ namespace ChocolArm64.Decoders
                    opCode is IOpCode32BReg;
         }
 
+        private static bool IsCall(OpCode64 opCode)
+        {
+            //TODO (CQ): ARM32 support.
+            return opCode.Emitter == InstEmit.Bl ||
+                   opCode.Emitter == InstEmit.Blr;
+        }
+
         private static bool IsException(OpCode64 opCode)
         {
             return opCode.Emitter == InstEmit.Brk ||