Changeset 5581


Ignore:
Timestamp:
Jul 28, 2017, 12:02:56 PM (3 weeks ago)
Author:
nmedfort
Message:

Optimization to UCD Compiler to make use of multiple assignments for Vars.

Location:
icGREP/icgrep-devel/icgrep/UCD
Files:
2 edited

Legend:

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

    r5558 r5581  
    1010#include <pablo/pe_ones.h>
    1111
     12#include <pablo/printer_pablos.h>
     13#include <llvm/Support/raw_ostream.h>
     14
    1215using namespace cc;
    1316using namespace re;
    1417using namespace pablo;
    1518using namespace llvm;
     19using namespace boost::container;
    1620
    1721namespace UCD {
     
    160164    }
    161165
     166    for (auto & f : mTargetValue) {
     167        const auto v = mTarget.find(f.first);
     168        assert (v != mTarget.end());
     169        PabloAST * value = f.second;
     170        if (!isa<Zeroes>(value)) {
     171            if (LLVM_LIKELY(builder.getParent() != nullptr)) {
     172                value = builder.createOr(v->second, value);
     173            }
     174            builder.createAssign(v->second, value);
     175            f.second = builder.createZeroes();
     176        }
     177    }
     178
    162179    const auto outer = outerRanges(enclosed);
    163180    const auto inner = innerRanges(enclosed);
     181
     182    Values nonIntersectingTargets;
     183
    164184    for (const auto range : outer) {
    165 
    166         TargetVector intersectingTargets;
    167         TargetVector nonIntersectingTargets;
    168185
    169186        // Split our current target list into two sets: the intersecting and non-intersecting ones. Any non-
     
    173190        // inner value with the outer value.
    174191
    175         for (auto ti = mTargetMap.begin(); ti != mTargetMap.end(); ) {           
    176             if (ti->first->intersects(range.first, range.second)) {
    177                 intersectingTargets.emplace_back(ti->first, ti->second);
    178                 ++ti;
     192        for (auto f = mTargetValue.begin(); f != mTargetValue.end(); ) {
     193            if (f->first->intersects(range.first, range.second)) {
     194                ++f;
    179195            } else {
    180                 nonIntersectingTargets.emplace_back(ti->first, ti->second);
    181                 ti = mTargetMap.erase(ti);
    182             }
    183         }
    184         if (mTargetMap.size() > 0) {
    185 
     196                nonIntersectingTargets.push_back(*f);
     197                f = mTargetValue.erase(f);
     198            }
     199        }
     200        if (mTargetValue.size() > 0) {
    186201            PabloBuilder inner_block = PabloBuilder::Create(builder);
    187 
     202            builder.createIf(ifTestCompiler(range.first, range.second, builder), inner_block);
    188203            generateRange(inner, range.first, range.second, inner_block);
    189 
    190             for (auto ti = intersectingTargets.begin(); ti != intersectingTargets.end(); ) {
    191                 auto f = mTargetMap.find(ti->first);
    192                 assert (f != mTargetMap.end());
    193                 if (LLVM_UNLIKELY(isa<Zeroes>(f->second))) {
    194                     ti = intersectingTargets.erase(ti);
    195                     continue;
    196                 }
    197                 Var * m = builder.createVar("m", builder.createZeroes());
    198                 inner_block.createAssign(m, f->second);
    199                 f->second = m;
    200                 ++ti;
    201             }
    202             // If this range is empty, just skip creating the if block
    203             if (intersectingTargets.size() > 0) {
    204                 builder.createIf(ifTestCompiler(range.first, range.second, builder), inner_block);
    205                 for (const auto ti : intersectingTargets) {
    206                     auto f = mTargetMap.find(ti.first);
    207                     assert (f != mTargetMap.end());
    208                     f->second = builder.createOr(ti.second, f->second);
    209                 }
    210             }
    211         }
    212         for (const Target t : nonIntersectingTargets) {
    213             mTargetMap.emplace(t.first, t.second);
    214         }
     204        }
     205        for (auto t : nonIntersectingTargets) {
     206            mTargetValue.insert(t);
     207        }
     208        nonIntersectingTargets.clear();
    215209    }
    216210}
     
    220214 ** ------------------------------------------------------------------------------------------------------------- */
    221215void UCDCompiler::generateSubRanges(const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder) {
    222     for (auto & t : mTargetMap) {
     216    for (auto & t : mTargetValue) {
    223217        const auto range = rangeIntersect(*t.first, lo, hi);
    224218        PabloAST * target = t.second;
     
    485479 ** ------------------------------------------------------------------------------------------------------------- */
    486480void UCDCompiler::generateWithDefaultIfHierarchy(NameMap & names, PabloBuilder & entry) {
    487     addTargets(entry, names);
     481    makeTargets(entry, names);
    488482    generateRange(defaultIfHierachy, entry);
    489     updateNames(names, entry);
    490 }
    491 
    492 /** ------------------------------------------------------------------------------------------------------------- *
    493  * @brief generateWithDefaultIfHierarchy
    494  ** ------------------------------------------------------------------------------------------------------------- */
    495 PabloAST * UCDCompiler::generateWithDefaultIfHierarchy(const UnicodeSet * set, PabloBuilder & entry) {
    496     // mTargetMap.insert(std::make_pair<const UnicodeSet *, PabloAST *>(set, PabloBlock::createZeroes()));
    497     mTargetMap.emplace(set, entry.createZeroes());
    498     generateRange(defaultIfHierachy, entry);
    499     return mTargetMap.begin()->second;
    500483}
    501484
     
    504487 ** ------------------------------------------------------------------------------------------------------------- */
    505488void UCDCompiler::generateWithoutIfHierarchy(NameMap & names, PabloBuilder & entry) {
    506     addTargets(entry, names);
     489    makeTargets(entry, names);
    507490    generateRange(noIfHierachy, entry);
    508     updateNames(names, entry);
    509 }
    510 
    511 /** ------------------------------------------------------------------------------------------------------------- *
    512  * @brief generateWithoutIfHierarchy
    513  ** ------------------------------------------------------------------------------------------------------------- */
    514 PabloAST * UCDCompiler::generateWithoutIfHierarchy(const UnicodeSet * set, PabloBuilder & entry) {
    515     mTargetMap.emplace(set, entry.createZeroes());
    516     generateRange(noIfHierachy, entry);
    517     return mTargetMap.begin()->second;
    518491}
    519492
     
    521494 * @brief addTargets
    522495 ** ------------------------------------------------------------------------------------------------------------- */
    523 inline void UCDCompiler::addTargets(PabloBuilder & entry, const NameMap & names) {
    524     for (const auto t : names) {
    525         if (t.first->getType() == Name::Type::Byte) {
     496inline void UCDCompiler::makeTargets(PabloBuilder & entry, NameMap & names) {
     497
     498    mTargetValue.clear();
     499    mTarget.clear();
     500
     501    struct Comparator {
     502        inline bool operator() (const CC * lh, const CC * rh) const{
     503            return *lh < *rh;
     504        }
     505    } ec;
     506
     507    flat_map<CC *, Var *, Comparator> CCs(ec);
     508
     509    Zeroes * const zeroes = entry.createZeroes();
     510
     511    for (auto & t : names) {
     512        Name * const name = t.first;
     513        if (name->getType() == Name::Type::Byte) {
    526514            continue;
    527         }
    528         if (LLVM_LIKELY(isa<CC>(t.first->getDefinition()))) {
    529             mTargetMap.emplace(cast<CC>(t.first->getDefinition()), t.second ? t.second : entry.createZeroes());
     515        }       
     516        CC * const cc = dyn_cast<CC>(name->getDefinition());
     517        if (cc) {           
     518            const auto f = CCs.find(cc);
     519            if (LLVM_LIKELY(f == CCs.end())) {
     520                PabloAST * const value = t.second ? t.second : zeroes;
     521                mTargetValue.emplace(cc, value);
     522                Var * const var = entry.createVar(name->getName(), value);
     523                mTarget.emplace(cc, var);
     524                CCs.emplace(cc, var);
     525                t.second = var;
     526            } else {
     527                t.second = f->second;
     528            }
    530529        } else {
    531             throw std::runtime_error(t.first->getName() + " is not defined by a CC!");
    532         }
    533     }
    534     assert (mTargetMap.size() > 0);
    535 }
    536 
    537 /** ------------------------------------------------------------------------------------------------------------- *
    538  * @brief updateNames
    539  ** ------------------------------------------------------------------------------------------------------------- */
    540 inline void UCDCompiler::updateNames(NameMap & names, PabloBuilder & entry) {
    541     for (auto & t : names) {
    542         auto f = mTargetMap.find(cast<CC>(t.first->getDefinition()));
    543         if (f != mTargetMap.end()) {
    544             std::string name = t.first->getName();
    545             if (Statement * result = dyn_cast<Statement>(f->second)) {
    546                 result->setName(entry.makeName(name));
    547                 t.second = result;
    548             } else {
    549                 Var * var = entry.createVar(name);
    550                 entry.createAssign(var, f->second);
    551                 t.second = var;
    552             }
    553         }
    554     }
    555     mTargetMap.clear();
     530            report_fatal_error(name->getName() + " is not defined by a CC!");
     531        }
     532    }
    556533}
    557534
  • icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.hpp

    r5160 r5581  
    1717    class PabloBuilder;
    1818    class PabloAST;
     19    class Var;
    1920}
    2021
     
    3031    using codepoint_t = re::codepoint_t;
    3132    using RangeList = std::vector<re::interval_t>;
    32     using TargetMap = boost::container::flat_map<const UnicodeSet *, PabloAST *>;
    33     using Target = std::pair<const UnicodeSet *, PabloAST *>;
    34     using TargetVector = std::vector<Target>;
     33
     34    using TargetMap = boost::container::flat_map<const UnicodeSet *, pablo::Var *>;
     35    using ValueMap = boost::container::flat_map<const UnicodeSet *, PabloAST *>;
     36    using Values = std::vector<std::pair<ValueMap::key_type, ValueMap::mapped_type>>;
    3537
    3638    static const RangeList defaultIfHierachy;
     
    4648
    4749    void generateWithoutIfHierarchy(NameMap & names, PabloBuilder & entry);
    48 
    49     PabloAST * generateWithDefaultIfHierarchy(const UnicodeSet * set, PabloBuilder & entry);
    50 
    51     PabloAST * generateWithoutIfHierarchy(const UnicodeSet * set, PabloBuilder & entry);
    5250
    5351protected:
     
    8078    static RangeList innerRanges(const RangeList & list);
    8179
    82     void addTargets(PabloBuilder & entry, const NameMap & names);
    83 
    84     void updateNames(NameMap & names, PabloBuilder & entry);
     80    void makeTargets(PabloBuilder & entry, NameMap & names);
    8581
    8682private:
    8783    cc::CC_Compiler &       mCharacterClassCompiler;
    8884    PabloAST *              mSuffixVar;
    89     TargetMap               mTargetMap;
     85    TargetMap               mTarget;
     86    ValueMap                mTargetValue;
    9087};
    9188
Note: See TracChangeset for help on using the changeset viewer.