source: icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.cpp @ 4899

Last change on this file since 4899 was 4899, checked in by nmedfort, 3 years ago

Work on lowering + minor bug fixes.

File size: 16.4 KB
Line 
1#include "factorizedfg.h"
2
3#include <pablo/codegenstate.h>
4#include <pablo/analysis/pabloverifier.hpp>
5#include <pablo/optimizers/pablo_simplifier.hpp>
6#include <pablo/passes/flattenassociativedfg.h>
7#include <boost/container/flat_set.hpp>
8#include <set>
9
10using namespace boost;
11using namespace boost::container;
12
13
14namespace pablo {
15
16using VertexSet = std::vector<PabloAST *>;
17using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
18using BicliqueSet = std::vector<Biclique>;
19using TypeId = PabloAST::ClassTypeId;
20
21///** ------------------------------------------------------------------------------------------------------------- *
22// * @brief lower
23// ** ------------------------------------------------------------------------------------------------------------- */
24//inline PabloAST * FactorizeDFG::lower(Variadic * const var, PabloBlock * block, OrderingMap & order) {
25//    PabloAST * result = nullptr;
26//    assert (var->getNumOperands() > 2);
27////    // Sort the operands by their order in the current AST
28////    std::sort(var->begin(), var->end(),
29////        [&order](const PabloAST * const a, const PabloAST * const b)
30////    {
31////        return order.of(a) > order.of(b);
32////    });
33////    unsigned operands = var->getNumOperands();
34////    // Swap the final two operands so that we can just append the temporary calculations onto the end
35////    // and trust that the PENULTIMATE operand is the "latest" in the AST.
36////    PabloAST * const item = var->getOperand(operands - 1);
37////    var->setOperand(operands - 1, var->getOperand(operands - 2));
38////    var->setOperand(operands - 2, item);
39//    // Finally rewrite all of the variadic statements as binary operations
40//    block->setInsertPoint(var->getPrevNode());
41//    while (var->getNumOperands() > 1) {
42//        PabloAST * const op2 = var->removeOperand(1);
43//        PabloAST * const op1 = var->removeOperand(0);
44//        assert (op1 != op2);
45//        if (isa<And>(var)) {
46//            result = block->createAnd(op1, op2);
47//        } else if (isa<Or>(var)) {
48//            result = block->createOr(op1, op2);
49//        } else { // if (isa<Xor>(var)) {
50//            result = block->createXor(op1, op2);
51//        }
52//        var->addOperand(result);
53//    }
54//    assert (result);
55//    return result;
56//}
57
58///** ------------------------------------------------------------------------------------------------------------- *
59// * @brief lower
60// ** ------------------------------------------------------------------------------------------------------------- */
61//void FactorizeDFG::lower(PabloBlock * const block, OrderingMap & parent) {
62//    OrderingMap order(parent);
63//    Statement * stmt = block->front();
64//    while (stmt) {
65//        if (isa<If>(stmt) || isa<While>(stmt)) {
66//            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), order);
67//            if (isa<If>(stmt)) {
68//                for (Assign * def : cast<If>(stmt)->getDefined()) {
69//                    order.enumerate(def);
70//                }
71//            } else { // if (isa<While>(stmt)) {
72//                for (Next * var : cast<While>(stmt)->getVariants()) {
73//                    order.enumerate(var);
74//                }
75//            }
76//        } else {
77//            if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
78//                // We should maintain an ordering list and sort each Variadic according to it prior to writing them out.
79//                PabloAST * result = lower(cast<Variadic>(stmt), block, order);
80//                order.enumerate(result);
81//                stmt = stmt->replaceWith(result, true);
82//                continue;
83//            }
84//            order.enumerate(stmt);
85//        }
86//        stmt = stmt->getNextNode();
87//    }
88//}
89
90/** ------------------------------------------------------------------------------------------------------------- *
91 * @brief finalize
92 ** ------------------------------------------------------------------------------------------------------------- */
93inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) {
94    PabloAST * result = nullptr;
95    assert (var->getNumOperands() > 2);
96    block->setInsertPoint(var->getPrevNode());
97    while (var->getNumOperands() > 1) {
98        PabloAST * const op2 = var->removeOperand(1);
99        PabloAST * const op1 = var->removeOperand(0);
100        assert (op1 != op2);
101        if (isa<And>(var)) {
102            result = block->createAnd(op1, op2);
103        } else if (isa<Or>(var)) {
104            result = block->createOr(op1, op2);
105        } else { // if (isa<Xor>(var)) {
106            result = block->createXor(op1, op2);
107        }
108        var->addOperand(result);
109    }
110    return var->replaceWith(result, true);
111}
112
113/** ------------------------------------------------------------------------------------------------------------- *
114 * @brief finalize
115 ** ------------------------------------------------------------------------------------------------------------- */
116void FactorizeDFG::lower(PabloBlock * const block) {
117    Statement * stmt = block->front();
118    while (stmt) {
119        if (isa<If>(stmt) || isa<While>(stmt)) {
120            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
121        } else if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
122            // We should maintain an ordering list and sort each Variadic according to it prior to writing them out.
123            stmt = lower(cast<Variadic>(stmt), block);
124            continue;
125        }
126        stmt = stmt->getNextNode();
127    }
128}
129
130///** ------------------------------------------------------------------------------------------------------------- *
131// * @brief lower
132// ** ------------------------------------------------------------------------------------------------------------- */
133//inline void FactorizeDFG::lower(PabloFunction & function) {
134//    OrderingMap ordering;
135//    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
136//        ordering.enumerate(function.getParameter(i));
137//    }
138//    lower(function.getEntryBlock(), ordering);
139//}
140
141/** ------------------------------------------------------------------------------------------------------------- *
142 * @brief enumerateBicliques
143 *
144 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
145 * bicliques" by Alexe et. al. (2003).
146 ** ------------------------------------------------------------------------------------------------------------- */
147static BicliqueSet enumerateBicliques(Variadic * const var) {
148    using IntersectionSets = std::set<VertexSet>;
149
150    IntersectionSets B1;
151
152    const TypeId typeId = var->getClassTypeId();
153    for (unsigned i = 0; i != var->getNumOperands(); ++i) {
154        PabloAST * const op = var->getOperand(i);
155        VertexSet B;
156        B.reserve(op->getNumUses());
157        for (PabloAST * user : op->users()) {
158            if (user->getClassTypeId() == typeId) {
159                B.push_back(user);
160            }
161        }
162        std::sort(B.begin(), B.end());
163        B1.insert(std::move(B));
164    }
165
166    IntersectionSets B(B1);
167
168    IntersectionSets Bi;
169
170    VertexSet clique;
171    for (auto i = B1.begin(); i != B1.end(); ++i) {
172        for (auto j = i; ++j != B1.end(); ) {
173            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
174            if (clique.size() > 0) {
175                if (B.count(clique) == 0) {
176                    Bi.insert(clique);
177                }
178                clique.clear();
179            }
180        }
181    }
182
183    while (!Bi.empty()) {
184        B.insert(Bi.begin(), Bi.end());
185        IntersectionSets Bk;
186        for (auto i = B1.begin(); i != B1.end(); ++i) {
187            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
188                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
189                if (clique.size() > 0) {
190                    if (B.count(clique) == 0) {
191                        Bk.insert(clique);
192                    }
193                    clique.clear();
194                }
195            }
196        }
197        Bi.swap(Bk);
198    }
199
200    BicliqueSet bicliques;
201    unsigned userSize = 2;
202    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
203        if (userSize <= Bi->size()) {
204            VertexSet Ai(var->begin(), var->end());
205            for (const PabloAST * user : *Bi) {
206                VertexSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
207                std::sort(Aj.begin(), Aj.end());
208                VertexSet Ak;
209                Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
210                std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
211                Ai.swap(Ak);
212            }
213            if (Ai.size() > 1) {
214                if (userSize < Bi->size()) {
215                    bicliques.clear();
216                    userSize = Bi->size();
217                }
218                bicliques.emplace_back(std::move(Ai), std::move(*Bi));
219            }
220        }
221    }
222    return bicliques;
223}
224
225/** ------------------------------------------------------------------------------------------------------------- *
226 * @brief pick
227 ** ------------------------------------------------------------------------------------------------------------- */
228inline static Biclique pick(BicliqueSet && bicliques) {
229    unsigned best_w = 0;
230    auto best_c = bicliques.begin();
231    for (auto c = bicliques.begin(); c != bicliques.end(); ++c) {
232        const unsigned w = std::get<0>(*c).size();
233        if (best_w < w) {
234            best_c = c;
235            best_w = w;
236        }
237    }
238    return std::move(*best_c);
239}
240
241/** ------------------------------------------------------------------------------------------------------------- *
242 * @brief chooseInsertionPoint
243 ** ------------------------------------------------------------------------------------------------------------- */
244inline PabloBlock * FactorizeDFG::chooseInsertionScope(const ASTVector & users) {
245
246    ScopeSet scopes;
247    scopes.reserve(users.size());
248
249    flat_set<PabloBlock *> visited;
250    visited.reserve(users.size());
251
252    for (PabloAST * user : users) {
253        PabloBlock * const scope = cast<Statement>(user)->getParent();
254        assert (scope);
255        if (visited.insert(scope).second) {
256            scopes.push_back(scope);
257        }
258    }
259
260    while (scopes.size() > 1) {
261        // Find the LCA of both scopes then add the LCA back to the list of scopes.
262        PabloBlock * scope1 = scopes.back(); scopes.pop_back();
263        PabloBlock * scope2 = scopes.back(); scopes.pop_back();
264        if (scope1 != scope2) {
265            unsigned depth1 = mScopeDepth.find(scope1)->second;
266            unsigned depth2 = mScopeDepth.find(scope2)->second;
267            // If one of these scopes is nested deeper than the other, scan upwards through
268            // the scope tree until both scopes are at the same depth.
269            while (depth1 > depth2) {
270                scope1 = scope1->getParent();
271                --depth1;
272            }
273            while (depth1 < depth2) {
274                scope2 = scope2->getParent();
275                --depth2;
276            }
277            // Then iteratively step backwards until we find a matching set of scopes; this
278            // must be the LCA of our original scopes.
279            while (scope1 != scope2) {
280                scope1 = scope1->getParent();
281                scope2 = scope2->getParent();
282            }
283            assert (scope1 && scope2);
284        }
285        scopes.push_back(scope1);
286    }
287    assert (scopes.size() == 1);
288    return scopes[0];
289}
290
291/** ------------------------------------------------------------------------------------------------------------- *
292 * @brief findInsertionPoint
293 ** ------------------------------------------------------------------------------------------------------------- */
294void FactorizeDFG::findInsertionPoint(const ASTVector & operands, PabloBlock * const scope) {
295    const flat_set<const PabloAST *> ops(operands.begin(), operands.end());
296    Statement * stmt = scope->back();
297    scope->setInsertPoint(nullptr);
298    while (stmt) {
299        if (isa<If>(stmt)) {
300            for (Assign * def : cast<If>(stmt)->getDefined()) {
301                if (ops.count(def)) {
302                    scope->setInsertPoint(stmt);
303                    return;
304                }
305            }
306        } else if (isa<While>(stmt)) {
307            for (Next * var : cast<While>(stmt)->getVariants()) {
308                if (ops.count(var)) {
309                    scope->setInsertPoint(stmt);
310                    return;
311                }
312            }
313        } else if (ops.count(stmt)) {
314            scope->setInsertPoint(stmt);
315            break;
316        }
317        stmt = stmt->getPrevNode();
318    }
319}
320
321/** ------------------------------------------------------------------------------------------------------------- *
322 * @brief cse
323 ** ------------------------------------------------------------------------------------------------------------- */
324inline void FactorizeDFG::cse(Variadic * var) {
325    while (var->getNumOperands() > 2) {
326        BicliqueSet bicliques = enumerateBicliques(var);
327        if (bicliques.empty()) {
328            break;
329        }
330        ASTVector operands;
331        ASTVector users;
332        std::tie(operands, users) = pick(std::move(bicliques));
333        PabloBlock * const block = chooseInsertionScope(users);
334        findInsertionPoint(operands, block);
335        Variadic * factored = nullptr;
336        if (isa<And>(var)) {
337            factored = block->createAnd(operands.begin(), operands.end());
338        } else if (isa<Or>(var)) {
339            factored = block->createOr(operands.begin(), operands.end());
340        } else { // if (isa<Xor>(var)) {
341            factored = block->createXor(operands.begin(), operands.end());
342        }
343        for (PabloAST * user : users) {
344            for (PabloAST * op : operands) {
345                cast<Variadic>(user)->deleteOperand(op);
346            }
347            cast<Variadic>(user)->addOperand(factored);
348        }
349    }
350}
351
352/** ------------------------------------------------------------------------------------------------------------- *
353 * @brief cse
354 *
355 * Perform common subexpression elimination on the Variadic statements
356 ** ------------------------------------------------------------------------------------------------------------- */
357void FactorizeDFG::cse(PabloBlock * const block) {
358    Statement * stmt = block->front();
359    while (stmt) {
360        if (isa<If>(stmt) || isa<While>(stmt)) {           
361            cse(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
362        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
363            cse(cast<Variadic>(stmt));
364        }
365        stmt = stmt->getNextNode();
366    }
367}
368
369/** ------------------------------------------------------------------------------------------------------------- *
370 * @brief enumerateScopeDepth
371 ** ------------------------------------------------------------------------------------------------------------- */
372void FactorizeDFG::enumerateScopeDepth(const PabloBlock * const block, const unsigned depth) {
373    const Statement * stmt = block->front();
374    while (stmt) {
375        if (isa<If>(stmt) || isa<While>(stmt)) {
376            PabloBlock * body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
377            mScopeDepth.emplace(body, depth);
378            enumerateScopeDepth(body, depth + 1);
379        }
380        stmt = stmt->getNextNode();
381    }
382}
383
384/** ------------------------------------------------------------------------------------------------------------- *
385 * @brief enumerateScopeDepth
386 ** ------------------------------------------------------------------------------------------------------------- */
387inline void FactorizeDFG::enumerateScopeDepth(const PabloFunction & function) {
388    mScopeDepth.emplace(function.getEntryBlock(), 0);
389    enumerateScopeDepth(function.getEntryBlock(), 1);
390}
391
392/** ------------------------------------------------------------------------------------------------------------- *
393 * @brief transform
394 ** ------------------------------------------------------------------------------------------------------------- */
395void FactorizeDFG::transform(PabloFunction & function) {
396    FactorizeDFG ldfg;
397    ldfg.enumerateScopeDepth(function);
398    ldfg.cse(function.getEntryBlock());
399    #ifndef NDEBUG
400    PabloVerifier::verify(function, "post-cse");
401    #endif
402    Simplifier::optimize(function);
403    ldfg.lower(function.getEntryBlock());
404    #ifndef NDEBUG
405    PabloVerifier::verify(function, "post-lowering");
406    #endif   
407}
408
409}
Note: See TracBrowser for help on using the repository browser.