Ignore:
Timestamp:
Sep 15, 2015, 11:33:40 PM (4 years ago)
Author:
nmedfort
Message:

Bug fixes for reassociation pass.

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

Legend:

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

    r4771 r4773  
    33#include <pablo/codegenstate.h>
    44#include <pablo/printer_pablos.h>
     5#include <iostream>
    56#include <unordered_set>
    67
     
    7071
    7172void PabloVerifier::verify(const PabloFunction & function, const bool ignoreUnusedStatements) {
    72     isTopologicallyOrdered(function, ignoreUnusedStatements);
     73    try {
     74        isTopologicallyOrdered(function, ignoreUnusedStatements);
     75    } catch(std::runtime_error err) {
     76        raw_os_ostream out(std::cerr);
     77        PabloPrinter::print(function.getEntryBlock().statements(), out);
     78        out.flush();
     79        throw err;
     80    }
    7381}
    7482
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4772 r4773  
    323323inline void BooleanReassociationPass::processScope(PabloFunction & function, PabloBlock & block) {
    324324    Graph G;
     325    summarizeAST(block, G);
     326    redistributeAST(block, G);
     327    mergeAndWrite(block, G);
     328}
     329
     330/** ------------------------------------------------------------------------------------------------------------- *
     331 * @brief mergeAndWrite
     332 ** ------------------------------------------------------------------------------------------------------------- */
     333void BooleanReassociationPass::mergeAndWrite(PabloBlock & block, Graph & G) {
    325334
    326335    circular_buffer<Vertex> Q(num_vertices(G));
    327336    topological_sort(G, std::back_inserter(Q));
    328337    block.setInsertPoint(nullptr);
     338
     339    flat_set<PabloAST *> alreadyWritten;
    329340
    330341    while (!Q.empty()) {
     
    337348                    stmt = cast<Statement>(replacement);
    338349                } else { // optimization reduced this to a Constant, Var or an outer-scope statement
     350                    std::get<0>(G[u]) = TypeId::Var;
    339351                    continue;
    340352                }
     
    344356            assert (stmt);
    345357            assert (inCurrentBlock(stmt, block));
    346             for (auto e : make_iterator_range(out_edges(u, G))) {
    347                 if (G[e] && G[e] != stmt) {
    348                     PabloAST * expr = std::get<1>(G[target(e, G)]);
    349                     if (expr) { // processing a yet-to-be created value
    350                         cast<Statement>(expr)->replaceUsesOfWith(G[e], stmt);
     358            // make sure that optimization doesn't reduce this to an already written statement
     359            if (alreadyWritten.insert(stmt).second) {
     360                for (auto e : make_iterator_range(out_edges(u, G))) {
     361                    if (G[e] && G[e] != stmt) {
     362                        PabloAST * expr = std::get<1>(G[target(e, G)]);
     363                        if (expr) { // processing a yet-to-be created value
     364                            cast<Statement>(expr)->replaceUsesOfWith(G[e], stmt);
     365                        }
    351366                    }
    352367                }
    353             }
    354             block.insert(stmt);
     368                block.insert(stmt);
     369            }
    355370        }
    356371    }
     
    527542    IntersectionSets B1;
    528543    for (auto u : A) {
    529         VertexSet V;
    530         V.reserve(in_degree(u, G));
    531         for (auto e : make_iterator_range(in_edges(u, G))) {
    532             V.push_back(source(e, G));
    533         }
    534         std::sort(V.begin(), V.end());
    535         B1.insert(std::move(V));
     544        assert (u < num_vertices(G));
     545        if (in_degree(u, G) > 0) {
     546            VertexSet V;
     547            V.reserve(in_degree(u, G));
     548            for (auto e : make_iterator_range(in_edges(u, G))) {
     549                V.push_back(source(e, G));
     550            }
     551            std::sort(V.begin(), V.end());
     552            B1.insert(std::move(V));
     553        }
    536554    }
    537555
     
    577595    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
    578596        VertexSet Ai(A);
    579         for (const Vertex u : *Bi) {
    580             VertexSet Aj;
    581             Aj.reserve(out_degree(u, G));
    582             for (auto e : make_iterator_range(out_edges(u, G))) {
    583                 Aj.push_back(target(e, G));
    584             }
    585             std::sort(Aj.begin(), Aj.end());
    586 
     597        for (const Vertex u : *Bi) {           
    587598            VertexSet Ak;
    588             std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
    589 
     599            if (out_degree(u, G) > 0) {
     600                VertexSet Aj;
     601                Aj.reserve(out_degree(u, G));
     602                for (auto e : make_iterator_range(out_edges(u, G))) {
     603                    Aj.push_back(target(e, G));
     604                }
     605                std::sort(Aj.begin(), Aj.end());
     606                std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
     607            }
    590608            Ai.swap(Ak);
    591609        }
     
    701719
    702720    VertexSet sinks;
    703     for (const Vertex u : make_iterator_range(vertices(G))) {
    704         if (out_degree(u, G) == 0) {
     721    for (const Vertex u : make_iterator_range(vertices(H))) {
     722        if (out_degree(u, H) == 0) {
    705723            sinks.push_back(u);
    706724        }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4771 r4773  
    2828    void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis = nullptr) const;
    2929    void redistributeAST(const PabloBlock & block, Graph & G) const;
     30    void mergeAndWrite(PabloBlock & block, Graph & G);
    3031public:
    3132    static bool isOptimizable(const VertexData & data);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4772 r4773  
    157157        RECORD_TIMESTAMP(end_select_independent_sets);
    158158        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
    159 
    160         RECORD_TIMESTAMP(start_topological_sort);
    161         am.topologicalSort(function.getEntryBlock());
    162         RECORD_TIMESTAMP(end_topological_sort);
    163         LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
    164159    }
    165160
     
    10361031}
    10371032
    1038 /** ------------------------------------------------------------------------------------------------------------- *
    1039  * @brief topologicalSort
    1040  *
    1041  * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
    1042  * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
    1043  * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
    1044  * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
    1045  * it's not necessarily the original ordering.
    1046  ** ------------------------------------------------------------------------------------------------------------- */
    1047 void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
    1048     // Note: not a real topological sort. I expect the original graph to be close to the resulting one. Thus cost
    1049     // of constructing a graph in which to perform the sort takes longer than potentially moving an instruction
    1050     // multiple times.
    1051     std::unordered_set<const PabloAST *> encountered;
    1052     std::stack<Statement *> scope;
    1053 
    1054     for (Statement * stmt = entry.front(); ; ) { restart:
    1055         while ( stmt ) {
    1056             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    1057                 PabloAST * const op = stmt->getOperand(i);
    1058                 if (LLVM_LIKELY(isa<Statement>(op))) {
    1059                     if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
    1060                         if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
    1061                             if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
    1062                                 continue;
    1063                             }
    1064                         }
    1065                         Statement * const next = stmt->getNextNode();
    1066                         Statement * after = cast<Statement>(op);
    1067                         if (LLVM_UNLIKELY(after->getParent() != stmt->getParent())) {
    1068                             if (after->getParent()) {
    1069                                 throw std::runtime_error("Operand is not in the same scope as the statement!");
    1070                             } else {
    1071                                 throw std::runtime_error("Operand is not in any pablo scope!");
    1072                             }
    1073                         }
    1074                         stmt->insertAfter(cast<Statement>(op));
    1075                         stmt = next;
    1076                         goto restart;
    1077                     }
    1078                 }
    1079             }
    1080             if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    1081                 // Set the next statement to be the first statement of the inner scope and push the
    1082                 // next statement of the current statement into the scope stack.
    1083                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    1084                 scope.push(stmt->getNextNode());
    1085                 stmt = nested.front();
    1086                 continue;
    1087             }
    1088 
    1089             encountered.insert(stmt);
    1090             stmt = stmt->getNextNode();
    1091         }
    1092         if (scope.empty()) {
    1093             break;
    1094         }
    1095         stmt = scope.top();
    1096         scope.pop();
    1097     }
    1098 }
    1099 
    11001033} // end of namespace pablo
    11011034
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4738 r4773  
    4848    void applySubsetConstraints();
    4949    void multiplexSelectedIndependentSets();
    50     void topologicalSort(PabloBlock & entry) const;
    5150    inline AutoMultiplexing()
    5251    : mVariables(0)
Note: See TracChangeset for help on using the changeset viewer.