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

* Replace LinkedList by IntrusiveList to avoid allocations on JIT

* Fix wrong replacements

7 files changed, 45 insertions, 46 deletions

diff --git a/ARMeilleure/Translation/ControlFlowGraph.cs b/ARMeilleure/Translation/ControlFlowGraph.cs
index 758f1f96..37613eb4 100644
--- a/ARMeilleure/Translation/ControlFlowGraph.cs
+++ b/ARMeilleure/Translation/ControlFlowGraph.cs
@@ -9,13 +9,13 @@ namespace ARMeilleure.Translation
     {
         public BasicBlock Entry { get; }
 
-        public LinkedList<BasicBlock> Blocks { get; }
+        public IntrusiveList<BasicBlock> Blocks { get; }
 
         public BasicBlock[] PostOrderBlocks { get; }
 
         public int[] PostOrderMap { get; }
 
-        public ControlFlowGraph(BasicBlock entry, LinkedList<BasicBlock> blocks)
+        public ControlFlowGraph(BasicBlock entry, IntrusiveList<BasicBlock> blocks)
         {
             Entry  = entry;
             Blocks = blocks;
@@ -57,7 +57,7 @@ namespace ARMeilleure.Translation
             }
         }
 
-        private void RemoveUnreachableBlocks(LinkedList<BasicBlock> blocks)
+        private void RemoveUnreachableBlocks(IntrusiveList<BasicBlock> blocks)
         {
             HashSet<BasicBlock> visited = new HashSet<BasicBlock>();
 
@@ -87,25 +87,23 @@ namespace ARMeilleure.Translation
                 // Remove unreachable blocks and renumber.
                 int index = 0;
 
-                for (LinkedListNode<BasicBlock> node = blocks.First; node != null;)
+                for (BasicBlock block = blocks.First; block != null;)
                 {
-                    LinkedListNode<BasicBlock> nextNode = node.Next;
-
-                    BasicBlock block = node.Value;
+                    BasicBlock nextBlock = block.ListNext;
 
                     if (!visited.Contains(block))
                     {
-                        block.Next   = null;
+                        block.Next = null;
                         block.Branch = null;
 
-                        blocks.Remove(node);
+                        blocks.Remove(block);
                     }
                     else
                     {
                         block.Index = index++;
                     }
 
-                    node = nextNode;
+                    block = nextBlock;
                 }
             }
         }
@@ -130,7 +128,7 @@ namespace ARMeilleure.Translation
             }
 
             // Insert the new block on the list of blocks.
-            BasicBlock succPrev = successor.Node.Previous?.Value;
+            BasicBlock succPrev = successor.ListPrevious;
 
             if (succPrev != null && succPrev != predecessor && succPrev.Next == successor)
             {
@@ -145,12 +143,12 @@ namespace ARMeilleure.Translation
 
                 splitBlock2.Operations.AddLast(new Operation(Instruction.Branch, null));
 
-                Blocks.AddBefore(successor.Node, splitBlock2);
+                Blocks.AddBefore(successor, splitBlock2);
             }
 
             splitBlock.Next = successor;
 
-            Blocks.AddBefore(successor.Node, splitBlock);
+            Blocks.AddBefore(successor, splitBlock);
 
             return splitBlock;
         }
