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

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

added code sinking module; disabled by default as it hurts performance unless if-insertions occur.

File size: 14.0 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
7
8using namespace llvm;
9
10namespace pablo {
11
12static void AutoMultiplexing::optimize(PabloBlock & block) {
13    // indentifyInputVariables
14
15
16    // generateVariableConstraints
17
18
19
20    // identifySuffixConstraints
21
22
23
24}
25
26struct AnnotatedStatement {
27    Statement * mNode;
28    PabloAST *  mOutput;
29    bool        mNegated;
30};
31
32void 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());
43            }
44            else {
45                identifyInputVariables(cast<While>(stmt)->getBody());
46            }
47            continue;
48        }
49
50
51
52        if (isa<Advance>(stmt)) {
53            // The result of an Advance(expr,n) is the input expr advanced by n.
54
55        }
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
71    }
72
73
74}
75
76
77AutoMultiplexing::AutoMultiplexing()
78{
79
80}
81
82struct 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) ≠ ∅ -> ∃a ∈ CC(A) : a ∈ CC(B) ∧ ∃b ∈ CC(B) : b ∈ CC(A) -> |CC(A) ∪ CC(B)| < |CC(A)| + |CC(B)|
179                return set.size() < (CCA->size() + CCB->size());
180            }
181            else { // if (a.second && b.second)
182                // Both predecessors are from negated advanced streams; ergo by De Morgan's law:
183                // _____   _____       _____________
184                // CC(A) ∩ CC(B) ≠ ∅ ≡ CC(A) ∪ CC(B) ≠ ∅ -> |CC(A) ∪ CC(B)| ≠ |U|
185                return set.size() != U.size();
186            }
187        }
188        else {
189            // One (and only one) of the predecessors is from a negated advanced stream; thus:
190            // _____
191            // CC(A) ∩ CC(B) ≠ ∅ -> ∄a ∈ CC(A) : a ∈ CC(B)
192            const auto * CCA = a.first->constraintSet();
193            const auto * CCB = b.first->constraintSet();
194            if (b.second) { // if B is the negated class, swap them for simplicity
195                std::swap(CCA, CCB);
196            }
197            for (const Advance * a : *CCA) {
198                if (CCB->count(a)) {
199                    return false;
200                }
201            }
202            return true;
203        }
204    }
205
206    iterator begin() {
207        return _verticies.begin();
208    }
209
210    iterator end() {
211        return _verticies.end();
212    }
213
214    const_iterator begin() const {
215        return _verticies.begin();
216    }
217
218    const_iterator end() const {
219        return _verticies.end();
220    }
221
222    bool empty() const {
223        return _verticies.empty();
224    }
225
226    Verticies::size_type size() const {
227        return _verticies.size();
228    }
229
230    inline void clear() {
231        for (Vertex * v : *this) {
232            _pool.destroy(v);
233        }
234        _map.clear();
235        _verticies.clear();
236    }
237
238private:
239
240    DenseMap<const Advance *, Vertex *>         _map;
241    Verticies                                   _verticies;
242    boost::object_pool<Vertex>                  _pool;
243};
244
245typedef AdvancedStreamGraph::Vertex AdvanceNode;
246
247
248/** ------------------------------------------------------------------------------------------------------------- *
249 * @brief initializeSuffixConstraints
250 * @param bb
251 * @return if any multiplexing opportunities exist
252 ** ------------------------------------------------------------------------------------------------------------- */
253bool AutoMultiplexing::initializeSuffixConstraints(PabloBlock & bb) {
254
255    AdvancedStreamGraph G;
256    // scan through the graph and compute the advance suffix constraints ...
257    for (PabloAST * inst : bb) {
258        if (Advance * advance = dyn_cast<Advance>(inst)) {
259            VariableConstraintNode * set = _variableConstraints.find(variable);
260            AdvanceNode * node = G.add(&advance, set);
261            // If this is an initial advance, we'll find the set directly; otherwise
262            // we'll have to search for it. Since we cannot be certain that we'll end
263            // up parsing the blocks in sequential order, just buffer them for now.
264            if (set == nullptr) {
265                // first test for the most common case: we're ANDing a previously advanced
266                // stream with some character class.
267                if (variable->getOpcode() == Instruction::And) {
268                    assert (variable->getNumOperands() == 2);
269                    int index = 1;
270                    VariableConstraintNode * set = nullptr;
271                    for (;;) {
272                        set = _variableConstraints.find(dyn_cast<Instruction>(variable->getOperand(index)));
273                        if (set) {
274                            node->setConstraintSet(set);
275                            break;
276                        }
277                        if (index == 0) {
278                            break;
279                        }
280                        --index;
281                    }
282
283                    // If we found a character class constraint set for one of the operands; select the other as our preceeding
284                    // (advance) stream; otherwise test to see if the variable is the preceeding stream (i.e., there is no CC)
285
286                    Instruction * preceedingStream = set ? dyn_cast<Instruction>(variable->getOperand(1 - index)) : variable;
287
288                    // is this a negated stream?
289                    bool negated = false;
290                    while (preceedingStream->getOpcode() == Instruction::Xor) {
291                        assert (preceedingStream->getNumOperands() == 2);
292                        for (unsigned i = 0; i < 2; ++i) {
293                            Value * const operand = preceedingStream->getOperand(i);
294                            if (isa<Constant>(operand) && dyn_cast<Constant>(operand)->isAllOnesValue()) {
295                                negated = !negated;
296                                preceedingStream = dyn_cast<Instruction>(preceedingStream->getOperand(1 - i));
297                            }
298                        }
299                    }
300
301                    // If we reach a PHINode, we'll end up handling this through the advance chains anyway. Ignore it.
302                    if (isa<PHINode>(preceedingStream)) {
303                        continue;
304                    }
305
306                    // did we find an immediate predecessor?
307                    AdvanceNode * predecessor = G.find(preceedingStream);
308
309                    if (predecessor == nullptr && preceedingStream->getOpcode() == Instruction::And) {
310                        assert (preceedingStream->getNumOperands() == 2);
311                        for (unsigned i = 0; i < 2; ++i) {
312                            Instruction * const operand = dyn_cast<Instruction>(preceedingStream->getOperand(i));
313                            if (operand) {
314                                if (operand->getOpcode() == Instruction::Xor) {
315                                    continue;
316                                }
317                                predecessor = G.find(operand);
318                                break;
319                            }
320                        }
321                    }
322                    if (predecessor) {
323                        node->addPrecessor(predecessor, negated);
324                        continue;
325                    }
326
327                    // if not, we could be dealing with a series of disjunctions ORing together the results
328                    // of several preceeding streams.
329                    if (preceedingStream->getOpcode() == Instruction::Or) {
330                        std::queue<Instruction *> disjunctions;
331                        Instruction * disjunction = preceedingStream;
332                        bool resolvedAllPredecessors = true;
333                        for (;;) {
334                            assert (disjunction->getNumOperands() == 2);
335                            for (unsigned i = 0; i < 2; ++i) {
336                                Instruction * const operand = dyn_cast<Instruction>(disjunction->getOperand(i));
337                                if (operand && operand->getOpcode() == Instruction::Or) {
338                                    AdvanceNode * predecessor = G.find(operand);
339                                    if (predecessor) {
340                                        node->addPrecessor(predecessor, negated);
341                                    }
342                                    else {
343                                        disjunctions.push(operand);
344                                    }
345                                    continue;
346                                }
347                                resolvedAllPredecessors = false;
348                            }
349                            if (disjunctions.empty()) {
350                                break;
351                            }
352                            disjunction = disjunctions.front();
353                            disjunctions.pop();
354                        }
355                        if (resolvedAllPredecessors) {
356                            continue;
357                        }
358                    }
359                }
360                #ifdef DEBUG_METADATA_ANNOTATIONS
361                advance.setMetadata("unresolved", MDNode::get(bb.getContext(), &advance));
362                #endif
363            }
364        }
365    }
366
367    if (G.size() < 3) {
368        return false;
369    }
370
371    InstructionVector advances;
372    advances.reserve(G.size());
373    // Generate the initial suffix constraint graph for these advances.
374    for (const AdvanceNode * v : G) {
375        _suffixConstraints.add(v->advance());
376        advances.push_back(const_cast<Instruction *>(v->advance()));
377    }
378    // Compute the dependency constraints for this graph.
379    const auto M = getDependencyMatrixTC<DependencyMatrix>(bb, advances);
380    for (auto i = G.begin(); ++i != G.end(); ) {
381        const AdvanceNode * const a = *i;
382        for (auto j = G.begin(); j != i; ++j) {
383            const AdvanceNode * const b = *j;
384            if (hasSuffixConstraint(a, b, M)) {
385                _suffixConstraints.addConstraint(a->advance(), b->advance());
386            }
387        }
388    }
389
390    return true;
391}
392
393
394}
Note: See TracBrowser for help on using the repository browser.