B3 should be able to compile a program with Switch
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 12 Nov 2015 04:08:46 +0000 (04:08 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 12 Nov 2015 04:08:46 +0000 (04:08 +0000)
https://bugs.webkit.org/show_bug.cgi?id=151115

Reviewed by Benjamin Poulain.

Adds lowering of Switch to a binary switch. This doesn't require any Air support.

* b3/B3BasicBlock.cpp:
(JSC::B3::BasicBlock::append):
(JSC::B3::BasicBlock::removeLast):
(JSC::B3::BasicBlock::replaceLast):
* b3/B3BasicBlock.h:
* b3/B3BlockInsertionSet.cpp:
(JSC::B3::BlockInsertionSet::insertBefore):
(JSC::B3::BlockInsertionSet::insertAfter):
(JSC::B3::BlockInsertionSet::splitForward):
* b3/B3BlockInsertionSet.h:
* b3/B3ControlValue.h:
* b3/B3Generate.cpp:
(JSC::B3::generateToAir):
* b3/B3LowerMacros.cpp:
* b3/B3SwitchValue.cpp:
(JSC::B3::SwitchValue::dumpMeta):
(JSC::B3::SwitchValue::SwitchValue):
* b3/B3SwitchValue.h:
* b3/testb3.cpp:
(JSC::B3::testChillDiv64):
(JSC::B3::testSwitch):
(JSC::B3::run):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3BasicBlock.cpp
Source/JavaScriptCore/b3/B3BasicBlock.h
Source/JavaScriptCore/b3/B3BlockInsertionSet.cpp
Source/JavaScriptCore/b3/B3BlockInsertionSet.h
Source/JavaScriptCore/b3/B3ControlValue.h
Source/JavaScriptCore/b3/B3Generate.cpp
Source/JavaScriptCore/b3/B3LowerMacros.cpp
Source/JavaScriptCore/b3/B3SwitchValue.cpp
Source/JavaScriptCore/b3/B3SwitchValue.h
Source/JavaScriptCore/b3/testb3.cpp

index ab6c91d..6b99208 100644 (file)
@@ -1,5 +1,37 @@
 2015-11-11  Filip Pizlo  <fpizlo@apple.com>
 
+        B3 should be able to compile a program with Switch
+        https://bugs.webkit.org/show_bug.cgi?id=151115
+
+        Reviewed by Benjamin Poulain.
+
+        Adds lowering of Switch to a binary switch. This doesn't require any Air support.
+
+        * b3/B3BasicBlock.cpp:
+        (JSC::B3::BasicBlock::append):
+        (JSC::B3::BasicBlock::removeLast):
+        (JSC::B3::BasicBlock::replaceLast):
+        * b3/B3BasicBlock.h:
+        * b3/B3BlockInsertionSet.cpp:
+        (JSC::B3::BlockInsertionSet::insertBefore):
+        (JSC::B3::BlockInsertionSet::insertAfter):
+        (JSC::B3::BlockInsertionSet::splitForward):
+        * b3/B3BlockInsertionSet.h:
+        * b3/B3ControlValue.h:
+        * b3/B3Generate.cpp:
+        (JSC::B3::generateToAir):
+        * b3/B3LowerMacros.cpp:
+        * b3/B3SwitchValue.cpp:
+        (JSC::B3::SwitchValue::dumpMeta):
+        (JSC::B3::SwitchValue::SwitchValue):
+        * b3/B3SwitchValue.h:
+        * b3/testb3.cpp:
+        (JSC::B3::testChillDiv64):
+        (JSC::B3::testSwitch):
+        (JSC::B3::run):
+
+2015-11-11  Filip Pizlo  <fpizlo@apple.com>
+
         Patchpoints with stackArgument constraints should work
         https://bugs.webkit.org/show_bug.cgi?id=151177
 
index 501266f..2f5f80c 100644 (file)
@@ -54,10 +54,16 @@ void BasicBlock::append(Value* value)
     m_values.append(value);
 }
 
