Title: [193993] trunk/Source/_javascript_Core
- Revision
- 193993
- Author
- fpi...@apple.com
- Date
- 2015-12-11 16:17:24 -0800 (Fri, 11 Dec 2015)
Log Message
B3::reduceStrength should remove redundant Phi's
https://bugs.webkit.org/show_bug.cgi?id=152184
Reviewed by Benjamin Poulain.
This adds redundant Phi removal using Aycock and Horspools SSA simplification algorithm. This
is needed because even in simple asm.js code, we see a lot of CFG simplification that leaves
behind totally useless Phi's.
* b3/B3PhiChildren.cpp:
(JSC::B3::PhiChildren::PhiChildren):
* b3/B3PhiChildren.h:
(JSC::B3::PhiChildren::at):
(JSC::B3::PhiChildren::operator[]):
(JSC::B3::PhiChildren::phis):
* b3/B3ReduceStrength.cpp:
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (193992 => 193993)
--- trunk/Source/_javascript_Core/ChangeLog 2015-12-12 00:11:40 UTC (rev 193992)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-12-12 00:17:24 UTC (rev 193993)
@@ -1,3 +1,22 @@
+2015-12-11 Filip Pizlo <fpi...@apple.com>
+
+ B3::reduceStrength should remove redundant Phi's
+ https://bugs.webkit.org/show_bug.cgi?id=152184
+
+ Reviewed by Benjamin Poulain.
+
+ This adds redundant Phi removal using Aycock and Horspools SSA simplification algorithm. This
+ is needed because even in simple asm.js code, we see a lot of CFG simplification that leaves
+ behind totally useless Phi's.
+
+ * b3/B3PhiChildren.cpp:
+ (JSC::B3::PhiChildren::PhiChildren):
+ * b3/B3PhiChildren.h:
+ (JSC::B3::PhiChildren::at):
+ (JSC::B3::PhiChildren::operator[]):
+ (JSC::B3::PhiChildren::phis):
+ * b3/B3ReduceStrength.cpp:
+
2015-12-11 Benjamin Poulain <benja...@webkit.org>
[JSC] Add an implementation of pow() taking an integer exponent to B3
Modified: trunk/Source/_javascript_Core/b3/B3PhiChildren.cpp (193992 => 193993)
--- trunk/Source/_javascript_Core/b3/B3PhiChildren.cpp 2015-12-12 00:11:40 UTC (rev 193992)
+++ trunk/Source/_javascript_Core/b3/B3PhiChildren.cpp 2015-12-12 00:17:24 UTC (rev 193993)
@@ -36,8 +36,13 @@
: m_upsilons(proc.values().size())
{
for (Value* value : proc.values()) {
- if (UpsilonValue* upsilon = value->as<UpsilonValue>())
- m_upsilons[upsilon->phi()].append(upsilon);
+ if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
+ Value* phi = upsilon->phi();
+ Vector<UpsilonValue*>& vector = m_upsilons[phi];
+ if (vector.isEmpty())
+ m_phis.append(phi);
+ vector.append(upsilon);
+ }
}
}
Modified: trunk/Source/_javascript_Core/b3/B3PhiChildren.h (193992 => 193993)
--- trunk/Source/_javascript_Core/b3/B3PhiChildren.h 2015-12-12 00:11:40 UTC (rev 193992)
+++ trunk/Source/_javascript_Core/b3/B3PhiChildren.h 2015-12-12 00:17:24 UTC (rev 193993)
@@ -166,8 +166,11 @@
UpsilonCollection at(Value* value) { return UpsilonCollection(this, value, &m_upsilons[value]); }
UpsilonCollection operator[](Value* value) { return at(value); }
+ const Vector<Value*, 8>& phis() const { return m_phis; }
+
private:
IndexMap<Value, Vector<UpsilonValue*>> m_upsilons;
+ Vector<Value*, 8> m_phis;
};
} } // namespace JSC::B3
Modified: trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp (193992 => 193993)
--- trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp 2015-12-12 00:11:40 UTC (rev 193992)
+++ trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp 2015-12-12 00:17:24 UTC (rev 193993)
@@ -35,6 +35,7 @@
#include "B3InsertionSetInlines.h"
#include "B3MemoryValue.h"
#include "B3PhaseScope.h"
+#include "B3PhiChildren.h"
#include "B3ProcedureInlines.h"
#include "B3UpsilonValue.h"
#include "B3UseCounts.h"
@@ -134,6 +135,7 @@
}
killDeadCode();
+ simplifySSA();
result |= m_changed;
} while (m_changed);
@@ -1248,6 +1250,67 @@
}
}
+ void simplifySSA()
+ {
+ // This runs Aycock and Horspool's algorithm on our Phi functions [1]. For most CFG patterns,
+ // this can take a suboptimal arrangement of Phi functions and make it optimal, as if you had
+ // run Cytron, Ferrante, Rosen, Wegman, and Zadeck. It's only suboptimal for irreducible
+ // CFGs. In practice, that doesn't matter, since we expect clients of B3 to run their own SSA
+ // conversion before lowering to B3, and in the case of the DFG, that conversion uses Cytron
+ // et al. In that context, this algorithm is intended to simplify Phi functions that were
+ // made redundant by prior CFG simplification. But according to Aycock and Horspool's paper,
+ // this algorithm is good enough that a B3 client could just give us maximal Phi's (i.e. Phi
+ // for each variable at each basic block) and we will make them optimal.
+ // [1] http://pages.cpsc.ucalgary.ca/~aycock/papers/ssa.ps
+
+ // Aycock and Horspool prescribe two rules that are to be run to fixpoint:
+ //
+ // 1) If all of the Phi's children are the same (i.e. it's one child referenced from one or
+ // more Upsilons), then replace all uses of the Phi with the one child.
+ //
+ // 2) If all of the Phi's children are either the Phi itself or exactly one other child, then
+ // replace all uses of the Phi with the one other child.
+ //
+ // Rule (2) subsumes rule (1), so we can just run (2). We only run one fixpoint iteration
+ // here. This premise is that in common cases, this will only find optimization opportunities
+ // as a result of CFG simplification and usually CFG simplification will only do one round
+ // of block merging per ReduceStrength fixpoint iteration, so it's OK for this to only do one
+ // round of Phi merging - since Phis are the value analogue of blocks.
+
+ PhiChildren phiChildren(m_proc);
+
+ for (Value* phi : phiChildren.phis()) {
+ Value* otherChild = nullptr;
+ bool ok = true;
+ for (Value* child : phiChildren[phi].values()) {
+ if (child == phi)
+ continue;
+ if (child == otherChild)
+ continue;
+ if (!otherChild) {
+ otherChild = child;
+ continue;
+ }
+ ok = false;
+ break;
+ }
+ if (!ok)
+ continue;
+ if (!otherChild) {
+ // Wow, this would be super weird. It probably won't happen, except that things could
+ // get weird as a consequence of stepwise simplifications in the strength reduction
+ // fixpoint.
+ continue;
+ }
+
+ // Turn the Phi into an Identity and turn the Upsilons into Nops.
+ m_changed = true;
+ for (Value* upsilon : phiChildren[phi])
+ upsilon->replaceWithNop();
+ phi->replaceWithIdentity(otherChild);
+ }
+ }
+
Procedure& m_proc;
InsertionSet m_insertionSet;
BasicBlock* m_block { nullptr };
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes
