- Revision
- 193987
- Author
- [email protected]
- Date
- 2015-12-11 15:20:20 -0800 (Fri, 11 Dec 2015)
Log Message
B3 should have CSE
https://bugs.webkit.org/show_bug.cgi?id=150961
Reviewed by Benjamin Poulain.
This implements a very simple CSE for pure values. I need this as a prerequisite for other
optimizations that I'm implementing. For now, this is neutral on imaging-gaussian-blur but a
slow-down on asm.js code. I suspect that the asm.js slow-down is because of other things that are
still going wrong, and anyway, I need CSE to be able to do even the most basic asm.js strength
reductions.
* b3/B3ReduceStrength.cpp:
* b3/B3ReduceStrength.h:
* b3/B3Value.cpp:
(JSC::B3::Value::replaceWithIdentity):
(JSC::B3::Value::key):
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (193986 => 193987)
--- trunk/Source/_javascript_Core/ChangeLog 2015-12-11 23:09:35 UTC (rev 193986)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-12-11 23:20:20 UTC (rev 193987)
@@ -1,3 +1,22 @@
+2015-12-11 Filip Pizlo <[email protected]>
+
+ B3 should have CSE
+ https://bugs.webkit.org/show_bug.cgi?id=150961
+
+ Reviewed by Benjamin Poulain.
+
+ This implements a very simple CSE for pure values. I need this as a prerequisite for other
+ optimizations that I'm implementing. For now, this is neutral on imaging-gaussian-blur but a
+ slow-down on asm.js code. I suspect that the asm.js slow-down is because of other things that are
+ still going wrong, and anyway, I need CSE to be able to do even the most basic asm.js strength
+ reductions.
+
+ * b3/B3ReduceStrength.cpp:
+ * b3/B3ReduceStrength.h:
+ * b3/B3Value.cpp:
+ (JSC::B3::Value::replaceWithIdentity):
+ (JSC::B3::Value::key):
+
2015-12-11 Mark Lam <[email protected]>
Refactoring to reduce potential cut-paste errors with the FTL ICs.
Modified: trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp (193986 => 193987)
--- trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp 2015-12-11 23:09:35 UTC (rev 193986)
+++ trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp 2015-12-11 23:20:20 UTC (rev 193987)
@@ -30,6 +30,7 @@
#include "B3BasicBlockInlines.h"
#include "B3ControlValue.h"
+#include "B3Dominators.h"
#include "B3IndexSet.h"
#include "B3InsertionSetInlines.h"
#include "B3MemoryValue.h"
@@ -37,8 +38,10 @@
#include "B3ProcedureInlines.h"
#include "B3UpsilonValue.h"
#include "B3UseCounts.h"
+#include "B3ValueKey.h"
#include "B3ValueInlines.h"
#include <wtf/GraphNodeWorklist.h>
+#include <wtf/HashMap.h>
namespace JSC { namespace B3 {
@@ -105,11 +108,20 @@
dataLog(m_proc);
}
+ m_proc.resetValueOwners();
+ m_dominators = &m_proc.dominators(); // Recompute if necessary.
+ m_pureValues.clear();
+
for (BasicBlock* block : m_proc.blocksInPreOrder()) {
m_block = block;
- for (m_index = 0; m_index < block->size(); ++m_index)
- process();
+ for (m_index = 0; m_index < block->size(); ++m_index) {
+ m_value = m_block->at(m_index);
+ m_value->performSubstitution();
+
+ reduceValueStrength();
+ replaceIfRedundant();
+ }
m_insertionSet.execute(m_block);
}
@@ -129,11 +141,8 @@
}
private:
- void process()
+ void reduceValueStrength()
{
- m_value = m_block->at(m_index);
- m_value->performSubstitution();
-
switch (m_value->opcode()) {
case Add:
handleCommutativity();
@@ -1014,6 +1023,35 @@
return false;
}
+ void replaceIfRedundant()
+ {
+ // This does a very simple pure dominator-based CSE. In the future we could add load elimination.
+ // Note that if we add load elimination, we should do it by directly matching load and store
+ // instructions instead of using the ValueKey functionality or doing DFG HeapLocation-like
+ // things.
+
+ // Don't bother with identities. We kill those anyway.
+ if (m_value->opcode() == Identity)
+ return;
+
+ ValueKey key = m_value->key();
+ if (!key)
+ return;
+
+ Vector<Value*, 1>& matches = m_pureValues.add(key, Vector<Value*, 1>()).iterator->value;
+
+ // Replace this value with whichever value dominates us.
+ for (Value* match : matches) {
+ if (m_dominators->dominates(match->owner, m_value->owner)) {
+ m_value->replaceWithIdentity(match);
+ m_changed = true;
+ return;
+ }
+ }
+
+ matches.append(m_value);
+ }
+
void simplifyCFG()
{
if (verbose) {
@@ -1212,11 +1250,13 @@
Procedure& m_proc;
InsertionSet m_insertionSet;
- BasicBlock* m_block;
- unsigned m_index;
- Value* m_value;
- bool m_changed;
- bool m_changedCFG;
+ BasicBlock* m_block { nullptr };
+ unsigned m_index { 0 };
+ Value* m_value { nullptr };
+ Dominators* m_dominators { nullptr };
+ HashMap<ValueKey, Vector<Value*, 1>> m_pureValues;
+ bool m_changed { false };
+ bool m_changedCFG { false };
};
} // anonymous namespace
Modified: trunk/Source/_javascript_Core/b3/B3ReduceStrength.h (193986 => 193987)
--- trunk/Source/_javascript_Core/b3/B3ReduceStrength.h 2015-12-11 23:09:35 UTC (rev 193986)
+++ trunk/Source/_javascript_Core/b3/B3ReduceStrength.h 2015-12-11 23:20:20 UTC (rev 193987)
@@ -32,8 +32,11 @@
class Procedure;
-// Does strength reduction, constant folding, canonicalization, CFG simplification, and DCE. In the
-// future we may also have it do CSE.
+// Does strength reduction, constant folding, canonicalization, CFG simplification, DCE, and CSE. This
+// phase runs those optimizations to fixpoint. The goal of the phase is to dramatically reduce the
+// complexity of the code. In the future, it's preferable to add optimizations to this phase rather than
+// creating new optimizations because then the optimizations can participate in the fixpoint. However,
+// this phase shouldn't become too expensive, so expensive optimizations should be separate.
bool reduceStrength(Procedure&);
Modified: trunk/Source/_javascript_Core/b3/B3Value.cpp (193986 => 193987)
--- trunk/Source/_javascript_Core/b3/B3Value.cpp 2015-12-11 23:09:35 UTC (rev 193986)
+++ trunk/Source/_javascript_Core/b3/B3Value.cpp 2015-12-11 23:20:20 UTC (rev 193987)
@@ -54,6 +54,13 @@
// a plain Identity Value. We first collect all of the information we need, then we destruct the
// previous value in place, and then we construct the Identity Value in place.
+ ASSERT(m_type == value->m_type);
+
+ if (m_type == Void) {
+ replaceWithNop();
+ return;
+ }
+
unsigned index = m_index;
Type type = m_type;
Origin origin = m_origin;
@@ -438,6 +445,7 @@
case FloatToDouble:
case DoubleToFloat:
case Check:
+ case BitwiseCast:
return ValueKey(opcode(), type(), child(0));
case Add:
case Sub:
