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

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

Bug fix for DistributivePass?. Minor change to Simplifier to prevent the first conditional assignment of a Var from being combined with its strictly dominating assigned value.

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