Changeset 4770


Ignore:
Timestamp:
Sep 14, 2015, 3:57:02 PM (3 years ago)
Author:
nmedfort
Message:

More bug-fixing work on reassociation pass.

Location:
icGREP/icgrep-devel/icgrep
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/icgrep.cpp

    r4767 r4770  
    4040#ifdef ENABLE_MULTIPLEXING
    4141#include <pablo/optimizers/pablo_automultiplexing.hpp>
     42#include <pablo/optimizers/pablo_bddminimization.h>
     43#include <pablo/optimizers/booleanreassociationpass.h>
    4244#endif
    4345#include <pablo/function.h>
     
    9698
    9799#ifdef ENABLE_MULTIPLEXING
    98 static cl::opt<bool> EnableMultiplexing("multiplexing", cl::init(true),
     100static cl::opt<bool> EnableMultiplexing("multiplexing", cl::init(false),
    99101    cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."),
    100102    cl::cat(cPabloOptimizationsOptions));
     
    241243    }
    242244#ifdef ENABLE_MULTIPLEXING
     245    pablo::BDDMinimizationPass::optimize(*function);
    243246    if (EnableMultiplexing) {
    244247        pablo::AutoMultiplexing::optimize(*function);
    245248    }
     249    pablo::BooleanReassociationPass::optimize(*function);
    246250#endif
    247251    if (PrintOptimizedREcode) {
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4769 r4770  
    66#include <boost/graph/filtered_graph.hpp>
    77#include <boost/graph/topological_sort.hpp>
    8 #include <boost/graph/strong_components.hpp>
    98#include <pablo/optimizers/pablo_simplifier.hpp>
    109#include <pablo/analysis/pabloverifier.hpp>
     
    8079
    8180inline void add_edge(PabloAST * expr, const Vertex u, const Vertex v, Graph & G) {
     81    assert (u != v);
    8282    G[add_edge(u, v, G).first] = expr;
    8383}
     
    180180}
    181181
    182 
    183182/** ------------------------------------------------------------------------------------------------------------- *
    184183 * @brief getVertex
     
    200199static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) {
    201200    raw_os_ostream out(std::cerr);
     201    std::vector<unsigned> visible(num_vertices(G), false);
    202202    out << "digraph " << name << " {\n";
    203203    for (auto u : make_iterator_range(vertices(G))) {
     
    205205            continue;
    206206        }
    207         out << "v" << u << " [label=\"";
     207        visible[u] = true;
     208
     209        out << "v" << u << " [label=\"" << u << ": ";
    208210        PabloAST * expr;
    209211        TypeId typeId;
     
    213215        if (expr == nullptr) {
    214216            temporary = true;
    215             out << u << ": ";
    216217            switch (typeId) {
    217218                case TypeId::And:
     
    229230                    break;
    230231            }
    231         } else if (isa<Statement>(expr)) {
     232        } else if (G[u].first != TypeId::Var) {
    232233            if (LLVM_UNLIKELY(isa<If>(expr))) {
    233234                out << "If ";
     
    245246        }
    246247        out << "\"";
    247         if (BooleanReassociationPass::isMutable(G[u], block) == false) {
     248        if (!BooleanReassociationPass::isMutable(G[u], block)) {
    248249            out << " style=dashed";
    249250        }
     
    256257    }
    257258    for (auto e : make_iterator_range(edges(G))) {
    258         out << "v" << source(e, G) << " -> v" << target(e, G);
     259        if (visible[source(e, G)] && visible[target(e, G)]) {
     260            out << "v" << source(e, G) << " -> v" << target(e, G);
     261        }
    259262        if (G[e]) {
    260263             out << " [label=\"";
     
    269272        out << "{ rank=same;";
    270273        for (auto u : make_iterator_range(vertices(G))) {
    271             if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     274            if (visible[u] && in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    272275                out << " v" << u;
    273276            }
     
    277280        out << "{ rank=same;";
    278281        for (auto u : make_iterator_range(vertices(G))) {
    279             if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     282            if (visible[u] && out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    280283                out << " v" << u;
    281284            }
     
    292295 * @brief createTree
    293296 ** ------------------------------------------------------------------------------------------------------------- */
    294 static Statement * createTree(PabloBlock & block, const Vertex u, Graph & G) {
    295     circular_buffer<PabloAST *> Q(in_degree(u, G));
     297static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G) {
     298    flat_set<PabloAST *> sources;
    296299    for (const auto e : make_iterator_range(in_edges(u, G))) {
    297300        PabloAST * expr = G[source(e, G)].second;
    298         assert (expr);
    299         assert (std::find(Q.begin(), Q.end(), expr) == Q.end());
    300         Q.push_back(expr);
    301     }
    302     assert (Q.size() > 1);
     301        assert ("G contains a null input variable!" && (expr != nullptr));
     302        sources.insert(expr);
     303    }
     304    circular_buffer<PabloAST *> Q(sources.begin(), sources.end());
    303305    const TypeId typeId = G[u].first;
    304306    while (Q.size() > 1) {
     
    318320        Q.push_back(expr);
    319321    }
    320     Statement * const result = cast<Statement>(Q.front());
     322    PabloAST * const result = Q.front();
     323    assert (result);
    321324    G[u].second = result;
    322325    return result;
     
    329332    Graph G;
    330333
    331     raw_os_ostream out(std::cerr);
    332     out << "============================================================\n";
    333     PabloPrinter::print(function.getEntryBlock().statements(), out);
    334     out << "------------------------------------------------------------\n";
    335     out.flush();
     334//    raw_os_ostream out(std::cerr);
     335//    out << "============================================================\n";
     336//    PabloPrinter::print(block.statements(), " > ", out);
     337//    out << "------------------------------------------------------------\n";
     338//    out.flush();
    336339
    337340    summarizeAST(block, G);
     
    345348        const Vertex u = Q.back(); Q.pop_back();
    346349        if (LLVM_LIKELY(isMutable(G[u], block))) {
    347             out << "Mutable: " << u << ": ";
    348             PabloPrinter::print(G[u].second, out);
    349             out.flush();
     350//            out << "Mutable: " << u << ": ";
     351//            PabloPrinter::print(G[u].second, out);
     352//            out << '\n';
     353//            out.flush();
    350354            Statement * stmt = nullptr;
    351355            if (isOptimizable(G[u])) {
    352                 stmt = createTree(block, u, G);
     356                PabloAST * replacement = createTree(block, u, G);
     357                if (LLVM_LIKELY(inCurrentBlock(replacement, block))) {
     358                    stmt = cast<Statement>(replacement);
     359                } else { // optimization reduced this to a Constant, Var or an outer-scope statement
     360                    continue;
     361                }
    353362            } else { // update any potential mappings
    354363                stmt = cast<Statement>(G[u].second);
    355364            }
    356365            assert (stmt);
    357             PabloPrinter::print(stmt, " -> ", out);
    358             out << '\n';
    359             out.flush();
    360             assert (stmt->getParent() == &block);
     366            assert (inCurrentBlock(stmt, block));
    361367            for (auto e : make_iterator_range(out_edges(u, G))) {
    362368                if (G[e] && G[e] != stmt) {
     
    371377    }
    372378
    373     Simplifier::deadCodeElimination(function.getEntryBlock());
    374 
    375     out << "------------------------------------------------------------\n";
    376     PabloPrinter::print(function.getEntryBlock().statements(), out);
    377     out.flush();
    378 
    379     PabloVerifier::verify(function);
     379//    Simplifier::deadCodeElimination(block);
     380
     381//    out << "------------------------------------------------------------\n";
     382//    PabloPrinter::print(block.statements(), " < ", out);
     383//    out.flush();
     384
     385//    PabloVerifier::verify(function);
    380386}
    381387
     
    531537        }
    532538    }
    533 
    534     // Test whether any operation has (A op2 B) op1 (¬A op3 C) contained within it, where op1, op2 and op3 are all
    535     // optimizable operations; if so, modify G to reflect the result. The main goal is to optimize the underlying
    536     // equations but this also eliminates a problematic case in which the internal boolean simplification logic
    537     // could detect the contradiction and return an unexpected value.
    538 
    539 //    VertexSet inputs;
    540 //    VertexSets lit;
    541 //    VertexSets neg;
    542 //    for (const Vertex t : reverse_topological_ordering) {
    543 //        if (isOptimizable(G[t])) {
    544 //            for (auto e : make_iterator_range(in_edges(t, G))) {
    545 //                const Vertex u = source(e, G);
    546 //                if (isOptimizable(G[u])) {
    547 //                    inputs.push_back(u);
    548 //                }
    549 //            }
    550 //            if (inputs.size() > 1) {
    551 //                unsigned count = 0;
    552 
    553 //                for (const Vertex u : inputs) {
    554 //                    lit[count].clear();
    555 //                    neg[count].clear();
    556 //                    for (auto ei : make_iterator_range(in_edges(u, G))) {
    557 //                        const Vertex w = source(ei, G);
    558 //                        if (isOptimizable(G[w])) {
    559 //                            lit[count].push_back(w);
    560 //                        } else if (LLVM_UNLIKELY(isNegated(G[w]))) {
    561 //                            assert (in_degree(w, G) > 0);
    562 //                            neg[count].push_back(source(first(in_edges(w, G)), G));
    563 //                        }
    564 //                    }
    565 //                    std::sort(lit[count].begin(), lit[count].end());
    566 //                    std::sort(neg[count].begin(), neg[count].end());
    567 //                    ++count;
    568 //                }
    569 
    570 
    571 //                for (unsigned i = 0; i != count; ++i) {
    572 //                    for (unsigned j = 0; j != count; ++j) {
    573 //                        VertexSet cap;
    574 //                        std::set_intersection(lit[i].begin(), lit[i].end(), neg[j].begin(), neg[j].end(), std::back_inserter(cap));
    575 
    576 
    577 //                    }
    578 //                }
    579 
    580 
    581 
    582 //            }
    583 //            inputs.clear();
    584 //        }
    585 //    }
    586539}
    587540
     
    842795void BooleanReassociationPass::redistributeAST(const PabloBlock & block, Graph & G) const {
    843796
    844     printGraph(block, G, "G0");
    845 
    846     unsigned count = 0;
     797//    printGraph(block, G, "G0");
     798
     799//    unsigned count = 0;
    847800
    848801    std::vector<Vertex> mapping(num_vertices(G) + 16);
     
    866819        }
    867820
    868         raw_os_ostream out(std::cerr);
    869         out << "DISTRIBUTION SETS: " << distributionSets.size() << '\n';
    870 
    871         ++count;
    872 
    873         unsigned subcount = 0;
    874 
    875 
     821//        raw_os_ostream out(std::cerr);
     822//        out << "DISTRIBUTION SETS: " << distributionSets.size() << '\n';
     823
     824//        ++count;
     825
     826//        unsigned subcount = 0;
    876827
    877828        for (const DistributionSet & set : distributionSets) {
     
    882833            const VertexSet & sinks = std::get<2>(set);
    883834
    884             out << "SOURCES:";
    885             for (const Vertex u : sources) {
    886                 const Vertex x = mapping[H[u]];
    887                 out << " " << x << ": "; PabloPrinter::print(G[x].second, out);
    888             }
    889             out << "\n";
    890             out << "INTERMEDIARY:";
    891             for (const Vertex u : intermediary) {
    892                 const Vertex x = mapping[H[u]];
    893                 out << " " << x << ": "; PabloPrinter::print(G[x].second, out);
    894             }
    895             out << "\n";
    896             out << "SINKS:";
    897             for (const Vertex u : sinks) {
    898                 const Vertex x = mapping[H[u]];
    899                 out << " " << x << ": "; PabloPrinter::print(G[x].second, out);
    900             }
    901             out << "\n";
    902             out.flush();
     835//            out << "SOURCES:";
     836//            for (const Vertex u : sources) {
     837//                const Vertex x = mapping[H[u]];
     838//                out << " " << x << ": "; PabloPrinter::print(G[x].second, out);
     839//            }
     840//            out << "\n";
     841//            out << "INTERMEDIARY:";
     842//            for (const Vertex u : intermediary) {
     843//                const Vertex x = mapping[H[u]];
     844//                out << " " << x << ": "; PabloPrinter::print(G[x].second, out);
     845//            }
     846//            out << "\n";
     847//            out << "SINKS:";
     848//            for (const Vertex u : sinks) {
     849//                const Vertex x = mapping[H[u]];
     850//                out << " " << x << ": "; PabloPrinter::print(G[x].second, out);
     851//            }
     852//            out << "\n";
     853//            out.flush();
    903854
    904855            const TypeId outerTypeId = G[mapping[H[sinks.front()]]].first;
     
    921872                    for (auto e : make_iterator_range(out_edges(u, G))) {
    922873                        if (target(e, G) == v) {
     874                            assert (u != v);
    923875                            remove_edge(e, G);
    924876                        }
     
    934886                    for (auto e : make_iterator_range(out_edges(u, G))) {
    935887                        if (target(e, G) == v) {
     888                            assert (u != v);
    936889                            remove_edge(e, G);
    937890                        }
     
    950903            summarizeGraph(G, mapping);
    951904
    952             printGraph(block, G, "G" + std::to_string(count) + "_" + std::to_string(++subcount));
    953         }
    954     }
    955 }
    956 
    957 }
     905//            printGraph(block, G, "G" + std::to_string(count) + "_" + std::to_string(++subcount));
     906        }
     907    }
     908}
     909
     910}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4753 r4770  
    1717#include <unordered_set>
    1818#include <pablo/optimizers/pablo_simplifier.hpp>
    19 #include <pablo/optimizers/booleanreassociationpass.h>
    2019#include <pablo/optimizers/pablo_bddminimization.h>
     20
    2121
    2222using namespace llvm;
     
    164164        RECORD_TIMESTAMP(end_topological_sort);
    165165        LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
    166 
    167         BooleanReassociationPass::optimize(function);
    168 
    169         BDDMinimizationPass::optimize(function);
    170166    }
    171167
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4751 r4770  
    1414#include <boost/container/flat_map.hpp>
    1515#include <boost/graph/adjacency_list.hpp>
     16#include <boost/graph/topological_sort.hpp>
    1617
    1718using namespace llvm;
     
    2122namespace pablo {
    2223
     24using TypeId = PabloAST::ClassTypeId;
     25
    2326bool BDDMinimizationPass::optimize(PabloFunction & function) {
    2427    BDDMinimizationPass am;
    2528    am.eliminateLogicallyEquivalentStatements(function);
     29
     30    am.shutdown();
    2631    return Simplifier::optimize(function);
    2732}
     
    5257            }
    5358            switch (stmt->getClassTypeId()) {
    54                 case PabloAST::ClassTypeId::Assign:
    55                 case PabloAST::ClassTypeId::Next:
    56                 case PabloAST::ClassTypeId::Advance:
    57                 case PabloAST::ClassTypeId::Call:
    58                 case PabloAST::ClassTypeId::MatchStar:
    59                 case PabloAST::ClassTypeId::ScanThru:
     59                case TypeId::Assign:
     60                case TypeId::Next:
     61                case TypeId::Advance:
     62                case TypeId::Call:
     63                case TypeId::MatchStar:
     64                case TypeId::ScanThru:
    6065                    variableCount++;
    6166                    break;                                   
     
    9398
    9499    eliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
    95 
    96     Cudd_Quit(mManager);
    97100}
    98101
     
    135138        stmt = stmt->getNextNode();
    136139    }   
    137     Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 1);
     140    // Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 1);
    138141}
    139142
     
    166169
    167170    switch (stmt->getClassTypeId()) {
    168         case PabloAST::ClassTypeId::Assign:
    169         case PabloAST::ClassTypeId::Next:
     171        case TypeId::Assign:
     172        case TypeId::Next:
    170173            return std::make_pair(input[0], false);
    171         case PabloAST::ClassTypeId::And:
     174        case TypeId::And:
    172175            bdd = And(input[0], input[1]);
    173176            break;
    174         case PabloAST::ClassTypeId::Or:
     177        case TypeId::Or:
    175178            bdd = Or(input[0], input[1]);
    176179            break;
    177         case PabloAST::ClassTypeId::Xor:
     180        case TypeId::Xor:
    178181            bdd = Xor(input[0], input[1]);
    179182            break;
    180         case PabloAST::ClassTypeId::Not:
     183        case TypeId::Not:
    181184            bdd = Not(input[0]);
    182185            break;
    183         case PabloAST::ClassTypeId::Sel:
     186        case TypeId::Sel:
    184187            bdd = Ite(input[0], input[1], input[2]);
    185188            break;
    186         case PabloAST::ClassTypeId::MatchStar:
    187         case PabloAST::ClassTypeId::ScanThru:
     189        case TypeId::MatchStar:
     190        case TypeId::ScanThru:
    188191            if (LLVM_UNLIKELY(input[1] == Zero())) {
    189192                return std::make_pair(Zero(), true);
    190193            }
    191         case PabloAST::ClassTypeId::Advance:
     194        case TypeId::Advance:
    192195            if (LLVM_UNLIKELY(input[0] == Zero())) {
    193196                return std::make_pair(Zero(), true);
    194197            }
    195         case PabloAST::ClassTypeId::Call:
     198        case TypeId::Call:
    196199            // TODO: we may have more than one output. Need to fix call class to allow for it.
    197200            return std::make_pair(NewVar(stmt), false);
     
    208211
    209212/** ------------------------------------------------------------------------------------------------------------- *
     213 * @brief identifyHiddenContradicionsAndTautologies
     214 *
     215 * This function attempts to scan through the AST and identify statements such as (A op2 B) op1 (¬A op3 C), where
     216 * op1, op2 and op3 are And, Or or Xor operations.
     217 ** ------------------------------------------------------------------------------------------------------------- */
     218void BDDMinimizationPass::identifyHiddenContradicionsAndTautologies(PabloBlock & block) {
     219
     220    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     221    using Vertex = Graph::vertex_descriptor;
     222    using Map = std::unordered_map<const PabloAST *, Vertex>;
     223
     224    Graph G;
     225    Map M;
     226    for (Statement * stmt : block) {
     227        const TypeId typeId = stmt->getClassTypeId();
     228        if (typeId == TypeId::And || typeId == TypeId::Or || typeId == TypeId::Xor) {
     229            const auto u = add_vertex(stmt, G);
     230            M.insert(std::make_pair(stmt, u));
     231            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     232                const auto f = M.find(stmt->getOperand(i));
     233                if (f != M.end()) {
     234                    add_edge(f->second, u, G);
     235                }
     236            }
     237        }
     238    }
     239
     240    if (num_edges(G) == 0) {
     241        return;
     242    }
     243
     244    std::vector<Vertex> ordering;
     245    ordering.reserve(num_vertices(G));
     246    topological_sort(G, std::back_inserter(ordering));
     247
     248    std::vector<unsigned> component(num_vertices(G));
     249    unsigned components = 0;
     250    for (auto u : ordering) {
     251        if (out_degree(u, G) != G[u]->users().size()) {
     252            assert (out_degree(u, G) > G[u]->users().size());
     253            component[u] = ++components;
     254        }
     255    }
     256
     257    // ....
     258
     259
     260}
     261
     262/** ------------------------------------------------------------------------------------------------------------- *
    210263 * @brief CUDD wrappers
    211264 ** ------------------------------------------------------------------------------------------------------------- */
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4748 r4770  
    4747    void eliminateLogicallyEquivalentStatements(Statement * const stmt, SubsitutionMap & map);
    4848    std::pair<DdNode *, bool> characterize(Statement * const stmt);
     49    void identifyHiddenContradicionsAndTautologies(PabloBlock & block);
    4950private:
    5051    DdNode * Zero() const;
Note: See TracChangeset for help on using the changeset viewer.