source: icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp @ 4767

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

Work on reassociation pass

File size: 27.8 KB
Line 
1#include "booleanreassociationpass.h"
2#include <boost/container/flat_set.hpp>
3#include <boost/container/flat_map.hpp>
4#include <boost/circular_buffer.hpp>
5#include <boost/graph/adjacency_list.hpp>
6#include <boost/graph/filtered_graph.hpp>
7#include <boost/graph/topological_sort.hpp>
8#include <boost/graph/strong_components.hpp>
9#include <pablo/optimizers/pablo_simplifier.hpp>
10#include <pablo/analysis/pabloverifier.hpp>
11#include <algorithm>
12#include <queue>
13#include <set>
14#include <iostream>
15#include <pablo/printer_pablos.h>
16#include "graph-facade.hpp"
17
18using namespace boost;
19using namespace boost::container;
20
21namespace pablo {
22
23using Graph = BooleanReassociationPass::Graph;
24using Vertex = Graph::vertex_descriptor;
25using VertexQueue = circular_buffer<Vertex>;
26using Map = BooleanReassociationPass::Map;
27using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
28using TypeId = PabloAST::ClassTypeId;
29using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
30using DistributionMap = flat_map<Graph::vertex_descriptor, DistributionGraph::vertex_descriptor>;
31using VertexSet = std::vector<Vertex>;
32using VertexSets = std::vector<VertexSet>;
33using Biclique = std::pair<VertexSet, VertexSet>;
34using BicliqueSet = std::vector<Biclique>;
35using DistributionSet = std::tuple<std::vector<Vertex>, std::vector<Vertex>, std::vector<Vertex>>;
36using DistributionSets = std::vector<DistributionSet>;
37
38template <class Graph>
39static VertexSet incomingVertexSet(const Vertex u, const Graph & G) {
40    VertexSet V;
41    V.reserve(G.in_degree(u));
42    for (auto e : make_iterator_range(G.in_edges(u))) {
43        V.push_back(G.source(e));
44    }
45    std::sort(V.begin(), V.end());
46    return std::move(V);
47}
48
49template <class Graph>
50static VertexSet outgoingVertexSet(const Vertex u, const Graph & G) {
51    VertexSet V;
52    V.reserve(G.out_degree(u));
53    for (auto e : make_iterator_range(G.out_edges(u))) {
54        V.push_back(G.target(e));
55    }
56    std::sort(V.begin(), V.end());
57    return std::move(V);
58}
59
60template <class Graph>
61static VertexSet sinks(const Graph & G) {
62    VertexSet V;
63    for (const Vertex u : make_iterator_range(vertices(G))) {
64        if (out_degree(u, G) == 0) {
65            V.push_back(u);
66        }
67    }
68    std::sort(V.begin(), V.end());
69    return std::move(V);
70}
71
72/** ------------------------------------------------------------------------------------------------------------- *
73 * @brief optimize
74 ** ------------------------------------------------------------------------------------------------------------- */
75bool BooleanReassociationPass::optimize(PabloFunction & function) {
76    BooleanReassociationPass brp;
77    brp.resolveScopes(function);
78    brp.processScopes(function);
79    Simplifier::optimize(function);
80    return true;
81}
82
83/** ------------------------------------------------------------------------------------------------------------- *
84 * @brief resolveScopes
85 ** ------------------------------------------------------------------------------------------------------------- */
86inline void BooleanReassociationPass::resolveScopes(PabloFunction &function) {
87    mResolvedScopes.emplace(&function.getEntryBlock(), nullptr);
88    resolveScopes(function.getEntryBlock());
89}
90
91/** ------------------------------------------------------------------------------------------------------------- *
92 * @brief resolveScopes
93 ** ------------------------------------------------------------------------------------------------------------- */
94void BooleanReassociationPass::resolveScopes(PabloBlock & block) {
95    for (Statement * stmt : block) {
96        if (isa<If>(stmt) || isa<While>(stmt)) {
97            PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
98            mResolvedScopes.emplace(&nested, stmt);
99            resolveScopes(nested);
100        }
101    }
102}
103
104/** ------------------------------------------------------------------------------------------------------------- *
105 * @brief processScopes
106 ** ------------------------------------------------------------------------------------------------------------- */
107inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
108    processScopes(function, function.getEntryBlock());
109}
110
111/** ------------------------------------------------------------------------------------------------------------- *
112 * @brief processScopes
113 ** ------------------------------------------------------------------------------------------------------------- */
114void BooleanReassociationPass::processScopes(PabloFunction & function, PabloBlock & block) {
115    for (Statement * stmt : block) {
116        if (isa<If>(stmt)) {
117            processScopes(function, cast<If>(stmt)->getBody());
118        } else if (isa<While>(stmt)) {
119            processScopes(function, cast<While>(stmt)->getBody());
120        }
121    }
122    processScope(function, block);
123}
124
125/** ------------------------------------------------------------------------------------------------------------- *
126 * @brief isOptimizable
127 *
128 * And, Or and Xor instructions are all associative, commutative and distributive operations. Thus we can
129 * safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
130 ** ------------------------------------------------------------------------------------------------------------- */
131static inline bool isOptimizable(const PabloAST * const expr) {
132    assert (expr);
133    switch (expr->getClassTypeId()) {
134        case PabloAST::ClassTypeId::And:
135        case PabloAST::ClassTypeId::Or:
136        case PabloAST::ClassTypeId::Xor:
137            return true;
138        default:
139            return false;
140    }
141}
142
143/** ------------------------------------------------------------------------------------------------------------- *
144 * @brief inCurrentBlock
145 ** ------------------------------------------------------------------------------------------------------------- */
146static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
147    return stmt->getParent() == &block;
148}
149
150static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
151    return isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block);
152}
153
154/** ------------------------------------------------------------------------------------------------------------- *
155 * @brief getVertex
156 ** ------------------------------------------------------------------------------------------------------------- */
157template<typename ValueType, typename GraphType, typename MapType>
158static inline Vertex getVertex(const ValueType value, GraphType & G, MapType & M) {
159    const auto f = M.find(value);
160    if (f != M.end()) {
161        return f->second;
162    }
163    const auto u = add_vertex(value, G);
164    M.insert(std::make_pair(value, u));
165    return u;
166}
167
168/** ------------------------------------------------------------------------------------------------------------- *
169 * @brief createTree
170 ** ------------------------------------------------------------------------------------------------------------- */
171static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) {
172    assert (Q.size() > 0);
173    while (Q.size() > 1) {
174        PabloAST * e1 = Q.front(); Q.pop_front();
175        PabloAST * e2 = Q.front(); Q.pop_front();
176        PabloAST * expr = nullptr;
177        // Note: this switch ought to compile to an array of function pointers to the appropriate method.
178        switch (typeId) {
179            case PabloAST::ClassTypeId::And:
180                expr = block.createAnd(e1, e2); break;
181            case PabloAST::ClassTypeId::Or:
182                expr = block.createOr(e1, e2); break;
183            case PabloAST::ClassTypeId::Xor:
184                expr = block.createXor(e1, e2); break;
185            default: break;
186        }
187        Q.push_back(expr);
188    }
189    PabloAST * const expr = Q.front();
190    Q.clear();
191    return expr;
192}
193
194/** ------------------------------------------------------------------------------------------------------------- *
195 * @brief processScope
196 ** ------------------------------------------------------------------------------------------------------------- */
197inline void BooleanReassociationPass::processScope(PabloFunction & function, PabloBlock & block) {
198    Graph G;
199
200    summarizeAST(block, G);
201    redistributeAST(block, G);
202
203    circular_buffer<Vertex> Q(num_vertices(G));
204    topological_sort(G, std::front_inserter(Q));
205    circular_buffer<PabloAST *> nodes;
206    block.setInsertPoint(nullptr);
207
208    while (!Q.empty()) {
209        const Vertex u = Q.front();
210        Q.pop_front();
211        PabloAST * expr = G[u];
212        if (LLVM_LIKELY(inCurrentBlock(expr, block))) {
213            if (isOptimizable(expr)) {
214                if (in_degree(u, G) != 0 && out_degree(u, G) != 0) {
215                    if (LLVM_UNLIKELY(nodes.capacity() < in_degree(u, G))) {
216                        nodes.set_capacity(in_degree(u, G));
217                    }
218                    for (auto e : make_iterator_range(in_edges(u, G))) {
219                        nodes.push_back(G[source(e, G)]);
220                    }
221                    G[u] = createTree(block, expr->getClassTypeId(), nodes);
222                    cast<Statement>(expr)->replaceWith(G[u], true, true);
223                    if (LLVM_UNLIKELY(isa<Var>(G[u]))) {
224                        continue;
225                    }
226                    expr = G[u];
227                }
228            }
229            block.insert(cast<Statement>(expr));
230        }
231    }
232    PabloVerifier::verify(function);
233
234}
235
236/** ------------------------------------------------------------------------------------------------------------- *
237 * @brief summarizeAST
238 *
239 * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences
240 * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to
241 * reassociate them in the most efficient way possible.
242 ** ------------------------------------------------------------------------------------------------------------- */
243void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const {
244
245    Map M;
246
247    // Compute the base def-use graph ...
248    for (Statement * stmt : block) {
249        const Vertex u = getVertex(stmt, G, M);
250        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
251            PabloAST * const op = stmt->getOperand(i);
252            if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
253                continue;
254            }
255            add_edge(getVertex(op, G, M), u, G);
256        }
257        if (isa<If>(stmt)) {
258            for (Assign * def : cast<const If>(stmt)->getDefined()) {
259                const Vertex v = getVertex(def, G, M);
260                add_edge(u, v, G);
261                resolveUsages(v, def, block, G, M);
262            }
263        } else if (isa<While>(stmt)) {
264            for (Next * var : cast<const While>(stmt)->getVariants()) {
265                const Vertex v = getVertex(var, G, M);
266                add_edge(u, v, G);
267                resolveUsages(v, var, block, G, M);
268            }
269        } else {
270            resolveUsages(u, stmt, block, G, M);
271        }
272    }
273
274    std::vector<Vertex> ordering;
275    ordering.reserve(num_vertices(G));
276    topological_sort(G, std::back_inserter(ordering));
277
278    for (auto i = ordering.rbegin(); i != ordering.rend(); ++i) {
279        const Vertex u = *i;
280        if (isOptimizable(G[u])) {
281            std::vector<Vertex> removable;
282            for (auto e : make_iterator_range(in_edges(u, G))) {
283                const Vertex v = source(e, G);
284                if (out_degree(v, G) == 1 && in_degree(v, G) != 0 && G[u]->getClassTypeId() == G[v]->getClassTypeId()) {
285                    removable.push_back(v);
286                    for (auto e : make_iterator_range(in_edges(v, G))) {
287                        add_edge(source(e, G), u, G);
288                    }
289                }
290            }
291            for (auto v : removable) {
292                clear_vertex(v, G);
293            }
294        }
295    }
296}
297
298/** ------------------------------------------------------------------------------------------------------------- *
299 * @brief resolveUsages
300 ** ------------------------------------------------------------------------------------------------------------- */
301void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const {
302    for (PabloAST * user : expr->users()) {
303        assert (user);
304        if (LLVM_LIKELY(user != expr && isa<Statement>(user))) {
305            PabloBlock * parent = cast<Statement>(user)->getParent();
306            assert (parent);
307            if (LLVM_UNLIKELY(parent != &block)) {
308                for (;;) {
309                    if (LLVM_UNLIKELY(parent == nullptr)) {
310                        assert (isa<Assign>(expr) || isa<Next>(expr));
311                        break;
312                    } else if (parent->getParent() == &block) {
313                        const auto f = mResolvedScopes.find(parent);
314                        if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
315                            throw std::runtime_error("Failed to resolve scope block!");
316                        }
317                        add_edge(u, getVertex(f->second, G, M), G);
318                        break;
319                    }
320                    parent = parent->getParent();
321                }
322            }
323        }
324    }
325}
326
327/** ------------------------------------------------------------------------------------------------------------- *
328 * @brief enumerateBicliques
329 *
330 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
331 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an in-degree of 0
332 * to be in bipartition A and their adjacencies to be in B.
333  ** ------------------------------------------------------------------------------------------------------------- */
334template <class Graph>
335static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
336    using IntersectionSets = std::set<VertexSet>;
337
338    IntersectionSets B1;
339    for (auto u : A) {
340        B1.insert(std::move(incomingVertexSet(u, G)));
341    }
342
343    IntersectionSets B(B1);
344
345    IntersectionSets Bi;
346
347    VertexSet clique;
348    for (auto i = B1.begin(); i != B1.end(); ++i) {
349        for (auto j = i; ++j != B1.end(); ) {
350            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
351            if (clique.size() > 0) {
352                if (B.count(clique) == 0) {
353                    Bi.insert(clique);
354                }
355                clique.clear();
356            }
357        }
358    }
359
360    for (;;) {
361        if (Bi.empty()) {
362            break;
363        }
364        B.insert(Bi.begin(), Bi.end());
365        IntersectionSets Bk;
366        for (auto i = B1.begin(); i != B1.end(); ++i) {
367            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
368                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
369                if (clique.size() > 0) {
370                    if (B.count(clique) == 0) {
371                        Bk.insert(clique);
372                    }
373                    clique.clear();
374                }
375            }
376        }
377        Bi.swap(Bk);
378    }
379
380    BicliqueSet cliques;
381    cliques.reserve(B.size());
382    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
383        VertexSet Ai(A);
384        for (const Vertex u : *Bi) {
385            VertexSet Aj = outgoingVertexSet(u, G);
386            VertexSet Ak;
387            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
388            Ai.swap(Ak);
389        }
390        cliques.emplace_back(std::move(Ai), std::move(*Bi));
391    }
392    return std::move(cliques);
393}
394
395/** ------------------------------------------------------------------------------------------------------------- *
396 * @brief intersects
397 ** ------------------------------------------------------------------------------------------------------------- */
398template <class Type>
399inline bool intersects(const Type & A, const Type & B) {
400    auto first1 = A.begin(), last1 = A.end();
401    auto first2 = B.begin(), last2 = B.end();
402    while (first1 != last1 && first2 != last2) {
403        if (*first1 < *first2) {
404            ++first1;
405        } else if (*first2 < *first1) {
406            ++first2;
407        } else {
408            return true;
409        }
410    }
411    return false;
412}
413
414/** ------------------------------------------------------------------------------------------------------------- *
415 * @brief independentCliqueSets
416 ** ------------------------------------------------------------------------------------------------------------- */
417template <unsigned side>
418inline static BicliqueSet && independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) {
419    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
420
421    const auto l = cliques.size();
422    IndependentSetGraph I(l);
423
424    // Initialize our weights
425    for (unsigned i = 0; i != l; ++i) {
426        I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
427    }
428
429    // Determine our constraints
430    for (unsigned i = 0; i != l; ++i) {
431        for (unsigned j = i + 1; j != l; ++j) {
432            if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
433                add_edge(i, j, I);
434            }
435        }
436    }
437
438    // Use the greedy algorithm to choose our independent set
439    VertexSet selected;
440    for (;;) {
441        unsigned w = 0;
442        Vertex u = 0;
443        for (unsigned i = 0; i != l; ++i) {
444            if (I[i] > w) {
445                w = I[i];
446                u = i;
447            }
448        }
449        if (w < minimum) break;
450        selected.push_back(u);
451        I[u] = 0;
452        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
453            I[v] = 0;
454        }
455    }
456
457    // Sort the selected list and then remove the unselected cliques
458    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
459    auto end = cliques.end();
460    for (const unsigned offset : selected) {
461        end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
462    }
463    cliques.erase(cliques.begin(), end);
464
465    return std::move(cliques);
466}
467
468/** ------------------------------------------------------------------------------------------------------------- *
469 * @brief removeUnhelpfulBicliques
470 *
471 * An intermediary vertex could have more than one outgoing edge but if any edge is not directed to a vertex in our
472 * biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if there are not
473 * enough vertices in the biclique to make distribution profitable, eliminate the clique.
474 ** ------------------------------------------------------------------------------------------------------------- */
475static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, const Graph & G, DistributionGraph & H) {
476    for (auto ci = cliques.begin(); ci != cliques.end(); ) {
477        const auto cardinalityA = std::get<0>(*ci).size();
478        VertexSet & B = std::get<1>(*ci);
479        for (auto bi = B.begin(); bi != B.end(); ) {
480            if (out_degree(H[*bi], G) == cardinalityA) {
481                ++bi;
482            } else {
483                bi = B.erase(bi);
484            }
485        }
486        if (B.size() > 1) {
487            ++ci;
488        } else {
489            ci = cliques.erase(ci);
490        }
491    }
492    return std::move(cliques);
493}
494
495/** ------------------------------------------------------------------------------------------------------------- *
496 * @brief safeDistributionSets
497 ** ------------------------------------------------------------------------------------------------------------- */
498static DistributionSets safeDistributionSets(const PabloBlock & block, const Graph & G, DistributionGraph & H) {
499    const auto F = makeGraphFacade(H);
500    DistributionSets T;
501    BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(F, sinks(H)), G, H), 1);
502    for (Biclique & lower : lowerSet) {
503        BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(F, std::get<1>(lower)), 2);
504        for (Biclique & upper : upperSet) {
505            T.emplace_back(std::move(std::get<1>(upper)), std::move(std::get<0>(upper)), std::get<0>(lower));
506        }
507    }
508    return std::move(T);
509}
510
511/** ------------------------------------------------------------------------------------------------------------- *
512 * @brief generateDistributionGraph
513 ** ------------------------------------------------------------------------------------------------------------- */
514void generateDistributionGraph(const PabloBlock & block, const Graph & G, DistributionGraph & H) {
515    DistributionMap M;
516    for (const Vertex u : make_iterator_range(vertices(G))) {
517        if (in_degree(u, G) > 0) {
518            const TypeId outerTypeId = G[u]->getClassTypeId();
519            if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
520                if (inCurrentBlock(cast<Statement>(G[u]), block)) {
521                    const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
522                    flat_set<Vertex> distributable;
523                    for (auto e : make_iterator_range(in_edges(u, G))) {
524                        const Vertex v = source(e, G);
525                        if (LLVM_UNLIKELY(G[v]->getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block))) {
526                            bool safe = true;
527                            for (const auto e : make_iterator_range(out_edges(v, G))) {
528                                if (G[target(e, G)]->getClassTypeId() != outerTypeId) {
529                                    safe = false;
530                                    break;
531                                }
532                            }
533                            if (safe) {
534                                distributable.insert(v);
535                            }
536                        }
537                    }
538                    if (LLVM_LIKELY(distributable.size() > 1)) {
539                        // We're only interested in computing a subgraph of G in which every source has an out-degree
540                        // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
541                        // benefit. (Note: this does not consider register pressure / liveness.)
542                        flat_map<Vertex, bool> observedMoreThanOnce;
543                        bool anyOpportunities = false;
544                        for (const Vertex v : distributable) {
545                            for (auto e : make_iterator_range(in_edges(v, G))) {
546                                const Vertex w = source(e, G);
547                                auto ob = observedMoreThanOnce.find(w);
548                                if (ob == observedMoreThanOnce.end()) {
549                                    observedMoreThanOnce.emplace(w, false);
550                                } else {
551                                    ob->second = true;
552                                    anyOpportunities = true;
553                                }
554                            }
555                        }
556                        if (anyOpportunities) {
557                            for (const auto ob : observedMoreThanOnce) {
558                                if (ob.second) {
559                                    const Vertex w = ob.first;
560                                    for (auto e : make_iterator_range(out_edges(w, G))) {
561                                        const Vertex v = target(e, G);
562                                        if (distributable.count(v)) {
563                                            const Vertex y = getVertex(v, H, M);
564                                            add_edge(y, getVertex(u, H, M), H);
565                                            add_edge(getVertex(w, H, M), y, H);
566                                        }
567                                    }
568                                }
569                            }
570                        }
571                    }
572                }
573            }
574        }
575    }
576}
577
578/** ------------------------------------------------------------------------------------------------------------- *
579 * @brief redistributeAST
580 *
581 * Apply the distribution law to reduce computations whenever possible.
582 ** ------------------------------------------------------------------------------------------------------------- */
583bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const {
584    bool anyChanges = false;
585
586    for (;;) {
587
588        DistributionGraph H;
589
590        generateDistributionGraph(block, G, H);
591
592        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
593        if (num_vertices(H) == 0) {
594            break;
595        }
596
597        const DistributionSets distributionSets = safeDistributionSets(block, G, H);
598
599        if (LLVM_UNLIKELY(distributionSets.empty())) {
600            break;
601        }
602
603        for (const DistributionSet & set : distributionSets) {
604            // Each distribution tuple consists of the sources, intermediary, and sink nodes.
605            const VertexSet & sources = std::get<0>(set);
606            const VertexSet & intermediary = std::get<1>(set);
607            const VertexSet & sinks = std::get<2>(set);
608
609            const TypeId outerTypeId = G[H[sinks.front()]]->getClassTypeId();
610            assert (outerTypeId == TypeId::And || outerTypeId == TypeId::Or);
611            const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or;
612
613            // Eliminate the edges from our original graph G
614            for (const Vertex u : intermediary) {
615                const auto x = H[u];
616                assert (G[x]->getClassTypeId() == innerTypeId);
617                for (const Vertex s : sources) {
618                    assert (edge(H[s], x, G).second);
619                    remove_edge(H[s], x, G);
620                }
621                for (const Vertex t : sinks) {
622                    assert (edge(x, H[t], G).second);
623                    assert (G[H[t]]->getClassTypeId() == outerTypeId);
624                    remove_edge(x, H[t], G);
625                }
626            }
627
628            // Update G to match the desired changes
629            const Vertex x = add_vertex(nullptr, G);
630            const Vertex y = add_vertex(nullptr, G);
631            for (const Vertex u : intermediary) {
632                add_edge(H[u], x, G);
633            }
634            for (const Vertex s : sources) {
635                add_edge(H[s], y, G);
636            }
637            for (const Vertex t : sinks) {
638                add_edge(y, H[t], G);
639            }
640            add_edge(x, y, G);
641
642
643            // Now begin transforming the AST (TODO: fix the abstraction so I can defer creation until the final phase)
644            circular_buffer<PabloAST *> Q(std::max(in_degree(x, G), in_degree(y, G)));
645            for (auto e : make_iterator_range(in_edges(x, G))) {
646                Q.push_back(G[source(e, G)]);
647            }
648            G[x] = createTree(block, outerTypeId, Q);
649            for (auto e : make_iterator_range(in_edges(y, G))) {
650                Q.push_back(G[source(e, G)]);
651            }
652            G[y] = createTree(block, innerTypeId, Q);
653
654            // Summarize the graph after transforming G
655            std::vector<Vertex> ordering;
656            ordering.reserve(num_vertices(G));
657            for (const Vertex u : ordering) {
658                if (LLVM_UNLIKELY(out_degree(u, G) == 1 && inCurrentBlock(G[u], block))) {
659                    if (isOptimizable(G[u])) {
660                        const Vertex v = target(*(out_edges(u, G).first), G);
661                        if (LLVM_UNLIKELY(G[v]->getClassTypeId() == G[u]->getClassTypeId())) {
662                            for (auto e : make_iterator_range(in_edges(u, G))) {
663                                assert (source(e, G) != u);
664                                add_edge(source(e, G), v, G);
665                            }
666                            clear_vertex(u, G);
667                        }
668                    }
669                }
670            }
671        }
672        anyChanges = true;
673    }
674    return anyChanges;
675}
676
677}
Note: See TracBrowser for help on using the repository browser.