DFnetlist.h

Go to the documentation of this file.

#ifndef DATAFLOW_IMPL_H
#define DATAFLOW_IMPL_H

#include <cassert>
#include <deque>
#include <list>
#include <map>
#include <string>
#include "Dataflow.h"
#include "ErrorManager.h"
#include "FileUtil.h"
#include "MILP_Model.h"

// Some useful macros
#define ForAllBlocks(b)         for (blockID b: allBlocks)
#define ForAllChannels(c)       for (channelID c: allChannels)
#define ForAllPorts(b,p)        for (portID p: getPorts(b, ALL_PORTS))
#define ForAllInputPorts(b,p)   for (portID p: getPorts(b, INPUT_PORTS))
#define ForAllOutputPorts(b,p)  for (portID p: getPorts(b, OUTPUT_PORTS))
#define ForAllBasicBlocks(bb)   for (bbID bb = 0; bb < numBasicBlocks(); ++bb)

namespace Dataflow
{
struct milpVarsEB; // Defined locally in DFnetlist_buffers.cpp
struct milpVarsMG; // Defined locally in DFnetlist_MG.cpp

using bbID = int;       // Identifiers for Basic Blocks
using bbArcID = int;    // Identifiers for Basic Block arcs
using vecBBs = std::vector<bbID>;
using setBBs = std::set<bbID>;
using vecBBArcs = std::vector<bbArcID>;
using setBBArcs = std::set<bbArcID>;

using longValueType = long long;    // Internal representation for constant values

class BasicBlockGraph
{
public:

    BasicBlockGraph() {
        clear();
    }

    void clear() {
        BBs.clear();
        Arcs.clear();
        entryBB = invalidDataflowID;
    }

    int numBasicBlocks() const {
        return BBs.size();
    }

    int numArcs() const {
        return Arcs.size();
    }

    bool empty() const {
        return numBasicBlocks() == 0;
    }

    bbID createBasicBlock() {
        bbID id = BBs.size() + 1;

        // Block with freq = -1 and exec = 1
        BasicBlock bb;
        bb.exec = 1;
        bb.freq = -1;
        bb.id = id;

        BBs.push_back(bb);
        return id;
    }

    void setEntryBasicBlock(bbID bb) {
        entryBB = bb;
    }

    bbID getEntryBasicBlock() const {
        return entryBB;
    }

    setBBs& getExitBasicBlocks() {
        return exitBBs;
    }

    void addExitBasicBlock(bbID bb) {
        exitBBs.insert(bb);
    }

    bool isEntryBasicBlock(bbID bb) {
        return entryBB == bb;
    }

    bool isExitBasicBlock(bbID bb) {
        return exitBBs.count(bb) > 0;
    }

    bbArcID findArc(bbID src, bbID dst) const;

    bbArcID findOrAddArc(bbID src, bbID dst, double freq = 0);

    bbID getSrcBB(bbArcID arc) const {
        return Arcs[arc].src;
    }

    bbID getDstBB(bbArcID arc) const {
        return Arcs[arc].dst;
    }

    void setProbability(bbArcID arc, double prob) {
        Arcs[arc].prob = prob;
    }

    double getProbability(bbArcID arc) const {
        return Arcs[arc].prob;
    }

    void setFrequencyArc(bbArcID arc, double freq) {
        Arcs[arc].freq = freq;
    }

    double getFrequencyArc(bbArcID arc) const {
        return Arcs[arc].freq;
    }

    bool calculateBackArcs();

    void setBackArc(bbArcID arc, bool back = true) {
        Arcs[arc].back = back;
    }

    bool isBackArc(bbArcID arc) const {
        return Arcs[arc].back;
    }

    setBBArcs& predecessors(bbID bb) {
        return BBs[bb - 1].pred;
    }

    setBBArcs& successors(bbID bb) {
        return BBs[bb - 1].succ;
    }

    void setFrequency(bbID bb, double f) {
        BBs[bb - 1].freq = f;
    }

    double getFrequency(bbID bb) const {
        return BBs[bb - 1].freq;
    }

    void setExecTime(bbID bb, double t) {
        BBs[bb - 1].exec = t;
    }

    double getExecTime(bbID bb) const {
        return BBs[bb - 1].exec;
    }

    double isEntryBB(bbID bb) {
        return entryBB == bb;
    }

    double getDFSorder(bbID bb) {
        return BBs[bb - 1].DFS_order;
    }

    void setDFSorder(bbID bb, int order) {
        BBs[bb - 1].DFS_order = order;
    }

    double getSCCnumber(bbID bb) {
        return BBs[bb - 1].SCC_number;
    }

    void setSCCnumber(bbID bb, int number) {
        BBs[bb - 1].SCC_number = number;
    }


    bool calculateBasicBlockFrequencies(double back_prob = 0.9);

