Changeset 4536


Ignore:
Timestamp:
Mar 4, 2015, 4:41:06 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check-in of incomplete multiplexing module.

Location:
icGREP/icgrep-devel/icgrep
Files:
3 added
3 edited

Legend:

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

    r4521 r4536  
    44#include <llvm/ADT/DenseMap.h>
    55#include <llvm/ADT/DenseSet.h>
    6 
     6#include <pablo/analysis/bdd/bdd.hpp>
     7#include <stack>
    78
    89using namespace llvm;
     10using namespace bdd;
    911
    1012namespace pablo {
     
    2426}
    2527
    26 struct AnnotatedStatement {
    27     Statement * mNode;
    28     PabloAST *  mOutput;
    29     bool        mNegated;
    30 };
    31 
    32 void AutoMultiplexing::identifyInputVariables(const PabloBlock & block) {
    33 
    34     for (const Statement * stmt : block) {
    35 
    36 
    37 
    38         if (isa<If>(stmt) || isa<While>(stmt)) {
    39             // Process any statements we found to determine their constraints. Purge the statement list afterwards.
    40 
    41             if (isa<If>(stmt)) {
    42                 identifyInputVariables(cast<If>(stmt)->getBody());
     28void 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
     37    std::stack<const Statement *> scope;
     38    const Statement * stmt = block.front();
     39    while(true) {
     40        for (; stmt; stmt = stmt->getNextNode()) {
     41
     42            if (isa<If>(stmt) || isa<While>(stmt)) {
     43                // Set the next statement to be the first statement of the inner scope and push the
     44                // next statement of the current statement into the scope stack.
     45                PabloBlock & b = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     46                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();
    4356            }
    4457            else {
    45                 identifyInputVariables(cast<While>(stmt)->getBody());
     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                }
    4698            }
    47             continue;
     99
     100            transitoryNodes.insert(std::make_pair(stmt, bdd));
    48101        }
    49 
    50 
    51 
    52         if (isa<Advance>(stmt)) {
    53             // The result of an Advance(expr,n) is the input expr advanced by n.
    54 
     102        if (scope.empty()) {
     103            break;
    55104        }
    56         else if (isa<ScanThru>(stmt)) {
    57             // The result of a ScanThru(from, thru) is anything starting from the "from" and cannot be something in "thru"
    58 
    59         }
    60         else if (isa<MatchStar>(stmt)) {
    61             // The result of a MatchStar(marker, charclass) is anything starting from the "marker" and cannot be something in "charclass"
    62 
    63             // Logically this is similar to ScanThru but only one "marker" can preceed each "charclass" in that case.
    64             // Could we prove whether ScanThru can be used in place of MatchStar and generalize the concept?
    65 
    66 
    67 
    68         }
    69 
    70 
     105        stmt = scope.top();
     106        scope.pop();
    71107    }
     108
     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);
     148//            }
     149//        }
    72150
    73151
     
    80158}
    81159
    82 struct AdvancedStreamGraph {
    83 
    84     struct Vertex;
    85 
    86     typedef std::pair<Vertex *, bool>                   Edge;
    87     typedef SmallVector<Edge, 1>                        Edges;
    88     typedef std::vector<Vertex *>                       Verticies;
    89     typedef Verticies::iterator                         iterator;
    90     typedef Verticies::const_iterator                   const_iterator;
    91     typedef Verticies::size_type                        size_type;
    92     typedef PMDSet                                   VariableConstraintNode;
    93 
    94     struct Vertex {
    95         Vertex(size_type index, const Advance * advance, const VariableConstraintNode * constraints)
    96         : _index(index)
    97         , _advance(advance)
    98         , _constraints(constraints)
    99         , _accept(true)
    100         {
    101         }
    102 
    103         inline void setConstraintSet(const VariableConstraintNode * constraints) {
    104             assert (!_constraints && constraints);
    105             _constraints = constraints;
    106         }
    107 
    108         inline const VariableConstraintNode * constraintSet() const {
    109             return _constraints;
    110         }
    111 
    112         inline bool hasConstraint(const Vertex * other) const {
    113             return VariableConstraintGraph::hasConstraint(constraintSet(), other->constraintSet());
    114         }
    115 
    116         inline void addPrecessor(Vertex * predecessor, bool negated = false) {
    117             assert (predecessor);
    118             _dependencies.push_back(std::make_pair(predecessor, negated));
    119             predecessor->_accept = false;
    120         }
    121 
    122         Edges & predecessors() {
    123             return _dependencies;
    124         }
    125 
    126         const Edges & predecessors() const {
    127             return _dependencies;
    128         }
    129 
    130         const Advance * advance() const {
    131             return _advance;
    132         }
    133 
    134         bool accept() const {
    135             return _accept;
    136         }
    137 
    138         size_type index() const {
    139             return _index;
    140         }
    141 
    142         const size_type                 _index;
    143         const Advance *                 _advance;
    144         const VariableConstraintNode *  _constraints;
    145         Edges                           _dependencies;
    146         bool                            _accept;
    147     };
    148 
    149     inline Vertex * add(const Advance * advance, const VariableConstraintNode * constraints) {
    150         Vertex * const v = _pool.construct(_verticies.size(), advance, constraints);
    151         _map.insert(std::make_pair(advance, v));
    152         _verticies.push_back(v);
    153         return v;
    154     }
    155 
    156     inline Vertex * find(const Advance * advance) const {
    157         auto itr = _map.find(advance);
    158         if (itr == _map.end()) {
    159             return nullptr;
    160         }
    161         return itr->second;
    162     }
    163 
    164     static inline bool hasConstraint(const Vertex * a, const Vertex * b)  {
    165         return VariableConstraintGraph::hasConstraint(a->constraintSet(), b->constraintSet());
    166     }
    167 
    168     inline static bool hasCharacterClassConstraint(const Edge & a, const Edge & b, const VariableConstraintGraph & U) {
    169         if (a.second == b.second) {
    170             DenseSet<const Advance *> set;
    171             const auto * CCA = a.first->constraintSet();
    172             set.insert(CCA->begin(), CCA->end());
    173             const auto * CCB = b.first->constraintSet();
    174             set.insert(CCB->begin(), CCB->end());
    175             if (!a.second) {
    176                 // Neither predecessor is from a negated advanced stream.
    177                 //
    178                 // CC(A) ∩ CC(B) ≠ âˆ
     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) ≠ âˆ
    179257 -> ∃a ∈ CC(A) : a ∈ CC(B) ∧ ∃b ∈ CC(B) : b ∈ CC(A) -> |CC(A) ∪ CC(B)| < |CC(A)| + |CC(B)|
    180                 return set.size() < (CCA->size() + CCB->size());
    181             }
    182             else { // if (a.second && b.second)
    183                 // Both predecessors are from negated advanced streams; ergo by De Morgan's law:
    184                 // _____   _____       _____________
    185                 // 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) ≠ âˆ
    186264 â‰¡ CC(A) ∪ CC(B) ≠ âˆ
    187265 -> |CC(A) ∪ CC(B)| ≠ |U|
    188                 return set.size() != U.size();
    189             }
    190         }
    191         else {
    192             // One (and only one) of the predecessors is from a negated advanced stream; thus:
    193             // _____
    194             // CC(A) ∩ CC(B) ≠ âˆ
     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) ≠ âˆ
    195273 -> ∄a ∈ CC(A) : a ∈ CC(B)
    196             const auto * CCA = a.first->constraintSet();
    197             const auto * CCB = b.first->constraintSet();
    198             if (b.second) { // if B is the negated class, swap them for simplicity
    199                 std::swap(CCA, CCB);
    200             }
    201             for (const Advance * a : *CCA) {
    202                 if (CCB->count(a)) {
    203                     return false;
    204                 }
    205             }
    206             return true;
    207         }
    208     }
    209 
    210     iterator begin() {
    211         return _verticies.begin();
    212     }
    213 
    214     iterator end() {
    215         return _verticies.end();
    216     }
    217 
    218     const_iterator begin() const {
    219         return _verticies.begin();
    220     }
    221 
    222     const_iterator end() const {
    223         return _verticies.end();
    224     }
    225 
    226     bool empty() const {
    227         return _verticies.empty();
    228     }
    229 
    230     Verticies::size_type size() const {
    231         return _verticies.size();
    232     }
    233 
    234     inline void clear() {
    235         for (Vertex * v : *this) {
    236             _pool.destroy(v);
    237         }
    238         _map.clear();
    239         _verticies.clear();
    240     }
    241 
    242 private:
    243 
    244     DenseMap<const Advance *, Vertex *>         _map;
    245     Verticies                                   _verticies;
    246     boost::object_pool<Vertex>                  _pool;
    247 };
    248 
    249 typedef AdvancedStreamGraph::Vertex AdvanceNode;
    250 
    251 
    252 /** ------------------------------------------------------------------------------------------------------------- *
    253  * @brief initializeSuffixConstraints
    254  * @param bb
    255  * @return if any multiplexing opportunities exist
    256  ** ------------------------------------------------------------------------------------------------------------- */
    257 bool AutoMultiplexing::initializeSuffixConstraints(PabloBlock & bb) {
    258 
    259     AdvancedStreamGraph G;
    260     // scan through the graph and compute the advance suffix constraints ...
    261     for (PabloAST * inst : bb) {
    262         if (Advance * advance = dyn_cast<Advance>(inst)) {
    263             VariableConstraintNode * set = _variableConstraints.find(variable);
    264             AdvanceNode * node = G.add(&advance, set);
    265             // If this is an initial advance, we'll find the set directly; otherwise
    266             // we'll have to search for it. Since we cannot be certain that we'll end
    267             // up parsing the blocks in sequential order, just buffer them for now.
    268             if (set == nullptr) {
    269                 // first test for the most common case: we're ANDing a previously advanced
    270                 // stream with some character class.
    271                 if (variable->getOpcode() == Instruction::And) {
    272                     assert (variable->getNumOperands() == 2);
    273                     int index = 1;
    274                     VariableConstraintNode * set = nullptr;
    275                     for (;;) {
    276                         set = _variableConstraints.find(dyn_cast<Instruction>(variable->getOperand(index)));
    277                         if (set) {
    278                             node->setConstraintSet(set);
    279                             break;
    280                         }
    281                         if (index == 0) {
    282                             break;
    283                         }
    284                         --index;
    285                     }
    286 
    287                     // If we found a character class constraint set for one of the operands; select the other as our preceeding
    288                     // (advance) stream; otherwise test to see if the variable is the preceeding stream (i.e., there is no CC)
    289 
    290                     Instruction * preceedingStream = set ? dyn_cast<Instruction>(variable->getOperand(1 - index)) : variable;
    291 
    292                     // is this a negated stream?
    293                     bool negated = false;
    294                     while (preceedingStream->getOpcode() == Instruction::Xor) {
    295                         assert (preceedingStream->getNumOperands() == 2);
    296                         for (unsigned i = 0; i < 2; ++i) {
    297                             Value * const operand = preceedingStream->getOperand(i);
    298                             if (isa<Constant>(operand) && dyn_cast<Constant>(operand)->isAllOnesValue()) {
    299                                 negated = !negated;
    300                                 preceedingStream = dyn_cast<Instruction>(preceedingStream->getOperand(1 - i));
    301                             }
    302                         }
    303                     }
    304 
    305                     // If we reach a PHINode, we'll end up handling this through the advance chains anyway. Ignore it.
    306                     if (isa<PHINode>(preceedingStream)) {
    307                         continue;
    308                     }
    309 
    310                     // did we find an immediate predecessor?
    311                     AdvanceNode * predecessor = G.find(preceedingStream);
    312 
    313                     if (predecessor == nullptr && preceedingStream->getOpcode() == Instruction::And) {
    314                         assert (preceedingStream->getNumOperands() == 2);
    315                         for (unsigned i = 0; i < 2; ++i) {
    316                             Instruction * const operand = dyn_cast<Instruction>(preceedingStream->getOperand(i));
    317                             if (operand) {
    318                                 if (operand->getOpcode() == Instruction::Xor) {
    319                                     continue;
    320                                 }
    321                                 predecessor = G.find(operand);
    322                                 break;
    323                             }
    324                         }
    325                     }
    326                     if (predecessor) {
    327                         node->addPrecessor(predecessor, negated);
    328                         continue;
    329                     }
    330 
    331                     // if not, we could be dealing with a series of disjunctions ORing together the results
    332                     // of several preceeding streams.
    333                     if (preceedingStream->getOpcode() == Instruction::Or) {
    334                         std::queue<Instruction *> disjunctions;
    335                         Instruction * disjunction = preceedingStream;
    336                         bool resolvedAllPredecessors = true;
    337                         for (;;) {
    338                             assert (disjunction->getNumOperands() == 2);
    339                             for (unsigned i = 0; i < 2; ++i) {
    340                                 Instruction * const operand = dyn_cast<Instruction>(disjunction->getOperand(i));
    341                                 if (operand && operand->getOpcode() == Instruction::Or) {
    342                                     AdvanceNode * predecessor = G.find(operand);
    343                                     if (predecessor) {
    344                                         node->addPrecessor(predecessor, negated);
    345                                     }
    346                                     else {
    347                                         disjunctions.push(operand);
    348                                     }
    349                                     continue;
    350                                 }
    351                                 resolvedAllPredecessors = false;
    352                             }
    353                             if (disjunctions.empty()) {
    354                                 break;
    355                             }
    356                             disjunction = disjunctions.front();
    357                             disjunctions.pop();
    358                         }
    359                         if (resolvedAllPredecessors) {
    360                             continue;
    361                         }
    362                     }
    363                 }
    364                 #ifdef DEBUG_METADATA_ANNOTATIONS
    365                 advance.setMetadata("unresolved", MDNode::get(bb.getContext(), &advance));
    366                 #endif
    367             }
    368         }
    369     }
    370 
    371     if (G.size() < 3) {
    372         return false;
    373     }
    374 
    375     InstructionVector advances;
    376     advances.reserve(G.size());
    377     // Generate the initial suffix constraint graph for these advances.
    378     for (const AdvanceNode * v : G) {
    379         _suffixConstraints.add(v->advance());
    380         advances.push_back(const_cast<Instruction *>(v->advance()));
    381     }
    382     // Compute the dependency constraints for this graph.
    383     const auto M = getDependencyMatrixTC<DependencyMatrix>(bb, advances);
    384     for (auto i = G.begin(); ++i != G.end(); ) {
    385         const AdvanceNode * const a = *i;
    386         for (auto j = G.begin(); j != i; ++j) {
    387             const AdvanceNode * const b = *j;
    388             if (hasSuffixConstraint(a, b, M)) {
    389                 _suffixConstraints.addConstraint(a->advance(), b->advance());
    390             }
    391         }
    392     }
    393 
    394     return true;
     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
    395476}
    396 
    397 
    398 }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4242 r4536  
    33
    44#include <pablo/codegenstate.h>
     5
     6class bdd::Engine;
    57
    68namespace pablo {
  • icGREP/icgrep-devel/icgrep/slab_allocator.h

    r4526 r4536  
    44#include <llvm/Support/Allocator.h>
    55
     6using LLVMAllocator = llvm::BumpPtrAllocator;
     7
    68namespace {
    7 
    8 using LLVMAllocator = llvm::BumpPtrAllocator;
    99
    1010class __BumpPtrAllocatorProxy {
     
    5656    }
    5757
    58     inline void deallocate(pointer p, size_type n) noexcept {
     58    inline void deallocate(pointer p, size_type = 0) noexcept {
    5959        mAllocator.Deallocate<T>(p);
    6060    }
     
    8383}
    8484
     85template <typename T>
     86class LLVMAllocatorProxy {
     87public:
     88
     89    using value_type = T;
     90    using pointer = value_type*;
     91    using const_pointer = const value_type*;
     92    using reference = value_type&;
     93    using const_reference = const value_type&;
     94    using size_type = std::size_t;
     95    using difference_type = std::ptrdiff_t;
     96
     97    template<class U>
     98    struct rebind {
     99        typedef SlabAllocator<U> other;
     100    };
     101
     102    inline pointer allocate(size_type n, const_pointer = nullptr) noexcept {
     103        return mAllocator.Allocate<T>(n);
     104    }
     105
     106    inline void deallocate(pointer p, size_type = 0) noexcept {
     107        mAllocator.Deallocate(p);
     108    }
     109
     110    inline size_type max_size() const {
     111        return std::numeric_limits<size_type>::max();
     112    }
     113
     114    inline bool operator==(SlabAllocator<T> const&) { return true; }
     115    inline bool operator!=(SlabAllocator<T> const&) { return false; }
     116
     117    inline LLVMAllocatorProxy(LLVMAllocator & allocator) noexcept : mAllocator(allocator) {}
     118    inline LLVMAllocatorProxy(const LLVMAllocatorProxy & proxy) noexcept : mAllocator(proxy.mAllocator) {}
     119    inline ~LLVMAllocatorProxy() { }
     120private:
     121    LLVMAllocator & mAllocator;
     122};
     123
    85124#endif // SLAB_ALLOCATOR_H
Note: See TracChangeset for help on using the changeset viewer.