Changeset 5055


Ignore:
Timestamp:
Jun 14, 2016, 7:02:17 PM (3 years ago)
Author:
cameron
Message:

scanmatch kernel using new infrastructure

Location:
icGREP/icgrep-devel/icgrep/kernels
Files:
2 edited

Legend:

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

    r5037 r5055  
    203203
    204204void generateScanMatch(Module * m, IDISA::IDISA_Builder * iBuilder, unsigned scanWordBitWidth, KernelBuilder * kBuilder, bool isNameExpression) {
    205 
    206 
     205   
    207206    Type * T = iBuilder->getIntNTy(scanWordBitWidth);
    208207    Type * S = PointerType::get(iBuilder->getIntNTy(8), 0);
     208    kBuilder->setInstanceParameters({{S, "FileBuf"}, {T, "FileSize"}, {T, "FileIdx"}});
     209
    209210    const unsigned fieldCount = iBuilder->getBitBlockWidth() / scanWordBitWidth;
    210211    Type * scanwordVectorType =  VectorType::get(T, fieldCount);
     
    215216    const unsigned lineStart = kBuilder->addInternalState(T, "LineStart");
    216217    const unsigned lineNum = kBuilder->addInternalState(T, "LineNum");
    217     kBuilder->addInternalState(S, "FileBuf");
    218     kBuilder->addInternalState(T, "FileSize");
    219     kBuilder->addInternalState(T, "FileIdx");
    220 
     218   
     219    kBuilder->createInitMethod();
    221220    Function * function = kBuilder->prepareFunction();
    222221
     222
    223223    Function * scanWordFunction = generateScanWordRoutine(m, iBuilder, scanWordBitWidth, kBuilder, isNameExpression);
    224 
     224   
    225225    iBuilder->SetInsertPoint(&function->getEntryBlock());
    226226
     
    229229    Value * scanwordPos = iBuilder->CreateLoad(kBuilder->getInternalState("BlockNo"));
    230230    scanwordPos = iBuilder->CreateMul(scanwordPos, ConstantInt::get(scanwordPos->getType(), iBuilder->getBitBlockWidth()));
    231 
     231   
    232232    Value * recordStart = iBuilder->CreateBlockAlignedLoad(kBuilder->getInternalState(lineStart));
    233233    Value * recordNum = iBuilder->CreateBlockAlignedLoad(kBuilder->getInternalState(lineNum));
     
    245245    kBuilder->setInternalState(lineNum, recordNum);
    246246    kBuilder->finalize();
    247 }
    248 
    249 }
     247
     248}
     249       
     250std::unique_ptr<llvm::Module> scanMatchKernel::createKernelModule() {
     251    std::unique_ptr<llvm::Module> theModule = KernelInterface::createKernelModule();
     252   
     253    Function * scanWordFunction = generateScanWordRoutine(theModule.get());
     254    const unsigned fieldCount = iBuilder->getBitBlockWidth() / mScanwordBitWidth;
     255    Type * T = iBuilder->getIntNTy(mScanwordBitWidth);
     256    Type * scanwordVectorType =  VectorType::get(T, fieldCount);
     257
     258    Function * doBlockFunction = theModule.get()->getFunction(mKernelName + "_DoBlock");
     259
     260    iBuilder->SetInsertPoint(BasicBlock::Create(iBuilder->getContext(), "entry", doBlockFunction, 0));
     261    Value * kernelStuctParam = getParameter(doBlockFunction, "self");
     262    Value * scanwordPos = getScalarField(kernelStuctParam, "BlockNo");
     263    scanwordPos = iBuilder->CreateMul(scanwordPos, ConstantInt::get(scanwordPos->getType(), iBuilder->getBitBlockWidth()));
     264   
     265    Value * recordStart = getScalarField(kernelStuctParam, "LineStart");
     266    Value * recordNum = getScalarField(kernelStuctParam, "LineNum");
     267    Value * matchResultsPtr = getParameter(doBlockFunction, "matchResults");
     268    Value * matches = iBuilder->CreateBlockAlignedLoad(matchResultsPtr, {iBuilder->getInt32(0), iBuilder->getInt32(0)});
     269    Value * linebreaks = iBuilder->CreateBlockAlignedLoad(matchResultsPtr, {iBuilder->getInt32(0), iBuilder->getInt32(1)});
     270    Value * matchWordVector = iBuilder->CreateBitCast(matches, scanwordVectorType);
     271    Value * breakWordVector = iBuilder->CreateBitCast(linebreaks, scanwordVectorType);
     272    for(unsigned i = 0; i < fieldCount; ++i){
     273        Value * matchWord = iBuilder->CreateExtractElement(matchWordVector, ConstantInt::get(T, i));
     274        Value * recordBreaksWord = iBuilder->CreateExtractElement(breakWordVector, ConstantInt::get(T, i));
     275        Value * wordResult = iBuilder->CreateCall(scanWordFunction, {kernelStuctParam, matchWord, recordBreaksWord, scanwordPos, recordStart, recordNum});
     276        scanwordPos = iBuilder->CreateAdd(scanwordPos, ConstantInt::get(T, mScanwordBitWidth));
     277        recordStart = iBuilder->CreateExtractValue(wordResult, std::vector<unsigned>({0}));
     278        recordNum = iBuilder->CreateExtractValue(wordResult, std::vector<unsigned>({1}));
     279    }
     280    setScalarField(kernelStuctParam, "LineStart", recordStart);
     281    setScalarField(kernelStuctParam, "LineNum", recordNum);
     282    setScalarField(kernelStuctParam, "BlockNo", iBuilder->CreateAdd(getScalarField(kernelStuctParam, "BlockNo"), iBuilder->getInt64(1)));
     283    iBuilder -> CreateRetVoid();
     284   
     285    // scanMatch FinalBlock function simply dispatches to the DoBlock function
     286    Function * finalBlockFunction = theModule.get()->getFunction(mKernelName + "_FinalBlock");
     287    iBuilder->SetInsertPoint(BasicBlock::Create(iBuilder->getContext(), "fb_entry", finalBlockFunction, 0));
     288    Value * self = getParameter(finalBlockFunction, "self");
     289    Value * matchResults = getParameter(finalBlockFunction, "matchResults");
     290    iBuilder->CreateCall(doBlockFunction, {self, matchResults});
     291    iBuilder->CreateRetVoid();
     292    //
     293    return theModule;
     294}
     295
     296   
     297Function * scanMatchKernel::generateScanWordRoutine(Module * m) {
     298    Function * function = m->getFunction("scan_matches_in_scanword");
     299    if (LLVM_UNLIKELY(function != nullptr)) {
     300        return function;
     301    }
     302   
     303    LLVMContext & ctxt = m->getContext();
     304    Type * T = iBuilder->getIntNTy(mScanwordBitWidth);
     305    Type * S = PointerType::get(iBuilder->getIntNTy(8), 0);
     306    Type * returnType = StructType::get(ctxt, std::vector<Type *>({T, T}));
     307    FunctionType * functionType = FunctionType::get(returnType, std::vector<Type *>({PointerType::get(mKernelStateType, 0), T, T, T, T, T}), false);
     308   
     309    SmallVector<AttributeSet, 6> Attrs;
     310    Attrs.push_back(AttributeSet::get(ctxt, ~0U, std::vector<Attribute::AttrKind>({ Attribute::NoUnwind, Attribute::UWTable })));
     311    Attrs.push_back(AttributeSet::get(ctxt, 1, std::vector<Attribute::AttrKind>({})));
     312    Attrs.push_back(AttributeSet::get(ctxt, 2, std::vector<Attribute::AttrKind>({})));
     313    Attrs.push_back(AttributeSet::get(ctxt, 3, std::vector<Attribute::AttrKind>({})));
     314    Attrs.push_back(AttributeSet::get(ctxt, 4, std::vector<Attribute::AttrKind>({})));
     315    Attrs.push_back(AttributeSet::get(ctxt, 5, std::vector<Attribute::AttrKind>({})));
     316    AttributeSet AttrSet = AttributeSet::get(ctxt, Attrs);
     317   
     318    function = Function::Create(functionType, GlobalValue::ExternalLinkage, "scan_matches_in_scanword", m);
     319    function->setCallingConv(CallingConv::C);
     320    function->setAttributes(AttrSet);
     321    function->addFnAttr(llvm::Attribute::AlwaysInline);
     322   
     323    Function::arg_iterator args = function->arg_begin();
     324    Value * instance = &*(args++);
     325    instance->setName("this");
     326    Value * matches_input_parm = &*(args++);
     327    matches_input_parm->setName("matches");
     328    Value * record_breaks_input_parm = &*(args++);
     329    record_breaks_input_parm->setName("breaks");
     330    Value * scanwordPos = &*(args++);
     331    scanwordPos->setName("scanwordPos");
     332    Value * recordStart_input_parm = &*(args++);
     333    recordStart_input_parm->setName("pendingLineStart");
     334    Value * recordNum_input_parm = &*(args++);
     335    recordNum_input_parm->setName("lineNum");
     336   
     337    Constant * matchProcessor;
     338    if (mIsNameExpression) {
     339        matchProcessor = m->getOrInsertFunction("insert_codepoints", Type::getVoidTy(ctxt), T, T, T, S, nullptr);
     340    } else {
     341        matchProcessor = m->getOrInsertFunction("wrapped_report_match", Type::getVoidTy(ctxt), T, T, T, S, T, T, nullptr);
     342    }
     343    iBuilder->SetInsertPoint(BasicBlock::Create(ctxt, "entry", function,0));
     344   
     345    BasicBlock * entry_block = iBuilder->GetInsertBlock();
     346    BasicBlock * matches_test_block = BasicBlock::Create(ctxt, "matches_test_block", function, 0);
     347    BasicBlock * process_matches_loop_entry = BasicBlock::Create(ctxt, "process_matches_loop", function, 0);
     348    BasicBlock * prior_breaks_block = BasicBlock::Create(ctxt, "prior_breaks_block", function, 0);
     349    BasicBlock * loop_final_block = BasicBlock::Create(ctxt, "loop_final_block", function, 0);
     350    BasicBlock * matches_done_block = BasicBlock::Create(ctxt, "matches_done_block", function, 0);
     351    BasicBlock * remaining_breaks_block = BasicBlock::Create(ctxt, "remaining_breaks_block", function, 0);
     352    BasicBlock * return_block = BasicBlock::Create(ctxt, "return_block", function, 0);
     353   
     354   
     355    // The match scanner works with a loop involving four variables:
     356    // (a) the bit stream scanword of matches marking the ends of selected records,
     357    // (b) the bit stream scanword of record_breaks marking the ends of all records,
     358    // (c) the integer lastRecordNum indicating the number of records processed so far,
     359    // (d) the index lastRecordStart indicating the file position of the last record.
     360    // We set up a loop structure, in which a set of 4 phi nodes initialize these
     361    // variables from either the input to the scanner or the computed values within
     362    // the loop body.
     363   
     364   
     365    iBuilder->CreateBr(matches_test_block);
     366   
     367    // LOOP Test Block
     368    iBuilder->SetInsertPoint(matches_test_block);
     369    PHINode * matches_phi = iBuilder->CreatePHI(T, 2, "matches");
     370    PHINode * record_breaks_phi = iBuilder->CreatePHI(T, 2, "record_breaks");
     371    PHINode * recordNum_phi = iBuilder->CreatePHI(T, 2, "recordNum");
     372    PHINode * recordStart_phi = iBuilder->CreatePHI(T, 2, "recordStart");
     373    matches_phi->addIncoming(matches_input_parm, entry_block);
     374    record_breaks_phi->addIncoming(record_breaks_input_parm, entry_block);
     375    recordNum_phi->addIncoming(recordNum_input_parm, entry_block);
     376    recordStart_phi->addIncoming(recordStart_input_parm, entry_block);
     377    Value * have_matches_cond = iBuilder->CreateICmpNE(matches_phi, ConstantInt::get(T, 0));
     378    iBuilder->CreateCondBr(have_matches_cond, process_matches_loop_entry, matches_done_block);
     379   
     380    // LOOP BODY
     381    // The loop body is entered if we have more matches to process.
     382    iBuilder->SetInsertPoint(process_matches_loop_entry);
     383    Value * prior_breaks = iBuilder->CreateAnd(generateForwardZeroesMask(iBuilder, matches_phi), record_breaks_phi);
     384    // Within the loop we have a conditional block that is executed if there are any prior
     385    // record breaks.
     386    Value * prior_breaks_cond = iBuilder->CreateICmpNE(prior_breaks, ConstantInt::get(T, 0));
     387    iBuilder->CreateCondBr(prior_breaks_cond, prior_breaks_block, loop_final_block);
     388   
     389    // PRIOR_BREAKS_BLOCK
     390    // If there are prior breaks, we count them and compute the record start position.
     391    iBuilder->SetInsertPoint(prior_breaks_block);
     392    Value * matchRecordNum = iBuilder->CreateAdd(generatePopcount(iBuilder, prior_breaks), recordNum_phi);
     393    Value * reverseDistance = generateCountReverseZeroes(iBuilder, prior_breaks);
     394    Value * width = ConstantInt::get(T, mScanwordBitWidth);
     395    Value * matchRecordStart = iBuilder->CreateAdd(scanwordPos, iBuilder->CreateSub(width, reverseDistance));
     396    iBuilder->CreateBr(loop_final_block);
     397   
     398    // LOOP FINAL BLOCK
     399    // The prior breaks, if any have been counted.  Set up phi nodes for the recordNum
     400    // and recortStart depending on whether the conditional execution of prior_breaks_block.
     401    iBuilder->SetInsertPoint(loop_final_block);
     402    PHINode * matchRecordNum_phi = iBuilder->CreatePHI(T, 2, "matchRecordNum");
     403    PHINode * matchRecordStart_phi = iBuilder->CreatePHI(T, 2, "matchRecordStart");
     404    matchRecordNum_phi->addIncoming(recordNum_phi, process_matches_loop_entry);
     405    matchRecordNum_phi->addIncoming(matchRecordNum, prior_breaks_block);
     406    matchRecordStart_phi->addIncoming(recordStart_phi, process_matches_loop_entry);
     407    matchRecordStart_phi->addIncoming(matchRecordStart, prior_breaks_block);   
     408    Value * matchRecordEnd = iBuilder->CreateAdd(scanwordPos, generateCountForwardZeroes(iBuilder, matches_phi));
     409   
     410
     411    Value * fileBuf = getScalarField(instance, "FileBuf");
     412    if (mIsNameExpression) {
     413        iBuilder->CreateCall(matchProcessor, std::vector<Value *>({matchRecordNum_phi, matchRecordStart_phi, matchRecordEnd, fileBuf}));
     414    } else {
     415        Value * fileSize = getScalarField(instance, "FileSize");
     416        Value * fileIdx = getScalarField(instance, "FileIdx");
     417        iBuilder->CreateCall(matchProcessor, std::vector<Value *>({matchRecordNum_phi, matchRecordStart_phi, matchRecordEnd, fileBuf, fileSize, fileIdx}));
     418    }
     419   
     420    Value * remaining_matches = generateResetLowestBit(iBuilder, matches_phi);
     421    Value * remaining_breaks = iBuilder->CreateXor(record_breaks_phi, prior_breaks);
     422    matches_phi->addIncoming(remaining_matches, loop_final_block);
     423    record_breaks_phi->addIncoming(remaining_breaks, loop_final_block);
     424    recordNum_phi->addIncoming(matchRecordNum_phi, loop_final_block);
     425    recordStart_phi->addIncoming(matchRecordStart_phi, loop_final_block);
     426    iBuilder->CreateBr(matches_test_block);
     427   
     428   
     429    // LOOP EXIT/MATCHES_DONE
     430    iBuilder->SetInsertPoint(matches_done_block);
     431    // When the matches are done, there may be additional record breaks remaining
     432    Value * more_breaks_cond = iBuilder->CreateICmpNE(record_breaks_phi, ConstantInt::get(T, 0));
     433    iBuilder->CreateCondBr(more_breaks_cond, remaining_breaks_block, return_block);
     434   
     435    // REMAINING_BREAKS_BLOCK: process remaining record breaks after all matches are processed
     436    iBuilder->SetInsertPoint(remaining_breaks_block);
     437    Value * break_count = generatePopcount(iBuilder, record_breaks_phi);
     438    Value * final_record_num = iBuilder->CreateAdd(recordNum_phi, break_count);
     439    Value * reverseZeroes = generateCountReverseZeroes(iBuilder, record_breaks_phi);
     440    Value * pendingLineStart = iBuilder->CreateAdd(scanwordPos, iBuilder->CreateSub(width, reverseZeroes));
     441    iBuilder->CreateBr(return_block);
     442   
     443    // RETURN block
     444    iBuilder->SetInsertPoint(return_block);
     445    PHINode * finalRecordCount_phi = iBuilder->CreatePHI(T, 2, "finalRecordCount");
     446    PHINode * finalRecordStart_phi = iBuilder->CreatePHI(T, 2, "finalRecordStart");
     447    finalRecordCount_phi->addIncoming(recordNum_phi, matches_done_block);
     448    finalRecordCount_phi->addIncoming(final_record_num, remaining_breaks_block);
     449    finalRecordStart_phi->addIncoming(recordStart_phi, matches_done_block);
     450    finalRecordStart_phi->addIncoming(pendingLineStart, remaining_breaks_block);
     451    Value * retVal = UndefValue::get(returnType);
     452    retVal = iBuilder->CreateInsertValue(retVal, finalRecordStart_phi, 0);
     453    retVal = iBuilder->CreateInsertValue(retVal, finalRecordCount_phi, 1);
     454    iBuilder->CreateRet(retVal);
     455   
     456    return function;
     457}
     458
     459}
  • icGREP/icgrep-devel/icgrep/kernels/scanmatchgen.h

    r4974 r5055  
    66#define SCANMATCHGEN_H
    77
    8 namespace llvm { class Module; }
     8#include "streamset.h"
     9#include "interface.h"
     10
     11namespace llvm { class Module; class Function;}
    912
    1013namespace IDISA { class IDISA_Builder; }
     
    1619void generateScanMatch(llvm::Module * m, IDISA::IDISA_Builder * iBuilder, unsigned scanWordBitWidth, KernelBuilder * kBuilder, bool isNameExpression);
    1720
     21   
     22   
     23class scanMatchKernel : public KernelInterface {
     24public:
     25    scanMatchKernel(IDISA::IDISA_Builder * iBuilder, unsigned scanwordBitWidth, bool isNameExpression) :
     26    KernelInterface(iBuilder, "scanMatch",
     27                    {StreamSetBinding{StreamSetType(2, 1), "matchResults"}},
     28                    {},
     29                    {ScalarBinding{iBuilder->getInt8PtrTy(), "FileBuf"}, ScalarBinding{iBuilder->getInt64Ty(), "FileSize"}, ScalarBinding{iBuilder->getInt64Ty(), "FileIdx"}},
     30                    {},
     31                    {ScalarBinding{iBuilder->getInt64Ty(), "BlockNo"}, ScalarBinding{iBuilder->getInt64Ty(), "LineStart"}, ScalarBinding{iBuilder->getInt64Ty(), "LineNum"}}),
     32
     33    mScanwordBitWidth(scanwordBitWidth),
     34    mIsNameExpression(isNameExpression) {}
     35       
     36    std::unique_ptr<llvm::Module> createKernelModule() override;
     37
     38private:
     39    llvm::Function * generateScanWordRoutine(llvm::Module * m);
     40       
     41    unsigned mScanwordBitWidth;
     42    bool mIsNameExpression;
     43};
    1844}
    1945
Note: See TracChangeset for help on using the changeset viewer.