     //SHAB_note: check this :-?
    double extractBasicBlockCycles(double coverage = -1.0);

    void DFS();

    void computeSCC();

    void setDSUnumberArc(bbArcID arc, int number) {
        assert (arc >= 0 && arc < numArcs());
        Arcs[arc].DSU_number = number;
    }

    void addMGnumber(bbArcID arc, int number) {
        assert (arc >= 0 && arc < numArcs());
        Arcs[arc].MG_numbers.push_back(number);
    }

    int getDSUnumberArc(bbArcID arc) {
        return Arcs[arc].DSU_number;
    }

    vector<int>& getMGnumbers(bbArcID arc) {
        return Arcs[arc].MG_numbers;
    }

    std::vector<bbID>& getBlocksInCycle(int cycle_number){
        return cycles[cycle_number].cycle;
    }

    int getCycleNum(){
        return cycles.size();
    }

private:
    // Structure to represent a Basic Block.
    struct BasicBlock {
        double freq;            // Execution frequency of the BB
        double exec;            // Execution time of the BB
        setBBArcs pred;         // Prededessor arcs
        setBBArcs succ;         // Successor arcs
        double residual_freq;   // Residual frequency (used to compute frequent cycles)
        bbID id;
        int DFS_order;
        int SCC_number;
    };

    // Arc connecting two BBs in the Basic Block Graph
    struct BB_Arc {
        bbID src;       // Src BB
        bbID dst;       // Dst BB
        bool back;      // Is it a back edge?
        double prob;    // Probability of taking the arc (-1 if undefined)
        bbArcID id;
        double freq;    // Execution frequency of the arc

        vector<int> MG_numbers;
        int DSU_number;
    };

    // Structure to represent a cycle in the Basic Block Graph.
    struct BasicBlockCycle {
        double freq;                // Execution frequency of the cycle
        double exec;                // Execution time of the cycle
        std::vector<bbID> cycle;    // Sequence of BBs (the last BB is connected to the first)
        std::vector<bool> executed; // A flag to denote which block is executed
    };

    std::vector<BasicBlock> BBs;    // List of basic blocks
    std::vector<BB_Arc> Arcs;       // List of arcs
    bbID entryBB;                   // Entry Basic Block
    setBBs exitBBs;                 // set of exit Basic Blocks
    std::vector<bbID> DFSorder;     // DFS order to get SCC of MGs

    std::vector<BasicBlockCycle> cycles;    // List of critical cycles

    void setDefaultProbabilities(double back_prob = 0.9);

    BasicBlockCycle extractBasicBlockCycle();
};

class DFnetlist_Impl
{

public:
    DFnetlist_Impl();

    DFnetlist_Impl(const std::string& name);

    DFnetlist_Impl(FILE* file);

    DFnetlist_Impl(const std::string& name, const std::string& name_bb);

    bool check();

    const std::string& getName() const;

    blockID createBlock(BlockType type, const std::string& name = "");

    blockID getBlock(const std::string& name) const;

    const std::string& getBlockName(blockID id) const;

    BlockType getBlockType(blockID id) const;

    std::string printBlockType(BlockType type) const;

    void printChannelInfo(channelID c, int slots, int transparent);

    bool isInnerChannel(channelID c);

    bool getChannelMerge(channelID c); //Carmine 09.03.22 these two functions are used to preserve 
    void setChannelMerge(channelID c); //Carmine 09.03.22 the information for writing the dot after reduceMerges function


    double getBlockDelay(blockID id, int indx) const;


    void setBasicBlock(blockID id, bbID bb = invalidDataflowID);

    bbID getBasicBlock(blockID id) const;

    void setBlockDelay(blockID id, double d, int indx);

    int getLatency(blockID id) const;

    void setLatency(blockID id, int lat);


    double getBlockRetimingDiff(blockID id) const;


    void setBlockRetimingDiff(blockID id, double diff);

    int getInitiationInterval(blockID id) const;

    void setInitiationInterval(blockID id, int ii);

    void setExecutionFrequency(blockID id, double freq);

    int getExecutionFrequency(blockID id) const;


    void setTrueFrac(blockID id, double freq);

    double getTrueFrac(blockID id) const;

    void setValue(blockID id, longValueType value);

    void setOperation(blockID id, std::string op);

    // Lana 02.07.19 
    const std::string& getOperation(blockID id) const;

    // Lana 03.07.19 
    void setMemPortID(blockID id, int memPortID);

    int getMemPortID(blockID id) const;

    void setMemOffset(blockID id, int memOffset);

    int getMemOffset(blockID id) const;

    void setMemBBCount(blockID id, int count);

    int getMemBBCount(blockID id) const;

    void setMemLdCount(blockID id, int count);

    int getMemLdCount(blockID id) const;

    void setMemStCount(blockID id, int count);

    int getMemStCount(blockID id) const;

