Ignore:
Timestamp:
Nov 6, 2015, 4:54:29 PM (4 years ago)
Author:
nmedfort
Message:

Work on better scheduling in reassociation pass.

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

Legend:

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

    r4860 r4861  
    159159}
    160160
    161 /** ------------------------------------------------------------------------------------------------------------- *
    162  * @brief printGraph
    163  ** ------------------------------------------------------------------------------------------------------------- */
    164 static void printGraph(const Graph & G, const std::string name, raw_ostream & out) {
    165 
    166     std::vector<unsigned> c(num_vertices(G));
    167     strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
    168 
    169     out << "digraph " << name << " {\n";
    170     for (auto u : make_iterator_range(vertices(G))) {
    171         if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    172             continue;
    173         }
    174         out << "v" << u << " [label=\"" << u << ": ";
    175         PabloAST * expr;
    176         TypeId typeId;
    177         std::tie(typeId, expr) = G[u];
    178         bool temporary = false;
    179         bool error = false;
    180         if (expr == nullptr) {
    181             temporary = true;
    182             switch (typeId) {
    183                 case TypeId::And:
    184                     out << "And";
    185                     break;
    186                 case TypeId::Or:
    187                     out << "Or";
    188                     break;
    189                 case TypeId::Xor:
    190                     out << "Xor";
    191                     break;
    192                 default:
    193                     out << "???";
    194                     error = true;
    195                     break;
    196             }
    197         } else if (isMutable(G[u])) {
    198             if (LLVM_UNLIKELY(isa<If>(expr))) {
    199                 out << "If ";
    200                 PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
    201                 out << ":";
    202             } else if (LLVM_UNLIKELY(isa<While>(expr))) {
    203                 out << "While ";
    204                 PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
    205                 out << ":";
    206             } else {
    207                 PabloPrinter::print(cast<Statement>(expr), "", out);
    208             }
    209         } else {
    210             PabloPrinter::print(expr, out);
    211         }
    212         out << "\"";
    213         if (!isMutable(G[u])) {
    214             out << " style=dashed";
    215         }
    216         if (error) {
    217             out << " color=red";
    218         } else if (temporary) {
    219             out << " color=blue";
    220         }
    221         out << "];\n";
    222     }
    223     for (auto e : make_iterator_range(edges(G))) {
    224         const auto s = source(e, G);
    225         const auto t = target(e, G);
    226         out << "v" << s << " -> v" << t;
    227         bool cyclic = (c[s] == c[t]);
    228         if (G[e] || cyclic) {
    229             out << " [";
    230              if (G[e]) {
    231                 out << "label=\"";
    232                 PabloPrinter::print(G[e], out);
    233                 out << "\" ";
    234              }
    235              if (cyclic) {
    236                 out << "color=red ";
    237              }
    238              out << "]";
    239         }
    240         out << ";\n";
    241     }
    242 
    243     if (num_vertices(G) > 0) {
    244 
    245         out << "{ rank=same;";
    246         for (auto u : make_iterator_range(vertices(G))) {
    247             if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    248                 out << " v" << u;
    249             }
    250         }
    251         out << "}\n";
    252 
    253         out << "{ rank=same;";
    254         for (auto u : make_iterator_range(vertices(G))) {
    255             if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    256                 out << " v" << u;
    257             }
    258         }
    259         out << "}\n";
    260 
    261     }
    262 
    263     out << "}\n\n";
    264     out.flush();
    265 }
     161///** ------------------------------------------------------------------------------------------------------------- *
     162// * @brief printGraph
     163// ** ------------------------------------------------------------------------------------------------------------- */
     164//static void printGraph(const Graph & G, const std::string name, raw_ostream & out) {
     165
     166//    std::vector<unsigned> c(num_vertices(G));
     167//    strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
     168
     169//    out << "digraph " << name << " {\n";
     170//    for (auto u : make_iterator_range(vertices(G))) {
     171//        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     172//            continue;
     173//        }
     174//        out << "v" << u << " [label=\"" << u << ": ";
     175//        PabloAST * expr;
     176//        TypeId typeId;
     177//        std::tie(typeId, expr) = G[u];
     178//        bool temporary = false;
     179//        bool error = false;
     180//        if (expr == nullptr) {
     181//            temporary = true;
     182//            switch (typeId) {
     183//                case TypeId::And:
     184//                    out << "And";
     185//                    break;
     186//                case TypeId::Or:
     187//                    out << "Or";
     188//                    break;
     189//                case TypeId::Xor:
     190//                    out << "Xor";
     191//                    break;
     192//                default:
     193//                    out << "???";
     194//                    error = true;
     195//                    break;
     196//            }
     197//        } else if (isMutable(G[u])) {
     198//            if (LLVM_UNLIKELY(isa<If>(expr))) {
     199//                out << "If ";
     200//                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
     201//                out << ":";
     202//            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
     203//                out << "While ";
     204//                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
     205//                out << ":";
     206//            } else {
     207//                PabloPrinter::print(cast<Statement>(expr), "", out);
     208//            }
     209//        } else {
     210//            PabloPrinter::print(expr, out);
     211//        }
     212//        out << "\"";
     213//        if (!isMutable(G[u])) {
     214//            out << " style=dashed";
     215//        }
     216//        if (error) {
     217//            out << " color=red";
     218//        } else if (temporary) {
     219//            out << " color=blue";
     220//        }
     221//        out << "];\n";
     222//    }
     223//    for (auto e : make_iterator_range(edges(G))) {
     224//        const auto s = source(e, G);
     225//        const auto t = target(e, G);
     226//        out << "v" << s << " -> v" << t;
     227//        bool cyclic = (c[s] == c[t]);
     228//        if (G[e] || cyclic) {
     229//            out << " [";
     230//             if (G[e]) {
     231//                out << "label=\"";
     232//                PabloPrinter::print(G[e], out);
     233//                out << "\" ";
     234//             }
     235//             if (cyclic) {
     236//                out << "color=red ";
     237//             }
     238//             out << "]";
     239//        }
     240//        out << ";\n";
     241//    }
     242
     243//    if (num_vertices(G) > 0) {
     244
     245//        out << "{ rank=same;";
     246//        for (auto u : make_iterator_range(vertices(G))) {
     247//            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     248//                out << " v" << u;
     249//            }
     250//        }
     251//        out << "}\n";
     252
     253//        out << "{ rank=same;";
     254//        for (auto u : make_iterator_range(vertices(G))) {
     255//            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     256//                out << " v" << u;
     257//            }
     258//        }
     259//        out << "}\n";
     260
     261//    }
     262
     263//    out << "}\n\n";
     264//    out.flush();
     265//}
    266266
    267267/** ------------------------------------------------------------------------------------------------------------- *
     
    338338 * @brief writeTree
    339339 ** ------------------------------------------------------------------------------------------------------------- */
    340 inline void writeTree(PabloBlock & block, const TypeId typeId, circular_buffer<PabloAST *> & Q) {
     340inline PabloAST * writeTree(PabloBlock & block, const TypeId typeId, circular_buffer<PabloAST *> & Q) {
    341341    while (Q.size() > 1) {
    342342        PabloAST * e1 = Q.front(); Q.pop_front();
     
    353353        }
    354354        Q.push_back(expr);
    355     }
     355    }   
     356    return Q.front();
     357}
     358
     359/** ------------------------------------------------------------------------------------------------------------- *
     360 * @brief isReachableAtEntryPoint
     361 ** ------------------------------------------------------------------------------------------------------------- */
     362bool isReachableAtEntryPoint(const PabloAST * const expr, const PabloBlock & block) {
     363    // if expr is not a statement, it's always reachable
     364    if (isa<Statement>(expr)) {
     365        const PabloBlock * const parent = cast<Statement>(expr)->getParent();
     366        // if expr is in the current block, it's not reachable at the entry point of this block
     367        if (parent == &block) {
     368            return false;
     369        }
     370        const PabloBlock * current = block.getParent();
     371        // if we can find expr in a preceeding block, it's reachable
     372        while (current) {
     373            if (parent == current) {
     374                return true;
     375            }
     376            current = current->getParent();
     377        }
     378        // otherwise it must be in a nested block and therefore unreachable
     379        return false;
     380    }
     381    return true;
    356382}
    357383
     
    361387PabloAST * BooleanReassociationPass::createTree(PabloBlock & block, const Vertex u, Graph & G) {
    362388
    363     flat_set<PabloAST *> sources;
     389    flat_set<PabloAST *> internalVars;
     390
     391    flat_set<PabloAST *> externalVars;
     392
     393    assert (in_degree(u, G) > 0);
    364394
    365395    for (const auto e : make_iterator_range(in_edges(u, G))) {
    366396        PabloAST * const expr = getValue(G[source(e, G)]);
    367397        assert ("G contains a null input variable!" && (expr != nullptr));
    368         sources.insert(expr);
    369     }
    370 
    371     circular_buffer<PabloAST *> Q(sources.size());
    372 
    373     for (auto si = sources.begin(); si != sources.end(); ) {
    374         if (inCurrentBlock(*si, block)) {
    375             ++si;
    376         } else { // combine any non-Statements or statements from a preceeding block at the beginning of this block.
    377             Q.push_back(*si);
    378             si = sources.erase(si);
    379         }
     398        if (isReachableAtEntryPoint(expr, block)) {
     399            externalVars.insert(expr);
     400        } else {
     401            internalVars.insert(expr);
     402        }
     403    }
     404
     405    circular_buffer<PabloAST *> Q(in_degree(u, G));
     406    for (auto expr : externalVars) {
     407        Q.push_back(expr);
    380408    }
    381409
    382410    const TypeId typeId = getType(G[u]);
    383     Statement * current = block.front();
     411    Statement * stmt = block.front();
    384412    if (Q.size() > 1) {
    385413        block.setInsertPoint(nullptr);
    386414        writeTree(block, typeId, Q);
    387         current = block.getInsertPoint();
    388     }
    389 
    390     unsigned distance = 0;
    391     while (current) {
    392         if (sources.count(current)) {
    393             if (distance > 2) { // write out the current Q
    394                 writeTree(block, typeId, Q);
    395             } else {
    396                 block.setInsertPoint(current);
    397             }
    398             Q.push_back(current);
     415        assert (Q.size() == 1);
     416    }
     417
     418    for (unsigned distance = 0; stmt; ++distance, stmt = stmt->getNextNode()) {
     419
     420        if (distance > 3 && Q.size() > 1) { // write out the current Q
     421            writeTree(block, typeId, Q);
     422            assert (Q.size() == 1);
     423        }
     424
     425        bool found = false;
     426        if (isa<If>(stmt)) {
     427            for (Assign * def : cast<If>(stmt)->getDefined()) {
     428                if (internalVars.erase(def) != 0) {
     429                    assert (!Q.full());
     430                    Q.push_back(def);
     431                    found = true;
     432                }
     433            }
     434        } else if (isa<While>(stmt)) {
     435            for (Next * var : cast<While>(stmt)->getVariants()) {
     436                if (internalVars.erase(var) != 0) {
     437                    assert (!Q.full());
     438                    Q.push_back(var);
     439                    found = true;
     440                }
     441            }
     442        } else if (internalVars.erase(stmt) != 0) {
     443            Q.push_back(stmt);
     444            found = true;
     445        }
     446
     447        if (found) {
     448            block.setInsertPoint(stmt);
    399449            distance = 0;
    400450        }
    401         ++distance;
    402         current = current->getNextNode();
    403     }
     451    }
     452
     453    assert (internalVars.empty());
     454
     455    block.setInsertPoint(block.back());
     456
    404457    writeTree(block, typeId, Q);
    405458    assert (Q.size() == 1);
     
    407460    assert (result);
    408461    getValue(G[u]) = result;
    409     block.setInsertPoint(block.back());
     462
    410463    return result;
    411464}
     
    427480void BooleanReassociationPass::rewriteAST(PabloBlock & block, Graph & G) {
    428481
    429     using ReadySetQueue = std::priority_queue<std::pair<unsigned, Vertex>, std::deque<std::pair<unsigned, Vertex>>, std::greater<std::pair<unsigned, Vertex>>>;
    430 
    431     raw_os_ostream out(std::cerr);
    432     out << "***************************************************\n";
    433     printGraph(G, "G_" + std::to_string((unsigned long)(&block)), out);
    434 
     482    using ReadyPair = std::pair<unsigned, Vertex>;
     483    using ReadySet = std::vector<ReadyPair>;
    435484
    436485    // Determine the bottom-up ordering of G
     
    472521    }
    473522
    474     ReadySetQueue readySet;
     523    // Compute the initial ready set
     524    ReadySet readySet;
    475525    for (const Vertex u : make_iterator_range(vertices(G))) {
    476526        if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    477             readySet.emplace(ordering[u], u);
    478         }
    479     }
    480 
    481     out << "---------------------------------------------------\n";
    482     out.flush();
     527            readySet.emplace_back(ordering[u], u);
     528        }
     529    }
     530
     531    struct {
     532        bool operator()(const ReadyPair a, const ReadyPair b) {
     533            return std::get<0>(a) > std::get<0>(b);
     534        }
     535    } readyComparator;
     536
     537    std::sort(readySet.begin(), readySet.end(), readyComparator);
    483538
    484539    // Store the original AST then clear the block
    485540    std::vector<Statement *> originalAST(block.begin(), block.end());
    486541    block.clear();
    487     flat_set<Vertex> contains;
     542    flat_set<Vertex> tested;
    488543
    489544    // Rewrite the AST using the bottom-up ordering
    490545    while (!readySet.empty()) {
    491546
     547        // Scan through the ready set to determine which one 'kills' the greatest number of inputs
     548        // NOTE: the readySet is kept in sorted "distance to sink" order; thus those closest to a
     549        // sink will be evaluated first.
     550        unsigned best = 0;
     551        auto chosen = readySet.begin();
     552        for (auto ri = readySet.begin(); ri != readySet.end(); ++ri) {
     553            const Vertex u = std::get<1>(*ri);
     554            unsigned kills = 0;
     555            for (auto ei : make_iterator_range(in_edges(u, G))) {
     556                const auto v = source(ei, G);
     557                unsigned remaining = 0;
     558                for (auto ej : make_iterator_range(out_edges(v, G))) {
     559                    const auto w = target(ej, G);
     560                    PabloAST * expr = getValue(G[w]);
     561                    if (expr == nullptr || (isa<Statement>(expr) && cast<Statement>(expr)->getParent() == nullptr)) {
     562                        if (++remaining > 1) {
     563                            break;
     564                        }
     565                    }
     566                }
     567                if (remaining < 2) {
     568                    ++kills;
     569                }
     570            }
     571            if (kills > best) {
     572                chosen = ri;
     573                best = kills;
     574            }
     575        }
    492576        Vertex u; unsigned weight;
    493         std::tie(weight, u) = readySet.top();
    494         readySet.pop();
     577        std::tie(weight, u) = *chosen;
     578        readySet.erase(chosen);
    495579
    496580        PabloAST * expr = getValue(G[u]);
    497 
    498         out << " * processing " << u << ' ';
    499         PabloPrinter::print(expr, out);
    500         out << ", weight=" << weight;
    501         out.flush();
    502581
    503582        assert (weight > 0);
     
    525604            }
    526605            // Make sure that optimization doesn't reduce this to an already written statement
    527             if (stmt->getParent()) {
    528                 goto check_ready;
    529             }
    530             block.insert(stmt);
     606            if (stmt->getParent() == nullptr) {
     607                block.insert(stmt);
     608            }
    531609            expr = stmt;
    532610        }
    533611check_ready:
    534 
    535         out << ", wrote ";
    536         PabloPrinter::print(expr, out);
    537         out << '\n';
    538         out.flush();
    539 
    540612        // mark this instruction as written
    541613        ordering[u] = 0;
     
    545617            const auto v = target(ei, G);
    546618            // since G may be a multigraph, we need to check whether we've already tested v
    547             if (contains.insert(v).second) {
     619            if (tested.insert(v).second) {
    548620                for (auto ej : make_iterator_range(in_edges(v, G))) {
    549621                    if (ordering[source(ej, G)]) {
     
    553625                }
    554626                if (ready) {
    555 
    556                     out << "   adding " << v << ' ';
    557                     PabloPrinter::print(getValue(G[v]), out);
    558                     out << " to ready set, weight=" << ordering[v] << '\n';
    559 
    560                     readySet.emplace(ordering[v], v);
    561                 }
    562             }
    563         }
    564         contains.clear();
    565 
    566         out << "---------------------------------------------------\n";
    567         out.flush();
     627                    auto entry = std::make_pair(ordering[v], v);
     628                    auto li = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator);
     629                    while (li != readySet.end()) {
     630                        auto next = li + 1;
     631                        if (next == readySet.end() || std::get<0>(*next) == ordering[v]) {
     632                            li = next;
     633                            continue;
     634                        }
     635                        break;
     636                    }
     637                    readySet.insert(li, entry);
     638                }
     639            }
     640        }
     641        tested.clear();
    568642    }
    569643
     
    573647        }
    574648    }
    575 
    576     PabloPrinter::print(block.statements(), out);
    577 
    578649}
    579650
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4860 r4861  
    33
    44#include <pablo/codegenstate.h>
    5 #include <boost/container/flat_set.hpp>
    65#include <boost/container/flat_map.hpp>
    76#include <boost/graph/adjacency_list.hpp>
Note: See TracChangeset for help on using the changeset viewer.