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

Last change on this file since 5792 was 5706, checked in by nmedfort, 22 months ago

First stage of MultiBlockKernel? and pipeline restructuring

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