diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 20:01:00 -0800 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 20:01:00 -0800 |
commit | 0c6505a26a537dc911b6566f82d759521e527c08 (patch) | |
tree | f2687995efd4943fe3b1307fce7ef5942d0a57b3 /src/map | |
parent | 4d30a1e4f1edecff86d5066ce4653a370e59e5e1 (diff) | |
download | abc-0c6505a26a537dc911b6566f82d759521e527c08.tar.gz abc-0c6505a26a537dc911b6566f82d759521e527c08.tar.bz2 abc-0c6505a26a537dc911b6566f82d759521e527c08.zip |
Version abc80130_2
Diffstat (limited to 'src/map')
64 files changed, 5528 insertions, 283 deletions
diff --git a/src/map/fpga/fpga.c b/src/map/fpga/fpga.c index 3d2ca913..40423f4f 100644 --- a/src/map/fpga/fpga.c +++ b/src/map/fpga/fpga.c @@ -39,7 +39,7 @@ static int Fpga_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) */ //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -56,8 +56,11 @@ static int Fpga_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) void Fpga_Init( Abc_Frame_t * pAbc ) { // set the default library - //Fpga_LutLib_t s_LutLib = { "lutlib", 6, {0,1,2,4,8,16,32}, {0,1,2,3,4,5,6} }; - Fpga_LutLib_t s_LutLib = { "lutlib", 5, {0,1,1,1,1,1}, {0,1,1,1,1,1} }; + //Fpga_LutLib_t s_LutLib = { "lutlib", 6, 0, {0,1,2,4,8,16,32}, {{0},{1},{2},{3},{4},{5},{6}} }; +// Fpga_LutLib_t s_LutLib = { "lutlib", 5, 0, {0,1,1,1,1,1}, {{0},{1},{1},{1},{1},{1}} }; + Fpga_LutLib_t s_LutLib = { "lutlib", 4, 0, {0,1,1,1,1}, {{0},{1},{1},{1},{1}} }; + //Fpga_LutLib_t s_LutLib = { "lutlib", 3, 0, {0,1,1,1}, {{0},{1},{1},{1}} }; + Abc_FrameSetLibLut( Fpga_LutLibDup(&s_LutLib) ); Cmd_CommandAdd( pAbc, "FPGA mapping", "read_lut", Fpga_CommandReadLibrary, 0 ); @@ -77,7 +80,7 @@ void Fpga_Init( Abc_Frame_t * pAbc ) ***********************************************************************/ void Fpga_End() { - Fpga_LutLibFree( Abc_FrameReadLibLut(Abc_FrameGetGlobalFrame()) ); + Fpga_LutLibFree( Abc_FrameReadLibLut() ); } @@ -102,14 +105,14 @@ int Fpga_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) int fVerbose; int c; - pNet = Abc_FrameReadNet(pAbc); + pNet = Abc_FrameReadNtk(pAbc); pOut = Abc_FrameReadOut(pAbc); pErr = Abc_FrameReadErr(pAbc); // set the defaults fVerbose = 1; - util_getopt_reset(); - while ( (c = util_getopt(argc, argv, "vh")) != EOF ) + Extra_UtilGetoptReset(); + while ( (c = Extra_UtilGetopt(argc, argv, "vh")) != EOF ) { switch (c) { @@ -125,13 +128,13 @@ int Fpga_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) } - if ( argc != util_optind + 1 ) + if ( argc != globalUtilOptind + 1 ) { goto usage; } // get the input file name - FileName = argv[util_optind]; + FileName = argv[globalUtilOptind]; if ( (pFile = fopen( FileName, "r" )) == NULL ) { fprintf( pErr, "Cannot open input file \"%s\". ", FileName ); @@ -192,14 +195,14 @@ int Fpga_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) int fVerbose; int c; - pNet = Abc_FrameReadNet(pAbc); + pNet = Abc_FrameReadNtk(pAbc); pOut = Abc_FrameReadOut(pAbc); pErr = Abc_FrameReadErr(pAbc); // set the defaults fVerbose = 1; - util_getopt_reset(); - while ( (c = util_getopt(argc, argv, "vh")) != EOF ) + Extra_UtilGetoptReset(); + while ( (c = Extra_UtilGetopt(argc, argv, "vh")) != EOF ) { switch (c) { @@ -215,13 +218,13 @@ int Fpga_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) } - if ( argc != util_optind ) + if ( argc != globalUtilOptind ) { goto usage; } // set the new network - Fpga_LutLibPrint( Abc_FrameReadLibLut(Abc_FrameGetGlobalFrame()) ); + Fpga_LutLibPrint( Abc_FrameReadLibLut() ); return 0; usage: @@ -232,6 +235,47 @@ usage: return 1; /* error exit */ } +/**Function************************************************************* + + Synopsis [Sets simple LUT library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_SetSimpleLutLib( int nLutSize ) +{ + Fpga_LutLib_t s_LutLib10= { "lutlib",10, 0, {0,1,1,1,1,1,1,1,1,1,1}, {{0},{1},{1},{1},{1},{1},{1},{1},{1},{1},{1}} }; + Fpga_LutLib_t s_LutLib9 = { "lutlib", 9, 0, {0,1,1,1,1,1,1,1,1,1}, {{0},{1},{1},{1},{1},{1},{1},{1},{1},{1}} }; + Fpga_LutLib_t s_LutLib8 = { "lutlib", 8, 0, {0,1,1,1,1,1,1,1,1}, {{0},{1},{1},{1},{1},{1},{1},{1},{1}} }; + Fpga_LutLib_t s_LutLib7 = { "lutlib", 7, 0, {0,1,1,1,1,1,1,1}, {{0},{1},{1},{1},{1},{1},{1},{1}} }; + Fpga_LutLib_t s_LutLib6 = { "lutlib", 6, 0, {0,1,1,1,1,1,1}, {{0},{1},{1},{1},{1},{1},{1}} }; + Fpga_LutLib_t s_LutLib5 = { "lutlib", 5, 0, {0,1,1,1,1,1}, {{0},{1},{1},{1},{1},{1}} }; + Fpga_LutLib_t s_LutLib4 = { "lutlib", 4, 0, {0,1,1,1,1}, {{0},{1},{1},{1},{1}} }; + Fpga_LutLib_t s_LutLib3 = { "lutlib", 3, 0, {0,1,1,1}, {{0},{1},{1},{1}} }; + Fpga_LutLib_t * pLutLib; + assert( nLutSize >= 3 && nLutSize <= 10 ); + switch ( nLutSize ) + { + case 3: pLutLib = &s_LutLib3; break; + case 4: pLutLib = &s_LutLib4; break; + case 5: pLutLib = &s_LutLib5; break; + case 6: pLutLib = &s_LutLib6; break; + case 7: pLutLib = &s_LutLib7; break; + case 8: pLutLib = &s_LutLib8; break; + case 9: pLutLib = &s_LutLib9; break; + case 10: pLutLib = &s_LutLib10; break; + default: pLutLib = NULL; break; + } + if ( pLutLib == NULL ) + return; + Fpga_LutLibFree( Abc_FrameReadLibLut() ); + Abc_FrameSetLibLut( Fpga_LutLibDup(pLutLib) ); +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/map/fpga/fpga.h b/src/map/fpga/fpga.h index 19241a74..708cf385 100644 --- a/src/map/fpga/fpga.h +++ b/src/map/fpga/fpga.h @@ -19,6 +19,10 @@ #ifndef __FPGA_H__ #define __FPGA_H__ +#ifdef __cplusplus +extern "C" { +#endif + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// @@ -28,7 +32,7 @@ //////////////////////////////////////////////////////////////////////// // the maximum size of LUTs used for mapping -#define FPGA_MAX_LUTSIZE 10 +#define FPGA_MAX_LUTSIZE 32 //////////////////////////////////////////////////////////////////////// /// STRUCTURE DEFINITIONS /// @@ -45,20 +49,20 @@ typedef struct Fpga_LutLibStruct_t_ Fpga_LutLib_t; //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// -#define Fpga_IsComplement(p) (((int)((long) (p) & 01))) -#define Fpga_Regular(p) ((Fpga_Node_t *)((unsigned)(p) & ~01)) -#define Fpga_Not(p) ((Fpga_Node_t *)((long)(p) ^ 01)) -#define Fpga_NotCond(p,c) ((Fpga_Node_t *)((long)(p) ^ (c))) +#define Fpga_IsComplement(p) (((int)((unsigned long) (p) & 01))) +#define Fpga_Regular(p) ((Fpga_Node_t *)((unsigned long)(p) & ~01)) +#define Fpga_Not(p) ((Fpga_Node_t *)((unsigned long)(p) ^ 01)) +#define Fpga_NotCond(p,c) ((Fpga_Node_t *)((unsigned long)(p) ^ (c))) #define Fpga_Ref(p) #define Fpga_Deref(p) #define Fpga_RecursiveDeref(p,c) //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /*=== fpgaCreate.c =============================================================*/ @@ -74,7 +78,9 @@ extern Fpga_Node_t ** Fpga_ManReadOutputs( Fpga_Man_t * p ); extern Fpga_Node_t * Fpga_ManReadConst1 ( Fpga_Man_t * p ); extern float * Fpga_ManReadInputArrivals( Fpga_Man_t * p ); extern int Fpga_ManReadVerbose( Fpga_Man_t * p ); +extern int Fpga_ManReadVarMax( Fpga_Man_t * p ); extern float * Fpga_ManReadLutAreas( Fpga_Man_t * p ); +extern Fpga_NodeVec_t* Fpga_ManReadMapping( Fpga_Man_t * p ); extern void Fpga_ManSetTimeToMap( Fpga_Man_t * p, int Time ); extern void Fpga_ManSetTimeToNet( Fpga_Man_t * p, int Time ); extern void Fpga_ManSetTimeTotal( Fpga_Man_t * p, int Time ); @@ -92,13 +98,16 @@ extern void Fpga_ManSetChoiceNodeNum( Fpga_Man_t * p, int nChoiceNode extern void Fpga_ManSetChoiceNum( Fpga_Man_t * p, int nChoices ); extern void Fpga_ManSetVerbose( Fpga_Man_t * p, int fVerbose ); extern void Fpga_ManSetSwitching( Fpga_Man_t * p, int fSwitching ); +extern void Fpga_ManSetLatchPaths( Fpga_Man_t * p, int fLatchPaths ); extern void Fpga_ManSetLatchNum( Fpga_Man_t * p, int nLatches ); +extern void Fpga_ManSetDelayTarget( Fpga_Man_t * p, float DelayTarget ); extern void Fpga_ManSetName( Fpga_Man_t * p, char * pFileName ); extern int Fpga_LibReadLutMax( Fpga_LutLib_t * pLib ); extern char * Fpga_NodeReadData0( Fpga_Node_t * p ); extern Fpga_Node_t * Fpga_NodeReadData1( Fpga_Node_t * p ); +extern int Fpga_NodeReadRefs( Fpga_Node_t * p ); extern int Fpga_NodeReadNum( Fpga_Node_t * p ); extern int Fpga_NodeReadLevel( Fpga_Node_t * p ); extern Fpga_Cut_t * Fpga_NodeReadCuts( Fpga_Node_t * p ); @@ -134,23 +143,33 @@ extern int Fpga_Mapping( Fpga_Man_t * p ); /*=== fpgaCut.c ===============================================================*/ extern void Fpga_MappingCreatePiCuts( Fpga_Man_t * p ); extern void Fpga_CutsCleanSign( Fpga_Man_t * pMan ); +extern void Fpga_CutsCleanRoot( Fpga_Man_t * pMan ); /*=== fpgaCutUtils.c =============================================================*/ extern void Fpga_CutCreateFromNode( Fpga_Man_t * p, int iRoot, int * pLeaves, int nLeaves ); extern void Fpga_MappingSetUsedCuts( Fpga_Man_t * p ); -/*=== fpgaFraig.c =============================================================*/ -extern Fpga_Man_t * Fpga_ManDupFraig( Fraig_Man_t * pManFraig ); -extern Fpga_Man_t * Fpga_ManBalanceFraig( Fraig_Man_t * pManFraig, int * pInputArrivals ); /*=== fpgaLib.c =============================================================*/ extern Fpga_LutLib_t * Fpga_LutLibDup( Fpga_LutLib_t * p ); +extern int Fpga_LutLibReadVarMax( Fpga_LutLib_t * p ); +extern float * Fpga_LutLibReadLutAreas( Fpga_LutLib_t * p ); +extern float * Fpga_LutLibReadLutDelays( Fpga_LutLib_t * p ); +extern float Fpga_LutLibReadLutArea( Fpga_LutLib_t * p, int Size ); +extern float Fpga_LutLibReadLutDelay( Fpga_LutLib_t * p, int Size ); /*=== fpgaTruth.c =============================================================*/ extern void * Fpga_TruthsCutBdd( void * dd, Fpga_Cut_t * pCut ); +extern int Fpga_CutVolume( Fpga_Cut_t * pCut ); /*=== fpgaUtil.c =============================================================*/ extern int Fpga_ManCheckConsistency( Fpga_Man_t * p ); extern void Fpga_ManCleanData0( Fpga_Man_t * pMan ); extern Fpga_NodeVec_t * Fpga_CollectNodeTfo( Fpga_Man_t * pMan, Fpga_Node_t * pNode ); +/*=== fpga.c =============================================================*/ +extern void Fpga_SetSimpleLutLib( int nLutSize ); + +#ifdef __cplusplus +} +#endif +#endif //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -#endif diff --git a/src/map/fpga/fpgaCore.c b/src/map/fpga/fpgaCore.c index 9ca65379..634a8eb1 100644 --- a/src/map/fpga/fpgaCore.c +++ b/src/map/fpga/fpgaCore.c @@ -24,8 +24,12 @@ static int Fpga_MappingPostProcess( Fpga_Man_t * p ); +extern int s_MappingTime; +extern int s_MappingMem; + + //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -46,7 +50,7 @@ static int Fpga_MappingPostProcess( Fpga_Man_t * p ); int Fpga_Mapping( Fpga_Man_t * p ) { int clk, clkTotal = clock(); - + // collect the nodes reachable from POs in the DFS order (including the choices) p->vAnds = Fpga_MappingDfs( p, 1 ); Fpga_ManReportChoices( p ); // recomputes levels @@ -64,19 +68,23 @@ int Fpga_Mapping( Fpga_Man_t * p ) p->timeMatch = clock() - clk; // perform area recovery - if ( p->fAreaRecovery ) - { - clk = clock(); - if ( !Fpga_MappingPostProcess( p ) ) - return 0; - p->timeRecover = clock() - clk; - } + clk = clock(); + if ( !Fpga_MappingPostProcess( p ) ) + return 0; + p->timeRecover = clock() - clk; //PRT( "Total mapping time", clock() - clkTotal ); + s_MappingTime = clock() - clkTotal; + s_MappingMem = Fpga_CutCountAll(p) * (sizeof(Fpga_Cut_t) - sizeof(int) * (FPGA_MAX_LEAVES - p->nVarsMax)); + // print the AI-graph used for mapping //Fpga_ManShow( p, "test" ); +// if ( p->fVerbose ) +// Fpga_MappingPrintOutputArrivals( p ); if ( p->fVerbose ) - Fpga_MappingPrintOutputArrivals( p ); + { + PRT( "Total time", clock() - clkTotal ); + } return 1; } @@ -88,7 +96,7 @@ int Fpga_Mapping( Fpga_Man_t * p ) It iterates the loop, in which the required times are computed and the mapping is updated. It is conceptually similar to the paper: V. Manohararajah, S. D. Brown, Z. G. Vranesic, Heuristics for area - minimization in LUT-based FGPA technology mapping. Proc. IWLS '04.] + minimization in LUT-based FPGA technology mapping. Proc. IWLS '04.] SideEffects [] @@ -97,12 +105,15 @@ int Fpga_Mapping( Fpga_Man_t * p ) ***********************************************************************/ int Fpga_MappingPostProcess( Fpga_Man_t * p ) { - int fShowSwitching = 1; + int fShowSwitching = 0; int fRecoverAreaFlow = 1; int fRecoverArea = 1; float aAreaTotalCur, aAreaTotalCur2; int Iter, clk; +//if ( p->fVerbose ) +// printf( "Best clock period = %5.2f\n", Fpga_TimeComputeArrivalMax(p) ); + // compute area, set references, and collect nodes used in the mapping Iter = 1; aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); @@ -111,14 +122,20 @@ if ( p->fVerbose ) printf( "Iteration %dD : Area = %8.1f ", Iter++, aAreaTotalCur ); if ( fShowSwitching ) printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) ); +else +printf( "Delay = %5.2f ", Fpga_TimeComputeArrivalMax(p) ); + PRT( "Time", p->timeMatch ); } + if ( !p->fAreaRecovery ) + return 1; + if ( fRecoverAreaFlow ) { clk = clock(); // compute the required times and the fanouts - Fpga_TimeComputeRequiredGlobal( p ); + Fpga_TimeComputeRequiredGlobal( p, 1 ); // remap topologically Fpga_MappingMatches( p, 0 ); // get the resulting area @@ -131,6 +148,8 @@ if ( p->fVerbose ) printf( "Iteration %dF : Area = %8.1f ", Iter++, aAreaTotalCur ); if ( fShowSwitching ) printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) ); +else +printf( "Delay = %5.2f ", Fpga_TimeComputeArrivalMax(p) ); PRT( "Time", clock() - clk ); } } @@ -143,7 +162,7 @@ PRT( "Time", clock() - clk ); { clk = clock(); // compute the required times and the fanouts - Fpga_TimeComputeRequiredGlobal( p ); + Fpga_TimeComputeRequiredGlobal( p, 0 ); // remap topologically if ( p->fSwitching ) Fpga_MappingMatchesSwitch( p ); @@ -156,6 +175,8 @@ if ( p->fVerbose ) printf( "Iteration %d%s : Area = %8.1f ", Iter++, (p->fSwitching?"S":"A"), aAreaTotalCur ); if ( fShowSwitching ) printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) ); +else +printf( "Delay = %5.2f ", Fpga_TimeComputeArrivalMax(p) ); PRT( "Time", clock() - clk ); } } diff --git a/src/map/fpga/fpgaCreate.c b/src/map/fpga/fpgaCreate.c index b7bfa3c5..be71d74e 100644 --- a/src/map/fpga/fpgaCreate.c +++ b/src/map/fpga/fpgaCreate.c @@ -31,7 +31,7 @@ static Fpga_Node_t * Fpga_TableLookup( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_ static inline unsigned Fpga_HashKey2( Fpga_Node_t * p0, Fpga_Node_t * p1, int TableSize ) { return ((unsigned)(p0) + (unsigned)(p1) * 12582917) % TableSize; } //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -52,7 +52,9 @@ Fpga_Node_t ** Fpga_ManReadOutputs( Fpga_Man_t * p ) { retu Fpga_Node_t * Fpga_ManReadConst1 ( Fpga_Man_t * p ) { return p->pConst1; } float * Fpga_ManReadInputArrivals( Fpga_Man_t * p ) { return p->pInputArrivals;} int Fpga_ManReadVerbose( Fpga_Man_t * p ) { return p->fVerbose; } +int Fpga_ManReadVarMax( Fpga_Man_t * p ) { return p->pLutLib->LutMax; } float * Fpga_ManReadLutAreas( Fpga_Man_t * p ) { return p->pLutLib->pLutAreas; } +Fpga_NodeVec_t* Fpga_ManReadMapping( Fpga_Man_t * p ) { return p->vMapping; } void Fpga_ManSetTimeToMap( Fpga_Man_t * p, int Time ) { p->timeToMap = Time; } void Fpga_ManSetTimeToNet( Fpga_Man_t * p, int Time ) { p->timeToNet = Time; } void Fpga_ManSetTimeTotal( Fpga_Man_t * p, int Time ) { p->timeTotal = Time; } @@ -66,7 +68,9 @@ void Fpga_ManSetChoiceNodeNum( Fpga_Man_t * p, int nChoiceNodes ) { p void Fpga_ManSetChoiceNum( Fpga_Man_t * p, int nChoices ) { p->nChoices = nChoices; } void Fpga_ManSetVerbose( Fpga_Man_t * p, int fVerbose ) { p->fVerbose = fVerbose; } void Fpga_ManSetSwitching( Fpga_Man_t * p, int fSwitching ) { p->fSwitching = fSwitching; } +void Fpga_ManSetLatchPaths( Fpga_Man_t * p, int fLatchPaths ) { p->fLatchPaths = fLatchPaths; } void Fpga_ManSetLatchNum( Fpga_Man_t * p, int nLatches ) { p->nLatches = nLatches; } +void Fpga_ManSetDelayTarget( Fpga_Man_t * p, float DelayTarget ) { p->DelayTarget = DelayTarget; } void Fpga_ManSetName( Fpga_Man_t * p, char * pFileName ) { p->pFileName = pFileName; } /**Function************************************************************* @@ -95,6 +99,7 @@ int Fpga_LibReadLutMax( Fpga_LutLib_t * pLib ) { return pLib->LutMa ***********************************************************************/ char * Fpga_NodeReadData0( Fpga_Node_t * p ) { return p->pData0; } Fpga_Node_t * Fpga_NodeReadData1( Fpga_Node_t * p ) { return p->pLevel; } +int Fpga_NodeReadRefs( Fpga_Node_t * p ) { return p->nRefs; } int Fpga_NodeReadNum( Fpga_Node_t * p ) { return p->Num; } int Fpga_NodeReadLevel( Fpga_Node_t * p ) { return Fpga_Regular(p)->Level; } Fpga_Cut_t * Fpga_NodeReadCuts( Fpga_Node_t * p ) { return p->pCuts; } @@ -164,7 +169,7 @@ Fpga_Man_t * Fpga_ManCreate( int nInputs, int nOutputs, int fVerbose ) // start the manager p = ALLOC( Fpga_Man_t, 1 ); memset( p, 0, sizeof(Fpga_Man_t) ); - p->pLutLib = Abc_FrameReadLibLut(Abc_FrameGetGlobalFrame()); + p->pLutLib = Abc_FrameReadLibLut(); p->nVarsMax = p->pLutLib->LutMax; p->fVerbose = fVerbose; p->fAreaRecovery = 1; @@ -223,8 +228,8 @@ void Fpga_ManFree( Fpga_Man_t * p ) Fpga_NodeVecFree( p->vAnds ); if ( p->vNodesAll ) Fpga_NodeVecFree( p->vNodesAll ); - Extra_MmFixedStop( p->mmNodes, 0 ); - Extra_MmFixedStop( p->mmCuts, 0 ); + Extra_MmFixedStop( p->mmNodes ); + Extra_MmFixedStop( p->mmCuts ); FREE( p->ppOutputNames ); FREE( p->pInputArrivals ); FREE( p->pInputs ); diff --git a/src/map/fpga/fpgaCut.c b/src/map/fpga/fpgaCut.c index 5b5fbe69..ce688179 100644 --- a/src/map/fpga/fpgaCut.c +++ b/src/map/fpga/fpgaCut.c @@ -35,9 +35,11 @@ struct Fpga_CutTableStrutct_t }; // the largest number of cuts considered -#define FPGA_CUTS_MAX_COMPUTE 500 +//#define FPGA_CUTS_MAX_COMPUTE 500 +#define FPGA_CUTS_MAX_COMPUTE 2000 // the largest number of cuts used -#define FPGA_CUTS_MAX_USE 200 +//#define FPGA_CUTS_MAX_USE 200 +#define FPGA_CUTS_MAX_USE 1000 // primes used to compute the hash key static int s_HashPrimes[10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 }; @@ -95,7 +97,7 @@ static Fpga_Cut_t * Fpga_CutArray2List( Fpga_Cut_t ** pArray, int nCuts ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -128,9 +130,10 @@ void Fpga_MappingCuts( Fpga_Man_t * p ) Fpga_CutTable_t * pTable; Fpga_Node_t * pNode; int nCuts, nNodes, i; + int clk = clock(); // set the elementary cuts for the PI variables - assert( p->nVarsMax > 1 && p->nVarsMax < 7 ); + assert( p->nVarsMax > 1 && p->nVarsMax < 11 ); Fpga_MappingCreatePiCuts( p ); // compute the cuts for the internal nodes @@ -152,8 +155,9 @@ void Fpga_MappingCuts( Fpga_Man_t * p ) if ( p->fVerbose ) { nCuts = Fpga_CutCountAll(p); - printf( "Nodes = %6d. Total %d-feasible cuts = %d. Cuts per node = %.1f.\n", + printf( "Nodes = %6d. Total %d-cuts = %d. Cuts per node = %.1f. ", p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes ); + PRT( "Time", clock() - clk ); } // print the cuts for the first primary output @@ -245,7 +249,7 @@ Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Nod // set at the node pNode->pCuts = pCut; // remove the dominated cuts - Fpga_CutFilter( p, pNode ); +// Fpga_CutFilter( p, pNode ); // set the phase correctly if ( pNode->pRepr && Fpga_NodeComparePhase(pNode, pNode->pRepr) ) { @@ -347,8 +351,8 @@ void Fpga_CutFilter( Fpga_Man_t * p, Fpga_Node_t * pNode ) Fpga_Cut_t * Fpga_CutMergeLists( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 ) { - Fpga_Node_t * ppNodes[6]; - Fpga_Cut_t * pListNew, ** ppListNew, * pLists[7] = { NULL }; + Fpga_Node_t * ppNodes[FPGA_MAX_LEAVES]; + Fpga_Cut_t * pListNew, ** ppListNew, * pLists[FPGA_MAX_LEAVES+1] = { NULL }; Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2; int nNodes, Counter, i; Fpga_Cut_t ** ppArray1, ** ppArray2, ** ppArray3; @@ -532,8 +536,8 @@ QUITS : Fpga_Cut_t * Fpga_CutMergeLists2( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 ) { - Fpga_Node_t * ppNodes[6]; - Fpga_Cut_t * pListNew, ** ppListNew, * pLists[7] = { NULL }; + Fpga_Node_t * ppNodes[FPGA_MAX_LEAVES]; + Fpga_Cut_t * pListNew, ** ppListNew, * pLists[FPGA_MAX_LEAVES+1] = { NULL }; Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2; int nNodes, Counter, i; @@ -682,7 +686,8 @@ int Fpga_CutMergeTwo( Fpga_Cut_t * pCut1, Fpga_Cut_t * pCut2, Fpga_Node_t * ppNo { min = i; for ( k = i+1; k < nTotal; k++ ) - if ( ppNodes[k] < ppNodes[min] ) +// if ( ppNodes[k] < ppNodes[min] ) // reported bug fix (non-determinism!) + if ( ppNodes[k]->Num < ppNodes[min]->Num ) min = k; pNodeTemp = ppNodes[i]; ppNodes[i] = ppNodes[min]; @@ -767,7 +772,10 @@ int Fpga_CutCountAll( Fpga_Man_t * pMan ) for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext ) for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext ) if ( pCut->nLeaves > 1 ) // skip the elementary cuts + { +// Fpga_CutVolume( pCut ); nCuts++; + } return nCuts; } @@ -794,6 +802,28 @@ void Fpga_CutsCleanSign( Fpga_Man_t * pMan ) pCut->uSign = 0; } +/**Function************************************************************* + + Synopsis [Clean the signatures.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutsCleanRoot( Fpga_Man_t * pMan ) +{ + Fpga_Node_t * pNode; + Fpga_Cut_t * pCut; + int i; + for ( i = 0; i < pMan->nBins; i++ ) + for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext ) + for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext ) + pCut->pRoot = NULL; +} + /**Function************************************************************* @@ -1079,7 +1109,7 @@ Fpga_Cut_t * Fpga_CutSortCuts( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Cut_ nCuts = Fpga_CutList2Array( p->pCuts1, pList ); assert( nCuts <= FPGA_CUTS_MAX_COMPUTE ); // sort the cuts - qsort( (void *)p->pCuts1, nCuts, sizeof(Fpga_Cut_t *), + qsort( (void *)p->pCuts1, nCuts, sizeof(void *), (int (*)(const void *, const void *)) Fpga_CutSortCutsCompare ); // move them back into the list if ( nCuts > FPGA_CUTS_MAX_USE - 1 ) diff --git a/src/map/fpga/fpgaCutUtils.c b/src/map/fpga/fpgaCutUtils.c index 2419cac4..e60a1dee 100644 --- a/src/map/fpga/fpgaCutUtils.c +++ b/src/map/fpga/fpgaCutUtils.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -290,7 +290,9 @@ void Fpga_CutGetParameters( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) // pCut->aFlow += pFaninCut->aFlow / pCut->ppLeaves[i]->nRefs; pCut->aFlow += pFaninCut->aFlow / pCut->ppLeaves[i]->aEstFanouts; } - pCut->tArrival += pMan->pLutLib->pLutDelays[pCut->nLeaves]; + // use the first pin to compute the delay of the LUT + // (this mapper does not support the variable pin delay model) + pCut->tArrival += pMan->pLutLib->pLutDelays[pCut->nLeaves][0]; } @@ -338,7 +340,7 @@ float Fpga_CutGetAreaRefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) return 0; aResult = Fpga_CutDeref( pMan, NULL, pCut, 0 ); aResult2 = Fpga_CutRef( pMan, NULL, pCut, 0 ); - assert( aResult == aResult2 ); + assert( Fpga_FloatEqual( pMan, aResult, aResult2 ) ); return aResult; } @@ -360,7 +362,7 @@ float Fpga_CutGetAreaDerefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) return 0; aResult2 = Fpga_CutRef( pMan, NULL, pCut, 0 ); aResult = Fpga_CutDeref( pMan, NULL, pCut, 0 ); - assert( aResult == aResult2 ); + assert( Fpga_FloatEqual( pMan, aResult, aResult2 ) ); return aResult; } diff --git a/src/map/fpga/fpgaFanout.c b/src/map/fpga/fpgaFanout.c index 0a34ff43..c28a8799 100644 --- a/src/map/fpga/fpgaFanout.c +++ b/src/map/fpga/fpgaFanout.c @@ -25,7 +25,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* diff --git a/src/map/fpga/fpgaGENERIC.c b/src/map/fpga/fpgaGENERIC.c index f272c1b8..4483c215 100644 --- a/src/map/fpga/fpgaGENERIC.c +++ b/src/map/fpga/fpgaGENERIC.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* diff --git a/src/map/fpga/fpgaInt.h b/src/map/fpga/fpgaInt.h index ec6057a7..c01d1e3d 100644 --- a/src/map/fpga/fpgaInt.h +++ b/src/map/fpga/fpgaInt.h @@ -28,7 +28,6 @@ #include <stdlib.h> #include <string.h> #include "extra.h" -#include "fraig.h" #include "fpga.h" //////////////////////////////////////////////////////////////////////// @@ -39,7 +38,7 @@ //#define FPGA_ALLOCATE_FANOUT 1 //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// #ifdef _WIN32 @@ -68,16 +67,16 @@ #define FPGA_SEQ_SIGN(p) (1 << (((unsigned)p)%31)); // internal macros to work with cuts -#define Fpga_CutIsComplement(p) (((int)((long) (p) & 01))) -#define Fpga_CutRegular(p) ((Fpga_Cut_t *)((unsigned)(p) & ~01)) -#define Fpga_CutNot(p) ((Fpga_Cut_t *)((long)(p) ^ 01)) -#define Fpga_CutNotCond(p,c) ((Fpga_Cut_t *)((long)(p) ^ (c))) +#define Fpga_CutIsComplement(p) (((int)((unsigned long) (p) & 01))) +#define Fpga_CutRegular(p) ((Fpga_Cut_t *)((unsigned long)(p) & ~01)) +#define Fpga_CutNot(p) ((Fpga_Cut_t *)((unsigned long)(p) ^ 01)) +#define Fpga_CutNotCond(p,c) ((Fpga_Cut_t *)((unsigned long)(p) ^ (c))) // the cut nodes -#define Fpga_SeqIsComplement( p ) (((int)((long) (p) & 01))) -#define Fpga_SeqRegular( p ) ((Fpga_Node_t *)((unsigned)(p) & ~015)) -#define Fpga_SeqIndex( p ) ((((unsigned)(p)) >> 1) & 07) -#define Fpga_SeqIndexCreate( p, Ind ) (((unsigned)(p)) | (1 << (((unsigned)(Ind)) & 07))) +#define Fpga_SeqIsComplement( p ) (((int)((unsigned long) (p) & 01))) +#define Fpga_SeqRegular( p ) ((Fpga_Node_t *)((unsigned long)(p) & ~015)) +#define Fpga_SeqIndex( p ) ((((unsigned long)(p)) >> 1) & 07) +#define Fpga_SeqIndexCreate( p, Ind ) (((unsigned long)(p)) | (1 << (((unsigned)(Ind)) & 07))) // internal macros for referencing of nodes #define Fpga_NodeReadRef(p) ((Fpga_Regular(p))->nRefs) @@ -123,7 +122,9 @@ struct Fpga_ManStruct_t_ int fAreaRecovery; // the flag to use area flow as the first parameter int fVerbose; // the verbosiness flag int fSwitching; // minimize the switching activity (instead of area) - int nTravIds; + int fLatchPaths; // optimize latch paths for delay, other paths for area + int nTravIds; // the counter of traversal IDs + float DelayTarget; // the target required times // support of choice nodes int nChoiceNodes; // the number of choice nodes @@ -170,8 +171,9 @@ struct Fpga_LutLibStruct_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[FPGA_MAX_LUTSIZE+1]; // the areas of LUTs - float pLutDelays[FPGA_MAX_LUTSIZE+1];// the delays of LUTs + float pLutDelays[FPGA_MAX_LUTSIZE+1][FPGA_MAX_LUTSIZE+1];// the delays of LUTs }; // the mapping node @@ -182,8 +184,8 @@ struct Fpga_NodeStruct_t_ Fpga_Node_t * pLevel; // the next node in the linked list by level int Num; // the unique number of this node int NumA; // the unique number of this node - short Num2; // the temporary number of this node - short nRefs; // the number of references (fanouts) of the given node + int Num2; // the temporary number of this node + int nRefs; // the number of references (fanouts) of the given node unsigned fMark0 : 1; // the mark used for traversals unsigned fMark1 : 1; // the mark used for traversals unsigned fInv : 1; // the complemented attribute for the equivalent nodes @@ -276,12 +278,16 @@ struct Fpga_NodeVecStruct_t_ pFanout = pFanout2, \ pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout) ) +static inline Fpga_FloatMoreThan( Fpga_Man_t * p, float Arg1, float Arg2 ) { return Arg1 > Arg2 + p->fEpsilon; } +static inline Fpga_FloatLessThan( Fpga_Man_t * p, float Arg1, float Arg2 ) { return Arg1 < Arg2 - p->fEpsilon; } +static inline Fpga_FloatEqual( Fpga_Man_t * p, float Arg1, float Arg2 ) { return Arg1 > Arg2 - p->fEpsilon && Arg1 < Arg2 + p->fEpsilon; } + //////////////////////////////////////////////////////////////////////// /// GLOBAL VARIABLES /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /*=== fpgaCut.c ===============================================================*/ @@ -331,7 +337,7 @@ extern float Fpga_MappingGetSwitching( Fpga_Man_t * pMan, Fpga_NodeV extern float Fpga_TimeCutComputeArrival( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); extern float Fpga_TimeCutComputeArrival_rec( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); extern float Fpga_TimeComputeArrivalMax( Fpga_Man_t * p ); -extern void Fpga_TimeComputeRequiredGlobal( Fpga_Man_t * p ); +extern void Fpga_TimeComputeRequiredGlobal( Fpga_Man_t * p, int fFirstTime ); extern void Fpga_TimeComputeRequired( Fpga_Man_t * p, float fRequired ); extern void Fpga_TimePropagateRequired( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ); extern void Fpga_TimePropagateArrival( Fpga_Man_t * p ); @@ -375,8 +381,8 @@ extern void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan ); /*=== CUDD package.c ===============================================================*/ extern unsigned int Cudd_Prime( unsigned int p ); +#endif + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// - -#endif diff --git a/src/map/fpga/fpgaLib.c b/src/map/fpga/fpgaLib.c index 9fd8e281..b1bb4cdc 100644 --- a/src/map/fpga/fpgaLib.c +++ b/src/map/fpga/fpgaLib.c @@ -23,11 +23,26 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* + Synopsis [APIs to access LUT library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_LutLibReadVarMax( Fpga_LutLib_t * p ) { return p->LutMax; } +float * Fpga_LutLibReadLutAreas( Fpga_LutLib_t * p ) { return p->pLutAreas; } +float Fpga_LutLibReadLutArea( Fpga_LutLib_t * p, int Size ) { assert( Size <= p->LutMax ); return p->pLutAreas[Size]; } + +/**Function************************************************************* + Synopsis [Reads the description of LUTs from the LUT library file.] Description [] @@ -42,7 +57,7 @@ Fpga_LutLib_t * Fpga_LutLibCreate( char * FileName, int fVerbose ) char pBuffer[1000], * pToken; Fpga_LutLib_t * p; FILE * pFile; - int i; + int i, k; pFile = fopen( FileName, "r" ); if ( pFile == NULL ) @@ -53,7 +68,7 @@ Fpga_LutLib_t * Fpga_LutLibCreate( char * FileName, int fVerbose ) p = ALLOC( Fpga_LutLib_t, 1 ); memset( p, 0, sizeof(Fpga_LutLib_t) ); - p->pName = util_strsav( FileName ); + p->pName = Extra_UtilStrsav( FileName ); i = 1; while ( fgets( pBuffer, 1000, pFile ) != NULL ) @@ -70,25 +85,66 @@ Fpga_LutLib_t * Fpga_LutLibCreate( char * FileName, int fVerbose ) return NULL; } + // read area pToken = strtok( NULL, " \t\n" ); p->pLutAreas[i] = (float)atof(pToken); - pToken = strtok( NULL, " \t\n" ); - p->pLutDelays[i] = (float)atof(pToken); + // read delays + k = 0; + while ( pToken = strtok( NULL, " \t\n" ) ) + p->pLutDelays[i][k++] = (float)atof(pToken); + + // check for out-of-bound + if ( k > i ) + { + printf( "LUT %d has too many pins (%d). Max allowed is %d.\n", i, k, i ); + return NULL; + } + + // check if var delays are specifies + if ( k > 1 ) + p->fVarPinDelays = 1; if ( i == FPGA_MAX_LUTSIZE ) { printf( "Skipping LUTs of size more than %d.\n", i ); - break; + return NULL; } i++; } p->LutMax = i-1; + if ( p->LutMax > FPGA_MAX_LEAVES ) { p->LutMax = FPGA_MAX_LEAVES; - printf( "Warning: LUTs with more than %d input will not be used.\n", FPGA_MAX_LEAVES ); + printf( "Warning: LUTs with more than %d inputs will not be used.\n", FPGA_MAX_LEAVES ); } + + // check the library + if ( p->fVarPinDelays ) + { + for ( i = 1; i <= p->LutMax; i++ ) + for ( k = 0; k < i; k++ ) + { + if ( p->pLutDelays[i][k] <= 0.0 ) + printf( "Warning: Pin %d of LUT %d has delay %f. Pin delays should be non-negative numbers. Technology mapping may not work correctly.\n", + k, i, p->pLutDelays[i][k] ); + if ( k && p->pLutDelays[i][k-1] > p->pLutDelays[i][k] ) + printf( "Warning: Pin %d of LUT %d has delay %f. Pin %d of LUT %d has delay %f. Pin delays should be in non-decreasing order. Technology mapping may not work correctly.\n", + k-1, i, p->pLutDelays[i][k-1], + k, i, p->pLutDelays[i][k] ); + } + } + else + { + for ( i = 1; i <= p->LutMax; i++ ) + { + if ( p->pLutDelays[i][0] <= 0.0 ) + printf( "Warning: LUT %d has delay %f. Pin delays should be non-negative numbers. Technology mapping may not work correctly.\n", + k, i, p->pLutDelays[i][0] ); + } + } + return p; } @@ -108,7 +164,7 @@ Fpga_LutLib_t * Fpga_LutLibDup( Fpga_LutLib_t * p ) Fpga_LutLib_t * pNew; pNew = ALLOC( Fpga_LutLib_t, 1 ); *pNew = *p; - pNew->pName = util_strsav( pNew->pName ); + pNew->pName = Extra_UtilStrsav( pNew->pName ); return pNew; } @@ -145,11 +201,22 @@ void Fpga_LutLibFree( Fpga_LutLib_t * pLutLib ) ***********************************************************************/ void Fpga_LutLibPrint( Fpga_LutLib_t * pLutLib ) { - int i; + int i, k; printf( "# The area/delay of k-variable LUTs:\n" ); printf( "# k area delay\n" ); - for ( i = 1; i <= pLutLib->LutMax; i++ ) - printf( "%d %7.2f %7.2f\n", i, pLutLib->pLutAreas[i], pLutLib->pLutDelays[i] ); + if ( pLutLib->fVarPinDelays ) + { + for ( i = 1; i <= pLutLib->LutMax; i++ ) + { + printf( "%d %7.2f ", i, pLutLib->pLutAreas[i] ); + for ( k = 0; k < i; k++ ) + printf( " %7.2f", pLutLib->pLutDelays[i][k] ); + printf( "\n" ); + } + } + else + for ( i = 1; i <= pLutLib->LutMax; i++ ) + printf( "%d %7.2f %7.2f\n", i, pLutLib->pLutAreas[i], pLutLib->pLutDelays[i][0] ); } /**Function************************************************************* @@ -169,7 +236,7 @@ int Fpga_LutLibDelaysAreDiscrete( Fpga_LutLib_t * pLutLib ) int i; for ( i = 1; i <= pLutLib->LutMax; i++ ) { - Delay = pLutLib->pLutDelays[i]; + Delay = pLutLib->pLutDelays[i][0]; if ( ((float)((int)Delay)) != Delay ) return 0; } diff --git a/src/map/fpga/fpgaMatch.c b/src/map/fpga/fpgaMatch.c index 20444209..73fa1258 100644 --- a/src/map/fpga/fpgaMatch.c +++ b/src/map/fpga/fpgaMatch.c @@ -30,7 +30,7 @@ static Fpga_Cut_t * Fpga_MappingAreaWithoutNode( Fpga_Man_t * p, Fpga_Node_t * p static int Fpga_MappingMatchesAreaArray( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -87,6 +87,18 @@ int Fpga_MappingMatches( Fpga_Man_t * p, int fDelayOriented ) Extra_ProgressBarUpdate( pProgress, i, "Matches ..." ); } Extra_ProgressBarStop( pProgress ); +/* + if ( !fDelayOriented ) + { + float Area = 0.0; + for ( i = 0; i < p->nOutputs; i++ ) + { + printf( "%5.2f ", Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow ); + Area += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow; + } + printf( "\nTotal = %5.2f\n", Area ); + } +*/ return 1; } @@ -128,7 +140,7 @@ clk = clock(); Fpga_CutGetParameters( p, pCut ); //p->time2 += clock() - clk; // drop the cut if it does not meet the required times - if ( pCut->tArrival > pNode->tRequired ) + if ( Fpga_FloatMoreThan(p, pCut->tArrival, pNode->tRequired) ) continue; // if no cut is assigned, use the current one if ( pNode->pCutBest == NULL ) @@ -140,11 +152,11 @@ clk = clock(); // (1) delay oriented mapping (first traversal), delay first, area-flow as a tie-breaker // (2) area recovery (subsequent traversals), area-flow first, delay as a tie-breaker if ( (fDelayOriented && - (pNode->pCutBest->tArrival > pCut->tArrival || - pNode->pCutBest->tArrival == pCut->tArrival && pNode->pCutBest->aFlow > pCut->aFlow)) || + (Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival) || + Fpga_FloatEqual(p, pNode->pCutBest->tArrival, pCut->tArrival) && Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) )) || (!fDelayOriented && - (pNode->pCutBest->aFlow > pCut->aFlow || - pNode->pCutBest->aFlow == pCut->aFlow && pNode->pCutBest->tArrival > pCut->tArrival)) ) + (Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) || + Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival))) ) { pNode->pCutBest = pCut; } @@ -277,7 +289,7 @@ clk = clock(); pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut ); //p->time2 += clock() - clk; // drop the cut if it does not meet the required times - if ( pCut->tArrival > pNode->tRequired ) + if ( Fpga_FloatMoreThan( p, pCut->tArrival, pNode->tRequired ) ) continue; // get the area of this cut pCut->aFlow = Fpga_CutGetAreaDerefed( p, pCut ); @@ -288,8 +300,8 @@ clk = clock(); continue; } // choose the best cut as follows: exact area first, delay as a tie-breaker - if ( pNode->pCutBest->aFlow > pCut->aFlow || - pNode->pCutBest->aFlow == pCut->aFlow && pNode->pCutBest->tArrival > pCut->tArrival ) + if ( Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) || + Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival) ) { pNode->pCutBest = pCut; } @@ -311,7 +323,7 @@ clk = clock(); if ( pNode->nRefs ) { pNode->pCutBest->aFlow = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 ); - assert( pNode->pCutBest->aFlow <= aAreaCutBest ); +// assert( pNode->pCutBest->aFlow <= aAreaCutBest ); // assert( pNode->tRequired < FPGA_FLOAT_LARGE ); } return 1; @@ -398,7 +410,7 @@ clk = clock(); pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut ); //p->time2 += clock() - clk; // drop the cut if it does not meet the required times - if ( pCut->tArrival > pNode->tRequired ) + if ( Fpga_FloatMoreThan( p, pCut->tArrival, pNode->tRequired ) ) continue; // get the area of this cut pCut->aFlow = Fpga_CutGetSwitchDerefed( p, pNode, pCut ); @@ -409,8 +421,8 @@ clk = clock(); continue; } // choose the best cut as follows: exact area first, delay as a tie-breaker - if ( pNode->pCutBest->aFlow > pCut->aFlow || - pNode->pCutBest->aFlow == pCut->aFlow && pNode->pCutBest->tArrival > pCut->tArrival ) + if ( Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) || + Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival) ) { pNode->pCutBest = pCut; } @@ -501,7 +513,7 @@ void Fpga_Experiment( Fpga_Man_t * p ) AreaBefore = pNode->pCutBest->aFlow; pNode->pCutBest->aFlow = FPGA_FLOAT_LARGE; - Fpga_TimeComputeRequiredGlobal( p ); + Fpga_TimeComputeRequiredGlobal( p, 0 ); vNodesTfo = Fpga_CollectNodeTfo( p, pNode ); if ( Fpga_MappingMatchesAreaArray( p, vNodesTfo ) == 0 ) diff --git a/src/map/fpga/fpgaSwitch.c b/src/map/fpga/fpgaSwitch.c index 8cc77990..5e881959 100644 --- a/src/map/fpga/fpgaSwitch.c +++ b/src/map/fpga/fpgaSwitch.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**function************************************************************* @@ -139,8 +139,8 @@ float Fpga_MappingGetSwitching( Fpga_Man_t * pMan, Fpga_NodeVec_t * vMapping ) } // add buffer for each CO driven by a CI for ( i = 0; i < pMan->nOutputs; i++ ) - if ( Fpga_NodeIsVar(pMan->pOutputs[i]) && !Fpga_IsComplement(pMan->pOutputs[i]) ) - Switch += pMan->pOutputs[i]->Switching; + if ( Fpga_NodeIsVar(Fpga_Regular(pMan->pOutputs[i])) && !Fpga_IsComplement(pMan->pOutputs[i]) ) + Switch += Fpga_Regular(pMan->pOutputs[i])->Switching; return Switch; } diff --git a/src/map/fpga/fpgaTime.c b/src/map/fpga/fpgaTime.c index 6cbe16f9..879cad4d 100644 --- a/src/map/fpga/fpgaTime.c +++ b/src/map/fpga/fpgaTime.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -46,7 +46,7 @@ float Fpga_TimeCutComputeArrival( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) for ( i = 0; i < pCut->nLeaves; i++ ) if ( tArrival < pCut->ppLeaves[i]->pCutBest->tArrival ) tArrival = pCut->ppLeaves[i]->pCutBest->tArrival; - tArrival += pMan->pLutLib->pLutDelays[pCut->nLeaves]; + tArrival += pMan->pLutLib->pLutDelays[pCut->nLeaves][0]; return tArrival; } @@ -87,13 +87,34 @@ float Fpga_TimeComputeArrivalMax( Fpga_Man_t * p ) { float fRequired; int i; + if ( p->fLatchPaths && p->nLatches == 0 ) + { + printf( "Delay optimization of latch path is not performed because there is no latches.\n" ); + p->fLatchPaths = 0; + } // get the critical PO arrival time fRequired = -FPGA_FLOAT_LARGE; - for ( i = 0; i < p->nOutputs; i++ ) + if ( p->fLatchPaths ) { - if ( Fpga_NodeIsConst(p->pOutputs[i]) ) - continue; - fRequired = FPGA_MAX( fRequired, Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival ); + for ( i = p->nOutputs - p->nLatches; i < p->nOutputs; i++ ) + { + if ( Fpga_NodeIsConst(p->pOutputs[i]) ) + continue; + fRequired = FPGA_MAX( fRequired, Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival ); +// printf( " %5.1f", Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival ); + } +// printf( "Required latches = %5.1f\n", fRequired ); + } + else + { + for ( i = 0; i < p->nOutputs; i++ ) + { + if ( Fpga_NodeIsConst(p->pOutputs[i]) ) + continue; + fRequired = FPGA_MAX( fRequired, Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival ); +// printf( " %5.1f", Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival ); + } +// printf( "Required outputs = %5.1f\n", fRequired ); } return fRequired; } @@ -109,9 +130,24 @@ float Fpga_TimeComputeArrivalMax( Fpga_Man_t * p ) SeeAlso [] ***********************************************************************/ -void Fpga_TimeComputeRequiredGlobal( Fpga_Man_t * p ) +void Fpga_TimeComputeRequiredGlobal( Fpga_Man_t * p, int fFirstTime ) { p->fRequiredGlo = Fpga_TimeComputeArrivalMax( p ); + // update the required times according to the target + if ( p->DelayTarget != -1 ) + { + if ( p->fRequiredGlo > p->DelayTarget + p->fEpsilon ) + { + if ( fFirstTime ) + printf( "Cannot meet the target required times (%4.2f). Mapping continues anyway.\n", p->DelayTarget ); + } + else if ( p->fRequiredGlo < p->DelayTarget - p->fEpsilon ) + { + if ( fFirstTime ) + printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->fRequiredGlo, p->DelayTarget ); + p->fRequiredGlo = p->DelayTarget; + } + } Fpga_TimeComputeRequired( p, p->fRequiredGlo ); } @@ -133,10 +169,23 @@ void Fpga_TimeComputeRequired( Fpga_Man_t * p, float fRequired ) for ( i = 0; i < p->vAnds->nSize; i++ ) p->vAnds->pArray[i]->tRequired = FPGA_FLOAT_LARGE; // set the required times for the POs - for ( i = 0; i < p->nOutputs; i++ ) - Fpga_Regular(p->pOutputs[i])->tRequired = fRequired; + if ( p->fLatchPaths ) + for ( i = p->nOutputs - p->nLatches; i < p->nOutputs; i++ ) + Fpga_Regular(p->pOutputs[i])->tRequired = fRequired; + else + for ( i = 0; i < p->nOutputs; i++ ) + Fpga_Regular(p->pOutputs[i])->tRequired = fRequired; // collect nodes reachable from POs in the DFS order through the best cuts Fpga_TimePropagateRequired( p, p->vMapping ); +/* + { + int Counter = 0; + for ( i = 0; i < p->vAnds->nSize; i++ ) + if ( p->vAnds->pArray[i]->tRequired > FPGA_FLOAT_LARGE - 100 ) + Counter++; + printf( "The number of nodes with large required times = %d.\n", Counter ); + } +*/ } /**Function************************************************************* @@ -167,7 +216,7 @@ void Fpga_TimePropagateRequired( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ) if ( !Fpga_NodeIsAnd(pNode) ) continue; // get the required time for children - fRequired = pNode->tRequired - p->pLutLib->pLutDelays[pNode->pCutBest->nLeaves]; + fRequired = pNode->tRequired - p->pLutLib->pLutDelays[pNode->pCutBest->nLeaves][0]; // update the required time of the children for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) { diff --git a/src/map/fpga/fpgaTruth.c b/src/map/fpga/fpgaTruth.c index 17c6385c..e3eb487f 100644 --- a/src/map/fpga/fpgaTruth.c +++ b/src/map/fpga/fpgaTruth.c @@ -24,7 +24,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -94,12 +94,71 @@ void * Fpga_TruthsCutBdd( void * dd, Fpga_Cut_t * pCut ) Cudd_RecursiveDeref( dd, (DdNode*)pCut->uSign ); pCut->uSign = 0; } +// printf( "%d ", vVisited->nSize ); Fpga_NodeVecFree( vVisited ); Cudd_Deref( bFunc ); return bFunc; } +/**Function************************************************************* + + Synopsis [Recursively derives the truth table for the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutVolume_rec( Fpga_Cut_t * pCut, Fpga_NodeVec_t * vVisited ) +{ + assert( !Fpga_IsComplement(pCut) ); + if ( pCut->fMark ) + return; + pCut->fMark = 1; + Fpga_CutVolume_rec( Fpga_CutRegular(pCut->pOne), vVisited ); + Fpga_CutVolume_rec( Fpga_CutRegular(pCut->pTwo), vVisited ); + Fpga_NodeVecPush( vVisited, (Fpga_Node_t *)pCut ); +} + +/**Function************************************************************* + + Synopsis [Derives the truth table for one cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutVolume( Fpga_Cut_t * pCut ) +{ + Fpga_NodeVec_t * vVisited; + int Volume, i; + assert( pCut->nLeaves > 1 ); + // set the leaf variables + for ( i = 0; i < pCut->nLeaves; i++ ) + pCut->ppLeaves[i]->pCuts->fMark = 1; + // recursively compute the function + vVisited = Fpga_NodeVecAlloc( 10 ); + Fpga_CutVolume_rec( pCut, vVisited ); + // clean the marks + for ( i = 0; i < pCut->nLeaves; i++ ) + pCut->ppLeaves[i]->pCuts->fMark = 0; + for ( i = 0; i < vVisited->nSize; i++ ) + { + pCut = (Fpga_Cut_t *)vVisited->pArray[i]; + pCut->fMark = 0; + } + Volume = vVisited->nSize; + printf( "%d ", Volume ); + Fpga_NodeVecFree( vVisited ); + return Volume; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/map/fpga/fpgaUtils.c b/src/map/fpga/fpgaUtils.c index db0f9623..b951fd8f 100644 --- a/src/map/fpga/fpgaUtils.c +++ b/src/map/fpga/fpgaUtils.c @@ -30,10 +30,11 @@ static int Fpga_MappingCompareOutputDelay( Fpga_Node_t ** ppNode1, Fpga_Node_t static void Fpga_MappingFindLatest( Fpga_Man_t * p, int * pNodes, int nNodesMax ); static void Fpga_DfsLim_rec( Fpga_Node_t * pNode, int Level, Fpga_NodeVec_t * vNodes ); static int Fpga_CollectNodeTfo_rec( Fpga_Node_t * pNode, Fpga_Node_t * pPivot, Fpga_NodeVec_t * vVisited, Fpga_NodeVec_t * vTfo ); +static Fpga_NodeVec_t * Fpga_MappingOrderCosByLevel( Fpga_Man_t * pMan ); static Fpga_Man_t * s_pMan = NULL; //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// @@ -50,9 +51,11 @@ static Fpga_Man_t * s_pMan = NULL; ***********************************************************************/ Fpga_NodeVec_t * Fpga_MappingDfs( Fpga_Man_t * pMan, int fCollectEquiv ) { - Fpga_NodeVec_t * vNodes; + Fpga_NodeVec_t * vNodes;//, * vNodesCo; Fpga_Node_t * pNode; int i; + // collect the CO nodes by level +// vNodesCo = Fpga_MappingOrderCosByLevel( pMan ); // start the array vNodes = Fpga_NodeVecAlloc( 100 ); // collect the PIs @@ -65,10 +68,15 @@ Fpga_NodeVec_t * Fpga_MappingDfs( Fpga_Man_t * pMan, int fCollectEquiv ) // perform the traversal for ( i = 0; i < pMan->nOutputs; i++ ) Fpga_MappingDfs_rec( Fpga_Regular(pMan->pOutputs[i]), vNodes, fCollectEquiv ); +// for ( i = vNodesCo->nSize - 1; i >= 0 ; i-- ) +// for ( pNode = vNodesCo->pArray[i]; pNode; pNode = (Fpga_Node_t *)pNode->pData0 ) +// Fpga_MappingDfs_rec( pNode, vNodes, fCollectEquiv ); + // clean the node marks for ( i = 0; i < vNodes->nSize; i++ ) vNodes->pArray[i]->fMark0 = 0; // for ( i = 0; i < pMan->nOutputs; i++ ) // Fpga_MappingUnmark_rec( Fpga_Regular(pMan->pOutputs[i]) ); +// Fpga_NodeVecFree( vNodesCo ); return vNodes; } @@ -930,6 +938,47 @@ void Fpga_ManReportChoices( Fpga_Man_t * pMan ) */ } +/**Function************************************************************* + + Synopsis [Returns the array of CO nodes sorted by level.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_NodeVec_t * Fpga_MappingOrderCosByLevel( Fpga_Man_t * pMan ) +{ + Fpga_Node_t * pNode; + Fpga_NodeVec_t * vNodes; + int i, nLevels; + // get the largest level of a CO + nLevels = Fpga_MappingMaxLevel( pMan ); + // allocate the array of nodes + vNodes = Fpga_NodeVecAlloc( nLevels + 1 ); + for ( i = 0; i <= nLevels; i++ ) + Fpga_NodeVecPush( vNodes, NULL ); + // clean the marks + for ( i = 0; i < pMan->nOutputs; i++ ) + Fpga_Regular(pMan->pOutputs[i])->fMark0 = 0; + // put the nodes into the structure + for ( i = 0; i < pMan->nOutputs; i++ ) + { + pNode = Fpga_Regular(pMan->pOutputs[i]); + if ( pNode->fMark0 ) + continue; + pNode->fMark0 = 1; + pNode->pData0 = (char *)Fpga_NodeVecReadEntry( vNodes, pNode->Level ); + Fpga_NodeVecWriteEntry( vNodes, pNode->Level, pNode ); + } + for ( i = 0; i < pMan->nOutputs; i++ ) + Fpga_Regular(pMan->pOutputs[i])->fMark0 = 0; + return vNodes; + +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/map/fpga/fpgaVec.c b/src/map/fpga/fpgaVec.c index a8c6b983..70a4a7ac 100644 --- a/src/map/fpga/fpgaVec.c +++ b/src/map/fpga/fpgaVec.c @@ -25,7 +25,7 @@ static int Fpga_NodeVecCompareLevels( Fpga_Node_t ** pp1, Fpga_Node_t ** pp2 ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* diff --git a/src/map/if/if.h b/src/map/if/if.h new file mode 100644 index 00000000..b3d2d745 --- /dev/null +++ b/src/map/if/if.h @@ -0,0 +1,410 @@ +/**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" +#include "tim.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 parameters + 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 fEdge; // uses edge-based cut selection heuristics + int fCutMin; // performs cut minimization by removing functionally reducdant variables + 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 * vObjsRev; // reverse topological order of 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 + int nSmallSupp; // the small support + // timing manager + Tim_Man_t * pManTim; +}; + +// 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 + float Edge; // the edge flow + 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 IdPio; // integer ID of PIs/POs + 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 int * If_CutLeaves( If_Cut_t * pCut ) { return pCut->pLeaves; } +static inline unsigned * If_CutTruth( If_Cut_t * pCut ) { return pCut->pTruth; } +static inline unsigned If_CutSuppMask( If_Cut_t * pCut ) { return (~(unsigned)0) >> (32-pCut->nLeaves); } +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 in topological order +#define If_ManForEachObj( p, pObj, i ) \ + Vec_PtrForEachEntry( p->vObjs, pObj, i ) +// iterator over all objects in reverse topological order +#define If_ManForEachObjReverse( p, pObj, i ) \ + Vec_PtrForEachEntry( p->vObjsRev, 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 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_CutPrint( If_Man_t * p, If_Cut_t * pCut ); +extern void If_CutPrintTiming( If_Man_t * p, 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 float If_CutAreaFlow( If_Man_t * p, If_Cut_t * pCut ); +extern float If_CutEdgeFlow( If_Man_t * p, If_Cut_t * pCut ); +extern float If_CutAverageRefs( If_Man_t * p, If_Cut_t * pCut ); +extern float If_CutAreaDeref( If_Man_t * p, If_Cut_t * pCut ); +extern float If_CutAreaRef( If_Man_t * p, If_Cut_t * pCut ); +extern float If_CutAreaDerefed( If_Man_t * p, If_Cut_t * pCut ); +extern float If_CutAreaRefed( If_Man_t * p, If_Cut_t * pCut ); +extern float If_CutEdgeDeref( If_Man_t * p, If_Cut_t * pCut ); +extern float If_CutEdgeRef( If_Man_t * p, If_Cut_t * pCut ); +extern float If_CutEdgeDerefed( If_Man_t * p, If_Cut_t * pCut ); +extern float If_CutEdgeRefed( If_Man_t * p, If_Cut_t * pCut ); +/*=== 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_ManScanMappingDirect( 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 ); + +extern Vec_Ptr_t * If_ManReverseOrder( If_Man_t * p ); +extern void If_ManMarkMapping( If_Man_t * p ); +extern Vec_Ptr_t * If_ManCollectMappingDirect( 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 new file mode 100644 index 00000000..f7124703 --- /dev/null +++ b/src/map/if/ifCore.c @@ -0,0 +1,148 @@ +/**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) ); + // derive reverse top order + p->vObjsRev = If_ManReverseOrder( p ); + + // try sequential mapping + if ( p->pPars->fSeqMap ) + { + int RetValue = 1; + 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 new file mode 100644 index 00000000..cc842c19 --- /dev/null +++ b/src/map/if/ifCut.c @@ -0,0 +1,988 @@ +/**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_Man_t * p, If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) +{ + If_Cut_t * pC0 = *ppC0; + If_Cut_t * pC1 = *ppC1; + if ( pC0->Delay < pC1->Delay - p->fEpsilon ) + return -1; + if ( pC0->Delay > pC1->Delay + p->fEpsilon ) + return 1; + if ( pC0->nLeaves < pC1->nLeaves ) + return -1; + if ( pC0->nLeaves > pC1->nLeaves ) + return 1; + if ( pC0->Area < pC1->Area - p->fEpsilon ) + return -1; + if ( pC0->Area > pC1->Area + p->fEpsilon ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Prepares the object for FPGA mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutCompareDelayOld( If_Man_t * p, If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) +{ + If_Cut_t * pC0 = *ppC0; + If_Cut_t * pC1 = *ppC1; + if ( pC0->Delay < pC1->Delay - p->fEpsilon ) + return -1; + if ( pC0->Delay > pC1->Delay + p->fEpsilon ) + return 1; + if ( pC0->Area < pC1->Area - p->fEpsilon ) + return -1; + if ( pC0->Area > pC1->Area + p->fEpsilon ) + 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_Man_t * p, If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) +{ + If_Cut_t * pC0 = *ppC0; + If_Cut_t * pC1 = *ppC1; + if ( pC0->Area < pC1->Area - p->fEpsilon ) + return -1; + if ( pC0->Area > pC1->Area + p->fEpsilon ) + 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 - p->fEpsilon ) + return -1; + if ( pC0->Delay > pC1->Delay + p->fEpsilon ) + 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 - p->fEpsilon ) + return -1; + if ( pC0->Area > pC1->Area + p->fEpsilon ) + return 1; + if ( pC0->Edge < pC1->Edge - p->fEpsilon ) + return -1; + if ( pC0->Edge > pC1->Edge + p->fEpsilon ) + 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 - p->fEpsilon ) + return -1; + if ( pC0->Delay > pC1->Delay + p->fEpsilon ) + return 1; + return 0; + } + if ( p->SortMode == 0 ) // delay + { + if ( pC0->Delay < pC1->Delay - p->fEpsilon ) + return -1; + if ( pC0->Delay > pC1->Delay + p->fEpsilon ) + return 1; + if ( pC0->nLeaves < pC1->nLeaves ) + return -1; + if ( pC0->nLeaves > pC1->nLeaves ) + return 1; + if ( pC0->Area < pC1->Area - p->fEpsilon ) + return -1; + if ( pC0->Area > pC1->Area + p->fEpsilon ) + return 1; + if ( pC0->Edge < pC1->Edge - p->fEpsilon ) + return -1; + if ( pC0->Edge > pC1->Edge + p->fEpsilon ) + return 1; + return 0; + } + assert( p->SortMode == 2 ); // delay old + if ( pC0->Delay < pC1->Delay - p->fEpsilon ) + return -1; + if ( pC0->Delay > pC1->Delay + p->fEpsilon ) + return 1; + if ( pC0->Area < pC1->Area - p->fEpsilon ) + return -1; + if ( pC0->Area > pC1->Area + p->fEpsilon ) + return 1; + if ( pC0->Edge < pC1->Edge - p->fEpsilon ) + return -1; + if ( pC0->Edge > pC1->Edge + p->fEpsilon ) + return 1; + if ( pC0->nLeaves < pC1->nLeaves ) + return -1; + if ( pC0->nLeaves > pC1->nLeaves ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Comparison function for two cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_ManSortCompare_old( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1 ) +{ + if ( p->SortMode == 1 ) // area + { + if ( pC0->Area < pC1->Area - p->fEpsilon ) + return -1; + if ( pC0->Area > pC1->Area + p->fEpsilon ) + 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 - p->fEpsilon ) + return -1; + if ( pC0->Delay > pC1->Delay + p->fEpsilon ) + return 1; + return 0; + } + if ( p->SortMode == 0 ) // delay + { + if ( pC0->Delay < pC1->Delay - p->fEpsilon ) + return -1; + if ( pC0->Delay > pC1->Delay + p->fEpsilon ) + return 1; + if ( pC0->nLeaves < pC1->nLeaves ) + return -1; + if ( pC0->nLeaves > pC1->nLeaves ) + return 1; + if ( pC0->Area < pC1->Area - p->fEpsilon ) + return -1; + if ( pC0->Area > pC1->Area + p->fEpsilon ) + return 1; + return 0; + } + assert( p->SortMode == 2 ); // delay old + if ( pC0->Delay < pC1->Delay - p->fEpsilon ) + return -1; + if ( pC0->Delay > pC1->Delay + p->fEpsilon ) + return 1; + if ( pC0->Area < pC1->Area - p->fEpsilon ) + return -1; + if ( pC0->Area > pC1->Area + p->fEpsilon ) + 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 [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 [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; +} + + +/**Function************************************************************* + + Synopsis [Computes area flow.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_CutAreaFlow( 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 [Computes area flow.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_CutEdgeFlow( If_Man_t * p, If_Cut_t * pCut ) +{ + If_Obj_t * pLeaf; + float Flow; + int i; + assert( p->pPars->fSeqMap || pCut->nLeaves > 1 ); + Flow = pCut->nLeaves; + If_CutForEachLeaf( p, pCut, pLeaf, i ) + { + if ( pLeaf->nRefs == 0 ) + Flow += If_ObjCutBest(pLeaf)->Edge; + else if ( p->pPars->fSeqMap ) // seq + Flow += If_ObjCutBest(pLeaf)->Edge / pLeaf->nRefs; + else + { + assert( pLeaf->EstRefs > p->fEpsilon ); + Flow += If_ObjCutBest(pLeaf)->Edge / 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_CutAreaDeref( If_Man_t * p, If_Cut_t * pCut ) +{ + 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) ) + continue; + Area += If_CutAreaDeref( p, If_ObjCutBest(pLeaf) ); + } + return Area; +} + +/**Function************************************************************* + + Synopsis [Computes area of the first level.] + + Description [The cut need to be derefed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_CutAreaRef( If_Man_t * p, If_Cut_t * pCut ) +{ + 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) ) + continue; + Area += If_CutAreaRef( p, If_ObjCutBest(pLeaf) ); + } + return Area; +} + +/**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 ) +{ + float aResult, aResult2; + assert( p->pPars->fSeqMap || pCut->nLeaves > 1 ); + aResult2 = If_CutAreaRef( p, pCut ); + aResult = If_CutAreaDeref( p, pCut ); + 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 ) +{ + float aResult, aResult2; + assert( p->pPars->fSeqMap || pCut->nLeaves > 1 ); + aResult2 = If_CutAreaDeref( p, pCut ); + aResult = If_CutAreaRef( p, pCut ); + 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_CutEdgeDeref( If_Man_t * p, If_Cut_t * pCut ) +{ + If_Obj_t * pLeaf; + float Edge; + int i; + Edge = pCut->nLeaves; + If_CutForEachLeaf( p, pCut, pLeaf, i ) + { + assert( pLeaf->nRefs > 0 ); + if ( --pLeaf->nRefs > 0 || !If_ObjIsAnd(pLeaf) ) + continue; + Edge += If_CutEdgeDeref( p, If_ObjCutBest(pLeaf) ); + } + return Edge; +} + +/**Function************************************************************* + + Synopsis [Computes area of the first level.] + + Description [The cut need to be derefed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_CutEdgeRef( If_Man_t * p, If_Cut_t * pCut ) +{ + If_Obj_t * pLeaf; + float Edge; + int i; + Edge = pCut->nLeaves; + If_CutForEachLeaf( p, pCut, pLeaf, i ) + { + assert( pLeaf->nRefs >= 0 ); + if ( pLeaf->nRefs++ > 0 || !If_ObjIsAnd(pLeaf) ) + continue; + Edge += If_CutEdgeRef( p, If_ObjCutBest(pLeaf) ); + } + return Edge; +} + +/**Function************************************************************* + + Synopsis [Computes edge of the first level.] + + Description [The cut need to be derefed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_CutEdgeDerefed( If_Man_t * p, If_Cut_t * pCut ) +{ + float aResult, aResult2; + assert( p->pPars->fSeqMap || pCut->nLeaves > 1 ); + aResult2 = If_CutEdgeRef( p, pCut ); + aResult = If_CutEdgeDeref( p, pCut ); + 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_CutEdgeRefed( If_Man_t * p, If_Cut_t * pCut ) +{ + float aResult, aResult2; + assert( p->pPars->fSeqMap || pCut->nLeaves > 1 ); + aResult2 = If_CutEdgeDeref( p, pCut ); + aResult = If_CutEdgeRef( p, pCut ); + assert( aResult > aResult2 - p->fEpsilon ); + assert( aResult < aResult2 + p->fEpsilon ); + return aResult; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c new file mode 100644 index 00000000..6b21919b --- /dev/null +++ b/src/map/if/ifMan.c @@ -0,0 +1,577 @@ +/**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( "K = %d. Memory (bytes): Truth = %4d. Cut = %4d. Obj = %4d. Set = %4d.\n", + p->pPars->nLutSize, 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 ) +{ +// printf( "Small support = %d.\n", p->nSmallSupp ); + Vec_PtrFree( p->vCis ); + Vec_PtrFree( p->vCos ); + Vec_PtrFree( p->vObjs ); +// Vec_PtrFree( p->vMapped ); + Vec_PtrFree( p->vTemp ); + if ( p->vObjsRev ) Vec_PtrFree( p->vObjsRev ); + 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 ); + if ( p->pManTim ) + Tim_ManStop( p->pManTim ); + 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; + pObj->IdPio = Vec_PtrSize( p->vCis ); + 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 ); + pObj->IdPio = Vec_PtrSize( p->vCos ); + Vec_PtrPush( p->vCos, pObj ); + pObj->Type = IF_CO; + pObj->fCompl0 = If_IsComplement(pDriver); pDriver = If_Regular(pDriver); + pObj->pFanin0 = pDriver; pDriver->nRefs++; + pObj->Level = pDriver->Level; + 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 new file mode 100644 index 00000000..1ac5ef21 --- /dev/null +++ b/src/map/if/ifMap.c @@ -0,0 +1,350 @@ +/**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_CutAreaDeref( p, If_ObjCutBest(pObj) ); + + // 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_CutAreaFlow( p, pCut ); + if ( p->pPars->fEdge ) + pCut->Edge = (Mode == 2)? If_CutEdgeDerefed( p, pCut ) : If_CutEdgeFlow( 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_CutAreaFlow( p, pCut ); + if ( p->pPars->fEdge ) + pCut->Edge = (Mode == 2)? If_CutEdgeDerefed( p, pCut ) : If_CutEdgeFlow( 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_CutAreaRef( p, If_ObjCutBest(pObj) ); + + // 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_CutAreaDeref( p, If_ObjCutBest(pObj) ); + + // 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_CutAreaFlow( p, pCut ); + if ( p->pPars->fEdge ) + pCut->Edge = (Mode == 2)? If_CutEdgeDerefed( p, pCut ) : If_CutEdgeFlow( 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_CutAreaRef( p, If_ObjCutBest(pObj) ); + + // 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(); + float arrTime; + 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; + // make sure the visit counters are all zero + If_ManForEachNode( p, pObj, i ) + assert( pObj->nVisits == pObj->nVisitsCopy ); + // map the internal nodes + if ( p->pManTim != NULL ) + { + Tim_ManIncrementTravId( p->pManTim ); + If_ManForEachObj( p, pObj, i ) + { + if ( If_ObjIsAnd(pObj) ) + { + If_ObjPerformMappingAnd( p, pObj, Mode, fPreprocess ); + if ( pObj->fRepr ) + If_ObjPerformMappingChoice( p, pObj, Mode, fPreprocess ); + } + else if ( If_ObjIsCi(pObj) ) + { + arrTime = Tim_ManGetPiArrival( p->pManTim, pObj->IdPio ); + If_ObjSetArrTime( pObj, arrTime ); +/* + if ( pObj->IdPio >= 2000 ) + { + int x = 0; + printf( "+%d %6.3f ", pObj->IdPio, arrTime ); + } +*/ + } + else if ( If_ObjIsCo(pObj) ) + { + arrTime = If_ObjArrTime( If_ObjFanin0(pObj) ); + Tim_ManSetPoArrival( p->pManTim, pObj->IdPio, arrTime ); + } + else if ( If_ObjIsConst1(pObj) ) + { + } + else + assert( 0 ); + } +// Tim_ManPrint( p->pManTim ); + } + else + { + // 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 ); +// Tim_ManPrint( p->pManTim ); + if ( p->pPars->fVerbose ) + { + char Symb = fPreprocess? 'P' : ((Mode == 0)? 'D' : ((Mode == 1)? 'F' : 'A')); + printf( "%c: Del = %7.2f. Ar = %9.1f. Edge = %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 new file mode 100644 index 00000000..0912a965 --- /dev/null +++ b/src/map/if/ifReduce.c @@ -0,0 +1,575 @@ +/**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. Edge = %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); + pCut->Delay = If_CutDelay( p, pCut ); + 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 ( AreaBef == 1 ) +// return; + // the cut is non-trivial + If_ManImproveNodePrepare( p, pObj, nLimit, vFront, vFrontOld, vVisited ); + // iteratively modify the cut + If_CutAreaDeref( p, pCut ); + CostBef = If_ManImproveCutCost( p, vFront ); + If_ManImproveNodeFaninCompact( p, pObj, nLimit, vFront, vVisited ); + CostAft = If_ManImproveCutCost( p, vFront ); + If_CutAreaRef( p, pCut ); + 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 ( AreaAft > AreaBef || pCut->Delay > pObj->Required + p->fEpsilon ) + { + If_ManImproveNodeUpdate( p, pObj, vFrontOld ); + AreaAft = If_CutAreaRefed( p, pCut ); + 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_CutAreaDeref( p, pCut ); + // 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_CutAreaRef( p, pCut ); +} + + +/**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_CutAreaDeref( p, pCut ); + // get the area + AreaBef = If_CutAreaDerefed( p, pCut ); + // 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 ); + // 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 ); +*/ +} + +/**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 new file mode 100644 index 00000000..8d1de8c1 --- /dev/null +++ b/src/map/if/ifSeq.c @@ -0,0 +1,405 @@ +/**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 new file mode 100644 index 00000000..3d1dab1b --- /dev/null +++ b/src/map/if/ifTime.c @@ -0,0 +1,228 @@ +/**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 ) + { +/* + if ( pLeaf->IdPio > 2000 ) + { + int x = 0; + printf( "-%d %6.3f ", pLeaf->IdPio, If_ObjCutBest(pLeaf)->Delay ); + } +*/ + 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 new file mode 100644 index 00000000..f18d8308 --- /dev/null +++ b/src/map/if/ifTruth.c @@ -0,0 +1,404 @@ +/**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 /// +//////////////////////////////////////////////////////////////////////// + +static int If_CutTruthMinimize( If_Man_t * p, If_Cut_t * pCut ); + +//////////////////////////////////////////////////////////////////////// +/// 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 [Shrinks 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 what variables should remain.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void If_TruthShrink( unsigned * pOut, unsigned * pIn, int nVars, int nVarsAll, unsigned Phase, int fReturnIn ) +{ + unsigned * pTemp; + int i, k, Var = 0, Counter = 0; + for ( i = 0; i < nVarsAll; i++ ) + if ( Phase & (1 << i) ) + { + for ( k = i-1; k >= Var; k-- ) + { + If_TruthSwapAdjacentVars( pOut, pIn, nVarsAll, k ); + pTemp = pIn; pIn = pOut; pOut = pTemp; + Counter++; + } + Var++; + } + assert( Var == nVars ); + // swap if it was moved an even number of times + if ( fReturnIn ^ !(Counter & 1) ) + If_TruthCopy( pOut, pIn, nVarsAll ); +} + +/**Function************************************************************* + + Synopsis [Returns 1 if TT depends on the given variable.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutTruthVarInSupport( unsigned * pTruth, int nVars, int iVar ) +{ + int nWords = If_TruthWordNum( nVars ); + int i, k, Step; + + assert( iVar < nVars ); + switch ( iVar ) + { + case 0: + for ( i = 0; i < nWords; i++ ) + if ( (pTruth[i] & 0x55555555) != ((pTruth[i] & 0xAAAAAAAA) >> 1) ) + return 1; + return 0; + case 1: + for ( i = 0; i < nWords; i++ ) + if ( (pTruth[i] & 0x33333333) != ((pTruth[i] & 0xCCCCCCCC) >> 2) ) + return 1; + return 0; + case 2: + for ( i = 0; i < nWords; i++ ) + if ( (pTruth[i] & 0x0F0F0F0F) != ((pTruth[i] & 0xF0F0F0F0) >> 4) ) + return 1; + return 0; + case 3: + for ( i = 0; i < nWords; i++ ) + if ( (pTruth[i] & 0x00FF00FF) != ((pTruth[i] & 0xFF00FF00) >> 8) ) + return 1; + return 0; + case 4: + for ( i = 0; i < nWords; i++ ) + if ( (pTruth[i] & 0x0000FFFF) != ((pTruth[i] & 0xFFFF0000) >> 16) ) + return 1; + return 0; + default: + Step = (1 << (iVar - 5)); + for ( k = 0; k < nWords; k += 2*Step ) + { + for ( i = 0; i < Step; i++ ) + if ( pTruth[i] != pTruth[Step+i] ) + return 1; + pTruth += 2*Step; + } + return 0; + } +} + +/**Function************************************************************* + + Synopsis [Returns support of the function.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned If_CutTruthSupport( unsigned * pTruth, int nVars, int * pnSuppSize ) +{ + int i, Support = 0; + int nSuppSize = 0; + for ( i = 0; i < nVars; i++ ) + if ( If_CutTruthVarInSupport( pTruth, nVars, i ) ) + { + Support |= (1 << i); + nSuppSize++; + } + *pnSuppSize = nSuppSize; + return Support; +} + + +/**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 If_CutFactorTest( 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 ); + + // minimize the support of the cut + if ( p->pPars->fCutMin ) + If_CutTruthMinimize( p, pCut ); + + // perform +// If_CutFactorTest( If_CutTruth(pCut), pCut->nLimit ); +// printf( "%d ", If_CutLeaveNum(pCut) - If_CutTruthSupportSize(If_CutTruth(pCut), If_CutLeaveNum(pCut)) ); +} + + +/**Function************************************************************* + + Synopsis [Minimize support of the cut.] + + Description [Returns 1 if the node's support has changed] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutTruthMinimize( If_Man_t * p, If_Cut_t * pCut ) +{ + unsigned uSupport; + int nSuppSize, i, k; + // compute the support of the cut's function + uSupport = If_CutTruthSupport( If_CutTruth(pCut), If_CutLeaveNum(pCut), &nSuppSize ); + if ( nSuppSize == If_CutLeaveNum(pCut) ) + return 0; + +// TEMPORARY + if ( nSuppSize < 2 ) + { + p->nSmallSupp++; + return 0; + } +// if ( If_CutLeaveNum(pCut) - nSuppSize > 1 ) +// return 0; +//printf( "%d %d ", If_CutLeaveNum(pCut), nSuppSize ); + + // shrink the truth table + If_TruthShrink( p->puTemp[0], If_CutTruth(pCut), nSuppSize, pCut->nLimit, uSupport, 1 ); + // update leaves and signature + pCut->uSign = 0; + for ( i = k = 0; i < If_CutLeaveNum(pCut); i++ ) + { + if ( !(uSupport & (1 << i)) ) + continue; + pCut->pLeaves[k++] = pCut->pLeaves[i]; + pCut->uSign |= If_ObjCutSign( pCut->pLeaves[i] ); + } + assert( k == nSuppSize ); + pCut->nLeaves = nSuppSize; + // verify the result +// uSupport = If_CutTruthSupport( If_CutTruth(pCut), If_CutLeaveNum(pCut), &nSuppSize ); +// assert( nSuppSize == If_CutLeaveNum(pCut) ); + return 1; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/if/ifUtil.c b/src/map/if/ifUtil.c new file mode 100644 index 00000000..2624efd0 --- /dev/null +++ b/src/map/if/ifUtil.c @@ -0,0 +1,658 @@ +/**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; + float reqTime; + + // compute area, clean required times, collect nodes used in the mapping +// p->AreaGlo = If_ManScanMapping( p ); + If_ManMarkMapping( p ); + + if ( p->pManTim == NULL ) + { + // 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 ); + If_ManForEachObjReverse( p, pObj, i ) + { + if ( pObj->nRefs == 0 ) + continue; + If_CutPropagateRequired( p, If_ObjCutBest(pObj), pObj->Required ); + } + } + else + { + // get the global required times + p->RequiredGlo = If_ManDelayMax( p, 0 ); + // do not propagate required times if area minimization is requested + if ( p->pPars->fAreaOnly ) + return; + // set the required times for the POs + Tim_ManIncrementTravId( p->pManTim ); + if ( p->pPars->fLatchPaths ) + { + assert( 0 ); + If_ManForEachPo( p, pObj, i ) + Tim_ManSetPoRequired( p->pManTim, pObj->IdPio, IF_FLOAT_LARGE ); + If_ManForEachLatchInput( p, pObj, i ) + Tim_ManSetPoRequired( p->pManTim, pObj->IdPio, p->RequiredGlo ); + } + else + { + Tim_ManSetPoRequiredAll( p->pManTim, p->RequiredGlo ); +// If_ManForEachCo( p, pObj, i ) +// Tim_ManSetPoRequired( p->pManTim, pObj->IdPio, p->RequiredGlo ); + } + // go through the nodes in the reverse topological order + If_ManForEachObjReverse( p, pObj, i ) + { + if ( If_ObjIsAnd(pObj) ) + { + if ( pObj->nRefs == 0 ) + continue; + If_CutPropagateRequired( p, If_ObjCutBest(pObj), pObj->Required ); + } + else if ( If_ObjIsCi(pObj) ) + { + reqTime = pObj->Required; + Tim_ManSetPiRequired( p->pManTim, pObj->IdPio, reqTime ); + } + else if ( If_ObjIsCo(pObj) ) + { + reqTime = Tim_ManGetPoRequired( p->pManTim, pObj->IdPio ); + If_ObjFanin0(pObj)->Required = IF_MIN( reqTime, If_ObjFanin0(pObj)->Required ); + } + else if ( If_ObjIsConst1(pObj) ) + { + } + else // add the node to the mapper + assert( 0 ); + } + } +} + +#if 0 + +/**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 + p->nNets = 0; + 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 [Collects the nodes in reverse topological order in array + p->vMapping.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_ManScanMappingDirect( 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 ( i = 0; i <= p->nLevelMax; 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; +} + +#endif + +/**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 the reverse topological order of nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * If_ManReverseOrder( If_Man_t * p ) +{ + Vec_Ptr_t * vOrder; + If_Obj_t * pObj, ** ppStore; + int i; + // allocate place to store the nodes + ppStore = ALLOC( If_Obj_t *, p->nLevelMax + 1 ); + memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) ); + // add the nodes + If_ManForEachObj( p, pObj, i ) + { + assert( pObj->Level >= 0 && pObj->Level <= (unsigned)p->nLevelMax ); + pObj->pCopy = (char *)ppStore[pObj->Level]; + ppStore[pObj->Level] = pObj; + } + vOrder = Vec_PtrAlloc( If_ManObjNum(p) ); + for ( i = p->nLevelMax; i >= 0; i-- ) + for ( pObj = ppStore[i]; pObj; pObj = pObj->pCopy ) + Vec_PtrPush( vOrder, pObj ); + free( ppStore ); + // print the order +// Vec_PtrForEachEntry( vOrder, pObj, i ) +// printf( "Obj %2d Type %d Level = %d\n", pObj->Id, pObj->Type, pObj->Level ); + return vOrder; +} + +/**Function************************************************************* + + Synopsis [Computes area, references, and nodes used in the mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_ManMarkMapping_rec( If_Man_t * p, If_Obj_t * pObj ) +{ + 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) ); + // 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_ManMarkMapping_rec( p, pLeaf ); + return aArea; +} + +/**Function************************************************************* + + Synopsis [Computes area, references, and nodes used in the mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void If_ManMarkMapping( If_Man_t * p ) +{ + If_Obj_t * pObj; + int i; + If_ManForEachObj( p, pObj, i ) + { + pObj->Required = IF_FLOAT_LARGE; + pObj->nVisits = pObj->nVisitsCopy; + pObj->nRefs = 0; + } + p->nNets = 0; + p->AreaGlo = 0.0; + If_ManForEachCo( p, pObj, i ) + p->AreaGlo += If_ManMarkMapping_rec( p, If_ObjFanin0(pObj) ); +} + +/**Function************************************************************* + + Synopsis [Collects nodes used in the mapping in the topological order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * If_ManCollectMappingDirect( If_Man_t * p ) +{ + Vec_Ptr_t * vOrder; + If_Obj_t * pObj; + int i; + If_ManMarkMapping( p ); + vOrder = Vec_PtrAlloc( If_ManObjNum(p) ); + If_ManForEachObj( p, pObj, i ) + if ( If_ObjIsAnd(pObj) && pObj->nRefs ) + Vec_PtrPush( vOrder, pObj ); + return vOrder; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/if/if_.c b/src/map/if/if_.c new file mode 100644 index 00000000..d2960077 --- /dev/null +++ b/src/map/if/if_.c @@ -0,0 +1,47 @@ +/**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 new file mode 100644 index 00000000..c14428da --- /dev/null +++ b/src/map/if/module.make @@ -0,0 +1,8 @@ +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/ifTime.c \ + src/map/if/ifTruth.c \ + src/map/if/ifUtil.c diff --git a/src/map/mapper/mapper.c b/src/map/mapper/mapper.c index e59fa4a3..b18b68c0 100644 --- a/src/map/mapper/mapper.c +++ b/src/map/mapper/mapper.c @@ -28,7 +28,7 @@ static int Map_CommandReadLibrary ( Abc_Frame_t * pAbc, int argc, char **argv ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -61,7 +61,7 @@ void Map_Init( Abc_Frame_t * pAbc ) void Map_End() { // Map_SuperLibFree( s_pSuperLib ); - Map_SuperLibFree( Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()) ); + Map_SuperLibFree( Abc_FrameReadLibSuper() ); } @@ -87,7 +87,7 @@ int Map_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) int fAlgorithm; int c; - pNet = Abc_FrameReadNet(pAbc); + pNet = Abc_FrameReadNtk(pAbc); pOut = Abc_FrameReadOut(pAbc); pErr = Abc_FrameReadErr(pAbc); @@ -95,16 +95,16 @@ int Map_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) fVerbose = 1; fAlgorithm = 1; ExcludeFile = 0; - util_getopt_reset(); - while ( (c = util_getopt(argc, argv, "eovh")) != EOF ) + Extra_UtilGetoptReset(); + while ( (c = Extra_UtilGetopt(argc, argv, "eovh")) != EOF ) { switch (c) { case 'e': - ExcludeFile = argv[util_optind]; + ExcludeFile = argv[globalUtilOptind]; if ( ExcludeFile == 0 ) goto usage; - util_optind++; + globalUtilOptind++; break; case 'o': fAlgorithm ^= 1; @@ -121,15 +121,15 @@ int Map_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) } - if ( argc != util_optind + 1 ) + if ( argc != globalUtilOptind + 1 ) { goto usage; } // get the input file name - FileName = argv[util_optind]; -// if ( (pFile = Io_FileOpen( FileName, "open_path", "r" )) == NULL ) - if ( (pFile = fopen( FileName, "r" )) == NULL ) + FileName = argv[globalUtilOptind]; + if ( (pFile = Io_FileOpen( FileName, "open_path", "r", 0 )) == NULL ) +// if ( (pFile = fopen( FileName, "r" )) == NULL ) { fprintf( pErr, "Cannot open input file \"%s\". ", FileName ); if ( FileName = Extra_FileGetSimilarName( FileName, ".genlib", ".lib", ".gen", ".g", NULL ) ) diff --git a/src/map/mapper/mapper.h b/src/map/mapper/mapper.h index c3f1ce81..8eade761 100644 --- a/src/map/mapper/mapper.h +++ b/src/map/mapper/mapper.h @@ -19,6 +19,10 @@ #ifndef __MAPPER_H__ #define __MAPPER_H__ +#ifdef __cplusplus +extern "C" { +#endif + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// @@ -56,16 +60,16 @@ struct Map_TimeStruct_t_ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// -#define Map_IsComplement(p) (((int)((long) (p) & 01))) -#define Map_Regular(p) ((Map_Node_t *)((unsigned)(p) & ~01)) -#define Map_Not(p) ((Map_Node_t *)((long)(p) ^ 01)) -#define Map_NotCond(p,c) ((Map_Node_t *)((long)(p) ^ (c))) +#define Map_IsComplement(p) (((int)((unsigned long) (p) & 01))) +#define Map_Regular(p) ((Map_Node_t *)((unsigned long)(p) & ~01)) +#define Map_Not(p) ((Map_Node_t *)((unsigned long)(p) ^ 01)) +#define Map_NotCond(p,c) ((Map_Node_t *)((unsigned long)(p) ^ (c))) //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /*=== mapperCreate.c =============================================================*/ @@ -180,7 +184,12 @@ extern void Map_ManCleanData( Map_Man_t * p ); extern void Map_MappingSetupTruthTables( unsigned uTruths[][2] ); extern void Map_MappingSetupTruthTablesLarge( unsigned uTruths[][32] ); +#ifdef __cplusplus +} +#endif + +#endif + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -#endif diff --git a/src/map/mapper/mapperCanon.c b/src/map/mapper/mapperCanon.c index 2b0f261f..203c9142 100644 --- a/src/map/mapper/mapperCanon.c +++ b/src/map/mapper/mapperCanon.c @@ -26,7 +26,7 @@ static unsigned Map_CanonComputePhase( unsigned uTruths[][2], int nVars, unsigne static void Map_CanonComputePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[], unsigned uPhase, unsigned uTruthRes[] ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -218,7 +218,7 @@ int Map_CanonComputeFast( Map_Man_t * p, int nVarsMax, int nVarsReal, unsigned u if ( uCanon0 >= uCanon1 ) // using nCanon1 as the main one { assert( p->pCounters[uTruth1] > 0 ); - uCanonBest = 0xFFFF; + uCanonBest = 0xFFFFFFFF; for ( i = 0; i < p->pCounters[uTruth1]; i++ ) { uCanon0 = Extra_TruthPolarize( uTruth0, p->uPhases[uTruth1][i], 4 ); @@ -226,6 +226,7 @@ int Map_CanonComputeFast( Map_Man_t * p, int nVarsMax, int nVarsReal, unsigned u { uCanonBest = uCanon0; uPhaseBest = p->uPhases[uTruth1][i]; + assert( uPhaseBest < 16 ); } } uTruthRes[0] = (uCanon1 << 16) | uCanonBest; @@ -236,7 +237,7 @@ int Map_CanonComputeFast( Map_Man_t * p, int nVarsMax, int nVarsReal, unsigned u else if ( uCanon0 < uCanon1 ) { assert( p->pCounters[uTruth0] > 0 ); - uCanonBest = 0xFFFF; + uCanonBest = 0xFFFFFFFF; for ( i = 0; i < p->pCounters[uTruth0]; i++ ) { uCanon1 = Extra_TruthPolarize( uTruth1, p->uPhases[uTruth0][i], 4 ); @@ -244,6 +245,7 @@ int Map_CanonComputeFast( Map_Man_t * p, int nVarsMax, int nVarsReal, unsigned u { uCanonBest = uCanon1; uPhaseBest = p->uPhases[uTruth0][i]; + assert( uPhaseBest < 16 ); } } uTruthRes[0] = (uCanon0 << 16) | uCanonBest; diff --git a/src/map/mapper/mapperCore.c b/src/map/mapper/mapperCore.c index 629ba59d..5d4854e6 100644 --- a/src/map/mapper/mapperCore.c +++ b/src/map/mapper/mapperCore.c @@ -24,7 +24,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -46,7 +46,7 @@ ***********************************************************************/ int Map_Mapping( Map_Man_t * p ) { - int fShowSwitching = 0; + int fShowSwitching = 1; int fUseAreaFlow = 1; int fUseExactArea = !p->fSwitching; int fUseExactAreaWithPhase = !p->fSwitching; @@ -93,7 +93,11 @@ PRT( "Time", p->timeMatch ); ////////////////////////////////////////////////////////////////////// if ( !p->fAreaRecovery ) + { + if ( p->fVerbose ) + Map_MappingPrintOutputArrivals( p ); return 1; + } ////////////////////////////////////////////////////////////////////// // perform area recovery using area flow diff --git a/src/map/mapper/mapperCreate.c b/src/map/mapper/mapperCreate.c index 31fbf0ea..157d467b 100644 --- a/src/map/mapper/mapperCreate.c +++ b/src/map/mapper/mapperCreate.c @@ -30,7 +30,7 @@ static Map_Node_t * Map_TableLookup( Map_Man_t * p, Map_Node_t * p1, Map_Node static inline unsigned Map_HashKey2( Map_Node_t * p0, Map_Node_t * p1, int TableSize ) { return ((unsigned)(p0) + (unsigned)(p1) * 12582917) % TableSize; } //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -183,7 +183,7 @@ Map_Man_t * Map_ManCreate( int nInputs, int nOutputs, int fVerbose ) int i; // derive the supergate library - if ( Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()) == NULL ) + if ( Abc_FrameReadLibSuper() == NULL ) { printf( "The supergate library is not specified. Use \"read_library\" or \"read_super\".\n" ); return NULL; @@ -192,7 +192,7 @@ Map_Man_t * Map_ManCreate( int nInputs, int nOutputs, int fVerbose ) // start the manager p = ALLOC( Map_Man_t, 1 ); memset( p, 0, sizeof(Map_Man_t) ); - p->pSuperLib = Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()); + p->pSuperLib = Abc_FrameReadLibSuper(); p->nVarsMax = p->pSuperLib->nVarsMax; p->fVerbose = fVerbose; p->fEpsilon = (float)0.001; @@ -261,8 +261,8 @@ void Map_ManFree( Map_Man_t * p ) if ( p->uCanons ) free( p->uCanons ); if ( p->uPhases ) free( p->uPhases ); if ( p->pCounters ) free( p->pCounters ); - Extra_MmFixedStop( p->mmNodes, 0 ); - Extra_MmFixedStop( p->mmCuts, 0 ); + Extra_MmFixedStop( p->mmNodes ); + Extra_MmFixedStop( p->mmCuts ); FREE( p->pInputArrivals ); FREE( p->pInputs ); FREE( p->pOutputs ); @@ -314,7 +314,7 @@ void Map_ManPrintTimeStats( Map_Man_t * p ) void Map_ManPrintStatsToFile( char * pName, float Area, float Delay, int Time ) { FILE * pTable; - pTable = fopen( "stats.txt", "a+" ); + pTable = fopen( "map_stats.txt", "a+" ); fprintf( pTable, "%s ", pName ); fprintf( pTable, "%4.2f ", Area ); fprintf( pTable, "%4.2f ", Delay ); diff --git a/src/map/mapper/mapperCut.c b/src/map/mapper/mapperCut.c index b5ce4018..b05e9d0c 100644 --- a/src/map/mapper/mapperCut.c +++ b/src/map/mapper/mapperCut.c @@ -80,7 +80,7 @@ static unsigned Map_CutComputeTruth( Map_Man_t * p, Map_Cut_t * pCut, Ma pCut2 = pCut? pCut->pNext: NULL ) //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -149,7 +149,7 @@ void Map_MappingCuts( Map_Man_t * p ) if ( p->fVerbose ) { nCuts = Map_MappingCountAllCuts(p); - printf( "Nodes = %6d. Total %d-feasible cuts = %d. Per node = %.1f. ", + printf( "Nodes = %6d. Total %d-feasible cuts = %10d. Per node = %.1f. ", p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes ); PRT( "Time", clock() - clk ); } @@ -208,7 +208,7 @@ Map_Cut_t * Map_CutCompute( Map_Man_t * p, Map_CutTable_t * pTable, Map_Node_t * // set at the node pNode->pCuts = pCut; // remove the dominated cuts -// Map_CutFilter( p, pNode ); + Map_CutFilter( p, pNode ); // set the phase correctly if ( pNode->pRepr && Map_NodeComparePhase(pNode, pNode->pRepr) ) { @@ -612,7 +612,8 @@ int Map_CutMergeTwo( Map_Cut_t * pCut1, Map_Cut_t * pCut2, Map_Node_t * ppNodes[ { min = i; for ( k = i+1; k < nTotal; k++ ) - if ( ppNodes[k] < ppNodes[min] ) +// if ( ppNodes[k] < ppNodes[min] ) // reported bug fix (non-determinism!) + if ( ppNodes[k]->Num < ppNodes[min]->Num ) min = k; pNodeTemp = ppNodes[i]; ppNodes[i] = ppNodes[min]; diff --git a/src/map/mapper/mapperCutUtils.c b/src/map/mapper/mapperCutUtils.c index 9f572e75..4450cb04 100644 --- a/src/map/mapper/mapperCutUtils.c +++ b/src/map/mapper/mapperCutUtils.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* diff --git a/src/map/mapper/mapperFanout.c b/src/map/mapper/mapperFanout.c index aca29918..63cdbd2a 100644 --- a/src/map/mapper/mapperFanout.c +++ b/src/map/mapper/mapperFanout.c @@ -25,7 +25,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* diff --git a/src/map/mapper/mapperGENERIC.c b/src/map/mapper/mapperGENERIC.c index 4df5ee51..823eb4f2 100644 --- a/src/map/mapper/mapperGENERIC.c +++ b/src/map/mapper/mapperGENERIC.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* diff --git a/src/map/mapper/mapperInt.h b/src/map/mapper/mapperInt.h index 0acca56c..37cca3d3 100644 --- a/src/map/mapper/mapperInt.h +++ b/src/map/mapper/mapperInt.h @@ -41,7 +41,7 @@ //#define MAP_ALLOCATE_FANOUT 1 //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// // the bit masks @@ -61,10 +61,10 @@ #define MAP_RANDOM_UNSIGNED ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand())) // internal macros to work with cuts -#define Map_CutIsComplement(p) (((int)((long) (p) & 01))) -#define Map_CutRegular(p) ((Map_Cut_t *)((unsigned)(p) & ~01)) -#define Map_CutNot(p) ((Map_Cut_t *)((long)(p) ^ 01)) -#define Map_CutNotCond(p,c) ((Map_Cut_t *)((long)(p) ^ (c))) +#define Map_CutIsComplement(p) (((int)((unsigned long) (p) & 01))) +#define Map_CutRegular(p) ((Map_Cut_t *)((unsigned long)(p) & ~01)) +#define Map_CutNot(p) ((Map_Cut_t *)((unsigned long)(p) ^ 01)) +#define Map_CutNotCond(p,c) ((Map_Cut_t *)((unsigned long)(p) ^ (c))) // internal macros for referencing of nodes #define Map_NodeReadRef(p) ((Map_Regular(p))->nRefs) @@ -347,7 +347,7 @@ struct Map_HashEntryStruct_t_ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /*=== mapperCanon.c =============================================================*/ @@ -470,8 +470,8 @@ extern void Map_NodeVecWriteEntry( Map_NodeVec_t * p, int i, Map_No extern Map_Node_t * Map_NodeVecReadEntry( Map_NodeVec_t * p, int i ); extern void Map_NodeVecSortByLevel( Map_NodeVec_t * p ); +#endif + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// - -#endif diff --git a/src/map/mapper/mapperLib.c b/src/map/mapper/mapperLib.c index a9e9e29b..d916487e 100644 --- a/src/map/mapper/mapperLib.c +++ b/src/map/mapper/mapperLib.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -147,9 +147,9 @@ void Map_SuperLibFree( Map_SuperLib_t * p ) Map_SuperTableFree( p->tTableC ); if ( p->tTable ) Map_SuperTableFree( p->tTable ); - Extra_MmFixedStop( p->mmSupers, 0 ); - Extra_MmFixedStop( p->mmEntries, 0 ); - Extra_MmFlexStop( p->mmForms, 0 ); + Extra_MmFixedStop( p->mmSupers ); + Extra_MmFixedStop( p->mmEntries ); + Extra_MmFlexStop( p->mmForms ); FREE( p->ppSupers ); FREE( p ); } @@ -179,7 +179,7 @@ int Map_SuperLibDeriveFromGenlib( Mio_Library_t * pLib ) return 0; // write the current library into the file - strcpy( FileNameGenlib, Mio_LibraryReadName(pLib) ); + sprintf( FileNameGenlib, "%s_temp", Mio_LibraryReadName(pLib) ); pFile = fopen( FileNameGenlib, "w" ); Mio_WriteLibrary( pFile, pLib, 0 ); fclose( pFile ); diff --git a/src/map/mapper/mapperMatch.c b/src/map/mapper/mapperMatch.c index ddb9ebb7..bfa72601 100644 --- a/src/map/mapper/mapperMatch.c +++ b/src/map/mapper/mapperMatch.c @@ -41,7 +41,7 @@ static void Map_NodeTryDroppingOnePhase( Map_Man_t * p, Map_Node_t * pNode ); static void Map_NodeTransferArrivalTimes( Map_Man_t * p, Map_Node_t * pNode ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* diff --git a/src/map/mapper/mapperRefs.c b/src/map/mapper/mapperRefs.c index baaebfa1..a50b134a 100644 --- a/src/map/mapper/mapperRefs.c +++ b/src/map/mapper/mapperRefs.c @@ -28,7 +28,7 @@ static float Map_CutRefDeref( Map_Cut_t * pCut, int fPhase, int fReference ); static void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode, Map_Node_t ** ppStore ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -237,7 +237,7 @@ float Map_CutGetAreaRefed( Map_Cut_t * pCut, int fPhase ) float aResult, aResult2; aResult2 = Map_CutRefDeref( pCut, fPhase, 0 ); // dereference aResult = Map_CutRefDeref( pCut, fPhase, 1 ); // reference - assert( aResult == aResult2 ); +// assert( aResult == aResult2 ); return aResult; } @@ -257,7 +257,7 @@ float Map_CutGetAreaDerefed( Map_Cut_t * pCut, int fPhase ) float aResult, aResult2; aResult2 = Map_CutRefDeref( pCut, fPhase, 1 ); // reference aResult = Map_CutRefDeref( pCut, fPhase, 0 ); // dereference - assert( aResult == aResult2 ); +// assert( aResult == aResult2 ); return aResult; } diff --git a/src/map/mapper/mapperSuper.c b/src/map/mapper/mapperSuper.c index 34b1d8e6..ce6a780f 100644 --- a/src/map/mapper/mapperSuper.c +++ b/src/map/mapper/mapperSuper.c @@ -30,7 +30,7 @@ static void Map_LibraryComputeTruth_rec( Map_SuperLib_t * pLib, char * static void Map_LibraryPrintClasses( Map_SuperLib_t * p ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* diff --git a/src/map/mapper/mapperSwitch.c b/src/map/mapper/mapperSwitch.c index 13168b47..9dd6e42b 100644 --- a/src/map/mapper/mapperSwitch.c +++ b/src/map/mapper/mapperSwitch.c @@ -25,7 +25,7 @@ static float Map_SwitchCutRefDeref( Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase, int fReference ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**function************************************************************* diff --git a/src/map/mapper/mapperTable.c b/src/map/mapper/mapperTable.c index 747fe1c8..d0cb7a01 100644 --- a/src/map/mapper/mapperTable.c +++ b/src/map/mapper/mapperTable.c @@ -28,7 +28,7 @@ static void Map_SuperTableResize( Map_HashTable_t * pLib ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -325,7 +325,7 @@ void Map_SuperTableSortSupergates( Map_HashTable_t * p, int nSupersMax ) ppSupers[nSupers++] = pSuper; // sort by usage - qsort( (void *)ppSupers, nSupers, sizeof(int), + qsort( (void *)ppSupers, nSupers, sizeof(Map_Super_t *), (int (*)(const void *, const void *)) Map_SuperTableCompareSupergates ); assert( Map_SuperTableCompareSupergates( ppSupers, ppSupers + nSupers - 1 ) <= 0 ); @@ -380,7 +380,7 @@ void Map_SuperTableSortSupergatesByDelay( Map_HashTable_t * p, int nSupersMax ) if ( nSupers == 0 ) continue; // sort the gates by delay - qsort( (void *)ppSupers, nSupers, sizeof(int), + qsort( (void *)ppSupers, nSupers, sizeof(Map_Super_t *), (int (*)(const void *, const void *)) Map_SuperTableCompareGatesInList ); assert( Map_SuperTableCompareGatesInList( ppSupers, ppSupers + nSupers - 1 ) <= 0 ); // link them in the reverse order diff --git a/src/map/mapper/mapperTime.c b/src/map/mapper/mapperTime.c index f1cafae7..cc4173cf 100644 --- a/src/map/mapper/mapperTime.c +++ b/src/map/mapper/mapperTime.c @@ -27,7 +27,7 @@ static void Map_TimePropagateRequiredPhase( Map_Man_t * p, Map_Node_t * pNode, static float Map_MatchComputeReqTimes( Map_Cut_t * pCut, int fPhase, Map_Time_t * ptArrRes ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**function************************************************************* diff --git a/src/map/mapper/mapperTree.c b/src/map/mapper/mapperTree.c index 04576045..ef66082d 100644 --- a/src/map/mapper/mapperTree.c +++ b/src/map/mapper/mapperTree.c @@ -37,7 +37,7 @@ static unsigned Map_LibraryGetGateSupp_rec( Map_Super_t * pGate ); extern const int s_MapFanoutLimits[10] = { 1/*0*/, 10/*1*/, 5/*2*/, 2/*3*/, 1/*4*/, 1/*5*/, 1/*6*/ }; //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -60,8 +60,8 @@ int Map_LibraryReadTree( Map_SuperLib_t * pLib, char * pFileName, char * pExclud // read the beginning of the file assert( pLib->pGenlib == NULL ); -// pFile = Io_FileOpen( pFileName, "open_path", "r" ); - pFile = fopen( pFileName, "r" ); + pFile = Io_FileOpen( pFileName, "open_path", "r", 1 ); +// pFile = fopen( pFileName, "r" ); if ( pFile == NULL ) { printf( "Cannot open input file \"%s\".\n", pFileName ); @@ -149,8 +149,8 @@ int Map_LibraryReadFileTree( Map_SuperLib_t * pLib, FILE * pFile, char *pFileNam } #endif -// pFileGen = Io_FileOpen( pLibFile, "open_path", "r" ); - pFileGen = fopen( pLibFile, "r" ); + pFileGen = Io_FileOpen( pLibFile, "open_path", "r", 1 ); +// pFileGen = fopen( pLibFile, "r" ); if ( pFileGen == NULL ) { printf( "Cannot open the GENLIB file \"%s\".\n", pLibFile ); @@ -439,6 +439,9 @@ int Map_LibraryDeriveGateInfo( Map_SuperLib_t * pLib, st_table * tExcludeGate ) pGate->tDelayMax.Fall = pGate->tDelaysF[k].Rise; if ( pGate->tDelayMax.Fall < pGate->tDelaysF[k].Fall ) pGate->tDelayMax.Fall = pGate->tDelaysF[k].Fall; + + pGate->tDelaysF[k].Worst = MAP_MAX( pGate->tDelaysF[k].Fall, pGate->tDelaysF[k].Rise ); + pGate->tDelaysR[k].Worst = MAP_MAX( pGate->tDelaysR[k].Fall, pGate->tDelaysR[k].Rise ); } // count gates and area of the supergate diff --git a/src/map/mapper/mapperTruth.c b/src/map/mapper/mapperTruth.c index 7eabf4df..388b6dd3 100644 --- a/src/map/mapper/mapperTruth.c +++ b/src/map/mapper/mapperTruth.c @@ -27,7 +27,7 @@ extern void Map_TruthsCutOne( Map_Man_t * p, Map_Cut_t * pCut, unsigned uTruth[] static void Map_CutsCollect_rec( Map_Cut_t * pCut, Map_NodeVec_t * vVisited ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -89,14 +89,15 @@ void Map_MappingTruths( Map_Man_t * pMan ) ***********************************************************************/ void Map_TruthsCut( Map_Man_t * p, Map_Cut_t * pCut ) -{ +{ // unsigned uCanon1, uCanon2; unsigned uTruth[2], uCanon[2]; unsigned char uPhases[16]; unsigned * uCanon2; char * pPhases2; - int fUseFast = 0; - int fUseRec = 1; + int fUseFast = 1; + int fUseSlow = 0; + int fUseRec = 0; // this does not work for Solaris extern int Map_CanonCompute( int nVarsMax, int nVarsReal, unsigned * pt, unsigned ** pptRes, char ** ppfRes ); @@ -117,6 +118,8 @@ void Map_TruthsCut( Map_Man_t * p, Map_Cut_t * pCut ) // compute the canonical form for the positive phase if ( fUseFast ) Map_CanonComputeFast( p, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + else if ( fUseSlow ) + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); else if ( fUseRec ) { // Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); @@ -145,6 +148,8 @@ void Map_TruthsCut( Map_Man_t * p, Map_Cut_t * pCut ) uTruth[1] = ~uTruth[1]; if ( fUseFast ) Map_CanonComputeFast( p, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + else if ( fUseSlow ) + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); else if ( fUseRec ) { // Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); diff --git a/src/map/mapper/mapperUtils.c b/src/map/mapper/mapperUtils.c index 00f1b85b..11a3a683 100644 --- a/src/map/mapper/mapperUtils.c +++ b/src/map/mapper/mapperUtils.c @@ -40,7 +40,7 @@ static int Map_MappingCountUsedNodes( Map_Man_t * pMan, int fChoices ); static Map_Man_t * s_pMan = NULL; //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// diff --git a/src/map/mapper/mapperVec.c b/src/map/mapper/mapperVec.c index e3ab4b7f..f75138fb 100644 --- a/src/map/mapper/mapperVec.c +++ b/src/map/mapper/mapperVec.c @@ -25,7 +25,7 @@ static int Map_NodeVecCompareLevels( Map_Node_t ** pp1, Map_Node_t ** pp2 ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* diff --git a/src/map/mio/mio.c b/src/map/mio/mio.c index bb6dbba1..10a5af9d 100644 --- a/src/map/mio/mio.c +++ b/src/map/mio/mio.c @@ -55,7 +55,7 @@ static char * pMcncGenlib[25] = { }; //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -108,7 +108,7 @@ void Mio_Init( Abc_Frame_t * pAbc ) void Mio_End() { // Mio_LibraryDelete( s_pLib ); - Mio_LibraryDelete( Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) ); + Mio_LibraryDelete( Abc_FrameReadLibGen() ); } @@ -133,14 +133,14 @@ int Mio_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) int fVerbose; int c; - pNet = Abc_FrameReadNet(pAbc); + pNet = Abc_FrameReadNtk(pAbc); pOut = Abc_FrameReadOut(pAbc); pErr = Abc_FrameReadErr(pAbc); // set the defaults fVerbose = 1; - util_getopt_reset(); - while ( (c = util_getopt(argc, argv, "vh")) != EOF ) + Extra_UtilGetoptReset(); + while ( (c = Extra_UtilGetopt(argc, argv, "vh")) != EOF ) { switch (c) { @@ -156,14 +156,14 @@ int Mio_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) } - if ( argc != util_optind + 1 ) + if ( argc != globalUtilOptind + 1 ) { goto usage; } // get the input file name - FileName = argv[util_optind]; - if ( (pFile = fopen( FileName, "r" )) == NULL ) + FileName = argv[globalUtilOptind]; + if ( (pFile = Io_FileOpen( FileName, "open_path", "r", 0 )) == NULL ) { fprintf( pErr, "Cannot open input file \"%s\". ", FileName ); if ( (FileName = Extra_FileGetSimilarName( FileName, ".genlib", ".lib", ".gen", ".g", NULL )) ) @@ -181,7 +181,7 @@ int Mio_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) return 1; } // free the current superlib because it depends on the old Mio library - if ( Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()) ) + if ( Abc_FrameReadLibSuper() ) { extern void Map_SuperLibFree( Map_SuperLib_t * p ); // Map_SuperLibFree( s_pSuperLib ); @@ -223,14 +223,14 @@ int Mio_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) int fVerbose; int c; - pNet = Abc_FrameReadNet(pAbc); + pNet = Abc_FrameReadNtk(pAbc); pOut = Abc_FrameReadOut(pAbc); pErr = Abc_FrameReadErr(pAbc); // set the defaults fVerbose = 1; - util_getopt_reset(); - while ( (c = util_getopt(argc, argv, "vh")) != EOF ) + Extra_UtilGetoptReset(); + while ( (c = Extra_UtilGetopt(argc, argv, "vh")) != EOF ) { switch (c) { @@ -246,13 +246,13 @@ int Mio_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) } - if ( argc != util_optind ) + if ( argc != globalUtilOptind ) { goto usage; } // set the new network - Mio_WriteLibrary( stdout, Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()), 0 ); + Mio_WriteLibrary( stdout, Abc_FrameReadLibGen(), 0 ); return 0; usage: diff --git a/src/map/mio/mio.h b/src/map/mio/mio.h index f9f4973d..dbe2420b 100644 --- a/src/map/mio/mio.h +++ b/src/map/mio/mio.h @@ -19,6 +19,10 @@ #ifndef __MIO_H__ #define __MIO_H__ +#ifdef __cplusplus +extern "C" { +#endif + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// @@ -42,7 +46,7 @@ typedef struct Mio_PinStruct_t_ Mio_Pin_t; //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// #define Mio_LibraryForEachGate( Lib, Gate ) \ @@ -68,7 +72,7 @@ typedef struct Mio_PinStruct_t_ Mio_Pin_t; Pin2 = (Pin? Mio_PinReadNext(Pin): NULL) ) //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /*=== mioApi.c =============================================================*/ @@ -81,6 +85,7 @@ extern char * Mio_LibraryReadSopByName ( Mio_Library_t * pLib, char extern Mio_Gate_t * Mio_LibraryReadConst0 ( Mio_Library_t * pLib ); extern Mio_Gate_t * Mio_LibraryReadConst1 ( Mio_Library_t * pLib ); extern Mio_Gate_t * Mio_LibraryReadNand2 ( Mio_Library_t * pLib ); +extern Mio_Gate_t * Mio_LibraryReadAnd2 ( Mio_Library_t * pLib ); extern Mio_Gate_t * Mio_LibraryReadBuf ( Mio_Library_t * pLib ); extern Mio_Gate_t * Mio_LibraryReadInv ( Mio_Library_t * pLib ); extern float Mio_LibraryReadDelayInvRise( Mio_Library_t * pLib ); @@ -89,9 +94,11 @@ extern float Mio_LibraryReadDelayInvMax( Mio_Library_t * pLib ); extern float Mio_LibraryReadDelayNand2Rise( Mio_Library_t * pLib ); extern float Mio_LibraryReadDelayNand2Fall( Mio_Library_t * pLib ); extern float Mio_LibraryReadDelayNand2Max( Mio_Library_t * pLib ); +extern float Mio_LibraryReadDelayAnd2Max( Mio_Library_t * pLib ); extern float Mio_LibraryReadAreaInv ( Mio_Library_t * pLib ); extern float Mio_LibraryReadAreaBuf ( Mio_Library_t * pLib ); extern float Mio_LibraryReadAreaNand2 ( Mio_Library_t * pLib ); +extern int Mio_LibraryReadGateNameMax( Mio_Library_t * pLib ); extern char * Mio_GateReadName ( Mio_Gate_t * pGate ); extern char * Mio_GateReadOutName ( Mio_Gate_t * pGate ); extern double Mio_GateReadArea ( Mio_Gate_t * pGate ); @@ -114,8 +121,8 @@ extern double Mio_PinReadDelayFanoutFall( Mio_Pin_t * pPin ); extern double Mio_PinReadDelayBlockMax ( Mio_Pin_t * pPin ); extern Mio_Pin_t * Mio_PinReadNext ( Mio_Pin_t * pPin ); /*=== mioRead.c =============================================================*/ -extern Mio_Library_t * Mio_LibraryRead( Abc_Frame_t * pAbc, char * FileName, char * ExcludeFile, int fVerbose ); -extern int Mio_LibraryReadExclude( Abc_Frame_t * pAbc, char * ExcludeFile, st_table * tExcludeGate ); +extern Mio_Library_t * Mio_LibraryRead( void * pAbc, char * FileName, char * ExcludeFile, int fVerbose ); +extern int Mio_LibraryReadExclude( void * pAbc, char * ExcludeFile, st_table * tExcludeGate ); /*=== mioFunc.c =============================================================*/ extern int Mio_LibraryParseFormulas( Mio_Library_t * pLib ); /*=== mioUtils.c =============================================================*/ @@ -131,7 +138,13 @@ extern void Mio_DeriveGateDelays( Mio_Gate_t * pGate, float * ptDelaysRes, float * ptPinDelayMax ); extern Mio_Gate_t * Mio_GateCreatePseudo( int nInputs ); +#ifdef __cplusplus +} +#endif + +#endif + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -#endif + diff --git a/src/map/mio/mioApi.c b/src/map/mio/mioApi.c index a39c6288..73473f8b 100644 --- a/src/map/mio/mioApi.c +++ b/src/map/mio/mioApi.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -43,21 +43,47 @@ Mio_Gate_t * Mio_LibraryReadGates ( Mio_Library_t * pLib ) { retur DdManager * Mio_LibraryReadDd ( Mio_Library_t * pLib ) { return pLib->dd; } Mio_Gate_t * Mio_LibraryReadBuf ( Mio_Library_t * pLib ) { return pLib->pGateBuf; } Mio_Gate_t * Mio_LibraryReadInv ( Mio_Library_t * pLib ) { return pLib->pGateInv; } -Mio_Gate_t * Mio_LibraryReadConst0 ( Mio_Library_t * pLib ) { return pLib->pGate0; } -Mio_Gate_t * Mio_LibraryReadConst1 ( Mio_Library_t * pLib ) { return pLib->pGate1; } +Mio_Gate_t * Mio_LibraryReadConst0 ( Mio_Library_t * pLib ) { return pLib->pGate0; } +Mio_Gate_t * Mio_LibraryReadConst1 ( Mio_Library_t * pLib ) { return pLib->pGate1; } Mio_Gate_t * Mio_LibraryReadNand2 ( Mio_Library_t * pLib ) { return pLib->pGateNand2; } +Mio_Gate_t * Mio_LibraryReadAnd2 ( Mio_Library_t * pLib ) { return pLib->pGateAnd2; } float Mio_LibraryReadDelayInvRise ( Mio_Library_t * pLib ) { return (float)(pLib->pGateInv? pLib->pGateInv->pPins->dDelayBlockRise : 0.0); } float Mio_LibraryReadDelayInvFall ( Mio_Library_t * pLib ) { return (float)(pLib->pGateInv? pLib->pGateInv->pPins->dDelayBlockFall : 0.0); } float Mio_LibraryReadDelayInvMax ( Mio_Library_t * pLib ) { return (float)(pLib->pGateInv? pLib->pGateInv->pPins->dDelayBlockMax : 0.0); } float Mio_LibraryReadDelayNand2Rise( Mio_Library_t * pLib ) { return (float)(pLib->pGateNand2? pLib->pGateNand2->pPins->dDelayBlockRise : 0.0); } float Mio_LibraryReadDelayNand2Fall( Mio_Library_t * pLib ) { return (float)(pLib->pGateNand2? pLib->pGateNand2->pPins->dDelayBlockFall : 0.0); } float Mio_LibraryReadDelayNand2Max ( Mio_Library_t * pLib ) { return (float)(pLib->pGateNand2? pLib->pGateNand2->pPins->dDelayBlockMax : 0.0); } +float Mio_LibraryReadDelayAnd2Max ( Mio_Library_t * pLib ) { return (float)(pLib->pGateAnd2? pLib->pGateAnd2->pPins->dDelayBlockMax : 0.0); } float Mio_LibraryReadAreaInv ( Mio_Library_t * pLib ) { return (float)(pLib->pGateInv? pLib->pGateInv->dArea : 0.0); } float Mio_LibraryReadAreaBuf ( Mio_Library_t * pLib ) { return (float)(pLib->pGateBuf? pLib->pGateBuf->dArea : 0.0); } float Mio_LibraryReadAreaNand2 ( Mio_Library_t * pLib ) { return (float)(pLib->pGateNand2? pLib->pGateNand2->dArea : 0.0); } /**Function************************************************************* + Synopsis [Returns the longest gate name.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Mio_LibraryReadGateNameMax( Mio_Library_t * pLib ) +{ + Mio_Gate_t * pGate; + int LenMax = 0, LenCur; + Mio_LibraryForEachGate( pLib, pGate ) + { + LenCur = strlen( Mio_GateReadName(pGate) ); + if ( LenMax < LenCur ) + LenMax = LenCur; + } + return LenMax; +} + +/**Function************************************************************* + Synopsis [Read Mvc of the gate by name.] Description [] diff --git a/src/map/mio/mioFunc.c b/src/map/mio/mioFunc.c index 24b2fecb..21a078f9 100644 --- a/src/map/mio/mioFunc.c +++ b/src/map/mio/mioFunc.c @@ -35,7 +35,7 @@ static int Mio_GateParseFormula( Mio_Gate_t * pGate ); static int Mio_GateCollectNames( char * pFormula, char * pPinNames[] ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -213,7 +213,7 @@ int Mio_GateParseFormula( Mio_Gate_t * pGate ) Cudd_Ref( pGate->bFunc ); // derive the cover (SOP) - pGate->pSop = Abc_ConvertBddToSop( pGate->pLib->pMmFlex, dd, pGate->bFunc, pGate->bFunc, nPins, pGate->pLib->vCube, -1 ); + pGate->pSop = Abc_ConvertBddToSop( pGate->pLib->pMmFlex, dd, pGate->bFunc, pGate->bFunc, nPins, 0, pGate->pLib->vCube, -1 ); return 0; } @@ -253,7 +253,7 @@ int Mio_GateCollectNames( char * pFormula, char * pPinNames[] ) break; if ( i == nPins ) { // cannot find this name; save it - pPinNames[nPins++] = util_strsav(pTemp); + pPinNames[nPins++] = Extra_UtilStrsav(pTemp); } // get the next name pTemp = strtok( NULL, " " ); diff --git a/src/map/mio/mioGENERIC.c b/src/map/mio/mioGENERIC.c index 6a40bc52..972c4ffc 100644 --- a/src/map/mio/mioGENERIC.c +++ b/src/map/mio/mioGENERIC.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* diff --git a/src/map/mio/mioInt.h b/src/map/mio/mioInt.h index 105e3d8d..3f90b625 100644 --- a/src/map/mio/mioInt.h +++ b/src/map/mio/mioInt.h @@ -60,6 +60,7 @@ struct Mio_LibraryStruct_t_ Mio_Gate_t * pGateBuf; // the buffer Mio_Gate_t * pGateInv; // the inverter Mio_Gate_t * pGateNand2; // the NAND2 gate + Mio_Gate_t * pGateAnd2; // the AND2 gate st_table * tName2Gate; // the mapping of gate names into their pointer DdManager * dd; // the nanager storing functions of gates Extra_MmFlex_t * pMmFlex; // the memory manaqer for SOPs @@ -106,19 +107,19 @@ struct Mio_PinStruct_t_ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /*=== mio.c =============================================================*/ /*=== mioRead.c =============================================================*/ /*=== mioUtils.c =============================================================*/ +#endif + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// - -#endif diff --git a/src/map/mio/mioRead.c b/src/map/mio/mioRead.c index f2778ca4..13c2cdcd 100644 --- a/src/map/mio/mioRead.c +++ b/src/map/mio/mioRead.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// static Mio_Library_t * Mio_LibraryReadOne( Abc_Frame_t * pAbc, char * FileName, bool fExtendedFormat, st_table * tExcludeGate, int fVerbose ); @@ -49,7 +49,7 @@ extern int isspace( int c ); // to silence the warning in VS SeeAlso [] ***********************************************************************/ -Mio_Library_t * Mio_LibraryRead( Abc_Frame_t * pAbc, char * FileName, char * ExcludeFile, int fVerbose ) +Mio_Library_t * Mio_LibraryRead( void * pAbc, char * FileName, char * ExcludeFile, int fVerbose ) { Mio_Library_t * pLib; int num; @@ -99,7 +99,7 @@ Mio_Library_t * Mio_LibraryReadOne( Abc_Frame_t * pAbc, char * FileName, bool fE // allocate the genlib structure pLib = ALLOC( Mio_Library_t, 1 ); memset( pLib, 0, sizeof(Mio_Library_t) ); - pLib->pName = util_strsav( FileName ); + pLib->pName = Extra_UtilStrsav( FileName ); pLib->tName2Gate = st_init_table(strcmp, st_strhash); pLib->pMmFlex = Extra_MmFlexStart(); pLib->vCube = Vec_StrAlloc( 100 ); @@ -114,8 +114,8 @@ Mio_Library_t * Mio_LibraryReadOne( Abc_Frame_t * pAbc, char * FileName, bool fE int nFileSize; // open the BLIF file for binary reading -// pFile = Io_FileOpen( FileName, "open_path", "rb" ); - pFile = fopen( FileName, "rb" ); + pFile = Io_FileOpen( FileName, "open_path", "rb", 1 ); +// pFile = fopen( FileName, "rb" ); // if we got this far, file should be okay otherwise would // have been detected by caller assert ( pFile != NULL ); @@ -251,7 +251,7 @@ Mio_Gate_t * Mio_LibraryReadGate( char ** ppToken, bool fExtendedFormat ) // read the name pToken = strtok( NULL, " \t\r\n" ); - pGate->pName = util_strsav( pToken ); + pGate->pName = Extra_UtilStrsav( pToken ); // read the area pToken = strtok( NULL, " \t\r\n" ); @@ -265,7 +265,7 @@ Mio_Gate_t * Mio_LibraryReadGate( char ** ppToken, bool fExtendedFormat ) // then rest of the expression pToken = strtok( NULL, ";" ); - pGate->pForm = util_strsav( pToken ); + pGate->pForm = Extra_UtilStrsav( pToken ); // read the pin info // start the linked list of pins @@ -319,7 +319,7 @@ Mio_Pin_t * Mio_LibraryReadPin( char ** ppToken, bool fExtendedFormat ) // read the name pToken = strtok( NULL, " \t\r\n" ); - pPin->pName = util_strsav( pToken ); + pPin->pName = Extra_UtilStrsav( pToken ); // read the pin phase pToken = strtok( NULL, " \t\r\n" ); @@ -418,12 +418,14 @@ char *chomp( char *s ) void Mio_LibraryDetectSpecialGates( Mio_Library_t * pLib ) { Mio_Gate_t * pGate; - DdNode * bFuncBuf, * bFuncInv, * bFuncNand2; + DdNode * bFuncBuf, * bFuncInv, * bFuncNand2, * bFuncAnd2; bFuncBuf = pLib->dd->vars[0]; Cudd_Ref( bFuncBuf ); bFuncInv = Cudd_Not( pLib->dd->vars[0] ); Cudd_Ref( bFuncInv ); bFuncNand2 = Cudd_bddNand( pLib->dd, pLib->dd->vars[0], pLib->dd->vars[1] ); Cudd_Ref( bFuncNand2 ); + bFuncAnd2 = Cudd_bddAnd( pLib->dd, pLib->dd->vars[0], pLib->dd->vars[1] ); Cudd_Ref( bFuncAnd2 ); + // get buffer Mio_LibraryForEachGate( pLib, pGate ) if ( pLib->pGateBuf == NULL && pGate->bFunc == bFuncBuf ) { @@ -435,7 +437,8 @@ void Mio_LibraryDetectSpecialGates( Mio_Library_t * pLib ) printf( "Warnings: GENLIB library reader cannot detect the buffer gate.\n" ); printf( "Some parts of the supergate-based technology mapper may not work correctly.\n" ); } - + + // get inverter Mio_LibraryForEachGate( pLib, pGate ) if ( pLib->pGateInv == NULL && pGate->bFunc == bFuncInv ) { @@ -448,20 +451,28 @@ void Mio_LibraryDetectSpecialGates( Mio_Library_t * pLib ) printf( "Some parts of the supergate-based technology mapper may not work correctly.\n" ); } + // get the NAND2 and AND2 gates Mio_LibraryForEachGate( pLib, pGate ) if ( pLib->pGateNand2 == NULL && pGate->bFunc == bFuncNand2 ) { pLib->pGateNand2 = pGate; break; } - if ( pLib->pGateNand2 == NULL ) + Mio_LibraryForEachGate( pLib, pGate ) + if ( pLib->pGateAnd2 == NULL && pGate->bFunc == bFuncAnd2 ) + { + pLib->pGateAnd2 = pGate; + break; + } + if ( pLib->pGateAnd2 == NULL && pLib->pGateNand2 == NULL ) { - printf( "Warnings: GENLIB library reader cannot detect the NAND2 gate.\n" ); + printf( "Warnings: GENLIB library reader cannot detect the AND2 or NAND2 gate.\n" ); printf( "Some parts of the supergate-based technology mapper may not work correctly.\n" ); } Cudd_RecursiveDeref( pLib->dd, bFuncInv ); Cudd_RecursiveDeref( pLib->dd, bFuncNand2 ); + Cudd_RecursiveDeref( pLib->dd, bFuncAnd2 ); } /**Function************************************************************* @@ -475,7 +486,7 @@ void Mio_LibraryDetectSpecialGates( Mio_Library_t * pLib ) SeeAlso [] ***********************************************************************/ -int Mio_LibraryReadExclude( Abc_Frame_t * pAbc, char * ExcludeFile, st_table * tExcludeGate ) +int Mio_LibraryReadExclude( void * pAbc, char * ExcludeFile, st_table * tExcludeGate ) { int nDel = 0; FILE *pEx; @@ -496,7 +507,7 @@ int Mio_LibraryReadExclude( Abc_Frame_t * pAbc, char * ExcludeFile, st_table * t while (1 == fscanf( pEx, "%127s", buffer )) { //printf ("Read: '%s'\n", buffer ); - st_insert( tExcludeGate, util_strsav( buffer ), (char *)0 ); + st_insert( tExcludeGate, Extra_UtilStrsav( buffer ), (char *)0 ); nDel++; } diff --git a/src/map/mio/mioUtils.c b/src/map/mio/mioUtils.c index 15f32890..bd3d01f7 100644 --- a/src/map/mio/mioUtils.c +++ b/src/map/mio/mioUtils.c @@ -28,7 +28,7 @@ static int Mio_DelayCompare( Mio_Gate_t ** ppG1, Mio_Gate_t ** ppG2 ); static void Mio_DeriveTruthTable_rec( DdNode * bFunc, unsigned uTruthsIn[][2], unsigned uTruthRes[] ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -53,7 +53,7 @@ void Mio_LibraryDelete( Mio_Library_t * pLib ) FREE( pLib->pName ); Mio_LibraryForEachGateSafe( pLib, pGate, pGate2 ) Mio_GateDelete( pGate ); - Extra_MmFlexStop( pLib->pMmFlex, 0 ); + Extra_MmFlexStop( pLib->pMmFlex ); Vec_StrFree( pLib->vCube ); if ( pLib->tName2Gate ) st_free_table( pLib->tName2Gate ); @@ -120,7 +120,7 @@ Mio_Pin_t * Mio_PinDup( Mio_Pin_t * pPin ) pPinNew = ALLOC( Mio_Pin_t, 1 ); *pPinNew = *pPin; - pPinNew->pName = (pPinNew->pName ? util_strsav(pPinNew->pName) : NULL); + pPinNew->pName = (pPinNew->pName ? Extra_UtilStrsav(pPinNew->pName) : NULL); pPinNew->pNext = NULL; return pPinNew; @@ -165,9 +165,9 @@ void Mio_WriteGate( FILE * pFile, Mio_Gate_t * pGate, int fPrintSops ) Mio_Pin_t * pPin; fprintf( pFile, "GATE " ); - fprintf( pFile, "%12s ", pGate->pName ); + fprintf( pFile, "%12s ", pGate->pName ); fprintf( pFile, "%10.2f ", pGate->dArea ); - fprintf( pFile, "O=%s;\n", pGate->pForm ); + fprintf( pFile, "%s=%s;\n", pGate->pOutName, pGate->pForm ); // print the pins if ( fPrintSops ) fprintf( pFile, "%s", pGate->pSop? pGate->pSop : "unspecified\n" ); diff --git a/src/map/super/super.c b/src/map/super/super.c index ffb432d5..97420c5c 100644 --- a/src/map/super/super.c +++ b/src/map/super/super.c @@ -28,7 +28,7 @@ static int Super_CommandSupergates ( Abc_Frame_t * pAbc, int argc, char **argv static int Super_CommandSupergatesAnd( Abc_Frame_t * pAbc, int argc, char **argv ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -90,20 +90,20 @@ int Super_CommandSupergatesAnd( Abc_Frame_t * pAbc, int argc, char **argv ) nVarsMax = 4; nLevels = 3; fVerbose = 0; - util_getopt_reset(); - while ( (c = util_getopt(argc, argv, "ilvh")) != EOF ) + Extra_UtilGetoptReset(); + while ( (c = Extra_UtilGetopt(argc, argv, "ilvh")) != EOF ) { switch (c) { case 'i': - nVarsMax = atoi(argv[util_optind]); - util_optind++; + nVarsMax = atoi(argv[globalUtilOptind]); + globalUtilOptind++; if ( nVarsMax < 0 ) goto usage; break; case 'l': - nLevels = atoi(argv[util_optind]); - util_optind++; + nLevels = atoi(argv[globalUtilOptind]); + globalUtilOptind++; if ( nLevels < 0 ) goto usage; break; @@ -172,44 +172,44 @@ int Super_CommandSupergates( Abc_Frame_t * pAbc, int argc, char **argv ) fWriteOldFormat = 0; ExcludeFile = 0; - util_getopt_reset(); - while ( (c = util_getopt(argc, argv, "eiltdasovh")) != EOF ) + Extra_UtilGetoptReset(); + while ( (c = Extra_UtilGetopt(argc, argv, "eiltdasovh")) != EOF ) { switch (c) { case 'e': - ExcludeFile = argv[util_optind]; + ExcludeFile = argv[globalUtilOptind]; if ( ExcludeFile == 0 ) goto usage; - util_optind++; + globalUtilOptind++; break; case 'i': - nVarsMax = atoi(argv[util_optind]); - util_optind++; + nVarsMax = atoi(argv[globalUtilOptind]); + globalUtilOptind++; if ( nVarsMax < 0 ) goto usage; break; case 'l': - nLevels = atoi(argv[util_optind]); - util_optind++; + nLevels = atoi(argv[globalUtilOptind]); + globalUtilOptind++; if ( nLevels < 0 ) goto usage; break; case 't': - TimeLimit = atoi(argv[util_optind]); - util_optind++; + TimeLimit = atoi(argv[globalUtilOptind]); + globalUtilOptind++; if ( TimeLimit < 0 ) goto usage; break; case 'd': - DelayLimit = (float)atof(argv[util_optind]); - util_optind++; + DelayLimit = (float)atof(argv[globalUtilOptind]); + globalUtilOptind++; if ( DelayLimit <= 0.0 ) goto usage; break; case 'a': - AreaLimit = (float)atof(argv[util_optind]); - util_optind++; + AreaLimit = (float)atof(argv[globalUtilOptind]); + globalUtilOptind++; if ( AreaLimit <= 0.0 ) goto usage; break; @@ -231,7 +231,7 @@ int Super_CommandSupergates( Abc_Frame_t * pAbc, int argc, char **argv ) } - if ( argc != util_optind + 1 ) + if ( argc != globalUtilOptind + 1 ) { fprintf( pErr, "The GENLIB library file should be given on the command line.\n" ); goto usage; @@ -244,9 +244,9 @@ int Super_CommandSupergates( Abc_Frame_t * pAbc, int argc, char **argv ) } // get the input file name - FileName = argv[util_optind]; -// if ( (pFile = Io_FileOpen( FileName, "open_path", "r" )) == NULL ) - if ( (pFile = fopen( FileName, "r" )) == NULL ) + FileName = argv[globalUtilOptind]; + if ( (pFile = Io_FileOpen( FileName, "open_path", "r", 0 )) == NULL ) +// if ( (pFile = fopen( FileName, "r" )) == NULL ) { fprintf( pErr, "Cannot open input file \"%s\". ", FileName ); if (( FileName = Extra_FileGetSimilarName( FileName, ".genlib", ".lib", ".gen", ".g", NULL ) )) diff --git a/src/map/super/super.h b/src/map/super/super.h index ce2b7433..a7169924 100644 --- a/src/map/super/super.h +++ b/src/map/super/super.h @@ -19,6 +19,10 @@ #ifndef __SUPER_H__ #define __SUPER_H__ +#ifdef __cplusplus +extern "C" { +#endif + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// @@ -36,16 +40,21 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /*=== superCore.c =============================================================*/ + +#ifdef __cplusplus +} +#endif + +#endif //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -#endif diff --git a/src/map/super/superAnd.c b/src/map/super/superAnd.c index e90fc76d..52473fba 100644 --- a/src/map/super/superAnd.c +++ b/src/map/super/superAnd.c @@ -61,10 +61,10 @@ struct Super2_GateStruct_t_ // manipulation of complemented attributes -#define Super2_IsComplement(p) (((int)((long) (p) & 01))) -#define Super2_Regular(p) ((Super2_Gate_t *)((unsigned)(p) & ~01)) -#define Super2_Not(p) ((Super2_Gate_t *)((long)(p) ^ 01)) -#define Super2_NotCond(p,c) ((Super2_Gate_t *)((long)(p) ^ (c))) +#define Super2_IsComplement(p) (((int)((unsigned long) (p) & 01))) +#define Super2_Regular(p) ((Super2_Gate_t *)((unsigned long)(p) & ~01)) +#define Super2_Not(p) ((Super2_Gate_t *)((unsigned long)(p) ^ 01)) +#define Super2_NotCond(p,c) ((Super2_Gate_t *)((unsigned long)(p) ^ (c))) // iterating through the gates in the library #define Super2_LibForEachGate( Lib, Gate ) \ @@ -93,7 +93,7 @@ static int Super2_LibWriteCompare( char * pStr1, char * pStr2 ); static int Super2_LibCompareGates( Super2_Gate_t ** ppG1, Super2_Gate_t ** ppG2 ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -183,7 +183,7 @@ Super2_Man_t * Super2_ManStart() ***********************************************************************/ void Super2_ManStop( Super2_Man_t * pMan ) { - Extra_MmFixedStop( pMan->pMem, 0 ); + Extra_MmFixedStop( pMan->pMem ); stmm_free_table( pMan->tTable ); free( pMan ); } diff --git a/src/map/super/superGENERIC.c b/src/map/super/superGENERIC.c index 4c7b67ca..1f2b7651 100644 --- a/src/map/super/superGENERIC.c +++ b/src/map/super/superGENERIC.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* diff --git a/src/map/super/superGate.c b/src/map/super/superGate.c index d0cd0ad7..91a1e513 100644 --- a/src/map/super/superGate.c +++ b/src/map/super/superGate.c @@ -120,7 +120,7 @@ static void Super_WriteLibraryTree( Super_Man_t * pMan ); static void Super_WriteLibraryTree_rec( FILE * pFile, Super_Man_t * pMan, Super_Gate_t * pSuper, int * pCounter ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -886,7 +886,7 @@ Super_Man_t * Super_ManStart() ***********************************************************************/ void Super_ManStop( Super_Man_t * pMan ) { - Extra_MmFixedStop( pMan->pMem, 0 ); + Extra_MmFixedStop( pMan->pMem ); if ( pMan->tTable ) stmm_free_table( pMan->tTable ); FREE( pMan->pGates ); free( pMan ); diff --git a/src/map/super/superInt.h b/src/map/super/superInt.h index 686c8739..ec6d0a38 100644 --- a/src/map/super/superInt.h +++ b/src/map/super/superInt.h @@ -43,11 +43,11 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /*=== superAnd.c =============================================================*/ @@ -55,8 +55,8 @@ extern void Super2_Precompute( int nInputs, int nLevels, int fVerbose ); /*=== superGate.c =============================================================*/ extern void Super_Precompute( Mio_Library_t * pLibGen, int nInputs, int nLevels, float tDelayMax, float tAreaMax, int TimeLimit, bool fSkipInv, bool fWriteOldFormat, int fVerbose ); +#endif + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// - -#endif diff --git a/src/map/super/superWrite.c b/src/map/super/superWrite.c index a0e85604..395ef145 100644 --- a/src/map/super/superWrite.c +++ b/src/map/super/superWrite.c @@ -53,7 +53,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* |