Changeset 4899


Ignore:
Timestamp:
Dec 23, 2015, 4:28:42 PM (3 years ago)
Author:
nmedfort
Message:

Work on lowering + minor bug fixes.

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

Legend:

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

    r4885 r4899  
    144144
    145145/** ------------------------------------------------------------------------------------------------------------- *
     146 * @brief throwUncontainedEscapedValueError
     147 ** ------------------------------------------------------------------------------------------------------------- */
     148static void throwUncontainedEscapedValueError(const Statement * const stmt, const PabloAST * const value) {
     149    std::string tmp;
     150    raw_string_ostream str(tmp);
     151    str << "PabloVerifier: structure error: escaped value \"";
     152    PabloPrinter::print(value, str);
     153    str << "\" is not contained within the body of ";
     154    PabloPrinter::print(stmt, str);
     155    throw std::runtime_error(str.str());
     156}
     157
     158/** ------------------------------------------------------------------------------------------------------------- *
     159 * @brief throwEscapedValueUsageError
     160 ** ------------------------------------------------------------------------------------------------------------- */
     161static void throwEscapedValueUsageError(const Statement * const stmt, const PabloAST * const value, const PabloAST * const def, const PabloAST * const user, const unsigned count) {
     162    std::string tmp;
     163    raw_string_ostream str(tmp);
     164    str << "PabloVerifier: structure error: ";
     165    PabloPrinter::print(value, str);
     166    str << " is an escaped value of ";
     167    PabloPrinter::print(stmt, str);
     168    str << " but ";
     169    PabloPrinter::print(user, str);
     170    if (count == 0) {
     171        str << " is not recorded in ";
     172    } else if (count > 0) {
     173        str << " is recorded" << count << " times in ";
     174    }
     175    PabloPrinter::print(def, str);
     176    str << "'s user list.";
     177    throw std::runtime_error(str.str());
     178}
     179
     180/** ------------------------------------------------------------------------------------------------------------- *
    146181 * @brief verifyProgramStructure
    147182 ** ------------------------------------------------------------------------------------------------------------- */
     
    191226                }
    192227            }
    193             const Statement * badEscapedValue = nullptr;
    194228            if (isa<If>(stmt)) {
    195229                for (const Assign * def : cast<If>(stmt)->getDefined()) {
    196                     if (unreachable(def, nested)) {
    197                         badEscapedValue = def;
    198                         break;
     230                    if (LLVM_UNLIKELY(unreachable(def, nested))) {
     231                        throwUncontainedEscapedValueError(stmt, def);
     232                    }
     233                    unsigned count = std::count(stmt->user_begin(), stmt->user_end(), def);
     234                    if (LLVM_UNLIKELY(count != 1)) {
     235                        throwEscapedValueUsageError(stmt, def, stmt, def, count);
     236                    }
     237                    count = std::count(def->user_begin(), def->user_end(), stmt);
     238                    if (LLVM_UNLIKELY(count != 1)) {
     239                        throwEscapedValueUsageError(stmt, def, def, stmt, count);
    199240                    }
    200241                }
    201242            } else {
    202243                for (const Next * var : cast<While>(stmt)->getVariants()) {
    203                     if (unreachable(var, nested)) {
    204                         badEscapedValue = var;
    205                         break;
    206                     }
    207                 }
    208             }
    209             if (badEscapedValue) {
    210                 std::string tmp;
    211                 raw_string_ostream str(tmp);
    212                 str << "PabloVerifier: structure error: escaped value \"";
    213                 PabloPrinter::print(badEscapedValue, str);
    214                 str << "\" is not contained within the body of ";
    215                 PabloPrinter::print(stmt, str);
    216                 throw std::runtime_error(str.str());
    217             }
    218             if (isa<If>(stmt)) {
    219                 for (const Assign * def : cast<If>(stmt)->getDefined()) {
    220                     if (LLVM_UNLIKELY(std::find(stmt->user_begin(), stmt->user_end(), def) == stmt->user_end())) {
    221                         badEscapedValue = def;
    222                         break;
    223                     }
    224                 }
    225             } else {
    226                 for (const Next * var : cast<While>(stmt)->getVariants()) {
    227                     if (LLVM_UNLIKELY(std::find(stmt->user_begin(), stmt->user_end(), var) == stmt->user_end())) {
    228                         badEscapedValue = var;
    229                         break;
    230                     }
    231                 }
    232             }
    233             if (badEscapedValue) {
    234                 std::string tmp;
    235                 raw_string_ostream str(tmp);
    236                 str << "PabloVerifier: structure error: ";
    237                 PabloPrinter::print(badEscapedValue, str);
    238                 str << " is an escaped value of ";
    239                 PabloPrinter::print(stmt, str);
    240                 str << " but not a user";
    241                 throw std::runtime_error(str.str());
     244                    if (LLVM_UNLIKELY(unreachable(var, nested))) {
     245                        throwUncontainedEscapedValueError(stmt, var);
     246                    }
     247                    unsigned count = std::count(stmt->user_begin(), stmt->user_end(), var);
     248                    if (LLVM_UNLIKELY(count != 1)) {
     249                        throwEscapedValueUsageError(stmt, var, stmt, var, count);
     250                    }
     251                    count = std::count(var->user_begin(), var->user_end(), stmt);
     252                    if (LLVM_UNLIKELY(count != 1)) {
     253                        throwEscapedValueUsageError(stmt, var, var, stmt, count);
     254                    }
     255                }
    242256            }
    243257            verifyProgramStructure(nested);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4878 r4899  
    2525using Vertex = Graph::vertex_descriptor;
    2626using VertexData = BooleanReassociationPass::VertexData;
    27 using Map = BooleanReassociationPass::Map;
     27using SinkMap = BooleanReassociationPass::Map;
    2828using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
    2929using DistributionMap = flat_map<Graph::vertex_descriptor, DistributionGraph::vertex_descriptor>;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r4896 r4899  
    1616using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
    1717using Vertex = Graph::vertex_descriptor;
    18 using Map = flat_map<PabloAST *, Vertex>;
     18using SinkMap = flat_map<PabloAST *, Vertex>;
    1919using VertexSet = std::vector<Vertex>;
    2020using Biclique = std::pair<VertexSet, VertexSet>;
     
    2828 * @brief getVertex
    2929 ** ------------------------------------------------------------------------------------------------------------- */
    30 static inline Vertex getVertex(PabloAST * value, Graph & G, Map & M) {
     30static inline Vertex getVertex(PabloAST * value, Graph & G, SinkMap & M) {
    3131    const auto f = M.find(value);
    3232    if (f != M.end()) {
     
    4444 ** ------------------------------------------------------------------------------------------------------------- */
    4545VertexSet generateDistributionGraph(PabloBlock * block, Graph & G) {
    46     Map M;
     46    SinkMap M;
    4747    VertexSet distSet;
    4848    for (Statement * stmt : *block) {
     
    307307    for (;;) {
    308308
    309         FlattenAssociativeDFG::coalesce(block, false);
     309        // FlattenAssociativeDFG::coalesce(block, false);
    310310
    311311        Graph G;
     
    350350                outerOp->addOperand(G[u]);
    351351            }
     352            FlattenAssociativeDFG::coalesce(outerOp);
    352353
    353354            for (const Vertex u : sources) {
     
    358359            }
    359360            innerOp->addOperand(outerOp);
     361            FlattenAssociativeDFG::coalesce(innerOp);
    360362
    361363            for (const Vertex u : sinks) {
    362                 cast<Variadic>(G[u])->addOperand(innerOp);
    363             }
    364         }
    365 
     364                Variadic * const resultOp = cast<Variadic>(G[u]);
     365                resultOp->addOperand(innerOp);
     366                FlattenAssociativeDFG::coalesce(resultOp);
     367            }
     368        }
    366369    }
    367370}
     
    388391    #endif
    389392    Simplifier::optimize(function);
    390     FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock());
    391     #ifndef NDEBUG
    392     PabloVerifier::verify(function, "post-demorgans-reduction");
    393     #endif
    394     Simplifier::optimize(function);
    395 }
    396 
    397 
    398 }
     393//    FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock());
     394//    #ifndef NDEBUG
     395//    PabloVerifier::verify(function, "post-demorgans-reduction");
     396//    #endif
     397//    Simplifier::optimize(function);
     398}
     399
     400
     401}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4896 r4899  
    1010#include <boost/range/iterator_range.hpp>
    1111#include <pablo/analysis/pabloverifier.hpp>
     12#include <pablo/optimizers/pablo_simplifier.hpp>
    1213#include <stack>
    1314#include <queue>
     
    172173        PabloVerifier::verify(function, "post-multiplexing");
    173174        #endif
     175
     176        Simplifier::optimize(function);
    174177    }
    175178
     
    931934            const size_t m = log2_plus_one(n);
    932935            Advance * input[n];
    933             Advance * muxed[m];
     936            PabloAST * muxed[m];
     937            PabloAST * muxed_n[m];
    934938            // The multiplex set graph is a DAG with edges denoting the set relationships of our independent sets.
    935939            unsigned i = 0;
     
    939943            Advance * const adv = input[0];
    940944            PabloBlock * const block = adv->getParent(); assert (block);
    941             block->setInsertPoint(nullptr);
     945            block->setInsertPoint(nullptr);           
    942946            /// Perform n-to-m Multiplexing
    943947            for (size_t j = 0; j != m; ++j) {
     
    951955                    }
    952956                }
    953                 muxed[j] = cast<Advance>(block->createAdvance(muxing, adv->getOperand(1), prefix.str()));
     957                muxed[j] = block->createAdvance(muxing, adv->getOperand(1), prefix.str());
     958                muxed_n[j] = block->createNot(muxed[j]);
    954959            }
    955960            /// Perform m-to-n Demultiplexing
    956961            for (size_t i = 0; i != n; ++i) {
    957962                // Construct the demuxed values and replaces all the users of the original advances with them.               
    958                 PabloAST * demuxing[m];
    959                 for (size_t j = 0; j != m; ++j) {
    960                     demuxing[j] = muxed[j];
    961                     if (((i + 1) & (1UL << j)) == 0) {
    962                         demuxing[j] = block->createNot(muxed[j]);
    963                     }
    964                 }
    965963                And * demuxed = block->createAnd(m);
    966964                for (size_t j = 0; j != m; ++j) {
    967                     demuxed->addOperand(demuxing[j]);
     965                    demuxed->addOperand((((i + 1) & (1UL << j)) != 0) ? muxed[j] : muxed_n[j]);
    968966                }
    969967                input[i]->replaceWith(demuxed, true, true);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4890 r4899  
    202202 ** ------------------------------------------------------------------------------------------------------------- */
    203203inline bool Simplifier::isSuperfluous(const Assign * const assign) {
    204     for (const PabloAST * inst : assign->users()) {
    205         if (isa<Next>(inst) || isa<PabloFunction>(inst) || (isa<If>(inst) && (cast<If>(inst)->getCondition() != assign))) {
     204    for (const PabloAST * user : assign->users()) {
     205        if (LLVM_UNLIKELY(isa<PabloFunction>(user) || isa<Next>(user))) {
     206            return false;
     207        } else if (isa<If>(user)) {
     208            if (LLVM_UNLIKELY(cast<If>(user)->getCondition() == assign)) {
     209                continue;
     210            } else if (isa<Assign>(assign->getExpression())) {
     211                continue;
     212            }
    206213            return false;
    207214        }
     
    318325            // the Assign's expression directly.
    319326            if (isSuperfluous(assign)) {
    320                 stmt = assign->replaceWith(assign->getExpression());
     327                stmt = assign->replaceWith(assign->getExpression());               
    321328                continue;
    322329            }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/schedulingprepass.cpp

    r4896 r4899  
    44#include <boost/container/flat_set.hpp>
    55#include <pablo/analysis/pabloverifier.hpp>
     6
     7#include <pablo/printer_pablos.h>
     8#include <iostream>
    69
    710using namespace boost;
     
    3841}
    3942
     43///** ------------------------------------------------------------------------------------------------------------- *
     44// * @brief printGraph
     45// ** ------------------------------------------------------------------------------------------------------------- */
     46//template <typename Graph>
     47//static void printGraph(const Graph & G, const std::vector<unsigned> & ordering, const std::string name, raw_ostream & out) {
     48//    out << "*******************************************\n";
     49//    out << "digraph " << name << " {\n";
     50//    for (auto u : make_iterator_range(vertices(G))) {
     51//        out << "v" << u << " [label=\"" << ordering[u] << " : ";
     52//        PabloPrinter::print(G[u], out);
     53//        out << "\"];\n";
     54//    }
     55//    for (auto e : make_iterator_range(edges(G))) {
     56//        out << "v" << source(e, G) << " -> v" << target(e, G);
     57//        out << ";\n";
     58//    }
     59
     60//    out << "}\n\n";
     61//    out.flush();
     62//}
     63
    4064/** ------------------------------------------------------------------------------------------------------------- *
    4165 * @brief schedule
     
    6286                    auto v = M.find(op);
    6387                    assert (v != M.end());
     88                    assert (v->second != u);
    6489                    add_edge(v->second, u, G);
    6590                } else if (isa<Assign>(op) || isa<Next>(op)) {
     
    7499                            auto v = M.find(s->second);
    75100                            assert (v != M.end());
    76                             add_edge(v->second, u, G);
     101                            if (v->second != u) {
     102                                add_edge(v->second, u, G);
     103                            }
    77104                            break;
    78105                        }
     
    101128    circular_buffer<Vertex> Q(num_vertices(G));
    102129    for (const Vertex u : make_iterator_range(vertices(G))) {
    103         if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     130        if (out_degree(u, G) == 0) {
    104131            ordering[u] = 1;
    105132            Q.push_back(u);
     
    139166    for (const Vertex u : make_iterator_range(vertices(G))) {
    140167        if (in_degree(u, G) == 0) {
    141             assert (out_degree(u, G) > 0);
    142168            readySet.emplace_back(ordering[u], u);
    143169        }
     
    153179
    154180    block->setInsertPoint(nullptr);
     181
    155182
    156183    // Rewrite the AST using the bottom-up ordering
     
    195222        readySet.erase(chosen);
    196223
    197         assert (weight > 0);
     224        assert ("Error: SchedulingPrePass is attempting to reschedule a statement!" && (weight > 0));
    198225
    199226        // insert the statement then mark it as written ...
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4886 r4899  
    1010#include <pablo/printer_pablos.h>
    1111#include <llvm/ADT/SmallVector.h>
    12 #include <iostream>
    1312
    1413namespace pablo {
     
    7776 * @brief replaceAllUsesWith
    7877 ** ------------------------------------------------------------------------------------------------------------- */
    79 void PabloAST::replaceAllUsesWith(PabloAST * expr) {
     78void PabloAST::replaceAllUsesWith(PabloAST * const expr) {
    8079    assert (expr);
    8180    if (LLVM_UNLIKELY(this == expr)) {
     
    102101 ** ------------------------------------------------------------------------------------------------------------- */
    103102template <class ValueType, class ValueList>
    104 inline void Statement::checkEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
     103inline void Statement::checkEscapedValueList(Statement * const branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
    105104    if (LLVM_LIKELY(isa<ValueType>(from))) {
    106105        auto f = std::find(list.begin(), list.end(), cast<ValueType>(from));
    107106        if (LLVM_LIKELY(f != list.end())) {
     107            branch->removeUser(from);
     108            from->removeUser(branch);
    108109            if (LLVM_LIKELY(isa<ValueType>(to))) {
    109                 if (std::find(list.begin(), list.end(), cast<ValueType>(to)) == list.end()) {
     110                if (std::count(list.begin(), list.end(), cast<ValueType>(to)) == 0) {
    110111                    *f = cast<ValueType>(to);
    111112                    branch->addUser(to);
    112                 } else {
    113                     list.erase(f);
    114                 }
    115                 branch->removeUser(from);
    116                 assert (std::find(list.begin(), list.end(), cast<ValueType>(to)) != list.end());
    117                 assert (std::find(branch->user_begin(), branch->user_end(), cast<ValueType>(to)) != branch->user_end());
    118             } else {
    119                 list.erase(f);
    120                 branch->removeUser(from);
    121             }
    122         }               
    123         assert (std::find(list.begin(), list.end(), cast<ValueType>(from)) == list.end());
    124         assert (std::find(branch->user_begin(), branch->user_end(), cast<ValueType>(from)) == branch->user_end());
     113                    to->addUser(branch);
     114                    return;
     115                }
     116            }
     117            list.erase(f);
     118        }                             
    125119    }
    126120}
     
    149143 ** ------------------------------------------------------------------------------------------------------------- */
    150144void Statement::setOperand(const unsigned index, PabloAST * const value) {
    151     assert ("No operand can be null!" && value);
     145    assert ("Operand cannot be null!" && value);
    152146    assert (index < getNumOperands());
    153147    PabloAST * const prior = getOperand(index);
    154     assert ("No operand can be null!" && prior);
     148    assert ("Operand cannot be null!" && prior);
    155149    if (LLVM_UNLIKELY(prior == value)) {
    156150        return;
     
    343337        }
    344338    }
    345     replaceAllUsesWith(expr);   
     339    replaceAllUsesWith(expr);
    346340    return eraseFromParent(recursively);
    347341}
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4896 r4899  
    110110    }
    111111
    112     void replaceAllUsesWith(PabloAST * expr);
     112    void replaceAllUsesWith(PabloAST * const expr);
    113113
    114114    inline Users::size_type getNumUses() const {
     
    131131
    132132    }
    133     void addUser(PabloAST * user);
    134     void removeUser(PabloAST * user);
     133    void addUser(PabloAST * const user);
     134    void removeUser(PabloAST * const user);
    135135    virtual ~PabloAST() {
    136136        mUsers.clear();
     
    604604 * @brief addUser
    605605 ** ------------------------------------------------------------------------------------------------------------- */
    606 inline void PabloAST::addUser(PabloAST *user) {
     606inline void PabloAST::addUser(PabloAST * const user) {
    607607    assert (user);   
    608     // Note: for the rare situation that this node is used multiple times by a statement, duplicates are allowed.
     608    // Note: for the rare situation that this node is used multiple times by the same statement, duplicates are allowed.
    609609    mUsers.insert(std::lower_bound(mUsers.begin(), mUsers.end(), user), user);
    610610}
     
    613613 * @brief removeUser
    614614 ** ------------------------------------------------------------------------------------------------------------- */
    615 inline void PabloAST::removeUser(PabloAST * user) {
     615inline void PabloAST::removeUser(PabloAST * const user) {
    616616    assert (user);
    617     auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
     617    const auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
    618618    assert ("Could not find user to remove!" && (pos != mUsers.end() && *pos == user));
    619619    mUsers.erase(pos);
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.cpp

    r4896 r4899  
    1919using TypeId = PabloAST::ClassTypeId;
    2020
     21///** ------------------------------------------------------------------------------------------------------------- *
     22// * @brief lower
     23// ** ------------------------------------------------------------------------------------------------------------- */
     24//inline PabloAST * FactorizeDFG::lower(Variadic * const var, PabloBlock * block, OrderingMap & order) {
     25//    PabloAST * result = nullptr;
     26//    assert (var->getNumOperands() > 2);
     27////    // Sort the operands by their order in the current AST
     28////    std::sort(var->begin(), var->end(),
     29////        [&order](const PabloAST * const a, const PabloAST * const b)
     30////    {
     31////        return order.of(a) > order.of(b);
     32////    });
     33////    unsigned operands = var->getNumOperands();
     34////    // Swap the final two operands so that we can just append the temporary calculations onto the end
     35////    // and trust that the PENULTIMATE operand is the "latest" in the AST.
     36////    PabloAST * const item = var->getOperand(operands - 1);
     37////    var->setOperand(operands - 1, var->getOperand(operands - 2));
     38////    var->setOperand(operands - 2, item);
     39//    // Finally rewrite all of the variadic statements as binary operations
     40//    block->setInsertPoint(var->getPrevNode());
     41//    while (var->getNumOperands() > 1) {
     42//        PabloAST * const op2 = var->removeOperand(1);
     43//        PabloAST * const op1 = var->removeOperand(0);
     44//        assert (op1 != op2);
     45//        if (isa<And>(var)) {
     46//            result = block->createAnd(op1, op2);
     47//        } else if (isa<Or>(var)) {
     48//            result = block->createOr(op1, op2);
     49//        } else { // if (isa<Xor>(var)) {
     50//            result = block->createXor(op1, op2);
     51//        }
     52//        var->addOperand(result);
     53//    }
     54//    assert (result);
     55//    return result;
     56//}
     57
     58///** ------------------------------------------------------------------------------------------------------------- *
     59// * @brief lower
     60// ** ------------------------------------------------------------------------------------------------------------- */
     61//void FactorizeDFG::lower(PabloBlock * const block, OrderingMap & parent) {
     62//    OrderingMap order(parent);
     63//    Statement * stmt = block->front();
     64//    while (stmt) {
     65//        if (isa<If>(stmt) || isa<While>(stmt)) {
     66//            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), order);
     67//            if (isa<If>(stmt)) {
     68//                for (Assign * def : cast<If>(stmt)->getDefined()) {
     69//                    order.enumerate(def);
     70//                }
     71//            } else { // if (isa<While>(stmt)) {
     72//                for (Next * var : cast<While>(stmt)->getVariants()) {
     73//                    order.enumerate(var);
     74//                }
     75//            }
     76//        } else {
     77//            if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
     78//                // We should maintain an ordering list and sort each Variadic according to it prior to writing them out.
     79//                PabloAST * result = lower(cast<Variadic>(stmt), block, order);
     80//                order.enumerate(result);
     81//                stmt = stmt->replaceWith(result, true);
     82//                continue;
     83//            }
     84//            order.enumerate(stmt);
     85//        }
     86//        stmt = stmt->getNextNode();
     87//    }
     88//}
     89
    2190/** ------------------------------------------------------------------------------------------------------------- *
    2291 * @brief finalize
    2392 ** ------------------------------------------------------------------------------------------------------------- */
    24 inline Statement * FactorizeDFG::finalize(Variadic * const var, PabloBlock * block) {
     93inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) {
    2594    PabloAST * result = nullptr;
    2695    assert (var->getNumOperands() > 2);
     
    45114 * @brief finalize
    46115 ** ------------------------------------------------------------------------------------------------------------- */
    47 void FactorizeDFG::finalize(PabloBlock * const block) {
     116void FactorizeDFG::lower(PabloBlock * const block) {
    48117    Statement * stmt = block->front();
    49118    while (stmt) {
    50119        if (isa<If>(stmt) || isa<While>(stmt)) {
    51             finalize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     120            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    52121        } else if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
    53122            // We should maintain an ordering list and sort each Variadic according to it prior to writing them out.
    54             stmt = finalize(cast<Variadic>(stmt), block);
     123            stmt = lower(cast<Variadic>(stmt), block);
    55124            continue;
    56125        }
     
    58127    }
    59128}
     129
     130///** ------------------------------------------------------------------------------------------------------------- *
     131// * @brief lower
     132// ** ------------------------------------------------------------------------------------------------------------- */
     133//inline void FactorizeDFG::lower(PabloFunction & function) {
     134//    OrderingMap ordering;
     135//    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
     136//        ordering.enumerate(function.getParameter(i));
     137//    }
     138//    lower(function.getEntryBlock(), ordering);
     139//}
    60140
    61141/** ------------------------------------------------------------------------------------------------------------- *
     
    162242 * @brief chooseInsertionPoint
    163243 ** ------------------------------------------------------------------------------------------------------------- */
    164 inline PabloBlock * FactorizeDFG::chooseInsertionScope(const VertexSet & users) {
    165 
    166     std::vector<PabloBlock *> scopes;
     244inline PabloBlock * FactorizeDFG::chooseInsertionScope(const ASTVector & users) {
     245
     246    ScopeSet scopes;
    167247    scopes.reserve(users.size());
    168248
     
    212292 * @brief findInsertionPoint
    213293 ** ------------------------------------------------------------------------------------------------------------- */
    214 void FactorizeDFG::findInsertionPoint(const VertexSet & operands, PabloBlock * const scope) {
     294void FactorizeDFG::findInsertionPoint(const ASTVector & operands, PabloBlock * const scope) {
    215295    const flat_set<const PabloAST *> ops(operands.begin(), operands.end());
    216296    Statement * stmt = scope->back();
     
    240320
    241321/** ------------------------------------------------------------------------------------------------------------- *
    242  * @brief Common Subexpression Elimination
    243  ** ------------------------------------------------------------------------------------------------------------- */
    244 inline void FactorizeDFG::CSE(Variadic * var) {
     322 * @brief cse
     323 ** ------------------------------------------------------------------------------------------------------------- */
     324inline void FactorizeDFG::cse(Variadic * var) {
    245325    while (var->getNumOperands() > 2) {
    246326        BicliqueSet bicliques = enumerateBicliques(var);
     
    248328            break;
    249329        }
    250         VertexSet operands;
    251         VertexSet users;
     330        ASTVector operands;
     331        ASTVector users;
    252332        std::tie(operands, users) = pick(std::move(bicliques));
    253 
    254333        PabloBlock * const block = chooseInsertionScope(users);
    255334        findInsertionPoint(operands, block);
     
    272351
    273352/** ------------------------------------------------------------------------------------------------------------- *
    274  * @brief Common Subexpression Elimination
    275  ** ------------------------------------------------------------------------------------------------------------- */
    276 void FactorizeDFG::CSE(PabloBlock * const block) {
     353 * @brief cse
     354 *
     355 * Perform common subexpression elimination on the Variadic statements
     356 ** ------------------------------------------------------------------------------------------------------------- */
     357void FactorizeDFG::cse(PabloBlock * const block) {
    277358    Statement * stmt = block->front();
    278359    while (stmt) {
    279360        if (isa<If>(stmt) || isa<While>(stmt)) {           
    280             CSE(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     361            cse(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    281362        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
    282             CSE(cast<Variadic>(stmt));
     363            cse(cast<Variadic>(stmt));
    283364        }
    284365        stmt = stmt->getNextNode();
     
    287368
    288369/** ------------------------------------------------------------------------------------------------------------- *
    289  * @brief preScanDFG
    290  ** ------------------------------------------------------------------------------------------------------------- */
    291 void FactorizeDFG::initialize(const PabloBlock * const block, const unsigned depth) {
     370 * @brief enumerateScopeDepth
     371 ** ------------------------------------------------------------------------------------------------------------- */
     372void FactorizeDFG::enumerateScopeDepth(const PabloBlock * const block, const unsigned depth) {
    292373    const Statement * stmt = block->front();
    293374    while (stmt) {
     
    295376            PabloBlock * body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    296377            mScopeDepth.emplace(body, depth);
    297             initialize(body, depth + 1);
     378            enumerateScopeDepth(body, depth + 1);
    298379        }
    299380        stmt = stmt->getNextNode();
     
    302383
    303384/** ------------------------------------------------------------------------------------------------------------- *
    304  * @brief preScanDFG
    305  ** ------------------------------------------------------------------------------------------------------------- */
    306 inline void FactorizeDFG::initialize(const PabloFunction &function) {
     385 * @brief enumerateScopeDepth
     386 ** ------------------------------------------------------------------------------------------------------------- */
     387inline void FactorizeDFG::enumerateScopeDepth(const PabloFunction & function) {
    307388    mScopeDepth.emplace(function.getEntryBlock(), 0);
    308     initialize(function.getEntryBlock(), 1);
     389    enumerateScopeDepth(function.getEntryBlock(), 1);
    309390}
    310391
     
    314395void FactorizeDFG::transform(PabloFunction & function) {
    315396    FactorizeDFG ldfg;
    316     ldfg.initialize(function);
    317     ldfg.CSE(function.getEntryBlock());
     397    ldfg.enumerateScopeDepth(function);
     398    ldfg.cse(function.getEntryBlock());
    318399    #ifndef NDEBUG
    319     PabloVerifier::verify(function, "post-factorize");
    320     #endif
    321     ldfg.finalize(function.getEntryBlock());
    322     #ifndef NDEBUG
    323     PabloVerifier::verify(function, "post-finalize");
     400    PabloVerifier::verify(function, "post-cse");
    324401    #endif
    325402    Simplifier::optimize(function);
    326 }
    327 
    328 }
     403    ldfg.lower(function.getEntryBlock());
     404    #ifndef NDEBUG
     405    PabloVerifier::verify(function, "post-lowering");
     406    #endif   
     407}
     408
     409}
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.h

    r4890 r4899  
    1616class FactorizeDFG {
    1717    using ScopeDepth = boost::container::flat_map<const PabloBlock *, unsigned>;
    18     using VertexSet = std::vector<PabloAST *>;
     18    using ScopeSet = std::vector<PabloBlock *>;
     19    using ASTVector = std::vector<PabloAST *>;
     20    struct OrderingMap {
     21        unsigned of(const PabloAST * const expr) const {
     22            auto f = mMap.find(expr);
     23            if (f == mMap.end()) {
     24                return mParent ? mParent->of(expr) : 0;
     25            }
     26            return f->second;
     27        }
     28        inline void enumerate(const PabloAST * const expr) {
     29            mMap.emplace(expr, ++mOrderingCount);
     30        }
     31        OrderingMap() :  mParent(nullptr), mOrderingCount(0) {}
     32        OrderingMap(OrderingMap * const parent) :  mParent(parent), mOrderingCount(parent->mOrderingCount) {}
     33        ~OrderingMap() { if (mParent) { mParent->mOrderingCount = mOrderingCount; } }
     34    private:
     35        OrderingMap * const mParent;
     36        unsigned mOrderingCount;
     37        boost::container::flat_map<const PabloAST *, unsigned> mMap;
     38    };
     39
    1940public:
    2041    static void transform(PabloFunction & function);
    2142protected:   
    22     void initialize(const PabloFunction & function);
    23     void initialize(const PabloBlock * const block, const unsigned depth);
    24     void CSE(PabloBlock * const block);
    25     void CSE(Variadic * const var);
    26     PabloBlock * chooseInsertionScope(const VertexSet & users);
    27     void findInsertionPoint(const VertexSet & operands, PabloBlock * const scope);
    28     void finalize(PabloBlock * const block);
    29     Statement * finalize(Variadic * const var, PabloBlock * block);
     43    void enumerateScopeDepth(const PabloFunction & function);
     44    void enumerateScopeDepth(const PabloBlock * const block, const unsigned depth);
     45    void cse(PabloBlock * const block);
     46    void cse(Variadic * const var);
     47    PabloBlock * chooseInsertionScope(const ASTVector & users);
     48    void findInsertionPoint(const ASTVector & operands, PabloBlock * const scope);
     49    void lower(PabloFunction & function);
     50//    void lower(PabloBlock * const block, OrderingMap & parent);
     51//    PabloAST * lower(Variadic * const var, PabloBlock * block, OrderingMap & order);
     52    void lower(PabloBlock * const block);
     53    Statement * lower(Variadic * const var, PabloBlock * block);
    3054    FactorizeDFG() = default;
    3155private:
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp

    r4896 r4899  
    66#include <boost/container/flat_map.hpp>
    77#include <boost/graph/adjacency_list.hpp>
    8 
    9 #include <pablo/printer_pablos.h>
    10 #include <iostream>
     8#include <queue>
    119
    1210using namespace boost;
     
    119117 * @brief deMorgansReduction
    120118 ** ------------------------------------------------------------------------------------------------------------- */
    121 inline void FlattenAssociativeDFG::deMorgansReduction(PabloBlock * const block) {
     119void FlattenAssociativeDFG::deMorgansReduction(PabloBlock * const block, const bool traverse) {
    122120    for (Statement * stmt : *block) {
    123         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    124             deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     121        if (LLVM_UNLIKELY((isa<If>(stmt) || isa<While>(stmt)) && traverse)) {
     122            deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), true);
    125123        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
    126124            deMorgansReduction(cast<Variadic>(stmt), block);
     
    138136using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, Variadic *>;
    139137using Vertex = Graph::vertex_descriptor;
    140 using Map = flat_map<TypeId, Vertex>;
     138using SourceMap = flat_map<Assign *, Vertex>;
     139using SinkMap = flat_map<TypeId, Vertex>;
    141140using VertexSet = std::vector<Vertex>;
    142141using Biclique = std::pair<VertexSet, VertexSet>;
     
    146145 * @brief addToVariadicGraph
    147146 ** ------------------------------------------------------------------------------------------------------------- */
    148 static bool addToVariadicGraph(Assign * const def, Graph & G, Map & M, VertexSet & A) {
    149 
    150     // Test if its valid to transform this statement
    151     for (PabloAST * user : def->users()) {
    152         if (isa<Variadic>(user) == 0) {
    153             if (isa<If>(user)) {
    154                 const auto defs = cast<If>(user)->getDefined();
    155                 if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), def) != defs.end())) {
    156                     continue;
    157                 }
    158             }
    159             return false;
    160         }
    161     }
    162 
    163     // Add the statement and its users to G
    164     const Vertex u = add_vertex(VertexData(def), G);
    165     A.push_back(u);
    166     for (PabloAST * user : def->users()) {
    167         if (isa<Variadic>(user)) {
    168             auto f = M.find(user->getClassTypeId());
    169             if (f == M.end()) {
    170                 f = M.emplace(user->getClassTypeId(), add_vertex(VertexData(user->getClassTypeId()), G)).first;
    171             }
    172             assert (f != M.end());
    173             G[add_edge(u, f->second, G).first] = cast<Variadic>(user);
     147static bool addToVariadicGraph(Assign * const def, Graph & G, SourceMap & A, SinkMap & B) {
     148
     149    if (LLVM_LIKELY(A.count(def) == 0)) {
     150        // Test if its valid to transform this statement
     151        for (PabloAST * user : def->users()) {
     152            if (isa<Variadic>(user) == 0) {
     153                if (isa<If>(user)) {
     154                    if (LLVM_LIKELY(cast<If>(user)->getCondition() != def)) {
     155                        continue;
     156                    }
     157                }
     158                return false;
     159            }
     160        }
     161
     162        // Add the statement and its users to G
     163        const Vertex u = add_vertex(VertexData(def), G);
     164        A.emplace(def, u);
     165        for (PabloAST * user : def->users()) {
     166            if (isa<Variadic>(user)) {
     167                auto f = B.find(user->getClassTypeId());
     168                if (f == B.end()) {
     169                    f = B.emplace(user->getClassTypeId(), add_vertex(VertexData(user->getClassTypeId()), G)).first;
     170                }
     171                assert (f != B.end());
     172                G[add_edge(u, f->second, G).first] = cast<Variadic>(user);
     173            }
    174174        }
    175175    }
     
    342342 * @brief tryToPartiallyExtractVariadic
    343343 ** ------------------------------------------------------------------------------------------------------------- */
    344 void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
     344inline void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
    345345
    346346    for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    347347        PabloAST * const op = var->getOperand(i);
    348348        if (isa<Assign>(op)) {
     349
    349350            // Have we found a variadic operation that can sunk into a nested scope?
    350351            for (unsigned j = i + 1; j != var->getNumOperands(); ++j) {
     
    352353                if (LLVM_UNLIKELY(matches(op, var->getOperand(j)))) {
    353354                    Graph G;
    354                     Map M;
    355                     VertexSet A;
    356                     if (addToVariadicGraph(cast<Assign>(op), G, M, A) == 0) {
     355                    SourceMap A;
     356                    SinkMap B;
     357                    if (addToVariadicGraph(cast<Assign>(op), G, A, B) == 0) {
    357358                        invalid = true;
    358359                        break;
    359360                    }
    360                     addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, M, A);
     361                    addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, A, B);
    361362                    for (++j; j != var->getNumOperands(); ++j) {
    362363                        if (LLVM_UNLIKELY(matches(op, var->getOperand(j)))) {
    363                             addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, M, A);
     364                            addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, A, B);
    364365                        }
    365366                    }
     367
    366368                    if (A.size() > 1) {
    367                         const auto S = independentCliqueSets<0>(std::move(enumerateBicliques(G, A)), 2);
     369
     370                        VertexSet H;
     371                        H.reserve(A.size());
     372                        for (auto a : A) {
     373                            H.push_back(a.second);
     374                        }
     375
     376                        const auto S = independentCliqueSets<0>(std::move(enumerateBicliques(G, H)), 2);
     377                        assert (S.size() > 0);
    368378                        for (const Biclique & C : S) {
    369379                            const VertexSet & sources = std::get<0>(C);
    370380                            const VertexSet & variadics = std::get<1>(C);
     381                            assert (variadics.size() > 0);
     382                            assert (sources.size() > variadics.size());
    371383                            PabloBlock * const block = cast<Assign>(op)->getParent();
    372384                            block->setInsertPoint(block->back());
     
    383395                                        joiner = block->createXor(sources.size());
    384396                                        break;
    385                                     default:
    386                                         break;
     397                                    default: llvm_unreachable("Unexpected!");
    387398                                }
    388399                                assert (joiner);
    389                                 flat_set<Variadic *> vars;
     400                                flat_set<Assign *> defs;
    390401                                for (const auto u : sources) {
    391                                     Assign * const def = G[u].def;
    392                                     joiner->addOperand(def->getOperand(0));
    393                                     for (auto e : make_iterator_range(out_edges(u, G))) {
    394                                         if (LLVM_LIKELY(target(e, G) == v)) {
    395                                             Variadic * const var = cast<Variadic>(G[e]);
    396                                             vars.insert(var);
    397                                             var->deleteOperand(def);
    398                                         }
    399                                     }
    400                                     assert (def->getNumUses() == 1);
    401                                     def->eraseFromParent();
     402                                    defs.insert(G[u].def);
    402403                                }
     404                                for (Assign * def : defs) {
     405                                    joiner->addOperand(def->getOperand(0));                                   
     406                                }
     407
    403408                                coalesce(joiner);
    404                                 Assign * const def = block->createAssign("m", joiner);
    405                                 cast<If>(block->getBranch())->addDefined(def);
    406                                 for (Variadic * var : vars) {
    407                                     var->addOperand(def);
     409                                Assign * const joined = block->createAssign("m", joiner);
     410
     411                                for (Assign * def : defs) {
     412                                    def->replaceWith(joined);
     413                                    assert (def->getNumUses() == 0);
    408414                                }
    409415                            }
    410416                        }
     417                        --i;
    411418                    }
    412419                    break;
     
    421428
    422429/** ------------------------------------------------------------------------------------------------------------- *
    423  * @brief removeFalseScopeDependencies
    424  ** ------------------------------------------------------------------------------------------------------------- */
    425 inline void FlattenAssociativeDFG::removeFalseScopeDependencies(Assign * const def) {
    426     if (isa<Variadic>(def->getOperand(0))) {
    427         Variadic * const var = cast<Variadic>(def->getOperand(0));
    428         for (unsigned i = 0; i != var->getNumOperands(); ++i) {
    429             if (isa<Assign>(var->getOperand(i))) {
    430                 Assign * const nestedDef = cast<Assign>(var->getOperand(i));
    431                 if (LLVM_LIKELY(nestedDef->getOperand(0)->getClassTypeId() == var->getClassTypeId())) {
    432                     if (LLVM_LIKELY(nestedDef->getNumUses() == 2)) { // The If node that produces it and the "var"
    433                         Variadic * const nestedVar = cast<Variadic>(nestedDef->getOperand(0));
    434                         if (LLVM_LIKELY(nestedVar->getNumUses() == 1 && nestedVar->getNumOperands() > 0)) {
    435                             for (unsigned i = 0, j = 0; ; ) {
    436                                 if (var->getOperand(i) < nestedVar->getOperand(j)) {
    437                                     if (++i == var->getNumOperands()) {
    438                                         break;
    439                                     }
    440                                 } else {
    441                                     if (var->getOperand(i) > nestedVar->getOperand(j)) {
    442                                         ++j;
    443                                     } else {
    444                                         nestedVar->removeOperand(j);
    445                                     }
    446                                     if (j == nestedVar->getNumOperands()) {
    447                                         break;
    448                                     }
    449                                 }
    450                             }
     430 * @brief tryToPartiallyExtractVariadic
     431 ** ------------------------------------------------------------------------------------------------------------- */
     432void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(PabloBlock * const block) {
     433    for (Statement * stmt = block->back(); stmt; stmt = stmt->getPrevNode()) {
     434        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     435            tryToPartiallyExtractVariadic(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     436        } else if (isa<Variadic>(stmt)) {
     437            tryToPartiallyExtractVariadic(cast<Variadic>(stmt));
     438        }
     439    }
     440}
     441
     442using ScopeDependencyGraph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     443using ScopeDependencyMap = flat_map<PabloAST *, ScopeDependencyGraph::vertex_descriptor>;
     444
     445/** ------------------------------------------------------------------------------------------------------------- *
     446 * @brief find
     447 ** ------------------------------------------------------------------------------------------------------------- */
     448inline ScopeDependencyGraph::vertex_descriptor find(PabloAST * expr, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     449    auto f = M.find(expr);
     450    if (f == M.end()) {
     451        f = M.emplace(expr, add_vertex(expr, G)).first;
     452    }
     453    return f->second;
     454}
     455
     456/** ------------------------------------------------------------------------------------------------------------- *
     457 * @brief buildScopeDependencyGraph
     458 ** ------------------------------------------------------------------------------------------------------------- */
     459ScopeDependencyGraph::vertex_descriptor buildScopeDependencyGraph(Variadic * const var, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     460    auto f = M.find(var);
     461    if (f != M.end()) {
     462        return f->second;
     463    }
     464    auto u = add_vertex(var, G);
     465    M.emplace(var, u);
     466    for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     467        PabloAST * expr = var->getOperand(i);
     468        PabloAST * value = var;
     469        while (isa<Assign>(expr)) {           
     470            value = expr;
     471            expr = cast<Assign>(expr)->getExpression();
     472        }
     473        if ((expr->getClassTypeId() == var->getClassTypeId()) && (expr->getNumUses() == 1)) {
     474            const auto v = find(value, G, M);
     475            add_edge(v, u, G);
     476            add_edge(buildScopeDependencyGraph(cast<Variadic>(expr), G, M), v, G);
     477        }
     478    }
     479    return u;
     480}
     481
     482/** ------------------------------------------------------------------------------------------------------------- *
     483 * @brief analyzeScopeDependencies
     484 ** ------------------------------------------------------------------------------------------------------------- */
     485inline void analyzeScopeDependencies(Assign * const def, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     486    if (LLVM_LIKELY(isa<Variadic>(def->getExpression()))) {
     487        buildScopeDependencyGraph(cast<Variadic>(def->getExpression()), G, M);
     488    }
     489}
     490
     491/** ------------------------------------------------------------------------------------------------------------- *
     492 * @brief analyzeScopeDependencies
     493 ** ------------------------------------------------------------------------------------------------------------- */
     494void analyzeScopeDependencies(PabloBlock * const block, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     495    for (Statement * stmt : *block) {
     496        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     497            analyzeScopeDependencies(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), G, M);
     498        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     499            analyzeScopeDependencies(cast<Assign>(stmt), G, M);
     500        }
     501    }
     502}
     503
     504/** ------------------------------------------------------------------------------------------------------------- *
     505 * @brief removeDependenciesWithUnresolvedUses
     506 ** ------------------------------------------------------------------------------------------------------------- */
     507void removeDependenciesWithUnresolvedUses(ScopeDependencyGraph & G) {
     508    for (auto u : make_iterator_range(vertices(G))) {
     509        const PabloAST * const expr = G[u];
     510        unsigned uses = 0;
     511        if (isa<Assign>(expr)) {
     512            for (const PabloAST * user : cast<Assign>(expr)->users()) {
     513                if (!isa<If>(user) || cast<If>(user)->getCondition() == expr) {
     514                    ++uses;
     515                }
     516            }
     517        } else {
     518            uses = expr->getNumUses();
     519        }
     520        if (uses != out_degree(u, G)) {
     521            clear_out_edges(u, G);
     522        }
     523    }
     524}
     525
     526/** ------------------------------------------------------------------------------------------------------------- *
     527 * @brief eliminateUnecessaryDependencies
     528 ** ------------------------------------------------------------------------------------------------------------- */
     529void eliminateUnecessaryDependencies(ScopeDependencyGraph & G) {
     530    using Vertex = ScopeDependencyGraph::vertex_descriptor;
     531    std::vector<bool> visited(num_vertices(G), false);
     532    std::queue<Vertex> Q;
     533    for (auto u : make_iterator_range(vertices(G))) {
     534        if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     535            Q.push(u);
     536        }
     537    }
     538    while (Q.size() > 0) {
     539        const auto u = Q.front(); Q.pop();
     540        visited[u] = true;
     541        for (auto e : make_iterator_range(in_edges(u, G))) {
     542            bool usersHaveBeenVisited = true;
     543            const auto v = source(e, G);
     544            for (auto e : make_iterator_range(out_edges(v, G))) {
     545                if (visited[target(e, G)] == 0) {
     546                    usersHaveBeenVisited = false;
     547                    break;
     548                }
     549            }
     550            if (usersHaveBeenVisited) {
     551                Q.push(v);
     552                for (auto e : make_iterator_range(in_edges(u, G))) {
     553                    const auto w = source(e, G);
     554                    if (w != v) {
     555                        auto f = add_edge(w, v, G);
     556                        if (f.second == 0) {
     557                            cast<Variadic>(G[v])->deleteOperand(G[w]);
    451558                        }
    452559                    }
     
    463570 * If statement. Unless necessary for correctness, eliminate it as we can potentially schedule the If nodes
    464571 * better without the sequential dependency.
    465  ** ------------------------------------------------------------------------------------------------------------- */
    466 void FlattenAssociativeDFG::removeFalseScopeDependencies(PabloBlock * const block) {
    467     for (Statement * stmt = block->back(); stmt; stmt = stmt->getPrevNode()) {
    468         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    469             removeFalseScopeDependencies(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    470         } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
    471             removeFalseScopeDependencies(cast<Assign>(stmt));
    472         } else if (isa<Variadic>(stmt)) {
    473             tryToPartiallyExtractVariadic(cast<Variadic>(stmt));
    474         }
    475     }
     572 *
     573 * TODO: make this only iterate over the scope blocks and test the scope branch.
     574 ** ------------------------------------------------------------------------------------------------------------- */
     575inline void FlattenAssociativeDFG::removeFalseScopeDependencies(PabloFunction & function) {
     576    ScopeDependencyGraph G;
     577    {
     578        ScopeDependencyMap M;
     579        analyzeScopeDependencies(function.getEntryBlock(), G, M);
     580    }
     581    removeDependenciesWithUnresolvedUses(G);
     582    eliminateUnecessaryDependencies(G);
    476583}
    477584
     
    488595    Simplifier::optimize(function);
    489596
    490     FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock());
     597    FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock(), true);
    491598    #ifndef NDEBUG
    492599    PabloVerifier::verify(function, "post-demorgans-reduction");
     
    495602    Simplifier::optimize(function);
    496603
    497     FlattenAssociativeDFG::removeFalseScopeDependencies(function.getEntryBlock());
     604    FlattenAssociativeDFG::removeFalseScopeDependencies(function);
    498605    #ifndef NDEBUG
    499606    PabloVerifier::verify(function, "post-remove-false-scope-dependencies");
    500607    #endif
    501608
     609    FlattenAssociativeDFG::tryToPartiallyExtractVariadic(function.getEntryBlock());
     610    #ifndef NDEBUG
     611    PabloVerifier::verify(function, "post-partial-variadic-extraction");
     612    #endif
     613
    502614    Simplifier::optimize(function);
    503 }
    504 
    505 }
     615
     616
     617}
     618
     619}
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.h

    r4896 r4899  
    2020    static void coalesce(Variadic * const var);
    2121    static void deMorgansExpansion(Not * const var, PabloBlock * const block);
    22     static void deMorgansReduction(PabloBlock * const block);
     22    static void deMorgansReduction(PabloBlock * const block, const bool traverse);
    2323    static void deMorgansReduction(Variadic * const var, PabloBlock * const block);
    24     static void removeFalseScopeDependencies(PabloBlock * const block);
    25     static void removeFalseScopeDependencies(Assign * const def);
     24    static void tryToPartiallyExtractVariadic(PabloBlock * const block);
    2625    static void tryToPartiallyExtractVariadic(Variadic * const var);
     26    static void removeFalseScopeDependencies(PabloFunction & function);
    2727    FlattenAssociativeDFG() = default;
    2828};
  • icGREP/icgrep-devel/icgrep/toolchain.cpp

    r4896 r4899  
    8080
    8181#ifdef ENABLE_MULTIPLEXING
     82static cl::opt<bool> PrintUnloweredCode("print-unlowered-pablo", cl::init(false), cl::desc("print Pablo output prior to lowering. "), cl::cat(dPabloDumpOptions));
     83
    8284static cl::opt<bool> EnableMultiplexing("multiplexing", cl::init(false),
    8385                                        cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."),
     
    9799                                         cl::desc("coalesce associative functions prior to optimization passes."),
    98100                                         cl::cat(cPabloOptimizationsOptions));
    99 static cl::opt<bool> EnableDistribution("dist", cl::init(false),
     101static cl::opt<bool> EnablePreDistribution("pre-dist", cl::init(false),
     102                                         cl::desc("apply distribution law optimization."),
     103                                         cl::cat(cPabloOptimizationsOptions));
     104static cl::opt<bool> EnablePostDistribution("post-dist", cl::init(false),
    100105                                         cl::desc("apply distribution law optimization."),
    101106                                         cl::cat(cPabloOptimizationsOptions));
     
    153158    }
    154159#ifdef ENABLE_MULTIPLEXING
    155     if (EnableLowering || EnableDistribution || EnableMultiplexing) {
     160    if (EnableLowering || EnablePreDistribution || EnablePostDistribution || EnableMultiplexing) {
    156161        FlattenAssociativeDFG::transform(*function);
    157162    }
     
    161166    }
    162167#ifdef ENABLE_MULTIPLEXING   
    163     if (EnableDistribution) {
     168    if (EnablePreDistribution) {
    164169        DistributivePass::optimize(*function);
    165170    }
     
    167172        MultiplexingPass::optimize(*function, MultiplexingSetLimit, MultiplexingSelectionLimit, MultiplexingWindowSize);
    168173    }
     174    if (EnablePostDistribution) {
     175        DistributivePass::optimize(*function);
     176    }
    169177    SchedulingPrePass::optimize(*function);
    170     if (EnableLowering || EnableDistribution || EnableMultiplexing) {
     178    if (PrintUnloweredCode) {
     179        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
     180        llvm::raw_os_ostream cerr(std::cerr);
     181        cerr << "Unlowered Pablo AST:\n";
     182        PabloPrinter::print(*function, cerr);
     183    }
     184    if (EnableLowering || EnablePreDistribution || EnablePostDistribution || EnableMultiplexing) {
    171185        FactorizeDFG::transform(*function);
    172186    }
Note: See TracChangeset for help on using the changeset viewer.