Ignore:
Timestamp:
Jun 3, 2015, 11:43:51 PM (4 years ago)
Author:
nmedfort
Message:

More multiplexing work; passes make check.

Location:
icGREP/icgrep-devel/icgrep
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4590 r4592  
    6363                                      cl::cat(cPabloOptimizationsOptions));
    6464#ifdef ENABLE_MULTIPLEXING
    65 static cl::opt<bool> PabloMutualExclusionPass("mutual-exclusion", cl::init(true),
    66                                       cl::desc("Multiplex Advances whose inputs are mutual exclusive and replaces any contradictory stream with Zero."),
     65static cl::opt<bool> PabloMutualExclusionPass("mutual-exclusion", cl::init(false),
     66                                      cl::desc("Multiplex Advances whose inputs are mutual exclusive and replace any contradictory stream with Zero."),
    6767                                      cl::cat(cPabloOptimizationsOptions));
    6868#endif
     
    171171    #ifdef ENABLE_MULTIPLEXING
    172172    if (PabloMutualExclusionPass) {
    173         if (PrintCompiledREcode) {
    174             //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
    175             llvm::raw_os_ostream cerr(std::cerr);
    176             cerr << "Pre-Multiplexing Pablo AST:\n";
    177             PabloPrinter::print(main.statements(), cerr);
    178         }
    179173        AutoMultiplexing::optimize(basisBits, main);
    180174    }
  • icGREP/icgrep-devel/icgrep/icgrep-devel.includes

    r4586 r4592  
    55pablo/analysis
    66pablo/optimizers
    7 ../cudd-2.5.1
     7../cudd-2.5.1/cudd
     8../cudd-2.5.1/util
    89UCD
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4590 r4592  
    11#include "pablo_automultiplexing.hpp"
    22#include <pablo/codegenstate.h>
    3 #include <llvm/ADT/SmallVector.h>
    4 #include <llvm/ADT/DenseMap.h>
    5 #include <llvm/ADT/DenseSet.h>
    63#include <llvm/ADT/BitVector.h>
    74#include <stack>
     
    1310#include <boost/circular_buffer.hpp>
    1411#include <include/simd-lib/builtins.hpp>
    15 // #include <pablo/expression_map.hpp>
     12#include <pablo/expression_map.hpp>
    1613#include <pablo/printer_pablos.h>
    1714#include <iostream>
     
    4037        am.topologicalSort(entry);
    4138    }
    42 
    4339}
    4440
     
    191187
    192188    // Map the predefined 0/1 entries
    193     mCharacterizationMap.emplace(entry.createZeroes(), Cudd_ReadZero(mManager));
    194     mCharacterizationMap.emplace(entry.createOnes(), Cudd_ReadOne(mManager));
     189    mCharacterizationMap.emplace(entry.createZeroes(), Zero());
     190    mCharacterizationMap.emplace(entry.createOnes(), One());
    195191
    196192    // Order the variables so the input Vars are pushed to the end; they ought to
     
    258254                    // an operand of a Statement. Instead it updates the Initial operand's value.
    259255                    testContradiction = false;
    260                 case PabloAST::ClassTypeId::Or:
     256                case PabloAST::ClassTypeId::Or:           
    261257                    bdd = Or(input[0], input[1]);
    262258                    break;
     
    276272                case PabloAST::ClassTypeId::MatchStar:
    277273                    if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
    278                         bdd = Cudd_ReadZero(mManager);
     274                        bdd = Zero();
    279275                        break;
    280276                    }
     
    286282                    assert (stmt == mAdvance[advances.size()]);
    287283                    if (LLVM_UNLIKELY(isZero(input[0]))) {
    288                         bdd = Cudd_ReadZero(mManager);
    289                         // mark this advance as having an input and output of 0
     284                        bdd = input[0];
    290285                        advances.emplace_back(bdd, bdd);
    291286                    }
     
    360355                    break;
    361356                default:
    362                     throw std::runtime_error("Unexpected statement " + stmt->getName()->to_string());
     357                    throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
    363358            }
    364359            assert ("Failed to generate a BDD." && (bdd || !(testContradiction || updateVariable)));
    365             if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) {
    366                 // std::cerr << stmt->getName()->to_string() << " = âˆ
    367 "  << std::endl;
    368                 Cudd_RecursiveDeref(mManager, bdd);               
    369                 stmt = stmt->replaceWith(entry.createZeroes());
    370             }
    371             else if (LLVM_LIKELY(updateVariable)) {
     360            if (LLVM_LIKELY(updateVariable)) {
    372361                mCharacterizationMap[stmt] = bdd;
     362            }
     363            if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) {               
     364                if (!isa<Assign>(stmt) || cast<Assign>(stmt)->superfluous()) {
     365                    Cudd_RecursiveDeref(mManager, bdd);
     366                    stmt = stmt->replaceWith(entry.createZeroes());
     367                    continue;
     368                }
    373369            }
    374370            stmt = stmt->getNextNode();
     
    387383 ** ------------------------------------------------------------------------------------------------------------- */
    388384
     385inline DdNode * AutoMultiplexing::Zero() const {
     386    DdNode * r = Cudd_ReadLogicZero(mManager);
     387    Cudd_Ref(r);
     388    return r;
     389}
     390
     391inline DdNode * AutoMultiplexing::One() const {
     392    DdNode * r = Cudd_ReadOne(mManager);
     393    Cudd_Ref(r);
     394    return r;
     395}
     396
    389397inline bool AutoMultiplexing::isZero(DdNode * x) const {
    390     return x == Cudd_ReadZero(mManager);
     398    return x == Cudd_ReadLogicZero(mManager);
    391399}
    392400
     
    420428
    421429inline bool AutoMultiplexing::noSatisfyingAssignment(DdNode * x) {
    422     // TODO: since we're only interested in knowing whether there is no such cube,
    423     // write an optimized function for that if one does not exist.
    424     int* cube;
    425     CUDD_VALUE_TYPE dummy;
    426     auto gen = Cudd_FirstCube(mManager, x, &cube, &dummy);
    427     bool r = Cudd_IsGenEmpty(gen);
    428     Cudd_GenFree(gen);
    429     return r;
     430    return Cudd_bddLeq(mManager, x, Cudd_ReadLogicZero(mManager));
    430431}
    431432
     
    435436
    436437/** ------------------------------------------------------------------------------------------------------------- *
    437  * @brief createMappingGraph
     438 * @brief createMultiplexSetGraph
    438439 ** ------------------------------------------------------------------------------------------------------------- */
    439440void AutoMultiplexing::createMultiplexSetGraph() {
     
    498499    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
    499500
    500     // Question: should we enumerate the power set of S?
     501    // TODO: Instead of building a graph, construct a trie of all members in the powerset of S that are of size
     502    // >= 3 and not 2^n for any n.
    501503
    502504    const auto v = add_vertex(mMultiplexSetGraph);
     
    735737}
    736738
    737 
    738 static inline size_t smallest_multiplexed_set(const size_t x) {
    739     return std::log2<size_t>(x) + 1; // use a faster builtin function for this?
    740 }
    741 
     739/** ------------------------------------------------------------------------------------------------------------- *
     740 * @brief compute_m
     741 ** ------------------------------------------------------------------------------------------------------------- */
     742static inline size_t compute_m(const size_t n) {
     743    return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
     744}
     745
     746struct CreateOr {
     747    CreateOr(PabloBlock * pb) : mPb(pb) {}
     748    PabloAST * operator() (PabloAST * x, PabloAST * y) { return mPb->createOr(x, y); }
     749    PabloBlock * mPb;
     750};
     751
     752struct CreateAnd {
     753    CreateAnd(PabloBlock * pb) : mPb(pb) {}
     754    PabloAST * operator() (PabloAST * x, PabloAST * y) { return mPb->createAnd(x, y); }
     755    PabloBlock * mPb;
     756};
    742757
    743758/** ------------------------------------------------------------------------------------------------------------- *
     
    754769        max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
    755770    }
    756     const size_t max_m = smallest_multiplexed_set(max_n);
     771    const size_t max_m = compute_m(max_n);
    757772
    758773    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
     
    768783        if (n) {
    769784
    770             const size_t m = smallest_multiplexed_set(n);
     785            const size_t m = compute_m(n);
    771786
    772787            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
     
    794809            #endif
    795810
     811            ExpressionMap<PabloAST *, PabloAST *> expMap(nullptr);
     812
    796813            /// Perform n-to-m Multiplexing
    797814            for (size_t j = 0; j != m; ++j) {
     
    799816                assert (Q.empty());
    800817
    801                 std::stringstream name;
    802                 name << "mux";
     818                std::ostringstream prefix;
     819
     820                prefix << "mux";
    803821                for (size_t i = 1; i <= n; ++i) {
    804822                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
    805823                        assert (!Q.full());
    806824                        PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
     825                        prefix << '_' << V[i - 1]->getName()->to_string();
    807826                        Q.push_back(tmp);
    808                         name << "_" << V[i - 1]->getName()->to_string();
    809827                    }
    810828                }
     
    821839                    assert (!Q.full());
    822840                    pb->setInsertPoint(choose(a2, a1, adv));
    823                     PabloAST * tmp = pb->createOr(a1, a2); assert (tmp);
     841                    CreateOr createOr(pb);
     842                    PabloAST * tmp = expMap.findOrCall(createOr, PabloAST::ClassTypeId::Or, a1, a2); assert (tmp);
    824843                    Q.push_back(tmp);
    825844                }
     
    827846
    828847                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
    829                 muxed[j] = pb->createAdvance(mux, adv->getOperand(1), name.str());
     848                muxed[j] = pb->createAdvance(mux, adv->getOperand(1), prefix.str());
    830849            }
    831850
     
    836855
    837856                Advance * const adv = V[i - 1];
     857
     858                pb->setInsertPoint(adv);
    838859
    839860                assert (Q.empty());
     
    850871                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    851872                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    852                         pb->setInsertPoint(choose(a2, a1, adv));
    853873                        assert (!Q.full());
    854                         PabloAST * tmp = pb->createOr(a1, a2); assert (tmp);
     874                        CreateOr createOr(pb);
     875                        PabloAST * tmp = expMap.findOrCall(createOr, PabloAST::ClassTypeId::Or, a1, a2); assert (tmp);
    855876                        Q.push_back(tmp);
    856877                    }
     
    870891                assert (Q.size() >= 1);
    871892
    872                 while (Q.size() > (1 + ((neg == nullptr) ? 1 : 0))) {
     893                while (Q.size() > 1) {
    873894                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    874895                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    875 
    876896                    assert (!Q.full());
    877                     PabloAST * tmp = pb->createAnd(a1, a2); assert (tmp);
     897                    CreateAnd createAnd(pb);
     898                    PabloAST * tmp = expMap.findOrCall(createAnd, PabloAST::ClassTypeId::And, a1, a2); assert (tmp);
    878899                    Q.push_back(tmp);
    879900                }
    880901
    881                 assert (Q.size() >= 0 && Q.size() <= 2);
    882 
    883                 PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    884                 PabloAST * a2 = neg;
    885                 if (LLVM_UNLIKELY(neg == nullptr)) {
    886                     a2 = Q.front(); Q.pop_front(); assert (a2);
    887                 }
    888                 assert (Q.empty());
    889 
    890                 pb->setInsertPoint(choose(a2, a1, adv));
    891                 PabloAST * demux = pb->createAnd(a1, a2, "demux_" + V[i - 1]->getName()->to_string());
    892 
    893                 V[i - 1]->replaceWith(demux, false);
     902                assert (Q.size() == 1);
     903
     904                PabloAST * demux = Q.front(); Q.pop_front(); assert (demux);
     905                if (LLVM_LIKELY(neg != nullptr)) {
     906                    CreateAnd createAnd(pb);
     907                    demux = expMap.findOrCall(createAnd, PabloAST::ClassTypeId::And, demux, neg); assert (demux);
     908                }
     909                V[i - 1]->replaceWith(demux, true, true);
    894910            }
    895911        }
     
    910926    std::unordered_set<const PabloAST *> encountered;
    911927    std::stack<Statement *> scope;
    912     for (Statement * stmt = entry.front(); ; ) {
    913 restart:while ( stmt ) {
     928    for (Statement * stmt = entry.front(); ; ) { restart:
     929        while ( stmt ) {
    914930            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    915931                PabloAST * const op = stmt->getOperand(i);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4586 r4592  
    5555    }
    5656private:
     57    DdNode * Zero() const;
     58    DdNode * One() const;
    5759    bool isZero(DdNode * x) const;
    5860    DdNode * And(DdNode * x, DdNode * y);
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4586 r4592  
    9898}
    9999
    100 
    101 
    102100void Statement::setOperand(const unsigned index, PabloAST * const value) {
    103101    assert (value);
     
    113111    unsigned count = 0;
    114112    for (unsigned i = 0; i != getNumOperands(); ++i) {
    115         count += (getOperand(index) == priorValue) ? 1 : 0;
     113        count += (getOperand(i) == priorValue) ? 1 : 0;
    116114    }
    117115    assert (count >= 1);
     
    175173            mNext->mPrev = mPrev;
    176174        }
    177     }   
     175    }
    178176    mPrev = nullptr;
    179177    mNext = nullptr;
     
    183181
    184182Statement * Statement::eraseFromParent(const bool recursively) {
    185 
    186183    // remove this statement from its operands' users list
    187184    for (auto i = 0; i != mOperands; ++i) {
    188         PabloAST * const op = mOperand[i];
    189         op->removeUser(this);
    190     }
    191 
     185        mOperand[i]->removeUser(this);
     186    }
    192187    if (recursively) {
    193188        for (auto i = 0; i != mOperands; ++i) {
     
    212207        }
    213208    }
    214     replaceAllUsesWith(expr);
     209    replaceAllUsesWith(expr);   
    215210    return eraseFromParent(recursively);
    216211}
Note: See TracChangeset for help on using the changeset viewer.