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

* Replace LinkedList by IntrusiveList to avoid allocations on JIT

* Fix wrong replacements

5 files changed, 208 insertions, 30 deletions

diff --git a/ARMeilleure/IntermediateRepresentation/BasicBlock.cs b/ARMeilleure/IntermediateRepresentation/BasicBlock.cs
index 06839f30..ac48ac8e 100644
--- a/ARMeilleure/IntermediateRepresentation/BasicBlock.cs
+++ b/ARMeilleure/IntermediateRepresentation/BasicBlock.cs
@@ -2,13 +2,14 @@ using System.Collections.Generic;
 
 namespace ARMeilleure.IntermediateRepresentation
 {
-    class BasicBlock
+    class BasicBlock : IIntrusiveListNode<BasicBlock>
     {
         public int Index { get; set; }
 
-        public LinkedListNode<BasicBlock> Node { get; set; }
+        public BasicBlock ListPrevious { get; set; }
+        public BasicBlock ListNext { get; set; }
 
-        public LinkedList<Node> Operations { get; }
+        public IntrusiveList<Node> Operations { get; }
 
         private BasicBlock _next;
         private BasicBlock _branch;
@@ -33,7 +34,7 @@ namespace ARMeilleure.IntermediateRepresentation
 
         public BasicBlock()
         {
-            Operations = new LinkedList<Node>();
+            Operations = new IntrusiveList<Node>();
 
             Predecessors = new List<BasicBlock>();
 
@@ -77,7 +78,7 @@ namespace ARMeilleure.IntermediateRepresentation
 
         public Node GetLastOp()
         {
-            return Operations.Last?.Value;
+            return Operations.Last;
         }
     }
 }
\ No newline at end of file
diff --git a/ARMeilleure/IntermediateRepresentation/IIntrusiveListNode.cs b/ARMeilleure/IntermediateRepresentation/IIntrusiveListNode.cs
new file mode 100644
index 00000000..797e7891
--- /dev/null
+++ b/ARMeilleure/IntermediateRepresentation/IIntrusiveListNode.cs
@@ -0,0 +1,8 @@
+namespace ARMeilleure.IntermediateRepresentation
+{
+    interface IIntrusiveListNode<T> where T : class
+    {
+        T ListPrevious { get; set; }
+        T ListNext { get; set; }
+    }
+}
diff --git a/ARMeilleure/IntermediateRepresentation/IntrusiveList.cs b/ARMeilleure/IntermediateRepresentation/IntrusiveList.cs
new file mode 100644
index 00000000..a7b0f7a7
--- /dev/null
+++ b/ARMeilleure/IntermediateRepresentation/IntrusiveList.cs
@@ -0,0 +1,178 @@
+using System.Diagnostics;
+using System.Runtime.CompilerServices;
+
+namespace ARMeilleure.IntermediateRepresentation
+{
+    /// <summary>
+    /// Represents a efficient linked list that stores the pointer on the object directly and does not allocate.
+    /// </summary>
+    /// <typeparam name="T">Type of the list items</typeparam>
+    class IntrusiveList<T> where T : class, IIntrusiveListNode<T>
+    {
+        /// <summary>
+        /// First item of the list, or null if empty.
+        /// </summary>
+        public T First { get; private set; }
+
+        /// <summary>
+        /// Last item of the list, or null if empty.
+        /// </summary>
+        public T Last { get; private set; }
+
+        /// <summary>
+        /// Total number of items on the list.
+        /// </summary>
+        public int Count { get; private set; }
+
+        /// <summary>
+        /// Adds a item as the first item of the list.
+        /// </summary>
+        /// <param name="newNode">Item to be added</param>
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        public void AddFirst(T newNode)
+        {
+            if (First != null)
+            {
+                AddBefore(First, newNode);
+            }
+            else
+            {
+                Debug.Assert(newNode.ListPrevious == null);
+                Debug.Assert(newNode.ListNext == null);
+                Debug.Assert(Last == null);
+
+                First = newNode;
+                Last = newNode;
+
+                Debug.Assert(Count == 0);
+
+                Count = 1;
+            }
+        }
+
+        /// <summary>
+        /// Adds a item as the last item of the list.
+        /// </summary>
+        /// <param name="newNode">Item to be added</param>
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        public void AddLast(T newNode)
+        {
+            if (Last != null)
+            {
+                AddAfter(Last, newNode);
+            }
+            else
+            {
+                Debug.Assert(newNode.ListPrevious == null);
+                Debug.Assert(newNode.ListNext == null);
+                Debug.Assert(First == null);
+
+                First = newNode;
+                Last = newNode;
+
+                Debug.Assert(Count == 0);
+
+                Count = 1;
+            }
+        }
+
+        /// <summary>
+        /// Adds a item before a existing item on the list.
+        /// </summary>
+        /// <param name="node">Item on the list that will succeed the new item</param>
+        /// <param name="newNode">Item to be added</param>
+        /// <returns>New item</returns>
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        public T AddBefore(T node, T newNode)
+        {
+            Debug.Assert(newNode.ListPrevious == null);
+            Debug.Assert(newNode.ListNext == null);
+
+            newNode.ListPrevious = node.ListPrevious;
+            newNode.ListNext = node;
+
+            node.ListPrevious = newNode;
+
+            if (newNode.ListPrevious != null)
+            {
+                newNode.ListPrevious.ListNext = newNode;
+            }
+
+            if (First == node)
+            {
+                First = newNode;
+            }
+
+            Count++;
+
+            return newNode;
+        }
+
+        /// <summary>
+        /// Adds a item after a existing item on the list.
+        /// </summary>
+        /// <param name="node">Item on the list that will preceed the new item</param>
+        /// <param name="newNode">Item to be added</param>
+        /// <returns>New item</returns>
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        public T AddAfter(T node, T newNode)
+        {
+            Debug.Assert(newNode.ListPrevious == null);
+            Debug.Assert(newNode.ListNext == null);
+
+            newNode.ListPrevious = node;
+            newNode.ListNext = node.ListNext;
+
+            node.ListNext = newNode;
+
+            if (newNode.ListNext != null)
+            {
+                newNode.ListNext.ListPrevious = newNode;
+            }
+
+            if (Last == node)
+            {
+                Last = newNode;
+            }
+
+            Count++;
+
+            return newNode;
+        }
+
+        /// <summary>
+        /// Removes a item from the list.
+        /// </summary>
+        /// <param name="node">The item to be removed</param>
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        public void Remove(T node)
+        {
+            if (node.ListPrevious != null)
+            {
+                node.ListPrevious.ListNext = node.ListNext;
+            }
+            else
+            {
+                Debug.Assert(First == node);
+
+                First = node.ListNext;
+            }
+
+            if (node.ListNext != null)
+            {
+                node.ListNext.ListPrevious = node.ListPrevious;
+            }
+            else
+            {
+                Debug.Assert(Last == node);
+
+                Last = node.ListPrevious;
+            }
+
+            node.ListPrevious = null;
+            node.ListNext = null;
+
+            Count--;
+        }
+    }
+}
diff --git a/ARMeilleure/IntermediateRepresentation/Node.cs b/ARMeilleure/IntermediateRepresentation/Node.cs
index 167acd07..e1f8b11b 100644
--- a/ARMeilleure/IntermediateRepresentation/Node.cs
+++ b/ARMeilleure/IntermediateRepresentation/Node.cs
@@ -1,10 +1,12 @@
 using System;
-using System.Collections.Generic;
 
 namespace ARMeilleure.IntermediateRepresentation
 {
-    class Node
+    class Node : IIntrusiveListNode<Node>
     {
+        public Node ListPrevious { get; set; }
+        public Node ListNext { get; set; }
+
         public Operand Destination
         {
             get
@@ -27,9 +29,6 @@ namespace ARMeilleure.IntermediateRepresentation
         private Operand[] _destinations;
         private Operand[] _sources;
 
-        private LinkedListNode<Node>[] _asgUseNodes;
-        private LinkedListNode<Node>[] _srcUseNodes;
-
         public int DestinationsCount => _destinations.Length;
         public int SourcesCount      => _sources.Length;
 
@@ -38,8 +37,6 @@ namespace ARMeilleure.IntermediateRepresentation
             Destination = destination;
 
             _sources = new Operand[sourcesCount];
-
-            _srcUseNodes = new LinkedListNode<Node>[sourcesCount];
         }
 
         public Node(Operand[] destinations, int sourcesCount)
@@ -47,8 +44,6 @@ namespace ARMeilleure.IntermediateRepresentation
             SetDestinations(destinations ?? throw new ArgumentNullException(nameof(destinations)));
 
             _sources = new Operand[sourcesCount];
-
-            _srcUseNodes = new LinkedListNode<Node>[sourcesCount];
         }
 
         public Operand GetDestination(int index)
@@ -67,12 +62,12 @@ namespace ARMeilleure.IntermediateRepresentation
 
             if (oldOp != null && oldOp.Kind == OperandKind.LocalVariable)
             {
-                oldOp.Assignments.Remove(_asgUseNodes[index]);
+                oldOp.Assignments.Remove(this);
             }
 
             if (destination != null && destination.Kind == OperandKind.LocalVariable)
             {
-                _asgUseNodes[index] = destination.Assignments.AddLast(this);
+                destination.Assignments.Add(this);
             }
 
             _destinations[index] = destination;
@@ -84,12 +79,12 @@ namespace ARMeilleure.IntermediateRepresentation
 
             if (oldOp != null && oldOp.Kind == OperandKind.LocalVariable)
             {
-                oldOp.Uses.Remove(_srcUseNodes[index]);
+                oldOp.Uses.Remove(this);
             }
 
             if (source != null && source.Kind == OperandKind.LocalVariable)
             {
-                _srcUseNodes[index] = source.Uses.AddLast(this);
+                source.Uses.Add(this);
             }
 
             _sources[index] = source;
@@ -105,7 +100,7 @@ namespace ARMeilleure.IntermediateRepresentation
 
                     if (oldOp != null && oldOp.Kind == OperandKind.LocalVariable)
                     {
-                        oldOp.Assignments.Remove(_asgUseNodes[index]);
+                        oldOp.Assignments.Remove(this);
                     }
                 }
 
@@ -116,8 +111,6 @@ namespace ARMeilleure.IntermediateRepresentation
                 _destinations = new Operand[destinations.Length];
             }
 
