[B3] B3 strength reduction could encounter Value without owner in PureCSE
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 Jan 2017 08:40:05 +0000 (08:40 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 Jan 2017 08:40:05 +0000 (08:40 +0000)
https://bugs.webkit.org/show_bug.cgi?id=167161

Reviewed by Filip Pizlo.

PureCSE relies on the fact that all the stored Values have owner member.
This assumption is broken when you execute specializeSelect in B3ReduceStrength phase.
It clears owner of Values which are in between Select and Check to clone them to then/else
blocks. If these cleared Values are already stored in PureCSE map, this map poses a Value
with nullptr owner in PureCSE.

This patch changes PureCSE to ignore stored Values tha have nullptr owner. This even means
that a client of PureCSE could deliberately null the owner if they wanted to signal the
Value should be ignored.

While PureCSE ignores chance for optimization if Value's owner is nullptr, in the current
strength reduction algorithm, this does not hurt optimization because CSE will be eventually
applied since the strength reduction phase want to reach fixed point. But even without
this iterations, our result itself is valid since PureCSE is allowed to be conservative.

* b3/B3PureCSE.cpp:
(JSC::B3::PureCSE::findMatch):
(JSC::B3::PureCSE::process):
* b3/testb3.cpp:
(JSC::B3::testCheckSelectAndCSE):
(JSC::B3::run):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@210919 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3PureCSE.cpp
Source/JavaScriptCore/b3/testb3.cpp

index 8ce258c..1345c6a 100644 (file)
@@ -1,3 +1,32 @@
+2017-01-18  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [B3] B3 strength reduction could encounter Value without owner in PureCSE
+        https://bugs.webkit.org/show_bug.cgi?id=167161
+
+        Reviewed by Filip Pizlo.
+
+        PureCSE relies on the fact that all the stored Values have owner member.
+        This assumption is broken when you execute specializeSelect in B3ReduceStrength phase.
+        It clears owner of Values which are in between Select and Check to clone them to then/else
+        blocks. If these cleared Values are already stored in PureCSE map, this map poses a Value
+        with nullptr owner in PureCSE.
+
+        This patch changes PureCSE to ignore stored Values tha have nullptr owner. This even means
+        that a client of PureCSE could deliberately null the owner if they wanted to signal the
+        Value should be ignored.
+
+        While PureCSE ignores chance for optimization if Value's owner is nullptr, in the current
+        strength reduction algorithm, this does not hurt optimization because CSE will be eventually
+        applied since the strength reduction phase want to reach fixed point. But even without
+        this iterations, our result itself is valid since PureCSE is allowed to be conservative.
+
+        * b3/B3PureCSE.cpp:
+        (JSC::B3::PureCSE::findMatch):
+        (JSC::B3::PureCSE::process):
+        * b3/testb3.cpp:
+        (JSC::B3::testCheckSelectAndCSE):
+        (JSC::B3::run):
+
 2017-01-18  Filip Pizlo  <fpizlo@apple.com>
 
         JSSegmentedVariableObject and its subclasses should have a sane destruction story
index 4030e28..0ea3447 100644 (file)
@@ -56,6 +56,8 @@ Value* PureCSE::findMatch(const ValueKey& key, BasicBlock* block, Dominators& do
         return nullptr;
 
     for (Value* match : iter->value) {
+        if (!match->owner)
+            continue;
         if (dominators.dominates(match->owner, block))
             return match;
     }
@@ -75,6 +77,8 @@ bool PureCSE::process(Value* value, Dominators& dominators)
     Matches& matches = m_map.add(key, Matches()).iterator->value;
 
     for (Value* match : matches) {
+        if (!match->owner)
+            continue;
         if (dominators.dominates(match->owner, value->owner)) {
             value->replaceWithIdentity(match);
             return true;
index fc33c6f..b835026 100644 (file)
@@ -11831,6 +11831,50 @@ void testCheckSelectCheckSelect()
     CHECK(invoke<int>(*code, true, false) == 667);
 }
 
+void testCheckSelectAndCSE()
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+
+    auto* selectValue = root->appendNew<Value>(
+        proc, Select, Origin(),
+        root->appendNew<Value>(
+            proc, BitAnd, Origin(),
+            root->appendNew<Value>(
+                proc, Trunc, Origin(),
+                root->appendNew<ArgumentRegValue>(
+                    proc, Origin(), GPRInfo::argumentGPR0)),
+            root->appendNew<Const32Value>(proc, Origin(), 0xff)),
+        root->appendNew<ConstPtrValue>(proc, Origin(), -42),
+        root->appendNew<ConstPtrValue>(proc, Origin(), 35));
+
+    auto* constant = root->appendNew<ConstPtrValue>(proc, Origin(), 42);
+    auto* addValue = root->appendNew<Value>(proc, Add, Origin(), selectValue, constant);
+
+    CheckValue* check = root->appendNew<CheckValue>(proc, Check, Origin(), addValue);
+    unsigned generationCount = 0;
+    check->setGenerator(
+        [&] (CCallHelpers& jit, const StackmapGenerationParams&) {
+            AllowMacroScratchRegisterUsage allowScratch(jit);
+
+            generationCount++;
+            jit.move(CCallHelpers::TrustedImm32(666), GPRInfo::returnValueGPR);
+            jit.emitFunctionEpilogue();
+            jit.ret();
+        });
+
+    auto* addValue2 = root->appendNew<Value>(proc, Add, Origin(), selectValue, constant);
+
+    root->appendNewControlValue(
+        proc, Return, Origin(),
+        root->appendNew<Value>(proc, Add, Origin(), addValue, addValue2));
+
+    auto code = compile(proc);
+    CHECK(generationCount == 1);
+    CHECK(invoke<int>(*code, true) == 0);
+    CHECK(invoke<int>(*code, false) == 666);
+}
+
 double b3Pow(double x, int y)
 {
     if (y < 0 || y > 1000)
@@ -15433,6 +15477,7 @@ void run(const char* filter)
     RUN(testSelectInvert());
     RUN(testCheckSelect());
     RUN(testCheckSelectCheckSelect());
+    RUN(testCheckSelectAndCSE());
     RUN_BINARY(testPowDoubleByIntegerLoop, floatingPointOperands<double>(), int64Operands());
 
     RUN(testTruncOrHigh());