Ignore:
Timestamp:
Sep 18, 2015, 1:25:24 PM (4 years ago)
Author:
nmedfort
Message:

Work towards testing reassociation + multiplexing.

File:
1 edited

Legend:

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

    r4773 r4775  
    1717#include <unordered_set>
    1818#include <pablo/optimizers/pablo_simplifier.hpp>
     19#include <pablo/analysis/pabloverifier.hpp>
    1920
    2021using namespace llvm;
     
    154155
    155156        RECORD_TIMESTAMP(start_select_independent_sets);
    156         am.multiplexSelectedIndependentSets();
     157        am.multiplexSelectedIndependentSets(function);
    157158        RECORD_TIMESTAMP(end_select_independent_sets);
    158159        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
     160
     161        Simplifier::optimize(function);
    159162    }
    160163
     
    186189                // next statement of the current statement into the scope stack.
    187190                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     191                mResolvedScopes.emplace(&nested, stmt);
    188192                scope.push(stmt->getNextNode());
    189193                stmt = nested.front();
     
    928932 * @brief multiplexSelectedIndependentSets
    929933 ** ------------------------------------------------------------------------------------------------------------- */
    930 void AutoMultiplexing::multiplexSelectedIndependentSets() {
     934void AutoMultiplexing::multiplexSelectedIndependentSets(PabloFunction & function) {
    931935
    932936    const unsigned first_set = num_vertices(mConstraintGraph);
     
    940944
    941945    circular_buffer<PabloAST *> Q(max_n);
     946    flat_set<PabloBlock *> modified;
    942947
    943948    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
     
    959964            assert (i == n);
    960965
    961             PabloBlock * const block = input[0]->getParent();
     966            Advance * const adv = input[0];
     967            assert (adv);
     968            PabloBlock * const block = adv->getParent();
     969            assert (block);           
     970            PabloBuilder builder(*block);
    962971            block->setInsertPoint(block->back());
    963             PabloBuilder builder(*block);
    964             Advance * const adv = input[0];
    965972
    966973            /// Perform n-to-m Multiplexing
     
    971978                for (size_t i = 0; i != n; ++i) {
    972979                    if (((i + 1) & (1ULL << j)) != 0) {
     980                        assert (input[i]->getParent() == block);
    973981                        Q.push_back(input[i]->getOperand(0));
    974982                    }
     
    10271035                input[i]->replaceWith(demuxed, true, true);
    10281036            }
    1029         }       
    1030     }
     1037            modified.insert(block);
     1038        }
     1039    }
     1040
     1041    for (PabloBlock * block : modified) {
     1042        topologicalSort(function, *block);
     1043    }
     1044}
     1045
     1046///** ------------------------------------------------------------------------------------------------------------- *
     1047// * @brief printGraph
     1048// ** ------------------------------------------------------------------------------------------------------------- */
     1049//template <class Graph>
     1050//static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) {
     1051//    raw_os_ostream out(std::cerr);
     1052
     1053//    out << "digraph " << name << " {\n";
     1054//    for (auto u : make_iterator_range(vertices(G))) {
     1055//        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     1056//            continue;
     1057//        }
     1058//        out << "v" << u << " [label=\"" << u << ": ";
     1059//        PabloAST * const expr = G[u];
     1060//        if (isa<Statement>(expr)) {
     1061//            if (LLVM_UNLIKELY(isa<If>(expr))) {
     1062//                out << "If ";
     1063//                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
     1064//                out << ":";
     1065//            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
     1066//                out << "While ";
     1067//                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
     1068//                out << ":";
     1069//            } else {
     1070//                PabloPrinter::print(cast<Statement>(expr), "", out);
     1071//            }
     1072//        } else {
     1073//            PabloPrinter::print(expr, out);
     1074//        }
     1075//        out << "\"";
     1076//        if (!isa<Statement>(expr) || cast<Statement>(expr)->getParent() != &block) {
     1077//            out << " style=dashed";
     1078//        }
     1079//        out << "];\n";
     1080//    }
     1081//    for (auto e : make_iterator_range(edges(G))) {
     1082//        const auto s = source(e, G);
     1083//        const auto t = target(e, G);
     1084//        out << "v" << s << " -> v" << t << ";\n";
     1085//    }
     1086
     1087//    if (num_vertices(G) > 0) {
     1088
     1089//        out << "{ rank=same;";
     1090//        for (auto u : make_iterator_range(vertices(G))) {
     1091//            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     1092//                out << " v" << u;
     1093//            }
     1094//        }
     1095//        out << "}\n";
     1096
     1097//        out << "{ rank=same;";
     1098//        for (auto u : make_iterator_range(vertices(G))) {
     1099//            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     1100//                out << " v" << u;
     1101//            }
     1102//        }
     1103//        out << "}\n";
     1104
     1105//    }
     1106
     1107//    out << "}\n\n";
     1108//    out.flush();
     1109//}
     1110
     1111/** ------------------------------------------------------------------------------------------------------------- *
     1112 * @brief topologicalSort
     1113 ** ------------------------------------------------------------------------------------------------------------- */
     1114void AutoMultiplexing::topologicalSort(PabloFunction &, PabloBlock & block) const {
     1115
     1116    TopologicalGraph G;
     1117    TopologicalMap M;
     1118    // Compute the base def-use graph ...
     1119    for (Statement * stmt : block) {       
     1120        const TopologicalVertex u = getVertex(stmt, G, M);
     1121        if (isa<If>(stmt)) {
     1122            for (Assign * def : cast<const If>(stmt)->getDefined()) {
     1123                resolveUsages(u, def, block, G, M, stmt);
     1124            }
     1125        } else if (isa<While>(stmt)) {
     1126            for (Next * var : cast<const While>(stmt)->getVariants()) {
     1127                resolveUsages(u, var, block, G, M, stmt);
     1128            }
     1129        } else {
     1130            resolveUsages(u, stmt, block, G, M, nullptr);
     1131        }
     1132    }
     1133
     1134    circular_buffer<TopologicalVertex> Q(num_vertices(G));
     1135    topological_sort(G, std::back_inserter(Q));
     1136
     1137    block.setInsertPoint(nullptr);
     1138    while (!Q.empty()) {
     1139        Statement * stmt = G[Q.back()];
     1140        Q.pop_back();
     1141        if (stmt->getParent() == &block) {
     1142            block.insert(stmt);
     1143        }
     1144    }
     1145
     1146}
     1147
     1148/** ------------------------------------------------------------------------------------------------------------- *
     1149 * @brief resolveUsages
     1150 ** ------------------------------------------------------------------------------------------------------------- */
     1151void AutoMultiplexing::resolveUsages(const TopologicalVertex u, Statement * expr, PabloBlock & block, TopologicalGraph & G, TopologicalMap & M, Statement * ignoreIfThis) const {
     1152    for (PabloAST * user : expr->users()) {
     1153        if (LLVM_LIKELY(user != ignoreIfThis && isa<Statement>(user))) {
     1154            PabloBlock * parent = cast<Statement>(user)->getParent();
     1155            assert (parent);
     1156            if (LLVM_LIKELY(parent == &block)) {
     1157                add_edge(u, getVertex(cast<Statement>(user), G, M), G);
     1158            } else {
     1159                for (;;) {
     1160                    if (LLVM_UNLIKELY(parent == nullptr)) {
     1161                        assert (isa<Assign>(expr) || isa<Next>(expr));
     1162                        break;
     1163                    } else if (parent->getParent() == &block) {
     1164                        const auto f = mResolvedScopes.find(parent);
     1165                        if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
     1166                            throw std::runtime_error("Failed to resolve scope block!");
     1167                        }
     1168                        Statement * const branch = f->second;
     1169                        if (LLVM_UNLIKELY(branch != ignoreIfThis)) {
     1170                            add_edge(u, getVertex(branch, G, M), G);
     1171                        }
     1172                        break;
     1173                    }
     1174                    parent = parent->getParent();
     1175                }
     1176            }
     1177        }
     1178    }
     1179}
     1180
     1181/** ------------------------------------------------------------------------------------------------------------- *
     1182 * @brief getVertex
     1183 ** ------------------------------------------------------------------------------------------------------------- */
     1184AutoMultiplexing::TopologicalVertex AutoMultiplexing::getVertex(Statement * expr, TopologicalGraph & G, TopologicalMap & M) {
     1185    const auto f = M.find(expr);
     1186    if (f != M.end()) {
     1187        return f->second;
     1188    }
     1189    const auto u = add_vertex(expr, G);
     1190    M.emplace(expr, u);
     1191    return u;
    10311192}
    10321193
Note: See TracChangeset for help on using the changeset viewer.