- Revision
- 225893
- Author
- fpi...@apple.com
- Date
- 2017-12-13 22:04:51 -0800 (Wed, 13 Dec 2017)
Log Message
Octane/richards regressed by a whopping 20% because eliminateCommonSubexpressions has a weird fixpoint requirement
https://bugs.webkit.org/show_bug.cgi?id=180783
Reviewed by Saam Barati.
This fixes the regression by fixpointing CSE. We need to fixpoint CSE because of this case:
BB#1:
a: Load(@x)
b: Load(@x)
c: Load(@b)
BB#2:
d: Load(@b)
BB#3:
e: Load(@b)
Lets assume that #3 loops around to #2, so to eliminate @d, we need to prove that it's redundant
with both @c and @e. The problem is that by the time we get to @d, the CSE state will look like
this:
BB#1:
a: Load(@x)
b: Load(@x)
c: Load(@a)
memoryAtTail: {@x=>@a, @a=>@c}
BB#2:
d: Load(@a) [sic]
memoryAtTail: {@b=>@d}
BB#3:
e: Load(@b)
memoryAtTail: {@b=>@e} [sic]
Note that #3's atTail map is keyed on @b, which was the old (no longer canonical) version of @a.
But @d's children were already substituted, so it refers to @a. Since @a is not in #3's atTail
map, we don't find it and leave the redundancy.
I think that the cleanest solution is to fixpoint. CSE is pretty cheap, so hopefully we can afford
this. It fixes the richards regression, since richards is super dependent on B3 CSE.
* b3/B3EliminateCommonSubexpressions.cpp: Logging.
* b3/B3Generate.cpp:
(JSC::B3::generateToAir): Fix the bug.
* b3/air/AirReportUsedRegisters.cpp:
(JSC::B3::Air::reportUsedRegisters): Logging.
* dfg/DFGByteCodeParser.cpp:
* dfg/DFGSSAConversionPhase.cpp:
(JSC::DFG::SSAConversionPhase::run): Don't generate EntrySwitch if we don't need it (makes IR easier to read).
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::lower): Don't generate EntrySwitch if we don't need it (makes IR easier to read).
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (225892 => 225893)
--- trunk/Source/_javascript_Core/ChangeLog 2017-12-14 04:47:34 UTC (rev 225892)
+++ trunk/Source/_javascript_Core/ChangeLog 2017-12-14 06:04:51 UTC (rev 225893)
@@ -1,3 +1,55 @@
+2017-12-13 Filip Pizlo <fpi...@apple.com>
+
+ Octane/richards regressed by a whopping 20% because eliminateCommonSubexpressions has a weird fixpoint requirement
+ https://bugs.webkit.org/show_bug.cgi?id=180783
+
+ Reviewed by Saam Barati.
+
+ This fixes the regression by fixpointing CSE. We need to fixpoint CSE because of this case:
+
+ BB#1:
+ a: Load(@x)
+ b: Load(@x)
+ c: Load(@b)
+ BB#2:
+ d: Load(@b)
+ BB#3:
+ e: Load(@b)
+
+ Lets assume that #3 loops around to #2, so to eliminate @d, we need to prove that it's redundant
+ with both @c and @e. The problem is that by the time we get to @d, the CSE state will look like
+ this:
+
+ BB#1:
+ a: Load(@x)
+ b: Load(@x)
+ c: Load(@a)
+ memoryAtTail: {@x=>@a, @a=>@c}
+ BB#2:
+ d: Load(@a) [sic]
+ memoryAtTail: {@b=>@d}
+ BB#3:
+ e: Load(@b)
+ memoryAtTail: {@b=>@e} [sic]
+
+ Note that #3's atTail map is keyed on @b, which was the old (no longer canonical) version of @a.
+ But @d's children were already substituted, so it refers to @a. Since @a is not in #3's atTail
+ map, we don't find it and leave the redundancy.
+
+ I think that the cleanest solution is to fixpoint. CSE is pretty cheap, so hopefully we can afford
+ this. It fixes the richards regression, since richards is super dependent on B3 CSE.
+
+ * b3/B3EliminateCommonSubexpressions.cpp: Logging.
+ * b3/B3Generate.cpp:
+ (JSC::B3::generateToAir): Fix the bug.
+ * b3/air/AirReportUsedRegisters.cpp:
+ (JSC::B3::Air::reportUsedRegisters): Logging.
+ * dfg/DFGByteCodeParser.cpp:
+ * dfg/DFGSSAConversionPhase.cpp:
+ (JSC::DFG::SSAConversionPhase::run): Don't generate EntrySwitch if we don't need it (makes IR easier to read).
+ * ftl/FTLLowerDFGToB3.cpp:
+ (JSC::FTL::DFG::LowerDFGToB3::lower): Don't generate EntrySwitch if we don't need it (makes IR easier to read).
+
2017-12-13 Joseph Pecoraro <pecor...@apple.com>
REGRESSION: Web Inspector: Opening inspector crashes page if there are empty resources
Modified: trunk/Source/_javascript_Core/b3/B3EliminateCommonSubexpressions.cpp (225892 => 225893)
--- trunk/Source/_javascript_Core/b3/B3EliminateCommonSubexpressions.cpp 2017-12-14 04:47:34 UTC (rev 225892)
+++ trunk/Source/_javascript_Core/b3/B3EliminateCommonSubexpressions.cpp 2017-12-14 06:04:51 UTC (rev 225893)
@@ -106,8 +106,14 @@
template<typename Functor>
MemoryValue* find(Value* ptr, const Functor& functor)
{
+ if (B3EliminateCommonSubexpressionsInternal::verbose)
+ dataLog(" Looking for ", pointerDump(ptr), " in ", *this, "\n");
if (Matches* matches = find(ptr)) {
+ if (B3EliminateCommonSubexpressionsInternal::verbose)
+ dataLog(" Matches: ", pointerListDump(*matches), "\n");
for (Value* candidateValue : *matches) {
+ if (B3EliminateCommonSubexpressionsInternal::verbose)
+ dataLog(" Having candidate: ", pointerDump(candidateValue), "\n");
if (MemoryValue* candidateMemory = candidateValue->as<MemoryValue>()) {
if (functor(candidateMemory))
return candidateMemory;
@@ -405,15 +411,26 @@
handleMemoryValue(
ptr, range,
[&] (MemoryValue* candidate) -> bool {
+ if (B3EliminateCommonSubexpressionsInternal::verbose)
+ dataLog(" Consdering ", pointerDump(candidate), "\n");
if (candidate->offset() != offset)
return false;
-
+
+ if (B3EliminateCommonSubexpressionsInternal::verbose)
+ dataLog(" offset ok.\n");
+
if (candidate->opcode() == Load && candidate->type() == type)
return true;
+ if (B3EliminateCommonSubexpressionsInternal::verbose)
+ dataLog(" not a load with ok type.\n");
+
if (candidate->opcode() == Store && candidate->child(0)->type() == type)
return true;
+ if (B3EliminateCommonSubexpressionsInternal::verbose)
+ dataLog(" not a store with ok type.\n");
+
return false;
});
break;
@@ -617,8 +634,10 @@
template<typename Filter>
MemoryMatches findMemoryValue(Value* ptr, HeapRange range, const Filter& filter)
{
- if (B3EliminateCommonSubexpressionsInternal::verbose)
+ if (B3EliminateCommonSubexpressionsInternal::verbose) {
dataLog(*m_value, ": looking backward for ", *ptr, "...\n");
+ dataLog(" Full value: ", deepDump(m_value), "\n");
+ }
if (m_value->as<MemoryValue>()->hasFence()) {
if (B3EliminateCommonSubexpressionsInternal::verbose)
@@ -650,6 +669,8 @@
ImpureBlockData& data = ""
MemoryValue* match = data.memoryValuesAtTail.find(ptr, filter);
+ if (B3EliminateCommonSubexpressionsInternal::verbose)
+ dataLog(" Consdering match: ", pointerDump(match), "\n");
if (match && match != m_value) {
if (B3EliminateCommonSubexpressionsInternal::verbose)
dataLog(" Found match: ", *match, "\n");
Modified: trunk/Source/_javascript_Core/b3/B3Generate.cpp (225892 => 225893)
--- trunk/Source/_javascript_Core/b3/B3Generate.cpp 2017-12-14 04:47:34 UTC (rev 225892)
+++ trunk/Source/_javascript_Core/b3/B3Generate.cpp 2017-12-14 06:04:51 UTC (rev 225893)
@@ -85,7 +85,8 @@
reduceDoubleToFloat(procedure);
reduceStrength(procedure);
hoistLoopInvariantValues(procedure);
- eliminateCommonSubexpressions(procedure);
+ if (eliminateCommonSubexpressions(procedure))
+ eliminateCommonSubexpressions(procedure);
inferSwitches(procedure);
duplicateTails(procedure);
fixSSA(procedure);
Modified: trunk/Source/_javascript_Core/b3/air/AirReportUsedRegisters.cpp (225892 => 225893)
--- trunk/Source/_javascript_Core/b3/air/AirReportUsedRegisters.cpp 2017-12-14 04:47:34 UTC (rev 225892)
+++ trunk/Source/_javascript_Core/b3/air/AirReportUsedRegisters.cpp 2017-12-14 06:04:51 UTC (rev 225893)
@@ -39,14 +39,25 @@
void reportUsedRegisters(Code& code)
{
PhaseScope phaseScope(code, "reportUsedRegisters");
+
+ static constexpr bool verbose = false;
+
+ if (verbose)
+ dataLog("Doing reportUsedRegisters on:\n", code);
RegLiveness liveness(code);
for (BasicBlock* block : code) {
+ if (verbose)
+ dataLog("Looking at: ", *block, "\n");
+
RegLiveness::LocalCalc localCalc(liveness, block);
for (unsigned instIndex = block->size(); instIndex--;) {
Inst& inst = block->at(instIndex);
+
+ if (verbose)
+ dataLog(" Looking at: ", inst, "\n");
// Kill dead assignments to registers. For simplicity we say that a store is killable if
// it has only late defs and those late defs are to registers that are dead right now.
@@ -55,6 +66,8 @@
inst.forEachArg(
[&] (Arg& arg, Arg::Role role, Bank, Width) {
if (Arg::isEarlyDef(role)) {
+ if (verbose)
+ dataLog(" Cannot delete because of ", arg, "\n");
canDelete = false;
return;
}
@@ -61,10 +74,14 @@
if (!Arg::isLateDef(role))
return;
if (!arg.isReg()) {
+ if (verbose)
+ dataLog(" Cannot delete because arg is not reg: ", arg, "\n");
canDelete = false;
return;
}
if (localCalc.isLive(arg.reg())) {
+ if (verbose)
+ dataLog(" Cannot delete because arg is live: ", arg, "\n");
canDelete = false;
return;
}
@@ -87,6 +104,9 @@
return !inst;
});
}
+
+ if (verbose)
+ dataLog("After reportUsedRegisters:\n", code);
}
} } } // namespace JSC::B3::Air
Modified: trunk/Source/_javascript_Core/dfg/DFGSSAConversionPhase.cpp (225892 => 225893)
--- trunk/Source/_javascript_Core/dfg/DFGSSAConversionPhase.cpp 2017-12-14 04:47:34 UTC (rev 225892)
+++ trunk/Source/_javascript_Core/dfg/DFGSSAConversionPhase.cpp 2017-12-14 06:04:51 UTC (rev 225893)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2017 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -37,6 +37,14 @@
#include "DFGVariableAccessDataDump.h"
#include "JSCInlines.h"
+#undef RELEASE_ASSERT
+#define RELEASE_ASSERT(assertion) do { \
+ if (!(assertion)) { \
+ WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
+ CRASH(); \
+ } \
+} while (0)
+
namespace JSC { namespace DFG {
class SSAConversionPhase : public Phase {
@@ -60,9 +68,22 @@
HashMap<unsigned, BasicBlock*, WTF::IntHash<unsigned>, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> entrypointIndexToArgumentsBlock;
- {
- m_graph.m_numberOfEntrypoints = m_graph.m_roots.size();
+ m_graph.m_numberOfEntrypoints = m_graph.m_roots.size();
+ m_graph.m_argumentFormats.resize(m_graph.m_numberOfEntrypoints);
+ for (unsigned entrypointIndex = 0; entrypointIndex < m_graph.m_numberOfEntrypoints; ++entrypointIndex) {
+ BasicBlock* oldRoot = m_graph.m_roots[entrypointIndex];
+ entrypointIndexToArgumentsBlock.add(entrypointIndex, oldRoot);
+
+ NodeOrigin origin = oldRoot->at(0)->origin;
+ m_insertionSet.insertNode(
+ 0, SpecNone, InitializeEntrypointArguments, origin, OpInfo(entrypointIndex));
+ m_insertionSet.insertNode(
+ 0, SpecNone, ExitOK, origin);
+ m_insertionSet.execute(oldRoot);
+ }
+
+ if (m_graph.m_numberOfEntrypoints > 1) {
BlockInsertionSet blockInsertionSet(m_graph);
BasicBlock* newRoot = blockInsertionSet.insert(0, 1.0f);
@@ -69,7 +90,6 @@
EntrySwitchData* entrySwitchData = m_graph.m_entrySwitchData.add();
for (unsigned entrypointIndex = 0; entrypointIndex < m_graph.m_numberOfEntrypoints; ++entrypointIndex) {
BasicBlock* oldRoot = m_graph.m_roots[entrypointIndex];
- entrypointIndexToArgumentsBlock.add(entrypointIndex, oldRoot);
entrySwitchData->cases.append(oldRoot);
ASSERT(oldRoot->predecessors.isEmpty());
@@ -79,19 +99,10 @@
ASSERT(!!entrypointIndex);
m_graph.m_entrypointIndexToCatchBytecodeOffset.add(entrypointIndex, oldRoot->bytecodeBegin);
}
-
- NodeOrigin origin = oldRoot->at(0)->origin;
- m_insertionSet.insertNode(
- 0, SpecNone, InitializeEntrypointArguments, origin, OpInfo(entrypointIndex));
- m_insertionSet.insertNode(
- 0, SpecNone, ExitOK, origin);
- m_insertionSet.execute(oldRoot);
}
RELEASE_ASSERT(entrySwitchData->cases[0] == m_graph.block(0)); // We strongly assume the normal call entrypoint is the first item in the list.
- m_graph.m_argumentFormats.resize(m_graph.m_numberOfEntrypoints);
-
const bool exitOK = false;
NodeOrigin origin { CodeOrigin(0), CodeOrigin(0), exitOK };
newRoot->appendNode(
@@ -102,7 +113,7 @@
blockInsertionSet.execute();
}
-
+
SSACalculator calculator(m_graph);
m_graph.ensureSSADominators();
Modified: trunk/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp (225892 => 225893)
--- trunk/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp 2017-12-14 04:47:34 UTC (rev 225892)
+++ trunk/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp 2017-12-14 06:04:51 UTC (rev 225893)
@@ -93,6 +93,14 @@
#include <wtf/Box.h>
#include <wtf/Gigacage.h>
+#undef RELEASE_ASSERT
+#define RELEASE_ASSERT(assertion) do { \
+ if (!(assertion)) { \
+ WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
+ CRASH(); \
+ } \
+} while (0)
+
namespace JSC { namespace FTL {
using namespace B3;
@@ -187,8 +195,10 @@
// We use prologue frequency for all of the initialization code.
m_out.setFrequency(1);
+ bool hasMultipleEntrypoints = m_graph.m_numberOfEntrypoints > 1;
+
LBasicBlock prologue = m_out.newBlock();
- LBasicBlock callEntrypointArgumentSpeculations = m_out.newBlock();
+ LBasicBlock callEntrypointArgumentSpeculations = hasMultipleEntrypoints ? m_out.newBlock() : nullptr;
m_handleExceptions = m_out.newBlock();
for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
@@ -202,7 +212,7 @@
// Back to prologue frequency for any bocks that get sneakily created in the initialization code.
m_out.setFrequency(1);
- m_out.appendTo(prologue, callEntrypointArgumentSpeculations);
+ m_out.appendTo(prologue, hasMultipleEntrypoints ? callEntrypointArgumentSpeculations : m_handleExceptions);
m_out.initializeConstants(m_proc, prologue);
createPhiVariables();
@@ -287,19 +297,21 @@
LBasicBlock firstDFGBasicBlock = lowBlock(m_graph.block(0));
{
- Vector<LBasicBlock> successors(m_graph.m_numberOfEntrypoints);
- successors[0] = callEntrypointArgumentSpeculations;
- for (unsigned i = 1; i < m_graph.m_numberOfEntrypoints; ++i) {
- // Currently, the only other entrypoint is an op_catch entrypoint.
- // We do OSR entry at op_catch, and we prove argument formats before
- // jumping to FTL code, so we don't need to check argument types here
- // for these entrypoints.
- successors[i] = firstDFGBasicBlock;
+ if (hasMultipleEntrypoints) {
+ Vector<LBasicBlock> successors(m_graph.m_numberOfEntrypoints);
+ successors[0] = callEntrypointArgumentSpeculations;
+ for (unsigned i = 1; i < m_graph.m_numberOfEntrypoints; ++i) {
+ // Currently, the only other entrypoint is an op_catch entrypoint.
+ // We do OSR entry at op_catch, and we prove argument formats before
+ // jumping to FTL code, so we don't need to check argument types here
+ // for these entrypoints.
+ successors[i] = firstDFGBasicBlock;
+ }
+
+ m_out.entrySwitch(successors);
+ m_out.appendTo(callEntrypointArgumentSpeculations, m_handleExceptions);
}
- m_out.entrySwitch(successors);
- m_out.appendTo(callEntrypointArgumentSpeculations, m_handleExceptions);
-
m_node = nullptr;
m_origin = NodeOrigin(CodeOrigin(0), CodeOrigin(0), true);