diff options
Diffstat (limited to 'ARMeilleure/CodeGen/RegisterAllocators')
4 files changed, 165 insertions, 158 deletions
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/CopyResolver.cs b/ARMeilleure/CodeGen/RegisterAllocators/CopyResolver.cs index 417f3bae..cc731b74 100644 --- a/ARMeilleure/CodeGen/RegisterAllocators/CopyResolver.cs +++ b/ARMeilleure/CodeGen/RegisterAllocators/CopyResolver.cs @@ -1,9 +1,8 @@ using ARMeilleure.IntermediateRepresentation; using System; using System.Collections.Generic; - -using static ARMeilleure.IntermediateRepresentation.OperandHelper; -using static ARMeilleure.IntermediateRepresentation.OperationHelper; +using static ARMeilleure.IntermediateRepresentation.Operand.Factory; +using static ARMeilleure.IntermediateRepresentation.Operation.Factory; namespace ARMeilleure.CodeGen.RegisterAllocators { @@ -210,7 +209,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators Operand register = GetRegister(left.Register, type); - _spillQueue.Enqueue(Operation(Instruction.Spill, null, offset, register)); + _spillQueue.Enqueue(Operation(Instruction.Spill, default, offset, register)); HasCopy = true; } diff --git a/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs index 2f68c43f..7b339efb 100644 --- a/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs +++ b/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs @@ -1,11 +1,10 @@ using ARMeilleure.IntermediateRepresentation; using ARMeilleure.Translation; -using System.Collections.Generic; +using System; using System.Diagnostics; using System.Numerics; - -using static ARMeilleure.IntermediateRepresentation.OperandHelper; -using static ARMeilleure.IntermediateRepresentation.OperationHelper; +using static ARMeilleure.IntermediateRepresentation.Operand.Factory; +using static ARMeilleure.IntermediateRepresentation.Operation.Factory; namespace ARMeilleure.CodeGen.RegisterAllocators { @@ -29,19 +28,14 @@ namespace ARMeilleure.CodeGen.RegisterAllocators } } - private class LocalInfo + private struct LocalInfo { - public int Uses { get; set; } - public int UseCount { get; set; } - - public bool PreAllocated { get; set; } - public int Register { get; set; } - public int SpillOffset { get; set; } - + public int Uses { get; set; } + public int UsesAllocated { get; set; } + public int Register { get; set; } + public int SpillOffset { get; set; } public int Sequence { get; set; } - public Operand Temp { get; set; } - public OperandType Type { get; } private int _first; @@ -49,13 +43,21 @@ namespace ARMeilleure.CodeGen.RegisterAllocators public bool IsBlockLocal => _first == _last; - public LocalInfo(OperandType type, int uses) + public LocalInfo(OperandType type, int uses, int blkIndex) { Uses = uses; Type = type; + UsesAllocated = 0; + Register = 0; + SpillOffset = 0; + Sequence = 0; + Temp = default; + _first = -1; _last = -1; + + SetBlockIndex(blkIndex); } public void SetBlockIndex(int blkIndex) @@ -72,10 +74,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators } } - public AllocationResult RunPass( - ControlFlowGraph cfg, - StackAllocator stackAlloc, - RegisterMasks regMasks) + public AllocationResult RunPass(ControlFlowGraph cfg, StackAllocator stackAlloc, RegisterMasks regMasks) { int intUsedRegisters = 0; int vecUsedRegisters = 0; @@ -84,9 +83,33 @@ namespace ARMeilleure.CodeGen.RegisterAllocators int vecFreeRegisters = regMasks.VecAvailableRegisters; var blockInfo = new BlockInfo[cfg.Blocks.Count]; + var localInfo = new LocalInfo[cfg.Blocks.Count * 3]; + int localInfoCount = 0; + + // The "visited" state is stored in the MSB of the local's value. + const ulong VisitedMask = 1ul << 63; + + bool IsVisited(Operand local) + { + return (local.GetValueUnsafe() & VisitedMask) != 0; + } + + void SetVisited(Operand local) + { + local.GetValueUnsafe() |= VisitedMask | (uint)++localInfoCount; + } + + ref LocalInfo GetLocalInfo(Operand local) + { + Debug.Assert(local.Kind == OperandKind.LocalVariable); + + if (!IsVisited(local)) + { + throw new InvalidOperationException("Local was not visisted yet. Used before defined?"); + } - var locInfo = new List<LocalInfo>(); - var locVisited = new HashSet<Operand>(); + return ref localInfo[(uint)local.GetValueUnsafe() - 1]; + } for (int index = cfg.PostOrderBlocks.Length - 1; index >= 0; index--) { @@ -97,59 +120,58 @@ namespace ARMeilleure.CodeGen.RegisterAllocators bool hasCall = false; - for (Node node = block.Operations.First; node != null; node = node.ListNext) + for (Operation node = block.Operations.First; node != default; node = node.ListNext) { - if (node is Operation operation && operation.Instruction == Instruction.Call) + if (node.Instruction == Instruction.Call) { hasCall = true; } - for (int srcIndex = 0; srcIndex < node.SourcesCount; srcIndex++) + for (int i = 0; i < node.SourcesCount; i++) { - Operand source = node.GetSource(srcIndex); + Operand source = node.GetSource(i); if (source.Kind == OperandKind.LocalVariable) { - locInfo[source.GetLocalNumber() - 1].SetBlockIndex(block.Index); + GetLocalInfo(source).SetBlockIndex(block.Index); } else if (source.Kind == OperandKind.Memory) { - MemoryOperand memOp = (MemoryOperand)source; + MemoryOperand memOp = source.GetMemory(); - if (memOp.BaseAddress != null) + if (memOp.BaseAddress != default) { - locInfo[memOp.BaseAddress.GetLocalNumber() - 1].SetBlockIndex(block.Index); + GetLocalInfo(memOp.BaseAddress).SetBlockIndex(block.Index); } - if (memOp.Index != null) + if (memOp.Index != default) { - locInfo[memOp.Index.GetLocalNumber() - 1].SetBlockIndex(block.Index); + GetLocalInfo(memOp.Index).SetBlockIndex(block.Index); } } } - for (int dstIndex = 0; dstIndex < node.DestinationsCount; dstIndex++) + for (int i = 0; i < node.DestinationsCount; i++) { - Operand dest = node.GetDestination(dstIndex); + Operand dest = node.GetDestination(i); if (dest.Kind == OperandKind.LocalVariable) { - LocalInfo info; - - if (!locVisited.Add(dest)) + if (IsVisited(dest)) { - info = locInfo[dest.GetLocalNumber() - 1]; + GetLocalInfo(dest).SetBlockIndex(block.Index); } else { - dest.NumberLocal(locInfo.Count + 1); + SetVisited(dest); - info = new LocalInfo(dest.Type, UsesCount(dest)); + if (localInfoCount > localInfo.Length) + { + Array.Resize(ref localInfo, localInfoCount * 2); + } - locInfo.Add(info); + GetLocalInfo(dest) = new LocalInfo(dest.Type, UsesCount(dest), block.Index); } - - info.SetBlockIndex(block.Index); } else if (dest.Kind == OperandKind.Register) { @@ -192,42 +214,26 @@ namespace ARMeilleure.CodeGen.RegisterAllocators intLocalFreeRegisters &= ~(intSpillTempRegisters | intCallerSavedRegisters); vecLocalFreeRegisters &= ~(vecSpillTempRegisters | vecCallerSavedRegisters); - for (Node node = block.Operations.First; node != null; node = node.ListNext) + for (Operation node = block.Operations.First; node != default; node = node.ListNext) { int intLocalUse = 0; int vecLocalUse = 0; - void AllocateRegister(Operand source, MemoryOperand memOp, int srcIndex) + Operand AllocateRegister(Operand local) { - LocalInfo info = locInfo[source.GetLocalNumber() - 1]; + ref LocalInfo info = ref GetLocalInfo(local); - info.UseCount++; + info.UsesAllocated++; - Debug.Assert(info.UseCount <= info.Uses); + Debug.Assert(info.UsesAllocated <= info.Uses); if (info.Register != -1) { - Operand reg = Register(info.Register, source.Type.ToRegisterType(), source.Type); - - if (memOp != null) - { - if (srcIndex == 0) - { - memOp.BaseAddress = reg; - } - else /* if (srcIndex == 1) */ - { - memOp.Index = reg; - } - } - else - { - node.SetSource(srcIndex, reg); - } + Operand reg = Register(info.Register, local.Type.ToRegisterType(), local.Type); - if (info.UseCount == info.Uses && !info.PreAllocated) + if (info.UsesAllocated == info.Uses) { - if (source.Type.IsInteger()) + if (local.Type.IsInteger()) { intLocalFreeRegisters |= 1 << info.Register; } @@ -236,72 +242,80 @@ namespace ARMeilleure.CodeGen.RegisterAllocators vecLocalFreeRegisters |= 1 << info.Register; } } - } - else if (node is Operation operation && operation.Instruction == Instruction.Copy) - { - Operation fillOp = Operation(Instruction.Fill, node.Destination, Const(info.SpillOffset)); - block.Operations.AddBefore(node, fillOp); - block.Operations.Remove(node); - - node = fillOp; + return reg; } else { Operand temp = info.Temp; - if (temp == null || info.Sequence != sequence) + if (temp == default || info.Sequence != sequence) { - temp = source.Type.IsInteger() - ? GetSpillTemp(source, intSpillTempRegisters, ref intLocalUse) - : GetSpillTemp(source, vecSpillTempRegisters, ref vecLocalUse); + temp = local.Type.IsInteger() + ? GetSpillTemp(local, intSpillTempRegisters, ref intLocalUse) + : GetSpillTemp(local, vecSpillTempRegisters, ref vecLocalUse); info.Sequence = sequence; info.Temp = temp; } - if (memOp != null) - { - if (srcIndex == 0) - { - memOp.BaseAddress = temp; - } - else /* if (srcIndex == 1) */ - { - memOp.Index = temp; - } - } - else - { - node.SetSource(srcIndex, temp); - } - Operation fillOp = Operation(Instruction.Fill, temp, Const(info.SpillOffset)); block.Operations.AddBefore(node, fillOp); + + return temp; } } - for (int srcIndex = 0; srcIndex < node.SourcesCount; srcIndex++) + bool folded = false; + + // If operation is a copy of a local and that local is living on the stack, we turn the copy into + // a fill, instead of inserting a fill before it. + if (node.Instruction == Instruction.Copy) { - Operand source = node.GetSource(srcIndex); + Operand source = node.GetSource(0); if (source.Kind == OperandKind.LocalVariable) { - AllocateRegister(source, null, srcIndex); + ref LocalInfo info = ref GetLocalInfo(source); + + if (info.Register == -1) + { + Operation fillOp = Operation(Instruction.Fill, node.Destination, Const(info.SpillOffset)); + + block.Operations.AddBefore(node, fillOp); + block.Operations.Remove(node); + + node = fillOp; + + folded = true; + } } - else if (source.Kind == OperandKind.Memory) + } + + if (!folded) + { + for (int i = 0; i < node.SourcesCount; i++) { - MemoryOperand memOp = (MemoryOperand)source; + Operand source = node.GetSource(i); - if (memOp.BaseAddress != null) + if (source.Kind == OperandKind.LocalVariable) { - AllocateRegister(memOp.BaseAddress, memOp, 0); + node.SetSource(i, AllocateRegister(source)); } - - if (memOp.Index != null) + else if (source.Kind == OperandKind.Memory) { - AllocateRegister(memOp.Index, memOp, 1); + MemoryOperand memOp = source.GetMemory(); + + if (memOp.BaseAddress != default) + { + memOp.BaseAddress = AllocateRegister(memOp.BaseAddress); + } + + if (memOp.Index != default) + { + memOp.Index = AllocateRegister(memOp.Index); + } } } } @@ -309,18 +323,18 @@ namespace ARMeilleure.CodeGen.RegisterAllocators int intLocalAsg = 0; int vecLocalAsg = 0; - for (int dstIndex = 0; dstIndex < node.DestinationsCount; dstIndex++) + for (int i = 0; i < node.DestinationsCount; i++) { - Operand dest = node.GetDestination(dstIndex); + Operand dest = node.GetDestination(i); if (dest.Kind != OperandKind.LocalVariable) { continue; } - LocalInfo info = locInfo[dest.GetLocalNumber() - 1]; + ref LocalInfo info = ref GetLocalInfo(dest); - if (info.UseCount == 0 && !info.PreAllocated) + if (info.UsesAllocated == 0) { int mask = dest.Type.IsInteger() ? intLocalFreeRegisters @@ -350,19 +364,19 @@ namespace ARMeilleure.CodeGen.RegisterAllocators } } - info.UseCount++; + info.UsesAllocated++; - Debug.Assert(info.UseCount <= info.Uses); + Debug.Assert(info.UsesAllocated <= info.Uses); if (info.Register != -1) { - node.SetDestination(dstIndex, Register(info.Register, dest.Type.ToRegisterType(), dest.Type)); + node.SetDestination(i, Register(info.Register, dest.Type.ToRegisterType(), dest.Type)); } else { Operand temp = info.Temp; - if (temp == null || info.Sequence != sequence) + if (temp == default || info.Sequence != sequence) { temp = dest.Type.IsInteger() ? GetSpillTemp(dest, intSpillTempRegisters, ref intLocalAsg) @@ -372,9 +386,9 @@ namespace ARMeilleure.CodeGen.RegisterAllocators info.Temp = temp; } - node.SetDestination(dstIndex, temp); + node.SetDestination(i, temp); - Operation spillOp = Operation(Instruction.Spill, null, Const(info.SpillOffset), temp); + Operation spillOp = Operation(Instruction.Spill, default, Const(info.SpillOffset), temp); block.Operations.AddAfter(node, spillOp); @@ -435,7 +449,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators private static int UsesCount(Operand local) { - return local.Assignments.Count + local.Uses.Count; + return local.AssignmentsCount + local.UsesCount; } } }
\ No newline at end of file diff --git a/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs index 88adeeb0..fd1420a2 100644 --- a/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs +++ b/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs @@ -29,11 +29,11 @@ namespace ARMeilleure.CodeGen.RegisterAllocators private LiveInterval[] _parentIntervals; - private List<(IntrusiveList<Node>, Node)> _operationNodes; + private List<(IntrusiveList<Operation>, Operation)> _operationNodes; private int _operationsCount; - private class AllocationContext : IDisposable + private class AllocationContext { public RegisterMasks Masks { get; } @@ -50,10 +50,8 @@ namespace ARMeilleure.CodeGen.RegisterAllocators StackAlloc = stackAlloc; Masks = masks; - BitMapPool.PrepareBitMapPool(); - - Active = BitMapPool.Allocate(intervalsCount); - Inactive = BitMapPool.Allocate(intervalsCount); + Active = new BitMap(Allocators.Default, intervalsCount); + Inactive = new BitMap(Allocators.Default, intervalsCount); } public void MoveActiveToInactive(int bit) @@ -72,11 +70,6 @@ namespace ARMeilleure.CodeGen.RegisterAllocators dest.Set(bit); } - - public void Dispose() - { - BitMapPool.ResetBitMapPool(); - } } public AllocationResult RunPass( @@ -86,7 +79,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators { NumberLocals(cfg); - using AllocationContext context = new AllocationContext(stackAlloc, regMasks, _intervals.Count); + var context = new AllocationContext(stackAlloc, regMasks, _intervals.Count); BuildIntervals(cfg, context); @@ -588,7 +581,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators int splitPosition = kv.Key; - (IntrusiveList<Node> nodes, Node node) = GetOperationNode(splitPosition); + (IntrusiveList<Operation> nodes, Operation node) = GetOperationNode(splitPosition); Operation[] sequence = copyResolver.Sequence(); @@ -621,9 +614,9 @@ namespace ARMeilleure.CodeGen.RegisterAllocators continue; } - bool hasSingleOrNoSuccessor = block.SuccessorCount <= 1; + bool hasSingleOrNoSuccessor = block.SuccessorsCount <= 1; - for (int i = 0; i < block.SuccessorCount; i++) + for (int i = 0; i < block.SuccessorsCount; i++) { BasicBlock successor = block.GetSuccessor(i); @@ -677,7 +670,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators { successor.Operations.AddFirst(sequence[0]); - Node prependNode = sequence[0]; + Operation prependNode = sequence[0]; for (int index = 1; index < sequence.Length; index++) { @@ -710,7 +703,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators for (int i = usePositions.Count - 1; i >= 0; i--) { int usePosition = -usePositions[i]; - (_, Node operation) = GetOperationNode(usePosition); + (_, Operation operation) = GetOperationNode(usePosition); for (int index = 0; index < operation.SourcesCount; index++) { @@ -722,7 +715,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators } else if (source.Kind == OperandKind.Memory) { - MemoryOperand memOp = (MemoryOperand)source; + MemoryOperand memOp = source.GetMemory(); if (memOp.BaseAddress == current.Local) { @@ -752,20 +745,20 @@ namespace ARMeilleure.CodeGen.RegisterAllocators { Debug.Assert(!interval.IsSpilled, "Spilled intervals are not allowed."); - return OperandHelper.Register( + return Operand.Factory.Register( interval.Register.Index, interval.Register.Type, interval.Local.Type); } - private (IntrusiveList<Node>, Node) GetOperationNode(int position) + private (IntrusiveList<Operation>, Operation) GetOperationNode(int position) { return _operationNodes[position / InstructionGap]; } private void NumberLocals(ControlFlowGraph cfg) { - _operationNodes = new List<(IntrusiveList<Node>, Node)>(); + _operationNodes = new List<(IntrusiveList<Operation>, Operation)>(); _intervals = new List<LiveInterval>(); @@ -783,13 +776,14 @@ namespace ARMeilleure.CodeGen.RegisterAllocators { BasicBlock block = cfg.PostOrderBlocks[index]; - for (Node node = block.Operations.First; node != null; node = node.ListNext) + for (Operation node = block.Operations.First; node != default; node = node.ListNext) { _operationNodes.Add((block.Operations, node)); for (int i = 0; i < node.DestinationsCount; i++) { Operand dest = node.GetDestination(i); + if (dest.Kind == OperandKind.LocalVariable && visited.Add(dest)) { dest.NumberLocal(_intervals.Count); @@ -804,7 +798,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators if (block.Operations.Count == 0) { // Pretend we have a dummy instruction on the empty block. - _operationNodes.Add((null, null)); + _operationNodes.Add((default, default)); _operationsCount += InstructionGap; } @@ -825,10 +819,10 @@ namespace ARMeilleure.CodeGen.RegisterAllocators // Compute local live sets. for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) { - BitMap liveGen = BitMapPool.Allocate(mapSize); - BitMap liveKill = BitMapPool.Allocate(mapSize); + BitMap liveGen = new BitMap(Allocators.Default, mapSize); + BitMap liveKill = new BitMap(Allocators.Default, mapSize); - for (Node node = block.Operations.First; node != null; node = node.ListNext) + for (Operation node = block.Operations.First; node != default; node = node.ListNext) { Sources(node, (source) => { @@ -857,8 +851,8 @@ namespace ARMeilleure.CodeGen.RegisterAllocators for (int index = 0; index < cfg.Blocks.Count; index++) { - blkLiveIn [index] = BitMapPool.Allocate(mapSize); - blkLiveOut[index] = BitMapPool.Allocate(mapSize); + blkLiveIn [index] = new BitMap(Allocators.Default, mapSize); + blkLiveOut[index] = new BitMap(Allocators.Default, mapSize); } bool modified; @@ -873,7 +867,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators BitMap liveOut = blkLiveOut[block.Index]; - for (int i = 0; i < block.SuccessorCount; i++) + for (int i = 0; i < block.SuccessorsCount; i++) { BasicBlock succ = block.GetSuccessor(i); @@ -926,7 +920,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators continue; } - foreach (Node node in BottomOperations(block)) + foreach (Operation node in BottomOperations(block)) { operationPos -= InstructionGap; @@ -947,7 +941,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators interval.AddUsePosition(operationPos); }); - if (node is Operation operation && operation.Instruction == Instruction.Call) + if (node.Instruction == Instruction.Call) { AddIntervalCallerSavedReg(context.Masks.IntCallerSavedRegisters, operationPos, RegisterType.Integer); AddIntervalCallerSavedReg(context.Masks.VecCallerSavedRegisters, operationPos, RegisterType.Vector); @@ -993,11 +987,11 @@ namespace ARMeilleure.CodeGen.RegisterAllocators return (register.Index << 1) | (register.Type == RegisterType.Vector ? 1 : 0); } - private static IEnumerable<Node> BottomOperations(BasicBlock block) + private static IEnumerable<Operation> BottomOperations(BasicBlock block) { - Node node = block.Operations.Last; + Operation node = block.Operations.Last; - while (node != null && !(node is PhiNode)) + while (node != default) { yield return node; @@ -1005,7 +999,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators } } - private static void Sources(Node node, Action<Operand> action) + private static void Sources(Operation node, Action<Operand> action) { for (int index = 0; index < node.SourcesCount; index++) { @@ -1017,14 +1011,14 @@ namespace ARMeilleure.CodeGen.RegisterAllocators } else if (source.Kind == OperandKind.Memory) { - MemoryOperand memOp = (MemoryOperand)source; + MemoryOperand memOp = source.GetMemory(); - if (memOp.BaseAddress != null) + if (memOp.BaseAddress != default) { action(memOp.BaseAddress); } - if (memOp.Index != null) + if (memOp.Index != default) { action(memOp.Index); } diff --git a/ARMeilleure/CodeGen/RegisterAllocators/LiveInterval.cs b/ARMeilleure/CodeGen/RegisterAllocators/LiveInterval.cs index 309c5ba3..be587652 100644 --- a/ARMeilleure/CodeGen/RegisterAllocators/LiveInterval.cs +++ b/ARMeilleure/CodeGen/RegisterAllocators/LiveInterval.cs @@ -34,7 +34,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators public bool IsEmpty => _ranges.Count == 0; - public LiveInterval(Operand local = null, LiveInterval parent = null) + public LiveInterval(Operand local = default, LiveInterval parent = null) { Local = local; _parent = parent ?? this; |