Ignore:
Timestamp:
Jan 21, 2016, 5:15:33 PM (3 years ago)
Author:
nmedfort
Message:

Work on lowering + some timing and papi information that will be cleaned up later.

File:
1 edited

Legend:

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

    r4899 r4919  
    33#include <boost/circular_buffer.hpp>
    44#include <boost/container/flat_set.hpp>
     5#include <boost/container/flat_map.hpp>
    56#include <pablo/analysis/pabloverifier.hpp>
     7#include <boost/graph/adjacency_list.hpp>
     8#include <unordered_map>
    69
    710#include <pablo/printer_pablos.h>
     
    1316namespace pablo {
    1417
     18using DependencyGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, std::vector<PabloAST *>>;
     19using Vertex = DependencyGraph::vertex_descriptor;
     20using Map = std::unordered_map<const PabloAST *, Vertex>;
     21using ReadyPair = std::pair<unsigned, Vertex>;
     22using ReadySet = std::vector<ReadyPair>;
     23
     24using weight_t = unsigned;
     25using TypeId = PabloAST::ClassTypeId;
     26using LiveSet = flat_set<Vertex>;
     27
     28void schedule(PabloBlock * const block);
     29
     30/** ------------------------------------------------------------------------------------------------------------- *
     31 * @brief printGraph
     32 ** ------------------------------------------------------------------------------------------------------------- */
     33template <typename DependencyGraph>
     34static void printGraph(const DependencyGraph & G, const std::vector<unsigned> & ordering, const std::string name, raw_ostream & out) {
     35    out << "*******************************************\n";
     36    out << "digraph " << name << " {\n";
     37    for (auto u : make_iterator_range(vertices(G))) {
     38        if (G[u].empty()) {
     39            continue;
     40        }
     41        out << "v" << u << " [label=\"" << ordering[u] << " : ";
     42        bool newLine = false;
     43        for (PabloAST * expr : G[u]) {
     44            if (newLine) {
     45                out << '\n';
     46            }
     47            newLine = true;
     48            if (isa<Statement>(expr)) {
     49                PabloPrinter::print(cast<Statement>(expr), out);
     50            } else {
     51                PabloPrinter::print(expr, out);
     52            }
     53        }
     54        out << "\"];\n";
     55    }
     56    for (auto e : make_iterator_range(edges(G))) {
     57        out << "v" << source(e, G) << " -> v" << target(e, G);
     58        out << ";\n";
     59    }
     60
     61    out << "}\n\n";
     62    out.flush();
     63}
     64
    1565/** ------------------------------------------------------------------------------------------------------------- *
    1666 * @brief resolveNestedUsages
    1767 ** ------------------------------------------------------------------------------------------------------------- */
    18 void SchedulingPrePass::resolveNestedUsages(Statement * const root, Statement * const stmt, Graph & G, Map & M, PabloBlock * const block) {
     68static void resolveNestedUsages(Statement * const root, Statement * const stmt, DependencyGraph & G, Map & M, PabloBlock * const block) {
    1969    for (PabloAST * use : stmt->users()) {
    2070        if (LLVM_LIKELY(isa<Statement>(use))) {
     
    2373                for (PabloBlock * prior = scope->getParent(); prior; scope = prior, prior = prior->getParent()) {
    2474                    if (prior == block) {
    25                         auto s = mResolvedScopes.find(scope);
    26                         assert (s != mResolvedScopes.end());
    27                         assert (s->second);
    28                         auto v = M.find(s->second);
     75                        assert (scope->getBranch());
     76                        auto v = M.find(scope->getBranch());
    2977                        assert (v != M.end());
    3078                        auto u = M.find(root);
     
    4189}
    4290
    43 ///** ------------------------------------------------------------------------------------------------------------- *
    44 // * @brief printGraph
    45 // ** ------------------------------------------------------------------------------------------------------------- */
    46 //template <typename Graph>
    47 //static void printGraph(const Graph & G, const std::vector<unsigned> & ordering, const std::string name, raw_ostream & out) {
    48 //    out << "*******************************************\n";
    49 //    out << "digraph " << name << " {\n";
    50 //    for (auto u : make_iterator_range(vertices(G))) {
    51 //        out << "v" << u << " [label=\"" << ordering[u] << " : ";
    52 //        PabloPrinter::print(G[u], out);
    53 //        out << "\"];\n";
    54 //    }
    55 //    for (auto e : make_iterator_range(edges(G))) {
    56 //        out << "v" << source(e, G) << " -> v" << target(e, G);
    57 //        out << ";\n";
    58 //    }
    59 
    60 //    out << "}\n\n";
    61 //    out.flush();
    62 //}
    63 
    64 /** ------------------------------------------------------------------------------------------------------------- *
    65  * @brief schedule
    66  ** ------------------------------------------------------------------------------------------------------------- */
    67 void SchedulingPrePass::schedule(PabloBlock * const block) {
    68     Graph G;
     91/** ------------------------------------------------------------------------------------------------------------- *
     92 * @brief resolveNestedUsages
     93 ** ------------------------------------------------------------------------------------------------------------- */
     94static void computeDependencyGraph(DependencyGraph & G, PabloBlock * const block) {
    6995    Map M;
    70 
    7196    // Construct a use-def graph G representing the current scope block
    7297    for (Statement * stmt : *block) {
    73         if (isa<If>(stmt) || isa<While>(stmt)) {
    74             PabloBlock * body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    75             mResolvedScopes.emplace(body, stmt);
    76             schedule(body);
    77         }
    78         const auto u = add_vertex(stmt, G);
     98        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     99            schedule(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     100        }
     101        const auto u = add_vertex({stmt}, G);
    79102        M.insert(std::make_pair(stmt, u));
    80103        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     
    94117                        // Was this instruction computed by a nested block?
    95118                        if (prior == block) {
    96                             auto s = mResolvedScopes.find(scope);
    97                             assert (s != mResolvedScopes.end());
    98                             assert (s->second);
    99                             auto v = M.find(s->second);
     119                            assert (scope->getBranch());
     120                            auto v = M.find(scope->getBranch());
    100121                            assert (v != M.end());
    101122                            if (v->second != u) {
     
    109130        }
    110131    }
    111     // Do a second pass to ensure that we've accounted for any nested usage of a statement
     132    // Do a second pass to ensure that we've accounted for any nested usage of an If or While statement
    112133    for (Statement * stmt : *block) {
    113134        if (LLVM_UNLIKELY(isa<If>(stmt))) {
     
    123144        }
    124145    }
    125 
     146    // Contract the graph
     147    for (;;) {
     148        bool done = true;
     149        for (const Vertex u : make_iterator_range(vertices(G))) {
     150            if (out_degree(u, G) == 1) {
     151                const Vertex v = target(*(out_edges(u, G).first), G);
     152                G[v].insert(G[v].begin(), G[u].begin(), G[u].end());
     153                for (auto e : make_iterator_range(in_edges(u, G))) {
     154                    add_edge(source(e, G), v, G);
     155                }
     156                G[u].clear();
     157                clear_vertex(u, G);
     158                done = false;
     159            }
     160        }
     161        if (done) {
     162            break;
     163        }
     164    }
     165
     166
     167}
     168
     169/** ------------------------------------------------------------------------------------------------------------- *
     170 * @brief computeGraphOrdering
     171 ** ------------------------------------------------------------------------------------------------------------- */
     172std::vector<weight_t> computeGraphOrdering(const DependencyGraph & G) {
    126173    // Determine the bottom-up ordering of G
    127     std::vector<unsigned> ordering(num_vertices(G));
     174    std::vector<weight_t> ordering(num_vertices(G));
    128175    circular_buffer<Vertex> Q(num_vertices(G));
    129176    for (const Vertex u : make_iterator_range(vertices(G))) {
    130         if (out_degree(u, G) == 0) {
     177        if (out_degree(u, G) == 0 && G[u].size() > 0) {
    131178            ordering[u] = 1;
    132179            Q.push_back(u);
    133180        }
    134181    }
    135 
    136182    while (!Q.empty()) {
    137183        const Vertex u = Q.front();
     
    141187            const Vertex v = source(ei, G);
    142188            if (ordering[v] == 0) {
    143                 unsigned weight = 0;
     189                weight_t weight = 0;
    144190                bool ready = true;
    145191                for (const auto ej : make_iterator_range(out_edges(v, G))) {
    146192                    const Vertex w = target(ej, G);
    147                     const unsigned t = ordering[w];
     193                    const weight_t t = ordering[w];
    148194                    if (t == 0) {
    149195                        ready = false;
     
    155201                    assert (weight < std::numeric_limits<unsigned>::max());
    156202                    assert (weight > 0);
    157                     ordering[v] = (weight + 1);
     203                    ordering[v] = weight + 1;
    158204                    Q.push_back(v);
    159205                }
     
    161207        }
    162208    }
     209    return ordering;
     210}
     211
     212/** ------------------------------------------------------------------------------------------------------------- *
     213 * @brief schedule
     214 ** ------------------------------------------------------------------------------------------------------------- */
     215void schedule(PabloBlock * const block) {
     216    DependencyGraph G;
     217    computeDependencyGraph(G, block);
     218    std::vector<weight_t> ordering = computeGraphOrdering(G);
     219
     220//    raw_os_ostream out(std::cerr);
     221//    printGraph(G, ordering, "G", out);
    163222
    164223    // Compute the initial ready set
    165224    ReadySet readySet;
    166225    for (const Vertex u : make_iterator_range(vertices(G))) {
    167         if (in_degree(u, G) == 0) {
     226        if (in_degree(u, G) == 0 && G[u].size() > 0) {
    168227            readySet.emplace_back(ordering[u], u);
    169228        }
     
    180239    block->setInsertPoint(nullptr);
    181240
    182 
    183     // Rewrite the AST using the bottom-up ordering
     241    // Rewrite the AST
    184242    while (!readySet.empty()) {
    185 
    186         // Scan through the ready set to determine which one 'kills' the greatest number of inputs
    187         // NOTE: the readySet is kept in sorted "distance to sink" order; thus those closest to a
    188         // sink will be evaluated first.
    189         double best = 0;
     243        DependencyGraph::degree_size_type killed = 0;
    190244        auto chosen = readySet.begin();
    191245        for (auto ri = readySet.begin(); ri != readySet.end(); ++ri) {
    192             const Vertex u = std::get<1>(*ri);
    193             const PabloAST * const expr = G[u];
    194             if (expr && (isa<Assign>(expr) || isa<Next>(expr))) {
     246            DependencyGraph::degree_size_type kills = 0;
     247            for (auto e : make_iterator_range(in_edges(ri->first, G))) {
     248                if (out_degree(source(e, G), G) == 1) {
     249                    ++kills;
     250                }
     251            }
     252            if (kills > killed) {
    195253                chosen = ri;
    196                 break;
    197             }
    198             double progress = 0;
    199             for (auto ei : make_iterator_range(in_edges(u, G))) {
    200                 const auto v = source(ei, G);
    201                 const auto totalUsesOfIthOperand = out_degree(v, G);
    202                 if (LLVM_UNLIKELY(totalUsesOfIthOperand == 0)) {
    203                     progress += 1.0;
    204                 } else {
    205                     unsigned unscheduledUsesOfIthOperand = 0;
    206                     for (auto ej : make_iterator_range(out_edges(v, G))) {
    207                         if (ordering[target(ej, G)]) { // if this edge leads to an unscheduled statement
    208                             ++unscheduledUsesOfIthOperand;
    209                         }
    210                     }
    211                     progress += std::pow((double)(totalUsesOfIthOperand - unscheduledUsesOfIthOperand + 1) / (double)(totalUsesOfIthOperand), 2);
    212                 }
    213             }
    214             if (progress > best) {
    215                 chosen = ri;
    216                 best = progress;
     254                killed = kills;
    217255            }
    218256        }
     
    221259        std::tie(weight, u) = *chosen;
    222260        readySet.erase(chosen);
     261        clear_in_edges(u, G);
    223262
    224263        assert ("Error: SchedulingPrePass is attempting to reschedule a statement!" && (weight > 0));
    225264
    226265        // insert the statement then mark it as written ...
    227         block->insert(cast<Statement>(G[u]));
     266        for (PabloAST * expr : G[u]) {
     267            block->insert(cast<Statement>(expr));
     268        }
     269
    228270        ordering[u] = 0;
    229271        // Now check whether any new instructions are ready
     
    245287        }
    246288    }
     289
    247290}
    248291
     
    250293 * @brief schedule
    251294 ** ------------------------------------------------------------------------------------------------------------- */
    252 void SchedulingPrePass::schedule(PabloFunction & function) {
    253     mResolvedScopes.emplace(function.getEntryBlock(), nullptr);
     295void schedule(PabloFunction & function) {
    254296    schedule(function.getEntryBlock());
    255297}
     
    259301 ** ------------------------------------------------------------------------------------------------------------- */
    260302bool SchedulingPrePass::optimize(PabloFunction & function) {
    261     SchedulingPrePass pp;
    262     pp.schedule(function);
     303    schedule(function);
    263304    #ifndef NDEBUG
    264305    PabloVerifier::verify(function, "post-scheduling-prepass");
Note: See TracChangeset for help on using the changeset viewer.