#include "config.h"
#include "DFGLICMPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGAbstractInterpreterInlines.h"
#include "DFGAtTailAbstractState.h"
#include "DFGBasicBlockInlines.h"
#include "DFGClobberSet.h"
#include "DFGClobberize.h"
#include "DFGControlEquivalenceAnalysis.h"
#include "DFGEdgeDominates.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGMayExit.h"
#include "DFGNaturalLoops.h"
#include "DFGPhase.h"
#include "DFGSafeToExecute.h"
#include "JSCInlines.h"
namespace JSC { namespace DFG {
namespace {
struct LoopData {
LoopData()
: preHeader(nullptr)
{
}
ClobberSet writes;
BasicBlock* preHeader;
};
}
class LICMPhase : public Phase {
static const bool verbose = false;
public:
LICMPhase(Graph& graph)
: Phase(graph, "LICM")
, m_state(graph)
, m_interpreter(graph, m_state)
{
}
bool run()
{
DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
m_graph.ensureDominators();
m_graph.ensureNaturalLoops();
m_graph.ensureControlEquivalenceAnalysis();
if (verbose) {
dataLog("Graph before LICM:\n");
m_graph.dump();
}
m_data.resize(m_graph.m_naturalLoops->numLoops());
for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
if (!block->cfaHasVisited)
continue;
const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
if (!loop)
continue;
LoopData& data = m_data[loop->index()];
for (auto* node : *block) {
if (node->op() == ForceOSRExit)
break;
addWrites(m_graph, node, data.writes);
}
}
for (unsigned loopIndex = m_graph.m_naturalLoops->numLoops(); loopIndex--;) {
const NaturalLoop& loop = m_graph.m_naturalLoops->loop(loopIndex);
LoopData& data = m_data[loop.index()];
for (
const NaturalLoop* outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(loop);
outerLoop;
outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(*outerLoop))
m_data[outerLoop->index()].writes.addAll(data.writes);
BasicBlock* header = loop.header();
BasicBlock* preHeader = nullptr;
unsigned numberOfPreHeaders = 0;
DFG_ASSERT(m_graph, header->at(0), header->predecessors.size() > 1);
for (unsigned i = header->predecessors.size(); i--;) {
BasicBlock* predecessor = header->predecessors[i];
if (m_graph.m_dominators->dominates(header, predecessor))
continue;
preHeader = predecessor;
++numberOfPreHeaders;
}
if (numberOfPreHeaders != 1)
continue;
DFG_ASSERT(m_graph, preHeader->terminal(), preHeader->terminal()->op() == Jump);
if (!preHeader->terminal()->origin.exitOK)
continue;
data.preHeader = preHeader;
}
m_graph.initializeNodeOwners();
Vector<const NaturalLoop*> loopStack;
bool changed = false;
for (BasicBlock* block : m_graph.blocksInPreOrder()) {
const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
if (!loop)
continue;
loopStack.resize(0);
for (
const NaturalLoop* current = loop;
current;
current = m_graph.m_naturalLoops->innerMostOuterLoop(*current))
loopStack.append(current);
if (verbose) {
dataLog(
"Attempting to hoist out of block ", *block, " in loops:\n");
for (unsigned stackIndex = loopStack.size(); stackIndex--;) {
dataLog(
" ", *loopStack[stackIndex], ", which writes ",
m_data[loopStack[stackIndex]->index()].writes, "\n");
}
}
for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
Node*& nodeRef = block->at(nodeIndex);
if (doesWrites(m_graph, nodeRef)) {
if (verbose)
dataLog(" Not hoisting ", nodeRef, " because it writes things.\n");
continue;
}
for (unsigned stackIndex = loopStack.size(); stackIndex--;)
changed |= attemptHoist(block, nodeRef, loopStack[stackIndex]);
}
}
return changed;
}
private:
bool attemptHoist(BasicBlock* fromBlock, Node*& nodeRef, const NaturalLoop* loop)
{
Node* node = nodeRef;
LoopData& data = m_data[loop->index()];
if (!data.preHeader) {
if (verbose)
dataLog(" Not hoisting ", node, " because the pre-header is invalid.\n");
return false;
}
if (!data.preHeader->cfaDidFinish) {
if (verbose)
dataLog(" Not hoisting ", node, " because CFA is invalid.\n");
return false;
}
if (!edgesDominate(m_graph, node, data.preHeader)) {
if (verbose) {
dataLog(
" Not hoisting ", node, " because it isn't loop invariant.\n");
}
return false;
}
if (readsOverlap(m_graph, node, data.writes)) {
if (verbose) {
dataLog(
" Not hoisting ", node,
" because it reads things that the loop writes.\n");
}
return false;
}
m_state.initializeTo(data.preHeader);
if (!safeToExecute(m_state, m_graph, node)) {
if (verbose) {
dataLog(
" Not hoisting ", node, " because it isn't safe to execute.\n");
}
return false;
}
NodeOrigin originalOrigin = node->origin;
bool addsBlindSpeculation = mayExit(m_graph, node, m_state)
&& !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
if (addsBlindSpeculation
&& m_graph.baselineCodeBlockFor(originalOrigin.semantic)->hasExitSite(FrequentExitSite(HoistingFailed))) {
if (verbose) {
dataLog(
" Not hoisting ", node, " because it may exit and the pre-header (",
*data.preHeader, ") is not control equivalent to the node's original block (",
*fromBlock, ") and hoisting had previously failed.\n");
}
return false;
}
if (verbose) {
dataLog(
" Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
"\n");
}
data.preHeader->insertBeforeTerminal(node);
node->owner = data.preHeader;
NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
node->origin = terminalOrigin.withSemantic(node->origin.semantic);
node->origin.wasHoisted |= addsBlindSpeculation;
for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
BasicBlock* subBlock = loop->at(bodyIndex);
const NaturalLoop* subLoop = m_graph.m_naturalLoops->headerOf(subBlock);
if (!subLoop)
continue;
BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
if (!subPreHeader)
continue;
if (!subPreHeader->cfaDidFinish)
continue;
m_state.initializeTo(subPreHeader);
m_interpreter.execute(node);
}
DFG_ASSERT(m_graph, node, !(node->flags() & NodeHasVarArgs));
nodeRef = m_graph.addNode(Check, originalOrigin, node->children);
return true;
}
AtTailAbstractState m_state;
AbstractInterpreter<AtTailAbstractState> m_interpreter;
Vector<LoopData> m_data;
};
bool performLICM(Graph& graph)
{
return runPhase<LICMPhase>(graph);
}
} }
#endif // ENABLE(DFG_JIT)