Ignore:
Timestamp:
Feb 12, 2016, 4:44:35 PM (4 years ago)
Author:
nmedfort
Message:

Bug fixes

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

Legend:

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

    r4925 r4927  
    303303 * @brief blendCarrySummaryWithOuterSummary
    304304 ** ------------------------------------------------------------------------------------------------------------- */
    305 void CarryManager::blendCarrySummaryWithOuterSummary() {
     305void CarryManager::addOuterSummaryToNestedSummary() {
    306306    if (LLVM_LIKELY(mCarrySummary.size() > 0)) {
    307307        addToSummary(mCarrySummary.back());
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.h

    r4925 r4927  
    8787    void storeCarryOutSummary();
    8888
    89     void blendCarrySummaryWithOuterSummary();
     89    void addOuterSummaryToNestedSummary();
    9090
    9191    void buildCarryDataPhisAfterIfBody(BasicBlock * const entry, BasicBlock * const end);
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4896 r4927  
    117117    }
    118118
     119    And * createAnd(Variadic::iterator begin, Variadic::iterator end) {
     120        return insertAtInsertionPoint(new And(begin, end, makeName("and_")));
     121    }
     122
    119123    PabloAST * createNot(PabloAST * expr);
    120124
     
    129133    }
    130134
     135    Or * createOr(Variadic::iterator begin, Variadic::iterator end) {
     136        return insertAtInsertionPoint(new Or(begin, end, makeName("or_")));
     137    }
     138
    131139    Or * createOr(const unsigned reserved);
    132140
     
    138146
    139147    Xor * createXor(std::vector<PabloAST *>::iterator begin, std::vector<PabloAST *>::iterator end) {
     148        return insertAtInsertionPoint(new Xor(begin, end, makeName("xor_")));
     149    }
     150
     151    Xor * createXor(Variadic::iterator begin, Variadic::iterator end) {
    140152        return insertAtInsertionPoint(new Xor(begin, end, makeName("xor_")));
    141153    }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.cpp

    r4919 r4927  
    33#include <pablo/analysis/pabloverifier.hpp>
    44#include <boost/container/flat_set.hpp>
     5#include <boost/container/flat_map.hpp>
     6#include <boost/graph/adjacency_list.hpp>
     7#include <boost/graph/topological_sort.hpp>
     8#include <boost/circular_buffer.hpp>
    59
    610using namespace boost;
     
    1317 ** ------------------------------------------------------------------------------------------------------------- */
    1418bool CodeMotionPass::optimize(PabloFunction & function) {
    15     CodeMotionPass::global(function.getEntryBlock());
     19    CodeMotionPass::movement(function.getEntryBlock());
    1620    #ifndef NDEBUG
    1721    PabloVerifier::verify(function, "post-code-motion");
     
    2125
    2226/** ------------------------------------------------------------------------------------------------------------- *
    23  * @brief process
    24  ** ------------------------------------------------------------------------------------------------------------- */
    25 void CodeMotionPass::global(PabloBlock * const block) {
     27 * @brief movement
     28 ** ------------------------------------------------------------------------------------------------------------- */
     29void CodeMotionPass::movement(PabloBlock * const block) {
    2630    sink(block);
    2731    for (Statement * stmt : *block) {
    2832        if (isa<If>(stmt)) {
    29             global(cast<If>(stmt)->getBody());
     33            movement(cast<If>(stmt)->getBody());
    3034        } else if (isa<While>(stmt)) {
    31             global(cast<While>(stmt)->getBody());
     35            movement(cast<While>(stmt)->getBody());
    3236            // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
    3337            // determine whether hoisting will helpful or harmful to the expected run time.
     
    3539        }
    3640    }
     41    reschedule(block);
    3742}
    3843
     
    4752 * @brief calculateDepthToCurrentBlock
    4853 ** ------------------------------------------------------------------------------------------------------------- */
    49 inline static unsigned calculateDepthToCurrentBlock(const PabloBlock * scope, const PabloBlock * const root) {
     54inline static unsigned depthTo(const PabloBlock * scope, const PabloBlock * const root) {
    5055    unsigned depth = 0;
    5156    while (scope != root) {
     
    103108 * @brief sink
    104109 ** ------------------------------------------------------------------------------------------------------------- */
    105 void CodeMotionPass::sink(PabloBlock * const block) {
     110inline void CodeMotionPass::sink(PabloBlock * const block) {
    106111    ScopeSet scopes;
    107112    Statement * stmt = block->back(); // note: reverse AST traversal
     
    113118                // Find the LCA of both scopes then add the LCA back to the list of scopes.
    114119                PabloBlock * scope1 = scopes.back(); scopes.pop_back();
    115                 unsigned depth1 = calculateDepthToCurrentBlock(scope1, block);
     120                unsigned depth1 = depthTo(scope1, block);
    116121
    117122                PabloBlock * scope2 = scopes.back(); scopes.pop_back();
    118                 unsigned depth2 = calculateDepthToCurrentBlock(scope2, block);
     123                unsigned depth2 = depthTo(scope2, block);
    119124
    120125                // If one of these scopes is nested deeper than the other, scan upwards through
     
    194199}
    195200
    196 }
     201/** ------------------------------------------------------------------------------------------------------------- *
     202 * @brief reschedule
     203 ** ------------------------------------------------------------------------------------------------------------- */
     204void CodeMotionPass::reschedule(PabloBlock * const block) {
     205
     206//    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, Statement *>;
     207//    using Vertex = Graph::vertex_descriptor;
     208//    using Map = flat_map<Statement *, Vertex>;
     209
     210//    const unsigned size = std::distance(block->begin(), block->end());
     211
     212//    Graph G(size);
     213//    Map M;
     214
     215//    M.reserve(size);
     216
     217//    unsigned i = 0;
     218//    for (Statement * stmt : *block) {
     219//        G[i] = stmt;
     220//        M.emplace(stmt, i);
     221//        ++i;
     222//    }
     223
     224//    i = 0;
     225//    for (Statement * stmt : *block) {
     226//        for (PabloAST * user : stmt->users()) {
     227//            if (isa<Statement>(user)) {
     228//                Statement * use = cast<Statement>(user);
     229//                PabloBlock * parent = use->getParent();
     230//                while (parent) {
     231//                    if (parent == block) {
     232//                        break;
     233//                    }
     234//                    use = parent->getBranch();
     235//                    parent = parent->getParent();
     236//                }
     237//                auto f = M.find(use);
     238//                assert (f != M.end());
     239//                add_edge(i, f->second, G);
     240//            }
     241//        }
     242//        ++i;
     243//    }
     244
     245//    circular_buffer<Vertex> ordering(size);
     246//    std::vector<unsigned> cumulativeDependencies;
     247//    topological_sort(G, std::back_inserter(ordering));
     248   
     249
     250
     251}
     252
     253}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.h

    r4919 r4927  
    3131    static bool optimize(PabloFunction & function);
    3232protected:
    33     static void global(PabloBlock * const block);
     33    static void movement(PabloBlock * const block);
    3434    static bool isAcceptableTarget(Statement *stmt, ScopeSet & scopeSet, const PabloBlock * const block);
    3535    static void sink(PabloBlock * const block);
    3636    static void hoistLoopInvariants(While * loop);
     37
     38    static void reschedule(PabloBlock * const block);
    3739};
    3840
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r4922 r4927  
    377377inline void DistributivePass::distribute(Variadic * const var) {
    378378
    379     std::vector<Variadic *> Q;
     379
    380380
    381381    assert (isa<And>(var) || isa<Or>(var));
    382 
    383     Q.push_back(var);
    384382
    385383    Graph G;
    386384    VertexSet A;
    387385
     386    std::vector<Variadic *> Q = {var};
     387
    388388    while (Q.size() > 0) {
    389 
    390         Variadic * expr = CanonicalizeDFG::canonicalize(Q.back());
    391         Q.pop_back();
     389        Variadic * expr = CanonicalizeDFG::canonicalize(Q.back()); Q.pop_back();
    392390        PabloAST * const replacement = Simplifier::fold(expr, expr->getParent());
    393391        if (LLVM_UNLIKELY(replacement != nullptr)) {
     
    427425                const VertexSet & sinks = std::get<2>(set);
    428426                assert (sinks.size() > 0);
    429 
    430                 // Test whether we can apply the identity law to distributed set. I.e., (P ∧ Q) √ (P ∧ ¬Q) ⇔ (P √ Q) ∧ (P √ ¬Q) ⇔ P
    431 
    432427
    433428                for (const Vertex u : intermediary) {
     
    465460                Q.push_back(innerOp);
    466461                Q.push_back(outerOp);
     462
     463                unmodified = false;
    467464            }
    468465
     
    471468        }
    472469    }
     470
    473471}
    474472
     
    477475 ** ------------------------------------------------------------------------------------------------------------- */
    478476void DistributivePass::distribute(PabloBlock * const block) {
    479     for (Statement * stmt : *block) {
     477    Statement * stmt = block->front();
     478    while (stmt) {
     479        Statement * next = stmt->getNextNode();
    480480        if (isa<If>(stmt) || isa<While>(stmt)) {
    481481            distribute(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     
    483483            distribute(cast<Variadic>(stmt));
    484484        }
     485        stmt = next;
    485486    }
    486487}
     
    489490 * @brief optimize
    490491 ** ------------------------------------------------------------------------------------------------------------- */
    491 void DistributivePass::optimize(PabloFunction & function) {
    492     DistributivePass::distribute(function.getEntryBlock());
    493     #ifndef NDEBUG
    494     PabloVerifier::verify(function, "post-distribution");
    495     #endif
    496     Simplifier::optimize(function);
    497 }
    498 
    499 
    500 }
     492bool DistributivePass::optimize(PabloFunction & function) {
     493    DistributivePass dp;
     494    unsigned rounds = 0;
     495    for (;;) {
     496        dp.unmodified = true;
     497        dp.distribute(function.getEntryBlock());
     498        if (dp.unmodified) {
     499            break;
     500        }
     501        ++rounds;
     502        #ifndef NDEBUG
     503        PabloVerifier::verify(function, "post-distribution");
     504        #endif
     505        Simplifier::optimize(function);
     506    }
     507    return rounds > 0;
     508}
     509
     510
     511}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.h

    r4922 r4927  
    1010class DistributivePass {
    1111public:
    12     static void optimize(PabloFunction & function);
     12    static bool optimize(PabloFunction & function);
    1313protected:
    14     static void distribute(PabloBlock * const block);
    15     static void distribute(Variadic * const expr);
     14    void distribute(PabloBlock * const block);
     15    void distribute(Variadic * const var);
    1616    DistributivePass() = default;
     17private:
     18    bool unmodified;
    1719};
    1820
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4919 r4927  
    1717#include <bdd.h>
    1818
    19 /// TODO: Investigate why ./icgrep -c -multiplexing-window-size=13,14...,20 "^\p{l}$" causes segfault in BuDDy.
    20 
    2119using namespace llvm;
    2220using namespace boost;
    2321using namespace boost::container;
    2422using namespace boost::numeric::ublas;
     23
     24/// Interesting test case: ./icgrep '[\p{Lm}\p{Meetei_Mayek}]' -disable-if-hierarchy-strategy
    2525
    2626// #define PRINT_DEBUG_OUTPUT
     
    115115    std::random_device rd;
    116116    const RNG::result_type seed = rd();
    117     // const RNG::result_type seed = 83234827342;
     117//    const RNG::result_type seed = 83234827342;
    118118
    119119    LOG("Seed:                    " << seed);
     
    181181        mp.multiplexSelectedSets(function);
    182182        RECORD_TIMESTAMP(end_select_independent_sets);
    183         LOG("SelectedIndependentSets:  " << (end_select_independent_sets - start_select_independent_sets));
    184 
    185         RECORD_TIMESTAMP(start_topological_sort);
    186         MultiplexingPass::topologicalSort(function);
    187         RECORD_TIMESTAMP(end_topological_sort);
    188         LOG("TopologicalSort:          " << (end_topological_sort - start_topological_sort));
     183        LOG("MultiplexSelectedSets:    " << (end_select_independent_sets - start_select_independent_sets));
    189184
    190185        #ifndef NDEBUG
     
    954949 * @brief multiplexSelectedSets
    955950 ** ------------------------------------------------------------------------------------------------------------- */
    956 void MultiplexingPass::multiplexSelectedSets(PabloFunction &) {
     951void MultiplexingPass::multiplexSelectedSets(PabloFunction & function) {
     952    flat_set<PabloBlock *> modified;
    957953    const auto first_set = num_vertices(mConstraintGraph);
    958954    const auto last_set = num_vertices(mMultiplexSetGraph);
     
    971967            Advance * const adv = input[0];
    972968            PabloBlock * const block = adv->getParent(); assert (block);
     969            modified.insert(block);
     970
     971            circular_buffer<PabloAST *> Q(n);
     972
     973            PabloBuilder builder(block);
    973974            block->setInsertPoint(nullptr);
    974             circular_buffer<PabloAST *> Q(n);
    975             PabloBuilder builder(block);
    976975            /// Perform n-to-m Multiplexing           
    977             for (size_t j = 0; j != m; ++j) {
     976            for (size_t j = 0; j != m; ++j) {               
    978977                std::ostringstream prefix;
    979                 prefix << "mux" << n << "to" << m << '.' << (j + 1);
    980 //                Or * muxing = block->createOr(n);
    981 //                for (size_t i = 0; i != n; ++i) {
    982 //                    if (((i + 1) & (1UL << j)) != 0) {
    983 //                        assert (input[i]->getParent() == block);
    984 //                        muxing->addOperand(input[i]->getOperand(0));
    985 //                    }
    986 //                }
     978                prefix << "mux" << n << "to" << m << '.' << (j);
     979                assert (Q.empty());
    987980                for (size_t i = 0; i != n; ++i) {
    988981                    if (((i + 1) & (1UL << j)) != 0) {
     
    995988                    Q.push_back(builder.createOr(a, b));
    996989                }
    997                 PabloAST * muxing =  Q.front(); Q.clear();
     990                PabloAST * const muxing =  Q.front(); Q.clear();
    998991                muxed[j] = builder.createAdvance(muxing, adv->getOperand(1), prefix.str());
    999992                muxed_n[j] = builder.createNot(muxed[j]);
    1000993            }
    1001             /// Perform m-to-n Demultiplexing           
     994            /// Perform m-to-n Demultiplexing
     995            block->setInsertPoint(block->back());
    1002996            for (size_t i = 0; i != n; ++i) {
    1003997                // Construct the demuxed values and replaces all the users of the original advances with them.
     
    10071001                }
    10081002                while (Q.size() > 1) {
    1009                     PabloAST * a = Q.front(); Q.pop_front();
    1010                     PabloAST * b = Q.front(); Q.pop_front();
     1003                    PabloAST * const a = Q.front(); Q.pop_front();
     1004                    PabloAST * const b = Q.front(); Q.pop_front();
    10111005                    Q.push_back(builder.createAnd(a, b));
    10121006                }
    1013                 PabloAST * demuxed =  Q.front(); Q.clear();
    1014 //                And * demuxed = block->createAnd(m);
    1015 //                for (size_t j = 0; j != m; ++j) {
    1016 //                    demuxed->addOperand((((i + 1) & (1UL << j)) != 0) ? muxed[j] : muxed_n[j]);
    1017 //                }
     1007                PabloAST * const demuxed =  Q.front(); Q.clear();
    10181008                input[i]->replaceWith(demuxed, true, true);
    10191009            }
    10201010        }
     1011    }
     1012    for (PabloBlock * block : modified) {
     1013        topologicalSort(block);
    10211014    }
    10221015}
     
    10651058
    10661059/** ------------------------------------------------------------------------------------------------------------- *
    1067  * @brief OrderingVerifier
    1068  ** ------------------------------------------------------------------------------------------------------------- */
    1069 struct OrderingVerifier {
    1070     OrderingVerifier() : mParent(nullptr) {}
    1071     OrderingVerifier(const OrderingVerifier & parent) : mParent(&parent) {}
    1072     bool count(const PabloAST * expr) const {
    1073         if (mSet.count(expr)) {
    1074             return true;
    1075         } else if (mParent) {
    1076             return mParent->count(expr);
    1077         }
    1078         return false;
    1079     }
    1080     void insert(const PabloAST * expr) {
    1081         mSet.insert(expr);
    1082     }
    1083 private:
    1084     const OrderingVerifier * const mParent;
    1085     std::unordered_set<const PabloAST *> mSet;
    1086 };
    1087 
    1088 /** ------------------------------------------------------------------------------------------------------------- *
    10891060 * @brief topologicalSort
    10901061 ** ------------------------------------------------------------------------------------------------------------- */
    1091 void MultiplexingPass::topologicalSort(PabloFunction & function) {
    1092     OrderingVerifier set;
    1093     set.insert(PabloBlock::createZeroes());
    1094     set.insert(PabloBlock::createOnes());
    1095     for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
    1096         set.insert(function.getParameter(i));
    1097     }
    1098     topologicalSort(function.getEntryBlock(), set);
    1099 }
    1100 
    1101 /** ------------------------------------------------------------------------------------------------------------- *
    1102  * @brief topologicalSort
    1103  ** ------------------------------------------------------------------------------------------------------------- */
    1104 void MultiplexingPass::topologicalSort(PabloBlock * block, OrderingVerifier & parent) {
    1105     OrderingVerifier encountered(parent);
    1106     for (Statement * stmt = block->front(); stmt; ) {
     1062void MultiplexingPass::topologicalSort(PabloBlock * const block) {
     1063
     1064    using Vertex = OrderingGraph::vertex_descriptor;
     1065
     1066    OrderingGraph G;
     1067    OrderingMap M;
     1068
     1069    for (Statement * stmt : *block ) {
     1070        const auto u = add_vertex(G);
     1071        G[u] = stmt;
     1072        M.emplace(stmt, u);
    11071073        if (LLVM_UNLIKELY(isa<If>(stmt))) {
    1108             topologicalSort(cast<If>(stmt)->getBody(), encountered);
    11091074            for (Assign * def : cast<If>(stmt)->getDefined()) {
    1110                 encountered.insert(def);
     1075                M.emplace(def, u);
    11111076            }
    11121077        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    1113             topologicalSort(cast<While>(stmt)->getBody(), encountered);
    11141078            for (Next * var : cast<While>(stmt)->getVariants()) {
    1115                 encountered.insert(var);
    1116             }
    1117         }
    1118         bool unmodified = true;
     1079                M.emplace(var, u);
     1080            }
     1081        }
     1082    }
     1083
     1084    Vertex u = 0;
     1085    for (Statement * stmt : *block ) {
     1086
    11191087        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    11201088            PabloAST * const op = stmt->getOperand(i);
    1121             if (LLVM_UNLIKELY(encountered.count(op) == 0 && isa<Statement>(op))) {
    1122                 Statement * const next = stmt->getNextNode();
    1123                 Statement * pos = cast<Statement>(op);
    1124                 if (cast<Statement>(op)->getParent() != block) {
    1125                     // If we haven't already encountered the Assign or Next node, it must come from a If or
    1126                     // While node that we haven't processed yet. Scan ahead and try to locate it.
    1127                     pos = nullptr;
    1128                     if (isa<Assign>(pos)) {
    1129                         for (pos = cast<Statement>(op); pos; pos = pos->getNextNode()) {
    1130                             if (LLVM_UNLIKELY(isa<If>(pos))) {
    1131                                 const auto & defs = cast<If>(pos)->getDefined();
    1132                                 if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), op) != defs.end())) {
    1133                                     break;
    1134                                 }
    1135                             }
    1136                         }
    1137                     } else if (isa<Next>(pos)) {
    1138                         for (pos = cast<Statement>(op); pos; pos = pos->getNextNode()) {
    1139                             if (LLVM_UNLIKELY(isa<While>(pos))) {
    1140                                 const auto & vars = cast<While>(pos)->getVariants();
    1141                                 if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), op) != vars.end())) {
    1142                                     break;
    1143                                 }
    1144                             }
    1145                         }
    1146                     }
    1147                     if (LLVM_UNLIKELY(pos == nullptr)) {
    1148                         throw std::runtime_error("Unexpected error: MultiplexingPass failed to topologically sort the function!");
    1149                     }
    1150                 }
    1151                 stmt->insertAfter(pos);
    1152                 stmt = next;
    1153                 unmodified = false;
    1154                 break;
    1155             }
    1156         }
    1157         if (unmodified) {
    1158             encountered.insert(stmt);
    1159             stmt = stmt->getNextNode();
     1089            if (isa<Statement>(op)) {
     1090                auto f = M.find(cast<Statement>(op));
     1091                if (f != M.end()) {
     1092                    add_edge(f->second, u, G);
     1093                }
     1094            }
     1095        }
     1096
     1097        if (LLVM_UNLIKELY(isa<If>(stmt))) {
     1098            for (Assign * def : cast<If>(stmt)->getDefined()) {
     1099                topologicalSort(u, block, def, G, M);
     1100            }
     1101        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
     1102            for (Next * var : cast<While>(stmt)->getVariants()) {
     1103                topologicalSort(u, block, var, G, M);
     1104            }
     1105        } else {
     1106            topologicalSort(u, block, stmt, G, M);
     1107        }
     1108
     1109        ++u;
     1110
     1111    }
     1112
     1113    circular_buffer<Vertex> Q(num_vertices(G));
     1114    topological_sort(G, std::back_inserter(Q));
     1115
     1116    block->setInsertPoint(nullptr);
     1117    while (Q.size() > 0) {
     1118        const Vertex u = Q.back(); Q.pop_back();
     1119        block->insert(G[u]);
     1120    }
     1121
     1122}
     1123
     1124/** ------------------------------------------------------------------------------------------------------------- *
     1125 * @brief topologicalSort
     1126 ** ------------------------------------------------------------------------------------------------------------- */
     1127void MultiplexingPass::topologicalSort(const OrderingGraph::vertex_descriptor u, const PabloBlock * const block, const Statement * const stmt, OrderingGraph & G, OrderingMap & M) {
     1128    for (const PabloAST * user : stmt->users()) {
     1129        if (LLVM_LIKELY(isa<Statement>(user))) {
     1130            const Statement * use = cast<Statement>(user);
     1131            auto f = M.find(use);
     1132            if (LLVM_UNLIKELY(f == M.end())) {
     1133                const PabloBlock * parent = use->getParent();
     1134                for (;;) {
     1135                    if (parent == block) {
     1136                        break;
     1137                    }
     1138                    use = parent->getBranch();
     1139                    parent = parent->getParent();
     1140                    if (parent == nullptr) {
     1141                        return;
     1142                    }
     1143                }
     1144                f = M.find(use);
     1145                assert (f != M.end());
     1146                M.emplace(use, f->second);
     1147            }
     1148            const auto v = f->second;
     1149            if (LLVM_UNLIKELY(u != v)) {
     1150                add_edge(u, v, G);
     1151            }
    11601152        }
    11611153    }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4919 r4927  
    1212#include <stdint.h>
    1313#include <llvm/ADT/DenseMap.h>
     14#include <llvm/ADT/DenseSet.h>
    1415
    1516typedef int BDD;
     
    1920class PabloBuilder;
    2021class PabloFunction;
    21 struct OrderingVerifier;
    2222
    2323class MultiplexingPass {
     
    3535    using CliqueSet = boost::container::flat_set<CliqueGraph::vertex_descriptor>;
    3636    using CliqueSets = boost::container::flat_set<std::vector<CliqueGraph::vertex_descriptor>>;
     37    using OrderingGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, Statement *>;
     38    using OrderingMap = boost::container::flat_map<const Statement *, OrderingGraph::vertex_descriptor>;
    3739
    3840    using AdvanceVector = std::vector<Advance *>;
     
    7678    void multiplexSelectedSets(PabloFunction & function);
    7779
    78     static void topologicalSort(PabloFunction & function);
    79     static void topologicalSort(PabloBlock * block, OrderingVerifier & parent);
     80    static void topologicalSort(PabloBlock * const block);
     81    static void topologicalSort(const OrderingGraph::vertex_descriptor u, const PabloBlock * const block, const Statement * const stmt, OrderingGraph & G, OrderingMap & M);
    8082
    8183    BDD & get(const PabloAST * const expr);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4925 r4927  
    4040    // Ensure all operands of a reassociatiable function are consistently ordered.
    4141    std::sort(var->begin(), var->end());
     42
    4243    // Apply the idempotence law to any And and Or statement and the identity law to any Xor
    4344    for (int i = var->getNumOperands() - 1; i > 0; --i) {
    44         if (LLVM_UNLIKELY(var->getOperand(i) == var->getOperand(i - 1))) {
     45        if (LLVM_UNLIKELY(equals(var->getOperand(i), var->getOperand(i - 1)))) {
    4546            var->removeOperand(i);
    4647            if (LLVM_UNLIKELY(isa<Xor>(var))) {
     
    122123                                    // Although we can apply this transformation, we have a potential problem. If P is not a "literal", we
    123124                                    // cannot optimize var without creating a new And/Or statement. However, the redundancy elimination
    124                                     // pass will miss this new statement unless we mark "var" as its own replacement.
     125                                    // pass will miss this new statement unless we mark "var" as its own replacement. We'll end up checking
     126                                    // "var" again but termination is still guaranteed once none of the new statements can be replaced by
     127                                    // prior statements in the AST.
    125128                                    PabloAST * expr = nullptr;
    126129                                    if (operands == 2) {
     
    145148                                        replacement = var;
    146149                                    }
    147                                     var->setOperand(j, expr);
    148150                                    var->removeOperand(i);
    149                                     i = 0;
     151                                    var->removeOperand(j);
     152                                    bool unique = true;
     153                                    for (unsigned k = 0; k != var->getNumOperands(); ++k) {
     154                                        if (LLVM_UNLIKELY(equals(var->getOperand(k), expr))) {
     155                                            unique = false;
     156                                            break;
     157                                        }
     158                                    }
     159                                    if (LLVM_LIKELY(unique)) {
     160                                        var->addOperand(expr);
     161                                    }
     162                                    i -= 2;
    150163                                    break; // out of for j = 0 to i - 1
    151164                                }
     
    213226        }
    214227
    215         if (LLVM_UNLIKELY(replacement != nullptr)) {
    216             // Ensure all operands of a reassociatiable function are consistently ordered.
    217             std::sort(var->begin(), var->end());
    218             // Apply the idempotence law to any And and Or statement
    219             for (int i = var->getNumOperands() - 1; i > 0; --i) {
    220                 if (LLVM_UNLIKELY(var->getOperand(i) == var->getOperand(i - 1))) {
    221                     var->removeOperand(i);
    222                 }
    223             }
    224         }
    225 
    226228    }
    227229
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4922 r4927  
    1111class Simplifier {
    1212    friend class DistributivePass;
     13    friend class FactorizeDFG;
    1314public:
    1415    static bool optimize(PabloFunction & function);
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r4925 r4927  
    265265        mCarryManager->storeCarryOutSummary();
    266266    }
    267     mCarryManager->blendCarrySummaryWithOuterSummary();
     267    mCarryManager->addOuterSummaryToNestedSummary();
    268268
    269269    iBuilder->CreateBr(ifEndBlock);
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.cpp

    r4922 r4927  
    1010#include <boost/graph/adjacency_matrix.hpp>
    1111#include <queue>
     12#include <llvm/Support/CommandLine.h>
    1213
    1314#include <pablo/printer_pablos.h>
     
    1617using namespace boost;
    1718using namespace boost::container;
     19
     20//static cl::opt<unsigned> RematerializationThreshold("factoring-remat", cl::desc("Number of registers available for factoring rematerialization"), cl::init(16));
    1821
    1922namespace pablo {
     
    454457}
    455458
    456 //inline void print(PabloAST * expr, raw_ostream & out) {
    457 //    if (isa<Statement>(expr)) {
    458 //        PabloPrinter::print(cast<Statement>(expr), out);
    459 //    } else {
    460 //        PabloPrinter::print(expr, out);
     459///** ------------------------------------------------------------------------------------------------------------- *
     460// * @brief rematerialize
     461// ** ------------------------------------------------------------------------------------------------------------- */
     462//void FactorizeDFG::rematerialize(PabloBlock * const block, LiveSet & priorSet) {
     463
     464//    LiveSet liveSet(priorSet);
     465
     466//    Statement * stmt = block->front();
     467//    block->setInsertPoint(nullptr);
     468//    while (stmt) {
     469//        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     470//            PabloAST * const op = stmt->getOperand(i);
     471//            auto f = std::find(liveSet.begin(), liveSet.end(), op);
     472//            if (f != liveSet.end()) {
     473//                liveSet.erase(f);
     474//                liveSet.push_back(op);
     475//            } else if (isa<Variadic>(op)) {
     476//                Variadic * const var = cast<Variadic>(op);
     477//                const double minimum = 4.0 + (3.0 / (double)var->getNumUses());
     478//                if ((double)(var->getNumOperands()) < minimum) {
     479//                    if (std::find(liveSet.begin(), liveSet.end(), var) == liveSet.end()) {
     480//                        // If we don't have this value in the live set, test whether it is cheaper to recompute it
     481//                        // rather than spill and reload it; if so, rematerialize the value and replace its reachable users.
     482//                        bool rematerialize = true;
     483//                        for (unsigned j = 0; j != var->getNumOperands(); ++j) {
     484//                            if (std::find(liveSet.begin(), liveSet.end(), var->getOperand(j)) == liveSet.end()) {
     485//                                rematerialize = false;
     486//                                break;
     487//                            }
     488//                        }
     489//                        if (rematerialize) {
     490//                            Variadic * replacement = nullptr;
     491//                            if (isa<And>(var)) {
     492//                                replacement = block->createAnd(var->begin(), var->end());
     493//                            } else if (isa<Or>(var)) {
     494//                                replacement = block->createOr(var->begin(), var->end());
     495//                            } else if (isa<Xor>(var)) {
     496//                                replacement = block->createXor(var->begin(), var->end());
     497//                            }
     498//                            raw_os_ostream out(std::cerr);
     499//                            out << "Remateralizing ";
     500//                            PabloPrinter::print(var, out);
     501//                            out << " as ";
     502//                            PabloPrinter::print(replacement, out);
     503//                            out << '\n';
     504//                            out.flush();
     505//                            for (PabloAST * user : var->users()) {
     506//                                if (LLVM_LIKELY(isa<Statement>(user))) {
     507//                                    PabloBlock * parent = cast<Statement>(user)->getParent();
     508//                                    while (parent) {
     509//                                        if (parent == block) {
     510//                                            stmt->replaceUsesOfWith(var, replacement);
     511//                                            break;
     512//                                        }
     513//                                        parent = parent->getParent();
     514//                                    }
     515//                                }
     516//                            }
     517//                            if (liveSet.size() > RematerializationThreshold) {
     518//                                liveSet.pop_front();
     519//                            }
     520//                            liveSet.push_back(replacement);
     521//                        }
     522//                    }
     523//                }
     524//            }
     525//        }
     526//        if (liveSet.size() > RematerializationThreshold) {
     527//            liveSet.pop_front();
     528//        }
     529//        liveSet.push_back(stmt);
     530
     531//        if (isa<If>(stmt) || isa<While>(stmt)) {
     532//            rematerialize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), liveSet);
     533//        }
     534//        block->setInsertPoint(stmt);
     535//        stmt = stmt->getNextNode();
    461536//    }
     537
     538//    // Let the prior set be an intersection between it and the current live set.
     539//    for (auto i = priorSet.begin(); i != priorSet.end(); ) {
     540//        if (LLVM_LIKELY(std::find(liveSet.begin(), liveSet.end(), *i) == liveSet.end())) {
     541//            i = priorSet.erase(i);
     542//        } else {
     543//            ++i;
     544//        }
     545//    }
     546
     547
    462548//}
    463549
     550///** ------------------------------------------------------------------------------------------------------------- *
     551// * @brief rematerialize
     552// ** ------------------------------------------------------------------------------------------------------------- */
     553//inline void FactorizeDFG::rematerialize(PabloFunction & function) {
     554//    LiveSet live;
     555//    rematerialize(function.getEntryBlock(), live);
     556//}
     557
     558
    464559/** ------------------------------------------------------------------------------------------------------------- *
    465560 * @brief lower
    466  *
    467  * The goal of this function is to try and lower a variadic operation into binary form while attempting to mitigate
    468  * register pressure under the assumption that LLVM is not going to significantly change the IR (which was observed
    469  * when assessing the ASM output of LLVM 3.6.1 using O3.)
    470  ** ------------------------------------------------------------------------------------------------------------- */
    471 inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) const {
     561 ** ------------------------------------------------------------------------------------------------------------- */
     562inline PabloAST * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) const {
    472563
    473564    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *, unsigned>;
     
    493584    M.emplace(var, operands);
    494585
    495     for (Vertex u = 0; u != operands; ++u) {
    496         PabloAST * const op = var->getOperand(u);
    497         G[u] = op;
    498         M.emplace(op, u);
     586    for (Vertex i = 0; i < operands; ++i) {
     587        PabloAST * const op = var->getOperand(i);
     588        G[i] = op;
     589        M.emplace(op, i);
    499590        assert ("AST structural error!" && (op->getNumUses() > 0));
    500591        for (PabloAST * user : op->users()) {
     
    512603                            v = f->second;
    513604                        }
    514                         G[add_edge(u, v, G).first] = 0;
     605                        G[add_edge(i, v, G).first] = 0;
    515606                        break;
    516607                    }
    517608                    usage = scope->getBranch();
     609                    assert (scope != scope->getParent());
    518610                    scope = scope->getParent();
    519611                }
     
    522614    }
    523615
    524     assert (M.count(var) == 1);
    525 
    526     unsigned estQuantum = 0;
     616    unsigned time = 0;
    527617    circular_buffer<std::pair<unsigned, Vertex>> defs(operands);
    528618    for (Statement * stmt : *block) {
     
    531621            case TypeId::Or:
    532622            case TypeId::Xor:
    533                 estQuantum += BOOLEAN_STEP;
     623                assert (stmt->getNumOperands() == 2 || stmt == var);
     624                time += BOOLEAN_STEP;
    534625                break;
    535626            case TypeId::Not:
    536                 estQuantum += NOT_STEP;
     627                time += NOT_STEP;
    537628                break;
    538629            default:
    539                 estQuantum += OTHER_STEP;
     630                time += OTHER_STEP;
    540631        }
    541632        auto f = M.find(stmt);
     
    547638            }
    548639            for (auto e : make_iterator_range(in_edges(u, G)))   {
    549                 G[e] = estQuantum;
     640                G[e] = time;
    550641            }
    551642            if (u < operands) {
    552                 defs.push_back(std::make_pair(estQuantum + DESIRED_GAP, u));
    553             }
    554         }
     643                defs.push_back(std::make_pair(time + DESIRED_GAP, u));
     644            }
     645        }
     646        assert (stmt != var);
    555647        // Annotate G to indicate when we expect a statement will be available
    556648        while (defs.size() > 0) {
    557             unsigned availQuantum = 0;
     649            unsigned avail = 0;
    558650            Vertex u = 0;
    559             std::tie(availQuantum, u) = defs.front();
    560             if (availQuantum > estQuantum) {
     651            std::tie(avail, u) = defs.front();
     652            if (avail > time) {
    561653                break;
    562654            }
     
    570662                v = f->second;
    571663            }
    572             G[add_edge(u, v, G).first] = estQuantum;
     664            G[add_edge(u, v, G).first] = time;
    573665        }
    574666    }
     
    588680
    589681    for (auto e : make_iterator_range(in_edges(operands, G)))   {
    590         G[e] = estQuantum;
     682        G[e] = time;
    591683    }
    592684
    593685    assert (num_edges(G) == var->getNumOperands());
    594 
    595 //    raw_os_ostream out(std::cerr);
    596 
    597 //    out << "==============================================================================\n";
    598 //    PabloPrinter::print(var, out); out << '\n';
    599 //    out << "------------------------------------------------------------------------------\n";
    600 
    601 //    out << "digraph G {\n";
    602 //    for (auto u : make_iterator_range(vertices(G))) {
    603 //        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    604 //            continue;
    605 //        }
    606 //        out << "v" << u << " [label=\"" << u << ": ";
    607 //        PabloPrinter::print(G[u], out);
    608 //        out << "\"];\n";
    609 //    }
    610 //    for (auto e : make_iterator_range(edges(G))) {
    611 //        const auto s = source(e, G);
    612 //        const auto t = target(e, G);
    613 //        out << "v" << s << " -> v" << t << "[label=\"" << G[e] << "\"];\n";
    614 //    }
    615 
    616 //    out << "}\n\n";
    617 //    out.flush();
    618 
    619 //    out << "------------------------------------------------------------------------------\n";
    620686
    621687    SchedulingPriorityQueue Q;
     
    623689
    624690        Graph::edge_descriptor f;
    625         unsigned quantum = std::numeric_limits<unsigned>::max();
     691        unsigned t = std::numeric_limits<unsigned>::max();
    626692        for (auto e : make_iterator_range(edges(G))) {
    627693            if (in_degree(source(e, G), G) == 0) {
    628                 if (quantum > G[e]) {
    629                     quantum = G[e];
     694                if (t > G[e]) {
     695                    t = G[e];
    630696                    f = e;
    631697                }
     
    633699        }
    634700
    635         assert ("No edge selected!" && (quantum < std::numeric_limits<unsigned>::max()));
     701        assert ("No edge selected!" && (t < std::numeric_limits<unsigned>::max()));
    636702
    637703        const auto u = source(f, G);
     
    646712        block->setInsertPoint(cast<Statement>(G[v]));
    647713        if (LLVM_LIKELY(Q.size() > 0)) {
    648             unsigned minQuantum = 0; PabloAST * op2 = nullptr;
    649             std::tie(minQuantum, op2) = Q.top();
    650             if (minQuantum < quantum) {
     714            unsigned min = 0; PabloAST * op2 = nullptr;
     715            std::tie(min, op2) = Q.top();
     716            if (min < t) {
    651717                Q.pop();
    652718                PabloAST * result = nullptr;
     
    658724                    result = block->createXor(op1, op2);
    659725                }
    660 
    661 //                out << " -- ";
    662 //                print(op1, out);
    663 //                out << " + ";
    664 //                print(op2, out);
    665 //                out << " -> ";
    666 //                print(result, out);
    667 //                out << '\n';
    668 //                out.flush();
    669 
    670726                if (LLVM_LIKELY(isa<Statement>(result))) {
    671727                    G[v] = result; // update the insertion point node value
    672                     quantum += DESIRED_GAP;
     728                    t += DESIRED_GAP;
    673729                } else {
    674730                    G[v] = cast<Statement>(op2); // update the insertion point node value
    675                     quantum = estQuantum;
    676                 }
    677                 Q.emplace(quantum, result);
     731                    t = time;
     732                }
     733                Q.emplace(t, result);
    678734                continue;
    679735            }
    680736        }
    681         Q.emplace(quantum, op1);
    682     }
    683 
    684 //    out << "------------------------------------------------------------------------------\n";
     737        Q.emplace(t, op1);
     738    }
    685739
    686740    // If we've done our best to schedule the statements and have operands remaining in our queue, generate a
     
    705759            result = block->createXor(op1, op2);
    706760        }
    707 
    708 //        out << " -- ";
    709 //        print(op1, out);
    710 //        out << " + ";
    711 //        print(op2, out);
    712 //        out << " -> ";
    713 //        print(result, out);
    714 //        out << '\n';
    715 //        out.flush();
    716 
    717761        Q.emplace(q2 + DESIRED_GAP, result);
    718762    }
    719763
    720764    assert (Q.size() == 1);
    721     return var->replaceWith(std::get<1>(Q.top()));
     765    return std::get<1>(Q.top());
    722766}
    723767
     
    730774        if (isa<If>(stmt) || isa<While>(stmt)) {
    731775            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    732         } else if ((stmt->getNumOperands() > 2) && (isa<Variadic>(stmt))) {
    733             stmt = lower(cast<Variadic>(stmt), block);
     776        } else if (LLVM_UNLIKELY(stmt->getNumOperands() > 2 && isa<Variadic>(stmt))) {
     777            PabloAST * const replacement = lower(cast<Variadic>(stmt), block);
     778            stmt = stmt->replaceWith(replacement);
     779            if (LLVM_LIKELY(isa<Variadic>(replacement))) {
     780                elevate(cast<Variadic>(replacement), block);
     781            }
    734782            continue;
    735783        }
     
    739787
    740788/** ------------------------------------------------------------------------------------------------------------- *
    741  * @brief lower
     789 * @brief elevate
    742790 ** ------------------------------------------------------------------------------------------------------------- */
    743791inline void FactorizeDFG::lower(PabloFunction & function) const {
    744792    lower(function.getEntryBlock());
     793}
     794
     795/** ------------------------------------------------------------------------------------------------------------- *
     796 * @brief noUsesOfAfter
     797 ** ------------------------------------------------------------------------------------------------------------- */
     798static bool noUsesOfAfter(const PabloAST * value, const Statement * const stmt) {
     799    if (value->getNumUses() == 1) {
     800        return true;
     801    }
     802    for (const Statement * after = stmt->getNextNode(); after; after = after->getNextNode()) {
     803        for (unsigned i = 0; i != after->getNumOperands(); ++i) {
     804            if (LLVM_UNLIKELY(after->getOperand(i) == value)) {
     805                return false;
     806            }
     807        }
     808    }
     809    return true;
     810}
     811
     812/** ------------------------------------------------------------------------------------------------------------- *
     813 * @brief elevate
     814 ** ------------------------------------------------------------------------------------------------------------- */
     815inline void FactorizeDFG::elevate(Variadic * const var, PabloBlock * block) const {
     816    assert (var->getParent() == block);
     817    const unsigned operands = var->getNumOperands();
     818    PabloAST * operand[operands];
     819    unsigned count = 0;
     820    for (unsigned i = 0; i != operands; ++i) {
     821        PabloAST * const op = var->getOperand(i);
     822        if (noUsesOfAfter(op, var)) {
     823            operand[count++] = op;
     824        }
     825    }
     826    if (count) {
     827        PabloAST * def[operands];
     828        for (unsigned i = 0; i != operands; ++i) {
     829            PabloAST * op = var->getOperand(i);
     830            if (LLVM_LIKELY(isa<Statement>(op))) {
     831                PabloBlock * scope = cast<Statement>(op)->getParent();
     832                while (scope) {
     833                    if (scope == block) {
     834                        break;
     835                    }
     836                    op = scope->getBranch();
     837                    scope = scope->getParent();
     838                }
     839            }
     840            def[i] = op;
     841        }
     842        std::sort(operand, operand + count);
     843        std::sort(def, def + operands);
     844        for (Statement * ip = var->getPrevNode(); ip; ip = ip->getPrevNode()) {
     845            if (std::binary_search(def, def + operands, ip)) {
     846                var->insertAfter(ip);
     847                return;
     848            }
     849            for (unsigned i = 0; i != ip->getNumOperands(); ++i) {
     850                if (std::binary_search(operand, operand + count, ip->getOperand(i))) {
     851                    var->insertAfter(ip);
     852                    return;
     853                }
     854            }
     855        }
     856    }
     857}
     858
     859/** ------------------------------------------------------------------------------------------------------------- *
     860 * @brief elevate
     861 ** ------------------------------------------------------------------------------------------------------------- */
     862void FactorizeDFG::elevate(PabloBlock * const block) const {
     863    Statement * stmt = block->front();
     864    while (stmt) {
     865        Statement * next = stmt->getNextNode();
     866        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     867            elevate(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     868        } else if (LLVM_LIKELY(isa<Variadic>(stmt))) {
     869            elevate(cast<Variadic>(stmt), block);
     870        }
     871        stmt = next;
     872    }
     873}
     874
     875/** ------------------------------------------------------------------------------------------------------------- *
     876 * @brief elevate
     877 ** ------------------------------------------------------------------------------------------------------------- */
     878inline void FactorizeDFG::elevate(PabloFunction & function) const {
     879    elevate(function.getEntryBlock());
    745880}
    746881
     
    799934    Simplifier::optimize(function);
    800935
     936    ldfg.elevate(function);
     937    #ifndef NDEBUG
     938    PabloVerifier::verify(function, "post-elevation");
     939    #endif
     940
    801941    ldfg.lower(function);
    802942    #ifndef NDEBUG
    803943    PabloVerifier::verify(function, "post-lowering");
    804944    #endif
    805     Simplifier::optimize(function);
    806 }
    807 
    808 }
     945}
     946
     947}
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.h

    r4922 r4927  
    77#include <pablo/pabloAST.h>
    88#include <vector>
     9#include <deque>
    910
    1011namespace pablo {
     
    2425    using BicliqueSet = std::vector<Biclique>;
    2526    using CheckSet = boost::container::flat_set<PabloAST *>;
     27    using LiveSet = std::deque<PabloAST *>;
    2628    using TypeId = PabloAST::ClassTypeId;
    2729public:
     
    4850    void factor(PabloFunction & function);
    4951
     52//    void rematerialize(PabloBlock * const block, LiveSet & priorSet);
     53//    void rematerialize(PabloFunction & function);
     54
     55    void elevate(PabloFunction & function) const;
     56    void elevate(PabloBlock * const block) const;
     57    void elevate(Variadic * const var, PabloBlock * block) const;
     58
    5059    void lower(PabloFunction & function) const;
    5160    void lower(PabloBlock * const block) const;
    52     Statement * lower(Variadic * const var, PabloBlock * block) const;
     61    PabloAST * lower(Variadic * const var, PabloBlock * block) const;
    5362
    5463    FactorizeDFG() = default;
Note: See TracChangeset for help on using the changeset viewer.