-            _asgUseNodes = new LinkedListNode<Node>[destinations.Length];
-
             for (int index = 0; index < destinations.Length; index++)
             {
                 Operand newOp = destinations[index];
@@ -126,7 +119,7 @@ namespace ARMeilleure.IntermediateRepresentation
 
                 if (newOp.Kind == OperandKind.LocalVariable)
                 {
-                    _asgUseNodes[index] = newOp.Assignments.AddLast(this);
+                    newOp.Assignments.Add(this);
                 }
             }
         }
@@ -139,14 +132,12 @@ namespace ARMeilleure.IntermediateRepresentation
 
                 if (oldOp != null && oldOp.Kind == OperandKind.LocalVariable)
                 {
-                    oldOp.Uses.Remove(_srcUseNodes[index]);
+                    oldOp.Uses.Remove(this);
                 }
             }
 
             _sources = new Operand[sources.Length];
 
-            _srcUseNodes = new LinkedListNode<Node>[sources.Length];
-
             for (int index = 0; index < sources.Length; index++)
             {
                 Operand newOp = sources[index];
@@ -155,7 +146,7 @@ namespace ARMeilleure.IntermediateRepresentation
 
                 if (newOp.Kind == OperandKind.LocalVariable)
                 {
-                    _srcUseNodes[index] = newOp.Uses.AddLast(this);
+                    newOp.Uses.Add(this);
                 }
             }
         }
diff --git a/ARMeilleure/IntermediateRepresentation/Operand.cs b/ARMeilleure/IntermediateRepresentation/Operand.cs
index 2df6256f..fe5bf073 100644
--- a/ARMeilleure/IntermediateRepresentation/Operand.cs
+++ b/ARMeilleure/IntermediateRepresentation/Operand.cs
@@ -11,13 +11,13 @@ namespace ARMeilleure.IntermediateRepresentation
 
         public ulong Value { get; private set; }
 
-        public LinkedList<Node> Assignments { get; }
-        public LinkedList<Node> Uses        { get; }
+        public List<Node> Assignments { get; }
+        public List<Node> Uses        { get; }
 
         private Operand()
         {
-            Assignments = new LinkedList<Node>();
-            Uses        = new LinkedList<Node>();
+            Assignments = new List<Node>();
+            Uses        = new List<Node>();
         }
 
         public Operand(OperandKind kind, OperandType type = OperandType.None) : this()