source: icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp @ 4919

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

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

File size: 26.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#include <queue>
9
10using namespace boost;
11using namespace boost::container;
12
13namespace pablo {
14
15using TypeId = PabloAST::ClassTypeId;
16
17/** ------------------------------------------------------------------------------------------------------------- *
18 * @brief coalesce
19 ** ------------------------------------------------------------------------------------------------------------- */
20inline Variadic * CoalesceDFG::coalesce(Variadic * const var) {
21    const TypeId typeId = var->getClassTypeId();
22    for (unsigned i = 0; i < var->getNumOperands(); ) {
23        PabloAST * const op = var->getOperand(i);
24        if (op->getClassTypeId() == typeId) {
25            Variadic * removedVar = cast<Variadic>(var->removeOperand(i));
26            for (unsigned j = 0; j != cast<Variadic>(op)->getNumOperands(); ++j) {
27                var->addOperand(cast<Variadic>(op)->getOperand(j));
28            }
29            if (removedVar->getNumOperands() == 1) {
30                removedVar->replaceWith(removedVar->getOperand(0));
31            } else if (removedVar->getNumUses() == 0) {
32                removedVar->eraseFromParent(true);
33            }
34            continue;
35        }
36        ++i;
37    }
38    return var;
39}
40
41/** ------------------------------------------------------------------------------------------------------------- *
42 * @brief coalesce
43 ** ------------------------------------------------------------------------------------------------------------- */
44void CoalesceDFG::coalesce(PabloBlock * const block, const bool traverse) {
45    Statement * stmt = block->front();
46    while (stmt) {
47        Statement * next = stmt->getNextNode();
48        if (LLVM_UNLIKELY((isa<If>(stmt) || isa<While>(stmt)) && traverse)) {
49            coalesce(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), true);
50        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
51            coalesce(cast<Variadic>(stmt));
52        }/* else if (isa<Not>(stmt)) {
53            deMorgansExpansion(cast<Not>(stmt), block);
54        }*/
55        stmt = next;
56    }
57}
58
59/** ------------------------------------------------------------------------------------------------------------- *
60 * @brief deMorgansExpansion
61 *
62 * Apply the De Morgans' law to any negated And or Or statement with the intent of further coalescing its operands
63 * thereby allowing the Simplifier to check for tautologies and contradictions.
64 ** ------------------------------------------------------------------------------------------------------------- */
65inline void CoalesceDFG::deMorgansExpansion(Not * const var, PabloBlock * const block) {
66    PabloAST * const negatedVar = var->getOperand(0);
67    if (isa<And>(negatedVar) || isa<Or>(negatedVar)) {
68        const TypeId desiredTypeId = isa<And>(negatedVar) ? TypeId::Or : TypeId::And;
69        bool canApplyDeMorgans = true;
70        for (PabloAST * user : var->users()) {
71            if (desiredTypeId != user->getClassTypeId()) {
72                canApplyDeMorgans = false;
73                break;
74            }
75        }
76        if (canApplyDeMorgans) {
77            const unsigned operands = cast<Variadic>(negatedVar)->getNumOperands();
78            PabloAST * negations[operands];
79            block->setInsertPoint(var);
80            for (unsigned i = 0; i != operands; ++i) {
81                negations[i] = block->createNot(cast<Variadic>(negatedVar)->getOperand(i));
82            }
83            const unsigned users = var->getNumUses();
84            PabloAST * user[users];
85            std::copy(var->user_begin(), var->user_end(), user);
86            for (unsigned i = 0; i != users; ++i) {
87                cast<Variadic>(user[i])->deleteOperand(var);
88                for (unsigned j = 0; j != operands; ++j) {
89                    cast<Variadic>(user[i])->addOperand(negations[j]);
90                }
91            }
92            var->eraseFromParent(true);
93        }
94    }
95}
96
97/** ------------------------------------------------------------------------------------------------------------- *
98 * @brief deMorgansReduction
99 ** ------------------------------------------------------------------------------------------------------------- */
100inline void CoalesceDFG::deMorgansReduction(Variadic * const var, PabloBlock * const block) {
101    unsigned negations = 0;
102    for (unsigned i = 0; i < var->getNumOperands(); ++i) {
103        if (isa<Not>(var->getOperand(i))) {
104            ++negations;
105        }
106    }
107    if (negations > 1) {
108        PabloAST * negated[negations];
109        for (unsigned i = var->getNumOperands(), j = negations; i && j; ) {
110            if (isa<Not>(var->getOperand(--i))) {
111                negated[--j] = cast<Not>(var->removeOperand(i))->getOperand(0);
112            }
113        }
114        block->setInsertPoint(var->getPrevNode());
115        Variadic * extractedVar = nullptr;
116        if (isa<And>(var)) {
117            extractedVar = block->createOr(negations);
118        } else { // if (isa<Or>(var)) {
119            extractedVar = block->createAnd(negations);
120        }
121        for (unsigned i = 0; i != negations; ++i) {
122            extractedVar->addOperand(negated[i]);
123        }
124        var->addOperand(block->createNot(extractedVar));
125    }
126}
127
128/** ------------------------------------------------------------------------------------------------------------- *
129 * @brief deMorgansReduction
130 ** ------------------------------------------------------------------------------------------------------------- */
131void CoalesceDFG::deMorgansReduction(PabloBlock * const block, const bool traverse) {
132    for (Statement * stmt : *block) {
133        if (LLVM_UNLIKELY((isa<If>(stmt) || isa<While>(stmt)) && traverse)) {
134            deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), true);
135        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
136            deMorgansReduction(cast<Variadic>(stmt), block);
137        }
138    }
139}
140
141union VertexData {
142    Assign * def;
143    TypeId   typeId;
144    explicit VertexData() : def(nullptr) { }
145    explicit VertexData(Assign * def) : def(def) { }
146    explicit VertexData(TypeId typeId) : typeId(typeId) { }
147};
148using DependencyGraph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, Variadic *>;
149using Vertex = DependencyGraph::vertex_descriptor;
150using SourceMap = flat_map<Assign *, Vertex>;
151using SinkMap = flat_map<TypeId, Vertex>;
152using VertexSet = std::vector<Vertex>;
153using Biclique = std::pair<VertexSet, VertexSet>;
154using BicliqueSet = std::vector<Biclique>;
155
156/** ------------------------------------------------------------------------------------------------------------- *
157 * @brief addToVariadicGraph
158 ** ------------------------------------------------------------------------------------------------------------- */
159static bool addToVariadicGraph(Assign * const def, DependencyGraph & G, SourceMap & A, SinkMap & B) {
160
161    if (LLVM_LIKELY(A.count(def) == 0)) {
162        // Test if its valid to transform this statement
163        for (PabloAST * user : def->users()) {
164            if (isa<Variadic>(user) == 0) {
165                if (isa<If>(user)) {
166                    if (LLVM_LIKELY(cast<If>(user)->getCondition() != def)) {
167                        continue;
168                    }
169                }
170                return false;
171            }
172        }
173
174        // Add the statement and its users to G
175        const Vertex u = add_vertex(VertexData(def), G);
176        A.emplace(def, u);
177        for (PabloAST * user : def->users()) {
178            if (isa<Variadic>(user)) {
179                auto f = B.find(user->getClassTypeId());
180                if (f == B.end()) {
181                    f = B.emplace(user->getClassTypeId(), add_vertex(VertexData(user->getClassTypeId()), G)).first;
182                }
183                assert (f != B.end());
184                G[add_edge(u, f->second, G).first] = cast<Variadic>(user);
185            }
186        }
187    }
188    return true;
189}
190
191/** ------------------------------------------------------------------------------------------------------------- *
192 * @brief matches
193 ** ------------------------------------------------------------------------------------------------------------- */
194inline static bool matches(const PabloAST * const a, const PabloAST * const b) {
195    return (isa<Assign>(b)) && (cast<Assign>(a)->getParent() == cast<Assign>(b)->getParent());
196}
197
198/** ------------------------------------------------------------------------------------------------------------- *
199 * @brief enumerateBicliques
200 *
201 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
202 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
203 * bipartition A and their adjacencies to be in B.
204  ** ------------------------------------------------------------------------------------------------------------- */
205static BicliqueSet enumerateBicliques(const DependencyGraph & G, const VertexSet & A) {
206    using IntersectionSets = std::set<VertexSet>;
207
208    IntersectionSets B1;
209    for (auto u : A) {
210        flat_set<Vertex> adj;
211        adj.reserve(out_degree(u, G));
212        for (auto e : make_iterator_range(out_edges(u, G))) {
213            adj.insert(target(e, G));
214        }
215        B1.emplace(adj.begin(), adj.end());
216    }
217
218    IntersectionSets B(B1);
219
220    IntersectionSets Bi;
221
222    VertexSet clique;
223    for (auto i = B1.begin(); i != B1.end(); ++i) {
224        for (auto j = i; ++j != B1.end(); ) {
225            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
226            if (clique.size() > 0) {
227                if (B.count(clique) == 0) {
228                    Bi.insert(clique);
229                }
230                clique.clear();
231            }
232        }
233    }
234
235    for (;;) {
236        if (Bi.empty()) {
237            break;
238        }
239        B.insert(Bi.begin(), Bi.end());
240        IntersectionSets Bk;
241        for (auto i = B1.begin(); i != B1.end(); ++i) {
242            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
243                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
244                if (clique.size() > 0) {
245                    if (B.count(clique) == 0) {
246                        Bk.insert(clique);
247                    }
248                    clique.clear();
249                }
250            }
251        }
252        Bi.swap(Bk);
253    }
254
255    BicliqueSet S;
256    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
257        VertexSet Ai(A);
258        for (const Vertex u : *Bi) {
259            VertexSet Aj;
260            Aj.reserve(in_degree(u, G));
261            for (auto e : make_iterator_range(in_edges(u, G))) {
262                Aj.push_back(source(e, G));
263            }
264            std::sort(Aj.begin(), Aj.end());
265            VertexSet Ak;
266            Ak.reserve(std::min(Ai.size(), Aj.size()));
267            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
268            Ai.swap(Ak);
269        }
270        assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
271        // If |Ai| > |Bi|, removing Ai from of the Variadic and sinking it into the nested scope will
272        // reduce the number of values stored.
273        if (Ai.size() > Bi->size()) {
274            S.emplace_back(std::move(Ai), std::move(*Bi));
275        }
276    }
277    return S;
278}
279
280/** ------------------------------------------------------------------------------------------------------------- *
281 * @brief intersects
282 ** ------------------------------------------------------------------------------------------------------------- */
283template <class Type>
284inline bool intersects(const Type & A, const Type & B) {
285    auto first1 = A.begin(), last1 = A.end();
286    auto first2 = B.begin(), last2 = B.end();
287    assert (std::is_sorted(first1, last1));
288    assert (std::is_sorted(first2, last2));
289    while (first1 != last1 && first2 != last2) {
290        if (*first1 < *first2) {
291            ++first1;
292        } else if (*first2 < *first1) {
293            ++first2;
294        } else {
295            return true;
296        }
297    }
298    return false;
299}
300
301/** ------------------------------------------------------------------------------------------------------------- *
302 * @brief independentCliqueSets
303 ** ------------------------------------------------------------------------------------------------------------- */
304template <unsigned side>
305inline static BicliqueSet independentCliqueSets(BicliqueSet && bicliques, const unsigned minimum) {
306    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
307
308    const auto l = bicliques.size();
309    IndependentSetGraph I(l);
310
311    // Initialize our weights and determine the constraints
312    for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
313        I[std::distance(bicliques.begin(), i)] = std::pow(std::get<side>(*i).size(), 2);
314        for (auto j = i; ++j != bicliques.end(); ) {
315            if (intersects(i->second, j->second) && intersects(i->first, j->first)) {
316                add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
317            }
318        }
319    }
320
321    // Use the greedy algorithm to choose our independent set
322    VertexSet selected;
323    for (;;) {
324        unsigned w = 0;
325        Vertex u = 0;
326        for (unsigned i = 0; i != l; ++i) {
327            if (I[i] > w) {
328                w = I[i];
329                u = i;
330            }
331        }
332        if (w < minimum) break;
333        selected.push_back(u);
334        I[u] = 0;
335        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
336            I[v] = 0;
337        }
338    }
339
340    // Sort the selected list and then remove the unselected cliques
341    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
342    auto end = bicliques.end();
343    for (const unsigned offset : selected) {
344        end = bicliques.erase(bicliques.begin() + offset + 1, end) - 1;
345    }
346    bicliques.erase(bicliques.begin(), end);
347
348    return std::move(bicliques);
349}
350
351/** ------------------------------------------------------------------------------------------------------------- *
352 * @brief tryToPartiallyExtractVariadic
353 ** ------------------------------------------------------------------------------------------------------------- */
354inline void CoalesceDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
355    for (unsigned i = 0; i < var->getNumOperands(); ++i) {
356        PabloAST * const op = var->getOperand(i);
357        if (isa<Assign>(op)) {
358            // Look for two Assign statements in this variadic; we don't want to generate a dependency graph unless
359            // we expect some optimization can occur.
360            for (unsigned j = i + 1; j != var->getNumOperands(); ++j) {
361                bool invalid = false;
362                if (LLVM_UNLIKELY(matches(op, var->getOperand(j)))) {
363                    DependencyGraph G;
364                    SourceMap A;
365                    SinkMap B;
366                    if (addToVariadicGraph(cast<Assign>(op), G, A, B) == 0) {
367                        invalid = true;
368                        break;
369                    }
370                    addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, A, B);
371                    for (++j; j != var->getNumOperands(); ++j) {
372                        if (LLVM_UNLIKELY(matches(op, var->getOperand(j)))) {
373                            addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, A, B);
374                        }
375                    }
376
377                    if (A.size() > 1) {
378
379                        VertexSet H;
380                        H.reserve(A.size());
381                        for (auto a : A) {
382                            H.push_back(a.second);
383                        }
384
385                        const auto S = independentCliqueSets<0>(std::move(enumerateBicliques(G, H)), 2);
386                        if (LLVM_UNLIKELY(S.empty())) {
387                            break;
388                        }
389                        for (const Biclique & C : S) {
390                            const VertexSet & sources = std::get<0>(C);
391                            const VertexSet & variadics = std::get<1>(C);
392                            assert (variadics.size() > 0);
393                            assert (sources.size() > variadics.size());
394                            PabloBlock * const block = cast<Assign>(op)->getParent();
395                            block->setInsertPoint(block->back());
396                            for (const auto v : variadics) {
397                                Variadic * joiner = nullptr;
398                                switch (G[v].typeId) {
399                                    case TypeId::And:
400                                        joiner = block->createAnd(sources.size());
401                                        break;
402                                    case TypeId::Or:
403                                        joiner = block->createOr(sources.size());
404                                        break;
405                                    case TypeId::Xor:
406                                        joiner = block->createXor(sources.size());
407                                        break;
408                                    default: llvm_unreachable("Unexpected!");
409                                }
410                                assert (joiner);
411                                flat_set<Assign *> defs;
412                                for (const auto u : sources) {
413                                    defs.insert(G[u].def);
414                                }
415                                for (Assign * def : defs) {
416                                    joiner->addOperand(def->getOperand(0));                                   
417                                }
418                                Assign * const joined = block->createAssign("m", coalesce(joiner));
419                                for (Assign * def : defs) {
420                                    def->replaceWith(joined);
421                                    assert (def->getNumUses() == 0);
422                                }
423                            }
424                        }
425                        --i;
426                    }
427                    break;
428                }
429                if (invalid) {
430                    break;
431                }
432            }
433        }
434    }
435}
436
437/** ------------------------------------------------------------------------------------------------------------- *
438 * @brief tryToPartiallyExtractVariadic
439 ** ------------------------------------------------------------------------------------------------------------- */
440void CoalesceDFG::tryToPartiallyExtractVariadic(PabloBlock * const block) {
441    for (Statement * stmt = block->back(); stmt; stmt = stmt->getPrevNode()) {
442        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
443            tryToPartiallyExtractVariadic(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
444        } else if (isa<Variadic>(stmt)) {
445            tryToPartiallyExtractVariadic(cast<Variadic>(stmt));
446        }
447    }
448}
449
450using ScopeDependencyGraph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
451using ScopeDependencyMap = flat_map<PabloAST *, ScopeDependencyGraph::vertex_descriptor>;
452
453/** ------------------------------------------------------------------------------------------------------------- *
454 * @brief find
455 ** ------------------------------------------------------------------------------------------------------------- */
456inline ScopeDependencyGraph::vertex_descriptor find(PabloAST * expr, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
457    auto f = M.find(expr);
458    if (f == M.end()) {
459        f = M.emplace(expr, add_vertex(expr, G)).first;
460    }
461    return f->second;
462}
463
464/** ------------------------------------------------------------------------------------------------------------- *
465 * @brief buildScopeDependencyGraph
466 ** ------------------------------------------------------------------------------------------------------------- */
467ScopeDependencyGraph::vertex_descriptor buildScopeDependencyGraph(Variadic * const var, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
468    auto f = M.find(var);
469    if (f != M.end()) {
470        return f->second;
471    }
472    auto u = add_vertex(var, G);
473    M.emplace(var, u);
474    for (unsigned i = 0; i != var->getNumOperands(); ++i) {
475        PabloAST * expr = var->getOperand(i);
476        PabloAST * value = var;
477        while (isa<Assign>(expr)) {           
478            value = expr;
479            expr = cast<Assign>(expr)->getExpression();
480        }
481        if ((expr->getClassTypeId() == var->getClassTypeId()) && (expr->getNumUses() == 1)) {
482            const auto v = find(value, G, M);
483            add_edge(v, u, G);
484            add_edge(buildScopeDependencyGraph(cast<Variadic>(expr), G, M), v, G);
485        }
486    }
487    return u;
488}
489
490/** ------------------------------------------------------------------------------------------------------------- *
491 * @brief analyzeScopeDependencies
492 ** ------------------------------------------------------------------------------------------------------------- */
493inline void analyzeScopeDependencies(Assign * const def, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
494    if (LLVM_LIKELY(isa<Variadic>(def->getExpression()))) {
495        buildScopeDependencyGraph(cast<Variadic>(def->getExpression()), G, M);
496    }
497}
498
499/** ------------------------------------------------------------------------------------------------------------- *
500 * @brief analyzeScopeDependencies
501 ** ------------------------------------------------------------------------------------------------------------- */
502void analyzeScopeDependencies(PabloBlock * const block, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
503    for (Statement * stmt : *block) {
504        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
505            analyzeScopeDependencies(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), G, M);
506        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
507            analyzeScopeDependencies(cast<Assign>(stmt), G, M);
508        }
509    }
510}
511
512/** ------------------------------------------------------------------------------------------------------------- *
513 * @brief removeDependenciesWithUnresolvedUses
514 ** ------------------------------------------------------------------------------------------------------------- */
515void removeDependenciesWithUnresolvedUses(ScopeDependencyGraph & G) {
516    for (auto u : make_iterator_range(vertices(G))) {
517        const PabloAST * const expr = G[u];
518        unsigned uses = 0;
519        if (isa<Assign>(expr)) {
520            for (const PabloAST * user : cast<Assign>(expr)->users()) {
521                if (!isa<If>(user) || cast<If>(user)->getCondition() == expr) {
522                    ++uses;
523                }
524            }
525        } else {
526            uses = expr->getNumUses();
527        }
528        if (uses != out_degree(u, G)) {
529            clear_out_edges(u, G);
530        }
531    }
532}
533
534/** ------------------------------------------------------------------------------------------------------------- *
535 * @brief eliminateUnecessaryDependencies
536 ** ------------------------------------------------------------------------------------------------------------- */
537void eliminateUnecessaryDependencies(ScopeDependencyGraph & G) {
538    using Vertex = ScopeDependencyGraph::vertex_descriptor;
539    std::vector<bool> visited(num_vertices(G), false);
540    std::queue<Vertex> Q;
541    for (auto u : make_iterator_range(vertices(G))) {
542        if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
543            Q.push(u);
544        }
545    }
546    while (Q.size() > 0) {
547        const auto u = Q.front(); Q.pop();
548        visited[u] = true;
549        for (auto e : make_iterator_range(in_edges(u, G))) {
550            bool usersHaveBeenVisited = true;
551            const auto v = source(e, G);
552            for (auto e : make_iterator_range(out_edges(v, G))) {
553                if (visited[target(e, G)] == 0) {
554                    usersHaveBeenVisited = false;
555                    break;
556                }
557            }
558            if (usersHaveBeenVisited) {
559                Q.push(v);
560                for (auto e : make_iterator_range(in_edges(u, G))) {
561                    const auto w = source(e, G);
562                    if (w != v) {
563                        auto f = add_edge(w, v, G);
564                        if (f.second == 0) {
565                            cast<Variadic>(G[v])->deleteOperand(G[w]);
566                        }
567                    }
568                }
569            }
570        }
571    }
572}
573
574/** ------------------------------------------------------------------------------------------------------------- *
575 * @brief removeFalseScopeDependencies
576 *
577 * After coalescing the AST, we may find that a result of some If statement is added to a result of a subsequent
578 * If statement. Unless necessary for correctness, eliminate it as we can potentially schedule the If nodes
579 * better without the sequential dependency.
580 *
581 * TODO: make this only iterate over the scope blocks and test the scope branch.
582 ** ------------------------------------------------------------------------------------------------------------- */
583inline void CoalesceDFG::removeFalseScopeDependencies(PabloFunction & function) {
584    ScopeDependencyGraph G;
585    {
586        ScopeDependencyMap M;
587        analyzeScopeDependencies(function.getEntryBlock(), G, M);
588    }
589    removeDependenciesWithUnresolvedUses(G);
590    eliminateUnecessaryDependencies(G);
591}
592
593/** ------------------------------------------------------------------------------------------------------------- *
594 * @brief transform
595 ** ------------------------------------------------------------------------------------------------------------- */
596void CoalesceDFG::transform(PabloFunction & function) {
597
598    CoalesceDFG::coalesce(function.getEntryBlock(), true);
599    #ifndef NDEBUG
600    PabloVerifier::verify(function, "post-coalescence");
601    #endif
602
603    Simplifier::optimize(function);
604
605//    CoalesceDFG::deMorgansReduction(function.getEntryBlock(), true);
606//    #ifndef NDEBUG
607//    PabloVerifier::verify(function, "post-demorgans-reduction");
608//    #endif
609
610//    Simplifier::optimize(function);
611
612    CoalesceDFG::removeFalseScopeDependencies(function);
613    #ifndef NDEBUG
614    PabloVerifier::verify(function, "post-remove-false-scope-dependencies");
615    #endif
616
617    Simplifier::optimize(function);
618
619    CoalesceDFG::tryToPartiallyExtractVariadic(function.getEntryBlock());
620    #ifndef NDEBUG
621    PabloVerifier::verify(function, "post-partial-variadic-extraction");
622    #endif
623
624    Simplifier::optimize(function);
625
626
627}
628
629}
Note: See TracBrowser for help on using the repository browser.