B3::lowerMacros forgets to before->updatePredecessorsAfter() when lowering ChillMod...
[WebKit-https.git] / Source / JavaScriptCore / b3 / B3LowerMacros.cpp
index 17aca90..fa6de93 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 
 #if ENABLE(B3_JIT)
 
+#include "AllowMacroScratchRegisterUsage.h"
 #include "B3BasicBlockInlines.h"
 #include "B3BlockInsertionSet.h"
-#include "B3ControlValue.h"
+#include "B3CCallValue.h"
+#include "B3CaseCollectionInlines.h"
+#include "B3ConstPtrValue.h"
 #include "B3InsertionSetInlines.h"
+#include "B3MemoryValue.h"
+#include "B3PatchpointValue.h"
 #include "B3PhaseScope.h"
 #include "B3ProcedureInlines.h"
+#include "B3StackmapGenerationParams.h"
+#include "B3SwitchValue.h"
 #include "B3UpsilonValue.h"
 #include "B3ValueInlines.h"
+#include "CCallHelpers.h"
+#include "LinkBuffer.h"
+#include <cmath>
+#include <wtf/BitVector.h>
 
 namespace JSC { namespace B3 {
 
@@ -57,8 +68,10 @@ public:
             processCurrentBlock();
         }
         m_changed |= m_blockInsertionSet.execute();
-        if (m_changed)
+        if (m_changed) {
             m_proc.resetReachability();
+            m_proc.invalidateCFG();
+        }
         return m_changed;
     }
     
@@ -67,111 +80,98 @@ 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 Mod: {
+                double (*fmodDouble)(double, double) = fmod;
+                if (m_value->type() == Double) {
+                    Value* functionAddress = m_insertionSet.insert<ConstPtrValue>(m_index, m_origin, fmodDouble);
+                    Value* result = m_insertionSet.insert<CCallValue>(m_index, Double, m_origin,
+                        Effects::none(),
+                        functionAddress,
+                        m_value->child(0),
+                        m_value->child(1));
+                    m_value->replaceWithIdentity(result);
+                    m_changed = true;
+                } else if (m_value->type() == Float) {
+                    Value* numeratorAsDouble = m_insertionSet.insert<Value>(m_index, FloatToDouble, m_origin, m_value->child(0));
+                    Value* denominatorAsDouble = m_insertionSet.insert<Value>(m_index, FloatToDouble, m_origin, m_value->child(1));
+                    Value* functionAddress = m_insertionSet.insert<ConstPtrValue>(m_index, m_origin, fmodDouble);
+                    Value* doubleMod = m_insertionSet.insert<CCallValue>(m_index, Double, m_origin,
+                        Effects::none(),
+                        functionAddress,
+                        numeratorAsDouble,
+                        denominatorAsDouble);
+                    Value* result = m_insertionSet.insert<Value>(m_index, DoubleToFloat, m_origin, doubleMod);
+                    m_value->replaceWithIdentity(result);
+                    m_changed = true;
+                } else if (isARM64()) {
+                    Value* divResult = m_insertionSet.insert<Value>(m_index, ChillDiv, m_origin, m_value->child(0), m_value->child(1));
+                    Value* multipliedBack = m_insertionSet.insert<Value>(m_index, Mul, m_origin, divResult, m_value->child(1));
+                    Value* result = m_insertionSet.insert<Value>(m_index, Sub, m_origin, m_value->child(0), multipliedBack);
+                    m_value->replaceWithIdentity(result);
+                    m_changed = true;
+                }
+                break;
+            }
             case ChillDiv: {
-                // ARM supports this instruction natively.
-                if (isARM64())
-                    break;
+                makeDivisionChill(Div);
+                break;
+            }
 
