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

Last change on this file since 5571 was 5571, checked in by nmedfort, 23 months ago

DistributionPass? bug fix and code clean up

File size: 60.5 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
23#include <boost/container/flat_set.hpp>
24#include <boost/container/flat_map.hpp>
25#include <boost/range/adaptor/reversed.hpp>
26#include <boost/graph/adjacency_list.hpp>
27#include <boost/graph/topological_sort.hpp>
28#include <boost/function_output_iterator.hpp>
29#include <boost/functional/hash.hpp>
30
31#include <set>
32#include <unordered_set>
33
34using namespace boost;
35using namespace boost::container;
36using namespace llvm;
37
38namespace pablo {
39
40using TypeId = pablo::PabloAST::ClassTypeId;
41
42enum class State {
43    Dead
44    , Live
45    , Modified
46};
47
48using UsageTime = size_t;
49
50using VertexData = std::tuple<pablo::PabloAST *, TypeId, State, UsageTime>;
51
52using OperandIndex = unsigned;
53
54using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, OperandIndex>;
55using Vertex = Graph::vertex_descriptor;
56using in_edge_iterator = graph_traits<Graph>::in_edge_iterator;
57using out_edge_iterator = graph_traits<Graph>::out_edge_iterator;
58
59using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
60using DistributionVertex = DistributionGraph::vertex_descriptor;
61
62using Sequence = std::vector<Vertex>;
63using Biclique = std::pair<Sequence, Sequence>;
64using BicliqueSet = std::vector<Biclique>;
65using DistributionSet = std::tuple<Sequence, Sequence, Sequence>;
66using DistributionSets = std::vector<DistributionSet>;
67
68using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
69
70struct PassContainer {
71
72    /** ------------------------------------------------------------------------------------------------------------- *
73     * @brief run
74     *
75     * Based on the knowledge that:
76     *
77     *  (ASSOCIATIVITY)    A ∧ (B ∧ C) ⇔ (A ∧ B) ∧ C ⇔ A ∧ B ∧ C   and   A √ (B √ C) ⇔ (A √ B) √ C ⇔ A √ B √ C
78     *
79     *  (IDENTITY)         A √ 0 ⇔ A   and   A ∧ 1 = A
80     *
81     *  (ANNULMENT)        A ∧ 0 ⇔ 0   and   A √ 1 = 1
82     *
83     *  (IDEMPOTENT)       A √ (A √ B) ⇔ A √ B   and   A ∧ (A ∧ B) ⇔ A ∧ B
84     *
85     *  (ABSORBTION)       A √ (A ∧ B) ⇔ A ∧ (A √ B) ⇔ A
86     *
87     *  (COMPLEMENT)       A √ ¬A ⇔ 1   and   A ∧ ¬A = 0
88     *
89     *  (DISTRIBUTIVITY)   (A ∧ B) √ (A ∧ C) ⇔ A ∧ (B √ C)   and   (A √ B) ∧ (A √ C) ⇔ A √ (B ∧ C)
90     *
91     *  (DE MORGAN'S)      ¬(A ∧ B) ⇔ ¬A √ ¬B   and   Â¬(A √ B) ⇔ ¬A ∧ ¬B
92     *
93     * Try to simplify the equations and eliminate some of the unnecessary statements
94     ** ------------------------------------------------------------------------------------------------------------- */
95    bool run(PabloKernel * const kernel) {
96        readAST(kernel->getEntryBlock());
97        if (LLVM_LIKELY(simplifyGraph())) {
98            rewriteAST(kernel->getEntryBlock());
99            return true;
100        }
101        return false;
102    }
103
104protected:
105
106    /** ------------------------------------------------------------------------------------------------------------- *
107     * @brief readAST
108     ** ------------------------------------------------------------------------------------------------------------- */
109    void readAST(PabloBlock * const block) {
110        for (Statement * stmt : *block) {
111            addStatement(stmt);
112            if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
113                readAST(cast<Branch>(stmt)->getBody());
114            }
115        }
116    }
117
118    /** ------------------------------------------------------------------------------------------------------------- *
119     * @brief rewriteAST
120     *
121     * The goal here is to rewrite the AST with the minimal amount of perturbation to the sequence of instructions
122     * themselves. The exception is that associative instructions are regenerated w.r.t. their sequence in the AST
123     ** ------------------------------------------------------------------------------------------------------------- */
124    size_t rewriteAST(PabloBlock * entry, size_t count = 0) {
125
126        for (Statement * stmt : *entry) {
127
128            const Vertex u = findVertex(stmt);
129            const auto typeId = getType(u);
130
131            // There are two main reasons to ignore a statement: (1) it's dead or regenerable and thus not of interest,
132            // and (2), the value in G strictly dominates the statement. Typically, if two expressions are equivalent,
133            // they're in disjoint nested scopes. When neither dominates the other, this algorithm updates G as it
134            // processes the statements. However, if one dominates the other, G must refer to the dominating statement
135            // to avoid producing an illegal AST.
136
137            if (LLVM_LIKELY(isDead(u) || isRegenerable(typeId)) || LLVM_UNLIKELY(strictly_dominates(getValue(u), stmt))) {
138                continue;
139            }
140
141            assert (isLive(u));
142            assert (stmt->getClassTypeId() == typeId);
143            assert (hasValidOperandIndicies(u));
144            assert (in_degree(u, G) == stmt->getNumOperands());
145
146            in_edge_iterator ei_begin, ei_end;
147            std::tie(ei_begin, ei_end) = in_edges(u, G);
148            auto ei = ei_begin;
149
150            // For each associative operand, find the vertex that describes the operand in G
151            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
152
153                // Does the vertex have a value and, if so, does value dominate this statement?
154                // If not, we need to regenerate it.
155                for (;;) {
156                    if (ei == ei_end) {
157                        ei = ei_begin;
158                    }
159                    if (G[*ei] == i) {
160                        break;
161                    }
162                    ++ei;
163                }
164
165                entry->setInsertPoint(stmt->getPrevNode());
166
167                stmt->setOperand(i, regenerateIfNecessary(stmt, entry, source(*ei, G), count));
168            }
169
170            if (LLVM_UNLIKELY(typeId == TypeId::Assign)) {
171                setLastUsageTime(findVertex(stmt->getOperand(0)), ++count);
172            }
173            setLastUsageTime(u, ++count);
174            setValue(u, stmt);
175
176            if (isa<Branch>(stmt)) {
177                count = rewriteAST(cast<Branch>(stmt)->getBody(), count);
178            }
179        }
180
181        return count;
182    }
183
184    /** ------------------------------------------------------------------------------------------------------------- *
185     * @brief regenerateIfNecessary
186     *
187     * Does vertex (u) have a value and, if so, does value dominate the statement? If not, regenerate it.
188     ** ------------------------------------------------------------------------------------------------------------- */
189    PabloAST * regenerateIfNecessary(Statement * const stmt, PabloBlock * const entry, const Vertex u, size_t & count) {
190
191        assert (isLive(u));
192
193        const TypeId typeId = getType(u);
194
195        PabloAST * value = isModified(u) ? nullptr : getValue(u);
196        if (LLVM_LIKELY(!dominates(value, stmt))) {
197
198            assert (isRegenerable(typeId));
199
200            for (auto e : make_iterator_range(in_edges(u, G))) {
201                const auto v = source(e, G);
202                regenerateIfNecessary(stmt, entry, v, count);
203                assert (getValue(v));
204                assert (dominates(getValue(v), stmt));
205            }
206
207            if (LLVM_LIKELY(isAssociative(typeId))) {
208
209                const auto n = in_degree(u, G);
210
211                assert (n >= 2);
212
213                // Suppose we try to minimize the pairwise difference in last usage time,
214                // taking into account that we can use negations of variables when they've
215                // been used more recently. Take note to update the correct vertex if an
216                // ANDC can be used instead.
217
218                Vertex input[n];
219                unsigned i = 0;
220                for (auto e : make_iterator_range(in_edges(u, G))) {
221                    input[i++] = source(e, G);
222                }
223
224                std::sort(input, input + n, [this](const Vertex u, const Vertex v) {
225                    return getLastUsageTime(u) < getLastUsageTime(v);
226                });
227
228                PabloBuilder builder(entry);
229                value = getValue(input[0]);
230                for (unsigned i = 1; i < n; ++i) {
231                    PabloAST * const op = getValue(input[i]);
232                    switch (typeId) {
233                        case TypeId::And:
234                            value = builder.createAnd(value, op);
235                            break;
236                        case TypeId::Or:
237                            value = builder.createOr(value, op);
238                            break;
239                        case TypeId::Xor:
240                            value = builder.createXor(value, op);
241                            break;
242                        default:
243                            llvm_unreachable("impossible!");
244                    }
245                }
246
247            } else if (typeId == TypeId::Not) {
248                assert (in_degree(u, G) == 1);
249                value = entry->createNot(getValue(first_source(in_edges(u, G))));
250            } else {
251                assert (isConstant(typeId));
252                assert (in_degree(u, G) == 0);
253                if (typeId == TypeId::Zeroes) {
254                    value = entry->createZeroes();
255                } else {
256                    value = entry->createOnes();
257                }
258            }
259
260            setValue(u, value);
261            setUnmodified(u);
262        }
263
264        // negations inherit the last usage time from their operand
265        if (LLVM_UNLIKELY(typeId == TypeId::Not)) {
266            setLastUsageTime(u, getLastUsageTime(first_source(in_edges(u, G))));
267        } else {
268            setLastUsageTime(u, ++count);
269        }
270        return value;
271    }
272
273protected:
274
275    /** ------------------------------------------------------------------------------------------------------------- *
276     * @brief simplifyGraph
277     ** ------------------------------------------------------------------------------------------------------------- */
278    bool simplifyGraph() {
279        bool modified = false;
280repeat: getReverseTopologicalOrdering();
281        compactGraph();
282        if (applyDistributivityLaw()) {
283            modified = true;
284            goto repeat;
285        }
286        factorizeGraph();
287        return modified;
288    }
289
290    /** ------------------------------------------------------------------------------------------------------------- *
291     * @brief getReverseTopologicalOrdering
292     ** ------------------------------------------------------------------------------------------------------------- */
293    void getReverseTopologicalOrdering() {
294
295        struct PrePassInserter {
296            PrePassInserter & operator=(const Vertex u) {
297                if (LLVM_LIKELY(self.isLive(u))) {
298                    assert(self.hasValidOperandIndicies(u));
299                    if (LLVM_LIKELY(isImmutable(self.getType(u)) || out_degree(u, self.G) != 0)) {
300                        self.ordering.push_back(u);
301                    } else {
302                        self.removeVertex(u);
303                    }
304                }
305                return *this;
306            }
307
308            PrePassInserter(PassContainer & pc) : self(pc) { }
309            PrePassInserter & operator*() { return *this; }
310            PrePassInserter & operator++() { return *this; }
311            PrePassInserter & operator++(int) { return *this; }
312
313        public:
314            PassContainer & self;
315        };
316
317
318        ordering.clear();
319        ordering.reserve(num_vertices(G));
320        topological_sort(G, PrePassInserter(*this));
321        assert (!ordering.empty());
322    }
323
324    /** ------------------------------------------------------------------------------------------------------------- *
325     * @brief compactGraph
326     ** ------------------------------------------------------------------------------------------------------------- */
327    void compactGraph() {
328
329        auto IdentityHash = [this](const Vertex u) {
330            using value_of = std::underlying_type<TypeId>::type;
331            const auto n = in_degree(u, G);
332            Vertex operands[n];
333            unsigned i = 0;
334            for (auto e : make_iterator_range(in_edges(u, G))) {
335                operands[i++] = source(e, G);
336            }
337            std::sort(operands, operands + n);
338            size_t h = 0;
339            boost::hash_combine(h, static_cast<value_of>(getType(u)));
340            for (unsigned j = 0; j < n; ++j) {
341                boost::hash_combine(h, operands[j]);
342            }
343            return h;
344        };
345
346        auto IdentityComparator = [this](const Vertex u, const Vertex v) {
347            const auto typeId = getType(u);
348            if (LLVM_LIKELY(typeId == getType(v))) {
349                const unsigned n = in_degree(u, G);
350                if (LLVM_UNLIKELY(n == 0)) {
351                    assert (isConstant(typeId) && in_degree(v, G) == 0);
352                    return true;
353                }
354                if (in_degree(v, G) == n) {
355                    Vertex adjA[n];
356                    Vertex adjB[n];
357                    auto ei = std::get<0>(in_edges(u, G));
358                    auto ej = std::get<0>(in_edges(v, G));
359                    // if this is an associative op, order doesn't matter
360                    if (isAssociative(typeId)) {
361                        for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
362                            adjA[i] = source(*ei, G);
363                            adjB[i] = source(*ej, G);
364                        }
365                        std::sort(adjA, adjA + n);
366                        std::sort(adjB, adjB + n);
367                    } else { // otherwise consider the order indicated by the edges
368                        for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
369                            adjA[G[*ei]] = source(*ei, G);
370                            adjB[G[*ej]] = source(*ej, G);
371                        }
372                    }
373                    for (unsigned i = 0; i < n; ++i) {
374                        if (adjA[i] != adjB[i]) {
375                            return false;
376                        }
377                    }
378                    return true;
379                }
380            }
381            return false;
382        };
383
384        using IdentitySet = std::unordered_set<Vertex, decltype(IdentityHash), decltype(IdentityComparator)>;
385
386        IdentitySet V{0, IdentityHash, IdentityComparator};
387        V.reserve(num_vertices(G));
388
389        for (const auto u : boost::adaptors::reverse(ordering)) {
390
391            assert (isLive(u));
392
393            const auto typeId = getType(u);
394            if (LLVM_UNLIKELY(isImmutable(typeId))) {
395                continue;
396            }
397
398            assert (hasValidOperandIndicies(u));
399
400            assert (out_degree(u, G) > 0);
401
402            if (LLVM_UNLIKELY(isConstant(typeId))) {
403                if (processConstant(u, typeId)) {
404                    continue;
405                }
406            } else if (isAssociative(typeId)) {
407                if (processAssociative(u, typeId)) {
408                    continue;
409                }
410            } else if (typeId == TypeId::Not) {
411                if (processNegation(u, typeId)) {
412                    continue;
413                }
414            }
415
416            // check whether this vertex is a duplicate
417            auto f = V.insert(u);
418            if (LLVM_UNLIKELY(!f.second)) {
419                remapVertex(u, *f.first);             
420            }
421        }
422    }
423
424    /** ------------------------------------------------------------------------------------------------------------- *
425     * @brief processAssociative
426     ** ------------------------------------------------------------------------------------------------------------- */
427    bool processAssociative(const Vertex u, const TypeId typeId) {
428
429        assert (isLive(u));
430        assert (getType(u) == typeId);
431        assert (isAssociative(typeId));
432
433        if (LLVM_UNLIKELY(in_degree(u, G) == 0)) {
434            setModified(u);
435            setType(u, TypeId::Zeroes);
436            return processConstant(u, TypeId::Zeroes);
437        } else if (LLVM_UNLIKELY(in_degree(u, G) == 1)) {
438            // An associative operation with only one element is always equivalent to the element
439            const auto v = first_source(in_edges(u, G));
440            for (const auto e : make_iterator_range(out_edges(u, G))) {
441                addEdge(v, target(e, G), G[e]);
442            }
443            removeVertex(u);
444            return true;
445        } else {
446            // Take the transitive closure of these arcs to reveal the underlying equations
447            Vertex removed[out_degree(u, G)];
448            unsigned n = 0;
449            for (auto ei : make_iterator_range(out_edges(u, G))) {
450                const auto v = target(ei, G);
451                if (typeId == getType(v)) {
452                    assert(hasValidOperandIndicies(v));
453                    for (auto ej : make_iterator_range(in_edges(u, G))) {
454                        addEdge(source(ej, G), v, G[ei]);
455                    }
456                    setModified(v);
457                    removed[n++] = v;
458                }
459            }
460            for (unsigned i = 0; i < n; ++i) {
461                const auto v = removed[i];
462                assert (edge(u, v, G).second);
463                remove_edge(u, v, G);
464                assert(hasValidOperandIndicies(v));
465            }
466            if (LLVM_UNLIKELY(out_degree(u, G) == 0)) {
467                removeVertex(u);
468                return true;
469            }
470            if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
471                // Canonicalize xor operations: (A ⊕ ¬B) = (A ⊕ B ⊕ 1)
472                Vertex negation[in_degree(u, G)];
473                unsigned count = 0;
474                for (const auto e : make_iterator_range(in_edges(u, G))) {
475                    const auto v = source(e, G);
476                    if (LLVM_UNLIKELY(getType(v) == TypeId::Not)) {
477                        negation[count++] = v;
478                    }
479                }
480                if (LLVM_UNLIKELY(count != 0)) {
481                    for (unsigned i = 0; i < count; ++i) {
482                        const auto v = negation[i];
483                        assert (edge(v, u, G).second);
484                        remove_edge(v, u, G);
485                        addEdge(first_source(in_edges(v, G)), u);
486                    }
487                    if ((count & 1) != 0) {
488                        addEdge(makeVertex(TypeId::Ones), u);
489                    }
490                    setModified(u);
491                    assert(hasValidOperandIndicies(u));
492                }
493            } else { // perform De Morgan's law expansion
494                applyDeMorgans(u, typeId);
495                return applyAbsorbtionComplementLaw(u, typeId);
496            }
497        }
498        return false;
499    }
500
501    /** ------------------------------------------------------------------------------------------------------------- *
502     * @brief processNegation
503     ** ------------------------------------------------------------------------------------------------------------- */
504    bool processNegation(const Vertex u, const TypeId typeId) {
505
506        assert (isLive(u));
507        assert ("negation must have one input!" && in_degree(u, G) == 1);
508        assert (getType(u) == typeId);
509        assert (typeId == TypeId::Not);
510
511        const auto v = first_source(in_edges(u, G));
512        const auto negatedTypeId = getType(v);
513        if (LLVM_UNLIKELY(negatedTypeId == TypeId::Not)) { // ¬¬A = A
514            const auto w = first_source(in_edges(v, G));
515            for (const auto e : make_iterator_range(out_edges(u, G))) {
516                const auto v = target(e, G);
517                addEdge(w, v, G[e]);
518                setModified(v);
519            }
520            removeVertex(u);
521            return true;
522        } else if (LLVM_UNLIKELY(negatedTypeId == TypeId::Xor)) {
523            // Canonicalize xor operations: ¬(A ⊕ B) = (A ⊕ B ⊕ 1)
524            setModified(u);
525            setType(u, TypeId::Xor);
526            clear_in_edges(u, G);
527            for (const auto e : make_iterator_range(in_edges(v, G))) {
528                add_edge(source(e, G), u, 0, G);
529            }
530            addEdge(makeVertex(TypeId::Ones), u);
531            assert(hasValidOperandIndicies(u));
532        }
533        return false;
534    }
535
536    /** ------------------------------------------------------------------------------------------------------------- *
537     * @brief applyDeMorgans
538     ** ------------------------------------------------------------------------------------------------------------- */
539    void applyDeMorgans(const Vertex u, const TypeId typeId) {
540
541        assert (isLive(u));
542        assert (in_degree(u, G) > 0);
543        assert (getType(u) == typeId);
544        assert (isDistributive(typeId));
545
546        Vertex A[in_degree(u, G)];
547        unsigned n = 0;
548        for (const auto e : make_iterator_range(in_edges(u, G))) {
549            const auto v = source(e, G);
550            if (LLVM_UNLIKELY(getType(v) == TypeId::Not)) {
551                const auto w = first_source(in_edges(v, G));
552                if (LLVM_UNLIKELY(getType(w) == oppositeTypeId(typeId))) {
553                    A[n++] = v;
554                }
555            }
556        }
557
558        if (LLVM_UNLIKELY(n != 0)) {
559            for (unsigned i = 0; i < n; ++i) {
560                const auto v = A[i];
561                assert (edge(v, u, G).second);
562                assert (getType(v) == TypeId::Not);
563                remove_edge(v, u, G);
564                // NOTE: we cannot remove v even if this was its last edge since
565                // it must be in our duplicate check map
566                const auto w = first_source(in_edges(v, G));
567                assert (getType(w) == oppositeTypeId(typeId));
568                for (const auto e : make_iterator_range(in_edges(w, G))) {
569                    const auto x = makeVertex(TypeId::Not);
570                    add_edge(source(e, G), x, 0, G);
571                    addEdge(x, u);
572                }
573            }
574            setModified(u);
575            assert(hasValidOperandIndicies(u));
576        }
577
578    }
579
580    /** ------------------------------------------------------------------------------------------------------------- *
581     * @brief applyAbsorbtionComplementLaw
582     ** ------------------------------------------------------------------------------------------------------------- */
583    bool applyAbsorbtionComplementLaw(const Vertex u, const TypeId typeId) {
584
585        assert (isLive(u));
586        assert (in_degree(u, G) > 0);
587        assert (getType(u) == typeId);
588        assert (isDistributive(typeId));
589
590        Vertex A[in_degree(u, G)];
591        unsigned n = 0;
592        for (const auto ei : make_iterator_range(in_edges(u, G))) {
593            const auto v = source(ei, G);
594            assert (isLive(v));
595            const auto innerTypeId = getType(v);
596            if (innerTypeId == TypeId::Not) {
597                const auto w = first_source(in_edges(v, G));
598                assert (isLive(w));
599                for (const auto ej : make_iterator_range(in_edges(u, G))) {
600                    if (LLVM_UNLIKELY(source(ej, G) == w)) {
601                        const auto complementTypeId = (typeId == TypeId::And) ? TypeId::Zeroes : TypeId::Ones;
602                        setModified(u);
603                        setType(u, complementTypeId);
604                        clear_in_edges(u, G);
605                        return processConstant(u, complementTypeId);
606                    }
607                }
608            } else if (innerTypeId == oppositeTypeId(typeId) && LLVM_UNLIKELY(absorbs(u, v))) {
609                A[n++] = v;
610            }
611        }
612
613        if (n) {
614            setModified(u);
615            for (;;) {
616                const auto v = A[--n];
617                assert (edge(v, u, G).second);
618                remove_edge(v, u, G);
619                if (LLVM_UNLIKELY(out_degree(v, G) == 0)) {
620                    removeVertex(v);
621                }
622                if (LLVM_LIKELY(n == 0)) {
623                    break;
624                }
625            }
626        }
627
628        return false;
629    }
630
631    /** ------------------------------------------------------------------------------------------------------------- *
632     * @brief absorbs
633     ** ------------------------------------------------------------------------------------------------------------- */
634    bool absorbs(const Vertex u, const Vertex v) {
635        assert (getType(u) == oppositeTypeId(getType(v)));
636        for (const auto ei : make_iterator_range(in_edges(u, G))) {
637            for (const auto ej : make_iterator_range(in_edges(v, G))) {
638                if (LLVM_UNLIKELY(source(ei, G) == source(ej, G))) {
639                    return true;
640                }
641            }
642        }
643        return false;
644    }
645
646    /** ------------------------------------------------------------------------------------------------------------- *
647     * @brief processConstant
648     ** ------------------------------------------------------------------------------------------------------------- */
649    bool processConstant(const Vertex u, const TypeId typeId) {
650
651        const auto l = out_degree(u, G);
652        Vertex modification[l];
653        unsigned n = 0;
654        unsigned m = 0;
655
656        assert (isConstant(typeId));
657        assert (getType(u) == typeId);
658
659        for (auto e : make_iterator_range(out_edges(u, G))) {
660            const auto v = target(e, G);
661            const auto targetTypeId = getType(v);
662            if (LLVM_UNLIKELY(isDistributive(targetTypeId))) {
663                // typeId           targetTypeId     Optimization
664                // ------------     ------------     ------------
665                // Zeroes           Or               identity
666                // Zeroes           And              annulment (0)
667                // Ones             Or               annulment (1)
668                // Ones             And              identity
669                if (isIdentityRelation(typeId, targetTypeId)) {
670                    modification[l - ++n] = v; // fill in from the end
671                } else { // annulment
672                    setType(v, typeId);
673                    modification[m++] = v;
674                }
675            } else if (LLVM_UNLIKELY(targetTypeId == TypeId::Not)) {
676                const auto negatedTypeId = (typeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes;
677                setType(u, negatedTypeId);
678                modification[m++] = v;
679            } else if (LLVM_UNLIKELY(isStreamOperation(typeId))) {
680                if (LLVM_LIKELY(typeId == TypeId::Zeroes)) {
681                    setType(v, TypeId::Zeroes);
682                    modification[m++] = v;
683                } else { // if (typeId == TypeId::Ones) {
684                    switch (targetTypeId) {
685                        case TypeId::ScanThru:
686                            if (LLVM_UNLIKELY(G[e] == 1)) {
687                                setType(v, TypeId::Zeroes);
688                                modification[m++] = v;
689                            }
690                            break;
691                        case TypeId::MatchStar:
692                            if (LLVM_UNLIKELY(G[e] == 0)) {
693                                setType(v, TypeId::Ones);
694                                modification[m++] = v;
695                            }
696                            break;
697                        default: break;
698                    }
699                }
700            }
701        }
702
703        if (LLVM_LIKELY(n == 0 && m == 0)) {
704            return false;
705        }
706
707        // handle any identity graph modifications
708        while (LLVM_UNLIKELY(n != 0)) {
709            const auto v = modification[l - n--];
710            setModified(v);
711            remove_edge(u, v, G);
712        }
713
714        // ... then handle the rest
715        while (LLVM_LIKELY(m != 0)) {
716            const auto v = modification[--m];
717            setModified(v);
718            clear_in_edges(v, G);
719            // We could recursively call "processConstant" but this could cause a stack overflow
720            // in a pathological case. Instead rely on the fact v will be processed eventually.
721        }
722
723        if (LLVM_UNLIKELY(out_degree(u, G) == 0)) {
724            removeVertex(u);
725            return true;
726        }
727
728        return false;
729    }
730
731
732    /** ------------------------------------------------------------------------------------------------------------- *
733     * @brief applyDistributivityLaw
734     *
735     * sources        (s)               inner       (√)   (√)
736     *               /   \                            \   /
737     * inner       (√)   (√)            x              (∧)
738     *               \   /                              |
739     * outer          (∧)               sources         |  (s)
740     *                                                  | /
741     *                                  y              (√)
742     *                                                  |
743     *                                  outer          (∧)
744     *
745     ** ------------------------------------------------------------------------------------------------------------- */
746    bool applyDistributivityLaw() {
747
748        makeDistributionSubgraph();
749
750        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
751        if (LLVM_UNLIKELY(distributable.empty())) {
752            return false;
753        }
754
755        bool modified = false;
756
757        const auto lowerSet = obtainDistributableClauses(distributable);
758        for (const auto & lower : lowerSet) {
759            const auto & outer = std::get<0>(lower);
760            const auto upperSet = obtainDistributableSources(std::get<1>(lower));
761            for (const auto & upper : upperSet) {
762                const auto & inner = std::get<0>(upper);
763                const auto & sources = std::get<1>(upper);
764
765                const auto outerTypeId = getType(Gd[outer[0]]);
766                const auto innerTypeId = oppositeTypeId(outerTypeId);
767
768                // Update G to match the desired change
769                const auto x = makeVertex(outerTypeId);
770                const auto y = makeVertex(innerTypeId);
771
772                for (const Vertex i : sources) {
773                    const auto u = Gd[i];
774                    for (const Vertex j : inner) {
775                        const auto v = Gd[j];
776                        assert (edge(u, v, G).second);
777                        assert (getType(v) == innerTypeId);
778                        remove_edge(u, v, G);
779                    }
780                    addEdge(u, y);
781                }
782
783                for (const auto i : inner) {
784                    const auto u = Gd[i];
785                    assert (getType(u) == innerTypeId);
786                    for (const Vertex j : outer) {
787                        const auto v = Gd[j];
788                        assert (edge(u, v, G).second);
789                        assert (getType(v) == outerTypeId);
790                        remove_edge(u, v, G);
791                    }
792                    addEdge(u, x);
793                }
794
795                addEdge(x, y);
796
797                for (const Vertex i : outer) {
798                    const auto u = Gd[i];
799                    assert (getType(u) == outerTypeId);
800                    setModified(u);
801                    addEdge(y, u);
802                }
803
804                modified = true;
805            }
806        }
807
808        Gd.clear();
809        Md.clear();
810
811        return modified;
812    }
813
814    /** ------------------------------------------------------------------------------------------------------------- *
815     * @brief makeDistributionSubgraph
816     ** ------------------------------------------------------------------------------------------------------------- */
817    void makeDistributionSubgraph() {
818        // TODO: instead of creating a subgraph, mark the vertices in G as being part of the subgraph? The last usage
819        // time could be a "round counter"
820        distributable.clear();
821        for (const auto u : boost::adaptors::reverse(ordering)) {
822            if (LLVM_LIKELY(isLive(u) && out_degree(u, G) != 0)) {
823                const auto outerTypeId = getType(u);
824                if (isDistributive(outerTypeId)) {
825                    const auto n = in_degree(u, G);
826                    assert (n > 1);
827                    const auto innerTypeId = oppositeTypeId(getType(u));
828                    Vertex D[n];
829                    unsigned count = 0;
830                    for (const auto ei : make_iterator_range(in_edges(u, G))) {
831                        const auto v = source(ei, G);
832                        assert (isLive(v));
833                        if (getType(v) == innerTypeId) {
834                            bool safe = true;
835                            for (const auto ej : make_iterator_range(out_edges(v, G))) {
836                                const auto w = target(ej, G);
837                                assert (isLive(w));
838                                if (getType(w) != outerTypeId) {
839                                    safe = false;
840                                    break;
841                                }
842                            }
843                            if (safe) {
844                                D[count++] = v;
845                            }
846                        }
847                    }
848                    if (count > 1) {
849                        const auto du = addDistributionVertex(u);
850                        for (unsigned i = 0; i < count; ++i) {
851                            const auto v = D[i];
852                            assert (isLive(v));
853                            if (getType(v) == innerTypeId) {
854                                const auto dv = addDistributionVertex(v);
855                                add_edge(dv, du, Gd);
856                                for (const auto ej : make_iterator_range(in_edges(v, G))) {
857                                    const auto w = source(ej, G);
858                                    assert (isLive(w));
859                                    add_edge(addDistributionVertex(w), dv, Gd);
860                                }
861                            }
862                        }
863                        distributable.push_back(du);
864                    }
865                }
866            }
867        }
868        std::sort(distributable.begin(), distributable.end());
869    }
870
871    /** ------------------------------------------------------------------------------------------------------------- *
872     * @brief obtainDistributableClauses
873     ** ------------------------------------------------------------------------------------------------------------- */
874    BicliqueSet obtainDistributableClauses(const Sequence & S) {
875        auto cliques = enumerateBicliques(S, Gd, 1, 2);
876        // remove any cliques from our set that do not contain all of their users
877        for (auto ci = cliques.begin(); ci != cliques.end(); ) {
878            const auto & A = std::get<0>(*ci);
879            auto & B = std::get<1>(*ci);
880            for (auto bi = B.begin(); bi != B.end(); ) {
881                if (out_degree(Gd[*bi], G) != A.size()) {
882                    bi = B.erase(bi);
883                } else {
884                    ++bi;
885                }
886            }
887            if (B.size() < 2) {
888                ci = cliques.erase(ci);
889            } else {
890                ++ci;
891            }
892        }
893        return makeIndependent(std::move(cliques), 0);
894    }
895
896    /** ------------------------------------------------------------------------------------------------------------- *
897     * @brief obtainDistributableSources
898     ** ------------------------------------------------------------------------------------------------------------- */
899    BicliqueSet obtainDistributableSources(const Sequence & S) {
900        return makeIndependent(enumerateBicliques(S, Gd, 2, 1), 0);
901    }
902
903    /** ------------------------------------------------------------------------------------------------------------- *
904     * @brief factorizeGraph
905     *
906     * Factorize the associative operations in the final graph
907     ** ------------------------------------------------------------------------------------------------------------- */
908    void factorizeGraph() {
909
910        Sequence groups[3];
911        for (const auto u : make_iterator_range(vertices(G))) {
912            if (isLive(u)) {
913                switch (getType(u)) {
914                    case TypeId::And:
915                        groups[0].push_back(u); break;
916                    case TypeId::Or:
917                        groups[1].push_back(u); break;
918                    case TypeId::Xor:
919                        groups[2].push_back(u); break;
920                    default: break;
921                }
922            }
923        }
924
925        const TypeId op[3] = { TypeId::And, TypeId::Or, TypeId::Xor };
926
927        for (unsigned i = 0; i < 3; ++i) {
928
929            // Although we risk losing better combinations by greedily taking the larger factorings,
930            // choosing only those of minSize or greater first can significantly reduce the running
931            // time of this optimization.
932
933            for (unsigned minSize = 64; minSize >= 2; minSize /= 2)  {
934
935                for (;;) {
936
937                    auto factors = makeIndependent(enumerateBicliques(groups[i], G, 2, minSize), 1);
938                    if (factors.empty()) {
939                        break;
940                    }
941
942                    for (auto & factor : factors) {
943                        const auto & sources = std::get<1>(factor);
944                        assert (sources.size() > 1);
945                        auto & targets = std::get<0>(factor);
946                        assert (targets.size() > 1);
947
948                        // Check whether one of the targets is the factorization
949                        Vertex x = 0;
950                        bool create = true;
951                        for (auto j = targets.begin(); j != targets.end(); ) {
952                            assert (hasValidOperandIndicies(*j));
953                            if (in_degree(*j, G) == sources.size()) {
954                                if (LLVM_LIKELY(create)) {
955                                    x = *j;
956                                    create = false;
957                                } else {
958                                    for (auto e : make_iterator_range(out_edges(*j, G))) {
959                                        addEdge(x, target(e, G), G[e]);
960                                    }
961                                    removeVertex(*j);
962                                }
963                                j = targets.erase(j);
964                            } else {
965                                ++j;
966                            }
967                        }
968                        if (create) {
969                            x = makeVertex(op[i]);
970                            groups[i].push_back(x);
971                            for (auto u : sources) {
972                                add_edge(u, x, 0, G);
973                            }
974                            assert (hasValidOperandIndicies(x));
975                        }
976
977                        // Remove the biclique between the source and target vertices
978                        for (auto u : sources) {
979                            for (auto v : targets) {
980                                assert (getType(v) == op[i]);
981                                assert (edge(u, v, G).second);
982                                boost::remove_edge(u, v, G);
983                            }
984                        }
985
986                        // ... and replace it with the factorization
987                        for (auto v : targets) {
988                            assert (getType(v) == op[i]);
989                            addEdge(x, v);
990                            setModified(v);
991                            assert(hasValidOperandIndicies(v));
992                        }
993                    }
994                }
995            }
996        }
997    }
998
999private:
1000
1001    /** ------------------------------------------------------------------------------------------------------------- *
1002     * @brief enumerateBicliques
1003     *
1004     * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
1005     * bicliques" by Alexe et. al. (2003). This implementation considers all verticies in set S to be in
1006     * bipartition A (0) and their *INCOMING* adjacencies to be in B (1).
1007     ** ------------------------------------------------------------------------------------------------------------- */
1008    template <typename Graph>
1009    BicliqueSet enumerateBicliques(const Sequence & S, const Graph & G, const unsigned minimumSizeA = 1, const unsigned minimumSizeB = 1) {
1010        using IntersectionSets = std::set<Sequence>;
1011
1012        assert (std::is_sorted(S.begin(), S.end()));
1013
1014        BicliqueSet cliques(0);
1015
1016        if (LLVM_LIKELY(S.size() >= minimumSizeA)) {
1017
1018            IntersectionSets B1;
1019            for (auto u : S) {
1020                const auto n = in_degree(u, G);
1021                if (n >= minimumSizeB) {
1022                    Sequence B;
1023                    B.reserve(n);
1024                    for (auto e : make_iterator_range(in_edges(u, G))) {
1025                        const auto v = source(e, G);
1026                        if (out_degree(v, G) >= minimumSizeA) {
1027                            B.push_back(v);
1028                        }
1029                    }
1030                    if (B.size() >= minimumSizeB) {
1031                        std::sort(B.begin(), B.end());
1032                        assert(std::unique(B.begin(), B.end()) == B.end());
1033                        B1.insert(std::move(B));
1034                    }
1035                }
1036            }
1037
1038            IntersectionSets B(B1);
1039
1040            IntersectionSets Bi;
1041
1042            Sequence T;
1043            for (auto i = B1.begin(), end = B1.end(); i != end; ++i) {
1044                assert (std::is_sorted(i->begin(), i->end()));
1045                for (auto j = i; ++j != end; ) {
1046                    assert (std::is_sorted(j->begin(), j->end()));
1047                    std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(T));
1048                    if ((T.size() >= minimumSizeB) && (B.count(T) == 0)) {
1049                        Bi.insert(T);
1050                    }
1051                    T.clear();
1052                }
1053            }
1054
1055            IntersectionSets Bj;
1056            for (;;) {
1057                if (Bi.empty()) {
1058                    break;
1059                }
1060                B.insert(Bi.begin(), Bi.end());
1061                for (auto i = B1.begin(); i != B1.end(); ++i) {
1062                    assert (std::is_sorted(i->begin(), i->end()));
1063                    for (auto j = Bi.begin(), end = Bi.end(); j != end; ++j) {
1064                        assert (std::is_sorted(j->begin(), j->end()));
1065                        std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(T));
1066                        if ((T.size() >= minimumSizeB) && (B.count(T) == 0)) {
1067                            Bj.insert(T);
1068                        }
1069                        T.clear();
1070                    }
1071                }
1072                Bi.swap(Bj);
1073                Bj.clear();
1074            }
1075
1076            cliques.reserve(B.size());
1077
1078            Sequence Aj;
1079            for (auto && Bi : B) {
1080                Sequence Ai(S);
1081                assert (Bi.size() >= minimumSizeB);
1082                bool largeEnough = true;
1083                for (const Vertex u : Bi) {
1084                    assert (std::is_sorted(Ai.begin(), Ai.end()));
1085                    assert (Ai.size() >= minimumSizeA);
1086                    T.clear();
1087                    const auto m = out_degree(u, G);
1088                    assert (m >= minimumSizeA);
1089                    T.reserve(m);
1090                    for (auto e : make_iterator_range(out_edges(u, G))) {
1091                        T.push_back(target(e, G));
1092                    }
1093                    std::sort(T.begin(), T.end());
1094                    assert(std::unique(T.begin(), T.end()) == T.end());
1095                    Aj.clear();
1096                    Aj.reserve(std::min(Ai.size(), T.size()));
1097                    std::set_intersection(Ai.begin(), Ai.end(), T.begin(), T.end(), std::back_inserter(Aj));
1098                    if (Aj.size() < minimumSizeA) {
1099                        largeEnough = false;
1100                        break;
1101                    }
1102                    Ai.swap(Aj);
1103                }
1104                if (largeEnough) {
1105                    cliques.emplace_back(std::move(Ai), std::move(Bi));
1106                }
1107            }
1108
1109        }
1110
1111        return cliques;
1112    }
1113
1114    /** ------------------------------------------------------------------------------------------------------------- *
1115     * @brief makeIndependent
1116     ** ------------------------------------------------------------------------------------------------------------- */
1117    BicliqueSet && makeIndependent(BicliqueSet && S, const unsigned independentSide) {
1118
1119        const auto l = S.size();
1120        IndependentSetGraph I(l);
1121
1122        assert (independentSide < 2);
1123
1124        // Initialize our weights
1125        for (unsigned i = 0; i != l; ++i) {
1126            I[i] = std::get<0>(S[i]).size() * std::get<1>(S[i]).size();
1127        }
1128
1129        // Determine our constraints
1130        for (unsigned i = 0; i != l; ++i) {
1131            const auto & Si = (independentSide == 0) ? std::get<0>(S[i]) : std::get<1>(S[i]);
1132            for (unsigned j = i + 1; j != l; ++j) {
1133                const auto & Sj = (independentSide == 0) ? std::get<0>(S[j]) : std::get<1>(S[j]);
1134                if (intersects(Si, Sj)) {
1135                    boost::add_edge(i, j, I);
1136                }
1137            }
1138        }
1139
1140        // Use the greedy algorithm to choose our independent set
1141        Sequence selected;
1142        for (;;) {
1143            unsigned w = 0;
1144            Vertex u = 0;
1145            for (unsigned i = 0; i != l; ++i) {
1146                if (I[i] > w) {
1147                    w = I[i];
1148                    u = i;
1149                }
1150            }
1151            if (LLVM_UNLIKELY(w == 0)) break;
1152            selected.push_back(u);
1153            I[u] = 0;
1154            for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
1155                I[v] = 0;
1156            }
1157        }
1158
1159        // Sort the selected list and then remove the unselected cliques
1160        std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
1161        auto end = S.end();
1162        for (const unsigned offset : selected) {
1163            end = S.erase(S.begin() + offset + 1, end) - 1;
1164        }
1165        S.erase(S.begin(), end);
1166
1167        return std::move(S);
1168    }
1169
1170    /** ------------------------------------------------------------------------------------------------------------- *
1171     * @brief makeVertex
1172     ** ------------------------------------------------------------------------------------------------------------- */
1173    Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) {
1174        return add_vertex(std::make_tuple(expr, typeId, expr ? State::Live : State::Modified, 0), G);
1175    }
1176
1177    /** ------------------------------------------------------------------------------------------------------------- *
1178     * @brief addExpression
1179     ** ------------------------------------------------------------------------------------------------------------- */
1180    Vertex addExpression(PabloAST * const expr) {
1181        assert (expr);
1182        const auto f = M.find(expr);
1183        if (LLVM_LIKELY(f != M.end())) {
1184            return f->second;
1185        }
1186        assert (isConstant(expr->getClassTypeId()) || isLiteral(expr->getClassTypeId()));
1187        const auto u = makeVertex(expr->getClassTypeId(), expr);
1188        M.emplace(expr, u);
1189        return u;
1190    }
1191
1192    /** ------------------------------------------------------------------------------------------------------------- *
1193     * @brief addStatement
1194     ** ------------------------------------------------------------------------------------------------------------- */
1195    Vertex addStatement(Statement * const stmt) {
1196        assert (stmt);
1197        assert (M.count(stmt) == 0);
1198        const auto typeId = stmt->getClassTypeId();
1199        if (LLVM_UNLIKELY(typeId == TypeId::Sel)) {
1200            const auto c = addExpression(cast<Sel>(stmt)->getCondition());
1201            const auto t = addExpression(cast<Sel>(stmt)->getTrueExpr());
1202            const auto f = addExpression(cast<Sel>(stmt)->getFalseExpr());
1203            const auto u = makeVertex(TypeId::And);
1204            add_edge(c, u, 0, G);
1205            add_edge(t, u, 1, G);
1206            const auto n = makeVertex(TypeId::Not);
1207            add_edge(c, n, 0, G);
1208            const auto v = makeVertex(TypeId::And);
1209            add_edge(n, v, 0, G);
1210            add_edge(f, v, 1, G);
1211            const auto w = makeVertex(TypeId::Or);
1212            add_edge(u, w, 0, G);
1213            add_edge(v, w, 1, G);
1214            M.emplace(stmt, w);
1215            return w;
1216        } else {
1217            const auto u = makeVertex(typeId, stmt);
1218            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1219                PabloAST * const op = stmt->getOperand(i);
1220                if (LLVM_UNLIKELY(isa<String>(op))) {
1221                    continue;
1222                }
1223                add_edge(addExpression(op), u, i, G);
1224            }
1225            assert(hasValidOperandIndicies(u));
1226            M.emplace(stmt, u);
1227            return u;
1228        }
1229    }
1230
1231    /** ------------------------------------------------------------------------------------------------------------- *
1232     * @brief addEdge
1233     ** ------------------------------------------------------------------------------------------------------------- */
1234    bool addEdge(const Vertex u, const Vertex v, const OperandIndex index = 0) {
1235        const auto typeId = getType(v);
1236        if (isAssociative(typeId)) {
1237            for (const auto e : make_iterator_range(out_edges(u, G))) {
1238                if (LLVM_UNLIKELY(target(e, G) == v)) {
1239                    if (LLVM_LIKELY(isDistributive(typeId))) {
1240                        G[e] = std::max(G[e], index);
1241                    } else {
1242                        remove_edge(e, G);
1243                    }
1244                    return false;
1245                }
1246            }
1247        }
1248        boost::add_edge(u, v, index, G);
1249        return true;
1250    }
1251
1252    #ifndef NDEBUG
1253    /** ------------------------------------------------------------------------------------------------------------- *
1254     * @brief hasValidOperandIndicies
1255     ** ------------------------------------------------------------------------------------------------------------- */
1256    bool hasValidOperandIndicies(const Vertex u, const bool report = true) {
1257        if (isLive(u)) {
1258            const auto n = in_degree(u, G);
1259            const auto typeId = getType(u);
1260            if (LLVM_UNLIKELY(n == 0)) {
1261                if (LLVM_LIKELY(isAssociative(typeId) || isNullary(typeId))) {
1262                    return true;
1263                }
1264                if (report) {
1265                    errs() << u << " cannot be nullary " << (int)typeId << "\n";
1266                }
1267                return false;
1268            } else if (isAssociative(typeId)) {
1269                Vertex V[n];
1270                unsigned i = 0;
1271                for (auto e : make_iterator_range(in_edges(u, G))) {
1272                    V[i++] = source(e, G);
1273                }
1274                std::sort(V, V + n);
1275                for (unsigned i = 1; i != n; ++i) {
1276                    if (LLVM_UNLIKELY(V[i - 1] == V[i])) {
1277                        if (report) {
1278                            errs() << u << " has duplicate operands " << V[i] << "\n";
1279                        }
1280                        return false;
1281                    }
1282                }
1283            } else if (requiredOperands(typeId) == n) {
1284                bool used[n] = { false };
1285                for (auto e : make_iterator_range(in_edges(u, G))) {
1286                    const auto i = G[e];
1287                    if (LLVM_UNLIKELY(i >= n)) {
1288                        if (report) {
1289                            errs() << u << " has operand index " << i << " exceeds in degree " << n << "\n";
1290                        }
1291                        return false;
1292                    } else if (LLVM_UNLIKELY(used[i])) {
1293                        if (report) {
1294                            errs() << u << " has duplicate operand indicies " << i << "\n";
1295                        }
1296                        return false;
1297                    }
1298                    used[i] = true;
1299                }
1300            } else {
1301                if (report) {
1302                    errs() << u << " has " << n << " operands but requires " << requiredOperands(typeId) << "\n";
1303                }
1304                return false;
1305            }
1306        }
1307        for (auto e : make_iterator_range(in_edges(u, G))) {
1308            const auto v = source(e, G);
1309            if (!isLive(v)) {
1310                if (report) {
1311                    errs() << u << " has dead operand " << v << "\n";
1312                }
1313                return false;
1314            }
1315        }
1316        return true;
1317    }
1318
1319    static unsigned requiredOperands(const TypeId typeId) {
1320        switch (typeId) {
1321            case TypeId::Not:
1322            case TypeId::InFile:
1323            case TypeId::AtEOF:
1324            case TypeId::Count:
1325            case TypeId::If:
1326            case TypeId::While:
1327                return 1;
1328            case TypeId::Sel:
1329                llvm_unreachable("impossible");
1330            default:
1331                assert (!isAssociative(typeId) && !isNullary(typeId));
1332                return 2;
1333        }
1334    }
1335
1336    static bool isNullary(const TypeId typeId) {
1337        return isConstant(typeId) || isLiteral(typeId);
1338    }
1339    #endif
1340
1341    /** ------------------------------------------------------------------------------------------------------------- *
1342     * @brief removeVertex
1343     ** ------------------------------------------------------------------------------------------------------------- */
1344    void removeVertex(const Vertex u) { assert (isLive(u));
1345        setDead(u);
1346        clear_vertex(u, G);
1347    }
1348
1349    /** ------------------------------------------------------------------------------------------------------------- *
1350     * @brief remapVertex
1351     ** ------------------------------------------------------------------------------------------------------------- */
1352    void remapVertex(const Vertex u, const Vertex v) { assert (u != v);
1353        const PabloAST * expr = getValue(u);
1354        if (expr) {
1355            auto f = M.find(expr);
1356            assert (f != M.end() && f->second == u);
1357            f->second = v;
1358            setValue(v, nullptr);
1359        }
1360        for (const auto e : make_iterator_range(out_edges(u, G))) {
1361            addEdge(v, target(e, G), G[e]);
1362        }
1363        removeVertex(u);
1364    }
1365
1366    /** ------------------------------------------------------------------------------------------------------------- *
1367     * @brief findVertex
1368     ** ------------------------------------------------------------------------------------------------------------- */
1369    Vertex findVertex(const PabloAST * const expr) const {
1370        assert (expr);
1371        const auto f = M.find(expr);
1372        assert (f != M.end());
1373        return f->second;
1374    }
1375
1376    /** ------------------------------------------------------------------------------------------------------------- *
1377     * @brief addDistributionVertex
1378     ** ------------------------------------------------------------------------------------------------------------- */
1379    DistributionVertex addDistributionVertex(const Vertex u) {
1380        assert (isLive(u));
1381        const auto f = Md.find(u);
1382        if (f == Md.end()) {
1383            #ifndef NDEBUG
1384            for (auto v : make_iterator_range(vertices(Gd))) {
1385                assert ("duplicate vertex found that was not in Md!" && Gd[v] != u);
1386            }
1387            #endif
1388            const auto du = add_vertex(u, Gd);
1389            Md.emplace(u, du);
1390            return du;
1391        }
1392        return f->second;
1393    }
1394
1395    /** ------------------------------------------------------------------------------------------------------------- *
1396     * @brief intersects
1397     ** ------------------------------------------------------------------------------------------------------------- */
1398    template <class Type>
1399    inline bool intersects(Type & A, Type & B) {
1400        auto first1 = A.begin(), last1 = A.end();
1401        assert (std::is_sorted(first1, last1));
1402        auto first2 = B.begin(), last2 = B.end();
1403        assert (std::is_sorted(first2, last2));
1404        while (first1 != last1 && first2 != last2) {
1405            if (*first1 < *first2) {
1406                ++first1;
1407            } else if (*first2 < *first1) {
1408                ++first2;
1409            } else {
1410                return true;
1411            }
1412        }
1413        return false;
1414    }
1415
1416    TypeId getType(const Vertex u) const {
1417        assert (u < num_vertices(G));
1418        return std::get<1>(G[u]);
1419    }
1420
1421    void setType(const Vertex u, const TypeId typeId) {
1422        assert (u < num_vertices(G));
1423        std::get<1>(G[u]) = typeId;
1424    }
1425
1426    PabloAST * getValue(const Vertex u) const {
1427        assert (u < num_vertices(G));
1428        return std::get<0>(G[u]);
1429    }
1430
1431    void setValue(const Vertex u, PabloAST * const value) {
1432        assert (u < num_vertices(G));
1433        std::get<0>(G[u]) = value;
1434    }
1435
1436    bool isLive(const Vertex u) const {
1437        return getState(u) != State::Dead;
1438    }
1439
1440    bool isDead(const Vertex u) const {
1441        return getState(u) == State::Dead;
1442    }
1443
1444    void setDead(const Vertex u) {
1445        setState(u, State::Dead);
1446    }
1447
1448    void setUnmodified(const Vertex u) {
1449        setState(u, State::Live);
1450    }
1451
1452    bool isModified(const Vertex u) const {
1453        return getState(u) == State::Modified;
1454    }
1455
1456    void setModified(const Vertex u) {
1457        assert(!isImmutable(getType(u)));
1458        setState(u, State::Modified);
1459    }
1460
1461    State getState(const Vertex u) const {
1462        assert (u < num_vertices(G));
1463        return std::get<2>(G[u]);
1464    }
1465
1466    void setState(const Vertex u, const State value) {
1467        assert (u < num_vertices(G));
1468        std::get<2>(G[u]) = value;
1469    }
1470
1471    UsageTime getLastUsageTime(const Vertex u) const {
1472        assert (u < num_vertices(G));
1473        return std::get<3>(G[u]);
1474    }
1475
1476    void setLastUsageTime(const Vertex u, const UsageTime time) {
1477        assert (u < num_vertices(G));
1478        std::get<3>(G[u]) = time;
1479    }
1480
1481    static bool isIdentityRelation(const TypeId a, const TypeId b) {
1482        assert (isConstant(a) && isDistributive(b));
1483        return !((a == TypeId::Zeroes) ^ (b == TypeId::Or));
1484    }
1485
1486    static bool isAssociative(const TypeId typeId) {
1487        return (isDistributive(typeId) || typeId == TypeId::Xor);
1488    }
1489
1490    static bool isRegenerable(const TypeId typeId) {
1491        return (isConstant(typeId) || isAssociative(typeId) || typeId == TypeId::Not);
1492    }
1493
1494    static bool isAssociative(const PabloAST * const expr) {
1495        return isAssociative(expr->getClassTypeId());
1496    }
1497
1498    static bool isConstant(const TypeId typeId) {
1499        return typeId == TypeId::Zeroes || typeId == TypeId::Ones;
1500    }
1501
1502    static bool isLiteral(const TypeId typeId) {
1503        return typeId == TypeId::Integer || typeId == TypeId::Var;
1504    }
1505
1506    static bool isDistributive(const TypeId typeId) {
1507        return (typeId == TypeId::And || typeId == TypeId::Or);
1508    }
1509
1510    static bool isImmutable(const TypeId typeId) {
1511        switch (typeId) {
1512            case TypeId::Extract: case TypeId::Assign: case TypeId::If: case TypeId::While:
1513                return true;
1514            default:
1515                return isLiteral(typeId);
1516        }
1517    }
1518
1519    static bool isStreamOperation(const TypeId typeId) {
1520        switch (typeId) {
1521            case TypeId::Advance:
1522            case TypeId::ScanThru:
1523            case TypeId::AdvanceThenScanThru:
1524//            case TypeId::ScanTo:
1525//            case TypeId::AdvanceThenScanTo:
1526            case TypeId::Lookahead:
1527            case TypeId::MatchStar:
1528            case TypeId::InFile:
1529            case TypeId::AtEOF:
1530                return true;
1531            default:
1532                return false;
1533        }
1534    }
1535
1536    static TypeId oppositeTypeId(const TypeId typeId) {
1537        assert (isDistributive(typeId));
1538        return (typeId == TypeId::And) ? TypeId::Or : TypeId::And;
1539    }
1540
1541    Vertex first_source(const std::pair<in_edge_iterator, in_edge_iterator> & e) const {
1542        return source(*std::get<0>(e), G);
1543    }
1544
1545private:
1546
1547    Graph G;
1548    flat_map<const pablo::PabloAST *, Vertex> M;
1549
1550    DistributionGraph Gd;
1551    flat_map<Vertex, DistributionVertex> Md;
1552
1553    Sequence ordering;
1554    Sequence distributable;
1555};
1556
1557/** ------------------------------------------------------------------------------------------------------------- *
1558 * @brief optimize
1559 ** ------------------------------------------------------------------------------------------------------------- */
1560bool DistributivePass::optimize(PabloKernel * const kernel) {
1561    PassContainer C;
1562    C.run(kernel);
1563    #ifndef NDEBUG
1564    PabloVerifier::verify(kernel, "post-distributive-pass");
1565    #endif
1566    Simplifier::optimize(kernel);
1567    return true;
1568}
1569
1570}
Note: See TracBrowser for help on using the repository browser.