Changeset 4862

Timestamp:

Nov 7, 2015, 3:57:52 PM (3 years ago)

Author:

nmedfort

Message:

Bug fixes for statement scheduling in reassociation pass.

Location:

icGREP/icgrep-devel/icgrep/pablo/optimizers

Files:

• booleanreassociationpass.cpp (modified) (9 diffs)
• booleanreassociationpass.h (modified) (1 diff)

icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

@@ -4 +4 @@
 #include <boost/circular_buffer.hpp>
 #include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/filtered_graph.hpp>
 #include <boost/graph/topological_sort.hpp>
 #include <pablo/optimizers/pablo_simplifier.hpp>
@@ -10 +9 @@
 #include <algorithm>
 #include <numeric> // std::iota
-#include <queue>
-#include <set>
-#include <pablo/printer_pablos.h>
-#include <iostream>
-#include <llvm/Support/raw_os_ostream.h>
-#include <boost/graph/strong_components.hpp>
 
 using namespace boost;
@@ -159 +152 @@
 }
 
-///** ------------------------------------------------------------------------------------------------------------- *
-// * @brief printGraph
-// ** ------------------------------------------------------------------------------------------------------------- */
-//static void printGraph(const Graph & G, const std::string name, raw_ostream & out) {
-
-//    std::vector<unsigned> c(num_vertices(G));
-//    strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
-
-//    out << "digraph " << name << " {\n";
-//    for (auto u : make_iterator_range(vertices(G))) {
-//        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
-//            continue;
-//        }
-//        out << "v" << u << " [label=\"" << u << ": ";
-//        PabloAST * expr;
-//        TypeId typeId;
-//        std::tie(typeId, expr) = G[u];
-//        bool temporary = false;
-//        bool error = false;
-//        if (expr == nullptr) {
-//            temporary = true;
-//            switch (typeId) {
-//                case TypeId::And:
-//                    out << "And";
-//                    break;
-//                case TypeId::Or:
-//                    out << "Or";
-//                    break;
-//                case TypeId::Xor:
-//                    out << "Xor";
-//                    break;
-//                default:
-//                    out << "???";
-//                    error = true;
-//                    break;
-//            }
-//        } else if (isMutable(G[u])) {
-//            if (LLVM_UNLIKELY(isa<If>(expr))) {
-//                out << "If ";
-//                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
-//                out << ":";
-//            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
-//                out << "While ";
-//                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
-//                out << ":";
-//            } else {
-//                PabloPrinter::print(cast<Statement>(expr), "", out);
-//            }
-//        } else {
-//            PabloPrinter::print(expr, out);
-//        }
-//        out << "\"";
-//        if (!isMutable(G[u])) {
-//            out << " style=dashed";
-//        }
-//        if (error) {
-//            out << " color=red";
-//        } else if (temporary) {
-//            out << " color=blue";
-//        }
-//        out << "];\n";
-//    }
-//    for (auto e : make_iterator_range(edges(G))) {
-//        const auto s = source(e, G);
-//        const auto t = target(e, G);
-//        out << "v" << s << " -> v" << t;
-//        bool cyclic = (c[s] == c[t]);
-//        if (G[e] || cyclic) {
-//            out << " [";
-//             if (G[e]) {
-//                out << "label=\"";
-//                PabloPrinter::print(G[e], out);
-//                out << "\" ";
-//             }
-//             if (cyclic) {
-//                out << "color=red ";
-//             }
-//             out << "]";
-//        }
-//        out << ";\n";
-//    }
-
-//    if (num_vertices(G) > 0) {
-
-//        out << "{ rank=same;";
-//        for (auto u : make_iterator_range(vertices(G))) {
-//            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
-//                out << " v" << u;
-//            }
-//        }
-//        out << "}\n";
-
-//        out << "{ rank=same;";
-//        for (auto u : make_iterator_range(vertices(G))) {
-//            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
-//                out << " v" << u;
-//            }
-//        }
-//        out << "}\n";
-
-//    }
-
-//    out << "}\n\n";
-//    out.flush();
-//}
-
 /** ------------------------------------------------------------------------------------------------------------- *
  * @brief optimize
@@ -363 +250 @@
     // if expr is not a statement, it's always reachable
     if (isa<Statement>(expr)) {
-        const PabloBlock * const parent = cast<Statement>(expr)->getParent();
+        const PabloBlock * parent = cast<Statement>(expr)->getParent();
         // if expr is in the current block, it's not reachable at the entry point of this block
         if (parent == &block) {
@@ -369 +256 @@
         }
         const PabloBlock * current = block.getParent();
-        // if we can find expr in a preceeding block, it's reachable
-        while (current) {
+        // If expr is an Assign or Next node, it must escape its block (presuming the Simplifier has eliminated any
+        // unnecessary Assign or Next nodes.) We'll want to test whether the parent of its block is an ancestor of
+        // the current block.
+        if (isa<Assign>(expr) || isa<Next>(expr)) {
+            parent = parent->getParent();
+        }
+        // If we can find expr in a preceeding block, it's reachable
+        for (;;) {
             if (parent == current) {
                 return true;
+            }
+            if (current == nullptr) {
+                break;
             }
             current = current->getParent();
@@ -525 +421 @@
     for (const Vertex u : make_iterator_range(vertices(G))) {
         if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
+
             readySet.emplace_back(ordering[u], u);
         }
@@ -576 +473 @@
         Vertex u; unsigned weight;
         std::tie(weight, u) = *chosen;
-        readySet.erase(chosen);
-
+        readySet.erase(chosen);                
         PabloAST * expr = getValue(G[u]);
 
@@ -583 +479 @@
 
         if (LLVM_LIKELY(isMutable(G[u]))) {
-            Statement * stmt = nullptr;
             if (isAssociative(G[u])) {
-                PabloAST * replacement = createTree(block, u, G);
-                if (LLVM_LIKELY(inCurrentBlock(replacement, block))) {
-                    stmt = cast<Statement>(replacement);
-                } else { // optimization reduced this to a Constant, Var or a prior-scope statement
-                    getType(G[u]) = TypeId::Var;
-                    goto check_ready;
-                }
-            } else { // update any potential mappings
-                stmt = cast<Statement>(expr);
-            }
-            assert (stmt);
+                expr = createTree(block, u, G);
+            }
+            assert (expr);
             for (auto e : make_iterator_range(out_edges(u, G))) {
-                if (G[e] && G[e] != stmt) {
+                if (G[e] && G[e] != expr) {
                     if (PabloAST * user = getValue(G[target(e, G)])) {
-                        cast<Statement>(user)->replaceUsesOfWith(G[e], stmt);
+                        cast<Statement>(user)->replaceUsesOfWith(G[e], expr);
                     }
                 }
             }
             // Make sure that optimization doesn't reduce this to an already written statement
-            if (stmt->getParent() == nullptr) {
-                block.insert(stmt);
-            }
-            expr = stmt;
-        }
-check_ready:
+            if (LLVM_LIKELY(isa<Statement>(expr) && cast<Statement>(expr)->getParent() == nullptr)) {
+                block.insert(cast<Statement>(expr));
+            }
+        }
+
         // mark this instruction as written
         ordering[u] = 0;
@@ -626 +512 @@
                 if (ready) {
                     auto entry = std::make_pair(ordering[v], v);
-                    auto li = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator);
-                    while (li != readySet.end()) {
-                        auto next = li + 1;
-                        if (next == readySet.end() || std::get<0>(*next) == ordering[v]) {
-                            li = next;
-                            continue;
-                        }
-                        break;
-                    }
-                    readySet.insert(li, entry);
+                    auto position = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator);
+                    readySet.insert(position, entry);
+                    assert (std::is_sorted(readySet.cbegin(), readySet.cend(), readyComparator));
                 }
             }

icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

@@ -14 +14 @@
     using Vertex = Graph::vertex_descriptor;
     using Map = std::unordered_map<const PabloAST *, Vertex>;
-    using WrittenAt = boost::container::flat_map<const PabloAST *, unsigned>;
     using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
     static bool optimize(PabloFunction & function);