https://bugs.webkit.org/show_bug.cgi?id=126185

Reviewed by Ryosuke Niwa.

Source/WebCore: 

Compile selectors on demand and use the generated binary to perform
element matching in SelectorQuery.

Tests: fast/selectors/querySelector-long-adjacent-backtracking.html
       fast/selectors/querySelector-long-child-backtracking.html
       fast/selectors/querySelector-mixed-child-adjacent-backtracking.html
       fast/selectors/querySelector-multiple-simple-child-backtracking.html
       fast/selectors/querySelector-simple-adjacent-backtracking.html
       fast/selectors/querySelector-simple-child-backtracking.html

* dom/SelectorQuery.cpp:
(WebCore::SelectorDataList::executeCompiledSimpleSelectorChecker):
(WebCore::SelectorDataList::executeCompiledSelectorCheckerWithContext):
(WebCore::SelectorDataList::execute):
* dom/SelectorQuery.h:

LayoutTests: 

Add some tests for longer backtracking cases typically not covered by the other tests.

* fast/selectors/querySelector-long-adjacent-backtracking-expected.txt: Added.
* fast/selectors/querySelector-long-adjacent-backtracking.html: Added.
* fast/selectors/querySelector-long-child-backtracking-expected.txt: Added.
* fast/selectors/querySelector-long-child-backtracking.html: Added.
* fast/selectors/querySelector-mixed-child-adjacent-backtracking-expected.txt: Added.
* fast/selectors/querySelector-mixed-child-adjacent-backtracking.html: Added.
* fast/selectors/querySelector-multiple-simple-child-backtracking-expected.txt: Added.
* fast/selectors/querySelector-multiple-simple-child-backtracking.html: Added.
* fast/selectors/querySelector-simple-adjacent-backtracking-expected.txt: Added.
* fast/selectors/querySelector-simple-adjacent-backtracking.html: Added.
* fast/selectors/querySelector-simple-child-backtracking-expected.txt: Added.
* fast/selectors/querySelector-simple-child-backtracking.html: Added.


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@161839 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=126196

Reviewed by Ryosuke Niwa.

* cssjit/SelectorCompiler.cpp:
(WebCore::SelectorCompiler::addPseudoType):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementIsLink):
* dom/Node.h:
(WebCore::Node::flagIsElement):
(WebCore::Node::flagIsLink):
Fix the type to match TrustedImm32.


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@161046 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=126189

Reviewed by Ryosuke Niwa.

* cssjit/SelectorCompiler.cpp:
(WebCore::SelectorCompiler::addPseudoType):
(WebCore::SelectorCompiler::SelectorCodeGenerator::SelectorCodeGenerator):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementIsFocused):


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@161041 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=126176

Source/JavaScriptCore: 

Reviewed by Antti Koivisto and Oliver Hunt.

Add test and branch based on BaseIndex addressing for x86_64.
Fast loops are needed to compete with clang on tight loops.

* assembler/MacroAssembler.h:
* assembler/MacroAssemblerX86_64.h:
(JSC::MacroAssemblerX86_64::branch64):
(JSC::MacroAssemblerX86_64::branchPtr):
* assembler/X86Assembler.h:
(JSC::X86Assembler::cmpq_rm):

Source/WebCore: 

Reviewed by Antti Koivisto.

Add selector matching based on classname to the Selector Compiler.

* cssjit/SelectorCompiler.cpp:
(WebCore::SelectorCompiler::SelectorCodeGenerator::SelectorCodeGenerator):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementDataMatching):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementHasClasses):
* dom/ElementData.h:
(WebCore::ElementData::classNamesMemoryOffset):
* dom/SpaceSplitString.h:
(WebCore::SpaceSplitStringData::sizeMemoryOffset):
(WebCore::SpaceSplitStringData::tokensMemoryOffset):


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@161031 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=126154

Reviewed by Antti Koivisto.

Compile matching for #id selectors. IDs are Atomic String so it is just a matter
of comparing the pointers.

No attempt is made at optimizing for the double #id case because such problem
do not really happen outside tests.

* cssjit/SelectorCompiler.cpp:
(WebCore::SelectorCompiler::SelectorFragment::SelectorFragment):
(WebCore::SelectorCompiler::SelectorCodeGenerator::SelectorCodeGenerator):
(WebCore::SelectorCompiler::SelectorCodeGenerator::compile):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementDataMatching):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementHasId):
* dom/Element.h:
(WebCore::Element::elementDataMemoryOffset):
* dom/ElementData.h:
(WebCore::ElementData::idForStyleResolutionMemoryOffset):


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@161010 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=126044

Source/JavaScriptCore: 

Reviewed by Antti Koivisto and Gavin Barraclough.

* assembler/LinkBuffer.h:
Add a new owner UID for code compiled for CSS.
Export the symbols needed to link code from WebCore.

Source/WebCore: 

Patch by Benjamin Poulain <bpoulain@apple.com> on 2013-12-22
Reviewed by Antti Koivisto and Gavin Barraclough.

Add CSSCompiler, which provides the basic infrastructure to compile
CSS Selectors on x86_64.