-                m_changed = true;
+            case ChillMod: {
+                if (isARM64()) {
+                    BasicBlock* before = m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
+                    BasicBlock* zeroDenCase = m_blockInsertionSet.insertBefore(m_block);
+                    BasicBlock* normalModCase = m_blockInsertionSet.insertBefore(m_block);
 
-                // We implement "res = ChillDiv(num, den)" as follows:
-                //
-                //     if (den + 1 <=_unsigned 1) {
-                //         if (!den) {
-                //             res = 0;
-                //             goto done;
-                //         }
-                //         if (num == -2147483648) {
-                //             res = num;
-                //             goto done;
-                //         }
-                //     }
-                //     res = num / dev;
-                // done:
-
-                Value* num = m_value->child(0);
-                Value* den = m_value->child(1);
-
-                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),
-                    one);
-
-                BasicBlock* before =
-                    m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
-
-                BasicBlock* normalDivCase = m_blockInsertionSet.insertBefore(m_block);
-                BasicBlock* shadyDenCase = m_blockInsertionSet.insertBefore(m_block);
-                BasicBlock* zeroDenCase = m_blockInsertionSet.insertBefore(m_block);
-                BasicBlock* neg1DenCase = m_blockInsertionSet.insertBefore(m_block);
-                BasicBlock* intMinCase = m_blockInsertionSet.insertBefore(m_block);
-
-                before->replaceLastWithNew<ControlValue>(
-                    m_proc, Branch, m_value->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));
-                normalDivCase->appendNew<ControlValue>(
-                    m_proc, Jump, m_value->origin(), FrequentedBlock(m_block));
-
-                shadyDenCase->appendNew<ControlValue>(
-                    m_proc, Branch, m_value->origin(), den,
-                    FrequentedBlock(neg1DenCase, FrequencyClass::Normal),
-                    FrequentedBlock(zeroDenCase, FrequencyClass::Rare));
-
-                UpsilonValue* zeroResult = zeroDenCase->appendNew<UpsilonValue>(
-                    m_proc, m_value->origin(),
-                    zeroDenCase->appendIntConstant(m_proc, m_value, 0));
-                zeroDenCase->appendNew<ControlValue>(
-                    m_proc, Jump, m_value->origin(), FrequentedBlock(m_block));
-
-                int64_t badNumeratorConst;
-                switch (m_value->type()) {
-                case Int32:
-                    badNumeratorConst = std::numeric_limits<int32_t>::min();
-                    break;
-                case Int64:
-                    badNumeratorConst = std::numeric_limits<int64_t>::min();
-                    break;
-                default:
-                    ASSERT_NOT_REACHED();
-                    badNumeratorConst = 0;
-                }
+                    before->replaceLastWithNew<Value>(m_proc, Branch, m_origin, m_value->child(1));
+                    before->setSuccessors(
+                        FrequentedBlock(normalModCase, FrequencyClass::Normal),
+                        FrequentedBlock(zeroDenCase, FrequencyClass::Rare));
 
-                Value* badNumerator =
-                    neg1DenCase->appendIntConstant(m_proc, m_value, badNumeratorConst);
-
-                neg1DenCase->appendNew<ControlValue>(
-                    m_proc, Branch, m_value->origin(),
-                    neg1DenCase->appendNew<Value>(
-                        m_proc, Equal, m_value->origin(), num, badNumerator),
-                    FrequentedBlock(intMinCase, FrequencyClass::Rare),
-                    FrequentedBlock(normalDivCase, FrequencyClass::Normal));
-
-                UpsilonValue* intMinResult = intMinCase->appendNew<UpsilonValue>(
-                    m_proc, m_value->origin(), badNumerator);
-                intMinCase->appendNew<ControlValue>(
-                    m_proc, Jump, m_value->origin(), FrequentedBlock(m_block));
-
-                Value* phi = m_insertionSet.insert<Value>(
-                    m_index, Phi, m_value->type(), m_value->origin());
-                normalResult->setPhi(phi);
-                zeroResult->setPhi(phi);
-                intMinResult->setPhi(phi);
-
-                m_value->replaceWithIdentity(phi);
-                before->updatePredecessorsAfter();
+                    Value* divResult = normalModCase->appendNew<Value>(m_proc, ChillDiv, m_origin, m_value->child(0), m_value->child(1));
+                    Value* multipliedBack = normalModCase->appendNew<Value>(m_proc, Mul, m_origin, divResult, m_value->child(1));
+                    Value* result = normalModCase->appendNew<Value>(m_proc, Sub, m_origin, m_value->child(0), multipliedBack);
+                    UpsilonValue* normalResult = normalModCase->appendNew<UpsilonValue>(m_proc, m_origin, result);
+                    normalModCase->appendNew<Value>(m_proc, Jump, m_origin);
+                    normalModCase->setSuccessors(FrequentedBlock(m_block));
+
+                    UpsilonValue* zeroResult = zeroDenCase->appendNew<UpsilonValue>(
+                        m_proc, m_origin,
+                        zeroDenCase->appendIntConstant(m_proc, m_value, 0));
+                    zeroDenCase->appendNew<Value>(m_proc, Jump, m_origin);
+                    zeroDenCase->setSuccessors(FrequentedBlock(m_block));
+
+                    Value* phi = m_insertionSet.insert<Value>(m_index, Phi, m_value->type(), m_origin);
+                    normalResult->setPhi(phi);
+                    zeroResult->setPhi(phi);
+                    m_value->replaceWithIdentity(phi);
+                    before->updatePredecessorsAfter();
+                    m_changed = true;
+                } else
+                    makeDivisionChill(Mod);
                 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(m_block))
