DFGCFGSimplificationPhase.cpp [plain text]
#include "config.h"
#include "DFGCFGSimplificationPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGBasicBlockInlines.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "DFGValidate.h"
#include "JSCInlines.h"
namespace JSC { namespace DFG {
class CFGSimplificationPhase : public Phase {
public:
CFGSimplificationPhase(Graph& graph)
: Phase(graph, "CFG simplification")
{
}
bool run()
{
DFG_ASSERT(m_graph, nullptr, m_graph.m_form != SSA);
const bool extremeLogging = false;
bool outerChanged = false;
bool innerChanged;
do {
innerChanged = false;
for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
ASSERT(block->isReachable);
switch (block->terminal()->op()) {
case Jump: {
if (block->successor(0)->predecessors.size() == 1) {
ASSERT(block->successor(0)->predecessors[0] == block);
if (extremeLogging)
m_graph.dump();
m_graph.dethread();
mergeBlocks(block, block->successor(0), noBlocks());
innerChanged = outerChanged = true;
break;
}
break;
}
case Branch: {
if (isKnownDirection(block->cfaBranchDirection)) {
bool condition = branchCondition(block->cfaBranchDirection);
BasicBlock* targetBlock = block->successorForCondition(condition);
BasicBlock* jettisonedBlock = block->successorForCondition(!condition);
if (targetBlock->predecessors.size() == 1) {
if (extremeLogging)
m_graph.dump();
m_graph.dethread();
mergeBlocks(block, targetBlock, oneBlock(jettisonedBlock));
} else {
if (extremeLogging)
m_graph.dump();
m_graph.dethread();
Node* terminal = block->terminal();
ASSERT(terminal->isTerminal());
NodeOrigin boundaryNodeOrigin = terminal->origin;
jettisonBlock(block, jettisonedBlock, boundaryNodeOrigin);
block->replaceTerminal(
m_graph, SpecNone, Jump, boundaryNodeOrigin,
OpInfo(targetBlock));
ASSERT(block->terminal());
}
innerChanged = outerChanged = true;
break;
}
if (block->successor(0) == block->successor(1)) {
convertToJump(block, block->successor(0));
innerChanged = outerChanged = true;
break;
}
break;
}
case Switch: {
SwitchData* data = block->terminal()->switchData();
for (unsigned i = 0; i < data->cases.size(); ++i) {
if (data->cases[i].target.block == data->fallThrough.block) {
data->fallThrough.count += data->cases[i].target.count;
data->cases[i--] = data->cases.last();
data->cases.removeLast();
}
}
if (data->cases.isEmpty()) {
convertToJump(block, data->fallThrough.block);
innerChanged = outerChanged = true;
break;
}
Node* terminal = block->terminal();
if (terminal->child1()->hasConstant()) {
FrozenValue* value = terminal->child1()->constant();
TriState found = FalseTriState;
BasicBlock* targetBlock = 0;
for (unsigned i = data->cases.size(); found == FalseTriState && i--;) {
found = data->cases[i].value.strictEqual(value);
if (found == TrueTriState)
targetBlock = data->cases[i].target.block;
}
if (found == MixedTriState)
break;
if (found == FalseTriState)
targetBlock = data->fallThrough.block;
ASSERT(targetBlock);
Vector<BasicBlock*, 1> jettisonedBlocks;
for (BasicBlock* successor : terminal->successors()) {
if (successor != targetBlock)
jettisonedBlocks.append(successor);
}
if (targetBlock->predecessors.size() == 1) {
if (extremeLogging)
m_graph.dump();
m_graph.dethread();
mergeBlocks(block, targetBlock, jettisonedBlocks);
} else {
if (extremeLogging)
m_graph.dump();
m_graph.dethread();
NodeOrigin boundaryNodeOrigin = terminal->origin;
for (unsigned i = jettisonedBlocks.size(); i--;)
jettisonBlock(block, jettisonedBlocks[i], boundaryNodeOrigin);
block->replaceTerminal(
m_graph, SpecNone, Jump, boundaryNodeOrigin, OpInfo(targetBlock));
}
innerChanged = outerChanged = true;
break;
}
break;
}
default:
break;
}
}
if (innerChanged) {
m_graph.invalidateCFG();
m_graph.resetReachability();
m_graph.killUnreachableBlocks();
}
if (Options::validateGraphAtEachPhase())
validate();
} while (innerChanged);
return outerChanged;
}
private:
void convertToJump(BasicBlock* block, BasicBlock* targetBlock)
{
ASSERT(targetBlock);
ASSERT(targetBlock->isReachable);
if (targetBlock->predecessors.size() == 1) {
m_graph.dethread();
mergeBlocks(block, targetBlock, noBlocks());
} else {
Node* branch = block->terminal();
ASSERT(branch->op() == Branch || branch->op() == Switch);
block->replaceTerminal(
m_graph, SpecNone, Jump, branch->origin, OpInfo(targetBlock));
}
}
void keepOperandAlive(BasicBlock* block, BasicBlock* jettisonedBlock, NodeOrigin nodeOrigin, VirtualRegister operand)
{
Node* livenessNode = jettisonedBlock->variablesAtHead.operand(operand);
if (!livenessNode)
return;
NodeType nodeType;
if (livenessNode->flags() & NodeIsFlushed)
nodeType = Flush;
else {
nodeType = PhantomLocal;
}
block->appendNode(
m_graph, SpecNone, nodeType, nodeOrigin,
OpInfo(livenessNode->variableAccessData()));
}
void jettisonBlock(BasicBlock* block, BasicBlock* jettisonedBlock, NodeOrigin boundaryNodeOrigin)
{
for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
keepOperandAlive(block, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForArgument(i));
for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
keepOperandAlive(block, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForLocal(i));
fixJettisonedPredecessors(block, jettisonedBlock);
}
void fixJettisonedPredecessors(BasicBlock* block, BasicBlock* jettisonedBlock)
{
jettisonedBlock->removePredecessor(block);
}
Vector<BasicBlock*, 1> noBlocks()
{
return Vector<BasicBlock*, 1>();
}
Vector<BasicBlock*, 1> oneBlock(BasicBlock* block)
{
Vector<BasicBlock*, 1> result;
result.append(block);
return result;
}
void mergeBlocks(
BasicBlock* firstBlock, BasicBlock* secondBlock,
Vector<BasicBlock*, 1> jettisonedBlocks)
{
Node* terminal = firstBlock->terminal();
ASSERT(terminal->isTerminal());
NodeOrigin boundaryNodeOrigin = terminal->origin;
terminal->remove();
ASSERT(terminal->refCount() == 1);
for (unsigned i = jettisonedBlocks.size(); i--;) {
BasicBlock* jettisonedBlock = jettisonedBlocks[i];
for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
keepOperandAlive(firstBlock, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForArgument(i));
for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
keepOperandAlive(firstBlock, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForLocal(i));
}
for (size_t i = 0; i < secondBlock->phis.size(); ++i)
firstBlock->phis.append(secondBlock->phis[i]);
for (size_t i = 0; i < secondBlock->size(); ++i)
firstBlock->append(secondBlock->at(i));
ASSERT(firstBlock->terminal()->isTerminal());
for (unsigned i = firstBlock->numSuccessors(); i--;) {
BasicBlock* successor = firstBlock->successor(i);
for (unsigned j = 0; j < successor->predecessors.size(); ++j) {
if (successor->predecessors[j] == secondBlock)
successor->predecessors[j] = firstBlock;
}
}
for (unsigned i = jettisonedBlocks.size(); i--;)
fixJettisonedPredecessors(firstBlock, jettisonedBlocks[i]);
firstBlock->valuesAtTail = secondBlock->valuesAtTail;
firstBlock->cfaBranchDirection = secondBlock->cfaBranchDirection;
m_graph.killBlock(secondBlock);
}
};
bool performCFGSimplification(Graph& graph)
{
return runPhase<CFGSimplificationPhase>(graph);
}
} }
#endif // ENABLE(DFG_JIT)