Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (191761 => 191762)
--- trunk/Source/_javascript_Core/ChangeLog 2015-10-29 23:13:10 UTC (rev 191761)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-10-29 23:42:04 UTC (rev 191762)
@@ -1,3 +1,59 @@
+2015-10-29 Filip Pizlo <[email protected]>
+
+ StoreOpLoad pattern matching should check effects between the Store and Load
+ https://bugs.webkit.org/show_bug.cgi?id=150534
+
+ Reviewed by Geoffrey Garen.
+
+ If we turn:
+
+ a = Load(addr)
+ b = Add(a, 42)
+ Store(b, addr)
+
+ Into:
+
+ Add $42, (addr)
+
+ Then we must make sure that we didn't really have this to begin with:
+
+ a = Load(addr)
+ Store(666, addr)
+ b = Add(a, 42)
+ Store(b, addr)
+
+ That's because pattern matching doesn't care about control flow, and it finds the Load
+ just using data flow. This patch fleshes out B3's aliasing analysis, and makes it powerful
+ enough to broadly ask questions about whether such a code motion of the Load is legal.
+
+ * b3/B3Effects.cpp:
+ (JSC::B3::Effects::interferes):
+ (JSC::B3::Effects::dump):
+ * b3/B3Effects.h:
+ (JSC::B3::Effects::mustExecute):
+ * b3/B3LowerToAir.cpp:
+ (JSC::B3::Air::LowerToAir::run):
+ (JSC::B3::Air::LowerToAir::commitInternal):
+ (JSC::B3::Air::LowerToAir::crossesInterference):
+ (JSC::B3::Air::LowerToAir::effectiveAddr):
+ (JSC::B3::Air::LowerToAir::loadAddr):
+ * b3/B3Procedure.cpp:
+ (JSC::B3::Procedure::addBlock):
+ (JSC::B3::Procedure::resetValueOwners):
+ (JSC::B3::Procedure::resetReachability):
+ * b3/B3Procedure.h:
+ * b3/B3Value.cpp:
+ (JSC::B3::Value::effects):
+ * b3/B3Value.h:
+ * b3/testb3.cpp:
+ (JSC::B3::testStoreAddLoad):
+ (JSC::B3::testStoreAddLoadInterference):
+ (JSC::B3::testStoreAddAndLoad):
+ (JSC::B3::testLoadOffsetUsingAdd):
+ (JSC::B3::testLoadOffsetUsingAddInterference):
+ (JSC::B3::testLoadOffsetUsingAddNotConstant):
+ (JSC::B3::run):
+
2015-10-29 Brady Eidson <[email protected]>
Modern IDB: deleteObjectStore support.
Modified: trunk/Source/_javascript_Core/b3/B3Effects.cpp (191761 => 191762)
--- trunk/Source/_javascript_Core/b3/B3Effects.cpp 2015-10-29 23:13:10 UTC (rev 191761)
+++ trunk/Source/_javascript_Core/b3/B3Effects.cpp 2015-10-29 23:42:04 UTC (rev 191762)
@@ -29,9 +29,53 @@
#if ENABLE(B3_JIT)
#include <wtf/CommaPrinter.h>
+#include <wtf/DataLog.h>
namespace JSC { namespace B3 {
+namespace {
+
+// These helpers cascade in such a way that after the helper for terminal, we don't have to worry
+// about terminal again, since the terminal case considers all ways that a terminal may interfere
+// with something else. And after the exit sideways case, we don't have to worry about either
+// exitsSideways or terminal. And so on...
+
+bool interferesWithTerminal(const Effects& terminal, const Effects& other)
+{
+ if (!terminal.terminal)
+ return false;
+ return other.terminal || other.controlDependent || other.writesSSAState || other.writes;
+}
+
+bool interferesWithExitSideways(const Effects& exitsSideways, const Effects& other)
+{
+ if (!exitsSideways.exitsSideways)
+ return false;
+ return other.controlDependent || other.writes;
+}
+
+bool interferesWithWritesSSAState(const Effects& writesSSAState, const Effects& other)
+{
+ if (!writesSSAState.writesSSAState)
+ return false;
+ return other.writesSSAState || other.readsSSAState;
+}
+
+} // anonymous namespace
+
+bool Effects::interferes(const Effects& other) const
+{
+ if (interferesWithTerminal(*this, other) || interferesWithTerminal(other, *this))
+ return true;
+ if (interferesWithExitSideways(*this, other) || interferesWithExitSideways(other, *this))
+ return true;
+ if (interferesWithWritesSSAState(*this, other) || interferesWithWritesSSAState(other, *this))
+ return true;
+ return writes.overlaps(other.writes)
+ || writes.overlaps(other.reads)
+ || reads.overlaps(other.writes);
+}
+
void Effects::dump(PrintStream& out) const
{
CommaPrinter comma("|");
@@ -43,6 +87,8 @@
out.print(comma, "ControlDependent");
if (writesSSAState)
out.print(comma, "WritesSSAState");
+ if (readsSSAState)
+ out.print(comma, "ReadsSSAState");
if (writes)
out.print(comma, "Writes:", writes);
if (reads)
Modified: trunk/Source/_javascript_Core/b3/B3Effects.h (191761 => 191762)
--- trunk/Source/_javascript_Core/b3/B3Effects.h 2015-10-29 23:13:10 UTC (rev 191761)
+++ trunk/Source/_javascript_Core/b3/B3Effects.h 2015-10-29 23:42:04 UTC (rev 191762)
@@ -49,6 +49,9 @@
// anyway.
bool writesSSAState { false };
+ // True if this reads from the SSA state. This is only used for Phi.
+ bool readsSSAState { false };
+
HeapRange writes;
HeapRange reads;
@@ -57,6 +60,10 @@
return terminal || exitsSideways || writesSSAState || writes;
}
+ // Returns true if reordering instructions with these respective effects would change program
+ // behavior in an observable way.
+ bool interferes(const Effects&) const;
+
void dump(PrintStream& out) const;
};
Modified: trunk/Source/_javascript_Core/b3/B3LowerToAir.cpp (191761 => 191762)
--- trunk/Source/_javascript_Core/b3/B3LowerToAir.cpp 2015-10-29 23:13:10 UTC (rev 191761)
+++ trunk/Source/_javascript_Core/b3/B3LowerToAir.cpp 2015-10-29 23:42:04 UTC (rev 191762)
@@ -74,15 +74,19 @@
stackToStack.add(stackSlotValue, code.addStackSlot(stackSlotValue));
}
+ procedure.resetValueOwners(); // Used by crossesInterference().
+
// Lower defs before uses on a global level. This is a good heuristic to lock down a
// hoisted address _expression_ before we duplicate it back into the loop.
for (B3::BasicBlock* block : procedure.blocksInPreOrder()) {
+ currentBlock = block;
// Reset some state.
insts.resize(0);
// Process blocks in reverse order so we see uses before defs. That's what allows us
// to match patterns effectively.
for (unsigned i = block->size(); i--;) {
+ currentIndex = i;
currentValue = block->at(i);
if (locked.contains(currentValue))
continue;
@@ -144,6 +148,29 @@
locked.add(value);
}
+ bool crossesInterference(Value* value)
+ {
+ // If it's in a foreign block, then be conservative. We could handle this if we were
+ // willing to do heavier analysis. For example, if we had liveness, then we could label
+ // values as "crossing interference" if they interfere with anything that they are live
+ // across. But, it's not clear how useful this would be.
+ if (value->owner != currentValue->owner)
+ return true;
+
+ Effects effects = value->effects();
+
+ for (unsigned i = currentIndex; i--;) {
+ Value* otherValue = currentBlock->at(i);
+ if (otherValue == value)
+ return false;
+ if (effects.interferes(otherValue->effects()))
+ return true;
+ }
+
+ ASSERT_NOT_REACHED();
+ return true;
+ }
+
// This turns the given operand into an address.
Arg effectiveAddr(Value* address)
{
@@ -179,11 +206,13 @@
Arg loadAddr(Value* loadValue)
{
+ if (loadValue->opcode() != Load)
+ return Arg();
if (!canBeInternal(loadValue))
return Arg();
- if (loadValue->opcode() == Load)
- return addr(loadValue);
- return Arg();
+ if (crossesInterference(loadValue))
+ return Arg();
+ return addr(loadValue);
}
Arg imm(Value* value)
@@ -289,11 +318,6 @@
template<Air::Opcode opcode, Commutativity commutativity = NotCommutative>
bool tryAppendStoreBinOp(Value* left, Value* right)
{
- // FIXME: This fails to check if there are any effects between the Load and the Store that
- // could clobber the loaded value. We need to check such things because we are effectively
- // sinking the load.
- // https://bugs.webkit.org/show_bug.cgi?id=150534
-
Arg storeAddr = addr(currentValue);
ASSERT(storeAddr);
@@ -366,6 +390,8 @@
Vector<Vector<Inst, 4>> insts;
Vector<Inst> prologue;
+ B3::BasicBlock* currentBlock;
+ unsigned currentIndex;
Value* currentValue;
// The address selector will match any pattern where the input operands are available as Tmps.
Modified: trunk/Source/_javascript_Core/b3/B3Procedure.cpp (191761 => 191762)
--- trunk/Source/_javascript_Core/b3/B3Procedure.cpp 2015-10-29 23:13:10 UTC (rev 191761)
+++ trunk/Source/_javascript_Core/b3/B3Procedure.cpp 2015-10-29 23:42:04 UTC (rev 191762)
@@ -52,6 +52,14 @@
return result;
}
+void Procedure::resetValueOwners()
+{
+ for (BasicBlock* block : *this) {
+ for (Value* value : *block)
+ value->owner = block;
+ }
+}
+
void Procedure::resetReachability()
{
B3::resetReachability(m_blocks);
Modified: trunk/Source/_javascript_Core/b3/B3Procedure.h (191761 => 191762)
--- trunk/Source/_javascript_Core/b3/B3Procedure.h 2015-10-29 23:13:10 UTC (rev 191761)
+++ trunk/Source/_javascript_Core/b3/B3Procedure.h 2015-10-29 23:42:04 UTC (rev 191762)
@@ -53,6 +53,7 @@
template<typename ValueType, typename... Arguments>
ValueType* add(Arguments...);
+ void resetValueOwners();
void resetReachability();
JS_EXPORT_PRIVATE void dump(PrintStream&) const;
Modified: trunk/Source/_javascript_Core/b3/B3Value.cpp (191761 => 191762)
--- trunk/Source/_javascript_Core/b3/B3Value.cpp 2015-10-29 23:13:10 UTC (rev 191761)
+++ trunk/Source/_javascript_Core/b3/B3Value.cpp 2015-10-29 23:42:04 UTC (rev 191762)
@@ -168,7 +168,6 @@
case Below:
case AboveEqual:
case BelowEqual:
- case Phi:
break;
case Div:
result.controlDependent = true;
@@ -209,6 +208,9 @@
case Upsilon:
result.writesSSAState = true;
break;
+ case Phi:
+ result.readsSSAState = true;
+ break;
case Jump:
case Branch:
case Switch:
Modified: trunk/Source/_javascript_Core/b3/B3Value.h (191761 => 191762)
--- trunk/Source/_javascript_Core/b3/B3Value.h 2015-10-29 23:13:10 UTC (rev 191761)
+++ trunk/Source/_javascript_Core/b3/B3Value.h 2015-10-29 23:42:04 UTC (rev 191762)
@@ -197,7 +197,7 @@
AdjacencyList m_children;
public:
- BasicBlock* owner { nullptr }; // computed lazily.
+ BasicBlock* owner { nullptr }; // computed by Procedure::resetValueOwners().
};
class DeepValueDump {
Modified: trunk/Source/_javascript_Core/b3/testb3.cpp (191761 => 191762)
--- trunk/Source/_javascript_Core/b3/testb3.cpp 2015-10-29 23:13:10 UTC (rev 191761)
+++ trunk/Source/_javascript_Core/b3/testb3.cpp 2015-10-29 23:42:04 UTC (rev 191762)
@@ -235,6 +235,33 @@
CHECK(slot == 37 + amount);
}
+void testStoreAddLoadInterference(int amount)
+{
+ Procedure proc;
+ BasicBlock* root = proc.addBlock();
+ int slot = 37;
+ ConstPtrValue* slotPtr = root->appendNew<ConstPtrValue>(proc, Origin(), &slot);
+ ArgumentRegValue* otherSlotPtr =
+ root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
+ MemoryValue* load = root->appendNew<MemoryValue>(proc, Load, Int32, Origin(), slotPtr);
+ root->appendNew<MemoryValue>(
+ proc, Store, Origin(),
+ root->appendNew<Const32Value>(proc, Origin(), 666),
+ otherSlotPtr);
+ root->appendNew<MemoryValue>(
+ proc, Store, Origin(),
+ root->appendNew<Value>(
+ proc, Add, Origin(),
+ load, root->appendNew<Const32Value>(proc, Origin(), amount)),
+ slotPtr);
+ root->appendNew<ControlValue>(
+ proc, Return, Origin(),
+ root->appendNew<Const32Value>(proc, Origin(), 0));
+
+ CHECK(!compileAndRun<int>(proc, &slot));
+ CHECK(slot == 37 + amount);
+}
+
void testStoreAddAndLoad(int amount, int mask)
{
Procedure proc;
@@ -331,6 +358,39 @@
CHECK(compileAndRun<int>(proc) == array[0] + array[1]);
}
+void testLoadOffsetUsingAddInterference()
+{
+ Procedure proc;
+ BasicBlock* root = proc.addBlock();
+ int array[] = { 1, 2 };
+ ConstPtrValue* arrayPtr = root->appendNew<ConstPtrValue>(proc, Origin(), array);
+ ArgumentRegValue* otherArrayPtr =
+ root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
+ Const32Value* theNumberOfTheBeast = root->appendNew<Const32Value>(proc, Origin(), 666);
+ MemoryValue* left = root->appendNew<MemoryValue>(
+ proc, Load, Int32, Origin(),
+ root->appendNew<Value>(
+ proc, Add, Origin(), arrayPtr,
+ root->appendNew<ConstPtrValue>(proc, Origin(), 0)));
+ MemoryValue* right = root->appendNew<MemoryValue>(
+ proc, Load, Int32, Origin(),
+ root->appendNew<Value>(
+ proc, Add, Origin(), arrayPtr,
+ root->appendNew<ConstPtrValue>(proc, Origin(), sizeof(int))));
+ root->appendNew<MemoryValue>(
+ proc, Store, Origin(), theNumberOfTheBeast, otherArrayPtr, 0);
+ root->appendNew<MemoryValue>(
+ proc, Store, Origin(), theNumberOfTheBeast, otherArrayPtr, sizeof(int));
+ root->appendNew<ControlValue>(
+ proc, Return, Origin(),
+ root->appendNew<Value>(
+ proc, Add, Origin(), left, right));
+
+ CHECK(compileAndRun<int>(proc, &array[0]) == 1 + 2);
+ CHECK(array[0] == 666);
+ CHECK(array[1] == 666);
+}
+
void testLoadOffsetUsingAddNotConstant()
{
Procedure proc;
@@ -443,12 +503,14 @@
RUN(testTrunc((static_cast<int64_t>(1) << 40) + 42));
RUN(testAdd1(45));
RUN(testStoreAddLoad(46));
+ RUN(testStoreAddLoadInterference(52));
RUN(testStoreAddAndLoad(47, 0xffff));
RUN(testStoreAddAndLoad(470000, 0xffff));
RUN(testAdd1Uncommuted(48));
RUN(testLoadOffset());
RUN(testLoadOffsetNotConstant());
RUN(testLoadOffsetUsingAdd());
+ RUN(testLoadOffsetUsingAddInterference());
RUN(testLoadOffsetUsingAddNotConstant());
RUN(testFramePointer());
RUN(testStackSlot());
Modified: trunk/Source/WTF/wtf/MathExtras.h (191761 => 191762)
--- trunk/Source/WTF/wtf/MathExtras.h 2015-10-29 23:13:10 UTC (rev 191761)
+++ trunk/Source/WTF/wtf/MathExtras.h 2015-10-29 23:42:04 UTC (rev 191762)
@@ -428,6 +428,13 @@
{
ASSERT(leftMin <= leftMax);
ASSERT(rightMin <= rightMax);
+
+ // Empty ranges interfere with nothing.
+ if (leftMin == leftMax)
+ return false;
+ if (rightMin == rightMax)
+ return false;
+
if (leftMin <= rightMin && leftMax > rightMin)
return true;
if (rightMin <= leftMin && rightMax > leftMin)
