Ignore:
Timestamp:
Sep 27, 2015, 1:32:27 AM (4 years ago)
Author:
nmedfort
Message:

Progress on multi-target UCD compiler.

File:
1 edited

Legend:

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

    r4788 r4797  
    2525using Vertex = Graph::vertex_descriptor;
    2626using VertexData = BooleanReassociationPass::VertexData;
    27 using VertexQueue = circular_buffer<Vertex>;
    2827using Map = BooleanReassociationPass::Map;
    2928using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
     
    4544}
    4645
    47 inline bool has_edge(const Vertex u, const Vertex v, const Graph & G) {
    48     return edge(u, v, G).second == true;
    49 }
    50 
    51 inline bool no_edge(const Vertex u, const Vertex v, const Graph & G) {
    52     return edge(u, v, G).second == false;
    53 }
     46#ifndef NDEBUG
     47static bool no_path(const Vertex u, const Vertex v, const Graph & G) {
     48    if (u == v) return false;
     49    flat_set<Vertex> V;
     50    std::queue<Vertex> Q;
     51    Q.push(u);
     52    for (;;) {
     53        Vertex w = Q.front();
     54        if (w == v) {
     55            return false;
     56        }
     57        Q.pop();
     58        for (auto e : make_iterator_range(out_edges(w, G))) {
     59            Vertex x = target(e, G);
     60            if (V.count(x)) continue;
     61            Q.push(x);
     62            V.insert(x);
     63        }
     64        if (Q.empty()) {
     65            break;
     66        }
     67    }
     68    return true;
     69}
     70#endif
    5471
    5572inline void add_edge(PabloAST * expr, const Vertex u, const Vertex v, Graph & G) {
    56     assert (u != v);
    57     assert (no_edge(v, u, G));
     73    assert (no_path(v, u, G));
    5874    // Make sure each edge is unique
    5975    for (auto e : make_iterator_range(out_edges(u, G))) {
     
    111127}
    112128
    113 inline bool isNegated(const VertexData & data) {
    114     return getType(data) == TypeId::Not && (getValue(data) != nullptr);
     129inline bool isConstant(const VertexData & data) {
     130    switch (getType(data)) {
     131        case TypeId::Zeroes:
     132        case TypeId::Ones:
     133            return true;
     134        default: return false;
     135    }
    115136}
    116137
     
    147168
    148169/** ------------------------------------------------------------------------------------------------------------- *
    149  * @brief intersection_count
    150  ** ------------------------------------------------------------------------------------------------------------- */
    151 template <class Type>
    152 inline unsigned intersection_count(const Type & A, const Type & B) {
    153     auto first1 = A.begin(), last1 = A.end();
    154     auto first2 = B.begin(), last2 = B.end();
    155     unsigned count = 0;
    156     while (first1 != last1 && first2 != last2) {
    157         if (*first1 < *first2) {
    158             ++first1;
    159         } else if (*first2 < *first1) {
    160             ++first2;
    161         } else {
    162             ++count;
    163         }
    164     }
    165     return count;
    166 }
    167 
    168 
    169 /** ------------------------------------------------------------------------------------------------------------- *
    170170 * @brief optimize
    171171 ** ------------------------------------------------------------------------------------------------------------- */
     
    173173    BooleanReassociationPass brp;
    174174    brp.resolveScopes(function);
    175     brp.processScopes(function);
     175    brp.processScopes(function);   
     176    #ifndef NDEBUG
     177    Simplifier::deadCodeElimination(function.getEntryBlock());
     178    PabloVerifier::verify(function, "post-reassociation");
     179    #endif
    176180    Simplifier::optimize(function);
    177181    return true;
     
    232236    M.insert(std::make_pair(value, u));
    233237    return u;
    234 }
    235 
    236 /** ------------------------------------------------------------------------------------------------------------- *
    237  * @brief printGraph
    238  ** ------------------------------------------------------------------------------------------------------------- */
    239 static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) {
    240     raw_os_ostream out(std::cerr);
    241 
    242     std::vector<unsigned> c(num_vertices(G));
    243     strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
    244 
    245     out << "digraph " << name << " {\n";
    246     for (auto u : make_iterator_range(vertices(G))) {
    247         if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    248             continue;
    249         }
    250         out << "v" << u << " [label=\"" << u << ": ";
    251         PabloAST * expr;
    252         TypeId typeId;
    253         std::tie(typeId, expr) = G[u];
    254         bool temporary = false;
    255         bool error = false;
    256         if (expr == nullptr) {
    257             temporary = true;
    258             switch (typeId) {
    259                 case TypeId::And:
    260                     out << "And";
    261                     break;
    262                 case TypeId::Or:
    263                     out << "Or";
    264                     break;
    265                 case TypeId::Xor:
    266                     out << "Xor";
    267                     break;
    268                 default:
    269                     out << "???";
    270                     error = true;
    271                     break;
    272             }
    273         } else if (isMutable(G[u], block)) {
    274             if (LLVM_UNLIKELY(isa<If>(expr))) {
    275                 out << "If ";
    276                 PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
    277                 out << ":";
    278             } else if (LLVM_UNLIKELY(isa<While>(expr))) {
    279                 out << "While ";
    280                 PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
    281                 out << ":";
    282             } else {
    283                 PabloPrinter::print(cast<Statement>(expr), "", out);
    284             }
    285         } else {
    286             PabloPrinter::print(expr, out);
    287         }
    288         out << "\"";
    289         if (!isMutable(G[u], block)) {
    290             out << " style=dashed";
    291         }
    292         if (error) {
    293             out << " color=red";
    294         } else if (temporary) {
    295             out << " color=blue";
    296         }
    297         out << "];\n";
    298     }
    299     for (auto e : make_iterator_range(edges(G))) {
    300         const auto s = source(e, G);
    301         const auto t = target(e, G);
    302         out << "v" << s << " -> v" << t;
    303         bool cyclic = (c[s] == c[t]);
    304         if (G[e] || cyclic) {
    305             out << " [";
    306              if (G[e]) {
    307                 out << "label=\"";
    308                 PabloPrinter::print(G[e], out);
    309                 out << "\" ";
    310              }
    311              if (cyclic) {
    312                 out << "color=red ";
    313              }
    314              out << "]";
    315         }
    316         out << ";\n";
    317     }
    318 
    319     if (num_vertices(G) > 0) {
    320 
    321         out << "{ rank=same;";
    322         for (auto u : make_iterator_range(vertices(G))) {
    323             if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    324                 out << " v" << u;
    325             }
    326         }
    327         out << "}\n";
    328 
    329         out << "{ rank=same;";
    330         for (auto u : make_iterator_range(vertices(G))) {
    331             if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    332                 out << " v" << u;
    333             }
    334         }
    335         out << "}\n";
    336 
    337     }
    338 
    339     out << "}\n\n";
    340     out.flush();
    341238}
    342239
     
    386283inline void BooleanReassociationPass::processScope(PabloFunction &, PabloBlock & block) {
    387284    Graph G;
    388     summarizeAST(block, G);
    389     redistributeAST(block, G);
     285    Map M;
     286    summarizeAST(block, G, M);
     287    redistributeAST(block, G, M);
    390288    rewriteAST(block, G);
    391289}
     
    395293 ** ------------------------------------------------------------------------------------------------------------- */
    396294void BooleanReassociationPass::rewriteAST(PabloBlock & block, Graph & G) {
    397 
    398 //    // Clear out the current AST
    399 //    std::vector<Statement *> currentAST;
    400 //    for (Statement * stmt = block.front(); stmt; stmt = stmt->removeFromParent()) {
    401 //        currentAST.push_back(stmt);
    402 //    }
    403295    // Rewrite the AST in accordance to G
    404296    circular_buffer<Vertex> Q(num_vertices(G));
     
    408300    unsigned statementCount = 0;
    409301    WrittenAt writtenAt;
     302    writtenAt.emplace(PabloBlock::createZeroes(), 0);
     303    writtenAt.emplace(PabloBlock::createOnes(), 0);
    410304    while (!Q.empty()) {
    411305        const Vertex u = Q.back();
    412306        Q.pop_back();
    413         // Supress any isolated vertices; the AST must be a single connected component.
     307        // Supress any isolated vertices
    414308        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    415309            continue;
     
    449343        writtenAt.emplace(expr, statementIndex);
    450344    }
    451 //    // Erase any AST node that weren't placed back into the AST
    452 //    for (Statement * stmt : currentAST) {
    453 //        if (stmt->getParent() == nullptr) {
    454 //            stmt->eraseFromParent(true);
    455 //        }
    456 //    }
    457345}
    458346
     
    463351 * are "flattened" (i.e., allowed to have any number of inputs.)
    464352 ** ------------------------------------------------------------------------------------------------------------- */
    465 void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const {
    466     Map M;
     353void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G, Map & M) const {
    467354    // Compute the base def-use graph ...
    468355    for (Statement * stmt : block) {
     
    506393    }
    507394    std::vector<Vertex> mapping(num_vertices(G));
    508     summarizeGraph(block, G, mapping);
     395    summarizeGraph(block, G, mapping, M);
    509396}
    510397
     
    512399 * @brief resolveUsages
    513400 ** ------------------------------------------------------------------------------------------------------------- */
    514 void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis) const {
     401void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, const Statement * const ignoreIfThis) const {
    515402    for (PabloAST * user : expr->users()) {
    516403        assert (user);
     
    550437 * @brief summarizeGraph
    551438 ** ------------------------------------------------------------------------------------------------------------- */
    552 inline void BooleanReassociationPass::summarizeGraph(const PabloBlock &, Graph & G, std::vector<Vertex> & mapping) {
     439inline void BooleanReassociationPass::summarizeGraph(const PabloBlock &, Graph & G, std::vector<Vertex> & mapping, Map &) {
    553440    std::vector<Vertex> reverse_topological_ordering;
    554441    reverse_topological_ordering.reserve(num_vertices(G));
     
    556443    topological_sort(G, std::back_inserter(reverse_topological_ordering));
    557444    assert(mapping.size() >= num_vertices(G));
    558     for (const Vertex u : reverse_topological_ordering) {
    559         if (LLVM_LIKELY(out_degree(u, G) > 0)) {
     445    for (const Vertex u : reverse_topological_ordering) {       
     446        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     447            continue;
     448        } else if (LLVM_LIKELY(out_degree(u, G) > 0)) {
    560449            if (isAssociative(G[u])) {
    561450                if (LLVM_UNLIKELY(in_degree(u, G) == 1)) {
     
    572461                        }
    573462                    }
    574                     clear_vertex(u, G);
     463                    mapping[u] = v;
     464                    clear_vertex(u, G);                   
    575465                    getType(G[u]) = TypeId::Var;
    576                     mapping[u] = v;
     466                    getValue(G[u]) = nullptr;
    577467                    continue;
    578468                } else if (LLVM_UNLIKELY(out_degree(u, G) == 1)) {
     
    586476                            add_edge(G[ei], source(ej, G), v, G);
    587477                        }
     478                        mapping[u] = v;
    588479                        clear_vertex(u, G);
    589480                        getType(G[u]) = TypeId::Var;
    590                         mapping[u] = v;
     481                        getValue(G[u]) = nullptr;
     482                        continue;
    591483                    }
    592484                }
     
    595487            clear_in_edges(u, G);
    596488            getType(G[u]) = TypeId::Var;
     489            getValue(G[u]) = nullptr;
     490            continue;
    597491        }
    598492    }   
     
    792686void generateDistributionGraph(const Graph & G, DistributionGraph & H) {
    793687    DistributionMap M;
    794     for (const Vertex u : make_iterator_range(vertices(G))) {       
    795         if (isDistributive(G[u])) {
     688    for (const Vertex u : make_iterator_range(vertices(G))) {
     689        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     690            continue;
     691        } else if (isDistributive(G[u])) {
    796692            const TypeId outerTypeId = getType(G[u]);
    797693            const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
     
    855751 * Apply the distribution law to reduce computations whenever possible.
    856752 ** ------------------------------------------------------------------------------------------------------------- */
    857 void BooleanReassociationPass::redistributeAST(const PabloBlock & block, Graph & G) const {
     753void BooleanReassociationPass::redistributeAST(const PabloBlock & block, Graph & G, Map & M) const {
    858754
    859755    std::vector<Vertex> mapping(num_vertices(G) + 16);
     
    888784            const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or;
    889785
    890             // Update G to match the desired changes (TODO: modify this to reuse a discarded vertex instead)
    891             const Vertex x = add_vertex(std::make_pair(outerTypeId, nullptr), G);
    892             const Vertex y = add_vertex(std::make_pair(innerTypeId, nullptr), G);
     786            // Update G to match the desired change
     787            const Vertex x = addSummaryVertex(outerTypeId, G);
     788            const Vertex y = addSummaryVertex(innerTypeId, G);
    893789            mapping.resize(num_vertices(G));
    894790            mapping[x] = x;
     
    912808                add_edge(nullptr, u, y, G);
    913809            }
    914 
    915810            add_edge(nullptr, x, y, G);
    916811
     
    920815            }
    921816
    922             summarizeGraph(block, G, mapping);
    923         }
    924     }
     817            summarizeGraph(block, G, mapping, M);
     818        }
     819    }
     820}
     821
     822/** ------------------------------------------------------------------------------------------------------------- *
     823 * @brief addSummaryVertex
     824 ** ------------------------------------------------------------------------------------------------------------- */
     825inline Vertex BooleanReassociationPass::addSummaryVertex(const TypeId typeId, Graph & G) {
     826    return add_vertex(std::make_pair(typeId, nullptr), G);
    925827}
    926828
Note: See TracChangeset for help on using the changeset viewer.