Changeset 4569


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
Files:
2 added
7 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
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r4524 r4569  
    417417, mParent(predecessor)
    418418{
    419 
     419    // predecessor->addUser(this);
    420420}
    421421
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4536 r4569  
    44#include <llvm/ADT/DenseMap.h>
    55#include <llvm/ADT/DenseSet.h>
     6#include <stack>
     7#include <queue>
     8#include <unordered_set>
    69#include <pablo/analysis/bdd/bdd.hpp>
    7 #include <stack>
     10#include <boost/container/flat_set.hpp>
     11#include <boost/numeric/ublas/matrix.hpp>
    812
    913using namespace llvm;
    1014using namespace bdd;
     15using namespace boost;
     16using namespace boost::container;
     17using namespace boost::numeric::ublas;
    1118
    1219namespace pablo {
    1320
    1421static void AutoMultiplexing::optimize(PabloBlock & block) {
    15     // indentifyInputVariables
    16 
    17 
    18     // generateVariableConstraints
    19 
    20 
    21 
    22     // identifySuffixConstraints
    23 
    24 
    25 
    26 }
    27 
    28 void AutoMultiplexing::generateVariableConstraints(const PabloBlock & block, const std::vector<pablo::Var *> & inputVars) {
    29 
    30     Engine engine(1000, inputVars.size());
    31     std::unordered_map<const PabloAST *, BDD> transitoryNodes;
    32 
    33     for (auto i = 0; i != inputVars.size(); ++i) {
    34         transitoryNodes.insert(std::make_pair(inputVars[i], engine.var(i)));
    35     }
    36 
     22    AutoMultiplexing am;
     23
     24    Engine eng = am.initialize(block, vars);
     25    am.characterize(eng, vars);
     26
     27
     28}
     29
     30/** ------------------------------------------------------------------------------------------------------------- *
     31 * @brief initialize
     32 * @param vars the input vars for this program
     33 * @param entry the entry block
     34 *
     35 * Scan through the program to identify any advances and calls then initialize the BDD engine with
     36 * the proper variable ordering.
     37 ** ------------------------------------------------------------------------------------------------------------- */
     38Engine AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry) {
     39
     40    std::vector<const Statement *> advances;
    3741    std::stack<const Statement *> scope;
    38     const Statement * stmt = block.front();
    39     while(true) {
     42
     43    unsigned variables = 0;
     44
     45    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
     46    unsigned n = 1;
     47    for (const Statement * stmt = entry.front(); ; ) {
    4048        for (; stmt; stmt = stmt->getNextNode()) {
    41 
    42             if (isa<If>(stmt) || isa<While>(stmt)) {
     49            ++n;
     50            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    4351                // Set the next statement to be the first statement of the inner scope and push the
    4452                // next statement of the current statement into the scope stack.
    45                 PabloBlock & b = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     53                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    4654                scope.push(stmt->getNextNode());
    47                 stmt = b.front();
    48             }
    49 
    50             BDD bdd;
    51 
    52             if (isa<Call>(stmt)) {
    53                 // TODO: Have a BDD precomputed for each called function?
    54                 // Note: this assumes that no Call occurs twice in the function.
    55                 bdd = engine.addVar();
    56             }
    57             else {
    58 
    59                 bool ignore = false;
    60 
    61                 std::array<BDD> nodes;
    62                 for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    63                     auto f = transitoryNodes.find(stmt->getOperand(i));
    64                     if (f == transitoryNodes.end()) {
    65                         ignore = true;
    66                         break;
    67                     }
    68                     nodes[i] = f->second;
    69                 }
    70 
    71                 if (ignore) {
    72                     continue;
    73                 }
    74 
    75                 switch (stmt->getClassTypeId()) {
    76                     case PabloAST::ClassTypeId::And:
    77                         bdd = engine.applyAND(nodes[0], nodes[1]);
    78                         break;
    79                     case PabloAST::ClassTypeId::Or:
    80                         bdd = engine.applyOR(nodes[0], nodes[1]);
    81                         break;
    82                     case PabloAST::ClassTypeId::Xor:
    83                         bdd = engine.applyXOR(nodes[0], nodes[1]);
    84                         break;
    85                     case PabloAST::ClassTypeId::Not:
    86                         bdd = engine.applyNOT(nodes[0]);
    87                         break;
    88                     case PabloAST::ClassTypeId::Sel:
    89                         bdd = engine.applySEL(nodes[0], nodes[1], nodes[2]);
    90                         break;
    91                     default:
    92                         ignore = true;
    93                 }
    94 
    95                 if (ignore) {
    96                     continue;
    97                 }
    98             }
    99 
    100             transitoryNodes.insert(std::make_pair(stmt, bdd));
     55                stmt = nested.front();
     56                assert (stmt);
     57                continue;
     58            }
     59            switch (stmt->getClassTypeId()) {
     60                case PabloAST::ClassTypeId::Advance:
     61                    advances.push_back(stmt);
     62                case PabloAST::ClassTypeId::Call:
     63                case PabloAST::ClassTypeId::ScanThru:
     64                case PabloAST::ClassTypeId::MatchStar:
     65                    ++variables;
     66                    break;
     67                default:
     68                    break;
     69            }
    10170        }
    10271        if (scope.empty()) {
     
    10776    }
    10877
    109 
    110 //    for (unsigned i = 0; i < variables.size(); ++i) {
    111 //        const Instruction * const instI = variables[i];
    112 //        _variableConstraints.add(instI);
    113 //        #ifdef ALLOW_SUBSET_CONSTRAINT_TRANSFORMATIONS
    114 //        _subsetConstraints.add(instI);
    115 //        #endif
    116 //        const bdd & A = transitoryVariables.find(instI)->second;
    117 
    118 //        // std::cout << bddset << A << std::endl;
    119 
    120 //        for (unsigned j = 0; j < i; ++j) {
    121 //            const Instruction * const instJ = variables[j];
    122 //            // are these variables within differing basic blocks?
    123 //            bool constrained = true;
    124 //            // if (instI->getParent() == instJ->getParent()) {
    125 //                // or is there any truth assignment can satisfy both "character class" equations?
    126 //                const bdd & B = transitoryVariables.find(instJ)->second;
    127 //                const bdd C = A & B;
    128 //                // is there any satisfying truth assignment?
    129 //                if (bdd_satone(C) == bdd_false()) {
    130 //                    constrained = false;
    131 //                }
    132 //                #ifdef ALLOW_SUBSET_CONSTRAINT_TRANSFORMATIONS
    133 //                // is one a subset of the other?
    134 //                else if (A == C) {
    135 //                    _subsetConstraints.addConstraint(instI, instJ);
    136 //                    constrained = false;
    137 //                }
    138 //                else if (B == C) {
    139 //                    _subsetConstraints.addConstraint(instJ, instI);
    140 //                    constrained = false;
    141 //                }
    142 //                #endif
    143 //            // }
    144 //            if (constrained) {
    145 //                // if so, these these character classes are not mutually exclusive and cannot be
    146 //                // multiplexed together; mark the constraint accordingly.
    147 //                _variableConstraints.addConstraint(instI, instJ);
     78    // create the transitive closure matrix of our advances; we'll use
     79    const unsigned m = advances.size() + 1;
     80    flat_map<PabloAST *, unsigned> map;
     81    for (const Var * var : vars) {
     82        map.emplace(var, 0);
     83    }
     84    for (unsigned i = 1; i != m; ++i) {
     85        map.emplace(advances[i], i);
     86    }
     87    matrix<bool> G(n, m);
     88    G.clear();
     89    for (unsigned i = 0; i != m; ++i) {
     90        G(i, i) = true;
     91    }
     92
     93    for (const Statement * stmt = entry.front(), n = 1; ; ) {
     94        for (; stmt; stmt = stmt->getNextNode()) {
     95            // Fill in the transitive closure G ...
     96            const unsigned u = n++;
     97            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     98                const unsigned v = map[stmt->getOperand(i)];
     99                for (unsigned w = 0; w != m; ++w) {
     100                    G(v, w) |= G(u, w);
     101                }
     102            }
     103            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     104                // Set the next statement to be the first statement of the inner scope and push the
     105                // next statement of the current statement into the scope stack.
     106                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     107                scope.push(stmt->getNextNode());
     108                stmt = nested.front();
     109                assert (stmt);
     110                continue;
     111            }
     112        }
     113        if (scope.empty()) {
     114            break;
     115        }
     116        stmt = scope.top();
     117        scope.pop();
     118    }
     119
     120    // Record our transitive closure in the path graph and remove any reflexive-loops
     121    mPathGraph = PathGraph(m);
     122    for (unsigned i = 0; i != m; ++i) {
     123        for (unsigned j = 0; j != m; ++j) {
     124            if (G(i, j)) {
     125                add_edge(i, j, mPathGraph);
     126            }
     127        }
     128        G(i, i) = false;
     129    }
     130
     131    // Now transcribe the transitive reduction of G into our constraint graph
     132    mConstraintGraph = ConstraintGraph(m);
     133    for (unsigned j = 0; j != m; ++j) {
     134        for (unsigned i = 0; i != m; ++i) {
     135            if (G(i, j)) {
     136                add_edge(i, j, mConstraintGraph);
     137                // Eliminate any unecessary arcs not covered by a longer path
     138                for (unsigned k = 0; k != m; ++k) {
     139                    G(i, k) = G(j, k) ? false : G(i, k);
     140                }
     141            }
     142        }
     143    }
     144
     145    // initialize the BDD engine ...
     146    Engine engine(variables + vars.size());
     147    mCharacterizationMap.emplace(entry.createZeroes(), BDD::Contradiction());
     148    mCharacterizationMap.emplace(entry.createOnes(), BDD::Tautology());
     149    for (const Var * var : vars) {
     150        mCharacterizationMap.emplace(var, engine.var(variables++));
     151    }
     152    return engine;
     153}
     154
     155/** ------------------------------------------------------------------------------------------------------------- *
     156 * @brief characterize
     157 * @param engine the BDD engine
     158 * @param vars the input vars for this program
     159 *
     160 * Scan through the program and iteratively compute the BDDs for each statement.
     161 ** ------------------------------------------------------------------------------------------------------------- */
     162void AutoMultiplexing::characterize(Engine & engine, const PabloBlock & entry) {
     163
     164    std::vector<std::pair<Advance *, BDD>> advances;
     165    std::stack<const Statement *> scope;
     166
     167    unsigned variables = 0;
     168    unsigned offset = 0;
     169
     170    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
     171    for (const Statement * stmt = entry.front(); ; ) {
     172        for (; stmt; stmt = stmt->getNextNode()) {
     173
     174            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     175                // Set the next statement to be the first statement of the inner scope and push the
     176                // next statement of the current statement into the scope stack.
     177                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     178                scope.push(stmt->getNextNode());
     179                stmt = nested.front();
     180                assert (stmt);
     181                continue;
     182            }
     183
     184            BDD bdd;
     185
     186            // Map our operands to the computed BDDs
     187            std::array<BDD, 3> input;
     188            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     189                PabloAST * const op = stmt->getOperand(i);
     190                if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
     191                    continue;
     192                }
     193                auto f = mCharacterizationMap.find(op);
     194                if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
     195                    throw std::runtime_error("Uncharacterized operand " + std::to_string(i) + " of " + stmt->getName()->to_string());
     196                }
     197                input[i] = f->second;
     198            }
     199
     200            switch (stmt->getClassTypeId()) {
     201                case PabloAST::ClassTypeId::Assign:
     202                    bdd = input[0];
     203                    break;
     204                case PabloAST::ClassTypeId::And:
     205                    bdd = engine.applyAnd(input[0], input[1]);
     206                    if (LLVM_UNLIKELY(mTestForConjunctionContradictions && engine.satOne(bdd).isFalse())) {
     207                        bdd = BDD::Contradiction();
     208                        // Look into making a "replaceAllUsesWithZero" method that can recursively apply
     209                        // the implication of having a Zero output.
     210                        stmt->replaceAllUsesWith(entry.createZeroes());
     211                        stmt->eraseFromParent(true);
     212                    }
     213                    break;
     214                case PabloAST::ClassTypeId::Or:
     215                case PabloAST::ClassTypeId::Next:
     216                    bdd = engine.applyOr(input[0], input[1]);
     217                    break;
     218                case PabloAST::ClassTypeId::Xor:
     219                    bdd = engine.applyXor(input[0], input[1]);
     220                    break;
     221
     222                case PabloAST::ClassTypeId::Not:
     223                    bdd = engine.applyNot(input[0]);
     224                    break;
     225                case PabloAST::ClassTypeId::Sel:
     226                    bdd = engine.applySel(input[0], input[1], input[2]);
     227                    break;
     228                case PabloAST::ClassTypeId::ScanThru:
     229                    // some optimization may be possible use not op2 for scan thrus if we rule out the possibility
     230                    // of a contradition being calculated later.
     231                case PabloAST::ClassTypeId::Call:
     232                case PabloAST::ClassTypeId::MatchStar:
     233                    bdd = engine.var(variables++);
     234                    break;
     235                case PabloAST::ClassTypeId::Advance:
     236                    {
     237                        BDD var = engine.var(variables++);
     238
     239                        bdd = var;
     240
     241                        // when we built the path graph, we constructed it in the same order; hense the row/column of
     242                        // the path graph is equivalent to the index.
     243
     244                        const unsigned k = advances.size();
     245                        const BDD A = input[0];
     246
     247                        for (unsigned i = 0; i != k; ++i) {
     248
     249                            Advance * adv;
     250                            BDD B;
     251                            std::tie(adv, B) = advances[i];
     252
     253                            // Are these two advances advancing their values by the same amount?
     254                            if (stmt->getOperand(1) == adv->getOperand(1)) {
     255                                continue;
     256                            }
     257
     258                            // Are these advances transitively dependant?
     259                            if (edge(offset + i, offset + k, mPathGraph).second) {
     260                                continue;
     261                            }
     262
     263                            const BDD C = engine.applyAnd(A, B); // do we need to simplify this to identify subsets?
     264                            // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
     265                            if (engine.satOne(C).isFalse()) {
     266                                auto f = mCharacterizationMap.find(adv);
     267                                bdd = engine.applyAnd(bdd, engine.applyNot(f->second));
     268                                f->second = engine.applyAnd(f->second, engine.applyNot(var));
     269                            }
     270                            else if (LLVM_UNLIKELY(A == C)) {
     271                                add_edge(k, i, mSubsetGraph);
     272                            }
     273                            else if (LLVM_UNLIKELY(B == C)) {
     274                                add_edge(i, k, mSubsetGraph);
     275                            }
     276                            else {
     277                                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
     278                                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
     279                                add_edge(k > i ? i : k, k > i ? k : i, mConstraintGraph);
     280                            }
     281
     282                            advances.emplace_back(cast<Advance>(stmt), A);
     283                        }
     284                    }
     285                    break;
     286                }
     287                mCharacterizationMap.insert(std::make_pair(stmt, bdd));
     288            }
     289        }
     290        if (scope.empty()) {
     291            break;
     292        }
     293        stmt = scope.top();
     294        scope.pop();
     295    }
     296}
     297
     298/** ------------------------------------------------------------------------------------------------------------- *
     299 * @brief findIndependentSets
     300 * @param bb
     301 * @param tli
     302 ** ------------------------------------------------------------------------------------------------------------- */
     303void AutoMultiplexing::findIndependentSets() {
     304
     305    typedef DependencyGraph::vertex_descriptor                  Vertex;
     306    typedef graph_traits<DependencyGraph>::vertex_iterator      VertexIterator;
     307    typedef graph_traits<DependencyGraph>::out_edge_iterator    EdgeIterator;
     308
     309    // push all source nodes into the active independent set S
     310    Vertices S;
     311    VertexIterator vi, vi_end;
     312    for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
     313        if (in_degree(*vi, G) == 0) {
     314            S.push_back(*vi);
     315        }
     316    }
     317
     318    while (!S.empty()) {
     319        if (S.size() >= 3) {
     320            independentSets.push_back(std::move(Vertices(S)));
     321        }
     322        if (num_edges(G) == 0) {
     323            break;
     324        }
     325        // discard the node of maximum degree from S.
     326        auto max_vi = S.begin();
     327        auto max_timestamp = timestamp[*max_vi];
     328        auto max_degree = out_degree(*max_vi, G);
     329        for (auto vi = max_vi + 1; vi != S.end(); ++vi) {
     330            const auto d = out_degree(*vi, G);
     331            const auto t = timestamp[*vi];
     332             if (max_degree < d || (max_degree == d && max_timestamp < t)) {
     333             // if (max_timestamp < t || (max_timestamp == t && max_degree < d)) {
     334                max_degree = d;
     335                max_timestamp = t;
     336                max_vi = vi;
     337            }
     338        }
     339
     340//        auto max_m = metric[*max_vi];
     341//        for (auto vi = max_vi + 1; vi != S.end(); ++vi) {
     342//            const auto m = metric[*max_vi];
     343//            const auto t = timestamp[*vi];
     344//            if (max_m < m || (max_m == m && max_timestamp < t)) {
     345//                max_m = m;
     346//                max_timestamp = t;
     347//                max_vi = vi;
    148348//            }
    149349//        }
    150350
    151 
    152 }
     351        const unsigned v = *max_vi;
     352        S.erase(max_vi);
     353        EdgeIterator ei, ei_end;
     354        for (std::tie(ei, ei_end) = out_edges(v, G); ei != ei_end; ++ei) {
     355            const Vertex u = target(*ei, G);
     356            if (in_degree(u, G) == 1) {
     357                S.push_back(u);
     358            }
     359        }
     360        clear_out_edges(v, G);
     361    }
     362}
     363
     364
    153365
    154366
     
    158370}
    159371
    160 //struct AdvancedStreamGraph {
    161 
    162 //    struct Vertex;
    163 
    164 //    typedef std::pair<Vertex *, bool>                   Edge;
    165 //    typedef SmallVector<Edge, 1>                        Edges;
    166 //    typedef std::vector<Vertex *>                       Verticies;
    167 //    typedef Verticies::iterator                         iterator;
    168 //    typedef Verticies::const_iterator                   const_iterator;
    169 //    typedef Verticies::size_type                        size_type;
    170 //    typedef PMDSet                                   VariableConstraintNode;
    171 
    172 //    struct Vertex {
    173 //        Vertex(size_type index, const Advance * advance, const VariableConstraintNode * constraints)
    174 //        : _index(index)
    175 //        , _advance(advance)
    176 //        , _constraints(constraints)
    177 //        , _accept(true)
    178 //        {
    179 //        }
    180 
    181 //        inline void setConstraintSet(const VariableConstraintNode * constraints) {
    182 //            assert (!_constraints && constraints);
    183 //            _constraints = constraints;
    184 //        }
    185 
    186 //        inline const VariableConstraintNode * constraintSet() const {
    187 //            return _constraints;
    188 //        }
    189 
    190 //        inline bool hasConstraint(const Vertex * other) const {
    191 //            return VariableConstraintGraph::hasConstraint(constraintSet(), other->constraintSet());
    192 //        }
    193 
    194 //        inline void addPrecessor(Vertex * predecessor, bool negated = false) {
    195 //            assert (predecessor);
    196 //            _dependencies.push_back(std::make_pair(predecessor, negated));
    197 //            predecessor->_accept = false;
    198 //        }
    199 
    200 //        Edges & predecessors() {
    201 //            return _dependencies;
    202 //        }
    203 
    204 //        const Edges & predecessors() const {
    205 //            return _dependencies;
    206 //        }
    207 
    208 //        const Advance * advance() const {
    209 //            return _advance;
    210 //        }
    211 
    212 //        bool accept() const {
    213 //            return _accept;
    214 //        }
    215 
    216 //        size_type index() const {
    217 //            return _index;
    218 //        }
    219 
    220 //        const size_type                 _index;
    221 //        const Advance *                 _advance;
    222 //        const VariableConstraintNode *  _constraints;
    223 //        Edges                           _dependencies;
    224 //        bool                            _accept;
    225 //    };
    226 
    227 //    inline Vertex * add(const Advance * advance, const VariableConstraintNode * constraints) {
    228 //        Vertex * const v = _pool.construct(_verticies.size(), advance, constraints);
    229 //        _map.insert(std::make_pair(advance, v));
    230 //        _verticies.push_back(v);
    231 //        return v;
    232 //    }
    233 
    234 //    inline Vertex * find(const Advance * advance) const {
    235 //        auto itr = _map.find(advance);
    236 //        if (itr == _map.end()) {
    237 //            return nullptr;
    238 //        }
    239 //        return itr->second;
    240 //    }
    241 
    242 //    static inline bool hasConstraint(const Vertex * a, const Vertex * b)  {
    243 //        return VariableConstraintGraph::hasConstraint(a->constraintSet(), b->constraintSet());
    244 //    }
    245 
    246 //    inline static bool hasCharacterClassConstraint(const Edge & a, const Edge & b, const VariableConstraintGraph & U) {
    247 //        if (a.second == b.second) {
    248 //            DenseSet<const Advance *> set;
    249 //            const auto * CCA = a.first->constraintSet();
    250 //            set.insert(CCA->begin(), CCA->end());
    251 //            const auto * CCB = b.first->constraintSet();
    252 //            set.insert(CCB->begin(), CCB->end());
    253 //            if (!a.second) {
    254 //                // Neither predecessor is from a negated advanced stream.
    255 //                //
    256 //                // CC(A) ∩ CC(B) ≠ âˆ
    257  -> ∃a ∈ CC(A) : a ∈ CC(B) ∧ ∃b ∈ CC(B) : b ∈ CC(A) -> |CC(A) ∪ CC(B)| < |CC(A)| + |CC(B)|
    258 //                return set.size() < (CCA->size() + CCB->size());
    259 //            }
    260 //            else { // if (a.second && b.second)
    261 //                // Both predecessors are from negated advanced streams; ergo by De Morgan's law:
    262 //                // _____   _____       _____________
    263 //                // CC(A) ∩ CC(B) ≠ âˆ
    264  â‰¡ CC(A) ∪ CC(B) ≠ âˆ
    265  -> |CC(A) ∪ CC(B)| ≠ |U|
    266 //                return set.size() != U.size();
    267 //            }
    268 //        }
    269 //        else {
    270 //            // One (and only one) of the predecessors is from a negated advanced stream; thus:
    271 //            // _____
    272 //            // CC(A) ∩ CC(B) ≠ âˆ
    273  -> ∄a ∈ CC(A) : a ∈ CC(B)
    274 //            const auto * CCA = a.first->constraintSet();
    275 //            const auto * CCB = b.first->constraintSet();
    276 //            if (b.second) { // if B is the negated class, swap them for simplicity
    277 //                std::swap(CCA, CCB);
    278 //            }
    279 //            for (const Advance * a : *CCA) {
    280 //                if (CCB->count(a)) {
    281 //                    return false;
    282 //                }
    283 //            }
    284 //            return true;
    285 //        }
    286 //    }
    287 
    288 //    iterator begin() {
    289 //        return _verticies.begin();
    290 //    }
    291 
    292 //    iterator end() {
    293 //        return _verticies.end();
    294 //    }
    295 
    296 //    const_iterator begin() const {
    297 //        return _verticies.begin();
    298 //    }
    299 
    300 //    const_iterator end() const {
    301 //        return _verticies.end();
    302 //    }
    303 
    304 //    bool empty() const {
    305 //        return _verticies.empty();
    306 //    }
    307 
    308 //    Verticies::size_type size() const {
    309 //        return _verticies.size();
    310 //    }
    311 
    312 //    inline void clear() {
    313 //        for (Vertex * v : *this) {
    314 //            _pool.destroy(v);
    315 //        }
    316 //        _map.clear();
    317 //        _verticies.clear();
    318 //    }
    319 
    320 //private:
    321 
    322 //    DenseMap<const Advance *, Vertex *>         _map;
    323 //    Verticies                                   _verticies;
    324 //    boost::object_pool<Vertex>                  _pool;
    325 //};
    326 
    327 //typedef AdvancedStreamGraph::Vertex AdvanceNode;
    328 
    329 
    330 ///** ------------------------------------------------------------------------------------------------------------- *
    331 // * @brief initializeSuffixConstraints
    332 // * @param bb
    333 // * @return if any multiplexing opportunities exist
    334 // ** ------------------------------------------------------------------------------------------------------------- */
    335 //bool AutoMultiplexing::initializeSuffixConstraints(PabloBlock & bb) {
    336 
    337 //    AdvancedStreamGraph G;
    338 //    // scan through the graph and compute the advance suffix constraints ...
    339 //    for (PabloAST * inst : bb) {
    340 //        if (Advance * advance = dyn_cast<Advance>(inst)) {
    341 //            VariableConstraintNode * set = _variableConstraints.find(variable);
    342 //            AdvanceNode * node = G.add(&advance, set);
    343 //            // If this is an initial advance, we'll find the set directly; otherwise
    344 //            // we'll have to search for it. Since we cannot be certain that we'll end
    345 //            // up parsing the blocks in sequential order, just buffer them for now.
    346 //            if (set == nullptr) {
    347 //                // first test for the most common case: we're ANDing a previously advanced
    348 //                // stream with some character class.
    349 //                if (variable->getOpcode() == Instruction::And) {
    350 //                    assert (variable->getNumOperands() == 2);
    351 //                    int index = 1;
    352 //                    VariableConstraintNode * set = nullptr;
    353 //                    for (;;) {
    354 //                        set = _variableConstraints.find(dyn_cast<Instruction>(variable->getOperand(index)));
    355 //                        if (set) {
    356 //                            node->setConstraintSet(set);
    357 //                            break;
    358 //                        }
    359 //                        if (index == 0) {
    360 //                            break;
    361 //                        }
    362 //                        --index;
    363 //                    }
    364 
    365 //                    // If we found a character class constraint set for one of the operands; select the other as our preceeding
    366 //                    // (advance) stream; otherwise test to see if the variable is the preceeding stream (i.e., there is no CC)
    367 
    368 //                    Instruction * preceedingStream = set ? dyn_cast<Instruction>(variable->getOperand(1 - index)) : variable;
    369 
    370 //                    // is this a negated stream?
    371 //                    bool negated = false;
    372 //                    while (preceedingStream->getOpcode() == Instruction::Xor) {
    373 //                        assert (preceedingStream->getNumOperands() == 2);
    374 //                        for (unsigned i = 0; i < 2; ++i) {
    375 //                            Value * const operand = preceedingStream->getOperand(i);
    376 //                            if (isa<Constant>(operand) && dyn_cast<Constant>(operand)->isAllOnesValue()) {
    377 //                                negated = !negated;
    378 //                                preceedingStream = dyn_cast<Instruction>(preceedingStream->getOperand(1 - i));
    379 //                            }
    380 //                        }
    381 //                    }
    382 
    383 //                    // If we reach a PHINode, we'll end up handling this through the advance chains anyway. Ignore it.
    384 //                    if (isa<PHINode>(preceedingStream)) {
    385 //                        continue;
    386 //                    }
    387 
    388 //                    // did we find an immediate predecessor?
    389 //                    AdvanceNode * predecessor = G.find(preceedingStream);
    390 
    391 //                    if (predecessor == nullptr && preceedingStream->getOpcode() == Instruction::And) {
    392 //                        assert (preceedingStream->getNumOperands() == 2);
    393 //                        for (unsigned i = 0; i < 2; ++i) {
    394 //                            Instruction * const operand = dyn_cast<Instruction>(preceedingStream->getOperand(i));
    395 //                            if (operand) {
    396 //                                if (operand->getOpcode() == Instruction::Xor) {
    397 //                                    continue;
    398 //                                }
    399 //                                predecessor = G.find(operand);
    400 //                                break;
    401 //                            }
    402 //                        }
    403 //                    }
    404 //                    if (predecessor) {
    405 //                        node->addPrecessor(predecessor, negated);
    406 //                        continue;
    407 //                    }
    408 
    409 //                    // if not, we could be dealing with a series of disjunctions ORing together the results
    410 //                    // of several preceeding streams.
    411 //                    if (preceedingStream->getOpcode() == Instruction::Or) {
    412 //                        std::queue<Instruction *> disjunctions;
    413 //                        Instruction * disjunction = preceedingStream;
    414 //                        bool resolvedAllPredecessors = true;
    415 //                        for (;;) {
    416 //                            assert (disjunction->getNumOperands() == 2);
    417 //                            for (unsigned i = 0; i < 2; ++i) {
    418 //                                Instruction * const operand = dyn_cast<Instruction>(disjunction->getOperand(i));
    419 //                                if (operand && operand->getOpcode() == Instruction::Or) {
    420 //                                    AdvanceNode * predecessor = G.find(operand);
    421 //                                    if (predecessor) {
    422 //                                        node->addPrecessor(predecessor, negated);
    423 //                                    }
    424 //                                    else {
    425 //                                        disjunctions.push(operand);
    426 //                                    }
    427 //                                    continue;
    428 //                                }
    429 //                                resolvedAllPredecessors = false;
    430 //                            }
    431 //                            if (disjunctions.empty()) {
    432 //                                break;
    433 //                            }
    434 //                            disjunction = disjunctions.front();
    435 //                            disjunctions.pop();
    436 //                        }
    437 //                        if (resolvedAllPredecessors) {
    438 //                            continue;
    439 //                        }
    440 //                    }
    441 //                }
    442 //                #ifdef DEBUG_METADATA_ANNOTATIONS
    443 //                advance.setMetadata("unresolved", MDNode::get(bb.getContext(), &advance));
    444 //                #endif
    445 //            }
    446 //        }
    447 //    }
    448 
    449 //    if (G.size() < 3) {
    450 //        return false;
    451 //    }
    452 
    453 //    InstructionVector advances;
    454 //    advances.reserve(G.size());
    455 //    // Generate the initial suffix constraint graph for these advances.
    456 //    for (const AdvanceNode * v : G) {
    457 //        _suffixConstraints.add(v->advance());
    458 //        advances.push_back(const_cast<Instruction *>(v->advance()));
    459 //    }
    460 //    // Compute the dependency constraints for this graph.
    461 //    const auto M = getDependencyMatrixTC<DependencyMatrix>(bb, advances);
    462 //    for (auto i = G.begin(); ++i != G.end(); ) {
    463 //        const AdvanceNode * const a = *i;
    464 //        for (auto j = G.begin(); j != i; ++j) {
    465 //            const AdvanceNode * const b = *j;
    466 //            if (hasSuffixConstraint(a, b, M)) {
    467 //                _suffixConstraints.addConstraint(a->advance(), b->advance());
    468 //            }
    469 //        }
    470 //    }
    471 
    472 //    return true;
    473 //}
    474 
    475 
    476 }
     372
     373}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4536 r4569  
    33
    44#include <pablo/codegenstate.h>
    5 
    6 class bdd::Engine;
     5#include <slab_allocator.h>
     6#include <unordered_map>
     7#include <pablo/analysis/bdd/bdd.hpp>
     8#include <boost/graph/adjacency_list.hpp>
     9#include <boost/graph/adjacency_matrix.hpp>
     10#include <boost/graph/edge_list.hpp>
     11#include <boost/container/flat_map.hpp>
     12#include <boost/numeric/ublas/matrix.hpp>
     13#include <stdint.h>
    714
    815namespace pablo {
    916
    10 class AutoMultiplexing
    11 {
     17class AutoMultiplexing {
     18
     19    using CharacterizationMap = boost::container::flat_map<PabloAST *, bdd::BDD>;
     20    using ConstraintGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::directedS>;
     21    using PathGraph = boost::adjacency_matrix<boost::undirectedS>;
     22    using SubsetGraph = boost::edge_list<std::pair<unsigned, unsigned>>;
     23    using IndexMap = boost::container::flat_map<PabloAST *, unsigned>;
     24
    1225public:
    1326    static void optimize(PabloBlock & block);
    14 
     27protected:
     28    bdd::Engine AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
    1529
    1630
    1731private:
    1832    AutoMultiplexing();
     33
     34    CharacterizationMap     mCharacterizationMap;
     35    PathGraph               mPathGraph;
     36    ConstraintGraph         mConstraintGraph;
     37    SubsetGraph             mSubsetGraph;
     38
     39    bool                    mTestForConjunctionContradictions;
    1940};
    2041
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4510 r4569  
    1212    eliminateRedundantCode(block);
    1313    deadCodeElimination(block);
    14 
     14    eliminateRedundantComplexStatements(block);
    1515    return true;
    1616}
     
    149149        stmt = stmt->getNextNode();
    150150    }
    151 }
    152 
    153 
     151    block.setInsertPoint(block.back());
     152}
     153
     154void Simplifier::eliminateRedundantComplexStatements(PabloBlock & block) {
     155    Statement * stmt = block.front();
     156    while (stmt) {
     157        if (isa<If>(stmt)) {
     158            eliminateRedundantComplexStatements(cast<If>(stmt)->getBody());
     159        }
     160        else if (isa<While>(stmt)) {
     161            eliminateRedundantComplexStatements(cast<While>(stmt)->getBody());
     162        }
     163        else if (stmt->getNumOperands() == 2){
     164            if (isa<Advance>(stmt)) {
     165                // If we're advancing an Advance and the internal Advance does not have any other user,
     166                // we can merge both Advance instructions.
     167                if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(0)))) {
     168                    Advance * op = cast<Advance>(stmt->getOperand(0));
     169                    if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
     170                        Advance * adv = cast<Advance>(stmt);
     171                        adv->setOperand(0, op->getOperand(0));
     172                        adv->setOperand(1, block.getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
     173                        assert(op->getNumUses() == 0);
     174                        op->eraseFromParent();
     175                    }
     176                }
     177            }
     178            // If an AND, OR or XOR instruction has two Advance instructions as inputs and neither Advance
     179            // has another user and both shift their input by the same amount, we can perform the AND, OR
     180            // or XOR on the inputs to the Advances and remove one of the Advance statements.
     181            else if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(1)) && isa<Advance>(stmt->getOperand(0)))) {
     182                Advance * const a0 = cast<Advance>(stmt->getOperand(0));
     183                Advance * const a1 = cast<Advance>(stmt->getOperand(1));
     184                switch (stmt->getClassTypeId()) {
     185                    case PabloAST::ClassTypeId::And:
     186                    case PabloAST::ClassTypeId::Or:
     187                    case PabloAST::ClassTypeId::Xor:
     188                        if (LLVM_UNLIKELY(a0->getNumUses() == 1 && a1->getNumUses() == 1 && a0->getOperand(1) == a1->getOperand(1))) {
     189                            block.setInsertPoint(stmt);
     190                            stmt->setOperand(0, a0->getOperand(0));
     191                            stmt->setOperand(1, a1->getOperand(0));
     192                            a0->insertAfter(stmt);
     193                            a0->setOperand(0, stmt);
     194                            stmt->replaceAllUsesWith(a0);
     195                            assert(a1->getNumUses() == 0);
     196                            a1->eraseFromParent();
     197                            stmt = a0;
     198                    }
     199                    default: break;
     200                }
     201            }
     202            else if (LLVM_UNLIKELY(isa<MatchStar>(stmt->getOperand(1)) && isa<MatchStar>(stmt->getOperand(0))) && isa<Or>(stmt)) {
     203
     204
     205            }
     206        }
     207        stmt = stmt->getNextNode();
     208    }
     209    block.setInsertPoint(block.back());
     210}
    154211
    155212
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4419 r4569  
    1616    static void eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor = nullptr);
    1717    static void deadCodeElimination(PabloBlock & block);
     18    static void eliminateRedundantComplexStatements(PabloBlock & block);
    1819private:
    1920
Note: See TracChangeset for help on using the changeset viewer.