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

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

Corrected DistributionPass? algorithm.

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