+                    cases.append(switchCase);
+                std::sort(
+                    cases.begin(), cases.end(),
+                    [] (const SwitchCase& left, const SwitchCase& right) {
+                        return left.caseValue() < right.caseValue();
+                    });
+                FrequentedBlock fallThrough = m_block->fallThrough();
+                m_block->values().removeLast();
+                recursivelyBuildSwitch(cases, fallThrough, 0, false, cases.size(), m_block);
+                m_proc.deleteValue(switchValue);
+                m_block->updatePredecessorsAfter();
+                m_changed = true;
+                break;
+            }
 
             default:
                 break;
@@ -179,6 +179,280 @@ private:
         }
         m_insertionSet.execute(m_block);
     }
+
+    void makeDivisionChill(Opcode nonChillOpcode)
+    {
+        ASSERT(nonChillOpcode == Div || nonChillOpcode == Mod);
+
+        // ARM supports this instruction natively.
+        if (isARM64())
+            return;
+
+        // We implement "res = ChillDiv/ChillMod(num, den)" as follows:
+        //
+        //     if (den + 1 <=_unsigned 1) {
+        //         if (!den) {
+        //             res = 0;
+        //             goto done;
+        //         }
+        //         if (num == -2147483648) {
+        //             res = isDiv ? num : 0;
+        //             goto done;
+        //         }
+        //     }
+        //     res = num (/ or %) dev;
+        // done:
+        m_changed = true;
+
+        Value* num = m_value->child(0);
+        Value* den = m_value->child(1);
+
+        Value* one = m_insertionSet.insertIntConstant(m_index, m_value, 1);
+        Value* isDenOK = m_insertionSet.insert<Value>(
+            m_index, Above, m_origin,
+            m_insertionSet.insert<Value>(m_index, Add, m_origin, den, one),
+            one);
+
+        BasicBlock* before = m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
+
+        BasicBlock* normalDivCase = m_blockInsertionSet.insertBefore(m_block);
+        BasicBlock* shadyDenCase = m_blockInsertionSet.insertBefore(m_block);
+        BasicBlock* zeroDenCase = m_blockInsertionSet.insertBefore(m_block);
+        BasicBlock* neg1DenCase = m_blockInsertionSet.insertBefore(m_block);
+        BasicBlock* intMinCase = m_blockInsertionSet.insertBefore(m_block);
+
+        before->replaceLastWithNew<Value>(m_proc, Branch, m_origin, isDenOK);
+        before->setSuccessors(
+            FrequentedBlock(normalDivCase, FrequencyClass::Normal),
+            FrequentedBlock(shadyDenCase, FrequencyClass::Rare));
+
+        UpsilonValue* normalResult = normalDivCase->appendNew<UpsilonValue>(
+            m_proc, m_origin,
+            normalDivCase->appendNew<Value>(m_proc, nonChillOpcode, m_origin, num, den));
+        normalDivCase->appendNew<Value>(m_proc, Jump, m_origin);
+        normalDivCase->setSuccessors(FrequentedBlock(m_block));
+
+        shadyDenCase->appendNew<Value>(m_proc, Branch, m_origin, den);
+        shadyDenCase->setSuccessors(
+            FrequentedBlock(neg1DenCase, FrequencyClass::Normal),
+            FrequentedBlock(zeroDenCase, FrequencyClass::Rare));
+
+        UpsilonValue* zeroResult = zeroDenCase->appendNew<UpsilonValue>(
+            m_proc, m_origin,
+            zeroDenCase->appendIntConstant(m_proc, m_value, 0));
+        zeroDenCase->appendNew<Value>(m_proc, Jump, m_origin);
+        zeroDenCase->setSuccessors(FrequentedBlock(m_block));
+
+        int64_t badNumeratorConst = 0;
+        switch (m_value->type()) {
+        case Int32:
+            badNumeratorConst = std::numeric_limits<int32_t>::min();
+            break;
+        case Int64:
+            badNumeratorConst = std::numeric_limits<int64_t>::min();
+            break;
+        default:
+            ASSERT_NOT_REACHED();
+            badNumeratorConst = 0;
+        }
+
+        Value* badNumerator =
+            neg1DenCase->appendIntConstant(m_proc, m_value, badNumeratorConst);
+
+        neg1DenCase->appendNew<Value>(
+            m_proc, Branch, m_origin,
+            neg1DenCase->appendNew<Value>(
+                m_proc, Equal, m_origin, num, badNumerator));
+        neg1DenCase->setSuccessors(
+            FrequentedBlock(intMinCase, FrequencyClass::Rare),
+            FrequentedBlock(normalDivCase, FrequencyClass::Normal));
+
+        Value* intMinResult = nonChillOpcode == Div ? badNumerator : intMinCase->appendIntConstant(m_proc, m_value, 0);
+        UpsilonValue* intMinResultUpsilon = intMinCase->appendNew<UpsilonValue>(
+            m_proc, m_origin, intMinResult);
+        intMinCase->appendNew<Value>(m_proc, Jump, m_origin);
+        intMinCase->setSuccessors(FrequentedBlock(m_block));
+
+        Value* phi = m_insertionSet.insert<Value>(
+            m_index, Phi, m_value->type(), m_origin);
+        normalResult->setPhi(phi);
+        zeroResult->setPhi(phi);
+        intMinResultUpsilon->setPhi(phi);
+
+        m_value->replaceWithIdentity(phi);
+        before->updatePredecessorsAfter();
+    }
+
+    void recursivelyBuildSwitch(
+        const Vector<SwitchCase>& cases, FrequentedBlock fallThrough, unsigned start, bool hardStart,
+        unsigned end, BasicBlock* before)
+    {
+        Value* child = m_value->child(0);
+        Type type = child->type();
+        
+        // It's a good idea to use a table-based switch in some cases: the number of cases has to be
+        // large enough and they have to be dense enough. This could probably be improved a lot. For
+        // example, we could still use a jump table in cases where the inputs are sparse so long as we
+        // shift off the uninteresting bits. On the other hand, it's not clear that this would
+        // actually be any better than what we have done here and it's not clear that it would be
+        // better than a binary switch.
+        const unsigned minCasesForTable = 7;
+        const unsigned densityLimit = 4;
+        if (end - start >= minCasesForTable) {
+            int64_t firstValue = cases[start].caseValue();
+            int64_t lastValue = cases[end - 1].caseValue();
+            if ((lastValue - firstValue + 1) / (end - start) < densityLimit) {
+                BasicBlock* switchBlock = m_blockInsertionSet.insertAfter(m_block);
+                Value* index = before->appendNew<Value>(
+                    m_proc, Sub, m_origin, child,
+                    before->appendIntConstant(m_proc, m_origin, type, firstValue));
+                before->appendNew<Value>(
+                    m_proc, Branch, m_origin,
+                    before->appendNew<Value>(
+                        m_proc, Above, m_origin, index,
+                        before->appendIntConstant(m_proc, m_origin, type, lastValue - firstValue)));
+                before->setSuccessors(fallThrough, FrequentedBlock(switchBlock));
+                
+                size_t tableSize = lastValue - firstValue + 1;
+                
+                if (index->type() != pointerType() && index->type() == Int32)
+                    index = switchBlock->appendNew<Value>(m_proc, ZExt32, m_origin, index);
+                
+                PatchpointValue* patchpoint =
+                    switchBlock->appendNew<PatchpointValue>(m_proc, Void, m_origin);
+
+                // Even though this loads from the jump table, the jump table is immutable. For the
+                // purpose of alias analysis, reading something immutable is like reading nothing.
+                patchpoint->effects = Effects();
+                patchpoint->effects.terminal = true;
+                
+                patchpoint->appendSomeRegister(index);
+                patchpoint->numGPScratchRegisters++;
+                // Technically, we don't have to clobber macro registers on X86_64. This is probably
+                // OK though.
+                patchpoint->clobber(RegisterSet::macroScratchRegisters());
+                
+                BitVector handledIndices;
+                for (unsigned i = start; i < end; ++i) {
+                    FrequentedBlock block = cases[i].target();
+                    int64_t value = cases[i].caseValue();
+                    switchBlock->appendSuccessor(block);
+                    size_t index = value - firstValue;
+                    ASSERT(!handledIndices.get(index));
+                    handledIndices.set(index);
+                }
+                
+                bool hasUnhandledIndex = false;
+                for (unsigned i = 0; i < tableSize; ++i) {
+                    if (!handledIndices.get(i)) {
+                        hasUnhandledIndex = true;
+                        break;
+                    }
+                }
+                
+                if (hasUnhandledIndex)
+                    switchBlock->appendSuccessor(fallThrough);
+
+                patchpoint->setGenerator(
+                    [=] (CCallHelpers& jit, const StackmapGenerationParams& params) {
+                        AllowMacroScratchRegisterUsage allowScratch(jit);
+                        
+                        MacroAssemblerCodePtr* jumpTable = static_cast<MacroAssemblerCodePtr*>(
+                            params.proc().addDataSection(sizeof(MacroAssemblerCodePtr) * tableSize));
+                        
+                        GPRReg index = params[0].gpr();
+                        GPRReg scratch = params.gpScratch(0);
+                        
+                        jit.move(CCallHelpers::TrustedImmPtr(jumpTable), scratch);
+                        jit.jump(CCallHelpers::BaseIndex(scratch, index, CCallHelpers::timesPtr()));
+                        
+                        // These labels are guaranteed to be populated before either late paths or
+                        // link tasks run.
+                        Vector<Box<CCallHelpers::Label>> labels = params.successorLabels();
+                        
+                        jit.addLinkTask(
+                            [=] (LinkBuffer& linkBuffer) {
+                                if (hasUnhandledIndex) {
+                                    MacroAssemblerCodePtr fallThrough =
+                                        linkBuffer.locationOf(*labels.last());
+                                    for (unsigned i = tableSize; i--;)
+                                        jumpTable[i] = fallThrough;
+                                }
+                                
+                                unsigned labelIndex = 0;
+                                for (unsigned tableIndex : handledIndices) {
+                                    jumpTable[tableIndex] =
+                                        linkBuffer.locationOf(*labels[labelIndex++]);
+                                }
+                            });
+                    });
+                return;
+            }
+        }
+        
+        // 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<Value>(
+                    m_proc, Branch, m_origin,
+                    before->appendNew<Value>(
+                        m_proc, Equal, m_origin, child,
+                        before->appendIntConstant(
+                            m_proc, m_origin, type,
+                            cases[start + i].caseValue())));
+                before->setSuccessors(cases[start + i].target(), FrequentedBlock(nextCheck));
+
+                before = nextCheck;
+            }
+
+            before->appendNew<Value>(m_proc, Jump, m_origin);
+            if (allConsecutive)
+                before->setSuccessors(cases[end - 1].target());
+            else
+                before->setSuccessors(fallThrough);
+            return;
+        }
+
+        unsigned medianIndex = (start + end) / 2;
+
+        BasicBlock* left = m_blockInsertionSet.insertAfter(m_block);
+        BasicBlock* right = m_blockInsertionSet.insertAfter(m_block);
+
+        before->appendNew<Value>(
+            m_proc, Branch, m_origin,
+            before->appendNew<Value>(
+                m_proc, LessThan, m_origin, child,
+                before->appendIntConstant(
+                    m_proc, m_origin, type,
+                    cases[medianIndex].caseValue())));
+        before->setSuccessors(FrequentedBlock(left), FrequentedBlock(right));
+
+        recursivelyBuildSwitch(cases, fallThrough, start, hardStart, medianIndex, left);
+        recursivelyBuildSwitch(cases, fallThrough, medianIndex, true, end, right);
+    }
     
     Procedure& m_proc;
     BlockInsertionSet m_blockInsertionSet;
@@ -186,6 +460,7 @@ private:
     BasicBlock* m_block;
     unsigned m_index;
     Value* m_value;
+    Origin m_origin;
     bool m_changed { false };
 };