Changeset 4592 for icGREP/icgrepdevel/icgrep/pablo/optimizers
 Timestamp:
 Jun 3, 2015, 11:43:51 PM (4 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo/optimizers
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4590 r4592 1 1 #include "pablo_automultiplexing.hpp" 2 2 #include <pablo/codegenstate.h> 3 #include <llvm/ADT/SmallVector.h>4 #include <llvm/ADT/DenseMap.h>5 #include <llvm/ADT/DenseSet.h>6 3 #include <llvm/ADT/BitVector.h> 7 4 #include <stack> … … 13 10 #include <boost/circular_buffer.hpp> 14 11 #include <include/simdlib/builtins.hpp> 15 //#include <pablo/expression_map.hpp>12 #include <pablo/expression_map.hpp> 16 13 #include <pablo/printer_pablos.h> 17 14 #include <iostream> … … 40 37 am.topologicalSort(entry); 41 38 } 42 43 39 } 44 40 … … 191 187 192 188 // Map the predefined 0/1 entries 193 mCharacterizationMap.emplace(entry.createZeroes(), Cudd_ReadZero(mManager));194 mCharacterizationMap.emplace(entry.createOnes(), Cudd_ReadOne(mManager));189 mCharacterizationMap.emplace(entry.createZeroes(), Zero()); 190 mCharacterizationMap.emplace(entry.createOnes(), One()); 195 191 196 192 // Order the variables so the input Vars are pushed to the end; they ought to … … 258 254 // an operand of a Statement. Instead it updates the Initial operand's value. 259 255 testContradiction = false; 260 case PabloAST::ClassTypeId::Or: 256 case PabloAST::ClassTypeId::Or: 261 257 bdd = Or(input[0], input[1]); 262 258 break; … … 276 272 case PabloAST::ClassTypeId::MatchStar: 277 273 if (LLVM_UNLIKELY(isZero(input[0])  isZero(input[1]))) { 278 bdd = Cudd_ReadZero(mManager);274 bdd = Zero(); 279 275 break; 280 276 } … … 286 282 assert (stmt == mAdvance[advances.size()]); 287 283 if (LLVM_UNLIKELY(isZero(input[0]))) { 288 bdd = Cudd_ReadZero(mManager); 289 // mark this advance as having an input and output of 0 284 bdd = input[0]; 290 285 advances.emplace_back(bdd, bdd); 291 286 } … … 360 355 break; 361 356 default: 362 throw std::runtime_error("Unexpected statement " + stmt>getName()>to_string());357 throw std::runtime_error("Unexpected statement type " + stmt>getName()>to_string()); 363 358 } 364 359 assert ("Failed to generate a BDD." && (bdd  !(testContradiction  updateVariable))); 365 if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) { 366 // std::cerr << stmt>getName()>to_string() << " = â 367 " << std::endl; 368 Cudd_RecursiveDeref(mManager, bdd); 369 stmt = stmt>replaceWith(entry.createZeroes()); 370 } 371 else if (LLVM_LIKELY(updateVariable)) { 360 if (LLVM_LIKELY(updateVariable)) { 372 361 mCharacterizationMap[stmt] = bdd; 362 } 363 if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) { 364 if (!isa<Assign>(stmt)  cast<Assign>(stmt)>superfluous()) { 365 Cudd_RecursiveDeref(mManager, bdd); 366 stmt = stmt>replaceWith(entry.createZeroes()); 367 continue; 368 } 373 369 } 374 370 stmt = stmt>getNextNode(); … … 387 383 **  */ 388 384 385 inline DdNode * AutoMultiplexing::Zero() const { 386 DdNode * r = Cudd_ReadLogicZero(mManager); 387 Cudd_Ref(r); 388 return r; 389 } 390 391 inline DdNode * AutoMultiplexing::One() const { 392 DdNode * r = Cudd_ReadOne(mManager); 393 Cudd_Ref(r); 394 return r; 395 } 396 389 397 inline bool AutoMultiplexing::isZero(DdNode * x) const { 390 return x == Cudd_Read Zero(mManager);398 return x == Cudd_ReadLogicZero(mManager); 391 399 } 392 400 … … 420 428 421 429 inline bool AutoMultiplexing::noSatisfyingAssignment(DdNode * x) { 422 // TODO: since we're only interested in knowing whether there is no such cube, 423 // write an optimized function for that if one does not exist. 424 int* cube; 425 CUDD_VALUE_TYPE dummy; 426 auto gen = Cudd_FirstCube(mManager, x, &cube, &dummy); 427 bool r = Cudd_IsGenEmpty(gen); 428 Cudd_GenFree(gen); 429 return r; 430 return Cudd_bddLeq(mManager, x, Cudd_ReadLogicZero(mManager)); 430 431 } 431 432 … … 435 436 436 437 /**  * 437 * @brief createM appingGraph438 * @brief createMultiplexSetGraph 438 439 **  */ 439 440 void AutoMultiplexing::createMultiplexSetGraph() { … … 498 499 // between the "set vertex" and its members. We obtain these from "generateMultiplexSets". 499 500 500 // Question: should we enumerate the power set of S? 501 // TODO: Instead of building a graph, construct a trie of all members in the powerset of S that are of size 502 // >= 3 and not 2^n for any n. 501 503 502 504 const auto v = add_vertex(mMultiplexSetGraph); … … 735 737 } 736 738 737 738 static inline size_t smallest_multiplexed_set(const size_t x) { 739 return std::log2<size_t>(x) + 1; // use a faster builtin function for this? 740 } 741 739 /**  * 740 * @brief compute_m 741 **  */ 742 static inline size_t compute_m(const size_t n) { 743 return std::log2<size_t>(n) + 1; // use a faster builtin function for this? 744 } 745 746 struct CreateOr { 747 CreateOr(PabloBlock * pb) : mPb(pb) {} 748 PabloAST * operator() (PabloAST * x, PabloAST * y) { return mPb>createOr(x, y); } 749 PabloBlock * mPb; 750 }; 751 752 struct CreateAnd { 753 CreateAnd(PabloBlock * pb) : mPb(pb) {} 754 PabloAST * operator() (PabloAST * x, PabloAST * y) { return mPb>createAnd(x, y); } 755 PabloBlock * mPb; 756 }; 742 757 743 758 /**  * … … 754 769 max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph)); 755 770 } 756 const size_t max_m = smallest_multiplexed_set(max_n);771 const size_t max_m = compute_m(max_n); 757 772 758 773 std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n); … … 768 783 if (n) { 769 784 770 const size_t m = smallest_multiplexed_set(n);785 const size_t m = compute_m(n); 771 786 772 787 graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end; … … 794 809 #endif 795 810 811 ExpressionMap<PabloAST *, PabloAST *> expMap(nullptr); 812 796 813 /// Perform ntom Multiplexing 797 814 for (size_t j = 0; j != m; ++j) { … … 799 816 assert (Q.empty()); 800 817 801 std::stringstream name; 802 name << "mux"; 818 std::ostringstream prefix; 819 820 prefix << "mux"; 803 821 for (size_t i = 1; i <= n; ++i) { 804 822 if ((i & (static_cast<size_t>(1) << j)) != 0) { 805 823 assert (!Q.full()); 806 824 PabloAST * tmp = V[i  1]>getOperand(0); assert (tmp); 825 prefix << '_' << V[i  1]>getName()>to_string(); 807 826 Q.push_back(tmp); 808 name << "_" << V[i  1]>getName()>to_string();809 827 } 810 828 } … … 821 839 assert (!Q.full()); 822 840 pb>setInsertPoint(choose(a2, a1, adv)); 823 PabloAST * tmp = pb>createOr(a1, a2); assert (tmp); 841 CreateOr createOr(pb); 842 PabloAST * tmp = expMap.findOrCall(createOr, PabloAST::ClassTypeId::Or, a1, a2); assert (tmp); 824 843 Q.push_back(tmp); 825 844 } … … 827 846 828 847 PabloAST * mux = Q.front(); Q.pop_front(); assert (mux); 829 muxed[j] = pb>createAdvance(mux, adv>getOperand(1), name.str());848 muxed[j] = pb>createAdvance(mux, adv>getOperand(1), prefix.str()); 830 849 } 831 850 … … 836 855 837 856 Advance * const adv = V[i  1]; 857 858 pb>setInsertPoint(adv); 838 859 839 860 assert (Q.empty()); … … 850 871 PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1); 851 872 PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2); 852 pb>setInsertPoint(choose(a2, a1, adv));853 873 assert (!Q.full()); 854 PabloAST * tmp = pb>createOr(a1, a2); assert (tmp); 874 CreateOr createOr(pb); 875 PabloAST * tmp = expMap.findOrCall(createOr, PabloAST::ClassTypeId::Or, a1, a2); assert (tmp); 855 876 Q.push_back(tmp); 856 877 } … … 870 891 assert (Q.size() >= 1); 871 892 872 while (Q.size() > (1 + ((neg == nullptr) ? 1 : 0))) {893 while (Q.size() > 1) { 873 894 PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1); 874 895 PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2); 875 876 896 assert (!Q.full()); 877 PabloAST * tmp = pb>createAnd(a1, a2); assert (tmp); 897 CreateAnd createAnd(pb); 898 PabloAST * tmp = expMap.findOrCall(createAnd, PabloAST::ClassTypeId::And, a1, a2); assert (tmp); 878 899 Q.push_back(tmp); 879 900 } 880 901 881 assert (Q.size() >= 0 && Q.size() <= 2); 882 883 PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1); 884 PabloAST * a2 = neg; 885 if (LLVM_UNLIKELY(neg == nullptr)) { 886 a2 = Q.front(); Q.pop_front(); assert (a2); 887 } 888 assert (Q.empty()); 889 890 pb>setInsertPoint(choose(a2, a1, adv)); 891 PabloAST * demux = pb>createAnd(a1, a2, "demux_" + V[i  1]>getName()>to_string()); 892 893 V[i  1]>replaceWith(demux, false); 902 assert (Q.size() == 1); 903 904 PabloAST * demux = Q.front(); Q.pop_front(); assert (demux); 905 if (LLVM_LIKELY(neg != nullptr)) { 906 CreateAnd createAnd(pb); 907 demux = expMap.findOrCall(createAnd, PabloAST::ClassTypeId::And, demux, neg); assert (demux); 908 } 909 V[i  1]>replaceWith(demux, true, true); 894 910 } 895 911 } … … 910 926 std::unordered_set<const PabloAST *> encountered; 911 927 std::stack<Statement *> scope; 912 for (Statement * stmt = entry.front(); ; ) { 913 restart:while ( stmt ) {928 for (Statement * stmt = entry.front(); ; ) { restart: 929 while ( stmt ) { 914 930 for (unsigned i = 0; i != stmt>getNumOperands(); ++i) { 915 931 PabloAST * const op = stmt>getOperand(i); 
icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp
r4586 r4592 55 55 } 56 56 private: 57 DdNode * Zero() const; 58 DdNode * One() const; 57 59 bool isZero(DdNode * x) const; 58 60 DdNode * And(DdNode * x, DdNode * y);
Note: See TracChangeset
for help on using the changeset viewer.