Changeset 5607


Ignore:
Timestamp:
Aug 9, 2017, 3:20:04 PM (12 days ago)
Author:
nmedfort
Message:

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

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r5596 r5607  
    3737#include <pablo/printer_pablos.h>
    3838
     39
    3940using namespace boost;
    4041using namespace boost::container;
    4142using namespace llvm;
    42 using namespace pablo;
    43 
    44 using TypeId = PabloAST::ClassTypeId;
     43
     44struct svecS{};
     45
     46namespace boost {
     47
     48    template<class T>
     49    struct __sorted_edge_vector : public std::vector<T> {
     50        using iterator = typename std::vector<T>::iterator;
     51        void push_back(const T & item) {
     52            const auto p = std::upper_bound(std::vector<T>::begin(), std::vector<T>::end(), item);
     53            std::vector<T>::insert(p, item);
     54        }
     55    };
     56
     57    template <class ValueType> struct container_gen<svecS, ValueType> {
     58        typedef __sorted_edge_vector<ValueType> type;
     59    };
     60
     61    template <> struct parallel_edge_traits<svecS> {
     62        typedef allow_parallel_edge_tag type;
     63    };
     64
     65    template<class T> graph_detail::vector_tag container_category(const __sorted_edge_vector<T>&) {
     66        return graph_detail::vector_tag();
     67    }
     68
     69    template <class T> graph_detail::unstable_tag iterator_stability(const __sorted_edge_vector<T>&) {
     70        return graph_detail::unstable_tag();
     71    }
     72}
     73
     74namespace pablo {
    4575
    4676enum class State {
     
    5080};
    5181
     82using TypeId = PabloAST::ClassTypeId;
     83
    5284using UsageTime = size_t;
    5385
     
    5587
    5688using OperandIndex = unsigned;
    57 
    58 struct svecS{};
    59 
    60 namespace boost {
    61 
    62     template<class T>
    63     struct __sorted_edge_vector : public std::vector<T> {
    64         using iterator = typename std::vector<T>::iterator;
    65         void push_back(const T & item) {
    66             std::vector<T>::insert(std::upper_bound(std::vector<T>::begin(), std::vector<T>::end(), item), item);
    67         }
    68     };
    69 
    70     template <class ValueType> struct container_gen<svecS, ValueType> {
    71         typedef __sorted_edge_vector<ValueType> type;
    72     };
    73 
    74     template <> struct parallel_edge_traits<svecS> {
    75         typedef allow_parallel_edge_tag type;
    76     };
    77 
    78     template<class T> graph_detail::vector_tag container_category(const __sorted_edge_vector<T>&) {
    79         return graph_detail::vector_tag();
    80     }
    81 
    82     template <class T> graph_detail::unstable_tag iterator_stability(const __sorted_edge_vector<T>&) {
    83         return graph_detail::unstable_tag();
    84     }
    85 }
    86 
    87 namespace pablo {
    8889
    8990using Graph = adjacency_list<svecS, vecS, bidirectionalS, VertexData, OperandIndex, vecS>;
     
    137138
    138139    PassContainer()
    139     : reprocessGraph(false)
     140    : compactedGraph(false)
    140141    , V{0, IdentityHash(G), IdentityComparator(G)} {
    141142
     
    199200            // recognizes a duplicate value in scope.
    200201
     202            // TODO: try setting the insertion point to a dominating position of its known (non-regenerable) users
     203            // of each operand?
     204
    201205            entry->setInsertPoint(stmt->getPrevNode());
    202206            for (const auto e : make_iterator_range(in_edges(u, G))) {
     
    221225     * Does vertex (u) have a value and, if so, does value dominate the statement? If not, regenerate it.
    222226     ** ------------------------------------------------------------------------------------------------------------- */
    223     PabloAST * regenerateIfNecessary(Statement * const ip, PabloBlock * const entry, const Vertex u, size_t & count) {
     227    PabloAST * regenerateIfNecessary(const Statement * const stmt, PabloBlock * const entry, const Vertex u, size_t & count) {
    224228        assert (isLive(u));
    225229        PabloAST * value = getValue(u);
    226         if (!dominates(value, ip)) {
     230        if (dominates(value, stmt)) {
     231            assert (isNullary(getType(u)) || getLastUsageTime(u) > 0);
     232        } else { // regenerate the statement ...
    227233
    228234            assert (isRegenerable(getType(u)));
    229 
    230             // if the outdegree of this vertex > 1, try setting the insertion point to a dominating position?
    231 
    232             for (const auto e : make_iterator_range(in_edges(u, G))) {
    233                 regenerateIfNecessary(ip, entry, source(e, G), count);
    234             }
    235235
    236236            const auto n = in_degree(u, G);
     
    244244                    value = entry->createOnes();
    245245                }
    246             } else if (LLVM_LIKELY(n != 1)) {
    247 
    248                 const TypeId typeId = getType(u);
    249 
    250                 assert (isAssociative(typeId));
    251 
    252                 // Suppose we try to minimize the pairwise difference in last usage time,
    253                 // taking into account that we can use negations of variables when they've
    254                 // been used more recently. Take note to update the correct vertex if an
    255                 // ANDC can be used instead.
    256 
    257                 Vertex input[n];
    258                 unsigned i = 0;
    259                 for (auto e : make_iterator_range(in_edges(u, G))) {
    260                     input[i++] = source(e, G);
    261                     assert (getLastUsageTime(source(e, G)) > 0);
    262                 }
    263 
    264                 std::sort(input, input + n, [this](const Vertex u, const Vertex v) {
    265                     return getLastUsageTime(u) < getLastUsageTime(v);
    266                 });
    267 
    268 //                for (unsigned i = 0; i < n; ++i) {
    269 //                    setLastUsageTime(input[i], ++count);
    270 //                }
    271 
    272                 PabloBuilder builder(entry);
    273                 value = getValue(input[0]);
    274                 for (unsigned i = 1; i < n; ++i) {
    275                     PabloAST * const op = getValue(input[i]);                   
    276                     switch (typeId) {
    277                         case TypeId::And:
    278                             value = builder.createAnd(value, op);
    279                             break;
    280                         case TypeId::Or:
    281                             value = builder.createOr(value, op);
    282                             break;
    283                         case TypeId::Xor:
    284                             value = builder.createXor(value, op);
    285                             break;
    286                         default:
    287                             llvm_unreachable("impossible!");
    288                     }
    289                 }
    290246            } else {
    291                 value = entry->createNot(getValue(getNegatedLiteral(u)));
     247
     248                for (const auto e : make_iterator_range(in_edges(u, G))) {
     249                    regenerateIfNecessary(stmt, entry, source(e, G), count);
     250                }
     251
     252                if (LLVM_LIKELY(n != 1)) {
     253
     254                    const TypeId typeId = getType(u);
     255
     256                    assert (isAssociative(typeId));
     257
     258                    // Suppose we try to minimize the pairwise difference in last usage time,
     259                    // taking into account that we can use negations of variables when they've
     260                    // been used more recently. Take note to update the correct vertex if an
     261                    // ANDC can be used instead.
     262
     263                    Vertex input[n];
     264                    unsigned i = 0;
     265                    for (auto e : make_iterator_range(in_edges(u, G))) {
     266                        input[i++] = source(e, G);
     267                    }
     268
     269                    std::sort(input, input + n, [this](const Vertex v, const Vertex w) {
     270                        return getLastUsageTime(v) < getLastUsageTime(w);
     271                    });
     272
     273                    PabloBuilder builder(entry);
     274                    value = getValue(input[0]);
     275                    setLastUsageTime(input[0], ++count);
     276                    for (unsigned i = 1; i < n; ++i) {
     277                        PabloAST * const op = getValue(input[i]);
     278                        setLastUsageTime(input[i], ++count);
     279                        switch (typeId) {
     280                            case TypeId::And:
     281                                value = builder.createAnd(value, op);
     282                                break;
     283                            case TypeId::Or:
     284                                value = builder.createOr(value, op);
     285                                break;
     286                            case TypeId::Xor:
     287                                value = builder.createXor(value, op);
     288                                break;
     289                            default:
     290                                llvm_unreachable("impossible!");
     291                        }
     292                    }
     293                } else {
     294                    const auto v = getNegatedLiteral(u);
     295                    setLastUsageTime(v, ++count);
     296                    value = entry->createNot(getValue(v));
     297                }
    292298            }
    293299            assert (value);
     300            setUnmodified(u);
    294301            setValue(u, value);
    295             setUnmodified(u);
    296302            setLastUsageTime(u, ++count);
    297         }       
     303        }
    298304        return value;
    299305    }
    300306
    301307protected:
    302 
    303     /** ------------------------------------------------------------------------------------------------------------- *
    304      * @brief printGraph
    305      ** ------------------------------------------------------------------------------------------------------------- */
    306     void printGraph(const std::string & name, llvm::raw_ostream & out, std::vector<Vertex> restricted = {}) {
    307 
    308         const auto n = num_vertices(G);
    309         std::vector<unsigned> c(n);
    310         const auto components = strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
    311 
    312         std::vector<bool> show(n, false);
    313         if (LLVM_LIKELY(restricted.empty() && n == components)) {
    314             for (const auto u : make_iterator_range(vertices(G))) {
    315                 show[u] = isLive(u);
    316             }
    317         } else {
    318             std::queue<Vertex> Q;
    319             for (const auto m : restricted) {
    320                 if (m < n && isLive(m)) {
    321                     show[m] = true;
    322                     assert (Q.empty());
    323                     Q.push(m);
    324                     for (;;) {
    325                         const auto u = Q.front();
    326                         Q.pop();
    327                         for (auto e : make_iterator_range(in_edges(u, G))) {
    328                             const auto v = source(e, G);
    329                             if (show[v] || !isLive(v)) {
    330                                 continue;
    331                             }
    332                             show[v] = true;
    333                             Q.push(v);
    334                         }
    335                         if (Q.empty()) {
    336                             break;
    337                         }
    338                     }
    339                     for (auto e : make_iterator_range(out_edges(m, G))) {
    340                         const auto v = target(e, G);
    341                         show[v] = isLive(v) ? true : show[v];
    342                     }
    343                 }
    344             }
    345         }
    346 
    347         out << "digraph " << name << " {\n";
    348         for (auto u : make_iterator_range(vertices(G))) {
    349 
    350             if (show[u]) {
    351 
    352                 out << "v" << u << " [label=\"" << u << ": ";
    353                 TypeId typeId;
    354                 PabloAST * expr;
    355                 State state;
    356 
    357                 std::tie(expr, typeId, state, std::ignore) = G[u];
    358 
    359                 bool space = true;
    360 
    361                 switch (typeId) {
    362                     case TypeId::And:
    363                         out << "(∧)";
    364                         break;
    365                     case TypeId::Or:
    366                         out << "(√)";
    367                         break;
    368                     case TypeId::Xor:
    369                         out << "(⊕)";
    370                         break;
    371                     case TypeId::Not:
    372                         out << "(¬)";
    373                         break;
    374                     case TypeId::Zeroes:
    375                         out << "(⊥)";
    376                         break;
    377                     case TypeId::Ones:
    378                         out << "(⊀)";
    379                     default:
    380                         space = false;
    381                         break;
    382                 }
    383                 if (expr) {
    384                     if (space) {
    385                         out << ' ';
    386                     }
    387                     expr->print(out);
    388                 }
    389 
    390                 out << "\"";
    391                 if (!hasValidOperandIndicies(u)) {
    392                     out << " color=red style=bold";
    393                 } else if (!(isImmutable(typeId) || out_degree(u, G) > 0)) {
    394                     out << " color=orange style=bold";
    395                 } else if (isRegenerable(typeId)) {
    396                     out << " color=blue";
    397                     if (state == State::Modified) {
    398                         out << " style=dashed";
    399                     }
    400                 }
    401                 out << "];\n";
    402             }
    403         }
    404         for (auto e : make_iterator_range(edges(G))) {
    405             const auto s = source(e, G);
    406             const auto t = target(e, G);
    407             if (show[s] && show[t]) {
    408                 const auto cyclic = (c[s] == c[t]);
    409                 const auto nonAssoc = !isAssociative(getType(t));
    410                 out << "v" << s << " -> v" << t;
    411                 if (cyclic || nonAssoc) {
    412                     out << " [";
    413                     if (nonAssoc) {
    414                         out << " label=\"" << G[e] << "\"";
    415                     }
    416                     if (cyclic) {
    417                         out << " color=red";
    418                     }
    419                     out << "]";
    420                 }
    421                 out << ";\n";
    422             }
    423         }
    424 
    425         out << "}\n\n";
    426         out.flush();
    427     }
    428308
    429309    /** ------------------------------------------------------------------------------------------------------------- *
     
    432312    bool simplifyGraph() {
    433313        bool modified = false;
    434         errs() << "=================================================================\n";
    435         printGraph("S", errs());
    436         V.reserve(num_vertices(G));
    437         for (;;) {
    438             V.clear();
    439             getReverseTopologicalOrdering();
    440             if (compactGraph()) {
    441                 continue;
    442             }
    443             if (applyDistributivityLaw()) {
    444                 modified = true;
    445                 continue;
    446             }
    447             break;
    448         }
    449         if (modified) {
    450             factorizeGraph();
    451             errs() << "-----------------------------------------------------------------\n";
    452             printGraph("F", errs());
    453         }
     314repeat: getReverseTopologicalOrdering();
     315        if (compactGraph()) {
     316            goto repeat;
     317        }
     318        if (applyDistributivityLaw()) {
     319            modified = true;
     320            goto repeat;
     321        }
     322        factorizeGraph();
    454323        return modified;
    455324    }
     
    464333                if (LLVM_LIKELY(self.isLive(u))) {
    465334                    assert(self.hasValidOperandIndicies(u));
    466                     if (LLVM_LIKELY(isImmutable(self.getType(u)) || out_degree(u, self.G) != 0)) {
     335                    if (LLVM_UNLIKELY(isImmutable(self.getType(u)))) {
     336                        /* do nothing */
     337                    } else if (LLVM_LIKELY(out_degree(u, self.G) != 0)) {
    467338                        self.ordering.push_back(u);
    468339                    } else {
     
    486357        ordering.reserve(num_vertices(G));
    487358        topological_sort(G, PrePassInserter(*this));
    488         assert (!ordering.empty());
    489359    }
    490360
     
    493363     ** ------------------------------------------------------------------------------------------------------------- */
    494364    bool compactGraph() {
    495         reprocessGraph = false;
     365
     366        V.clear();
     367        compactedGraph = false;
     368
    496369        for (const auto u : boost::adaptors::reverse(ordering)) {
    497             if (LLVM_LIKELY(isLive(u))) {
    498                 const auto typeId = getType(u);
    499                 if (LLVM_UNLIKELY(isImmutable(typeId))) {
     370
     371            const auto typeId = getType(u);
     372
     373            assert (isLive(u));
     374            assert (!isImmutable(typeId));
     375            assert (hasValidOperandIndicies(u));
     376            assert (out_degree(u, G) > 0);
     377
     378            if (LLVM_UNLIKELY(isConstant(typeId))) {
     379                if (processConstant(u, typeId)) {
    500380                    continue;
    501381                }
    502                 assert (hasValidOperandIndicies(u));
    503                 if (LLVM_UNLIKELY(out_degree(u, G) == 0)) {
    504                     removeVertex(u);
     382            } else if (isAssociative(typeId)) {
     383                if (processAssociative(u, typeId)) {
    505384                    continue;
    506385                }
    507                 if (LLVM_UNLIKELY(isConstant(typeId))) {
    508                     if (processConstant(u, typeId)) {
    509                         continue;
    510                     }
    511                 } else if (isAssociative(typeId)) {
    512                     if (processAssociative(u, typeId)) {
    513                         continue;
    514                     }
    515                 } else if (typeId == TypeId::Not) {
    516                     if (processNegation(u)) {
    517                         continue;
    518                     }
    519                 }
    520                 consolidate(u);
    521             }
    522         }
    523         return reprocessGraph;
     386            } else if (typeId == TypeId::Not) {
     387                if (processNegation(u)) {
     388                    continue;
     389                }
     390            }
     391
     392            consolidate(u);
     393        }
     394
     395        return compactedGraph;
    524396    }
    525397
     
    541413            const auto v = first_source(in_edges(u, G));
    542414            for (const auto e : make_iterator_range(out_edges(u, G))) {
    543                 addEdge(v, target(e, G), G[e]);               
     415                addEdge(v, target(e, G), G[e]);
    544416            }
    545417            removeVertex(u);
     418            compactedGraph = true;
    546419            return true;
    547420        } else {
     
    553426                canonicalizeXor(u);
    554427            } else { // is distributive
    555                 applyDeMorganExpansion(u, typeId);
    556                 if (LLVM_UNLIKELY(applyAbsorbtionComplementLaw(u, typeId))) {
    557                     return true;
    558                 }
     428                applyDeMorgans(u, typeId);
     429                return applyAbsorbtionComplementLaw(u, typeId);
    559430            }
    560431        }
     
    566437     ** ------------------------------------------------------------------------------------------------------------- */
    567438    bool transitiveClosure(const Vertex u, const TypeId typeId) {
    568         // Take the transitive closure of these arcs to reveal the underlying equations
    569439
    570440        assert (isLive(u));
     
    576446        for (auto ei : make_iterator_range(out_edges(u, G))) {
    577447            const auto v = target(ei, G);
    578             if (getType(v) == typeId) {
     448            if (typeId == getType(v)) {
    579449                assert(hasValidOperandIndicies(v));
    580450                for (auto ej : make_iterator_range(in_edges(u, G))) {
    581                     addEdge(source(ej, G), v);
     451                    addEdge(source(ej, G), v, G[ei]);
    582452                }
    583453                setModified(v);
    584454                removed[n++] = v;
    585455            }
     456        }
     457        if (LLVM_UNLIKELY(out_degree(u, G) == n)) {
     458            removeVertex(u);
     459            compactedGraph = true;
     460            return true;
    586461        }
    587462        for (unsigned i = 0; i < n; ++i) {
     
    590465            remove_edge(u, v, G);
    591466            assert(hasValidOperandIndicies(v));
    592         }
    593         if (out_degree(u, G) == 0) {
    594             removeVertex(u);
    595             return true;
    596         }
     467            compactedGraph = true;
     468        }
     469        assert (out_degree(u, G) > 0);
    597470        return false;
    598471    }
     
    603476     * (A ⊕ ¬B) = (A ⊕ B ⊕ 1) = ¬(A ⊕ B)
    604477     ** ------------------------------------------------------------------------------------------------------------- */
    605     void canonicalizeXor(const Vertex u) {
     478    Vertex canonicalizeXor(const Vertex u) {
    606479
    607480        assert (isLive(u));
    608481        assert (getType(u) == TypeId::Xor);
     482        assert (in_degree(u, G) > 1);
    609483
    610484        const auto l = in_degree(u, G);
     
    625499                assert (edge(v, u, G).second);
    626500                remove_edge(v, u, G);
    627                 addEdge(first_source(in_edges(v, G)), u);
     501                addEdge(getNegatedLiteral(v), u);
    628502            }
    629503            for (unsigned i = 0; i < m; ++i) {
     
    632506                remove_edge(v, u, G);
    633507            }
     508            setModified(u);
     509            compactedGraph = true;
    634510            if (((n + m) & 1) != 0) {
    635511                const auto x = makeVertex(TypeId::Not);
     
    637513                    add_edge(x, target(e, G), G[e], G);
    638514                }
    639                 clear_out_edges(u, G);
     515                clear_out_edges(u, G);               
    640516                add_edge(u, x, 0, G);
    641             }
    642             setModified(u);
    643             assert(hasValidOperandIndicies(u));
    644         }
     517                assert(hasValidOperandIndicies(u));               
     518                return x;
     519            }
     520        }
     521        return u;
    645522    }
    646523
     
    664541            }
    665542            removeVertex(u);
     543            compactedGraph = true;
    666544            return true;
    667545        }
     
    670548
    671549    /** ------------------------------------------------------------------------------------------------------------- *
    672      * @brief applyDeMorganExpansion
    673      ** ------------------------------------------------------------------------------------------------------------- */
    674     bool applyDeMorganExpansion(const Vertex u, const TypeId typeId) {
     550     * @brief applyDeMorgans
     551     ** ------------------------------------------------------------------------------------------------------------- */
     552    bool applyDeMorgans(const Vertex u, const TypeId typeId) {
    675553
    676554        assert (isLive(u));
     
    708586            }
    709587            setModified(u);
    710             reprocessGraph = true;
    711588            assert(hasValidOperandIndicies(u));
     589            compactedGraph = true;
    712590            return true;
    713591        }
    714592        return false;
    715     }
    716 
    717     /** ------------------------------------------------------------------------------------------------------------- *
    718      * @brief applyXorTransformation
    719      *
    720      * (A ∧ ¬B ∧ C) √ (¬A ∧ B ∧ D) ⇔ (A ⊕ B) ∧ ((A ∧ C) √ (B ∧ D))
    721      *
    722      * (A √ ¬B √ C) ∧ (¬A √ B √ D) ⇔ ¬(A ⊕ B) √ ((A √ C) ∧ (B √ D))
    723      ** ------------------------------------------------------------------------------------------------------------- */
    724     bool applyXorTransformation() {
    725         reprocessGraph = false;
    726         for (const auto u : ordering) {
    727             const auto typeId = getType(u);
    728             if (isDistributive(typeId)) {
    729                 if (LLVM_LIKELY(in_degree(u, G) > 1)) {
    730                     while (LLVM_UNLIKELY(applyXorTransformation(u, typeId)));
    731                 }
    732             }
    733         }
    734         return reprocessGraph;
    735     }
    736 
    737     /** ------------------------------------------------------------------------------------------------------------- *
    738      * @brief applyXorTransformation
    739      *
    740      * (A ∧ ¬B ∧ C) √ (¬A ∧ B ∧ D) ⇔ (A ⊕ B) ∧ ((A ∧ C) √ (B ∧ D))
    741      *
    742      * (A √ ¬B √ C) ∧ (¬A √ B √ D) ⇔ ¬(A ⊕ B) √ ((A √ C) ∧ (B √ D))
    743      ** ------------------------------------------------------------------------------------------------------------- */
    744     bool applyXorTransformation(const Vertex u, const TypeId typeId) {
    745 
    746         if (in_degree(u, G) != 2) {
    747             return false;
    748         }
    749 
    750         unsigned clauses = 0;
    751         unsigned count = 0;
    752         assert (getType(u) == typeId);
    753         const TypeId innerTypeId = oppositeTypeId(typeId);
    754         assert (in_degree(u, G) > 1);
    755 
    756         for (const auto e : make_iterator_range(in_edges(u, G))) {
    757             const auto v = source(e, G);
    758             if (isXorCandidate(v, innerTypeId)) {
    759                 ++clauses;
    760                 count += in_degree(v, G);
    761             }
    762         }
    763 
    764         if (clauses > 1) {
    765             unsigned B[clauses + 1];
    766             Vertex C[clauses];
    767             Vertex V[count];
    768 
    769             unsigned i = 0, j = 0;
    770 
    771             for (const auto e : make_iterator_range(in_edges(u, G))) {
    772                 const auto v = source(e, G);
    773                 if (isXorCandidate(v, innerTypeId)) {
    774                     B[i] = j;
    775                     C[i] = v;
    776                     for (const auto e : make_iterator_range(in_edges(v, G))) {
    777                         V[j++] = source(e, G);
    778                     }
    779                     // We know no clause contains {A, A}, {A, ¬A} or {¬¬A} for any A.
    780                     std::sort(V + B[i++], V + j, [this](const Vertex u, const Vertex v){
    781                         return removeNegation(u) < removeNegation(v);
    782                     });
    783                 }
    784             }
    785             B[clauses] = j;
    786 
    787             for (unsigned i = 0; i < (clauses - 1); ++i) {
    788                 for (unsigned j = (i + 1); j < clauses; ++j) {
    789                     bool first = true;
    790                     unsigned ei = B[i], ej = B[j], ek = 0;
    791                     while (ei < B[i + 1] && ej < B[j + 1]) {
    792                         if (V[ei] == V[ej]) {
    793                             ++ei, ++ej;
    794                         } else {
    795                             if (LLVM_UNLIKELY(isNegationOf(V[ei], V[ej]))) {
    796                                 if (LLVM_LIKELY(first)) {
    797                                     ek = ei;
    798                                     first = false;
    799                                     ++ei, ++ej;
    800                                     continue;
    801                                 } else {
    802                                     const auto x = V[ek];
    803                                     const auto v = C[i];
    804                                     const auto y = V[ej];
    805                                     const auto w = C[j];
    806 
    807                                     reprocessGraph = true;
    808 
    809                                     assert (edge(x, v, G).second);
    810                                     remove_edge(x, v, G);
    811                                     assert (edge(y, w, G).second);
    812                                     remove_edge(y, w, G);
    813 
    814                                     const auto a = makeVertex(typeId);
    815                                     add_edge(v, a, 0, G);
    816                                     add_edge(w, a, 0, G);
    817 
    818                                     const auto z = makeVertex(TypeId::Xor);
    819                                     add_edge(x, z, 0, G);
    820                                     add_edge(y, z, 0, G);
    821 
    822                                     auto b = z;
    823                                     if (LLVM_UNLIKELY(typeId == TypeId::And)) {
    824                                         b = getNegationOf(z);
    825                                     }
    826                                     canonicalizeXor(z);
    827                                     if (LLVM_UNLIKELY(b != z)) {
    828                                         processNegation(b);
    829                                     }
    830 
    831                                     if (in_degree(u, G) == 2) {
    832                                         clear_in_edges(u, G);
    833                                         setType(u, innerTypeId);
    834                                         add_edge(a, u, 0, G);
    835                                         add_edge(b, u, 0, G);
    836                                         return false;
    837                                     } else {
    838                                         assert (edge(v, u, G).second);
    839                                         remove_edge(v, u, G);
    840                                         assert (edge(w, u, G).second);
    841                                         remove_edge(w, u, G);
    842                                         const auto c = makeVertex(innerTypeId);
    843                                         add_edge(a, c, 0, G);
    844                                         add_edge(b, c, 0, G);
    845                                         add_edge(c, u, 0, G);
    846                                         assert (in_degree(u, G) > 1);
    847                                         return true;
    848                                     }
    849                                 }
    850                             }
    851                             if (removeNegation(V[ei]) < removeNegation(V[ej])) {
    852                                 ++ei;
    853                             } else {
    854                                 ++ej;
    855                             }
    856                         }
    857                     }
    858                 }
    859             }
    860         }
    861         return false;
    862     }
    863 
    864     bool isXorCandidate(const Vertex u, const TypeId typeId) const {
    865         assert (isAssociative(typeId));
    866         return (getType(u) == typeId) && (out_degree(u, G) == 1) && (in_degree(u, G) > 1);
    867     }
    868 
    869     bool isNegationOf(const Vertex u, const Vertex v) const {
    870         const auto t = (getType(u) == TypeId::Not);
    871         if (t ^ (getType(v) == TypeId::Not)) {
    872             if (t) {
    873                 return getNegatedLiteral(u) == v;
    874             } else { // if (getType(y) == TypeId::Not) {
    875                 return u == getNegatedLiteral(v);
    876             }
    877         }
    878         return false;
    879     }
    880 
    881     /** ------------------------------------------------------------------------------------------------------------- *
    882      * @brief getNegationOf
    883      ** ------------------------------------------------------------------------------------------------------------- */
    884     Vertex getNegationOf(const Vertex u) {
    885         if (getType(u) == TypeId::Not) {
    886             return getNegatedLiteral(u);
    887         } else {
    888             for (const auto e : make_iterator_range(out_edges(u, G))) {
    889                 const auto v = target(e, G);
    890                 if (getType(v) == TypeId::Not) {
    891                     return v;
    892                 }
    893             }
    894             const auto v = makeVertex(TypeId::Not);
    895             add_edge(u, v, 0, G);
    896             return v;
    897         }
    898     }
    899 
    900     Vertex getNegatedLiteral(const Vertex u) const {
    901         assert (getType(u) == TypeId::Not);
    902         assert (in_degree(u, G) == 1);
    903         return first_source(in_edges(u, G));
    904     }
    905 
    906     Vertex removeNegation(const Vertex u) const {
    907         return getType(u) == TypeId::Not ? getNegatedLiteral(u) : u;
     593
    908594    }
    909595
     
    925611            const auto innerTypeId = getType(v);
    926612            if (innerTypeId == TypeId::Not) {
    927                 const auto w = getNegatedLiteral(v);
     613                const auto w = first_source(in_edges(v, G));
    928614                assert (isLive(w));
    929615                for (const auto ej : make_iterator_range(in_edges(u, G))) {
     
    941627        }
    942628
    943         if (n) {
     629        if (LLVM_UNLIKELY(n != 0)) {
    944630            setModified(u);
    945             reprocessGraph = true;
    946             for (;;) {
     631            compactedGraph = true;
     632            do {
    947633                const auto v = A[--n];
    948634                assert (edge(v, u, G).second);
    949635                remove_edge(v, u, G);
    950                 if (LLVM_UNLIKELY(out_degree(v, G) == 0)) {
    951                     removeVertex(v);
    952                 }
    953                 if (LLVM_LIKELY(n == 0)) {
    954                     break;
    955                 }
    956             }
     636            } while (LLVM_UNLIKELY(n != 0));
    957637        }
    958638
     
    1005685                }
    1006686            } else if (LLVM_UNLIKELY(targetTypeId == TypeId::Not)) {
    1007                 const auto negatedTypeId = (typeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes;
    1008                 setType(u, negatedTypeId);
     687                setType(u, (typeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes);
    1009688                modification[m++] = v;
    1010             } else if (LLVM_UNLIKELY(isStreamOperation(typeId))) {
     689            } else { // check if this is a stream operation and optimize accordingly
    1011690                if (LLVM_LIKELY(typeId == TypeId::Zeroes)) {
    1012                     setType(v, TypeId::Zeroes);
    1013                     modification[m++] = v;
     691                    switch (targetTypeId) {
     692                        case TypeId::Advance:
     693                        case TypeId::Lookahead:
     694                        case TypeId::InFile:
     695                        case TypeId::AtEOF:
     696                            assert (G[e] == 0);
     697                            setType(v, TypeId::Zeroes);
     698                            modification[m++] = v;
     699                            break;
     700                        case TypeId::ScanThru:
     701                        case TypeId::AdvanceThenScanThru:
     702                        case TypeId::MatchStar:
     703                            if (G[e] == 0) {
     704                                setType(v, TypeId::Zeroes);
     705                                modification[m++] = v;
     706                            } else {
     707                                strengthReduction(v);
     708                            }
     709                            break;
     710                        case TypeId::ScanTo:
     711                        case TypeId::AdvanceThenScanTo:
     712                            strengthReduction(v);
     713                        default: break;
     714                    }
    1014715                } else { // if (typeId == TypeId::Ones) {
    1015716                    switch (targetTypeId) {
    1016717                        case TypeId::ScanThru:
    1017                             if (LLVM_UNLIKELY(G[e] == 1)) {
     718                            if (G[e] == 1) {
    1018719                                setType(v, TypeId::Zeroes);
    1019720                                modification[m++] = v;
     
    1021722                            break;
    1022723                        case TypeId::MatchStar:
    1023                             if (LLVM_UNLIKELY(G[e] == 0)) {
     724                            if (G[e] == 0) {
    1024725                                setType(v, TypeId::Ones);
    1025726                                modification[m++] = v;
     
    1036737        }
    1037738
     739        compactedGraph = true;
     740
    1038741        // handle any identity graph modifications
    1039742        while (LLVM_UNLIKELY(n != 0)) {
     
    1056759
    1057760        return false;
     761    }
     762
     763    /** ------------------------------------------------------------------------------------------------------------- *
     764     * @brief strengthReduction
     765     ** ------------------------------------------------------------------------------------------------------------- */
     766    void strengthReduction(const Vertex u) {
     767
     768
    1058769    }
    1059770
     
    1088799            const auto upperSet = obtainDistributableSources(std::get<1>(lower));
    1089800            for (const auto & upper : upperSet) {
    1090 
    1091801                const auto & inner = std::get<0>(upper);
    1092802                const auto & sources = std::get<1>(upper);
     
    1096806
    1097807                // Update G to match the desired change
    1098                 auto x = makeVertex(outerTypeId);
    1099                 auto y = makeVertex(innerTypeId);
    1100 
    1101                 for (const Vertex i : sources) {
    1102                     const auto u = Gd[i];
    1103                     for (const Vertex j : inner) {
    1104                         const auto v = Gd[j];
    1105                         assert (edge(u, v, G).second);
    1106                         assert (getType(v) == innerTypeId);
    1107                         remove_edge(u, v, G);
    1108                     }
    1109                     add_edge(u, y, 0, G);
    1110                 }
    1111                 y = consolidate(y);
     808                const auto x = makeVertex(outerTypeId);
    1112809                for (const auto i : inner) {
    1113810                    const auto u = Gd[i];
     
    1119816                        remove_edge(u, v, G);
    1120817                    }
    1121                     add_edge(u, x, 0, G);
    1122                 }
    1123                 x = consolidate(x);
    1124                 addEdge(x, y);
     818                    addEdge(u, x);
     819                }
     820                const auto y = makeVertex(innerTypeId);
     821                addEdge(consolidate(x), y);
     822                for (const Vertex i : sources) {
     823                    const auto u = Gd[i];
     824                    for (const Vertex j : inner) {
     825                        const auto v = Gd[j];
     826                        assert (edge(u, v, G).second);
     827                        assert (getType(v) == innerTypeId);
     828                        remove_edge(u, v, G);
     829                    }
     830                    addEdge(u, y);
     831                }
     832                const auto yy = consolidate(y);
    1125833                for (const Vertex i : outer) {
    1126834                    const auto u = Gd[i];
    1127835                    assert (getType(u) == outerTypeId);
    1128836                    setModified(u);
    1129                     addEdge(y, u);
    1130                 }
     837                    addEdge(yy, u);
     838                }
     839
    1131840                modified = true;
    1132841            }
     
    1151860                if (isDistributive(outerTypeId)) {
    1152861                    const auto n = in_degree(u, G);
    1153                     if (n < 2) continue;
    1154862                    assert (n > 1);
    1155863                    const auto innerTypeId = oppositeTypeId(getType(u));
     
    1202910    BicliqueSet obtainDistributableClauses(const Sequence & S) {
    1203911        auto cliques = enumerateBicliques(S, Gd, 1, 2);
     912
    1204913        // remove any cliques from our set that do not contain all of their users
    1205         for (auto ci = cliques.begin(); ci != cliques.end(); ) {
    1206             const auto & A = std::get<0>(*ci);
    1207             auto & B = std::get<1>(*ci);
    1208             for (auto bi = B.begin(); bi != B.end(); ) {
    1209                 if (out_degree(Gd[*bi], G) != A.size()) {
    1210                     bi = B.erase(bi);
    1211                 } else {
    1212                     ++bi;
    1213                 }
    1214             }
    1215             if (B.size() < 2) {
    1216                 ci = cliques.erase(ci);
    1217             } else {
    1218                 ++ci;
    1219             }
    1220         }
     914        cliques.erase(std::remove_if(cliques.begin(), cliques.end(), [this](Biclique & C){
     915            const auto & A = std::get<0>(C);
     916            auto & B = std::get<1>(C);
     917            B.erase(std::remove_if(B.begin(), B.end(), [this, &A](const DistributionVertex u) {
     918                return out_degree(Gd[u], G) != A.size();
     919            }), B.end());
     920            return B.size() < 2;
     921        }), cliques.end());
     922
    1221923        return makeIndependent(std::move(cliques), 0);
    1222924    }
     
    1236938    void factorizeGraph() {
    1237939
    1238         Sequence associative;
     940        Sequence associative(0);
     941        associative.reserve(num_vertices(G));
     942
    1239943        for (const auto u : make_iterator_range(vertices(G))) {
    1240944            if (isLive(u) && isAssociative(getType(u))) {
     
    1244948
    1245949        // Although we risk losing better combinations by greedily taking the larger factorings,
    1246         // choosing only those of minSize or greater first can significantly reduce the running
    1247         // time of this optimization.
     950        // choosing only those of some minSizeB or greater first can significantly reduce the
     951        // running time of this optimization.
    1248952
    1249953        Sequence group[3];
     
    1251955        const TypeId typeCode[3] = { TypeId::And, TypeId::Or, TypeId::Xor };
    1252956
     957        for (unsigned i = 0; i < 3; ++i) {
     958            assert (getFactorGroup(typeCode[i]) == i);
     959        }
     960
    1253961        for (;;) {
    1254962
    1255             auto factors = makeIndependent(enumerateBicliques(associative, G, 2, 2), 1);
    1256             if (factors.empty()) {
     963            // This should be made smarter. Ideally I'd like to factor sets of variables that are
     964            // whose sources are computed around the same point in the program.
     965
     966            const auto factors = makeIndependent(enumerateBicliques(associative, G, 2, 2), 1);
     967
     968            if (LLVM_UNLIKELY(factors.empty())) {
    1257969                break;
    1258970            }
     
    1260972            bool unchanged = true;
    1261973
    1262             for (auto & factor : factors) {
    1263                 const auto & sources = std::get<1>(factor);
     974            for (const auto factor : factors) {
     975                const auto sources = std::get<1>(factor);
    1264976                assert (sources.size() > 1);
    1265                 auto & targets = std::get<0>(factor);
     977                const auto targets = std::get<0>(factor);
    1266978                assert (targets.size() > 1);
    1267979
    1268                 for (unsigned k = 0; k < 3; ++k) {
    1269                     assert (group[k].empty());
     980                for (unsigned i = 0; i < 3; ++i) {
     981                    assert (group[i].empty());
    1270982                }
    1271983
     
    1275987                for (const auto u : targets) {
    1276988                    assert (hasValidOperandIndicies(u));
    1277                     const auto k = factorGroup(getType(u));
     989                    const auto k = getFactorGroup(getType(u));
    1278990                    if (LLVM_UNLIKELY(in_degree(u, G) == sources.size())) {
    1279                         if (LLVM_LIKELY(create[k])) {
    1280                             t[k] = u;
    1281                             create[k] = false;
    1282                         } else {
    1283                             for (auto e : make_iterator_range(out_edges(u, G))) {
    1284                                 addEdge(t[k], target(e, G), G[e]);
    1285                             }
    1286                             removeVertex(u);
    1287                         }
     991                        assert (create[k]);
     992                        t[k] = u;
     993                        create[k] = false;
    1288994                    } else {
    1289995                        group[k].push_back(u);
     
    1292998
    1293999                for (unsigned k = 0; k < 3; ++k) {
    1294                     if (LLVM_LIKELY(group[k].empty())) {
    1295                         continue;
    1296                     }
    1297                     if (LLVM_LIKELY(create[k])) {
    1298                         t[k] = makeVertex(typeCode[k]);
     1000                    if (LLVM_LIKELY(group[k].size() > (create[k] ? 1 : 0))) {
     1001                        if (LLVM_LIKELY(create[k])) {
     1002                            t[k] = makeVertex(typeCode[k]);
     1003                            for (const auto u : sources) {
     1004                                add_edge(u, t[k], 0, G);
     1005                            }
     1006                            associative.push_back(t[k]);
     1007                            assert (t[k] == consolidate(t[k]));
     1008                        }
     1009
     1010                        assert (hasValidOperandIndicies(t[k]));
     1011                        // Remove the biclique between the source and target vertices
    12991012                        for (auto u : sources) {
    1300                             add_edge(u, t[k], 0, G);
     1013                            for (auto v : group[k]) {
     1014                                assert (getType(v) == typeCode[k]);
     1015                                assert (edge(u, v, G).second);
     1016                                boost::remove_edge(u, v, G);
     1017                            }
    13011018                        }
    1302                         associative.push_back(t[k]);
    1303                     }
    1304                     assert (hasValidOperandIndicies(t[k]));
    1305                     // Remove the biclique between the source and target vertices
    1306                     for (auto u : sources) {
     1019                        // ... and replace it with the factorization
    13071020                        for (auto v : group[k]) {
    13081021                            assert (getType(v) == typeCode[k]);
    1309                             assert (edge(u, v, G).second);
    1310                             boost::remove_edge(u, v, G);
     1022                            addEdge(t[k], v);
     1023                            setModified(v);
     1024                            assert(hasValidOperandIndicies(v));
    13111025                        }
    1312                     }
    1313                     // ... and replace it with the factorization
    1314                     for (auto v : group[k]) {
    1315                         assert (getType(v) == typeCode[k]);
    1316                         addEdge(t[k], v);
    1317                         setModified(v);
    1318                         assert(hasValidOperandIndicies(v));
     1026                        unchanged = false;
    13191027                    }
    13201028                    group[k].clear();
    1321                     unchanged = false;
    13221029                }
    13231030            }
    13241031
    13251032            if (unchanged) {
    1326                 break;
    1327             }
    1328         }
    1329 
    1330 //        #ifndef NDEBUG
    1331 //        for (const auto u : make_iterator_range(vertices(G))) {
    1332 //            if (LLVM_LIKELY(isLive(u))) {
    1333 //                const auto typeId = getType(u);
    1334 //                if (isAssociative(typeId)) {
    1335 //                    if (in_degree(u, G) != 2) {
    1336 //                        bool atMostOneSourceVertexCanHaveAnOutDegreeOverOne = true;
    1337 //                        for (auto e : make_iterator_range(in_edges(u, G))) {
    1338 //                            if (out_degree(source(e, G), G) != 1) {
    1339 //                                assert (atMostOneSourceVertexCanHaveAnOutDegreeOverOne);
    1340 //                                atMostOneSourceVertexCanHaveAnOutDegreeOverOne = false;
    1341 //                            }
    1342 //                        }
    1343 //                    }
    1344 //                }
    1345 //            }
    1346 //        }
    1347 //        #endif
    1348 
    1349     }
    1350 
    1351     unsigned factorGroup(const TypeId typeId) {
     1033                for (const auto factor : factors) {
     1034                    const auto targets = std::get<0>(factor);
     1035                    for (const auto u : targets) {
     1036                        const auto f = std::lower_bound(associative.begin(), associative.end(), u);
     1037                        if (LLVM_LIKELY(f != associative.end() && *f == u)) {
     1038                            associative.erase(f);
     1039                        }
     1040                    }
     1041                }
     1042            }
     1043        }
     1044    }
     1045
     1046    /** ------------------------------------------------------------------------------------------------------------- *
     1047     * @brief getFactorGroup
     1048     ** ------------------------------------------------------------------------------------------------------------- */
     1049    static unsigned getFactorGroup(const TypeId typeId) {
    13521050        switch (typeId) {
    13531051            case TypeId::And:
     
    13601058        }
    13611059    }
    1362 
    1363 //    /** ------------------------------------------------------------------------------------------------------------- *
    1364 //     * @brief applyDeMorganContraction
    1365 //     ** ------------------------------------------------------------------------------------------------------------- */
    1366 //    bool applyDeMorganContraction(const Vertex u, const TypeId typeId) {
    1367 
    1368 //        assert (isLive(u));
    1369 //        assert (in_degree(u, G) > 0);
    1370 //        assert (getType(u) == typeId);
    1371 //        assert (isDistributive(typeId));
    1372 
    1373 //        Vertex T[in_degree(u, G)];
    1374 //        unsigned n = 0;
    1375 //        for (const auto e : make_iterator_range(in_edges(u, G))) {
    1376 //            const auto v = source(e, G);
    1377 //            if (getType(v) == TypeId::Not) {
    1378 //                T[n++] = v;
    1379 //            }
    1380 //        }
    1381 //        if (LLVM_UNLIKELY(n > 1)) {
    1382 //            const auto oppositeType = oppositeTypeId(typeId);
    1383 //            Vertex x = makeVertex(oppositeType);
    1384 //            for (unsigned i = 0; i < n; ++i) {
    1385 //                const auto v = T[i];
    1386 //                const auto w = first_source(in_edges(v, G));
    1387 //                add_edge(w, x, 0, G);
    1388 //                remove_edge(v, u, G);
    1389 //            }
    1390 //            x = consolidate(x);
    1391 //            if (in_degree(u, G) == 0) {
    1392 //                setType(u, TypeId::Not);
    1393 //                add_edge(x, u, 0, G);
    1394 //                processNegation(u);
    1395 //                return true;
    1396 //            } else {
    1397 //                Vertex y = makeVertex(TypeId::Not);
    1398 //                add_edge(x, y, 0, G);
    1399 //                y = consolidate(y);
    1400 //                add_edge(y, u, 0, G);
    1401 //                processNegation(y);
    1402 //            }
    1403 //            return processAssociative(x, oppositeType);
    1404 //        }
    1405 //        return false;
    1406 //    }
    1407 
    14081060
    14091061private:
     
    14391091                    }
    14401092                    if (B.size() >= minimumSizeB) {
    1441                         // std::sort(B.begin(), B.end());
    14421093                        assert (std::is_sorted(B.begin(), B.end()));
    14431094                        assert (std::unique(B.begin(), B.end()) == B.end());
     
    15021153                        T.push_back(target(e, G));
    15031154                    }
    1504                     // std::sort(T.begin(), T.end());
    15051155                    assert (std::is_sorted(T.begin(), T.end()));
    15061156                    assert (std::unique(T.begin(), T.end()) == T.end());
     
    15301180
    15311181        const auto l = S.size();
     1182        IndependentSetGraph I(l);
     1183
    15321184        assert (independentSide < 2);
    1533         if (LLVM_LIKELY(l > 1)) {
    1534 
    1535             IndependentSetGraph I(l);
    1536 
    1537             // Initialize our weights
     1185
     1186        // Initialize our weights
     1187        for (unsigned i = 0; i != l; ++i) {
     1188            I[i] = std::get<0>(S[i]).size() * std::get<1>(S[i]).size();
     1189        }
     1190
     1191        // Determine our constraints
     1192        for (unsigned i = 0; i != l; ++i) {
     1193            const auto & Si = (independentSide == 0) ? std::get<0>(S[i]) : std::get<1>(S[i]);
     1194            for (unsigned j = i + 1; j != l; ++j) {
     1195                const auto & Sj = (independentSide == 0) ? std::get<0>(S[j]) : std::get<1>(S[j]);
     1196                if (intersects(Si, Sj)) {
     1197                    boost::add_edge(i, j, I);
     1198                }
     1199            }
     1200        }
     1201
     1202        // Use the greedy algorithm to choose our independent set
     1203        Sequence selected;
     1204        for (;;) {
     1205            unsigned w = 0;
     1206            Vertex u = 0;
    15381207            for (unsigned i = 0; i != l; ++i) {
    1539                 I[i] = std::get<0>(S[i]).size() * std::get<1>(S[i]).size();
    1540             }
    1541 
    1542             // Determine our constraints
    1543             for (unsigned i = 0; i != l; ++i) {
    1544                 const auto & Si = (independentSide == 0) ? std::get<0>(S[i]) : std::get<1>(S[i]);
    1545                 for (unsigned j = i + 1; j != l; ++j) {
    1546                     const auto & Sj = (independentSide == 0) ? std::get<0>(S[j]) : std::get<1>(S[j]);
    1547                     if (intersects(Si, Sj)) {
    1548                         boost::add_edge(i, j, I);
    1549                     }
    1550                 }
    1551             }
    1552 
    1553             // Use the greedy algorithm to choose our independent set
    1554             Sequence selected;
    1555             for (;;) {
    1556                 Vertex u = 0;
    1557                 auto w = I[0];
    1558                 for (unsigned i = 1; i != l; ++i) {
    1559                     if (I[i] > w) {
    1560                         w = I[i];
    1561                         u = i;
    1562                     }
    1563                 }
    1564                 if (LLVM_UNLIKELY(w == 0)) break;
    1565                 selected.push_back(u);
    1566                 I[u] = 0;
    1567                 for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
    1568                     I[v] = 0;
    1569                 }
    1570             }
    1571 
    1572             // Sort the selected list and then remove the unselected cliques
    1573             std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
    1574             auto end = S.end();
    1575             for (const unsigned offset : selected) {
    1576                 end = S.erase(S.begin() + offset + 1, end) - 1;
    1577             }
    1578             S.erase(S.begin(), end);
    1579         }
     1208                if (I[i] > w) {
     1209                    w = I[i];
     1210                    u = i;
     1211                }
     1212            }
     1213            if (LLVM_UNLIKELY(w == 0)) break;
     1214            selected.push_back(u);
     1215            I[u] = 0;
     1216            for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
     1217                I[v] = 0;
     1218            }
     1219        }
     1220
     1221        // Sort the selected list and then remove the unselected cliques
     1222        std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
     1223        auto end = S.end();
     1224        for (const unsigned offset : selected) {
     1225            end = S.erase(S.begin() + offset + 1, end) - 1;
     1226        }
     1227        S.erase(S.begin(), end);
    15801228
    15811229        return std::move(S);
     
    15861234     ** ------------------------------------------------------------------------------------------------------------- */
    15871235    Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) {
    1588         reprocessGraph = true;
    15891236        return add_vertex(std::make_tuple(expr, typeId, expr ? State::Live : State::Modified, 0), G);
    15901237    }
     
    16291276            M.emplace(stmt, w);
    16301277            return w;
    1631 //        } else if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
    1632 //            assert (stmt->getNumOperands() == 2);
    1633 //            const auto a = addExpression(stmt->getOperand(0));
    1634 //            const auto b = addExpression(stmt->getOperand(1));
    1635 //            const auto c = makeVertex(TypeId::Not);
    1636 //            add_edge(b, c, 0, G);
    1637 //            const auto d = makeVertex(TypeId::Not);
    1638 //            add_edge(a, d, 0, G);
    1639 //            const auto u = makeVertex(TypeId::And);
    1640 //            add_edge(a, u, 0, G);
    1641 //            add_edge(c, u, 1, G);
    1642 //            const auto v = makeVertex(TypeId::And);
    1643 //            add_edge(b, v, 0, G);
    1644 //            add_edge(d, v, 1, G);
    1645 //            const auto w = makeVertex(TypeId::Or);
    1646 //            add_edge(u, w, 0, G);
    1647 //            add_edge(v, w, 1, G);
    1648 //            M.emplace(stmt, w);
    1649 //            return w;
    16501278        } else {
    16511279            const auto u = makeVertex(typeId, isRegenerable(typeId) ? nullptr : stmt);
     
    16711299            for (const auto e : make_iterator_range(out_edges(u, G))) {
    16721300                if (LLVM_UNLIKELY(target(e, G) == v)) {
    1673                     if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
     1301                    if (LLVM_LIKELY(isDistributive(typeId))) {
     1302                        G[e] = std::max(G[e], index);
     1303                    } else {
    16741304                        remove_edge(e, G);
    16751305                    }
     
    17131343                }
    17141344            } else if (requiredOperands(typeId) == n) {
    1715                 bool used[n];
    1716                 std::fill_n(used, n, false);
     1345                bool used[n] = { false };
    17171346                for (auto e : make_iterator_range(in_edges(u, G))) {
    17181347                    const auto i = G[e];
     
    17711400
    17721401    /** ------------------------------------------------------------------------------------------------------------- *
    1773      * @brief removeVertex
    1774      ** ------------------------------------------------------------------------------------------------------------- */
    1775     void removeVertex(const Vertex u) { assert (isLive(u));
    1776         setDead(u);
    1777         Vertex D[in_degree(u, G)];
    1778         unsigned n = 0;
    1779         for (const auto e : make_iterator_range(in_edges(u, G))) {
    1780             const auto v = source(e, G);
    1781             if (LLVM_UNLIKELY(out_degree(v, G) == 1)) {
    1782                 D[n++] = v;
    1783             }
    1784         }
    1785         while (LLVM_UNLIKELY(n != 0)) {
    1786             removeVertex(D[--n]);
    1787         }
    1788         clear_vertex(u, G);
    1789         reprocessGraph = true;
    1790     }
    1791 
    1792     /** ------------------------------------------------------------------------------------------------------------- *
    17931402     * @brief consolidate
    17941403     ** ------------------------------------------------------------------------------------------------------------- */
     
    17971406        assert (hasValidOperandIndicies(u));
    17981407        const auto f = V.insert(u);
    1799         if (LLVM_UNLIKELY(f.second)) {           
     1408        if (LLVM_UNLIKELY(f.second)) {
    18001409            return u;
    18011410        }
    18021411        const auto v = *f.first;
     1412        assert (IdentityComparator(G)(u, v));
     1413        replaceVertex(u, v);
     1414        return v;
     1415    }
     1416
     1417    /** ------------------------------------------------------------------------------------------------------------- *
     1418     * @brief replaceVertex
     1419     ** ------------------------------------------------------------------------------------------------------------- */
     1420    void replaceVertex(const Vertex u, const Vertex v) {
    18031421        assert (u != v);
    1804         assert (isLive(v));
    1805         const PabloAST * expr = getValue(u);
     1422        assert (isLive(u) && isLive(v));
     1423        const PabloAST * const expr = getValue(u);
    18061424        if (expr) {
    18071425            assert (!isRegenerable(getType(u)));
     
    18161434        }
    18171435        removeVertex(u);
    1818         return v;
     1436    }
     1437
     1438    /** ------------------------------------------------------------------------------------------------------------- *
     1439     * @brief removeVertex
     1440     ** ------------------------------------------------------------------------------------------------------------- */
     1441    void removeVertex(const Vertex u) {
     1442        assert (isLive(u));
     1443        setDead(u);
     1444        clear_vertex(u, G);       
    18191445    }
    18201446
     
    19071533    void setDead(const Vertex u) {
    19081534        setState(u, State::Dead);
     1535        setValue(u, nullptr);
    19091536    }
    19101537
     
    19181545
    19191546    void setModified(const Vertex u) {
     1547        assert(!isImmutable(getType(u)));
    19201548        setState(u, State::Modified);
    19211549    }
     
    19381566    void setLastUsageTime(const Vertex u, const UsageTime time) {
    19391567        assert (u < num_vertices(G));
    1940 
    1941 //        errs() << "   " << u << " ";
    1942 //        PabloPrinter::print(getValue(u), errs());
    1943 //        errs() << " @ " << time << "\n";
    1944 
    1945 
    19461568        std::get<3>(G[u]) = time;
    19471569    }
     
    19851607    }
    19861608
    1987     static bool isStreamOperation(const TypeId typeId) {
    1988         switch (typeId) {
    1989             case TypeId::Advance:
    1990             case TypeId::ScanThru:
    1991             case TypeId::AdvanceThenScanThru:
    1992 //            case TypeId::ScanTo:
    1993 //            case TypeId::AdvanceThenScanTo:
    1994             case TypeId::Lookahead:
    1995             case TypeId::MatchStar:
    1996             case TypeId::InFile:
    1997             case TypeId::AtEOF:
    1998                 return true;
    1999             default:
    2000                 return false;
    2001         }
    2002     }
    2003 
    20041609    static TypeId oppositeTypeId(const TypeId typeId) {
    20051610        assert (isDistributive(typeId));
     
    20111616    }
    20121617
    2013 private:
     1618    Vertex getNegatedLiteral(const Vertex u) const {
     1619        assert (getType(u) == TypeId::Not);
     1620        assert (in_degree(u, G) == 1);
     1621        return first_source(in_edges(u, G));
     1622    }
     1623
     1624    Vertex removeNegation(const Vertex u) const {
     1625        return getType(u) == TypeId::Not ? getNegatedLiteral(u) : u;
     1626    }
     1627
     1628    /** ------------------------------------------------------------------------------------------------------------- *
     1629     * @brief getNegationOf
     1630     ** ------------------------------------------------------------------------------------------------------------- */
     1631    Vertex getNegationOf(const Vertex u) {
     1632        if (getType(u) == TypeId::Not) {
     1633            return getNegatedLiteral(u);
     1634        } else {
     1635            for (const auto e : make_iterator_range(out_edges(u, G))) {
     1636                const auto v = target(e, G);
     1637                if (getType(v) == TypeId::Not) {
     1638                    return v;
     1639                }
     1640            }
     1641            const auto v = makeVertex(TypeId::Not);
     1642            add_edge(u, v, 0, G);
     1643            return v;
     1644        }
     1645    }
    20141646
    20151647    struct IdentityHash {
    20161648        size_t operator()(const Vertex u) const {
    20171649            using value_of = std::underlying_type<TypeId>::type;
    2018 //            InEdgeIterator begin, end;
    2019 //            std::tie(begin, end) = in_edges(u, G);
    2020 //            assert (std::is_sorted(begin, end));
    2021             const auto n = in_degree(u, G);
    2022             Vertex operands[n];
    2023             unsigned i = 0;
    2024             for (auto e : make_iterator_range(in_edges(u, G))) {
    2025                 operands[i++] = source(e, G);
    2026             }
    2027             std::sort(operands, operands + n);
     1650            #ifndef NDEBUG
     1651            InEdgeIterator begin, end;
     1652            std::tie(begin, end) = in_edges(u, G);
     1653            assert (std::is_sorted(begin, end, [this](const Edge ei, const Edge ej) {
     1654                return source(ei, G) <= source(ej, G);
     1655            }));
     1656            #endif
    20281657            size_t h = 0;
    20291658            boost::hash_combine(h, static_cast<value_of>(PassContainer::getType(u, G)));
    2030             for (unsigned j = 0; j < n; ++j) {
    2031                 boost::hash_combine(h, operands[j]);
    2032             }
    2033 //            for (auto e : make_iterator_range(in_edges(u, G))) {
    2034 //                boost::hash_combine(h, source(e, G));
    2035 //            }
     1659            for (auto e : make_iterator_range(in_edges(u, G))) {
     1660                boost::hash_combine(h, source(e, G));
     1661            }
    20361662            return h;
    20371663        }
     
    20481674                if (LLVM_UNLIKELY(n == 0)) {
    20491675                    assert (isNullary(typeId) && in_degree(v, G) == 0);
    2050                     if (LLVM_UNLIKELY(isLiteral(typeId))) {
    2051                         assert (getValue(u, G) && getValue(v, G));
    2052                         return getValue(u, G) == getValue(v, G);
    2053                     }
    2054                     return true;
     1676                    return getValue(u, G) == getValue(v, G);
    20551677                }
    20561678                if (in_degree(v, G) == n) {
     
    20921714private:
    20931715
    2094     bool reprocessGraph;
     1716    bool compactedGraph;
    20951717
    20961718    Graph G;
     
    21151737    PabloVerifier::verify(kernel, "post-distributive-pass");
    21161738    #endif
    2117 
    2118 //    errs() << "-----------------------------------------------\n"
    2119 //              "BEFORE SIMPLIFICATION:\n"
    2120 //              "-----------------------------------------------\n";
    2121 //    PabloPrinter::print(kernel, errs());
    2122 
    21231739    Simplifier::optimize(kernel);
    2124 
    2125 //    errs() << "-----------------------------------------------\n"
    2126 //              "AFTER SIMPLIFICATION:\n"
    2127 //              "-----------------------------------------------\n";
    2128 //    PabloPrinter::print(kernel, errs());
    2129 
    21301740    return true;
    21311741}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r5536 r5607  
    203203        assert ("block has a branch but the expression and variable tables were not supplied" && et && vt);
    204204        variables.addNonZero(br->getCondition());
    205         if (LLVM_UNLIKELY(isa<While>(br))) {
    206             for (Var * var : cast<While>(br)->getEscaped()) {
    207                 variables.put(var, var);
    208             }
     205        for (Var * var : br->getEscaped()) {
     206            variables.put(var, var);
    209207        }
    210208    }
     
    255253
    256254            if (LLVM_LIKELY(isa<If>(br))) {
    257                 if (LLVM_UNLIKELY(variables.isNonZero(br->getCondition()))) {
     255                if (LLVM_UNLIKELY(variables.isNonZero(cond))) {
    258256                    stmt = flatten(br);
    259257                    continue;
Note: See TracChangeset for help on using the changeset viewer.