Ignore:
Timestamp:
Nov 12, 2015, 4:26:25 PM (4 years ago)
Author:
nmedfort
Message:

Work on bug fixes for multiplexing pass.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4860 r4868  
    1313#include <llvm/ADT/DenseMap.h>
    1414
    15 struct DdManager; // forward declare of the CUDD manager
    16 struct DdNode;
     15typedef int BDD;
    1716
    1817namespace pablo {
     
    2322class AutoMultiplexing {
    2423
    25     using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
     24    using CharacterizationMap = llvm::DenseMap<const PabloAST *, BDD>;
    2625    using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
    2726    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
     
    3029    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    3130    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 *>>;
     31    using AdvanceAttributes = std::vector<std::tuple<Advance *, BDD, BDD>>; // the Advance pointer, input BDD, the base BDD variable
    3532    using VertexVector = std::vector<ConstraintVertex>;
    36     using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;
    3733    using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
    38     using TopologicalGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, Statement *>;
    39     using TopologicalVertex = TopologicalGraph::vertex_descriptor;
    40     using TopologicalMap = boost::container::flat_map<const Statement *, TopologicalVertex>;
     34
    4135public:
    4236    static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100);
    4337protected:
    44     bool initialize(PabloFunction & function);
     38    unsigned initialize(PabloFunction & function);
    4539    void characterize(PabloBlock & block);
    46     DdNode * characterize(Statement * const stmt);
    47     DdNode * characterize(Advance * adv, DdNode * input);
    48     bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
     40    BDD characterize(Statement * const stmt);
     41    BDD characterize(Advance * const adv, const BDD Ik);
     42    bool independent(const ConstraintVertex i, const ConstraintVertex j) const;
    4943    bool generateCandidateSets(RNG & rng);
    5044    void addCandidateSet(const VertexVector & S, RNG & rng);
    5145    void selectMultiplexSets(RNG &);
     46    void transitiveReductionOfSubsetGraph() ;
    5247    void applySubsetConstraints();
    5348    void multiplexSelectedIndependentSets(PabloFunction & function);
     49    static void topologicalSort(PabloFunction & function);
    5450
    5551    inline AutoMultiplexing(const unsigned limit, const unsigned maxSelections)
     
    6258
    6359private:
    64 
    65     DdNode * Zero() const;
    66     DdNode * One() const;
    67     bool isZero(DdNode * const x) const;
    68     DdNode * And(DdNode * const x, DdNode * const y);
    69     DdNode * Or(DdNode * const x, DdNode * const y);
    70     DdNode * Xor(DdNode * const x, DdNode * const y);
    71     DdNode * Not(DdNode * x) const;
    72     DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
    73     DdNode * NewVar();
    74     void Ref(DdNode * const x);
    75     void Deref(DdNode * const x);
    76     bool NoSatisfyingAssignment(DdNode * const x);
    77     void Shutdown();
    78 
    79 private:
    80     DdManager *                 mManager;
    81     const unsigned              mLimit;
     60    unsigned                    mLimit;
    8261    const unsigned              mMaxSelections;
    8362    unsigned                    mVariables;
     
    8564    ConstraintGraph             mConstraintGraph;
    8665    SubsetGraph                 mSubsetGraph;
    87     AdvanceMap                  mAdvanceMap;
    88     AdvanceVector               mAdvance;
     66    AdvanceAttributes           mAdvanceAttributes;
    8967    MultiplexSetGraph           mMultiplexSetGraph;
    90     RecentCharacterizations     mRecentCharacterizations;
    9168    ScopeMap                    mResolvedScopes;
    9269};
Note: See TracChangeset for help on using the changeset viewer.