source: icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp @ 4919

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

Work on lowering + some timing and papi information that will be cleaned up later.

File size: 15.8 KB
Line 
1#include "distributivepass.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 <boost/container/flat_map.hpp>
9#include <boost/graph/adjacency_list.hpp>
10
11using namespace boost;
12using namespace boost::container;
13
14namespace pablo {
15
16using DependencyGraph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
17using Vertex = DependencyGraph::vertex_descriptor;
18using SinkMap = flat_map<PabloAST *, Vertex>;
19using VertexSet = std::vector<Vertex>;
20using Biclique = std::pair<VertexSet, VertexSet>;
21using BicliqueSet = std::vector<Biclique>;
22using DistributionSet = std::tuple<VertexSet, VertexSet, VertexSet>;
23using DistributionSets = std::vector<DistributionSet>;
24
25using TypeId = PabloAST::ClassTypeId;
26
27/** ------------------------------------------------------------------------------------------------------------- *
28 * @brief getVertex
29 ** ------------------------------------------------------------------------------------------------------------- */
30static inline Vertex getVertex(PabloAST * value, DependencyGraph & G, SinkMap & M) {
31    const auto f = M.find(value);
32    if (f != M.end()) {
33        return f->second;
34    }
35    const auto u = add_vertex(value, G);
36    M.emplace(value, u);
37    return u;
38}
39
40/** ------------------------------------------------------------------------------------------------------------- *
41 * @brief generateDistributionGraph
42 *
43 * Generate a graph G describing the potential applications of the distributive law for the given block.
44 ** ------------------------------------------------------------------------------------------------------------- */
45VertexSet generateDistributionGraph(PabloBlock * block, DependencyGraph & G) {
46    SinkMap M;
47    VertexSet distSet;
48    for (Statement * stmt : *block) {
49        if (isa<And>(stmt) || isa<Or>(stmt)) {
50            const TypeId outerTypeId = stmt->getClassTypeId();
51            const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
52            flat_set<PabloAST *> distributable;
53            for (PabloAST * const expr : *cast<Variadic>(stmt)) {
54                if (LLVM_UNLIKELY(expr->getClassTypeId() == innerTypeId)) {
55                    bool safe = true;
56                    for (PabloAST * const user : expr->users()) {
57                        if (user->getClassTypeId() != outerTypeId) {
58                            safe = false;
59                            break;
60                        }
61                    }
62                    if (safe) {
63                        distributable.insert(expr);
64                    }
65                }
66            }
67            if (LLVM_LIKELY(distributable.size() > 1)) {
68                flat_map<PabloAST *, bool> observedMoreThanOnce;
69                bool anyOpportunities = false;
70                for (const PabloAST * distOperation : distributable) {
71                    for (PabloAST * const distVar : *cast<Variadic>(distOperation)) {
72                        auto ob = observedMoreThanOnce.find(distVar);
73                        if (ob == observedMoreThanOnce.end()) {
74                            observedMoreThanOnce.emplace(distVar, false);
75                        } else {
76                            ob->second = true;
77                            anyOpportunities = true;
78                        }
79                    }
80                }
81                if (anyOpportunities) {
82                    for (const auto ob : observedMoreThanOnce) {
83                        PabloAST * distVar = nullptr;
84                        bool observedTwice = false;
85                        std::tie(distVar, observedTwice) = ob;
86                        if (observedTwice) {
87                            const Vertex z = getVertex(stmt, G, M);
88                            distSet.push_back(z);
89                            for (PabloAST * const distOperation : distVar->users()) {
90                                if (distributable.count(distOperation)) {
91                                    const Vertex y = getVertex(distOperation, G, M);
92                                    add_edge(getVertex(distVar, G, M), y, G);
93                                    add_edge(y, z, G);
94                                }
95                            }
96                        }
97                    }
98                }
99            }
100        }
101    }
102    return distSet;
103}
104
105/** ------------------------------------------------------------------------------------------------------------- *
106 * @brief intersects
107 ** ------------------------------------------------------------------------------------------------------------- */
108template <class Type>
109inline bool intersects(const Type & A, const Type & B) {
110    auto first1 = A.begin(), last1 = A.end();
111    auto first2 = B.begin(), last2 = B.end();
112    while (first1 != last1 && first2 != last2) {
113        if (*first1 < *first2) {
114            ++first1;
115        } else if (*first2 < *first1) {
116            ++first2;
117        } else {
118            return true;
119        }
120    }
121    return false;
122}
123
124/** ------------------------------------------------------------------------------------------------------------- *
125 * @brief independentCliqueSets
126 ** ------------------------------------------------------------------------------------------------------------- */
127template <unsigned side>
128inline static BicliqueSet && independentCliqueSets(BicliqueSet && bicliques, const unsigned minimum) {
129    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
130
131    const auto l = bicliques.size();
132    IndependentSetGraph I(l);
133
134    // Initialize our weights and determine the constraints
135    for (unsigned i = 0; i != l; ++i) {
136        I[i] = std::pow(std::get<side>(bicliques[i]).size(), 2);
137        for (unsigned j = i + 1; j != l; ++j) {
138            if (intersects(std::get<side>(bicliques[i]), std::get<side>(bicliques[j]))) {
139                add_edge(i, j, I);
140            }
141        }
142    }
143
144//    // Initialize our weights and determine the constraints
145//    for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
146//        I[std::distance(bicliques.begin(), i)] = std::pow(std::get<side>(*i).size(), 2);
147//        for (auto j = i; ++j != bicliques.end(); ) {
148//            if (intersects(i->second, j->second) && intersects(i->first, j->first)) {
149//                add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
150//            }
151//        }
152//    }
153
154    // Use the greedy algorithm to choose our independent set
155    VertexSet selected;
156    for (;;) {
157        unsigned w = 0;
158        Vertex u = 0;
159        for (unsigned i = 0; i != l; ++i) {
160            if (I[i] > w) {
161                w = I[i];
162                u = i;
163            }
164        }
165        if (w < minimum) break;
166        selected.push_back(u);
167        I[u] = 0;
168        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
169            I[v] = 0;
170        }
171    }
172
173    // Sort the selected list and then remove the unselected cliques
174    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
175    auto end = bicliques.end();
176    for (const unsigned offset : selected) {
177        end = bicliques.erase(bicliques.begin() + offset + 1, end) - 1;
178    }
179    bicliques.erase(bicliques.begin(), end);
180
181    return std::move(bicliques);
182}
183
184/** ------------------------------------------------------------------------------------------------------------- *
185 * @brief enumerateBicliques
186 *
187 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
188 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
189 * bipartition A and their adjacencies to be in B.
190  ** ------------------------------------------------------------------------------------------------------------- */
191static BicliqueSet enumerateBicliques(const DependencyGraph & G, const VertexSet & A) {
192    using IntersectionSets = std::set<VertexSet>;
193
194    IntersectionSets B1;
195    for (auto u : A) {
196        if (in_degree(u, G) > 0) {
197            VertexSet incomingAdjacencies;
198            incomingAdjacencies.reserve(in_degree(u, G));
199            for (auto e : make_iterator_range(in_edges(u, G))) {
200                incomingAdjacencies.push_back(source(e, G));
201            }
202            std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
203            B1.insert(std::move(incomingAdjacencies));
204        }
205    }
206
207    IntersectionSets B(B1);
208
209    IntersectionSets Bi;
210
211    VertexSet clique;
212    for (auto i = B1.begin(); i != B1.end(); ++i) {
213        for (auto j = i; ++j != B1.end(); ) {
214            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
215            if (clique.size() > 0) {
216                if (B.count(clique) == 0) {
217                    Bi.insert(clique);
218                }
219                clique.clear();
220            }
221        }
222    }
223
224    for (;;) {
225        if (Bi.empty()) {
226            break;
227        }
228        B.insert(Bi.begin(), Bi.end());
229        IntersectionSets Bk;
230        for (auto i = B1.begin(); i != B1.end(); ++i) {
231            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
232                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
233                if (clique.size() > 0) {
234                    if (B.count(clique) == 0) {
235                        Bk.insert(clique);
236                    }
237                    clique.clear();
238                }
239            }
240        }
241        Bi.swap(Bk);
242    }
243
244    BicliqueSet cliques;
245    cliques.reserve(B.size());
246    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
247        VertexSet Ai(A);
248        for (const Vertex u : *Bi) {
249            VertexSet Aj;
250            Aj.reserve(out_degree(u, G));
251            for (auto e : make_iterator_range(out_edges(u, G))) {
252                Aj.push_back(target(e, G));
253            }
254            std::sort(Aj.begin(), Aj.end());
255            VertexSet Ak;
256            Ak.reserve(std::min(Ai.size(), Aj.size()));
257            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
258            Ai.swap(Ak);
259        }
260        assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
261        cliques.emplace_back(std::move(Ai), std::move(*Bi));
262    }
263    return std::move(cliques);
264}
265
266/** ------------------------------------------------------------------------------------------------------------- *
267 * @brief removeUnhelpfulBicliques
268 *
269 * An intermediary vertex could have more than one outgoing edge but if any that are not directed to vertices in
270 * the lower biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if
271 * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
272 ** ------------------------------------------------------------------------------------------------------------- */
273static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, DependencyGraph & G) {
274    for (auto ci = cliques.begin(); ci != cliques.end(); ) {
275        const auto cardinalityA = std::get<0>(*ci).size();
276        VertexSet & B = std::get<1>(*ci);
277        for (auto bi = B.begin(); bi != B.end(); ) {
278            if (G[*bi]->getNumUses() == cardinalityA) {
279                ++bi;
280            } else {
281                bi = B.erase(bi);
282            }
283        }
284        if (B.size() > 1) {
285            ++ci;
286        } else {
287            ci = cliques.erase(ci);
288        }
289    }
290    return std::move(cliques);
291}
292
293/** ------------------------------------------------------------------------------------------------------------- *
294 * @brief safeDistributionSets
295 ** ------------------------------------------------------------------------------------------------------------- */
296static DistributionSets safeDistributionSets(DependencyGraph & G, const VertexSet & distSet) {
297    DistributionSets T;
298    BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(G, distSet), G), 1);
299    for (Biclique & lower : lowerSet) {
300        BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(G, std::get<1>(lower)), 2);
301        for (Biclique & upper : upperSet) {
302            T.emplace_back(std::move(std::get<1>(upper)), std::move(std::get<0>(upper)), std::get<0>(lower));
303        }
304    }
305    return std::move(T);
306}
307
308/** ------------------------------------------------------------------------------------------------------------- *
309 * @brief process
310 ** ------------------------------------------------------------------------------------------------------------- */
311inline void DistributivePass::process(PabloBlock * const block) {
312
313    for (;;) {
314
315        // FlattenAssociativeDFG::coalesce(block, false);
316
317        DependencyGraph G;
318
319        const VertexSet distSet = generateDistributionGraph(block, G);
320
321        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
322        if (LLVM_UNLIKELY(distSet.empty())) {
323            break;
324        }
325
326        const DistributionSets distributionSets = safeDistributionSets(G, distSet);
327
328        if (LLVM_UNLIKELY(distributionSets.empty())) {
329            break;
330        }
331
332        for (const DistributionSet & set : distributionSets) {
333
334            // Each distribution tuple consists of the sources, intermediary, and sink nodes.
335            const VertexSet & sources = std::get<0>(set);
336            const VertexSet & intermediary = std::get<1>(set);
337            const VertexSet & sinks = std::get<2>(set);
338
339            // Find the first sink and set the insert point immediately before that.
340            Variadic * innerOp = nullptr;
341            Variadic * outerOp = nullptr;
342
343            block->setInsertPoint(cast<Variadic>(G[sinks.front()])->getPrevNode());
344            if (isa<And>(G[sinks.front()])) {
345                outerOp = block->createAnd(intermediary.size());
346                innerOp = block->createOr(sources.size() + 1);
347            } else {
348                outerOp = block->createOr(intermediary.size());
349                innerOp = block->createAnd(sources.size() + 1);
350            }
351
352            for (const Vertex u : intermediary) {
353                for (const Vertex v : sinks) {
354                    cast<Variadic>(G[v])->deleteOperand(G[u]);
355                }
356                outerOp->addOperand(G[u]);
357            }
358            CoalesceDFG::coalesce(outerOp);
359
360            for (const Vertex u : sources) {
361                for (const Vertex v : intermediary) {
362                    cast<Variadic>(G[v])->deleteOperand(G[u]);
363                }
364                innerOp->addOperand(G[u]);
365            }
366            innerOp->addOperand(outerOp);
367            CoalesceDFG::coalesce(innerOp);
368
369            for (const Vertex u : sinks) {
370                cast<Variadic>(G[u])->addOperand(innerOp);
371            }
372        }
373    }
374}
375
376/** ------------------------------------------------------------------------------------------------------------- *
377 * @brief distribute
378 ** ------------------------------------------------------------------------------------------------------------- */
379void DistributivePass::distribute(PabloBlock * const block) {
380    for (Statement * stmt : *block) {
381        if (isa<If>(stmt) || isa<While>(stmt)) {
382            distribute(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
383        }
384    }
385    process(block);
386}
387
388/** ------------------------------------------------------------------------------------------------------------- *
389 * @brief optimize
390 ** ------------------------------------------------------------------------------------------------------------- */
391void DistributivePass::optimize(PabloFunction & function) {
392    DistributivePass::distribute(function.getEntryBlock());
393    #ifndef NDEBUG
394    PabloVerifier::verify(function, "post-distribution");
395    #endif
396    Simplifier::optimize(function);
397}
398
399
400}
Note: See TracBrowser for help on using the repository browser.