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

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

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
2 added
16 edited

Legend:

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

    r4919 r4959  
    218218 * @brief verifyProgramStructure
    219219 ** ------------------------------------------------------------------------------------------------------------- */
    220 void verifyProgramStructure(const PabloBlock * block) {
     220void verifyProgramStructure(const PabloBlock * block, unsigned & nestingDepth) {
    221221    const Statement * prev = nullptr;
    222222    for (const Statement * stmt : *block) {
     
    279279                }
    280280            }
    281             verifyProgramStructure(nested);
    282         }
    283     }
     281            ++nestingDepth;
     282            verifyProgramStructure(nested, nestingDepth);
     283            --nestingDepth;
     284        }
     285    }   
    284286}
    285287
    286288inline void verifyProgramStructure(const PabloFunction & function) {
    287     verifyProgramStructure(function.getEntryBlock());
     289    unsigned nestingDepth = 0;
     290    verifyProgramStructure(function.getEntryBlock(), nestingDepth);
     291    if (LLVM_UNLIKELY(nestingDepth != 0)) {
     292        // This error isn't actually possible to occur with the current AST structure but that could change
     293        // in the future. Leaving this test in for a reminder to check for it.
     294        throw std::runtime_error("PabloVerifier: unbalanced If or While nesting depth.");
     295    }
    288296}
    289297
  • icGREP/icgrep-devel/icgrep/pablo/builder.cpp

    r4722 r4959  
    8282}
    8383
     84PabloAST * PabloBuilder::createLookahead(PabloAST * expr, PabloAST * shiftAmount) {
     85    MAKE_BINARY(createLookahead, PabloAST::ClassTypeId::Lookahead, expr, shiftAmount);
     86    return result;
     87}
     88
     89PabloAST * PabloBuilder::createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix) {
     90    MAKE_BINARY(createLookahead, PabloAST::ClassTypeId::Lookahead, expr, shiftAmount, prefix);
     91    return result;
     92}
     93
    8494PabloAST * PabloBuilder::createMod64Advance(PabloAST * expr, PabloAST * shiftAmount) {
    8595    MAKE_BINARY(createMod64Advance, PabloAST::ClassTypeId::Mod64Advance, expr, shiftAmount);
     
    92102}
    93103
     104PabloAST * PabloBuilder::createMod64Lookahead(PabloAST * expr, PabloAST * shiftAmount) {
     105    MAKE_BINARY(createMod64Lookahead, PabloAST::ClassTypeId::Mod64Lookahead, expr, shiftAmount);
     106    return result;
     107}
     108
     109PabloAST * PabloBuilder::createMod64Lookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix) {
     110    MAKE_BINARY(createMod64Lookahead, PabloAST::ClassTypeId::Mod64Lookahead, expr, shiftAmount, prefix);
     111    return result;
     112}
     113
    94114PabloAST * PabloBuilder::createNot(PabloAST * expr) {
    95115    MAKE_UNARY(createNot, PabloAST::ClassTypeId::Not, expr);
  • icGREP/icgrep-devel/icgrep/pablo/builder.hpp

    r4870 r4959  
    8686
    8787    PabloAST * createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
     88
     89    inline PabloAST * createLookahead(PabloAST * expr, const Integer::Type shiftAmount) {
     90        if (shiftAmount == 0) {
     91            return expr;
     92        }
     93        return createLookahead(expr, mPb->getInteger(shiftAmount));
     94    }
     95
     96    PabloAST * createLookahead(PabloAST * expr, PabloAST * shiftAmount);
     97
     98    inline PabloAST * createLookahead(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix) {
     99        if (shiftAmount == 0) {
     100            return expr;
     101        }
     102        return createLookahead(expr, mPb->getInteger(shiftAmount), prefix);
     103    }
     104
     105    PabloAST * createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
    88106
    89107    inline Next * createNext(Assign * assign, PabloAST * expr) {
     
    134152    }
    135153
     154    PabloAST * createMod64Advance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
     155
    136156    inline PabloAST * createMod64Advance(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix) {
    137157        if (shiftAmount == 0) {
     
    141161    }
    142162
    143     PabloAST * createMod64Advance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
     163    PabloAST * createMod64Lookahead(PabloAST * expr, PabloAST * shiftAmount);
     164
     165    inline PabloAST * createMod64Lookahead(PabloAST * expr, const Integer::Type shiftAmount) {
     166        if (shiftAmount == 0) {
     167            return expr;
     168        }
     169        return createMod64Lookahead(expr, mPb->getInteger(shiftAmount));
     170    }
     171
     172    PabloAST * createMod64Lookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
     173
     174    inline PabloAST * createMod64Lookahead(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix) {
     175        if (shiftAmount == 0) {
     176            return expr;
     177        }
     178        return createMod64Lookahead(expr, mPb->getInteger(shiftAmount), prefix);
     179    }
    144180
    145181    PabloAST * createMod64MatchStar(PabloAST * marker, PabloAST * charclass);
  • icGREP/icgrep-devel/icgrep/pablo/carry_data.cpp

    r4942 r4959  
    1515    for (Statement * stmt : *theScope) {
    1616        if (Advance * adv = dyn_cast<Advance>(stmt)) {
    17             unsigned shift_amount = adv->getAdvanceAmount();
     17            unsigned shift_amount = adv->getAmount();
    1818            if (shift_amount == 1) {
    19                 adv->setLocalAdvanceIndex(unitAdvance.entries);
     19                adv->setLocalIndex(unitAdvance.entries);
    2020                unitAdvance.entries++;               
    2121            }
     
    2929                        shortAdvance.allocatedBits = alignCeiling(shortAdvance.allocatedBits, mPackSize);
    3030                    }
    31                     adv->setLocalAdvanceIndex(shortAdvance.allocatedBits);
     31                    adv->setLocalIndex(shortAdvance.allocatedBits);
    3232                }
    3333                else {
    34                     adv->setLocalAdvanceIndex(shortAdvance.entries);
     34                    adv->setLocalIndex(shortAdvance.entries);
    3535                }
    3636                shortAdvance.entries++;
     
    3838            }
    3939            else {
    40                 adv->setLocalAdvanceIndex(longAdvance.allocatedBitBlocks);
     40                adv->setLocalIndex(longAdvance.allocatedBitBlocks);
    4141                longAdvance.entries++;
    4242                longAdvance.allocatedBitBlocks += longAdvanceBufferSize(shift_amount);
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp

    r4954 r4959  
    2020
    2121/** ------------------------------------------------------------------------------------------------------------- *
    22  * @brief doScopeCount
    23  ** ------------------------------------------------------------------------------------------------------------- */
    24 static unsigned doScopeCount(const PabloBlock * const pb) {
    25     unsigned count = 1;
    26     for (const Statement * stmt : *pb) {
    27         if (LLVM_UNLIKELY(isa<If>(stmt))) {
    28             count += doScopeCount(cast<If>(stmt)->getBody());
    29         } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    30             count += doScopeCount(cast<While>(stmt)->getBody());
    31         }
    32     }
    33     return count;
    34 }
    35 
    36 /** ------------------------------------------------------------------------------------------------------------- *
    3722 * @brief initialize
    3823 ** ------------------------------------------------------------------------------------------------------------- */
    39 void CarryManager::initialize(PabloBlock * pb, KernelBuilder * kBuilder) {
    40     mRootScope = pb;
    41     mCarryInfoVector.resize(doScopeCount(pb));
     24void CarryManager::initialize(PabloFunction * const function, KernelBuilder * const kBuilder) {
     25    mRootScope = function->getEntryBlock();
     26    mCarryInfoVector.resize(mRootScope->enumerateScopes(0) + 1);
    4227    mCarryPackType = mBitBlockType;
    43 
    44     const unsigned totalCarryDataSize = enumerate(pb, 0, 0);
    45 
     28    const unsigned totalCarryDataSize = std::max<unsigned>(enumerate(mRootScope, 0, 0), 1);
    4629    mCarryPackPtr.resize(totalCarryDataSize, nullptr);
    4730    mCarryInPack.resize(totalCarryDataSize, nullptr);
    4831    mCarryOutPack.resize(totalCarryDataSize, nullptr);
    49 
    5032    mTotalCarryDataBitBlocks = totalCarryDataSize;
    51    
    5233    ArrayType* cdArrayTy = ArrayType::get(mBitBlockType, mTotalCarryDataBitBlocks);
    53     mCdArrayIdx = kBuilder->extendKernelInternalStateType(cdArrayTy);
    54    
     34    mCdArrayIdx = kBuilder->addInternalStateType(cdArrayTy);
    5535    if (mPabloCountCount > 0) {
    5636        ArrayType* pcArrayTy = ArrayType::get(iBuilder->getIntNTy(64), mPabloCountCount);
    57         mPcArrayIdx = kBuilder->extendKernelInternalStateType(pcArrayTy);
    58     }
    59  
     37        mPcArrayIdx = kBuilder->addInternalStateType(pcArrayTy);
     38    }
    6039    mCurrentScope = mRootScope;
    6140    mCurrentFrameIndex = 0;
     
    6443}
    6544
     45/** ------------------------------------------------------------------------------------------------------------- *
     46 * @brief initialize_setPtrs
     47 ** ------------------------------------------------------------------------------------------------------------- */
    6648void CarryManager::initialize_setPtrs(KernelBuilder * kBuilder) {
    67 
    68     Value * kernelStuctParam = kBuilder->getKernelStructParam();
    69     Value * cdArrayPtr = kBuilder->getKernelInternalStatePtr(kernelStuctParam, mCdArrayIdx);
    70  
     49    Value * cdArrayPtr = kBuilder->getInternalState(mCdArrayIdx);
    7150    mCarryPackBasePtr = iBuilder->CreateBitCast(cdArrayPtr, PointerType::get(mCarryPackType, 0));
    72     mCarryBitBlockPtr = iBuilder->CreateBitCast(cdArrayPtr, PointerType::get(mBitBlockType, 0));   
    73    
     51    mCarryBitBlockPtr = iBuilder->CreateBitCast(cdArrayPtr, PointerType::get(mBitBlockType, 0));
    7452    if (mPabloCountCount > 0) {
    75         Value * pcArrayPtr = kBuilder->getKernelInternalStatePtr(kernelStuctParam, mPcArrayIdx);
     53        Value * pcArrayPtr = kBuilder->getInternalState(mPcArrayIdx);
    7654        mPopcountBasePtr = iBuilder->CreateBitCast(pcArrayPtr, Type::getInt64PtrTy(iBuilder->getContext()));
    7755    }
    78  
    79     mBlockNo = iBuilder->CreateUDiv(kBuilder->getKernelInternalState(kernelStuctParam, mFilePosIdx), iBuilder->getInt64(mBitBlockWidth));
     56    setBlockNo(kBuilder);
    8057    mCurrentScope = mRootScope;
    8158    mCurrentFrameIndex = 0;
     
    8461}
    8562
    86 void CarryManager::set_BlockNo(KernelBuilder * kBuilder){
    87     Value * kernelStuctParam = kBuilder->getKernelStructParam();
    88     mBlockNo = iBuilder->CreateUDiv(kBuilder->getKernelInternalState(kernelStuctParam, mFilePosIdx), iBuilder->getInt64(mBitBlockWidth));
     63/** ------------------------------------------------------------------------------------------------------------- *
     64 * @brief setBlockNo
     65 ** ------------------------------------------------------------------------------------------------------------- */
     66void CarryManager::setBlockNo(KernelBuilder * kBuilder) {
     67    mBlockNo = iBuilder->CreateUDiv(iBuilder->CreateBlockAlignedLoad(kBuilder->getInternalState(mFilePosIdx)), iBuilder->getInt64(mBitBlockWidth));
    8968}
    9069
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.h

    r4941 r4959  
    4848    , mCarryBitBlockPtr(nullptr)
    4949    , mPopcountBasePtr(nullptr)
    50     , mBlockNoPtr(nullptr)
    5150    , mBlockNo(nullptr)
    5251    , mPabloCountCount(0)
     
    6059    ~CarryManager();
    6160   
    62     void initialize(PabloBlock * blk, KernelBuilder * kBuilder);
     61    void initialize(PabloFunction * const function, KernelBuilder * const kBuilder);
    6362
    64     void initialize_setPtrs(KernelBuilder * kBuilder);
     63    void initialize_setPtrs(KernelBuilder * const kBuilder);
    6564
    66     void set_BlockNo(KernelBuilder * kBuilder);
     65    void setBlockNo(KernelBuilder * kBuilder);
     66    Value * getBlockNo() const;
    6767   
    6868    unsigned enumerate(PabloBlock * blk, unsigned ifDepth, unsigned whileDepth);
    69        
    70     Value * getBlockNoPtr() const;
    71    
     69         
    7270    /* Entering and leaving scopes. */
    7371   
     
    145143    Value * mCarryBitBlockPtr;
    146144    Value * mPopcountBasePtr;
    147     Value * mBlockNoPtr;
    148145    Value * mBlockNo;
    149146    unsigned mPabloCountCount; // Number of Pablo "Count" operations
     
    166163}
    167164
    168 inline Value * CarryManager::getBlockNoPtr() const {
    169     return mBlockNoPtr;
     165inline Value * CarryManager::getBlockNo() const {
     166    return mBlockNo;
    170167}
    171168
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r4896 r4959  
    4444/// UNARY CREATE FUNCTIONS
    4545
    46 Assign * PabloBlock::createAssign(const std::string && prefix, PabloAST * expr)  {
     46Assign * PabloBlock::createAssign(const std::string && prefix, PabloAST * const expr)  {
     47    assert ("Assign expression cannot be null!" && expr);
    4748    return insertAtInsertionPoint(new Assign(expr, makeName(prefix, false)));
    4849}
     
    7273    if (isa<Zeroes>(expr) || shiftAmount == 0) {
    7374        return renameNonNamedNode(expr, std::move(prefix));
    74     }   
     75    }
    7576    return insertAtInsertionPoint(new Advance(expr, getInteger(shiftAmount), makeName(prefix, false)));
     77}
     78
     79PabloAST * PabloBlock::createLookahead(PabloAST * expr, PabloAST * shiftAmount) {
     80    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
     81        return expr;
     82    }
     83    return insertAtInsertionPoint(new Lookahead(expr, shiftAmount, makeName("lookahead")));
     84}
     85
     86PabloAST * PabloBlock::createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix) {
     87    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
     88        return expr;
     89    }
     90    return insertAtInsertionPoint(new Lookahead(expr, shiftAmount, makeName(prefix, false)));
     91}
     92
     93PabloAST * PabloBlock::createLookahead(PabloAST * expr, const Integer::Type shiftAmount) {
     94    if (isa<Zeroes>(expr) || shiftAmount == 0) {
     95        return expr;
     96    }
     97    return insertAtInsertionPoint(new Lookahead(expr, getInteger(shiftAmount), makeName("lookahead")));
     98}
     99
     100PabloAST * PabloBlock::createLookahead(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix) {
     101    if (isa<Zeroes>(expr) || shiftAmount == 0) {
     102        return renameNonNamedNode(expr, std::move(prefix));
     103    }
     104    return insertAtInsertionPoint(new Lookahead(expr, getInteger(shiftAmount), makeName(prefix, false)));
    76105}
    77106
     
    141170    }   
    142171    return insertAtInsertionPoint(new Mod64Advance(expr, getInteger(shiftAmount), makeName(prefix, false)));
     172}
     173
     174PabloAST * PabloBlock::createMod64Lookahead(PabloAST * expr, PabloAST * shiftAmount) {
     175    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
     176        return expr;
     177    }
     178    return insertAtInsertionPoint(new Mod64Lookahead(expr, shiftAmount, makeName("advance")));
     179}
     180
     181PabloAST * PabloBlock::createMod64Lookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix) {
     182    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
     183        return expr;
     184    }
     185    return insertAtInsertionPoint(new Mod64Lookahead(expr, shiftAmount, makeName(prefix, false)));
     186}
     187
     188PabloAST * PabloBlock::createMod64Lookahead(PabloAST * expr, const Integer::Type shiftAmount) {
     189    if (isa<Zeroes>(expr) || shiftAmount == 0) {
     190        return expr;
     191    }
     192    return insertAtInsertionPoint(new Mod64Lookahead(expr, getInteger(shiftAmount), makeName("advance")));
     193}
     194
     195PabloAST * PabloBlock::createMod64Lookahead(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix) {
     196    if (isa<Zeroes>(expr) || shiftAmount == 0) {
     197        return renameNonNamedNode(expr, std::move(prefix));
     198    }
     199    return insertAtInsertionPoint(new Mod64Lookahead(expr, getInteger(shiftAmount), makeName(prefix, false)));
    143200}
    144201
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4927 r4959  
    1111#include <pablo/symbol_generator.h>
    1212#include <pablo/pe_advance.h>
     13#include <pablo/pe_lookahead.h>
    1314#include <pablo/pe_and.h>
    1415#include <pablo/pe_call.h>
     
    7172    PabloAST * createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
    7273
     74    PabloAST * createLookahead(PabloAST * expr, const Integer::Type shiftAmount);
     75
     76    PabloAST * createLookahead(PabloAST * expr, PabloAST * shiftAmount);
     77
     78    PabloAST * createLookahead(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix);
     79
     80    PabloAST * createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
     81
    7382    static inline Zeroes * createZeroes() {
    7483        return &mZeroes;
     
    93102    }
    94103
    95     Assign * createAssign(const std::string && prefix, PabloAST * expr);
     104    Assign * createAssign(const std::string && prefix, PabloAST * const expr);
    96105
    97106    inline Var * createVar(const std::string name) {
     
    192201
    193202    PabloAST * createMod64Advance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
     203
     204    PabloAST * createMod64Lookahead(PabloAST * expr, const Integer::Type shiftAmount);
     205
     206    PabloAST * createMod64Lookahead(PabloAST * expr, PabloAST * shiftAmount);
     207
     208    PabloAST * createMod64Lookahead(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix);
     209
     210    PabloAST * createMod64Lookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
    194211
    195212    PabloAST * createMod64MatchStar(PabloAST * marker, PabloAST * charclass);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4942 r4959  
    166166bool MultiplexingPass::optimize(PabloFunction & function, const bool independent) {
    167167
     168    if (LLVM_UNLIKELY(Samples < 1)) {
     169        return false;
     170    }
     171
     172
    168173    LOG("Seed:                    " << Seed);
    169174
     
    395400        for (unsigned j = 0; j < i; ++j) {
    396401            if (G(i, j)) {
    397                 add_edge(j, i, mConstraintGraph);
     402                add_edge(j, i, true, mConstraintGraph);
    398403            }
    399404        }
    400405        for (unsigned j = i + 1; j < advances; ++j) {
    401406            if (G(i, j)) {
    402                 add_edge(j, i, mConstraintGraph);
     407                add_edge(j, i, true, mConstraintGraph);
    403408            }
    404409        }
     
    607612
    608613    BDD Ak = bdd_ithvar(mVariables++);
    609     const BDD Nk = bdd_addref(bdd_not(Ak));
     614    const BDD Nk = bdd_addref(bdd_not(Ak));   
    610615    for (unsigned i = 0; i != k; ++i) {
    611616        if (unconstrained[i]) {
     
    627632            }
    628633        }
    629         add_edge(i, k, mConstraintGraph);
     634        add_edge(i, k, false, mConstraintGraph);
    630635    }
    631636    // To minimize the number of BDD computations, we store the negated variable instead of negating it each time.
     
    639644inline bool MultiplexingPass::independent(const ConstraintVertex i, const ConstraintVertex j) const {
    640645    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
    641     return (mConstraintGraph.get_edge(i, j) == 0);
     646    return mConstraintGraph.get_edge(i, j).first == false;
    642647}
    643648
     
    719724    mCandidateGraph = CandidateGraph(num_vertices(mConstraintGraph));
    720725
    721     for (unsigned iteration = 0; iteration < Samples; ++iteration) {
     726    for (unsigned r = Samples; r; --r) {
    722727
    723728        // Push all source nodes into the (initial) independent set S
     
    768773    }
    769774
     775    #ifdef PRINT_DEBUG_OUTPUT
     776    const auto n = num_vertices(mConstraintGraph);
     777    const auto m = num_vertices(mCandidateGraph);
     778    unsigned sets = 0;
     779    for (auto i = n; i < m; ++i) {
     780        if (degree(i, mCandidateGraph) > 0) {
     781            ++sets;
     782        }
     783    }
     784    LOG("Unique Candidate Sets:    " << (sets));
     785    #endif
     786
    770787    return num_vertices(mCandidateGraph) > num_vertices(mConstraintGraph);
    771788}
     
    912929    const size_t n = num_vertices(mCandidateGraph) - m;
    913930
    914     degree_t remaining[n];
    915     vertex_t chosen_set[m];
    916 
    917     for (unsigned i = 0; i != n; ++i) {
    918         remaining[i] = degree(i + m, mCandidateGraph);
    919     }
    920     for (unsigned i = 0; i != m; ++i) {
    921         chosen_set[i] = 0;
    922     }
     931    std::vector<bool> chosen(n, false);
    923932
    924933    for (;;) {
    925934
    926935        // Choose the set with the greatest number of vertices not already included in some other set.
    927         vertex_t k = 0;
     936        vertex_t u = 0;
    928937        degree_t w = 0;
    929938        for (vertex_t i = 0; i != n; ++i) {
    930             degree_t r = remaining[i];
    931             if (r > 2) { // if this set has at least 3 elements.
     939            if (chosen[i]) continue;
     940            const auto t = i + m;
     941            degree_t r = degree(t, mCandidateGraph);
     942            if (LLVM_LIKELY(r >= 3)) { // if this set has at least 3 elements.
    932943                r *= r;
    933944                AdjIterator begin, end;
    934                 std::tie(begin, end) = adjacent_vertices(i + m, mCandidateGraph);
     945                std::tie(begin, end) = adjacent_vertices(t, mCandidateGraph);
    935946                for (auto ei = begin; ei != end; ++ei) {
    936947                    for (auto ej = ei; ++ej != end; ) {
     
    941952                }
    942953                if (w < r) {
    943                     k = i;
     954                    u = t;
    944955                    w = r;
    945956                }
     957            } else if (r) {
     958                clear_vertex(t, mCandidateGraph);
    946959            }
    947960        }
    948961
    949962        // Multiplexing requires 3 or more elements; if no set contains at least 3, abort.
    950         if (w == 0) {
     963        if (LLVM_UNLIKELY(w == 0)) {
    951964            break;
    952965        }
    953966
    954         for (const auto u : make_iterator_range(adjacent_vertices(k + m, mCandidateGraph))) {
    955             if (chosen_set[u] == 0) {
    956                 chosen_set[u] = (k + m);
    957                 for (const auto v : make_iterator_range(adjacent_vertices(u, mCandidateGraph))) {
    958                     assert (v >= m);
    959                     remaining[v - m]--;
    960                 }
    961             }
    962         }
    963 
    964         assert (remaining[k] == 0);
     967        chosen[u - m] = true;
    965968
    966969        // If this contains 2^n elements for any n, discard the member that is most likely to be added
    967970        // to some future set.
    968         if (LLVM_UNLIKELY(is_power_of_2(w))) {
    969             vertex_t j = 0;
     971        if (LLVM_UNLIKELY(is_power_of_2(degree(u, mCandidateGraph)))) {
     972            vertex_t x = 0;
    970973            degree_t w = 0;
    971             for (vertex_t i = 0; i != m; ++i) {
    972                 if (chosen_set[i] == (k + m)) {
    973                     degree_t r = 1;
    974                     for (const auto u : make_iterator_range(adjacent_vertices(i, mCandidateGraph))) {
    975                         // strongly prefer adding weight to unvisited sets that have more remaining vertices
    976                         r += std::pow(remaining[u - m], 2);
    977                     }
    978                     if (w < r) {
    979                         j = i;
    980                         w = r;
    981                     }
    982                 }
    983             }
    984             assert (w > 0);
    985             chosen_set[j] = 0;
    986             for (const auto u : make_iterator_range(adjacent_vertices(j, mCandidateGraph))) {
    987                 assert (u >= m);
    988                 remaining[u - m]++;
    989             }
    990         }
    991 
    992         // If Samples > 1 then our candidate sets were generated by more than one traversal through the constraint graph.
    993         // Sets generated by differing traversals may generate a cycle in the AST if multiplex even when they are not
    994         // multiplexed together. For example,
    995 
    996         // Assume we're multiplexing set {A,B,C} and {D,E,F} and that no constraint exists between any nodes in
    997         // either set. If A is dependent on D and E is dependent on B, multiplexing both sets would result in a cycle
    998         // in the AST. To fix this, we'd have to remove A, D, B or E.
    999 
    1000         // This cannot occur with only one traversal (or between sets generated by the same traversal) because of the
    1001         // DAG traversal strategy used in "generateCandidateSets".
    1002 
    1003 
    1004     }
    1005 
    1006     for (unsigned i = 0; i != m; ++i) {
    1007         AdjIterator ei, ei_end;
    1008         std::tie(ei, ei_end) = adjacent_vertices(i, mCandidateGraph);
    1009         for (auto next = ei; ei != ei_end; ei = next) {
    1010             ++next;
    1011             if (*ei != chosen_set[i]) {
    1012                 remove_edge(i, *ei, mCandidateGraph);
    1013             }
     974            for (const auto v : make_iterator_range(adjacent_vertices(u, mCandidateGraph))) {
     975                if (degree(v, mCandidateGraph) > w) {
     976                    x = v;
     977                    w = degree(v, mCandidateGraph);
     978                }
     979            }
     980            remove_edge(u, x, mCandidateGraph);
     981        }
     982
     983        AdjIterator begin, end;
     984        std::tie(begin, end) = adjacent_vertices(u, mCandidateGraph);
     985        for (auto vi = begin; vi != end; ) {
     986            const auto v = *vi++;
     987            clear_vertex(v, mCandidateGraph);
     988            add_edge(v, u, mCandidateGraph);
     989        }
     990
     991        if (Samples > 1) {
     992            removePotentialCycles(u);
    1014993        }
    1015994    }
     
    10601039
    10611040
     1041}
     1042
     1043/** ------------------------------------------------------------------------------------------------------------- *
     1044 * @brief removePotentialCycles
     1045 *
     1046 * If Samples > 1, our candidate sets were generated by more than one traversal through the constraint DAG.
     1047 * Multiplexing disjoint sets generated by differing traversals can induce a cycle in the AST. For example,
     1048 * suppose sets {A,B} and {C,D} and A is dependent on C and D on B; multiplexing both will result in a cycle.
     1049 *
     1050 * Eliminating all potential cycles will likely lead to the removal of many candidate sets. Instead we "fix"
     1051 * the candidate sets after the selection of a particular candidate set.
     1052 ** ------------------------------------------------------------------------------------------------------------- */
     1053void MultiplexingPass::removePotentialCycles(const CandidateGraph::vertex_descriptor i) {
     1054
     1055    using AdjIterator = graph_traits<CandidateGraph>::adjacency_iterator;
     1056
     1057    const auto m = num_vertices(mConstraintGraph);
     1058    const auto n = num_vertices(mCandidateGraph);
     1059
     1060    // Suppose we construct a graph G that indicates whether selecting candidate set V will induce a cycle, given
     1061    // that we've already chosen candidate set U. This can occur here only because some elements of V are dependent
     1062    // on U and vice versa.
     1063
     1064    // We want the minimal minimum weight feedback arc set of G; however, we also know any edge will either have
     1065    //
     1066
     1067    for (auto j = m; j < n; ++j) {
     1068        if (LLVM_UNLIKELY(i == j)) continue;
     1069        AdjIterator begin, end;
     1070        std::tie(begin, end) = adjacent_vertices(j, mCandidateGraph);
     1071        for (auto ui = begin; ui != end; )  {
     1072            const auto u = *ui++;
     1073            unsigned outgoing = 0;
     1074            unsigned incoming = 0;
     1075            for (auto v : make_iterator_range(adjacent_vertices(i, mCandidateGraph)))  {
     1076                if (dependent(u, v)) {
     1077                    ++outgoing;
     1078                } else if (dependent(v, u)) {
     1079                    ++incoming;
     1080                }
     1081            }
     1082            if (LLVM_UNLIKELY(outgoing > 0 && incoming > 0)) {
     1083                remove_edge(j, u, mCandidateGraph);
     1084            }
     1085        }
     1086    }
     1087}
     1088
     1089/** ------------------------------------------------------------------------------------------------------------- *
     1090 * @brief dependent
     1091 ** ------------------------------------------------------------------------------------------------------------- */
     1092inline bool MultiplexingPass::dependent(const ConstraintVertex i, const ConstraintVertex j) const {
     1093    const auto e = mConstraintGraph.get_edge(i, j);
     1094    return (e.second && e.first);
    10621095}
    10631096
     
    12671300                    work = 2;
    12681301                    break;
    1269 //                case TypeId::Not:
     1302                case TypeId::Not:
    12701303                case TypeId::Assign:
    12711304                case TypeId::Next:
     
    13661399            bool ready = true;
    13671400            const auto v = target(ei, G);
     1401            assert (rank[v] != 0);
    13681402            for (auto ej : make_iterator_range(in_edges(v, G))) {
    13691403                if (rank[source(ej, G)] != 0) {
     
    13731407            }
    13741408            if (ready) {
    1375                 assert (rank[v] != 0);
    13761409                readySet.insert(std::lower_bound(readySet.begin(), readySet.end(), v, by_nonincreasing_rank), v);
    13771410                assert (std::is_sorted(readySet.cbegin(), readySet.cend(), by_nonincreasing_rank));
     
    16061639
    16071640    #ifndef NDEBUG
    1608     std::vector<typename Graph::vertex_descriptor> nothing;
     1641    std::vector<Vertex> nothing;
    16091642    topological_sort(G, std::back_inserter(nothing));
    16101643    #endif
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4937 r4959  
    2525    using CharacterizationMap = llvm::DenseMap<const PabloAST *, BDD>;
    2626
    27     using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
     27    using ConstraintGraph = boost::adjacency_matrix<boost::directedS, boost::no_property, bool>;
    2828    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
    2929    using Constraints = std::vector<ConstraintVertex>;
     
    4242
    4343    using AdvanceVector = std::vector<Advance *>;
    44     using AdvanceDepth = std::vector<int>;
     44    using AdvanceRank = std::vector<int>;
    4545    using AdvanceVariable = std::vector<BDD>;
    4646
     
    7878    void selectMultiplexSetsWorkingSet();
    7979
     80    void removePotentialCycles(const CandidateGraph::vertex_descriptor u);
     81    bool dependent(const ConstraintVertex i, const ConstraintVertex j) const;
     82
    8083    void eliminateSubsetConstraints();
    8184    void doTransitiveReductionOfSubsetGraph();
     
    109112    ConstraintGraph             mConstraintGraph;   
    110113    AdvanceVector               mAdvance;
    111     AdvanceDepth                mAdvanceRank;
     114    AdvanceRank                 mAdvanceRank;
    112115    AdvanceVariable             mAdvanceNegatedVariable;
    113116    SubsetGraph                 mSubsetGraph;
    114117    CliqueGraph                 mUsageGraph;
    115     CandidateGraph           mCandidateGraph;
     118    CandidateGraph              mCandidateGraph;
    116119};
    117120
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4937 r4959  
    525525
    526526/** ------------------------------------------------------------------------------------------------------------- *
     527 * @brief unused
     528 ** ------------------------------------------------------------------------------------------------------------- */
     529inline static bool unused(const Statement * const stmt) {
     530    if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
     531        // TODO: prototypes ought to state whether they have side effects.
     532        if (LLVM_UNLIKELY(isa<Call>(stmt) && cast<Call>(stmt)->getPrototype()->getNumOfResults() == 0)) {
     533            return false;
     534        }
     535        return true;
     536    }
     537    return false;
     538}
     539
     540/** ------------------------------------------------------------------------------------------------------------- *
    527541 * @brief deadCodeElimination
    528542 ** ------------------------------------------------------------------------------------------------------------- */
     
    530544    Statement * stmt = block->front();
    531545    while (stmt) {
    532         if (isa<If>(stmt)) {
     546        if (LLVM_UNLIKELY(isa<If>(stmt))) {
    533547            deadCodeElimination(cast<If>(stmt)->getBody());
    534         } else if (isa<While>(stmt)) {
     548        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    535549            deadCodeElimination(cast<While>(stmt)->getBody());
    536         } else if (stmt->getNumUses() == 0){
     550        } else if (LLVM_UNLIKELY(unused(stmt))){
    537551            stmt = stmt->eraseFromParent(true);
    538552            continue;
     
    562576                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
    563577                    adv->setOperand(0, op->getOperand(0));
    564                     adv->setOperand(1, block->getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
     578                    adv->setOperand(1, block->getInteger(adv->getAmount() + op->getAmount()));
    565579                    op->eraseFromParent(false);
    566580                }
     
    573587                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
    574588                    block->setInsertPoint(scanThru->getPrevNode());
    575                     PabloAST * expr = block->createAdvance(op->getOperand(0), op->getAdvanceAmount() - 1);
     589                    PabloAST * expr = block->createAdvance(op->getOperand(0), op->getAmount() - 1);
    576590                    scanThru->setOperand(0, expr);
    577591                    scanThru->setOperand(1, block->createOr(scanThru->getOperand(1), expr));
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4922 r4959  
    6666        , Advance
    6767        , ScanThru
     68        , Lookahead
    6869        , MatchStar
    6970        // Mod 64 approximate stream operations
    7071        , Mod64Advance
    7172        , Mod64ScanThru
     73        , Mod64Lookahead
    7274        , Mod64MatchStar
    7375        // Statistics operations
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

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

    r4951 r4959  
    88#define PABLO_COMPILER_H
    99
    10 
     10//Pablo Expressions
    1111#include <string>
    12 #include <list>
    1312#include <vector>
    14 #include <map>
    15 #include <algorithm>
    1613#include <unordered_map>
    17 #include <pablo/pe_string.h>
    1814#include <pablo/carry_manager.h>
    1915#include <llvm/ADT/Twine.h>
     
    3733namespace pablo {
    3834
    39 using namespace llvm;
    40 
    4135class PabloAST;
    4236class PabloBlock;
     
    5145class PabloCompiler {
    5246
    53     typedef std::unordered_map<const pablo::PabloAST *, Value *>   ASTToValueMap;
     47    using MarkerMap = std::unordered_map<const PabloAST *, Value *>;
    5448
    5549public:
    5650    PabloCompiler(Module * m, IDISA::IDISA_Builder * b);
    57     ~PabloCompiler();
    58     Function * compile(pablo::PabloFunction * function);   
     51
     52    llvm::Function * compile(PabloFunction * function);
    5953    void setKernel(KernelBuilder * kBuilder);
    60    
     54
    6155private:
    62     void GenerateFunction(PabloFunction & function);
     56
    6357    void Examine(PabloFunction & function);
    6458    void Examine(PabloBlock * block);
    65 
    66     void SetOutputValue(Value * marker, const unsigned index);
    6759
    6860    void compileBlock(PabloBlock * block);
     
    7062    void compileIf(const If * ifStmt);
    7163    void compileWhile(const While * whileStmt);
    72     Value* compileExpression(const PabloAST * expr);
    73     void GenerateKernel(PabloBlock * block, PabloFunction * function);
     64    Value * compileExpression(const PabloAST * expr);
     65    void GenerateKernel(PabloFunction * const function);
    7466
    75     ASTToValueMap                       mMarkerMap;
     67    MarkerMap                           mMarkerMap;
    7668
    7769    Module *                            mMod;
     
    8173    CarryManager *                      mCarryManager;
    8274
    83     PointerType*                        mInputType;
    84 
     75    PabloFunction *                     mPabloFunction;
    8576    PabloBlock *                        mPabloBlock;
    8677
    8778    KernelBuilder *                     mKBuilder;
    88    
     79
    8980    unsigned                            mWhileDepth;
    9081    unsigned                            mIfDepth;
    9182
    92     Function *                          mFunction;
    93     Value *                             mInputAddressPtr;
    94     Value *                             mOutputAddressPtr;
     83    llvm::Function *                    mFunction;
    9584
    9685    unsigned                            mMaxWhileDepth;
    9786    int                                 mFilePosIdx;
    98 
    9987};
    10088
  • icGREP/icgrep-devel/icgrep/pablo/pe_advance.h

    r4717 r4959  
    2828        return getOperand(0);
    2929    }
    30     inline Integer::Type getAdvanceAmount() const {
     30    inline Integer::Type getAmount() const {
    3131        return cast<Integer>(getOperand(1))->value();
    3232    }
    33     inline void setLocalAdvanceIndex(const unsigned idx) {
     33    inline void setLocalIndex(const unsigned idx) {
    3434        localAdvanceIndex = idx;
    3535    }
    36     inline unsigned getLocalAdvanceIndex() const {
     36    inline unsigned getLocalIndex() const {
    3737        return localAdvanceIndex;
    3838    }
     
    6161        return getOperand(0);
    6262    }
    63     inline Integer::Type getAdvanceAmount() const {
     63    inline Integer::Type getAmount() const {
    6464        return cast<Integer>(getOperand(1))->value();
    6565    }
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.cpp

    r4919 r4959  
    4141            out << ":\n";
    4242            print(ifNode->getBody(), out, true, indent + BlockIndenting);
    43             out.indent(indent);
    44             out << "Else:\n";
    45             print_vars(ifNode->getDefined(), out, indent + BlockIndenting);
     43            if (ifNode->getDefined().size() > 0) {
     44                out.indent(indent);
     45                out << "Else:\n";
     46                print_vars(ifNode->getDefined(), out, indent + BlockIndenting);
     47            }
    4648        }
    4749    } else if (const While * whileNode = dyn_cast<const While>(stmt)) {
     
    5355        }
    5456    } else if (const Call * call = dyn_cast<const Call>(stmt)) {
    55         out << " = " << call->getCallee() << "()";
     57        if (call->getPrototype()->getNumOfResults() > 0) {
     58            out << " = ";
     59        }
     60        out << call->getCallee() << "(";
     61        for (unsigned i = 0; i != call->getNumOperands(); ++i) {
     62            print(call->getOperand(i), out);
     63        }
     64        out << ")";
    5665    } else if (const And * andNode = dyn_cast<const And>(stmt)) {
    5766        out << andNode->getName() << " = (";
     
    9099        out << adv->getName() << " = pablo.Advance(";
    91100        print(adv->getExpr(), out);
    92         out << ", " << std::to_string(adv->getAdvanceAmount()) << ")";
     101        out << ", " << std::to_string(adv->getAmount()) << ")";
     102    } else if (const Lookahead * adv = dyn_cast<const Lookahead>(stmt)) {
     103        out << adv->getName() << " = pablo.Lookahead(";
     104        print(adv->getExpr(), out);
     105        out << ", " << std::to_string(adv->getAmount()) << ")";
    93106    } else if (const MatchStar * mstar = dyn_cast<const MatchStar>(stmt)) {
    94107        out << mstar->getName() << " = pablo.MatchStar(";
     
    106119        out << adv->getName() << " = pablo.Mod64Advance(";
    107120        print(adv->getExpr(), out);
    108         out << ", " << std::to_string(adv->getAdvanceAmount()) << ")";
     121        out << ", " << std::to_string(adv->getAmount()) << ")";
     122    } else if (const Mod64Lookahead * adv = dyn_cast<const Mod64Lookahead>(stmt)) {
     123        out << adv->getName() << " = pablo.Mod64Lookahead(";
     124        print(adv->getExpr(), out);
     125        out << ", " << std::to_string(adv->getAmount()) << ")";
    109126    } else if (const Mod64MatchStar * mstar = dyn_cast<const Mod64MatchStar>(stmt)) {
    110127        out << mstar->getName() << " = pablo.Mod64MatchStar(";
Note: See TracChangeset for help on using the changeset viewer.