Compilation happens in two phases.
1) The various matching and relation of each CSSSelector is aggregated into units
   matching a single element: SelectorFragment.
   SelectorFragment also knows about the relations between different fragments,
   and contains all the information to generate the code for a particular element.
2) The compiler then goes over the fragments, and generate code based on the information
   of each fragment.

It the current state, SelectorCompiler only compiles the tag matching selectors and
any of the relation between selectors.

Depending on the relation and position of a fragment, failure on traversal or matching
does not necessarily causes the complete selector. A failure can cause matching to
resume from the parent or the sibling of a previously visisted node.
The implementation of this is done through the BacktrackingAction. In case of failure,
the next starting state is setup and the program counter jumps back to the appropriate
starting point.

When backtracking, the method used to save the starting point depends on the type
of backtracking.
The child/parent relation (">") is very common so it uses an additional register to keep
the next starting point (m_descendantBacktrackingStart).
The indirect sibling relation ("~") is much less common and uses the stack to save
the next starting point.

* WebCore.xcodeproj/project.pbxproj:
* cssjit/SelectorCompiler.cpp: Added.
(WebCore::SelectorCompiler::SelectorFragment::SelectorFragment):
(WebCore::SelectorCompiler::compileSelector):
(WebCore::SelectorCompiler::fragmentRelationForSelectorRelation):
(WebCore::SelectorCompiler::SelectorCodeGenerator::SelectorCodeGenerator):
(WebCore::SelectorCompiler::SelectorCodeGenerator::compile):
(WebCore::SelectorCompiler::updateChainStates):
(WebCore::SelectorCompiler::isFirstAncestor):
(WebCore::SelectorCompiler::isFirstAdjacent):
(WebCore::SelectorCompiler::isAfterChildRelation):
(WebCore::SelectorCompiler::solveBacktrackingAction):
(WebCore::SelectorCompiler::requiresAdjacentTail):
(WebCore::SelectorCompiler::requiresDescendantTail):
(WebCore::SelectorCompiler::SelectorCodeGenerator::computeBacktrackingInformation):
(WebCore::SelectorCompiler::testIsElementFlagOnNode):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateWalkToParentElement):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateParentElementTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateAncestorTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateWalkToPreviousAdjacent):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateDirectAdjacentTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateIndirectAdjacentTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::markParentElementIfResolvingStyle):
(WebCore::SelectorCompiler::SelectorCodeGenerator::linkFailures):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateAdjacentBacktrackingTail):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateDescendantBacktrackingTail):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateBacktrackingTailsIfNeeded):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementHasTagName):
* cssjit/SelectorCompiler.h: Added.
(WebCore::SelectorCompilationStatus::SelectorCompilationStatus):
(WebCore::SelectorCompilationStatus::operator Status):
(WebCore::SelectorCompiler::simpleSelectorCheckerFunction):
(WebCore::SelectorCompiler::selectorCheckerFunctionWithCheckingContext):
* dom/Element.cpp:
(WebCore::Element::setChildrenAffectedByDirectAdjacentRules):
(WebCore::Element::setChildrenAffectedByForwardPositionalRules):
* dom/Element.h:
(WebCore::Element::tagQNameMemoryOffset):
(WebCore::Element::setChildrenAffectedByForwardPositionalRules):
* dom/Node.h:
(WebCore::Node::parentNodeMemoryOffset):
(WebCore::Node::previousSiblingMemoryOffset):
(WebCore::Node::nodeFlagsMemoryOffset):
(WebCore::Node::flagIsElement):
* dom/QualifiedName.h:
(WebCore::QualifiedName::QualifiedNameImpl::localNameMemoryOffset):
(WebCore::QualifiedName::QualifiedNameImpl::namespaceMemoryOffset):
(WebCore::QualifiedName::implMemoryOffset):


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@160983 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=125972

Reviewed by Geoffrey Garen.

Source/JavaScriptCore: 

Split branchTest32 in two functions: test32AndSetFlags and branchOnFlags.
This is done to allow code where the flags are set, multiple operation that
do not modify the flags occur, then the flags are used.

This is used for function calls to test the return value while discarding the
return register.

* assembler/MacroAssemblerX86Common.h:
(JSC::MacroAssemblerX86Common::test32AndSetFlags):
(JSC::MacroAssemblerX86Common::branchOnFlags):
(JSC::MacroAssemblerX86Common::branchTest32):

Source/WebCore: 

FunctionCall is a little helper class to make function calls from the JIT
in 3 or 4 lines.

FunctionCall takes a StackAllocator, a RegisterAllocator and a function pointer.
When the call is generated, the helper saves the registers as necessary, aligns
the stack, does the call, restores the stack, and restore the registers.

* cssjit/FunctionCall.h: Added.
(WebCore::FunctionCall::FunctionCall):
(WebCore::FunctionCall::setFunctionAddress):
(WebCore::FunctionCall::setFirstArgument):
(WebCore::FunctionCall::call):

