Ignore:
Timestamp:
May 20, 2015, 12:51:44 PM (4 years ago)
Author:
nmedfort
Message:

Some work on multiplexing.

Location:
icGREP/icgrep-devel/icgrep/pablo/analysis/bdd
Files:
2 edited

Legend:

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

    r4536 r4569  
    1919    const Node & n = mNode[l];
    2020
    21     return makenode(n.level, n.low, n.high);
     21    return makeNode(n.level, n.low, n.high);
    2222}
    2323
     
    6767    }
    6868
    69     return makenode(level, apply(lowl, lowr, op), apply(highl, highr, op));
     69    return makeNode(level, apply(lowl, lowr, op), apply(highl, highr, op));
    7070}
    7171
    72 Engine::index_type Engine::makenode(const index_type level, const index_type low, const index_type high) {
     72Engine::index_type Engine::makeNode(const index_type level, const index_type low, const index_type high) {
    7373    if (low == high) {
    7474        return low;
     
    8383}
    8484
    85 Engine::index_type Engine::satone(const index_type root) {
     85Engine::index_type Engine::satOne(const index_type root) {
    8686    if (ISCONST(root))
    8787       return root;
    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).mRoot);
    9191    }
    9292    else {
    93         return makenode(v.level, satone(v.low).mRoot, 0);
     93        return makeNode(v.level, satOne(v.low).mRoot, 0);
    9494    }
    9595}
     
    105105BDD Engine::addVar() {
    106106    unsigned level = mVar.size() >> 1;
    107     index_type var = makenode(level, 0, 1);
     107    index_type var = makeNode(level, 0, 1);
    108108    mVar.push_back(var);
    109     mVar.push_back(makenode(level, 1, 0));
     109    mVar.push_back(makeNode(level, 1, 0));
    110110    return BDD(var);
    111111}
    112112
    113 void Engine::addVars(const size_t vars) {
    114     unsigned level = mVar.size() >> 1;
    115     for (size_t i = 0; i != vars; ++i, ++level) {
    116         mVar.push_back(makenode(level, 0, 1));
    117         mVar.push_back(makenode(level, 1, 0));
    118     }
    119 }
    120 
    121 Engine::Engine(const size_t initialSize, const size_t varCount)
     113Engine::Engine(const size_t initialSize)
    122114: mNode(LLVMAllocatorProxy(mAllocator))
    123115, mVar(LLVMAllocatorProxy(mAllocator))
  • icGREP/icgrep-devel/icgrep/pablo/analysis/bdd/bdd.hpp

    r4536 r4569  
    5757    };
    5858    #ifdef USE_BOOST
    59     using Map = boost::unordered_map<Key, Array::size_type, BijectionHash, std::equal_to<Key>, LLVMAllocatorProxy>;
     59    using Map = boost::unordered_map<Key, Array::size_type, BijectionHash, std::equal_to<Key>, LLVMAllocatorProxy<std::pair<Key, index_type>>;
    6060    #else
    61     using Map = std::unordered_map<Key, index_type, BijectionHash, std::equal_to<Key>, LLVMAllocatorProxy>;
     61    using Map = std::unordered_map<Key, index_type, BijectionHash, std::equal_to<Key>, LLVMAllocatorProxy<std::pair<Key, index_type>>;
    6262    #endif
    6363
    6464public:
    6565
    66     Engine(const size_t initialSize, const size_t varCount);
     66    Engine(const size_t initialSize);
    6767
    68     BDD applyAND(const BDD & r, const BDD & l);
     68    BDD applyAnd(const BDD & r, const BDD & l);
    6969
    70     BDD applyOR(const BDD & r, const BDD & l);
     70    BDD applyOr(const BDD & r, const BDD & l);
    7171
    72     BDD applyNOT(const BDD & bdd);
     72    BDD applyNot(const BDD & bdd);
    7373
    74     BDD applyXOR(const BDD & r, const BDD & l);
     74    BDD applyXor(const BDD & r, const BDD & l);
    7575
    76     BDD applySEL(const BDD & cond, const BDD & trueBDD, const BDD & falseBDD);
     76    BDD applySel(const BDD & cond, const BDD & trueBDD, const BDD & falseBDD);
    7777
    7878    BDD addVar();
    79 
    80     void addVars(const size_t vars);
    8179
    8280    BDD var(const unsigned index);
     
    8482    BDD nvar(const unsigned index);
    8583
     84    BDD satOne(const BDD & bdd);
     85
    8686protected:
    8787
    88     index_type satone(const index_type root);
     88    index_type satOne(const index_type root);
    8989
    9090    index_type apply(const index_type l, const index_type r, const OpCode op);
    9191
    92     index_type makenode(const index_type level, const index_type low, const index_type high);
     92    index_type makeNode(const index_type level, const index_type low, const index_type high);
    9393
    9494private:
     
    102102struct BDD {
    103103
     104    friend struct Engine;
     105
    104106    using OpCode = Engine::OpCode;
    105107    using index_type = Engine::index_type;
    106108
    107     inline int operator==(const BDD &r) const {
     109    inline int operator==(const bool term) const {
     110        return term ? isTrue() : isFalse();
     111    }
     112
     113    inline int operator==(const bool term) const {
     114        return term ? isFalse() : isTrue();
     115    }
     116
     117    inline int operator==(const BDD & r) const {
    108118        return mRoot == r.mRoot;
    109119    }
    110120
    111     inline int operator!=(const BDD &r) const {
     121    inline int operator!=(const BDD & r) const {
    112122        return mRoot != r.mRoot;
    113123    }
    114124
    115     inline bool isZero() const {
     125    inline bool isFalse() const {
    116126        return mRoot == 0;
    117127    }
    118128
    119     inline bool isOne() const {
     129    inline bool isTrue() const {
    120130        return mRoot == 1;
    121131    }
     
    125135    }
    126136
    127     inline BDD() : mRoot(0) {}
     137    inline BDD Contradiction() const {
     138        return BDD(0);
     139    }
     140
     141    inline BDD Tautology() const {
     142        return BDD(1);
     143    }
    128144
    129145protected:
    130146
     147    inline BDD() : mRoot(0) {}
    131148    inline BDD(const index_type index) : mRoot(index) { }
    132149    inline BDD(const BDD & r) : mRoot(r.mRoot) {  }
     
    139156};
    140157
    141 BDD Engine::satone(const BDD & bdd) {
     158BDD Engine::satOne(const BDD & bdd) {
    142159    if (bdd.isConstant()) {
    143160        return bdd;
    144161    }
    145     return BDD(satone(bdd.mRoot));
     162    return BDD(satOne(bdd.mRoot));
    146163}
    147164
    148 BDD Engine::applyAND(const BDD & r, const BDD & l) {
     165BDD Engine::applyAnd(const BDD & r, const BDD & l) {
    149166    return apply(r.mRoot, l.mRoot, BDD::OpCode::AND);
    150167}
    151168
    152 BDD Engine::applyOR(const BDD & r, const BDD & l) {
     169BDD Engine::applyOr(const BDD & r, const BDD & l) {
    153170    return apply(r.mRoot, l.mRoot, BDD::OpCode::OR);
    154171}
    155172
    156 BDD Engine::applyNOT(const BDD & bdd) {
     173BDD Engine::applyNot(const BDD & bdd) {
    157174    return apply(bdd.mRoot, BDD::OpCode::NOT);
    158175}
    159176
    160 BDD Engine::applyXOR(const BDD & r, const BDD & l) {
     177BDD Engine::applyXor(const BDD & r, const BDD & l) {
    161178    return apply(r.mRoot, l.mRoot, BDD::OpCode::XOR);
    162179}
    163180
    164 BDD Engine::applySEL(const BDD & cond, const BDD & trueBDD, const BDD & falseBDD) {
    165     return applyOR(applyAND(cond, trueBDD), applyAND(applyNOT(cond), falseBDD));
     181BDD Engine::applySel(const BDD & cond, const BDD & trueBDD, const BDD & falseBDD) {
     182    return applyOr(applyAnd(cond, trueBDD), applyAnd(applyNot(cond), falseBDD));
    166183}
    167184
Note: See TracChangeset for help on using the changeset viewer.