Ignore:
Timestamp:
Jul 24, 2015, 6:31:27 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check in.

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

Legend:

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

    r4695 r4699  
    1515#include <unordered_set>
    1616
     17#include <pablo/optimizers/pablo_simplifier.hpp>
     18#include <pablo/optimizers/pablo_bddminimization.h>
     19
    1720using namespace llvm;
    1821using namespace boost;
     
    160163
    161164    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
     165
     166    BDDMinimizationPass::optimize(function);
    162167
    163168    return multiplex;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4692 r4699  
    11#include "pablo_bddminimization.h"
    22#include <pablo/codegenstate.h>
    3 #include <llvm/ADT/BitVector.h>
     3#include <pablo/builder.hpp>
    44#include <stack>
    5 #include <queue>
    6 #include <unordered_set>
    7 #include <boost/container/flat_set.hpp>
    8 #include <boost/numeric/ublas/matrix.hpp>
    9 #include <boost/circular_buffer.hpp>
    10 #include <include/simd-lib/builtins.hpp>
    11 #include <pablo/builder.hpp>
    12 #include <boost/range/iterator_range.hpp>
     5#include <iostream>
    136#include <pablo/printer_pablos.h>
    147#include <cudd.h>
    158#include <util.h>
     9#include <mtr.h>
    1610
    1711using namespace llvm;
    18 using namespace boost;
    19 using namespace boost::container;
    20 using namespace boost::numeric::ublas;
    21 
    22 // #define PRINT_DEBUG_OUTPUT
    23 
    24 #if !defined(NDEBUG) || defined(PRINT_DEBUG_OUTPUT)
    25 #include <iostream>
    26 
    27 using namespace pablo;
    28 typedef uint64_t timestamp_t;
    29 
    30 static inline timestamp_t read_cycle_counter() {
    31 #ifdef __GNUC__
    32 timestamp_t ts;
    33 #ifdef __x86_64__
    34   unsigned int eax, edx;
    35   asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
    36   ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
    37 #else
    38   asm volatile("rdtsc\n" : "=A" (ts));
    39 #endif
    40   return(ts);
    41 #endif
    42 #ifdef _MSC_VER
    43   return __rdtsc();
    44 #endif
    45 }
    46 
    47 #define LOG(x) std::cerr << x << std::endl;
    48 #define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter()
    49 #define LOG_GRAPH(Name, G) \
    50     LOG(Name << " |V|=" << num_vertices(G) << ", |E|="  << num_edges(G) << \
    51                 " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
    52 
    53 
    54 #else
    55 #define LOG(x)
    56 #define RECORD_TIMESTAMP(Name)
    57 #define LOG_GRAPH(Name, G)
    58 #define LOG_NUMBER_OF_ADVANCES(entry)
    59 #endif
    60 
    6112
    6213namespace pablo {
    6314
    6415bool BDDMinimizationPass::optimize(PabloFunction & function) {
    65 
    6616    BDDMinimizationPass am;
    67     RECORD_TIMESTAMP(start_initialize);
    6817    am.initialize(function);
    69     RECORD_TIMESTAMP(end_initialize);
    70 
    71     LOG("Initialize:              " << (end_initialize - start_initialize));
    72 
    73     RECORD_TIMESTAMP(start_characterize);
    74     am.characterize(entry);
    75     RECORD_TIMESTAMP(end_characterize);
    76 
    77     LOG("Characterize:            " << (end_characterize - start_characterize));
    78 
    79     RECORD_TIMESTAMP(start_minimization);
    80     am.eliminateLogicallyEquivalentStatements(entry);
    81     RECORD_TIMESTAMP(end_minimization);
    82     LOG("Minimize:                " << (end_minimization - start_minimization));
    83 
    84     RECORD_TIMESTAMP(start_minimization);
    85     am.simplify(entry);
    86     RECORD_TIMESTAMP(end_minimization);
    87     LOG("Minimize:                " << (end_minimization - start_minimization));
    88 
    89     RECORD_TIMESTAMP(start_shutdown);
     18    am.characterize(function.getEntryBlock());
     19    am.eliminateLogicallyEquivalentStatements(function.getEntryBlock());
     20    am.simplifyAST(function);
    9021    am.shutdown();
    91     RECORD_TIMESTAMP(end_shutdown);
    92     LOG("Shutdown:                " << (end_shutdown - start_shutdown));
    93 
    94 
    95 
    96     return multiplex;
     22    return true;
    9723}
    9824
     
    10531 * the proper variable ordering.
    10632 ** ------------------------------------------------------------------------------------------------------------- */
    107 void BDDMinimizationPass::initialize(PabloFunction &function) {
     33void BDDMinimizationPass::initialize(const PabloFunction & function) {
    10834
    10935    std::stack<Statement *> scope;
     
    12652                case PabloAST::ClassTypeId::Advance:
    12753                case PabloAST::ClassTypeId::Call:
    128                 case PabloAST::ClassTypeId::ScanThru:
    12954                case PabloAST::ClassTypeId::MatchStar:
     55                case PabloAST::ClassTypeId::ScanThru:               
    13056                    variableCount++;
    13157                    break;
     
    14369
    14470    // Initialize the BDD engine ...
    145     mManager = Cudd_Init((variableCount + function.getNumOfParameters()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    146     Cudd_AutodynDisable(mManager);
    147 
     71    unsigned maxVariableCount = variableCount + function.getNumOfParameters();
     72    mManager = Cudd_Init(maxVariableCount, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     73    Cudd_MakeTreeNode(mManager, variableCount, function.getNumOfParameters(), MTR_DEFAULT);
     74    Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
    14875    // Map the predefined 0/1 entries
    14976    mCharacterizationMap[function.getEntryBlock().createZeroes()] = Zero();
    15077    mCharacterizationMap[function.getEntryBlock().createOnes()] = One();
    15178
     79    mVariables = 0;
     80
     81    mStatementVector.resize(maxVariableCount, nullptr);
    15282    // Order the variables so the input Vars are pushed to the end; they ought to
    153     // be the most complex to resolve.
     83    // be the most complex to resolve.   
    15484    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
     85        mStatementVector[variableCount] = const_cast<Var *>(function.getParameter(i));
    15586        mCharacterizationMap[function.getParameter(i)] = Cudd_bddIthVar(mManager, variableCount++);
    15687    }
     
    16495 ** ------------------------------------------------------------------------------------------------------------- */
    16596void BDDMinimizationPass::characterize(const PabloBlock & block) {
    166     for (Statement * stmt : block) {
     97    for (const Statement * stmt : block) {
    16798        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    16899            // Set the next statement to be the first statement of the inner scope and push the
    169100            // next statement of the current statement into the scope stack.
    170             characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     101            characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());           
    171102            continue;
    172103        }
    173         mCharacterizationMap[stmt] =  characterize(stmt);
    174     }
     104        mCharacterizationMap.insert(std::make_pair(stmt, characterize(stmt)));
     105    }
     106    Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);
    175107}
    176108
     
    179111 ** ------------------------------------------------------------------------------------------------------------- */
    180112inline DdNode * BDDMinimizationPass::characterize(const Statement * const stmt) {
     113
     114//    llvm::raw_os_ostream out(std::cerr);
     115//    PabloPrinter::print(stmt, "> ", out); out << "\n"; out.flush();
    181116
    182117    DdNode * bdd = nullptr;
     
    185120    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    186121        PabloAST * const op = stmt->getOperand(i);
     122        if (op == nullptr) {
     123            throw std::runtime_error("Statement has Null operand!");
     124        }
    187125        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
    188126            continue;
    189127        }
    190         input[i] = mCharacterizationMap[op];
     128        auto f = mCharacterizationMap.find(op);
     129        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
     130            throw std::runtime_error("Error in AST: attempted to characterize statement with unknown operand!");
     131        }
     132        input[i] = f->second;
    191133    }
    192134
     
    210152            bdd = Ite(input[0], input[1], input[2]);
    211153            break;
     154        case PabloAST::ClassTypeId::Advance:
     155        case PabloAST::ClassTypeId::Call:
     156        case PabloAST::ClassTypeId::MatchStar:
    212157        case PabloAST::ClassTypeId::ScanThru:
    213         case PabloAST::ClassTypeId::MatchStar:
    214         case PabloAST::ClassTypeId::Call:
    215         case PabloAST::ClassTypeId::Advance:
    216             return NewVar();
     158            return NewVar(const_cast<Statement *>(stmt));
    217159        default:
    218160            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
    219161    }
     162
     163    Cudd_Ref(bdd);
    220164
    221165    if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
     
    225169
    226170    return bdd;
    227 
    228171}
    229172
     
    239182    baseMap.insert(Zero(), entry.createZeroes());
    240183    baseMap.insert(One(), entry.createOnes());
     184    Cudd_AutodynDisable(mManager);
    241185    eliminateLogicallyEquivalentStatements(entry, baseMap);
    242186}
     
    250194    while (stmt) {
    251195        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    252             // Set the next statement to be the first statement of the inner scope and push the
    253             // next statement of the current statement into the scope stack.
    254196            eliminateLogicallyEquivalentStatements(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
    255             continue;
    256         }
    257 
    258         if (LLVM_UNLIKELY(isa<Assign>(stmt) || isa<Next>(stmt))) {
    259             continue;
    260         }
    261 
    262         DdNode * bdd = mCharacterizationMap[stmt];
    263         PabloAST * replacement = subsitutionMap[bdd];
    264         if (replacement) {
    265             Cudd_RecursiveDeref(mManager, bdd);
    266             stmt = stmt->replaceWith(replacement, false, true);
    267         }
    268         else {
    269             stmt = stmt->getNextNode();
    270         }
    271     }
    272 }
    273 
    274 /** ------------------------------------------------------------------------------------------------------------- *
    275  * @brief simplify
    276  ** ------------------------------------------------------------------------------------------------------------- */
    277 PabloAST * BDDMinimizationPass::simplify(DdNode * bdd) const {
    278 
    279     CUDD_VALUE_TYPE value;
    280     int * cube = nullptr;
    281 
    282     DdGen * gen = Cudd_FirstCube(mManager, bdd, &cube, &value);
    283     while (!Cudd_IsGenEmpty(gen)) {
    284         // cube[0 ... n - 1] = { 0 : false, 1: true, 2: don't care }
    285 
    286 
    287 
    288 
    289         Cudd_NextCube(gen, &cube, &value);
    290     }
    291     Cudd_GenFree(gen);
    292 
     197        } else if (LLVM_LIKELY(!isa<Assign>(stmt) && !isa<Next>(stmt))) {
     198            DdNode * bdd = mCharacterizationMap[stmt];
     199            PabloAST * replacement = subsitutionMap[bdd];
     200            if (replacement) {
     201                Cudd_RecursiveDeref(mManager, bdd);
     202                stmt = stmt->replaceWith(replacement, false, true);
     203                continue;
     204            }
     205            subsitutionMap.insert(bdd, stmt);
     206        }
     207        stmt = stmt->getNextNode();
     208    }
     209}
     210
     211/** ------------------------------------------------------------------------------------------------------------- *
     212 * @brief simplifyAST
     213 *
     214 * Assignment and Next statements are unique in the AST in that they are the only way a value can escape its
     215 * local block. By trying to simplify those aggressively
     216 ** ------------------------------------------------------------------------------------------------------------- */
     217inline void BDDMinimizationPass::simplifyAST(PabloFunction & function) {
     218    Cudd_ReduceHeap(mManager, CUDD_REORDER_EXACT, 0);
     219    Cudd_zddVarsFromBddVars(mManager, 1);
     220    simplifyAST(function.getEntryBlock());
     221    Cudd_PrintInfo(mManager, stderr);
     222}
     223
     224/** ------------------------------------------------------------------------------------------------------------- *
     225 * @brief simplifyAST
     226 ** ------------------------------------------------------------------------------------------------------------- */
     227void BDDMinimizationPass::simplifyAST(PabloBlock & block) {
     228    for (Statement * stmt : block) {
     229        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     230            simplifyAST(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     231        } else if (isa<Advance>(stmt) || isa<Assign>(stmt) || isa<Next>(stmt)) {
     232            simplifyAST(block, stmt->getOperand(0));
     233        }
     234    }
     235}
     236
     237/** ------------------------------------------------------------------------------------------------------------- *
     238 * @brief simplifyAST
     239 ** ------------------------------------------------------------------------------------------------------------- */
     240inline void BDDMinimizationPass::simplifyAST(PabloBlock & block, PabloAST * const stmt) {
     241
     242    DdNode * const bdd = mCharacterizationMap[stmt];
     243
     244    llvm::raw_os_ostream out(std::cerr);
     245    out << " >>>>>>>> "; PabloPrinter::print(stmt, out); out << " <<<<<<<<"; out.flush();
     246
     247//    unsigned count = 0;
     248//    // TODO: look into 0/1/x dominators?
     249//    CUDD_VALUE_TYPE value;
     250//    int * cube = nullptr;
     251//    DdGen * gen = Cudd_FirstCube(mManager, bdd, &cube, &value);
     252//    while (!Cudd_IsGenEmpty(gen)) {
     253//        ++count;
     254//        // cube[0 ... n - 1] = { 0 : false, 1: true, 2: don't care }
     255//        Cudd_NextCube(gen, &cube, &value);
     256//    }
     257//    Cudd_GenFree(gen);
     258
     259//    out << count;
     260
     261    out << "\n"; out.flush();
     262
     263
     264
     265
     266//    block.setInsertPoint(stmt->getPrevNode());
     267
     268//    DdNode * zdd = Cudd_zddPortFromBdd(mManager, bdd);
     269//    Cudd_zddPrintCover(mManager, zdd);
     270//    Cudd_RecursiveDerefZdd(mManager, zdd);
    293271}
    294272
     
    305283}
    306284
    307 inline DdNode * BDDMinimizationPass::NewVar() {
     285inline DdNode * BDDMinimizationPass::NewVar(Statement * const stmt) {
     286    mStatementVector[mVariables] = stmt;
    308287    return Cudd_bddIthVar(mManager, mVariables++);
    309288}
     
    315294inline DdNode * BDDMinimizationPass::And(DdNode * const x, DdNode * const y) {
    316295    DdNode * r = Cudd_bddAnd(mManager, x, y);
    317     Cudd_Ref(r);
    318296    return r;
    319297}
     
    326304inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) {
    327305    DdNode * r = Cudd_bddOr(mManager, x, y);
    328     Cudd_Ref(r);
    329306    return r;
    330307}
     
    332309inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) {
    333310    DdNode * r = Cudd_bddXor(mManager, x, y);
    334     Cudd_Ref(r);
    335311    return r;
    336312}
     
    342318inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
    343319    DdNode * r = Cudd_bddIte(mManager, x, y, z);
    344     Cudd_Ref(r);
    345320    return r;
    346321}
     
    354329}
    355330
    356 
    357 
    358331} // end of namespace pablo
    359332
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4692 r4699  
    22#define PABLO_BDDMINIMIZATION_H
    33
    4 #include <pablo/codegenstate.h>
    5 #include <slab_allocator.h>
    6 #include <queue>
    7 #include <boost/graph/adjacency_list.hpp>
    8 #include <boost/graph/adjacency_matrix.hpp>
    9 #include <boost/graph/edge_list.hpp>
    10 #include <boost/container/flat_map.hpp>
    11 #include <boost/container/flat_set.hpp>
    12 #include <boost/numeric/ublas/matrix.hpp>
    13 #include <random>
    14 #include <stdint.h>
    154#include <llvm/ADT/DenseMap.h>
    165
     
    209namespace pablo {
    2110
     11class PabloAST;
     12class PabloBlock;
     13class PabloFunction;
     14class Statement;
     15
    2216class BDDMinimizationPass {
    2317
    2418    using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
     19    using StatementVector = std::vector<PabloAST *>;
    2520
    2621    struct SubsitutionMap {
     
    3025            auto f = mMap.find(node);
    3126            if (f == mMap.end()) {
    32                 return mParent ? mParent->find(node) : nullptr;
     27                return mParent ? mParent->operator [](node) : nullptr;
    3328            }
    3429            return f->second;
     
    4641    static bool optimize(PabloFunction & function);
    4742protected:
    48     void initialize(PabloFunction & function);
    49     void characterize(const PabloBlock &block);
     43    void initialize(const PabloFunction & function);
     44    void characterize(const PabloBlock & block);
    5045    DdNode * characterize(const Statement * const stmt);
    5146    void eliminateLogicallyEquivalentStatements(PabloBlock & entry);
    5247    void eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
    53     void simplify(PabloBlock & entry);
    54     PabloAST * simplify(DdNode * bdd);
     48    void simplifyAST(PabloFunction & function);
     49    void simplifyAST(PabloBlock & block);
     50    void simplifyAST(PabloBlock & block, PabloAST * const stmt);
    5551
    5652private:
     
    6460    DdNode * Not(DdNode * x) const;
    6561    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
    66     DdNode * NewVar();
     62    DdNode * NewVar(Statement * const stmt);
    6763    bool noSatisfyingAssignment(DdNode * const x);
    6864    void shutdown();
     
    7167    unsigned                mVariables;
    7268    CharacterizationMap     mCharacterizationMap;
     69    StatementVector         mStatementVector;
    7370};
    7471
     72}
    7573
    7674#endif // PABLO_BDDMINIMIZATION_H
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4658 r4699  
    4343inline bool Simplifier::isSuperfluous(const Assign * const assign) {
    4444    for (const PabloAST * inst : assign->users()) {
    45         if (isa<Next>(inst) || isa<PabloFunction>(inst) || isa<If>(inst)) {
     45        if (isa<Next>(inst) || isa<PabloFunction>(inst)) {
     46            return false;
     47        } else if (isa<If>(inst)) {
     48            const If * ifNode = cast<If>(inst);
     49            if (ifNode->getCondition() == assign) {
     50                bool notFound = true;
     51                for (Assign * defVar : ifNode->getDefined()) {
     52                    if (defVar == assign) {
     53                        notFound = false;
     54                        break;
     55                    }
     56                }
     57                if (notFound) {
     58                    continue;
     59                }
     60            }
    4661            return false;
    4762        }
     
    6883                }
    6984                else {
    70                     stmt = assign->replaceWith(assign->getExpression());
     85                    stmt = assign->replaceWith(assign->getExpression(), true, true);
    7186                }
    7287                continue;
Note: See TracChangeset for help on using the changeset viewer.