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

Last change on this file since 5124 was 5081, checked in by cameron, 3 years ago

Some changes recommended by cppcheck

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