BBQ-Air: Emit better code for switch
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 11 Feb 2019 03:25:52 +0000 (03:25 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 11 Feb 2019 03:25:52 +0000 (03:25 +0000)
https://bugs.webkit.org/show_bug.cgi?id=194053

Reviewed by Yusuke Suzuki.

Instead of emitting a linear set of jumps for Switch, this patch
makes the BBQ-Air backend emit a binary switch.

* wasm/WasmAirIRGenerator.cpp:
(JSC::Wasm::AirIRGenerator::addSwitch):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/wasm/WasmAirIRGenerator.cpp

index 562101b..3dd3f85 100644 (file)
@@ -1,3 +1,16 @@
+2019-02-10  Saam barati  <sbarati@apple.com>
+
+        BBQ-Air: Emit better code for switch
+        https://bugs.webkit.org/show_bug.cgi?id=194053
+
+        Reviewed by Yusuke Suzuki.
+
+        Instead of emitting a linear set of jumps for Switch, this patch
+        makes the BBQ-Air backend emit a binary switch.
+
+        * wasm/WasmAirIRGenerator.cpp:
+        (JSC::Wasm::AirIRGenerator::addSwitch):
+
 2019-02-09  Yusuke Suzuki  <ysuzuki@apple.com>
 
         Unreviewed, Lexer should use isLatin1 implementation in WTF
index 8b49723..127b0ca 100644 (file)
@@ -39,6 +39,7 @@
 #include "B3PatchpointSpecial.h"
 #include "B3Procedure.h"
 #include "B3ProcedureInlines.h"
+#include "BinarySwitch.h"
 #include "ScratchRegisterAllocator.h"
 #include "VirtualRegister.h"
 #include "WasmCallingConvention.h"
@@ -1523,26 +1524,60 @@ auto AirIRGenerator::addBranch(ControlData& data, ExpressionType condition, cons
 
 auto AirIRGenerator::addSwitch(ExpressionType condition, const Vector<ControlData*>& targets, ControlData& defaultTarget, const ExpressionList& expressionStack) -> PartialResult
 {
-    for (size_t i = 0; i < targets.size(); ++i)
-        unifyValuesWithBlock(expressionStack, targets[i]->resultForBranch());
+    auto& successors = m_currentBlock->successors();
+    ASSERT(successors.isEmpty());
+    for (const auto& target : targets) {
+        unifyValuesWithBlock(expressionStack, target->resultForBranch());
+        successors.append(target->targetBlockForBranch());
+    }
     unifyValuesWithBlock(expressionStack, defaultTarget.resultForBranch());
+    successors.append(defaultTarget.targetBlockForBranch());
 
-    // FIXME: Emit either a jump table or a binary switch here.
-    // https://bugs.webkit.org/show_bug.cgi?id=194053
+    ASSERT(condition.type() == Type::I32);
 
-    for (size_t i = 0; i < targets.size(); ++i) {
-        BasicBlock* target = targets[i]->targetBlockForBranch();
-        BasicBlock* continuation = m_code.addBlock();
-        auto constant = g64();
-        append(Move, Arg::bigImm(i), constant);
-        append(Branch32, Arg::relCond(MacroAssembler::Equal), constant, condition);
-        m_currentBlock->setSuccessors(target, continuation);
+    // FIXME: We should consider dynamically switching between a jump table
+    // and a binary switch depending on the number of successors.
+    // https://bugs.webkit.org/show_bug.cgi?id=194477
 
-        m_currentBlock = continuation;
-    }
+    size_t numTargets = targets.size();
 
-    append(Jump);
-    m_currentBlock->setSuccessors(defaultTarget.targetBlockForBranch());
+    auto* patchpoint = addPatchpoint(B3::Void);
+    patchpoint->effects = B3::Effects::none();
+    patchpoint->effects.terminal = true;
+
+    patchpoint->setGenerator([=] (CCallHelpers& jit, const B3::StackmapGenerationParams& params) {
+        Vector<int64_t> cases;
+        cases.reserveInitialCapacity(numTargets);
+        for (size_t i = 0; i < numTargets; ++i)
+            cases.uncheckedAppend(i);
+
+        GPRReg valueReg = params[0].gpr();
+        BinarySwitch binarySwitch(valueReg, cases, BinarySwitch::Int32);
+
+        Vector<CCallHelpers::Jump> caseJumps;
+        caseJumps.resize(numTargets);
+
+        while (binarySwitch.advance(jit)) {
+            unsigned value = binarySwitch.caseValue();
+            unsigned index = binarySwitch.caseIndex();
+            ASSERT_UNUSED(value, value == index);
+            ASSERT(index < numTargets);
+            caseJumps[index] = jit.jump();
+        }
+
+        CCallHelpers::JumpList fallThrough = binarySwitch.fallThrough();
+
+        Vector<Box<CCallHelpers::Label>> successorLabels = params.successorLabels();
+        ASSERT(successorLabels.size() == caseJumps.size() + 1);
+
+        params.addLatePath([=, caseJumps = WTFMove(caseJumps), successorLabels = WTFMove(successorLabels)] (CCallHelpers& jit) {
+            for (size_t i = 0; i < numTargets; ++i)
+                caseJumps[i].linkTo(*successorLabels[i], &jit);                
+            fallThrough.linkTo(*successorLabels[numTargets], &jit);
+        });
+    });
+
+    emitPatchpoint(patchpoint, TypedTmp(), condition);
 
     return { };
 }