aboutsummaryrefslogtreecommitdiff
path: root/ARMeilleure/Translation/ControlFlowGraph.cs
diff options
context:
space:
mode:
authorTSR Berry <20988865+TSRBerry@users.noreply.github.com>2023-04-08 01:22:00 +0200
committerMary <thog@protonmail.com>2023-04-27 23:51:14 +0200
commitcee712105850ac3385cd0091a923438167433f9f (patch)
tree4a5274b21d8b7f938c0d0ce18736d3f2993b11b1 /ARMeilleure/Translation/ControlFlowGraph.cs
parentcd124bda587ef09668a971fa1cac1c3f0cfc9f21 (diff)
Move solution and projects to src
Diffstat (limited to 'ARMeilleure/Translation/ControlFlowGraph.cs')
-rw-r--r--ARMeilleure/Translation/ControlFlowGraph.cs155
1 files changed, 0 insertions, 155 deletions
diff --git a/ARMeilleure/Translation/ControlFlowGraph.cs b/ARMeilleure/Translation/ControlFlowGraph.cs
deleted file mode 100644
index c935f152..00000000
--- a/ARMeilleure/Translation/ControlFlowGraph.cs
+++ /dev/null
@@ -1,155 +0,0 @@
-using ARMeilleure.IntermediateRepresentation;
-using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-
-namespace ARMeilleure.Translation
-{
- class ControlFlowGraph
- {
- private BasicBlock[] _postOrderBlocks;
- private int[] _postOrderMap;
-
- public int LocalsCount { get; private set; }
- public BasicBlock Entry { get; }
- public IntrusiveList<BasicBlock> Blocks { get; }
- public BasicBlock[] PostOrderBlocks => _postOrderBlocks;
- public int[] PostOrderMap => _postOrderMap;
-
- public ControlFlowGraph(BasicBlock entry, IntrusiveList<BasicBlock> blocks, int localsCount)
- {
- Entry = entry;
- Blocks = blocks;
- LocalsCount = localsCount;
-
- Update();
- }
-
- public Operand AllocateLocal(OperandType type)
- {
- Operand result = Operand.Factory.Local(type);
-
- result.NumberLocal(++LocalsCount);
-
- return result;
- }
-
- public void Update()
- {
- RemoveUnreachableBlocks(Blocks);
-
- var visited = new HashSet<BasicBlock>();
- var blockStack = new Stack<BasicBlock>();
-
- Array.Resize(ref _postOrderBlocks, Blocks.Count);
- Array.Resize(ref _postOrderMap, Blocks.Count);
-
- visited.Add(Entry);
- blockStack.Push(Entry);
-
- int index = 0;
-
- while (blockStack.TryPop(out BasicBlock block))
- {
- bool visitedNew = false;
-
- for (int i = 0; i < block.SuccessorsCount; i++)
- {
- BasicBlock succ = block.GetSuccessor(i);
-
- if (visited.Add(succ))
- {
- blockStack.Push(block);
- blockStack.Push(succ);
-
- visitedNew = true;
-
- break;
- }
- }
-
- if (!visitedNew)
- {
- PostOrderMap[block.Index] = index;
-
- PostOrderBlocks[index++] = block;
- }
- }
- }
-
- private void RemoveUnreachableBlocks(IntrusiveList<BasicBlock> blocks)
- {
- 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.");
-
- for (int i = 0; i < block.SuccessorsCount; i++)
- {
- BasicBlock succ = block.GetSuccessor(i);
-
- if (visited.Add(succ))
- {
- workQueue.Enqueue(succ);
- }
- }
- }
-
- if (visited.Count < blocks.Count)
- {
- // Remove unreachable blocks and renumber.
- int index = 0;
-
- for (BasicBlock block = blocks.First; block != null;)
- {
- BasicBlock nextBlock = block.ListNext;
-
- if (!visited.Contains(block))
- {
- while (block.SuccessorsCount > 0)
- {
- block.RemoveSuccessor(index: block.SuccessorsCount - 1);
- }
-
- blocks.Remove(block);
- }
- else
- {
- block.Index = index++;
- }
-
- block = nextBlock;
- }
- }
- }
-
- public BasicBlock SplitEdge(BasicBlock predecessor, BasicBlock successor)
- {
- BasicBlock splitBlock = new BasicBlock(Blocks.Count);
-
- for (int i = 0; i < predecessor.SuccessorsCount; i++)
- {
- if (predecessor.GetSuccessor(i) == successor)
- {
- predecessor.SetSuccessor(i, splitBlock);
- }
- }
-
- if (splitBlock.Predecessors.Count == 0)
- {
- throw new ArgumentException("Predecessor and successor are not connected.");
- }
-
- splitBlock.AddSuccessor(successor);
-
- Blocks.AddBefore(successor, splitBlock);
-
- return splitBlock;
- }
- }
-} \ No newline at end of file