| /* |
| * 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 |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
| * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "config.h" |
| #include "B3LowerMacros.h" |
| |
| #if ENABLE(B3_JIT) |
| |
| #include "AllowMacroScratchRegisterUsage.h" |
| #include "B3BasicBlockInlines.h" |
| #include "B3BlockInsertionSet.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 { |
| |
| namespace { |
| |
| class LowerMacros { |
| public: |
| LowerMacros(Procedure& proc) |
| : m_proc(proc) |
| , m_blockInsertionSet(proc) |
| , m_insertionSet(proc) |
| { |
| } |
| |
| bool run() |
| { |
| for (BasicBlock* block : m_proc) { |
| m_block = block; |
| processCurrentBlock(); |
| } |
| m_changed |= m_blockInsertionSet.execute(); |
| if (m_changed) { |
| m_proc.resetReachability(); |
| m_proc.invalidateCFG(); |
| } |
| return m_changed; |
| } |
| |
| private: |
| void processCurrentBlock() |
| { |
| 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: { |
| makeDivisionChill(Div); |
| break; |
| } |
| |
| 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); |
| |
| before->replaceLastWithNew<Value>(m_proc, Branch, m_origin, m_value->child(1)); |
| before->setSuccessors( |
| FrequentedBlock(normalModCase, FrequencyClass::Normal), |
| FrequentedBlock(zeroDenCase, FrequencyClass::Rare)); |
| |
| 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); |
| m_changed = true; |
| } else |
| makeDivisionChill(Mod); |
| break; |
| } |
| |
| 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; |
| } |
| } |
| 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; |
| InsertionSet m_insertionSet; |
| BasicBlock* m_block; |
| unsigned m_index; |
| Value* m_value; |
| Origin m_origin; |
| bool m_changed { false }; |
| }; |
| |
| bool lowerMacrosImpl(Procedure& proc) |
| { |
| LowerMacros lowerMacros(proc); |
| return lowerMacros.run(); |
| } |
| |
| } // anonymous namespace |
| |
| bool lowerMacros(Procedure& proc) |
| { |
| PhaseScope phaseScope(proc, "lowerMacros"); |
| bool result = lowerMacrosImpl(proc); |
| if (shouldValidateIR()) |
| RELEASE_ASSERT(!lowerMacrosImpl(proc)); |
| return result; |
| } |
| |
| } } // namespace JSC::B3 |
| |
| #endif // ENABLE(B3_JIT) |
| |
