From f60033e0aaf546d7f56a4925b5aeec76709fb851 Mon Sep 17 00:00:00 2001 From: FICTURE7 Date: Sun, 20 Sep 2020 03:00:24 +0400 Subject: Implement block placement (#1549) * Implement block placement Implement a simple pass which re-orders cold blocks at the end of the list of blocks in the CFG. * Set PPTC version * Use Array.Resize Address gdkchan's feedback --- ARMeilleure/Translation/ControlFlowGraph.cs | 25 ++++++++++++++++++------- ARMeilleure/Translation/EmitterContext.cs | 27 +++++++++++++++++---------- ARMeilleure/Translation/PTC/Ptc.cs | 2 +- ARMeilleure/Translation/Translator.cs | 4 ++-- 4 files changed, 38 insertions(+), 20 deletions(-) (limited to 'ARMeilleure/Translation') diff --git a/ARMeilleure/Translation/ControlFlowGraph.cs b/ARMeilleure/Translation/ControlFlowGraph.cs index 34963534..ee1a245e 100644 --- a/ARMeilleure/Translation/ControlFlowGraph.cs +++ b/ARMeilleure/Translation/ControlFlowGraph.cs @@ -7,26 +7,37 @@ namespace ARMeilleure.Translation { class ControlFlowGraph { + private BasicBlock[] _postOrderBlocks; + private int[] _postOrderMap; + public BasicBlock Entry { get; } public IntrusiveList Blocks { get; } - public BasicBlock[] PostOrderBlocks { get; } - public int[] PostOrderMap { get; } + public BasicBlock[] PostOrderBlocks => _postOrderBlocks; + public int[] PostOrderMap => _postOrderMap; public ControlFlowGraph(BasicBlock entry, IntrusiveList blocks) { Entry = entry; Blocks = blocks; - RemoveUnreachableBlocks(blocks); + Update(removeUnreachableBlocks: true); + } + + public void Update(bool removeUnreachableBlocks) + { + if (removeUnreachableBlocks) + { + RemoveUnreachableBlocks(Blocks); + } var visited = new HashSet(); var blockStack = new Stack(); - PostOrderBlocks = new BasicBlock[blocks.Count]; - PostOrderMap = new int[blocks.Count]; + Array.Resize(ref _postOrderBlocks, Blocks.Count); + Array.Resize(ref _postOrderMap, Blocks.Count); - visited.Add(entry); - blockStack.Push(entry); + visited.Add(Entry); + blockStack.Push(Entry); int index = 0; diff --git a/ARMeilleure/Translation/EmitterContext.cs b/ARMeilleure/Translation/EmitterContext.cs index 2261fb87..d85a502b 100644 --- a/ARMeilleure/Translation/EmitterContext.cs +++ b/ARMeilleure/Translation/EmitterContext.cs @@ -20,6 +20,7 @@ namespace ARMeilleure.Translation private BasicBlock _ifBlock; private bool _needsNewBlock; + private BasicBlockFrequency _nextBlockFreq; public EmitterContext() { @@ -27,6 +28,7 @@ namespace ARMeilleure.Translation _irBlocks = new IntrusiveList(); _needsNewBlock = true; + _nextBlockFreq = BasicBlockFrequency.Default; } public Operand Add(Operand op1, Operand op2) @@ -58,24 +60,24 @@ namespace ARMeilleure.Translation { NewNextBlockIfNeeded(); - BranchToLabel(label, uncond: true); + BranchToLabel(label, uncond: true, BasicBlockFrequency.Default); } - public void BranchIf(Operand label, Operand op1, Operand op2, Comparison comp) + public void BranchIf(Operand label, Operand op1, Operand op2, Comparison comp, BasicBlockFrequency falseFreq = default) { Add(Instruction.BranchIf, null, op1, op2, Const((int)comp)); - BranchToLabel(label, uncond: false); + BranchToLabel(label, uncond: false, falseFreq); } - public void BranchIfFalse(Operand label, Operand op1) + public void BranchIfFalse(Operand label, Operand op1, BasicBlockFrequency falseFreq = default) { - BranchIf(label, op1, Const(op1.Type, 0), Comparison.Equal); + BranchIf(label, op1, Const(op1.Type, 0), Comparison.Equal, falseFreq); } - public void BranchIfTrue(Operand label, Operand op1) + public void BranchIfTrue(Operand label, Operand op1, BasicBlockFrequency falseFreq = default) { - BranchIf(label, op1, Const(op1.Type, 0), Comparison.NotEqual); + BranchIf(label, op1, Const(op1.Type, 0), Comparison.NotEqual, falseFreq); } public Operand ByteSwap(Operand op1) @@ -582,7 +584,7 @@ namespace ARMeilleure.Translation return dest; } - private void BranchToLabel(Operand label, bool uncond) + private void BranchToLabel(Operand label, bool uncond, BasicBlockFrequency nextFreq) { if (!_irLabels.TryGetValue(label, out BasicBlock branchBlock)) { @@ -602,10 +604,13 @@ namespace ARMeilleure.Translation } _needsNewBlock = true; + _nextBlockFreq = nextFreq; } - public void MarkLabel(Operand label) + public void MarkLabel(Operand label, BasicBlockFrequency nextFreq = default) { + _nextBlockFreq = nextFreq; + if (_irLabels.TryGetValue(label, out BasicBlock nextBlock)) { nextBlock.Index = _irBlocks.Count; @@ -633,7 +638,7 @@ namespace ARMeilleure.Translation private void NextBlock(BasicBlock nextBlock) { - if (_irBlock != null && _irBlock.SuccessorCount == 0 && !EndsWithUnconditional(_irBlock)) + if (_irBlock?.SuccessorCount == 0 && !EndsWithUnconditional(_irBlock)) { _irBlock.AddSuccessor(nextBlock); @@ -646,8 +651,10 @@ namespace ARMeilleure.Translation } _irBlock = nextBlock; + _irBlock.Frequency = _nextBlockFreq; _needsNewBlock = false; + _nextBlockFreq = BasicBlockFrequency.Default; } private static bool EndsWithUnconditional(BasicBlock block) diff --git a/ARMeilleure/Translation/PTC/Ptc.cs b/ARMeilleure/Translation/PTC/Ptc.cs index ae884ab6..89aeed08 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 = 1535; //! To be incremented manually for each change to the ARMeilleure project. + private const int InternalVersion = 1549; //! 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/Translator.cs b/ARMeilleure/Translation/Translator.cs index 1a02bce0..4448abd7 100644 --- a/ARMeilleure/Translation/Translator.cs +++ b/ARMeilleure/Translation/Translator.cs @@ -301,11 +301,11 @@ namespace ARMeilleure.Translation Operand lblNonZero = Label(); Operand lblExit = Label(); - context.BranchIfTrue(lblNonZero, count); + context.BranchIfTrue(lblNonZero, count, BasicBlockFrequency.Cold); Operand running = context.Call(typeof(NativeInterface).GetMethod(nameof(NativeInterface.CheckSynchronization))); - context.BranchIfTrue(lblExit, running); + context.BranchIfTrue(lblExit, running, BasicBlockFrequency.Cold); context.Return(Const(0L)); -- cgit v1.2.3