Changeset 5571


Ignore:
Timestamp:
Jul 18, 2017, 1:39:43 PM (5 months ago)
Author:
nmedfort
Message:

DistributionPass? bug fix and code clean up

File:
1 edited

Legend:

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

    r5570 r5571  
    3131#include <set>
    3232#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
    4333
    4434using namespace boost;
     
    114104protected:
    115105
    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 
    244 protected:
    245 
    246106    /** ------------------------------------------------------------------------------------------------------------- *
    247107     * @brief readAST
     
    269129            const auto typeId = getType(u);
    270130
    271             if (isDead(u) || isRegenerable(typeId)) {
     131            // There are two main reasons to ignore a statement: (1) it's dead or regenerable and thus not of interest,
     132            // and (2), the value in G strictly dominates the statement. Typically, if two expressions are equivalent,
     133            // they're in disjoint nested scopes. When neither dominates the other, this algorithm updates G as it
     134            // processes the statements. However, if one dominates the other, G must refer to the dominating statement
     135            // to avoid producing an illegal AST.
     136
     137            if (LLVM_LIKELY(isDead(u) || isRegenerable(typeId)) || LLVM_UNLIKELY(strictly_dominates(getValue(u), stmt))) {
    272138                continue;
    273139            }
    274 
    275             #ifdef PRINT_DEBUG
    276             errs() << u << ") ";
    277             PabloPrinter::print(stmt, errs());
    278             errs() << "\n";
    279             #endif
    280140
    281141            assert (isLive(u));
     
    330190
    331191        assert (isLive(u));
     192
    332193        const TypeId typeId = getType(u);
     194
    333195        PabloAST * value = isModified(u) ? nullptr : getValue(u);
    334196        if (LLVM_LIKELY(!dominates(value, stmt))) {
    335197
    336             const auto n = in_degree(u, G);           
    337 
    338             #ifdef PRINT_DEBUG
    339             errs() << "   making " << u << "  " << n << "  " << (int)typeId << "\n";
    340             #endif
     198            assert (isRegenerable(typeId));
    341199
    342200            for (auto e : make_iterator_range(in_edges(u, G))) {
     
    349207            if (LLVM_LIKELY(isAssociative(typeId))) {
    350208
     209                const auto n = in_degree(u, G);
     210
    351211                assert (n >= 2);
     212
     213                // Suppose we try to minimize the pairwise difference in last usage time,
     214                // taking into account that we can use negations of variables when they've
     215                // been used more recently. Take note to update the correct vertex if an
     216                // ANDC can be used instead.
    352217
    353218                Vertex input[n];
     
    380245                }
    381246
    382             } else if (n == 1) {
    383                 assert (typeId == TypeId::Not);
     247            } else if (typeId == TypeId::Not) {
     248                assert (in_degree(u, G) == 1);
    384249                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 
    411250            } else {
    412251                assert (isConstant(typeId));
     252                assert (in_degree(u, G) == 0);
    413253                if (typeId == TypeId::Zeroes) {
    414254                    value = entry->createZeroes();
     
    421261            setUnmodified(u);
    422262        }
     263
    423264        // negations inherit the last usage time from their operand
    424265        if (LLVM_UNLIKELY(typeId == TypeId::Not)) {
     
    443284            goto repeat;
    444285        }
    445         transitiveReduction();
    446286        factorizeGraph();
    447287        return modified;
     
    554394            if (LLVM_UNLIKELY(isImmutable(typeId))) {
    555395                continue;
    556             } else if (LLVM_UNLIKELY(out_degree(u, G) == 0)) {
    557                 removeVertex(u);
    558                 continue;
    559396            }
    560397
    561398            assert (hasValidOperandIndicies(u));
     399
     400            assert (out_degree(u, G) > 0);
    562401
    563402            if (LLVM_UNLIKELY(isConstant(typeId))) {
     
    593432
    594433        if (LLVM_UNLIKELY(in_degree(u, G) == 0)) {
    595             #ifdef PRINT_DEBUG
    596             errs() << "nullary associative " << u << "\n";
    597             #endif
    598434            setModified(u);
    599435            setType(u, TypeId::Zeroes);
     
    605441                addEdge(v, target(e, G), G[e]);
    606442            }
    607             #ifdef PRINT_DEBUG
    608             errs() << "unary associative " << v << " -> " << u << "\n";
    609             #endif
    610443            removeVertex(u);
    611444            return true;
     
    623456                    setModified(v);
    624457                    removed[n++] = v;
    625                     #ifdef PRINT_DEBUG
    626                     errs() << "transitive associative " << v << " -> " << u << "\n";
    627                     #endif
    628458                }
    629459            }
     
    649479                }
    650480                if (LLVM_UNLIKELY(count != 0)) {
    651                     #ifdef PRINT_DEBUG
    652                     errs() << "xor canonicalization (a) " << u << "\n";
    653                     #endif
    654481                    for (unsigned i = 0; i < count; ++i) {
    655482                        const auto v = negation[i];
     
    686513        if (LLVM_UNLIKELY(negatedTypeId == TypeId::Not)) { // ¬¬A = A
    687514            const auto w = first_source(in_edges(v, G));
    688             #ifdef PRINT_DEBUG
    689             errs() << "double negation " << u << " -> " << w << "\n";
    690             #endif
    691515            for (const auto e : make_iterator_range(out_edges(u, G))) {
    692516                const auto v = target(e, G);
     
    698522        } else if (LLVM_UNLIKELY(negatedTypeId == TypeId::Xor)) {
    699523            // Canonicalize xor operations: ¬(A ⊕ B) = (A ⊕ B ⊕ 1)
    700             #ifdef PRINT_DEBUG
    701             errs() << "xor canonicalization (n) " << u << "\n";
    702             #endif
    703524            setModified(u);
    704525            setType(u, TypeId::Xor);
     
    738559            for (unsigned i = 0; i < n; ++i) {
    739560                const auto v = A[i];
    740                 #ifdef PRINT_DEBUG
    741                 errs() << "de morgan's expansion " << v << " -> " << u << "\n";
    742                 #endif
    743561                assert (edge(v, u, G).second);
    744562                assert (getType(v) == TypeId::Not);
     
    778596            if (innerTypeId == TypeId::Not) {
    779597                const auto w = first_source(in_edges(v, G));
    780                 assert ("G is cyclic!" && (w != v));
    781598                assert (isLive(w));
    782599                for (const auto ej : make_iterator_range(in_edges(u, G))) {
    783600                    if (LLVM_UNLIKELY(source(ej, G) == w)) {
    784601                        const auto complementTypeId = (typeId == TypeId::And) ? TypeId::Zeroes : TypeId::Ones;
    785                         #ifdef PRINT_DEBUG
    786                         errs() << "complement (" << (int)complementTypeId << ") " << u << "\n";
    787                         #endif
    788602                        setModified(u);
    789603                        setType(u, complementTypeId);
     
    801615            for (;;) {
    802616                const auto v = A[--n];
    803                 #ifdef PRINT_DEBUG
    804                 errs() << "absorbing " << v  << "," << u << "\n";
    805                 #endif
    806617                assert (edge(v, u, G).second);
    807618                remove_edge(v, u, G);
     
    857668                // Ones             And              identity
    858669                if (isIdentityRelation(typeId, targetTypeId)) {
    859                     #ifdef PRINT_DEBUG
    860                     errs() << "identity (" << (int)(typeId) << ") " << v << " >> " << u << "\n";
    861                     #endif
    862                     modification[l - ++n] = v;
     670                    modification[l - ++n] = v; // fill in from the end
    863671                } else { // annulment
    864                     #ifdef PRINT_DEBUG
    865                     errs() << "annulment (" << (int)(typeId) << ") " << u << " >> " << v << "\n";
    866                     #endif
    867672                    setType(v, typeId);
    868673                    modification[m++] = v;
     
    870675            } else if (LLVM_UNLIKELY(targetTypeId == TypeId::Not)) {
    871676                const auto negatedTypeId = (typeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes;
    872                 #ifdef PRINT_DEBUG
    873                 errs() << "constant negation (" << (int)typeId << ") " << u << "\n";
    874                 #endif
    875677                setType(u, negatedTypeId);
    876678                modification[m++] = v;
    877679            } else if (LLVM_UNLIKELY(isStreamOperation(typeId))) {
    878680                if (LLVM_LIKELY(typeId == TypeId::Zeroes)) {
    879                     #ifdef PRINT_DEBUG
    880                     errs() << "zero propagation (" << (int)(typeId) << ") " << u << " >> " << v << "\n";
    881                     #endif
    882681                    setType(v, TypeId::Zeroes);
    883682                    modification[m++] = v;
     
    919718            clear_in_edges(v, G);
    920719            // 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.
     720            // in a pathological case. Instead rely on the fact v will be processed eventually.
    923721        }
    924722
     
    971769                const auto x = makeVertex(outerTypeId);
    972770                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
    991771
    992772                for (const Vertex i : sources) {
     
    1122902
    1123903    /** ------------------------------------------------------------------------------------------------------------- *
    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     /** ------------------------------------------------------------------------------------------------------------- *
    1180904     * @brief factorizeGraph
    1181905     *
     
    1211935                for (;;) {
    1212936
    1213                     #ifdef PRINT_DEBUG
    1214                     errs() << "--------------------------------------------\n";
    1215                     #endif
    1216 
    1217937                    auto factors = makeIndependent(enumerateBicliques(groups[i], G, 2, minSize), 1);
    1218938                    if (factors.empty()) {
     
    1225945                        auto & targets = std::get<0>(factor);
    1226946                        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
    1240947
    1241948                        // Check whether one of the targets is the factorization
     
    1267974                            assert (hasValidOperandIndicies(x));
    1268975                        }
    1269                         #ifdef PRINT_DEBUG
    1270                         errs() << x << '\n';
    1271                         #endif
    1272976
    1273977                        // Remove the biclique between the source and target vertices
     
    15461250    }
    15471251
    1548     #if !defined(NDEBUG) || defined(PRINT_DEBUG)
     1252    #ifndef NDEBUG
    15491253    /** ------------------------------------------------------------------------------------------------------------- *
    15501254     * @brief hasValidOperandIndicies
     
    16251329                llvm_unreachable("impossible");
    16261330            default:
     1331                assert (!isAssociative(typeId) && !isNullary(typeId));
    16271332                return 2;
    16281333        }
    16291334    }
     1335
     1336    static bool isNullary(const TypeId typeId) {
     1337        return isConstant(typeId) || isLiteral(typeId);
     1338    }
    16301339    #endif
    16311340
     
    16331342     * @brief removeVertex
    16341343     ** ------------------------------------------------------------------------------------------------------------- */
    1635     void removeVertex(const Vertex u) {
    1636         #ifdef PRINT_DEBUG
    1637         errs() << "removing " << u << "\n";
    1638         #endif
    1639         assert (isLive(u));
     1344    void removeVertex(const Vertex u) { assert (isLive(u));
    16401345        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         }
    16471346        clear_vertex(u, G);
    16481347    }
     
    16511350     * @brief remapVertex
    16521351     ** ------------------------------------------------------------------------------------------------------------- */
    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)) {
     1352    void remapVertex(const Vertex u, const Vertex v) { assert (u != v);
     1353        const PabloAST * expr = getValue(u);
     1354        if (expr) {
    16611355            auto f = M.find(expr);
    1662             assert (f->second == u);
     1356            assert (f != M.end() && f->second == u);
    16631357            f->second = v;
    1664         }
    1665         for (auto e : make_iterator_range(out_edges(u, G))) {
     1358            setValue(v, nullptr);
     1359        }
     1360        for (const auto e : make_iterator_range(out_edges(u, G))) {
    16661361            addEdge(v, target(e, G), G[e]);
    16671362        }
     
    18201515                return isLiteral(typeId);
    18211516        }
    1822     }
    1823 
    1824     static bool isNullary(const TypeId typeId) {
    1825         return isConstant(typeId) || isLiteral(typeId);
    18261517    }
    18271518
     
    18521543    }
    18531544
    1854     bool inCurrentScope(const PabloAST * const expr, const PabloBlock * const scope) {
    1855         return isa<Statement>(expr) && cast<Statement>(expr)->getParent() == scope;
    1856     }
    1857 
    18581545private:
    18591546
     
    18721559 ** ------------------------------------------------------------------------------------------------------------- */
    18731560bool DistributivePass::optimize(PabloKernel * const kernel) {
    1874 
    18751561    PassContainer C;
    18761562    C.run(kernel);
Note: See TracChangeset for help on using the changeset viewer.