    void setMemName(blockID id, std::string name);

    const std::string& getMemName(blockID id) const;

    void setMemPortSuffix(blockID id, std::string op);

    const std::string& getMemPortSuffix(blockID id) const;

    void setFuncName(blockID id, std::string op);

    const std::string& getFuncName(blockID id) const;

    void setOrderings(blockID id, map<bbID, vector<int>> value);

    // Lana 04/10/19

    void setLSQDepth(blockID id, int depth);

    int getLSQDepth(blockID id) const;

    void setNumLoads(blockID id, std::string name);

    const std::string& getNumLoads(blockID id) const;

    void setNumStores(blockID id, std::string name);

    const std::string& getNumStores(blockID id) const;

    void setLoadOffsets(blockID id, std::string name);

    const std::string& getLoadOffsets(blockID id) const;

    void setStoreOffsets(blockID id, std::string name);

    const std::string& getStoreOffsets(blockID id) const;

    void setLoadPorts(blockID id, std::string name);

    const std::string& getLoadPorts(blockID id) const;

    void setStorePorts(blockID id, std::string name);

    const std::string& getStorePorts(blockID id) const;

    void setGetPtrConst(blockID id, int c);

    int getGetPtrConst(blockID id) const;

    longValueType getValue(blockID id);

    bool getBoolValue(blockID id) const;

    int getBufferSize(blockID id) const;

    void setBufferSize(blockID id, int slots);

    bool isBufferTransparent(blockID id) const;

    void setBufferTransparency(blockID id, bool value);

    blockID getBlockFromPort(portID p) const;

    void removeBlock(blockID block);

    portID createPort(blockID block, bool isInput, const std::string& name="", int width = -1, PortType type = GENERIC_PORT);

    void removePort(portID port);

    portID getPort(blockID block, const std::string& name) const;

    const std::string& getPortName(portID port, bool full=true) const;

    PortType getPortType(portID port) const;

    bool isInputPort(portID port) const;

    bool isOutputPort(portID port) const;

    void setPortWidth(portID port, int width);

    int getPortWidth(portID port) const;

    bool isBooleanPort(portID port) const;

    bool isControlPort(portID port) const;

    bool isBooleanConstant(portID port, bool& value) const;

    double getPortDelay(portID port) const;

    void setPortDelay(portID port, double d);

    double getCombinationalDelay(portID inp, portID outp) const;

    const setPorts& getPorts(blockID id, PortDirection dir) const;

    const setPorts& getDefinitions(portID p) const;

    portID getConditionalPort(blockID id) const;

    portID getTruePort(blockID id) const;

    portID getFalsePort(blockID id) const;

    portID getDataPort(blockID id) const;

    portID getDemuxComplementaryPort(portID port) const;

    channelID getConnectedChannel(portID port) const;

    bool isPortConnected(portID port) const;

    portID getConnectedPort(portID port) const;

    channelID createChannel(portID src, portID dst, int slots = 0, bool transparent = true);

    void removeChannel(channelID id);

    portID getSrcPort(channelID id) const;

    portID getDstPort(channelID id) const;

    blockID getSrcBlock(channelID id) const;

    blockID getDstBlock(channelID id) const;

    string getChannelName(channelID id, bool full=true) const;

    channelID getChannelID(portID id); //Carmine 09.03.22 new function


    int getChannelBufferSize(channelID id) const;

    void setChannelBufferSize(blockID id, int slots);

    bool isChannelTransparent(channelID id) const;

    void setChannelTransparency(channelID id, bool value);


    void setChannelEB(channelID id);

    bool getChannelEB(channelID id);

    void setChannelFrequency(channelID id, double value);

    double getChannelFrequency(channelID id);

    bool hasBuffer(channelID id) const;

    blockID insertBuffer(channelID c, int slots, bool transparent);

    blockID insertBuffer(channelID c, int slots, bool transparent, bool EB);

    channelID removeBuffer(blockID buf);

    void setError(const std::string& err);

    const std::string& getError() const;

    std::string& getError();

    void clearError();

    bool hasError() const;

    int numBlocks() const;

    int numChannels() const;

    int numPorts() const;

    bool validPort(portID p) const;

    bool validBlock(blockID id) const;

    bool validChannel(channelID id) const;

    void reduceMerges(); //Carmine 09.03.22 new function

    void execute_reduction(blockID b);  //Carmine 09.03.22 function to eliminate  a block

    bool writeDot(const std::string& filename = "");

    bool writeDot(std::ostream& of);

    bool writeDotMG(const std::string& filename = "");
    bool writeDotMG(std::ostream& s);

    bool writeDotBB(const std::string& filename = "");
    bool writeDotBB(std::ostream& of);

    bool writeBasicBlockDot(const std::string& filename = "");

    bool writeBasicBlockDot(std::ostream& s);

