Ignore:
Timestamp:
Aug 21, 2015, 4:12:09 PM (4 years ago)
Author:
nmedfort
Message:

Initial stages of a simple boolean equation reassociation pass.

File:
1 edited

Legend:

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

    r4728 r4736  
    160160        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
    161161
     162        BooleanReassociationPass::optimize(function);
     163
    162164        RECORD_TIMESTAMP(start_topological_sort);
    163165        am.topologicalSort(function.getEntryBlock());
     
    165167        LOG("TopologicalSort (1):     " << (end_topological_sort - start_topological_sort));
    166168
    167         BDDMinimizationPass::optimize(function, true);
     169        BDDMinimizationPass::optimize(function, false);
    168170    }
    169171
    170172    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
    171 
    172173    return multiplex;
    173174}
     
    645646    }
    646647
     648    assert (S.size() > 0);
     649
    647650    auto remainingVerticies = num_vertices(mConstraintGraph) - S.size();
    648651
     
    653656        bool noNewElements = true;
    654657        do {
     658            assert (S.size() > 0);
    655659            // Randomly choose a vertex in S and discard it.
    656660            const auto i = S.begin() + IntDistribution(0, S.size() - 1)(rng);
    657             const ConstraintVertex u = *i;
    658             S.erase(i);
    659             --remainingVerticies;
     661            assert (i != S.end());
     662            const ConstraintVertex u = *i;           
     663            S.erase(i);           
    660664
    661665            for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
     
    663667                if ((--D[v]) == 0) {
    664668                    S.push_back(v);
     669                    --remainingVerticies;
    665670                    noNewElements = false;
    666671                }
     
    851856            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
    852857            // For each member of a "set vertex" ...
    853             std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
    854             for (; ei != ei_end; ++ei) {
    855                 const auto s = source(*ei, mMultiplexSetGraph);
     858            for (auto e : make_iterator_range(out_edges(i, mMultiplexSetGraph))) {
     859                const auto s = source(e, mMultiplexSetGraph);
    856860                if (out_degree(s, mMultiplexSetGraph) != 0) {
    857861                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
     
    942946void AutoMultiplexing::multiplexSelectedIndependentSets() {
    943947
    944     const unsigned f = num_vertices(mConstraintGraph);
    945     const unsigned l = num_vertices(mMultiplexSetGraph);
     948    const unsigned first_set = num_vertices(mConstraintGraph);
     949    const unsigned last_set = num_vertices(mMultiplexSetGraph);
    946950
    947951    // Preallocate the structures based on the size of the largest multiplex set
    948952    size_t max_n = 3;
    949     for (unsigned s = f; s != l; ++s) {
    950         max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
     953    for (unsigned idx = first_set; idx != last_set; ++idx) {
     954        max_n = std::max<unsigned>(max_n, out_degree(idx, mMultiplexSetGraph));
    951955    }
    952956
     
    956960    // relationships of our independent sets.
    957961
    958     for (unsigned s = f; s != l; ++s) {
    959         const size_t n = out_degree(s, mMultiplexSetGraph);
     962    for (unsigned idx = first_set; idx != last_set; ++idx) {
     963        const size_t n = out_degree(idx, mMultiplexSetGraph);
    960964        if (n) {
    961965            const size_t m = log2_plus_one(n);           
    962966            Advance * input[n];
    963             Advance * muxed[m];
     967            Advance * muxed[m];           
    964968
    965969            unsigned i = 0;
    966             for (const auto e : make_iterator_range(out_edges(s, mMultiplexSetGraph))) {
     970            for (const auto e : make_iterator_range(out_edges(idx, mMultiplexSetGraph))) {
    967971                input[i] = std::get<0>(mAdvance[target(e, mMultiplexSetGraph)]);
    968972                assert (input[i]);
     
    980984
    981985                std::ostringstream prefix;
    982                 prefix << "mux" << n << "to" << m << '_';
    983                 for (size_t i = 1; i <= n; ++i) {
    984                     if ((i & (static_cast<size_t>(1) << j)) != 0) {
    985                         Q.push_back(input[i - 1]->getOperand(0));
     986                prefix << "mux" << n << "to" << m << '.' << (j + 1);
     987                for (size_t i = 0; i != n; ++i) {
     988                    if (((i + 1) & (1ULL << j)) != 0) {
     989                        Q.push_back(input[i]->getOperand(0));
    986990                    }
    987991                }
     
    10001004            }
    10011005
    1002             /// Perform m-to-n Demultiplexing           
    1003             for (size_t i = 1; i <= n; ++i) {
     1006            /// Perform m-to-n Demultiplexing                       
     1007            for (size_t i = 0; i != n; ++i) {
    10041008
    10051009                // Construct the demuxed values and replaces all the users of the original advances with them.
    10061010                for (size_t j = 0; j != m; ++j) {
    1007                     if ((i & (1ULL << j)) == 0) {
     1011                    if (((i + 1) & (1ULL << j)) == 0) {
    10081012                        Q.push_back(muxed[j]);
    10091013                    }
     
    10231027
    10241028                for (unsigned j = 0; j != m; ++j) {
    1025                     if ((i & (1ULL << j)) != 0) {
     1029                    if (((i + 1) & (1ULL << j)) != 0) {
    10261030                        assert (!Q.full());
    10271031                        Q.push_back(muxed[j]);
     
    10371041
    10381042                PabloAST * demuxed = Q.front(); Q.pop_front(); assert (demuxed);
    1039                 input[i - 1]->replaceWith(demuxed, true, true);
     1043                input[i]->replaceWith(demuxed, true, true);
    10401044            }
    10411045        }       
     
    10591063    std::stack<Statement *> scope;
    10601064
     1065    raw_os_ostream out(std::cerr);
     1066
    10611067    for (Statement * stmt = entry.front(); ; ) { restart:
    10621068        while ( stmt ) {
    1063 
    10641069            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    10651070                PabloAST * const op = stmt->getOperand(i);
     
    10981103}
    10991104
     1105/** ------------------------------------------------------------------------------------------------------------- *
     1106 * @brief reassociate
     1107 ** ------------------------------------------------------------------------------------------------------------- */
     1108inline 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
    11001276} // end of namespace pablo
    11011277
Note: See TracChangeset for help on using the changeset viewer.