(WebCore::FunctionCall::callAndBranchOnCondition): Most test functions used
with FunctionCall return a boolean. When the boolean is the sole purpose of the function
call, this provides an easy way to branch on the boolean without worrying about registers.

The return register is tested first, then all the saved registers are restored from the stack
(which can include the return register), finally the flags are used for a jump.

(WebCore::FunctionCall::prepareAndCall):
(WebCore::FunctionCall::cleanupPostCall):
(WebCore::FunctionCall::saveAllocatedRegisters):
(WebCore::FunctionCall::restoreAllocatedRegisters):
* WebCore.xcodeproj/project.pbxproj:
* cssjit/FunctionCall.h: Added.
(WebCore::FunctionCall::FunctionCall):
(WebCore::FunctionCall::setFunctionAddress):
(WebCore::FunctionCall::setFirstArgument):
(WebCore::FunctionCall::call):
(WebCore::FunctionCall::callAndBranchOnCondition):
(WebCore::FunctionCall::prepareAndCall):
(WebCore::FunctionCall::cleanupPostCall):
(WebCore::FunctionCall::saveAllocatedRegisters):
(WebCore::FunctionCall::restoreAllocatedRegisters):


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@160881 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=125908

Reviewed by Geoffrey Garen.

Source/JavaScriptCore: 

* assembler/MacroAssemblerX86_64.h:
(JSC::MacroAssemblerX86_64::addPtrNoFlags):
Add an explicit abstraction for the "lea" instruction. This is needed
by the experimental JIT to have add and substract without changing the flags.

This is useful for function calls to test the return value, restore the registers,
then branch on the flags from the return value.

Source/WebCore: 

StackAllocator provides an abstraction to make it hard to make mistakes and protects from obvious
issues at runtime.

The key roles of StackAllocators are:
-Provide the necessary stack alignment for function calls (only x86_64 stack for now).
-Provide ways to save registers on the stack, restore or discard them as needed.
-Crash at runtime if an operation would obviously cause a stack inconsistency.

The way simple inconsistencies are detected is through the StackReference object
returned whenever something is added on the stack.
The object keeps a reference to the offset of what has been pushed. When the StackReference
is used to recover the register, if the offset is different, there is a missmatch between
push() and pop() after the object was pushed.

* cssjit/StackAllocator.h: Added.
(WebCore::StackAllocator::StackReference::StackReference):
(WebCore::StackAllocator::StackReference::operator unsigned):
(WebCore::StackAllocator::StackAllocator):
(WebCore::StackAllocator::~StackAllocator):
(WebCore::StackAllocator::push):
(WebCore::StackAllocator::pop):

(WebCore::StackAllocator::alignStackPreFunctionCall):
(WebCore::StackAllocator::unalignStackPostFunctionCall):
Those helpers provide a simple way to have a valid stack prior to a function call.
Since StackAllocator knows the offset and the platform rules, it can adjust the stack
if needed for x86_64.

(WebCore::StackAllocator::discard): Discard a single register or the full stack.

(WebCore::StackAllocator::combine): combining stacks is the way to solve branches
where the stack is used differently in each case.
To do that, the stack is first copied to A and B. Each branch works on its own
StackAllocator copy, then the two copies are linked together to the original stack.

The copies ensure the local consistency in each branch, linking the copies ensure global
consistencies and that both branches end in the same stack state.

(WebCore::StackAllocator::offsetToStackReference): Helper function to access the stack by address
through its StackReference.

(WebCore::StackAllocator::reset):


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@160800 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=125771

Reviewed by Geoffrey Garen.

Source/WebCore: 

Add a brain dead register allocator to simplify the use of registers
when writting code generators.

RegisterAllocator has two purposes:
-make it easy to name registers properly.
-make it hard to reuse a register accidentally.

A helper class LocalRegister is also defined to provide an easy
way to work with registers within a C++ scope. For example:
    LocalRegister elementPointer(allocator);
    assembler.load(address, elementPointer);

RegisterAllocator makes no attempt at optimizing register allocations, but it reduces
implicit dependencies by returning used register at the end of the queue, making it less
likely they will be reused before their last instruction is executed.

The current implementation only support unix x86_64, it only uses caller saved registers.

* WebCore.xcodeproj/project.pbxproj:
* cssjit/RegisterAllocator.h: Added.
(WebCore::RegisterAllocator::allocateRegister): Provides any available register.
To restrict runtime exploitation of compiler bugs, the method crashes in release
if the register pool is empty.

(WebCore::RegisterAllocator::reserveRegister): Reserve a particular register.
(WebCore::RegisterAllocator::returnRegister): Return a previously allocated or reserved register.

(WebCore::RegisterAllocator::allocatedRegisters):
(WebCore::LocalRegister::LocalRegister):
(WebCore::LocalRegister::~LocalRegister):
(WebCore::LocalRegister::operator JSC::MacroAssembler::RegisterID):
(WebCore::RegisterAllocator::RegisterAllocator):

Source/WTF: 

* wtf/Platform.h: Add a new flag "CSS_SELECTOR_JIT" to guard
an experimental JIT compiler in WebCore.


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@160697 268f45cc-cd09-0410-ab3c-d52691b4dbfc