diff --git a/ARMeilleure/Translation/Dominance.cs b/ARMeilleure/Translation/Dominance.cs
index bb55169e..b9b961d1 100644
--- a/ARMeilleure/Translation/Dominance.cs
+++ b/ARMeilleure/Translation/Dominance.cs
@@ -71,7 +71,7 @@ namespace ARMeilleure.Translation
 
         public static void FindDominanceFrontiers(ControlFlowGraph cfg)
         {
-            foreach (BasicBlock block in cfg.Blocks)
+            for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext)
             {
                 if (block.Predecessors.Count < 2)
                 {
diff --git a/ARMeilleure/Translation/EmitterContext.cs b/ARMeilleure/Translation/EmitterContext.cs
index 13cf677c..a125a715 100644
--- a/ARMeilleure/Translation/EmitterContext.cs
+++ b/ARMeilleure/Translation/EmitterContext.cs
@@ -12,7 +12,7 @@ namespace ARMeilleure.Translation
     {
         private Dictionary<Operand, BasicBlock> _irLabels;
 
-        private LinkedList<BasicBlock> _irBlocks;
+        private IntrusiveList<BasicBlock> _irBlocks;
 
         private BasicBlock _irBlock;
 
@@ -22,7 +22,7 @@ namespace ARMeilleure.Translation
         {
             _irLabels = new Dictionary<Operand, BasicBlock>();
 
-            _irBlocks = new LinkedList<BasicBlock>();
+            _irBlocks = new IntrusiveList<BasicBlock>();
 
             _needsNewBlock = true;
         }
@@ -508,7 +508,8 @@ namespace ARMeilleure.Translation
             if (_irLabels.TryGetValue(label, out BasicBlock nextBlock))
             {
                 nextBlock.Index = _irBlocks.Count;
-                nextBlock.Node  = _irBlocks.AddLast(nextBlock);
+
+                _irBlocks.AddLast(nextBlock);
 
                 NextBlock(nextBlock);
             }
@@ -524,7 +525,7 @@ namespace ARMeilleure.Translation
         {
             BasicBlock block = new BasicBlock(_irBlocks.Count);
 
-            block.Node = _irBlocks.AddLast(block);
+            _irBlocks.AddLast(block);
 
             NextBlock(block);
         }
@@ -556,7 +557,7 @@ namespace ARMeilleure.Translation
 
         public ControlFlowGraph GetControlFlowGraph()
         {
-            return new ControlFlowGraph(_irBlocks.First.Value, _irBlocks);
+            return new ControlFlowGraph(_irBlocks.First, _irBlocks);
         }
     }
 }
\ No newline at end of file
diff --git a/ARMeilleure/Translation/RegisterToLocal.cs b/ARMeilleure/Translation/RegisterToLocal.cs
index aa918018..088cec7e 100644
--- a/ARMeilleure/Translation/RegisterToLocal.cs
+++ b/ARMeilleure/Translation/RegisterToLocal.cs
@@ -25,9 +25,9 @@ namespace ARMeilleure.Translation
                 return local;
             }
 
-            foreach (BasicBlock block in cfg.Blocks)
+            for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext)
             {
-                foreach (Node node in block.Operations)
+                for (Node node = block.Operations.First; node != null; node = node.ListNext)
                 {
                     Operand dest = node.Destination;
 
diff --git a/ARMeilleure/Translation/RegisterUsage.cs b/ARMeilleure/Translation/RegisterUsage.cs
index 4164786b..becaa24c 100644
--- a/ARMeilleure/Translation/RegisterUsage.cs
+++ b/ARMeilleure/Translation/RegisterUsage.cs
@@ -74,9 +74,9 @@ namespace ARMeilleure.Translation
             RegisterMask[] localInputs  = new RegisterMask[cfg.Blocks.Count];
             RegisterMask[] localOutputs = new RegisterMask[cfg.Blocks.Count];
 
-            foreach (BasicBlock block in cfg.Blocks)
+            for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext)
             {
-                foreach (Node node in block.Operations)
+                for (Node node = block.Operations.First; node != null; node = node.ListNext)
                 {
                     Operation operation = node as Operation;
 
@@ -192,13 +192,13 @@ namespace ARMeilleure.Translation
             while (modified);
 
             // Insert load and store context instructions where needed.
-            foreach (BasicBlock block in cfg.Blocks)
+            for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext)
             {
                 bool hasContextLoad = HasContextLoad(block);
 
                 if (hasContextLoad)
                 {
-                    block.Operations.RemoveFirst();
+                    block.Operations.Remove(block.Operations.First);
                 }
 
                 // The only block without any predecessor should be the entry block.
@@ -213,7 +213,7 @@ namespace ARMeilleure.Translation
 
                 if (hasContextStore)
                 {
-                    block.Operations.RemoveLast();
+                    block.Operations.Remove(block.Operations.Last);
                 }
 
                 if (EndsWithReturn(block) || hasContextStore)
@@ -226,7 +226,7 @@ namespace ARMeilleure.Translation
 
         private static bool HasContextLoad(BasicBlock block)
         {
-            return StartsWith(block, Instruction.LoadFromContext) && block.Operations.First.Value.SourcesCount == 0;
+            return StartsWith(block, Instruction.LoadFromContext) && block.Operations.First.SourcesCount == 0;
         }
 
         private static bool HasContextStore(BasicBlock block)
@@ -241,7 +241,7 @@ namespace ARMeilleure.Translation
                 return false;
             }
 
-            return block.Operations.First.Value is Operation operation && operation.Instruction == inst;
+            return block.Operations.First is Operation operation && operation.Instruction == inst;
         }
 
         private static bool EndsWith(BasicBlock block, Instruction inst)
@@ -251,7 +251,7 @@ namespace ARMeilleure.Translation
                 return false;
             }
 
