abc70930: src/map/if/if.h Source File

00001 
00021 #ifndef __IF_H__
00022 #define __IF_H__
00023 
00024 #ifdef __cplusplus
00025 extern "C" {
00026 #endif
00027 
00031 
00032 #include <stdio.h>
00033 #include <stdlib.h>
00034 #include <string.h>
00035 #include <assert.h>
00036 #include <time.h>
00037 #include "vec.h"
00038 #include "mem.h"
00039 
00043  
00044 // the maximum size of LUTs used for mapping (should be the same as FPGA_MAX_LUTSIZE defined in "fpga.h"!!!)
00045 #define IF_MAX_LUTSIZE       32
00046 // the largest possible number of LUT inputs when funtionality of the LUTs are computed
00047 #define IF_MAX_FUNC_LUTSIZE  15
00048 // a very large number
00049 #define IF_INFINITY          100000000  
00050 // the largest possible user cut cost
00051 #define IF_COST_MAX          ((1<<14)-1)
00052 
00053 // object types
00054 typedef enum { 
00055     IF_NONE,     // 0: non-existent object
00056     IF_CONST1,   // 1: constant 1 
00057     IF_CI,       // 2: combinational input
00058     IF_CO,       // 3: combinational output
00059     IF_AND,      // 4: AND node
00060     IF_VOID      // 5: unused object
00061 } If_Type_t;
00062 
00066 
00067 typedef struct If_Man_t_     If_Man_t;
00068 typedef struct If_Par_t_     If_Par_t;
00069 typedef struct If_Lib_t_     If_Lib_t;
00070 typedef struct If_Obj_t_     If_Obj_t;
00071 typedef struct If_Cut_t_     If_Cut_t;
00072 typedef struct If_Set_t_     If_Set_t;
00073 
00074 // parameters
00075 struct If_Par_t_
00076 {
00077     // user-controlable paramters
00078     int                nLutSize;      // the LUT size
00079     int                nCutsMax;      // the max number of cuts
00080     int                nFlowIters;    // the number of iterations of area recovery
00081     int                nAreaIters;    // the number of iterations of area recovery
00082     float              DelayTarget;   // delay target
00083     int                fPreprocess;   // preprossing
00084     int                fArea;         // area-oriented mapping
00085     int                fFancy;        // a fancy feature
00086     int                fExpRed;       // expand/reduce of the best cuts
00087     int                fLatchPaths;   // reset timing on latch paths
00088     int                fSeqMap;       // sequential mapping
00089     int                fVerbose;      // the verbosity flag
00090     // internal parameters
00091     int                fAreaOnly;     // area only mode
00092     int                fTruth;        // truth table computation enabled
00093     int                fUsePerm;      // use permutation (delay info)
00094     int                fUseBdds;      // use local BDDs as a cost function
00095     int                fUseSops;      // use local SOPs as a cost function
00096     int                fUseCnfs;      // use local CNFs as a cost function
00097     int                fUseMv;        // use local MV-SOPs as a cost function
00098     int                nLatches;      // the number of latches in seq mapping
00099     int                fLiftLeaves;   // shift the leaves for seq mapping
00100     If_Lib_t *         pLutLib;       // the LUT library
00101     float *            pTimesArr;     // arrival times
00102     float *            pTimesReq;     // required times
00103     int (* pFuncCost)  (If_Cut_t *);  // procedure to compute the user's cost of a cut
00104     int (* pFuncUser)  (If_Man_t *, If_Obj_t *, If_Cut_t *); //  procedure called for each cut when cut computation is finished
00105     void *             pReoMan;       // reordering manager
00106 };
00107 
00108 // the LUT library
00109 struct If_Lib_t_
00110 {
00111     char *             pName;         // the name of the LUT library
00112     int                LutMax;        // the maximum LUT size 
00113     int                fVarPinDelays; // set to 1 if variable pin delays are specified
00114     float              pLutAreas[IF_MAX_LUTSIZE+1]; // the areas of LUTs
00115     float              pLutDelays[IF_MAX_LUTSIZE+1][IF_MAX_LUTSIZE+1];// the delays of LUTs
00116 };
00117 
00118 // manager
00119 struct If_Man_t_
00120 {
00121     // mapping parameters
00122     If_Par_t *         pPars;
00123     // mapping nodes
00124     If_Obj_t *         pConst1;       // the constant 1 node
00125     Vec_Ptr_t *        vCis;          // the primary inputs
00126     Vec_Ptr_t *        vCos;          // the primary outputs
00127     Vec_Ptr_t *        vObjs;         // all objects
00128     Vec_Ptr_t *        vMapped;       // objects used in the mapping
00129     Vec_Ptr_t *        vTemp;         // temporary array
00130     int                nObjs[IF_VOID];// the number of objects by type
00131     // various data
00132     int                nLevelMax;     // the max number of AIG levels
00133     float              fEpsilon;      // epsilon used for comparison
00134     float              RequiredGlo;   // global required times
00135     float              RequiredGlo2;  // global required times
00136     float              AreaGlo;       // global area
00137     int                nNets;         // the sum total of fanins of all LUTs in the mapping
00138     int                nCutsUsed;     // the number of cuts currently used
00139     int                nCutsMerged;   // the total number of cuts merged
00140     unsigned *         puTemp[4];     // used for the truth table computation
00141     int                SortMode;      // one of the three sorting modes
00142     int                fNextRound;    // set to 1 after the first round
00143     int                nChoices;      // the number of choice nodes
00144     // sequential mapping
00145     Vec_Ptr_t *        vLatchOrder;   // topological ordering of latches
00146     Vec_Int_t *        vLags;         // sequentail lags of all nodes
00147     int                nAttempts;     // the number of attempts in binary search
00148     int                nMaxIters;     // the maximum number of iterations
00149     int                Period;        // the current value of the clock period (for seq mapping)
00150     // memory management
00151     int                nTruthWords;   // the size of the truth table if allocated
00152     int                nPermWords;    // the size of the permutation array (in words)
00153     int                nObjBytes;     // the size of the object
00154     int                nCutBytes;     // the size of the cut
00155     int                nSetBytes;     // the size of the cut set
00156     Mem_Fixed_t *      pMemObj;       // memory manager for objects (entrysize = nEntrySize)
00157     Mem_Fixed_t *      pMemSet;       // memory manager for sets of cuts (entrysize = nCutSize*(nCutsMax+1))
00158     If_Set_t *         pMemCi;        // memory for CI cutsets
00159     If_Set_t *         pMemAnd;       // memory for AND cutsets
00160     If_Set_t *         pFreeList;     // the list of free cutsets
00161 };
00162 
00163 // priority cut
00164 struct If_Cut_t_
00165 {
00166     float              Delay;         // delay of the cut
00167     float              Area;          // area (or area-flow) of the cut
00168     float              AveRefs;       // the average number of leaf references
00169     unsigned           uSign;         // cut signature
00170     unsigned           Cost    : 14;  // the user's cost of the cut
00171     unsigned           fCompl  :  1;  // the complemented attribute 
00172     unsigned           fUser   :  1;  // using the user's area and delay
00173     unsigned           nLimit  :  8;  // the maximum number of leaves
00174     unsigned           nLeaves :  8;  // the number of leaves
00175     int *              pLeaves;       // array of fanins
00176     char *             pPerm;         // permutation
00177     unsigned *         pTruth;        // the truth table
00178 };
00179 
00180 // set of priority cut
00181 struct If_Set_t_
00182 {
00183     short              nCutsMax;      // the max number of cuts
00184     short              nCuts;         // the current number of cuts
00185     If_Set_t *         pNext;         // next cutset in the free list
00186     If_Cut_t **        ppCuts;        // the array of pointers to the cuts
00187 };
00188 
00189 // node extension
00190 struct If_Obj_t_
00191 {
00192     unsigned           Type    :  4;  // object
00193     unsigned           fCompl0 :  1;  // complemented attribute
00194     unsigned           fCompl1 :  1;  // complemented attribute
00195     unsigned           fPhase  :  1;  // phase of the node
00196     unsigned           fRepr   :  1;  // representative of the equivalence class
00197     unsigned           fMark   :  1;  // multipurpose mark
00198     unsigned           fVisit  :  1;  // multipurpose mark
00199     unsigned           Level   : 22;  // logic level of the node
00200     int                Id;            // integer ID
00201     int                nRefs;         // the number of references
00202     int                nVisits;       // the number of visits to this node
00203     int                nVisitsCopy;   // the number of visits to this node
00204     If_Obj_t *         pFanin0;       // the first fanin 
00205     If_Obj_t *         pFanin1;       // the second fanin
00206     If_Obj_t *         pEquiv;        // the choice node
00207     float              EstRefs;       // estimated reference counter
00208     float              Required;      // required time of the onde
00209     float              LValue;        // sequential arrival time of the node
00210     void *             pCopy;         // used for object duplication
00211     If_Set_t *         pCutSet;       // the pointer to the cutset
00212     If_Cut_t           CutBest;       // the best cut selected 
00213 };
00214 
00215 static inline If_Obj_t * If_Regular( If_Obj_t * p )                          { return (If_Obj_t *)((unsigned long)(p) & ~01);  }
00216 static inline If_Obj_t * If_Not( If_Obj_t * p )                              { return (If_Obj_t *)((unsigned long)(p) ^  01);  }
00217 static inline If_Obj_t * If_NotCond( If_Obj_t * p, int c )                   { return (If_Obj_t *)((unsigned long)(p) ^ (c));  }
00218 static inline int        If_IsComplement( If_Obj_t * p )                     { return (int )(((unsigned long)p) & 01);         }
00219 
00220 static inline int        If_ManCiNum( If_Man_t * p )                         { return p->nObjs[IF_CI];               }
00221 static inline int        If_ManCoNum( If_Man_t * p )                         { return p->nObjs[IF_CO];               }
00222 static inline int        If_ManAndNum( If_Man_t * p )                        { return p->nObjs[IF_AND];              }
00223 static inline int        If_ManObjNum( If_Man_t * p )                        { return Vec_PtrSize(p->vObjs);         }
00224 
00225 static inline If_Obj_t * If_ManConst1( If_Man_t * p )                        { return p->pConst1;                              }
00226 static inline If_Obj_t * If_ManCi( If_Man_t * p, int i )                     { return (If_Obj_t *)Vec_PtrEntry( p->vCis, i );  }
00227 static inline If_Obj_t * If_ManCo( If_Man_t * p, int i )                     { return (If_Obj_t *)Vec_PtrEntry( p->vCos, i );  }
00228 static inline If_Obj_t * If_ManLi( If_Man_t * p, int i )                     { return (If_Obj_t *)Vec_PtrEntry( p->vCos, If_ManCoNum(p) - p->pPars->nLatches + i );  }
00229 static inline If_Obj_t * If_ManLo( If_Man_t * p, int i )                     { return (If_Obj_t *)Vec_PtrEntry( p->vCis, If_ManCiNum(p) - p->pPars->nLatches + i );  }
00230 static inline If_Obj_t * If_ManObj( If_Man_t * p, int i )                    { return (If_Obj_t *)Vec_PtrEntry( p->vObjs, i ); }
00231 
00232 static inline int        If_ObjIsConst1( If_Obj_t * pObj )                   { return pObj->Type == IF_CONST1;       }
00233 static inline int        If_ObjIsCi( If_Obj_t * pObj )                       { return pObj->Type == IF_CI;           }
00234 static inline int        If_ObjIsCo( If_Obj_t * pObj )                       { return pObj->Type == IF_CO;           }
00235 static inline int        If_ObjIsPi( If_Obj_t * pObj )                       { return If_ObjIsCi(pObj) && pObj->pFanin0 == NULL; }
00236 static inline int        If_ObjIsLatch( If_Obj_t * pObj )                    { return If_ObjIsCi(pObj) && pObj->pFanin0 != NULL; }
00237 static inline int        If_ObjIsAnd( If_Obj_t * pObj )                      { return pObj->Type == IF_AND;          }
00238 
00239 static inline If_Obj_t * If_ObjFanin0( If_Obj_t * pObj )                     { return pObj->pFanin0;                 }
00240 static inline If_Obj_t * If_ObjFanin1( If_Obj_t * pObj )                     { return pObj->pFanin1;                 }
00241 static inline int        If_ObjFaninC0( If_Obj_t * pObj )                    { return pObj->fCompl0;                 }
00242 static inline int        If_ObjFaninC1( If_Obj_t * pObj )                    { return pObj->fCompl1;                 }
00243 static inline void *     If_ObjCopy( If_Obj_t * pObj )                       { return pObj->pCopy;                   }
00244 static inline void       If_ObjSetCopy( If_Obj_t * pObj, void * pCopy )      { pObj->pCopy = pCopy;                  }
00245 static inline void       If_ObjSetChoice( If_Obj_t * pObj, If_Obj_t * pEqu ) { pObj->pEquiv = pEqu;                  }
00246 
00247 static inline If_Cut_t * If_ObjCutBest( If_Obj_t * pObj )                    { return &pObj->CutBest;                }
00248 static inline unsigned   If_ObjCutSign( unsigned ObjId )                     { return (1 << (ObjId % 31));           }
00249 
00250 static inline float      If_ObjArrTime( If_Obj_t * pObj )                    { return If_ObjCutBest(pObj)->Delay;    }
00251 static inline void       If_ObjSetArrTime( If_Obj_t * pObj, float ArrTime )  { If_ObjCutBest(pObj)->Delay = ArrTime; }
00252 
00253 static inline float      If_ObjLValue( If_Obj_t * pObj )                     { return pObj->LValue;                  }
00254 static inline void       If_ObjSetLValue( If_Obj_t * pObj, float LValue )    { pObj->LValue = LValue;                }
00255 
00256 static inline void *     If_CutData( If_Cut_t * pCut )                       { return *(void **)pCut;                }
00257 static inline void       If_CutSetData( If_Cut_t * pCut, void * pData )      { *(void **)pCut = pData;               }
00258 
00259 static inline int        If_CutLeaveNum( If_Cut_t * pCut )                   { return pCut->nLeaves;                             }
00260 static inline unsigned * If_CutTruth( If_Cut_t * pCut )                      { return pCut->pTruth;                              }
00261 static inline int        If_CutTruthWords( int nVarsMax )                    { return nVarsMax <= 5 ? 1 : (1 << (nVarsMax - 5)); }
00262 static inline int        If_CutPermWords( int nVarsMax )                     { return nVarsMax / sizeof(int) + ((nVarsMax % sizeof(int)) > 0); }
00263 
00264 static inline float      If_CutLutArea( If_Man_t * p, If_Cut_t * pCut )      { return pCut->fUser? (float)pCut->Cost : (p->pPars->pLutLib? p->pPars->pLutLib->pLutAreas[pCut->nLeaves] : (float)1.0); }
00265 
00269 
00270 #define IF_MIN(a,b)      (((a) < (b))? (a) : (b))
00271 #define IF_MAX(a,b)      (((a) > (b))? (a) : (b))
00272 
00273 // the small and large numbers (min/max float are 1.17e-38/3.40e+38)
00274 #define IF_FLOAT_LARGE   ((float)1.0e+20)
00275 #define IF_FLOAT_SMALL   ((float)1.0e-20)
00276 #define IF_INT_LARGE     (10000000)
00277 
00278 // iterator over the primary inputs
00279 #define If_ManForEachCi( p, pObj, i )                                          \
00280     Vec_PtrForEachEntry( p->vCis, pObj, i )
00281 // iterator over the primary outputs
00282 #define If_ManForEachCo( p, pObj, i )                                          \
00283     Vec_PtrForEachEntry( p->vCos, pObj, i )
00284 // iterator over the primary inputs
00285 #define If_ManForEachPi( p, pObj, i )                                          \
00286     Vec_PtrForEachEntryStop( p->vCis, pObj, i, If_ManCiNum(p) - p->pPars->nLatches )
00287 // iterator over the primary outputs
00288 #define If_ManForEachPo( p, pObj, i )                                          \
00289     Vec_PtrForEachEntryStop( p->vCos, pObj, i, If_ManCoNum(p) - p->pPars->nLatches )
00290 // iterator over the latches 
00291 #define If_ManForEachLatchInput( p, pObj, i )                                  \
00292     Vec_PtrForEachEntryStart( p->vCos, pObj, i, If_ManCoNum(p) - p->pPars->nLatches )
00293 #define If_ManForEachLatchOutput( p, pObj, i )                                 \
00294     Vec_PtrForEachEntryStart( p->vCis, pObj, i, If_ManCiNum(p) - p->pPars->nLatches )
00295 // iterator over all objects, including those currently not used
00296 #define If_ManForEachObj( p, pObj, i )                                         \
00297     Vec_PtrForEachEntry( p->vObjs, pObj, i )
00298 // iterator over logic nodes 
00299 #define If_ManForEachNode( p, pObj, i )                                        \
00300     If_ManForEachObj( p, pObj, i ) if ( pObj->Type != IF_AND ) {} else
00301 // iterator over cuts of the node
00302 #define If_ObjForEachCut( pObj, pCut, i )                                      \
00303     for ( i = 0; (i < (pObj)->pCutSet->nCuts) && ((pCut) = (pObj)->pCutSet->ppCuts[i]); i++ )
00304 // iterator over the leaves of the cut
00305 #define If_CutForEachLeaf( p, pCut, pLeaf, i )                                 \
00306     for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i])); i++ )
00307 #define If_CutForEachLeafReverse( p, pCut, pLeaf, i )                                 \
00308     for ( i = (int)(pCut)->nLeaves - 1; (i >= 0) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i])); i-- )
00309 //#define If_CutForEachLeaf( p, pCut, pLeaf, i )                                 \
00310 //    for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, p->pPars->fLiftLeaves? (pCut)->pLeaves[i] >> 8 : (pCut)->pLeaves[i])); i++ )
00311 // iterator over the leaves of the sequential cut
00312 #define If_CutForEachLeafSeq( p, pCut, pLeaf, Shift, i )                       \
00313     for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i] >> 8)) && (((Shift) = ((pCut)->pLeaves[i] & 255)) >= 0); i++ )
00314 
00318 
00319 /*=== ifCore.c ===========================================================*/
00320 extern int             If_ManPerformMapping( If_Man_t * p );
00321 extern int             If_ManPerformMappingComb( If_Man_t * p );
00322 /*=== ifCut.c ============================================================*/
00323 extern float           If_CutAreaDerefed( If_Man_t * p, If_Cut_t * pCut, int nLevels );
00324 extern float           If_CutAreaRefed( If_Man_t * p, If_Cut_t * pCut, int nLevels );
00325 extern float           If_CutDeref( If_Man_t * p, If_Cut_t * pCut, int nLevels );
00326 extern float           If_CutRef( If_Man_t * p, If_Cut_t * pCut, int nLevels );
00327 extern void            If_CutPrint( If_Man_t * p, If_Cut_t * pCut );
00328 extern void            If_CutPrintTiming( If_Man_t * p, If_Cut_t * pCut );
00329 extern float           If_CutFlow( If_Man_t * p, If_Cut_t * pCut );
00330 extern float           If_CutAverageRefs( If_Man_t * p, If_Cut_t * pCut );
00331 extern int             If_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut );
00332 extern void            If_CutSort( If_Man_t * p, If_Set_t * pCutSet, If_Cut_t * pCut );
00333 extern int             If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut );
00334 extern void            If_CutLift( If_Cut_t * pCut );
00335 extern void            If_CutCopy( If_Man_t * p, If_Cut_t * pCutDest, If_Cut_t * pCutSrc );
00336 extern void            If_ManSortCuts( If_Man_t * p, int Mode );
00337 /*=== ifMan.c =============================================================*/
00338 extern If_Man_t *      If_ManStart( If_Par_t * pPars );
00339 extern void            If_ManRestart( If_Man_t * p );
00340 extern void            If_ManStop( If_Man_t * p );
00341 extern If_Obj_t *      If_ManCreateCi( If_Man_t * p );
00342 extern If_Obj_t *      If_ManCreateCo( If_Man_t * p, If_Obj_t * pDriver );
00343 extern If_Obj_t *      If_ManCreateAnd( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1 );
00344 extern If_Obj_t *      If_ManCreateXor( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1 );
00345 extern If_Obj_t *      If_ManCreateMux( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1, If_Obj_t * pCtrl );
00346 extern void            If_ManCreateChoice( If_Man_t * p, If_Obj_t * pRepr );
00347 extern void            If_ManSetupCutTriv( If_Man_t * p, If_Cut_t * pCut, int ObjId );
00348 extern void            If_ManSetupCiCutSets( If_Man_t * p );
00349 extern If_Set_t *      If_ManSetupNodeCutSet( If_Man_t * p, If_Obj_t * pObj );
00350 extern void            If_ManDerefNodeCutSet( If_Man_t * p, If_Obj_t * pObj );
00351 extern void            If_ManDerefChoiceCutSet( If_Man_t * p, If_Obj_t * pObj );
00352 extern void            If_ManSetupSetAll( If_Man_t * p, int nCrossCut );
00353 /*=== ifMap.c =============================================================*/
00354 extern void            If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess );
00355 extern void            If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess );
00356 extern int             If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fPreprocess, char * pLabel );
00357 /*=== ifReduce.c ==========================================================*/
00358 extern void            If_ManImproveMapping( If_Man_t * p );
00359 /*=== ifSeq.c =============================================================*/
00360 extern int             If_ManPerformMappingSeq( If_Man_t * p );
00361 /*=== ifTime.c ============================================================*/
00362 extern float           If_CutDelay( If_Man_t * p, If_Cut_t * pCut );
00363 extern void            If_CutPropagateRequired( If_Man_t * p, If_Cut_t * pCut, float Required );
00364 /*=== ifTruth.c ===========================================================*/
00365 extern void            If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 );
00366 /*=== ifUtil.c ============================================================*/
00367 extern void            If_ManCleanNodeCopy( If_Man_t * p );
00368 extern void            If_ManCleanCutData( If_Man_t * p );
00369 extern void            If_ManCleanMarkV( If_Man_t * p );
00370 extern float           If_ManDelayMax( If_Man_t * p, int fSeq );
00371 extern void            If_ManComputeRequired( If_Man_t * p );
00372 extern float           If_ManScanMapping( If_Man_t * p );
00373 extern float           If_ManScanMappingSeq( If_Man_t * p );
00374 extern void            If_ManResetOriginalRefs( If_Man_t * p );
00375 extern int             If_ManCrossCut( If_Man_t * p );
00376 
00377 #ifdef __cplusplus
00378 }
00379 #endif
00380 
00381 #endif
00382 
00386