Changeset 4741


Ignore:
Timestamp:
Aug 23, 2015, 10:50:34 AM (4 years ago)
Author:
nmedfort
Message:

More work on the reassociation pass.

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4736 r4741  
    6161endif()
    6262
    63 SET(PABLO_SRC pablo/pabloAST.cpp pablo/ps_if.cpp pablo/ps_while.cpp pablo/function.cpp pablo/codegenstate.cpp pablo/builder.cpp pablo/symbol_generator.cpp pablo/carry_data.cpp pablo/printer_pablos.cpp)
    64 SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_compiler.cpp pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/pablo_codesinking.cpp pablo/carry_manager.cpp IDISA/idisa_builder.cpp)
     63SET(PABLO_SRC pablo/pabloAST.cpp pablo/ps_if.cpp pablo/ps_while.cpp pablo/function.cpp pablo/codegenstate.cpp pablo/builder.cpp pablo/symbol_generator.cpp pablo/printer_pablos.cpp)
     64SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_compiler.cpp pablo/carry_manager.cpp pablo/carry_data.cpp IDISA/idisa_builder.cpp)
     65SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/pablo_codesinking.cpp pablo/optimizers/booleanreassociationpass.cpp)
    6566IF (ENABLE_MULTIPLEXING)
    66 SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_automultiplexing.cpp pablo/optimizers/pablo_bddminimization.cpp pablo/optimizers/booleanreassociationpass.cpp)
     67SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_automultiplexing.cpp pablo/optimizers/pablo_bddminimization.cpp)
    6768ENDIF()
    6869
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r4665 r4741  
    335335UCD/resolve_properties.h
    336336generate_predefined_ucd_functions.cpp
     337pablo/optimizers/booleanreassociationpass.cpp
     338pablo/optimizers/booleanreassociationpass.h
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4738 r4741  
    4444 ** ------------------------------------------------------------------------------------------------------------- */
    4545static inline size_t ceil_log2(const size_t n) {
    46     return std::log2<size_t>(n) + (is_power_of_2(n) ? 1 : 0);
     46    return std::log2<size_t>(n) + (is_power_of_2(n) ? 0 : 1);
     47}
     48
     49/** ------------------------------------------------------------------------------------------------------------- *
     50 * @brief isACD
     51 ** ------------------------------------------------------------------------------------------------------------- */
     52static inline bool isaBooleanOperation(const PabloAST * const expr) {
     53    switch (expr->getClassTypeId()) {
     54        case PabloAST::ClassTypeId::And:
     55        case PabloAST::ClassTypeId::Or:
     56        case PabloAST::ClassTypeId::Xor:
     57            return true;
     58        default:
     59            return false;
     60    }
     61}
     62
     63using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     64using Vertex = Graph::vertex_descriptor;
     65
     66/** ------------------------------------------------------------------------------------------------------------- *
     67 * @brief isCutNecessary
     68 ** ------------------------------------------------------------------------------------------------------------- */
     69static inline bool isCutNecessary(const Vertex u, const Vertex v, const Graph & G, const std::vector<unsigned> & component) {
     70    if (LLVM_UNLIKELY(component[u] != component[v])) {
     71        return true;
     72    } else if (LLVM_UNLIKELY(out_degree(v, G) && in_degree(u, G) && G[u]->getClassTypeId() != G[v]->getClassTypeId())) {
     73        return true;
     74    }
     75    return false;
     76}
     77
     78/** ------------------------------------------------------------------------------------------------------------- *
     79 * @brief isCutNecessary
     80 ** ------------------------------------------------------------------------------------------------------------- */
     81static bool print(const Graph & G, const std::vector<unsigned> & component, raw_os_ostream & out) {
     82    bool hasError = false;
     83    out << "digraph G {\n";
     84    unsigned i = 0;
     85    for (auto u : make_iterator_range(vertices(G))) {
     86        out << "u" << u << " [label=\"";
     87        out << i++ << " : ";
     88        PabloPrinter::print(G[u], out);
     89        out << " (" << component[u] << ')';
     90        out << "\"";
     91        if (isaBooleanOperation(G[u]) && (in_degree(u, G) == 1 || in_degree(u, G) > 2)) {
     92            out << " color=red";
     93            hasError = true;
     94        }
     95        out << "];\n";
     96    }
     97    for (auto e : make_iterator_range(edges(G))) {
     98        Vertex u = source(e, G);
     99        Vertex v = target(e, G);
     100        out << "u" << u << " -> u" << v;
     101        if (isCutNecessary(u, v, G, component)) {
     102            out << " [color=red]";
     103            hasError = true;
     104        }
     105        out << ";\n";
     106    }
     107    out << "}\n";
     108    out.flush();
     109    return hasError;
    47110}
    48111
     
    52115void BooleanReassociationPass::scan(PabloBlock & block, Terminals && terminals) {
    53116
    54     using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *>;
    55     using Vertex = Graph::vertex_descriptor;
    56117    using Map = std::unordered_map<PabloAST *, Vertex>;
    57118    using VertexQueue = std::queue<Vertex>;
     
    75136    raw_os_ostream out(std::cerr);
    76137
    77     // PabloBuilder builder(block);
    78 
    79138    out << "=================================================\n";
     139
     140    PabloBuilder builder(block);
    80141
    81142    for (;;) {
     
    84145        Map M;
    85146
     147        // Generate a graph depicting the relationships between the terminals. If the original terminals
     148        // cannot be optimized with this algorithm bypass them in favour of their operands.
     149
     150        VertexQueue Q;
     151
    86152        for (Statement * const term : terminals) {
    87             M.insert(std::make_pair(term, add_vertex(term, G)));
    88         }
    89 
    90         // Generate a graph depicting the relationships between the terminals
    91         for (Statement * const term : terminals) {
    92             const Vertex u = M.find(term)->second;
    93             for (unsigned i = 0; i != term->getNumOperands(); ++i) {
    94                 PabloAST * const var = term->getOperand(i);
    95                 if (LLVM_UNLIKELY(isa<Integer>(var) || isa<String>(var))) {
    96                     continue;
    97                 }
    98                 auto f = M.find(var);
    99                 if (f == M.end()) {
    100                     Vertex v = add_vertex(var, G);
    101                     f = M.insert(std::make_pair(var, v)).first;
    102                     if ((isa<And>(var) || isa<Or>(var) || isa<Xor>(var))) {
    103                         VertexQueue Q;
    104                         // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
    105                         for (Statement * stmt = cast<Statement>(var); ;) {
    106                             for (unsigned i = 0; i != 2; ++i) {
    107                                 PabloAST * op = stmt->getOperand(i);
    108                                 auto f = M.find(op);
    109                                 if (f == M.end()) {
    110                                     const auto w = add_vertex(op, G);
    111                                     f = M.insert(std::make_pair(op, w)).first;
    112                                     if (op->getClassTypeId() == stmt->getClassTypeId() && cast<Statement>(op)->getParent() == &block) {
    113                                         Q.push(w);
    114                                     }
    115                                 }
    116                                 add_edge(f->second, v, G);
    117                             }
    118                             if (Q.empty()) break;
    119                             v = Q.front(); Q.pop();
    120                             stmt = cast<Statement>(G[v]);
     153            if (isaBooleanOperation(term)) {
     154                if (LLVM_LIKELY(M.count(term) == 0)) {
     155                    const auto v = add_vertex(term, G);
     156                    M.insert(std::make_pair(term, v));
     157                    Q.push(v);
     158                }
     159            } else {
     160                for (unsigned i = 0; i != term->getNumOperands(); ++i) {
     161                    PabloAST * const op = term->getOperand(i);
     162                    if (LLVM_LIKELY(isa<Statement>(op) && M.count(op) == 0)) {
     163                        const auto v = add_vertex(op, G);
     164                        M.insert(std::make_pair(op, v));
     165                        Q.push(v);
     166                    }
     167                }
     168            }
     169
     170        }
     171
     172        for (;;) {
     173            const Vertex u = Q.front(); Q.pop();
     174            if (isaBooleanOperation(G[u])) {
     175                // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
     176                Statement * stmt = cast<Statement>(G[u]);
     177                for (unsigned i = 0; i != 2; ++i) {
     178                    PabloAST * op = stmt->getOperand(i);
     179                    auto f = M.find(op);
     180                    if (f == M.end()) {
     181                        const auto v = add_vertex(op, G);
     182                        f = M.insert(std::make_pair(op, v)).first;
     183                        if (op->getClassTypeId() == stmt->getClassTypeId() && cast<Statement>(op)->getParent() == &block) {
     184                            Q.push(v);
    121185                        }
    122186                    }
    123187                    add_edge(f->second, u, G);
    124188                }
     189            }
     190            if (Q.empty()) {
     191                break;
    125192            }
    126193        }
     
    133200        std::vector<unsigned> component(num_vertices(G));
    134201
    135         // unsigned i = 0;
    136 
    137202        for (;;) {
    138203
     
    142207                unsigned id = 0;
    143208                // If this one of our original terminals or a sink in G, it is the root of a new component.
    144                 if (u < terminals.size() || out_degree(u, G) == 0) {
     209                if (out_degree(u, G) == 0) {
    145210                    id = ++count;
    146211                } else {
     
    154219
    155220            if (count > 1) {
    156 
    157 //                if (i++ == 0) {
    158 
    159 //                    out << "digraph G_" << i << " {\n";
    160 //                    unsigned i = 0;
    161 //                    for (auto u : ordering) {
    162 //                        out << "u" << u << " [label=\"";
    163 //                        out << i++ << " : ";
    164 //                        PabloPrinter::print(G[u], out);
    165 //                        out << " (" << component[u] << ')';
    166 //                        out << "\"];\n";
    167 //                    }
    168 //                    for (auto e : make_iterator_range(edges(G))) {
    169 //                        out << "u" << source(e, G) << " -> u" << target(e, G) << ";\n";
    170 //                    }
    171 //                    out << "}\n";
    172 //                    out.flush();
    173 
    174 //                    out << "*************************************************\n";
    175 
    176 //                }
    177 
    178221                // Cut the graph wherever a computation crosses a component
    179222                EdgeQueue Q;
     
    184227                    const Vertex u = source(e, G);
    185228                    const Vertex v = target(e, G);
    186                     if (LLVM_UNLIKELY(component[u] != component[v])) {
     229                    if (LLVM_UNLIKELY(isCutNecessary(u, v, G, component))) {
    187230                        Q.push(std::make_pair(u, v));
    188231                        remove_edge(u, v, G);
     
    207250                        std::swap(u, v);
    208251                    }
    209 
    210 //                    out << " -- replicating ";
    211 //                    PabloPrinter::print(G[u], out);
    212 //                    out << " for component " << component[v] << '\n';
    213 //                    out.flush();
    214252
    215253                    // Replicate u and fix the ordering and component vectors to reflect the change in G.
     
    236274
    237275                }
    238 
    239 //                out << "*************************************************\n";
    240 
    241276                continue; // outer for loop
    242277            }
     
    244279        }
    245280
    246         out << "digraph X {\n";
    247         unsigned i = 0;
    248         for (auto u : ordering) {
    249             out << "u" << u << " [label=\"";
    250             out << i++ << " : ";
    251             PabloPrinter::print(G[u], out);
    252             out << " (" << component[u] << ')';
    253             out << "\"];\n";
    254         }
    255         for (auto e : make_iterator_range(edges(G))) {
    256             out << "u" << source(e, G) << " -> u" << target(e, G) << ";\n";
    257         }
    258         out << "}\n";
    259         out.flush();
     281        if (print(G, component, out)) {
     282            PabloPrinter::print(block.statements(), out);
     283            out.flush();
     284            throw std::runtime_error("Illegal graph generated!");
     285        }
    260286
    261287        // Scan through the graph in reverse order so that we find all subexpressions first
    262         for (auto ui = ordering.rbegin(), ui_end = ordering.rend(); ui != ui_end; ++ui) {
     288        for (auto ui = ordering.begin(); ui != ordering.end(); ++ui) {
    263289            const Vertex u = *ui;
    264290            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    265291
    266                 PabloAST * expr = G[u];
    267 
    268 
    269                 std::array<Vertex, 3> root;
    270                 unsigned count = 0;
    271 
    272                 if (isa<And>(expr) || isa<Or>(expr) || isa<Xor>(expr)) {
    273                     root[count++] = u;
    274                 } else {
    275                     for (auto e : make_iterator_range(in_edges(u, G))) {
    276                         root[count++] = source(e, G);
    277                     }
    278                 }
    279 
    280                 for (unsigned i = 0; i != count; ++i) {
    281                     // While we're collecting our variable set V, keep track of the maximum path length L.
    282                     // If L == ceil(log2(|V|)), then this portion of the AST is already optimal.
    283 
    284                     flat_map<Vertex, unsigned> L;
    285                     flat_set<PabloAST *> V;
    286                     VertexQueue Q;
    287 
    288                     Vertex v = root[i];
    289                     unsigned maxPathLength = 0;
    290                     L.emplace(v, 0);
    291                     for (;;) {
    292                         if (in_degree(v, G) == 0) {
    293                             V.insert(G[v]);
    294                         } else {
    295                             const auto l = L[v] + 1;
    296                             maxPathLength = std::max(maxPathLength, l);
    297                             for (auto e : make_iterator_range(in_edges(v, G))) {
    298                                 const Vertex w = source(e, G);
    299                                 auto f = L.find(w);
    300                                 if (LLVM_LIKELY(f == L.end())) {
    301                                     L.emplace(w, l);
    302                                 } else {
    303                                     f->second = std::max(f->second, l);
    304                                 }
    305                                 Q.push(w);
     292                out << " -- checking component " << component[u] << " : ";
     293                PabloPrinter::print(G[u], out);
     294                out << "\n";
     295                out.flush();
     296
     297                // While we're collecting our variable set V, keep track of the maximum path length L.
     298                // If L == ceil(log2(|V|)), then this portion of the AST is already optimal.
     299
     300                flat_map<Vertex, unsigned> L;
     301                flat_set<PabloAST *> V;
     302                VertexQueue Q;
     303
     304                Vertex v = u;
     305                unsigned maxPathLength = 0;
     306                L.emplace(v, 0);
     307                for (;;) {
     308                    assert (isa<Statement>(G[v]) ? cast<Statement>(G[v])->getParent() != nullptr : true);
     309                    if (in_degree(v, G) == 0) {
     310                        V.insert(G[v]);
     311                    } else {
     312                        const auto l = L[v] + 1;
     313                        maxPathLength = std::max(maxPathLength, l);
     314                        for (auto e : make_iterator_range(in_edges(v, G))) {
     315                            const Vertex w = source(e, G);
     316                            auto f = L.find(w);
     317                            if (LLVM_LIKELY(f == L.end())) {
     318                                L.emplace(w, l);
     319                            } else {
     320                                f->second = std::max(f->second, l);
    306321                            }
    307                         }
    308                         if (Q.empty()) {
    309                             break;
    310                         }
    311                         v = Q.front();
    312                         Q.pop();
    313                     }
    314 
    315                     // Should we optimize this portion of the AST?
    316                     if (maxPathLength != ceil_log2(V.size())) {
    317 
    318 
    319 
    320                     }
    321 
    322 
    323                 }
    324 
    325 
    326 
    327 
    328 
    329             }
    330         }
    331 
    332         // if (u < terminals.size() || out_degree(u, G) == 0) {
    333 
    334         for (auto e : make_iterator_range(edges(G))) {
    335             Vertex u = target(e, G);
    336             Vertex v = source(e, G);
    337             if (u >= terminals.size() && out_degree(v, G) != 0 && G[u]->getClassTypeId() != G[v]->getClassTypeId()) {
    338                 throw std::runtime_error("Illegal graph generated!");
     322                            Q.push(w);
     323                        }
     324                    }
     325                    if (Q.empty()) {
     326                        break;
     327                    }
     328                    v = Q.front();
     329                    Q.pop();
     330                }
     331
     332                // Should we optimize this portion of the AST?
     333                if (maxPathLength > ceil_log2(V.size())) {
     334
     335                    out << " -- rewriting component " << component[u] << " : |P|=" << maxPathLength << ", |V|=" << V.size() << " (" << ceil_log2(V.size()) << ")\n";
     336                    out.flush();
     337
     338                    circular_buffer<PabloAST *> Q(V.size());
     339                    for (PabloAST * var : V) {
     340                        Q.push_back(var);
     341                    }
     342                    Statement * stmt = cast<Statement>(G[u]);
     343
     344                    block.setInsertPoint(stmt->getPrevNode());
     345                    if (isa<And>(stmt)) {
     346                        while (Q.size() > 1) {
     347                            PabloAST * e1 = Q.front(); Q.pop_front();
     348                            PabloAST * e2 = Q.front(); Q.pop_front();
     349                            Q.push_back(builder.createAnd(e1, e2));
     350                        }
     351                    } else if (isa<Or>(stmt)) {
     352                        while (Q.size() > 1) {
     353                            PabloAST * e1 = Q.front(); Q.pop_front();
     354                            PabloAST * e2 = Q.front(); Q.pop_front();
     355                            Q.push_back(builder.createOr(e1, e2));
     356                        }
     357                    } else { // if (isa<Xor>(stmt)) {
     358                        while (Q.size() > 1) {
     359                            PabloAST * e1 = Q.front(); Q.pop_front();
     360                            PabloAST * e2 = Q.front(); Q.pop_front();
     361                            Q.push_back(builder.createXor(e1, e2));
     362                        }
     363                    }
     364                    stmt->replaceWith(Q.front(), true, true);
     365                }
     366
     367                for (auto uj = ui; ++uj != ordering.end(); ) {
     368                    assert (isa<Statement>(G[*uj]) ? cast<Statement>(G[*uj])->getParent() != nullptr : true);
     369                }
     370
    339371            }
    340372        }
     
    363395
    364396        out << "-------------------------------------------------\n";
    365 
    366 
    367 
    368 
    369 
    370 //        if (variables.size() > 3) {
    371 
    372 //            circular_buffer<PabloAST *> Q(variables.size());
    373 
    374 //            out << "-------------------------------------------------\n";
    375 
    376 //            for (auto var : variables) {
    377 //                Q.push_back(var);
    378 
    379 //                out << " -> ";
    380 //                PabloPrinter::print(var, out); out << '\n';
    381 
    382 
    383 
    384 //                if (LLVM_LIKELY(isa<Statement>(var))) {
    385 //                    nextSet.insert(cast<Statement>(var));
    386 //                }
    387 //            }
    388 
    389 
    390 
    391 //            block.setInsertPoint(stmt->getPrevNode());
    392 //            while (Q.size() > 1) {
    393 //                PabloAST * e1 = Q.front(); Q.pop_front();
    394 //                PabloAST * e2 = Q.front(); Q.pop_front();
    395 //                PabloAST * r = nullptr;
    396 //                switch (classTypeId) {
    397 //                    case PabloAST::ClassTypeId::And:
    398 //                        r = builder.createAnd(e1, e2);
    399 //                        break;
    400 //                    case PabloAST::ClassTypeId::Or:
    401 //                        r = builder.createOr(e1, e2);
    402 //                        break;
    403 //                    case PabloAST::ClassTypeId::Xor:
    404 //                        r = builder.createAnd(e1, e2);
    405 //                        break;
    406 //                    default: LLVM_BUILTIN_UNREACHABLE;
    407 //                }
    408 //                Q.push_back(r);
    409 //            }
    410 //            cast<Statement>(op)->replaceWith(Q.front(), true, true);
    411 
    412 //            for (PabloAST * var : variables) {
    413 //                if (isa<Statement>(var) && cast<Statement>(var)->getParent() == &block) {
    414 //                    nextSet.insert(cast<Statement>(var));
    415 //                }
    416 //            }
    417 
    418 //        }
    419 
    420 
    421 
    422 //        if (nextSet.empty()) {
    423 //            break;
    424 //        }
    425 
    426 //        out << "-------------------------------------------------\n";
    427 
    428 //        terminals.assign(nextSet.begin(), nextSet.end());
    429     }
    430 
     397    }
    431398}
    432399
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4736 r4741  
    1818
    1919    using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
     20    using ReverseCharacterizationMap = llvm::DenseMap<const DdNode *, PabloAST *>;
    2021    using Terminals = std::vector<Statement *>;
    2122
     
    6869    std::vector<PabloAST *>         mVariables;
    6970    CharacterizationMap             mCharacterizationMap;
     71    ReverseCharacterizationMap      mLookupMap;
    7072};
    7173
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r4734 r4741  
    159159    // Write the output values out
    160160    for (unsigned i = 0; i != function->getNumOfResults(); ++i) {
    161         assert (function.getResult(i));
     161        assert (function->getResult(i));
    162162        SetOutputValue(mMarkerMap[function->getResult(i)], i);
    163163    }
Note: See TracChangeset for help on using the changeset viewer.