Ignore:
Timestamp:
Feb 27, 2017, 2:30:14 PM (2 years ago)
Author:
nmedfort
Message:

Update to BlockOrientedKernel? to move the indirect branch out of the StrideLoopBody? and into StrideLoopDone? to simplify branch prediction.

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

Legend:

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

    r5347 r5351  
    5353}
    5454
    55 
    5655void KernelInterface::addKernelDeclarations(Module * client) {
    5756    Module * saveModule = iBuilder->getModule();
     
    9493        (++args)->setName(ss.name + "_availableItems");
    9594    }
    96 
    97 //    // Add any additional kernel declarations
    98 //    addAdditionalKernelDeclarations(client, selfType);
    9995
    10096    // Create the accumulator get function prototypes
  • icGREP/icgrep-devel/icgrep/kernels/kernel.cpp

    r5350 r5351  
    1212#include <llvm/IR/MDBuilder.h>
    1313#include <llvm/IR/Module.h>
    14 #include <llvm/IR/Verifier.h>
    1514#include <llvm/Support/raw_ostream.h>
    1615#include <llvm/Transforms/Utils/Local.h>
     
    443442    mStrideLoopBody = CreateBasicBlock(getName() + "_strideLoopBody");
    444443    BasicBlock * const stridesDone = CreateBasicBlock(getName() + "_stridesDone");
     444    BasicBlock * const doFinalBlock = CreateBasicBlock(getName() + "_doFinalBlock");
     445    BasicBlock * const segmentDone = CreateBasicBlock(getName() + "_segmentDone");
     446
     447    Value * baseTarget = nullptr;
     448    if (useIndirectBr()) {
     449        baseTarget = iBuilder->CreateSelect(doFinal, BlockAddress::get(doFinalBlock), BlockAddress::get(segmentDone));
     450    }
    445451
    446452    ConstantInt * stride = iBuilder->getSize(iBuilder->getStride());
     
    458464
    459465    iBuilder->SetInsertPoint(strideLoopCond);
     466
     467    PHINode * branchTarget = nullptr;
     468    if (useIndirectBr()) {
     469        branchTarget = iBuilder->CreatePHI(baseTarget->getType(), 2, "branchTarget");
     470        branchTarget->addIncoming(baseTarget, entryBlock);
     471    }
     472
    460473    PHINode * stridesRemaining = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2, "stridesRemaining");
    461474    stridesRemaining->addIncoming(stridesToDo, entryBlock);
    462     Value * notDone = iBuilder->CreateICmpNE(stridesRemaining, iBuilder->getSize(0));
    463     iBuilder->CreateCondBr(notDone, mStrideLoopBody, stridesDone);
     475    Value * notDone = iBuilder->CreateICmpSGT(stridesRemaining, iBuilder->getSize(0));
     476    iBuilder->CreateLikelyCondBr(notDone, mStrideLoopBody, stridesDone);
    464477
    465478    iBuilder->SetInsertPoint(mStrideLoopBody);
    466479
    467480    if (useIndirectBr()) {
    468         mStrideLoopBranchAddress = iBuilder->CreatePHI(iBuilder->getInt8PtrTy(), 2);
    469         mStrideLoopBranchAddress->addIncoming(BlockAddress::get(strideLoopCond), strideLoopCond);       
     481        mStrideLoopTarget = iBuilder->CreatePHI(baseTarget->getType(), 2, "strideTarget");
     482        mStrideLoopTarget->addIncoming(branchTarget, strideLoopCond);
    470483    }
    471484
     
    482495    stridesRemaining->addIncoming(iBuilder->CreateSub(stridesRemaining, iBuilder->getSize(1)), iBuilder->GetInsertBlock());
    483496
     497    BasicBlock * bodyEnd = iBuilder->GetInsertBlock();
    484498    if (useIndirectBr()) {
    485         mStrideLoopBranch = iBuilder->CreateIndirectBr(mStrideLoopBranchAddress, 2);
    486         mStrideLoopBranch->addDestination(strideLoopCond);
     499        branchTarget->addIncoming(mStrideLoopTarget, bodyEnd);
     500    }
     501    iBuilder->CreateBr(strideLoopCond);
     502
     503    stridesDone->moveAfter(bodyEnd);
     504
     505    iBuilder->SetInsertPoint(stridesDone);
     506
     507    // Now conditionally perform the final block processing depending on the doFinal parameter.
     508    if (useIndirectBr()) {
     509        mStrideLoopBranch = iBuilder->CreateIndirectBr(branchTarget, 3);
     510        mStrideLoopBranch->addDestination(doFinalBlock);
     511        mStrideLoopBranch->addDestination(segmentDone);
    487512    } else {
    488         iBuilder->CreateBr(strideLoopCond);
    489     }
    490 
    491     iBuilder->SetInsertPoint(stridesDone);
    492 
    493     // Now conditionally perform the final block processing depending on the doFinal parameter.
    494     BasicBlock * const doFinalBlock = CreateBasicBlock(getName() + "_doFinalBlock");
    495     BasicBlock * const segmentDone = CreateBasicBlock(getName() + "_segmentDone");
    496     iBuilder->CreateCondBr(doFinal, doFinalBlock, segmentDone);
     513        iBuilder->CreateUnlikelyCondBr(doFinal, doFinalBlock, segmentDone);
     514    }
     515
     516    doFinalBlock->moveAfter(stridesDone);
     517
    497518    iBuilder->SetInsertPoint(doFinalBlock);
    498519
    499520    Value * remainingItems = iBuilder->CreateSub(producerPos[0], getProcessedItemCount(mStreamSetInputs[0].name));
    500521    writeFinalBlockMethod(remainingItems);
    501     // if remainingItems was not used, this will eliminate it.
    502     RecursivelyDeleteTriviallyDeadInstructions(remainingItems);
    503522
    504523    itemsDone = producerPos[0];
     
    507526    iBuilder->CreateBr(segmentDone);
    508527
     528    segmentDone->moveAfter(iBuilder->GetInsertBlock());
     529
     530    iBuilder->SetInsertPoint(segmentDone);
     531
     532    // Update the branch prediction metadata to indicate that the likely target will be segmentDone
    509533    if (useIndirectBr()) {
     534        MDBuilder mdb(iBuilder->getContext());
    510535        const auto destinations = mStrideLoopBranch->getNumDestinations();
    511         assert (mStrideLoopBranchAddress->getNumIncomingValues() == destinations);
    512         if (destinations == 1) {
    513             // Final block does not call DoBlock. Replace the indirect branch with a direct one.
    514             iBuilder->SetInsertPoint(mStrideLoopBranch);
    515             iBuilder->CreateBr(strideLoopCond);
    516             mStrideLoopBranch->eraseFromParent();
    517             mStrideLoopBranch = nullptr;
    518             mStrideLoopBranchAddress->eraseFromParent();
    519             mStrideLoopBranchAddress = nullptr;
    520         } else {
    521             MDBuilder mdb(iBuilder->getContext());
    522             uint32_t weights[destinations] = { 100, 0 };
    523             ArrayRef<uint32_t> bw(weights, destinations);
    524             mStrideLoopBranch->setMetadata(LLVMContext::MD_prof, mdb.createBranchWeights(bw));
    525         }
    526     }
    527 
    528     segmentDone->moveAfter(iBuilder->GetInsertBlock());
    529 
    530     iBuilder->SetInsertPoint(segmentDone);
     536        uint32_t weights[destinations];
     537        for (unsigned i = 0; i < destinations; ++i) {
     538            weights[i] = (mStrideLoopBranch->getDestination(i) == segmentDone) ? 100 : 1;
     539        }
     540        ArrayRef<uint32_t> bw(weights, destinations);
     541        mStrideLoopBranch->setMetadata(LLVMContext::MD_prof, mdb.createBranchWeights(bw));
     542    }
    531543
    532544}
     
    580592
    581593    /// Call the do block method if necessary then restore the current function state to the do segement method
    582 
    583594    if (!useIndirectBr()) {
    584595        iBuilder->CreateRetVoid();
     
    613624    }
    614625
    615     generateFinalBlockMethod(remainingItems); // may be implemented by the BlockOrientedKernelBuilder subtype
     626    generateFinalBlockMethod(remainingItems); // may be implemented by the BlockOrientedKernel subtype
     627
     628    RecursivelyDeleteTriviallyDeadInstructions(remainingItems); // if remainingItems was not used, this will eliminate it.
    616629
    617630    if (!useIndirectBr()) {
     
    634647        BasicBlock * bb = CreateBasicBlock("resume");
    635648        mStrideLoopBranch->addDestination(bb);
    636         mStrideLoopBranchAddress->addIncoming(BlockAddress::get(bb), iBuilder->GetInsertBlock());
     649        mStrideLoopTarget->addIncoming(BlockAddress::get(bb), iBuilder->GetInsertBlock());
    637650        iBuilder->CreateBr(mStrideLoopBody);
     651        bb->moveAfter(iBuilder->GetInsertBlock());
    638652        iBuilder->SetInsertPoint(bb);
    639653    } else {
     
    655669, mStrideLoopBody(nullptr)
    656670, mStrideLoopBranch(nullptr)
    657 , mStrideLoopBranchAddress(nullptr) {
     671, mStrideLoopTarget(nullptr) {
    658672
    659673}
  • icGREP/icgrep-devel/icgrep/kernels/kernel.h

    r5350 r5351  
    335335    llvm::BasicBlock *      mStrideLoopBody;
    336336    llvm::IndirectBrInst *  mStrideLoopBranch;
    337     llvm::PHINode *         mStrideLoopBranchAddress;
     337    llvm::PHINode *         mStrideLoopTarget;
    338338};
    339339
Note: See TracChangeset for help on using the changeset viewer.