Ignore:
Timestamp:
May 27, 2015, 12:43:25 PM (4 years ago)
Author:
nmedfort
Message:

More multiplexing work

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4579 r4581  
    638638        N = std::max<unsigned>(N, out_degree(s, mMultiplexSetGraph));
    639639    }
    640     unsigned M = static_cast<unsigned>(std::ceil(std::log2(N))); // use a faster builtin function for this.
    641640
    642641    std::vector<MultiplexSetGraph::vertex_descriptor> V(N);
    643     std::queue<PabloAST *> T(M);
    644     std::queue<PabloAST *> F(M);
    645     std::vector<SmallVector<User *, 4>> users(N);
     642    std::queue<PabloAST *> T;
     643    std::queue<PabloAST *> F;
     644    std::vector<SmallVector<PabloAST *, 4>> users(N);
    646645
    647646    for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMultiplexSetGraph); s != e; ++s) {
     
    745744 * it's not necessarily the original ordering.
    746745 ** ------------------------------------------------------------------------------------------------------------- */
    747 void AutoMultiplexing::topologicalSort(PabloBlock & entry) {
     746void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
    748747
    749748    TopologicalSortGraph G;
    750749    TopologicalSortQueue Q;
    751     flat_map<Statement *, TopologicalSortGraph::vertex_descriptor> map;
    752 
    753     std::stack<std::pair<Statement *, PabloBlock *>> scope;
    754 
    755 
    756     Statement * insertionPtr = nullptr;
    757     PabloBlock * insertionBlock = &entry;
    758 
    759     for (Statement * stmt = entry.front(); ; ) {
     750    TopologicalSortMap map;
     751
     752    std::stack<Statement *> scope;
     753
     754    Statement * ip = nullptr, first, stmt;
     755
     756    for (first = stmt = entry.front(); ; ) {
     757
    760758        while ( stmt ) {
    761759            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     760                // Sort the current "basic block"
     761                topologicalSort(G, Q, map, ip, first);
    762762                // Set the next statement to be the first statement of the inner scope and push the
    763763                // next statement of the current statement into the scope stack.
    764764                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    765                 scope.push(std::make_pair(stmt, insertionBlock));
    766                 insertionBlock = &nested;
    767                 insertionPtr = nullptr;
    768                 stmt = nested.front();
     765                scope.push(stmt);
     766                ip = nullptr;
     767                first = stmt = nested.front();
    769768                assert (stmt);
    770769                continue;
     
    779778                add_edge(f->second, u);
    780779            }
    781             if (in_degree(u, G)) {
     780            if (in_degree(u, G) == 0) {
    782781                Q.push(u);
    783782            }
    784783            map.emplace(stmt, u);
    785 
    786 
    787 
    788 
    789784            stmt = stmt->getNextNode();
    790785        }
     786
     787        topologicalSort(G, Q, map, ip, first);
    791788        if (scope.empty()) {
    792789            break;
    793790        }
    794         std::tie(insertionPtr, insertionBlock) = scope.top();
     791        ip = scope.top();
    795792        scope.pop();
    796         stmt = insertionPtr->getNextNode();
    797     }
    798 
    799 }
    800 
    801 void AutoMultiplexing::topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q) {
    802 
    803 
    804     std::vector<Statement *> L;
    805     L.reserve(num_vertices(G));
     793        first = stmt = ip->getNextNode();
     794    }
     795
     796}
     797
     798void AutoMultiplexing::topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q, TopologicalSortMap & M, Statement * ip, Statement * first) const {
     799    Statement * stmt = first;
    806800    while (!Q.empty()) {
    807801        const auto u = Q.front(); Q.pop();
     
    813807            }
    814808        }
    815         clear_out_edges(u, G);
    816         L.push_back(G[u]);
    817     }
    818 
    819 
    820 }
     809        Statement * next = G[u];
     810        if (stmt != next) {
     811            if (LLVM_UNLIKELY(ip == nullptr)) {
     812                next->insertBefore(first);
     813            }
     814            else {
     815                next->insertAfter(ip);
     816            }
     817        }
     818        ip = next;
     819    }
     820    G.clear();
     821    M.clear();
     822}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4579 r4581  
    2727    using TopologicalSortGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::directedS, PabloAST *>;
    2828    using TopologicalSortQueue = std::queue<TopologicalSortGraph::vertex_descriptor>;
     29    using TopologicalSortMap = boost::container::flat_map<Statement *, TopologicalSortGraph::vertex_descriptor>;
    2930
    3031    using RNG = std::mt19937;
     
    4748    void multiplexSelectedIndependentSets();
    4849    void topologicalSort(PabloBlock & entry) const;
    49     void topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q) const;
     50    void topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q, TopologicalSortMap & M, Statement * ip, Statement * first) const;
    5051
    5152private:
Note: See TracChangeset for help on using the changeset viewer.