    bool addElasticBuffers(double Period = 0, double BufferDelay = 0, bool MaxThroughput = false, double coverage = 0);

    bool addElasticBuffersBB(double Period = 0, double BufferDelay = 0, bool MaxThroughput = false, double coverage = 0, int timeout = -1, bool first_MG = false);
    bool addElasticBuffersBB_sc(double Period = 0, double BufferDelay = 0, bool MaxThroughput = false, double coverage = 0, int timeout = -1, bool first_MG = false, const std::string& model_mode = "default", const std::string& lib_path="");

    void addBorderBuffers();
    void findMCLSQ_load_channels();
    void instantiateElasticBuffers();

    void instantiateAdditionalElasticBuffers(const std::string& filename);


    void hideElasticBuffers();

    void cleanElasticBuffers();

    void setMilpSolver(const std::string& solver="cbc");

    void eraseNonSCC();

    bool calculateBasicBlocks();

    bool optimize();

    bool removeControl();

    double extractMarkedGraphs(double coverage);

    double extractMarkedGraphsBB(double coverage);

    void printBlockSCCs();
    void computeSCCpublic(bool onlyMarked) {
        computeSCC(onlyMarked);
    }

    setBlocks allBlocks;       // Set of blocks (for iterators)
    setPorts allPorts;         // Set of ports (for iterators)
    setChannels allChannels;   // Set of channels (for iterators)

    BasicBlockGraph BBG;        // Graph of Basic Blocks


private:

    struct Block {
        blockID id;                 // Id of the block (redundant, but useful)
        std::string name;           // Name of the block
        BlockType type;             // Type of block
        longValueType value;        // Value (only used for constants)
        bool boolValue;             // Boolean value (only used for constants)
        blockID nextFree;           // Next free block in the vector of blocks
        bbID basicBlock;            // Basic block to which the block belongs to
        double delay;               // Delay of the block
        double delays[8];           // Delays of the block //Andrea
        int latency;                // Latency of the block (only for Operators)
        int II;                     // Initiation interval of the block (only for Operators)
        int slots;                  // Number of slots (only for EBs)
        bool transparent;           // Is the buffer transparent? (only for EBs)
        setPorts inPorts;           // Set of input ports (id's)
        setPorts outPorts;          // Set of output ports (id's)
        setPorts allPorts;          // All ports of the block
        portID portCond;            // Port for condition (for branch/select)
        portID portTrue, portFalse; // True and false ports (for branch/select)
        portID data;                // Port for data (input for branch/demux, output for select)
        portID srcCond;             // Port that generates the condition for the branch (beyond forks)
        double freq;                // Execution frequency (obtained from profiling)
        double frac;                // True/false fraction of select inputs (obtained from profiling)
        double retimingDiff;        // Axel
        bool mark;                  // Flag used for traversals
        int scc_number;             // SCC number
        int DFSorder;               // Post-visit number during DFS traversal
        std::deque<portID> listPorts;       // Temporary list of input ports (for demux pairing)
        std::map<portID,portID> demuxPairs; // Pairs of ports in a demux. The pairs are in both directions.
        blockID bbParent;           // Disjoint set parent for BB calculation
        int bbRank;                 // Disjoint set rank for BB calculation
        std::string operation;      // Lana: arithmetic/memory operation (instruction)
        int memPortID;              // Lana: used to connect load/store to MC/LSQ
        int memOffset;              // Lana: used to connect load/store to MC/LSQ
        int memBBCount;             // Lana: number of BBs connected to MC/LSQ
        int memLdCount;             // Lana: number of loads connected to MC/LSQ
        int memStCount;             // Lana: number of stores connected to MC/LSQ
        std::string memName;        // LSQ/MC name
        std::string funcName;       // Lana: name of called function (for call instruction)
        int fifoDepth;              // Lana: LSQ depth
        // Lana: LSQ json configuration info
        std::string numLoads;       
        std::string numStores;
        std::string loadOffsets;
        std::string storeOffsets;
        std::string loadPorts;
        std::string storePorts;
        int getptrc; // Lana: constant for getelementpointer dimensions
        map<bbID, vector<int>> orderings; //Axel : used by selector to know order of execution
    };

    struct Port {
        portID id;              // Identifier of the port
        std::string short_name; // Name of the port
        std::string full_name;  // Full name of the port (block:port)
        blockID block;          // Owner of the port
        portID nextFree;        // Next free slot in the vector of ports
        bool isInput;           // Direction of the port
        int width;              // Width of the port (0: control, 1: boolean, >1: data)
        double delay;           // Delay associated to the port
        PortType type;          // Type: generic, selection, sel_true or sel_false
        channelID channel;      // Channel connected to the port
        setPorts defs;          // Set of definitions (ports) reaching this port
        std::string memPortSuffix;  // Lana: MC/LSQ port suffix, to distinguish port types of MC/LSQ
    };

