diff options
| author | FICTURE7 <FICTURE7@gmail.com> | 2020-09-12 19:32:53 +0400 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2020-09-12 12:32:53 -0300 |
| commit | 36ec1bc6c023811235d9f5fb664feff09bc7b4f7 (patch) | |
| tree | 98d74ad92cdce8294bb5116bf7cd06acb55ff9da /ARMeilleure/Translation/ControlFlowGraph.cs | |
| parent | 3d055da5fc77f462e9c7099e08570213c0220cd4 (diff) | |
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
Diffstat (limited to 'ARMeilleure/Translation/ControlFlowGraph.cs')
| -rw-r--r-- | ARMeilleure/Translation/ControlFlowGraph.cs | 94 |
1 files changed, 37 insertions, 57 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); |