Ignore:
Timestamp:
Nov 5, 2015, 4:41:37 PM (4 years ago)
Author:
nmedfort
Message:

Back up check in. Memory leaks should be fixed.

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

Legend:

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

    r4797 r4860  
    534534/// CONSTRUCTOR
    535535
    536 PabloBlock::PabloBlock(SymbolGenerator & symbolGenerator)
     536PabloBlock::PabloBlock(SymbolGenerator * symbolGenerator)
    537537: PabloAST(PabloAST::ClassTypeId::Block)
    538538, mSymbolGenerator(symbolGenerator)
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4797 r4860  
    5353    }
    5454
    55     inline static PabloBlock & Create(SymbolGenerator & symbolGenerator) {
     55    inline static PabloBlock & Create(SymbolGenerator * symbolGenerator) {
     56        assert (symbolGenerator);
    5657        return *(new PabloBlock(symbolGenerator));
    5758    }
     
    173174
    174175    inline String * getName(const std::string name, const bool generated = true) const {
    175         return mSymbolGenerator.get(name, generated);
     176        return mSymbolGenerator->get(name, generated);
    176177    }
    177178
    178179    inline String * makeName(const std::string prefix, const bool generated = true) const {
    179         return mSymbolGenerator.make(prefix, generated);
     180        return mSymbolGenerator->make(prefix, generated);
    180181    }
    181182
    182183    inline Integer * getInteger(Integer::Type value) {
    183         return mSymbolGenerator.getInteger(value);
     184        return mSymbolGenerator->getInteger(value);
    184185    }
    185186
     
    200201protected:
    201202
    202     PabloBlock(SymbolGenerator & symbolGenerator);
    203 
    204     PabloBlock(PabloBlock * predecessor);
     203    explicit PabloBlock(SymbolGenerator * symbolGenerator);
     204
     205    explicit PabloBlock(PabloBlock * predecessor);
    205206
    206207    PabloAST * renameNonNamedNode(PabloAST * expr, const std::string && prefix);
     
    227228    static Zeroes                                       mZeroes;
    228229    static Ones                                         mOnes;
    229     SymbolGenerator &                                   mSymbolGenerator;
     230    SymbolGenerator *                                   mSymbolGenerator;
    230231    PabloBlock *                                        mParent;
    231232    unsigned                                            mScopeIndex;
  • icGREP/icgrep-devel/icgrep/pablo/function.cpp

    r4726 r4860  
    1616PabloFunction::PabloFunction(std::string && name, const unsigned numOfParameters, const unsigned numOfResults)
    1717: Prototype(ClassTypeId::Function, std::move(name), numOfParameters, numOfResults, nullptr)
     18, mSymbolTable(new SymbolGenerator())
    1819, mEntryBlock(PabloBlock::Create(mSymbolTable))
    1920, mParameters(reinterpret_cast<Var **>(mAllocator.allocate(sizeof(Var *) * numOfParameters)))
     
    3738}
    3839
     40void PabloFunction::operator delete(void * ptr) {
     41    PabloFunction * f = static_cast<PabloFunction *>(ptr);
     42    delete f->mSymbolTable;
     43    f->mSymbolTable = nullptr;
    3944}
     45
     46}
  • icGREP/icgrep-devel/icgrep/pablo/function.h

    r4734 r4860  
    4343        return mFunctionPtr;
    4444    }
    45 
    4645protected:
    4746    Prototype(const PabloAST::ClassTypeId type, std::string && name, const unsigned numOfParameters, const unsigned numOfResults, void * functionPtr);
     
    8988    const PabloBlock & getEntryBlock() const {
    9089        return mEntryBlock;
    91     }
    92 
    93     SymbolGenerator & getSymbolTable() {
    94         return mSymbolTable;
    9590    }
    9691
     
    142137    }
    143138
     139    void operator delete (void*);
     140
    144141    virtual ~PabloFunction() { }
    145142
     
    152149    PabloFunction(std::string && name, const unsigned numOfParameters, const unsigned numOfResults);
    153150private:
    154     PabloBlock &        mEntryBlock;
    155     SymbolGenerator     mSymbolTable;
     151    SymbolGenerator *   mSymbolTable;
     152    PabloBlock &        mEntryBlock;   
    156153    Var ** const        mParameters;
    157154    Assign ** const     mResults;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4808 r4860  
    1313#include <set>
    1414#include <pablo/printer_pablos.h>
     15#include <iostream>
     16#include <llvm/Support/raw_os_ostream.h>
     17#include <boost/graph/strong_components.hpp>
    1518
    1619using namespace boost;
     
    125128}
    126129
    127 inline bool isMutable(const VertexData & data, const PabloBlock &) {
     130inline bool isMutable(const VertexData & data) {
    128131    return getType(data) != TypeId::Var;
    129132}
     
    157160
    158161/** ------------------------------------------------------------------------------------------------------------- *
     162 * @brief printGraph
     163 ** ------------------------------------------------------------------------------------------------------------- */
     164static void printGraph(const Graph & G, const std::string name, raw_ostream & out) {
     165
     166    std::vector<unsigned> c(num_vertices(G));
     167    strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
     168
     169    out << "digraph " << name << " {\n";
     170    for (auto u : make_iterator_range(vertices(G))) {
     171        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     172            continue;
     173        }
     174        out << "v" << u << " [label=\"" << u << ": ";
     175        PabloAST * expr;
     176        TypeId typeId;
     177        std::tie(typeId, expr) = G[u];
     178        bool temporary = false;
     179        bool error = false;
     180        if (expr == nullptr) {
     181            temporary = true;
     182            switch (typeId) {
     183                case TypeId::And:
     184                    out << "And";
     185                    break;
     186                case TypeId::Or:
     187                    out << "Or";
     188                    break;
     189                case TypeId::Xor:
     190                    out << "Xor";
     191                    break;
     192                default:
     193                    out << "???";
     194                    error = true;
     195                    break;
     196            }
     197        } else if (isMutable(G[u])) {
     198            if (LLVM_UNLIKELY(isa<If>(expr))) {
     199                out << "If ";
     200                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
     201                out << ":";
     202            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
     203                out << "While ";
     204                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
     205                out << ":";
     206            } else {
     207                PabloPrinter::print(cast<Statement>(expr), "", out);
     208            }
     209        } else {
     210            PabloPrinter::print(expr, out);
     211        }
     212        out << "\"";
     213        if (!isMutable(G[u])) {
     214            out << " style=dashed";
     215        }
     216        if (error) {
     217            out << " color=red";
     218        } else if (temporary) {
     219            out << " color=blue";
     220        }
     221        out << "];\n";
     222    }
     223    for (auto e : make_iterator_range(edges(G))) {
     224        const auto s = source(e, G);
     225        const auto t = target(e, G);
     226        out << "v" << s << " -> v" << t;
     227        bool cyclic = (c[s] == c[t]);
     228        if (G[e] || cyclic) {
     229            out << " [";
     230             if (G[e]) {
     231                out << "label=\"";
     232                PabloPrinter::print(G[e], out);
     233                out << "\" ";
     234             }
     235             if (cyclic) {
     236                out << "color=red ";
     237             }
     238             out << "]";
     239        }
     240        out << ";\n";
     241    }
     242
     243    if (num_vertices(G) > 0) {
     244
     245        out << "{ rank=same;";
     246        for (auto u : make_iterator_range(vertices(G))) {
     247            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     248                out << " v" << u;
     249            }
     250        }
     251        out << "}\n";
     252
     253        out << "{ rank=same;";
     254        for (auto u : make_iterator_range(vertices(G))) {
     255            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     256                out << " v" << u;
     257            }
     258        }
     259        out << "}\n";
     260
     261    }
     262
     263    out << "}\n\n";
     264    out.flush();
     265}
     266
     267/** ------------------------------------------------------------------------------------------------------------- *
    159268 * @brief optimize
    160269 ** ------------------------------------------------------------------------------------------------------------- */
     
    164273    brp.processScopes(function);   
    165274    #ifndef NDEBUG
    166     Simplifier::deadCodeElimination(function.getEntryBlock());
    167275    PabloVerifier::verify(function, "post-reassociation");
    168276    #endif
     
    228336
    229337/** ------------------------------------------------------------------------------------------------------------- *
    230  * @brief createTree
    231  ** ------------------------------------------------------------------------------------------------------------- */
    232 PabloAST * BooleanReassociationPass::createTree(PabloBlock & block, const Vertex u, Graph & G, const WrittenAt & writtenAt) {
    233     flat_set<PabloAST *> sources;
    234     for (const auto e : make_iterator_range(in_edges(u, G))) {
    235         PabloAST * expr = getValue(G[source(e, G)]);
    236         assert ("G contains a null input variable!" && (expr != nullptr));
    237         sources.insert(expr);
    238     }
    239     circular_buffer<PabloAST *> Q(sources.begin(), sources.end());
    240     // Sort the queue in order of how the inputs were written
    241     std::sort(Q.begin(), Q.end(), [&writtenAt](const PabloAST * const e1, const PabloAST * const e2) -> bool {
    242         const auto f1 = writtenAt.find(e1); assert (f1 != writtenAt.end());
    243         const auto f2 = writtenAt.find(e2); assert (f2 != writtenAt.end());
    244         return f1->second < f2->second;
    245     });
    246 
    247     const TypeId typeId = getType(G[u]);
     338 * @brief writeTree
     339 ** ------------------------------------------------------------------------------------------------------------- */
     340inline void writeTree(PabloBlock & block, const TypeId typeId, circular_buffer<PabloAST *> & Q) {
    248341    while (Q.size() > 1) {
    249         PabloAST * e1 = Q.front(); Q.pop_front();       
     342        PabloAST * e1 = Q.front(); Q.pop_front();
    250343        PabloAST * e2 = Q.front(); Q.pop_front();
    251344        PabloAST * expr = nullptr;
     
    261354        Q.push_back(expr);
    262355    }
     356}
     357
     358/** ------------------------------------------------------------------------------------------------------------- *
     359 * @brief createTree
     360 ** ------------------------------------------------------------------------------------------------------------- */
     361PabloAST * BooleanReassociationPass::createTree(PabloBlock & block, const Vertex u, Graph & G) {
     362
     363    flat_set<PabloAST *> sources;
     364
     365    for (const auto e : make_iterator_range(in_edges(u, G))) {
     366        PabloAST * const expr = getValue(G[source(e, G)]);
     367        assert ("G contains a null input variable!" && (expr != nullptr));
     368        sources.insert(expr);
     369    }
     370
     371    circular_buffer<PabloAST *> Q(sources.size());
     372
     373    for (auto si = sources.begin(); si != sources.end(); ) {
     374        if (inCurrentBlock(*si, block)) {
     375            ++si;
     376        } else { // combine any non-Statements or statements from a preceeding block at the beginning of this block.
     377            Q.push_back(*si);
     378            si = sources.erase(si);
     379        }
     380    }
     381
     382    const TypeId typeId = getType(G[u]);
     383    Statement * current = block.front();
     384    if (Q.size() > 1) {
     385        block.setInsertPoint(nullptr);
     386        writeTree(block, typeId, Q);
     387        current = block.getInsertPoint();
     388    }
     389
     390    unsigned distance = 0;
     391    while (current) {
     392        if (sources.count(current)) {
     393            if (distance > 2) { // write out the current Q
     394                writeTree(block, typeId, Q);
     395            } else {
     396                block.setInsertPoint(current);
     397            }
     398            Q.push_back(current);
     399            distance = 0;
     400        }
     401        ++distance;
     402        current = current->getNextNode();
     403    }
     404    writeTree(block, typeId, Q);
     405    assert (Q.size() == 1);
    263406    PabloAST * const result = Q.front();
    264407    assert (result);
    265408    getValue(G[u]) = result;
     409    block.setInsertPoint(block.back());
    266410    return result;
    267411}
     
    282426 ** ------------------------------------------------------------------------------------------------------------- */
    283427void BooleanReassociationPass::rewriteAST(PabloBlock & block, Graph & G) {
    284     // Rewrite the AST in accordance to G
     428
     429    using ReadySetQueue = std::priority_queue<std::pair<unsigned, Vertex>, std::deque<std::pair<unsigned, Vertex>>, std::greater<std::pair<unsigned, Vertex>>>;
     430
     431    raw_os_ostream out(std::cerr);
     432    out << "***************************************************\n";
     433    printGraph(G, "G_" + std::to_string((unsigned long)(&block)), out);
     434
     435
     436    // Determine the bottom-up ordering of G
     437    std::vector<unsigned> ordering(num_vertices(G));
    285438    circular_buffer<Vertex> Q(num_vertices(G));
    286     topological_sort(G, std::back_inserter(Q));
    287 
    288     block.setInsertPoint(nullptr);
    289     unsigned statementCount = 0;
    290     WrittenAt writtenAt;
    291     writtenAt.emplace(PabloBlock::createZeroes(), 0);
    292     writtenAt.emplace(PabloBlock::createOnes(), 0);
     439    for (const Vertex u : make_iterator_range(vertices(G))) {
     440        if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     441            ordering[u] = 1;
     442            Q.push_back(u);
     443        }
     444    }
     445
    293446    while (!Q.empty()) {
    294         const Vertex u = Q.back();
    295         Q.pop_back();
    296         // Supress any isolated vertices
    297         if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    298             continue;
    299         }
    300         unsigned statementIndex = 0;
     447        const Vertex u = Q.front();
     448        Q.pop_front();
     449        assert (ordering[u] > 0);
     450        for (const auto ei : make_iterator_range(in_edges(u, G))) {
     451            const Vertex v = source(ei, G);
     452            if (ordering[v] == 0) {
     453                unsigned weight = 0;
     454                bool ready = true;
     455                for (const auto ej : make_iterator_range(out_edges(v, G))) {
     456                    const Vertex w = target(ej, G);
     457                    const unsigned t = ordering[w];
     458                    if (t == 0) {
     459                        ready = false;
     460                        break;
     461                    }
     462                    weight = std::max(weight, t);
     463                }
     464                if (ready) {
     465                    assert (weight < std::numeric_limits<unsigned>::max());
     466                    assert (weight > 0);
     467                    ordering[v] = (weight + 1);
     468                    Q.push_back(v);
     469                }
     470            }
     471        }
     472    }
     473
     474    ReadySetQueue readySet;
     475    for (const Vertex u : make_iterator_range(vertices(G))) {
     476        if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     477            readySet.emplace(ordering[u], u);
     478        }
     479    }
     480
     481    out << "---------------------------------------------------\n";
     482    out.flush();
     483
     484    // Store the original AST then clear the block
     485    std::vector<Statement *> originalAST(block.begin(), block.end());
     486    block.clear();
     487    flat_set<Vertex> contains;
     488
     489    // Rewrite the AST using the bottom-up ordering
     490    while (!readySet.empty()) {
     491
     492        Vertex u; unsigned weight;
     493        std::tie(weight, u) = readySet.top();
     494        readySet.pop();
     495
    301496        PabloAST * expr = getValue(G[u]);
    302         if (LLVM_LIKELY(isMutable(G[u], block))) {
     497
     498        out << " * processing " << u << ' ';
     499        PabloPrinter::print(expr, out);
     500        out << ", weight=" << weight;
     501        out.flush();
     502
     503        assert (weight > 0);
     504
     505        if (LLVM_LIKELY(isMutable(G[u]))) {
    303506            Statement * stmt = nullptr;
    304507            if (isAssociative(G[u])) {
    305                 PabloAST * replacement = createTree(block, u, G, writtenAt);
     508                PabloAST * replacement = createTree(block, u, G);
    306509                if (LLVM_LIKELY(inCurrentBlock(replacement, block))) {
    307510                    stmt = cast<Statement>(replacement);
    308511                } else { // optimization reduced this to a Constant, Var or a prior-scope statement
    309512                    getType(G[u]) = TypeId::Var;
    310                     continue;
     513                    goto check_ready;
    311514                }
    312515            } else { // update any potential mappings
    313                 stmt = cast<Statement>(getValue(G[u]));
     516                stmt = cast<Statement>(expr);
    314517            }
    315518            assert (stmt);
    316519            for (auto e : make_iterator_range(out_edges(u, G))) {
    317520                if (G[e] && G[e] != stmt) {
    318                     PabloAST * expr = getValue(G[target(e, G)]);
    319                     if (expr) { // processing a yet-to-be created value
    320                         cast<Statement>(expr)->replaceUsesOfWith(G[e], stmt);
     521                    if (PabloAST * user = getValue(G[target(e, G)])) {
     522                        cast<Statement>(user)->replaceUsesOfWith(G[e], stmt);
    321523                    }
    322524                }
    323525            }
    324             // make sure that optimization doesn't reduce this to an already written statement
    325             if (writtenAt.count(stmt)) {
    326                 continue;
     526            // Make sure that optimization doesn't reduce this to an already written statement
     527            if (stmt->getParent()) {
     528                goto check_ready;
    327529            }
    328530            block.insert(stmt);
    329             statementIndex = ++statementCount;
    330531            expr = stmt;
    331532        }
    332         writtenAt.emplace(expr, statementIndex);
    333     }
     533check_ready:
     534
     535        out << ", wrote ";
     536        PabloPrinter::print(expr, out);
     537        out << '\n';
     538        out.flush();
     539
     540        // mark this instruction as written
     541        ordering[u] = 0;
     542        // Now check whether any new instructions are ready
     543        for (auto ei : make_iterator_range(out_edges(u, G))) {
     544            bool ready = true;
     545            const auto v = target(ei, G);
     546            // since G may be a multigraph, we need to check whether we've already tested v
     547            if (contains.insert(v).second) {
     548                for (auto ej : make_iterator_range(in_edges(v, G))) {
     549                    if (ordering[source(ej, G)]) {
     550                        ready = false;
     551                        break;
     552                    }
     553                }
     554                if (ready) {
     555
     556                    out << "   adding " << v << ' ';
     557                    PabloPrinter::print(getValue(G[v]), out);
     558                    out << " to ready set, weight=" << ordering[v] << '\n';
     559
     560                    readySet.emplace(ordering[v], v);
     561                }
     562            }
     563        }
     564        contains.clear();
     565
     566        out << "---------------------------------------------------\n";
     567        out.flush();
     568    }
     569
     570    for (Statement * stmt : originalAST) {
     571        if (stmt->getParent() == nullptr) {
     572            stmt->eraseFromParent();
     573        }
     574    }
     575
     576    PabloPrinter::print(block.statements(), out);
     577
    334578}
    335579
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4797 r4860  
    1717    using WrittenAt = boost::container::flat_map<const PabloAST *, unsigned>;
    1818    using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
    19 
    2019    static bool optimize(PabloFunction & function);
    2120protected:
     
    2726    void processScope(PabloFunction &, PabloBlock & block);
    2827    void summarizeAST(PabloBlock & block, Graph & G, Map & M) const;
    29     static void findAndPropogateAnyConstants(const Vertex u, Graph & G, Map & M);
    3028    static void summarizeGraph(const PabloBlock & block, Graph & G, std::vector<Vertex> & mapping, Map &M);
    3129    void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, const Statement * const ignoreIfThis = nullptr) const;
    3230    void redistributeAST(const PabloBlock & block, Graph & G, Map & M) const;
    3331    void rewriteAST(PabloBlock & block, Graph & G);
    34     static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G, const WrittenAt & writtenAt);
     32    static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G);
    3533    static Vertex getSummaryVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block);
    3634    static Vertex addSummaryVertex(const PabloAST::ClassTypeId typeId, Graph & G);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.cpp

    r4856 r4860  
    2525    CodeMotionPass::process(function.getEntryBlock());
    2626    #ifndef NDEBUG
    27     PabloVerifier::verify(function, "post-sinking");
     27    PabloVerifier::verify(function, "post-code-motion");
    2828    #endif
    2929    return true;
     
    4040        } else if (isa<While>(stmt)) {
    4141            process(cast<While>(stmt)->getBody());
    42             // TODO: if we analyzed the probability of this loop being executed once, twice or many times, we could
    43             // determine hoisting will helpful or harmful to the expected run time.
     42            // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
     43            // determine whether hoisting will helpful or harmful to the expected run time.
    4444            hoistLoopInvariants(cast<While>(stmt));
    4545        }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4822 r4860  
    1616#include <queue>
    1717#include <unordered_set>
    18 #include <pablo/optimizers/pablo_simplifier.hpp>
    1918#include <pablo/optimizers/booleanreassociationpass.h>
    2019#include <pablo/analysis/pabloverifier.hpp>
     
    165164        #endif
    166165
    167         Simplifier::optimize(function);
     166        BooleanReassociationPass::optimize(function);
    168167    }
    169168
     
    994993 * @brief multiplexSelectedIndependentSets
    995994 ** ------------------------------------------------------------------------------------------------------------- */
    996 void AutoMultiplexing::multiplexSelectedIndependentSets(PabloFunction & function) {
     995void AutoMultiplexing::multiplexSelectedIndependentSets(PabloFunction &) {
    997996
    998997    const unsigned first_set = num_vertices(mConstraintGraph);
     
    11001099        }
    11011100    }
    1102 
    1103     for (PabloBlock * block : modified) {
    1104         topologicalSort(function, *block);
    1105     }
    1106 }
    1107 
    1108 ///** ------------------------------------------------------------------------------------------------------------- *
    1109 // * @brief printGraph
    1110 // ** ------------------------------------------------------------------------------------------------------------- */
    1111 //template <class Graph>
    1112 //static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) {
    1113 //    raw_os_ostream out(std::cerr);
    1114 
    1115 //    out << "digraph " << name << " {\n";
    1116 //    for (auto u : make_iterator_range(vertices(G))) {
    1117 //        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    1118 //            continue;
    1119 //        }
    1120 //        out << "v" << u << " [label=\"" << u << ": ";
    1121 //        PabloAST * const expr = G[u];
    1122 //        if (isa<Statement>(expr)) {
    1123 //            if (LLVM_UNLIKELY(isa<If>(expr))) {
    1124 //                out << "If ";
    1125 //                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
    1126 //                out << ":";
    1127 //            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
    1128 //                out << "While ";
    1129 //                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
    1130 //                out << ":";
    1131 //            } else {
    1132 //                PabloPrinter::print(cast<Statement>(expr), "", out);
    1133 //            }
    1134 //        } else {
    1135 //            PabloPrinter::print(expr, out);
    1136 //        }
    1137 //        out << "\"";
    1138 //        if (!isa<Statement>(expr) || cast<Statement>(expr)->getParent() != &block) {
    1139 //            out << " style=dashed";
    1140 //        }
    1141 //        out << "];\n";
    1142 //    }
    1143 //    for (auto e : make_iterator_range(edges(G))) {
    1144 //        const auto s = source(e, G);
    1145 //        const auto t = target(e, G);
    1146 //        out << "v" << s << " -> v" << t << ";\n";
    1147 //    }
    1148 
    1149 //    if (num_vertices(G) > 0) {
    1150 
    1151 //        out << "{ rank=same;";
    1152 //        for (auto u : make_iterator_range(vertices(G))) {
    1153 //            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    1154 //                out << " v" << u;
    1155 //            }
    1156 //        }
    1157 //        out << "}\n";
    1158 
    1159 //        out << "{ rank=same;";
    1160 //        for (auto u : make_iterator_range(vertices(G))) {
    1161 //            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    1162 //                out << " v" << u;
    1163 //            }
    1164 //        }
    1165 //        out << "}\n";
    1166 
    1167 //    }
    1168 
    1169 //    out << "}\n\n";
    1170 //    out.flush();
    1171 //}
    1172 
    1173 /** ------------------------------------------------------------------------------------------------------------- *
    1174  * @brief topologicalSort
    1175  ** ------------------------------------------------------------------------------------------------------------- */
    1176 void AutoMultiplexing::topologicalSort(PabloFunction &, PabloBlock & block) const {
    1177 
    1178     TopologicalGraph G;
    1179     TopologicalMap M;
    1180     // Compute the base def-use graph ...
    1181     for (Statement * stmt : block) {       
    1182         const TopologicalVertex u = getVertex(stmt, G, M);
    1183         if (isa<If>(stmt)) {
    1184             for (Assign * def : cast<const If>(stmt)->getDefined()) {
    1185                 resolveUsages(u, def, block, G, M, stmt);
    1186             }
    1187         } else if (isa<While>(stmt)) {
    1188             for (Next * var : cast<const While>(stmt)->getVariants()) {
    1189                 resolveUsages(u, var, block, G, M, stmt);
    1190             }
    1191         } else {
    1192             resolveUsages(u, stmt, block, G, M, nullptr);
    1193         }
    1194     }
    1195 
    1196     circular_buffer<TopologicalVertex> Q(num_vertices(G));
    1197     topological_sort(G, std::back_inserter(Q));
    1198 
    1199     block.setInsertPoint(nullptr);
    1200     while (!Q.empty()) {
    1201         Statement * stmt = G[Q.back()];
    1202         Q.pop_back();
    1203         if (stmt->getParent() == &block) {
    1204             block.insert(stmt);
    1205         }
    1206     }
    1207 
    1208 }
    1209 
    1210 /** ------------------------------------------------------------------------------------------------------------- *
    1211  * @brief resolveUsages
    1212  ** ------------------------------------------------------------------------------------------------------------- */
    1213 void AutoMultiplexing::resolveUsages(const TopologicalVertex u, Statement * expr, PabloBlock & block, TopologicalGraph & G, TopologicalMap & M, Statement * ignoreIfThis) const {
    1214     for (PabloAST * user : expr->users()) {
    1215         if (LLVM_LIKELY(user != ignoreIfThis && isa<Statement>(user))) {
    1216             PabloBlock * parent = cast<Statement>(user)->getParent();
    1217             assert (parent);
    1218             if (LLVM_LIKELY(parent == &block)) {
    1219                 add_edge(u, getVertex(cast<Statement>(user), G, M), G);
    1220             } else {
    1221                 for (;;) {
    1222                     if (LLVM_UNLIKELY(parent == nullptr)) {
    1223                         assert (isa<Assign>(expr) || isa<Next>(expr));
    1224                         break;
    1225                     } else if (parent->getParent() == &block) {
    1226                         const auto f = mResolvedScopes.find(parent);
    1227                         if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
    1228                             throw std::runtime_error("Failed to resolve scope block!");
    1229                         }
    1230                         Statement * const branch = f->second;
    1231                         if (LLVM_UNLIKELY(branch != ignoreIfThis)) {
    1232                             add_edge(u, getVertex(branch, G, M), G);
    1233                         }
    1234                         break;
    1235                     }
    1236                     parent = parent->getParent();
    1237                 }
    1238             }
    1239         }
    1240     }
    1241 }
    1242 
    1243 /** ------------------------------------------------------------------------------------------------------------- *
    1244  * @brief getVertex
    1245  ** ------------------------------------------------------------------------------------------------------------- */
    1246 AutoMultiplexing::TopologicalVertex AutoMultiplexing::getVertex(Statement * expr, TopologicalGraph & G, TopologicalMap & M) {
    1247     const auto f = M.find(expr);
    1248     if (f != M.end()) {
    1249         return f->second;
    1250     }
    1251     const auto u = add_vertex(expr, G);
    1252     M.emplace(expr, u);
    1253     return u;
    12541101}
    12551102
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4822 r4860  
    5252    void applySubsetConstraints();
    5353    void multiplexSelectedIndependentSets(PabloFunction & function);
    54     void topologicalSort(PabloFunction & function, PabloBlock & block) const;
    55     void resolveUsages(const TopologicalVertex u, Statement * expr, PabloBlock & block, TopologicalGraph & G, TopologicalMap & M, Statement * ignoreIfThis) const;
    56     static TopologicalVertex getVertex(Statement * expr, TopologicalGraph & G, TopologicalMap & M);
    5754
    5855    inline AutoMultiplexing(const unsigned limit, const unsigned maxSelections)
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4856 r4860  
    228228            if (isSuperfluous(assign)) {
    229229                if (assign->getNumUses() == 0) {
    230                     stmt = assign->eraseFromParent();
     230                    stmt = assign->eraseFromParent(true);
    231231                } else {
    232232                    stmt = assign->replaceWith(assign->getExpression(), true, true);
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4856 r4860  
    1414
    1515PabloAST::Allocator PabloAST::mAllocator;
    16 PabloAST::VectorAllocator PabloAST::mVectorAllocator;
    1716
    1817/*
     
    379378}
    380379
     380/** ------------------------------------------------------------------------------------------------------------- *
     381 * @brief clear
     382 ** ------------------------------------------------------------------------------------------------------------- */
     383void StatementList::clear() {
     384    Statement * stmt = front();
     385    while (stmt) {
     386        Statement * next = stmt->mNext;
     387        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     388            PabloBlock & body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     389            stmt->mParent->removeUser(&body);
     390        }
     391        stmt->mPrev = nullptr;
     392        stmt->mNext = nullptr;
     393        stmt->mParent = nullptr;
     394        stmt = next;
     395    }
     396    mInsertionPoint = nullptr;
     397    mFirst = nullptr;
     398    mLast = nullptr;
     399}
     400
    381401StatementList::~StatementList() {
    382402
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4856 r4860  
    2525class PabloAST {
    2626    friend class Statement;
     27    friend class StatementList;
    2728    friend class Var;
    2829    friend class If;   
     
    3536
    3637    using Allocator = SlabAllocator<u_int8_t>;
    37     using VectorAllocator = SlabAllocator<PabloAST *>;
     38    using VectorAllocator = Allocator::rebind<PabloAST *>::other;
    3839    using Vector = std::vector<PabloAST*, VectorAllocator>;
    3940    using user_iterator = Vector::iterator;
     
    115116        return mAllocator.allocate(size);
    116117    }
     118
     119    void operator delete (void * ptr) {
     120        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
     121    }
     122
    117123protected:
    118124    inline PabloAST(const ClassTypeId id)
    119125    : mClassTypeId(id)
    120     , mUsers(mVectorAllocator)
     126    , mUsers(reinterpret_cast<VectorAllocator &>(mAllocator))
    121127    {
    122128
     
    148154    const ClassTypeId       mClassTypeId;
    149155    Vector                  mUsers;
    150     static VectorAllocator  mVectorAllocator;
    151156};
    152157
     
    482487    }
    483488
     489    void clear();
     490
    484491    inline void setInsertPoint(Statement * const statement) {
    485492        assert (statement == nullptr || contains(statement));
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.cpp

    r4856 r4860  
    88: Statement(ClassTypeId::If, {expr}, nullptr)
    99, mBody(body)
    10 , mDefined(definedVars.begin(), definedVars.end(), reinterpret_cast<DefinedAllocator &>(mVectorAllocator))
     10, mDefined(definedVars.begin(), definedVars.end(), reinterpret_cast<DefinedAllocator &>(mAllocator))
    1111{
    1212    // Conceptually, having a defined var X is identical to having:
     
    3030: Statement(ClassTypeId::If, {expr}, nullptr)
    3131, mBody(body)
    32 , mDefined(definedVars.begin(), definedVars.end(), reinterpret_cast<DefinedAllocator &>(mVectorAllocator))
     32, mDefined(definedVars.begin(), definedVars.end(), reinterpret_cast<DefinedAllocator &>(mAllocator))
    3333{
    3434    for (PabloAST * def : mDefined) {
  • icGREP/icgrep-devel/icgrep/pablo/ps_while.cpp

    r4856 r4860  
    77: Statement(ClassTypeId::While, {expr}, nullptr)
    88, mBody(body)
    9 , mNext(nextVars.begin(), nextVars.end(), reinterpret_cast<NextAllocator &>(mVectorAllocator)) {
     9, mNext(nextVars.begin(), nextVars.end(), reinterpret_cast<NextAllocator &>(mAllocator)) {
    1010    for (Next * variant : nextVars) {
    1111        variant->addUser(this);
     
    1717: Statement(ClassTypeId::While, {expr}, nullptr)
    1818, mBody(body)
    19 , mNext(nextVars.begin(), nextVars.end(), reinterpret_cast<NextAllocator &>(mVectorAllocator)) {
     19, mNext(nextVars.begin(), nextVars.end(), reinterpret_cast<NextAllocator &>(mAllocator)) {
    2020    for (Next * variant : nextVars) {
    2121        variant->addUser(this);
  • icGREP/icgrep-devel/icgrep/pablo/symbol_generator.cpp

    r4510 r4860  
    1111namespace pablo {
    1212
    13 SymbolGenerator::SymbolGenerator()
    14 : mPrefixMap()
    15 {
    16 
    17 }
    18 
    1913String * SymbolGenerator::get(const std::string name, const bool generated) {
     14    if (name.length() == 0) {
     15        throw std::runtime_error("symbol name cannot be 0-length");
     16    }
    2017    auto f = mStringMap.find(name);
    21     String * result;
     18    String * result = nullptr;
    2219    if (f == mStringMap.end()) {
    2320        result = new String(name, generated);
     21        assert (result);
    2422        mStringMap.insert(std::make_pair(std::move(name), result));
    2523    }
     
    3735        assert (result->value() == value);
    3836        mIntegerMap.insert(std::make_pair(value, result));
    39     }
    40     else {
     37    } else {
    4138        result = f->second;
    4239    }
     
    5047        mPrefixMap.insert(std::make_pair(prefix, 1));
    5148        return get(prefix, generated);
    52     }
    53     else {
     49    } else {
    5450        count = f->second++;
    5551        return get(prefix + std::to_string(count), generated);
     
    5753}
    5854
    59 SymbolGenerator::~SymbolGenerator() {
    60 
    6155}
    62 
    63 }
  • icGREP/icgrep-devel/icgrep/pablo/symbol_generator.h

    r4692 r4860  
    2828    String * make(const std::string prefix, const bool generated = true);
    2929    Integer * getInteger(const integer_t value);
    30     SymbolGenerator();
    31     ~SymbolGenerator();
     30    SymbolGenerator() = default;
     31    ~SymbolGenerator() = default;
    3232private:
    3333    std::unordered_map<std::string, integer_t>  mPrefixMap;
Note: See TracChangeset for help on using the changeset viewer.