[4629] | 1 | #include "pablo_bddminimization.h" |
---|
| 2 | #include <pablo/codegenstate.h> |
---|
| 3 | #include <llvm/ADT/BitVector.h> |
---|
| 4 | #include <stack> |
---|
| 5 | #include <queue> |
---|
| 6 | #include <unordered_set> |
---|
| 7 | #include <boost/container/flat_set.hpp> |
---|
| 8 | #include <boost/numeric/ublas/matrix.hpp> |
---|
| 9 | #include <boost/circular_buffer.hpp> |
---|
| 10 | #include <include/simd-lib/builtins.hpp> |
---|
| 11 | #include <pablo/builder.hpp> |
---|
| 12 | #include <boost/range/iterator_range.hpp> |
---|
| 13 | #include <pablo/printer_pablos.h> |
---|
| 14 | #include <cudd.h> |
---|
| 15 | #include <util.h> |
---|
| 16 | |
---|
| 17 | using namespace llvm; |
---|
| 18 | using namespace boost; |
---|
| 19 | using namespace boost::container; |
---|
| 20 | using namespace boost::numeric::ublas; |
---|
| 21 | |
---|
| 22 | // #define PRINT_DEBUG_OUTPUT |
---|
| 23 | |
---|
| 24 | #if !defined(NDEBUG) || defined(PRINT_DEBUG_OUTPUT) |
---|
| 25 | #include <iostream> |
---|
| 26 | |
---|
| 27 | using namespace pablo; |
---|
| 28 | typedef uint64_t timestamp_t; |
---|
| 29 | |
---|
| 30 | static inline timestamp_t read_cycle_counter() { |
---|
| 31 | #ifdef __GNUC__ |
---|
| 32 | timestamp_t ts; |
---|
| 33 | #ifdef __x86_64__ |
---|
| 34 | unsigned int eax, edx; |
---|
| 35 | asm volatile("rdtsc" : "=a" (eax), "=d" (edx)); |
---|
| 36 | ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32); |
---|
| 37 | #else |
---|
| 38 | asm volatile("rdtsc\n" : "=A" (ts)); |
---|
| 39 | #endif |
---|
| 40 | return(ts); |
---|
| 41 | #endif |
---|
| 42 | #ifdef _MSC_VER |
---|
| 43 | return __rdtsc(); |
---|
| 44 | #endif |
---|
| 45 | } |
---|
| 46 | |
---|
| 47 | #define LOG(x) std::cerr << x << std::endl; |
---|
| 48 | #define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter() |
---|
| 49 | #define LOG_GRAPH(Name, G) \ |
---|
| 50 | LOG(Name << " |V|=" << num_vertices(G) << ", |E|=" << num_edges(G) << \ |
---|
| 51 | " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')') |
---|
| 52 | |
---|
| 53 | unsigned __count_advances(const PabloBlock & entry) { |
---|
| 54 | |
---|
| 55 | std::stack<const Statement *> scope; |
---|
| 56 | unsigned advances = 0; |
---|
| 57 | |
---|
| 58 | // Scan through and collect all the advances, calls, scanthrus and matchstars ... |
---|
| 59 | for (const Statement * stmt = entry.front(); ; ) { |
---|
| 60 | while ( stmt ) { |
---|
| 61 | if (isa<Advance>(stmt)) { |
---|
| 62 | ++advances; |
---|
| 63 | } |
---|
| 64 | else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) { |
---|
| 65 | // Set the next statement to be the first statement of the inner scope and push the |
---|
| 66 | // next statement of the current statement into the scope stack. |
---|
| 67 | const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(); |
---|
| 68 | scope.push(stmt->getNextNode()); |
---|
| 69 | stmt = nested.front(); |
---|
| 70 | assert (stmt); |
---|
| 71 | continue; |
---|
| 72 | } |
---|
| 73 | stmt = stmt->getNextNode(); |
---|
| 74 | } |
---|
| 75 | if (scope.empty()) { |
---|
| 76 | break; |
---|
| 77 | } |
---|
| 78 | stmt = scope.top(); |
---|
| 79 | scope.pop(); |
---|
| 80 | } |
---|
| 81 | return advances; |
---|
| 82 | } |
---|
| 83 | |
---|
| 84 | #define LOG_NUMBER_OF_ADVANCES(entry) LOG("|Advances|=" << __count_advances(entry)) |
---|
| 85 | |
---|
| 86 | #else |
---|
| 87 | #define LOG(x) |
---|
| 88 | #define RECORD_TIMESTAMP(Name) |
---|
| 89 | #define LOG_GRAPH(Name, G) |
---|
| 90 | #define LOG_NUMBER_OF_ADVANCES(entry) |
---|
| 91 | #endif |
---|
| 92 | |
---|
| 93 | |
---|
| 94 | namespace pablo { |
---|
| 95 | |
---|
| 96 | bool BDDMinimizationPass::optimize(const std::vector<Var *> & input, PabloBlock & entry) { |
---|
| 97 | |
---|
| 98 | std::random_device rd; |
---|
| 99 | const auto seed = rd(); |
---|
| 100 | RNG rng(seed); |
---|
| 101 | |
---|
| 102 | LOG("Seed: " << seed); |
---|
| 103 | |
---|
| 104 | BDDMinimizationPass am; |
---|
| 105 | RECORD_TIMESTAMP(start_initialize); |
---|
| 106 | am.initialize(input, entry); |
---|
| 107 | RECORD_TIMESTAMP(end_initialize); |
---|
| 108 | |
---|
| 109 | LOG("Initialize: " << (end_initialize - start_initialize)); |
---|
| 110 | |
---|
| 111 | LOG_NUMBER_OF_ADVANCES(entry); |
---|
| 112 | |
---|
| 113 | RECORD_TIMESTAMP(start_characterize); |
---|
| 114 | am.characterize(entry); |
---|
| 115 | RECORD_TIMESTAMP(end_characterize); |
---|
| 116 | |
---|
| 117 | LOG("Characterize: " << (end_characterize - start_characterize)); |
---|
| 118 | |
---|
| 119 | RECORD_TIMESTAMP(start_minimization); |
---|
| 120 | am.minimize(entry); |
---|
| 121 | RECORD_TIMESTAMP(end_minimization); |
---|
| 122 | LOG("Minimize: " << (end_minimization - start_minimization)); |
---|
| 123 | |
---|
| 124 | RECORD_TIMESTAMP(start_shutdown); |
---|
| 125 | am.shutdown(); |
---|
| 126 | RECORD_TIMESTAMP(end_shutdown); |
---|
| 127 | LOG("Shutdown: " << (end_shutdown - start_shutdown)); |
---|
| 128 | |
---|
| 129 | RECORD_TIMESTAMP(start_create_multiplex_graph); |
---|
| 130 | const bool multiplex = am.generateMultiplexSets(rng, 1); |
---|
| 131 | RECORD_TIMESTAMP(end_create_multiplex_graph); |
---|
| 132 | LOG("GenerateMultiplexSets: " << (end_create_multiplex_graph - start_create_multiplex_graph)); |
---|
| 133 | |
---|
| 134 | if (multiplex) { |
---|
| 135 | |
---|
| 136 | RECORD_TIMESTAMP(start_select_multiplex_sets); |
---|
| 137 | am.selectMultiplexSets(rng); |
---|
| 138 | RECORD_TIMESTAMP(end_select_multiplex_sets); |
---|
| 139 | LOG("SelectMultiplexSets: " << (end_select_multiplex_sets - start_select_multiplex_sets)); |
---|
| 140 | |
---|
| 141 | RECORD_TIMESTAMP(start_subset_constraints); |
---|
| 142 | am.applySubsetConstraints(); |
---|
| 143 | RECORD_TIMESTAMP(end_subset_constraints); |
---|
| 144 | LOG("ApplySubsetConstraints: " << (end_subset_constraints - start_subset_constraints)); |
---|
| 145 | |
---|
| 146 | RECORD_TIMESTAMP(start_select_independent_sets); |
---|
| 147 | am.multiplexSelectedIndependentSets(); |
---|
| 148 | RECORD_TIMESTAMP(end_select_independent_sets); |
---|
| 149 | LOG("MultiplexSelectedSets: " << (end_select_independent_sets - start_select_independent_sets)); |
---|
| 150 | |
---|
| 151 | RECORD_TIMESTAMP(start_topological_sort); |
---|
| 152 | am.topologicalSort(entry); |
---|
| 153 | RECORD_TIMESTAMP(end_topological_sort); |
---|
| 154 | LOG("TopologicalSort: " << (end_topological_sort - start_topological_sort)); |
---|
| 155 | } |
---|
| 156 | |
---|
| 157 | LOG_NUMBER_OF_ADVANCES(entry); |
---|
| 158 | |
---|
| 159 | return multiplex; |
---|
| 160 | } |
---|
| 161 | |
---|
| 162 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 163 | * @brief initialize |
---|
| 164 | * @param vars the input vars for this program |
---|
| 165 | * @param entry the entry block |
---|
| 166 | * |
---|
| 167 | * Scan through the program to identify any advances and calls then initialize the BDD engine with |
---|
| 168 | * the proper variable ordering. |
---|
| 169 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 170 | void BDDMinimizationPass::initialize(const std::vector<Var *> & vars, PabloBlock & entry) { |
---|
| 171 | |
---|
| 172 | flat_map<const PabloAST *, unsigned> map; |
---|
| 173 | std::stack<Statement *> scope; |
---|
| 174 | unsigned complexStatements = 0; // number of statements that cannot always be categorized without generating a new variable |
---|
| 175 | |
---|
| 176 | // Scan through and collect all the advances, calls, scanthrus and matchstars ... |
---|
| 177 | unsigned n = 0, m = 0; |
---|
| 178 | for (Statement * stmt = entry.front(); ; ) { |
---|
| 179 | while ( stmt ) { |
---|
| 180 | ++n; |
---|
| 181 | if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) { |
---|
| 182 | // Set the next statement to be the first statement of the inner scope and push the |
---|
| 183 | // next statement of the current statement into the scope stack. |
---|
| 184 | const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(); |
---|
| 185 | scope.push(stmt->getNextNode()); |
---|
| 186 | stmt = nested.front(); |
---|
| 187 | assert (stmt); |
---|
| 188 | continue; |
---|
| 189 | } |
---|
| 190 | |
---|
| 191 | assert ("Run the Simplifer pass prior to this!" && (stmt->getNumUses() != 0 || (isa<Assign>(stmt) ? !cast<Assign>(stmt)->superfluous() : false))); |
---|
| 192 | |
---|
| 193 | switch (stmt->getClassTypeId()) { |
---|
| 194 | case PabloAST::ClassTypeId::Advance: |
---|
| 195 | mAdvanceMap.emplace(stmt, m); |
---|
| 196 | map.emplace(stmt, m++); |
---|
| 197 | case PabloAST::ClassTypeId::Call: |
---|
| 198 | case PabloAST::ClassTypeId::ScanThru: |
---|
| 199 | case PabloAST::ClassTypeId::MatchStar: |
---|
| 200 | complexStatements++; |
---|
| 201 | break; |
---|
| 202 | default: |
---|
| 203 | break; |
---|
| 204 | } |
---|
| 205 | stmt = stmt->getNextNode(); |
---|
| 206 | } |
---|
| 207 | if (scope.empty()) { |
---|
| 208 | break; |
---|
| 209 | } |
---|
| 210 | stmt = scope.top(); |
---|
| 211 | scope.pop(); |
---|
| 212 | } |
---|
| 213 | |
---|
| 214 | // Create the transitive closure matrix of graph. From this we'll construct |
---|
| 215 | // two graphs restricted to the relationships between advances. The first will |
---|
| 216 | // be a path graph, which is used to bypass testing for mutual exclusivity of |
---|
| 217 | // advances that cannot be multiplexed. The second is a transitive reduction |
---|
| 218 | // of that graph, which forms the basis of our constraint graph when deciding |
---|
| 219 | // which advances ought to be multiplexed. |
---|
| 220 | |
---|
| 221 | matrix<bool> G(n, m); // Let G be a matrix with n rows of m (Advance) elements |
---|
| 222 | G.clear(); |
---|
| 223 | for (unsigned i = 0; i != m; ++i) { |
---|
| 224 | G(i, i) = true; |
---|
| 225 | } |
---|
| 226 | |
---|
| 227 | n = m; |
---|
| 228 | m = 0; |
---|
| 229 | |
---|
| 230 | const Statement * stmt = entry.front(); |
---|
| 231 | for (;;) { |
---|
| 232 | while ( stmt ) { |
---|
| 233 | |
---|
| 234 | unsigned u; |
---|
| 235 | if (isa<Advance>(stmt)) { |
---|
| 236 | assert (mAdvanceMap.count(stmt) && mAdvanceMap[stmt] == m); |
---|
| 237 | u = m++; |
---|
| 238 | } |
---|
| 239 | else { |
---|
| 240 | u = n++; |
---|
| 241 | map.emplace(stmt, u); |
---|
| 242 | } |
---|
| 243 | |
---|
| 244 | for (unsigned i = 0; i != stmt->getNumOperands(); ++i) { |
---|
| 245 | const PabloAST * const op = stmt->getOperand(i); |
---|
| 246 | if (LLVM_LIKELY(isa<Statement>(op))) { |
---|
| 247 | const unsigned v = map[op]; |
---|
| 248 | for (unsigned w = 0; w != m; ++w) { |
---|
| 249 | G(u, w) |= G(v, w); |
---|
| 250 | } |
---|
| 251 | } |
---|
| 252 | } |
---|
| 253 | if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) { |
---|
| 254 | // Set the next statement to be the first statement of the inner scope |
---|
| 255 | // and push the next statement of the current statement into the stack. |
---|
| 256 | const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(); |
---|
| 257 | scope.push(stmt->getNextNode()); |
---|
| 258 | stmt = nested.front(); |
---|
| 259 | assert (stmt); |
---|
| 260 | continue; |
---|
| 261 | } |
---|
| 262 | stmt = stmt->getNextNode(); |
---|
| 263 | } |
---|
| 264 | if (scope.empty()) { |
---|
| 265 | break; |
---|
| 266 | } |
---|
| 267 | stmt = scope.top(); |
---|
| 268 | scope.pop(); |
---|
| 269 | } |
---|
| 270 | |
---|
| 271 | // Record the path / base constraint graph after removing any reflexive-loops. |
---|
| 272 | // Since G is a use-def graph and we want our constraint graph to be a def-use graph, |
---|
| 273 | // reverse the edges as we're writing them to obtain the transposed graph. |
---|
| 274 | mConstraintGraph = ConstraintGraph(m); |
---|
| 275 | mSubsetGraph = SubsetGraph(m); |
---|
| 276 | |
---|
| 277 | for (unsigned i = 0; i != m; ++i) { |
---|
| 278 | G(i, i) = false; |
---|
| 279 | for (unsigned j = 0; j != m; ++j) { |
---|
| 280 | if (G(i, j)) { |
---|
| 281 | add_edge(j, i, mConstraintGraph); |
---|
| 282 | } |
---|
| 283 | } |
---|
| 284 | } |
---|
| 285 | |
---|
| 286 | // Initialize the BDD engine ... |
---|
| 287 | mManager = Cudd_Init((complexStatements + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0); |
---|
| 288 | Cudd_AutodynDisable(mManager); |
---|
| 289 | |
---|
| 290 | // Map the predefined 0/1 entries |
---|
| 291 | mCharacterizationMap[entry.createZeroes()] = Zero(); |
---|
| 292 | mCharacterizationMap[entry.createOnes()] = One(); |
---|
| 293 | |
---|
| 294 | // Order the variables so the input Vars are pushed to the end; they ought to |
---|
| 295 | // be the most complex to resolve. |
---|
| 296 | unsigned i = complexStatements; |
---|
| 297 | for (const Var * var : vars) { |
---|
| 298 | mCharacterizationMap[var] = Cudd_bddIthVar(mManager, i++); |
---|
| 299 | } |
---|
| 300 | } |
---|
| 301 | |
---|
| 302 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 303 | * @brief characterize |
---|
| 304 | * @param vars the input vars for this program |
---|
| 305 | * |
---|
| 306 | * Scan through the program and iteratively compute the BDDs for each statement. |
---|
| 307 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 308 | void BDDMinimizationPass::characterize(PabloBlock & block) { |
---|
| 309 | for (Statement * stmt : block) { |
---|
| 310 | if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) { |
---|
| 311 | // Set the next statement to be the first statement of the inner scope and push the |
---|
| 312 | // next statement of the current statement into the scope stack. |
---|
| 313 | characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody()); |
---|
| 314 | continue; |
---|
| 315 | } |
---|
| 316 | mCharacterizationMap[stmt] = characterize(stmt, true); |
---|
| 317 | } |
---|
| 318 | } |
---|
| 319 | |
---|
| 320 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 321 | * @brief characterize |
---|
| 322 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 323 | DdNode * BDDMinimizationPass::characterize(Statement * const stmt, const bool throwUncharacterizedOperandError) { |
---|
| 324 | |
---|
| 325 | DdNode * bdd = nullptr; |
---|
| 326 | // Map our operands to the computed BDDs |
---|
| 327 | std::array<DdNode *, 3> input; |
---|
| 328 | for (unsigned i = 0; i != stmt->getNumOperands(); ++i) { |
---|
| 329 | PabloAST * const op = stmt->getOperand(i); |
---|
| 330 | if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) { |
---|
| 331 | continue; |
---|
| 332 | } |
---|
| 333 | auto f = mCharacterizationMap.find(op); |
---|
| 334 | if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) { |
---|
| 335 | if (throwUncharacterizedOperandError) { |
---|
| 336 | std::string tmp; |
---|
| 337 | llvm::raw_string_ostream msg(tmp); |
---|
| 338 | msg << "Uncharacterized operand " << std::to_string(i); |
---|
| 339 | PabloPrinter::print(stmt, " of ", msg); |
---|
| 340 | throw std::runtime_error(msg.str()); |
---|
| 341 | } |
---|
| 342 | return nullptr; |
---|
| 343 | } |
---|
| 344 | input[i] = f->second; |
---|
| 345 | } |
---|
| 346 | |
---|
| 347 | switch (stmt->getClassTypeId()) { |
---|
| 348 | case PabloAST::ClassTypeId::Assign: |
---|
| 349 | return input[0]; |
---|
| 350 | case PabloAST::ClassTypeId::And: |
---|
| 351 | bdd = And(input[0], input[1]); |
---|
| 352 | break; |
---|
| 353 | case PabloAST::ClassTypeId::Next: |
---|
| 354 | case PabloAST::ClassTypeId::Or: |
---|
| 355 | return Or(input[0], input[1]); |
---|
| 356 | case PabloAST::ClassTypeId::Xor: |
---|
| 357 | return Xor(input[0], input[1]); |
---|
| 358 | case PabloAST::ClassTypeId::Not: |
---|
| 359 | return Not(input[0]); |
---|
| 360 | case PabloAST::ClassTypeId::Sel: |
---|
| 361 | bdd = Ite(input[0], input[1], input[2]); |
---|
| 362 | break; |
---|
| 363 | case PabloAST::ClassTypeId::ScanThru: |
---|
| 364 | // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility |
---|
| 365 | // of a contradition being erroneously calculated later. An example of this |
---|
| 366 | // would be Â¬(ScanThru(c,m) âš m) |
---|
| 367 | case PabloAST::ClassTypeId::MatchStar: |
---|
| 368 | if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) { |
---|
| 369 | return Zero(); |
---|
| 370 | } |
---|
| 371 | case PabloAST::ClassTypeId::Call: |
---|
| 372 | return NewVar(); |
---|
| 373 | case PabloAST::ClassTypeId::Advance: |
---|
| 374 | return characterize(cast<Advance>(stmt), input[0]); |
---|
| 375 | default: |
---|
| 376 | throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string()); |
---|
| 377 | } |
---|
| 378 | |
---|
| 379 | if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) { |
---|
| 380 | Cudd_RecursiveDeref(mManager, bdd); |
---|
| 381 | bdd = Zero(); |
---|
| 382 | } |
---|
| 383 | |
---|
| 384 | return bdd; |
---|
| 385 | |
---|
| 386 | } |
---|
| 387 | |
---|
| 388 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 389 | * @brief characterize |
---|
| 390 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 391 | inline DdNode * BDDMinimizationPass::characterize(Advance * adv, DdNode * input) { |
---|
| 392 | DdNode * Ik, * Ck, * Nk; |
---|
| 393 | if (LLVM_UNLIKELY(isZero(input))) { |
---|
| 394 | Ik = Ck = Nk = Zero(); |
---|
| 395 | } |
---|
| 396 | else { |
---|
| 397 | |
---|
| 398 | Ik = input; |
---|
| 399 | Ck = NewVar(); |
---|
| 400 | Nk = Not(Ck); |
---|
| 401 | |
---|
| 402 | assert (mAdvanceMap.count(adv)); |
---|
| 403 | |
---|
| 404 | const auto k = mAdvanceMap[adv]; |
---|
| 405 | |
---|
| 406 | std::vector<bool> unconstrained(k , false); |
---|
| 407 | |
---|
| 408 | // Can we use a transposed copy of the subset graph to determine an ordering of variables? |
---|
| 409 | for (unsigned i = 0; i != k; ++i) { |
---|
| 410 | // Have we already proven that these are unconstrained by the subset relationships? |
---|
| 411 | if (unconstrained[i]) continue; |
---|
| 412 | Advance * tmp = std::get<0>(mAdvance[i]); |
---|
| 413 | // If these advances are "shifting" their values by the same amount and aren't transitively dependant ... |
---|
| 414 | if ((adv->getOperand(1) == tmp->getOperand(1)) && (notTransitivelyDependant(i, k))) { |
---|
| 415 | DdNode * Ii = std::get<1>(mAdvance[i]); |
---|
| 416 | DdNode * Ni = std::get<2>(mAdvance[i]); |
---|
| 417 | // TODO: test both Cudd_And and Cudd_bddIntersect to see which is faster |
---|
| 418 | DdNode * const IiIk = Intersect(Ik, Ii); |
---|
| 419 | // Is there any satisfying truth assignment? If not, these streams are mutually exclusive. |
---|
| 420 | if (noSatisfyingAssignment(IiIk)) { |
---|
| 421 | assert (mCharacterizationMap.count(tmp)); |
---|
| 422 | DdNode *& Ci = mCharacterizationMap[tmp]; |
---|
| 423 | // Mark the i-th and k-th Advances as being mutually exclusive |
---|
| 424 | Ck = And(Ck, Ni); |
---|
| 425 | Ci = And(Ci, Nk); |
---|
| 426 | // If Ai â© Ak = â
and Aj â Ai, Aj â© Ak = â
. |
---|
| 427 | graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end; |
---|
| 428 | for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) { |
---|
| 429 | const auto j = source(*ei, mSubsetGraph); |
---|
| 430 | if (notTransitivelyDependant(k, j)) { |
---|
| 431 | Advance * adv = std::get<0>(mAdvance[j]); |
---|
| 432 | assert (mCharacterizationMap.count(adv)); |
---|
| 433 | DdNode *& Cj = mCharacterizationMap[adv]; |
---|
| 434 | DdNode * Nj = std::get<2>(mAdvance[j]); |
---|
| 435 | // Mark the i-th and j-th Advances as being mutually exclusive |
---|
| 436 | Ck = And(Ck, Nj); |
---|
| 437 | Cj = And(Cj, Nk); |
---|
| 438 | unconstrained[j] = true; |
---|
| 439 | } |
---|
| 440 | } |
---|
| 441 | unconstrained[i] = true; |
---|
| 442 | } |
---|
| 443 | else if (Ik == IiIk) { |
---|
| 444 | // If Ik = Ii â© Ik then Ik â Ii. Record this in the subset graph with the arc (k,i). |
---|
| 445 | // These edges will be moved into the multiplex set graph if Ai and Ak happen to be |
---|
| 446 | // in the same mutually exclusive set. |
---|
| 447 | add_edge(k, i, mSubsetGraph); |
---|
| 448 | // If Ak â Ai and Ai â Aj, Ak â Aj. |
---|
| 449 | graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end; |
---|
| 450 | for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) { |
---|
| 451 | const auto j = target(*ei, mSubsetGraph); |
---|
| 452 | add_edge(k, j, mSubsetGraph); |
---|
| 453 | unconstrained[j] = true; |
---|
| 454 | } |
---|
| 455 | unconstrained[i] = true; |
---|
| 456 | } |
---|
| 457 | else if (Ii == IiIk) { |
---|
| 458 | // If Ii = Ii â© Ik then Ii â Ik. Record this in the subset graph with the arc (i,k). |
---|
| 459 | add_edge(i, k, mSubsetGraph); |
---|
| 460 | // If Ai â Ak and Aj â Ai, Aj â Ak. |
---|
| 461 | graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end; |
---|
| 462 | for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) { |
---|
| 463 | const auto j = source(*ei, mSubsetGraph); |
---|
| 464 | add_edge(j, k, mSubsetGraph); |
---|
| 465 | unconstrained[j] = true; |
---|
| 466 | } |
---|
| 467 | unconstrained[i] = true; |
---|
| 468 | } |
---|
| 469 | Cudd_RecursiveDeref(mManager, IiIk); |
---|
| 470 | } |
---|
| 471 | } |
---|
| 472 | |
---|
| 473 | for (unsigned i = 0; i != k; ++i) { |
---|
| 474 | const Advance * const tmp = std::get<0>(mAdvance[i]); |
---|
| 475 | // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed. |
---|
| 476 | if (!unconstrained[i] || (adv->getParent() != tmp->getParent())) { |
---|
| 477 | // We want the constraint graph to be acyclic; since the dependencies are already in topological order, |
---|
| 478 | // adding an arc from a lesser to greater numbered vertex won't induce a cycle. |
---|
| 479 | add_edge(i, k, mConstraintGraph); |
---|
| 480 | } |
---|
| 481 | } |
---|
| 482 | } |
---|
| 483 | |
---|
| 484 | mAdvance.emplace_back(adv, Ik, Nk); |
---|
| 485 | |
---|
| 486 | return Ck; |
---|
| 487 | } |
---|
| 488 | |
---|
| 489 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 490 | * @brief reevaluate |
---|
| 491 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 492 | void BDDMinimizationPass::reevaluate(Next * next, DdNode * value) { |
---|
| 493 | |
---|
| 494 | Assign * const initial = cast<Assign>(next->getOperand(0)); |
---|
| 495 | |
---|
| 496 | if (LLVM_UNLIKELY(mCharacterizationMap[initial] == value)) { |
---|
| 497 | return; |
---|
| 498 | } |
---|
| 499 | mCharacterizationMap[initial] = value; |
---|
| 500 | |
---|
| 501 | |
---|
| 502 | std::queue<PabloAST *> Q; |
---|
| 503 | flat_set<PabloBlock *> within_scope; |
---|
| 504 | |
---|
| 505 | for (PabloBlock * block = next->getParent(); ;) { |
---|
| 506 | within_scope.insert(block); |
---|
| 507 | for (PabloAST * user : block->users()) { |
---|
| 508 | if (within_scope.insert(cast<PabloBlock>(user)).second) { |
---|
| 509 | Q.push(user); |
---|
| 510 | } |
---|
| 511 | } |
---|
| 512 | if (Q.empty()) { |
---|
| 513 | break; |
---|
| 514 | } |
---|
| 515 | block = cast<PabloBlock>(Q.front()); |
---|
| 516 | Q.pop(); |
---|
| 517 | } |
---|
| 518 | |
---|
| 519 | std::unordered_set<PabloAST *> visited; |
---|
| 520 | |
---|
| 521 | for (Statement * current = initial; ; ) { |
---|
| 522 | for (PabloAST * user : current->users()) { |
---|
| 523 | if (Statement * stmt = dyn_cast<Statement>(user)) { |
---|
| 524 | if (visited.insert(user).second && within_scope.count(stmt->getParent())) { |
---|
| 525 | DdNode * bdd = characterize(stmt, false); |
---|
| 526 | if (bdd && mCharacterizationMap[user] != bdd) { |
---|
| 527 | mCharacterizationMap[user] = bdd; |
---|
| 528 | Q.push(stmt); |
---|
| 529 | } |
---|
| 530 | } |
---|
| 531 | } |
---|
| 532 | } |
---|
| 533 | if (Q.empty()) { |
---|
| 534 | break; |
---|
| 535 | } |
---|
| 536 | current = cast<Statement>(Q.front()); |
---|
| 537 | Q.pop(); |
---|
| 538 | } |
---|
| 539 | |
---|
| 540 | } |
---|
| 541 | |
---|
| 542 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 543 | * @brief minimize |
---|
| 544 | * @param entry the entry block of the program |
---|
| 545 | * |
---|
| 546 | * Scan through the program using the precomputed BDDs and replace any statements with equivalent BDDs with the |
---|
| 547 | * earlier one (assuming its in scope) and replace any contradictions with Zero. |
---|
| 548 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 549 | inline void BDDMinimizationPass::minimize(PabloBlock & entry) { |
---|
| 550 | SubsitutionMap baseMap; |
---|
| 551 | baseMap.insert(Zero(), entry.createZeroes()); |
---|
| 552 | baseMap.insert(One(), entry.createOnes()); |
---|
| 553 | minimize(entry, baseMap); |
---|
| 554 | } |
---|
| 555 | |
---|
| 556 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 557 | * @brief prohibited |
---|
| 558 | * |
---|
| 559 | * If this statement is an Assign or Next node or any of its operands is a non-superfluous Assign or Next node, |
---|
| 560 | * then we're prohibited from minimizing this statement. |
---|
| 561 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 562 | inline bool prohibited(const Statement * const stmt) { |
---|
| 563 | if (isa<Assign>(stmt) || isa<Next>(stmt)) { |
---|
| 564 | return true; |
---|
| 565 | } |
---|
| 566 | for (unsigned i = 0; i != stmt->getNumOperands(); ++i) { |
---|
| 567 | const PabloAST * const op = stmt->getOperand(i); |
---|
| 568 | const Assign * const assign = dyn_cast<Assign>(op); |
---|
| 569 | if (LLVM_UNLIKELY((assign && !assign->superfluous()) || isa<Next>(op))) { |
---|
| 570 | return true; |
---|
| 571 | } |
---|
| 572 | } |
---|
| 573 | return false; |
---|
| 574 | } |
---|
| 575 | |
---|
| 576 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 577 | * @brief minimize |
---|
| 578 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 579 | void BDDMinimizationPass::minimize(PabloBlock & block, SubsitutionMap & parent) { |
---|
| 580 | SubsitutionMap subsitutionMap(&parent); |
---|
| 581 | for (Statement * stmt : block) { |
---|
| 582 | if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) { |
---|
| 583 | // Set the next statement to be the first statement of the inner scope and push the |
---|
| 584 | // next statement of the current statement into the scope stack. |
---|
| 585 | minimize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap); |
---|
| 586 | continue; |
---|
| 587 | } |
---|
| 588 | |
---|
| 589 | if (LLVM_UNLIKELY(prohibited(stmt))) { |
---|
| 590 | continue; |
---|
| 591 | } |
---|
| 592 | |
---|
| 593 | DdNode * bdd = mCharacterizationMap[stmt]; |
---|
| 594 | PabloAST * replacement = subsitutionMap.test(bdd, stmt); |
---|
| 595 | if (LLVM_UNLIKELY(replacement != nullptr)) { |
---|
| 596 | if (LLVM_UNLIKELY(isa<Advance>(stmt))) { |
---|
| 597 | assert (mAdvanceMap.count(stmt)); |
---|
| 598 | const auto k = mAdvanceMap[stmt]; |
---|
| 599 | const auto m = num_vertices(mConstraintGraph); |
---|
| 600 | for (unsigned i = 0; i != m; ++i) { |
---|
| 601 | add_edge(k, m, mConstraintGraph); |
---|
| 602 | } |
---|
| 603 | } |
---|
| 604 | Cudd_RecursiveDeref(mManager, bdd); |
---|
| 605 | stmt->replaceWith(replacement); |
---|
| 606 | } |
---|
| 607 | } |
---|
| 608 | } |
---|
| 609 | |
---|
| 610 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 611 | * @brief notTransitivelyDependant |
---|
| 612 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 613 | inline bool BDDMinimizationPass::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const { |
---|
| 614 | assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph)); |
---|
| 615 | return (mConstraintGraph.get_edge(i, j) == 0); |
---|
| 616 | } |
---|
| 617 | |
---|
| 618 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 619 | * @brief CUDD wrappers |
---|
| 620 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 621 | |
---|
| 622 | inline DdNode * BDDMinimizationPass::Zero() const { |
---|
| 623 | return Cudd_ReadLogicZero(mManager); |
---|
| 624 | } |
---|
| 625 | |
---|
| 626 | inline DdNode * BDDMinimizationPass::One() const { |
---|
| 627 | return Cudd_ReadOne(mManager); |
---|
| 628 | } |
---|
| 629 | |
---|
| 630 | inline DdNode * BDDMinimizationPass::NewVar() { |
---|
| 631 | return Cudd_bddIthVar(mManager, mVariables++); |
---|
| 632 | } |
---|
| 633 | |
---|
| 634 | inline bool BDDMinimizationPass::isZero(DdNode * const x) const { |
---|
| 635 | return x == Zero(); |
---|
| 636 | } |
---|
| 637 | |
---|
| 638 | inline DdNode * BDDMinimizationPass::And(DdNode * const x, DdNode * const y) { |
---|
| 639 | DdNode * r = Cudd_bddAnd(mManager, x, y); |
---|
| 640 | Cudd_Ref(r); |
---|
| 641 | return r; |
---|
| 642 | } |
---|
| 643 | |
---|
| 644 | inline DdNode * BDDMinimizationPass::Intersect(DdNode * const x, DdNode * const y) { |
---|
| 645 | DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r); |
---|
| 646 | return r; |
---|
| 647 | } |
---|
| 648 | |
---|
| 649 | inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) { |
---|
| 650 | DdNode * r = Cudd_bddOr(mManager, x, y); |
---|
| 651 | Cudd_Ref(r); |
---|
| 652 | return r; |
---|
| 653 | } |
---|
| 654 | |
---|
| 655 | inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) { |
---|
| 656 | DdNode * r = Cudd_bddXor(mManager, x, y); |
---|
| 657 | Cudd_Ref(r); |
---|
| 658 | return r; |
---|
| 659 | } |
---|
| 660 | |
---|
| 661 | inline DdNode * BDDMinimizationPass::Not(DdNode * const x) const { |
---|
| 662 | return Cudd_Not(x); |
---|
| 663 | } |
---|
| 664 | |
---|
| 665 | inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) { |
---|
| 666 | DdNode * r = Cudd_bddIte(mManager, x, y, z); |
---|
| 667 | Cudd_Ref(r); |
---|
| 668 | return r; |
---|
| 669 | } |
---|
| 670 | |
---|
| 671 | inline bool BDDMinimizationPass::noSatisfyingAssignment(DdNode * const x) { |
---|
| 672 | return Cudd_bddLeq(mManager, x, Zero()); |
---|
| 673 | } |
---|
| 674 | |
---|
| 675 | inline void BDDMinimizationPass::shutdown() { |
---|
| 676 | Cudd_Quit(mManager); |
---|
| 677 | } |
---|
| 678 | |
---|
| 679 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 680 | * @brief generateMultiplexSets |
---|
| 681 | * @param RNG random number generator |
---|
| 682 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 683 | bool BDDMinimizationPass::generateMultiplexSets(RNG & rng, unsigned k) { |
---|
| 684 | |
---|
| 685 | using vertex_t = ConstraintGraph::vertex_descriptor; |
---|
| 686 | using degree_t = graph_traits<ConstraintGraph>::degree_size_type; |
---|
| 687 | |
---|
| 688 | // What if we generated a "constraint free" graph instead? By taking each connected component of it |
---|
| 689 | // and computing the complement of it (with the same lesser to greater index ordering), we should |
---|
| 690 | // have the same problem here but decomposed into subgraphs. |
---|
| 691 | |
---|
| 692 | IndependentSet M, N; |
---|
| 693 | auto remainingVerticies = num_vertices(mConstraintGraph); |
---|
| 694 | std::vector<degree_t> D(remainingVerticies); |
---|
| 695 | M.reserve(15); |
---|
| 696 | N.reserve(15); |
---|
| 697 | |
---|
| 698 | mMultiplexSetGraph = MultiplexSetGraph(remainingVerticies); |
---|
| 699 | |
---|
| 700 | while (k) { |
---|
| 701 | |
---|
| 702 | // Push all source nodes into the new independent set N |
---|
| 703 | for (auto v : make_iterator_range(vertices(mConstraintGraph))) { |
---|
| 704 | const auto d = in_degree(v, mConstraintGraph); |
---|
| 705 | D[v] = d; |
---|
| 706 | if (d == 0) { |
---|
| 707 | N.push_back(v); |
---|
| 708 | } |
---|
| 709 | } |
---|
| 710 | |
---|
| 711 | for (;;) { |
---|
| 712 | |
---|
| 713 | addMultiplexSet(N, M); |
---|
| 714 | |
---|
| 715 | if (remainingVerticies == 0) { |
---|
| 716 | break; |
---|
| 717 | } |
---|
| 718 | |
---|
| 719 | assert (N.size() > 0); |
---|
| 720 | |
---|
| 721 | // Move all of our "newly" uncovered vertices in S into the "known" set M. By always choosing |
---|
| 722 | // at least one element from N, this will prevent us from adding the same multiplexing set again. |
---|
| 723 | M.insert(M.end(), N.begin(), N.end()); N.clear(); |
---|
| 724 | |
---|
| 725 | do { |
---|
| 726 | // Randomly choose a vertex in S and discard it. |
---|
| 727 | assert (!M.empty()); |
---|
| 728 | const auto i = M.begin() + IntDistribution(0, M.size() - 1)(rng); |
---|
| 729 | const vertex_t u = *i; |
---|
| 730 | M.erase(i); |
---|
| 731 | --remainingVerticies; |
---|
| 732 | for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) { |
---|
| 733 | const vertex_t v = target(e, mConstraintGraph); |
---|
| 734 | if ((--D[v]) == 0) { |
---|
| 735 | N.push_back(v); |
---|
| 736 | } |
---|
| 737 | } |
---|
| 738 | } |
---|
| 739 | while (N.empty() && remainingVerticies != 0); |
---|
| 740 | } |
---|
| 741 | |
---|
| 742 | if (--k == 0) { |
---|
| 743 | break; |
---|
| 744 | } |
---|
| 745 | |
---|
| 746 | N.clear(); |
---|
| 747 | M.clear(); |
---|
| 748 | } |
---|
| 749 | |
---|
| 750 | return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph); |
---|
| 751 | } |
---|
| 752 | |
---|
| 753 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 754 | * @brief addMultiplexSet |
---|
| 755 | * @param N an independent set |
---|
| 756 | * @param M an independent set |
---|
| 757 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 758 | inline void BDDMinimizationPass::addMultiplexSet(const IndependentSet & N, const IndependentSet & M) { |
---|
| 759 | |
---|
| 760 | // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships |
---|
| 761 | // between the "set vertex" and its members. We obtain these from "generateMultiplexSets". |
---|
| 762 | |
---|
| 763 | if ((N.size() + M.size()) >= 3) { |
---|
| 764 | const auto u = add_vertex(mMultiplexSetGraph); |
---|
| 765 | for (const auto x : N) { |
---|
| 766 | add_edge(u, x, mMultiplexSetGraph); |
---|
| 767 | } |
---|
| 768 | for (const auto y : M) { |
---|
| 769 | add_edge(u, y, mMultiplexSetGraph); |
---|
| 770 | } |
---|
| 771 | } |
---|
| 772 | } |
---|
| 773 | |
---|
| 774 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 775 | * @brief is_power_of_2 |
---|
| 776 | * @param n an integer |
---|
| 777 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 778 | static inline bool is_power_of_2(const size_t n) { |
---|
| 779 | return ((n & (n - 1)) == 0) ; |
---|
| 780 | } |
---|
| 781 | |
---|
| 782 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 783 | * @brief log2_plus_one |
---|
| 784 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 785 | static inline size_t log2_plus_one(const size_t n) { |
---|
| 786 | return std::log2<size_t>(n) + 1; // use a faster builtin function for this? |
---|
| 787 | } |
---|
| 788 | |
---|
| 789 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 790 | * @brief selectMultiplexSets |
---|
| 791 | * @param RNG random number generator |
---|
| 792 | * |
---|
| 793 | * This algorithm is simply computes a greedy set cover. We want an exact max-weight set cover but can generate new |
---|
| 794 | * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well |
---|
| 795 | * enough but more analysis is needed. |
---|
| 796 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 797 | void BDDMinimizationPass::selectMultiplexSets(RNG &) { |
---|
| 798 | |
---|
| 799 | |
---|
| 800 | using OutEdgeIterator = graph_traits<MultiplexSetGraph>::out_edge_iterator; |
---|
| 801 | using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator; |
---|
| 802 | using degree_t = MultiplexSetGraph::degree_size_type; |
---|
| 803 | using vertex_t = MultiplexSetGraph::vertex_descriptor; |
---|
| 804 | |
---|
| 805 | const size_t m = num_vertices(mConstraintGraph); |
---|
| 806 | const size_t n = num_vertices(mMultiplexSetGraph) - m; |
---|
| 807 | |
---|
| 808 | std::vector<degree_t> remaining(n, 0); |
---|
| 809 | std::vector<vertex_t> chosen_set(m, 0); |
---|
| 810 | |
---|
| 811 | for (unsigned i = 0; i != n; ++i) { |
---|
| 812 | remaining[i] = out_degree(i + m, mMultiplexSetGraph); |
---|
| 813 | } |
---|
| 814 | |
---|
| 815 | for (;;) { |
---|
| 816 | |
---|
| 817 | // Choose the set with the greatest number of vertices not already included in some other set. |
---|
| 818 | vertex_t k = 0; |
---|
| 819 | degree_t w = 0; |
---|
| 820 | for (vertex_t i = 0; i != n; ++i) { |
---|
| 821 | const degree_t r = remaining[i]; |
---|
| 822 | if (w < r) { |
---|
| 823 | k = i; |
---|
| 824 | w = r; |
---|
| 825 | } |
---|
| 826 | } |
---|
| 827 | |
---|
| 828 | // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort. |
---|
| 829 | if (w < 3) { |
---|
| 830 | break; |
---|
| 831 | } |
---|
| 832 | |
---|
| 833 | OutEdgeIterator ei, ei_end; |
---|
| 834 | for (std::tie(ei, ei_end) = out_edges(k + m, mMultiplexSetGraph); ei != ei_end; ++ei) { |
---|
| 835 | const vertex_t j = target(*ei, mMultiplexSetGraph); |
---|
| 836 | if (chosen_set[j] == 0) { |
---|
| 837 | chosen_set[j] = (k + m); |
---|
| 838 | InEdgeIterator ej, ej_end; |
---|
| 839 | for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) { |
---|
| 840 | remaining[source(*ej, mMultiplexSetGraph) - m]--; |
---|
| 841 | } |
---|
| 842 | } |
---|
| 843 | } |
---|
| 844 | |
---|
| 845 | assert (remaining[k] == 0); |
---|
| 846 | |
---|
| 847 | // If this contains 2^n elements for any n, discard the member that is most likely to be added |
---|
| 848 | // to some future set. |
---|
| 849 | if (is_power_of_2(w)) { |
---|
| 850 | vertex_t j = 0; |
---|
| 851 | degree_t w = 0; |
---|
| 852 | for (vertex_t i = 0; i != m; ++i) { |
---|
| 853 | if (chosen_set[i] == (k + m)) { |
---|
| 854 | InEdgeIterator ej, ej_end; |
---|
| 855 | degree_t r = 1; |
---|
| 856 | for (std::tie(ej, ej_end) = in_edges(i, mMultiplexSetGraph); ej != ej_end; ++ej) { |
---|
| 857 | // strongly prefer adding weight to unvisited sets that have more remaining vertices |
---|
| 858 | r += std::pow(remaining[source(*ej, mMultiplexSetGraph) - m], 2); |
---|
| 859 | } |
---|
| 860 | if (w < r) { |
---|
| 861 | j = i; |
---|
| 862 | w = r; |
---|
| 863 | } |
---|
| 864 | } |
---|
| 865 | } |
---|
| 866 | assert (w > 0); |
---|
| 867 | chosen_set[j] = 0; |
---|
| 868 | InEdgeIterator ej, ej_end; |
---|
| 869 | for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) { |
---|
| 870 | remaining[source(*ej, mMultiplexSetGraph) - m]++; |
---|
| 871 | } |
---|
| 872 | } |
---|
| 873 | } |
---|
| 874 | |
---|
| 875 | for (unsigned i = 0; i != m; ++i) { |
---|
| 876 | InEdgeIterator ei, ei_end; |
---|
| 877 | std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph); |
---|
| 878 | for (auto next = ei; ei != ei_end; ei = next) { |
---|
| 879 | ++next; |
---|
| 880 | if (source(*ei, mMultiplexSetGraph) != chosen_set[i]) { |
---|
| 881 | remove_edge(*ei, mMultiplexSetGraph); |
---|
| 882 | } |
---|
| 883 | } |
---|
| 884 | } |
---|
| 885 | |
---|
| 886 | #ifndef NDEBUG |
---|
| 887 | for (unsigned i = 0; i != m; ++i) { |
---|
| 888 | assert (in_degree(i, mMultiplexSetGraph) <= 1); |
---|
| 889 | } |
---|
| 890 | for (unsigned i = m; i != (m + n); ++i) { |
---|
| 891 | assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3); |
---|
| 892 | } |
---|
| 893 | #endif |
---|
| 894 | } |
---|
| 895 | |
---|
| 896 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 897 | * @brief choose |
---|
| 898 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 899 | |
---|
| 900 | inline Statement * choose(PabloAST * x, PabloAST * y, Statement * z) { |
---|
| 901 | return isa<Statement>(x) ? cast<Statement>(x) : (isa<Statement>(y) ? cast<Statement>(y) : z); |
---|
| 902 | } |
---|
| 903 | |
---|
| 904 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 905 | * @brief applySubsetConstraints |
---|
| 906 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 907 | void BDDMinimizationPass::applySubsetConstraints() { |
---|
| 908 | |
---|
| 909 | // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set |
---|
| 910 | // relationships of our independent sets. |
---|
| 911 | const unsigned m = num_vertices(mConstraintGraph); |
---|
| 912 | const unsigned n = num_vertices(mMultiplexSetGraph); |
---|
| 913 | |
---|
| 914 | // Add in any edges from our subset constraints to M that are within the same set. |
---|
| 915 | bool hasSubsetConstraint = false; |
---|
| 916 | |
---|
| 917 | graph_traits<SubsetGraph>::edge_iterator ei, ei_end; |
---|
| 918 | for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) { |
---|
| 919 | const auto u = source(*ei, mSubsetGraph); |
---|
| 920 | const auto v = target(*ei, mSubsetGraph); |
---|
| 921 | graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end; |
---|
| 922 | // If both the source and target of ei are adjacent to the same vertex, that vertex must be the |
---|
| 923 | // "set vertex". Add the edge between the vertices. |
---|
| 924 | for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) { |
---|
| 925 | auto w = target(*ej, mMultiplexSetGraph); |
---|
| 926 | // Only check (v, w) if w is a "set vertex". |
---|
| 927 | if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) { |
---|
| 928 | add_edge(u, v, mMultiplexSetGraph); |
---|
| 929 | hasSubsetConstraint = true; |
---|
| 930 | } |
---|
| 931 | } |
---|
| 932 | } |
---|
| 933 | |
---|
| 934 | if (LLVM_UNLIKELY(hasSubsetConstraint)) { |
---|
| 935 | // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices |
---|
| 936 | // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST. |
---|
| 937 | // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams. |
---|
| 938 | |
---|
| 939 | std::vector<MultiplexSetGraph::vertex_descriptor> V; |
---|
| 940 | std::stack<MultiplexSetGraph::vertex_descriptor> S; |
---|
| 941 | std::queue<PabloAST *> Q; |
---|
| 942 | BitVector D(n - m, 0); |
---|
| 943 | |
---|
| 944 | for (auto i = m; i != n; ++i) { |
---|
| 945 | graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end; |
---|
| 946 | // For each member of a "set vertex" ... |
---|
| 947 | std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph); |
---|
| 948 | for (; ei != ei_end; ++ei) { |
---|
| 949 | const auto s = source(*ei, mMultiplexSetGraph); |
---|
| 950 | if (out_degree(s, mMultiplexSetGraph) != 0) { |
---|
| 951 | // First scan through the subgraph of vertices in M dominated by s and build up the set T, |
---|
| 952 | // consisting of all sinks w.r.t. vertex s. |
---|
| 953 | auto u = s; |
---|
| 954 | for (;;) { |
---|
| 955 | graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end; |
---|
| 956 | for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) { |
---|
| 957 | auto v = target(*ej, mMultiplexSetGraph); |
---|
| 958 | if (D.test(v)) { |
---|
| 959 | continue; |
---|
| 960 | } |
---|
| 961 | D.set(v); |
---|
| 962 | if (out_degree(v, mMultiplexSetGraph) == 0) { |
---|
| 963 | V.push_back(v); |
---|
| 964 | } |
---|
| 965 | else { |
---|
| 966 | S.push(v); |
---|
| 967 | } |
---|
| 968 | } |
---|
| 969 | if (S.empty()) { |
---|
| 970 | break; |
---|
| 971 | } |
---|
| 972 | u = S.top(); |
---|
| 973 | S.pop(); |
---|
| 974 | } |
---|
| 975 | D.clear(); |
---|
| 976 | // Now in order for these advances to be mutually exclusive, the input to A_s must be masked |
---|
| 977 | // with the complement of each advance indicated by V. |
---|
| 978 | |
---|
| 979 | Advance * adv = std::get<0>(mAdvance[s]); |
---|
| 980 | PabloBlock * pb = adv->getParent(); |
---|
| 981 | |
---|
| 982 | for (auto i : V) { |
---|
| 983 | Q.push(std::get<0>(mAdvance[i])->getOperand(0)); |
---|
| 984 | } |
---|
| 985 | while (Q.size() > 1) { |
---|
| 986 | PabloAST * a1 = Q.front(); Q.pop(); |
---|
| 987 | PabloAST * a2 = Q.front(); Q.pop(); |
---|
| 988 | pb->setInsertPoint(cast<Statement>(a2)); |
---|
| 989 | Q.push(pb->createOr(a1, a2)); |
---|
| 990 | } |
---|
| 991 | assert (Q.size() == 1); |
---|
| 992 | |
---|
| 993 | PabloAST * const mask = pb->createNot(Q.front()); Q.pop(); |
---|
| 994 | adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in")); |
---|
| 995 | |
---|
| 996 | // Similar to the above, we're going to OR together the result of each advance, |
---|
| 997 | // including s. This will restore the advanced variable back to its original state. |
---|
| 998 | |
---|
| 999 | // Gather the original users to this advance. We'll be manipulating it shortly. |
---|
[4656] | 1000 | Statement::Vector U(adv->users()); |
---|
[4629] | 1001 | |
---|
| 1002 | // Add s to V and sort the list; it'll be closer to being in topological order. |
---|
| 1003 | V.push_back(s); |
---|
| 1004 | std::sort(V.begin(), V.end()); |
---|
| 1005 | for (auto i : V) { |
---|
| 1006 | Q.push(std::get<0>(mAdvance[i])); |
---|
| 1007 | } |
---|
| 1008 | while (Q.size() > 1) { |
---|
| 1009 | PabloAST * a1 = Q.front(); Q.pop(); |
---|
| 1010 | PabloAST * a2 = Q.front(); Q.pop(); |
---|
| 1011 | pb->setInsertPoint(choose(a2, a1, adv)); |
---|
| 1012 | Q.push(pb->createOr(a1, a2)); |
---|
| 1013 | } |
---|
| 1014 | assert (Q.size() == 1); |
---|
| 1015 | |
---|
| 1016 | PabloAST * const input = Q.front(); Q.pop(); |
---|
| 1017 | for (PabloAST * use : U) { |
---|
| 1018 | if (LLVM_LIKELY(isa<Statement>(use))) { |
---|
| 1019 | cast<Statement>(use)->replaceUsesOfWith(adv, input); |
---|
| 1020 | } |
---|
| 1021 | } |
---|
| 1022 | |
---|
| 1023 | pb->setInsertPoint(pb->back()); |
---|
| 1024 | |
---|
| 1025 | V.clear(); |
---|
| 1026 | |
---|
| 1027 | } |
---|
| 1028 | } |
---|
| 1029 | } |
---|
| 1030 | } |
---|
| 1031 | } |
---|
| 1032 | |
---|
| 1033 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 1034 | * @brief multiplexSelectedIndependentSets |
---|
| 1035 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 1036 | void BDDMinimizationPass::multiplexSelectedIndependentSets() const { |
---|
| 1037 | |
---|
| 1038 | const unsigned f = num_vertices(mConstraintGraph); |
---|
| 1039 | const unsigned l = num_vertices(mMultiplexSetGraph); |
---|
| 1040 | |
---|
| 1041 | // Preallocate the structures based on the size of the largest multiplex set |
---|
| 1042 | size_t max_n = 3; |
---|
| 1043 | for (unsigned s = f; s != l; ++s) { |
---|
| 1044 | max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph)); |
---|
| 1045 | } |
---|
| 1046 | const size_t max_m = log2_plus_one(max_n); |
---|
| 1047 | |
---|
| 1048 | std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n); |
---|
| 1049 | std::vector<Advance *> V(max_n); |
---|
| 1050 | std::vector<PabloAST *> muxed(max_m); |
---|
| 1051 | circular_buffer<PabloAST *> Q(max_n); |
---|
| 1052 | |
---|
| 1053 | // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set |
---|
| 1054 | // relationships of our independent sets. |
---|
| 1055 | |
---|
| 1056 | for (unsigned s = f; s != l; ++s) { |
---|
| 1057 | const size_t n = out_degree(s, mMultiplexSetGraph); |
---|
| 1058 | if (n) { |
---|
| 1059 | |
---|
| 1060 | const size_t m = log2_plus_one(n); |
---|
| 1061 | |
---|
| 1062 | graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end; |
---|
| 1063 | std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph); |
---|
| 1064 | for (unsigned i = 0; i != n; ++ei, ++i) { |
---|
| 1065 | I[i] = target(*ei, mMultiplexSetGraph); |
---|
| 1066 | assert (I[i] < mAdvance.size()); |
---|
| 1067 | } |
---|
| 1068 | std::sort(I.begin(), I.begin() + n); |
---|
| 1069 | |
---|
| 1070 | for (unsigned i = 0; i != n; ++i) { |
---|
| 1071 | V[i] = std::get<0>(mAdvance[I[i]]); |
---|
| 1072 | } |
---|
| 1073 | |
---|
| 1074 | PabloBlock * const block = V[0]->getParent(); |
---|
| 1075 | assert (block); |
---|
| 1076 | |
---|
| 1077 | // Sanity test to make sure every advance is in the same scope. |
---|
| 1078 | #ifndef NDEBUG |
---|
| 1079 | for (unsigned i = 1; i != n; ++i) { |
---|
| 1080 | assert (I[i - 1] < I[i]); |
---|
| 1081 | assert (V[i - 1] != V[i]); |
---|
| 1082 | assert (V[i]->getParent() == block); |
---|
| 1083 | } |
---|
| 1084 | #endif |
---|
| 1085 | |
---|
| 1086 | PabloBuilder pb(*block); |
---|
| 1087 | |
---|
| 1088 | /// Perform n-to-m Multiplexing |
---|
| 1089 | for (size_t j = 0; j != m; ++j) { |
---|
| 1090 | |
---|
| 1091 | assert (Q.empty()); |
---|
| 1092 | |
---|
| 1093 | std::ostringstream prefix; |
---|
| 1094 | prefix << "mux" << n << "to" << m << '_'; |
---|
| 1095 | for (size_t i = 1; i <= n; ++i) { |
---|
| 1096 | if ((i & (static_cast<size_t>(1) << j)) != 0) { |
---|
| 1097 | assert (!Q.full()); |
---|
| 1098 | PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp); |
---|
| 1099 | // prefix << '_' << V[i - 1]->getName()->to_string(); |
---|
| 1100 | Q.push_back(tmp); |
---|
| 1101 | } |
---|
| 1102 | } |
---|
| 1103 | |
---|
| 1104 | assert (Q.size() >= 1); |
---|
| 1105 | |
---|
| 1106 | Advance * const adv = V[j]; |
---|
| 1107 | // TODO: figure out a way to determine whether we're creating a duplicate value below. |
---|
| 1108 | // The expression map findOrCall ought to work conceptually but the functors method |
---|
| 1109 | // doesn't really work anymore with the current API. |
---|
| 1110 | while (Q.size() > 1) { |
---|
| 1111 | PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1); |
---|
| 1112 | PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2); |
---|
| 1113 | assert (!Q.full()); |
---|
| 1114 | pb.setInsertPoint(choose(a2, a1, adv)); |
---|
| 1115 | Q.push_back(pb.createOr(a1, a2)); |
---|
| 1116 | } |
---|
| 1117 | assert (Q.size() == 1); |
---|
| 1118 | |
---|
| 1119 | PabloAST * mux = Q.front(); Q.pop_front(); assert (mux); |
---|
| 1120 | muxed[j] = pb.createAdvance(mux, adv->getOperand(1), prefix.str()); |
---|
| 1121 | } |
---|
| 1122 | |
---|
| 1123 | |
---|
| 1124 | /// Perform m-to-n Demultiplexing |
---|
| 1125 | // Now construct the demuxed values and replaces all the users of the original advances with them. |
---|
| 1126 | for (size_t i = 1; i <= n; ++i) { |
---|
| 1127 | |
---|
| 1128 | Advance * const adv = V[i - 1]; |
---|
| 1129 | |
---|
| 1130 | pb.setInsertPoint(adv); |
---|
| 1131 | assert (Q.empty()); |
---|
| 1132 | for (size_t j = 0; j != m; ++j) { |
---|
| 1133 | if ((i & (static_cast<size_t>(1) << j)) == 0) { |
---|
| 1134 | Q.push_back(muxed[j]); |
---|
| 1135 | } |
---|
| 1136 | } |
---|
| 1137 | |
---|
| 1138 | assert (Q.size() <= m); |
---|
| 1139 | PabloAST * neg = nullptr; |
---|
| 1140 | if (LLVM_LIKELY(Q.size() > 0)) { |
---|
| 1141 | while (Q.size() > 1) { |
---|
| 1142 | PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1); |
---|
| 1143 | PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2); |
---|
| 1144 | assert (!Q.full()); |
---|
| 1145 | Q.push_back(pb.createOr(a1, a2)); |
---|
| 1146 | } |
---|
| 1147 | assert (Q.size() == 1); |
---|
| 1148 | neg = pb.createNot(Q.front()); Q.pop_front(); assert (neg); |
---|
| 1149 | } |
---|
| 1150 | |
---|
| 1151 | assert (Q.empty()); |
---|
| 1152 | for (unsigned j = 0; j != m; ++j) { |
---|
| 1153 | if ((i & (static_cast<unsigned>(1) << j)) != 0) { |
---|
| 1154 | assert (!Q.full()); |
---|
| 1155 | Q.push_back(muxed[j]); |
---|
| 1156 | } |
---|
| 1157 | } |
---|
| 1158 | |
---|
| 1159 | assert (Q.size() <= m); |
---|
| 1160 | assert (Q.size() >= 1); |
---|
| 1161 | |
---|
| 1162 | while (Q.size() > 1) { |
---|
| 1163 | PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1); |
---|
| 1164 | PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2); |
---|
| 1165 | assert (!Q.full()); |
---|
| 1166 | Q.push_back(pb.createAnd(a1, a2)); |
---|
| 1167 | } |
---|
| 1168 | |
---|
| 1169 | assert (Q.size() == 1); |
---|
| 1170 | |
---|
| 1171 | PabloAST * demux = Q.front(); Q.pop_front(); assert (demux); |
---|
| 1172 | if (LLVM_LIKELY(neg != nullptr)) { |
---|
| 1173 | demux = pb.createAnd(demux, neg); |
---|
| 1174 | } |
---|
| 1175 | V[i - 1]->replaceWith(demux, true, true); |
---|
| 1176 | } |
---|
| 1177 | } |
---|
| 1178 | } |
---|
| 1179 | } |
---|
| 1180 | |
---|
| 1181 | /** ------------------------------------------------------------------------------------------------------------- * |
---|
| 1182 | * @brief topologicalSort |
---|
| 1183 | * |
---|
| 1184 | * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set |
---|
| 1185 | * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent |
---|
| 1186 | * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and |
---|
| 1187 | * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program, |
---|
| 1188 | * it's not necessarily the original ordering. |
---|
| 1189 | ** ------------------------------------------------------------------------------------------------------------- */ |
---|
| 1190 | void BDDMinimizationPass::topologicalSort(PabloBlock & entry) const { |
---|
| 1191 | // Note: not a real topological sort. I expect the original order to be very close to the resulting one. |
---|
| 1192 | std::unordered_set<const PabloAST *> encountered; |
---|
| 1193 | std::stack<Statement *> scope; |
---|
| 1194 | for (Statement * stmt = entry.front(); ; ) { restart: |
---|
| 1195 | while ( stmt ) { |
---|
| 1196 | for (unsigned i = 0; i != stmt->getNumOperands(); ++i) { |
---|
| 1197 | PabloAST * const op = stmt->getOperand(i); |
---|
| 1198 | if (LLVM_LIKELY(isa<Statement>(op))) { |
---|
| 1199 | if (LLVM_UNLIKELY(encountered.count(op) == 0)) { |
---|
| 1200 | if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) { |
---|
| 1201 | if (encountered.count(cast<Next>(op)->getInitial()) != 0) { |
---|
| 1202 | continue; |
---|
| 1203 | } |
---|
| 1204 | } |
---|
| 1205 | Statement * const next = stmt->getNextNode(); |
---|
| 1206 | stmt->insertAfter(cast<Statement>(op)); |
---|
| 1207 | stmt = next; |
---|
| 1208 | goto restart; |
---|
| 1209 | } |
---|
| 1210 | } |
---|
| 1211 | } |
---|
| 1212 | if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) { |
---|
| 1213 | // Set the next statement to be the first statement of the inner scope and push the |
---|
| 1214 | // next statement of the current statement into the scope stack. |
---|
| 1215 | const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(); |
---|
| 1216 | scope.push(stmt->getNextNode()); |
---|
| 1217 | stmt = nested.front(); |
---|
| 1218 | continue; |
---|
| 1219 | } |
---|
| 1220 | encountered.insert(stmt); |
---|
| 1221 | stmt = stmt->getNextNode(); |
---|
| 1222 | } |
---|
| 1223 | if (scope.empty()) { |
---|
| 1224 | break; |
---|
| 1225 | } |
---|
| 1226 | stmt = scope.top(); |
---|
| 1227 | scope.pop(); |
---|
| 1228 | } |
---|
| 1229 | } |
---|
| 1230 | |
---|
| 1231 | } // end of namespace pablo |
---|
| 1232 | |
---|