Changeset 4885 for icGREP/icgrep-devel


Ignore:
Timestamp:
Nov 30, 2015, 4:30:02 PM (4 years ago)
Author:
nmedfort
Message:

More work on n-ary operations. Unresolved bug in DistributionPass?.

Location:
icGREP/icgrep-devel/icgrep
Files:
2 added
15 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4880 r4885  
    6464SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_compiler.cpp pablo/carry_manager.cpp pablo/carry_data.cpp IDISA/idisa_builder.cpp)
    6565SET(PABLO_SRC ${PABLO_SRC} pablo/analysis/pabloverifier.cpp)
    66 SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/codemotionpass.cpp pablo/optimizers/distributivepass.cpp pablo/passes/flattenassociativedfg.cpp)
     66SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/codemotionpass.cpp pablo/optimizers/distributivepass.cpp pablo/passes/flattenassociativedfg.cpp pablo/passes/factorizedfg.cpp)
    6767SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/booleanreassociationpass.cpp)
    6868IF (ENABLE_MULTIPLEXING)
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r4878 r4885  
    488488pablo/optimizers/distributivepass.h
    489489pablo/optimizers/distributivepass.cpp
     490pablo/passes/factorizedfg.h
     491pablo/passes/factorizedfg.cpp
  • icGREP/icgrep-devel/icgrep/pablo/analysis/pabloverifier.cpp

    r4876 r4885  
    179179                throw std::runtime_error(str.str());
    180180            }
     181            if (isa<If>(stmt)) {
     182                for (const Assign * def : cast<If>(stmt)->getDefined()) {
     183                    if (LLVM_UNLIKELY(def == cast<If>(stmt)->getCondition())) {
     184                        std::string tmp;
     185                        raw_string_ostream str(tmp);
     186                        str << "PabloVerifier: structure error: the condition of ";
     187                        PabloPrinter::print(cast<PabloAST>(stmt), str);
     188                        str << " cannot be defined by the If node itself.";
     189                        throw std::runtime_error(str.str());
     190                    }
     191                }
     192            }
    181193            const Statement * badEscapedValue = nullptr;
    182194            if (isa<If>(stmt)) {
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r4878 r4885  
    9191    }
    9292    else if (Not * not1 = dyn_cast<Not>(expr)) {
    93         return not1->getExpr();
     93        return not1->getOperand(0);
    9494    }
    9595    return insertAtInsertionPoint(new Not(expr, makeName("not_")));
     
    105105    }
    106106    else if (Not * not1 = dyn_cast<Not>(expr)) {       
    107         return renameNonNamedNode(not1->getExpr(), std::move(prefix));
     107        return renameNonNamedNode(not1->getOperand(0), std::move(prefix));
    108108    }
    109109    return insertAtInsertionPoint(new Not(expr, makeName(prefix, false)));
     
    232232        return expr1;
    233233    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    234         if (equals(not1->getExpr(), expr2)) {
     234        if (Not * not2 = dyn_cast<Not>(expr2)) {
     235            return createNot(createOr(not1->getOperand(0), not2->getOperand(0)));
     236        } else if (equals(not1->getOperand(0), expr2)) {
    235237            return createZeroes();
    236238        }
    237239    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    238         if (equals(expr1, not2->getExpr())) {
     240        if (equals(expr1, not2->getOperand(0))) {
    239241            return createZeroes();
    240242        }
     
    248250        }
    249251    }
     252    if (isa<Not>(expr1) || expr1 > expr2) {
     253        std::swap(expr1, expr2);
     254    }
    250255    return insertAtInsertionPoint(new And(expr1, expr2, makeName("and_")));
    251 }
    252 
    253 And * PabloBlock::createAnd(const unsigned operands, PabloAST * value) {
    254     return insertAtInsertionPoint(new And(operands, value, makeName("and_")));
    255256}
    256257
     
    258259    assert (expr1 && expr2);
    259260    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
    260         return expr2;
    261     } else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
    262         return expr1;
     261        return renameNonNamedNode(expr2, std::move(prefix));
     262    }
     263    else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
     264        return renameNonNamedNode(expr1, std::move(prefix));
    263265    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    264         if (equals(not1->getExpr(), expr2)) {
     266        if (Not * not2 = dyn_cast<Not>(expr2)) {
     267            return createNot(createOr(not1->getOperand(0), not2->getOperand(0)), prefix);
     268        }
     269        else if (equals(not1->getOperand(0), expr2)) {
    265270            return createZeroes();
    266271        }
    267272    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    268         if (equals(expr1, not2->getExpr())) {
     273        if (equals(expr1, not2->getOperand(0))) {
    269274            return createZeroes();
    270275        }
    271     } if (Or * or1 = dyn_cast<Or>(expr1)) {
     276    } else if (Or * or1 = dyn_cast<Or>(expr1)) {
    272277        if (equals(or1->getOperand(0), expr2) || equals(or1->getOperand(1), expr2)) {
    273             return expr2; // (a √ b) ∧ a = a
     278            return expr2;
    274279        }
    275280    } else if (Or * or2 = dyn_cast<Or>(expr2)) {
     
    278283        }
    279284    }
     285    if (isa<Not>(expr1) || expr1 > expr2) {
     286        std::swap(expr1, expr2);
     287    }
    280288    return insertAtInsertionPoint(new And(expr1, expr2, makeName(prefix, false)));
     289}
     290
     291And * PabloBlock::createAnd(const unsigned operands, PabloAST * value) {
     292    return insertAtInsertionPoint(new And(operands, value, makeName("and_")));
    281293}
    282294
     
    285297    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
    286298        return expr2;
    287     } else if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
     299    }
     300    if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
     301        return expr1;
     302    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     303        // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
     304        return createNot(createAnd(not1->getOperand(0), createNot(expr2)));
     305    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
     306        // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
     307        return createNot(createAnd(not2->getOperand(0), createNot(expr1)));
     308    } else if (equals(expr1, expr2)) {
    288309        return expr1;
    289310    } else if (And * and1 = dyn_cast<And>(expr1)) {
    290         if (equals(and1->getOperand(0), expr2) || equals(and1->getOperand(1), expr2)){
    291             return expr2; // (a ∧ b) √ a = a
     311        if (And * and2 = dyn_cast<And>(expr2)) {
     312            PabloAST * const expr1a = and1->getOperand(0);
     313            PabloAST * const expr1b = and1->getOperand(1);
     314            PabloAST * const expr2a = and2->getOperand(0);
     315            PabloAST * const expr2b = and2->getOperand(1);
     316            //These optimizations factor out common components that can occur when sets are formed by union
     317            //(e.g., union of [a-z] and [A-Z].
     318            if (equals(expr1a, expr2a)) {
     319                return createAnd(expr1a, createOr(expr1b, expr2b));
     320            } else if (equals(expr1b, expr2b)) {
     321                return createAnd(expr1b, createOr(expr1a, expr2a));
     322            } else if (equals(expr1a, expr2b)) {
     323                return createAnd(expr1a, createOr(expr1b, expr2a));
     324            } else if (equals(expr1b, expr2a)) {
     325                return createAnd(expr1b, createOr(expr1a, expr2b));
     326            }
     327        } else if (equals(and1->getOperand(0), expr2) || equals(and1->getOperand(1), expr2)){
     328            // (a∧b) √ a = a
     329            return expr2;
    292330        }
    293331    } else if (And * and2 = dyn_cast<And>(expr2)) {
     
    296334        }
    297335    }
     336    if (expr1 > expr2) {
     337        std::swap(expr1, expr2);
     338    }
    298339    return insertAtInsertionPoint(new Or(expr1, expr2, makeName("or_")));
    299 }
    300 
    301 Or * PabloBlock::createOr(const unsigned operands, PabloAST * value) {
    302     return insertAtInsertionPoint(new Or(operands, value, makeName("or_")));
    303340}
    304341
     
    306343    assert (expr1 && expr2);
    307344    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
    308         return expr2;
    309     } else if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
    310         return expr1;
     345        return renameNonNamedNode(expr2, std::move(prefix));
     346    }
     347    else if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
     348        return renameNonNamedNode(expr1, std::move(prefix));
     349    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     350        // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
     351        return createNot(createAnd(not1->getOperand(0), createNot(expr2)), prefix);
     352    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
     353        // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
     354        return createNot(createAnd(not2->getOperand(0), createNot(expr1)), prefix);
    311355    } else if (And * and1 = dyn_cast<And>(expr1)) {
    312         if (equals(and1->getOperand(0), expr2) || equals(and1->getOperand(1), expr2)){
    313             return expr2; // (a ∧ b) √ a = a
     356        if (And * and2 = dyn_cast<And>(expr2)) {
     357            PabloAST * const expr1a = and1->getOperand(0);
     358            PabloAST * const expr1b = and1->getOperand(1);
     359            PabloAST * const expr2a = and2->getOperand(0);
     360            PabloAST * const expr2b = and2->getOperand(1);
     361            //These optimizations factor out common components that can occur when sets are formed by union
     362            //(e.g., union of [a-z] and [A-Z].
     363            if (equals(expr1a, expr2a)) {
     364                return createAnd(expr1a, createOr(expr1b, expr2b), prefix);
     365            } else if (equals(expr1b, expr2b)) {
     366                return createAnd(expr1b, createOr(expr1a, expr2a), prefix);
     367            } else if (equals(expr1a, expr2b)) {
     368                return createAnd(expr1a, createOr(expr1b, expr2a), prefix);
     369            } else if (equals(expr1b, expr2a)) {
     370                return createAnd(expr1b, createOr(expr1a, expr2b), prefix);
     371            }
     372        } else if (equals(and1->getOperand(0), expr2) || equals(and1->getOperand(1), expr2)) {
     373            // (a∧b) √ a = a
     374            return expr2;
    314375        }
    315376    } else if (And * and2 = dyn_cast<And>(expr2)) {
     
    318379        }
    319380    }
     381    if (expr1 > expr2) {
     382        std::swap(expr1, expr2);
     383    }
    320384    return insertAtInsertionPoint(new Or(expr1, expr2, makeName(prefix, false)));
     385}
     386
     387Or * PabloBlock::createOr(const unsigned operands, PabloAST * value) {
     388    return insertAtInsertionPoint(new Or(operands, value, makeName("or_")));
    321389}
    322390
     
    325393    if (expr1 == expr2) {
    326394        return PabloBlock::createZeroes();
     395    }
     396    if (isa<Ones>(expr1)) {
     397        return createNot(expr2);
    327398    } else if (isa<Zeroes>(expr1)){
    328399        return expr2;
     400    } else if (isa<Ones>(expr2)) {
     401        return createNot(expr1);
    329402    } else if (isa<Zeroes>(expr2)){
    330403        return expr1;
    331     } else if (isa<Not>(expr1) && isa<Not>(expr2)) {
    332         return createXor(cast<Not>(expr1)->getExpr(), cast<Not>(expr2)->getExpr());
     404    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     405        if (Not * not2 = dyn_cast<Not>(expr2)) {
     406            return createXor(not1->getOperand(0), not2->getOperand(0));
     407        }
     408    }
     409    if (expr1 > expr2) {
     410        std::swap(expr1, expr2);
    333411    }
    334412    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName("xor_")));
     
    339417    if (expr1 == expr2) {
    340418        return PabloBlock::createZeroes();
     419    }
     420    if (isa<Ones>(expr1)) {
     421        return createNot(expr2, prefix);
    341422    } else if (isa<Zeroes>(expr1)){
    342423        return expr2;
     424    } else if (isa<Ones>(expr2)) {
     425        return createNot(expr1, prefix);
    343426    } else if (isa<Zeroes>(expr2)){
    344427        return expr1;
    345     } else if (isa<Not>(expr1) && isa<Not>(expr2)) {
    346         return createXor(cast<Not>(expr1)->getExpr(), cast<Not>(expr2)->getExpr());
     428    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     429        if (Not * not2 = dyn_cast<Not>(expr2)) {
     430            return createXor(not1->getOperand(0), not2->getOperand(0), prefix);
     431        }
     432    }
     433    if (expr1 > expr2) {
     434        std::swap(expr1, expr2);
    347435    }
    348436    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName(prefix, false)));
    349437}
    350 
    351 
    352 //PabloAST * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2) {
    353 //    assert (expr1 && expr2);
    354 //    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
    355 //        return expr2;
    356 //    } else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
    357 //        return expr1;
    358 //    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    359 //        if (Not * not2 = dyn_cast<Not>(expr2)) {
    360 //            return createNot(createOr(not1->getExpr(), not2->getExpr()));
    361 //        } else if (equals(not1->getExpr(), expr2)) {
    362 //            return createZeroes();
    363 //        }
    364 //    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    365 //        if (equals(expr1, not2->getExpr())) {
    366 //            return createZeroes();
    367 //        }
    368 //    } else if (Or * or1 = dyn_cast<Or>(expr1)) {
    369 //        if (equals(or1->getOperand(0), expr2) || equals(or1->getOperand(1), expr2)) {
    370 //            return expr2;
    371 //        }
    372 //    } else if (Or * or2 = dyn_cast<Or>(expr2)) {
    373 //        if (equals(or2->getOperand(0), expr1) || equals(or2->getOperand(1), expr1)) {
    374 //            return expr1;
    375 //        }
    376 //    }
    377 //    if (isa<Not>(expr1) || expr1 > expr2) {
    378 //        std::swap(expr1, expr2);
    379 //    }
    380 //    return insertAtInsertionPoint(new And(expr1, expr2, makeName("and_")));
    381 //}
    382 
    383 //PabloAST * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
    384 //    assert (expr1 && expr2);
    385 //    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
    386 //        return renameNonNamedNode(expr2, std::move(prefix));
    387 //    } else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
    388 //        return renameNonNamedNode(expr1, std::move(prefix));
    389 //    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    390 //        if (Not * not2 = dyn_cast<Not>(expr2)) {
    391 //            return createNot(createOr(not1->getExpr(), not2->getExpr()), prefix);
    392 //        }
    393 //        else if (equals(not1->getExpr(), expr2)) {
    394 //            return createZeroes();
    395 //        }
    396 //    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    397 //        if (equals(expr1, not2->getExpr())) {
    398 //            return createZeroes();
    399 //        }
    400 //    } else if (Or * or1 = dyn_cast<Or>(expr1)) {
    401 //        if (equals(or1->getOperand(0), expr2) || equals(or1->getOperand(1), expr2)) {
    402 //            return expr2;
    403 //        }
    404 //    } else if (Or * or2 = dyn_cast<Or>(expr2)) {
    405 //        if (equals(or2->getOperand(0), expr1) || equals(or2->getOperand(1), expr1)) {
    406 //            return expr1;
    407 //        }
    408 //    }
    409 //    if (isa<Not>(expr1) || expr1 > expr2) {
    410 //        std::swap(expr1, expr2);
    411 //    }
    412 //    return insertAtInsertionPoint(new And(expr1, expr2, makeName(prefix, false)));
    413 //}
    414 
    415 //PabloAST * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2) {
    416 //    assert (expr1 && expr2);
    417 //    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
    418 //        return expr2;
    419 //    }
    420 //    if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
    421 //        return expr1;
    422 //    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    423 //        // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
    424 //        return createNot(createAnd(not1->getExpr(), createNot(expr2)));
    425 //    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    426 //        // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
    427 //        return createNot(createAnd(not2->getExpr(), createNot(expr1)));
    428 //    } else if (equals(expr1, expr2)) {
    429 //        return expr1;
    430 //    } else if (And * and1 = dyn_cast<And>(expr1)) {
    431 //        if (And * and2 = dyn_cast<And>(expr2)) {
    432 //            PabloAST * const expr1a = and1->getOperand(0);
    433 //            PabloAST * const expr1b = and1->getOperand(1);
    434 //            PabloAST * const expr2a = and2->getOperand(0);
    435 //            PabloAST * const expr2b = and2->getOperand(1);
    436 //            //These optimizations factor out common components that can occur when sets are formed by union
    437 //            //(e.g., union of [a-z] and [A-Z].
    438 //            if (equals(expr1a, expr2a)) {
    439 //                return createAnd(expr1a, createOr(expr1b, expr2b));
    440 //            } else if (equals(expr1b, expr2b)) {
    441 //                return createAnd(expr1b, createOr(expr1a, expr2a));
    442 //            } else if (equals(expr1a, expr2b)) {
    443 //                return createAnd(expr1a, createOr(expr1b, expr2a));
    444 //            } else if (equals(expr1b, expr2a)) {
    445 //                return createAnd(expr1b, createOr(expr1a, expr2b));
    446 //            }
    447 //        } else if (equals(and1->getOperand(0), expr2) || equals(and1->getOperand(1), expr2)){
    448 //            // (a∧b) √ a = a
    449 //            return expr2;
    450 //        }
    451 //    } else if (And * and2 = dyn_cast<And>(expr2)) {
    452 //        if (equals(and2->getOperand(0), expr1) || equals(and2->getOperand(1), expr1)) {
    453 //            return expr1;
    454 //        }
    455 //    }
    456 //    if (expr1 > expr2) {
    457 //        std::swap(expr1, expr2);
    458 //    }
    459 //    return insertAtInsertionPoint(new Or(expr1, expr2, makeName("or_")));
    460 //}
    461 
    462 //PabloAST * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
    463 //    assert (expr1 && expr2);
    464 //    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
    465 //        return renameNonNamedNode(expr2, std::move(prefix));
    466 //    }
    467 //    else if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
    468 //        return renameNonNamedNode(expr1, std::move(prefix));
    469 //    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    470 //        // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
    471 //        return createNot(createAnd(not1->getExpr(), createNot(expr2)), prefix);
    472 //    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    473 //        // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
    474 //        return createNot(createAnd(not2->getExpr(), createNot(expr1)), prefix);
    475 //    } else if (And * and1 = dyn_cast<And>(expr1)) {
    476 //        if (And * and2 = dyn_cast<And>(expr2)) {
    477 //            PabloAST * const expr1a = and1->getOperand(0);
    478 //            PabloAST * const expr1b = and1->getOperand(1);
    479 //            PabloAST * const expr2a = and2->getOperand(0);
    480 //            PabloAST * const expr2b = and2->getOperand(1);
    481 //            //These optimizations factor out common components that can occur when sets are formed by union
    482 //            //(e.g., union of [a-z] and [A-Z].
    483 //            if (equals(expr1a, expr2a)) {
    484 //                return createAnd(expr1a, createOr(expr1b, expr2b), prefix);
    485 //            } else if (equals(expr1b, expr2b)) {
    486 //                return createAnd(expr1b, createOr(expr1a, expr2a), prefix);
    487 //            } else if (equals(expr1a, expr2b)) {
    488 //                return createAnd(expr1a, createOr(expr1b, expr2a), prefix);
    489 //            } else if (equals(expr1b, expr2a)) {
    490 //                return createAnd(expr1b, createOr(expr1a, expr2b), prefix);
    491 //            }
    492 //        } else if (equals(and1->getOperand(0), expr2) || equals(and1->getOperand(1), expr2)) {
    493 //            // (a∧b) √ a = a
    494 //            return expr2;
    495 //        }
    496 //    } else if (And * and2 = dyn_cast<And>(expr2)) {
    497 //        if (equals(and2->getOperand(0), expr1) || equals(and2->getOperand(1), expr1)) {
    498 //            return expr1;
    499 //        }
    500 //    }
    501 //    if (expr1 > expr2) {
    502 //        std::swap(expr1, expr2);
    503 //    }
    504 //    return insertAtInsertionPoint(new Or(expr1, expr2, makeName(prefix, false)));
    505 //}
    506 
    507 //PabloAST * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2) {
    508 //    assert (expr1 && expr2);
    509 //    if (expr1 == expr2) {
    510 //        return PabloBlock::createZeroes();
    511 //    }
    512 //    if (isa<Ones>(expr1)) {
    513 //        return createNot(expr2);
    514 //    } else if (isa<Zeroes>(expr1)){
    515 //        return expr2;
    516 //    } else if (isa<Ones>(expr2)) {
    517 //        return createNot(expr1);
    518 //    } else if (isa<Zeroes>(expr2)){
    519 //        return expr1;
    520 //    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    521 //        if (Not * not2 = dyn_cast<Not>(expr2)) {
    522 //            return createXor(not1->getExpr(), not2->getExpr());
    523 //        }
    524 //    }
    525 //    if (expr1 > expr2) {
    526 //        std::swap(expr1, expr2);
    527 //    }
    528 //    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName("xor_")));
    529 //}
    530 
    531 //PabloAST * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
    532 //    assert (expr1 && expr2);
    533 //    if (expr1 == expr2) {
    534 //        return PabloBlock::createZeroes();
    535 //    }
    536 //    if (isa<Ones>(expr1)) {
    537 //        return createNot(expr2, prefix);
    538 //    } else if (isa<Zeroes>(expr1)){
    539 //        return expr2;
    540 //    } else if (isa<Ones>(expr2)) {
    541 //        return createNot(expr1, prefix);
    542 //    } else if (isa<Zeroes>(expr2)){
    543 //        return expr1;
    544 //    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    545 //        if (Not * not2 = dyn_cast<Not>(expr2)) {
    546 //            return createXor(not1->getExpr(), not2->getExpr(), prefix);
    547 //        }
    548 //    }
    549 //    if (expr1 > expr2) {
    550 //        std::swap(expr1, expr2);
    551 //    }
    552 //    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName(prefix, false)));
    553 //}
    554438
    555439/// TERNARY CREATE FUNCTION
     
    571455    } else if (equals(trueExpr, falseExpr)) {
    572456        return trueExpr;
    573     } else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getExpr(), falseExpr)) {
     457    } else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getOperand(0), falseExpr)) {
    574458        return createXor(condition, falseExpr);
    575     } else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getExpr())){
     459    } else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getOperand(0))){
    576460        return createXor(condition, falseExpr);
    577461    }
     
    599483        return createAnd(condition, trueExpr, prefix);
    600484    }
    601     else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getExpr(), falseExpr)) {
     485    else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getOperand(0), falseExpr)) {
    602486        return createXor(condition, falseExpr, prefix);
    603487    }
    604     else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getExpr())){
     488    else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getOperand(0))){
    605489        return createXor(condition, falseExpr, prefix);
    606490    }
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4878 r4885  
    105105    PabloAST * createAnd(PabloAST * expr1, PabloAST * expr2);
    106106
     107    PabloAST * createAnd(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
     108
    107109    And * createAnd(const unsigned operands, PabloAST * value);
    108110
    109     PabloAST * createAnd(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
     111    And * createAnd(std::vector<PabloAST *>::iterator begin, std::vector<PabloAST *>::iterator end) {
     112        return insertAtInsertionPoint(new And(begin, end, makeName("and_")));
     113    }
    110114
    111115    PabloAST * createNot(PabloAST * expr);
     
    115119    PabloAST * createOr(PabloAST * expr1, PabloAST * expr2);
    116120
     121    PabloAST * createOr(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
     122
     123    Or * createOr(std::vector<PabloAST *>::iterator begin, std::vector<PabloAST *>::iterator end) {
     124        return insertAtInsertionPoint(new Or(begin, end, makeName("or_")));
     125    }
     126
    117127    Or * createOr(const unsigned operands, PabloAST * value);
    118128
    119     PabloAST * createOr(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
    120 
    121129    PabloAST * createXor(PabloAST * expr1, PabloAST * expr2);
    122130
    123131    PabloAST * createXor(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
     132
     133    Xor * createXor(std::vector<PabloAST *>::iterator begin, std::vector<PabloAST *>::iterator end) {
     134        return insertAtInsertionPoint(new Xor(begin, end, makeName("xor_")));
     135    }
    124136
    125137    PabloAST * createMatchStar(PabloAST * marker, PabloAST * charclass);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r4880 r4885  
    77#include <boost/container/flat_map.hpp>
    88#include <boost/graph/adjacency_list.hpp>
     9
     10#include <pablo/printer_pablos.h>
     11#include <iostream>
    912
    1013using namespace boost;
     
    331334
    332335        block->setInsertPoint(cast<Variadic>(G[sinks.front()])->getPrevNode());
    333 
    334336        if (isa<And>(G[sinks.front()])) {
    335337            outerOp = block->createAnd(intermediary.size(), PabloBlock::createOnes());
     
    343345        for (const Vertex u : intermediary) {
    344346            for (const Vertex v : sinks) {
    345                 cast<Variadic>(G[v])->removeOperand(cast<Variadic>(G[u]));
     347                cast<Variadic>(G[v])->deleteOperand(G[u]);
    346348            }
    347349            outerOp->setOperand(i++, cast<Variadic>(G[u]));
     
    351353        for (const Vertex u : sources) {
    352354            for (const Vertex v : intermediary) {
    353                 cast<Variadic>(G[v])->removeOperand(G[u]);
     355                cast<Variadic>(G[v])->deleteOperand(G[u]);
    354356            }
    355357            innerOp->setOperand(i++, G[u]);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4880 r4885  
    2020using namespace boost::numeric::ublas;
    2121
    22 #define PRINT_DEBUG_OUTPUT
     22// #define PRINT_DEBUG_OUTPUT
    2323
    2424#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
     
    159159
    160160        AutoMultiplexing::topologicalSort(function);
    161 
    162161        #ifndef NDEBUG
    163162        PabloVerifier::verify(function, "post-multiplexing");
     
    469468    }
    470469
    471     const BDD Vk = bdd_ithvar(mVariables++);
    472 
    473     BDD Ck = Vk;
    474 
     470    const BDD Vk = bdd_addref(bdd_not(bdd_ithvar(mVariables++)));
     471    BDD Ck = bdd_one();
    475472    for (unsigned i = 0; i != k; ++i) {
    476473        const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
     
    478475        const BDD Vi = std::get<1>(mAdvanceAttributes[i]);
    479476        if (unconstrained[i]) {
    480             Ck = bdd_addref(bdd_imp(Ck, bdd_addref(bdd_not(Vi))));
    481             Ci = bdd_addref(bdd_imp(Ci, bdd_addref(bdd_not(Vk))));
    482             // If these Advances are mutually exclusive, in the same scope, and transitively independent,
    483             // we safely multiplex them.
     477            const BDD exclusionConstraint = bdd_addref(bdd_or(Vi, Vk));
     478            Ci = bdd_addref(bdd_and(Ci, exclusionConstraint));
     479            Ck = bdd_addref(bdd_and(Ck, exclusionConstraint));
     480            // If these Advances are mutually exclusive, in the same scope and transitively independent,
     481            // we can safely multiplex them. Otherwise mark the constraint edge in the graph.
    484482            if (adv->getParent() == ithAdv->getParent()) {
    485483                continue;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4880 r4885  
    1010#include <unordered_set>
    1111#endif
    12 #include <iostream>
    1312
    1413namespace pablo {
     
    2726bool Simplifier::optimize(PabloFunction & function) {
    2827    eliminateRedundantCode(function.getEntryBlock());
     28    #ifndef NDEBUG
     29    PabloVerifier::verify(function, "post-eliminate-redundant-code");
     30    #endif
    2931    deadCodeElimination(function.getEntryBlock());
     32    #ifndef NDEBUG
     33    PabloVerifier::verify(function, "post-dead-code-elimination");
     34    #endif
    3035    strengthReduction(function.getEntryBlock());
    3136    #ifndef NDEBUG
    32     PabloVerifier::verify(function, "post-simplification");
     37    PabloVerifier::verify(function, "post-strength-reduction");
    3338    #endif
    3439    return true;
     
    5964        for (unsigned i = 0; i != var->getNumOperands(); ++i) {
    6065            if (isa<Not>(var->getOperand(i))) {
    61                 // (A ⊕ ¬B) = ¬(A ⊕ B)
     66                // (A ⊕ ¬B) = (A ⊕ (B ⊕ 1)) = ¬(A ⊕ B)
    6267                var->setOperand(i, cast<Not>(var->getOperand(i))->getOperand(0));
    6368                negated = !negated;
     
    9095                const PabloAST * const negatedOp = cast<Not>(var->getOperand(i))->getOperand(0);
    9196                for (unsigned j = 0; j != var->getNumOperands(); ++j) {
    92                     if (LLVM_UNLIKELY(var->getOperand(j) == negatedOp)) {
     97                    if (LLVM_UNLIKELY(equals(var->getOperand(j), negatedOp))) {
    9398                        if (isa<And>(var)) { // (A ∧ ¬A) ∧ B = 0 for any B
    9499                            return PabloBlock::createZeroes();
     
    194199inline bool Simplifier::isSuperfluous(const Assign * const assign) {
    195200    for (const PabloAST * inst : assign->users()) {
    196         if (isa<Next>(inst) || isa<PabloFunction>(inst)) {
    197             return false;
    198         } else if (isa<If>(inst)) {
    199             const If * ifNode = cast<If>(inst);
    200             if (ifNode->getCondition() == assign) {
    201                 bool notFound = true;
    202                 for (Assign * defVar : ifNode->getDefined()) {
    203                     if (defVar == assign) {
    204                         notFound = false;
    205                         break;
    206                     }
    207                 }
    208                 if (notFound) {
    209                     continue;
    210                 }
    211             }
     201        if (isa<Next>(inst) || isa<PabloFunction>(inst) || (isa<If>(inst) && (cast<If>(inst)->getCondition() != assign))) {
    212202            return false;
    213203        }
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4880 r4885  
    1010#include <llvm/Support/Casting.h>
    1111#include <llvm/Support/Compiler.h>
     12#include <boost/iterator/iterator_facade.hpp>
     13#include <iterator>
     14#include <slab_allocator.h>
     15#include <type_traits>
     16#include <unordered_map>
    1217#include <vector>
    13 #include <slab_allocator.h>
    14 #include <iterator>
    15 #include <unordered_map>
    16 #include <boost/iterator/iterator_facade.hpp>
    1718
    1819using namespace llvm;
     
    233234            ++i;
    234235        }
    235     } 
     236    }
    236237    Statement(const ClassTypeId id, unsigned operands, PabloAST * value, const String * const name)
    237238    : PabloAST(id)
     
    248249        }
    249250    }
     251    template<typename iterator>
     252    explicit Statement(const ClassTypeId id, iterator begin, iterator end, const String * const name)
     253    : PabloAST(id)
     254    , mName(name)
     255    , mNext(nullptr)
     256    , mPrev(nullptr)
     257    , mParent(nullptr)
     258    , mOperands(std::distance(begin, end))
     259    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
     260        unsigned i = 0;
     261        for (auto value = begin; value != end; ++value, ++i) {
     262            assert (*value);
     263            mOperand[i] = *value;
     264            (*value)->addUser(this);
     265        }
     266    }
    250267private:
    251268    template <class ValueType, class ValueList>
     
    303320    PabloAST * removeOperand(const unsigned index);
    304321
    305     unsigned removeOperand(const PabloAST * const expr);
     322    bool deleteOperand(const PabloAST * const expr);
    306323
    307324    iterator begin() {
     
    330347    : Statement(id, operands, value, name)
    331348    , mCapacity(operands) {
     349
     350    }
     351    template<typename iterator>
     352    explicit Variadic(const ClassTypeId id, iterator begin, iterator end, String * name)
     353    : Statement(id, begin, end, name)
     354    , mCapacity(std::distance(begin, end)) {
    332355
    333356    }
     
    608631 * @brief removeOperand
    609632 ** ------------------------------------------------------------------------------------------------------------- */
    610 inline unsigned Variadic::removeOperand(const PabloAST * const expr) {
     633inline bool Variadic::deleteOperand(const PabloAST * const expr) {
    611634    for (unsigned i = 0; i != getNumOperands(); ++i) {
    612635        if (getOperand(i) == expr) {
    613636            removeOperand(i);
    614             return i;
    615         }
    616     }
    617     return -1;
     637            return true;
     638        }
     639    }
     640    return false;
    618641}
    619642
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp

    r4880 r4885  
    77#include <pablo/analysis/pabloverifier.hpp>
    88#include <pablo/optimizers/distributivepass.h>
    9 
     9#include <pablo/optimizers/codemotionpass.h>
    1010
    1111#include <pablo/printer_pablos.h>
     
    114114
    115115/** ------------------------------------------------------------------------------------------------------------- *
    116  * @brief removeCommonLiterals
     116 * @brief extractNegationsOutwards
    117117 ** ------------------------------------------------------------------------------------------------------------- */
    118 inline void FlattenAssociativeDFG::removeCommonLiterals(Assign * const def) {
    119     PabloAST * op = def->getOperand(0);
    120     if (isa<And>(op) || isa<Or>(op) || isa<Xor>(op)) {
    121         removeCommonLiterals(def, cast<Variadic>(op));
    122     }
    123 }
    124 
    125 /** ------------------------------------------------------------------------------------------------------------- *
    126  * @brief removeCommonLiterals
    127  ** ------------------------------------------------------------------------------------------------------------- */
    128 void FlattenAssociativeDFG::removeCommonLiterals(Statement * input, Variadic * var) {
    129     std::vector<PabloAST *> common(var->begin(), var->end());
    130     std::vector<PabloAST *> temp;
    131     temp.reserve(common.size());
    132     for (PabloAST * user : input->users()) {
    133         if (user->getClassTypeId() != var->getClassTypeId()) {
    134             if (isa<If>(user) && (input != cast<If>(user)->getCondition())) {
    135                 continue;
    136             }
    137             return;
    138         }
    139         std::set_intersection(common.begin(), common.end(), cast<Variadic>(user)->begin(), cast<Variadic>(user)->end(), std::back_inserter(temp));
    140         common.swap(temp);
    141         temp.clear();
    142     }
    143     for (PabloAST * op : common) {
    144         var->removeOperand(op);
    145     }
    146 }
    147 
    148 /** ------------------------------------------------------------------------------------------------------------- *
    149  * @brief removeCommonLiterals
    150  ** ------------------------------------------------------------------------------------------------------------- */
    151 inline void FlattenAssociativeDFG::removeCommonLiterals(PabloBlock * const block) {
     118inline void FlattenAssociativeDFG::extractNegationsOutwards(PabloBlock * const block) {
    152119    for (Statement * stmt : *block) {
    153120        if (isa<If>(stmt) || isa<While>(stmt)) {
    154             removeCommonLiterals(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    155         } else if (isa<And>(stmt) || isa<Or>(stmt)) {
    156             removeCommonLiterals(cast<Variadic>(stmt), cast<Variadic>(stmt));
    157         } else if (isa<Assign>(stmt)) {
    158             removeCommonLiterals(cast<Assign>(stmt));
    159         }
    160     }
    161 }
    162 
    163 /** ------------------------------------------------------------------------------------------------------------- *
    164  * @brief extract
    165  ** ------------------------------------------------------------------------------------------------------------- */
    166 inline void FlattenAssociativeDFG::extract(PabloBlock * const block) {
    167     for (Statement * stmt : *block) {
    168         if (isa<If>(stmt) || isa<While>(stmt)) {
    169             extract(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     121            extractNegationsOutwards(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    170122        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
    171123            extractNegationsOutwards(cast<Variadic>(stmt), block);
     
    175127
    176128/** ------------------------------------------------------------------------------------------------------------- *
    177  * @brief process
     129 * @brief transform
    178130 ** ------------------------------------------------------------------------------------------------------------- */
    179131void FlattenAssociativeDFG::transform(PabloFunction & function) {
    180132
    181     for (;;) {
     133    FlattenAssociativeDFG::flatten(function.getEntryBlock());
     134    #ifndef NDEBUG
     135    PabloVerifier::verify(function, "post-flatten");
     136    #endif
    182137
    183         FlattenAssociativeDFG::flatten(function.getEntryBlock());
    184         #ifndef NDEBUG
    185         PabloVerifier::verify(function, "post-flatten");
    186         #endif
    187         FlattenAssociativeDFG::removeCommonLiterals(function.getEntryBlock());
    188         #ifndef NDEBUG
    189         PabloVerifier::verify(function, "post-remove-common-literals");
    190         #endif
     138    Simplifier::optimize(function);
     139    DistributivePass::optimize(function);
    191140
    192         Simplifier::optimize(function);
     141    FlattenAssociativeDFG::extractNegationsOutwards(function.getEntryBlock());
     142    #ifndef NDEBUG
     143    PabloVerifier::verify(function, "post-extract-negations-outwards");
     144    #endif
    193145
    194         const bool distributed = DistributivePass::optimize(function);
    195 
    196         FlattenAssociativeDFG::extract(function.getEntryBlock());
    197         #ifndef NDEBUG
    198         PabloVerifier::verify(function, "post-extract");
    199         #endif
    200         Simplifier::optimize(function);
    201 
    202         if (distributed == 0) {
    203             break;
    204         }
    205     }
    206 
    207     if (DistributivePass::optimize(function)) {
    208         throw std::runtime_error("Some distributions remained!");
    209     }
     146    Simplifier::optimize(function);
    210147
    211148}
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.h

    r4880 r4885  
    2020    static void applyNegationInwards(Not * const var, PabloBlock * const block);
    2121
    22     static void removeCommonLiterals(PabloBlock * const block);
    23     static void removeCommonLiterals(Assign * const def);
    24     static void removeCommonLiterals(Statement * input, Variadic * var);
     22//    static void removeCommonLiterals(PabloBlock * const block);
     23//    static void removeCommonLiterals(Assign * const def);
     24//    static void removeCommonLiterals(Statement * const input, Variadic * const var);
    2525
    26     static void extract(PabloBlock * const block);
     26    static void extractNegationsOutwards(PabloBlock * const block);
    2727    static void extractNegationsOutwards(Variadic * const var, PabloBlock * const block);
    2828
  • icGREP/icgrep-devel/icgrep/pablo/pe_and.h

    r4878 r4885  
    3333
    3434    }
     35    template<typename iterator>
     36    And(iterator begin, iterator end, String * name)
     37    : Variadic(ClassTypeId::And, begin, end, name) {
     38
     39    }
    3540};
    3641
  • icGREP/icgrep-devel/icgrep/pablo/pe_or.h

    r4878 r4885  
    3333
    3434    }
     35    template<typename iterator>
     36    Or(iterator begin, iterator end, String * name)
     37    : Variadic(ClassTypeId::Or, begin, end, name) {
     38
     39    }
    3540};
    3641
  • icGREP/icgrep-devel/icgrep/pablo/pe_xor.h

    r4878 r4885  
    3333
    3434    }
     35    template<typename iterator>
     36    Xor(iterator begin, iterator end, String * name)
     37    : Variadic(ClassTypeId::Xor, begin, end, name) {
     38
     39    }
    3540};
    3641
  • icGREP/icgrep-devel/icgrep/toolchain.cpp

    r4878 r4885  
    3838#include <pablo/optimizers/codemotionpass.h>
    3939#include <pablo/passes/flattenassociativedfg.h>
     40#include <pablo/passes/factorizedfg.h>
    4041#ifdef ENABLE_MULTIPLEXING
    4142#include <pablo/optimizers/pablo_automultiplexing.hpp>
     
    8889                                        cl::desc("maximum number of selections from any partial candidate multiplexing set."),
    8990                                        cl::cat(cPabloOptimizationsOptions));
    90 
     91static cl::opt<bool> EnableLowering("lowering", cl::init(false),
     92                                         cl::desc("coalesce associative functions prior to optimization passes."),
     93                                         cl::cat(cPabloOptimizationsOptions));
    9194static cl::opt<bool> EnableReassociation("reassoc", cl::init(false),
    9295                                         cl::desc("perform reassocation and distribution law optimization."),
     
    133136        PabloPrinter::print(*function, cerr);
    134137    }
    135 #ifndef NDEBUG
     138    #ifndef NDEBUG
    136139    PabloVerifier::verify(*function, "creation");
    137 #endif
     140    #endif
    138141    return function;
    139142}
     
    144147        Simplifier::optimize(*function);
    145148    }
    146     // FlattenAssociativeDFG::transform(*function);
     149#ifdef ENABLE_MULTIPLEXING
     150    if (EnableLowering || EnableMultiplexing) {
     151        FlattenAssociativeDFG::transform(*function);
     152    }
     153#endif
    147154    if (PabloSinkingPass) {
    148155        CodeMotionPass::optimize(*function);
     
    150157#ifdef ENABLE_MULTIPLEXING   
    151158    if (EnableMultiplexing) {
    152         BDDMinimizationPass::optimize(*function);
     159        // BDDMinimizationPass::optimize(*function);
    153160        AutoMultiplexing::optimize(*function, MultiplexingSetLimit, MultiplexingSelectionLimit);
     161        FlattenAssociativeDFG::transform(*function);
    154162    }
    155163    if (EnableReassociation) {
     
    157165    }
    158166#endif
     167    if (EnableLowering || EnableMultiplexing) {
     168        FactorizeDFG::transform(*function);
     169    }
    159170    if (PrintOptimizedREcode) {
    160171        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
Note: See TracChangeset for help on using the changeset viewer.