1. 19 Oct, 2013 1 commit
  2. 25 Jul, 2013 3 commits
    • oliver@apple.com's avatar
      fourthTier: NaturalLoops + Profiler = Crash · 1d325fa7
      oliver@apple.com authored
      https://bugs.webkit.org/show_bug.cgi?id=118486
      
      Reviewed by Geoffrey Garen.
      
      I borked dominators in:
      http://trac.webkit.org/changeset/152431/branches/dfgFourthTier/Source/JavaScriptCore/dfg/DFGDominators.h
      
      This patch also adds some debug support, and fixes the loop that adds a block to
      an already-existing natural loop. Note that we currently don't take that path in
      most programs, but it will arise, for example if you use 'continue' - though you'd
      have to use it rather cleverly since the bytecode will not jump to the loop header
      in most uses of 'continue'.
      
      * dfg/DFGDominators.cpp:
      (JSC::DFG::Dominators::dump):
      (DFG):
      * dfg/DFGDominators.h:
      (JSC::DFG::Dominators::dominates):
      (Dominators):
      * dfg/DFGNaturalLoops.cpp:
      (JSC::DFG::NaturalLoops::compute):
      
      git-svn-id: http://svn.webkit.org/repository/webkit/trunk@153272 268f45cc-cd09-0410-ab3c-d52691b4dbfc
      1d325fa7
    • oliver@apple.com's avatar
      fourthTier: DFG should refer to BasicBlocks by BasicBlock* and not BlockIndex · 426f5b02
      oliver@apple.com authored
      https://bugs.webkit.org/show_bug.cgi?id=118339
      
      Reviewed by Michael Saboff.
      
      This accomplishes two goals:
      
      1) Simplifies a bunch of code. You can now much more directly get to a successor
         or predecessor, since you just get the pointer directly. The backend(s) always
         hold onto a pointer to the block they're on, so you don't have to do work to
         get the block from the index.
      
      2) It allows for the possibility of inserting blocks into the program.
         Previously, if you did that, you'd have to edit all references to blocks since
         those references would have outdated indexing after an insertion. Now, if you
         change the indexing, you just have to invalidate some analyses and make sure
         that you change each block's BasicBlock::index accordingly.
      
      * dfg/DFGAbstractState.cpp:
      (JSC::DFG::AbstractState::initialize):
      (JSC::DFG::AbstractState::endBasicBlock):
      (JSC::DFG::AbstractState::mergeToSuccessors):
      * dfg/DFGAbstractState.h:
      (AbstractState):
      * dfg/DFGArgumentsSimplificationPhase.cpp:
      (JSC::DFG::ArgumentsSimplificationPhase::run):
      * dfg/DFGBackwardsPropagationPhase.cpp:
      (JSC::DFG::BackwardsPropagationPhase::run):
      * dfg/DFGBasicBlock.h:
      (DFG):
      (JSC::DFG::BasicBlock::BasicBlock):
      (JSC::DFG::BasicBlock::size):
      (JSC::DFG::BasicBlock::isEmpty):
      (JSC::DFG::BasicBlock::at):
      (JSC::DFG::BasicBlock::operator[]):
      (JSC::DFG::BasicBlock::last):
      (JSC::DFG::BasicBlock::resize):
      (JSC::DFG::BasicBlock::grow):
      (BasicBlock):
      (JSC::DFG::BasicBlock::append):
      (JSC::DFG::BasicBlock::numSuccessors):
      (JSC::DFG::BasicBlock::successor):
      (JSC::DFG::BasicBlock::successorForCondition):
      (JSC::DFG::BasicBlock::dump):
      (UnlinkedBlock):
      (JSC::DFG::UnlinkedBlock::UnlinkedBlock):
      (JSC::DFG::getBytecodeBeginForBlock):
      (JSC::DFG::blockForBytecodeOffset):
      * dfg/DFGByteCodeParser.cpp:
      (ByteCodeParser):
      (InlineStackEntry):
      (JSC::DFG::ByteCodeParser::handleInlining):
      (JSC::DFG::ByteCodeParser::parseBlock):
      (JSC::DFG::ByteCodeParser::linkBlock):
      (JSC::DFG::ByteCodeParser::linkBlocks):
      (JSC::DFG::ByteCodeParser::InlineStackEntry::InlineStackEntry):
      (JSC::DFG::ByteCodeParser::parseCodeBlock):
      (JSC::DFG::ByteCodeParser::parse):
      * dfg/DFGCFAPhase.cpp:
      (JSC::DFG::CFAPhase::performBlockCFA):
      (JSC::DFG::CFAPhase::performForwardCFA):
      * dfg/DFGCFGSimplificationPhase.cpp:
      (JSC::DFG::CFGSimplificationPhase::run):
      (JSC::DFG::CFGSimplificationPhase::convertToJump):
      * dfg/DFGCPSRethreadingPhase.cpp:
      (JSC::DFG::CPSRethreadingPhase::freeUnnecessaryNodes):
      (JSC::DFG::CPSRethreadingPhase::canonicalizeLocalsInBlocks):
      (JSC::DFG::CPSRethreadingPhase::propagatePhis):
      (CPSRethreadingPhase):
      * dfg/DFGCSEPhase.cpp:
      (JSC::DFG::CSEPhase::run):
      * dfg/DFGConstantFoldingPhase.cpp:
      (JSC::DFG::ConstantFoldingPhase::run):
      (JSC::DFG::ConstantFoldingPhase::foldConstants):
      * dfg/DFGDCEPhase.cpp:
      (JSC::DFG::DCEPhase::run):
      * dfg/DFGDisassembler.cpp:
      (JSC::DFG::Disassembler::Disassembler):
      (JSC::DFG::Disassembler::createDumpList):
      * dfg/DFGDisassembler.h:
      (JSC::DFG::Disassembler::setForBlockIndex):
      * dfg/DFGDominators.cpp:
      (JSC::DFG::Dominators::compute):
      (JSC::DFG::Dominators::iterateForBlock):
      * dfg/DFGDominators.h:
      (JSC::DFG::Dominators::dominates):
      * dfg/DFGFixupPhase.cpp:
      (JSC::DFG::FixupPhase::run):
      (JSC::DFG::FixupPhase::fixupNode):
      * dfg/DFGGraph.cpp:
      (JSC::DFG::Graph::dump):
      (JSC::DFG::Graph::dumpBlockHeader):
      (JSC::DFG::Graph::handleSuccessor):
      (JSC::DFG::Graph::determineReachability):
      (JSC::DFG::Graph::resetReachability):
      * dfg/DFGGraph.h:
      (JSC::DFG::Graph::numBlocks):
      (JSC::DFG::Graph::block):
      (JSC::DFG::Graph::lastBlock):
      (Graph):
      (JSC::DFG::Graph::appendBlock):
      (JSC::DFG::Graph::killBlock):
      (DFG):
      * dfg/DFGJITCompiler.cpp:
      (JSC::DFG::JITCompiler::JITCompiler):
      (JSC::DFG::JITCompiler::link):
      * dfg/DFGJITCompiler.h:
      (JSC::DFG::JITCompiler::setForBlockIndex):
      * dfg/DFGNaturalLoops.cpp:
      (JSC::DFG::NaturalLoop::dump):
      (JSC::DFG::NaturalLoops::compute):
      (JSC::DFG::NaturalLoops::loopsOf):
      * dfg/DFGNaturalLoops.h:
      (JSC::DFG::NaturalLoop::NaturalLoop):
      (JSC::DFG::NaturalLoop::addBlock):
      (JSC::DFG::NaturalLoop::header):
      (JSC::DFG::NaturalLoop::at):
      (JSC::DFG::NaturalLoop::operator[]):
      (JSC::DFG::NaturalLoop::contains):
      (NaturalLoop):
      (JSC::DFG::NaturalLoops::headerOf):
      (NaturalLoops):
      * dfg/DFGNode.h:
      (DFG):
      (JSC::DFG::SwitchCase::SwitchCase):
      (JSC::DFG::SwitchCase::withBytecodeIndex):
      (SwitchCase):
      (JSC::DFG::SwitchCase::targetBytecodeIndex):
      (JSC::DFG::SwitchData::SwitchData):
      (JSC::DFG::SwitchData::setFallThroughBytecodeIndex):
      (JSC::DFG::SwitchData::fallThroughBytecodeIndex):
      (SwitchData):
      (JSC::DFG::Node::setTakenBlock):
      (JSC::DFG::Node::setNotTakenBlock):
      (JSC::DFG::Node::takenBlock):
      (JSC::DFG::Node::notTakenBlock):
      (JSC::DFG::Node::successor):
      (JSC::DFG::Node::successorForCondition):
      * dfg/DFGPredictionInjectionPhase.cpp:
      (JSC::DFG::PredictionInjectionPhase::run):
      * dfg/DFGPredictionPropagationPhase.cpp:
      (JSC::DFG::PredictionPropagationPhase::propagateForward):
      (JSC::DFG::PredictionPropagationPhase::propagateBackward):
      (JSC::DFG::PredictionPropagationPhase::doRoundOfDoubleVoting):
      * dfg/DFGSpeculativeJIT.cpp:
      (JSC::DFG::SpeculativeJIT::convertLastOSRExitToForward):
      (JSC::DFG::SpeculativeJIT::nonSpeculativeCompare):
      (JSC::DFG::SpeculativeJIT::nonSpeculativeStrictEq):
      (JSC::DFG::SpeculativeJIT::compilePeepHoleDoubleBranch):
      (JSC::DFG::SpeculativeJIT::compilePeepHoleObjectEquality):
      (JSC::DFG::SpeculativeJIT::compilePeepHoleIntegerBranch):
      (JSC::DFG::SpeculativeJIT::compilePeepHoleBranch):
      (JSC::DFG::SpeculativeJIT::compileCurrentBlock):
      (JSC::DFG::SpeculativeJIT::compile):
      (JSC::DFG::SpeculativeJIT::createOSREntries):
      (JSC::DFG::SpeculativeJIT::linkOSREntries):
      (JSC::DFG::SpeculativeJIT::compileStrictEqForConstant):
      (JSC::DFG::SpeculativeJIT::compileStrictEq):
      (JSC::DFG::SpeculativeJIT::compileRegExpExec):
      (JSC::DFG::SpeculativeJIT::addBranch):
      (JSC::DFG::SpeculativeJIT::linkBranches):
      * dfg/DFGSpeculativeJIT.h:
      (JSC::DFG::SpeculativeJIT::nextBlock):
      (SpeculativeJIT):
      (JSC::DFG::SpeculativeJIT::detectPeepHoleBranch):
      (JSC::DFG::SpeculativeJIT::branchDouble):
      (JSC::DFG::SpeculativeJIT::branchDoubleNonZero):
      (JSC::DFG::SpeculativeJIT::branch32):
      (JSC::DFG::SpeculativeJIT::branchTest32):
      (JSC::DFG::SpeculativeJIT::branch64):
      (JSC::DFG::SpeculativeJIT::branch8):
      (JSC::DFG::SpeculativeJIT::branchPtr):
      (JSC::DFG::SpeculativeJIT::branchTestPtr):
      (JSC::DFG::SpeculativeJIT::branchTest8):
      (JSC::DFG::SpeculativeJIT::jump):
      (JSC::DFG::SpeculativeJIT::addBranch):
      (JSC::DFG::SpeculativeJIT::StringSwitchCase::StringSwitchCase):
      (StringSwitchCase):
      (JSC::DFG::SpeculativeJIT::BranchRecord::BranchRecord):
      (BranchRecord):
      * dfg/DFGSpeculativeJIT32_64.cpp:
      (JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeBranchNull):
      (JSC::DFG::SpeculativeJIT::nonSpeculativeCompareNull):
      (JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeBranch):
      (JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeStrictEq):
      (JSC::DFG::SpeculativeJIT::compilePeepHoleObjectToObjectOrOtherEquality):
      (JSC::DFG::SpeculativeJIT::emitObjectOrOtherBranch):
      (JSC::DFG::SpeculativeJIT::emitBranch):
      (JSC::DFG::SpeculativeJIT::compile):
      * dfg/DFGSpeculativeJIT64.cpp:
      (JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeBranchNull):
      (JSC::DFG::SpeculativeJIT::nonSpeculativeCompareNull):
      (JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeBranch):
      (JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeStrictEq):
      (JSC::DFG::SpeculativeJIT::compilePeepHoleObjectToObjectOrOtherEquality):
      (JSC::DFG::SpeculativeJIT::emitObjectOrOtherBranch):
      (JSC::DFG::SpeculativeJIT::emitBranch):
      (JSC::DFG::SpeculativeJIT::compile):
      * dfg/DFGTypeCheckHoistingPhase.cpp:
      (JSC::DFG::TypeCheckHoistingPhase::run):
      (JSC::DFG::TypeCheckHoistingPhase::identifyRedundantStructureChecks):
      (JSC::DFG::TypeCheckHoistingPhase::identifyRedundantArrayChecks):
      (JSC::DFG::TypeCheckHoistingPhase::disableHoistingAcrossOSREntries):
      * dfg/DFGUnificationPhase.cpp:
      (JSC::DFG::UnificationPhase::run):
      * dfg/DFGValidate.cpp:
      (JSC::DFG::Validate::validate):
      (JSC::DFG::Validate::checkOperand):
      (JSC::DFG::Validate::reportValidationContext):
      * dfg/DFGVirtualRegisterAllocationPhase.cpp:
      (JSC::DFG::VirtualRegisterAllocationPhase::run):
      * ftl/FTLCapabilities.cpp:
      (JSC::FTL::canCompile):
      * ftl/FTLLowerDFGToLLVM.cpp:
      (JSC::FTL::LowerDFGToLLVM::LowerDFGToLLVM):
      (JSC::FTL::LowerDFGToLLVM::lower):
      (JSC::FTL::LowerDFGToLLVM::compileBlock):
      (JSC::FTL::LowerDFGToLLVM::compileJump):
      (JSC::FTL::LowerDFGToLLVM::compileBranch):
      (JSC::FTL::LowerDFGToLLVM::lowBlock):
      
      git-svn-id: http://svn.webkit.org/repository/webkit/trunk@153267 268f45cc-cd09-0410-ab3c-d52691b4dbfc
      426f5b02
    • oliver@apple.com's avatar
      fourthTier: DFG should know how to find natural loops · fc3f1177
      oliver@apple.com authored
      https://bugs.webkit.org/show_bug.cgi?id=118152
      
      Reviewed by Mark Hahnenberg.
      
      There are a bunch of things we can do when we know where the loops are.
      Previously we didn't. With this patch, we do.
      
      This patch adds the classic dominator based natural loop finder.
      
      The only client of this right now is the DFG::Disassembler. It prints out
      a summary of the analysis for each block.
      
      This will become more important when I do
      https://bugs.webkit.org/show_bug.cgi?id=118151, which definitely requires
      this kind of analysis, at least if we want to do the optimization over
      DFG IR (and I'm pretty sure we do).
      
      * JavaScriptCore.xcodeproj/project.pbxproj:
      * dfg/DFGAnalysis.h: Added.
      (DFG):
      (Analysis):
      (JSC::DFG::Analysis::Analysis):
      (JSC::DFG::Analysis::invalidate):
      (JSC::DFG::Analysis::computeIfNecessary):
      (JSC::DFG::Analysis::isValid):
      * dfg/DFGCFGSimplificationPhase.cpp:
      (JSC::DFG::CFGSimplificationPhase::run):
      * dfg/DFGDisassembler.cpp:
      (JSC::DFG::Disassembler::createDumpList):
      * dfg/DFGDominators.cpp:
      (JSC::DFG::Dominators::Dominators):
      (JSC::DFG::Dominators::compute):
      * dfg/DFGDominators.h:
      (Dominators):
      * dfg/DFGGraph.cpp:
      (JSC::DFG::Graph::dumpBlockHeader):
      (JSC::DFG::Graph::invalidateCFG):
      (DFG):
      * dfg/DFGGraph.h:
      (Graph):
      * dfg/DFGNaturalLoops.cpp: Added.
      (DFG):
      (JSC::DFG::NaturalLoop::dump):
      (JSC::DFG::NaturalLoops::NaturalLoops):
      (JSC::DFG::NaturalLoops::~NaturalLoops):
      (JSC::DFG::NaturalLoops::compute):
      (JSC::DFG::NaturalLoops::loopsOf):
      (JSC::DFG::NaturalLoops::dump):
      * dfg/DFGNaturalLoops.h: Added.
      (DFG):
      (NaturalLoop):
      (JSC::DFG::NaturalLoop::NaturalLoop):
      (JSC::DFG::NaturalLoop::addBlock):
      (JSC::DFG::NaturalLoop::header):
      (JSC::DFG::NaturalLoop::size):
      (JSC::DFG::NaturalLoop::at):
      (JSC::DFG::NaturalLoop::operator[]):
      (JSC::DFG::NaturalLoop::contains):
      (NaturalLoops):
      (JSC::DFG::NaturalLoops::numLoops):
      (JSC::DFG::NaturalLoops::loop):
      (JSC::DFG::NaturalLoops::headerOf):
      
      git-svn-id: http://svn.webkit.org/repository/webkit/trunk@153257 268f45cc-cd09-0410-ab3c-d52691b4dbfc
      fc3f1177
  3. 22 May, 2012 1 commit
    • fpizlo@apple.com's avatar
      DFG should be able to compute dominators · ba79d1f9
      fpizlo@apple.com authored
      https://bugs.webkit.org/show_bug.cgi?id=85269
      
      Source/JavaScriptCore: 
      
      Reviewed by Oliver Hunt.
              
      Merged r115754 from dfgopt.
              
      Implements a naive dominator calculator, which is currently just used to
      print information in graph dumps. I've enabled it by default mainly to
      be able to track its performance impact. So far it appears that there is
      none, which is unsurprising given that the number of basic blocks in most
      procedures is small.
              
      Also tweaked bytecode dumping to reveal more useful information about the
      nature of the code block.
      
      * CMakeLists.txt:
      * GNUmakefile.list.am:
      * JavaScriptCore.xcodeproj/project.pbxproj:
      * Target.pri:
      * bytecode/CodeBlock.cpp:
      (JSC::CodeBlock::dump):
      * dfg/DFGDominators.cpp: Added.
      (DFG):
      (JSC::DFG::Dominators::Dominators):
      (JSC::DFG::Dominators::~Dominators):
      (JSC::DFG::Dominators::compute):
      (JSC::DFG::Dominators::iterateForBlock):
      * dfg/DFGDominators.h: Added.
      (DFG):
      (Dominators):
      (JSC::DFG::Dominators::invalidate):
      (JSC::DFG::Dominators::computeIfNecessary):
      (JSC::DFG::Dominators::isValid):
      (JSC::DFG::Dominators::dominates):
      * dfg/DFGDriver.cpp:
      (JSC::DFG::compile):
      * dfg/DFGGraph.cpp:
      (JSC::DFG::Graph::dump):
      * dfg/DFGGraph.h:
      (Graph):
      
      Source/WTF: 
      
      Reviewed by Oliver Hunt.
              
      Merged r115754 from dfgopt.
              
      Added a bitvector class suitable for cheap static analysis. This class
      differs from BitVector in that instead of optimizing for space, it
      optimizes for execution time. Its API is also somewhat less friendly,
      which is intentional; it's meant to be used in places where you know
      up front how bit your bitvectors are going to be.
      
      * GNUmakefile.list.am:
      * WTF.vcproj/WTF.vcproj:
      * WTF.xcodeproj/project.pbxproj:
      * wtf/FastBitVector.h: Added.
      (WTF):
      (FastBitVector):
      (WTF::FastBitVector::FastBitVector):
      (WTF::FastBitVector::operator=):
      (WTF::FastBitVector::numBits):
      (WTF::FastBitVector::resize):
      (WTF::FastBitVector::setAll):
      (WTF::FastBitVector::clearAll):
      (WTF::FastBitVector::set):
      (WTF::FastBitVector::setAndCheck):
      (WTF::FastBitVector::equals):
      (WTF::FastBitVector::merge):
      (WTF::FastBitVector::filter):
      (WTF::FastBitVector::exclude):
      (WTF::FastBitVector::clear):
      (WTF::FastBitVector::get):
      (WTF::FastBitVector::arrayLength):
      
      
      
      git-svn-id: http://svn.webkit.org/repository/webkit/trunk@117861 268f45cc-cd09-0410-ab3c-d52691b4dbfc
      ba79d1f9