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

Work on coalescing algorithm + minor changes.

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
2 added
5 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.cpp

    r4870 r4896  
    11#include "codemotionpass.h"
    2 #include <pablo/function.h>
    3 #include <pablo/ps_while.h>
     2#include <pablo/codegenstate.h>
    43#include <pablo/analysis/pabloverifier.hpp>
    5 #ifdef USE_BOOST
    64#include <boost/container/flat_set.hpp>
    7 #else
    8 #include <unordered_set>
    9 #endif
    10 #include <pablo/printer_pablos.h>
    11 #include <iostream>
     5
     6using namespace boost;
     7using namespace boost::container;
    128
    139namespace pablo {
    14 
    15 #ifdef USE_BOOST
    16 using LoopVariants = boost::container::flat_set<const PabloAST *>;
    17 #else
    18 using LoopVariants = std::unordered_set<const PabloAST *>;
    19 #endif
    2010
    2111/** ------------------------------------------------------------------------------------------------------------- *
     
    7161 ** ------------------------------------------------------------------------------------------------------------- */
    7262template <class ScopeSet>
    73 inline bool findScopeUsages(Statement * stmt, ScopeSet & scopeSet, const PabloBlock * const block, const PabloBlock * const ignored = nullptr) {
     63inline bool findScopeUsages(Statement * stmt, ScopeSet & scopeSet, const PabloBlock * const block, const PabloBlock * const blocker) {
    7464    for (PabloAST * use : stmt->users()) {
    7565        assert (isa<Statement>(use));
     
    7868            return false;
    7969        }
    80         if (parent != ignored) {
     70        if (parent != blocker) {
    8171            scopeSet.insert(parent);
    8272        }
     
    10595        }
    10696    } else if (isSafeToMove(stmt)) {
    107         return findScopeUsages(stmt, scopeSet, block);
     97        return findScopeUsages(stmt, scopeSet, block, nullptr);
    10898    }
    10999    return false;
     
    166156 ** ------------------------------------------------------------------------------------------------------------- */
    167157void CodeMotionPass::hoistLoopInvariants(While * loop) {
    168     LoopVariants loopVariants;
     158    flat_set<const PabloAST *> loopVariants;
    169159    for (Next * variant : loop->getVariants()) {
    170160        loopVariants.insert(variant);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.h

    r4870 r4896  
    22#define PABLO_CODESINKING_HPP
    33
    4 #include <pablo/codegenstate.h>
    54#include <vector>
    65#include <algorithm>
     
    98
    109class PabloFunction;
     10class PabloBlock;
     11class Statement;
     12class While;
     13class Variadic;
    1114
    1215class CodeMotionPass {
     
    1619            if (i == end() || *i != block) {
    1720                std::vector<PabloBlock *>::insert(i, block);
    18                 assert (std::is_sorted(begin(), end()));
    1921                return true;
    2022            }
     
    2628        }
    2729    };
    28 
    2930public:
    3031    static bool optimize(PabloFunction & function);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r4887 r4896  
    270270        VertexSet & B = std::get<1>(*ci);
    271271        for (auto bi = B.begin(); bi != B.end(); ) {
    272             if (G[*bi]->getNumUsers() == cardinalityA) {
     272            if (G[*bi]->getNumUses() == cardinalityA) {
    273273                ++bi;
    274274            } else {
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4890 r4896  
    160160
    161161        RECORD_TIMESTAMP(start_select_independent_sets);
    162         mp.multiplexSelectedIndependentSets(function);
     162        mp.multiplexSelectedSets(function);
    163163        RECORD_TIMESTAMP(end_select_independent_sets);
    164164        LOG("SelectedIndependentSets:  " << (end_select_independent_sets - start_select_independent_sets));
     
    575575 *
    576576 * Note: it'd be preferable to contract vertices in the constraint graph prior to scanning through it but that
    577  * leaves us with a more difficult problem. Namely, an Advance node may belong to more than one clique and we
    578  * want to avoid generating a multiplexing set whose size is 2^n for any n ∈ â„€* but don't want to needlessly
    579  * limit the size of any clique. Look into this further later.
     577 * leaves us with a more difficult problem. Namely, Advance nodes may belong to more than one clique but it'd be
     578 * useless to compute a value twice; furthermore, we want to avoid generating a multiplexing set whose size is 2^n
     579 * for any n ∈ â„€* but don't want to needlessly limit the size of any clique. Look into this further later.
    580580 ** ------------------------------------------------------------------------------------------------------------- */
    581581void MultiplexingPass::generateUsageWeightingGraph() {
     
    588588        for (unsigned j = i + 1; j != n; ++j) {
    589589            const Advance * const advJ = mAdvance[j];
    590             if (LLVM_UNLIKELY(advI->getNumUsers() == advJ->getNumUsers()) && independent(i, j)) {
     590            if (LLVM_UNLIKELY(advI->getNumUses() == advJ->getNumUses()) && independent(i, j)) {
    591591                if (LLVM_UNLIKELY(std::equal(advI->user_begin(), advI->user_end(), advJ->user_begin()))) {
    592592                    // INVESTIGATE: we should be able to ignore subset relations if these are going to become a
     
    614614        }
    615615    }
    616     mUsageWeightingGraph = G;
     616    mUsageGraph = G;
    617617}
    618618
     
    763763 * enough but can be shown to produce a suboptimal solution if there are three candidate sets labelled A, B and C,
    764764 * in which A ∩ B = âˆ
    765 , |A| ≀ |B| < |C| < (|A| + |B|), and C ∩ (A ∪ B) = C.
     765, |A| ≀ |B| < |C|, and C ⊂ (A ∪ B).
    766766 ** ------------------------------------------------------------------------------------------------------------- */
    767767void MultiplexingPass::selectMultiplexSets() {
     
    798798                for (auto ei = begin; ei != end; ++ei) {
    799799                    for (auto ej = ei; ++ej != end; ) {
    800                         if (edge(target(*ei, mMultiplexSetGraph), target(*ej, mMultiplexSetGraph), mUsageWeightingGraph).second) {
     800                        if (edge(target(*ei, mMultiplexSetGraph), target(*ej, mMultiplexSetGraph), mUsageGraph).second) {
    801801                            ++r;
    802802                        }
     
    901901
    902902        // At least one subset constraint exists; perform a transitive reduction on the graph to ensure that
    903         // we perform the minimum number of AST modifications for the given multiplexing sets.
     903        // we perform the minimum number of AST modifications for the selected multiplexing sets.
    904904
    905905        doTransitiveReductionOfSubsetGraph();
     
    921921
    922922/** ------------------------------------------------------------------------------------------------------------- *
    923  * @brief multiplexSelectedIndependentSets
    924  ** ------------------------------------------------------------------------------------------------------------- */
    925 void MultiplexingPass::multiplexSelectedIndependentSets(PabloFunction &) {
     923 * @brief multiplexSelectedSets
     924 ** ------------------------------------------------------------------------------------------------------------- */
     925void MultiplexingPass::multiplexSelectedSets(PabloFunction &) {
    926926    const auto first_set = num_vertices(mConstraintGraph);
    927927    const auto last_set = num_vertices(mMultiplexSetGraph);
     
    934934            // The multiplex set graph is a DAG with edges denoting the set relationships of our independent sets.
    935935            unsigned i = 0;
    936             for (const auto e : make_iterator_range(out_edges(idx, mMultiplexSetGraph))) {
    937                 input[i++] = mAdvance[target(e, mMultiplexSetGraph)];
     936            for (const auto u : orderMultiplexSet(idx)) {
     937                input[i++] = mAdvance[u];
    938938            }
    939939            Advance * const adv = input[0];
     
    960960                    demuxing[j] = muxed[j];
    961961                    if (((i + 1) & (1UL << j)) == 0) {
    962                         demuxing[j] = block->createNot(demuxing[j]);
     962                        demuxing[j] = block->createNot(muxed[j]);
    963963                    }
    964964                }
     
    971971        }
    972972    }
     973}
     974
     975/** ------------------------------------------------------------------------------------------------------------- *
     976 * @brief orderMultiplexSet
     977 ** ------------------------------------------------------------------------------------------------------------- */
     978inline MultiplexingPass::MultiplexVector MultiplexingPass::orderMultiplexSet(const MultiplexSetGraph::vertex_descriptor u) {
     979    MultiplexVector set;
     980    set.reserve(out_degree(u, mMultiplexSetGraph));
     981    for (const auto e : make_iterator_range(out_edges(u, mMultiplexSetGraph))) {
     982        set.push_back(target(e, mMultiplexSetGraph));
     983    }
     984    std::sort(set.begin(), set.end());
     985    MultiplexVector clique;
     986    MultiplexVector result;
     987    result.reserve(out_degree(u, mMultiplexSetGraph));
     988    while (set.size() > 0) {
     989        const auto v = *set.begin();
     990        clique.push_back(v);
     991        set.erase(set.begin());
     992        for (const auto w : make_iterator_range(adjacent_vertices(v, mUsageGraph))) {
     993            auto f = std::lower_bound(set.begin(), set.end(), w);
     994            // Is w in our multiplexing set?
     995            if (f == set.end() || *f != w) {
     996                continue;
     997            }
     998            // Is our subgraph still a clique after adding w to it?
     999            bool valid = true;
     1000            for (const auto y : clique) {
     1001                if (!edge(w, y, mUsageGraph).second) {
     1002                    valid = false;
     1003                    break;
     1004                }
     1005            }
     1006            if (valid) {
     1007                clique.push_back(w);
     1008                set.erase(f);
     1009            }
     1010        }
     1011        result.insert(result.end(), clique.begin(), clique.end());
     1012        clique.clear();
     1013    }
     1014    return result;
    9731015}
    9741016
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4890 r4896  
    2929    using IntDistribution = std::uniform_int_distribution<RNG::result_type>;
    3030    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
     31    using MultiplexVector = std::vector<MultiplexSetGraph::vertex_descriptor>;
    3132    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    3233    using SubsetEdgeIterator = boost::graph_traits<SubsetGraph>::edge_iterator;
     
    6768    void doTransitiveReductionOfSubsetGraph();
    6869
    69     void multiplexSelectedIndependentSets(PabloFunction & function);
     70    MultiplexVector orderMultiplexSet(const MultiplexSetGraph::vertex_descriptor u);
     71    void multiplexSelectedSets(PabloFunction & function);
    7072
    7173    static void topologicalSort(PabloFunction & function);
     
    102104    AdvanceVariable             mAdvanceNegatedVariable;
    103105    SubsetGraph                 mSubsetGraph;
    104     CliqueGraph                 mUsageWeightingGraph;
     106    CliqueGraph                 mUsageGraph;
    105107    MultiplexSetGraph           mMultiplexSetGraph;
    106108};
Note: See TracChangeset for help on using the changeset viewer.