Changeset 5708


Ignore:
Timestamp:
Oct 25, 2017, 10:26:15 PM (16 months ago)
Author:
cameron
Message:

Progress on indexed advance

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp

    r5706 r5708  
    111111    if (mHasLongAdvance) {
    112112        kernel->addScalar(iBuilder->getSizeTy(), "CarryBlockIndex");
     113    }
     114    for (unsigned i = 0; i < mIndexedLongAdvanceTotal; i++) {
     115        kernel->addScalar(iBuilder->getSizeTy(), "LongAdvancePosition" + std::to_string(i));
    113116    }
    114117}
     
    610613}
    611614
    612 Value * CarryManager::indexedAdvanceCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const IndexedAdvance * const advance, Value * const value, Value * const index_strm) {
    613     llvm::report_fatal_error("IndexedAdvance not yet supported.");
    614 }
     615Value * CarryManager::indexedAdvanceCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> & b, const IndexedAdvance * const advance, Value * const strm, Value * const index_strm) {
     616    const auto shiftAmount = advance->getAmount();
     617    if (LLVM_LIKELY(shiftAmount < LONG_ADVANCE_BREAKPOINT)) {
     618        Value * const carryIn = getNextCarryIn(b);
     619        unsigned bitWidth = sizeof(size_t) * 8;
     620        Value * popcount_f = Intrinsic::getDeclaration(b->getModule(), Intrinsic::ctpop, b->getSizeTy());
     621        Value * PEXT_f = nullptr;
     622        Value * PDEP_f = nullptr;
     623        if (bitWidth == 64) {
     624            PEXT_f = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_bmi_pext_64);
     625            PDEP_f = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_bmi_pdep_64);
     626        }
     627        else if ((bitWidth == 32)  && (shiftAmount < 32)) {
     628            PEXT_f = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_bmi_pext_32);
     629            PDEP_f = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_bmi_pdep_32);
     630        }
     631        else {
     632            llvm::report_fatal_error("indexed_advance unsupported bit width");
     633        }
     634        Value * carry = b->mvmd_extract(bitWidth, carryIn, 0);
     635        Value * result = b->allZeroes();
     636        for (unsigned i = 0; i < b->getBitBlockWidth()/bitWidth; i++) {
     637            Value * s = b->mvmd_extract(bitWidth, strm, i);
     638            Value * ix = b->mvmd_extract(bitWidth, index_strm, i);
     639            Value * ix_popcnt = b->CreateCall(popcount_f, {ix});
     640            Value * bits = b->CreateCall(PEXT_f, {s, ix});
     641            Value * adv = b->CreateOr(b->CreateShl(bits, shiftAmount), carry);
     642            Value * overflow = b->CreateLShr(bits, bitWidth - shiftAmount);
     643            result = b->mvmd_insert(bitWidth, result, b->CreateCall(PDEP_f, {adv, ix}), i);
     644            carry = b->CreateOr(b->CreateLShr(adv, ix_popcnt), b->CreateShl(overflow, b->CreateSub(b->getSize(bitWidth), ix_popcnt)));
     645        }
     646        setNextCarryOut(b, carry);
     647        return result;
     648    } else {
     649        llvm::report_fatal_error("IndexedAdvance > LONG_ADVANCE_BREAKPOINT not yet supported.");
     650    }
     651}
     652
    615653
    616654/** ------------------------------------------------------------------------------------------------------------- *
     
    905943    std::vector<Type *> state;
    906944    for (const Statement * stmt : *scope) {
    907         if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
    908             const auto amount = cast<Advance>(stmt)->getAmount();
     945        if (LLVM_UNLIKELY(isa<Advance>(stmt) || isa<IndexedAdvance>(stmt))) {
     946            int64_t amount;
     947            if (isa<Advance>(stmt)) amount = cast<Advance>(stmt)->getAmount();
     948            else amount = cast<IndexedAdvance>(stmt)->getAmount();
    909949            Type * type = carryPackType;
    910950            if (LLVM_UNLIKELY(amount >= LONG_ADVANCE_BREAKPOINT)) {
     
    917957                    state.push_back(ArrayType::get(blockTy, summarySize));
    918958                }
    919                 mHasLongAdvance = true;               
     959                mHasLongAdvance = true;
     960                if (isa<IndexedAdvance>(stmt)) mIndexedLongAdvanceTotal++;
    920961            }
    921962            state.push_back(type);
    922         } else if (LLVM_UNLIKELY(isa<IndexedAdvance>(stmt))) {
    923             // The carry data for the indexed advance stores N bits of carry data,
    924             // organized in packs that can be processed with GR instructions (such as PEXT, PDEP, popcount).
    925             // A circular buffer is used.  Because the number of bits to be dequeued
    926             // and enqueued is variable (based on the popcount of the index), an extra
    927             // pack stores the offset position in the circular buffer.
    928             const auto amount = cast<IndexedAdvance>(stmt)->getAmount();
    929             const auto packWidth = sizeof(size_t) * 8;
    930             const auto packs = ceil_udiv(amount, packWidth);
    931             state.push_back(ArrayType::get(iBuilder->getSizeTy(), nearest_pow2(packs) + 1));
    932963        } else if (LLVM_UNLIKELY(isNonAdvanceCarryGeneratingStatement(stmt))) {
    933964            state.push_back(carryPackType);
     
    9881019, mIfDepth(0)
    9891020, mHasLongAdvance(false)
     1021, mIndexedLongAdvanceTotal(0)
     1022, mIndexedLongAdvanceIndex(0)
    9901023, mHasNonCarryCollapsingLoops(false)
    9911024, mHasLoop(false)
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.h

    r5706 r5708  
    122122
    123123    bool                                            mHasLongAdvance;
     124    unsigned                                        mIndexedLongAdvanceTotal;
     125    unsigned                                        mIndexedLongAdvanceIndex;
    124126    bool                                            mHasNonCarryCollapsingLoops;
    125127    bool                                            mHasLoop;
  • icGREP/icgrep-devel/icgrep/pablo/carrypack_manager.cpp

    r5705 r5708  
    136136    if (mHasLongAdvance) {
    137137        kernel->addScalar(iBuilder->getSizeTy(), "CarryBlockIndex");
     138    }
     139    for (unsigned i = 0; i < mIndexedLongAdvanceTotal; i++) {
     140        kernel->addScalar(iBuilder->getSizeTy(), "LongAdvancePosition" + std::to_string(i));
    138141    }
    139142}
     
    11031106            if (carryGroup.groupSize == 0) {
    11041107                Type * packTy = carryPackTy;
    1105                 if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
    1106                     const auto amount = cast<Advance>(stmt)->getAmount();
     1108                if (LLVM_UNLIKELY(isa<Advance>(stmt) || isa<IndexedAdvance>(stmt))) {
     1109                    const auto amount = isa<Advance>(stmt) ? : cast<Advance>(stmt)->getAmount() : cast<IndexedAdvance>(stmt)->getAmount();
    11071110                    if (LLVM_UNLIKELY(amount >= mElementWidth)) {
    11081111                        if (LLVM_UNLIKELY(ifDepth > 0 && amount > iBuilder->getBitBlockWidth())) {
     
    11111114                        }
    11121115                        mHasLongAdvance = true;
     1116                        if isa<IndexedAdvance>(stmt) mIndexedLongAdvanceTotal++;
    11131117                        const auto blocks = ceil_udiv(amount, iBuilder->getBitBlockWidth());
    11141118                        packTy = ArrayType::get(carryTy, nearest_pow2(blocks + ((loopDepth != 0) ? 1 : 0)));
    11151119                    }
    1116                 }
    1117                 if (LLVM_UNLIKELY(isa<IndexedAdvance>(stmt))) {
    1118                     // The carry data for the indexed advance stores N bits of carry data,
    1119                     // organized in packs that can be processed with GR instructions (such as PEXT, PDEP, popcount).
    1120                     // A circular buffer is used.  Because the number of bits to be dequeued
    1121                     // and enqueued is variable (based on the popcount of the index), an extra
    1122                     // pack stores the offset position in the circular buffer.
    1123                     const auto amount = cast<IndexedAdvance>(stmt)->getAmount();
    1124                     const auto packWidth = sizeof(size_t) * 8;
    1125                     const auto packs = ceil_udiv(amount, packWidth);
    1126                     packTy = ArrayType::get(iBuilder->getSizeTy(), nearest_pow2(packs) + 1);
    11271120                }
    11281121                state.push_back(packTy);
     
    11901183, mIfDepth(0)
    11911184, mHasLongAdvance(false)
     1185, mIndexedLongAdvanceTotal(0)
     1186, mIndexedLongAdvanceIndex(0)
    11921187, mHasNonCarryCollapsingLoops(false)
    11931188, mHasLoop(false)
  • icGREP/icgrep-devel/icgrep/pablo/carrypack_manager.h

    r5705 r5708  
    150150
    151151    bool                                            mHasLongAdvance;
     152    unsigned                                        mIndexedLongAdvanceTotal;
     153    unsigned                                        mIndexedLongAdvanceIndex;
    152154    bool                                            mHasNonCarryCollapsingLoops;
    153155    bool                                            mHasLoop;
Note: See TracChangeset for help on using the changeset viewer.