+void BasicBlock::removeLast(Procedure& proc)
+{
+    ASSERT(!m_values.isEmpty());
+    proc.deleteValue(m_values.takeLast());
+}
+
 void BasicBlock::replaceLast(Procedure& proc, Value* value)
 {
-    proc.deleteValue(last());
-    last() = value;
+    removeLast(proc);
+    append(value);
 }
 
 Value* BasicBlock::appendIntConstant(Procedure& proc, Origin origin, Type type, int64_t value)
index d28f6af..68b29a7 100644 (file)
@@ -78,6 +78,8 @@ public:
 
     Value* appendIntConstant(Procedure&, Origin, Type, int64_t value);
     Value* appendIntConstant(Procedure&, Value* likeValue, int64_t value);
+
+    void removeLast(Procedure&);
     
     template<typename ValueType, typename... Arguments>
     ValueType* replaceLastWithNew(Procedure&, Arguments...);
index 4e2ef33..902b1dd 100644 (file)
@@ -60,6 +60,11 @@ BasicBlock* BlockInsertionSet::insertBefore(BasicBlock* before, double frequency
     return insert(before->index(), frequency == frequency ? frequency : before->frequency());
 }
 
+BasicBlock* BlockInsertionSet::insertAfter(BasicBlock* after, double frequency)
+{
+    return insert(after->index() + 1, frequency == frequency ? frequency : after->frequency());
+}
+
 BasicBlock* BlockInsertionSet::splitForward(
     BasicBlock* block, unsigned& valueIndex, InsertionSet* insertionSet, double frequency)
 {
index 63649e5..d23ad29 100644 (file)
@@ -53,6 +53,9 @@ public:
     // usually what you want.
     BasicBlock* insertBefore(BasicBlock* before, double frequency = PNaN);
 
+    // Inserts a new block after the given block.
+    BasicBlock* insertAfter(BasicBlock* after, double frequency = PNaN);
+
     // A helper to split a block when forward iterating over it. It creates a new block to hold
     // everything before the instruction at valueIndex. The current block is left with
     // everything at and after valueIndex. If the optional InsertionSet is provided, it will get
index 24b82c0..fce3c3e 100644 (file)
@@ -95,7 +95,7 @@ protected:
     // Use this for subclasses.
     template<typename... Arguments>
     ControlValue(unsigned index, Opcode opcode, Type type, Origin origin, Arguments... arguments)
-        : Value(index, opcode, type, origin, arguments...)
+        : Value(index, CheckedOpcode, opcode, type, origin, arguments...)
     {
         ASSERT(accepts(opcode));
     }
index 4f2d760..28166b8 100644 (file)
@@ -55,18 +55,17 @@ void generateToAir(Procedure& procedure, Air::Code& code, unsigned optLevel)
 {
     TimingScope timingScope("generateToAir");
     
+    if (shouldDumpIR() && !shouldDumpIRAtEachPhase()) {
+        dataLog("Initial B3:\n");
+        dataLog(procedure);
+    }
+
     // We don't require the incoming IR to have predecessors computed.
     procedure.resetReachability();
     
     if (shouldValidateIR())
         validate(procedure);
 
-    // If we're doing super verbose dumping, the phase scope of any phase will already do a dump.
-    if (shouldDumpIR() && !shouldDumpIRAtEachPhase()) {
-        dataLog("Initial B3:\n");
-        dataLog(procedure);
-    }
-
     lowerMacros(procedure);
 
     if (optLevel >= 1) {
index 17aca90..c907bba 100644 (file)
@@ -34,6 +34,7 @@
 #include "B3InsertionSetInlines.h"
 #include "B3PhaseScope.h"
 #include "B3ProcedureInlines.h"
+#include "B3SwitchValue.h"
 #include "B3UpsilonValue.h"
 #include "B3ValueInlines.h"
 
@@ -67,6 +68,7 @@ private:
     {
         for (m_index = 0; m_index < m_block->size(); ++m_index) {
             m_value = m_block->at(m_index);
+            m_origin = m_value->origin();
             switch (m_value->opcode()) {
             case ChillDiv: {
                 // ARM supports this instruction natively.
@@ -96,8 +98,8 @@ private:
                 Value* one =
                     m_insertionSet.insertIntConstant(m_index, m_value, 1);
                 Value* isDenOK = m_insertionSet.insert<Value>(
-                    m_index, Above, m_value->origin(),
-                    m_insertionSet.insert<Value>(m_index, Add, m_value->origin(), den, one),
+                    m_index, Above, m_origin,
+                    m_insertionSet.insert<Value>(m_index, Add, m_origin, den, one),
                     one);
 
                 BasicBlock* before =
@@ -110,26 +112,26 @@ private:
                 BasicBlock* intMinCase = m_blockInsertionSet.insertBefore(m_block);
 
                 before->replaceLastWithNew<ControlValue>(
-                    m_proc, Branch, m_value->origin(), isDenOK,
+                    m_proc, Branch, m_origin, isDenOK,
                     FrequentedBlock(normalDivCase, FrequencyClass::Normal),
                     FrequentedBlock(shadyDenCase, FrequencyClass::Rare));
 
                 UpsilonValue* normalResult = normalDivCase->appendNew<UpsilonValue>(
-                    m_proc, m_value->origin(),
-                    normalDivCase->appendNew<Value>(m_proc, Div, m_value->origin(), num, den));
+                    m_proc, m_origin,
+                    normalDivCase->appendNew<Value>(m_proc, Div, m_origin, num, den));
                 normalDivCase->appendNew<ControlValue>(
-                    m_proc, Jump, m_value->origin(), FrequentedBlock(m_block));
+                    m_proc, Jump, m_origin, FrequentedBlock(m_block));
 
                 shadyDenCase->appendNew<ControlValue>(
-                    m_proc, Branch, m_value->origin(), den,
+                    m_proc, Branch, m_origin, den,
                     FrequentedBlock(neg1DenCase, FrequencyClass::Normal),
                     FrequentedBlock(zeroDenCase, FrequencyClass::Rare));
 
                 UpsilonValue* zeroResult = zeroDenCase->appendNew<UpsilonValue>(
-                    m_proc, m_value->origin(),
+                    m_proc, m_origin,
                     zeroDenCase->appendIntConstant(m_proc, m_value, 0));
                 zeroDenCase->appendNew<ControlValue>(
-                    m_proc, Jump, m_value->origin(), FrequentedBlock(m_block));
+                    m_proc, Jump, m_origin, FrequentedBlock(m_block));
 
                 int64_t badNumeratorConst;
                 switch (m_value->type()) {
@@ -148,19 +150,19 @@ private:
                     neg1DenCase->appendIntConstant(m_proc, m_value, badNumeratorConst);
 
                 neg1DenCase->appendNew<ControlValue>(
-                    m_proc, Branch, m_value->origin(),
+                    m_proc, Branch, m_origin,
                     neg1DenCase->appendNew<Value>(
-                        m_proc, Equal, m_value->origin(), num, badNumerator),
+                        m_proc, Equal, m_origin, num, badNumerator),
                     FrequentedBlock(intMinCase, FrequencyClass::Rare),
                     FrequentedBlock(normalDivCase, FrequencyClass::Normal));
 
                 UpsilonValue* intMinResult = intMinCase->appendNew<UpsilonValue>(
-                    m_proc, m_value->origin(), badNumerator);
+                    m_proc, m_origin, badNumerator);
                 intMinCase->appendNew<ControlValue>(
-                    m_proc, Jump, m_value->origin(), FrequentedBlock(m_block));
+                    m_proc, Jump, m_origin, FrequentedBlock(m_block));
 
                 Value* phi = m_insertionSet.insert<Value>(
-                    m_index, Phi, m_value->type(), m_value->origin());
+                    m_index, Phi, m_value->type(), m_origin);
                 normalResult->setPhi(phi);
                 zeroResult->setPhi(phi);
                 intMinResult->setPhi(phi);
@@ -170,8 +172,23 @@ private:
                 break;
             }
 
