- Revision
- 231660
- Author
- fpi...@apple.com
- Date
- 2018-05-10 14:31:49 -0700 (Thu, 10 May 2018)
Log Message
InPlaceAbstractState::beginBasicBlock shouldn't copy all m_variables every time
https://bugs.webkit.org/show_bug.cgi?id=185452
Reviewed by Michael Saboff.
We were spending a lot of time in beginBasicBlock() just copying the state of all variables
from the block head to InPlaceAbstractState::m_variables. It is necessary for
InPlaceAbstractState to have its own copy since we need to mutate it separately from
block->valuesAtHead. But most variables are untouched by most basic blocks, so this was a lot
of superfluous work.
This change adds a bitvector called m_activeVariables that tracks which variables have been
copied. We lazily copy the variables on first use. Variables that were never copied also have
a simplified merging path, which just needs to consider if the variable got clobbered between
head and tail.
This is a 1.5% speed-up on SunSpider-CompileTime and a 1.7% speed-up on V8Spider-CompileTime.
* bytecode/Operands.h:
(JSC::Operands::argumentIndex const):
(JSC::Operands::localIndex const):
(JSC::Operands::argument):
(JSC::Operands::argument const):
(JSC::Operands::local):
(JSC::Operands::local const):
(JSC::Operands::operandIndex const):
* dfg/DFGAbstractValue.h:
(JSC::DFG::AbstractValue::fastForwardFromTo):
* dfg/DFGCFAPhase.cpp:
(JSC::DFG::CFAPhase::performForwardCFA):
* dfg/DFGInPlaceAbstractState.cpp:
(JSC::DFG::InPlaceAbstractState::beginBasicBlock):
(JSC::DFG::InPlaceAbstractState::variablesForDebugging):
(JSC::DFG::InPlaceAbstractState::activateAllVariables):
(JSC::DFG::InPlaceAbstractState::endBasicBlock):
(JSC::DFG::InPlaceAbstractState::activateVariable):
(JSC::DFG::InPlaceAbstractState::mergeStateAtTail): Deleted.
* dfg/DFGInPlaceAbstractState.h:
(JSC::DFG::InPlaceAbstractState::variableAt):
(JSC::DFG::InPlaceAbstractState::operand):
(JSC::DFG::InPlaceAbstractState::local):
(JSC::DFG::InPlaceAbstractState::argument):
(JSC::DFG::InPlaceAbstractState::activateVariableIfNecessary):
(JSC::DFG::InPlaceAbstractState::variablesForDebugging): Deleted.
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (231659 => 231660)
--- trunk/Source/_javascript_Core/ChangeLog 2018-05-10 20:59:07 UTC (rev 231659)
+++ trunk/Source/_javascript_Core/ChangeLog 2018-05-10 21:31:49 UTC (rev 231660)
@@ -1,3 +1,50 @@
+2018-05-09 Filip Pizlo <fpi...@apple.com>
+
+ InPlaceAbstractState::beginBasicBlock shouldn't copy all m_variables every time
+ https://bugs.webkit.org/show_bug.cgi?id=185452
+
+ Reviewed by Michael Saboff.
+
+ We were spending a lot of time in beginBasicBlock() just copying the state of all variables
+ from the block head to InPlaceAbstractState::m_variables. It is necessary for
+ InPlaceAbstractState to have its own copy since we need to mutate it separately from
+ block->valuesAtHead. But most variables are untouched by most basic blocks, so this was a lot
+ of superfluous work.
+
+ This change adds a bitvector called m_activeVariables that tracks which variables have been
+ copied. We lazily copy the variables on first use. Variables that were never copied also have
+ a simplified merging path, which just needs to consider if the variable got clobbered between
+ head and tail.
+
+ This is a 1.5% speed-up on SunSpider-CompileTime and a 1.7% speed-up on V8Spider-CompileTime.
+
+ * bytecode/Operands.h:
+ (JSC::Operands::argumentIndex const):
+ (JSC::Operands::localIndex const):
+ (JSC::Operands::argument):
+ (JSC::Operands::argument const):
+ (JSC::Operands::local):
+ (JSC::Operands::local const):
+ (JSC::Operands::operandIndex const):
+ * dfg/DFGAbstractValue.h:
+ (JSC::DFG::AbstractValue::fastForwardFromTo):
+ * dfg/DFGCFAPhase.cpp:
+ (JSC::DFG::CFAPhase::performForwardCFA):
+ * dfg/DFGInPlaceAbstractState.cpp:
+ (JSC::DFG::InPlaceAbstractState::beginBasicBlock):
+ (JSC::DFG::InPlaceAbstractState::variablesForDebugging):
+ (JSC::DFG::InPlaceAbstractState::activateAllVariables):
+ (JSC::DFG::InPlaceAbstractState::endBasicBlock):
+ (JSC::DFG::InPlaceAbstractState::activateVariable):
+ (JSC::DFG::InPlaceAbstractState::mergeStateAtTail): Deleted.
+ * dfg/DFGInPlaceAbstractState.h:
+ (JSC::DFG::InPlaceAbstractState::variableAt):
+ (JSC::DFG::InPlaceAbstractState::operand):
+ (JSC::DFG::InPlaceAbstractState::local):
+ (JSC::DFG::InPlaceAbstractState::argument):
+ (JSC::DFG::InPlaceAbstractState::activateVariableIfNecessary):
+ (JSC::DFG::InPlaceAbstractState::variablesForDebugging): Deleted.
+
2018-05-09 Caio Lima <ticaiol...@gmail.com>
[ESNext][BigInt] Implement support for "==" operation
Modified: trunk/Source/_javascript_Core/bytecode/Operands.h (231659 => 231660)
--- trunk/Source/_javascript_Core/bytecode/Operands.h 2018-05-10 20:59:07 UTC (rev 231659)
+++ trunk/Source/_javascript_Core/bytecode/Operands.h 2018-05-10 21:31:49 UTC (rev 231660)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2011, 2012, 2013, 2015, 2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-2018 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -71,19 +71,28 @@
size_t numberOfArguments() const { return m_numArguments; }
size_t numberOfLocals() const { return m_values.size() - m_numArguments; }
- T& argument(size_t idx)
+ size_t argumentIndex(size_t idx) const
{
ASSERT(idx < m_numArguments);
- return m_values[idx];
+ return idx;
}
+
+ size_t localIndex(size_t idx) const
+ {
+ return m_numArguments + idx;
+ }
+
+ T& argument(size_t idx)
+ {
+ return m_values[argumentIndex(idx)];
+ }
const T& argument(size_t idx) const
{
- ASSERT(idx < m_numArguments);
- return m_values[idx];
+ return m_values[argumentIndex(idx)];
}
- T& local(size_t idx) { return m_values[m_numArguments + idx]; }
- const T& local(size_t idx) const { return m_values[m_numArguments + idx]; }
+ T& local(size_t idx) { return m_values[localIndex(idx)]; }
+ const T& local(size_t idx) const { return m_values[localIndex(idx)]; }
template<OperandKind operandKind>
size_t sizeFor() const
@@ -156,6 +165,18 @@
setLocal(idx, value);
}
+ size_t operandIndex(int operand) const
+ {
+ if (operandIsArgument(operand))
+ return argumentIndex(VirtualRegister(operand).toArgument());
+ return localIndex(VirtualRegister(operand).toLocal());
+ }
+
+ size_t operandIndex(VirtualRegister virtualRegister) const
+ {
+ return operandIndex(virtualRegister.offset());
+ }
+
T& operand(int operand)
{
if (operandIsArgument(operand))
Modified: trunk/Source/_javascript_Core/dfg/DFGAbstractValue.h (231659 => 231660)
--- trunk/Source/_javascript_Core/dfg/DFGAbstractValue.h 2018-05-10 20:59:07 UTC (rev 231659)
+++ trunk/Source/_javascript_Core/dfg/DFGAbstractValue.h 2018-05-10 21:31:49 UTC (rev 231660)
@@ -104,6 +104,22 @@
checkConsistency();
}
+ ALWAYS_INLINE void fastForwardFromTo(AbstractValueClobberEpoch oldEpoch, AbstractValueClobberEpoch newEpoch)
+ {
+ if (newEpoch == oldEpoch)
+ return;
+
+ if (!(m_type & SpecCell))
+ return;
+
+ if (newEpoch.clobberEpoch() != oldEpoch.clobberEpoch())
+ clobberStructures();
+ if (newEpoch.structureClobberState() == StructuresAreWatched)
+ m_structure.observeInvalidationPoint();
+
+ checkConsistency();
+ }
+
ALWAYS_INLINE void fastForwardTo(AbstractValueClobberEpoch newEpoch)
{
if (newEpoch == m_effectEpoch)
Modified: trunk/Source/_javascript_Core/dfg/DFGCFAPhase.cpp (231659 => 231660)
--- trunk/Source/_javascript_Core/dfg/DFGCFAPhase.cpp 2018-05-10 20:59:07 UTC (rev 231659)
+++ trunk/Source/_javascript_Core/dfg/DFGCFAPhase.cpp 2018-05-10 21:31:49 UTC (rev 231660)
@@ -203,7 +203,7 @@
{
++m_count;
if (m_verbose)
- dataLogF("CFA [%u]\n", ++m_count);
+ dataLogF("CFA [%u]\n", m_count);
for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
performBlockCFA(m_graph.block(blockIndex));
Modified: trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp (231659 => 231660)
--- trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp 2018-05-10 20:59:07 UTC (rev 231659)
+++ trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp 2018-05-10 21:31:49 UTC (rev 231660)
@@ -54,8 +54,6 @@
void InPlaceAbstractState::beginBasicBlock(BasicBlock* basicBlock)
{
- // This function is ~1.6-2% of execution time.
-
ASSERT(!m_block);
ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
@@ -62,23 +60,19 @@
ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
- m_abstractValues.resize(); // This part is ~0.1-0.4% of execution time.
+ m_abstractValues.resize();
AbstractValueClobberEpoch epoch = AbstractValueClobberEpoch::first(basicBlock->cfaStructureClobberStateAtHead);
+ m_epochAtHead = epoch;
m_effectEpoch = epoch;
- // This loop is 0.9-1.2% of execution time.
- // FIXME: Lazily populate m_variables when GetLocal/SetLocal happens. Apply the same idea to
- // merging. Alternatively, we could just use liveness here.
- // https://bugs.webkit.org/show_bug.cgi?id=185452
- for (size_t i = m_variables.size(); i--;) {
- AbstractValue& value = m_variables[i];
- value = basicBlock->valuesAtHead[i];
- value.m_effectEpoch = epoch;
- }
+ m_block = basicBlock;
+
+ m_activeVariables.clearRange(0, std::min(m_variables.size(), m_activeVariables.size()));
+ if (m_variables.size() > m_activeVariables.size())
+ m_activeVariables.resize(m_variables.size());
if (m_graph.m_form == SSA) {
- // This loop is 0.05-0.17% of execution time.
for (NodeAbstractValuePair& entry : basicBlock->ssa->valuesAtHead) {
if (entry.node.isStillValid()) {
AbstractValue& value = m_abstractValues.at(entry.node);
@@ -89,7 +83,6 @@
}
basicBlock->cfaShouldRevisit = false;
basicBlock->cfaHasVisited = true;
- m_block = basicBlock;
m_isValid = true;
m_foundConstants = false;
m_branchDirection = InvalidBranchDirection;
@@ -104,6 +97,18 @@
values.uncheckedAppend(NodeAbstractValuePair { node, AbstractValue() });
}
+Operands<AbstractValue>& InPlaceAbstractState::variablesForDebugging()
+{
+ activateAllVariables();
+ return m_variables;
+}
+
+void InPlaceAbstractState::activateAllVariables()
+{
+ for (size_t i = m_variables.size(); i--;)
+ activateVariableIfNecessary(i);
+}
+
void InPlaceAbstractState::initialize()
{
for (BasicBlock* entrypoint : m_graph.m_roots) {
@@ -206,25 +211,67 @@
return false;
}
+ AbstractValueClobberEpoch epochAtHead = m_epochAtHead;
+ AbstractValueClobberEpoch currentEpoch = m_effectEpoch;
+
block->cfaStructureClobberStateAtTail = m_structureClobberState;
-
+
switch (m_graph.m_form) {
case ThreadedCPS: {
- for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
- AbstractValue& destination = block->valuesAtTail.argument(argument);
- mergeStateAtTail(destination, this->argument(argument), block->variablesAtTail.argument(argument));
+ ASSERT(block->variablesAtTail.size() == block->valuesAtTail.size());
+ ASSERT(block->variablesAtTail.size() == m_variables.size());
+ for (size_t index = m_variables.size(); index--;) {
+ Node* node = block->variablesAtTail[index];
+ if (!node)
+ continue;
+ AbstractValue& destination = block->valuesAtTail[index];
+
+ if (!m_activeVariables[index]) {
+ destination = block->valuesAtHead[index];
+ destination.fastForwardFromTo(epochAtHead, currentEpoch);
+ continue;
+ }
+
+ switch (node->op()) {
+ case Phi:
+ case SetArgument:
+ case PhantomLocal:
+ case Flush:
+ // The block transfers the value from head to tail.
+ destination = variableAt(index);
+ break;
+
+ case GetLocal:
+ // The block refines the value with additional speculations.
+ destination = forNode(node);
+ break;
+
+ case SetLocal:
+ // The block sets the variable, and potentially refines it, both
+ // before and after setting it.
+ destination = forNode(node->child1());
+ break;
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ break;
+ }
}
-
- for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
- AbstractValue& destination = block->valuesAtTail.local(local);
- mergeStateAtTail(destination, this->local(local), block->variablesAtTail.local(local));
- }
break;
}
case SSA: {
- for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
+ for (size_t i = 0; i < block->valuesAtTail.size(); ++i) {
+ AbstractValue& destination = block->valuesAtTail[i];
+
+ if (!m_activeVariables[i]) {
+ destination = block->valuesAtHead[i];
+ destination.fastForwardFromTo(epochAtHead, currentEpoch);
+ continue;
+ }
+
block->valuesAtTail[i] = variableAt(i);
+ }
for (NodeAbstractValuePair& valueAtTail : block->ssa->valuesAtTail)
valueAtTail.value = forNode(valueAtTail.node);
@@ -248,40 +295,12 @@
m_structureClobberState = StructuresAreWatched;
}
-void InPlaceAbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
+void InPlaceAbstractState::activateVariable(size_t variableIndex)
{
- if (!node)
- return;
-
- const AbstractValue* source = nullptr;
-
- switch (node->op()) {
- case Phi:
- case SetArgument:
- case PhantomLocal:
- case Flush:
- // The block transfers the value from head to tail.
- source = &inVariable;
- break;
-
- case GetLocal:
- // The block refines the value with additional speculations.
- source = &forNode(node);
- break;
-
- case SetLocal:
- // The block sets the variable, and potentially refines it, both
- // before and after setting it.
- source = &forNode(node->child1());
- if (node->variableAccessData()->flushFormat() == FlushedDouble)
- RELEASE_ASSERT(!(source->m_type & ~SpecFullDouble));
- break;
-
- default:
- RELEASE_ASSERT_NOT_REACHED();
- break;
- }
- destination = *source;
+ AbstractValue& value = m_variables[variableIndex];
+ value = m_block->valuesAtHead[variableIndex];
+ value.m_effectEpoch = m_epochAtHead;
+ m_activeVariables[variableIndex] = true;
}
bool InPlaceAbstractState::merge(BasicBlock* from, BasicBlock* to)
Modified: trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h (231659 => 231660)
--- trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h 2018-05-10 20:59:07 UTC (rev 231659)
+++ trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h 2018-05-10 21:31:49 UTC (rev 231660)
@@ -156,16 +156,34 @@
makeHeapTopForNode(edge.node());
}
- Operands<AbstractValue>& variablesForDebugging() { return m_variables; }
+ Operands<AbstractValue>& variablesForDebugging();
unsigned numberOfArguments() const { return m_variables.numberOfArguments(); }
unsigned numberOfLocals() const { return m_variables.numberOfLocals(); }
- AbstractValue& operand(int operand) { return fastForward(m_variables.operand(operand)); }
- AbstractValue& operand(VirtualRegister operand) { return fastForward(m_variables.operand(operand)); }
- AbstractValue& local(size_t index) { return fastForward(m_variables.local(index)); }
- AbstractValue& argument(size_t index) { return fastForward(m_variables.argument(index)); }
- AbstractValue& variableAt(size_t index) { return fastForward(m_variables[index]); }
+ AbstractValue& variableAt(size_t index)
+ {
+ activateVariableIfNecessary(index);
+ return fastForward(m_variables[index]);
+ }
+
+ AbstractValue& operand(int operand)
+ {
+ return variableAt(m_variables.operandIndex(operand));
+ }
+
+ AbstractValue& operand(VirtualRegister operand) { return this->operand(operand.offset()); }
+
+ AbstractValue& local(size_t index)
+ {
+ return variableAt(m_variables.localIndex(index));
+ }
+
+ AbstractValue& argument(size_t index)
+ {
+ return variableAt(m_variables.argumentIndex(index));
+ }
+
// Call this before beginning CFA to initialize the abstract values of
// arguments, and to indicate which blocks should be listed for CFA
// execution.
@@ -247,8 +265,15 @@
}
private:
- void mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node*);
-
+ ALWAYS_INLINE void activateVariableIfNecessary(size_t variableIndex)
+ {
+ if (!m_activeVariables[variableIndex])
+ activateVariable(variableIndex);
+ }
+
+ void activateVariable(size_t variableIndex);
+ void activateAllVariables();
+
static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode);
Graph& m_graph;
@@ -255,6 +280,7 @@
FlowMap<AbstractValue>& m_abstractValues;
Operands<AbstractValue> m_variables;
+ FastBitVector m_activeVariables;
BasicBlock* m_block;
bool m_foundConstants;
@@ -262,6 +288,7 @@
bool m_isValid;
AbstractInterpreterClobberState m_clobberState;
StructureClobberState m_structureClobberState;
+ AbstractValueClobberEpoch m_epochAtHead;
AbstractValueClobberEpoch m_effectEpoch;
BranchDirection m_branchDirection; // This is only set for blocks that end in Branch and that execute to completion (i.e. m_isValid == true).
