CSEPhase(Graph& graph)

: Phase(graph, cseMode == NormalCSE ? "common subexpression elimination" : "store elimination")

{

}

bool run()

{

ASSERT(m_graph.m_fixpointState != BeforeFixpoint);

m_changed = false;

m_graph.clearReplacements();

for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {

BasicBlock* block = m_graph.block(blockIndex);

if (!block)

continue;

// All Phis need to already be marked as relevant to OSR.

if (!ASSERT_DISABLED) {

for (unsigned i = 0; i < block->phis.size(); ++i)

ASSERT(block->phis[i]->flags() & NodeRelevantToOSR);

}

for (unsigned i = block->size(); i--;) {

Node* node = block->at(i);

switch (node->op()) {

case SetLocal:

case GetLocal: // FIXME: The GetLocal case is only necessary until we do https://bugs.webkit.org/show_bug.cgi?id=106707.

node->mergeFlags(NodeRelevantToOSR);

break;

default:

node->clearFlags(NodeRelevantToOSR);

break;

}

}

}

for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {

BasicBlock* block = m_graph.block(blockIndex);

if (!block)

continue;

for (unsigned i = block->size(); i--;) {

Node* node = block->at(i);

if (!node->containsMovHint())

continue;

ASSERT(node->op() != ZombieHint);

node->child1()->mergeFlags(NodeRelevantToOSR);

}

}

if (m_graph.m_form == SSA) {

Vector<BasicBlock*> depthFirst;

m_graph.getBlocksInDepthFirstOrder(depthFirst);

for (unsigned i = 0; i < depthFirst.size(); ++i)

performBlockCSE(depthFirst[i]);

} else {

for (unsigned blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)

performBlockCSE(m_graph.block(blockIndex));

}

return m_changed;

}

unsigned endIndexForPureCSE()

{

unsigned result = m_lastSeen[m_currentNode->op()];

if (result == UINT_MAX)

result = 0;

else

result++;

ASSERT(result <= m_indexInBlock);

return result;

}

Node* pureCSE(Node* node)

{

Edge child1 = node->child1();

Edge child2 = node->child2();

Edge child3 = node->child3();

for (unsigned i = endIndexForPureCSE(); i--;) {

Node* otherNode = m_currentBlock->at(i);

if (otherNode == child1 || otherNode == child2 || otherNode == child3)

break;

if (node->op() != otherNode->op())

continue;

if (node->arithNodeFlags() != otherNode->arithNodeFlags())

continue;

Edge otherChild = otherNode->child1();

if (!otherChild)

return otherNode;

if (otherChild != child1)

continue;

otherChild = otherNode->child2();

if (!otherChild)

return otherNode;

if (otherChild != child2)

continue;

otherChild = otherNode->child3();

if (!otherChild)

return otherNode;

if (otherChild != child3)

continue;

return otherNode;

}

return 0;

}

Node* int32ToDoubleCSE(Node* node)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* otherNode = m_currentBlock->at(i);

if (otherNode == node->child1())

return 0;

switch (otherNode->op()) {

case Int32ToDouble:

if (otherNode->child1() == node->child1())

return otherNode;

break;

default:

break;

}

}

return 0;

}

Node* constantCSE(Node* node)

{

for (unsigned i = endIndexForPureCSE(); i--;) {

Node* otherNode = m_currentBlock->at(i);

if (otherNode->op() != JSConstant)

continue;

if (otherNode->constantNumber() != node->constantNumber())

continue;

return otherNode;

}

return 0;

}

Node* weakConstantCSE(Node* node)

{

for (unsigned i = endIndexForPureCSE(); i--;) {

Node* otherNode = m_currentBlock->at(i);

if (otherNode->op() != WeakJSConstant)

continue;

if (otherNode->weakConstant() != node->weakConstant())

continue;

return otherNode;

}

return 0;

}

Node* constantStoragePointerCSE(Node* node)

{

for (unsigned i = endIndexForPureCSE(); i--;) {

Node* otherNode = m_currentBlock->at(i);

if (otherNode->op() != ConstantStoragePointer)

continue;

if (otherNode->storagePointer() != node->storagePointer())

continue;

return otherNode;

}

return 0;

}

Node* getCalleeLoadElimination()

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

switch (node->op()) {

case GetCallee:

return node;

default:

break;

}

}

return 0;

}

Node* getArrayLengthElimination(Node* array)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

switch (node->op()) {

case GetArrayLength:

if (node->child1() == array)

return node;

break;

case PutByValDirect:

case PutByVal:

if (!m_graph.byValIsPure(node))

return 0;

if (node->arrayMode().mayStoreToHole())

return 0;

break;

default:

if (m_graph.clobbersWorld(node))

return 0;

}

}

return 0;

}

Node* globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

