diff options
18 files changed, 365 insertions, 198 deletions
diff --git a/ARMeilleure/CodeGen/Optimizations/Optimizer.cs b/ARMeilleure/CodeGen/Optimizations/Optimizer.cs index c01a8f1e..e3117d1f 100644 --- a/ARMeilleure/CodeGen/Optimizations/Optimizer.cs +++ b/ARMeilleure/CodeGen/Optimizations/Optimizer.cs @@ -16,17 +16,17 @@ namespace ARMeilleure.CodeGen.Optimizations { modified = false; - 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 != null) { - LinkedListNode<Node> nextNode = node.Next; + Node nextNode = node.ListNext; - bool isUnused = IsUnused(node.Value); + bool isUnused = IsUnused(node); - if (!(node.Value is Operation operation) || isUnused) + if (!(node is Operation operation) || isUnused) { if (isUnused) { @@ -80,13 +80,11 @@ namespace ARMeilleure.CodeGen.Optimizations } } - private static void RemoveNode(BasicBlock block, LinkedListNode<Node> llNode) + private static void RemoveNode(BasicBlock block, Node node) { // Remove a node from the nodes list, and also remove itself // from all the use lists on the operands that this node uses. - block.Operations.Remove(llNode); - - Node node = llNode.Value; + block.Operations.Remove(node); for (int index = 0; index < node.SourcesCount; index++) { 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; } } diff --git a/ARMeilleure/CodeGen/X86/CodeGenerator.cs b/ARMeilleure/CodeGen/X86/CodeGenerator.cs index 0268665c..d0cb77f8 100644 --- a/ARMeilleure/CodeGen/X86/CodeGenerator.cs +++ b/ARMeilleure/CodeGen/X86/CodeGenerator.cs @@ -157,11 +157,11 @@ namespace ARMeilleure.CodeGen.X86 UnwindInfo unwindInfo = WritePrologue(context); - foreach (BasicBlock block in cfg.Blocks) + for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) { context.EnterBlock(block); - foreach (Node node in block.Operations) + for (Node node = block.Operations.First; node != null; node = node.ListNext) { if (node is Operation operation) { diff --git a/ARMeilleure/CodeGen/X86/PreAllocator.cs b/ARMeilleure/CodeGen/X86/PreAllocator.cs index 034a87ac..d250f5e8 100644 --- a/ARMeilleure/CodeGen/X86/PreAllocator.cs +++ b/ARMeilleure/CodeGen/X86/PreAllocator.cs @@ -8,8 +8,6 @@ using static ARMeilleure.IntermediateRepresentation.OperandHelper; namespace ARMeilleure.CodeGen.X86 { - using LLNode = LinkedListNode<Node>; - static class PreAllocator { public static void RunPass(CompilerContext cctx, StackAllocator stackAlloc, out int maxCallArgs) @@ -20,24 +18,24 @@ namespace ARMeilleure.CodeGen.X86 Operand[] preservedArgs = new Operand[CallingConvention.GetArgumentsOnRegsCount()]; - foreach (BasicBlock block in cctx.Cfg.Blocks) + for (BasicBlock block = cctx.Cfg.Blocks.First; block != null; block = block.ListNext) { - LLNode nextNode; + Node nextNode; - for (LLNode node = block.Operations.First; node != null; node = nextNode) + for (Node node = block.Operations.First; node != null; node = nextNode) { - nextNode = node.Next; + nextNode = node.ListNext; - if (!(node.Value is Operation operation)) + if (!(node is Operation operation)) { continue; } - HandleConstantCopy(node, operation); + HandleConstantCopy(block.Operations, node, operation); - HandleSameDestSrc1Copy(node, operation); + HandleSameDestSrc1Copy(block.Operations, node, operation); - HandleFixedRegisterCopy(node, operation); + HandleFixedRegisterCopy(block.Operations, node, operation); switch (operation.Instruction) { @@ -62,51 +60,51 @@ namespace ARMeilleure.CodeGen.X86 // being called, as mandated by the ABI. if (callConv == CallConvName.Windows) { - node = HandleCallWindowsAbi(stackAlloc, node, operation); + node = HandleCallWindowsAbi(block.Operations, stackAlloc, node, operation); } else /* if (callConv == CallConvName.SystemV) */ { - node = HandleCallSystemVAbi(node, operation); + node = HandleCallSystemVAbi(block.Operations, node, operation); } break; case Instruction.ConvertToFPUI: - HandleConvertToFPUI(node, operation); + HandleConvertToFPUI(block.Operations, node, operation); break; case Instruction.LoadArgument: if (callConv == CallConvName.Windows) { - HandleLoadArgumentWindowsAbi(cctx, node, preservedArgs, operation); + HandleLoadArgumentWindowsAbi(cctx, block.Operations, node, preservedArgs, operation); } else /* if (callConv == CallConvName.SystemV) */ { - HandleLoadArgumentSystemVAbi(cctx, node, preservedArgs, operation); + HandleLoadArgumentSystemVAbi(cctx, block.Operations, node, preservedArgs, operation); } break; case Instruction.Negate: if (!operation.GetSource(0).Type.IsInteger()) { - node = HandleNegate(node, operation); + node = HandleNegate(block.Operations, node, operation); } break; case Instruction.Return: if (callConv == CallConvName.Windows) { - HandleReturnWindowsAbi(cctx, node, preservedArgs, operation); + HandleReturnWindowsAbi(cctx, block.Operations, node, preservedArgs, operation); } else /* if (callConv == CallConvName.SystemV) */ { - HandleReturnSystemVAbi(node, operation); + HandleReturnSystemVAbi(block.Operations, node, operation); } break; case Instruction.VectorInsert8: if (!HardwareCapabilities.SupportsSse41) { - node = HandleVectorInsert8(node, operation); + node = HandleVectorInsert8(block.Operations, node, operation); } break; } @@ -114,7 +112,7 @@ namespace ARMeilleure.CodeGen.X86 } } - private static void HandleConstantCopy(LLNode node, Operation operation) + private static void HandleConstantCopy(IntrusiveList<Node> nodes, Node node, Operation operation) { if (operation.SourcesCount == 0 || IsIntrinsic(operation.Instruction)) { @@ -135,7 +133,7 @@ namespace ARMeilleure.CodeGen.X86 // - Insert a copy with the constant value (as integer) to a GPR. // - Insert a copy from the GPR to a XMM register. // - Replace the constant use with the XMM register. - src1 = AddXmmCopy(node, src1); + src1 = AddXmmCopy(nodes, node, src1); operation.SetSource(0, src1); } @@ -164,7 +162,7 @@ namespace ARMeilleure.CodeGen.X86 if (src1.Kind == OperandKind.Constant) { - src1 = AddCopy(node, src1); + src1 = AddCopy(nodes, node, src1); operation.SetSource(0, src1); } @@ -182,25 +180,23 @@ namespace ARMeilleure.CodeGen.X86 { if (!src2.Type.IsInteger()) { - src2 = AddXmmCopy(node, src2); + src2 = AddXmmCopy(nodes, node, src2); operation.SetSource(1, src2); } else if (!HasConstSrc2(inst) || IsLongConst(src2)) { - src2 = AddCopy(node, src2); + src2 = AddCopy(nodes, node, src2); operation.SetSource(1, src2); } } } - private static LLNode HandleFixedRegisterCopy(LLNode node, Operation operation) + private static Node HandleFixedRegisterCopy(IntrusiveList<Node> nodes, Node node, Operation operation) { Operand dest = operation.Destination; - LinkedList<Node> nodes = node.List; - switch (operation.Instruction) { case Instruction.CompareAndSwap128: @@ -359,7 +355,7 @@ namespace ARMeilleure.CodeGen.X86 return node; } - private static LLNode HandleSameDestSrc1Copy(LLNode node, Operation operation) + private static Node HandleSameDestSrc1Copy(IntrusiveList<Node> nodes, Node node, Operation operation) { if (operation.Destination == null || operation.SourcesCount == 0) { @@ -371,8 +367,6 @@ namespace ARMeilleure.CodeGen.X86 Operand dest = operation.Destination; Operand src1 = operation.GetSource(0); - LinkedList<Node> nodes = node.List; - // The multiply instruction (that maps to IMUL) is somewhat special, it has // a three operand form where the second source is a immediate value. bool threeOperandForm = inst == Instruction.Multiply && operation.GetSource(1).Kind == OperandKind.Constant; @@ -441,7 +435,7 @@ namespace ARMeilleure.CodeGen.X86 return node; } - private static LLNode HandleConvertToFPUI(LLNode node, Operation operation) + private static Node HandleConvertToFPUI(IntrusiveList<Node> nodes, Node node, Operation operation) { // Unsigned integer to FP conversions are not supported on X86. // We need to turn them into signed integer to FP conversions, and @@ -451,9 +445,7 @@ namespace ARMeilleure.CodeGen.X86 Debug.Assert(source.Type.IsInteger(), $"Invalid source type \"{source.Type}\"."); - LinkedList<Node> nodes = node.List; - - LLNode currentNode = node; + Node currentNode = node; if (source.Type == OperandType.I32) { @@ -494,12 +486,12 @@ namespace ARMeilleure.CodeGen.X86 node = nodes.AddAfter(node, new Operation(Instruction.Add, dest, dest, lsbF)); } - Delete(currentNode, operation); + Delete(nodes, currentNode, operation); return node; } - private static LLNode HandleNegate(LLNode node, Operation operation) + private static Node HandleNegate(IntrusiveList<Node> nodes, Node node, Operation operation) { // There's no SSE FP negate instruction, so we need to transform that into // a XOR of the value to be negated with a mask with the highest bit set. @@ -510,9 +502,7 @@ namespace ARMeilleure.CodeGen.X86 Debug.Assert(dest.Type == OperandType.FP32 || dest.Type == OperandType.FP64, $"Invalid destination type \"{dest.Type}\"."); - LinkedList<Node> nodes = node.List; - - LLNode currentNode = node; + Node currentNode = node; Operand res = Local(dest.Type); @@ -531,12 +521,12 @@ namespace ARMeilleure.CodeGen.X86 node = nodes.AddAfter(node, new Operation(Instruction.Copy, dest, res)); - Delete(currentNode, operation); + Delete(nodes, currentNode, operation); return node; } - private static LLNode HandleVectorInsert8(LLNode node, Operation operation) + private static Node HandleVectorInsert8(IntrusiveList<Node> nodes, Node node, Operation operation) { // Handle vector insertion, when SSE 4.1 is not supported. Operand dest = operation.Destination; @@ -550,9 +540,7 @@ namespace ARMeilleure.CodeGen.X86 Debug.Assert(index < 16); - LinkedList<Node> nodes = node.List; - - LLNode currentNode = node; + Node currentNode = node; Operand temp1 = Local(OperandType.I32); Operand temp2 = Local(OperandType.I32); @@ -580,17 +568,15 @@ namespace ARMeilleure.CodeGen.X86 node = nodes.AddAfter(node, vinsOp); - Delete(currentNode, operation); + Delete(nodes, currentNode, operation); return node; } - private static LLNode HandleCallWindowsAbi(StackAllocator stackAlloc, LLNode node, Operation operation) + private static Node HandleCallWindowsAbi(IntrusiveList<Node> nodes, StackAllocator stackAlloc, Node node, Operation operation) { Operand dest = operation.Destination; - LinkedList<Node> nodes = node.List; - // Handle struct arguments. int retArgs = 0; @@ -661,7 +647,7 @@ namespace ARMeilleure.CodeGen.X86 Operation storeOp = new Operation(Instruction.Store, null, stackAddr, source); - HandleConstantCopy(nodes.AddBefore(node, storeOp), storeOp); + HandleConstantCopy(nodes, nodes.AddBefore(node, storeOp), storeOp); operation.SetSource(index, stackAddr); } @@ -687,7 +673,7 @@ namespace ARMeilleure.CodeGen.X86 Operation copyOp = new Operation(Instruction.Copy, argReg, source); - HandleConstantCopy(nodes.AddBefore(node, copyOp), copyOp); + HandleConstantCopy(nodes, nodes.AddBefore(node, copyOp), copyOp); sources[1 + retArgs + index] = argReg; } @@ -702,7 +688,7 @@ namespace ARMeilleure.CodeGen.X86 Operation spillOp = new Operation(Instruction.SpillArg, null, offset, source); - HandleConstantCopy(nodes.AddBefore(node, spillOp), spillOp); + HandleConstantCopy(nodes, nodes.AddBefore(node, spillOp), spillOp); } if (dest != null) @@ -738,15 +724,14 @@ namespace ARMeilleure.CodeGen.X86 return node; } - private static LLNode HandleCallSystemVAbi(LLNode node, Operation operation) + private static Node HandleCallSystemVAbi(IntrusiveList<Node> nodes, Node node, Operation operation) { Operand dest = operation.Destination; - LinkedList<Node> nodes = node.List; - - List<Operand> sources = new List<Operand>(); - - sources.Add(operation.GetSource(0)); + List<Operand> sources = new List<Operand> + { + operation.GetSource(0) + }; int argsCount = operation.SourcesCount - 1; @@ -797,7 +782,7 @@ namespace ARMeilleure.CodeGen.X86 Operation copyOp = new Operation(Instruction.Copy, argReg, source); - HandleConstantCopy(nodes.AddBefore(node, copyOp), copyOp); + HandleConstantCopy(nodes, nodes.AddBefore(node, copyOp), copyOp); sources.Add(argReg); } @@ -807,7 +792,7 @@ namespace ARMeilleure.CodeGen.X86 Operation spillOp = new Operation(Instruction.SpillArg, null, offset, source); - HandleConstantCopy(nodes.AddBefore(node, spillOp), spillOp); + HandleConstantCopy(nodes, nodes.AddBefore(node, spillOp), spillOp); stackOffset += source.Type.GetSizeInBytes(); } @@ -846,7 +831,8 @@ namespace ARMeilleure.CodeGen.X86 private static void HandleLoadArgumentWindowsAbi( CompilerContext cctx, - LLNode node, + IntrusiveList<Node> nodes, + Node node, Operand[] preservedArgs, Operation operation) { @@ -896,9 +882,9 @@ namespace ARMeilleure.CodeGen.X86 ? Instruction.Load : Instruction.Copy, dest, preservedArgs[index]); - node.List.AddBefore(node, argCopyOp); + nodes.AddBefore(node, argCopyOp); - Delete(node, operation); + Delete(nodes, node, operation); } else { @@ -908,7 +894,8 @@ namespace ARMeilleure.CodeGen.X86 private static void HandleLoadArgumentSystemVAbi( CompilerContext cctx, - LLNode node, + IntrusiveList<Node> nodes, + Node node, Operand[] preservedArgs, Operation operation) { @@ -994,9 +981,9 @@ namespace ARMeilleure.CodeGen.X86 Operation argCopyOp = new Operation(Instruction.Copy, dest, preservedArgs[index]); - node.List.AddBefore(node, argCopyOp); + nodes.AddBefore(node, argCopyOp); - Delete(node, operation); + Delete(nodes, node, operation); } else { @@ -1006,7 +993,8 @@ namespace ARMeilleure.CodeGen.X86 private static void HandleReturnWindowsAbi( CompilerContext cctx, - LLNode node, + IntrusiveList<Node> nodes, + Node node, Operand[] preservedArgs, Operation operation) { @@ -1049,19 +1037,19 @@ namespace ARMeilleure.CodeGen.X86 { Operation retStoreOp = new Operation(Instruction.Store, null, retReg, source); - node.List.AddBefore(node, retStoreOp); + nodes.AddBefore(node, retStoreOp); } else { Operation retCopyOp = new Operation(Instruction.Copy, retReg, source); - node.List.AddBefore(node, retCopyOp); + nodes.AddBefore(node, retCopyOp); } operation.SetSources(new Operand[0]); } - private static void HandleReturnSystemVAbi(LLNode node, Operation operation) + private static void HandleReturnSystemVAbi(IntrusiveList<Node> nodes, Node node, Operation operation) { if (operation.SourcesCount == 0) { @@ -1075,8 +1063,8 @@ namespace ARMeilleure.CodeGen.X86 Operand retLReg = Gpr(CallingConvention.GetIntReturnRegister(), OperandType.I64); Operand retHReg = Gpr(CallingConvention.GetIntReturnRegisterHigh(), OperandType.I64); - node.List.AddBefore(node, new Operation(Instruction.VectorExtract, retLReg, source, Const(0))); - node.List.AddBefore(node, new Operation(Instruction.VectorExtract, retHReg, source, Const(1))); + nodes.AddBefore(node, new Operation(Instruction.VectorExtract, retLReg, source, Const(0))); + nodes.AddBefore(node, new Operation(Instruction.VectorExtract, retHReg, source, Const(1))); } else { @@ -1086,30 +1074,30 @@ namespace ARMeilleure.CodeGen.X86 Operation retCopyOp = new Operation(Instruction.Copy, retReg, source); - node.List.AddBefore(node, retCopyOp); + nodes.AddBefore(node, retCopyOp); } } - private static Operand AddXmmCopy(LLNode node, Operand source) + private static Operand AddXmmCopy(IntrusiveList<Node> nodes, Node node, Operand source) { Operand temp = Local(source.Type); - Operand intConst = AddCopy(node, GetIntConst(source)); + Operand intConst = AddCopy(nodes, node, GetIntConst(source)); Operation copyOp = new Operation(Instruction.VectorCreateScalar, temp, intConst); - node.List.AddBefore(node, copyOp); + nodes.AddBefore(node, copyOp); return temp; } - private static Operand AddCopy(LLNode node, Operand source) + private static Operand AddCopy(IntrusiveList<Node> nodes, Node node, Operand source) { Operand temp = Local(source.Type); Operation copyOp = new Operation(Instruction.Copy, temp, source); - node.List.AddBefore(node, copyOp); + nodes.AddBefore(node, copyOp); return temp; } @@ -1142,7 +1130,7 @@ namespace ARMeilleure.CodeGen.X86 return value == (int)value; } - private static void Delete(LLNode node, Operation operation) + private static void Delete(IntrusiveList<Node> nodes, Node node, Operation operation) { operation.Destination = null; @@ -1151,7 +1139,7 @@ namespace ARMeilleure.CodeGen.X86 operation.SetSource(index, null); } - node.List.Remove(node); + nodes.Remove(node); } private static Operand Gpr(X86Register register, OperandType type) diff --git a/ARMeilleure/Diagnostics/IRDumper.cs b/ARMeilleure/Diagnostics/IRDumper.cs index 55d5b493..c3e99dfa 100644 --- a/ARMeilleure/Diagnostics/IRDumper.cs +++ b/ARMeilleure/Diagnostics/IRDumper.cs @@ -35,7 +35,7 @@ namespace ARMeilleure.Diagnostics IncreaseIndentation(); - foreach (BasicBlock block in cfg.Blocks) + for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) { string blockName = GetBlockName(block); @@ -55,7 +55,7 @@ namespace ARMeilleure.Diagnostics IncreaseIndentation(); - foreach (Node node in block.Operations) + for (Node node = block.Operations.First; node != null; node = node.ListNext) { string[] sources = new string[node.SourcesCount]; 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() 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); |