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

Last change on this file was 6184, checked in by nmedfort, 7 months ago

Initial version of PipelineKernel? + revised StreamSet? model.

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