switch (node->op()) {

case GetGlobalVar:

if (node->registerPointer() == registerPointer)

return node;

break;

case PutGlobalVar:

if (node->registerPointer() == registerPointer)

return node->child1().node();

break;

default:

break;

}

if (m_graph.clobbersWorld(node))

break;

}

return 0;

}

Node* scopedVarLoadElimination(Node* registers, int varNumber)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

switch (node->op()) {

case GetClosureVar: {

if (node->child1() == registers && node->varNumber() == varNumber)

return node;

break;

}

case PutClosureVar: {

if (node->varNumber() != varNumber)

break;

if (node->child2() == registers)

return node->child3().node();

return 0;

}

case SetLocal: {

VariableAccessData* variableAccessData = node->variableAccessData();

if (variableAccessData->isCaptured()

&& variableAccessData->local() == static_cast<VirtualRegister>(varNumber))

return 0;

break;

}

default:

break;

}

if (m_graph.clobbersWorld(node))

break;

}

return 0;

}

bool varInjectionWatchpointElimination()

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

if (node->op() == VarInjectionWatchpoint)

return true;

if (m_graph.clobbersWorld(node))

break;

}

return false;

}

Node* globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

switch (node->op()) {

case PutGlobalVar:

if (node->registerPointer() == registerPointer)

return node;

break;

case GetGlobalVar:

if (node->registerPointer() == registerPointer)

return 0;

break;

default:

break;

}

if (m_graph.clobbersWorld(node) || node->canExit())

return 0;

}

return 0;

}

Node* scopedVarStoreElimination(Node* scope, Node* registers, int varNumber)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

switch (node->op()) {

case PutClosureVar: {

if (node->varNumber() != varNumber)

break;

if (node->child1() == scope && node->child2() == registers)

return node;

return 0;

}

case GetClosureVar: {

// Let's be conservative.

if (node->varNumber() == varNumber)

return 0;

break;

}

case GetLocal:

case SetLocal: {

VariableAccessData* variableAccessData = node->variableAccessData();

if (variableAccessData->isCaptured()

&& variableAccessData->local() == static_cast<VirtualRegister>(varNumber))

return 0;

break;

}

default:

break;

}

if (m_graph.clobbersWorld(node) || node->canExit())

return 0;

}

return 0;

}

Node* getByValLoadElimination(Node* child1, Node* child2, ArrayMode arrayMode)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1 || node == child2)

break;

switch (node->op()) {

case GetByVal:

if (!m_graph.byValIsPure(node))

return 0;

if (node->child1() == child1

&& node->child2() == child2

&& node->arrayMode().type() == arrayMode.type())

return node;

break;

case PutByValDirect:

case PutByVal:

case PutByValAlias: {

if (!m_graph.byValIsPure(node))

return 0;

// Typed arrays

if (arrayMode.typedArrayType() != NotTypedArray)

return 0;

if (m_graph.varArgChild(node, 0) == child1

&& m_graph.varArgChild(node, 1) == child2

&& node->arrayMode().type() == arrayMode.type())

return m_graph.varArgChild(node, 2).node();

// We must assume that the PutByVal will clobber the location we're getting from.

// FIXME: We can do better; if we know that the PutByVal is accessing an array of a

// different type than the GetByVal, then we know that they won't clobber each other.

// ... except of course for typed arrays, where all typed arrays clobber all other

// typed arrays! An Int32Array can alias a Float64Array for example, and so on.

return 0;

}

default:

if (m_graph.clobbersWorld(node))

return 0;

break;

}

}

return 0;

}

bool checkFunctionElimination(JSCell* function, Node* child1)

{

for (unsigned i = endIndexForPureCSE(); i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1)

break;

if (node->op() == CheckFunction && node->child1() == child1 && node->function() == function)

return true;

}

return false;

}

bool checkExecutableElimination(ExecutableBase* executable, Node* child1)

{

for (unsigned i = endIndexForPureCSE(); i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1)

break;

if (node->op() == CheckExecutable && node->child1() == child1 && node->executable() == executable)

return true;

}

return false;

}

bool checkStructureElimination(const StructureSet& structureSet, Node* child1)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1)

break;

switch (node->op()) {

case CheckStructure:

if (node->child1() == child1

&& structureSet.isSupersetOf(node->structureSet()))

return true;

break;

case StructureTransitionWatchpoint:

if (node->child1() == child1

&& structureSet.contains(node->structure()))

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:

// Setting a property cannot change the structure.

break;

case PutByValDirect:

case PutByVal:

case PutByValAlias:

if (m_graph.byValIsPure(node)) {

// If PutByVal speculates that it's accessing an array with an

// integer index, then it's impossible for it to cause a structure

// change.

break;

}

return false;

case Arrayify:

case ArrayifyToStructure:

// We could check if the arrayification could affect our structures.

// But that seems like it would take Effort.

return false;

default:

if (m_graph.clobbersWorld(node))

return false;

break;

}

}