-            return block.Operations.Last.Value is Operation operation && operation.Instruction == inst;
+            return block.Operations.Last is Operation operation && operation.Instruction == inst;
         }
 
         private static RegisterMask GetMask(Register register)
diff --git a/ARMeilleure/Translation/SsaConstruction.cs b/ARMeilleure/Translation/SsaConstruction.cs
index ccf52591..292e74e3 100644
--- a/ARMeilleure/Translation/SsaConstruction.cs
+++ b/ARMeilleure/Translation/SsaConstruction.cs
@@ -47,7 +47,7 @@ namespace ARMeilleure.Translation
         {
             DefMap[] globalDefs = new DefMap[cfg.Blocks.Count];
 
-            foreach (BasicBlock block in cfg.Blocks)
+            for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext)
             {
                 globalDefs[block.Index] = new DefMap();
             }
@@ -55,11 +55,11 @@ namespace ARMeilleure.Translation
             Queue<BasicBlock> dfPhiBlocks = new Queue<BasicBlock>();
 
             // First pass, get all defs and locals uses.
-            foreach (BasicBlock block in cfg.Blocks)
+            for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext)
             {
                 Operand[] localDefs = new Operand[RegisterConsts.TotalCount];
 
-                LinkedListNode<Node> node = block.Operations.First;
+                Node node = block.Operations.First;
 
                 Operand RenameLocal(Operand operand)
                 {
@@ -75,7 +75,7 @@ namespace ARMeilleure.Translation
 
                 while (node != null)
                 {
-                    if (node.Value is Operation operation)
+                    if (node is Operation operation)
                     {
                         for (int index = 0; index < operation.SourcesCount; index++)
                         {
@@ -94,7 +94,7 @@ namespace ARMeilleure.Translation
                         }
                     }
 
-                    node = node.Next;
+                    node = node.ListNext;
                 }
 
                 for (int index = 0; index < RegisterConsts.TotalCount; index++)
@@ -126,11 +126,11 @@ namespace ARMeilleure.Translation
             }
 
             // Second pass, rename variables with definitions on different blocks.
-            foreach (BasicBlock block in cfg.Blocks)
+            for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext)
             {
                 Operand[] localDefs = new Operand[RegisterConsts.TotalCount];
 
-                LinkedListNode<Node> node = block.Operations.First;
+                Node node = block.Operations.First;
 
                 Operand RenameGlobal(Operand operand)
                 {
@@ -155,7 +155,7 @@ namespace ARMeilleure.Translation
 
                 while (node != null)
                 {
-                    if (node.Value is Operation operation)
+                    if (node is Operation operation)
                     {
                         for (int index = 0; index < operation.SourcesCount; index++)
                         {
@@ -163,7 +163,7 @@ namespace ARMeilleure.Translation
                         }
                     }
 
-                    node = node.Next;
+                    node = node.ListNext;
                 }
             }
         }
@@ -238,17 +238,17 @@ namespace ARMeilleure.Translation
 
         private static void AddPhi(BasicBlock block, PhiNode phi)
         {
-            LinkedListNode<Node> node = block.Operations.First;
+            Node node = block.Operations.First;
 
             if (node != null)
             {
-                while (node.Next?.Value is PhiNode)
+                while (node.ListNext is PhiNode)
                 {
-                    node = node.Next;
+                    node = node.ListNext;
                 }
             }
 
-            if (node?.Value is PhiNode)
+            if (node is PhiNode)
             {
                 block.Operations.AddAfter(node, phi);
             }
diff --git a/ARMeilleure/Translation/SsaDeconstruction.cs b/ARMeilleure/Translation/SsaDeconstruction.cs
index 2ba78bdf..37d61625 100644
--- a/ARMeilleure/Translation/SsaDeconstruction.cs
+++ b/ARMeilleure/Translation/SsaDeconstruction.cs
@@ -9,13 +9,13 @@ namespace ARMeilleure.Translation
     {
         public static void Deconstruct(ControlFlowGraph cfg)
         {
-            foreach (BasicBlock block in cfg.Blocks)
+            for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext)
             {
-                LinkedListNode<Node> node = block.Operations.First;
+                Node node = block.Operations.First;
 
-                while (node?.Value is PhiNode phi)
+                while (node is PhiNode phi)
                 {
-                    LinkedListNode<Node> nextNode = node.Next;
+                    Node nextNode = node.ListNext;
 
                     Operand local = Local(phi.Destination.Type);