-            // FIXME: Implement Switch.
-            // https://bugs.webkit.org/show_bug.cgi?id=151115
+            case Switch: {
+                SwitchValue* switchValue = m_value->as<SwitchValue>();
+                Vector<SwitchCase> cases;
+                for (const SwitchCase& switchCase : *switchValue)
+                    cases.append(switchCase);
+                std::sort(
+                    cases.begin(), cases.end(),
+                    [] (const SwitchCase& left, const SwitchCase& right) {
+                        return left.caseValue() < right.caseValue();
+                    });
+                m_block->values().removeLast();
+                recursivelyBuildSwitch(cases, 0, false, cases.size(), m_block);
+                m_proc.deleteValue(switchValue);
+                m_block->updatePredecessorsAfter();
+                m_changed = true;
+                break;
+            }
 
             default:
                 break;
@@ -179,6 +196,79 @@ private:
         }
         m_insertionSet.execute(m_block);
     }
+
+    void recursivelyBuildSwitch(
+        const Vector<SwitchCase>& cases, unsigned start, bool hardStart, unsigned end,
+        BasicBlock* before)
+    {
+        // FIXME: Add table-based switch lowering.
+        // https://bugs.webkit.org/show_bug.cgi?id=151141
+        
+        // See comments in jit/BinarySwitch.cpp for a justification of this algorithm. The only
+        // thing we do differently is that we don't use randomness.
+
+        const unsigned leafThreshold = 3;
+
+        unsigned size = end - start;
+
+        if (size <= leafThreshold) {
+            bool allConsecutive = false;
+
+            if ((hardStart || (start && cases[start - 1].caseValue() == cases[start].caseValue() - 1))
+                && end < cases.size()
+                && cases[end - 1].caseValue() == cases[end].caseValue() - 1) {
+                allConsecutive = true;
+                for (unsigned i = 0; i < size - 1; ++i) {
+                    if (cases[start + i].caseValue() + 1 != cases[start + i + 1].caseValue()) {
+                        allConsecutive = false;
+                        break;
+                    }
+                }
+            }
+
+            unsigned limit = allConsecutive ? size - 1 : size;
+            
+            for (unsigned i = 0; i < limit; ++i) {
+                BasicBlock* nextCheck = m_blockInsertionSet.insertAfter(m_block);
+                before->appendNew<ControlValue>(
+                    m_proc, Branch, m_origin,
+                    before->appendNew<Value>(
+                        m_proc, Equal, m_origin, m_value->child(0),
+                        before->appendIntConstant(
+                            m_proc, m_origin, m_value->child(0)->type(),
+                            cases[start + i].caseValue())),
+                    cases[start + i].target(), FrequentedBlock(nextCheck));
+
+                before = nextCheck;
+            }
+
+            if (allConsecutive) {
+                before->appendNew<ControlValue>(
+                    m_proc, Jump, m_origin, cases[end - 1].target());
+            } else {
+                before->appendNew<ControlValue>(
+                    m_proc, Jump, m_origin, m_value->as<SwitchValue>()->fallThrough());
+            }
+            return;
+        }
+
+        unsigned medianIndex = (start + end) / 2;
+
+        BasicBlock* left = m_blockInsertionSet.insertAfter(m_block);
+        BasicBlock* right = m_blockInsertionSet.insertAfter(m_block);
+
+        before->appendNew<ControlValue>(
+            m_proc, Branch, m_origin,
+            before->appendNew<Value>(
+                m_proc, LessThan, m_origin, m_value->child(0),
+                before->appendIntConstant(
+                    m_proc, m_origin, m_value->child(0)->type(),
+                    cases[medianIndex].caseValue())),
+            FrequentedBlock(left), FrequentedBlock(right));
+
+        recursivelyBuildSwitch(cases, start, hardStart, medianIndex, left);
+        recursivelyBuildSwitch(cases, medianIndex, true, end, right);
+    }
     
     Procedure& m_proc;
     BlockInsertionSet m_blockInsertionSet;
