source: icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp @ 4765

Last change on this file since 4765 was 4765, checked in by nmedfort, 4 years ago

Work on distribution law.

File size: 28.1 KB
Line 
1#include "booleanreassociationpass.h"
2#include <boost/container/flat_set.hpp>
3#include <boost/container/flat_map.hpp>
4#include <boost/circular_buffer.hpp>
5#include <boost/graph/adjacency_list.hpp>
6#include <boost/graph/filtered_graph.hpp>
7#include <boost/graph/topological_sort.hpp>
8#include <pablo/optimizers/pablo_simplifier.hpp>
9#include <algorithm>
10#include <queue>
11#include <set>
12#include <iostream>
13#include <pablo/printer_pablos.h>
14#include "graph-facade.hpp"
15
16using namespace boost;
17using namespace boost::container;
18
19namespace pablo {
20
21using Graph = BooleanReassociationPass::Graph;
22using Vertex = Graph::vertex_descriptor;
23using VertexQueue = circular_buffer<Vertex>;
24using Map = BooleanReassociationPass::Map;
25using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
26using TypeId = PabloAST::ClassTypeId;
27using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
28using DistributionMap = flat_map<Graph::vertex_descriptor, DistributionGraph::vertex_descriptor>;
29using VertexSet = std::vector<Vertex>;
30using VertexSets = std::vector<VertexSet>;
31using Biclique = std::pair<VertexSet, VertexSet>;
32using BicliqueSet = std::vector<Biclique>;
33using DistributionSet = std::tuple<std::vector<Vertex>, std::vector<Vertex>, std::vector<Vertex>>;
34using DistributionSets = std::vector<DistributionSet>;
35
36template <class Graph>
37static VertexSet incomingVertexSet(const Vertex u, const Graph & G) {
38    VertexSet V;
39    V.reserve(G.in_degree(u));
40    for (auto e : make_iterator_range(G.in_edges(u))) {
41        V.push_back(G.source(e));
42    }
43    std::sort(V.begin(), V.end());
44    return std::move(V);
45}
46
47template <class Graph>
48static VertexSet outgoingVertexSet(const Vertex u, const Graph & G) {
49    VertexSet V;
50    V.reserve(G.out_degree(u));
51    for (auto e : make_iterator_range(G.out_edges(u))) {
52        V.push_back(G.target(e));
53    }
54    std::sort(V.begin(), V.end());
55    return std::move(V);
56}
57
58/** ------------------------------------------------------------------------------------------------------------- *
59 * @brief optimize
60 ** ------------------------------------------------------------------------------------------------------------- */
61bool BooleanReassociationPass::optimize(PabloFunction & function) {
62    BooleanReassociationPass brp;
63    brp.resolveScopes(function);
64    brp.processScopes(function);
65    Simplifier::optimize(function);
66    return true;
67}
68
69/** ------------------------------------------------------------------------------------------------------------- *
70 * @brief resolveScopes
71 ** ------------------------------------------------------------------------------------------------------------- */
72inline void BooleanReassociationPass::resolveScopes(PabloFunction &function) {
73    mResolvedScopes.emplace(&function.getEntryBlock(), nullptr);
74    resolveScopes(function.getEntryBlock());
75}
76
77/** ------------------------------------------------------------------------------------------------------------- *
78 * @brief resolveScopes
79 ** ------------------------------------------------------------------------------------------------------------- */
80void BooleanReassociationPass::resolveScopes(PabloBlock & block) {
81    for (Statement * stmt : block) {
82        if (isa<If>(stmt) || isa<While>(stmt)) {
83            PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
84            mResolvedScopes.emplace(&nested, stmt);
85            resolveScopes(nested);
86        }
87    }
88}
89
90/** ------------------------------------------------------------------------------------------------------------- *
91 * @brief processScopes
92 ** ------------------------------------------------------------------------------------------------------------- */
93inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
94    processScopes(function.getEntryBlock());
95}
96
97/** ------------------------------------------------------------------------------------------------------------- *
98 * @brief processScopes
99 ** ------------------------------------------------------------------------------------------------------------- */
100void BooleanReassociationPass::processScopes(PabloBlock & block) {
101    for (Statement * stmt : block) {
102        if (isa<If>(stmt)) {
103            processScopes(cast<If>(stmt)->getBody());
104        } else if (isa<While>(stmt)) {
105            processScopes(cast<While>(stmt)->getBody());
106        }
107    }
108    processScope(block);
109}
110
111/** ------------------------------------------------------------------------------------------------------------- *
112 * @brief isOptimizable
113 *
114 * And, Or and Xor instructions are all associative, commutative and distributive operations. Thus we can
115 * safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
116 ** ------------------------------------------------------------------------------------------------------------- */
117static inline bool isOptimizable(const PabloAST * const expr) {
118    assert (expr);
119    switch (expr->getClassTypeId()) {
120        case PabloAST::ClassTypeId::And:
121        case PabloAST::ClassTypeId::Or:
122        case PabloAST::ClassTypeId::Xor:
123            return true;
124        default:
125            return false;
126    }
127}
128
129/** ------------------------------------------------------------------------------------------------------------- *
130 * @brief inCurrentBlock
131 ** ------------------------------------------------------------------------------------------------------------- */
132static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
133    return stmt->getParent() == &block;
134}
135
136static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
137    return isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block);
138}
139
140/** ------------------------------------------------------------------------------------------------------------- *
141 * @brief getVertex
142 ** ------------------------------------------------------------------------------------------------------------- */
143template<typename ValueType, typename GraphType, typename MapType>
144static inline Vertex getVertex(const ValueType value, GraphType & G, MapType & M) {
145    const auto f = M.find(value);
146    if (f != M.end()) {
147        return f->second;
148    }
149    const auto u = add_vertex(value, G);
150    M.insert(std::make_pair(value, u));
151    return u;
152}
153
154/** ------------------------------------------------------------------------------------------------------------- *
155 * @brief createTree
156 ** ------------------------------------------------------------------------------------------------------------- */
157static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) {
158    assert (!Q.empty());
159    while (Q.size() > 1) {
160        PabloAST * e1 = Q.front(); Q.pop_front();
161        // assert (isa<Statement>(e1) ? cast<Statement>(e1)->getParent() != nullptr : true);
162        PabloAST * e2 = Q.front(); Q.pop_front();
163        // assert (isa<Statement>(e2) ? cast<Statement>(e2)->getParent() != nullptr : true);
164        PabloAST * expr = nullptr;
165        // Note: this switch ought to compile to an array of function pointers to the appropriate method.
166        switch (typeId) {
167            case PabloAST::ClassTypeId::And:
168                expr = block.createAnd(e1, e2); break;
169            case PabloAST::ClassTypeId::Or:
170                expr = block.createOr(e1, e2); break;
171            case PabloAST::ClassTypeId::Xor:
172                expr = block.createXor(e1, e2); break;
173            default: break;
174        }
175        Q.push_back(expr);
176    }
177    PabloAST * r = Q.front();
178    Q.clear();
179    return r;
180}
181
182/** ------------------------------------------------------------------------------------------------------------- *
183 * @brief printGraph
184 ** ------------------------------------------------------------------------------------------------------------- */
185static void printGraph(PabloBlock & block, const Graph & G, const std::string name) {
186    raw_os_ostream out(std::cerr);
187    out << "digraph " << name << " {\n";
188    for (auto u : make_iterator_range(vertices(G))) {
189        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
190            continue;
191        }
192        out << "v" << u << " [label=\"";
193        PabloAST * expr = G[u];
194        if (isa<Statement>(expr)) {
195            if (LLVM_UNLIKELY(isa<If>(expr))) {
196                out << "If ";
197                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
198                out << ":";
199            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
200                out << "While ";
201                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
202                out << ":";
203            } else {
204                PabloPrinter::print(cast<Statement>(expr), "", out);
205            }
206        } else {
207            PabloPrinter::print(expr, out);
208        }
209        out << "\"";
210        if (!inCurrentBlock(expr, block)) {
211            out << " style=dashed";
212        }
213        out << "];\n";
214    }
215    for (auto e : make_iterator_range(edges(G))) {
216        out << "v" << source(e, G) << " -> v" << target(e, G) << ";\n";
217    }
218
219    if (num_vertices(G) > 0) {
220
221        out << "{ rank=same;";
222        for (auto u : make_iterator_range(vertices(G))) {
223            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
224                out << " v" << u;
225            }
226        }
227        out << "}\n";
228
229        out << "{ rank=same;";
230        for (auto u : make_iterator_range(vertices(G))) {
231            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
232                out << " v" << u;
233            }
234        }
235        out << "}\n";
236
237    }
238
239    out << "}\n\n";
240    out.flush();
241}
242
243/** ------------------------------------------------------------------------------------------------------------- *
244 * @brief printGraph
245 ** ------------------------------------------------------------------------------------------------------------- */
246template<typename SubgraphType>
247static void printGraph(PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) {
248    raw_os_ostream out(std::cerr);
249    out << "digraph " << name << " {\n";
250    for (auto u : make_iterator_range(vertices(S))) {
251        if (in_degree(u, S) == 0 && out_degree(u, S) == 0) {
252            continue;
253        }
254        out << "v" << u << " [label=\"";
255        PabloAST * expr = G[S[u]];
256        if (isa<Statement>(expr)) {
257            if (LLVM_UNLIKELY(isa<If>(expr))) {
258                out << "If ";
259                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
260                out << ":";
261            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
262                out << "While ";
263                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
264                out << ":";
265            } else {
266                PabloPrinter::print(cast<Statement>(expr), "", out);
267            }
268        } else {
269            PabloPrinter::print(expr, out);
270        }
271        out << "\"";
272        if (!inCurrentBlock(expr, block)) {
273            out << " style=dashed";
274        }
275        out << "];\n";
276    }
277    for (auto e : make_iterator_range(edges(S))) {
278        out << "v" << source(e, S) << " -> v" << target(e, S) << ";\n";
279    }
280
281    if (num_vertices(S) > 0) {
282
283        out << "{ rank=same;";
284        for (auto u : make_iterator_range(vertices(S))) {
285            if (in_degree(u, S) == 0 && out_degree(u, S) != 0) {
286                out << " v" << u;
287            }
288        }
289        out << "}\n";
290
291        out << "{ rank=same;";
292        for (auto u : make_iterator_range(vertices(S))) {
293            if (out_degree(u, S) == 0 && in_degree(u, S) != 0) {
294                out << " v" << u;
295            }
296        }
297        out << "}\n";
298
299    }
300
301    out << "}\n\n";
302    out.flush();
303}
304
305/** ------------------------------------------------------------------------------------------------------------- *
306 * @brief processScope
307 ** ------------------------------------------------------------------------------------------------------------- */
308inline void BooleanReassociationPass::processScope(PabloBlock & block) {
309    Graph G;
310
311    summarizeAST(block, G);
312    redistributeAST(block, G);
313
314    circular_buffer<Vertex> Q(num_vertices(G));
315    topological_sort(G, std::front_inserter(Q));
316    assert (Q.size() == num_vertices(G));
317
318    circular_buffer<PabloAST *> nodes;
319    block.setInsertPoint(nullptr);
320
321    while (!Q.empty()) {
322        const Vertex u = Q.front();
323        Q.pop_front();
324        PabloAST * expr = G[u];
325        if (LLVM_LIKELY(inCurrentBlock(expr, block))) {
326            if (isOptimizable(expr)) {
327                if (in_degree(u, G) == 0) {
328                    cast<Statement>(expr)->eraseFromParent(false);
329                    continue;
330                } else {
331                    if (LLVM_UNLIKELY(nodes.capacity() < in_degree(u, G))) {
332                        nodes.set_capacity(in_degree(u, G));
333                    }
334                    for (auto e : make_iterator_range(in_edges(u, G))) {
335                        nodes.push_back(G[source(e, G)]);
336                    }
337                    G[u] = createTree(block, expr->getClassTypeId(), nodes);
338                    cast<Statement>(expr)->replaceWith(G[u], true, true);
339                    if (LLVM_UNLIKELY(isa<Var>(G[u]))) {
340                        continue;
341                    }
342                    expr = G[u];
343                }
344            }
345            block.insert(cast<Statement>(expr));
346        }
347    }
348
349}
350
351/** ------------------------------------------------------------------------------------------------------------- *
352 * @brief summarizeAST
353 *
354 * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences
355 * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to
356 * reassociate them in the most efficient way possible.
357 ** ------------------------------------------------------------------------------------------------------------- */
358void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const {
359
360    Map M;
361
362    // Compute the base def-use graph ...
363    for (Statement * stmt : block) {
364        const Vertex u = getVertex(stmt, G, M);
365        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
366            PabloAST * const op = stmt->getOperand(i);
367            if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
368                continue;
369            }
370            add_edge(getVertex(op, G, M), u, G);
371        }
372        if (isa<If>(stmt)) {
373            for (Assign * def : cast<const If>(stmt)->getDefined()) {
374                const Vertex v = getVertex(def, G, M);
375                add_edge(u, v, G);
376                resolveUsages(v, def, block, G, M);
377            }
378        } else if (isa<While>(stmt)) {
379            for (Next * var : cast<const While>(stmt)->getVariants()) {
380                const Vertex v = getVertex(var, G, M);
381                add_edge(u, v, G);
382                resolveUsages(v, var, block, G, M);
383            }
384        } else {
385            resolveUsages(u, stmt, block, G, M);
386        }
387    }
388
389    std::vector<Vertex> ordering;
390    ordering.reserve(num_vertices(G));
391    topological_sort(G, std::back_inserter(ordering));
392
393    for (auto i = ordering.rbegin(); i != ordering.rend(); ++i) {
394        const Vertex u = *i;
395        if (isOptimizable(G[u])) {
396            std::vector<Vertex> removable;
397            for (auto e : make_iterator_range(in_edges(u, G))) {
398                const Vertex v = source(e, G);
399                if (out_degree(v, G) == 1 && in_degree(v, G) != 0 && G[u]->getClassTypeId() == G[v]->getClassTypeId()) {
400                    removable.push_back(v);
401                    for (auto e : make_iterator_range(in_edges(v, G))) {
402                        add_edge(source(e, G), u, G);
403                    }
404                }
405            }
406            for (auto v : removable) {
407                clear_vertex(v, G);
408            }
409        }
410    }
411}
412
413/** ------------------------------------------------------------------------------------------------------------- *
414 * @brief resolveUsages
415 ** ------------------------------------------------------------------------------------------------------------- */
416void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const {
417    for (PabloAST * user : expr->users()) {
418        assert (user);
419        if (LLVM_LIKELY(user != expr && isa<Statement>(user))) {
420            PabloBlock * parent = cast<Statement>(user)->getParent();
421            assert (parent);
422            if (LLVM_UNLIKELY(parent != &block)) {
423                for (;;) {
424                    if (LLVM_UNLIKELY(parent == nullptr)) {
425                        assert (isa<Assign>(expr) || isa<Next>(expr));
426                        break;
427                    } else if (parent->getParent() == &block) {
428                        const auto f = mResolvedScopes.find(parent);
429                        if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
430                            throw std::runtime_error("Failed to resolve scope block!");
431                        }
432                        add_edge(u, getVertex(f->second, G, M), G);
433                        break;
434                    }
435                    parent = parent->getParent();
436                }
437            }
438        }
439    }
440}
441
442/** ------------------------------------------------------------------------------------------------------------- *
443 * @brief enumerateBicliques
444 *
445 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
446 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an in-degree of 0
447 * to be in bipartition A and their adjacencies to be in B.
448  ** ------------------------------------------------------------------------------------------------------------- */
449template <class Graph>
450static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
451    using IntersectionSets = std::set<VertexSet>;
452
453    IntersectionSets B1;
454    for (auto u : A) {
455        B1.insert(std::move(incomingVertexSet(u, G)));
456    }
457
458    IntersectionSets B(B1.begin(), B1.end());
459
460    IntersectionSets Bi;
461
462    VertexSet clique;
463    for (auto i = B1.begin(); i != B1.end(); ++i) {
464        for (auto j = i; ++j != B1.end(); ) {
465            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
466            if (clique.size() > 0) {
467                if (B.count(clique) == 0) {
468                    Bi.insert(clique);
469                }
470                clique.clear();
471            }
472        }
473    }
474
475    for (;;) {
476        if (Bi.empty()) {
477            break;
478        }
479        B.insert(Bi.begin(), Bi.end());
480        IntersectionSets Bk;
481        for (auto i = B1.begin(); i != B1.end(); ++i) {
482            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
483                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
484                if (clique.size() > 0) {
485                    if (B.count(clique) == 0) {
486                        Bk.insert(clique);
487                    }
488                    clique.clear();
489                }
490            }
491        }
492        Bi.swap(Bk);
493    }
494
495    BicliqueSet cliques;
496    cliques.reserve(B.size());
497    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
498        // Compute our A set
499        auto bi = Bi->begin();
500        VertexSet Ai = outgoingVertexSet(*bi, G);
501        while (++bi != Bi->end()) {
502            VertexSet Aj = outgoingVertexSet(*bi, G);
503            VertexSet Ak;
504            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
505            Ai.swap(Ak);
506        }
507        cliques.emplace_back(std::move(Ai), std::move(*Bi));
508    }
509
510    return std::move(cliques);
511}
512
513/** ------------------------------------------------------------------------------------------------------------- *
514 * @brief safeDistributionSets
515 ** ------------------------------------------------------------------------------------------------------------- */
516static DistributionSets safeDistributionSets(DistributionGraph & H, const Graph & G) {
517
518    VertexSet terminals;
519    for (const Vertex u : make_iterator_range(vertices(H))) {
520        if (out_degree(u, H) == 0) {
521            terminals.push_back(u);
522        }
523    }
524
525    BicliqueSet lowerSet = enumerateBicliques(makeGraphFacade(H), terminals);
526    // An intermediary vertex could have more than one outgoing edge but if any edge
527    // is not directed to a vertex in our biclique, we'll need to compute that specific
528    // value anyway. Remove them from the clique set and if there are not enough vertices
529    // in the biclique to make distribution profitable, eliminate the clique.
530    for (auto ci = lowerSet.begin(); ci != lowerSet.end(); ) {
531        VertexSet & A = std::get<0>(*ci);
532        VertexSet & B = std::get<1>(*ci);
533        const auto cardinalityA = A.size();
534        for (auto bi = B.begin(); bi != B.end(); ) {
535            if (out_degree(H[*bi], G) == cardinalityA) {
536                ++bi;
537            } else {
538                bi = B.erase(bi);
539            }
540        }
541
542        if (B.size() > 1) {
543            ++ci;
544        } else {
545            ci = lowerSet.erase(ci);
546        }
547    }
548
549    // Each distribution tuple consists of the sources, intermediary, and sink nodes.
550    DistributionSets T;
551    for (const Biclique & lower : lowerSet) {
552        BicliqueSet upperSet = enumerateBicliques(makeGraphFacade(H), std::get<1>(lower));
553        for (Biclique upper : upperSet) {
554            T.emplace_back(std::get<1>(upper), std::get<0>(upper), std::get<0>(lower));
555        }
556    }
557
558    return std::move(T);
559}
560
561/** ------------------------------------------------------------------------------------------------------------- *
562 * @brief generateDistributionGraph
563 ** ------------------------------------------------------------------------------------------------------------- */
564void generateDistributionGraph(PabloBlock & block, Graph & G, DistributionGraph & H) {
565    DistributionMap M;
566    for (const Vertex u : make_iterator_range(vertices(G))) {
567        const TypeId outerTypeId = G[u]->getClassTypeId();
568        if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
569            if (inCurrentBlock(cast<Statement>(G[u]), block)) {
570                const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
571                flat_set<Vertex> distributable;
572                for (auto e : make_iterator_range(in_edges(u, G))) {
573                    const Vertex v = source(e, G);
574                    if (LLVM_UNLIKELY(G[v]->getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block))) {
575                        bool safe = true;
576                        for (const auto e : make_iterator_range(out_edges(v, G))) {
577                            if (G[target(e, G)]->getClassTypeId() != outerTypeId) {
578                                safe = false;
579                                break;
580                            }
581                        }
582                        if (safe) {
583                            distributable.insert(v);
584                        }
585                    }
586                }
587                if (LLVM_LIKELY(distributable.size() > 1)) {
588                    // We're only interested in computing a subgraph of G in which every source has an out-degree
589                    // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
590                    // benefit. (Note: this does not consider register pressure / liveness.)
591                    flat_map<Vertex, bool> observedMoreThanOnce;
592                    bool anyOpportunities = false;
593                    for (const Vertex v : distributable) {
594                        for (auto e : make_iterator_range(in_edges(v, G))) {
595                            const Vertex w = source(e, G);
596                            auto ob = observedMoreThanOnce.find(w);
597                            if (ob == observedMoreThanOnce.end()) {
598                                observedMoreThanOnce.emplace(w, false);
599                            } else {
600                                ob->second = true;
601                                anyOpportunities = true;
602                            }
603                        }
604                    }
605                    if (anyOpportunities) {
606                        for (const auto ob : observedMoreThanOnce) {
607                            if (ob.second) {
608                                const Vertex w = ob.first;
609                                for (auto e : make_iterator_range(out_edges(w, G))) {
610                                    const Vertex v = target(e, G);
611                                    if (distributable.count(v)) {
612                                        const Vertex y = getVertex(v, H, M);
613                                        add_edge(y, getVertex(u, H, M), H);
614                                        add_edge(getVertex(w, H, M), y, H);
615                                    }
616                                }
617                            }
618                        }
619                    }
620                }
621            }
622        }
623    }
624}
625
626/** ------------------------------------------------------------------------------------------------------------- *
627 * @brief redistributeAST
628 *
629 * Apply the distribution law to reduce computations whenever possible.
630 ** ------------------------------------------------------------------------------------------------------------- */
631bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const {
632    bool anyChanges = false;
633    for (;;) {
634
635        DistributionGraph H;
636
637        generateDistributionGraph(block, G, H);
638
639        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
640        if (num_vertices(H) == 0) {
641            break;
642        }
643
644        DistributionSets distributionSets = safeDistributionSets(H, G);
645
646        if (LLVM_UNLIKELY(distributionSets.empty())) {
647            break;
648        }
649
650
651        break;
652
653
654
655//        for (const Vertex s : make_iterator_range(vertices(H))) {
656
657//            if (in_degree(s, H) == 0) {
658
659//                assert (sources.size() > 0);
660//                const VertexSet intermediary = outgoingVertexSet(sources.front(), makeGraphFacade(H));
661//                assert (intermediary.size() > 0);
662//                const VertexSet sinks = outgoingVertexSet(intermediary.front(), makeGraphFacade(H));
663//                assert (sinks.size() > 0);
664
665//                // Now begin transforming the AST
666//                circular_buffer<PabloAST *> Q(std::max(sources.size(), intermediary.size() + 1));
667//                for (const Vertex u : intermediary) {
668//                    Q.push_back(G[H[u]]);
669//                }
670//                const TypeId typeId = G[H[sinks.front()]]->getClassTypeId();
671//                assert (typeId == TypeId::And || typeId == TypeId::Or);
672//                PabloAST * merged = createTree(block, typeId, Q);
673//                for (const Vertex s : sources) {
674//                    Q.push_back(G[H[s]]);
675//                }
676//                Q.push_back(merged);
677//                PabloAST * masked = createTree(block, (typeId == TypeId::Or) ? TypeId::And : TypeId::Or, Q);
678
679//                // Eliminate the edges from our original graph G
680//                for (const Vertex u : intermediary) {
681//                    const auto uu = H[u];
682//                    for (const Vertex s : sources) {
683//                        assert(edge(H[s], uu, G).second);
684//                        remove_edge(H[s], uu, G);
685//                    }
686//                    for (const Vertex t : sinks) {
687//                        assert(edge(uu, H[t], G).second);
688//                        remove_edge(uu, H[t], G);
689//                    }
690//                }
691
692//                // Finally update G to match the desired changes
693//                const Vertex x = add_vertex(merged, G);
694//                const Vertex y = add_vertex(masked, G);
695//                for (const Vertex u : intermediary) {
696//                    add_edge(H[u], x, G);
697//                }
698//                add_edge(x, y, G);
699//                for (const Vertex s : sources) {
700//                    add_edge(H[s], y, G);
701//                }
702//                for (const Vertex t : sinks) {
703//                    add_edge(y, H[t], G);
704//                }
705
706//            }
707
708//        }
709//        anyChanges = true;
710
711    }
712
713    return anyChanges;
714}
715
716}
Note: See TracBrowser for help on using the repository browser.