Ignore:
Timestamp:
May 31, 2017, 4:25:33 PM (2 years ago)
Author:
nmedfort
Message:

Initial attempt to improve debugging capabilities with compilation stack traces on error.

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
14 edited

Legend:

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

    r5464 r5486  
    4444
    4545inline static bool isNonAdvanceCarryGeneratingStatement(const Statement * const stmt) {
    46     switch (stmt->getClassTypeId()) {
    47         case TypeId::ScanThru:
    48         case TypeId::AdvanceThenScanThru:
    49         case TypeId::ScanTo:
    50         case TypeId::AdvanceThenScanTo:
    51         case TypeId::MatchStar:
    52             return true;
    53         default:
    54             return false;
    55     }
     46    return isa<CarryProducingStatement>(stmt) && !isa<Advance>(stmt);
    5647}
    5748
     
    6152 * @brief initializeCarryData
    6253 ** ------------------------------------------------------------------------------------------------------------- */
    63 void CarryManager::initializeCarryData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, PabloKernel * const kernel) {
     54void CarryManager::initializeCarryData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, PabloKernel * const kernel) {
    6455
    6556    // Each scope constructs its own CarryData struct, which will be added to the final "carries" struct
     
    10192
    10293/** ------------------------------------------------------------------------------------------------------------- *
     94 * @brief releaseCarryData
     95 ** ------------------------------------------------------------------------------------------------------------- */
     96void CarryManager::releaseCarryData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, PabloKernel * const kernel) {
     97
     98
     99}
     100
     101/** ------------------------------------------------------------------------------------------------------------- *
    103102 * @brief initializeCodeGen
    104103 ** ------------------------------------------------------------------------------------------------------------- */
    105 void CarryManager::initializeCodeGen(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder) {
     104void CarryManager::initializeCodeGen(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
    106105
    107106    assert(!mCarryMetadata.empty());
     
    132131 * @brief finalizeCodeGen
    133132 ** ------------------------------------------------------------------------------------------------------------- */
    134 void CarryManager::finalizeCodeGen(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder) {
     133void CarryManager::finalizeCodeGen(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
    135134    if (mHasLoop) {
    136135        iBuilder->setScalarField("selector", mNextLoopSelector);
     
    152151 * @brief enterLoopScope
    153152 ** ------------------------------------------------------------------------------------------------------------- */
    154 void CarryManager::enterLoopScope(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const scope) {
     153void CarryManager::enterLoopScope(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const scope) {
    155154    assert (scope);
    156155    assert (mHasLoop);
     
    162161 * @brief enterLoopBody
    163162 ** ------------------------------------------------------------------------------------------------------------- */
    164 void CarryManager::enterLoopBody(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, BasicBlock * const entryBlock) {
     163void CarryManager::enterLoopBody(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, BasicBlock * const entryBlock) {
    165164    if (mCarryInfo->hasSummary()) {
    166165        Type * const carryTy = iBuilder->getBitBlockType();
     
    179178        assert (mCarryInfo->hasSummary());
    180179
     180        Type * const int8PtrTy = iBuilder->getInt8PtrTy();
    181181        Type * const carryTy = iBuilder->getBitBlockType();
    182182        PointerType * const carryPtrTy = carryTy->getPointerTo();
     
    218218        Value * const newCapacitySize = iBuilder->CreateShl(capacitySize, 1); // x 2
    219219
    220 
    221         Value * newArray = iBuilder->CreateAlignedMalloc(newCapacitySize, iBuilder->getCacheAlignment());
    222         iBuilder->CreateMemCpy(newArray, array, capacitySize, BlockWidth);
    223         iBuilder->CreateMemZero(iBuilder->CreateGEP(newArray, capacitySize), capacitySize, BlockWidth);
    224         iBuilder->CreateFree(array);
    225         newArray = iBuilder->CreatePointerCast(newArray, array->getType());
     220        Value * newArray = iBuilder->CreateRealloc(array, newCapacitySize);
     221
     222        Value * const startNewArrayPtr = iBuilder->CreateGEP(iBuilder->CreatePointerCast(newArray, int8PtrTy), capacitySize);
     223        iBuilder->CreateMemZero(startNewArrayPtr, capacitySize, BlockWidth);
     224
    226225        iBuilder->CreateStore(newArray, arrayPtr);
    227226
     
    232231
    233232        Value * const summary = iBuilder->CreateLoad(summaryPtr, false);
    234         Value * newSummary = iBuilder->CreateAlignedMalloc(newSummarySize, BlockWidth);
    235         iBuilder->CreateMemCpy(newSummary, summary, summarySize, BlockWidth);
    236         iBuilder->CreateMemZero(iBuilder->CreateGEP(newSummary, summarySize), iBuilder->getSize(2 * BlockWidth), BlockWidth);
    237         iBuilder->CreateFree(summary);
     233        Value * newSummary = iBuilder->CreateRealloc(summary, newSummarySize);
     234        Value * const startNewSummaryPtr = iBuilder->CreateGEP(iBuilder->CreatePointerCast(newArray, int8PtrTy), summarySize);
     235        iBuilder->CreateMemZero(startNewSummaryPtr, iBuilder->getSize(2 * BlockWidth), BlockWidth);
    238236
    239237        Value * ptr1 = iBuilder->CreateGEP(newSummary, summarySize);
     
    290288 * @brief leaveLoopBody
    291289 ** ------------------------------------------------------------------------------------------------------------- */
    292 void CarryManager::leaveLoopBody(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, BasicBlock * /* exitBlock */) {
     290void CarryManager::leaveLoopBody(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, BasicBlock * /* exitBlock */) {
    293291
    294292    Type * const carryTy = iBuilder->getBitBlockType();
     
    400398 * @brief leaveLoopScope
    401399 ** ------------------------------------------------------------------------------------------------------------- */
    402 void CarryManager::leaveLoopScope(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, BasicBlock * const /* entryBlock */, BasicBlock * const /* exitBlock */) {
     400void CarryManager::leaveLoopScope(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, BasicBlock * const /* entryBlock */, BasicBlock * const /* exitBlock */) {
    403401    assert (mLoopDepth > 0);
    404402    --mLoopDepth;
     
    409407 * @brief enterIfScope
    410408 ** ------------------------------------------------------------------------------------------------------------- */
    411 void CarryManager::enterIfScope(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const scope) {
     409void CarryManager::enterIfScope(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const scope) {
    412410    ++mIfDepth;
    413411    enterScope(iBuilder, scope);
     
    429427 * @brief generateSummaryTest
    430428 ** ------------------------------------------------------------------------------------------------------------- */
    431 Value * CarryManager::generateSummaryTest(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, Value * condition) {
     429Value * CarryManager::generateSummaryTest(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, Value * condition) {
    432430    if (LLVM_LIKELY(mCarryInfo->hasSummary())) {
    433431        assert ("summary test was not generated" && mNextSummaryTest);
     
    442440 * @brief enterIfBody
    443441 ** ------------------------------------------------------------------------------------------------------------- */
    444 void CarryManager::enterIfBody(const std::unique_ptr<kernel::KernelBuilder> &  /* iBuilder */, BasicBlock * const entryBlock) {
     442void CarryManager::enterIfBody(const std::unique_ptr<kernel::KernelBuilder> & /* iBuilder */, BasicBlock * const entryBlock) {
    445443    assert (entryBlock);
    446444}
     
    449447 * @brief leaveIfBody
    450448 ** ------------------------------------------------------------------------------------------------------------- */
    451 void CarryManager::leaveIfBody(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, BasicBlock * const exitBlock) {
     449void CarryManager::leaveIfBody(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, BasicBlock * const exitBlock) {
    452450    assert (exitBlock);
    453451    const auto n = mCarrySummaryStack.size();
     
    463461 * @brief leaveIfScope
    464462 ** ------------------------------------------------------------------------------------------------------------- */
    465 void CarryManager::leaveIfScope(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, BasicBlock * const entryBlock, BasicBlock * const exitBlock) {
     463void CarryManager::leaveIfScope(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, BasicBlock * const entryBlock, BasicBlock * const exitBlock) {
    466464    assert (mIfDepth > 0);
    467465    if (LLVM_LIKELY(mCarryInfo->hasSummary())) {
     
    487485 * @brief enterScope
    488486 ** ------------------------------------------------------------------------------------------------------------- */
    489 void CarryManager::enterScope(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const scope) {
     487void CarryManager::enterScope(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const scope) {
    490488    assert (scope);
    491489    // Store the state of the current frame and update the scope state
     
    506504 * @brief leaveScope
    507505 ** ------------------------------------------------------------------------------------------------------------- */
    508 void CarryManager::leaveScope(const std::unique_ptr<kernel::KernelBuilder> &  /* iBuilder */) {
     506void CarryManager::leaveScope(const std::unique_ptr<kernel::KernelBuilder> & /* iBuilder */) {
    509507
    510508    // Did we use all of the packs in this carry struct?
     
    528526 * @brief addCarryInCarryOut
    529527 ** ------------------------------------------------------------------------------------------------------------- */
    530 Value * CarryManager::addCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const Statement * const operation, Value * const e1, Value * const e2) {
     528Value * CarryManager::addCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const Statement * const operation, Value * const e1, Value * const e2) {
    531529    assert (operation && (isNonAdvanceCarryGeneratingStatement(operation)));
    532530    Value * const carryIn = getNextCarryIn(iBuilder);
     
    541539 * @brief advanceCarryInCarryOut
    542540 ** ------------------------------------------------------------------------------------------------------------- */
    543 Value * CarryManager::advanceCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const Advance * const advance, Value * const value) {
     541Value * CarryManager::advanceCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const Advance * const advance, Value * const value) {
    544542    const auto shiftAmount = advance->getAmount();
    545543    if (LLVM_LIKELY(shiftAmount < LONG_ADVANCE_BREAKPOINT)) {
     
    558556 * @brief longAdvanceCarryInCarryOut
    559557 ** ------------------------------------------------------------------------------------------------------------- */
    560 inline Value * CarryManager::longAdvanceCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, Value * const value, const unsigned shiftAmount) {
     558inline Value * CarryManager::longAdvanceCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, Value * const value, const unsigned shiftAmount) {
    561559
    562560    assert (mHasLongAdvance);
     
    638636 * @brief getNextCarryIn
    639637 ** ------------------------------------------------------------------------------------------------------------- */
    640 Value * CarryManager::getNextCarryIn(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder) {
     638Value * CarryManager::getNextCarryIn(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
    641639    assert (mCurrentFrameIndex < mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
    642640    if (mLoopDepth == 0) {
     
    657655 * @brief setNextCarryOut
    658656 ** ------------------------------------------------------------------------------------------------------------- */
    659 void CarryManager::setNextCarryOut(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, Value * carryOut) {
     657void CarryManager::setNextCarryOut(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, Value * carryOut) {
    660658    Type * const carryTy = iBuilder->getBitBlockType();
    661659    assert (mCurrentFrameIndex < mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
     
    679677 * @brief readCarryInSummary
    680678 ** ------------------------------------------------------------------------------------------------------------- */
    681 Value * CarryManager::readCarryInSummary(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, ConstantInt * index) const {
     679Value * CarryManager::readCarryInSummary(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, ConstantInt * index) const {
    682680    assert (mCarryInfo->hasSummary());
    683681    unsigned count = 2;
     
    711709 * @brief writeCarryOutSummary
    712710 ** ------------------------------------------------------------------------------------------------------------- */
    713 inline void CarryManager::writeCarryOutSummary(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, Value * const summary, ConstantInt * index) const {
     711inline void CarryManager::writeCarryOutSummary(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, Value * const summary, ConstantInt * index) const {
    714712    Value * ptr = nullptr;
    715713    assert (mCarryInfo->hasExplicitSummary());
     
    725723 * @brief addToCarryOutSummary
    726724 ** ------------------------------------------------------------------------------------------------------------- */
    727 inline void CarryManager::addToCarryOutSummary(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, Value * const value) {
     725inline void CarryManager::addToCarryOutSummary(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, Value * const value) {
    728726    assert ("cannot add null summary value!" && value);   
    729727    assert ("summary stack is empty!" && !mCarrySummaryStack.empty());
     
    748746 ** ------------------------------------------------------------------------------------------------------------- */
    749747bool CarryManager::hasIterationSpecificAssignment(const PabloBlock * const scope) {
     748#if 0
     749    return dyn_cast_or_null<While>(scope->getBranch()) != nullptr;
     750#else
    750751    if (const While * const br = dyn_cast_or_null<While>(scope->getBranch())) {
    751752        for (const Var * var : br->getEscaped()) {
     
    771772    }
    772773    return false;
     774#endif
    773775}
    774776
     
    776778 * @brief analyse
    777779 ** ------------------------------------------------------------------------------------------------------------- */
    778 StructType * CarryManager::analyse(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const scope, const unsigned ifDepth, const unsigned loopDepth, const bool isNestedWithinNonCarryCollapsingLoop) {
     780StructType * CarryManager::analyse(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const scope, const unsigned ifDepth, const unsigned loopDepth, const bool isNestedWithinNonCarryCollapsingLoop) {
    779781    assert ("scope cannot be null!" && scope);
    780782    assert (mCarryScopes == 0 ? (scope == mKernel->getEntryBlock()) : (scope != mKernel->getEntryBlock()));
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.h

    r5440 r5486  
    4646    CarryManager() noexcept;
    4747
    48     void initializeCarryData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, PabloKernel * const kernel);
     48    void initializeCarryData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, PabloKernel * const kernel);
    4949
    50     void initializeCodeGen(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
     50    void releaseCarryData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, PabloKernel * const kernel);
    5151
    52     void finalizeCodeGen(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
     52    void initializeCodeGen(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
     53
     54    void finalizeCodeGen(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
    5355
    5456    /* Entering and leaving loops. */
    5557
    56     void enterLoopScope(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const scope);
     58    void enterLoopScope(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const scope);
    5759
    58     void enterLoopBody(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::BasicBlock * const entryBlock);
     60    void enterLoopBody(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::BasicBlock * const entryBlock);
    5961
    60     void leaveLoopBody(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::BasicBlock * const exitBlock);
     62    void leaveLoopBody(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::BasicBlock * const exitBlock);
    6163
    62     void leaveLoopScope(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::BasicBlock * const entryBlock, llvm::BasicBlock * const exitBlock);
     64    void leaveLoopScope(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::BasicBlock * const entryBlock, llvm::BasicBlock * const exitBlock);
    6365
    6466    /* Entering and leaving ifs. */
    6567
    66     void enterIfScope(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const scope);
     68    void enterIfScope(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const scope);
    6769
    68     void enterIfBody(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::BasicBlock * const entryBlock);
     70    void enterIfBody(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::BasicBlock * const entryBlock);
    6971
    70     void leaveIfBody(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::BasicBlock * const exitBlock);
     72    void leaveIfBody(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::BasicBlock * const exitBlock);
    7173
    72     void leaveIfScope(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::BasicBlock * const entryBlock, llvm::BasicBlock * const exitBlock);
     74    void leaveIfScope(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::BasicBlock * const entryBlock, llvm::BasicBlock * const exitBlock);
    7375
    7476    /* Methods for processing individual carry-generating operations. */
    7577   
    76     llvm::Value * addCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const Statement * operation, llvm::Value * const e1, llvm::Value * const e2);
     78    llvm::Value * addCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const Statement * operation, llvm::Value * const e1, llvm::Value * const e2);
    7779
    78     llvm::Value * advanceCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const Advance * advance, llvm::Value * const strm);
     80    llvm::Value * advanceCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const Advance * advance, llvm::Value * const strm);
    7981 
    8082    /* Methods for getting and setting carry summary values for If statements */
    8183         
    82     llvm::Value * generateSummaryTest(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::Value * condition);
     84    llvm::Value * generateSummaryTest(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::Value * condition);
    8385
    8486protected:
     
    8890    static bool hasIterationSpecificAssignment(const PabloBlock * const scope);
    8991
    90     llvm::StructType * analyse(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const scope, const unsigned ifDepth = 0, const unsigned whileDepth = 0, const bool isNestedWithinNonCarryCollapsingLoop = false);
     92    llvm::StructType * analyse(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const scope, const unsigned ifDepth = 0, const unsigned whileDepth = 0, const bool isNestedWithinNonCarryCollapsingLoop = false);
    9193
    9294    /* Entering and leaving scopes. */
    93     void enterScope(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const scope);
    94     void leaveScope(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
     95    void enterScope(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const scope);
     96    void leaveScope(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
    9597
    9698    /* Methods for processing individual carry-generating operations. */
    97     llvm::Value * getNextCarryIn(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
    98     void setNextCarryOut(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::Value * const carryOut);
    99     llvm::Value * longAdvanceCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::Value * const value, const unsigned shiftAmount);
    100     llvm::Value * readCarryInSummary(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::ConstantInt *index) const;
    101     void writeCarryOutSummary(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::Value * const summary, llvm::ConstantInt * index) const;
     99    llvm::Value * getNextCarryIn(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
     100    void setNextCarryOut(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::Value * const carryOut);
     101    llvm::Value * longAdvanceCarryInCarryOut(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::Value * const value, const unsigned shiftAmount);
     102    llvm::Value * readCarryInSummary(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::ConstantInt *index) const;
     103    void writeCarryOutSummary(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::Value * const summary, llvm::ConstantInt * index) const;
    102104
    103105    /* Summary handling routines */
    104     void addToCarryOutSummary(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, llvm::Value * const value);
     106    void addToCarryOutSummary(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, llvm::Value * const value);
    105107
    106108private:
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r5454 r5486  
    337337            }
    338338        } else { // characterize this statement then check whether it is equivalent to any existing one.
    339             PabloAST * const folded = Simplifier::fold(stmt, block);
     339            PabloAST * const folded = Simplifier::triviallyFold(stmt, block);
    340340            if (LLVM_UNLIKELY(folded != nullptr)) {
    341341                stmt = stmt->replaceWith(folded);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r5464 r5486  
    99#include <pablo/pe_ones.h>
    1010#include <pablo/boolean.h>
     11#include <pablo/pe_var.h>
    1112#include <boost/container/flat_set.hpp>
    1213#include <boost/container/flat_map.hpp>
     14#include <boost/range/adaptor/reversed.hpp>
    1315#include <boost/graph/adjacency_list.hpp>
    1416#include <boost/graph/topological_sort.hpp>
    1517#include <boost/function_output_iterator.hpp>
     18#include <set>
    1619
    1720#include <boost/graph/strong_components.hpp>
     
    2528using VertexData = std::pair<pablo::PabloAST *, TypeId>;
    2629
    27 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, VertexData, pablo::PabloAST *>;
     30using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, pablo::PabloAST *>;
    2831using Vertex = Graph::vertex_descriptor;
    29 
    30 using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
    31 using DistributionVertex = DistributionGraph::vertex_descriptor;
     32using in_edge_iterator = graph_traits<Graph>::in_edge_iterator;
     33using out_edge_iterator = graph_traits<Graph>::out_edge_iterator;
    3234
    3335using VertexSet = std::vector<Vertex>;
     
    145147struct PassContainer {
    146148
     149    enum Modification {
     150        None, Trivial, Structural
     151    };
     152
    147153    /** ------------------------------------------------------------------------------------------------------------- *
    148154     * @brief run
     
    166172     * Try to eliminate some of the unnecessary operations from the current Variadic expressions
    167173     ** ------------------------------------------------------------------------------------------------------------- */
     174    void run(PabloKernel * const kernel) {
     175        run(kernel->getEntryBlock());
     176
     177        printGraph(G, "G", errs());
     178        if (simplifyGraph() == Structural) {
     179            // rewriteAST(first, stmt);
     180            printGraph(G, "O", errs());
     181        }
     182
     183    }
     184
    168185    void run(PabloBlock * const block) {
    169         Statement * stmt = block->front();
    170         // Statement * first = stmt;
    171         while (stmt) {
    172             Statement * next = stmt->getNextNode();
     186        for (Statement * stmt : *block) {           
    173187            if (isa<Branch>(stmt)) {
    174                 // addUsageInformation();
    175                 if (simplifyGraph()) {
    176                     // rewriteAST(first, stmt);
    177 
    178                     // printGraph(G, "G", errs());
    179                 }
    180 
    181 
    182 
    183                 G.clear();
    184                 M.clear();
     188                addBranch(stmt);
    185189                run(cast<Branch>(stmt)->getBody());
    186                 G.clear();
    187                 M.clear();
    188190            } else {
    189191                addStatement(stmt);
    190192            }
    191             stmt = next;
    192         }
     193        }
     194
     195//        G.clear();
     196//        M.clear();
     197//        for (Statement * stmt : *block) {
     198//            addStatement(stmt);
     199//        }
     200
     201//        printGraph(G, "G", errs());
     202//        if (simplifyGraph() == Structural) {
     203//            // rewriteAST(first, stmt);
     204//            printGraph(G, "O", errs());
     205//        }
     206
     207    }
     208
     209    /** ------------------------------------------------------------------------------------------------------------- *
     210     * @brief simplifyGraph
     211     ** ------------------------------------------------------------------------------------------------------------- */
     212    Modification simplifyGraph() {
     213        Modification modified = None;
     214        for (;;) {
     215            const auto p1 = applyAssociativeIdentityAnnulmentLaws();
     216            const auto p2 = applyAbsorbtionComplementIdempotentLaws();
     217            const auto p3 = applyDistributivityLaw();
     218            if (std::max(std::max(p1, p2), p3) != Structural) {
     219                break;
     220            }
     221            modified = Structural;
     222        }
     223        return modified;
    193224    }
    194225
    195226protected:
    196227
    197 //    /** ------------------------------------------------------------------------------------------------------------- *
    198 //     * @brief addUsageInformation
    199 //     *
    200 //     * Populate G with the user information of each statement so that we can determine whether it'll be cost effective
    201 //     * to distribute an operation.
    202 //     ** ------------------------------------------------------------------------------------------------------------- */
    203 //    void addUsageInformation() {
    204 //        for (const Vertex u : make_iterator_range(vertices(G))) {
    205 //            PabloAST * expr; TypeId typeId;
    206 //            std::tie(expr, typeId) = G[u];
    207 //            if (LLVM_LIKELY(typeId != TypeId::Var)) {
    208 //                for (PabloAST * user : expr->users()) {
    209 //                    add_edge(u, addExpression(user), user, G);
    210 //                }
    211 //            }
    212 //        }
    213 //    }
    214 
    215228    /** ------------------------------------------------------------------------------------------------------------- *
    216229     * @brief applyAssociativeIdentityAnnulmentLaws
    217230     ** ------------------------------------------------------------------------------------------------------------- */
    218     bool applyAssociativeIdentityAnnulmentLaws() {
    219 
    220         bool modified = false;
    221 
    222         std::function<void(const Vertex)> apply = [&](const Vertex u) {
    223             PabloAST * expr; TypeId typeId;
    224             std::tie(expr, typeId) = G[u];
    225 
    226 
    227 
    228             if (LLVM_UNLIKELY(typeId == TypeId::Zeroes || typeId == TypeId::Ones)) {
    229 repeat:         for (auto e : make_iterator_range(out_edges(u, G))) {
    230                     const auto v = target(e, G);
    231                     const auto targetTypeId = getType(v);
    232                     if (LLVM_UNLIKELY(isAssociative(targetTypeId))) {
    233                         if (isIdentityRelation(typeId, targetTypeId)) {
    234                             remove_edge(e, G);
    235                         } else {
    236                             setType(v, typeId == TypeId::And ? TypeId::Zeroes : TypeId::Ones);
    237                             clear_in_edges(v, G);
    238                             apply(v);
    239                         }
    240                         modified = true;
    241                         goto repeat;
     231    Modification applyAssociativeIdentityAnnulmentLaws() {
     232
     233        auto identityComparator = [this](const Vertex u, const Vertex v) -> bool {
     234            const auto typeA = getType(u);
     235            assert (typeA != TypeId::Var);
     236            const auto typeB = getType(v);
     237            assert (typeB != TypeId::Var);
     238            if (LLVM_LIKELY(typeA != typeB)) {
     239                using value_of = std::underlying_type<TypeId>::type;
     240                return static_cast<value_of>(typeA) < static_cast<value_of>(typeB);
     241            } else {
     242                const auto degA = in_degree(u, G);
     243                const auto degB = in_degree(v, G);
     244                if (degA != degB) {
     245                    return degA < degB;
     246                } else {
     247                    Vertex adjA[degA];
     248                    Vertex adjB[degA];
     249                    in_edge_iterator ei, ej;
     250                    std::tie(ei, std::ignore) = in_edges(u, G);
     251                    std::tie(ej, std::ignore) = in_edges(v, G);
     252                    for (size_t i = 0; i < degA; ++i, ++ei, ++ej) {
     253                        adjA[i] = source(*ei, G);
     254                        adjB[i] = source(*ej, G);
     255                    }
     256                    std::sort(adjA, adjA + degA);
     257                    std::sort(adjB, adjB + degA);
     258                    for (size_t i = 0; i < degA; ++i) {
     259                        if (adjA[i] < adjB[i]) {
     260                            return true;
     261                        }
     262                    }
     263                    return false;
     264                }
     265            }
     266        };
     267
     268        flat_set<Vertex, decltype(identityComparator)> V(identityComparator);
     269        V.reserve(num_vertices(G));
     270
     271        VertexSet ordering;
     272        ordering.reserve(num_vertices(G));
     273
     274        topological_sort(G, std::back_inserter(ordering)); // note: ordering is in reverse topological order
     275
     276        Modification modified = None;
     277
     278        for (const auto u : boost::adaptors::reverse(ordering)) {
     279            const TypeId typeId = getType(u);
     280            if (isImmutable(typeId)) {
     281                continue;
     282            } else if (LLVM_UNLIKELY(typeId == TypeId::Zeroes || typeId == TypeId::Ones)) {
     283                for(;;) {
     284                    bool done = true;
     285                    for (auto e : make_iterator_range(out_edges(u, G))) {
     286                        const auto v = target(e, G);
     287                        const auto targetTypeId = getType(v);
     288                        if (LLVM_UNLIKELY(isAssociative(targetTypeId))) {
     289
     290                            errs() << " -- identity relationship\n";
     291
     292                            if (isIdentityRelation(typeId, targetTypeId)) {
     293                                remove_edge(e, G);
     294                            } else {
     295                                setType(v, typeId == TypeId::And ? TypeId::Zeroes : TypeId::Ones);
     296                                clear_in_edges(v, G);
     297                            }
     298                            done = false;
     299                            modified = Structural;
     300                            break;
     301                        }
     302                    }
     303                    if (done) {
     304                        break;
    242305                    }
    243306                }
    244307            } else if (isAssociative(typeId)) {
    245 
    246                 bool contractable = true;
    247                 // an associative operation with only one element is always equivalent to the element
    248                 if (LLVM_LIKELY(in_degree(u, G) != 1)) {
    249                     for (auto e : make_iterator_range(out_edges(u, G))) {
    250                         if (LLVM_LIKELY(typeId != getType(target(e, G)))) {
    251                             contractable = false;
    252                             break;
    253                         }
    254                     }
    255                 }
    256                 if (LLVM_UNLIKELY(contractable)) {
    257                     for (auto ei : make_iterator_range(in_edges(u, G))) {
    258                         for (auto ej : make_iterator_range(out_edges(u, G))) {
    259                             add_edge(source(ei, G), target(ej, G), expr, G);
    260                         }
    261                     }
    262                     clear_vertex(u, G);
    263                     setType(u, TypeId::Var);
    264                     modified = true;
    265                 }
    266             }
    267         };
    268 
    269         // note: calls "apply" on each vertex in reverse topological order
    270         topological_sort(G, boost::make_function_output_iterator(apply));
    271 
     308                if (LLVM_UNLIKELY(in_degree(u, G) == 0)) {
     309                    setType(u, TypeId::Zeroes);
     310                } else {
     311                    // An associative operation with only one element is always equivalent to the element
     312                    bool contractable = true;
     313                    if (LLVM_LIKELY(in_degree(u, G) > 1)) {
     314                        for (auto e : make_iterator_range(out_edges(u, G))) {
     315                            if (LLVM_LIKELY(typeId != getType(target(e, G)))) {
     316                                contractable = false;
     317                                break;
     318                            }
     319                        }
     320                    }
     321                    if (LLVM_UNLIKELY(contractable)) {
     322                        for (auto ei : make_iterator_range(in_edges(u, G))) {
     323                            for (auto ej : make_iterator_range(out_edges(u, G))) {
     324                                addEdge(source(ei, G), target(ej, G), G[ei]);
     325                            }
     326                        }
     327                        removeVertex(u);
     328                        modified = std::max(modified, Trivial);
     329                        continue;
     330                    }
     331
     332                    if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
     333                        // TODO:: (A ⊕ ¬B) = (A ⊕ (B ⊕ 1)) = ¬(A ⊕ B)
     334
     335                    }
     336
     337
     338
     339                }
     340            }
     341
     342            assert (getType(u) != TypeId::Var);
     343
     344            const auto f = V.insert(u);
     345            if (LLVM_UNLIKELY(!f.second)) {
     346                const auto v = *f.first;
     347
     348                errs() << " -- replacing " << u << " with " << v << "\n";
     349
     350                for (auto e : make_iterator_range(out_edges(u, G))) {
     351                    addEdge(v, target(e, G), G[e]);
     352                }
     353                removeVertex(u);
     354                modified = Structural;
     355            }
     356        }
    272357        return modified;
    273358    }
     
    276361     * @brief applyAbsorbtionComplementIdempotentLaws
    277362     ** ------------------------------------------------------------------------------------------------------------- */
    278     bool applyAbsorbtionComplementIdempotentLaws() {
    279         using in_edge_iterator = graph_traits<Graph>::in_edge_iterator;
    280         bool modified = false;
     363    Modification applyAbsorbtionComplementIdempotentLaws() {
     364        Modification modified = None;
    281365        for (const Vertex u : make_iterator_range(vertices(G))) {
    282366            const TypeId typeId = getType(u);
     
    293377                            for (auto ek = ek_begin; ek != ek_end; ++ek) {
    294378                                if (LLVM_UNLIKELY(source(*ej, G) == source(*ek, G))) {
     379                                    modified = Structural;
    295380                                    if (LLVM_UNLIKELY(innerTypeId == TypeId::Not)) {
    296381                                        // complement
     
    305390                                            // absorbtion
    306391                                            remove_edge(*ej, G);
    307                                         }
    308                                         modified = true;
     392                                        }                                       
    309393                                        // this seldom occurs so if it does, just restart the process rather than
    310394                                        // trying to keep the iterators valid.
     
    322406    }
    323407
    324 
    325     /** ------------------------------------------------------------------------------------------------------------- *
    326      * @brief contractGraph
    327      *
    328      * This function scans through a scope block and computes a DAG G in which any sequences of AND, OR or XOR functions
    329      * are "flattened" (i.e., allowed to have any number of inputs.)
    330      ** ------------------------------------------------------------------------------------------------------------- */
    331     bool contractGraph() {
    332         bool modified = false;
    333         bool alreadyGoneOnce = false;
    334         for (;;) {
    335             if (applyAssociativeIdentityAnnulmentLaws()) {
    336                 modified = true;
    337             } else if (alreadyGoneOnce) {
    338                 break;
    339             }
    340             if (applyAbsorbtionComplementIdempotentLaws()) {
    341                 modified = true;
    342             } else { // if (alreadyGoneOnce) {
    343                 break;
    344             }
    345             alreadyGoneOnce = true;
    346         }
    347         return modified;
    348     }
    349 
    350     /** ------------------------------------------------------------------------------------------------------------- *
    351      * @brief addVertex
    352      ** ------------------------------------------------------------------------------------------------------------- */
    353     DistributionVertex addVertex(const Vertex u) {
    354         const auto f = D.find(u);
    355         if (LLVM_LIKELY(f != D.end())) {
    356             return f->second;
    357         }
    358         const auto v = add_vertex(u, H);
    359         D.emplace(u, v);
    360         return v;
    361     }
    362 
    363     /** ------------------------------------------------------------------------------------------------------------- *
    364      * @brief generateDistributionGraph
     408    /** ------------------------------------------------------------------------------------------------------------- *
     409     * @brief identifyDistributableVertices
    365410     *
    366411     * Let (u) ∈ V(G) be a conjunction ∧ or disjunction √ and (v) be a ∧ or √ and the opposite type of (u). If (u,v) ∈
     
    375420     *
    376421     ** ------------------------------------------------------------------------------------------------------------- */
    377     void generateDistributionGraph() {
    378 
    379         assert (D.empty());
    380 
    381         flat_set<Vertex> distributable;
    382         flat_set<Vertex> observed;
     422    void identifyDistributableVertices() {
     423
     424        assert (D.empty() && L.empty());
    383425
    384426        for (const Vertex u : make_iterator_range(vertices(G))) {
    385427            const TypeId outerTypeId = getType(u);
    386428            if (isDistributive(outerTypeId)) {
     429                bool beneficial = true;
    387430                const TypeId innerTypeId = oppositeTypeId(outerTypeId);
    388                 for (auto e : make_iterator_range(in_edges(u, G))) {
    389                     const Vertex v = source(e, G);
    390                     if (LLVM_UNLIKELY(std::get<1>(G[v]) == innerTypeId)) {
    391                         bool beneficial = true;
    392                         for (const auto e : make_iterator_range(out_edges(v, G))) {
    393                             if (std::get<1>(G[target(e, G)]) != outerTypeId) {
    394                                 beneficial = false;
    395                                 break;
    396                             }
    397                         }
    398                         if (beneficial) {
    399                             distributable.insert(v);
    400                         }
    401                     }
    402                 }
    403                 if (LLVM_LIKELY(distributable.size() > 1)) {
    404                     for (const Vertex v : distributable) {
    405                         for (auto e : make_iterator_range(in_edges(v, G))) {
    406                             observed.insert(source(e, G));
    407                         }
    408                     }
    409                     for (const Vertex w : observed) {
    410                         for (auto e : make_iterator_range(out_edges(w, G))) {
    411                             const Vertex v = target(e, G);
    412                             if (distributable.count(v)) {
    413                                 const Vertex y = addVertex(v);
    414                                 boost::add_edge(y, addVertex(u), H);
    415                                 boost::add_edge(addVertex(w), y, H);
    416                             }
    417                         }
    418                     }
    419                     observed.clear();
    420                 }
    421                 distributable.clear();
     431                for (auto e : make_iterator_range(out_edges(u, G))) {
     432                    const Vertex v = target(e, G);
     433                    if (LLVM_UNLIKELY(getType(v) != innerTypeId)) {
     434                        beneficial = false;
     435                        break;
     436                    }
     437                }
     438                if (beneficial) {
     439                    for (auto e : make_iterator_range(out_edges(u, G))) {
     440                        const auto v = target(e, G);
     441                        const auto f = std::lower_bound(D.begin(), D.end(), v);
     442                        if (f == D.end() || *f != v) {
     443                            D.insert(f, v);
     444                            assert (std::is_sorted(D.begin(), D.end()));
     445                        }
     446                    }
     447                    for (auto e : make_iterator_range(in_edges(u, G))) {
     448                        const auto v = source(e, G);
     449                        const auto f = std::lower_bound(L.begin(), L.end(), v);
     450                        if (f == L.end() || *f != v) {
     451                            L.insert(f, v);
     452                            assert (std::is_sorted(L.begin(), L.end()));
     453                        }
     454                    }
     455                }
     456            }
     457        }
     458
     459        // D = D - L
     460
     461        if (!L.empty()) {
     462            if (!D.empty()) {
     463                auto di = D.begin(), li = L.begin(), li_end = L.end();
     464                for (;;) {
     465                    if (*li < *di) {
     466                        if (++li == li_end) {
     467                            break;
     468                        }
     469                    } else {
     470                        if (*di < *li) {
     471                            ++di;
     472                        } else {
     473                            di = D.erase(di);
     474                        }
     475                        if (di == D.end()) {
     476                            break;
     477                        }
     478                    }
     479                }
     480            }
     481            L.clear();
     482        }
     483    }
     484
     485    /** ------------------------------------------------------------------------------------------------------------- *
     486     * @brief applyDistributivityLaw
     487     ** ------------------------------------------------------------------------------------------------------------- */
     488    Modification applyDistributivityLaw() {
     489
     490        identifyDistributableVertices();
     491
     492        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
     493        if (D.empty()) {
     494            return None;
     495        }
     496
     497        Modification modified = None;
     498
     499        const auto lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(D)), 1);
     500
     501        for (auto & lower : lowerSet) {
     502            const auto upperSet = independentCliqueSets<0>(enumerateBicliques(std::get<1>(lower)), 2);
     503            for (const auto & upper : upperSet) {
     504
     505                const auto & sources = std::get<1>(upper);
     506                const auto & intermediary = std::get<0>(upper);
     507                const auto & sinks = std::get<0>(lower);
     508
     509
     510
     511                const auto outerTypeId = getType(sinks.front());
     512                const auto innerTypeId = oppositeTypeId(outerTypeId);
     513
     514                errs() << " -- distributing\n";
     515
     516                // Update G to match the desired change
     517                const auto x = makeVertex(outerTypeId);
     518                const auto y = makeVertex(innerTypeId);
     519
     520                for (const auto i : intermediary) {
     521                    assert (getType(i) == innerTypeId);
     522                    for (const Vertex t : sinks) {
     523                        assert (getType(t) == outerTypeId);
     524                        remove_edge(i, t, G);
     525                    }
     526                    addEdge(i, x);
     527                }
     528
     529                for (const Vertex s : sources) {
     530                    for (const Vertex i : intermediary) {
     531                        remove_edge(s, i, G);
     532                    }
     533                    addEdge(s, y);
     534                }
     535                addEdge(x, y);
     536
     537                for (const Vertex t : sinks) {
     538                    addEdge(y, t, std::get<0>(G[t]));
     539                }
     540
     541                modified = Structural;
    422542            }
    423543        }
    424544
    425545        D.clear();
    426     }
    427 
    428 
    429     /** ------------------------------------------------------------------------------------------------------------- *
    430      * @brief redistributeAST
    431      *
    432      * Apply the distribution law to reduce computations whenever possible.
    433      ** ------------------------------------------------------------------------------------------------------------- */
    434     bool simplifyGraph() {
    435 
    436         VertexSet sinks;
    437 
    438         bool modified = false;
    439 
    440         for (;;) {
    441 
    442             assert (num_vertices(H) == 0 && num_edges(H) == 0);
    443 
    444             if (contractGraph()) {
    445                 modified = true;
    446             }
    447 
    448             generateDistributionGraph();
    449 
    450             // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
    451             if (num_vertices(H) == 0) {
    452                 break;
    453             }
    454 
    455             for (const Vertex u : make_iterator_range(vertices(H))) {
    456                 if (out_degree(u, H) == 0 && in_degree(u, H) != 0) {
    457                     sinks.push_back(u);
    458                 }
    459             }
    460             std::sort(sinks.begin(), sinks.end());
    461 
    462             bool done = true;
    463 
    464             const auto lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(sinks)), 1);
    465 
    466             for (auto & lower : lowerSet) {
    467                 const auto upperSet = independentCliqueSets<0>(enumerateBicliques(std::get<1>(lower)), 2);
    468                 for (const auto & upper : upperSet) {
    469 
    470                     const auto & sources = std::get<1>(upper);
    471                     const auto & intermediary = std::get<0>(upper);
    472                     const auto & sinks = std::get<0>(lower);
    473 
    474                     const auto outerTypeId = getType(H[sinks.front()]);
    475                     const auto innerTypeId = oppositeTypeId(outerTypeId);
    476 
    477                     // Update G to match the desired change
    478                     const auto x = makeVertex(outerTypeId);
    479                     const auto y = makeVertex(innerTypeId);
    480 
    481                     for (const auto i : intermediary) {
    482                         const auto u = H[i];
    483                         assert (getType(u) == innerTypeId);
    484                         for (const Vertex t : sinks) {
    485                             assert (getType(H[t]) == outerTypeId);
    486                             remove_edge(u, H[t], G);
    487                         }
    488                         add_edge(u, x, nullptr, G);
    489                     }
    490 
    491                     for (const Vertex s : sources) {
    492                         const auto u = H[s];
    493                         for (const Vertex i : intermediary) {
    494                             remove_edge(u, H[i], G);
    495                         }
    496                         add_edge(u, y, nullptr, G);
    497                     }
    498                     add_edge(x, y, nullptr, G);
    499 
    500                     for (const Vertex t : sinks) {
    501                         const auto v = H[t];
    502                         add_edge(y, v, std::get<0>(G[v]), G);
    503                     }
    504 
    505                     done = false;
    506                 }
    507             }
    508 
    509             H.clear();
    510 
    511             if (done) {
    512                 break;
    513             } else {
    514                 sinks.clear();
    515                 modified = true;
    516             }
    517         }
    518 
    519         assert (num_vertices(H) == 0 && num_edges(H) == 0);
    520546
    521547        return modified;
     
    536562        IntersectionSets B1;
    537563        for (auto u : A) {
    538             if (in_degree(u, H) > 0) {
     564            if (in_degree(u, G) > 0) {
    539565                VertexSet incomingAdjacencies;
    540                 incomingAdjacencies.reserve(in_degree(u, H));
    541                 for (auto e : make_iterator_range(in_edges(u, H))) {
    542                     incomingAdjacencies.push_back(source(e, H));
     566                incomingAdjacencies.reserve(in_degree(u, G));
     567                for (auto e : make_iterator_range(in_edges(u, G))) {
     568                    incomingAdjacencies.push_back(source(e, G));
    543569                }
    544570                std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
     
    590616            for (const Vertex u : *Bi) {
    591617                VertexSet Aj;
    592                 Aj.reserve(out_degree(u, H));
    593                 for (auto e : make_iterator_range(out_edges(u, H))) {
    594                     Aj.push_back(target(e, H));
     618                Aj.reserve(out_degree(u, G));
     619                for (auto e : make_iterator_range(out_edges(u, G))) {
     620                    Aj.push_back(target(e, G));
    595621                }
    596622                std::sort(Aj.begin(), Aj.end());
     
    673699            VertexSet & B = std::get<1>(*ci);
    674700            for (auto bi = B.begin(); bi != B.end(); ) {
    675                 if (out_degree(H[*bi], G) == cardinalityA) {
     701                if (out_degree(*bi, G) == cardinalityA) {
    676702                    ++bi;
    677703                } else {
     
    689715
    690716    /** ------------------------------------------------------------------------------------------------------------- *
    691      * @brief addTemporary
     717     * @brief makeVertex
    692718     ** ------------------------------------------------------------------------------------------------------------- */
    693719    Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) {
     
    711737        const auto u = makeVertex(typeId, expr);
    712738        M.emplace(expr, u);
     739        if (LLVM_UNLIKELY(isa<Not>(expr))) {
     740            PabloAST * const negated = cast<Not>(expr)->getExpr();
     741            addEdge(addExpression(negated), u, negated);
     742        }
    713743        return u;
    714744    }
     
    717747     * @brief addStatement
    718748     ** ------------------------------------------------------------------------------------------------------------- */
    719     void addStatement(Statement * const stmt) {
     749    Vertex addStatement(Statement * const stmt) {
    720750        assert (M.count(stmt) == 0);
    721751        const auto typeId = stmt->getClassTypeId();
    722         const auto u = makeVertex(typeId, stmt);
    723         M.emplace(stmt, u);
    724         for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    725             PabloAST * const op = stmt->getOperand(i);
    726             if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
    727                 continue;
    728             }
    729             const auto v = addExpression(op);
    730             add_edge(v, u, op, G);
    731             if (LLVM_UNLIKELY(isa<Not>(op))) {
    732                 PabloAST * const negated = cast<Not>(op)->getExpr();
    733                 add_edge(addExpression(negated), v, negated, G);
    734             }
    735         }
     752        if (LLVM_UNLIKELY(typeId == TypeId::Sel)) {
     753
     754            // expand Sel (C,T,F) statements into (C ∧ T) √ (C ∧ F)
     755
     756            const auto c = addExpression(cast<Sel>(stmt)->getCondition());
     757            const auto t = addExpression(cast<Sel>(stmt)->getTrueExpr());
     758            const auto l = makeVertex(TypeId::And);
     759            addEdge(c, l);
     760            addEdge(t, l);
     761            const auto n = makeVertex(TypeId::Not);
     762            addEdge(c, n);
     763            const auto r = makeVertex(TypeId::And);
     764            const auto f = addExpression(cast<Sel>(stmt)->getFalseExpr());
     765            addEdge(n, r);
     766            addEdge(f, r);
     767            const auto u = makeVertex(TypeId::Or, stmt);
     768            M.emplace(stmt, u);
     769            addEdge(l, u);
     770            addEdge(r, u);
     771
     772            return u;
     773
     774        } else {
     775
     776            const auto u = makeVertex(typeId, stmt);
     777            M.emplace(stmt, u);
     778            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     779                PabloAST * const op = stmt->getOperand(i);
     780                if (LLVM_UNLIKELY(isa<String>(op))) {
     781                    continue;
     782                }
     783                addEdge(addExpression(op), u, op);
     784            }
     785
     786            return u;
     787        }
     788
     789    }
     790
     791    /** ------------------------------------------------------------------------------------------------------------- *
     792     * @brief addBranch
     793     ** ------------------------------------------------------------------------------------------------------------- */
     794    void addBranch(Statement * const br) {
     795        const auto u = addStatement(br);
     796        for (auto escaped : cast<Branch>(br)->getEscaped()) {
     797            addEdge(u, addExpression(escaped), escaped);
     798        }
     799    }
     800
     801
     802    /** ------------------------------------------------------------------------------------------------------------- *
     803     * @brief addEdge
     804     ** ------------------------------------------------------------------------------------------------------------- */
     805    void addEdge(const Vertex u, const Vertex v, PabloAST * const value = nullptr) {
     806        const auto typeId = getType(v);
     807        if (isAssociative(typeId)) {
     808            for (auto e : make_iterator_range(in_edges(u, G))) {
     809                if (LLVM_UNLIKELY(source(e, G) == u)) {
     810                    if (LLVM_LIKELY(isDistributive(typeId))) {
     811                        G[e] = std::max(G[e], value);
     812                    } else {
     813                        remove_edge(e, G);
     814                    }
     815                    return;
     816                }
     817            }
     818        }
     819        boost::add_edge(u, v, value, G);
     820    }
     821
     822    /** ------------------------------------------------------------------------------------------------------------- *
     823     * @brief removeVertex
     824     ** ------------------------------------------------------------------------------------------------------------- */
     825    void removeVertex(const Vertex u) {
     826        clear_vertex(u, G);
     827        setType(u, TypeId::Var);
    736828    }
    737829
     
    775867    }
    776868
     869    static bool isImmutable(const TypeId typeId) {
     870        return (typeId == TypeId::Var || typeId == TypeId::Assign || typeId == TypeId::Extract);
     871    }
     872
    777873    static TypeId oppositeTypeId(const TypeId typeId) {
    778874        assert (isDistributive(typeId));
     
    780876    }
    781877
    782     void add_edge(const Vertex u, const Vertex v, PabloAST * const value, Graph & G) {
    783         G[std::get<0>(boost::add_edge(u, v, G))] = value;
    784     }
    785 
    786878private:
    787879
    788880    Graph G;
    789881    flat_map<pablo::PabloAST *, Vertex> M;
    790 
    791     DistributionGraph H;
    792     flat_map<Vertex, DistributionVertex> D;
     882    VertexSet D;
     883    VertexSet L;
    793884
    794885};
     
    798889 ** ------------------------------------------------------------------------------------------------------------- */
    799890bool DistributivePass::optimize(PabloKernel * const kernel) {
     891    #ifdef NDEBUG
     892    report_fatal_error("DistributivePass is unsupported");
     893    #endif
    800894    PassContainer C;
    801     C.run(kernel->getEntryBlock());
     895    C.run(kernel);
    802896    return true;
    803897}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r5454 r5486  
    2929/** ------------------------------------------------------------------------------------------------------------- *
    3030 * @brief fold
    31  *
    32  * Note: if folding alters this variadic without making any other modification to the AST, it will return null as
    33  * if no change was made.
    34  ** ------------------------------------------------------------------------------------------------------------- */
    35 inline PabloAST * Simplifier::fold(Variadic * var, PabloBlock * const block) {
    36 
    37     assert (var);
    38 
    39     bool negated = false;
    40     if (LLVM_UNLIKELY(isa<Xor>(var))) {
    41         for (unsigned i = 0; i != var->getNumOperands(); ++i) {
    42             if (isa<Not>(var->getOperand(i))) {
    43                 // (A ⊕ ¬B) = (A ⊕ (B ⊕ 1)) = ¬(A ⊕ B)
    44                 var->setOperand(i, cast<Not>(var->getOperand(i))->getOperand(0));
    45                 negated = !negated;
    46             }
    47         }
    48     }
    49 
    50     // Ensure all operands of a reassociatiable function are consistently ordered.
    51     std::sort(var->begin(), var->end());
    52 
    53     // Apply the idempotence law to any And and Or statement and the identity law to any Xor
    54     for (int i = var->getNumOperands() - 1; i > 0; --i) {
    55         if (LLVM_UNLIKELY(equals(var->getOperand(i), var->getOperand(i - 1)))) {
    56             var->removeOperand(i);
    57             if (LLVM_UNLIKELY(isa<Xor>(var))) {
    58                 var->removeOperand(--i);
    59             }
    60         }
    61     }
    62 
    63     // Apply the annihilator and identity laws
    64     for (unsigned i = 0; i != var->getNumOperands(); ) {
    65         if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
    66             if (LLVM_UNLIKELY(isa<And>(var))) {
    67                 return block->createZeroes(var->getType());
    68             }
    69             var->removeOperand(i);
    70             continue;
    71         } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
    72             if (LLVM_UNLIKELY(isa<Or>(var))) {
    73                 return block->createOnes(var->getType());
    74             } else if (LLVM_UNLIKELY(isa<Xor>(var))) {
    75                 negated = !negated;
    76             }
    77             var->removeOperand(i);
    78             continue;
    79         }
    80         ++i;
    81     }
    82 
    83     PabloAST * replacement = nullptr;
    84 
    85     if (LLVM_LIKELY(isa<And>(var) || isa<Or>(var))) {
    86         // Apply an implicit distribution + identity law whenever possible
    87         //    (P ∧ Q) √ (P ∧ ¬Q) = P √ (Q ∧ ¬Q) ⇔ P
    88         TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
    89         for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    90             if (var->getOperand(i)->getClassTypeId() == typeId) {
    91                 Variadic * const Vi = cast<Variadic>(var->getOperand(i));
    92                 // Ensure the i-th operand is sorted incase it was altered after being folded.
    93                 std::sort(Vi->begin(), Vi->end());
    94                 for (unsigned j = 0; j < i; ++j) {
    95                     assert (var->getOperand(i) == Vi);
    96                     if (var->getOperand(j)->getClassTypeId() == typeId) {
    97                         Variadic * const Vj = cast<Variadic>(var->getOperand(j));
    98                         assert (std::is_sorted(Vj->begin(), Vj->end()));
    99                         if (Vi->getNumOperands() == Vj->getNumOperands()) {
    100                             // If vi and vj differ by precisely one operand, say di and dj,
    101                             // and di ⇔ ¬dj, we can apply this rule.
    102                             unsigned vi = 0, vj = 0;
    103                             const unsigned operands = Vi->getNumOperands();
    104                             unsigned di = operands - 1, dj = operands - 1;
    105                             bool differsByOne = true;
    106                             while (vi < operands && vj < operands) {
    107                                 if (Vi->getOperand(vi) < Vj->getOperand(vj)) {
    108                                     if (LLVM_UNLIKELY(di != (operands - 1))) { // <- we want the branch predictor to fail only once
    109                                         differsByOne = false;
    110                                         break;
    111                                     }
    112                                     di = vi++;
    113                                 } else if (Vj->getOperand(vj) < Vi->getOperand(vi)) {
    114                                     if (LLVM_UNLIKELY(dj != (operands - 1))) {
    115                                         differsByOne = false;
    116                                         break;
    117                                     }
    118                                     dj = vj++;
    119                                 } else {
    120                                     ++vi;
    121                                     ++vj;
    122                                 }
    123                             }
    124                             if (LLVM_UNLIKELY(differsByOne)) {
    125                                 assert (di < operands && dj < operands);
    126                                 assert ("Found an equivalent set of operations that was not deduced earlier!" && (!equals(Vi, Vj)));
    127                                 // test if di ⇔ ¬dj
    128                                 bool apply = false;
    129                                 if (isa<Not>(Vi->getOperand(di))) {
    130                                     apply = cast<Not>(Vi->getOperand(di))->getOperand(0) == Vj->getOperand(dj);
    131                                 } else if (isa<Not>(Vj->getOperand(dj))) {
    132                                     apply = cast<Not>(Vj->getOperand(dj))->getOperand(0) == Vi->getOperand(di);
    133                                 }
    134                                 if (LLVM_UNLIKELY(apply)) {
    135                                     // Although we can apply this transformation, we have a potential problem. If P is not a "literal", we
    136                                     // cannot optimize var without creating a new And/Or statement. However, the redundancy elimination
    137                                     // pass will miss this new statement unless we mark "var" as its own replacement. We'll end up checking
    138                                     // "var" again but termination is still guaranteed once none of the new statements can be replaced by
    139                                     // prior statements in the AST.
    140                                     PabloAST * expr = nullptr;
    141                                     if (operands == 2) {
    142                                         expr = Vi->getOperand(1 ^ di);
    143                                         if (LLVM_LIKELY(var->getNumOperands() == 2)) {
    144                                             return expr;
    145                                         }
    146                                     } else { // if (operands > 2) {
    147                                         assert (operands > 2);
    148                                         block->setInsertPoint(var->getPrevNode());
    149                                         if (typeId == TypeId::And) {
    150                                             expr = block->createAnd(var->getType(), operands - 1);
    151                                         } else { // if (typeId == TypeId::Or) {
    152                                             expr = block->createOr(var->getType(), operands - 1);
    153                                         }
    154                                         for (unsigned k = 0; k != di; ++k) {
    155                                             cast<Variadic>(expr)->addOperand(Vi->getOperand(k));
    156                                         }
    157                                         for (unsigned k = di + 1; k < operands; ++k) {
    158                                             cast<Variadic>(expr)->addOperand(Vi->getOperand(k));
    159                                         }
    160                                         replacement = var;
    161                                     }
    162                                     var->removeOperand(i);
    163                                     var->removeOperand(j);
    164                                     bool unique = true;
    165                                     for (unsigned k = 0; k != var->getNumOperands(); ++k) {
    166                                         if (LLVM_UNLIKELY(equals(var->getOperand(k), expr))) {
    167                                             unique = false;
    168                                             break;
    169                                         }
    170                                     }
    171                                     if (LLVM_LIKELY(unique)) {
    172                                         var->addOperand(expr);
    173                                     }
    174                                     i -= 2;
    175                                     break; // out of for j = 0 to i - 1
    176                                 }
    177                             }
    178                         }
    179                     }
    180                 }
    181             }
    182         }
    183 
    184         // Apply the absorption law whenever possible
    185         //   P √ (P ∧ Q) ⇔ P ∧ (P √ Q) ⇔ P
    186         for (unsigned i = 1; i < var->getNumOperands(); ++i) {
    187             PabloAST * const op = var->getOperand(i);
    188             if (op->getClassTypeId() == typeId) {
    189                 Variadic * const vi = cast<Variadic>(op);
    190                 assert (std::is_sorted(vi->begin(), vi->end()));
    191                 for (unsigned j = 0; j < i; ++j) {
    192                     assert (var->getOperand(i) == vi);
    193                     if (var->getOperand(j)->getClassTypeId() == typeId) {
    194                         Variadic * const vj = cast<Variadic>(var->getOperand(j));
    195                         assert (std::is_sorted(vj->begin(), vj->end()));
    196                         if (vi->getNumOperands() < vj->getNumOperands()) {
    197                             if (LLVM_UNLIKELY(std::includes(vi->begin(), vi->end(), vj->begin(), vj->end()))) {
    198                                 var->removeOperand(i--);
    199                                 break;
    200                             }
    201                         } else { // if (vi->getNumOperands() >= vj->getNumOperands()) {
    202                             if (LLVM_UNLIKELY(std::includes(vj->begin(), vj->end(), vi->begin(), vi->end()))) {
    203                                 var->removeOperand(j--);
    204                                 --i;
    205                             }
    206                         }
    207                     }
    208                 }
    209             } else { // treat the operand as a literal
    210                 for (unsigned j = 0; j < var->getNumOperands(); ) {
    211                     if (var->getOperand(j)->getClassTypeId() == typeId) {
    212                         Variadic * const vj = cast<Variadic>(var->getOperand(j));
    213                         assert (std::is_sorted(vj->begin(), vj->end()));
    214                         if (LLVM_UNLIKELY(std::binary_search(vj->begin(), vj->end(), op))) {
    215                             var->removeOperand(j);
    216                             continue;
    217                         }
    218                     }
    219                     ++j;
    220                 }
    221             }
    222         }
    223 
    224         // Apply the complementation law whenever possible.
    225         for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    226             if (isa<Not>(var->getOperand(i))) {
    227                 const PabloAST * const negated = cast<Not>(var->getOperand(i))->getOperand(0);
    228                 for (unsigned j = 0; j != var->getNumOperands(); ++j) {
    229                     if (LLVM_UNLIKELY(var->getOperand(j) == negated)) {
    230                         if (isa<And>(var)) { // (A ∧ ¬A) ∧ B ⇔ 0 for any B
    231                             return block->createZeroes(var->getType());
    232                         } else { // if (isa<Or>(var)) { // (A √ ¬A) √ B ⇔ 1 for any B
    233                             return block->createOnes(var->getType());
    234                         }
    235                     }
    236                 }
    237             }
    238         }
    239 
    240     }
    241 
    242     if (LLVM_UNLIKELY(var->getNumOperands() < 2)) {
    243         if (LLVM_UNLIKELY(var->getNumOperands() == 0)) {
    244             return block->createZeroes(var->getType());
    245         }
    246         replacement = var->getOperand(0);
    247     }
    248     if (LLVM_UNLIKELY(negated)) {
    249         assert (isa<Xor>(var));
    250         block->setInsertPoint(var);
    251         replacement = block->createNot(replacement ? replacement : var);
    252     }
    253     return replacement;
    254 }
    255 
    256 /** ------------------------------------------------------------------------------------------------------------- *
    257  * @brief fold
    258  ** ------------------------------------------------------------------------------------------------------------- */
    259 PabloAST * Simplifier::fold(Statement * stmt, PabloBlock * const block) {
    260     if (isa<Variadic>(stmt)) {
    261         return fold(cast<Variadic>(stmt), block);
    262     } else if (isa<Not>(stmt)) {
     31 ** ------------------------------------------------------------------------------------------------------------- */
     32PabloAST * Simplifier::triviallyFold(Statement * stmt, PabloBlock * const block) {
     33    if (isa<Not>(stmt)) {
    26334        PabloAST * value = stmt->getOperand(0);
    26435        if (LLVM_UNLIKELY(isa<Not>(value))) {
     
    479250            }
    480251
    481             Statement * const prior = stmt->getPrevNode();
    482             PabloAST * const folded = fold(stmt, block);
     252            PabloAST * const folded = triviallyFold(stmt, block);
    483253            if (folded) {
    484                 // If we determine we can fold this statement, go back to the original prior node of this statement.
    485                 // New statements may have been inserted after it.
    486                 stmt->replaceWith(folded, true);
    487                 stmt = LLVM_LIKELY(prior != nullptr) ? prior->getNextNode() : block->front();
    488                 continue;
    489             }
     254                stmt = stmt->replaceWith(folded);
     255                continue;
     256            }
     257
    490258            // By recording which statements have already been seen, we can detect the redundant statements
    491259            // as any having the same type and operands. If so, we can replace its users with the prior statement.
     
    493261            const auto f = expressions.findOrAdd(stmt);
    494262            if (!f.second) {
    495                 stmt = stmt->replaceWith(f.first, true);
     263                stmt = stmt->replaceWith(f.first);
    496264                continue;
    497265            }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r5217 r5486  
    2020    Simplifier() = default;
    2121private:
    22     static PabloAST * fold(Variadic * var, PabloBlock * const block);
    23     static PabloAST * fold(Statement * const stmt, PabloBlock * const block);
     22    static PabloAST * triviallyFold(Statement * const stmt, PabloBlock * const block);
    2423    static void redundancyElimination(PabloBlock * const block, ExpressionTable * et = nullptr, VariableTable * const vt = nullptr);
    2524    static void deadCodeElimination(PabloKernel * const kernel);
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r5371 r5486  
    3434
    3535    using Allocator = SlabAllocator<PabloAST *>;
    36     using UserAllocator = ProxyAllocator<PabloAST *>;
    37     using Users = std::vector<PabloAST *, UserAllocator>;
     36    using Users = std::vector<PabloAST *, ProxyAllocator<PabloAST *>>;
    3837    using user_iterator = Users::iterator;
    3938    using const_user_iterator = Users::const_iterator;
     
    155154    }
    156155    bool addUser(PabloAST * const user);
     156
    157157    bool removeUser(PabloAST * const user);
    158     virtual ~PabloAST() {
    159         mUsers.clear();
    160     }       
     158
     159    virtual ~PabloAST() = default;
     160
    161161private:
    162162    const ClassTypeId       mClassTypeId;
     
    226226        return mParent;
    227227    }
    228     virtual ~Statement() {}
     228    virtual ~Statement() = default;
     229
    229230protected:
    230231
     
    283284};
    284285
     286class CarryProducingStatement : public Statement {
     287public:
     288
     289    static inline bool classof(const PabloAST * e) {
     290        switch (e->getClassTypeId()) {
     291            case PabloAST::ClassTypeId::Advance:
     292            case PabloAST::ClassTypeId::ScanThru:
     293            case PabloAST::ClassTypeId::AdvanceThenScanThru:
     294            case PabloAST::ClassTypeId::ScanTo:
     295            case PabloAST::ClassTypeId::AdvanceThenScanTo:
     296            case PabloAST::ClassTypeId::MatchStar:
     297                return true;
     298            default: return false;
     299        }
     300    }
     301    static inline bool classof(const CarryProducingStatement *) {
     302        return true;
     303    }
     304    static inline bool classof(const void *) {
     305        return false;
     306    }
     307
     308    unsigned getCarryGroup() const {
     309        return mCarryGroup;
     310    }
     311
     312    void setCarryGroup(const unsigned carryGroup) {
     313        mCarryGroup = carryGroup;
     314    }
     315
     316    virtual ~CarryProducingStatement() = default;
     317
     318protected:
     319
     320    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
     321    : Statement(id, type, operands, name, allocator)
     322    , mCarryGroup(0) {
     323
     324    }
     325
     326    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * name, Allocator & allocator)
     327    : Statement(id, type, reserved, name, allocator)
     328    , mCarryGroup(0) {
     329
     330    }
     331
     332    template<typename iterator>
     333    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * name, Allocator & allocator)
     334    : Statement(id, type, begin, end, name, allocator)
     335    , mCarryGroup(0) {
     336
     337    }
     338
     339private:
     340
     341    unsigned mCarryGroup;
     342};
     343
     344
    285345class Variadic : public Statement {
    286346public:
     
    343403        return iterator(mOperand + mOperands);
    344404    }
     405
     406    virtual ~Variadic() = default;
    345407
    346408protected:
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r5440 r5486  
    4848    examineBlock(iBuilder, mKernel->getEntryBlock());
    4949    mCarryManager->initializeCarryData(iBuilder, mKernel);
     50}
     51
     52void PabloCompiler::releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder) {
     53    assert ("PabloCompiler does not have a IDISA iBuilder" && iBuilder);
     54    mCarryManager->releaseCarryData(iBuilder, mKernel);
    5055}
    5156
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.h

    r5440 r5486  
    4242    void compile(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
    4343
     44    void releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
     45
    4446private:
    4547
  • icGREP/icgrep-devel/icgrep/pablo/pablo_kernel.cpp

    r5464 r5486  
    145145    iBuilder->setScalarField("EOFmask", iBuilder->bitblock_mask_from(remainingBytes));
    146146    CreateDoBlockMethodCall(iBuilder);
     147}
     148
     149void PabloKernel::generateFinalizeMethod(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
     150    mPabloCompiler->releaseKernelData(iBuilder);
    147151}
    148152
  • icGREP/icgrep-devel/icgrep/pablo/pablo_kernel.h

    r5454 r5486  
    158158    void generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & iBuilder, llvm::Value * remainingBytes) final;
    159159
     160    void generateFinalizeMethod(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) final;
     161
    160162private:
    161163
  • icGREP/icgrep-devel/icgrep/pablo/pe_advance.h

    r5454 r5486  
    1313namespace pablo {
    1414
    15 class Advance final : public Statement {
     15class Advance final : public CarryProducingStatement {
    1616    friend class PabloBlock;
    1717public:
     
    3232protected:
    3333    Advance(PabloAST * expr, PabloAST * shiftAmount, const String * name, Allocator & allocator)
    34     : Statement(ClassTypeId::Advance, expr->getType(), {expr, shiftAmount}, name, allocator) {
     34    : CarryProducingStatement(ClassTypeId::Advance, expr->getType(), {expr, shiftAmount}, name, allocator) {
    3535        assert(llvm::isa<Integer>(shiftAmount));
    3636    }
  • icGREP/icgrep-devel/icgrep/pablo/pe_matchstar.h

    r5454 r5486  
    1212namespace pablo {
    1313
    14 class MatchStar final : public Statement {
     14class MatchStar final : public CarryProducingStatement {
    1515    friend class PabloBlock;
    1616public:
     
    3030protected:
    3131    MatchStar(PabloAST * marker,  PabloAST * cc, const String * name, Allocator & allocator)
    32     : Statement(ClassTypeId::MatchStar, marker->getType(), {marker, cc}, name, allocator) {
     32    : CarryProducingStatement(ClassTypeId::MatchStar, marker->getType(), {marker, cc}, name, allocator) {
    3333    }
    3434};
  • icGREP/icgrep-devel/icgrep/pablo/pe_scanthru.h

    r5329 r5486  
    1212namespace pablo {
    1313
    14 class ScanThru : public Statement {
     14class ScanThru : public CarryProducingStatement {
    1515    friend class PabloBlock;
    1616public:
     
    3131protected:
    3232    ScanThru(PabloAST * from, PabloAST * thru, const String * name, Allocator & allocator)
    33     : Statement(ClassTypeId::ScanThru, from->getType(), {from, thru}, name, allocator) {
     33    : CarryProducingStatement(ClassTypeId::ScanThru, from->getType(), {from, thru}, name, allocator) {
    3434
    3535    }
    3636};
    3737
    38 class ScanTo : public Statement {
     38class ScanTo : public CarryProducingStatement {
    3939    friend class PabloBlock;
    4040public:
     
    5555protected:
    5656    ScanTo(PabloAST * from, PabloAST * to, const String * name, Allocator & allocator)
    57     : Statement(ClassTypeId::ScanTo, from->getType(), {from, to}, name, allocator) {
     57    : CarryProducingStatement(ClassTypeId::ScanTo, from->getType(), {from, to}, name, allocator) {
    5858
    5959    }
    6060};
    6161
    62 class AdvanceThenScanThru : public Statement {
     62class AdvanceThenScanThru : public CarryProducingStatement {
    6363    friend class PabloBlock;
    6464public:
     
    7979protected:
    8080    AdvanceThenScanThru(PabloAST * from, PabloAST * thru, const String * name, Allocator & allocator)
    81     : Statement(ClassTypeId::AdvanceThenScanThru, from->getType(), {from, thru}, name, allocator) {
     81    : CarryProducingStatement(ClassTypeId::AdvanceThenScanThru, from->getType(), {from, thru}, name, allocator) {
    8282
    8383    }
    8484};
    8585
    86 class AdvanceThenScanTo : public Statement {
     86class AdvanceThenScanTo : public CarryProducingStatement {
    8787    friend class PabloBlock;
    8888public:
     
    103103protected:
    104104    AdvanceThenScanTo(PabloAST * from, PabloAST * to, const String * name, Allocator & allocator)
    105     : Statement(ClassTypeId::AdvanceThenScanTo, from->getType(), {from, to}, name, allocator) {
     105    : CarryProducingStatement(ClassTypeId::AdvanceThenScanTo, from->getType(), {from, to}, name, allocator) {
    106106
    107107    }
Note: See TracChangeset for help on using the changeset viewer.