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

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

Continued work on multiplexing pass.

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