Ignore:
Timestamp:
Sep 8, 2015, 9:44:05 AM (4 years ago)
Author:
nmedfort
Message:

More work on reassociation pass

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

Legend:

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

    r4753 r4764  
    318318SET(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS} -O3 -DNDEBUG")
    319319IF (${CMAKE_SYSTEM} MATCHES "Linux")
    320     SET(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS} -g -fsanitize=address")
     320    SET(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS} -g") # -fsanitize=address
    321321ENDIF()
    322322
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4763 r4764  
    3232    BooleanReassociationPass brp;
    3333
     34    raw_os_ostream out(std::cerr);
     35
     36    out << "BEFORE:\n";
     37    PabloPrinter::print(function.getEntryBlock().statements(), out);
     38    out << "----------------------------------------------------------\n";
     39    out.flush();
     40
    3441    brp.resolveScopes(function);
    3542    brp.processScopes(function);
    3643    Simplifier::optimize(function);
     44
     45    out << "AFTER:\n";
     46    PabloPrinter::print(function.getEntryBlock().statements(), out);
    3747
    3848    return true;
     
    90100
    91101/** ------------------------------------------------------------------------------------------------------------- *
    92  * @brief is_power_of_2
    93  * @param n an integer
    94  ** ------------------------------------------------------------------------------------------------------------- */
    95 static inline bool is_power_of_2(const size_t n) {
    96     return ((n & (n - 1)) == 0);
    97 }
    98 
    99 /** ------------------------------------------------------------------------------------------------------------- *
    100  * @brief log2_plus_one
    101  ** ------------------------------------------------------------------------------------------------------------- */
    102 static inline size_t ceil_log2(const size_t n) {
    103     return std::log2<size_t>(n) + (is_power_of_2(n) ? 0 : 1);
    104 }
    105 
    106 /** ------------------------------------------------------------------------------------------------------------- *
    107102 * @brief isOptimizable
    108103 *
     
    133128}
    134129
    135 ///** ------------------------------------------------------------------------------------------------------------- *
    136 // * @brief isCutNecessary
    137 // ** ------------------------------------------------------------------------------------------------------------- */
    138 //static inline bool isCutNecessary(const Vertex u, const Vertex v, const Graph & G, const std::vector<unsigned> & component) {
    139 //    // Either this edge crosses a component boundary or the operations performed by the vertices differs, we need to cut
    140 //    // the graph here and generate two partial equations.
    141 //    if (LLVM_UNLIKELY(component[u] != component[v])) {
    142 //        return true;
    143 //    } else if (LLVM_UNLIKELY((in_degree(u, G) != 0) && (G[u]->getClassTypeId() != G[v]->getClassTypeId()))) {
    144 //        return true;
    145 //    }
    146 //    return false;
    147 //}
    148 
    149 ///** ------------------------------------------------------------------------------------------------------------- *
    150 // * @brief push
    151 // ** ------------------------------------------------------------------------------------------------------------- */
    152 //static inline void push(const Vertex u, VertexQueue & Q) {
    153 //    if (LLVM_UNLIKELY(Q.full())) {
    154 //        Q.set_capacity(Q.capacity() * 2);
    155 //    }
    156 //    Q.push_back(u);
    157 //    assert (Q.back() == u);
    158 //}
    159 
    160 ///** ------------------------------------------------------------------------------------------------------------- *
    161 // * @brief pop
    162 // ** ------------------------------------------------------------------------------------------------------------- */
    163 //static inline Vertex pop(VertexQueue & Q) {
    164 //    assert (!Q.empty() && "Popping an empty vertex queue");
    165 //    const Vertex u = Q.front();
    166 //    Q.pop_front();
    167 //    return u;
    168 //}
    169 
    170130/** ------------------------------------------------------------------------------------------------------------- *
    171131 * @brief getVertex
    172132 ** ------------------------------------------------------------------------------------------------------------- */
    173133template<typename ValueType, typename GraphType, typename MapType>
    174 static inline Vertex getVertex(ValueType value, GraphType & G, MapType & M) {
    175     assert (value);
     134static inline Vertex getVertex(const ValueType value, GraphType & G, MapType & M) {
    176135    const auto f = M.find(value);
    177136    if (f != M.end()) {
     
    339298
    340299    summarizeAST(block, G);
    341 //    redistributeAST(block, G);
    342 
    343 
    344     raw_os_ostream out(std::cerr);
    345 
    346     out << "BEFORE:\n";
    347     PabloPrinter::print(block.statements(), out);
    348     out << "----------------------------------------------------------\n";
    349     out.flush();
    350 
     300    redistributeAST(block, G);
    351301
    352302    circular_buffer<Vertex> Q(num_vertices(G));
     
    363313            if (isOptimizable(expr)) {
    364314                if (in_degree(u, G) == 0) {
    365                     PabloPrinter::print(cast<Statement>(expr), " erasing ", out); out << '\n';
    366                     cast<Statement>(expr)->eraseFromParent(true);
     315                    cast<Statement>(expr)->eraseFromParent(false);
    367316                    continue;
    368317                } else {
     
    376325                    PabloAST * replacement = createTree(block, expr->getClassTypeId(), nodes);
    377326
    378                     PabloPrinter::print(cast<Statement>(expr), " replacing ", out);
    379                     PabloPrinter::print(cast<Statement>(replacement), " with ", out);
    380                     out << '\n';
    381 
    382                     cast<Statement>(expr)->replaceWith(replacement, true, true);
     327                    cast<Statement>(expr)->replaceWith(replacement, true, false);
    383328                    expr = replacement;
    384                 }
    385             }
    386 
    387             PabloPrinter::print(cast<Statement>(expr), "    -> ", out);
    388             out << '\n';
    389 
     329                    G[u] = replacement;
     330                }
     331            }
    390332            block.insert(cast<Statement>(expr));
    391333        }
    392334    }
    393 
    394     out << "----------------------------------------------------------\n";
    395     out << "AFTER:\n";
    396     PabloPrinter::print(block.statements(), out);
    397     out.flush();
    398     out << "==========================================================\n";
    399335}
    400336
     
    424360                const Vertex v = getVertex(def, G, M);
    425361                add_edge(u, v, G);
    426                 annotateUseDefs(v, def, block, G, M);
     362                resolveUsages(v, def, block, G, M);
    427363            }
    428364        } else if (isa<While>(stmt)) {
     
    430366                const Vertex v = getVertex(var, G, M);
    431367                add_edge(u, v, G);
    432                 annotateUseDefs(v, var, block, G, M);
     368                resolveUsages(v, var, block, G, M);
    433369            }
    434370        } else {
    435             annotateUseDefs(u, stmt, block, G, M);
     371            resolveUsages(u, stmt, block, G, M);
    436372        }
    437373    }
     
    459395        }
    460396    }
    461 
    462     printGraph(block, G, "G");
    463 
    464 }
    465 
    466 /** ------------------------------------------------------------------------------------------------------------- *
    467  * @brief annotateUseDefs
    468  ** ------------------------------------------------------------------------------------------------------------- */
    469 void BooleanReassociationPass::annotateUseDefs(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const {
     397}
     398
     399/** ------------------------------------------------------------------------------------------------------------- *
     400 * @brief resolveUsages
     401 ** ------------------------------------------------------------------------------------------------------------- */
     402void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const {
    470403    for (PabloAST * user : expr->users()) {
    471404        assert (user);
    472         if (LLVM_UNLIKELY(user == expr)) {
    473             continue;
    474         }
    475         if (LLVM_LIKELY(isa<Statement>(user))) {
     405        if (LLVM_LIKELY(user != expr && isa<Statement>(user))) {
    476406            PabloBlock * parent = cast<Statement>(user)->getParent();
    477407            assert (parent);
    478408            if (LLVM_UNLIKELY(parent != &block)) {
    479                 #ifndef NDEBUG
    480                 bool found = false;
    481                 for (Statement * test : *parent) {
    482                     if (test == user) {
    483                         found = true;
    484                         break;
    485                     }
    486                 }
    487                 assert ("Could not locate user in its recorded scope block!" && found);
    488                 #endif
    489409                for (;;) {
    490410                    if (LLVM_UNLIKELY(parent == nullptr)) {
     
    889809        }
    890810
    891         segmentInto3LevelGraph(H);
    892 
    893         const VertexSets distributionSets = safeDistributionSets(H);
    894 
    895         printGraph(block, H, G, "H");
     811        printGraph(block, H, G, "H1");
     812
     813        const VertexSets distributionSets = safeDistributionSets(segmentInto3LevelGraph(H));
     814
     815        printGraph(block, H, G, "H2");
    896816
    897817        // If no sources remain, no bicliques were found that would have a meaningful impact on the AST.
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4763 r4764  
    1212    using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *>;
    1313    using Vertex = Graph::vertex_descriptor;
    14     using Map = std::unordered_map<PabloAST *, Vertex>;
     14    using Map = std::unordered_map<const PabloAST *, Vertex>;
    1515
    1616    static bool optimize(PabloFunction & function);
     
    2323    void processScope(PabloBlock & block, std::vector<Statement *> && terminals);
    2424    void summarizeAST(PabloBlock & block, Graph & G) const;
    25     void annotateUseDefs(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const;
     25    void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const;
    2626    bool redistributeAST(PabloBlock & block, Graph & G) const;
    2727private:
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4763 r4764  
    44#include <pablo/function.h>
    55#include <pablo/printer_pablos.h>
     6#include <unordered_map>
    67#include <iostream>
    7 
    88
    99namespace pablo {
     
    332332}
    333333
    334 
    335334Simplifier::Simplifier()
    336335{
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.cpp

    r4650 r4764  
    2121    // of it.
    2222
    23     for (PabloAST * assign : mDefined) {
    24         assign->addUser(this);
    25         addUser(assign);
     23    for (PabloAST * def : mDefined) {
     24        def->addUser(this);
     25        addUser(def);
    2626    }
    2727}
     
    3232, mDefined(definedVars.begin(), definedVars.end(), reinterpret_cast<DefinedAllocator &>(mVectorAllocator))
    3333{
    34     for (PabloAST * assign : mDefined) {
    35         assign->addUser(this);
    36         addUser(assign);
     34    for (PabloAST * def : mDefined) {
     35        def->addUser(this);
     36        addUser(def);
    3737    }
    3838}
    3939
     40void If::addDefined(Assign * def) {
     41    if (LLVM_LIKELY(std::find(mDefined.begin(), mDefined.end(), def) != mDefined.end())) {
     42        const auto size = mDefined.size();
     43        mDefined.push_back(def);
     44        assert (mDefined.size() == size + 1);
     45        assert (mDefined.back() == def);
     46        def->addUser(this);
     47        addUser(def);
     48    }
     49}
    4050
    4151}
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.h

    r4650 r4764  
    4444        return mDefined;
    4545    }
     46    void addDefined(Assign * def);
    4647protected:
    4748    inline DefinedVars & getDefined() {
Note: See TracChangeset for help on using the changeset viewer.