@@ -186,6 +276,7 @@ private:
     BasicBlock* m_block;
     unsigned m_index;
     Value* m_value;
+    Origin m_origin;
     bool m_changed { false };
 };
 
index 7a3eca0..759af9f 100644 (file)
@@ -63,8 +63,9 @@ void SwitchValue::dumpMeta(CommaPrinter& comma, PrintStream& out) const
     out.print(comma, "fallThrough = ", fallThrough());
 }
 
-SwitchValue::SwitchValue(unsigned index, Origin origin, const FrequentedBlock& fallThrough)
-    : ControlValue(index, Switch, Void, origin)
+SwitchValue::SwitchValue(
+    unsigned index, Origin origin, Value* child, const FrequentedBlock& fallThrough)
+    : ControlValue(index, Switch, Void, origin, child)
 {
     m_successors.append(fallThrough);
 }
index 960a9c0..5f17087 100644 (file)
@@ -111,7 +111,7 @@ public:
     // contain some other case value). This removes the case that was removed.
     SwitchCase removeCase(unsigned index);
 
-    void appendCase(const SwitchCase&);
+    JS_EXPORT_PRIVATE void appendCase(const SwitchCase&);
 
 protected:
     void dumpMeta(CommaPrinter&, PrintStream&) const override;
@@ -119,7 +119,8 @@ protected:
 private:
     friend class Procedure;
 
