Changeset 4896


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
Files:
2 added
16 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4892 r4896  
    6565SET(PABLO_SRC ${PABLO_SRC} pablo/analysis/pabloverifier.cpp)
    6666SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/codemotionpass.cpp pablo/optimizers/distributivepass.cpp pablo/passes/flattenassociativedfg.cpp pablo/passes/factorizedfg.cpp)
    67 SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/booleanreassociationpass.cpp)
     67SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/schedulingprepass.cpp)
    6868IF (ENABLE_MULTIPLEXING)
    6969SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_automultiplexing.cpp pablo/optimizers/pablo_bddminimization.cpp)
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r4890 r4896  
    491491pablo/passes/factorizedfg.cpp
    492492ispc.cpp
     493pablo/optimizers/schedulingprepass.h
     494pablo/optimizers/schedulingprepass.cpp
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r4890 r4896  
    564564, mSymbolGenerator(symbolGenerator)
    565565, mParent(nullptr)
     566, mBranch(nullptr)
    566567, mScopeIndex(0)
    567568{
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4890 r4896  
    3737class PabloBlock : public PabloAST, public StatementList {
    3838    friend class PabloAST;
     39    friend class If;
     40    friend class While;
    3941    friend class PabloBuilder;
    4042public:
     
    187189    PabloAST * createMod64ScanThru(PabloAST * from, PabloAST * thru, const std::string prefix);
    188190
    189 
    190191    inline StatementList & statements() {
    191192        return *this;
     
    226227   
    227228    void eraseFromParent(const bool recursively = false);
     229
     230    inline Statement * getBranch() const {
     231        return mBranch;
     232    }
    228233
    229234    virtual ~PabloBlock();
     
    248253    }
    249254
     255    inline void setBranch(Statement * const branch) {
     256        mBranch = branch;
     257    }
     258
    250259private:
    251260
     
    259268    SymbolGenerator *                                   mSymbolGenerator; // TODO: need a better way of passing a symbol generator around
    260269    PabloBlock *                                        mParent;
     270    Statement *                                         mBranch; // What statement branches into this scope block?
    261271    unsigned                                            mScopeIndex;
    262272};
  • 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};
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4886 r4896  
    6060        , And
    6161        , Or
    62         , Not
    6362        , Xor
     63        , Not       
    6464        , Sel
    6565        // Stream operations
     
    102102    }
    103103
    104     inline unsigned getNumUsers() const {
    105         return mUsers.size();
    106     }
    107 
    108104    inline Users & users() {
    109105        return mUsers;
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.cpp

    r4890 r4896  
    5151            finalize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    5252        } else if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
     53            // We should maintain an ordering list and sort each Variadic according to it prior to writing them out.
    5354            stmt = finalize(cast<Variadic>(stmt), block);
    5455            continue;
     
    7374        PabloAST * const op = var->getOperand(i);
    7475        VertexSet B;
    75         B.reserve(op->getNumUsers());
     76        B.reserve(op->getNumUses());
    7677        for (PabloAST * user : op->users()) {
    7778            if (user->getClassTypeId() == typeId) {
  • 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}
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.h

    r4890 r4896  
    2222    static void deMorgansReduction(PabloBlock * const block);
    2323    static void deMorgansReduction(Variadic * const var, PabloBlock * const block);
     24    static void removeFalseScopeDependencies(PabloBlock * const block);
     25    static void removeFalseScopeDependencies(Assign * const def);
     26    static void tryToPartiallyExtractVariadic(Variadic * const var);
    2427    FlattenAssociativeDFG() = default;
    2528};
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.cpp

    r4878 r4896  
    1919    // Assign's value is also dependant on the 'Next' value, the If node is also a user
    2020    // of it.
    21 
     21    mBody->setBranch(this);
    2222    mBody->setParent(getParent());
    2323    for (Assign * def : mDefined) {
     
    3131, mBody(body)
    3232, mDefined(definedVars.begin(), definedVars.end(), reinterpret_cast<DefinedAllocator &>(mAllocator)) {
     33    mBody->setBranch(this);
    3334    mBody->setParent(getParent());
    3435    for (Assign * def : mDefined) {
  • icGREP/icgrep-devel/icgrep/pablo/ps_while.cpp

    r4878 r4896  
    88, mBody(body)
    99, mVariant(nextVars.begin(), nextVars.end(), reinterpret_cast<NextAllocator &>(mAllocator)) {
     10    mBody->setBranch(this);
    1011    mBody->setParent(getParent());
    1112    for (Next * variant : nextVars) {
     
    1920, mBody(body)
    2021, mVariant(nextVars.begin(), nextVars.end(), reinterpret_cast<NextAllocator &>(mAllocator)) {
     22    mBody->setBranch(this);
    2123    mBody->setParent(getParent());
    2224    for (Next * variant : nextVars) {
  • icGREP/icgrep-devel/icgrep/toolchain.cpp

    r4890 r4896  
    4444#include <pablo/optimizers/pablo_bddminimization.h>
    4545#include <pablo/optimizers/distributivepass.h>
     46#include <pablo/optimizers/schedulingprepass.h>
    4647#endif
    4748#include <pablo/function.h>
     
    166167        MultiplexingPass::optimize(*function, MultiplexingSetLimit, MultiplexingSelectionLimit, MultiplexingWindowSize);
    167168    }
     169    SchedulingPrePass::optimize(*function);
    168170    if (EnableLowering || EnableDistribution || EnableMultiplexing) {
    169171        FactorizeDFG::transform(*function);
Note: See TracChangeset for help on using the changeset viewer.