diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2007-09-30 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2007-09-30 08:01:00 -0700 |
commit | e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 (patch) | |
tree | de3ffe87c3e17950351e3b7d97fa18318bd5ea9a /src/map/if | |
parent | 7d7e60f2dc84393cd4c5db22d2eaf7b1fb1a79b2 (diff) | |
download | abc-e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7.tar.gz abc-e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7.tar.bz2 abc-e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7.zip |
Version abc70930
Diffstat (limited to 'src/map/if')
-rw-r--r-- | src/map/if/if.h | 386 | ||||
-rw-r--r-- | src/map/if/ifCore.c | 146 | ||||
-rw-r--r-- | src/map/if/ifCut.c | 777 | ||||
-rw-r--r-- | src/map/if/ifMan.c | 570 | ||||
-rw-r--r-- | src/map/if/ifMap.c | 300 | ||||
-rw-r--r-- | src/map/if/ifReduce.c | 574 | ||||
-rw-r--r-- | src/map/if/ifSeq.c | 405 | ||||
-rw-r--r-- | src/map/if/ifTime.c | 221 | ||||
-rw-r--r-- | src/map/if/ifTruth.c | 230 | ||||
-rw-r--r-- | src/map/if/ifUtil.c | 454 | ||||
-rw-r--r-- | src/map/if/if_.c | 47 | ||||
-rw-r--r-- | src/map/if/module.make | 9 |
12 files changed, 0 insertions, 4119 deletions
diff --git a/src/map/if/if.h b/src/map/if/if.h deleted file mode 100644 index 706f8552..00000000 --- a/src/map/if/if.h +++ /dev/null @@ -1,386 +0,0 @@ -/**CFile**************************************************************** - - FileName [if.h] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [External declarations.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: if.h,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#ifndef __IF_H__ -#define __IF_H__ - -#ifdef __cplusplus -extern "C" { -#endif - -//////////////////////////////////////////////////////////////////////// -/// INCLUDES /// -//////////////////////////////////////////////////////////////////////// - -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <assert.h> -#include <time.h> -#include "vec.h" -#include "mem.h" - -//////////////////////////////////////////////////////////////////////// -/// PARAMETERS /// -//////////////////////////////////////////////////////////////////////// - -// the maximum size of LUTs used for mapping (should be the same as FPGA_MAX_LUTSIZE defined in "fpga.h"!!!) -#define IF_MAX_LUTSIZE 32 -// the largest possible number of LUT inputs when funtionality of the LUTs are computed -#define IF_MAX_FUNC_LUTSIZE 15 -// a very large number -#define IF_INFINITY 100000000 -// the largest possible user cut cost -#define IF_COST_MAX ((1<<14)-1) - -// object types -typedef enum { - IF_NONE, // 0: non-existent object - IF_CONST1, // 1: constant 1 - IF_CI, // 2: combinational input - IF_CO, // 3: combinational output - IF_AND, // 4: AND node - IF_VOID // 5: unused object -} If_Type_t; - -//////////////////////////////////////////////////////////////////////// -/// BASIC TYPES /// -//////////////////////////////////////////////////////////////////////// - -typedef struct If_Man_t_ If_Man_t; -typedef struct If_Par_t_ If_Par_t; -typedef struct If_Lib_t_ If_Lib_t; -typedef struct If_Obj_t_ If_Obj_t; -typedef struct If_Cut_t_ If_Cut_t; -typedef struct If_Set_t_ If_Set_t; - -// parameters -struct If_Par_t_ -{ - // user-controlable paramters - int nLutSize; // the LUT size - int nCutsMax; // the max number of cuts - int nFlowIters; // the number of iterations of area recovery - int nAreaIters; // the number of iterations of area recovery - float DelayTarget; // delay target - int fPreprocess; // preprossing - int fArea; // area-oriented mapping - int fFancy; // a fancy feature - int fExpRed; // expand/reduce of the best cuts - int fLatchPaths; // reset timing on latch paths - int fSeqMap; // sequential mapping - int fVerbose; // the verbosity flag - // internal parameters - int fAreaOnly; // area only mode - int fTruth; // truth table computation enabled - int fUsePerm; // use permutation (delay info) - int fUseBdds; // use local BDDs as a cost function - int fUseSops; // use local SOPs as a cost function - int fUseCnfs; // use local CNFs as a cost function - int fUseMv; // use local MV-SOPs as a cost function - int nLatches; // the number of latches in seq mapping - int fLiftLeaves; // shift the leaves for seq mapping - If_Lib_t * pLutLib; // the LUT library - float * pTimesArr; // arrival times - float * pTimesReq; // required times - int (* pFuncCost) (If_Cut_t *); // procedure to compute the user's cost of a cut - int (* pFuncUser) (If_Man_t *, If_Obj_t *, If_Cut_t *); // procedure called for each cut when cut computation is finished - void * pReoMan; // reordering manager -}; - -// the LUT library -struct If_Lib_t_ -{ - char * pName; // the name of the LUT library - int LutMax; // the maximum LUT size - int fVarPinDelays; // set to 1 if variable pin delays are specified - float pLutAreas[IF_MAX_LUTSIZE+1]; // the areas of LUTs - float pLutDelays[IF_MAX_LUTSIZE+1][IF_MAX_LUTSIZE+1];// the delays of LUTs -}; - -// manager -struct If_Man_t_ -{ - // mapping parameters - If_Par_t * pPars; - // mapping nodes - If_Obj_t * pConst1; // the constant 1 node - Vec_Ptr_t * vCis; // the primary inputs - Vec_Ptr_t * vCos; // the primary outputs - Vec_Ptr_t * vObjs; // all objects - Vec_Ptr_t * vMapped; // objects used in the mapping - Vec_Ptr_t * vTemp; // temporary array - int nObjs[IF_VOID];// the number of objects by type - // various data - int nLevelMax; // the max number of AIG levels - float fEpsilon; // epsilon used for comparison - float RequiredGlo; // global required times - float RequiredGlo2; // global required times - float AreaGlo; // global area - int nNets; // the sum total of fanins of all LUTs in the mapping - int nCutsUsed; // the number of cuts currently used - int nCutsMerged; // the total number of cuts merged - unsigned * puTemp[4]; // used for the truth table computation - int SortMode; // one of the three sorting modes - int fNextRound; // set to 1 after the first round - int nChoices; // the number of choice nodes - // sequential mapping - Vec_Ptr_t * vLatchOrder; // topological ordering of latches - Vec_Int_t * vLags; // sequentail lags of all nodes - int nAttempts; // the number of attempts in binary search - int nMaxIters; // the maximum number of iterations - int Period; // the current value of the clock period (for seq mapping) - // memory management - int nTruthWords; // the size of the truth table if allocated - int nPermWords; // the size of the permutation array (in words) - int nObjBytes; // the size of the object - int nCutBytes; // the size of the cut - int nSetBytes; // the size of the cut set - Mem_Fixed_t * pMemObj; // memory manager for objects (entrysize = nEntrySize) - Mem_Fixed_t * pMemSet; // memory manager for sets of cuts (entrysize = nCutSize*(nCutsMax+1)) - If_Set_t * pMemCi; // memory for CI cutsets - If_Set_t * pMemAnd; // memory for AND cutsets - If_Set_t * pFreeList; // the list of free cutsets -}; - -// priority cut -struct If_Cut_t_ -{ - float Delay; // delay of the cut - float Area; // area (or area-flow) of the cut - float AveRefs; // the average number of leaf references - unsigned uSign; // cut signature - unsigned Cost : 14; // the user's cost of the cut - unsigned fCompl : 1; // the complemented attribute - unsigned fUser : 1; // using the user's area and delay - unsigned nLimit : 8; // the maximum number of leaves - unsigned nLeaves : 8; // the number of leaves - int * pLeaves; // array of fanins - char * pPerm; // permutation - unsigned * pTruth; // the truth table -}; - -// set of priority cut -struct If_Set_t_ -{ - short nCutsMax; // the max number of cuts - short nCuts; // the current number of cuts - If_Set_t * pNext; // next cutset in the free list - If_Cut_t ** ppCuts; // the array of pointers to the cuts -}; - -// node extension -struct If_Obj_t_ -{ - unsigned Type : 4; // object - unsigned fCompl0 : 1; // complemented attribute - unsigned fCompl1 : 1; // complemented attribute - unsigned fPhase : 1; // phase of the node - unsigned fRepr : 1; // representative of the equivalence class - unsigned fMark : 1; // multipurpose mark - unsigned fVisit : 1; // multipurpose mark - unsigned Level : 22; // logic level of the node - int Id; // integer ID - int nRefs; // the number of references - int nVisits; // the number of visits to this node - int nVisitsCopy; // the number of visits to this node - If_Obj_t * pFanin0; // the first fanin - If_Obj_t * pFanin1; // the second fanin - If_Obj_t * pEquiv; // the choice node - float EstRefs; // estimated reference counter - float Required; // required time of the onde - float LValue; // sequential arrival time of the node - void * pCopy; // used for object duplication - If_Set_t * pCutSet; // the pointer to the cutset - If_Cut_t CutBest; // the best cut selected -}; - -static inline If_Obj_t * If_Regular( If_Obj_t * p ) { return (If_Obj_t *)((unsigned long)(p) & ~01); } -static inline If_Obj_t * If_Not( If_Obj_t * p ) { return (If_Obj_t *)((unsigned long)(p) ^ 01); } -static inline If_Obj_t * If_NotCond( If_Obj_t * p, int c ) { return (If_Obj_t *)((unsigned long)(p) ^ (c)); } -static inline int If_IsComplement( If_Obj_t * p ) { return (int )(((unsigned long)p) & 01); } - -static inline int If_ManCiNum( If_Man_t * p ) { return p->nObjs[IF_CI]; } -static inline int If_ManCoNum( If_Man_t * p ) { return p->nObjs[IF_CO]; } -static inline int If_ManAndNum( If_Man_t * p ) { return p->nObjs[IF_AND]; } -static inline int If_ManObjNum( If_Man_t * p ) { return Vec_PtrSize(p->vObjs); } - -static inline If_Obj_t * If_ManConst1( If_Man_t * p ) { return p->pConst1; } -static inline If_Obj_t * If_ManCi( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vCis, i ); } -static inline If_Obj_t * If_ManCo( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vCos, i ); } -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 ); } -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 ); } -static inline If_Obj_t * If_ManObj( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vObjs, i ); } - -static inline int If_ObjIsConst1( If_Obj_t * pObj ) { return pObj->Type == IF_CONST1; } -static inline int If_ObjIsCi( If_Obj_t * pObj ) { return pObj->Type == IF_CI; } -static inline int If_ObjIsCo( If_Obj_t * pObj ) { return pObj->Type == IF_CO; } -static inline int If_ObjIsPi( If_Obj_t * pObj ) { return If_ObjIsCi(pObj) && pObj->pFanin0 == NULL; } -static inline int If_ObjIsLatch( If_Obj_t * pObj ) { return If_ObjIsCi(pObj) && pObj->pFanin0 != NULL; } -static inline int If_ObjIsAnd( If_Obj_t * pObj ) { return pObj->Type == IF_AND; } - -static inline If_Obj_t * If_ObjFanin0( If_Obj_t * pObj ) { return pObj->pFanin0; } -static inline If_Obj_t * If_ObjFanin1( If_Obj_t * pObj ) { return pObj->pFanin1; } -static inline int If_ObjFaninC0( If_Obj_t * pObj ) { return pObj->fCompl0; } -static inline int If_ObjFaninC1( If_Obj_t * pObj ) { return pObj->fCompl1; } -static inline void * If_ObjCopy( If_Obj_t * pObj ) { return pObj->pCopy; } -static inline void If_ObjSetCopy( If_Obj_t * pObj, void * pCopy ) { pObj->pCopy = pCopy; } -static inline void If_ObjSetChoice( If_Obj_t * pObj, If_Obj_t * pEqu ) { pObj->pEquiv = pEqu; } - -static inline If_Cut_t * If_ObjCutBest( If_Obj_t * pObj ) { return &pObj->CutBest; } -static inline unsigned If_ObjCutSign( unsigned ObjId ) { return (1 << (ObjId % 31)); } - -static inline float If_ObjArrTime( If_Obj_t * pObj ) { return If_ObjCutBest(pObj)->Delay; } -static inline void If_ObjSetArrTime( If_Obj_t * pObj, float ArrTime ) { If_ObjCutBest(pObj)->Delay = ArrTime; } - -static inline float If_ObjLValue( If_Obj_t * pObj ) { return pObj->LValue; } -static inline void If_ObjSetLValue( If_Obj_t * pObj, float LValue ) { pObj->LValue = LValue; } - -static inline void * If_CutData( If_Cut_t * pCut ) { return *(void **)pCut; } -static inline void If_CutSetData( If_Cut_t * pCut, void * pData ) { *(void **)pCut = pData; } - -static inline int If_CutLeaveNum( If_Cut_t * pCut ) { return pCut->nLeaves; } -static inline unsigned * If_CutTruth( If_Cut_t * pCut ) { return pCut->pTruth; } -static inline int If_CutTruthWords( int nVarsMax ) { return nVarsMax <= 5 ? 1 : (1 << (nVarsMax - 5)); } -static inline int If_CutPermWords( int nVarsMax ) { return nVarsMax / sizeof(int) + ((nVarsMax % sizeof(int)) > 0); } - -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); } - -//////////////////////////////////////////////////////////////////////// -/// MACRO DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -#define IF_MIN(a,b) (((a) < (b))? (a) : (b)) -#define IF_MAX(a,b) (((a) > (b))? (a) : (b)) - -// the small and large numbers (min/max float are 1.17e-38/3.40e+38) -#define IF_FLOAT_LARGE ((float)1.0e+20) -#define IF_FLOAT_SMALL ((float)1.0e-20) -#define IF_INT_LARGE (10000000) - -// iterator over the primary inputs -#define If_ManForEachCi( p, pObj, i ) \ - Vec_PtrForEachEntry( p->vCis, pObj, i ) -// iterator over the primary outputs -#define If_ManForEachCo( p, pObj, i ) \ - Vec_PtrForEachEntry( p->vCos, pObj, i ) -// iterator over the primary inputs -#define If_ManForEachPi( p, pObj, i ) \ - Vec_PtrForEachEntryStop( p->vCis, pObj, i, If_ManCiNum(p) - p->pPars->nLatches ) -// iterator over the primary outputs -#define If_ManForEachPo( p, pObj, i ) \ - Vec_PtrForEachEntryStop( p->vCos, pObj, i, If_ManCoNum(p) - p->pPars->nLatches ) -// iterator over the latches -#define If_ManForEachLatchInput( p, pObj, i ) \ - Vec_PtrForEachEntryStart( p->vCos, pObj, i, If_ManCoNum(p) - p->pPars->nLatches ) -#define If_ManForEachLatchOutput( p, pObj, i ) \ - Vec_PtrForEachEntryStart( p->vCis, pObj, i, If_ManCiNum(p) - p->pPars->nLatches ) -// iterator over all objects, including those currently not used -#define If_ManForEachObj( p, pObj, i ) \ - Vec_PtrForEachEntry( p->vObjs, pObj, i ) -// iterator over logic nodes -#define If_ManForEachNode( p, pObj, i ) \ - If_ManForEachObj( p, pObj, i ) if ( pObj->Type != IF_AND ) {} else -// iterator over cuts of the node -#define If_ObjForEachCut( pObj, pCut, i ) \ - for ( i = 0; (i < (pObj)->pCutSet->nCuts) && ((pCut) = (pObj)->pCutSet->ppCuts[i]); i++ ) -// iterator over the leaves of the cut -#define If_CutForEachLeaf( p, pCut, pLeaf, i ) \ - for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i])); i++ ) -#define If_CutForEachLeafReverse( p, pCut, pLeaf, i ) \ - for ( i = (int)(pCut)->nLeaves - 1; (i >= 0) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i])); i-- ) -//#define If_CutForEachLeaf( p, pCut, pLeaf, i ) \ -// for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, p->pPars->fLiftLeaves? (pCut)->pLeaves[i] >> 8 : (pCut)->pLeaves[i])); i++ ) -// iterator over the leaves of the sequential cut -#define If_CutForEachLeafSeq( p, pCut, pLeaf, Shift, i ) \ - for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i] >> 8)) && (((Shift) = ((pCut)->pLeaves[i] & 255)) >= 0); i++ ) - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -/*=== ifCore.c ===========================================================*/ -extern int If_ManPerformMapping( If_Man_t * p ); -extern int If_ManPerformMappingComb( If_Man_t * p ); -/*=== ifCut.c ============================================================*/ -extern float If_CutAreaDerefed( If_Man_t * p, If_Cut_t * pCut, int nLevels ); -extern float If_CutAreaRefed( If_Man_t * p, If_Cut_t * pCut, int nLevels ); -extern float If_CutDeref( If_Man_t * p, If_Cut_t * pCut, int nLevels ); -extern float If_CutRef( If_Man_t * p, If_Cut_t * pCut, int nLevels ); -extern void If_CutPrint( If_Man_t * p, If_Cut_t * pCut ); -extern void If_CutPrintTiming( If_Man_t * p, If_Cut_t * pCut ); -extern float If_CutFlow( If_Man_t * p, If_Cut_t * pCut ); -extern float If_CutAverageRefs( If_Man_t * p, If_Cut_t * pCut ); -extern int If_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut ); -extern void If_CutSort( If_Man_t * p, If_Set_t * pCutSet, If_Cut_t * pCut ); -extern int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut ); -extern void If_CutLift( If_Cut_t * pCut ); -extern void If_CutCopy( If_Man_t * p, If_Cut_t * pCutDest, If_Cut_t * pCutSrc ); -extern void If_ManSortCuts( If_Man_t * p, int Mode ); -/*=== ifMan.c =============================================================*/ -extern If_Man_t * If_ManStart( If_Par_t * pPars ); -extern void If_ManRestart( If_Man_t * p ); -extern void If_ManStop( If_Man_t * p ); -extern If_Obj_t * If_ManCreateCi( If_Man_t * p ); -extern If_Obj_t * If_ManCreateCo( If_Man_t * p, If_Obj_t * pDriver ); -extern If_Obj_t * If_ManCreateAnd( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1 ); -extern If_Obj_t * If_ManCreateXor( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1 ); -extern If_Obj_t * If_ManCreateMux( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1, If_Obj_t * pCtrl ); -extern void If_ManCreateChoice( If_Man_t * p, If_Obj_t * pRepr ); -extern void If_ManSetupCutTriv( If_Man_t * p, If_Cut_t * pCut, int ObjId ); -extern void If_ManSetupCiCutSets( If_Man_t * p ); -extern If_Set_t * If_ManSetupNodeCutSet( If_Man_t * p, If_Obj_t * pObj ); -extern void If_ManDerefNodeCutSet( If_Man_t * p, If_Obj_t * pObj ); -extern void If_ManDerefChoiceCutSet( If_Man_t * p, If_Obj_t * pObj ); -extern void If_ManSetupSetAll( If_Man_t * p, int nCrossCut ); -/*=== ifMap.c =============================================================*/ -extern void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess ); -extern void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess ); -extern int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fPreprocess, char * pLabel ); -/*=== ifReduce.c ==========================================================*/ -extern void If_ManImproveMapping( If_Man_t * p ); -/*=== ifSeq.c =============================================================*/ -extern int If_ManPerformMappingSeq( If_Man_t * p ); -/*=== ifTime.c ============================================================*/ -extern float If_CutDelay( If_Man_t * p, If_Cut_t * pCut ); -extern void If_CutPropagateRequired( If_Man_t * p, If_Cut_t * pCut, float Required ); -/*=== ifTruth.c ===========================================================*/ -extern void If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 ); -/*=== ifUtil.c ============================================================*/ -extern void If_ManCleanNodeCopy( If_Man_t * p ); -extern void If_ManCleanCutData( If_Man_t * p ); -extern void If_ManCleanMarkV( If_Man_t * p ); -extern float If_ManDelayMax( If_Man_t * p, int fSeq ); -extern void If_ManComputeRequired( If_Man_t * p ); -extern float If_ManScanMapping( If_Man_t * p ); -extern float If_ManScanMappingSeq( If_Man_t * p ); -extern void If_ManResetOriginalRefs( If_Man_t * p ); -extern int If_ManCrossCut( If_Man_t * p ); - -#ifdef __cplusplus -} -#endif - -#endif - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - diff --git a/src/map/if/ifCore.c b/src/map/if/ifCore.c deleted file mode 100644 index 59ad5a1c..00000000 --- a/src/map/if/ifCore.c +++ /dev/null @@ -1,146 +0,0 @@ -/**CFile**************************************************************** - - FileName [ifCore.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [The central part of the mapper.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: ifCore.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "if.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -extern int s_MappingTime; - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManPerformMapping( If_Man_t * p ) -{ - p->pPars->fAreaOnly = p->pPars->fArea; // temporary - - // create the CI cutsets - If_ManSetupCiCutSets( p ); - // allocate memory for other cutsets - If_ManSetupSetAll( p, If_ManCrossCut(p) ); - - // try sequential mapping - if ( p->pPars->fSeqMap ) - { - int RetValue; -// printf( "Currently sequential mapping is not performed.\n" ); - RetValue = If_ManPerformMappingSeq( p ); - return RetValue; -// return 1; - } - - return If_ManPerformMappingComb( p ); -} - - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManPerformMappingComb( If_Man_t * p ) -{ - If_Obj_t * pObj; - int clkTotal = clock(); - int i; - - // set arrival times and fanout estimates - If_ManForEachCi( p, pObj, i ) - { - If_ObjSetArrTime( pObj, p->pPars->pTimesArr[i] ); - pObj->EstRefs = (float)1.0; - } - - // delay oriented mapping - if ( p->pPars->fPreprocess && !p->pPars->fArea ) - { - // map for delay - If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 1, "Delay" ); - // map for delay second option - p->pPars->fFancy = 1; - If_ManResetOriginalRefs( p ); - If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 1, "Delay-2" ); - p->pPars->fFancy = 0; - // map for area - p->pPars->fArea = 1; - If_ManResetOriginalRefs( p ); - If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 1, "Area" ); - p->pPars->fArea = 0; - } - else - If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 0, "Delay" ); - - // try to improve area by expanding and reducing the cuts - if ( p->pPars->fExpRed && !p->pPars->fTruth ) - If_ManImproveMapping( p ); - - // area flow oriented mapping - for ( i = 0; i < p->pPars->nFlowIters; i++ ) - { - If_ManPerformMappingRound( p, p->pPars->nCutsMax, 1, 0, "Flow" ); - if ( p->pPars->fExpRed && !p->pPars->fTruth ) - If_ManImproveMapping( p ); - } - - // area oriented mapping - for ( i = 0; i < p->pPars->nAreaIters; i++ ) - { - If_ManPerformMappingRound( p, p->pPars->nCutsMax, 2, 0, "Area" ); - if ( p->pPars->fExpRed && !p->pPars->fTruth ) - If_ManImproveMapping( p ); - } - - if ( p->pPars->fVerbose ) - { -// printf( "Total memory = %7.2f Mb. Peak cut memory = %7.2f Mb. ", -// 1.0 * (p->nObjBytes + 2*sizeof(void *)) * If_ManObjNum(p) / (1<<20), -// 1.0 * p->nSetBytes * Mem_FixedReadMaxEntriesUsed(p->pMemSet) / (1<<20) ); - PRT( "Total time", clock() - clkTotal ); - } -// printf( "Cross cut memory = %d.\n", Mem_FixedReadMaxEntriesUsed(p->pMemSet) ); - s_MappingTime = clock() - clkTotal; - return 1; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/map/if/ifCut.c b/src/map/if/ifCut.c deleted file mode 100644 index 1a7ecc2c..00000000 --- a/src/map/if/ifCut.c +++ /dev/null @@ -1,777 +0,0 @@ -/**CFile**************************************************************** - - FileName [ifCut.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [Cut computation.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: ifCut.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "if.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - - -/**Function************************************************************* - - Synopsis [Returns 1 if pDom is contained in pCut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int If_CutCheckDominance( If_Cut_t * pDom, If_Cut_t * pCut ) -{ - int i, k; - for ( i = 0; i < (int)pDom->nLeaves; i++ ) - { - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - if ( pDom->pLeaves[i] == pCut->pLeaves[k] ) - break; - if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut - return 0; - } - // every node in pDom is contained in pCut - return 1; -} - -/**Function************************************************************* - - Synopsis [Returns 1 if pDom is equal to pCut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int If_CutCheckEquality( If_Cut_t * pDom, If_Cut_t * pCut ) -{ - int i; - if ( (int)pDom->nLeaves != (int)pCut->nLeaves ) - return 0; - for ( i = 0; i < (int)pDom->nLeaves; i++ ) - if ( pDom->pLeaves[i] != pCut->pLeaves[i] ) - return 0; - return 1; -} - -/**Function************************************************************* - - Synopsis [Returns 1 if the cut is contained.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut ) -{ - If_Cut_t * pTemp; - int i, k; - assert( pCutSet->ppCuts[pCutSet->nCuts] == pCut ); - for ( i = 0; i < pCutSet->nCuts; i++ ) - { - pTemp = pCutSet->ppCuts[i]; - if ( pTemp->nLeaves > pCut->nLeaves ) - { - // do not fiter the first cut - if ( i == 0 ) - continue; - // skip the non-contained cuts - if ( (pTemp->uSign & pCut->uSign) != pCut->uSign ) - continue; - // check containment seriously - if ( If_CutCheckDominance( pCut, pTemp ) ) - { -// p->ppCuts[i] = p->ppCuts[p->nCuts-1]; -// p->ppCuts[p->nCuts-1] = pTemp; -// p->nCuts--; -// i--; - // remove contained cut - for ( k = i; k < pCutSet->nCuts; k++ ) - pCutSet->ppCuts[k] = pCutSet->ppCuts[k+1]; - pCutSet->ppCuts[pCutSet->nCuts] = pTemp; - pCutSet->nCuts--; - i--; - } - } - else - { - // skip the non-contained cuts - if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign ) - continue; - // check containment seriously - if ( If_CutCheckDominance( pTemp, pCut ) ) - return 1; - } - } - return 0; -} - -/**Function************************************************************* - - Synopsis [Merges two cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) -{ - int i, k, c; - assert( pC0->nLeaves >= pC1->nLeaves ); - // the case of the largest cut sizes - if ( pC0->nLeaves == pC->nLimit && pC1->nLeaves == pC->nLimit ) - { - for ( i = 0; i < (int)pC0->nLeaves; i++ ) - if ( pC0->pLeaves[i] != pC1->pLeaves[i] ) - return 0; - for ( i = 0; i < (int)pC0->nLeaves; i++ ) - pC->pLeaves[i] = pC0->pLeaves[i]; - pC->nLeaves = pC0->nLeaves; - return 1; - } - // the case when one of the cuts is the largest - if ( pC0->nLeaves == pC->nLimit ) - { - for ( i = 0; i < (int)pC1->nLeaves; i++ ) - { - for ( k = (int)pC0->nLeaves - 1; k >= 0; k-- ) - if ( pC0->pLeaves[k] == pC1->pLeaves[i] ) - break; - if ( k == -1 ) // did not find - return 0; - } - for ( i = 0; i < (int)pC0->nLeaves; i++ ) - pC->pLeaves[i] = pC0->pLeaves[i]; - pC->nLeaves = pC0->nLeaves; - return 1; - } - - // compare two cuts with different numbers - i = k = 0; - for ( c = 0; c < (int)pC->nLimit; c++ ) - { - if ( k == (int)pC1->nLeaves ) - { - if ( i == (int)pC0->nLeaves ) - { - pC->nLeaves = c; - return 1; - } - pC->pLeaves[c] = pC0->pLeaves[i++]; - continue; - } - if ( i == (int)pC0->nLeaves ) - { - if ( k == (int)pC1->nLeaves ) - { - pC->nLeaves = c; - return 1; - } - pC->pLeaves[c] = pC1->pLeaves[k++]; - continue; - } - if ( pC0->pLeaves[i] < pC1->pLeaves[k] ) - { - pC->pLeaves[c] = pC0->pLeaves[i++]; - continue; - } - if ( pC0->pLeaves[i] > pC1->pLeaves[k] ) - { - pC->pLeaves[c] = pC1->pLeaves[k++]; - continue; - } - pC->pLeaves[c] = pC0->pLeaves[i++]; - k++; - } - if ( i < (int)pC0->nLeaves || k < (int)pC1->nLeaves ) - return 0; - pC->nLeaves = c; - return 1; -} - -/**Function************************************************************* - - Synopsis [Merges two cuts.] - - Description [Special case when the cut is known to exist.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int If_CutMergeOrdered2( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) -{ - int i, k, c; - assert( pC0->nLeaves >= pC1->nLeaves ); - // copy the first cut - for ( i = 0; i < (int)pC0->nLeaves; i++ ) - pC->pLeaves[i] = pC0->pLeaves[i]; - pC->nLeaves = pC0->nLeaves; - // the case when one of the cuts is the largest - if ( pC0->nLeaves == pC->nLimit ) - return 1; - // add nodes of the second cut - k = 0; - for ( i = 0; i < (int)pC1->nLeaves; i++ ) - { - // find k-th node before which i-th node should be added - for ( ; k < (int)pC->nLeaves; k++ ) - if ( pC->pLeaves[k] >= pC1->pLeaves[i] ) - break; - // check the case when this should be the last node - if ( k == (int)pC->nLeaves ) - { - pC->pLeaves[k++] = pC1->pLeaves[i]; - pC->nLeaves++; - continue; - } - // check the case when equal node is found - if ( pC1->pLeaves[i] == pC->pLeaves[k] ) - continue; - // add the node - for ( c = (int)pC->nLeaves; c > k; c-- ) - pC->pLeaves[c] = pC->pLeaves[c-1]; - pC->pLeaves[k++] = pC1->pLeaves[i]; - pC->nLeaves++; - } -/* - assert( pC->nLeaves <= pC->nLimit ); - for ( i = 1; i < (int)pC->nLeaves; i++ ) - assert( pC->pLeaves[i-1] < pC->pLeaves[i] ); -*/ - return 1; -} - -/**Function************************************************************* - - Synopsis [Prepares the object for FPGA mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut ) -{ - assert( pCut->nLimit > 0 ); - // merge the nodes - if ( pCut0->nLeaves < pCut1->nLeaves ) - { - if ( !If_CutMergeOrdered( pCut1, pCut0, pCut ) ) - return 0; - } - else - { - if ( !If_CutMergeOrdered( pCut0, pCut1, pCut ) ) - return 0; - } - pCut->uSign = pCut0->uSign | pCut1->uSign; - return 1; -} - -/**Function************************************************************* - - Synopsis [Prepares the object for FPGA mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_CutCompareDelay( If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) -{ - If_Cut_t * pC0 = *ppC0; - If_Cut_t * pC1 = *ppC1; - if ( pC0->Delay < pC1->Delay - 0.0001 ) - return -1; - if ( pC0->Delay > pC1->Delay + 0.0001 ) - return 1; - if ( pC0->nLeaves < pC1->nLeaves ) - return -1; - if ( pC0->nLeaves > pC1->nLeaves ) - return 1; - if ( pC0->Area < pC1->Area - 0.0001 ) - return -1; - if ( pC0->Area > pC1->Area + 0.0001 ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [Prepares the object for FPGA mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_CutCompareDelayOld( If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) -{ - If_Cut_t * pC0 = *ppC0; - If_Cut_t * pC1 = *ppC1; - if ( pC0->Delay < pC1->Delay - 0.0001 ) - return -1; - if ( pC0->Delay > pC1->Delay + 0.0001 ) - return 1; - if ( pC0->Area < pC1->Area - 0.0001 ) - return -1; - if ( pC0->Area > pC1->Area + 0.0001 ) - return 1; - if ( pC0->nLeaves < pC1->nLeaves ) - return -1; - if ( pC0->nLeaves > pC1->nLeaves ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [Prepares the object for FPGA mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_CutCompareArea( If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) -{ - If_Cut_t * pC0 = *ppC0; - If_Cut_t * pC1 = *ppC1; - if ( pC0->Area < pC1->Area - 0.0001 ) - return -1; - if ( pC0->Area > pC1->Area + 0.0001 ) - return 1; - if ( pC0->AveRefs > pC1->AveRefs ) - return -1; - if ( pC0->AveRefs < pC1->AveRefs ) - return 1; - if ( pC0->nLeaves < pC1->nLeaves ) - return -1; - if ( pC0->nLeaves > pC1->nLeaves ) - return 1; - if ( pC0->Delay < pC1->Delay - 0.0001 ) - return -1; - if ( pC0->Delay > pC1->Delay + 0.0001 ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [Sorts the cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManSortCuts( If_Man_t * p, int Mode ) -{ -/* - // sort the cuts - if ( Mode || p->pPars->fArea ) // area - qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareArea ); - else if ( p->pPars->fFancy ) - qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelayOld ); - else - qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelay ); -*/ -} - -/**Function************************************************************* - - Synopsis [Comparison function for two cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int If_ManSortCompare( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1 ) -{ - if ( p->SortMode == 1 ) // area - { - if ( pC0->Area < pC1->Area - 0.0001 ) - return -1; - if ( pC0->Area > pC1->Area + 0.0001 ) - return 1; - if ( pC0->AveRefs > pC1->AveRefs ) - return -1; - if ( pC0->AveRefs < pC1->AveRefs ) - return 1; - if ( pC0->nLeaves < pC1->nLeaves ) - return -1; - if ( pC0->nLeaves > pC1->nLeaves ) - return 1; - if ( pC0->Delay < pC1->Delay - 0.0001 ) - return -1; - if ( pC0->Delay > pC1->Delay + 0.0001 ) - return 1; - return 0; - } - if ( p->SortMode == 0 ) // delay - { - if ( pC0->Delay < pC1->Delay - 0.0001 ) - return -1; - if ( pC0->Delay > pC1->Delay + 0.0001 ) - return 1; - if ( pC0->nLeaves < pC1->nLeaves ) - return -1; - if ( pC0->nLeaves > pC1->nLeaves ) - return 1; - if ( pC0->Area < pC1->Area - 0.0001 ) - return -1; - if ( pC0->Area > pC1->Area + 0.0001 ) - return 1; - return 0; - } - assert( p->SortMode == 2 ); // delay old - if ( pC0->Delay < pC1->Delay - 0.0001 ) - return -1; - if ( pC0->Delay > pC1->Delay + 0.0001 ) - return 1; - if ( pC0->Area < pC1->Area - 0.0001 ) - return -1; - if ( pC0->Area > pC1->Area + 0.0001 ) - return 1; - if ( pC0->nLeaves < pC1->nLeaves ) - return -1; - if ( pC0->nLeaves > pC1->nLeaves ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [Performs incremental sorting of cuts.] - - Description [Currently only the trivial sorting is implemented.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_CutSort( If_Man_t * p, If_Set_t * pCutSet, If_Cut_t * pCut ) -{ -// int Counter = 0; - int i; - - // the new cut is the last one - assert( pCutSet->ppCuts[pCutSet->nCuts] == pCut ); - assert( pCutSet->nCuts <= pCutSet->nCutsMax ); - - // cut structure is empty - if ( pCutSet->nCuts == 0 ) - { - pCutSet->nCuts++; - return; - } - - // the cut will be added - find its place - for ( i = pCutSet->nCuts-1; i >= 0; i-- ) - { -// Counter++; - if ( If_ManSortCompare( p, pCutSet->ppCuts[i], pCut ) <= 0 ) - break; - pCutSet->ppCuts[i+1] = pCutSet->ppCuts[i]; - pCutSet->ppCuts[i] = pCut; - } -// printf( "%d ", Counter ); - - // update the number of cuts - if ( pCutSet->nCuts < pCutSet->nCutsMax ) - pCutSet->nCuts++; -} - -/**Function************************************************************* - - Synopsis [Computes area flow.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_CutFlow( If_Man_t * p, If_Cut_t * pCut ) -{ - If_Obj_t * pLeaf; - float Flow; - int i; - assert( p->pPars->fSeqMap || pCut->nLeaves > 1 ); - Flow = If_CutLutArea(p, pCut); - If_CutForEachLeaf( p, pCut, pLeaf, i ) - { - if ( pLeaf->nRefs == 0 ) - Flow += If_ObjCutBest(pLeaf)->Area; - else if ( p->pPars->fSeqMap ) // seq - Flow += If_ObjCutBest(pLeaf)->Area / pLeaf->nRefs; - else - { - assert( pLeaf->EstRefs > p->fEpsilon ); - Flow += If_ObjCutBest(pLeaf)->Area / pLeaf->EstRefs; - } - } - return Flow; -} - -/**Function************************************************************* - - Synopsis [Average number of references of the leaves.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_CutAverageRefs( If_Man_t * p, If_Cut_t * pCut ) -{ - If_Obj_t * pLeaf; - int nRefsTotal, i; - assert( p->pPars->fSeqMap || pCut->nLeaves > 1 ); - nRefsTotal = 0; - If_CutForEachLeaf( p, pCut, pLeaf, i ) - nRefsTotal += pLeaf->nRefs; - return ((float)nRefsTotal)/pCut->nLeaves; -} - -/**Function************************************************************* - - Synopsis [Computes area of the first level.] - - Description [The cut need to be derefed.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_CutDeref( If_Man_t * p, If_Cut_t * pCut, int nLevels ) -{ - If_Obj_t * pLeaf; - float Area; - int i; - Area = If_CutLutArea(p, pCut); - If_CutForEachLeaf( p, pCut, pLeaf, i ) - { - assert( pLeaf->nRefs > 0 ); - if ( --pLeaf->nRefs > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 ) - continue; - Area += If_CutDeref( p, If_ObjCutBest(pLeaf), nLevels - 1 ); - } - return Area; -} - -/**Function************************************************************* - - Synopsis [Computes area of the first level.] - - Description [The cut need to be derefed.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_CutRef( If_Man_t * p, If_Cut_t * pCut, int nLevels ) -{ - If_Obj_t * pLeaf; - float Area; - int i; - Area = If_CutLutArea(p, pCut); - If_CutForEachLeaf( p, pCut, pLeaf, i ) - { - assert( pLeaf->nRefs >= 0 ); - if ( pLeaf->nRefs++ > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 ) - continue; - Area += If_CutRef( p, If_ObjCutBest(pLeaf), nLevels - 1 ); - } - return Area; -} - -/**Function************************************************************* - - Synopsis [Prints one cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_CutPrint( If_Man_t * p, If_Cut_t * pCut ) -{ - unsigned i; - printf( "{" ); - for ( i = 0; i < pCut->nLeaves; i++ ) - printf( " %d", pCut->pLeaves[i] ); - printf( " }\n" ); -} - -/**Function************************************************************* - - Synopsis [Prints one cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_CutPrintTiming( If_Man_t * p, If_Cut_t * pCut ) -{ - If_Obj_t * pLeaf; - unsigned i; - printf( "{" ); - If_CutForEachLeaf( p, pCut, pLeaf, i ) - printf( " %d(%.2f/%.2f)", pLeaf->Id, If_ObjCutBest(pLeaf)->Delay, pLeaf->Required ); - printf( " }\n" ); -} - -/**Function************************************************************* - - Synopsis [Computes area of the first level.] - - Description [The cut need to be derefed.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_CutAreaDerefed( If_Man_t * p, If_Cut_t * pCut, int nLevels ) -{ - float aResult, aResult2; - assert( p->pPars->fSeqMap || pCut->nLeaves > 1 ); - aResult2 = If_CutRef( p, pCut, nLevels ); - aResult = If_CutDeref( p, pCut, nLevels ); - assert( aResult > aResult2 - p->fEpsilon ); - assert( aResult < aResult2 + p->fEpsilon ); - return aResult; -} - -/**Function************************************************************* - - Synopsis [Computes area of the first level.] - - Description [The cut need to be derefed.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_CutAreaRefed( If_Man_t * p, If_Cut_t * pCut, int nLevels ) -{ - float aResult, aResult2; - assert( p->pPars->fSeqMap || pCut->nLeaves > 1 ); - aResult2 = If_CutDeref( p, pCut, nLevels ); - aResult = If_CutRef( p, pCut, nLevels ); - assert( aResult > aResult2 - p->fEpsilon ); - assert( aResult < aResult2 + p->fEpsilon ); - return aResult; -} - -/**Function************************************************************* - - Synopsis [Moves the cut over the latch.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_CutLift( If_Cut_t * pCut ) -{ - unsigned i; - for ( i = 0; i < pCut->nLeaves; i++ ) - { - assert( (pCut->pLeaves[i] & 255) < 255 ); - pCut->pLeaves[i]++; - } -} - -/**Function************************************************************* - - Synopsis [Computes area of the first level.] - - Description [The cut need to be derefed.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_CutCopy( If_Man_t * p, If_Cut_t * pCutDest, If_Cut_t * pCutSrc ) -{ - int * pLeaves; - char * pPerm; - unsigned * pTruth; - // save old arrays - pLeaves = pCutDest->pLeaves; - pPerm = pCutDest->pPerm; - pTruth = pCutDest->pTruth; - // copy the cut info - memcpy( pCutDest, pCutSrc, p->nCutBytes ); - // restore the arrays - pCutDest->pLeaves = pLeaves; - pCutDest->pPerm = pPerm; - pCutDest->pTruth = pTruth; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c deleted file mode 100644 index b713d80d..00000000 --- a/src/map/if/ifMan.c +++ /dev/null @@ -1,570 +0,0 @@ -/**CFile**************************************************************** - - FileName [ifMan.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [Mapping manager.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: ifMan.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "if.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -static If_Obj_t * If_ManSetupObj( If_Man_t * p ); - -static void If_ManCutSetRecycle( If_Man_t * p, If_Set_t * pSet ) { pSet->pNext = p->pFreeList; p->pFreeList = pSet; } -static If_Set_t * If_ManCutSetFetch( If_Man_t * p ) { If_Set_t * pTemp = p->pFreeList; p->pFreeList = p->pFreeList->pNext; return pTemp; } - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Starts the AIG manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Man_t * If_ManStart( If_Par_t * pPars ) -{ - If_Man_t * p; - // start the manager - p = ALLOC( If_Man_t, 1 ); - memset( p, 0, sizeof(If_Man_t) ); - p->pPars = pPars; - p->fEpsilon = (float)0.001; - // allocate arrays for nodes - p->vCis = Vec_PtrAlloc( 100 ); - p->vCos = Vec_PtrAlloc( 100 ); - p->vObjs = Vec_PtrAlloc( 100 ); - p->vMapped = Vec_PtrAlloc( 100 ); - p->vTemp = Vec_PtrAlloc( 100 ); - // prepare the memory manager - p->nTruthWords = p->pPars->fTruth? If_CutTruthWords( p->pPars->nLutSize ) : 0; - p->nPermWords = p->pPars->fUsePerm? If_CutPermWords( p->pPars->nLutSize ) : 0; - p->nObjBytes = sizeof(If_Obj_t) + sizeof(int) * (p->pPars->nLutSize + p->nPermWords + p->nTruthWords); - p->nCutBytes = sizeof(If_Cut_t) + sizeof(int) * (p->pPars->nLutSize + p->nPermWords + p->nTruthWords); - p->nSetBytes = sizeof(If_Set_t) + (sizeof(If_Cut_t *) + p->nCutBytes) * (p->pPars->nCutsMax + 1); - p->pMemObj = Mem_FixedStart( p->nObjBytes ); -// p->pMemSet = Mem_FixedStart( p->nSetBytes ); - // report expected memory usage - if ( p->pPars->fVerbose ) - printf( "Memory (bytes): Truth = %4d. Cut = %4d. Obj = %4d. Set = %4d.\n", - 4 * p->nTruthWords, p->nCutBytes, p->nObjBytes, p->nSetBytes ); - // room for temporary truth tables - p->puTemp[0] = p->pPars->fTruth? ALLOC( unsigned, 4 * p->nTruthWords ) : NULL; - p->puTemp[1] = p->puTemp[0] + p->nTruthWords; - p->puTemp[2] = p->puTemp[1] + p->nTruthWords; - p->puTemp[3] = p->puTemp[2] + p->nTruthWords; - // create the constant node - p->pConst1 = If_ManSetupObj( p ); - p->pConst1->Type = IF_CONST1; - p->pConst1->fPhase = 1; - p->nObjs[IF_CONST1]++; - return p; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManRestart( If_Man_t * p ) -{ - FREE( p->pMemCi ); - Vec_PtrClear( p->vCis ); - Vec_PtrClear( p->vCos ); - Vec_PtrClear( p->vObjs ); - Vec_PtrClear( p->vMapped ); - Vec_PtrClear( p->vTemp ); - Mem_FixedRestart( p->pMemObj ); - // create the constant node - p->pConst1 = If_ManSetupObj( p ); - p->pConst1->Type = IF_CONST1; - p->pConst1->fPhase = 1; - // reset the counter of other nodes - p->nObjs[IF_CI] = p->nObjs[IF_CO] = p->nObjs[IF_AND] = 0; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManStop( If_Man_t * p ) -{ - Vec_PtrFree( p->vCis ); - Vec_PtrFree( p->vCos ); - Vec_PtrFree( p->vObjs ); - Vec_PtrFree( p->vMapped ); - Vec_PtrFree( p->vTemp ); - if ( p->vLatchOrder ) Vec_PtrFree( p->vLatchOrder ); - if ( p->vLags ) Vec_IntFree( p->vLags ); - Mem_FixedStop( p->pMemObj, 0 ); - FREE( p->pMemCi ); - FREE( p->pMemAnd ); - FREE( p->puTemp[0] ); - // free pars memory - if ( p->pPars->pTimesArr ) - FREE( p->pPars->pTimesArr ); - if ( p->pPars->pTimesReq ) - FREE( p->pPars->pTimesReq ); - free( p ); -} - -/**Function************************************************************* - - Synopsis [Creates primary input.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * If_ManCreateCi( If_Man_t * p ) -{ - If_Obj_t * pObj; - pObj = If_ManSetupObj( p ); - pObj->Type = IF_CI; - Vec_PtrPush( p->vCis, pObj ); - p->nObjs[IF_CI]++; - return pObj; -} - -/**Function************************************************************* - - Synopsis [Creates primary output with the given driver.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * If_ManCreateCo( If_Man_t * p, If_Obj_t * pDriver ) -{ - If_Obj_t * pObj; - pObj = If_ManSetupObj( p ); - Vec_PtrPush( p->vCos, pObj ); - pObj->Type = IF_CO; - pObj->fCompl0 = If_IsComplement(pDriver); pDriver = If_Regular(pDriver); - pObj->pFanin0 = pDriver; pDriver->nRefs++; - p->nObjs[IF_CO]++; - return pObj; -} - -/**Function************************************************************* - - Synopsis [Create the new node assuming it does not exist.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * If_ManCreateAnd( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1 ) -{ - If_Obj_t * pObj; - // perform constant propagation - if ( pFan0 == pFan1 ) - return pFan0; - if ( pFan0 == If_Not(pFan1) ) - return If_Not(p->pConst1); - if ( If_Regular(pFan0) == p->pConst1 ) - return pFan0 == p->pConst1 ? pFan1 : If_Not(p->pConst1); - if ( If_Regular(pFan1) == p->pConst1 ) - return pFan1 == p->pConst1 ? pFan0 : If_Not(p->pConst1); - // get memory for the new object - pObj = If_ManSetupObj( p ); - pObj->Type = IF_AND; - pObj->fCompl0 = If_IsComplement(pFan0); pFan0 = If_Regular(pFan0); - pObj->fCompl1 = If_IsComplement(pFan1); pFan1 = If_Regular(pFan1); - pObj->pFanin0 = pFan0; pFan0->nRefs++; pFan0->nVisits++; pFan0->nVisitsCopy++; - pObj->pFanin1 = pFan1; pFan1->nRefs++; pFan1->nVisits++; pFan1->nVisitsCopy++; - pObj->fPhase = (pObj->fCompl0 ^ pFan0->fPhase) & (pObj->fCompl1 ^ pFan1->fPhase); - pObj->Level = 1 + IF_MAX( pFan0->Level, pFan1->Level ); - if ( p->nLevelMax < (int)pObj->Level ) - p->nLevelMax = (int)pObj->Level; - p->nObjs[IF_AND]++; - return pObj; -} - -/**Function************************************************************* - - Synopsis [Create the new node assuming it does not exist.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * If_ManCreateXor( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1 ) -{ - If_Obj_t * pRes1, * pRes2; - pRes1 = If_ManCreateAnd( p, If_Not(pFan0), pFan1 ); - pRes2 = If_ManCreateAnd( p, pFan0, If_Not(pFan1) ); - return If_Not( If_ManCreateAnd( p, If_Not(pRes1), If_Not(pRes2) ) ); -} - -/**Function************************************************************* - - Synopsis [Create the new node assuming it does not exist.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * If_ManCreateMux( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1, If_Obj_t * pCtrl ) -{ - If_Obj_t * pRes1, * pRes2; - pRes1 = If_ManCreateAnd( p, pFan0, If_Not(pCtrl) ); - pRes2 = If_ManCreateAnd( p, pFan1, pCtrl ); - return If_Not( If_ManCreateAnd( p, If_Not(pRes1), If_Not(pRes2) ) ); -} - -/**Function************************************************************* - - Synopsis [Creates the choice node.] - - Description [Should be called after the equivalence class nodes are linked.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManCreateChoice( If_Man_t * p, If_Obj_t * pObj ) -{ - If_Obj_t * pTemp; - // mark the node as a representative if its class - assert( pObj->fRepr == 0 ); - pObj->fRepr = 1; - // update the level of this node (needed for correct required time computation) - for ( pTemp = pObj; pTemp; pTemp = pTemp->pEquiv ) - { - pObj->Level = IF_MAX( pObj->Level, pTemp->Level ); - pTemp->nVisits++; pTemp->nVisitsCopy++; - } - // mark the largest level - if ( p->nLevelMax < (int)pObj->Level ) - p->nLevelMax = (int)pObj->Level; -} - -/**Function************************************************************* - - Synopsis [Prepares memory for one cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManSetupCut( If_Man_t * p, If_Cut_t * pCut ) -{ - memset( pCut, 0, sizeof(If_Cut_t) ); - pCut->nLimit = p->pPars->nLutSize; - pCut->pLeaves = (int *)(pCut + 1); - if ( p->pPars->fUsePerm ) - pCut->pPerm = (char *)(pCut->pLeaves + p->pPars->nLutSize); - if ( p->pPars->fTruth ) - pCut->pTruth = pCut->pLeaves + p->pPars->nLutSize + p->nPermWords; -} - -/**Function************************************************************* - - Synopsis [Prepares memory for one cutset.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManSetupSet( If_Man_t * p, If_Set_t * pSet ) -{ - char * pArray; - int i; - pSet->nCuts = 0; - pSet->nCutsMax = p->pPars->nCutsMax; - pSet->ppCuts = (If_Cut_t **)(pSet + 1); - pArray = (char *)pSet->ppCuts + sizeof(If_Cut_t *) * (pSet->nCutsMax+1); - for ( i = 0; i <= pSet->nCutsMax; i++ ) - { - pSet->ppCuts[i] = (If_Cut_t *)(pArray + i * p->nCutBytes); - If_ManSetupCut( p, pSet->ppCuts[i] ); - } -// pArray += (pSet->nCutsMax + 1) * p->nCutBytes; -// assert( ((char *)pArray) - ((char *)pSet) == p->nSetBytes ); -} - -/**Function************************************************************* - - Synopsis [Prepares memory for one cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManSetupCutTriv( If_Man_t * p, If_Cut_t * pCut, int ObjId ) -{ - pCut->fCompl = 0; - pCut->nLimit = p->pPars->nLutSize; - pCut->nLeaves = 1; - pCut->pLeaves[0] = p->pPars->fLiftLeaves? (ObjId << 8) : ObjId; - pCut->uSign = If_ObjCutSign( pCut->pLeaves[0] ); - // set up elementary truth table of the unit cut - if ( p->pPars->fTruth ) - { - int i, nTruthWords; - nTruthWords = pCut->nLimit <= 5 ? 1 : (1 << (pCut->nLimit - 5)); - for ( i = 0; i < nTruthWords; i++ ) - If_CutTruth(pCut)[i] = 0xAAAAAAAA; - } -} - -/**Function************************************************************* - - Synopsis [Prepares memory for the node with cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * If_ManSetupObj( If_Man_t * p ) -{ - If_Obj_t * pObj; - // get memory for the object - pObj = (If_Obj_t *)Mem_FixedEntryFetch( p->pMemObj ); - memset( pObj, 0, sizeof(If_Obj_t) ); - If_ManSetupCut( p, &pObj->CutBest ); - // assign ID and save - pObj->Id = Vec_PtrSize(p->vObjs); - Vec_PtrPush( p->vObjs, pObj ); - // set the required times - pObj->Required = IF_FLOAT_LARGE; - return pObj; -} - -/**Function************************************************************* - - Synopsis [Prepares memory for one cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManSetupCiCutSets( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i; - assert( p->pMemCi == NULL ); - // create elementary cuts for the CIs - If_ManForEachCi( p, pObj, i ) - If_ManSetupCutTriv( p, &pObj->CutBest, pObj->Id ); - // create elementary cutsets for the CIs - p->pMemCi = (If_Set_t *)malloc( If_ManCiNum(p) * (sizeof(If_Set_t) + sizeof(void *)) ); - If_ManForEachCi( p, pObj, i ) - { - pObj->pCutSet = (If_Set_t *)((char *)p->pMemCi + i * (sizeof(If_Set_t) + sizeof(void *))); - pObj->pCutSet->nCuts = 1; - pObj->pCutSet->nCutsMax = p->pPars->nCutsMax; - pObj->pCutSet->ppCuts = (If_Cut_t **)(pObj->pCutSet + 1); - pObj->pCutSet->ppCuts[0] = &pObj->CutBest; - } -} - -/**Function************************************************************* - - Synopsis [Prepares cutset of the node.] - - Description [Elementary cutset will be added last.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Set_t * If_ManSetupNodeCutSet( If_Man_t * p, If_Obj_t * pObj ) -{ - assert( If_ObjIsAnd(pObj) ); - assert( pObj->pCutSet == NULL ); -// pObj->pCutSet = (If_Set_t *)Mem_FixedEntryFetch( p->pMemSet ); -// If_ManSetupSet( p, pObj->pCutSet ); - - pObj->pCutSet = If_ManCutSetFetch( p ); - pObj->pCutSet->nCuts = 0; - pObj->pCutSet->nCutsMax = p->pPars->nCutsMax; - - return pObj->pCutSet; -} - -/**Function************************************************************* - - Synopsis [Dereferences cutset of the node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManDerefNodeCutSet( If_Man_t * p, If_Obj_t * pObj ) -{ - If_Obj_t * pFanin; - assert( If_ObjIsAnd(pObj) ); - // consider the node - assert( pObj->nVisits >= 0 ); - if ( pObj->nVisits == 0 ) - { -// Mem_FixedEntryRecycle( p->pMemSet, (char *)pObj->pCutSet ); - If_ManCutSetRecycle( p, pObj->pCutSet ); - pObj->pCutSet = NULL; - } - // consider the first fanin - pFanin = If_ObjFanin0(pObj); - assert( pFanin->nVisits > 0 ); - if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 ) - { -// Mem_FixedEntryRecycle( p->pMemSet, (char *)pFanin->pCutSet ); - If_ManCutSetRecycle( p, pFanin->pCutSet ); - pFanin->pCutSet = NULL; - } - // consider the second fanin - pFanin = If_ObjFanin1(pObj); - assert( pFanin->nVisits > 0 ); - if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 ) - { -// Mem_FixedEntryRecycle( p->pMemSet, (char *)pFanin->pCutSet ); - If_ManCutSetRecycle( p, pFanin->pCutSet ); - pFanin->pCutSet = NULL; - } -} - -/**Function************************************************************* - - Synopsis [Dereferences cutset of the node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManDerefChoiceCutSet( If_Man_t * p, If_Obj_t * pObj ) -{ - If_Obj_t * pTemp; - assert( If_ObjIsAnd(pObj) ); - assert( pObj->fRepr ); - assert( pObj->nVisits > 0 ); - // consider the nodes in the choice class - for ( pTemp = pObj; pTemp; pTemp = pTemp->pEquiv ) - { - assert( pTemp == pObj || pTemp->nVisits == 1 ); - if ( --pTemp->nVisits == 0 ) - { -// Mem_FixedEntryRecycle( p->pMemSet, (char *)pTemp->pCutSet ); - If_ManCutSetRecycle( p, pTemp->pCutSet ); - pTemp->pCutSet = NULL; - } - } -} - -/**Function************************************************************* - - Synopsis [Dereferences cutset of the node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManSetupSetAll( If_Man_t * p, int nCrossCut ) -{ - If_Set_t * pCutSet; - int i, nCutSets; - nCutSets = 128 + nCrossCut; - p->pFreeList = p->pMemAnd = pCutSet = (If_Set_t *)malloc( nCutSets * p->nSetBytes ); - for ( i = 0; i < nCutSets; i++ ) - { - If_ManSetupSet( p, pCutSet ); - if ( i == nCutSets - 1 ) - pCutSet->pNext = NULL; - else - pCutSet->pNext = (If_Set_t *)( (char *)pCutSet + p->nSetBytes ); - pCutSet = pCutSet->pNext; - } - assert( pCutSet == NULL ); - - if ( p->pPars->fVerbose ) - { - printf( "Node = %7d. Ch = %5d. Total mem = %7.2f Mb. Peak cut mem = %7.2f Mb.\n", - If_ManAndNum(p), p->nChoices, - 1.0 * (p->nObjBytes + 2*sizeof(void *)) * If_ManObjNum(p) / (1<<20), - 1.0 * p->nSetBytes * nCrossCut / (1<<20) ); - } -// printf( "Cross cut = %d.\n", nCrossCut ); - -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c deleted file mode 100644 index e3f0dfda..00000000 --- a/src/map/if/ifMap.c +++ /dev/null @@ -1,300 +0,0 @@ -/**CFile**************************************************************** - - FileName [ifMap.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [Mapping procedures.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: ifMap.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "if.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Counts the number of 1s in the signature.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int If_WordCountOnes( unsigned uWord ) -{ - uWord = (uWord & 0x55555555) + ((uWord>>1) & 0x55555555); - uWord = (uWord & 0x33333333) + ((uWord>>2) & 0x33333333); - uWord = (uWord & 0x0F0F0F0F) + ((uWord>>4) & 0x0F0F0F0F); - uWord = (uWord & 0x00FF00FF) + ((uWord>>8) & 0x00FF00FF); - return (uWord & 0x0000FFFF) + (uWord>>16); -} - -/**Function************************************************************* - - Synopsis [Finds the best cut for the given node.] - - Description [Mapping modes: delay (0), area flow (1), area (2).] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess ) -{ - If_Set_t * pCutSet; - If_Cut_t * pCut0, * pCut1, * pCut; - int i, k; - - assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin0) || pObj->pFanin0->pCutSet->nCuts > 1 ); - assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin1) || pObj->pFanin1->pCutSet->nCuts > 1 ); - - // prepare - if ( !p->pPars->fSeqMap ) - { - if ( Mode == 0 ) - pObj->EstRefs = (float)pObj->nRefs; - else if ( Mode == 1 ) - pObj->EstRefs = (float)((2.0 * pObj->EstRefs + pObj->nRefs) / 3.0); - } - if ( Mode && pObj->nRefs > 0 ) - If_CutDeref( p, If_ObjCutBest(pObj), IF_INFINITY ); - - // prepare the cutset - pCutSet = If_ManSetupNodeCutSet( p, pObj ); - - // get the current assigned best cut - pCut = If_ObjCutBest(pObj); - if ( pCut->nLeaves > 0 ) - { - // recompute the parameters of the best cut - pCut->Delay = If_CutDelay( p, pCut ); - assert( pCut->Delay <= pObj->Required + p->fEpsilon ); - pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, IF_INFINITY ) : If_CutFlow( p, pCut ); - // save the best cut from the previous iteration - if ( !fPreprocess ) - If_CutCopy( p, pCutSet->ppCuts[pCutSet->nCuts++], pCut ); - } - - // generate cuts - If_ObjForEachCut( pObj->pFanin0, pCut0, i ) - If_ObjForEachCut( pObj->pFanin1, pCut1, k ) - { - // get the next free cut - assert( pCutSet->nCuts <= pCutSet->nCutsMax ); - pCut = pCutSet->ppCuts[pCutSet->nCuts]; - // make sure K-feasible cut exists - if ( If_WordCountOnes(pCut0->uSign | pCut1->uSign) > p->pPars->nLutSize ) - continue; - // merge the nodes - if ( !If_CutMerge( pCut0, pCut1, pCut ) ) - continue; - assert( p->pPars->fSeqMap || pCut->nLeaves > 1 ); - p->nCutsMerged++; - // check if this cut is contained in any of the available cuts -// if ( p->pPars->pFuncCost == NULL && If_CutFilter( p, pCut ) ) // do not filter functionality cuts - if ( If_CutFilter( pCutSet, pCut ) ) - continue; - // compute the truth table - pCut->fCompl = 0; - if ( p->pPars->fTruth ) - If_CutComputeTruth( p, pCut, pCut0, pCut1, pObj->fCompl0, pObj->fCompl1 ); - // compute the application-specific cost and depth - pCut->fUser = (p->pPars->pFuncCost != NULL); - pCut->Cost = p->pPars->pFuncCost? p->pPars->pFuncCost(pCut) : 0; - if ( pCut->Cost == IF_COST_MAX ) - continue; - // check if the cut satisfies the required times - pCut->Delay = If_CutDelay( p, pCut ); -// printf( "%.2f ", pCut->Delay ); - if ( Mode && pCut->Delay > pObj->Required + p->fEpsilon ) - continue; - // compute area of the cut (this area may depend on the application specific cost) - pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, IF_INFINITY ) : If_CutFlow( p, pCut ); - pCut->AveRefs = (Mode == 0)? (float)0.0 : If_CutAverageRefs( p, pCut ); - // insert the cut into storage - If_CutSort( p, pCutSet, pCut ); - } - assert( pCutSet->nCuts > 0 ); - - // add the trivial cut to the set - If_ManSetupCutTriv( p, pCutSet->ppCuts[pCutSet->nCuts++], pObj->Id ); - assert( pCutSet->nCuts <= pCutSet->nCutsMax+1 ); - - // update the best cut - if ( !fPreprocess || pCutSet->ppCuts[0]->Delay <= pObj->Required + p->fEpsilon ) - If_CutCopy( p, If_ObjCutBest(pObj), pCutSet->ppCuts[0] ); - assert( p->pPars->fSeqMap || If_ObjCutBest(pObj)->nLeaves > 1 ); - - // ref the selected cut - if ( Mode && pObj->nRefs > 0 ) - If_CutRef( p, If_ObjCutBest(pObj), IF_INFINITY ); - - // call the user specified function for each cut - if ( p->pPars->pFuncUser ) - If_ObjForEachCut( pObj, pCut, i ) - p->pPars->pFuncUser( p, pObj, pCut ); - - // free the cuts - If_ManDerefNodeCutSet( p, pObj ); -} - -/**Function************************************************************* - - Synopsis [Finds the best cut for the choice node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess ) -{ - If_Set_t * pCutSet; - If_Obj_t * pTemp; - If_Cut_t * pCutTemp, * pCut; - int i; - assert( pObj->pEquiv != NULL ); - - // prepare - if ( Mode && pObj->nRefs > 0 ) - If_CutDeref( p, If_ObjCutBest(pObj), IF_INFINITY ); - - // remove elementary cuts - for ( pTemp = pObj; pTemp; pTemp = pTemp->pEquiv ) - pTemp->pCutSet->nCuts--; - - // update the cutset of the node - pCutSet = pObj->pCutSet; - - // generate cuts - for ( pTemp = pObj->pEquiv; pTemp; pTemp = pTemp->pEquiv ) - { - assert( pTemp->nRefs == 0 ); - assert( p->pPars->fSeqMap || pTemp->pCutSet->nCuts > 0 ); - // go through the cuts of this node - If_ObjForEachCut( pTemp, pCutTemp, i ) - { - assert( p->pPars->fSeqMap || pCutTemp->nLeaves > 1 ); - // get the next free cut - assert( pCutSet->nCuts <= pCutSet->nCutsMax ); - pCut = pCutSet->ppCuts[pCutSet->nCuts]; - // copy the cut into storage - If_CutCopy( p, pCut, pCutTemp ); - // check if this cut is contained in any of the available cuts - if ( If_CutFilter( pCutSet, pCut ) ) - continue; - // check if the cut satisfies the required times - assert( pCut->Delay == If_CutDelay( p, pCut ) ); - if ( Mode && pCut->Delay > pObj->Required + p->fEpsilon ) - continue; - // set the phase attribute - assert( pCut->fCompl == 0 ); - pCut->fCompl ^= (pObj->fPhase ^ pTemp->fPhase); // why ^= ? - // compute area of the cut (this area may depend on the application specific cost) - pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, IF_INFINITY ) : If_CutFlow( p, pCut ); - pCut->AveRefs = (Mode == 0)? (float)0.0 : If_CutAverageRefs( p, pCut ); - // insert the cut into storage - If_CutSort( p, pCutSet, pCut ); - } - } - assert( pCutSet->nCuts > 0 ); - - // add the trivial cut to the set - If_ManSetupCutTriv( p, pCutSet->ppCuts[pCutSet->nCuts++], pObj->Id ); - assert( pCutSet->nCuts <= pCutSet->nCutsMax+1 ); - - // update the best cut - if ( !fPreprocess || pCutSet->ppCuts[0]->Delay <= pObj->Required + p->fEpsilon ) - If_CutCopy( p, If_ObjCutBest(pObj), pCutSet->ppCuts[0] ); - assert( p->pPars->fSeqMap || If_ObjCutBest(pObj)->nLeaves > 1 ); - - // ref the selected cut - if ( Mode && pObj->nRefs > 0 ) - If_CutRef( p, If_ObjCutBest(pObj), IF_INFINITY ); - - // free the cuts - If_ManDerefChoiceCutSet( p, pObj ); -} - -/**Function************************************************************* - - Synopsis [Performs one mapping pass over all nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fPreprocess, char * pLabel ) -{ -// ProgressBar * pProgress; - If_Obj_t * pObj; - int i, clk = clock(); - assert( Mode >= 0 && Mode <= 2 ); - // set the sorting function - if ( Mode || p->pPars->fArea ) // area - p->SortMode = 1; - else if ( p->pPars->fFancy ) - p->SortMode = 2; - else - p->SortMode = 0; - // set the cut number - p->nCutsUsed = nCutsUsed; - p->nCutsMerged = 0; - // map the internal nodes -// pProgress = Extra_ProgressBarStart( stdout, If_ManObjNum(p) ); - If_ManForEachNode( p, pObj, i ) - { -// Extra_ProgressBarUpdate( pProgress, i, pLabel ); - If_ObjPerformMappingAnd( p, pObj, Mode, fPreprocess ); - if ( pObj->fRepr ) - If_ObjPerformMappingChoice( p, pObj, Mode, fPreprocess ); - } -// Extra_ProgressBarStop( pProgress ); - // make sure the visit counters are all zero - If_ManForEachNode( p, pObj, i ) - assert( pObj->nVisits == 0 ); - // compute required times and stats - If_ManComputeRequired( p ); - if ( p->pPars->fVerbose ) - { - char Symb = fPreprocess? 'P' : ((Mode == 0)? 'D' : ((Mode == 1)? 'F' : 'A')); - printf( "%c: Del = %7.2f. Ar = %9.1f. Net = %8d. Cut = %8d. ", - Symb, p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged ); - PRT( "T", clock() - clk ); -// printf( "Max number of cuts = %d. Average number of cuts = %5.2f.\n", -// p->nCutsMax, 1.0 * p->nCutsMerged / If_ManAndNum(p) ); - } - return 1; -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/map/if/ifReduce.c b/src/map/if/ifReduce.c deleted file mode 100644 index 9728b3db..00000000 --- a/src/map/if/ifReduce.c +++ /dev/null @@ -1,574 +0,0 @@ -/**CFile**************************************************************** - - FileName [ifExpand.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [Incremental improvement of current mapping.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: ifExpand.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "if.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -static void If_ManImproveReduce( If_Man_t * p, int nLimit ); -static void If_ManImproveExpand( If_Man_t * p, int nLimit ); -static void If_ManImproveNodeExpand( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld, Vec_Ptr_t * vVisited ); -static void If_ManImproveNodePrepare( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld, Vec_Ptr_t * vVisited ); -static void If_ManImproveNodeUpdate( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vFront ); -static void If_ManImproveNodeFaninCompact( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited ); - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Improves current mapping using expand/Expand of one cut.] - - Description [Assumes current mapping assigned and required times computed.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveMapping( If_Man_t * p ) -{ - int clk; - - clk = clock(); - If_ManImproveExpand( p, p->pPars->nLutSize ); - If_ManComputeRequired( p ); - if ( p->pPars->fVerbose ) - { - printf( "E: Del = %7.2f. Ar = %9.1f. Net = %8d. Cut = %8d. ", - p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged ); - PRT( "T", clock() - clk ); - } - -/* - clk = clock(); - If_ManImproveReduce( p, p->pPars->nLutSize ); - If_ManComputeRequired( p, 0 ); - if ( p->pPars->fVerbose ) - { - printf( "R: Del = %6.2f. Area = %8.2f. Nets = %6d. Cuts = %8d. Lim = %2d. Ave = %5.2f. ", - p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) ); - PRT( "T", clock() - clk ); - } -*/ -/* - clk = clock(); - If_ManImproveExpand( p, p->pPars->nLutSize ); - If_ManComputeRequired( p, 0 ); - if ( p->pPars->fVerbose ) - { - printf( "E: Del = %6.2f. Area = %8.2f. Nets = %6d. Cuts = %8d. Lim = %2d. Ave = %5.2f. ", - p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) ); - PRT( "T", clock() - clk ); - } -*/ -} - -/**Function************************************************************* - - Synopsis [Performs area recovery for each node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveExpand( If_Man_t * p, int nLimit ) -{ - Vec_Ptr_t * vFront, * vFrontOld, * vVisited; - If_Obj_t * pObj; - int i; - vFront = Vec_PtrAlloc( nLimit ); - vFrontOld = Vec_PtrAlloc( nLimit ); - vVisited = Vec_PtrAlloc( 100 ); - // iterate through all nodes in the topological order - If_ManForEachNode( p, pObj, i ) - If_ManImproveNodeExpand( p, pObj, nLimit, vFront, vFrontOld, vVisited ); - Vec_PtrFree( vFront ); - Vec_PtrFree( vFrontOld ); - Vec_PtrFree( vVisited ); -} - -/**Function************************************************************* - - Synopsis [Counts the number of nodes with no external fanout.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManImproveCutCost( If_Man_t * p, Vec_Ptr_t * vFront ) -{ - If_Obj_t * pFanin; - int i, Counter = 0; - Vec_PtrForEachEntry( vFront, pFanin, i ) - if ( pFanin->nRefs == 0 ) - Counter++; - return Counter; -} - -/**Function************************************************************* - - Synopsis [Performs area recovery for each node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveNodeExpand( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld, Vec_Ptr_t * vVisited ) -{ - If_Obj_t * pFanin; - If_Cut_t * pCut; - int CostBef, CostAft, i; - float DelayOld, AreaBef, AreaAft; - pCut = If_ObjCutBest(pObj); - assert( pCut->Delay <= pObj->Required + p->fEpsilon ); - if ( pObj->nRefs == 0 ) - return; - // get the delay - DelayOld = pCut->Delay; - // get the area - AreaBef = If_CutAreaRefed( p, pCut, IF_INFINITY ); -// if ( AreaBef == 1 ) -// return; - // the cut is non-trivial - If_ManImproveNodePrepare( p, pObj, nLimit, vFront, vFrontOld, vVisited ); - // iteratively modify the cut - If_CutDeref( p, pCut, IF_INFINITY ); - CostBef = If_ManImproveCutCost( p, vFront ); - If_ManImproveNodeFaninCompact( p, pObj, nLimit, vFront, vVisited ); - CostAft = If_ManImproveCutCost( p, vFront ); - If_CutRef( p, pCut, IF_INFINITY ); - assert( CostBef >= CostAft ); - // clean up - Vec_PtrForEachEntry( vVisited, pFanin, i ) - pFanin->fMark = 0; - // update the node - If_ManImproveNodeUpdate( p, pObj, vFront ); - pCut->Delay = If_CutDelay( p, pCut ); - // get the new area - AreaAft = If_CutAreaRefed( p, pCut, IF_INFINITY ); - if ( AreaAft > AreaBef || pCut->Delay > pObj->Required + p->fEpsilon ) - { - If_ManImproveNodeUpdate( p, pObj, vFrontOld ); - AreaAft = If_CutAreaRefed( p, pCut, IF_INFINITY ); - assert( AreaAft == AreaBef ); - pCut->Delay = DelayOld; - } -} - -/**Function************************************************************* - - Synopsis [Performs area recovery for each node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveMark_rec( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vVisited ) -{ - if ( pObj->fMark ) - return; - assert( If_ObjIsAnd(pObj) ); - If_ManImproveMark_rec( p, If_ObjFanin0(pObj), vVisited ); - If_ManImproveMark_rec( p, If_ObjFanin1(pObj), vVisited ); - Vec_PtrPush( vVisited, pObj ); - pObj->fMark = 1; -} - -/**Function************************************************************* - - Synopsis [Prepares node mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveNodePrepare( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld, Vec_Ptr_t * vVisited ) -{ - If_Cut_t * pCut; - If_Obj_t * pLeaf; - int i; - Vec_PtrClear( vFront ); - Vec_PtrClear( vFrontOld ); - Vec_PtrClear( vVisited ); - // expand the cut downwards from the given place - pCut = If_ObjCutBest(pObj); - If_CutForEachLeaf( p, pCut, pLeaf, i ) - { - Vec_PtrPush( vFront, pLeaf ); - Vec_PtrPush( vFrontOld, pLeaf ); - Vec_PtrPush( vVisited, pLeaf ); - pLeaf->fMark = 1; - } - // mark the nodes in the cone - If_ManImproveMark_rec( p, pObj, vVisited ); -} - -/**Function************************************************************* - - Synopsis [Updates the frontier.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveNodeUpdate( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vFront ) -{ - If_Cut_t * pCut; - If_Obj_t * pFanin; - int i; - pCut = If_ObjCutBest(pObj); - // deref node's cut - If_CutDeref( p, pCut, IF_INFINITY ); - // update the node's cut - pCut->nLeaves = Vec_PtrSize(vFront); - Vec_PtrForEachEntry( vFront, pFanin, i ) - pCut->pLeaves[i] = pFanin->Id; - // ref the new cut - If_CutRef( p, pCut, IF_INFINITY ); -} - - -/**Function************************************************************* - - Synopsis [Returns 1 if the number of fanins will grow.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManImproveNodeWillGrow( If_Man_t * p, If_Obj_t * pObj ) -{ - If_Obj_t * pFanin0, * pFanin1; - assert( If_ObjIsAnd(pObj) ); - pFanin0 = If_ObjFanin0(pObj); - pFanin1 = If_ObjFanin1(pObj); - return !pFanin0->fMark && !pFanin1->fMark; -} - -/**Function************************************************************* - - Synopsis [Returns the increase in the number of fanins with no external refs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManImproveNodeFaninCost( If_Man_t * p, If_Obj_t * pObj ) -{ - int Counter = 0; - assert( If_ObjIsAnd(pObj) ); - // check if the node has external refs - if ( pObj->nRefs == 0 ) - Counter--; - // increment the number of fanins without external refs - if ( !If_ObjFanin0(pObj)->fMark && If_ObjFanin0(pObj)->nRefs == 0 ) - Counter++; - // increment the number of fanins without external refs - if ( !If_ObjFanin1(pObj)->fMark && If_ObjFanin1(pObj)->nRefs == 0 ) - Counter++; - return Counter; -} - -/**Function************************************************************* - - Synopsis [Updates the frontier.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveNodeFaninUpdate( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited ) -{ - If_Obj_t * pFanin; - assert( If_ObjIsAnd(pObj) ); - Vec_PtrRemove( vFront, pObj ); - pFanin = If_ObjFanin0(pObj); - if ( !pFanin->fMark ) - { - Vec_PtrPush( vFront, pFanin ); - Vec_PtrPush( vVisited, pFanin ); - pFanin->fMark = 1; - } - pFanin = If_ObjFanin1(pObj); - if ( !pFanin->fMark ) - { - Vec_PtrPush( vFront, pFanin ); - Vec_PtrPush( vVisited, pFanin ); - pFanin->fMark = 1; - } -} - -/**Function************************************************************* - - Synopsis [Compacts the number of external refs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManImproveNodeFaninCompact0( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited ) -{ - If_Obj_t * pFanin; - int i; - Vec_PtrForEachEntry( vFront, pFanin, i ) - { - if ( If_ObjIsCi(pFanin) ) - continue; - if ( If_ManImproveNodeWillGrow(p, pFanin) ) - continue; - if ( If_ManImproveNodeFaninCost(p, pFanin) <= 0 ) - { - If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited ); - return 1; - } - } - return 0; -} - -/**Function************************************************************* - - Synopsis [Compacts the number of external refs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManImproveNodeFaninCompact1( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited ) -{ - If_Obj_t * pFanin; - int i; - Vec_PtrForEachEntry( vFront, pFanin, i ) - { - if ( If_ObjIsCi(pFanin) ) - continue; - if ( If_ManImproveNodeFaninCost(p, pFanin) < 0 ) - { - If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited ); - return 1; - } - } - return 0; -} - -/**Function************************************************************* - - Synopsis [Compacts the number of external refs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManImproveNodeFaninCompact2( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited ) -{ - If_Obj_t * pFanin; - int i; - Vec_PtrForEachEntry( vFront, pFanin, i ) - { - if ( If_ObjIsCi(pFanin) ) - continue; - if ( If_ManImproveNodeFaninCost(p, pFanin) <= 0 ) - { - If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited ); - return 1; - } - } - return 0; -} - -/**Function************************************************************* - - Synopsis [Compacts the number of external refs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManImproveNodeFaninCompact_int( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited ) -{ - if ( If_ManImproveNodeFaninCompact0(p, pObj, nLimit, vFront, vVisited) ) - return 1; - if ( Vec_PtrSize(vFront) < nLimit && If_ManImproveNodeFaninCompact1(p, pObj, nLimit, vFront, vVisited) ) - return 1; - if ( Vec_PtrSize(vFront) < nLimit && If_ManImproveNodeFaninCompact2(p, pObj, nLimit, vFront, vVisited) ) - return 1; - assert( Vec_PtrSize(vFront) <= nLimit ); - return 0; -} - -/**Function************************************************************* - - Synopsis [Compacts the number of external refs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveNodeFaninCompact( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited ) -{ - while ( If_ManImproveNodeFaninCompact_int( p, pObj, nLimit, vFront, vVisited ) ); -} - - - - - -/**Function************************************************************* - - Synopsis [Performs fast mapping for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveNodeReduce( If_Man_t * p, If_Obj_t * pObj, int nLimit ) -{ -/* - If_Cut_t * pCut, * pCut0, * pCut1, * pCutR; - If_Obj_t * pFanin0, * pFanin1; - float AreaBef, AreaAft; - int RetValue; - - assert( nLimit <= 32 ); - assert( If_ObjIsAnd(pObj) ); - // get the fanins - pFanin0 = If_ObjFanin0(pObj); - pFanin1 = If_ObjFanin1(pObj); - // get the cuts - pCut = If_ObjCutBest(pObj); - pCut0 = If_ObjIsCi(pFanin0) ? If_ObjCutTriv(pFanin0) : If_ObjCutBest(pFanin0); - pCut1 = If_ObjIsCi(pFanin1) ? If_ObjCutTriv(pFanin1) : If_ObjCutBest(pFanin1); - assert( pCut->Delay <= pObj->Required + p->fEpsilon ); - - // deref the cut if the node is refed - if ( pObj->nRefs > 0 ) - If_CutDeref( p, pCut, IF_INFINITY ); - // get the area - AreaBef = If_CutAreaDerefed( p, pCut, IF_INFINITY ); - // get the fanin support - if ( pFanin0->nRefs > 2 && pCut0->Delay < pObj->Required + p->fEpsilon ) -// if ( pSupp0->nRefs > 0 && pSupp0->Delay < pSupp->DelayR ) // this leads to 2% worse results - { - pCut0 = If_ObjCutTriv(pFanin0); - } - // get the fanin support - if ( pFanin1->nRefs > 2 && pCut1->Delay < pObj->Required + p->fEpsilon ) -// if ( pSupp1->nRefs > 0 && pSupp1->Delay < pSupp->DelayR ) - { - pCut1 = If_ObjCutTriv(pFanin1); - } - - // merge the cuts - pCutR = p->ppCuts[0]; - RetValue = If_CutMerge( pCut0, pCut1, pCutR ); - // try very simple cut - if ( !RetValue ) - { - RetValue = If_CutMerge( If_ObjCutTriv(pFanin0), If_ObjCutTriv(pFanin1), pCutR ); - assert( RetValue == 1 ); - } - if ( RetValue ) - { - pCutR->Delay = If_CutDelay( p, pCutR ); - AreaAft = If_CutAreaDerefed( p, pCutR, IF_INFINITY ); - // update the best cut - if ( AreaAft < AreaBef - p->fEpsilon && pCutR->Delay < pObj->Required + p->fEpsilon ) - If_CutCopy( p, pCut, pCutR ); - } - // recompute the delay of the best cut - pCut->Delay = If_CutDelay( p, pCut ); - // ref the cut if the node is refed - if ( pObj->nRefs > 0 ) - If_CutRef( p, pCut, IF_INFINITY ); -*/ -} - -/**Function************************************************************* - - Synopsis [Performs area recovery for each node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveReduce( If_Man_t * p, int nLimit ) -{ - If_Obj_t * pObj; - int i; - If_ManForEachNode( p, pObj, i ) - If_ManImproveNodeReduce( p, pObj, nLimit ); -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/map/if/ifSeq.c b/src/map/if/ifSeq.c deleted file mode 100644 index 8d1de8c1..00000000 --- a/src/map/if/ifSeq.c +++ /dev/null @@ -1,405 +0,0 @@ -/**CFile**************************************************************** - - FileName [ifSeq.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [Sequential mapping.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: ifSeq.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "if.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -extern int s_MappingTime; - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Prepares for sequential mapping by linking the latches.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManPrepareMappingSeq( If_Man_t * p ) -{ - If_Obj_t * pObjLi, * pObjLo; - int i; - - // link the latch outputs (CIs) directly to the drivers of latch inputs (COs) - for ( i = 0; i < p->pPars->nLatches; i++ ) - { - pObjLi = If_ManLi( p, i ); - pObjLo = If_ManLo( p, i ); - pObjLo->pFanin0 = If_ObjFanin0( pObjLi ); - pObjLo->fCompl0 = If_ObjFaninC0( pObjLi ); - } -} - -/**Function************************************************************* - - Synopsis [Collects latches in the topological order.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManCollectLatches_rec( If_Obj_t * pObj, Vec_Ptr_t * vLatches ) -{ - if ( !If_ObjIsLatch(pObj) ) - return; - if ( pObj->fMark ) - return; - pObj->fMark = 1; - If_ManCollectLatches_rec( pObj->pFanin0, vLatches ); - Vec_PtrPush( vLatches, pObj ); -} - -/**Function************************************************************* - - Synopsis [Collects latches in the topological order.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Ptr_t * If_ManCollectLatches( If_Man_t * p ) -{ - Vec_Ptr_t * vLatches; - If_Obj_t * pObj; - int i; - // collect latches - vLatches = Vec_PtrAlloc( p->pPars->nLatches ); - If_ManForEachLatchOutput( p, pObj, i ) - If_ManCollectLatches_rec( pObj, vLatches ); - // clean marks - Vec_PtrForEachEntry( vLatches, pObj, i ) - pObj->fMark = 0; - assert( Vec_PtrSize(vLatches) == p->pPars->nLatches ); - return vLatches; -} - -/**Function************************************************************* - - Synopsis [Performs one pass of l-value computation over all nodes.] - - Description [Experimentally it was found that checking POs changes - is not enough to detect the convergence of l-values in the network.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManPerformMappingRoundSeq( If_Man_t * p, int nIter ) -{ - If_Obj_t * pObj; - int i, clk = clock(); - int fVeryVerbose = 0; - int fChange = 0; - - // map the internal nodes - p->nCutsMerged = 0; - If_ManForEachNode( p, pObj, i ) - { - If_ObjPerformMappingAnd( p, pObj, 0, 0 ); - if ( pObj->fRepr ) - If_ObjPerformMappingChoice( p, pObj, 0, 0 ); - } - - // postprocess the mapping -//printf( "Itereation %d: \n", nIter ); - If_ManForEachNode( p, pObj, i ) - { - // update the LValues stored separately - if ( If_ObjLValue(pObj) < If_ObjCutBest(pObj)->Delay - p->fEpsilon ) - { - If_ObjSetLValue( pObj, If_ObjCutBest(pObj)->Delay ); - fChange = 1; - } -//printf( "%d ", (int)If_ObjLValue(pObj) ); - // reset the visit counters - assert( pObj->nVisits == 0 ); - pObj->nVisits = pObj->nVisitsCopy; - } -//printf( "\n" ); - - // propagate LValues over the registers - Vec_PtrForEachEntry( p->vLatchOrder, pObj, i ) - { - If_ObjSetLValue( pObj, If_ObjLValue(If_ObjFanin0(pObj)) - p->Period ); - If_ObjSetArrTime( pObj, If_ObjLValue(pObj) ); - } - - // compute area and delay - if ( fVeryVerbose ) - { - p->RequiredGlo = If_ManDelayMax( p, 1 ); - p->AreaGlo = If_ManScanMapping(p); - printf( "S%d: Fi = %6.2f. Del = %6.2f. Area = %8.2f. Cuts = %8d. ", - nIter, (float)p->Period, p->RequiredGlo, p->AreaGlo, p->nCutsMerged ); - PRT( "T", clock() - clk ); - } - return fChange; -} - -/**Function************************************************************* - - Synopsis [Returns 1 if retiming with this clock period is feasible.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManBinarySearchPeriod( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i, c, fConverged; - int fResetRefs = 0; - - p->nAttempts++; - - // reset initial LValues (PIs to 0; others to -inf) - If_ManForEachObj( p, pObj, i ) - { - if ( If_ObjIsPi(pObj) || If_ObjIsConst1(pObj) ) - { - If_ObjSetLValue( pObj, (float)0.0 ); - If_ObjSetArrTime( pObj, (float)0.0 ); - } - else - { - If_ObjSetLValue( pObj, (float)-IF_INFINITY ); - If_ObjSetArrTime( pObj, (float)-IF_INFINITY ); - } - // undo any previous mapping, except for CIs - if ( If_ObjIsAnd(pObj) ) - If_ObjCutBest(pObj)->nLeaves = 0; - } - - // update all values iteratively - fConverged = 0; - for ( c = 1; c <= p->nMaxIters; c++ ) - { - if ( !If_ManPerformMappingRoundSeq( p, c ) ) - { - p->RequiredGlo = If_ManDelayMax( p, 1 ); - fConverged = 1; - break; - } - p->RequiredGlo = If_ManDelayMax( p, 1 ); -//printf( "Global = %d \n", (int)p->RequiredGlo ); - if ( p->RequiredGlo > p->Period + p->fEpsilon ) - break; - } - - // report the results - if ( p->pPars->fVerbose ) - { - p->AreaGlo = If_ManScanMapping(p); - printf( "Attempt = %2d. Iters = %3d. Area = %10.2f. Fi = %6.2f. ", p->nAttempts, c, p->AreaGlo, (float)p->Period ); - if ( fConverged ) - printf( " Feasible" ); - else if ( c > p->nMaxIters ) - printf( "Infeasible (timeout)" ); - else - printf( "Infeasible" ); - printf( "\n" ); - } - return fConverged; -} - - -/**Function************************************************************* - - Synopsis [Performs binary search for the optimal clock period.] - - Description [Assumes that FiMin is infeasible while FiMax is feasible.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManBinarySearch_rec( If_Man_t * p, int FiMin, int FiMax ) -{ - assert( FiMin < FiMax ); - if ( FiMin + 1 == FiMax ) - return FiMax; - // compute the median - p->Period = FiMin + (FiMax - FiMin)/2; - if ( If_ManBinarySearchPeriod( p ) ) - return If_ManBinarySearch_rec( p, FiMin, p->Period ); // Median is feasible - else - return If_ManBinarySearch_rec( p, p->Period, FiMax ); // Median is infeasible -} - -/**Function************************************************************* - - Synopsis [Performs sequential mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManPerformMappingSeqPost( If_Man_t * p ) -{ - If_Obj_t * pObjLi, * pObjLo, * pObj; - int i; - - // link the latch outputs (CIs) directly to the drivers of latch inputs (COs) - for ( i = 0; i < p->pPars->nLatches; i++ ) - { - pObjLi = If_ManLi( p, i ); - pObjLo = If_ManLo( p, i ); -// printf( "%3d : %2d -> %2d \n", i, -// (int)If_ObjLValue(If_ObjFanin0(pObjLo)), (int)If_ObjLValue(pObjLo) ); - } - - // set arrival times - assert( p->pPars->pTimesArr != NULL ); - If_ManForEachLatchOutput( p, pObjLo, i ) - p->pPars->pTimesArr[i] = If_ObjLValue(pObjLo); - - // set the required times - assert( p->pPars->pTimesReq == NULL ); - p->pPars->pTimesReq = ALLOC( float, If_ManCoNum(p) ); - If_ManForEachPo( p, pObj, i ) - { - p->pPars->pTimesReq[i] = p->RequiredGlo2; -// printf( "Out %3d : %2d \n", i, (int)p->pPars->pTimesReq[i] ); - } - If_ManForEachLatchInput( p, pObjLi, i ) - { - p->pPars->pTimesReq[i] = If_ObjLValue(If_ObjFanin0(pObjLi)); -// printf( "Out %3d : %2d \n", i, (int)p->pPars->pTimesReq[i] ); - } - - // undo previous mapping - If_ManForEachObj( p, pObj, i ) - if ( If_ObjIsAnd(pObj) ) - If_ObjCutBest(pObj)->nLeaves = 0; - - // map again combinationally - p->pPars->fSeqMap = 0; - If_ManPerformMappingComb( p ); - p->pPars->fSeqMap = 1; -} - -/**Function************************************************************* - - Synopsis [Performs sequential mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManPerformMappingSeq( If_Man_t * p ) -{ - int clkTotal = clock(); - int PeriodBest; - - p->SortMode = 0; - - // perform combinational mapping to get the upper bound on the clock period - If_ManPerformMappingRound( p, 1, 0, 0, NULL ); - p->RequiredGlo = If_ManDelayMax( p, 0 ); - p->RequiredGlo2 = p->RequiredGlo; - - // set direct linking of latches with their inputs - If_ManPrepareMappingSeq( p ); - - // collect latches - p->vLatchOrder = If_ManCollectLatches( p ); - - // set parameters - p->nCutsUsed = p->pPars->nCutsMax; - p->nAttempts = 0; - p->nMaxIters = 50; - p->Period = (int)p->RequiredGlo; - - // make sure the clock period works - if ( !If_ManBinarySearchPeriod( p ) ) - { - printf( "If_ManPerformMappingSeq(): The upper bound on the clock period cannot be computed.\n" ); - return 0; - } - - // perform binary search - PeriodBest = If_ManBinarySearch_rec( p, 0, p->Period ); - - // recompute the best l-values - if ( p->Period != PeriodBest ) - { - p->Period = PeriodBest; - if ( !If_ManBinarySearchPeriod( p ) ) - { - printf( "If_ManPerformMappingSeq(): The final clock period cannot be confirmed.\n" ); - return 0; - } - } - if ( p->pPars->fVerbose ) - { -/* - { - FILE * pTable; - pTable = fopen( "iscas/stats_new.txt", "a+" ); -// fprintf( pTable, "%s ", pNtk->pName ); - fprintf( pTable, "%d ", p->Period ); - // fprintf( pTable, "%.2f ", (float)(s_MappingMem)/(float)(1<<20) ); -// fprintf( pTable, "%.2f", (float)(s_MappingTime)/(float)(CLOCKS_PER_SEC) ); -// fprintf( pTable, "\n" ); - fclose( pTable ); - } -*/ - printf( "The best clock period is %3d. ", p->Period ); - PRT( "Sequential time", clock() - clkTotal ); - } - p->RequiredGlo = (float)PeriodBest; - - // postprocess it using combinational mapping - If_ManPerformMappingSeqPost( p ); - s_MappingTime = clock() - clkTotal; - return 1; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/map/if/ifTime.c b/src/map/if/ifTime.c deleted file mode 100644 index 60417c67..00000000 --- a/src/map/if/ifTime.c +++ /dev/null @@ -1,221 +0,0 @@ -/**CFile**************************************************************** - - FileName [ifTime.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [Computation of delay paramters depending on the library.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: ifTime.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "if.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -static void If_CutSortInputPins( If_Man_t * p, If_Cut_t * pCut, int * pPinPerm, float * pPinDelays ); - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Computes delay.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_CutDelay( If_Man_t * p, If_Cut_t * pCut ) -{ - static int pPinPerm[IF_MAX_LUTSIZE]; - static float pPinDelays[IF_MAX_LUTSIZE]; - If_Obj_t * pLeaf; - float Delay, DelayCur; - float * pLutDelays; - int i, Shift; - assert( p->pPars->fSeqMap || pCut->nLeaves > 1 ); - Delay = -IF_FLOAT_LARGE; - if ( p->pPars->pLutLib ) - { - assert( !p->pPars->fLiftLeaves ); - pLutDelays = p->pPars->pLutLib->pLutDelays[pCut->nLeaves]; - if ( p->pPars->pLutLib->fVarPinDelays ) - { - // compute the delay using sorted pins - If_CutSortInputPins( p, pCut, pPinPerm, pPinDelays ); - for ( i = 0; i < (int)pCut->nLeaves; i++ ) - { - DelayCur = pPinDelays[pPinPerm[i]] + pLutDelays[i]; - Delay = IF_MAX( Delay, DelayCur ); - } - } - else - { - If_CutForEachLeaf( p, pCut, pLeaf, i ) - { - DelayCur = If_ObjCutBest(pLeaf)->Delay + pLutDelays[0]; - Delay = IF_MAX( Delay, DelayCur ); - } - } - } - else - { - if ( pCut->fUser ) - { - assert( !p->pPars->fLiftLeaves ); - If_CutForEachLeaf( p, pCut, pLeaf, i ) - { - DelayCur = If_ObjCutBest(pLeaf)->Delay + (float)pCut->pPerm[i]; - Delay = IF_MAX( Delay, DelayCur ); - } - } - else - { - if ( p->pPars->fLiftLeaves ) - { - If_CutForEachLeafSeq( p, pCut, pLeaf, Shift, i ) - { - DelayCur = If_ObjCutBest(pLeaf)->Delay - Shift * p->Period; - Delay = IF_MAX( Delay, DelayCur ); - } - } - else - { - If_CutForEachLeaf( p, pCut, pLeaf, i ) - { - DelayCur = If_ObjCutBest(pLeaf)->Delay; - Delay = IF_MAX( Delay, DelayCur ); - } - } - Delay += 1.0; - } - } - return Delay; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_CutPropagateRequired( If_Man_t * p, If_Cut_t * pCut, float ObjRequired ) -{ - static int pPinPerm[IF_MAX_LUTSIZE]; - static float pPinDelays[IF_MAX_LUTSIZE]; - If_Obj_t * pLeaf; - float * pLutDelays; - float Required; - int i; - assert( !p->pPars->fLiftLeaves ); - // compute the pins - if ( p->pPars->pLutLib ) - { - pLutDelays = p->pPars->pLutLib->pLutDelays[pCut->nLeaves]; - if ( p->pPars->pLutLib->fVarPinDelays ) - { - // compute the delay using sorted pins - If_CutSortInputPins( p, pCut, pPinPerm, pPinDelays ); - for ( i = 0; i < (int)pCut->nLeaves; i++ ) - { - Required = ObjRequired - pLutDelays[i]; - pLeaf = If_ManObj( p, pCut->pLeaves[pPinPerm[i]] ); - pLeaf->Required = IF_MIN( pLeaf->Required, Required ); - } - } - else - { - Required = ObjRequired - pLutDelays[0]; - If_CutForEachLeaf( p, pCut, pLeaf, i ) - pLeaf->Required = IF_MIN( pLeaf->Required, Required ); - } - } - else - { - if ( pCut->fUser ) - { - If_CutForEachLeaf( p, pCut, pLeaf, i ) - { - Required = ObjRequired - (float)pCut->pPerm[i]; - pLeaf->Required = IF_MIN( pLeaf->Required, Required ); - } - } - else - { - Required = ObjRequired - (float)1.0; - If_CutForEachLeaf( p, pCut, pLeaf, i ) - pLeaf->Required = IF_MIN( pLeaf->Required, Required ); - } - } -} - -/**Function************************************************************* - - Synopsis [Sorts the pins in the decreasing order of delays.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_CutSortInputPins( If_Man_t * p, If_Cut_t * pCut, int * pPinPerm, float * pPinDelays ) -{ - If_Obj_t * pLeaf; - int i, j, best_i, temp; - // start the trivial permutation and collect pin delays - If_CutForEachLeaf( p, pCut, pLeaf, i ) - { - pPinPerm[i] = i; - pPinDelays[i] = If_ObjCutBest(pLeaf)->Delay; - } - // selection sort the pins in the decreasible order of delays - // this order will match the increasing order of LUT input pins - for ( i = 0; i < (int)pCut->nLeaves-1; i++ ) - { - best_i = i; - for ( j = i+1; j < (int)pCut->nLeaves; j++ ) - if ( pPinDelays[pPinPerm[j]] > pPinDelays[pPinPerm[best_i]] ) - best_i = j; - if ( best_i == i ) - continue; - temp = pPinPerm[i]; - pPinPerm[i] = pPinPerm[best_i]; - pPinPerm[best_i] = temp; - } - // verify - assert( pPinPerm[0] < (int)pCut->nLeaves ); - for ( i = 1; i < (int)pCut->nLeaves; i++ ) - { - assert( pPinPerm[i] < (int)pCut->nLeaves ); - assert( pPinDelays[pPinPerm[i-1]] >= pPinDelays[pPinPerm[i]] ); - } -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/map/if/ifTruth.c b/src/map/if/ifTruth.c deleted file mode 100644 index 5587e3ff..00000000 --- a/src/map/if/ifTruth.c +++ /dev/null @@ -1,230 +0,0 @@ -/**CFile**************************************************************** - - FileName [ifTruth.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [Computation of truth tables of the cuts.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: ifTruth.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "if.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Several simple procedures working with truth tables.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int If_TruthWordNum( int nVars ) { return nVars <= 5 ? 1 : (1 << (nVars - 5)); } -static inline void If_TruthNot( unsigned * pOut, unsigned * pIn, int nVars ) -{ - int w; - for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- ) - pOut[w] = ~pIn[w]; -} -static inline void If_TruthCopy( unsigned * pOut, unsigned * pIn, int nVars ) -{ - int w; - for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- ) - pOut[w] = pIn[w]; -} -static inline void If_TruthNand( unsigned * pOut, unsigned * pIn0, unsigned * pIn1, int nVars ) -{ - int w; - for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- ) - pOut[w] = ~(pIn0[w] & pIn1[w]); -} -static inline void If_TruthAnd( unsigned * pOut, unsigned * pIn0, unsigned * pIn1, int nVars ) -{ - int w; - for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- ) - pOut[w] = pIn0[w] & pIn1[w]; -} - -/**Function************************************************************* - - Synopsis [Swaps two adjacent variables in the truth table.] - - Description [Swaps var number Start and var number Start+1 (0-based numbers). - The input truth table is pIn. The output truth table is pOut.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_TruthSwapAdjacentVars( unsigned * pOut, unsigned * pIn, int nVars, int iVar ) -{ - static unsigned PMasks[4][3] = { - { 0x99999999, 0x22222222, 0x44444444 }, - { 0xC3C3C3C3, 0x0C0C0C0C, 0x30303030 }, - { 0xF00FF00F, 0x00F000F0, 0x0F000F00 }, - { 0xFF0000FF, 0x0000FF00, 0x00FF0000 } - }; - int nWords = If_TruthWordNum( nVars ); - int i, k, Step, Shift; - - assert( iVar < nVars - 1 ); - if ( iVar < 4 ) - { - Shift = (1 << iVar); - for ( i = 0; i < nWords; i++ ) - pOut[i] = (pIn[i] & PMasks[iVar][0]) | ((pIn[i] & PMasks[iVar][1]) << Shift) | ((pIn[i] & PMasks[iVar][2]) >> Shift); - } - else if ( iVar > 4 ) - { - Step = (1 << (iVar - 5)); - for ( k = 0; k < nWords; k += 4*Step ) - { - for ( i = 0; i < Step; i++ ) - pOut[i] = pIn[i]; - for ( i = 0; i < Step; i++ ) - pOut[Step+i] = pIn[2*Step+i]; - for ( i = 0; i < Step; i++ ) - pOut[2*Step+i] = pIn[Step+i]; - for ( i = 0; i < Step; i++ ) - pOut[3*Step+i] = pIn[3*Step+i]; - pIn += 4*Step; - pOut += 4*Step; - } - } - else // if ( iVar == 4 ) - { - for ( i = 0; i < nWords; i += 2 ) - { - pOut[i] = (pIn[i] & 0x0000FFFF) | ((pIn[i+1] & 0x0000FFFF) << 16); - pOut[i+1] = (pIn[i+1] & 0xFFFF0000) | ((pIn[i] & 0xFFFF0000) >> 16); - } - } -} - -/**Function************************************************************* - - Synopsis [Expands the truth table according to the phase.] - - Description [The input and output truth tables are in pIn/pOut. The current number - of variables is nVars. The total number of variables in nVarsAll. The last argument - (Phase) contains shows where the variables should go.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_TruthStretch( unsigned * pOut, unsigned * pIn, int nVars, int nVarsAll, unsigned Phase ) -{ - unsigned * pTemp; - int i, k, Var = nVars - 1, Counter = 0; - for ( i = nVarsAll - 1; i >= 0; i-- ) - if ( Phase & (1 << i) ) - { - for ( k = Var; k < i; k++ ) - { - If_TruthSwapAdjacentVars( pOut, pIn, nVarsAll, k ); - pTemp = pIn; pIn = pOut; pOut = pTemp; - Counter++; - } - Var--; - } - assert( Var == -1 ); - // swap if it was moved an even number of times - if ( !(Counter & 1) ) - If_TruthCopy( pOut, pIn, nVarsAll ); -} - -/**Function************************************************************* - - Synopsis [Computes the stretching phase of the cut w.r.t. the merged cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline unsigned If_CutTruthPhase( If_Cut_t * pCut, If_Cut_t * pCut1 ) -{ - unsigned uPhase = 0; - int i, k; - for ( i = k = 0; i < (int)pCut->nLeaves; i++ ) - { - if ( k == (int)pCut1->nLeaves ) - break; - if ( pCut->pLeaves[i] < pCut1->pLeaves[k] ) - continue; - assert( pCut->pLeaves[i] == pCut1->pLeaves[k] ); - uPhase |= (1 << i); - k++; - } - return uPhase; -} - -/**Function************************************************************* - - Synopsis [Performs truth table computation.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 ) -{ - extern void Kit_FactorTest( unsigned * pTruth, int nVars ); - - // permute the first table - if ( fCompl0 ^ pCut0->fCompl ) - If_TruthNot( p->puTemp[0], If_CutTruth(pCut0), pCut->nLimit ); - else - If_TruthCopy( p->puTemp[0], If_CutTruth(pCut0), pCut->nLimit ); - If_TruthStretch( p->puTemp[2], p->puTemp[0], pCut0->nLeaves, pCut->nLimit, If_CutTruthPhase(pCut, pCut0) ); - // permute the second table - if ( fCompl1 ^ pCut1->fCompl ) - If_TruthNot( p->puTemp[1], If_CutTruth(pCut1), pCut->nLimit ); - else - If_TruthCopy( p->puTemp[1], If_CutTruth(pCut1), pCut->nLimit ); - If_TruthStretch( p->puTemp[3], p->puTemp[1], pCut1->nLeaves, pCut->nLimit, If_CutTruthPhase(pCut, pCut1) ); - // produce the resulting table - assert( pCut->fCompl == 0 ); - if ( pCut->fCompl ) - If_TruthNand( If_CutTruth(pCut), p->puTemp[2], p->puTemp[3], pCut->nLimit ); - else - If_TruthAnd( If_CutTruth(pCut), p->puTemp[2], p->puTemp[3], pCut->nLimit ); - - // perform -// Kit_FactorTest( If_CutTruth(pCut), pCut->nLimit ); -// printf( "%d ", If_CutLeaveNum(pCut) - Kit_TruthSupportSize(If_CutTruth(pCut), If_CutLeaveNum(pCut)) ); -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/map/if/ifUtil.c b/src/map/if/ifUtil.c deleted file mode 100644 index f3fa049e..00000000 --- a/src/map/if/ifUtil.c +++ /dev/null @@ -1,454 +0,0 @@ -/**CFile**************************************************************** - - FileName [ifUtil.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [Various utilities.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: ifUtil.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "if.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Sets all the node copy to NULL.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManCleanNodeCopy( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i; - If_ManForEachObj( p, pObj, i ) - If_ObjSetCopy( pObj, NULL ); -} - -/**Function************************************************************* - - Synopsis [Sets all the cut data to NULL.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManCleanCutData( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i; - If_ManForEachObj( p, pObj, i ) - If_CutSetData( If_ObjCutBest(pObj), NULL ); -} - -/**Function************************************************************* - - Synopsis [Sets all visited marks to 0.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManCleanMarkV( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i; - If_ManForEachObj( p, pObj, i ) - pObj->fVisit = 0; -} - -/**Function************************************************************* - - Synopsis [Returns the max delay of the POs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManDelayMax( If_Man_t * p, int fSeq ) -{ - If_Obj_t * pObj; - float DelayBest; - int i; - if ( p->pPars->fLatchPaths && p->pPars->nLatches == 0 ) - { - printf( "Delay optimization of latch path is not performed because there is no latches.\n" ); - p->pPars->fLatchPaths = 0; - } - DelayBest = -IF_FLOAT_LARGE; - if ( fSeq ) - { - assert( p->pPars->nLatches > 0 ); - If_ManForEachPo( p, pObj, i ) - if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) ) - DelayBest = If_ObjArrTime(If_ObjFanin0(pObj)); - } - else if ( p->pPars->fLatchPaths ) - { - If_ManForEachLatchInput( p, pObj, i ) - if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) ) - DelayBest = If_ObjArrTime(If_ObjFanin0(pObj)); - } - else - { - If_ManForEachCo( p, pObj, i ) - if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) ) - DelayBest = If_ObjArrTime(If_ObjFanin0(pObj)); - } - return DelayBest; -} - -/**Function************************************************************* - - Synopsis [Computes the required times of all nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManComputeRequired( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i, Counter; - - // compute area, clean required times, collect nodes used in the mapping - p->nNets = 0; - p->AreaGlo = If_ManScanMapping( p ); - - // consider the case when the required times are given - if ( p->pPars->pTimesReq ) - { - assert( !p->pPars->fAreaOnly ); - // make sure that the required time hold - Counter = 0; - If_ManForEachCo( p, pObj, i ) - { - if ( If_ObjArrTime(If_ObjFanin0(pObj)) > p->pPars->pTimesReq[i] + p->fEpsilon ) - { - Counter++; -// printf( "Required times are violated for output %d (arr = %d; req = %d).\n", -// i, (int)If_ObjArrTime(If_ObjFanin0(pObj)), (int)p->pPars->pTimesReq[i] ); - } - If_ObjFanin0(pObj)->Required = p->pPars->pTimesReq[i]; - } - if ( Counter ) - printf( "Required times are violated for %d outputs.\n", Counter ); - } - else - { - // get the global required times - p->RequiredGlo = If_ManDelayMax( p, 0 ); - // update the required times according to the target - if ( p->pPars->DelayTarget != -1 ) - { - if ( p->RequiredGlo > p->pPars->DelayTarget + p->fEpsilon ) - { - if ( p->fNextRound == 0 ) - { - p->fNextRound = 1; - printf( "Cannot meet the target required times (%4.2f). Mapping continues anyway.\n", p->pPars->DelayTarget ); - } - } - else if ( p->RequiredGlo < p->pPars->DelayTarget - p->fEpsilon ) - { - if ( p->fNextRound == 0 ) - { - p->fNextRound = 1; - printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->RequiredGlo, p->pPars->DelayTarget ); - } - p->RequiredGlo = p->pPars->DelayTarget; - } - } - // do not propagate required times if area minimization is requested - if ( p->pPars->fAreaOnly ) - return; - // set the required times for the POs - if ( p->pPars->fLatchPaths ) - { - If_ManForEachLatchInput( p, pObj, i ) - If_ObjFanin0(pObj)->Required = p->RequiredGlo; - } - else - { - If_ManForEachCo( p, pObj, i ) - If_ObjFanin0(pObj)->Required = p->RequiredGlo; - } - } - // go through the nodes in the reverse topological order - Vec_PtrForEachEntry( p->vMapped, pObj, i ) - If_CutPropagateRequired( p, If_ObjCutBest(pObj), pObj->Required ); -} - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManScanMapping_rec( If_Man_t * p, If_Obj_t * pObj, If_Obj_t ** ppStore ) -{ - If_Obj_t * pLeaf; - If_Cut_t * pCutBest; - float aArea; - int i; - if ( pObj->nRefs++ || If_ObjIsCi(pObj) || If_ObjIsConst1(pObj) ) - return 0.0; - // store the node in the structure by level - assert( If_ObjIsAnd(pObj) ); - pObj->pCopy = (char *)ppStore[pObj->Level]; - ppStore[pObj->Level] = pObj; - // visit the transitive fanin of the selected cut - pCutBest = If_ObjCutBest(pObj); - p->nNets += pCutBest->nLeaves; - aArea = If_CutLutArea( p, pCutBest ); - If_CutForEachLeaf( p, pCutBest, pLeaf, i ) - aArea += If_ManScanMapping_rec( p, pLeaf, ppStore ); - return aArea; -} - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [Collects the nodes in reverse topological order in array - p->vMapping.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManScanMapping( If_Man_t * p ) -{ - If_Obj_t * pObj, ** ppStore; - float aArea; - int i; - assert( !p->pPars->fLiftLeaves ); - // clean all references - If_ManForEachObj( p, pObj, i ) - { - pObj->Required = IF_FLOAT_LARGE; - pObj->nVisits = pObj->nVisitsCopy; - pObj->nRefs = 0; - } - // allocate place to store the nodes - ppStore = ALLOC( If_Obj_t *, p->nLevelMax + 1 ); - memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) ); - // collect nodes reachable from POs in the DFS order through the best cuts - aArea = 0; - If_ManForEachCo( p, pObj, i ) - aArea += If_ManScanMapping_rec( p, If_ObjFanin0(pObj), ppStore ); - // reconnect the nodes in reverse topological order - Vec_PtrClear( p->vMapped ); - for ( i = p->nLevelMax; i >= 0; i-- ) - for ( pObj = ppStore[i]; pObj; pObj = pObj->pCopy ) - Vec_PtrPush( p->vMapped, pObj ); - free( ppStore ); - return aArea; -} - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManScanMappingSeq_rec( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vMapped ) -{ - If_Obj_t * pLeaf; - If_Cut_t * pCutBest; - float aArea; - int i, Shift; - // treat latches transparently - if ( If_ObjIsLatch(pObj) ) - return If_ManScanMappingSeq_rec( p, If_ObjFanin0(pObj), vMapped ); - // consider trivial cases - if ( pObj->nRefs++ || If_ObjIsPi(pObj) || If_ObjIsConst1(pObj) ) - return 0.0; - // store the node in the structure by level - assert( If_ObjIsAnd(pObj) ); - // visit the transitive fanin of the selected cut - pCutBest = If_ObjCutBest(pObj); - aArea = If_ObjIsAnd(pObj)? If_CutLutArea(p, pCutBest) : (float)0.0; - If_CutForEachLeafSeq( p, pCutBest, pLeaf, Shift, i ) - aArea += If_ManScanMappingSeq_rec( p, pLeaf, vMapped ); - // add the node - Vec_PtrPush( vMapped, pObj ); - return aArea; -} - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [Collects the nodes in reverse topological order in array - p->vMapping.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManScanMappingSeq( If_Man_t * p ) -{ - If_Obj_t * pObj; - float aArea; - int i; - assert( p->pPars->fLiftLeaves ); - // clean all references - If_ManForEachObj( p, pObj, i ) - pObj->nRefs = 0; - // collect nodes reachable from POs in the DFS order through the best cuts - aArea = 0; - Vec_PtrClear( p->vMapped ); - If_ManForEachPo( p, pObj, i ) - aArea += If_ManScanMappingSeq_rec( p, If_ObjFanin0(pObj), p->vMapped ); - return aArea; -} - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [Collects the nodes in reverse topological order in array - p->vMapping.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManResetOriginalRefs( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i; - If_ManForEachObj( p, pObj, i ) - pObj->nRefs = 0; - If_ManForEachObj( p, pObj, i ) - { - if ( If_ObjIsAnd(pObj) ) - { - pObj->pFanin0->nRefs++; - pObj->pFanin1->nRefs++; - } - else if ( If_ObjIsCo(pObj) ) - pObj->pFanin0->nRefs++; - } -} - -/**Function************************************************************* - - Synopsis [Computes cross-cut of the circuit.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManCrossCut( If_Man_t * p ) -{ - If_Obj_t * pObj, * pFanin; - int i, nCutSize = 0, nCutSizeMax = 0; - If_ManForEachObj( p, pObj, i ) - { - if ( !If_ObjIsAnd(pObj) ) - continue; - // consider the node - if ( nCutSizeMax < ++nCutSize ) - nCutSizeMax = nCutSize; - if ( pObj->nVisits == 0 ) - nCutSize--; - // consider the fanins - pFanin = If_ObjFanin0(pObj); - if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 ) - nCutSize--; - pFanin = If_ObjFanin1(pObj); - if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 ) - nCutSize--; - // consider the choice class - if ( pObj->fRepr ) - for ( pFanin = pObj; pFanin; pFanin = pFanin->pEquiv ) - if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 ) - nCutSize--; - } - If_ManForEachObj( p, pObj, i ) - { - assert( If_ObjIsCi(pObj) || pObj->fVisit == 0 ); - pObj->nVisits = pObj->nVisitsCopy; - } - assert( nCutSize == 0 ); -// printf( "Max cross cut size = %6d.\n", nCutSizeMax ); - return nCutSizeMax; -} - -/**Function************************************************************* - - Synopsis [Computes cross-cut of the circuit.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManCountTrueArea( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i, Area = 0; - Vec_PtrForEachEntry( p->vMapped, pObj, i ) - Area += 1 + (If_ObjCutBest(pObj)->nLeaves > (unsigned)p->pPars->nLutSize / 2); - return Area; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/map/if/if_.c b/src/map/if/if_.c deleted file mode 100644 index d2960077..00000000 --- a/src/map/if/if_.c +++ /dev/null @@ -1,47 +0,0 @@ -/**CFile**************************************************************** - - FileName [if_.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: if_.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "if.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/map/if/module.make b/src/map/if/module.make deleted file mode 100644 index f3d189be..00000000 --- a/src/map/if/module.make +++ /dev/null @@ -1,9 +0,0 @@ -SRC += src/map/if/ifCore.c \ - src/map/if/ifCut.c \ - src/map/if/ifMan.c \ - src/map/if/ifMap.c \ - src/map/if/ifReduce.c \ - src/map/if/ifSeq.c \ - src/map/if/ifTime.c \ - src/map/if/ifTruth.c \ - src/map/if/ifUtil.c |