    struct Channel {
        channelID id;               // Identifier of the channel
        portID src;                 // Source port (output port)
        portID dst;                 // Destination port (input port)
        int slots;                  // Number of slots (used to insert Elastic Buffers)
        bool transparent;           // Is the buffer transparent? (used to insert Elastic Buffers)
        bool backEdge;              // Indicates whether it is a back edge (after calculation of BBs)
        channelID nextFree;         // Next free slot in the vector of channels
        bool mark;                  // Flag used for traversals
        double freq;                // number of times this channels is executed
        bool EB = false;            // boolean to set the presence of an elastic buffer on the channel // Carmine 21.02.22 
        bool channelMerge = false;  // boolean to set the presence of merge after channel during reduceMerges function // Carmine 09.03.22
    };

    // Structure to represent a fragment of a netlist.
    // It is used for extracting SCCs and Marked Graphs.
    struct subNetlist {
        setBlocks blocks;       // Set of blocks in the subnetlist
        setChannels channels;   // Set of channels in the subnetlist

        // Constructor
        subNetlist() {}

        // Copy
        subNetlist(subNetlist const& other) :
            blocks(other.blocks), channels(other.channels) {}

        // Assignment
        subNetlist& operator=(subNetlist other) {
            other.swap(*this);
            return *this;
        }

        // Swap
        void swap(subNetlist& other) {
            using std::swap;
            swap(blocks, other.blocks);
            swap(channels, other.channels);
        }

        // Resets the subnetlist
        void clear() {
            blocks.clear();
            channels.clear();
        }

        // Is it empty?
        bool empty() const {
            return channels.empty() and blocks.empty();
        }

        // Number of blocks of the subnetlist
        int numBlocks() const {
            return blocks.size();
        }

        // Number of channels of the subnetlist
        int numChannels() const {
            return channels.size();
        }

        // Returns the set of blocks (not modifiable)
        const setBlocks& getBlocks() const {
            return blocks;
        }

        // Returns the set of channels
        const setChannels& getChannels() const {
            return channels;
        }

        // Checks whether a block is in the subnetlist
        bool hasBlock(blockID b) const {
            return blocks.count(b) > 0;
        }

        // Checks whether a channel is in the subnetlist
        bool hasChannel(channelID c) const {
            return channels.count(c) > 0;
        }

        // Inserts a block into the subnetlist
        void insertBlock(blockID b) {
            blocks.insert(b);
        }

        // Inserts a channel into the subnetlist.
        // The blocks connected to the channel are also inserted.
        void insertChannel(const DFnetlist_Impl& dfn, channelID c) {
            channels.insert(c);
            insertBlock(dfn.getBlockFromPort(dfn.getSrcPort(c)));
            insertBlock(dfn.getBlockFromPort(dfn.getDstPort(c)));
        }
    };

    struct subNetlistBB {
        set <bbID> BasicBlocks;
        set <bbArcID> BasicBlockArcs;

        int SCC_no;
        int min_freq; //todo: for now we're ignoring this

        int DSU_no;
        int DSU_parent;
        int DSU_rank;

        subNetlistBB(){
            BasicBlocks = {};
            BasicBlockArcs = {};
            clear();
        }

        void clear(){
            BasicBlocks.clear();
            BasicBlockArcs.clear();
            SCC_no = 0;
            min_freq = 0;
            DSU_rank = -1;
            DSU_parent = -1;
            DSU_no = -1;
        }

        bool empty(){
            return BasicBlocks.empty() and BasicBlockArcs.empty();
        }

        int numBasicBlocks(){
            return BasicBlocks.size();
        }

        int numBasicBlockArcs() {
            return BasicBlockArcs.size();
        }

        const set<bbID>& getBasicBlocks() {
            return BasicBlocks;
        }

        const set<bbArcID>& getBasicBlockArcs() {
            return BasicBlockArcs;
        }

        bool hasBasicBlock(bbID b) {
            return BasicBlocks.count(b) > 0;
        }

        bool hasBasicBlockArc(bbArcID a) {
            return BasicBlockArcs.count(a) > 0;
        }

        void insertBasicBlock(bbID b) {
            BasicBlocks.insert(b);
        }

        void insertBasicBlockArc(bbArcID a) {
            BasicBlockArcs.insert(a);
        }

        void merge(subNetlistBB& other) {
            for (bbID bb: other.getBasicBlocks()) {
                insertBasicBlock(bb);
            }

            for (bbArcID bbArc: other.getBasicBlockArcs()) {
                insertBasicBlockArc(bbArc);
            }
        }

        bool sameSCC(subNetlistBB other) {
            return SCC_no == other.getSCCnumber();
        }

        int getSCCnumber() {
            return SCC_no;
        }

        int setSCCnumber(int number) {
            SCC_no = number;
        }

