Ignore:
Timestamp:
Apr 18, 2018, 3:30:28 AM (17 months ago)
Author:
xwa163
Message:
  1. Use i1 bit stream instead of i64 number stream in M0 related streams and Match Offset related stream
  2. Improve the performance of lz4_index_builder
File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/kernels/lz4/lz4_swizzled_match_copy_kernel.cpp

    r5967 r5974  
    55#include "lz4_swizzled_match_copy_kernel.h"
    66#include <kernels/kernel_builder.h>
     7#include <kernels/streamset.h>
     8#include <toolchain/toolchain.h>
     9#include <vector>
     10#include <llvm/Support/raw_ostream.h>
    711
    812using namespace llvm;
    9 
     13using namespace std;
    1014namespace kernel {
    1115
     16Value *LZ4SwizzledMatchCopyKernel::advanceUntilNextBit(const std::unique_ptr<KernelBuilder> &iBuilder, string inputName, Value *startPos, bool isNextOne) {
     17    BasicBlock* entryBlock = iBuilder->GetInsertBlock();
     18
     19    Constant* SIZE_0 = iBuilder->getSize(0);
     20    Constant* SIZE_1 = iBuilder->getSize(1);
     21    Value* SIZE_64 = iBuilder->getSize(64); // maybe need to handle 32 bit machine
     22    Value* SIZE_INPUT_64_COUNT = iBuilder->getSize(this->getInputStreamSetBuffer(inputName)->getBufferBlocks() * iBuilder->getBitBlockWidth() / 64);
     23
     24    Value* initCurrentPos = startPos;
     25
     26    Value* offsetMarkerRawPtr = iBuilder->CreatePointerCast(iBuilder->getRawInputPointer(inputName, SIZE_0), iBuilder->getInt64Ty()->getPointerTo());
     27
     28    BasicBlock* findNextMatchOffsetConBlock = iBuilder->CreateBasicBlock("findNextMatchOffsetConBlock");
     29    BasicBlock* findNextMatchOffsetBodyBlock = iBuilder->CreateBasicBlock("findNextMatchOffsetBodyBlock");
     30
     31    iBuilder->CreateBr(findNextMatchOffsetConBlock);
     32    iBuilder->SetInsertPoint(findNextMatchOffsetConBlock);
     33    // Find position marker bit of next 1 bit
     34
     35    PHINode* phiCurrentPos = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2);
     36    phiCurrentPos->addIncoming(initCurrentPos, entryBlock);
     37
     38    Value* currentPosGlobalBlockIndex = iBuilder->CreateUDiv(phiCurrentPos, SIZE_64);
     39    Value* currentPosLocalBlockIndex = iBuilder->CreateURem(currentPosGlobalBlockIndex, SIZE_INPUT_64_COUNT);
     40    Value* currentPosBlockOffset = iBuilder->CreateURem(phiCurrentPos, SIZE_64);
     41    Value* currentValue = iBuilder->CreateLoad(iBuilder->CreateGEP(offsetMarkerRawPtr, currentPosLocalBlockIndex));
     42
     43    Value* countValue = iBuilder->CreateLShr(currentValue, currentPosBlockOffset);
     44    if (!isNextOne) {
     45        countValue = iBuilder->CreateNot(countValue);
     46    }
     47    Value* forwardZero = iBuilder->CreateCountForwardZeroes(countValue);
     48    Value* realForwardZero = iBuilder->CreateAdd(currentPosBlockOffset, forwardZero);
     49
     50    // If targetMarker == 0, move to next block, otherwise count forward zero
     51    phiCurrentPos->addIncoming(iBuilder->CreateMul(SIZE_64, iBuilder->CreateAdd(currentPosGlobalBlockIndex, SIZE_1)), iBuilder->GetInsertBlock());
     52    iBuilder->CreateCondBr(iBuilder->CreateICmpUGE(realForwardZero, SIZE_64), findNextMatchOffsetConBlock, findNextMatchOffsetBodyBlock);
     53
     54    iBuilder->SetInsertPoint(findNextMatchOffsetBodyBlock);
     55
     56    Value* newPosition = iBuilder->CreateAdd(iBuilder->CreateMul(currentPosGlobalBlockIndex, SIZE_64), realForwardZero);
     57
     58    return newPosition;
     59}
     60
     61Value* LZ4SwizzledMatchCopyKernel::loadNextMatchOffset(const unique_ptr<KernelBuilder> &iBuilder) {
     62    Value* initCurrentPos = iBuilder->CreateAdd(iBuilder->getScalarField("currentOffsetMarkerPos"), iBuilder->getSize(1));
     63    Value* newPosition = this->advanceUntilNextBit(iBuilder, "MatchOffsetMarker", initCurrentPos, true);
     64
     65    // Load Match Offset from newPosition
     66    iBuilder->setScalarField("currentOffsetMarkerPos", newPosition);
     67    iBuilder->setProcessedItemCount("MatchOffsetMarker", newPosition);
     68
     69    Value* matchOffsetPtr = iBuilder->getRawInputPointer("byteStream", newPosition);
     70    // For now, it is safe to cast matchOffset pointer into i16 since the input byte stream is always linear available
     71    matchOffsetPtr = iBuilder->CreatePointerCast(matchOffsetPtr, iBuilder->getInt16Ty()->getPointerTo());
     72    Value* matchOffset = iBuilder->CreateZExt(iBuilder->CreateLoad(matchOffsetPtr), iBuilder->getSizeTy());
     73
     74    return matchOffset;
     75}
     76
     77pair<Value*, Value*> LZ4SwizzledMatchCopyKernel::loadNextM0StartEnd(const unique_ptr<KernelBuilder> &iBuilder) {
     78    Value* initCurrentPos = iBuilder->getScalarField("currentM0MarkerPos");
     79    Value* m0Start = this->advanceUntilNextBit(iBuilder, "M0Marker", initCurrentPos, true);
     80    Value* m0End = this->advanceUntilNextBit(iBuilder, "M0Marker", m0Start, false);
     81    iBuilder->setScalarField("currentM0MarkerPos", m0End);
     82    return std::make_pair(m0Start, m0End);
     83};
     84
     85
     86
     87
    1288void LZ4SwizzledMatchCopyKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> & iBuilder) {
    13 
    1489    ConstantInt * const SIZE_ZERO = iBuilder->getSize(0);
    1590    ConstantInt * const SIZE_ONE = iBuilder->getSize(1);
     
    2499
    25100    Value * const itemsToDo = iBuilder->CreateUMin(iBuilder->CreateSub(available, processed), SIZE_4_MEGS);
    26 
    27101    iBuilder->setTerminationSignal(iBuilder->CreateICmpULT(itemsToDo, SIZE_4_MEGS));
    28102
     
    35109
    36110    // Match Copy
    37     Value * const initM0StartProcessIndex = iBuilder->getProcessedItemCount("m0Start");
    38     Value * const totalM0StartItemsCount = iBuilder->getAvailableItemCount("m0Start");
     111    Value *initM0StartProcessIndex = iBuilder->getProcessedItemCount("M0CountMarker");
     112    Value *totalM0StartItemsCount = iBuilder->getAvailableItemCount("M0CountMarker");
    39113
    40114    Value * const initMatchOffset = iBuilder->getScalarField("pendingMatchOffset");
     
    70144    iBuilder->SetInsertPoint(loadNextMatchInfoBodyBlock);
    71145
    72     Value * const newM0Start = loadOffset(iBuilder, "m0Start", phiProcessIndex);
    73     Value * const newM0End = loadOffset(iBuilder, "m0End", phiProcessIndex);
    74     Value * const newMatchOffset = loadOffset(iBuilder, "matchOffset", phiProcessIndex);
     146    auto ret = this->loadNextM0StartEnd(iBuilder);
     147    Value *newM0Start = ret.first;
     148    Value *newM0End = ret.second;
     149    iBuilder->setProcessedItemCount("M0Marker", newM0End);
     150    Value *newMatchOffset = this->loadNextMatchOffset(iBuilder);
     151
     152
     153
    75154    Value * const newMatchLength = iBuilder->CreateAdd(iBuilder->CreateSub(newM0End, newM0Start), iBuilder->getInt64(1));
    76155
    77     phiProcessIndex->addIncoming(iBuilder->CreateAdd(phiProcessIndex, SIZE_ONE), loadNextMatchInfoBodyBlock);
    78 
    79     phiMatchPos->addIncoming(newM0Start, loadNextMatchInfoBodyBlock);
    80     phiMatchOffset->addIncoming(newMatchOffset, loadNextMatchInfoBodyBlock);
    81     phiMatchLength->addIncoming(newMatchLength, loadNextMatchInfoBodyBlock);
     156    phiProcessIndex->addIncoming(iBuilder->CreateAdd(phiProcessIndex, SIZE_ONE), iBuilder->GetInsertBlock());
     157
     158    phiMatchPos->addIncoming(newM0Start, iBuilder->GetInsertBlock());
     159    phiMatchOffset->addIncoming(newMatchOffset, iBuilder->GetInsertBlock());
     160    phiMatchLength->addIncoming(newMatchLength, iBuilder->GetInsertBlock());
    82161
    83162    iBuilder->CreateBr(matchCopyLoopCon);
     
    140219    iBuilder->setScalarField("pendingMatchLength", phiMatchLength);
    141220    iBuilder->setScalarField("pendingMatchPos", phiMatchPos);
    142     iBuilder->setProcessedItemCount("m0Start", phiProcessIndex);
    143     iBuilder->setProcessedItemCount("m0End", phiProcessIndex);
    144     iBuilder->setProcessedItemCount("matchOffset", phiProcessIndex);
     221    iBuilder->setProcessedItemCount("M0CountMarker", phiProcessIndex);
    145222    iBuilder->setProcessedItemCount("sourceStreamSet0", toProcessItemCount);
    146223}
     
    164241// Inputs
    165242{
    166        Binding{iBuilder->getStreamSetTy(1, 64), "m0Start", BoundedRate(0, 1), DisableSufficientChecking()},
    167        Binding{iBuilder->getStreamSetTy(1, 64), "m0End", BoundedRate(0, 1), DisableSufficientChecking()},
    168        Binding{iBuilder->getStreamSetTy(1, 64), "matchOffset", BoundedRate(0, 1), DisableSufficientChecking()},
     243                                   Binding{iBuilder->getStreamSetTy(1, 1), "MatchOffsetMarker", BoundedRate(0, 1), {DisableSufficientChecking()}},
     244                                   Binding{iBuilder->getStreamSetTy(1, 1), "M0Marker", BoundedRate(0, 1), {DisableSufficientChecking()}},
     245                                   Binding{iBuilder->getStreamSetTy(1, 1), "M0CountMarker", BoundedRate(0, 1), {DisableSufficientChecking()}},
     246                                   Binding{iBuilder->getStreamSetTy(1, 8), "byteStream", BoundedRate(0, 1)}
    169247},
    170248// Outputs
     
    172250// Arguments
    173251{
    174        Binding{iBuilder->getSizeTy(), "fileSize"} //TODO remove
    175252},
    176253{},
     
    180257       Binding{iBuilder->getSizeTy(), "pendingMatchOffset"},
    181258       Binding{iBuilder->getSizeTy(), "pendingMatchLength"},
     259       Binding(iBuilder->getSizeTy(), "currentOffsetMarkerPos"),
     260       Binding(iBuilder->getSizeTy(), "currentM0MarkerPos")
    182261})
    183262, mSwizzleFactor(swizzleFactor)
Note: See TracChangeset for help on using the changeset viewer.