Ignore:
Timestamp:
Jul 23, 2015, 4:47:59 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check in.

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

Legend:

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

    r4686 r4692  
    6161endif()
    6262
    63 SET(PABLO_SRC pablo/pabloAST.cpp pablo/ps_if.cpp pablo/ps_while.cpp pablo/function.cpp pablo/codegenstate.cpp pablo/builder.cpp pablo/symbol_generator.cpp pablo/printer_pablos.cpp pablo/pablo_compiler.cpp pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/pablo_codesinking.cpp pablo/carry_data.cpp pablo/carry_manager.cpp IDISA/idisa_builder.cpp)
     63SET(PABLO_SRC pablo/pabloAST.cpp pablo/ps_if.cpp pablo/ps_while.cpp pablo/function.cpp pablo/codegenstate.cpp pablo/builder.cpp pablo/symbol_generator.cpp pablo/carry_data.cpp pablo/printer_pablos.cpp)
     64SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_compiler.cpp pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/pablo_codesinking.cpp pablo/optimizers/booleanreassociationpass.cpp pablo/carry_manager.cpp IDISA/idisa_builder.cpp)
    6465IF (ENABLE_MULTIPLEXING)
    6566SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_automultiplexing.cpp)
     
    8687MESSAGE("Disabling predefined UCD functions...")
    8788ELSE()
     89
    8890# add the executable
    8991add_executable(generate_predefined_ucd_functions generate_predefined_ucd_functions.cpp)
     
    104106  VERBATIM)
    105107
    106 add_custom_target(run_generate_predefined_ucd_functions ALL DEPENDS ${PRECOMPILED_FILES})
     108add_custom_target(run_generate_predefined_ucd_functions DEPENDS ${PRECOMPILED_FILES})
    107109
    108110add_dependencies(RegExpCompiler run_generate_predefined_ucd_functions)
  • icGREP/icgrep-devel/icgrep/generate_predefined_ucd_functions.cpp

    r4686 r4692  
    293293    #else
    294294    PM.add(new DataLayoutPass());
    295     #endif
    296     // PM.add(createDependenceAnalysisPass());
     295    #endif   
    297296    PM.add(createReassociatePass());
    298297    PM.add(createInstructionCombiningPass());
     
    306305
    307306    PM.run(*module);
     307
    308308
    309309    out->keep();
     
    320320    InitializeAllAsmParsers();
    321321    cl::ParseCommandLineOptions(argc, argv, "UCD Compiler\n");
     322
     323
     324
     325
    322326    #ifdef ENABLE_MULTIPLEXING
    323327    if (MultiplexingDistribution.length() > 0) {
  • icGREP/icgrep-devel/icgrep/pablo/builder.cpp

    r4683 r4692  
    88        return mPb->NAME(arg); \
    99    } \
    10     inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
    11 private: \
    12     PabloBlock * mPb; \
    13 }; \
    14 __##NAME functor(mPb); \
    15 PabloAST * result = mExprTable.findUnaryOrCall(std::move(functor), TYPE, ARGS)
    16 
    17 #define MAKE_NAMED_UNARY(NAME, TYPE, ARGS...) \
    18 struct __##NAME { \
    1910    inline PabloAST * operator()(PabloAST * arg, const std::string name) { \
    2011        return mPb->NAME(arg, name); \
     
    2718PabloAST * result = mExprTable.findUnaryOrCall(std::move(functor), TYPE, ARGS)
    2819
    29 #define MAKE_UNARY_VARIABLE(NAME, TYPE, ARGS...) \
    30 struct __##NAME { \
    31     inline PabloAST * operator()(PabloAST * arg, const std::vector<PabloAST *> & args) { \
    32         return mPb->NAME(arg, args); \
    33     } \
    34     inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
    35 private: \
    36     PabloBlock * mPb; \
    37 }; \
    38 __##NAME functor(mPb); \
    39 PabloAST * result = mExprTable.findUnaryVariableOrCall(std::move(functor), TYPE, ARGS)
    40 
    41 
    4220#define MAKE_BINARY(NAME, TYPE, ARGS...) \
    4321struct __##NAME { \
     
    4523        return mPb->NAME(arg1, arg2); \
    4624    } \
    47     inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
    48 private: \
    49     PabloBlock * mPb; \
    50 }; \
    51 __##NAME functor(mPb); \
    52 PabloAST * result = mExprTable.findBinaryOrCall(std::move(functor), TYPE, ARGS)
    53 
    54 #define MAKE_NAMED_BINARY(NAME, TYPE, ARGS...) \
    55 struct __##NAME { \
    5625    inline PabloAST * operator()(PabloAST * arg1, PabloAST * arg2, const std::string name) { \
    5726        return mPb->NAME(arg1, arg2, name); \
     
    6433PabloAST * result = mExprTable.findBinaryOrCall(std::move(functor), TYPE, ARGS)
    6534
     35
    6636#define MAKE_TERNARY(NAME, TYPE, ARGS...) \
    6737struct __##NAME { \
     
    6939        return mPb->NAME(arg1, arg2, arg3); \
    7040    } \
    71     inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
    72 private: \
    73     PabloBlock * mPb; \
    74 }; \
    75 __##NAME functor(mPb); \
    76 PabloAST * result = mExprTable.findTernaryOrCall(std::move(functor), TYPE, ARGS)
    77 
    78 #define MAKE_NAMED_TERNARY(NAME, TYPE, ARGS...) \
    79 struct __##NAME { \
    8041    inline PabloAST * operator()(PabloAST * arg1, PabloAST * arg2, PabloAST * arg3, const std::string name) { \
    8142        return mPb->NAME(arg1, arg2, arg3, name); \
     
    8849PabloAST * result = mExprTable.findTernaryOrCall(std::move(functor), TYPE, ARGS)
    8950
    90 #define MAKE_VARIABLE(NAME, TYPE, ARGS) \
     51#define MAKE_VARIABLE(NAME, TYPE, ARGS...) \
    9152struct __##NAME { \
    92     inline PabloAST * operator()(PabloAST * arg) { \
    93         return mPb->NAME(arg); \
     53    inline PabloAST * operator()(const std::vector<PabloAST *> & args, PabloAST * prototype) { \
     54        return mPb->NAME(prototype, args); \
    9455    } \
    9556    inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
     
    9859}; \
    9960__##NAME functor(mPb); \
    100 PabloAST * result = mExprTable.findUnaryOrCall(std::move(functor), TYPE, ARGS)
     61PabloAST * result = mExprTable.findVariableOrCall(std::move(functor), TYPE, ARGS)
    10162
    102 
    103 Call * PabloBuilder::createCall(Prototype * prototype, const std::vector<Var *> & args) {
     63Call * PabloBuilder::createCall(Prototype * prototype, const std::vector<PabloAST *> & args) {
     64    if (prototype == nullptr) {
     65        throw std::runtime_error("Call object cannot be created with a Null prototype!");
     66    }
    10467    if (args.size() != cast<Prototype>(prototype)->getNumOfParameters()) {
    10568        throw std::runtime_error("Invalid number of arguments passed into Call object!");
    10669    }
    107     MAKE_UNARY_VARIABLE(createCall, PabloAST::ClassTypeId::Call, prototype, reinterpret_cast<const std::vector<PabloAST *> &>(args));
     70    MAKE_VARIABLE(createCall, PabloAST::ClassTypeId::Call, prototype->getName(), args, prototype);
    10871    return cast<Call>(result);
    10972}
     
    11578
    11679PabloAST * PabloBuilder::createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix) {
    117     MAKE_NAMED_BINARY(createAdvance, PabloAST::ClassTypeId::Advance, expr, shiftAmount, prefix);
     80    MAKE_BINARY(createAdvance, PabloAST::ClassTypeId::Advance, expr, shiftAmount, prefix);
    11881    return result;
    11982}
     
    12588
    12689PabloAST * PabloBuilder::createNot(PabloAST * expr, const std::string prefix) {
    127     MAKE_NAMED_UNARY(createNot, PabloAST::ClassTypeId::Not, expr, prefix);
     90    MAKE_UNARY(createNot, PabloAST::ClassTypeId::Not, expr, prefix);
    12891    return result;
    12992}
     
    141104        std::swap(expr1, expr2);
    142105    }
    143     MAKE_NAMED_BINARY(createAnd, PabloAST::ClassTypeId::And, expr1, expr2, prefix);
     106    MAKE_BINARY(createAnd, PabloAST::ClassTypeId::And, expr1, expr2, prefix);
    144107    return result;
    145108}
     
    157120        std::swap(expr1, expr2);
    158121    }
    159     MAKE_NAMED_BINARY(createOr, PabloAST::ClassTypeId::Or, expr1, expr2, prefix);
     122    MAKE_BINARY(createOr, PabloAST::ClassTypeId::Or, expr1, expr2, prefix);
    160123    return result;
    161124}
     
    173136        std::swap(expr1, expr2);
    174137    }
    175     MAKE_NAMED_BINARY(createXor, PabloAST::ClassTypeId::Xor, expr1, expr2, prefix);
     138    MAKE_BINARY(createXor, PabloAST::ClassTypeId::Xor, expr1, expr2, prefix);
    176139    return result;
    177140}
     
    183146
    184147PabloAST * PabloBuilder::createMatchStar(PabloAST * marker, PabloAST * charclass, const std::string prefix) {
    185     MAKE_NAMED_BINARY(createMatchStar, PabloAST::ClassTypeId::MatchStar, marker, charclass, prefix);
     148    MAKE_BINARY(createMatchStar, PabloAST::ClassTypeId::MatchStar, marker, charclass, prefix);
    186149    return result;
    187150}
     
    193156
    194157PabloAST * PabloBuilder::createScanThru(PabloAST * from, PabloAST * thru, const std::string prefix) {
    195     MAKE_NAMED_BINARY(createScanThru, PabloAST::ClassTypeId::ScanThru, from, thru, prefix);
     158    MAKE_BINARY(createScanThru, PabloAST::ClassTypeId::ScanThru, from, thru, prefix);
    196159    return result;
    197160}
     
    204167
    205168PabloAST * PabloBuilder::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string prefix) {
    206     MAKE_NAMED_TERNARY(createSel, PabloAST::ClassTypeId::Sel, condition, trueExpr, falseExpr, prefix);
     169    MAKE_TERNARY(createSel, PabloAST::ClassTypeId::Sel, condition, trueExpr, falseExpr, prefix);
    207170    return result;
    208171}
  • icGREP/icgrep-devel/icgrep/pablo/builder.hpp

    r4683 r4692  
    5151    }
    5252
    53     Call * createCall(Prototype * prototype, const std::vector<Var *> & vars);
     53    inline Call * createCall(Prototype * prototype, const std::vector<Var *> & args) {
     54        return createCall(prototype, reinterpret_cast<const std::vector<PabloAST *> &>(args));
     55    }
     56
     57    Call * createCall(Prototype * prototype, const std::vector<PabloAST *> &vars);
    5458
    5559    Assign * createAssign(const std::string && prefix, PabloAST * expr) {
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp

    r4691 r4692  
    420420#endif
    421421        PHINode * phi = mCarryOutAccumPhis[index];
     422        assert (phi);
     423        assert (mCarryOutVector[index]);
    422424        Value * carryOut = mBuilder->CreateOr(phi, mCarryOutVector[index]);
    423425        phi->addIncoming(carryOut, whileBodyFinalBlock);
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r4687 r4692  
    7272}
    7373
    74 Call * PabloBlock::createCall(PabloAST * prototype, const std::vector<PabloAST *> & args) {
     74Call * PabloBlock::createCall(PabloAST * prototype, const std::vector<PabloAST *> &) {
    7575    assert (prototype);
    76     if (prototype == nullptr) {
    77         throw std::runtime_error("Call object cannot be created with a Null prototype!");
    78     }
    79     if (args.size() != cast<Prototype>(prototype)->getNumOfParameters()) {
    80         throw std::runtime_error("Invalid number of arguments passed into Call object!");
    81     }
    8276    return insertAtInsertionPoint(new Call(prototype));
    8377}
     78
    8479
    8580PabloAST * PabloBlock::createNot(PabloAST * expr) {
     
    176171        }
    177172    }
    178     if (isa<Not>(expr1)) {
     173    if (isa<Not>(expr1) || expr1 > expr2) {
    179174        std::swap(expr1, expr2);
    180175    }
     
    204199        }
    205200    }
    206     if (isa<Not>(expr1)) {
     201    if (isa<Not>(expr1) || expr1 > expr2) {
    207202        std::swap(expr1, expr2);
    208203    }
     
    251246        }
    252247    }
     248    if (expr1 > expr2) {
     249        std::swap(expr1, expr2);
     250    }
    253251    return insertAtInsertionPoint(new Or(expr1, expr2, makeName("or_")));
    254252}
     
    292290        }
    293291    }
     292    if (expr1 > expr2) {
     293        std::swap(expr1, expr2);
     294    }
    294295    return insertAtInsertionPoint(new Or(expr1, expr2, makeName(prefix, false)));
    295296}
     
    314315        }
    315316    }
     317    if (expr1 > expr2) {
     318        std::swap(expr1, expr2);
     319    }
    316320    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName("xor_")));
    317321}
     
    336340        }
    337341    }
     342    if (expr1 > expr2) {
     343        std::swap(expr1, expr2);
     344    }
    338345    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName(prefix, false)));
    339346}
     
    343350PabloAST * PabloBlock::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
    344351    assert (condition && trueExpr && falseExpr);
    345 
    346352    if (isa<Ones>(condition)) {
    347353        return trueExpr;
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4687 r4692  
    8080    }
    8181
     82    inline Call * createCall(Prototype * prototype, const std::vector<PabloAST *> & args) {
     83        if (prototype == nullptr) {
     84            throw std::runtime_error("Call object cannot be created with a Null prototype!");
     85        }
     86        if (args.size() != cast<Prototype>(prototype)->getNumOfParameters()) {
     87            throw std::runtime_error("Invalid number of arguments passed into Call object!");
     88        }
     89        return createCall(static_cast<PabloAST *>(prototype), args);
     90    }
     91
    8292    Assign * createAssign(const std::string && prefix, PabloAST * expr);
    8393
     
    168178
    169179protected:
    170 
    171180
    172181    PabloBlock(SymbolGenerator & symbolGenerator);
     
    187196        return expr;
    188197    }
     198
    189199private:
    190200
    191     Call * createCall(PabloAST * prototype, const std::vector<PabloAST *> & args);
     201    Call * createCall(PabloAST * prototype, const std::vector<PabloAST *> &);
    192202
    193203    Var * createVar(PabloAST * name);
  • icGREP/icgrep-devel/icgrep/pablo/expression_map.hpp

    r4684 r4692  
    9898    friend struct ExpressionTable;
    9999
     100    using Allocator = LLVMAllocator;
     101
    100102    struct Key {
    101         inline Key(PabloAST::ClassTypeId type, unsigned args, PabloAST ** arg) : mType(type), mArgs(args), mArg(arg) {}
     103
     104        inline Key(PabloAST::ClassTypeId type, const PabloAST * arg1, const std::vector<PabloAST *> & args, Allocator & allocator)
     105        : mType(type)
     106        , mArgs(1 + args.size())
     107        , mArg(allocator.Allocate<const PabloAST *>(mArgs)) {
     108            unsigned i = 1;
     109            mArg[0] = arg1;
     110            for (PabloAST * arg : args) {
     111                mArg[i++] = arg;
     112            }
     113        }
     114
    102115        inline Key(const Key & key) = default;
     116
    103117        inline Key(Key && key) = default;
     118
    104119        inline bool operator < (const Key & other) const {
    105             if (mType != other.mType)
     120            if (mType != other.mType) {
    106121                return mType < other.mType;
    107             if (mArgs != other.mArgs)
     122            } else if (mArgs != other.mArgs) {
    108123                return mArgs < other.mArgs;
     124            }
    109125            for (unsigned i = 0; i != mArgs; ++i) {
    110126                if (mArg[i] != other.mArg[i]) {
     
    114130            return false;
    115131        }
    116     private:
    117         PabloAST::ClassTypeId         mType;
    118         unsigned                      mArgs;
    119         PabloAST **                   mArg;
     132
     133        const PabloAST::ClassTypeId   mType;
     134        const unsigned                mArgs;
     135        const PabloAST **             mArg;
    120136    };
    121137
    122     using Allocator = LLVMAllocator;
    123     using MapAllocator = LLVMAllocatorProxy<std::pair<Key, PabloAST *>>;
    124     using Map = std::map<Key, PabloAST *>; // , std::less<Key>, MapAllocator
     138    using Map = std::map<Key, PabloAST *>;
    125139
    126140    explicit VarArgMap(VarArgMap * predecessor = nullptr)
     
    142156
    143157    template <class Functor, typename... Params>
    144     inline PabloAST * findOrCall(Functor && functor, const PabloAST::ClassTypeId type, std::initializer_list<PabloAST *> args, Params... params) {
    145         PabloAST * const f = find(type, args);
     158    inline PabloAST * findOrCall(Functor && functor, const PabloAST::ClassTypeId type, const PabloAST * arg1, const std::vector<PabloAST *> & args, Params... params) {
     159        Key key(type, arg1, args, mAllocator);
     160        PabloAST * const f = find(key);
    146161        if (f) {
     162            mAllocator.Deallocate<const PabloAST *>(key.mArg);
    147163            return f;
    148164        }
    149165        PabloAST * const object = functor(args, std::forward<Params>(params)...);
    150         PabloAST ** const args_copy = mAllocator.Allocate<PabloAST *>(args.size());
    151         std::copy(args.begin(), args.end(), args_copy);
    152         Key key(type, args.size(), args_copy);
    153166        mMap.insert(std::make_pair(std::move(key), object));
    154167        return object;
    155168    }
    156169
    157     inline std::pair<PabloAST *, bool> findOrAdd(PabloAST * object, const PabloAST::ClassTypeId type, std::initializer_list<PabloAST *> args) {
    158         PabloAST * const entry = find(type, args);
     170    inline std::pair<PabloAST *, bool> findOrAdd(PabloAST * object, const PabloAST::ClassTypeId type, PabloAST * arg1, const std::vector<PabloAST *> & args) {
     171        Key key(type, arg1, args, mAllocator);
     172        PabloAST * const entry = find(key);
    159173        if (entry) {
     174            mAllocator.Deallocate<const PabloAST *>(key.mArg);
    160175            return std::make_pair(entry, false);
    161176        }
    162         PabloAST ** const args_copy = mAllocator.Allocate<PabloAST *>(args.size());
    163         std::copy(args.begin(), args.end(), args_copy);
    164         Key key(type, args.size(), args_copy);
    165177        mMap.insert(std::make_pair(std::move(key), object));
    166178        return std::make_pair(object, true);
    167179    }
    168180
    169     inline PabloAST * find(const PabloAST::ClassTypeId type, const std::initializer_list<PabloAST *> args) const {
    170         PabloAST * value[args.size()];
    171         std::copy(args.begin(), args.end(), value);
    172         return find(std::move(Key(type, args.size(), value)));
    173     }
    174 
    175 private:
    176 
    177     inline PabloAST * find(Key && key) const {
     181private:
     182
     183    inline PabloAST * find(const Key & key) const {
    178184        // check this map to see if we have it
    179185        auto itr = mMap.find(key);
     
    196202private:
    197203    VarArgMap *     mPredecessor;
     204    Map             mMap;
    198205    Allocator       mAllocator;
    199     Map             mMap;
    200206};
    201207
     
    207213            mBinary.mPredecessor = &(predecessor->mBinary);
    208214            mTernary.mPredecessor = &(predecessor->mTernary);
    209             mUnaryVariable.mPredecessor = &(predecessor->mUnaryVariable);
     215            mVariable.mPredecessor = &(predecessor->mVariable);
    210216        }
    211217    }
     
    217223    , mBinary(std::move(other.mBinary))
    218224    , mTernary(std::move(other.mTernary))
    219     , mUnaryVariable(std::move(other.mUnaryVariable)) {
     225    , mVariable(std::move(other.mVariable)) {
    220226
    221227    }
     
    225231        mBinary = std::move(other.mBinary);
    226232        mTernary = std::move(other.mTernary);
    227         mUnaryVariable = std::move(other.mUnaryVariable);
     233        mVariable = std::move(other.mVariable);
    228234        return *this;
    229235    }
    230 
    231236
    232237    template <class Functor, typename... Params>
     
    236241
    237242    template <class Functor, typename... Params>
    238     inline PabloAST * findUnaryVariableOrCall(Functor && functor, const PabloAST::ClassTypeId type, PabloAST * expr, const std::vector<PabloAST *> & args, Params... params) {
    239         return mUnaryVariable.findOrCall(std::move(functor), type, expr, args, std::forward<Params>(params)...);
    240     }
    241 
    242     template <class Functor, typename... Params>
    243243    inline PabloAST * findBinaryOrCall(Functor && functor, const PabloAST::ClassTypeId type, PabloAST * expr1, PabloAST * expr2, Params... params) {
    244244        return mBinary.findOrCall(std::move(functor), type, expr1, expr2, std::forward<Params>(params)...);
     
    250250    }
    251251
     252    template <class Functor, typename... Params>
     253    inline PabloAST * findVariableOrCall(Functor && functor, const PabloAST::ClassTypeId type, const PabloAST * arg1, const std::vector<PabloAST *> & args, Params... params) {
     254        return mVariable.findOrCall(std::move(functor), type, arg1, args, std::forward<Params>(params)...);
     255    }
    252256
    253257    std::pair<PabloAST *, bool> findOrAdd(Statement * stmt) {
     
    260264            case PabloAST::ClassTypeId::Or:
    261265            case PabloAST::ClassTypeId::Xor:
    262                 // test whether the communative version of this statement exists
    263                 if (PabloAST * commExpr = mBinary.find(stmt->getClassTypeId(), stmt->getOperand(1), stmt->getOperand(0))) {
    264                     return std::make_pair(commExpr, false);
    265                 }
    266266            case PabloAST::ClassTypeId::Advance:
    267267            case PabloAST::ClassTypeId::ScanThru:
     
    280280
    281281private:
    282     FixedArgMap<PabloAST *>                                     mUnary;
    283     FixedArgMap<PabloAST *, PabloAST *>                         mBinary;
    284     FixedArgMap<PabloAST *, PabloAST *, PabloAST *>             mTernary;
    285     FixedArgMap<PabloAST *, const std::vector<PabloAST *> &>    mUnaryVariable;
     282    FixedArgMap<PabloAST *>                             mUnary;
     283    FixedArgMap<PabloAST *, PabloAST *>                 mBinary;
     284    FixedArgMap<PabloAST *, PabloAST *, PabloAST *>     mTernary;
     285    VarArgMap                                           mVariable;
    286286};
    287287
  • icGREP/icgrep-devel/icgrep/pablo/function.cpp

    r4684 r4692  
    77Prototype::Prototype(const PabloAST::ClassTypeId type, std::string && name, const unsigned numOfParameters, const unsigned numOfResults, const unsigned requiredStateSpace, void * functionPtr)
    88: PabloAST(type)
    9 , mName(new String(name, false)) // <-- Should there be a global pool to assert that no two prototypes have the same name?
     9, mName(GlobalSymbolGenerator.get(name, false))
    1010, mNumOfParameters(numOfParameters)
    1111, mNumOfResults(numOfResults)
     
    3838}
    3939
    40 
    4140}
  • icGREP/icgrep-devel/icgrep/pablo/function.h

    r4684 r4692  
    2626    }
    2727
    28     static Prototype * Create(std::string name, const unsigned inputVariables, const unsigned outputVariables, const unsigned requiredStateSpace, void * functionPtr = nullptr);
     28    static Prototype * Create(std::string name, const unsigned numOfParameters, const unsigned numOfResults, const unsigned requiredStateSpace, void * functionPtr = nullptr);
    2929
    3030    const String * getName() const {
     
    3232    }
    3333
    34     // Note: this will have to be updated once different stream types exist
    3534    unsigned getNumOfParameters() const {
    3635        return mNumOfParameters;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4686 r4692  
    102102
    103103    std::random_device rd;
    104     const auto seed = rd();
     104    const auto seed = rd(); // 83234827342;
    105105    RNG rng(seed);
    106106
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4656 r4692  
    5151                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
    5252
    53 unsigned __count_advances(const PabloBlock & entry) {
    54 
    55     std::stack<const Statement *> scope;
    56     unsigned advances = 0;
    57 
    58     // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    59     for (const Statement * stmt = entry.front(); ; ) {
    60         while ( stmt ) {
    61             if (isa<Advance>(stmt)) {
    62                 ++advances;
    63             }
    64             else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    65                 // Set the next statement to be the first statement of the inner scope and push the
    66                 // next statement of the current statement into the scope stack.
    67                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    68                 scope.push(stmt->getNextNode());
    69                 stmt = nested.front();
    70                 assert (stmt);
    71                 continue;
    72             }
    73             stmt = stmt->getNextNode();
    74         }
    75         if (scope.empty()) {
    76             break;
    77         }
    78         stmt = scope.top();
    79         scope.pop();
    80     }
    81     return advances;
    82 }
    83 
    84 #define LOG_NUMBER_OF_ADVANCES(entry) LOG("|Advances|=" << __count_advances(entry))
    8553
    8654#else
     
    9462namespace pablo {
    9563
    96 bool BDDMinimizationPass::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
    97 
    98     std::random_device rd;
    99     const auto seed = rd();
    100     RNG rng(seed);
    101 
    102     LOG("Seed:                    " << seed);
     64bool BDDMinimizationPass::optimize(PabloFunction & function) {
    10365
    10466    BDDMinimizationPass am;
    10567    RECORD_TIMESTAMP(start_initialize);
    106     am.initialize(input, entry);
     68    am.initialize(function);
    10769    RECORD_TIMESTAMP(end_initialize);
    10870
    10971    LOG("Initialize:              " << (end_initialize - start_initialize));
    110 
    111     LOG_NUMBER_OF_ADVANCES(entry);
    11272
    11373    RECORD_TIMESTAMP(start_characterize);
     
    11878
    11979    RECORD_TIMESTAMP(start_minimization);
    120     am.minimize(entry);
     80    am.eliminateLogicallyEquivalentStatements(entry);
     81    RECORD_TIMESTAMP(end_minimization);
     82    LOG("Minimize:                " << (end_minimization - start_minimization));
     83
     84    RECORD_TIMESTAMP(start_minimization);
     85    am.simplify(entry);
    12186    RECORD_TIMESTAMP(end_minimization);
    12287    LOG("Minimize:                " << (end_minimization - start_minimization));
     
    12792    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
    12893
    129     RECORD_TIMESTAMP(start_create_multiplex_graph);
    130     const bool multiplex = am.generateMultiplexSets(rng, 1);
    131     RECORD_TIMESTAMP(end_create_multiplex_graph);
    132     LOG("GenerateMultiplexSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
    133 
    134     if (multiplex) {
    135 
    136         RECORD_TIMESTAMP(start_select_multiplex_sets);
    137         am.selectMultiplexSets(rng);
    138         RECORD_TIMESTAMP(end_select_multiplex_sets);
    139         LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
    140 
    141         RECORD_TIMESTAMP(start_subset_constraints);
    142         am.applySubsetConstraints();
    143         RECORD_TIMESTAMP(end_subset_constraints);
    144         LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
    145 
    146         RECORD_TIMESTAMP(start_select_independent_sets);
    147         am.multiplexSelectedIndependentSets();
    148         RECORD_TIMESTAMP(end_select_independent_sets);
    149         LOG("MultiplexSelectedSets:   " << (end_select_independent_sets - start_select_independent_sets));
    150 
    151         RECORD_TIMESTAMP(start_topological_sort);
    152         am.topologicalSort(entry);
    153         RECORD_TIMESTAMP(end_topological_sort);
    154         LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
    155     }
    156 
    157     LOG_NUMBER_OF_ADVANCES(entry);
     94
    15895
    15996    return multiplex;
     
    168105 * the proper variable ordering.
    169106 ** ------------------------------------------------------------------------------------------------------------- */
    170 void BDDMinimizationPass::initialize(const std::vector<Var *> & vars, PabloBlock & entry) {
    171 
    172     flat_map<const PabloAST *, unsigned> map;
     107void BDDMinimizationPass::initialize(PabloFunction &function) {
     108
    173109    std::stack<Statement *> scope;
    174     unsigned complexStatements = 0; // number of statements that cannot always be categorized without generating a new variable
    175 
    176     // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    177     unsigned n = 0, m = 0;
    178     for (Statement * stmt = entry.front(); ; ) {
     110    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
     111
     112    for (Statement * stmt = function.getEntryBlock().front(); ; ) {
    179113        while ( stmt ) {
    180             ++n;
     114
    181115            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    182116                // Set the next statement to be the first statement of the inner scope and push the
     
    189123            }
    190124
    191             assert ("Run the Simplifer pass prior to this!" && (stmt->getNumUses() != 0 || (isa<Assign>(stmt) ? !cast<Assign>(stmt)->superfluous() : false)));
    192 
    193125            switch (stmt->getClassTypeId()) {
    194126                case PabloAST::ClassTypeId::Advance:
    195                     mAdvanceMap.emplace(stmt, m);
    196                     map.emplace(stmt, m++);
    197127                case PabloAST::ClassTypeId::Call:
    198128                case PabloAST::ClassTypeId::ScanThru:
    199129                case PabloAST::ClassTypeId::MatchStar:
    200                     complexStatements++;
     130                    variableCount++;
    201131                    break;
    202132                default:
     
    212142    }
    213143
    214     // Create the transitive closure matrix of graph. From this we'll construct
    215     // two graphs restricted to the relationships between advances. The first will
    216     // be a path graph, which is used to bypass testing for mutual exclusivity of
    217     // advances that cannot be multiplexed. The second is a transitive reduction
    218     // of that graph, which forms the basis of our constraint graph when deciding
    219     // which advances ought to be multiplexed.
    220 
    221     matrix<bool> G(n, m); // Let G be a matrix with n rows of m (Advance) elements
    222     G.clear();
    223     for (unsigned i = 0; i != m; ++i) {
    224         G(i, i) = true;
    225     }
    226 
    227     n = m;
    228     m = 0;
    229 
    230     const Statement * stmt = entry.front();
    231     for (;;) {
    232         while ( stmt ) {
    233 
    234             unsigned u;
    235             if (isa<Advance>(stmt)) {
    236                 assert (mAdvanceMap.count(stmt) && mAdvanceMap[stmt] == m);
    237                 u = m++;
    238             }
    239             else {
    240                 u = n++;
    241                 map.emplace(stmt, u);
    242             }
    243 
    244             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    245                 const PabloAST * const op = stmt->getOperand(i);
    246                 if (LLVM_LIKELY(isa<Statement>(op))) {
    247                     const unsigned v = map[op];
    248                     for (unsigned w = 0; w != m; ++w) {
    249                         G(u, w) |= G(v, w);
    250                     }
    251                 }
    252             }
    253             if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    254                 // Set the next statement to be the first statement of the inner scope
    255                 // and push the next statement of the current statement into the stack.
    256                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    257                 scope.push(stmt->getNextNode());
    258                 stmt = nested.front();
    259                 assert (stmt);
    260                 continue;
    261             }
    262             stmt = stmt->getNextNode();
    263         }
    264         if (scope.empty()) {
    265             break;
    266         }
    267         stmt = scope.top();
    268         scope.pop();
    269     }
    270 
    271     // Record the path / base constraint graph after removing any reflexive-loops.
    272     // Since G is a use-def graph and we want our constraint graph to be a def-use graph,
    273     // reverse the edges as we're writing them to obtain the transposed graph.
    274     mConstraintGraph = ConstraintGraph(m);
    275     mSubsetGraph = SubsetGraph(m);
    276 
    277     for (unsigned i = 0; i != m; ++i) {
    278         G(i, i) = false;
    279         for (unsigned j = 0; j != m; ++j) {
    280             if (G(i, j)) {
    281                 add_edge(j, i, mConstraintGraph);
    282             }
    283         }
    284     }
    285 
    286144    // Initialize the BDD engine ...
    287     mManager = Cudd_Init((complexStatements + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     145    mManager = Cudd_Init((variableCount + function.getNumOfParameters()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    288146    Cudd_AutodynDisable(mManager);
    289147
    290148    // Map the predefined 0/1 entries
    291     mCharacterizationMap[entry.createZeroes()] = Zero();
    292     mCharacterizationMap[entry.createOnes()] = One();
     149    mCharacterizationMap[function.getEntryBlock().createZeroes()] = Zero();
     150    mCharacterizationMap[function.getEntryBlock().createOnes()] = One();
    293151
    294152    // Order the variables so the input Vars are pushed to the end; they ought to
    295153    // be the most complex to resolve.
    296     unsigned i = complexStatements;
    297     for (const Var * var : vars) {
    298         mCharacterizationMap[var] = Cudd_bddIthVar(mManager, i++);
     154    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
     155        mCharacterizationMap[function.getParameter(i)] = Cudd_bddIthVar(mManager, variableCount++);
    299156    }
    300157}
     
    306163 * Scan through the program and iteratively compute the BDDs for each statement.
    307164 ** ------------------------------------------------------------------------------------------------------------- */
    308 void BDDMinimizationPass::characterize(PabloBlock & block) {
     165void BDDMinimizationPass::characterize(const PabloBlock & block) {
    309166    for (Statement * stmt : block) {
    310167        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     
    314171            continue;
    315172        }
    316         mCharacterizationMap[stmt] = characterize(stmt, true);
     173        mCharacterizationMap[stmt] =  characterize(stmt);
    317174    }
    318175}
     
    321178 * @brief characterize
    322179 ** ------------------------------------------------------------------------------------------------------------- */
    323 DdNode * BDDMinimizationPass::characterize(Statement * const stmt, const bool throwUncharacterizedOperandError) {
     180inline DdNode * BDDMinimizationPass::characterize(const Statement * const stmt) {
    324181
    325182    DdNode * bdd = nullptr;
     
    331188            continue;
    332189        }
    333         auto f = mCharacterizationMap.find(op);
    334         if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
    335             if (throwUncharacterizedOperandError) {
    336                 std::string tmp;
    337                 llvm::raw_string_ostream msg(tmp);
    338                 msg << "Uncharacterized operand " << std::to_string(i);
    339                 PabloPrinter::print(stmt, " of ", msg);
    340                 throw std::runtime_error(msg.str());
    341             }
    342             return nullptr;
    343         }
    344         input[i] = f->second;
     190        input[i] = mCharacterizationMap[op];
    345191    }
    346192
     
    353199        case PabloAST::ClassTypeId::Next:
    354200        case PabloAST::ClassTypeId::Or:
    355             return Or(input[0], input[1]);
     201            bdd = Or(input[0], input[1]);
     202            break;
    356203        case PabloAST::ClassTypeId::Xor:
    357             return Xor(input[0], input[1]);
     204            bdd = Xor(input[0], input[1]);
     205            break;
    358206        case PabloAST::ClassTypeId::Not:
    359             return Not(input[0]);
     207            bdd = Not(input[0]);
     208            break;
    360209        case PabloAST::ClassTypeId::Sel:
    361210            bdd = Ite(input[0], input[1], input[2]);
    362211            break;
    363212        case PabloAST::ClassTypeId::ScanThru:
    364             // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
    365             // of a contradition being erroneously calculated later. An example of this
    366             // would be ¬(ScanThru(c,m) √ m)
    367213        case PabloAST::ClassTypeId::MatchStar:
    368             if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
    369                 return Zero();
    370             }
    371214        case PabloAST::ClassTypeId::Call:
     215        case PabloAST::ClassTypeId::Advance:
    372216            return NewVar();
    373         case PabloAST::ClassTypeId::Advance:
    374             return characterize(cast<Advance>(stmt), input[0]);
    375217        default:
    376218            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
     
    387229
    388230/** ------------------------------------------------------------------------------------------------------------- *
    389  * @brief characterize
    390  ** ------------------------------------------------------------------------------------------------------------- */
    391 inline DdNode * BDDMinimizationPass::characterize(Advance * adv, DdNode * input) {
    392     DdNode * Ik, * Ck, * Nk;
    393     if (LLVM_UNLIKELY(isZero(input))) {
    394         Ik = Ck = Nk = Zero();
    395     }
    396     else {
    397 
    398         Ik = input;
    399         Ck = NewVar();
    400         Nk = Not(Ck);
    401 
    402         assert (mAdvanceMap.count(adv));
    403 
    404         const auto k = mAdvanceMap[adv];
    405 
    406         std::vector<bool> unconstrained(k , false);
    407 
    408         // Can we use a transposed copy of the subset graph to determine an ordering of variables?
    409         for (unsigned i = 0; i != k; ++i) {
    410             // Have we already proven that these are unconstrained by the subset relationships?
    411             if (unconstrained[i]) continue;
    412             Advance * tmp = std::get<0>(mAdvance[i]);
    413             // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
    414             if ((adv->getOperand(1) == tmp->getOperand(1)) && (notTransitivelyDependant(i, k))) {
    415                 DdNode * Ii = std::get<1>(mAdvance[i]);
    416                 DdNode * Ni = std::get<2>(mAdvance[i]);
    417                 // TODO: test both Cudd_And and Cudd_bddIntersect to see which is faster
    418                 DdNode * const IiIk = Intersect(Ik, Ii);
    419                 // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    420                 if (noSatisfyingAssignment(IiIk)) {
    421                     assert (mCharacterizationMap.count(tmp));
    422                     DdNode *& Ci = mCharacterizationMap[tmp];
    423                     // Mark the i-th and k-th Advances as being mutually exclusive
    424                     Ck = And(Ck, Ni);
    425                     Ci = And(Ci, Nk);
    426                     // If Ai ∩ Ak = âˆ
    427  and Aj ⊂ Ai, Aj ∩ Ak = âˆ
    428 .
    429                     graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
    430                     for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    431                         const auto j = source(*ei, mSubsetGraph);
    432                         if (notTransitivelyDependant(k, j)) {
    433                             Advance * adv = std::get<0>(mAdvance[j]);
    434                             assert (mCharacterizationMap.count(adv));
    435                             DdNode *& Cj = mCharacterizationMap[adv];
    436                             DdNode * Nj = std::get<2>(mAdvance[j]);
    437                             // Mark the i-th and j-th Advances as being mutually exclusive
    438                             Ck = And(Ck, Nj);
    439                             Cj = And(Cj, Nk);
    440                             unconstrained[j] = true;
    441                         }
    442                     }
    443                     unconstrained[i] = true;
    444                 }
    445                 else if (Ik == IiIk) {
    446                     // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
    447                     // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
    448                     // in the same mutually exclusive set.
    449                     add_edge(k, i, mSubsetGraph);
    450                     // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
    451                     graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
    452                     for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    453                         const auto j = target(*ei, mSubsetGraph);
    454                         add_edge(k, j, mSubsetGraph);
    455                         unconstrained[j] = true;
    456                     }
    457                     unconstrained[i] = true;
    458                 }
    459                 else if (Ii == IiIk) {
    460                     // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
    461                     add_edge(i, k, mSubsetGraph);
    462                     // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
    463                     graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
    464                     for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    465                         const auto j = source(*ei, mSubsetGraph);
    466                         add_edge(j, k, mSubsetGraph);
    467                         unconstrained[j] = true;
    468                     }
    469                     unconstrained[i] = true;
    470                 }
    471                 Cudd_RecursiveDeref(mManager, IiIk);
    472             }
    473         }
    474 
    475         for (unsigned i = 0; i != k; ++i) {
    476             const Advance * const tmp = std::get<0>(mAdvance[i]);
    477             // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
    478             if (!unconstrained[i] || (adv->getParent() != tmp->getParent())) {
    479                 // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
    480                 // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
    481                 add_edge(i, k, mConstraintGraph);
    482             }
    483         }
    484     }
    485 
    486     mAdvance.emplace_back(adv, Ik, Nk);
    487 
    488     return Ck;
    489 }
    490 
    491 /** ------------------------------------------------------------------------------------------------------------- *
    492  * @brief reevaluate
    493  ** ------------------------------------------------------------------------------------------------------------- */
    494 void BDDMinimizationPass::reevaluate(Next * next, DdNode * value) {
    495 
    496     Assign * const initial = cast<Assign>(next->getOperand(0));
    497 
    498     if (LLVM_UNLIKELY(mCharacterizationMap[initial] == value)) {
    499         return;
    500     }
    501     mCharacterizationMap[initial] = value;
    502 
    503 
    504     std::queue<PabloAST *> Q;
    505     flat_set<PabloBlock *> within_scope;
    506 
    507     for (PabloBlock * block = next->getParent(); ;) {
    508         within_scope.insert(block);
    509         for (PabloAST * user : block->users()) {
    510             if (within_scope.insert(cast<PabloBlock>(user)).second) {
    511                 Q.push(user);
    512             }
    513         }
    514         if (Q.empty()) {
    515             break;
    516         }
    517         block = cast<PabloBlock>(Q.front());
    518         Q.pop();
    519     }
    520 
    521     std::unordered_set<PabloAST *> visited;
    522 
    523     for (Statement * current = initial; ; ) {
    524         for (PabloAST * user : current->users()) {
    525             if (Statement * stmt = dyn_cast<Statement>(user)) {
    526                 if (visited.insert(user).second && within_scope.count(stmt->getParent())) {
    527                     DdNode * bdd = characterize(stmt, false);
    528                     if (bdd && mCharacterizationMap[user] != bdd) {
    529                         mCharacterizationMap[user] = bdd;
    530                         Q.push(stmt);
    531                     }
    532                 }
    533             }
    534         }
    535         if (Q.empty()) {
    536             break;
    537         }
    538         current = cast<Statement>(Q.front());
    539         Q.pop();
    540     }
    541 
    542 }
    543 
    544 /** ------------------------------------------------------------------------------------------------------------- *
    545  * @brief minimize
     231 * @brief eliminateLogicallyEquivalentStatements
    546232 * @param entry the entry block of the program
    547233 *
     
    549235 * earlier one (assuming its in scope) and replace any contradictions with Zero.
    550236 ** ------------------------------------------------------------------------------------------------------------- */
    551 inline void BDDMinimizationPass::minimize(PabloBlock & entry) {
     237inline void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & entry) {
    552238    SubsitutionMap baseMap;
    553239    baseMap.insert(Zero(), entry.createZeroes());
    554240    baseMap.insert(One(), entry.createOnes());
    555     minimize(entry, baseMap);
    556 }
    557 
    558 /** ------------------------------------------------------------------------------------------------------------- *
    559  * @brief prohibited
    560  *
    561  * If this statement is an Assign or Next node or any of its operands is a non-superfluous Assign or Next node,
    562  * then we're prohibited from minimizing this statement.
    563  ** ------------------------------------------------------------------------------------------------------------- */
    564 inline bool prohibited(const Statement * const stmt) {
    565     if (isa<Assign>(stmt) || isa<Next>(stmt)) {
    566         return true;
    567     }
    568     for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    569         const PabloAST * const  op = stmt->getOperand(i);
    570         const Assign * const assign = dyn_cast<Assign>(op);
    571         if (LLVM_UNLIKELY((assign && !assign->superfluous()) || isa<Next>(op))) {
    572             return true;
    573         }
    574     }
    575     return false;
    576 }
    577 
    578 /** ------------------------------------------------------------------------------------------------------------- *
    579  * @brief minimize
    580  ** ------------------------------------------------------------------------------------------------------------- */
    581 void BDDMinimizationPass::minimize(PabloBlock & block, SubsitutionMap & parent) {
     241    eliminateLogicallyEquivalentStatements(entry, baseMap);
     242}
     243
     244/** ------------------------------------------------------------------------------------------------------------- *
     245 * @brief eliminateLogicallyEquivalentStatements
     246 ** ------------------------------------------------------------------------------------------------------------- */
     247void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
    582248    SubsitutionMap subsitutionMap(&parent);
    583     for (Statement * stmt : block) {
     249    Statement * stmt = block.front();
     250    while (stmt) {
    584251        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    585252            // Set the next statement to be the first statement of the inner scope and push the
    586253            // next statement of the current statement into the scope stack.
    587             minimize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
     254            eliminateLogicallyEquivalentStatements(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
    588255            continue;
    589256        }
    590257
    591         if (LLVM_UNLIKELY(prohibited(stmt))) {
     258        if (LLVM_UNLIKELY(isa<Assign>(stmt) || isa<Next>(stmt))) {
    592259            continue;
    593260        }
    594261
    595262        DdNode * bdd = mCharacterizationMap[stmt];
    596         PabloAST * replacement = subsitutionMap.test(bdd, stmt);
    597         if (LLVM_UNLIKELY(replacement != nullptr)) {
    598             if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
    599                 assert (mAdvanceMap.count(stmt));
    600                 const auto k = mAdvanceMap[stmt];
    601                 const auto m = num_vertices(mConstraintGraph);
    602                 for (unsigned i = 0; i != m; ++i) {
    603                     add_edge(k, m, mConstraintGraph);
    604                 }
    605             }
     263        PabloAST * replacement = subsitutionMap[bdd];
     264        if (replacement) {
    606265            Cudd_RecursiveDeref(mManager, bdd);
    607             stmt->replaceWith(replacement);
    608         }
    609     }
    610 }
    611 
    612 /** ------------------------------------------------------------------------------------------------------------- *
    613  * @brief notTransitivelyDependant
    614  ** ------------------------------------------------------------------------------------------------------------- */
    615 inline bool BDDMinimizationPass::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const {
    616     assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
    617     return (mConstraintGraph.get_edge(i, j) == 0);
     266            stmt = stmt->replaceWith(replacement, false, true);
     267        }
     268        else {
     269            stmt = stmt->getNextNode();
     270        }
     271    }
     272}
     273
     274/** ------------------------------------------------------------------------------------------------------------- *
     275 * @brief simplify
     276 ** ------------------------------------------------------------------------------------------------------------- */
     277PabloAST * BDDMinimizationPass::simplify(DdNode * bdd) const {
     278
     279    CUDD_VALUE_TYPE value;
     280    int * cube = nullptr;
     281
     282    DdGen * gen = Cudd_FirstCube(mManager, bdd, &cube, &value);
     283    while (!Cudd_IsGenEmpty(gen)) {
     284        // cube[0 ... n - 1] = { 0 : false, 1: true, 2: don't care }
     285
     286
     287
     288
     289        Cudd_NextCube(gen, &cube, &value);
     290    }
     291    Cudd_GenFree(gen);
     292
    618293}
    619294
     
    679354}
    680355
    681 /** ------------------------------------------------------------------------------------------------------------- *
    682  * @brief generateMultiplexSets
    683  * @param RNG random number generator
    684  ** ------------------------------------------------------------------------------------------------------------- */
    685 bool BDDMinimizationPass::generateMultiplexSets(RNG & rng, unsigned k) {
    686 
    687     using vertex_t = ConstraintGraph::vertex_descriptor;
    688     using degree_t = graph_traits<ConstraintGraph>::degree_size_type;
    689 
    690     // What if we generated a "constraint free" graph instead? By taking each connected component of it
    691     // and computing the complement of it (with the same lesser to greater index ordering), we should
    692     // have the same problem here but decomposed into subgraphs.
    693 
    694     IndependentSet M, N;
    695     auto remainingVerticies = num_vertices(mConstraintGraph);
    696     std::vector<degree_t> D(remainingVerticies);
    697     M.reserve(15);
    698     N.reserve(15);
    699 
    700     mMultiplexSetGraph = MultiplexSetGraph(remainingVerticies);
    701 
    702     while (k) {
    703 
    704         // Push all source nodes into the new independent set N
    705         for (auto v : make_iterator_range(vertices(mConstraintGraph))) {
    706             const auto d = in_degree(v, mConstraintGraph);
    707             D[v] = d;
    708             if (d == 0) {
    709                 N.push_back(v);
    710             }
    711         }
    712 
    713         for (;;) {
    714 
    715             addMultiplexSet(N, M);
    716 
    717             if (remainingVerticies == 0) {
    718                 break;
    719             }
    720 
    721             assert (N.size() > 0);
    722 
    723             // Move all of our "newly" uncovered vertices in S into the "known" set M. By always choosing
    724             // at least one element from N, this will prevent us from adding the same multiplexing set again.
    725             M.insert(M.end(), N.begin(), N.end()); N.clear();
    726 
    727             do {
    728                 // Randomly choose a vertex in S and discard it.
    729                 assert (!M.empty());
    730                 const auto i = M.begin() + IntDistribution(0, M.size() - 1)(rng);
    731                 const vertex_t u = *i;
    732                 M.erase(i);
    733                 --remainingVerticies;
    734                 for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
    735                     const vertex_t v = target(e, mConstraintGraph);
    736                     if ((--D[v]) == 0) {
    737                         N.push_back(v);
    738                     }
    739                 }
    740             }
    741             while (N.empty() && remainingVerticies != 0);
    742         }
    743 
    744         if (--k == 0) {
    745             break;
    746         }
    747 
    748         N.clear();
    749         M.clear();
    750     }
    751 
    752     return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
    753 }
    754 
    755 /** ------------------------------------------------------------------------------------------------------------- *
    756  * @brief addMultiplexSet
    757  * @param N an independent set
    758  * @param M an independent set
    759  ** ------------------------------------------------------------------------------------------------------------- */
    760 inline void BDDMinimizationPass::addMultiplexSet(const IndependentSet & N, const IndependentSet & M) {
    761 
    762     // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
    763     // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
    764 
    765     if ((N.size() + M.size()) >= 3) {
    766         const auto u = add_vertex(mMultiplexSetGraph);
    767         for (const auto x : N) {
    768             add_edge(u, x, mMultiplexSetGraph);
    769         }
    770         for (const auto y : M) {
    771             add_edge(u, y, mMultiplexSetGraph);
    772         }
    773     }
    774 }
    775 
    776 /** ------------------------------------------------------------------------------------------------------------- *
    777  * @brief is_power_of_2
    778  * @param n an integer
    779  ** ------------------------------------------------------------------------------------------------------------- */
    780 static inline bool is_power_of_2(const size_t n) {
    781     return ((n & (n - 1)) == 0) ;
    782 }
    783 
    784 /** ------------------------------------------------------------------------------------------------------------- *
    785  * @brief log2_plus_one
    786  ** ------------------------------------------------------------------------------------------------------------- */
    787 static inline size_t log2_plus_one(const size_t n) {
    788     return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
    789 }
    790 
    791 /** ------------------------------------------------------------------------------------------------------------- *
    792  * @brief selectMultiplexSets
    793  * @param RNG random number generator
    794  *
    795  * This algorithm is simply computes a greedy set cover. We want an exact max-weight set cover but can generate new
    796  * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well
    797  * enough but more analysis is needed.
    798  ** ------------------------------------------------------------------------------------------------------------- */
    799 void BDDMinimizationPass::selectMultiplexSets(RNG &) {
    800 
    801 
    802     using OutEdgeIterator = graph_traits<MultiplexSetGraph>::out_edge_iterator;
    803     using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator;
    804     using degree_t = MultiplexSetGraph::degree_size_type;
    805     using vertex_t = MultiplexSetGraph::vertex_descriptor;
    806 
    807     const size_t m = num_vertices(mConstraintGraph);
    808     const size_t n = num_vertices(mMultiplexSetGraph) - m;
    809 
    810     std::vector<degree_t> remaining(n, 0);
    811     std::vector<vertex_t> chosen_set(m, 0);
    812 
    813     for (unsigned i = 0; i != n; ++i) {
    814         remaining[i] = out_degree(i + m, mMultiplexSetGraph);
    815     }
    816 
    817     for (;;) {
    818 
    819         // Choose the set with the greatest number of vertices not already included in some other set.
    820         vertex_t k = 0;
    821         degree_t w = 0;
    822         for (vertex_t i = 0; i != n; ++i) {
    823             const degree_t r = remaining[i];
    824             if (w < r) {
    825                 k = i;
    826                 w = r;
    827             }
    828         }
    829 
    830         // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort.
    831         if (w < 3) {
    832             break;
    833         }
    834 
    835         OutEdgeIterator ei, ei_end;
    836         for (std::tie(ei, ei_end) = out_edges(k + m, mMultiplexSetGraph); ei != ei_end; ++ei) {
    837             const vertex_t j = target(*ei, mMultiplexSetGraph);
    838             if (chosen_set[j] == 0) {
    839                 chosen_set[j] = (k + m);
    840                 InEdgeIterator ej, ej_end;
    841                 for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
    842                     remaining[source(*ej, mMultiplexSetGraph) - m]--;
    843                 }
    844             }
    845         }
    846 
    847         assert (remaining[k] == 0);
    848 
    849         // If this contains 2^n elements for any n, discard the member that is most likely to be added
    850         // to some future set.
    851         if (is_power_of_2(w)) {
    852             vertex_t j = 0;
    853             degree_t w = 0;
    854             for (vertex_t i = 0; i != m; ++i) {
    855                 if (chosen_set[i] == (k + m)) {
    856                     InEdgeIterator ej, ej_end;
    857                     degree_t r = 1;
    858                     for (std::tie(ej, ej_end) = in_edges(i, mMultiplexSetGraph); ej != ej_end; ++ej) {
    859                         // strongly prefer adding weight to unvisited sets that have more remaining vertices
    860                         r += std::pow(remaining[source(*ej, mMultiplexSetGraph) - m], 2);
    861                     }
    862                     if (w < r) {
    863                         j = i;
    864                         w = r;
    865                     }
    866                 }
    867             }
    868             assert (w > 0);
    869             chosen_set[j] = 0;
    870             InEdgeIterator ej, ej_end;
    871             for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
    872                 remaining[source(*ej, mMultiplexSetGraph) - m]++;
    873             }
    874         }
    875     }
    876 
    877     for (unsigned i = 0; i != m; ++i) {
    878         InEdgeIterator ei, ei_end;
    879         std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
    880         for (auto next = ei; ei != ei_end; ei = next) {
    881             ++next;
    882             if (source(*ei, mMultiplexSetGraph) != chosen_set[i]) {
    883                 remove_edge(*ei, mMultiplexSetGraph);
    884             }
    885         }
    886     }
    887 
    888     #ifndef NDEBUG
    889     for (unsigned i = 0; i != m; ++i) {
    890         assert (in_degree(i, mMultiplexSetGraph) <= 1);
    891     }
    892     for (unsigned i = m; i != (m + n); ++i) {
    893         assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
    894     }
    895     #endif
    896 }
    897 
    898 /** ------------------------------------------------------------------------------------------------------------- *
    899  * @brief choose
    900  ** ------------------------------------------------------------------------------------------------------------- */
    901 
    902 inline Statement * choose(PabloAST * x, PabloAST * y, Statement * z) {
    903     return isa<Statement>(x) ? cast<Statement>(x) : (isa<Statement>(y) ? cast<Statement>(y) : z);
    904 }
    905 
    906 /** ------------------------------------------------------------------------------------------------------------- *
    907  * @brief applySubsetConstraints
    908  ** ------------------------------------------------------------------------------------------------------------- */
    909 void BDDMinimizationPass::applySubsetConstraints() {
    910 
    911     // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
    912     // relationships of our independent sets.
    913     const unsigned m = num_vertices(mConstraintGraph);
    914     const unsigned n = num_vertices(mMultiplexSetGraph);
    915 
    916     // Add in any edges from our subset constraints to M that are within the same set.
    917     bool hasSubsetConstraint = false;
    918 
    919     graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
    920     for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
    921         const auto u = source(*ei, mSubsetGraph);
    922         const auto v = target(*ei, mSubsetGraph);
    923         graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
    924         // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
    925         // "set vertex". Add the edge between the vertices.
    926         for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
    927             auto w = target(*ej, mMultiplexSetGraph);
    928             // Only check (v, w) if w is a "set vertex".
    929             if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
    930                 add_edge(u, v, mMultiplexSetGraph);
    931                 hasSubsetConstraint = true;
    932             }
    933         }
    934     }
    935 
    936     if (LLVM_UNLIKELY(hasSubsetConstraint)) {
    937         // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
    938         // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
    939         // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
    940 
    941         std::vector<MultiplexSetGraph::vertex_descriptor> V;
    942         std::stack<MultiplexSetGraph::vertex_descriptor> S;
    943         std::queue<PabloAST *> Q;
    944         BitVector D(n - m, 0);
    945 
    946         for (auto i = m; i != n; ++i) {
    947             graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
    948             // For each member of a "set vertex" ...
    949             std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
    950             for (; ei != ei_end; ++ei) {
    951                 const auto s = source(*ei, mMultiplexSetGraph);
    952                 if (out_degree(s, mMultiplexSetGraph) != 0) {
    953                     // First scan through the subgraph of vertices in M dominated by s and build up the set T,
    954                     // consisting of all sinks w.r.t. vertex s.
    955                     auto u = s;
    956                     for (;;) {
    957                         graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
    958                         for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
    959                             auto v = target(*ej, mMultiplexSetGraph);
    960                             if (D.test(v)) {
    961                                 continue;
    962                             }
    963                             D.set(v);
    964                             if (out_degree(v, mMultiplexSetGraph) == 0) {
    965                                 V.push_back(v);
    966                             }
    967                             else {
    968                                 S.push(v);
    969                             }
    970                         }
    971                         if (S.empty()) {
    972                             break;
    973                         }
    974                         u = S.top();
    975                         S.pop();
    976                     }
    977                     D.clear();
    978                     // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
    979                     // with the complement of each advance indicated by V.
    980 
    981                     Advance * adv = std::get<0>(mAdvance[s]);
    982                     PabloBlock * pb = adv->getParent();
    983 
    984                     for (auto i : V) {
    985                         Q.push(std::get<0>(mAdvance[i])->getOperand(0));
    986                     }
    987                     while (Q.size() > 1) {
    988                         PabloAST * a1 = Q.front(); Q.pop();
    989                         PabloAST * a2 = Q.front(); Q.pop();
    990                         pb->setInsertPoint(cast<Statement>(a2));
    991                         Q.push(pb->createOr(a1, a2));
    992                     }
    993                     assert (Q.size() == 1);
    994 
    995                     PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
    996                     adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in"));
    997 
    998                     // Similar to the above, we're going to OR together the result of each advance,
    999                     // including s. This will restore the advanced variable back to its original state.
    1000 
    1001                     // Gather the original users to this advance. We'll be manipulating it shortly.
    1002                     Statement::Vector U(adv->users());
    1003 
    1004                     // Add s to V and sort the list; it'll be closer to being in topological order.
    1005                     V.push_back(s);
    1006                     std::sort(V.begin(), V.end());
    1007                     for (auto i : V) {
    1008                         Q.push(std::get<0>(mAdvance[i]));
    1009                     }
    1010                     while (Q.size() > 1) {
    1011                         PabloAST * a1 = Q.front(); Q.pop();
    1012                         PabloAST * a2 = Q.front(); Q.pop();
    1013                         pb->setInsertPoint(choose(a2, a1, adv));
    1014                         Q.push(pb->createOr(a1, a2));
    1015                     }
    1016                     assert (Q.size() == 1);
    1017 
    1018                     PabloAST * const input = Q.front(); Q.pop();
    1019                     for (PabloAST * use : U) {
    1020                         if (LLVM_LIKELY(isa<Statement>(use))) {
    1021                             cast<Statement>(use)->replaceUsesOfWith(adv, input);
    1022                         }
    1023                     }
    1024 
    1025                     pb->setInsertPoint(pb->back());
    1026 
    1027                     V.clear();
    1028 
    1029                 }
    1030             }
    1031         }
    1032     }
    1033 }
    1034 
    1035 /** ------------------------------------------------------------------------------------------------------------- *
    1036  * @brief multiplexSelectedIndependentSets
    1037  ** ------------------------------------------------------------------------------------------------------------- */
    1038 void BDDMinimizationPass::multiplexSelectedIndependentSets() const {
    1039 
    1040     const unsigned f = num_vertices(mConstraintGraph);
    1041     const unsigned l = num_vertices(mMultiplexSetGraph);
    1042 
    1043     // Preallocate the structures based on the size of the largest multiplex set
    1044     size_t max_n = 3;
    1045     for (unsigned s = f; s != l; ++s) {
    1046         max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
    1047     }
    1048     const size_t max_m = log2_plus_one(max_n);
    1049 
    1050     std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
    1051     std::vector<Advance *> V(max_n);
    1052     std::vector<PabloAST *> muxed(max_m);
    1053     circular_buffer<PabloAST *> Q(max_n);
    1054 
    1055     // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
    1056     // relationships of our independent sets.
    1057 
    1058     for (unsigned s = f; s != l; ++s) {
    1059         const size_t n = out_degree(s, mMultiplexSetGraph);
    1060         if (n) {
    1061 
    1062             const size_t m = log2_plus_one(n);
    1063 
    1064             graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
    1065             std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph);
    1066             for (unsigned i = 0; i != n; ++ei, ++i) {
    1067                 I[i] = target(*ei, mMultiplexSetGraph);
    1068                 assert (I[i] < mAdvance.size());
    1069             }
    1070             std::sort(I.begin(), I.begin() + n);
    1071 
    1072             for (unsigned i = 0; i != n; ++i) {
    1073                 V[i] = std::get<0>(mAdvance[I[i]]);
    1074             }
    1075 
    1076             PabloBlock * const block = V[0]->getParent();
    1077             assert (block);
    1078 
    1079             // Sanity test to make sure every advance is in the same scope.
    1080             #ifndef NDEBUG
    1081             for (unsigned i = 1; i != n; ++i) {
    1082                 assert (I[i - 1] < I[i]);
    1083                 assert (V[i - 1] != V[i]);
    1084                 assert (V[i]->getParent() == block);
    1085             }
    1086             #endif
    1087 
    1088             PabloBuilder pb(*block);
    1089 
    1090             /// Perform n-to-m Multiplexing
    1091             for (size_t j = 0; j != m; ++j) {
    1092 
    1093                 assert (Q.empty());
    1094 
    1095                 std::ostringstream prefix;
    1096                 prefix << "mux" << n << "to" << m << '_';
    1097                 for (size_t i = 1; i <= n; ++i) {
    1098                     if ((i & (static_cast<size_t>(1) << j)) != 0) {
    1099                         assert (!Q.full());
    1100                         PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
    1101                         // prefix << '_' << V[i - 1]->getName()->to_string();
    1102                         Q.push_back(tmp);
    1103                     }
    1104                 }
    1105 
    1106                 assert (Q.size() >= 1);
    1107 
    1108                 Advance * const adv = V[j];
    1109                 // TODO: figure out a way to determine whether we're creating a duplicate value below.
    1110                 // The expression map findOrCall ought to work conceptually but the functors method
    1111                 // doesn't really work anymore with the current API.
    1112                 while (Q.size() > 1) {
    1113                     PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    1114                     PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    1115                     assert (!Q.full());
    1116                     pb.setInsertPoint(choose(a2, a1, adv));
    1117                     Q.push_back(pb.createOr(a1, a2));
    1118                 }
    1119                 assert (Q.size() == 1);
    1120 
    1121                 PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
    1122                 muxed[j] = pb.createAdvance(mux, adv->getOperand(1), prefix.str());
    1123             }
    1124 
    1125 
    1126             /// Perform m-to-n Demultiplexing
    1127             // Now construct the demuxed values and replaces all the users of the original advances with them.
    1128             for (size_t i = 1; i <= n; ++i) {
    1129 
    1130                 Advance * const adv = V[i - 1];
    1131 
    1132                 pb.setInsertPoint(adv);
    1133                 assert (Q.empty());
    1134                 for (size_t j = 0; j != m; ++j) {
    1135                     if ((i & (static_cast<size_t>(1) << j)) == 0) {
    1136                         Q.push_back(muxed[j]);
    1137                     }
    1138                 }
    1139 
    1140                 assert (Q.size() <= m);
    1141                 PabloAST * neg = nullptr;
    1142                 if (LLVM_LIKELY(Q.size() > 0)) {
    1143                     while (Q.size() > 1) {
    1144                         PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    1145                         PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    1146                         assert (!Q.full());
    1147                         Q.push_back(pb.createOr(a1, a2));
    1148                     }
    1149                     assert (Q.size() == 1);
    1150                     neg = pb.createNot(Q.front()); Q.pop_front(); assert (neg);
    1151                 }
    1152 
    1153                 assert (Q.empty());
    1154                 for (unsigned j = 0; j != m; ++j) {
    1155                     if ((i & (static_cast<unsigned>(1) << j)) != 0) {
    1156                         assert (!Q.full());
    1157                         Q.push_back(muxed[j]);
    1158                     }
    1159                 }
    1160 
    1161                 assert (Q.size() <= m);
    1162                 assert (Q.size() >= 1);
    1163 
    1164                 while (Q.size() > 1) {
    1165                     PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    1166                     PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    1167                     assert (!Q.full());
    1168                     Q.push_back(pb.createAnd(a1, a2));
    1169                 }
    1170 
    1171                 assert (Q.size() == 1);
    1172 
    1173                 PabloAST * demux = Q.front(); Q.pop_front(); assert (demux);
    1174                 if (LLVM_LIKELY(neg != nullptr)) {
    1175                     demux = pb.createAnd(demux, neg);
    1176                 }
    1177                 V[i - 1]->replaceWith(demux, true, true);
    1178             }
    1179         }
    1180     }
    1181 }
    1182 
    1183 /** ------------------------------------------------------------------------------------------------------------- *
    1184  * @brief topologicalSort
    1185  *
    1186  * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
    1187  * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
    1188  * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
    1189  * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
    1190  * it's not necessarily the original ordering.
    1191  ** ------------------------------------------------------------------------------------------------------------- */
    1192 void BDDMinimizationPass::topologicalSort(PabloBlock & entry) const {
    1193     // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
    1194     std::unordered_set<const PabloAST *> encountered;
    1195     std::stack<Statement *> scope;
    1196     for (Statement * stmt = entry.front(); ; ) { restart:
    1197         while ( stmt ) {
    1198             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    1199                 PabloAST * const op = stmt->getOperand(i);
    1200                 if (LLVM_LIKELY(isa<Statement>(op))) {
    1201                     if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
    1202                         if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
    1203                             if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
    1204                                 continue;
    1205                             }
    1206                         }
    1207                         Statement * const next = stmt->getNextNode();
    1208                         stmt->insertAfter(cast<Statement>(op));
    1209                         stmt = next;
    1210                         goto restart;
    1211                     }
    1212                 }
    1213             }
    1214             if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    1215                 // Set the next statement to be the first statement of the inner scope and push the
    1216                 // next statement of the current statement into the scope stack.
    1217                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    1218                 scope.push(stmt->getNextNode());
    1219                 stmt = nested.front();
    1220                 continue;
    1221             }
    1222             encountered.insert(stmt);
    1223             stmt = stmt->getNextNode();
    1224         }
    1225         if (scope.empty()) {
    1226             break;
    1227         }
    1228         stmt = scope.top();
    1229         scope.pop();
    1230     }
    1231 }
     356
    1232357
    1233358} // end of namespace pablo
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4629 r4692  
    2323
    2424    using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
    25     using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
    26     using ConstraintVertex = ConstraintGraph::vertex_descriptor;
    27     using RNG = std::mt19937;
    28     using IntDistribution = std::uniform_int_distribution<RNG::result_type>;
    29     using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    30     using IndependentSetGraph = boost::adjacency_matrix<boost::undirectedS, std::pair<int, int>>;
    31     using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    32     // the Advance pointer, input BDD and the BDD variable of the i-th Advance
    33     using AdvanceMap = boost::container::flat_map<const Statement *, unsigned>;
    34     using AdvanceVector = std::vector<std::tuple<Advance *, DdNode *, DdNode *>>;
    35     using IndependentSet = std::vector<ConstraintVertex>;
    3625
    3726    struct SubsitutionMap {
    3827        SubsitutionMap(SubsitutionMap * parent = nullptr) : mParent(parent) {}
    39         PabloAST * test(const DdNode * node, PabloAST * stmt) {
    40             PabloAST * replacement = find(node);
    41             if (LLVM_LIKELY(replacement == nullptr)) {
    42                 mMap.insert(std::make_pair(node, stmt));
    43             }
    44             return replacement;
    45         }
    46         PabloAST * find(const DdNode * node) const {
     28
     29        PabloAST * operator [](const DdNode * node) const {
    4730            auto f = mMap.find(node);
    48             if (LLVM_LIKELY(f == mMap.end())) {
    49                 PabloAST * replacement = nullptr;
    50                 if (mParent == nullptr) {
    51                     replacement = mParent->find(node);
    52                 }
    53                 return replacement;
     31            if (f == mMap.end()) {
     32                return mParent ? mParent->find(node) : nullptr;
    5433            }
    5534            return f->second;
    5635        }
     36
    5737        void insert(const DdNode * node, PabloAST * stmt) {
    5838            mMap.insert(std::make_pair(node, stmt));
     
    6444
    6545public:
    66     static bool optimize(const std::vector<Var *> & input, PabloBlock & entry);
     46    static bool optimize(PabloFunction & function);
    6747protected:
    68     void initialize(const std::vector<Var *> & vars, PabloBlock & entry);
    69     void characterize(PabloBlock & block);
    70     DdNode * characterize(Statement * const stmt, const bool throwUncharacterizedOperandError);
    71     DdNode * characterize(Advance * adv, DdNode * input);
    72     void reevaluate(Next * next, DdNode * value);
    73     void minimize(PabloBlock & entry);
    74     void minimize(PabloBlock & block, SubsitutionMap & parent);
     48    void initialize(PabloFunction & function);
     49    void characterize(const PabloBlock &block);
     50    DdNode * characterize(const Statement * const stmt);
     51    void eliminateLogicallyEquivalentStatements(PabloBlock & entry);
     52    void eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
     53    void simplify(PabloBlock & entry);
     54    PabloAST * simplify(DdNode * bdd);
    7555
    76     bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
    77     bool generateMultiplexSets(RNG & rng, unsigned k = 1);
    78     void addMultiplexSet(const IndependentSet & N, const IndependentSet & M);
    79     void selectMultiplexSets(RNG &);
    80     void applySubsetConstraints();
    81     void multiplexSelectedIndependentSets() const;
    82     void topologicalSort(PabloBlock & entry) const;
    83     inline AutoMultiplexing()
    84     : mVariables(0)
    85     , mConstraintGraph(0)
    86     {
    87     }
    8856private:
    8957    DdNode * Zero() const;
     
    10371    unsigned                mVariables;
    10472    CharacterizationMap     mCharacterizationMap;
    105     ConstraintGraph         mConstraintGraph;
    106     SubsetGraph             mSubsetGraph;
    107     AdvanceMap              mAdvanceMap;
    108     AdvanceVector           mAdvance;
    109     MultiplexSetGraph       mMultiplexSetGraph;
    11073};
    11174
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4680 r4692  
    137137private:
    138138    const ClassTypeId       mClassTypeId;
    139     Vector                   mUsers;
     139    Vector                  mUsers;
    140140    static VectorAllocator  mVectorAllocator;
    141141};
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r4690 r4692  
    173173        Value * gep = mBuilder->CreateGEP(mInputAddressPtr, indices);
    174174        LoadInst * basisBit = mBuilder->CreateAlignedLoad(gep, BLOCK_SIZE/8, false, function.getParameter(i)->getName()->to_string());
    175         mMarkerMap.insert(std::make_pair(function.getParameter(i), basisBit));
     175        mMarkerMap[function.getParameter(i)] = basisBit;
    176176        if (DumpTrace) {
    177177            genPrintRegister(function.getParameter(i)->getName()->to_string(), basisBit);
     
    323323
    324324inline void PabloCompiler::Examine(PabloFunction & function) {
    325     if (mMod == nullptr) {
    326 
    327         mWhileDepth = 0;
    328         mIfDepth = 0;
    329         mMaxWhileDepth = 0;
    330 
    331         Examine(function.getEntryBlock());
    332 
    333         if (LLVM_UNLIKELY(mWhileDepth != 0 || mIfDepth != 0)) {
    334             throw std::runtime_error("Malformed Pablo AST: Unbalanced If or While nesting depth!");
    335         }
     325    mWhileDepth = 0;
     326    mIfDepth = 0;
     327    mMaxWhileDepth = 0;
     328    Examine(function.getEntryBlock());
     329    if (LLVM_UNLIKELY(mWhileDepth != 0 || mIfDepth != 0)) {
     330        throw std::runtime_error("Malformed Pablo AST: Unbalanced If or While nesting depth!");
    336331    }
    337332}
  • icGREP/icgrep-devel/icgrep/pablo/pe_string.h

    r4680 r4692  
    8383}
    8484
     85
    8586}
    8687
  • icGREP/icgrep-devel/icgrep/pablo/symbol_generator.h

    r4510 r4692  
    3636};
    3737
     38static SymbolGenerator GlobalSymbolGenerator;
     39
    3840}
    3941
Note: See TracChangeset for help on using the changeset viewer.