Ignore:
Timestamp:
May 31, 2017, 4:25:33 PM (2 years ago)
Author:
nmedfort
Message:

Initial attempt to improve debugging capabilities with compilation stack traces on error.

File:
1 edited

Legend:

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

    r5464 r5486  
    99#include <pablo/pe_ones.h>
    1010#include <pablo/boolean.h>
     11#include <pablo/pe_var.h>
    1112#include <boost/container/flat_set.hpp>
    1213#include <boost/container/flat_map.hpp>
     14#include <boost/range/adaptor/reversed.hpp>
    1315#include <boost/graph/adjacency_list.hpp>
    1416#include <boost/graph/topological_sort.hpp>
    1517#include <boost/function_output_iterator.hpp>
     18#include <set>
    1619
    1720#include <boost/graph/strong_components.hpp>
     
    2528using VertexData = std::pair<pablo::PabloAST *, TypeId>;
    2629
    27 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, VertexData, pablo::PabloAST *>;
     30using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, pablo::PabloAST *>;
    2831using Vertex = Graph::vertex_descriptor;
    29 
    30 using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
    31 using DistributionVertex = DistributionGraph::vertex_descriptor;
     32using in_edge_iterator = graph_traits<Graph>::in_edge_iterator;
     33using out_edge_iterator = graph_traits<Graph>::out_edge_iterator;
    3234
    3335using VertexSet = std::vector<Vertex>;
     
    145147struct PassContainer {
    146148
     149    enum Modification {
     150        None, Trivial, Structural
     151    };
     152
    147153    /** ------------------------------------------------------------------------------------------------------------- *
    148154     * @brief run
     
    166172     * Try to eliminate some of the unnecessary operations from the current Variadic expressions
    167173     ** ------------------------------------------------------------------------------------------------------------- */
     174    void run(PabloKernel * const kernel) {
     175        run(kernel->getEntryBlock());
     176
     177        printGraph(G, "G", errs());
     178        if (simplifyGraph() == Structural) {
     179            // rewriteAST(first, stmt);
     180            printGraph(G, "O", errs());
     181        }
     182
     183    }
     184
    168185    void run(PabloBlock * const block) {
    169         Statement * stmt = block->front();
    170         // Statement * first = stmt;
    171         while (stmt) {
    172             Statement * next = stmt->getNextNode();
     186        for (Statement * stmt : *block) {           
    173187            if (isa<Branch>(stmt)) {
    174                 // addUsageInformation();
    175                 if (simplifyGraph()) {
    176                     // rewriteAST(first, stmt);
    177 
    178                     // printGraph(G, "G", errs());
    179                 }
    180 
    181 
    182 
    183                 G.clear();
    184                 M.clear();
     188                addBranch(stmt);
    185189                run(cast<Branch>(stmt)->getBody());
    186                 G.clear();
    187                 M.clear();
    188190            } else {
    189191                addStatement(stmt);
    190192            }
    191             stmt = next;
    192         }
     193        }
     194
     195//        G.clear();
     196//        M.clear();
     197//        for (Statement * stmt : *block) {
     198//            addStatement(stmt);
     199//        }
     200
     201//        printGraph(G, "G", errs());
     202//        if (simplifyGraph() == Structural) {
     203//            // rewriteAST(first, stmt);
     204//            printGraph(G, "O", errs());
     205//        }
     206
     207    }
     208
     209    /** ------------------------------------------------------------------------------------------------------------- *
     210     * @brief simplifyGraph
     211     ** ------------------------------------------------------------------------------------------------------------- */
     212    Modification simplifyGraph() {
     213        Modification modified = None;
     214        for (;;) {
     215            const auto p1 = applyAssociativeIdentityAnnulmentLaws();
     216            const auto p2 = applyAbsorbtionComplementIdempotentLaws();
     217            const auto p3 = applyDistributivityLaw();
     218            if (std::max(std::max(p1, p2), p3) != Structural) {
     219                break;
     220            }
     221            modified = Structural;
     222        }
     223        return modified;
    193224    }
    194225
    195226protected:
    196227
    197 //    /** ------------------------------------------------------------------------------------------------------------- *
    198 //     * @brief addUsageInformation
    199 //     *
    200 //     * Populate G with the user information of each statement so that we can determine whether it'll be cost effective
    201 //     * to distribute an operation.
    202 //     ** ------------------------------------------------------------------------------------------------------------- */
    203 //    void addUsageInformation() {
    204 //        for (const Vertex u : make_iterator_range(vertices(G))) {
    205 //            PabloAST * expr; TypeId typeId;
    206 //            std::tie(expr, typeId) = G[u];
    207 //            if (LLVM_LIKELY(typeId != TypeId::Var)) {
    208 //                for (PabloAST * user : expr->users()) {
    209 //                    add_edge(u, addExpression(user), user, G);
    210 //                }
    211 //            }
    212 //        }
    213 //    }
    214 
    215228    /** ------------------------------------------------------------------------------------------------------------- *
    216229     * @brief applyAssociativeIdentityAnnulmentLaws
    217230     ** ------------------------------------------------------------------------------------------------------------- */
    218     bool applyAssociativeIdentityAnnulmentLaws() {
    219 
    220         bool modified = false;
    221 
    222         std::function<void(const Vertex)> apply = [&](const Vertex u) {
    223             PabloAST * expr; TypeId typeId;
    224             std::tie(expr, typeId) = G[u];
    225 
    226 
    227 
    228             if (LLVM_UNLIKELY(typeId == TypeId::Zeroes || typeId == TypeId::Ones)) {
    229 repeat:         for (auto e : make_iterator_range(out_edges(u, G))) {
    230                     const auto v = target(e, G);
    231                     const auto targetTypeId = getType(v);
    232                     if (LLVM_UNLIKELY(isAssociative(targetTypeId))) {
    233                         if (isIdentityRelation(typeId, targetTypeId)) {
    234                             remove_edge(e, G);
    235                         } else {
    236                             setType(v, typeId == TypeId::And ? TypeId::Zeroes : TypeId::Ones);
    237                             clear_in_edges(v, G);
    238                             apply(v);
    239                         }
    240                         modified = true;
    241                         goto repeat;
     231    Modification applyAssociativeIdentityAnnulmentLaws() {
     232
     233        auto identityComparator = [this](const Vertex u, const Vertex v) -> bool {
     234            const auto typeA = getType(u);
     235            assert (typeA != TypeId::Var);
     236            const auto typeB = getType(v);
     237            assert (typeB != TypeId::Var);
     238            if (LLVM_LIKELY(typeA != typeB)) {
     239                using value_of = std::underlying_type<TypeId>::type;
     240                return static_cast<value_of>(typeA) < static_cast<value_of>(typeB);
     241            } else {
     242                const auto degA = in_degree(u, G);
     243                const auto degB = in_degree(v, G);
     244                if (degA != degB) {
     245                    return degA < degB;
     246                } else {
     247                    Vertex adjA[degA];
     248                    Vertex adjB[degA];
     249                    in_edge_iterator ei, ej;
     250                    std::tie(ei, std::ignore) = in_edges(u, G);
     251                    std::tie(ej, std::ignore) = in_edges(v, G);
     252                    for (size_t i = 0; i < degA; ++i, ++ei, ++ej) {
     253                        adjA[i] = source(*ei, G);
     254                        adjB[i] = source(*ej, G);
     255                    }
     256                    std::sort(adjA, adjA + degA);
     257                    std::sort(adjB, adjB + degA);
     258                    for (size_t i = 0; i < degA; ++i) {
     259                        if (adjA[i] < adjB[i]) {
     260                            return true;
     261                        }
     262                    }
     263                    return false;
     264                }
     265            }
     266        };
     267
     268        flat_set<Vertex, decltype(identityComparator)> V(identityComparator);
     269        V.reserve(num_vertices(G));
     270
     271        VertexSet ordering;
     272        ordering.reserve(num_vertices(G));
     273
     274        topological_sort(G, std::back_inserter(ordering)); // note: ordering is in reverse topological order
     275
     276        Modification modified = None;
     277
     278        for (const auto u : boost::adaptors::reverse(ordering)) {
     279            const TypeId typeId = getType(u);
     280            if (isImmutable(typeId)) {
     281                continue;
     282            } else if (LLVM_UNLIKELY(typeId == TypeId::Zeroes || typeId == TypeId::Ones)) {
     283                for(;;) {
     284                    bool done = true;
     285                    for (auto e : make_iterator_range(out_edges(u, G))) {
     286                        const auto v = target(e, G);
     287                        const auto targetTypeId = getType(v);
     288                        if (LLVM_UNLIKELY(isAssociative(targetTypeId))) {
     289
     290                            errs() << " -- identity relationship\n";
     291
     292                            if (isIdentityRelation(typeId, targetTypeId)) {
     293                                remove_edge(e, G);
     294                            } else {
     295                                setType(v, typeId == TypeId::And ? TypeId::Zeroes : TypeId::Ones);
     296                                clear_in_edges(v, G);
     297                            }
     298                            done = false;
     299                            modified = Structural;
     300                            break;
     301                        }
     302                    }
     303                    if (done) {
     304                        break;
    242305                    }
    243306                }
    244307            } else if (isAssociative(typeId)) {
    245 
    246                 bool contractable = true;
    247                 // an associative operation with only one element is always equivalent to the element
    248                 if (LLVM_LIKELY(in_degree(u, G) != 1)) {
    249                     for (auto e : make_iterator_range(out_edges(u, G))) {
    250                         if (LLVM_LIKELY(typeId != getType(target(e, G)))) {
    251                             contractable = false;
    252                             break;
    253                         }
    254                     }
    255                 }
    256                 if (LLVM_UNLIKELY(contractable)) {
    257                     for (auto ei : make_iterator_range(in_edges(u, G))) {
    258                         for (auto ej : make_iterator_range(out_edges(u, G))) {
    259                             add_edge(source(ei, G), target(ej, G), expr, G);
    260                         }
    261                     }
    262                     clear_vertex(u, G);
    263                     setType(u, TypeId::Var);
    264                     modified = true;
    265                 }
    266             }
    267         };
    268 
    269         // note: calls "apply" on each vertex in reverse topological order
    270         topological_sort(G, boost::make_function_output_iterator(apply));
    271 
     308                if (LLVM_UNLIKELY(in_degree(u, G) == 0)) {
     309                    setType(u, TypeId::Zeroes);
     310                } else {
     311                    // An associative operation with only one element is always equivalent to the element
     312                    bool contractable = true;
     313                    if (LLVM_LIKELY(in_degree(u, G) > 1)) {
     314                        for (auto e : make_iterator_range(out_edges(u, G))) {
     315                            if (LLVM_LIKELY(typeId != getType(target(e, G)))) {
     316                                contractable = false;
     317                                break;
     318                            }
     319                        }
     320                    }
     321                    if (LLVM_UNLIKELY(contractable)) {
     322                        for (auto ei : make_iterator_range(in_edges(u, G))) {
     323                            for (auto ej : make_iterator_range(out_edges(u, G))) {
     324                                addEdge(source(ei, G), target(ej, G), G[ei]);
     325                            }
     326                        }
     327                        removeVertex(u);
     328                        modified = std::max(modified, Trivial);
     329                        continue;
     330                    }
     331
     332                    if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
     333                        // TODO:: (A ⊕ ¬B) = (A ⊕ (B ⊕ 1)) = ¬(A ⊕ B)
     334
     335                    }
     336
     337
     338
     339                }
     340            }
     341
     342            assert (getType(u) != TypeId::Var);
     343
     344            const auto f = V.insert(u);
     345            if (LLVM_UNLIKELY(!f.second)) {
     346                const auto v = *f.first;
     347
     348                errs() << " -- replacing " << u << " with " << v << "\n";
     349
     350                for (auto e : make_iterator_range(out_edges(u, G))) {
     351                    addEdge(v, target(e, G), G[e]);
     352                }
     353                removeVertex(u);
     354                modified = Structural;
     355            }
     356        }
    272357        return modified;
    273358    }
     
    276361     * @brief applyAbsorbtionComplementIdempotentLaws
    277362     ** ------------------------------------------------------------------------------------------------------------- */
    278     bool applyAbsorbtionComplementIdempotentLaws() {
    279         using in_edge_iterator = graph_traits<Graph>::in_edge_iterator;
    280         bool modified = false;
     363    Modification applyAbsorbtionComplementIdempotentLaws() {
     364        Modification modified = None;
    281365        for (const Vertex u : make_iterator_range(vertices(G))) {
    282366            const TypeId typeId = getType(u);
     
    293377                            for (auto ek = ek_begin; ek != ek_end; ++ek) {
    294378                                if (LLVM_UNLIKELY(source(*ej, G) == source(*ek, G))) {
     379                                    modified = Structural;
    295380                                    if (LLVM_UNLIKELY(innerTypeId == TypeId::Not)) {
    296381                                        // complement
     
    305390                                            // absorbtion
    306391                                            remove_edge(*ej, G);
    307                                         }
    308                                         modified = true;
     392                                        }                                       
    309393                                        // this seldom occurs so if it does, just restart the process rather than
    310394                                        // trying to keep the iterators valid.
     
    322406    }
    323407
    324 
    325     /** ------------------------------------------------------------------------------------------------------------- *
    326      * @brief contractGraph
    327      *
    328      * This function scans through a scope block and computes a DAG G in which any sequences of AND, OR or XOR functions
    329      * are "flattened" (i.e., allowed to have any number of inputs.)
    330      ** ------------------------------------------------------------------------------------------------------------- */
    331     bool contractGraph() {
    332         bool modified = false;
    333         bool alreadyGoneOnce = false;
    334         for (;;) {
    335             if (applyAssociativeIdentityAnnulmentLaws()) {
    336                 modified = true;
    337             } else if (alreadyGoneOnce) {
    338                 break;
    339             }
    340             if (applyAbsorbtionComplementIdempotentLaws()) {
    341                 modified = true;
    342             } else { // if (alreadyGoneOnce) {
    343                 break;
    344             }
    345             alreadyGoneOnce = true;
    346         }
    347         return modified;
    348     }
    349 
    350     /** ------------------------------------------------------------------------------------------------------------- *
    351      * @brief addVertex
    352      ** ------------------------------------------------------------------------------------------------------------- */
    353     DistributionVertex addVertex(const Vertex u) {
    354         const auto f = D.find(u);
    355         if (LLVM_LIKELY(f != D.end())) {
    356             return f->second;
    357         }
    358         const auto v = add_vertex(u, H);
    359         D.emplace(u, v);
    360         return v;
    361     }
    362 
    363     /** ------------------------------------------------------------------------------------------------------------- *
    364      * @brief generateDistributionGraph
     408    /** ------------------------------------------------------------------------------------------------------------- *
     409     * @brief identifyDistributableVertices
    365410     *
    366411     * Let (u) ∈ V(G) be a conjunction ∧ or disjunction √ and (v) be a ∧ or √ and the opposite type of (u). If (u,v) ∈
     
    375420     *
    376421     ** ------------------------------------------------------------------------------------------------------------- */
    377     void generateDistributionGraph() {
    378 
    379         assert (D.empty());
    380 
    381         flat_set<Vertex> distributable;
    382         flat_set<Vertex> observed;
     422    void identifyDistributableVertices() {
     423
     424        assert (D.empty() && L.empty());
    383425
    384426        for (const Vertex u : make_iterator_range(vertices(G))) {
    385427            const TypeId outerTypeId = getType(u);
    386428            if (isDistributive(outerTypeId)) {
     429                bool beneficial = true;
    387430                const TypeId innerTypeId = oppositeTypeId(outerTypeId);
    388                 for (auto e : make_iterator_range(in_edges(u, G))) {
    389                     const Vertex v = source(e, G);
    390                     if (LLVM_UNLIKELY(std::get<1>(G[v]) == innerTypeId)) {
    391                         bool beneficial = true;
    392                         for (const auto e : make_iterator_range(out_edges(v, G))) {
    393                             if (std::get<1>(G[target(e, G)]) != outerTypeId) {
    394                                 beneficial = false;
    395                                 break;
    396                             }
    397                         }
    398                         if (beneficial) {
    399                             distributable.insert(v);
    400                         }
    401                     }
    402                 }
    403                 if (LLVM_LIKELY(distributable.size() > 1)) {
    404                     for (const Vertex v : distributable) {
    405                         for (auto e : make_iterator_range(in_edges(v, G))) {
    406                             observed.insert(source(e, G));
    407                         }
    408                     }
    409                     for (const Vertex w : observed) {
    410                         for (auto e : make_iterator_range(out_edges(w, G))) {
    411                             const Vertex v = target(e, G);
    412                             if (distributable.count(v)) {
    413                                 const Vertex y = addVertex(v);
    414                                 boost::add_edge(y, addVertex(u), H);
    415                                 boost::add_edge(addVertex(w), y, H);
    416                             }
    417                         }
    418                     }
    419                     observed.clear();
    420                 }
    421                 distributable.clear();
     431                for (auto e : make_iterator_range(out_edges(u, G))) {
     432                    const Vertex v = target(e, G);
     433                    if (LLVM_UNLIKELY(getType(v) != innerTypeId)) {
     434                        beneficial = false;
     435                        break;
     436                    }
     437                }
     438                if (beneficial) {
     439                    for (auto e : make_iterator_range(out_edges(u, G))) {
     440                        const auto v = target(e, G);
     441                        const auto f = std::lower_bound(D.begin(), D.end(), v);
     442                        if (f == D.end() || *f != v) {
     443                            D.insert(f, v);
     444                            assert (std::is_sorted(D.begin(), D.end()));
     445                        }
     446                    }
     447                    for (auto e : make_iterator_range(in_edges(u, G))) {
     448                        const auto v = source(e, G);
     449                        const auto f = std::lower_bound(L.begin(), L.end(), v);
     450                        if (f == L.end() || *f != v) {
     451                            L.insert(f, v);
     452                            assert (std::is_sorted(L.begin(), L.end()));
     453                        }
     454                    }
     455                }
     456            }
     457        }
     458
     459        // D = D - L
     460
     461        if (!L.empty()) {
     462            if (!D.empty()) {
     463                auto di = D.begin(), li = L.begin(), li_end = L.end();
     464                for (;;) {
     465                    if (*li < *di) {
     466                        if (++li == li_end) {
     467                            break;
     468                        }
     469                    } else {
     470                        if (*di < *li) {
     471                            ++di;
     472                        } else {
     473                            di = D.erase(di);
     474                        }
     475                        if (di == D.end()) {
     476                            break;
     477                        }
     478                    }
     479                }
     480            }
     481            L.clear();
     482        }
     483    }
     484
     485    /** ------------------------------------------------------------------------------------------------------------- *
     486     * @brief applyDistributivityLaw
     487     ** ------------------------------------------------------------------------------------------------------------- */
     488    Modification applyDistributivityLaw() {
     489
     490        identifyDistributableVertices();
     491
     492        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
     493        if (D.empty()) {
     494            return None;
     495        }
     496
     497        Modification modified = None;
     498
     499        const auto lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(D)), 1);
     500
     501        for (auto & lower : lowerSet) {
     502            const auto upperSet = independentCliqueSets<0>(enumerateBicliques(std::get<1>(lower)), 2);
     503            for (const auto & upper : upperSet) {
     504
     505                const auto & sources = std::get<1>(upper);
     506                const auto & intermediary = std::get<0>(upper);
     507                const auto & sinks = std::get<0>(lower);
     508
     509
     510
     511                const auto outerTypeId = getType(sinks.front());
     512                const auto innerTypeId = oppositeTypeId(outerTypeId);
     513
     514                errs() << " -- distributing\n";
     515
     516                // Update G to match the desired change
     517                const auto x = makeVertex(outerTypeId);
     518                const auto y = makeVertex(innerTypeId);
     519
     520                for (const auto i : intermediary) {
     521                    assert (getType(i) == innerTypeId);
     522                    for (const Vertex t : sinks) {
     523                        assert (getType(t) == outerTypeId);
     524                        remove_edge(i, t, G);
     525                    }
     526                    addEdge(i, x);
     527                }
     528
     529                for (const Vertex s : sources) {
     530                    for (const Vertex i : intermediary) {
     531                        remove_edge(s, i, G);
     532                    }
     533                    addEdge(s, y);
     534                }
     535                addEdge(x, y);
     536
     537                for (const Vertex t : sinks) {
     538                    addEdge(y, t, std::get<0>(G[t]));
     539                }
     540
     541                modified = Structural;
    422542            }
    423543        }
    424544
    425545        D.clear();
    426     }
    427 
    428 
    429     /** ------------------------------------------------------------------------------------------------------------- *
    430      * @brief redistributeAST
    431      *
    432      * Apply the distribution law to reduce computations whenever possible.
    433      ** ------------------------------------------------------------------------------------------------------------- */
    434     bool simplifyGraph() {
    435 
    436         VertexSet sinks;
    437 
    438         bool modified = false;
    439 
    440         for (;;) {
    441 
    442             assert (num_vertices(H) == 0 && num_edges(H) == 0);
    443 
    444             if (contractGraph()) {
    445                 modified = true;
    446             }
    447 
    448             generateDistributionGraph();
    449 
    450             // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
    451             if (num_vertices(H) == 0) {
    452                 break;
    453             }
    454 
    455             for (const Vertex u : make_iterator_range(vertices(H))) {
    456                 if (out_degree(u, H) == 0 && in_degree(u, H) != 0) {
    457                     sinks.push_back(u);
    458                 }
    459             }
    460             std::sort(sinks.begin(), sinks.end());
    461 
    462             bool done = true;
    463 
    464             const auto lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(sinks)), 1);
    465 
    466             for (auto & lower : lowerSet) {
    467                 const auto upperSet = independentCliqueSets<0>(enumerateBicliques(std::get<1>(lower)), 2);
    468                 for (const auto & upper : upperSet) {
    469 
    470                     const auto & sources = std::get<1>(upper);
    471                     const auto & intermediary = std::get<0>(upper);
    472                     const auto & sinks = std::get<0>(lower);
    473 
    474                     const auto outerTypeId = getType(H[sinks.front()]);
    475                     const auto innerTypeId = oppositeTypeId(outerTypeId);
    476 
    477                     // Update G to match the desired change
    478                     const auto x = makeVertex(outerTypeId);
    479                     const auto y = makeVertex(innerTypeId);
    480 
    481                     for (const auto i : intermediary) {
    482                         const auto u = H[i];
    483                         assert (getType(u) == innerTypeId);
    484                         for (const Vertex t : sinks) {
    485                             assert (getType(H[t]) == outerTypeId);
    486                             remove_edge(u, H[t], G);
    487                         }
    488                         add_edge(u, x, nullptr, G);
    489                     }
    490 
    491                     for (const Vertex s : sources) {
    492                         const auto u = H[s];
    493                         for (const Vertex i : intermediary) {
    494                             remove_edge(u, H[i], G);
    495                         }
    496                         add_edge(u, y, nullptr, G);
    497                     }
    498                     add_edge(x, y, nullptr, G);
    499 
    500                     for (const Vertex t : sinks) {
    501                         const auto v = H[t];
    502                         add_edge(y, v, std::get<0>(G[v]), G);
    503                     }
    504 
    505                     done = false;
    506                 }
    507             }
    508 
    509             H.clear();
    510 
    511             if (done) {
    512                 break;
    513             } else {
    514                 sinks.clear();
    515                 modified = true;
    516             }
    517         }
    518 
    519         assert (num_vertices(H) == 0 && num_edges(H) == 0);
    520546
    521547        return modified;
     
    536562        IntersectionSets B1;
    537563        for (auto u : A) {
    538             if (in_degree(u, H) > 0) {
     564            if (in_degree(u, G) > 0) {
    539565                VertexSet incomingAdjacencies;
    540                 incomingAdjacencies.reserve(in_degree(u, H));
    541                 for (auto e : make_iterator_range(in_edges(u, H))) {
    542                     incomingAdjacencies.push_back(source(e, H));
     566                incomingAdjacencies.reserve(in_degree(u, G));
     567                for (auto e : make_iterator_range(in_edges(u, G))) {
     568                    incomingAdjacencies.push_back(source(e, G));
    543569                }
    544570                std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
     
    590616            for (const Vertex u : *Bi) {
    591617                VertexSet Aj;
    592                 Aj.reserve(out_degree(u, H));
    593                 for (auto e : make_iterator_range(out_edges(u, H))) {
    594                     Aj.push_back(target(e, H));
     618                Aj.reserve(out_degree(u, G));
     619                for (auto e : make_iterator_range(out_edges(u, G))) {
     620                    Aj.push_back(target(e, G));
    595621                }
    596622                std::sort(Aj.begin(), Aj.end());
     
    673699            VertexSet & B = std::get<1>(*ci);
    674700            for (auto bi = B.begin(); bi != B.end(); ) {
    675                 if (out_degree(H[*bi], G) == cardinalityA) {
     701                if (out_degree(*bi, G) == cardinalityA) {
    676702                    ++bi;
    677703                } else {
     
    689715
    690716    /** ------------------------------------------------------------------------------------------------------------- *
    691      * @brief addTemporary
     717     * @brief makeVertex
    692718     ** ------------------------------------------------------------------------------------------------------------- */
    693719    Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) {
     
    711737        const auto u = makeVertex(typeId, expr);
    712738        M.emplace(expr, u);
     739        if (LLVM_UNLIKELY(isa<Not>(expr))) {
     740            PabloAST * const negated = cast<Not>(expr)->getExpr();
     741            addEdge(addExpression(negated), u, negated);
     742        }
    713743        return u;
    714744    }
     
    717747     * @brief addStatement
    718748     ** ------------------------------------------------------------------------------------------------------------- */
    719     void addStatement(Statement * const stmt) {
     749    Vertex addStatement(Statement * const stmt) {
    720750        assert (M.count(stmt) == 0);
    721751        const auto typeId = stmt->getClassTypeId();
    722         const auto u = makeVertex(typeId, stmt);
    723         M.emplace(stmt, u);
    724         for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    725             PabloAST * const op = stmt->getOperand(i);
    726             if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
    727                 continue;
    728             }
    729             const auto v = addExpression(op);
    730             add_edge(v, u, op, G);
    731             if (LLVM_UNLIKELY(isa<Not>(op))) {
    732                 PabloAST * const negated = cast<Not>(op)->getExpr();
    733                 add_edge(addExpression(negated), v, negated, G);
    734             }
    735         }
     752        if (LLVM_UNLIKELY(typeId == TypeId::Sel)) {
     753
     754            // expand Sel (C,T,F) statements into (C ∧ T) √ (C ∧ F)
     755
     756            const auto c = addExpression(cast<Sel>(stmt)->getCondition());
     757            const auto t = addExpression(cast<Sel>(stmt)->getTrueExpr());
     758            const auto l = makeVertex(TypeId::And);
     759            addEdge(c, l);
     760            addEdge(t, l);
     761            const auto n = makeVertex(TypeId::Not);
     762            addEdge(c, n);
     763            const auto r = makeVertex(TypeId::And);
     764            const auto f = addExpression(cast<Sel>(stmt)->getFalseExpr());
     765            addEdge(n, r);
     766            addEdge(f, r);
     767            const auto u = makeVertex(TypeId::Or, stmt);
     768            M.emplace(stmt, u);
     769            addEdge(l, u);
     770            addEdge(r, u);
     771
     772            return u;
     773
     774        } else {
     775
     776            const auto u = makeVertex(typeId, stmt);
     777            M.emplace(stmt, u);
     778            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     779                PabloAST * const op = stmt->getOperand(i);
     780                if (LLVM_UNLIKELY(isa<String>(op))) {
     781                    continue;
     782                }
     783                addEdge(addExpression(op), u, op);
     784            }
     785
     786            return u;
     787        }
     788
     789    }
     790
     791    /** ------------------------------------------------------------------------------------------------------------- *
     792     * @brief addBranch
     793     ** ------------------------------------------------------------------------------------------------------------- */
     794    void addBranch(Statement * const br) {
     795        const auto u = addStatement(br);
     796        for (auto escaped : cast<Branch>(br)->getEscaped()) {
     797            addEdge(u, addExpression(escaped), escaped);
     798        }
     799    }
     800
     801
     802    /** ------------------------------------------------------------------------------------------------------------- *
     803     * @brief addEdge
     804     ** ------------------------------------------------------------------------------------------------------------- */
     805    void addEdge(const Vertex u, const Vertex v, PabloAST * const value = nullptr) {
     806        const auto typeId = getType(v);
     807        if (isAssociative(typeId)) {
     808            for (auto e : make_iterator_range(in_edges(u, G))) {
     809                if (LLVM_UNLIKELY(source(e, G) == u)) {
     810                    if (LLVM_LIKELY(isDistributive(typeId))) {
     811                        G[e] = std::max(G[e], value);
     812                    } else {
     813                        remove_edge(e, G);
     814                    }
     815                    return;
     816                }
     817            }
     818        }
     819        boost::add_edge(u, v, value, G);
     820    }
     821
     822    /** ------------------------------------------------------------------------------------------------------------- *
     823     * @brief removeVertex
     824     ** ------------------------------------------------------------------------------------------------------------- */
     825    void removeVertex(const Vertex u) {
     826        clear_vertex(u, G);
     827        setType(u, TypeId::Var);
    736828    }
    737829
     
    775867    }
    776868
     869    static bool isImmutable(const TypeId typeId) {
     870        return (typeId == TypeId::Var || typeId == TypeId::Assign || typeId == TypeId::Extract);
     871    }
     872
    777873    static TypeId oppositeTypeId(const TypeId typeId) {
    778874        assert (isDistributive(typeId));
     
    780876    }
    781877
    782     void add_edge(const Vertex u, const Vertex v, PabloAST * const value, Graph & G) {
    783         G[std::get<0>(boost::add_edge(u, v, G))] = value;
    784     }
    785 
    786878private:
    787879
    788880    Graph G;
    789881    flat_map<pablo::PabloAST *, Vertex> M;
    790 
    791     DistributionGraph H;
    792     flat_map<Vertex, DistributionVertex> D;
     882    VertexSet D;
     883    VertexSet L;
    793884
    794885};
     
    798889 ** ------------------------------------------------------------------------------------------------------------- */
    799890bool DistributivePass::optimize(PabloKernel * const kernel) {
     891    #ifdef NDEBUG
     892    report_fatal_error("DistributivePass is unsupported");
     893    #endif
    800894    PassContainer C;
    801     C.run(kernel->getEntryBlock());
     895    C.run(kernel);
    802896    return true;
    803897}
Note: See TracChangeset for help on using the changeset viewer.