        int getMinimumFreq() {
            return min_freq;
        }

        void setMinimumFreq(int freq) {
            min_freq = freq;
        }

        int getDSUnumber() {
            return DSU_no;
        }

        void setDSUnumber(int number) {
            DSU_no = number;
        }

        bool haveCommonBasicBlock(subNetlistBB &other) {
            for (bbID bb: other.getBasicBlocks()) {
                if (hasBasicBlock(bb)) {
                    return true;
                }
            }
            return false;
        }

        int getDSUParent() {
            return DSU_parent;
        }

        void setDSUParent(int parent) {
            DSU_parent = parent;
        }

        int getDSURank() {
            return DSU_rank;
        }

        void setDSURank(int rank) {
            DSU_rank = rank;
        }

        void increaseDSURank() {
            DSU_rank++;
        }
    };

    std::string net_name;   // Name of the DF net
    int default_width;      // Default width for the channels
    ErrorMgr error;      // Error message
    int nBlocks;            // Number of blocks
    int nChannels;          // Number of channels
    int nPorts;             // Number of ports
    funcID nextFree;        // Next free slot in a library of functions

    std::vector<Block> blocks;       // List of blocks
    std::vector<Port> ports;         // List of ports
    std::vector<Channel> channels;   // List of channels

    double total_freq;

    //double delays [250][8];

    int freeBlock;      // Next free Block in the vector of blocks
    int freePort;       // Next free Port in the vector of ports
    int freeChannel;    // Next free Channel in the vector of channels

    //setBlocks allBlocks;       // Set of blocks (for iterators)
    //setPorts allPorts;         // Set of ports (for iterators)
    //setChannels allChannels;   // Set of channels (for iterators)

    setBlocks parameters;       // Set of paramenters of the dataflow netlist (entry)
    setBlocks results;          // Set of results of the dataflow netlist (exit)
    blockID entryControl;       // Entry block for control
    setBlocks exitControl;      // Exit blocks

    //BasicBlockGraph BBG;        // Graph of Basic Blocks
    bbID entryBB;               // Entry basic block

    std::string milpSolver;     // Name of the MILP solver

    std::map<std::string,blockID> name2block; // Map to obtain blocks from names
    std::map<std::string,portID> name2port;   // Map to obtain ports from names (string = "block:port")

    // Maps from/to blokcs/ports to strings
    static std::map<BlockType,std::string> BlockType2String;
    static std::map<std::string,BlockType> String2BlockType;
    static std::map<PortType,std::string> PortType2String;
    static std::map<std::string,PortType> String2PortType;

    std::vector<blockID> DFSorder;  // DFS order according to the post-visit ordering (tail is an entry node)
    std::vector<subNetlist> SCC;    // SCCs with at least one channel (in descending order of size)

    std::vector<subNetlist> MG;     // Extracted marked graphs in order of importance
    std::vector<double> MGfreq;     // Execution frequency of Marked Graphs

    setBlocks blocks_in_MGs;
    setChannels channels_in_MGs;

    setBlocks blocks_in_borders;
    setChannels channels_in_borders;

    setBlocks blocks_in_MC_LSQ;
    setChannels channels_in_MC_LSQ;

    std::vector<subNetlist> MG_disjoint; // All marked graphs that make the disjoint sets
    std::vector<double> MG_disjoint_freq;

    std::vector<subNetlistBB> CFDFC;
    std::vector<double> CFDFCfreq;

    // SHAB_note: should be change this to a map?
    std::vector<subNetlistBB> CFDFC_disjoint;
    std::vector<double> CFDFC_disjoint_freq;

    std::vector<vector<int> > components;  // each index corresponds to the CFDFCs the DSU_CFDFC is built of

    // Structure to store the MILP variables
    // Note: the out_retime variables are only used for pipelined units (latency > 0)
    struct milpVarsEB {
        vector<int> buffer_flop;        // Elastic buffer to cut combinational paths
        vector<int> buffer_flop_valid;        //Carmine 17.02.22 // Elastic buffer to cut combinational valid paths
        vector<int> buffer_flop_ready;        //Carmine 17.02.22 // Elastic buffer to cut combinational ready paths
        vector<int> buffer_slots;       // Number of slots of the elastic buffer
        vector<int> has_buffer;         // Boolean variable to indicate whether there is a buffer
        vector<int> time_path;          // Combinational arrival time for ports
        vector<int> time_valid_path;    //Carmine 16.02.22 // Combinational arrival time for valid ports
        vector<int> time_ready_path;    //Carmine 17.02.22 // Combinational arrival time for ready ports
        vector<int> time_elastic;       // Arrival time for elasticity (longest rigid fragment)
        vector<vector<int>> in_retime_tokens;  // Input retiming variables for tokens (indices: [MarkedGraph,block])
        vector<vector<int>> out_retime_tokens; // Output retiming variables for tokens (indices: [MarkedGraph,block]).
        vector<vector<int>> retime_bubbles;    // Retiming variables for bubbles (indices: [MarkedGraph,block])
        vector<vector<int>> th_tokens;  // Throughput associated to every channel for tokens (indices: [MargedGraph, channel])
        vector<vector<int>> th_bubbles; // Throughput associated to every channel for bubbles (indices: [MargedGraph, channel])
        vector<int> th_MG;              // Throughput variables (one for each marked graph)
    };

