Changeset 4919

Timestamp:

Jan 21, 2016, 5:15:33 PM (3 years ago)

Author:

nmedfort

Message:

Work on lowering + some timing and papi information that will be cleaned up later.

Location:

icGREP/icgrep-devel/icgrep

Files:

• CMakeLists.txt (modified) (5 diffs)
• cmake (added)
• cmake/FindPAPI.cmake (added)
• hrtime.h (modified) (2 diffs)
• icgrep-devel.files (modified) (1 diff)
• icgrep-devel.includes (modified) (1 diff)
• icgrep.cpp (modified) (7 diffs)
• pablo/analysis/pabloverifier.cpp (modified) (3 diffs)
• pablo/optimizers/booleanreassociationpass.cpp (modified) (7 diffs)
• pablo/optimizers/codemotionpass.cpp (modified) (3 diffs)
• pablo/optimizers/codemotionpass.h (modified) (1 diff)
• pablo/optimizers/distributivepass.cpp (modified) (12 diffs)
• pablo/optimizers/pablo_automultiplexing.cpp (modified) (9 diffs)
• pablo/optimizers/pablo_automultiplexing.hpp (modified) (3 diffs)
• pablo/optimizers/pablo_simplifier.cpp (modified) (3 diffs)
• pablo/optimizers/pablo_simplifier.hpp (modified) (1 diff)
• pablo/optimizers/schedulingprepass.cpp (modified) (15 diffs)
• pablo/optimizers/schedulingprepass.h (modified) (1 diff)
• pablo/pablo_compiler.cpp (modified) (3 diffs)
• pablo/passes/factorizedfg.cpp (modified) (10 diffs)
• pablo/passes/factorizedfg.h (modified) (3 diffs)
• pablo/passes/flattenassociativedfg.cpp (modified) (20 diffs)
• pablo/passes/flattenassociativedfg.h (modified) (3 diffs)
• pablo/printer_pablos.cpp (modified) (1 diff)
• papi_helper.hpp (added)
• re/re_compiler.cpp (modified) (2 diffs)
• toolchain.cpp (modified) (8 diffs)

icGREP/icgrep-devel/icgrep/CMakeLists.txt

@@ -17 +17 @@
 option(USE_BOOST_MMAP "Using mmap from Boost.Iostreams")
 option(ENABLE_PREGENERATED_UCD_FUNCTIONS "Enable compiling the pregenerated UCD functions")
-
+option(PRINT_TIMING_INFORMATION "Write compilation and execution timing information to standard error stream")
 
 # configure a header file to pass some of the CMake settings
@@ -37 +37 @@
 
 # We incorporate the CMake features provided by LLVM:
-set(CMAKE_MODULE_PATH ${CMAKE_MODULE_PATH} "${LLVM_ROOT}/share/llvm/cmake")
+set(CMAKE_MODULE_PATH "${CMAKE_MODULE_PATH};${LLVM_ROOT}/share/llvm/cmake;${CMAKE_CURRENT_SOURCE_DIR}/cmake")
+
 include(LLVMConfig)
 
@@ -47 +48 @@
 # Let's suppose we want to build a JIT compiler with support for
 # binary code (no interpreter):
-llvm_map_components_to_libnames(REQ_LLVM_LIBRARIES mcjit native IRReader)
+llvm_map_components_to_libnames(REQ_LLVM_LIBRARIES mcjit native IRReader) # ipo
 
 message(STATUS "Found LLVM ${LLVM_PACKAGE_VERSION}")
@@ -124 +125 @@
     target_link_libraries(icgrep ${Boost_LIBRARIES})
 ENDIF()
+IF (PRINT_TIMING_INFORMATION)
+    find_package(PAPI REQUIRED)
+    include_directories(${PAPI_INCLUDE_DIRS})
+    target_link_libraries(icgrep ${PAPI_LIBRARIES})
+ENDIF()
+
 
 target_link_libraries (icgrep UCDlib PabloADT RegExpCompiler CCADT ${REQ_LLVM_LIBRARIES})
@@ -314 +321 @@
 ENDIF()
 
+IF (PRINT_TIMING_INFORMATION)   
+    SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DPRINT_TIMING_INFORMATION")
+ENDIF()
+
 SET(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS} -O3 -DNDEBUG")
 IF (${CMAKE_SYSTEM} MATCHES "Linux")

icGREP/icgrep-devel/icgrep/hrtime.h

@@ -36 +36 @@
 }
 
+typedef uint64_t timestamp_t;
+
 // get the number of CPU cycles since startup using rdtsc instruction
-inline unsigned long long get_hrcycles() {
-  unsigned int tmp[2];
-  asm ("rdtsc" : "=a" (tmp[1]), "=d" (tmp[0]));
-  return (((unsigned long long)tmp[0] << 32 | tmp[1]));
+static inline timestamp_t read_cycle_counter() {
+#ifdef __GNUC__
+timestamp_t ts;
+#ifdef __x86_64__
+  unsigned int eax, edx;
+  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
+  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
+#else
+  asm volatile("rdtsc\n" : "=A" (ts));
+#endif
+  return(ts);
+#endif
+#ifdef _MSC_VER
+  return __rdtsc();
+#endif
 }
 
@@ -48 +61 @@
   if (CPU_HZ == 0)
     CPU_HZ = getMHZ() * 1000000;
-  return (get_hrcycles() / CPU_HZ);
+  return (read_cycle_counter() / CPU_HZ);
 }
 

icGREP/icgrep-devel/icgrep/icgrep-devel.files

@@ -493 +493 @@
 pablo/optimizers/schedulingprepass.h
 pablo/optimizers/schedulingprepass.cpp
+papi_helper.hpp

icGREP/icgrep-devel/icgrep/icgrep-devel.includes

@@ -12 +12 @@
 ../buddy-2.4/src
 pablo/passes
+../llvm-build/lib

icGREP/icgrep-devel/icgrep/icgrep.cpp

@@ -25 +25 @@
 #include <llvm/Support/Host.h>
 #include <llvm/IR/Verifier.h>
-
 #include <kernels/s2p_gen.h>
 #include <kernels/scanmatchgen.h>
@@ -36 +35 @@
 #include <pablo/function.h>
 
