Changeset 5989 for icGREP


Ignore:
Timestamp:
Apr 25, 2018, 2:57:33 PM (13 months ago)
Author:
cameron
Message:

AbortOnNull? functionality - initial check-in

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/grep/grep_engine.cpp

    r5971 r5989  
    7474namespace grep {
    7575   
     76extern "C" void signal_dispatcher(intptr_t callback_object_addr, unsigned signal) {
     77    reinterpret_cast<GrepCallBackObject *>(callback_object_addr)->handle_signal(signal);
     78}
     79   
     80void GrepCallBackObject::handle_signal(unsigned s) {
     81    if (static_cast<GrepSignal>(s) == GrepSignal::BinaryFile) {
     82        mBinaryFile = true;
     83    } else {
     84        llvm::report_fatal_error("Unknown GrepSignal");
     85    }
     86}
    7687
    7788extern "C" void accumulate_match_wrapper(intptr_t accum_addr, const size_t lineNum, char * line_start, char * line_end) {
     
    231242}
    232243   
    233 std::pair<StreamSetBuffer *, StreamSetBuffer *> GrepEngine::grepPipeline(StreamSetBuffer * ByteStream) {
     244std::pair<StreamSetBuffer *, StreamSetBuffer *> GrepEngine::grepPipeline(StreamSetBuffer * ByteStream, Value * callback_object_addr) {
    234245    auto & idb = mGrepDriver->getBuilder();
    235246    const unsigned segmentSize = codegen::SegmentSize;
     
    249260        anyGCB |= hasGCB[i];
    250261    }
     262    StreamSetBuffer * SourceStream = ByteStream;
     263    ByteStream = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 8), baseBufferSize);
     264    kernel::Kernel * binaryCheckK = mGrepDriver->addKernelInstance<kernel::AbortOnNull>(idb);
     265    binaryCheckK->setInitialArguments({ConstantInt::get(idb->getIntAddrTy(), reinterpret_cast<intptr_t>(callback_object_addr))});
     266    mGrepDriver->makeKernelCall(binaryCheckK, {SourceStream}, {ByteStream});
     267    mGrepDriver->LinkFunction(*binaryCheckK, "signal_dispatcher", &signal_dispatcher);
     268
    251269    StreamSetBuffer * LineBreakStream = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
    252270    std::vector<StreamSetBuffer *> MatchResultsBufs(nREs);
     
    450468    const unsigned encodingBits = 8;
    451469
    452     Function * mainFunc = cast<Function>(M->getOrInsertFunction("Main", idb->getInt64Ty(), idb->getInt8Ty(), idb->getInt32Ty(), nullptr));
     470    Function * mainFunc = cast<Function>(M->getOrInsertFunction("Main", idb->getInt64Ty(), idb->getInt8Ty(), idb->getInt32Ty(), idb->getIntAddrTy(), nullptr));
    453471    mainFunc->setCallingConv(CallingConv::C);
    454472    idb->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", mainFunc, 0));
     
    459477    Value * const fileDescriptor = &*(args++);
    460478    fileDescriptor->setName("fileDescriptor");
     479    Value * call_back_object = &*(args++);
     480    call_back_object->setName("call_back_object");
    461481
    462482    StreamSetBuffer * ByteStream = mGrepDriver->addBuffer<SourceBuffer>(idb, idb->getStreamSetTy(1, encodingBits));
     
    467487    StreamSetBuffer * LineBreakStream;
    468488    StreamSetBuffer * Matches;
    469     std::tie(LineBreakStream, Matches) = grepPipeline(ByteStream);
     489    std::tie(LineBreakStream, Matches) = grepPipeline(ByteStream, call_back_object);
    470490
    471491    kernel::Kernel * matchCountK = mGrepDriver->addKernelInstance<kernel::PopcountKernel>(idb);
     
    480500    mGrepDriver->finalizeObject();
    481501}
    482 
    483502
    484503//
     
    547566    StreamSetBuffer * LineBreakStream;
    548567    StreamSetBuffer * Matches;
    549     std::tie(LineBreakStream, Matches) = grepPipeline(ByteStream);
     568    std::tie(LineBreakStream, Matches) = grepPipeline(ByteStream, match_accumulator);
    550569
    551570    kernel::Kernel * scanMatchK = mGrepDriver->addKernelInstance<kernel::ScanMatchKernel>(idb);
     
    567586
    568587uint64_t GrepEngine::doGrep(const std::string & fileName, std::ostringstream & strm) {
    569     typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor);
     588    typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor, intptr_t callback_addr);
    570589    using namespace boost::filesystem;
    571590    path p(fileName);
     
    578597    int32_t fileDescriptor = openFile(fileName, strm);
    579598    if (fileDescriptor == -1) return 0;
    580 
    581     uint64_t grepResult = f(useMMap, fileDescriptor);
     599    GrepCallBackObject handler;
     600    uint64_t grepResult = f(useMMap, fileDescriptor, reinterpret_cast<intptr_t>(&handler));
    582601    close(fileDescriptor);
    583     return grepResult;
    584 }
    585 
    586 uint64_t CountOnlyEngine::doGrep(const std::string & fileName, std::ostringstream & strm) {
    587     uint64_t grepResult = GrepEngine::doGrep(fileName, strm);
    588     if (mShowFileNames) strm << linePrefix(fileName);
    589     strm << grepResult << "\n";
    590     return grepResult;
     602    if (handler.binaryFileSignalled()) {
     603        return 0;
     604    }
     605    else {
     606        showResult(grepResult, fileName, strm);
     607        return grepResult;
     608    }
    591609}
    592610
     
    601619}
    602620
    603 uint64_t MatchOnlyEngine::doGrep(const std::string & fileName, std::ostringstream & strm) {
    604     uint64_t grepResult = GrepEngine::doGrep(fileName, strm);
     621// Default: do not show anything
     622void GrepEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
     623}
     624   
     625void CountOnlyEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
     626    if (mShowFileNames) strm << linePrefix(fileName);
     627    strm << grepResult << "\n";
     628}
     629   
     630void MatchOnlyEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
    605631    if (grepResult == mRequiredCount) {
    606632       strm << linePrefix(fileName);
    607633    }
    608     return grepResult;
    609634}
    610635
     
    622647    f(useMMap, fileDescriptor, reinterpret_cast<intptr_t>(&accum));
    623648    close(fileDescriptor);
     649    if (accum.binaryFileSignalled()) {
     650        accum.mResultStr.clear();
     651    }
    624652    if (accum.mLineCount > 0) grepMatchFound = true;
    625653    return accum.mLineCount;
  • icGREP/icgrep-devel/icgrep/grep/grep_engine.h

    r5969 r5989  
    2727enum class GrepRecordBreakKind {Null, LF, Unicode};
    2828
    29 class MatchAccumulator {
     29enum GrepSignal : unsigned {BinaryFile};
     30
     31class GrepCallBackObject {
     32public:
     33    GrepCallBackObject() : mBinaryFile(false) {}
     34    virtual void handle_signal(unsigned signal);
     35    bool binaryFileSignalled() {return mBinaryFile;}
     36private:
     37    bool mBinaryFile;
     38};
     39   
     40class MatchAccumulator : public GrepCallBackObject {
    3041public:
    3142    MatchAccumulator() {}
     
    3445};
    3546
     47extern "C" void signal_dispatcher(intptr_t callback_object_addr, unsigned signal);
     48   
    3649extern "C" void accumulate_match_wrapper(intptr_t accum_addr, const size_t lineNum, char * line_start, char * line_end);
    3750
    3851extern "C" void finalize_match_wrapper(intptr_t accum_addr, char * buffer_end);
    39 
    4052
    4153class GrepEngine {
     
    6678    bool searchAllFiles();
    6779    void * DoGrepThreadMethod();
     80    virtual void showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm);
    6881
    6982protected:
    70     std::pair<parabix::StreamSetBuffer *, parabix::StreamSetBuffer *> grepPipeline(parabix::StreamSetBuffer * ByteStream);
     83    std::pair<parabix::StreamSetBuffer *, parabix::StreamSetBuffer *> grepPipeline(parabix::StreamSetBuffer * ByteStream, llvm::Value * callback_object_addr);
    7184
    7285    virtual uint64_t doGrep(const std::string & fileName, std::ostringstream & strm);
     
    145158    CountOnlyEngine();
    146159private:
    147     uint64_t doGrep(const std::string & fileName, std::ostringstream & strm) override;
     160    void showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) override;
    148161};
    149162
     
    152165    MatchOnlyEngine(bool showFilesWithoutMatch, bool useNullSeparators);
    153166private:
    154     uint64_t doGrep(const std::string & fileName, std::ostringstream & strm) override;
     167    void showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) override;
    155168    unsigned mRequiredCount;
    156169};
     
    184197   
    185198   
    186 #define MAX_SIMD_WIDTH_SUPPORTED 256
     199#define MAX_SIMD_WIDTH_SUPPORTED 512
    187200#define INITIAL_CAPACITY 64
    188201   
  • icGREP/icgrep-devel/icgrep/kernels/grep_kernel.cpp

    r5985 r5989  
    1111#include <re/re_toolchain.h>
    1212#include <re/re_reverse.h>
     13#include <grep/grep_engine.h>
    1314#include <pablo/codegenstate.h>
    1415#include <pablo/pablo_toolchain.h>
     
    2829#include <re/re_compiler.h>
    2930#include <UCD/ucd_compiler.hpp>
     31#include <llvm/IR/Module.h>
    3032#include <llvm/Support/raw_ostream.h>
    3133
     
    447449
    448450}
     451
     452
     453void AbortOnNull::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, llvm::Value * const numOfStrides) {
     454    Module * const m = b->getModule();
     455    DataLayout DL(m);
     456    IntegerType * const intPtrTy = DL.getIntPtrType(m->getContext());
     457    Type * voidPtrTy = b->getVoidPtrTy();
     458    const auto blocksPerStride = getStride() / b->getBitBlockWidth();
     459    Constant * const BLOCKS_PER_STRIDE = b->getSize(blocksPerStride);
     460    BasicBlock * const entry = b->GetInsertBlock();
     461    BasicBlock * const strideLoop = b->CreateBasicBlock("strideLoop");
     462    BasicBlock * const stridesDone = b->CreateBasicBlock("stridesDone");
     463    BasicBlock * const nullByteDetection = b->CreateBasicBlock("nullByteDetection");
     464    BasicBlock * const nullByteFound = b->CreateBasicBlock("nullByteFound");
     465    BasicBlock * const finalStride = b->CreateBasicBlock("finalStride");
     466    BasicBlock * const segmentDone = b->CreateBasicBlock("segmentDone");
     467
     468    Value * const numOfBlocks = b->CreateMul(numOfStrides, BLOCKS_PER_STRIDE);
     469    Value * availItems = b->getAvailableItemCount("bytedata");
     470    //
     471    // Fast loop to prove that there are no null bytes in a multiblock region.
     472    // We repeatedly combine byte packs using a SIMD unsigned min operation
     473    // (implemented as a Select/ICmpULT combination).
     474    //
     475    Value * byteStreamBasePtr = b->getInputStreamBlockPtr("bytedata", b->getSize(0), b->getSize(0));
     476    Value * outputStreamBasePtr = b->getOutputStreamBlockPtr("untilNull", b->getSize(0), b->getSize(0));
     477
     478    //
     479    // We set up a a set of eight accumulators to accumulate the minimum byte
     480    // values seen at each position in a block.   The initial min value at
     481    // each position is 0xFF (all ones).
     482    Value * blockMin[8];
     483    for (unsigned i = 0; i < 8; i++) {
     484        blockMin[i] = b->fwCast(8, b->allOnes());
     485    }
     486    // If we're in the final block bypass the fast loop.
     487    b->CreateCondBr(mIsFinal, finalStride, strideLoop);
     488   
     489    b->SetInsertPoint(strideLoop);
     490    PHINode * const baseBlockIndex = b->CreatePHI(b->getSizeTy(), 2);
     491    baseBlockIndex->addIncoming(ConstantInt::get(baseBlockIndex->getType(), 0), entry);
     492    PHINode * const blocksRemaining = b->CreatePHI(b->getSizeTy(), 2);
     493    blocksRemaining->addIncoming(numOfBlocks, entry);
     494    for (unsigned i = 0; i < 8; i++) {
     495        Value * next = b->CreateBlockAlignedLoad(b->CreateGEP(byteStreamBasePtr, {baseBlockIndex, b->getSize(i)}));
     496        b->CreateBlockAlignedStore(next, b->CreateGEP(outputStreamBasePtr, {baseBlockIndex, b->getSize(i)}));
     497        next = b->fwCast(8, next);
     498        blockMin[i] = b->CreateSelect(b->CreateICmpULT(next, blockMin[i]), next, blockMin[i]);
     499    }
     500    Value * nextBlockIndex = b->CreateAdd(baseBlockIndex, ConstantInt::get(baseBlockIndex->getType(), 1));
     501    Value * nextRemaining = b->CreateSub(blocksRemaining, ConstantInt::get(blocksRemaining->getType(), 1));
     502    baseBlockIndex->addIncoming(nextBlockIndex, strideLoop);
     503    blocksRemaining->addIncoming(nextRemaining, strideLoop);
     504    b->CreateCondBr(b->CreateICmpUGT(nextRemaining, ConstantInt::getNullValue(blocksRemaining->getType())), strideLoop, stridesDone);
     505   
     506    b->SetInsertPoint(stridesDone);
     507    // Combine the 8 blockMin values.
     508    for (unsigned i = 0; i < 4; i++) {
     509        blockMin[i] = b->CreateSelect(b->CreateICmpULT(blockMin[i], blockMin[i+4]), blockMin[i], blockMin[i+4]);
     510    }
     511    for (unsigned i = 0; i < 2; i++) {
     512        blockMin[i] = b->CreateSelect(b->CreateICmpULT(blockMin[i], blockMin[i+4]), blockMin[i], blockMin[i+2]);
     513    }
     514    blockMin[0] = b->CreateSelect(b->CreateICmpULT(blockMin[0], blockMin[1]), blockMin[0], blockMin[1]);
     515    Value * anyNull = b->bitblock_any(b->simd_eq(8, blockMin[0], b->allZeroes()));
     516   
     517    b->CreateCondBr(anyNull, nullByteDetection, segmentDone);
     518   
     519   
     520    b->SetInsertPoint(finalStride);
     521    b->CreateMemCpy(b->CreatePointerCast(outputStreamBasePtr, voidPtrTy), b->CreatePointerCast(byteStreamBasePtr, voidPtrTy), availItems, 1);
     522    b->CreateBr(nullByteDetection);
     523   
     524    b->SetInsertPoint(nullByteDetection);
     525    //  Find the exact location using memchr, which should be fast enough.
     526    //
     527    Value * ptrToNull = b->CreateMemChr(b->CreatePointerCast(byteStreamBasePtr, voidPtrTy), b->getInt32(0), availItems);
     528    Value * ptrAddr = b->CreatePtrToInt(ptrToNull, intPtrTy);
     529    b->CreateCondBr(b->CreateICmpEQ(ptrAddr, ConstantInt::getNullValue(intPtrTy)), segmentDone, nullByteFound);
     530   
     531    // A null byte has been located; set the termination code and call the signal handler.
     532    b->SetInsertPoint(nullByteFound);
     533    Value * nullPosn = b->CreateSub(b->CreatePtrToInt(ptrToNull, intPtrTy), b->CreatePtrToInt(byteStreamBasePtr, intPtrTy));
     534    b->setTerminationSignal();
     535    Function * const dispatcher = m->getFunction("signal_dispatcher"); assert (dispatcher);
     536    Value * handler = b->getScalarField("handler_address");
     537    b->CreateCall(dispatcher, {handler, ConstantInt::get(b->getInt32Ty(), static_cast<unsigned>(grep::GrepSignal::BinaryFile))});
     538    b->CreateBr(segmentDone);
     539   
     540    b->SetInsertPoint(segmentDone);
     541    PHINode * const produced = b->CreatePHI(b->getSizeTy(), 3);
     542    produced->addIncoming(nullPosn, nullByteFound);
     543    produced->addIncoming(availItems, stridesDone);
     544    produced->addIncoming(availItems, nullByteDetection);
     545    Value * producedCount = b->getProducedItemCount("untilNull");
     546    producedCount = b->CreateAdd(producedCount, produced);
     547    b->setProducedItemCount("untilNull", producedCount);
     548}
     549
     550AbortOnNull::AbortOnNull(const std::unique_ptr<kernel::KernelBuilder> & b)
     551: MultiBlockKernel("AbortOnNull",
     552                   // inputs
     553{Binding{b->getStreamSetTy(1, 8), "bytedata"}},
     554                   // outputs
     555{Binding{b->getStreamSetTy(1, 8), "untilNull", FixedRate(), Deferred()}},
     556                   // input scalars
     557{Binding{b->getIntAddrTy(), "handler_address"}},
     558{}, {}) {
     559    addAttribute(CanTerminateEarly());
     560}
  • icGREP/icgrep-devel/icgrep/kernels/grep_kernel.h

    r5902 r5989  
    131131    void generatePabloMethod() override;   
    132132};
     133
     134class AbortOnNull final : public MultiBlockKernel {
     135public:
     136    AbortOnNull(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
     137private:
     138    void generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, llvm::Value * const numOfStrides) final;
    133139   
     140};
     141
    134142}
    135143#endif
Note: See TracChangeset for help on using the changeset viewer.