source: icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.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: 21.3 KB
Line 
1#include "flattenassociativedfg.h"
2#include <pablo/codegenstate.h>
3#include <pablo/optimizers/pablo_simplifier.hpp>
4#include <pablo/analysis/pabloverifier.hpp>
5#include <boost/container/flat_set.hpp>
6#include <boost/container/flat_map.hpp>
7#include <boost/graph/adjacency_list.hpp>
8
9#include <pablo/printer_pablos.h>
10#include <iostream>
11
12using namespace boost;
13using namespace boost::container;
14
15namespace pablo {
16
17using TypeId = PabloAST::ClassTypeId;
18
19/** ------------------------------------------------------------------------------------------------------------- *
20 * @brief coalesce
21 ** ------------------------------------------------------------------------------------------------------------- */
22inline void FlattenAssociativeDFG::coalesce(Variadic * const var) {
23    const TypeId typeId = var->getClassTypeId();
24    for (unsigned i = 0; i < var->getNumOperands(); ) {
25        PabloAST * const op = var->getOperand(i);
26        if (op->getClassTypeId() == typeId) {
27            Variadic * removedVar = cast<Variadic>(var->removeOperand(i));
28            for (unsigned j = 0; j != cast<Variadic>(op)->getNumOperands(); ++j) {
29                var->addOperand(cast<Variadic>(op)->getOperand(j));
30            }
31            if (removedVar->getNumOperands() == 1) {
32                removedVar->replaceWith(removedVar->getOperand(0));
33            } else if (removedVar->getNumUses() == 0) {
34                removedVar->eraseFromParent(true);
35            }
36            continue;
37        }
38        ++i;
39    }
40}
41
42/** ------------------------------------------------------------------------------------------------------------- *
43 * @brief coalesce
44 ** ------------------------------------------------------------------------------------------------------------- */
45void FlattenAssociativeDFG::coalesce(PabloBlock * const block, const bool traverse) {
46    Statement * stmt = block->front();
47    while (stmt) {
48        Statement * next = stmt->getNextNode();
49        if (LLVM_UNLIKELY((isa<If>(stmt) || isa<While>(stmt)) && traverse)) {
50            coalesce(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), true);
51        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
52            coalesce(cast<Variadic>(stmt));
53        } else if (isa<Not>(stmt)) {
54            deMorgansExpansion(cast<Not>(stmt), block);
55        }
56        stmt = next;
57    }
58}
59
60/** ------------------------------------------------------------------------------------------------------------- *
61 * @brief deMorgansExpansion
62 *
63 * Apply the De Morgans' law to any negated And or Or statement with the intent of further coalescing its operands
64 * thereby allowing the Simplifier to check for tautologies and contradictions.
65 ** ------------------------------------------------------------------------------------------------------------- */
66inline void FlattenAssociativeDFG::deMorgansExpansion(Not * const var, PabloBlock * const block) {
67    PabloAST * const negatedVar = var->getOperand(0);
68    if (isa<And>(negatedVar) || isa<Or>(negatedVar)) {
69        Variadic * src = cast<Variadic>(negatedVar);
70        const unsigned operands = src->getNumOperands();
71        Variadic * replacement = nullptr;
72        block->setInsertPoint(var->getPrevNode());
73        if (isa<And>(negatedVar)) {
74            replacement = block->createOr(operands);
75        } else {
76            replacement = block->createAnd(operands);
77        }
78        block->setInsertPoint(replacement->getPrevNode());
79        for (unsigned i = 0; i != operands; ++i) {
80            replacement->addOperand(block->createNot(src->getOperand(i)));
81        }
82        coalesce(replacement);
83        var->replaceWith(replacement, true, true);
84    }
85}
86
87/** ------------------------------------------------------------------------------------------------------------- *
88 * @brief deMorgansReduction
89 ** ------------------------------------------------------------------------------------------------------------- */
90inline void FlattenAssociativeDFG::deMorgansReduction(Variadic * const var, PabloBlock * const block) {
91    unsigned negations = 0;
92    for (unsigned i = 0; i < var->getNumOperands(); ++i) {
93        if (isa<Not>(var->getOperand(i))) {
94            ++negations;
95        }
96    }
97    if (negations > 1) {
98        PabloAST * negated[negations];
99        for (unsigned i = var->getNumOperands(), j = negations; i && j; ) {
100            if (isa<Not>(var->getOperand(--i))) {
101                negated[--j] = cast<Not>(var->removeOperand(i))->getOperand(0);
102            }
103        }
104        block->setInsertPoint(var->getPrevNode());
105        Variadic * extractedVar = nullptr;
106        if (isa<And>(var)) {
107            extractedVar = block->createOr(negations);
108        } else { // if (isa<Or>(var)) {
109            extractedVar = block->createAnd(negations);
110        }
111        for (unsigned i = 0; i != negations; ++i) {
112            extractedVar->addOperand(negated[i]);
113        }
114        var->addOperand(block->createNot(extractedVar));
115    }
116}
117
118/** ------------------------------------------------------------------------------------------------------------- *
119 * @brief deMorgansReduction
120 ** ------------------------------------------------------------------------------------------------------------- */
121inline void FlattenAssociativeDFG::deMorgansReduction(PabloBlock * const block) {
122    for (Statement * stmt : *block) {
123        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
124            deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
125        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
126            deMorgansReduction(cast<Variadic>(stmt), block);
127        }
128    }
129}
130
131union VertexData {
132    Assign * def;
133    TypeId   typeId;
134    explicit VertexData() : def(nullptr) { }
135    explicit VertexData(Assign * def) : def(def) { }
136    explicit VertexData(TypeId typeId) : typeId(typeId) { }
137};
138using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, Variadic *>;
139using Vertex = Graph::vertex_descriptor;
140using Map = flat_map<TypeId, Vertex>;
141using VertexSet = std::vector<Vertex>;
142using Biclique = std::pair<VertexSet, VertexSet>;
143using BicliqueSet = std::vector<Biclique>;
144
145/** ------------------------------------------------------------------------------------------------------------- *
146 * @brief addToVariadicGraph
147 ** ------------------------------------------------------------------------------------------------------------- */
148static bool addToVariadicGraph(Assign * const def, Graph & G, Map & M, VertexSet & A) {
149
150    // Test if its valid to transform this statement
151    for (PabloAST * user : def->users()) {
152        if (isa<Variadic>(user) == 0) {
153            if (isa<If>(user)) {
154                const auto defs = cast<If>(user)->getDefined();
155                if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), def) != defs.end())) {
156                    continue;
157                }
158            }
159            return false;
160        }
161    }
162
163    // Add the statement and its users to G
164    const Vertex u = add_vertex(VertexData(def), G);
165    A.push_back(u);
166    for (PabloAST * user : def->users()) {
167        if (isa<Variadic>(user)) {
168            auto f = M.find(user->getClassTypeId());
169            if (f == M.end()) {
170                f = M.emplace(user->getClassTypeId(), add_vertex(VertexData(user->getClassTypeId()), G)).first;
171            }
172            assert (f != M.end());
173            G[add_edge(u, f->second, G).first] = cast<Variadic>(user);
174        }
175    }
176    return true;
177}
178
179/** ------------------------------------------------------------------------------------------------------------- *
180 * @brief matches
181 ** ------------------------------------------------------------------------------------------------------------- */
182inline static bool matches(const PabloAST * const a, const PabloAST * const b) {
183    return (isa<Assign>(b)) && (cast<Assign>(a)->getParent() == cast<Assign>(b)->getParent());
184}
185
186/** ------------------------------------------------------------------------------------------------------------- *
187 * @brief enumerateBicliques
188 *
189 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
190 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
191 * bipartition A and their adjacencies to be in B.
192  ** ------------------------------------------------------------------------------------------------------------- */
193static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
194    using IntersectionSets = std::set<VertexSet>;
195
196    IntersectionSets B1;
197    for (auto u : A) {
198        flat_set<Vertex> adj;
199        adj.reserve(out_degree(u, G));
200        for (auto e : make_iterator_range(out_edges(u, G))) {
201            adj.insert(target(e, G));
202        }
203        B1.emplace(adj.begin(), adj.end());
204    }
205
206    IntersectionSets B(B1);
207
208    IntersectionSets Bi;
209
210    VertexSet clique;
211    for (auto i = B1.begin(); i != B1.end(); ++i) {
212        for (auto j = i; ++j != B1.end(); ) {
213            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
214            if (clique.size() > 0) {
215                if (B.count(clique) == 0) {
216                    Bi.insert(clique);
217                }
218                clique.clear();
219            }
220        }
221    }
222
223    for (;;) {
224        if (Bi.empty()) {
225            break;
226        }
227        B.insert(Bi.begin(), Bi.end());
228        IntersectionSets Bk;
229        for (auto i = B1.begin(); i != B1.end(); ++i) {
230            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
231                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
232                if (clique.size() > 0) {
233                    if (B.count(clique) == 0) {
234                        Bk.insert(clique);
235                    }
236                    clique.clear();
237                }
238            }
239        }
240        Bi.swap(Bk);
241    }
242
243    BicliqueSet S;
244    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
245        VertexSet Ai(A);
246        for (const Vertex u : *Bi) {
247            VertexSet Aj;
248            Aj.reserve(in_degree(u, G));
249            for (auto e : make_iterator_range(in_edges(u, G))) {
250                Aj.push_back(source(e, G));
251            }
252            std::sort(Aj.begin(), Aj.end());
253            VertexSet Ak;
254            Ak.reserve(std::min(Ai.size(), Aj.size()));
255            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
256            Ai.swap(Ak);
257        }
258        assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
259        // If |Ai| > |Bi|, removing Ai from of the Variadic and sinking it into the nested scope will
260        // reduce the number of values stored.
261        if (Ai.size() > Bi->size()) {
262            S.emplace_back(std::move(Ai), std::move(*Bi));
263        }
264    }
265    return S;
266}
267
268/** ------------------------------------------------------------------------------------------------------------- *
269 * @brief intersects
270 ** ------------------------------------------------------------------------------------------------------------- */
271template <class Type>
272inline bool intersects(const Type & A, const Type & B) {
273    auto first1 = A.begin(), last1 = A.end();
274    auto first2 = B.begin(), last2 = B.end();
275    while (first1 != last1 && first2 != last2) {
276        if (*first1 < *first2) {
277            ++first1;
278        } else if (*first2 < *first1) {
279            ++first2;
280        } else {
281            return true;
282        }
283    }
284    return false;
285}
286
287/** ------------------------------------------------------------------------------------------------------------- *
288 * @brief independentCliqueSets
289 ** ------------------------------------------------------------------------------------------------------------- */
290template <unsigned side>
291inline static BicliqueSet independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) {
292    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
293
294    const auto l = cliques.size();
295    IndependentSetGraph I(l);
296
297    // Initialize our weights
298    for (unsigned i = 0; i != l; ++i) {
299        I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
300    }
301
302    // Determine our constraints
303    for (unsigned i = 0; i != l; ++i) {
304        for (unsigned j = i + 1; j != l; ++j) {
305            if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
306                add_edge(i, j, I);
307            }
308        }
309    }
310
311    // Use the greedy algorithm to choose our independent set
312    VertexSet selected;
313    for (;;) {
314        unsigned w = 0;
315        Vertex u = 0;
316        for (unsigned i = 0; i != l; ++i) {
317            if (I[i] > w) {
318                w = I[i];
319                u = i;
320            }
321        }
322        if (w < minimum) break;
323        selected.push_back(u);
324        I[u] = 0;
325        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
326            I[v] = 0;
327        }
328    }
329
330    // Sort the selected list and then remove the unselected cliques
331    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
332    auto end = cliques.end();
333    for (const unsigned offset : selected) {
334        end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
335    }
336    cliques.erase(cliques.begin(), end);
337
338    return std::move(cliques);
339}
340
341/** ------------------------------------------------------------------------------------------------------------- *
342 * @brief tryToPartiallyExtractVariadic
343 ** ------------------------------------------------------------------------------------------------------------- */
344void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
345
346    for (unsigned i = 0; i < var->getNumOperands(); ++i) {
347        PabloAST * const op = var->getOperand(i);
348        if (isa<Assign>(op)) {
349            // Have we found a variadic operation that can sunk into a nested scope?
350            for (unsigned j = i + 1; j != var->getNumOperands(); ++j) {
351                bool invalid = false;
352                if (LLVM_UNLIKELY(matches(op, var->getOperand(j)))) {
353                    Graph G;
354                    Map M;
355                    VertexSet A;
356                    if (addToVariadicGraph(cast<Assign>(op), G, M, A) == 0) {
357                        invalid = true;
358                        break;
359                    }
360                    addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, M, A);
361                    for (++j; j != var->getNumOperands(); ++j) {
362                        if (LLVM_UNLIKELY(matches(op, var->getOperand(j)))) {
363                            addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, M, A);
364                        }
365                    }
366                    if (A.size() > 1) {
367                        const auto S = independentCliqueSets<0>(std::move(enumerateBicliques(G, A)), 2);
368                        for (const Biclique & C : S) {
369                            const VertexSet & sources = std::get<0>(C);
370                            const VertexSet & variadics = std::get<1>(C);
371                            PabloBlock * const block = cast<Assign>(op)->getParent();
372                            block->setInsertPoint(block->back());
373                            for (const auto v : variadics) {
374                                Variadic * joiner = nullptr;
375                                switch (G[v].typeId) {
376                                    case TypeId::And:
377                                        joiner = block->createAnd(sources.size());
378                                        break;
379                                    case TypeId::Or:
380                                        joiner = block->createOr(sources.size());
381                                        break;
382                                    case TypeId::Xor:
383                                        joiner = block->createXor(sources.size());
384                                        break;
385                                    default:
386                                        break;
387                                }
388                                assert (joiner);
389                                flat_set<Variadic *> vars;
390                                for (const auto u : sources) {
391                                    Assign * const def = G[u].def;
392                                    joiner->addOperand(def->getOperand(0));
393                                    for (auto e : make_iterator_range(out_edges(u, G))) {
394                                        if (LLVM_LIKELY(target(e, G) == v)) {
395                                            Variadic * const var = cast<Variadic>(G[e]);
396                                            vars.insert(var);
397                                            var->deleteOperand(def);
398                                        }
399                                    }
400                                    assert (def->getNumUses() == 1);
401                                    def->eraseFromParent();
402                                }
403                                coalesce(joiner);
404                                Assign * const def = block->createAssign("m", joiner);
405                                cast<If>(block->getBranch())->addDefined(def);
406                                for (Variadic * var : vars) {
407                                    var->addOperand(def);
408                                }
409                            }
410                        }
411                    }
412                    break;
413                }
414                if (invalid) {
415                    break;
416                }
417            }
418        }
419    }
420}
421
422/** ------------------------------------------------------------------------------------------------------------- *
423 * @brief removeFalseScopeDependencies
424 ** ------------------------------------------------------------------------------------------------------------- */
425inline void FlattenAssociativeDFG::removeFalseScopeDependencies(Assign * const def) {
426    if (isa<Variadic>(def->getOperand(0))) {
427        Variadic * const var = cast<Variadic>(def->getOperand(0));
428        for (unsigned i = 0; i != var->getNumOperands(); ++i) {
429            if (isa<Assign>(var->getOperand(i))) {
430                Assign * const nestedDef = cast<Assign>(var->getOperand(i));
431                if (LLVM_LIKELY(nestedDef->getOperand(0)->getClassTypeId() == var->getClassTypeId())) {
432                    if (LLVM_LIKELY(nestedDef->getNumUses() == 2)) { // The If node that produces it and the "var"
433                        Variadic * const nestedVar = cast<Variadic>(nestedDef->getOperand(0));
434                        if (LLVM_LIKELY(nestedVar->getNumUses() == 1 && nestedVar->getNumOperands() > 0)) {
435                            for (unsigned i = 0, j = 0; ; ) {
436                                if (var->getOperand(i) < nestedVar->getOperand(j)) {
437                                    if (++i == var->getNumOperands()) {
438                                        break;
439                                    }
440                                } else {
441                                    if (var->getOperand(i) > nestedVar->getOperand(j)) {
442                                        ++j;
443                                    } else {
444                                        nestedVar->removeOperand(j);
445                                    }
446                                    if (j == nestedVar->getNumOperands()) {
447                                        break;
448                                    }
449                                }
450                            }
451                        }
452                    }
453                }
454            }
455        }
456    }
457}
458
459/** ------------------------------------------------------------------------------------------------------------- *
460 * @brief removeFalseScopeDependencies
461 *
462 * After coalescing the AST, we may find that a result of some If statement is added to a result of a subsequent
463 * If statement. Unless necessary for correctness, eliminate it as we can potentially schedule the If nodes
464 * better without the sequential dependency.
465 ** ------------------------------------------------------------------------------------------------------------- */
466void FlattenAssociativeDFG::removeFalseScopeDependencies(PabloBlock * const block) {
467    for (Statement * stmt = block->back(); stmt; stmt = stmt->getPrevNode()) {
468        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
469            removeFalseScopeDependencies(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
470        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
471            removeFalseScopeDependencies(cast<Assign>(stmt));
472        } else if (isa<Variadic>(stmt)) {
473            tryToPartiallyExtractVariadic(cast<Variadic>(stmt));
474        }
475    }
476}
477
478/** ------------------------------------------------------------------------------------------------------------- *
479 * @brief transform
480 ** ------------------------------------------------------------------------------------------------------------- */
481void FlattenAssociativeDFG::transform(PabloFunction & function) {
482
483    FlattenAssociativeDFG::coalesce(function.getEntryBlock(), true);
484    #ifndef NDEBUG
485    PabloVerifier::verify(function, "post-coalescence");
486    #endif
487
488    Simplifier::optimize(function);
489
490    FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock());
491    #ifndef NDEBUG
492    PabloVerifier::verify(function, "post-demorgans-reduction");
493    #endif
494
495    Simplifier::optimize(function);
496
497    FlattenAssociativeDFG::removeFalseScopeDependencies(function.getEntryBlock());
498    #ifndef NDEBUG
499    PabloVerifier::verify(function, "post-remove-false-scope-dependencies");
500    #endif
501
502    Simplifier::optimize(function);
503}
504
505}
Note: See TracBrowser for help on using the repository browser.