From 36ec1bc6c023811235d9f5fb664feff09bc7b4f7 Mon Sep 17 00:00:00 2001
From: FICTURE7 <FICTURE7@gmail.com>
Date: Sat, 12 Sep 2020 19:32:53 +0400
Subject: 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
---
ARMeilleure/Translation/ControlFlowGraph.cs | 94 ++++++++++++-----------------
1 file changed, 37 insertions(+), 57 deletions(-)
(limited to 'ARMeilleure/Translation/ControlFlowGraph.cs')
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);
--
cgit v1.2.3-70-g09d2