-#include "do_grep.h"
+#include <iostream>
+
+#include <do_grep.h>
+#include <hrtime.h>
+
+#ifdef PRINT_TIMING_INFORMATION
+#include "papi_helper.hpp"
+#endif
 
 static cl::OptionCategory aRegexSourceOptions("Regular Expression Options",
@@ -61 +67 @@
 static cl::opt<std::string> IRFileName("precompiled", cl::desc("Use precompiled regular expression"), cl::value_desc("LLVM IR file"), cl::init(""), cl::cat(aRegexSourceOptions));
 
-
+using namespace llvm;
 
 static unsigned firstInputFile = 1;  // Normal case when first positional arg is a regex.
@@ -154 +160 @@
         re_ast = regular_expression_passes(encoding, re_ast);
         
+        #ifdef PRINT_TIMING_INFORMATION
+        const timestamp_t regex_compilation_start = read_cycle_counter();
+        #endif
         pablo::PabloFunction * function = re2pablo_compiler(encoding, re_ast);
+        #ifdef PRINT_TIMING_INFORMATION
+        const timestamp_t regex_compilation_end = read_cycle_counter();
+        std::cerr << "REGEX COMPILATION TIME: " << (regex_compilation_end - regex_compilation_start) << std::endl;
+        #endif
 
         pablo_function_passes(function);
-        
         
         pablo::PabloCompiler pablo_compiler(M, idb);
@@ -181 +193 @@
     llvm::Function * s2p_IR = M->getFunction("s2p_block");
     
-    llvm::Function * scanRoutine = M->getFunction("scan_matches_in_bitblock");
+   // llvm::Function * scanRoutine = M->getFunction("scan_matches_in_bitblock");
     
     if (s2p_IR == nullptr) {
@@ -200 +212 @@
     void * icgrep_MCptr = engine->getPointerToFunction(icgrep_IR);
     void * s2p_MCptr = engine->getPointerToFunction(s2p_IR);
-    void * scan_MCptr = engine->getPointerToFunction(scanRoutine);
+    // void * scan_MCptr = engine->getPointerToFunction(scanRoutine);
     if (s2p_MCptr == nullptr) {
         std::cerr << "No s2p_MCptr!\n";
         exit(1);
     }
-    
+
     if (icgrep_MCptr) {
         GrepExecutor grepEngine(s2p_MCptr, icgrep_init_carry_ptr, icgrep_MCptr);
@@ -215 +227 @@
             grepEngine.setShowFileNameOption();
         }
+        #ifdef PRINT_TIMING_INFORMATION
+        papi::PapiCounter<4> papiCounters({PAPI_RES_STL, PAPI_STL_CCY, PAPI_FUL_CCY, PAPI_MEM_WCY});
+        #endif
         for (unsigned i = firstInputFile; i != inputFiles.size(); ++i) {
+            #ifdef PRINT_TIMING_INFORMATION
+            papiCounters.start();
+            const timestamp_t execution_start = read_cycle_counter();
+            #endif
             grepEngine.doGrep(inputFiles[i]);
+            #ifdef PRINT_TIMING_INFORMATION
+            const timestamp_t execution_end = read_cycle_counter();
+            papiCounters.stop();
+            std::cerr << "EXECUTION TIME: " << inputFiles[i] << ":" << "CYCLES|" << (execution_end - execution_start) << papiCounters << std::endl;
+            #endif
         }
     }

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

@@ -169 +169 @@
     PabloPrinter::print(user, str);
     if (count == 0) {
-        str << " is not recorded in ";
+        str << " is not considered a user of ";
     } else if (count > 0) {
-        str << " is recorded" << count << " times in ";
+        str << " was recorded too many times (" << count << ") in the user list of ";
     }
     PabloPrinter::print(def, str);
-    str << "'s user list.";
+    throw std::runtime_error(str.str());
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief throwReportedScopeError
+ ** ------------------------------------------------------------------------------------------------------------- */
+static void throwReportedScopeError(const Statement * const stmt) {
+    std::string tmp;
+    raw_string_ostream str(tmp);
+    str << "PabloVerifier: structure error: ";
+    PabloPrinter::print(stmt, str);
+    str << " is not contained in its reported scope block";
+    throw std::runtime_error(str.str());
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief throwMisreportedBranchError
+ ** ------------------------------------------------------------------------------------------------------------- */
+static void throwMisreportedBranchError(const Statement * const stmt, const Statement * const branch) {
+    std::string tmp;
+    raw_string_ostream str(tmp);
+    str << "PabloVerifier: structure error: ";
+    PabloPrinter::print(stmt, str);
+    str << " branches into a scope block that reports ";
+    PabloPrinter::print(stmt, str);
+    str << " as its branching statement.";
+    throw std::runtime_error(str.str());
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief throwReflexiveIfConditionError
+ ** ------------------------------------------------------------------------------------------------------------- */
+static void throwReflexiveIfConditionError(const PabloAST * const ifNode) {
+    std::string tmp;
+    raw_string_ostream str(tmp);
+    str << "PabloVerifier: structure error: the condition of ";
+    PabloPrinter::print(ifNode, str);
+    str << " cannot be defined by the If node itself.";
     throw std::runtime_error(str.str());
 }
@@ -206 +243 @@
         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
             const PabloBlock * nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
-            if (LLVM_UNLIKELY(nested->getParent() != block)) {
-                std::string tmp;
-                raw_string_ostream str(tmp);
-                str << "PabloVerifier: structure error: body of ";
-                PabloPrinter::print(stmt, str);
-                str << " is not nested within the expected scope block";
-                throw std::runtime_error(str.str());
+            if (LLVM_UNLIKELY(nested->getBranch() != stmt)) {
+                throwMisreportedBranchError(stmt, nested->getBranch());
+            } else if (LLVM_UNLIKELY(nested->getParent() != block)) {
+                throwReportedScopeError(stmt);
             }
             if (isa<If>(stmt)) {
                 for (const Assign * def : cast<If>(stmt)->getDefined()) {
                     if (LLVM_UNLIKELY(def == cast<If>(stmt)->getCondition())) {
-                        std::string tmp;
-                        raw_string_ostream str(tmp);
-                        str << "PabloVerifier: structure error: the condition of ";
-                        PabloPrinter::print(cast<PabloAST>(stmt), str);
-                        str << " cannot be defined by the If node itself.";
-                        throw std::runtime_error(str.str());
-                    }
-                }
-            }
-            if (isa<If>(stmt)) {
-                for (const Assign * def : cast<If>(stmt)->getDefined()) {
-                    if (LLVM_UNLIKELY(unreachable(def, nested))) {
+                        throwReflexiveIfConditionError(stmt);
+                    } else if (LLVM_UNLIKELY(unreachable(def, nested))) {
                         throwUncontainedEscapedValueError(stmt, def);
                     }
@@ -250 +274 @@
                     }
                     count = std::count(var->user_begin(), var->user_end(), stmt);
-                    if (LLVM_UNLIKELY(count != 1)) {
+                    if (LLVM_UNLIKELY(count != ((cast<While>(stmt)->getCondition() == var) ? 2 : 1))) {
                         throwEscapedValueUsageError(stmt, var, var, stmt, count);
                     }

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

@@ -22 +22 @@
 
 using TypeId = PabloAST::ClassTypeId;
-using Graph = BooleanReassociationPass::Graph;
-using Vertex = Graph::vertex_descriptor;
+using DependencyGraph = BooleanReassociationPass::Graph;
+using Vertex = DependencyGraph::vertex_descriptor;
 using VertexData = BooleanReassociationPass::VertexData;
 using SinkMap = BooleanReassociationPass::Map;
 using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
-using DistributionMap = flat_map<Graph::vertex_descriptor, DistributionGraph::vertex_descriptor>;
+using DistributionMap = flat_map<DependencyGraph::vertex_descriptor, DistributionGraph::vertex_descriptor>;
 using VertexSet = std::vector<Vertex>;
 using VertexSets = std::vector<VertexSet>;
@@ -39 +39 @@
  ** ------------------------------------------------------------------------------------------------------------- */
 template<typename Iterator>
-inline Graph::edge_descriptor first(const std::pair<Iterator, Iterator> & range) {
+inline DependencyGraph::edge_descriptor first(const std::pair<Iterator, Iterator> & range) {
     assert (range.first != range.second);
     return *range.first;
@@ -45 +45 @@
 
 #ifndef NDEBUG
-static bool no_path(const Vertex u, const Vertex v, const Graph & G) {
+static bool no_path(const Vertex u, const Vertex v, const DependencyGraph & G) {
     if (u == v) return false;
     flat_set<Vertex> V;
@@ -70 +70 @@
 #endif
 
-inline void add_edge(PabloAST * expr, const Vertex u, const Vertex v, Graph & G) {
+inline void add_edge(PabloAST * expr, const Vertex u, const Vertex v, DependencyGraph & G) {
     assert (no_path(v, u, G));
     // Make sure each edge is unique
@@ -821 +821 @@
  * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
  ** ------------------------------------------------------------------------------------------------------------- */
-static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, const Graph & G, DistributionGraph & H) {
+static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, const DependencyGraph & G, DistributionGraph & H) {
     for (auto ci = cliques.begin(); ci != cliques.end(); ) {
         const auto cardinalityA = std::get<0>(*ci).size();
@@ -844 +844 @@
  * @brief safeDistributionSets
  ** ------------------------------------------------------------------------------------------------------------- */
-static DistributionSets safeDistributionSets(const Graph & G, DistributionGraph & H) {
+static DistributionSets safeDistributionSets(const DependencyGraph & G, DistributionGraph & H) {
 
     VertexSet sinks;
@@ -868 +868 @@
  * @brief generateDistributionGraph
  ** ------------------------------------------------------------------------------------------------------------- */
-void generateDistributionGraph(const Graph & G, DistributionGraph & H) {
+void generateDistributionGraph(const DependencyGraph & G, DistributionGraph & H) {
     DistributionMap M;
     for (const Vertex u : make_iterator_range(vertices(G))) {

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

@@ -13 +13 @@
  ** ------------------------------------------------------------------------------------------------------------- */
 bool CodeMotionPass::optimize(PabloFunction & function) {
-    CodeMotionPass::process(function.getEntryBlock());
+    CodeMotionPass::global(function.getEntryBlock());
     #ifndef NDEBUG
     PabloVerifier::verify(function, "post-code-motion");
@@ -23 +23 @@
  * @brief process
  ** ------------------------------------------------------------------------------------------------------------- */
-void CodeMotionPass::process(PabloBlock * const block) {
+void CodeMotionPass::global(PabloBlock * const block) {
     sink(block);
     for (Statement * stmt : *block) {
         if (isa<If>(stmt)) {
-            process(cast<If>(stmt)->getBody());
+            global(cast<If>(stmt)->getBody());
         } else if (isa<While>(stmt)) {
-            process(cast<While>(stmt)->getBody());
+            global(cast<While>(stmt)->getBody());
             // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
             // determine whether hoisting will helpful or harmful to the expected run time.
@@ -132 +132 @@
                 // must be the LCA of our original scopes.
                 while (scope1 != scope2) {
+                    assert (scope1 && scope2);
                     scope1 = scope1->getParent();
                     scope2 = scope2->getParent();
                 }
-                assert (scope1 && scope2);
+                assert (scope1);
                 // But if the LCA is the current block, we can't sink the statement.
                 if (scope1 == block) {

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

@@ -31 +31 @@
     static bool optimize(PabloFunction & function);
 protected:
-    static void process(PabloBlock * const block);
+    static void global(PabloBlock * const block);
     static bool isAcceptableTarget(Statement *stmt, ScopeSet & scopeSet, const PabloBlock * const block);
     static void sink(PabloBlock * const block);

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

@@ -14 +14 @@
 namespace pablo {
 
-using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
-using Vertex = Graph::vertex_descriptor;
+using DependencyGraph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
+using Vertex = DependencyGraph::vertex_descriptor;
 using SinkMap = flat_map<PabloAST *, Vertex>;
 using VertexSet = std::vector<Vertex>;
@@ -28 +28 @@
  * @brief getVertex
  ** ------------------------------------------------------------------------------------------------------------- */
-static inline Vertex getVertex(PabloAST * value, Graph & G, SinkMap & M) {
+static inline Vertex getVertex(PabloAST * value, DependencyGraph & G, SinkMap & M) {
     const auto f = M.find(value);
     if (f != M.end()) {
@@ -43 +43 @@
  * Generate a graph G describing the potential applications of the distributive law for the given block.
  ** ------------------------------------------------------------------------------------------------------------- */
-VertexSet generateDistributionGraph(PabloBlock * block, Graph & G) {
+VertexSet generateDistributionGraph(PabloBlock * block, DependencyGraph & G) {
     SinkMap M;
     VertexSet distSet;
@@ -126 +126 @@
  ** ------------------------------------------------------------------------------------------------------------- */
 template <unsigned side>
-inline static BicliqueSet && independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) {
+inline static BicliqueSet && independentCliqueSets(BicliqueSet && bicliques, const unsigned minimum) {
     using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
 
-    const auto l = cliques.size();
+    const auto l = bicliques.size();
     IndependentSetGraph I(l);
 
-    // Initialize our weights
+    // Initialize our weights and determine the constraints
     for (unsigned i = 0; i != l; ++i) {
-        I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
-    }
-
-    // Determine our constraints
-    for (unsigned i = 0; i != l; ++i) {
+        I[i] = std::pow(std::get<side>(bicliques[i]).size(), 2);
         for (unsigned j = i + 1; j != l; ++j) {
-            if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
+            if (intersects(std::get<side>(bicliques[i]), std::get<side>(bicliques[j]))) {
                 add_edge(i, j, I);
             }
         }
     }
+
+//    // Initialize our weights and determine the constraints
+//    for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
+//        I[std::distance(bicliques.begin(), i)] = std::pow(std::get<side>(*i).size(), 2);
+//        for (auto j = i; ++j != bicliques.end(); ) {
+//            if (intersects(i->second, j->second) && intersects(i->first, j->first)) {
+//                add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
+//            }
+//        }
+//    }
 
     // Use the greedy algorithm to choose our independent set
@@ -167 +173 @@
     // Sort the selected list and then remove the unselected cliques
     std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
-    auto end = cliques.end();
+    auto end = bicliques.end();
     for (const unsigned offset : selected) {
-        end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
-    }
-    cliques.erase(cliques.begin(), end);
-
-    return std::move(cliques);
+        end = bicliques.erase(bicliques.begin() + offset + 1, end) - 1;
+    }
+    bicliques.erase(bicliques.begin(), end);
+
+    return std::move(bicliques);
 }
 
@@ -183 +189 @@
  * bipartition A and their adjacencies to be in B.
   ** ------------------------------------------------------------------------------------------------------------- */
-static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
+static BicliqueSet enumerateBicliques(const DependencyGraph & G, const VertexSet & A) {
     using IntersectionSets = std::set<VertexSet>;
 
@@ -265 +271 @@
  * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
  ** ------------------------------------------------------------------------------------------------------------- */
-static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, Graph & G) {
+static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, DependencyGraph & G) {
     for (auto ci = cliques.begin(); ci != cliques.end(); ) {
         const auto cardinalityA = std::get<0>(*ci).size();
@@ -288 +294 @@
  * @brief safeDistributionSets
  ** ------------------------------------------------------------------------------------------------------------- */
-static DistributionSets safeDistributionSets(Graph & G, const VertexSet & distSet) {
+static DistributionSets safeDistributionSets(DependencyGraph & G, const VertexSet & distSet) {
     DistributionSets T;
     BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(G, distSet), G), 1);
@@ -309 +315 @@
         // FlattenAssociativeDFG::coalesce(block, false);
 
-        Graph G;
+        DependencyGraph G;
 
         const VertexSet distSet = generateDistributionGraph(block, G);
@@ -350 +356 @@
                 outerOp->addOperand(G[u]);
             }
-            FlattenAssociativeDFG::coalesce(outerOp);
+            CoalesceDFG::coalesce(outerOp);
 
             for (const Vertex u : sources) {
@@ -359 +365 @@
             }
             innerOp->addOperand(outerOp);
-            FlattenAssociativeDFG::coalesce(innerOp);
+            CoalesceDFG::coalesce(innerOp);
 
             for (const Vertex u : sinks) {
-                Variadic * const resultOp = cast<Variadic>(G[u]);
-                resultOp->addOperand(innerOp);
-                FlattenAssociativeDFG::coalesce(resultOp);
+                cast<Variadic>(G[u])->addOperand(innerOp);
             }
         }
@@ -391 +395 @@
     #endif
     Simplifier::optimize(function);
-//    FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock());
-//    #ifndef NDEBUG
-//    PabloVerifier::verify(function, "post-demorgans-reduction");
-//    #endif
-//    Simplifier::optimize(function);
-}
-
-
-}
+}
+
+
+}

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

@@ -11 +11 @@
 #include <pablo/analysis/pabloverifier.hpp>
 #include <pablo/optimizers/pablo_simplifier.hpp>
+#include <pablo/builder.hpp>
 #include <stack>
 #include <queue>
@@ -23 +24 @@
 using namespace boost::numeric::ublas;
 
-#define PRINT_DEBUG_OUTPUT
+// #define PRINT_DEBUG_OUTPUT
 
 #if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
@@ -102 +103 @@
 namespace pablo {
 
+#ifdef PRINT_TIMING_INFORMATION
+MultiplexingPass::seed_t MultiplexingPass::SEED = 0;
+unsigned MultiplexingPass::NODES_ALLOCATED = 0;
+unsigned MultiplexingPass::NODES_USED = 0;
+#endif
+
 using TypeId = PabloAST::ClassTypeId;
 
 bool MultiplexingPass::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections, const unsigned windowSize, const bool independent) {
 
-//    std::random_device rd;
-//    const auto seed = rd();
-    const auto seed = 83234827342;
+    std::random_device rd;
+    const RNG::result_type seed = rd();
+    // const RNG::result_type seed = 83234827342;
 
     LOG("Seed:                    " << seed);
+
+    #ifdef PRINT_TIMING_INFORMATION
+    MultiplexingPass::SEED = seed;
+    MultiplexingPass::NODES_ALLOCATED = 0;
+    MultiplexingPass::NODES_USED = 0;
+    #endif
 
     MultiplexingPass mp(seed, limit, maxSelections, windowSize);
@@ -132 +145 @@
 
     LOG("Nodes in BDD:             " << bdd_getnodenum() << " of " << bdd_getallocnum());
+
+    #ifdef PRINT_TIMING_INFORMATION
+    MultiplexingPass::NODES_ALLOCATED = bdd_getallocnum();
+    MultiplexingPass::NODES_USED = bdd_getnodenum();
+    #endif
 
     RECORD_TIMESTAMP(start_shutdown);
@@ -491 +509 @@
 .
                 for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
-                    unconstrained[source(e, mSubsetGraph)] = true;
+                    const auto j = source(e, mSubsetGraph);
+                    if (mSubsetImplicationsAdhereToWindowingSizeConstraint && exceedsWindowSize(j, k)) {
+                        continue;
+                    }
+                    unconstrained[j] = true;
                 }
                 unconstrained[i] = true;
@@ -503 +525 @@
                     const auto j = source(e, mSubsetGraph);
                     add_edge(j, k, mSubsetGraph);
+                    if (mSubsetImplicationsAdhereToWindowingSizeConstraint && exceedsWindowSize(j, k)) {
+                        continue;
+                    }
                     unconstrained[j] = true;
                 }
@@ -513 +538 @@
                     const auto j = target(e, mSubsetGraph);
                     add_edge(k, j, mSubsetGraph);
+                    if (mSubsetImplicationsAdhereToWindowingSizeConstraint && exceedsWindowSize(j, k)) {
+                        continue;
+                    }
                     unconstrained[j] = true;
                 }
@@ -527 +555 @@
             // Note: this algorithm deems two streams are mutually exclusive if and only if the conjuntion of their BDDs results
             // in a contradiction. To generate a contradiction when comparing Advances, the BDD of each Advance is represented by
-            // the conjunction of variable representing that Advance and the negation of all variables for the Advances in which
-            // the inputs are deemed to be mutually exclusive. For example, if the input of the i-th Advance is mutually exclusive
+            // the conjunction of variable representing the k-th Advance and the negation of all variables for the Advances whose
+            // inputs are mutually exclusive with the k-th input. For example, if the input of the i-th Advance is mutually exclusive
             // with the input of the j-th and k-th Advance, the BDD of the i-th Advance is Ai ∧ ¬Aj ∧ ¬Ak.
             const Advance * const ithAdv = mAdvance[i];
@@ -943 +971 @@
             Advance * const adv = input[0];
             PabloBlock * const block = adv->getParent(); assert (block);
-            block->setInsertPoint(nullptr);            
-            /// Perform n-to-m Multiplexing
+            block->setInsertPoint(nullptr);
+            circular_buffer<PabloAST *> Q(n);
+            PabloBuilder builder(block);
+            /// Perform n-to-m Multiplexing            
             for (size_t j = 0; j != m; ++j) {
                 std::ostringstream prefix;
                 prefix << "mux" << n << "to" << m << '.' << (j + 1);
-                Or * muxing = block->createOr(n);
+//                Or * muxing = block->createOr(n);
+//                for (size_t i = 0; i != n; ++i) {
+//                    if (((i + 1) & (1UL << j)) != 0) {
+//                        assert (input[i]->getParent() == block);
+//                        muxing->addOperand(input[i]->getOperand(0));
+//                    }
+//                }
                 for (size_t i = 0; i != n; ++i) {
                     if (((i + 1) & (1UL << j)) != 0) {
-                        assert (input[i]->getParent() == block);
-                        muxing->addOperand(input[i]->getOperand(0));
-                    }
-                }
-                muxed[j] = block->createAdvance(muxing, adv->getOperand(1), prefix.str());
-                muxed_n[j] = block->createNot(muxed[j]);
-            }
-            /// Perform m-to-n Demultiplexing
+                        Q.push_back(input[i]->getOperand(0));
+                    }
+                }
+                while (Q.size() > 1) {
+                    PabloAST * a = Q.front(); Q.pop_front();
+                    PabloAST * b = Q.front(); Q.pop_front();
+                    Q.push_back(builder.createOr(a, b));
+                }
+                PabloAST * muxing =  Q.front(); Q.clear();
+                muxed[j] = builder.createAdvance(muxing, adv->getOperand(1), prefix.str());
+                muxed_n[j] = builder.createNot(muxed[j]);
+            }
+            /// Perform m-to-n Demultiplexing            
             for (size_t i = 0; i != n; ++i) {
-                // Construct the demuxed values and replaces all the users of the original advances with them.                
-                And * demuxed = block->createAnd(m);
+                // Construct the demuxed values and replaces all the users of the original advances with them.
+                assert (Q.empty());
                 for (size_t j = 0; j != m; ++j) {
-                    demuxed->addOperand((((i + 1) & (1UL << j)) != 0) ? muxed[j] : muxed_n[j]);
-                }
+                    Q.push_back((((i + 1) & (1UL << j)) != 0) ? muxed[j] : muxed_n[j]);
+                }
+                while (Q.size() > 1) {
+                    PabloAST * a = Q.front(); Q.pop_front();
+                    PabloAST * b = Q.front(); Q.pop_front();
+                    Q.push_back(builder.createAnd(a, b));
+                }
+                PabloAST * demuxed =  Q.front(); Q.clear();
+//                And * demuxed = block->createAnd(m);
+//                for (size_t j = 0; j != m; ++j) {
+//                    demuxed->addOperand((((i + 1) & (1UL << j)) != 0) ? muxed[j] : muxed_n[j]);
+//                }
                 input[i]->replaceWith(demuxed, true, true);
             }

icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

@@ -44 +44 @@
 
     static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100, const unsigned windowSize = 1, const bool independent = false);
-
+    #ifdef PRINT_TIMING_INFORMATION
+    using seed_t = RNG::result_type;
+    static seed_t SEED;
+    static unsigned NODES_ALLOCATED;
+    static unsigned NODES_USED;
+    #endif
 protected:
 
@@ -81 +86 @@
     , mWindowSize(windowSize)
     , mTestConstrainedAdvances(true)
+    , mSubsetImplicationsAdhereToWindowingSizeConstraint(false)
     , mVariables(0)
     , mRNG(seed)
@@ -96 +102 @@
     const unsigned              mWindowSize;
     const bool                  mTestConstrainedAdvances;
+    const bool                  mSubsetImplicationsAdhereToWindowingSizeConstraint;
     unsigned                    mVariables;
     RNG                         mRNG;

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

@@ -5 +5 @@
 #include <pablo/printer_pablos.h>
 #include <pablo/analysis/pabloverifier.hpp>
-#ifdef USE_BOOST
 #include <boost/container/flat_set.hpp>
-#else
-#include <unordered_set>
-#endif
 
 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
 
 /** ------------------------------------------------------------------------------------------------------------- *
@@ -25 +16 @@
  ** ------------------------------------------------------------------------------------------------------------- */
 bool Simplifier::optimize(PabloFunction & function) {
+    // negationsShouldImmediatelySucceedTheirLiteral(function.getEntryBlock());
+    #ifndef NDEBUG
+    PabloVerifier::verify(function, "post-negation-must-immediately-succeed-their-literal");
+    #endif
     eliminateRedundantCode(function.getEntryBlock());
     #ifndef NDEBUG
@@ -476 +471 @@
 }
 
-}
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief negationsShouldImmediatelySucceedTheirLiteral
+ *
+ * Assuming that most negations are actually replaced by an ANDC operations or that we only need a literal or its
+ * negation, by pushing all negations up to immediately succeed the literal we should generate equally efficient
+ * code whilst simplifying analysis.
+ *
+ * TODO: this theory needs evaluation.
+ ** ------------------------------------------------------------------------------------------------------------- */
+void Simplifier::negationsShouldImmediatelySucceedTheirLiteral(PabloBlock * const block) {
+    Statement * stmt = block->front();
+    while (stmt) {
+        Statement * next = stmt->getNextNode();
+        if (isa<If>(stmt)) {
+            negationsShouldImmediatelySucceedTheirLiteral(cast<If>(stmt)->getBody());
+        } else if (isa<While>(stmt)) {
+            negationsShouldImmediatelySucceedTheirLiteral(cast<While>(stmt)->getBody());
+        } else if (isa<Not>(stmt)) {
+            PabloAST * op = cast<Not>(stmt)->getExpr();
+            if (LLVM_LIKELY(isa<Statement>(op))) {
+                PabloBlock * scope = cast<Statement>(op)->getParent();
+                // If the operand is not in a nested scope, we can move it.
+                for (;;) {
+                    if (LLVM_UNLIKELY(scope == nullptr)) {
+                        stmt->insertAfter(cast<Statement>(op));
+                        break;
+                    }
+                    scope = scope->getParent();
+                    if (LLVM_UNLIKELY(scope == block)) {
+                        break;
+                    }
+                }
+            }
+        }
+        stmt = next;
+    }
+}
+
+}

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

@@ -15 +15 @@
     Simplifier() = default;
 private:
+    static void negationsShouldImmediatelySucceedTheirLiteral(PabloBlock * const block);
     static void eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor = nullptr);
     static PabloAST * fold(Variadic * const var, PabloBlock * const block);

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

@@ -3 +3 @@
 #include <boost/circular_buffer.hpp>
 #include <boost/container/flat_set.hpp>
+#include <boost/container/flat_map.hpp>
 #include <pablo/analysis/pabloverifier.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <unordered_map>
 
 #include <pablo/printer_pablos.h>
@@ -13 +16 @@
 namespace pablo {
 
+using DependencyGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, std::vector<PabloAST *>>;
+using Vertex = DependencyGraph::vertex_descriptor;
+using Map = std::unordered_map<const PabloAST *, Vertex>;
+using ReadyPair = std::pair<unsigned, Vertex>;
+using ReadySet = std::vector<ReadyPair>;
+
+using weight_t = unsigned;
+using TypeId = PabloAST::ClassTypeId;
+using LiveSet = flat_set<Vertex>;
+
+void schedule(PabloBlock * const block);
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief printGraph
+ ** ------------------------------------------------------------------------------------------------------------- */
+template <typename DependencyGraph>
+static void printGraph(const DependencyGraph & G, const std::vector<unsigned> & ordering, const std::string name, raw_ostream & out) {
+    out << "*******************************************\n";
+    out << "digraph " << name << " {\n";
+    for (auto u : make_iterator_range(vertices(G))) {
+        if (G[u].empty()) {
+            continue;
+        }
+        out << "v" << u << " [label=\"" << ordering[u] << " : ";
+        bool newLine = false;
+        for (PabloAST * expr : G[u]) {
+            if (newLine) {
+                out << '\n';
+            }
+            newLine = true;
+            if (isa<Statement>(expr)) {
+                PabloPrinter::print(cast<Statement>(expr), out);
+            } else {
+                PabloPrinter::print(expr, out);
+            }
+        }
+        out << "\"];\n";
+    }
+    for (auto e : make_iterator_range(edges(G))) {
+        out << "v" << source(e, G) << " -> v" << target(e, G);
+        out << ";\n";
+    }
+
+    out << "}\n\n";
+    out.flush();
+}
+
 /** ------------------------------------------------------------------------------------------------------------- *
  * @brief resolveNestedUsages
  ** ------------------------------------------------------------------------------------------------------------- */
-void SchedulingPrePass::resolveNestedUsages(Statement * const root, Statement * const stmt, Graph & G, Map & M, PabloBlock * const block) {
+static void resolveNestedUsages(Statement * const root, Statement * const stmt, DependencyGraph & G, Map & M, PabloBlock * const block) {
     for (PabloAST * use : stmt->users()) {
         if (LLVM_LIKELY(isa<Statement>(use))) {
@@ -23 +73 @@
                 for (PabloBlock * prior = scope->getParent(); prior; scope = prior, prior = prior->getParent()) {
                     if (prior == block) {
-                        auto s = mResolvedScopes.find(scope);
-                        assert (s != mResolvedScopes.end());
-                        assert (s->second);
-                        auto v = M.find(s->second);
+                        assert (scope->getBranch());
+                        auto v = M.find(scope->getBranch());
                         assert (v != M.end());
                         auto u = M.find(root);
@@ -41 +89 @@
 }
 
-///** ------------------------------------------------------------------------------------------------------------- *
-// * @brief printGraph
-// ** ------------------------------------------------------------------------------------------------------------- */
-//template <typename Graph>
-//static void printGraph(const Graph & G, const std::vector<unsigned> & ordering, const std::string name, raw_ostream & out) {
-//    out << "*******************************************\n";
-//    out << "digraph " << name << " {\n";
-//    for (auto u : make_iterator_range(vertices(G))) {
-//        out << "v" << u << " [label=\"" << ordering[u] << " : ";
-//        PabloPrinter::print(G[u], out);
-//        out << "\"];\n";
-//    }
-//    for (auto e : make_iterator_range(edges(G))) {
-//        out << "v" << source(e, G) << " -> v" << target(e, G);
-//        out << ";\n";
-//    }
-
-//    out << "}\n\n";
-//    out.flush();
-//}
-
-/** ------------------------------------------------------------------------------------------------------------- *
- * @brief schedule
- ** ------------------------------------------------------------------------------------------------------------- */
-void SchedulingPrePass::schedule(PabloBlock * const block) {
-    Graph G;
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief resolveNestedUsages
+ ** ------------------------------------------------------------------------------------------------------------- */
+static void computeDependencyGraph(DependencyGraph & G, PabloBlock * const block) {
     Map M;
-
     // Construct a use-def graph G representing the current scope block
     for (Statement * stmt : *block) {
-        if (isa<If>(stmt) || isa<While>(stmt)) {
-            PabloBlock * body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
-            mResolvedScopes.emplace(body, stmt);
-            schedule(body);
-        }
-        const auto u = add_vertex(stmt, G);
+        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
+            schedule(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
+        }
+        const auto u = add_vertex({stmt}, G);
         M.insert(std::make_pair(stmt, u));
         for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
@@ -94 +117 @@
                         // Was this instruction computed by a nested block?
                         if (prior == block) {
-                            auto s = mResolvedScopes.find(scope);
-                            assert (s != mResolvedScopes.end());
-                            assert (s->second);
-                            auto v = M.find(s->second);
+                            assert (scope->getBranch());
+                            auto v = M.find(scope->getBranch());
                             assert (v != M.end());
                             if (v->second != u) {
@@ -109 +130 @@
         }
     }
-    // Do a second pass to ensure that we've accounted for any nested usage of a statement
+    // Do a second pass to ensure that we've accounted for any nested usage of an If or While statement
     for (Statement * stmt : *block) {
         if (LLVM_UNLIKELY(isa<If>(stmt))) {
@@ -123 +144 @@
         }
     }
-
+    // Contract the graph
+    for (;;) {
+        bool done = true;
+        for (const Vertex u : make_iterator_range(vertices(G))) {
+            if (out_degree(u, G) == 1) {
+                const Vertex v = target(*(out_edges(u, G).first), G);
+                G[v].insert(G[v].begin(), G[u].begin(), G[u].end());
+                for (auto e : make_iterator_range(in_edges(u, G))) {
+                    add_edge(source(e, G), v, G);
+                }
+                G[u].clear();
+                clear_vertex(u, G);
+                done = false;
+            }
+        }
+        if (done) {
+            break;
+        }
+    }
+
+
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief computeGraphOrdering
+ ** ------------------------------------------------------------------------------------------------------------- */
+std::vector<weight_t> computeGraphOrdering(const DependencyGraph & G) {
     // Determine the bottom-up ordering of G
-    std::vector<unsigned> ordering(num_vertices(G));
+    std::vector<weight_t> ordering(num_vertices(G));
     circular_buffer<Vertex> Q(num_vertices(G));
     for (const Vertex u : make_iterator_range(vertices(G))) {
-        if (out_degree(u, G) == 0) {
+        if (out_degree(u, G) == 0 && G[u].size() > 0) {
             ordering[u] = 1;
             Q.push_back(u);
         }
     }
-
     while (!Q.empty()) {
         const Vertex u = Q.front();
@@ -141 +187 @@
             const Vertex v = source(ei, G);
             if (ordering[v] == 0) {
-                unsigned weight = 0;
+                weight_t weight = 0;
                 bool ready = true;
                 for (const auto ej : make_iterator_range(out_edges(v, G))) {
                     const Vertex w = target(ej, G);
-                    const unsigned t = ordering[w];
+                    const weight_t t = ordering[w];
                     if (t == 0) {
                         ready = false;
@@ -155 +201 @@
                     assert (weight < std::numeric_limits<unsigned>::max());
                     assert (weight > 0);
-                    ordering[v] = (weight + 1);
+                    ordering[v] = weight + 1;
                     Q.push_back(v);
                 }
@@ -161 +207 @@
         }
     }
+    return ordering;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief schedule
+ ** ------------------------------------------------------------------------------------------------------------- */
+void schedule(PabloBlock * const block) {
+    DependencyGraph G;
+    computeDependencyGraph(G, block);
+    std::vector<weight_t> ordering = computeGraphOrdering(G);
+
+//    raw_os_ostream out(std::cerr);
+//    printGraph(G, ordering, "G", out);
 
     // Compute the initial ready set
     ReadySet readySet;
     for (const Vertex u : make_iterator_range(vertices(G))) {
-        if (in_degree(u, G) == 0) {
+        if (in_degree(u, G) == 0 && G[u].size() > 0) {
             readySet.emplace_back(ordering[u], u);
         }
@@ -180 +239 @@
     block->setInsertPoint(nullptr);
 
-
-    // Rewrite the AST using the bottom-up ordering
+    // Rewrite the AST
     while (!readySet.empty()) {
-
-        // Scan through the ready set to determine which one 'kills' the greatest number of inputs
-        // NOTE: the readySet is kept in sorted "distance to sink" order; thus those closest to a
-        // sink will be evaluated first.
-        double best = 0;
+        DependencyGraph::degree_size_type killed = 0;
         auto chosen = readySet.begin();
         for (auto ri = readySet.begin(); ri != readySet.end(); ++ri) {
-            const Vertex u = std::get<1>(*ri);
-            const PabloAST * const expr = G[u];
-            if (expr && (isa<Assign>(expr) || isa<Next>(expr))) {
+            DependencyGraph::degree_size_type kills = 0;
+            for (auto e : make_iterator_range(in_edges(ri->first, G))) {
+                if (out_degree(source(e, G), G) == 1) {
+                    ++kills;
+                }
+            }
+            if (kills > killed) {
                 chosen = ri;
-                break;
-            }
-            double progress = 0;
-            for (auto ei : make_iterator_range(in_edges(u, G))) {
-                const auto v = source(ei, G);
-                const auto totalUsesOfIthOperand = out_degree(v, G);
-                if (LLVM_UNLIKELY(totalUsesOfIthOperand == 0)) {
-                    progress += 1.0;
-                } else {
-                    unsigned unscheduledUsesOfIthOperand = 0;
-                    for (auto ej : make_iterator_range(out_edges(v, G))) {
-                        if (ordering[target(ej, G)]) { // if this edge leads to an unscheduled statement
-                            ++unscheduledUsesOfIthOperand;
-                        }
-                    }
-                    progress += std::pow((double)(totalUsesOfIthOperand - unscheduledUsesOfIthOperand + 1) / (double)(totalUsesOfIthOperand), 2);
-                }
-            }
-            if (progress > best) {
-                chosen = ri;
-                best = progress;
+                killed = kills;
             }
         }
@@ -221 +259 @@
         std::tie(weight, u) = *chosen;
         readySet.erase(chosen);
+        clear_in_edges(u, G);
 
         assert ("Error: SchedulingPrePass is attempting to reschedule a statement!" && (weight > 0));
 
         // insert the statement then mark it as written ...
-        block->insert(cast<Statement>(G[u]));
+        for (PabloAST * expr : G[u]) {
+            block->insert(cast<Statement>(expr));
+        }
+
         ordering[u] = 0;
         // Now check whether any new instructions are ready
@@ -245 +287 @@
         }
     }
+
 }
 
@@ -250 +293 @@
  * @brief schedule
  ** ------------------------------------------------------------------------------------------------------------- */
-void SchedulingPrePass::schedule(PabloFunction & function) {
-    mResolvedScopes.emplace(function.getEntryBlock(), nullptr);
+void schedule(PabloFunction & function) {
     schedule(function.getEntryBlock());
 }
@@ -259 +301 @@
  ** ------------------------------------------------------------------------------------------------------------- */
 bool SchedulingPrePass::optimize(PabloFunction & function) {
-    SchedulingPrePass pp;
-    pp.schedule(function);
+    schedule(function);
     #ifndef NDEBUG
     PabloVerifier::verify(function, "post-scheduling-prepass");

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

@@ -1 +1 @@
 #ifndef SCHEDULINGPREPASS_H
 #define SCHEDULINGPREPASS_H
-
-#include <boost/container/flat_map.hpp>
-#include <boost/graph/adjacency_list.hpp>
-#include <unordered_map>
 
 namespace pablo {
 
 class PabloFunction;
-class PabloBlock;
-class Statement;
-class PabloAST;
 
 class SchedulingPrePass {
 public:
-    using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *>;
-    using Vertex = Graph::vertex_descriptor;
-    using Map = std::unordered_map<const PabloAST *, Vertex>;
-    using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
-    using ReadyPair = std::pair<unsigned, Vertex>;
-    using ReadySet = std::vector<ReadyPair>;
-public:
     static bool optimize(PabloFunction & function);
 protected:
-    void schedule(PabloFunction & function);
-    void schedule(PabloBlock * const block);
-    void resolveNestedUsages(Statement * const root, Statement * const stmt, Graph & G, Map & M, PabloBlock * const block);
     SchedulingPrePass() = default;
-private:
-    ScopeMap mResolvedScopes;
 };
-
 
 }
 
-
 #endif // SCHEDULINGPREPASS_H

icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

@@ -47 +47 @@
 #include <llvm/ADT/Twine.h>
 #include <iostream>
+#include <llvm/Support/raw_ostream.h>
+#include <llvm/Support/FileSystem.h>
+
+//#include <llvm/PassManager.h>
+//#include <llvm/Transforms/IPO/PassManagerBuilder.h>
+
+#include <hrtime.h>
 
 static cl::OptionCategory eIRDumpOptions("LLVM IR Dump Options", "These options control dumping of LLVM IR.");
 static cl::opt<bool> DumpGeneratedIR("dump-generated-IR", cl::init(false), cl::desc("Print LLVM IR generated by Pablo Compiler."), cl::cat(eIRDumpOptions));
+static cl::opt<std::string> IROutputFilename("dump-generated-IR-output", cl::init(""), cl::desc("output IR filename"), cl::cat(eIRDumpOptions));
+
 
 static cl::OptionCategory fTracingOptions("Run-time Tracing Options", "These options control execution traces.");
@@ -76 +85 @@
 llvm::Function * PabloCompiler::compile(PabloFunction * function) {
 
+    #ifdef PRINT_TIMING_INFORMATION
+    const timestamp_t pablo_compilation_start = read_cycle_counter();
+    #endif
   
     PabloBlock * const mainScope = function->getEntryBlock();
@@ -126 +138 @@
     
     // Clean up
-    delete mCarryManager; mCarryManager = nullptr;
-    
+    delete mCarryManager;
+    mCarryManager = nullptr;
+    
+    #ifdef PRINT_TIMING_INFORMATION
+    const timestamp_t pablo_compilation_end = read_cycle_counter();
+    std::cerr << "PABLO COMPILATION TIME: " << (pablo_compilation_end - pablo_compilation_start) << std::endl;
+    #endif
+
+//    llvm::PassManager pm;
+//    llvm::PassManagerBuilder pmb;
+//    pmb.OptLevel = 3;
+//    pmb.populateModulePassManager(pm);
+//    pm.run(*mMod);
+
     if (LLVM_UNLIKELY(DumpGeneratedIR)) {
-        mMod->dump();
+
+        if (IROutputFilename.empty()) {
+            mMod->dump();
+        } else {
+            std::error_code error;
+            llvm::raw_fd_ostream out(IROutputFilename, error, sys::fs::OpenFlags::F_None);
+            mMod->print(out, nullptr);
+        }
     }
 

icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.cpp

@@ -6 +6 @@
 #include <pablo/passes/flattenassociativedfg.h>
 #include <boost/container/flat_set.hpp>
+#include <boost/circular_buffer.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/adjacency_matrix.hpp>
+#include <boost/graph/topological_sort.hpp>
+#include <queue>
+#include <tuple>
+
 #include <set>
+#include <type_traits>
+
+#include <pablo/printer_pablos.h>
+#include <iostream>
 
 using namespace boost;
 using namespace boost::container;
 
-
 namespace pablo {
 
-using VertexSet = std::vector<PabloAST *>;
-using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
-using BicliqueSet = std::vector<Biclique>;
 using TypeId = PabloAST::ClassTypeId;
 
-///** ------------------------------------------------------------------------------------------------------------- *
-// * @brief lower
-// ** ------------------------------------------------------------------------------------------------------------- */
-//inline PabloAST * FactorizeDFG::lower(Variadic * const var, PabloBlock * block, OrderingMap & order) {
-//    PabloAST * result = nullptr;
-//    assert (var->getNumOperands() > 2);
-////    // Sort the operands by their order in the current AST
-////    std::sort(var->begin(), var->end(),
-////        [&order](const PabloAST * const a, const PabloAST * const b)
-////    {
-////        return order.of(a) > order.of(b);
-////    });
-////    unsigned operands = var->getNumOperands();
-////    // Swap the final two operands so that we can just append the temporary calculations onto the end
-////    // and trust that the PENULTIMATE operand is the "latest" in the AST.
-////    PabloAST * const item = var->getOperand(operands - 1);
-////    var->setOperand(operands - 1, var->getOperand(operands - 2));
-////    var->setOperand(operands - 2, item);
-//    // Finally rewrite all of the variadic statements as binary operations
-//    block->setInsertPoint(var->getPrevNode());
-//    while (var->getNumOperands() > 1) {
-//        PabloAST * const op2 = var->removeOperand(1);
-//        PabloAST * const op1 = var->removeOperand(0);
-//        assert (op1 != op2);
-//        if (isa<And>(var)) {
-//            result = block->createAnd(op1, op2);
-//        } else if (isa<Or>(var)) {
-//            result = block->createOr(op1, op2);
-//        } else { // if (isa<Xor>(var)) {
-//            result = block->createXor(op1, op2);
-//        }
-//        var->addOperand(result);
-//    }
-//    assert (result);
-//    return result;
-//}
-
-///** ------------------------------------------------------------------------------------------------------------- *
-// * @brief lower
-// ** ------------------------------------------------------------------------------------------------------------- */
-//void FactorizeDFG::lower(PabloBlock * const block, OrderingMap & parent) {
-//    OrderingMap order(parent);
-//    Statement * stmt = block->front();
-//    while (stmt) {
-//        if (isa<If>(stmt) || isa<While>(stmt)) {
-//            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), order);
-//            if (isa<If>(stmt)) {
-//                for (Assign * def : cast<If>(stmt)->getDefined()) {
-//                    order.enumerate(def);
-//                }
-//            } else { // if (isa<While>(stmt)) {
-//                for (Next * var : cast<While>(stmt)->getVariants()) {
-//                    order.enumerate(var);
-//                }
-//            }
-//        } else {
-//            if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
-//                // We should maintain an ordering list and sort each Variadic according to it prior to writing them out.
-//                PabloAST * result = lower(cast<Variadic>(stmt), block, order);
-//                order.enumerate(result);
-//                stmt = stmt->replaceWith(result, true);
-//                continue;
-//            }
-//            order.enumerate(stmt);
-//        }
-//        stmt = stmt->getNextNode();
-//    }
-//}
-
-/** ------------------------------------------------------------------------------------------------------------- *
- * @brief finalize
- ** ------------------------------------------------------------------------------------------------------------- */
-inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) {
-    PabloAST * result = nullptr;
+// TODO: move the "tryToPartiallyExtractVariadic" from the coalescedfg class into here to run prior to lowering?
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief lower
+ *
+ * The goal of this function is to try and lower a variadic operation into binary form while attempting to mitigate
+ * register pressure under the assumption that LLVM is not going to significantly change the IR (which was observed
+ * when assessing the ASM output of LLVM 3.6.1 using O3.)
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) const {
+
+    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *, int>;
+    using Vertex = Graph::vertex_descriptor;
+    using Map = flat_map<const PabloAST *, Vertex>;
+    using SchedulingData = std::pair<unsigned, PabloAST *>;
+    using SchedulingQueue = std::priority_queue<SchedulingData, std::vector<SchedulingData>, std::greater<SchedulingData>>;
+
+    const unsigned NOT_STEP = 1;
+    const unsigned BOOLEAN_STEP = 10;
+    const unsigned OTHER_STEP = 30;
+    const unsigned DESIRED_GAP = 30;
+
+    assert (var->getParent() == block);
     assert (var->getNumOperands() > 2);
-    block->setInsertPoint(var->getPrevNode());
-    while (var->getNumOperands() > 1) {
-        PabloAST * const op2 = var->removeOperand(1);
-        PabloAST * const op1 = var->removeOperand(0);
-        assert (op1 != op2);
+
+    // Begin by computing a graph G depicting which operands are used by which statements. We know that
+    // all of them are used by the Variadic but they might be used elsewhere in the current block.
+
+
+    // If this operand was defined in this block, we want to indicate that in G as well so that we
+    // don't mistakingly pair them together.
+
+    const unsigned operands = var->getNumOperands();
+
+    Graph G(operands + 1);
+    Map M;
+
+    G[operands] = var;
+    M.emplace(var, operands);
+
+    for (Vertex u = 0; u != operands; ++u) {
+        PabloAST * const op = var->getOperand(u);
+        G[u] = op;
+        M.emplace(op, u);
+        assert ("AST structural error!" && (op->getNumUses() > 0));
+        for (PabloAST * user : op->users()) {
+            if (LLVM_LIKELY(isa<Statement>(user))) {
+                Statement * usage = cast<Statement>(user);
+                PabloBlock * scope = usage->getParent();
+                while (scope) {
+                    if (scope == block) {
+                        auto f = M.find(usage);
+                        Vertex v = 0;
+                        if (f == M.end()) {
+                            v = add_vertex(usage, G);
+                            M.emplace(usage, v);
+                        } else {
+                            v = f->second;
+                        }
+                        G[add_edge(u, v, G).first] = 0;
+                        break;
+                    }
+                    usage = scope->getBranch();
+                    scope = scope->getParent();
+                }
+            }
+        }
+    }
+
+    assert (M.count(var) == 1);
+
+    unsigned estQuantum = 0;
+    circular_buffer<std::pair<unsigned, Vertex>> defs(operands);
+    for (Statement * stmt : *block) {
+        switch (stmt->getClassTypeId()) {
+            case TypeId::And:
+            case TypeId::Or:
+            case TypeId::Xor:
+                estQuantum += BOOLEAN_STEP;
+                break;
+            case TypeId::Not:
+                estQuantum += NOT_STEP;
+                break;
+            default:
+                estQuantum += OTHER_STEP;
+        }
+        auto f = M.find(stmt);
+        if (LLVM_UNLIKELY(f != M.end())) {
+            const auto u = f->second;
+            if (LLVM_UNLIKELY(u == operands)) {
+                assert (stmt == var);
+                break;
+            }
+            for (auto e : make_iterator_range(in_edges(u, G)))   {
+                G[e] = estQuantum;
+            }
+            if (u < operands) {
+                defs.push_back(std::make_pair(estQuantum + DESIRED_GAP, u));
+            }
+        }
+        // Annotate G to indicate when we expect a statement will be available
+        while (defs.size() > 0) {
+            unsigned availQuantum = 0;
+            Vertex u = 0;
+            std::tie(availQuantum, u) = defs.front();
+            if (availQuantum > estQuantum) {
+                break;
+            }
+            defs.pop_front();
+            auto f = M.find(stmt);
+            Vertex v = 0;
+            if (f == M.end()) {
+                v = add_vertex(stmt, G);
+                M.emplace(stmt, v);
+            } else {
+                v = f->second;
+            }
+            G[add_edge(u, v, G).first] = estQuantum;
+        }
+    }
+
+    for (Vertex u = 0; u < operands; ++u) {
+        unsigned quantum = 0;
+        Vertex v = operands;
+        for (auto e : make_iterator_range(out_edges(u, G))) {
+            if (quantum < G[e]) {
+                quantum = G[e];
+                v = target(e, G);
+            }
+        }
+        clear_out_edges(u, G);
+        G[add_edge(u, v, G).first] = quantum;
+    }
+
+    for (auto e : make_iterator_range(in_edges(operands, G)))   {
+        G[e] = estQuantum;
+    }
+
+    assert (num_edges(G) == var->getNumOperands());
+
+    SchedulingQueue Q;
+    while (num_edges(G) > 0) {
+
+        Graph::edge_descriptor f;
+        unsigned quantum = std::numeric_limits<unsigned>::max();
+        for (auto e : make_iterator_range(edges(G))) {
+            if (in_degree(source(e, G), G) == 0) {
+                if (quantum > G[e]) {
+                    quantum = G[e];
+                    f = e;
+                }
+            }
+        }
+
+        assert ("No edge selected!" && (quantum < std::numeric_limits<unsigned>::max()));
+
+        const auto u = source(f, G);
+        assert (u < operands);
+        const auto v = target(f, G);
+        assert (isa<Statement>(G[v]));
+        // Since this might have been a target of a prior pairing, read the original operand value instead of
+        // G when checking which value is indicated by u.
+        PabloAST * const op1 = var->getOperand(u);
+        block->setInsertPoint(cast<Statement>(G[v]));
+        remove_edge(f, G);
+
+        if (LLVM_LIKELY(Q.size() > 0)) {
+            unsigned minQuantum = 0; PabloAST * op2 = nullptr;
+            std::tie(minQuantum, op2) = Q.top();
+            if (minQuantum < quantum) {
+                Q.pop();
+                PabloAST * result = nullptr;
+                if (isa<And>(var)) {
+                    result = block->createAnd(op1, op2);
+                } else if (isa<Or>(var)) {
+                    result = block->createOr(op1, op2);
+                } else { // if (isa<Xor>(var)) {
+                    result = block->createXor(op1, op2);
+                }
+                Q.emplace(quantum + DESIRED_GAP, result);
+                G[v] = result; // update the insertion point node value
+                continue;
+            }
+        }
+        Q.emplace(quantum, op1);
+    }
+
+    // If we've done our best to schedule the statements and have operands remaining in our queue, generate a
+    // tree of the remaining operands.
+    while (Q.size() > 1) {
+        unsigned q1 = 0; PabloAST * op1 = nullptr;
+        std::tie(q1, op1) = Q.top();
+        Q.pop();
+
+        unsigned q2 = 0; PabloAST * op2 = nullptr;
+        std::tie(q2, op2) = Q.top();
+        Q.pop();
+
+        PabloAST * result = nullptr;
         if (isa<And>(var)) {
             result = block->createAnd(op1, op2);
@@ -106 +232 @@
             result = block->createXor(op1, op2);
         }
-        var->addOperand(result);
-    }
+        Q.emplace(std::max(q1, q2) + DESIRED_GAP, result);
+    }
+
+    assert (Q.size() == 1);
+    return var->replaceWith(std::get<1>(Q.top()));
+}
+
+#if 0
+using EnumerationMap = flat_map<const PabloAST *, unsigned>;
+
+inline void enumerate(PabloBlock * const block, EnumerationMap & M, std::vector<Statement *> & S) {
+    for (Statement * stmt : *block) {
+        M.emplace(stmt, static_cast<int>(S.size()));
+        S.push_back(stmt);
+    }
+}
+
+inline static unsigned indexOf(const PabloAST * const expr, const EnumerationMap & M) {
+    assert (expr);
+    const auto f = M.find(expr);
+    assert (f != M.end());
+    return f->second;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief lower
+ *
+ * The goal of this function is to try and lower a variadic operation into binary form while attempting to mitigate
+ * register pressure under the assumption that LLVM is not going to significantly change the IR (which was observed
+ * when assessing the ASM output of LLVM 3.6.1 using O3.)
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) const {
+
+    assert (var->getNumOperands() > 2);
+
+    EnumerationMap M;
+    std::vector<Statement *> S;
+
+    enumerate(block, M, S);
+
+    const int varIdx = indexOf(var, M);
+
+    circular_buffer<std::tuple<unsigned, unsigned, PabloAST *>> lowered(var->getNumOperands());
+    for (unsigned i = 0; i != var->getNumOperands(); ++i) {
+        PabloAST * const op = var->getOperand(i);
+
+        unsigned defIdx = 0;
+        if (LLVM_LIKELY(isa<Statement>(op))) {
+            Statement * producer = cast<Statement>(op);
+            PabloBlock * scope = producer->getParent();
+            while (scope && (scope != block)) {
+                producer = scope->getBranch();
+                scope = scope->getParent();
+            }
+            defIdx = producer ? indexOf(producer, M) : 0;
+        }
+
+        unsigned useIdx = defIdx;
+        for (PabloAST * user : op->users()) {
+            // if this user is in the current scope or a nested scope of this block
+            if ((cast<Statement>(user)->getParent() == block) && (user != var)) {
+                useIdx = std::max(useIdx, indexOf(user, M));
+            }
+        }
+        if (useIdx > varIdx) {
+            useIdx = varIdx;
+        }
+        assert (!lowered.full());
+        lowered.push_back(std::make_tuple(useIdx, defIdx, op));
+    }
+
+    std::sort(lowered.begin(), lowered.end());
+
+    PabloAST * result = nullptr;
+    while (lowered.size() > 1) {
+
+        PabloAST * op1, * op2;
+        unsigned def1, def2;
+        unsigned use1, use2;
+
+        std::tie(use1, def1, op1) = lowered.front(); lowered.pop_front();
+        std::tie(use2, def2, op2) = lowered.front(); lowered.pop_front();
+
+//        if (((def1 < def2) ? ((def1 + 3) > def2) : ((def2 + 3) > def1)) && (lowered.size() > 0)) {
+//            unsigned def3 = def1;
+//            unsigned use3 = use1;
+//            PabloAST * op3 = op1;
+//            std::tie(use1, def1, op1) = lowered.front(); lowered.pop_front();
+//            lowered.push_front(std::make_tuple(use3, def3, op3));
+//        }
+
+        // Is the last use of op1 prior to the definition of op2?
+        if (use1 < def2) {
+            use1 = def2;
+        }
+
+        block->setInsertPoint(S[use1]);
+
+        if (isa<And>(var)) {
+            result = block->createAnd(op1, op2);
+        } else if (isa<Or>(var)) {
+            result = block->createOr(op1, op2);
+        } else { // if (isa<Xor>(var)) {
+            result = block->createXor(op1, op2);
+        }
+
+        S[use1] = cast<Statement>(result);
+
+        assert (!lowered.full());
+        lowered.push_front(std::make_tuple(use1, use1, result));
+    }
+    assert (result);
+
     return var->replaceWith(result, true);
 }
-
-/** ------------------------------------------------------------------------------------------------------------- *
- * @brief finalize
- ** ------------------------------------------------------------------------------------------------------------- */
-void FactorizeDFG::lower(PabloBlock * const block) {
+#endif
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief lower
+ ** ------------------------------------------------------------------------------------------------------------- */
+void FactorizeDFG::lower(PabloBlock * const block) const {
     Statement * stmt = block->front();
     while (stmt) {
         if (isa<If>(stmt) || isa<While>(stmt)) {
             lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
-        } else if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
-            // We should maintain an ordering list and sort each Variadic according to it prior to writing them out.
+        } else if ((stmt->getNumOperands() > 2) && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
             stmt = lower(cast<Variadic>(stmt), block);
             continue;
@@ -128 +365 @@
 }
 
-///** ------------------------------------------------------------------------------------------------------------- *
-// * @brief lower
-// ** ------------------------------------------------------------------------------------------------------------- */
-//inline void FactorizeDFG::lower(PabloFunction & function) {
-//    OrderingMap ordering;
-//    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
-//        ordering.enumerate(function.getParameter(i));
-//    }
-//    lower(function.getEntryBlock(), ordering);
-//}
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief lower
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline void FactorizeDFG::lower(PabloFunction & function) const {
+    lower(function.getEntryBlock());
+}
+
+#if 0
+
+using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, PabloAST *>;
+using Vertex = Graph::vertex_descriptor;
+using Map = flat_map<const PabloAST *, Vertex>;
+
+using VertexSet = std::vector<PabloAST *>;
+using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
+using BicliqueSet = std::set<Biclique>;
+using TypeId = PabloAST::ClassTypeId;
 
 /** ------------------------------------------------------------------------------------------------------------- *
@@ -145 +389 @@
  * bicliques" by Alexe et. al. (2003).
  ** ------------------------------------------------------------------------------------------------------------- */
-static BicliqueSet enumerateBicliques(Variadic * const var) {
-    using IntersectionSets = std::set<VertexSet>;
+inline void FactorizeDFG::enumerateBicliques(Variadic * const var, BicliqueSet & bicliques) {
+    using IntersectionSets = flat_set<VertexSet>;
 
     IntersectionSets B1;
@@ -198 +442 @@
     }
 
-    BicliqueSet bicliques;
-    unsigned userSize = 2;
     for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
-        if (userSize <= Bi->size()) {
-            VertexSet Ai(var->begin(), var->end());
-            for (const PabloAST * user : *Bi) {
-                VertexSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
-                std::sort(Aj.begin(), Aj.end());
-                VertexSet Ak;
-                Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
-                std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
-                Ai.swap(Ak);
-            }
-            if (Ai.size() > 1) {
-                if (userSize < Bi->size()) {
-                    bicliques.clear();
-                    userSize = Bi->size();
-                }
-                bicliques.emplace_back(std::move(Ai), std::move(*Bi));
-            }
-        }
-    }
-    return bicliques;
-}
-
-/** ------------------------------------------------------------------------------------------------------------- *
- * @brief pick
- ** ------------------------------------------------------------------------------------------------------------- */
-inline static Biclique pick(BicliqueSet && bicliques) {
-    unsigned best_w = 0;
-    auto best_c = bicliques.begin();
-    for (auto c = bicliques.begin(); c != bicliques.end(); ++c) {
-        const unsigned w = std::get<0>(*c).size();
-        if (best_w < w) {
-            best_c = c;
-            best_w = w;
-        }
-    }
-    return std::move(*best_c);
-}
-
-/** ------------------------------------------------------------------------------------------------------------- *
- * @brief chooseInsertionPoint
- ** ------------------------------------------------------------------------------------------------------------- */
-inline PabloBlock * FactorizeDFG::chooseInsertionScope(const ASTVector & users) {
+        VertexSet Ai(var->begin(), var->end());
+        for (const PabloAST * user : *Bi) {
+            VertexSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
+            std::sort(Aj.begin(), Aj.end());
+            VertexSet Ak;
+            Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
+            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
+            Ai.swap(Ak);
+        }
+        if (Ai.size() > 1 && Bi->size() > 1) {
+            bicliques.emplace(std::move(Ai), std::move(*Bi));
+        }
+    }
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief intersects
+ ** ------------------------------------------------------------------------------------------------------------- */
+template <class Type>
+inline bool intersects(const Type & A, const Type & B) {
+    auto first1 = A.begin(), last1 = A.end();
+    auto first2 = B.begin(), last2 = B.end();
+    while (first1 != last1 && first2 != last2) {
+        if (*first1 < *first2) {
+            ++first1;
+        } else if (*first2 < *first1) {
+            ++first2;
+        } else {
+            return true;
+        }
+    }
+    return false;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief independentCliqueSets
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline void FactorizeDFG::independentCliqueSets(BicliqueSet & bicliques) {
+    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
+
+    const auto l = bicliques.size();
+    IndependentSetGraph I(l);
+
+    // Initialize our weights and determine the constraints
+    for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
+        I[std::distance(bicliques.begin(), i)] = std::pow(std::get<0>(*i).size(), 2);
+        for (auto j = i; ++j != bicliques.end(); ) {
+            if (intersects(i->second, j->second) && intersects(i->first, j->first)) {
+                add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
+            }
+        }
+    }
+
+    // Use the greedy algorithm to choose our independent set
+    std::vector<Vertex> selected;
+    for (;;) {
+        unsigned w = 0;
+        Vertex u = 0;
+        for (unsigned i = 0; i != l; ++i) {
+            if (I[i] > w) {
+                w = I[i];
+                u = i;
+            }
+        }
+        if (w < 2) break;
+        selected.push_back(u);
+        I[u] = 0;
+        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
+            I[v] = 0;
+        }
+    }
+
+    // Sort the selected list and then remove the unselected cliques
+    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
+    auto end = bicliques.end();
+    for (const unsigned offset : selected) {
+        end = bicliques.erase(bicliques.begin() + offset + 1, end) - 1;
+    }
+    bicliques.erase(bicliques.begin(), end);
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief findInsertionPoint
+ *
+ * Look for the first user in this scope; if none can be found, look for the last operand.
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline PabloBlock * FactorizeDFG::findInsertionPoint(NodeSet & operands, NodeSet & users) const {
 
     ScopeSet scopes;
     scopes.reserve(users.size());
 
-    flat_set<PabloBlock *> visited;
-    visited.reserve(users.size());
-
     for (PabloAST * user : users) {
-        PabloBlock * const scope = cast<Statement>(user)->getParent();
-        assert (scope);
-        if (visited.insert(scope).second) {
+        PabloBlock * const scope = cast<Statement>(user)->getParent(); assert (scope);
+        if (std::find(scopes.begin(), scopes.end(), scope) == scopes.end()) {
             scopes.push_back(scope);
         }
+    }
+
+    if (LLVM_UNLIKELY(scopes.size() == 1)) {
+        PabloBlock * const scope = scopes.front();
+        Statement * stmt = scope->front();
+        std::sort(users.begin(), users.end());
+        while (stmt) {
+            if (LLVM_UNLIKELY(std::binary_search(users.begin(), users.end(), stmt))) {
+                scope->setInsertPoint(stmt->getPrevNode());
+                return scope;
+            }
+            stmt = stmt->getNextNode();
+        }
+        llvm_unreachable("Failed to locate user in single scope block!");
     }
 
@@ -286 +583 @@
     }
     assert (scopes.size() == 1);
-    return scopes[0];
-}
-
-/** ------------------------------------------------------------------------------------------------------------- *
- * @brief findInsertionPoint
- ** ------------------------------------------------------------------------------------------------------------- */
-void FactorizeDFG::findInsertionPoint(const ASTVector & operands, PabloBlock * const scope) {
-    const flat_set<const PabloAST *> ops(operands.begin(), operands.end());
+
+    PabloBlock * const scope = scopes.front();
     Statement * stmt = scope->back();
-    scope->setInsertPoint(nullptr);
+    std::sort(operands.begin(), operands.end());
     while (stmt) {
         if (isa<If>(stmt)) {
             for (Assign * def : cast<If>(stmt)->getDefined()) {
-                if (ops.count(def)) {
+                if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), def))) {
                     scope->setInsertPoint(stmt);
-                    return;
+                    return scope;
                 }
             }
         } else if (isa<While>(stmt)) {
             for (Next * var : cast<While>(stmt)->getVariants()) {
-                if (ops.count(var)) {
+                if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), var))) {
                     scope->setInsertPoint(stmt);
-                    return;
-                }
-            }
-        } else if (ops.count(stmt)) {
+                    return scope;
+                }
+            }
+        } else if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), stmt))) {
             scope->setInsertPoint(stmt);
-            break;
+            return scope;
         }
         stmt = stmt->getPrevNode();
     }
-}
-
-/** ------------------------------------------------------------------------------------------------------------- *
- * @brief cse
- ** ------------------------------------------------------------------------------------------------------------- */
-inline void FactorizeDFG::cse(Variadic * var) {
-    while (var->getNumOperands() > 2) {
-        BicliqueSet bicliques = enumerateBicliques(var);
-        if (bicliques.empty()) {
-            break;
-        }
-        ASTVector operands;
-        ASTVector users;
-        std::tie(operands, users) = pick(std::move(bicliques));
-        PabloBlock * const block = chooseInsertionScope(users);
-        findInsertionPoint(operands, block);
+    scope->setInsertPoint(nullptr);
+    return scope;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief processBicliques
+ ** ------------------------------------------------------------------------------------------------------------- */
+void FactorizeDFG::processBicliques(BicliqueSet & bicliques) const {
+    independentCliqueSets(bicliques);
+    for (Biclique & B : bicliques) {
+        VertexSet & operands = B.first;
+        VertexSet & users = B.second;
+        PabloBlock * const block = findInsertionPoint(operands, users);
         Variadic * factored = nullptr;
-        if (isa<And>(var)) {
+        if (isa<And>(users.front())) {
             factored = block->createAnd(operands.begin(), operands.end());
-        } else if (isa<Or>(var)) {
+        } else if (isa<Or>(users.front())) {
             factored = block->createOr(operands.begin(), operands.end());
         } else { // if (isa<Xor>(var)) {
@@ -348 +636 @@
         }
     }
-}
-
-/** ------------------------------------------------------------------------------------------------------------- *
- * @brief cse
+    bicliques.clear();
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief factor
  *
  * Perform common subexpression elimination on the Variadic statements
  ** ------------------------------------------------------------------------------------------------------------- */
-void FactorizeDFG::cse(PabloBlock * const block) {
+void FactorizeDFG::factor(PabloBlock * const block, BicliqueSet & bicliques) const {
     Statement * stmt = block->front();
     while (stmt) {
-        if (isa<If>(stmt) || isa<While>(stmt)) {            
-            cse(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
+        if (isa<If>(stmt) || isa<While>(stmt)) {
+            processBicliques(bicliques);
+            factor(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), bicliques);
+        } else if (stmt->getNumOperands() > 2 && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
+            enumerateBicliques(cast<Variadic>(stmt), bicliques);
+        }
+        stmt = stmt->getNextNode();
+    }
+    processBicliques(bicliques);
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief factor
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline void FactorizeDFG::factor(PabloFunction & function) const {
+    BicliqueSet bicliques;
+    factor(function.getEntryBlock(), bicliques);
+}
+
+#endif
+
+#if 1
+
+using VertexSet = std::vector<PabloAST *>;
+using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
+using BicliqueSet = std::vector<Biclique>;
+using TypeId = PabloAST::ClassTypeId;
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief findAllFactoringsOf
+ *
+ * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
+ * bicliques" by Alexe et. al. (2003).
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline BicliqueSet FactorizeDFG::findAllFactoringsOf(Variadic * const var) {
+    using IntersectionSets = flat_set<VertexSet>;
+
+    IntersectionSets B1;
+    const TypeId typeId = var->getClassTypeId();
+    for (unsigned i = 0; i != var->getNumOperands(); ++i) {
+        PabloAST * const op = var->getOperand(i);
+        VertexSet B;
+        B.reserve(op->getNumUses());
+        for (PabloAST * user : op->users()) {
+            if (user->getClassTypeId() == typeId) {
+                // Only consider a user who is in the same or a nested scope?
+                PabloBlock * scope = cast<Variadic>(user)->getParent();
+                while (scope) {
+                    if (scope == var->getParent()) {
+                        B.push_back(user);
+                        break;
+                    }
+                    scope = scope->getParent();
+                }
+
+//                B.push_back(user);
+            }
+        }
+        std::sort(B.begin(), B.end());
+        B1.insert(std::move(B));
+    }
+
+    IntersectionSets B(B1);
+
+    IntersectionSets Bi;
+
+    VertexSet clique;
+    for (auto i = B1.begin(); i != B1.end(); ++i) {
+        for (auto j = i; ++j != B1.end(); ) {
+            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
+            if (clique.size() > 0) {
+                if (B.count(clique) == 0) {
+                    Bi.insert(clique);
+                }
+                clique.clear();
+            }
+        }
+    }
+
+    while (!Bi.empty()) {
+        B.insert(Bi.begin(), Bi.end());
+        IntersectionSets Bk;
+        for (auto i = B1.begin(); i != B1.end(); ++i) {
+            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
+                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
+                if (clique.size() > 0) {
+                    if (B.count(clique) == 0) {
+                        Bk.insert(clique);
+                    }
+                    clique.clear();
+                }
+            }
+        }
+        Bi.swap(Bk);
+    }
+
+    BicliqueSet bicliques;
+    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
+        VertexSet Ai(var->begin(), var->end());
+        for (const PabloAST * user : *Bi) {
+            VertexSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
+            std::sort(Aj.begin(), Aj.end());
+            VertexSet Ak;
+            Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
+            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
+            Ai.swap(Ak);
+        }
+        if (Ai.size() > 1 && Bi->size() > 1) {
+            bicliques.emplace_back(std::move(Ai), std::move(*Bi));
+        }
+    }
+    return bicliques;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief intersects
+ ** ------------------------------------------------------------------------------------------------------------- */
+template <class Type>
+inline bool intersects(const Type & A, const Type & B) {
+    auto first1 = A.begin(), last1 = A.end();
+    auto first2 = B.begin(), last2 = B.end();
+    assert (std::is_sorted(first1, last1));
+    assert (std::is_sorted(first2, last2));
+    while (first1 != last1 && first2 != last2) {
+        if (*first1 < *first2) {
+            ++first1;
+        } else if (*first2 < *first1) {
+            ++first2;
+        } else {
+            return true;
+        }
+    }
+    return false;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief independentCliqueSets
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline void FactorizeDFG::independentCliqueSets(BicliqueSet & bicliques) {
+    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
+    using Vertex = IndependentSetGraph::vertex_descriptor;
+
+    const auto l = bicliques.size();
+    IndependentSetGraph I(l);
+
+    // Initialize our weights and determine the constraints
+    for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
+        I[std::distance(bicliques.begin(), i)] = std::pow(std::get<0>(*i).size(), 2);
+        for (auto j = i; ++j != bicliques.end(); ) {
+            if (intersects(i->second, j->second) && intersects(i->first, j->first)) {
+                add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
+            }
+        }
+    }
+
+    // Use the greedy algorithm to choose our independent set
+    std::vector<Vertex> selected;
+    for (;;) {
+        unsigned w = 0;
+        Vertex u = 0;
+        for (unsigned i = 0; i != l; ++i) {
+            if (I[i] > w) {
+                w = I[i];
+                u = i;
+            }
+        }
+        if (w < 2) break;
+        selected.push_back(u);
+        I[u] = 0;
+        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
+            I[v] = 0;
+        }
+    }
+
+    // Sort the selected list and then remove the unselected cliques
+    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
+    auto end = bicliques.end();
+    for (const unsigned offset : selected) {
+        end = bicliques.erase(bicliques.begin() + offset + 1, end) - 1;
+    }
+    bicliques.erase(bicliques.begin(), end);
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief findInsertionScope
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline PabloBlock * FactorizeDFG::findInsertionScope(const NodeSet & users) const {
+    ScopeSet scopes;
+    scopes.reserve(users.size());
+
+    for (PabloAST * user : users) {
+        PabloBlock * const scope = cast<Statement>(user)->getParent(); assert (scope);
+        if (std::find(scopes.begin(), scopes.end(), scope) == scopes.end()) {
+            scopes.push_back(scope);
+        }
+    }
+
+    while (scopes.size() > 1) {
+        // Find the LCA of both scopes then add the LCA back to the list of scopes.
+        PabloBlock * scope1 = scopes.back(); scopes.pop_back();
+        PabloBlock * scope2 = scopes.back(); scopes.pop_back();
+        if (scope1 != scope2) {
+            unsigned depth1 = scopeDepthOf(scope1);
+            unsigned depth2 = scopeDepthOf(scope2);
+            // If one of these scopes is nested deeper than the other, scan upwards through
+            // the scope tree until both scopes are at the same depth.
+            while (depth1 > depth2) {
+                scope1 = scope1->getParent();
+                --depth1;
+            }
+            while (depth1 < depth2) {
+                scope2 = scope2->getParent();
+                --depth2;
+            }
+            // Then iteratively step backwards until we find a matching set of scopes; this
+            // must be the LCA of our original scopes.
+            while (scope1 != scope2) {
+                scope1 = scope1->getParent();
+                scope2 = scope2->getParent();
+            }
+            assert (scope1 && scope2);
+        }
+        if (LLVM_LIKELY(std::find(scopes.begin(), scopes.end(), scope1) == scopes.end())) {
+            scopes.push_back(scope1);
+        }
+    }
+    assert (scopes.size() == 1);
+
+    return scopes.front();
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief makeCheckSet
+ ** ------------------------------------------------------------------------------------------------------------- */
+FactorizeDFG::CheckSet FactorizeDFG::makeCheckSet(PabloBlock * const scope, const NodeSet & values) const {
+    CheckSet checks;
+    assert (scope);
+    const unsigned baseScopeDepth = scopeDepthOf(scope);
+    for (PabloAST * value : values) {
+        if (isa<Statement>(value)) {
+            unsigned scopeDepth = scopeDepthOf(cast<Statement>(value)->getParent());
+            // Is this from a preceeding scope? Or a nested scope?
+            if (scopeDepth < baseScopeDepth) {
+                continue;
+            } else if (scopeDepth > baseScopeDepth) {
+                // If we're in a nested scope, we want to know what branch statement enters it and
+                // add that to our checks instead of the operand itself.
+                PabloBlock * nested = cast<Statement>(value)->getParent();
+                for (;;) {
+                    assert (nested);
+                    value = nested->getBranch();
+                    nested = nested->getParent();
+                    if (nested == scope) {
+                        break;
+                    }
+                }
+            }
+            checks.insert(value);
+        }
+    }
+    return checks;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief firstIn
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline Statement * FactorizeDFG::firstIn(PabloBlock * const scope, Statement * stmt, const NodeSet & users) const {
+    const auto checks = makeCheckSet(scope, users);
+    while (stmt) {
+        if (LLVM_UNLIKELY(checks.count(stmt) != 0)) {
+            break;
+        }
+        stmt = stmt->getNextNode();
+    }
+    return stmt;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief lastIn
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline Statement * FactorizeDFG::lastIn(PabloBlock * const scope, Statement * stmt, const NodeSet & operands) const {
+    const auto checks = makeCheckSet(scope, operands);
+    while (stmt) {
+        if (LLVM_UNLIKELY(checks.count(stmt) != 0)) {
+            break;
+        }
+        stmt = stmt->getPrevNode();
+    }
+    return stmt;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief findInsertionPoint
+ *
+ * Look for the first user in this scope; if none can be found, look for the last operand.
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline PabloBlock * FactorizeDFG::findInsertionPoint(const NodeSet & operands, const NodeSet & users) const {
+    PabloBlock * const scope = findInsertionScope(users);
+    Statement * const lastOperand = lastIn(scope, scope->back(), operands);
+    Statement * const firstUsage = firstIn(scope, lastOperand, users);
+    scope->setInsertPoint(firstUsage ? firstUsage->getPrevNode() : lastOperand);
+    return scope;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief factor
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline void FactorizeDFG::factor(Variadic * const var, Variadics & factors) const {
+    if (var->getNumOperands() > 2) {
+        BicliqueSet S = findAllFactoringsOf(var);
+        if (S.empty()) return;
+        independentCliqueSets(S);
+        assert (S.size() > 0);
+        for (Biclique & B : S) {
+            VertexSet & operands = B.first;
+            VertexSet & users = B.second;
+            PabloBlock * const block = findInsertionPoint(operands, users);
+            Variadic * factoring = nullptr;
+            if (isa<And>(var)) {
+                factoring = block->createAnd(operands.begin(), operands.end());
+            } else if (isa<Or>(var)) {
+                factoring = block->createOr(operands.begin(), operands.end());
+            } else { // if (isa<Xor>(var)) {
+                factoring = block->createXor(operands.begin(), operands.end());
+            }
+            for (PabloAST * user : users) {
+                for (PabloAST * op : operands) {
+                    cast<Variadic>(user)->deleteOperand(op);
+                }
+                cast<Variadic>(user)->addOperand(factoring);
+            }
+            if (factoring->getNumOperands() > 2) {
+                if (LLVM_UNLIKELY(factors.full())) {
+                    factors.set_capacity(factors.capacity() + factors.capacity() / 2);
+                }
+                factors.push_back(factoring);
+            }
+        }
+        if (var->getNumOperands() > 2) {
+            if (LLVM_UNLIKELY(factors.full())) {
+                factors.set_capacity(factors.capacity() + factors.capacity() / 2);
+            }
+            factors.push_back(var);
+        } else if (var->getNumOperands()  == 1) {
+            var->replaceWith(var->getOperand(0));
+        }
+    }
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief factor
+ *
+ * Perform common subexpression elimination on the Variadic statements
+ ** ------------------------------------------------------------------------------------------------------------- */
+void FactorizeDFG::factor(PabloBlock * const block, Variadics & vars) const {
+    Statement * stmt = block->front();
+    while (stmt) {
+        if (isa<If>(stmt) || isa<While>(stmt)) {
+            factor(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), vars);
+        } else if (stmt->getNumOperands() > 2 && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
+            assert (!vars.full());
+            vars.push_back(cast<Variadic>(stmt));
+        }
+        stmt = stmt->getNextNode();
+    }
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief factor
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline void FactorizeDFG::factor(PabloFunction & function) const {
+    Variadics vars(mNumOfVariadics);
+    factor(function.getEntryBlock(), vars);
+    while (vars.size() > 0) {
+        Variadic * var = vars.front();
+        vars.pop_front();
+        factor(var, vars);
+    }
+}
+
+#endif
+
+#if 0
+
+using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, PabloAST *>;
+using Vertex = Graph::vertex_descriptor;
+using Map = flat_map<const PabloAST *, Vertex>;
+
+using VertexSet = std::vector<Vertex>;
+using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
+using BicliqueSet = std::vector<Biclique>;
+using TypeId = PabloAST::ClassTypeId;
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief enumerateBicliques
+ *
+ * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
+ * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
+ * bipartition A and their adjacencies to be in B.
+  ** ------------------------------------------------------------------------------------------------------------- */
+template <class Graph>
+static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
+    using IntersectionSets = std::set<VertexSet>;
+
+    IntersectionSets B1;
+    for (auto u : A) {
+        if (out_degree(u, G) > 0) {
+            VertexSet incomingAdjacencies;
+            incomingAdjacencies.reserve(out_degree(u, G));
+            for (auto e : make_iterator_range(out_edges(u, G))) {
+                incomingAdjacencies.push_back(target(e, G));
+            }
+            std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
+            B1.insert(std::move(incomingAdjacencies));
+        }
+    }
+
+    IntersectionSets B(B1);
+
+    IntersectionSets Bi;
+
+    VertexSet clique;
+    for (auto i = B1.begin(); i != B1.end(); ++i) {
+        for (auto j = i; ++j != B1.end(); ) {
+            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
+            if (clique.size() > 0) {
+                if (B.count(clique) == 0) {
+                    Bi.insert(clique);
+                }
+                clique.clear();
+            }
+        }
+    }
+
+    for (;;) {
+        if (Bi.empty()) {
+            break;
+        }
+        B.insert(Bi.begin(), Bi.end());
+        IntersectionSets Bk;
+        for (auto i = B1.begin(); i != B1.end(); ++i) {
+            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
+                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
+                if (clique.size() > 0) {
+                    if (B.count(clique) == 0) {
+                        Bk.insert(clique);
+                    }
+                    clique.clear();
+                }
+            }
+        }
+        Bi.swap(Bk);
+    }
+
+    BicliqueSet cliques;
+    cliques.reserve(B.size());
+    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
+        VertexSet Ai(A);
+        for (const Vertex u : *Bi) {
+            VertexSet Aj;
+            Aj.reserve(in_degree(u, G));
+            for (auto e : make_iterator_range(in_edges(u, G))) {
+                Aj.push_back(source(e, G));
+            }
+            std::sort(Aj.begin(), Aj.end());
+            VertexSet Ak;
+            Ak.reserve(std::min(Ai.size(), Aj.size()));
+            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
+            Ai.swap(Ak);
+        }
+        assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
+        cliques.emplace_back(std::move(Ai), std::move(*Bi));
+    }
+    return std::move(cliques);
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief intersects
+ ** ------------------------------------------------------------------------------------------------------------- */
+template <class Type>
+inline bool intersects(const Type & A, const Type & B) {
+    auto first1 = A.begin(), last1 = A.end();
+    auto first2 = B.begin(), last2 = B.end();
+    while (first1 != last1 && first2 != last2) {
+        if (*first1 < *first2) {
+            ++first1;
+        } else if (*first2 < *first1) {
+            ++first2;
+        } else {
+            return true;
+        }
+    }
+    return false;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief getMaximalIndependentBicliques
+ ** ------------------------------------------------------------------------------------------------------------- */
+template <unsigned side = 1>
+inline static BicliqueSet && maximalIndependentBicliques(BicliqueSet && cliques, const unsigned minimum = 1) {
+    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
+
+    static_assert((side == 0 || side == 1), "Side must be 0 (bipartition A) or 1 (bipartition B)");
+    assert ("Minimum must be at least 1 or an infinite number of empty sets would be generated!" && minimum > 0);
+
+    const auto l = cliques.size();
+    IndependentSetGraph I(l);
+
+    // Initialize our weights
+    for (unsigned i = 0; i != l; ++i) {
+        I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
+    }
+
+    // Determine our constraints
+    for (unsigned i = 0; i != l; ++i) {
+        for (unsigned j = i + 1; j != l; ++j) {
+            if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
+                add_edge(i, j, I);
+            }
+        }
+    }
+
+    // Use the greedy algorithm to choose our independent set
+    VertexSet selected;
+    for (;;) {
+        unsigned w = 0;
+        Vertex u = 0;
+        for (unsigned i = 0; i != l; ++i) {
+            if (I[i] > w) {
+                w = I[i];
+                u = i;
+            }
+        }
+        if (w < minimum) break;
+        selected.push_back(u);
+        I[u] = 0;
+        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
+            I[v] = 0;
+        }
+    }
+
+    // Sort the selected list and then remove the unselected cliques
+    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
+    auto end = cliques.end();
+    for (const unsigned offset : selected) {
+        end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
+    }
+    cliques.erase(cliques.begin(), end);
+
+    return std::move(cliques);
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief factor
+ ** ------------------------------------------------------------------------------------------------------------- */
+template<class Type>
+inline void factorAny(Graph & G, VertexSet & A, const Biclique & Si, PabloBlock * const block) {
+
+    static_assert (std::is_same<Type, And>::value || std::is_same<Type, Or>::value || std::is_same<Type, Xor>::value, "Can only factor And, Or or Xor statements here!");
+
+    flat_set<Statement *> S;
+    for (auto u : Si.first) {
+        if (isa<Type>(G[u])) {
+            S.insert(cast<Type>(G[u]));
+        }
+    }
+    if (S.empty()) {
+        return;
+    }
+    // find the insertion point for this statement type
+    for (Statement * ip : *block) {
+        if (S.count(ip)) {
+            block->setInsertPoint(ip->getPrevNode());
+            break;
+        }
+    }
+    Variadic * factored = nullptr;
+    if (std::is_same<Type, And>::value) {
+        factored = block->createAnd(Si.second.size());
+    } else if (std::is_same<Type, Or>::value) {
+        factored = block->createOr(Si.second.size());
+    } else if (std::is_same<Type, Xor>::value) {
+        factored = block->createXor(Si.second.size());
+    }
+    const auto u = add_vertex(factored, G);
+    A.push_back(u);
+    for (auto v : Si.second) {
+        factored->addOperand(G[v]);
+        add_edge(u, v, G);
+    }
+    const auto w = add_vertex(factored, G);
+    for (auto u : Si.first) {
+        if (isa<Type>(G[u])) {
+            Type * factoring = cast<Type>(G[u]);
+            for (auto v : Si.second) {
+                factoring->deleteOperand(G[v]);
+                remove_edge(u, v, G);
+            }
+            factoring->addOperand(factored);
+            add_edge(u, w, G);
+        }
+    }
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief eliminateCommonSubexpressions
+ ** ------------------------------------------------------------------------------------------------------------- */
+void eliminateCommonSubexpressions(Graph & G, VertexSet & A, PabloBlock * const block) {
+    for (;;) {
+        const auto S = maximalIndependentBicliques<1>(enumerateBicliques(G, A), 2);
+        if (S.empty()) {
+            break;
+        }
+        for (const Biclique Si : S) {
+            factorAny<And>(G, A, Si, block);
+            factorAny<Or>(G, A, Si, block);
+            factorAny<Xor>(G, A, Si, block);
+        }
+    }
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief factor
+ *
+ * Perform common subexpression elimination on the Variadic statements
+ ** ------------------------------------------------------------------------------------------------------------- */
+void FactorizeDFG::factor(PabloBlock * const block) {
+
+    Graph G;
+    VertexSet A;
+    Map B;
+
+    Statement * stmt = block->front();
+    while (stmt) {
+        if (isa<If>(stmt) || isa<While>(stmt)) {
+            eliminateCommonSubexpressions(G, A, block);
+            G.clear(); A.clear(); B.clear();
+            factor(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
         } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
-            cse(cast<Variadic>(stmt));
+            // When we encounter a reassociative statement, add it and its operands to our bigraph G.
+            const auto u = add_vertex(stmt, G);
+            A.push_back(u);
+            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
+                auto f = B.find(stmt->getOperand(i));
+                if (f == B.end()) {
+                    f = B.emplace(stmt->getOperand(i), add_vertex(stmt->getOperand(i), G)).first;
+                }
+                add_edge(f->second, u, G);
+            }
+        }
+        stmt = stmt->getNextNode();
+    }
+    eliminateCommonSubexpressions(G, A, block);
+}
+#endif
+
+#if 0
+
+using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, PabloAST *>;
+using Matrix = adjacency_matrix<directedS>;
+using Vertex = Graph::vertex_descriptor;
+using Map = flat_map<const PabloAST *, Vertex>;
+using TypeId = PabloAST::ClassTypeId;
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief getVertex
+ ** ------------------------------------------------------------------------------------------------------------- */
+static inline Vertex getVertex(PabloAST * expr, Graph & G, Map & M) {
+    auto f = M.find(expr);
+    if (LLVM_LIKELY(f != M.end())) {
+        return f->second;
+    } else {
+        const Vertex u = add_vertex(expr, G);
+        M.emplace(expr, u);
+        return u;
+    }
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief buildDependencyGraph
+ ** ------------------------------------------------------------------------------------------------------------- */
+static void buildDependencyGraph(PabloBlock * const block, Graph & G, Map & M) {
+    Statement * stmt = block->front();
+    while (stmt) {
+        if (isa<If>(stmt) || isa<While>(stmt)) {
+            buildDependencyGraph(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), G, M);
+        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
+            const Vertex u = getVertex(stmt, G, M);
+            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
+                add_edge(getVertex(stmt->getOperand(i), G, M), u, G);
+            }
+        }
+        stmt = stmt->getNextNode();
+    }
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief transitiveClosure
+ ** ------------------------------------------------------------------------------------------------------------- */
+static Matrix transitiveClosureOf(const Graph & G) {
+    std::vector<Vertex> rto; // reverse topological ordering
+    rto.reserve(num_vertices(G));
+    topological_sort(G, std::back_inserter(rto));
+    Matrix M(num_vertices(G));
+    for (auto u : rto) {
+        for (auto ej : make_iterator_range(in_edges(u, G))) {
+            add_edge(source(ej, G), target(ej, G), M);
+        }
+        for (auto ei : make_iterator_range(out_edges(u, M))) {
+            for (auto ej : make_iterator_range(in_edges(u, G))) {
+                add_edge(source(ej, G), target(ei, M), M);
+            }
+        }
+        add_edge(u, u, M);
+    }
+    return std::move(M);
+}
+
+using VertexSet = std::vector<Vertex>;
+using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
+using BicliqueSet = flat_set<Biclique>;
+using IntersectionSets = std::set<VertexSet>;
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief enumerateBicliques
+ *
+ * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
+ * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
+ * bipartition A and their adjacencies to be in B.
+  ** ------------------------------------------------------------------------------------------------------------- */
+inline static void enumerateBicliques(VertexSet & A, VertexSet & B, const Graph & G, BicliqueSet & bicliques) {
+
+    std::sort(A.begin(), A.end());
+    std::sort(B.begin(), B.end());
+
+    VertexSet S;
+    IntersectionSets B1;
+    for (auto u : A) {
+        S.reserve(out_degree(u, G));
+        for (auto e : make_iterator_range(out_edges(u, G))) {
+            S.push_back(target(e, G));
+        }
+        assert (S.size() > 0);
+        std::sort(S.begin(), S.end());
+        VertexSet T;        
+        std::set_intersection(B.begin(), B.end(), S.begin(), S.end(), std::back_inserter(T));
+        assert (T.size() > 0);
+        B1.emplace(std::move(T));
+        S.clear();
+    }
+
+    IntersectionSets C(B1);
+    IntersectionSets Bi;
+    for (auto i = B1.begin(); i != B1.end(); ++i) {
+        for (auto j = i; ++j != B1.end(); ) {
+            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(S));
+            if (S.size() > 0) {
+                if (C.count(S) == 0) {
+                    Bi.insert(S);
+                }
+                S.clear();
+            }
+        }
+    }
+
+    for (;;) {
+        if (Bi.empty()) {
+            break;
+        }
+        C.insert(Bi.begin(), Bi.end());
+        IntersectionSets Bk;
+        for (auto i = B1.begin(); i != B1.end(); ++i) {
+            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
+                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(S));
+                if (S.size() > 0) {
+                    if (C.count(S) == 0) {
+                        Bk.insert(S);
+                    }
+                    S.clear();
+                }
+            }
+        }
+        Bi.swap(Bk);
+    }
+
+    for (auto Bi = C.begin(); Bi != C.end(); ++Bi) {
+        VertexSet Ai(A);
+        for (const Vertex u : *Bi) {
+            VertexSet Aj;
+            Aj.reserve(in_degree(u, G));
+            for (auto e : make_iterator_range(in_edges(u, G))) {
+                Aj.push_back(source(e, G));
+            }
+            std::sort(Aj.begin(), Aj.end());
+            VertexSet Ak;
+            Ak.reserve(std::min(Ai.size(), Aj.size()));
+            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
+            Ai.swap(Ak);
+        }
+        assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
+        if (Ai.size() > 1 && Bi->size() > 1) {
+            bicliques.emplace(std::move(Ai), std::move(*Bi));
+        }
+    }
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief analyzeGraph
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline static void analyzeGraph(const Vertex u, Graph & G, const Matrix & M, BicliqueSet & bicliques, const unsigned traversalLimit = 10) {
+
+    VertexSet A;
+    VertexSet B;
+
+    std::vector<bool> visited(num_vertices(G), false);
+    circular_buffer<Vertex> Q(64);
+    const TypeId typeId = G[u]->getClassTypeId();
+
+    Vertex v = u;
+    visited[v] = true;
+    for (;;) {
+        bool independent = true;
+        for (auto w : B) {
+            if (M.get_edge(v, w)) {
+                independent = false;
+                break;
+            }
+        }
+        if (independent) {
+            B.push_back(v);
+            if (B.size() < traversalLimit) {
+                for (auto e : make_iterator_range(in_edges(v, G))) {
+                    const auto w = source(e, G);
+                    if (visited[w]) {
+                        continue;
+                    }
+                    bool independent = true;
+                    for (auto x : A) {
+                        if (M.get_edge(w, x)) {
+                            independent = false;
+                            break;
+                        }
+                    }
+                    visited[w] = true;
+                    if (independent) {
+                        A.push_back(w);
+                        for (auto e : make_iterator_range(out_edges(w, G))) {
+                            const auto x = target(e, G);
+                            if (visited[x]) {
+                                continue;
+                            }
+                            visited[x] = true;
+                            if (G[x]->getClassTypeId() == typeId) {
+                                if (LLVM_UNLIKELY(Q.full())) {
+                                    Q.set_capacity(Q.capacity() + (Q.capacity() / 2));
+                                }
+                                Q.push_back(x);
+                            }
+                        }
+                    }
+                }
+            }
+        }
+        if (Q.empty()) {
+            break;
+        }
+        v = Q.front();
+        Q.pop_front();
+    }
+
+    enumerateBicliques(A, B, G, bicliques);
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief intersects
+ ** ------------------------------------------------------------------------------------------------------------- */
+template <class Type>
+inline bool intersects(const Type & A, const Type & B) {
+    auto first1 = A.begin(), last1 = A.end();
+    auto first2 = B.begin(), last2 = B.end();
+    while (first1 != last1 && first2 != last2) {
+        if (*first1 < *first2) {
+            ++first1;
+        } else if (*first2 < *first1) {
+            ++first2;
+        } else {
+            return true;
+        }
+    }
+    return false;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief independentCliqueSets
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline static void independentCliqueSets(BicliqueSet & bicliques, const unsigned minimum) {
+    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
+
+    const auto l = bicliques.size();
+    IndependentSetGraph I(l);
+
+    // Initialize our weights and determine the constraints
+    for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
+        I[std::distance(bicliques.begin(), i)] = std::pow(std::get<0>(*i).size(), 2);
+        for (auto j = i; ++j != bicliques.end(); ) {
+            if (intersects(std::get<1>(*i), std::get<1>(*j))) {
+                add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
+            }
+        }
+    }
+
+    // Use the greedy algorithm to choose our independent set
+    VertexSet selected;
+    for (;;) {
+        unsigned w = 0;
+        Vertex u = 0;
+        for (unsigned i = 0; i != l; ++i) {
+            if (I[i] > w) {
+                w = I[i];
+                u = i;
+            }
+        }
+        if (w < minimum) break;
+        selected.push_back(u);
+        I[u] = 0;
+        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
+            I[v] = 0;
+        }
+    }
+
+    // Sort the selected list and then remove the unselected cliques
+    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
+    auto end = bicliques.end();
+    for (const unsigned offset : selected) {
+        end = bicliques.erase(bicliques.begin() + offset + 1, end) - 1;
+    }
+    bicliques.erase(bicliques.begin(), end);
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief chooseInsertionPoint
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline PabloBlock * FactorizeDFG::chooseInsertionScope(const NodeSet & users) {
+
+    ScopeSet scopes;
+    scopes.reserve(users.size());
+
+    flat_set<PabloBlock *> visited;
+    visited.reserve(users.size());
+
+    for (PabloAST * user : users) {
+        PabloBlock * const scope = cast<Statement>(user)->getParent();
+        assert (scope);
+        if (visited.insert(scope).second) {
+            scopes.push_back(scope);
+        }
+    }
+
+    while (scopes.size() > 1) {
+        // Find the LCA of both scopes then add the LCA back to the list of scopes.
+        PabloBlock * scope1 = scopes.back(); scopes.pop_back();
+        PabloBlock * scope2 = scopes.back(); scopes.pop_back();
+        if (scope1 != scope2) {
+            unsigned depth1 = mScopeDepth.find(scope1)->second;
+            unsigned depth2 = mScopeDepth.find(scope2)->second;
+            // If one of these scopes is nested deeper than the other, scan upwards through
+            // the scope tree until both scopes are at the same depth.
+            while (depth1 > depth2) {
+                scope1 = scope1->getParent();
+                --depth1;
+            }
+            while (depth1 < depth2) {
+                scope2 = scope2->getParent();
+                --depth2;
+            }
+            // Then iteratively step backwards until we find a matching set of scopes; this
+            // must be the LCA of our original scopes.
+            while (scope1 != scope2) {
+                scope1 = scope1->getParent();
+                scope2 = scope2->getParent();
+            }
+            assert (scope1 && scope2);
+        }
+        scopes.push_back(scope1);
+    }
+    assert (scopes.size() == 1);
+    return scopes[0];
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief findInsertionPoint
+ ** ------------------------------------------------------------------------------------------------------------- */
+void FactorizeDFG::findInsertionPoint(const NodeSet & operands, PabloBlock * const scope) {
+    Statement * stmt = scope->back();
+    scope->setInsertPoint(nullptr);
+    assert (std::is_sorted(operands.begin(), operands.end()));
+    while (stmt) {
+        if (isa<If>(stmt)) {
+            for (Assign * def : cast<If>(stmt)->getDefined()) {
+                if (std::binary_search(operands.begin(), operands.end(), def)) {
+                    scope->setInsertPoint(stmt);
+                    return;
+                }
+            }
+        } else if (isa<While>(stmt)) {
+            for (Next * var : cast<While>(stmt)->getVariants()) {
+                if (std::binary_search(operands.begin(), operands.end(), var)) {
+                    scope->setInsertPoint(stmt);
+                    return;
+                }
+            }
+        } else if (std::binary_search(operands.begin(), operands.end(), stmt)) {
+            scope->setInsertPoint(stmt);
+            break;
+        }
+        stmt = stmt->getPrevNode();
+    }
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief factor
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline void FactorizeDFG::factor(PabloFunction & function) {
+
+//    raw_os_ostream out(std::cerr);
+
+//    out << "BEFORE:\n\n";
+//    PabloPrinter::print(function, out);
+//    out << "******************************************\n";
+//    out.flush();
+
+    for (;;) {
+
+        Graph G;
+        {
+            Map M;
+            // Let G be a DAG representing each associative statement and its inputs
+            buildDependencyGraph(function.getEntryBlock(), G, M);
+        }
+
+        BicliqueSet S;
+        {
+            const Matrix M = transitiveClosureOf(G);
+            for (const Vertex u : make_iterator_range(vertices(M))) {
+                if ((in_degree(u, G) > 2) && (isa<And>(G[u]) || isa<Or>(G[u]) || isa<Xor>(G[u]))) {
+                    analyzeGraph(u, G, M, S);
+                }
+            }
+        }
+
+        independentCliqueSets(S, 2);
+
+        if (S.empty()) {
+            break;
+        }
+
+        std::vector<PabloAST *> operands;
+        std::vector<PabloAST *> users;
+
+        for (const Biclique & B : S) {
+            for (auto u : std::get<0>(B)) {
+                operands.push_back(G[u]);
+            }
+            std::sort(operands.begin(), operands.end());
+
+            for (auto u : std::get<1>(B)) {
+                users.push_back(G[u]);
+            }
+            std::sort(users.begin(), users.end());
+
+//            out << " -- factoring {";
+//            for (PabloAST * operand : operands) {
+//                out << ' ';
+//                PabloPrinter::print(operand, out);
+//            }
+//            out << " } from { ";
+//            for (PabloAST * user : users) {
+//                out << ' ';
+//                PabloPrinter::print(user, out);
+//            }
+//            out << " } -> ";
+
+            const TypeId typeId = users.front()->getClassTypeId();
+            assert(typeId == TypeId::And || typeId == TypeId::Or || typeId == TypeId::Xor);
+            #ifndef NDEBUG
+            for (PabloAST * user : users) {
+                assert(user->getClassTypeId() == typeId);
+            }
+            #endif
+            PabloBlock * const block = chooseInsertionScope(users);
+            findInsertionPoint(operands, block);
+            Variadic * factored = nullptr;
+            if (typeId == TypeId::And) {
+                factored = block->createAnd(operands.begin(), operands.end());
+            } else if (typeId == TypeId::Or) {
+                factored = block->createOr(operands.begin(), operands.end());
+            } else { // if (isa<Xor>(var)) {
+                factored = block->createXor(operands.begin(), operands.end());
+            }
+
+//            PabloPrinter::print(factored, out);
+//            out << '\n';
+//            out.flush();
+
+            for (PabloAST * user : users) {
+                for (PabloAST * op : operands) {
+                    cast<Variadic>(user)->deleteOperand(op);
+                }
+                cast<Variadic>(user)->addOperand(factored);
+            }
+            operands.clear();
+            users.clear();
+        }
+//        out << "-----------------------------------------------------------------\n";
+    }
+
+//    out << "AFTER:\n\n";
+//    PabloPrinter::print(function, out);
+//    out << "******************************************\n";
+
+}
+
+
+#endif
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief deMorgansExpansion
+ *
+ * Apply the De Morgans' law to any negated And or Or statement with the intent of further coalescing its operands
+ * thereby allowing the Simplifier to check for tautologies and contradictions.
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline void FactorizeDFG::deMorgansExpansion(Not * const var, PabloBlock * const block) {
+    PabloAST * const negatedVar = var->getOperand(0);
+    if (isa<And>(negatedVar) || isa<Or>(negatedVar)) {
+        const TypeId desiredTypeId = isa<And>(negatedVar) ? TypeId::Or : TypeId::And;
+        bool canApplyDeMorgans = true;
+        for (PabloAST * user : var->users()) {
+            if (desiredTypeId != user->getClassTypeId()) {
+                canApplyDeMorgans = false;
+                break;
+            }
+        }
+        if (canApplyDeMorgans) {
+            const unsigned operands = cast<Variadic>(negatedVar)->getNumOperands();
+            PabloAST * negations[operands];
+            block->setInsertPoint(var);
+            for (unsigned i = 0; i != operands; ++i) {
+                negations[i] = block->createNot(cast<Variadic>(negatedVar)->getOperand(i));
+            }
+            const unsigned users = var->getNumUses();
+            PabloAST * user[users];
+            std::copy(var->user_begin(), var->user_end(), user);
+            for (unsigned i = 0; i != users; ++i) {
+                cast<Variadic>(user[i])->deleteOperand(var);
+                for (unsigned j = 0; j != operands; ++j) {
+                    cast<Variadic>(user[i])->addOperand(negations[j]);
+                }
+            }
+            var->eraseFromParent(true);
+        }
+    }
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief deMorgansExpansion
+ ** ------------------------------------------------------------------------------------------------------------- */
+void FactorizeDFG::deMorgansExpansion(PabloBlock * const block) {
+    Statement * stmt = block->front();
+    while (stmt) {
+        if (isa<If>(stmt) || isa<While>(stmt)) {
+            deMorgansExpansion(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
+        } else if (isa<Not>(stmt)) {
+            deMorgansExpansion(cast<Not>(stmt), block);
         }
         stmt = stmt->getNextNode();
@@ -377 +1835 @@
             mScopeDepth.emplace(body, depth);
             enumerateScopeDepth(body, depth + 1);
+        } else if (stmt->getNumOperands() > 2 && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
+            ++mNumOfVariadics;
         }
         stmt = stmt->getNextNode();
@@ -386 +1846 @@
  ** ------------------------------------------------------------------------------------------------------------- */
 inline void FactorizeDFG::enumerateScopeDepth(const PabloFunction & function) {
-    mScopeDepth.emplace(function.getEntryBlock(), 0);
-    enumerateScopeDepth(function.getEntryBlock(), 1);
+    mScopeDepth.emplace(nullptr, 0);
+    mScopeDepth.emplace(function.getEntryBlock(), 1);
+    enumerateScopeDepth(function.getEntryBlock(), 2);
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief scopeDepthOf
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline unsigned FactorizeDFG::scopeDepthOf(const PabloAST * const expr) const {
+    return LLVM_LIKELY(isa<Statement>(expr)) ? scopeDepthOf(cast<Statement>(expr)->getParent()) : 0;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief scopeDepthOf
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline unsigned FactorizeDFG::scopeDepthOf(const PabloBlock * const block) const {
+    assert (block);
+    const auto f = mScopeDepth.find(block);
+    assert (f != mScopeDepth.end());
+    return f->second;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief ensureLegality
+ *
+ * We don't want to run the simplifier after this as it might undo some of the ordering work we've done. Instead
+ * just do the minimum possible to ensure that each variadic is legal prior to compilation.
+ ** ------------------------------------------------------------------------------------------------------------- */
+void FactorizeDFG::ensureLegality(PabloBlock * const block) {
+    Statement * stmt = block->front();
+    while (stmt) {
+        if (isa<If>(stmt) || isa<While>(stmt)) {
+            ensureLegality(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
+        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
+            assert (stmt->getNumOperands() <= 2);
+            if (LLVM_UNLIKELY(stmt->getNumOperands() < 2)) {
+                if (LLVM_UNLIKELY(stmt->getNumOperands() == 0)) {
+                    stmt = stmt->eraseFromParent(true);
+                } else {
+                    stmt = stmt->replaceWith(stmt->getOperand(0), true, true);
+                }
+                continue;
+            }
+        }
+        stmt = stmt->getNextNode();
+    }
 }
 
@@ -395 +1899 @@
 void FactorizeDFG::transform(PabloFunction & function) {
     FactorizeDFG ldfg;
+//    ldfg.deMorgansExpansion(function.getEntryBlock());
+//    #ifndef NDEBUG
+//    PabloVerifier::verify(function, "post-demorgans-expansion");
+//    #endif
     ldfg.enumerateScopeDepth(function);
-    ldfg.cse(function.getEntryBlock());
+    ldfg.factor(function);
     #ifndef NDEBUG
-    PabloVerifier::verify(function, "post-cse");
+    PabloVerifier::verify(function, "post-factoring");
     #endif
-    Simplifier::optimize(function);
-    ldfg.lower(function.getEntryBlock());
+    ldfg.lower(function);
     #ifndef NDEBUG
     PabloVerifier::verify(function, "post-lowering");
-    #endif    
-}
-
-}
+    #endif
+    ldfg.ensureLegality(function.getEntryBlock());
+}
+
+}

icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.h

@@ -3 +3 @@
 
 #include <boost/container/flat_map.hpp>
+#include <boost/circular_buffer.hpp>
 #include <vector>
+#include <set>
 
 namespace pablo {
@@ -17 +19 @@
     using ScopeDepth = boost::container::flat_map<const PabloBlock *, unsigned>;
     using ScopeSet = std::vector<PabloBlock *>;
-    using ASTVector = std::vector<PabloAST *>;
-    struct OrderingMap {
-        unsigned of(const PabloAST * const expr) const {
-            auto f = mMap.find(expr);
-            if (f == mMap.end()) {
-                return mParent ? mParent->of(expr) : 0;
-            }
-            return f->second;
-        }
-        inline void enumerate(const PabloAST * const expr) {
-            mMap.emplace(expr, ++mOrderingCount);
-        }
-        OrderingMap() :  mParent(nullptr), mOrderingCount(0) {}
-        OrderingMap(OrderingMap * const parent) :  mParent(parent), mOrderingCount(parent->mOrderingCount) {}
-        ~OrderingMap() { if (mParent) { mParent->mOrderingCount = mOrderingCount; } }
-    private:
-        OrderingMap * const mParent;
-        unsigned mOrderingCount;
-        boost::container::flat_map<const PabloAST *, unsigned> mMap;
-    };
+    using NodeSet = std::vector<PabloAST *>;
+    // using Variadics = std::vector<Variadic *>;
+    using Variadics = boost::circular_buffer<Variadic *>;
 
+    using VertexSet = std::vector<PabloAST *>;
+    using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
+    // using BicliqueSet = boost::container::flat_set<Biclique>;
+    using BicliqueSet = std::vector<Biclique>;
+    using CheckSet = boost::container::flat_set<PabloAST *>;
 public:
     static void transform(PabloFunction & function);
@@ -43 +33 @@
     void enumerateScopeDepth(const PabloFunction & function);
     void enumerateScopeDepth(const PabloBlock * const block, const unsigned depth);
-    void cse(PabloBlock * const block);
-    void cse(Variadic * const var);
-    PabloBlock * chooseInsertionScope(const ASTVector & users);
-    void findInsertionPoint(const ASTVector & operands, PabloBlock * const scope);
-    void lower(PabloFunction & function);
-//    void lower(PabloBlock * const block, OrderingMap & parent);
-//    PabloAST * lower(Variadic * const var, PabloBlock * block, OrderingMap & order);
-    void lower(PabloBlock * const block);
-    Statement * lower(Variadic * const var, PabloBlock * block);
-    FactorizeDFG() = default;
+    static void deMorgansExpansion(Not * const var, PabloBlock * const block);
+    static void deMorgansExpansion(PabloBlock * const block);
+    void factor(PabloFunction & function) const;
+    // static void factor(PabloBlock * const block, BicliqueSet & bicliques);
+    // static void enumerateBicliques(Variadic * const var, BicliqueSet & bicliques);
+    static BicliqueSet findAllFactoringsOf(Variadic * const var);
+    static void independentCliqueSets(BicliqueSet & bicliques);
+    void processBicliques(BicliqueSet & bicliques) const;
+    // void factor(PabloBlock * const block, BicliqueSet & vars) const;
+    void factor(PabloBlock * const block, Variadics & vars) const;
+    void factor(Variadic * const var, Variadics & Q) const;
+    PabloBlock * findInsertionScope(const NodeSet & users) const;
+    CheckSet makeCheckSet(PabloBlock * const scope, const NodeSet & values) const;
+    Statement * firstIn(PabloBlock * const scope, Statement * stmt, const NodeSet & operands) const;
+    Statement * lastIn(PabloBlock * const scope, Statement * stmt, const NodeSet & users) const;
+    PabloBlock * findInsertionPoint(const NodeSet & operands, const NodeSet & users) const;
+    void lower(PabloFunction & function) const;
+    void lower(PabloBlock * const block) const;
+    Statement * lower(Variadic * const var, PabloBlock * block) const;
+    unsigned scopeDepthOf(const PabloBlock * const block) const;
+    unsigned scopeDepthOf(const PabloAST * const expr) const;
+    static void ensureLegality(PabloBlock * const block);
+    FactorizeDFG() : mNumOfVariadics(0) {}
 private:
-    ScopeDepth  mScopeDepth;
+    unsigned        mNumOfVariadics;
+    ScopeDepth      mScopeDepth;
 };
 

icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp

@@ -18 +18 @@
  * @brief coalesce
  ** ------------------------------------------------------------------------------------------------------------- */
-inline void FlattenAssociativeDFG::coalesce(Variadic * const var) {
+inline Variadic * CoalesceDFG::coalesce(Variadic * const var) {
     const TypeId typeId = var->getClassTypeId();
     for (unsigned i = 0; i < var->getNumOperands(); ) {
@@ -36 +36 @@
         ++i;
     }
+    return var;
 }
 
@@ -41 +42 @@
  * @brief coalesce
  ** ------------------------------------------------------------------------------------------------------------- */
-void FlattenAssociativeDFG::coalesce(PabloBlock * const block, const bool traverse) {
+void CoalesceDFG::coalesce(PabloBlock * const block, const bool traverse) {
     Statement * stmt = block->front();
     while (stmt) {
@@ -49 +50 @@
         } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
             coalesce(cast<Variadic>(stmt));
-        } else if (isa<Not>(stmt)) {
+        }/* else if (isa<Not>(stmt)) {
             deMorgansExpansion(cast<Not>(stmt), block);
-        }
+        }*/
         stmt = next;
     }
@@ -62 +63 @@
  * thereby allowing the Simplifier to check for tautologies and contradictions.
  ** ------------------------------------------------------------------------------------------------------------- */
-inline void FlattenAssociativeDFG::deMorgansExpansion(Not * const var, PabloBlock * const block) {
+inline void CoalesceDFG::deMorgansExpansion(Not * const var, PabloBlock * const block) {
     PabloAST * const negatedVar = var->getOperand(0);
     if (isa<And>(negatedVar) || isa<Or>(negatedVar)) {
-        Variadic * src = cast<Variadic>(negatedVar);
-        const unsigned operands = src->getNumOperands();
-        Variadic * replacement = nullptr;
-        block->setInsertPoint(var->getPrevNode());
-        if (isa<And>(negatedVar)) {
-            replacement = block->createOr(operands);
-        } else {
-            replacement = block->createAnd(operands);
-        }
-        block->setInsertPoint(replacement->getPrevNode());
-        for (unsigned i = 0; i != operands; ++i) {
-            replacement->addOperand(block->createNot(src->getOperand(i)));
-        }
-        coalesce(replacement);
-        var->replaceWith(replacement, true, true);
+        const TypeId desiredTypeId = isa<And>(negatedVar) ? TypeId::Or : TypeId::And;
+        bool canApplyDeMorgans = true;
+        for (PabloAST * user : var->users()) {
+            if (desiredTypeId != user->getClassTypeId()) {
+                canApplyDeMorgans = false;
+                break;
+            }
+        }
+        if (canApplyDeMorgans) {
+            const unsigned operands = cast<Variadic>(negatedVar)->getNumOperands();
+            PabloAST * negations[operands];
+            block->setInsertPoint(var);
+            for (unsigned i = 0; i != operands; ++i) {
+                negations[i] = block->createNot(cast<Variadic>(negatedVar)->getOperand(i));
+            }
+            const unsigned users = var->getNumUses();
+            PabloAST * user[users];
+            std::copy(var->user_begin(), var->user_end(), user);
+            for (unsigned i = 0; i != users; ++i) {
+                cast<Variadic>(user[i])->deleteOperand(var);
+                for (unsigned j = 0; j != operands; ++j) {
+                    cast<Variadic>(user[i])->addOperand(negations[j]);
+                }
+            }
+            var->eraseFromParent(true);
+        }
     }
 }
@@ -86 +98 @@
  * @brief deMorgansReduction
  ** ------------------------------------------------------------------------------------------------------------- */
-inline void FlattenAssociativeDFG::deMorgansReduction(Variadic * const var, PabloBlock * const block) {
+inline void CoalesceDFG::deMorgansReduction(Variadic * const var, PabloBlock * const block) {
     unsigned negations = 0;
     for (unsigned i = 0; i < var->getNumOperands(); ++i) {
@@ -117 +129 @@
  * @brief deMorgansReduction
  ** ------------------------------------------------------------------------------------------------------------- */
-void FlattenAssociativeDFG::deMorgansReduction(PabloBlock * const block, const bool traverse) {
+void CoalesceDFG::deMorgansReduction(PabloBlock * const block, const bool traverse) {
     for (Statement * stmt : *block) {
         if (LLVM_UNLIKELY((isa<If>(stmt) || isa<While>(stmt)) && traverse)) {
@@ -134 +146 @@
     explicit VertexData(TypeId typeId) : typeId(typeId) { }
 };
-using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, Variadic *>;
-using Vertex = Graph::vertex_descriptor;
+using DependencyGraph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, Variadic *>;
+using Vertex = DependencyGraph::vertex_descriptor;
 using SourceMap = flat_map<Assign *, Vertex>;
 using SinkMap = flat_map<TypeId, Vertex>;
@@ -145 +157 @@
  * @brief addToVariadicGraph
  ** ------------------------------------------------------------------------------------------------------------- */
-static bool addToVariadicGraph(Assign * const def, Graph & G, SourceMap & A, SinkMap & B) {
+static bool addToVariadicGraph(Assign * const def, DependencyGraph & G, SourceMap & A, SinkMap & B) {
 
     if (LLVM_LIKELY(A.count(def) == 0)) {
@@ -191 +203 @@
  * bipartition A and their adjacencies to be in B.
   ** ------------------------------------------------------------------------------------------------------------- */
-static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
+static BicliqueSet enumerateBicliques(const DependencyGraph & G, const VertexSet & A) {
     using IntersectionSets = std::set<VertexSet>;
 
@@ -273 +285 @@
     auto first1 = A.begin(), last1 = A.end();
     auto first2 = B.begin(), last2 = B.end();
+    assert (std::is_sorted(first1, last1));
+    assert (std::is_sorted(first2, last2));
     while (first1 != last1 && first2 != last2) {
         if (*first1 < *first2) {
@@ -289 +303 @@
  ** ------------------------------------------------------------------------------------------------------------- */
 template <unsigned side>
-inline static BicliqueSet independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) {
+inline static BicliqueSet independentCliqueSets(BicliqueSet && bicliques, const unsigned minimum) {
     using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
 
-    const auto l = cliques.size();
+    const auto l = bicliques.size();
     IndependentSetGraph I(l);
 
-    // Initialize our weights
-    for (unsigned i = 0; i != l; ++i) {
-        I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
-    }
-
-    // Determine our constraints
-    for (unsigned i = 0; i != l; ++i) {
-        for (unsigned j = i + 1; j != l; ++j) {
-            if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
-                add_edge(i, j, I);
+    // Initialize our weights and determine the constraints
+    for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
+        I[std::distance(bicliques.begin(), i)] = std::pow(std::get<side>(*i).size(), 2);
+        for (auto j = i; ++j != bicliques.end(); ) {
+            if (intersects(i->second, j->second) && intersects(i->first, j->first)) {
+                add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
             }
         }
@@ -330 +340 @@
     // Sort the selected list and then remove the unselected cliques
     std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
-    auto end = cliques.end();
+    auto end = bicliques.end();
     for (const unsigned offset : selected) {
-        end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
-    }
-    cliques.erase(cliques.begin(), end);
-
-    return std::move(cliques);
+        end = bicliques.erase(bicliques.begin() + offset + 1, end) - 1;
+    }
+    bicliques.erase(bicliques.begin(), end);
+
+    return std::move(bicliques);
 }
 
@@ -342 +352 @@
  * @brief tryToPartiallyExtractVariadic
  ** ------------------------------------------------------------------------------------------------------------- */
-inline void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
-
+inline void CoalesceDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
     for (unsigned i = 0; i < var->getNumOperands(); ++i) {
         PabloAST * const op = var->getOperand(i);
         if (isa<Assign>(op)) {
-
-            // Have we found a variadic operation that can sunk into a nested scope?
+            // Look for two Assign statements in this variadic; we don't want to generate a dependency graph unless
+            // we expect some optimization can occur.
             for (unsigned j = i + 1; j != var->getNumOperands(); ++j) {
                 bool invalid = false;
                 if (LLVM_UNLIKELY(matches(op, var->getOperand(j)))) {
-                    Graph G;
+                    DependencyGraph G;
                     SourceMap A;
                     SinkMap B;
@@ -375 +384 @@
 
                         const auto S = independentCliqueSets<0>(std::move(enumerateBicliques(G, H)), 2);
-                        assert (S.size() > 0);
+                        if (LLVM_UNLIKELY(S.empty())) {
+                            break;
+                        }
                         for (const Biclique & C : S) {
                             const VertexSet & sources = std::get<0>(C);
@@ -405 +416 @@
                                     joiner->addOperand(def->getOperand(0));                                    
                                 }
-
-                                coalesce(joiner);
-                                Assign * const joined = block->createAssign("m", joiner);
-
+                                Assign * const joined = block->createAssign("m", coalesce(joiner));
                                 for (Assign * def : defs) {
                                     def->replaceWith(joined);
@@ -430 +438 @@
  * @brief tryToPartiallyExtractVariadic
  ** ------------------------------------------------------------------------------------------------------------- */
-void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(PabloBlock * const block) {
+void CoalesceDFG::tryToPartiallyExtractVariadic(PabloBlock * const block) {
     for (Statement * stmt = block->back(); stmt; stmt = stmt->getPrevNode()) {
         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
@@ -573 +581 @@
  * TODO: make this only iterate over the scope blocks and test the scope branch.
  ** ------------------------------------------------------------------------------------------------------------- */
-inline void FlattenAssociativeDFG::removeFalseScopeDependencies(PabloFunction & function) {
+inline void CoalesceDFG::removeFalseScopeDependencies(PabloFunction & function) {
     ScopeDependencyGraph G;
     {
@@ -586 +594 @@
  * @brief transform
  ** ------------------------------------------------------------------------------------------------------------- */
-void FlattenAssociativeDFG::transform(PabloFunction & function) {
-
-    FlattenAssociativeDFG::coalesce(function.getEntryBlock(), true);
+void CoalesceDFG::transform(PabloFunction & function) {
+
+    CoalesceDFG::coalesce(function.getEntryBlock(), true);
     #ifndef NDEBUG
     PabloVerifier::verify(function, "post-coalescence");
@@ -595 +603 @@
     Simplifier::optimize(function);
 
-    FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock(), true);
-    #ifndef NDEBUG
-    PabloVerifier::verify(function, "post-demorgans-reduction");
-    #endif
-
-    Simplifier::optimize(function);
-
-    FlattenAssociativeDFG::removeFalseScopeDependencies(function);
+//    CoalesceDFG::deMorgansReduction(function.getEntryBlock(), true);
+//    #ifndef NDEBUG
+//    PabloVerifier::verify(function, "post-demorgans-reduction");
+//    #endif
+
+//    Simplifier::optimize(function);
+
+    CoalesceDFG::removeFalseScopeDependencies(function);
     #ifndef NDEBUG
     PabloVerifier::verify(function, "post-remove-false-scope-dependencies");
     #endif
 
-    FlattenAssociativeDFG::tryToPartiallyExtractVariadic(function.getEntryBlock());
+    Simplifier::optimize(function);
+
+    CoalesceDFG::tryToPartiallyExtractVariadic(function.getEntryBlock());
     #ifndef NDEBUG
     PabloVerifier::verify(function, "post-partial-variadic-extraction");

icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.h

@@ -11 +11 @@
 class Assign;
 
-class FlattenAssociativeDFG {
+class CoalesceDFG {
     friend class DistributivePass;
     friend class FactorizeDFG;
@@ -18 +18 @@
 protected:
     static void coalesce(PabloBlock * const block, const bool traverse);
-    static void coalesce(Variadic * const var);
+    static Variadic *coalesce(Variadic * const var);
     static void deMorgansExpansion(Not * const var, PabloBlock * const block);
     static void deMorgansReduction(PabloBlock * const block, const bool traverse);
@@ -25 +25 @@
     static void tryToPartiallyExtractVariadic(Variadic * const var);
     static void removeFalseScopeDependencies(PabloFunction & function);
-    FlattenAssociativeDFG() = default;
+    CoalesceDFG() = default;
 };
 

icGREP/icgrep-devel/icgrep/pablo/printer_pablos.cpp

@@ -35 +35 @@
         out << "Next(" << next->getName() << ") = ";
         print(next->getExpr(), out);
-    } else if (const If * ifstmt = dyn_cast<const If>(stmt)) {
-        out << "if ";
-        print(ifstmt->getCondition(), out);
+    } else if (const If * ifNode = dyn_cast<const If>(stmt)) {
+        out << "If ";
+        print(ifNode->getCondition(), out);
         if (expandNested) {
             out << ":\n";
-            print(ifstmt->getBody(), out, true, indent + BlockIndenting);
+            print(ifNode->getBody(), out, true, indent + BlockIndenting);
             out.indent(indent);
-            out << "else:\n";
-            print_vars(ifstmt->getDefined(), out, indent + BlockIndenting);
+            out << "Else:\n";
+            print_vars(ifNode->getDefined(), out, indent + BlockIndenting);
         }
     } else if (const While * whileNode = dyn_cast<const While>(stmt)) {
-        out << "while ";
+        out << "While ";
         print(whileNode->getCondition(), out);
         if (expandNested) {

icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

@@ -39 +39 @@
 static cl::opt<bool> DisableLog2BoundedRepetition("disable-log2-bounded-repetition", cl::init(false),
                      cl::desc("disable log2 optimizations for bounded repetition of bytes"), cl::cat(fREcompilationOptions));
+static cl::opt<bool> DisableIfHierarchy("disable-if-hierarchy-strategy", cl::init(false),
+                     cl::desc("disable nested if hierarchy for generated Unicode classes (not recommended)"), cl::cat(fREcompilationOptions));
 static cl::opt<int> IfInsertionGap("if-insertion-gap", cl::init(3), cl::desc("minimum number of nonempty elements between inserted if short-circuit tests"), cl::cat(fREcompilationOptions));
 static cl::opt<bool> DisableMatchStar("disable-matchstar", cl::init(false),
@@ -303 +305 @@
     if (LLVM_LIKELY(nameMap.size() > 0)) {
         UCD::UCDCompiler ucdCompiler(mCCCompiler);
-        ucdCompiler.generateWithDefaultIfHierarchy(nameMap, mPB);
+        if (LLVM_UNLIKELY(DisableIfHierarchy)) {
+            ucdCompiler.generateWithoutIfHierarchy(nameMap, mPB);
+        } else {
+            ucdCompiler.generateWithDefaultIfHierarchy(nameMap, mPB);
+        }
         for (auto t : nameMap) {
             if (t.second) {

icGREP/icgrep-devel/icgrep/toolchain.cpp

@@ -22 +22 @@
 #include <llvm/Support/TargetSelect.h>
 #include <llvm/Support/Host.h>
+#include <llvm/Support/FileSystem.h>
+
 
 #include <IDISA/idisa_avx_builder.h>
@@ -53 +55 @@
 #include <pablo/printer_pablos.h>
 
-#include "do_grep.h"
+#include <hrtime.h>
+#include <do_grep.h>
 
 using namespace pablo;
@@ -65 +68 @@
 static cl::opt<bool> PrintUTF8REs("print-utf8-REs", cl::init(false), cl::desc("print out UTF-8 REs"), cl::cat(cRegexOutputOptions));
 static cl::opt<bool> PrintSimplifiedREs("print-simplified-REs", cl::init(false), cl::desc("print out final simplified REs"), cl::cat(cRegexOutputOptions));
-static cl::OptionCategory dPabloDumpOptions("Pablo Dump Options",
-                                            "These options control printing of intermediate Pablo code.");
+static cl::OptionCategory dPabloDumpOptions("Pablo Dump Options", "These options control printing of intermediate Pablo code.");
 
 static cl::opt<bool> PrintOptimizedREcode("print-pablo", cl::init(false), cl::desc("print final optimized Pablo code"), cl::cat(dPabloDumpOptions));
 static cl::opt<bool> PrintCompiledCCcode("print-CC-pablo", cl::init(false), cl::desc("print Pablo output from character class compiler"), cl::cat(dPabloDumpOptions));
 static cl::opt<bool> PrintCompiledREcode("print-RE-pablo", cl::init(false), cl::desc("print Pablo output from the regular expression compiler"), cl::cat(dPabloDumpOptions));
+static cl::opt<std::string> PabloOutputFilename("print-pablo-output", cl::init(""), cl::desc("output Pablo filename"), cl::cat(dPabloDumpOptions));
 
 static cl::OptionCategory cPabloOptimizationsOptions("Pablo Optimizations", "These options control Pablo optimization passes.");
 
-static cl::opt<bool> DisablePabloCSE("disable-CSE", cl::init(false),
-                                     cl::desc("Disable Pablo common subexpression elimination/dead code elimination"),
+static cl::opt<bool> DisableSimplification("disable-simplification", cl::init(false),
+                                     cl::desc("Disable Pablo Simplification pass (not recommended)"),
                                      cl::cat(cPabloOptimizationsOptions));
+
 static cl::opt<bool> PabloSinkingPass("sinking", cl::init(false),
                                       cl::desc("Moves all instructions into the innermost legal If-scope so that they are only executed when needed."),
                                       cl::cat(cPabloOptimizationsOptions));
 
+static cl::OptionCategory cMachineCodeOptimization("Machine Code Optimizations", "These options control back-end compilier optimization levels.");
+
+
+static cl::opt<char> OptLevel("O", cl::desc("Optimization level. [-O0, -O1, -O2, or -O3] (default = '-O0')"),
+                              cl::cat(cMachineCodeOptimization), cl::Prefix, cl::ZeroOrMore, cl::init('0'));
+
 #ifdef ENABLE_MULTIPLEXING
 static cl::opt<bool> PrintUnloweredCode("print-unlowered-pablo", cl::init(false), cl::desc("print Pablo output prior to lowering. "), cl::cat(dPabloDumpOptions));
@@ -91 +101 @@
                                         cl::desc("maximum size of any candidate multiplexing set."),
                                         cl::cat(cPabloOptimizationsOptions));
+
 static cl::opt<unsigned> MultiplexingSelectionLimit("multiplexing-selection-limit", cl::init(100),
                                         cl::desc("maximum number of selections from any partial candidate multiplexing set."),
                                         cl::cat(cPabloOptimizationsOptions));
+
 static cl::opt<unsigned> MultiplexingWindowSize("multiplexing-window-size", cl::init(1),
                                         cl::desc("maximum depth difference for computing mutual exclusion of Advance nodes."),
@@ -101 +113 @@
                                          cl::desc("coalesce associative functions prior to optimization passes."),
                                          cl::cat(cPabloOptimizationsOptions));
+
 static cl::opt<bool> EnablePreDistribution("pre-dist", cl::init(false),
-                                         cl::desc("apply distribution law optimization."),
+                                         cl::desc("apply distribution law optimization prior to multiplexing."),
                                          cl::cat(cPabloOptimizationsOptions));
+
 static cl::opt<bool> EnablePostDistribution("post-dist", cl::init(false),
-                                         cl::desc("apply distribution law optimization."),
+                                         cl::desc("apply distribution law optimization after multiplexing."),
+                                         cl::cat(cPabloOptimizationsOptions));
+
+static cl::opt<bool> EnablePrePassScheduling("pre-pass-scheduling", cl::init(false),
+                                         cl::desc("apply pre-pass scheduling prior to LLVM IR generation."),
                                          cl::cat(cPabloOptimizationsOptions));
 #endif
@@ -154 +172 @@
 }
 
-void pablo_function_passes(PabloFunction * function) {
+#ifdef PRINT_TIMING_INFORMATION
+#define READ_CYCLE_COUNTER(name) name = read_cycle_counter();
+#else
+#define READ_CYCLE_COUNTER(name)
+#endif
+
+#ifdef PRINT_TIMING_INFORMATION
+unsigned COUNT_STATEMENTS(const PabloFunction * const entry) {
+    std::stack<const Statement *> scope;
+    unsigned statements = 0;
+    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
+    for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
+        while ( stmt ) {
+            ++statements;
+            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
+                // Set the next statement to be the first statement of the inner scope and push the
+                // next statement of the current statement into the scope stack.
+                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
+                scope.push(stmt->getNextNode());
+                stmt = nested->front();
+                assert (stmt);
+                continue;
+            }
+            stmt = stmt->getNextNode();
+        }
+        if (scope.empty()) {
+            break;
+        }
+        stmt = scope.top();
+        scope.pop();
+    }
+    return statements;
+}
+
+unsigned COUNT_ADVANCES(const PabloFunction * const entry) {
+
+    std::stack<const Statement *> scope;
+    unsigned advances = 0;
+
+    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
+    for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
+        while ( stmt ) {
+            if (isa<Advance>(stmt)) {
+                ++advances;
+            }
+            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
+                // Set the next statement to be the first statement of the inner scope and push the
+                // next statement of the current statement into the scope stack.
+                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
+                scope.push(stmt->getNextNode());
+                stmt = nested->front();
+                assert (stmt);
+                continue;
+            }
+            stmt = stmt->getNextNode();
+        }
+        if (scope.empty()) {
+            break;
+        }
+        stmt = scope.top();
+        scope.pop();
+    }
+    return advances;
+}
+
+using DistributionMap = boost::container::flat_map<unsigned, unsigned>;
+
+DistributionMap SUMMARIZE_VARIADIC_DISTRIBUTION(const PabloFunction * const entry) {
+    std::stack<const Statement *> scope;
+    DistributionMap distribution;
+    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
+    for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
+        while ( stmt ) {
+            if (isa<Variadic>(stmt)) {
+                auto f = distribution.find(stmt->getNumOperands());
+                if (f == distribution.end()) {
+                    distribution.emplace(stmt->getNumOperands(), 1);
+                } else {
+                    f->second += 1;
+                }
+            }
+            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
+                // Set the next statement to be the first statement of the inner scope and push the
+                // next statement of the current statement into the scope stack.
+                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
+                scope.push(stmt->getNextNode());
+                stmt = nested->front();
+                assert (stmt);
+                continue;
+            }
+            stmt = stmt->getNextNode();
+        }
+        if (scope.empty()) {
+            break;
+        }
+        stmt = scope.top();
+        scope.pop();
+    }
+    return distribution;
+}
+#endif
+
+void pablo_function_passes(PabloFunction * function) {   
     // Scan through the pablo code and perform DCE and CSE
-    if (!DisablePabloCSE) {
+
+#ifdef PRINT_TIMING_INFORMATION
+    timestamp_t simplification_start = 0, simplification_end = 0;
+    timestamp_t coalescing_start = 0, coalescing_end = 0;
+    timestamp_t sinking_start = 0, sinking_end = 0;
+    timestamp_t pre_distribution_start = 0, pre_distribution_end = 0;
+    timestamp_t multiplexing_start = 0, multiplexing_end = 0;
+    timestamp_t post_distribution_start = 0, post_distribution_end = 0;
+    timestamp_t lowering_start = 0, lowering_end = 0;
+    timestamp_t scheduling_start = 0, scheduling_end = 0;
+    DistributionMap distribution;
+    const timestamp_t optimization_start = read_cycle_counter();
+#endif
+    if (!DisableSimplification) {
+        READ_CYCLE_COUNTER(simplification_start);
         Simplifier::optimize(*function);
+        READ_CYCLE_COUNTER(simplification_end);
     }
 #ifdef ENABLE_MULTIPLEXING
-    if (EnableLowering || EnablePreDistribution || EnablePostDistribution || EnableMultiplexing) {
-        FlattenAssociativeDFG::transform(*function);
+    if (EnableLowering || EnablePreDistribution || EnablePostDistribution) {
+        READ_CYCLE_COUNTER(coalescing_start);
+        CoalesceDFG::transform(*function);
+        READ_CYCLE_COUNTER(coalescing_end);
+    }
+    if (EnablePreDistribution) {
+        READ_CYCLE_COUNTER(pre_distribution_start);
+        DistributivePass::optimize(*function);
+        READ_CYCLE_COUNTER(pre_distribution_end);
+    }
+    if (EnableMultiplexing) {
+        READ_CYCLE_COUNTER(multiplexing_start);
+        MultiplexingPass::optimize(*function, MultiplexingSetLimit, MultiplexingSelectionLimit, MultiplexingWindowSize);
+        READ_CYCLE_COUNTER(multiplexing_end);
+        if (EnableLowering || EnablePreDistribution || EnablePostDistribution) {
+            CoalesceDFG::transform(*function);
+        }
+    }
+    if (EnablePostDistribution) {
+        READ_CYCLE_COUNTER(post_distribution_start);
+        DistributivePass::optimize(*function);
+        READ_CYCLE_COUNTER(post_distribution_end);
     }
 #endif
     if (PabloSinkingPass) {
+        READ_CYCLE_COUNTER(sinking_start);
         CodeMotionPass::optimize(*function);
-    }
-#ifdef ENABLE_MULTIPLEXING    
-    if (EnablePreDistribution) {
-        DistributivePass::optimize(*function);
-    }
-    if (EnableMultiplexing) {
-        MultiplexingPass::optimize(*function, MultiplexingSetLimit, MultiplexingSelectionLimit, MultiplexingWindowSize);
-    }
-    if (EnablePostDistribution) {
-        DistributivePass::optimize(*function);
-    }
-    SchedulingPrePass::optimize(*function);
+        READ_CYCLE_COUNTER(sinking_end);
+    }
+#ifdef ENABLE_MULTIPLEXING
     if (PrintUnloweredCode) {
         //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
@@ -183 +330 @@
         cerr << "Unlowered Pablo AST:\n";
         PabloPrinter::print(*function, cerr);
-    }
-    if (EnableLowering || EnablePreDistribution || EnablePostDistribution || EnableMultiplexing) {
+    }    
+    #ifdef PRINT_TIMING_INFORMATION
+    distribution = SUMMARIZE_VARIADIC_DISTRIBUTION(function);
+    #endif
+    if (EnableLowering || EnablePreDistribution || EnablePostDistribution) {
+        READ_CYCLE_COUNTER(lowering_start);
         FactorizeDFG::transform(*function);
-    }
+        READ_CYCLE_COUNTER(lowering_end);
+    }
+    if (EnablePrePassScheduling) {
+        READ_CYCLE_COUNTER(scheduling_start);
+        SchedulingPrePass::optimize(*function);
+        READ_CYCLE_COUNTER(scheduling_end);
+    }
+#endif
+#ifdef PRINT_TIMING_INFORMATION
+    const timestamp_t optimization_end = read_cycle_counter();
 #endif
     if (PrintOptimizedREcode) {
-        PabloVerifier::verify(*function, "post-optimization");
-        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
-        llvm::raw_os_ostream cerr(std::cerr);
-        cerr << "Final Pablo AST:\n";
-        PabloPrinter::print(*function, cerr);
-    }
+        if (PabloOutputFilename.empty()) {
+            //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
+            llvm::raw_os_ostream cerr(std::cerr);
+            cerr << "Final Pablo AST:\n";
+            PabloPrinter::print(*function, cerr);
+        } else {
+            std::error_code error;
+            llvm::raw_fd_ostream out(PabloOutputFilename, error, sys::fs::OpenFlags::F_None);
+            PabloPrinter::print(*function, out);
+        }
+    }
+#ifdef PRINT_TIMING_INFORMATION
+    std::cerr << "PABLO OPTIMIZATION TIME: " << (optimization_end - optimization_start) << std::endl;
+    std::cerr << "  SIMPLIFICATION TIME: " << (simplification_end - simplification_start) << std::endl;
+    std::cerr << "  COALESCING TIME: " << (coalescing_end - coalescing_start) << std::endl;
+    std::cerr << "  SINKING TIME: " << (sinking_end - sinking_start) << std::endl;
+    std::cerr << "  PRE-DISTRIBUTION TIME: " << (pre_distribution_end - pre_distribution_start) << std::endl;
+    std::cerr << "  MULTIPLEXING TIME: " << (multiplexing_end - multiplexing_start) << std::endl;
+    std::cerr << "  MULTIPLEXING SEED: " << MultiplexingPass::SEED << std::endl;
+    std::cerr << "  MULTIPLEXING NODES USED: " << MultiplexingPass::NODES_USED << std::endl;
+    std::cerr << "  MULTIPLEXING NODES ALLOCATED: " << MultiplexingPass::NODES_ALLOCATED << std::endl;
+    std::cerr << "  LOWERING TIME: " << (lowering_end - lowering_start) << std::endl;
+    std::cerr << "  POST-DISTRIBUTION TIME: " << (post_distribution_end - post_distribution_start) << std::endl;
+    std::cerr << "  SCHEDULING TIME: " << (scheduling_end - scheduling_start) << std::endl;
+    std::cerr << "PABLO STATEMENTS: " << COUNT_STATEMENTS(function) << std::endl;
+    std::cerr << "PABLO ADVANCES: " << COUNT_ADVANCES(function) << std::endl;
+    std::cerr << "PRE-LOWERING VARIADIC DISTRIBUTION: ";
+    bool join = false;
+    for (auto dist : distribution) {
+        if (join) {
+            std::cerr << ';';
+        }
+        std::cerr << dist.first << '|' << dist.second;
+        join = true;
+    }
+    std::cerr << std::endl;
+#endif
 }
 
@@ -232 +423 @@
     builder.setErrorStr(&errMessage);
     builder.setMCPU(sys::getHostCPUName());
-    builder.setOptLevel(CodeGenOpt::Level::None);
+    CodeGenOpt::Level optLevel = CodeGenOpt::Level::None;
+    switch (OptLevel) {
+        case '0': optLevel = CodeGenOpt::None; break;
+        case '1': optLevel = CodeGenOpt::Less; break;
+        case '2': optLevel = CodeGenOpt::Default; break;
+        case '3': optLevel = CodeGenOpt::Aggressive; break;
+        default: errs() << OptLevel << " is an invalid optimization level.\n";
+    }
+    builder.setOptLevel(optLevel);
 
 #if (BLOCK_SIZE == 256)