1. 12 Jan, 2014 1 commit
    • benjamin@webkit.org's avatar
      Use the Selector Code Generator for matching in SelectorQuery · b2d9efda
      benjamin@webkit.org authored
      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
      b2d9efda
  2. 23 Dec, 2013 4 commits
    • benjamin@webkit.org's avatar
      Add the pseudo classes link and any-link to the Selector Code Generator · 07627794
      benjamin@webkit.org authored
      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
      07627794
    • benjamin@webkit.org's avatar
      Add the pseudo class :focus to the Selector Code Generator · 46e596cb
      benjamin@webkit.org authored
      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
      46e596cb
    • benjamin@webkit.org's avatar
      Add class matching to the Selector Code Generator · 3a722540
      benjamin@webkit.org authored
      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
      3a722540
    • benjamin@webkit.org's avatar
      Add id matching to the Selector Code Generator · a26c491c
      benjamin@webkit.org authored
      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
      a26c491c
  3. 22 Dec, 2013 1 commit
    • benjamin@webkit.org's avatar
      Create a skeleton for CSS Selector code generation · 182c19a4
      benjamin@webkit.org authored
      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
      182c19a4
  4. 19 Dec, 2013 1 commit
    • benjamin@webkit.org's avatar
      Add an utility class to simplify generating function calls · 05413aee
      benjamin@webkit.org authored
      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
      05413aee
  5. 18 Dec, 2013 1 commit
    • benjamin@webkit.org's avatar
      Add a simple stack abstraction for x86_64 · da98b823
      benjamin@webkit.org authored
      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
      da98b823
  6. 17 Dec, 2013 1 commit
    • benjamin@webkit.org's avatar
      Add a simple register allocator to WebCore for x86_64 · 1f71579f
      benjamin@webkit.org authored
      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
      1f71579f