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

Reviewed by Gavin Barraclough.

Implemented a control flow analysis (CFA). It currently propagates type
proofs only. For example, if all predecessors to a basic block have
checks that variable X is a JSFinalObject with structure 0xabcdef, then
this basic block will now know this fact and will know that it does not
have to emit either JSFinalObject checks or any structure checks since
the structure is precisely known. The CFA takes heap side-effects into
account (though somewhat conservatively), so that if the object pointed
to by variable X could have possibly undergone a structure transition
then this is reflected: the analysis may simply say that X's structure
is unknown.
        
This also propagates a wealth of other type information which is
currently not being used. For example, we now know when a variable can
only hold doubles. Even if a variable may hold other types at different
points in its live range, we can still prove exactly when it will only
be double.
        
There's a bunch of stuff that the CFA could do that it still does not
do, like precise handling of PutStructure (i.e. structure transitions),
precise handling of CheckFunction and CheckMethod, etc. So this is
very much intended to be a starting point rather than an end unto
itself.
        
This is a 1% win on V8 (mostly due to a 3% win on richards and deltablue)
and a 1% win on Kraken (mostly due to a 6% win on imaging-desaturate).
Neutral on SunSpider.

* GNUmakefile.list.am:
* JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* bytecode/ActionablePrediction.h: Removed.
* bytecode/PredictedType.cpp:
(JSC::predictionToString):
* bytecode/PredictedType.h:
* dfg/DFGAbstractState.cpp: Added.
(JSC::DFG::AbstractState::AbstractState):
(JSC::DFG::AbstractState::~AbstractState):
(JSC::DFG::AbstractState::beginBasicBlock):
(JSC::DFG::AbstractState::initialize):
(JSC::DFG::AbstractState::endBasicBlock):
(JSC::DFG::AbstractState::reset):
(JSC::DFG::AbstractState::execute):
(JSC::DFG::AbstractState::clobberStructures):
(JSC::DFG::AbstractState::mergeStateAtTail):
(JSC::DFG::AbstractState::merge):
(JSC::DFG::AbstractState::mergeToSuccessors):
(JSC::DFG::AbstractState::mergeVariableBetweenBlocks):
(JSC::DFG::AbstractState::dump):
* dfg/DFGAbstractState.h: Added.
(JSC::DFG::AbstractState::forNode):
(JSC::DFG::AbstractState::isValid):
* dfg/DFGAbstractValue.h: Added.
(JSC::DFG::StructureAbstractValue::StructureAbstractValue):
(JSC::DFG::StructureAbstractValue::clear):
(JSC::DFG::StructureAbstractValue::makeTop):
(JSC::DFG::StructureAbstractValue::top):
(JSC::DFG::StructureAbstractValue::add):
(JSC::DFG::StructureAbstractValue::addAll):
(JSC::DFG::StructureAbstractValue::contains):
(JSC::DFG::StructureAbstractValue::isSubsetOf):
(JSC::DFG::StructureAbstractValue::doesNotContainAnyOtherThan):
(JSC::DFG::StructureAbstractValue::isSupersetOf):
(JSC::DFG::StructureAbstractValue::filter):
(JSC::DFG::StructureAbstractValue::isClear):
(JSC::DFG::StructureAbstractValue::isTop):
(JSC::DFG::StructureAbstractValue::size):
(JSC::DFG::StructureAbstractValue::at):
(JSC::DFG::StructureAbstractValue::operator[]):
(JSC::DFG::StructureAbstractValue::last):
(JSC::DFG::StructureAbstractValue::predictionFromStructures):
(JSC::DFG::StructureAbstractValue::operator==):
(JSC::DFG::StructureAbstractValue::dump):
(JSC::DFG::AbstractValue::AbstractValue):
(JSC::DFG::AbstractValue::clear):
(JSC::DFG::AbstractValue::isClear):
(JSC::DFG::AbstractValue::makeTop):
(JSC::DFG::AbstractValue::clobberStructures):
(JSC::DFG::AbstractValue::isTop):
(JSC::DFG::AbstractValue::top):
(JSC::DFG::AbstractValue::set):
(JSC::DFG::AbstractValue::operator==):
(JSC::DFG::AbstractValue::merge):
(JSC::DFG::AbstractValue::filter):
(JSC::DFG::AbstractValue::validate):
(JSC::DFG::AbstractValue::dump):
* dfg/DFGBasicBlock.h: Added.
(JSC::DFG::BasicBlock::BasicBlock):
(JSC::DFG::BasicBlock::getBytecodeBegin):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::getLocal):
(JSC::DFG::ByteCodeParser::setLocal):
(JSC::DFG::ByteCodeParser::getArgument):
(JSC::DFG::ByteCodeParser::setArgument):
(JSC::DFG::ByteCodeParser::parseBlock):
(JSC::DFG::ByteCodeParser::processPhiStack):
(JSC::DFG::ByteCodeParser::setupPredecessors):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
* dfg/DFGGraph.h:
* dfg/DFGJITCodeGenerator.h:
(JSC::DFG::block):
* dfg/DFGJITCodeGenerator32_64.cpp:
(JSC::DFG::JITCodeGenerator::nonSpeculativePeepholeBranchNull):
(JSC::DFG::JITCodeGenerator::nonSpeculativePeepholeBranch):
(JSC::DFG::JITCodeGenerator::nonSpeculativePeepholeStrictEq):
* dfg/DFGJITCodeGenerator64.cpp:
(JSC::DFG::JITCodeGenerator::nonSpeculativePeepholeBranchNull):
(JSC::DFG::JITCodeGenerator::nonSpeculativePeepholeBranch):
(JSC::DFG::JITCodeGenerator::nonSpeculativePeepholeStrictEq):
* dfg/DFGJITCompiler.h:
(JSC::DFG::JITCompiler::noticeOSREntry):
* dfg/DFGNode.h:
(JSC::DFG::NodeIndexTraits::defaultValue):
(JSC::DFG::Node::variableAccessData):
(JSC::DFG::Node::takenBytecodeOffsetDuringParsing):
(JSC::DFG::Node::notTakenBytecodeOffsetDuringParsing):
(JSC::DFG::Node::setTakenBlockIndex):
(JSC::DFG::Node::setNotTakenBlockIndex):
(JSC::DFG::Node::takenBlockIndex):
(JSC::DFG::Node::notTakenBlockIndex):
* dfg/DFGOSREntry.cpp:
(JSC::DFG::prepareOSREntry):
* dfg/DFGOSREntry.h:
* dfg/DFGOperands.h: Added.
(JSC::DFG::operandIsArgument):
(JSC::DFG::OperandValueTraits::defaultValue):
(JSC::DFG::Operands::Operands):
(JSC::DFG::Operands::numberOfArguments):
(JSC::DFG::Operands::numberOfLocals):
(JSC::DFG::Operands::argument):
(JSC::DFG::Operands::local):
(JSC::DFG::Operands::setLocal):
(JSC::DFG::Operands::setArgumentFirstTime):
(JSC::DFG::Operands::setLocalFirstTime):
(JSC::DFG::Operands::operand):
(JSC::DFG::Operands::setOperand):
(JSC::DFG::Operands::clear):
(JSC::DFG::dumpOperands):
* dfg/DFGPropagator.cpp:
(JSC::DFG::Propagator::fixpoint):
(JSC::DFG::Propagator::propagateArithNodeFlags):
(JSC::DFG::Propagator::propagateNodePredictions):
(JSC::DFG::Propagator::propagatePredictions):
(JSC::DFG::Propagator::performBlockCFA):
(JSC::DFG::Propagator::performForwardCFA):
(JSC::DFG::Propagator::globalCFA):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compilePeepHoleDoubleBranch):
(JSC::DFG::SpeculativeJIT::compilePeepHoleObjectEquality):
(JSC::DFG::SpeculativeJIT::compilePeepHoleIntegerBranch):
(JSC::DFG::SpeculativeJIT::compilePeepHoleBranch):
(JSC::DFG::SpeculativeJIT::compile):
(JSC::DFG::SpeculativeJIT::compileGetCharCodeAt):
(JSC::DFG::SpeculativeJIT::compileGetByValOnString):
* dfg/DFGSpeculativeJIT.h:
(JSC::DFG::SpeculativeJIT::SpeculativeJIT):
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compileObjectEquality):
(JSC::DFG::SpeculativeJIT::compare):
(JSC::DFG::SpeculativeJIT::compileObjectOrOtherLogicalNot):
(JSC::DFG::SpeculativeJIT::compileLogicalNot):
(JSC::DFG::SpeculativeJIT::emitObjectOrOtherBranch):
(JSC::DFG::SpeculativeJIT::emitBranch):
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compileObjectEquality):
(JSC::DFG::SpeculativeJIT::compare):
(JSC::DFG::SpeculativeJIT::compileObjectOrOtherLogicalNot):
(JSC::DFG::SpeculativeJIT::compileLogicalNot):
(JSC::DFG::SpeculativeJIT::emitObjectOrOtherBranch):
(JSC::DFG::SpeculativeJIT::emitBranch):
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGStructureSet.h:
(JSC::DFG::StructureSet::clear):
(JSC::DFG::StructureSet::predictionFromStructures):
(JSC::DFG::StructureSet::operator==):
(JSC::DFG::StructureSet::dump):
* dfg/DFGVariableAccessData.h: Added.



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