-    SwitchValue(unsigned index, Origin, const FrequentedBlock& fallThrough);
+    JS_EXPORT_PRIVATE SwitchValue(
+        unsigned index, Origin, Value* child, const FrequentedBlock& fallThrough);
 
     Vector<int64_t> m_values;
 };
index 077606a..b91ede5 100644 (file)
@@ -35,6 +35,7 @@
 #include "B3MemoryValue.h"
 #include "B3Procedure.h"
 #include "B3StackSlotValue.h"
+#include "B3SwitchValue.h"
 #include "B3UpsilonValue.h"
 #include "B3ValueInlines.h"
 #include "CCallHelpers.h"
@@ -1266,7 +1267,7 @@ void testSShrArg32(int32_t a)
         proc, Return, Origin(),
         root->appendNew<Value>(proc, SShr, Origin(), value, value));
 
-    CHECK(compileAndRun<int32_t>(proc, a) == (a >> a));
+    CHECK(compileAndRun<int32_t>(proc, a) == (a >> (a & 31)));
 }
 
 void testSShrArgs32(int32_t a, int32_t b)
@@ -1372,7 +1373,7 @@ void testZShrArg32(uint32_t a)
         proc, Return, Origin(),
         root->appendNew<Value>(proc, ZShr, Origin(), value, value));
 
-    CHECK(compileAndRun<uint32_t>(proc, a) == (a >> a));
+    CHECK(compileAndRun<uint32_t>(proc, a) == (a >> (a & 31)));
 }
 
 void testZShrArgs32(uint32_t a, uint32_t b)
@@ -3188,6 +3189,89 @@ void testChillDiv64(int64_t num, int64_t den, int64_t res)
     }
 }
 
