Ignore:
Timestamp:
Aug 22, 2015, 1:53:05 PM (4 years ago)
Author:
nmedfort
Message:

More work on the boolean reassociation pass.

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

Legend:

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

    r4736 r4738  
    2121}
    2222
     23/** ------------------------------------------------------------------------------------------------------------- *
     24 * @brief scan
     25 ** ------------------------------------------------------------------------------------------------------------- */
    2326void BooleanReassociationPass::scan(PabloFunction & function) {
    2427    Terminals terminals;
     
    2932}
    3033
     34/** ------------------------------------------------------------------------------------------------------------- *
     35 * @brief is_power_of_2
     36 * @param n an integer
     37 ** ------------------------------------------------------------------------------------------------------------- */
     38static inline bool is_power_of_2(const size_t n) {
     39    return ((n & (n - 1)) == 0);
     40}
     41
     42/** ------------------------------------------------------------------------------------------------------------- *
     43 * @brief log2_plus_one
     44 ** ------------------------------------------------------------------------------------------------------------- */
     45static inline size_t ceil_log2(const size_t n) {
     46    return std::log2<size_t>(n) + (is_power_of_2(n) ? 1 : 0);
     47}
     48
     49/** ------------------------------------------------------------------------------------------------------------- *
     50 * @brief scan
     51 ** ------------------------------------------------------------------------------------------------------------- */
    3152void BooleanReassociationPass::scan(PabloBlock & block, Terminals && terminals) {
    3253
     
    3455    using Vertex = Graph::vertex_descriptor;
    3556    using Map = std::unordered_map<PabloAST *, Vertex>;
    36     using Queue = std::queue<Vertex>;
     57    using VertexQueue = std::queue<Vertex>;
     58    using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
    3759
    3860    for (Statement * stmt : block) {
     
    79101                    f = M.insert(std::make_pair(var, v)).first;
    80102                    if ((isa<And>(var) || isa<Or>(var) || isa<Xor>(var))) {
    81                         Queue Q;
     103                        VertexQueue Q;
    82104                        // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
    83105                        for (Statement * stmt = cast<Statement>(var); ;) {
     
    111133        std::vector<unsigned> component(num_vertices(G));
    112134
    113         for (unsigned i = 0; ;) {
     135        // unsigned i = 0;
     136
     137        for (;;) {
    114138
    115139            // Mark which computation component these vertices are in based on their topological (occurence) order.
     
    117141            for (auto u : ordering) {
    118142                unsigned id = 0;
    119                 if (out_degree(u, G) == 0) {
     143                // If this one of our original terminals or a sink in G, it is the root of a new component.
     144                if (u < terminals.size() || out_degree(u, G) == 0) {
    120145                    id = ++count;
    121146                } else {
     
    130155            if (count > 1) {
    131156
    132                 if (i++ == 0) {
    133 
    134                     out << "digraph G_" << i << " {\n";
    135                     unsigned i = 0;
    136                     for (auto u : ordering) {
    137                         out << "u" << u << " [label=\"";
    138                         out << i++ << " : ";
    139                         PabloPrinter::print(G[u], out);
    140                         out << " (" << component[u] << ')';
    141                         out << "\"];\n";
    142                     }
    143                     for (auto e : make_iterator_range(edges(G))) {
    144                         out << "u" << source(e, G) << " -> u" << target(e, G) << ";\n";
    145                     }
    146                     out << "}\n";
    147                     out.flush();
    148 
    149                     out << "*************************************************\n";
    150 
    151                 }
    152 
    153                 // Cut the graph wherever a computation is crosses a component
    154                 std::queue<std::pair<Vertex, Vertex>> Q;
     157//                if (i++ == 0) {
     158
     159//                    out << "digraph G_" << i << " {\n";
     160//                    unsigned i = 0;
     161//                    for (auto u : ordering) {
     162//                        out << "u" << u << " [label=\"";
     163//                        out << i++ << " : ";
     164//                        PabloPrinter::print(G[u], out);
     165//                        out << " (" << component[u] << ')';
     166//                        out << "\"];\n";
     167//                    }
     168//                    for (auto e : make_iterator_range(edges(G))) {
     169//                        out << "u" << source(e, G) << " -> u" << target(e, G) << ";\n";
     170//                    }
     171//                    out << "}\n";
     172//                    out.flush();
     173
     174//                    out << "*************************************************\n";
     175
     176//                }
     177
     178                // Cut the graph wherever a computation crosses a component
     179                EdgeQueue Q;
    155180                graph_traits<Graph>::edge_iterator ei, ei_end;
    156181
     
    176201
    177202                    // The vertex belonging to a component with a greater number must come "earlier"
    178                     // in the program. Thus it must be computed first.
     203                    // in the program. By replicating it, this ensures it's computed as an output of
     204                    // one component and used as an input of another.
    179205
    180206                    if (component[u] < component[v]) {
     
    182208                    }
    183209
    184                     out << " -- replicating ";
    185                     PabloPrinter::print(G[u], out);
    186                     out << " for component " << component[v] << '\n';
    187                     out.flush();
     210//                    out << " -- replicating ";
     211//                    PabloPrinter::print(G[u], out);
     212//                    out << " for component " << component[v] << '\n';
     213//                    out.flush();
    188214
    189215                    // Replicate u and fix the ordering and component vectors to reflect the change in G.
     
    211237                }
    212238
    213                 out << "*************************************************\n";
     239//                out << "*************************************************\n";
    214240
    215241                continue; // outer for loop
     
    233259        out.flush();
    234260
    235 
    236         // Determine the source variables in this portion of the AST
    237         flat_set<PabloAST *> variables;
    238 
    239         for (auto u : make_iterator_range(vertices(G))) {
     261        // Scan through the graph in reverse order so that we find all subexpressions first
     262        for (auto ui = ordering.rbegin(), ui_end = ordering.rend(); ui != ui_end; ++ui) {
     263            const Vertex u = *ui;
     264            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     265
     266                PabloAST * expr = G[u];
     267
     268
     269                std::array<Vertex, 3> root;
     270                unsigned count = 0;
     271
     272                if (isa<And>(expr) || isa<Or>(expr) || isa<Xor>(expr)) {
     273                    root[count++] = u;
     274                } else {
     275                    for (auto e : make_iterator_range(in_edges(u, G))) {
     276                        root[count++] = source(e, G);
     277                    }
     278                }
     279
     280                for (unsigned i = 0; i != count; ++i) {
     281                    // While we're collecting our variable set V, keep track of the maximum path length L.
     282                    // If L == ceil(log2(|V|)), then this portion of the AST is already optimal.
     283
     284                    flat_map<Vertex, unsigned> L;
     285                    flat_set<PabloAST *> V;
     286                    VertexQueue Q;
     287
     288                    Vertex v = root[i];
     289                    unsigned maxPathLength = 0;
     290                    L.emplace(v, 0);
     291                    for (;;) {
     292                        if (in_degree(v, G) == 0) {
     293                            V.insert(G[v]);
     294                        } else {
     295                            const auto l = L[v] + 1;
     296                            maxPathLength = std::max(maxPathLength, l);
     297                            for (auto e : make_iterator_range(in_edges(v, G))) {
     298                                const Vertex w = source(e, G);
     299                                auto f = L.find(w);
     300                                if (LLVM_LIKELY(f == L.end())) {
     301                                    L.emplace(w, l);
     302                                } else {
     303                                    f->second = std::max(f->second, l);
     304                                }
     305                                Q.push(w);
     306                            }
     307                        }
     308                        if (Q.empty()) {
     309                            break;
     310                        }
     311                        v = Q.front();
     312                        Q.pop();
     313                    }
     314
     315                    // Should we optimize this portion of the AST?
     316                    if (maxPathLength != ceil_log2(V.size())) {
     317
     318
     319
     320                    }
     321
     322
     323                }
     324
     325
     326
     327
     328
     329            }
     330        }
     331
     332        // if (u < terminals.size() || out_degree(u, G) == 0) {
     333
     334        for (auto e : make_iterator_range(edges(G))) {
     335            Vertex u = target(e, G);
     336            Vertex v = source(e, G);
     337            if (u >= terminals.size() && out_degree(v, G) != 0 && G[u]->getClassTypeId() != G[v]->getClassTypeId()) {
     338                throw std::runtime_error("Illegal graph generated!");
     339            }
     340        }
     341
     342        // Determine the source variables of the next "layer" of the AST
     343        flat_set<Statement *> nextSet;
     344        for (auto u : ordering) {
    240345            if (in_degree(u, G) == 0) {
    241                 variables.insert(G[u]);
    242             }
    243         }
    244 
    245         terminals.clear();
    246         for (PabloAST * var : variables) {
    247             if (isa<Statement>(var) && cast<Statement>(var)->getParent() == &block) {
    248                 terminals.push_back(cast<Statement>(var));
    249             }
    250         }
    251 
    252         if (terminals.empty()) {
     346                PabloAST * const var = G[u];
     347                if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) {
     348                    nextSet.insert(cast<Statement>(var));
     349                }
     350            } else if (out_degree(u, G) == 0) { // an input may also be the output of some subgraph of G. We don't need to reevaluate it.
     351                PabloAST * const var = G[u];
     352                if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) {
     353                    nextSet.erase(cast<Statement>(var));
     354                }
     355            }
     356        }
     357
     358        if (nextSet.empty()) {
    253359            break;
    254360        }
     361
     362        terminals.assign(nextSet.begin(), nextSet.end());
    255363
    256364        out << "-------------------------------------------------\n";
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4736 r4738  
    11031103}
    11041104
    1105 /** ------------------------------------------------------------------------------------------------------------- *
    1106  * @brief reassociate
    1107  ** ------------------------------------------------------------------------------------------------------------- */
    1108 inline void AutoMultiplexing::reassociate(PabloBuilder & builder, PabloAST * const demuxed[], const unsigned n) const {
    1109     using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *>;
    1110     using Map = std::unordered_map<PabloAST *, Graph::vertex_descriptor>;
    1111     using Queue = std::queue<Graph::vertex_descriptor>;
    1112     using Or = pablo::Or;
    1113     using And = pablo::And;
    1114 
    1115 
    1116     flat_set<PabloAST *> initial_vars;
    1117 
    1118 
    1119     std::queue<And *> andQ;
    1120     for (unsigned i = 0; i != n; ++i) {
    1121         for (PabloAST * user : demuxed[i]->users()) {
    1122             if (isa<And>(user)) {
    1123                 andQ.push(cast<And>(user));
    1124             } else if (isa<Or>(user)) {
    1125                 initial_vars.insert(demuxed[i]);
    1126             }
    1127         }
    1128     }
    1129 
    1130     while (!andQ.empty()) {
    1131         And * inst = andQ.front(); andQ.pop();
    1132         for (PabloAST * user : inst->users()) {
    1133             if (isa<And>(user)) {
    1134                 andQ.push(cast<And>(user));
    1135             } else if (isa<Or>(user)) {
    1136                 initial_vars.insert(inst);
    1137             }
    1138         }
    1139     }
    1140 
    1141     Graph G;
    1142     Map M;
    1143     Queue Q;
    1144 
    1145     // First insert the demuxed variables as our initial sources (as vertices 0 ... n-1)
    1146     for (PabloAST * inst : initial_vars) {
    1147         M.insert(std::make_pair(inst, add_vertex(inst, G)));
    1148     }
    1149 
    1150     // Now add in the users of those demuxed variables
    1151     for (PabloAST * inst : initial_vars) {
    1152         const auto i = M[inst];
    1153         for (PabloAST * user : inst->users()) {
    1154             const auto f = M.find(user);
    1155             if (LLVM_LIKELY(f == M.end())) {
    1156                 const auto j = add_vertex(user, G);
    1157                 M.insert(std::make_pair(user, j));
    1158                 add_edge(i, j, G);
    1159                 if (isa<Or>(user)) {
    1160                     Q.push(j);
    1161                 }
    1162             } else {
    1163                 add_edge(i, f->second, G);
    1164             }
    1165         }
    1166     }
    1167 
    1168     // Now scan through the graph to locate any disjunctions and the final outputs
    1169     while (!Q.empty()) {
    1170         const auto u = Q.front(); Q.pop();
    1171         Or * expr = cast<Or>(G[u]);
    1172         for (unsigned i = 0; i != 2; ++i) {
    1173             PabloAST * op = expr->getOperand(i);
    1174             const auto f = M.find(op);
    1175             if (LLVM_UNLIKELY(f == M.end())) {
    1176                 const auto v = add_vertex(op, G);
    1177                 M.insert(std::make_pair(op, v));
    1178                 add_edge(v, u, G);
    1179                 if (isa<Or>(op)) {
    1180                     Q.push(v);
    1181                 }
    1182             }
    1183         }
    1184         for (PabloAST * user : expr->users()) {
    1185             const auto f = M.find(user);
    1186             if (LLVM_UNLIKELY(f == M.end())) {
    1187                 const auto v = add_vertex(user, G);
    1188                 M.insert(std::make_pair(user, v));
    1189                 add_edge(u, v, G);
    1190                 if (isa<Or>(user)) {
    1191                     Q.push(v);
    1192                 }
    1193             } else {
    1194                 add_edge(u, f->second, G);
    1195             }
    1196         }
    1197     }
    1198 
    1199     // Clean up the graph to remove any non-disjunctions and their dependencies
    1200     for (auto u : make_iterator_range(vertices(G))) {
    1201         if (in_degree(u, G) == 0 || isa<Or>(G[u])) {
    1202             continue;
    1203         }
    1204         clear_in_edges(u, G);
    1205         for (;;) {
    1206             for (auto e : make_iterator_range(out_edges(u, G))) {
    1207                 Q.push(target(e, G));
    1208             }
    1209             clear_out_edges(u, G);
    1210             if (Q.empty()) {
    1211                 break;
    1212             }
    1213             u = Q.front(); Q.pop();
    1214         }
    1215     }
    1216 
    1217     // Now determine the number of source variables
    1218     unsigned m = 0;
    1219     for (auto u : make_iterator_range(vertices(G))) {
    1220         if (in_degree(u, G) == 0 && out_degree(u, G) > 0) {
    1221             ++m;
    1222         }
    1223     }
    1224 
    1225 
    1226     circular_buffer<PabloAST *> R(m);
    1227     // And then which variables required to compute each disjunction
    1228     for (const auto u : make_iterator_range(vertices(G))) {
    1229         if (out_degree(u, G) == 0 && in_degree(u, G) > 0) {
    1230 
    1231             std::vector<bool> visited(num_vertices(G), false);
    1232             flat_set<Graph::vertex_descriptor> variables;
    1233             for (auto v = u; ; ) {
    1234                 if (in_degree(v, G) == 0) {
    1235                     variables.insert(v);
    1236                 } else {
    1237                     for (auto e : make_iterator_range(in_edges(v, G))) {
    1238                         const auto w = source(e, G);
    1239                         if (!visited[w]) {
    1240                             Q.push(w);
    1241                             visited[w] = true;
    1242                         }
    1243                     }
    1244                 }
    1245                 if (Q.empty()) {
    1246                     break;
    1247                 }
    1248                 v = Q.front(); Q.pop();
    1249             }
    1250             if (variables.size() > 3) {
    1251                 unsigned i = 0;
    1252                 for (auto j : variables) {
    1253                     for (; i < j; ++i) {
    1254                         R.push_back(builder.createZeroes());
    1255                     }
    1256                     R.push_back(G[j]);
    1257                 }
    1258                 for (; i < m; ++i) {
    1259                     R.push_back(builder.createZeroes());
    1260                 }
    1261                 while (R.size() > 1) {
    1262                     PabloAST * e1 = R.front(); R.pop_front();
    1263                     PabloAST * e2 = R.front(); R.pop_front();
    1264                     R.push_back(builder.createOr(e1, e2));
    1265                 }
    1266                 Statement * stmt = cast<Statement>(G[u]);
    1267                 stmt->replaceAllUsesWith(R.front());
    1268                 R.clear();
    1269             }
    1270         }
    1271     }
    1272 
    1273 }
    1274 
    1275 
    12761105} // end of namespace pablo
    12771106
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4736 r4738  
    4848    void applySubsetConstraints();
    4949    void multiplexSelectedIndependentSets();
    50     void reassociate(PabloBuilder & builder, PabloAST * const demuxed[], const unsigned n) const;
    5150    void topologicalSort(PabloBlock & entry) const;
    5251    inline AutoMultiplexing()
Note: See TracChangeset for help on using the changeset viewer.