    void init();

    int vecBlocksSize() const {
        return blocks.size();
    }

    int vecChannelsSize() const {
        return channels.size();
    }

    int vecPortsSize() const {
        return ports.size();
    }

    bool readDataflowDot(const std::string& filename);

    bool readDataflowDot(FILE* f);

    bool readDataflowDotBB(FILE *f);
    bool readDataflowDotBB(const std::string& filename);

    std::string genBlockName(BlockType type) const;

    bool checkPortsConnected(blockID id = invalidDataflowID);

    int numInPorts(blockID b) const {
        assert(validBlock(b));
        return blocks[b].inPorts.size();
    }

    int getBlockSCCno(blockID b) const {
        assert(validBlock(b));
        return blocks[b].scc_number;
    }
    int numOutPorts(blockID b) const {
        assert(validBlock(b));
        return blocks[b].outPorts.size();
    }

    portID getInPort(blockID b) const {
        if (blocks[b].inPorts.empty()) return invalidDataflowID;
        return *(blocks[b].inPorts.begin());
    }

    portID getOutPort(blockID b) const {
        if (blocks[b].outPorts.empty()) return invalidDataflowID;
        return *(blocks[b].outPorts.begin());
    }

    bool checkElasticBuffer(blockID b);

    bool checkFork(blockID b);

    bool checkBranch(blockID b);

    bool checkMerge(blockID b);

    bool checkSelect(blockID b);

    bool checkFunc(blockID b);

    bool checkConstant(blockID b);

    bool checkFuncEntry(blockID b);

    bool checkFuncExit(blockID b);

    bool checkDemux(blockID b);

    bool checkGenericPorts(blockID b);

    void inferChannelWidth(int default_width);

    bool checkSamePortWidth(portID p1, portID p2);

    bool checkSamePortWidth(const setPorts& P);

    bool checkNumPorts(blockID b, int nin, int nout);

    bool setAllBBFrequencies();
    bool determineEntryExitBlock();
    void computeChannelFrequencies();
    void computeBlockFrequencies();

    void writeBlockDot(std::ostream& s, blockID id);

    void writeChannelDot(std::ostream& s, channelID id);

    //SHAB_note: implement these
    void writeBasicBlockDot(std::ostream& s, bbID id);
    void writeArcDot(std::ostream& s, bbArcID id);

    void markAllBlocks(bool value) {
        ForAllBlocks(b) blocks[b].mark = value;
    }

    void markAllChannels(bool value) {
        ForAllChannels(c) channels[c].mark = value;
    }

    void markBlock(blockID b, bool value) {
        assert(validBlock(b));
        blocks[b].mark = value;
    }

    void setDFSorder(blockID b, int value) {
        assert(validBlock(b));
        blocks[b].DFSorder = value;
    }

    int getDFSorder(blockID b) const {
        assert(validBlock(b));
        return blocks[b].DFSorder;
    }

    void markChannel(channelID c, bool value) {
        assert(validChannel(c));
        channels[c].mark = value;
    }

    bool isBlockMarked(blockID b) const {
        assert(validBlock(b));
        return blocks[b].mark;
    }

    bool isChannelMarked(channelID c) const {
        assert(validChannel(c));
        return channels[c].mark;
    }

    void setBackEdge(channelID c, bool value = true) {
        assert(validChannel(c));
        channels[c].backEdge = value;
    }

    bool isBackEdge(channelID c) const {
        assert(validChannel(c));
        return channels[c].backEdge;
    }

    void DFS(bool forward = true, bool onlyMarked = false);

    void calculateBackEdges();

    void computeSCC(bool onlyMarked = false);

    const std::string& getMilpSolver() const {
        return milpSolver;
    }

    void createMilpVarsEB(Milp_Model& milp, milpVarsEB& vars, bool max_throughput, bool first_MG= false);
    void createMilpVarsEB_sc(Milp_Model& milp, milpVarsEB& vars, bool max_throughput, int mg, bool first_MG= false, string model_mode="default");
    void createMilpVars_remaining(Milp_Model& milp, milpVarsEB& vars, string model_mode);

