Changeset 4775


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

Work towards testing reassociation + multiplexing.

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4766 r4775  
    9797set(PRECOMPILED_FILES ${PRECOMPILED_PROPERTIES_OBJ} ${PROJECT_SOURCE_DIR}/UCD/precompiled_properties.cpp)
    9898
    99 if(ENABLE_MULTIPLEXING)
    100 set(MULTIPLEXING_FLAG -multiplexing -multiplexing-dist=${PROJECT_BINARY_DIR}/ucd-multiplexing.csv)
    101 endif()
     99#if(ENABLE_MULTIPLEXING)
     100#set(MULTIPLEXING_FLAG -multiplexing) # -multiplexing-dist=${PROJECT_BINARY_DIR}/ucd-multiplexing.csv #-ldc=ldc.csv
     101#endif()
    102102
    103103add_custom_command(OUTPUT ${PRECOMPILED_FILES}
    104104  COMMAND generate_predefined_ucd_functions
    105   ARGS -o ${PRECOMPILED_PROPERTIES_OBJ} -dir ${PROJECT_SOURCE_DIR}/UCD/ ${MULTIPLEXING_FLAG} -ldc=ldc.csv -DefaultIfHierarchy
     105  ARGS -o ${PRECOMPILED_PROPERTIES_OBJ} -dir ${PROJECT_SOURCE_DIR}/UCD/ -multiplexing -reassoc -DefaultIfHierarchy
    106106  DEPENDS generate_predefined_ucd_functions
    107107  COMMENT "Building predefined UCD functions..."
  • icGREP/icgrep-devel/icgrep/generate_predefined_ucd_functions.cpp

    r4754 r4775  
    1414#include <llvm/Support/CommandLine.h>
    1515#include <utf_encoding.h>
     16#include <pablo/analysis/pabloverifier.hpp>
    1617#include <pablo/optimizers/pablo_simplifier.hpp>
    1718#include <pablo/optimizers/pablo_codesinking.hpp>
    1819#ifdef ENABLE_MULTIPLEXING
     20#include <pablo/optimizers/pablo_bddminimization.h>
    1921#include <pablo/optimizers/pablo_automultiplexing.hpp>
    2022#endif
     23#include <pablo/optimizers/booleanreassociationpass.h>
    2124#include <llvm/IR/Verifier.h>
    2225#include <llvm/Support/Debug.h>
     
    6568                                                           clEnumValEnd));
    6669
    67 
     70static cl::opt<bool> EnableReassociation("reassoc", cl::init(false),
     71                                      cl::desc("Enable reassociation and distribution optimization of Boolean functions."), cl::Optional);
    6872
    6973
     
    238242        (*LongestDependenceChainFile) << name;
    239243    }
    240     //std::cerr << name << std::endl;
     244    std::cerr << name << std::endl;
    241245
    242246    PabloFunction * function = PabloFunction::Create(std::move(name), 8, 1);
     
    260264
    261265    #ifdef ENABLE_MULTIPLEXING
     266    BDDMinimizationPass::optimize(*function);
    262267    if (EnableMultiplexing) {
    263268        if (LongestDependenceChainFile) {
     
    279284    }
    280285    #endif
     286    if (EnableReassociation) {
     287        BooleanReassociationPass::optimize(*function);
     288    }
     289
    281290    // Now compile the function ...
    282291    llvm::Function * func = pc.compile(function, module);
  • icGREP/icgrep-devel/icgrep/icgrep.cpp

    r4774 r4775  
    224224    re_compiler.initializeRequiredStreams();
    225225    re_compiler.finalizeMatchResult(re_compiler.compile(re_ast));
    226    
     226
    227227    if (PrintCompiledREcode) {
    228228        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
     
    244244#ifdef ENABLE_MULTIPLEXING
    245245    pablo::BDDMinimizationPass::optimize(*function);
    246 //    if (EnableMultiplexing) {
    247 //        pablo::AutoMultiplexing::optimize(*function);
    248 //    }
     246    //if (EnableMultiplexing) {
     247        pablo::AutoMultiplexing::optimize(*function);
     248    //}
    249249    pablo::BooleanReassociationPass::optimize(*function);
    250250#endif
  • icGREP/icgrep-devel/icgrep/pablo/analysis/pabloverifier.cpp

    r4773 r4775  
    44#include <pablo/printer_pablos.h>
    55#include <iostream>
    6 #include <unordered_set>
     6#include <boost/container/flat_set.hpp>
    77
    88namespace pablo {
     
    2424private:
    2525    const OrderingVerifier * const mParent;
    26     std::unordered_set<const PabloAST *> mSet;
     26    boost::container::flat_set<const PabloAST *> mSet;
    2727};
    2828
    2929void isTopologicallyOrdered(const PabloBlock & block, const OrderingVerifier & parent, const bool ignoreUnusedStatements) {
    3030    OrderingVerifier ov(parent);
     31    const Statement * previousStatement = nullptr;
    3132    for (const Statement * stmt : block) {
     33        if (stmt->getPrevNode() != previousStatement) {
     34            // TODO: make this actually test whether the operand is ever defined,
     35            // or if it was defined in a scope that cannot be reached?
     36            std::string tmp;
     37            raw_string_ostream str(tmp);
     38            PabloPrinter::print(stmt, "PabloVerifier: ", str);
     39            str << " is not preceeded by the expected statement!";
     40            throw std::runtime_error(str.str());
     41        }
     42        previousStatement = stmt;
    3243        if (stmt->getNumUses() == 0 && ignoreUnusedStatements) {
    3344            continue;
     
    4859                str << "PabloVerifier: function is not topologically ordered! ";
    4960                PabloPrinter::print(stmt->getOperand(i), str);
    50                 str << " was used before definition!";
     61                PabloPrinter::print(stmt, " was used before definition by ", str);
    5162                throw std::runtime_error(str.str());
    5263            }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4774 r4775  
    2323using Graph = BooleanReassociationPass::Graph;
    2424using Vertex = Graph::vertex_descriptor;
     25using VertexData = BooleanReassociationPass::VertexData;
    2526using VertexQueue = circular_buffer<Vertex>;
    2627using Map = BooleanReassociationPass::Map;
    27 using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
    2828using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
    2929using DistributionMap = flat_map<Graph::vertex_descriptor, DistributionGraph::vertex_descriptor>;
     
    6565}
    6666
     67static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
     68    return stmt->getParent() == &block;
     69}
     70
     71static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
     72    return expr ? isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block) : true;
     73}
     74
     75inline TypeId & getType(VertexData & data) {
     76    return std::get<0>(data);
     77}
     78
     79inline TypeId getType(const VertexData & data) {
     80    return std::get<0>(data);
     81}
     82
     83inline bool isAssociative(const VertexData & data) {
     84    switch (getType(data)) {
     85        case TypeId::And:
     86        case TypeId::Or:
     87        case TypeId::Xor:
     88            return true;
     89        default:
     90            return false;
     91    }
     92}
     93
     94inline bool isDistributive(const VertexData & data) {
     95    switch (getType(data)) {
     96        case TypeId::And:
     97        case TypeId::Or:
     98            return true;
     99        default:
     100            return false;
     101    }
     102}
     103
     104inline bool isNegated(const VertexData & data) {
     105    return getType(data) == TypeId::Not && (std::get<1>(data) != nullptr);
     106}
     107
     108inline bool isMutable(const VertexData & data, const PabloBlock &) {
     109    return getType(data) != TypeId::Var;
     110}
     111
     112inline bool isNonEscaping(const VertexData & data) {
     113    return getType(data) != TypeId::Assign && getType(data) != TypeId::Next;
     114}
     115
     116inline bool isSameType(const VertexData & data1, const VertexData & data2) {
     117    return getType(data1) == getType(data2);
     118}
     119
     120/** ------------------------------------------------------------------------------------------------------------- *
     121 * @brief intersects
     122 ** ------------------------------------------------------------------------------------------------------------- */
     123template <class Type>
     124inline bool intersects(const Type & A, const Type & B) {
     125    auto first1 = A.begin(), last1 = A.end();
     126    auto first2 = B.begin(), last2 = B.end();
     127    while (first1 != last1 && first2 != last2) {
     128        if (*first1 < *first2) {
     129            ++first1;
     130        } else if (*first2 < *first1) {
     131            ++first2;
     132        } else {
     133            return true;
     134        }
     135    }
     136    return false;
     137}
     138
     139/** ------------------------------------------------------------------------------------------------------------- *
     140 * @brief intersection_count
     141 ** ------------------------------------------------------------------------------------------------------------- */
     142template <class Type>
     143inline unsigned intersection_count(const Type & A, const Type & B) {
     144    auto first1 = A.begin(), last1 = A.end();
     145    auto first2 = B.begin(), last2 = B.end();
     146    unsigned count = 0;
     147    while (first1 != last1 && first2 != last2) {
     148        if (*first1 < *first2) {
     149            ++first1;
     150        } else if (*first2 < *first1) {
     151            ++first2;
     152        } else {
     153            ++count;
     154        }
     155    }
     156    return count;
     157}
     158
    67159
    68160/** ------------------------------------------------------------------------------------------------------------- *
     
    117209    }
    118210    processScope(function, block);
    119 }
    120 
    121 /** ------------------------------------------------------------------------------------------------------------- *
    122  * @brief inCurrentBlock
    123  ** ------------------------------------------------------------------------------------------------------------- */
    124 static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
    125     return stmt->getParent() == &block;
    126 }
    127 
    128 static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
    129     return expr ? isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block) : true;
    130 }
    131 
    132 /** ------------------------------------------------------------------------------------------------------------- *
    133  * @brief isOptimizable
    134  *
    135  * And, Or and Xor instructions are all associative, commutative and distributive operations. Thus we can
    136  * safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
    137  ** ------------------------------------------------------------------------------------------------------------- */
    138 inline bool BooleanReassociationPass::isOptimizable(const VertexData & data) {
    139     switch (std::get<0>(data)) {
    140         case PabloAST::ClassTypeId::And:
    141         case PabloAST::ClassTypeId::Or:
    142         case PabloAST::ClassTypeId::Xor:
    143             return true;
    144         default:
    145             return false;
    146     }
    147 }
    148 
    149 inline bool isNegated(const BooleanReassociationPass::VertexData & data) {
    150     return (std::get<0>(data) == TypeId::Not) && (std::get<1>(data) != nullptr);
    151 }
    152 
    153 inline bool BooleanReassociationPass::isMutable(const VertexData & data, const PabloBlock &) {
    154     return (std::get<0>(data) != TypeId::Var);
    155 }
    156 
    157 inline bool BooleanReassociationPass::isNonEscaping(const VertexData & data) {
    158     return std::get<0>(data) != TypeId::Assign && std::get<0>(data) != TypeId::Next;
    159 }
    160 
    161 inline bool BooleanReassociationPass::isSameType(const VertexData & data1, const VertexData & data2) {
    162     return std::get<0>(data1) == std::get<0>(data2);
    163211}
    164212
     
    214262                    break;
    215263            }
    216         } else if (std::get<0>(G[u]) != TypeId::Var) {
     264        } else if (isMutable(G[u], block)) {
    217265            if (LLVM_UNLIKELY(isa<If>(expr))) {
    218266                out << "If ";
     
    230278        }
    231279        out << "\"";
    232         if (!BooleanReassociationPass::isMutable(G[u], block)) {
     280        if (!isMutable(G[u], block)) {
    233281            out << " style=dashed";
    234282        }
     
    287335 * @brief createTree
    288336 ** ------------------------------------------------------------------------------------------------------------- */
    289 static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G, const flat_map<const PabloAST *, unsigned> & writtenAt) {
     337PabloAST * BooleanReassociationPass::createTree(PabloBlock & block, const Vertex u, Graph & G, const WrittenAt & writtenAt) {
    290338    flat_set<PabloAST *> sources;
    291339    for (const auto e : make_iterator_range(in_edges(u, G))) {
     
    304352    });
    305353
    306     const TypeId typeId = std::get<0>(G[u]);
     354    const TypeId typeId = getType(G[u]);
    307355    while (Q.size() > 1) {
    308356        PabloAST * e1 = Q.front(); Q.pop_front();
     
    311359        // Note: this switch ought to compile to an array of function pointers to the appropriate method.
    312360        switch (typeId) {
    313             case PabloAST::ClassTypeId::And:
     361            case TypeId::And:
    314362                expr = block.createAnd(e1, e2); break;
    315             case PabloAST::ClassTypeId::Or:
     363            case TypeId::Or:
    316364                expr = block.createOr(e1, e2); break;
    317             case PabloAST::ClassTypeId::Xor:
     365            case TypeId::Xor:
    318366                expr = block.createXor(e1, e2); break;
    319367            default: break;
     
    347395
    348396    unsigned index = 0;
    349     flat_map<const PabloAST *, unsigned> writtenAt;
     397    WrittenAt writtenAt;
    350398    while (!Q.empty()) {
    351399        const Vertex u = Q.back(); Q.pop_back();
    352400        if (LLVM_LIKELY(isMutable(G[u], block))) {
    353401            Statement * stmt = nullptr;
    354             if (isOptimizable(G[u])) {
     402            if (isAssociative(G[u])) {
    355403                PabloAST * replacement = createTree(block, u, G, writtenAt);
    356404                if (LLVM_LIKELY(inCurrentBlock(replacement, block))) {
    357405                    stmt = cast<Statement>(replacement);
    358406                } else { // optimization reduced this to a Constant, Var or an outer-scope statement
    359                     std::get<0>(G[u]) = TypeId::Var;
     407                    getType(G[u]) = TypeId::Var;
    360408                    continue;
    361409                }
     
    476524 * @brief summarizeGraph
    477525 ** ------------------------------------------------------------------------------------------------------------- */
    478 inline void BooleanReassociationPass::summarizeGraph(const PabloBlock & block, Graph & G, std::vector<Vertex> & mapping) {
     526inline void BooleanReassociationPass::summarizeGraph(const PabloBlock &, Graph & G, std::vector<Vertex> & mapping) {
    479527    std::vector<Vertex> reverse_topological_ordering;
    480528    reverse_topological_ordering.reserve(num_vertices(G));
     
    484532    for (const Vertex u : reverse_topological_ordering) {
    485533        if (LLVM_LIKELY(out_degree(u, G) > 0)) {
    486             if (isOptimizable(G[u])) {
     534            if (isAssociative(G[u])) {
    487535                if (LLVM_UNLIKELY(in_degree(u, G) == 1)) {
    488536                    // We have a redundant node here that'll simply end up being a duplicate
     
    499547                    }
    500548                    clear_vertex(u, G);
    501                     std::get<0>(G[u]) = TypeId::Var;
     549                    getType(G[u]) = TypeId::Var;
    502550                    mapping[u] = v;
    503551                    continue;
     
    513561                        }
    514562                        clear_vertex(u, G);
    515                         std::get<0>(G[u]) = TypeId::Var;
     563                        getType(G[u]) = TypeId::Var;
    516564                        mapping[u] = v;
    517565                    }
     
    520568        } else if (isNonEscaping(G[u])) {
    521569            clear_in_edges(u, G);
    522             std::get<0>(G[u]) = TypeId::Var;
     570            getType(G[u]) = TypeId::Var;
    523571        }
    524572    }   
     
    529577 *
    530578 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
    531  * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an in-degree of 0
    532  * to be in bipartition A and their adjacencies to be in B.
     579 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
     580 * bipartition A and their adjacencies to be in B.
    533581  ** ------------------------------------------------------------------------------------------------------------- */
    534582template <class Graph>
     
    538586    IntersectionSets B1;
    539587    for (auto u : A) {
    540         assert (u < num_vertices(G));
    541588        if (in_degree(u, G) > 0) {
    542             VertexSet V;
    543             V.reserve(in_degree(u, G));
     589            VertexSet incomingAdjacencies;
     590            incomingAdjacencies.reserve(in_degree(u, G));
    544591            for (auto e : make_iterator_range(in_edges(u, G))) {
    545                 V.push_back(source(e, G));
    546             }
    547             std::sort(V.begin(), V.end());
    548             B1.insert(std::move(V));
     592                incomingAdjacencies.push_back(source(e, G));
     593            }
     594            std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
     595            B1.insert(std::move(incomingAdjacencies));
    549596        }
    550597    }
     
    591638    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
    592639        VertexSet Ai(A);
    593         for (const Vertex u : *Bi) {           
     640        for (const Vertex u : *Bi) {                                   
     641            VertexSet Aj;
     642            Aj.reserve(out_degree(u, G));
     643            for (auto e : make_iterator_range(out_edges(u, G))) {
     644                Aj.push_back(target(e, G));
     645            }
     646            std::sort(Aj.begin(), Aj.end());
    594647            VertexSet Ak;
    595             if (out_degree(u, G) > 0) {
    596                 VertexSet Aj;
    597                 Aj.reserve(out_degree(u, G));
    598                 for (auto e : make_iterator_range(out_edges(u, G))) {
    599                     Aj.push_back(target(e, G));
    600                 }
    601                 std::sort(Aj.begin(), Aj.end());
    602                 std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
    603             }
     648            Ak.reserve(std::min(Ai.size(), Aj.size()));
     649            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
    604650            Ai.swap(Ak);
    605651        }
     652        assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
    606653        cliques.emplace_back(std::move(Ai), std::move(*Bi));
    607654    }
    608655    return std::move(cliques);
    609 }
    610 
    611 /** ------------------------------------------------------------------------------------------------------------- *
    612  * @brief intersects
    613  ** ------------------------------------------------------------------------------------------------------------- */
    614 template <class Type>
    615 inline bool intersects(const Type & A, const Type & B) {
    616     auto first1 = A.begin(), last1 = A.end();
    617     auto first2 = B.begin(), last2 = B.end();
    618     while (first1 != last1 && first2 != last2) {
    619         if (*first1 < *first2) {
    620             ++first1;
    621         } else if (*first2 < *first1) {
    622             ++first2;
    623         } else {
    624             return true;
    625         }
    626     }
    627     return false;
    628656}
    629657
     
    738766void generateDistributionGraph(const Graph & G, DistributionGraph & H) {
    739767    DistributionMap M;
    740     for (const Vertex u : make_iterator_range(vertices(G))) {
    741         const TypeId outerTypeId = std::get<0>(G[u]);
    742         if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
     768    for (const Vertex u : make_iterator_range(vertices(G))) {       
     769        if (isDistributive(G[u])) {
     770            const TypeId outerTypeId = getType(G[u]);
    743771            const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
    744772            flat_set<Vertex> distributable;
    745773            for (auto e : make_iterator_range(in_edges(u, G))) {
    746774                const Vertex v = source(e, G);
    747                 if (LLVM_UNLIKELY(std::get<0>(G[v]) == innerTypeId)) {
     775                if (LLVM_UNLIKELY(getType(G[v]) == innerTypeId)) {
    748776                    bool safe = true;
    749777                    for (const auto e : make_iterator_range(out_edges(v, G))) {
    750                         if (std::get<0>(G[target(e, G)]) != outerTypeId) {
     778                        if (getType(G[target(e, G)]) != outerTypeId) {
    751779                            safe = false;
    752780                            break;
     
    830858            const VertexSet & sinks = std::get<2>(set);
    831859
    832             const TypeId outerTypeId = std::get<0>(G[mapping[H[sinks.front()]]]);
     860            const TypeId outerTypeId = getType(G[mapping[H[sinks.front()]]]);
    833861            assert (outerTypeId == TypeId::And || outerTypeId == TypeId::Or);
    834862            const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or;
     
    843871            for (const Vertex i : intermediary) {
    844872                const auto u = mapping[H[i]];
    845                 assert (std::get<0>(G[u]) == innerTypeId);
     873                assert (getType(G[u]) == innerTypeId);
    846874                for (const Vertex t : sinks) {
    847                     assert (std::get<0>(G[mapping[H[t]]]) == outerTypeId);
     875                    assert (getType(G[mapping[H[t]]]) == outerTypeId);
    848876                    remove_edge(u, mapping[H[t]], G);
    849877                }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4774 r4775  
    1515    using Vertex = Graph::vertex_descriptor;
    1616    using Map = std::unordered_map<const PabloAST *, Vertex>;
     17    using WrittenAt = boost::container::flat_map<const PabloAST *, unsigned>;
     18    using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
    1719
    1820    static bool optimize(PabloFunction & function);
     
    2931    void redistributeAST(const PabloBlock & block, Graph & G) const;
    3032    void rewriteAST(PabloBlock & block, Graph & G);
    31 public:
    32     static bool isOptimizable(const VertexData & data);
    33     static bool isMutable(const VertexData & data, const PabloBlock &block);
    34     static bool isNonEscaping(const VertexData & data);
    35     static bool isSameType(const VertexData & data1, const VertexData & data2);
     33    static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G, const WrittenAt & writtenAt);
    3634    static Vertex getSummaryVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block);
    3735private:
    38     boost::container::flat_map<PabloBlock *, Statement *> mResolvedScopes;
     36    ScopeMap mResolvedScopes;
    3937};
    4038
  • 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
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4773 r4775  
    3535    using VertexVector = std::vector<ConstraintVertex>;
    3636    using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;
     37    using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
     38    using TopologicalGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, Statement *>;
     39    using TopologicalVertex = TopologicalGraph::vertex_descriptor;
     40    using TopologicalMap = boost::container::flat_map<const Statement *, TopologicalVertex>;
    3741public:
    3842    static bool optimize(PabloFunction & function);
    3943protected:
    4044    bool initialize(PabloFunction & function);
    41     void characterize(PabloBlock &block);
     45    void characterize(PabloBlock & block);
    4246    DdNode * characterize(Statement * const stmt);
    4347    DdNode * characterize(Advance * adv, DdNode * input);
     
    4751    void selectMultiplexSets(RNG &);
    4852    void applySubsetConstraints();
    49     void multiplexSelectedIndependentSets();
     53    void multiplexSelectedIndependentSets(PabloFunction & function);
     54    void topologicalSort(PabloFunction & function, PabloBlock & block) const;
     55    void resolveUsages(const TopologicalVertex u, Statement * expr, PabloBlock & block, TopologicalGraph & G, TopologicalMap & M, Statement * ignoreIfThis) const;
     56    static TopologicalVertex getVertex(Statement * expr, TopologicalGraph & G, TopologicalMap & M);
     57
    5058    inline AutoMultiplexing()
    5159    : mVariables(0)
     
    7987    MultiplexSetGraph           mMultiplexSetGraph;
    8088    RecentCharacterizations     mRecentCharacterizations;
     89    ScopeMap                    mResolvedScopes;
    8190};
    8291
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4774 r4775  
    143143                map.insert(bdd, stmt);
    144144            }
    145             mCharacterizationMap.insert(std::make_pair(stmt, bdd));
     145            mCharacterizationMap.emplace(stmt, bdd);
    146146        }
    147147        stmt = stmt->getNextNode();
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4774 r4775  
    22#define PABLO_BDDMINIMIZATION_H
    33
    4 #include <unordered_map>
     4#include <boost/container/flat_map.hpp>
    55#include <vector>
    66
     
    1818class BDDMinimizationPass {
    1919
    20     using CharacterizationMap = std::unordered_map<const PabloAST *, DdNode *>;
     20    using CharacterizationMap = boost::container::flat_map<const PabloAST *, DdNode *>;
    2121    using Terminals = std::vector<Statement *>;
    2222
     
    3333
    3434        void insert(const DdNode * node, PabloAST * stmt) {
    35             mMap.insert(std::make_pair(node, stmt));
     35            mMap.emplace(node, stmt);
    3636        }
    3737    private:
    3838        const SubsitutionMap * const mParent;
    39         std::unordered_map<const DdNode *, PabloAST *> mMap;
     39        boost::container::flat_map<const DdNode *, PabloAST *> mMap;
    4040    };
    4141
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4774 r4775  
    9797                if (assign->getNumUses() == 0) {
    9898                    stmt = assign->eraseFromParent();
    99                 }
    100                 else {
     99                } else {
    101100                    stmt = assign->replaceWith(assign->getExpression(), true, true);
    102101                }
     
    213212            const auto f = encountered.findOrAdd(stmt);
    214213            if (!std::get<1>(f)) {
    215                 stmt = stmt->replaceWith(std::get<0>(f));
     214                stmt = stmt->replaceWith(std::get<0>(f), true, true);
    216215                continue;
    217216            }
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4774 r4775  
    286286#endif
    287287
     288bool StatementList::contains(Statement * const statement) {
     289    for (Statement * stmt : *this) {
     290        if (statement == stmt) {
     291            return true;
     292        }
     293    }
     294    return false;
     295}
     296
    288297StatementList::~StatementList() {
    289298
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4774 r4775  
    486486
    487487    inline void setInsertPoint(Statement * const statement) {
     488        assert (statement == nullptr || contains(statement));
    488489        mInsertionPoint = statement;
    489490    }
     
    494495
    495496    ~StatementList();
     497
     498    bool contains(Statement * const statement);
    496499
    497500private:
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.cpp

    r4769 r4775  
    6868    }
    6969    else if (const Assign * an = dyn_cast<const Assign>(stmt)) {
    70 //        if (an->isOutputAssignment()) {
    71 //            strm << "output.";
    72 //        }
    7370        strm << an->getName() << " = ";
    7471        print(an->getExpression(), strm);
     
    191188
    192189void PabloPrinter::print(const PabloAST * expr, llvm::raw_ostream & strm) {
     190    strm.write_hex((unsigned long long)expr) << " ";
    193191    if (expr == nullptr) {
    194192        strm << "<null-expr>";
Note: See TracChangeset for help on using the changeset viewer.