return false;

}

bool structureTransitionWatchpointElimination(Structure* structure, Node* child1)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1)

break;

switch (node->op()) {

case CheckStructure:

if (node->child1() == child1

&& node->structureSet().containsOnly(structure))

return true;

break;

case PutStructure:

ASSERT(node->structureTransitionData().previousStructure != structure);

break;

case PutByOffset:

// Setting a property cannot change the structure.

break;

case PutByValDirect:

case PutByVal:

case PutByValAlias:

if (m_graph.byValIsPure(node)) {

// If PutByVal speculates that it's accessing an array with an

// integer index, then it's impossible for it to cause a structure

// change.

break;

}

return false;

case StructureTransitionWatchpoint:

if (node->structure() == structure && node->child1() == child1)

return true;

break;

case Arrayify:

case ArrayifyToStructure:

// We could check if the arrayification could affect our structures.

// But that seems like it would take Effort.

return false;

default:

if (m_graph.clobbersWorld(node))

return false;

break;

}

}

return false;

}

Node* putStructureStoreElimination(Node* child1)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1)

break;

switch (node->op()) {

case CheckStructure:

return 0;

case PhantomPutStructure:

if (node->child1() == child1) // No need to retrace our steps.

return 0;

break;

case PutStructure:

if (node->child1() == child1)

return node;

break;

// PutStructure needs to execute if we GC. Hence this needs to

// be careful with respect to nodes that GC.

case CreateArguments:

case TearOffArguments:

case NewFunctionNoCheck:

case NewFunction:

case NewFunctionExpression:

case CreateActivation:

case TearOffActivation:

case ToPrimitive:

case NewRegexp:

case NewArrayBuffer:

case NewArray:

case NewObject:

case CreateThis:

case AllocatePropertyStorage:

case ReallocatePropertyStorage:

case TypeOf:

case ToString:

case NewStringObject:

case MakeRope:

case NewTypedArray:

return 0;

// This either exits, causes a GC (lazy string allocation), or clobbers

// the world. The chances of it not doing any of those things are so

// slim that we might as well not even try to reason about it.

case GetByVal:

return 0;

case GetIndexedPropertyStorage:

if (node->arrayMode().getIndexedPropertyStorageMayTriggerGC())

return 0;

break;

default:

break;

}

if (m_graph.clobbersWorld(node) || node->canExit())

return 0;

if (edgesUseStructure(m_graph, node))

return 0;

}

return 0;

}

Node* getByOffsetLoadElimination(unsigned identifierNumber, Node* child1)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1)

break;

switch (node->op()) {

case GetByOffset:

if (node->child1() == child1

&& m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)

return node;

break;

case PutByOffset:

if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {

if (node->child1() == child1) // Must be same property storage.

return node->child3().node();

return 0;

}

break;

case PutByValDirect:

case PutByVal:

case PutByValAlias:

if (m_graph.byValIsPure(node)) {

// If PutByVal speculates that it's accessing an array with an

// integer index, then it's impossible for it to cause a structure

// change.

break;

}

return 0;

default:

if (m_graph.clobbersWorld(node))

return 0;

break;

}

}

return 0;

}

Node* putByOffsetStoreElimination(unsigned identifierNumber, Node* child1)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1)

break;

switch (node->op()) {

case GetByOffset:

if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)

return 0;

break;

case PutByOffset:

if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {

if (node->child1() == child1) // Must be same property storage.

return node;

return 0;

}

break;

case PutByValDirect:

case PutByVal:

case PutByValAlias:

case GetByVal:

if (m_graph.byValIsPure(node)) {

// If PutByVal speculates that it's accessing an array with an

// integer index, then it's impossible for it to cause a structure

// change.

break;

}

return 0;

default:

if (m_graph.clobbersWorld(node))

return 0;

break;

}

if (node->canExit())

return 0;

}

return 0;

}

Node* getPropertyStorageLoadElimination(Node* child1)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1)

break;

switch (node->op()) {

case GetButterfly:

if (node->child1() == child1)

return node;

break;

case AllocatePropertyStorage:

case ReallocatePropertyStorage:

// If we can cheaply prove this is a change to our object's storage, we

// can optimize and use its result.

if (node->child1() == child1)

return node;

// Otherwise, we currently can't prove that this doesn't change our object's

// storage, so we conservatively assume that it may change the storage

// pointer of any object, including ours.

return 0;

case PutByValDirect:

case PutByVal:

case PutByValAlias:

if (m_graph.byValIsPure(node)) {

// If PutByVal speculates that it's accessing an array with an

// integer index, then it's impossible for it to cause a structure

// change.

break;

}

return 0;

case Arrayify:

case ArrayifyToStructure:

// We could check if the arrayification could affect our butterfly.

// But that seems like it would take Effort.

return 0;

default:

if (m_graph.clobbersWorld(node))

return 0;

break;

}

}

