diff options
| author | gdkchan <gab.dark.100@gmail.com> | 2019-08-08 15:56:22 -0300 |
|---|---|---|
| committer | emmauss <emmausssss@gmail.com> | 2019-08-08 21:56:22 +0300 |
| commit | a731ab3a2aad56e6ceb8b4e2444a61353246295c (patch) | |
| tree | c7f13f51bfec6b19431e62167811ae31e9d2fea9 /ARMeilleure/Decoders/Decoder.cs | |
| parent | 1ba58e9942e54175e3f3a0e1d57a48537f4888b1 (diff) | |
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
Diffstat (limited to 'ARMeilleure/Decoders/Decoder.cs')
| -rw-r--r-- | ARMeilleure/Decoders/Decoder.cs | 351 |
1 files changed, 351 insertions, 0 deletions
diff --git a/ARMeilleure/Decoders/Decoder.cs b/ARMeilleure/Decoders/Decoder.cs new file mode 100644 index 00000000..2311e9e9 --- /dev/null +++ b/ARMeilleure/Decoders/Decoder.cs @@ -0,0 +1,351 @@ +using ARMeilleure.Instructions; +using ARMeilleure.Memory; +using ARMeilleure.State; +using System; +using System.Collections.Concurrent; +using System.Collections.Generic; +using System.Reflection.Emit; + +namespace ARMeilleure.Decoders +{ + static class Decoder + { + private delegate object MakeOp(InstDescriptor inst, ulong address, int opCode); + + private static ConcurrentDictionary<Type, MakeOp> _opActivators; + + static Decoder() + { + _opActivators = new ConcurrentDictionary<Type, MakeOp>(); + } + + public static Block[] DecodeBasicBlock(MemoryManager memory, ulong address, ExecutionMode mode) + { + Block block = new Block(address); + + FillBlock(memory, mode, block, ulong.MaxValue); + + return new Block[] { block }; + } + + public static Block[] DecodeFunction(MemoryManager memory, ulong address, ExecutionMode mode) + { + List<Block> blocks = new List<Block>(); + + Queue<Block> workQueue = new Queue<Block>(); + + Dictionary<ulong, Block> visited = new Dictionary<ulong, Block>(); + + Block GetBlock(ulong blkAddress) + { + if (!visited.TryGetValue(blkAddress, out Block block)) + { + block = new Block(blkAddress); + + workQueue.Enqueue(block); + + visited.Add(blkAddress, block); + } + + return block; + } + + GetBlock(address); + + while (workQueue.TryDequeue(out Block currBlock)) + { + // Check if the current block is inside another block. + if (BinarySearch(blocks, currBlock.Address, out int nBlkIndex)) + { + Block nBlock = blocks[nBlkIndex]; + + if (nBlock.Address == currBlock.Address) + { + throw new InvalidOperationException("Found duplicate block address on the list."); + } + + nBlock.Split(currBlock); + + blocks.Insert(nBlkIndex + 1, currBlock); + + continue; + } + + // If we have a block after the current one, set the limit address. + ulong limitAddress = ulong.MaxValue; + + if (nBlkIndex != blocks.Count) + { + Block nBlock = blocks[nBlkIndex]; + + 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, currBlock, limitAddress); + + if (currBlock.OpCodes.Count != 0) + { + // 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. + OpCode lastOp = currBlock.GetLastOp(); + + bool isCall = IsCall(lastOp); + + if (lastOp is IOpCodeBImm op && !isCall) + { + currBlock.Branch = GetBlock((ulong)op.Immediate); + } + + if (!IsUnconditionalBranch(lastOp) /*|| isCall*/) + { + currBlock.Next = GetBlock(currBlock.EndAddress); + } + } + + // Insert the new block on the list (sorted by address). + if (blocks.Count != 0) + { + Block nBlock = blocks[nBlkIndex]; + + blocks.Insert(nBlkIndex + (nBlock.Address < currBlock.Address ? 1 : 0), currBlock); + } + else + { + blocks.Add(currBlock); + } + } + + 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; + + int middle = left + (size >> 1); + + Block block = blocks[middle]; + + index = middle; + + if (address >= block.Address && address < block.EndAddress) + { + return true; + } + + if (address < block.Address) + { + right = middle - 1; + } + else + { + left = middle + 1; + } + } + + return false; + } + + private static void FillBlock( + MemoryManager memory, + ExecutionMode mode, + Block block, + ulong limitAddress) + { + ulong address = block.Address; + + OpCode opCode; + + do + { + if (address >= limitAddress) + { + break; + } + + opCode = DecodeOpCode(memory, address, mode); + + block.OpCodes.Add(opCode); + + address += (ulong)opCode.OpCodeSizeInBytes; + } + while (!(IsBranch(opCode) || IsException(opCode))); + + block.EndAddress = address; + } + + private static bool IsBranch(OpCode opCode) + { + return opCode is OpCodeBImm || + opCode is OpCodeBReg || IsAarch32Branch(opCode); + } + + private static bool IsUnconditionalBranch(OpCode opCode) + { + return opCode is OpCodeBImmAl || + opCode is OpCodeBReg || IsAarch32UnconditionalBranch(opCode); + } + + private static bool IsAarch32UnconditionalBranch(OpCode opCode) + { + if (!(opCode is OpCode32 op)) + { + return false; + } + + // Note: On ARM32, most instructions have conditional execution, + // so there's no "Always" (unconditional) branch like on ARM64. + // We need to check if the condition is "Always" instead. + return IsAarch32Branch(op) && op.Cond >= Condition.Al; + } + + private static bool IsAarch32Branch(OpCode opCode) + { + // Note: On ARM32, most ALU operations can write to R15 (PC), + // so we must consider such operations as a branch in potential aswell. + if (opCode is IOpCode32Alu opAlu && opAlu.Rd == RegisterAlias.Aarch32Pc) + { + return true; + } + + // Same thing for memory operations. We have the cases where PC is a target + // register (Rt == 15 or (mask & (1 << 15)) != 0), and cases where there is + // a write back to PC (wback == true && Rn == 15), however the later may + // be "undefined" depending on the CPU, so compilers should not produce that. + if (opCode is IOpCode32Mem || opCode is IOpCode32MemMult) + { + int rt, rn; + + bool wBack, isLoad; + + if (opCode is IOpCode32Mem opMem) + { + rt = opMem.Rt; + rn = opMem.Rn; + wBack = opMem.WBack; + isLoad = opMem.IsLoad; + + // For the dual load, we also need to take into account the + // case were Rt2 == 15 (PC). + if (rt == 14 && opMem.Instruction.Name == InstName.Ldrd) + { + rt = RegisterAlias.Aarch32Pc; + } + } + else if (opCode is IOpCode32MemMult opMemMult) + { + const int pcMask = 1 << RegisterAlias.Aarch32Pc; + + rt = (opMemMult.RegisterMask & pcMask) != 0 ? RegisterAlias.Aarch32Pc : 0; + rn = opMemMult.Rn; + wBack = opMemMult.PostOffset != 0; + isLoad = opMemMult.IsLoad; + } + else + { + throw new NotImplementedException($"The type \"{opCode.GetType().Name}\" is not implemented on the decoder."); + } + + if ((rt == RegisterAlias.Aarch32Pc && isLoad) || + (rn == RegisterAlias.Aarch32Pc && wBack)) + { + return true; + } + } + + // Explicit branch instructions. + return opCode is IOpCode32BImm || + opCode is IOpCode32BReg; + } + + private static bool IsCall(OpCode opCode) + { + // TODO (CQ): ARM32 support. + return opCode.Instruction.Name == InstName.Bl || + opCode.Instruction.Name == InstName.Blr; + } + + private static bool IsException(OpCode opCode) + { + return opCode.Instruction.Name == InstName.Brk || + opCode.Instruction.Name == InstName.Svc || + opCode.Instruction.Name == InstName.Und; + } + + public static OpCode DecodeOpCode(MemoryManager memory, ulong address, ExecutionMode mode) + { + int opCode = memory.ReadInt32((long)address); + + InstDescriptor inst; + + Type type; + + if (mode == ExecutionMode.Aarch64) + { + (inst, type) = OpCodeTable.GetInstA64(opCode); + } + else + { + if (mode == ExecutionMode.Aarch32Arm) + { + (inst, type) = OpCodeTable.GetInstA32(opCode); + } + else /* if (mode == ExecutionMode.Aarch32Thumb) */ + { + (inst, type) = OpCodeTable.GetInstT32(opCode); + } + } + + if (type != null) + { + return MakeOpCode(inst, type, address, opCode); + } + else + { + return new OpCode(inst, address, opCode); + } + } + + private static OpCode MakeOpCode(InstDescriptor inst, Type type, ulong address, int opCode) + { + MakeOp createInstance = _opActivators.GetOrAdd(type, CacheOpActivator); + + return (OpCode)createInstance(inst, address, opCode); + } + + private static MakeOp CacheOpActivator(Type type) + { + Type[] argTypes = new Type[] { typeof(InstDescriptor), typeof(ulong), typeof(int) }; + + DynamicMethod mthd = new DynamicMethod($"Make{type.Name}", type, argTypes); + + ILGenerator generator = mthd.GetILGenerator(); + + generator.Emit(OpCodes.Ldarg_0); + generator.Emit(OpCodes.Ldarg_1); + generator.Emit(OpCodes.Ldarg_2); + generator.Emit(OpCodes.Newobj, type.GetConstructor(argTypes)); + generator.Emit(OpCodes.Ret); + + return (MakeOp)mthd.CreateDelegate(typeof(MakeOp)); + } + } +}
\ No newline at end of file |