Replace LinkedList by IntrusiveList to avoid allocations on JIT (#931)

* Replace LinkedList by IntrusiveList to avoid allocations on JIT

* Fix wrong replacements

2 files changed, 34 insertions, 30 deletions

diff --git a/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs
index 9a827420..ed0e1ae1 100644
--- a/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs
+++ b/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs
@@ -95,7 +95,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
 
                 bool hasCall = false;
 
-                foreach (Node node in block.Operations)
+                for (Node node = block.Operations.First; node != null; node = node.ListNext)
                 {
                     if (node is Operation operation && operation.Instruction == Instruction.Call)
                     {
@@ -176,10 +176,8 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
                 intLocalFreeRegisters &= ~(intSpillTempRegisters | intCallerSavedRegisters);
                 vecLocalFreeRegisters &= ~(vecSpillTempRegisters | vecCallerSavedRegisters);
 
-                for (LinkedListNode<Node> llNode = block.Operations.First; llNode != null; llNode = llNode.Next)
+                for (Node node = block.Operations.First; node != null; node = node.ListNext)
                 {
-                    Node node = llNode.Value;
-
                     int intLocalUse = 0;
                     int vecLocalUse = 0;
 
@@ -232,7 +230,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
 
                             Operation fillOp = new Operation(Instruction.Fill, temp, Const(info.SpillOffset));
 
-                            block.Operations.AddBefore(llNode, fillOp);
+                            block.Operations.AddBefore(node, fillOp);
                         }
                     }
 
@@ -306,7 +304,9 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
 
                             Operation spillOp = new Operation(Instruction.Spill, null, Const(info.SpillOffset), temp);
 
-                            llNode = block.Operations.AddAfter(llNode, spillOp);
+                            block.Operations.AddAfter(node, spillOp);
+
+                            node = spillOp;
                         }
                     }
 
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs
index 6d5ecc14..1127ccd5 100644
--- a/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs
+++ b/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs
@@ -28,7 +28,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
 
         private LiveInterval[] _parentIntervals;
 
-        private List<LinkedListNode<Node>> _operationNodes;
+        private List<(IntrusiveList<Node>, Node)> _operationNodes;
 
         private int _operationsCount;
 
@@ -583,15 +583,19 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
 
                 int splitPosition = kv.Key;
 
-                LinkedListNode<Node> node = GetOperationNode(splitPosition);
+                (IntrusiveList<Node> nodes, Node node) = GetOperationNode(splitPosition);
 
                 Operation[] sequence = copyResolver.Sequence();
 
-                node = node.List.AddBefore(node, sequence[0]);
+                nodes.AddBefore(node, sequence[0]);
+
+                node = sequence[0];
 
                 for (int index = 1; index < sequence.Length; index++)
                 {
-                    node = node.List.AddAfter(node, sequence[index]);
+                    nodes.AddAfter(node, sequence[index]);
+
+                    node = sequence[index];
                 }
             }
         }
@@ -605,10 +609,8 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
                 return block.Index >= blocksCount;
             }
 
-            for (LinkedListNode<BasicBlock> node = cfg.Blocks.First; node != null; node = node.Next)
+            for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext)
             {
-                BasicBlock block = node.Value;
-
                 if (IsSplitEdgeBlock(block))
                 {
                     continue;
@@ -666,13 +668,17 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
                     }
                     else if (successor.Predecessors.Count == 1)
                     {
-                        LinkedListNode<Node> prependNode = successor.Operations.AddFirst(sequence[0]);
+                        successor.Operations.AddFirst(sequence[0]);
+
+                        Node prependNode = sequence[0];
 
                         for (int index = 1; index < sequence.Length; index++)
                         {
                             Operation operation = sequence[index];
 
-                            prependNode = successor.Operations.AddAfter(prependNode, operation);
+                            successor.Operations.AddAfter(prependNode, operation);
+
+                            prependNode = operation;
                         }
                     }
                     else
@@ -695,7 +701,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
 
             foreach (int usePosition in current.UsePositions())
             {
-                Node operation = GetOperationNode(usePosition).Value;
+                (_, Node operation) = GetOperationNode(usePosition);
 
                 for (int index = 0; index < operation.SourcesCount; index++)
                 {
@@ -729,14 +735,14 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
                 interval.Local.Type);
         }
 
-        private LinkedListNode<Node> GetOperationNode(int position)
+        private (IntrusiveList<Node>, Node) GetOperationNode(int position)
         {
             return _operationNodes[position / InstructionGap];
         }
 
         private void NumberLocals(ControlFlowGraph cfg)
         {
-            _operationNodes = new List<LinkedListNode<Node>>();
+            _operationNodes = new List<(IntrusiveList<Node>, Node)>();
 
             _intervals = new List<LiveInterval>();
 
@@ -754,13 +760,11 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
             {
                 BasicBlock block = cfg.PostOrderBlocks[index];
 
-                for (LinkedListNode<Node> node = block.Operations.First; node != null; node = node.Next)
+                for (Node node = block.Operations.First; node != null; node = node.ListNext)
                 {
-                    _operationNodes.Add(node);
-
-                    Node operation = node.Value;
+                    _operationNodes.Add((block.Operations, node));
 
-                    foreach (Operand dest in Destinations(operation))
+                    foreach (Operand dest in Destinations(node))
                     {
                         if (dest.Kind == OperandKind.LocalVariable && visited.Add(dest))
                         {
@@ -776,7 +780,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
                 if (block.Operations.Count == 0)
                 {
                     // Pretend we have a dummy instruction on the empty block.
-                    _operationNodes.Add(null);
+                    _operationNodes.Add((null, null));
 
                     _operationsCount += InstructionGap;
                 }
@@ -795,12 +799,12 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
             BitMap[] blkLiveKill = new BitMap[cfg.Blocks.Count];
 
             // Compute local live sets.
-            foreach (BasicBlock block in cfg.Blocks)
+            for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext)
             {
                 BitMap liveGen  = new BitMap(mapSize);
                 BitMap liveKill = new BitMap(mapSize);
 
-                foreach (Node node in block.Operations)
+                for (Node node = block.Operations.First; node != null; node = node.ListNext)
                 {
                     foreach (Operand source in Sources(node))
                     {
@@ -979,13 +983,13 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
 
         private static IEnumerable<Node> BottomOperations(BasicBlock block)
         {
-            LinkedListNode<Node> node = block.Operations.Last;
+            Node node = block.Operations.Last;
 
-            while (node != null && !(node.Value is PhiNode))
+            while (node != null && !(node is PhiNode))
             {
-                yield return node.Value;
+                yield return node;
 
-                node = node.Previous;
+                node = node.ListPrevious;
             }
         }