diff options
Diffstat (limited to 'abc70930/src/map/fpga')
| -rw-r--r-- | abc70930/src/map/fpga/fpga.c | 283 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpga.h | 172 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaCore.c | 188 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaCreate.c | 580 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaCut.c | 1159 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaCutUtils.c | 470 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaFanout.c | 141 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaGENERIC.c | 46 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaInt.h | 388 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaLib.c | 249 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaMatch.c | 794 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaSwitch.c | 151 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaTime.c | 262 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaTruth.c | 166 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaUtils.c | 986 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/fpgaVec.c | 408 | ||||
| -rw-r--r-- | abc70930/src/map/fpga/module.make | 13 |
17 files changed, 0 insertions, 6456 deletions
diff --git a/abc70930/src/map/fpga/fpga.c b/abc70930/src/map/fpga/fpga.c deleted file mode 100644 index 40423f4f..00000000 --- a/abc70930/src/map/fpga/fpga.c +++ /dev/null @@ -1,283 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpga.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Command file for the FPGA package.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpga.c,v 1.4 2004/10/28 17:36:07 alanmi Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" -#include "main.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -static int Fpga_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ); -static int Fpga_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ); - -// the library file format should be as follows: -/* -# The area/delay of k-variable LUTs: -# k area delay -1 1 1 -2 2 2 -3 4 3 -4 8 4 -5 16 5 -6 32 6 -*/ - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Package initialization procedure.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_Init( Abc_Frame_t * pAbc ) -{ - // set the default library - //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 ); - Cmd_CommandAdd( pAbc, "FPGA mapping", "print_lut", Fpga_CommandPrintLibrary, 0 ); -} - -/**Function************************************************************* - - Synopsis [Package ending procedure.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_End() -{ - Fpga_LutLibFree( Abc_FrameReadLibLut() ); -} - - -/**Function************************************************************* - - Synopsis [Command procedure to read LUT libraries.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) -{ - FILE * pFile; - FILE * pOut, * pErr; - Fpga_LutLib_t * pLib; - Abc_Ntk_t * pNet; - char * FileName; - int fVerbose; - int c; - - pNet = Abc_FrameReadNtk(pAbc); - pOut = Abc_FrameReadOut(pAbc); - pErr = Abc_FrameReadErr(pAbc); - - // set the defaults - fVerbose = 1; - Extra_UtilGetoptReset(); - while ( (c = Extra_UtilGetopt(argc, argv, "vh")) != EOF ) - { - switch (c) - { - case 'v': - fVerbose ^= 1; - break; - case 'h': - goto usage; - break; - default: - goto usage; - } - } - - - if ( argc != globalUtilOptind + 1 ) - { - goto usage; - } - - // get the input file name - FileName = argv[globalUtilOptind]; - if ( (pFile = fopen( FileName, "r" )) == NULL ) - { - fprintf( pErr, "Cannot open input file \"%s\". ", FileName ); - if ( FileName = Extra_FileGetSimilarName( FileName, ".genlib", ".lib", ".gen", ".g", NULL ) ) - fprintf( pErr, "Did you mean \"%s\"?", FileName ); - fprintf( pErr, "\n" ); - return 1; - } - fclose( pFile ); - - // set the new network - pLib = Fpga_LutLibCreate( FileName, fVerbose ); - if ( pLib == NULL ) - { - fprintf( pErr, "Reading LUT library has failed.\n" ); - goto usage; - } - // replace the current library - Fpga_LutLibFree( Abc_FrameReadLibLut() ); - Abc_FrameSetLibLut( pLib ); - return 0; - -usage: - fprintf( pErr, "\nusage: read_lut [-vh]\n"); - fprintf( pErr, "\t read the LUT library from the file\n" ); - fprintf( pErr, "\t-v : toggles enabling of verbose output [default = %s]\n", (fVerbose? "yes" : "no") ); - fprintf( pErr, "\t-h : print the command usage\n"); - fprintf( pErr, "\t \n"); - fprintf( pErr, "\t File format for a LUT library:\n"); - fprintf( pErr, "\t (the default library is shown)\n"); - fprintf( pErr, "\t \n"); - fprintf( pErr, "\t # The area/delay of k-variable LUTs:\n"); - fprintf( pErr, "\t # k area delay\n"); - fprintf( pErr, "\t 1 1 1\n"); - fprintf( pErr, "\t 2 2 2\n"); - fprintf( pErr, "\t 3 4 3\n"); - fprintf( pErr, "\t 4 8 4\n"); - fprintf( pErr, "\t 5 16 5\n"); - fprintf( pErr, "\t 6 32 6\n"); - return 1; /* error exit */ -} - -/**Function************************************************************* - - Synopsis [Command procedure to read LUT libraries.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) -{ - FILE * pOut, * pErr; - Abc_Ntk_t * pNet; - int fVerbose; - int c; - - pNet = Abc_FrameReadNtk(pAbc); - pOut = Abc_FrameReadOut(pAbc); - pErr = Abc_FrameReadErr(pAbc); - - // set the defaults - fVerbose = 1; - Extra_UtilGetoptReset(); - while ( (c = Extra_UtilGetopt(argc, argv, "vh")) != EOF ) - { - switch (c) - { - case 'v': - fVerbose ^= 1; - break; - case 'h': - goto usage; - break; - default: - goto usage; - } - } - - - if ( argc != globalUtilOptind ) - { - goto usage; - } - - // set the new network - Fpga_LutLibPrint( Abc_FrameReadLibLut() ); - return 0; - -usage: - fprintf( pErr, "\nusage: read_print [-vh]\n"); - fprintf( pErr, "\t print the current LUT library\n" ); - fprintf( pErr, "\t-v : toggles enabling of verbose output [default = %s]\n", (fVerbose? "yes" : "no") ); - fprintf( pErr, "\t-h : print the command usage\n"); - 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/abc70930/src/map/fpga/fpga.h b/abc70930/src/map/fpga/fpga.h deleted file mode 100644 index 188420b1..00000000 --- a/abc70930/src/map/fpga/fpga.h +++ /dev/null @@ -1,172 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpga.h] - - PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] - - Synopsis [Technology mapping for variable-size-LUT FPGAs.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpga.h,v 1.7 2004/09/30 21:18:09 satrajit Exp $] - -***********************************************************************/ - -#ifndef __FPGA_H__ -#define __FPGA_H__ - -#ifdef __cplusplus -extern "C" { -#endif - -//////////////////////////////////////////////////////////////////////// -/// INCLUDES /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// PARAMETERS /// -//////////////////////////////////////////////////////////////////////// - -// the maximum size of LUTs used for mapping -#define FPGA_MAX_LUTSIZE 32 - -//////////////////////////////////////////////////////////////////////// -/// STRUCTURE DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -typedef struct Fpga_ManStruct_t_ Fpga_Man_t; -typedef struct Fpga_NodeStruct_t_ Fpga_Node_t; -typedef struct Fpga_NodeVecStruct_t_ Fpga_NodeVec_t; -typedef struct Fpga_CutStruct_t_ Fpga_Cut_t; -typedef struct Fpga_LutLibStruct_t_ Fpga_LutLib_t; - -//////////////////////////////////////////////////////////////////////// -/// GLOBAL VARIABLES /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// MACRO DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -#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 DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/*=== fpgaCreate.c =============================================================*/ -extern Fpga_Man_t * Fpga_ManCreate( int nInputs, int nOutputs, int fVerbose ); -extern Fpga_Node_t * Fpga_NodeCreate( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ); -extern void Fpga_ManFree( Fpga_Man_t * pMan ); -extern void Fpga_ManPrintTimeStats( Fpga_Man_t * p ); - -extern int Fpga_ManReadInputNum( Fpga_Man_t * p ); -extern int Fpga_ManReadOutputNum( Fpga_Man_t * p ); -extern Fpga_Node_t ** Fpga_ManReadInputs ( Fpga_Man_t * p ); -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 float * Fpga_ManReadLutAreas( 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 ); -extern void Fpga_ManSetOutputNames( Fpga_Man_t * p, char ** ppNames ); -extern void Fpga_ManSetInputArrivals( Fpga_Man_t * p, float * pArrivals ); -extern void Fpga_ManSetAreaRecovery( Fpga_Man_t * p, int fAreaRecovery ); -extern void Fpga_ManSetDelayLimit( Fpga_Man_t * p, float DelayLimit ); -extern void Fpga_ManSetAreaLimit( Fpga_Man_t * p, float AreaLimit ); -extern void Fpga_ManSetTimeLimit( Fpga_Man_t * p, float TimeLimit ); -extern void Fpga_ManSetObeyFanoutLimits( Fpga_Man_t * p, int fObeyFanoutLimits ); -extern void Fpga_ManSetNumIterations( Fpga_Man_t * p, int nNumIterations ); -extern int Fpga_ManReadFanoutViolations( Fpga_Man_t * p ); -extern void Fpga_ManSetFanoutViolations( Fpga_Man_t * p, int nVio ); -extern void Fpga_ManSetChoiceNodeNum( Fpga_Man_t * p, int nChoiceNodes ); -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 ); -extern Fpga_Cut_t * Fpga_NodeReadCutBest( Fpga_Node_t * p ); -extern Fpga_Node_t * Fpga_NodeReadOne( Fpga_Node_t * p ); -extern Fpga_Node_t * Fpga_NodeReadTwo( Fpga_Node_t * p ); -extern void Fpga_NodeSetLevel( Fpga_Node_t * p, Fpga_Node_t * pNode ); -extern void Fpga_NodeSetData0( Fpga_Node_t * p, char * pData ); -extern void Fpga_NodeSetData1( Fpga_Node_t * p, Fpga_Node_t * pNode ); -extern void Fpga_NodeSetArrival( Fpga_Node_t * p, float Time ); -extern void Fpga_NodeSetNextE( Fpga_Node_t * p, Fpga_Node_t * pNextE ); -extern void Fpga_NodeSetRepr( Fpga_Node_t * p, Fpga_Node_t * pRepr ); -extern void Fpga_NodeSetSwitching( Fpga_Node_t * p, float Switching ); - -extern int Fpga_NodeIsConst( Fpga_Node_t * p ); -extern int Fpga_NodeIsVar( Fpga_Node_t * p ); -extern int Fpga_NodeIsAnd( Fpga_Node_t * p ); -extern int Fpga_NodeComparePhase( Fpga_Node_t * p1, Fpga_Node_t * p2 ); - -extern int Fpga_CutReadLeavesNum( Fpga_Cut_t * p ); -extern Fpga_Node_t ** Fpga_CutReadLeaves( Fpga_Cut_t * p ); - -extern Fpga_Node_t * Fpga_NodeAnd( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ); -extern Fpga_Node_t * Fpga_NodeOr( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ); -extern Fpga_Node_t * Fpga_NodeExor( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ); -extern Fpga_Node_t * Fpga_NodeMux( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Node_t * pNodeT, Fpga_Node_t * pNodeE ); -extern void Fpga_NodeSetChoice( Fpga_Man_t * pMan, Fpga_Node_t * pNodeOld, Fpga_Node_t * pNodeNew ); - -extern void Fpga_ManStats( Fpga_Man_t * p ); - -/*=== fpgaCore.c =============================================================*/ -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 ); -/*=== fpgaCutUtils.c =============================================================*/ -extern void Fpga_CutCreateFromNode( Fpga_Man_t * p, int iRoot, int * pLeaves, int nLeaves ); -extern void Fpga_MappingSetUsedCuts( Fpga_Man_t * p ); -/*=== 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 /// -//////////////////////////////////////////////////////////////////////// diff --git a/abc70930/src/map/fpga/fpgaCore.c b/abc70930/src/map/fpga/fpgaCore.c deleted file mode 100644 index 634a8eb1..00000000 --- a/abc70930/src/map/fpga/fpgaCore.c +++ /dev/null @@ -1,188 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaCore.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Technology mapping for variable-size-LUT FPGAs.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaCore.c,v 1.7 2004/10/01 23:41:04 satrajit Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -static int Fpga_MappingPostProcess( Fpga_Man_t * p ); - -extern int s_MappingTime; -extern int s_MappingMem; - - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Performs technology mapping for the given object graph.] - - Description [The object graph is stored in the mapping manager. - First, all the AND-nodes, which fanout into the POs, are collected - in the DFS fashion. Next, three steps are performed: the k-feasible - cuts are computed for each node, the truth tables are computed for - each cut, and the delay-optimal matches are assigned for each node.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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 - Fpga_MappingSetChoiceLevels( p ); - - // compute the cuts of nodes in the DFS order - clk = clock(); - Fpga_MappingCuts( p ); - p->timeCuts = clock() - clk; - - // match the truth tables to the supergates - clk = clock(); - if ( !Fpga_MappingMatches( p, 1 ) ) - return 0; - p->timeMatch = clock() - clk; - - // perform area recovery - 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 ) - { - PRT( "Total time", clock() - clkTotal ); - } - return 1; -} - -/**Function************************************************************* - - Synopsis [Postprocesses the mapped network for area recovery.] - - Description [This procedure assumes that the mapping is assigned. - 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 FPGA technology mapping. Proc. IWLS '04.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MappingPostProcess( Fpga_Man_t * p ) -{ - 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 ); -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, 1 ); - // remap topologically - Fpga_MappingMatches( p, 0 ); - // get the resulting area -// aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); - aAreaTotalCur = Fpga_MappingAreaTrav( p ); - // note that here we do not update the reference counter - // for some reason, this works better on benchmarks -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 ); -} - } - - // update reference counters - aAreaTotalCur2 = Fpga_MappingSetRefsAndArea( p ); - assert( aAreaTotalCur == aAreaTotalCur2 ); - - if ( fRecoverArea ) - { -clk = clock(); - // compute the required times and the fanouts - Fpga_TimeComputeRequiredGlobal( p, 0 ); - // remap topologically - if ( p->fSwitching ) - Fpga_MappingMatchesSwitch( p ); - else - Fpga_MappingMatchesArea( p ); - // get the resulting area - aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); -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 ); -} - } - - p->fAreaGlo = aAreaTotalCur; - return 1; -} - - diff --git a/abc70930/src/map/fpga/fpgaCreate.c b/abc70930/src/map/fpga/fpgaCreate.c deleted file mode 100644 index fa0f80d1..00000000 --- a/abc70930/src/map/fpga/fpgaCreate.c +++ /dev/null @@ -1,580 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaCreate.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Technology mapping for variable-size-LUT FPGAs.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaCreate.c,v 1.8 2004/09/30 21:18:09 satrajit Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" -#include "main.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -static void Fpga_TableCreate( Fpga_Man_t * p ); -static void Fpga_TableResize( Fpga_Man_t * p ); -static Fpga_Node_t * Fpga_TableLookup( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ); - -// hash key for the structural hash table -static inline unsigned Fpga_HashKey2( Fpga_Node_t * p0, Fpga_Node_t * p1, int TableSize ) { return ((unsigned)(p0) + (unsigned)(p1) * 12582917) % TableSize; } - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Reads parameters of the mapping manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_ManReadInputNum( Fpga_Man_t * p ) { return p->nInputs; } -int Fpga_ManReadOutputNum( Fpga_Man_t * p ) { return p->nOutputs; } -Fpga_Node_t ** Fpga_ManReadInputs ( Fpga_Man_t * p ) { return p->pInputs; } -Fpga_Node_t ** Fpga_ManReadOutputs( Fpga_Man_t * p ) { return p->pOutputs; } -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; } -float * Fpga_ManReadLutAreas( Fpga_Man_t * p ) { return p->pLutLib->pLutAreas; } -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; } -void Fpga_ManSetOutputNames( Fpga_Man_t * p, char ** ppNames ) { p->ppOutputNames = ppNames; } -void Fpga_ManSetInputArrivals( Fpga_Man_t * p, float * pArrivals ) { p->pInputArrivals = pArrivals; } -void Fpga_ManSetAreaRecovery( Fpga_Man_t * p, int fAreaRecovery ) { p->fAreaRecovery = fAreaRecovery;} -void Fpga_ManSetDelayLimit( Fpga_Man_t * p, float DelayLimit ) { p->DelayLimit = DelayLimit; } -void Fpga_ManSetAreaLimit( Fpga_Man_t * p, float AreaLimit ) { p->AreaLimit = AreaLimit; } -void Fpga_ManSetTimeLimit( Fpga_Man_t * p, float TimeLimit ) { p->TimeLimit = TimeLimit; } -void Fpga_ManSetChoiceNodeNum( Fpga_Man_t * p, int nChoiceNodes ) { p->nChoiceNodes = nChoiceNodes; } -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************************************************************* - - Synopsis [Reads the parameters of the LUT library.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_LibReadLutMax( Fpga_LutLib_t * pLib ) { return pLib->LutMax; } - -/**Function************************************************************* - - Synopsis [Reads parameters of the mapping node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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; } -Fpga_Cut_t * Fpga_NodeReadCutBest( Fpga_Node_t * p ) { return p->pCutBest; } -Fpga_Node_t * Fpga_NodeReadOne( Fpga_Node_t * p ) { return p->p1; } -Fpga_Node_t * Fpga_NodeReadTwo( Fpga_Node_t * p ) { return p->p2; } -void Fpga_NodeSetData0( Fpga_Node_t * p, char * pData ) { p->pData0 = pData; } -void Fpga_NodeSetData1( Fpga_Node_t * p, Fpga_Node_t * pNode ) { p->pLevel = pNode; } -void Fpga_NodeSetNextE( Fpga_Node_t * p, Fpga_Node_t * pNextE ) { p->pNextE = pNextE; } -void Fpga_NodeSetRepr( Fpga_Node_t * p, Fpga_Node_t * pRepr ) { p->pRepr = pRepr; } -void Fpga_NodeSetSwitching( Fpga_Node_t * p, float Switching ) { p->Switching = Switching; } - -/**Function************************************************************* - - Synopsis [Checks the type of the node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_NodeIsConst( Fpga_Node_t * p ) { return (Fpga_Regular(p))->Num == -1; } -int Fpga_NodeIsVar( Fpga_Node_t * p ) { return (Fpga_Regular(p))->p1 == NULL && (Fpga_Regular(p))->Num >= 0; } -int Fpga_NodeIsAnd( Fpga_Node_t * p ) { return (Fpga_Regular(p))->p1 != NULL; } -int Fpga_NodeComparePhase( Fpga_Node_t * p1, Fpga_Node_t * p2 ) { assert( !Fpga_IsComplement(p1) ); assert( !Fpga_IsComplement(p2) ); return p1->fInv ^ p2->fInv; } - -/**Function************************************************************* - - Synopsis [Reads parameters from the cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CutReadLeavesNum( Fpga_Cut_t * p ) { return p->nLeaves; } -Fpga_Node_t ** Fpga_CutReadLeaves( Fpga_Cut_t * p ) { return p->ppLeaves; } - - -/**Function************************************************************* - - Synopsis [Create the mapping manager.] - - Description [The number of inputs and outputs is assumed to be - known is advance. It is much simpler to have them fixed upfront. - When it comes to representing the object graph in the form of - AIG, the resulting manager is similar to the regular AIG manager, - except that it does not use reference counting (and therefore - does not have garbage collections). It does have table resizing. - The data structure is more flexible to represent additional - information needed for mapping.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Man_t * Fpga_ManCreate( int nInputs, int nOutputs, int fVerbose ) -{ - Fpga_Man_t * p; - int i; - - // start the manager - p = ALLOC( Fpga_Man_t, 1 ); - memset( p, 0, sizeof(Fpga_Man_t) ); - p->pLutLib = Abc_FrameReadLibLut(); - p->nVarsMax = p->pLutLib->LutMax; - p->fVerbose = fVerbose; - p->fAreaRecovery = 1; - p->fEpsilon = (float)0.001; - - Fpga_TableCreate( p ); -//if ( p->fVerbose ) -// printf( "Node = %d (%d) bytes. Cut = %d bytes.\n", sizeof(Fpga_Node_t), FPGA_NUM_BYTES(sizeof(Fpga_Node_t)), sizeof(Fpga_Cut_t) ); - p->mmNodes = Extra_MmFixedStart( FPGA_NUM_BYTES(sizeof(Fpga_Node_t)) ); - p->mmCuts = Extra_MmFixedStart( sizeof(Fpga_Cut_t) ); - - assert( p->nVarsMax > 0 ); -// Fpga_MappingSetupTruthTables( p->uTruths ); - - // make sure the constant node will get index -1 - p->nNodes = -1; - // create the constant node - p->pConst1 = Fpga_NodeCreate( p, NULL, NULL ); - p->vNodesAll = Fpga_NodeVecAlloc( 1000 ); - p->vMapping = Fpga_NodeVecAlloc( 1000 ); - - // create the PI nodes - p->nInputs = nInputs; - p->pInputs = ALLOC( Fpga_Node_t *, nInputs ); - for ( i = 0; i < nInputs; i++ ) - p->pInputs[i] = Fpga_NodeCreate( p, NULL, NULL ); - - // create the place for the output nodes - p->nOutputs = nOutputs; - p->pOutputs = ALLOC( Fpga_Node_t *, nOutputs ); - memset( p->pOutputs, 0, sizeof(Fpga_Node_t *) * nOutputs ); - return p; -} - -/**Function************************************************************* - - Synopsis [Deallocates the mapping manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_ManFree( Fpga_Man_t * p ) -{ -// Fpga_ManStats( p ); -// int i; -// for ( i = 0; i < p->vNodesAll->nSize; i++ ) -// Fpga_NodeVecFree( p->vNodesAll->pArray[i]->vFanouts ); -// Fpga_NodeVecFree( p->pConst1->vFanouts ); - if ( p->vMapping ) - Fpga_NodeVecFree( p->vMapping ); - if ( p->vAnds ) - Fpga_NodeVecFree( p->vAnds ); - if ( p->vNodesAll ) - Fpga_NodeVecFree( p->vNodesAll ); - Extra_MmFixedStop( p->mmNodes ); - Extra_MmFixedStop( p->mmCuts ); - FREE( p->ppOutputNames ); - FREE( p->pInputArrivals ); - FREE( p->pInputs ); - FREE( p->pOutputs ); - FREE( p->pBins ); - FREE( p ); -} - - -/**Function************************************************************* - - Synopsis [Prints runtime statistics of the mapping manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_ManPrintTimeStats( Fpga_Man_t * p ) -{ - extern char * pNetName; - extern int TotalLuts; -// FILE * pTable; - - -/* - pTable = fopen( "stats.txt", "a+" ); - fprintf( pTable, "%s ", pNetName ); - fprintf( pTable, "%.0f ", p->fRequiredGlo ); -// fprintf( pTable, "%.0f ", p->fAreaGlo );//+ (float)nOutputInvs ); - fprintf( pTable, "%.0f ", (float)TotalLuts ); - fprintf( pTable, "%4.2f\n", (float)(p->timeTotal-p->timeToMap)/(float)(CLOCKS_PER_SEC) ); - fclose( pTable ); -*/ - -// printf( "N-canonical = %d. Matchings = %d. ", p->nCanons, p->nMatches ); -// printf( "Choice nodes = %d. Choices = %d.\n", p->nChoiceNodes, p->nChoices ); - PRT( "ToMap", p->timeToMap ); - PRT( "Cuts ", p->timeCuts ); - PRT( "Match", p->timeMatch ); - PRT( "Area ", p->timeRecover ); - PRT( "ToNet", p->timeToNet ); - PRT( "TOTAL", p->timeTotal ); - if ( p->time1 ) { PRT( "time1", p->time1 ); } - if ( p->time2 ) { PRT( "time2", p->time2 ); } -} - -/**Function************************************************************* - - Synopsis [Creates a new node.] - - Description [This procedure should be called to create the constant - node and the PI nodes first.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Node_t * Fpga_NodeCreate( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ) -{ - Fpga_Node_t * pNode; - // create the node - pNode = (Fpga_Node_t *)Extra_MmFixedEntryFetch( p->mmNodes ); - memset( pNode, 0, sizeof(Fpga_Node_t) ); - // set very large required time - pNode->tRequired = FPGA_FLOAT_LARGE; - pNode->aEstFanouts = -1; - pNode->p1 = p1; - pNode->p2 = p2; - // set the number of this node - pNode->Num = p->nNodes++; - // place to store the fanouts -// pNode->vFanouts = Fpga_NodeVecAlloc( 5 ); - // store this node in the internal array - if ( pNode->Num >= 0 ) - Fpga_NodeVecPush( p->vNodesAll, pNode ); - else - pNode->fInv = 1; - // set the level of this node - if ( p1 ) - { -#ifdef FPGA_ALLOCATE_FANOUT - // create the fanout info - Fpga_NodeAddFaninFanout( Fpga_Regular(p1), pNode ); - Fpga_NodeAddFaninFanout( Fpga_Regular(p2), pNode ); -#endif - // compute the level - pNode->Level = 1 + FPGA_MAX(Fpga_Regular(p1)->Level, Fpga_Regular(p2)->Level); - pNode->fInv = Fpga_NodeIsSimComplement(p1) & Fpga_NodeIsSimComplement(p2); - } - // reference the inputs - if ( p1 ) Fpga_NodeRef(p1); - if ( p2 ) Fpga_NodeRef(p2); - return pNode; -} - -/**Function************************************************************* - - Synopsis [Create the unique table of AND gates.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_TableCreate( Fpga_Man_t * pMan ) -{ - assert( pMan->pBins == NULL ); - pMan->nBins = Cudd_Prime(50000); - pMan->pBins = ALLOC( Fpga_Node_t *, pMan->nBins ); - memset( pMan->pBins, 0, sizeof(Fpga_Node_t *) * pMan->nBins ); - pMan->nNodes = 0; -} - -/**Function************************************************************* - - Synopsis [Looks up the AND2 node in the unique table.] - - Description [This procedure implements one-level hashing. All the nodes - are hashed by their children. If the node with the same children was already - created, it is returned by the call to this procedure. If it does not exist, - this procedure creates a new node with these children. ] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Node_t * Fpga_TableLookup( Fpga_Man_t * pMan, Fpga_Node_t * p1, Fpga_Node_t * p2 ) -{ - Fpga_Node_t * pEnt; - unsigned Key; - - if ( p1 == p2 ) - return p1; - if ( p1 == Fpga_Not(p2) ) - return Fpga_Not(pMan->pConst1); - if ( Fpga_NodeIsConst(p1) ) - { - if ( p1 == pMan->pConst1 ) - return p2; - return Fpga_Not(pMan->pConst1); - } - if ( Fpga_NodeIsConst(p2) ) - { - if ( p2 == pMan->pConst1 ) - return p1; - return Fpga_Not(pMan->pConst1); - } - - if ( Fpga_Regular(p1)->Num > Fpga_Regular(p2)->Num ) - pEnt = p1, p1 = p2, p2 = pEnt; - - Key = Fpga_HashKey2( p1, p2, pMan->nBins ); - for ( pEnt = pMan->pBins[Key]; pEnt; pEnt = pEnt->pNext ) - if ( pEnt->p1 == p1 && pEnt->p2 == p2 ) - return pEnt; - // resize the table - if ( pMan->nNodes >= 2 * pMan->nBins ) - { - Fpga_TableResize( pMan ); - Key = Fpga_HashKey2( p1, p2, pMan->nBins ); - } - // create the new node - pEnt = Fpga_NodeCreate( pMan, p1, p2 ); - // add the node to the corresponding linked list in the table - pEnt->pNext = pMan->pBins[Key]; - pMan->pBins[Key] = pEnt; - return pEnt; -} - - -/**Function************************************************************* - - Synopsis [Resizes the table.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_TableResize( Fpga_Man_t * pMan ) -{ - Fpga_Node_t ** pBinsNew; - Fpga_Node_t * pEnt, * pEnt2; - int nBinsNew, Counter, i, clk; - unsigned Key; - -clk = clock(); - // get the new table size - nBinsNew = Cudd_Prime(2 * pMan->nBins); - // allocate a new array - pBinsNew = ALLOC( Fpga_Node_t *, nBinsNew ); - memset( pBinsNew, 0, sizeof(Fpga_Node_t *) * nBinsNew ); - // rehash the entries from the old table - Counter = 0; - for ( i = 0; i < pMan->nBins; i++ ) - for ( pEnt = pMan->pBins[i], pEnt2 = pEnt? pEnt->pNext: NULL; pEnt; - pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL ) - { - Key = Fpga_HashKey2( pEnt->p1, pEnt->p2, nBinsNew ); - pEnt->pNext = pBinsNew[Key]; - pBinsNew[Key] = pEnt; - Counter++; - } - assert( Counter == pMan->nNodes - pMan->nInputs ); - if ( pMan->fVerbose ) - { -// printf( "Increasing the unique table size from %6d to %6d. ", pMan->nBins, nBinsNew ); -// PRT( "Time", clock() - clk ); - } - // replace the table and the parameters - free( pMan->pBins ); - pMan->pBins = pBinsNew; - pMan->nBins = nBinsNew; -} - - - -/**Function************************************************************* - - Synopsis [Elementary AND operation on the AIG.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Node_t * Fpga_NodeAnd( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ) -{ - Fpga_Node_t * pNode; - pNode = Fpga_TableLookup( p, p1, p2 ); - return pNode; -} - -/**Function************************************************************* - - Synopsis [Elementary OR operation on the AIG.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Node_t * Fpga_NodeOr( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ) -{ - Fpga_Node_t * pNode; - pNode = Fpga_Not( Fpga_TableLookup( p, Fpga_Not(p1), Fpga_Not(p2) ) ); - return pNode; -} - -/**Function************************************************************* - - Synopsis [Elementary EXOR operation on the AIG.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Node_t * Fpga_NodeExor( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ) -{ - return Fpga_NodeMux( p, p1, Fpga_Not(p2), p2 ); -} - -/**Function************************************************************* - - Synopsis [Elementary MUX operation on the AIG.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Node_t * Fpga_NodeMux( Fpga_Man_t * p, Fpga_Node_t * pC, Fpga_Node_t * pT, Fpga_Node_t * pE ) -{ - Fpga_Node_t * pAnd1, * pAnd2, * pRes; - pAnd1 = Fpga_TableLookup( p, pC, pT ); - pAnd2 = Fpga_TableLookup( p, Fpga_Not(pC), pE ); - pRes = Fpga_NodeOr( p, pAnd1, pAnd2 ); - return pRes; -} - - -/**Function************************************************************* - - Synopsis [Sets the node to be equivalent to the given one.] - - Description [This procedure is a work-around for the equivalence check. - Does not verify the equivalence. Use at the user's risk.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeSetChoice( Fpga_Man_t * pMan, Fpga_Node_t * pNodeOld, Fpga_Node_t * pNodeNew ) -{ - pNodeNew->pNextE = pNodeOld->pNextE; - pNodeOld->pNextE = pNodeNew; - pNodeNew->pRepr = pNodeOld; -} - - - -/**Function************************************************************* - - Synopsis [Prints some interesting stats.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_ManStats( Fpga_Man_t * p ) -{ - FILE * pTable; - pTable = fopen( "stats.txt", "a+" ); - fprintf( pTable, "%s ", p->pFileName ); - fprintf( pTable, "%4d ", p->nInputs - p->nLatches ); - fprintf( pTable, "%4d ", p->nOutputs - p->nLatches ); - fprintf( pTable, "%4d ", p->nLatches ); - fprintf( pTable, "%7d ", p->vAnds->nSize ); - fprintf( pTable, "%7d ", Fpga_CutCountAll(p) ); - fprintf( pTable, "%2d\n", (int)p->fRequiredGlo ); - fclose( pTable ); -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - diff --git a/abc70930/src/map/fpga/fpgaCut.c b/abc70930/src/map/fpga/fpgaCut.c deleted file mode 100644 index a5505e72..00000000 --- a/abc70930/src/map/fpga/fpgaCut.c +++ /dev/null @@ -1,1159 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaCut.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Generic technology mapping engine.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaCut.c,v 1.3 2004/07/06 04:55:57 alanmi Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -typedef struct Fpga_CutTableStrutct_t Fpga_CutTable_t; -struct Fpga_CutTableStrutct_t -{ - Fpga_Cut_t ** pBins; // the table used for linear probing - int nBins; // the size of the table - int * pCuts; // the array of cuts currently stored - int nCuts; // the number of cuts currently stored - Fpga_Cut_t ** pArray; // the temporary array of cuts - Fpga_Cut_t ** pCuts1; // the temporary array of cuts - Fpga_Cut_t ** pCuts2; // the temporary array of cuts -}; - -// the largest number of cuts considered -//#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 1000 - -// primes used to compute the hash key -static int s_HashPrimes[10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 }; - -static int bit_count[256] = { - 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, - 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, - 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, - 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, - 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, - 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, - 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, - 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8 -}; - -#define FPGA_COUNT_ONES(u) (bit_count[(u)&255]+bit_count[((u)>>8)&255]+bit_count[((u)>>16)&255]+bit_count[(u)>>24]) - -static Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Node_t * pNode ); -static void Fpga_CutFilter( Fpga_Man_t * p, Fpga_Node_t * pNode ); -static 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 ); -static int Fpga_CutMergeTwo( Fpga_Cut_t * pCut1, Fpga_Cut_t * pCut2, Fpga_Node_t * ppNodes[], int nNodesMax ); -static Fpga_Cut_t * Fpga_CutUnionLists( Fpga_Cut_t * pList1, Fpga_Cut_t * pList2 ); -static int Fpga_CutBelongsToList( Fpga_Cut_t * pList, Fpga_Node_t * ppNodes[], int nNodes ); -extern Fpga_Cut_t * Fpga_CutAlloc( Fpga_Man_t * p ); -extern int Fpga_CutCountAll( Fpga_Man_t * pMan ); - -static void Fpga_CutListPrint( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ); -static void Fpga_CutListPrint2( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ); -static void Fpga_CutPrint_( Fpga_Man_t * pMan, Fpga_Cut_t * pCut, Fpga_Node_t * pRoot ); - -static Fpga_CutTable_t * Fpga_CutTableStart( Fpga_Man_t * pMan ); -static void Fpga_CutTableStop( Fpga_CutTable_t * p ); -static unsigned Fpga_CutTableHash( Fpga_Node_t * ppNodes[], int nNodes ); -static int Fpga_CutTableLookup( Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ); -static Fpga_Cut_t * Fpga_CutTableConsider( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ); -static void Fpga_CutTableRestart( Fpga_CutTable_t * p ); - -static int Fpga_CutSortCutsCompare( Fpga_Cut_t ** pC1, Fpga_Cut_t ** pC2 ); -static Fpga_Cut_t * Fpga_CutSortCuts( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Cut_t * pList ); -static int Fpga_CutList2Array( Fpga_Cut_t ** pArray, Fpga_Cut_t * pList ); -static Fpga_Cut_t * Fpga_CutArray2List( Fpga_Cut_t ** pArray, int nCuts ); - - -// iterator through all the cuts of the list -#define Fpga_ListForEachCut( pList, pCut ) \ - for ( pCut = pList; \ - pCut; \ - pCut = pCut->pNext ) -#define Fpga_ListForEachCutSafe( pList, pCut, pCut2 ) \ - for ( pCut = pList, \ - pCut2 = pCut? pCut->pNext: NULL; \ - pCut; \ - pCut = pCut2, \ - pCut2 = pCut? pCut->pNext: NULL ) - - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Computes the cuts for each node in the object graph.] - - Description [The cuts are computed in one sweep over the mapping graph. - First, the elementary cuts, which include the node itself, are assigned - to the PI nodes. The internal nodes are considered in the DFS order. - Each node is two-input AND-gate. So to compute the cuts at a node, we - need to merge the sets of cuts of its two predecessors. The merged set - contains only unique cuts with the number of inputs equal to k or less. - Finally, the elementary cut, composed of the node itself, is added to - the set of cuts for the node. - - This procedure is pretty fast for 5-feasible cuts, but it dramatically - slows down on some "dense" networks when computing 6-feasible cuts. - The problem is that there are too many cuts in this case. We should - think how to heuristically trim the number of cuts in such cases, - to have reasonable runtime.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingCuts( Fpga_Man_t * p ) -{ - ProgressBar * pProgress; - 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 < 11 ); - Fpga_MappingCreatePiCuts( p ); - - // compute the cuts for the internal nodes - nNodes = p->vAnds->nSize; - pProgress = Extra_ProgressBarStart( stdout, nNodes ); - pTable = Fpga_CutTableStart( p ); - for ( i = 0; i < nNodes; i++ ) - { - Extra_ProgressBarUpdate( pProgress, i, "Cuts ..." ); - pNode = p->vAnds->pArray[i]; - if ( !Fpga_NodeIsAnd( pNode ) ) - continue; - Fpga_CutCompute( p, pTable, pNode ); - } - Extra_ProgressBarStop( pProgress ); - Fpga_CutTableStop( pTable ); - - // report the stats - if ( p->fVerbose ) - { - nCuts = Fpga_CutCountAll(p); - 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 -// Fpga_CutListPrint( p, Fpga_Regular(p->pOutputs[0]) ); -} - -/**Function************************************************************* - - Synopsis [Performs technology mapping for variable-size-LUTs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingCreatePiCuts( Fpga_Man_t * p ) -{ - Fpga_Cut_t * pCut; - int i; - - // set the elementary cuts for the PI variables - for ( i = 0; i < p->nInputs; i++ ) - { - pCut = Fpga_CutAlloc( p ); - pCut->nLeaves = 1; - pCut->ppLeaves[0] = p->pInputs[i]; - pCut->uSign = (1 << (i%31)); - p->pInputs[i]->pCuts = pCut; - p->pInputs[i]->pCutBest = pCut; - // set the input arrival times -// p->pInputs[i]->pCut[1]->tArrival = p->pInputArrivals[i]; - } -} - -/**Function************************************************************* - - Synopsis [Computes the cuts for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Node_t * pNode ) -{ - Fpga_Node_t * pTemp; - Fpga_Cut_t * pList, * pList1, * pList2; - Fpga_Cut_t * pCut; - int fTree = 0; - int fPivot1 = fTree && (Fpga_NodeReadRef(pNode->p1)>2); - int fPivot2 = fTree && (Fpga_NodeReadRef(pNode->p2)>2); - - // if the cuts are computed return them - if ( pNode->pCuts ) - return pNode->pCuts; - - // compute the cuts for the children - pList1 = Fpga_Regular(pNode->p1)->pCuts; - pList2 = Fpga_Regular(pNode->p2)->pCuts; - // merge the lists - pList = Fpga_CutMergeLists( p, pTable, pList1, pList2, - Fpga_IsComplement(pNode->p1), Fpga_IsComplement(pNode->p2), - fPivot1, fPivot2 ); - // if there are functionally equivalent nodes, union them with this list - assert( pList ); - // only add to the list of cuts if the node is a representative one - if ( pNode->pRepr == NULL ) - { - for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE ) - { - assert( pTemp->pCuts ); - pList = Fpga_CutUnionLists( pList, pTemp->pCuts ); - assert( pTemp->pCuts ); - pList = Fpga_CutSortCuts( p, pTable, pList ); - } - } - // add the new cut - pCut = Fpga_CutAlloc( p ); - pCut->nLeaves = 1; - pCut->ppLeaves[0] = pNode; - pCut->uSign = (1 << (pNode->Num%31)); - pCut->fLevel = (float)pCut->ppLeaves[0]->Level; - // append (it is important that the elementary cut is appended first) - pCut->pNext = pList; - // set at the node - pNode->pCuts = pCut; - // remove the dominated cuts -// Fpga_CutFilter( p, pNode ); - // set the phase correctly - if ( pNode->pRepr && Fpga_NodeComparePhase(pNode, pNode->pRepr) ) - { - Fpga_ListForEachCut( pNode->pCuts, pCut ) - pCut->Phase = 1; - } - - -/* - { - Fpga_Cut_t * pPrev; - int i, Counter = 0; - for ( pCut = pNode->pCuts->pNext, pPrev = pNode->pCuts; pCut; pCut = pCut->pNext ) - { - for ( i = 0; i < pCut->nLeaves; i++ ) - if ( pCut->ppLeaves[i]->Level >= pNode->Level ) - break; - if ( i != pCut->nLeaves ) - pPrev->pNext = pCut->pNext; - else - pPrev = pCut; - } - } - { - int i, Counter = 0;; - for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) - for ( i = 0; i < pCut->nLeaves; i++ ) - Counter += (pCut->ppLeaves[i]->Level >= pNode->Level); - if ( Counter ) - printf( " %d", Counter ); - } -*/ - - return pCut; -} - -/**Function************************************************************* - - Synopsis [Filter the cuts using dominance.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_CutFilter( Fpga_Man_t * p, Fpga_Node_t * pNode ) -{ - Fpga_Cut_t * pTemp, * pPrev, * pCut, * pCut2; - int i, k, Counter; - - Counter = 0; - pPrev = pNode->pCuts; - Fpga_ListForEachCutSafe( pNode->pCuts->pNext, pCut, pCut2 ) - { - // go through all the previous cuts up to pCut - for ( pTemp = pNode->pCuts->pNext; pTemp != pCut; pTemp = pTemp->pNext ) - { - // check if every node in pTemp is contained in pCut - for ( i = 0; i < pTemp->nLeaves; i++ ) - { - for ( k = 0; k < pCut->nLeaves; k++ ) - if ( pTemp->ppLeaves[i] == pCut->ppLeaves[k] ) - break; - if ( k == pCut->nLeaves ) // node i in pTemp is not contained in pCut - break; - } - if ( i == pTemp->nLeaves ) // every node in pTemp is contained in pCut - { - Counter++; - break; - } - } - if ( pTemp != pCut ) // pTemp contain pCut - { - pPrev->pNext = pCut->pNext; // skip pCut - // recycle pCut - Fpga_CutFree( p, pCut ); - } - else - pPrev = pCut; - } -// printf( "Dominated = %3d. \n", Counter ); -} - - -/**Function************************************************************* - - Synopsis [Merges two lists of cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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[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; - int nCuts1, nCuts2, nCuts3, k, fComp3; - - ppArray1 = pTable->pCuts1; - ppArray2 = pTable->pCuts2; - nCuts1 = Fpga_CutList2Array( ppArray1, pList1 ); - nCuts2 = Fpga_CutList2Array( ppArray2, pList2 ); - if ( fPivot1 ) - nCuts1 = 1; - if ( fPivot2 ) - nCuts2 = 1; - // swap the lists based on their length - if ( nCuts1 > nCuts2 ) - { - ppArray3 = ppArray1; - ppArray1 = ppArray2; - ppArray2 = ppArray3; - - nCuts3 = nCuts1; - nCuts1 = nCuts2; - nCuts2 = nCuts3; - - fComp3 = fComp1; - fComp1 = fComp2; - fComp2 = fComp3; - } - // pList1 is shorter or equal length compared to pList2 - - // prepare the manager for the cut computation - Fpga_CutTableRestart( pTable ); - // go through the cut pairs - Counter = 0; -// for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext ) -// for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext ) - for ( i = 0; i < nCuts1; i++ ) - { - for ( k = 0; k <= i; k++ ) - { - pTemp1 = ppArray1[i]; - pTemp2 = ppArray2[k]; - - if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax ) - { - if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] ) - continue; - if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] ) - continue; - } - - // check if k-feasible cut exists - nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); - if ( nNodes == 0 ) - continue; - // consider the cut for possible addition to the set of new cuts - pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes ); - if ( pCut == NULL ) - continue; - // add data to the cut - pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 ); - pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 ); - // create the signature - pCut->uSign = pTemp1->uSign | pTemp2->uSign; - // add it to the corresponding list - pCut->pNext = pLists[pCut->nLeaves]; - pLists[pCut->nLeaves] = pCut; - // count this cut and quit if limit is reached - Counter++; - if ( Counter == FPGA_CUTS_MAX_COMPUTE ) - goto QUITS; - } - for ( k = 0; k < i; k++ ) - { - pTemp1 = ppArray1[k]; - pTemp2 = ppArray2[i]; - - if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax ) - { - if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] ) - continue; - if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] ) - continue; - } - - - // check if k-feasible cut exists - nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); - if ( nNodes == 0 ) - continue; - // consider the cut for possible addition to the set of new cuts - pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes ); - if ( pCut == NULL ) - continue; - // add data to the cut - pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 ); - pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 ); - // create the signature - pCut->uSign = pTemp1->uSign | pTemp2->uSign; - // add it to the corresponding list - pCut->pNext = pLists[pCut->nLeaves]; - pLists[pCut->nLeaves] = pCut; - // count this cut and quit if limit is reached - Counter++; - if ( Counter == FPGA_CUTS_MAX_COMPUTE ) - goto QUITS; - } - } - // consider the rest of them - for ( i = nCuts1; i < nCuts2; i++ ) - for ( k = 0; k < nCuts1; k++ ) - { - pTemp1 = ppArray1[k]; - pTemp2 = ppArray2[i]; - - if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax ) - { - if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] ) - continue; - if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] ) - continue; - if ( pTemp1->ppLeaves[2] != pTemp2->ppLeaves[2] ) - continue; - } - - - // check if k-feasible cut exists - nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); - if ( nNodes == 0 ) - continue; - // consider the cut for possible addition to the set of new cuts - pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes ); - if ( pCut == NULL ) - continue; - // add data to the cut - pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 ); - pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 ); - // create the signature - pCut->uSign = pTemp1->uSign | pTemp2->uSign; - // add it to the corresponding list - pCut->pNext = pLists[pCut->nLeaves]; - pLists[pCut->nLeaves] = pCut; - // count this cut and quit if limit is reached - Counter++; - if ( Counter == FPGA_CUTS_MAX_COMPUTE ) - goto QUITS; - } -QUITS : - // combine all the lists into one - pListNew = NULL; - ppListNew = &pListNew; - for ( i = 1; i <= p->nVarsMax; i++ ) - { - if ( pLists[i] == NULL ) - continue; - // find the last entry - for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut; - pPrev = pCut, pCut = pCut->pNext ); - // connect these lists - *ppListNew = pLists[i]; - ppListNew = &pPrev->pNext; - } - *ppListNew = NULL; - // sort the cuts by arrival times and use only the first FPGA_CUTS_MAX_USE - pListNew = Fpga_CutSortCuts( p, pTable, pListNew ); - return pListNew; -} - - -/**Function************************************************************* - - Synopsis [Merges two lists of cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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[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; - - // prepare the manager for the cut computation - Fpga_CutTableRestart( pTable ); - // go through the cut pairs - Counter = 0; - for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext ) - for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext ) - { - // check if k-feasible cut exists - nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); - if ( nNodes == 0 ) - continue; - // consider the cut for possible addition to the set of new cuts - pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes ); - if ( pCut == NULL ) - continue; - // add data to the cut - pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 ); - pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 ); - // add it to the corresponding list - pCut->pNext = pLists[pCut->nLeaves]; - pLists[pCut->nLeaves] = pCut; - // count this cut and quit if limit is reached - Counter++; - if ( Counter == FPGA_CUTS_MAX_COMPUTE ) - goto QUITS; - } -QUITS : - // combine all the lists into one - pListNew = NULL; - ppListNew = &pListNew; - for ( i = 1; i <= p->nVarsMax; i++ ) - { - if ( pLists[i] == NULL ) - continue; - // find the last entry - for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut; - pPrev = pCut, pCut = pCut->pNext ); - // connect these lists - *ppListNew = pLists[i]; - ppListNew = &pPrev->pNext; - } - *ppListNew = NULL; - // sort the cuts by arrival times and use only the first FPGA_CUTS_MAX_USE - pListNew = Fpga_CutSortCuts( p, pTable, pListNew ); - return pListNew; -} - -/**Function************************************************************* - - Synopsis [Merges two cuts.] - - Description [Returns the number of nodes in the resulting cut, or 0 if the - cut is infeasible. Returns the resulting nodes in the array ppNodes[].] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CutMergeTwo( Fpga_Cut_t * pCut1, Fpga_Cut_t * pCut2, Fpga_Node_t * ppNodes[], int nNodesMax ) -{ - Fpga_Node_t * pNodeTemp; - int nTotal, i, k, min, Counter; - unsigned uSign; - - // use quick prefiltering - uSign = pCut1->uSign | pCut2->uSign; - Counter = FPGA_COUNT_ONES(uSign); - if ( Counter > nNodesMax ) - return 0; -/* - // check the special case when at least of the cuts is the largest - if ( pCut1->nLeaves == nNodesMax ) - { - if ( pCut2->nLeaves == nNodesMax ) - { - // return 0 if the cuts are different - for ( i = 0; i < nNodesMax; i++ ) - if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i] ) - return 0; - // return nNodesMax if they are the same - for ( i = 0; i < nNodesMax; i++ ) - ppNodes[i] = pCut1->ppLeaves[i]; - return nNodesMax; - } - else if ( pCut2->nLeaves == nNodesMax - 1 ) - { - // return 0 if the cuts are different - fMismatch = 0; - for ( i = 0; i < nNodesMax; i++ ) - if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i - fMismatch] ) - { - if ( fMismatch == 1 ) - return 0; - fMismatch = 1; - } - // return nNodesMax if they are the same - for ( i = 0; i < nNodesMax; i++ ) - ppNodes[i] = pCut1->ppLeaves[i]; - return nNodesMax; - } - } - else if ( pCut1->nLeaves == nNodesMax - 1 && pCut2->nLeaves == nNodesMax ) - { - // return 0 if the cuts are different - fMismatch = 0; - for ( i = 0; i < nNodesMax; i++ ) - if ( pCut1->ppLeaves[i - fMismatch] != pCut2->ppLeaves[i] ) - { - if ( fMismatch == 1 ) - return 0; - fMismatch = 1; - } - // return nNodesMax if they are the same - for ( i = 0; i < nNodesMax; i++ ) - ppNodes[i] = pCut2->ppLeaves[i]; - return nNodesMax; - } -*/ - // count the number of unique entries in pCut2 - nTotal = pCut1->nLeaves; - for ( i = 0; i < pCut2->nLeaves; i++ ) - { - // try to find this entry among the leaves of pCut1 - for ( k = 0; k < pCut1->nLeaves; k++ ) - if ( pCut2->ppLeaves[i] == pCut1->ppLeaves[k] ) - break; - if ( k < pCut1->nLeaves ) // found - continue; - // we found a new entry to add - if ( nTotal == nNodesMax ) - return 0; - ppNodes[nTotal++] = pCut2->ppLeaves[i]; - } - // we know that the feasible cut exists - - // add the starting entries - for ( k = 0; k < pCut1->nLeaves; k++ ) - ppNodes[k] = pCut1->ppLeaves[k]; - - // selection-sort the entries - for ( i = 0; i < nTotal - 1; i++ ) - { - min = i; - for ( k = i+1; k < nTotal; k++ ) -// 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]; - ppNodes[min] = pNodeTemp; - } - - return nTotal; -} - -/**Function************************************************************* - - Synopsis [Computes the union of the two lists of cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Cut_t * Fpga_CutUnionLists( Fpga_Cut_t * pList1, Fpga_Cut_t * pList2 ) -{ - Fpga_Cut_t * pTemp, * pRoot; - // find the last cut in the first list - pRoot = pList1; - Fpga_ListForEachCut( pList1, pTemp ) - pRoot = pTemp; - // attach the non-trival part of the second cut to the end of the first - assert( pRoot->pNext == NULL ); - pRoot->pNext = pList2->pNext; - pList2->pNext = NULL; - return pList1; -} - - -/**Function************************************************************* - - Synopsis [Checks whether the given cut belongs to the list.] - - Description [This procedure takes most of the runtime in the cut - computation.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CutBelongsToList( Fpga_Cut_t * pList, Fpga_Node_t * ppNodes[], int nNodes ) -{ - Fpga_Cut_t * pTemp; - int i; - for ( pTemp = pList; pTemp; pTemp = pTemp->pNext ) - { - for ( i = 0; i < nNodes; i++ ) - if ( pTemp->ppLeaves[i] != ppNodes[i] ) - break; - if ( i == nNodes ) - return 1; - } - return 0; -} - -/**Function************************************************************* - - Synopsis [Counts all the cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CutCountAll( Fpga_Man_t * pMan ) -{ - Fpga_Node_t * pNode; - Fpga_Cut_t * pCut; - int i, nCuts; - // go through all the nodes in the unique table of the manager - nCuts = 0; - for ( i = 0; i < pMan->nBins; i++ ) - 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; -} - - -/**Function************************************************************* - - Synopsis [Clean the signatures.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_CutsCleanSign( 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->uSign = 0; -} - - - -/**Function************************************************************* - - Synopsis [Prints the cuts in the list.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_CutListPrint( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ) -{ - Fpga_Cut_t * pTemp; - int Counter; - for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ ) - { - printf( "%2d : ", Counter + 1 ); - Fpga_CutPrint_( pMan, pTemp, pRoot ); - } -} - -/**Function************************************************************* - - Synopsis [Prints the cuts in the list.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_CutListPrint2( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ) -{ - Fpga_Cut_t * pTemp; - int Counter; - for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ ) - { - printf( "%2d : ", Counter + 1 ); - Fpga_CutPrint_( pMan, pTemp, pRoot ); - } -} - -/**Function************************************************************* - - Synopsis [Prints the cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_CutPrint_( Fpga_Man_t * pMan, Fpga_Cut_t * pCut, Fpga_Node_t * pRoot ) -{ - int i; - printf( "(%3d) {", pRoot->Num ); - for ( i = 0; i < pMan->nVarsMax; i++ ) - if ( pCut->ppLeaves[i] ) - printf( " %3d", pCut->ppLeaves[i]->Num ); - printf( " }\n" ); -} - - - - - - - - -/**Function************************************************************* - - Synopsis [Starts the hash table to canonicize cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_CutTable_t * Fpga_CutTableStart( Fpga_Man_t * pMan ) -{ - Fpga_CutTable_t * p; - // allocate the table - p = ALLOC( Fpga_CutTable_t, 1 ); - memset( p, 0, sizeof(Fpga_CutTable_t) ); - p->nBins = Cudd_Prime( 10 * FPGA_CUTS_MAX_COMPUTE ); - p->pBins = ALLOC( Fpga_Cut_t *, p->nBins ); - memset( p->pBins, 0, sizeof(Fpga_Cut_t *) * p->nBins ); - p->pCuts = ALLOC( int, 2 * FPGA_CUTS_MAX_COMPUTE ); - p->pArray = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE ); - p->pCuts1 = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE ); - p->pCuts2 = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE ); - return p; -} - -/**Function************************************************************* - - Synopsis [Stops the hash table.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_CutTableStop( Fpga_CutTable_t * p ) -{ - free( p->pCuts1 ); - free( p->pCuts2 ); - free( p->pArray ); - free( p->pBins ); - free( p->pCuts ); - free( p ); -} - -/**Function************************************************************* - - Synopsis [Computes the hash value of the cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -unsigned Fpga_CutTableHash( Fpga_Node_t * ppNodes[], int nNodes ) -{ - unsigned uRes; - int i; - uRes = 0; - for ( i = 0; i < nNodes; i++ ) - uRes += s_HashPrimes[i] * ppNodes[i]->Num; - return uRes; -} - -/**Function************************************************************* - - Synopsis [Looks up the table for the available cut.] - - Description [Returns -1 if the same cut is found. Returns the index - of the cell where the cut should be added, if it does not exist.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CutTableLookup( Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ) -{ - Fpga_Cut_t * pCut; - unsigned Key; - int b, i; - - Key = Fpga_CutTableHash(ppNodes, nNodes) % p->nBins; - for ( b = Key; p->pBins[b]; b = (b+1) % p->nBins ) - { - pCut = p->pBins[b]; - if ( pCut->nLeaves != nNodes ) - continue; - for ( i = 0; i < nNodes; i++ ) - if ( pCut->ppLeaves[i] != ppNodes[i] ) - break; - if ( i == nNodes ) - return -1; - } - return b; -} - - -/**Function************************************************************* - - Synopsis [Starts the hash table to canonicize cuts.] - - Description [Considers addition of the cut to the hash table.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Cut_t * Fpga_CutTableConsider( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ) -{ - Fpga_Cut_t * pCut; - int Place, i; - // check the cut - Place = Fpga_CutTableLookup( p, ppNodes, nNodes ); - if ( Place == -1 ) - return NULL; - assert( nNodes > 0 ); - // create the new cut - pCut = Fpga_CutAlloc( pMan ); - pCut->nLeaves = nNodes; - pCut->fLevel = 0.0; - for ( i = 0; i < nNodes; i++ ) - { - pCut->ppLeaves[i] = ppNodes[i]; - pCut->fLevel += ppNodes[i]->Level; - } - pCut->fLevel /= nNodes; - // add the cut to the table - assert( p->pBins[Place] == NULL ); - p->pBins[Place] = pCut; - // add the cut to the new list - p->pCuts[ p->nCuts++ ] = Place; - return pCut; -} - -/**Function************************************************************* - - Synopsis [Prepares the table to be used with other cuts.] - - Description [Restarts the table by cleaning the info about cuts stored - when the previous node was considered.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_CutTableRestart( Fpga_CutTable_t * p ) -{ - int i; - for ( i = 0; i < p->nCuts; i++ ) - { - assert( p->pBins[ p->pCuts[i] ] ); - p->pBins[ p->pCuts[i] ] = NULL; - } - p->nCuts = 0; -} - - - -/**Function************************************************************* - - Synopsis [Compares the cuts by the number of leaves and then by delay.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CutSortCutsCompare( Fpga_Cut_t ** pC1, Fpga_Cut_t ** pC2 ) -{ - if ( (*pC1)->nLeaves < (*pC2)->nLeaves ) - return -1; - if ( (*pC1)->nLeaves > (*pC2)->nLeaves ) - return 1; -/* - if ( (*pC1)->fLevel > (*pC2)->fLevel ) - return -1; - if ( (*pC1)->fLevel < (*pC2)->fLevel ) - return 1; -*/ - return 0; -} - -/**Function************************************************************* - - Synopsis [Sorts the cuts by average arrival time.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Cut_t * Fpga_CutSortCuts( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Cut_t * pList ) -{ - Fpga_Cut_t * pListNew; - int nCuts, i; - // move the cuts from the list into the array - nCuts = Fpga_CutList2Array( p->pCuts1, pList ); - assert( nCuts <= FPGA_CUTS_MAX_COMPUTE ); - // sort the cuts - 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 ) - { -// printf( "*" ); - // free the remaining cuts - for ( i = FPGA_CUTS_MAX_USE - 1; i < nCuts; i++ ) - Extra_MmFixedEntryRecycle( pMan->mmCuts, (char *)p->pCuts1[i] ); - // update the number of cuts - nCuts = FPGA_CUTS_MAX_USE - 1; - } - pListNew = Fpga_CutArray2List( p->pCuts1, nCuts ); - return pListNew; -} - -/**Function************************************************************* - - Synopsis [Moves the nodes from the list into the array.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CutList2Array( Fpga_Cut_t ** pArray, Fpga_Cut_t * pList ) -{ - int i; - for ( i = 0; pList; pList = pList->pNext, i++ ) - pArray[i] = pList; - return i; -} - -/**Function************************************************************* - - Synopsis [Moves the nodes from the array into the list.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Cut_t * Fpga_CutArray2List( Fpga_Cut_t ** pArray, int nCuts ) -{ - Fpga_Cut_t * pListNew, ** ppListNew; - int i; - pListNew = NULL; - ppListNew = &pListNew; - for ( i = 0; i < nCuts; i++ ) - { - // connect these lists - *ppListNew = pArray[i]; - ppListNew = &pArray[i]->pNext; -//printf( " %d(%.2f)", pArray[i]->nLeaves, pArray[i]->fLevel ); - } -//printf( "\n" ); - - *ppListNew = NULL; - return pListNew; -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - diff --git a/abc70930/src/map/fpga/fpgaCutUtils.c b/abc70930/src/map/fpga/fpgaCutUtils.c deleted file mode 100644 index e60a1dee..00000000 --- a/abc70930/src/map/fpga/fpgaCutUtils.c +++ /dev/null @@ -1,470 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaCutUtils.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Generic technology mapping engine.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaCutUtils.h,v 1.0 2003/09/08 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Allocates the cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Cut_t * Fpga_CutAlloc( Fpga_Man_t * p ) -{ - Fpga_Cut_t * pCut; - pCut = (Fpga_Cut_t *)Extra_MmFixedEntryFetch( p->mmCuts ); - memset( pCut, 0, sizeof(Fpga_Cut_t) ); - return pCut; -} - -/**Function************************************************************* - - Synopsis [Duplicates the cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Cut_t * Fpga_CutDup( Fpga_Man_t * p, Fpga_Cut_t * pCutOld ) -{ - Fpga_Cut_t * pCutNew; - int i; - pCutNew = Fpga_CutAlloc( p ); - pCutNew->pRoot = pCutOld->pRoot; - pCutNew->nLeaves = pCutOld->nLeaves; - for ( i = 0; i < pCutOld->nLeaves; i++ ) - pCutNew->ppLeaves[i] = pCutOld->ppLeaves[i]; - return pCutNew; -} - -/**Function************************************************************* - - Synopsis [Deallocates the cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_CutFree( Fpga_Man_t * p, Fpga_Cut_t * pCut ) -{ - if ( pCut ) - Extra_MmFixedEntryRecycle( p->mmCuts, (char *)pCut ); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_CutPrint( Fpga_Man_t * p, Fpga_Node_t * pRoot, Fpga_Cut_t * pCut ) -{ - int i; - printf( "CUT: Delay = %4.2f. Area = %4.2f. Nodes = %d -> {", - pCut->tArrival, pCut->aFlow, pRoot->Num ); - for ( i = 0; i < pCut->nLeaves; i++ ) - printf( " %d", pCut->ppLeaves[i]->Num ); - printf( " } \n" ); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Cut_t * Fpga_CutCreateSimple( Fpga_Man_t * p, Fpga_Node_t * pNode ) -{ - Fpga_Cut_t * pCut; - pCut = Fpga_CutAlloc( p ); - pCut->pRoot = pNode; - pCut->nLeaves = 1; - pCut->ppLeaves[0] = pNode; - pCut->uSign = FPGA_SEQ_SIGN(pCut->ppLeaves[0]); - return pCut; -} - - -/**function************************************************************* - - synopsis [Computes the exact area associated with the cut.] - - description [] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutGetRootArea( Fpga_Man_t * p, Fpga_Cut_t * pCut ) -{ - return p->pLutLib->pLutAreas[pCut->nLeaves]; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Cut_t * Fpga_CutListAppend( Fpga_Cut_t * pSetAll, Fpga_Cut_t * pSets ) -{ - Fpga_Cut_t * pPrev, * pTemp; - if ( pSetAll == NULL ) - return pSets; - if ( pSets == NULL ) - return pSetAll; - // find the last one - for ( pTemp = pSets; pTemp; pTemp = pTemp->pNext ) - pPrev = pTemp; - // append all the end of the current set - assert( pPrev->pNext == NULL ); - pPrev->pNext = pSetAll; - return pSets; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_CutListRecycle( Fpga_Man_t * p, Fpga_Cut_t * pSetList, Fpga_Cut_t * pSave ) -{ - Fpga_Cut_t * pNext, * pTemp; - for ( pTemp = pSetList, pNext = pTemp? pTemp->pNext : NULL; - pTemp; - pTemp = pNext, pNext = pNext? pNext->pNext : NULL ) - if ( pTemp != pSave ) - Extra_MmFixedEntryRecycle( p->mmCuts, (char *)pTemp ); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CutListCount( Fpga_Cut_t * pSets ) -{ - Fpga_Cut_t * pTemp; - int i; - for ( i = 0, pTemp = pSets; pTemp; pTemp = pTemp->pNext, i++ ); - return i; -} - -#if 0 - -/**function************************************************************* - - synopsis [Removes the fanouts of the cut.] - - description [] - - sideeffects [] - - seealso [] - -***********************************************************************/ -void Fpga_CutRemoveFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ) -{ - Fpga_NodeVec_t * vFanouts; - int i, k; - for ( i = 0; i < pCut->nLeaves; i++ ) - { - vFanouts = pCut->ppLeaves[i]->vFanouts; - for ( k = 0; k < vFanouts->nSize; k++ ) - if ( vFanouts->pArray[k] == pNode ) - break; - assert( k != vFanouts->nSize ); - for ( k++; k < vFanouts->nSize; k++ ) - vFanouts->pArray[k-1] = vFanouts->pArray[k]; - vFanouts->nSize--; - } -} - -/**function************************************************************* - - synopsis [Removes the fanouts of the cut.] - - description [] - - sideeffects [] - - seealso [] - -***********************************************************************/ -void Fpga_CutInsertFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ) -{ - int i; - for ( i = 0; i < pCut->nLeaves; i++ ) - Fpga_NodeVecPush( pCut->ppLeaves[i]->vFanouts, pNode ); -} -#endif - -/**Function************************************************************* - - Synopsis [Computes the arrival time and the area flow of the cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_CutGetParameters( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) -{ - Fpga_Cut_t * pFaninCut; - int i; - pCut->tArrival = -FPGA_FLOAT_LARGE; - pCut->aFlow = pMan->pLutLib->pLutAreas[pCut->nLeaves]; - for ( i = 0; i < pCut->nLeaves; i++ ) - { - pFaninCut = pCut->ppLeaves[i]->pCutBest; - if ( pCut->tArrival < pFaninCut->tArrival ) - pCut->tArrival = pFaninCut->tArrival; - // if the fanout count is not set, assume it to be 1 - if ( pCut->ppLeaves[i]->nRefs == 0 ) - pCut->aFlow += pFaninCut->aFlow; - else -// pCut->aFlow += pFaninCut->aFlow / pCut->ppLeaves[i]->nRefs; - pCut->aFlow += pFaninCut->aFlow / pCut->ppLeaves[i]->aEstFanouts; - } - // 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]; -} - - -/**function************************************************************* - - synopsis [Computes the area flow of the cut.] - - description [] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutGetAreaFlow( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) -{ - Fpga_Cut_t * pCutFanin; - int i; - pCut->aFlow = pMan->pLutLib->pLutAreas[pCut->nLeaves]; - for ( i = 0; i < pCut->nLeaves; i++ ) - { - // get the cut implementing this phase of the fanin - pCutFanin = pCut->ppLeaves[i]->pCutBest; - assert( pCutFanin ); - pCut->aFlow += pCutFanin->aFlow / pCut->ppLeaves[i]->nRefs; - } - return pCut->aFlow; -} - -/**function************************************************************* - - synopsis [Computes the exact area associated with the cut.] - - description [] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutGetAreaRefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) -{ - float aResult, aResult2; - if ( pCut->nLeaves == 1 ) - return 0; - aResult = Fpga_CutDeref( pMan, NULL, pCut, 0 ); - aResult2 = Fpga_CutRef( pMan, NULL, pCut, 0 ); - assert( Fpga_FloatEqual( pMan, aResult, aResult2 ) ); - return aResult; -} - -/**function************************************************************* - - synopsis [Computes the exact area associated with the cut.] - - description [] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutGetAreaDerefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) -{ - float aResult, aResult2; - if ( pCut->nLeaves == 1 ) - return 0; - aResult2 = Fpga_CutRef( pMan, NULL, pCut, 0 ); - aResult = Fpga_CutDeref( pMan, NULL, pCut, 0 ); - assert( Fpga_FloatEqual( pMan, aResult, aResult2 ) ); - return aResult; -} - -/**function************************************************************* - - synopsis [References the cut.] - - description [This procedure is similar to the procedure NodeReclaim.] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutRef( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ) -{ - Fpga_Node_t * pNodeChild; - float aArea; - int i; - - // deref the fanouts -// if ( fFanouts ) -// Fpga_CutInsertFanouts( pMan, pNode, pCut ); - - // start the area of this cut - aArea = pMan->pLutLib->pLutAreas[pCut->nLeaves]; - // go through the children - for ( i = 0; i < pCut->nLeaves; i++ ) - { - pNodeChild = pCut->ppLeaves[i]; - assert( pNodeChild->nRefs >= 0 ); - if ( pNodeChild->nRefs++ > 0 ) - continue; - if ( !Fpga_NodeIsAnd(pNodeChild) ) - continue; - aArea += Fpga_CutRef( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts ); - } - return aArea; -} - -/**function************************************************************* - - synopsis [Dereferences the cut.] - - description [This procedure is similar to the procedure NodeRecusiveDeref.] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutDeref( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ) -{ - Fpga_Node_t * pNodeChild; - float aArea; - int i; - - // deref the fanouts -// if ( fFanouts ) -// Fpga_CutRemoveFanouts( pMan, pNode, pCut ); - - // start the area of this cut - aArea = pMan->pLutLib->pLutAreas[pCut->nLeaves]; - // go through the children - for ( i = 0; i < pCut->nLeaves; i++ ) - { - pNodeChild = pCut->ppLeaves[i]; - assert( pNodeChild->nRefs > 0 ); - if ( --pNodeChild->nRefs > 0 ) - continue; - if ( !Fpga_NodeIsAnd(pNodeChild) ) - continue; - aArea += Fpga_CutDeref( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts ); - } - return aArea; -} - - -/**Function************************************************************* - - Synopsis [Sets the used cuts to be the currently selected ones.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingSetUsedCuts( Fpga_Man_t * pMan ) -{ - int i; - for ( i = 0; i < pMan->vNodesAll->nSize; i++ ) - if ( pMan->vNodesAll->pArray[i]->pCutOld ) - { - pMan->vNodesAll->pArray[i]->pCutBest = pMan->vNodesAll->pArray[i]->pCutOld; - pMan->vNodesAll->pArray[i]->pCutOld = NULL; - } -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/abc70930/src/map/fpga/fpgaFanout.c b/abc70930/src/map/fpga/fpgaFanout.c deleted file mode 100644 index c28a8799..00000000 --- a/abc70930/src/map/fpga/fpgaFanout.c +++ /dev/null @@ -1,141 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaFanout.c] - - PackageName [FRAIG: Functionally reduced AND-INV graphs.] - - Synopsis [Procedures to manipulate fanouts of the FRAIG nodes.] - - Author [Alan Mishchenko <alanmi@eecs.berkeley.edu>] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaFanout.c,v 1.1 2005/01/23 06:59:41 alanmi Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" - -#ifdef MAP_ALLOCATE_FANOUT - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Add the fanout to the node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeAddFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanout ) -{ - Fpga_Node_t * pPivot; - - // pFanins is a fanin of pFanout - assert( !Fpga_IsComplement(pFanin) ); - assert( !Fpga_IsComplement(pFanout) ); - assert( Fpga_Regular(pFanout->p1) == pFanin || Fpga_Regular(pFanout->p2) == pFanin ); - - pPivot = pFanin->pFanPivot; - if ( pPivot == NULL ) - { - pFanin->pFanPivot = pFanout; - return; - } - - if ( Fpga_Regular(pPivot->p1) == pFanin ) - { - if ( Fpga_Regular(pFanout->p1) == pFanin ) - { - pFanout->pFanFanin1 = pPivot->pFanFanin1; - pPivot->pFanFanin1 = pFanout; - } - else // if ( Fpga_Regular(pFanout->p2) == pFanin ) - { - pFanout->pFanFanin2 = pPivot->pFanFanin1; - pPivot->pFanFanin1 = pFanout; - } - } - else // if ( Fpga_Regular(pPivot->p2) == pFanin ) - { - assert( Fpga_Regular(pPivot->p2) == pFanin ); - if ( Fpga_Regular(pFanout->p1) == pFanin ) - { - pFanout->pFanFanin1 = pPivot->pFanFanin2; - pPivot->pFanFanin2 = pFanout; - } - else // if ( Fpga_Regular(pFanout->p2) == pFanin ) - { - pFanout->pFanFanin2 = pPivot->pFanFanin2; - pPivot->pFanFanin2 = pFanout; - } - } -} - -/**Function************************************************************* - - Synopsis [Add the fanout to the node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeRemoveFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanoutToRemove ) -{ - Fpga_Node_t * pFanout, * pFanout2, ** ppFanList; - // start the linked list of fanouts - ppFanList = &pFanin->pFanPivot; - // go through the fanouts - Fpga_NodeForEachFanoutSafe( pFanin, pFanout, pFanout2 ) - { - // skip the fanout-to-remove - if ( pFanout == pFanoutToRemove ) - continue; - // add useful fanouts to the list - *ppFanList = pFanout; - ppFanList = Fpga_NodeReadNextFanoutPlace( pFanin, pFanout ); - } - *ppFanList = NULL; -} - -/**Function************************************************************* - - Synopsis [Returns the number of fanouts of a node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_NodeGetFanoutNum( Fpga_Node_t * pNode ) -{ - Fpga_Node_t * pFanout; - int Counter = 0; - Fpga_NodeForEachFanout( pNode, pFanout ) - Counter++; - return Counter; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - -#endif - diff --git a/abc70930/src/map/fpga/fpgaGENERIC.c b/abc70930/src/map/fpga/fpgaGENERIC.c deleted file mode 100644 index 4483c215..00000000 --- a/abc70930/src/map/fpga/fpgaGENERIC.c +++ /dev/null @@ -1,46 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpga__.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Generic technology mapping engine.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - September 8, 2003.] - - Revision [$Id: fpga__.h,v 1.0 2003/09/08 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/abc70930/src/map/fpga/fpgaInt.h b/abc70930/src/map/fpga/fpgaInt.h deleted file mode 100644 index b93eacab..00000000 --- a/abc70930/src/map/fpga/fpgaInt.h +++ /dev/null @@ -1,388 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaInt.h] - - PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] - - Synopsis [Technology mapping for variable-size-LUT FPGAs.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaInt.h,v 1.8 2004/09/30 21:18:10 satrajit Exp $] - -***********************************************************************/ - -#ifndef __FPGA_INT_H__ -#define __FPGA_INT_H__ - -//////////////////////////////////////////////////////////////////////// -/// INCLUDES /// -//////////////////////////////////////////////////////////////////////// - -//#include "leaks.h" -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include "extra.h" -#include "fpga.h" - -//////////////////////////////////////////////////////////////////////// -/// PARAMETERS /// -//////////////////////////////////////////////////////////////////////// - -// uncomment to have fanouts represented in the mapping graph -//#define FPGA_ALLOCATE_FANOUT 1 - -//////////////////////////////////////////////////////////////////////// -/// MACRO DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -#ifdef _WIN32 -#define inline __inline // compatible with MS VS 6.0 -#endif - -// the maximum number of cut leaves (currently does not work for 7) -#define FPGA_MAX_LEAVES 6 - -// the bit masks -#define FPGA_MASK(n) ((~((unsigned)0)) >> (32-(n))) -#define FPGA_FULL (~((unsigned)0)) -#define FPGA_NO_VAR (-9999.0) -#define FPGA_NUM_BYTES(n) (((n)/16 + (((n)%16) > 0))*16) - -// maximum/minimum operators -#define FPGA_MIN(a,b) (((a) < (b))? (a) : (b)) -#define FPGA_MAX(a,b) (((a) > (b))? (a) : (b)) - -// the small and large numbers (min/max float are 1.17e-38/3.40e+38) -#define FPGA_FLOAT_LARGE ((float)1.0e+20) -#define FPGA_FLOAT_SMALL ((float)1.0e-20) -#define FPGA_INT_LARGE (10000000) - -// the macro to compute the signature -#define FPGA_SEQ_SIGN(p) (1 << (((unsigned)p)%31)); - -// internal macros to work with cuts -#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)((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) -#define Fpga_NodeRef(p) ((Fpga_Regular(p))->nRefs++) - -// returns the complemented attribute of the node -#define Fpga_NodeIsSimComplement(p) (Fpga_IsComplement(p)? !(Fpga_Regular(p)->fInv) : (p)->fInv) - -// generating random unsigned (#define RAND_MAX 0x7fff) -#define FPGA_RANDOM_UNSIGNED ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand())) - -// outputs the runtime in seconds -#define PRT(a,t) printf("%s = ", (a)); printf("%6.2f sec\n", (float)(t)/(float)(CLOCKS_PER_SEC)) - -//////////////////////////////////////////////////////////////////////// -/// STRUCTURE DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -// the mapping manager -struct Fpga_ManStruct_t_ -{ - // the mapping graph - Fpga_Node_t ** pBins; // the table of nodes hashed by their children - int nBins; // the size of the table - Fpga_Node_t ** pInputs; // the array of inputs - int nInputs; // the number of inputs - Fpga_Node_t ** pOutputs; // the array of outputs - int nOutputs; // the number of outputs - int nNodes; // the total number of nodes - int nLatches; // the number of latches in the circuit - Fpga_Node_t * pConst1; // the constant 1 node - Fpga_NodeVec_t * vNodesAll; // the nodes by number - Fpga_NodeVec_t * vAnds; // the nodes reachable from COs - Fpga_NodeVec_t * vMapping; // the nodes used in the current mapping - - // info about the original circuit - char * pFileName; // the file name - char ** ppOutputNames; // the primary output names - float * pInputArrivals;// the PI arrival times - - // mapping parameters - int nVarsMax; // the max number of variables - 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 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 - int nChoices; // the number of all choices - - int nCanons; - int nMatches; - - // the supergate library - Fpga_LutLib_t * pLutLib; // the current LUT library - - // the memory managers - Extra_MmFixed_t * mmNodes; // the memory manager for nodes - Extra_MmFixed_t * mmCuts; // the memory manager for cuts - - // resynthesis parameters - int fResynthesis; // the resynthesis flag - float fRequiredGlo; // the global required times - float fRequiredShift;// the shift of the required times - float fRequiredStart;// the starting global required times - float fRequiredGain; // the reduction in delay - float fAreaGlo; // the total area - float fAreaGain; // the reduction in area - float fEpsilon; // the epsilon used to compare floats - float fDelayWindow; // the delay window for delay-oriented resynthesis - float DelayLimit; // for resynthesis - float AreaLimit; // for resynthesis - float TimeLimit; // for resynthesis - - // runtime statistics - int timeToMap; // time to transfer to the mapping structure - int timeCuts; // time to compute k-feasible cuts - int timeTruth; // time to compute the truth table for each cut - int timeMatch; // time to perform matching for each node - int timeRecover; // time to perform area recovery - int timeToNet; // time to transfer back to the network - int timeTotal; // the total mapping time - int time1; // time to transfer to the mapping structure - int time2; // time to transfer to the mapping structure -}; - -// the LUT library -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][FPGA_MAX_LUTSIZE+1];// the delays of LUTs -}; - -// the mapping node -struct Fpga_NodeStruct_t_ -{ - // general information about the node - Fpga_Node_t * pNext; // the next node in the hash table - 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 - 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 - unsigned Value : 2; // the value of the nodes - unsigned fUsed : 1; // the flag indicating that the node is used in the mapping - unsigned fTemp : 1; // unused - unsigned Level :11; // the level of the given node - unsigned uData :14; // used to mark the fanins, for which resynthesis was tried - int TravId; - - // the successors of this node - Fpga_Node_t * p1; // the first child - Fpga_Node_t * p2; // the second child - Fpga_Node_t * pNextE; // the next functionally equivalent node - Fpga_Node_t * pRepr; // the representative of the functionally equivalent class - -#ifdef FPGA_ALLOCATE_FANOUT - // representation of node's fanouts - Fpga_Node_t * pFanPivot; // the first fanout of this node - Fpga_Node_t * pFanFanin1; // the next fanout of p1 - Fpga_Node_t * pFanFanin2; // the next fanout of p2 -// Fpga_NodeVec_t * vFanouts; // the array of fanouts of the gate -#endif - - // the delay information - float tRequired; // the best area flow - float aEstFanouts; // the fanout estimation - float Switching; // the probability of switching - int LValue; // the l-value of the node - short nLatches1; // the number of latches on the first edge - short nLatches2; // the number of latches on the second edge - - // cut information - Fpga_Cut_t * pCutBest; // the best mapping - Fpga_Cut_t * pCutOld; // the old mapping - Fpga_Cut_t * pCuts; // mapping choices for the node (elementary comes first) - Fpga_Cut_t * pCutsN; // mapping choices for the node (elementary comes first) - - // misc information - char * pData0; // temporary storage for the corresponding network node -}; - -// the cuts used for matching -struct Fpga_CutStruct_t_ -{ - Fpga_Cut_t * pOne; // the father of this cut - Fpga_Cut_t * pTwo; // the mother of this cut - Fpga_Node_t * pRoot; // the root of the cut - Fpga_Node_t * ppLeaves[FPGA_MAX_LEAVES+1]; // the leaves of this cut - float fLevel; // the average level of the fanins - unsigned uSign; // signature for quick comparison - char fMark; // the mark to denote visited cut - char Phase; // the mark to denote complemented cut - char nLeaves; // the number of leaves of this cut - char nVolume; // the volume of this cut - float tArrival; // the arrival time - float aFlow; // the area flow of the cut - Fpga_Cut_t * pNext; // the pointer to the next cut in the list -}; - -// the vector of nodes -struct Fpga_NodeVecStruct_t_ -{ - Fpga_Node_t ** pArray; // the array of nodes - int nSize; // the number of entries in the array - int nCap; // the number of allocated entries -}; - -// getting hold of the next fanout of the node -#define Fpga_NodeReadNextFanout( pNode, pFanout ) \ - ( ( pFanout == NULL )? NULL : \ - ((Fpga_Regular((pFanout)->p1) == (pNode))? \ - (pFanout)->pFanFanin1 : (pFanout)->pFanFanin2) ) - -// getting hold of the place where the next fanout will be attached -#define Fpga_NodeReadNextFanoutPlace( pNode, pFanout ) \ - ( (Fpga_Regular((pFanout)->p1) == (pNode))? \ - &(pFanout)->pFanFanin1 : &(pFanout)->pFanFanin2 ) - -// iterator through the fanouts of the node -#define Fpga_NodeForEachFanout( pNode, pFanout ) \ - for ( pFanout = (pNode)->pFanPivot; pFanout; \ - pFanout = Fpga_NodeReadNextFanout(pNode, pFanout) ) - -// safe iterator through the fanouts of the node -#define Fpga_NodeForEachFanoutSafe( pNode, pFanout, pFanout2 ) \ - for ( pFanout = (pNode)->pFanPivot, \ - pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout); \ - pFanout; \ - 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 DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/*=== fpgaCut.c ===============================================================*/ -extern void Fpga_MappingCuts( Fpga_Man_t * p ); -extern void Fpga_MappingCreatePiCuts( Fpga_Man_t * p ); -extern int Fpga_CutCountAll( Fpga_Man_t * pMan ); -/*=== fpgaCutUtils.c ===============================================================*/ -extern Fpga_Cut_t * Fpga_CutAlloc( Fpga_Man_t * p ); -extern Fpga_Cut_t * Fpga_CutDup( Fpga_Man_t * p, Fpga_Cut_t * pCutOld ); -extern void Fpga_CutFree( Fpga_Man_t * p, Fpga_Cut_t * pCut ); -extern void Fpga_CutPrint( Fpga_Man_t * p, Fpga_Node_t * pRoot, Fpga_Cut_t * pCut ); -extern Fpga_Cut_t * Fpga_CutCreateSimple( Fpga_Man_t * p, Fpga_Node_t * pNode ); -extern float Fpga_CutGetRootArea( Fpga_Man_t * p, Fpga_Cut_t * pCut ); -extern Fpga_Cut_t * Fpga_CutListAppend( Fpga_Cut_t * pSetAll, Fpga_Cut_t * pSets ); -extern void Fpga_CutListRecycle( Fpga_Man_t * p, Fpga_Cut_t * pSetList, Fpga_Cut_t * pSave ); -extern int Fpga_CutListCount( Fpga_Cut_t * pSets ); -extern void Fpga_CutRemoveFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ); -extern void Fpga_CutInsertFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ); -extern float Fpga_CutGetAreaRefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); -extern float Fpga_CutGetAreaDerefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); -extern float Fpga_CutRef( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); -extern float Fpga_CutDeref( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); -extern float Fpga_CutGetAreaFlow( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); -extern void Fpga_CutGetParameters( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); -/*=== fraigFanout.c =============================================================*/ -extern void Fpga_NodeAddFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanout ); -extern void Fpga_NodeRemoveFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanoutToRemove ); -extern int Fpga_NodeGetFanoutNum( Fpga_Node_t * pNode ); -/*=== fpgaLib.c ============================================================*/ -extern Fpga_LutLib_t * Fpga_LutLibCreate( char * FileName, int fVerbose ); -extern void Fpga_LutLibFree( Fpga_LutLib_t * p ); -extern void Fpga_LutLibPrint( Fpga_LutLib_t * pLutLib ); -extern int Fpga_LutLibDelaysAreDiscrete( Fpga_LutLib_t * pLutLib ); -/*=== fpgaMatch.c ===============================================================*/ -extern int Fpga_MappingMatches( Fpga_Man_t * p, int fDelayOriented ); -extern int Fpga_MappingMatchesArea( Fpga_Man_t * p ); -extern int Fpga_MappingMatchesSwitch( Fpga_Man_t * p ); -/*=== fpgaShow.c =============================================================*/ -extern void Fpga_MappingShow( Fpga_Man_t * pMan, char * pFileName ); -extern void Fpga_MappingShowNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppRoots, int nRoots, char * pFileName ); -/*=== fpgaSwitch.c =============================================================*/ -extern float Fpga_CutGetSwitchDerefed( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ); -extern float Fpga_CutRefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); -extern float Fpga_CutDerefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); -extern float Fpga_MappingGetSwitching( Fpga_Man_t * pMan, Fpga_NodeVec_t * vMapping ); -/*=== fpgaTime.c ===============================================================*/ -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, 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 ); -/*=== fpgaVec.c =============================================================*/ -extern Fpga_NodeVec_t * Fpga_NodeVecAlloc( int nCap ); -extern void Fpga_NodeVecFree( Fpga_NodeVec_t * p ); -extern Fpga_Node_t ** Fpga_NodeVecReadArray( Fpga_NodeVec_t * p ); -extern int Fpga_NodeVecReadSize( Fpga_NodeVec_t * p ); -extern void Fpga_NodeVecGrow( Fpga_NodeVec_t * p, int nCapMin ); -extern void Fpga_NodeVecShrink( Fpga_NodeVec_t * p, int nSizeNew ); -extern void Fpga_NodeVecClear( Fpga_NodeVec_t * p ); -extern void Fpga_NodeVecPush( Fpga_NodeVec_t * p, Fpga_Node_t * Entry ); -extern int Fpga_NodeVecPushUnique( Fpga_NodeVec_t * p, Fpga_Node_t * Entry ); -extern Fpga_Node_t * Fpga_NodeVecPop( Fpga_NodeVec_t * p ); -extern void Fpga_NodeVecWriteEntry( Fpga_NodeVec_t * p, int i, Fpga_Node_t * Entry ); -extern Fpga_Node_t * Fpga_NodeVecReadEntry( Fpga_NodeVec_t * p, int i ); -extern void Fpga_NodeVecSortByLevel( Fpga_NodeVec_t * p ); -extern void Fpga_SortNodesByArrivalTimes( Fpga_NodeVec_t * p ); -extern void Fpga_NodeVecUnion( Fpga_NodeVec_t * p, Fpga_NodeVec_t * p1, Fpga_NodeVec_t * p2 ); -extern void Fpga_NodeVecPushOrder( Fpga_NodeVec_t * vNodes, Fpga_Node_t * pNode, int fIncreasing ); -extern void Fpga_NodeVecReverse( Fpga_NodeVec_t * vNodes ); - -/*=== fpgaUtils.c ===============================================================*/ -extern Fpga_NodeVec_t * Fpga_MappingDfs( Fpga_Man_t * pMan, int fCollectEquiv ); -extern Fpga_NodeVec_t * Fpga_MappingDfsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes, int fEquiv ); -extern int Fpga_CountLevels( Fpga_Man_t * pMan ); -extern float Fpga_MappingGetAreaFlow( Fpga_Man_t * p ); -extern float Fpga_MappingArea( Fpga_Man_t * pMan ); -extern float Fpga_MappingAreaTrav( Fpga_Man_t * pMan ); -extern float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ); -extern void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p ); -extern void Fpga_MappingSetupTruthTables( unsigned uTruths[][2] ); -extern void Fpga_MappingSetupMask( unsigned uMask[], int nVarsMax ); -extern void Fpga_MappingSortByLevel( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes, int fIncreasing ); -extern Fpga_NodeVec_t * Fpga_DfsLim( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int nLevels ); -extern Fpga_NodeVec_t * Fpga_MappingLevelize( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes ); -extern int Fpga_MappingMaxLevel( Fpga_Man_t * pMan ); -extern void Fpga_ManReportChoices( Fpga_Man_t * pMan ); -extern void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan ); - -/*=== CUDD package.c ===============================================================*/ -extern unsigned int Cudd_Prime( unsigned int p ); - -#endif - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// diff --git a/abc70930/src/map/fpga/fpgaLib.c b/abc70930/src/map/fpga/fpgaLib.c deleted file mode 100644 index e74def32..00000000 --- a/abc70930/src/map/fpga/fpgaLib.c +++ /dev/null @@ -1,249 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaLib.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Technology mapping for variable-size-LUT FPGAs.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaLib.c,v 1.4 2005/01/23 06:59:41 alanmi Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// 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 [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_LutLib_t * Fpga_LutLibCreate( char * FileName, int fVerbose ) -{ - char pBuffer[1000], * pToken; - Fpga_LutLib_t * p; - FILE * pFile; - int i, k; - - pFile = fopen( FileName, "r" ); - if ( pFile == NULL ) - { - printf( "Cannot open LUT library file \"%s\".\n", FileName ); - return NULL; - } - - p = ALLOC( Fpga_LutLib_t, 1 ); - memset( p, 0, sizeof(Fpga_LutLib_t) ); - p->pName = Extra_UtilStrsav( FileName ); - - i = 1; - while ( fgets( pBuffer, 1000, pFile ) != NULL ) - { - pToken = strtok( pBuffer, " \t\n" ); - if ( pToken == NULL ) - continue; - if ( pToken[0] == '#' ) - continue; - if ( i != atoi(pToken) ) - { - printf( "Error in the LUT library file \"%s\".\n", FileName ); - free( p ); - return NULL; - } - - // read area - pToken = strtok( NULL, " \t\n" ); - p->pLutAreas[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 ); - 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 ); - } - - // 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; -} - -/**Function************************************************************* - - Synopsis [Duplicates the LUT library.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_LutLib_t * Fpga_LutLibDup( Fpga_LutLib_t * p ) -{ - Fpga_LutLib_t * pNew; - pNew = ALLOC( Fpga_LutLib_t, 1 ); - *pNew = *p; - pNew->pName = Extra_UtilStrsav( pNew->pName ); - return pNew; -} - -/**Function************************************************************* - - Synopsis [Frees the LUT library.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_LutLibFree( Fpga_LutLib_t * pLutLib ) -{ - if ( pLutLib == NULL ) - return; - FREE( pLutLib->pName ); - FREE( pLutLib ); -} - - -/**Function************************************************************* - - Synopsis [Prints the LUT library.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_LutLibPrint( Fpga_LutLib_t * pLutLib ) -{ - int i, k; - printf( "# The area/delay of k-variable LUTs:\n" ); - printf( "# k area delay\n" ); - 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************************************************************* - - Synopsis [Returns 1 if the delays are discrete.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_LutLibDelaysAreDiscrete( Fpga_LutLib_t * pLutLib ) -{ - float Delay; - int i; - for ( i = 1; i <= pLutLib->LutMax; i++ ) - { - Delay = pLutLib->pLutDelays[i][0]; - if ( ((float)((int)Delay)) != Delay ) - return 0; - } - return 1; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/abc70930/src/map/fpga/fpgaMatch.c b/abc70930/src/map/fpga/fpgaMatch.c deleted file mode 100644 index 73fa1258..00000000 --- a/abc70930/src/map/fpga/fpgaMatch.c +++ /dev/null @@ -1,794 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaMatch.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Technology mapping for variable-size-LUT FPGAs.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaMatch.c,v 1.7 2004/09/30 21:18:10 satrajit Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -static int Fpga_MatchNode( Fpga_Man_t * p, Fpga_Node_t * pNode, int fDelayOriented ); -static int Fpga_MatchNodeArea( Fpga_Man_t * p, Fpga_Node_t * pNode ); -static int Fpga_MatchNodeSwitch( Fpga_Man_t * p, Fpga_Node_t * pNode ); - -static Fpga_Cut_t * Fpga_MappingAreaWithoutNode( Fpga_Man_t * p, Fpga_Node_t * pFanout, Fpga_Node_t * pNodeNo ); -static int Fpga_MappingMatchesAreaArray( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ); - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Finds the best delay assignment of LUTs.] - - Description [This procedure iterates through all the nodes - of the object graph reachable from the POs and assigns the best - match to each of them. If the flag fDelayOriented is set to 1, it - tries to minimize the arrival time and uses the area flow as a - tie-breaker. If the flag is set to 0, it considers all the cuts, - whose arrival times matches the required time at the node, and - minimizes the area flow using the arrival time as a tie-breaker. - - Before this procedure is called, the required times should be set - and the fanout counts should be computed. In the first iteration, - the required times are set to very large number (by NodeCreate) - and the fanout counts are set to the number of fanouts in the AIG. - In the following iterations, the required times are set by the - backward traversal, while the fanouts are estimated approximately. - - If the arrival times of the PI nodes are given, they should be - assigned to the PIs after the cuts are computed and before this - procedure is called for the first time.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MappingMatches( Fpga_Man_t * p, int fDelayOriented ) -{ - ProgressBar * pProgress; - Fpga_Node_t * pNode; - int i, nNodes; - - // assign the arrival times of the PIs - for ( i = 0; i < p->nInputs; i++ ) - p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i]; - - // match LUTs with nodes in the topological order - nNodes = p->vAnds->nSize; - pProgress = Extra_ProgressBarStart( stdout, nNodes ); - for ( i = 0; i < nNodes; i++ ) - { - pNode = p->vAnds->pArray[i]; - if ( !Fpga_NodeIsAnd( pNode ) ) - continue; - // skip a secondary node - if ( pNode->pRepr ) - continue; - // match the node - Fpga_MatchNode( p, pNode, 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; -} - -/**Function************************************************************* - - Synopsis [Computes the best matching for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MatchNode( Fpga_Man_t * p, Fpga_Node_t * pNode, int fDelayOriented ) -{ - Fpga_Cut_t * pCut, * pCutBestOld; - int clk; - // make sure that at least one cut other than the trivial is present - if ( pNode->pCuts->pNext == NULL ) - { - printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" ); - return 0; - } - - // estimate the fanouts of the node - if ( pNode->aEstFanouts < 0 ) - pNode->aEstFanouts = (float)pNode->nRefs; - else - pNode->aEstFanouts = (float)((2.0 * pNode->aEstFanouts + pNode->nRefs) / 3.0); -// pNode->aEstFanouts = (float)pNode->nRefs; - - pCutBestOld = pNode->pCutBest; - pNode->pCutBest = NULL; - for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) - { - // compute the arrival time of the cut and its area flow -clk = clock(); - Fpga_CutGetParameters( p, pCut ); -//p->time2 += clock() - clk; - // drop the cut if it does not meet the required times - if ( Fpga_FloatMoreThan(p, pCut->tArrival, pNode->tRequired) ) - continue; - // if no cut is assigned, use the current one - if ( pNode->pCutBest == NULL ) - { - pNode->pCutBest = pCut; - continue; - } - // choose the best cut using one of the two criteria: - // (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 && - (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 && - (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; - } - } - - // make sure the match is found - if ( pNode->pCutBest == NULL ) - { - if ( pCutBestOld == NULL ) - { -// printf( "\nError: Could not match a node in the object graph.\n" ); - return 0; - } - pNode->pCutBest = pCutBestOld; - } - return 1; -} - - - - - -/**Function************************************************************* - - Synopsis [Finds the best area assignment of LUTs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MappingMatchesArea( Fpga_Man_t * p ) -{ - ProgressBar * pProgress; - Fpga_Node_t * pNode; - int i, nNodes; - - // assign the arrival times of the PIs - for ( i = 0; i < p->nInputs; i++ ) - p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i]; - - // match LUTs with nodes in the topological order - nNodes = p->vAnds->nSize; - pProgress = Extra_ProgressBarStart( stdout, nNodes ); - for ( i = 0; i < nNodes; i++ ) - { - pNode = p->vAnds->pArray[i]; - if ( !Fpga_NodeIsAnd( pNode ) ) - continue; - // skip a secondary node - if ( pNode->pRepr ) - continue; - // match the node - Fpga_MatchNodeArea( p, pNode ); - Extra_ProgressBarUpdate( pProgress, i, "Matches ..." ); - } - Extra_ProgressBarStop( pProgress ); - return 1; -} - -/**Function************************************************************* - - Synopsis [Finds the best area assignment of LUTs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MappingMatchesAreaArray( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ) -{ - Fpga_Node_t * pNode; - int i; - - // match LUTs with nodes in the topological order - for ( i = 0; i < vNodes->nSize; i++ ) - { - pNode = vNodes->pArray[i]; - if ( !Fpga_NodeIsAnd( pNode ) ) - continue; - // skip a secondary node - if ( pNode->pRepr ) - continue; - // match the node - if ( !Fpga_MatchNodeArea( p, pNode ) ) - return 0; - } - return 1; -} - -/**Function************************************************************* - - Synopsis [Computes the best matching for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MatchNodeArea( Fpga_Man_t * p, Fpga_Node_t * pNode ) -{ - Fpga_Cut_t * pCut, * pCutBestOld; - float aAreaCutBest; - int clk; - // make sure that at least one cut other than the trivial is present - if ( pNode->pCuts->pNext == NULL ) - { - printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" ); - return 0; - } - - // remember the old cut - pCutBestOld = pNode->pCutBest; - // deref the old cut - if ( pNode->nRefs ) - aAreaCutBest = Fpga_CutDeref( p, pNode, pNode->pCutBest, 0 ); - - // search for a better cut - pNode->pCutBest = NULL; - for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) - { - // compute the arrival time of the cut and its area flow -clk = clock(); - pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut ); -//p->time2 += clock() - clk; - // drop the cut if it does not meet the required times - if ( Fpga_FloatMoreThan( p, pCut->tArrival, pNode->tRequired ) ) - continue; - // get the area of this cut - pCut->aFlow = Fpga_CutGetAreaDerefed( p, pCut ); - // if no cut is assigned, use the current one - if ( pNode->pCutBest == NULL ) - { - pNode->pCutBest = pCut; - continue; - } - // choose the best cut as follows: exact area first, delay as a tie-breaker - 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; - } - } - - // make sure the match is found - if ( pNode->pCutBest == NULL ) - { - pNode->pCutBest = pCutBestOld; - // insert the new cut - if ( pNode->nRefs ) - pNode->pCutBest->aFlow = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 ); -// printf( "\nError: Could not match a node in the object graph.\n" ); - return 0; - } - - // insert the new cut - // make sure the area selected is not worse then the original area - if ( pNode->nRefs ) - { - pNode->pCutBest->aFlow = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 ); -// assert( pNode->pCutBest->aFlow <= aAreaCutBest ); -// assert( pNode->tRequired < FPGA_FLOAT_LARGE ); - } - return 1; -} - - - - -/**Function************************************************************* - - Synopsis [Finds the best area assignment of LUTs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MappingMatchesSwitch( Fpga_Man_t * p ) -{ - ProgressBar * pProgress; - Fpga_Node_t * pNode; - int i, nNodes; - - // assign the arrival times of the PIs - for ( i = 0; i < p->nInputs; i++ ) - p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i]; - - // match LUTs with nodes in the topological order - nNodes = p->vAnds->nSize; - pProgress = Extra_ProgressBarStart( stdout, nNodes ); - for ( i = 0; i < nNodes; i++ ) - { - pNode = p->vAnds->pArray[i]; - if ( !Fpga_NodeIsAnd( pNode ) ) - continue; - // skip a secondary node - if ( pNode->pRepr ) - continue; - // match the node - Fpga_MatchNodeSwitch( p, pNode ); - Extra_ProgressBarUpdate( pProgress, i, "Matches ..." ); - } - Extra_ProgressBarStop( pProgress ); - return 1; -} - -/**Function************************************************************* - - Synopsis [Computes the best matching for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MatchNodeSwitch( Fpga_Man_t * p, Fpga_Node_t * pNode ) -{ - Fpga_Cut_t * pCut, * pCutBestOld; - float aAreaCutBest; - int clk; - // make sure that at least one cut other than the trivial is present - if ( pNode->pCuts->pNext == NULL ) - { - printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" ); - return 0; - } - - // remember the old cut - pCutBestOld = pNode->pCutBest; - // deref the old cut - if ( pNode->nRefs ) - aAreaCutBest = Fpga_CutDerefSwitch( p, pNode, pNode->pCutBest, 0 ); - - // search for a better cut - pNode->pCutBest = NULL; - for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) - { - // compute the arrival time of the cut and its area flow -clk = clock(); - pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut ); -//p->time2 += clock() - clk; - // drop the cut if it does not meet the required times - if ( Fpga_FloatMoreThan( p, pCut->tArrival, pNode->tRequired ) ) - continue; - // get the area of this cut - pCut->aFlow = Fpga_CutGetSwitchDerefed( p, pNode, pCut ); - // if no cut is assigned, use the current one - if ( pNode->pCutBest == NULL ) - { - pNode->pCutBest = pCut; - continue; - } - // choose the best cut as follows: exact area first, delay as a tie-breaker - 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; - } - } - - // make sure the match is found - if ( pNode->pCutBest == NULL ) - { - pNode->pCutBest = pCutBestOld; - // insert the new cut - if ( pNode->nRefs ) - pNode->pCutBest->aFlow = Fpga_CutRefSwitch( p, pNode, pNode->pCutBest, 0 ); -// printf( "\nError: Could not match a node in the object graph.\n" ); - return 0; - } - - // insert the new cut - // make sure the area selected is not worse then the original area - if ( pNode->nRefs ) - { - pNode->pCutBest->aFlow = Fpga_CutRefSwitch( p, pNode, pNode->pCutBest, 0 ); - assert( pNode->pCutBest->aFlow <= aAreaCutBest + 0.001 ); -// assert( pNode->tRequired < FPGA_FLOAT_LARGE ); - } - return 1; -} - - -#if 0 -/**function************************************************************* - - synopsis [References the cut.] - - description [This procedure is similar to the procedure NodeReclaim.] - - sideeffects [] - - seealso [] - -***********************************************************************/ -void Fpga_Experiment( Fpga_Man_t * p ) -{ - int Counter[10] = {0}; - Fpga_Node_t * pNode; - int i; - - for ( i = 0; i < p->nOutputs; i++ ) - { - pNode = Fpga_Regular(p->pOutputs[i]); - pNode->vFanouts = NULL; - } - - for ( i = 0; i < p->vAnds->nSize; i++ ) - { - pNode = p->vAnds->pArray[i]; - if ( !Fpga_NodeIsAnd( pNode ) ) - continue; - if ( pNode->vFanouts == NULL ) - continue; - if ( pNode->vFanouts->nSize >= 10 ) - continue; - Counter[pNode->vFanouts->nSize]++; - } - - printf( "Fanout stats: " ); - for ( i = 0; i < 10; i++ ) - printf( " %d=%d", i, Counter[i] ); - printf( "\n" ); - printf( "Area before = %4.2f.\n", Fpga_MappingArea(p) ); - - for ( i = 0; i < p->vAnds->nSize; i++ ) - { - Fpga_NodeVec_t * vNodesTfo; - float AreaBefore; - - pNode = p->vAnds->pArray[i]; - if ( !Fpga_NodeIsAnd( pNode ) ) - continue; - if ( pNode->vFanouts == NULL ) - continue; - if ( pNode->vFanouts->nSize != 1 && pNode->vFanouts->nSize != 2 && pNode->vFanouts->nSize != 3 ) - continue; - -// assert( pNode->nRefs > 0 ); - if ( pNode->nRefs == 0 ) - continue; - - AreaBefore = pNode->pCutBest->aFlow; - pNode->pCutBest->aFlow = FPGA_FLOAT_LARGE; - - Fpga_TimeComputeRequiredGlobal( p, 0 ); - - vNodesTfo = Fpga_CollectNodeTfo( p, pNode ); - if ( Fpga_MappingMatchesAreaArray( p, vNodesTfo ) == 0 ) - printf( "attempt failed\n" ); - else - printf( "attempt succeeded\n" ); - Fpga_NodeVecFree( vNodesTfo ); - - pNode->pCutBest->aFlow = AreaBefore; -// break; - } - printf( "Area after = %4.2f.\n", Fpga_MappingArea(p) ); -// printf( "AREA GAIN = %4.2f (%.2f %%)\n", GainTotal, 100.0 * GainTotal / Fpga_MappingArea(p) ); -} - - - -/**function************************************************************* - - synopsis [References the cut.] - - description [This procedure is similar to the procedure NodeReclaim.] - - sideeffects [] - - seealso [] - -***********************************************************************/ -void Fpga_Experiment2( Fpga_Man_t * p ) -{ - int Counter[10] = {0}; - Fpga_Cut_t * ppCutsNew[10]; - Fpga_Cut_t * ppCutsOld[10]; - Fpga_Node_t * pFanout, * pNode; - float Gain, Loss, GainTotal, Area1, Area2; - int i, k; - - for ( i = 0; i < p->nOutputs; i++ ) - { - pNode = Fpga_Regular(p->pOutputs[i]); - pNode->vFanouts = NULL; - } - - for ( i = 0; i < p->vAnds->nSize; i++ ) - { - pNode = p->vAnds->pArray[i]; - if ( !Fpga_NodeIsAnd( pNode ) ) - continue; - if ( pNode->vFanouts == NULL ) - continue; - if ( pNode->vFanouts->nSize >= 10 ) - continue; - Counter[pNode->vFanouts->nSize]++; - } - - printf( "Fanout stats: " ); - for ( i = 0; i < 10; i++ ) - printf( " %d=%d", i, Counter[i] ); - printf( "\n" ); - printf( "Area before = %4.2f.\n", Fpga_MappingArea(p) ); - - GainTotal = 0; - for ( i = 0; i < p->vAnds->nSize; i++ ) - { - pNode = p->vAnds->pArray[i]; - if ( !Fpga_NodeIsAnd( pNode ) ) - continue; - if ( pNode->vFanouts == NULL ) - continue; - if ( pNode->vFanouts->nSize != 2 )//&& pNode->vFanouts->nSize != 2 && pNode->vFanouts->nSize != 3 ) - continue; - - assert( pNode->nRefs > 0 ); - - // for all fanouts, find the best cut without this node - for ( k = 0; k < pNode->vFanouts->nSize; k++ ) - { - pFanout = pNode->vFanouts->pArray[k]; - ppCutsOld[k] = pFanout->pCutBest; - ppCutsNew[k] = Fpga_MappingAreaWithoutNode( p, pFanout, pNode ); - if ( ppCutsNew[k] == NULL ) - break; - } - if ( k != pNode->vFanouts->nSize ) - { - printf( "Node %4d: Skipped.\n", pNode->Num ); - continue; - } - - - // compute the area after replacing all the cuts - Gain = 0; - for ( k = 0; k < pNode->vFanouts->nSize; k++ ) - { - pFanout = pNode->vFanouts->pArray[k]; - // deref old cut - Area1 = Fpga_MatchAreaDeref( p, ppCutsOld[k] ); - // assign new cut - pFanout->pCutBest = ppCutsNew[k]; - // ref new cut - Area2 = Fpga_MatchAreaRef( p, ppCutsNew[k] ); - // compute the gain - Gain += Area1 - Area2; - } - - printf( "%d ", pNode->nRefs ); - - // undo the whole thing - Loss = 0; - for ( k = 0; k < pNode->vFanouts->nSize; k++ ) - { - pFanout = pNode->vFanouts->pArray[k]; - // deref old cut - Area1 = Fpga_MatchAreaDeref( p, ppCutsNew[k] ); - // assign new cut - pFanout->pCutBest = ppCutsOld[k]; - // ref new cut - Area2 = Fpga_MatchAreaRef( p, ppCutsOld[k] ); - // compute the gain - Loss += Area2 - Area1; - } - assert( Gain == Loss ); - - - printf( "Node %4d: Fanouts = %d. Cut area = %4.2f. Gain = %4.2f.\n", - pNode->Num, pNode->nRefs, pNode->pCutBest->aFlow, Gain ); - - if ( Gain > 0 ) - GainTotal += Gain; - } - printf( "Area after = %4.2f.\n", Fpga_MappingArea(p) ); - printf( "AREA GAIN = %4.2f (%.2f %%)\n", GainTotal, 100.0 * GainTotal / Fpga_MappingArea(p) ); -} - - -/**function************************************************************* - - synopsis [Computes the loss of area when node is not allowed.] - - description [Returning FPGA_FLOAT_LARGE means it does not exist.] - - sideeffects [] - - seealso [] - -***********************************************************************/ -Fpga_Cut_t * Fpga_MappingAreaWithoutNode( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Node_t * pNodeNo ) -{ - Fpga_Cut_t * pCut, * pCutBestOld, * pCutRes; - float aAreaCutBest; - int i, clk; - // make sure that at least one cut other than the trivial is present - if ( pNode->pCuts->pNext == NULL ) - { - printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" ); - return 0; - } - - assert( pNode->nRefs > 0 ); - - // remember the old cut - pCutBestOld = pNode->pCutBest; - // deref the old cut - aAreaCutBest = Fpga_MatchAreaDeref( p, pNode->pCutBest ); - - // search for a better cut - pNode->pCutBest = NULL; - for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) - { - // compute the arrival time of the cut and its area flow -clk = clock(); - Fpga_MatchCutGetArrTime( p, pCut ); -//p->time2 += clock() - clk; - // drop the cut if it does not meet the required times - if ( pCut->tArrival > pNode->tRequired ) - continue; - - // skip the cut if it contains the no-node - for ( i = 0; i < pCut->nLeaves; i++ ) - if ( pCut->ppLeaves[i] == pNodeNo ) - break; - if ( i != pCut->nLeaves ) - continue; - - // get the area of this cut - pCut->aFlow = Fpga_MatchAreaCount( p, pCut ); - // if no cut is assigned, use the current one - if ( pNode->pCutBest == NULL ) - { - pNode->pCutBest = pCut; - 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 ) - { - pNode->pCutBest = pCut; - } - } - - // make sure the match is found - if ( pNode->pCutBest == NULL ) - { - pNode->pCutBest = pCutBestOld; - // insert the new cut - pNode->pCutBest->aFlow = Fpga_MatchAreaRef( p, pNode->pCutBest ); - return NULL; - } - - pCutRes = pNode->pCutBest; - pNode->pCutBest = pCutBestOld; - - // insert the new cut - pNode->pCutBest->aFlow = Fpga_MatchAreaRef( p, pNode->pCutBest ); - - // make sure the area selected is not worse then the original area - assert( pNode->pCutBest->aFlow == aAreaCutBest ); - assert( pNode->tRequired < FPGA_FLOAT_LARGE ); - return pCutRes; -} - -#endif - - -/**function************************************************************* - - synopsis [Performs area minimization using a heuristic algorithm.] - - description [] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_FindBestNode( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes, Fpga_Node_t ** ppNode, Fpga_Cut_t ** ppCutBest ) -{ - Fpga_Node_t * pNode; - Fpga_Cut_t * pCut; - float Gain, CutArea1, CutArea2, CutArea3; - int i; - - Gain = 0; - for ( i = 0; i < vNodes->nSize; i++ ) - { - pNode = vNodes->pArray[i]; - // deref the current cut - CutArea1 = Fpga_CutDeref( p, pNode, pNode->pCutBest, 0 ); - - // ref all the cuts - for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) - { - if ( pCut == pNode->pCutBest ) - continue; - if ( pCut->tArrival > pNode->tRequired ) - continue; - - CutArea2 = Fpga_CutGetAreaDerefed( p, pCut ); - if ( Gain < CutArea1 - CutArea2 ) - { - *ppNode = pNode; - *ppCutBest = pCut; - Gain = CutArea1 - CutArea2; - } - } - // ref the old cut - CutArea3 = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 ); - assert( CutArea1 == CutArea3 ); - } - if ( Gain == 0 ) - printf( "Returning no gain.\n" ); - - return Gain; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// diff --git a/abc70930/src/map/fpga/fpgaSwitch.c b/abc70930/src/map/fpga/fpgaSwitch.c deleted file mode 100644 index c93e0de4..00000000 --- a/abc70930/src/map/fpga/fpgaSwitch.c +++ /dev/null @@ -1,151 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaSwitch.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Generic technology mapping engine.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - September 8, 2003.] - - Revision [$Id: fpgaSwitch.h,v 1.0 2003/09/08 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**function************************************************************* - - synopsis [Computes the exact area associated with the cut.] - - description [] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutGetSwitchDerefed( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ) -{ - float aResult, aResult2; - aResult2 = Fpga_CutRefSwitch( pMan, pNode, pCut, 0 ); - aResult = Fpga_CutDerefSwitch( pMan, pNode, pCut, 0 ); -// assert( aResult == aResult2 ); - return aResult; -} - -/**function************************************************************* - - synopsis [References the cut.] - - description [This procedure is similar to the procedure NodeReclaim.] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutRefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ) -{ - Fpga_Node_t * pNodeChild; - float aArea; - int i; - // start the area of this cut - aArea = pNode->Switching; - if ( pCut->nLeaves == 1 ) - return aArea; - // go through the children - for ( i = 0; i < pCut->nLeaves; i++ ) - { - pNodeChild = pCut->ppLeaves[i]; - assert( pNodeChild->nRefs >= 0 ); - if ( pNodeChild->nRefs++ > 0 ) - continue; - aArea += Fpga_CutRefSwitch( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts ); - } - return aArea; -} - -/**function************************************************************* - - synopsis [Dereferences the cut.] - - description [This procedure is similar to the procedure NodeRecusiveDeref.] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutDerefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ) -{ - Fpga_Node_t * pNodeChild; - float aArea; - int i; - // start the area of this cut - aArea = pNode->Switching; - if ( pCut->nLeaves == 1 ) - return aArea; - // go through the children - for ( i = 0; i < pCut->nLeaves; i++ ) - { - pNodeChild = pCut->ppLeaves[i]; - assert( pNodeChild->nRefs > 0 ); - if ( --pNodeChild->nRefs > 0 ) - continue; - aArea += Fpga_CutDerefSwitch( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts ); - } - return aArea; -} - -/**Function************************************************************* - - Synopsis [Computes the array of mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Fpga_MappingGetSwitching( Fpga_Man_t * pMan, Fpga_NodeVec_t * vMapping ) -{ - Fpga_Node_t * pNode; - float Switch; - int i; - Switch = 0.0; - for ( i = 0; i < vMapping->nSize; i++ ) - { - pNode = vMapping->pArray[i]; - // at least one phase has the best cut assigned - assert( !Fpga_NodeIsAnd(pNode) || pNode->pCutBest != NULL ); - // at least one phase is used in the mapping - assert( pNode->nRefs > 0 ); - // compute the array due to the supergate - Switch += pNode->Switching; - } - // 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; - return Switch; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/abc70930/src/map/fpga/fpgaTime.c b/abc70930/src/map/fpga/fpgaTime.c deleted file mode 100644 index 879cad4d..00000000 --- a/abc70930/src/map/fpga/fpgaTime.c +++ /dev/null @@ -1,262 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaTime.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Technology mapping for variable-size-LUT FPGAs.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaTime.c,v 1.1 2005/01/23 06:59:42 alanmi Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Computes the arrival times of the cut.] - - Description [Computes the maximum arrival time of the cut leaves and - adds the delay of the LUT.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Fpga_TimeCutComputeArrival( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) -{ - int i; - float tArrival; - tArrival = -FPGA_FLOAT_LARGE; - 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][0]; - return tArrival; -} - -/**Function************************************************************* - - Synopsis [Computes the arrival times of the cut recursively.] - - Description [When computing the arrival time for the previously unused - cuts, their arrival time may be incorrect because their fanins have - incorrect arrival time. This procedure is called to fix this problem.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Fpga_TimeCutComputeArrival_rec( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) -{ - int i; - for ( i = 0; i < pCut->nLeaves; i++ ) - if ( pCut->ppLeaves[i]->nRefs == 0 ) - Fpga_TimeCutComputeArrival_rec( pMan, pCut->ppLeaves[i]->pCutBest ); - return Fpga_TimeCutComputeArrival( pMan, pCut ); -} - -/**Function************************************************************* - - Synopsis [Computes the maximum arrival times.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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; - if ( p->fLatchPaths ) - { - 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; -} - -/**Function************************************************************* - - Synopsis [Computes the required times of all nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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 ); -} - -/**Function************************************************************* - - Synopsis [Computes the required times of all nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_TimeComputeRequired( Fpga_Man_t * p, float fRequired ) -{ - int i; - // clean the required times and the fanout counts for all nodes - for ( i = 0; i < p->vAnds->nSize; i++ ) - p->vAnds->pArray[i]->tRequired = FPGA_FLOAT_LARGE; - // set the required times for the POs - 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************************************************************* - - Synopsis [Computes the required times of the given nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_TimePropagateRequired( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ) -{ - Fpga_Node_t * pNode, * pChild; - float fRequired; - int i, k; - - // sorts the nodes in the decreasing order of levels -// Fpga_MappingSortByLevel( p, vNodes, 0 ); - // the nodes area already sorted in Fpga_MappingSetRefsAndArea() - - // go through the nodes in the reverse topological order - for ( k = 0; k < vNodes->nSize; k++ ) - { - pNode = vNodes->pArray[k]; - if ( !Fpga_NodeIsAnd(pNode) ) - continue; - // get the required time for children - 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++ ) - { - pChild = pNode->pCutBest->ppLeaves[i]; - pChild->tRequired = FPGA_MIN( pChild->tRequired, fRequired ); - } - } -} - - - -/**Function************************************************************* - - Synopsis [Computes the required times of all nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_TimePropagateArrival( Fpga_Man_t * p ) -{ - Fpga_Node_t * pNode; - Fpga_Cut_t * pCut; - int i; - - // clean the required times and the fanout counts for all nodes - for ( i = 0; i < p->vAnds->nSize; i++ ) - { - pNode = p->vAnds->pArray[i]; - for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) - pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut ); - } -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/abc70930/src/map/fpga/fpgaTruth.c b/abc70930/src/map/fpga/fpgaTruth.c deleted file mode 100644 index e3eb487f..00000000 --- a/abc70930/src/map/fpga/fpgaTruth.c +++ /dev/null @@ -1,166 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaTruth.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Technology mapping for variable-size-LUT FPGAs.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaTruth.c,v 1.4 2005/01/23 06:59:42 alanmi Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" -#include "cudd.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Recursively derives the truth table for the cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -DdNode * Fpga_TruthsCutBdd_rec( DdManager * dd, Fpga_Cut_t * pCut, Fpga_NodeVec_t * vVisited ) -{ - DdNode * bFunc, * bFunc0, * bFunc1; - assert( !Fpga_IsComplement(pCut) ); - // if the cut is visited, return the result - if ( pCut->uSign ) - return (DdNode *)pCut->uSign; - // compute the functions of the children - bFunc0 = Fpga_TruthsCutBdd_rec( dd, Fpga_CutRegular(pCut->pOne), vVisited ); Cudd_Ref( bFunc0 ); - bFunc0 = Cudd_NotCond( bFunc0, Fpga_CutIsComplement(pCut->pOne) ); - bFunc1 = Fpga_TruthsCutBdd_rec( dd, Fpga_CutRegular(pCut->pTwo), vVisited ); Cudd_Ref( bFunc1 ); - bFunc1 = Cudd_NotCond( bFunc1, Fpga_CutIsComplement(pCut->pTwo) ); - // get the function of the cut - bFunc = Cudd_bddAnd( dd, bFunc0, bFunc1 ); Cudd_Ref( bFunc ); - bFunc = Cudd_NotCond( bFunc, pCut->Phase ); - Cudd_RecursiveDeref( dd, bFunc0 ); - Cudd_RecursiveDeref( dd, bFunc1 ); - assert( pCut->uSign == 0 ); - pCut->uSign = (unsigned)bFunc; - // add this cut to the visited list - Fpga_NodeVecPush( vVisited, (Fpga_Node_t *)pCut ); - return bFunc; -} - -/**Function************************************************************* - - Synopsis [Derives the truth table for one cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void * Fpga_TruthsCutBdd( void * dd, Fpga_Cut_t * pCut ) -{ - Fpga_NodeVec_t * vVisited; - DdNode * bFunc; - int i; - assert( pCut->nLeaves > 1 ); - // set the leaf variables - for ( i = 0; i < pCut->nLeaves; i++ ) - pCut->ppLeaves[i]->pCuts->uSign = (unsigned)Cudd_bddIthVar( dd, i ); - // recursively compute the function - vVisited = Fpga_NodeVecAlloc( 10 ); - bFunc = Fpga_TruthsCutBdd_rec( dd, pCut, vVisited ); Cudd_Ref( bFunc ); - // clean the intermediate BDDs - for ( i = 0; i < pCut->nLeaves; i++ ) - pCut->ppLeaves[i]->pCuts->uSign = 0; - for ( i = 0; i < vVisited->nSize; i++ ) - { - pCut = (Fpga_Cut_t *)vVisited->pArray[i]; - 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/abc70930/src/map/fpga/fpgaUtils.c b/abc70930/src/map/fpga/fpgaUtils.c deleted file mode 100644 index b951fd8f..00000000 --- a/abc70930/src/map/fpga/fpgaUtils.c +++ /dev/null @@ -1,986 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaUtils.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Technology mapping for variable-size-LUT FPGAs.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaUtils.c,v 1.3 2004/07/06 04:55:58 alanmi Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -#define FPGA_CO_LIST_SIZE 5 - -static void Fpga_MappingDfs_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes, int fCollectEquiv ); -static void Fpga_MappingDfsCuts_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes ); -static int Fpga_MappingCompareOutputDelay( Fpga_Node_t ** ppNode1, Fpga_Node_t ** ppNode2 ); -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 DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - - -/**Function************************************************************* - - Synopsis [Computes the DFS ordering of the nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_NodeVec_t * Fpga_MappingDfs( Fpga_Man_t * pMan, int fCollectEquiv ) -{ - 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 - for ( i = 0; i < pMan->nInputs; i++ ) - { - pNode = pMan->pInputs[i]; - Fpga_NodeVecPush( vNodes, pNode ); - pNode->fMark0 = 1; - } - // 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; -} - -/**Function************************************************************* - - Synopsis [Recursively computes the DFS ordering of the nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingDfs_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes, int fCollectEquiv ) -{ - assert( !Fpga_IsComplement(pNode) ); - if ( pNode->fMark0 ) - return; - // visit the transitive fanin - if ( Fpga_NodeIsAnd(pNode) ) - { - Fpga_MappingDfs_rec( Fpga_Regular(pNode->p1), vNodes, fCollectEquiv ); - Fpga_MappingDfs_rec( Fpga_Regular(pNode->p2), vNodes, fCollectEquiv ); - } - // visit the equivalent nodes - if ( fCollectEquiv && pNode->pNextE ) - Fpga_MappingDfs_rec( pNode->pNextE, vNodes, fCollectEquiv ); - // make sure the node is not visited through the equivalent nodes - assert( pNode->fMark0 == 0 ); - // mark the node as visited - pNode->fMark0 = 1; - // add the node to the list - Fpga_NodeVecPush( vNodes, pNode ); -} - -/**Function************************************************************* - - Synopsis [Computes the DFS ordering of the nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_NodeVec_t * Fpga_MappingDfsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes, int fEquiv ) -{ - Fpga_NodeVec_t * vNodes; - int i; - // perform the traversal - vNodes = Fpga_NodeVecAlloc( 200 ); - for ( i = 0; i < nNodes; i++ ) - Fpga_MappingDfs_rec( ppNodes[i], vNodes, fEquiv ); - for ( i = 0; i < vNodes->nSize; i++ ) - vNodes->pArray[i]->fMark0 = 0; - return vNodes; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Fpga_MappingGetAreaFlow( Fpga_Man_t * p ) -{ - float aFlowFlowTotal = 0; - int i; - for ( i = 0; i < p->nOutputs; i++ ) - { - if ( Fpga_NodeIsConst(p->pOutputs[i]) ) - continue; - aFlowFlowTotal += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow; - } - return aFlowFlowTotal; -} - -/**Function************************************************************* - - Synopsis [Computes the area of the current mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Fpga_MappingArea( Fpga_Man_t * pMan ) -{ - Fpga_Node_t * pNode; - float aTotal; - int i; - // perform the traversal - aTotal = 0; - for ( i = 0; i < pMan->vMapping->nSize; i++ ) - { - pNode = pMan->vMapping->pArray[i]; - aTotal += pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves]; - } - return aTotal; -} - -/**Function************************************************************* - - Synopsis [Recursively computes the DFS ordering of the nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Fpga_MappingArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes ) -{ - float aArea; - int i; - assert( !Fpga_IsComplement(pNode) ); - if ( !Fpga_NodeIsAnd(pNode) ) - return 0; - if ( pNode->fMark0 ) - return 0; - assert( pNode->pCutBest != NULL ); - // visit the transitive fanin of the selected cut - aArea = 0; - for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) - aArea += Fpga_MappingArea_rec( pMan, pNode->pCutBest->ppLeaves[i], vNodes ); - // make sure the node is not visited through the fanin nodes - assert( pNode->fMark0 == 0 ); - // mark the node as visited - pNode->fMark0 = 1; - // add the node to the list - aArea += pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves]; - // add the node to the list - Fpga_NodeVecPush( vNodes, pNode ); - return aArea; -} - -/**Function************************************************************* - - Synopsis [Computes the area of the current mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Fpga_MappingAreaTrav( Fpga_Man_t * pMan ) -{ - Fpga_NodeVec_t * vNodes; - float aTotal; - int i; - // perform the traversal - aTotal = 0; - vNodes = Fpga_NodeVecAlloc( 100 ); - for ( i = 0; i < pMan->nOutputs; i++ ) - aTotal += Fpga_MappingArea_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), vNodes ); - for ( i = 0; i < vNodes->nSize; i++ ) - vNodes->pArray[i]->fMark0 = 0; - Fpga_NodeVecFree( vNodes ); - return aTotal; -} - - -/**Function************************************************************* - - Synopsis [Recursively computes the DFS ordering of the nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Fpga_MappingSetRefsAndArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Node_t ** ppStore ) -{ - float aArea; - int i; - assert( !Fpga_IsComplement(pNode) ); - if ( pNode->nRefs++ ) - return 0; - if ( !Fpga_NodeIsAnd(pNode) ) - return 0; - assert( pNode->pCutBest != NULL ); - // store the node in the structure by level - pNode->pData0 = (char *)ppStore[pNode->Level]; - ppStore[pNode->Level] = pNode; - // visit the transitive fanin of the selected cut - aArea = pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves]; - for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) - aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode->pCutBest->ppLeaves[i], ppStore ); - return aArea; -} - -/**Function************************************************************* - - Synopsis [Sets the correct reference counts for the mapping.] - - Description [Collects the nodes in reverse topological order - and places in them in array pMan->vMapping.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ) -{ - Fpga_Node_t * pNode, ** ppStore; - float aArea; - int i, LevelMax; - - // clean all references - for ( i = 0; i < pMan->vNodesAll->nSize; i++ ) - pMan->vNodesAll->pArray[i]->nRefs = 0; - - // allocate place to store the nodes - LevelMax = Fpga_MappingMaxLevel( pMan ); - ppStore = ALLOC( Fpga_Node_t *, LevelMax + 1 ); - memset( ppStore, 0, sizeof(Fpga_Node_t *) * (LevelMax + 1) ); - - // collect nodes reachable from POs in the DFS order through the best cuts - aArea = 0; - for ( i = 0; i < pMan->nOutputs; i++ ) - { - pNode = Fpga_Regular(pMan->pOutputs[i]); - if ( pNode == pMan->pConst1 ) - continue; - aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode, ppStore ); - pNode->nRefs++; - } - - // reconnect the nodes in reverse topological order - pMan->vMapping->nSize = 0; - for ( i = LevelMax; i >= 0; i-- ) - for ( pNode = ppStore[i]; pNode; pNode = (Fpga_Node_t *)pNode->pData0 ) - Fpga_NodeVecPush( pMan->vMapping, pNode ); - free( ppStore ); - return aArea; -} - - -/**Function************************************************************* - - Synopsis [Compares the outputs by their arrival times.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MappingCompareOutputDelay( Fpga_Node_t ** ppNode1, Fpga_Node_t ** ppNode2 ) -{ - Fpga_Node_t * pNode1 = Fpga_Regular(*ppNode1); - Fpga_Node_t * pNode2 = Fpga_Regular(*ppNode2); - float Arrival1 = pNode1->pCutBest? pNode1->pCutBest->tArrival : 0; - float Arrival2 = pNode2->pCutBest? pNode2->pCutBest->tArrival : 0; - if ( Arrival1 < Arrival2 ) - return -1; - if ( Arrival1 > Arrival2 ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [Finds given number of latest arriving COs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingFindLatest( Fpga_Man_t * p, int * pNodes, int nNodesMax ) -{ - int nNodes, i, k, v; - assert( p->nOutputs >= nNodesMax ); - pNodes[0] = 0; - nNodes = 1; - for ( i = 1; i < p->nOutputs; i++ ) - { - for ( k = nNodes - 1; k >= 0; k-- ) - if ( Fpga_MappingCompareOutputDelay( &p->pOutputs[pNodes[k]], &p->pOutputs[i] ) >= 0 ) - break; - if ( k == nNodesMax - 1 ) - continue; - if ( nNodes < nNodesMax ) - nNodes++; - for ( v = nNodes - 1; v > k+1; v-- ) - pNodes[v] = pNodes[v-1]; - pNodes[k+1] = i; - } -} - -/**Function************************************************************* - - Synopsis [Prints a bunch of latest arriving outputs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p ) -{ - Fpga_Node_t * pNode; - int pSorted[FPGA_CO_LIST_SIZE]; - int fCompl, Limit, MaxNameSize, i; - - // determine the number of nodes to print - Limit = (p->nOutputs > FPGA_CO_LIST_SIZE)? FPGA_CO_LIST_SIZE : p->nOutputs; - - // determine the order - Fpga_MappingFindLatest( p, pSorted, Limit ); - - // determine max size of the node's name - MaxNameSize = 0; - for ( i = 0; i < Limit; i++ ) - if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) ) - MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]); - - // print the latest outputs - for ( i = 0; i < Limit; i++ ) - { - // get the i-th latest output - pNode = Fpga_Regular(p->pOutputs[pSorted[i]]); - fCompl = Fpga_IsComplement(p->pOutputs[pSorted[i]]); - // print out the best arrival time - printf( "Output %-*s : ", MaxNameSize + 3, p->ppOutputNames[pSorted[i]] ); - printf( "Delay = %8.2f ", (double)pNode->pCutBest->tArrival ); - if ( fCompl ) - printf( "NEG" ); - else - printf( "POS" ); - printf( "\n" ); - } -} - - -/**Function************************************************************* - - Synopsis [Sets up the truth tables.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingSetupTruthTables( unsigned uTruths[][2] ) -{ - int m, v; - // set up the truth tables - for ( m = 0; m < 32; m++ ) - for ( v = 0; v < 5; v++ ) - if ( m & (1 << v) ) - uTruths[v][0] |= (1 << m); - // make adjustments for the case of 6 variables - for ( v = 0; v < 5; v++ ) - uTruths[v][1] = uTruths[v][0]; - uTruths[5][0] = 0; - uTruths[5][1] = FPGA_FULL; -} - -/**Function************************************************************* - - Synopsis [Sets up the mask.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingSetupMask( unsigned uMask[], int nVarsMax ) -{ - if ( nVarsMax == 6 ) - uMask[0] = uMask[1] = FPGA_FULL; - else - { - uMask[0] = FPGA_MASK(1 << nVarsMax); - uMask[1] = 0; - } -} - -/**Function************************************************************* - - Synopsis [Verify one useful property.] - - Description [This procedure verifies one useful property. After - the FRAIG construction with choice nodes is over, each primary node - should have fanins that are primary nodes. The primary nodes is the - one that does not have pNode->pRepr set to point to another node.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_ManCheckConsistency( Fpga_Man_t * p ) -{ - Fpga_Node_t * pNode; - Fpga_NodeVec_t * pVec; - int i; - pVec = Fpga_MappingDfs( p, 0 ); - for ( i = 0; i < pVec->nSize; i++ ) - { - pNode = pVec->pArray[i]; - if ( Fpga_NodeIsVar(pNode) ) - { - if ( pNode->pRepr ) - printf( "Primary input %d is a secondary node.\n", pNode->Num ); - } - else if ( Fpga_NodeIsConst(pNode) ) - { - if ( pNode->pRepr ) - printf( "Constant 1 %d is a secondary node.\n", pNode->Num ); - } - else - { - if ( pNode->pRepr ) - printf( "Internal node %d is a secondary node.\n", pNode->Num ); - if ( Fpga_Regular(pNode->p1)->pRepr ) - printf( "Internal node %d has first fanin that is a secondary node.\n", pNode->Num ); - if ( Fpga_Regular(pNode->p2)->pRepr ) - printf( "Internal node %d has second fanin that is a secondary node.\n", pNode->Num ); - } - } - Fpga_NodeVecFree( pVec ); - return 1; -} - -/**Function************************************************************* - - Synopsis [Compares the supergates by their level.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CompareNodesByLevelDecreasing( Fpga_Node_t ** ppS1, Fpga_Node_t ** ppS2 ) -{ - if ( Fpga_Regular(*ppS1)->Level > Fpga_Regular(*ppS2)->Level ) - return -1; - if ( Fpga_Regular(*ppS1)->Level < Fpga_Regular(*ppS2)->Level ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [Compares the supergates by their level.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CompareNodesByLevelIncreasing( Fpga_Node_t ** ppS1, Fpga_Node_t ** ppS2 ) -{ - if ( Fpga_Regular(*ppS1)->Level < Fpga_Regular(*ppS2)->Level ) - return -1; - if ( Fpga_Regular(*ppS1)->Level > Fpga_Regular(*ppS2)->Level ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [Orders the nodes in the decreasing order of levels.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingSortByLevel( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes, int fIncreasing ) -{ - if ( fIncreasing ) - qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *), - (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelIncreasing ); - else - qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *), - (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelDecreasing ); -// assert( Fpga_CompareNodesByLevel( vNodes->pArray, vNodes->pArray + vNodes->nSize - 1 ) <= 0 ); -} - -/**Function************************************************************* - - Synopsis [Computes the limited DFS ordering for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_NodeVec_t * Fpga_DfsLim( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int nLevels ) -{ - Fpga_NodeVec_t * vNodes; - int i; - // perform the traversal - vNodes = Fpga_NodeVecAlloc( 100 ); - Fpga_DfsLim_rec( pNode, nLevels, vNodes ); - for ( i = 0; i < vNodes->nSize; i++ ) - vNodes->pArray[i]->fMark0 = 0; - return vNodes; -} - -/**Function************************************************************* - - Synopsis [Recursively computes the DFS ordering of the nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_DfsLim_rec( Fpga_Node_t * pNode, int Level, Fpga_NodeVec_t * vNodes ) -{ - assert( !Fpga_IsComplement(pNode) ); - if ( pNode->fMark0 ) - return; - pNode->fMark0 = 1; - // visit the transitive fanin - Level--; - if ( Level > 0 && Fpga_NodeIsAnd(pNode) ) - { - Fpga_DfsLim_rec( Fpga_Regular(pNode->p1), Level, vNodes ); - Fpga_DfsLim_rec( Fpga_Regular(pNode->p2), Level, vNodes ); - } - // add the node to the list - Fpga_NodeVecPush( vNodes, pNode ); -} - -/**Function************************************************************* - - Synopsis [Computes the limited DFS ordering for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_ManCleanData0( Fpga_Man_t * pMan ) -{ - int i; - for ( i = 0; i < pMan->vNodesAll->nSize; i++ ) - pMan->vNodesAll->pArray[i]->pData0 = 0; -} - -/**Function************************************************************* - - Synopsis [Collects the TFO of the node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_NodeVec_t * Fpga_CollectNodeTfo( Fpga_Man_t * pMan, Fpga_Node_t * pNode ) -{ - Fpga_NodeVec_t * vVisited, * vTfo; - int i; - // perform the traversal - vVisited = Fpga_NodeVecAlloc( 100 ); - vTfo = Fpga_NodeVecAlloc( 100 ); - for ( i = 0; i < pMan->nOutputs; i++ ) - Fpga_CollectNodeTfo_rec( Fpga_Regular(pMan->pOutputs[i]), pNode, vVisited, vTfo ); - for ( i = 0; i < vVisited->nSize; i++ ) - vVisited->pArray[i]->fMark0 = vVisited->pArray[i]->fMark1 = 0; - Fpga_NodeVecFree( vVisited ); - return vTfo; -} - -/**Function************************************************************* - - Synopsis [Collects the TFO of the node.] - - Description [Returns 1 if the node should be collected.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CollectNodeTfo_rec( Fpga_Node_t * pNode, Fpga_Node_t * pPivot, Fpga_NodeVec_t * vVisited, Fpga_NodeVec_t * vTfo ) -{ - int Ret1, Ret2; - assert( !Fpga_IsComplement(pNode) ); - // skip visited nodes - if ( pNode->fMark0 ) - return pNode->fMark1; - pNode->fMark0 = 1; - Fpga_NodeVecPush( vVisited, pNode ); - - // return the pivot node - if ( pNode == pPivot ) - { - pNode->fMark1 = 1; - return 1; - } - if ( pNode->Level < pPivot->Level ) - { - pNode->fMark1 = 0; - return 0; - } - // visit the transitive fanin - assert( Fpga_NodeIsAnd(pNode) ); - Ret1 = Fpga_CollectNodeTfo_rec( Fpga_Regular(pNode->p1), pPivot, vVisited, vTfo ); - Ret2 = Fpga_CollectNodeTfo_rec( Fpga_Regular(pNode->p2), pPivot, vVisited, vTfo ); - if ( Ret1 || Ret2 ) - { - pNode->fMark1 = 1; - Fpga_NodeVecPush( vTfo, pNode ); - } - else - pNode->fMark1 = 0; - return pNode->fMark1; -} - -/**Function************************************************************* - - Synopsis [Levelizes the nodes accessible from the POs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_NodeVec_t * Fpga_MappingLevelize( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes ) -{ - Fpga_NodeVec_t * vLevels; - Fpga_Node_t ** ppNodes; - Fpga_Node_t * pNode; - int nNodes, nLevelsMax, i; - - // reassign the levels (this may be necessary for networks which choices) - ppNodes = vNodes->pArray; - nNodes = vNodes->nSize; - for ( i = 0; i < nNodes; i++ ) - { - pNode = ppNodes[i]; - if ( !Fpga_NodeIsAnd(pNode) ) - { - pNode->Level = 0; - continue; - } - pNode->Level = 1 + FPGA_MAX( Fpga_Regular(pNode->p1)->Level, Fpga_Regular(pNode->p2)->Level ); - } - - // get the max levels - nLevelsMax = 0; - for ( i = 0; i < pMan->nOutputs; i++ ) - nLevelsMax = FPGA_MAX( nLevelsMax, (int)Fpga_Regular(pMan->pOutputs[i])->Level ); - nLevelsMax++; - - // allocate storage for levels - vLevels = Fpga_NodeVecAlloc( nLevelsMax ); - for ( i = 0; i < nLevelsMax; i++ ) - Fpga_NodeVecPush( vLevels, NULL ); - - // go through the nodes and add them to the levels - for ( i = 0; i < nNodes; i++ ) - { - pNode = ppNodes[i]; - pNode->pLevel = NULL; - if ( !Fpga_NodeIsAnd(pNode) ) - continue; - // attach the node to this level - pNode->pLevel = Fpga_NodeVecReadEntry( vLevels, pNode->Level ); - Fpga_NodeVecWriteEntry( vLevels, pNode->Level, pNode ); - } - return vLevels; -} - -/**Function************************************************************* - - Synopsis [Sets up the mask.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MappingMaxLevel( Fpga_Man_t * pMan ) -{ - int nLevelMax, i; - nLevelMax = 0; - for ( i = 0; i < pMan->nOutputs; i++ ) - nLevelMax = nLevelMax > (int)Fpga_Regular(pMan->pOutputs[i])->Level? - nLevelMax : (int)Fpga_Regular(pMan->pOutputs[i])->Level; - return nLevelMax; -} - - -/**Function************************************************************* - - Synopsis [Analyses choice nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MappingUpdateLevel_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int fMaximum ) -{ - Fpga_Node_t * pTemp; - int Level1, Level2, LevelE; - assert( !Fpga_IsComplement(pNode) ); - if ( !Fpga_NodeIsAnd(pNode) ) - return pNode->Level; - // skip the visited node - if ( pNode->TravId == pMan->nTravIds ) - return pNode->Level; - pNode->TravId = pMan->nTravIds; - // compute levels of the children nodes - Level1 = Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pNode->p1), fMaximum ); - Level2 = Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pNode->p2), fMaximum ); - pNode->Level = 1 + FPGA_MAX( Level1, Level2 ); - if ( pNode->pNextE ) - { - LevelE = Fpga_MappingUpdateLevel_rec( pMan, pNode->pNextE, fMaximum ); - if ( fMaximum ) - { - if ( pNode->Level < (unsigned)LevelE ) - pNode->Level = LevelE; - } - else - { - if ( pNode->Level > (unsigned)LevelE ) - pNode->Level = LevelE; - } - // set the level of all equivalent nodes to be the same minimum - if ( pNode->pRepr == NULL ) // the primary node - for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE ) - pTemp->Level = pNode->Level; - } - return pNode->Level; -} - -/**Function************************************************************* - - Synopsis [Resets the levels of the nodes in the choice graph.] - - Description [Makes the level of the choice nodes to be equal to the - maximum of the level of the nodes in the equivalence class. This way - sorting by level leads to the reverse topological order, which is - needed for the required time computation.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan ) -{ - int i; - pMan->nTravIds++; - for ( i = 0; i < pMan->nOutputs; i++ ) - Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 1 ); -} - -/**Function************************************************************* - - Synopsis [Reports statistics on choice nodes.] - - Description [The number of choice nodes is the number of primary nodes, - which has pNextE set to a pointer. The number of choices is the number - of entries in the equivalent-node lists of the primary nodes.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_ManReportChoices( Fpga_Man_t * pMan ) -{ - Fpga_Node_t * pNode, * pTemp; - int nChoiceNodes, nChoices; - int i, LevelMax1, LevelMax2; - - // report the number of levels - LevelMax1 = Fpga_MappingMaxLevel( pMan ); - pMan->nTravIds++; - for ( i = 0; i < pMan->nOutputs; i++ ) - Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 0 ); - LevelMax2 = Fpga_MappingMaxLevel( pMan ); - - // report statistics about choices - nChoiceNodes = nChoices = 0; - for ( i = 0; i < pMan->vAnds->nSize; i++ ) - { - pNode = pMan->vAnds->pArray[i]; - if ( pNode->pRepr == NULL && pNode->pNextE != NULL ) - { // this is a choice node = the primary node that has equivalent nodes - nChoiceNodes++; - for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE ) - nChoices++; - } - } - if ( pMan->fVerbose ) - { - printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 ); - printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices ); - } -/* - { - FILE * pTable; - pTable = fopen( "stats_choice.txt", "a+" ); - fprintf( pTable, "%s ", pMan->pFileName ); - fprintf( pTable, "%4d ", LevelMax1 ); - fprintf( pTable, "%4d ", pMan->vAnds->nSize - pMan->nInputs ); - fprintf( pTable, "%4d ", LevelMax2 ); - fprintf( pTable, "%7d ", nChoiceNodes ); - fprintf( pTable, "%7d ", nChoices + nChoiceNodes ); - fprintf( pTable, "\n" ); - fclose( pTable ); - } -*/ -} - -/**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/abc70930/src/map/fpga/fpgaVec.c b/abc70930/src/map/fpga/fpgaVec.c deleted file mode 100644 index 70a4a7ac..00000000 --- a/abc70930/src/map/fpga/fpgaVec.c +++ /dev/null @@ -1,408 +0,0 @@ -/**CFile**************************************************************** - - FileName [fpgaVec.c] - - PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] - - Synopsis [Technology mapping for variable-size-LUT FPGAs.] - - Author [MVSIS Group] - - Affiliation [UC Berkeley] - - Date [Ver. 2.0. Started - August 18, 2004.] - - Revision [$Id: fpgaVec.c,v 1.3 2005/01/23 06:59:42 alanmi Exp $] - -***********************************************************************/ - -#include "fpgaInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -static int Fpga_NodeVecCompareLevels( Fpga_Node_t ** pp1, Fpga_Node_t ** pp2 ); - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Allocates a vector with the given capacity.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_NodeVec_t * Fpga_NodeVecAlloc( int nCap ) -{ - Fpga_NodeVec_t * p; - p = ALLOC( Fpga_NodeVec_t, 1 ); - if ( nCap > 0 && nCap < 16 ) - nCap = 16; - p->nSize = 0; - p->nCap = nCap; - p->pArray = p->nCap? ALLOC( Fpga_Node_t *, p->nCap ) : NULL; - return p; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeVecFree( Fpga_NodeVec_t * p ) -{ - FREE( p->pArray ); - FREE( p ); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Node_t ** Fpga_NodeVecReadArray( Fpga_NodeVec_t * p ) -{ - return p->pArray; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_NodeVecReadSize( Fpga_NodeVec_t * p ) -{ - return p->nSize; -} - -/**Function************************************************************* - - Synopsis [Resizes the vector to the given capacity.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeVecGrow( Fpga_NodeVec_t * p, int nCapMin ) -{ - if ( p->nCap >= nCapMin ) - return; - p->pArray = REALLOC( Fpga_Node_t *, p->pArray, nCapMin ); - p->nCap = nCapMin; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeVecShrink( Fpga_NodeVec_t * p, int nSizeNew ) -{ - assert( p->nSize >= nSizeNew ); - p->nSize = nSizeNew; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeVecClear( Fpga_NodeVec_t * p ) -{ - p->nSize = 0; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeVecPush( Fpga_NodeVec_t * p, Fpga_Node_t * Entry ) -{ - if ( p->nSize == p->nCap ) - { - if ( p->nCap < 16 ) - Fpga_NodeVecGrow( p, 16 ); - else - Fpga_NodeVecGrow( p, 2 * p->nCap ); - } - p->pArray[p->nSize++] = Entry; -} - -/**Function************************************************************* - - Synopsis [Add the element while ensuring uniqueness.] - - Description [Returns 1 if the element was found, and 0 if it was new. ] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_NodeVecPushUnique( Fpga_NodeVec_t * p, Fpga_Node_t * Entry ) -{ - int i; - for ( i = 0; i < p->nSize; i++ ) - if ( p->pArray[i] == Entry ) - return 1; - Fpga_NodeVecPush( p, Entry ); - return 0; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Node_t * Fpga_NodeVecPop( Fpga_NodeVec_t * p ) -{ - return p->pArray[--p->nSize]; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeVecWriteEntry( Fpga_NodeVec_t * p, int i, Fpga_Node_t * Entry ) -{ - assert( i >= 0 && i < p->nSize ); - p->pArray[i] = Entry; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_Node_t * Fpga_NodeVecReadEntry( Fpga_NodeVec_t * p, int i ) -{ - assert( i >= 0 && i < p->nSize ); - return p->pArray[i]; -} - -/**Function************************************************************* - - Synopsis [Comparison procedure for two nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_NodeVecCompareLevels( Fpga_Node_t ** pp1, Fpga_Node_t ** pp2 ) -{ - int Level1 = Fpga_Regular(*pp1)->Level; - int Level2 = Fpga_Regular(*pp2)->Level; - if ( Level1 < Level2 ) - return -1; - if ( Level1 > Level2 ) - return 1; - if ( Fpga_Regular(*pp1)->Num < Fpga_Regular(*pp2)->Num ) - return -1; - if ( Fpga_Regular(*pp1)->Num > Fpga_Regular(*pp2)->Num ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [Sorting the entries by their integer value.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeVecSortByLevel( Fpga_NodeVec_t * p ) -{ - qsort( (void *)p->pArray, p->nSize, sizeof(Fpga_Node_t *), - (int (*)(const void *, const void *)) Fpga_NodeVecCompareLevels ); -} - -/**Function************************************************************* - - Synopsis [Compares the arrival times.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_NodeVecCompareArrivals( Fpga_Node_t ** ppS1, Fpga_Node_t ** ppS2 ) -{ - if ( (*ppS1)->pCutBest->tArrival < (*ppS2)->pCutBest->tArrival ) - return -1; - if ( (*ppS1)->pCutBest->tArrival > (*ppS2)->pCutBest->tArrival ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [Orders the nodes in the increasing order of the arrival times.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_SortNodesByArrivalTimes( Fpga_NodeVec_t * p ) -{ - qsort( (void *)p->pArray, p->nSize, sizeof(Fpga_Node_t *), - (int (*)(const void *, const void *)) Fpga_NodeVecCompareArrivals ); -// assert( Fpga_CompareNodesByLevel( p->pArray, p->pArray + p->nSize - 1 ) <= 0 ); -} - - -/**Function************************************************************* - - Synopsis [Computes the union of nodes in two arrays.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeVecUnion( Fpga_NodeVec_t * p, Fpga_NodeVec_t * p1, Fpga_NodeVec_t * p2 ) -{ - int i; - Fpga_NodeVecClear( p ); - for ( i = 0; i < p1->nSize; i++ ) - Fpga_NodeVecPush( p, p1->pArray[i] ); - for ( i = 0; i < p2->nSize; i++ ) - Fpga_NodeVecPush( p, p2->pArray[i] ); -} - -/**Function************************************************************* - - Synopsis [Inserts a new node in the order by arrival times.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeVecPushOrder( Fpga_NodeVec_t * vNodes, Fpga_Node_t * pNode, int fIncreasing ) -{ - Fpga_Node_t * pNode1, * pNode2; - int i; - Fpga_NodeVecPush( vNodes, pNode ); - // find the place of the node - for ( i = vNodes->nSize-1; i > 0; i-- ) - { - pNode1 = vNodes->pArray[i ]; - pNode2 = vNodes->pArray[i-1]; - if ( fIncreasing && pNode1->pCutBest->tArrival >= pNode2->pCutBest->tArrival || - !fIncreasing && pNode1->pCutBest->tArrival <= pNode2->pCutBest->tArrival ) - break; - vNodes->pArray[i ] = pNode2; - vNodes->pArray[i-1] = pNode1; - } -} - -/**Function************************************************************* - - Synopsis [Inserts a new node in the order by arrival times.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_NodeVecReverse( Fpga_NodeVec_t * vNodes ) -{ - Fpga_Node_t * pNode1, * pNode2; - int i; - for ( i = 0; i < vNodes->nSize/2; i++ ) - { - pNode1 = vNodes->pArray[i]; - pNode2 = vNodes->pArray[vNodes->nSize-1-i]; - vNodes->pArray[i] = pNode2; - vNodes->pArray[vNodes->nSize-1-i] = pNode1; - } -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - diff --git a/abc70930/src/map/fpga/module.make b/abc70930/src/map/fpga/module.make deleted file mode 100644 index cc3a6573..00000000 --- a/abc70930/src/map/fpga/module.make +++ /dev/null @@ -1,13 +0,0 @@ -SRC += src/map/fpga/fpga.c \ - src/map/fpga/fpgaCore.c \ - src/map/fpga/fpgaCreate.c \ - src/map/fpga/fpgaCut.c \ - src/map/fpga/fpgaCutUtils.c \ - src/map/fpga/fpgaFanout.c \ - src/map/fpga/fpgaLib.c \ - src/map/fpga/fpgaMatch.c \ - src/map/fpga/fpgaSwitch.c \ - src/map/fpga/fpgaTime.c \ - src/map/fpga/fpgaTruth.c \ - src/map/fpga/fpgaUtils.c \ - src/map/fpga/fpgaVec.c |