Ignore:
Timestamp:
Dec 1, 2015, 5:13:00 PM (4 years ago)
Author:
nmedfort
Message:

Bug fixes

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.cpp

    r4885 r4886  
    2222 * @brief finalize
    2323 ** ------------------------------------------------------------------------------------------------------------- */
    24 inline void FactorizeDFG::finalize(Variadic * const var, PabloBlock * block) {
     24inline Statement * FactorizeDFG::finalize(Variadic * const var, PabloBlock * block) {
     25    PabloAST * result = nullptr;
     26    assert (var->getNumOperands() > 2);
    2527    block->setInsertPoint(var->getPrevNode());
    26     std::sort(var->begin(), var->end());
    27     while (var->getNumOperands() > 2) {
     28    while (var->getNumOperands() > 1) {
     29        PabloAST * const op2 = var->removeOperand(1);
    2830        PabloAST * const op1 = var->removeOperand(0);
    29         PabloAST * const op2 = var->removeOperand(0);
    30         PabloAST * newOp = nullptr;
     31        assert (op1 != op2);
    3132        if (isa<And>(var)) {
    32             newOp = block->createAnd(op1, op2);
     33            result = block->createAnd(op1, op2);
    3334        } else if (isa<Or>(var)) {
    34             newOp = block->createOr(op1, op2);
     35            result = block->createOr(op1, op2);
    3536        } else { // if (isa<Xor>(var)) {
    36             newOp = block->createXor(op1, op2);
    37         }
    38         var->addOperand(newOp);
    39     }
     37            result = block->createXor(op1, op2);
     38        }
     39        var->addOperand(result);
     40    }
     41    return var->replaceWith(result, true);
    4042}
    4143
     
    4850        if (isa<If>(stmt) || isa<While>(stmt)) {
    4951            finalize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    50         } else if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
    51             finalize(cast<Variadic>(stmt), block);
     52        } else if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
     53            stmt = finalize(cast<Variadic>(stmt), block);
     54            continue;
    5255        }
    5356        stmt = stmt->getNextNode();
     
    317320    PabloVerifier::verify(function, "post-factorize");
    318321    #endif
    319     Simplifier::optimize(function);
    320322    ldfg.finalize(function.getEntryBlock());
    321323    #ifndef NDEBUG
    322324    PabloVerifier::verify(function, "post-finalize");
    323325    #endif
    324 }
    325 
    326 }
     326    Simplifier::optimize(function);
     327}
     328
     329}
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.h

    r4885 r4886  
    2626    void findInsertionPoint(const VertexSet & operands, PabloBlock * const scope);
    2727    void finalize(PabloBlock * const block);
    28     void finalize(Variadic * const var, PabloBlock * block);
     28    Statement * finalize(Variadic * const var, PabloBlock * block);
    2929    FactorizeDFG() = default;
    3030private:
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp

    r4885 r4886  
    66#include <boost/graph/adjacency_list.hpp>
    77#include <pablo/analysis/pabloverifier.hpp>
    8 #include <pablo/optimizers/distributivepass.h>
    9 #include <pablo/optimizers/codemotionpass.h>
    10 
    11 #include <pablo/printer_pablos.h>
    12 #include <iostream>
    138
    149using namespace boost;
     
    2217
    2318/** ------------------------------------------------------------------------------------------------------------- *
    24  * @brief flatten
     19 * @brief coalesce
    2520 ** ------------------------------------------------------------------------------------------------------------- */
    26 inline void FlattenAssociativeDFG::flatten(Variadic * const var) {
     21inline void FlattenAssociativeDFG::coalesce(Variadic * const var) {
    2722    const TypeId typeId = var->getClassTypeId();
    2823    for (unsigned i = 0; i < var->getNumOperands(); ) {
    2924        PabloAST * const op = var->getOperand(i);
    3025        if (op->getClassTypeId() == typeId) {
    31             var->removeOperand(i);
     26            Variadic * removedVar = cast<Variadic>(var->removeOperand(i));
    3227            for (unsigned j = 0; j != cast<Variadic>(op)->getNumOperands(); ++j) {
    3328                var->addOperand(cast<Variadic>(op)->getOperand(j));
     29            }
     30            if (removedVar->getNumOperands() == 1) {
     31                removedVar->replaceWith(removedVar->getOperand(0));
     32            } else if (removedVar->getNumUsers() == 0) {
     33                removedVar->eraseFromParent(true);
    3434            }
    3535            continue;
     
    4040
    4141/** ------------------------------------------------------------------------------------------------------------- *
    42  * @brief applyNegationInwards
     42 * @brief coalesce
     43 ** ------------------------------------------------------------------------------------------------------------- */
     44void FlattenAssociativeDFG::coalesce(PabloBlock * const block) {
     45    Statement * stmt = block->front();
     46    while (stmt) {
     47        Statement * next = stmt->getNextNode();
     48        if (isa<If>(stmt) || isa<While>(stmt)) {
     49            coalesce(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     50        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
     51            coalesce(cast<Variadic>(stmt));
     52        } else if (isa<Not>(stmt)) {
     53            deMorgansExpansion(cast<Not>(stmt), block);
     54        }
     55        stmt = next;
     56    }
     57}
     58
     59/** ------------------------------------------------------------------------------------------------------------- *
     60 * @brief deMorgansExpansion
    4361 *
    44  * Apply the De Morgans' law to any negated And or Or statement with the intent of further flattening its operands
    45  * and creating a bigger clause for the Simplifier to analyze.
     62 * Apply the De Morgans' law to any negated And or Or statement with the intent of further coalescing its operands
     63 * thereby allowing the Simplifier to check for tautologies and contradictions.
    4664 ** ------------------------------------------------------------------------------------------------------------- */
    47 inline void FlattenAssociativeDFG::applyNegationInwards(Not * const var, PabloBlock * const block) {
    48     PabloAST * negatedVar = var->getOperand(0);
     65inline void FlattenAssociativeDFG::deMorgansExpansion(Not * const var, PabloBlock * const block) {
     66    PabloAST * const negatedVar = var->getOperand(0);
    4967    if (isa<And>(negatedVar) || isa<Or>(negatedVar)) {
    5068        Variadic * src = cast<Variadic>(negatedVar);
     
    5371        block->setInsertPoint(var->getPrevNode());
    5472        if (isa<And>(negatedVar)) {
    55             replacement = block->createOr(operands, PabloBlock::createZeroes());
     73            replacement = block->createOr(operands);
    5674        } else {
    57             replacement = block->createAnd(operands, PabloBlock::createOnes());
     75            replacement = block->createAnd(operands);
    5876        }
    5977        block->setInsertPoint(replacement->getPrevNode());
    6078        for (unsigned i = 0; i != operands; ++i) {
    61             replacement->setOperand(i, block->createNot(src->getOperand(i)));
     79            replacement->addOperand(block->createNot(src->getOperand(i)));
    6280        }
    63         flatten(replacement);
     81        coalesce(replacement);
    6482        var->replaceWith(replacement, true, true);
    6583    }
     
    6785
    6886/** ------------------------------------------------------------------------------------------------------------- *
    69  * @brief flatten
     87 * @brief deMorgansReduction
    7088 ** ------------------------------------------------------------------------------------------------------------- */
    71 void FlattenAssociativeDFG::flatten(PabloBlock * const block) {
    72     Statement * stmt = block->front();
    73     while (stmt) {
    74         Statement * next = stmt->getNextNode();
    75         if (isa<If>(stmt) || isa<While>(stmt)) {
    76             flatten(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    77         } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
    78             flatten(cast<Variadic>(stmt));
    79         } else if (isa<Not>(stmt)) {
    80             applyNegationInwards(cast<Not>(stmt), block);
     89inline void FlattenAssociativeDFG::deMorgansReduction(Variadic * const var, PabloBlock * const block) {
     90    unsigned negations = 0;
     91    for (unsigned i = 0; i < var->getNumOperands(); ++i) {
     92        if (isa<Not>(var->getOperand(i))) {
     93            ++negations;
    8194        }
    82         stmt = next;
    8395    }
    84 }
    85 
    86 /** ------------------------------------------------------------------------------------------------------------- *
    87  * @brief extractNegationsOutwards
    88  ** ------------------------------------------------------------------------------------------------------------- */
    89 inline void FlattenAssociativeDFG::extractNegationsOutwards(Variadic * const var, PabloBlock * const block) {
    90     PabloAST * negated[var->getNumOperands()];
    91     unsigned operands = 0;
    92     for (unsigned i = 0; i != var->getNumOperands(); ) {
    93         if (isa<Not>(var->getOperand(i))) {
    94             negated[operands++] = cast<Not>(var->removeOperand(i))->getOperand(0);
    95             continue;
     96    if (negations > 1) {
     97        PabloAST * negated[negations];
     98        for (unsigned i = var->getNumOperands(), j = negations; i && j; ) {
     99            if (isa<Not>(var->getOperand(--i))) {
     100                negated[--j] = cast<Not>(var->removeOperand(i))->getOperand(0);
     101            }
    96102        }
    97         ++i;
    98     }
    99     if (operands) {
    100103        block->setInsertPoint(var->getPrevNode());
    101104        Variadic * extractedVar = nullptr;
    102105        if (isa<And>(var)) {
    103             extractedVar = block->createOr(operands, PabloBlock::createZeroes());
    104         } else {
    105             extractedVar = block->createAnd(operands, PabloBlock::createOnes());
     106            extractedVar = block->createOr(negations);
     107        } else { // if (isa<Or>(var)) {
     108            extractedVar = block->createAnd(negations);
    106109        }
    107         for (unsigned i = 0; i != operands; ++i) {
    108             extractedVar->setOperand(i, negated[i]);
     110        for (unsigned i = 0; i != negations; ++i) {
     111            extractedVar->addOperand(negated[i]);
    109112        }
    110         std::sort(extractedVar->begin(), extractedVar->end());
    111113        var->addOperand(block->createNot(extractedVar));
    112114    }
     
    116118 * @brief extractNegationsOutwards
    117119 ** ------------------------------------------------------------------------------------------------------------- */
    118 inline void FlattenAssociativeDFG::extractNegationsOutwards(PabloBlock * const block) {
     120inline void FlattenAssociativeDFG::deMorgansReduction(PabloBlock * const block) {
    119121    for (Statement * stmt : *block) {
    120122        if (isa<If>(stmt) || isa<While>(stmt)) {
    121             extractNegationsOutwards(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     123            deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    122124        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
    123             extractNegationsOutwards(cast<Variadic>(stmt), block);
     125            deMorgansReduction(cast<Variadic>(stmt), block);
    124126        }
    125127    }
     
    131133void FlattenAssociativeDFG::transform(PabloFunction & function) {
    132134
    133     FlattenAssociativeDFG::flatten(function.getEntryBlock());
     135    FlattenAssociativeDFG::coalesce(function.getEntryBlock());
    134136    #ifndef NDEBUG
    135     PabloVerifier::verify(function, "post-flatten");
    136     #endif
    137 
    138     Simplifier::optimize(function);
    139     DistributivePass::optimize(function);
    140 
    141     FlattenAssociativeDFG::extractNegationsOutwards(function.getEntryBlock());
    142     #ifndef NDEBUG
    143     PabloVerifier::verify(function, "post-extract-negations-outwards");
     137    PabloVerifier::verify(function, "post-coalescence");
    144138    #endif
    145139
    146140    Simplifier::optimize(function);
    147141
     142    FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock());
     143    #ifndef NDEBUG
     144    PabloVerifier::verify(function, "post-demorgans-reduction");
     145    #endif
     146
     147    Simplifier::optimize(function);
    148148}
    149149
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.h

    r4885 r4886  
    1212
    1313class FlattenAssociativeDFG {
     14    friend class DistributivePass;
    1415public:
    1516    static void transform(PabloFunction & function);
    1617protected:
    17 
    18     static void flatten(PabloBlock * const block);
    19     static void flatten(Variadic * const var);
    20     static void applyNegationInwards(Not * const var, PabloBlock * const block);
    21 
    22 //    static void removeCommonLiterals(PabloBlock * const block);
    23 //    static void removeCommonLiterals(Assign * const def);
    24 //    static void removeCommonLiterals(Statement * const input, Variadic * const var);
    25 
    26     static void extractNegationsOutwards(PabloBlock * const block);
    27     static void extractNegationsOutwards(Variadic * const var, PabloBlock * const block);
    28 
     18    static void coalesce(PabloBlock * const block);
     19    static void coalesce(Variadic * const var);
     20    static void deMorgansExpansion(Not * const var, PabloBlock * const block);
     21    static void deMorgansReduction(PabloBlock * const block);
     22    static void deMorgansReduction(Variadic * const var, PabloBlock * const block);
    2923    FlattenAssociativeDFG() = default;
    3024};
Note: See TracChangeset for help on using the changeset viewer.