+void testSwitch(unsigned degree, unsigned gap = 1)
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+
+    BasicBlock* terminate = proc.addBlock();
+    terminate->appendNew<ControlValue>(
+        proc, Return, Origin(),
+        terminate->appendNew<Const32Value>(proc, Origin(), 0));
+
+    SwitchValue* switchValue = root->appendNew<SwitchValue>(
+        proc, Origin(),
+        root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+        FrequentedBlock(terminate));
+
+    for (unsigned i = 0; i < degree; ++i) {
+        BasicBlock* newBlock = proc.addBlock();
+        newBlock->appendNew<ControlValue>(
+            proc, Return, Origin(),
+            newBlock->appendNew<ArgumentRegValue>(
+                proc, Origin(), (i & 1) ? GPRInfo::argumentGPR2 : GPRInfo::argumentGPR1));
+        switchValue->appendCase(SwitchCase(gap * i, FrequentedBlock(newBlock)));
+    }
+
+    auto code = compile(proc);
+
+    for (unsigned i = 0; i < degree; ++i) {
+        CHECK(invoke<int32_t>(*code, i * gap, 42, 11) == ((i & 1) ? 11 : 42));
+        if (gap > 1) {
+            CHECK(!invoke<int32_t>(*code, i * gap + 1, 42, 11));
+            CHECK(!invoke<int32_t>(*code, i * gap - 1, 42, 11));
+        }
+    }
+
+    CHECK(!invoke<int32_t>(*code, -1, 42, 11));
+    CHECK(!invoke<int32_t>(*code, degree * gap, 42, 11));
+    CHECK(!invoke<int32_t>(*code, degree * gap + 1, 42, 11));
+}
+
+void testSwitchChillDiv(unsigned degree, unsigned gap = 1)
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+
+    Value* left = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1);
+    Value* right = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR2);
+
+    BasicBlock* terminate = proc.addBlock();
+    terminate->appendNew<ControlValue>(
+        proc, Return, Origin(),
+        terminate->appendNew<Const32Value>(proc, Origin(), 0));
+
+    SwitchValue* switchValue = root->appendNew<SwitchValue>(
+        proc, Origin(),
+        root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+        FrequentedBlock(terminate));
+
+    for (unsigned i = 0; i < degree; ++i) {
+        BasicBlock* newBlock = proc.addBlock();
+
+        newBlock->appendNew<ControlValue>(
+            proc, Return, Origin(),
+            newBlock->appendNew<Value>(
+                proc, ChillDiv, Origin(), (i & 1) ? right : left, (i & 1) ? left : right));
+        
+        switchValue->appendCase(SwitchCase(gap * i, FrequentedBlock(newBlock)));
+    }
+
+    auto code = compile(proc);
+
+    for (unsigned i = 0; i < degree; ++i) {
+        CHECK(invoke<int32_t>(*code, i * gap, 42, 11) == ((i & 1) ? 11/42 : 42/11));
+        if (gap > 1) {
+            CHECK(!invoke<int32_t>(*code, i * gap + 1, 42, 11));
+            CHECK(!invoke<int32_t>(*code, i * gap - 1, 42, 11));
+        }
+    }
+
+    CHECK(!invoke<int32_t>(*code, -1, 42, 11));
+    CHECK(!invoke<int32_t>(*code, degree * gap, 42, 11));
+    CHECK(!invoke<int32_t>(*code, degree * gap + 1, 42, 11));
+}
+
 #define RUN(test) do {                          \
         if (!shouldRun(#test))                  \
             break;                              \
@@ -3729,6 +3813,24 @@ void run(const char* filter)
     RUN(testChillDivTwice(4, 0, 6, 2, 3));
     RUN(testChillDivTwice(4, 2, 6, 0, 2));
 
+    RUN(testSwitch(0, 1));
+    RUN(testSwitch(1, 1));
+    RUN(testSwitch(2, 1));
+    RUN(testSwitch(2, 2));
+    RUN(testSwitch(10, 1));
+    RUN(testSwitch(10, 2));
+    RUN(testSwitch(100, 1));
+    RUN(testSwitch(100, 100));
+
+    RUN(testSwitchChillDiv(0, 1));
+    RUN(testSwitchChillDiv(1, 1));
+    RUN(testSwitchChillDiv(2, 1));
+    RUN(testSwitchChillDiv(2, 2));
+    RUN(testSwitchChillDiv(10, 1));
+    RUN(testSwitchChillDiv(10, 2));
+    RUN(testSwitchChillDiv(100, 1));
+    RUN(testSwitchChillDiv(100, 100));
+
     if (tasks.isEmpty())
         usage();