Ignore:
Timestamp:
Dec 17, 2015, 4:45:18 PM (4 years ago)
Author:
nmedfort
Message:

Work on coalescing algorithm + minor changes.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp

    r4887 r4896  
    11#include "flattenassociativedfg.h"
    2 
    32#include <pablo/codegenstate.h>
    43#include <pablo/optimizers/pablo_simplifier.hpp>
     4#include <pablo/analysis/pabloverifier.hpp>
     5#include <boost/container/flat_set.hpp>
    56#include <boost/container/flat_map.hpp>
    67#include <boost/graph/adjacency_list.hpp>
    7 #include <pablo/analysis/pabloverifier.hpp>
     8
     9#include <pablo/printer_pablos.h>
     10#include <iostream>
    811
    912using namespace boost;
     
    1316
    1417using TypeId = PabloAST::ClassTypeId;
    15 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
    16 using Map = flat_map<PabloAST *, Graph::vertex_descriptor>;
    1718
    1819/** ------------------------------------------------------------------------------------------------------------- *
     
    3031            if (removedVar->getNumOperands() == 1) {
    3132                removedVar->replaceWith(removedVar->getOperand(0));
    32             } else if (removedVar->getNumUsers() == 0) {
     33            } else if (removedVar->getNumUses() == 0) {
    3334                removedVar->eraseFromParent(true);
    3435            }
     
    4647    while (stmt) {
    4748        Statement * next = stmt->getNextNode();
    48         if (traverse && (isa<If>(stmt) || isa<While>(stmt))) {
     49        if (LLVM_UNLIKELY((isa<If>(stmt) || isa<While>(stmt)) && traverse)) {
    4950            coalesce(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), true);
    5051        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
     
    116117
    117118/** ------------------------------------------------------------------------------------------------------------- *
    118  * @brief extractNegationsOutwards
     119 * @brief deMorgansReduction
    119120 ** ------------------------------------------------------------------------------------------------------------- */
    120121inline void FlattenAssociativeDFG::deMorgansReduction(PabloBlock * const block) {
    121122    for (Statement * stmt : *block) {
    122         if (isa<If>(stmt) || isa<While>(stmt)) {
     123        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    123124            deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    124125        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
    125126            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));
    126474        }
    127475    }
     
    146494
    147495    Simplifier::optimize(function);
    148 }
    149 
    150 }
     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 TracChangeset for help on using the changeset viewer.