Changeset 4886


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

Bug fixes

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
14 edited

Legend:

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

    r4885 r4886  
    223223    }
    224224    return insertAtInsertionPoint(new Mod64ScanThru(from, thru, makeName(prefix, false)));
     225}
     226
     227template<typename Type>
     228static inline Type * isBinary(PabloAST * expr) {
     229    if (isa<Type>(expr) && cast<Type>(expr)->getNumOperands() == 2) {
     230        return cast<Type>(expr);
     231    }
     232    return nullptr;
    225233}
    226234
     
    241249            return createZeroes();
    242250        }
    243     } else if (Or * or1 = dyn_cast<Or>(expr1)) {
     251    } else if (Or * or1 = isBinary<Or>(expr1)) {
    244252        if (equals(or1->getOperand(0), expr2) || equals(or1->getOperand(1), expr2)) {
    245253            return expr2;
    246254        }
    247     } else if (Or * or2 = dyn_cast<Or>(expr2)) {
     255    } else if (Or * or2 = isBinary<Or>(expr2)) {
    248256        if (equals(or2->getOperand(0), expr1) || equals(or2->getOperand(1), expr1)) {
    249257            return expr1;
    250258        }
    251     }
    252     if (isa<Not>(expr1) || expr1 > expr2) {
    253         std::swap(expr1, expr2);
    254259    }
    255260    return insertAtInsertionPoint(new And(expr1, expr2, makeName("and_")));
     
    274279            return createZeroes();
    275280        }
    276     } else if (Or * or1 = dyn_cast<Or>(expr1)) {
     281    } else if (Or * or1 = isBinary<Or>(expr1)) {
    277282        if (equals(or1->getOperand(0), expr2) || equals(or1->getOperand(1), expr2)) {
    278283            return expr2;
    279284        }
    280     } else if (Or * or2 = dyn_cast<Or>(expr2)) {
     285    } else if (Or * or2 = isBinary<Or>(expr2)) {
    281286        if (equals(or2->getOperand(0), expr1) || equals(or2->getOperand(1), expr1)) {
    282287            return expr1;
    283288        }
    284289    }
    285     if (isa<Not>(expr1) || expr1 > expr2) {
    286         std::swap(expr1, expr2);
    287     }
    288290    return insertAtInsertionPoint(new And(expr1, expr2, makeName(prefix, false)));
    289291}
    290292
    291 And * PabloBlock::createAnd(const unsigned operands, PabloAST * value) {
    292     return insertAtInsertionPoint(new And(operands, value, makeName("and_")));
     293And * PabloBlock::createAnd(const unsigned reserved) {
     294    return insertAtInsertionPoint(new And(reserved, makeName("and_")));
    293295}
    294296
     
    301303        return expr1;
    302304    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    303         // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
     305        // ¬a√b = ¬¬(¬a âˆš b) = ¬(a ∧ ¬b)
    304306        return createNot(createAnd(not1->getOperand(0), createNot(expr2)));
    305307    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    306         // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
     308        // a√¬b = ¬¬(¬b âˆš a) = ¬(b ∧ ¬a)
    307309        return createNot(createAnd(not2->getOperand(0), createNot(expr1)));
    308310    } else if (equals(expr1, expr2)) {
    309311        return expr1;
    310     } else if (And * and1 = dyn_cast<And>(expr1)) {
    311         if (And * and2 = dyn_cast<And>(expr2)) {
     312    } else if (And * and1 = isBinary<And>(expr1)) {
     313        if (And * and2 = isBinary<And>(expr2)) {
    312314            PabloAST * const expr1a = and1->getOperand(0);
    313315            PabloAST * const expr1b = and1->getOperand(1);
     
    325327                return createAnd(expr1b, createOr(expr1a, expr2b));
    326328            }
    327         } else if (equals(and1->getOperand(0), expr2) || equals(and1->getOperand(1), expr2)){
    328             // (a∧b) √ a = a
     329        } else if (equals(and1->getOperand(0), expr2) || equals(and1->getOperand(1), expr2)) {
     330            // (a âˆ§ b) √ a = a
    329331            return expr2;
    330332        }
    331     } else if (And * and2 = dyn_cast<And>(expr2)) {
     333    } else if (And * and2 = isBinary<And>(expr2)) {
    332334        if (equals(and2->getOperand(0), expr1) || equals(and2->getOperand(1), expr1)) {
    333335            return expr1;
    334336        }
    335     }
    336     if (expr1 > expr2) {
    337         std::swap(expr1, expr2);
    338337    }
    339338    return insertAtInsertionPoint(new Or(expr1, expr2, makeName("or_")));
     
    353352        // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
    354353        return createNot(createAnd(not2->getOperand(0), createNot(expr1)), prefix);
    355     } else if (And * and1 = dyn_cast<And>(expr1)) {
    356         if (And * and2 = dyn_cast<And>(expr2)) {
     354    } else if (And * and1 = isBinary<And>(expr1)) {
     355        if (And * and2 = isBinary<And>(expr2)) {
    357356            PabloAST * const expr1a = and1->getOperand(0);
    358357            PabloAST * const expr1b = and1->getOperand(1);
     
    374373            return expr2;
    375374        }
    376     } else if (And * and2 = dyn_cast<And>(expr2)) {
     375    } else if (And * and2 = isBinary<And>(expr2)) {
    377376        if (equals(and2->getOperand(0), expr1) || equals(and2->getOperand(1), expr1)) {
    378377            return expr1;
    379378        }
    380379    }
    381     if (expr1 > expr2) {
    382         std::swap(expr1, expr2);
    383     }
    384380    return insertAtInsertionPoint(new Or(expr1, expr2, makeName(prefix, false)));
    385381}
    386382
    387 Or * PabloBlock::createOr(const unsigned operands, PabloAST * value) {
    388     return insertAtInsertionPoint(new Or(operands, value, makeName("or_")));
     383Or * PabloBlock::createOr(const unsigned reserved) {
     384    return insertAtInsertionPoint(new Or(reserved, makeName("or_")));
    389385}
    390386
     
    407403        }
    408404    }
    409     if (expr1 > expr2) {
    410         std::swap(expr1, expr2);
    411     }
    412405    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName("xor_")));
    413406}
     
    431424        }
    432425    }
    433     if (expr1 > expr2) {
    434         std::swap(expr1, expr2);
    435     }
    436426    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName(prefix, false)));
     427}
     428
     429Xor * PabloBlock::createXor(const unsigned reserved) {
     430    return insertAtInsertionPoint(new Xor(reserved, makeName("xor_")));
    437431}
    438432
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4885 r4886  
    107107    PabloAST * createAnd(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
    108108
    109     And * createAnd(const unsigned operands, PabloAST * value);
     109    And * createAnd(const unsigned reserved);
    110110
    111111    And * createAnd(std::vector<PabloAST *>::iterator begin, std::vector<PabloAST *>::iterator end) {
     
    125125    }
    126126
    127     Or * createOr(const unsigned operands, PabloAST * value);
     127    Or * createOr(const unsigned reserved);
    128128
    129129    PabloAST * createXor(PabloAST * expr1, PabloAST * expr2);
     
    134134        return insertAtInsertionPoint(new Xor(begin, end, makeName("xor_")));
    135135    }
     136
     137    Xor * createXor(const unsigned reserved);
    136138
    137139    PabloAST * createMatchStar(PabloAST * marker, PabloAST * charclass);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r4885 r4886  
    77#include <boost/container/flat_map.hpp>
    88#include <boost/graph/adjacency_list.hpp>
    9 
    10 #include <pablo/printer_pablos.h>
    11 #include <iostream>
    129
    1310using namespace boost;
     
    335332        block->setInsertPoint(cast<Variadic>(G[sinks.front()])->getPrevNode());
    336333        if (isa<And>(G[sinks.front()])) {
    337             outerOp = block->createAnd(intermediary.size(), PabloBlock::createOnes());
    338             innerOp = block->createOr(sources.size() + 1, outerOp);
     334            outerOp = block->createAnd(intermediary.size());
     335            innerOp = block->createOr(sources.size() + 1);
    339336        } else {
    340             outerOp = block->createOr(intermediary.size(), PabloBlock::createZeroes());
    341             innerOp = block->createAnd(sources.size() + 1, outerOp);
    342         }
    343 
    344         unsigned i = 0;
     337            outerOp = block->createOr(intermediary.size());
     338            innerOp = block->createAnd(sources.size() + 1);
     339        }
     340
    345341        for (const Vertex u : intermediary) {
    346342            for (const Vertex v : sinks) {
    347343                cast<Variadic>(G[v])->deleteOperand(G[u]);
    348344            }
    349             outerOp->setOperand(i++, cast<Variadic>(G[u]));
    350         }
    351 
    352         i = 0;
     345            outerOp->addOperand(G[u]);
     346        }
     347
    353348        for (const Vertex u : sources) {
    354349            for (const Vertex v : intermediary) {
    355350                cast<Variadic>(G[v])->deleteOperand(G[u]);
    356351            }
    357             innerOp->setOperand(i++, G[u]);
    358         }
     352            innerOp->addOperand(G[u]);
     353        }
     354        innerOp->addOperand(outerOp);
     355
    359356        for (const Vertex u : sinks) {
    360357            cast<Variadic>(G[u])->addOperand(innerOp);
     
    387384    PabloVerifier::verify(function, "post-distribution");
    388385    #endif
     386
    389387    Simplifier::optimize(function);
    390388    return modified;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4885 r4886  
    5454
    5555/** ------------------------------------------------------------------------------------------------------------- *
    56  * @brief foldReassociativeFunction
    57  ** ------------------------------------------------------------------------------------------------------------- */
    58 PabloAST * Simplifier::foldReassociativeFunction(Variadic * const var, PabloBlock * const block) {
     56 * @brief fold
     57 ** ------------------------------------------------------------------------------------------------------------- */
     58inline PabloAST * Simplifier::fold(Variadic * const var, PabloBlock * const block) {
    5959
    6060    assert (var);
     
    8080            if (LLVM_UNLIKELY(isa<Xor>(var))) {
    8181                var->removeOperand(i - 1);
    82                 if (LLVM_UNLIKELY(var->getNumOperands() == 0)) {
    83                     return PabloBlock::createZeroes();
    84                 }
    8582            }
    8683            continue;
     
    133130    if (LLVM_UNLIKELY(negated)) {
    134131        block->setInsertPoint(var);
    135         if (replacement) {
    136             replacement = block->createNot(replacement);
    137         } else {
    138             var->replaceAllUsesWith(block->createNot(var));
    139         }
     132        replacement = block->createNot(replacement ? replacement : var);
    140133    }
    141134    return replacement;
     
    143136
    144137/** ------------------------------------------------------------------------------------------------------------- *
    145  * @brief canTriviallyFold
    146  ** ------------------------------------------------------------------------------------------------------------- */
    147 inline static PabloAST * canTriviallyFold(Statement * stmt, PabloBlock * block) {
    148     for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    149         if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
    150             switch (stmt->getClassTypeId()) {
    151                 case PabloAST::ClassTypeId::Advance:
    152                     return block->createZeroes();
    153                 case PabloAST::ClassTypeId::Not:
    154                     return block->createOnes();
    155                 case PabloAST::ClassTypeId::Sel:
    156                     block->setInsertPoint(stmt->getPrevNode());
    157                     switch (i) {
    158                         case 0: return stmt->getOperand(2);
    159                         case 1: return block->createAnd(block->createNot(stmt->getOperand(0)), stmt->getOperand(2));
    160                         case 2: return block->createAnd(stmt->getOperand(0), stmt->getOperand(1));
    161                     }
    162                 case PabloAST::ClassTypeId::ScanThru:
    163                 case PabloAST::ClassTypeId::MatchStar:
    164                     return stmt->getOperand(0);
    165                 default: break;
    166             }
    167         } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
    168             block->setInsertPoint(stmt->getPrevNode());
    169             switch (stmt->getClassTypeId()) {
    170                 case PabloAST::ClassTypeId::Not:
    171                     return block->createZeroes();
    172                 case PabloAST::ClassTypeId::Sel:
    173                     block->setInsertPoint(stmt->getPrevNode());
    174                     switch (i) {
    175                         case 0: return stmt->getOperand(1);
    176                         case 1: return block->createOr(stmt->getOperand(0), stmt->getOperand(2));
    177                         case 2: return block->createOr(block->createNot(stmt->getOperand(0)), stmt->getOperand(1));
    178                     }
    179                 case PabloAST::ClassTypeId::ScanThru:
    180                     if (i == 1) {
     138 * @brief fold
     139 ** ------------------------------------------------------------------------------------------------------------- */
     140inline PabloAST * Simplifier::fold(Statement * stmt, PabloBlock * block) {
     141    if (isReassociative(stmt)) {
     142        return fold(cast<Variadic>(stmt), block);
     143    } else {
     144        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     145            if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
     146                switch (stmt->getClassTypeId()) {
     147                    case PabloAST::ClassTypeId::Advance:
    181148                        return block->createZeroes();
    182                     }
    183                     break;
    184                 case PabloAST::ClassTypeId::MatchStar:
    185                     if (i == 0) {
     149                    case PabloAST::ClassTypeId::Not:
    186150                        return block->createOnes();
    187                     }
    188                     break;
    189                 default: break;
    190             }
    191         }
    192     }
    193     return nullptr;
     151                    case PabloAST::ClassTypeId::Sel:
     152                        block->setInsertPoint(stmt->getPrevNode());
     153                        switch (i) {
     154                            case 0: return stmt->getOperand(2);
     155                            case 1: return block->createAnd(block->createNot(stmt->getOperand(0)), stmt->getOperand(2));
     156                            case 2: return block->createAnd(stmt->getOperand(0), stmt->getOperand(1));
     157                        }
     158                    case PabloAST::ClassTypeId::ScanThru:
     159                    case PabloAST::ClassTypeId::MatchStar:
     160                        return stmt->getOperand(0);
     161                    default: break;
     162                }
     163            } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
     164                block->setInsertPoint(stmt->getPrevNode());
     165                switch (stmt->getClassTypeId()) {
     166                    case PabloAST::ClassTypeId::Not:
     167                        return block->createZeroes();
     168                    case PabloAST::ClassTypeId::Sel:
     169                        block->setInsertPoint(stmt->getPrevNode());
     170                        switch (i) {
     171                            case 0: return stmt->getOperand(1);
     172                            case 1: return block->createOr(stmt->getOperand(0), stmt->getOperand(2));
     173                            case 2: return block->createOr(block->createNot(stmt->getOperand(0)), stmt->getOperand(1));
     174                        }
     175                    case PabloAST::ClassTypeId::ScanThru:
     176                        if (i == 1) {
     177                            return block->createZeroes();
     178                        }
     179                        break;
     180                    case PabloAST::ClassTypeId::MatchStar:
     181                        if (i == 0) {
     182                            return block->createOnes();
     183                        }
     184                        break;
     185                    default: break;
     186                }
     187            }
     188        }
     189        return nullptr;
     190    }
    194191}
    195192
     
    383380            // statements into the body.
    384381        } else {
    385             PabloAST * folded = nullptr;
    386             if (isReassociative(stmt)) {
    387                 folded =  foldReassociativeFunction(cast<Variadic>(stmt), block);
    388             } else {
    389                 folded = canTriviallyFold(stmt, block);
    390             }
    391             if (folded) {
     382            if (PabloAST * folded = fold(stmt, block)) {
    392383                // If we determine we can fold this statement,
    393384                Statement * const prior = stmt->getPrevNode();
    394385                stmt->replaceWith(folded, true);
    395                 stmt = prior ? prior->getNextNode() : block->front();
     386                stmt = LLVM_LIKELY(prior != nullptr) ? prior->getNextNode() : block->front();
    396387                continue;
    397388            }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4880 r4886  
    1616private:
    1717    static void eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor = nullptr);
    18     static PabloAST * foldReassociativeFunction(Variadic * const var, PabloBlock * const block);
     18    static PabloAST * fold(Variadic * const var, PabloBlock * const block);
     19    static PabloAST * fold(Statement * const stmt, PabloBlock * const block);
    1920    static void deadCodeElimination(PabloBlock * const block);
    2021    static void strengthReduction(PabloBlock * const block);
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4878 r4886  
    2929        if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
    3030            return true;
    31         } else if (const Var * var1 = dyn_cast<const Var>(expr1)) {
    32             if (const Var * var2 = cast<const Var>(expr2)) {
    33                 return (var1->getName() == var2->getName());
    34             }
    35         } else if (const Not* not1 = dyn_cast<const Not>(expr1)) {
    36             if (const Not* not2 = cast<const Not>(expr2)) {
    37                 return equals(not1->getExpr(), not2->getExpr());
    38             }
    39         } else if (const And* and1 = dyn_cast<const And>(expr1)) {
    40             if (const And* and2 = cast<const And>(expr2)) {
    41                 if (equals(and1->getOperand(0), and2->getOperand(0))) {
    42                     return equals(and1->getOperand(1), and2->getOperand(1));
    43                 } else if (equals(and1->getOperand(0), and2->getOperand(1))) {
    44                     return equals(and1->getOperand(1), and2->getOperand(0));
    45                 }
    46             }
    47         } else if (const Or * or1 = dyn_cast<const Or>(expr1)) {
    48             if (const Or* or2 = cast<const Or>(expr2)) {
    49                 if (equals(or1->getOperand(0), or2->getOperand(0))) {
    50                     return equals(or1->getOperand(1), or2->getOperand(1));
    51                 } else if (equals(or1->getOperand(0), or2->getOperand(1))) {
    52                     return equals(or1->getOperand(1), or2->getOperand(0));
    53                 }
    54             }
    55         } else if (const Xor * xor1 = dyn_cast<const Xor>(expr1)) {
    56             if (const Xor * xor2 = cast<const Xor>(expr2)) {
    57                 if (equals(xor1->getOperand(0), xor2->getOperand(0))) {
    58                     return equals(xor1->getOperand(1), xor2->getOperand(1));
    59                 } else if (equals(xor1->getOperand(0), xor2->getOperand(1))) {
    60                     return equals(xor1->getOperand(1), xor2->getOperand(0));
    61                 }
     31        } else if (isa<Var>(expr1)) {
     32            return (cast<Var>(expr1)->getName() == cast<Var>(expr2)->getName());
     33        } else if (isa<Not>(expr1)) {
     34            return equals(cast<Not>(expr1)->getOperand(0), cast<Not>(expr2)->getOperand(0));
     35        } else if (isa<Variadic>(expr1)) {
     36            const Variadic * const var1 = cast<Variadic>(expr1);
     37            const Variadic * const var2 = cast<Variadic>(expr2);
     38            if (var1->getNumOperands() == var2->getNumOperands()) {
     39                const unsigned operands = var1->getNumOperands();
     40                for (unsigned i = 0; i != operands; ++i) {
     41                    bool missing = true;
     42                    for (unsigned j = 0; j != operands; ++j) {
     43                        // odds are both variadics will be sorted; optimize towards testing them in order.
     44                        unsigned k = i + j;
     45                        if (LLVM_UNLIKELY(k >= operands)) {
     46                            k -= operands;
     47                        }
     48                        if (equals(var1->getOperand(i), var2->getOperand(k))) {
     49                            missing = false;
     50                            break;
     51                        }
     52                    }
     53                    if (missing) {
     54                        return false;
     55                    }
     56                }
     57                return true;
    6258            }
    6359        } else if (isa<Integer>(expr1) || isa<String>(expr1) || isa<Call>(expr1)) {
    64             // If these weren't equivalent by address they won't be equivalent by their operands.
    65             return false;
     60            return false; // If these weren't equivalent by address they won't be equivalent by their operands.
    6661        } else { // Non-reassociatable functions (i.e., Sel, Advance, ScanThru, MatchStar, Assign, Next)
    6762            const Statement * stmt1 = cast<Statement>(expr1);
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4885 r4886  
    219219    virtual ~Statement() {}
    220220protected:
    221     Statement(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
     221    explicit Statement(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
    222222    : PabloAST(id)
    223223    , mName(name)
     
    235235        }
    236236    }
    237     Statement(const ClassTypeId id, unsigned operands, PabloAST * value, const String * const name)
     237    explicit Statement(const ClassTypeId id, const unsigned reserved, const String * const name)
    238238    : PabloAST(id)
    239239    , mName(name)
     
    241241    , mPrev(nullptr)
    242242    , mParent(nullptr)
    243     , mOperands(operands)
    244     , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
    245         for (unsigned i = 0; i != operands; ++i) {
    246             assert (value);
    247             mOperand[i] = value;
    248             value->addUser(this);
    249         }
     243    , mOperands(0)
     244    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(reserved * sizeof(PabloAST *)))) {
     245        std::memset(mOperand, reserved * sizeof(PabloAST *), 0);
    250246    }
    251247    template<typename iterator>
     
    339335
    340336protected:
    341     Variadic(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
     337    explicit Variadic(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
    342338    : Statement(id, operands, name)
    343339    , mCapacity(operands.size()) {
    344340
    345341    }
    346     Variadic(const ClassTypeId id, const unsigned operands, PabloAST * value, String * name)
    347     : Statement(id, operands, value, name)
    348     , mCapacity(operands) {
     342    explicit Variadic(const ClassTypeId id, const unsigned reserved, String * name)
     343    : Statement(id, reserved, name)
     344    , mCapacity(reserved) {
    349345
    350346    }
  • 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};
  • icGREP/icgrep-devel/icgrep/pablo/pe_and.h

    r4885 r4886  
    2828
    2929    }
    30     And(const unsigned operands, PabloAST * value, String * name)
    31     : Variadic(ClassTypeId::And, operands, value, name)
     30    And(const unsigned reserved, String * name)
     31    : Variadic(ClassTypeId::And, reserved, name)
    3232    {
    3333
  • icGREP/icgrep-devel/icgrep/pablo/pe_or.h

    r4885 r4886  
    2828
    2929    }
    30     Or(const unsigned operands, PabloAST * value, String * name)
    31     : Variadic(ClassTypeId::Or, operands, value, name)
     30    Or(const unsigned reserved, String * name)
     31    : Variadic(ClassTypeId::Or, reserved, name)
    3232    {
    3333
  • icGREP/icgrep-devel/icgrep/pablo/pe_xor.h

    r4885 r4886  
    2828
    2929    }
    30     Xor(const unsigned operands, PabloAST * value, String * name)
    31     : Variadic(ClassTypeId::Xor, operands, value, name)
     30    Xor(const unsigned reserved, String * name)
     31    : Variadic(ClassTypeId::Xor, reserved, name)
    3232    {
    3333
Note: See TracChangeset for help on using the changeset viewer.