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

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

Work on coalescing algorithm + minor changes.

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