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

Last change on this file since 4885 was 4885, checked in by nmedfort, 4 years ago

More work on n-ary operations. Unresolved bug in DistributionPass?.

File size: 12.5 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/optimizers/codemotionpass.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 finalize
23 ** ------------------------------------------------------------------------------------------------------------- */
24inline void FactorizeDFG::finalize(Variadic * const var, PabloBlock * block) {
25    block->setInsertPoint(var->getPrevNode());
26    std::sort(var->begin(), var->end());
27    while (var->getNumOperands() > 2) {
28        PabloAST * const op1 = var->removeOperand(0);
29        PabloAST * const op2 = var->removeOperand(0);
30        PabloAST * newOp = nullptr;
31        if (isa<And>(var)) {
32            newOp = block->createAnd(op1, op2);
33        } else if (isa<Or>(var)) {
34            newOp = block->createOr(op1, op2);
35        } else { // if (isa<Xor>(var)) {
36            newOp = block->createXor(op1, op2);
37        }
38        var->addOperand(newOp);
39    }
40}
41
42/** ------------------------------------------------------------------------------------------------------------- *
43 * @brief finalize
44 ** ------------------------------------------------------------------------------------------------------------- */
45void FactorizeDFG::finalize(PabloBlock * const block) {
46    Statement * stmt = block->front();
47    while (stmt) {
48        if (isa<If>(stmt) || isa<While>(stmt)) {
49            finalize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
50        } else if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
51            finalize(cast<Variadic>(stmt), block);
52        }
53        stmt = stmt->getNextNode();
54    }
55}
56
57/** ------------------------------------------------------------------------------------------------------------- *
58 * @brief enumerateBicliques
59 *
60 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
61 * bicliques" by Alexe et. al. (2003).
62 ** ------------------------------------------------------------------------------------------------------------- */
63static BicliqueSet enumerateBicliques(Variadic * const var) {
64    using IntersectionSets = std::set<VertexSet>;
65
66    IntersectionSets B1;
67
68    const TypeId typeId = var->getClassTypeId();
69    for (unsigned i = 0; i != var->getNumOperands(); ++i) {
70        PabloAST * const op = var->getOperand(i);
71        VertexSet B;
72        B.reserve(op->getNumUsers());
73        for (PabloAST * user : op->users()) {
74            if (user->getClassTypeId() == typeId) {
75                B.push_back(user);
76            }
77        }
78        std::sort(B.begin(), B.end());
79        B1.insert(std::move(B));
80    }
81
82    IntersectionSets B(B1);
83
84    IntersectionSets Bi;
85
86    VertexSet clique;
87    for (auto i = B1.begin(); i != B1.end(); ++i) {
88        for (auto j = i; ++j != B1.end(); ) {
89            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
90            if (clique.size() > 0) {
91                if (B.count(clique) == 0) {
92                    Bi.insert(clique);
93                }
94                clique.clear();
95            }
96        }
97    }
98
99    while (!Bi.empty()) {
100        B.insert(Bi.begin(), Bi.end());
101        IntersectionSets Bk;
102        for (auto i = B1.begin(); i != B1.end(); ++i) {
103            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
104                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
105                if (clique.size() > 0) {
106                    if (B.count(clique) == 0) {
107                        Bk.insert(clique);
108                    }
109                    clique.clear();
110                }
111            }
112        }
113        Bi.swap(Bk);
114    }
115
116    BicliqueSet bicliques;
117    unsigned userSize = 2;
118    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
119        if (userSize <= Bi->size()) {
120            VertexSet Ai(var->begin(), var->end());
121            for (const PabloAST * user : *Bi) {
122                VertexSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
123                std::sort(Aj.begin(), Aj.end());
124                VertexSet Ak;
125                Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
126                std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
127                Ai.swap(Ak);
128            }
129            if (Ai.size() > 1) {
130                if (userSize < Bi->size()) {
131                    bicliques.clear();
132                    userSize = Bi->size();
133                }
134                bicliques.emplace_back(std::move(Ai), std::move(*Bi));
135            }
136        }
137    }
138    return bicliques;
139}
140
141/** ------------------------------------------------------------------------------------------------------------- *
142 * @brief pick
143 ** ------------------------------------------------------------------------------------------------------------- */
144inline static Biclique pick(BicliqueSet && bicliques) {
145    unsigned best_w = 0;
146    auto best_c = bicliques.begin();
147    for (auto c = bicliques.begin(); c != bicliques.end(); ++c) {
148        const unsigned w = std::get<0>(*c).size();
149        if (best_w < w) {
150            best_c = c;
151            best_w = w;
152        }
153    }
154    return std::move(*best_c);
155}
156
157/** ------------------------------------------------------------------------------------------------------------- *
158 * @brief chooseInsertionPoint
159 ** ------------------------------------------------------------------------------------------------------------- */
160inline PabloBlock * FactorizeDFG::chooseInsertionScope(const VertexSet & users) {
161
162    std::vector<PabloBlock *> scopes;
163    scopes.reserve(users.size());
164
165    flat_set<PabloBlock *> visited;
166    visited.reserve(users.size());
167
168    for (PabloAST * user : users) {
169        PabloBlock * const scope = cast<Statement>(user)->getParent();
170        assert (scope);
171        if (visited.insert(scope).second) {
172            scopes.push_back(scope);
173        }
174    }
175
176    while (scopes.size() > 1) {
177        // Find the LCA of both scopes then add the LCA back to the list of scopes.
178        PabloBlock * scope1 = scopes.back(); scopes.pop_back();
179        PabloBlock * scope2 = scopes.back(); scopes.pop_back();
180        if (scope1 != scope2) {
181            unsigned depth1 = mScopeDepth.find(scope1)->second;
182            unsigned depth2 = mScopeDepth.find(scope2)->second;
183            // If one of these scopes is nested deeper than the other, scan upwards through
184            // the scope tree until both scopes are at the same depth.
185            while (depth1 > depth2) {
186                scope1 = scope1->getParent();
187                --depth1;
188            }
189            while (depth1 < depth2) {
190                scope2 = scope2->getParent();
191                --depth2;
192            }
193            // Then iteratively step backwards until we find a matching set of scopes; this
194            // must be the LCA of our original scopes.
195            while (scope1 != scope2) {
196                scope1 = scope1->getParent();
197                scope2 = scope2->getParent();
198            }
199            assert (scope1 && scope2);
200        }
201        scopes.push_back(scope1);
202    }
203    assert (scopes.size() == 1);
204    return scopes[0];
205}
206
207/** ------------------------------------------------------------------------------------------------------------- *
208 * @brief findInsertionPoint
209 ** ------------------------------------------------------------------------------------------------------------- */
210void FactorizeDFG::findInsertionPoint(const VertexSet & operands, PabloBlock * const scope) {
211    const flat_set<const PabloAST *> ops(operands.begin(), operands.end());
212    Statement * stmt = scope->back();
213    scope->setInsertPoint(nullptr);
214    while (stmt) {
215        if (isa<If>(stmt)) {
216            for (Assign * def : cast<If>(stmt)->getDefined()) {
217                if (ops.count(def)) {
218                    scope->setInsertPoint(stmt);
219                    return;
220                }
221            }
222        } else if (isa<While>(stmt)) {
223            for (Next * var : cast<While>(stmt)->getVariants()) {
224                if (ops.count(var)) {
225                    scope->setInsertPoint(stmt);
226                    return;
227                }
228            }
229        } else if (ops.count(stmt)) {
230            scope->setInsertPoint(stmt);
231            break;
232        }
233        stmt = stmt->getPrevNode();
234    }
235}
236
237/** ------------------------------------------------------------------------------------------------------------- *
238 * @brief factorize
239 ** ------------------------------------------------------------------------------------------------------------- */
240inline void FactorizeDFG::factorize(Variadic * var) {
241    while (var->getNumOperands() > 2) {
242        unsigned numOperands = var->getNumOperands();
243        BicliqueSet bicliques = enumerateBicliques(var);
244        if (bicliques.empty()) {
245            break;
246        }
247        VertexSet operands;
248        VertexSet users;
249        std::tie(operands, users) = pick(std::move(bicliques));
250
251        PabloBlock * const block = chooseInsertionScope(users);
252        findInsertionPoint(operands, block);
253        Variadic * factored = nullptr;
254        if (isa<And>(var)) {
255            factored = block->createAnd(operands.begin(), operands.end());
256        } else if (isa<Or>(var)) {
257            factored = block->createOr(operands.begin(), operands.end());
258        } else { // if (isa<Xor>(var)) {
259            factored = block->createXor(operands.begin(), operands.end());
260        }
261        for (PabloAST * user : users) {
262            for (PabloAST * op : operands) {
263                cast<Variadic>(user)->deleteOperand(op);
264            }
265            cast<Variadic>(user)->addOperand(factored);
266        }
267        assert (var->getNumOperands() < numOperands);
268    }
269}
270
271/** ------------------------------------------------------------------------------------------------------------- *
272 * @brief factorize
273 ** ------------------------------------------------------------------------------------------------------------- */
274void FactorizeDFG::factorize(PabloBlock * const block) {
275    Statement * stmt = block->front();
276    while (stmt) {
277        if (isa<If>(stmt) || isa<While>(stmt)) {           
278            factorize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
279        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
280            factorize(cast<Variadic>(stmt));
281        }
282        stmt = stmt->getNextNode();
283    }
284}
285
286/** ------------------------------------------------------------------------------------------------------------- *
287 * @brief initialize
288 ** ------------------------------------------------------------------------------------------------------------- */
289void FactorizeDFG::initialize(const PabloBlock * const block, const unsigned depth) {
290    const Statement * stmt = block->front();
291    while (stmt) {
292        if (isa<If>(stmt) || isa<While>(stmt)) {
293            PabloBlock * body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
294            mScopeDepth.emplace(body, depth);
295            initialize(body, depth + 1);
296        }
297        stmt = stmt->getNextNode();
298    }
299}
300
301/** ------------------------------------------------------------------------------------------------------------- *
302 * @brief initialize
303 ** ------------------------------------------------------------------------------------------------------------- */
304inline void FactorizeDFG::initialize(const PabloFunction & function) {
305    mScopeDepth.emplace(function.getEntryBlock(), 0);
306    initialize(function.getEntryBlock(), 1);
307}
308
309/** ------------------------------------------------------------------------------------------------------------- *
310 * @brief transform
311 ** ------------------------------------------------------------------------------------------------------------- */
312void FactorizeDFG::transform(PabloFunction & function) {
313    FactorizeDFG ldfg;
314    ldfg.initialize(function);
315    ldfg.factorize(function.getEntryBlock());
316    #ifndef NDEBUG
317    PabloVerifier::verify(function, "post-factorize");
318    #endif
319    Simplifier::optimize(function);
320    ldfg.finalize(function.getEntryBlock());
321    #ifndef NDEBUG
322    PabloVerifier::verify(function, "post-finalize");
323    #endif
324}
325
326}
Note: See TracBrowser for help on using the repository browser.