Ignore:
Timestamp:
Jul 23, 2018, 4:56:33 AM (14 months ago)
Author:
xwa163
Message:
  1. More experiment on lz4 grep
  2. Improve performance of lzparabix grep
Location:
icGREP/icgrep-devel/icgrep/kernels/lzparabix/decoder
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/kernels/lzparabix/decoder/LZParabixAioKernel.cpp

    r6131 r6132  
    4343                                   {
    4444                                           Binding{b->getSizeTy(), "blockDataIndex"},
    45                                            Binding{b->getInt64Ty(), "outputPos"},
    46 
     45                                           Binding{b->getInt64Ty(), "outputPos"}
    4746
    4847                                   }), mNumsOfBitStreams(numsOfBitStreams) {
     
    6463
    6564
     65    void LZParabixAioKernel::initScalarOutputPtr(const std::unique_ptr<KernelBuilder> &b) {
     66//        b->CallPrintInt("------------------", b->getSize(0));
     67        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
     68            Value* ptr = b->CreatePointerCast(b->getOutputStreamBlockPtr("outputStream" + std::to_string(i), b->getSize(0)), b->getInt64Ty()->getPointerTo());
     69            b->setScalarField("currentOutputPtr_" + std::to_string(i), ptr);
     70
     71            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
     72                b->CreateStore(b->getInt64(0), b->CreateGEP(ptr, b->getInt32(j * 4)));
     73            }
     74        }
     75    }
     76
    6677    void LZParabixAioKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> &b) {
     78        this->initScalarOutputPtr(b);
     79
    6780        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
    6881        BasicBlock* blockEndConBlock = b->CreateBasicBlock("blockEndConBlock");
     
    168181
    169182        b->SetInsertPoint(exitBlock);
    170         this->storePendingOutput(b);
    171183        b->setProcessedItemCount("inputBitStream0", b->CreateAdd(literalStartPos, totalLiteralLength));
    172184    }
    173 
    174185
    175186    std::pair<llvm::Value *, llvm::Value *>
     
    339350    }
    340351
    341 
    342352    // ---- Output
    343353    void LZParabixAioKernel::initPendingOutputScalar(const std::unique_ptr<KernelBuilder> &b) {
    344         this->initPendingOutputScalar_BitStream(b);
    345 //        this->initPendingOutputScalar_Swizzled(b);
     354        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
     355            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
     356                this->addScalar(b->getInt64Ty(), "pendingOutput" + std::to_string(i) + "_" + std::to_string(j));
     357            }
     358        }
     359        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
     360            this->addScalar(b->getInt64Ty()->getPointerTo(), "currentOutputPtr_" + std::to_string(i));
     361        }
    346362    }
    347363
    348364    void LZParabixAioKernel::appendBitStreamOutput(const std::unique_ptr<KernelBuilder> &b, std::vector<llvm::Value*>& extractedValues, llvm::Value* valueLength) {
    349         this->appendBitStreamOutput_BitStream(b, extractedValues, valueLength);
    350 //        this->appendBitStreamOutput_Swizzled(b, extractedValues, valueLength);
    351     }
    352 
    353     void LZParabixAioKernel::storePendingOutput(const std::unique_ptr<KernelBuilder> &b) {
    354         BasicBlock* storePendingOutputBlock = b->CreateBasicBlock("storePendingOutputBlock");
    355         BasicBlock* storePendingOutputExitBlock = b->CreateBasicBlock("storePendingOutputExitBlock");
    356 
    357         Value* oldOutputPos = b->getScalarField("outputPos");
    358         b->CreateCondBr(
    359                 b->CreateICmpNE(b->CreateURem(oldOutputPos, b->getSize(64)), b->getSize(0)),
    360                 storePendingOutputBlock,
    361                 storePendingOutputExitBlock
    362         );
    363 
    364         b->SetInsertPoint(storePendingOutputBlock);
    365         this->storePendingOutput_BitStream(b);
    366 //        this->storePendingOutput_Swizzled(b);
    367         b->CreateBr(storePendingOutputExitBlock);
    368 
    369         b->SetInsertPoint(storePendingOutputExitBlock);
    370     }
    371 
    372 
    373     // ---- Output BitStream
    374     void LZParabixAioKernel::initPendingOutputScalar_BitStream(const std::unique_ptr<KernelBuilder> &b) {
    375         for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
    376             for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
    377                 this->addScalar(b->getInt64Ty(), "pendingOutput" + std::to_string(i) + "_" + std::to_string(j));
    378             }
    379         }
    380     }
    381 
    382     void LZParabixAioKernel::appendBitStreamOutput_BitStream(const std::unique_ptr<KernelBuilder> &b, std::vector<llvm::Value*>& extractedValues, llvm::Value* valueLength) {
    383365        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
    384366
     
    389371
    390372        unsigned iStreamIndex = 0;
    391         for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
    392             for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
    393                 Value* newValue = b->CreateOr(b->getScalarField("pendingOutput" + std::to_string(i) + "_" + std::to_string(j)), b->CreateShl(extractedValues[iStreamIndex], oldOutputPosRem64));
    394                 newOutputVec.push_back(newValue);
     373
     374        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
     375            Value* outputPtr = b->getScalarField("currentOutputPtr_" + std::to_string(i));
     376            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
     377                Value* ptr = b->CreateGEP(outputPtr, b->getSize(j * 4));
     378                Value* newValue = b->CreateOr(b->CreateLoad(ptr), b->CreateShl(extractedValues[iStreamIndex], oldOutputPosRem64));
     379                b->CreateStore(newValue, ptr);
    395380                ++iStreamIndex;
    396381            }
    397382        }
    398383
    399         BasicBlock* noStoreOutputBlock = b->CreateBasicBlock("noStoreOutputBlock");
    400384        BasicBlock* storeOutputBlock =b->CreateBasicBlock("storeOutputBlock");
    401 
    402         b->CreateCondBr(b->CreateICmpULT(b->CreateAdd(oldOutputPosRem64, valueLength), b->getSize(64)), noStoreOutputBlock, storeOutputBlock);
    403 
    404         // ---- noStoreOutputBlock
    405         b->SetInsertPoint(noStoreOutputBlock);
    406 
    407         iStreamIndex = 0;
    408         for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
    409             for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
    410                 b->setScalarField("pendingOutput" + std::to_string(i) + "_" + std::to_string(j), newOutputVec[iStreamIndex]);
    411                 ++iStreamIndex;
    412             }
    413         }
    414 
    415         b->CreateBr(exitBlock);
     385        b->CreateCondBr(b->CreateICmpULT(b->CreateAdd(oldOutputPosRem64, valueLength), b->getSize(64)), exitBlock, storeOutputBlock);
    416386
    417387        // ---- storeOutputBlock
    418388        b->SetInsertPoint(storeOutputBlock);
    419389
    420         Value* oldOutputPosRem = b->CreateURem(oldOutputPos, b->getCapacity("outputStream0"));
    421         Value* oldOutputPosBitBlockIndex = b->CreateUDiv(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
    422         Value* oldOutputPosBitBlockRem = b->CreateURem(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
    423 
    424         iStreamIndex = 0;
    425         for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
    426             Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream" + std::to_string(i), b->getSize(0)), b->getBitBlockType()->getPointerTo());
    427             Value* outputBitBlockBasePtr = b->CreateGEP(outputBasePtr, b->CreateMul(oldOutputPosBitBlockIndex, b->getSize(mNumsOfBitStreams[i])));
    428             outputBitBlockBasePtr = b->CreatePointerCast(outputBitBlockBasePtr, b->getInt64Ty()->getPointerTo());
    429 
    430             Value* oldOutputPosI64Index = b->CreateUDiv(oldOutputPosBitBlockRem, b->getSize(64));
    431 
    432             for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
    433                 Value* targetPtr = b->CreateGEP(outputBitBlockBasePtr, b->CreateAdd(oldOutputPosI64Index, b->getSize(j * (b->getBitBlockWidth() / 64))));
    434                 b->CreateStore(newOutputVec[iStreamIndex], targetPtr);
    435                 ++iStreamIndex;
    436             }
    437         }
    438 
    439390        Value* shiftAmount = b->CreateSub(b->getSize(0x40), oldOutputPosRem64);
    440391        Value* fullyShift = b->CreateICmpEQ(shiftAmount, b->getSize(0x40));
    441392
     393        Value* exceedBlock = b->CreateICmpUGE(b->CreateAdd(b->CreateURem(oldOutputPos, b->getSize(b->getBitBlockWidth())), valueLength), b->getSize(b->getBitBlockWidth()));
    442394        iStreamIndex = 0;
    443395        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
    444             for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
    445                 b->setScalarField("pendingOutput" + std::to_string(i) + "_" + std::to_string(j), b->CreateSelect(fullyShift, b->getInt64(0), b->CreateLShr(extractedValues[iStreamIndex], shiftAmount)));
     396            Value* oldOutputPtr = b->getScalarField("currentOutputPtr_" + std::to_string(i));
     397            Value* distance = b->CreateSelect(exceedBlock, b->getSize(1 + (mNumsOfBitStreams[i] - 1) * b->getBitBlockWidth() / 64), b->getSize(1));
     398            Value* newOutputPtr = b->CreateGEP(oldOutputPtr, distance);
     399            b->setScalarField("currentOutputPtr_" + std::to_string(i), newOutputPtr);
     400            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
     401                Value* newValue = b->CreateSelect(fullyShift, b->getInt64(0), b->CreateLShr(extractedValues[iStreamIndex], shiftAmount));
     402                Value* ptr = b->CreateGEP(newOutputPtr, b->getSize(j * 4));
     403                b->CreateStore(newValue, ptr);
    446404                ++iStreamIndex;
    447405            }
     
    452410        b->SetInsertPoint(exitBlock);
    453411        b->setScalarField("outputPos", b->CreateAdd(oldOutputPos, valueLength));
    454     }
    455 
    456     void LZParabixAioKernel::storePendingOutput_BitStream(const std::unique_ptr<KernelBuilder> &b) {
    457         Value* oldOutputPos = b->getScalarField("outputPos");
    458         Value* oldOutputPosRem = b->CreateURem(oldOutputPos, b->getCapacity("outputStream0"));
    459         Value* oldOutputPosBitBlockIndex = b->CreateUDiv(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
    460         Value* oldOutputPosBitBlockRem = b->CreateURem(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
    461         Value* oldOutputPosI64Index = b->CreateUDiv(oldOutputPosBitBlockRem, b->getSize(64));
    462 
    463         unsigned iStreamIndex = 0;
    464         for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
    465             Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream" + std::to_string(i), b->getSize(0)), b->getBitBlockType()->getPointerTo());
    466             Value* outputBitBlockBasePtr = b->CreateGEP(outputBasePtr, b->CreateMul(oldOutputPosBitBlockIndex, b->getSize(mNumsOfBitStreams[i])));
    467             outputBitBlockBasePtr = b->CreatePointerCast(outputBitBlockBasePtr, b->getInt64Ty()->getPointerTo());
    468             for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
    469                 Value* targetPtr = b->CreateGEP(outputBitBlockBasePtr, b->CreateAdd(oldOutputPosI64Index, b->getSize(j * (b->getBitBlockWidth() / 64))));
    470                 b->CreateStore(b->getScalarField("pendingOutput" + std::to_string(i) + "_" + std::to_string(j)), targetPtr);
    471                 ++iStreamIndex;
    472             }
    473         }
    474     }
    475 
    476     // ---- Output Swizzled
    477     void LZParabixAioKernel::initPendingOutputScalar_Swizzled(const std::unique_ptr<KernelBuilder> &b) {
    478         for (unsigned i = 0; i < (mNumsOfBitStreams[0] + 3) / 4; i++) {
    479             this->addScalar(b->getBitBlockType(), "pendingOutput" + std::to_string(0) + "_" + std::to_string(i));
    480         }
    481     }
    482     void LZParabixAioKernel::appendBitStreamOutput_Swizzled(const std::unique_ptr<KernelBuilder> &b, std::vector<llvm::Value*>& extractedValues, llvm::Value* valueLength) {
    483 
    484         std::vector<llvm::Value*> extractedValuesVec;
    485         for (unsigned i = 0; i < 2; i++) {
    486             Value* vec = ConstantVector::getNullValue(b->getBitBlockType());
    487             for (unsigned j = 0; j < 4; j++) {
    488                 vec = b->CreateInsertElement(vec, extractedValues[i * 4 + j], j);
    489             }
    490             extractedValuesVec.push_back(vec);
    491         }
    492 
    493         BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
    494 
    495         Value* oldOutputPos = b->getScalarField("outputPos");
    496         Value* oldOutputPosRem64 = b->CreateURem(oldOutputPos, b->getSize(64));
    497 
    498         std::vector<llvm::Value*> newOutputVec;
    499         for (unsigned i = 0; i < 2; i++) {
    500             Value* newValue = b->CreateOr(b->getScalarField("pendingOutput" + std::to_string(0) + "_" + std::to_string(i)), b->CreateShl(extractedValuesVec[i], b->simd_fill(64, oldOutputPosRem64)));
    501             newOutputVec.push_back(newValue);
    502         }
    503 
    504 
    505         BasicBlock* noStoreOutputBlock = b->CreateBasicBlock("noStoreOutputBlock");
    506         BasicBlock* storeOutputBlock =b->CreateBasicBlock("storeOutputBlock");
    507 
    508         b->CreateCondBr(b->CreateICmpULT(b->CreateAdd(oldOutputPosRem64, valueLength), b->getSize(64)), noStoreOutputBlock, storeOutputBlock);
    509 
    510         // ---- noStoreOutputBlock
    511         b->SetInsertPoint(noStoreOutputBlock);
    512         for (unsigned i = 0; i < 2; i++) {
    513             b->setScalarField("pendingOutput" + std::to_string(0) + "_" + std::to_string(i), newOutputVec[i]);
    514         }
    515         b->CreateBr(exitBlock);
    516 
    517         // ---- storeOutputBlock
    518         b->SetInsertPoint(storeOutputBlock);
    519 
    520         Value* oldOutputPosRem = b->CreateURem(oldOutputPos, b->getCapacity("outputStream0"));
    521         Value* oldOutputPosBitBlockIndex = b->CreateUDiv(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
    522         Value* oldOutputPosBitBlockRem = b->CreateURem(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
    523 
    524         Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream0", b->getSize(0)), b->getBitBlockType()->getPointerTo());
    525         Value* outputBitBlockBasePtr = b->CreateGEP(outputBasePtr, b->CreateMul(oldOutputPosBitBlockIndex, b->getSize(8)));
    526         outputBitBlockBasePtr = b->CreatePointerCast(outputBitBlockBasePtr, b->getInt64Ty()->getPointerTo());
    527 
    528         Value* oldOutputPosI64Index = b->CreateUDiv(oldOutputPosBitBlockRem, b->getSize(64));
    529 
    530         for (unsigned i = 0; i < 2; i++) {
    531             for (unsigned j = 0; j < 4; j++) {
    532                 Value* targetPtr = b->CreateGEP(outputBitBlockBasePtr, b->CreateAdd(oldOutputPosI64Index, b->getSize((i * 4 + j) * 4)));
    533                 b->CreateStore(b->CreateExtractElement(newOutputVec[i], j), targetPtr);
    534             }
    535 
    536         }
    537 
    538         Value* shiftAmount = b->CreateSub(b->getSize(0x40), oldOutputPosRem64);
    539         Value* fullyShift = b->CreateICmpEQ(shiftAmount, b->getSize(0x40));
    540 
    541         for (unsigned i = 0; i < 2; i++) {
    542 
    543             b->setScalarField("pendingOutput" + std::to_string(0) + "_" + std::to_string(i), b->CreateSelect(fullyShift, ConstantVector::getNullValue(b->getBitBlockType()), b->CreateLShr(extractedValuesVec[i], b->simd_fill(64, shiftAmount))));
    544         }
    545 
    546         b->CreateBr(exitBlock);
    547 
    548         b->SetInsertPoint(exitBlock);
    549         b->setScalarField("outputPos", b->CreateAdd(oldOutputPos, valueLength));
    550 
    551     }
    552 
    553     void LZParabixAioKernel::storePendingOutput_Swizzled(const std::unique_ptr<KernelBuilder> &b) {
    554         Value* oldOutputPos = b->getScalarField("outputPos");
    555         Value* oldOutputPosRem = b->CreateURem(oldOutputPos, b->getCapacity("outputStream0"));
    556         Value* oldOutputPosBitBlockIndex = b->CreateUDiv(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
    557         Value* oldOutputPosBitBlockRem = b->CreateURem(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
    558 
    559         Value* oldOutputPosI64Index = b->CreateUDiv(oldOutputPosBitBlockRem, b->getSize(64));
    560 
    561         Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream0", b->getSize(0)), b->getBitBlockType()->getPointerTo());
    562         Value* outputBitBlockBasePtr = b->CreateGEP(outputBasePtr, b->CreateMul(oldOutputPosBitBlockIndex, b->getSize(8)));
    563         outputBitBlockBasePtr = b->CreatePointerCast(outputBitBlockBasePtr, b->getInt64Ty()->getPointerTo());
    564 
    565         vector<Value*> pendingOutputVec;
    566         for (unsigned i = 0; i < 2; i++) {
    567             pendingOutputVec.push_back(b->getScalarField("pendingOutput" + std::to_string(0) + "_" + std::to_string(i)));
    568         }
    569 
    570         for (unsigned i = 0; i < 2; i++) {
    571             for (unsigned j = 0; j < 2; j++) {
    572                 Value* targetPtr = b->CreateGEP(outputBitBlockBasePtr, b->CreateAdd(oldOutputPosI64Index, b->getSize((i * 4 + j) * 4)));
    573                 b->CreateStore(b->CreateExtractElement(pendingOutputVec[i], j), targetPtr);
    574             }
    575         }
    576     }
     412
     413    }
     414
    577415}
  • icGREP/icgrep-devel/icgrep/kernels/lzparabix/decoder/LZParabixAioKernel.h

    r6123 r6132  
    4141        std::vector<unsigned> mNumsOfBitStreams;
    4242
    43 
    4443        // ---- Output
    4544        void initPendingOutputScalar(const std::unique_ptr<KernelBuilder> &b);
    4645        void appendBitStreamOutput(const std::unique_ptr<KernelBuilder> &b, std::vector<llvm::Value*>& extractedValues, llvm::Value* valueLength);
    47         void storePendingOutput(const std::unique_ptr<KernelBuilder> &b);
    4846
    49 
    50         void initPendingOutputScalar_BitStream(const std::unique_ptr<KernelBuilder> &b);
    51         void appendBitStreamOutput_BitStream(const std::unique_ptr<KernelBuilder> &b, std::vector<llvm::Value*>& extractedValues, llvm::Value* valueLength);
    52         void storePendingOutput_BitStream(const std::unique_ptr<KernelBuilder> &b);
    53 
    54 
    55         void initPendingOutputScalar_Swizzled(const std::unique_ptr<KernelBuilder> &b);
    56         void appendBitStreamOutput_Swizzled(const std::unique_ptr<KernelBuilder> &b, std::vector<llvm::Value*>& extractedValues, llvm::Value* valueLength);
    57         void storePendingOutput_Swizzled(const std::unique_ptr<KernelBuilder> &b);
     47        void initScalarOutputPtr(const std::unique_ptr<KernelBuilder> &b);
    5848    };
    5949
Note: See TracChangeset for help on using the changeset viewer.