Ignore:
Timestamp:
Aug 5, 2014, 10:27:46 PM (11 years ago)
Author:
[email protected]
Message:

Merge r170564, r170571, r170604, r170628, r170672, r170680, r170724, r170728, r170729, r170819, r170821, r170836, r170855, r170860, r170890, r170907, r170929, r171052, r171106, r171152, r171153, r171214 from ftlopt.

Source/JavaScriptCore:

This part of the merge delivers roughly a 2% across-the-board performance
improvement, mostly due to immutable property inference and DFG-side GCSE. It also
almost completely resolves accessor performance issues; in the common case the DFG
will compile a getter/setter access into code that is just as efficient as a normal
property access.

Another major highlight of this part of the merge is the work to add a type profiler
to the inspector. This work is still on-going but this greatly increases coverage.

Note that this merge fixes a minor bug in the GetterSetter refactoring from
​http://trac.webkit.org/changeset/170729 (​https://bugs.webkit.org/show_bug.cgi?id=134518).
It also adds a new tests to tests/stress to cover that bug. That bug was previously only
covered by layout tests.

2014-07-17 Filip Pizlo <​[email protected]>


[ftlopt] DFG Flush(SetLocal) store elimination is overzealous for captured variables in the presence of nodes that have no effects but may throw (merge trunk r171190)
​https://bugs.webkit.org/show_bug.cgi?id=135019


Reviewed by Oliver Hunt.


Behaviorally, this is just a merge of trunk r171190, except that the relevant functionality
has moved to StrengthReductionPhase and is written in a different style. Same algorithm,
different code.


  • dfg/DFGNodeType.h:
  • dfg/DFGStrengthReductionPhase.cpp: (JSC::DFG::StrengthReductionPhase::handleNode):
  • tests/stress/capture-escape-and-throw.js: Added. (foo.f): (foo):
  • tests/stress/new-array-with-size-throw-exception-and-tear-off-arguments.js: Added. (foo): (bar):


2014-07-15 Filip Pizlo <​[email protected]>


[ftlopt] Constant fold GetGetter and GetSetter if the GetterSetter is a constant
​https://bugs.webkit.org/show_bug.cgi?id=134962


Reviewed by Oliver Hunt.


This removes yet another steady-state-throughput implication of using getters and setters:
if your accessor call is monomorphic then you'll just get a structure check, nothing more.
No more loads to get to the GetterSetter object or the accessor function object.


  • dfg/DFGAbstractInterpreterInlines.h: (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
  • runtime/GetterSetter.h: (JSC::GetterSetter::getterConcurrently): (JSC::GetterSetter::setGetter): (JSC::GetterSetter::setterConcurrently): (JSC::GetterSetter::setSetter):


2014-07-15 Filip Pizlo <​[email protected]>


[ftlopt] Identity replacement in CSE shouldn't create a Phantom over the Identity's children
​https://bugs.webkit.org/show_bug.cgi?id=134893


Reviewed by Oliver Hunt.


Replace Identity with Check instead of Phantom. Phantom means that the child of the
Identity should be unconditionally live. The liveness semantics of Identity are such that
if the parents of Identity are live then the child is live. Removing the Identity entirely
preserves such liveness semantics. So, the only thing that should be left behind is the
type check on the child, which is what Check means: do the check but don't keep the child
alive if the check isn't needed.


  • dfg/DFGCSEPhase.cpp:
  • dfg/DFGNode.h: (JSC::DFG::Node::convertToCheck):


2014-07-13 Filip Pizlo <​[email protected]>


[ftlopt] DFG should be able to do GCSE in SSA and this should be unified with the CSE in CPS, and both of these things should use abstract heaps for reasoning about effects
​https://bugs.webkit.org/show_bug.cgi?id=134677


Reviewed by Sam Weinig.


This removes the old local CSE phase, which was based on manually written backward-search
rules for all of the different kinds of things we cared about, and adds a new local/global
CSE (local for CPS and global for SSA) that leaves the node semantics almost entirely up to
clobberize(). Thus, the CSE phase itself just worries about the algorithms and data
structures used for storing sets of available values. This results in a large reduction in
code size in CSEPhase.cpp while greatly increasing the phase's power (since it now does
global CSE) and reducing compile time (since local CSE is now rewritten to use smarter data
structures). Even though LLVM was already running GVN, the extra GCSE at DFG IR level means
that this is a significant (~0.7%) throughput improvement.


This work is based on the concept of "def" to clobberize(). If clobberize() calls def(), it
means that the node being analyzed makes available some value in some DFG node, and that
future attempts to compute that value can simply use that node. In other words, it
establishes an available value mapping of the form value=>node. There are two kinds of
values that can be passed to def():


PureValue. This captures everything needed to determine whether two pure nodes - nodes that

neither read nor write, and produce a value that is a CSE candidate - are identical. It
carries the NodeType, an AdjacencyList, and one word of meta-data. The meta-data is
usually used for things like the arithmetic mode or constant pointer. Passing a
PureValue to def() means that the node produces a value that is valid anywhere that the
node dominates.


HeapLocation. This describes a location in the heap that could be written to or read from.

Both stores and loads can def() a HeapLocation. HeapLocation carries around an abstract
heap that both serves as part of the "name" of the heap location (together with the
other fields of HeapLocation) and also tells us what write()'s to watch for. If someone
write()'s to an abstract heap that overlaps the heap associated with the HeapLocation,
then it means that the values for that location are no longer available.


This approach is sufficiently clever that the CSEPhase itself can focus on the mechanism of
tracking the PureValue=>node and HeapLocation=>node maps, without having to worry about
interpreting the semantics of different DFG node types - that is now almost entirely in
clobberize(). The only things we special-case inside CSEPhase are the Identity node, which
CSE is traditionally responsible for eliminating even though it has nothing to do with CSE,
and the LocalCSE rule for turning PutByVal into PutByValAlias.


This is a slight Octane, SunSpider, and Kraken speed-up - all somewhere arond 0.7% . It's
not a bigger win because LLVM was already giving us most of what we needed in its GVN.
Also, the SunSpider speed-up isn't from GCSE as much as it's a clean-up of local CSE - that
is no longer O(n2). Basically this is purely good: it reduces the amount of LLVM IR we
generate, it removes the old CSE's heap modeling (which was a constant source of bugs), and
it improves both the quality of the code we generate and the speed with which we generate
it. Also, any future optimizations that depend on GCSE will now be easier to implement.


During the development of this patch I also rationalized some other stuff, like Graph's
ordered traversals - we now have preorder and postorder rather than just "depth first".


  • CMakeLists.txt:
  • JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • dfg/DFGAbstractHeap.h:
  • dfg/DFGAdjacencyList.h: (JSC::DFG::AdjacencyList::hash): (JSC::DFG::AdjacencyList::operator==):
  • dfg/DFGBasicBlock.h:
  • dfg/DFGCSEPhase.cpp: (JSC::DFG::performLocalCSE): (JSC::DFG::performGlobalCSE): (JSC::DFG::CSEPhase::CSEPhase): Deleted. (JSC::DFG::CSEPhase::run): Deleted. (JSC::DFG::CSEPhase::endIndexForPureCSE): Deleted. (JSC::DFG::CSEPhase::pureCSE): Deleted. (JSC::DFG::CSEPhase::constantCSE): Deleted. (JSC::DFG::CSEPhase::constantStoragePointerCSE): Deleted. (JSC::DFG::CSEPhase::getCalleeLoadElimination): Deleted. (JSC::DFG::CSEPhase::getArrayLengthElimination): Deleted. (JSC::DFG::CSEPhase::globalVarLoadElimination): Deleted. (JSC::DFG::CSEPhase::scopedVarLoadElimination): Deleted. (JSC::DFG::CSEPhase::varInjectionWatchpointElimination): Deleted. (JSC::DFG::CSEPhase::getByValLoadElimination): Deleted. (JSC::DFG::CSEPhase::checkFunctionElimination): Deleted. (JSC::DFG::CSEPhase::checkExecutableElimination): Deleted. (JSC::DFG::CSEPhase::checkStructureElimination): Deleted. (JSC::DFG::CSEPhase::structureTransitionWatchpointElimination): Deleted. (JSC::DFG::CSEPhase::getByOffsetLoadElimination): Deleted. (JSC::DFG::CSEPhase::getGetterSetterByOffsetLoadElimination): Deleted. (JSC::DFG::CSEPhase::getPropertyStorageLoadElimination): Deleted. (JSC::DFG::CSEPhase::checkArrayElimination): Deleted. (JSC::DFG::CSEPhase::getIndexedPropertyStorageLoadElimination): Deleted. (JSC::DFG::CSEPhase::getInternalFieldLoadElimination): Deleted. (JSC::DFG::CSEPhase::getMyScopeLoadElimination): Deleted. (JSC::DFG::CSEPhase::getLocalLoadElimination): Deleted. (JSC::DFG::CSEPhase::invalidationPointElimination): Deleted. (JSC::DFG::CSEPhase::setReplacement): Deleted. (JSC::DFG::CSEPhase::eliminate): Deleted. (JSC::DFG::CSEPhase::performNodeCSE): Deleted. (JSC::DFG::CSEPhase::performBlockCSE): Deleted. (JSC::DFG::performCSE): Deleted.
  • dfg/DFGCSEPhase.h:
  • dfg/DFGClobberSet.cpp: (JSC::DFG::addReads): (JSC::DFG::addWrites): (JSC::DFG::addReadsAndWrites): (JSC::DFG::readsOverlap): (JSC::DFG::writesOverlap):
  • dfg/DFGClobberize.cpp: (JSC::DFG::doesWrites): (JSC::DFG::accessesOverlap): (JSC::DFG::writesOverlap):
  • dfg/DFGClobberize.h: (JSC::DFG::clobberize): (JSC::DFG::NoOpClobberize::operator()): (JSC::DFG::CheckClobberize::operator()): (JSC::DFG::ReadMethodClobberize::ReadMethodClobberize): (JSC::DFG::ReadMethodClobberize::operator()): (JSC::DFG::WriteMethodClobberize::WriteMethodClobberize): (JSC::DFG::WriteMethodClobberize::operator()): (JSC::DFG::DefMethodClobberize::DefMethodClobberize): (JSC::DFG::DefMethodClobberize::operator()):
  • dfg/DFGDCEPhase.cpp: (JSC::DFG::DCEPhase::run): (JSC::DFG::DCEPhase::fixupBlock):
  • dfg/DFGGraph.cpp: (JSC::DFG::Graph::getBlocksInPreOrder): (JSC::DFG::Graph::getBlocksInPostOrder): (JSC::DFG::Graph::addForDepthFirstSort): Deleted. (JSC::DFG::Graph::getBlocksInDepthFirstOrder): Deleted.
  • dfg/DFGGraph.h:
  • dfg/DFGHeapLocation.cpp: Added. (JSC::DFG::HeapLocation::dump): (WTF::printInternal):
  • dfg/DFGHeapLocation.h: Added. (JSC::DFG::HeapLocation::HeapLocation): (JSC::DFG::HeapLocation::operator!): (JSC::DFG::HeapLocation::kind): (JSC::DFG::HeapLocation::heap): (JSC::DFG::HeapLocation::base): (JSC::DFG::HeapLocation::index): (JSC::DFG::HeapLocation::hash): (JSC::DFG::HeapLocation::operator==): (JSC::DFG::HeapLocation::isHashTableDeletedValue): (JSC::DFG::HeapLocationHash::hash): (JSC::DFG::HeapLocationHash::equal):
  • dfg/DFGLICMPhase.cpp: (JSC::DFG::LICMPhase::run):
  • dfg/DFGNode.h: (JSC::DFG::Node::replaceWith): (JSC::DFG::Node::convertToPhantomUnchecked): Deleted.
  • dfg/DFGPlan.cpp: (JSC::DFG::Plan::compileInThreadImpl):
  • dfg/DFGPureValue.cpp: Added. (JSC::DFG::PureValue::dump):
  • dfg/DFGPureValue.h: Added. (JSC::DFG::PureValue::PureValue): (JSC::DFG::PureValue::operator!): (JSC::DFG::PureValue::op): (JSC::DFG::PureValue::children): (JSC::DFG::PureValue::info): (JSC::DFG::PureValue::hash): (JSC::DFG::PureValue::operator==): (JSC::DFG::PureValue::isHashTableDeletedValue): (JSC::DFG::PureValueHash::hash): (JSC::DFG::PureValueHash::equal):
  • dfg/DFGSSAConversionPhase.cpp: (JSC::DFG::SSAConversionPhase::run):
  • ftl/FTLLowerDFGToLLVM.cpp: (JSC::FTL::LowerDFGToLLVM::lower):


2014-07-13 Filip Pizlo <​[email protected]>


Unreviewed, revert unintended change in r171051.


  • dfg/DFGCSEPhase.cpp:


2014-07-08 Filip Pizlo <​[email protected]>


[ftlopt] Move Flush(SetLocal) store elimination to StrengthReductionPhase
​https://bugs.webkit.org/show_bug.cgi?id=134739


Reviewed by Mark Hahnenberg.


I'm going to streamline CSE around clobberize() as part of
​https://bugs.webkit.org/show_bug.cgi?id=134677, and so Flush(SetLocal) store
elimination wouldn't belong in CSE anymore. It doesn't quite belong anywhere, which
means that it belongs in StrengthReductionPhase, since that's intended to be our
dumping ground.


To do this I had to add some missing smarts to clobberize(). Previously clobberize()
could play a bit loose with reads of Variables because it wasn't used for store
elimination. The main client of read() was LICM, but it would only use it to
determine hoistability and anything that did a write() was not hoistable - so, we had
benign (but still wrong) missing read() calls in places that did write()s. This fixes
a bunch of those cases.


  • dfg/DFGCSEPhase.cpp: (JSC::DFG::CSEPhase::performNodeCSE): (JSC::DFG::CSEPhase::setLocalStoreElimination): Deleted.
  • dfg/DFGClobberize.cpp: (JSC::DFG::accessesOverlap):
  • dfg/DFGClobberize.h: (JSC::DFG::clobberize): Make clobberize() smart enough for detecting when this store elimination would be sound.
  • dfg/DFGStrengthReductionPhase.cpp: (JSC::DFG::StrengthReductionPhase::handleNode): Implement the store elimination in terms of clobberize().


2014-07-08 Filip Pizlo <​[email protected]>


[ftlopt] Phantom simplification should be in its own phase
​https://bugs.webkit.org/show_bug.cgi?id=134742


Reviewed by Geoffrey Garen.


This moves Phantom simplification out of CSE, which greatly simplifies CSE and gives it
more focus. Also this finally adds a phase that removes empty Phantoms. We sort of had
this in CPSRethreading, but that phase runs too infrequently and doesn't run at all for
SSA.


  • CMakeLists.txt:
  • JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • dfg/DFGAdjacencyList.h:
  • dfg/DFGCSEPhase.cpp: (JSC::DFG::CSEPhase::run): (JSC::DFG::CSEPhase::setReplacement): (JSC::DFG::CSEPhase::eliminate): (JSC::DFG::CSEPhase::performNodeCSE): (JSC::DFG::CSEPhase::eliminateIrrelevantPhantomChildren): Deleted.
  • dfg/DFGPhantomRemovalPhase.cpp: Added. (JSC::DFG::PhantomRemovalPhase::PhantomRemovalPhase): (JSC::DFG::PhantomRemovalPhase::run): (JSC::DFG::performCleanUp):
  • dfg/DFGPhantomRemovalPhase.h: Added.
  • dfg/DFGPlan.cpp: (JSC::DFG::Plan::compileInThreadImpl):


