- Revision
- 231204
- Author
- fpi...@apple.com
- Date
- 2018-05-01 12:55:59 -0700 (Tue, 01 May 2018)
Log Message
B3::demoteValues should be able to handle patchpoint terminals
https://bugs.webkit.org/show_bug.cgi?id=185151
Reviewed by Saam Barati.
If we try to demote a patchpoint terminal then prior to this change we would append a Set to
the basic block that the patchpoint terminated. That's wrong because then the terminal is no
longer the last thing in the block.
Air encounters this problem in spilling and solves it by doing a fixup afterwards. We can't
really do that because demotion happens as a prerequisite to other transformations.
One solution might have been to make demoteValues insert a basic block whenever it encounters
this problem. But that would break clients that do CFG analysis before demoteValues and use
the results of the CFG analysis after demoteValues. Taildup does this. Fortunately, taildup
also runs breakCriticalEdges. Probably anyone using demoteValues will use breakCriticalEdges,
so it's not bad to introduce that requirement.
So, this patch solves the problem by ensuring that breakCriticalEdges treats any patchpoint
terminal as if it had multiple successors. This means that a patchpoint terminal's successors
will only have it as their predecessor. Then, demoteValues just prepends the Set to the
successors of the patchpoint terminal.
This was probably asymptomatic. It's hard to write a JS test that triggers this, so I added
a unit test in testb3.
* b3/B3BreakCriticalEdges.cpp:
(JSC::B3::breakCriticalEdges):
* b3/B3BreakCriticalEdges.h:
* b3/B3FixSSA.cpp:
(JSC::B3::demoteValues):
(JSC::B3::fixSSA):
* b3/B3FixSSA.h:
* b3/B3Value.cpp:
(JSC::B3::Value::foldIdentity const):
(JSC::B3::Value::performSubstitution):
* b3/B3Value.h:
* b3/testb3.cpp:
(JSC::B3::testDemotePatchpointTerminal):
(JSC::B3::run):
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (231203 => 231204)
--- trunk/Source/_javascript_Core/ChangeLog 2018-05-01 19:45:34 UTC (rev 231203)
+++ trunk/Source/_javascript_Core/ChangeLog 2018-05-01 19:55:59 UTC (rev 231204)
@@ -1,3 +1,46 @@
+2018-04-30 Filip Pizlo <fpi...@apple.com>
+
+ B3::demoteValues should be able to handle patchpoint terminals
+ https://bugs.webkit.org/show_bug.cgi?id=185151
+
+ Reviewed by Saam Barati.
+
+ If we try to demote a patchpoint terminal then prior to this change we would append a Set to
+ the basic block that the patchpoint terminated. That's wrong because then the terminal is no
+ longer the last thing in the block.
+
+ Air encounters this problem in spilling and solves it by doing a fixup afterwards. We can't
+ really do that because demotion happens as a prerequisite to other transformations.
+
+ One solution might have been to make demoteValues insert a basic block whenever it encounters
+ this problem. But that would break clients that do CFG analysis before demoteValues and use
+ the results of the CFG analysis after demoteValues. Taildup does this. Fortunately, taildup
+ also runs breakCriticalEdges. Probably anyone using demoteValues will use breakCriticalEdges,
+ so it's not bad to introduce that requirement.
+
+ So, this patch solves the problem by ensuring that breakCriticalEdges treats any patchpoint
+ terminal as if it had multiple successors. This means that a patchpoint terminal's successors
+ will only have it as their predecessor. Then, demoteValues just prepends the Set to the
+ successors of the patchpoint terminal.
+
+ This was probably asymptomatic. It's hard to write a JS test that triggers this, so I added
+ a unit test in testb3.
+
+ * b3/B3BreakCriticalEdges.cpp:
+ (JSC::B3::breakCriticalEdges):
+ * b3/B3BreakCriticalEdges.h:
+ * b3/B3FixSSA.cpp:
+ (JSC::B3::demoteValues):
+ (JSC::B3::fixSSA):
+ * b3/B3FixSSA.h:
+ * b3/B3Value.cpp:
+ (JSC::B3::Value::foldIdentity const):
+ (JSC::B3::Value::performSubstitution):
+ * b3/B3Value.h:
+ * b3/testb3.cpp:
+ (JSC::B3::testDemotePatchpointTerminal):
+ (JSC::B3::run):
+
2018-05-01 Robin Morisset <rmoris...@apple.com>
Use CheckedArithmetic for length computation in JSArray::unshiftCountWithAnyIndexingType
Modified: trunk/Source/_javascript_Core/b3/B3BreakCriticalEdges.cpp (231203 => 231204)
--- trunk/Source/_javascript_Core/b3/B3BreakCriticalEdges.cpp 2018-05-01 19:45:34 UTC (rev 231203)
+++ trunk/Source/_javascript_Core/b3/B3BreakCriticalEdges.cpp 2018-05-01 19:55:59 UTC (rev 231204)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2016-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
@@ -40,7 +40,10 @@
BlockInsertionSet insertionSet(proc);
for (BasicBlock* block : proc) {
- if (block->numSuccessors() <= 1)
+ // Non-void terminals that are the moral equivalent of jumps trigger critical edge breaking
+ // because of fixSSA's demoteValues.
+ if (block->numSuccessors() <= 1
+ && block->last()->type() == Void)
continue;
for (BasicBlock*& successor : block->successorBlocks()) {
@@ -57,8 +60,8 @@
}
}
- insertionSet.execute();
- proc.invalidateCFG();
+ if (insertionSet.execute())
+ proc.invalidateCFG();
}
} } // namespace JSC::B3
Modified: trunk/Source/_javascript_Core/b3/B3BreakCriticalEdges.h (231203 => 231204)
--- trunk/Source/_javascript_Core/b3/B3BreakCriticalEdges.h 2018-05-01 19:45:34 UTC (rev 231203)
+++ trunk/Source/_javascript_Core/b3/B3BreakCriticalEdges.h 2018-05-01 19:55:59 UTC (rev 231204)
@@ -31,7 +31,7 @@
class Procedure;
-void breakCriticalEdges(Procedure&);
+JS_EXPORT_PRIVATE void breakCriticalEdges(Procedure&);
} } // namespace JSC::B3
Modified: trunk/Source/_javascript_Core/b3/B3FixSSA.cpp (231203 => 231204)
--- trunk/Source/_javascript_Core/b3/B3FixSSA.cpp 2018-05-01 19:45:34 UTC (rev 231203)
+++ trunk/Source/_javascript_Core/b3/B3FixSSA.cpp 2018-05-01 19:55:59 UTC (rev 231204)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
+ * Copyright (C) 2016-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
@@ -172,6 +172,7 @@
TimingScope timingScope("fixSSA: convert");
InsertionSet insertionSet(proc);
IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
+ IndexSet<Value*> valuesToDelete;
for (BasicBlock* block : proc.blocksInPreOrder()) {
mapping.clear();
@@ -207,6 +208,7 @@
Variable* variable = variableValue->variable();
value->replaceWithIdentity(ensureMapping(variable, valueIndex, value->origin()));
+ valuesToDelete.add(value);
break;
}
@@ -240,12 +242,25 @@
}
insertionSet.insert<UpsilonValue>(
- upsilonInsertionPoint, upsilonOrigin, mappedValue, phi);
+ upsilonInsertionPoint, upsilonOrigin, mappedValue->foldIdentity(), phi);
}
}
insertionSet.execute(block);
}
+
+ // This is isn't strictly necessary, but it leaves the IR nice and tidy, which is particularly
+ // useful for phases that do size estimates.
+ for (BasicBlock* block : proc) {
+ block->values().removeAllMatching(
+ [&] (Value* value) -> bool {
+ if (!valuesToDelete.contains(value) && value->opcode() != Nop)
+ return false;
+
+ proc.deleteValue(value);
+ return true;
+ });
+ }
if (B3FixSSAInternal::verbose) {
dataLog("B3 after SSA conversion:\n");
@@ -285,6 +300,17 @@
// Change accesses to the values to accesses to the stack slots.
InsertionSet insertionSet(proc);
for (BasicBlock* block : proc) {
+ if (block->numPredecessors()) {
+ // Deal with terminals that produce values (i.e. patchpoint terminals, like the ones we
+ // generate for the allocation fast path).
+ Value* value = block->predecessor(0)->last();
+ Variable* variable = map.get(value);
+ if (variable) {
+ RELEASE_ASSERT(block->numPredecessors() == 1); // Critical edges better be broken.
+ insertionSet.insert<VariableValue>(0, Set, value->origin(), variable, value);
+ }
+ }
+
for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
Value* value = block->at(valueIndex);
@@ -312,8 +338,10 @@
}
if (Variable* variable = map.get(value)) {
- insertionSet.insert<VariableValue>(
- valueIndex + 1, Set, value->origin(), variable, value);
+ if (valueIndex + 1 < block->size()) {
+ insertionSet.insert<VariableValue>(
+ valueIndex + 1, Set, value->origin(), variable, value);
+ }
}
}
insertionSet.execute(block);
@@ -324,6 +352,9 @@
{
PhaseScope phaseScope(proc, "fixSSA");
+ if (proc.variables().isEmpty())
+ return false;
+
// Lots of variables have trivial local liveness. We can allocate those without any
// trouble.
fixSSALocally(proc);
@@ -336,7 +367,6 @@
if (proc.variables().isEmpty())
return false;
- // We know that we have variables to optimize, so do that now.
breakCriticalEdges(proc);
fixSSAGlobally(proc);
Modified: trunk/Source/_javascript_Core/b3/B3FixSSA.h (231203 => 231204)
--- trunk/Source/_javascript_Core/b3/B3FixSSA.h 2018-05-01 19:45:34 UTC (rev 231203)
+++ trunk/Source/_javascript_Core/b3/B3FixSSA.h 2018-05-01 19:55:59 UTC (rev 231204)
@@ -37,7 +37,7 @@
// Turns all mentions of the given values into accesses to variables. This is meant to be used
// from phases that don't like SSA for whatever reason.
-void demoteValues(Procedure&, const IndexSet<Value*>&);
+JS_EXPORT_PRIVATE void demoteValues(Procedure&, const IndexSet<Value*>&);
// This fixes SSA for you. Use this after you have done demoteValues() and you have performed
// whatever evil transformation you needed.
Modified: trunk/Source/_javascript_Core/b3/B3Value.cpp (231203 => 231204)
--- trunk/Source/_javascript_Core/b3/B3Value.cpp 2018-05-01 19:45:34 UTC (rev 231203)
+++ trunk/Source/_javascript_Core/b3/B3Value.cpp 2018-05-01 19:55:59 UTC (rev 231204)
@@ -778,13 +778,21 @@
}
}
+Value* Value::foldIdentity() const
+{
+ Value* current = const_cast<Value*>(this);
+ while (current->opcode() == Identity)
+ current = current->child(0);
+ return current;
+}
+
bool Value::performSubstitution()
{
bool result = false;
for (Value*& child : children()) {
- while (child->opcode() == Identity) {
+ if (child->opcode() == Identity) {
result = true;
- child = child->child(0);
+ child = child->foldIdentity();
}
}
return result;
Modified: trunk/Source/_javascript_Core/b3/B3Value.h (231203 => 231204)
--- trunk/Source/_javascript_Core/b3/B3Value.h 2018-05-01 19:45:34 UTC (rev 231203)
+++ trunk/Source/_javascript_Core/b3/B3Value.h 2018-05-01 19:55:59 UTC (rev 231204)
@@ -260,6 +260,8 @@
// empty ValueKey if this Value is impure. Note that an operation that returns Void could still
// have a non-empty ValueKey. This happens for example with Check operations.
ValueKey key() const;
+
+ Value* foldIdentity() const;
// Makes sure that none of the children are Identity's. If a child points to Identity, this will
// repoint it at the Identity's child. For simplicity, this will follow arbitrarily long chains
Modified: trunk/Source/_javascript_Core/b3/testb3.cpp (231203 => 231204)
--- trunk/Source/_javascript_Core/b3/testb3.cpp 2018-05-01 19:45:34 UTC (rev 231203)
+++ trunk/Source/_javascript_Core/b3/testb3.cpp 2018-05-01 19:55:59 UTC (rev 231204)
@@ -32,6 +32,7 @@
#include "B3ArgumentRegValue.h"
#include "B3AtomicValue.h"
#include "B3BasicBlockInlines.h"
+#include "B3BreakCriticalEdges.h"
#include "B3CCallValue.h"
#include "B3Compilation.h"
#include "B3Compile.h"
@@ -40,6 +41,7 @@
#include "B3ConstPtrValue.h"
#include "B3Effects.h"
#include "B3FenceValue.h"
+#include "B3FixSSA.h"
#include "B3Generate.h"
#include "B3LowerToAir.h"
#include "B3MathExtras.h"
@@ -69,6 +71,7 @@
#include <cmath>
#include <string>
#include <wtf/FastTLS.h>
+#include <wtf/IndexSet.h>
#include <wtf/ListDump.h>
#include <wtf/Lock.h>
#include <wtf/NumberOfCores.h>
@@ -16210,6 +16213,27 @@
fastFree(inputPtr);
}
+void testDemotePatchpointTerminal()
+{
+ Procedure proc;
+
+ BasicBlock* root = proc.addBlock();
+ BasicBlock* done = proc.addBlock();
+
+ PatchpointValue* patchpoint = root->appendNew<PatchpointValue>(proc, Int32, Origin());
+ patchpoint->effects.terminal = true;
+ root->setSuccessors(done);
+
+ done->appendNew<Value>(proc, Return, Origin(), patchpoint);
+
+ proc.resetReachability();
+ breakCriticalEdges(proc);
+ IndexSet<Value*> valuesToDemote;
+ valuesToDemote.add(patchpoint);
+ demoteValues(proc, valuesToDemote);
+ validate(proc);
+}
+
// Make sure the compiler does not try to optimize anything out.
NEVER_INLINE double zero()
{
@@ -17777,6 +17801,7 @@
RUN(testFloatEqualOrUnorderedDontFold());
RUN(testShuffleDoesntTrashCalleeSaves());
+ RUN(testDemotePatchpointTerminal());
if (isX86()) {
RUN(testBranchBitAndImmFusion(Identity, Int64, 1, Air::BranchTest32, Air::Arg::Tmp));
