Relax block ordering constraints (#1535)

* Relax block ordering constraints

Before `block.Next` had to follow `block.ListNext`, now it does not.
Instead `CodeGenerator` will now emit the necessary jump instructions
to ensure control flow.

This makes control flow and block order modifications easier. It also
eliminates some simple cases of redundant branches.

* Set PPTC version

5 files changed, 67 insertions, 84 deletions

diff --git a/ARMeilleure/Translation/ControlFlowGraph.cs b/ARMeilleure/Translation/ControlFlowGraph.cs
index 16b406ab..34963534 100644
--- a/ARMeilleure/Translation/ControlFlowGraph.cs
+++ b/ARMeilleure/Translation/ControlFlowGraph.cs
@@ -8,47 +8,48 @@ namespace ARMeilleure.Translation
     class ControlFlowGraph
     {
         public BasicBlock Entry { get; }
-
         public IntrusiveList<BasicBlock> Blocks { get; }
-
         public BasicBlock[] PostOrderBlocks { get; }
-
         public int[] PostOrderMap { get; }
 
         public ControlFlowGraph(BasicBlock entry, IntrusiveList<BasicBlock> blocks)
         {
-            Entry  = entry;
+            Entry = entry;
             Blocks = blocks;
 
             RemoveUnreachableBlocks(blocks);
 
-            HashSet<BasicBlock> visited = new HashSet<BasicBlock>();
-
-            Stack<BasicBlock> blockStack = new Stack<BasicBlock>();
+            var visited = new HashSet<BasicBlock>();
+            var blockStack = new Stack<BasicBlock>();
 
             PostOrderBlocks = new BasicBlock[blocks.Count];
-
             PostOrderMap = new int[blocks.Count];
 
             visited.Add(entry);
-
             blockStack.Push(entry);
 
             int index = 0;
 
             while (blockStack.TryPop(out BasicBlock block))
             {
-                if (block.Next != null && visited.Add(block.Next))
-                {
-                    blockStack.Push(block);
-                    blockStack.Push(block.Next);
-                }
-                else if (block.Branch != null && visited.Add(block.Branch))
+                bool visitedNew = false;
+
+                for (int i = 0; i < block.SuccessorCount; i++)
                 {
-                    blockStack.Push(block);
-                    blockStack.Push(block.Branch);
+                    BasicBlock succ = block.GetSuccessor(i);
+
+                    if (visited.Add(succ))
+                    {
+                        blockStack.Push(block);
+                        blockStack.Push(succ);
+
+                        visitedNew = true;
+
+                        break;
+                    }
                 }
-                else
+
+                if (!visitedNew)
                 {
                     PostOrderMap[block.Index] = index;
 
@@ -59,26 +60,24 @@ namespace ARMeilleure.Translation
 
         private void RemoveUnreachableBlocks(IntrusiveList<BasicBlock> blocks)
         {
-            HashSet<BasicBlock> visited = new HashSet<BasicBlock>();
-
-            Queue<BasicBlock> workQueue = new Queue<BasicBlock>();
+            var visited = new HashSet<BasicBlock>();
+            var workQueue = new Queue<BasicBlock>();
 
             visited.Add(Entry);
-
             workQueue.Enqueue(Entry);
 
             while (workQueue.TryDequeue(out BasicBlock block))
             {
                 Debug.Assert(block.Index != -1, "Invalid block index.");
 
-                if (block.Next != null && visited.Add(block.Next))
+                for (int i = 0; i < block.SuccessorCount; i++)
                 {
-                    workQueue.Enqueue(block.Next);
-                }
+                    BasicBlock succ = block.GetSuccessor(i);
 
-                if (block.Branch != null && visited.Add(block.Branch))
-                {
-                    workQueue.Enqueue(block.Branch);
+                    if (visited.Add(succ))
+                    {
+                        workQueue.Enqueue(succ);
+                    }
                 }
             }
 
@@ -93,8 +92,10 @@ namespace ARMeilleure.Translation
 
                     if (!visited.Contains(block))
                     {
-                        block.Next = null;
-                        block.Branch = null;
+                        while (block.SuccessorCount > 0)
+                        {
+                            block.RemoveSuccessor(index: block.SuccessorCount - 1);
+                        }
 
                         blocks.Remove(block);
                     }
@@ -112,14 +113,12 @@ namespace ARMeilleure.Translation
         {
             BasicBlock splitBlock = new BasicBlock(Blocks.Count);
 
-            if (predecessor.Next == successor)
+            for (int i = 0; i < predecessor.SuccessorCount; i++)
             {
-                predecessor.Next = splitBlock;
-            }
-
-            if (predecessor.Branch == successor)
-            {
-                predecessor.Branch = splitBlock;
+                if (predecessor.GetSuccessor(i) == successor)
+                {
+                    predecessor.SetSuccessor(i, splitBlock);
+                }
             }
 
             if (splitBlock.Predecessors.Count == 0)
@@ -127,26 +126,7 @@ namespace ARMeilleure.Translation
                 throw new ArgumentException("Predecessor and successor are not connected.");
             }
 
-            // Insert the new block on the list of blocks.
-            BasicBlock succPrev = successor.ListPrevious;
-
-            if (succPrev != null && succPrev != predecessor && succPrev.Next == successor)
-            {
-                // Can't insert after the predecessor or before the successor.
-                // Here, we insert it before the successor by also spliting another
-                // edge (the one between the block before "successor" and "successor").
-                BasicBlock splitBlock2 = new BasicBlock(splitBlock.Index + 1);
-
-                succPrev.Next = splitBlock2;
-
-                splitBlock2.Branch = successor;
-
-                splitBlock2.Operations.AddLast(OperationHelper.Operation(Instruction.Branch, null));
-
-                Blocks.AddBefore(successor, splitBlock2);
-            }
-
-            splitBlock.Next = successor;
+            splitBlock.AddSuccessor(successor);
 
             Blocks.AddBefore(successor, splitBlock);
 
diff --git a/ARMeilleure/Translation/EmitterContext.cs b/ARMeilleure/Translation/EmitterContext.cs
index a6cc55df..2261fb87 100644
--- a/ARMeilleure/Translation/EmitterContext.cs
+++ b/ARMeilleure/Translation/EmitterContext.cs
@@ -13,18 +13,17 @@ namespace ARMeilleure.Translation
 
     class EmitterContext
     {
-        private Dictionary<Operand, BasicBlock> _irLabels;
-
-        private IntrusiveList<BasicBlock> _irBlocks;
+        private readonly Dictionary<Operand, BasicBlock> _irLabels;
+        private readonly IntrusiveList<BasicBlock> _irBlocks;
 
         private BasicBlock _irBlock;
+        private BasicBlock _ifBlock;
 
         private bool _needsNewBlock;
 
         public EmitterContext()
         {
             _irLabels = new Dictionary<Operand, BasicBlock>();
-
             _irBlocks = new IntrusiveList<BasicBlock>();
 
             _needsNewBlock = true;
@@ -57,16 +56,16 @@ namespace ARMeilleure.Translation
 
         public void Branch(Operand label)
         {
-            Add(Instruction.Branch, null);
+            NewNextBlockIfNeeded();
 
-            BranchToLabel(label);
+            BranchToLabel(label, uncond: true);
         }
 
         public void BranchIf(Operand label, Operand op1, Operand op2, Comparison comp)
         {
             Add(Instruction.BranchIf, null, op1, op2, Const((int)comp));
 
-            BranchToLabel(label);
+            BranchToLabel(label, uncond: false);
         }
 
         public void BranchIfFalse(Operand label, Operand op1)
@@ -574,10 +573,7 @@ namespace ARMeilleure.Translation
 
         private Operand Add(Intrinsic intrin, Operand dest, params Operand[] sources)
         {
-            if (_needsNewBlock)
-            {
-                NewNextBlock();
-            }
+            NewNextBlockIfNeeded();
 
             IntrinsicOperation operation = new IntrinsicOperation(intrin, dest, sources);
 
@@ -586,7 +582,7 @@ namespace ARMeilleure.Translation
             return dest;
         }
 
-        private void BranchToLabel(Operand label)
+        private void BranchToLabel(Operand label, bool uncond)
         {
             if (!_irLabels.TryGetValue(label, out BasicBlock branchBlock))
             {
@@ -595,7 +591,15 @@ namespace ARMeilleure.Translation
                 _irLabels.Add(label, branchBlock);
             }
 
-            _irBlock.Branch = branchBlock;
+            if (uncond)
+            {
+                _irBlock.AddSuccessor(branchBlock);
+            }
+            else
+            {
+                // Defer registration of successor to _irBlock so that the order of successors is correct.
+                _ifBlock = branchBlock;
+            }
 
             _needsNewBlock = true;
         }
@@ -629,9 +633,16 @@ namespace ARMeilleure.Translation
 
         private void NextBlock(BasicBlock nextBlock)
         {
-            if (_irBlock != null && !EndsWithUnconditional(_irBlock))
+            if (_irBlock != null && _irBlock.SuccessorCount == 0 && !EndsWithUnconditional(_irBlock))
             {
-                _irBlock.Next = nextBlock;
+                _irBlock.AddSuccessor(nextBlock);
+
+                if (_ifBlock != null)
+                {
+                    _irBlock.AddSuccessor(_ifBlock);
+
+                    _ifBlock = null;
+                }
             }
 
             _irBlock = nextBlock;
@@ -642,8 +653,7 @@ namespace ARMeilleure.Translation
         private static bool EndsWithUnconditional(BasicBlock block)
         {
             return block.Operations.Last is Operation lastOp &&
-                   (lastOp.Instruction == Instruction.Branch ||
-                    lastOp.Instruction == Instruction.Return ||
+                   (lastOp.Instruction == Instruction.Return ||
                     lastOp.Instruction == Instruction.Tailcall);
         }
 
diff --git a/ARMeilleure/Translation/PTC/Ptc.cs b/ARMeilleure/Translation/PTC/Ptc.cs
index eebf8075..ae884ab6 100644
--- a/ARMeilleure/Translation/PTC/Ptc.cs
+++ b/ARMeilleure/Translation/PTC/Ptc.cs
@@ -21,7 +21,7 @@ namespace ARMeilleure.Translation.PTC
     {
         private const string HeaderMagic = "PTChd";
 
-        private const int InternalVersion = 1537; //! To be incremented manually for each change to the ARMeilleure project.
+        private const int InternalVersion = 1535; //! To be incremented manually for each change to the ARMeilleure project.
 
         private const string ActualDir = "0";
         private const string BackupDir = "1";
diff --git a/ARMeilleure/Translation/RegisterUsage.cs b/ARMeilleure/Translation/RegisterUsage.cs
index d5124285..6a21ae2a 100644
--- a/ARMeilleure/Translation/RegisterUsage.cs
+++ b/ARMeilleure/Translation/RegisterUsage.cs
@@ -171,14 +171,9 @@ namespace ARMeilleure.Translation
 
                     RegisterMask inputs = localInputs[block.Index];
 
-                    if (block.Next != null)
+                    for (int i = 0; i < block.SuccessorCount; i++)
                     {
-                        inputs |= globalInputs[block.Next.Index];
-                    }
-
-                    if (block.Branch != null)
-                    {
-                        inputs |= globalInputs[block.Branch.Index];
+                        inputs |= globalInputs[block.GetSuccessor(i).Index];
                     }
 
                     inputs &= ~globalCmnOutputs[block.Index];
diff --git a/ARMeilleure/Translation/Translator.cs b/ARMeilleure/Translation/Translator.cs
index d1404796..1a02bce0 100644
--- a/ARMeilleure/Translation/Translator.cs
+++ b/ARMeilleure/Translation/Translator.cs
@@ -309,8 +309,6 @@ namespace ARMeilleure.Translation
 
             context.Return(Const(0L));
 
-            context.Branch(lblExit);
-
             context.MarkLabel(lblNonZero);
 
             count = context.Subtract(count, Const(1));