diff options
Diffstat (limited to 'ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs')
| -rw-r--r-- | ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs | 98 |
1 files changed, 51 insertions, 47 deletions
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs index 1dc6ad73..01bb9554 100644 --- a/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs +++ b/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs @@ -5,6 +5,7 @@ using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; +using System.Numerics; namespace ARMeilleure.CodeGen.RegisterAllocators { @@ -32,7 +33,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators private int _operationsCount; - private class AllocationContext + private class AllocationContext : IDisposable { public RegisterMasks Masks { get; } @@ -49,8 +50,8 @@ namespace ARMeilleure.CodeGen.RegisterAllocators StackAlloc = stackAlloc; Masks = masks; - Active = new BitMap(intervalsCount); - Inactive = new BitMap(intervalsCount); + Active = BitMapPool.Allocate(intervalsCount); + Inactive = BitMapPool.Allocate(intervalsCount); } public void MoveActiveToInactive(int bit) @@ -69,6 +70,11 @@ namespace ARMeilleure.CodeGen.RegisterAllocators dest.Set(bit); } + + public void Dispose() + { + BitMapPool.Release(); + } } public AllocationResult RunPass( @@ -121,10 +127,14 @@ namespace ARMeilleure.CodeGen.RegisterAllocators InsertSplitCopies(); InsertSplitCopiesAtEdges(cfg); - return new AllocationResult( + AllocationResult result = new AllocationResult( context.IntUsedRegisters, context.VecUsedRegisters, context.StackAlloc.TotalSize); + + context.Dispose(); + + return result; } private void AllocateInterval(AllocationContext context, LiveInterval current, int cIndex) @@ -618,15 +628,22 @@ namespace ARMeilleure.CodeGen.RegisterAllocators bool hasSingleOrNoSuccessor = block.Next == null || block.Branch == null; - foreach (BasicBlock successor in Successors(block)) + for (int i = 0; i < 2; i++) { + // This used to use an enumerable, but it ended up generating a lot of garbage, so now it is a loop. + BasicBlock successor = (i == 0) ? block.Next : block.Branch; + if (successor == null) + { + continue; + } + int succIndex = successor.Index; // If the current node is a split node, then the actual successor node // (the successor before the split) should be right after it. if (IsSplitEdgeBlock(successor)) { - succIndex = Successors(successor).First().Index; + succIndex = FirstSuccessor(successor).Index; } CopyResolver copyResolver = new CopyResolver(); @@ -699,8 +716,10 @@ namespace ARMeilleure.CodeGen.RegisterAllocators { Operand register = GetRegister(current); - foreach (int usePosition in current.UsePositions()) + IList<int> usePositions = current.UsePositions(); + for (int i = usePositions.Count - 1; i >= 0; i--) { + int usePosition = -usePositions[i]; (_, Node operation) = GetOperationNode(usePosition); for (int index = 0; index < operation.SourcesCount; index++) @@ -743,7 +762,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators { Debug.Assert(!interval.IsSpilled, "Spilled intervals are not allowed."); - return new Operand( + return OperandHelper.Register( interval.Register.Index, interval.Register.Type, interval.Local.Type); @@ -778,8 +797,9 @@ namespace ARMeilleure.CodeGen.RegisterAllocators { _operationNodes.Add((block.Operations, node)); - foreach (Operand dest in Destinations(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); @@ -815,12 +835,12 @@ namespace ARMeilleure.CodeGen.RegisterAllocators // Compute local live sets. for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) { - BitMap liveGen = new BitMap(mapSize); - BitMap liveKill = new BitMap(mapSize); + BitMap liveGen = BitMapPool.Allocate(mapSize); + BitMap liveKill = BitMapPool.Allocate(mapSize); for (Node node = block.Operations.First; node != null; node = node.ListNext) { - foreach (Operand source in Sources(node)) + Sources(node, (source) => { int id = GetOperandId(source); @@ -828,10 +848,11 @@ namespace ARMeilleure.CodeGen.RegisterAllocators { liveGen.Set(id); } - } + }); - foreach (Operand dest in Destinations(node)) + for (int i = 0; i < node.DestinationsCount; i++) { + Operand dest = node.GetDestination(i); liveKill.Set(GetOperandId(dest)); } } @@ -846,8 +867,8 @@ namespace ARMeilleure.CodeGen.RegisterAllocators for (int index = 0; index < cfg.Blocks.Count; index++) { - blkLiveIn [index] = new BitMap(mapSize); - blkLiveOut[index] = new BitMap(mapSize); + blkLiveIn [index] = BitMapPool.Allocate(mapSize); + blkLiveOut[index] = BitMapPool.Allocate(mapSize); } bool modified; @@ -862,12 +883,10 @@ namespace ARMeilleure.CodeGen.RegisterAllocators BitMap liveOut = blkLiveOut[block.Index]; - foreach (BasicBlock successor in Successors(block)) + if ((block.Next != null && liveOut.Set(blkLiveIn[block.Next.Index])) || + (block.Branch != null && liveOut.Set(blkLiveIn[block.Branch.Index]))) { - if (liveOut.Set(blkLiveIn[successor.Index])) - { - modified = true; - } + modified = true; } BitMap liveIn = blkLiveIn[block.Index]; @@ -920,21 +939,22 @@ namespace ARMeilleure.CodeGen.RegisterAllocators { operationPos -= InstructionGap; - foreach (Operand dest in Destinations(node)) + for (int i = 0; i < node.DestinationsCount; i++) { + Operand dest = node.GetDestination(i); LiveInterval interval = _intervals[GetOperandId(dest)]; interval.SetStart(operationPos + 1); interval.AddUsePosition(operationPos + 1); } - foreach (Operand source in Sources(node)) + Sources(node, (source) => { LiveInterval interval = _intervals[GetOperandId(source)]; interval.AddRange(blockStart, operationPos + 1); interval.AddUsePosition(operationPos); - } + }); if (node is Operation operation && operation.Instruction == Instruction.Call) { @@ -949,7 +969,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators { while (mask != 0) { - int regIndex = BitUtils.LowestBitSet(mask); + int regIndex = BitOperations.TrailingZeroCount(mask); Register callerSavedReg = new Register(regIndex, regType); @@ -982,17 +1002,9 @@ namespace ARMeilleure.CodeGen.RegisterAllocators return (register.Index << 1) | (register.Type == RegisterType.Vector ? 1 : 0); } - private static IEnumerable<BasicBlock> Successors(BasicBlock block) + private static BasicBlock FirstSuccessor(BasicBlock block) { - if (block.Next != null) - { - yield return block.Next; - } - - if (block.Branch != null) - { - yield return block.Branch; - } + return block.Next ?? block.Branch; } private static IEnumerable<Node> BottomOperations(BasicBlock block) @@ -1007,15 +1019,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators } } - private static IEnumerable<Operand> Destinations(Node node) - { - for (int index = 0; index < node.DestinationsCount; index++) - { - yield return node.GetDestination(index); - } - } - - private static IEnumerable<Operand> Sources(Node node) + private static void Sources(Node node, Action<Operand> action) { for (int index = 0; index < node.SourcesCount; index++) { @@ -1023,7 +1027,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators if (IsLocalOrRegister(source.Kind)) { - yield return source; + action(source); } else if (source.Kind == OperandKind.Memory) { @@ -1031,12 +1035,12 @@ namespace ARMeilleure.CodeGen.RegisterAllocators if (memOp.BaseAddress != null) { - yield return memOp.BaseAddress; + action(memOp.BaseAddress); } if (memOp.Index != null) { - yield return memOp.Index; + action(memOp.Index); } } } |