Changeset 4862


Ignore:
Timestamp:
Nov 7, 2015, 3:57:52 PM (4 years ago)
Author:
nmedfort
Message:

Bug fixes for statement scheduling in reassociation pass.

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
2 edited

Legend:

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

    r4861 r4862  
    44#include <boost/circular_buffer.hpp>
    55#include <boost/graph/adjacency_list.hpp>
    6 #include <boost/graph/filtered_graph.hpp>
    76#include <boost/graph/topological_sort.hpp>
    87#include <pablo/optimizers/pablo_simplifier.hpp>
     
    109#include <algorithm>
    1110#include <numeric> // std::iota
    12 #include <queue>
    13 #include <set>
    14 #include <pablo/printer_pablos.h>
    15 #include <iostream>
    16 #include <llvm/Support/raw_os_ostream.h>
    17 #include <boost/graph/strong_components.hpp>
    1811
    1912using namespace boost;
     
    159152}
    160153
    161 ///** ------------------------------------------------------------------------------------------------------------- *
    162 // * @brief printGraph
    163 // ** ------------------------------------------------------------------------------------------------------------- */
    164 //static void printGraph(const Graph & G, const std::string name, raw_ostream & out) {
    165 
    166 //    std::vector<unsigned> c(num_vertices(G));
    167 //    strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
    168 
    169 //    out << "digraph " << name << " {\n";
    170 //    for (auto u : make_iterator_range(vertices(G))) {
    171 //        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    172 //            continue;
    173 //        }
    174 //        out << "v" << u << " [label=\"" << u << ": ";
    175 //        PabloAST * expr;
    176 //        TypeId typeId;
    177 //        std::tie(typeId, expr) = G[u];
    178 //        bool temporary = false;
    179 //        bool error = false;
    180 //        if (expr == nullptr) {
    181 //            temporary = true;
    182 //            switch (typeId) {
    183 //                case TypeId::And:
    184 //                    out << "And";
    185 //                    break;
    186 //                case TypeId::Or:
    187 //                    out << "Or";
    188 //                    break;
    189 //                case TypeId::Xor:
    190 //                    out << "Xor";
    191 //                    break;
    192 //                default:
    193 //                    out << "???";
    194 //                    error = true;
    195 //                    break;
    196 //            }
    197 //        } else if (isMutable(G[u])) {
    198 //            if (LLVM_UNLIKELY(isa<If>(expr))) {
    199 //                out << "If ";
    200 //                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
    201 //                out << ":";
    202 //            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
    203 //                out << "While ";
    204 //                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
    205 //                out << ":";
    206 //            } else {
    207 //                PabloPrinter::print(cast<Statement>(expr), "", out);
    208 //            }
    209 //        } else {
    210 //            PabloPrinter::print(expr, out);
    211 //        }
    212 //        out << "\"";
    213 //        if (!isMutable(G[u])) {
    214 //            out << " style=dashed";
    215 //        }
    216 //        if (error) {
    217 //            out << " color=red";
    218 //        } else if (temporary) {
    219 //            out << " color=blue";
    220 //        }
    221 //        out << "];\n";
    222 //    }
    223 //    for (auto e : make_iterator_range(edges(G))) {
    224 //        const auto s = source(e, G);
    225 //        const auto t = target(e, G);
    226 //        out << "v" << s << " -> v" << t;
    227 //        bool cyclic = (c[s] == c[t]);
    228 //        if (G[e] || cyclic) {
    229 //            out << " [";
    230 //             if (G[e]) {
    231 //                out << "label=\"";
    232 //                PabloPrinter::print(G[e], out);
    233 //                out << "\" ";
    234 //             }
    235 //             if (cyclic) {
    236 //                out << "color=red ";
    237 //             }
    238 //             out << "]";
    239 //        }
    240 //        out << ";\n";
    241 //    }
    242 
    243 //    if (num_vertices(G) > 0) {
    244 
    245 //        out << "{ rank=same;";
    246 //        for (auto u : make_iterator_range(vertices(G))) {
    247 //            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    248 //                out << " v" << u;
    249 //            }
    250 //        }
    251 //        out << "}\n";
    252 
    253 //        out << "{ rank=same;";
    254 //        for (auto u : make_iterator_range(vertices(G))) {
    255 //            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    256 //                out << " v" << u;
    257 //            }
    258 //        }
    259 //        out << "}\n";
    260 
    261 //    }
    262 
    263 //    out << "}\n\n";
    264 //    out.flush();
    265 //}
    266 
    267154/** ------------------------------------------------------------------------------------------------------------- *
    268155 * @brief optimize
     
    363250    // if expr is not a statement, it's always reachable
    364251    if (isa<Statement>(expr)) {
    365         const PabloBlock * const parent = cast<Statement>(expr)->getParent();
     252        const PabloBlock * parent = cast<Statement>(expr)->getParent();
    366253        // if expr is in the current block, it's not reachable at the entry point of this block
    367254        if (parent == &block) {
     
    369256        }
    370257        const PabloBlock * current = block.getParent();
    371         // if we can find expr in a preceeding block, it's reachable
    372         while (current) {
     258        // If expr is an Assign or Next node, it must escape its block (presuming the Simplifier has eliminated any
     259        // unnecessary Assign or Next nodes.) We'll want to test whether the parent of its block is an ancestor of
     260        // the current block.
     261        if (isa<Assign>(expr) || isa<Next>(expr)) {
     262            parent = parent->getParent();
     263        }
     264        // If we can find expr in a preceeding block, it's reachable
     265        for (;;) {
    373266            if (parent == current) {
    374267                return true;
     268            }
     269            if (current == nullptr) {
     270                break;
    375271            }
    376272            current = current->getParent();
     
    525421    for (const Vertex u : make_iterator_range(vertices(G))) {
    526422        if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     423
    527424            readySet.emplace_back(ordering[u], u);
    528425        }
     
    576473        Vertex u; unsigned weight;
    577474        std::tie(weight, u) = *chosen;
    578         readySet.erase(chosen);
    579 
     475        readySet.erase(chosen);               
    580476        PabloAST * expr = getValue(G[u]);
    581477
     
    583479
    584480        if (LLVM_LIKELY(isMutable(G[u]))) {
    585             Statement * stmt = nullptr;
    586481            if (isAssociative(G[u])) {
    587                 PabloAST * replacement = createTree(block, u, G);
    588                 if (LLVM_LIKELY(inCurrentBlock(replacement, block))) {
    589                     stmt = cast<Statement>(replacement);
    590                 } else { // optimization reduced this to a Constant, Var or a prior-scope statement
    591                     getType(G[u]) = TypeId::Var;
    592                     goto check_ready;
    593                 }
    594             } else { // update any potential mappings
    595                 stmt = cast<Statement>(expr);
    596             }
    597             assert (stmt);
     482                expr = createTree(block, u, G);
     483            }
     484            assert (expr);
    598485            for (auto e : make_iterator_range(out_edges(u, G))) {
    599                 if (G[e] && G[e] != stmt) {
     486                if (G[e] && G[e] != expr) {
    600487                    if (PabloAST * user = getValue(G[target(e, G)])) {
    601                         cast<Statement>(user)->replaceUsesOfWith(G[e], stmt);
     488                        cast<Statement>(user)->replaceUsesOfWith(G[e], expr);
    602489                    }
    603490                }
    604491            }
    605492            // Make sure that optimization doesn't reduce this to an already written statement
    606             if (stmt->getParent() == nullptr) {
    607                 block.insert(stmt);
    608             }
    609             expr = stmt;
    610         }
    611 check_ready:
     493            if (LLVM_LIKELY(isa<Statement>(expr) && cast<Statement>(expr)->getParent() == nullptr)) {
     494                block.insert(cast<Statement>(expr));
     495            }
     496        }
     497
    612498        // mark this instruction as written
    613499        ordering[u] = 0;
     
    626512                if (ready) {
    627513                    auto entry = std::make_pair(ordering[v], v);
    628                     auto li = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator);
    629                     while (li != readySet.end()) {
    630                         auto next = li + 1;
    631                         if (next == readySet.end() || std::get<0>(*next) == ordering[v]) {
    632                             li = next;
    633                             continue;
    634                         }
    635                         break;
    636                     }
    637                     readySet.insert(li, entry);
     514                    auto position = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator);
     515                    readySet.insert(position, entry);
     516                    assert (std::is_sorted(readySet.cbegin(), readySet.cend(), readyComparator));
    638517                }
    639518            }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4861 r4862  
    1414    using Vertex = Graph::vertex_descriptor;
    1515    using Map = std::unordered_map<const PabloAST *, Vertex>;
    16     using WrittenAt = boost::container::flat_map<const PabloAST *, unsigned>;
    1716    using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
    1817    static bool optimize(PabloFunction & function);
Note: See TracChangeset for help on using the changeset viewer.