Ignore:
Timestamp:
May 31, 2015, 11:19:37 AM (4 years ago)
Author:
nmedfort
Message:

Temporary check-in

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4566 r4585  
    5555class PabloBlock : public PabloAST, public StatementList {
    5656    friend class pablo::PabloAST;
    57     friend class Builder;
     57    friend class Builder;   
    5858public:
    5959
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4583 r4585  
    1616#include <cudd.h>
    1717#include <util.h>
    18 #include <fstream>
    1918
    2019using namespace llvm;
     
    2221using namespace boost::container;
    2322using namespace boost::numeric::ublas;
     23
     24#define PROVIDE_ASSIGNMENT_STATEMENTS_FOR_MUX_AND_DEMUX_STATEMENTS
    2425
    2526namespace pablo {
     
    453454    std::vector<DegreeType> D(remainingVerticies);
    454455
    455     bool canMultiplex = false;
    456 
    457456    VertexIterator vi, vi_end;
    458457    for (std::tie(vi, vi_end) = vertices(mConstraintGraph); vi != vi_end; ++vi) {
     
    469468        if (S.size() >= 3) {
    470469            addMultiplexSet(S);
    471             canMultiplex = true;
    472470        }       
    473471        // Randomly choose a vertex in S and discard it.
     
    485483    }
    486484
    487     raw_os_ostream out(std::cerr);
    488 
    489     out << "\n\ndigraph G {\n";
    490 
    491     const unsigned m = num_vertices(mConstraintGraph);
    492     const unsigned n = num_vertices(mMultiplexSetGraph);
    493 
    494     for (unsigned i = 0; i != m; ++i) {
    495         out << "v" << i << " [shape=box,label=\"" << mAdvance[i]->getName()->to_string() << "\"];\n";
    496     }
    497     for (unsigned i = m; i != n; ++i) {
    498         out << "v" << i << " [shape=circle];\n";
    499     }
    500 
    501     for (unsigned i = m; i != n; ++i) {
    502         graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
    503         for (std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph); ei != ei_end; ++ei) {
    504             out << "v" << i << " -> v" << target(*ei, mMultiplexSetGraph) << ";\n";
    505         }
    506     }
    507 
    508     out << "}\n\n";
    509 
    510 
    511     return canMultiplex;
     485//    raw_os_ostream out(std::cerr);
     486
     487//    out << "\n\ndigraph G {\n";
     488
     489//    const unsigned m = num_vertices(mConstraintGraph);
     490//    const unsigned n = num_vertices(mMultiplexSetGraph);
     491
     492//    for (unsigned i = 0; i != m; ++i) {
     493//        out << "v" << i << " [shape=box,label=\"" << mAdvance[i]->getName()->to_string() << "\"];\n";
     494//    }
     495//    for (unsigned i = m; i != n; ++i) {
     496//        out << "v" << i << " [shape=circle];\n";
     497//    }
     498
     499//    for (unsigned i = m; i != n; ++i) {
     500//        graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
     501//        for (std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph); ei != ei_end; ++ei) {
     502//            out << "v" << i << " -> v" << target(*ei, mMultiplexSetGraph) << ";\n";
     503//        }
     504//    }
     505
     506//    out << "}\n\n";
     507
     508    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
    512509}
    513510
     
    536533    // from contracting one advance node edge with an adjacent vertex
    537534
    538     using Set = flat_set<IndependentSetGraph::vertex_descriptor>;
    539535    const unsigned m = num_vertices(mConstraintGraph);
    540536    const unsigned n = num_vertices(mMultiplexSetGraph) - m;
     
    542538    IndependentSetGraph G(n);
    543539
    544     if (true) {
    545 
    546         std::vector<Set> S(n);
    547         // Record the "weight" of this set vertex and compute the actual set
    548         for (IndependentSetGraph::vertex_descriptor i = 0; i != n; ++i) {
    549             G[i] = out_degree(i + m, mMultiplexSetGraph);
    550             Set & Si = S[i];
    551             graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
    552             // What are the members of the i-th set? (i.e., the outgoing edges of the i-th set vertex)
    553             for (std::tie(ei, ei_end) = out_edges(i + m, mMultiplexSetGraph); ei != ei_end; ++ei) {
    554                 Si.insert(target(*ei, mMultiplexSetGraph));
    555             }
    556         }
    557 
    558         // Make all vertices in G adjacent if their sets intersect.
    559         for (unsigned i = 1; i != n; ++i) {
    560             const Set & Si = S[i];
    561             for (unsigned j = 0; j != i; ++j) {
    562                 const Set & Sj = S[j];
    563                 auto mi = Si.begin();
    564                 const auto mi_end = Si.end();
    565                 auto mj = Sj.begin();
    566                 const auto mj_end = Sj.end();
    567                 while (mi != mi_end && mj != mj_end) {
    568                     if (*mi < *mj) {
    569                         ++mi;
    570                     }
    571                     else if (*mj < *mi) {
    572                         ++mj;
    573                     }
    574                     else {
    575                         // they intersect; add an edge between them.
    576                         add_edge(i, j, G);
    577                         break;
    578                     }
     540    for (IndependentSetGraph::vertex_descriptor i = 0; i != n; ++i) {
     541        G[i] = out_degree(i + m, mMultiplexSetGraph);
     542    }
     543
     544    // Let M be mMultiplexSetGraph. Each vertex in G corresponds to a set vertex in M.
     545    // If an advance vertex in M (i.e., one of the first m vertices of M) is adjacent
     546    // to two or more set vertices, add an edge between the corresponding vertices in G.
     547    // I.e., make all vertices in G adjacent if their corresponding sets intersect.
     548
     549    for (unsigned i = 0; i != m; ++i) {
     550        if (in_degree(i, mMultiplexSetGraph) > 1) {
     551            graph_traits<MultiplexSetGraph>::in_edge_iterator ei_begin, ei_end;
     552            std::tie(ei_begin, ei_end) = in_edges(i, mMultiplexSetGraph);
     553            for (auto ei = ei_begin; ei != ei_end; ++ei) {
     554                for (auto ej = ei_begin; ej != ei; ++ej) {
     555                    // Note: ei and ej are incoming edges. The source is the set vertex,
     556                    // which must have a id >= m.
     557                    add_edge(source(*ei, mMultiplexSetGraph) - m, source(*ej, mMultiplexSetGraph) - m, G);
    579558                }
    580559            }
     
    608587            break;
    609588        }
    610         // Select u from S
     589        // Select u from S       
    611590        const auto i = S.begin() + RNGDistribution(0, S.size() - 1)(rng);
    612591        const auto u = *i;
    613592        S.erase(i);
    614 
    615593        // Remove u and its adjacencies from G; clear the adjacent set vertices from the multiplex set graph. This will effectively
    616594        // choose the set refered to by u as one of our chosen independent sets and discard any other sets that contain one
     
    702680                    PabloBlock * pb = adv->getParent();
    703681
    704                     #define CHOOSE(A,B,C) (isa<Statement>(A) ? cast<Statement>(A) : (isa<Statement>(B) ? cast<Statement>(B) : C))
    705 
    706682                    for (auto i : V) {
    707683                        Q.push(mAdvance[i]->getOperand(0));
     
    710686                        PabloAST * a1 = Q.front(); Q.pop();
    711687                        PabloAST * a2 = Q.front(); Q.pop();
    712                         pb->setInsertPoint(CHOOSE(a2, a1, adv));
     688                        pb->setInsertPoint(cast<Statement>(a2));
    713689                        Q.push(pb->createOr(a1, a2));
    714690                    }
     
    733709                        PabloAST * a1 = Q.front(); Q.pop();
    734710                        PabloAST * a2 = Q.front(); Q.pop();
    735                         pb->setInsertPoint(CHOOSE(a2, a1, adv));
     711                        pb->setInsertPoint(cast<Statement>(a2));
    736712                        Q.push(pb->createOr(a1, a2));
    737713                    }
     
    762738 * @brief multiplexSelectedIndependentSets
    763739 ** ------------------------------------------------------------------------------------------------------------- */
    764 void AutoMultiplexing::multiplexSelectedIndependentSets() {
     740void AutoMultiplexing::multiplexSelectedIndependentSets() const {
    765741
    766742    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
     
    783759            const unsigned m = static_cast<unsigned>(std::ceil(std::log2(n))); // use a faster builtin function for this.
    784760
     761            assert (n < (1 << m));
     762
    785763            graph_traits<MultiplexSetGraph>::out_edge_iterator ei_begin, ei_end;
    786764            std::tie(ei_begin, ei_end) = out_edges(s, mMultiplexSetGraph);
     
    790768            std::sort(V.begin(), V.begin() + n);
    791769
     770//            raw_os_ostream out(std::cerr);
     771
     772//            out << "M={";
     773//            for (auto i = 0; i != n; ++i) {
     774//                out << ' ' << mAdvance[V[i]]->getName()->to_string() << " (" << (ptrdiff_t)(mAdvance[V[i]]->getParent()) << ")";
     775//            }
     776//            out << "}\n\n";
     777
    792778            PabloBlock * const pb = mAdvance[V[0]]->getParent();
     779            assert (pb);
     780
    793781            // Sanity test to make sure every advance is in the same scope.
    794782            #ifndef NDEBUG
    795783            for (auto i = 1; i != n; ++i) {
     784                assert (V[i - 1] < V[i]);
     785                assert (V[i] < mAdvance.size());
    796786                assert (mAdvance[V[i]]->getParent() == pb);
    797787            }
    798788            #endif
     789
     790            // Store the original users of our advances; we'll be modifying these extensively shortly.
     791            for (unsigned i = 0; i != n; ++i) {
     792                const Advance * const adv = mAdvance[V[i]];
     793                assert (users[i].empty());
     794                users[i].insert(users[i].begin(), adv->user_begin(), adv->user_end()) ;
     795            }
    799796
    800797            /// Perform n-to-m Multiplexing
    801798            for (unsigned j = 0; j != m; ++j) {
    802                 for (unsigned i = 0; i != (1 << m); ++i) {
    803                     if (((i + 1) & (1 << j)) != 0) {
    804                         T.push(mAdvance[V[i]]->getOperand(0));
     799                for (unsigned i = 1; i != (1 << m); ++i) {
     800                    if ((i & (1 << j)) != 0) {
     801                        T.push(mAdvance[V[i - 1]]->getOperand(0));
    805802                    }
    806803                }
     
    812809                    PabloAST * a1 = T.front(); T.pop();
    813810                    PabloAST * a2 = T.front(); T.pop();
    814                     pb->setInsertPoint(CHOOSE(a2, a1, adv));
     811                    pb->setInsertPoint(cast<Statement>(a2));
    815812                    T.push(pb->createOr(a1, a2));
    816813                }
    817                 adv->setOperand(0, T.front()); T.pop();
     814                assert (T.size() == 1);                               
     815
     816                PabloAST * mux = T.front(); T.pop();
     817                #ifdef PROVIDE_ASSIGNMENT_STATEMENTS_FOR_MUX_AND_DEMUX_STATEMENTS
     818                mux = pb->createAssign("mux", mux);
     819                #endif
     820
     821                adv->setOperand(0, mux);
    818822            }
    819823
    820824            /// Perform m-to-n Demultiplexing
    821             // Store the original users of our advances; we'll be modifying these extensively shortly.
    822             for (unsigned i = 0; i != n; ++i) {
    823                 const Advance * const adv = mAdvance[V[i]];
    824                 users[i].insert(users[i].begin(), adv->user_begin(), adv->user_end()) ;
    825             }
    826 
    827825            // Now construct the demuxed values and replaces all the users of the original advances with them.
    828             for (unsigned i = 0; i != n; ++i) {
    829                 Advance * adv = mAdvance[V[i]];
     826            for (unsigned i = 1; i <= n; ++i) {
     827
     828                assert (T.size() == 0 && F.size() == 0);
     829
    830830                for (unsigned j = 0; j != m; ++j) {
    831                     if (((i + 1) & (1 << j)) != 0) {
     831                    if ((i & (1 << j)) != 0) {
    832832                        T.push(mAdvance[V[j]]);
    833833                    }
     
    836836                    }
    837837                }
     838
     839                assert (T.size() > 0);
     840
    838841                while (T.size() > 1) {
    839842                    PabloAST * a1 = T.front(); T.pop();
    840843                    PabloAST * a2 = T.front(); T.pop();
    841                     pb->setInsertPoint(CHOOSE(a2, a1, adv));
     844                    pb->setInsertPoint(cast<Statement>(a2));
    842845                    T.push(pb->createAnd(a1, a2));
    843846                }
     847
    844848                assert (T.size() == 1);
    845849
    846                 while (F.size() > 1) {
    847                     PabloAST * a1 = T.front(); T.pop();
    848                     PabloAST * a2 = T.front(); T.pop();
    849                     pb->setInsertPoint(CHOOSE(a2, a1, adv));
    850                     F.push(pb->createOr(a1, a2));
    851                 }
    852                 assert (F.size() == 1);
    853 
    854                 PabloAST * const demux = pb->createAnd(T.front(), pb->createNot(F.front()), "demux"); T.pop(); F.pop();
    855                 for (PabloAST * use : users[i]) {
     850                PabloAST * demux = T.front(); T.pop();
     851
     852                if (LLVM_LIKELY(F.size() > 0)) {
     853                    while (F.size() > 1) {
     854                        PabloAST * a1 = T.front(); T.pop();
     855                        PabloAST * a2 = T.front(); T.pop();
     856                        pb->setInsertPoint(cast<Statement>(a2));
     857                        F.push(pb->createOr(a1, a2));
     858                    }
     859                    assert (F.size() == 1);
     860                    demux = pb->createAnd(demux, pb->createNot(F.front())); F.pop();
     861                }
     862
     863                #ifdef PROVIDE_ASSIGNMENT_STATEMENTS_FOR_MUX_AND_DEMUX_STATEMENTS
     864                demux = pb->createAssign("demux", demux);
     865                #endif
     866
     867                Advance * const adv = mAdvance[V[i - 1]];
     868                for (PabloAST * use : users[i - 1]) {
    856869                    cast<Statement>(use)->replaceUsesOfWith(adv, demux);
    857870                }
     
    881894void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
    882895
    883     TopologicalSortGraph G;
    884     TopologicalSortQueue Q;
    885     TopologicalSortMap map;
    886 
     896    // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
     897
     898    std::unordered_set<PabloAST *> encountered;
    887899    std::stack<Statement *> scope;
    888 
    889     Statement * ip = nullptr;
    890     Statement * first;
    891     Statement * stmt;
    892 
    893     for (first = stmt = entry.front(); ; ) {
     900    for (Statement * stmt = entry.front(); ; ) {
    894901
    895902        while ( stmt ) {
     903
     904            bool moved = false;
     905
     906            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     907                PabloAST * const op = stmt->getOperand(i);
     908                if (LLVM_LIKELY(isa<Statement>(op))) {
     909                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
     910                        Statement * next = stmt->getNextNode();
     911                        stmt->insertAfter(cast<Statement>(op));
     912                        stmt = next;
     913                        moved = true;
     914                        break;
     915                    }
     916                }
     917            }
     918
     919            if (moved) {
     920                continue;
     921            }
     922
     923            encountered.insert(stmt);
     924
    896925            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    897                 // Sort the current "basic block"
    898                 topologicalSort(G, Q, map, ip, first);
    899926                // Set the next statement to be the first statement of the inner scope and push the
    900927                // next statement of the current statement into the scope stack.
    901928                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    902                 scope.push(stmt);
    903                 ip = nullptr;
    904                 first = stmt = nested.front();
     929                scope.push(stmt->getNextNode());
     930                stmt = nested.front();
    905931                assert (stmt);
    906932                continue;
    907933            }
    908934
    909             const auto u = add_vertex(stmt, G);
    910             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    911                 auto f = map.find(stmt->getOperand(i));
    912                 if (f == map.end()) {
    913                     continue;
    914                 }
    915                 add_edge(f->second, u, G);
    916             }
    917             if (in_degree(u, G) == 0) {
    918                 Q.push(u);
    919             }
    920             map.emplace(stmt, u);
    921935            stmt = stmt->getNextNode();
    922936        }
    923937
    924         topologicalSort(G, Q, map, ip, first);
    925938        if (scope.empty()) {
    926939            break;
    927940        }
    928         ip = scope.top();
     941        stmt = scope.top();
    929942        scope.pop();
    930         first = stmt = ip->getNextNode();
    931     }
    932 
    933 }
    934 
    935 void AutoMultiplexing::topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q, TopologicalSortMap & M, Statement * ip, Statement * first) const {
    936     Statement * stmt = first;
    937     while (!Q.empty()) {
    938         const auto u = Q.front(); Q.pop();
    939         graph_traits<TopologicalSortGraph>::out_edge_iterator ei, ei_end;
    940         for (std::tie(ei, ei_end) = out_edges(u, G); ei != ei_end; ++ei) {
    941             const auto v = target(*ei, G);
    942             if (in_degree(v, G) == 1) {
    943                 Q.push(v);
    944             }
    945         }
    946         Statement * next = G[u];
    947         if (stmt != next) {
    948             if (LLVM_UNLIKELY(ip == nullptr)) {
    949                 next->insertBefore(first);
    950             }
    951             else {
    952                 next->insertAfter(ip);
    953             }
    954         }
    955         ip = next;
    956     }
    957     G.clear();
    958     M.clear();
    959 }
     943    }
     944
     945}
     946
    960947
    961948} // end of namespace pablo
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4583 r4585  
    4848    void approxMaxWeightIndependentSet(RNG & rng);
    4949    void applySubsetConstraints();
    50     void multiplexSelectedIndependentSets();
     50    void multiplexSelectedIndependentSets() const;
    5151    void topologicalSort(PabloBlock & entry) const;
    52     void topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q, TopologicalSortMap & M, Statement * ip, Statement * first) const;
    5352    inline AutoMultiplexing()
    5453    : mPathGraph(0) {
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4510 r4585  
    101101
    102102void Statement::setOperand(const unsigned index, PabloAST * const value) {
     103    assert (value);
    103104    assert (index < getNumOperands());
    104105    assert (noRecursiveOperand(value));
Note: See TracChangeset for help on using the changeset viewer.