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

3 files changed, 26 insertions, 37 deletions

diff --git a/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs
index 21470a66..898cc1db 100644
--- a/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs
+++ b/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs
@@ -427,18 +427,5 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
         {
             return local.Assignments.Count + local.Uses.Count;
         }
-
-        private static IEnumerable<BasicBlock> Successors(BasicBlock block)
-        {
-            if (block.Next != null)
-            {
-                yield return block.Next;
-            }
-
-            if (block.Branch != null)
-            {
-                yield return block.Branch;
-            }
-        }
     }
 }
\ No newline at end of file
diff --git a/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs
index 01bb9554..71739d43 100644
--- a/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs
+++ b/ARMeilleure/CodeGen/RegisterAllocators/LinearScanAllocator.cs
@@ -626,16 +626,11 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
                     continue;
                 }
 
-                bool hasSingleOrNoSuccessor = block.Next == null || block.Branch == null;
+                bool hasSingleOrNoSuccessor = block.SuccessorCount <= 1;
 
-                for (int i = 0; i < 2; i++)
+                for (int i = 0; i < block.SuccessorCount; i++)
                 {
-                    // This used to use an enumerable, but it ended up generating a lot of garbage, so now it is a loop.
-                    BasicBlock successor = (i == 0) ? block.Next : block.Branch;
-                    if (successor == null)
-                    {
-                        continue;
-                    }
+                    BasicBlock successor = block.GetSuccessor(i);
 
                     int succIndex = successor.Index;
 
@@ -643,7 +638,7 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
                     // (the successor before the split) should be right after it.
                     if (IsSplitEdgeBlock(successor))
                     {
-                        succIndex = FirstSuccessor(successor).Index;
+                        succIndex = successor.GetSuccessor(0).Index;
                     }
 
                     CopyResolver copyResolver = new CopyResolver();
@@ -883,10 +878,11 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
 
                     BitMap liveOut = blkLiveOut[block.Index];
 
-                    if ((block.Next != null && liveOut.Set(blkLiveIn[block.Next.Index])) || 
-                        (block.Branch != null && liveOut.Set(blkLiveIn[block.Branch.Index])))
+                    for (int i = 0; i < block.SuccessorCount; i++)
                     {
-                        modified = true;
+                        BasicBlock succ = block.GetSuccessor(i);
+
+                        modified |= liveOut.Set(blkLiveIn[succ.Index]);
                     }
 
                     BitMap liveIn = blkLiveIn[block.Index];
@@ -1002,11 +998,6 @@ namespace ARMeilleure.CodeGen.RegisterAllocators
             return (register.Index << 1) | (register.Type == RegisterType.Vector ? 1 : 0);
         }
 
-        private static BasicBlock FirstSuccessor(BasicBlock block)
-        {
-            return block.Next ?? block.Branch;
-        }
-
         private static IEnumerable<Node> BottomOperations(BasicBlock block)
         {
             Node node = block.Operations.Last;
diff --git a/ARMeilleure/CodeGen/X86/CodeGenerator.cs b/ARMeilleure/CodeGen/X86/CodeGenerator.cs
index f2d4c462..a51f4a13 100644
--- a/ARMeilleure/CodeGen/X86/CodeGenerator.cs
+++ b/ARMeilleure/CodeGen/X86/CodeGenerator.cs
@@ -32,7 +32,6 @@ namespace ARMeilleure.CodeGen.X86
             Add(Instruction.BitwiseExclusiveOr,      GenerateBitwiseExclusiveOr);
             Add(Instruction.BitwiseNot,              GenerateBitwiseNot);
             Add(Instruction.BitwiseOr,               GenerateBitwiseOr);
-            Add(Instruction.Branch,                  GenerateBranch);
             Add(Instruction.BranchIf,                GenerateBranchIf);
             Add(Instruction.ByteSwap,                GenerateByteSwap);
             Add(Instruction.Call,                    GenerateCall);
@@ -168,6 +167,23 @@ namespace ARMeilleure.CodeGen.X86
                             GenerateOperation(context, operation);
                         }
                     }
+
+                    if (block.SuccessorCount == 0)
+                    {
+                        // The only blocks which can have 0 successors are exit blocks.
+                        Debug.Assert(block.Operations.Last is Operation operation &&
+                                     (operation.Instruction == Instruction.Tailcall ||
+                                      operation.Instruction == Instruction.Return));
+                    }
+                    else
+                    {
+                        BasicBlock succ = block.GetSuccessor(0);
+
+                        if (succ != block.ListNext)
+                        {
+                            context.JumpTo(succ);
+                        }
+                    }
                 }
 
                 Logger.EndPass(PassName.CodeGeneration);
@@ -512,11 +528,6 @@ namespace ARMeilleure.CodeGen.X86
             context.Assembler.Or(dest, src2, dest.Type);
         }
 
-        private static void GenerateBranch(CodeGenContext context, Operation operation)
-        {
-            context.JumpTo(context.CurrBlock.Branch);
-        }
-
         private static void GenerateBranchIf(CodeGenContext context, Operation operation)
         {
             Operand comp = operation.GetSource(2);
@@ -527,7 +538,7 @@ namespace ARMeilleure.CodeGen.X86
 
             GenerateCompareCommon(context, operation);
 
-            context.JumpTo(cond, context.CurrBlock.Branch);
+            context.JumpTo(cond, context.CurrBlock.GetSuccessor(1));
         }
 
         private static void GenerateByteSwap(CodeGenContext context, Operation operation)