From e5f78fb1d44b825ee9195660f4387680055137dc Mon Sep 17 00:00:00 2001 From: gdkchan Date: Mon, 17 Feb 2020 18:30:54 -0300 Subject: Replace LinkedList by IntrusiveList to avoid allocations on JIT (#931) * Replace LinkedList by IntrusiveList to avoid allocations on JIT * Fix wrong replacements --- .../IntermediateRepresentation/BasicBlock.cs | 11 +- .../IIntrusiveListNode.cs | 8 + .../IntermediateRepresentation/IntrusiveList.cs | 178 +++++++++++++++++++++ ARMeilleure/IntermediateRepresentation/Node.cs | 33 ++-- ARMeilleure/IntermediateRepresentation/Operand.cs | 8 +- 5 files changed, 208 insertions(+), 30 deletions(-) create mode 100644 ARMeilleure/IntermediateRepresentation/IIntrusiveListNode.cs create mode 100644 ARMeilleure/IntermediateRepresentation/IntrusiveList.cs (limited to 'ARMeilleure/IntermediateRepresentation') 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 { public int Index { get; set; } - public LinkedListNode Node { get; set; } + public BasicBlock ListPrevious { get; set; } + public BasicBlock ListNext { get; set; } - public LinkedList Operations { get; } + public IntrusiveList Operations { get; } private BasicBlock _next; private BasicBlock _branch; @@ -33,7 +34,7 @@ namespace ARMeilleure.IntermediateRepresentation public BasicBlock() { - Operations = new LinkedList(); + Operations = new IntrusiveList(); Predecessors = new List(); @@ -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 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 +{ + /// + /// Represents a efficient linked list that stores the pointer on the object directly and does not allocate. + /// + /// Type of the list items + class IntrusiveList where T : class, IIntrusiveListNode + { + /// + /// First item of the list, or null if empty. + /// + public T First { get; private set; } + + /// + /// Last item of the list, or null if empty. + /// + public T Last { get; private set; } + + /// + /// Total number of items on the list. + /// + public int Count { get; private set; } + + /// + /// Adds a item as the first item of the list. + /// + /// Item to be added + [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; + } + } + + /// + /// Adds a item as the last item of the list. + /// + /// Item to be added + [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; + } + } + + /// + /// Adds a item before a existing item on the list. + /// + /// Item on the list that will succeed the new item + /// Item to be added + /// New item + [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; + } + + /// + /// Adds a item after a existing item on the list. + /// + /// Item on the list that will preceed the new item + /// Item to be added + /// New item + [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; + } + + /// + /// Removes a item from the list. + /// + /// The item to be removed + [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 { + 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[] _asgUseNodes; - private LinkedListNode[] _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[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[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[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[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 Assignments { get; } - public LinkedList Uses { get; } + public List Assignments { get; } + public List Uses { get; } private Operand() { - Assignments = new LinkedList(); - Uses = new LinkedList(); + Assignments = new List(); + Uses = new List(); } public Operand(OperandKind kind, OperandType type = OperandType.None) : this() -- cgit v1.2.3