Ignore:
Timestamp:
Mar 7, 2016, 3:37:30 PM (3 years ago)
Author:
nmedfort
Message:

Initial modifications to Pablo Compiler and Kernel Builder to support circular buffers for Lookahead.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r4945 r4959  
    7171, mBitBlockType(b->getBitBlockType())
    7272, mCarryManager(nullptr)
    73 , mInputType(nullptr)
     73, mPabloFunction(nullptr)
     74, mPabloBlock(nullptr)
    7475, mKBuilder(nullptr)
    7576, mWhileDepth(0)
    7677, mIfDepth(0)
    7778, mFunction(nullptr)
    78 , mInputAddressPtr(nullptr)
    79 , mOutputAddressPtr(nullptr)
    8079, mMaxWhileDepth(0)
    8180, mFilePosIdx(2) {
     
    8382}
    8483
    85 PabloCompiler::~PabloCompiler() {
    86 }
    87  
    8884void PabloCompiler::setKernel(KernelBuilder * kBuilder){
    8985    mKBuilder = kBuilder;   
     
    9692    #endif
    9793 
    98     PabloBlock * const mainScope = function->getEntryBlock();
    99 
    100     mainScope->enumerateScopes(0);
    101    
    10294    Examine(*function);
    10395
    10496    mCarryManager = new CarryManager(iBuilder);
    10597
    106     GenerateKernel(mainScope, function);
     98    GenerateKernel(function);
    10799       
    108100    delete mCarryManager;
     
    113105    std::cerr << "PABLO COMPILATION TIME: " << (pablo_compilation_end - pablo_compilation_start) << std::endl;
    114106    #endif
    115 
    116107
    117108    if (LLVM_UNLIKELY(DumpGeneratedIR)) {
     
    127118
    128119    #ifndef NDEBUG
    129     raw_os_ostream err(std::cerr);
    130     verifyModule(*mMod, &err);
     120    verifyModule(*mMod, &errs());
    131121    #endif
    132122
     
    134124}
    135125
    136 inline void PabloCompiler::GenerateKernel(PabloBlock * mainScope, PabloFunction * function) {
     126inline void PabloCompiler::GenerateKernel(PabloFunction * const function) {
    137127 
    138     for(int i=0; i<8; i++){
    139         mKBuilder->addKernelInputStream(1, "basis_bits");
    140     }
    141     mKBuilder->addKernelOutputStream(1);
    142     mKBuilder->addKernelOutputStream(1);
    143 
    144     mCarryManager->initialize(mainScope, mKBuilder);
    145  
    146     int segBlocks = mKBuilder->getSegmentBlocks();
    147     mKBuilder->PrepareDoBlockFunction();
    148     struct Inputs inputs = mKBuilder->openDoBlock();
    149     struct Outputs outputs;
     128    mPabloFunction = function;
     129
     130    for (unsigned i = 0; i < function->getNumOfParameters(); ++i) {
     131        mKBuilder->addInputStream(1, function->getParameter(i)->getName()->to_string());
     132    }
     133    for (unsigned i = 0; i < function->getNumOfResults(); ++i) {
     134        mKBuilder->addOutputStream(1);
     135    }
     136
     137    mCarryManager->initialize(function, mKBuilder);
     138
     139    mKBuilder->prepareFunction();
     140
    150141    mFunction = mKBuilder->getDoBlockFunction();
    151     Value * kernelStuctParam = mKBuilder->getKernelStructParam();
    152142
    153143    mCarryManager->initialize_setPtrs(mKBuilder);
    154144
    155     valptr results[segBlocks][2];
    156     for(int j=0; j<segBlocks; j++){     
    157         for(int i=0; i<inputs.streams[j].size(); i++){
    158             mMarkerMap[function->getParameter(i)] = inputs.streams[j][i];
    159         }
    160 
    161         compileBlock(mainScope);
    162 
    163         Value * filePos = iBuilder->CreateAdd(mKBuilder->getKernelInternalState(kernelStuctParam, mFilePosIdx), iBuilder->getInt64(iBuilder->getBitBlockWidth()));
    164         mKBuilder->changeKernelInternalState(kernelStuctParam, mFilePosIdx, filePos);
    165 
    166         mCarryManager->set_BlockNo(mKBuilder);
    167 
    168         results[j][0] = mMarkerMap[function->getResult(0)];
    169         results[j][1] = mMarkerMap[function->getResult(1)];
    170         outputs.streams.push_back(results[j]);
     145    for(unsigned i = 0; i < mKBuilder->getSegmentBlocks(); i++){
     146
     147        for (unsigned j = 0; j < function->getNumOfParameters(); ++j) {
     148            mMarkerMap.insert(std::make_pair(function->getParameter(j), mKBuilder->getInputStream(j)));
     149        }
     150
     151        compileBlock(function->getEntryBlock());
     152
     153        Value * filePos = mKBuilder->getInternalState(mFilePosIdx);
     154        filePos = iBuilder->CreateBlockAlignedLoad(filePos);
     155        filePos = iBuilder->CreateAdd(filePos, iBuilder->getInt64(iBuilder->getBitBlockWidth()));
     156        mKBuilder->setInternalState(mFilePosIdx, filePos);
     157
     158        mCarryManager->setBlockNo(mKBuilder);
     159
     160        for (unsigned j = 0; j < function->getNumOfResults(); ++j) {
     161            const auto f = mMarkerMap.find(function->getResult(j));
     162            Value * result = nullptr;
     163            if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
     164                result = iBuilder->allZeroes();
     165            } else {
     166                result = f->second;
     167            }
     168            iBuilder->CreateBlockAlignedStore(result, mKBuilder->getOutputStream(j));
     169        }
     170
     171        mMarkerMap.clear();
     172
     173        mKBuilder->increment();
    171174    }   
    172175
    173     mKBuilder->closeDoBlock(outputs);
    174     mKBuilder->finalizeMethods();
    175 }
    176 
    177 inline void PabloCompiler::GenerateFunction(PabloFunction & function) {
    178     mInputType = PointerType::get(StructType::get(mMod->getContext(), std::vector<Type *>(function.getNumOfParameters(), mBitBlockType)), 0);
    179     Type * outputType = PointerType::get(StructType::get(mMod->getContext(), std::vector<Type *>(function.getNumOfResults(), mBitBlockType)), 0);
    180     FunctionType * functionType = FunctionType::get(Type::getVoidTy(mMod->getContext()), std::vector<Type *>({mInputType, outputType}), false);
    181 
    182 
    183     //Starts on process_block
    184     SmallVector<AttributeSet, 3> Attrs;
    185     Attrs.push_back(AttributeSet::get(mMod->getContext(), ~0U, std::vector<Attribute::AttrKind>({ Attribute::NoUnwind, Attribute::UWTable })));
    186     Attrs.push_back(AttributeSet::get(mMod->getContext(), 1U, std::vector<Attribute::AttrKind>({ Attribute::ReadOnly, Attribute::NoCapture })));
    187     Attrs.push_back(AttributeSet::get(mMod->getContext(), 2U, std::vector<Attribute::AttrKind>({ Attribute::ReadNone, Attribute::NoCapture })));
    188     AttributeSet AttrSet = AttributeSet::get(mMod->getContext(), Attrs);
    189 
    190     // Create the function that will be generated.
    191     mFunction = Function::Create(functionType, GlobalValue::ExternalLinkage, function.getName()->value(), mMod);
    192     mFunction->setCallingConv(CallingConv::C);
    193     mFunction->setAttributes(AttrSet);
    194 
    195     Function::arg_iterator args = mFunction->arg_begin();
    196     mInputAddressPtr = args++;
    197     mInputAddressPtr->setName("input");
    198     mOutputAddressPtr = args++;
    199     mOutputAddressPtr->setName("output");
     176    mKBuilder->finalize();
    200177}
    201178
     
    205182    mMaxWhileDepth = 0;
    206183    Examine(function.getEntryBlock());
    207     if (LLVM_UNLIKELY(mWhileDepth != 0 || mIfDepth != 0)) {
    208         throw std::runtime_error("Malformed Pablo AST: Unbalanced If or While nesting depth!");
    209     }
    210184}
    211185
     
    213187void PabloCompiler::Examine(PabloBlock * block) {
    214188    for (Statement * stmt : *block) {
    215         if (If * ifStatement = dyn_cast<If>(stmt)) {
    216             Examine(ifStatement->getBody());
    217         }
    218         else if (While * whileStatement = dyn_cast<While>(stmt)) {
     189        if (LLVM_UNLIKELY(isa<If>(stmt))) {
     190            Examine(cast<If>(stmt)->getBody());
     191        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    219192            mMaxWhileDepth = std::max(mMaxWhileDepth, ++mWhileDepth);
    220             Examine(whileStatement->getBody());
     193            Examine(cast<While>(stmt)->getBody());
    221194            --mWhileDepth;
    222195        }
     
    368341    if (const Assign * assign = dyn_cast<const Assign>(stmt)) {
    369342        expr = compileExpression(assign->getExpression());
    370     }
    371     else if (const Next * next = dyn_cast<const Next>(stmt)) {
     343    } else if (const Next * next = dyn_cast<const Next>(stmt)) {
    372344        expr = compileExpression(next->getExpr());
    373     }
    374     else if (const If * ifStatement = dyn_cast<const If>(stmt)) {
     345    } else if (const If * ifStatement = dyn_cast<const If>(stmt)) {
    375346        compileIf(ifStatement);
    376347        return;
    377     }
    378     else if (const While * whileStatement = dyn_cast<const While>(stmt)) {
     348    } else if (const While * whileStatement = dyn_cast<const While>(stmt)) {
    379349        compileWhile(whileStatement);
    380350        return;
    381     }
    382     else if (const Call* call = dyn_cast<Call>(stmt)) {
    383         // Call the callee once and store the result in the marker map.
    384         if (mMarkerMap.count(call)) {
    385             return;
    386         }
    387 
    388         const Prototype * proto = call->getPrototype();
    389         const String * callee = proto->getName();
    390 
    391         Type * inputType = StructType::get(mMod->getContext(), std::vector<Type *>{proto->getNumOfParameters(), mBitBlockType});
    392         Type * outputType = StructType::get(mMod->getContext(), std::vector<Type *>{proto->getNumOfResults(), mBitBlockType});
    393         FunctionType * functionType = FunctionType::get(Type::getVoidTy(mMod->getContext()), std::vector<Type *>{PointerType::get(inputType, 0), PointerType::get(outputType, 0)}, false);
    394 
    395         //Starts on process_block
    396         SmallVector<AttributeSet, 3> Attrs;
    397         Attrs.push_back(AttributeSet::get(mMod->getContext(), 1U, std::vector<Attribute::AttrKind>({ Attribute::ReadOnly, Attribute::NoCapture })));
    398         Attrs.push_back(AttributeSet::get(mMod->getContext(), 2U, std::vector<Attribute::AttrKind>({ Attribute::ReadNone, Attribute::NoCapture })));
    399         AttributeSet AttrSet = AttributeSet::get(mMod->getContext(), Attrs);
    400 
    401         Function * externalFunction = cast<Function>(mMod->getOrInsertFunction(callee->value(), functionType, AttrSet));
    402         if (LLVM_UNLIKELY(externalFunction == nullptr)) {
    403             throw std::runtime_error("Could not create static method call for external function \"" + callee->to_string() + "\"");
    404         }
    405         externalFunction->setCallingConv(llvm::CallingConv::C);
    406 
    407 
    408         AllocaInst * outputStruct = iBuilder->CreateAlloca(outputType);
    409         iBuilder->CreateCall2(externalFunction, mInputAddressPtr, outputStruct);
    410         Value * outputPtr = iBuilder->CreateGEP(outputStruct, std::vector<Value *>({ iBuilder->getInt32(0), iBuilder->getInt32(0) }));
    411         expr = iBuilder->CreateAlignedLoad(outputPtr, iBuilder->getBitBlockWidth() / 8, false);
    412     }
    413     else if (const And * pablo_and = dyn_cast<And>(stmt)) {
     351//    } else if (const Call* call = dyn_cast<Call>(stmt)) {
     352//        // Call the callee once and store the result in the marker map.
     353//        if (LLVM_UNLIKELY(mMarkerMap.count(call) == 0)) {
     354//            return;
     355//        }
     356
     357//        const Prototype * proto = call->getPrototype();
     358//        const String * callee = proto->getName();
     359
     360//        Type * inputType = StructType::get(mMod->getContext(), std::vector<Type *>{proto->getNumOfParameters(), mBitBlockType});
     361//        Type * outputType = StructType::get(mMod->getContext(), std::vector<Type *>{proto->getNumOfResults(), mBitBlockType});
     362//        FunctionType * functionType = FunctionType::get(Type::getVoidTy(mMod->getContext()), std::vector<Type *>{PointerType::get(inputType, 0), PointerType::get(outputType, 0)}, false);
     363
     364//        //Starts on process_block
     365//        SmallVector<AttributeSet, 3> Attrs;
     366//        Attrs.push_back(AttributeSet::get(mMod->getContext(), 1U, std::vector<Attribute::AttrKind>({ Attribute::ReadOnly, Attribute::NoCapture })));
     367//        Attrs.push_back(AttributeSet::get(mMod->getContext(), 2U, std::vector<Attribute::AttrKind>({ Attribute::ReadNone, Attribute::NoCapture })));
     368//        AttributeSet AttrSet = AttributeSet::get(mMod->getContext(), Attrs);
     369
     370//        Function * externalFunction = cast<Function>(mMod->getOrInsertFunction(callee->value(), functionType, AttrSet));
     371//        if (LLVM_UNLIKELY(externalFunction == nullptr)) {
     372//            throw std::runtime_error("Could not create static method call for external function \"" + callee->to_string() + "\"");
     373//        }
     374//        externalFunction->setCallingConv(llvm::CallingConv::C);
     375
     376//        AllocaInst * outputStruct = iBuilder->CreateAlloca(outputType);
     377//        iBuilder->CreateCall2(externalFunction, mInputAddressPtr, outputStruct);
     378//        Value * outputPtr = iBuilder->CreateGEP(outputStruct, std::vector<Value *>({ iBuilder->getInt32(0), iBuilder->getInt32(0) }));
     379
     380//        expr = iBuilder->CreateAlignedLoad(outputPtr, iBuilder->getBitBlockWidth() / 8, false);
     381    } else if (const And * pablo_and = dyn_cast<And>(stmt)) {
    414382        expr = iBuilder->simd_and(compileExpression(pablo_and->getOperand(0)), compileExpression(pablo_and->getOperand(1)));
    415     }
    416     else if (const Or * pablo_or = dyn_cast<Or>(stmt)) {
     383    } else if (const Or * pablo_or = dyn_cast<Or>(stmt)) {
    417384        expr = iBuilder->simd_or(compileExpression(pablo_or->getOperand(0)), compileExpression(pablo_or->getOperand(1)));
    418     }
    419     else if (const Xor * pablo_xor = dyn_cast<Xor>(stmt)) {
     385    } else if (const Xor * pablo_xor = dyn_cast<Xor>(stmt)) {
    420386        expr = iBuilder->simd_xor(compileExpression(pablo_xor->getOperand(0)), compileExpression(pablo_xor->getOperand(1)));
    421     }
    422     else if (const Sel * sel = dyn_cast<Sel>(stmt)) {
     387    } else if (const Sel * sel = dyn_cast<Sel>(stmt)) {
    423388        Value* ifMask = compileExpression(sel->getCondition());
    424389        Value* ifTrue = iBuilder->simd_and(ifMask, compileExpression(sel->getTrueExpr()));
    425390        Value* ifFalse = iBuilder->simd_and(iBuilder->simd_not(ifMask), compileExpression(sel->getFalseExpr()));
    426391        expr = iBuilder->simd_or(ifTrue, ifFalse);
    427     }
    428     else if (const Not * pablo_not = dyn_cast<Not>(stmt)) {
     392    } else if (const Not * pablo_not = dyn_cast<Not>(stmt)) {
    429393        expr = iBuilder->simd_not(compileExpression(pablo_not->getExpr()));
    430     }
    431     else if (const Advance * adv = dyn_cast<Advance>(stmt)) {
     394    } else if (const Advance * adv = dyn_cast<Advance>(stmt)) {
    432395        Value * const strm_value = compileExpression(adv->getExpr());
    433         expr = mCarryManager->advanceCarryInCarryOut(adv->getLocalAdvanceIndex(), adv->getAdvanceAmount(), strm_value);
    434     }
    435     else if (const Mod64Advance * adv = dyn_cast<Mod64Advance>(stmt)) {
     396        expr = mCarryManager->advanceCarryInCarryOut(adv->getLocalIndex(), adv->getAmount(), strm_value);
     397    } else if (const Mod64Advance * adv = dyn_cast<Mod64Advance>(stmt)) {
    436398        Value * const strm_value = compileExpression(adv->getExpr());
    437         expr = iBuilder->simd_slli(64, strm_value, adv->getAdvanceAmount());
    438     }
    439     else if (const MatchStar * mstar = dyn_cast<MatchStar>(stmt)) {
     399        expr = iBuilder->simd_slli(64, strm_value, adv->getAmount());
     400    } else if (const MatchStar * mstar = dyn_cast<MatchStar>(stmt)) {
    440401        Value * const marker = compileExpression(mstar->getMarker());
    441402        Value * const cc = compileExpression(mstar->getCharClass());
     
    443404        Value * const sum = mCarryManager->addCarryInCarryOut(mstar->getLocalCarryIndex(), marker_and_cc, cc);
    444405        expr = iBuilder->simd_or(iBuilder->simd_xor(sum, cc), marker);
    445     }
    446     else if (const Mod64MatchStar * mstar = dyn_cast<Mod64MatchStar>(stmt)) {
     406    } else if (const Mod64MatchStar * mstar = dyn_cast<Mod64MatchStar>(stmt)) {
    447407        Value * const marker = compileExpression(mstar->getMarker());
    448408        Value * const cc = compileExpression(mstar->getCharClass());
     
    450410        Value * const sum = iBuilder->simd_add(64, marker_and_cc, cc);
    451411        expr = iBuilder->simd_or(iBuilder->simd_xor(sum, cc), marker);
    452     }
    453     else if (const ScanThru * sthru = dyn_cast<ScanThru>(stmt)) {
     412    } else if (const ScanThru * sthru = dyn_cast<ScanThru>(stmt)) {
    454413        Value * const  marker_expr = compileExpression(sthru->getScanFrom());
    455414        Value * const  cc_expr = compileExpression(sthru->getScanThru());
    456415        Value * const  sum = mCarryManager->addCarryInCarryOut(sthru->getLocalCarryIndex(), marker_expr, cc_expr);
    457416        expr = iBuilder->simd_and(sum, iBuilder->simd_not(cc_expr));
    458     }
    459     else if (const Mod64ScanThru * sthru = dyn_cast<Mod64ScanThru>(stmt)) {
     417    } else if (const Mod64ScanThru * sthru = dyn_cast<Mod64ScanThru>(stmt)) {
    460418        Value * const marker_expr = compileExpression(sthru->getScanFrom());
    461419        Value * const cc_expr = compileExpression(sthru->getScanThru());
    462420        Value * const sum = iBuilder->simd_add(64, marker_expr, cc_expr);
    463421        expr = iBuilder->simd_and(sum, iBuilder->simd_not(cc_expr));
    464     }
    465     else if (const Count * c = dyn_cast<Count>(stmt)) {
     422    } else if (const Count * c = dyn_cast<Count>(stmt)) {
    466423        Value * const to_count = compileExpression(c->getExpr());
    467424        expr = mCarryManager->popCount(to_count, c->getGlobalCountIndex());
     425    } else if (const Lookahead * l = dyn_cast<Lookahead>(stmt)) {
     426        PabloAST * const var = l->getExpr();
     427        if (LLVM_UNLIKELY(!isa<Var>(var))) {
     428            throw std::runtime_error("Lookahead input type must be a Var object");
     429        }
     430        Value * index = nullptr;
     431        for (unsigned i = 0; i < mPabloFunction->getNumOfParameters(); ++i) {
     432            if (mPabloFunction->getParameter(i) == var) {
     433                index = iBuilder->getInt32(i);
     434                break;
     435            }
     436        }
     437        if (LLVM_UNLIKELY(index == nullptr)) {
     438            throw std::runtime_error("Lookahead has an illegal Var operand");
     439        }
     440        Type * const streamType = iBuilder->getIntNTy(iBuilder->getBitBlockWidth());
     441        const unsigned offset = l->getAmount() / iBuilder->getBitBlockWidth();
     442        const unsigned shift = (l->getAmount() % iBuilder->getBitBlockWidth());
     443        Value * const b0 = iBuilder->CreateBitCast(iBuilder->CreateBlockAlignedLoad(mKBuilder->getInputStream(offset), index), streamType);
     444        Value * const b1 = iBuilder->CreateBitCast(iBuilder->CreateBlockAlignedLoad(mKBuilder->getInputStream(offset + 1), index), streamType);
     445        Value * result = iBuilder->CreateOr(iBuilder->CreateLShr(b0, shift), iBuilder->CreateShl(b1, iBuilder->getBitBlockWidth() - shift), "lookahead");
     446        expr = iBuilder->CreateBitCast(result, iBuilder->getBitBlockType());
    468447    } else {
    469448        std::string tmp;
     
    482461
    483462Value * PabloCompiler::compileExpression(const PabloAST * expr) {
    484     if (isa<Ones>(expr)) {
     463    if (LLVM_UNLIKELY(isa<Ones>(expr))) {
    485464        return iBuilder->allOnes();
    486     }
    487     else if (isa<Zeroes>(expr)) {
     465    } else if (LLVM_UNLIKELY(isa<Zeroes>(expr))) {
    488466        return iBuilder->allZeroes();
    489467    }
     
    497475        throw std::runtime_error(str.str());
    498476    }
    499     return f->second;
    500 }
    501 
    502 void PabloCompiler::SetOutputValue(Value * marker, const unsigned index) {
    503     if (LLVM_UNLIKELY(marker == nullptr)) {
    504         throw std::runtime_error("Cannot set result " + std::to_string(index) + " to Null");
    505     }
    506     if (LLVM_UNLIKELY(marker->getType()->isPointerTy())) {
    507         marker = iBuilder->CreateAlignedLoad(marker, iBuilder->getBitBlockWidth()/8, false);
    508     }
    509     Value* indices[] = {iBuilder->getInt64(0), iBuilder->getInt32(index)};
    510     Value* gep = iBuilder->CreateGEP(mOutputAddressPtr, indices);
    511     if (marker->getType() != mBitBlockType) {
    512         marker = iBuilder->CreateBitCast(marker, mBitBlockType);
    513     }
    514     iBuilder->CreateAlignedStore(marker, gep, iBuilder->getBitBlockWidth()/8, false);
    515 }
    516 
    517 }
     477    Value * result = f->second;
     478    if (LLVM_UNLIKELY(isa<Var>(expr))) {
     479        assert (isa<GetElementPtrInst>(result));
     480        result = iBuilder->CreateBlockAlignedLoad(result);
     481    }
     482    return result;
     483}
     484
     485}
Note: See TracChangeset for help on using the changeset viewer.