Changeset 4724 for icGREP


Ignore:
Timestamp:
Aug 12, 2015, 5:02:38 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check in

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

Legend:

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

    r4723 r4724  
    4040#include <queue>
    4141#include <unordered_map>
     42#include <pablo/printer_pablos.h>
     43#include <llvm/Analysis/PostDominators.h>
    4244
    4345using namespace pablo;
     
    9395 * @brief computePabloDependencyMetrics
    9496 ** ------------------------------------------------------------------------------------------------------------- */
    95 unsigned computePabloDependencyChainMetrics(const PabloBlock & b, std::unordered_map<const PabloAST *, unsigned> G) {
     97unsigned computePabloDependencyChainMetrics(const PabloBlock & b, std::unordered_map<const PabloAST *, unsigned> & G) {
    9698    unsigned lpl = 0;
    9799    flat_map<const PabloAST *, unsigned> L;
     
    100102        unsigned global_lpl = 0;
    101103        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    102             const auto l = L.find(stmt->getOperand(i));
     104            const PabloAST * const op = stmt->getOperand(i);
     105            if (isa<String>(op) || isa<Integer>(op)) {
     106                continue;
     107            }
     108            const auto l = L.find(op);
    103109            if (l != L.end()) {
    104110                local_lpl = std::max<unsigned>(local_lpl, l->second);
    105111            }
    106             const auto g = G.find(stmt->getOperand(i));
     112            const auto g = G.find(op);
    107113            if (LLVM_UNLIKELY(g == G.end())) {
    108114                throw std::runtime_error("Could not find dependency chain length for all operands!");
     
    128134std::pair<unsigned, unsigned> computePabloDependencyChainMetrics(const PabloFunction & f) {
    129135    std::unordered_map<const PabloAST *, unsigned> G;
     136    G.insert(std::make_pair(f.getEntryBlock().createZeroes(), 0));
     137    G.insert(std::make_pair(f.getEntryBlock().createOnes(), 0));
    130138    for (unsigned i = 0; i != f.getNumOfParameters(); ++i) {
    131139        G.insert(std::make_pair(f.getParameter(i), 0));
     
    134142    unsigned global_lpl = 0;
    135143    for (unsigned i = 0; i != f.getNumOfResults(); ++i) {
    136         assert (V.count(f.getParameter(i)));
    137         global_lpl = std::max<unsigned>(global_lpl, G[f.getResult(i)]);
     144        const auto e = G.find(f.getResult(i));
     145        if (e == G.end()) {
     146            throw std::runtime_error("No result computed!");
     147        }
     148        global_lpl = std::max<unsigned>(global_lpl, e->second);
    138149    }
    139150    return std::make_pair(global_lpl, local_lpl);
    140151}
    141152
    142 
    143153/** ------------------------------------------------------------------------------------------------------------- *
    144154 * @brief computeLLVMDependencyMetrics
    145155 ** ------------------------------------------------------------------------------------------------------------- */
    146 unsigned computeLLVMDependencyChainMetrics(const llvm::BasicBlock & b, std::unordered_map<const llvm::Value *, unsigned> G) {
     156unsigned computeLLVMDependencyChainMetrics(const DomTreeNode * t, std::unordered_map<const Value *, unsigned> & G) {
    147157    unsigned lpl = 0;
    148158    if (true) {
    149         flat_map<const llvm::Value *, unsigned> L;
    150         for (const llvm::Instruction & inst : b) {
     159        flat_map<const Value *, unsigned> L;
     160        const BasicBlock * b = t->getBlock();
     161        for (auto itr = b->rbegin(); itr != b->rend(); ++itr) {
    151162            unsigned local_lpl = 0;
    152163            unsigned global_lpl = 0;
    153             for (unsigned i = 0; i != inst.getNumOperands(); ++i) {
    154                 const auto l = L.find(inst.getOperand(i));
    155                 if (l != L.end()) {
    156                     local_lpl = std::max<unsigned>(local_lpl, l->second);
     164            const Instruction & inst = *itr;
     165            for (const Value * user : inst.users()) {
     166                if (LLVM_LIKELY(isa<Instruction>(user))) {
     167                    const auto l = L.find(user);
     168                    if (l != L.end()) {
     169                        local_lpl = std::max<unsigned>(local_lpl, l->second);
     170                    }
     171                    const auto g = G.find(user);
     172                    if (LLVM_UNLIKELY(g == G.end())) {
     173                        throw std::runtime_error("Could not find chain length for all users!");
     174                    }
     175                    global_lpl = std::max<unsigned>(global_lpl, g->second);
    157176                }
    158                 const auto g = G.find(inst.getOperand(i));
    159                 if (LLVM_UNLIKELY(g == G.end())) {
    160                     throw std::runtime_error("Could not find dependency chain length for all operands!");
    161                 }
    162                 global_lpl = std::max<unsigned>(global_lpl, g->second);
    163177            }
    164178            L.emplace(&inst, local_lpl + 1);
    165179            G.insert(std::make_pair(&inst, global_lpl + 1));
    166         }
    167         for (const auto & l : L) {
    168             lpl = std::max(lpl, l.second);
    169         }
    170     }
    171     const TerminatorInst * t = b.getTerminator();
    172     if (LLVM_LIKELY(isa<BranchInst>(t))) {
    173         for (unsigned i = t->getNumSuccessors(); i-- != 0; ) {
    174             lpl = std::max(lpl, computeLLVMDependencyChainMetrics(*(t->getSuccessor(i)), G));
    175         }
     180            lpl = std::max(lpl, local_lpl + 1);
     181        }
     182    }
     183    for (const DomTreeNode * pt : *t) {
     184        lpl = std::max(lpl, computeLLVMDependencyChainMetrics(pt, G));
    176185    }
    177186    return lpl;
     
    181190 * @brief computeLLVMDependencyMetrics
    182191 ** ------------------------------------------------------------------------------------------------------------- */
    183 std::pair<unsigned, unsigned> computeLLVMDependencyChainMetrics(const llvm::Function & f) {
     192std::pair<unsigned, unsigned> computeLLVMDependencyChainMetrics(llvm::Function & f) {
    184193    std::unordered_map<const llvm::Value *, unsigned> G;
    185     auto arg_itr = f.getArgumentList().begin();
    186     const Argument & input = *arg_itr++;
    187     input.dump();
    188     for (const auto user : input.users()) {
    189         user->dump();
     194
     195    auto itr = f.getArgumentList().begin();
     196    const Argument & input = *itr++;
     197    const Argument & output = *itr;
     198    for (const User * user : output.users()) {
    190199        G.insert(std::make_pair(user, 0));
    191200    }
    192     const unsigned local_lpl = computeLLVMDependencyChainMetrics(f.getEntryBlock(), G);
    193     const Argument & output = *arg_itr;
     201
     202    PostDominatorTree dt;
     203    dt.runOnFunction(f);
     204    const unsigned local_lpl = computeLLVMDependencyChainMetrics(dt.getRootNode(), G);
     205    dt.releaseMemory();
     206
    194207    unsigned global_lpl = 0;
    195     for (const auto user : output.users()) {
    196         user->dump();
    197         global_lpl = std::max<unsigned>(global_lpl, G[user]);
     208    for (const User * user : input.users()) {
     209        const auto e = G.find(user);
     210        if (e == G.end()) {
     211            throw std::runtime_error("No result computed!");
     212        }
     213        global_lpl = std::max<unsigned>(global_lpl, e->second);
    198214    }
    199215    return std::make_pair(global_lpl, local_lpl);
     
    226242    #ifdef ENABLE_MULTIPLEXING
    227243    if (EnableMultiplexing) {
    228         if (MultiplexingDistributionFile) {
    229             (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function.getEntryBlock());
    230         }
    231         AutoMultiplexing::optimize(function);
    232         Simplifier::optimize(function);
    233         if (MultiplexingDistributionFile) {
    234             (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function.getEntryBlock()) << '\n';
    235         }
    236244
    237245        if (LongestDependenceChainFile) {
     
    240248            Module module("tmp", getGlobalContext());
    241249            auto func = pc.compile(function, &module);
    242             const auto llvm_metrix = computeLLVMDependencyChainMetrics(func.second);
     250            const auto llvm_metrix = computeLLVMDependencyChainMetrics(*func.first);
    243251            (*LongestDependenceChainFile) << ',' << llvm_metrix.first << ',' << llvm_metrix.second;
     252        }
     253
     254        if (MultiplexingDistributionFile) {
     255            (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function.getEntryBlock());
     256        }
     257        AutoMultiplexing::optimize(function);
     258        Simplifier::optimize(function);
     259        if (MultiplexingDistributionFile) {
     260            (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function.getEntryBlock()) << '\n';
    244261        }
    245262    }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4722 r4724  
    170170//        RECORD_TIMESTAMP(end_topological_sort2);
    171171//        LOG("TopologicalSort (2):     " << (end_topological_sort2 - start_topological_sort2));
     172
    172173    }
    173174
     
    988989            const size_t m = log2_plus_one(n);
    989990            Advance * input[n];
    990             std::vector<PabloAST *> muxed(m);
     991            std::vector<Advance *> muxed(m);
    991992
    992993            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
     
    10271028                // The only way this did not return an Advance statement would be if either the mux or shift amount
    10281029                // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.               
    1029                 muxed[j] = builder.createAdvance(mux, adv->getOperand(1), prefix.str());
     1030                muxed[j] = cast<Advance>(builder.createAdvance(mux, adv->getOperand(1), prefix.str()));
    10301031            }
    10311032
     
    10871088    raw_os_ostream out(std::cerr);
    10881089
    1089     PabloPrinter::print(function.getEntryBlock(), "", out);
    1090     out << "\n+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n\n";
    1091     out.flush();
    1092 
    1093 
    10941090    // TODO: this should build a single graph and iterate by connected component instead.
    10951091    for (const auto & muxed : mMuxedVariables) {
     
    10981094        std::unordered_map<PabloAST *, unsigned> M;
    10991095        std::queue<Statement *> Q;
     1096
     1097        out << "-----------------------------------------------------------------------------------\n";
     1098        PabloPrinter::print(function.getEntryBlock().statements(), out);
     1099        out << "-----------------------------------------------------------------------------------\n"; out.flush();
     1100
    11001101
    11011102        for (unsigned i = 0; i != muxed.size(); ++i) {
     
    11261127        while (!Q.empty()) {
    11271128            Statement * const var = Q.front(); Q.pop();
     1129
     1130
    11281131            const Vertex u = M[var];
    11291132            for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     
    11611164        }
    11621165
     1166        for (auto u : make_iterator_range(vertices(G))) {
     1167            PabloAST * expr = G[u];
     1168            switch (expr->getClassTypeId()) {
     1169                case PabloAST::ClassTypeId::And:
     1170                case PabloAST::ClassTypeId::Or:
     1171                case PabloAST::ClassTypeId::Not:
     1172                case PabloAST::ClassTypeId::Sel:
     1173                    break;
     1174                default: // this vertex corresponds to a non-Boolean function. It needs to be split.
     1175                    if (in_degree(u, G) > 0 && out_degree(u, G) > 0) {
     1176                        Vertex v = add_vertex(expr, G);
     1177                        for (auto e : make_iterator_range(out_edges(u, G))) {
     1178                            add_edge(v, target(e, G), G);
     1179                        }
     1180                        clear_out_edges(u, G);
     1181                    }
     1182            }
     1183        }
     1184
     1185        out << "\ndigraph x {\n";
     1186        for (auto u : make_iterator_range(vertices(G))) {
     1187            std::string tmp;
     1188            raw_string_ostream name(tmp);
     1189            PabloPrinter::print(G[u], name);
     1190            out << "v" << u << " [label=\"" << name.str() << "\"];\n";
     1191        }
     1192        for (auto e : make_iterator_range(edges(G))) {
     1193            out << "v" << source(e, G) << " -> v" << target(e, G) << '\n';
     1194        }
     1195
     1196        out << " { rank=same;";
     1197        for (auto u : make_iterator_range(vertices(G))) {
     1198            if (in_degree(u, G) == 0) {
     1199                out << " v" << u;
     1200            }
     1201        }
     1202        out << "}\n";
     1203
     1204        out << " { rank=same;";
     1205        for (auto u : make_iterator_range(vertices(G))) {
     1206            if (out_degree(u, G) == 0) {
     1207                out << " v" << u;
     1208            }
     1209        }
     1210        out << "}\n";
     1211
     1212        out << "}\n\n";
     1213        out.flush();
     1214
    11631215        // count the number of sources (sinks) so we know how many variables (terminals) will exist in the BDD
    11641216        std::vector<Vertex> inputs;
    11651217        flat_set<Vertex> terminals;
     1218
    11661219        for (auto u : make_iterator_range(vertices(G))) {
    11671220            if (in_degree(u, G) == 0) {
     
    11751228            }
    11761229        }
     1230
     1231
     1232
    11771233
    11781234        const auto n = inputs.size();
     
    12071263                input[i] = characterization[source(e, G)];
    12081264                if (input[i] == nullptr) {
    1209                     throw std::runtime_error("Uncharacterized input!");
     1265                    std::string tmp;
     1266                    raw_string_ostream out(tmp);
     1267                    out << "Uncharacterized input! ";
     1268                    PabloPrinter::print(G[source(e, G)], out);
     1269                    throw std::runtime_error(out.str());
    12101270                }
    12111271                ++i;
     
    12361296        }
    12371297
    1238         Cudd_AutodynDisable(mManager);
    12391298        assert (Cudd_DebugCheck(mManager) == 0);
    12401299        Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);
    1241 
    1242         mSimplifyDepth = 0;
    12431300
    12441301        assert (mManager->size == nodes.size());
     
    12921349        DdNode * h = Cudd_Cofactor(mManager, f, g);
    12931350        Cudd_Ref(h);
    1294         Cudd_RecursiveDeref(mManager, g);
    12951351        PabloAST * c1 = simplifyAST(h, variables, builder);
    1296         Cudd_RecursiveDeref(mManager, h);
    12971352        if (LLVM_UNLIKELY(c1 == nullptr)) {
     1353            Cudd_RecursiveDeref(mManager, g);
     1354            Cudd_RecursiveDeref(mManager, h);
    12981355            cast<Statement>(c0)->eraseFromParent(true);
    12991356            return nullptr;
    13001357        }
    1301         return builder.createAnd(c0, c1);
     1358        assert (And(g, h) == f);
     1359        Cudd_RecursiveDeref(mManager, g);
     1360        Cudd_RecursiveDeref(mManager, h);
     1361        return builder.createAnd(c0, c1, "escf");
    13021362    }
    13031363
     
    13161376    }
    13171377
    1318     DdNode ** decomp = nullptr;
     1378    DdNode * decomp[] = { nullptr, nullptr };
    13191379    if (disjuncts == 2) {
    1320         FREE(conjunct); conjunct = nullptr; decomp = disjunct;
     1380        memcpy(decomp, disjunct, sizeof(DdNode *) * 2);
    13211381    } else if (conjuncts == 2) {
    1322         FREE(disjunct); disjunct = nullptr; decomp = conjunct;
    1323     }
    1324 
    1325     if (decomp && (decomp[0] != decomp[1]) && (decomp[0] != f) && (decomp[1] != f)) {
     1382        memcpy(decomp, conjunct, sizeof(DdNode *) * 2);
     1383    }
     1384
     1385    FREE(disjunct);
     1386    FREE(conjunct);
     1387
     1388    if ((decomp[0] != decomp[1]) && (decomp[0] != f) && (decomp[1] != f)) {
    13261389        Cudd_Ref(decomp[0]);
    13271390        Cudd_Ref(decomp[1]);
     
    13351398        PabloAST * d1 = simplifyAST(decomp[1], variables, builder);
    13361399        Cudd_RecursiveDeref(mManager, decomp[1]);
    1337         FREE(decomp);
    13381400        if (LLVM_UNLIKELY(d1 == nullptr)) {
    13391401            cast<Statement>(d0)->eraseFromParent(true);
     
    13411403        }
    13421404
    1343         std::cerr << "d0: " << (ptruint)(d0) << "  d1: " << (ptruint)(d1) << " disjunct: " << (disjunct != 0) << " conjunct: " << (conjunct != 0) << std::endl;
    1344 
    1345         if (disjunct) {
    1346             return builder.createOr(d0, d1);
     1405        if (disjuncts == 2) {
     1406            return builder.createOr(d0, d1, "disj");
    13471407        } else {
    1348             return builder.createAnd(d0, d1);
     1408            return builder.createAnd(d0, d1, "conj");
    13491409        }
    13501410    }
     
    14071467
    14081468        for (auto i = 0; i != n; ++i) {
     1469            assert (cube[i] >= 0 && cube[i] <= 2);
    14091470            if (cube[i] == 0) {
    14101471                assert (!DQ.full());
     
    14171478
    14181479        if (LLVM_UNLIKELY(DQ.empty() && CQ.empty())) {
    1419             continue;
     1480            throw std::runtime_error("Error! statement contains no elements!");
    14201481        }
    14211482
     
    14401501    Cudd_RecursiveDeref(mManager, g);
    14411502    if (LLVM_UNLIKELY(SQ.empty())) {
    1442         return nullptr;
     1503        throw std::runtime_error("Error! statement queue empty!");
    14431504    }
    14441505    while (SQ.size() > 1) {
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4722 r4724  
    3636    using VertexVector = std::vector<ConstraintVertex>;
    3737    using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;
    38     using MuxedVariables = std::vector<std::vector<PabloAST *>>;
     38    using MuxedVariables = std::vector<std::vector<Advance *>>;
    3939public:
    4040    static bool optimize(PabloFunction & function);
     
    8686    RecentCharacterizations     mRecentCharacterizations;
    8787    MuxedVariables              mMuxedVariables;
    88     unsigned                    mSimplifyDepth;
    8988};
    9089
Note: See TracChangeset for help on using the changeset viewer.