Ignore:
Timestamp:
Dec 15, 2017, 12:44:01 PM (18 months ago)
Author:
nmedfort
Message:

Initial check-in of LookAhead? support; modified LineBreakKernel? to compute CR+LF using LookAhead?(1) + misc. fixes.

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

Legend:

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

    r5706 r5782  
    77#include <pablo/pablo_kernel.h>
    88#include <pablo/printer_pablos.h>
    9 #include <boost/container/flat_set.hpp>
    109#include <llvm/Support/ErrorHandling.h>
    1110#include <llvm/Support/raw_ostream.h>
     11#include <llvm/ADT/SmallSet.h>
     12#include <llvm/ADT/DenseMap.h>
     13#include <llvm/ADT/SmallBitVector.h>
     14#include <llvm/IR/Type.h>
    1215
    1316using namespace llvm;
     
    1720using TypeId = PabloAST::ClassTypeId;
    1821
    19 template <typename Type>
    20 using SmallSet = boost::container::flat_set<Type>;
    21 
    22 using ScopeSet = SmallSet<const PabloBlock *>;
     22using ScopeSet = SmallSet<const PabloBlock *, 32>;
    2323
    2424/** ------------------------------------------------------------------------------------------------------------- *
     
    2727void testUsers(const PabloAST * expr, const ScopeSet & validScopes) {
    2828    size_t uses = 0;
    29     SmallSet<const PabloAST *> verified;
     29    SmallSet<const PabloAST *, 16> verified;
    3030    for (const PabloAST * use : expr->users()) {
    3131        if (LLVM_UNLIKELY(verified.count(use) != 0)) {
     
    154154    }
    155155    verifyUseDefInformation(kernel->getEntryBlock(), validScopes);
    156 }
    157 
    158 /** ------------------------------------------------------------------------------------------------------------- *
    159  * @brief unreachable
    160  ** ------------------------------------------------------------------------------------------------------------- */
    161 bool unreachable(const Statement * stmt, const PabloBlock * const block) {
    162     PabloBlock * parent = stmt->getParent();
    163     while (parent)  {
    164         if (parent == block) {
    165             return false;
    166         }
    167         parent = parent->getPredecessor();
    168     }
    169     return true;
    170156}
    171157
     
    302288
    303289/** ------------------------------------------------------------------------------------------------------------- *
    304  * @brief isTopologicallyOrdered
    305  ** ------------------------------------------------------------------------------------------------------------- */
    306 struct OrderingVerifier {
    307     OrderingVerifier() : mParent(nullptr), mSet() {}
    308     OrderingVerifier(const OrderingVerifier & parent) : mParent(&parent) {}
    309     bool count(const PabloAST * expr) const {
     290 * @brief verifyAllPathsDominate
     291 ** ------------------------------------------------------------------------------------------------------------- */
     292void verifyAllPathsDominate(const PabloBlock * block) {
     293    for (const Statement * stmt : *block) {
     294        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     295            const PabloAST * const op = stmt->getOperand(i);
     296            if (LLVM_UNLIKELY(!dominates(op, stmt))) {
     297                std::string tmp;
     298                raw_string_ostream out(tmp);
     299                PabloPrinter::print(cast<Statement>(op), out);
     300                out << " does not dominate ";
     301                PabloPrinter::print(stmt, out);
     302                throw std::runtime_error(out.str());
     303            }
     304        }
     305        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     306            verifyAllPathsDominate(cast<Branch>(stmt)->getBody());
     307        }
     308    }
     309}
     310
     311void verifyAllPathsDominate(const PabloKernel * kernel) {
     312    verifyAllPathsDominate(kernel->getEntryBlock());
     313}
     314
     315/** ------------------------------------------------------------------------------------------------------------- *
     316 * @brief verifyVariableAssignments
     317 ** ------------------------------------------------------------------------------------------------------------- */
     318struct AssignmentSet {
     319    AssignmentSet() : mParent(nullptr), mSet() {}
     320    AssignmentSet(const AssignmentSet & parent) : mParent(&parent) {}
     321    bool contains(const Var * expr) const {
    310322        if (mSet.count(expr)) {
    311323            return true;
    312324        } else if (mParent) {
    313             return mParent->count(expr);
     325            return mParent->contains(expr);
    314326        }
    315327        return false;
    316328    }
    317     void insert(const PabloAST * expr) {
     329
     330    void insert_full(const Var * expr) {
     331        const auto n = getNumOfElements(expr);
     332        auto f = mAssignment.find(expr);
     333        if (LLVM_LIKELY(f == mAssignment.end())) {
     334            mAssignment.insert(std::move(std::make_pair(expr, SmallBitVector(n, true))));
     335        } else {
     336            f->second.resize(n, true);
     337        }
     338    }
     339
     340    void insert(const Var * expr, const unsigned i) {
    318341        mSet.insert(expr);
    319342    }
     343protected:
     344
     345    static unsigned getNumOfElements(const Var * expr) {
     346        const Type * const ty = expr->getType();
     347        if (ty->isArrayTy()) {
     348            return ty->getArrayNumElements();
     349        }
     350        return 1;
     351    }
     352
    320353private:
    321     const OrderingVerifier * const mParent;
    322     SmallSet<const PabloAST *> mSet;
     354    const AssignmentSet * const mParent;
     355    DenseMap<const Var *, SmallBitVector> mAssignment;
     356
     357    SmallSet<const Var *, 16> mSet;
    323358};
    324359
    325 void isTopologicallyOrdered(const PabloBlock * block, const OrderingVerifier & parent) {
    326     OrderingVerifier ov(parent);
    327     for (const Statement * stmt : *block) {
    328         if (LLVM_UNLIKELY(isa<While>(stmt))) {
    329             isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
    330             for (const Var * var : cast<While>(stmt)->getEscaped()) {
    331                 ov.insert(var);
    332             }
    333         } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
    334             ov.insert(cast<Assign>(stmt)->getVariable());
    335         }
    336         for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    337             const PabloAST * const op = stmt->getOperand(i);
    338             if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
    339                 std::string tmp;
    340                 raw_string_ostream out(tmp);
    341                 if (isa<Var>(op)) {
    342                     PabloPrinter::print(op, out);
    343                     out << " is used by ";
    344                     PabloPrinter::print(stmt, out);
    345                     out << " before being assigned a value.";
    346                 } else {
    347                     PabloPrinter::print(op, out);
    348                     if (LLVM_UNLIKELY(isa<Statement>(op) && unreachable(stmt, cast<Statement>(op)->getParent()))) {
    349                         out << " was defined in a scope that is unreachable by ";
    350                     } else {
    351                         out << " was used before definition by ";
    352                     }
    353                     PabloPrinter::print(stmt, out);
    354                 }
    355                 throw std::runtime_error(out.str());
    356             }
    357         }
    358         ov.insert(stmt);
    359         if (LLVM_UNLIKELY(isa<If>(stmt))) {
    360             isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
    361             for (const Var * def : cast<If>(stmt)->getEscaped()) {
    362                 ov.insert(def);
    363             }
    364         }
    365     }
    366 }
    367 
    368 void isTopologicallyOrdered(const PabloKernel * kernel) {
    369     OrderingVerifier ov;
    370     for (unsigned i = 0; i != kernel->getNumOfInputs(); ++i) {
    371         ov.insert(kernel->getInput(i));
    372     }
    373     for (unsigned i = 0; i != kernel->getNumOfOutputs(); ++i) {
    374         ov.insert(kernel->getOutput(i));
    375     }
    376     isTopologicallyOrdered(kernel->getEntryBlock(), ov);
    377 }
     360//void verifyVariableUsages(const PabloBlock * block, const AssignmentSet & parent) {
     361//    AssignmentSet A(parent);
     362//    for (const Statement * stmt : *block) {
     363//        if (isa<Assign>(stmt)) {
     364//            PabloAST * var = cast<Assign>(stmt)->getVariable();
     365//            if (isa<Extract>(var)) {
     366//                var = cast<Extract>(var)->getArray();
     367//            }
     368//            A.insert(cast<Var>(var));
     369//        } else if (isa<Extract>(stmt)) {
     370//            Var * const var = cast<Var>(cast<Extract>(var)->getArray());
     371//            if (A.contains(var)) {
     372//                continue;
     373//            }
     374//        } else {
     375//            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     376//                const PabloAST * const op = stmt->getOperand(i);
     377//                if (isa<Var>(op)) {
     378
     379//                }
     380//            }
     381//        }
     382
     383
     384
     385//        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     386//            const PabloAST * const op = stmt->getOperand(i);
     387//            if (LLVM_UNLIKELY(!dominates(op, stmt))) {
     388//                std::string tmp;
     389//                raw_string_ostream out(tmp);
     390//                PabloPrinter::print(cast<Statement>(op), out);
     391//                out << " does not dominate ";
     392//                PabloPrinter::print(stmt, out);
     393//                throw std::runtime_error(out.str());
     394//            }
     395//        }
     396//        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     397//            verifyAllPathsDominate(cast<Branch>(stmt)->getBody());
     398//        }
     399//    }
     400//}
     401
     402//void verifyVariableUsages(const PabloKernel * kernel) {
     403//    AssignmentSet A;
     404//    for (unsigned i = 0; i != kernel->getNumOfInputs(); ++i) {
     405//        A.insert(kernel->getInput(i));
     406//    }
     407//    for (unsigned i = 0; i != kernel->getNumOfOutputs(); ++i) {
     408//        A.insert(kernel->getOutput(i));
     409//    }
     410//    verifyVariableUsages(kernel->getEntryBlock(), A);
     411//}
     412
     413
    378414
    379415void PabloVerifier::verify(const PabloKernel * kernel, const std::string & location) {
     
    381417        verifyProgramStructure(kernel);
    382418        verifyUseDefInformation(kernel);
    383         isTopologicallyOrdered(kernel);
     419        verifyAllPathsDominate(kernel);
    384420    } catch(std::runtime_error & err) {
    385421        PabloPrinter::print(kernel, errs());
  • icGREP/icgrep-devel/icgrep/pablo/builder.cpp

    r5714 r5782  
    172172
    173173PabloAST * PabloBuilder::createLookahead(PabloAST * expr, PabloAST * shiftAmount) {
    174     if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
     174    if (LLVM_UNLIKELY(isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0)) {
    175175        return expr;
    176176    }
     
    180180
    181181PabloAST * PabloBuilder::createLookahead(PabloAST * expr, PabloAST * shiftAmount, const llvm::StringRef & prefix) {
    182     if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
     182    if (LLVM_UNLIKELY(isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0)) {
    183183        return expr;
    184184    }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r5706 r5782  
    483483                }
    484484            }
    485         } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt))) {
    486             ScanThru * scanThru = cast<ScanThru>(stmt);
    487             if (LLVM_UNLIKELY(isa<Advance>(scanThru->getScanFrom()))) {
    488                 // Replace a ScanThru(Advance(x,n),y) with an ScanThru(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x
    489                 Advance * adv = cast<Advance>(scanThru->getScanFrom());
    490                 if (LLVM_UNLIKELY(adv->getNumUses() == 1)) {
    491                     PabloAST * stream = adv->getExpression();
     485        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt))) {           
     486            ScanThru * const outer = cast<ScanThru>(stmt);
     487            if (LLVM_UNLIKELY(isa<Advance>(outer->getScanFrom()))) {
     488                // Replace ScanThru(Advance(x,n),y) with ScanThru(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x               
     489                Advance * const inner = cast<Advance>(outer->getScanFrom());
     490                if (LLVM_UNLIKELY(inner->getNumUses() == 1)) {
     491                    PabloAST * stream = inner->getExpression();
    492492                    block->setInsertPoint(stmt);
    493                     if (LLVM_UNLIKELY(adv->getAmount() != 1)) {
    494                         stream = block->createAdvance(stream, block->getInteger(adv->getAmount() - 1));
    495                     }
    496                     stmt = scanThru->replaceWith(block->createAdvanceThenScanThru(stream, scanThru->getScanThru()));
    497                     adv->eraseFromParent(false);
     493                    if (LLVM_UNLIKELY(inner->getAmount() != 1)) {
     494                        stream = block->createAdvance(stream, block->getInteger(inner->getAmount() - 1));
     495                    }
     496                    stmt = outer->replaceWith(block->createAdvanceThenScanThru(stream, outer->getScanThru()));
     497                    inner->eraseFromParent(false);
    498498                    continue;
    499499                }
    500             } else if (LLVM_UNLIKELY(isa<And>(scanThru->getScanFrom()))) {
     500            } else if (LLVM_UNLIKELY(isa<ScanThru>(outer->getScanFrom()))) {
     501                // Replace ScanThru(ScanThru(x, y), z) with ScanThru(x, y | z)
     502                ScanThru * const inner = cast<ScanThru>(outer->getScanFrom());
     503                block->setInsertPoint(stmt);
     504                ScanThru * const scanThru = block->createScanThru(inner->getScanFrom(), block->createOr(inner->getScanThru(), outer->getScanThru()));
     505                stmt->replaceWith(scanThru);
     506                stmt = scanThru;
     507                continue;
     508            } else if (LLVM_UNLIKELY(isa<And>(outer->getScanFrom()))) {
    501509                // Suppose B is an arbitrary bitstream and A = Advance(B, 1). ScanThru(B ∧ ¬A, B) will leave a marker on the position
    502510                // following the end of any run of 1-bits in B. But this is equivalent to computing A ∧ ¬B since A will have exactly
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r5706 r5782  
    8282            const Lookahead * const la = cast<Lookahead>(stmt);
    8383            PabloAST * input = la->getExpression();
    84             if (LLVM_UNLIKELY(isa<Extract>(input))) {
     84            if (isa<Extract>(input)) {
    8585                input = cast<Extract>(input)->getArray();
    8686            }
     
    8989                for (unsigned i = 0; i < mKernel->getNumOfInputs(); ++i) {
    9090                    if (input == mKernel->getInput(i)) {
    91                         if (LLVM_LIKELY(mKernel->getLookAhead(i) < la->getAmount())) {
    92                             mKernel->setLookAhead(i, la->getAmount());
     91                        const auto & binding = mKernel->getStreamInput(i);
     92                        if (LLVM_UNLIKELY(!binding.hasLookahead() || binding.getLookahead() < la->getAmount())) {
     93                            std::string tmp;
     94                            raw_string_ostream out(tmp);
     95                            input->print(out);
     96                            out << " must have a lookahead attribute of at least " << la->getAmount();
     97                            report_fatal_error(out.str());
    9398                        }
    9499                        notFound = false;
     
    566571            PabloAST * stream = l->getExpression();
    567572            Value * index = nullptr;
    568             if (LLVM_UNLIKELY(isa<Extract>(stream))) {
     573            if (LLVM_UNLIKELY(isa<Extract>(stream))) {               
     574                index = compileExpression(iBuilder, cast<Extract>(stream)->getIndex(), true);
    569575                stream = cast<Extract>(stream)->getArray();
    570                 index = compileExpression(iBuilder, cast<Extract>(stream)->getIndex());
    571576            } else {
    572577                index = iBuilder->getInt32(0);
     
    574579            const auto bit_shift = (l->getAmount() % iBuilder->getBitBlockWidth());
    575580            const auto block_shift = (l->getAmount() / iBuilder->getBitBlockWidth());
    576             Value * ptr = iBuilder->getAdjustedInputStreamBlockPtr(iBuilder->getSize(block_shift), cast<Var>(stream)->getName(), index);
     581            Value * ptr = iBuilder->getInputStreamBlockPtr(cast<Var>(stream)->getName(), index, iBuilder->getSize(block_shift));
    577582            Value * lookAhead = iBuilder->CreateBlockAlignedLoad(ptr);
    578583            if (bit_shift == 0) {  // Simple case with no intra-block shifting.
    579584                value = lookAhead;
    580585            } else { // Need to form shift result from two adjacent blocks.
    581                 Value * ptr = iBuilder->getAdjustedInputStreamBlockPtr(iBuilder->getSize(block_shift + 1), cast<Var>(stream)->getName(), index);
     586                Value * ptr = iBuilder->getInputStreamBlockPtr(cast<Var>(stream)->getName(), index, iBuilder->getSize(block_shift + 1));
    582587                Value * lookAhead1 = iBuilder->CreateBlockAlignedLoad(ptr);
    583588                if (LLVM_UNLIKELY((bit_shift % 8) == 0)) { // Use a single whole-byte shift, if possible.
  • icGREP/icgrep-devel/icgrep/pablo/pablo_kernel.cpp

    r5706 r5782  
    183183        }
    184184
    185 //        Value * base = iBuilder->CreateLoad(iBuilder->CreateGEP(profile, {iBuilder->getInt32(0), iBuilder->getInt32(0)}));
    186 //        base = iBuilder->CreateUIToFP(base, iBuilder->getDoubleTy());
    187 
    188 //        unsigned branchCount = 0;
    189 //        std::function<void (const PabloBlock *)> writeProfile = [&](const PabloBlock * const scope) {
    190 //            for (const Statement * stmt : *scope) {
    191 //                if (isa<Branch>(stmt)) {
    192 
    193 //                    ++branchCount;
    194 
    195 //                    std::string tmp;
    196 //                    raw_string_ostream str(tmp);
    197 //                    str << "%3.3f\t";
    198 //                    str << mPabloCompiler->getBranchEntry(branchCount)->getName();
    199 //                    str << "\n";
    200 
    201 //                    Value * branches = iBuilder->CreateLoad(iBuilder->CreateGEP(profile, {iBuilder->getInt32(0), iBuilder->getInt32(branchCount)}));
    202 //                    branches = iBuilder->CreateUIToFP(branches, iBuilder->getDoubleTy());
    203 //                    Value * prob = iBuilder->CreateFDiv(branches, base);
    204 //                    iBuilder->CreateCall(dprintf, {fd, iBuilder->GetString(str.str()), prob});
    205 
    206 //                    writeProfile(cast<Branch>(stmt)->getBody());
    207 
    208 //                }
    209 //            }
    210 //        };
    211 
    212 //        writeProfile(getEntryBlock());
    213185        iBuilder->CreateCloseCall(fd);
    214186    }
  • icGREP/icgrep-devel/icgrep/pablo/pe_lookahead.h

    r5646 r5782  
    2727        return getOperand(0);
    2828    }
    29     inline int64_t getAmount() const {
     29    inline unsigned getAmount() const {
    3030        return llvm::cast<Integer>(getOperand(1))->value();
    3131    }
     
    3333    Lookahead(PabloAST * expr, PabloAST * shiftAmount, const String * name, Allocator & allocator)
    3434    : Statement(ClassTypeId::Lookahead, expr->getType(), {expr, shiftAmount}, name, allocator) {
    35         assert(llvm::isa<Integer>(shiftAmount));
     35        assert(llvm::isa<Integer>(shiftAmount) && llvm::cast<Integer>(shiftAmount)->value() >= 0);
    3636    }
    3737};
Note: See TracChangeset for help on using the changeset viewer.