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

Progress on indexed advance

File:
1 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)
Note: See TracChangeset for help on using the changeset viewer.