Changeset 4804

Timestamp:

Sep 28, 2015, 2:39:59 PM (2 years ago)

Author:

nmedfort

Message:

Bug fixes

Location:

icGREP/icgrep-devel/icgrep

Files:

• UCD/ucd_compiler.cpp (modified) (4 diffs)
• UCD/ucd_compiler.hpp (modified) (1 diff)
• icgrep-devel.config (modified) (1 diff)
• pablo/analysis/pabloverifier.cpp (modified) (2 diffs)
• pablo/optimizers/booleanreassociationpass.cpp (modified) (2 diffs)
• pablo/optimizers/pablo_bddminimization.cpp (modified) (2 diffs)
• pablo/optimizers/pablo_bddminimization.h (modified) (1 diff)
• pablo/optimizers/pablo_codesinking.cpp (modified) (3 diffs)
• pablo/optimizers/pablo_simplifier.cpp (modified) (4 diffs)

icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.cpp

@@ -9 +9 @@
 
 namespace UCD {
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief addTarget
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline void UCDCompiler::addTarget(const UnicodeSet & set) {
+    mTargetMap.emplace(&set, PabloBlock::createZeroes());
+}
 
 /** ------------------------------------------------------------------------------------------------------------- *
@@ -89 +96 @@
             }
         }
-        for (Target t : nonIntersectingTargets) {
-            mTargetMap.insert(t);
+        for (const Target t : nonIntersectingTargets) {
+            mTargetMap.emplace(t.first, t.second);
         }
     }
@@ -99 +106 @@
  ** ------------------------------------------------------------------------------------------------------------- */
 void UCDCompiler::generateSubRanges(const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder) {
-    for (Target & t : mTargetMap) {
+    for (auto & t : mTargetMap) {
         const auto range = rangeIntersect(*t.first, lo, hi);
         PabloAST * target = t.second;
@@ -354 +361 @@
     }
     return ranges;
-}
-
-/** ------------------------------------------------------------------------------------------------------------- *
- * @brief addTarget
- ** ------------------------------------------------------------------------------------------------------------- */
-inline void UCDCompiler::addTarget(const UnicodeSet & set) {
-#ifdef USE_BOOST
-    mTargetMap.emplace(&set, PabloBlock::createZeroes());
-#else
-    mTargetMap.insert(std::make_pair(&set, PabloBlock::createZeroes()));
-#endif
 }
 

icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.hpp

@@ -35 +35 @@
     using TargetMap = std::unordered_map<const UnicodeSet *, PabloAST *>;
     #endif
-    using Target = TargetMap::value_type;
+    using Target = std::pair<const UnicodeSet *, PabloAST *>;
     using TargetVector = std::vector<Target>;
 

icGREP/icgrep-devel/icgrep/icgrep-devel.config

@@ -1 @@
-#define USE_BOOST
-#define USE_BOOST_MMAP

icGREP/icgrep-devel/icgrep/pablo/analysis/pabloverifier.cpp

@@ -4 +4 @@
 #include <pablo/printer_pablos.h>
 #include <iostream>
+#ifdef USE_BOOST
 #include <boost/container/flat_set.hpp>
-#include <boost/container/flat_map.hpp>
-
-using namespace boost::container;
+#else
+#include <unordered_set>
+#endif
 
 namespace pablo {
 
-using ScopeSet = flat_set<const PabloBlock *>;
+#ifdef USE_BOOST
+template <typename Type>
+using SmallSet = boost::container::flat_set<Type>;
+#else
+template <typename Type>
+using SmallSet = std::unordered_set<Type>;
+#endif
+
+using ScopeSet = SmallSet<const PabloBlock *>;
 
 /** ------------------------------------------------------------------------------------------------------------- *
@@ -202 +211 @@
 private:
     const OrderingVerifier * const mParent;
-    boost::container::flat_set<const PabloAST *> mSet;
+    SmallSet<const PabloAST *> mSet;
 };
 

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

@@ -6 +6 @@
 #include <boost/graph/filtered_graph.hpp>
 #include <boost/graph/topological_sort.hpp>
-#include <boost/graph/strong_components.hpp>
 #include <pablo/optimizers/pablo_simplifier.hpp>
 #include <pablo/analysis/pabloverifier.hpp>
@@ -124 +123 @@
         default:
             return false;
-    }
-}
-
-inline bool isConstant(const VertexData & data) {
-    switch (getType(data)) {
-        case TypeId::Zeroes:
-        case TypeId::Ones:
-            return true;
-        default: return false;
     }
 }

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

@@ -2 +2 @@
 #include <pablo/codegenstate.h>
 #include <pablo/builder.hpp>
-#include <stack>
-#include <iostream>
 #include <pablo/printer_pablos.h>
 #include <cudd.h>
-#include <cuddInt.h>
 #include <util.h>
-#include <queue>
-#include <boost/circular_buffer.hpp>
 #include <pablo/optimizers/pablo_simplifier.hpp>
 #include <pablo/analysis/pabloverifier.hpp>
+#include <stack>
 
 using namespace llvm;
@@ -117 +113 @@
             }
         } else { // attempt to characterize this statement and replace it if we've encountered an equivalent one
+
+            /// TODO: I found evidence that some of the UCD functions have disjunctions of nested marker values
+            /// in which one is a superset of the other. It's not safe to eliminate the subset marker unless the
+            /// condition that lead us to compute the first marker is a superset of the condition that let us
+            /// compute the subset value too. We can alter the superset condition to include the union of both
+            /// but this may lead to taking an expensive branch more often. So, we'd need to decide whether the
+            /// cost of each scope is close enough w.r.t. the probability both branches are taken.
+
             DdNode * bdd = nullptr;
             bool test = false;

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

@@ -48 +48 @@
     void eliminateLogicallyEquivalentStatements(Statement * const stmt, SubsitutionMap & map);
     std::pair<DdNode *, bool> characterize(Statement * const stmt);
-    void identifyHiddenContradicionsAndTautologies(PabloBlock & block);
 private:
     DdNode * Zero() const;

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

@@ -58 +58 @@
 
             ScopeSet scopes;
-            bool canSinkInstruction = false;
+            bool sinkable = false;
             for (const PabloAST * use : stmt->users()) {
                 if (const Statement * user = dyn_cast<Statement>(use)) {
                     if (mProcessed.count(user->getParent())) {
-                        canSinkInstruction = true;
+                        sinkable = true;
                         scopes.insert(user->getParent());
                         continue;
                     }
-                    canSinkInstruction = false;
+                    sinkable = false;
                     break;
                 }
             }
-            if (canSinkInstruction) {
+            if (sinkable) {
 
                 while (scopes.size() > 1) {
@@ -102 +102 @@
                     // But if the LCA is the current block, we can't sink the statement.
                     if (scope1 == &block) {
-                        canSinkInstruction = false;
+                        sinkable = false;
                         break;
                     }
@@ -108 +108 @@
                 }
 
-                if (canSinkInstruction) {
+                if (sinkable) {
                     assert (scopes.size() == 1);
                     stmt->insertBefore(scopes.front()->front());

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

@@ -5 +5 @@
 #include <pablo/printer_pablos.h>
 #include <pablo/analysis/pabloverifier.hpp>
-#include <unordered_map>
+#ifdef USE_BOOST
+#include <boost/container/flat_set.hpp>
+#else
+#include <unordered_set>
+#endif
 #include <iostream>
 
 namespace pablo {
+
+#ifdef USE_BOOST
+template <typename Type>
+using SmallSet = boost::container::flat_set<Type>;
+#else
+template <typename Type>
+using SmallSet = std::unordered_set<Type>;
+#endif
 
 bool Simplifier::optimize(PabloFunction & function) {
@@ -72 +84 @@
 }
 
+inline void replaceReachableUsersOfWith(Statement * stmt, PabloAST * expr) {
+    const PabloBlock * const root = stmt->getParent();
+    SmallSet<const PabloBlock *> forbidden;
+    for (PabloAST * use : stmt->users()) {
+        if (LLVM_UNLIKELY(isa<Next>(use))) {
+            const PabloBlock * parent = cast<Next>(use)->getParent();
+            if (parent != root) {
+                forbidden.insert(parent);
+            }
+        }
+    }
+    for (PabloAST * use : stmt->users()) {
+        if (Statement * user = dyn_cast<Statement>(use)) {
+            const PabloBlock * parent = user->getParent();
+            while (parent && forbidden.count(parent) == 0) {
+                if (LLVM_UNLIKELY(parent == root)) {
+                    user->replaceUsesOfWith(stmt, expr);
+                    break;
+                }
+                parent = parent->getParent();
+            }
+        }
+    }
+}
+
 void Simplifier::eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor) {
     ExpressionTable encountered(predecessor);
@@ -87 +124 @@
                 continue;
             }
-            // Force the uses of an local Assign to be the expression instead.
-            for (PabloAST * use : assign->users()) {
-                if (Statement * user = dyn_cast<Statement>(use)) {
-                    if (LLVM_UNLIKELY(user->getParent() == &block)) {
-                        user->replaceUsesOfWith(assign, assign->getExpression());
-                    }
-                }
-            }
+            // Force the uses of an Assign node that can reach the original expression to use the expression instead.
+            replaceReachableUsersOfWith(assign, assign->getExpression());
+        } else if (Next * next = dyn_cast<Next>(stmt)) {
+            replaceReachableUsersOfWith(next, next->getExpr());
         } else if (If * ifNode = dyn_cast<If>(stmt)) {
             // Check to see if the Cond is Zero and delete the loop.
             if (LLVM_UNLIKELY(isa<Zeroes>(ifNode->getCondition()))) {
-                for (Assign * defVar : ifNode->getDefined()) {
-                    defVar->replaceWith(PabloBlock::createZeroes(), false, true);
-                }
                 stmt = stmt->eraseFromParent(true);
                 continue;
@@ -143 +173 @@
                 }
             }
-        } else if (isa<While>(stmt)) {
-            eliminateRedundantCode(cast<While>(stmt)->getBody(), &encountered);
+        } else if (While * whileNode = dyn_cast<While>(stmt)) {
+
+            const PabloAST * initial = whileNode->getCondition();
+            if (LLVM_LIKELY(isa<Next>(initial))) {
+                initial = cast<Next>(initial)->getInitial();
+            }
+            if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
+                stmt = stmt->eraseFromParent(true);
+                continue;
+            }
+
+            eliminateRedundantCode(whileNode->getBody(), &encountered);
+
+
         } else if (canTriviallyFold(stmt)) { // non-Assign node
             // Do a trivial folding test to see if we're using all 0s or 1s as an operand.