source: icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp @ 4722

Last change on this file since 4722 was 4722, checked in by nmedfort, 4 years ago

Misc. changes and start of dependency chain analysis in ucd generator.

File size: 3.7 KB
RevLine 
[4242]1#ifndef PABLO_AUTOMULTIPLEXING_HPP
2#define PABLO_AUTOMULTIPLEXING_HPP
3
4#include <pablo/codegenstate.h>
[4569]5#include <slab_allocator.h>
[4579]6#include <queue>
[4569]7#include <boost/graph/adjacency_list.hpp>
8#include <boost/graph/adjacency_matrix.hpp>
9#include <boost/container/flat_map.hpp>
10#include <boost/numeric/ublas/matrix.hpp>
[4570]11#include <random>
[4569]12#include <stdint.h>
[4611]13#include <llvm/ADT/DenseMap.h>
[4242]14
[4583]15struct DdManager; // forward declare of the CUDD manager
16struct DdNode;
17
[4242]18namespace pablo {
19
[4638]20class PabloBuilder;
[4657]21class PabloFunction;
[4638]22
[4569]23class AutoMultiplexing {
24
[4611]25    using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
[4601]26    using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
[4610]27    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
[4608]28    using RNG = std::mt19937;
29    using IntDistribution = std::uniform_int_distribution<RNG::result_type>;
[4610]30    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
[4648]31    using Trie = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::directedS, ConstraintVertex, boost::no_property>;
[4594]32    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
[4611]33    // the Advance pointer, input BDD and the BDD variable of the i-th Advance
34    using AdvanceMap = boost::container::flat_map<const Statement *, unsigned>;
35    using AdvanceVector = std::vector<std::tuple<Advance *, DdNode *, DdNode *>>;
[4648]36    using VertexVector = std::vector<ConstraintVertex>;
[4722]37    using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;
38    using MuxedVariables = std::vector<std::vector<PabloAST *>>;
[4242]39public:
[4657]40    static bool optimize(PabloFunction & function);
[4569]41protected:
[4665]42    bool initialize(PabloFunction & function);
[4646]43    void characterize(PabloBlock &block);
[4629]44    DdNode * characterize(Statement * const stmt);
[4611]45    DdNode * characterize(Advance * adv, DdNode * input);
[4610]46    bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
[4650]47    bool generateCandidateSets(RNG & rng);
48    void addCandidateSet(const VertexVector & S);
[4608]49    void selectMultiplexSets(RNG &);
[4571]50    void applySubsetConstraints();
[4722]51    void multiplexSelectedIndependentSets();
52    void simplifyAST(const PabloFunction & function);
53    PabloAST * simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder);
54    PabloAST * makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder);
[4579]55    void topologicalSort(PabloBlock & entry) const;
[4657]56    inline AutoMultiplexing()
[4600]57    : mVariables(0)
[4601]58    , mConstraintGraph(0)
[4599]59    {
[4583]60    }
[4242]61private:
[4639]62
[4592]63    DdNode * Zero() const;
64    DdNode * One() const;
[4594]65    bool isZero(DdNode * const x) const;
66    DdNode * And(DdNode * const x, DdNode * const y);
67    DdNode * Or(DdNode * const x, DdNode * const y);
68    DdNode * Xor(DdNode * const x, DdNode * const y);
69    DdNode * Not(DdNode * x) const;
70    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
[4610]71    DdNode * NewVar();
[4646]72    void Ref(DdNode * const x);
73    void Deref(DdNode * const x);
[4639]74    bool NoSatisfyingAssignment(DdNode * const x);
75    void Shutdown();
76
[4583]77private:
[4639]78    DdManager *                 mManager;
79    unsigned                    mVariables;
80    CharacterizationMap         mCharacterizationMap;
81    ConstraintGraph             mConstraintGraph;
82    SubsetGraph                 mSubsetGraph;
83    AdvanceMap                  mAdvanceMap;
84    AdvanceVector               mAdvance;
85    MultiplexSetGraph           mMultiplexSetGraph;
[4646]86    RecentCharacterizations     mRecentCharacterizations;
[4722]87    MuxedVariables              mMuxedVariables;
88    unsigned                    mSimplifyDepth;
[4242]89};
90
91}
92
93#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.