    bool createPathConstraints(Milp_Model& milp, milpVarsEB& Vars, double Period, double BufferDelay);
    bool createPathConstraints_sc(Milp_Model& milp, milpVarsEB& Vars, double Period, double BufferDelay, int mg);
    bool createPathConstraintsOthers_sc(Milp_Model& milp, milpVarsEB& Vars, double Period, double BufferDelay, int mg, string model_mode, string lib_path);
    bool createPathConstraints_remaining(Milp_Model& milp, milpVarsEB& Vars, double Period, double BufferDelay);
    bool createPathConstraintsOthers_remaining(Milp_Model& milp, milpVarsEB& Vars, double Period, double BufferDelay, string model_mode, string lib_path);


    vector< pair<string, vector<double>>> read_lib_file(string lib_file_path); //Carmine 18.02.22 function to read block delays values from library
    bool createElasticityConstraints(Milp_Model& milp, milpVarsEB& Vars);
    bool createElasticityConstraints_sc(Milp_Model& milp, milpVarsEB& Vars, int mg);
    bool createElasticityConstraints_remaining(Milp_Model& milp, milpVarsEB& Vars);

    bool createThroughputConstraints(Milp_Model& milp, milpVarsEB& Vars, bool first_MG= false);
    bool createThroughputConstraints_sc(Milp_Model& milp, milpVarsEB& Vars, int mg, bool first_MG= false);

    bool channelIsInMGs(channelID c);
    bool blockIsInMGs(blockID b);

    bool channelIsInBorders(channelID c);
    bool blockIsInBorders(blockID b);

    bool channelIsInMCLSQ(channelID c);
    bool blockIsInMCLSQ(blockID b);

    bool channelIsCovered(channelID c, bool MG, bool borders, bool MC_LSQ);
    bool blockIsCovered(blockID b, bool MG, bool borders, bool MC_LSQ);
    void dumpMilpSolution(const Milp_Model& milp, const milpVarsEB& vars) const;

    void writeRetimingDiffs(const Milp_Model& milp, const milpVarsEB& vars);

    void makeNonTransparentBuffers();

    bool removeUnreachableBlocksAndPorts();

    bool removeConstantBranchSelect();

    bool removeOneInOneOutMergeForkDemux();

    bool collapseMergeFork();

    void makeDisjointBB(blockID b);

    blockID findDisjointBB(blockID b);

    bool unionDisjointBB(blockID b1, blockID b2);

    void invalidateBasicBlocks();

    void calculateDefinitions();

    subNetlist extractMarkedGraph(const map<blockID, double>& freq);

    subNetlistBB extractMarkedGraphBB(const map<bbID, double>& freq);

    subNetlist getMGfromCFDFC(subNetlistBB &BB_CFDFC);

    void calculateDisjointCFDFCs();
    int findCFDFC(int i);
    void unionCFDFC(int x, int y);

    void makeMGsfromCFDFCs();


    void setUnitDelays();

    bool removeFakeBranches();

public :
    //added for convenience, probably remove later
    std::vector<Block> & getBlocks(){
        return blocks;       // List of blocks
    }
    std::vector<Port> & getPorts(){
        return ports;// List of ports
    }
    std::vector<Channel> & getChannels(){
        return channels;// List of channels
    }
};

class DFlib_Impl
{
public:

    DFlib_Impl() {
        init();
    }

    DFlib_Impl(const string& filename);

    bool add(const string& filename);

    bool writeDot(const std::string& filename = "");

    bool writeDot(std::ostream& s);

    void setError(const std::string& err) {
        error.set(err);
    }

    const std::string& getError() const {
        return error.get();
    }

    std::string& getError() {
        return error.get();
    }

    void clearError() {
        error.clear();
    }

    bool hasError() const {
        return error.exists();
    }

    int numFuncs() const {
        return nFuncs;
    }

    funcID getFuncID(const string& fname) const {
        auto it = name2func.find(fname);
        if (it == name2func.end()) return invalidDataflowID;
        return it->second;
    }

    DFnetlist& operator[](const string& fname) {
        funcID id = getFuncID(fname);
        assert (id != invalidDataflowID);
        return funcs[id];
    }

    const DFnetlist& operator[](const string& fname) const {
        funcID id = getFuncID(fname);
        assert (id != invalidDataflowID);
        return funcs[id];
    }

    DFnetlist& operator[](funcID id) {
        assert (allFuncs.count(id) > 0);
        return funcs[id];
    }

    const DFnetlist& operator[](funcID id) const {
        assert (allFuncs.count(id) > 0);
        return funcs[id];
    }

private:
    std::string libName;    // Name of the DF library
    ErrorMgr error;         // Error manager
    int nFuncs;             // Number of functions (DF netlists)
    int freeDF;             // Next free slot in the vector of functions

    vector<DFnetlist> funcs;        // Vector of functions (index corresponds to funcID)
    map<string, funcID> name2func;  // Map from function name to funcID
    set<funcID> allFuncs;           // Set of all valid funcID's

    void init();
};

}

#endif // DATAFLOW_IMPL_H