source: icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp @ 5464

Last change on this file since 5464 was 5464, checked in by nmedfort, 2 years ago

Restructuring work for the Driver classes. Start of work to eliminate the memory leaks with the ExecutionEngine?. Replaced custom AlignedMalloc? with backend call to std::aligned_malloc. Salvaged some work on DistributionPass? for reevaluation.

File size: 30.3 KB
Line 
1#include "distributivepass.h"
2
3#include <pablo/pablo_kernel.h>
4#include <pablo/codegenstate.h>
5#include <pablo/branch.h>
6#include <pablo/pe_string.h>
7#include <pablo/pe_integer.h>
8#include <pablo/pe_zeroes.h>
9#include <pablo/pe_ones.h>
10#include <pablo/boolean.h>
11#include <boost/container/flat_set.hpp>
12#include <boost/container/flat_map.hpp>
13#include <boost/graph/adjacency_list.hpp>
14#include <boost/graph/topological_sort.hpp>
15#include <boost/function_output_iterator.hpp>
16
17#include <boost/graph/strong_components.hpp>
18#include <llvm/Support/raw_ostream.h>
19
20using namespace boost;
21using namespace boost::container;
22using namespace llvm;
23
24using TypeId = pablo::PabloAST::ClassTypeId;
25using VertexData = std::pair<pablo::PabloAST *, TypeId>;
26
27using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, VertexData, pablo::PabloAST *>;
28using Vertex = Graph::vertex_descriptor;
29
30using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
31using DistributionVertex = DistributionGraph::vertex_descriptor;
32
33using VertexSet = std::vector<Vertex>;
34using Biclique = std::pair<VertexSet, VertexSet>;
35using BicliqueSet = std::vector<Biclique>;
36using DistributionSet = std::tuple<VertexSet, VertexSet, VertexSet>;
37using DistributionSets = std::vector<DistributionSet>;
38
39using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
40
41namespace pablo {
42
43
44/** ------------------------------------------------------------------------------------------------------------- *
45 * @brief printGraph
46 ** ------------------------------------------------------------------------------------------------------------- */
47static void printGraph(const Graph & G, const std::string & name, llvm::raw_ostream & out) {
48
49    std::vector<unsigned> c(num_vertices(G));
50    strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
51
52    out << "digraph " << name << " {\n";
53    for (auto u : make_iterator_range(vertices(G))) {
54        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
55            continue;
56        }
57        out << "v" << u << " [label=\"" << u << ": ";
58        TypeId typeId;
59        PabloAST * expr;
60        std::tie(expr, typeId) = G[u];
61        bool temporary = false;
62        bool error = false;
63        if (expr == nullptr || (typeId != expr->getClassTypeId() && typeId != TypeId::Var)) {
64            temporary = true;
65            switch (typeId) {
66                case TypeId::And:
67                    out << "And";
68                    break;
69                case TypeId::Or:
70                    out << "Or";
71                    break;
72                case TypeId::Xor:
73                    out << "Xor";
74                    break;
75                case TypeId::Not:
76                    out << "Not";
77                    break;
78                default:
79                    out << "???";
80                    error = true;
81                    break;
82            }
83            if (expr) {
84                out << " ("; expr->print(out); out << ")";
85            }
86        } else {
87            expr->print(out);
88        }
89        out << "\"";
90        if (typeId == TypeId::Var) {
91            out << " style=dashed";
92        }
93        if (error) {
94            out << " color=red";
95        } else if (temporary) {
96            out << " color=blue";
97        }
98        out << "];\n";
99    }
100    for (auto e : make_iterator_range(edges(G))) {
101        const auto s = source(e, G);
102        const auto t = target(e, G);
103        out << "v" << s << " -> v" << t;
104        bool cyclic = (c[s] == c[t]);
105        if (G[e] || cyclic) {
106            out << " [";
107            PabloAST * const expr = G[e];
108            if (expr) {
109                out << "label=\"";
110                expr->print(out);
111                out << "\" ";
112             }
113             if (cyclic) {
114                out << "color=red ";
115             }
116             out << "]";
117        }
118        out << ";\n";
119    }
120
121    if (num_vertices(G) > 0) {
122
123        out << "{ rank=same;";
124        for (auto u : make_iterator_range(vertices(G))) {
125            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
126                out << " v" << u;
127            }
128        }
129        out << "}\n";
130
131        out << "{ rank=same;";
132        for (auto u : make_iterator_range(vertices(G))) {
133            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
134                out << " v" << u;
135            }
136        }
137        out << "}\n";
138
139    }
140
141    out << "}\n\n";
142    out.flush();
143}
144
145struct PassContainer {
146
147    /** ------------------------------------------------------------------------------------------------------------- *
148     * @brief run
149     *
150     * Based on the knowledge that:
151     *
152     *  (ASSOCIATIVITY)    A ∧ (B ∧ C) ⇔ (A ∧ B) ∧ C ⇔ A ∧ B ∧ C   and   A √ (B √ C) ⇔ (A √ B) √ C ⇔ A √ B √ C
153     *
154     *  (IDENTITY)         A √ 0 ⇔ A   and   A ∧ 1 = A
155     *
156     *  (ANNULMENT)        A ∧ 0 ⇔ 0   and   A √ 1 = 1
157     *
158     *  (IDEMPOTENT)       A √ (A √ B) ⇔ A √ B   and   A ∧ (A ∧ B) ⇔ A ∧ B
159     *
160     *  (ABSORBTION)       A √ (A ∧ B) ⇔ A ∧ (A √ B) ⇔ A
161     *
162     *  (COMPLEMENT)       A √ ¬A ⇔ 1   and   A ∧ ¬A = 0
163     *
164     *  (DISTRIBUTIVITY)   (A ∧ B) √ (A ∧ C) ⇔ A ∧ (B √ C)   and   (A √ B) ∧ (A √ C) ⇔ A √ (B ∧ C)
165     *
166     * Try to eliminate some of the unnecessary operations from the current Variadic expressions
167     ** ------------------------------------------------------------------------------------------------------------- */
168    void run(PabloBlock * const block) {
169        Statement * stmt = block->front();
170        // Statement * first = stmt;
171        while (stmt) {
172            Statement * next = stmt->getNextNode();
173            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();
185                run(cast<Branch>(stmt)->getBody());
186                G.clear();
187                M.clear();
188            } else {
189                addStatement(stmt);
190            }
191            stmt = next;
192        }
193    }
194
195protected:
196
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
215    /** ------------------------------------------------------------------------------------------------------------- *
216     * @brief applyAssociativeIdentityAnnulmentLaws
217     ** ------------------------------------------------------------------------------------------------------------- */
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)) {
229repeat:         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;
242                    }
243                }
244            } 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
272        return modified;
273    }
274
275    /** ------------------------------------------------------------------------------------------------------------- *
276     * @brief applyAbsorbtionComplementIdempotentLaws
277     ** ------------------------------------------------------------------------------------------------------------- */
278    bool applyAbsorbtionComplementIdempotentLaws() {
279        using in_edge_iterator = graph_traits<Graph>::in_edge_iterator;
280        bool modified = false;
281        for (const Vertex u : make_iterator_range(vertices(G))) {
282            const TypeId typeId = getType(u);
283            if (isDistributive(typeId)) {
284restart_loop:   in_edge_iterator ei_begin, ei_end;
285                std::tie(ei_begin, ei_end) = in_edges(u, G);
286                for (auto ei = ei_begin; ei != ei_end; ++ei) {
287                    const auto v = source(*ei, G);
288                    const auto innerTypeId = getType(v);
289                    if (isDistributive(innerTypeId) || innerTypeId == TypeId::Not) {
290                        in_edge_iterator ek_begin, ek_end;
291                        std::tie(ek_begin, ek_end) = in_edges(v, G);
292                        for (auto ej = ei_begin; ej != ei_end; ++ej) {
293                            for (auto ek = ek_begin; ek != ek_end; ++ek) {
294                                if (LLVM_UNLIKELY(source(*ej, G) == source(*ek, G))) {
295                                    if (LLVM_UNLIKELY(innerTypeId == TypeId::Not)) {
296                                        // complement
297                                        setType(u, typeId == TypeId::And ? TypeId::Zeroes : TypeId::Ones);
298                                        clear_in_edges(u, G);
299                                        goto abort_loop;
300                                    } else {
301                                        if (LLVM_LIKELY(innerTypeId != typeId)) {
302                                            // idempotent
303                                            remove_edge(*ei, G);
304                                        } else {
305                                            // absorbtion
306                                            remove_edge(*ej, G);
307                                        }
308                                        modified = true;
309                                        // this seldom occurs so if it does, just restart the process rather than
310                                        // trying to keep the iterators valid.
311                                        goto restart_loop;
312                                    }
313                                }
314                            }
315                        }
316                    }
317                }
318            }
319            abort_loop:;
320        }
321        return modified;
322    }
323
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
365     *
366     * Let (u) ∈ V(G) be a conjunction ∧ or disjunction √ and (v) be a ∧ or √ and the opposite type of (u). If (u,v) ∈
367     * E(G) and all outgoing edges of (v) lead to a vertex of the same type, add (u), (v) and any vertex (w) in which
368     * (w,v) ∈ E(G) to the distribution graph H as well as the edges indicating their relationships within G.
369     *
370     *                  (?) (?) (?) <-- w1, w2, ...
371     *                     \ | /
372     *                      (v)   <-- v
373     *                     /   \
374     *            u --> (∧)     (∧)
375     *
376     ** ------------------------------------------------------------------------------------------------------------- */
377    void generateDistributionGraph() {
378
379        assert (D.empty());
380
381        flat_set<Vertex> distributable;
382        flat_set<Vertex> observed;
383
384        for (const Vertex u : make_iterator_range(vertices(G))) {
385            const TypeId outerTypeId = getType(u);
386            if (isDistributive(outerTypeId)) {
387                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();
422            }
423        }
424
425        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);
520
521        return modified;
522    }
523
524
525    /** ------------------------------------------------------------------------------------------------------------- *
526     * @brief enumerateBicliques
527     *
528     * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
529     * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
530     * bipartition A and their adjacencies to be in B.
531      ** ------------------------------------------------------------------------------------------------------------- */
532
533    BicliqueSet enumerateBicliques(const VertexSet & A) {
534        using IntersectionSets = std::set<VertexSet>;
535
536        IntersectionSets B1;
537        for (auto u : A) {
538            if (in_degree(u, H) > 0) {
539                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));
543                }
544                std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
545                B1.insert(std::move(incomingAdjacencies));
546            }
547        }
548
549        IntersectionSets B(B1);
550
551        IntersectionSets Bi;
552
553        VertexSet clique;
554        for (auto i = B1.begin(); i != B1.end(); ++i) {
555            for (auto j = i; ++j != B1.end(); ) {
556                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
557                if (clique.size() > 0) {
558                    if (B.count(clique) == 0) {
559                        Bi.insert(clique);
560                    }
561                    clique.clear();
562                }
563            }
564        }
565
566        for (;;) {
567            if (Bi.empty()) {
568                break;
569            }
570            B.insert(Bi.begin(), Bi.end());
571            IntersectionSets Bk;
572            for (auto i = B1.begin(); i != B1.end(); ++i) {
573                for (auto j = Bi.begin(); j != Bi.end(); ++j) {
574                    std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
575                    if (clique.size() > 0) {
576                        if (B.count(clique) == 0) {
577                            Bk.insert(clique);
578                        }
579                        clique.clear();
580                    }
581                }
582            }
583            Bi.swap(Bk);
584        }
585
586        BicliqueSet cliques;
587        cliques.reserve(B.size());
588        for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
589            VertexSet Ai(A);
590            for (const Vertex u : *Bi) {
591                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));
595                }
596                std::sort(Aj.begin(), Aj.end());
597                VertexSet Ak;
598                Ak.reserve(std::min(Ai.size(), Aj.size()));
599                std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
600                Ai.swap(Ak);
601            }
602            assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
603            cliques.emplace_back(std::move(Ai), std::move(*Bi));
604        }
605        return std::move(cliques);
606    }
607
608
609    /** ------------------------------------------------------------------------------------------------------------- *
610     * @brief independentCliqueSets
611     ** ------------------------------------------------------------------------------------------------------------- */
612    template <unsigned side>
613    BicliqueSet && independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) {
614
615
616        const auto l = cliques.size();
617        IndependentSetGraph I(l);
618
619        // Initialize our weights
620        for (unsigned i = 0; i != l; ++i) {
621            I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
622        }
623
624        // Determine our constraints
625        for (unsigned i = 0; i != l; ++i) {
626            for (unsigned j = i + 1; j != l; ++j) {
627                if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
628                    boost::add_edge(i, j, I);
629                }
630            }
631        }
632
633        // Use the greedy algorithm to choose our independent set
634        VertexSet selected;
635        for (;;) {
636            unsigned w = 0;
637            Vertex u = 0;
638            for (unsigned i = 0; i != l; ++i) {
639                if (I[i] > w) {
640                    w = I[i];
641                    u = i;
642                }
643            }
644            if (w < minimum) break;
645            selected.push_back(u);
646            I[u] = 0;
647            for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
648                I[v] = 0;
649            }
650        }
651
652        // Sort the selected list and then remove the unselected cliques
653        std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
654        auto end = cliques.end();
655        for (const unsigned offset : selected) {
656            end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
657        }
658        cliques.erase(cliques.begin(), end);
659
660        return std::move(cliques);
661    }
662
663    /** ------------------------------------------------------------------------------------------------------------- *
664     * @brief removeUnhelpfulBicliques
665     *
666     * An intermediary vertex could have more than one outgoing edge but if any that are not directed to vertices in
667     * the lower biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if
668     * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
669     ** ------------------------------------------------------------------------------------------------------------- */
670    BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques) {
671        for (auto ci = cliques.begin(); ci != cliques.end(); ) {
672            const auto cardinalityA = std::get<0>(*ci).size();
673            VertexSet & B = std::get<1>(*ci);
674            for (auto bi = B.begin(); bi != B.end(); ) {
675                if (out_degree(H[*bi], G) == cardinalityA) {
676                    ++bi;
677                } else {
678                    bi = B.erase(bi);
679                }
680            }
681            if (B.size() > 1) {
682                ++ci;
683            } else {
684                ci = cliques.erase(ci);
685            }
686        }
687        return std::move(cliques);
688    }
689
690    /** ------------------------------------------------------------------------------------------------------------- *
691     * @brief addTemporary
692     ** ------------------------------------------------------------------------------------------------------------- */
693    Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) {
694        return add_vertex(std::make_pair(expr, typeId), G);
695    }
696
697    /** ------------------------------------------------------------------------------------------------------------- *
698     * @brief addExpression
699     ** ------------------------------------------------------------------------------------------------------------- */
700    Vertex addExpression(PabloAST * const expr) {
701        const auto f = M.find(expr);
702        if (LLVM_LIKELY(f != M.end())) {
703            return f->second;
704        }
705        TypeId typeId = TypeId::Var;
706        if (isa<Zeroes>(expr)) {
707            typeId = TypeId::Zeroes;
708        } else if (isa<Ones>(expr)) {
709            typeId = TypeId::Ones;
710        }
711        const auto u = makeVertex(typeId, expr);
712        M.emplace(expr, u);
713        return u;
714    }
715
716    /** ------------------------------------------------------------------------------------------------------------- *
717     * @brief addStatement
718     ** ------------------------------------------------------------------------------------------------------------- */
719    void addStatement(Statement * const stmt) {
720        assert (M.count(stmt) == 0);
721        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        }
736    }
737
738    /** ------------------------------------------------------------------------------------------------------------- *
739     * @brief intersects
740     ** ------------------------------------------------------------------------------------------------------------- */
741    template <class Type>
742    inline bool intersects(Type & A, Type & B) {
743        auto first1 = A.begin(), last1 = A.end();
744        auto first2 = B.begin(), last2 = B.end();
745        while (first1 != last1 && first2 != last2) {
746            if (*first1 < *first2) {
747                ++first1;
748            } else if (*first2 < *first1) {
749                ++first2;
750            } else {
751                return true;
752            }
753        }
754        return false;
755    }
756
757    TypeId getType(const Vertex u) {
758        return std::get<1>(G[u]);
759    }
760
761    void setType(const Vertex u, const TypeId typeId) {
762        std::get<1>(G[u]) = typeId;
763    }
764
765    static bool isIdentityRelation(const TypeId a, const TypeId b) {
766        return !((a == TypeId::Zeroes) ^ (b == TypeId::Or));
767    }
768
769    static bool isAssociative(const TypeId typeId) {
770        return (isDistributive(typeId) || typeId == TypeId::Xor);
771    }
772
773    static bool isDistributive(const TypeId typeId) {
774        return (typeId == TypeId::And || typeId == TypeId::Or);
775    }
776
777    static TypeId oppositeTypeId(const TypeId typeId) {
778        assert (isDistributive(typeId));
779        return (typeId == TypeId::And) ? TypeId::Or : TypeId::And;
780    }
781
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
786private:
787
788    Graph G;
789    flat_map<pablo::PabloAST *, Vertex> M;
790
791    DistributionGraph H;
792    flat_map<Vertex, DistributionVertex> D;
793
794};
795
796/** ------------------------------------------------------------------------------------------------------------- *
797 * @brief optimize
798 ** ------------------------------------------------------------------------------------------------------------- */
799bool DistributivePass::optimize(PabloKernel * const kernel) {
800    PassContainer C;
801    C.run(kernel->getEntryBlock());
802    return true;
803}
804
805}
Note: See TracBrowser for help on using the repository browser.