Ignore:
Timestamp:
Dec 23, 2015, 4:28:42 PM (3 years ago)
Author:
nmedfort
Message:

Work on lowering + minor bug fixes.

File:
1 edited

Legend:

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

    r4896 r4899  
    66#include <boost/container/flat_map.hpp>
    77#include <boost/graph/adjacency_list.hpp>
    8 
    9 #include <pablo/printer_pablos.h>
    10 #include <iostream>
     8#include <queue>
    119
    1210using namespace boost;
     
    119117 * @brief deMorgansReduction
    120118 ** ------------------------------------------------------------------------------------------------------------- */
    121 inline void FlattenAssociativeDFG::deMorgansReduction(PabloBlock * const block) {
     119void FlattenAssociativeDFG::deMorgansReduction(PabloBlock * const block, const bool traverse) {
    122120    for (Statement * stmt : *block) {
    123         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    124             deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     121        if (LLVM_UNLIKELY((isa<If>(stmt) || isa<While>(stmt)) && traverse)) {
     122            deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), true);
    125123        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
    126124            deMorgansReduction(cast<Variadic>(stmt), block);
     
    138136using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, Variadic *>;
    139137using Vertex = Graph::vertex_descriptor;
    140 using Map = flat_map<TypeId, Vertex>;
     138using SourceMap = flat_map<Assign *, Vertex>;
     139using SinkMap = flat_map<TypeId, Vertex>;
    141140using VertexSet = std::vector<Vertex>;
    142141using Biclique = std::pair<VertexSet, VertexSet>;
     
    146145 * @brief addToVariadicGraph
    147146 ** ------------------------------------------------------------------------------------------------------------- */
    148 static 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);
     147static bool addToVariadicGraph(Assign * const def, Graph & G, SourceMap & A, SinkMap & B) {
     148
     149    if (LLVM_LIKELY(A.count(def) == 0)) {
     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                    if (LLVM_LIKELY(cast<If>(user)->getCondition() != def)) {
     155                        continue;
     156                    }
     157                }
     158                return false;
     159            }
     160        }
     161
     162        // Add the statement and its users to G
     163        const Vertex u = add_vertex(VertexData(def), G);
     164        A.emplace(def, u);
     165        for (PabloAST * user : def->users()) {
     166            if (isa<Variadic>(user)) {
     167                auto f = B.find(user->getClassTypeId());
     168                if (f == B.end()) {
     169                    f = B.emplace(user->getClassTypeId(), add_vertex(VertexData(user->getClassTypeId()), G)).first;
     170                }
     171                assert (f != B.end());
     172                G[add_edge(u, f->second, G).first] = cast<Variadic>(user);
     173            }
    174174        }
    175175    }
     
    342342 * @brief tryToPartiallyExtractVariadic
    343343 ** ------------------------------------------------------------------------------------------------------------- */
    344 void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
     344inline void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
    345345
    346346    for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    347347        PabloAST * const op = var->getOperand(i);
    348348        if (isa<Assign>(op)) {
     349
    349350            // Have we found a variadic operation that can sunk into a nested scope?
    350351            for (unsigned j = i + 1; j != var->getNumOperands(); ++j) {
     
    352353                if (LLVM_UNLIKELY(matches(op, var->getOperand(j)))) {
    353354                    Graph G;
    354                     Map M;
    355                     VertexSet A;
    356                     if (addToVariadicGraph(cast<Assign>(op), G, M, A) == 0) {
     355                    SourceMap A;
     356                    SinkMap B;
     357                    if (addToVariadicGraph(cast<Assign>(op), G, A, B) == 0) {
    357358                        invalid = true;
    358359                        break;
    359360                    }
    360                     addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, M, A);
     361                    addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, A, B);
    361362                    for (++j; j != var->getNumOperands(); ++j) {
    362363                        if (LLVM_UNLIKELY(matches(op, var->getOperand(j)))) {
    363                             addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, M, A);
     364                            addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, A, B);
    364365                        }
    365366                    }
     367
    366368                    if (A.size() > 1) {
    367                         const auto S = independentCliqueSets<0>(std::move(enumerateBicliques(G, A)), 2);
     369
     370                        VertexSet H;
     371                        H.reserve(A.size());
     372                        for (auto a : A) {
     373                            H.push_back(a.second);
     374                        }
     375
     376                        const auto S = independentCliqueSets<0>(std::move(enumerateBicliques(G, H)), 2);
     377                        assert (S.size() > 0);
    368378                        for (const Biclique & C : S) {
    369379                            const VertexSet & sources = std::get<0>(C);
    370380                            const VertexSet & variadics = std::get<1>(C);
     381                            assert (variadics.size() > 0);
     382                            assert (sources.size() > variadics.size());
    371383                            PabloBlock * const block = cast<Assign>(op)->getParent();
    372384                            block->setInsertPoint(block->back());
     
    383395                                        joiner = block->createXor(sources.size());
    384396                                        break;
    385                                     default:
    386                                         break;
     397                                    default: llvm_unreachable("Unexpected!");
    387398                                }
    388399                                assert (joiner);
    389                                 flat_set<Variadic *> vars;
     400                                flat_set<Assign *> defs;
    390401                                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                                    defs.insert(G[u].def);
    402403                                }
     404                                for (Assign * def : defs) {
     405                                    joiner->addOperand(def->getOperand(0));                                   
     406                                }
     407
    403408                                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);
     409                                Assign * const joined = block->createAssign("m", joiner);
     410
     411                                for (Assign * def : defs) {
     412                                    def->replaceWith(joined);
     413                                    assert (def->getNumUses() == 0);
    408414                                }
    409415                            }
    410416                        }
     417                        --i;
    411418                    }
    412419                    break;
     
    421428
    422429/** ------------------------------------------------------------------------------------------------------------- *
    423  * @brief removeFalseScopeDependencies
    424  ** ------------------------------------------------------------------------------------------------------------- */
    425 inline 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                             }
     430 * @brief tryToPartiallyExtractVariadic
     431 ** ------------------------------------------------------------------------------------------------------------- */
     432void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(PabloBlock * const block) {
     433    for (Statement * stmt = block->back(); stmt; stmt = stmt->getPrevNode()) {
     434        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     435            tryToPartiallyExtractVariadic(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     436        } else if (isa<Variadic>(stmt)) {
     437            tryToPartiallyExtractVariadic(cast<Variadic>(stmt));
     438        }
     439    }
     440}
     441
     442using ScopeDependencyGraph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     443using ScopeDependencyMap = flat_map<PabloAST *, ScopeDependencyGraph::vertex_descriptor>;
     444
     445/** ------------------------------------------------------------------------------------------------------------- *
     446 * @brief find
     447 ** ------------------------------------------------------------------------------------------------------------- */
     448inline ScopeDependencyGraph::vertex_descriptor find(PabloAST * expr, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     449    auto f = M.find(expr);
     450    if (f == M.end()) {
     451        f = M.emplace(expr, add_vertex(expr, G)).first;
     452    }
     453    return f->second;
     454}
     455
     456/** ------------------------------------------------------------------------------------------------------------- *
     457 * @brief buildScopeDependencyGraph
     458 ** ------------------------------------------------------------------------------------------------------------- */
     459ScopeDependencyGraph::vertex_descriptor buildScopeDependencyGraph(Variadic * const var, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     460    auto f = M.find(var);
     461    if (f != M.end()) {
     462        return f->second;
     463    }
     464    auto u = add_vertex(var, G);
     465    M.emplace(var, u);
     466    for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     467        PabloAST * expr = var->getOperand(i);
     468        PabloAST * value = var;
     469        while (isa<Assign>(expr)) {           
     470            value = expr;
     471            expr = cast<Assign>(expr)->getExpression();
     472        }
     473        if ((expr->getClassTypeId() == var->getClassTypeId()) && (expr->getNumUses() == 1)) {
     474            const auto v = find(value, G, M);
     475            add_edge(v, u, G);
     476            add_edge(buildScopeDependencyGraph(cast<Variadic>(expr), G, M), v, G);
     477        }
     478    }
     479    return u;
     480}
     481
     482/** ------------------------------------------------------------------------------------------------------------- *
     483 * @brief analyzeScopeDependencies
     484 ** ------------------------------------------------------------------------------------------------------------- */
     485inline void analyzeScopeDependencies(Assign * const def, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     486    if (LLVM_LIKELY(isa<Variadic>(def->getExpression()))) {
     487        buildScopeDependencyGraph(cast<Variadic>(def->getExpression()), G, M);
     488    }
     489}
     490
     491/** ------------------------------------------------------------------------------------------------------------- *
     492 * @brief analyzeScopeDependencies
     493 ** ------------------------------------------------------------------------------------------------------------- */
     494void analyzeScopeDependencies(PabloBlock * const block, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     495    for (Statement * stmt : *block) {
     496        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     497            analyzeScopeDependencies(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), G, M);
     498        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     499            analyzeScopeDependencies(cast<Assign>(stmt), G, M);
     500        }
     501    }
     502}
     503
     504/** ------------------------------------------------------------------------------------------------------------- *
     505 * @brief removeDependenciesWithUnresolvedUses
     506 ** ------------------------------------------------------------------------------------------------------------- */
     507void removeDependenciesWithUnresolvedUses(ScopeDependencyGraph & G) {
     508    for (auto u : make_iterator_range(vertices(G))) {
     509        const PabloAST * const expr = G[u];
     510        unsigned uses = 0;
     511        if (isa<Assign>(expr)) {
     512            for (const PabloAST * user : cast<Assign>(expr)->users()) {
     513                if (!isa<If>(user) || cast<If>(user)->getCondition() == expr) {
     514                    ++uses;
     515                }
     516            }
     517        } else {
     518            uses = expr->getNumUses();
     519        }
     520        if (uses != out_degree(u, G)) {
     521            clear_out_edges(u, G);
     522        }
     523    }
     524}
     525
     526/** ------------------------------------------------------------------------------------------------------------- *
     527 * @brief eliminateUnecessaryDependencies
     528 ** ------------------------------------------------------------------------------------------------------------- */
     529void eliminateUnecessaryDependencies(ScopeDependencyGraph & G) {
     530    using Vertex = ScopeDependencyGraph::vertex_descriptor;
     531    std::vector<bool> visited(num_vertices(G), false);
     532    std::queue<Vertex> Q;
     533    for (auto u : make_iterator_range(vertices(G))) {
     534        if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     535            Q.push(u);
     536        }
     537    }
     538    while (Q.size() > 0) {
     539        const auto u = Q.front(); Q.pop();
     540        visited[u] = true;
     541        for (auto e : make_iterator_range(in_edges(u, G))) {
     542            bool usersHaveBeenVisited = true;
     543            const auto v = source(e, G);
     544            for (auto e : make_iterator_range(out_edges(v, G))) {
     545                if (visited[target(e, G)] == 0) {
     546                    usersHaveBeenVisited = false;
     547                    break;
     548                }
     549            }
     550            if (usersHaveBeenVisited) {
     551                Q.push(v);
     552                for (auto e : make_iterator_range(in_edges(u, G))) {
     553                    const auto w = source(e, G);
     554                    if (w != v) {
     555                        auto f = add_edge(w, v, G);
     556                        if (f.second == 0) {
     557                            cast<Variadic>(G[v])->deleteOperand(G[w]);
    451558                        }
    452559                    }
     
    463570 * If statement. Unless necessary for correctness, eliminate it as we can potentially schedule the If nodes
    464571 * better without the sequential dependency.
    465  ** ------------------------------------------------------------------------------------------------------------- */
    466 void FlattenAssociativeDFG::removeFalseScopeDependencies(PabloBlock * const block) {
    467     for (Statement * stmt = block->back(); stmt; stmt = stmt->getPrevNode()) {
    468         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    469             removeFalseScopeDependencies(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    470         } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
    471             removeFalseScopeDependencies(cast<Assign>(stmt));
    472         } else if (isa<Variadic>(stmt)) {
    473             tryToPartiallyExtractVariadic(cast<Variadic>(stmt));
    474         }
    475     }
     572 *
     573 * TODO: make this only iterate over the scope blocks and test the scope branch.
     574 ** ------------------------------------------------------------------------------------------------------------- */
     575inline void FlattenAssociativeDFG::removeFalseScopeDependencies(PabloFunction & function) {
     576    ScopeDependencyGraph G;
     577    {
     578        ScopeDependencyMap M;
     579        analyzeScopeDependencies(function.getEntryBlock(), G, M);
     580    }
     581    removeDependenciesWithUnresolvedUses(G);
     582    eliminateUnecessaryDependencies(G);
    476583}
    477584
     
    488595    Simplifier::optimize(function);
    489596
    490     FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock());
     597    FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock(), true);
    491598    #ifndef NDEBUG
    492599    PabloVerifier::verify(function, "post-demorgans-reduction");
     
    495602    Simplifier::optimize(function);
    496603
    497     FlattenAssociativeDFG::removeFalseScopeDependencies(function.getEntryBlock());
     604    FlattenAssociativeDFG::removeFalseScopeDependencies(function);
    498605    #ifndef NDEBUG
    499606    PabloVerifier::verify(function, "post-remove-false-scope-dependencies");
    500607    #endif
    501608
     609    FlattenAssociativeDFG::tryToPartiallyExtractVariadic(function.getEntryBlock());
     610    #ifndef NDEBUG
     611    PabloVerifier::verify(function, "post-partial-variadic-extraction");
     612    #endif
     613
    502614    Simplifier::optimize(function);
    503 }
    504 
    505 }
     615
     616
     617}
     618
     619}
Note: See TracChangeset for help on using the changeset viewer.