return 0;

}

bool checkArrayElimination(Node* child1, ArrayMode arrayMode)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1)

break;

switch (node->op()) {

case CheckArray:

if (node->child1() == child1 && node->arrayMode() == arrayMode)

return true;

break;

case Arrayify:

case ArrayifyToStructure:

// We could check if the arrayification could affect our array.

// But that seems like it would take Effort.

return false;

default:

if (m_graph.clobbersWorld(node))

return false;

break;

}

}

return false;

}

Node* getIndexedPropertyStorageLoadElimination(Node* child1, ArrayMode arrayMode)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1)

break;

switch (node->op()) {

case GetIndexedPropertyStorage: {

if (node->child1() == child1 && node->arrayMode() == arrayMode)

return node;

break;

}

default:

if (m_graph.clobbersWorld(node))

return 0;

break;

}

}

return 0;

}

Node* getTypedArrayByteOffsetLoadElimination(Node* child1)

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

if (node == child1)

break;

switch (node->op()) {

case GetTypedArrayByteOffset: {

if (node->child1() == child1)

return node;

break;

}

default:

if (m_graph.clobbersWorld(node))

return 0;

break;

}

}

return 0;

}

Node* getMyScopeLoadElimination()

{

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

switch (node->op()) {

case CreateActivation:

// This may cause us to return a different scope.

return 0;

case GetMyScope:

return node;

default:

break;

}

}

return 0;

}

Node* getLocalLoadElimination(VirtualRegister local, Node*& relevantLocalOp, bool careAboutClobbering)

{

relevantLocalOp = 0;

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

switch (node->op()) {

case GetLocal:

if (node->local() == local) {

relevantLocalOp = node;

return node;

}

break;

case GetLocalUnlinked:

if (node->unlinkedLocal() == local) {

relevantLocalOp = node;

return node;

}

break;

case SetLocal:

if (node->local() == local) {

relevantLocalOp = node;

return node->child1().node();

}

break;

case GetClosureVar:

case PutClosureVar:

if (static_cast<VirtualRegister>(node->varNumber()) == local)

return 0;

break;

default:

if (careAboutClobbering && m_graph.clobbersWorld(node))

return 0;

break;

}

}

return 0;

}

struct SetLocalStoreEliminationResult {

SetLocalStoreEliminationResult()

: mayBeAccessed(false)

, mayExit(false)

, mayClobberWorld(false)

{

}

bool mayBeAccessed;

bool mayExit;

bool mayClobberWorld;

};

SetLocalStoreEliminationResult setLocalStoreElimination(

VirtualRegister local, Node* expectedNode)

{

SetLocalStoreEliminationResult result;

for (unsigned i = m_indexInBlock; i--;) {

Node* node = m_currentBlock->at(i);

switch (node->op()) {

case GetLocal:

case Flush:

if (node->local() == local)

result.mayBeAccessed = true;

break;

case GetLocalUnlinked:

if (node->unlinkedLocal() == local)

result.mayBeAccessed = true;

break;

case SetLocal: {

if (node->local() != local)

break;

if (node != expectedNode)

result.mayBeAccessed = true;

return result;

}

case GetClosureVar:

case PutClosureVar:

if (static_cast<VirtualRegister>(node->varNumber()) == local)

result.mayBeAccessed = true;

break;

case GetMyScope:

case SkipTopScope:

if (node->codeOrigin.inlineCallFrame)

break;

if (m_graph.uncheckedActivationRegister() == local)

result.mayBeAccessed = true;

break;

case CheckArgumentsNotCreated:

case GetMyArgumentsLength:

case GetMyArgumentsLengthSafe:

if (m_graph.uncheckedArgumentsRegisterFor(node->codeOrigin) == local)

result.mayBeAccessed = true;

break;

case GetMyArgumentByVal:

case GetMyArgumentByValSafe:

result.mayBeAccessed = true;

break;

case GetByVal:

// If this is accessing arguments then it's potentially accessing locals.

if (node->arrayMode().type() == Array::Arguments)

result.mayBeAccessed = true;

break;

case CreateArguments:

case TearOffActivation:

case TearOffArguments:

// If an activation is being torn off then it means that captured variables

// are live. We could be clever here and check if the local qualifies as an

// argument register. But that seems like it would buy us very little since

// any kind of tear offs are rare to begin with.

result.mayBeAccessed = true;

break;

default:

break;

}

result.mayExit |= node->canExit();

result.mayClobberWorld |= m_graph.clobbersWorld(node);

}