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

Last change on this file since 5608 was 5608, checked in by cameron, 20 months ago

Whole block copying in multiblock kernel builder

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];
1346                std::fill_n(used, n, false);
1347                for (auto e : make_iterator_range(in_edges(u, G))) {
1348                    const auto i = G[e];
1349                    if (LLVM_UNLIKELY(i >= n)) {
1350                        if (report) {
1351                            errs() << u << " has operand index " << i << " exceeds in degree " << n << "\n";
1352                        }
1353                        return false;
1354                    } else if (LLVM_UNLIKELY(used[i])) {
1355                        if (report) {
1356                            errs() << u << " has duplicate operand indicies " << i << "\n";
1357                        }
1358                        return false;
1359                    }
1360                    used[i] = true;
1361                }
1362            } else {
1363                if (report) {
1364                    errs() << u << " has " << n << " operands but requires " << requiredOperands(typeId) << "\n";
1365                }
1366                return false;
1367            }
1368        }
1369        for (auto e : make_iterator_range(in_edges(u, G))) {
1370            const auto v = source(e, G);
1371            if (!isLive(v)) {
1372                if (report) {
1373                    errs() << u << " has dead operand " << v << "\n";
1374                }
1375                return false;
1376            }
1377        }
1378        return true;
1379    }
1380
1381    static unsigned requiredOperands(const TypeId typeId) {
1382        switch (typeId) {
1383            case TypeId::Not:
1384            case TypeId::InFile:
1385            case TypeId::AtEOF:
1386            case TypeId::Count:
1387            case TypeId::If:
1388            case TypeId::While:
1389                return 1;
1390            case TypeId::Sel:
1391                llvm_unreachable("impossible");
1392            default:
1393                assert (!isAssociative(typeId) && !isNullary(typeId));
1394                return 2;
1395        }
1396    }
1397
1398    static bool isNullary(const TypeId typeId) {
1399        return isConstant(typeId) || isLiteral(typeId);
1400    }
1401
1402    /** ------------------------------------------------------------------------------------------------------------- *
1403     * @brief consolidate
1404     ** ------------------------------------------------------------------------------------------------------------- */
1405    Vertex consolidate(const Vertex u) {
1406        assert (isLive(u));
1407        assert (hasValidOperandIndicies(u));
1408        const auto f = V.insert(u);
1409        if (LLVM_UNLIKELY(f.second)) {
1410            return u;
1411        }
1412        const auto v = *f.first;
1413        assert (IdentityComparator(G)(u, v));
1414        replaceVertex(u, v);
1415        return v;
1416    }
1417
1418    /** ------------------------------------------------------------------------------------------------------------- *
1419     * @brief replaceVertex
1420     ** ------------------------------------------------------------------------------------------------------------- */
1421    void replaceVertex(const Vertex u, const Vertex v) {
1422        assert (u != v);
1423        assert (isLive(u) && isLive(v));
1424        const PabloAST * const expr = getValue(u);
1425        if (expr) {
1426            assert (!isRegenerable(getType(u)));
1427            auto f = M.find(expr);
1428            assert (f != M.end() && f->second == u);
1429            f->second = v;
1430            setValue(v, nullptr);
1431            setModified(v);
1432        }
1433        for (const auto e : make_iterator_range(out_edges(u, G))) {
1434            addEdge(v, target(e, G), G[e]);
1435        }
1436        removeVertex(u);
1437    }
1438
1439    /** ------------------------------------------------------------------------------------------------------------- *
1440     * @brief removeVertex
1441     ** ------------------------------------------------------------------------------------------------------------- */
1442    void removeVertex(const Vertex u) {
1443        assert (isLive(u));
1444        setDead(u);
1445        clear_vertex(u, G);       
1446    }
1447
1448    /** ------------------------------------------------------------------------------------------------------------- *
1449     * @brief findVertex
1450     ** ------------------------------------------------------------------------------------------------------------- */
1451    Vertex findVertex(const PabloAST * const expr) const {
1452        assert (expr);
1453        const auto f = M.find(expr);
1454        assert (f != M.end());
1455        return f->second;
1456    }
1457
1458    /** ------------------------------------------------------------------------------------------------------------- *
1459     * @brief addDistributionVertex
1460     ** ------------------------------------------------------------------------------------------------------------- */
1461    DistributionVertex addDistributionVertex(const Vertex u) {
1462        assert (isLive(u));
1463        const auto f = Md.find(u);
1464        if (f == Md.end()) {
1465            #ifndef NDEBUG
1466            for (auto v : make_iterator_range(vertices(Gd))) {
1467                assert ("duplicate vertex found that was not in Md!" && Gd[v] != u);
1468            }
1469            #endif
1470            const auto du = add_vertex(u, Gd);
1471            Md.emplace(u, du);
1472            return du;
1473        }
1474        return f->second;
1475    }
1476
1477    /** ------------------------------------------------------------------------------------------------------------- *
1478     * @brief intersects
1479     ** ------------------------------------------------------------------------------------------------------------- */
1480    template <class Type>
1481    inline bool intersects(Type & A, Type & B) {
1482        auto first1 = A.begin(), last1 = A.end();
1483        assert (std::is_sorted(first1, last1));
1484        auto first2 = B.begin(), last2 = B.end();
1485        assert (std::is_sorted(first2, last2));
1486        while (first1 != last1 && first2 != last2) {
1487            if (*first1 < *first2) {
1488                ++first1;
1489            } else if (*first2 < *first1) {
1490                ++first2;
1491            } else {
1492                return true;
1493            }
1494        }
1495        return false;
1496    }
1497
1498    static TypeId getType(const Vertex u, const Graph & G) {
1499        assert (u < num_vertices(G));
1500        return std::get<1>(G[u]);
1501    }
1502
1503    TypeId getType(const Vertex u) const {
1504        return getType(u, G);
1505    }
1506
1507    void setType(const Vertex u, const TypeId typeId) {
1508        assert (u < num_vertices(G));
1509        std::get<1>(G[u]) = typeId;
1510    }
1511
1512    static PabloAST * getValue(const Vertex u, const Graph & G) {
1513        assert (u < num_vertices(G));
1514        return std::get<0>(G[u]);
1515    }
1516
1517    PabloAST * getValue(const Vertex u) const {
1518        return getValue(u, G);
1519    }
1520
1521    void setValue(const Vertex u, PabloAST * const value) {
1522        assert (u < num_vertices(G));
1523        std::get<0>(G[u]) = value;
1524    }
1525
1526    bool isLive(const Vertex u) const {
1527        return getState(u) != State::Dead;
1528    }
1529
1530    bool isDead(const Vertex u) const {
1531        return getState(u) == State::Dead;
1532    }
1533
1534    void setDead(const Vertex u) {
1535        setState(u, State::Dead);
1536        setValue(u, nullptr);
1537    }
1538
1539    void setUnmodified(const Vertex u) {
1540        setState(u, State::Live);
1541    }
1542
1543    bool isModified(const Vertex u) const {
1544        return getState(u) == State::Modified;
1545    }
1546
1547    void setModified(const Vertex u) {
1548        assert(!isImmutable(getType(u)));
1549        setState(u, State::Modified);
1550    }
1551
1552    State getState(const Vertex u) const {
1553        assert (u < num_vertices(G));
1554        return std::get<2>(G[u]);
1555    }
1556
1557    void setState(const Vertex u, const State value) {
1558        assert (u < num_vertices(G));
1559        std::get<2>(G[u]) = value;
1560    }
1561
1562    UsageTime getLastUsageTime(const Vertex u) const {
1563        assert (u < num_vertices(G));
1564        return std::get<3>(G[u]);
1565    }
1566
1567    void setLastUsageTime(const Vertex u, const UsageTime time) {
1568        assert (u < num_vertices(G));
1569        std::get<3>(G[u]) = time;
1570    }
1571
1572    static bool isIdentityRelation(const TypeId a, const TypeId b) {
1573        assert (isConstant(a) && isDistributive(b));
1574        return !((a == TypeId::Zeroes) ^ (b == TypeId::Or));
1575    }
1576
1577    static bool isAssociative(const TypeId typeId) {
1578        return (isDistributive(typeId) || typeId == TypeId::Xor);
1579    }
1580
1581    static bool isRegenerable(const TypeId typeId) {
1582        return (isConstant(typeId) || isAssociative(typeId) || typeId == TypeId::Not);
1583    }
1584
1585    static bool isAssociative(const PabloAST * const expr) {
1586        return isAssociative(expr->getClassTypeId());
1587    }
1588
1589    static bool isConstant(const TypeId typeId) {
1590        return typeId == TypeId::Zeroes || typeId == TypeId::Ones;
1591    }
1592
1593    static bool isLiteral(const TypeId typeId) {
1594        return typeId == TypeId::Integer || typeId == TypeId::Var;
1595    }
1596
1597    static bool isDistributive(const TypeId typeId) {
1598        return (typeId == TypeId::And || typeId == TypeId::Or);
1599    }
1600
1601    static bool isImmutable(const TypeId typeId) {
1602        switch (typeId) {
1603            case TypeId::Extract: case TypeId::Assign: case TypeId::If: case TypeId::While:
1604                return true;
1605            default:
1606                return isLiteral(typeId);
1607        }
1608    }
1609
1610    static TypeId oppositeTypeId(const TypeId typeId) {
1611        assert (isDistributive(typeId));
1612        return (typeId == TypeId::And) ? TypeId::Or : TypeId::And;
1613    }
1614
1615    Vertex first_source(const std::pair<InEdgeIterator, InEdgeIterator> & e) const {
1616        return source(*std::get<0>(e), G);
1617    }
1618
1619    Vertex getNegatedLiteral(const Vertex u) const {
1620        assert (getType(u) == TypeId::Not);
1621        assert (in_degree(u, G) == 1);
1622        return first_source(in_edges(u, G));
1623    }
1624
1625    Vertex removeNegation(const Vertex u) const {
1626        return getType(u) == TypeId::Not ? getNegatedLiteral(u) : u;
1627    }
1628
1629    /** ------------------------------------------------------------------------------------------------------------- *
1630     * @brief getNegationOf
1631     ** ------------------------------------------------------------------------------------------------------------- */
1632    Vertex getNegationOf(const Vertex u) {
1633        if (getType(u) == TypeId::Not) {
1634            return getNegatedLiteral(u);
1635        } else {
1636            for (const auto e : make_iterator_range(out_edges(u, G))) {
1637                const auto v = target(e, G);
1638                if (getType(v) == TypeId::Not) {
1639                    return v;
1640                }
1641            }
1642            const auto v = makeVertex(TypeId::Not);
1643            add_edge(u, v, 0, G);
1644            return v;
1645        }
1646    }
1647
1648    struct IdentityHash {
1649        size_t operator()(const Vertex u) const {
1650            using value_of = std::underlying_type<TypeId>::type;
1651            #ifndef NDEBUG
1652            InEdgeIterator begin, end;
1653            std::tie(begin, end) = in_edges(u, G);
1654            assert (std::is_sorted(begin, end, [this](const Edge ei, const Edge ej) {
1655                return source(ei, G) <= source(ej, G);
1656            }));
1657            #endif
1658            size_t h = 0;
1659            boost::hash_combine(h, static_cast<value_of>(PassContainer::getType(u, G)));
1660            for (auto e : make_iterator_range(in_edges(u, G))) {
1661                boost::hash_combine(h, source(e, G));
1662            }
1663            return h;
1664        }
1665        IdentityHash (const Graph & g) : G(g) { }
1666    private:
1667        const Graph & G;
1668    };
1669
1670    struct IdentityComparator {
1671        bool operator()(const Vertex u, const Vertex v) const {
1672            const auto typeId = getType(u, G);
1673            if (LLVM_LIKELY(typeId == getType(v, G))) {
1674                const unsigned n = in_degree(u, G);
1675                if (LLVM_UNLIKELY(n == 0)) {
1676                    assert (isNullary(typeId) && in_degree(v, G) == 0);
1677                    return getValue(u, G) == getValue(v, G);
1678                }
1679                if (in_degree(v, G) == n) {
1680                    Vertex adjA[n];
1681                    Vertex adjB[n];
1682                    auto ei = std::get<0>(in_edges(u, G));
1683                    auto ej = std::get<0>(in_edges(v, G));
1684                    // if this is an associative op, order doesn't matter
1685                    if (isAssociative(typeId)) {
1686                        for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
1687                            adjA[i] = source(*ei, G);
1688                            adjB[i] = source(*ej, G);
1689                        }
1690                        assert(std::is_sorted(adjA, adjA + n));
1691                        assert(std::is_sorted(adjB, adjB + n));
1692                    } else { // otherwise consider the order indicated by the edges
1693                        for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
1694                            adjA[G[*ei]] = source(*ei, G);
1695                            adjB[G[*ej]] = source(*ej, G);
1696                        }
1697                    }
1698                    for (unsigned i = 0; i < n; ++i) {
1699                        if (adjA[i] != adjB[i]) {
1700                            return false;
1701                        }
1702                    }
1703                    return true;
1704                }
1705            }
1706            return false;
1707        }
1708        IdentityComparator (const Graph & g) : G(g) { }
1709    private:
1710        const Graph & G;
1711    };
1712
1713    using IdentitySet = std::unordered_set<Vertex, IdentityHash, IdentityComparator>;
1714
1715private:
1716
1717    bool compactedGraph;
1718
1719    Graph G;
1720    flat_map<const pablo::PabloAST *, Vertex> M;
1721
1722    IdentitySet V;
1723
1724    DistributionGraph Gd;
1725    flat_map<Vertex, DistributionVertex> Md;
1726
1727    Sequence ordering;
1728    Sequence distributable;
1729};
1730
1731/** ------------------------------------------------------------------------------------------------------------- *
1732 * @brief optimize
1733 ** ------------------------------------------------------------------------------------------------------------- */
1734bool DistributivePass::optimize(PabloKernel * const kernel) {
1735    PassContainer C;
1736    C.run(kernel);
1737    #ifndef NDEBUG
1738    PabloVerifier::verify(kernel, "post-distributive-pass");
1739    #endif
1740    Simplifier::optimize(kernel);
1741    return true;
1742}
1743
1744}
Note: See TracBrowser for help on using the repository browser.