Changeset 5620


Ignore:
Timestamp:
Aug 28, 2017, 4:00:17 PM (3 months ago)
Author:
nmedfort
Message:

Bug fixes for multigrep mode. Optional PabloKernel? branch hit counter added. Minor optimizations.

Location:
icGREP/icgrep-devel/icgrep
Files:
34 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.cpp

    r5581 r5620  
    515515        }       
    516516        CC * const cc = dyn_cast<CC>(name->getDefinition());
    517         if (cc) {           
     517        if (cc) {
    518518            const auto f = CCs.find(cc);
     519            // This check may not be needed. Memoization ought to detect duplicate classes earlier.
    519520            if (LLVM_LIKELY(f == CCs.end())) {
    520521                PabloAST * const value = t.second ? t.second : zeroes;
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp

    r5386 r5620  
    152152
    153153/** ------------------------------------------------------------------------------------------------------------- *
     154 * @brief print
     155 ** ------------------------------------------------------------------------------------------------------------- */
     156void UnicodeSet::print(llvm::raw_ostream & out) const {
     157    if (LLVM_UNLIKELY(empty())) {
     158        out << "()";
     159    } else {
     160        char joiner = '(';
     161        for (auto r : *this) {
     162            out << joiner << std::get<0>(r);
     163            if (std::get<0>(r) != std::get<1>(r)) {
     164                out << '-' << std::get<1>(r);
     165            }
     166            joiner = ',';
     167        }
     168        out << ')';
     169
     170    }
     171}
     172
     173/** ------------------------------------------------------------------------------------------------------------- *
    154174 * @brief dump
    155175 ** ------------------------------------------------------------------------------------------------------------- */
     
    327347            i1 += n;
    328348            i2 += n;
    329         }
    330         else if (i1.type() == Empty) {
     349        } else if (i1.type() == Empty) {
    331350            for (unsigned i = 0; i < n; ++i, ++i2) {
    332351                append_quad(i2.quad(), quads, runs);
    333352            }
    334353            i1 += n;
    335         }
    336         else if (i2.type() == Empty) {
     354        } else if (i2.type() == Empty) {
    337355            for (unsigned i = 0; i < n; ++i, ++i1) {
    338356                append_quad(i1.quad(), quads, runs);
    339357            }
    340358            i2 += n;
    341         }
    342         else if (i1.type() == Full) {
     359        } else if (i1.type() == Full) {
    343360            for (unsigned i = 0; i < n; ++i, ++i2) {
    344361                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
    345362            }
    346363            i1 += n;
    347         }
    348         else if (i2.type() == Empty) {
     364        } else if (i2.type() == Full) {
    349365            for (unsigned i = 0; i < n; ++i, ++i1) {
    350366                append_quad(FULL_QUAD_MASK ^ i1.quad(), quads, runs);
    351367            }
    352368            i2 += n;
    353         }
    354         else {
     369        } else {
    355370            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
    356371                append_quad(i1.quad() ^ i2.quad(), quads, runs);
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.h

    r5278 r5620  
    101101    }
    102102
     103    bool empty() const;
     104
    103105    bool contains(const codepoint_t codepoint) const;
    104106
     
    109111    void insert_range(const codepoint_t lo, const codepoint_t hi);
    110112
    111     bool empty() const;
    112 
    113113    size_type size() const;
    114114
     
    116116
    117117    interval_t back() const;
     118
     119    void print(llvm::raw_ostream & out) const;
    118120
    119121    void dump(llvm::raw_ostream & out) const;
  • icGREP/icgrep-devel/icgrep/base64.cpp

    r5601 r5620  
    6363    //Round up to a multiple of 3.
    6464    const unsigned initSegSize = ((codegen::SegmentSize + 2)/3) * 3;
    65     const unsigned bufferSize = initSegSize * 4/3 * codegen::BufferSegments;
     65    const unsigned bufferSize = (4 * initSegSize * codegen::BufferSegments) / 3;
    6666
    6767    StreamSetBuffer * ByteStream = pxDriver.addBuffer(make_unique<SourceBuffer>(iBuilder, iBuilder->getStreamSetTy(1, 8)));
  • icGREP/icgrep-devel/icgrep/cc/alphabet.cpp

    r5279 r5620  
    1212// of the nth character is just the given value n, if it is in range.
    1313
    14 UCD::codepoint_t Alphabet::toUnicode(unsigned n) {
     14UCD::codepoint_t Alphabet::toUnicode(const unsigned n) const {
    1515    UCD::codepoint_t cp = n;
    1616    if (mCharSet.contains(cp)) return cp;
     
    2121// of a Unicode codepoint is just the given codepoint, if it is in range.
    2222
    23 unsigned Alphabet::fromUnicode(UCD::codepoint_t codepoint) {
     23unsigned Alphabet::fromUnicode(const UCD::codepoint_t codepoint) const {
    2424    if (mCharSet.contains(codepoint)) return codepoint;
    2525    throw std::runtime_error("fromUnicode: codepoint not found in alphabet.");
     
    3636}   
    3737
    38 template <class uint_t> UCD::codepoint_t ExtendedASCII<uint_t>::toUnicode(unsigned n) {
     38template <class uint_t> UCD::codepoint_t ExtendedASCII<uint_t>::toUnicode(const unsigned n) const {
    3939    //  The first 128 characters are just ASCII.
    4040    if (n < 128) return n;
     
    4343}   
    4444
    45 template <class uint_t> unsigned ExtendedASCII<uint_t>::fromUnicode(UCD::codepoint_t codepoint) {
     45template <class uint_t> unsigned ExtendedASCII<uint_t>::fromUnicode(const UCD::codepoint_t codepoint) const {
    4646    if (codepoint < 128) return codepoint;
    4747    for (unsigned i = 0; i < 128; i++) {
  • icGREP/icgrep-devel/icgrep/cc/alphabet.h

    r5281 r5620  
    2626        mAlphabetName(alphabetName), mCharSet(UCD::UnicodeSet(0, maxChar)) {}
    2727       
    28     std::string getName() { return mAlphabetName;}
     28    const std::string & getName() const { return mAlphabetName;}
    2929   
    30     UCD::UnicodeSet getSet() { return mCharSet;}
     30    const UCD::UnicodeSet & getSet() const { return mCharSet;}
    3131   
    3232    //  The Unicode codepoint of the nth character (the character whose alphabet code is n).
    33     virtual UCD::codepoint_t toUnicode(unsigned n);
     33    virtual UCD::codepoint_t toUnicode(const unsigned n) const;
    3434   
    3535    //  The ordinal position of the character whose Unicode codepoint value is ucp.
    36     virtual unsigned fromUnicode(UCD::codepoint_t ucp);
     36    virtual unsigned fromUnicode(const UCD::codepoint_t ucp) const;
    3737
    3838protected:
     
    5959public:
    6060    ExtendedASCII(std::string alphabetName, const uint_t (& extendedTable)[128]);
    61     UCD::codepoint_t  toUnicode(unsigned n) override;
    62     unsigned fromUnicode(UCD::codepoint_t ucp) override;
     61    UCD::codepoint_t toUnicode(const unsigned n) const final;
     62    unsigned fromUnicode(const UCD::codepoint_t ucp) const final;
    6363private:
    6464    const uint_t (& mExtendedCharacterTable)[128];
  • icGREP/icgrep-devel/icgrep/cc/cc_compiler.cpp

    r5310 r5620  
    1212#include <pablo/builder.hpp>
    1313#include <pablo/pablo_kernel.h>
     14
    1415
    1516using namespace re;
     
    3334   
    3435   
    35     CC_Compiler::CC_Compiler(pablo::PabloKernel * kernel, pablo::Var * basisBits)
    36     : mBuilder(kernel->getEntryBlock())
    37     , mEncodingBits(basisBits->getType()->getArrayNumElements())
    38     , mBasisBit(mEncodingBits) {
    39         for (unsigned i = 0; i != mEncodingBits; i++) {
    40             mBasisBit[i] = mBuilder.createExtract(basisBits, mBuilder.getInteger(i)); assert (mBasisBit[i]);
    41         }
    42         mEncodingMask = (static_cast<unsigned>(1) << mEncodingBits) - static_cast<unsigned>(1);
    43     }
    44    
    45    
    46 
    47 PabloAST * CC_Compiler::compileCC(const std::string & canonicalName, const CC *cc, PabloBlock & block) {
     36CC_Compiler::CC_Compiler(pablo::PabloKernel * kernel, pablo::Var * basisBits)
     37: mBuilder(kernel->getEntryBlock())
     38, mEncodingBits(basisBits->getType()->getArrayNumElements())
     39, mBasisBit(mEncodingBits) {
     40    for (unsigned i = 0; i != mEncodingBits; i++) {
     41        mBasisBit[i] = mBuilder.createExtract(basisBits, mBuilder.getInteger(i)); assert (mBasisBit[i]);
     42    }
     43    mEncodingMask = (static_cast<unsigned>(1) << mEncodingBits) - static_cast<unsigned>(1);
     44}
     45
     46PabloAST * CC_Compiler::compileCC(const std::string & canonicalName, const CC *cc, PabloBlock & block) {   
    4847    PabloAST * const var = charset_expr(cc, block);
    4948    if (LLVM_LIKELY(isa<Statement>(var))) {
     
    155154    for (codepoint_t diff_bits = n1 ^ n2; diff_bits; diff_count++, diff_bits >>= 1);
    156155
    157     if ((n2 < n1) || (diff_count > mEncodingBits))
    158     {
    159         throw std::runtime_error("Bad Range: [" + std::to_string(n1) + "," + std::to_string(n2) + "]");
     156    if ((n2 < n1) || (diff_count > mEncodingBits)) {
     157        throw std::runtime_error("Bad Range: [" + std::to_string(n1) + "," +
     158                                 std::to_string(n2) + "] for " +
     159                                 std::to_string(mEncodingBits) + "-bit encoding");
    160160    }
    161161
  • icGREP/icgrep-devel/icgrep/cc/cc_compiler.h

    r5440 r5620  
    3838    pablo::PabloBuilder & getBuilder();
    3939
    40     const std::vector<pablo::PabloAST *> & getBasisBits() {
     40    const std::vector<pablo::PabloAST *> & getBasisBits() const {
    4141        return mBasisBit;
    4242    }
  • icGREP/icgrep-devel/icgrep/combine/icgrep-test/icgrep-test.cpp

    r5614 r5620  
    3535    }
    3636
    37         for (const auto& dirEnt : fs::recursive_directory_iterator{src}) 
    38         {
     37        for (const auto& dirEnt : fs::recursive_directory_iterator{src})
     38    {
    3939        const auto& path = dirEnt.path();
    4040        auto relativePathStr = path.string();
  • icGREP/icgrep-devel/icgrep/grep_engine.cpp

    r5597 r5620  
    305305
    306306   
    307 std::pair<StreamSetBuffer *, StreamSetBuffer *> grepPipeline(Driver * grepDriver, std::vector<re::RE *> REs, const GrepModeType grepMode, unsigned encodingBits, StreamSetBuffer * ByteStream) {
     307std::pair<StreamSetBuffer *, StreamSetBuffer *> grepPipeline(Driver * grepDriver, std::vector<re::RE *> & REs, const GrepModeType grepMode, unsigned encodingBits, StreamSetBuffer * ByteStream) {
    308308    auto & idb = grepDriver->getBuilder();
    309309    const unsigned segmentSize = codegen::SegmentSize;
     
    334334        std::vector<std::vector<unsigned>> exclusiveSetIDs;
    335335        std::vector<UCD::UnicodeSet> multiplexedCCs;
    336 
    337336        doMultiplexCCs(UnicodeSets, exclusiveSetIDs, multiplexedCCs);
    338 
    339         REs[i] = multiplex(REs[i], UnicodeSets, exclusiveSetIDs, multiplexedCCs);
     337        REs[i] = multiplex(REs[i], UnicodeSets, exclusiveSetIDs);
    340338        charclasses.push_back(multiplexedCCs);
    341339    }
     
    344342
    345343    for(unsigned i = 0; i < n; ++i){
    346         StreamSetBuffer * CharClasses = grepDriver->addBuffer(make_unique<CircularBuffer>(idb, idb->getStreamSetTy(charclasses[i].size()), segmentSize * bufferSegments));
    347         kernel::Kernel * ccK = grepDriver->addKernelInstance(make_unique<kernel::CharClassesKernel>(idb, charclasses[i]));
    348         ccK->setName("cc" + std::to_string(i));
     344        const auto numOfCharacterClasses = charclasses[i].size();
     345        StreamSetBuffer * CharClasses = grepDriver->addBuffer(make_unique<CircularBuffer>(idb, idb->getStreamSetTy(numOfCharacterClasses), segmentSize * bufferSegments));
     346        kernel::Kernel * ccK = grepDriver->addKernelInstance(make_unique<kernel::CharClassesKernel>(idb, std::move(charclasses[i])));
    349347        grepDriver->makeKernelCall(ccK, {BasisBits}, {CharClasses});
    350348        StreamSetBuffer * MatchResults = grepDriver->addBuffer(make_unique<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), segmentSize * bufferSegments));
    351         kernel::Kernel * icgrepK = grepDriver->addKernelInstance(make_unique<kernel::ICGrepKernel>(idb, REs[i], true, charclasses[i].size()));
     349        kernel::Kernel * icgrepK = grepDriver->addKernelInstance(make_unique<kernel::ICGrepKernel>(idb, REs[i], true, numOfCharacterClasses));
    352350        grepDriver->makeKernelCall(icgrepK, {CharClasses, LineBreakStream, RequiredStreams}, {MatchResults});
    353351        MatchResultsBufs[i] = MatchResults;
  • icGREP/icgrep-devel/icgrep/grep_engine.h

    r5574 r5620  
    1010#include <string>       // for string
    1111#include <vector>
    12 #include <re/re_parser.h> 
     12#include <re/re_parser.h>
     13#include <re/re_multiplex.h>
    1314
    1415namespace re { class CC; }
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r5510 r5620  
    55cc/multiplex_CCs.cpp
    66cc/multiplex_CCs.h
     7combine/icgrep-test/icgrep-test.cpp
     8combine/icgrep-test/icgrep-test.h
     9combine/pugixml/src/pugiconfig.hpp
     10combine/pugixml/src/pugixml.cpp
     11combine/pugixml/src/pugixml.hpp
     12combine/core.cpp
     13combine/regexGen.cpp
     14combine/regexGen.h
     15combine/stringGen.cpp
     16combine/stringGen.h
     17combine/ugrep.cpp
    718editd/editd.cpp
    819editd/editd_cpu_kernel.cpp
     
    3950kernels/cc_scan_kernel.cpp
    4051kernels/cc_scan_kernel.h
     52kernels/charclasses.cpp
     53kernels/charclasses.h
    4154kernels/deletion.cpp
    4255kernels/deletion.h
     56kernels/delmask_kernel.cpp
     57kernels/delmask_kernel.h
    4358kernels/evenodd.cpp
    4459kernels/evenodd.h
     
    5772kernels/lz4_index_decoder.cpp
    5873kernels/lz4_index_decoder.h
    59 kernels/match_count.cpp
    60 kernels/match_count.h
    6174kernels/p2s_kernel.cpp
    6275kernels/p2s_kernel.h
     76kernels/pdep_kernel.cpp
     77kernels/pdep_kernel.h
    6378kernels/radix64.cpp
    6479kernels/radix64.h
     
    7792kernels/swizzle.cpp
    7893kernels/swizzle.h
     94kernels/u8u32_kernel.cpp
     95kernels/u8u32_kernel.h
    7996kernels/until_n.cpp
    8097kernels/until_n.h
     
    114131pablo/carry_manager.cpp
    115132pablo/carry_manager.h
     133pablo/carrypack_manager.cpp
     134pablo/carrypack_manager.h
    116135pablo/codegenstate.cpp
    117136pablo/codegenstate.h
     
    152171re/re_cc.cpp
    153172re/re_cc.h
     173re/re_collect_unicodesets.cpp
     174re/re_collect_unicodesets.h
    154175re/re_compiler.cpp
    155176re/re_compiler.h
     
    159180re/re_intersect.cpp
    160181re/re_intersect.h
     182re/re_local.cpp
     183re/re_local.h
    161184re/re_memoizer.hpp
     185re/re_multiplex.cpp
     186re/re_multiplex.h
    162187re/re_name.h
     188re/re_name_gather.cpp
     189re/re_name_gather.h
    163190re/re_name_resolve.cpp
    164191re/re_name_resolve.h
     
    180207re/re_rep.cpp
    181208re/re_rep.h
     209re/re_reverse.cpp
     210re/re_reverse.h
    182211re/re_seq.h
    183212re/re_simplifier.cpp
    184213re/re_simplifier.h
     214re/re_star_normal.cpp
     215re/re_star_normal.h
    185216re/re_start.h
    186217re/re_toolchain.cpp
     
    260291wc.cpp
    261292CMakeLists.txt
    262 pablo/carrypack_manager.cpp
    263 pablo/carrypack_manager.h
  • icGREP/icgrep-devel/icgrep/icgrep-devel.includes

    r5486 r5620  
    22../boost/include/
    33../libllvm/include/
    4 pablo
    5 kernels
    6 UCD
    7 editd
    8 IR_Gen
    9 util
    10 re
    11 toolchain
    12 pablo/passes
    13 pablo/analysis
    14 cc
    15 pablo/optimizers
  • icGREP/icgrep-devel/icgrep/icgrep.cpp

    r5554 r5620  
    9797        REs.swap(groups);
    9898    } else if (REs.size() > 1) {
    99         re::RE * re_ast = re::makeAlt(REs.begin(), REs.end());
    100         REs.assign({re_ast});
     99        REs.assign({re::makeAlt(REs.begin(), REs.end())});
    101100    }
    102101
    103102    for (re::RE *& re_ast : REs) {
     103        assert (re_ast);
    104104        if (grep::WordRegexpFlag) {
    105105            re_ast = re::makeSeq({re::makeWordBoundary(), re_ast, re::makeWordBoundary()});
  • icGREP/icgrep-devel/icgrep/kernels/charclasses.cpp

    r5564 r5620  
    1717#include <re/re_name.h>
    1818#include <llvm/Support/raw_ostream.h>
     19#include <boost/uuid/sha1.hpp>
    1920
    2021using NameMap = UCD::UCDCompiler::NameMap;
     
    2728using namespace UCD;
    2829
    29 CharClassesKernel::CharClassesKernel(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, std::vector<UCD::UnicodeSet> multiplexedCCs)
    30 : PabloKernel(iBuilder,
    31               "cc",
     30inline static std::string sha1sum(const std::string & str) {
     31    char buffer[41];    // 40 hex-digits and the terminating null
     32    uint32_t digest[5]; // 160 bits in total
     33    boost::uuids::detail::sha1 sha1;
     34    sha1.process_bytes(str.c_str(), str.size());
     35    sha1.get_digest(digest);
     36    snprintf(buffer, sizeof(buffer), "%.8x%.8x%.8x%.8x%.8x",
     37             digest[0], digest[1], digest[2], digest[3], digest[4]);
     38    return std::string(buffer);
     39}
     40
     41inline std::string signature(const std::vector<UCD::UnicodeSet> & ccs) {
     42    if (LLVM_UNLIKELY(ccs.empty())) {
     43        return "[]";
     44    } else {
     45        std::string tmp;
     46        raw_string_ostream out(tmp);
     47        char joiner = '[';
     48        for (const auto & set : ccs) {
     49            out << joiner;
     50            set.print(out);
     51            joiner = ',';
     52        }
     53        out << ']';
     54        return out.str();
     55    }
     56}
     57
     58CharClassesSignature::CharClassesSignature(const std::vector<UCD::UnicodeSet> & ccs)
     59: mSignature(signature(ccs)) {
     60
     61}
     62
     63
     64CharClassesKernel::CharClassesKernel(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, std::vector<UnicodeSet> && ccs)
     65: CharClassesSignature(ccs)
     66, PabloKernel(iBuilder,
     67              "cc" + sha1sum(mSignature),
    3268              {Binding{iBuilder->getStreamSetTy(8), "basis"}},
    33               {Binding{iBuilder->getStreamSetTy(multiplexedCCs.size(), 1), "charclasses"}})
    34 , mMultiplexedCCs(multiplexedCCs) {
     69              {Binding{iBuilder->getStreamSetTy(ccs.size(), 1), "charclasses"}})
     70, mCCs(std::move(ccs)) {
    3571
     72}
     73
     74std::string CharClassesKernel::makeSignature(const std::unique_ptr<kernel::KernelBuilder> &) {
     75    return mSignature;
    3676}
    3777
     
    3979    CC_Compiler ccc(this, getInput(0));
    4080    auto & pb = ccc.getBuilder();
    41     unsigned n = mMultiplexedCCs.size();
     81    unsigned n = mCCs.size();
    4282
    4383    NameMap nameMap;
    4484    std::vector<Name *> names;
    4585    for (unsigned i = 0; i < n; i++) {
    46         Name * name = re::makeName("cc" + std::to_string(i), makeCC(std::move(mMultiplexedCCs[i])));
     86        Name * name = re::makeName("cc" + std::to_string(i), makeCC(std::move(mCCs[i])));
    4787        nameMap.emplace(name, nullptr);
    4888        names.push_back(name);
     
    5696    }
    5797
    58     // The first UnicodeSet in the vector multiplexedCCs represents the last bit of the character class basis bit streams.
     98    // The first UnicodeSet in the vector ccs represents the last bit of the character class basis bit streams.
    5999    std::reverse(names.begin(), names.end());
    60100    for (unsigned i = 0; i < names.size(); i++) {
     
    68108            }
    69109        } else {
    70           throw std::runtime_error("Can't compile character classes.");
     110            throw std::runtime_error("Can't compile character classes.");
    71111        }
    72112    }
  • icGREP/icgrep-devel/icgrep/kernels/charclasses.h

    r5578 r5620  
    1414namespace kernel {
    1515
    16 class CharClassesKernel : public pablo::PabloKernel {
     16struct CharClassesSignature {
     17    CharClassesSignature(const std::vector<UCD::UnicodeSet> & ccs);
     18protected:
     19    const std::string mSignature;
     20};
     21
     22class CharClassesKernel : public CharClassesSignature, public pablo::PabloKernel {
    1723public:
    18     CharClassesKernel(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, std::vector<UCD::UnicodeSet> multiplexedCCs);
    19     bool hasSignature() const override { return false; }
     24    CharClassesKernel(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, std::vector<UCD::UnicodeSet> && ccs);
     25    bool hasSignature() const override { return true; }
     26    std::string makeSignature(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) override;
     27    bool isCachable() const override { return true; }
    2028protected:
    2129    void generatePabloMethod() override;
    2230protected:
    23     std::vector<UCD::UnicodeSet> mMultiplexedCCs;
     31    std::vector<UCD::UnicodeSet> mCCs;
    2432};
    2533
  • icGREP/icgrep-devel/icgrep/kernels/interface.h

    r5611 r5620  
    9494    }
    9595       
    96     void setName(std::string newName) { mKernelName = newName; }
    97 
    9896    virtual bool isCachable() const = 0;
    9997
     
    173171    llvm::Function * getTerminateFunction(llvm::Module * const module) const;
    174172
    175     KernelInterface(std::string kernelName,
     173    KernelInterface(const std::string && kernelName,
    176174                    std::vector<Binding> && stream_inputs,
    177175                    std::vector<Binding> && stream_outputs,
     
    198196    llvm::StructType *                      mKernelStateType;
    199197    unsigned                                mLookAheadPositions;
    200     std::string                             mKernelName;
     198    const std::string                       mKernelName;
    201199    std::vector<llvm::Value *>              mInitialArguments;
    202200    std::vector<Binding>                    mStreamSetInputs;
  • icGREP/icgrep-devel/icgrep/kernels/kernel.cpp

    r5615 r5620  
    191191    // will be able to add instrumentation to cached modules without recompilation.
    192192    addScalar(idb->getInt64Ty(), CYCLECOUNT_SCALAR);
    193    
    194     mKernelStateType = StructType::create(idb->getContext(), mKernelFields, getName());
    195    
     193    // NOTE: StructType::create always creates a new type even if an identical one exists.
     194    mKernelStateType = getModule()->getTypeByName(getName());
     195    if (LLVM_LIKELY(mKernelStateType == nullptr)) {
     196        mKernelStateType = StructType::create(idb->getContext(), mKernelFields, getName());
     197    }
    196198    processingRateAnalysis();
    197199}
     
    11601162        name += "_EA";
    11611163    }
     1164    name += "_O" + std::to_string((int)codegen::OptLevel);
    11621165    return name;
    11631166}
  • icGREP/icgrep-devel/icgrep/kernels/streamset.cpp

    r5618 r5620  
    811811}
    812812
     813inline StructType * getDynamicBufferStructType(const std::unique_ptr<kernel::KernelBuilder> & b, Type * baseType, const unsigned addrSpace) {
     814    IntegerType * sizeTy = b->getSizeTy();
     815    PointerType * typePtr = baseType->getPointerTo(addrSpace);
     816    return StructType::get(typePtr, typePtr, sizeTy, sizeTy, sizeTy, sizeTy, sizeTy, nullptr);
     817}
     818
    813819DynamicBuffer::DynamicBuffer(const std::unique_ptr<kernel::KernelBuilder> & b, Type * type, size_t initialCapacity, size_t overflow, unsigned swizzle, unsigned addrSpace)
    814820: StreamSetBuffer(BufferKind::DynamicBuffer, type, resolveStreamSetType(b, type), initialCapacity, addrSpace)
    815 , mBufferStructType(StructType::get(resolveStreamSetType(b, type)->getPointerTo(addrSpace), resolveStreamSetType(b, type)->getPointerTo(addrSpace),
    816                                     b->getSizeTy(), b->getSizeTy(), b->getSizeTy(), b->getSizeTy(), b->getSizeTy(), nullptr))
     821, mBufferStructType(getDynamicBufferStructType(b, mType, addrSpace))
    817822, mSwizzleFactor(swizzle)
    818823, mOverflowBlocks(overflow)
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.cpp

    r5566 r5620  
    99#include <pablo/analysis/pabloverifier.hpp>
    1010#endif
     11
     12#include <llvm/Support/raw_ostream.h>
     13#include <pablo/printer_pablos.h>
    1114
    1215using namespace llvm;
     
    183186        for (Var * variant : loop->getEscaped()) {
    184187            mLoopVariants.insert(variant);
    185         }
     188            mLoopInvariants.insert(variant);
     189        }
     190        mLoopInvariants.erase(loop->getCondition());
     191
    186192        Statement * outerNode = loop->getPrevNode();
    187193        Statement * stmt = loop->getBody()->front();
     
    190196                for (Var * var : cast<Branch>(stmt)->getEscaped()) {
    191197                    mLoopVariants.insert(var);
     198                    mLoopInvariants.erase(var);
    192199                }
    193200                stmt = stmt->getNextNode();
    194201            } else {
    195202                bool invariant = true;
    196                 for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    197                     if (mLoopVariants.count(stmt->getOperand(i)) != 0) {
     203                if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     204                    if (mLoopVariants.count(cast<Assign>(stmt)->getValue()) != 0) {
    198205                        invariant = false;
    199                         break;
    200206                    }
    201                 }
    202                 if (LLVM_UNLIKELY(invariant)) {
    203                     Statement * next = stmt->getNextNode();
     207                } else {
     208                    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     209                        const PabloAST * const op = stmt->getOperand(i);
     210                        if (mLoopVariants.count(op) != 0) {
     211                            if (isa<Var>(op)) {
     212                                mLoopInvariants.erase(op);
     213                            }
     214                            invariant = false;
     215                        }
     216                    }
     217                }
     218
     219                Statement * const next = stmt->getNextNode();
     220                if (LLVM_UNLIKELY(invariant)) {                   
    204221                    stmt->insertAfter(outerNode);
    205                     outerNode = stmt;
    206                     stmt = next;
     222                    outerNode = stmt;                   
    207223                } else {
    208224                    mLoopVariants.insert(stmt);
    209                     stmt = stmt->getNextNode();
    210                 }
     225                }
     226                stmt = next;
    211227            }
    212228        }
    213229        mLoopVariants.clear();
     230        assert (mLoopInvariants.empty());
    214231    }
    215232
     
    249266    UserSet         mUsers;
    250267    LoopVariants    mLoopVariants;
     268    LoopVariants    mLoopInvariants;
    251269};
    252270
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r5608 r5620  
    205205            entry->setInsertPoint(stmt->getPrevNode());
    206206            for (const auto e : make_iterator_range(in_edges(u, G))) {
    207                 stmt->setOperand(G[e], regenerateIfNecessary(stmt, entry, source(e, G), count));
     207                const auto v = source(e, G);
     208                stmt->setOperand(G[e], regenerateIfNecessary(stmt, entry, v, count));
     209                setLastUsageTime(v, ++count);
    208210            }
    209211            setValue(u, stmt);
    210212            setLastUsageTime(u, ++count);
    211 
    212             if (isa<Branch>(stmt)) {
     213            if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
    213214                count = rewriteAST(cast<Branch>(stmt)->getBody(), count);
    214215            }
     
    299300            assert (value);
    300301            setUnmodified(u);
    301             setValue(u, value);
    302             setLastUsageTime(u, ++count);
    303         }
     302            setValue(u, value);           
     303        }       
    304304        return value;
    305305    }
     
    325325
    326326    /** ------------------------------------------------------------------------------------------------------------- *
     327     * @brief printGraph
     328     ** ------------------------------------------------------------------------------------------------------------- */
     329    void printGraph(const std::string & name, llvm::raw_ostream & out, std::vector<Vertex> restricted = {}) {
     330
     331        const auto n = num_vertices(G);
     332        std::vector<unsigned> c(n);
     333        const auto components = strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
     334
     335        std::vector<bool> show(n, false);
     336        if (LLVM_LIKELY(restricted.empty() && n == components)) {
     337            for (const auto u : make_iterator_range(vertices(G))) {
     338                show[u] = isLive(u);
     339            }
     340        } else {
     341            std::queue<Vertex> Q;
     342            for (const auto m : restricted) {
     343                if (m < n && isLive(m)) {
     344                    show[m] = true;
     345                    assert (Q.empty());
     346                    Q.push(m);
     347                    for (;;) {
     348                        const auto u = Q.front();
     349                        Q.pop();
     350                        for (auto e : make_iterator_range(in_edges(u, G))) {
     351                            const auto v = source(e, G);
     352                            if (show[v] || !isLive(v)) {
     353                                continue;
     354                            }
     355                            show[v] = true;
     356                            Q.push(v);
     357                        }
     358                        if (Q.empty()) {
     359                            break;
     360                        }
     361                    }
     362                    for (auto e : make_iterator_range(out_edges(m, G))) {
     363                        const auto v = target(e, G);
     364                        show[v] = isLive(v) ? true : show[v];
     365                    }
     366                }
     367            }
     368        }
     369
     370        out << "digraph " << name << " {\n";
     371        for (auto u : make_iterator_range(vertices(G))) {
     372
     373            if (show[u]) {
     374
     375                out << "v" << u << " [label=\"" << u << ": ";
     376                TypeId typeId;
     377                PabloAST * expr;
     378                State state;
     379
     380                std::tie(expr, typeId, state, std::ignore) = G[u];
     381
     382                bool space = true;
     383
     384                switch (typeId) {
     385                    case TypeId::And:
     386                        out << "(∧)";
     387                        break;
     388                    case TypeId::Or:
     389                        out << "(√)";
     390                        break;
     391                    case TypeId::Xor:
     392                        out << "(⊕)";
     393                        break;
     394                    case TypeId::Not:
     395                        out << "(¬)";
     396                        break;
     397                    case TypeId::Zeroes:
     398                        out << "(⊥)";
     399                        break;
     400                    case TypeId::Ones:
     401                        out << "(⊀)";
     402                    default:
     403                        space = false;
     404                        break;
     405                }
     406                if (expr) {
     407                    if (space) {
     408                        out << ' ';
     409                    }
     410                    expr->print(out);
     411                }
     412
     413                out << "\"";
     414                if (!hasValidOperandIndicies(u, false)) {
     415                    out << " color=red style=bold";
     416                } else if (!(isImmutable(typeId) || out_degree(u, G) > 0)) {
     417                    out << " color=orange style=bold";
     418                } else if (isRegenerable(typeId)) {
     419                    out << " color=blue";
     420                    if (state == State::Modified) {
     421                        out << " style=dashed";
     422                    }
     423                }
     424                out << "];\n";
     425            }
     426        }
     427        for (auto e : make_iterator_range(edges(G))) {
     428            const auto s = source(e, G);
     429            const auto t = target(e, G);
     430            if (show[s] && show[t]) {
     431                const auto cyclic = (c[s] == c[t]);
     432                const auto nonAssoc = !isAssociative(getType(t));
     433                out << "v" << s << " -> v" << t;
     434                if (cyclic || nonAssoc) {
     435                    out << " [";
     436                    if (nonAssoc) {
     437                        out << " label=\"" << G[e] << "\"";
     438                    }
     439                    if (cyclic) {
     440                        out << " color=red";
     441                    }
     442                    out << "]";
     443                }
     444                out << ";\n";
     445            }
     446        }
     447
     448        out << "}\n\n";
     449        out.flush();
     450    }
     451
     452    /** ------------------------------------------------------------------------------------------------------------- *
    327453     * @brief getReverseTopologicalOrdering
    328454     ** ------------------------------------------------------------------------------------------------------------- */
     
    332458            PrePassInserter & operator=(const Vertex u) {
    333459                if (LLVM_LIKELY(self.isLive(u))) {
    334                     assert(self.hasValidOperandIndicies(u));
     460                    assert (self.hasValidOperandIndicies(u));
    335461                    if (LLVM_UNLIKELY(isImmutable(self.getType(u)))) {
    336462                        /* do nothing */
     
    353479        };
    354480
    355 
    356481        ordering.clear();
    357482        ordering.reserve(num_vertices(G));
     
    370495
    371496            const auto typeId = getType(u);
    372 
    373497            assert (isLive(u));
    374498            assert (!isImmutable(typeId));
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r5607 r5620  
    1313#include <pablo/pe_matchstar.h>
    1414#include <pablo/pe_var.h>
    15 #include <boost/container/flat_set.hpp>
    1615#ifndef NDEBUG
    1716#include <pablo/analysis/pabloverifier.hpp>
    1817#endif
    19 #include <llvm/Support/raw_ostream.h>
    20 
     18#include <boost/container/flat_set.hpp>
    2119
    2220using namespace boost;
     
    2826using TypeId = PabloAST::ClassTypeId;
    2927
     28using ScopeMap = flat_map<PabloBlock *, unsigned>;
     29
     30/** ------------------------------------------------------------------------------------------------------------- *
     31 * @brief VariableTable
     32 ** ------------------------------------------------------------------------------------------------------------- */
     33struct VariableTable {
     34
     35    VariableTable(VariableTable * predecessor = nullptr)
     36    : mPredecessor(predecessor) {
     37
     38    }
     39
     40    PabloAST * get(PabloAST * const var) const {
     41        const auto f = mMap.find(var);
     42        if (f == mMap.end()) {
     43            return (mPredecessor) ? mPredecessor->get(var) : nullptr;
     44        }
     45        return f->second;
     46    }
     47
     48    void put(PabloAST * const var, PabloAST * value) {
     49        const auto f = mMap.find(var);
     50        if (LLVM_LIKELY(f == mMap.end())) {
     51            mMap.emplace(var, value);
     52        } else {
     53            f->second = value;
     54        }
     55        assert (get(var) == value);
     56    }
     57
     58private:
     59    VariableTable * const mPredecessor;
     60    flat_map<PabloAST *, PabloAST *> mMap;
     61};
     62
     63struct PassContainer {
     64
     65/** ------------------------------------------------------------------------------------------------------------- *
     66 * @brief run
     67 ** ------------------------------------------------------------------------------------------------------------- */
     68void run(PabloKernel * const kernel) {
     69    redundancyElimination(kernel->getEntryBlock(), nullptr, nullptr);
     70    strengthReduction(kernel->getEntryBlock());
     71    deadCodeElimination(kernel->getEntryBlock());
     72}
     73
     74protected:
     75
     76/** ------------------------------------------------------------------------------------------------------------- *
     77 * @brief redundancyElimination
     78 *
     79 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
     80 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
     81 ** ------------------------------------------------------------------------------------------------------------- */
     82void redundancyElimination(PabloBlock * const block, ExpressionTable * const et, VariableTable * const vt) {
     83    ExpressionTable expressions(et);
     84    VariableTable variables(vt);
     85
     86    if (Branch * br = block->getBranch()) {
     87        assert ("block has a branch but the expression and variable tables were not supplied" && et && vt);
     88        for (Var * var : br->getEscaped()) {
     89            variables.put(var, var);
     90        }
     91    }
     92
     93    mInScope.push_back(block);
     94
     95    const auto baseNonZeroEntries = mNonZero.size();
     96    Statement * stmt = block->front();
     97    while (stmt) {
     98
     99        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     100            Assign * const assign = cast<Assign>(stmt);
     101            PabloAST * const var = assign->getVariable();
     102            PabloAST * value = assign->getValue();
     103            if (LLVM_UNLIKELY(var == value)) {
     104                stmt = stmt->eraseFromParent();
     105                continue;
     106            }
     107            while (LLVM_UNLIKELY(isa<Var>(value))) {
     108                PabloAST * next = variables.get(cast<Var>(value));
     109                if (LLVM_LIKELY(next == nullptr || next == value)) {
     110                    break;
     111                }
     112                value = next;
     113                assign->setValue(value);
     114            }
     115            if (LLVM_UNLIKELY(variables.get(var) == value)) {
     116                stmt = stmt->eraseFromParent();
     117                continue;
     118            }
     119            variables.put(var, value);
     120
     121        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     122
     123            Branch * const br = cast<Branch>(stmt);
     124            PabloAST * cond = br->getCondition();
     125            if (isa<Var>(cond)) {
     126                PabloAST * const value = variables.get(cast<Var>(cond));
     127                if (value) {
     128                    cond = value;
     129                    if (isa<If>(br)) {
     130                        br->setCondition(cond);
     131                    }
     132                }
     133            }
     134
     135            // Test whether we can ever take this branch
     136            if (LLVM_UNLIKELY(isa<Zeroes>(cond))) {
     137                stmt = stmt->eraseFromParent();
     138                continue;
     139            }
     140
     141            // If we're guaranteed to take this branch, flatten it.
     142            if (LLVM_LIKELY(isa<If>(br)) && LLVM_UNLIKELY(isNonZero(cond))) {
     143                stmt = flatten(br);
     144                continue;
     145            }
     146
     147            // Mark the cond as non-zero prior to processing the inner scope.
     148            mNonZero.push_back(cond);
     149            // Process the Branch body
     150            redundancyElimination(br->getBody(), &expressions, &variables);
     151            assert (mNonZero.back() == cond);
     152            mNonZero.pop_back();
     153
     154            if (LLVM_LIKELY(isa<If>(br))) {
     155                // Check whether the cost of testing the condition and taking the branch with
     156                // 100% correct prediction rate exceeds the cost of the body itself
     157                if (LLVM_UNLIKELY(isTrivial(br->getBody()))) {
     158                    stmt = flatten(br);
     159                    continue;
     160                }
     161            }
     162
     163        } else {
     164
     165            // demote any uses of any Var whose value is in scope
     166            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     167                PabloAST * op = stmt->getOperand(i);
     168                if (LLVM_UNLIKELY(isa<Var>(op))) {
     169                    PabloAST * const value = variables.get(cast<Var>(op));
     170                    if (value && value != op) {
     171                        stmt->setOperand(i, value);
     172                    }
     173                }
     174            }
     175
     176            PabloAST * const folded = triviallyFold(stmt, block);
     177            if (folded) {
     178                Statement * const prior = stmt->getPrevNode();
     179                stmt->replaceWith(folded);
     180                stmt = prior ? prior->getNextNode() : block->front();
     181                continue;
     182            }
     183
     184            // By recording which statements have already been seen, we can detect the redundant statements
     185            // as any having the same type and operands. If so, we can replace its users with the prior statement.
     186            // and erase this statement from the AST
     187            const auto f = expressions.findOrAdd(stmt);
     188            if (!f.second) {
     189                stmt = stmt->replaceWith(f.first);
     190                continue;
     191            }
     192
     193            // Attempt to extend our set of trivially non-zero statements.
     194            if (isa<Or>(stmt)) {
     195                for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     196                    if (LLVM_UNLIKELY(isNonZero(stmt->getOperand(i)))) {
     197                        mNonZero.push_back(stmt);
     198                        break;
     199                    }
     200                }
     201            } else if (isa<Advance>(stmt)) {
     202                const Advance * const adv = cast<Advance>(stmt);
     203                if (LLVM_LIKELY(adv->getAmount() < (adv->getType()->getPrimitiveSizeInBits() / 2))) {
     204                    if (LLVM_UNLIKELY(isNonZero(adv->getExpression()))) {
     205                        mNonZero.push_back(adv);
     206                    }
     207                }
     208            }
     209        }
     210
     211        stmt = stmt->getNextNode();
     212    }
     213
     214    // Erase any local non-zero entries that were discovered while processing this scope
     215    mNonZero.erase(mNonZero.begin() + baseNonZeroEntries, mNonZero.end());
     216
     217    assert (mInScope.back() == block);
     218    mInScope.pop_back();
     219
     220    // If this block has a branch statement leading into it, we can verify whether an escaped value
     221    // was updated within this block and update the preceeding block's variable state appropriately.
     222
     223    Branch * const br = block->getBranch();
     224    if (LLVM_LIKELY(br != nullptr)) {
     225
     226        // When removing identical escaped values, we have to consider that the identical Vars could
     227        // be assigned new differing values later in the outer body. Thus instead of replacing them
     228        // directly, we map future uses of the duplicate Var to the initial one. The DCE pass will
     229        // later mark any Assign statement as dead if the Var is never read.
     230
     231        const auto escaped = br->getEscaped();
     232        const auto n = escaped.size();
     233        PabloAST * variable[n];
     234        PabloAST * incoming[n];
     235        PabloAST * outgoing[n];
     236        for (unsigned i = 0; i < n; ++i) {
     237            variable[i] = escaped[i];
     238            incoming[i] = vt->get(variable[i]);
     239            outgoing[i] = variables.get(variable[i]);
     240            if (LLVM_UNLIKELY(incoming[i] == outgoing[i])) {
     241                variable[i] = incoming[i];
     242            } else {
     243                for (unsigned j = 0; j < i; ++j) {
     244                    if (LLVM_UNLIKELY((outgoing[j] == outgoing[i]) && (incoming[j] == incoming[i]))) {
     245                        variable[i] = variable[j];
     246                        break;
     247                    }
     248                }
     249            }
     250            vt->put(escaped[i], variable[i]);
     251        }
     252
     253    }
     254
     255}
     256
     257
    30258/** ------------------------------------------------------------------------------------------------------------- *
    31259 * @brief fold
    32260 ** ------------------------------------------------------------------------------------------------------------- */
    33 PabloAST * triviallyFold(Statement * stmt, PabloBlock * const block) {
     261static PabloAST * triviallyFold(Statement * stmt, PabloBlock * const block) {
    34262    if (isa<Not>(stmt)) {
    35263        PabloAST * value = stmt->getOperand(0);
     
    41269            return block->createZeroes(stmt->getType()); // ¬1 ⇔ 0
    42270        }
    43     } else if (isa<Advance>(stmt)) {
    44         if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(0)))) {
    45             return block->createZeroes(stmt->getType());
    46         }
    47     } else if (isa<Add>(stmt) || isa<Subtract>(stmt)) {
     271    } else if (LLVM_UNLIKELY(isa<Add>(stmt) || isa<Subtract>(stmt))) {
    48272       if (LLVM_UNLIKELY(isa<Integer>(stmt->getOperand(0)) && isa<Integer>(stmt->getOperand(1)))) {
    49273           const Integer * const int0 = cast<Integer>(stmt->getOperand(0));
     
    57281           return block->getInteger(result);
    58282       }
     283    } else if (LLVM_UNLIKELY(isa<Variadic>(stmt))) {
     284
     285        std::sort(cast<Variadic>(stmt)->begin(), cast<Variadic>(stmt)->end());
     286
     287        for (unsigned i = 1; i < stmt->getNumOperands(); ) {
     288            if (LLVM_UNLIKELY(stmt->getOperand(i - 1) == stmt->getOperand(i))) {
     289                if (LLVM_UNLIKELY(isa<Xor>(stmt))) {
     290                    if (LLVM_LIKELY(stmt->getNumOperands() == 2)) {
     291                        return block->createZeroes(stmt->getType());
     292                    } else {
     293                        cast<Variadic>(stmt)->removeOperand(i);
     294                        cast<Variadic>(stmt)->removeOperand(i - 1);
     295                        continue;
     296                    }
     297                } else {
     298                    if (LLVM_LIKELY(stmt->getNumOperands() == 2)) {
     299                        return stmt->getOperand(1 - i);
     300                    } else {
     301                        cast<Variadic>(stmt)->removeOperand(i);
     302                        continue;
     303                    }
     304                }
     305            }
     306            ++i;
     307        }
     308
     309        if (LLVM_UNLIKELY(stmt->getNumOperands() < 2)) {
     310            if (LLVM_LIKELY(stmt->getNumOperands() == 1)) {
     311                return stmt->getOperand(0);
     312            } else {
     313                return block->createZeroes(stmt->getType());
     314            }
     315        }
     316
     317        if (LLVM_UNLIKELY(isa<Xor>(stmt))) {
     318            bool negated = false;
     319            PabloAST * expr = nullptr;
     320            for (unsigned i = 0; i < stmt->getNumOperands(); ) {
     321                const PabloAST * const op = stmt->getOperand(i);
     322                if (isa<Not>(op)) {
     323                    negated ^= true;
     324                    stmt->setOperand(i, cast<Not>(op)->getExpr());
     325                } else if (LLVM_UNLIKELY(isa<Zeroes>(op) || isa<Ones>(op))) {
     326                    negated ^= isa<Ones>(op);
     327                    if (LLVM_LIKELY(stmt->getNumOperands() == 2)) {
     328                        expr = stmt->getOperand(1 - i);
     329                        break;
     330                    } else {
     331                        cast<Variadic>(stmt)->removeOperand(i);
     332                        continue;
     333                    }
     334                }
     335                ++i;
     336            }
     337            if (LLVM_UNLIKELY(negated)) {
     338                block->setInsertPoint(stmt);
     339                expr = block->createNot(expr ? expr : stmt);
     340            }
     341            return expr;
     342        } else { // if (isa<And>(stmt) || isa<Or>(stmt))
     343            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     344                const PabloAST * const op = stmt->getOperand(i);
     345                if (LLVM_UNLIKELY(isa<Zeroes>(op) || isa<Ones>(op))) {
     346                    if (isa<And>(stmt) ^ isa<Zeroes>(op)) {
     347                        if (LLVM_LIKELY(stmt->getNumOperands() == 2)) {
     348                            return stmt->getOperand(1 - i);
     349                        } else {
     350                            cast<Variadic>(stmt)->removeOperand(i);
     351                            continue;
     352                        }
     353                    } else {
     354                        return stmt->getOperand(i);
     355                    }
     356                }
     357                ++i;
     358            }
     359        }
    59360    } else {
    60361        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     
    68369                            case 2: return block->createAnd(stmt->getOperand(0), stmt->getOperand(1));
    69370                        }
     371                    case TypeId::Advance:
    70372                    case TypeId::ScanThru:
    71373                    case TypeId::MatchStar:
     
    101403
    102404/** ------------------------------------------------------------------------------------------------------------- *
    103  * @brief VariableTable
    104  ** ------------------------------------------------------------------------------------------------------------- */
    105 struct VariableTable {
    106 
    107     VariableTable(VariableTable * predecessor = nullptr)
    108     : mPredecessor(predecessor) {
    109 
    110     }
    111 
    112     PabloAST * get(PabloAST * const var) const {
    113         const auto f = mMap.find(var);
    114         if (f == mMap.end()) {
    115             return (mPredecessor) ? mPredecessor->get(var) : nullptr;
    116         }
    117         return f->second;
    118     }
    119 
    120     void put(PabloAST * const var, PabloAST * value) {
    121         const auto f = mMap.find(var);
    122         if (LLVM_LIKELY(f == mMap.end())) {
    123             mMap.emplace(var, value);
    124         } else {
    125             f->second = value;
    126         }
    127         assert (get(var) == value);
    128     }
    129 
    130     bool isNonZero(const PabloAST * const var) const {
    131         if (mNonZero.count(var) != 0) {
    132             return true;
    133         } else if (mPredecessor) {
    134             return mPredecessor->isNonZero(var);
    135         }
    136         return false;
    137     }
    138 
    139     void addNonZero(const PabloAST * const var) {
    140         mNonZero.insert(var);
    141     }
    142 
    143 private:
    144     VariableTable * const mPredecessor;
    145     flat_map<PabloAST *, PabloAST *> mMap;
    146     flat_set<const PabloAST *> mNonZero;
    147 };
    148 
    149 /** ------------------------------------------------------------------------------------------------------------- *
    150405 * @brief isTrivial
    151406 *
     
    153408 * statements, just add the statements in the inner block to the current block
    154409 ** ------------------------------------------------------------------------------------------------------------- */
    155 inline bool isTrivial(const PabloBlock * const block) {
     410static bool isTrivial(const PabloBlock * const block) {
    156411    unsigned computations = 0;
    157412    for (const Statement * stmt : *block) {
     
    176431 * @brief flatten
    177432 ** ------------------------------------------------------------------------------------------------------------- */
    178 Statement * flatten(Branch * const br) {
     433static Statement * flatten(Branch * const br) {
    179434    Statement * stmt = br;
    180435    Statement * nested = br->getBody()->front();
     
    189444
    190445/** ------------------------------------------------------------------------------------------------------------- *
    191  * @brief redundancyElimination
    192  *
    193  * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
    194  * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
    195  ** ------------------------------------------------------------------------------------------------------------- */
    196 void redundancyElimination(PabloBlock * const block, ExpressionTable * const et, VariableTable * const vt) {
    197     VariableTable variables(vt);
    198 
    199     // When processing a While body, we cannot use its initial value from the outer
    200     // body since the Var will likely be assigned a different value in the current
    201     // body that should be used on the subsequent iteration of the loop.
    202     if (Branch * br = block->getBranch()) {
    203         assert ("block has a branch but the expression and variable tables were not supplied" && et && vt);
    204         variables.addNonZero(br->getCondition());
    205         for (Var * var : br->getEscaped()) {
    206             variables.put(var, var);
    207         }
    208     }
    209 
    210     ExpressionTable expressions(et);
    211 
    212     Statement * stmt = block->front();
    213     while (stmt) {
    214 
    215         if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
    216             Assign * const assign = cast<Assign>(stmt);
    217             PabloAST * const var = assign->getVariable();
    218             PabloAST * value = assign->getValue();
    219             while (LLVM_UNLIKELY(isa<Var>(value))) {
    220                 PabloAST * next = variables.get(cast<Var>(value));
    221                 if (LLVM_LIKELY(next == nullptr || next == value)) {
    222                     break;
    223                 }
    224                 value = next;
    225                 assign->setValue(value);
    226             }
    227             if (LLVM_UNLIKELY(variables.get(var) == value)) {
    228                 stmt = stmt->eraseFromParent();
    229                 continue;
    230             }
    231             variables.put(var, value);
    232         } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
    233 
    234             Branch * const br = cast<Branch>(stmt);
    235 
    236             // Test whether we can ever take this branch
    237             PabloAST * cond = br->getCondition();
    238             if (isa<Var>(cond)) {
    239                 PabloAST * const value = variables.get(cast<Var>(cond));
    240                 if (value) {
    241                     cond = value;
    242                     // TODO: verify this works for a nested If node within a While body.
    243                     if (isa<If>(br)) {
    244                         br->setCondition(cond);
    245                     }
    246                 }
    247             }
    248 
    249             if (LLVM_UNLIKELY(isa<Zeroes>(cond))) {
    250                 stmt = stmt->eraseFromParent();
    251                 continue;
    252             }
    253 
    254             if (LLVM_LIKELY(isa<If>(br))) {
    255                 if (LLVM_UNLIKELY(variables.isNonZero(cond))) {
    256                     stmt = flatten(br);
    257                     continue;
    258                 }
    259             }
    260 
    261             // Process the Branch body
    262             redundancyElimination(br->getBody(), &expressions, &variables);
    263 
    264             if (LLVM_LIKELY(isa<If>(br))) {
    265                 // Check whether the cost of testing the condition and taking the branch with
    266                 // 100% correct prediction rate exceeds the cost of the body itself
    267                 if (LLVM_UNLIKELY(isTrivial(br->getBody()))) {
    268                     stmt = flatten(br);
    269                     continue;
    270                 }
    271             }
    272 
    273         } else {
    274 
    275             // demote any uses of a Var whose value is in scope
    276             for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
    277                 PabloAST * op = stmt->getOperand(i);
    278                 if (LLVM_UNLIKELY(isa<Var>(op))) {
    279                     PabloAST * const value = variables.get(cast<Var>(op));
    280                     if (value && value != op) {
    281                         stmt->setOperand(i, value);
    282                     }
    283                 }
    284             }
    285 
    286             PabloAST * const folded = triviallyFold(stmt, block);
    287             if (folded) {
    288                 stmt = stmt->replaceWith(folded);
    289                 continue;
    290             }
    291 
    292             // By recording which statements have already been seen, we can detect the redundant statements
    293             // as any having the same type and operands. If so, we can replace its users with the prior statement.
    294             // and erase this statement from the AST
    295             const auto f = expressions.findOrAdd(stmt);
    296             if (!f.second) {
    297                 stmt = stmt->replaceWith(f.first);
    298                 continue;
    299             }
    300 
    301             // Check whether this statement is trivially non-zero and if so, add it to our set of non-zero variables.
    302             // This will allow us to flatten an If scope if its branch is always taken.
    303             if (isa<Or>(stmt)) {
    304                 for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
    305                     if (LLVM_UNLIKELY(variables.isNonZero(stmt->getOperand(i)))) {
    306                         variables.addNonZero(stmt);
    307                         break;
    308                     }
    309                 }
    310             } else if (isa<Advance>(stmt)) {
    311                 const Advance * const adv = cast<Advance>(stmt);
    312                 if (LLVM_LIKELY(adv->getAmount() < 32)) {
    313                     if (LLVM_UNLIKELY(variables.isNonZero(adv->getExpression()))) {
    314                         variables.addNonZero(adv);
    315                     }
    316                 }
    317             }
    318         }
    319 
    320         stmt = stmt->getNextNode();
    321     }
    322 
    323     // If this block has a branch statement leading into it, we can verify whether an escaped value
    324     // was updated within this block and update the preceeding block's variable state appropriately.
    325 
    326     if (Branch * const br = block->getBranch()) {
    327 
    328         // When removing identical escaped values, we have to consider that the identical Vars could
    329         // be assigned new differing values later in the outer body. Thus instead of replacing them
    330         // directly, we map future uses of the duplicate Var to the initial one. The DCE pass will
    331         // later mark any Assign statement as dead if the Var is never read.
    332 
    333         /// TODO: this doesn't properly optimize the loop control variable(s) yet.
    334 
    335         const auto escaped = br->getEscaped();
    336         const auto n = escaped.size();
    337         PabloAST * variable[n];
    338         PabloAST * incoming[n];
    339         PabloAST * outgoing[n];
    340 
    341         for (unsigned i = 0; i < escaped.size(); ++i) {
    342             PabloAST * var = escaped[i];
    343             incoming[i] = vt->get(var);
    344             outgoing[i] = variables.get(var);
    345             if (LLVM_UNLIKELY(incoming[i] == outgoing[i])) {
    346                 var = incoming[i];
    347             } else {
    348                 for (size_t j = 0; j != i; ++j) {
    349                     if ((outgoing[j] == outgoing[i]) && (incoming[j] == incoming[i])) {
    350                         var = variable[j];
    351                         break;
    352                     }
    353                 }
    354             }
    355             variable[i] = var;
    356             vt->put(escaped[i], var);
    357         }
    358     }
    359 }
    360 
    361 /** ------------------------------------------------------------------------------------------------------------- *
    362  * @brief deadCodeElimination
    363  ** ------------------------------------------------------------------------------------------------------------- */
    364 void deadCodeElimination(PabloBlock * const block) {
    365 
    366     flat_map<PabloAST *, Assign *> unread;
    367 
    368     Statement * stmt = block->front();
    369     while (stmt) {
    370         if (unread.size() != 0) {
    371             for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
    372                 PabloAST * const op = stmt->getOperand(i);
    373                 if (LLVM_UNLIKELY(isa<Var>(op))) {
    374                     unread.erase(op);
    375                 }
    376             }
    377         }
    378         if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
    379             Branch * const br = cast<Branch>(stmt);
    380             deadCodeElimination(br->getBody());
    381             if (LLVM_UNLIKELY(br->getEscaped().empty())) {
    382                 stmt = stmt->eraseFromParent(true);
    383                 continue;
    384             }
    385         } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
    386             // An Assign statement is locally dead whenever its variable is not read
    387             // before being reassigned a value.
    388             PabloAST * var = cast<Assign>(stmt)->getVariable();
    389             auto f = unread.find(var);
    390             if (f != unread.end()) {
    391                 auto prior = f->second;
    392                 prior->eraseFromParent(true);
    393                 f->second = cast<Assign>(stmt);
    394             } else {
    395                 unread.emplace(var, cast<Assign>(stmt));
    396             }
    397         } else if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
    398             stmt = stmt->eraseFromParent(true);
    399             continue;
    400         }
    401         stmt = stmt->getNextNode();
    402     }
    403 }
    404 
    405 /** ------------------------------------------------------------------------------------------------------------- *
    406  * @brief deadCodeElimination
    407  ** ------------------------------------------------------------------------------------------------------------- */
    408 void deadCodeElimination(PabloKernel * kernel) {
    409 
    410     deadCodeElimination(kernel->getEntryBlock());
    411 
    412     for (unsigned i = 0; i < kernel->getNumOfVariables(); ++i) {
    413         Var * var = kernel->getVariable(i);
    414         bool unused = true;
    415         for (PabloAST * user : var->users()) {
    416             if (isa<Assign>(user)) {
    417                 if (cast<Assign>(user)->getValue() == var) {
    418                     unused = false;
    419                     break;
    420                 }
    421             } else {
    422                 unused = false;
    423                 break;
    424             }
    425         }
    426         if (LLVM_UNLIKELY(unused)) {
    427             for (PabloAST * user : var->users()) {
    428                 cast<Assign>(user)->eraseFromParent(true);
    429             }
    430         }
    431     }
    432 
     446 * @brief isNonZero
     447 ** ------------------------------------------------------------------------------------------------------------- */
     448bool isNonZero(const PabloAST * const expr) const {
     449    return isa<Ones>(expr) || std::find(mNonZero.begin(), mNonZero.end(), expr) != mNonZero.end();
    433450}
    434451
     
    503520
    504521/** ------------------------------------------------------------------------------------------------------------- *
     522 * @brief deadCodeElimination
     523 ** ------------------------------------------------------------------------------------------------------------- */
     524void deadCodeElimination(PabloBlock * const block) {
     525
     526    flat_set<PabloAST *> written;
     527
     528    for (Statement * stmt = block->back(), * prior; stmt; stmt = prior) {
     529        prior = stmt->getPrevNode();
     530        if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
     531            if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     532                written.clear();
     533                deadCodeElimination(cast<Branch>(stmt)->getBody());
     534            } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     535                // An Assign statement is locally dead whenever its variable is not read
     536                // before being reassigned a value.
     537                PabloAST * var = cast<Assign>(stmt)->getVariable();
     538                if (LLVM_UNLIKELY(!written.insert(var).second)) {
     539                    stmt->eraseFromParent();
     540                }
     541            } else {
     542                stmt->eraseFromParent();
     543            }
     544        }
     545    }
     546}
     547
     548std::vector<const PabloAST *>       mNonZero;
     549std::vector<const PabloBlock *>     mInScope;
     550
     551};
     552
     553/** ------------------------------------------------------------------------------------------------------------- *
    505554 * @brief optimize
    506555 ** ------------------------------------------------------------------------------------------------------------- */
    507556bool Simplifier::optimize(PabloKernel * kernel) {
    508     redundancyElimination(kernel->getEntryBlock(), nullptr, nullptr);
    509     strengthReduction(kernel->getEntryBlock());
    510     deadCodeElimination(kernel);
     557    PassContainer pc;
     558    pc.run(kernel);
    511559    #ifndef NDEBUG
    512560    PabloVerifier::verify(kernel, "post-simplification");
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r5510 r5620  
    4040using TypeId = PabloAST::ClassTypeId;
    4141
    42 inline static unsigned getAlignment(const Value * const ptr) {
    43     return ptr->getType()->getPrimitiveSizeInBits() / 8;
     42inline static unsigned getAlignment(const Value * const type) {
     43    return type->getType()->getPrimitiveSizeInBits() / 8;
    4444}
    4545
     
    4848}
    4949
    50 void PabloCompiler::initializeKernelData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder) {
     50void PabloCompiler::initializeKernelData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
    5151    assert ("PabloCompiler does not have a IDISA iBuilder" && iBuilder);
     52    mBranchCount = 0;
    5253    examineBlock(iBuilder, mKernel->getEntryBlock());
    5354    mCarryManager->initializeCarryData(iBuilder, mKernel);
    54 }
    55 
    56 void PabloCompiler::releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder) {
     55    if (CompileOptionIsSet(PabloCompilationFlags::EnableProfiling)) {
     56        const auto count = (mBranchCount * 2) + 1;
     57        mKernel->addScalar(ArrayType::get(mKernel->getSizeTy(), count), "profile");
     58        mBasicBlock.reserve(count);
     59    }
     60}
     61
     62void PabloCompiler::releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
    5763    assert ("PabloCompiler does not have a IDISA iBuilder" && iBuilder);
    5864    mCarryManager->releaseCarryData(iBuilder);
    5965}
    6066
    61 void PabloCompiler::compile(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder) {
     67void PabloCompiler::compile(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
    6268    assert ("PabloCompiler does not have a IDISA iBuilder" && iBuilder);
    6369    mCarryManager->initializeCodeGen(iBuilder);
     
    6571    mMarker.emplace(entryBlock->createZeroes(), iBuilder->allZeroes());
    6672    mMarker.emplace(entryBlock->createOnes(), iBuilder->allOnes());
     73    mBranchCount = 0;
     74    addBranchCounter(iBuilder);
    6775    compileBlock(iBuilder, entryBlock);
    6876    mCarryManager->finalizeCodeGen(iBuilder);
    6977}
    7078
    71 void PabloCompiler::examineBlock(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const block) {
     79void PabloCompiler::examineBlock(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const block) {
    7280    for (const Statement * stmt : *block) {
    7381        if (LLVM_UNLIKELY(isa<Lookahead>(stmt))) {
     
    7886            }
    7987        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     88            ++mBranchCount;
    8089            examineBlock(iBuilder, cast<Branch>(stmt)->getBody());
    8190        } else if (LLVM_UNLIKELY(isa<Count>(stmt))) {
     
    8594}
    8695
    87 inline void PabloCompiler::compileBlock(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const block) {
     96void PabloCompiler::addBranchCounter(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
     97    if (CompileOptionIsSet(PabloCompilationFlags::EnableProfiling)) {       
     98        Value * ptr = iBuilder->getScalarFieldPtr("profile");
     99        assert (mBasicBlock.size() < ptr->getType()->getPointerElementType()->getArrayNumElements());
     100        ptr = iBuilder->CreateGEP(ptr, {iBuilder->getInt32(0), iBuilder->getInt32(mBasicBlock.size())});
     101        const auto alignment = getPointerElementAlignment(ptr);
     102        Value * value = iBuilder->CreateAlignedLoad(ptr, alignment, false, "branchCounter");
     103        value = iBuilder->CreateAdd(value, ConstantInt::get(cast<IntegerType>(value->getType()), 1));
     104        iBuilder->CreateAlignedStore(value, ptr, alignment);
     105        mBasicBlock.push_back(iBuilder->GetInsertBlock());
     106    }
     107}
     108
     109inline void PabloCompiler::compileBlock(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const block) {
    88110    for (const Statement * statement : *block) {
    89111        compileStatement(iBuilder, statement);
     
    91113}
    92114
    93 void PabloCompiler::compileIf(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const If * const ifStatement) {
     115void PabloCompiler::compileIf(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const If * const ifStatement) {
    94116    //
    95117    //  The If-ElseZero stmt:
     
    111133
    112134    BasicBlock * const ifEntryBlock = iBuilder->GetInsertBlock();
    113     BasicBlock * const ifBodyBlock = iBuilder->CreateBasicBlock("if.body");
    114     BasicBlock * const ifEndBlock = iBuilder->CreateBasicBlock("if.end");
     135    ++mBranchCount;
     136    BasicBlock * const ifBodyBlock = iBuilder->CreateBasicBlock("if.body_" + std::to_string(mBranchCount));
     137    BasicBlock * const ifEndBlock = iBuilder->CreateBasicBlock("if.end_" + std::to_string(mBranchCount));
    115138   
    116139    std::vector<std::pair<const Var *, Value *>> incoming;
     
    156179
    157180    mCarryManager->enterIfBody(iBuilder, ifEntryBlock);
     181
     182    addBranchCounter(iBuilder);
    158183
    159184    compileBlock(iBuilder, ifBody);
     
    209234        phi->addIncoming(outgoing, ifExitBlock);
    210235        f->second = phi;
    211     }   
    212 }
    213 
    214 void PabloCompiler::compileWhile(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const While * const whileStatement) {
     236    }
     237
     238    addBranchCounter(iBuilder);
     239}
     240
     241void PabloCompiler::compileWhile(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const While * const whileStatement) {
    215242
    216243    const PabloBlock * const whileBody = whileStatement->getBody();
     
    243270    mCarryManager->enterLoopScope(iBuilder, whileBody);
    244271
    245     BasicBlock * whileBodyBlock = iBuilder->CreateBasicBlock("while.body");
     272    BasicBlock * whileBodyBlock = iBuilder->CreateBasicBlock("while.body_" + std::to_string(mBranchCount));
     273    BasicBlock * whileEndBlock = iBuilder->CreateBasicBlock("while.end_" + std::to_string(mBranchCount));
     274    ++mBranchCount;
    246275
    247276    iBuilder->CreateBr(whileBodyBlock);
     
    287316
    288317    mCarryManager->enterLoopBody(iBuilder, whileEntryBlock);
     318
     319    addBranchCounter(iBuilder);
    289320
    290321    compileBlock(iBuilder, whileBody);
     
    338369    }
    339370
    340     BasicBlock * whileEndBlock = iBuilder->CreateBasicBlock("while.end");
    341 
    342371    // Terminate the while loop body with a conditional branch back.
    343372    Value * condition = compileExpression(iBuilder, whileStatement->getCondition());
     
    348377    iBuilder->CreateCondBr(condition, whileBodyBlock, whileEndBlock);
    349378
     379    whileEndBlock->moveAfter(whileExitBlock);
     380
    350381    iBuilder->SetInsertPoint(whileEndBlock);
    351382
    352383    mCarryManager->leaveLoopScope(iBuilder, whileEntryBlock, whileExitBlock);
    353384
    354 }
    355 
    356 void PabloCompiler::compileStatement(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const Statement * const stmt) {
     385    addBranchCounter(iBuilder);
     386}
     387
     388void PabloCompiler::compileStatement(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const Statement * const stmt) {
    357389
    358390    if (LLVM_UNLIKELY(isa<If>(stmt))) {
     
    587619}
    588620
    589 Value * PabloCompiler::compileExpression(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloAST * expr, const bool ensureLoaded) const {
     621Value * PabloCompiler::compileExpression(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloAST * expr, const bool ensureLoaded) const {
    590622    if (LLVM_UNLIKELY(isa<Ones>(expr))) {
    591623        return iBuilder->allOnes();
     
    654686PabloCompiler::PabloCompiler(PabloKernel * const kernel)
    655687: mKernel(kernel)
    656 , mCarryManager(new CarryManager) {
     688, mCarryManager(new CarryManager)
     689, mBranchCount(0) {
    657690    assert ("PabloKernel cannot be null!" && kernel);
    658691}
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.h

    r5486 r5620  
    99
    1010#include <unordered_map>
     11#include <vector>
    1112#include <memory>
    1213namespace IDISA { class IDISA_Builder; }
     14namespace llvm { class BasicBlock; }
    1315namespace llvm { class Function; }
    1416namespace llvm { class Value; }
     
    3840protected:
    3941
    40     void initializeKernelData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
     42    void initializeKernelData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
    4143
    42     void compile(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
     44    void compile(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
    4345
    44     void releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
     46    void releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
    4547
    4648private:
    4749
    48     void examineBlock(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const block);
     50    void examineBlock(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const block);
    4951
    50     void compileBlock(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const block);
     52    void compileBlock(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const block);
    5153
    52     void compileStatement(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const Statement * stmt);
     54    void compileStatement(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const Statement * stmt);
    5355
    54     void compileIf(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const If * ifStmt);
     56    void compileIf(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const If * ifStmt);
    5557
    56     void compileWhile(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const While * whileStmt);
     58    void compileWhile(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const While * whileStmt);
    5759
    58     llvm::Value * compileExpression(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloAST * expr, const bool ensureLoaded = true) const;
     60    void addBranchCounter(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
     61
     62    llvm::Value * compileExpression(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloAST * expr, const bool ensureLoaded = true) const;
    5963
    6064private:
     
    6468    TranslationMap                  mMarker;
    6569    TranslationMap                  mAccumulator;
    66 
     70    unsigned                        mBranchCount;
     71    std::vector<llvm::BasicBlock *> mBasicBlock;
    6772};
    6873
  • icGREP/icgrep-devel/icgrep/pablo/pablo_kernel.cpp

    r5493 r5620  
    1313#include <kernels/kernel_builder.h>
    1414#include <llvm/IR/Module.h>
     15
     16#include <pablo/branch.h>
     17#include <sys/stat.h>
     18#include <fcntl.h>
     19#include <llvm/Support/raw_ostream.h>
    1520
    1621using namespace kernel;
     
    149154void PabloKernel::generateFinalizeMethod(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
    150155    mPabloCompiler->releaseKernelData(iBuilder);
     156
     157    if (CompileOptionIsSet(PabloCompilationFlags::EnableProfiling)) {
     158
     159
     160        Value * fd = iBuilder->CreateOpenCall(iBuilder->GetString("./" + getName() + ".profile"),
     161                                              iBuilder->getInt32(O_WRONLY | O_CREAT | O_TRUNC),
     162                                              iBuilder->getInt32(S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH));
     163
     164        Function * dprintf = iBuilder->GetDprintf();
     165
     166
     167
     168        Value * profile = iBuilder->getScalarFieldPtr("profile");
     169
     170
     171        unsigned branchCount = 0;
     172
     173        for (const auto bb : mPabloCompiler->mBasicBlock) {
     174
     175            std::string tmp;
     176            raw_string_ostream str(tmp);
     177            str << "%lu\t";
     178            str << bb->getName();
     179            str << "\n";
     180
     181            Value * taken = iBuilder->CreateLoad(iBuilder->CreateGEP(profile, {iBuilder->getInt32(0), iBuilder->getInt32(branchCount++)}));
     182            iBuilder->CreateCall(dprintf, {fd, iBuilder->GetString(str.str()), taken});
     183
     184        }
     185
     186//        Value * base = iBuilder->CreateLoad(iBuilder->CreateGEP(profile, {iBuilder->getInt32(0), iBuilder->getInt32(0)}));
     187//        base = iBuilder->CreateUIToFP(base, iBuilder->getDoubleTy());
     188
     189//        unsigned branchCount = 0;
     190//        std::function<void (const PabloBlock *)> writeProfile = [&](const PabloBlock * const scope) {
     191//            for (const Statement * stmt : *scope) {
     192//                if (isa<Branch>(stmt)) {
     193
     194//                    ++branchCount;
     195
     196//                    std::string tmp;
     197//                    raw_string_ostream str(tmp);
     198//                    str << "%3.3f\t";
     199//                    str << mPabloCompiler->getBranchEntry(branchCount)->getName();
     200//                    str << "\n";
     201
     202//                    Value * branches = iBuilder->CreateLoad(iBuilder->CreateGEP(profile, {iBuilder->getInt32(0), iBuilder->getInt32(branchCount)}));
     203//                    branches = iBuilder->CreateUIToFP(branches, iBuilder->getDoubleTy());
     204//                    Value * prob = iBuilder->CreateFDiv(branches, base);
     205//                    iBuilder->CreateCall(dprintf, {fd, iBuilder->GetString(str.str()), prob});
     206
     207//                    writeProfile(cast<Branch>(stmt)->getBody());
     208
     209//                }
     210//            }
     211//        };
     212
     213//        writeProfile(getEntryBlock());
     214        iBuilder->CreateCloseCall(fd);
     215    }
     216
    151217}
    152218
     
    163229}
    164230
    165 static inline std::string annotateKernelNameWithDebugFlags(std::string && name) {
     231static inline std::string && annotateKernelNameWithDebugFlags(std::string && name) {
    166232    if (DebugOptionIsSet(DumpTrace)) {
    167233        name += "_DumpTrace";
    168234    }
    169     return name;
     235    if (CompileOptionIsSet(EnableProfiling)) {
     236        name += "_BranchProfiling";
     237    }
     238    return std::move(name);
    170239}
    171240
  • icGREP/icgrep-devel/icgrep/pablo/pablo_toolchain.cpp

    r5562 r5620  
    3333                        clEnumVal(ShowOptimizedPablo, "Print optimizeed Pablo code"),
    3434                        clEnumVal(VerifyPablo, "Run the Pablo verifier"),
    35                         clEnumVal(DumpTrace, "Generate dynamic traces of executed Pablo assignments."),
     35                        clEnumVal(DumpTrace, "Generate dynamic traces of executed Pablo assignments."),                       
    3636                        clEnumValEnd), cl::cat(PabloOptions));
    3737   
     
    4242    PabloOptimizationsOptions(cl::values(clEnumVal(DisableSimplification, "Disable Pablo Simplification pass (not recommended)"),
    4343                                         clEnumVal(DisableCodeMotion, "Moves statements into the innermost legal If-scope and moves invariants out of While-loops."),
    44                                          clEnumVal(EnableDistribution, "Apply distribution law optimization."),
    45 
     44                                         clEnumVal(EnableDistribution, "Apply distribution law optimization."),                                         
    4645                                         clEnumVal(EnableSchedulingPrePass, "Pablo Statement Scheduling Pre-Pass"),
     46                                         clEnumVal(EnableProfiling, "Profile branch statistics."),
    4747                                         clEnumValEnd), cl::cat(PabloOptions));
    4848
    49 bool DebugOptionIsSet(PabloDebugFlags flag) {return DebugOptions.isSet(flag);}
     49bool DebugOptionIsSet(const PabloDebugFlags flag) {return DebugOptions.isSet(flag);}
    5050   
     51bool CompileOptionIsSet(const PabloCompilationFlags flag) {return PabloOptimizationsOptions.isSet(flag);}
    5152
    5253void pablo_function_passes(PabloKernel * kernel) {
     
    6768
    6869    // Scan through the pablo code and perform DCE and CSE
     70    if (Flatten){
     71        FlattenIf::transform(kernel);
     72    }
    6973    if (LLVM_LIKELY(!PabloOptimizationsOptions.isSet(DisableSimplification))) {
    7074        Simplifier::optimize(kernel);
    7175    }
    72     if (Flatten){
    73         FlattenIf::transform(kernel);
     76    if (PabloOptimizationsOptions.isSet(EnableDistribution)) {
     77        DistributivePass::optimize(kernel);
    7478    }
    7579    if (LLVM_LIKELY(!PabloOptimizationsOptions.isSet(DisableCodeMotion))) {
    7680        CodeMotionPass::optimize(kernel);
    77     }
    78     if (PabloOptimizationsOptions.isSet(EnableDistribution)) {
    79         DistributivePass::optimize(kernel);
    8081    }
    8182    if (PabloOptimizationsOptions.isSet(EnableSchedulingPrePass)) {
  • icGREP/icgrep-devel/icgrep/pablo/pablo_toolchain.h

    r5562 r5620  
    1818
    1919enum PabloCompilationFlags {
    20     DisableSimplification, DisableCodeMotion, EnableDistribution, EnableSchedulingPrePass
     20    DisableSimplification, DisableCodeMotion, EnableDistribution, EnableSchedulingPrePass, EnableProfiling
    2121};
    2222   
    2323const llvm::cl::OptionCategory * pablo_toolchain_flags();
    2424
    25 bool DebugOptionIsSet(PabloDebugFlags flag);
     25bool DebugOptionIsSet(const PabloDebugFlags flag);
     26
     27bool CompileOptionIsSet(const PabloCompilationFlags flag);
    2628
    2729void pablo_function_passes(PabloKernel * kernel);
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r5617 r5620  
    7272   
    7373MarkerType RE_Compiler::compile_local(RE * re, MarkerType marker, PabloBuilder & pb) {
    74     UCD::UnicodeSet* first = RE_Local::first(re);
    75     PabloAST * pablo_first = mCCCompiler.compileCC(makeCC(std::move(*first)));
    76     UCD::UnicodeSet* final = RE_Local::final(re);
    77     PabloAST * pablo_final = mCCCompiler.compileCC(makeCC(std::move(*final)));
    78     std::map<UCD::UnicodeSet*, UCD::UnicodeSet*> follow_map;
    79     RE_Local::follow(re, follow_map);
     74    CC * first = RE_Local::first(re);
     75    CC * final = RE_Local::final(re);
    8076
    8177    if (first == nullptr || final == nullptr) {
     
    8379        return process(re, marker, pb);
    8480    }
     81
     82    PabloAST * pablo_first = mCCCompiler.compileCC(first);
     83    PabloAST * pablo_final = mCCCompiler.compileCC(final);
     84    std::map<CC*, CC*> follow_map;
     85    RE_Local::follow(re, follow_map);
    8586
    8687    PabloAST * pablo_follow = pb.createZeroes();
  • icGREP/icgrep-devel/icgrep/re/re_local.cpp

    r5619 r5620  
    113113}
    114114
    115 void RE_Local::follow(RE * re, std::map<UCD::UnicodeSet*, UCD::UnicodeSet*> &follow_map) {
     115void RE_Local::follow(RE * re, std::map<CC *, CC*> &follow_map) {
    116116    if (Name * name = dyn_cast<Name>(re)) {
    117117        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
     
    122122    } else if (Seq * seq = dyn_cast<Seq>(re)) {
    123123        RE * re_first = *(seq->begin());
    124         std::vector<RE *> list;
    125         list.reserve(seq->size());
    126         for (auto i = seq->begin() + 1; i != seq->end(); i++) {
    127             list.push_back(*i);
    128         }
    129         RE * re_follow = makeSeq(list.begin(), list.end());
     124        RE * re_follow = makeSeq(seq->begin() + 1, seq->end());
    130125        auto e1 = final(re_first);
    131126        auto e2 = first(re_follow);
     
    133128            auto e = follow_map.find(e1);
    134129            if (e != follow_map.end()) {
    135                 *(e->second) = *(e->second) + *e2;
     130                e->second = makeCC(e->second, e2);
    136131            } else {
    137                 follow_map.insert(std::pair<UCD::UnicodeSet*, UCD::UnicodeSet*>(e1, e2));
     132                follow_map.emplace(e1, e2);
    138133            }
    139134        }
    140135        follow(re_first, follow_map);
    141136        follow(re_follow, follow_map);
    142         return;
    143137    } else if (Alt * alt = dyn_cast<Alt>(re)) {
    144138        for (auto ai = alt->begin(); ai != alt->end(); ++ai) {
    145139            follow(*ai, follow_map);
    146140        }
    147         return;
    148141    } else if (Rep * rep = dyn_cast<Rep>(re)) {
    149142        auto e1 = final(rep->getRE());
     
    152145            auto e = follow_map.find(e1);
    153146            if (e != follow_map.end()) {
    154                 *(e->second) = *(e->second) + *e2;
     147                e->second = makeCC(e->second, e2);
    155148            } else {
    156                 follow_map.insert(std::pair<UCD::UnicodeSet*, UCD::UnicodeSet*>(e1, e2));
     149                follow_map.emplace(e1, e2);
    157150            }
    158151        }
    159152        follow(rep->getRE(), follow_map);
    160         return;
    161     }
    162     return;
     153    }
    163154}
    164155
  • icGREP/icgrep-devel/icgrep/re/re_local.h

    r5619 r5620  
    1313    static CC * first(RE * re);
    1414    static CC * final(RE * re);
    15         static void follow(RE * re, std::map<UCD::UnicodeSet*, UCD::UnicodeSet*> &follow_map);
     15    static void follow(RE * re, std::map<CC*, CC*> &follow_map);
    1616        static bool isLocalLanguage(RE * re);
    1717private:
  • icGREP/icgrep-devel/icgrep/re/re_multiplex.cpp

    r5619 r5620  
    1616#include <sstream>
    1717#include <iostream>
     18#include <functional>
    1819
    1920using namespace boost::container;
     
    3132}
    3233
    33 Memoizer                mMemoizer_multiplex;
    34    
    3534RE * multiplex(RE * const re,
    3635               const std::vector<UCD::UnicodeSet> & UnicodeSets,
    37                const std::vector<std::vector<unsigned>> & exclusiveSetIDs,
    38                const std::vector<UCD::UnicodeSet> & multiplexedCCs) {
    39     if (Name * name = dyn_cast<Name>(re)) {
    40         auto f = mMemoizer_multiplex.find(name);
    41         if (f == mMemoizer_multiplex.end()) {
    42             if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
    43                 if (CC * cc = dyn_cast<CC>(name->getDefinition())) {
    44                     UCD::UnicodeSet * sets = cast<UCD::UnicodeSet>(cc);
    45                     auto index = find(UnicodeSets.begin(), UnicodeSets.end(), *sets) - UnicodeSets.begin();
    46                     auto exclusive_IDs = exclusiveSetIDs[index];
    47                     CC * CC_union = makeCC();
    48                     for (auto i : exclusive_IDs) {
    49                         CC_union = makeCC(CC_union, makeCC(i));
     36               const std::vector<std::vector<unsigned>> & exclusiveSetIDs) {
     37
     38    Memoizer memoizer;
     39
     40    std::function<RE *(RE *)> multiplex = [&](RE * const re) -> RE * {
     41        if (Name * name = dyn_cast<Name>(re)) {
     42            auto f = memoizer.find(name);
     43            if (f == memoizer.end()) {
     44                if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
     45                    if (CC * cc = dyn_cast<CC>(name->getDefinition())) {
     46                        UCD::UnicodeSet * sets = cast<UCD::UnicodeSet>(cc);
     47                        auto index = find(UnicodeSets.begin(), UnicodeSets.end(), *sets) - UnicodeSets.begin();
     48                        auto exclusive_IDs = exclusiveSetIDs[index];
     49                        CC * CC_union = makeCC();
     50                        for (auto i : exclusive_IDs) {
     51                            CC_union = makeCC(CC_union, makeCC(i));
     52                        }
     53                        name->setDefinition(CC_union);
     54                    } else {
     55                        multiplex(name->getDefinition());
    5056                    }
    51                     name->setDefinition(CC_union);
    5257                } else {
    53                     multiplex(name->getDefinition(), UnicodeSets, exclusiveSetIDs, multiplexedCCs);
     58                    throw std::runtime_error("All non-unicode-property Name objects should have been defined prior to Unicode property resolution.");
    5459                }
     60                return memoizer.memoize(name);
    5561            } else {
    56                 throw std::runtime_error("All non-unicode-property Name objects should have been defined prior to Unicode property resolution.");
     62                return *f;
    5763            }
    58             mMemoizer_multiplex.memoize(name);
    59             return name;
    60         } else {
    61             return *f;
    62         }
    63     } else if (Seq * seq = dyn_cast<Seq>(re)) {
    64         for (auto si = seq->begin(); si != seq->end(); ++si) {
    65             *si = multiplex(*si, UnicodeSets, exclusiveSetIDs, multiplexedCCs);
    66         }
    67     } else if (Alt * alt = dyn_cast<Alt>(re)) {
    68         CC * unionCC = nullptr;
    69         std::stringstream name;
    70         for (auto ai = alt->begin(); ai != alt->end(); ) {
    71             RE * re = multiplex(*ai, UnicodeSets, exclusiveSetIDs, multiplexedCCs);
    72             if (CC * cc = extractCC(re)) {
    73                 if (unionCC == nullptr) {
    74                     unionCC = cc;
     64        } else if (Seq * seq = dyn_cast<Seq>(re)) {
     65            for (auto si = seq->begin(); si != seq->end(); ++si) {
     66                *si = multiplex(*si);
     67            }
     68        } else if (Alt * alt = dyn_cast<Alt>(re)) {
     69            CC * unionCC = nullptr;
     70            std::stringstream name;
     71            for (auto ai = alt->begin(); ai != alt->end(); ) {
     72                RE * re = multiplex(*ai);
     73                if (CC * cc = extractCC(re)) {
     74                    if (unionCC == nullptr) {
     75                        unionCC = cc;
     76                    } else {
     77                        unionCC = makeCC(unionCC, cc);
     78                        name << '+';
     79                    }
     80                    if (LLVM_LIKELY(isa<Name>(re))) {
     81                        Name * n = cast<Name>(re);
     82                        if (n->hasNamespace()) {
     83                            name << n->getNamespace() << ':';
     84                        }
     85                        name << n->getName();
     86                    } else if (isa<CC>(re)) {
     87                        name << cast<CC>(re)->canonicalName(UnicodeClass);
     88                    }
     89                    ai = alt->erase(ai);
    7590                } else {
    76                     unionCC = makeCC(unionCC, cc);
    77                     name << '+';
     91                    *ai++ = re;
    7892                }
    79                 if (LLVM_LIKELY(isa<Name>(re))) {
    80                     Name * n = cast<Name>(re);
    81                     if (n->hasNamespace()) {
    82                         name << n->getNamespace() << ':';
    83                     }
    84                     name << n->getName();
    85                 } else if (isa<CC>(re)) {
    86                     name << cast<CC>(re)->canonicalName(UnicodeClass);
    87                 }
    88                 ai = alt->erase(ai);
    89             } else {
    90                 *ai++ = re;
     93            }
     94            if (unionCC) {
     95                alt->push_back(multiplex(makeName(name.str(), unionCC)));
     96            }
     97            if (alt->size() == 1) {
     98                return alt->front();
     99            }
     100        } else if (Rep * rep = dyn_cast<Rep>(re)) {
     101            rep->setRE(multiplex(rep->getRE()));
     102        } else if (Assertion * a = dyn_cast<Assertion>(re)) {
     103            a->setAsserted(multiplex(a->getAsserted()));
     104        } else if (Diff * diff = dyn_cast<Diff>(re)) {
     105            diff->setLH(multiplex(diff->getLH()));
     106            diff->setRH(multiplex(diff->getRH()));
     107            CC * lh = extractCC(diff->getLH());
     108            CC * rh = extractCC(diff->getRH());
     109            if (lh && rh) {
     110                return multiplex(makeName("diff", subtractCC(lh, rh)));
     111            }
     112        } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
     113            ix->setLH(multiplex(ix->getLH()));
     114            ix->setRH(multiplex(ix->getRH()));
     115            CC * lh = extractCC(ix->getLH());
     116            CC * rh = extractCC(ix->getRH());
     117            if (lh && rh) {
     118                return multiplex(makeName("intersect", intersectCC(lh, rh)));
    91119            }
    92120        }
    93         if (unionCC) {
    94             alt->push_back(multiplex(makeName(name.str(), unionCC), UnicodeSets, exclusiveSetIDs, multiplexedCCs));
    95         }
    96         if (alt->size() == 1) {
    97             return alt->front();
    98         }
    99     } else if (Rep * rep = dyn_cast<Rep>(re)) {
    100         rep->setRE(multiplex(rep->getRE(), UnicodeSets, exclusiveSetIDs, multiplexedCCs));
    101     } else if (Assertion * a = dyn_cast<Assertion>(re)) {
    102         a->setAsserted(multiplex(a->getAsserted(), UnicodeSets, exclusiveSetIDs, multiplexedCCs));
    103     } else if (Diff * diff = dyn_cast<Diff>(re)) {
    104         diff->setLH(multiplex(diff->getLH(), UnicodeSets, exclusiveSetIDs, multiplexedCCs));
    105         diff->setRH(multiplex(diff->getRH(), UnicodeSets, exclusiveSetIDs, multiplexedCCs));
    106         CC * lh = extractCC(diff->getLH());
    107         CC * rh = extractCC(diff->getRH());
    108         if (lh && rh) {
    109             return multiplex(makeName("diff", subtractCC(lh, rh)), UnicodeSets, exclusiveSetIDs, multiplexedCCs);
    110         }
    111     } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
    112         ix->setLH(multiplex(ix->getLH(), UnicodeSets, exclusiveSetIDs, multiplexedCCs));
    113         ix->setRH(multiplex(ix->getRH(), UnicodeSets, exclusiveSetIDs, multiplexedCCs));
    114         CC * lh = extractCC(ix->getLH());
    115         CC * rh = extractCC(ix->getRH());
    116         if (lh && rh) {
    117             return multiplex(makeName("intersect", intersectCC(lh, rh)), UnicodeSets, exclusiveSetIDs, multiplexedCCs);
    118         }
    119     }
    120     return re;
     121        return re;
     122    };
     123
     124    return multiplex(re);
    121125}   
    122126
  • icGREP/icgrep-devel/icgrep/re/re_multiplex.h

    r5619 r5620  
    99    class Name;
    1010
    11     RE * multiplex(RE * const re, const std::vector<UCD::UnicodeSet> & UnicodeSets,
    12                     const std::vector<std::vector<unsigned>> & exclusiveSetIDs,
    13                     const std::vector<UCD::UnicodeSet> & multiplexedCCs);
     11    RE * multiplex(RE * const re,
     12                   const std::vector<UCD::UnicodeSet> & UnicodeSets,
     13                   const std::vector<std::vector<unsigned>> & exclusiveSetIDs);
    1414
    1515}
  • icGREP/icgrep-devel/icgrep/re/re_parser.cpp

    r5558 r5620  
    3232#include <llvm/Support/Casting.h>
    3333#include <llvm/Support/ErrorHandling.h>
     34#include <llvm/Support/raw_ostream.h>
    3435
    3536using namespace llvm;
     
    4344
    4445RE * RE_Parser::parse(const std::string & regular_expression, ModeFlagSet initialFlags, RE_Syntax syntax, bool ByteMode) {
     46
    4547    std::unique_ptr<RE_Parser> parser = nullptr;
    4648    switch (syntax) {
  • icGREP/icgrep-devel/icgrep/re/re_toolchain.cpp

    r5617 r5620  
    1616#include <re/re_analysis.h>
    1717#include <iostream>
     18#include <llvm/Support/raw_ostream.h>
    1819
    1920using namespace pablo;
Note: See TracChangeset for help on using the changeset viewer.