Changeset 5510


Ignore:
Timestamp:
Jun 15, 2017, 12:39:20 PM (2 years ago)
Author:
nmedfort
Message:

Back up check-in. Should have no effect on current programs.

Location:
icGREP/icgrep-devel/icgrep
Files:
2 added
12 edited

Legend:

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

    r5496 r5510  
    1010option(ENABLE_MULTIPLEXING "Compiling the Multiplexing Module")
    1111option(DISABLE_DUAL_ABI "Disable GCC Dual ABI support" OFF)
     12option(CARRYPACK_MANAGER "Use CarryPack Manager to reduce space required for carries. For testing only." OFF)
    1213find_package(LLVM REQUIRED CONFIG)
    1314
     
    5859SET(OBJECT_CACHE_SRC toolchain/object_cache.cpp)
    5960
    60 SET(TOOLCHAIN_SRC toolchain/toolchain.cpp toolchain/pipeline.cpp toolchain/driver.cpp)
    61 
    62 SET(DRIVER_SRC toolchain/cpudriver.cpp toolchain/NVPTXDriver.cpp)
     61SET(TOOLCHAIN_SRC toolchain/toolchain.cpp toolchain/pipeline.cpp)
     62
     63SET(DRIVER_SRC toolchain/driver.cpp toolchain/cpudriver.cpp toolchain/NVPTXDriver.cpp)
    6364
    6465SET(KERNEL_SRC kernels/kernel.cpp kernels/streamset.cpp kernels/interface.cpp kernels/kernel_builder.cpp)
    6566SET(KERNEL_SRC ${KERNEL_SRC} kernels/source_kernel.cpp kernels/s2p_kernel.cpp kernels/deletion.cpp kernels/swizzle.cpp kernels/p2s_kernel.cpp kernels/stdout_kernel.cpp)
    6667
    67 SET(IDISA_SRC IR_Gen/CBuilder.cpp IR_Gen/idisa_builder.cpp IR_Gen/idisa_avx_builder.cpp IR_Gen/idisa_i64_builder.cpp IR_Gen/idisa_sse_builder.cpp IR_Gen/idisa_nvptx_builder.cpp IR_Gen/idisa_target.cpp)
     68SET(IDISA_SRC IR_Gen/CBuilder.cpp IR_Gen/idisa_builder.cpp IR_Gen/idisa_avx_builder.cpp IR_Gen/idisa_i64_builder.cpp IR_Gen/idisa_sse_builder.cpp IR_Gen/idisa_nvptx_builder.cpp)
     69SET(IDISA_SRC ${IDISA_SRC} IR_Gen/idisa_target.cpp)
    6870
    6971SET(PABLO_SRC pablo/pabloAST.cpp pablo/branch.cpp pablo/codegenstate.cpp pablo/builder.cpp pablo/symbol_generator.cpp pablo/printer_pablos.cpp pablo/pablo_toolchain.cpp)
    70 SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_kernel.cpp pablo/pablo_compiler.cpp pablo/carry_manager.cpp)
     72SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_kernel.cpp pablo/pablo_compiler.cpp)
     73IF (CARRYPACK_MANAGER)
     74SET(PABLO_SRC ${PABLO_SRC} pablo/carrypack_manager.cpp)
     75ELSE()
     76SET(PABLO_SRC ${PABLO_SRC} pablo/carry_manager.cpp)
     77ENDIF()
    7178SET(PABLO_SRC ${PABLO_SRC} pablo/analysis/pabloverifier.cpp)
    7279SET(PABLO_SRC ${PABLO_SRC} pablo/passes/ssapass.cpp)
    73 SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/codemotionpass.cpp pablo/optimizers/distributivepass.cpp pablo/passes/flattenif.cpp)
     80SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/codemotionpass.cpp pablo/optimizers/distributivepass.cpp pablo/optimizers/schedulingprepass.cpp)
     81SET(PABLO_SRC ${PABLO_SRC} pablo/passes/flattenif.cpp)
    7482IF(ENABLE_MULTIPLEXING)
    75 SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/booleanreassociationpass.cpp)
    76 SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/schedulingprepass.cpp pablo/optimizers/pablo_automultiplexing.cpp)
     83SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_automultiplexing.cpp)
    7784ENDIF()
    7885
     
    180187ENDIF()
    181188
     189IF (CARRYPACK_MANAGER)
     190SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DUSE_CARRYPACK_MANAGER")
     191ENDIF()
     192
    182193SET(CMAKE_REQUIRED_FLAGS)
    183194
  • icGREP/icgrep-devel/icgrep/IR_Gen/CBuilder.h

    r5493 r5510  
    180180    void CreateAssert(llvm::Value * assertion, llvm::StringRef failureMessage) {
    181181        if (LLVM_UNLIKELY(assertion->getType()->isVectorTy())) {
    182             assertion = CreateBitCast(assertion, llvm::IntegerType::get(getContext(), assertion->getType()->getPrimitiveSizeInBits()));
     182            assertion = CreateBitCast(assertion, getIntNTy(assertion->getType()->getPrimitiveSizeInBits()));
    183183        }
    184         return __CreateAssert(CreateICmpNE(assertion, llvm::Constant::getNullValue(assertion->getType())), failureMessage);
     184        return __CreateAssert(CreateIsNotNull(assertion), failureMessage);
    185185    }
    186186
    187187    void CreateAssertZero(llvm::Value * assertion, llvm::StringRef failureMessage) {
    188188        if (LLVM_UNLIKELY(assertion->getType()->isVectorTy())) {
    189             assertion = CreateBitCast(assertion, llvm::IntegerType::get(getContext(), assertion->getType()->getPrimitiveSizeInBits()));
     189            assertion = CreateBitCast(assertion, getIntNTy(assertion->getType()->getPrimitiveSizeInBits()));
    190190        }
    191         return __CreateAssert(CreateICmpEQ(assertion, llvm::Constant::getNullValue(assertion->getType())), failureMessage);
     191        return __CreateAssert(CreateIsNull(assertion), failureMessage);
    192192    }
    193193
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r5486 r5510  
    260260wc.cpp
    261261CMakeLists.txt
     262pablo/carrypack_manager.cpp
     263pablo/carrypack_manager.h
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r5493 r5510  
    891891    #ifdef NDEBUG
    892892    report_fatal_error("DistributivePass is unsupported");
    893     #endif
     893    #else
    894894    PassContainer C;
    895895    C.run(kernel);
    896896    return true;
     897    #endif
    897898}
    898899
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/schedulingprepass.cpp

    r5267 r5510  
    11#include "schedulingprepass.h"
     2
     3#include <pablo/pablo_kernel.h>
    24#include <pablo/codegenstate.h>
    3 #include <boost/circular_buffer.hpp>
    4 #include <boost/container/flat_set.hpp>
    5 #include <boost/container/flat_map.hpp>
     5#include <pablo/ps_assign.h>
     6#include <pablo/pe_var.h>
     7#include <pablo/branch.h>
    68#ifndef NDEBUG
    79#include <pablo/analysis/pabloverifier.hpp>
    810#endif
     11#include <boost/container/flat_set.hpp>
    912#include <boost/graph/adjacency_list.hpp>
    10 #include <unordered_map>
    11 
    12 #include <pablo/printer_pablos.h>
    13 #include <iostream>
    14 
     13#include <random>
     14
     15
     16#include <llvm/Support/raw_ostream.h>
     17
     18
     19
     20
     21using namespace llvm;
    1522using namespace boost;
    1623using namespace boost::container;
     
    1825namespace pablo {
    1926
    20 using DependencyGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, std::vector<PabloAST *>>;
    21 using Vertex = DependencyGraph::vertex_descriptor;
     27using IndexPair = std::pair<unsigned, Statement *>;
     28using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
     29using Vertex = Graph::vertex_descriptor;
    2230using Map = std::unordered_map<const PabloAST *, Vertex>;
    23 using ReadyPair = std::pair<unsigned, Vertex>;
    24 using ReadySet = std::vector<ReadyPair>;
    25 
    26 using weight_t = unsigned;
    27 using TypeId = PabloAST::ClassTypeId;
    28 using LiveSet = flat_set<Vertex>;
    29 
    30 void schedule(PabloBlock * const block);
    31 
    32 /** ------------------------------------------------------------------------------------------------------------- *
    33  * @brief printGraph
    34  ** ------------------------------------------------------------------------------------------------------------- */
    35 template <typename DependencyGraph>
    36 static void printGraph(const DependencyGraph & G, const std::vector<unsigned> & ordering, const std::string name, raw_ostream & out) {
    37     out << "*******************************************\n";
    38     out << "digraph " << name << " {\n";
    39     for (auto u : make_iterator_range(vertices(G))) {
    40         if (G[u].empty()) {
    41             continue;
    42         }
    43         out << "v" << u << " [label=\"" << ordering[u] << " : ";
    44         bool newLine = false;
    45         for (PabloAST * expr : G[u]) {
    46             if (newLine) {
    47                 out << '\n';
    48             }
    49             newLine = true;
    50             if (isa<Statement>(expr)) {
    51                 PabloPrinter::print(cast<Statement>(expr), out);
     31using ReadyPair = std::pair<Vertex, size_t>;
     32
     33struct SchedulingPrePassContainer {
     34
     35    void run(PabloBlock * const block) {
     36        // traverse to the inner-most branch first
     37        for (Statement * stmt : *block) {
     38            if (isa<Branch>(stmt)) {
     39                run(cast<Branch>(stmt)->getBody());
     40            }
     41        }
     42        // starting with the inner-most scope(s) first, attempt to schedule the statements to
     43        // minimize the number of simulaneously live variables.
     44        schedule(block);
     45    }
     46
     47protected:
     48
     49    /** ------------------------------------------------------------------------------------------------------------- *
     50     * @brief schedule
     51     ** ------------------------------------------------------------------------------------------------------------- */
     52    void schedule(PabloBlock * const block) {
     53        build_data_dependency_dag(block);
     54        initialize_process();
     55        initialize_probabilities();
     56
     57        unsigned count = 0;
     58        std::vector<size_t> W;
     59        W.reserve(num_vertices(G));
     60        for (;;) {
     61            ready_sort();
     62            const auto u = choose_ready(++count);
     63            queue_to_ready(u);
     64            if (LLVM_UNLIKELY(R.empty())) {
     65                break;
     66            }
     67            update_liveness(u);
     68            W.push_back(get_live_weight());
     69        }
     70
     71        const auto m = W.size() / 2;
     72        std::nth_element(W.begin(), W.begin() + m, W.end());
     73
     74        errs() << "median_live_weight: " << W[m] << "\n";
     75
     76
     77
     78//        std::sort(I.begin(), I.end(), [](const IndexPair & A, const IndexPair & B){
     79//            return std::get<0>(A) < std::get<0>(B);
     80//        });
     81
     82//        block->setInsertPoint(nullptr);
     83//        for (const auto & p : I) {
     84//            Statement * stmt = std::get<1>(p);
     85//            assert (std::get<0>(p) > 0);
     86//            assert (stmt->getParent() == block);
     87//            block->insert(stmt);
     88//        }
     89//        assert (block->getInsertPoint() == block->back());
     90
     91        I.clear();
     92        G.clear();
     93        L.clear();
     94    }
     95
     96    void build_data_dependency_dag(PabloBlock * const block) {
     97        assert (M.empty());
     98        for (Statement * stmt : *block) {
     99            const auto u = find(stmt);
     100            if (isa<Assign>(stmt)) {
     101                addDominatedUsers(u, cast<Assign>(stmt), block);
     102            } else if (isa<Branch>(stmt)) {
     103                addEscapedUsers(u, cast<Branch>(stmt), block);
    52104            } else {
    53                 PabloPrinter::print(expr, out);
    54             }
    55         }
    56         out << "\"];\n";
    57     }
    58     for (auto e : make_iterator_range(edges(G))) {
    59         out << "v" << source(e, G) << " -> v" << target(e, G);
    60         out << ";\n";
    61     }
    62 
    63     out << "}\n\n";
    64     out.flush();
    65 }
    66 
    67 /** ------------------------------------------------------------------------------------------------------------- *
    68  * @brief resolveNestedUsages
    69  ** ------------------------------------------------------------------------------------------------------------- */
    70 static void resolveNestedUsages(Statement * const root, PabloAST * const expr, DependencyGraph & G, Map & M, PabloBlock * const block) {
    71     for (PabloAST * use : expr->users()) {
    72         if (LLVM_LIKELY(isa<Statement>(use))) {
    73             const PabloBlock * scope = cast<Statement>(use)->getParent();
    74             if (scope != block) {
    75                 for (PabloBlock * prior = scope->getPredecessor(); prior; scope = prior, prior = prior->getPredecessor()) {
    76                     if (prior == block) {
    77                         assert (scope->getBranch());
    78                         auto v = M.find(scope->getBranch());
    79                         assert (v != M.end());
    80                         auto u = M.find(root);
    81                         assert (u != M.end());
    82                         if (u->second != v->second) {
    83                             add_edge(u->second, v->second, G);
    84                         }
    85                         break;
    86                     }
    87                 }
    88             }
    89         }
    90     }
    91 }
    92 
    93 /** ------------------------------------------------------------------------------------------------------------- *
    94  * @brief resolveNestedUsages
    95  ** ------------------------------------------------------------------------------------------------------------- */
    96 static void computeDependencyGraph(DependencyGraph & G, PabloBlock * const block) {
    97     Map M;
    98     // Construct a use-def graph G representing the current scope block
    99     for (Statement * stmt : *block) {
    100         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    101             schedule(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    102         }
    103         const auto u = add_vertex({stmt}, G);
    104         M.insert(std::make_pair(stmt, u));
    105         for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    106             const PabloAST * const op = stmt->getOperand(i);
    107             if (LLVM_LIKELY(isa<Statement>(op))) {
    108                 const PabloBlock * scope = cast<Statement>(op)->getParent();
    109                 // Was this instruction computed by this block?
    110                 if (scope == block) {
    111                     auto v = M.find(op);
    112                     assert (v != M.end());
    113                     assert (v->second != u);
    114                     add_edge(v->second, u, G);
    115                 } else if (isa<Assign>(op)) {
    116                     // if this statement isn't an Assign or Next node, it cannot come from a nested scope
    117                     // unless the function is invalid.
    118                     for (PabloBlock * prior = scope->getPredecessor(); prior; scope = prior, prior = prior->getPredecessor()) {
    119                         // Was this instruction computed by a nested block?
    120                         if (prior == block) {
    121                             assert (scope->getBranch());
    122                             auto v = M.find(scope->getBranch());
    123                             assert (v != M.end());
    124                             if (v->second != u) {
    125                                 add_edge(v->second, u, G);
     105                addUsers(u, stmt, block);
     106            }
     107        }
     108        M.clear();
     109    }
     110
     111    void addUsers(const Vertex u, Statement * const stmt, PabloBlock * const block) {
     112        for (PabloAST * use : stmt->users()) {
     113            if (LLVM_LIKELY(isa<Statement>(use))) {
     114                Statement * user = cast<Statement>(use);
     115                while (user->getParent() != block) {
     116                    PabloBlock * const parent = user->getParent();
     117                    assert (parent);
     118                    user = parent->getBranch();
     119                    assert (user);
     120                }
     121                assert (strictly_dominates(stmt, user));
     122                add_edge(u, find(user), G);
     123            }
     124        }
     125    }
     126
     127    void addEscapedUsers(const Vertex u, Branch * const br, PabloBlock * const block) {
     128        for (Var * var : br->getEscaped()) {
     129            for (PabloAST * use : var->users()) {
     130                if (LLVM_LIKELY(isa<Statement>(use))) {
     131                    Statement * user = cast<Statement>(use);
     132                    for (;;) {
     133                        if (user->getParent() == block) {
     134                            if (LLVM_LIKELY(isa<Assign>(user) ? dominates(br, user) : (br != user))) {
     135                                add_edge(u, find(user), G);
    126136                            }
    127137                            break;
    128138                        }
    129                     }
    130                 }
    131             }
    132         }
    133     }
    134     // Do a second pass to ensure that we've accounted for any nested usage of an If or While statement
    135     for (Statement * stmt : *block) {
    136         if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
    137             for (Var * var : cast<Branch>(stmt)->getEscaped()) {
    138                 resolveNestedUsages(stmt, var, G, M, block);
    139             }
    140         } else {
    141             resolveNestedUsages(stmt, stmt, G, M, block);
    142         }
    143     }
    144     // Contract the graph
    145     for (;;) {
    146         bool done = true;
    147         for (const Vertex u : make_iterator_range(vertices(G))) {
    148             if (out_degree(u, G) == 1) {
    149                 const Vertex v = target(*(out_edges(u, G).first), G);
    150                 G[v].insert(G[v].begin(), G[u].begin(), G[u].end());
    151                 for (auto e : make_iterator_range(in_edges(u, G))) {
    152                     add_edge(source(e, G), v, G);
    153                 }
    154                 G[u].clear();
    155                 clear_vertex(u, G);
    156                 done = false;
    157             }
    158         }
    159         if (done) {
    160             break;
    161         }
    162     }
    163 
    164 
    165 }
    166 
    167 /** ------------------------------------------------------------------------------------------------------------- *
    168  * @brief computeGraphOrdering
    169  ** ------------------------------------------------------------------------------------------------------------- */
    170 std::vector<weight_t> computeGraphOrdering(const DependencyGraph & G) {
    171     // Determine the bottom-up ordering of G
    172     std::vector<weight_t> ordering(num_vertices(G));
    173     circular_buffer<Vertex> Q(num_vertices(G));
    174     for (const Vertex u : make_iterator_range(vertices(G))) {
    175         if (out_degree(u, G) == 0 && G[u].size() > 0) {
    176             ordering[u] = 1;
    177             Q.push_back(u);
    178         }
    179     }
    180     while (!Q.empty()) {
    181         const Vertex u = Q.front();
    182         Q.pop_front();
    183         assert (ordering[u] > 0);
    184         for (const auto ei : make_iterator_range(in_edges(u, G))) {
    185             const Vertex v = source(ei, G);
    186             if (ordering[v] == 0) {
    187                 weight_t weight = 0;
    188                 bool ready = true;
    189                 for (const auto ej : make_iterator_range(out_edges(v, G))) {
    190                     const Vertex w = target(ej, G);
    191                     const weight_t t = ordering[w];
    192                     if (t == 0) {
    193                         ready = false;
     139                        PabloBlock * const parent = user->getParent();
     140                        assert (parent);
     141                        user = parent->getBranch();
     142                        if (LLVM_UNLIKELY(user == nullptr)) {
     143                            break;
     144                        }
     145                    }
     146                }
     147            }
     148        }
     149    }
     150
     151    void addDominatedUsers(const Vertex u, Assign * const assignment, PabloBlock * const block) {
     152        for (PabloAST * use : assignment->getVariable()->users()) {
     153            if (LLVM_LIKELY(isa<Statement>(use))) {
     154                Statement * user = cast<Statement>(use);
     155                for (;;) {
     156                    if (user->getParent() == block) {
     157                        if (user != assignment) {
     158                            const auto v = find(user);
     159                            if (strictly_dominates(assignment, user)) {
     160                                add_edge(u, v, G);
     161                            } else {
     162                                assert (strictly_dominates(user, assignment));
     163                                // although there is not actually a dependency here, a prior value
     164                                // must be read by statement v prior to assignment u
     165                                add_edge(v, u, G);
     166                            }
     167                        }
    194168                        break;
    195169                    }
    196                     weight = std::max(weight, t);
    197                 }
    198                 if (ready) {
    199                     assert (weight < std::numeric_limits<unsigned>::max());
    200                     assert (weight > 0);
    201                     ordering[v] = weight + 1;
    202                     Q.push_back(v);
    203                 }
    204             }
    205         }
    206     }
    207     return ordering;
    208 }
    209 
    210 /** ------------------------------------------------------------------------------------------------------------- *
    211  * @brief schedule
    212  ** ------------------------------------------------------------------------------------------------------------- */
    213 void schedule(PabloBlock * const block) {
    214     DependencyGraph G;
    215     computeDependencyGraph(G, block);
    216     std::vector<weight_t> ordering = computeGraphOrdering(G);
    217 
    218 //    raw_os_ostream out(std::cerr);
    219 //    printGraph(G, ordering, "G", out);
    220 
    221     // Compute the initial ready set
    222     ReadySet readySet;
    223     for (const Vertex u : make_iterator_range(vertices(G))) {
    224         if (in_degree(u, G) == 0 && G[u].size() > 0) {
    225             readySet.emplace_back(ordering[u], u);
    226         }
    227     }
    228 
    229     struct {
    230         bool operator()(const ReadyPair a, const ReadyPair b) {
    231             return std::get<0>(a) > std::get<0>(b);
    232         }
    233     } readyComparator;
    234 
    235     std::sort(readySet.begin(), readySet.end(), readyComparator);
    236 
    237     block->setInsertPoint(nullptr);
    238 
    239     // Rewrite the AST
    240     while (!readySet.empty()) {
    241         DependencyGraph::degree_size_type killed = 0;
    242         auto chosen = readySet.begin();
    243         for (auto ri = readySet.begin(); ri != readySet.end(); ++ri) {
    244             DependencyGraph::degree_size_type kills = 0;
    245             for (auto e : make_iterator_range(in_edges(ri->first, G))) {
    246                 if (out_degree(source(e, G), G) == 1) {
    247                     ++kills;
    248                 }
    249             }
    250             if (kills > killed) {
    251                 chosen = ri;
    252                 killed = kills;
    253             }
    254         }
    255 
    256         Vertex u; unsigned weight;
    257         std::tie(weight, u) = *chosen;
    258         readySet.erase(chosen);
    259         clear_in_edges(u, G);
    260 
    261         assert ("Error: SchedulingPrePass is attempting to reschedule a statement!" && (weight > 0));
    262 
    263         // insert the statement then mark it as written ...
    264         for (PabloAST * expr : G[u]) {
    265             block->insert(cast<Statement>(expr));
    266         }
    267 
    268         ordering[u] = 0;
    269         // Now check whether any new instructions are ready
     170                    PabloBlock * const parent = user->getParent();
     171                    assert (parent);
     172                    user = parent->getBranch();
     173                    if (LLVM_UNLIKELY(user == nullptr)) {
     174                        break;
     175                    }
     176                }
     177            }
     178        }
     179    }
     180
     181    void printGraph(const std::string name, raw_ostream & out) {
     182        out << "\ndigraph " << name << " {\n";
     183        for (auto u : make_iterator_range(vertices(G))) {
     184            out << "v" << u << " [label=\"" << u << " : ";
     185            std::get<1>(I[u])->print(out);
     186            out << "  " << std::get<0>(I[u]) << "\"];\n";
     187        }
     188        for (auto e : make_iterator_range(edges(G))) {
     189            out << "v" << source(e, G) << " -> v" << target(e, G) << ";\n";
     190        }
     191        out << "}\n\n";
     192        out.flush();
     193    }
     194
     195    void initialize_process() {
     196        assert ("Ready set was not cleared prior to initializing!" && R.empty());
     197        std::vector<Vertex> Q;
     198        Q.reserve(64);
     199        for (auto u : make_iterator_range(vertices(G))) {
     200            if (out_degree(u, G) == 0) {
     201                Q.push_back(u);
     202            } else if (in_degree(u, G) == 0) {
     203                R.push_back(u);
     204            }
     205        }
     206
     207        // perform a transitive reduction of G to remove the unnecessary dependency analysis work
     208        // within the genetic algorithm search process
     209
     210        const auto n = num_vertices(G);
     211
     212        std::vector<flat_set<Vertex>> reachability(n);
     213        flat_set<Vertex> pending;
     214
     215        for (;;) {
     216            const auto u = Q.back();
     217            Q.pop_back();
     218
     219            flat_set<Vertex> & D = reachability[u];
     220
     221            assert (D.empty());
     222
     223            // initially we do not immediately consider any adjacent vertices reachable
     224            for (auto e : make_iterator_range(out_edges(u, G))) {
     225                const auto v = target(e, G);
     226                const auto & R = reachability[v];
     227                assert (R.count(v) == 0);
     228                D.insert(R.begin(), R.end());
     229            }
     230
     231            // so that if one of our outgoing targets is already reachable, we can remove it.
     232            remove_out_edge_if(u, [&D, this](Graph::edge_descriptor e) {
     233
     234                // TODO: if we remove this edge, add the liveness weight of statement u to the
     235                // target since the "liveness" of u is transitively implied.
     236
     237                return D.count(target(e, G)) != 0;
     238            }, G);
     239
     240            // afterwards we insert any remaining outgoing targets to finalize our reachable set
     241            for (auto e : make_iterator_range(out_edges(u, G))) {
     242                D.insert(target(e, G));
     243            }
     244
     245            // add any incoming source to our pending set
     246            for (auto e : make_iterator_range(in_edges(u, G))) {
     247                pending.insert(source(e, G));
     248            }
     249
     250            // so that when we exhaust the queue, we can repopulate it with the next 'layer' of the graph
     251            if (LLVM_UNLIKELY(Q.empty())) {
     252                if (LLVM_UNLIKELY(pending.empty())) {
     253                    break;
     254                }
     255                for (auto v : pending) {
     256                    bool ready = true;
     257                    for (auto e : make_iterator_range(out_edges(v, G))) {
     258                        const auto w = target(e, G);
     259                        if (LLVM_UNLIKELY(out_degree(w, G) != 0 && reachability[w].empty())) {
     260                            ready = false;
     261                            break;
     262                        }
     263                    }
     264                    if (ready) {
     265                        Q.push_back(v);
     266                    }
     267                }
     268                pending.clear();
     269                assert (!Q.empty());
     270            }
     271
     272        }
     273    }
     274
     275    void initialize_probabilities() {
     276        std::random_device rd;
     277        std::default_random_engine rand(rd());
     278        std::uniform_int_distribution<size_t> dist(std::numeric_limits<size_t>::min(), std::numeric_limits<size_t>::max());
     279        const auto n = num_vertices(G);
     280        P.resize(n);
     281        std::generate_n(P.begin(), n, [&dist, &rand](){ return dist(rand); });
     282    }
     283
     284    void ready_sort() {
     285        std::sort(R.begin(), R.end(), [this](const Vertex u, const Vertex v){ return P[u] < P[v]; });
     286    }
     287
     288    Vertex choose_ready(const unsigned index) {
     289        assert (!R.empty());
     290        const auto u = R.back();
     291        assert (std::get<0>(I[u]) == 0);
     292        std::get<0>(I[u]) = index;
     293        R.pop_back();
     294        return u;
     295    }
     296
     297    void update_liveness(const Vertex u) {
     298        // determine which statements were killed (i.e., u was its last unscheduled user) or
     299        // killable (i.e., u is the penultimate unscheduled user)
     300        for (auto ei : make_iterator_range(in_edges(u, G))) {
     301            const auto v = source(ei, G);
     302            const auto f = L.find(v);
     303            if (f != L.end()) {
     304                bool killed = true;
     305                for (auto ej : make_iterator_range(out_edges(v, G))) {
     306                    if (std::get<0>(I[target(ej, G)]) == 0) {
     307                        killed = false;
     308                        break;
     309                    }
     310                }
     311                if (killed) {
     312                    L.erase(f);
     313                }
     314            }
     315        }
     316        L.insert_unique(u);
     317    }
     318
     319    size_t get_live_weight() {
     320        return L.size();
     321    }
     322
     323    void queue_to_ready(const Vertex u) {
     324        // determine which statements are now ready (i.e., u was its last unscheduled input)
    270325        for (auto ei : make_iterator_range(out_edges(u, G))) {
     326            const auto v = target(ei, G);
    271327            bool ready = true;
    272             const auto v = target(ei, G);
    273328            for (auto ej : make_iterator_range(in_edges(v, G))) {
    274                 if (ordering[source(ej, G)]) {
     329                if (std::get<0>(I[source(ej, G)]) == 0) {
    275330                    ready = false;
    276331                    break;
     
    278333            }
    279334            if (ready) {
    280                 auto entry = std::make_pair(ordering[v], v);
    281                 auto position = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator);
    282                 readySet.insert(position, entry);
    283                 assert (std::is_sorted(readySet.cbegin(), readySet.cend(), readyComparator));
    284             }
    285         }
    286     }
    287 
    288 }
    289 
    290 /** ------------------------------------------------------------------------------------------------------------- *
    291  * @brief schedule
    292  ** ------------------------------------------------------------------------------------------------------------- */
    293 void schedule(PabloFunction & function) {
    294     schedule(function.getEntryBlock());
    295 }
     335                R.push_back(v);
     336            }
     337        }
     338    }
     339
     340
     341
     342private:
     343
     344    Vertex find(Statement * expr) {
     345        const auto f = M.find(expr);
     346        if (f == M.end()) {
     347            const auto u = add_vertex(G);
     348            assert (u == I.size());
     349            I.emplace_back(0, expr);
     350            M.emplace(expr, u);
     351            return u;
     352        } else {
     353            return f->second;
     354        }
     355    }
     356
     357private:
     358
     359    std::vector<Vertex> R;      // ready
     360    flat_set<Vertex> L;         // live variables
     361    std::vector<IndexPair> I;   // index
     362    std::vector<size_t> P;
     363
     364    Graph G;
     365    Map M;
     366};
     367
    296368
    297369/** ------------------------------------------------------------------------------------------------------------- *
    298370 * @brief optimize
    299371 ** ------------------------------------------------------------------------------------------------------------- */
    300 bool SchedulingPrePass::optimize(PabloFunction & function) {
    301     schedule(function);
     372bool SchedulingPrePass::optimize(PabloKernel * const kernel) {
     373//    #ifdef NDEBUG
     374//    report_fatal_error("DistributivePass is unsupported");
     375//    #else
     376    SchedulingPrePassContainer S;
     377    S.run(kernel->getEntryBlock());
    302378    #ifndef NDEBUG
    303     PabloVerifier::verify(function, "post-scheduling-prepass");
     379    PabloVerifier::verify(kernel, "post-scheduling-prepass");
    304380    #endif
    305381    return true;
    306 
     382//    #endif
    307383}
    308384
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/schedulingprepass.h

    r4919 r5510  
    44namespace pablo {
    55
    6 class PabloFunction;
     6class PabloKernel;
    77
    88class SchedulingPrePass {
    99public:
    10     static bool optimize(PabloFunction & function);
    11 protected:
    12     SchedulingPrePass() = default;
     10    static bool optimize(PabloKernel * kernel);
    1311};
    1412
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r5486 r5510  
    169169bool dominates(const PabloAST * const expr1, const PabloAST * const expr2);
    170170
     171inline bool strictly_dominates(const PabloAST * const expr1, const PabloAST * const expr2) {
     172    return (expr1 != expr2) && dominates(expr1, expr2);
     173}
     174
    171175bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2);
     176
     177inline bool strictly_postdominates(const PabloAST * const expr1, const PabloAST * const expr2) {
     178    return (expr1 != expr2) && postdominates(expr1, expr2);
     179}
    172180
    173181class StatementList;
     
    314322    }
    315323
     324    unsigned getCarryWidth() const {
     325        return mCarryWidth;
     326    }
     327
     328    void setCarryWidth(const unsigned carryWidth) {
     329        mCarryWidth = carryWidth;
     330    }
     331
    316332    virtual ~CarryProducingStatement() = default;
    317333
     
    320336    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
    321337    : Statement(id, type, operands, name, allocator)
    322     , mCarryGroup(0) {
     338    , mCarryGroup(0)
     339    , mCarryWidth(0) {
    323340
    324341    }
     
    326343    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * name, Allocator & allocator)
    327344    : Statement(id, type, reserved, name, allocator)
    328     , mCarryGroup(0) {
     345    , mCarryGroup(0)
     346    , mCarryWidth(0) {
    329347
    330348    }
     
    333351    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * name, Allocator & allocator)
    334352    : Statement(id, type, begin, end, name, allocator)
    335     , mCarryGroup(0) {
     353    , mCarryGroup(0)
     354    , mCarryWidth(0) {
    336355
    337356    }
     
    340359
    341360    unsigned mCarryGroup;
     361    unsigned mCarryWidth;
    342362};
    343363
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r5493 r5510  
    2424#include <pablo/pe_var.h>
    2525#include <pablo/ps_assign.h>
     26#ifdef USE_CARRYPACK_MANAGER
     27#include <pablo/carrypack_manager.h>
     28#else
    2629#include <pablo/carry_manager.h>
     30#endif
    2731#include <kernels/kernel_builder.h>
    2832#include <kernels/streamset.h>
  • icGREP/icgrep-devel/icgrep/pablo/pablo_kernel.h

    r5486 r5510  
    3030    friend class PabloBlock;
    3131    friend class CarryManager;
     32    friend class CarryPackManager;
    3233
    3334public:
  • icGREP/icgrep-devel/icgrep/pablo/pablo_toolchain.cpp

    r5464 r5510  
    1010#include <pablo/optimizers/codemotionpass.h>
    1111#include <pablo/optimizers/distributivepass.h>
     12#include <pablo/optimizers/schedulingprepass.h>
    1213#include <pablo/passes/flattenif.hpp>
    1314#include <pablo/analysis/pabloverifier.hpp>
     
    4041    PabloOptimizationsOptions(cl::values(clEnumVal(DisableSimplification, "Disable Pablo Simplification pass (not recommended)"),
    4142                                         clEnumVal(DisableCodeMotion, "Moves statements into the innermost legal If-scope and moves invariants out of While-loops."),
    42                                          clEnumVal(EnableDistribution, "apply distribution law optimization."),
     43                                         clEnumVal(EnableDistribution, "Apply distribution law optimization."),
     44
     45                                         clEnumVal(EnableSchedulingPrePass, "Pablo Statement Scheduling Pre-Pass"),
    4346                                         clEnumValEnd), cl::cat(PabloOptions));
    4447
     
    7174        DistributivePass::optimize(kernel);
    7275    }
     76    if (PabloOptimizationsOptions.isSet(EnableSchedulingPrePass)) {
     77        SchedulingPrePass::optimize(kernel);
     78    }
    7379    if (DebugOptions.isSet(ShowOptimizedPablo)) {
    7480        if (PabloOutputFilename.empty()) {
  • icGREP/icgrep-devel/icgrep/pablo/pablo_toolchain.h

    r5464 r5510  
    1818
    1919enum PabloCompilationFlags {
    20     DisableSimplification, DisableCodeMotion, EnableDistribution
     20    DisableSimplification, DisableCodeMotion, EnableDistribution, EnableSchedulingPrePass
    2121};
    2222   
  • icGREP/icgrep-devel/icgrep/toolchain/cpudriver.cpp

    r5493 r5510  
    155155        PM.add(createVerifierPass());
    156156    }
    157     PM.add(createPromoteMemoryToRegisterPass()); //Force the use of mem2reg to promote stack variables.
    158     PM.add(createReassociatePass());             //Reassociate expressions.
    159     PM.add(createGVNPass());                     //Eliminate common subexpressions.
    160     PM.add(createInstructionCombiningPass());    //Simple peephole optimizations and bit-twiddling.
    161     PM.add(createCFGSimplificationPass());
     157    PM.add(createPromoteMemoryToRegisterPass());    // Promote stack variables to constants or PHI nodes
     158    PM.add(createCFGSimplificationPass());          // Remove dead basic blocks and unnecessary branch statements / phi nodes
     159    PM.add(createEarlyCSEPass());                   // Simple common subexpression elimination pass
     160    PM.add(createInstructionCombiningPass());       // Simple peephole optimizations and bit-twiddling.
     161    PM.add(createReassociatePass());                // Canonicalizes commutative expressions
     162    PM.add(createGVNPass());                        // Global value numbering redundant expression elimination pass
     163    PM.add(createCFGSimplificationPass());          // Repeat CFG Simplification to "clean up" any newly found redundant phi nodes
    162164
    163165    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::ShowIR))) {
Note: See TracChangeset for help on using the changeset viewer.