Ignore:
Timestamp:
Feb 12, 2016, 4:44:35 PM (4 years ago)
Author:
nmedfort
Message:

Bug fixes

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.cpp

    r4922 r4927  
    1010#include <boost/graph/adjacency_matrix.hpp>
    1111#include <queue>
     12#include <llvm/Support/CommandLine.h>
    1213
    1314#include <pablo/printer_pablos.h>
     
    1617using namespace boost;
    1718using namespace boost::container;
     19
     20//static cl::opt<unsigned> RematerializationThreshold("factoring-remat", cl::desc("Number of registers available for factoring rematerialization"), cl::init(16));
    1821
    1922namespace pablo {
     
    454457}
    455458
    456 //inline void print(PabloAST * expr, raw_ostream & out) {
    457 //    if (isa<Statement>(expr)) {
    458 //        PabloPrinter::print(cast<Statement>(expr), out);
    459 //    } else {
    460 //        PabloPrinter::print(expr, out);
     459///** ------------------------------------------------------------------------------------------------------------- *
     460// * @brief rematerialize
     461// ** ------------------------------------------------------------------------------------------------------------- */
     462//void FactorizeDFG::rematerialize(PabloBlock * const block, LiveSet & priorSet) {
     463
     464//    LiveSet liveSet(priorSet);
     465
     466//    Statement * stmt = block->front();
     467//    block->setInsertPoint(nullptr);
     468//    while (stmt) {
     469//        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     470//            PabloAST * const op = stmt->getOperand(i);
     471//            auto f = std::find(liveSet.begin(), liveSet.end(), op);
     472//            if (f != liveSet.end()) {
     473//                liveSet.erase(f);
     474//                liveSet.push_back(op);
     475//            } else if (isa<Variadic>(op)) {
     476//                Variadic * const var = cast<Variadic>(op);
     477//                const double minimum = 4.0 + (3.0 / (double)var->getNumUses());
     478//                if ((double)(var->getNumOperands()) < minimum) {
     479//                    if (std::find(liveSet.begin(), liveSet.end(), var) == liveSet.end()) {
     480//                        // If we don't have this value in the live set, test whether it is cheaper to recompute it
     481//                        // rather than spill and reload it; if so, rematerialize the value and replace its reachable users.
     482//                        bool rematerialize = true;
     483//                        for (unsigned j = 0; j != var->getNumOperands(); ++j) {
     484//                            if (std::find(liveSet.begin(), liveSet.end(), var->getOperand(j)) == liveSet.end()) {
     485//                                rematerialize = false;
     486//                                break;
     487//                            }
     488//                        }
     489//                        if (rematerialize) {
     490//                            Variadic * replacement = nullptr;
     491//                            if (isa<And>(var)) {
     492//                                replacement = block->createAnd(var->begin(), var->end());
     493//                            } else if (isa<Or>(var)) {
     494//                                replacement = block->createOr(var->begin(), var->end());
     495//                            } else if (isa<Xor>(var)) {
     496//                                replacement = block->createXor(var->begin(), var->end());
     497//                            }
     498//                            raw_os_ostream out(std::cerr);
     499//                            out << "Remateralizing ";
     500//                            PabloPrinter::print(var, out);
     501//                            out << " as ";
     502//                            PabloPrinter::print(replacement, out);
     503//                            out << '\n';
     504//                            out.flush();
     505//                            for (PabloAST * user : var->users()) {
     506//                                if (LLVM_LIKELY(isa<Statement>(user))) {
     507//                                    PabloBlock * parent = cast<Statement>(user)->getParent();
     508//                                    while (parent) {
     509//                                        if (parent == block) {
     510//                                            stmt->replaceUsesOfWith(var, replacement);
     511//                                            break;
     512//                                        }
     513//                                        parent = parent->getParent();
     514//                                    }
     515//                                }
     516//                            }
     517//                            if (liveSet.size() > RematerializationThreshold) {
     518//                                liveSet.pop_front();
     519//                            }
     520//                            liveSet.push_back(replacement);
     521//                        }
     522//                    }
     523//                }
     524//            }
     525//        }
     526//        if (liveSet.size() > RematerializationThreshold) {
     527//            liveSet.pop_front();
     528//        }
     529//        liveSet.push_back(stmt);
     530
     531//        if (isa<If>(stmt) || isa<While>(stmt)) {
     532//            rematerialize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), liveSet);
     533//        }
     534//        block->setInsertPoint(stmt);
     535//        stmt = stmt->getNextNode();
    461536//    }
     537
     538//    // Let the prior set be an intersection between it and the current live set.
     539//    for (auto i = priorSet.begin(); i != priorSet.end(); ) {
     540//        if (LLVM_LIKELY(std::find(liveSet.begin(), liveSet.end(), *i) == liveSet.end())) {
     541//            i = priorSet.erase(i);
     542//        } else {
     543//            ++i;
     544//        }
     545//    }
     546
     547
    462548//}
    463549
     550///** ------------------------------------------------------------------------------------------------------------- *
     551// * @brief rematerialize
     552// ** ------------------------------------------------------------------------------------------------------------- */
     553//inline void FactorizeDFG::rematerialize(PabloFunction & function) {
     554//    LiveSet live;
     555//    rematerialize(function.getEntryBlock(), live);
     556//}
     557
     558
    464559/** ------------------------------------------------------------------------------------------------------------- *
    465560 * @brief lower
    466  *
    467  * The goal of this function is to try and lower a variadic operation into binary form while attempting to mitigate
    468  * register pressure under the assumption that LLVM is not going to significantly change the IR (which was observed
    469  * when assessing the ASM output of LLVM 3.6.1 using O3.)
    470  ** ------------------------------------------------------------------------------------------------------------- */
    471 inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) const {
     561 ** ------------------------------------------------------------------------------------------------------------- */
     562inline PabloAST * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) const {
    472563
    473564    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *, unsigned>;
     
    493584    M.emplace(var, operands);
    494585
    495     for (Vertex u = 0; u != operands; ++u) {
    496         PabloAST * const op = var->getOperand(u);
    497         G[u] = op;
    498         M.emplace(op, u);
     586    for (Vertex i = 0; i < operands; ++i) {
     587        PabloAST * const op = var->getOperand(i);
     588        G[i] = op;
     589        M.emplace(op, i);
    499590        assert ("AST structural error!" && (op->getNumUses() > 0));
    500591        for (PabloAST * user : op->users()) {
     
    512603                            v = f->second;
    513604                        }
    514                         G[add_edge(u, v, G).first] = 0;
     605                        G[add_edge(i, v, G).first] = 0;
    515606                        break;
    516607                    }
    517608                    usage = scope->getBranch();
     609                    assert (scope != scope->getParent());
    518610                    scope = scope->getParent();
    519611                }
     
    522614    }
    523615
    524     assert (M.count(var) == 1);
    525 
    526     unsigned estQuantum = 0;
     616    unsigned time = 0;
    527617    circular_buffer<std::pair<unsigned, Vertex>> defs(operands);
    528618    for (Statement * stmt : *block) {
     
    531621            case TypeId::Or:
    532622            case TypeId::Xor:
    533                 estQuantum += BOOLEAN_STEP;
     623                assert (stmt->getNumOperands() == 2 || stmt == var);
     624                time += BOOLEAN_STEP;
    534625                break;
    535626            case TypeId::Not:
    536                 estQuantum += NOT_STEP;
     627                time += NOT_STEP;
    537628                break;
    538629            default:
    539                 estQuantum += OTHER_STEP;
     630                time += OTHER_STEP;
    540631        }
    541632        auto f = M.find(stmt);
     
    547638            }
    548639            for (auto e : make_iterator_range(in_edges(u, G)))   {
    549                 G[e] = estQuantum;
     640                G[e] = time;
    550641            }
    551642            if (u < operands) {
    552                 defs.push_back(std::make_pair(estQuantum + DESIRED_GAP, u));
    553             }
    554         }
     643                defs.push_back(std::make_pair(time + DESIRED_GAP, u));
     644            }
     645        }
     646        assert (stmt != var);
    555647        // Annotate G to indicate when we expect a statement will be available
    556648        while (defs.size() > 0) {
    557             unsigned availQuantum = 0;
     649            unsigned avail = 0;
    558650            Vertex u = 0;
    559             std::tie(availQuantum, u) = defs.front();
    560             if (availQuantum > estQuantum) {
     651            std::tie(avail, u) = defs.front();
     652            if (avail > time) {
    561653                break;
    562654            }
     
    570662                v = f->second;
    571663            }
    572             G[add_edge(u, v, G).first] = estQuantum;
     664            G[add_edge(u, v, G).first] = time;
    573665        }
    574666    }
     
    588680
    589681    for (auto e : make_iterator_range(in_edges(operands, G)))   {
    590         G[e] = estQuantum;
     682        G[e] = time;
    591683    }
    592684
    593685    assert (num_edges(G) == var->getNumOperands());
    594 
    595 //    raw_os_ostream out(std::cerr);
    596 
    597 //    out << "==============================================================================\n";
    598 //    PabloPrinter::print(var, out); out << '\n';
    599 //    out << "------------------------------------------------------------------------------\n";
    600 
    601 //    out << "digraph G {\n";
    602 //    for (auto u : make_iterator_range(vertices(G))) {
    603 //        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    604 //            continue;
    605 //        }
    606 //        out << "v" << u << " [label=\"" << u << ": ";
    607 //        PabloPrinter::print(G[u], out);
    608 //        out << "\"];\n";
    609 //    }
    610 //    for (auto e : make_iterator_range(edges(G))) {
    611 //        const auto s = source(e, G);
    612 //        const auto t = target(e, G);
    613 //        out << "v" << s << " -> v" << t << "[label=\"" << G[e] << "\"];\n";
    614 //    }
    615 
    616 //    out << "}\n\n";
    617 //    out.flush();
    618 
    619 //    out << "------------------------------------------------------------------------------\n";
    620686
    621687    SchedulingPriorityQueue Q;
     
    623689
    624690        Graph::edge_descriptor f;
    625         unsigned quantum = std::numeric_limits<unsigned>::max();
     691        unsigned t = std::numeric_limits<unsigned>::max();
    626692        for (auto e : make_iterator_range(edges(G))) {
    627693            if (in_degree(source(e, G), G) == 0) {
    628                 if (quantum > G[e]) {
    629                     quantum = G[e];
     694                if (t > G[e]) {
     695                    t = G[e];
    630696                    f = e;
    631697                }
     
    633699        }
    634700
    635         assert ("No edge selected!" && (quantum < std::numeric_limits<unsigned>::max()));
     701        assert ("No edge selected!" && (t < std::numeric_limits<unsigned>::max()));
    636702
    637703        const auto u = source(f, G);
     
    646712        block->setInsertPoint(cast<Statement>(G[v]));
    647713        if (LLVM_LIKELY(Q.size() > 0)) {
    648             unsigned minQuantum = 0; PabloAST * op2 = nullptr;
    649             std::tie(minQuantum, op2) = Q.top();
    650             if (minQuantum < quantum) {
     714            unsigned min = 0; PabloAST * op2 = nullptr;
     715            std::tie(min, op2) = Q.top();
     716            if (min < t) {
    651717                Q.pop();
    652718                PabloAST * result = nullptr;
     
    658724                    result = block->createXor(op1, op2);
    659725                }
    660 
    661 //                out << " -- ";
    662 //                print(op1, out);
    663 //                out << " + ";
    664 //                print(op2, out);
    665 //                out << " -> ";
    666 //                print(result, out);
    667 //                out << '\n';
    668 //                out.flush();
    669 
    670726                if (LLVM_LIKELY(isa<Statement>(result))) {
    671727                    G[v] = result; // update the insertion point node value
    672                     quantum += DESIRED_GAP;
     728                    t += DESIRED_GAP;
    673729                } else {
    674730                    G[v] = cast<Statement>(op2); // update the insertion point node value
    675                     quantum = estQuantum;
    676                 }
    677                 Q.emplace(quantum, result);
     731                    t = time;
     732                }
     733                Q.emplace(t, result);
    678734                continue;
    679735            }
    680736        }
    681         Q.emplace(quantum, op1);
    682     }
    683 
    684 //    out << "------------------------------------------------------------------------------\n";
     737        Q.emplace(t, op1);
     738    }
    685739
    686740    // If we've done our best to schedule the statements and have operands remaining in our queue, generate a
     
    705759            result = block->createXor(op1, op2);
    706760        }
    707 
    708 //        out << " -- ";
    709 //        print(op1, out);
    710 //        out << " + ";
    711 //        print(op2, out);
    712 //        out << " -> ";
    713 //        print(result, out);
    714 //        out << '\n';
    715 //        out.flush();
    716 
    717761        Q.emplace(q2 + DESIRED_GAP, result);
    718762    }
    719763
    720764    assert (Q.size() == 1);
    721     return var->replaceWith(std::get<1>(Q.top()));
     765    return std::get<1>(Q.top());
    722766}
    723767
     
    730774        if (isa<If>(stmt) || isa<While>(stmt)) {
    731775            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    732         } else if ((stmt->getNumOperands() > 2) && (isa<Variadic>(stmt))) {
    733             stmt = lower(cast<Variadic>(stmt), block);
     776        } else if (LLVM_UNLIKELY(stmt->getNumOperands() > 2 && isa<Variadic>(stmt))) {
     777            PabloAST * const replacement = lower(cast<Variadic>(stmt), block);
     778            stmt = stmt->replaceWith(replacement);
     779            if (LLVM_LIKELY(isa<Variadic>(replacement))) {
     780                elevate(cast<Variadic>(replacement), block);
     781            }
    734782            continue;
    735783        }
     
    739787
    740788/** ------------------------------------------------------------------------------------------------------------- *
    741  * @brief lower
     789 * @brief elevate
    742790 ** ------------------------------------------------------------------------------------------------------------- */
    743791inline void FactorizeDFG::lower(PabloFunction & function) const {
    744792    lower(function.getEntryBlock());
     793}
     794
     795/** ------------------------------------------------------------------------------------------------------------- *
     796 * @brief noUsesOfAfter
     797 ** ------------------------------------------------------------------------------------------------------------- */
     798static bool noUsesOfAfter(const PabloAST * value, const Statement * const stmt) {
     799    if (value->getNumUses() == 1) {
     800        return true;
     801    }
     802    for (const Statement * after = stmt->getNextNode(); after; after = after->getNextNode()) {
     803        for (unsigned i = 0; i != after->getNumOperands(); ++i) {
     804            if (LLVM_UNLIKELY(after->getOperand(i) == value)) {
     805                return false;
     806            }
     807        }
     808    }
     809    return true;
     810}
     811
     812/** ------------------------------------------------------------------------------------------------------------- *
     813 * @brief elevate
     814 ** ------------------------------------------------------------------------------------------------------------- */
     815inline void FactorizeDFG::elevate(Variadic * const var, PabloBlock * block) const {
     816    assert (var->getParent() == block);
     817    const unsigned operands = var->getNumOperands();
     818    PabloAST * operand[operands];
     819    unsigned count = 0;
     820    for (unsigned i = 0; i != operands; ++i) {
     821        PabloAST * const op = var->getOperand(i);
     822        if (noUsesOfAfter(op, var)) {
     823            operand[count++] = op;
     824        }
     825    }
     826    if (count) {
     827        PabloAST * def[operands];
     828        for (unsigned i = 0; i != operands; ++i) {
     829            PabloAST * op = var->getOperand(i);
     830            if (LLVM_LIKELY(isa<Statement>(op))) {
     831                PabloBlock * scope = cast<Statement>(op)->getParent();
     832                while (scope) {
     833                    if (scope == block) {
     834                        break;
     835                    }
     836                    op = scope->getBranch();
     837                    scope = scope->getParent();
     838                }
     839            }
     840            def[i] = op;
     841        }
     842        std::sort(operand, operand + count);
     843        std::sort(def, def + operands);
     844        for (Statement * ip = var->getPrevNode(); ip; ip = ip->getPrevNode()) {
     845            if (std::binary_search(def, def + operands, ip)) {
     846                var->insertAfter(ip);
     847                return;
     848            }
     849            for (unsigned i = 0; i != ip->getNumOperands(); ++i) {
     850                if (std::binary_search(operand, operand + count, ip->getOperand(i))) {
     851                    var->insertAfter(ip);
     852                    return;
     853                }
     854            }
     855        }
     856    }
     857}
     858
     859/** ------------------------------------------------------------------------------------------------------------- *
     860 * @brief elevate
     861 ** ------------------------------------------------------------------------------------------------------------- */
     862void FactorizeDFG::elevate(PabloBlock * const block) const {
     863    Statement * stmt = block->front();
     864    while (stmt) {
     865        Statement * next = stmt->getNextNode();
     866        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     867            elevate(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     868        } else if (LLVM_LIKELY(isa<Variadic>(stmt))) {
     869            elevate(cast<Variadic>(stmt), block);
     870        }
     871        stmt = next;
     872    }
     873}
     874
     875/** ------------------------------------------------------------------------------------------------------------- *
     876 * @brief elevate
     877 ** ------------------------------------------------------------------------------------------------------------- */
     878inline void FactorizeDFG::elevate(PabloFunction & function) const {
     879    elevate(function.getEntryBlock());
    745880}
    746881
     
    799934    Simplifier::optimize(function);
    800935
     936    ldfg.elevate(function);
     937    #ifndef NDEBUG
     938    PabloVerifier::verify(function, "post-elevation");
     939    #endif
     940
    801941    ldfg.lower(function);
    802942    #ifndef NDEBUG
    803943    PabloVerifier::verify(function, "post-lowering");
    804944    #endif
    805     Simplifier::optimize(function);
    806 }
    807 
    808 }
     945}
     946
     947}
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.h

    r4922 r4927  
    77#include <pablo/pabloAST.h>
    88#include <vector>
     9#include <deque>
    910
    1011namespace pablo {
     
    2425    using BicliqueSet = std::vector<Biclique>;
    2526    using CheckSet = boost::container::flat_set<PabloAST *>;
     27    using LiveSet = std::deque<PabloAST *>;
    2628    using TypeId = PabloAST::ClassTypeId;
    2729public:
     
    4850    void factor(PabloFunction & function);
    4951
     52//    void rematerialize(PabloBlock * const block, LiveSet & priorSet);
     53//    void rematerialize(PabloFunction & function);
     54
     55    void elevate(PabloFunction & function) const;
     56    void elevate(PabloBlock * const block) const;
     57    void elevate(Variadic * const var, PabloBlock * block) const;
     58
    5059    void lower(PabloFunction & function) const;
    5160    void lower(PabloBlock * const block) const;
    52     Statement * lower(Variadic * const var, PabloBlock * block) const;
     61    PabloAST * lower(Variadic * const var, PabloBlock * block) const;
    5362
    5463    FactorizeDFG() = default;
Note: See TracChangeset for help on using the changeset viewer.