Changeset 4581 for icGREP


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

More multiplexing work

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/analysis/bdd/bdd.cpp

    r4569 r4581  
    7878        const size_t index = mNode.size();
    7979        mNode.emplace_back(level, low, high);
    80         f = mMap.insert(std::make_pair(std::make_tuple(level, low, high), index)).second;
     80        f = mMap.insert(std::make_pair(std::make_tuple(level, low, high), index)).first;
    8181    }
    8282    return f->second;
     
    8888    const Node & v = mNode[root];
    8989    if (ISZERO(v.low)) {
    90         return makeNode(v.level, 0, satOne(v.high).mRoot);
     90        return makeNode(v.level, 0, satOne(v.high));
    9191    }
    9292    else {
    93         return makeNode(v.level, satOne(v.low).mRoot, 0);
     93        return makeNode(v.level, satOne(v.low), 0);
    9494    }
    9595}
     
    111111}
    112112
    113 Engine::Engine(const size_t initialSize)
    114 : mNode(LLVMAllocatorProxy(mAllocator))
    115 , mVar(LLVMAllocatorProxy(mAllocator))
    116 , mMap(LLVMAllocatorProxy(mAllocator)) {
     113Engine::Engine(const size_t initialSize) {
    117114    mNode.reserve(initialSize + 2);
    118115    mMap.bucket_size(initialSize);
     
    129126
    130127    // and the variables
    131     addVars(varCount);
     128    mVar.resize(initialSize * 2);
     129    for (auto i = 0; i != initialSize; ++i) {
     130        mVar[i * 2] = makeNode(i, 0, 1);
     131        mVar[i * 2 + 1] = makeNode(i, 1, 0);
     132    }
    132133}
    133134
  • icGREP/icgrep-devel/icgrep/pablo/analysis/bdd/bdd.hpp

    r4571 r4581  
    2626    };
    2727
     28    using index_type = unsigned;
     29
    2830    struct Node {
    2931        friend struct BDD;
     
    3739        }
    3840
    39         const unsigned level;
    40         const unsigned low;
    41         const unsigned high;
     41        const index_type level;
     42        const index_type low;
     43        const index_type high;
    4244    };
    4345
    44     using Array = std::vector<Node, LLVMAllocatorProxy>;
    45     using index_type = unsigned;
    46     using Vars = std::vector<index_type, LLVMAllocatorProxy>;
    4746    using Key = std::tuple<index_type, index_type, index_type>;
     47    using Array = std::vector<Node>;
     48    using Vars = std::vector<index_type>;
    4849
    4950    struct BijectionHash {
     
    5758    };
    5859    #ifdef USE_BOOST
    59     using Map = boost::unordered_map<Key, Array::size_type, BijectionHash, std::equal_to<Key>, LLVMAllocatorProxy<std::pair<Key, index_type>>;
     60    using Map = boost::unordered_map<Key, index_type, BijectionHash, std::equal_to<Key>>;
    6061    #else
    61     using Map = std::unordered_map<Key, index_type, BijectionHash, std::equal_to<Key>, LLVMAllocatorProxy<std::pair<Key, index_type>>;
     62    using Map = std::unordered_map<Key, index_type, BijectionHash, std::equal_to<Key>>;
    6263    #endif
    6364
     
    8889    index_type satOne(const index_type root);
    8990
     91    index_type apply(const index_type l, const OpCode op);
     92
    9093    index_type apply(const index_type l, const index_type r, const OpCode op);
    9194
     
    102105struct BDD {
    103106
    104     friend struct Engine;
     107    friend class Engine;
    105108
    106109    using OpCode = Engine::OpCode;
     
    109112    inline int operator==(const bool term) const {
    110113        return term ? isTrue() : isFalse();
    111     }
    112 
    113     inline BDD & operator=(const bool term) const {
    114         mRoot = term ? 0 : 1;
    115         return *this;
    116114    }
    117115
  • 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.