Changeset 5592
 Timestamp:
 Aug 3, 2017, 12:49:20 PM (7 months ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/distributivepass.cpp
r5571 r5592 20 20 21 21 #include <pablo/optimizers/pablo_simplifier.hpp> 22 #include <pablo/analysis/pabloverifier.hpp> 22 23 23 24 #include <boost/container/flat_set.hpp> … … 32 33 #include <unordered_set> 33 34 35 #include <boost/graph/strong_components.hpp> 36 #include <llvm/Support/raw_ostream.h> 37 #include <pablo/printer_pablos.h> 38 34 39 using namespace boost; 35 40 using namespace boost::container; 36 41 using namespace llvm; 37 38 namespace pablo { 39 40 using TypeId = pablo::PabloAST::ClassTypeId; 42 using namespace pablo; 43 44 using TypeId = PabloAST::ClassTypeId; 41 45 42 46 enum class State { … … 48 52 using UsageTime = size_t; 49 53 50 using VertexData = std::tuple< pablo::PabloAST *, TypeId, State, UsageTime>;54 using VertexData = std::tuple<PabloAST *, TypeId, State, UsageTime>; 51 55 52 56 using OperandIndex = unsigned; 53 57 54 using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, OperandIndex>; 58 struct svecS{}; 59 60 namespace boost { 61 62 template<class T> 63 struct __sorted_edge_vector : public std::vector<T> { 64 using iterator = typename std::vector<T>::iterator; 65 void push_back(const T & item) { 66 std::vector<T>::insert(std::upper_bound(std::vector<T>::begin(), std::vector<T>::end(), item), item); 67 } 68 }; 69 70 template <class ValueType> struct container_gen<svecS, ValueType> { 71 typedef __sorted_edge_vector<ValueType> type; 72 }; 73 74 template <> struct parallel_edge_traits<svecS> { 75 typedef allow_parallel_edge_tag type; 76 }; 77 78 template<class T> graph_detail::vector_tag container_category(const __sorted_edge_vector<T>&) { 79 return graph_detail::vector_tag(); 80 } 81 82 template <class T> graph_detail::unstable_tag iterator_stability(const __sorted_edge_vector<T>&) { 83 return graph_detail::unstable_tag(); 84 } 85 } 86 87 namespace pablo { 88 89 using Graph = adjacency_list<svecS, vecS, bidirectionalS, VertexData, OperandIndex, vecS>; 55 90 using Vertex = Graph::vertex_descriptor; 56 using in_edge_iterator = graph_traits<Graph>::in_edge_iterator; 57 using out_edge_iterator = graph_traits<Graph>::out_edge_iterator; 58 59 using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>; 91 using Edge = Graph::edge_descriptor; 92 using InEdgeIterator = graph_traits<Graph>::in_edge_iterator; 93 using DistributionGraph = adjacency_list<setS, vecS, bidirectionalS, Vertex>; 60 94 using DistributionVertex = DistributionGraph::vertex_descriptor; 61 95 … … 66 100 using DistributionSets = std::vector<DistributionSet>; 67 101 68 using IndependentSetGraph = adjacency_list< hash_setS, vecS, undirectedS, unsigned>;102 using IndependentSetGraph = adjacency_list<vecS, vecS, undirectedS, size_t>; 69 103 70 104 struct PassContainer { … … 102 136 } 103 137 138 PassContainer() 139 : reprocessGraph(false) 140 , V{0, IdentityHash(G), IdentityComparator(G)} { 141 142 } 143 104 144 protected: 105 145 … … 122 162 * themselves. The exception is that associative instructions are regenerated w.r.t. their sequence in the AST 123 163 **  */ 124 size_t rewriteAST(PabloBlock * entry, size_t count = 0) { 125 126 for (Statement * stmt : *entry) { 164 size_t rewriteAST(PabloBlock * const entry, size_t count = 0) { 165 166 Statement * stmt = entry>front(); 167 168 while (stmt) { 127 169 128 170 const Vertex u = findVertex(stmt); 129 const auto typeId = getType(u); 130 131 // There are two main reasons to ignore a statement: (1) it's dead or regenerable and thus not of interest, 171 172 // There are two reasons to ignore a statement: (1) it's dead or regenerable and thus not of interest, 132 173 // and (2), the value in G strictly dominates the statement. Typically, if two expressions are equivalent, 133 // they're in disjoint nested scopes. When neither dominates the other, this algorithm updates G as it 134 // processes the statements. However, if one dominates the other, G must refer to the dominating statement 135 // to avoid producing an illegal AST. 136 137 if (LLVM_LIKELY(isDead(u)  isRegenerable(typeId))  LLVM_UNLIKELY(strictly_dominates(getValue(u), stmt))) { 174 // they're in disjoint nested scopes. When this occurs, they're merged into a single vertex in G to avoid 175 // redundant computations but must still be written individually in the AST. Sometimes equivalent statements 176 // are found during optimization. If one such statement dominates the other, G must refer to the dominating 177 // statement to avoid producing an illegal AST. 178 179 if (LLVM_LIKELY(isDead(u)  isRegenerable(getType(u)))) { 180 stmt = stmt>eraseFromParent(false); 138 181 continue; 182 } else if (LLVM_UNLIKELY(isModified(u) && strictly_dominates(getValue(u), stmt))) { 183 stmt = stmt>replaceWith(getValue(u)); 184 continue; 139 185 } 140 186 141 187 assert (isLive(u)); 142 assert (stmt>getClassTypeId() == typeId);188 assert (stmt>getClassTypeId() == getType(u)); 143 189 assert (hasValidOperandIndicies(u)); 144 190 assert (in_degree(u, G) == stmt>getNumOperands()); 145 191 146 in_edge_iterator ei_begin, ei_end; 147 std::tie(ei_begin, ei_end) = in_edges(u, G); 148 auto ei = ei_begin; 149 150 // For each associative operand, find the vertex that describes the operand in G 151 for (unsigned i = 0; i < stmt>getNumOperands(); ++i) { 152 153 // Does the vertex have a value and, if so, does value dominate this statement? 154 // If not, we need to regenerate it. 155 for (;;) { 156 if (ei == ei_end) { 157 ei = ei_begin; 158 } 159 if (G[*ei] == i) { 160 break; 161 } 162 ++ei; 163 } 164 165 entry>setInsertPoint(stmt>getPrevNode()); 166 167 stmt>setOperand(i, regenerateIfNecessary(stmt, entry, source(*ei, G), count)); 168 } 169 170 if (LLVM_UNLIKELY(typeId == TypeId::Assign)) { 171 setLastUsageTime(findVertex(stmt>getOperand(0)), ++count); 172 } 192 // Suppose we take a subgraph of G that contains every operand we'd have to regenerate to execute this 193 // statement? We could apply local optimizations to the subgraph with respect to the last usage time of 194 // each nonregenerated value and minimize the pairwise difference in last usage time, taking into account 195 // that we can use negations of variables when they've been used more recently. 196 197 // This could take incorporate rematerialization by determining whether it is cheaper / possible to 198 // recompute a value with what is already given but the Simplifer Pass could undo these changes if it 199 // recognizes a duplicate value in scope. 200 201 entry>setInsertPoint(stmt>getPrevNode()); 202 for (const auto e : make_iterator_range(in_edges(u, G))) { 203 stmt>setOperand(G[e], regenerateIfNecessary(stmt, entry, source(e, G), count)); 204 } 205 setValue(u, stmt); 173 206 setLastUsageTime(u, ++count); 174 setValue(u, stmt);175 207 176 208 if (isa<Branch>(stmt)) { 177 209 count = rewriteAST(cast<Branch>(stmt)>getBody(), count); 178 210 } 211 212 stmt = stmt>getNextNode(); 179 213 } 180 214 … … 187 221 * Does vertex (u) have a value and, if so, does value dominate the statement? If not, regenerate it. 188 222 **  */ 189 PabloAST * regenerateIfNecessary(Statement * const stmt, PabloBlock * const entry, const Vertex u, size_t & count) { 190 223 PabloAST * regenerateIfNecessary(Statement * const ip, PabloBlock * const entry, const Vertex u, size_t & count) { 191 224 assert (isLive(u)); 192 193 const TypeId typeId = getType(u); 194 195 PabloAST * value = isModified(u) ? nullptr : getValue(u); 196 if (LLVM_LIKELY(!dominates(value, stmt))) { 197 198 assert (isRegenerable(typeId)); 199 200 for (auto e : make_iterator_range(in_edges(u, G))) { 201 const auto v = source(e, G); 202 regenerateIfNecessary(stmt, entry, v, count); 203 assert (getValue(v)); 204 assert (dominates(getValue(v), stmt)); 205 } 206 207 if (LLVM_LIKELY(isAssociative(typeId))) { 208 209 const auto n = in_degree(u, G); 210 211 assert (n >= 2); 225 PabloAST * value = getValue(u); 226 if (!dominates(value, ip)) { 227 228 assert (isRegenerable(getType(u))); 229 230 // if the outdegree of this vertex > 1, try setting the insertion point to a dominating position? 231 232 for (const auto e : make_iterator_range(in_edges(u, G))) { 233 regenerateIfNecessary(ip, entry, source(e, G), count); 234 } 235 236 const auto n = in_degree(u, G); 237 238 if (LLVM_UNLIKELY(n == 0)) { 239 const TypeId typeId = getType(u); 240 assert (isConstant(typeId)); 241 if (typeId == TypeId::Zeroes) { 242 value = entry>createZeroes(); 243 } else { 244 value = entry>createOnes(); 245 } 246 } else if (LLVM_LIKELY(n != 1)) { 247 248 const TypeId typeId = getType(u); 249 250 assert (isAssociative(typeId)); 212 251 213 252 // Suppose we try to minimize the pairwise difference in last usage time, … … 220 259 for (auto e : make_iterator_range(in_edges(u, G))) { 221 260 input[i++] = source(e, G); 261 assert (getLastUsageTime(source(e, G)) > 0); 222 262 } 223 263 … … 226 266 }); 227 267 268 // for (unsigned i = 0; i < n; ++i) { 269 // setLastUsageTime(input[i], ++count); 270 // } 271 228 272 PabloBuilder builder(entry); 229 273 value = getValue(input[0]); 230 274 for (unsigned i = 1; i < n; ++i) { 231 PabloAST * const op = getValue(input[i]); 275 PabloAST * const op = getValue(input[i]); 232 276 switch (typeId) { 233 277 case TypeId::And: … … 244 288 } 245 289 } 246 247 } else if (typeId == TypeId::Not) {248 assert (in_degree(u, G) == 1);249 value = entry>createNot(getValue(first_source(in_edges(u, G))));250 290 } else { 251 assert (isConstant(typeId)); 252 assert (in_degree(u, G) == 0); 253 if (typeId == TypeId::Zeroes) { 254 value = entry>createZeroes(); 255 } else { 256 value = entry>createOnes(); 257 } 258 } 259 291 value = entry>createNot(getValue(getNegatedLiteral(u))); 292 } 293 assert (value); 260 294 setValue(u, value); 261 295 setUnmodified(u); 262 } 263 264 // negations inherit the last usage time from their operand 265 if (LLVM_UNLIKELY(typeId == TypeId::Not)) { 266 setLastUsageTime(u, getLastUsageTime(first_source(in_edges(u, G)))); 296 setLastUsageTime(u, ++count); 297 } 298 return value; 299 } 300 301 protected: 302 303 /**  * 304 * @brief printGraph 305 **  */ 306 void printGraph(const std::string & name, llvm::raw_ostream & out, std::vector<Vertex> restricted = {}) { 307 308 const auto n = num_vertices(G); 309 std::vector<unsigned> c(n); 310 const auto components = strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0])); 311 312 std::vector<bool> show(n, false); 313 if (LLVM_LIKELY(restricted.empty() && n == components)) { 314 for (const auto u : make_iterator_range(vertices(G))) { 315 show[u] = isLive(u); 316 } 267 317 } else { 268 setLastUsageTime(u, ++count); 269 } 270 return value; 271 } 272 273 protected: 318 std::queue<Vertex> Q; 319 for (const auto m : restricted) { 320 if (m < n && isLive(m)) { 321 show[m] = true; 322 assert (Q.empty()); 323 Q.push(m); 324 for (;;) { 325 const auto u = Q.front(); 326 Q.pop(); 327 for (auto e : make_iterator_range(in_edges(u, G))) { 328 const auto v = source(e, G); 329 if (show[v]  !isLive(v)) { 330 continue; 331 } 332 show[v] = true; 333 Q.push(v); 334 } 335 if (Q.empty()) { 336 break; 337 } 338 } 339 for (auto e : make_iterator_range(out_edges(m, G))) { 340 const auto v = target(e, G); 341 show[v] = isLive(v) ? true : show[v]; 342 } 343 } 344 } 345 } 346 347 out << "digraph " << name << " {\n"; 348 for (auto u : make_iterator_range(vertices(G))) { 349 350 if (show[u]) { 351 352 out << "v" << u << " [label=\"" << u << ": "; 353 TypeId typeId; 354 PabloAST * expr; 355 State state; 356 357 std::tie(expr, typeId, state, std::ignore) = G[u]; 358 359 bool space = true; 360 361 switch (typeId) { 362 case TypeId::And: 363 out << "(â§)"; 364 break; 365 case TypeId::Or: 366 out << "(âš)"; 367 break; 368 case TypeId::Xor: 369 out << "(â)"; 370 break; 371 case TypeId::Not: 372 out << "(Â¬)"; 373 break; 374 case TypeId::Zeroes: 375 out << "(â¥)"; 376 break; 377 case TypeId::Ones: 378 out << "(â€)"; 379 default: 380 space = false; 381 break; 382 } 383 if (expr) { 384 if (space) { 385 out << ' '; 386 } 387 expr>print(out); 388 } 389 390 out << "\""; 391 if (!hasValidOperandIndicies(u)) { 392 out << " color=red style=bold"; 393 } else if (!(isImmutable(typeId)  out_degree(u, G) > 0)) { 394 out << " color=orange style=bold"; 395 } else if (isRegenerable(typeId)) { 396 out << " color=blue"; 397 if (state == State::Modified) { 398 out << " style=dashed"; 399 } 400 } 401 out << "];\n"; 402 } 403 } 404 for (auto e : make_iterator_range(edges(G))) { 405 const auto s = source(e, G); 406 const auto t = target(e, G); 407 if (show[s] && show[t]) { 408 const auto cyclic = (c[s] == c[t]); 409 const auto nonAssoc = !isAssociative(getType(t)); 410 out << "v" << s << " > v" << t; 411 if (cyclic  nonAssoc) { 412 out << " ["; 413 if (nonAssoc) { 414 out << " label=\"" << G[e] << "\""; 415 } 416 if (cyclic) { 417 out << " color=red"; 418 } 419 out << "]"; 420 } 421 out << ";\n"; 422 } 423 } 424 425 out << "}\n\n"; 426 out.flush(); 427 } 274 428 275 429 /**  * … … 278 432 bool simplifyGraph() { 279 433 bool modified = false; 280 repeat: getReverseTopologicalOrdering(); 281 compactGraph(); 282 if (applyDistributivityLaw()) { 283 modified = true; 284 goto repeat; 285 } 286 factorizeGraph(); 434 errs() << "=================================================================\n"; 435 printGraph("S", errs()); 436 V.reserve(num_vertices(G)); 437 for (;;) { 438 V.clear(); 439 getReverseTopologicalOrdering(); 440 if (compactGraph()) { 441 continue; 442 } 443 if (applyDistributivityLaw()) { 444 modified = true; 445 continue; 446 } 447 break; 448 } 449 if (modified) { 450 factorizeGraph(); 451 errs() << "\n"; 452 printGraph("F", errs()); 453 } 287 454 return modified; 288 455 } … … 325 492 * @brief compactGraph 326 493 **  */ 327 void compactGraph() { 328 329 auto IdentityHash = [this](const Vertex u) { 330 using value_of = std::underlying_type<TypeId>::type; 331 const auto n = in_degree(u, G); 332 Vertex operands[n]; 333 unsigned i = 0; 334 for (auto e : make_iterator_range(in_edges(u, G))) { 335 operands[i++] = source(e, G); 336 } 337 std::sort(operands, operands + n); 338 size_t h = 0; 339 boost::hash_combine(h, static_cast<value_of>(getType(u))); 340 for (unsigned j = 0; j < n; ++j) { 341 boost::hash_combine(h, operands[j]); 342 } 343 return h; 344 }; 345 346 auto IdentityComparator = [this](const Vertex u, const Vertex v) { 347 const auto typeId = getType(u); 348 if (LLVM_LIKELY(typeId == getType(v))) { 349 const unsigned n = in_degree(u, G); 350 if (LLVM_UNLIKELY(n == 0)) { 351 assert (isConstant(typeId) && in_degree(v, G) == 0); 352 return true; 353 } 354 if (in_degree(v, G) == n) { 355 Vertex adjA[n]; 356 Vertex adjB[n]; 357 auto ei = std::get<0>(in_edges(u, G)); 358 auto ej = std::get<0>(in_edges(v, G)); 359 // if this is an associative op, order doesn't matter 360 if (isAssociative(typeId)) { 361 for (unsigned i = 0; i < n; ++i, ++ei, ++ej) { 362 adjA[i] = source(*ei, G); 363 adjB[i] = source(*ej, G); 364 } 365 std::sort(adjA, adjA + n); 366 std::sort(adjB, adjB + n); 367 } else { // otherwise consider the order indicated by the edges 368 for (unsigned i = 0; i < n; ++i, ++ei, ++ej) { 369 adjA[G[*ei]] = source(*ei, G); 370 adjB[G[*ej]] = source(*ej, G); 371 } 372 } 373 for (unsigned i = 0; i < n; ++i) { 374 if (adjA[i] != adjB[i]) { 375 return false; 376 } 377 } 378 return true; 379 } 380 } 381 return false; 382 }; 383 384 using IdentitySet = std::unordered_set<Vertex, decltype(IdentityHash), decltype(IdentityComparator)>; 385 386 IdentitySet V{0, IdentityHash, IdentityComparator}; 387 V.reserve(num_vertices(G)); 388 494 bool compactGraph() { 495 reprocessGraph = false; 389 496 for (const auto u : boost::adaptors::reverse(ordering)) { 390 391 assert (isLive(u)); 392 393 const auto typeId = getType(u); 394 if (LLVM_UNLIKELY(isImmutable(typeId))) { 395 continue; 396 } 397 398 assert (hasValidOperandIndicies(u)); 399 400 assert (out_degree(u, G) > 0); 401 402 if (LLVM_UNLIKELY(isConstant(typeId))) { 403 if (processConstant(u, typeId)) { 497 if (LLVM_LIKELY(isLive(u))) { 498 const auto typeId = getType(u); 499 if (LLVM_UNLIKELY(isImmutable(typeId))) { 404 500 continue; 405 501 } 406 } else if (isAssociative(typeId)) { 407 if (processAssociative(u, typeId)) { 502 assert (hasValidOperandIndicies(u)); 503 if (LLVM_UNLIKELY(out_degree(u, G) == 0)) { 504 removeVertex(u); 408 505 continue; 409 506 } 410 } else if (typeId == TypeId::Not) { 411 if (processNegation(u, typeId)) { 412 continue; 413 } 414 } 415 416 // check whether this vertex is a duplicate 417 auto f = V.insert(u); 418 if (LLVM_UNLIKELY(!f.second)) { 419 remapVertex(u, *f.first); 420 } 421 } 507 if (LLVM_UNLIKELY(isConstant(typeId))) { 508 if (processConstant(u, typeId)) { 509 continue; 510 } 511 } else if (isAssociative(typeId)) { 512 if (processAssociative(u, typeId)) { 513 continue; 514 } 515 } else if (typeId == TypeId::Not) { 516 if (processNegation(u)) { 517 continue; 518 } 519 } 520 consolidate(u); 521 } 522 } 523 return reprocessGraph; 422 524 } 423 525 … … 439 541 const auto v = first_source(in_edges(u, G)); 440 542 for (const auto e : make_iterator_range(out_edges(u, G))) { 441 addEdge(v, target(e, G), G[e]); 543 addEdge(v, target(e, G), G[e]); 442 544 } 443 545 removeVertex(u); … … 445 547 } else { 446 548 // Take the transitive closure of these arcs to reveal the underlying equations 447 Vertex removed[out_degree(u, G)]; 448 unsigned n = 0; 449 for (auto ei : make_iterator_range(out_edges(u, G))) { 450 const auto v = target(ei, G); 451 if (typeId == getType(v)) { 452 assert(hasValidOperandIndicies(v)); 453 for (auto ej : make_iterator_range(in_edges(u, G))) { 454 addEdge(source(ej, G), v, G[ei]); 455 } 456 setModified(v); 457 removed[n++] = v; 458 } 459 } 549 if (transitiveClosure(u, typeId)) { 550 return true; 551 } 552 if (LLVM_UNLIKELY(typeId == TypeId::Xor)) { 553 canonicalizeXor(u); 554 } else { // is distributive 555 applyDeMorganExpansion(u, typeId); 556 if (LLVM_UNLIKELY(applyAbsorbtionComplementLaw(u, typeId))) { 557 return true; 558 } 559 } 560 } 561 return false; 562 } 563 564 /**  * 565 * @brief transitiveClosure 566 **  */ 567 bool transitiveClosure(const Vertex u, const TypeId typeId) { 568 // Take the transitive closure of these arcs to reveal the underlying equations 569 570 assert (isLive(u)); 571 assert (getType(u) == typeId); 572 assert (isAssociative(typeId)); 573 574 Vertex removed[out_degree(u, G)]; 575 unsigned n = 0; 576 for (auto ei : make_iterator_range(out_edges(u, G))) { 577 const auto v = target(ei, G); 578 if (getType(v) == typeId) { 579 assert(hasValidOperandIndicies(v)); 580 for (auto ej : make_iterator_range(in_edges(u, G))) { 581 addEdge(source(ej, G), v); 582 } 583 setModified(v); 584 removed[n++] = v; 585 } 586 } 587 for (unsigned i = 0; i < n; ++i) { 588 const auto v = removed[i]; 589 assert (edge(u, v, G).second); 590 remove_edge(u, v, G); 591 assert(hasValidOperandIndicies(v)); 592 } 593 if (out_degree(u, G) == 0) { 594 removeVertex(u); 595 return true; 596 } 597 return false; 598 } 599 600 /**  * 601 * @brief canonicalizeXor 602 * 603 * (A â Â¬B) = (A â B â 1) = Â¬(A â B) 604 **  */ 605 void canonicalizeXor(const Vertex u) { 606 607 assert (isLive(u)); 608 assert (getType(u) == TypeId::Xor); 609 610 const auto l = in_degree(u, G); 611 Vertex negation[l]; 612 unsigned n = 0, m = 0; 613 for (const auto e : make_iterator_range(in_edges(u, G))) { 614 const auto v = source(e, G); 615 const auto typeId = getType(v); 616 if (LLVM_UNLIKELY(typeId == TypeId::Not)) { 617 negation[n++] = v; 618 } else if (LLVM_UNLIKELY(typeId == TypeId::Ones)) { 619 negation[l  ++m] = v; 620 } 621 } 622 if (LLVM_UNLIKELY(n != 0  m != 0)) { 460 623 for (unsigned i = 0; i < n; ++i) { 461 const auto v = removed[i]; 462 assert (edge(u, v, G).second); 463 remove_edge(u, v, G); 464 assert(hasValidOperandIndicies(v)); 465 } 466 if (LLVM_UNLIKELY(out_degree(u, G) == 0)) { 467 removeVertex(u); 468 return true; 469 } 470 if (LLVM_UNLIKELY(typeId == TypeId::Xor)) { 471 // Canonicalize xor operations: (A â Â¬B) = (A â B â 1) 472 Vertex negation[in_degree(u, G)]; 473 unsigned count = 0; 474 for (const auto e : make_iterator_range(in_edges(u, G))) { 475 const auto v = source(e, G); 476 if (LLVM_UNLIKELY(getType(v) == TypeId::Not)) { 477 negation[count++] = v; 478 } 479 } 480 if (LLVM_UNLIKELY(count != 0)) { 481 for (unsigned i = 0; i < count; ++i) { 482 const auto v = negation[i]; 483 assert (edge(v, u, G).second); 484 remove_edge(v, u, G); 485 addEdge(first_source(in_edges(v, G)), u); 486 } 487 if ((count & 1) != 0) { 488 addEdge(makeVertex(TypeId::Ones), u); 489 } 490 setModified(u); 491 assert(hasValidOperandIndicies(u)); 492 } 493 } else { // perform De Morgan's law expansion 494 applyDeMorgans(u, typeId); 495 return applyAbsorbtionComplementLaw(u, typeId); 496 } 497 } 498 return false; 624 const auto v = negation[i]; 625 assert (edge(v, u, G).second); 626 remove_edge(v, u, G); 627 addEdge(first_source(in_edges(v, G)), u); 628 } 629 for (unsigned i = 0; i < m; ++i) { 630 const auto v = negation[(l  1)  i]; 631 assert (edge(v, u, G).second); 632 remove_edge(v, u, G); 633 } 634 if (((n + m) & 1) != 0) { 635 const auto x = makeVertex(TypeId::Not); 636 for (const auto e : make_iterator_range(out_edges(u, G))) { 637 add_edge(x, target(e, G), G[e], G); 638 } 639 clear_out_edges(u, G); 640 add_edge(u, x, 0, G); 641 } 642 setModified(u); 643 assert(hasValidOperandIndicies(u)); 644 } 499 645 } 500 646 … … 502 648 * @brief processNegation 503 649 **  */ 504 bool processNegation(const Vertex u , const TypeId typeId) {650 bool processNegation(const Vertex u) { 505 651 506 652 assert (isLive(u)); 507 653 assert ("negation must have one input!" && in_degree(u, G) == 1); 508 assert (getType(u) == typeId); 509 assert (typeId == TypeId::Not); 654 assert (getType(u) == TypeId::Not); 510 655 511 656 const auto v = first_source(in_edges(u, G)); 512 657 const auto negatedTypeId = getType(v); 513 658 if (LLVM_UNLIKELY(negatedTypeId == TypeId::Not)) { // Â¬Â¬A = A 514 const auto w = first_source(in_edges(v, G));659 const auto w = getNegatedLiteral(v); 515 660 for (const auto e : make_iterator_range(out_edges(u, G))) { 516 661 const auto v = target(e, G); … … 520 665 removeVertex(u); 521 666 return true; 522 } else if (LLVM_UNLIKELY(negatedTypeId == TypeId::Xor)) {523 // Canonicalize xor operations: Â¬(A â B) = (A â B â 1)524 setModified(u);525 setType(u, TypeId::Xor);526 clear_in_edges(u, G);527 for (const auto e : make_iterator_range(in_edges(v, G))) {528 add_edge(source(e, G), u, 0, G);529 }530 addEdge(makeVertex(TypeId::Ones), u);531 assert(hasValidOperandIndicies(u));532 667 } 533 668 return false; … … 535 670 536 671 /**  * 537 * @brief applyDeMorgan s538 **  */ 539 void applyDeMorgans(const Vertex u, const TypeId typeId) {672 * @brief applyDeMorganExpansion 673 **  */ 674 bool applyDeMorganExpansion(const Vertex u, const TypeId typeId) { 540 675 541 676 assert (isLive(u)); … … 549 684 const auto v = source(e, G); 550 685 if (LLVM_UNLIKELY(getType(v) == TypeId::Not)) { 551 const auto w = first_source(in_edges(v, G)); 552 if (LLVM_UNLIKELY(getType(w) == oppositeTypeId(typeId))) { 686 if (LLVM_UNLIKELY(isDistributive(getType(getNegatedLiteral(v))))) { 553 687 A[n++] = v; 554 688 } … … 562 696 assert (getType(v) == TypeId::Not); 563 697 remove_edge(v, u, G); 564 // NOTE: we cannot remove v even if this was its last edge since 565 // it must be in our duplicate check map 566 const auto w = first_source(in_edges(v, G)); 567 assert (getType(w) == oppositeTypeId(typeId)); 698 const auto w = getNegatedLiteral(v); 699 auto x = u; 700 const auto innerTypeId = oppositeTypeId(getType(w)); 701 if (innerTypeId != typeId) { 702 x = makeVertex(innerTypeId); 703 add_edge(x, u, 0, G); 704 } 568 705 for (const auto e : make_iterator_range(in_edges(w, G))) { 569 const auto x = makeVertex(TypeId::Not); 570 add_edge(source(e, G), x, 0, G); 571 addEdge(x, u); 706 addEdge(getNegationOf(source(e, G)), x); 572 707 } 573 708 } 574 709 setModified(u); 710 reprocessGraph = true; 575 711 assert(hasValidOperandIndicies(u)); 576 } 577 712 return true; 713 } 714 return false; 715 } 716 717 /**  * 718 * @brief applyXorTransformation 719 * 720 * (A â§ Â¬B â§ C) âš (Â¬A â§ B â§ D) â (A â B) â§ ((A â§ C) âš (B â§ D)) 721 * 722 * (A âš Â¬B âš C) â§ (Â¬A âš B âš D) â Â¬(A â B) âš ((A âš C) â§ (B âš D)) 723 **  */ 724 bool applyXorTransformation() { 725 reprocessGraph = false; 726 for (const auto u : ordering) { 727 const auto typeId = getType(u); 728 if (isDistributive(typeId)) { 729 if (LLVM_LIKELY(in_degree(u, G) > 1)) { 730 while (LLVM_UNLIKELY(applyXorTransformation(u, typeId))); 731 } 732 } 733 } 734 return reprocessGraph; 735 } 736 737 /**  * 738 * @brief applyXorTransformation 739 * 740 * (A â§ Â¬B â§ C) âš (Â¬A â§ B â§ D) â (A â B) â§ ((A â§ C) âš (B â§ D)) 741 * 742 * (A âš Â¬B âš C) â§ (Â¬A âš B âš D) â Â¬(A â B) âš ((A âš C) â§ (B âš D)) 743 **  */ 744 bool applyXorTransformation(const Vertex u, const TypeId typeId) { 745 746 if (in_degree(u, G) != 2) { 747 return false; 748 } 749 750 unsigned clauses = 0; 751 unsigned count = 0; 752 assert (getType(u) == typeId); 753 const TypeId innerTypeId = oppositeTypeId(typeId); 754 assert (in_degree(u, G) > 1); 755 756 for (const auto e : make_iterator_range(in_edges(u, G))) { 757 const auto v = source(e, G); 758 if (isXorCandidate(v, innerTypeId)) { 759 ++clauses; 760 count += in_degree(v, G); 761 } 762 } 763 764 if (clauses > 1) { 765 unsigned B[clauses + 1]; 766 Vertex C[clauses]; 767 Vertex V[count]; 768 769 unsigned i = 0, j = 0; 770 771 for (const auto e : make_iterator_range(in_edges(u, G))) { 772 const auto v = source(e, G); 773 if (isXorCandidate(v, innerTypeId)) { 774 B[i] = j; 775 C[i] = v; 776 for (const auto e : make_iterator_range(in_edges(v, G))) { 777 V[j++] = source(e, G); 778 } 779 // We know no clause contains {A, A}, {A, Â¬A} or {Â¬Â¬A} for any A. 780 std::sort(V + B[i++], V + j, [this](const Vertex u, const Vertex v){ 781 return removeNegation(u) < removeNegation(v); 782 }); 783 } 784 } 785 B[clauses] = j; 786 787 for (unsigned i = 0; i < (clauses  1); ++i) { 788 for (unsigned j = (i + 1); j < clauses; ++j) { 789 bool first = true; 790 unsigned ei = B[i], ej = B[j], ek = 0; 791 while (ei < B[i + 1] && ej < B[j + 1]) { 792 if (V[ei] == V[ej]) { 793 ++ei, ++ej; 794 } else { 795 if (LLVM_UNLIKELY(isNegationOf(V[ei], V[ej]))) { 796 if (LLVM_LIKELY(first)) { 797 ek = ei; 798 first = false; 799 ++ei, ++ej; 800 continue; 801 } else { 802 const auto x = V[ek]; 803 const auto v = C[i]; 804 const auto y = V[ej]; 805 const auto w = C[j]; 806 807 reprocessGraph = true; 808 809 assert (edge(x, v, G).second); 810 remove_edge(x, v, G); 811 assert (edge(y, w, G).second); 812 remove_edge(y, w, G); 813 814 const auto a = makeVertex(typeId); 815 add_edge(v, a, 0, G); 816 add_edge(w, a, 0, G); 817 818 const auto z = makeVertex(TypeId::Xor); 819 add_edge(x, z, 0, G); 820 add_edge(y, z, 0, G); 821 822 auto b = z; 823 if (LLVM_UNLIKELY(typeId == TypeId::And)) { 824 b = getNegationOf(z); 825 } 826 canonicalizeXor(z); 827 if (LLVM_UNLIKELY(b != z)) { 828 processNegation(b); 829 } 830 831 if (in_degree(u, G) == 2) { 832 clear_in_edges(u, G); 833 setType(u, innerTypeId); 834 add_edge(a, u, 0, G); 835 add_edge(b, u, 0, G); 836 return false; 837 } else { 838 assert (edge(v, u, G).second); 839 remove_edge(v, u, G); 840 assert (edge(w, u, G).second); 841 remove_edge(w, u, G); 842 const auto c = makeVertex(innerTypeId); 843 add_edge(a, c, 0, G); 844 add_edge(b, c, 0, G); 845 add_edge(c, u, 0, G); 846 assert (in_degree(u, G) > 1); 847 return true; 848 } 849 } 850 } 851 if (removeNegation(V[ei]) < removeNegation(V[ej])) { 852 ++ei; 853 } else { 854 ++ej; 855 } 856 } 857 } 858 } 859 } 860 } 861 return false; 862 } 863 864 bool isXorCandidate(const Vertex u, const TypeId typeId) const { 865 assert (isAssociative(typeId)); 866 return (getType(u) == typeId) && (out_degree(u, G) == 1) && (in_degree(u, G) > 1); 867 } 868 869 bool isNegationOf(const Vertex u, const Vertex v) const { 870 const auto t = (getType(u) == TypeId::Not); 871 if (t ^ (getType(v) == TypeId::Not)) { 872 if (t) { 873 return getNegatedLiteral(u) == v; 874 } else { // if (getType(y) == TypeId::Not) { 875 return u == getNegatedLiteral(v); 876 } 877 } 878 return false; 879 } 880 881 /**  * 882 * @brief getNegationOf 883 **  */ 884 Vertex getNegationOf(const Vertex u) { 885 if (getType(u) == TypeId::Not) { 886 return getNegatedLiteral(u); 887 } else { 888 for (const auto e : make_iterator_range(out_edges(u, G))) { 889 const auto v = target(e, G); 890 if (getType(v) == TypeId::Not) { 891 return v; 892 } 893 } 894 const auto v = makeVertex(TypeId::Not); 895 add_edge(u, v, 0, G); 896 return v; 897 } 898 } 899 900 Vertex getNegatedLiteral(const Vertex u) const { 901 assert (getType(u) == TypeId::Not); 902 assert (in_degree(u, G) == 1); 903 return first_source(in_edges(u, G)); 904 } 905 906 Vertex removeNegation(const Vertex u) const { 907 return getType(u) == TypeId::Not ? getNegatedLiteral(u) : u; 578 908 } 579 909 … … 595 925 const auto innerTypeId = getType(v); 596 926 if (innerTypeId == TypeId::Not) { 597 const auto w = first_source(in_edges(v, G));927 const auto w = getNegatedLiteral(v); 598 928 assert (isLive(w)); 599 929 for (const auto ej : make_iterator_range(in_edges(u, G))) { … … 613 943 if (n) { 614 944 setModified(u); 945 reprocessGraph = true; 615 946 for (;;) { 616 947 const auto v = A[n]; … … 717 1048 setModified(v); 718 1049 clear_in_edges(v, G); 719 // We could recursively call "processConstant" but this could cause a stack overflow720 // in a pathological case. Instead rely on the fact v will be processed eventually.721 1050 } 722 1051 … … 728 1057 return false; 729 1058 } 730 731 1059 732 1060 /**  * … … 760 1088 const auto upperSet = obtainDistributableSources(std::get<1>(lower)); 761 1089 for (const auto & upper : upperSet) { 1090 762 1091 const auto & inner = std::get<0>(upper); 763 1092 const auto & sources = std::get<1>(upper); … … 767 1096 768 1097 // Update G to match the desired change 769 constauto x = makeVertex(outerTypeId);770 constauto y = makeVertex(innerTypeId);1098 auto x = makeVertex(outerTypeId); 1099 auto y = makeVertex(innerTypeId); 771 1100 772 1101 for (const Vertex i : sources) { … … 778 1107 remove_edge(u, v, G); 779 1108 } 780 add Edge(u, y);781 } 782 1109 add_edge(u, y, 0, G); 1110 } 1111 y = consolidate(y); 783 1112 for (const auto i : inner) { 784 1113 const auto u = Gd[i]; … … 790 1119 remove_edge(u, v, G); 791 1120 } 792 add Edge(u, x);793 } 794 1121 add_edge(u, x, 0, G); 1122 } 1123 x = consolidate(x); 795 1124 addEdge(x, y); 796 797 1125 for (const Vertex i : outer) { 798 1126 const auto u = Gd[i]; … … 801 1129 addEdge(y, u); 802 1130 } 803 804 1131 modified = true; 805 1132 } … … 824 1151 if (isDistributive(outerTypeId)) { 825 1152 const auto n = in_degree(u, G); 1153 if (n < 2) continue; 826 1154 assert (n > 1); 827 1155 const auto innerTypeId = oppositeTypeId(getType(u)); … … 908 1236 void factorizeGraph() { 909 1237 910 Sequence groups[3];1238 Sequence associative; 911 1239 for (const auto u : make_iterator_range(vertices(G))) { 912 if (isLive(u)) { 913 switch (getType(u)) { 914 case TypeId::And: 915 groups[0].push_back(u); break; 916 case TypeId::Or: 917 groups[1].push_back(u); break; 918 case TypeId::Xor: 919 groups[2].push_back(u); break; 920 default: break; 921 } 922 } 923 } 924 925 const TypeId op[3] = { TypeId::And, TypeId::Or, TypeId::Xor }; 926 927 for (unsigned i = 0; i < 3; ++i) { 928 929 // Although we risk losing better combinations by greedily taking the larger factorings, 930 // choosing only those of minSize or greater first can significantly reduce the running 931 // time of this optimization. 932 933 for (unsigned minSize = 64; minSize >= 2; minSize /= 2) { 934 935 for (;;) { 936 937 auto factors = makeIndependent(enumerateBicliques(groups[i], G, 2, minSize), 1); 938 if (factors.empty()) { 939 break; 940 } 941 942 for (auto & factor : factors) { 943 const auto & sources = std::get<1>(factor); 944 assert (sources.size() > 1); 945 auto & targets = std::get<0>(factor); 946 assert (targets.size() > 1); 947 948 // Check whether one of the targets is the factorization 949 Vertex x = 0; 950 bool create = true; 951 for (auto j = targets.begin(); j != targets.end(); ) { 952 assert (hasValidOperandIndicies(*j)); 953 if (in_degree(*j, G) == sources.size()) { 954 if (LLVM_LIKELY(create)) { 955 x = *j; 956 create = false; 957 } else { 958 for (auto e : make_iterator_range(out_edges(*j, G))) { 959 addEdge(x, target(e, G), G[e]); 960 } 961 removeVertex(*j); 962 } 963 j = targets.erase(j); 964 } else { 965 ++j; 1240 if (isLive(u) && isAssociative(getType(u))) { 1241 associative.push_back(u); 1242 } 1243 } 1244 1245 // Although we risk losing better combinations by greedily taking the larger factorings, 1246 // choosing only those of minSize or greater first can significantly reduce the running 1247 // time of this optimization. 1248 1249 Sequence group[3]; 1250 1251 const TypeId typeCode[3] = { TypeId::And, TypeId::Or, TypeId::Xor }; 1252 1253 for (;;) { 1254 1255 auto factors = makeIndependent(enumerateBicliques(associative, G, 2, 2), 1); 1256 if (factors.empty()) { 1257 break; 1258 } 1259 1260 bool unchanged = true; 1261 1262 for (auto & factor : factors) { 1263 const auto & sources = std::get<1>(factor); 1264 assert (sources.size() > 1); 1265 auto & targets = std::get<0>(factor); 1266 assert (targets.size() > 1); 1267 1268 for (unsigned k = 0; k < 3; ++k) { 1269 assert (group[k].empty()); 1270 } 1271 1272 // Group the target sets and check whether any target is the factorization 1273 Vertex t[3]; 1274 bool create[3] = { true, true, true }; 1275 for (const auto u : targets) { 1276 assert (hasValidOperandIndicies(u)); 1277 const auto k = factorGroup(getType(u)); 1278 if (LLVM_UNLIKELY(in_degree(u, G) == sources.size())) { 1279 if (LLVM_LIKELY(create[k])) { 1280 t[k] = u; 1281 create[k] = false; 1282 } else { 1283 for (auto e : make_iterator_range(out_edges(u, G))) { 1284 addEdge(t[k], target(e, G), G[e]); 966 1285 } 1286 removeVertex(u); 967 1287 } 968 if (create) { 969 x = makeVertex(op[i]); 970 groups[i].push_back(x); 971 for (auto u : sources) { 972 add_edge(u, x, 0, G); 973 } 974 assert (hasValidOperandIndicies(x)); 1288 } else { 1289 group[k].push_back(u); 1290 } 1291 } 1292 1293 for (unsigned k = 0; k < 3; ++k) { 1294 if (LLVM_LIKELY(group[k].empty())) { 1295 continue; 1296 } 1297 if (LLVM_LIKELY(create[k])) { 1298 t[k] = makeVertex(typeCode[k]); 1299 for (auto u : sources) { 1300 add_edge(u, t[k], 0, G); 975 1301 } 976 977 // Remove the biclique between the source and target vertices 978 for (auto u : sources) { 979 for (auto v : targets) { 980 assert (getType(v) == op[i]); 981 assert (edge(u, v, G).second); 982 boost::remove_edge(u, v, G); 983 } 1302 associative.push_back(t[k]); 1303 } 1304 assert (hasValidOperandIndicies(t[k])); 1305 // Remove the biclique between the source and target vertices 1306 for (auto u : sources) { 1307 for (auto v : group[k]) { 1308 assert (getType(v) == typeCode[k]); 1309 assert (edge(u, v, G).second); 1310 boost::remove_edge(u, v, G); 984 1311 } 985 986 // ... and replace it with the factorization 987 for (auto v : targets) { 988 assert (getType(v) == op[i]); 989 addEdge(x, v); 990 setModified(v); 991 assert(hasValidOperandIndicies(v)); 992 } 993 } 994 } 995 } 996 } 997 } 1312 } 1313 // ... and replace it with the factorization 1314 for (auto v : group[k]) { 1315 assert (getType(v) == typeCode[k]); 1316 addEdge(t[k], v); 1317 setModified(v); 1318 assert(hasValidOperandIndicies(v)); 1319 } 1320 group[k].clear(); 1321 unchanged = false; 1322 } 1323 } 1324 1325 if (unchanged) { 1326 break; 1327 } 1328 } 1329 1330 // #ifndef NDEBUG 1331 // for (const auto u : make_iterator_range(vertices(G))) { 1332 // if (LLVM_LIKELY(isLive(u))) { 1333 // const auto typeId = getType(u); 1334 // if (isAssociative(typeId)) { 1335 // if (in_degree(u, G) != 2) { 1336 // bool atMostOneSourceVertexCanHaveAnOutDegreeOverOne = true; 1337 // for (auto e : make_iterator_range(in_edges(u, G))) { 1338 // if (out_degree(source(e, G), G) != 1) { 1339 // assert (atMostOneSourceVertexCanHaveAnOutDegreeOverOne); 1340 // atMostOneSourceVertexCanHaveAnOutDegreeOverOne = false; 1341 // } 1342 // } 1343 // } 1344 // } 1345 // } 1346 // } 1347 // #endif 1348 1349 } 1350 1351 unsigned factorGroup(const TypeId typeId) { 1352 switch (typeId) { 1353 case TypeId::And: 1354 return 0; break; 1355 case TypeId::Or: 1356 return 1; break; 1357 case TypeId::Xor: 1358 return 2; break; 1359 default: llvm_unreachable("impossible"); 1360 } 1361 } 1362 1363 // /**  * 1364 // * @brief applyDeMorganContraction 1365 // **  */ 1366 // bool applyDeMorganContraction(const Vertex u, const TypeId typeId) { 1367 1368 // assert (isLive(u)); 1369 // assert (in_degree(u, G) > 0); 1370 // assert (getType(u) == typeId); 1371 // assert (isDistributive(typeId)); 1372 1373 // Vertex T[in_degree(u, G)]; 1374 // unsigned n = 0; 1375 // for (const auto e : make_iterator_range(in_edges(u, G))) { 1376 // const auto v = source(e, G); 1377 // if (getType(v) == TypeId::Not) { 1378 // T[n++] = v; 1379 // } 1380 // } 1381 // if (LLVM_UNLIKELY(n > 1)) { 1382 // const auto oppositeType = oppositeTypeId(typeId); 1383 // Vertex x = makeVertex(oppositeType); 1384 // for (unsigned i = 0; i < n; ++i) { 1385 // const auto v = T[i]; 1386 // const auto w = first_source(in_edges(v, G)); 1387 // add_edge(w, x, 0, G); 1388 // remove_edge(v, u, G); 1389 // } 1390 // x = consolidate(x); 1391 // if (in_degree(u, G) == 0) { 1392 // setType(u, TypeId::Not); 1393 // add_edge(x, u, 0, G); 1394 // processNegation(u); 1395 // return true; 1396 // } else { 1397 // Vertex y = makeVertex(TypeId::Not); 1398 // add_edge(x, y, 0, G); 1399 // y = consolidate(y); 1400 // add_edge(y, u, 0, G); 1401 // processNegation(y); 1402 // } 1403 // return processAssociative(x, oppositeType); 1404 // } 1405 // return false; 1406 // } 1407 998 1408 999 1409 private: … … 1029 1439 } 1030 1440 if (B.size() >= minimumSizeB) { 1031 std::sort(B.begin(), B.end()); 1032 assert(std::unique(B.begin(), B.end()) == B.end()); 1441 // std::sort(B.begin(), B.end()); 1442 assert (std::is_sorted(B.begin(), B.end())); 1443 assert (std::unique(B.begin(), B.end()) == B.end()); 1033 1444 B1.insert(std::move(B)); 1034 1445 } … … 1091 1502 T.push_back(target(e, G)); 1092 1503 } 1093 std::sort(T.begin(), T.end()); 1094 assert(std::unique(T.begin(), T.end()) == T.end()); 1504 // std::sort(T.begin(), T.end()); 1505 assert (std::is_sorted(T.begin(), T.end())); 1506 assert (std::unique(T.begin(), T.end()) == T.end()); 1095 1507 Aj.clear(); 1096 1508 Aj.reserve(std::min(Ai.size(), T.size())); … … 1118 1530 1119 1531 const auto l = S.size(); 1120 IndependentSetGraph I(l);1121 1122 1532 assert (independentSide < 2); 1123 1124 // Initialize our weights 1125 for (unsigned i = 0; i != l; ++i) { 1126 I[i] = std::get<0>(S[i]).size() * std::get<1>(S[i]).size(); 1127 } 1128 1129 // Determine our constraints 1130 for (unsigned i = 0; i != l; ++i) { 1131 const auto & Si = (independentSide == 0) ? std::get<0>(S[i]) : std::get<1>(S[i]); 1132 for (unsigned j = i + 1; j != l; ++j) { 1133 const auto & Sj = (independentSide == 0) ? std::get<0>(S[j]) : std::get<1>(S[j]); 1134 if (intersects(Si, Sj)) { 1135 boost::add_edge(i, j, I); 1136 } 1137 } 1138 } 1139 1140 // Use the greedy algorithm to choose our independent set 1141 Sequence selected; 1142 for (;;) { 1143 unsigned w = 0; 1144 Vertex u = 0; 1533 if (LLVM_LIKELY(l > 1)) { 1534 1535 IndependentSetGraph I(l); 1536 1537 // Initialize our weights 1145 1538 for (unsigned i = 0; i != l; ++i) { 1146 if (I[i] > w) { 1147 w = I[i]; 1148 u = i; 1149 } 1150 } 1151 if (LLVM_UNLIKELY(w == 0)) break; 1152 selected.push_back(u); 1153 I[u] = 0; 1154 for (auto v : make_iterator_range(adjacent_vertices(u, I))) { 1155 I[v] = 0; 1156 } 1157 } 1158 1159 // Sort the selected list and then remove the unselected cliques 1160 std::sort(selected.begin(), selected.end(), std::greater<Vertex>()); 1161 auto end = S.end(); 1162 for (const unsigned offset : selected) { 1163 end = S.erase(S.begin() + offset + 1, end)  1; 1164 } 1165 S.erase(S.begin(), end); 1539 I[i] = std::get<0>(S[i]).size() * std::get<1>(S[i]).size(); 1540 } 1541 1542 // Determine our constraints 1543 for (unsigned i = 0; i != l; ++i) { 1544 const auto & Si = (independentSide == 0) ? std::get<0>(S[i]) : std::get<1>(S[i]); 1545 for (unsigned j = i + 1; j != l; ++j) { 1546 const auto & Sj = (independentSide == 0) ? std::get<0>(S[j]) : std::get<1>(S[j]); 1547 if (intersects(Si, Sj)) { 1548 boost::add_edge(i, j, I); 1549 } 1550 } 1551 } 1552 1553 // Use the greedy algorithm to choose our independent set 1554 Sequence selected; 1555 for (;;) { 1556 Vertex u = 0; 1557 auto w = I[0]; 1558 for (unsigned i = 1; i != l; ++i) { 1559 if (I[i] > w) { 1560 w = I[i]; 1561 u = i; 1562 } 1563 } 1564 if (LLVM_UNLIKELY(w == 0)) break; 1565 selected.push_back(u); 1566 I[u] = 0; 1567 for (auto v : make_iterator_range(adjacent_vertices(u, I))) { 1568 I[v] = 0; 1569 } 1570 } 1571 1572 // Sort the selected list and then remove the unselected cliques 1573 std::sort(selected.begin(), selected.end(), std::greater<Vertex>()); 1574 auto end = S.end(); 1575 for (const unsigned offset : selected) { 1576 end = S.erase(S.begin() + offset + 1, end)  1; 1577 } 1578 S.erase(S.begin(), end); 1579 } 1166 1580 1167 1581 return std::move(S); … … 1172 1586 **  */ 1173 1587 Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) { 1588 reprocessGraph = true; 1174 1589 return add_vertex(std::make_tuple(expr, typeId, expr ? State::Live : State::Modified, 0), G); 1175 1590 } … … 1214 1629 M.emplace(stmt, w); 1215 1630 return w; 1631 // } else if (LLVM_UNLIKELY(typeId == TypeId::Xor)) { 1632 // assert (stmt>getNumOperands() == 2); 1633 // const auto a = addExpression(stmt>getOperand(0)); 1634 // const auto b = addExpression(stmt>getOperand(1)); 1635 // const auto c = makeVertex(TypeId::Not); 1636 // add_edge(b, c, 0, G); 1637 // const auto d = makeVertex(TypeId::Not); 1638 // add_edge(a, d, 0, G); 1639 // const auto u = makeVertex(TypeId::And); 1640 // add_edge(a, u, 0, G); 1641 // add_edge(c, u, 1, G); 1642 // const auto v = makeVertex(TypeId::And); 1643 // add_edge(b, v, 0, G); 1644 // add_edge(d, v, 1, G); 1645 // const auto w = makeVertex(TypeId::Or); 1646 // add_edge(u, w, 0, G); 1647 // add_edge(v, w, 1, G); 1648 // M.emplace(stmt, w); 1649 // return w; 1216 1650 } else { 1217 const auto u = makeVertex(typeId, stmt);1651 const auto u = makeVertex(typeId, isRegenerable(typeId) ? nullptr : stmt); 1218 1652 for (unsigned i = 0; i != stmt>getNumOperands(); ++i) { 1219 1653 PabloAST * const op = stmt>getOperand(i); … … 1237 1671 for (const auto e : make_iterator_range(out_edges(u, G))) { 1238 1672 if (LLVM_UNLIKELY(target(e, G) == v)) { 1239 if (LLVM_LIKELY(isDistributive(typeId))) { 1240 G[e] = std::max(G[e], index); 1241 } else { 1673 if (LLVM_UNLIKELY(typeId == TypeId::Xor)) { 1242 1674 remove_edge(e, G); 1243 1675 } … … 1250 1682 } 1251 1683 1252 #ifndef NDEBUG1253 1684 /**  * 1254 1685 * @brief hasValidOperandIndicies … … 1337 1768 return isConstant(typeId)  isLiteral(typeId); 1338 1769 } 1339 #endif1340 1770 1341 1771 /**  * … … 1344 1774 void removeVertex(const Vertex u) { assert (isLive(u)); 1345 1775 setDead(u); 1776 Vertex D[in_degree(u, G)]; 1777 unsigned n = 0; 1778 for (const auto e : make_iterator_range(in_edges(u, G))) { 1779 const auto v = source(e, G); 1780 if (LLVM_UNLIKELY(out_degree(v, G) == 1)) { 1781 D[n++] = v; 1782 } 1783 } 1784 while (LLVM_UNLIKELY(n != 0)) { 1785 removeVertex(D[n]); 1786 } 1346 1787 clear_vertex(u, G); 1347 } 1348 1349 /**  * 1350 * @brief remapVertex 1351 **  */ 1352 void remapVertex(const Vertex u, const Vertex v) { assert (u != v); 1788 reprocessGraph = true; 1789 } 1790 1791 /**  * 1792 * @brief consolidate 1793 **  */ 1794 Vertex consolidate(const Vertex u) { 1795 assert (isLive(u)); 1796 assert (hasValidOperandIndicies(u)); 1797 const auto f = V.insert(u); 1798 if (LLVM_UNLIKELY(f.second)) { 1799 return u; 1800 } 1801 const auto v = *f.first; 1802 assert (u != v); 1803 assert (isLive(v)); 1353 1804 const PabloAST * expr = getValue(u); 1354 1805 if (expr) { 1806 assert (!isRegenerable(getType(u))); 1355 1807 auto f = M.find(expr); 1356 1808 assert (f != M.end() && f>second == u); 1357 1809 f>second = v; 1358 1810 setValue(v, nullptr); 1811 setModified(v); 1359 1812 } 1360 1813 for (const auto e : make_iterator_range(out_edges(u, G))) { … … 1362 1815 } 1363 1816 removeVertex(u); 1817 return v; 1364 1818 } 1365 1819 … … 1414 1868 } 1415 1869 1416 TypeId getType(const Vertex u) const{1870 static TypeId getType(const Vertex u, const Graph & G) { 1417 1871 assert (u < num_vertices(G)); 1418 1872 return std::get<1>(G[u]); 1873 } 1874 1875 TypeId getType(const Vertex u) const { 1876 return getType(u, G); 1419 1877 } 1420 1878 … … 1424 1882 } 1425 1883 1426 PabloAST * getValue(const Vertex u) const{1884 static PabloAST * getValue(const Vertex u, const Graph & G) { 1427 1885 assert (u < num_vertices(G)); 1428 1886 return std::get<0>(G[u]); 1887 } 1888 1889 PabloAST * getValue(const Vertex u) const { 1890 return getValue(u, G); 1429 1891 } 1430 1892 … … 1455 1917 1456 1918 void setModified(const Vertex u) { 1457 assert(!isImmutable(getType(u)));1458 1919 setState(u, State::Modified); 1459 1920 } … … 1476 1937 void setLastUsageTime(const Vertex u, const UsageTime time) { 1477 1938 assert (u < num_vertices(G)); 1939 1940 // errs() << " " << u << " "; 1941 // PabloPrinter::print(getValue(u), errs()); 1942 // errs() << " @ " << time << "\n"; 1943 1944 1478 1945 std::get<3>(G[u]) = time; 1479 1946 } … … 1539 2006 } 1540 2007 1541 Vertex first_source(const std::pair< in_edge_iterator, in_edge_iterator> & e) const {2008 Vertex first_source(const std::pair<InEdgeIterator, InEdgeIterator> & e) const { 1542 2009 return source(*std::get<0>(e), G); 1543 2010 } 1544 2011 1545 2012 private: 2013 2014 struct IdentityHash { 2015 size_t operator()(const Vertex u) const { 2016 using value_of = std::underlying_type<TypeId>::type; 2017 // InEdgeIterator begin, end; 2018 // std::tie(begin, end) = in_edges(u, G); 2019 // assert (std::is_sorted(begin, end)); 2020 const auto n = in_degree(u, G); 2021 Vertex operands[n]; 2022 unsigned i = 0; 2023 for (auto e : make_iterator_range(in_edges(u, G))) { 2024 operands[i++] = source(e, G); 2025 } 2026 std::sort(operands, operands + n); 2027 size_t h = 0; 2028 boost::hash_combine(h, static_cast<value_of>(PassContainer::getType(u, G))); 2029 for (unsigned j = 0; j < n; ++j) { 2030 boost::hash_combine(h, operands[j]); 2031 } 2032 // for (auto e : make_iterator_range(in_edges(u, G))) { 2033 // boost::hash_combine(h, source(e, G)); 2034 // } 2035 return h; 2036 } 2037 IdentityHash (const Graph & g) : G(g) { } 2038 private: 2039 const Graph & G; 2040 }; 2041 2042 struct IdentityComparator { 2043 bool operator()(const Vertex u, const Vertex v) const { 2044 const auto typeId = getType(u, G); 2045 if (LLVM_LIKELY(typeId == getType(v, G))) { 2046 const unsigned n = in_degree(u, G); 2047 if (LLVM_UNLIKELY(n == 0)) { 2048 assert (isNullary(typeId) && in_degree(v, G) == 0); 2049 if (LLVM_UNLIKELY(isLiteral(typeId))) { 2050 assert (getValue(u, G) && getValue(v, G)); 2051 return getValue(u, G) == getValue(v, G); 2052 } 2053 return true; 2054 } 2055 if (in_degree(v, G) == n) { 2056 Vertex adjA[n]; 2057 Vertex adjB[n]; 2058 auto ei = std::get<0>(in_edges(u, G)); 2059 auto ej = std::get<0>(in_edges(v, G)); 2060 // if this is an associative op, order doesn't matter 2061 if (isAssociative(typeId)) { 2062 for (unsigned i = 0; i < n; ++i, ++ei, ++ej) { 2063 adjA[i] = source(*ei, G); 2064 adjB[i] = source(*ej, G); 2065 } 2066 assert(std::is_sorted(adjA, adjA + n)); 2067 assert(std::is_sorted(adjB, adjB + n)); 2068 } else { // otherwise consider the order indicated by the edges 2069 for (unsigned i = 0; i < n; ++i, ++ei, ++ej) { 2070 adjA[G[*ei]] = source(*ei, G); 2071 adjB[G[*ej]] = source(*ej, G); 2072 } 2073 } 2074 for (unsigned i = 0; i < n; ++i) { 2075 if (adjA[i] != adjB[i]) { 2076 return false; 2077 } 2078 } 2079 return true; 2080 } 2081 } 2082 return false; 2083 } 2084 IdentityComparator (const Graph & g) : G(g) { } 2085 private: 2086 const Graph & G; 2087 }; 2088 2089 using IdentitySet = std::unordered_set<Vertex, IdentityHash, IdentityComparator>; 2090 2091 private: 2092 2093 bool reprocessGraph; 1546 2094 1547 2095 Graph G; 1548 2096 flat_map<const pablo::PabloAST *, Vertex> M; 2097 2098 IdentitySet V; 1549 2099 1550 2100 DistributionGraph Gd; … … 1564 2114 PabloVerifier::verify(kernel, "postdistributivepass"); 1565 2115 #endif 2116 2117 // errs() << "\n" 2118 // "BEFORE SIMPLIFICATION:\n" 2119 // "\n"; 2120 // PabloPrinter::print(kernel, errs()); 2121 1566 2122 Simplifier::optimize(kernel); 2123 2124 // errs() << "\n" 2125 // "AFTER SIMPLIFICATION:\n" 2126 // "\n"; 2127 // PabloPrinter::print(kernel, errs()); 2128 1567 2129 return true; 1568 2130 }
Note: See TracChangeset
for help on using the changeset viewer.