source: icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp @ 4536

Last change on this file since 4536 was 4536, checked in by nmedfort, 5 years ago

Temporary check-in of incomplete multiplexing module.

File size: 17.9 KB
Line 
1#include "pablo_automultiplexing.hpp"
2#include <pablo/codegenstate.h>
3#include <llvm/ADT/SmallVector.h>
4#include <llvm/ADT/DenseMap.h>
5#include <llvm/ADT/DenseSet.h>
6#include <pablo/analysis/bdd/bdd.hpp>
7#include <stack>
8
9using namespace llvm;
10using namespace bdd;
11
12namespace pablo {
13
14static void AutoMultiplexing::optimize(PabloBlock & block) {
15    // indentifyInputVariables
16
17
18    // generateVariableConstraints
19
20
21
22    // identifySuffixConstraints
23
24
25
26}
27
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();
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));
101        }
102        if (scope.empty()) {
103            break;
104        }
105        stmt = scope.top();
106        scope.pop();
107    }
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//        }
150
151
152}
153
154
155AutoMultiplexing::AutoMultiplexing()
156{
157
158}
159
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) ≠ ∅ -> ∃a ∈ CC(A) : a ∈ CC(B) ∧ ∃b ∈ CC(B) : b ∈ CC(A) -> |CC(A) ∪ CC(B)| < |CC(A)| + |CC(B)|
257//                return set.size() < (CCA->size() + CCB->size());
258//            }
259//            else { // if (a.second && b.second)
260//                // Both predecessors are from negated advanced streams; ergo by De Morgan's law:
261//                // _____   _____       _____________
262//                // CC(A) ∩ CC(B) ≠ ∅ ≡ CC(A) ∪ CC(B) ≠ ∅ -> |CC(A) ∪ CC(B)| ≠ |U|
263//                return set.size() != U.size();
264//            }
265//        }
266//        else {
267//            // One (and only one) of the predecessors is from a negated advanced stream; thus:
268//            // _____
269//            // CC(A) ∩ CC(B) ≠ ∅ -> ∄a ∈ CC(A) : a ∈ CC(B)
270//            const auto * CCA = a.first->constraintSet();
271//            const auto * CCB = b.first->constraintSet();
272//            if (b.second) { // if B is the negated class, swap them for simplicity
273//                std::swap(CCA, CCB);
274//            }
275//            for (const Advance * a : *CCA) {
276//                if (CCB->count(a)) {
277//                    return false;
278//                }
279//            }
280//            return true;
281//        }
282//    }
283
284//    iterator begin() {
285//        return _verticies.begin();
286//    }
287
288//    iterator end() {
289//        return _verticies.end();
290//    }
291
292//    const_iterator begin() const {
293//        return _verticies.begin();
294//    }
295
296//    const_iterator end() const {
297//        return _verticies.end();
298//    }
299
300//    bool empty() const {
301//        return _verticies.empty();
302//    }
303
304//    Verticies::size_type size() const {
305//        return _verticies.size();
306//    }
307
308//    inline void clear() {
309//        for (Vertex * v : *this) {
310//            _pool.destroy(v);
311//        }
312//        _map.clear();
313//        _verticies.clear();
314//    }
315
316//private:
317
318//    DenseMap<const Advance *, Vertex *>         _map;
319//    Verticies                                   _verticies;
320//    boost::object_pool<Vertex>                  _pool;
321//};
322
323//typedef AdvancedStreamGraph::Vertex AdvanceNode;
324
325
326///** ------------------------------------------------------------------------------------------------------------- *
327// * @brief initializeSuffixConstraints
328// * @param bb
329// * @return if any multiplexing opportunities exist
330// ** ------------------------------------------------------------------------------------------------------------- */
331//bool AutoMultiplexing::initializeSuffixConstraints(PabloBlock & bb) {
332
333//    AdvancedStreamGraph G;
334//    // scan through the graph and compute the advance suffix constraints ...
335//    for (PabloAST * inst : bb) {
336//        if (Advance * advance = dyn_cast<Advance>(inst)) {
337//            VariableConstraintNode * set = _variableConstraints.find(variable);
338//            AdvanceNode * node = G.add(&advance, set);
339//            // If this is an initial advance, we'll find the set directly; otherwise
340//            // we'll have to search for it. Since we cannot be certain that we'll end
341//            // up parsing the blocks in sequential order, just buffer them for now.
342//            if (set == nullptr) {
343//                // first test for the most common case: we're ANDing a previously advanced
344//                // stream with some character class.
345//                if (variable->getOpcode() == Instruction::And) {
346//                    assert (variable->getNumOperands() == 2);
347//                    int index = 1;
348//                    VariableConstraintNode * set = nullptr;
349//                    for (;;) {
350//                        set = _variableConstraints.find(dyn_cast<Instruction>(variable->getOperand(index)));
351//                        if (set) {
352//                            node->setConstraintSet(set);
353//                            break;
354//                        }
355//                        if (index == 0) {
356//                            break;
357//                        }
358//                        --index;
359//                    }
360
361//                    // If we found a character class constraint set for one of the operands; select the other as our preceeding
362//                    // (advance) stream; otherwise test to see if the variable is the preceeding stream (i.e., there is no CC)
363
364//                    Instruction * preceedingStream = set ? dyn_cast<Instruction>(variable->getOperand(1 - index)) : variable;
365
366//                    // is this a negated stream?
367//                    bool negated = false;
368//                    while (preceedingStream->getOpcode() == Instruction::Xor) {
369//                        assert (preceedingStream->getNumOperands() == 2);
370//                        for (unsigned i = 0; i < 2; ++i) {
371//                            Value * const operand = preceedingStream->getOperand(i);
372//                            if (isa<Constant>(operand) && dyn_cast<Constant>(operand)->isAllOnesValue()) {
373//                                negated = !negated;
374//                                preceedingStream = dyn_cast<Instruction>(preceedingStream->getOperand(1 - i));
375//                            }
376//                        }
377//                    }
378
379//                    // If we reach a PHINode, we'll end up handling this through the advance chains anyway. Ignore it.
380//                    if (isa<PHINode>(preceedingStream)) {
381//                        continue;
382//                    }
383
384//                    // did we find an immediate predecessor?
385//                    AdvanceNode * predecessor = G.find(preceedingStream);
386
387//                    if (predecessor == nullptr && preceedingStream->getOpcode() == Instruction::And) {
388//                        assert (preceedingStream->getNumOperands() == 2);
389//                        for (unsigned i = 0; i < 2; ++i) {
390//                            Instruction * const operand = dyn_cast<Instruction>(preceedingStream->getOperand(i));
391//                            if (operand) {
392//                                if (operand->getOpcode() == Instruction::Xor) {
393//                                    continue;
394//                                }
395//                                predecessor = G.find(operand);
396//                                break;
397//                            }
398//                        }
399//                    }
400//                    if (predecessor) {
401//                        node->addPrecessor(predecessor, negated);
402//                        continue;
403//                    }
404
405//                    // if not, we could be dealing with a series of disjunctions ORing together the results
406//                    // of several preceeding streams.
407//                    if (preceedingStream->getOpcode() == Instruction::Or) {
408//                        std::queue<Instruction *> disjunctions;
409//                        Instruction * disjunction = preceedingStream;
410//                        bool resolvedAllPredecessors = true;
411//                        for (;;) {
412//                            assert (disjunction->getNumOperands() == 2);
413//                            for (unsigned i = 0; i < 2; ++i) {
414//                                Instruction * const operand = dyn_cast<Instruction>(disjunction->getOperand(i));
415//                                if (operand && operand->getOpcode() == Instruction::Or) {
416//                                    AdvanceNode * predecessor = G.find(operand);
417//                                    if (predecessor) {
418//                                        node->addPrecessor(predecessor, negated);
419//                                    }
420//                                    else {
421//                                        disjunctions.push(operand);
422//                                    }
423//                                    continue;
424//                                }
425//                                resolvedAllPredecessors = false;
426//                            }
427//                            if (disjunctions.empty()) {
428//                                break;
429//                            }
430//                            disjunction = disjunctions.front();
431//                            disjunctions.pop();
432//                        }
433//                        if (resolvedAllPredecessors) {
434//                            continue;
435//                        }
436//                    }
437//                }
438//                #ifdef DEBUG_METADATA_ANNOTATIONS
439//                advance.setMetadata("unresolved", MDNode::get(bb.getContext(), &advance));
440//                #endif
441//            }
442//        }
443//    }
444
445//    if (G.size() < 3) {
446//        return false;
447//    }
448
449//    InstructionVector advances;
450//    advances.reserve(G.size());
451//    // Generate the initial suffix constraint graph for these advances.
452//    for (const AdvanceNode * v : G) {
453//        _suffixConstraints.add(v->advance());
454//        advances.push_back(const_cast<Instruction *>(v->advance()));
455//    }
456//    // Compute the dependency constraints for this graph.
457//    const auto M = getDependencyMatrixTC<DependencyMatrix>(bb, advances);
458//    for (auto i = G.begin(); ++i != G.end(); ) {
459//        const AdvanceNode * const a = *i;
460//        for (auto j = G.begin(); j != i; ++j) {
461//            const AdvanceNode * const b = *j;
462//            if (hasSuffixConstraint(a, b, M)) {
463//                _suffixConstraints.addConstraint(a->advance(), b->advance());
464//            }
465//        }
466//    }
467
468//    return true;
469//}
470
471
472}
Note: See TracBrowser for help on using the repository browser.