Changeset 4419


Ignore:
Timestamp:
Jan 14, 2015, 3:58:52 PM (4 years ago)
Author:
nmedfort
Message:

Some code clean up and improvements to the CSE optimization.

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

Legend:

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

    r4416 r4419  
    3131
    3232PabloAST * PabloBlock::createNot(PabloAST * expr) {
    33     OptimizeNot op;
    34     return op(expr, this);
    35 }
    36 
    37 Not * PabloBlock::createNotImm(PabloAST * expr) {
     33    if (isa<Ones>(expr)) {
     34        return createZeroes();
     35    }
     36    else if (isa<Zeroes>(expr)){
     37        return createOnes();
     38    }
     39    else if (Not * not1 = dyn_cast<Not>(expr)) {
     40        return not1->getExpr();
     41    }
    3842    return insertAtInsertionPoint(new Not(expr, this));
    3943}
     
    6872
    6973PabloAST * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2) {
    70     if (expr1 < expr2) {
     74    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
     75        return expr2;
     76    }
     77    else if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
     78        return expr1;
     79    }
     80    else if (equals(expr1, expr2)) {
     81        return expr1;
     82    }
     83    else if (Not * not1 = dyn_cast<Not>(expr1)) {
     84        if (Not * not2 = dyn_cast<Not>(expr2)) {
     85            return createNot(createOr(not1->getExpr(), not2->getExpr()));
     86        }
     87        else if (equals(not1->getExpr(), expr2)) {
     88            return createZeroes();
     89        }
     90    }
     91    else if (Not * not2 = dyn_cast<Not>(expr2)) {
     92        if (equals(expr1, not2->getExpr())) {
     93            return createZeroes();
     94        }
     95    }
     96    if (isa<Not>(expr1)) {
    7197        std::swap(expr1, expr2);
    7298    }
    73     OptimizeAnd op;
    74     return op(expr1, expr2, this);
    75 }
    76 
    77 And * PabloBlock::createAndImm(PabloAST * expr1, PabloAST * expr2) {
    7899    return insertAtInsertionPoint(new And(expr1, expr2, this));
    79100}
    80101
     102
    81103PabloAST * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2) {
    82     if (expr1 < expr2) {
    83         std::swap(expr1, expr2);
    84     }
    85     OptimizeOr op;
    86     return op(expr1, expr2, this);
    87 }
    88 
    89 Or * PabloBlock::createOrImm(PabloAST * expr1, PabloAST * expr2) {
     104    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
     105        return expr1;
     106    }
     107    else if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
     108        return expr2;
     109    }
     110    else if (equals(expr1, expr2)) {
     111        return expr1;
     112    }
     113    else if (Not * not1 = dyn_cast<Not>(expr1)) {
     114        // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
     115        return createNot(createAnd(not1->getExpr(), createNot(expr2)));
     116    }
     117    else if (Not * not2 = dyn_cast<Not>(expr2)) {
     118        // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
     119        return createNot(createAnd(not2->getExpr(), createNot(expr1)));
     120    }
     121    else if (equals(expr1, expr2)) {
     122        return expr1;
     123    }
     124    else if (And * and_expr1 = dyn_cast<And>(expr1)) {
     125        if (And * and_expr2 = dyn_cast<And>(expr2)) {
     126            PabloAST * const expr1a = and_expr1->getExpr1();
     127            PabloAST * const expr1b = and_expr1->getExpr2();
     128            PabloAST * const expr2a = and_expr2->getExpr1();
     129            PabloAST * const expr2b = and_expr2->getExpr2();
     130            //These optimizations factor out common components that can occur when sets are formed by union
     131            //(e.g., union of [a-z] and [A-Z].
     132            if (equals(expr1a, expr2a)) {
     133                return createAnd(expr1a, createOr(expr1b, expr2b));
     134            }
     135            else if (equals(expr1b, expr2b)) {
     136                return createAnd(expr1b, createOr(expr1a, expr2a));
     137            }
     138            else if (equals(expr1a, expr2b)) {
     139                return createAnd(expr1a, createOr(expr1b, expr2a));
     140            }
     141            else if (equals(expr1b, expr2a)) {
     142                return createAnd(expr1b, createOr(expr1a, expr2b));
     143            }
     144        }
     145    }
    90146    return insertAtInsertionPoint(new Or(expr1, expr2, this));
    91147}
    92148
    93149PabloAST * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2) {
    94     if (expr1 < expr2) {
    95         std::swap(expr1, expr2);
    96     }
    97     OptimizeXor op;
    98     return op(expr1, expr2, this);
    99 }
    100 
    101 Xor * PabloBlock::createXorImm(PabloAST * expr1, PabloAST * expr2) {
     150    if (isa<Ones>(expr1)) {
     151        return createNot(expr2);
     152    }
     153    else if (isa<Zeroes>(expr1)){
     154        return expr2;
     155    }
     156    else if (isa<Ones>(expr2)) {
     157        return createNot(expr1);
     158    }
     159    else if (isa<Zeroes>(expr2)){
     160        return expr1;
     161    }
     162    else if (Not * not1 = dyn_cast<Not>(expr1)) {
     163        if (Not * not2 = dyn_cast<Not>(expr2)) {
     164            return createXor(not1->getExpr(), not2->getExpr());
     165        }
     166    }
    102167    return insertAtInsertionPoint(new Xor(expr1, expr2,  this));
    103168}
     
    106171
    107172PabloAST * PabloBlock::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
    108     OptimizeSel op;
    109     return op(condition, trueExpr, falseExpr, this);
    110 }
    111 
    112 Sel * PabloBlock::createSelImm(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
     173    assert (condition && trueExpr && falseExpr && pb);
     174
     175    if (isa<Ones>(condition)) {
     176        return trueExpr;
     177    }
     178    else if (isa<Zeroes>(condition)){
     179        return falseExpr;
     180    }
     181    else if (isa<Ones>(trueExpr)) {
     182        return createOr(condition, falseExpr);
     183    }
     184    else if (isa<Zeroes>(trueExpr)){
     185        return createAnd(createNot(condition), falseExpr);
     186    }
     187    else if (isa<Ones>(falseExpr)) {
     188        return createOr(createNot(condition), trueExpr);
     189    }
     190    else if (isa<Zeroes>(falseExpr)){
     191        return createAnd(condition, trueExpr);
     192    }
     193    else if (equals(trueExpr, falseExpr)) {
     194        return trueExpr;
     195    }
     196    else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getExpr(), falseExpr)) {
     197        return createXor(condition, falseExpr);
     198    }
     199    else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getExpr())){
     200        return createXor(condition, falseExpr);
     201    }
    113202    return insertAtInsertionPoint(new Sel(condition, trueExpr, falseExpr, this));
    114203}
    115 
    116204
    117205If * PabloBlock::createIf(PabloAST * condition, std::vector<Assign *> && definedVars, PabloBlock & body) {
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4416 r4419  
    5454class PabloBlock : public StatementList {
    5555    friend class pablo::PabloAST;
    56     friend struct OptimizeAnd;
    57     friend struct OptimizeOr;
    58     friend struct OptimizeSel;
    59     friend struct OptimizeXor;
    60     friend struct OptimizeNot;
    6156public:
    6257
     
    109104    PabloAST * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr);
    110105
    111     And * createAndImm(PabloAST * expr1, PabloAST * expr2);
    112 
    113     Not * createNotImm(PabloAST * expr);
    114 
    115     Or * createOrImm(PabloAST * expr1, PabloAST * expr2);
    116 
    117     Xor * createXorImm(PabloAST * expr1, PabloAST * expr2);
    118 
    119     Sel * createSelImm(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr);
    120 
    121106    If * createIf(PabloAST * condition, std::vector<Assign *> && definedVars, PabloBlock & body);
    122107
  • icGREP/icgrep-devel/icgrep/pablo/expression_map.hpp

    r4416 r4419  
    3030    }
    3131
    32 
    33 //    template <class Type, typename... Params>
    34 //    inline Type * findOrMake(const PabloAST::ClassTypeId type, Args... args, Params... params) {
    35 //        Key key = std::make_tuple(type, args...);
    36 //        PabloAST * const f = find(key);
    37 //        if (f) {
    38 //            return cast<Type>(f);
    39 //        }
    40 //        PabloAST * const expr = new Type(std::forward<Args>(args)..., std::forward<Params>(params)...);
    41 //        mMap.insert(std::make_pair(std::move(key), expr));
    42 //        return cast<Type>(expr);
    43 //    }
    44 
    45 //    template <class Functor, typename... Params>
    46 //    inline PabloAST * findOrCall(const PabloAST::ClassTypeId type, Args... args, Params... params) {
    47 //        Key key = std::make_tuple(type, args...);
    48 //        PabloAST * const f = find(key);
    49 //        if (f) {
    50 //            return f;
    51 //        }
    52 //        Functor mf;
    53 //        PabloAST * const expr = mf(std::forward<Args>(args)..., std::forward<Params>(params)...);
    54 //        mMap.insert(std::make_pair(std::move(key), expr));
    55 //        return expr;
    56 //    }
    57 
    5832    inline bool erase(const PabloAST::ClassTypeId type, Args... args) {
    5933        Key key = std::make_tuple(type, args...);
     
    6539        return true;
    6640    }
     41
     42    inline PabloAST * find(const PabloAST::ClassTypeId type, Args... args) const {
     43        Key key = std::make_tuple(type, args...);
     44        return find(key);
     45    }
     46
     47private:
    6748
    6849    inline PabloAST * find(const Key & key) const {
     
    122103            case PabloAST::ClassTypeId::Or:
    123104            case PabloAST::ClassTypeId::Xor:
     105                // test whether the communative version of this statement exists
     106                if (PabloAST * commExpr = mBinary.find(stmt->getClassTypeId(), stmt->getOperand(1), stmt->getOperand(0))) {
     107                    return std::make_pair(commExpr, false);
     108                }
    124109            case PabloAST::ClassTypeId::ScanThru:
    125110            case PabloAST::ClassTypeId::MatchStar:
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4416 r4419  
    33#include <pablo/expression_map.hpp>
    44
    5 //#include <pablo/printer_pablos.h>
     5#include <pablo/printer_pablos.h>
    66
    77
     
    1010
    1111bool Simplifier::optimize(PabloBlock & block) {
     12    eliminateRedundantCode(block);
    1213
    13     eliminateRedundantCode(nullptr, block);
    14 
    15 
    16 
     14    deadCodeElimination(block);
    1715    return true;
    1816}
    1917
    20 void Simplifier::eliminateRedundantCode(ExpressionTable * predecessor, PabloBlock & block) {
     18void Simplifier::eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor) {
    2119    ExpressionTable encountered(predecessor);
    2220
    2321    Statement * stmt = block.front();
    2422    while (stmt) {
    25 
    2623        if (isa<Assign>(stmt)) {
    2724            Assign * assign = cast<Assign>(stmt);
     
    3532                }
    3633                assign->replaceAllUsesWith(expr);
    37                 stmt = assign->removeFromParent();
     34                // Note: we cannot delete recursively yet because our "encountered" table may would not be
     35                // updated properly. The dead code elimination pass will perform any final clean-up.
     36                stmt = assign->eraseFromParent();
    3837                continue;
    3938            }
     
    4140        else { // non-Assign node
    4241
     42            bool canTriviallyFold = false;
     43
     44            // Do a trivial folding test to see if we're using all 0s or 1s as an operand.
     45            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     46                if (isa<Zeroes>(stmt->getOperand(i)) || isa<Ones>(stmt->getOperand(i))) {
     47                    canTriviallyFold = true;
     48                    break;
     49                }
     50            }
     51
     52            if (canTriviallyFold) {
     53                PabloAST * expr = nullptr;
     54                block.setInsertPoint(stmt->getPrevNode());
     55                switch (stmt->getClassTypeId()) {
     56                    case PabloAST::ClassTypeId::Advance:
     57                        expr = block.createAdvance(stmt->getOperand(0), cast<Advance>(stmt)->getAdvanceAmount());
     58                        break;
     59                    case PabloAST::ClassTypeId::And:
     60                        expr = block.createAnd(stmt->getOperand(0), stmt->getOperand(1));
     61                        break;
     62                    case PabloAST::ClassTypeId::Or:
     63                        expr = block.createOr(stmt->getOperand(0), stmt->getOperand(1));
     64                        break;
     65                    case PabloAST::ClassTypeId::Not:
     66                        expr = block.createNot(stmt->getOperand(0));
     67                        break;
     68                    case PabloAST::ClassTypeId::Xor:
     69                        expr = block.createXor(stmt->getOperand(0), stmt->getOperand(1));
     70                        break;
     71                    case PabloAST::ClassTypeId::Sel:
     72                        expr = block.createSel(stmt->getOperand(0), stmt->getOperand(1), stmt->getOperand(2));
     73                        break;
     74                    case PabloAST::ClassTypeId::ScanThru:
     75                        expr = block.createScanThru(stmt->getOperand(0), stmt->getOperand(1));
     76                        break;
     77                    case PabloAST::ClassTypeId::MatchStar:
     78                        expr = block.createMatchStar(stmt->getOperand(0), stmt->getOperand(1));
     79                        break;
     80                    default:
     81                        throw std::runtime_error("Unhandled trivial folding optimization!");
     82                }
     83                assert (expr);
     84                stmt = stmt->replaceWith(expr);
     85                // the next statement could be an Assign; just restart the loop.
     86                continue;
     87            }
     88
    4389            if (isa<If>(stmt)) {
    44                 eliminateRedundantCode(&encountered, cast<If>(stmt)->getBody());
     90                eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
    4591            }
    4692            else if (isa<While>(stmt)) {
    47                 eliminateRedundantCode(&encountered, cast<While>(stmt)->getBody());
     93                eliminateRedundantCode(cast<While>(stmt)->getBody(), &encountered);
    4894            }
    49             else if (stmt->getNumUses() == 0) {
    50                 stmt = stmt->removeFromParent();
     95            else if (stmt->getNumUses() == 0) {               
     96                stmt = stmt->eraseFromParent();
    5197                continue;
    5298            }
    5399            // When we're creating the Pablo program, it's possible that statements may occur more than once.
    54             // By recording which statements have already been seen, we can detect which statements to remove.
     100            // By recording which statements have already been seen, we can detect which statements are redundant.
    55101            const auto f = encountered.insert(stmt);
    56102            if (!std::get<1>(f)) {
    57103                stmt->replaceAllUsesWith(std::get<0>(f));
    58                 stmt = stmt->removeFromParent();
     104                stmt = stmt->eraseFromParent();
    59105                continue;
    60106            }
     
    62108        stmt = stmt->getNextNode();
    63109    }
     110    block.setInsertPoint(block.back());
    64111}
    65112
    66113
    67 void Simplifier::foldConstantAssigns(PabloBlock &) {
    68 
    69 
     114void Simplifier::deadCodeElimination(PabloBlock & block) {
     115    Statement * stmt = block.front();
     116    while (stmt) {
     117        if (isa<If>(stmt)) {
     118            deadCodeElimination(cast<If>(stmt)->getBody());
     119        }
     120        else if (isa<While>(stmt)) {
     121            deadCodeElimination(cast<While>(stmt)->getBody());
     122        }
     123        else if (stmt->getNumUses() == 0){
     124            assert ("Any Assign passed to this function ought to have users or be an output var!" && (!isa<Assign>(stmt) || cast<Assign>(stmt)->isOutputAssignment()));
     125            if (!isa<Assign>(stmt)) {
     126                stmt = stmt->eraseFromParent(true);
     127                continue;
     128            }
     129        }
     130        stmt = stmt->getNextNode();
     131    }
    70132}
    71133
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4416 r4419  
    1414    Simplifier();
    1515private:
    16     static void eliminateRedundantCode(ExpressionTable * predecessor, PabloBlock & block);
    17 
    18     static void foldConstantAssigns(PabloBlock & block);
     16    static void eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor = nullptr);
     17    static void deadCodeElimination(PabloBlock & block);
    1918private:
    2019
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4416 r4419  
    55 */
    66
    7 #include "pabloAST.h"
    8 #include "pe_advance.h"
    9 #include "pe_and.h"
    10 #include "pe_call.h"
    11 #include "pe_matchstar.h"
    12 #include "pe_not.h"
    13 #include "pe_or.h"
    14 #include "pabloAST.h"
    15 #include "pe_scanthru.h"
    16 #include "pe_sel.h"
    17 #include "pe_var.h"
    18 #include "pe_xor.h"
    19 #include "pe_zeroes.h"
    20 #include "pe_ones.h"
     7#include <pablo/pabloAST.h>
    218#include <pablo/codegenstate.h>
    229#include <llvm/Support/Compiler.h>
     10
     11#include <pablo/printer_pablos.h>
    2312
    2413namespace pablo {
     
    207196
    208197Statement * Statement::eraseFromParent(const bool recursively) {
    209     Statement * next = removeFromParent();
     198
    210199    // remove this statement from its operands' users list
    211200    for (PabloAST * op : mOperand) {
    212201        op->removeUser(this);
    213         if (recursively && isa<Statement>(op) && op->getNumUses() == 0) {
    214             cast<Statement>(op)->eraseFromParent();
    215         }
    216     }
    217     return next;
    218 }
    219 
    220 void Statement::replaceWith(PabloAST * const expr) {
    221 
     202    }
     203
     204    if (recursively) {
     205        for (PabloAST * op : mOperand) {
     206            if (op->getNumUses() == 0 && isa<Statement>(op)) {
     207                cast<Statement>(op)->eraseFromParent(true);
     208            }
     209        }
     210    }
     211
     212    return removeFromParent();
     213}
     214
     215Statement * Statement::replaceWith(PabloAST * const expr) {
    222216    if (LLVM_UNLIKELY(expr == this)) {
    223         return;
    224     }
    225 
    226     if (isa<Statement>(expr)) {
    227         Statement * stmt = cast<Statement>(expr);
    228         stmt->removeFromParent();
    229         stmt->mParent = mParent;
    230         stmt->mNext = mNext;
    231         stmt->mPrev = mPrev;
    232         if (LLVM_LIKELY(mPrev != nullptr)) {
    233             mPrev->mNext = stmt;
    234         }
    235         if (LLVM_LIKELY(mNext != nullptr)) {
    236             mNext->mPrev = stmt;
    237         }
    238         mParent=nullptr;
    239         mNext=nullptr;
    240         mPrev=nullptr;
    241     }
    242     else {
    243         removeFromParent();
    244     }
    245 
    246     // remove this statement from its operands' users list
    247     for (PabloAST * op : mOperand) {
    248         op->removeUser(this);
    249     }
    250 
    251     while (!mUsers.empty()) {
    252         PabloAST * user = mUsers.pop_back_val();
    253         if (isa<Statement>(user)) {
    254             assert(std::count(cast<Statement>(user)->mOperand.begin(), cast<Statement>(user)->mOperand.end(), this) == 1);
    255             cast<Statement>(user)->replaceUsesOfWith(this, expr);
    256         }
    257     }
    258 
     217        return getNextNode();
     218    }
     219    replaceAllUsesWith(expr);
     220    return eraseFromParent();
    259221}
    260222
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4416 r4419  
    171171    Statement * removeFromParent();
    172172    Statement * eraseFromParent(const bool recursively = false);
    173     void replaceWith(PabloAST * const expr);
     173    Statement * replaceWith(PabloAST * const expr);
    174174
    175175    inline const String * getName() const {
  • icGREP/icgrep-devel/icgrep/pablo/pe_and.cpp

    r4416 r4419  
    1919}
    2020
    21 PabloAST * OptimizeAnd::operator ()(PabloAST * expr1, PabloAST * expr2, PabloBlock * pb) {
    22 
    23     assert (expr1 && expr2 && pb);
    24 
    25     if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
    26         return expr2;
    27     }
    28     else if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
    29         return expr1;
    30     }
    31     else if (equals(expr1, expr2)) {
    32         return expr1;
    33     }
    34     else if (Not * not1 = dyn_cast<Not>(expr1)) {
    35         if (Not * not2 = dyn_cast<Not>(expr2)) {
    36             return pb->createNot(pb->createOr(not1->getExpr(), not2->getExpr()));
    37         }
    38         else if (equals(not1->getExpr(), expr2)) {
    39             return pb->createZeroes();
    40         }
    41     }
    42     else if (Not * not2 = dyn_cast<Not>(expr2)) {
    43         if (equals(expr1, not2->getExpr())) {
    44             return pb->createZeroes();
    45         }
    46     }
    47     if (isa<Not>(expr1)) {
    48         std::swap(expr1, expr2);
    49     }
    50     return pb->createAndImm(expr1, expr2);
    5121}
    52 
    53 }
  • icGREP/icgrep-devel/icgrep/pablo/pe_and.h

    r4414 r4419  
    1616
    1717class And : public Statement {
    18     friend struct OptimizeAnd;
    1918    friend class PabloBlock;
    2019public:
     
    3736};
    3837
    39 struct OptimizeAnd {
    40     PabloAST * operator()(PabloAST * expr1, PabloAST * expr2, PabloBlock * pb);
    41 };
    42 
    4338}
    4439
  • icGREP/icgrep-devel/icgrep/pablo/pe_not.cpp

    r4416 r4419  
    1818}
    1919
    20 PabloAST * OptimizeNot::operator ()(PabloAST * expr, PabloBlock * pb) {
    21 
    22     assert (expr && pb);
    23 
    24     if (isa<Ones>(expr)) {
    25         return pb->createZeroes();
    26     }
    27     else if (isa<Zeroes>(expr)){
    28         return pb->createOnes();
    29     }
    30     else if (Not * not1 = dyn_cast<Not>(expr)) {
    31         return not1->getExpr();
    32     }
    33     return pb->createNotImm(expr);
    3420}
    35 
    36 }
  • icGREP/icgrep-devel/icgrep/pablo/pe_not.h

    r4414 r4419  
    1515
    1616class Not : public Statement {
    17     friend struct OptimizeNot;
    1817    friend class PabloBlock;
    1918public:
     
    3332};
    3433
    35 struct OptimizeNot {
    36     PabloAST * operator()(PabloAST * expr, PabloBlock * pb);
    37 };
    38 
    3934}
    4035
  • icGREP/icgrep-devel/icgrep/pablo/pe_or.cpp

    r4416 r4419  
    2020}
    2121
    22 PabloAST * OptimizeOr::operator ()(PabloAST * expr1, PabloAST * expr2, PabloBlock * pb) {
    23 
    24     assert (expr1 && expr2 && pb);
    25 
    26     if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
    27         return expr1;
    28     }
    29     else if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
    30         return expr2;
    31     }
    32     else if (equals(expr1, expr2)) {
    33         return expr1;
    34     }
    35     else if (Not * not1 = dyn_cast<Not>(expr1)) {
    36         // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
    37         return pb->createNot(pb->createAnd(not1->getExpr(), pb->createNot(expr2)));
    38     }
    39     else if (Not * not2 = dyn_cast<Not>(expr2)) {
    40         // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
    41         return pb->createNot(pb->createAnd(not2->getExpr(), pb->createNot(expr1)));
    42     }
    43     else if (equals(expr1, expr2)) {
    44         return expr1;
    45     }
    46     else if (And * and_expr1 = dyn_cast<And>(expr1)) {
    47         if (And * and_expr2 = dyn_cast<And>(expr2)) {
    48             PabloAST * const expr1a = and_expr1->getExpr1();
    49             PabloAST * const expr1b = and_expr1->getExpr2();
    50             PabloAST * const expr2a = and_expr2->getExpr1();
    51             PabloAST * const expr2b = and_expr2->getExpr2();
    52             //These optimizations factor out common components that can occur when sets are formed by union
    53             //(e.g., union of [a-z] and [A-Z].
    54             if (equals(expr1a, expr2a)) {
    55                 return pb->createAnd(expr1a, pb->createOr(expr1b, expr2b));
    56             }
    57             else if (equals(expr1b, expr2b)) {
    58                 return pb->createAnd(expr1b, pb->createOr(expr1a, expr2a));
    59             }
    60             else if (equals(expr1a, expr2b)) {
    61                 return pb->createAnd(expr1a, pb->createOr(expr1b, expr2a));
    62             }
    63             else if (equals(expr1b, expr2a)) {
    64                 return pb->createAnd(expr1b, pb->createOr(expr1a, expr2b));
    65             }
    66         }
    67     }
    68     return pb->createOrImm(expr1, expr2);
    6922}
    70 
    71 }
  • icGREP/icgrep-devel/icgrep/pablo/pe_or.h

    r4414 r4419  
    1616
    1717class Or : public Statement {
    18     friend struct OptimizeOr;
    1918    friend class PabloBlock;
    2019public:
     
    3736};
    3837
    39 struct OptimizeOr {
    40     PabloAST * operator()(PabloAST * expr1, PabloAST * expr2, PabloBlock * pb);
    41 };
    42 
    4338}
    4439
  • icGREP/icgrep-devel/icgrep/pablo/pe_sel.cpp

    r4416 r4419  
    2020}
    2121
    22 PabloAST * OptimizeSel::operator()(PabloAST * if_expr, PabloAST * t_expr, PabloAST * f_expr, PabloBlock * pb) {
    23 
    24     assert (if_expr && t_expr && f_expr && pb);
    25 
    26     if (isa<Ones>(if_expr)) {
    27         return t_expr;
    28     }
    29     else if (isa<Zeroes>(if_expr)){
    30         return f_expr;
    31     }
    32     else if (isa<Ones>(t_expr)) {
    33         return pb->createOr(if_expr, f_expr);
    34     }
    35     else if (isa<Zeroes>(t_expr)){
    36         return pb->createAnd(pb->createNot(if_expr), f_expr);
    37     }
    38     else if (isa<Ones>(f_expr)) {
    39         return pb->createOr(pb->createNot(if_expr), t_expr);
    40     }
    41     else if (isa<Zeroes>(f_expr)){
    42         return pb->createAnd(if_expr, t_expr);
    43     }
    44     else if (equals(t_expr, f_expr)) {
    45         return t_expr;
    46     }
    47     else if (isa<Not>(t_expr) && equals(cast<Not>(t_expr)->getExpr(), f_expr)) {
    48         return pb->createXor(if_expr, f_expr);
    49     }
    50     else if (isa<Not>(f_expr) && equals(t_expr, cast<Not>(f_expr)->getExpr())){
    51         return pb->createXor(if_expr, f_expr);
    52     }
    53     return pb->createSelImm(if_expr, t_expr, f_expr);
    5422}
    55 
    56 }
  • icGREP/icgrep-devel/icgrep/pablo/pe_sel.h

    r4414 r4419  
    1616
    1717class Sel : public Statement {
    18     friend struct OptimizeSel;
    1918    friend class PabloBlock;
    2019public:
     
    4039};
    4140
    42 struct OptimizeSel {
    43     PabloAST * operator()(PabloAST * if_expr, PabloAST * t_expr, PabloAST * f_expr, PabloBlock * pb);
    44 };
    45 
    4641}
    4742
  • icGREP/icgrep-devel/icgrep/pablo/pe_xor.cpp

    r4416 r4419  
    1919}
    2020
    21 PabloAST * OptimizeXor::operator()(PabloAST * expr1, PabloAST * expr2, PabloBlock * pb) {
    22 
    23     assert (expr1 && expr2 && pb);
    24 
    25     if (isa<Ones>(expr1)) {
    26         return pb->createNot(expr2);
    27     }
    28     else if (isa<Zeroes>(expr1)){
    29         return expr2;
    30     }
    31     else if (isa<Ones>(expr2)) {
    32         return pb->createNot(expr1);
    33     }
    34     else if (isa<Zeroes>(expr2)){
    35         return expr1;
    36     }
    37     else if (Not * not1 = dyn_cast<Not>(expr1)) {
    38         if (Not * not2 = dyn_cast<Not>(expr2)) {
    39             return pb->createXor(not1->getExpr(), not2->getExpr());
    40         }
    41     }
    42     return pb->createXorImm(expr1, expr2);
    4321}
    44 
    45 }
  • icGREP/icgrep-devel/icgrep/pablo/pe_xor.h

    r4414 r4419  
    1616
    1717class Xor : public Statement {
    18     friend struct OptimizeXor;
    1918    friend class PabloBlock;
    2019public:
     
    3736};
    3837
    39 struct OptimizeXor {
    40     PabloAST * operator()(PabloAST * expr1, PabloAST * expr2, PabloBlock * pb);
    41 };
    42 
    4338}
    4439
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.cpp

    r4416 r4419  
    88: Statement(ClassTypeId::If, {expr}, nullptr, parent)
    99, mBody(body)
    10 , mDefined(definedVars.begin(), definedVars.end())
     10, mDefined(std::move(definedVars))
    1111, mCarryCount(0)
    1212, mAdvanceCount(0)
     
    1919    //
    2020    // Since the implied 'Next' node is a user of the Assign node, and the Assign node is
    21     // embedded into the If, the defined var is a user of the If node.
     21    // embedded into the If, the defined var is a user of the If node. However, since the
     22    // Assign's value is also dependant on the 'Next' value, the If node is also a user
     23    // of it.
    2224
    2325    for (PabloAST * assign : mDefined) {
     
    2729}
    2830
    29 void If::replaceCondOrDefinedVar(PabloAST * from, PabloAST * to) {
    30     if (mOperand[0] == from) {
    31         mOperand[0] = to;
    32     }
    33     if (isa<Statement>(from) && mDefined.remove(cast<Statement>(from))) {
    34         if (isa<Statement>(to)) {
    35             mDefined.insert(cast<Statement>(to));
    36         }
    37     }
    38 }
     31
    3932
    4033}
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.h

    r4416 r4419  
    3737        return mBody;
    3838    }
    39     inline const SetVector<Statement *> & getDefined() const {
     39    inline const DefinedVars & getDefined() const {
    4040        return mDefined;
    4141    }
     
    5454protected:
    5555    If(PabloAST * expr, DefinedVars && definedVars, PabloBlock & body, PabloBlock * parent);
    56 
    57     void replaceCondOrDefinedVar(PabloAST * from, PabloAST * to);
    58 
    5956private:
    60     PabloBlock &            mBody;
    61     SetVector<Statement *>  mDefined;
    62     unsigned                mCarryCount;
    63     unsigned                mAdvanceCount;
     57    PabloBlock &    mBody;
     58    DefinedVars     mDefined;
     59    unsigned        mCarryCount;
     60    unsigned        mAdvanceCount;
    6461};
    6562
Note: See TracChangeset for help on using the changeset viewer.