diff options
Diffstat (limited to 'ChocolArm64/Translation/RegisterUsage.cs')
| -rw-r--r-- | ChocolArm64/Translation/RegisterUsage.cs | 299 |
1 files changed, 95 insertions, 204 deletions
diff --git a/ChocolArm64/Translation/RegisterUsage.cs b/ChocolArm64/Translation/RegisterUsage.cs index 2e6829d5..fe0c8659 100644 --- a/ChocolArm64/Translation/RegisterUsage.cs +++ b/ChocolArm64/Translation/RegisterUsage.cs @@ -1,269 +1,160 @@ -using System; +using ChocolArm64.IntermediateRepresentation; +using ChocolArm64.State; using System.Collections.Generic; namespace ChocolArm64.Translation { class RegisterUsage { - public const long CallerSavedIntRegistersMask = 0x7fL << 9; - public const long PStateNzcvFlagsMask = 0xfL << 60; + private const long CallerSavedIntRegistersMask = 0x7fL << 9; + private const long PStateNzcvFlagsMask = 0xfL << 60; - public const long CallerSavedVecRegistersMask = 0xffffL << 16; + private const long CallerSavedVecRegistersMask = 0xffffL << 16; - private class PathIo + private RegisterMask[] _inputs; + private RegisterMask[] _outputs; + + public RegisterUsage(BasicBlock entryBlock, int blocksCount) { - private Dictionary<ILBlock, long> _allInputs; - private Dictionary<ILBlock, long> _cmnOutputs; + _inputs = new RegisterMask[blocksCount]; + _outputs = new RegisterMask[blocksCount]; - private long _allOutputs; + HashSet<BasicBlock> visited = new HashSet<BasicBlock>(); - public PathIo() - { - _allInputs = new Dictionary<ILBlock, long>(); - _cmnOutputs = new Dictionary<ILBlock, long>(); - } + Stack<BasicBlock> blockStack = new Stack<BasicBlock>(); + + List<BasicBlock> postOrderBlocks = new List<BasicBlock>(blocksCount); + + visited.Add(entryBlock); - public void Set(ILBlock entry, long inputs, long outputs) + blockStack.Push(entryBlock); + + while (blockStack.TryPop(out BasicBlock block)) { - if (!_allInputs.TryAdd(entry, inputs)) + if (block.Next != null && visited.Add(block.Next)) { - _allInputs[entry] |= inputs; + blockStack.Push(block); + blockStack.Push(block.Next); } - - if (!_cmnOutputs.TryAdd(entry, outputs)) + else if (block.Branch != null && visited.Add(block.Branch)) { - _cmnOutputs[entry] &= outputs; + blockStack.Push(block); + blockStack.Push(block.Branch); } - - _allOutputs |= outputs; - } - - public long GetInputs(ILBlock entry) - { - if (_allInputs.TryGetValue(entry, out long inputs)) + else { - //We also need to read the registers that may not be written - //by all paths that can reach a exit point, to ensure that - //the local variable will not remain uninitialized depending - //on the flow path taken. - return inputs | (_allOutputs & ~_cmnOutputs[entry]); + postOrderBlocks.Add(block); } - - return 0; } - public long GetOutputs() - { - return _allOutputs; - } - } - - private Dictionary<ILBlock, PathIo> _intPaths; - private Dictionary<ILBlock, PathIo> _vecPaths; - - private struct BlockIo : IEquatable<BlockIo> - { - public ILBlock Block { get; } - public ILBlock Entry { get; } - - public long IntInputs { get; set; } - public long VecInputs { get; set; } - public long IntOutputs { get; set; } - public long VecOutputs { get; set; } + RegisterMask[] cmnOutputMasks = new RegisterMask[blocksCount]; - public BlockIo(ILBlock block, ILBlock entry) - { - Block = block; - Entry = entry; + bool modified; - IntInputs = IntOutputs = 0; - VecInputs = VecOutputs = 0; - } + bool firstPass = true; - public BlockIo( - ILBlock block, - ILBlock entry, - long intInputs, - long vecInputs, - long intOutputs, - long vecOutputs) : this(block, entry) + do { - IntInputs = intInputs; - VecInputs = vecInputs; - IntOutputs = intOutputs; - VecOutputs = vecOutputs; - } + modified = false; - public override bool Equals(object obj) - { - if (!(obj is BlockIo other)) + for (int blkIndex = postOrderBlocks.Count - 1; blkIndex >= 0; blkIndex--) { - return false; - } + BasicBlock block = postOrderBlocks[blkIndex]; - return Equals(other); - } + if (block.Predecessors.Count != 0 && !block.HasStateLoad) + { + BasicBlock predecessor = block.Predecessors[0]; - public bool Equals(BlockIo other) - { - return other.Block == Block && - other.Entry == Entry && - other.IntInputs == IntInputs && - other.VecInputs == VecInputs && - other.IntOutputs == IntOutputs && - other.VecOutputs == VecOutputs; - } + RegisterMask cmnOutputs = predecessor.RegOutputs | cmnOutputMasks[predecessor.Index]; - public override int GetHashCode() - { - return HashCode.Combine(Block, Entry, IntInputs, VecInputs, IntOutputs, VecOutputs); - } + RegisterMask outputs = _outputs[predecessor.Index]; - public static bool operator ==(BlockIo lhs, BlockIo rhs) - { - return lhs.Equals(rhs); - } + for (int pIndex = 1; pIndex < block.Predecessors.Count; pIndex++) + { + predecessor = block.Predecessors[pIndex]; - public static bool operator !=(BlockIo lhs, BlockIo rhs) - { - return !(lhs == rhs); - } - } + cmnOutputs &= predecessor.RegOutputs | cmnOutputMasks[predecessor.Index]; - public RegisterUsage() - { - _intPaths = new Dictionary<ILBlock, PathIo>(); - _vecPaths = new Dictionary<ILBlock, PathIo>(); - } + outputs |= _outputs[predecessor.Index]; + } - public void BuildUses(ILBlock entry) - { - //This will go through all possible paths on the graph, - //and store all inputs/outputs for each block. A register - //that was previously written to already is not considered an input. - //When a block can be reached by more than one path, then the - //output from all paths needs to be set for this block, and - //only outputs present in all of the parent blocks can be considered - //when doing input elimination. Each block chain has a entry, that's where - //the code starts executing. They are present on the subroutine start point, - //and on call return points too (address written to X30 by BL). - HashSet<BlockIo> visited = new HashSet<BlockIo>(); - - Queue<BlockIo> unvisited = new Queue<BlockIo>(); - - void Enqueue(BlockIo block) - { - if (visited.Add(block)) - { - unvisited.Enqueue(block); - } - } + _inputs[block.Index] |= outputs & ~cmnOutputs; - Enqueue(new BlockIo(entry, entry)); + if (!firstPass) + { + cmnOutputs &= cmnOutputMasks[block.Index]; + } - while (unvisited.Count > 0) - { - BlockIo current = unvisited.Dequeue(); + if (Exchange(cmnOutputMasks, block.Index, cmnOutputs)) + { + modified = true; + } - current.IntInputs |= current.Block.IntInputs & ~current.IntOutputs; - current.VecInputs |= current.Block.VecInputs & ~current.VecOutputs; - current.IntOutputs |= current.Block.IntOutputs; - current.VecOutputs |= current.Block.VecOutputs; + outputs |= block.RegOutputs; - //Check if this is a exit block - //(a block that returns or calls another sub). - if ((current.Block.Next == null && - current.Block.Branch == null) || current.Block.HasStateStore) - { - if (!_intPaths.TryGetValue(current.Block, out PathIo intPath)) - { - _intPaths.Add(current.Block, intPath = new PathIo()); + if (Exchange(_outputs, block.Index, _outputs[block.Index] | outputs)) + { + modified = true; + } } - - if (!_vecPaths.TryGetValue(current.Block, out PathIo vecPath)) + else if (Exchange(_outputs, block.Index, block.RegOutputs)) { - _vecPaths.Add(current.Block, vecPath = new PathIo()); + modified = true; } - - intPath.Set(current.Entry, current.IntInputs, current.IntOutputs); - vecPath.Set(current.Entry, current.VecInputs, current.VecOutputs); } - void EnqueueFromCurrent(ILBlock block, bool retTarget) + firstPass = false; + } + while (modified); + + do + { + modified = false; + + for (int blkIndex = 0; blkIndex < postOrderBlocks.Count; blkIndex++) { - BlockIo blockIo; + BasicBlock block = postOrderBlocks[blkIndex]; + + RegisterMask inputs = block.RegInputs; - if (retTarget) + if (block.Next != null) { - blockIo = new BlockIo(block, block); + inputs |= _inputs[block.Next.Index]; } - else + + if (block.Branch != null) { - blockIo = new BlockIo( - block, - current.Entry, - current.IntInputs, - current.VecInputs, - current.IntOutputs, - current.VecOutputs); + inputs |= _inputs[block.Branch.Index]; } - Enqueue(blockIo); - } + inputs &= ~cmnOutputMasks[block.Index]; - if (current.Block.Next != null) - { - EnqueueFromCurrent(current.Block.Next, current.Block.HasStateStore); - } - - if (current.Block.Branch != null) - { - EnqueueFromCurrent(current.Block.Branch, false); + if (Exchange(_inputs, block.Index, _inputs[block.Index] | inputs)) + { + modified = true; + } } } + while (modified); } - public long GetIntInputs(ILBlock entry) => GetInputsImpl(entry, _intPaths.Values); - public long GetVecInputs(ILBlock entry) => GetInputsImpl(entry, _vecPaths.Values); - - private long GetInputsImpl(ILBlock entry, IEnumerable<PathIo> values) + private static bool Exchange(RegisterMask[] masks, int blkIndex, RegisterMask value) { - long inputs = 0; + RegisterMask oldValue = masks[blkIndex]; - foreach (PathIo path in values) - { - inputs |= path.GetInputs(entry); - } + masks[blkIndex] = value; - return inputs; + return oldValue != value; } - public long GetIntNotInputs(ILBlock entry) => GetNotInputsImpl(entry, _intPaths.Values); - public long GetVecNotInputs(ILBlock entry) => GetNotInputsImpl(entry, _vecPaths.Values); - - private long GetNotInputsImpl(ILBlock entry, IEnumerable<PathIo> values) - { - //Returns a mask with registers that are written to - //before being read. Only those registers that are - //written in all paths, and is not read before being - //written to on those paths, should be set on the mask. - long mask = -1L; - - foreach (PathIo path in values) - { - mask &= path.GetOutputs() & ~path.GetInputs(entry); - } - - return mask; - } + public RegisterMask GetInputs(BasicBlock entryBlock) => _inputs[entryBlock.Index]; - public long GetIntOutputs(ILBlock block) => _intPaths[block].GetOutputs(); - public long GetVecOutputs(ILBlock block) => _vecPaths[block].GetOutputs(); + public RegisterMask GetOutputs(BasicBlock block) => _outputs[block.Index]; - public static long ClearCallerSavedIntRegs(long mask, bool isAarch64) + public static long ClearCallerSavedIntRegs(long mask, ExecutionMode mode) { //TODO: ARM32 support. - if (isAarch64) + if (mode == ExecutionMode.Aarch64) { mask &= ~(CallerSavedIntRegistersMask | PStateNzcvFlagsMask); } @@ -271,10 +162,10 @@ namespace ChocolArm64.Translation return mask; } - public static long ClearCallerSavedVecRegs(long mask, bool isAarch64) + public static long ClearCallerSavedVecRegs(long mask, ExecutionMode mode) { //TODO: ARM32 support. - if (isAarch64) + if (mode == ExecutionMode.Aarch64) { mask &= ~CallerSavedVecRegistersMask; } |