2014-07-08 Filip Pizlo <​[email protected]>


[ftlopt] Get rid of Node::misc by moving the fields out of the union so that you can use replacement and owner simultaneously
​https://bugs.webkit.org/show_bug.cgi?id=134730


Reviewed by Mark Lam.


This will allow for a better GCSE implementation.


  • dfg/DFGCPSRethreadingPhase.cpp: (JSC::DFG::CPSRethreadingPhase::canonicalizeGetLocalFor):
  • dfg/DFGCSEPhase.cpp: (JSC::DFG::CSEPhase::setReplacement):
  • dfg/DFGEdgeDominates.h: (JSC::DFG::EdgeDominates::operator()):
  • dfg/DFGGraph.cpp: (JSC::DFG::Graph::clearReplacements): (JSC::DFG::Graph::initializeNodeOwners):
  • dfg/DFGGraph.h: (JSC::DFG::Graph::performSubstitutionForEdge):
  • dfg/DFGLICMPhase.cpp: (JSC::DFG::LICMPhase::attemptHoist):
  • dfg/DFGNode.h: (JSC::DFG::Node::Node):
  • dfg/DFGSSAConversionPhase.cpp: (JSC::DFG::SSAConversionPhase::run):


2014-07-04 Filip Pizlo <​[email protected]>


[ftlopt] Infer immutable object properties
​https://bugs.webkit.org/show_bug.cgi?id=134567


Reviewed by Mark Hahnenberg.


This introduces a new way of inferring immutable object properties. A property is said to
be immutable if after its creation (i.e. the transition that creates it), we never
overwrite it (i.e. replace it) or delete it. Immutability is a property of an "own
property" - so if we say that "f" is immutable at "o" then we are implying that "o" has "f"
directly and not on a prototype. More specifically, the immutability inference will prove
that a property on some structure is immutable. This means that, for example, we may have a
structure S1 with property "f" where we claim that "f" at S1 is immutable, but S1 has a
transition to S2 that adds a new property "g" and we may claim that "f" at S2 is actually
mutable. This is mainly for convenience; it allows us to decouple immutability logic from
transition logic. Immutability can be used to constant-fold accesses to objects at
DFG-time. The DFG needs to prove the following to constant-fold the access:


  • The base of the access must be a constant object pointer. We prove that a property at a structure is immutable, but that says nothing of its value; each actual instance of that property may have a different value. So, a constant object pointer is needed to get an actual constant instance of the immutable value.


  • A check (or watchpoint) must have been emitted proving that the object has a structure that allows loading the property in question.


  • The replacement watchpoint set of the property in the structure that we've proven the object to have is still valid and we add a watchpoint to it lazily. The replacement watchpoint set is the key new mechanism that this change adds. It's possible that we have proven that the object has one of many structures, in which case each of those structures needs a valid replacement watchpoint set.


The replacement watchpoint set is created the first time that any access to the property is
cached. A put replace cache will create, and immediately invalidate, the watchpoint set. A
get cache will create the watchpoint set and make it start watching. Any non-cached put
access will invalidate the watchpoint set if one had been created; the underlying algorithm
ensures that checking for the existence of a replacement watchpoint set is very fast in the
common case. This algorithm ensures that no cached access needs to ever do any work to
invalidate, or check the validity of, any replacement watchpoint sets. It also has some
other nice properties:


  • It's very robust in its definition of immutability. The strictest that it will ever be is that for any instance of the object, the property must be written to only once, specifically at the time that the property is created. But it's looser than this in practice. For example, the property may be written to any number of times before we add the final property that the object will have before anyone reads the property; this works since for optimization purposes we only care if we detect immutability on the structure that the object will have when it is most frequently read from, not any previous structure that the object had. Also, we may write to the property any number of times before anyone caches accesses to it.


  • It is mostly orthogonal to structure transitions. No new structures need to be created to track the immutability of a property. Hence, there is no risk from this feature causing more polymorphism. This is different from the previous "specificValue" constant inference, which did cause additional structures to be created and sometimes those structures led to fake polymorphism. This feature does leverage existing transitions to do some of the watchpointing: property deletions don't fire the replacement watchpoint set because that would cause a new structure and so the mandatory structure check would fail. Also, this feature is guaranteed to never kick in for uncacheable dictionaries because those wouldn't allow for cacheable accesses - and it takes a cacheable access for this feature to be enabled.


  • No memory overhead is incurred except when accesses to the property are cached. Dictionary properties will typically have no meta-data for immutability. The number of replacement watchpoint sets we allocate is proportional to the number of inline caches in the program, which is typically must smaller than the number of structures or even the number of objects.


This inference is far more powerful than the previous "specificValue" inference, so this
change also removes all of that code. It's interesting that the amount of code that is
changed to remove that feature is almost as big as the amount of code added to support the
new inference - and that's if you include the new tests in the tally. Without new tests,
it appears that the new feature actually touches less code!


There is one corner case where the previous "specificValue" inference was more powerful.
You can imagine someone creating objects with functions as self properties on those
objects, such that each object instance had the same function pointers - essentially,
someone might be trying to create a vtable but failing at the whole "one vtable for many
instances" concept. The "specificValue" inference would do very well for such programs,
because a structure check would be sufficient to prove a constant value for all of the
function properties. This new inference will fail because it doesn't track the constant
values of constant properties; instead it detects the immutability of otherwise variable
properties (in the sense that each instance of the property may have a different value).
So, the new inference requires having a particular object instance to actually get the
constant value. I think it's OK to lose this antifeature. It took a lot of code to support
and was a constant source of grief in our transition logic, and there doesn't appear to be
any real evidence that programs benefited from that particular kind of inference since
usually it's the singleton prototype instance that has all of the functions.


