Diff
Modified: branches/ftlopt/Source/_javascript_Core/ChangeLog (170015 => 170016)
--- branches/ftlopt/Source/_javascript_Core/ChangeLog 2014-06-16 17:41:40 UTC (rev 170015)
+++ branches/ftlopt/Source/_javascript_Core/ChangeLog 2014-06-16 18:03:04 UTC (rev 170016)
@@ -1,3 +1,35 @@
+2014-06-15 Filip Pizlo <[email protected]>
+
+ [ftlopt] DFG OSR entry should have a crystal-clear story for when it's safe to enter at a block with a set of values
+ https://bugs.webkit.org/show_bug.cgi?id=133935
+
+ Reviewed by Oliver Hunt.
+
+ * bytecode/Operands.h:
+ (JSC::Operands::Operands):
+ (JSC::Operands::ensureLocals):
+ * dfg/DFGAbstractValue.cpp:
+ (JSC::DFG::AbstractValue::filter): Now we can compute intersections of abstract values!
+ * dfg/DFGAbstractValue.h:
+ (JSC::DFG::AbstractValue::makeFullTop): Completeness.
+ (JSC::DFG::AbstractValue::bytecodeTop): Completeness.
+ (JSC::DFG::AbstractValue::fullTop): Completeness. We end up using this one.
+ * dfg/DFGBasicBlock.cpp:
+ (JSC::DFG::BasicBlock::BasicBlock):
+ (JSC::DFG::BasicBlock::ensureLocals):
+ * dfg/DFGBasicBlock.h: Remember the intersection of all things ever proven.
+ * dfg/DFGCFAPhase.cpp:
+ (JSC::DFG::CFAPhase::run): Compute the intersection.
+ * dfg/DFGConstantFoldingPhase.cpp:
+ (JSC::DFG::ConstantFoldingPhase::foldConstants): No need for the weirdo merge check since this fixes the root of the problem.
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::dumpBlockHeader): Better dumping.
+ (JSC::DFG::Graph::dump): Better dumping.
+ * dfg/DFGJITCompiler.h:
+ (JSC::DFG::JITCompiler::noticeOSREntry): Use the intersected abstract value.
+ * dfg/DFGSpeculativeJIT.cpp:
+ (JSC::DFG::SpeculativeJIT::compileCurrentBlock): Assert if the intersected state indicates the block shouldn't execute.
+
2014-06-12 Filip Pizlo <[email protected]>
[ftlopt] A DFG inlined ById access variant should not speak of a chain, but only of what structures to test the base for, whether to use a constant as an alternate base for the actual access, and what structures to check on what additional cell constants
Modified: branches/ftlopt/Source/_javascript_Core/bytecode/Operands.h (170015 => 170016)
--- branches/ftlopt/Source/_javascript_Core/bytecode/Operands.h 2014-06-16 17:41:40 UTC (rev 170015)
+++ branches/ftlopt/Source/_javascript_Core/bytecode/Operands.h 2014-06-16 18:03:04 UTC (rev 170016)
@@ -52,10 +52,10 @@
public:
Operands() { }
- explicit Operands(size_t numArguments, size_t numLocals)
+ explicit Operands(size_t numArguments, size_t numLocals, const T& initialValue = Traits::defaultValue())
{
- m_arguments.fill(Traits::defaultValue(), numArguments);
- m_locals.fill(Traits::defaultValue(), numLocals);
+ m_arguments.fill(initialValue, numArguments);
+ m_locals.fill(initialValue, numLocals);
}
template<typename U, typename OtherTraits>
@@ -96,7 +96,7 @@
return local(idx);
}
- void ensureLocals(size_t size)
+ void ensureLocals(size_t size, const T& ensuredValue = Traits::defaultValue())
{
if (size <= m_locals.size())
return;
@@ -104,7 +104,7 @@
size_t oldSize = m_locals.size();
m_locals.resize(size);
for (size_t i = oldSize; i < m_locals.size(); ++i)
- m_locals[i] = Traits::defaultValue();
+ m_locals[i] = ensuredValue;
}
void setLocal(size_t idx, const T& value)
Modified: branches/ftlopt/Source/_javascript_Core/dfg/DFGAbstractValue.cpp (170015 => 170016)
--- branches/ftlopt/Source/_javascript_Core/dfg/DFGAbstractValue.cpp 2014-06-16 17:41:40 UTC (rev 170015)
+++ branches/ftlopt/Source/_javascript_Core/dfg/DFGAbstractValue.cpp 2014-06-16 18:03:04 UTC (rev 170016)
@@ -229,6 +229,39 @@
return result;
}
+FiltrationResult AbstractValue::filter(const AbstractValue& other)
+{
+ m_type &= other.m_type;
+ m_structure.filter(other.m_structure);
+ m_arrayModes &= other.m_arrayModes;
+
+ m_structure.filter(m_type);
+ filterArrayModesByType();
+ filterValueByType();
+
+ if (normalizeClarity() == Contradiction)
+ return Contradiction;
+
+ if (m_value == other.m_value)
+ return FiltrationOK;
+
+ // Neither of us are BOTTOM, so an empty value means TOP.
+ if (!m_value) {
+ // We previously didn't prove a value but now we have done so.
+ m_value = other.m_value;
+ return FiltrationOK;
+ }
+
+ if (!other.m_value) {
+ // We had proved a value but the other guy hadn't, so keep our proof.
+ return FiltrationOK;
+ }
+
+ // We both proved there to be a specific value but they are different.
+ clear();
+ return Contradiction;
+}
+
void AbstractValue::filterValueByType()
{
// We could go further, and ensure that if the futurePossibleStructure contravenes
Modified: branches/ftlopt/Source/_javascript_Core/dfg/DFGAbstractValue.h (170015 => 170016)
--- branches/ftlopt/Source/_javascript_Core/dfg/DFGAbstractValue.h 2014-06-16 17:41:40 UTC (rev 170015)
+++ branches/ftlopt/Source/_javascript_Core/dfg/DFGAbstractValue.h 2014-06-16 18:03:04 UTC (rev 170016)
@@ -73,6 +73,11 @@
makeTop(SpecBytecodeTop);
}
+ void makeFullTop()
+ {
+ makeTop(SpecFullTop);
+ }
+
void clobberStructures()
{
if (m_type & SpecCell) {
@@ -174,6 +179,20 @@
return result;
}
+ static AbstractValue bytecodeTop()
+ {
+ AbstractValue result;
+ result.makeBytecodeTop();
+ return result;
+ }
+
+ static AbstractValue fullTop()
+ {
+ AbstractValue result;
+ result.makeFullTop();
+ return result;
+ }
+
void setOSREntryValue(Graph&, const FrozenValue&);
void set(Graph&, const FrozenValue&, StructureClobberState);
@@ -259,13 +278,12 @@
}
FiltrationResult filter(Graph&, const StructureSet&);
-
FiltrationResult filterArrayModes(ArrayModes arrayModes);
-
FiltrationResult filter(SpeculatedType type);
-
FiltrationResult filterByValue(const FrozenValue& value);
+ FiltrationResult filter(const AbstractValue&);
+
bool validate(JSValue value) const
{
if (isHeapTop())
Modified: branches/ftlopt/Source/_javascript_Core/dfg/DFGBasicBlock.cpp (170015 => 170016)
--- branches/ftlopt/Source/_javascript_Core/dfg/DFGBasicBlock.cpp 2014-06-16 17:41:40 UTC (rev 170015)
+++ branches/ftlopt/Source/_javascript_Core/dfg/DFGBasicBlock.cpp 2014-06-16 18:03:04 UTC (rev 170016)
@@ -52,6 +52,8 @@
, variablesAtTail(numArguments, numLocals)
, valuesAtHead(numArguments, numLocals)
, valuesAtTail(numArguments, numLocals)
+ , intersectionOfPastValuesAtHead(numArguments, numLocals, AbstractValue::fullTop())
+ , intersectionOfCFAHasVisited(true)
, executionCount(executionCount)
{
}
@@ -64,6 +66,7 @@
variablesAtTail.ensureLocals(newNumLocals);
valuesAtHead.ensureLocals(newNumLocals);
valuesAtTail.ensureLocals(newNumLocals);
+ intersectionOfPastValuesAtHead.ensureLocals(newNumLocals, AbstractValue::fullTop());
}
bool BasicBlock::isInPhis(Node* node) const
Modified: branches/ftlopt/Source/_javascript_Core/dfg/DFGBasicBlock.h (170015 => 170016)
--- branches/ftlopt/Source/_javascript_Core/dfg/DFGBasicBlock.h 2014-06-16 17:41:40 UTC (rev 170015)
+++ branches/ftlopt/Source/_javascript_Core/dfg/DFGBasicBlock.h 2014-06-16 18:03:04 UTC (rev 170016)
@@ -134,6 +134,26 @@
Operands<AbstractValue> valuesAtHead;
Operands<AbstractValue> valuesAtTail;
+ // The intersection of assumptions we have made previously at the head of this block. Note
+ // that under normal circumstances, each time we run the CFA, we will get strictly more precise
+ // results. But we don't actually require this to be the case. It's fine for the CFA to loosen
+ // up for any odd reason. It's fine when this happens, because anything that the CFA proves
+ // must be true from that point forward, except if some registered watchpoint fires, in which
+ // case the code won't ever run. So, the CFA proving something less precise later on is just an
+ // outcome of the CFA being imperfect; the more precise thing that it had proved earlier is no
+ // less true.
+ //
+ // But for the purpose of OSR entry, we need to make sure that we remember what assumptions we
+ // had used for optimizing any given basic block. That's what this is for.
+ //
+ // It's interesting that we could use this to make the CFA more precise: all future CFAs could
+ // filter their results with this thing to sort of maintain maximal precision. Because we
+ // expect CFA to usually be monotonically more precise each time we run it to fixpoint, this
+ // would not be a productive optimization: it would make setting up a basic block more
+ // expensive and would only benefit bizarre pathological cases.
+ Operands<AbstractValue> intersectionOfPastValuesAtHead;
+ bool intersectionOfCFAHasVisited;
+
float executionCount;
// These fields are reserved for NaturalLoops.
Modified: branches/ftlopt/Source/_javascript_Core/dfg/DFGCFAPhase.cpp (170015 => 170016)
--- branches/ftlopt/Source/_javascript_Core/dfg/DFGCFAPhase.cpp 2014-06-16 17:41:40 UTC (rev 170015)
+++ branches/ftlopt/Source/_javascript_Core/dfg/DFGCFAPhase.cpp 2014-06-16 18:03:04 UTC (rev 170016)
@@ -79,6 +79,19 @@
performForwardCFA();
} while (m_changed);
+ if (m_graph.m_form != SSA) {
+ // Make sure we record the intersection of all proofs that we ever allowed the
+ // compiler to rely upon.
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+ block->intersectionOfCFAHasVisited &= block->cfaHasVisited;
+ for (unsigned i = block->intersectionOfPastValuesAtHead.size(); i--;)
+ block->intersectionOfPastValuesAtHead[i].filter(block->valuesAtHead[i]);
+ }
+ }
+
return true;
}
Modified: branches/ftlopt/Source/_javascript_Core/dfg/DFGConstantFoldingPhase.cpp (170015 => 170016)
--- branches/ftlopt/Source/_javascript_Core/dfg/DFGConstantFoldingPhase.cpp 2014-06-16 17:41:40 UTC (rev 170015)
+++ branches/ftlopt/Source/_javascript_Core/dfg/DFGConstantFoldingPhase.cpp 2014-06-16 18:03:04 UTC (rev 170016)
@@ -281,17 +281,6 @@
if (!*value)
continue;
- // Check if merging the abstract value of the constant into the abstract value
- // we've proven for this node wouldn't widen the proof. If it widens the proof
- // (i.e. says that the set contains more things in it than it previously did)
- // then we refuse to fold.
- AbstractValue oldValue = m_state.forNode(node);
- AbstractValue constantValue;
- constantValue.set(m_graph, *value, m_state.structureClobberState());
- constantValue.fixTypeForRepresentation(node);
- if (oldValue.merge(constantValue))
- continue;
-
NodeOrigin origin = node->origin;
AdjacencyList children = node->children;
Modified: branches/ftlopt/Source/_javascript_Core/dfg/DFGGraph.cpp (170015 => 170016)
--- branches/ftlopt/Source/_javascript_Core/dfg/DFGGraph.cpp 2014-06-16 17:41:40 UTC (rev 170015)
+++ branches/ftlopt/Source/_javascript_Core/dfg/DFGGraph.cpp 2014-06-16 18:03:04 UTC (rev 170016)
@@ -364,7 +364,7 @@
void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* block, PhiNodeDumpMode phiNodeDumpMode, DumpContext* context)
{
- out.print(prefix, "Block ", *block, " (", inContext(block->at(0)->origin.semantic, context), "):", block->isReachable ? "" : " (skipped)", block->isOSRTarget ? " (OSR target)" : "", block->cfaHasVisited ? "" : " (CFA-unreachable)", "\n");
+ out.print(prefix, "Block ", *block, " (", inContext(block->at(0)->origin.semantic, context), "):", block->isReachable ? "" : " (skipped)", block->isOSRTarget ? " (OSR target)" : "", "\n");
if (block->executionCount == block->executionCount)
out.print(prefix, " Execution count: ", block->executionCount, "\n");
out.print(prefix, " Predecessors:");
@@ -447,7 +447,12 @@
if (!block)
continue;
dumpBlockHeader(out, "", block, DumpAllPhis, context);
- out.print(" States: ", block->cfaStructureClobberStateAtHead, "\n");
+ out.print(" States: ", block->cfaStructureClobberStateAtHead);
+ if (!block->cfaHasVisited)
+ out.print(", CurrentlyCFAUnreachable");
+ if (!block->intersectionOfCFAHasVisited)
+ out.print(", CFAUnreachable");
+ out.print("\n");
switch (m_form) {
case LoadStore:
case ThreadedCPS: {
@@ -457,6 +462,12 @@
else
out.print("<empty>");
out.print("\n");
+ out.print(" Intersected Vars Before: ");
+ if (block->intersectionOfCFAHasVisited)
+ out.print(inContext(block->intersectionOfPastValuesAtHead, context));
+ else
+ out.print("<empty>");
+ out.print("\n");
out.print(" Var Links: ", block->variablesAtHead, "\n");
break;
}
@@ -473,7 +484,10 @@
dump(out, "", block->at(i), context);
lastNode = block->at(i);
}
- out.print(" States: ", block->cfaBranchDirection, ", ", block->cfaStructureClobberStateAtTail, "\n");
+ out.print(" States: ", block->cfaBranchDirection, ", ", block->cfaStructureClobberStateAtTail);
+ if (!block->cfaDidFinish)
+ out.print(", CFAInvalidated");
+ out.print("\n");
switch (m_form) {
case LoadStore:
case ThreadedCPS: {
Modified: branches/ftlopt/Source/_javascript_Core/dfg/DFGJITCompiler.h (170015 => 170016)
--- branches/ftlopt/Source/_javascript_Core/dfg/DFGJITCompiler.h 2014-06-16 17:41:40 UTC (rev 170015)
+++ branches/ftlopt/Source/_javascript_Core/dfg/DFGJITCompiler.h 2014-06-16 18:03:04 UTC (rev 170016)
@@ -270,12 +270,12 @@
void noticeOSREntry(BasicBlock& basicBlock, JITCompiler::Label blockHead, LinkBuffer& linkBuffer)
{
// OSR entry is not allowed into blocks deemed unreachable by control flow analysis.
- if (!basicBlock.cfaHasVisited)
+ if (!basicBlock.intersectionOfCFAHasVisited)
return;
OSREntryData* entry = m_jitCode->appendOSREntryData(basicBlock.bytecodeBegin, linkBuffer.offsetOf(blockHead));
- entry->m_expectedValues = basicBlock.valuesAtHead;
+ entry->m_expectedValues = basicBlock.intersectionOfPastValuesAtHead;
// Fix the expected values: in our protocol, a dead variable will have an expected
// value of (None, []). But the old JIT may stash some values there. So we really
Modified: branches/ftlopt/Source/_javascript_Core/dfg/DFGSpeculativeJIT.cpp (170015 => 170016)
--- branches/ftlopt/Source/_javascript_Core/dfg/DFGSpeculativeJIT.cpp 2014-06-16 17:41:40 UTC (rev 170015)
+++ branches/ftlopt/Source/_javascript_Core/dfg/DFGSpeculativeJIT.cpp 2014-06-16 18:03:04 UTC (rev 170016)
@@ -1353,7 +1353,7 @@
m_jit.blockHeads()[m_block->index] = m_jit.label();
- if (!m_block->cfaHasVisited) {
+ if (!m_block->intersectionOfCFAHasVisited) {
// Don't generate code for basic blocks that are unreachable according to CFA.
// But to be sure that nobody has generated a jump to this block, drop in a
// breakpoint here.
