Changeset 4701 for icGREP


Ignore:
Timestamp:
Jul 26, 2015, 4:27:22 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check in.

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

Legend:

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

    r4699 r4701  
    1616    BDDMinimizationPass am;
    1717    am.initialize(function);
    18     am.characterize(function.getEntryBlock());
    19     am.eliminateLogicallyEquivalentStatements(function.getEntryBlock());
     18    am.characterizeAndEliminateLogicallyEquivalentStatements(function);
    2019    am.simplifyAST(function);
    2120    am.shutdown();
     
    3635    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
    3736
    38     for (Statement * stmt = function.getEntryBlock().front(); ; ) {
     37    for (const Statement * stmt = function.getEntryBlock().front(); ; ) {
    3938        while ( stmt ) {
    4039
     
    4342                // next statement of the current statement into the scope stack.
    4443                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     44                variableCount += isa<If>(stmt) ? cast<If>(stmt)->getDefined().size() : cast<While>(stmt)->getVariants().size();
    4545                scope.push(stmt->getNextNode());
    4646                stmt = nested.front();
     
    4848                continue;
    4949            }
    50 
    5150            switch (stmt->getClassTypeId()) {
    5251                case PabloAST::ClassTypeId::Advance:
    5352                case PabloAST::ClassTypeId::Call:
    5453                case PabloAST::ClassTypeId::MatchStar:
    55                 case PabloAST::ClassTypeId::ScanThru:               
     54                case PabloAST::ClassTypeId::ScanThru:
    5655                    variableCount++;
    57                     break;
     56                    break;                                   
    5857                default:
    5958                    break;
     
    7170    unsigned maxVariableCount = variableCount + function.getNumOfParameters();
    7271    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);
     72    Cudd_MakeTreeNode(mManager, 0, function.getNumOfParameters(), MTR_DEFAULT);
    7573    // Map the predefined 0/1 entries
    7674    mCharacterizationMap[function.getEntryBlock().createZeroes()] = Zero();
    77     mCharacterizationMap[function.getEntryBlock().createOnes()] = One();
    78 
    79     mVariables = 0;
    80 
    81     mStatementVector.resize(maxVariableCount, nullptr);
     75    mCharacterizationMap[function.getEntryBlock().createOnes()] = One();   
    8276    // Order the variables so the input Vars are pushed to the end; they ought to
    8377    // be the most complex to resolve.   
     78    mVariables = 0;
    8479    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
    85         mStatementVector[variableCount] = const_cast<Var *>(function.getParameter(i));
    86         mCharacterizationMap[function.getParameter(i)] = Cudd_bddIthVar(mManager, variableCount++);
     80        mCharacterizationMap[function.getParameter(i)] = NewVar();
    8781    }
    8882}
     
    9488 * Scan through the program and iteratively compute the BDDs for each statement.
    9589 ** ------------------------------------------------------------------------------------------------------------- */
    96 void BDDMinimizationPass::characterize(const PabloBlock & block) {
    97     for (const Statement * stmt : block) {
     90void BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(PabloFunction & function) {
     91    SubsitutionMap baseMap;
     92    baseMap.insert(Zero(), function.getEntryBlock().createZeroes());
     93    baseMap.insert(One(), function.getEntryBlock().createOnes());
     94    Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
     95    characterizeAndEliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
     96    Cudd_AutodynDisable(mManager);
     97    Cudd_ReduceHeap(mManager, CUDD_REORDER_EXACT, 0);
     98}
     99
     100/** ------------------------------------------------------------------------------------------------------------- *
     101 * @brief characterize
     102 * @param vars the input vars for this program
     103 *
     104 * Scan through the program and iteratively compute the BDDs for each statement.
     105 ** ------------------------------------------------------------------------------------------------------------- */
     106void BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
     107    SubsitutionMap subsitutionMap(&parent);
     108    Statement * stmt = block.front();
     109    while (stmt) {
    98110        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    99             // Set the next statement to be the first statement of the inner scope and push the
    100             // next statement of the current statement into the scope stack.
    101             characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());           
    102             continue;
    103         }
    104         mCharacterizationMap.insert(std::make_pair(stmt, characterize(stmt)));
     111            characterizeAndEliminateLogicallyEquivalentStatements(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
     112            // The defined vars of If statements and variants of While statements are unique in the AST in that
     113            // they are the only way a value can escape its local block. When we simplify this code later, we
     114            // do not want to recompute whatever was found within a nested block so instead they are marked as
     115            // new variables.
     116            if (isa<If>(stmt)) {
     117                for (const Assign * defVar : cast<const If>(stmt)->getDefined()) {
     118                    mCharacterizationMap[defVar] = NewVar();
     119                }
     120            } else { // if (isa<While>(stmt)) {
     121                for (const Next * variant : cast<const While>(stmt)->getVariants()) {
     122                    mCharacterizationMap[variant] = NewVar();
     123                }
     124            }
     125        } else { // attempt to characterize this statement and replace it if
     126            DdNode * bdd = characterizeAndEliminateLogicallyEquivalentStatements(stmt);
     127            if (LLVM_LIKELY(!isa<Assign>(stmt) && !isa<Next>(stmt))) {
     128                PabloAST * replacement = subsitutionMap[bdd];
     129                if (replacement) {
     130                    Cudd_RecursiveDeref(mManager, bdd);
     131                    stmt = stmt->replaceWith(replacement, false, true);
     132                    continue;
     133                }
     134                subsitutionMap.insert(bdd, stmt);
     135            }
     136            mCharacterizationMap.insert(std::make_pair(stmt, bdd));
     137        }
     138        stmt = stmt->getNextNode();
    105139    }
    106140    Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);
     
    110144 * @brief characterize
    111145 ** ------------------------------------------------------------------------------------------------------------- */
    112 inline 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();
     146inline DdNode * BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(const Statement * const stmt) {
    116147
    117148    DdNode * bdd = nullptr;
     
    135166    switch (stmt->getClassTypeId()) {
    136167        case PabloAST::ClassTypeId::Assign:
     168        case PabloAST::ClassTypeId::Next:
    137169            return input[0];
    138170        case PabloAST::ClassTypeId::And:
    139171            bdd = And(input[0], input[1]);
    140             break;
    141         case PabloAST::ClassTypeId::Next:
     172            break;       
    142173        case PabloAST::ClassTypeId::Or:
    143174            bdd = Or(input[0], input[1]);
     
    152183            bdd = Ite(input[0], input[1], input[2]);
    153184            break;
     185        case PabloAST::ClassTypeId::Call:
     186            // TODO: we may have more than one output. Need to fix call class to allow for it.
    154187        case PabloAST::ClassTypeId::Advance:
    155         case PabloAST::ClassTypeId::Call:
    156188        case PabloAST::ClassTypeId::MatchStar:
    157189        case PabloAST::ClassTypeId::ScanThru:
    158             return NewVar(const_cast<Statement *>(stmt));
     190            return NewVar();
    159191        default:
    160192            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
     
    172204
    173205/** ------------------------------------------------------------------------------------------------------------- *
    174  * @brief eliminateLogicallyEquivalentStatements
    175  * @param entry the entry block of the program
    176  *
    177  * Scan through the program using the precomputed BDDs and replace any statements with equivalent BDDs with the
    178  * earlier one (assuming its in scope) and replace any contradictions with Zero.
    179  ** ------------------------------------------------------------------------------------------------------------- */
    180 inline void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & entry) {
    181     SubsitutionMap baseMap;
    182     baseMap.insert(Zero(), entry.createZeroes());
    183     baseMap.insert(One(), entry.createOnes());
    184     Cudd_AutodynDisable(mManager);
    185     eliminateLogicallyEquivalentStatements(entry, baseMap);
    186 }
    187 
    188 /** ------------------------------------------------------------------------------------------------------------- *
    189  * @brief eliminateLogicallyEquivalentStatements
    190  ** ------------------------------------------------------------------------------------------------------------- */
    191 void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
    192     SubsitutionMap subsitutionMap(&parent);
    193     Statement * stmt = block.front();
    194     while (stmt) {
    195         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    196             eliminateLogicallyEquivalentStatements(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
    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 /** ------------------------------------------------------------------------------------------------------------- *
    212206 * @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
    216207 ** ------------------------------------------------------------------------------------------------------------- */
    217208inline void BDDMinimizationPass::simplifyAST(PabloFunction & function) {
    218     Cudd_ReduceHeap(mManager, CUDD_REORDER_EXACT, 0);
    219     Cudd_zddVarsFromBddVars(mManager, 1);
    220209    simplifyAST(function.getEntryBlock());
    221     Cudd_PrintInfo(mManager, stderr);
    222210}
    223211
     
    227215void BDDMinimizationPass::simplifyAST(PabloBlock & block) {
    228216    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));
     217        switch (stmt->getClassTypeId()) {
     218            case PabloAST::ClassTypeId::If:
     219            case PabloAST::ClassTypeId::While:
     220                simplifyAST(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     221                break;
     222            case PabloAST::ClassTypeId::ScanThru:
     223            case PabloAST::ClassTypeId::MatchStar:
     224                simplifyAST(stmt->getOperand(1), block, stmt->getPrevNode());
     225            case PabloAST::ClassTypeId::Advance:
     226            case PabloAST::ClassTypeId::Assign:
     227            case PabloAST::ClassTypeId::Next:
     228                simplifyAST(stmt->getOperand(0), block, stmt->getPrevNode());
     229            default: break;
    233230        }
    234231    }
     
    238235 * @brief simplifyAST
    239236 ** ------------------------------------------------------------------------------------------------------------- */
    240 inline void BDDMinimizationPass::simplifyAST(PabloBlock & block, PabloAST * const stmt) {
    241 
    242     DdNode * const bdd = mCharacterizationMap[stmt];
     237inline void BDDMinimizationPass::simplifyAST(PabloAST * const expr, PabloBlock & block, Statement * const insertionPoint) {
     238
     239    DdNode * bdd = mCharacterizationMap[expr];
    243240
    244241    llvm::raw_os_ostream out(std::cerr);
    245     out << " >>>>>>>> "; PabloPrinter::print(stmt, out); out << " <<<<<<<<"; out.flush();
    246 
    247 //    unsigned count = 0;
     242    PabloPrinter::print(expr, out); out << " : " << Cudd_SupportSize(mManager, bdd) << '\n';
     243    out.flush();
     244
     245    Cudd_bddPrintCover(mManager, bdd, bdd);
     246
    248247//    // TODO: look into 0/1/x dominators?
    249248//    CUDD_VALUE_TYPE value;
    250249//    int * cube = nullptr;
     250
     251//    char output[3] = { '0', '1', '.' };
     252
    251253//    DdGen * gen = Cudd_FirstCube(mManager, bdd, &cube, &value);
    252254//    while (!Cudd_IsGenEmpty(gen)) {
    253 //        ++count;
    254255//        // cube[0 ... n - 1] = { 0 : false, 1: true, 2: don't care }
     256//        for (unsigned i = 0; i != mVariables; ++i) {
     257//            out << output[cube[i]];
     258//        }
     259//        out << '\n';
    255260//        Cudd_NextCube(gen, &cube, &value);
    256261//    }
    257262//    Cudd_GenFree(gen);
    258263
    259 //    out << count;
    260 
    261     out << "\n"; out.flush();
    262 
    263 
    264 
    265 
    266 //    block.setInsertPoint(stmt->getPrevNode());
     264//    out.flush();
     265
     266    block.setInsertPoint(insertionPoint);
    267267
    268268//    DdNode * zdd = Cudd_zddPortFromBdd(mManager, bdd);
     
    283283}
    284284
    285 inline DdNode * BDDMinimizationPass::NewVar(Statement * const stmt) {
    286     mStatementVector[mVariables] = stmt;
     285inline DdNode * BDDMinimizationPass::NewVar() {
    287286    return Cudd_bddIthVar(mManager, mVariables++);
    288287}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4699 r4701  
    4242protected:
    4343    void initialize(const PabloFunction & function);
    44     void characterize(const PabloBlock & block);
    45     DdNode * characterize(const Statement * const stmt);
    46     void eliminateLogicallyEquivalentStatements(PabloBlock & entry);
    47     void eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
     44    void characterizeAndEliminateLogicallyEquivalentStatements(PabloFunction & function);
     45    void characterizeAndEliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
     46    DdNode * characterizeAndEliminateLogicallyEquivalentStatements(const Statement * const stmt);
    4847    void simplifyAST(PabloFunction & function);
    4948    void simplifyAST(PabloBlock & block);
    50     void simplifyAST(PabloBlock & block, PabloAST * const stmt);
     49    void simplifyAST(PabloAST * const value, PabloBlock & block, Statement * const insertionPoint);
    5150
    5251private:
     
    6059    DdNode * Not(DdNode * x) const;
    6160    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
    62     DdNode * NewVar(Statement * const stmt);
     61    DdNode * NewVar();
    6362    bool noSatisfyingAssignment(DdNode * const x);
    6463    void shutdown();
     
    6766    unsigned                mVariables;
    6867    CharacterizationMap     mCharacterizationMap;
    69     StatementVector         mStatementVector;
    7068};
    7169
Note: See TracChangeset for help on using the changeset viewer.