diff options
Diffstat (limited to 'ARMeilleure/Decoders')
| -rw-r--r-- | ARMeilleure/Decoders/Block.cs | 2 | ||||
| -rw-r--r-- | ARMeilleure/Decoders/Decoder.cs | 16 | ||||
| -rw-r--r-- | ARMeilleure/Decoders/Optimizations/TailCallRemover.cs | 75 |
3 files changed, 89 insertions, 4 deletions
diff --git a/ARMeilleure/Decoders/Block.cs b/ARMeilleure/Decoders/Block.cs index 3d13c2d5..d38b5a8e 100644 --- a/ARMeilleure/Decoders/Block.cs +++ b/ARMeilleure/Decoders/Block.cs @@ -11,6 +11,8 @@ namespace ARMeilleure.Decoders public Block Next { get; set; } public Block Branch { get; set; } + public bool TailCall { get; set; } + public List<OpCode> OpCodes { get; private set; } public Block() diff --git a/ARMeilleure/Decoders/Decoder.cs b/ARMeilleure/Decoders/Decoder.cs index 7cbb62e6..9675dc8d 100644 --- a/ARMeilleure/Decoders/Decoder.cs +++ b/ARMeilleure/Decoders/Decoder.cs @@ -1,3 +1,4 @@ +using ARMeilleure.Decoders.Optimizations; using ARMeilleure.Instructions; using ARMeilleure.Memory; using ARMeilleure.State; @@ -15,6 +16,9 @@ namespace ARMeilleure.Decoders // take too long to compile and use too much memory. private const int MaxInstsPerFunction = 5000; + // For lower code quality translation, we set a lower limit since we're blocking execution. + private const int MaxInstsPerFunctionLowCq = 500; + private delegate object MakeOp(InstDescriptor inst, ulong address, int opCode); private static ConcurrentDictionary<Type, MakeOp> _opActivators; @@ -33,7 +37,7 @@ namespace ARMeilleure.Decoders return new Block[] { block }; } - public static Block[] DecodeFunction(MemoryManager memory, ulong address, ExecutionMode mode) + public static Block[] DecodeFunction(MemoryManager memory, ulong address, ExecutionMode mode, bool highCq) { List<Block> blocks = new List<Block>(); @@ -43,11 +47,13 @@ namespace ARMeilleure.Decoders int opsCount = 0; + int instructionLimit = highCq ? MaxInstsPerFunction : MaxInstsPerFunctionLowCq; + Block GetBlock(ulong blkAddress) { if (!visited.TryGetValue(blkAddress, out Block block)) { - if (opsCount > MaxInstsPerFunction || !memory.IsMapped((long)blkAddress)) + if (opsCount > instructionLimit || !memory.IsMapped((long)blkAddress)) { return null; } @@ -121,7 +127,7 @@ namespace ARMeilleure.Decoders currBlock.Branch = GetBlock((ulong)op.Immediate); } - if (!IsUnconditionalBranch(lastOp) /*|| isCall*/) + if (!IsUnconditionalBranch(lastOp) || isCall) { currBlock.Next = GetBlock(currBlock.EndAddress); } @@ -140,10 +146,12 @@ namespace ARMeilleure.Decoders } } + TailCallRemover.RunPass(address, blocks); + return blocks.ToArray(); } - private static bool BinarySearch(List<Block> blocks, ulong address, out int index) + public static bool BinarySearch(List<Block> blocks, ulong address, out int index) { index = 0; diff --git a/ARMeilleure/Decoders/Optimizations/TailCallRemover.cs b/ARMeilleure/Decoders/Optimizations/TailCallRemover.cs new file mode 100644 index 00000000..2d6439ba --- /dev/null +++ b/ARMeilleure/Decoders/Optimizations/TailCallRemover.cs @@ -0,0 +1,75 @@ +using ARMeilleure.Decoders; +using System; +using System.Collections.Generic; + +namespace ARMeilleure.Decoders.Optimizations +{ + static class TailCallRemover + { + public static void RunPass(ulong entryAddress, List<Block> blocks) + { + // Detect tail calls: + // - Assume this function spans the space covered by contiguous code blocks surrounding the entry address. + // - Unconditional jump to an area outside this contiguous region will be treated as a tail call. + // - Include a small allowance for jumps outside the contiguous range. + + if (!Decoder.BinarySearch(blocks, entryAddress, out int entryBlockId)) + { + throw new InvalidOperationException("Function entry point is not contained in a block."); + } + + const ulong allowance = 4; + Block entryBlock = blocks[entryBlockId]; + int startBlockIndex = entryBlockId; + Block startBlock = entryBlock; + int endBlockIndex = entryBlockId; + Block endBlock = entryBlock; + + for (int i = entryBlockId + 1; i < blocks.Count; i++) // Search forwards. + { + Block block = blocks[i]; + if (endBlock.EndAddress < block.Address - allowance) + { + break; // End of contiguous function. + } + + endBlock = block; + endBlockIndex = i; + } + + for (int i = entryBlockId - 1; i >= 0; i--) // Search backwards. + { + Block block = blocks[i]; + if (startBlock.Address > block.EndAddress + allowance) + { + break; // End of contiguous function. + } + + startBlock = block; + startBlockIndex = i; + } + + if (startBlockIndex == 0 && endBlockIndex == blocks.Count - 1) + { + return; // Nothing to do here. + } + + // Replace all branches to blocks outside the range with null, and force a tail call. + + for (int i = startBlockIndex; i <= endBlockIndex; i++) + { + Block block = blocks[i]; + if (block.Branch != null && (block.Branch.Address > endBlock.EndAddress || block.Branch.EndAddress < startBlock.Address)) + { + block.Branch = null; + block.TailCall = true; + } + } + + // Finally, delete all blocks outside the contiguous range. + + blocks.RemoveRange(endBlockIndex + 1, (blocks.Count - endBlockIndex) - 1); + blocks.RemoveRange(0, startBlockIndex); + } + } +} |