OA Gear Fpga: oagFpgaRtlGraph.h Source File

00001 
00002 #if !defined(oagRtlGraph_P)
00003 #define oagRtlGraph_P
00004 
00005 #include "oaDesignDB.h"  
00006 #include "oagAiGraph.h"
00007 #include <assert.h>
00008 #include <vector>
00009 #include <list>
00010 #include <set>
00011 
00012 using namespace std;
00013 
00014 namespace oagFpga {
00015 
00016 class Manager;
00017 
00018 typedef unsigned int BBRef;
00019 typedef list<BBRef> BBRefBus;
00020 
00021 // *****************************************************************************
00022 // RtlNode 
00023 //
00027 // *****************************************************************************
00028 
00029 class RtlNode {
00030 
00031     friend class RtlGraph;
00032 
00033     public:
00034 
00035     // *****************************************************************************
00036     // Sequential BBNode Model
00037     // 
00038     //        clock--------+
00039     //                     |
00040     //                ----------
00041     //        aLoad---|>   V   |
00042     //                |        |
00043     //        aData---|>       |---out
00044     //                |        |
00045     //            D---|>       |
00046     //                ----------
00047     // *****************************************************************************
00048 
00049     class RtlSeqNodeInfo {
00050         public:
00051             BBRef D;        // pre-state
00052             BBRef clock;    // clock signal for a DFF or enable for latch
00053             BBRef aLoad;    // asynchronous load
00054             BBRef aData;    // data for asynchronous load
00055         public:
00056             RtlSeqNodeInfo(BBRef d, BBRef c, BBRef al, BBRef
00057                     ad):D(d),clock(c),aLoad(al),aData(ad){}
00058     };
00059 
00060     class RtlMuxNodeInfo {
00061         public:
00062             list<BBRef> in;
00063             list<BBRef> sel;   
00064     };
00065 
00066     class RtlOptNodeInfo {
00067         public:
00068             list<BBRef> op1;
00069             list<BBRef> op2;
00070             list<BBRef> op3;
00071             // assume that the maximum number of operands is 3
00072     };
00073 
00074     public:
00075 
00076         // *****************************************************************************
00077         // FuncType
00078         //
00089         //
00090         // *****************************************************************************
00091 
00092         typedef enum {NULL_FUNC, TERMINAL, CONTROL, OPERATOR, SEQ,
00093                         CONSTANT0, CONSTANT1} FuncType;
00094         static const char* funcTypeName [] ;
00095 
00096         // *****************************************************************************
00097         // OptType
00098         //
00112         //
00113         // *****************************************************************************
00114 
00115         typedef enum {
00116             UNKNOWN, PRIMARY, BUNDLE, BITWISE_AND, BITWISE_NAND, BITWISE_OR, BITWISE_NOR,
00117             BITWISE_XOR, BITWISE_XNOR, BITWISE_NOT, LOGICAL_AND, LOGICAL_NOT, LOGICAL_OR,
00118             REDUCTION_AND, REDUCTION_OR, REDUCTION_XOR, REDUCTION_NAND, REDUCTION_NOR,
00119             REDUCTION_XNOR, LESS_THAN, LESS_THAN_EQUAL, GREATER_THAN, GREATER_THAN_EQUAL,
00120             EQUAL, NOTEQUAL, IF_ELSE, LEFT_SHIFT, RIGHT_SHIFT, ADD, SUBTRACT, MULTIPLY, 
00121             DIVIDE, MODULO, NEGATE
00122         } OptType;
00123         static const char* optTypeName [] ;
00124 
00125         typedef enum {
00126             DFF,
00127             LATCH
00128         } SeqType;
00129         static const char* seqTypeName [] ;
00130 
00131         FuncType    funcType;
00132         union {
00133             OptType     optType;
00134             SeqType     seqType;
00135         };     
00136 
00137         // information for a sequential node (applicable only when
00138         // funcType==SEQ)
00139         union {
00140             RtlOptNodeInfo* optInfo;
00141             RtlMuxNodeInfo* muxInfo;
00142             RtlSeqNodeInfo* seqInfo;
00143         };
00144 
00145         // unique identification of the RtlNode, refer to the position of this
00146         // RtlNode in *nodes* field of *RtlGraph*, starting from 0.
00147         BBRef self;
00148 
00149         // auxiliary fields for graph traversal
00150         unsigned int traversalID;
00151 
00152         // connection between this RtlNode and other RtlNodes
00153         list<BBRef> fanin;
00154         list<BBRef> fanout;
00155 
00156         // mapping from the output bits to the correspoding AI nodes,
00157         // the size of this vector should be equal to "numOutputBits"
00158         vector<oagAi::Ref> aiRef;
00159 
00160         // a pointer for extension 
00161         void* externalTerminalConnection;
00162 
00163         int numOutputBits;
00164     
00165         // constructors
00166 
00167         RtlNode() {
00168             funcType = NULL_FUNC; externalTerminalConnection = NULL; 
00169             optInfo = NULL; muxInfo = NULL; seqInfo = NULL;
00170             // the default value of output bit number is 1
00171             numOutputBits = 1;
00172             // the initial value of traversalID is 0, note that a valid value of
00173             // RtlGraph::currentTraversalID can never be 0
00174             traversalID = 0;
00175         }
00176         RtlNode(FuncType ft) { 
00177             RtlNode(); funcType = ft;
00178         }
00179         RtlNode(FuncType ft, OptType ot) {
00180             RtlNode();
00181             assert(ft == OPERATOR); funcType = ft, optType = ot; 
00182         }
00183         RtlNode(FuncType ft, SeqType st) {
00184             RtlNode();
00185             assert(ft == OPERATOR); funcType = ft, seqType = st; 
00186         }
00187 
00188         ~RtlNode() {
00189             if(funcType == OPERATOR && optInfo) delete optInfo;
00190             else if(funcType == CONTROL && muxInfo) delete muxInfo;
00191             else if(funcType == SEQ && seqInfo) delete seqInfo;
00192         }
00193 
00194 };
00195 
00196 // *****************************************************************************
00197 // RtlGraph
00198 //
00202 // *****************************************************************************
00203 
00204 class RtlGraph {
00205     friend class Manager;
00206     friend class ModuleCompiler;
00207 
00208     public:
00209 
00211 
00212         RtlGraph() {
00213 
00214             // NULL_BBREF must be created when construction
00215             RtlNode* node = newNode();
00216             addNode(node);
00217             node->aiRef.push_back(oagAi::Graph::getNull());
00218             assert(node->self == NULL_BBREF);
00219 
00220             // create CONSTANT0_BBREF
00221             node = newNode();
00222             addNode(node);
00223             CONSTANT0_BBREF = node->self;
00224             node->funcType = RtlNode::CONSTANT0;
00225 
00226             // create CONSTANT1_BBREF
00227             node = newNode();
00228             addNode(node);
00229             CONSTANT1_BBREF = node->self;
00230             node->funcType = RtlNode::CONSTANT1;
00231 
00232             currentTraversalID = 1;
00233         }
00234         ~RtlGraph() {}
00235 
00237 
00238         // create a RtlNode by setup the internal attribution of a RtlNode
00239         BBRef unaryOpt(RtlNode::OptType ot, BBRef driver); 
00240         BBRef binaryOpt(RtlNode::OptType ot, BBRef in1, BBRef in2) ;
00241         BBRef unaryBusOpt(RtlNode::OptType ot, vector<BBRef>& ins) ;
00242         BBRef binaryBusOpt(RtlNode::OptType ot, vector<BBRef>& in1, vector<BBRef>& in2) ;
00243         void binaryBusInputOutputOpt(RtlNode::OptType ot, int numOutBits, vector<BBRef>& in1, 
00244                     vector<BBRef>& in2, vector<BBRef>& out) ;
00245         void unaryBusInputOutputOpt(RtlNode::OptType ot, int numOutBits, 
00246                     vector<BBRef>& in1, vector<BBRef>& out) ;
00247         BBRef bitSeq(RtlNode::SeqType st, BBRef D) ;
00248         BBRef bitSeq(RtlNode::SeqType st, BBRef D, BBRef clock, BBRef aLoad,
00249                 BBRef aData) ;
00250         BBRef bitMux(BBRef in1, BBRef in2, BBRef sel) ;
00251         BBRef busMux(vector<BBRef>& in, vector<BBRef>& sel);
00252         void busMux(vector<BBRef>& in1, vector<BBRef>& in2, vector<BBRef>& sel,
00253                     vector<BBRef>& outputs) ;
00254 
00255         // add a black box element into the bb list
00256         void addNode(RtlNode* node);
00257 
00258         // build connections between all RtlNodes in this graph according to the
00259         // port connection
00260         void buildNetlist() {}
00261 
00262         void setExternalTerminalConnection(BBRef ref, void* connection) {
00263             RtlNode* node = getNode(ref);
00264             assert(node);
00265             assert(node->funcType == RtlNode::TERMINAL);
00266             node->externalTerminalConnection = connection;
00267         }
00268 
00269         RtlNode* newNode() ;
00270 
00271         BBRef newTerminal(BBRef driver);
00272 
00273         inline BBRef getTerminalDriver(BBRef terminal) {
00274             RtlNode *node = getNode(terminal);
00275             assert(node);
00276             assert(node->funcType == RtlNode::TERMINAL);
00277             assert(node->fanin.size() == 1);
00278             return node->fanin.front();
00279         }
00280 
00281         inline BBRef getNextState(BBRef seq) const {
00282             RtlNode* node = getNode(seq);
00283             assert(node);
00284             assert(node->funcType == RtlNode::SEQ);
00285             assert(node->seqInfo);
00286             return node->seqInfo->D;
00287         }
00288 
00289         inline int getNumOutputBits(BBRef x) const {
00290             return getNode(x)->numOutputBits;
00291         }
00292 
00293         inline int getPrimaryBBID(BBRef x) const {
00294             return getNode(x)->self;
00295         }
00296 
00297         inline const list<BBRef>& getFanin(BBRef x) {
00302             return getNode(x)->fanin;
00303         }
00304 
00305         inline const list<BBRef>& getFanout(BBRef x) {
00310             return getNode(x)->fanout;
00311         }
00312 
00313         inline bool hasFanout(BBRef x) const {
00318             return (getNode(x)->fanout.size()>0);
00319 
00320         }
00321 
00322         void removeFromFanout(BBRef x, BBRef fanout) ;   
00323         void setTerminalDriver(BBRef terminal, BBRef driver) ; 
00324 
00326 
00327         RtlNode* getNode(BBRef ref) const {
00328             return bbNodes[ref];
00329         }
00330 
00331         RtlNode::FuncType getNodeType(BBRef ref) const {
00332             return getNode(ref)->funcType;
00333         }
00334 
00335         RtlNode::OptType getNodeOptType(BBRef ref) const {
00336             assert(getNode(ref)->funcType == RtlNode::OPERATOR);
00337             return getNode(ref)->optType;
00338         }
00339 
00340         RtlNode::SeqType getNodeSeqType(BBRef ref) const {
00341             assert(getNode(ref)->funcType == RtlNode::SEQ);
00342             return getNode(ref)->seqType;
00343         }
00344 
00345         bool isTerminal(BBRef x) const {
00346             RtlNode* node = getNode(x);
00347             assert(node);
00348             return (node->funcType == RtlNode::TERMINAL);
00349         }
00350 
00351         bool isFunctional(BBRef x) const {
00352             RtlNode* node = getNode(x);
00353             assert(node);
00354             return (node->funcType == RtlNode::CONTROL ||
00355                     node->funcType == RtlNode::OPERATOR); 
00356         }
00357 
00358         bool isSequential(BBRef x) const {
00359             RtlNode* node = getNode(x);
00360             assert(node);
00361             return (node->funcType == RtlNode::SEQ);
00362         }
00363 
00364         void* getExternalTerminalConnection(BBRef terminal) const {
00365             RtlNode *node = getNode(terminal);
00366             assert(node);
00367             assert(node->funcType == RtlNode::TERMINAL);
00368             return node->externalTerminalConnection;
00369         }    
00370 
00372         
00373         unsigned int    newTraversalID();
00374         inline void     markVisited(BBRef x) {
00378             getNode(x)->traversalID = currentTraversalID;
00379         }
00380         inline void     unmarkVisited(BBRef x) {
00384             getNode(x)->traversalID = 0;
00385         }
00386         inline bool     isVisited(BBRef x) const {
00388             //traversal.
00391             return getNode(x)->traversalID == currentTraversalID;
00392         }
00393 
00394         bool hasCombinationalCycle(); 
00395         void getTransitiveFanin(BBRef x, list<BBRef> &transitiveFanin, 
00396                 bool includeRoots = true, bool crossSequential = false);
00397         void getTransitiveFanin(BBRef x, vector<BBRef> &transitiveFanin, 
00398                 bool includeRoots = true, bool crossSequential = false);
00399         void getTransitiveFanin(list<BBRef> x, list<BBRef> &transitiveFanin, 
00400                 bool includeRoots = true, bool crossSequential = false);
00401         void getTransitiveFanin(list<BBRef> x, vector<BBRef> &transitiveFanin, 
00402                 bool includeRoots = true, bool crossSequential = false);
00403         void getTransitiveFanout(BBRef x, list<BBRef> &transitiveFanout, 
00404                 bool includeRoots = true, bool crossSequential = false);
00405         void getTransitiveFanout(BBRef x, vector<BBRef> &transitiveFanout, 
00406                 bool includeRoots = true, bool crossSequential = false);
00407         void getTransitiveFanout(list<BBRef> x, list<BBRef> &transitiveFanout, 
00408                 bool includeRoots = true, bool crossSequential = false);
00409         void getTransitiveFanout(list<BBRef> x, vector<BBRef> &transitiveFanout, 
00410                 bool includeRoots = true, bool crossSequential = false);
00411 
00413 
00414         void getTransitiveFanin_recursive(BBRef x, vector<BBRef> &transitiveFanin,
00415               bool includeRoots, bool crossSequential = false);
00416         void getTransitiveFanout_recursive(BBRef x, vector<BBRef>
00417               &transitiveFanout, bool includeRoots, 
00418               bool crossSequential = false);
00419         void getTransitiveFanin_recursive(BBRef x, list<BBRef>
00420               &transitiveFanin, bool includeRoots, bool crossSequential = false);
00421         void getTransitiveFanout_recursive(BBRef x, list<BBRef>
00422               &transitiveFanout, bool includeRoots, bool crossSequential = false);
00423         bool   hasCombinationalCycle_recursive(BBRef x, unsigned int
00424                 startingTraversalID);
00425 
00426 
00428 
00429         // *****************************************************************************
00435         //      equal to the first slot id in bbNodes array, each slot (with different
00436         //      BBRef) represents an output bit for this node, and this is used for
00437         //      its fanouts to refer to the correct output bit.
00438         // *****************************************************************************
00439         inline BBRef getOutputBit(BBRef ref) { 
00440             BBRef self = getNode(ref)->self;
00441             assert(ref >= self && ref <= self+getNode(ref)->numOutputBits);
00442             assert(ref >= self); 
00443             return ref - self; 
00444         }
00445 
00446         int getBBNodeNum() {
00447             return bbNodes.size();
00448         }
00449 
00451 
00452         static inline BBRef getNull() { return NULL_BBREF; }
00453         static inline bool  isNull(BBRef ref) { return ref == NULL_BBREF; }
00454 
00455         inline BBRef constantZero() const { return CONSTANT0_BBREF; }
00456         inline BBRef constantOne() const { return CONSTANT1_BBREF; }
00457 
00458         void print(ostream& os);
00459         void print(ostream& os, RtlNode* node);
00460 
00461     protected:
00462 
00463         // all black box nodes in RtlGraph (may contain repeated RtlNodes (see
00464         // Fanout model of black box node)
00465         vector<RtlNode*>    bbNodes;
00466 
00467         // all unique black box nodes in RtlGraph
00468         vector<RtlNode*>    dataBBNodes;
00469 
00470         static const BBRef  NULL_BBREF = 0;
00471         BBRef               CONSTANT0_BBREF;
00472         BBRef               CONSTANT1_BBREF;
00473 
00474         // auxiliary fields for graph traversal
00475         unsigned int        currentTraversalID;
00476 
00477 };
00478 
00479 }
00480 
00481 #endif