Changeset 4754 for icGREP


Ignore:
Timestamp:
Aug 31, 2015, 4:22:53 PM (4 years ago)
Author:
nmedfort
Message:

Start of work on applying the distribution law to the AST.

Location:
icGREP/icgrep-devel/icgrep
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/generate_predefined_ucd_functions.cpp

    r4753 r4754  
    1818#ifdef ENABLE_MULTIPLEXING
    1919#include <pablo/optimizers/pablo_automultiplexing.hpp>
    20 #include <pablo/optimizers/booleanreassociationpass.h>
    21 #include <pablo/optimizers/pablo_bddminimization.h>
    2220#endif
    2321#include <llvm/IR/Verifier.h>
     
    275273            (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function->getEntryBlock());
    276274        }
    277         BDDMinimizationPass::optimize(*function);
    278         // AutoMultiplexing::optimize(*function);
    279         BooleanReassociationPass::optimize(*function);
    280         BDDMinimizationPass::optimize(*function);
     275        AutoMultiplexing::optimize(*function);
    281276        if (MultiplexingDistributionFile) {
    282277            (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function->getEntryBlock()) << '\n';
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4753 r4754  
    1616namespace pablo {
    1717
    18 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     18using Graph = BooleanReassociationPass::Graph;
    1919using Vertex = Graph::vertex_descriptor;
    2020using VertexQueue = circular_buffer<Vertex>;
     
    2222using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
    2323
    24 static void redistributeAST(Graph & G);
     24static void redistributeAST(PabloBlock &block, Graph & G);
    2525
    2626/** ------------------------------------------------------------------------------------------------------------- *
     
    202202
    203203/** ------------------------------------------------------------------------------------------------------------- *
    204  * @brief processScope
    205  ** ------------------------------------------------------------------------------------------------------------- */
    206 void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
    207 
    208     Graph G;
    209     summarizeAST(block, std::move(terminals), G);
    210     redistributeAST(G);
    211 
     204 * @brief printGraph
     205 ** ------------------------------------------------------------------------------------------------------------- */
     206static void printGraph(PabloBlock & block, const Graph & G) {
    212207    raw_os_ostream out(std::cerr);
    213208    out << "digraph G {\n";
     
    217212        if (isa<Statement>(expr)) {
    218213            if (LLVM_UNLIKELY(isa<If>(expr))) {
    219                 out << "if ";
     214                out << "If ";
    220215                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
    221216                out << ":";
    222217            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
    223                 out << "while ";
     218                out << "While ";
    224219                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
    225220                out << ":";
     
    258253    out << "}\n\n";
    259254    out.flush();
    260 
    261 
    262 
    263 
     255}
     256
     257/** ------------------------------------------------------------------------------------------------------------- *
     258 * @brief processScope
     259 ** ------------------------------------------------------------------------------------------------------------- */
     260void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
     261
     262    Graph G;
     263    summarizeAST(block, std::move(terminals), G);
     264    redistributeAST(block, G);
     265
     266
     267
     268
     269    printGraph(block, G);
    264270
    265271}
     
    541547 * Apply the distribution law to reduce computations whenever possible.
    542548 ** ------------------------------------------------------------------------------------------------------------- */
    543 static void redistributeAST(Graph & G) {
     549static void redistributeAST(PabloBlock & block, Graph & G) {
     550    using TypeId = PabloAST::ClassTypeId;
     551
     552    // Process the graph in reverse topological order so that we end up recursively applying the distribution law
     553    // to the entire AST.
     554    std::vector<unsigned> ordering;
     555    ordering.reserve(num_vertices(G));
     556    topological_sort(G, std::back_inserter(ordering));
     557
     558    for (const Vertex u : ordering) {
     559        const TypeId outerTypeId = G[u]->getClassTypeId();
     560        if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
     561            if (inCurrentBlock(cast<Statement>(G[u]), block)) {
     562                const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
     563
     564                Graph H;
     565                Map M;
     566
     567                flat_set<Vertex> distributable;
     568
     569                for (auto e : make_iterator_range(in_edges(u, G))) {
     570                    const Vertex v = source(e, G);
     571                    if (G[v]->getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block)) {
     572                        bool safe = true;
     573                        // This operation is safe to transform if all of its users are AND or OR instructions.
     574                        if (out_degree(v, G) > 1) {
     575                            for (auto e : make_iterator_range(out_edges(v, G))) {
     576                                const PabloAST * expr = G[target(e, G)];
     577                                if (expr->getClassTypeId() != TypeId::And && expr->getClassTypeId() != TypeId::Or) {
     578                                    safe = false;
     579                                    break;
     580                                }
     581                            }
     582                        }
     583                        if (safe) {
     584                            distributable.insert(v);
     585                        }
     586                    }
     587                }
     588
     589                if (distributable.size() > 1) {
     590                    flat_map<Vertex, unsigned> sources;
     591                    bool canRedistribute = false;
     592                    for (const Vertex v : distributable) {
     593                        for (auto e : make_iterator_range(in_edges(v, G))) {
     594                            const Vertex w = source(e, G);
     595                            const auto f = sources.find(w);
     596                            if (f == sources.end()) {
     597                                sources.emplace(w, 1);
     598                            } else {
     599                                f->second += 1;
     600                                canRedistribute = true;
     601                            }
     602                        }
     603                    }
     604                    if (canRedistribute) {
     605                        Vertex w = 0;
     606                        unsigned count = 0;
     607                        const Vertex x = getVertex(G[u], H, M);
     608                        for (auto s : sources) {
     609                            std::tie(w, count) = s;
     610                            if (count > 1) {
     611                                const Vertex z = getVertex(G[w], H, M);
     612                                for (auto e : make_iterator_range(out_edges(w, G))) {
     613                                    const Vertex v = target(e, G);
     614                                    if (distributable.count(v)) {
     615                                        const Vertex y = getVertex(G[v], H, M);
     616                                        add_edge(y, x, H);
     617                                        add_edge(z, y, H);
     618                                    }
     619                                }
     620                            }
     621                        }
     622                    }
     623                }
     624
     625                printGraph(block, H);
     626            }
     627        }
     628    }
     629
     630
     631
     632
    544633
    545634}
     
    548637 * @brief applyDistributionLaw
    549638 ** ------------------------------------------------------------------------------------------------------------- */
    550 BooleanReassociationPass::BooleanReassociationPass()
    551 {
    552 
    553 }
    554 
    555 
    556 }
     639BooleanReassociationPass::BooleanReassociationPass() { }
     640
     641
     642}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4753 r4754  
    99
    1010class BooleanReassociationPass {
     11public:
    1112    using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *>;
    12 public:
     13
    1314    static bool optimize(PabloFunction & function);
    1415protected:
Note: See TracChangeset for help on using the changeset viewer.