This change is a speed-up on everything. date-format-xparb and both SunSpider/raytrace and
V8/raytrace seem to be the biggest winners among the macrobenchmarks; they see >5%
speed-ups. Many of our microbenchmarks see very large performance improvements, even 80% in
one case.


  • bytecode/ComplexGetStatus.cpp: (JSC::ComplexGetStatus::computeFor):
  • bytecode/GetByIdStatus.cpp: (JSC::GetByIdStatus::computeFromLLInt): (JSC::GetByIdStatus::computeForStubInfo): (JSC::GetByIdStatus::computeFor):
  • bytecode/GetByIdVariant.cpp: (JSC::GetByIdVariant::GetByIdVariant): (JSC::GetByIdVariant::operator=): (JSC::GetByIdVariant::attemptToMerge): (JSC::GetByIdVariant::dumpInContext):
  • bytecode/GetByIdVariant.h: (JSC::GetByIdVariant::alternateBase): (JSC::GetByIdVariant::specificValue): Deleted.
  • bytecode/PutByIdStatus.cpp: (JSC::PutByIdStatus::computeForStubInfo): (JSC::PutByIdStatus::computeFor):
  • bytecode/PutByIdVariant.cpp: (JSC::PutByIdVariant::operator=): (JSC::PutByIdVariant::setter): (JSC::PutByIdVariant::dumpInContext):
  • bytecode/PutByIdVariant.h: (JSC::PutByIdVariant::specificValue): Deleted.
  • bytecode/Watchpoint.cpp: (JSC::WatchpointSet::fireAllSlow): (JSC::WatchpointSet::fireAll): Deleted.
  • bytecode/Watchpoint.h: (JSC::WatchpointSet::fireAll):
  • dfg/DFGAbstractInterpreterInlines.h: (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
  • dfg/DFGByteCodeParser.cpp: (JSC::DFG::ByteCodeParser::handleGetByOffset): (JSC::DFG::ByteCodeParser::handleGetById): (JSC::DFG::ByteCodeParser::handlePutById): (JSC::DFG::ByteCodeParser::parseBlock):
  • dfg/DFGConstantFoldingPhase.cpp: (JSC::DFG::ConstantFoldingPhase::emitGetByOffset):
  • dfg/DFGFixupPhase.cpp: (JSC::DFG::FixupPhase::isStringPrototypeMethodSane): (JSC::DFG::FixupPhase::canOptimizeStringObjectAccess):
  • dfg/DFGGraph.cpp: (JSC::DFG::Graph::tryGetConstantProperty): (JSC::DFG::Graph::visitChildren):
  • dfg/DFGGraph.h:
  • dfg/DFGWatchableStructureWatchingPhase.cpp: (JSC::DFG::WatchableStructureWatchingPhase::run):
  • ftl/FTLLowerDFGToLLVM.cpp: (JSC::FTL::LowerDFGToLLVM::compileMultiGetByOffset):
  • jit/JITOperations.cpp:
  • jit/Repatch.cpp: (JSC::repatchByIdSelfAccess): (JSC::generateByIdStub): (JSC::tryCacheGetByID): (JSC::tryCachePutByID): (JSC::tryBuildPutByIdList):
  • llint/LLIntSlowPaths.cpp: (JSC::LLInt::LLINT_SLOW_PATH_DECL): (JSC::LLInt::putToScopeCommon):
  • runtime/CommonSlowPaths.h: (JSC::CommonSlowPaths::tryCachePutToScopeGlobal):
  • runtime/IntendedStructureChain.cpp: (JSC::IntendedStructureChain::mayInterceptStoreTo):
  • runtime/JSCJSValue.cpp: (JSC::JSValue::putToPrimitive):
  • runtime/JSGlobalObject.cpp: (JSC::JSGlobalObject::reset):
  • runtime/JSObject.cpp: (JSC::JSObject::put): (JSC::JSObject::putDirectNonIndexAccessor): (JSC::JSObject::deleteProperty): (JSC::JSObject::defaultValue): (JSC::getCallableObjectSlow): Deleted. (JSC::JSObject::getPropertySpecificValue): Deleted.
  • runtime/JSObject.h: (JSC::JSObject::getDirect): (JSC::JSObject::getDirectOffset): (JSC::JSObject::inlineGetOwnPropertySlot): (JSC::JSObject::putDirectInternal): (JSC::JSObject::putOwnDataProperty): (JSC::JSObject::putDirect): (JSC::JSObject::putDirectWithoutTransition): (JSC::getCallableObject): Deleted.
  • runtime/JSScope.cpp: (JSC::abstractAccess):
  • runtime/PropertyMapHashTable.h: (JSC::PropertyMapEntry::PropertyMapEntry): (JSC::PropertyTable::copy):
  • runtime/PropertyTable.cpp: (JSC::PropertyTable::clone): (JSC::PropertyTable::PropertyTable): (JSC::PropertyTable::visitChildren): Deleted.
  • runtime/Structure.cpp: (JSC::Structure::Structure): (JSC::Structure::materializePropertyMap): (JSC::Structure::addPropertyTransitionToExistingStructureImpl): (JSC::Structure::addPropertyTransitionToExistingStructure): (JSC::Structure::addPropertyTransitionToExistingStructureConcurrently): (JSC::Structure::addPropertyTransition): (JSC::Structure::changePrototypeTransition): (JSC::Structure::attributeChangeTransition): (JSC::Structure::toDictionaryTransition): (JSC::Structure::preventExtensionsTransition): (JSC::Structure::takePropertyTableOrCloneIfPinned): (JSC::Structure::nonPropertyTransition): (JSC::Structure::addPropertyWithoutTransition): (JSC::Structure::allocateRareData): (JSC::Structure::ensurePropertyReplacementWatchpointSet): (JSC::Structure::startWatchingPropertyForReplacements): (JSC::Structure::didCachePropertyReplacement): (JSC::Structure::startWatchingInternalProperties): (JSC::Structure::copyPropertyTable): (JSC::Structure::copyPropertyTableForPinning): (JSC::Structure::getConcurrently): (JSC::Structure::get): (JSC::Structure::add): (JSC::Structure::visitChildren): (JSC::Structure::prototypeChainMayInterceptStoreTo): (JSC::Structure::dump): (JSC::Structure::despecifyDictionaryFunction): Deleted. (JSC::Structure::despecifyFunctionTransition): Deleted. (JSC::Structure::despecifyFunction): Deleted. (JSC::Structure::despecifyAllFunctions): Deleted. (JSC::Structure::putSpecificValue): Deleted.
  • runtime/Structure.h: (JSC::Structure::startWatchingPropertyForReplacements): (JSC::Structure::startWatchingInternalPropertiesIfNecessary): (JSC::Structure::startWatchingInternalPropertiesIfNecessaryForEntireChain): (JSC::Structure::transitionDidInvolveSpecificValue): Deleted. (JSC::Structure::disableSpecificFunctionTracking): Deleted.
  • runtime/StructureInlines.h: (JSC::Structure::getConcurrently): (JSC::Structure::didReplaceProperty): (JSC::Structure::propertyReplacementWatchpointSet):
  • runtime/StructureRareData.cpp: (JSC::StructureRareData::destroy):
  • runtime/StructureRareData.h:
  • tests/stress/infer-constant-global-property.js: Added. (foo.Math.sin): (foo):
  • tests/stress/infer-constant-property.js: Added. (foo):
  • tests/stress/jit-cache-poly-replace-then-cache-get-and-fold-then-invalidate.js: Added. (foo): (bar):
  • tests/stress/jit-cache-replace-then-cache-get-and-fold-then-invalidate.js: Added. (foo): (bar):
  • tests/stress/jit-put-to-scope-global-cache-watchpoint-invalidate.js: Added. (foo): (bar):
  • tests/stress/llint-cache-replace-then-cache-get-and-fold-then-invalidate.js: Added. (foo): (bar):
  • tests/stress/llint-put-to-scope-global-cache-watchpoint-invalidate.js: Added. (foo): (bar):
  • tests/stress/repeat-put-to-scope-global-with-same-value-watchpoint-invalidate.js: Added. (foo): (bar):


2014-07-03 Saam Barati <​[email protected]>


Add more coverage for the profile_types_with_high_fidelity op code.
​https://bugs.webkit.org/show_bug.cgi?id=134616


Reviewed by Filip Pizlo.


More operations are now being recorded by the profile_types_with_high_fidelity
opcode. Specifically: function parameters, function return values,
function 'this' value, get_by_id, get_by_value, resolve nodes, function return
values at the call site. Added more flags to the profile_types_with_high_fidelity
opcode so more focused tasks can take place when the instruction is
being linked in CodeBlock. Re-worked the type profiler to search
through character offset ranges when asked for the type of an expression
at a given offset. Removed redundant calls to Structure::toStructureShape
in HighFidelityLog and TypeSet by caching calls based on StructureID.


  • bytecode/BytecodeList.json:
  • bytecode/BytecodeUseDef.h: (JSC::computeUsesForBytecodeOffset): (JSC::computeDefsForBytecodeOffset):
  • bytecode/CodeBlock.cpp: (JSC::CodeBlock::CodeBlock): (JSC::CodeBlock::finalizeUnconditionally): (JSC::CodeBlock::scopeDependentProfile):
  • bytecode/CodeBlock.h: (JSC::CodeBlock::returnStatementTypeSet):
  • bytecode/TypeLocation.h:
  • bytecode/UnlinkedCodeBlock.cpp: (JSC::UnlinkedCodeBlock::highFidelityTypeProfileExpressionInfoForBytecodeOffset): (JSC::UnlinkedCodeBlock::addHighFidelityTypeProfileExpressionInfo):
  • bytecode/UnlinkedCodeBlock.h:
  • bytecompiler/BytecodeGenerator.cpp: (JSC::BytecodeGenerator::emitMove): (JSC::BytecodeGenerator::emitProfileTypesWithHighFidelity): (JSC::BytecodeGenerator::emitGetFromScopeWithProfile): (JSC::BytecodeGenerator::emitPutToScope): (JSC::BytecodeGenerator::emitPutToScopeWithProfile): (JSC::BytecodeGenerator::emitPutById): (JSC::BytecodeGenerator::emitPutByVal):
  • bytecompiler/BytecodeGenerator.h: (JSC::BytecodeGenerator::emitHighFidelityTypeProfilingExpressionInfo):
  • bytecompiler/NodesCodegen.cpp: (JSC::ResolveNode::emitBytecode): (JSC::BracketAccessorNode::emitBytecode): (JSC::DotAccessorNode::emitBytecode): (JSC::FunctionCallValueNode::emitBytecode): (JSC::FunctionCallResolveNode::emitBytecode): (JSC::FunctionCallBracketNode::emitBytecode): (JSC::FunctionCallDotNode::emitBytecode): (JSC::CallFunctionCallDotNode::emitBytecode): (JSC::ApplyFunctionCallDotNode::emitBytecode): (JSC::PostfixNode::emitResolve): (JSC::PostfixNode::emitBracket): (JSC::PostfixNode::emitDot): (JSC::PrefixNode::emitResolve): (JSC::PrefixNode::emitBracket): (JSC::PrefixNode::emitDot): (JSC::ReadModifyResolveNode::emitBytecode): (JSC::AssignResolveNode::emitBytecode): (JSC::AssignDotNode::emitBytecode): (JSC::ReadModifyDotNode::emitBytecode): (JSC::AssignBracketNode::emitBytecode): (JSC::ReadModifyBracketNode::emitBytecode): (JSC::ReturnNode::emitBytecode): (JSC::FunctionBodyNode::emitBytecode):
  • inspector/agents/InspectorRuntimeAgent.cpp: (Inspector::InspectorRuntimeAgent::getRuntimeTypeForVariableAtOffset): (Inspector::InspectorRuntimeAgent::getRuntimeTypeForVariableInTextRange): Deleted.
  • inspector/agents/InspectorRuntimeAgent.h:
  • inspector/protocol/Runtime.json:
  • llint/LLIntSlowPaths.cpp: (JSC::LLInt::getFromScopeCommon): (JSC::LLInt::LLINT_SLOW_PATH_DECL):
  • llint/LLIntSlowPaths.h:
  • llint/LowLevelInterpreter.asm:
  • runtime/HighFidelityLog.cpp: (JSC::HighFidelityLog::processHighFidelityLog): (JSC::HighFidelityLog::actuallyProcessLogThreadFunction): (JSC::HighFidelityLog::recordTypeInformationForLocation): Deleted.
  • runtime/HighFidelityLog.h: (JSC::HighFidelityLog::recordTypeInformationForLocation):
  • runtime/HighFidelityTypeProfiler.cpp: (JSC::HighFidelityTypeProfiler::getTypesForVariableInAtOffset): (JSC::HighFidelityTypeProfiler::getGlobalTypesForVariableAtOffset): (JSC::HighFidelityTypeProfiler::getLocalTypesForVariableAtOffset): (JSC::HighFidelityTypeProfiler::insertNewLocation): (JSC::HighFidelityTypeProfiler::findLocation): (JSC::HighFidelityTypeProfiler::getTypesForVariableInRange): Deleted. (JSC::HighFidelityTypeProfiler::getGlobalTypesForVariableInRange): Deleted. (JSC::HighFidelityTypeProfiler::getLocalTypesForVariableInRange): Deleted. (JSC::HighFidelityTypeProfiler::getLocationBasedHash): Deleted.
  • runtime/HighFidelityTypeProfiler.h: (JSC::LocationKey::LocationKey): Deleted. (JSC::LocationKey::hash): Deleted. (JSC::LocationKey::operator==): Deleted.
  • runtime/Structure.cpp: (JSC::Structure::toStructureShape):
  • runtime/Structure.h:
  • runtime/TypeSet.cpp: (JSC::TypeSet::TypeSet): (JSC::TypeSet::addTypeForValue): (JSC::TypeSet::seenTypes): (JSC::TypeSet::removeDuplicatesInStructureHistory): Deleted.
  • runtime/TypeSet.h: (JSC::StructureShape::setConstructorName):
  • runtime/VM.cpp: (JSC::VM::getTypesForVariableAtOffset): (JSC::VM::dumpHighFidelityProfilingTypes): (JSC::VM::getTypesForVariableInRange): Deleted.
  • runtime/VM.h:


2014-07-04 Filip Pizlo <​[email protected]>


[ftlopt][REGRESSION] debug tests fail because PutByIdDirect is now implemented in terms of In
​https://bugs.webkit.org/show_bug.cgi?id=134642


Rubber stamped by Andreas Kling.


  • ftl/FTLLowerDFGToLLVM.cpp: (JSC::FTL::LowerDFGToLLVM::compileNode):


2014-07-01 Filip Pizlo <​[email protected]>


[ftlopt] Allocate a new GetterSetter if we change the value of any of its entries other than when they were previously null, so that if we constant-infer an accessor slot then we immediately get the function constant for free
​https://bugs.webkit.org/show_bug.cgi?id=134518


Reviewed by Mark Hahnenberg.


This has no real effect right now, particularly since almost all uses of
setSetter/setGetter were already allocating a branch new GetterSetter. But once we start
doing more aggressive constant property inference, this change will allow us to remove
all runtime checks from getter/setter calls.


  • runtime/GetterSetter.cpp: (JSC::GetterSetter::withGetter): (JSC::GetterSetter::withSetter):
  • runtime/GetterSetter.h: (JSC::GetterSetter::setGetter): (JSC::GetterSetter::setSetter):
  • runtime/JSObject.cpp: (JSC::JSObject::defineOwnNonIndexProperty):


2014-07-02 Filip Pizlo <​[email protected]>


[ftlopt] Rename notifyTransitionFromThisStructure to didTransitionFromThisStructure


Rubber stamped by Mark Hahnenberg.


  • runtime/Structure.cpp: (JSC::Structure::Structure): (JSC::Structure::nonPropertyTransition): (JSC::Structure::didTransitionFromThisStructure): (JSC::Structure::notifyTransitionFromThisStructure): Deleted.
  • runtime/Structure.h:


2014-07-02 Filip Pizlo <​[email protected]>


[ftlopt] Remove the functionality for cloning StructureRareData since we never do that anymore.


Rubber stamped by Mark Hahnenberg.


  • runtime/Structure.cpp: (JSC::Structure::Structure): (JSC::Structure::cloneRareDataFrom): Deleted.
  • runtime/Structure.h:
  • runtime/StructureRareData.cpp: (JSC::StructureRareData::clone): Deleted. (JSC::StructureRareData::StructureRareData): Deleted.
  • runtime/StructureRareData.h: (JSC::StructureRareData::needsCloning): Deleted.


2014-07-01 Mark Lam <​[email protected]>


[ftlopt] DebuggerCallFrame::scope() should return a DebuggerScope.
<​https://webkit.org/b/134420>


Reviewed by Geoffrey Garen.


Previously, DebuggerCallFrame::scope() returns a JSActivation (and relevant
peers) which the WebInspector will use to introspect CallFrame variables.
Instead, we should be returning a DebuggerScope as an abstraction layer that
provides the introspection functionality that the WebInspector needs. This
is the first step towards not forcing every frame to have a JSActivation
object just because the debugger is enabled.


  1. Instantiate the debuggerScopeStructure as a member of the JSGlobalObject instead of the VM. This allows JSObject::globalObject() to be able to return the global object for the DebuggerScope.


  1. On the DebuggerScope's life-cycle management:


The DebuggerCallFrame is designed to be "valid" only during a debugging session
(while the debugger is broken) through the use of a DebuggerCallFrameScope in
Debugger::pauseIfNeeded(). Once the debugger resumes from the break, the
DebuggerCallFrameScope destructs, and the DebuggerCallFrame will be invalidated.
We can't guarantee (from this code alone) that the Inspector code isn't still
holding a ref to the DebuggerCallFrame (though they shouldn't), but by contract,
the frame will be invalidated, and any attempt to query it will return null values.
This is pre-existing behavior.


Now, we're adding the DebuggerScope into the picture. While a single debugger
pause session is in progress, the Inspector may request the scope from the
DebuggerCallFrame. While the DebuggerCallFrame is still valid, we want
DebuggerCallFrame::scope() to always return the same DebuggerScope object.
This is why we hold on to the DebuggerScope with a strong ref.


If we use a weak ref instead, the following cooky behavior can manifest:

  1. The Inspector calls Debugger::scope() to get the top scope.
  2. The Inspector iterates down the scope chain and is now only holding a reference to a parent scope. It is no longer referencing the top scope.
  3. A GC occurs, and the DebuggerCallFrame's weak m_scope ref to the top scope gets cleared.
  4. The Inspector calls DebuggerCallFrame::scope() to get the top scope again but gets a different DebuggerScope instance.
  5. The Inspector iterates down the scope chain but never sees the parent scope instance that retained a ref to in step 2 above. This is because when iterating this new DebuggerScope instance (which has no knowledge of the previous parent DebuggerScope instance), a new DebuggerScope instance will get created for the same parent scope.


Since the DebuggerScope is a JSObject, it's liveness is determined by its reachability.
However, it's "validity" is determined by the life-cycle of its owner DebuggerCallFrame.
When the owner DebuggerCallFrame gets invalidated, its debugger scope chain (if
instantiated) will also get invalidated. This is why we need the
DebuggerScope::invalidateChain() method. The Inspector should not be using the
DebuggerScope instance after its owner DebuggerCallFrame is invalidated. If it does,
those methods will do nothing or returned a failed status.


  • debugger/Debugger.h:
  • debugger/DebuggerCallFrame.cpp: (JSC::DebuggerCallFrame::scope): (JSC::DebuggerCallFrame::evaluate): (JSC::DebuggerCallFrame::invalidate): (JSC::DebuggerCallFrame::vm): (JSC::DebuggerCallFrame::lexicalGlobalObject):
  • debugger/DebuggerCallFrame.h:
  • debugger/DebuggerScope.cpp: (JSC::DebuggerScope::DebuggerScope): (JSC::DebuggerScope::finishCreation): (JSC::DebuggerScope::visitChildren): (JSC::DebuggerScope::className): (JSC::DebuggerScope::getOwnPropertySlot): (JSC::DebuggerScope::put): (JSC::DebuggerScope::deleteProperty): (JSC::DebuggerScope::getOwnPropertyNames): (JSC::DebuggerScope::defineOwnProperty): (JSC::DebuggerScope::next): (JSC::DebuggerScope::invalidateChain): (JSC::DebuggerScope::isWithScope): (JSC::DebuggerScope::isGlobalScope): (JSC::DebuggerScope::isFunctionScope):
  • debugger/DebuggerScope.h: (JSC::DebuggerScope::create): (JSC::DebuggerScope::Iterator::Iterator): (JSC::DebuggerScope::Iterator::get): (JSC::DebuggerScope::Iterator::operator++): (JSC::DebuggerScope::Iterator::operator==): (JSC::DebuggerScope::Iterator::operator!=): (JSC::DebuggerScope::isValid): (JSC::DebuggerScope::jsScope): (JSC::DebuggerScope::begin): (JSC::DebuggerScope::end):
  • inspector/JSJavaScriptCallFrame.cpp: (Inspector::JSJavaScriptCallFrame::scopeType): (Inspector::JSJavaScriptCallFrame::scopeChain):
  • inspector/JavaScriptCallFrame.h: (Inspector::JavaScriptCallFrame::scopeChain):
  • inspector/ScriptDebugServer.cpp:
  • runtime/JSGlobalObject.cpp: (JSC::JSGlobalObject::reset): (JSC::JSGlobalObject::visitChildren):
  • runtime/JSGlobalObject.h: (JSC::JSGlobalObject::debuggerScopeStructure):
  • runtime/JSObject.h: (JSC::JSObject::isWithScope):
  • runtime/JSScope.h:
  • runtime/VM.cpp: (JSC::VM::VM):
  • runtime/VM.h:


2014-07-01 Filip Pizlo <​[email protected]>


[ftlopt] DFG bytecode parser should turn PutById with nothing but a Setter stub as stuff+handleCall, and handleCall should be allowed to inline if it wants to
​https://bugs.webkit.org/show_bug.cgi?id=130756


Reviewed by Oliver Hunt.


The enables exposing the call to setters in the DFG, and then inlining it. Previously we
already supproted inlined-cached calls to setters from within put_by_id inline caches,
and the DFG could certainly emit such IC's. Now, if an IC had a setter call, then the DFG
will either emit the GetGetterSetterByOffset/GetSetter/Call combo, or it will do one
better and inline the call.


A lot of the core functionality was already available from the previous work to inline
getters. So, there are some refactorings in this patch that move preexisting
functionality around. For example, the work to figure out how the DFG should go about
getting to what we call the "loaded value" - i.e. the GetterSetter object reference in
the case of accessors - is now shared in ComplexGetStatus, and both GetByIdStatus and
PutByIdStatus use it. This means that we can keep the safety checks common. This patch
also does additional refactorings in DFG::ByteCodeParser so that we can continue to reuse
handleCall() for all of the various kinds of calls we can now emit.


83% speed-up on getter-richards, 2% speed-up on box2d.


  • CMakeLists.txt:
  • JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • bytecode/ComplexGetStatus.cpp: Added. (JSC::ComplexGetStatus::computeFor):
  • bytecode/ComplexGetStatus.h: Added. (JSC::ComplexGetStatus::ComplexGetStatus): (JSC::ComplexGetStatus::skip): (JSC::ComplexGetStatus::takesSlowPath): (JSC::ComplexGetStatus::kind): (JSC::ComplexGetStatus::attributes): (JSC::ComplexGetStatus::specificValue): (JSC::ComplexGetStatus::offset): (JSC::ComplexGetStatus::chain):
  • bytecode/GetByIdStatus.cpp: (JSC::GetByIdStatus::computeForStubInfo):
  • bytecode/GetByIdVariant.cpp: (JSC::GetByIdVariant::GetByIdVariant):
  • bytecode/PolymorphicPutByIdList.h: (JSC::PutByIdAccess::PutByIdAccess): (JSC::PutByIdAccess::setter): (JSC::PutByIdAccess::structure): (JSC::PutByIdAccess::chainCount):
  • bytecode/PutByIdStatus.cpp: (JSC::PutByIdStatus::computeFromLLInt): (JSC::PutByIdStatus::computeFor): (JSC::PutByIdStatus::computeForStubInfo): (JSC::PutByIdStatus::makesCalls):
  • bytecode/PutByIdStatus.h: (JSC::PutByIdStatus::makesCalls): Deleted.
  • bytecode/PutByIdVariant.cpp: (JSC::PutByIdVariant::PutByIdVariant): (JSC::PutByIdVariant::operator=): (JSC::PutByIdVariant::replace): (JSC::PutByIdVariant::transition): (JSC::PutByIdVariant::setter): (JSC::PutByIdVariant::writesStructures): (JSC::PutByIdVariant::reallocatesStorage): (JSC::PutByIdVariant::makesCalls): (JSC::PutByIdVariant::dumpInContext):
  • bytecode/PutByIdVariant.h: (JSC::PutByIdVariant::PutByIdVariant): (JSC::PutByIdVariant::structure): (JSC::PutByIdVariant::oldStructure): (JSC::PutByIdVariant::alternateBase): (JSC::PutByIdVariant::specificValue): (JSC::PutByIdVariant::callLinkStatus): (JSC::PutByIdVariant::replace): Deleted. (JSC::PutByIdVariant::transition): Deleted.
  • dfg/DFGByteCodeParser.cpp: (JSC::DFG::ByteCodeParser::addCallWithoutSettingResult): (JSC::DFG::ByteCodeParser::addCall): (JSC::DFG::ByteCodeParser::handleCall): (JSC::DFG::ByteCodeParser::handleInlining): (JSC::DFG::ByteCodeParser::handleGetById): (JSC::DFG::ByteCodeParser::handlePutById): (JSC::DFG::ByteCodeParser::parseBlock):
  • jit/Repatch.cpp: (JSC::tryCachePutByID): (JSC::tryBuildPutByIdList):
  • runtime/IntendedStructureChain.cpp: (JSC::IntendedStructureChain::takesSlowPathInDFGForImpureProperty):
  • runtime/IntendedStructureChain.h:
  • tests/stress/exit-from-setter.js: Added.
  • tests/stress/poly-chain-setter.js: Added. (Cons): (foo): (test):
  • tests/stress/poly-chain-then-setter.js: Added. (Cons1): (Cons2): (foo): (test):
  • tests/stress/poly-setter-combo.js: Added. (Cons1): (Cons2): (foo): (test): (.test):
  • tests/stress/poly-setter-then-self.js: Added. (foo): (test): (.test):
  • tests/stress/weird-setter-counter.js: Added. (foo): (test):
  • tests/stress/weird-setter-counter-syntactic.js: Added. (foo): (test):


2014-07-01 Matthew Mirman <​[email protected]>


Added an implementation of the "in" check to FTL.
​https://bugs.webkit.org/show_bug.cgi?id=134508


Reviewed by Filip Pizlo.


  • ftl/FTLCapabilities.cpp: enabled compilation for "in" (JSC::FTL::canCompile): ditto
  • ftl/FTLCompile.cpp: (JSC::FTL::generateCheckInICFastPath): added. (JSC::FTL::fixFunctionBasedOnStackMaps): added case for CheckIn descriptors.
  • ftl/FTLInlineCacheDescriptor.h: (JSC::FTL::CheckInGenerator::CheckInGenerator): added. (JSC::FTL::CheckInDescriptor::CheckInDescriptor): added.
  • ftl/FTLInlineCacheSize.cpp: (JSC::FTL::sizeOfCheckIn): added. Currently larger than necessary.
  • ftl/FTLInlineCacheSize.h: ditto
  • ftl/FTLIntrinsicRepository.h: Added function type for operationInGeneric
  • ftl/FTLLowerDFGToLLVM.cpp: (JSC::FTL::LowerDFGToLLVM::compileNode): added case for In. (JSC::FTL::LowerDFGToLLVM::compileIn): added.
  • ftl/FTLSlowPathCall.cpp: Added a callOperation for operationIn (JSC::FTL::callOperation): ditto
  • ftl/FTLSlowPathCall.h: ditto
  • ftl/FTLState.h: Added a vector to hold CheckIn descriptors.
  • jit/JITOperations.h: made operationIns internal.
  • tests/stress/ftl-checkin.js: Added.
  • tests/stress/ftl-checkin-variable.js: Added.


2014-06-30 Mark Hahnenberg <​[email protected]>


CodeBlock::stronglyVisitWeakReferences should mark DFG::CommonData::weakStructureReferences
​https://bugs.webkit.org/show_bug.cgi?id=134455


Reviewed by Geoffrey Garen.


Otherwise we get hanging pointers which can cause us to die later.


  • bytecode/CodeBlock.cpp: (JSC::CodeBlock::stronglyVisitWeakReferences):


2014-06-27 Filip Pizlo <​[email protected]>


[ftlopt] Reduce the GC's influence on optimization decisions
​https://bugs.webkit.org/show_bug.cgi?id=134427


Reviewed by Oliver Hunt.


This is a slight speed-up on some platforms, that arises from a bunch of fixes that I made
while trying to make the GC keep more structures alive
(​https://bugs.webkit.org/show_bug.cgi?id=128072).


The fixes are, roughly:


  • If the GC clears an inline cache, then this no longer causes the IC to be forever polymorphic.


  • If we exit in inlined code into a function that tries to OSR enter, then we jettison sooner.


  • Some variables being uninitialized led to rage-recompilations.


This is a pretty strong step in the direction of keeping more Structures alive and not
blowing away code just because a Structure died. But, it seems like there is still a slight
speed-up to be had from blowing away code that references dead Structures.


  • bytecode/CodeBlock.cpp: (JSC::CodeBlock::dumpAssumingJITType): (JSC::shouldMarkTransition): (JSC::CodeBlock::propagateTransitions): (JSC::CodeBlock::determineLiveness):
  • bytecode/GetByIdStatus.cpp: (JSC::GetByIdStatus::computeForStubInfo):
  • bytecode/PutByIdStatus.cpp: (JSC::PutByIdStatus::computeForStubInfo):
  • dfg/DFGCapabilities.cpp: (JSC::DFG::isSupportedForInlining): (JSC::DFG::mightInlineFunctionForCall): (JSC::DFG::mightInlineFunctionForClosureCall): (JSC::DFG::mightInlineFunctionForConstruct):
  • dfg/DFGCapabilities.h:
  • dfg/DFGCommonData.h:
  • dfg/DFGDesiredWeakReferences.cpp: (JSC::DFG::DesiredWeakReferences::reallyAdd):
  • dfg/DFGOSREntry.cpp: (JSC::DFG::prepareOSREntry):
  • dfg/DFGOSRExitCompilerCommon.cpp: (JSC::DFG::handleExitCounts):
  • dfg/DFGOperations.cpp:
  • dfg/DFGOperations.h:
  • ftl/FTLForOSREntryJITCode.cpp: (JSC::FTL::ForOSREntryJITCode::ForOSREntryJITCode): These variables being uninitialized is benign in terms of correctness but can sometimes cause rage-recompilations. For some reason it took this patch to reveal this.
  • ftl/FTLOSREntry.cpp: (JSC::FTL::prepareOSREntry):
  • runtime/Executable.cpp: (JSC::ExecutableBase::destroy): (JSC::NativeExecutable::destroy): (JSC::ScriptExecutable::ScriptExecutable): (JSC::ScriptExecutable::destroy): (JSC::ScriptExecutable::installCode): (JSC::EvalExecutable::EvalExecutable): (JSC::ProgramExecutable::ProgramExecutable):
  • runtime/Executable.h: (JSC::ScriptExecutable::setDidTryToEnterInLoop): (JSC::ScriptExecutable::didTryToEnterInLoop): (JSC::ScriptExecutable::addressOfDidTryToEnterInLoop): (JSC::ScriptExecutable::ScriptExecutable): Deleted.
  • runtime/StructureInlines.h: (JSC::Structure::storedPrototypeObject): (JSC::Structure::storedPrototypeStructure):


2014-06-25 Filip Pizlo <​[email protected]>


[ftlopt] If a CodeBlock is jettisoned due to a watchpoint then it should be possible to figure out something about that watchpoint
​https://bugs.webkit.org/show_bug.cgi?id=134333


Reviewed by Geoffrey Garen.


This is engineered to provide loads of information to the profiler without incurring any
costs when the profiler is disabled. It's the oldest trick in the book: the thing that
fires the watchpoint doesn't actually create anything to describe the reason why it was
fired; instead it creates a stack-allocated FireDetail subclass instance. Only if the
FireDetail::dump() virtual method is called does anything happen.


Currently we use this to produce very fine-grained data for Structure watchpoints and
some cases of variable watchpoints. For all other situations, the given reason is just a
string constant, by using StringFireDetail. If we find a situation where that string
constant is insufficient to diagnose an issue then we can change it to provide more
fine-grained information.


  • JavaScriptCore.xcodeproj/project.pbxproj:
  • bytecode/CodeBlock.cpp: (JSC::CodeBlock::CodeBlock): (JSC::CodeBlock::jettison):
  • bytecode/CodeBlock.h:
  • bytecode/CodeBlockJettisoningWatchpoint.cpp: (JSC::CodeBlockJettisoningWatchpoint::fireInternal):
  • bytecode/CodeBlockJettisoningWatchpoint.h:
  • bytecode/ProfiledCodeBlockJettisoningWatchpoint.cpp: Removed.
  • bytecode/ProfiledCodeBlockJettisoningWatchpoint.h: Removed.
  • bytecode/StructureStubClearingWatchpoint.cpp: (JSC::StructureStubClearingWatchpoint::fireInternal):
  • bytecode/StructureStubClearingWatchpoint.h:
  • bytecode/VariableWatchpointSet.h: (JSC::VariableWatchpointSet::invalidate): (JSC::VariableWatchpointSet::finalizeUnconditionally):
  • bytecode/VariableWatchpointSetInlines.h: (JSC::VariableWatchpointSet::notifyWrite):
  • bytecode/Watchpoint.cpp: (JSC::StringFireDetail::dump): (JSC::WatchpointSet::fireAll): (JSC::WatchpointSet::fireAllSlow): (JSC::WatchpointSet::fireAllWatchpoints): (JSC::InlineWatchpointSet::fireAll):
  • bytecode/Watchpoint.h: (JSC::FireDetail::FireDetail): (JSC::FireDetail::~FireDetail): (JSC::StringFireDetail::StringFireDetail): (JSC::Watchpoint::fire): (JSC::WatchpointSet::fireAll): (JSC::WatchpointSet::touch): (JSC::WatchpointSet::invalidate): (JSC::InlineWatchpointSet::fireAll): (JSC::InlineWatchpointSet::touch):
  • dfg/DFGCommonData.h:
  • dfg/DFGOperations.cpp:
  • interpreter/Interpreter.cpp: (JSC::Interpreter::execute):
  • jsc.cpp: (WTF::Masquerader::create):
  • profiler/ProfilerCompilation.cpp: (JSC::Profiler::Compilation::setJettisonReason): (JSC::Profiler::Compilation::toJS):
  • profiler/ProfilerCompilation.h: (JSC::Profiler::Compilation::setJettisonReason): Deleted.
  • runtime/ArrayBuffer.cpp: (JSC::ArrayBuffer::transfer):
  • runtime/ArrayBufferNeuteringWatchpoint.cpp: (JSC::ArrayBufferNeuteringWatchpoint::fireAll):
  • runtime/ArrayBufferNeuteringWatchpoint.h:
  • runtime/CommonIdentifiers.h:
  • runtime/CommonSlowPaths.cpp: (JSC::SLOW_PATH_DECL):
  • runtime/Identifier.cpp: (JSC::Identifier::dump):
  • runtime/Identifier.h:
  • runtime/JSFunction.cpp: (JSC::JSFunction::put): (JSC::JSFunction::defineOwnProperty):
  • runtime/JSGlobalObject.cpp: (JSC::JSGlobalObject::addFunction): (JSC::JSGlobalObject::haveABadTime):
  • runtime/JSSymbolTableObject.cpp: (JSC::VariableWriteFireDetail::dump):
  • runtime/JSSymbolTableObject.h: (JSC::VariableWriteFireDetail::VariableWriteFireDetail): (JSC::symbolTablePut): (JSC::symbolTablePutWithAttributes):
  • runtime/PropertyName.h: (JSC::PropertyName::dump):
  • runtime/Structure.cpp: (JSC::Structure::notifyTransitionFromThisStructure):
  • runtime/Structure.h: (JSC::Structure::notifyTransitionFromThisStructure): Deleted.
  • runtime/SymbolTable.cpp: (JSC::SymbolTableEntry::notifyWriteSlow): (JSC::SymbolTable::WatchpointCleanup::finalizeUnconditionally):
  • runtime/SymbolTable.h: (JSC::SymbolTableEntry::notifyWrite):
  • runtime/VM.cpp: (JSC::VM::addImpureProperty):

Source/WebCore:

2014-07-01 Mark Lam <​[email protected]>


[ftlopt] DebuggerCallFrame::scope() should return a DebuggerScope.
<​https://webkit.org/b/134420>


Reviewed by Geoffrey Garen.


No new tests.


  • ForwardingHeaders/debugger/DebuggerCallFrame.h: Removed.
  • This is not in use. Hence, we can remove it.
  • bindings/js/ScriptController.cpp: (WebCore::ScriptController::attachDebugger):
  • We should acquire the JSLock before modifying a JS global object.


2014-06-25 Filip Pizlo <​[email protected]>


[ftlopt] If a CodeBlock is jettisoned due to a watchpoint then it should be possible to figure out something about that watchpoint
​https://bugs.webkit.org/show_bug.cgi?id=134333


Reviewed by Geoffrey Garen.


No new tests because no change in behavior.


  • bindings/scripts/CodeGeneratorJS.pm: (GenerateHeader):

Tools:

2014-06-25 Filip Pizlo <​[email protected]>


[ftlopt] If a CodeBlock is jettisoned due to a watchpoint then it should be possible to figure out something about that watchpoint
​https://bugs.webkit.org/show_bug.cgi?id=134333


Reviewed by Geoffrey Garen.


  • Scripts/display-profiler-output:

LayoutTests:

2014-07-16 Mark Hahnenberg <​[email protected]>


sputnik/Implementation_Diagnostics/S12.6.4_D1.html depends on undefined behavior
​https://bugs.webkit.org/show_bug.cgi?id=135007


Reviewed by Filip Pizlo.


EcmaScript 5.1 specifies that during for-in enumeration newly added properties may or may not be
visited during the current enumeration. Specifically, in section 12.6.4 the spec states:


"If new properties are added to the object being enumerated during enumeration, the newly added properties
are not guaranteed to be visited in the active enumeration."


The sputnik/Implementation_Diagnostics/S12.6.4_D1.html layout test is from before sputnik was added
to the test262 suite. I believe it has since been removed, so it would probably be okay to remove it
from our layout test suite.


  • sputnik/Implementation_Diagnostics/S12.6.4_D1-expected.txt: Removed.
  • sputnik/Implementation_Diagnostics/S12.6.4_D1.html: Removed.


2014-07-13 Filip Pizlo <​[email protected]>


[ftlopt] DFG should be able to do GCSE in SSA and this should be unified with the CSE in CPS, and both of these things should use abstract heaps for reasoning about effects
​https://bugs.webkit.org/show_bug.cgi?id=134677


Reviewed by Sam Weinig.


  • js/regress/gcse-expected.txt: Added.
  • js/regress/gcse-poly-get-expected.txt: Added.
  • js/regress/gcse-poly-get-less-obvious-expected.txt: Added.
  • js/regress/gcse-poly-get-less-obvious.html: Added.
  • js/regress/gcse-poly-get.html: Added.
  • js/regress/gcse.html: Added.
  • js/regress/script-tests/gcse-poly-get-less-obvious.js: Added.
  • js/regress/script-tests/gcse-poly-get.js: Added.
  • js/regress/script-tests/gcse.js: Added.


2014-07-04 Filip Pizlo <​[email protected]>


[ftlopt] Infer immutable object properties
​https://bugs.webkit.org/show_bug.cgi?id=134567


Reviewed by Mark Hahnenberg.


  • js/regress/infer-constant-global-property-expected.txt: Added.
  • js/regress/infer-constant-global-property.html: Added.
  • js/regress/infer-constant-property-expected.txt: Added.
  • js/regress/infer-constant-property.html: Added.
  • js/regress/script-tests/infer-constant-global-property.js: Added.
  • js/regress/script-tests/infer-constant-property.js: Added.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp

    r171613 r172129  
    3030
    3131#include "DFGAbstractHeap.h"
     32#include "DFGClobberSet.h"
    3233#include "DFGClobberize.h"
    3334#include "DFGEdgeUsesStructure.h"
    … …  
    4041namespace JSC { namespace DFG {
    4142
    42 class CSEPhase : public Phase {
     43// This file contains two CSE implementations: local and global. LocalCSE typically runs when we're
     44// in DFG mode, i.e. we want to compile quickly. LocalCSE contains a lot of optimizations for
     45// compile time. GlobalCSE, on the other hand, is fairly straight-forward. It will find more
     46// optimization opportunities by virtue of being global.
     47
     48namespace {
     49
     50const bool verbose = false;
     51
     52class ClobberFilter {
    4353public:
    44     CSEPhase(Graph& graph)
    45         : Phase(graph, "common subexpression elimination")
     54    ClobberFilter(AbstractHeap heap)
     55        : m_heap(heap)
     56    {
     57    }
     58   
     59    bool operator()(const ImpureMap::KeyValuePairType& pair) const
     60    {
     61        return m_heap.overlaps(pair.key.heap());
     62    }
     63   
     64private:
     65    AbstractHeap m_heap;
     66};
     67
     68inline void clobber(ImpureMap& map, AbstractHeap heap)
     69{
     70    ClobberFilter filter(heap);
     71    map.removeIf(filter);
     72}
     73
     74class LocalCSEPhase : public Phase {
     75public:
     76    LocalCSEPhase(Graph& graph)
     77        : Phase(graph, "local common subexpression elimination")
     78        , m_smallBlock(graph)
     79        , m_largeBlock(graph)
    4680    {
    4781    }
    … …  
    4983    bool run()
    5084    {
    51         ASSERT(m_graph.m_fixpointState != BeforeFixpoint);
    52        
    53         m_changed = false;
     85        ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
     86        ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == LoadStore);
     87       
     88        bool changed = false;
    5489       
    5590        m_graph.clearReplacements();
    … …  
    6095                continue;
    6196           
    62             // All Phis need to already be marked as relevant to OSR.
    63             if (!ASSERT_DISABLED) {
    64                 for (unsigned i = 0; i < block->phis.size(); ++i)
    65                     ASSERT(block->phis[i]->flags() & NodeRelevantToOSR);
    66             }
    67            
    68             for (unsigned i = block->size(); i--;) {
    69                 Node* node = block->at(i);
     97            if (block->size() <= SmallMaps::capacity)
     98                changed |= m_smallBlock.run(block);
     99            else
     100                changed |= m_largeBlock.run(block);
     101        }
     102       
     103        return changed;
     104    }
     105   
     106private:
     107    class SmallMaps {
     108    public:
     109        // This permits SmallMaps to be used for blocks that have up to 100 nodes. In practice,
     110        // fewer than half of the nodes in a block have pure defs, and even fewer have impure defs.
     111        // Thus, a capacity limit of 100 probably means that somewhere around ~40 things may end up
     112        // in one of these "small" list-based maps. That number still seems largeish, except that
     113        // the overhead of HashMaps can be quite high currently: clearing them, or even removing
     114        // enough things from them, deletes (or resizes) their backing store eagerly. Hence
     115        // HashMaps induce a lot of malloc traffic.
     116        static const unsigned capacity = 100;
     117   
     118        SmallMaps()
     119            : m_pureLength(0)
     120            , m_impureLength(0)
     121        {
     122        }
     123   
     124        void clear()
     125        {
     126            m_pureLength = 0;
     127            m_impureLength = 0;
     128        }
     129   
     130        void write(AbstractHeap heap)
     131        {
     132            for (unsigned i = 0; i < m_impureLength; ++i) {
     133                if (heap.overlaps(m_impureMap[i].key.heap()))
     134                    m_impureMap[i--] = m_impureMap[--m_impureLength];
     135            }
     136        }
     137   
     138        Node* addPure(PureValue value, Node* node)
     139        {
     140            for (unsigned i = m_pureLength; i--;) {
     141                if (m_pureMap[i].key == value)
     142                    return m_pureMap[i].value;
     143            }
     144       
     145            ASSERT(m_pureLength < capacity);
     146            m_pureMap[m_pureLength++] = WTF::KeyValuePair<PureValue, Node*>(value, node);
     147            return nullptr;
     148        }
     149       
     150        Node* findReplacement(HeapLocation location)
     151        {
     152            for (unsigned i = m_impureLength; i--;) {
     153                if (m_impureMap[i].key == location)
     154                    return m_impureMap[i].value;
     155            }
     156            return nullptr;
     157        }
     158   
     159        Node* addImpure(HeapLocation location, Node* node)
     160        {
     161            if (Node* result = findReplacement(location))
     162                return result;
     163            ASSERT(m_impureLength < capacity);
     164            m_impureMap[m_impureLength++] = WTF::KeyValuePair<HeapLocation, Node*>(location, node);
     165            return nullptr;
     166        }
     167   
     168    private:
     169        WTF::KeyValuePair<PureValue, Node*> m_pureMap[capacity];
     170        WTF::KeyValuePair<HeapLocation, Node*> m_impureMap[capacity];
     171        unsigned m_pureLength;
     172        unsigned m_impureLength;
     173    };
     174
     175    class LargeMaps {
     176    public:
     177        LargeMaps()
     178        {
     179        }
     180   
     181        void clear()
     182        {
     183            m_pureMap.clear();
     184            m_impureMap.clear();
     185        }
     186   
     187        void write(AbstractHeap heap)
     188        {
     189            clobber(m_impureMap, heap);
     190        }
     191   
     192        Node* addPure(PureValue value, Node* node)
     193        {
     194            auto result = m_pureMap.add(value, node);
     195            if (result.isNewEntry)
     196                return nullptr;
     197            return result.iterator->value;
     198        }
     199       
     200        Node* findReplacement(HeapLocation location)
     201        {
     202            return m_impureMap.get(location);
     203        }
     204   
     205        Node* addImpure(HeapLocation location, Node* node)
     206        {
     207            auto result = m_impureMap.add(location, node);
     208            if (result.isNewEntry)
     209                return nullptr;
     210            return result.iterator->value;
     211        }
     212
     213    private:
     214        HashMap<PureValue, Node*> m_pureMap;
     215        HashMap<HeapLocation, Node*> m_impureMap;
     216    };
     217
     218    template<typename Maps>
     219    class BlockCSE {
     220    public:
     221        BlockCSE(Graph& graph)
     222            : m_graph(graph)
     223        {
     224        }
     225   
     226        bool run(BasicBlock* block)
     227        {
     228            m_maps.clear();
     229            m_changed = false;
     230       
     231            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
     232                m_node = block->at(nodeIndex);
     233                m_graph.performSubstitution(m_node);
     234           
     235                if (m_node->op() == Identity) {
     236                    m_node->convertToCheck();
     237                    m_node->replacement = m_node->child1().node();
     238                    m_changed = true;
     239                } else {
     240                    // This rule only makes sense for local CSE, since in SSA form we have already
     241                    // factored the bounds check out of the PutByVal. It's kind of gross, but we
     242                    // still have reason to believe that PutByValAlias is a good optimization and
     243                    // that it's better to do it with a single node rather than separating out the
     244                    // CheckInBounds.
     245                    if (m_node->op() == PutByVal || m_node->op() == PutByValDirect) {
     246                        HeapLocation heap;
     247                       
     248                        Node* base = m_graph.varArgChild(m_node, 0).node();
     249                        Node* index = m_graph.varArgChild(m_node, 1).node();
     250                       
     251                        ArrayMode mode = m_node->arrayMode();
     252                        switch (mode.type()) {
     253                        case Array::Int32:
     254                            if (!mode.isInBounds())
     255                                break;
     256                            heap = HeapLocation(
     257                                IndexedPropertyLoc, IndexedInt32Properties, base, index);
     258                            break;
     259                           
     260                        case Array::Double:
     261                            if (!mode.isInBounds())
     262                                break;
     263                            heap = HeapLocation(
     264                                IndexedPropertyLoc, IndexedDoubleProperties, base, index);
     265                            break;
     266                           
     267                        case Array::Contiguous:
     268                            if (!mode.isInBounds())
     269                                break;
     270                            heap = HeapLocation(
     271                                IndexedPropertyLoc, IndexedContiguousProperties, base, index);
     272                            break;
     273                           
     274                        case Array::Int8Array:
     275                        case Array::Int16Array:
     276                        case Array::Int32Array:
     277                        case Array::Uint8Array:
     278                        case Array::Uint8ClampedArray:
     279                        case Array::Uint16Array:
     280                        case Array::Uint32Array:
     281                        case Array::Float32Array:
     282                        case Array::Float64Array:
     283                            if (!mode.isInBounds())
     284                                break;
     285                            heap = HeapLocation(
     286                                IndexedPropertyLoc, TypedArrayProperties, base, index);
     287                            break;
     288                           
     289                        default:
     290                            break;
     291                        }
     292
     293                        if (!!heap && m_maps.findReplacement(heap))
     294                            m_node->setOp(PutByValAlias);
     295                    }
     296
     297                    clobberize(m_graph, m_node, *this);
     298                }
     299            }
     300       
     301            return m_changed;
     302        }
     303   
     304        void read(AbstractHeap) { }
     305   
     306        void write(AbstractHeap heap)
     307        {
     308            m_maps.write(heap);
     309        }
     310       
     311        void def(PureValue value)
     312        {
     313            Node* match = m_maps.addPure(value, m_node);
     314            if (!match)
     315                return;
     316
     317            m_node->replaceWith(match);
     318            m_changed = true;
     319        }
     320   
     321        void def(HeapLocation location, Node* value)
     322        {
     323            Node* match = m_maps.addImpure(location, value);
     324            if (!match)
     325                return;
     326       
     327            if (m_node->op() == GetLocal) {
     328                // For uncaptured locals, usually the CPS rethreading phase does this. But it's OK
     329                // for us to mess with locals - regardless of their capturedness - so long as:
     330                //
     331                // - We dethread the graph. Any changes we make may invalidate the assumptions of
     332                //   our CPS form, particularly if this GetLocal is linked to the variablesAtTail.
     333                //
     334                // - We don't introduce a Phantom for the child of the GetLocal. This wouldn't be
     335                //   totally wrong but it would pessimize the code. Just because there is a
     336                //   GetLocal doesn't mean that the child was live. Simply rerouting the all uses
     337                //   of this GetLocal will preserve the live-at-exit information just fine.
     338                //
     339                // We accomplish the latter by just clearing the child; then the Phantom that we
     340                // introduce won't have children and so it will eventually just be deleted.
     341           
     342                m_node->child1() = Edge();
     343                m_graph.dethread();
     344            }
     345       
     346            m_node->replaceWith(match);
     347            m_changed = true;
     348        }
     349   
     350    private:
     351        Graph& m_graph;
     352       
     353        bool m_changed;
     354        Node* m_node;
     355   
     356        Maps m_maps;
     357    };
     358
     359    BlockCSE<SmallMaps> m_smallBlock;
     360    BlockCSE<LargeMaps> m_largeBlock;
     361};
     362
     363class GlobalCSEPhase : public Phase {
     364public:
     365    GlobalCSEPhase(Graph& graph)
     366        : Phase(graph, "global common subexpression elimination")
     367    {
     368    }
     369   
     370    bool run()
     371    {
     372        ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
     373        ASSERT(m_graph.m_form == SSA);
     374       
     375        m_graph.initializeNodeOwners();
     376        m_graph.m_dominators.computeIfNecessary(m_graph);
     377       
     378        m_graph.getBlocksInPreOrder(m_preOrder);
     379       
     380        m_impureDataMap.resize(m_graph.numBlocks());
     381       
     382        // First figure out what gets clobbered by blocks. Node that this uses the preOrder list
     383        // for convenience only.
     384        for (unsigned i = m_preOrder.size(); i--;) {
     385            m_block = m_preOrder[i];
     386            m_impureData = &m_impureDataMap[m_block->index];
     387            for (unsigned nodeIndex = m_block->size(); nodeIndex--;)
     388                addWrites(m_graph, m_block->at(nodeIndex), m_impureData->writes);
     389        }
     390       
     391        // Based on my experience doing this before, what follows might have to be made iterative.
     392        // Right now it doesn't have to be iterative because everything is dominator-bsed. But when
     393        // validation is enabled, we check if iterating would find new CSE opportunities.
     394
     395        bool changed = iterate();
     396       
     397        // Iterating a second time should not find new CSE opportunities, unless we have a bug.
     398        if (validationEnabled()) {
     399            reset();
     400            DFG_ASSERT(m_graph, nullptr, !iterate());
     401        }
     402       
     403        return changed;
     404    }
     405   
     406    void reset()
     407    {
     408        m_pureValues.clear();
     409       
     410        for (unsigned i = m_impureDataMap.size(); i--;) {
     411            m_impureDataMap[i].availableAtTail.clear();
     412            m_impureDataMap[i].didVisit = false;
     413        }
     414    }
     415   
     416    bool iterate()
     417    {
     418        if (verbose)
     419            dataLog("Performing iteration.\n");
     420       
     421        m_changed = false;
     422        m_graph.clearReplacements();
     423       
     424        for (unsigned i = 0; i < m_preOrder.size(); ++i) {
     425            m_block = m_preOrder[i];
     426            m_impureData = &m_impureDataMap[m_block->index];
     427            m_writesSoFar.clear();
     428           
     429            if (verbose)
     430                dataLog("Processing block ", *m_block, ":\n");
     431
     432            for (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
     433                m_node = m_block->at(nodeIndex);
     434                if (verbose)
     435                    dataLog("  Looking at node ", m_node, ":\n");
    70436               
    71                 switch (node->op()) {
    72                 case SetLocal:
    73                 case GetLocal: // FIXME: The GetLocal case is only necessary until we do https://bugs.webkit.org/show_bug.cgi?id=106707.
    74                     node->mergeFlags(NodeRelevantToOSR);
    75                     break;
    76                 default:
    77                     node->clearFlags(NodeRelevantToOSR);
    78                     break;
     437                m_graph.performSubstitution(m_node);
     438               
     439                if (m_node->op() == Identity) {
     440                    m_node->convertToCheck();
     441                    m_node->replacement = m_node->child1().node();
     442                    m_changed = true;
     443                } else
     444                    clobberize(m_graph, m_node, *this);
     445            }
     446           
     447            m_impureData->didVisit = true;
     448        }
     449       
     450        return m_changed;
     451    }
     452
     453    void read(AbstractHeap) { }
     454   
     455    void write(AbstractHeap heap)
     456    {
     457        clobber(m_impureData->availableAtTail, heap);
     458        m_writesSoFar.add(heap);
     459        if (verbose)
     460            dataLog("    Clobbered, new tail map: ", mapDump(m_impureData->availableAtTail), "\n");
     461    }
     462   
     463    void def(PureValue value)
     464    {
     465        // With pure values we do not have to worry about the possibility of some control flow path
     466        // clobbering the value. So, we just search for all of the like values that have been
     467        // computed. We pick one that is in a block that dominates ours. Note that this means that
     468        // a PureValue will map to a list of nodes, since there may be many places in the control
     469        // flow graph that compute a value but only one of them that dominates us. we may build up
     470        // a large list of nodes that compute some value in the case of gnarly control flow. This
     471        // is probably OK.
     472       
     473        auto result = m_pureValues.add(value, Vector<Node*>());
     474        if (result.isNewEntry) {
     475            result.iterator->value.append(m_node);
     476            return;
     477        }
     478       
     479        for (unsigned i = result.iterator->value.size(); i--;) {
     480            Node* candidate = result.iterator->value[i];
     481            if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
     482                m_node->replaceWith(candidate);
     483                m_changed = true;
     484                return;
     485            }
     486        }
     487       
     488        result.iterator->value.append(m_node);
     489    }
     490   
     491    Node* findReplacement(HeapLocation location)
     492    {
     493        // At this instant, our "availableAtTail" reflects the set of things that are available in
     494        // this block so far. We check this map to find block-local CSE opportunities before doing
     495        // a global search.
     496        Node* match = m_impureData->availableAtTail.get(location);
     497        if (match) {
     498            if (verbose)
     499                dataLog("      Found local match: ", match, "\n");
     500            return match;
     501        }
     502       
     503        // If it's not available at this point in the block, and at some prior point in the block
     504        // we have clobbered this heap location, then there is no point in doing a global search.
     505        if (m_writesSoFar.overlaps(location.heap())) {
     506            if (verbose)
     507                dataLog("      Not looking globally because of local clobber: ", m_writesSoFar, "\n");
     508            return nullptr;
     509        }
     510       
     511        // This perfoms a backward search over the control flow graph to find some possible
     512        // non-local def() that matches our heap location. Such a match is only valid if there does
     513        // not exist any path from that def() to our block that contains a write() that overlaps
     514        // our heap. This algorithm looks for both of these things (the matching def and the
     515        // overlapping writes) in one backwards DFS pass.
     516        //
     517        // This starts by looking at the starting block's predecessors, and then it continues along
     518        // their predecessors. As soon as this finds a possible def() - one that defines the heap
     519        // location we want while dominating our starting block - it assumes that this one must be
     520        // the match. It then lets the DFS over predecessors complete, but it doesn't add the
     521        // def()'s predecessors; this ensures that any blocks we visit thereafter are on some path
     522        // from the def() to us. As soon as the DFG finds a write() that overlaps the location's
     523        // heap, it stops, assuming that there is no possible match. Note that the write() case may
     524        // trigger before we find a def(), or after. Either way, the write() case causes this
     525        // function to immediately return nullptr.
     526        //
     527        // If the write() is found before we find the def(), then we know that any def() we would
     528        // find would have a path to us that trips over the write() and hence becomes invalid. This
     529        // is just a direct outcome of us looking for a def() that dominates us. Given a block A
     530        // that dominates block B - so that A is the one that would have the def() and B is our
     531        // starting block - we know that any other block must either be on the path from A to B, or
     532        // it must be on a path from the root to A, but not both. So, if we haven't found A yet but
     533        // we already have found a block C that has a write(), then C must be on some path from A
     534        // to B, which means that A's def() is invalid for our purposes. Hence, before we find the
     535        // def(), stopping on write() is the right thing to do.
     536        //
     537        // Stopping on write() is also the right thing to do after we find the def(). After we find
     538        // the def(), we don't add that block's predecessors to the search worklist. That means
     539        // that henceforth the only blocks we will see in the search are blocks on the path from
     540        // the def() to us. If any such block has a write() that clobbers our heap then we should
     541        // give up.
     542        //
     543        // Hence this graph search algorithm ends up being deceptively simple: any overlapping
     544        // write() causes us to immediately return nullptr, and a matching def() means that we just
     545        // record it and neglect to visit its precessors.
     546       
     547        Vector<BasicBlock*, 8> worklist;
     548        Vector<BasicBlock*, 8> seenList;
     549        BitVector seen;
     550       
     551        for (unsigned i = m_block->predecessors.size(); i--;) {
     552            BasicBlock* predecessor = m_block->predecessors[i];
     553            if (!seen.get(predecessor->index)) {
     554                worklist.append(predecessor);
     555                seen.set(predecessor->index);
     556            }
     557        }
     558       
     559        while (!worklist.isEmpty()) {
     560            BasicBlock* block = worklist.takeLast();
     561            seenList.append(block);
     562           
     563            if (verbose)
     564                dataLog("      Searching in block ", *block, "\n");
     565            ImpureBlockData& data = m_impureDataMap[block->index];
     566           
     567            // We require strict domination because this would only see things in our own block if
     568            // they came *after* our position in the block. Clearly, while our block dominates
     569            // itself, the things in the block after us don't dominate us.
     570            if (m_graph.m_dominators.dominates(block, m_block) && block != m_block) {
     571                if (verbose)
     572                    dataLog("        It strictly dominates.\n");
     573                DFG_ASSERT(m_graph, m_node, data.didVisit);
     574                DFG_ASSERT(m_graph, m_node, !match);
     575                if (verbose)
     576                    dataLog("        Availability map: ", mapDump(data.availableAtTail), "\n");
     577                match = data.availableAtTail.get(location);
     578                if (verbose)
     579                    dataLog("        Availability: ", match, "\n");
     580                if (match) {
     581                    // Don't examine the predecessors of a match. At this point we just want to
     582                    // establish that other blocks on the path from here to there don't clobber
     583                    // the location we're interested in.
     584                    continue;
    79585                }
    80586            }
    81         }
    82        
    83         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
    84             BasicBlock* block = m_graph.block(blockIndex);
    85             if (!block)
    86                 continue;
    87            
    88             for (unsigned i = block->size(); i--;) {
    89                 Node* node = block->at(i);
    90                 if (!node->containsMovHint())
    91                     continue;
    92                
    93                 ASSERT(node->op() != ZombieHint);
    94                 node->child1()->mergeFlags(NodeRelevantToOSR);
    95             }
    96         }
    97        
    98         if (m_graph.m_form == SSA) {
    99             Vector<BasicBlock*> depthFirst;
    100             m_graph.getBlocksInDepthFirstOrder(depthFirst);
    101             for (unsigned i = 0; i < depthFirst.size(); ++i)
    102                 performBlockCSE(depthFirst[i]);
    103         } else {
    104             for (unsigned blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
    105                 performBlockCSE(m_graph.block(blockIndex));
    106         }
    107        
    108         return m_changed;
    109     }
    110    
    111 private:
    112    
    113     unsigned endIndexForPureCSE()
    114     {
    115         unsigned result = m_lastSeen[m_currentNode->op()];
    116         if (result == UINT_MAX)
    117             result = 0;
    118         else
    119             result++;
    120         ASSERT(result <= m_indexInBlock);
    121         return result;
    122     }
    123 
    124     Node* pureCSE(Node* node)
    125     {
    126         Edge child1 = node->child1().sanitized();
    127         Edge child2 = node->child2().sanitized();
    128         Edge child3 = node->child3().sanitized();
    129        
    130         for (unsigned i = endIndexForPureCSE(); i--;) {
    131             Node* otherNode = m_currentBlock->at(i);
    132             if (otherNode == child1 || otherNode == child2 || otherNode == child3)
    133                 break;
    134 
    135             if (node->op() != otherNode->op())
    136                 continue;
    137            
    138             Edge otherChild = otherNode->child1().sanitized();
    139             if (!otherChild)
    140                 return otherNode;
    141             if (otherChild != child1)
    142                 continue;
    143            
    144             otherChild = otherNode->child2().sanitized();
    145             if (!otherChild)
    146                 return otherNode;
    147             if (otherChild != child2)
    148                 continue;
    149            
    150             otherChild = otherNode->child3().sanitized();
    151             if (!otherChild)
    152                 return otherNode;
    153             if (otherChild != child3)
    154                 continue;
    155            
    156             return otherNode;
    157         }
    158         return 0;
    159     }
    160    
    161     Node* constantCSE(Node* node)
    162     {
    163         for (unsigned i = endIndexForPureCSE(); i--;) {
    164             Node* otherNode = m_currentBlock->at(i);
    165             if (otherNode->op() != node->op())
    166                 continue;
    167            
    168             if (otherNode->constant() != node->constant())
    169                 continue;
    170            
    171             return otherNode;
    172         }
    173         return 0;
    174     }
    175    
    176     Node* constantStoragePointerCSE(Node* node)
    177     {
    178         for (unsigned i = endIndexForPureCSE(); i--;) {
    179             Node* otherNode = m_currentBlock->at(i);
    180             if (otherNode->op() != ConstantStoragePointer)
    181                 continue;
    182            
    183             if (otherNode->storagePointer() != node->storagePointer())
    184                 continue;
    185            
    186             return otherNode;
    187         }
    188         return 0;
    189     }
    190    
    191     Node* getCalleeLoadElimination()
    192     {
    193         for (unsigned i = m_indexInBlock; i--;) {
    194             Node* node = m_currentBlock->at(i);
    195             switch (node->op()) {
    196             case GetCallee:
    197                 return node;
    198             default:
    199                 break;
    200             }
    201         }
    202         return 0;
    203     }
    204    
    205     Node* getArrayLengthElimination(Node* array)
    206     {
    207         for (unsigned i = m_indexInBlock; i--;) {
    208             Node* node = m_currentBlock->at(i);
    209             switch (node->op()) {
    210             case GetArrayLength:
    211                 if (node->child1() == array)
    212                     return node;
    213                 break;
    214                
    215             case PutByValDirect:
    216             case PutByVal:
    217                 if (!m_graph.byValIsPure(node))
    218                     return 0;
    219                 if (node->arrayMode().mayStoreToHole())
    220                     return 0;
    221                 break;
    222                
    223             default:
    224                 if (m_graph.clobbersWorld(node))
    225                     return 0;
    226             }
    227         }
    228         return 0;
    229     }
    230    
    231     Node* globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)
    232     {
    233         for (unsigned i = m_indexInBlock; i--;) {
    234             Node* node = m_currentBlock->at(i);
    235             switch (node->op()) {
    236             case GetGlobalVar:
    237                 if (node->registerPointer() == registerPointer)
    238                     return node;
    239                 break;
    240             case PutGlobalVar:
    241                 if (node->registerPointer() == registerPointer)
    242                     return node->child1().node();
    243                 break;
    244             default:
    245                 break;
    246             }
    247             if (m_graph.clobbersWorld(node))
    248                 break;
    249         }
    250         return 0;
    251     }
    252    
    253     Node* scopedVarLoadElimination(Node* registers, int varNumber)
    254     {
    255         for (unsigned i = m_indexInBlock; i--;) {
    256             Node* node = m_currentBlock->at(i);
    257             switch (node->op()) {
    258             case GetClosureVar: {
    259                 if (node->child1() == registers && node->varNumber() == varNumber)
    260                     return node;
    261                 break;
    262             }
    263             case PutClosureVar: {
    264                 if (node->varNumber() != varNumber)
    265                     break;
    266                 if (node->child2() == registers)
    267                     return node->child3().node();
    268                 return 0;
    269             }
    270             case SetLocal: {
    271                 VariableAccessData* variableAccessData = node->variableAccessData();
    272                 if (variableAccessData->isCaptured()
    273                     && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
    274                     return 0;
    275                 break;
    276             }
    277             default:
    278                 break;
    279             }
    280             if (m_graph.clobbersWorld(node))
    281                 break;
    282         }
    283         return 0;
    284     }
    285    
    286     bool varInjectionWatchpointElimination()
    287     {
    288         for (unsigned i = m_indexInBlock; i--;) {
    289             Node* node = m_currentBlock->at(i);
    290             if (node->op() == VarInjectionWatchpoint)
    291                 return true;
    292             if (m_graph.clobbersWorld(node))
    293                 break;
    294         }
    295         return false;
    296     }
    297    
    298     Node* getByValLoadElimination(Node* child1, Node* child2, ArrayMode arrayMode)
    299     {
    300         for (unsigned i = m_indexInBlock; i--;) {
    301             Node* node = m_currentBlock->at(i);
    302             if (node == child1 || node == child2)
    303                 break;
    304 
    305             switch (node->op()) {
    306             case GetByVal:
    307                 if (!m_graph.byValIsPure(node))
    308                     return 0;
    309                 if (node->child1() == child1
    310                     && node->child2() == child2
    311                     && node->arrayMode().type() == arrayMode.type())
    312                     return node;
    313                 break;
    314                    
    315             case PutByValDirect:
    316             case PutByVal:
    317             case PutByValAlias: {
    318                 if (!m_graph.byValIsPure(node))
    319                     return 0;
    320                 // Typed arrays
    321                 if (arrayMode.typedArrayType() != NotTypedArray)
    322                     return 0;
    323                 if (m_graph.varArgChild(node, 0) == child1
    324                     && m_graph.varArgChild(node, 1) == child2
    325                     && node->arrayMode().type() == arrayMode.type())
    326                     return m_graph.varArgChild(node, 2).node();
    327                 // We must assume that the PutByVal will clobber the location we're getting from.
    328                 // FIXME: We can do better; if we know that the PutByVal is accessing an array of a
    329                 // different type than the GetByVal, then we know that they won't clobber each other.
    330                 // ... except of course for typed arrays, where all typed arrays clobber all other
    331                 // typed arrays!  An Int32Array can alias a Float64Array for example, and so on.
    332                 return 0;
    333             }
    334             default:
    335                 if (m_graph.clobbersWorld(node))
    336                     return 0;
    337                 break;
    338             }
    339         }
    340         return 0;
    341     }
    342 
    343     bool checkFunctionElimination(FrozenValue* function, Node* child1)
    344     {
    345         for (unsigned i = endIndexForPureCSE(); i--;) {
    346             Node* node = m_currentBlock->at(i);
    347             if (node == child1)
    348                 break;
    349 
    350             if (node->op() == CheckFunction && node->child1() == child1 && node->function() == function)
    351                 return true;
    352         }
    353         return false;
    354     }
    355    
    356     bool checkExecutableElimination(ExecutableBase* executable, Node* child1)
    357     {
    358         for (unsigned i = endIndexForPureCSE(); i--;) {
    359             Node* node = m_currentBlock->at(i);
    360             if (node == child1)
    361                 break;
    362 
    363             if (node->op() == CheckExecutable && node->child1() == child1 && node->executable() == executable)
    364                 return true;
    365         }
    366         return false;
    367     }
    368 
    369     bool checkStructureElimination(const StructureSet& structureSet, Node* child1)
    370     {
    371         for (unsigned i = m_indexInBlock; i--;) {
    372             Node* node = m_currentBlock->at(i);
    373             if (node == child1)
    374                 break;
    375 
    376             switch (node->op()) {
    377             case CheckStructure:
    378                 if (node->child1() == child1
    379                     && structureSet.isSupersetOf(node->structureSet()))
    380                     return true;
    381                 break;
    382                
    383             case PutStructure:
    384                 if (node->child1() == child1
    385                     && structureSet.contains(node->transition()->next))
    386                     return true;
    387                 if (structureSet.contains(node->transition()->previous))
    388                     return false;
    389                 break;
    390                
    391             case PutByOffset:
    392                 // Setting a property cannot change the structure.
    393                 break;
    394                
    395             case MultiPutByOffset:
    396                 if (node->multiPutByOffsetData().writesStructures())
    397                     return false;
    398                 break;
    399                
    400             case PutByValDirect:
    401             case PutByVal:
    402             case PutByValAlias:
    403                 if (m_graph.byValIsPure(node)) {
    404                     // If PutByVal speculates that it's accessing an array with an
    405                     // integer index, then it's impossible for it to cause a structure
    406                     // change.
    407                     break;
     587           
     588            if (verbose)
     589                dataLog("        Dealing with write set ", data.writes, "\n");
     590            if (data.writes.overlaps(location.heap())) {
     591                if (verbose)
     592                    dataLog("        Clobbered.\n");
     593                return nullptr;
     594            }
     595           
     596            for (unsigned i = block->predecessors.size(); i--;) {
     597                BasicBlock* predecessor = block->predecessors[i];
     598                if (!seen.get(predecessor->index)) {
     599                    worklist.append(predecessor);
     600                    seen.set(predecessor->index);
    408601                }
    409                 return false;
    410                
    411             case Arrayify:
    412             case ArrayifyToStructure:
    413                 // We could check if the arrayification could affect our structures.
    414                 // But that seems like it would take Effort.
    415                 return false;
    416                
    417             default:
    418                 if (m_graph.clobbersWorld(node))
    419                     return false;
    420                 break;
    421             }
    422         }
    423         return false;
    424     }
    425    
    426     bool structureTransitionWatchpointElimination(Structure* structure, Node* child1)
    427     {
    428         for (unsigned i = m_indexInBlock; i--;) {
    429             Node* node = m_currentBlock->at(i);
    430             if (node == child1)
    431                 break;
    432 
    433             switch (node->op()) {
    434             case CheckStructure:
    435                 if (node->child1() == child1
    436                     && node->structureSet().isSubsetOf(StructureSet(structure)))
    437                     return true;
    438                 break;
    439                
    440             case PutStructure:
    441                 ASSERT(node->transition()->previous != structure);
    442                 break;
    443                
    444             case PutByOffset:
    445                 // Setting a property cannot change the structure.
    446                 break;
    447                    
    448             case MultiPutByOffset:
    449                 if (node->multiPutByOffsetData().writesStructures())
    450                     return false;
    451                 break;
    452                
    453             case PutByValDirect:
    454             case PutByVal:
    455             case PutByValAlias:
    456                 if (m_graph.byValIsPure(node)) {
    457                     // If PutByVal speculates that it's accessing an array with an
    458                     // integer index, then it's impossible for it to cause a structure
    459                     // change.
    460                     break;
    461                 }
    462                 return false;
    463                
    464             case Arrayify:
    465             case ArrayifyToStructure:
    466                 // We could check if the arrayification could affect our structures.
    467                 // But that seems like it would take Effort.
    468                 return false;
    469                
    470             default:
    471                 if (m_graph.clobbersWorld(node))
    472                     return false;
    473                 break;
    474             }
    475         }
    476         return false;
    477     }
    478    
    479     Node* getByOffsetLoadElimination(unsigned identifierNumber, Node* base)
    480     {
    481         for (unsigned i = m_indexInBlock; i--;) {
    482             Node* node = m_currentBlock->at(i);
    483             if (node == base)
    484                 break;
    485 
    486             switch (node->op()) {
    487             case GetByOffset:
    488                 if (node->child2() == base
    489                     && m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
    490                     return node;
    491                 break;
    492                
    493             case MultiGetByOffset:
    494                 if (node->child1() == base
    495                     && node->multiGetByOffsetData().identifierNumber == identifierNumber)
    496                     return node;
    497                 break;
    498                
    499             case PutByOffset:
    500                 if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {
    501                     if (node->child2() == base) // Must be same property storage.
    502                         return node->child3().node();
    503                     return 0;
    504                 }
    505                 break;
    506                
    507             case MultiPutByOffset:
    508                 if (node->multiPutByOffsetData().identifierNumber == identifierNumber) {
    509                     if (node->child1() == base)
    510                         return node->child2().node();
    511                     return 0;
    512                 }
    513                 break;
    514                    
    515             case PutByValDirect:
    516             case PutByVal:
    517             case PutByValAlias:
    518                 if (m_graph.byValIsPure(node)) {
    519                     // If PutByVal speculates that it's accessing an array with an
    520                     // integer index, then it's impossible for it to cause a structure
    521                     // change.
    522                     break;
    523                 }
    524                 return 0;
    525                
    526             default:
    527                 if (m_graph.clobbersWorld(node))
    528                     return 0;
    529                 break;
    530             }
    531         }
    532         return 0;
    533     }
    534    
    535     Node* getGetterSetterByOffsetLoadElimination(unsigned identifierNumber, Node* base)
    536     {
    537         for (unsigned i = m_indexInBlock; i--;) {
    538             Node* node = m_currentBlock->at(i);
    539             if (node == base)
    540                 break;
    541 
    542             switch (node->op()) {
    543             case GetGetterSetterByOffset:
    544                 if (node->child2() == base
    545                     && m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
    546                     return node;
    547                 break;
    548                    
    549             case PutByValDirect:
    550             case PutByVal:
    551             case PutByValAlias:
    552                 if (m_graph.byValIsPure(node)) {
    553                     // If PutByVal speculates that it's accessing an array with an
    554                     // integer index, then it's impossible for it to cause a structure
    555                     // change.
    556                     break;
    557                 }
    558                 return 0;
    559                
    560             default:
    561                 if (m_graph.clobbersWorld(node))
    562                     return 0;
    563                 break;
    564             }
    565         }
    566         return 0;
    567     }
    568    
    569     Node* getPropertyStorageLoadElimination(Node* child1)
    570     {
    571         for (unsigned i = m_indexInBlock; i--;) {
    572             Node* node = m_currentBlock->at(i);
    573             if (node == child1)
    574                 break;
    575 
    576             switch (node->op()) {
    577             case GetButterfly:
    578                 if (node->child1() == child1)
    579                     return node;
    580                 break;
    581 
    582             case AllocatePropertyStorage:
    583             case ReallocatePropertyStorage:
    584                 // If we can cheaply prove this is a change to our object's storage, we
    585                 // can optimize and use its result.
    586                 if (node->child1() == child1)
    587                     return node;
    588                 // Otherwise, we currently can't prove that this doesn't change our object's
    589                 // storage, so we conservatively assume that it may change the storage
    590                 // pointer of any object, including ours.
    591                 return 0;
    592                    
    593             case PutByValDirect:
    594             case PutByVal:
    595             case PutByValAlias:
    596                 if (m_graph.byValIsPure(node)) {
    597                     // If PutByVal speculates that it's accessing an array with an
    598                     // integer index, then it's impossible for it to cause a structure
    599                     // change.
    600                     break;
    601                 }
    602                 return 0;
    603                
    604             case Arrayify:
    605             case ArrayifyToStructure:
    606                 // We could check if the arrayification could affect our butterfly.
    607                 // But that seems like it would take Effort.
    608                 return 0;
    609                
    610             case MultiPutByOffset:
    611                 if (node->multiPutByOffsetData().reallocatesStorage())
    612                     return 0;
    613                 break;
    614                
    615             default:
    616                 if (m_graph.clobbersWorld(node))
    617                     return 0;
    618                 break;
    619             }
    620         }
    621         return 0;
    622     }
    623    
    624     bool checkArrayElimination(Node* child1, ArrayMode arrayMode)
    625     {
    626         for (unsigned i = m_indexInBlock; i--;) {
    627             Node* node = m_currentBlock->at(i);
    628             if (node == child1)
    629                 break;
    630 
    631             switch (node->op()) {
    632             case CheckArray:
    633                 if (node->child1() == child1 && node->arrayMode() == arrayMode)
    634                     return true;
    635                 break;
    636                
    637             case Arrayify:
    638             case ArrayifyToStructure:
    639                 // We could check if the arrayification could affect our array.
    640                 // But that seems like it would take Effort.
    641                 return false;
    642                
    643             default:
    644                 if (m_graph.clobbersWorld(node))
    645                     return false;
    646                 break;
    647             }
    648         }
    649         return false;
    650     }
    651 
    652     Node* getIndexedPropertyStorageLoadElimination(Node* child1, ArrayMode arrayMode)
    653     {
    654         for (unsigned i = m_indexInBlock; i--;) {
    655             Node* node = m_currentBlock->at(i);
    656             if (node == child1)
    657                 break;
    658 
    659             switch (node->op()) {
    660             case GetIndexedPropertyStorage: {
    661                 if (node->child1() == child1 && node->arrayMode() == arrayMode)
    662                     return node;
    663                 break;
    664             }
    665 
    666             default:
    667                 if (m_graph.clobbersWorld(node))
    668                     return 0;
    669                 break;
    670             }
    671         }
    672         return 0;
    673     }
    674    
    675     Node* getInternalFieldLoadElimination(NodeType op, Node* child1)
    676     {
    677         for (unsigned i = m_indexInBlock; i--;) {
    678             Node* node = m_currentBlock->at(i);
    679             if (node == child1)
    680                 break;
    681 
    682             if (node->op() == op && node->child1() == child1)
    683                 return node;
    684 
    685             if (m_graph.clobbersWorld(node))
    686                 return 0;
    687         }
    688         return 0;
    689     }
    690    
    691     Node* getMyScopeLoadElimination()
    692     {
    693         for (unsigned i = m_indexInBlock; i--;) {
    694             Node* node = m_currentBlock->at(i);
    695             switch (node->op()) {
    696             case CreateActivation:
    697                 // This may cause us to return a different scope.
    698                 return 0;
    699             case GetMyScope:
    700                 return node;
    701             default:
    702                 break;
    703             }
    704         }
    705         return 0;
    706     }
    707    
    708     Node* getLocalLoadElimination(VirtualRegister local, Node*& relevantLocalOp, bool careAboutClobbering)
    709     {
    710         relevantLocalOp = 0;
    711        
    712         for (unsigned i = m_indexInBlock; i--;) {
    713             Node* node = m_currentBlock->at(i);
    714             switch (node->op()) {
    715             case GetLocal:
    716                 if (node->local() == local) {
    717                     relevantLocalOp = node;
    718                     return node;
    719                 }
    720                 break;
    721                
    722             case GetLocalUnlinked:
    723                 if (node->unlinkedLocal() == local) {
    724                     relevantLocalOp = node;
    725                     return node;
    726                 }
    727                 break;
    728                
    729             case SetLocal:
    730                 if (node->local() == local) {
    731                     relevantLocalOp = node;
    732                     return node->child1().node();
    733                 }
    734                 break;
    735                
    736             case GetClosureVar:
    737             case PutClosureVar:
    738                 if (static_cast<VirtualRegister>(node->varNumber()) == local)
    739                     return 0;
    740                 break;
    741                
    742             default:
    743                 if (careAboutClobbering && m_graph.clobbersWorld(node))
    744                     return 0;
    745                 break;
    746             }
    747         }
    748         return 0;
    749     }
    750    
    751     Node* uncapturedSetLocalStoreElimination(VirtualRegister local)
    752     {
    753         for (unsigned i = m_indexInBlock; i--;) {
    754             Node* node = m_currentBlock->at(i);
    755             switch (node->op()) {
    756             case GetLocal:
    757             case Flush:
    758                 if (node->local() == local)
    759                     return nullptr;
    760                 break;
    761                
    762             case GetLocalUnlinked:
    763                 if (node->unlinkedLocal() == local)
    764                     return nullptr;
    765                 break;
    766                
    767             case SetLocal: {
    768                 if (node->local() != local)
    769                     break;
    770                 return node;
    771             }
    772                
    773             case GetClosureVar:
    774             case PutClosureVar:
    775                 if (static_cast<VirtualRegister>(node->varNumber()) == local)
    776                     return nullptr;
    777                 break;
    778                
    779             case GetMyScope:
    780             case SkipTopScope:
    781                 if (node->origin.semantic.inlineCallFrame)
    782                     break;
    783                 if (m_graph.uncheckedActivationRegister() == local)
    784                     return nullptr;
    785                 break;
    786                
    787             case CheckArgumentsNotCreated:
    788             case GetMyArgumentsLength:
    789             case GetMyArgumentsLengthSafe:
    790                 if (m_graph.uncheckedArgumentsRegisterFor(node->origin.semantic) == local)
    791                     return nullptr;
    792                 break;
    793                
    794             case GetMyArgumentByVal:
    795             case GetMyArgumentByValSafe:
    796                 return nullptr;
    797                
    798             case GetByVal:
    799                 // If this is accessing arguments then it's potentially accessing locals.
    800                 if (node->arrayMode().type() == Array::Arguments)
    801                     return nullptr;
    802                 break;
    803                
    804             case CreateArguments:
    805             case TearOffActivation:
    806             case TearOffArguments:
    807                 // If an activation is being torn off then it means that captured variables
    808                 // are live. We could be clever here and check if the local qualifies as an
    809                 // argument register. But that seems like it would buy us very little since
    810                 // any kind of tear offs are rare to begin with.
    811                 return nullptr;
    812                
    813             default:
    814                 break;
    815             }
    816             if (m_graph.clobbersWorld(node))
    817                 return nullptr;
    818         }
    819         return nullptr;
    820     }
    821 
    822     Node* capturedSetLocalStoreElimination(VirtualRegister local)
    823     {
    824         for (unsigned i = m_indexInBlock; i--;) {
    825             Node* node = m_currentBlock->at(i);
    826             switch (node->op()) {
    827             case GetLocal:
    828             case Flush:
    829                 if (node->local() == local)
    830                     return nullptr;
    831                 break;
    832                
    833             case GetLocalUnlinked:
    834                 if (node->unlinkedLocal() == local)
    835                     return nullptr;
    836                 break;
    837                
    838             case SetLocal: {
    839                 if (node->local() != local)
    840                     break;
    841                 return node;
    842             }
    843                
    844             case Phantom:
    845             case Check:
    846             case HardPhantom:
    847             case MovHint:
    848             case JSConstant:
    849             case DoubleConstant:
    850             case Int52Constant:
    851                 break;
    852                
    853             default:
    854                 return nullptr;
    855             }
    856         }
    857         return nullptr;
    858     }
    859    
    860     Node* setLocalStoreElimination(VariableAccessData* variableAccessData)
    861     {
    862         if (variableAccessData->isCaptured())
    863             return capturedSetLocalStoreElimination(variableAccessData->local());
    864         return uncapturedSetLocalStoreElimination(variableAccessData->local());
    865     }
    866    
    867     bool invalidationPointElimination()
    868     {
    869         for (unsigned i = m_indexInBlock; i--;) {
    870             Node* node = m_currentBlock->at(i);
    871             if (node->op() == InvalidationPoint)
    872                 return true;
    873             if (writesOverlap(m_graph, node, Watchpoint_fire))
    874                 break;
    875         }
    876         return false;
    877     }
    878    
    879     void eliminateIrrelevantPhantomChildren(Node* node)
    880     {
    881         ASSERT(node->op() == Phantom);
    882         for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
    883             Edge edge = node->children.child(i);
    884             if (!edge)
    885                 continue;
    886             if (edge.useKind() != UntypedUse)
    887                 continue; // Keep the type check.
    888             if (edge->flags() & NodeRelevantToOSR)
    889                 continue;
    890            
    891             node->children.removeEdge(i--);
    892             m_changed = true;
    893         }
    894     }
    895    
    896     bool setReplacement(Node* replacement)
    897     {
    898         if (!replacement)
    899             return false;
    900        
    901         if (!ASSERT_DISABLED
    902             && canonicalResultRepresentation(m_currentNode->result()) != canonicalResultRepresentation(replacement->result())) {
    903             startCrashing();
    904             dataLog("CSE attempting to replace a node with a mismatched result: ", m_currentNode, " with ", replacement, "\n");
    905             dataLog("\n");
    906             m_graph.dump();
    907             RELEASE_ASSERT_NOT_REACHED();
    908         }
    909        
    910         m_currentNode->convertToPhantom();
    911         eliminateIrrelevantPhantomChildren(m_currentNode);
    912        
    913         // At this point we will eliminate all references to this node.
    914         m_currentNode->misc.replacement = replacement;
    915        
     602            }
     603        }
     604       
     605        if (!match)
     606            return nullptr;
     607       
     608        // Cache the results for next time. We cache them both for this block and for all of our
     609        // predecessors, since even though we've already visited our predecessors, our predecessors
     610        // probably have successors other than us.
     611        // FIXME: Consider caching failed searches as well, when match is null. It's not clear that
     612        // the reduction in compile time would warrant the increase in complexity, though.
     613        // https://bugs.webkit.org/show_bug.cgi?id=134876
     614        for (BasicBlock* block : seenList)
     615            m_impureDataMap[block->index].availableAtTail.add(location, match);
     616        m_impureData->availableAtTail.add(location, match);
     617       
     618        return match;
     619    }
     620   
     621    void def(HeapLocation location, Node* value)
     622    {
     623        if (verbose)
     624            dataLog("    Got heap location def: ", location, " -> ", value, "\n");
     625       
     626        Node* match = findReplacement(location);
     627       
     628        if (verbose)
     629            dataLog("      Got match: ", match, "\n");
     630       
     631        if (!match) {
     632            if (verbose)
     633                dataLog("      Adding at-tail mapping: ", location, " -> ", value, "\n");
     634            auto result = m_impureData->availableAtTail.add(location, value);
     635            ASSERT_UNUSED(result, result.isNewEntry);
     636            return;
     637        }
     638       
     639        m_node->replaceWith(match);
    916640        m_changed = true;
    917        
    918         return true;
    919     }
    920    
    921     void eliminate()
    922     {
    923         ASSERT(m_currentNode->mustGenerate());
    924         m_currentNode->convertToPhantom();
    925         eliminateIrrelevantPhantomChildren(m_currentNode);
    926        
    927         m_changed = true;
    928     }
    929    
    930     void eliminate(Node* node, NodeType phantomType = Phantom)
    931     {
    932         if (!node)
    933             return;
    934         ASSERT(node->mustGenerate());
    935         node->setOpAndDefaultFlags(phantomType);
    936         if (phantomType == Phantom)
    937             eliminateIrrelevantPhantomChildren(node);
    938        
    939         m_changed = true;
    940     }
    941    
    942     void performNodeCSE(Node* node)
    943     {
    944         m_graph.performSubstitution(node);
    945        
    946         switch (node->op()) {
    947        
    948         case Identity:
    949             setReplacement(node->child1().node());
    950             break;
    951            
    952         // Handle the pure nodes. These nodes never have any side-effects.
    953         case BitAnd:
    954         case BitOr:
    955         case BitXor:
    956         case BitRShift:
    957         case BitLShift:
    958         case BitURShift:
    959         case ArithAbs:
    960         case ArithMin:
    961         case ArithMax:
    962         case ArithSqrt:
    963         case ArithFRound:
    964         case ArithSin:
    965         case ArithCos:
    966         case StringCharAt:
    967         case StringCharCodeAt:
    968         case IsUndefined:
    969         case IsBoolean:
    970         case IsNumber:
    971         case IsString:
    972         case IsObject:
    973         case IsFunction:
    974         case LogicalNot:
    975         case SkipTopScope:
    976         case SkipScope:
    977         case GetClosureRegisters:
    978         case GetScope:
    979         case TypeOf:
    980         case CompareEqConstant:
    981         case ValueToInt32:
    982         case MakeRope:
    983         case DoubleRep:
    984         case ValueRep:
    985         case Int52Rep:
    986         case BooleanToNumber:
    987             setReplacement(pureCSE(node));
    988             break;
    989            
    990         case ArithAdd:
    991         case ArithSub:
    992         case ArithNegate:
    993         case ArithMul:
    994         case ArithDiv:
    995         case ArithMod:
    996         case UInt32ToNumber:
    997         case DoubleAsInt32: {
    998             Node* candidate = pureCSE(node);
    999             if (!candidate)
    1000                 break;
    1001             if (!subsumes(candidate->arithMode(), node->arithMode())) {
    1002                 if (!subsumes(node->arithMode(), candidate->arithMode()))
    1003                     break;
    1004                 candidate->setArithMode(node->arithMode());
    1005             }
    1006             setReplacement(candidate);
    1007             break;
    1008         }
    1009            
    1010         case GetCallee:
    1011             setReplacement(getCalleeLoadElimination());
    1012             break;
    1013 
    1014         case GetLocal: {
    1015             VariableAccessData* variableAccessData = node->variableAccessData();
    1016             if (!variableAccessData->isCaptured())
    1017                 break;
    1018             Node* relevantLocalOp;
    1019             Node* possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp, variableAccessData->isCaptured());
    1020             if (!relevantLocalOp)
    1021                 break;
    1022             if (relevantLocalOp->op() != GetLocalUnlinked
    1023                 && relevantLocalOp->variableAccessData() != variableAccessData)
    1024                 break;
    1025             Node* phi = node->child1().node();
    1026             if (!setReplacement(possibleReplacement))
    1027                 break;
    1028            
    1029             m_graph.dethread();
    1030            
    1031             // If we replace a GetLocal with a GetLocalUnlinked, then turn the GetLocalUnlinked
    1032             // into a GetLocal.
    1033             if (relevantLocalOp->op() == GetLocalUnlinked)
    1034                 relevantLocalOp->convertToGetLocal(variableAccessData, phi);
    1035 
    1036             m_changed = true;
    1037             break;
    1038         }
    1039            
    1040         case GetLocalUnlinked: {
    1041             Node* relevantLocalOpIgnored;
    1042             setReplacement(getLocalLoadElimination(node->unlinkedLocal(), relevantLocalOpIgnored, true));
    1043             break;
    1044         }
    1045            
    1046         case JSConstant:
    1047         case DoubleConstant:
    1048         case Int52Constant:
    1049             // This is strange, but necessary. Some phases will convert nodes to constants,
    1050             // which may result in duplicated constants. We use CSE to clean this up.
    1051             setReplacement(constantCSE(node));
    1052             break;
    1053            
    1054         case ConstantStoragePointer:
    1055             setReplacement(constantStoragePointerCSE(node));
    1056             break;
    1057            
    1058         case GetArrayLength:
    1059             setReplacement(getArrayLengthElimination(node->child1().node()));
    1060             break;
    1061 
    1062         case GetMyScope:
    1063             setReplacement(getMyScopeLoadElimination());
    1064             break;
    1065            
    1066         // Handle nodes that are conditionally pure: these are pure, and can
    1067         // be CSE'd, so long as the prediction is the one we want.
    1068         case CompareLess:
    1069         case CompareLessEq:
    1070         case CompareGreater:
    1071         case CompareGreaterEq:
    1072         case CompareEq: {
    1073             if (m_graph.isPredictedNumerical(node)) {
    1074                 Node* replacement = pureCSE(node);
    1075                 if (replacement && m_graph.isPredictedNumerical(replacement))
    1076                     setReplacement(replacement);
    1077             }
    1078             break;
    1079         }
    1080            
    1081         // Finally handle heap accesses. These are not quite pure, but we can still
    1082         // optimize them provided that some subtle conditions are met.
    1083         case GetGlobalVar:
    1084             setReplacement(globalVarLoadElimination(node->registerPointer()));
    1085             break;
    1086 
    1087         case GetClosureVar: {
    1088             setReplacement(scopedVarLoadElimination(node->child1().node(), node->varNumber()));
    1089             break;
    1090         }
    1091 
    1092         case VarInjectionWatchpoint:
    1093             if (varInjectionWatchpointElimination())
    1094                 eliminate();
    1095             break;
    1096            
    1097         case GetByVal:
    1098             if (m_graph.byValIsPure(node))
    1099                 setReplacement(getByValLoadElimination(node->child1().node(), node->child2().node(), node->arrayMode()));
    1100             break;
    1101                
    1102         case PutByValDirect:
    1103         case PutByVal: {
    1104             Edge child1 = m_graph.varArgChild(node, 0);
    1105             Edge child2 = m_graph.varArgChild(node, 1);
    1106             if (node->arrayMode().canCSEStorage()) {
    1107                 Node* replacement = getByValLoadElimination(child1.node(), child2.node(), node->arrayMode());
    1108                 if (!replacement)
    1109                     break;
    1110                 node->setOp(PutByValAlias);
    1111             }
    1112             break;
    1113         }
    1114            
    1115         case CheckStructure:
    1116             if (checkStructureElimination(node->structureSet(), node->child1().node()))
    1117                 eliminate();
    1118             break;
    1119            
    1120         case CheckFunction:
    1121             if (checkFunctionElimination(node->function(), node->child1().node()))
    1122                 eliminate();
    1123             break;
    1124                
    1125         case CheckExecutable:
    1126             if (checkExecutableElimination(node->executable(), node->child1().node()))
    1127                 eliminate();
    1128             break;
    1129                
    1130         case CheckArray:
    1131             if (checkArrayElimination(node->child1().node(), node->arrayMode()))
    1132                 eliminate();
    1133             break;
    1134            
    1135         case GetIndexedPropertyStorage: {
    1136             setReplacement(getIndexedPropertyStorageLoadElimination(node->child1().node(), node->arrayMode()));
    1137             break;
    1138         }
    1139            
    1140         case GetTypedArrayByteOffset:
    1141         case GetGetter:
    1142         case GetSetter: {
    1143             setReplacement(getInternalFieldLoadElimination(node->op(), node->child1().node()));
    1144             break;
    1145         }
    1146 
    1147         case GetButterfly:
    1148             setReplacement(getPropertyStorageLoadElimination(node->child1().node()));
    1149             break;
    1150 
    1151         case GetByOffset:
    1152             setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child2().node()));
    1153             break;
    1154            
    1155         case GetGetterSetterByOffset:
    1156             setReplacement(getGetterSetterByOffsetLoadElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child2().node()));
    1157             break;
    1158            
    1159         case MultiGetByOffset:
    1160             setReplacement(getByOffsetLoadElimination(node->multiGetByOffsetData().identifierNumber, node->child1().node()));
    1161             break;
    1162            
    1163         case InvalidationPoint:
    1164             if (invalidationPointElimination())
    1165                 eliminate();
    1166             break;
    1167            
    1168         case Phantom:
    1169             // FIXME: we ought to remove Phantom's that have no children.
    1170             // NB. It would be incorrect to do this for HardPhantom. In fact, the whole point
    1171             // of HardPhantom is that we *don't* do this for HardPhantoms, since they signify
    1172             // a more strict kind of liveness than the Phantom bytecode liveness.
    1173             eliminateIrrelevantPhantomChildren(node);
    1174             break;
    1175            
    1176         case Flush:
    1177             // This is needed for arguments simplification to work. We need to eliminate the
    1178             // redundancy between op_enter's undefined-all-the-things and the subsequent
    1179             // op_init_lazy_reg.
    1180            
    1181             ASSERT(m_graph.m_form != SSA);
    1182            
    1183             if (Node* setLocal = setLocalStoreElimination(node->variableAccessData())) {
    1184                 node->convertToPhantom();
    1185                 Node* dataNode = setLocal->child1().node();
    1186                 ASSERT(dataNode->hasResult());
    1187                 node->child1() = dataNode->defaultEdge();
    1188                 m_graph.dethread();
    1189                 m_changed = true;
    1190             }
    1191             break;
    1192            
    1193         default:
    1194             // do nothing.
    1195             break;
    1196         }
    1197        
    1198         m_lastSeen[node->op()] = m_indexInBlock;
    1199     }
    1200    
    1201     void performBlockCSE(BasicBlock* block)
    1202     {
    1203         if (!block)
    1204             return;
    1205         if (!block->isReachable)
    1206             return;
    1207        
    1208         m_currentBlock = block;
    1209         for (unsigned i = 0; i < LastNodeType; ++i)
    1210             m_lastSeen[i] = UINT_MAX;
    1211        
    1212         for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
    1213             m_currentNode = block->at(m_indexInBlock);
    1214             performNodeCSE(m_currentNode);
    1215         }
    1216     }
    1217    
    1218     BasicBlock* m_currentBlock;
    1219     Node* m_currentNode;
    1220     unsigned m_indexInBlock;
    1221     std::array<unsigned, LastNodeType> m_lastSeen;
    1222     bool m_changed; // Only tracks changes that have a substantive effect on other optimizations.
     641    }
     642   
     643    struct ImpureBlockData {
     644        ImpureBlockData()
     645            : didVisit(false)
     646        {
     647        }
     648       
     649        ClobberSet writes;
     650        ImpureMap availableAtTail;
     651        bool didVisit;
     652    };
     653   
     654    Vector<BasicBlock*> m_preOrder;
     655
     656    PureMultiMap m_pureValues;
     657    Vector<ImpureBlockData> m_impureDataMap;
     658   
     659    BasicBlock* m_block;
     660    Node* m_node;
     661    ImpureBlockData* m_impureData;
     662    ClobberSet m_writesSoFar;
     663   
     664    bool m_changed;
    1223665};
    1224666
    1225 bool performCSE(Graph& graph)
     667} // anonymous namespace
     668
     669bool performLocalCSE(Graph& graph)
    1226670{
    1227     SamplingRegion samplingRegion("DFG CSE Phase");
    1228     return runPhase<CSEPhase>(graph);
     671    SamplingRegion samplingRegion("DFG LocalCSE Phase");
     672    return runPhase<LocalCSEPhase>(graph);
    1229673}
    1230674
     675bool performGlobalCSE(Graph& graph)
     676{
     677    SamplingRegion samplingRegion("DFG GlobalCSE Phase");
     678    return runPhase<GlobalCSEPhase>(graph);
     679}
     680
    1231681} } // namespace JSC::DFG
    1232682
    1233683#endif // ENABLE(DFG_JIT)
    1234 
    1235 
Note: See TracChangeset for help on using the changeset viewer.