Ignore:
Timestamp:
Mar 7, 2016, 3:37:30 PM (3 years ago)
Author:
nmedfort
Message:

Initial modifications to Pablo Compiler and Kernel Builder to support circular buffers for Lookahead.

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

Legend:

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

    r4942 r4959  
    166166bool MultiplexingPass::optimize(PabloFunction & function, const bool independent) {
    167167
     168    if (LLVM_UNLIKELY(Samples < 1)) {
     169        return false;
     170    }
     171
     172
    168173    LOG("Seed:                    " << Seed);
    169174
     
    395400        for (unsigned j = 0; j < i; ++j) {
    396401            if (G(i, j)) {
    397                 add_edge(j, i, mConstraintGraph);
     402                add_edge(j, i, true, mConstraintGraph);
    398403            }
    399404        }
    400405        for (unsigned j = i + 1; j < advances; ++j) {
    401406            if (G(i, j)) {
    402                 add_edge(j, i, mConstraintGraph);
     407                add_edge(j, i, true, mConstraintGraph);
    403408            }
    404409        }
     
    607612
    608613    BDD Ak = bdd_ithvar(mVariables++);
    609     const BDD Nk = bdd_addref(bdd_not(Ak));
     614    const BDD Nk = bdd_addref(bdd_not(Ak));   
    610615    for (unsigned i = 0; i != k; ++i) {
    611616        if (unconstrained[i]) {
     
    627632            }
    628633        }
    629         add_edge(i, k, mConstraintGraph);
     634        add_edge(i, k, false, mConstraintGraph);
    630635    }
    631636    // To minimize the number of BDD computations, we store the negated variable instead of negating it each time.
     
    639644inline bool MultiplexingPass::independent(const ConstraintVertex i, const ConstraintVertex j) const {
    640645    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
    641     return (mConstraintGraph.get_edge(i, j) == 0);
     646    return mConstraintGraph.get_edge(i, j).first == false;
    642647}
    643648
     
    719724    mCandidateGraph = CandidateGraph(num_vertices(mConstraintGraph));
    720725
    721     for (unsigned iteration = 0; iteration < Samples; ++iteration) {
     726    for (unsigned r = Samples; r; --r) {
    722727
    723728        // Push all source nodes into the (initial) independent set S
     
    768773    }
    769774
     775    #ifdef PRINT_DEBUG_OUTPUT
     776    const auto n = num_vertices(mConstraintGraph);
     777    const auto m = num_vertices(mCandidateGraph);
     778    unsigned sets = 0;
     779    for (auto i = n; i < m; ++i) {
     780        if (degree(i, mCandidateGraph) > 0) {
     781            ++sets;
     782        }
     783    }
     784    LOG("Unique Candidate Sets:    " << (sets));
     785    #endif
     786
    770787    return num_vertices(mCandidateGraph) > num_vertices(mConstraintGraph);
    771788}
     
    912929    const size_t n = num_vertices(mCandidateGraph) - m;
    913930
    914     degree_t remaining[n];
    915     vertex_t chosen_set[m];
    916 
    917     for (unsigned i = 0; i != n; ++i) {
    918         remaining[i] = degree(i + m, mCandidateGraph);
    919     }
    920     for (unsigned i = 0; i != m; ++i) {
    921         chosen_set[i] = 0;
    922     }
     931    std::vector<bool> chosen(n, false);
    923932
    924933    for (;;) {
    925934
    926935        // Choose the set with the greatest number of vertices not already included in some other set.
    927         vertex_t k = 0;
     936        vertex_t u = 0;
    928937        degree_t w = 0;
    929938        for (vertex_t i = 0; i != n; ++i) {
    930             degree_t r = remaining[i];
    931             if (r > 2) { // if this set has at least 3 elements.
     939            if (chosen[i]) continue;
     940            const auto t = i + m;
     941            degree_t r = degree(t, mCandidateGraph);
     942            if (LLVM_LIKELY(r >= 3)) { // if this set has at least 3 elements.
    932943                r *= r;
    933944                AdjIterator begin, end;
    934                 std::tie(begin, end) = adjacent_vertices(i + m, mCandidateGraph);
     945                std::tie(begin, end) = adjacent_vertices(t, mCandidateGraph);
    935946                for (auto ei = begin; ei != end; ++ei) {
    936947                    for (auto ej = ei; ++ej != end; ) {
     
    941952                }
    942953                if (w < r) {
    943                     k = i;
     954                    u = t;
    944955                    w = r;
    945956                }
     957            } else if (r) {
     958                clear_vertex(t, mCandidateGraph);
    946959            }
    947960        }
    948961
    949962        // Multiplexing requires 3 or more elements; if no set contains at least 3, abort.
    950         if (w == 0) {
     963        if (LLVM_UNLIKELY(w == 0)) {
    951964            break;
    952965        }
    953966
    954         for (const auto u : make_iterator_range(adjacent_vertices(k + m, mCandidateGraph))) {
    955             if (chosen_set[u] == 0) {
    956                 chosen_set[u] = (k + m);
    957                 for (const auto v : make_iterator_range(adjacent_vertices(u, mCandidateGraph))) {
    958                     assert (v >= m);
    959                     remaining[v - m]--;
    960                 }
    961             }
    962         }
    963 
    964         assert (remaining[k] == 0);
     967        chosen[u - m] = true;
    965968
    966969        // If this contains 2^n elements for any n, discard the member that is most likely to be added
    967970        // to some future set.
    968         if (LLVM_UNLIKELY(is_power_of_2(w))) {
    969             vertex_t j = 0;
     971        if (LLVM_UNLIKELY(is_power_of_2(degree(u, mCandidateGraph)))) {
     972            vertex_t x = 0;
    970973            degree_t w = 0;
    971             for (vertex_t i = 0; i != m; ++i) {
    972                 if (chosen_set[i] == (k + m)) {
    973                     degree_t r = 1;
    974                     for (const auto u : make_iterator_range(adjacent_vertices(i, mCandidateGraph))) {
    975                         // strongly prefer adding weight to unvisited sets that have more remaining vertices
    976                         r += std::pow(remaining[u - m], 2);
    977                     }
    978                     if (w < r) {
    979                         j = i;
    980                         w = r;
    981                     }
    982                 }
    983             }
    984             assert (w > 0);
    985             chosen_set[j] = 0;
    986             for (const auto u : make_iterator_range(adjacent_vertices(j, mCandidateGraph))) {
    987                 assert (u >= m);
    988                 remaining[u - m]++;
    989             }
    990         }
    991 
    992         // If Samples > 1 then our candidate sets were generated by more than one traversal through the constraint graph.
    993         // Sets generated by differing traversals may generate a cycle in the AST if multiplex even when they are not
    994         // multiplexed together. For example,
    995 
    996         // Assume we're multiplexing set {A,B,C} and {D,E,F} and that no constraint exists between any nodes in
    997         // either set. If A is dependent on D and E is dependent on B, multiplexing both sets would result in a cycle
    998         // in the AST. To fix this, we'd have to remove A, D, B or E.
    999 
    1000         // This cannot occur with only one traversal (or between sets generated by the same traversal) because of the
    1001         // DAG traversal strategy used in "generateCandidateSets".
    1002 
    1003 
    1004     }
    1005 
    1006     for (unsigned i = 0; i != m; ++i) {
    1007         AdjIterator ei, ei_end;
    1008         std::tie(ei, ei_end) = adjacent_vertices(i, mCandidateGraph);
    1009         for (auto next = ei; ei != ei_end; ei = next) {
    1010             ++next;
    1011             if (*ei != chosen_set[i]) {
    1012                 remove_edge(i, *ei, mCandidateGraph);
    1013             }
     974            for (const auto v : make_iterator_range(adjacent_vertices(u, mCandidateGraph))) {
     975                if (degree(v, mCandidateGraph) > w) {
     976                    x = v;
     977                    w = degree(v, mCandidateGraph);
     978                }
     979            }
     980            remove_edge(u, x, mCandidateGraph);
     981        }
     982
     983        AdjIterator begin, end;
     984        std::tie(begin, end) = adjacent_vertices(u, mCandidateGraph);
     985        for (auto vi = begin; vi != end; ) {
     986            const auto v = *vi++;
     987            clear_vertex(v, mCandidateGraph);
     988            add_edge(v, u, mCandidateGraph);
     989        }
     990
     991        if (Samples > 1) {
     992            removePotentialCycles(u);
    1014993        }
    1015994    }
     
    10601039
    10611040
     1041}
     1042
     1043/** ------------------------------------------------------------------------------------------------------------- *
     1044 * @brief removePotentialCycles
     1045 *
     1046 * If Samples > 1, our candidate sets were generated by more than one traversal through the constraint DAG.
     1047 * Multiplexing disjoint sets generated by differing traversals can induce a cycle in the AST. For example,
     1048 * suppose sets {A,B} and {C,D} and A is dependent on C and D on B; multiplexing both will result in a cycle.
     1049 *
     1050 * Eliminating all potential cycles will likely lead to the removal of many candidate sets. Instead we "fix"
     1051 * the candidate sets after the selection of a particular candidate set.
     1052 ** ------------------------------------------------------------------------------------------------------------- */
     1053void MultiplexingPass::removePotentialCycles(const CandidateGraph::vertex_descriptor i) {
     1054
     1055    using AdjIterator = graph_traits<CandidateGraph>::adjacency_iterator;
     1056
     1057    const auto m = num_vertices(mConstraintGraph);
     1058    const auto n = num_vertices(mCandidateGraph);
     1059
     1060    // Suppose we construct a graph G that indicates whether selecting candidate set V will induce a cycle, given
     1061    // that we've already chosen candidate set U. This can occur here only because some elements of V are dependent
     1062    // on U and vice versa.
     1063
     1064    // We want the minimal minimum weight feedback arc set of G; however, we also know any edge will either have
     1065    //
     1066
     1067    for (auto j = m; j < n; ++j) {
     1068        if (LLVM_UNLIKELY(i == j)) continue;
     1069        AdjIterator begin, end;
     1070        std::tie(begin, end) = adjacent_vertices(j, mCandidateGraph);
     1071        for (auto ui = begin; ui != end; )  {
     1072            const auto u = *ui++;
     1073            unsigned outgoing = 0;
     1074            unsigned incoming = 0;
     1075            for (auto v : make_iterator_range(adjacent_vertices(i, mCandidateGraph)))  {
     1076                if (dependent(u, v)) {
     1077                    ++outgoing;
     1078                } else if (dependent(v, u)) {
     1079                    ++incoming;
     1080                }
     1081            }
     1082            if (LLVM_UNLIKELY(outgoing > 0 && incoming > 0)) {
     1083                remove_edge(j, u, mCandidateGraph);
     1084            }
     1085        }
     1086    }
     1087}
     1088
     1089/** ------------------------------------------------------------------------------------------------------------- *
     1090 * @brief dependent
     1091 ** ------------------------------------------------------------------------------------------------------------- */
     1092inline bool MultiplexingPass::dependent(const ConstraintVertex i, const ConstraintVertex j) const {
     1093    const auto e = mConstraintGraph.get_edge(i, j);
     1094    return (e.second && e.first);
    10621095}
    10631096
     
    12671300                    work = 2;
    12681301                    break;
    1269 //                case TypeId::Not:
     1302                case TypeId::Not:
    12701303                case TypeId::Assign:
    12711304                case TypeId::Next:
     
    13661399            bool ready = true;
    13671400            const auto v = target(ei, G);
     1401            assert (rank[v] != 0);
    13681402            for (auto ej : make_iterator_range(in_edges(v, G))) {
    13691403                if (rank[source(ej, G)] != 0) {
     
    13731407            }
    13741408            if (ready) {
    1375                 assert (rank[v] != 0);
    13761409                readySet.insert(std::lower_bound(readySet.begin(), readySet.end(), v, by_nonincreasing_rank), v);
    13771410                assert (std::is_sorted(readySet.cbegin(), readySet.cend(), by_nonincreasing_rank));
     
    16061639
    16071640    #ifndef NDEBUG
    1608     std::vector<typename Graph::vertex_descriptor> nothing;
     1641    std::vector<Vertex> nothing;
    16091642    topological_sort(G, std::back_inserter(nothing));
    16101643    #endif
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4937 r4959  
    2525    using CharacterizationMap = llvm::DenseMap<const PabloAST *, BDD>;
    2626
    27     using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
     27    using ConstraintGraph = boost::adjacency_matrix<boost::directedS, boost::no_property, bool>;
    2828    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
    2929    using Constraints = std::vector<ConstraintVertex>;
     
    4242
    4343    using AdvanceVector = std::vector<Advance *>;
    44     using AdvanceDepth = std::vector<int>;
     44    using AdvanceRank = std::vector<int>;
    4545    using AdvanceVariable = std::vector<BDD>;
    4646
     
    7878    void selectMultiplexSetsWorkingSet();
    7979
     80    void removePotentialCycles(const CandidateGraph::vertex_descriptor u);
     81    bool dependent(const ConstraintVertex i, const ConstraintVertex j) const;
     82
    8083    void eliminateSubsetConstraints();
    8184    void doTransitiveReductionOfSubsetGraph();
     
    109112    ConstraintGraph             mConstraintGraph;   
    110113    AdvanceVector               mAdvance;
    111     AdvanceDepth                mAdvanceRank;
     114    AdvanceRank                 mAdvanceRank;
    112115    AdvanceVariable             mAdvanceNegatedVariable;
    113116    SubsetGraph                 mSubsetGraph;
    114117    CliqueGraph                 mUsageGraph;
    115     CandidateGraph           mCandidateGraph;
     118    CandidateGraph              mCandidateGraph;
    116119};
    117120
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4937 r4959  
    525525
    526526/** ------------------------------------------------------------------------------------------------------------- *
     527 * @brief unused
     528 ** ------------------------------------------------------------------------------------------------------------- */
     529inline static bool unused(const Statement * const stmt) {
     530    if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
     531        // TODO: prototypes ought to state whether they have side effects.
     532        if (LLVM_UNLIKELY(isa<Call>(stmt) && cast<Call>(stmt)->getPrototype()->getNumOfResults() == 0)) {
     533            return false;
     534        }
     535        return true;
     536    }
     537    return false;
     538}
     539
     540/** ------------------------------------------------------------------------------------------------------------- *
    527541 * @brief deadCodeElimination
    528542 ** ------------------------------------------------------------------------------------------------------------- */
     
    530544    Statement * stmt = block->front();
    531545    while (stmt) {
    532         if (isa<If>(stmt)) {
     546        if (LLVM_UNLIKELY(isa<If>(stmt))) {
    533547            deadCodeElimination(cast<If>(stmt)->getBody());
    534         } else if (isa<While>(stmt)) {
     548        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    535549            deadCodeElimination(cast<While>(stmt)->getBody());
    536         } else if (stmt->getNumUses() == 0){
     550        } else if (LLVM_UNLIKELY(unused(stmt))){
    537551            stmt = stmt->eraseFromParent(true);
    538552            continue;
     
    562576                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
    563577                    adv->setOperand(0, op->getOperand(0));
    564                     adv->setOperand(1, block->getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
     578                    adv->setOperand(1, block->getInteger(adv->getAmount() + op->getAmount()));
    565579                    op->eraseFromParent(false);
    566580                }
     
    573587                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
    574588                    block->setInsertPoint(scanThru->getPrevNode());
    575                     PabloAST * expr = block->createAdvance(op->getOperand(0), op->getAdvanceAmount() - 1);
     589                    PabloAST * expr = block->createAdvance(op->getOperand(0), op->getAmount() - 1);
    576590                    scanThru->setOperand(0, expr);
    577591                    scanThru->setOperand(1, block->createOr(scanThru->getOperand(1), expr));
Note: See TracChangeset for help on using the changeset viewer.