#include "config.h"
#include "DFGCSEPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGGraph.h"
#include "DFGPhase.h"
namespace JSC { namespace DFG {
class CSEPhase : public Phase {
public:
CSEPhase(Graph& graph)
: Phase(graph, "common subexpression elimination")
{
m_replacements.resize(m_graph.size());
for (unsigned i = 0; i < m_graph.size(); ++i)
m_replacements[i] = NoNode;
}
void run()
{
for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
performBlockCSE(*m_graph.m_blocks[block]);
}
private:
NodeIndex canonicalize(NodeIndex nodeIndex)
{
if (nodeIndex == NoNode)
return NoNode;
if (m_graph[nodeIndex].op() == ValueToInt32)
nodeIndex = m_graph[nodeIndex].child1().index();
return nodeIndex;
}
NodeIndex canonicalize(Edge nodeUse)
{
return canonicalize(nodeUse.indexUnchecked());
}
unsigned endIndexForPureCSE()
{
unsigned result = m_lastSeen[m_graph[m_compileIndex].op()];
if (result == UINT_MAX)
result = 0;
else
result++;
ASSERT(result <= m_indexInBlock);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" limit %u: ", result);
#endif
return result;
}
NodeIndex pureCSE(Node& node)
{
NodeIndex child1 = canonicalize(node.child1());
NodeIndex child2 = canonicalize(node.child2());
NodeIndex child3 = canonicalize(node.child3());
for (unsigned i = endIndexForPureCSE(); i--;) {
NodeIndex index = m_currentBlock->at(i);
if (index == child1 || index == child2 || index == child3)
break;
Node& otherNode = m_graph[index];
if (node.op() != otherNode.op())
continue;
if (node.arithNodeFlags() != otherNode.arithNodeFlags())
continue;
NodeIndex otherChild = canonicalize(otherNode.child1());
if (otherChild == NoNode)
return index;
if (otherChild != child1)
continue;
otherChild = canonicalize(otherNode.child2());
if (otherChild == NoNode)
return index;
if (otherChild != child2)
continue;
otherChild = canonicalize(otherNode.child3());
if (otherChild == NoNode)
return index;
if (otherChild != child3)
continue;
return index;
}
return NoNode;
}
bool isPredictedNumerical(Node& node)
{
PredictedType left = m_graph[node.child1()].prediction();
PredictedType right = m_graph[node.child2()].prediction();
return isNumberPrediction(left) && isNumberPrediction(right);
}
bool logicalNotIsPure(Node& node)
{
PredictedType prediction = m_graph[node.child1()].prediction();
return isBooleanPrediction(prediction) || !prediction;
}
bool byValIsPure(Node& node)
{
return m_graph[node.child2()].shouldSpeculateInteger()
&& ((node.op() == PutByVal || node.op() == PutByValAlias)
? isActionableMutableArrayPrediction(m_graph[node.child1()].prediction())
: isActionableArrayPrediction(m_graph[node.child1()].prediction()));
}
bool clobbersWorld(NodeIndex nodeIndex)
{
Node& node = m_graph[nodeIndex];
if (node.flags() & NodeClobbersWorld)
return true;
if (!(node.flags() & NodeMightClobber))
return false;
switch (node.op()) {
case ValueAdd:
case CompareLess:
case CompareLessEq:
case CompareGreater:
case CompareGreaterEq:
case CompareEq:
return !isPredictedNumerical(node);
case LogicalNot:
return !logicalNotIsPure(node);
case GetByVal:
return !byValIsPure(node);
default:
ASSERT_NOT_REACHED();
return true; }
}
NodeIndex impureCSE(Node& node)
{
NodeIndex child1 = canonicalize(node.child1());
NodeIndex child2 = canonicalize(node.child2());
NodeIndex child3 = canonicalize(node.child3());
for (unsigned i = m_indexInBlock; i--;) {
NodeIndex index = m_currentBlock->at(i);
if (index == child1 || index == child2 || index == child3)
break;
Node& otherNode = m_graph[index];
if (node.op() == otherNode.op()
&& node.arithNodeFlags() == otherNode.arithNodeFlags()) {
NodeIndex otherChild = canonicalize(otherNode.child1());
if (otherChild == NoNode)
return index;
if (otherChild == child1) {
otherChild = canonicalize(otherNode.child2());
if (otherChild == NoNode)
return index;
if (otherChild == child2) {
otherChild = canonicalize(otherNode.child3());
if (otherChild == NoNode)
return index;
if (otherChild == child3)
return index;
}
}
}
if (clobbersWorld(index))
break;
}
return NoNode;
}
NodeIndex globalVarLoadElimination(unsigned varNumber, JSGlobalObject* globalObject)
{
for (unsigned i = m_indexInBlock; i--;) {
NodeIndex index = m_currentBlock->at(i);
Node& node = m_graph[index];
switch (node.op()) {
case GetGlobalVar:
if (node.varNumber() == varNumber && codeBlock()->globalObjectFor(node.codeOrigin) == globalObject)
return index;
break;
case PutGlobalVar:
if (node.varNumber() == varNumber && codeBlock()->globalObjectFor(node.codeOrigin) == globalObject)
return node.child1().index();
break;
default:
break;
}
if (clobbersWorld(index))
break;
}
return NoNode;
}
NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
{
for (unsigned i = m_indexInBlock; i--;) {
NodeIndex index = m_currentBlock->at(i);
if (index == child1 || index == canonicalize(child2))
break;
Node& node = m_graph[index];
switch (node.op()) {
case GetByVal:
if (!byValIsPure(node))
return NoNode;
if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
return index;
break;
case PutByVal:
case PutByValAlias:
if (!byValIsPure(node))
return NoNode;
if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
return node.child3().index();
return NoNode;
case PutStructure:
case PutByOffset:
break;
case ArrayPush:
break;
default:
if (clobbersWorld(index))
return NoNode;
break;
}
}
return NoNode;
}
bool checkFunctionElimination(JSFunction* function, NodeIndex child1)
{
for (unsigned i = endIndexForPureCSE(); i--;) {
NodeIndex index = m_currentBlock->at(i);
if (index == child1)
break;
Node& node = m_graph[index];
if (node.op() == CheckFunction && node.child1() == child1 && node.function() == function)
return true;
}
return false;
}
bool checkStructureLoadElimination(const StructureSet& structureSet, NodeIndex child1)
{
for (unsigned i = m_indexInBlock; i--;) {
NodeIndex index = m_currentBlock->at(i);
if (index == child1)
break;
Node& node = m_graph[index];
switch (node.op()) {
case CheckStructure:
if (node.child1() == child1
&& structureSet.isSupersetOf(node.structureSet()))
return true;
break;
case PutStructure:
if (node.child1() == child1
&& structureSet.contains(node.structureTransitionData().newStructure))
return true;
if (structureSet.contains(node.structureTransitionData().previousStructure))
return false;
break;
case PutByOffset:
break;
case PutByVal:
case PutByValAlias:
if (byValIsPure(node)) {
break;
}
return false;
default:
if (clobbersWorld(index))
return false;
break;
}
}
return false;
}
NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1)
{
for (unsigned i = m_indexInBlock; i--;) {
NodeIndex index = m_currentBlock->at(i);
if (index == child1)
break;
Node& node = m_graph[index];
switch (node.op()) {
case GetByOffset:
if (node.child1() == child1
&& m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
return index;
break;
case PutByOffset:
if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
if (node.child2() == child1)
return node.child3().index();
return NoNode;
}
break;
case PutStructure:
break;
case PutByVal:
case PutByValAlias:
if (byValIsPure(node)) {
break;
}
return NoNode;
default:
if (clobbersWorld(index))
return NoNode;
break;
}
}
return NoNode;
}
NodeIndex getPropertyStorageLoadElimination(NodeIndex child1)
{
for (unsigned i = m_indexInBlock; i--;) {
NodeIndex index = m_currentBlock->at(i);
if (index == child1)
break;
Node& node = m_graph[index];
switch (node.op()) {
case GetPropertyStorage:
if (node.child1() == child1)
return index;
break;
case PutByOffset:
case PutStructure:
break;
case PutByVal:
case PutByValAlias:
if (byValIsPure(node)) {
break;
}
return NoNode;
default:
if (clobbersWorld(index))
return NoNode;
break;
}
}
return NoNode;
}
NodeIndex getIndexedPropertyStorageLoadElimination(NodeIndex child1, bool hasIntegerIndexPrediction)
{
for (unsigned i = m_indexInBlock; i--;) {
NodeIndex index = m_currentBlock->at(i);
if (index == child1)
break;
Node& node = m_graph[index];
switch (node.op()) {
case GetIndexedPropertyStorage: {
PredictedType basePrediction = m_graph[node.child2()].prediction();
bool nodeHasIntegerIndexPrediction = !(!(basePrediction & PredictInt32) && basePrediction);
if (node.child1() == child1 && hasIntegerIndexPrediction == nodeHasIntegerIndexPrediction)
return index;
break;
}
case PutByOffset:
case PutStructure:
break;
case PutByValAlias:
break;
case PutByVal:
if (isFixedIndexedStorageObjectPrediction(m_graph[node.child1()].prediction()) && byValIsPure(node))
break;
return NoNode;
default:
if (clobbersWorld(index))
return NoNode;
break;
}
}
return NoNode;
}
NodeIndex getScopeChainLoadElimination(unsigned depth)
{
for (unsigned i = endIndexForPureCSE(); i--;) {
NodeIndex index = m_currentBlock->at(i);
Node& node = m_graph[index];
if (node.op() == GetScopeChain
&& node.scopeChainDepth() == depth)
return index;
}
return NoNode;
}
void performSubstitution(Edge& child, bool addRef = true)
{
if (!child)
return;
NodeIndex replacement = m_replacements[child.index()];
if (replacement == NoNode)
return;
child.setIndex(replacement);
ASSERT(m_replacements[child.index()] == NoNode);
if (addRef)
m_graph[child].ref();
}
void setReplacement(NodeIndex replacement)
{
if (replacement == NoNode)
return;
if (m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
return;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" Replacing @%u -> @%u", m_compileIndex, replacement);
#endif
Node& node = m_graph[m_compileIndex];
node.setOpAndDefaultFlags(Phantom);
node.setRefCount(1);
m_replacements[m_compileIndex] = replacement;
}
void eliminate()
{
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" Eliminating @%u", m_compileIndex);
#endif
Node& node = m_graph[m_compileIndex];
ASSERT(node.refCount() == 1);
ASSERT(node.mustGenerate());
node.setOpAndDefaultFlags(Phantom);
}
void performNodeCSE(Node& node)
{
bool shouldGenerate = node.shouldGenerate();
if (node.flags() & NodeHasVarArgs) {
for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate);
} else {
performSubstitution(node.children.child1(), shouldGenerate);
performSubstitution(node.children.child2(), shouldGenerate);
performSubstitution(node.children.child3(), shouldGenerate);
}
if (!shouldGenerate)
return;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" %s @%u: ", Graph::opName(m_graph[m_compileIndex].op()), m_compileIndex);
#endif
switch (node.op()) {
case BitAnd:
case BitOr:
case BitXor:
case BitRShift:
case BitLShift:
case BitURShift:
case ArithAdd:
case ArithSub:
case ArithNegate:
case ArithMul:
case ArithMod:
case ArithDiv:
case ArithAbs:
case ArithMin:
case ArithMax:
case ArithSqrt:
case GetInt8ArrayLength:
case GetInt16ArrayLength:
case GetInt32ArrayLength:
case GetUint8ArrayLength:
case GetUint8ClampedArrayLength:
case GetUint16ArrayLength:
case GetUint32ArrayLength:
case GetFloat32ArrayLength:
case GetFloat64ArrayLength:
case GetCallee:
case GetStringLength:
case StringCharAt:
case StringCharCodeAt:
case Int32ToDouble:
case IsUndefined:
case IsBoolean:
case IsNumber:
case IsString:
case IsObject:
case IsFunction:
case DoubleAsInt32:
setReplacement(pureCSE(node));
break;
case GetArrayLength:
setReplacement(impureCSE(node));
break;
case GetScopeChain:
setReplacement(getScopeChainLoadElimination(node.scopeChainDepth()));
break;
case ValueAdd:
case CompareLess:
case CompareLessEq:
case CompareGreater:
case CompareGreaterEq:
case CompareEq: {
if (isPredictedNumerical(node)) {
NodeIndex replacementIndex = pureCSE(node);
if (replacementIndex != NoNode && isPredictedNumerical(m_graph[replacementIndex]))
setReplacement(replacementIndex);
}
break;
}
case LogicalNot: {
if (logicalNotIsPure(node)) {
NodeIndex replacementIndex = pureCSE(node);
if (replacementIndex != NoNode && logicalNotIsPure(m_graph[replacementIndex]))
setReplacement(replacementIndex);
}
break;
}
case GetGlobalVar:
setReplacement(globalVarLoadElimination(node.varNumber(), codeBlock()->globalObjectFor(node.codeOrigin)));
break;
case GetByVal:
if (byValIsPure(node))
setReplacement(getByValLoadElimination(node.child1().index(), node.child2().index()));
break;
case PutByVal:
if (byValIsPure(node) && getByValLoadElimination(node.child1().index(), node.child2().index()) != NoNode)
node.setOp(PutByValAlias);
break;
case CheckStructure:
if (checkStructureLoadElimination(node.structureSet(), node.child1().index()))
eliminate();
break;
case CheckFunction:
if (checkFunctionElimination(node.function(), node.child1().index()))
eliminate();
break;
case GetIndexedPropertyStorage: {
PredictedType basePrediction = m_graph[node.child2()].prediction();
bool nodeHasIntegerIndexPrediction = !(!(basePrediction & PredictInt32) && basePrediction);
setReplacement(getIndexedPropertyStorageLoadElimination(node.child1().index(), nodeHasIntegerIndexPrediction));
break;
}
case GetPropertyStorage:
setReplacement(getPropertyStorageLoadElimination(node.child1().index()));
break;
case GetByOffset:
setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
break;
default:
break;
}
m_lastSeen[node.op()] = m_indexInBlock;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog("\n");
#endif
}
void performBlockCSE(BasicBlock& block)
{
m_currentBlock = █
for (unsigned i = 0; i < LastNodeType; ++i)
m_lastSeen[i] = UINT_MAX;
for (m_indexInBlock = 0; m_indexInBlock < block.size(); ++m_indexInBlock) {
m_compileIndex = block[m_indexInBlock];
performNodeCSE(m_graph[m_compileIndex]);
}
}
BasicBlock* m_currentBlock;
NodeIndex m_compileIndex;
unsigned m_indexInBlock;
Vector<NodeIndex, 16> m_replacements;
FixedArray<unsigned, LastNodeType> m_lastSeen;
};
void performCSE(Graph& graph)
{
runPhase<CSEPhase>(graph);
}
} }
#endif // ENABLE(DFG_JIT)