 Timestamp:
 Aug 9, 2017, 3:20:04 PM (20 months ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo/optimizers
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/distributivepass.cpp
r5596 r5607 37 37 #include <pablo/printer_pablos.h> 38 38 39 39 40 using namespace boost; 40 41 using namespace boost::container; 41 42 using namespace llvm; 42 using namespace pablo; 43 44 using TypeId = PabloAST::ClassTypeId; 43 44 struct svecS{}; 45 46 namespace boost { 47 48 template<class T> 49 struct __sorted_edge_vector : public std::vector<T> { 50 using iterator = typename std::vector<T>::iterator; 51 void push_back(const T & item) { 52 const auto p = std::upper_bound(std::vector<T>::begin(), std::vector<T>::end(), item); 53 std::vector<T>::insert(p, item); 54 } 55 }; 56 57 template <class ValueType> struct container_gen<svecS, ValueType> { 58 typedef __sorted_edge_vector<ValueType> type; 59 }; 60 61 template <> struct parallel_edge_traits<svecS> { 62 typedef allow_parallel_edge_tag type; 63 }; 64 65 template<class T> graph_detail::vector_tag container_category(const __sorted_edge_vector<T>&) { 66 return graph_detail::vector_tag(); 67 } 68 69 template <class T> graph_detail::unstable_tag iterator_stability(const __sorted_edge_vector<T>&) { 70 return graph_detail::unstable_tag(); 71 } 72 } 73 74 namespace pablo { 45 75 46 76 enum class State { … … 50 80 }; 51 81 82 using TypeId = PabloAST::ClassTypeId; 83 52 84 using UsageTime = size_t; 53 85 … … 55 87 56 88 using OperandIndex = unsigned; 57 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 89 90 using Graph = adjacency_list<svecS, vecS, bidirectionalS, VertexData, OperandIndex, vecS>; … … 137 138 138 139 PassContainer() 139 : reprocessGraph(false)140 : compactedGraph(false) 140 141 , V{0, IdentityHash(G), IdentityComparator(G)} { 141 142 … … 199 200 // recognizes a duplicate value in scope. 200 201 202 // TODO: try setting the insertion point to a dominating position of its known (nonregenerable) users 203 // of each operand? 204 201 205 entry>setInsertPoint(stmt>getPrevNode()); 202 206 for (const auto e : make_iterator_range(in_edges(u, G))) { … … 221 225 * Does vertex (u) have a value and, if so, does value dominate the statement? If not, regenerate it. 222 226 **  */ 223 PabloAST * regenerateIfNecessary( Statement * const ip, PabloBlock * const entry, const Vertex u, size_t & count) {227 PabloAST * regenerateIfNecessary(const Statement * const stmt, PabloBlock * const entry, const Vertex u, size_t & count) { 224 228 assert (isLive(u)); 225 229 PabloAST * value = getValue(u); 226 if (!dominates(value, ip)) { 230 if (dominates(value, stmt)) { 231 assert (isNullary(getType(u))  getLastUsageTime(u) > 0); 232 } else { // regenerate the statement ... 227 233 228 234 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 235 236 236 const auto n = in_degree(u, G); … … 244 244 value = entry>createOnes(); 245 245 } 246 } else if (LLVM_LIKELY(n != 1)) {247 248 const TypeId typeId = getType(u);249 250 assert (isAssociative(typeId));251 252 // Suppose we try to minimize the pairwise difference in last usage time,253 // taking into account that we can use negations of variables when they've254 // been used more recently. Take note to update the correct vertex if an255 // ANDC can be used instead.256 257 Vertex input[n];258 unsigned i = 0;259 for (auto e : make_iterator_range(in_edges(u, G))) {260 input[i++] = source(e, G);261 assert (getLastUsageTime(source(e, G)) > 0);262 }263 264 std::sort(input, input + n, [this](const Vertex u, const Vertex v) {265 return getLastUsageTime(u) < getLastUsageTime(v);266 });267 268 // for (unsigned i = 0; i < n; ++i) {269 // setLastUsageTime(input[i], ++count);270 // }271 272 PabloBuilder builder(entry);273 value = getValue(input[0]);274 for (unsigned i = 1; i < n; ++i) {275 PabloAST * const op = getValue(input[i]);276 switch (typeId) {277 case TypeId::And:278 value = builder.createAnd(value, op);279 break;280 case TypeId::Or:281 value = builder.createOr(value, op);282 break;283 case TypeId::Xor:284 value = builder.createXor(value, op);285 break;286 default:287 llvm_unreachable("impossible!");288 }289 }290 246 } else { 291 value = entry>createNot(getValue(getNegatedLiteral(u))); 247 248 for (const auto e : make_iterator_range(in_edges(u, G))) { 249 regenerateIfNecessary(stmt, entry, source(e, G), count); 250 } 251 252 if (LLVM_LIKELY(n != 1)) { 253 254 const TypeId typeId = getType(u); 255 256 assert (isAssociative(typeId)); 257 258 // Suppose we try to minimize the pairwise difference in last usage time, 259 // taking into account that we can use negations of variables when they've 260 // been used more recently. Take note to update the correct vertex if an 261 // ANDC can be used instead. 262 263 Vertex input[n]; 264 unsigned i = 0; 265 for (auto e : make_iterator_range(in_edges(u, G))) { 266 input[i++] = source(e, G); 267 } 268 269 std::sort(input, input + n, [this](const Vertex v, const Vertex w) { 270 return getLastUsageTime(v) < getLastUsageTime(w); 271 }); 272 273 PabloBuilder builder(entry); 274 value = getValue(input[0]); 275 setLastUsageTime(input[0], ++count); 276 for (unsigned i = 1; i < n; ++i) { 277 PabloAST * const op = getValue(input[i]); 278 setLastUsageTime(input[i], ++count); 279 switch (typeId) { 280 case TypeId::And: 281 value = builder.createAnd(value, op); 282 break; 283 case TypeId::Or: 284 value = builder.createOr(value, op); 285 break; 286 case TypeId::Xor: 287 value = builder.createXor(value, op); 288 break; 289 default: 290 llvm_unreachable("impossible!"); 291 } 292 } 293 } else { 294 const auto v = getNegatedLiteral(u); 295 setLastUsageTime(v, ++count); 296 value = entry>createNot(getValue(v)); 297 } 292 298 } 293 299 assert (value); 300 setUnmodified(u); 294 301 setValue(u, value); 295 setUnmodified(u);296 302 setLastUsageTime(u, ++count); 297 } 303 } 298 304 return value; 299 305 } 300 306 301 307 protected: 302 303 /**  *304 * @brief printGraph305 **  */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 }317 } else {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 }428 308 429 309 /**  * … … 432 312 bool simplifyGraph() { 433 313 bool modified = false; 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 } 314 repeat: getReverseTopologicalOrdering(); 315 if (compactGraph()) { 316 goto repeat; 317 } 318 if (applyDistributivityLaw()) { 319 modified = true; 320 goto repeat; 321 } 322 factorizeGraph(); 454 323 return modified; 455 324 } … … 464 333 if (LLVM_LIKELY(self.isLive(u))) { 465 334 assert(self.hasValidOperandIndicies(u)); 466 if (LLVM_LIKELY(isImmutable(self.getType(u))  out_degree(u, self.G) != 0)) { 335 if (LLVM_UNLIKELY(isImmutable(self.getType(u)))) { 336 /* do nothing */ 337 } else if (LLVM_LIKELY(out_degree(u, self.G) != 0)) { 467 338 self.ordering.push_back(u); 468 339 } else { … … 486 357 ordering.reserve(num_vertices(G)); 487 358 topological_sort(G, PrePassInserter(*this)); 488 assert (!ordering.empty());489 359 } 490 360 … … 493 363 **  */ 494 364 bool compactGraph() { 495 reprocessGraph = false; 365 366 V.clear(); 367 compactedGraph = false; 368 496 369 for (const auto u : boost::adaptors::reverse(ordering)) { 497 if (LLVM_LIKELY(isLive(u))) { 498 const auto typeId = getType(u); 499 if (LLVM_UNLIKELY(isImmutable(typeId))) { 370 371 const auto typeId = getType(u); 372 373 assert (isLive(u)); 374 assert (!isImmutable(typeId)); 375 assert (hasValidOperandIndicies(u)); 376 assert (out_degree(u, G) > 0); 377 378 if (LLVM_UNLIKELY(isConstant(typeId))) { 379 if (processConstant(u, typeId)) { 500 380 continue; 501 381 } 502 assert (hasValidOperandIndicies(u)); 503 if (LLVM_UNLIKELY(out_degree(u, G) == 0)) { 504 removeVertex(u); 382 } else if (isAssociative(typeId)) { 383 if (processAssociative(u, typeId)) { 505 384 continue; 506 385 } 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; 386 } else if (typeId == TypeId::Not) { 387 if (processNegation(u)) { 388 continue; 389 } 390 } 391 392 consolidate(u); 393 } 394 395 return compactedGraph; 524 396 } 525 397 … … 541 413 const auto v = first_source(in_edges(u, G)); 542 414 for (const auto e : make_iterator_range(out_edges(u, G))) { 543 addEdge(v, target(e, G), G[e]); 415 addEdge(v, target(e, G), G[e]); 544 416 } 545 417 removeVertex(u); 418 compactedGraph = true; 546 419 return true; 547 420 } else { … … 553 426 canonicalizeXor(u); 554 427 } else { // is distributive 555 applyDeMorganExpansion(u, typeId); 556 if (LLVM_UNLIKELY(applyAbsorbtionComplementLaw(u, typeId))) { 557 return true; 558 } 428 applyDeMorgans(u, typeId); 429 return applyAbsorbtionComplementLaw(u, typeId); 559 430 } 560 431 } … … 566 437 **  */ 567 438 bool transitiveClosure(const Vertex u, const TypeId typeId) { 568 // Take the transitive closure of these arcs to reveal the underlying equations569 439 570 440 assert (isLive(u)); … … 576 446 for (auto ei : make_iterator_range(out_edges(u, G))) { 577 447 const auto v = target(ei, G); 578 if ( getType(v) == typeId) {448 if (typeId == getType(v)) { 579 449 assert(hasValidOperandIndicies(v)); 580 450 for (auto ej : make_iterator_range(in_edges(u, G))) { 581 addEdge(source(ej, G), v );451 addEdge(source(ej, G), v, G[ei]); 582 452 } 583 453 setModified(v); 584 454 removed[n++] = v; 585 455 } 456 } 457 if (LLVM_UNLIKELY(out_degree(u, G) == n)) { 458 removeVertex(u); 459 compactedGraph = true; 460 return true; 586 461 } 587 462 for (unsigned i = 0; i < n; ++i) { … … 590 465 remove_edge(u, v, G); 591 466 assert(hasValidOperandIndicies(v)); 592 } 593 if (out_degree(u, G) == 0) { 594 removeVertex(u); 595 return true; 596 } 467 compactedGraph = true; 468 } 469 assert (out_degree(u, G) > 0); 597 470 return false; 598 471 } … … 603 476 * (A â Â¬B) = (A â B â 1) = Â¬(A â B) 604 477 **  */ 605 voidcanonicalizeXor(const Vertex u) {478 Vertex canonicalizeXor(const Vertex u) { 606 479 607 480 assert (isLive(u)); 608 481 assert (getType(u) == TypeId::Xor); 482 assert (in_degree(u, G) > 1); 609 483 610 484 const auto l = in_degree(u, G); … … 625 499 assert (edge(v, u, G).second); 626 500 remove_edge(v, u, G); 627 addEdge( first_source(in_edges(v, G)), u);501 addEdge(getNegatedLiteral(v), u); 628 502 } 629 503 for (unsigned i = 0; i < m; ++i) { … … 632 506 remove_edge(v, u, G); 633 507 } 508 setModified(u); 509 compactedGraph = true; 634 510 if (((n + m) & 1) != 0) { 635 511 const auto x = makeVertex(TypeId::Not); … … 637 513 add_edge(x, target(e, G), G[e], G); 638 514 } 639 clear_out_edges(u, G); 515 clear_out_edges(u, G); 640 516 add_edge(u, x, 0, G); 641 } 642 setModified(u); 643 assert(hasValidOperandIndicies(u)); 644 } 517 assert(hasValidOperandIndicies(u)); 518 return x; 519 } 520 } 521 return u; 645 522 } 646 523 … … 664 541 } 665 542 removeVertex(u); 543 compactedGraph = true; 666 544 return true; 667 545 } … … 670 548 671 549 /**  * 672 * @brief applyDeMorgan Expansion673 **  */ 674 bool applyDeMorgan Expansion(const Vertex u, const TypeId typeId) {550 * @brief applyDeMorgans 551 **  */ 552 bool applyDeMorgans(const Vertex u, const TypeId typeId) { 675 553 676 554 assert (isLive(u)); … … 708 586 } 709 587 setModified(u); 710 reprocessGraph = true;711 588 assert(hasValidOperandIndicies(u)); 589 compactedGraph = true; 712 590 return true; 713 591 } 714 592 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; 593 908 594 } 909 595 … … 925 611 const auto innerTypeId = getType(v); 926 612 if (innerTypeId == TypeId::Not) { 927 const auto w = getNegatedLiteral(v);613 const auto w = first_source(in_edges(v, G)); 928 614 assert (isLive(w)); 929 615 for (const auto ej : make_iterator_range(in_edges(u, G))) { … … 941 627 } 942 628 943 if ( n) {629 if (LLVM_UNLIKELY(n != 0)) { 944 630 setModified(u); 945 reprocessGraph = true;946 for (;;){631 compactedGraph = true; 632 do { 947 633 const auto v = A[n]; 948 634 assert (edge(v, u, G).second); 949 635 remove_edge(v, u, G); 950 if (LLVM_UNLIKELY(out_degree(v, G) == 0)) { 951 removeVertex(v); 952 } 953 if (LLVM_LIKELY(n == 0)) { 954 break; 955 } 956 } 636 } while (LLVM_UNLIKELY(n != 0)); 957 637 } 958 638 … … 1005 685 } 1006 686 } else if (LLVM_UNLIKELY(targetTypeId == TypeId::Not)) { 1007 const auto negatedTypeId = (typeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes; 1008 setType(u, negatedTypeId); 687 setType(u, (typeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes); 1009 688 modification[m++] = v; 1010 } else if (LLVM_UNLIKELY(isStreamOperation(typeId))) {689 } else { // check if this is a stream operation and optimize accordingly 1011 690 if (LLVM_LIKELY(typeId == TypeId::Zeroes)) { 1012 setType(v, TypeId::Zeroes); 1013 modification[m++] = v; 691 switch (targetTypeId) { 692 case TypeId::Advance: 693 case TypeId::Lookahead: 694 case TypeId::InFile: 695 case TypeId::AtEOF: 696 assert (G[e] == 0); 697 setType(v, TypeId::Zeroes); 698 modification[m++] = v; 699 break; 700 case TypeId::ScanThru: 701 case TypeId::AdvanceThenScanThru: 702 case TypeId::MatchStar: 703 if (G[e] == 0) { 704 setType(v, TypeId::Zeroes); 705 modification[m++] = v; 706 } else { 707 strengthReduction(v); 708 } 709 break; 710 case TypeId::ScanTo: 711 case TypeId::AdvanceThenScanTo: 712 strengthReduction(v); 713 default: break; 714 } 1014 715 } else { // if (typeId == TypeId::Ones) { 1015 716 switch (targetTypeId) { 1016 717 case TypeId::ScanThru: 1017 if ( LLVM_UNLIKELY(G[e] == 1)) {718 if (G[e] == 1) { 1018 719 setType(v, TypeId::Zeroes); 1019 720 modification[m++] = v; … … 1021 722 break; 1022 723 case TypeId::MatchStar: 1023 if ( LLVM_UNLIKELY(G[e] == 0)) {724 if (G[e] == 0) { 1024 725 setType(v, TypeId::Ones); 1025 726 modification[m++] = v; … … 1036 737 } 1037 738 739 compactedGraph = true; 740 1038 741 // handle any identity graph modifications 1039 742 while (LLVM_UNLIKELY(n != 0)) { … … 1056 759 1057 760 return false; 761 } 762 763 /**  * 764 * @brief strengthReduction 765 **  */ 766 void strengthReduction(const Vertex u) { 767 768 1058 769 } 1059 770 … … 1088 799 const auto upperSet = obtainDistributableSources(std::get<1>(lower)); 1089 800 for (const auto & upper : upperSet) { 1090 1091 801 const auto & inner = std::get<0>(upper); 1092 802 const auto & sources = std::get<1>(upper); … … 1096 806 1097 807 // Update G to match the desired change 1098 auto x = makeVertex(outerTypeId); 1099 auto y = makeVertex(innerTypeId); 1100 1101 for (const Vertex i : sources) { 1102 const auto u = Gd[i]; 1103 for (const Vertex j : inner) { 1104 const auto v = Gd[j]; 1105 assert (edge(u, v, G).second); 1106 assert (getType(v) == innerTypeId); 1107 remove_edge(u, v, G); 1108 } 1109 add_edge(u, y, 0, G); 1110 } 1111 y = consolidate(y); 808 const auto x = makeVertex(outerTypeId); 1112 809 for (const auto i : inner) { 1113 810 const auto u = Gd[i]; … … 1119 816 remove_edge(u, v, G); 1120 817 } 1121 add_edge(u, x, 0, G); 1122 } 1123 x = consolidate(x); 1124 addEdge(x, y); 818 addEdge(u, x); 819 } 820 const auto y = makeVertex(innerTypeId); 821 addEdge(consolidate(x), y); 822 for (const Vertex i : sources) { 823 const auto u = Gd[i]; 824 for (const Vertex j : inner) { 825 const auto v = Gd[j]; 826 assert (edge(u, v, G).second); 827 assert (getType(v) == innerTypeId); 828 remove_edge(u, v, G); 829 } 830 addEdge(u, y); 831 } 832 const auto yy = consolidate(y); 1125 833 for (const Vertex i : outer) { 1126 834 const auto u = Gd[i]; 1127 835 assert (getType(u) == outerTypeId); 1128 836 setModified(u); 1129 addEdge(y, u); 1130 } 837 addEdge(yy, u); 838 } 839 1131 840 modified = true; 1132 841 } … … 1151 860 if (isDistributive(outerTypeId)) { 1152 861 const auto n = in_degree(u, G); 1153 if (n < 2) continue;1154 862 assert (n > 1); 1155 863 const auto innerTypeId = oppositeTypeId(getType(u)); … … 1202 910 BicliqueSet obtainDistributableClauses(const Sequence & S) { 1203 911 auto cliques = enumerateBicliques(S, Gd, 1, 2); 912 1204 913 // remove any cliques from our set that do not contain all of their users 1205 for (auto ci = cliques.begin(); ci != cliques.end(); ) { 1206 const auto & A = std::get<0>(*ci); 1207 auto & B = std::get<1>(*ci); 1208 for (auto bi = B.begin(); bi != B.end(); ) { 1209 if (out_degree(Gd[*bi], G) != A.size()) { 1210 bi = B.erase(bi); 1211 } else { 1212 ++bi; 1213 } 1214 } 1215 if (B.size() < 2) { 1216 ci = cliques.erase(ci); 1217 } else { 1218 ++ci; 1219 } 1220 } 914 cliques.erase(std::remove_if(cliques.begin(), cliques.end(), [this](Biclique & C){ 915 const auto & A = std::get<0>(C); 916 auto & B = std::get<1>(C); 917 B.erase(std::remove_if(B.begin(), B.end(), [this, &A](const DistributionVertex u) { 918 return out_degree(Gd[u], G) != A.size(); 919 }), B.end()); 920 return B.size() < 2; 921 }), cliques.end()); 922 1221 923 return makeIndependent(std::move(cliques), 0); 1222 924 } … … 1236 938 void factorizeGraph() { 1237 939 1238 Sequence associative; 940 Sequence associative(0); 941 associative.reserve(num_vertices(G)); 942 1239 943 for (const auto u : make_iterator_range(vertices(G))) { 1240 944 if (isLive(u) && isAssociative(getType(u))) { … … 1244 948 1245 949 // 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 running1247 // time of this optimization.950 // choosing only those of some minSizeB or greater first can significantly reduce the 951 // running time of this optimization. 1248 952 1249 953 Sequence group[3]; … … 1251 955 const TypeId typeCode[3] = { TypeId::And, TypeId::Or, TypeId::Xor }; 1252 956 957 for (unsigned i = 0; i < 3; ++i) { 958 assert (getFactorGroup(typeCode[i]) == i); 959 } 960 1253 961 for (;;) { 1254 962 1255 auto factors = makeIndependent(enumerateBicliques(associative, G, 2, 2), 1); 1256 if (factors.empty()) { 963 // This should be made smarter. Ideally I'd like to factor sets of variables that are 964 // whose sources are computed around the same point in the program. 965 966 const auto factors = makeIndependent(enumerateBicliques(associative, G, 2, 2), 1); 967 968 if (LLVM_UNLIKELY(factors.empty())) { 1257 969 break; 1258 970 } … … 1260 972 bool unchanged = true; 1261 973 1262 for ( auto &factor : factors) {1263 const auto &sources = std::get<1>(factor);974 for (const auto factor : factors) { 975 const auto sources = std::get<1>(factor); 1264 976 assert (sources.size() > 1); 1265 auto &targets = std::get<0>(factor);977 const auto targets = std::get<0>(factor); 1266 978 assert (targets.size() > 1); 1267 979 1268 for (unsigned k = 0; k < 3; ++k) {1269 assert (group[ k].empty());980 for (unsigned i = 0; i < 3; ++i) { 981 assert (group[i].empty()); 1270 982 } 1271 983 … … 1275 987 for (const auto u : targets) { 1276 988 assert (hasValidOperandIndicies(u)); 1277 const auto k = factorGroup(getType(u));989 const auto k = getFactorGroup(getType(u)); 1278 990 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]); 1285 } 1286 removeVertex(u); 1287 } 991 assert (create[k]); 992 t[k] = u; 993 create[k] = false; 1288 994 } else { 1289 995 group[k].push_back(u); … … 1292 998 1293 999 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]); 1000 if (LLVM_LIKELY(group[k].size() > (create[k] ? 1 : 0))) { 1001 if (LLVM_LIKELY(create[k])) { 1002 t[k] = makeVertex(typeCode[k]); 1003 for (const auto u : sources) { 1004 add_edge(u, t[k], 0, G); 1005 } 1006 associative.push_back(t[k]); 1007 assert (t[k] == consolidate(t[k])); 1008 } 1009 1010 assert (hasValidOperandIndicies(t[k])); 1011 // Remove the biclique between the source and target vertices 1299 1012 for (auto u : sources) { 1300 add_edge(u, t[k], 0, G); 1013 for (auto v : group[k]) { 1014 assert (getType(v) == typeCode[k]); 1015 assert (edge(u, v, G).second); 1016 boost::remove_edge(u, v, G); 1017 } 1301 1018 } 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) { 1019 // ... and replace it with the factorization 1307 1020 for (auto v : group[k]) { 1308 1021 assert (getType(v) == typeCode[k]); 1309 assert (edge(u, v, G).second); 1310 boost::remove_edge(u, v, G); 1022 addEdge(t[k], v); 1023 setModified(v); 1024 assert(hasValidOperandIndicies(v)); 1311 1025 } 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)); 1026 unchanged = false; 1319 1027 } 1320 1028 group[k].clear(); 1321 unchanged = false;1322 1029 } 1323 1030 } 1324 1031 1325 1032 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) { 1033 for (const auto factor : factors) { 1034 const auto targets = std::get<0>(factor); 1035 for (const auto u : targets) { 1036 const auto f = std::lower_bound(associative.begin(), associative.end(), u); 1037 if (LLVM_LIKELY(f != associative.end() && *f == u)) { 1038 associative.erase(f); 1039 } 1040 } 1041 } 1042 } 1043 } 1044 } 1045 1046 /**  * 1047 * @brief getFactorGroup 1048 **  */ 1049 static unsigned getFactorGroup(const TypeId typeId) { 1352 1050 switch (typeId) { 1353 1051 case TypeId::And: … … 1360 1058 } 1361 1059 } 1362 1363 // /**  *1364 // * @brief applyDeMorganContraction1365 // **  */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 1408 1060 1409 1061 private: … … 1439 1091 } 1440 1092 if (B.size() >= minimumSizeB) { 1441 // std::sort(B.begin(), B.end());1442 1093 assert (std::is_sorted(B.begin(), B.end())); 1443 1094 assert (std::unique(B.begin(), B.end()) == B.end()); … … 1502 1153 T.push_back(target(e, G)); 1503 1154 } 1504 // std::sort(T.begin(), T.end());1505 1155 assert (std::is_sorted(T.begin(), T.end())); 1506 1156 assert (std::unique(T.begin(), T.end()) == T.end()); … … 1530 1180 1531 1181 const auto l = S.size(); 1182 IndependentSetGraph I(l); 1183 1532 1184 assert (independentSide < 2); 1533 if (LLVM_LIKELY(l > 1)) { 1534 1535 IndependentSetGraph I(l); 1536 1537 // Initialize our weights 1185 1186 // Initialize our weights 1187 for (unsigned i = 0; i != l; ++i) { 1188 I[i] = std::get<0>(S[i]).size() * std::get<1>(S[i]).size(); 1189 } 1190 1191 // Determine our constraints 1192 for (unsigned i = 0; i != l; ++i) { 1193 const auto & Si = (independentSide == 0) ? std::get<0>(S[i]) : std::get<1>(S[i]); 1194 for (unsigned j = i + 1; j != l; ++j) { 1195 const auto & Sj = (independentSide == 0) ? std::get<0>(S[j]) : std::get<1>(S[j]); 1196 if (intersects(Si, Sj)) { 1197 boost::add_edge(i, j, I); 1198 } 1199 } 1200 } 1201 1202 // Use the greedy algorithm to choose our independent set 1203 Sequence selected; 1204 for (;;) { 1205 unsigned w = 0; 1206 Vertex u = 0; 1538 1207 for (unsigned i = 0; i != l; ++i) { 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 } 1208 if (I[i] > w) { 1209 w = I[i]; 1210 u = i; 1211 } 1212 } 1213 if (LLVM_UNLIKELY(w == 0)) break; 1214 selected.push_back(u); 1215 I[u] = 0; 1216 for (auto v : make_iterator_range(adjacent_vertices(u, I))) { 1217 I[v] = 0; 1218 } 1219 } 1220 1221 // Sort the selected list and then remove the unselected cliques 1222 std::sort(selected.begin(), selected.end(), std::greater<Vertex>()); 1223 auto end = S.end(); 1224 for (const unsigned offset : selected) { 1225 end = S.erase(S.begin() + offset + 1, end)  1; 1226 } 1227 S.erase(S.begin(), end); 1580 1228 1581 1229 return std::move(S); … … 1586 1234 **  */ 1587 1235 Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) { 1588 reprocessGraph = true;1589 1236 return add_vertex(std::make_tuple(expr, typeId, expr ? State::Live : State::Modified, 0), G); 1590 1237 } … … 1629 1276 M.emplace(stmt, w); 1630 1277 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;1650 1278 } else { 1651 1279 const auto u = makeVertex(typeId, isRegenerable(typeId) ? nullptr : stmt); … … 1671 1299 for (const auto e : make_iterator_range(out_edges(u, G))) { 1672 1300 if (LLVM_UNLIKELY(target(e, G) == v)) { 1673 if (LLVM_UNLIKELY(typeId == TypeId::Xor)) { 1301 if (LLVM_LIKELY(isDistributive(typeId))) { 1302 G[e] = std::max(G[e], index); 1303 } else { 1674 1304 remove_edge(e, G); 1675 1305 } … … 1713 1343 } 1714 1344 } else if (requiredOperands(typeId) == n) { 1715 bool used[n]; 1716 std::fill_n(used, n, false); 1345 bool used[n] = { false }; 1717 1346 for (auto e : make_iterator_range(in_edges(u, G))) { 1718 1347 const auto i = G[e]; … … 1771 1400 1772 1401 /**  * 1773 * @brief removeVertex1774 **  */1775 void removeVertex(const Vertex u) { assert (isLive(u));1776 setDead(u);1777 Vertex D[in_degree(u, G)];1778 unsigned n = 0;1779 for (const auto e : make_iterator_range(in_edges(u, G))) {1780 const auto v = source(e, G);1781 if (LLVM_UNLIKELY(out_degree(v, G) == 1)) {1782 D[n++] = v;1783 }1784 }1785 while (LLVM_UNLIKELY(n != 0)) {1786 removeVertex(D[n]);1787 }1788 clear_vertex(u, G);1789 reprocessGraph = true;1790 }1791 1792 /**  *1793 1402 * @brief consolidate 1794 1403 **  */ … … 1797 1406 assert (hasValidOperandIndicies(u)); 1798 1407 const auto f = V.insert(u); 1799 if (LLVM_UNLIKELY(f.second)) { 1408 if (LLVM_UNLIKELY(f.second)) { 1800 1409 return u; 1801 1410 } 1802 1411 const auto v = *f.first; 1412 assert (IdentityComparator(G)(u, v)); 1413 replaceVertex(u, v); 1414 return v; 1415 } 1416 1417 /**  * 1418 * @brief replaceVertex 1419 **  */ 1420 void replaceVertex(const Vertex u, const Vertex v) { 1803 1421 assert (u != v); 1804 assert (isLive( v));1805 const PabloAST * expr = getValue(u);1422 assert (isLive(u) && isLive(v)); 1423 const PabloAST * const expr = getValue(u); 1806 1424 if (expr) { 1807 1425 assert (!isRegenerable(getType(u))); … … 1816 1434 } 1817 1435 removeVertex(u); 1818 return v; 1436 } 1437 1438 /**  * 1439 * @brief removeVertex 1440 **  */ 1441 void removeVertex(const Vertex u) { 1442 assert (isLive(u)); 1443 setDead(u); 1444 clear_vertex(u, G); 1819 1445 } 1820 1446 … … 1907 1533 void setDead(const Vertex u) { 1908 1534 setState(u, State::Dead); 1535 setValue(u, nullptr); 1909 1536 } 1910 1537 … … 1918 1545 1919 1546 void setModified(const Vertex u) { 1547 assert(!isImmutable(getType(u))); 1920 1548 setState(u, State::Modified); 1921 1549 } … … 1938 1566 void setLastUsageTime(const Vertex u, const UsageTime time) { 1939 1567 assert (u < num_vertices(G)); 1940 1941 // errs() << " " << u << " ";1942 // PabloPrinter::print(getValue(u), errs());1943 // errs() << " @ " << time << "\n";1944 1945 1946 1568 std::get<3>(G[u]) = time; 1947 1569 } … … 1985 1607 } 1986 1608 1987 static bool isStreamOperation(const TypeId typeId) {1988 switch (typeId) {1989 case TypeId::Advance:1990 case TypeId::ScanThru:1991 case TypeId::AdvanceThenScanThru:1992 // case TypeId::ScanTo:1993 // case TypeId::AdvanceThenScanTo:1994 case TypeId::Lookahead:1995 case TypeId::MatchStar:1996 case TypeId::InFile:1997 case TypeId::AtEOF:1998 return true;1999 default:2000 return false;2001 }2002 }2003 2004 1609 static TypeId oppositeTypeId(const TypeId typeId) { 2005 1610 assert (isDistributive(typeId)); … … 2011 1616 } 2012 1617 2013 private: 1618 Vertex getNegatedLiteral(const Vertex u) const { 1619 assert (getType(u) == TypeId::Not); 1620 assert (in_degree(u, G) == 1); 1621 return first_source(in_edges(u, G)); 1622 } 1623 1624 Vertex removeNegation(const Vertex u) const { 1625 return getType(u) == TypeId::Not ? getNegatedLiteral(u) : u; 1626 } 1627 1628 /**  * 1629 * @brief getNegationOf 1630 **  */ 1631 Vertex getNegationOf(const Vertex u) { 1632 if (getType(u) == TypeId::Not) { 1633 return getNegatedLiteral(u); 1634 } else { 1635 for (const auto e : make_iterator_range(out_edges(u, G))) { 1636 const auto v = target(e, G); 1637 if (getType(v) == TypeId::Not) { 1638 return v; 1639 } 1640 } 1641 const auto v = makeVertex(TypeId::Not); 1642 add_edge(u, v, 0, G); 1643 return v; 1644 } 1645 } 2014 1646 2015 1647 struct IdentityHash { 2016 1648 size_t operator()(const Vertex u) const { 2017 1649 using value_of = std::underlying_type<TypeId>::type; 2018 // InEdgeIterator begin, end; 2019 // std::tie(begin, end) = in_edges(u, G); 2020 // assert (std::is_sorted(begin, end)); 2021 const auto n = in_degree(u, G); 2022 Vertex operands[n]; 2023 unsigned i = 0; 2024 for (auto e : make_iterator_range(in_edges(u, G))) { 2025 operands[i++] = source(e, G); 2026 } 2027 std::sort(operands, operands + n); 1650 #ifndef NDEBUG 1651 InEdgeIterator begin, end; 1652 std::tie(begin, end) = in_edges(u, G); 1653 assert (std::is_sorted(begin, end, [this](const Edge ei, const Edge ej) { 1654 return source(ei, G) <= source(ej, G); 1655 })); 1656 #endif 2028 1657 size_t h = 0; 2029 1658 boost::hash_combine(h, static_cast<value_of>(PassContainer::getType(u, G))); 2030 for (unsigned j = 0; j < n; ++j) { 2031 boost::hash_combine(h, operands[j]); 2032 } 2033 // for (auto e : make_iterator_range(in_edges(u, G))) { 2034 // boost::hash_combine(h, source(e, G)); 2035 // } 1659 for (auto e : make_iterator_range(in_edges(u, G))) { 1660 boost::hash_combine(h, source(e, G)); 1661 } 2036 1662 return h; 2037 1663 } … … 2048 1674 if (LLVM_UNLIKELY(n == 0)) { 2049 1675 assert (isNullary(typeId) && in_degree(v, G) == 0); 2050 if (LLVM_UNLIKELY(isLiteral(typeId))) { 2051 assert (getValue(u, G) && getValue(v, G)); 2052 return getValue(u, G) == getValue(v, G); 2053 } 2054 return true; 1676 return getValue(u, G) == getValue(v, G); 2055 1677 } 2056 1678 if (in_degree(v, G) == n) { … … 2092 1714 private: 2093 1715 2094 bool reprocessGraph;1716 bool compactedGraph; 2095 1717 2096 1718 Graph G; … … 2115 1737 PabloVerifier::verify(kernel, "postdistributivepass"); 2116 1738 #endif 2117 2118 // errs() << "\n"2119 // "BEFORE SIMPLIFICATION:\n"2120 // "\n";2121 // PabloPrinter::print(kernel, errs());2122 2123 1739 Simplifier::optimize(kernel); 2124 2125 // errs() << "\n"2126 // "AFTER SIMPLIFICATION:\n"2127 // "\n";2128 // PabloPrinter::print(kernel, errs());2129 2130 1740 return true; 2131 1741 } 
icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_simplifier.cpp
r5536 r5607 203 203 assert ("block has a branch but the expression and variable tables were not supplied" && et && vt); 204 204 variables.addNonZero(br>getCondition()); 205 if (LLVM_UNLIKELY(isa<While>(br))) { 206 for (Var * var : cast<While>(br)>getEscaped()) { 207 variables.put(var, var); 208 } 205 for (Var * var : br>getEscaped()) { 206 variables.put(var, var); 209 207 } 210 208 } … … 255 253 256 254 if (LLVM_LIKELY(isa<If>(br))) { 257 if (LLVM_UNLIKELY(variables.isNonZero( br>getCondition()))) {255 if (LLVM_UNLIKELY(variables.isNonZero(cond))) { 258 256 stmt = flatten(br); 259 257 continue;
Note: See TracChangeset
for help on using the changeset viewer.