AirOptimizeBlockOrder.cpp [plain text]
#include "config.h"
#include "AirOptimizeBlockOrder.h"
#if ENABLE(B3_JIT)
#include "AirBlockWorklist.h"
#include "AirCode.h"
#include "AirInstInlines.h"
#include "AirPhaseScope.h"
#include <wtf/BubbleSort.h>
namespace JSC { namespace B3 { namespace Air {
namespace {
class SortedSuccessors {
public:
SortedSuccessors()
{
}
void append(BasicBlock* block)
{
m_successors.append(block);
}
void process(BlockWorklist& worklist)
{
bubbleSort(
m_successors.begin(), m_successors.end(),
[] (BasicBlock* left, BasicBlock* right) {
return left->frequency() < right->frequency();
});
for (unsigned i = 0; i < m_successors.size(); ++i)
worklist.push(m_successors[i]);
m_successors.shrink(0);
}
private:
Vector<BasicBlock*, 2> m_successors;
};
}
Vector<BasicBlock*> blocksInOptimizedOrder(Code& code)
{
Vector<BasicBlock*> blocksInOrder;
BlockWorklist fastWorklist;
SortedSuccessors sortedSuccessors;
SortedSuccessors sortedSlowSuccessors;
RELEASE_ASSERT(code.numEntrypoints());
auto appendSuccessor = [&] (const FrequentedBlock& block) {
if (block.isRare())
sortedSlowSuccessors.append(block.block());
else
sortedSuccessors.append(block.block());
};
for (unsigned i = 1; i < code.numEntrypoints(); ++i)
appendSuccessor(code.entrypoint(i));
fastWorklist.push(code.entrypoint(0).block());
while (BasicBlock* block = fastWorklist.pop()) {
blocksInOrder.append(block);
for (FrequentedBlock& successor : block->successors())
appendSuccessor(successor);
sortedSuccessors.process(fastWorklist);
}
BlockWorklist slowWorklist;
sortedSlowSuccessors.process(slowWorklist);
while (BasicBlock* block = slowWorklist.pop()) {
if (fastWorklist.saw(block))
continue;
blocksInOrder.append(block);
for (BasicBlock* successor : block->successorBlocks())
sortedSuccessors.append(successor);
sortedSuccessors.process(slowWorklist);
}
ASSERT(fastWorklist.isEmpty());
ASSERT(slowWorklist.isEmpty());
return blocksInOrder;
}
void optimizeBlockOrder(Code& code)
{
PhaseScope phaseScope(code, "optimizeBlockOrder");
Vector<BasicBlock*> blocksInOrder = blocksInOptimizedOrder(code);
for (auto& entry : code.blockList())
entry.release();
code.blockList().shrink(0);
for (unsigned i = 0; i < blocksInOrder.size(); ++i) {
BasicBlock* block = blocksInOrder[i];
block->setIndex(i);
code.blockList().append(std::unique_ptr<BasicBlock>(block));
}
for (BasicBlock* block : code) {
Inst& branch = block->last();
switch (branch.kind.opcode) {
case Branch8:
case Branch32:
case Branch64:
case BranchTest8:
case BranchTest32:
case BranchTest64:
case BranchFloat:
case BranchDouble:
case BranchAdd32:
case BranchAdd64:
case BranchMul32:
case BranchMul64:
case BranchSub32:
case BranchSub64:
case BranchNeg32:
case BranchNeg64:
case BranchAtomicStrongCAS8:
case BranchAtomicStrongCAS16:
case BranchAtomicStrongCAS32:
case BranchAtomicStrongCAS64:
if (code.findNextBlock(block) == block->successorBlock(0) && branch.args[0].isInvertible()) {
std::swap(block->successor(0), block->successor(1));
branch.args[0] = branch.args[0].inverted();
}
break;
default:
break;
}
}
}
} } }
#endif // ENABLE(B3_JIT)