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

Last change on this file since 5596 was 5596, checked in by nmedfort, 21 months ago

MAC OS Compile fix for DistributionPass?

File size: 81.6 KB
Line 
1#include "distributivepass.h"
2
3#include <pablo/pablo_kernel.h>
4#include <pablo/codegenstate.h>
5
6#include <pablo/boolean.h>
7#include <pablo/branch.h>
8#include <pablo/pe_advance.h>
9#include <pablo/pe_count.h>
10#include <pablo/pe_infile.h>
11#include <pablo/pe_integer.h>
12#include <pablo/pe_lookahead.h>
13#include <pablo/pe_matchstar.h>
14#include <pablo/pe_ones.h>
15#include <pablo/pe_scanthru.h>
16#include <pablo/pe_string.h>
17#include <pablo/pe_var.h>
18#include <pablo/pe_zeroes.h>
19#include <pablo/builder.hpp>
20
21#include <pablo/optimizers/pablo_simplifier.hpp>
22#include <pablo/analysis/pabloverifier.hpp>
23
24#include <boost/container/flat_set.hpp>
25#include <boost/container/flat_map.hpp>
26#include <boost/range/adaptor/reversed.hpp>
27#include <boost/graph/adjacency_list.hpp>
28#include <boost/graph/topological_sort.hpp>
29#include <boost/function_output_iterator.hpp>
30#include <boost/functional/hash.hpp>
31
32#include <set>
33#include <unordered_set>
34
35#include <boost/graph/strong_components.hpp>
36#include <llvm/Support/raw_ostream.h>
37#include <pablo/printer_pablos.h>
38
39using namespace boost;
40using namespace boost::container;
41using namespace llvm;
42using namespace pablo;
43
44using TypeId = PabloAST::ClassTypeId;
45
46enum class State {
47    Dead
48    , Live
49    , Modified
50};
51
52using UsageTime = size_t;
53
54using VertexData = std::tuple<PabloAST *, TypeId, State, UsageTime>;
55
56using OperandIndex = unsigned;
57
58struct svecS{};
59
60namespace boost {
61
62    template<class T>
63    struct __sorted_edge_vector : public std::vector<T> {
64        using iterator = typename std::vector<T>::iterator;
65        void push_back(const T & item) {
66            std::vector<T>::insert(std::upper_bound(std::vector<T>::begin(), std::vector<T>::end(), item), item);
67        }
68    };
69
70    template <class ValueType> struct container_gen<svecS, ValueType> {
71        typedef __sorted_edge_vector<ValueType> type;
72    };
73
74    template <> struct parallel_edge_traits<svecS> {
75        typedef allow_parallel_edge_tag type;
76    };
77
78    template<class T> graph_detail::vector_tag container_category(const __sorted_edge_vector<T>&) {
79        return graph_detail::vector_tag();
80    }
81
82    template <class T> graph_detail::unstable_tag iterator_stability(const __sorted_edge_vector<T>&) {
83        return graph_detail::unstable_tag();
84    }
85}
86
87namespace pablo {
88
89using Graph = adjacency_list<svecS, vecS, bidirectionalS, VertexData, OperandIndex, vecS>;
90using Vertex = Graph::vertex_descriptor;
91using Edge = Graph::edge_descriptor;
92using InEdgeIterator = graph_traits<Graph>::in_edge_iterator;
93using DistributionGraph = adjacency_list<setS, vecS, bidirectionalS, Vertex>;
94using DistributionVertex = DistributionGraph::vertex_descriptor;
95
96using Sequence = std::vector<Vertex>;
97using Biclique = std::pair<Sequence, Sequence>;
98using BicliqueSet = std::vector<Biclique>;
99using DistributionSet = std::tuple<Sequence, Sequence, Sequence>;
100using DistributionSets = std::vector<DistributionSet>;
101
102using IndependentSetGraph = adjacency_list<vecS, vecS, undirectedS, size_t>;
103
104struct PassContainer {
105
106    /** ------------------------------------------------------------------------------------------------------------- *
107     * @brief run
108     *
109     * Based on the knowledge that:
110     *
111     *  (ASSOCIATIVITY)    A ∧ (B ∧ C) ⇔ (A ∧ B) ∧ C ⇔ A ∧ B ∧ C   and   A √ (B √ C) ⇔ (A √ B) √ C ⇔ A √ B √ C
112     *
113     *  (IDENTITY)         A √ 0 ⇔ A   and   A ∧ 1 = A
114     *
115     *  (ANNULMENT)        A ∧ 0 ⇔ 0   and   A √ 1 = 1
116     *
117     *  (IDEMPOTENT)       A √ (A √ B) ⇔ A √ B   and   A ∧ (A ∧ B) ⇔ A ∧ B
118     *
119     *  (ABSORBTION)       A √ (A ∧ B) ⇔ A ∧ (A √ B) ⇔ A
120     *
121     *  (COMPLEMENT)       A √ ¬A ⇔ 1   and   A ∧ ¬A = 0
122     *
123     *  (DISTRIBUTIVITY)   (A ∧ B) √ (A ∧ C) ⇔ A ∧ (B √ C)   and   (A √ B) ∧ (A √ C) ⇔ A √ (B ∧ C)
124     *
125     *  (DE MORGAN'S)      ¬(A ∧ B) ⇔ ¬A √ ¬B   and   Â¬(A √ B) ⇔ ¬A ∧ ¬B
126     *
127     * Try to simplify the equations and eliminate some of the unnecessary statements
128     ** ------------------------------------------------------------------------------------------------------------- */
129    bool run(PabloKernel * const kernel) {
130        readAST(kernel->getEntryBlock());
131        if (LLVM_LIKELY(simplifyGraph())) {
132            rewriteAST(kernel->getEntryBlock());
133            return true;
134        }
135        return false;
136    }
137
138    PassContainer()
139    : reprocessGraph(false)
140    , V{0, IdentityHash(G), IdentityComparator(G)} {
141
142    }
143
144protected:
145
146    /** ------------------------------------------------------------------------------------------------------------- *
147     * @brief readAST
148     ** ------------------------------------------------------------------------------------------------------------- */
149    void readAST(PabloBlock * const block) {
150        for (Statement * stmt : *block) {
151            addStatement(stmt);
152            if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
153                readAST(cast<Branch>(stmt)->getBody());
154            }
155        }
156    }
157
158    /** ------------------------------------------------------------------------------------------------------------- *
159     * @brief rewriteAST
160     *
161     * The goal here is to rewrite the AST with the minimal amount of perturbation to the sequence of instructions
162     * themselves. The exception is that associative instructions are regenerated w.r.t. their sequence in the AST
163     ** ------------------------------------------------------------------------------------------------------------- */
164    size_t rewriteAST(PabloBlock * const entry, size_t count = 0) {
165
166        Statement * stmt = entry->front();
167
168        while (stmt) {
169
170            const Vertex u = findVertex(stmt);
171
172            // There are two reasons to ignore a statement: (1) it's dead or regenerable and thus not of interest,
173            // and (2), the value in G strictly dominates the statement. Typically, if two expressions are equivalent,
174            // they're in disjoint nested scopes. When this occurs, they're merged into a single vertex in G to avoid
175            // redundant computations but must still be written individually in the AST. Sometimes equivalent statements
176            // are found during optimization. If one such statement dominates the other, G must refer to the dominating
177            // statement to avoid producing an illegal AST.
178
179            if (LLVM_LIKELY(isDead(u) || isRegenerable(getType(u)))) {
180                stmt = stmt->eraseFromParent(false);
181                continue;
182            } else if (LLVM_UNLIKELY(isModified(u) && strictly_dominates(getValue(u), stmt))) {
183                stmt = stmt->replaceWith(getValue(u));
184                continue;
185            }
186
187            assert (isLive(u));
188            assert (stmt->getClassTypeId() == getType(u));
189            assert (hasValidOperandIndicies(u));
190            assert (in_degree(u, G) == stmt->getNumOperands());
191
192            // Suppose we take a subgraph of G that contains every operand we'd have to regenerate to execute this
193            // statement? We could apply local optimizations to the subgraph with respect to the last usage time of
194            // each non-regenerated value and minimize the pairwise difference in last usage time, taking into account
195            // that we can use negations of variables when they've been used more recently.
196
197            // This could take incorporate rematerialization by determining whether it is cheaper / possible to
198            // recompute a value with what is already given but the Simplifer Pass could undo these changes if it
199            // recognizes a duplicate value in scope.
200
201            entry->setInsertPoint(stmt->getPrevNode());
202            for (const auto e : make_iterator_range(in_edges(u, G))) {
203                stmt->setOperand(G[e], regenerateIfNecessary(stmt, entry, source(e, G), count));
204            }
205            setValue(u, stmt);
206            setLastUsageTime(u, ++count);
207
208            if (isa<Branch>(stmt)) {
209                count = rewriteAST(cast<Branch>(stmt)->getBody(), count);
210            }
211
212            stmt = stmt->getNextNode();
213        }
214
215        return count;
216    }
217
218    /** ------------------------------------------------------------------------------------------------------------- *
219     * @brief regenerateIfNecessary
220     *
221     * Does vertex (u) have a value and, if so, does value dominate the statement? If not, regenerate it.
222     ** ------------------------------------------------------------------------------------------------------------- */
223    PabloAST * regenerateIfNecessary(Statement * const ip, PabloBlock * const entry, const Vertex u, size_t & count) {
224        assert (isLive(u));
225        PabloAST * value = getValue(u);
226        if (!dominates(value, ip)) {
227
228            assert (isRegenerable(getType(u)));
229
230            // if the outdegree of this vertex > 1, try setting the insertion point to a dominating position?
231
232            for (const auto e : make_iterator_range(in_edges(u, G))) {
233                regenerateIfNecessary(ip, entry, source(e, G), count);
234            }
235
236            const auto n = in_degree(u, G);
237
238            if (LLVM_UNLIKELY(n == 0)) {
239                const TypeId typeId = getType(u);
240                assert (isConstant(typeId));
241                if (typeId == TypeId::Zeroes) {
242                    value = entry->createZeroes();
243                } else {
244                    value = entry->createOnes();
245                }
246            } else if (LLVM_LIKELY(n != 1)) {
247
248                const TypeId typeId = getType(u);
249
250                assert (isAssociative(typeId));
251
252                // Suppose we try to minimize the pairwise difference in last usage time,
253                // taking into account that we can use negations of variables when they've
254                // been used more recently. Take note to update the correct vertex if an
255                // ANDC can be used instead.
256
257                Vertex input[n];
258                unsigned i = 0;
259                for (auto e : make_iterator_range(in_edges(u, G))) {
260                    input[i++] = source(e, G);
261                    assert (getLastUsageTime(source(e, G)) > 0);
262                }
263
264                std::sort(input, input + n, [this](const Vertex u, const Vertex v) {
265                    return getLastUsageTime(u) < getLastUsageTime(v);
266                });
267
268//                for (unsigned i = 0; i < n; ++i) {
269//                    setLastUsageTime(input[i], ++count);
270//                }
271
272                PabloBuilder builder(entry);
273                value = getValue(input[0]);
274                for (unsigned i = 1; i < n; ++i) {
275                    PabloAST * const op = getValue(input[i]);                   
276                    switch (typeId) {
277                        case TypeId::And:
278                            value = builder.createAnd(value, op);
279                            break;
280                        case TypeId::Or:
281                            value = builder.createOr(value, op);
282                            break;
283                        case TypeId::Xor:
284                            value = builder.createXor(value, op);
285                            break;
286                        default:
287                            llvm_unreachable("impossible!");
288                    }
289                }
290            } else {
291                value = entry->createNot(getValue(getNegatedLiteral(u)));
292            }
293            assert (value);
294            setValue(u, value);
295            setUnmodified(u);
296            setLastUsageTime(u, ++count);
297        }       
298        return value;
299    }
300
301protected:
302
303    /** ------------------------------------------------------------------------------------------------------------- *
304     * @brief printGraph
305     ** ------------------------------------------------------------------------------------------------------------- */
306    void printGraph(const std::string & name, llvm::raw_ostream & out, std::vector<Vertex> restricted = {}) {
307
308        const auto n = num_vertices(G);
309        std::vector<unsigned> c(n);
310        const auto components = strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
311
312        std::vector<bool> show(n, false);
313        if (LLVM_LIKELY(restricted.empty() && n == components)) {
314            for (const auto u : make_iterator_range(vertices(G))) {
315                show[u] = isLive(u);
316            }
317        } else {
318            std::queue<Vertex> Q;
319            for (const auto m : restricted) {
320                if (m < n && isLive(m)) {
321                    show[m] = true;
322                    assert (Q.empty());
323                    Q.push(m);
324                    for (;;) {
325                        const auto u = Q.front();
326                        Q.pop();
327                        for (auto e : make_iterator_range(in_edges(u, G))) {
328                            const auto v = source(e, G);
329                            if (show[v] || !isLive(v)) {
330                                continue;
331                            }
332                            show[v] = true;
333                            Q.push(v);
334                        }
335                        if (Q.empty()) {
336                            break;
337                        }
338                    }
339                    for (auto e : make_iterator_range(out_edges(m, G))) {
340                        const auto v = target(e, G);
341                        show[v] = isLive(v) ? true : show[v];
342                    }
343                }
344            }
345        }
346
347        out << "digraph " << name << " {\n";
348        for (auto u : make_iterator_range(vertices(G))) {
349
350            if (show[u]) {
351
352                out << "v" << u << " [label=\"" << u << ": ";
353                TypeId typeId;
354                PabloAST * expr;
355                State state;
356
357                std::tie(expr, typeId, state, std::ignore) = G[u];
358
359                bool space = true;
360
361                switch (typeId) {
362                    case TypeId::And:
363                        out << "(∧)";
364                        break;
365                    case TypeId::Or:
366                        out << "(√)";
367                        break;
368                    case TypeId::Xor:
369                        out << "(⊕)";
370                        break;
371                    case TypeId::Not:
372                        out << "(¬)";
373                        break;
374                    case TypeId::Zeroes:
375                        out << "(⊥)";
376                        break;
377                    case TypeId::Ones:
378                        out << "(⊀)";
379                    default:
380                        space = false;
381                        break;
382                }
383                if (expr) {
384                    if (space) {
385                        out << ' ';
386                    }
387                    expr->print(out);
388                }
389
390                out << "\"";
391                if (!hasValidOperandIndicies(u)) {
392                    out << " color=red style=bold";
393                } else if (!(isImmutable(typeId) || out_degree(u, G) > 0)) {
394                    out << " color=orange style=bold";
395                } else if (isRegenerable(typeId)) {
396                    out << " color=blue";
397                    if (state == State::Modified) {
398                        out << " style=dashed";
399                    }
400                }
401                out << "];\n";
402            }
403        }
404        for (auto e : make_iterator_range(edges(G))) {
405            const auto s = source(e, G);
406            const auto t = target(e, G);
407            if (show[s] && show[t]) {
408                const auto cyclic = (c[s] == c[t]);
409                const auto nonAssoc = !isAssociative(getType(t));
410                out << "v" << s << " -> v" << t;
411                if (cyclic || nonAssoc) {
412                    out << " [";
413                    if (nonAssoc) {
414                        out << " label=\"" << G[e] << "\"";
415                    }
416                    if (cyclic) {
417                        out << " color=red";
418                    }
419                    out << "]";
420                }
421                out << ";\n";
422            }
423        }
424
425        out << "}\n\n";
426        out.flush();
427    }
428
429    /** ------------------------------------------------------------------------------------------------------------- *
430     * @brief simplifyGraph
431     ** ------------------------------------------------------------------------------------------------------------- */
432    bool simplifyGraph() {
433        bool modified = false;
434        errs() << "=================================================================\n";
435        printGraph("S", errs());
436        V.reserve(num_vertices(G));
437        for (;;) {
438            V.clear();
439            getReverseTopologicalOrdering();
440            if (compactGraph()) {
441                continue;
442            }
443            if (applyDistributivityLaw()) {
444                modified = true;
445                continue;
446            }
447            break;
448        }
449        if (modified) {
450            factorizeGraph();
451            errs() << "-----------------------------------------------------------------\n";
452            printGraph("F", errs());
453        }
454        return modified;
455    }
456
457    /** ------------------------------------------------------------------------------------------------------------- *
458     * @brief getReverseTopologicalOrdering
459     ** ------------------------------------------------------------------------------------------------------------- */
460    void getReverseTopologicalOrdering() {
461
462        struct PrePassInserter {
463            PrePassInserter & operator=(const Vertex u) {
464                if (LLVM_LIKELY(self.isLive(u))) {
465                    assert(self.hasValidOperandIndicies(u));
466                    if (LLVM_LIKELY(isImmutable(self.getType(u)) || out_degree(u, self.G) != 0)) {
467                        self.ordering.push_back(u);
468                    } else {
469                        self.removeVertex(u);
470                    }
471                }
472                return *this;
473            }
474
475            PrePassInserter(PassContainer & pc) : self(pc) { }
476            PrePassInserter & operator*() { return *this; }
477            PrePassInserter & operator++() { return *this; }
478            PrePassInserter & operator++(int) { return *this; }
479
480        public:
481            PassContainer & self;
482        };
483
484
485        ordering.clear();
486        ordering.reserve(num_vertices(G));
487        topological_sort(G, PrePassInserter(*this));
488        assert (!ordering.empty());
489    }
490
491    /** ------------------------------------------------------------------------------------------------------------- *
492     * @brief compactGraph
493     ** ------------------------------------------------------------------------------------------------------------- */
494    bool compactGraph() {
495        reprocessGraph = false;
496        for (const auto u : boost::adaptors::reverse(ordering)) {
497            if (LLVM_LIKELY(isLive(u))) {
498                const auto typeId = getType(u);
499                if (LLVM_UNLIKELY(isImmutable(typeId))) {
500                    continue;
501                }
502                assert (hasValidOperandIndicies(u));
503                if (LLVM_UNLIKELY(out_degree(u, G) == 0)) {
504                    removeVertex(u);
505                    continue;
506                }
507                if (LLVM_UNLIKELY(isConstant(typeId))) {
508                    if (processConstant(u, typeId)) {
509                        continue;
510                    }
511                } else if (isAssociative(typeId)) {
512                    if (processAssociative(u, typeId)) {
513                        continue;
514                    }
515                } else if (typeId == TypeId::Not) {
516                    if (processNegation(u)) {
517                        continue;
518                    }
519                }
520                consolidate(u);
521            }
522        }
523        return reprocessGraph;
524    }
525
526    /** ------------------------------------------------------------------------------------------------------------- *
527     * @brief processAssociative
528     ** ------------------------------------------------------------------------------------------------------------- */
529    bool processAssociative(const Vertex u, const TypeId typeId) {
530
531        assert (isLive(u));
532        assert (getType(u) == typeId);
533        assert (isAssociative(typeId));
534
535        if (LLVM_UNLIKELY(in_degree(u, G) == 0)) {
536            setModified(u);
537            setType(u, TypeId::Zeroes);
538            return processConstant(u, TypeId::Zeroes);
539        } else if (LLVM_UNLIKELY(in_degree(u, G) == 1)) {
540            // An associative operation with only one element is always equivalent to the element
541            const auto v = first_source(in_edges(u, G));
542            for (const auto e : make_iterator_range(out_edges(u, G))) {
543                addEdge(v, target(e, G), G[e]);               
544            }
545            removeVertex(u);
546            return true;
547        } else {
548            // Take the transitive closure of these arcs to reveal the underlying equations
549            if (transitiveClosure(u, typeId)) {
550                return true;
551            }
552            if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
553                canonicalizeXor(u);
554            } else { // is distributive
555                applyDeMorganExpansion(u, typeId);
556                if (LLVM_UNLIKELY(applyAbsorbtionComplementLaw(u, typeId))) {
557                    return true;
558                }
559            }
560        }
561        return false;
562    }
563
564    /** ------------------------------------------------------------------------------------------------------------- *
565     * @brief transitiveClosure
566     ** ------------------------------------------------------------------------------------------------------------- */
567    bool transitiveClosure(const Vertex u, const TypeId typeId) {
568        // Take the transitive closure of these arcs to reveal the underlying equations
569
570        assert (isLive(u));
571        assert (getType(u) == typeId);
572        assert (isAssociative(typeId));
573
574        Vertex removed[out_degree(u, G)];
575        unsigned n = 0;
576        for (auto ei : make_iterator_range(out_edges(u, G))) {
577            const auto v = target(ei, G);
578            if (getType(v) == typeId) {
579                assert(hasValidOperandIndicies(v));
580                for (auto ej : make_iterator_range(in_edges(u, G))) {
581                    addEdge(source(ej, G), v);
582                }
583                setModified(v);
584                removed[n++] = v;
585            }
586        }
587        for (unsigned i = 0; i < n; ++i) {
588            const auto v = removed[i];
589            assert (edge(u, v, G).second);
590            remove_edge(u, v, G);
591            assert(hasValidOperandIndicies(v));
592        }
593        if (out_degree(u, G) == 0) {
594            removeVertex(u);
595            return true;
596        }
597        return false;
598    }
599
600    /** ------------------------------------------------------------------------------------------------------------- *
601     * @brief canonicalizeXor
602     *
603     * (A ⊕ ¬B) = (A ⊕ B ⊕ 1) = ¬(A ⊕ B)
604     ** ------------------------------------------------------------------------------------------------------------- */
605    void canonicalizeXor(const Vertex u) {
606
607        assert (isLive(u));
608        assert (getType(u) == TypeId::Xor);
609
610        const auto l = in_degree(u, G);
611        Vertex negation[l];
612        unsigned n = 0, m = 0;
613        for (const auto e : make_iterator_range(in_edges(u, G))) {
614            const auto v = source(e, G);
615            const auto typeId = getType(v);
616            if (LLVM_UNLIKELY(typeId == TypeId::Not)) {
617                negation[n++] = v;
618            } else if (LLVM_UNLIKELY(typeId == TypeId::Ones)) {
619                negation[l - ++m] = v;
620            }
621        }
622        if (LLVM_UNLIKELY(n != 0 || m != 0)) {
623            for (unsigned i = 0; i < n; ++i) {
624                const auto v = negation[i];
625                assert (edge(v, u, G).second);
626                remove_edge(v, u, G);
627                addEdge(first_source(in_edges(v, G)), u);
628            }
629            for (unsigned i = 0; i < m; ++i) {
630                const auto v = negation[(l - 1) - i];
631                assert (edge(v, u, G).second);
632                remove_edge(v, u, G);
633            }
634            if (((n + m) & 1) != 0) {
635                const auto x = makeVertex(TypeId::Not);
636                for (const auto e : make_iterator_range(out_edges(u, G))) {
637                    add_edge(x, target(e, G), G[e], G);
638                }
639                clear_out_edges(u, G);
640                add_edge(u, x, 0, G);
641            }
642            setModified(u);
643            assert(hasValidOperandIndicies(u));
644        }
645    }
646
647    /** ------------------------------------------------------------------------------------------------------------- *
648     * @brief processNegation
649     ** ------------------------------------------------------------------------------------------------------------- */
650    bool processNegation(const Vertex u) {
651
652        assert (isLive(u));
653        assert ("negation must have one input!" && in_degree(u, G) == 1);
654        assert (getType(u) == TypeId::Not);
655
656        const auto v = first_source(in_edges(u, G));
657        const auto negatedTypeId = getType(v);
658        if (LLVM_UNLIKELY(negatedTypeId == TypeId::Not)) { // ¬¬A = A
659            const auto w = getNegatedLiteral(v);
660            for (const auto e : make_iterator_range(out_edges(u, G))) {
661                const auto v = target(e, G);
662                addEdge(w, v, G[e]);
663                setModified(v);
664            }
665            removeVertex(u);
666            return true;
667        }
668        return false;
669    }
670
671    /** ------------------------------------------------------------------------------------------------------------- *
672     * @brief applyDeMorganExpansion
673     ** ------------------------------------------------------------------------------------------------------------- */
674    bool applyDeMorganExpansion(const Vertex u, const TypeId typeId) {
675
676        assert (isLive(u));
677        assert (in_degree(u, G) > 0);
678        assert (getType(u) == typeId);
679        assert (isDistributive(typeId));
680
681        Vertex A[in_degree(u, G)];
682        unsigned n = 0;
683        for (const auto e : make_iterator_range(in_edges(u, G))) {
684            const auto v = source(e, G);
685            if (LLVM_UNLIKELY(getType(v) == TypeId::Not)) {
686                if (LLVM_UNLIKELY(isDistributive(getType(getNegatedLiteral(v))))) {
687                    A[n++] = v;
688                }
689            }
690        }
691
692        if (LLVM_UNLIKELY(n != 0)) {
693            for (unsigned i = 0; i < n; ++i) {
694                const auto v = A[i];
695                assert (edge(v, u, G).second);
696                assert (getType(v) == TypeId::Not);
697                remove_edge(v, u, G);
698                const auto w = getNegatedLiteral(v);
699                auto x = u;
700                const auto innerTypeId = oppositeTypeId(getType(w));
701                if (innerTypeId != typeId) {
702                    x = makeVertex(innerTypeId);
703                    add_edge(x, u, 0, G);
704                }
705                for (const auto e : make_iterator_range(in_edges(w, G))) {
706                    addEdge(getNegationOf(source(e, G)), x);
707                }
708            }
709            setModified(u);
710            reprocessGraph = true;
711            assert(hasValidOperandIndicies(u));
712            return true;
713        }
714        return false;
715    }
716
717    /** ------------------------------------------------------------------------------------------------------------- *
718     * @brief applyXorTransformation
719     *
720     * (A ∧ ¬B ∧ C) √ (¬A ∧ B ∧ D) ⇔ (A ⊕ B) ∧ ((A ∧ C) √ (B ∧ D))
721     *
722     * (A √ ¬B √ C) ∧ (¬A √ B √ D) ⇔ ¬(A ⊕ B) √ ((A √ C) ∧ (B √ D))
723     ** ------------------------------------------------------------------------------------------------------------- */
724    bool applyXorTransformation() {
725        reprocessGraph = false;
726        for (const auto u : ordering) {
727            const auto typeId = getType(u);
728            if (isDistributive(typeId)) {
729                if (LLVM_LIKELY(in_degree(u, G) > 1)) {
730                    while (LLVM_UNLIKELY(applyXorTransformation(u, typeId)));
731                }
732            }
733        }
734        return reprocessGraph;
735    }
736
737    /** ------------------------------------------------------------------------------------------------------------- *
738     * @brief applyXorTransformation
739     *
740     * (A ∧ ¬B ∧ C) √ (¬A ∧ B ∧ D) ⇔ (A ⊕ B) ∧ ((A ∧ C) √ (B ∧ D))
741     *
742     * (A √ ¬B √ C) ∧ (¬A √ B √ D) ⇔ ¬(A ⊕ B) √ ((A √ C) ∧ (B √ D))
743     ** ------------------------------------------------------------------------------------------------------------- */
744    bool applyXorTransformation(const Vertex u, const TypeId typeId) {
745
746        if (in_degree(u, G) != 2) {
747            return false;
748        }
749
750        unsigned clauses = 0;
751        unsigned count = 0;
752        assert (getType(u) == typeId);
753        const TypeId innerTypeId = oppositeTypeId(typeId);
754        assert (in_degree(u, G) > 1);
755
756        for (const auto e : make_iterator_range(in_edges(u, G))) {
757            const auto v = source(e, G);
758            if (isXorCandidate(v, innerTypeId)) {
759                ++clauses;
760                count += in_degree(v, G);
761            }
762        }
763
764        if (clauses > 1) {
765            unsigned B[clauses + 1];
766            Vertex C[clauses];
767            Vertex V[count];
768
769            unsigned i = 0, j = 0;
770
771            for (const auto e : make_iterator_range(in_edges(u, G))) {
772                const auto v = source(e, G);
773                if (isXorCandidate(v, innerTypeId)) {
774                    B[i] = j;
775                    C[i] = v;
776                    for (const auto e : make_iterator_range(in_edges(v, G))) {
777                        V[j++] = source(e, G);
778                    }
779                    // We know no clause contains {A, A}, {A, ¬A} or {¬¬A} for any A.
780                    std::sort(V + B[i++], V + j, [this](const Vertex u, const Vertex v){
781                        return removeNegation(u) < removeNegation(v);
782                    });
783                }
784            }
785            B[clauses] = j;
786
787            for (unsigned i = 0; i < (clauses - 1); ++i) {
788                for (unsigned j = (i + 1); j < clauses; ++j) {
789                    bool first = true;
790                    unsigned ei = B[i], ej = B[j], ek = 0;
791                    while (ei < B[i + 1] && ej < B[j + 1]) {
792                        if (V[ei] == V[ej]) {
793                            ++ei, ++ej;
794                        } else {
795                            if (LLVM_UNLIKELY(isNegationOf(V[ei], V[ej]))) {
796                                if (LLVM_LIKELY(first)) {
797                                    ek = ei;
798                                    first = false;
799                                    ++ei, ++ej;
800                                    continue;
801                                } else {
802                                    const auto x = V[ek];
803                                    const auto v = C[i];
804                                    const auto y = V[ej];
805                                    const auto w = C[j];
806
807                                    reprocessGraph = true;
808
809                                    assert (edge(x, v, G).second);
810                                    remove_edge(x, v, G);
811                                    assert (edge(y, w, G).second);
812                                    remove_edge(y, w, G);
813
814                                    const auto a = makeVertex(typeId);
815                                    add_edge(v, a, 0, G);
816                                    add_edge(w, a, 0, G);
817
818                                    const auto z = makeVertex(TypeId::Xor);
819                                    add_edge(x, z, 0, G);
820                                    add_edge(y, z, 0, G);
821
822                                    auto b = z;
823                                    if (LLVM_UNLIKELY(typeId == TypeId::And)) {
824                                        b = getNegationOf(z);
825                                    }
826                                    canonicalizeXor(z);
827                                    if (LLVM_UNLIKELY(b != z)) {
828                                        processNegation(b);
829                                    }
830
831                                    if (in_degree(u, G) == 2) {
832                                        clear_in_edges(u, G);
833                                        setType(u, innerTypeId);
834                                        add_edge(a, u, 0, G);
835                                        add_edge(b, u, 0, G);
836                                        return false;
837                                    } else {
838                                        assert (edge(v, u, G).second);
839                                        remove_edge(v, u, G);
840                                        assert (edge(w, u, G).second);
841                                        remove_edge(w, u, G);
842                                        const auto c = makeVertex(innerTypeId);
843                                        add_edge(a, c, 0, G);
844                                        add_edge(b, c, 0, G);
845                                        add_edge(c, u, 0, G);
846                                        assert (in_degree(u, G) > 1);
847                                        return true;
848                                    }
849                                }
850                            }
851                            if (removeNegation(V[ei]) < removeNegation(V[ej])) {
852                                ++ei;
853                            } else {
854                                ++ej;
855                            }
856                        }
857                    }
858                }
859            }
860        }
861        return false;
862    }
863
864    bool isXorCandidate(const Vertex u, const TypeId typeId) const {
865        assert (isAssociative(typeId));
866        return (getType(u) == typeId) && (out_degree(u, G) == 1) && (in_degree(u, G) > 1);
867    }
868
869    bool isNegationOf(const Vertex u, const Vertex v) const {
870        const auto t = (getType(u) == TypeId::Not);
871        if (t ^ (getType(v) == TypeId::Not)) {
872            if (t) {
873                return getNegatedLiteral(u) == v;
874            } else { // if (getType(y) == TypeId::Not) {
875                return u == getNegatedLiteral(v);
876            }
877        }
878        return false;
879    }
880
881    /** ------------------------------------------------------------------------------------------------------------- *
882     * @brief getNegationOf
883     ** ------------------------------------------------------------------------------------------------------------- */
884    Vertex getNegationOf(const Vertex u) {
885        if (getType(u) == TypeId::Not) {
886            return getNegatedLiteral(u);
887        } else {
888            for (const auto e : make_iterator_range(out_edges(u, G))) {
889                const auto v = target(e, G);
890                if (getType(v) == TypeId::Not) {
891                    return v;
892                }
893            }
894            const auto v = makeVertex(TypeId::Not);
895            add_edge(u, v, 0, G);
896            return v;
897        }
898    }
899
900    Vertex getNegatedLiteral(const Vertex u) const {
901        assert (getType(u) == TypeId::Not);
902        assert (in_degree(u, G) == 1);
903        return first_source(in_edges(u, G));
904    }
905
906    Vertex removeNegation(const Vertex u) const {
907        return getType(u) == TypeId::Not ? getNegatedLiteral(u) : u;
908    }
909
910    /** ------------------------------------------------------------------------------------------------------------- *
911     * @brief applyAbsorbtionComplementLaw
912     ** ------------------------------------------------------------------------------------------------------------- */
913    bool applyAbsorbtionComplementLaw(const Vertex u, const TypeId typeId) {
914
915        assert (isLive(u));
916        assert (in_degree(u, G) > 0);
917        assert (getType(u) == typeId);
918        assert (isDistributive(typeId));
919
920        Vertex A[in_degree(u, G)];
921        unsigned n = 0;
922        for (const auto ei : make_iterator_range(in_edges(u, G))) {
923            const auto v = source(ei, G);
924            assert (isLive(v));
925            const auto innerTypeId = getType(v);
926            if (innerTypeId == TypeId::Not) {
927                const auto w = getNegatedLiteral(v);
928                assert (isLive(w));
929                for (const auto ej : make_iterator_range(in_edges(u, G))) {
930                    if (LLVM_UNLIKELY(source(ej, G) == w)) {
931                        const auto complementTypeId = (typeId == TypeId::And) ? TypeId::Zeroes : TypeId::Ones;
932                        setModified(u);
933                        setType(u, complementTypeId);
934                        clear_in_edges(u, G);
935                        return processConstant(u, complementTypeId);
936                    }
937                }
938            } else if (innerTypeId == oppositeTypeId(typeId) && LLVM_UNLIKELY(absorbs(u, v))) {
939                A[n++] = v;
940            }
941        }
942
943        if (n) {
944            setModified(u);
945            reprocessGraph = true;
946            for (;;) {
947                const auto v = A[--n];
948                assert (edge(v, u, G).second);
949                remove_edge(v, u, G);
950                if (LLVM_UNLIKELY(out_degree(v, G) == 0)) {
951                    removeVertex(v);
952                }
953                if (LLVM_LIKELY(n == 0)) {
954                    break;
955                }
956            }
957        }
958
959        return false;
960    }
961
962    /** ------------------------------------------------------------------------------------------------------------- *
963     * @brief absorbs
964     ** ------------------------------------------------------------------------------------------------------------- */
965    bool absorbs(const Vertex u, const Vertex v) {
966        assert (getType(u) == oppositeTypeId(getType(v)));
967        for (const auto ei : make_iterator_range(in_edges(u, G))) {
968            for (const auto ej : make_iterator_range(in_edges(v, G))) {
969                if (LLVM_UNLIKELY(source(ei, G) == source(ej, G))) {
970                    return true;
971                }
972            }
973        }
974        return false;
975    }
976
977    /** ------------------------------------------------------------------------------------------------------------- *
978     * @brief processConstant
979     ** ------------------------------------------------------------------------------------------------------------- */
980    bool processConstant(const Vertex u, const TypeId typeId) {
981
982        const auto l = out_degree(u, G);
983        Vertex modification[l];
984        unsigned n = 0;
985        unsigned m = 0;
986
987        assert (isConstant(typeId));
988        assert (getType(u) == typeId);
989
990        for (auto e : make_iterator_range(out_edges(u, G))) {
991            const auto v = target(e, G);
992            const auto targetTypeId = getType(v);
993            if (LLVM_UNLIKELY(isDistributive(targetTypeId))) {
994                // typeId           targetTypeId     Optimization
995                // ------------     ------------     ------------
996                // Zeroes           Or               identity
997                // Zeroes           And              annulment (0)
998                // Ones             Or               annulment (1)
999                // Ones             And              identity
1000                if (isIdentityRelation(typeId, targetTypeId)) {
1001                    modification[l - ++n] = v; // fill in from the end
1002                } else { // annulment
1003                    setType(v, typeId);
1004                    modification[m++] = v;
1005                }
1006            } else if (LLVM_UNLIKELY(targetTypeId == TypeId::Not)) {
1007                const auto negatedTypeId = (typeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes;
1008                setType(u, negatedTypeId);
1009                modification[m++] = v;
1010            } else if (LLVM_UNLIKELY(isStreamOperation(typeId))) {
1011                if (LLVM_LIKELY(typeId == TypeId::Zeroes)) {
1012                    setType(v, TypeId::Zeroes);
1013                    modification[m++] = v;
1014                } else { // if (typeId == TypeId::Ones) {
1015                    switch (targetTypeId) {
1016                        case TypeId::ScanThru:
1017                            if (LLVM_UNLIKELY(G[e] == 1)) {
1018                                setType(v, TypeId::Zeroes);
1019                                modification[m++] = v;
1020                            }
1021                            break;
1022                        case TypeId::MatchStar:
1023                            if (LLVM_UNLIKELY(G[e] == 0)) {
1024                                setType(v, TypeId::Ones);
1025                                modification[m++] = v;
1026                            }
1027                            break;
1028                        default: break;
1029                    }
1030                }
1031            }
1032        }
1033
1034        if (LLVM_LIKELY(n == 0 && m == 0)) {
1035            return false;
1036        }
1037
1038        // handle any identity graph modifications
1039        while (LLVM_UNLIKELY(n != 0)) {
1040            const auto v = modification[l - n--];
1041            setModified(v);
1042            remove_edge(u, v, G);
1043        }
1044
1045        // ... then handle the rest
1046        while (LLVM_LIKELY(m != 0)) {
1047            const auto v = modification[--m];
1048            setModified(v);
1049            clear_in_edges(v, G);
1050        }
1051
1052        if (LLVM_UNLIKELY(out_degree(u, G) == 0)) {
1053            removeVertex(u);
1054            return true;
1055        }
1056
1057        return false;
1058    }
1059
1060    /** ------------------------------------------------------------------------------------------------------------- *
1061     * @brief applyDistributivityLaw
1062     *
1063     * sources        (s)               inner       (√)   (√)
1064     *               /   \                            \   /
1065     * inner       (√)   (√)            x              (∧)
1066     *               \   /                              |
1067     * outer          (∧)               sources         |  (s)
1068     *                                                  | /
1069     *                                  y              (√)
1070     *                                                  |
1071     *                                  outer          (∧)
1072     *
1073     ** ------------------------------------------------------------------------------------------------------------- */
1074    bool applyDistributivityLaw() {
1075
1076        makeDistributionSubgraph();
1077
1078        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
1079        if (LLVM_UNLIKELY(distributable.empty())) {
1080            return false;
1081        }
1082
1083        bool modified = false;
1084
1085        const auto lowerSet = obtainDistributableClauses(distributable);
1086        for (const auto & lower : lowerSet) {
1087            const auto & outer = std::get<0>(lower);
1088            const auto upperSet = obtainDistributableSources(std::get<1>(lower));
1089            for (const auto & upper : upperSet) {
1090
1091                const auto & inner = std::get<0>(upper);
1092                const auto & sources = std::get<1>(upper);
1093
1094                const auto outerTypeId = getType(Gd[outer[0]]);
1095                const auto innerTypeId = oppositeTypeId(outerTypeId);
1096
1097                // Update G to match the desired change
1098                auto x = makeVertex(outerTypeId);
1099                auto y = makeVertex(innerTypeId);
1100
1101                for (const Vertex i : sources) {
1102                    const auto u = Gd[i];
1103                    for (const Vertex j : inner) {
1104                        const auto v = Gd[j];
1105                        assert (edge(u, v, G).second);
1106                        assert (getType(v) == innerTypeId);
1107                        remove_edge(u, v, G);
1108                    }
1109                    add_edge(u, y, 0, G);
1110                }
1111                y = consolidate(y);
1112                for (const auto i : inner) {
1113                    const auto u = Gd[i];
1114                    assert (getType(u) == innerTypeId);
1115                    for (const Vertex j : outer) {
1116                        const auto v = Gd[j];
1117                        assert (edge(u, v, G).second);
1118                        assert (getType(v) == outerTypeId);
1119                        remove_edge(u, v, G);
1120                    }
1121                    add_edge(u, x, 0, G);
1122                }
1123                x = consolidate(x);
1124                addEdge(x, y);
1125                for (const Vertex i : outer) {
1126                    const auto u = Gd[i];
1127                    assert (getType(u) == outerTypeId);
1128                    setModified(u);
1129                    addEdge(y, u);
1130                }
1131                modified = true;
1132            }
1133        }
1134
1135        Gd.clear();
1136        Md.clear();
1137
1138        return modified;
1139    }
1140
1141    /** ------------------------------------------------------------------------------------------------------------- *
1142     * @brief makeDistributionSubgraph
1143     ** ------------------------------------------------------------------------------------------------------------- */
1144    void makeDistributionSubgraph() {
1145        // TODO: instead of creating a subgraph, mark the vertices in G as being part of the subgraph? The last usage
1146        // time could be a "round counter"
1147        distributable.clear();
1148        for (const auto u : boost::adaptors::reverse(ordering)) {
1149            if (LLVM_LIKELY(isLive(u) && out_degree(u, G) != 0)) {
1150                const auto outerTypeId = getType(u);
1151                if (isDistributive(outerTypeId)) {
1152                    const auto n = in_degree(u, G);
1153                    if (n < 2) continue;
1154                    assert (n > 1);
1155                    const auto innerTypeId = oppositeTypeId(getType(u));
1156                    Vertex D[n];
1157                    unsigned count = 0;
1158                    for (const auto ei : make_iterator_range(in_edges(u, G))) {
1159                        const auto v = source(ei, G);
1160                        assert (isLive(v));
1161                        if (getType(v) == innerTypeId) {
1162                            bool safe = true;
1163                            for (const auto ej : make_iterator_range(out_edges(v, G))) {
1164                                const auto w = target(ej, G);
1165                                assert (isLive(w));
1166                                if (getType(w) != outerTypeId) {
1167                                    safe = false;
1168                                    break;
1169                                }
1170                            }
1171                            if (safe) {
1172                                D[count++] = v;
1173                            }
1174                        }
1175                    }
1176                    if (count > 1) {
1177                        const auto du = addDistributionVertex(u);
1178                        for (unsigned i = 0; i < count; ++i) {
1179                            const auto v = D[i];
1180                            assert (isLive(v));
1181                            if (getType(v) == innerTypeId) {
1182                                const auto dv = addDistributionVertex(v);
1183                                add_edge(dv, du, Gd);
1184                                for (const auto ej : make_iterator_range(in_edges(v, G))) {
1185                                    const auto w = source(ej, G);
1186                                    assert (isLive(w));
1187                                    add_edge(addDistributionVertex(w), dv, Gd);
1188                                }
1189                            }
1190                        }
1191                        distributable.push_back(du);
1192                    }
1193                }
1194            }
1195        }
1196        std::sort(distributable.begin(), distributable.end());
1197    }
1198
1199    /** ------------------------------------------------------------------------------------------------------------- *
1200     * @brief obtainDistributableClauses
1201     ** ------------------------------------------------------------------------------------------------------------- */
1202    BicliqueSet obtainDistributableClauses(const Sequence & S) {
1203        auto cliques = enumerateBicliques(S, Gd, 1, 2);
1204        // remove any cliques from our set that do not contain all of their users
1205        for (auto ci = cliques.begin(); ci != cliques.end(); ) {
1206            const auto & A = std::get<0>(*ci);
1207            auto & B = std::get<1>(*ci);
1208            for (auto bi = B.begin(); bi != B.end(); ) {
1209                if (out_degree(Gd[*bi], G) != A.size()) {
1210                    bi = B.erase(bi);
1211                } else {
1212                    ++bi;
1213                }
1214            }
1215            if (B.size() < 2) {
1216                ci = cliques.erase(ci);
1217            } else {
1218                ++ci;
1219            }
1220        }
1221        return makeIndependent(std::move(cliques), 0);
1222    }
1223
1224    /** ------------------------------------------------------------------------------------------------------------- *
1225     * @brief obtainDistributableSources
1226     ** ------------------------------------------------------------------------------------------------------------- */
1227    BicliqueSet obtainDistributableSources(const Sequence & S) {
1228        return makeIndependent(enumerateBicliques(S, Gd, 2, 1), 0);
1229    }
1230
1231    /** ------------------------------------------------------------------------------------------------------------- *
1232     * @brief factorizeGraph
1233     *
1234     * Factorize the associative operations in the final graph
1235     ** ------------------------------------------------------------------------------------------------------------- */
1236    void factorizeGraph() {
1237
1238        Sequence associative;
1239        for (const auto u : make_iterator_range(vertices(G))) {
1240            if (isLive(u) && isAssociative(getType(u))) {
1241                associative.push_back(u);
1242            }
1243        }
1244
1245        // Although we risk losing better combinations by greedily taking the larger factorings,
1246        // choosing only those of minSize or greater first can significantly reduce the running
1247        // time of this optimization.
1248
1249        Sequence group[3];
1250
1251        const TypeId typeCode[3] = { TypeId::And, TypeId::Or, TypeId::Xor };
1252
1253        for (;;) {
1254
1255            auto factors = makeIndependent(enumerateBicliques(associative, G, 2, 2), 1);
1256            if (factors.empty()) {
1257                break;
1258            }
1259
1260            bool unchanged = true;
1261
1262            for (auto & factor : factors) {
1263                const auto & sources = std::get<1>(factor);
1264                assert (sources.size() > 1);
1265                auto & targets = std::get<0>(factor);
1266                assert (targets.size() > 1);
1267
1268                for (unsigned k = 0; k < 3; ++k) {
1269                    assert (group[k].empty());
1270                }
1271
1272                // Group the target sets and check whether any target is the factorization
1273                Vertex t[3];
1274                bool create[3] = { true, true, true };
1275                for (const auto u : targets) {
1276                    assert (hasValidOperandIndicies(u));
1277                    const auto k = factorGroup(getType(u));
1278                    if (LLVM_UNLIKELY(in_degree(u, G) == sources.size())) {
1279                        if (LLVM_LIKELY(create[k])) {
1280                            t[k] = u;
1281                            create[k] = false;
1282                        } else {
1283                            for (auto e : make_iterator_range(out_edges(u, G))) {
1284                                addEdge(t[k], target(e, G), G[e]);
1285                            }
1286                            removeVertex(u);
1287                        }
1288                    } else {
1289                        group[k].push_back(u);
1290                    }
1291                }
1292
1293                for (unsigned k = 0; k < 3; ++k) {
1294                    if (LLVM_LIKELY(group[k].empty())) {
1295                        continue;
1296                    }
1297                    if (LLVM_LIKELY(create[k])) {
1298                        t[k] = makeVertex(typeCode[k]);
1299                        for (auto u : sources) {
1300                            add_edge(u, t[k], 0, G);
1301                        }
1302                        associative.push_back(t[k]);
1303                    }
1304                    assert (hasValidOperandIndicies(t[k]));
1305                    // Remove the biclique between the source and target vertices
1306                    for (auto u : sources) {
1307                        for (auto v : group[k]) {
1308                            assert (getType(v) == typeCode[k]);
1309                            assert (edge(u, v, G).second);
1310                            boost::remove_edge(u, v, G);
1311                        }
1312                    }
1313                    // ... and replace it with the factorization
1314                    for (auto v : group[k]) {
1315                        assert (getType(v) == typeCode[k]);
1316                        addEdge(t[k], v);
1317                        setModified(v);
1318                        assert(hasValidOperandIndicies(v));
1319                    }
1320                    group[k].clear();
1321                    unchanged = false;
1322                }
1323            }
1324
1325            if (unchanged) {
1326                break;
1327            }
1328        }
1329
1330//        #ifndef NDEBUG
1331//        for (const auto u : make_iterator_range(vertices(G))) {
1332//            if (LLVM_LIKELY(isLive(u))) {
1333//                const auto typeId = getType(u);
1334//                if (isAssociative(typeId)) {
1335//                    if (in_degree(u, G) != 2) {
1336//                        bool atMostOneSourceVertexCanHaveAnOutDegreeOverOne = true;
1337//                        for (auto e : make_iterator_range(in_edges(u, G))) {
1338//                            if (out_degree(source(e, G), G) != 1) {
1339//                                assert (atMostOneSourceVertexCanHaveAnOutDegreeOverOne);
1340//                                atMostOneSourceVertexCanHaveAnOutDegreeOverOne = false;
1341//                            }
1342//                        }
1343//                    }
1344//                }
1345//            }
1346//        }
1347//        #endif
1348
1349    }
1350
1351    unsigned factorGroup(const TypeId typeId) {
1352        switch (typeId) {
1353            case TypeId::And:
1354                return 0; break;
1355            case TypeId::Or:
1356                return 1; break;
1357            case TypeId::Xor:
1358                return 2; break;
1359            default: llvm_unreachable("impossible");
1360        }
1361    }
1362
1363//    /** ------------------------------------------------------------------------------------------------------------- *
1364//     * @brief applyDeMorganContraction
1365//     ** ------------------------------------------------------------------------------------------------------------- */
1366//    bool applyDeMorganContraction(const Vertex u, const TypeId typeId) {
1367
1368//        assert (isLive(u));
1369//        assert (in_degree(u, G) > 0);
1370//        assert (getType(u) == typeId);
1371//        assert (isDistributive(typeId));
1372
1373//        Vertex T[in_degree(u, G)];
1374//        unsigned n = 0;
1375//        for (const auto e : make_iterator_range(in_edges(u, G))) {
1376//            const auto v = source(e, G);
1377//            if (getType(v) == TypeId::Not) {
1378//                T[n++] = v;
1379//            }
1380//        }
1381//        if (LLVM_UNLIKELY(n > 1)) {
1382//            const auto oppositeType = oppositeTypeId(typeId);
1383//            Vertex x = makeVertex(oppositeType);
1384//            for (unsigned i = 0; i < n; ++i) {
1385//                const auto v = T[i];
1386//                const auto w = first_source(in_edges(v, G));
1387//                add_edge(w, x, 0, G);
1388//                remove_edge(v, u, G);
1389//            }
1390//            x = consolidate(x);
1391//            if (in_degree(u, G) == 0) {
1392//                setType(u, TypeId::Not);
1393//                add_edge(x, u, 0, G);
1394//                processNegation(u);
1395//                return true;
1396//            } else {
1397//                Vertex y = makeVertex(TypeId::Not);
1398//                add_edge(x, y, 0, G);
1399//                y = consolidate(y);
1400//                add_edge(y, u, 0, G);
1401//                processNegation(y);
1402//            }
1403//            return processAssociative(x, oppositeType);
1404//        }
1405//        return false;
1406//    }
1407
1408
1409private:
1410
1411    /** ------------------------------------------------------------------------------------------------------------- *
1412     * @brief enumerateBicliques
1413     *
1414     * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
1415     * bicliques" by Alexe et. al. (2003). This implementation considers all verticies in set S to be in
1416     * bipartition A (0) and their *INCOMING* adjacencies to be in B (1).
1417     ** ------------------------------------------------------------------------------------------------------------- */
1418    template <typename Graph>
1419    BicliqueSet enumerateBicliques(const Sequence & S, const Graph & G, const unsigned minimumSizeA = 1, const unsigned minimumSizeB = 1) {
1420        using IntersectionSets = std::set<Sequence>;
1421
1422        assert (std::is_sorted(S.begin(), S.end()));
1423
1424        BicliqueSet cliques(0);
1425
1426        if (LLVM_LIKELY(S.size() >= minimumSizeA)) {
1427
1428            IntersectionSets B1;
1429            for (auto u : S) {
1430                const auto n = in_degree(u, G);
1431                if (n >= minimumSizeB) {
1432                    Sequence B;
1433                    B.reserve(n);
1434                    for (auto e : make_iterator_range(in_edges(u, G))) {
1435                        const auto v = source(e, G);
1436                        if (out_degree(v, G) >= minimumSizeA) {
1437                            B.push_back(v);
1438                        }
1439                    }
1440                    if (B.size() >= minimumSizeB) {
1441                        // std::sort(B.begin(), B.end());
1442                        assert (std::is_sorted(B.begin(), B.end()));
1443                        assert (std::unique(B.begin(), B.end()) == B.end());
1444                        B1.insert(std::move(B));
1445                    }
1446                }
1447            }
1448
1449            IntersectionSets B(B1);
1450
1451            IntersectionSets Bi;
1452
1453            Sequence T;
1454            for (auto i = B1.begin(), end = B1.end(); i != end; ++i) {
1455                assert (std::is_sorted(i->begin(), i->end()));
1456                for (auto j = i; ++j != end; ) {
1457                    assert (std::is_sorted(j->begin(), j->end()));
1458                    std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(T));
1459                    if ((T.size() >= minimumSizeB) && (B.count(T) == 0)) {
1460                        Bi.insert(T);
1461                    }
1462                    T.clear();
1463                }
1464            }
1465
1466            IntersectionSets Bj;
1467            for (;;) {
1468                if (Bi.empty()) {
1469                    break;
1470                }
1471                B.insert(Bi.begin(), Bi.end());
1472                for (auto i = B1.begin(); i != B1.end(); ++i) {
1473                    assert (std::is_sorted(i->begin(), i->end()));
1474                    for (auto j = Bi.begin(), end = Bi.end(); j != end; ++j) {
1475                        assert (std::is_sorted(j->begin(), j->end()));
1476                        std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(T));
1477                        if ((T.size() >= minimumSizeB) && (B.count(T) == 0)) {
1478                            Bj.insert(T);
1479                        }
1480                        T.clear();
1481                    }
1482                }
1483                Bi.swap(Bj);
1484                Bj.clear();
1485            }
1486
1487            cliques.reserve(B.size());
1488
1489            Sequence Aj;
1490            for (auto && Bi : B) {
1491                Sequence Ai(S);
1492                assert (Bi.size() >= minimumSizeB);
1493                bool largeEnough = true;
1494                for (const Vertex u : Bi) {
1495                    assert (std::is_sorted(Ai.begin(), Ai.end()));
1496                    assert (Ai.size() >= minimumSizeA);
1497                    T.clear();
1498                    const auto m = out_degree(u, G);
1499                    assert (m >= minimumSizeA);
1500                    T.reserve(m);
1501                    for (auto e : make_iterator_range(out_edges(u, G))) {
1502                        T.push_back(target(e, G));
1503                    }
1504                    // std::sort(T.begin(), T.end());
1505                    assert (std::is_sorted(T.begin(), T.end()));
1506                    assert (std::unique(T.begin(), T.end()) == T.end());
1507                    Aj.clear();
1508                    Aj.reserve(std::min(Ai.size(), T.size()));
1509                    std::set_intersection(Ai.begin(), Ai.end(), T.begin(), T.end(), std::back_inserter(Aj));
1510                    if (Aj.size() < minimumSizeA) {
1511                        largeEnough = false;
1512                        break;
1513                    }
1514                    Ai.swap(Aj);
1515                }
1516                if (largeEnough) {
1517                    cliques.emplace_back(std::move(Ai), std::move(Bi));
1518                }
1519            }
1520
1521        }
1522
1523        return cliques;
1524    }
1525
1526    /** ------------------------------------------------------------------------------------------------------------- *
1527     * @brief makeIndependent
1528     ** ------------------------------------------------------------------------------------------------------------- */
1529    BicliqueSet && makeIndependent(BicliqueSet && S, const unsigned independentSide) {
1530
1531        const auto l = S.size();
1532        assert (independentSide < 2);
1533        if (LLVM_LIKELY(l > 1)) {
1534
1535            IndependentSetGraph I(l);
1536
1537            // Initialize our weights
1538            for (unsigned i = 0; i != l; ++i) {
1539                I[i] = std::get<0>(S[i]).size() * std::get<1>(S[i]).size();
1540            }
1541
1542            // Determine our constraints
1543            for (unsigned i = 0; i != l; ++i) {
1544                const auto & Si = (independentSide == 0) ? std::get<0>(S[i]) : std::get<1>(S[i]);
1545                for (unsigned j = i + 1; j != l; ++j) {
1546                    const auto & Sj = (independentSide == 0) ? std::get<0>(S[j]) : std::get<1>(S[j]);
1547                    if (intersects(Si, Sj)) {
1548                        boost::add_edge(i, j, I);
1549                    }
1550                }
1551            }
1552
1553            // Use the greedy algorithm to choose our independent set
1554            Sequence selected;
1555            for (;;) {
1556                Vertex u = 0;
1557                auto w = I[0];
1558                for (unsigned i = 1; i != l; ++i) {
1559                    if (I[i] > w) {
1560                        w = I[i];
1561                        u = i;
1562                    }
1563                }
1564                if (LLVM_UNLIKELY(w == 0)) break;
1565                selected.push_back(u);
1566                I[u] = 0;
1567                for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
1568                    I[v] = 0;
1569                }
1570            }
1571
1572            // Sort the selected list and then remove the unselected cliques
1573            std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
1574            auto end = S.end();
1575            for (const unsigned offset : selected) {
1576                end = S.erase(S.begin() + offset + 1, end) - 1;
1577            }
1578            S.erase(S.begin(), end);
1579        }
1580
1581        return std::move(S);
1582    }
1583
1584    /** ------------------------------------------------------------------------------------------------------------- *
1585     * @brief makeVertex
1586     ** ------------------------------------------------------------------------------------------------------------- */
1587    Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) {
1588        reprocessGraph = true;
1589        return add_vertex(std::make_tuple(expr, typeId, expr ? State::Live : State::Modified, 0), G);
1590    }
1591
1592    /** ------------------------------------------------------------------------------------------------------------- *
1593     * @brief addExpression
1594     ** ------------------------------------------------------------------------------------------------------------- */
1595    Vertex addExpression(PabloAST * const expr) {
1596        assert (expr);
1597        const auto f = M.find(expr);
1598        if (LLVM_LIKELY(f != M.end())) {
1599            return f->second;
1600        }
1601        assert (isConstant(expr->getClassTypeId()) || isLiteral(expr->getClassTypeId()));
1602        const auto u = makeVertex(expr->getClassTypeId(), expr);
1603        M.emplace(expr, u);
1604        return u;
1605    }
1606
1607    /** ------------------------------------------------------------------------------------------------------------- *
1608     * @brief addStatement
1609     ** ------------------------------------------------------------------------------------------------------------- */
1610    Vertex addStatement(Statement * const stmt) {
1611        assert (stmt);
1612        assert (M.count(stmt) == 0);
1613        const auto typeId = stmt->getClassTypeId();
1614        if (LLVM_UNLIKELY(typeId == TypeId::Sel)) {
1615            const auto c = addExpression(cast<Sel>(stmt)->getCondition());
1616            const auto t = addExpression(cast<Sel>(stmt)->getTrueExpr());
1617            const auto f = addExpression(cast<Sel>(stmt)->getFalseExpr());
1618            const auto u = makeVertex(TypeId::And);
1619            add_edge(c, u, 0, G);
1620            add_edge(t, u, 1, G);
1621            const auto n = makeVertex(TypeId::Not);
1622            add_edge(c, n, 0, G);
1623            const auto v = makeVertex(TypeId::And);
1624            add_edge(n, v, 0, G);
1625            add_edge(f, v, 1, G);
1626            const auto w = makeVertex(TypeId::Or);
1627            add_edge(u, w, 0, G);
1628            add_edge(v, w, 1, G);
1629            M.emplace(stmt, w);
1630            return w;
1631//        } else if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
1632//            assert (stmt->getNumOperands() == 2);
1633//            const auto a = addExpression(stmt->getOperand(0));
1634//            const auto b = addExpression(stmt->getOperand(1));
1635//            const auto c = makeVertex(TypeId::Not);
1636//            add_edge(b, c, 0, G);
1637//            const auto d = makeVertex(TypeId::Not);
1638//            add_edge(a, d, 0, G);
1639//            const auto u = makeVertex(TypeId::And);
1640//            add_edge(a, u, 0, G);
1641//            add_edge(c, u, 1, G);
1642//            const auto v = makeVertex(TypeId::And);
1643//            add_edge(b, v, 0, G);
1644//            add_edge(d, v, 1, G);
1645//            const auto w = makeVertex(TypeId::Or);
1646//            add_edge(u, w, 0, G);
1647//            add_edge(v, w, 1, G);
1648//            M.emplace(stmt, w);
1649//            return w;
1650        } else {
1651            const auto u = makeVertex(typeId, isRegenerable(typeId) ? nullptr : stmt);
1652            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1653                PabloAST * const op = stmt->getOperand(i);
1654                if (LLVM_UNLIKELY(isa<String>(op))) {
1655                    continue;
1656                }
1657                add_edge(addExpression(op), u, i, G);
1658            }
1659            assert(hasValidOperandIndicies(u));
1660            M.emplace(stmt, u);
1661            return u;
1662        }
1663    }
1664
1665    /** ------------------------------------------------------------------------------------------------------------- *
1666     * @brief addEdge
1667     ** ------------------------------------------------------------------------------------------------------------- */
1668    bool addEdge(const Vertex u, const Vertex v, const OperandIndex index = 0) {
1669        const auto typeId = getType(v);
1670        if (isAssociative(typeId)) {
1671            for (const auto e : make_iterator_range(out_edges(u, G))) {
1672                if (LLVM_UNLIKELY(target(e, G) == v)) {
1673                    if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
1674                        remove_edge(e, G);
1675                    }
1676                    return false;
1677                }
1678            }
1679        }
1680        boost::add_edge(u, v, index, G);
1681        return true;
1682    }
1683
1684    /** ------------------------------------------------------------------------------------------------------------- *
1685     * @brief hasValidOperandIndicies
1686     ** ------------------------------------------------------------------------------------------------------------- */
1687    bool hasValidOperandIndicies(const Vertex u, const bool report = true) {
1688        if (isLive(u)) {
1689            const auto n = in_degree(u, G);
1690            const auto typeId = getType(u);
1691            if (LLVM_UNLIKELY(n == 0)) {
1692                if (LLVM_LIKELY(isAssociative(typeId) || isNullary(typeId))) {
1693                    return true;
1694                }
1695                if (report) {
1696                    errs() << u << " cannot be nullary " << (int)typeId << "\n";
1697                }
1698                return false;
1699            } else if (isAssociative(typeId)) {
1700                Vertex V[n];
1701                unsigned i = 0;
1702                for (auto e : make_iterator_range(in_edges(u, G))) {
1703                    V[i++] = source(e, G);
1704                }
1705                std::sort(V, V + n);
1706                for (unsigned i = 1; i != n; ++i) {
1707                    if (LLVM_UNLIKELY(V[i - 1] == V[i])) {
1708                        if (report) {
1709                            errs() << u << " has duplicate operands " << V[i] << "\n";
1710                        }
1711                        return false;
1712                    }
1713                }
1714            } else if (requiredOperands(typeId) == n) {
1715                bool used[n];
1716                std::fill_n(used, n, false);
1717                for (auto e : make_iterator_range(in_edges(u, G))) {
1718                    const auto i = G[e];
1719                    if (LLVM_UNLIKELY(i >= n)) {
1720                        if (report) {
1721                            errs() << u << " has operand index " << i << " exceeds in degree " << n << "\n";
1722                        }
1723                        return false;
1724                    } else if (LLVM_UNLIKELY(used[i])) {
1725                        if (report) {
1726                            errs() << u << " has duplicate operand indicies " << i << "\n";
1727                        }
1728                        return false;
1729                    }
1730                    used[i] = true;
1731                }
1732            } else {
1733                if (report) {
1734                    errs() << u << " has " << n << " operands but requires " << requiredOperands(typeId) << "\n";
1735                }
1736                return false;
1737            }
1738        }
1739        for (auto e : make_iterator_range(in_edges(u, G))) {
1740            const auto v = source(e, G);
1741            if (!isLive(v)) {
1742                if (report) {
1743                    errs() << u << " has dead operand " << v << "\n";
1744                }
1745                return false;
1746            }
1747        }
1748        return true;
1749    }
1750
1751    static unsigned requiredOperands(const TypeId typeId) {
1752        switch (typeId) {
1753            case TypeId::Not:
1754            case TypeId::InFile:
1755            case TypeId::AtEOF:
1756            case TypeId::Count:
1757            case TypeId::If:
1758            case TypeId::While:
1759                return 1;
1760            case TypeId::Sel:
1761                llvm_unreachable("impossible");
1762            default:
1763                assert (!isAssociative(typeId) && !isNullary(typeId));
1764                return 2;
1765        }
1766    }
1767
1768    static bool isNullary(const TypeId typeId) {
1769        return isConstant(typeId) || isLiteral(typeId);
1770    }
1771
1772    /** ------------------------------------------------------------------------------------------------------------- *
1773     * @brief removeVertex
1774     ** ------------------------------------------------------------------------------------------------------------- */
1775    void removeVertex(const Vertex u) { assert (isLive(u));
1776        setDead(u);
1777        Vertex D[in_degree(u, G)];
1778        unsigned n = 0;
1779        for (const auto e : make_iterator_range(in_edges(u, G))) {
1780            const auto v = source(e, G);
1781            if (LLVM_UNLIKELY(out_degree(v, G) == 1)) {
1782                D[n++] = v;
1783            }
1784        }
1785        while (LLVM_UNLIKELY(n != 0)) {
1786            removeVertex(D[--n]);
1787        }
1788        clear_vertex(u, G);
1789        reprocessGraph = true;
1790    }
1791
1792    /** ------------------------------------------------------------------------------------------------------------- *
1793     * @brief consolidate
1794     ** ------------------------------------------------------------------------------------------------------------- */
1795    Vertex consolidate(const Vertex u) {
1796        assert (isLive(u));
1797        assert (hasValidOperandIndicies(u));
1798        const auto f = V.insert(u);
1799        if (LLVM_UNLIKELY(f.second)) {           
1800            return u;
1801        }
1802        const auto v = *f.first;
1803        assert (u != v);
1804        assert (isLive(v));
1805        const PabloAST * expr = getValue(u);
1806        if (expr) {
1807            assert (!isRegenerable(getType(u)));
1808            auto f = M.find(expr);
1809            assert (f != M.end() && f->second == u);
1810            f->second = v;
1811            setValue(v, nullptr);
1812            setModified(v);
1813        }
1814        for (const auto e : make_iterator_range(out_edges(u, G))) {
1815            addEdge(v, target(e, G), G[e]);
1816        }
1817        removeVertex(u);
1818        return v;
1819    }
1820
1821    /** ------------------------------------------------------------------------------------------------------------- *
1822     * @brief findVertex
1823     ** ------------------------------------------------------------------------------------------------------------- */
1824    Vertex findVertex(const PabloAST * const expr) const {
1825        assert (expr);
1826        const auto f = M.find(expr);
1827        assert (f != M.end());
1828        return f->second;
1829    }
1830
1831    /** ------------------------------------------------------------------------------------------------------------- *
1832     * @brief addDistributionVertex
1833     ** ------------------------------------------------------------------------------------------------------------- */
1834    DistributionVertex addDistributionVertex(const Vertex u) {
1835        assert (isLive(u));
1836        const auto f = Md.find(u);
1837        if (f == Md.end()) {
1838            #ifndef NDEBUG
1839            for (auto v : make_iterator_range(vertices(Gd))) {
1840                assert ("duplicate vertex found that was not in Md!" && Gd[v] != u);
1841            }
1842            #endif
1843            const auto du = add_vertex(u, Gd);
1844            Md.emplace(u, du);
1845            return du;
1846        }
1847        return f->second;
1848    }
1849
1850    /** ------------------------------------------------------------------------------------------------------------- *
1851     * @brief intersects
1852     ** ------------------------------------------------------------------------------------------------------------- */
1853    template <class Type>
1854    inline bool intersects(Type & A, Type & B) {
1855        auto first1 = A.begin(), last1 = A.end();
1856        assert (std::is_sorted(first1, last1));
1857        auto first2 = B.begin(), last2 = B.end();
1858        assert (std::is_sorted(first2, last2));
1859        while (first1 != last1 && first2 != last2) {
1860            if (*first1 < *first2) {
1861                ++first1;
1862            } else if (*first2 < *first1) {
1863                ++first2;
1864            } else {
1865                return true;
1866            }
1867        }
1868        return false;
1869    }
1870
1871    static TypeId getType(const Vertex u, const Graph & G) {
1872        assert (u < num_vertices(G));
1873        return std::get<1>(G[u]);
1874    }
1875
1876    TypeId getType(const Vertex u) const {
1877        return getType(u, G);
1878    }
1879
1880    void setType(const Vertex u, const TypeId typeId) {
1881        assert (u < num_vertices(G));
1882        std::get<1>(G[u]) = typeId;
1883    }
1884
1885    static PabloAST * getValue(const Vertex u, const Graph & G) {
1886        assert (u < num_vertices(G));
1887        return std::get<0>(G[u]);
1888    }
1889
1890    PabloAST * getValue(const Vertex u) const {
1891        return getValue(u, G);
1892    }
1893
1894    void setValue(const Vertex u, PabloAST * const value) {
1895        assert (u < num_vertices(G));
1896        std::get<0>(G[u]) = value;
1897    }
1898
1899    bool isLive(const Vertex u) const {
1900        return getState(u) != State::Dead;
1901    }
1902
1903    bool isDead(const Vertex u) const {
1904        return getState(u) == State::Dead;
1905    }
1906
1907    void setDead(const Vertex u) {
1908        setState(u, State::Dead);
1909    }
1910
1911    void setUnmodified(const Vertex u) {
1912        setState(u, State::Live);
1913    }
1914
1915    bool isModified(const Vertex u) const {
1916        return getState(u) == State::Modified;
1917    }
1918
1919    void setModified(const Vertex u) {
1920        setState(u, State::Modified);
1921    }
1922
1923    State getState(const Vertex u) const {
1924        assert (u < num_vertices(G));
1925        return std::get<2>(G[u]);
1926    }
1927
1928    void setState(const Vertex u, const State value) {
1929        assert (u < num_vertices(G));
1930        std::get<2>(G[u]) = value;
1931    }
1932
1933    UsageTime getLastUsageTime(const Vertex u) const {
1934        assert (u < num_vertices(G));
1935        return std::get<3>(G[u]);
1936    }
1937
1938    void setLastUsageTime(const Vertex u, const UsageTime time) {
1939        assert (u < num_vertices(G));
1940
1941//        errs() << "   " << u << " ";
1942//        PabloPrinter::print(getValue(u), errs());
1943//        errs() << " @ " << time << "\n";
1944
1945
1946        std::get<3>(G[u]) = time;
1947    }
1948
1949    static bool isIdentityRelation(const TypeId a, const TypeId b) {
1950        assert (isConstant(a) && isDistributive(b));
1951        return !((a == TypeId::Zeroes) ^ (b == TypeId::Or));
1952    }
1953
1954    static bool isAssociative(const TypeId typeId) {
1955        return (isDistributive(typeId) || typeId == TypeId::Xor);
1956    }
1957
1958    static bool isRegenerable(const TypeId typeId) {
1959        return (isConstant(typeId) || isAssociative(typeId) || typeId == TypeId::Not);
1960    }
1961
1962    static bool isAssociative(const PabloAST * const expr) {
1963        return isAssociative(expr->getClassTypeId());
1964    }
1965
1966    static bool isConstant(const TypeId typeId) {
1967        return typeId == TypeId::Zeroes || typeId == TypeId::Ones;
1968    }
1969
1970    static bool isLiteral(const TypeId typeId) {
1971        return typeId == TypeId::Integer || typeId == TypeId::Var;
1972    }
1973
1974    static bool isDistributive(const TypeId typeId) {
1975        return (typeId == TypeId::And || typeId == TypeId::Or);
1976    }
1977
1978    static bool isImmutable(const TypeId typeId) {
1979        switch (typeId) {
1980            case TypeId::Extract: case TypeId::Assign: case TypeId::If: case TypeId::While:
1981                return true;
1982            default:
1983                return isLiteral(typeId);
1984        }
1985    }
1986
1987    static bool isStreamOperation(const TypeId typeId) {
1988        switch (typeId) {
1989            case TypeId::Advance:
1990            case TypeId::ScanThru:
1991            case TypeId::AdvanceThenScanThru:
1992//            case TypeId::ScanTo:
1993//            case TypeId::AdvanceThenScanTo:
1994            case TypeId::Lookahead:
1995            case TypeId::MatchStar:
1996            case TypeId::InFile:
1997            case TypeId::AtEOF:
1998                return true;
1999            default:
2000                return false;
2001        }
2002    }
2003
2004    static TypeId oppositeTypeId(const TypeId typeId) {
2005        assert (isDistributive(typeId));
2006        return (typeId == TypeId::And) ? TypeId::Or : TypeId::And;
2007    }
2008
2009    Vertex first_source(const std::pair<InEdgeIterator, InEdgeIterator> & e) const {
2010        return source(*std::get<0>(e), G);
2011    }
2012
2013private:
2014
2015    struct IdentityHash {
2016        size_t operator()(const Vertex u) const {
2017            using value_of = std::underlying_type<TypeId>::type;
2018//            InEdgeIterator begin, end;
2019//            std::tie(begin, end) = in_edges(u, G);
2020//            assert (std::is_sorted(begin, end));
2021            const auto n = in_degree(u, G);
2022            Vertex operands[n];
2023            unsigned i = 0;
2024            for (auto e : make_iterator_range(in_edges(u, G))) {
2025                operands[i++] = source(e, G);
2026            }
2027            std::sort(operands, operands + n);
2028            size_t h = 0;
2029            boost::hash_combine(h, static_cast<value_of>(PassContainer::getType(u, G)));
2030            for (unsigned j = 0; j < n; ++j) {
2031                boost::hash_combine(h, operands[j]);
2032            }
2033//            for (auto e : make_iterator_range(in_edges(u, G))) {
2034//                boost::hash_combine(h, source(e, G));
2035//            }
2036            return h;
2037        }
2038        IdentityHash (const Graph & g) : G(g) { }
2039    private:
2040        const Graph & G;
2041    };
2042
2043    struct IdentityComparator {
2044        bool operator()(const Vertex u, const Vertex v) const {
2045            const auto typeId = getType(u, G);
2046            if (LLVM_LIKELY(typeId == getType(v, G))) {
2047                const unsigned n = in_degree(u, G);
2048                if (LLVM_UNLIKELY(n == 0)) {
2049                    assert (isNullary(typeId) && in_degree(v, G) == 0);
2050                    if (LLVM_UNLIKELY(isLiteral(typeId))) {
2051                        assert (getValue(u, G) && getValue(v, G));
2052                        return getValue(u, G) == getValue(v, G);
2053                    }
2054                    return true;
2055                }
2056                if (in_degree(v, G) == n) {
2057                    Vertex adjA[n];
2058                    Vertex adjB[n];
2059                    auto ei = std::get<0>(in_edges(u, G));
2060                    auto ej = std::get<0>(in_edges(v, G));
2061                    // if this is an associative op, order doesn't matter
2062                    if (isAssociative(typeId)) {
2063                        for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
2064                            adjA[i] = source(*ei, G);
2065                            adjB[i] = source(*ej, G);
2066                        }
2067                        assert(std::is_sorted(adjA, adjA + n));
2068                        assert(std::is_sorted(adjB, adjB + n));
2069                    } else { // otherwise consider the order indicated by the edges
2070                        for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
2071                            adjA[G[*ei]] = source(*ei, G);
2072                            adjB[G[*ej]] = source(*ej, G);
2073                        }
2074                    }
2075                    for (unsigned i = 0; i < n; ++i) {
2076                        if (adjA[i] != adjB[i]) {
2077                            return false;
2078                        }
2079                    }
2080                    return true;
2081                }
2082            }
2083            return false;
2084        }
2085        IdentityComparator (const Graph & g) : G(g) { }
2086    private:
2087        const Graph & G;
2088    };
2089
2090    using IdentitySet = std::unordered_set<Vertex, IdentityHash, IdentityComparator>;
2091
2092private:
2093
2094    bool reprocessGraph;
2095
2096    Graph G;
2097    flat_map<const pablo::PabloAST *, Vertex> M;
2098
2099    IdentitySet V;
2100
2101    DistributionGraph Gd;
2102    flat_map<Vertex, DistributionVertex> Md;
2103
2104    Sequence ordering;
2105    Sequence distributable;
2106};
2107
2108/** ------------------------------------------------------------------------------------------------------------- *
2109 * @brief optimize
2110 ** ------------------------------------------------------------------------------------------------------------- */
2111bool DistributivePass::optimize(PabloKernel * const kernel) {
2112    PassContainer C;
2113    C.run(kernel);
2114    #ifndef NDEBUG
2115    PabloVerifier::verify(kernel, "post-distributive-pass");
2116    #endif
2117
2118//    errs() << "-----------------------------------------------\n"
2119//              "BEFORE SIMPLIFICATION:\n"
2120//              "-----------------------------------------------\n";
2121//    PabloPrinter::print(kernel, errs());
2122
2123    Simplifier::optimize(kernel);
2124
2125//    errs() << "-----------------------------------------------\n"
2126//              "AFTER SIMPLIFICATION:\n"
2127//              "-----------------------------------------------\n";
2128//    PabloPrinter::print(kernel, errs());
2129
2130    return true;
2131}
2132
2133}
Note: See TracBrowser for help on using the repository browser.