3 files changed, 541 insertions, 0 deletions
diff --git a/ARMeilleure/CodeGen/Optimizations/ConstantFolding.cs b/ARMeilleure/CodeGen/Optimizations/ConstantFolding.cs
new file mode 100644
index 00000000..84eedee0
--- /dev/null
+++ b/ARMeilleure/CodeGen/Optimizations/ConstantFolding.cs
@@ -0,0 +1,258 @@
+using ARMeilleure.IntermediateRepresentation;
+using System;
+
+using static ARMeilleure.IntermediateRepresentation.OperandHelper;
+
+namespace ARMeilleure.CodeGen.Optimizations
+{
+    static class ConstantFolding
+    {
+        public static void RunPass(Operation operation)
+        {
+            if (operation.Destination == null || operation.SourcesCount == 0)
+            {
+                return;
+            }
+
+            if (!AreAllSourcesConstant(operation))
+            {
+                return;
+            }
+
+            OperandType type = operation.Destination.Type;
+
+            switch (operation.Instruction)
+            {
+                case Instruction.Add:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateBinaryI32(operation, (x, y) => x + y);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateBinaryI64(operation, (x, y) => x + y);
+                    }
+                    break;
+
+                case Instruction.BitwiseAnd:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateBinaryI32(operation, (x, y) => x & y);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateBinaryI64(operation, (x, y) => x & y);
+                    }
+                    break;
+
+                case Instruction.BitwiseExclusiveOr:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateBinaryI32(operation, (x, y) => x ^ y);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateBinaryI64(operation, (x, y) => x ^ y);
+                    }
+                    break;
+
+                case Instruction.BitwiseNot:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateUnaryI32(operation, (x) => ~x);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateUnaryI64(operation, (x) => ~x);
+                    }
+                    break;
+
+                case Instruction.BitwiseOr:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateBinaryI32(operation, (x, y) => x | y);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateBinaryI64(operation, (x, y) => x | y);
+                    }
+                    break;
+
+                case Instruction.Copy:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateUnaryI32(operation, (x) => x);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateUnaryI64(operation, (x) => x);
+                    }
+                    break;
+
+                case Instruction.Divide:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateBinaryI32(operation, (x, y) => y != 0 ? x / y : 0);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateBinaryI64(operation, (x, y) => y != 0 ? x / y : 0);
+                    }
+                    break;
+
+                case Instruction.DivideUI:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateBinaryI32(operation, (x, y) => y != 0 ? (int)((uint)x / (uint)y) : 0);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateBinaryI64(operation, (x, y) => y != 0 ? (long)((ulong)x / (ulong)y) : 0);
+                    }
+                    break;
+
+                 case Instruction.Multiply:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateBinaryI32(operation, (x, y) => x * y);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateBinaryI64(operation, (x, y) => x * y);
+                    }
+                    break;
+
+                case Instruction.Negate:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateUnaryI32(operation, (x) => -x);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateUnaryI64(operation, (x) => -x);
+                    }
+                    break;
+
+                case Instruction.ShiftLeft:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateBinaryI32(operation, (x, y) => x << y);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateBinaryI64(operation, (x, y) => x << (int)y);
+                    }
+                    break;
+
+                case Instruction.ShiftRightSI:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateBinaryI32(operation, (x, y) => x >> y);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateBinaryI64(operation, (x, y) => x >> (int)y);
+                    }
+                    break;
+
+                case Instruction.ShiftRightUI:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateBinaryI32(operation, (x, y) => (int)((uint)x >> y));
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateBinaryI64(operation, (x, y) => (long)((ulong)x >> (int)y));
+                    }
+                    break;
+
+                case Instruction.SignExtend16:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateUnaryI32(operation, (x) => (short)x);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateUnaryI64(operation, (x) => (short)x);
+                    }
+                    break;
+
+                case Instruction.SignExtend32:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateUnaryI32(operation, (x) => x);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateUnaryI64(operation, (x) => (int)x);
+                    }
+                    break;
+
+                case Instruction.SignExtend8:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateUnaryI32(operation, (x) => (sbyte)x);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateUnaryI64(operation, (x) => (sbyte)x);
+                    }
+                    break;
+
+                case Instruction.Subtract:
+                    if (type == OperandType.I32)
+                    {
+                        EvaluateBinaryI32(operation, (x, y) => x - y);
+                    }
+                    else if (type == OperandType.I64)
+                    {
+                        EvaluateBinaryI64(operation, (x, y) => x - y);
+                    }
+                    break;
+            }
+        }
+
+        private static bool AreAllSourcesConstant(Operation operation)
+        {
+            for (int index = 0; index < operation.SourcesCount; index++)
+            {
+                if (operation.GetSource(index).Kind != OperandKind.Constant)
+                {
+                    return false;
+                }
+            }
+
+            return true;
+        }
+
+        private static void EvaluateUnaryI32(Operation operation, Func<int, int> op)
+        {
+            int x = operation.GetSource(0).AsInt32();
+
+            operation.TurnIntoCopy(Const(op(x)));
+        }
+
+        private static void EvaluateUnaryI64(Operation operation, Func<long, long> op)
+        {
+            long x = operation.GetSource(0).AsInt64();
+
+            operation.TurnIntoCopy(Const(op(x)));
+        }
+
+        private static void EvaluateBinaryI32(Operation operation, Func<int, int, int> op)
+        {
+            int x = operation.GetSource(0).AsInt32();
+            int y = operation.GetSource(1).AsInt32();
+
+            operation.TurnIntoCopy(Const(op(x, y)));
+        }
+
+        private static void EvaluateBinaryI64(Operation operation, Func<long, long, long> op)
+        {
+            long x = operation.GetSource(0).AsInt64();
+            long y = operation.GetSource(1).AsInt64();
+
+            operation.TurnIntoCopy(Const(op(x, y)));
+        }
+    }
+}
+\ No newline at end of file
diff --git a/ARMeilleure/CodeGen/Optimizations/Optimizer.cs b/ARMeilleure/CodeGen/Optimizations/Optimizer.cs
new file mode 100644
index 00000000..c01a8f1e
--- /dev/null
+++ b/ARMeilleure/CodeGen/Optimizations/Optimizer.cs
@@ -0,0 +1,126 @@
+using ARMeilleure.IntermediateRepresentation;
+using ARMeilleure.Translation;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+
+namespace ARMeilleure.CodeGen.Optimizations
+{
+    static class Optimizer
+    {
+        public static void RunPass(ControlFlowGraph cfg)
+        {
+            bool modified;
+
+            do
+            {
+                modified = false;
+
+                foreach (BasicBlock block in cfg.Blocks)
+                {
+                    LinkedListNode<Node> node = block.Operations.First;
+
+                    while (node != null)
+                    {
+                        LinkedListNode<Node> nextNode = node.Next;
+
+                        bool isUnused = IsUnused(node.Value);
+
+                        if (!(node.Value is Operation operation) || isUnused)
+                        {
+                            if (isUnused)
+                            {
+                                RemoveNode(block, node);
+
+                                modified = true;
+                            }
+
+                            node = nextNode;
+
+                            continue;
+                        }
+
+                        ConstantFolding.RunPass(operation);
+
+                        Simplification.RunPass(operation);
+
+                        if (DestIsLocalVar(operation) && IsPropagableCopy(operation))
+                        {
+                            PropagateCopy(operation);
+
+                            RemoveNode(block, node);
+
+                            modified = true;
+                        }
+
+                        node = nextNode;
+                    }
+                }
+            }
+            while (modified);
+        }
+
+        private static void PropagateCopy(Operation copyOp)
+        {
+            // Propagate copy source operand to all uses of the destination operand.
+            Operand dest   = copyOp.Destination;
+            Operand source = copyOp.GetSource(0);
+
+            Node[] uses = dest.Uses.ToArray();
+
+            foreach (Node use in uses)
+            {
+                for (int index = 0; index < use.SourcesCount; index++)
+                {
+                    if (use.GetSource(index) == dest)
+                    {
+                        use.SetSource(index, source);
+                    }
+                }
+            }
+        }
+
+        private static void RemoveNode(BasicBlock block, LinkedListNode<Node> llNode)
+        {
+            // 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;
+
+            for (int index = 0; index < node.SourcesCount; index++)
+            {
+                node.SetSource(index, null);
+            }
+
+            Debug.Assert(node.Destination == null || node.Destination.Uses.Count == 0);
+
+            node.Destination = null;
+        }
+
+        private static bool IsUnused(Node node)
+        {
+            return DestIsLocalVar(node) && node.Destination.Uses.Count == 0 && !HasSideEffects(node);
+        }
+
+        private static bool DestIsLocalVar(Node node)
+        {
+            return node.Destination != null && node.Destination.Kind == OperandKind.LocalVariable;
+        }
+
+        private static bool HasSideEffects(Node node)
+        {
+            return (node is Operation operation) && operation.Instruction == Instruction.Call;
+        }
+
+        private static bool IsPropagableCopy(Operation operation)
+        {
+            if (operation.Instruction != Instruction.Copy)
+            {
+                return false;
+            }
+
+            return operation.Destination.Type == operation.GetSource(0).Type;
+        }
+    }
+}
+\ No newline at end of file
diff --git a/ARMeilleure/CodeGen/Optimizations/Simplification.cs b/ARMeilleure/CodeGen/Optimizations/Simplification.cs
new file mode 100644
index 00000000..cafc025c
--- /dev/null
+++ b/ARMeilleure/CodeGen/Optimizations/Simplification.cs
@@ -0,0 +1,157 @@
+using ARMeilleure.IntermediateRepresentation;
+using System;
+
+using static ARMeilleure.IntermediateRepresentation.OperandHelper;
+
+namespace ARMeilleure.CodeGen.Optimizations
+{
+    static class Simplification
+    {
+        public static void RunPass(Operation operation)
+        {
+            switch (operation.Instruction)
+            {
+                case Instruction.Add:
+                case Instruction.BitwiseExclusiveOr:
+                    TryEliminateBinaryOpComutative(operation, 0);
+                    break;
+
+                case Instruction.BitwiseAnd:
+                    TryEliminateBitwiseAnd(operation);
+                    break;
+
+                case Instruction.BitwiseOr:
+                    TryEliminateBitwiseOr(operation);
+                    break;
+
+                case Instruction.ConditionalSelect:
+                    TryEliminateConditionalSelect(operation);
+                    break;
+
+                case Instruction.Divide:
+                    TryEliminateBinaryOpY(operation, 1);
+                    break;
+
+                case Instruction.Multiply:
+                    TryEliminateBinaryOpComutative(operation, 1);
+                    break;
+
+                case Instruction.ShiftLeft:
+                case Instruction.ShiftRightSI:
+                case Instruction.ShiftRightUI:
+                case Instruction.Subtract:
+                    TryEliminateBinaryOpY(operation, 0);
+                    break;
+            }
+        }
+
+        private static void TryEliminateBitwiseAnd(Operation operation)
+        {
+            // Try to recognize and optimize those 3 patterns (in order):
+            // x & 0xFFFFFFFF == x,          0xFFFFFFFF & y == y,
+            // x & 0x00000000 == 0x00000000, 0x00000000 & y == 0x00000000
+            Operand x = operation.GetSource(0);
+            Operand y = operation.GetSource(1);
+
+            if (IsConstEqual(x, AllOnes(x.Type)))
+            {
+                operation.TurnIntoCopy(y);
+            }
+            else if (IsConstEqual(y, AllOnes(y.Type)))
+            {
+                operation.TurnIntoCopy(x);
+            }
+            else if (IsConstEqual(x, 0) || IsConstEqual(y, 0))
+            {
+                operation.TurnIntoCopy(Const(0));
+            }
+        }
+
+        private static void TryEliminateBitwiseOr(Operation operation)
+        {
+            // Try to recognize and optimize those 3 patterns (in order):
+            // x | 0x00000000 == x,          0x00000000 | y == y,
+            // x | 0xFFFFFFFF == 0xFFFFFFFF, 0xFFFFFFFF | y == 0xFFFFFFFF
+            Operand x = operation.GetSource(0);
+            Operand y = operation.GetSource(1);
+
+            if (IsConstEqual(x, 0))
+            {
+                operation.TurnIntoCopy(y);
+            }
+            else if (IsConstEqual(y, 0))
+            {
+                operation.TurnIntoCopy(x);
+            }
+            else if (IsConstEqual(x, AllOnes(x.Type)) || IsConstEqual(y, AllOnes(y.Type)))
+            {
+                operation.TurnIntoCopy(Const(AllOnes(x.Type)));
+            }
+        }
+
+        private static void TryEliminateBinaryOpY(Operation operation, ulong comparand)
+        {
+            Operand x = operation.GetSource(0);
+            Operand y = operation.GetSource(1);
+
+            if (IsConstEqual(y, comparand))
+            {
+                operation.TurnIntoCopy(x);
+            }
+        }
+
+        private static void TryEliminateBinaryOpComutative(Operation operation, ulong comparand)
+        {
+            Operand x = operation.GetSource(0);
+            Operand y = operation.GetSource(1);
+
+            if (IsConstEqual(x, comparand))
+            {
+                operation.TurnIntoCopy(y);
+            }
+            else if (IsConstEqual(y, comparand))
+            {
+                operation.TurnIntoCopy(x);
+            }
+        }
+
+        private static void TryEliminateConditionalSelect(Operation operation)
+        {
+            Operand cond = operation.GetSource(0);
+
+            if (cond.Kind != OperandKind.Constant)
+            {
+                return;
+            }
+
+            // The condition is constant, we can turn it into a copy, and select
+            // the source based on the condition value.
+            int srcIndex = cond.Value != 0 ? 1 : 2;
+
+            Operand source = operation.GetSource(srcIndex);
+
+            operation.TurnIntoCopy(source);
+        }
+
+        private static bool IsConstEqual(Operand operand, ulong comparand)
+        {
+            if (operand.Kind != OperandKind.Constant || !operand.Type.IsInteger())
+            {
+                return false;
+            }
+
+            return operand.Value == comparand;
+        }
+
+        private static ulong AllOnes(OperandType type)
+        {
+            switch (type)
+            {
+                case OperandType.I32: return ~0U;
+                case OperandType.I64: return ~0UL;
+            }
+
+            throw new ArgumentException("Invalid operand type \"" + type + "\".");
+        }
+    }
+}
+\ No newline at end of file