diff options
Diffstat (limited to 'src')
46 files changed, 2308 insertions, 725 deletions
diff --git a/src/base/abc/abc.h b/src/base/abc/abc.h index f29859b9..0e296d64 100644 --- a/src/base/abc/abc.h +++ b/src/base/abc/abc.h @@ -430,11 +430,13 @@ extern void Abc_NodeFreeCuts( void * p, Abc_Obj_t * pObj ); extern Vec_Ptr_t * Abc_NtkDfs( Abc_Ntk_t * pNtk, int fCollectAll ); extern Vec_Ptr_t * Abc_NtkDfsNodes( Abc_Ntk_t * pNtk, Abc_Obj_t ** ppNodes, int nNodes ); extern Vec_Ptr_t * Abc_NtkDfsReverse( Abc_Ntk_t * pNtk ); +extern bool Abc_NtkIsDfsOrdered( Abc_Ntk_t * pNtk ); extern Vec_Ptr_t * Abc_NtkNodeSupport( Abc_Ntk_t * pNtk, Abc_Obj_t ** ppNodes, int nNodes ); extern Vec_Ptr_t * Abc_AigDfs( Abc_Ntk_t * pNtk, int fCollectAll, int fCollectCos ); extern Vec_Vec_t * Abc_DfsLevelized( Abc_Obj_t * pNode, bool fTfi ); extern int Abc_NtkGetLevelNum( Abc_Ntk_t * pNtk ); extern bool Abc_NtkIsAcyclic( Abc_Ntk_t * pNtk ); +extern Vec_Ptr_t * Abc_AigGetLevelizedOrder( Abc_Ntk_t * pNtk, int fCollectCis ); /*=== abcFanio.c ==========================================================*/ extern void Abc_ObjAddFanin( Abc_Obj_t * pObj, Abc_Obj_t * pFanin ); extern void Abc_ObjDeleteFanin( Abc_Obj_t * pObj, Abc_Obj_t * pFanin ); diff --git a/src/base/abc/abcCheck.c b/src/base/abc/abcCheck.c index 43235139..356a4eba 100644 --- a/src/base/abc/abcCheck.c +++ b/src/base/abc/abcCheck.c @@ -101,7 +101,7 @@ bool Abc_NtkDoCheck( Abc_Ntk_t * pNtk ) } if ( Abc_NtkHasMapping(pNtk) ) { - if ( pNtk->pManFunc != Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) ) + if ( pNtk->pManFunc != Abc_FrameReadLibGen() ) { fprintf( stdout, "NetworkCheck: The library of the mapped network is not the global library.\n" ); return 0; diff --git a/src/base/abc/abcDfs.c b/src/base/abc/abcDfs.c index 31a6e8b9..097ee92d 100644 --- a/src/base/abc/abcDfs.c +++ b/src/base/abc/abcDfs.c @@ -206,6 +206,37 @@ void Abc_NtkDfsReverse_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes ) Vec_PtrPush( vNodes, pNode ); } +/**Function************************************************************* + + Synopsis [Returns 1 if the ordering of nodes is DFS.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +bool Abc_NtkIsDfsOrdered( Abc_Ntk_t * pNtk ) +{ + Abc_Obj_t * pNode; + int i; + // set the traversal ID + Abc_NtkIncrementTravId( pNtk ); + // mark the CIs + Abc_NtkForEachCi( pNtk, pNode, i ) + Abc_NodeSetTravIdCurrent( pNode ); + // go through the nodes + Abc_NtkForEachNode( pNtk, pNode, i ) + { + if ( !Abc_NodeIsTravIdCurrent(Abc_ObjFanin0(pNode)) ) + return 0; + if ( !Abc_NodeIsTravIdCurrent(Abc_ObjFanin1(pNode)) ) + return 0; + Abc_NodeSetTravIdCurrent( pNode ); + } + return 1; +} /**Function************************************************************* @@ -573,6 +604,123 @@ bool Abc_NtkIsAcyclic_rec( Abc_Obj_t * pNode ) return 1; } + +/**Function************************************************************* + + Synopsis [Analyses choice nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NodeSetChoiceLevel_rec( Abc_Obj_t * pNode, int fMaximum ) +{ + Abc_Obj_t * pTemp; + int Level1, Level2, Level, LevelE; + // skip the visited node + if ( Abc_NodeIsTravIdCurrent( pNode ) ) + return (int)pNode->pCopy; + Abc_NodeSetTravIdCurrent( pNode ); + // compute levels of the children nodes + Level1 = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin0(pNode), fMaximum ); + Level2 = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin1(pNode), fMaximum ); + Level = 1 + ABC_MAX( Level1, Level2 ); + if ( pNode->pData ) + { + LevelE = Abc_NodeSetChoiceLevel_rec( pNode->pData, fMaximum ); + if ( fMaximum ) + Level = ABC_MAX( Level, LevelE ); + else + Level = ABC_MIN( Level, LevelE ); + // set the level of all equivalent nodes to be the same minimum + for ( pTemp = pNode->pData; pTemp; pTemp = pTemp->pData ) + pTemp->pCopy = (void *)Level; + } + pNode->pCopy = (void *)Level; + return 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 [] + +***********************************************************************/ +int Abc_AigSetChoiceLevels( Abc_Ntk_t * pNtk ) +{ + Abc_Obj_t * pObj; + int i, LevelMax, LevelCur; + assert( Abc_NtkIsStrash(pNtk) ); + // set the new travid counter + Abc_NtkIncrementTravId( pNtk ); + // set levels of the CI and constant + Abc_NtkForEachCi( pNtk, pObj, i ) + { + Abc_NodeSetTravIdCurrent( pObj ); + pObj->pCopy = NULL; + } + pObj = Abc_AigConst1( pNtk->pManFunc ); + Abc_NodeSetTravIdCurrent( pObj ); + pObj->pCopy = NULL; + // set levels of all other nodes + LevelMax = 0; + Abc_NtkForEachCo( pNtk, pObj, i ) + { + LevelCur = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin0(pObj), 1 ); + LevelMax = ABC_MAX( LevelMax, LevelCur ); + } + return LevelMax; +} + +/**Function************************************************************* + + Synopsis [Returns nodes by level from the smallest to the largest.] + + Description [Correctly handles the case of choice nodes, by first + spreading them out across several levels and then collecting.] + + SideEffects [What happens with dangling nodes???] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * Abc_AigGetLevelizedOrder( Abc_Ntk_t * pNtk, int fCollectCis ) +{ + Vec_Ptr_t * vNodes, * vLevels; + Abc_Obj_t * pNode, ** ppHead; + int LevelMax, i; + assert( Abc_NtkIsStrash(pNtk) ); + // set the correct levels + Abc_NtkCleanCopy( pNtk ); + LevelMax = Abc_AigSetChoiceLevels( pNtk ); + // relink nodes by level + vLevels = Vec_PtrStart( LevelMax + 1 ); + Abc_NtkForEachNode( pNtk, pNode, i ) + { + ppHead = ((Abc_Obj_t **)vLevels->pArray) + (int)pNode->pCopy; + pNode->pCopy = *ppHead; + *ppHead = pNode; + } + // recollect nodes + vNodes = Vec_PtrStart( Abc_NtkNodeNum(pNtk) ); + Vec_PtrForEachEntryStart( vLevels, pNode, i, !fCollectCis ) + for ( ; pNode; pNode = pNode->pCopy ) + Vec_PtrPush( vNodes, pNode ); + Vec_PtrFree( vLevels ); + return vNodes; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/base/abc/abcNtk.c b/src/base/abc/abcNtk.c index b21d16fc..dc4dd9e2 100644 --- a/src/base/abc/abcNtk.c +++ b/src/base/abc/abcNtk.c @@ -74,7 +74,7 @@ Abc_Ntk_t * Abc_NtkAlloc( Abc_NtkType_t Type, Abc_NtkFunc_t Func ) else if ( Abc_NtkHasAig(pNtk) ) pNtk->pManFunc = Abc_AigAlloc( pNtk ); else if ( Abc_NtkHasMapping(pNtk) ) - pNtk->pManFunc = Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()); + pNtk->pManFunc = Abc_FrameReadLibGen(); else assert( 0 ); return pNtk; diff --git a/src/base/abc/abcObj.c b/src/base/abc/abcObj.c index d5c18d2e..53ba3568 100644 --- a/src/base/abc/abcObj.c +++ b/src/base/abc/abcObj.c @@ -518,7 +518,7 @@ Abc_Obj_t * Abc_NodeCreateConst0( Abc_Ntk_t * pNtk ) else if ( Abc_NtkHasBdd(pNtk) ) pNode->pData = Cudd_ReadLogicZero(pNtk->pManFunc), Cudd_Ref( pNode->pData ); else if ( Abc_NtkHasMapping(pNtk) ) - pNode->pData = Mio_LibraryReadConst0(Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame())); + pNode->pData = Mio_LibraryReadConst0(Abc_FrameReadLibGen()); else assert( 0 ); return pNode; @@ -546,7 +546,7 @@ Abc_Obj_t * Abc_NodeCreateConst1( Abc_Ntk_t * pNtk ) else if ( Abc_NtkHasBdd(pNtk) ) pNode->pData = Cudd_ReadOne(pNtk->pManFunc), Cudd_Ref( pNode->pData ); else if ( Abc_NtkHasMapping(pNtk) ) - pNode->pData = Mio_LibraryReadConst1(Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame())); + pNode->pData = Mio_LibraryReadConst1(Abc_FrameReadLibGen()); else assert( 0 ); return pNode; @@ -574,7 +574,7 @@ Abc_Obj_t * Abc_NodeCreateInv( Abc_Ntk_t * pNtk, Abc_Obj_t * pFanin ) else if ( Abc_NtkHasBdd(pNtk) ) pNode->pData = Cudd_Not(Cudd_bddIthVar(pNtk->pManFunc,0)), Cudd_Ref( pNode->pData ); else if ( Abc_NtkHasMapping(pNtk) ) - pNode->pData = Mio_LibraryReadInv(Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame())); + pNode->pData = Mio_LibraryReadInv(Abc_FrameReadLibGen()); else assert( 0 ); return pNode; @@ -602,7 +602,7 @@ Abc_Obj_t * Abc_NodeCreateBuf( Abc_Ntk_t * pNtk, Abc_Obj_t * pFanin ) else if ( Abc_NtkHasBdd(pNtk) ) pNode->pData = Cudd_bddIthVar(pNtk->pManFunc,0), Cudd_Ref( pNode->pData ); else if ( Abc_NtkHasMapping(pNtk) ) - pNode->pData = Mio_LibraryReadBuf(Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame())); + pNode->pData = Mio_LibraryReadBuf(Abc_FrameReadLibGen()); else assert( 0 ); return pNode; @@ -781,7 +781,7 @@ bool Abc_NodeIsConst0( Abc_Obj_t * pNode ) if ( Abc_NtkHasAig(pNtk) ) return Abc_ObjNot(pNode) == Abc_AigConst1(pNode->pNtk->pManFunc); if ( Abc_NtkHasMapping(pNtk) ) - return pNode->pData == Mio_LibraryReadConst0(Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame())); + return pNode->pData == Mio_LibraryReadConst0(Abc_FrameReadLibSuper()); assert( 0 ); return 0; } @@ -809,7 +809,7 @@ bool Abc_NodeIsConst1( Abc_Obj_t * pNode ) if ( Abc_NtkHasAig(pNtk) ) return pNode == Abc_AigConst1(pNode->pNtk->pManFunc); if ( Abc_NtkHasMapping(pNtk) ) - return pNode->pData == Mio_LibraryReadConst1(Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame())); + return pNode->pData == Mio_LibraryReadConst1(Abc_FrameReadLibSuper()); assert( 0 ); return 0; } @@ -838,7 +838,7 @@ bool Abc_NodeIsBuf( Abc_Obj_t * pNode ) if ( Abc_NtkHasAig(pNtk) ) return 0; if ( Abc_NtkHasMapping(pNtk) ) - return pNode->pData == Mio_LibraryReadBuf(Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame())); + return pNode->pData == Mio_LibraryReadBuf(Abc_FrameReadLibSuper()); assert( 0 ); return 0; } @@ -867,7 +867,7 @@ bool Abc_NodeIsInv( Abc_Obj_t * pNode ) if ( Abc_NtkHasAig(pNtk) ) return 0; if ( Abc_NtkHasMapping(pNtk) ) - return pNode->pData == Mio_LibraryReadInv(Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame())); + return pNode->pData == Mio_LibraryReadInv(Abc_FrameReadLibSuper()); assert( 0 ); return 0; } diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index dfe3ccc8..c4feb7a2 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -22,6 +22,8 @@ #include "mainInt.h" #include "fraig.h" #include "fxu.h" +#include "fpga.h" +#include "pga.h" #include "cut.h" //////////////////////////////////////////////////////////////////////// @@ -80,6 +82,7 @@ static int Abc_CommandAttach ( Abc_Frame_t * pAbc, int argc, char ** argv static int Abc_CommandSuperChoice ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandFpga ( Abc_Frame_t * pAbc, int argc, char ** argv ); +static int Abc_CommandPga ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandSeq ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandRetime ( Abc_Frame_t * pAbc, int argc, char ** argv ); @@ -156,6 +159,7 @@ void Abc_Init( Abc_Frame_t * pAbc ) Cmd_CommandAdd( pAbc, "SC mapping", "sc", Abc_CommandSuperChoice, 1 ); Cmd_CommandAdd( pAbc, "FPGA mapping", "fpga", Abc_CommandFpga, 1 ); + Cmd_CommandAdd( pAbc, "FPGA mapping", "pga", Abc_CommandPga, 1 ); Cmd_CommandAdd( pAbc, "Sequential", "seq", Abc_CommandSeq, 1 ); Cmd_CommandAdd( pAbc, "Sequential", "retime", Abc_CommandRetime, 1 ); @@ -2720,14 +2724,13 @@ int Abc_CommandCut( Abc_Frame_t * pAbc, int argc, char ** argv ) // set defaults pParams->nVarsMax = 5; // the max cut size ("k" of the k-feasible cuts) pParams->nKeepMax = 250; // the max number of cuts kept at a node - pParams->fTruth = 1; // compute truth tables - pParams->fHash = 0; // hash cuts to detect unique - pParams->fFilter = 0; // filter dominated cuts + pParams->fTruth = 0; // compute truth tables + pParams->fFilter = 1; // filter dominated cuts pParams->fSeq = 0; // compute sequential cuts pParams->fDrop = 0; // drop cuts on the fly pParams->fVerbose = 0; // the verbosiness flag util_getopt_reset(); - while ( ( c = util_getopt( argc, argv, "KMtrfsdvh" ) ) != EOF ) + while ( ( c = util_getopt( argc, argv, "KMtfsdvh" ) ) != EOF ) { switch ( c ) { @@ -2756,9 +2759,6 @@ int Abc_CommandCut( Abc_Frame_t * pAbc, int argc, char ** argv ) case 't': pParams->fTruth ^= 1; break; - case 'r': - pParams->fHash ^= 1; - break; case 'f': pParams->fFilter ^= 1; break; @@ -2794,16 +2794,15 @@ int Abc_CommandCut( Abc_Frame_t * pAbc, int argc, char ** argv ) return 0; usage: - fprintf( pErr, "usage: cut [-K num] [-M num] [-trfsdvh]\n" ); + fprintf( pErr, "usage: cut [-K num] [-M num] [-tfsdvh]\n" ); fprintf( pErr, "\t computes k-feasible cuts for the AIG\n" ); - fprintf( pErr, "\t-K num : max number of leaves (4 <= num <= 6) [default = %d]\n", pParams->nVarsMax ); - fprintf( pErr, "\t-M num : max number of cuts stored at a node [default = %d]\n", pParams->nKeepMax ); - fprintf( pErr, "\t-t : toggle truth table computation [default = %s]\n", pParams->fTruth? "yes": "no" ); - fprintf( pErr, "\t-r : toggle reduction by hashing [default = %s]\n", pParams->fHash? "yes": "no" ); - fprintf( pErr, "\t-f : toggle filtering by dominance [default = %s]\n", pParams->fFilter? "yes": "no" ); - fprintf( pErr, "\t-s : toggle sequential cut computation [default = %s]\n", pParams->fSeq? "yes": "no" ); - fprintf( pErr, "\t-d : toggle dropping when fanouts are done [default = %s]\n", pParams->fDrop? "yes": "no" ); - fprintf( pErr, "\t-v : toggle printing verbose information [default = %s]\n", pParams->fVerbose? "yes": "no" ); + fprintf( pErr, "\t-K num : max number of leaves (4 <= num <= 6) [default = %d]\n", pParams->nVarsMax ); + fprintf( pErr, "\t-M num : max number of cuts stored at a node [default = %d]\n", pParams->nKeepMax ); + fprintf( pErr, "\t-t : toggle truth table computation [default = %s]\n", pParams->fTruth? "yes": "no" ); + fprintf( pErr, "\t-f : toggle filtering of duplicated/dominated [default = %s]\n", pParams->fFilter? "yes": "no" ); + fprintf( pErr, "\t-s : toggle sequential cut computation [default = %s]\n", pParams->fSeq? "yes": "no" ); + fprintf( pErr, "\t-d : toggle dropping when fanouts are done [default = %s]\n", pParams->fDrop? "yes": "no" ); + fprintf( pErr, "\t-v : toggle printing verbose information [default = %s]\n", pParams->fVerbose? "yes": "no" ); fprintf( pErr, "\t-h : print the command usage\n"); return 1; } @@ -3771,6 +3770,123 @@ usage: return 1; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_CommandPga( Abc_Frame_t * pAbc, int argc, char ** argv ) +{ + FILE * pOut, * pErr; + Abc_Ntk_t * pNtk, * pNtkRes; + Pga_Params_t Params, * pParams = &Params; + int c; + extern Abc_Ntk_t * Abc_NtkPga( Pga_Params_t * pParams ); + + pNtk = Abc_FrameReadNet(pAbc); + pOut = Abc_FrameReadOut(pAbc); + pErr = Abc_FrameReadErr(pAbc); + + // set defaults + memset( pParams, 0, sizeof(Pga_Params_t) ); + pParams->pNtk = pNtk; + pParams->pLutLib = Abc_FrameReadLibLut(); + pParams->fAreaFlow = 1; + pParams->fArea = 1; + pParams->fSwitching = 0; + pParams->fDropCuts = 0; + pParams->fVerbose = 0; + util_getopt_reset(); + while ( ( c = util_getopt( argc, argv, "fapdvh" ) ) != EOF ) + { + switch ( c ) + { + case 'f': + pParams->fAreaFlow ^= 1; + break; + case 'a': + pParams->fArea ^= 1; + break; + case 'p': + pParams->fSwitching ^= 1; + break; + case 'd': + pParams->fDropCuts ^= 1; + break; + case 'v': + pParams->fVerbose ^= 1; + break; + case 'h': + default: + goto usage; + } + } + + if ( pNtk == NULL ) + { + fprintf( pErr, "Empty network.\n" ); + return 1; + } + + if ( !Abc_NtkIsStrash(pNtk) ) + { + // strash and balance the network + pNtk = Abc_NtkStrash( pNtk, 0, 0 ); + if ( pNtk == NULL ) + { + fprintf( pErr, "Strashing before FPGA mapping has failed.\n" ); + return 1; + } + pNtk = Abc_NtkBalance( pNtkRes = pNtk, 0 ); + Abc_NtkDelete( pNtkRes ); + if ( pNtk == NULL ) + { + fprintf( pErr, "Balancing before FPGA mapping has failed.\n" ); + return 1; + } + fprintf( pOut, "The network was strashed and balanced before FPGA mapping.\n" ); + // get the new network + pNtkRes = Abc_NtkPga( pParams ); + if ( pNtkRes == NULL ) + { + Abc_NtkDelete( pNtk ); + fprintf( pErr, "FPGA mapping has failed.\n" ); + return 1; + } + Abc_NtkDelete( pNtk ); + } + else + { + // get the new network + pNtkRes = Abc_NtkPga( pParams ); + if ( pNtkRes == NULL ) + { + fprintf( pErr, "FPGA mapping has failed.\n" ); + return 1; + } + } + // replace the current network + Abc_FrameReplaceCurrentNetwork( pAbc, pNtkRes ); + return 0; + +usage: + fprintf( pErr, "usage: pga [-fapdvh]\n" ); + fprintf( pErr, "\t performs FPGA mapping of the current network\n" ); + fprintf( pErr, "\t-f : toggles area flow recovery [default = %s]\n", pParams->fAreaFlow? "yes": "no" ); + fprintf( pErr, "\t-a : toggles area recovery [default = %s]\n", pParams->fArea? "yes": "no" ); + fprintf( pErr, "\t-p : optimizes power by minimizing switching activity [default = %s]\n", pParams->fSwitching? "yes": "no" ); + fprintf( pErr, "\t-d : toggles dropping cuts to save memory [default = %s]\n", pParams->fDropCuts? "yes": "no" ); + fprintf( pErr, "\t-v : toggles verbose output [default = %s]\n", pParams->fVerbose? "yes": "no" ); + fprintf( pErr, "\t-h : prints the command usage\n"); + return 1; +} + /**Function************************************************************* diff --git a/src/base/abci/abcAttach.c b/src/base/abci/abcAttach.c index 6ee1fb90..02fe7284 100644 --- a/src/base/abci/abcAttach.c +++ b/src/base/abci/abcAttach.c @@ -66,7 +66,7 @@ int Abc_NtkAttach( Abc_Ntk_t * pNtk ) assert( Abc_NtkIsSopLogic(pNtk) ); // check that the library is available - pGenlib = Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()); + pGenlib = Abc_FrameReadLibGen(); if ( pGenlib == NULL ) { printf( "The current library is not available.\n" ); diff --git a/src/base/abci/abcCut.c b/src/base/abci/abcCut.c index f487bd1b..e7309a59 100644 --- a/src/base/abci/abcCut.c +++ b/src/base/abci/abcCut.c @@ -105,7 +105,6 @@ PRT( "Total", clock() - clk ); if ( Abc_NodeIsTravIdCurrent(pDriver) ) continue; Abc_NodeSetTravIdCurrent(pDriver); - Cut_NodeSetComputedAsNew( p, pDriver->Id ); } // compute as long as new cuts appear diff --git a/src/base/abci/abcFraig.c b/src/base/abci/abcFraig.c index 3f860585..7a8eed5d 100644 --- a/src/base/abci/abcFraig.c +++ b/src/base/abci/abcFraig.c @@ -556,7 +556,7 @@ void Abc_NtkFraigStoreCheck( Abc_Ntk_t * pFraig ) int i, k; // check that the PO functions are correct nPoFinal = Abc_NtkPoNum(pFraig); - nStored = Abc_FrameReadNtkStoreSize(Abc_FrameGetGlobalFrame()); + nStored = Abc_FrameReadNtkStoreSize(); assert( nPoFinal % nStored == 0 ); nPoOrig = nPoFinal / nStored; for ( i = 0; i < nPoOrig; i++ ) diff --git a/src/base/abci/abcMap.c b/src/base/abci/abcMap.c index ec5352cb..44f5aa94 100644 --- a/src/base/abci/abcMap.c +++ b/src/base/abci/abcMap.c @@ -66,18 +66,18 @@ Abc_Ntk_t * Abc_NtkMap( Abc_Ntk_t * pNtk, double DelayTarget, int fRecovery, int assert( Abc_NtkIsStrash(pNtk) ); // check that the library is available - if ( Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) == NULL ) + if ( Abc_FrameReadLibGen() == NULL ) { printf( "The current library is not available.\n" ); return 0; } // derive the supergate library - if ( Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()) == NULL && Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) ) + if ( Abc_FrameReadLibSuper() == NULL && Abc_FrameReadLibGen() ) { printf( "A simple supergate library is derived from gate library \"%s\".\n", - Mio_LibraryReadName(Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame())) ); - Map_SuperLibDeriveFromGenlib( Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) ); + Mio_LibraryReadName(Abc_FrameReadLibGen()) ); + Map_SuperLibDeriveFromGenlib( Abc_FrameReadLibGen() ); } // print a warning about choice nodes @@ -410,7 +410,7 @@ int Abc_NtkUnmap( Abc_Ntk_t * pNtk ) assert( Abc_NtkIsMappedLogic(pNtk) ); // update the functionality manager - assert( pNtk->pManFunc == Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) ); + assert( pNtk->pManFunc == Abc_FrameReadLibGen() ); pNtk->pManFunc = Extra_MmFlexStart(); pNtk->ntkFunc = ABC_FUNC_SOP; // update the nodes @@ -446,18 +446,18 @@ Abc_Ntk_t * Abc_NtkSuperChoice( Abc_Ntk_t * pNtk ) assert( Abc_NtkIsStrash(pNtk) ); // check that the library is available - if ( Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) == NULL ) + if ( Abc_FrameReadLibGen() == NULL ) { printf( "The current library is not available.\n" ); return 0; } // derive the supergate library - if ( Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()) == NULL && Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) ) + if ( Abc_FrameReadLibSuper() == NULL && Abc_FrameReadLibGen() ) { printf( "A simple supergate library is derived from gate library \"%s\".\n", - Mio_LibraryReadName(Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame())) ); - Map_SuperLibDeriveFromGenlib( Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) ); + Mio_LibraryReadName(Abc_FrameReadLibGen()) ); + Map_SuperLibDeriveFromGenlib( Abc_FrameReadLibGen() ); } // print a warning about choice nodes diff --git a/src/base/abci/abcPga.c b/src/base/abci/abcPga.c new file mode 100644 index 00000000..0562ddb2 --- /dev/null +++ b/src/base/abci/abcPga.c @@ -0,0 +1,155 @@ +/**CFile**************************************************************** + + FileName [abcPga.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Network and node package.] + + Synopsis [Interface with the FPGA mapping package.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: abcPga.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "abc.h" +#include "fraig.h" +#include "fpga.h" +#include "pga.h" +#include "cut.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static Abc_Ntk_t * Abc_NtkFromPga( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodeCuts ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Interface with the FPGA mapping package.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * Abc_NtkPga( Pga_Params_t * pParams ) +{ + Abc_Ntk_t * pNtkNew, * pNtk = pParams->pNtk; + Pga_Man_t * pMan; + Vec_Ptr_t * vNodeCuts; + + assert( Abc_NtkIsStrash(pNtk) ); + + // print a warning about choice nodes + if ( Abc_NtkGetChoiceNum( pNtk ) ) + printf( "Performing FPGA mapping with choices.\n" ); + + // start the mapping manager + pMan = Pga_ManStart( pParams ); + if ( pMan == NULL ) + return NULL; + + // perform mapping + vNodeCuts = Pga_DoMapping( pMan ); + + // transform the result of mapping into a BDD logic network + pNtkNew = Abc_NtkFromPga( pNtk, vNodeCuts ); + if ( pNtkNew == NULL ) + return NULL; + Pga_ManStop( pMan ); + Vec_PtrFree( vNodeCuts ); + + // make the network minimum base + Abc_NtkMinimumBase( pNtkNew ); + + // make sure that everything is okay + if ( !Abc_NtkCheck( pNtkNew ) ) + { + printf( "Abc_NtkPga: The network check has failed.\n" ); + Abc_NtkDelete( pNtkNew ); + return NULL; + } + return pNtkNew; +} + + +/**Function************************************************************* + + Synopsis [Creates the mapped network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * Abc_NtkFromPga( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodeCuts ) +{ + ProgressBar * pProgress; + DdManager * dd; + Abc_Ntk_t * pNtkNew; + Abc_Obj_t * pNode, * pFanin, * pNodeNew; + Cut_Cut_t * pCut; + Vec_Ptr_t * vLeaves, * vVisited; + int i, k, nDupGates; + // create the new network + pNtkNew = Abc_NtkStartFrom( pNtk, ABC_TYPE_LOGIC, ABC_FUNC_BDD ); + dd = pNtkNew->pManFunc; + // set the constant node + pNode = Abc_AigConst1(pNtk->pManFunc); + if ( Abc_ObjFanoutNum(pNode) > 0 ) + pNode->pCopy = Abc_NodeCreateConst1(pNtkNew); + // add new nodes in topologic order + vLeaves = Vec_PtrAlloc( 6 ); + vVisited = Vec_PtrAlloc( 100 ); + pProgress = Extra_ProgressBarStart( stdout, Vec_PtrSize(vNodeCuts) ); + Vec_PtrForEachEntry( vNodeCuts, pCut, i ) + { + Extra_ProgressBarUpdate( pProgress, i, NULL ); + // create the new node + pNodeNew = Abc_NtkCreateNode( pNtkNew ); + Vec_PtrClear( vLeaves ); + for ( k = 0; k < (int)pCut->nLeaves; k++ ) + { + // add the node representing the old fanin in the new network + pFanin = Abc_NtkObj( pNtk, pCut->pLeaves[k] ); + Vec_PtrPush( vLeaves, pFanin ); + Abc_ObjAddFanin( pNodeNew, pFanin->pCopy ); + } + // set the new node at the old node + pNode = Abc_NtkObj( pNtk, pCut->uSign ); // pCut->uSign contains the ID of the root node + pNode->pCopy = pNodeNew; + // create the function of the new node + pNodeNew->pData = Abc_NodeConeBdd( dd, dd->vars, pNode, vLeaves, vVisited ); Cudd_Ref( pNodeNew->pData ); + } + Extra_ProgressBarStop( pProgress ); + Vec_PtrFree( vVisited ); + Vec_PtrFree( vLeaves ); + // finalize the new network + Abc_NtkFinalize( pNtk, pNtkNew ); + // decouple the PO driver nodes to reduce the number of levels + nDupGates = Abc_NtkLogicMakeSimpleCos( pNtkNew, 1 ); +// if ( nDupGates && Fpga_ManReadVerbose(pMan) ) +// printf( "Duplicated %d gates to decouple the CO drivers.\n", nDupGates ); + return pNtkNew; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/base/abci/abcRewrite.c b/src/base/abci/abcRewrite.c index 81d97028..91a99a57 100644 --- a/src/base/abci/abcRewrite.c +++ b/src/base/abci/abcRewrite.c @@ -32,7 +32,7 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk, int fDrop ); +static Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk ); static void Abc_NodePrintCuts( Abc_Obj_t * pNode ); //////////////////////////////////////////////////////////////////////// @@ -52,7 +52,6 @@ static void Abc_NodePrintCuts( Abc_Obj_t * pNode ); ***********************************************************************/ int Abc_NtkRewrite( Abc_Ntk_t * pNtk, int fUpdateLevel, int fUseZeros, int fVerbose ) { - int fDrop = 0; ProgressBar * pProgress; Cut_Man_t * pManCut; Rwr_Man_t * pManRwr; @@ -72,7 +71,7 @@ int Abc_NtkRewrite( Abc_Ntk_t * pNtk, int fUpdateLevel, int fUseZeros, int fVerb Abc_NtkStartReverseLevels( pNtk ); // start the cut manager clk = clock(); - pManCut = Abc_NtkStartCutManForRewrite( pNtk, fDrop ); + pManCut = Abc_NtkStartCutManForRewrite( pNtk ); Rwr_ManAddTimeCuts( pManRwr, clock() - clk ); pNtk->pManCut = pManCut; @@ -142,7 +141,7 @@ Rwr_ManAddTimeTotal( pManRwr, clock() - clkStart ); SeeAlso [] ***********************************************************************/ -Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk, int fDrop ) +Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk ) { static Cut_Params_t Params, * pParams = &Params; Cut_Man_t * pManCut; @@ -153,10 +152,9 @@ Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk, int fDrop ) pParams->nVarsMax = 4; // the max cut size ("k" of the k-feasible cuts) pParams->nKeepMax = 250; // the max number of cuts kept at a node pParams->fTruth = 1; // compute truth tables - pParams->fHash = 1; // hash cuts to detect unique - pParams->fFilter = 0; // filter dominated cuts + pParams->fFilter = 1; // filter dominated cuts pParams->fSeq = 0; // compute sequential cuts - pParams->fDrop = fDrop; // drop cuts on the fly + pParams->fDrop = 0; // drop cuts on the fly pParams->fVerbose = 0; // the verbosiness flag pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); pManCut = Cut_ManStart( pParams ); @@ -182,13 +180,15 @@ Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk, int fDrop ) ***********************************************************************/ void Abc_NodePrintCuts( Abc_Obj_t * pNode ) { + Vec_Ptr_t * vCuts; Cut_Cut_t * pCut; - unsigned uTruth; + int k; + printf( "\nNode %s\n", Abc_ObjName(pNode) ); - for ( pCut = (Cut_Cut_t *)pNode->pCopy; pCut; pCut = pCut->pNext ) + vCuts = (Vec_Ptr_t *)pNode->pCopy; + Vec_PtrForEachEntry( vCuts, pCut, k ) { - uTruth = pCut->uTruth; - Extra_PrintBinary( stdout, &uTruth, 16 ); + Extra_PrintBinary( stdout, (unsigned *)&pCut->uSign, 16 ); printf( " " ); Cut_CutPrint( pCut ); printf( "\n" ); diff --git a/src/base/abci/abcTiming.c b/src/base/abci/abcTiming.c index b8524bd5..445978b3 100644 --- a/src/base/abci/abcTiming.c +++ b/src/base/abci/abcTiming.c @@ -470,9 +470,9 @@ void Abc_NtkSetNodeLevelsArrival( Abc_Ntk_t * pNtkOld ) int i; if ( pNtkOld->pManTime == NULL ) return; - if ( Mio_LibraryReadNand2(Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame())) == NULL ) + if ( Mio_LibraryReadNand2(Abc_FrameReadLibGen()) == NULL ) return; - tAndDelay = Mio_LibraryReadDelayNand2Max(Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame())); + tAndDelay = Mio_LibraryReadDelayNand2Max(Abc_FrameReadLibGen()); Abc_NtkForEachPi( pNtkOld, pNodeOld, i ) { pNodeNew = pNodeOld->pCopy; diff --git a/src/base/abci/module.make b/src/base/abci/module.make index d7c0add2..0123e213 100644 --- a/src/base/abci/module.make +++ b/src/base/abci/module.make @@ -10,6 +10,7 @@ SRC += src/base/abci/abc.c \ src/base/abci/abcMap.c \ src/base/abci/abcMiter.c \ src/base/abci/abcNtbdd.c \ + src/base/abci/abcPga.c \ src/base/abci/abcPrint.c \ src/base/abci/abcReconv.c \ src/base/abci/abcRefactor.c \ diff --git a/src/base/io/ioReadBlif.c b/src/base/io/ioReadBlif.c index 946de42b..7adec714 100644 --- a/src/base/io/ioReadBlif.c +++ b/src/base/io/ioReadBlif.c @@ -550,7 +550,7 @@ int Io_ReadBlifNetworkGate( Io_ReadBlif_t * p, Vec_Ptr_t * vTokens ) int i, nNames; // check that the library is available - pGenlib = Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()); + pGenlib = Abc_FrameReadLibGen(); if ( pGenlib == NULL ) { p->LineCur = Extra_FileReaderGetLineNumber(p->pReader, 0); diff --git a/src/base/main/main.c b/src/base/main/main.c index d44dade9..43ad6956 100644 --- a/src/base/main/main.c +++ b/src/base/main/main.c @@ -21,7 +21,7 @@ #include "mainInt.h" // this line should be included in the library project -#define _LIB +//#define _LIB //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// diff --git a/src/map/fpga/fpga.c b/src/map/fpga/fpga.c index 3d2ca913..9c56f6af 100644 --- a/src/map/fpga/fpga.c +++ b/src/map/fpga/fpga.c @@ -77,7 +77,7 @@ void Fpga_Init( Abc_Frame_t * pAbc ) ***********************************************************************/ void Fpga_End() { - Fpga_LutLibFree( Abc_FrameReadLibLut(Abc_FrameGetGlobalFrame()) ); + Fpga_LutLibFree( Abc_FrameReadLibLut() ); } @@ -221,7 +221,7 @@ int Fpga_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) } // set the new network - Fpga_LutLibPrint( Abc_FrameReadLibLut(Abc_FrameGetGlobalFrame()) ); + Fpga_LutLibPrint( Abc_FrameReadLibLut() ); return 0; usage: diff --git a/src/map/fpga/fpga.h b/src/map/fpga/fpga.h index 19241a74..04894d23 100644 --- a/src/map/fpga/fpga.h +++ b/src/map/fpga/fpga.h @@ -142,6 +142,11 @@ extern Fpga_Man_t * Fpga_ManDupFraig( Fraig_Man_t * pManFraig ); extern Fpga_Man_t * Fpga_ManBalanceFraig( Fraig_Man_t * pManFraig, int * pInputArrivals ); /*=== fpgaLib.c =============================================================*/ extern Fpga_LutLib_t * Fpga_LutLibDup( Fpga_LutLib_t * p ); +extern int Fpga_LutLibReadVarMax( Fpga_LutLib_t * p ); +extern float * Fpga_LutLibReadLutAreas( Fpga_LutLib_t * p ); +extern float * Fpga_LutLibReadLutDelays( Fpga_LutLib_t * p ); +extern float Fpga_LutLibReadLutArea( Fpga_LutLib_t * p, int Size ); +extern float Fpga_LutLibReadLutDelay( Fpga_LutLib_t * p, int Size ); /*=== fpgaTruth.c =============================================================*/ extern void * Fpga_TruthsCutBdd( void * dd, Fpga_Cut_t * pCut ); /*=== fpgaUtil.c =============================================================*/ diff --git a/src/map/fpga/fpgaCreate.c b/src/map/fpga/fpgaCreate.c index b7bfa3c5..c7acf974 100644 --- a/src/map/fpga/fpgaCreate.c +++ b/src/map/fpga/fpgaCreate.c @@ -164,7 +164,7 @@ Fpga_Man_t * Fpga_ManCreate( int nInputs, int nOutputs, int fVerbose ) // start the manager p = ALLOC( Fpga_Man_t, 1 ); memset( p, 0, sizeof(Fpga_Man_t) ); - p->pLutLib = Abc_FrameReadLibLut(Abc_FrameGetGlobalFrame()); + p->pLutLib = Abc_FrameReadLibLut(); p->nVarsMax = p->pLutLib->LutMax; p->fVerbose = fVerbose; p->fAreaRecovery = 1; diff --git a/src/map/fpga/fpgaCut.c b/src/map/fpga/fpgaCut.c index 5b5fbe69..f9afa581 100644 --- a/src/map/fpga/fpgaCut.c +++ b/src/map/fpga/fpgaCut.c @@ -245,7 +245,7 @@ Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Nod // set at the node pNode->pCuts = pCut; // remove the dominated cuts - Fpga_CutFilter( p, pNode ); +// Fpga_CutFilter( p, pNode ); // set the phase correctly if ( pNode->pRepr && Fpga_NodeComparePhase(pNode, pNode->pRepr) ) { diff --git a/src/map/fpga/fpgaLib.c b/src/map/fpga/fpgaLib.c index 9fd8e281..eb0b5c93 100644 --- a/src/map/fpga/fpgaLib.c +++ b/src/map/fpga/fpgaLib.c @@ -28,6 +28,23 @@ /**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_LutLibReadLutDelays( Fpga_LutLib_t * p ) { return p->pLutDelays; } +float Fpga_LutLibReadLutArea( Fpga_LutLib_t * p, int Size ) { assert( Size <= p->LutMax ); return p->pLutAreas[Size]; } +float Fpga_LutLibReadLutDelay( Fpga_LutLib_t * p, int Size ) { assert( Size <= p->LutMax ); return p->pLutDelays[Size]; } + +/**Function************************************************************* + Synopsis [Reads the description of LUTs from the LUT library file.] Description [] diff --git a/src/map/mapper/mapper.c b/src/map/mapper/mapper.c index e59fa4a3..3cfd159f 100644 --- a/src/map/mapper/mapper.c +++ b/src/map/mapper/mapper.c @@ -61,7 +61,7 @@ void Map_Init( Abc_Frame_t * pAbc ) void Map_End() { // Map_SuperLibFree( s_pSuperLib ); - Map_SuperLibFree( Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()) ); + Map_SuperLibFree( Abc_FrameReadLibSuper() ); } diff --git a/src/map/mapper/mapperCreate.c b/src/map/mapper/mapperCreate.c index 31fbf0ea..3dee7f7e 100644 --- a/src/map/mapper/mapperCreate.c +++ b/src/map/mapper/mapperCreate.c @@ -183,7 +183,7 @@ Map_Man_t * Map_ManCreate( int nInputs, int nOutputs, int fVerbose ) int i; // derive the supergate library - if ( Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()) == NULL ) + if ( Abc_FrameReadLibSuper() == NULL ) { printf( "The supergate library is not specified. Use \"read_library\" or \"read_super\".\n" ); return NULL; @@ -192,7 +192,7 @@ Map_Man_t * Map_ManCreate( int nInputs, int nOutputs, int fVerbose ) // start the manager p = ALLOC( Map_Man_t, 1 ); memset( p, 0, sizeof(Map_Man_t) ); - p->pSuperLib = Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()); + p->pSuperLib = Abc_FrameReadLibSuper(); p->nVarsMax = p->pSuperLib->nVarsMax; p->fVerbose = fVerbose; p->fEpsilon = (float)0.001; diff --git a/src/map/mapper/mapperCut.c b/src/map/mapper/mapperCut.c index b5ce4018..514d9da8 100644 --- a/src/map/mapper/mapperCut.c +++ b/src/map/mapper/mapperCut.c @@ -208,7 +208,7 @@ Map_Cut_t * Map_CutCompute( Map_Man_t * p, Map_CutTable_t * pTable, Map_Node_t * // set at the node pNode->pCuts = pCut; // remove the dominated cuts -// Map_CutFilter( p, pNode ); + Map_CutFilter( p, pNode ); // set the phase correctly if ( pNode->pRepr && Map_NodeComparePhase(pNode, pNode->pRepr) ) { diff --git a/src/map/mio/mio.c b/src/map/mio/mio.c index bb6dbba1..569bcceb 100644 --- a/src/map/mio/mio.c +++ b/src/map/mio/mio.c @@ -108,7 +108,7 @@ void Mio_Init( Abc_Frame_t * pAbc ) void Mio_End() { // Mio_LibraryDelete( s_pLib ); - Mio_LibraryDelete( Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) ); + Mio_LibraryDelete( Abc_FrameReadLibGen() ); } @@ -181,7 +181,7 @@ int Mio_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) return 1; } // free the current superlib because it depends on the old Mio library - if ( Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()) ) + if ( Abc_FrameReadLibSuper() ) { extern void Map_SuperLibFree( Map_SuperLib_t * p ); // Map_SuperLibFree( s_pSuperLib ); @@ -252,7 +252,7 @@ int Mio_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) } // set the new network - Mio_WriteLibrary( stdout, Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()), 0 ); + Mio_WriteLibrary( stdout, Abc_FrameReadLibGen(), 0 ); return 0; usage: diff --git a/src/map/pga/module.make b/src/map/pga/module.make new file mode 100644 index 00000000..2a45327e --- /dev/null +++ b/src/map/pga/module.make @@ -0,0 +1,4 @@ +SRC += src/map/pga/pgaCore.c \ + src/map/pga/pgaMan.c \ + src/map/pga/pgaMatch.c \ + src/map/pga/pgaUtil.c diff --git a/src/map/pga/pga.h b/src/map/pga/pga.h new file mode 100644 index 00000000..5575e0ce --- /dev/null +++ b/src/map/pga/pga.h @@ -0,0 +1,72 @@ +/**CFile**************************************************************** + + FileName [pga.h] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [FPGA mapper.] + + Synopsis [External declarations.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: pga.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#ifndef __PGA_H__ +#define __PGA_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// BASIC TYPES /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Pga_ManStruct_t_ Pga_Man_t; +typedef struct Pga_ParamsStruct_t_ Pga_Params_t; + +struct Pga_ParamsStruct_t_ +{ + // data for mapping + Abc_Ntk_t * pNtk; // the network to be mapped + Fpga_LutLib_t * pLutLib; // the LUT library + float * pSwitching; // switching activity for each node + // mapping parameters + int fDropCuts; // enables cut dropping + int fAreaFlow; // enables area flow minimization + int fArea; // enables area minimization + int fSwitching; // enables switching activity minimization + int fVerbose; // enables verbose output +}; + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== pgaApi.c ==========================================================*/ +extern Vec_Ptr_t * Pga_DoMapping( Pga_Man_t * p ); +/*=== pgaMan.c ==========================================================*/ +extern Pga_Man_t * Pga_ManStart( Pga_Params_t * pParams ); +extern void Pga_ManStop( Pga_Man_t * p ); + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + +#endif + diff --git a/src/map/pga/pgaCore.c b/src/map/pga/pgaCore.c new file mode 100644 index 00000000..09a9d218 --- /dev/null +++ b/src/map/pga/pgaCore.c @@ -0,0 +1,152 @@ +/**CFile**************************************************************** + + FileName [pgaCore.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [FPGA mapper.] + + Synopsis [External APIs of the FPGA manager.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: pgaCore.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "pgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Pga_MappingInitCis( Pga_Man_t * p ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**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 [] + +***********************************************************************/ +Vec_Ptr_t * Pga_DoMapping( Pga_Man_t * p ) +{ + int fShowSwitching = 0; + float aAreaTotalCur; + int Iter, clk, clkTotal = clock(); + + // assign the arrival times of the PIs + Pga_MappingInitCis( p ); + + // map the AIG for delay +clk = clock(); + Pga_MappingMatches( p, 0 ); +p->timeDelay = clock() - clk; + + // compute area, set references, and collect nodes used in the mapping + Iter = 1; + aAreaTotalCur = Pga_MappingSetRefsAndArea( p ); +if ( p->pParams->fVerbose ) +{ +printf( "Iteration %dD : Area = %8.1f ", Iter++, aAreaTotalCur ); +if ( fShowSwitching ) +printf( "Switch = %8.1f ", Pga_MappingGetSwitching(p) ); +PRT( "Time", p->timeDelay ); +} + + if ( p->pParams->fAreaFlow ) + { +clk = clock(); + // compute the required times and the fanouts + Pga_MappingComputeRequired( p ); + // remap topologically + Pga_MappingMatches( p, 1 ); +p->timeAreaFlow = clock() - clk; + // get the resulting area + aAreaTotalCur = Pga_MappingSetRefsAndArea( p ); + // note that here we do not update the reference counter + // for some reason, this works better on benchmarks +if ( p->pParams->fVerbose ) +{ +printf( "Iteration %dF : Area = %8.1f ", Iter++, aAreaTotalCur ); +if ( fShowSwitching ) +printf( "Switch = %8.1f ", Pga_MappingGetSwitching(p) ); +PRT( "Time", p->timeAreaFlow ); +} + } + + if ( p->pParams->fArea ) + { +clk = clock(); + // compute the required times and the fanouts + Pga_MappingComputeRequired( p ); + // remap topologically + if ( p->pParams->fSwitching ) + Pga_MappingMatches( p, 3 ); + else + Pga_MappingMatches( p, 2 ); +p->timeArea = clock() - clk; + // get the resulting area + aAreaTotalCur = Pga_MappingSetRefsAndArea( p ); +if ( p->pParams->fVerbose ) +{ +printf( "Iteration %d%s : Area = %8.1f ", Iter++, (p->pParams->fSwitching?"S":"A"), aAreaTotalCur ); +if ( fShowSwitching ) +printf( "Switch = %8.1f ", Pga_MappingGetSwitching(p) ); +PRT( "Time", p->timeArea ); +} + } + p->AreaGlobal = aAreaTotalCur; + + if ( p->pParams->fVerbose ) + Pga_MappingPrintOutputArrivals( p ); + + // return the mapping + return Pga_MappingResults( p ); +} + +/**Function************************************************************* + + Synopsis [Initializes the CI node arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Pga_MappingInitCis( Pga_Man_t * p ) +{ + Pga_Node_t * pNode; + float * pCiArrs; + int i; + // get the CI arrival times + pCiArrs = Abc_NtkGetCiArrivalFloats( p->pParams->pNtk ); + // assign the arrival times of the PIs + Pga_ManForEachCi( p, pNode, i ) + pNode->Match.Delay = pCiArrs[i]; + free( pCiArrs ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/pga/pgaInt.h b/src/map/pga/pgaInt.h new file mode 100644 index 00000000..27355459 --- /dev/null +++ b/src/map/pga/pgaInt.h @@ -0,0 +1,132 @@ +/**CFile**************************************************************** + + FileName [pgaInt.h] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [FPGA mapper.] + + Synopsis [Internal declarations.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: pgaInt.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#ifndef __PGA_INT_H__ +#define __PGA_INT_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#include <stdio.h> +#include "abc.h" +#include "fraig.h" +#include "fpga.h" +#include "cut.h" +#include "pga.h" + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// BASIC TYPES /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Pga_NodeStruct_t_ Pga_Node_t; +typedef struct Pga_MatchStruct_t_ Pga_Match_t; + +struct Pga_ManStruct_t_ +{ + // mapping parameters + Pga_Params_t * pParams; // input data + // mapping structures + Pga_Node_t * pMemory; // the memory for all mapping structures + Vec_Ptr_t * vStructs; // mapping structures one-to-one with ABC nodes + Vec_Ptr_t * vOrdering; // mapping nodes ordered by level + // k-feasible cuts + int nVarsMax; // the "k" of k-feasible cuts + Cut_Man_t * pManCut; // the cut manager + // LUT library + float * pLutDelays; // the delay of the LUTs + float * pLutAreas; // the areas of the LUTs + float Epsilon; + // global parameters + float AreaGlobal; // the total area of this mapping + float ArrivalGlobal; // the largest delay of any path + float RequiredGlobal;// the global required time (may be different from largest delay) + float RequiredUser; // the required time given by the user + // runtime stats + int timeToMap; // the time to start the mapper + int timeCuts; // the time to compute the cuts + int timeDelay; // the time to compute delay + int timeAreaFlow; // the time to perform area flow optimization + int timeArea; // the time to perform area flow optimization + int timeToNet; // the time to transform back to network + int timeTotal; // the total time + int time1; // temporary + int time2; // temporary +}; + +struct Pga_MatchStruct_t_ +{ + Cut_Cut_t * pCut; // the best cut + float Delay; // the arrival time of this cut + float Area; // the area of this cut +}; + +struct Pga_NodeStruct_t_ +{ + int Id; // ID of the node + int nRefs; // the number of references + float EstRefs; // the estimated reference counter + float Required; // the required time + float Switching; // the switching activity + Pga_Match_t Match; // the best match at the node +}; + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +static inline Pga_Node_t * Pga_Node( Pga_Man_t * p, int Id ) { return p->vStructs->pArray[Id]; } + +// iterator through the CIs +#define Pga_ManForEachCi( p, pCi, i ) \ + for ( i = 0; (i < Abc_NtkCiNum(p->pParams->pNtk)) && (((pCi) = Pga_Node(p, Abc_NtkCi(p->pParams->pNtk,i)->Id)), 1); i++ ) +// iterator through the CO derivers +#define Pga_ManForEachCoDriver( p, pCo, i ) \ + for ( i = 0; (i < Abc_NtkCoNum(p->pParams->pNtk)) && (((pCo) = Pga_Node(p, Abc_ObjFaninId0(Abc_NtkCo(p->pParams->pNtk,i)))), 1); i++ ) +// iterators through the CIs and internal nodes +#define Pga_ManForEachObjDirect( p, pNode, i ) \ + Vec_PtrForEachEntry( p->vOrdering, pNode, i ) +#define Pga_ManForEachObjReverse( p, pNode, i ) \ + Vec_PtrForEachEntryReverse( p->vOrdering, pNode, i ) + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== pgaMatch.c ==========================================================*/ +extern void Pga_MappingMatches( Pga_Man_t * p, int Mode ); +/*=== pgaUtil.c ==========================================================*/ +extern Vec_Ptr_t * Pga_MappingResults( Pga_Man_t * p ); +extern float Pga_TimeComputeArrivalMax( Pga_Man_t * p ); +extern void Pga_MappingComputeRequired( Pga_Man_t * p ); +extern float Pga_MappingSetRefsAndArea( Pga_Man_t * p ); +extern float Pga_MappingGetSwitching( Pga_Man_t * p ); +extern void Pga_MappingPrintOutputArrivals( Pga_Man_t * p ); + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + +#endif + diff --git a/src/map/pga/pgaMan.c b/src/map/pga/pgaMan.c new file mode 100644 index 00000000..d7573ecf --- /dev/null +++ b/src/map/pga/pgaMan.c @@ -0,0 +1,180 @@ +/**CFile**************************************************************** + + FileName [pgaMan.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [FPGA mapper.] + + Synopsis [Mapping manager.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: pgaMan.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "pgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static Cut_Man_t * Pga_ManStartCutMan( Pga_Params_t * pParamsPga ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Starts the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Pga_Man_t * Pga_ManStart( Pga_Params_t * pParams ) +{ + Pga_Man_t * p; + Pga_Node_t * pNode; + Cut_Man_t * pManCut; + Abc_Ntk_t * pNtk; + Abc_Obj_t * pObj; + int i, Counter; + int clk = clock(); + + // make sure the network is given + pNtk = pParams->pNtk; + if ( pNtk == NULL ) + { + printf( "Network is not specified.\n" ); + return NULL; + } + if ( !Abc_NtkIsStrash(pNtk) ) + { + printf( "Mapping can only be applied to an AIG.\n" ); + return NULL; + } + // the cut manager if given should be in sinc + pManCut = pNtk->pManCut; + if ( pManCut && Cut_ManReadVarsMax(pManCut) != Fpga_LutLibReadVarMax(pParams->pLutLib) ) + { + printf( "The precomputed cuts have different size.\n" ); + return NULL; + } + // make sure the nodes are in the topological order + if ( !Abc_NtkIsDfsOrdered(pNtk) ) + { + printf( "The nodes of the network are not DFS ordered.\n" ); +// Abc_NtkReassignIds( pNtk ); + return NULL; + } + // make sure there are no dangling nodes (unless they are choices) + + // start the mapping manager + p = ALLOC( Pga_Man_t, 1 ); + memset( p, 0, sizeof(Pga_Man_t) ); + p->pParams = pParams; + p->nVarsMax = Fpga_LutLibReadVarMax(pParams->pLutLib); + p->pManCut = pManCut? pManCut : Pga_ManStartCutMan(pParams); + p->vOrdering = Abc_AigGetLevelizedOrder(pNtk, 0); // what happens with dangling nodes??? + p->pLutAreas = Fpga_LutLibReadLutAreas(pParams->pLutLib); + p->pLutDelays = Fpga_LutLibReadLutDelays(pParams->pLutLib); + p->Epsilon = (float)0.00001; + + // allocate mapping structures + p->pMemory = ALLOC( Pga_Node_t, Abc_NtkObjNum(pNtk) ); + memset( p->pMemory, 0, sizeof(Pga_Node_t) * Abc_NtkObjNum(pNtk) ); + p->vStructs = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) ); + Counter = 0; + Abc_NtkForEachObj( pNtk, pObj, i ) + { + pNode = p->pMemory + Counter++; + pNode->Id = pObj->Id; + pNode->nRefs = pObj->vFanouts.nSize; + pNode->Required = ABC_INFINITY; + pNode->Match.Area = ABC_INFINITY; + // skip secondary nodes + if ( Abc_ObjFanoutNum(pObj) == 0 ) + continue; + Vec_PtrWriteEntry( p->vStructs, pObj->Id, pNode ); + } + assert( Counter == Abc_NtkObjNum(pNtk) ); + // update order to depend on mapping nodes + Vec_PtrForEachEntry( p->vOrdering, pObj, i ) + Vec_PtrWriteEntry( p->vOrdering, i, Pga_Node(p,pObj->Id) ); +p->timeToMap = clock() - clk; + return p; +} + +/**Function************************************************************* + + Synopsis [Stops the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Pga_ManStop( Pga_Man_t * p ) +{ + Cut_ManStop( p->pManCut ); + Vec_PtrFree( p->vOrdering ); + Vec_PtrFree( p->vStructs ); + free( p->pMemory ); + free( p ); +} + +/**Function************************************************************* + + Synopsis [Starts the cut manager for FPGA mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Man_t * Pga_ManStartCutMan( Pga_Params_t * pParamsPga ) +{ + static Cut_Params_t Params, * pParams = &Params; + Abc_Ntk_t * pNtk = pParamsPga->pNtk; + Cut_Man_t * pManCut; + Abc_Obj_t * pObj; + int i; + // start the cut manager + memset( pParams, 0, sizeof(Cut_Params_t) ); + pParams->nVarsMax = Fpga_LutLibReadVarMax(pParamsPga->pLutLib); // max cut size + pParams->nKeepMax = 250; // the max number of cuts kept at a node + pParams->fTruth = 0; // compute truth tables + pParams->fFilter = 1; // filter dominated cuts + pParams->fSeq = 0; // compute sequential cuts + pParams->fDrop = pParamsPga->fDropCuts; // drop cuts on the fly + pParams->fVerbose = 0; // the verbosiness flag + pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); + pManCut = Cut_ManStart( pParams ); + if ( pParams->fDrop ) + Cut_ManSetFanoutCounts( pManCut, Abc_NtkFanoutCounts(pNtk) ); + // set cuts for PIs + Abc_NtkForEachCi( pNtk, pObj, i ) + if ( Abc_ObjFanoutNum(pObj) > 0 ) + Cut_NodeSetTriv( pManCut, pObj->Id ); + return pManCut; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/pga/pgaMatch.c b/src/map/pga/pgaMatch.c new file mode 100644 index 00000000..f9f6b5c4 --- /dev/null +++ b/src/map/pga/pgaMatch.c @@ -0,0 +1,378 @@ +/**CFile**************************************************************** + + FileName [pgaMatch.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [FPGA mapper.] + + Synopsis [Mapping procedures.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: pgaMatch.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "pgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static char * s_Modes[4] = { "Delay", "Flow", "Area", "Switch" }; + +static int Pga_MappingMatchNode( Pga_Man_t * p, int NodeId, Cut_Cut_t * pList, int Mode ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Performs mapping for delay, area-flow, area, switching.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Pga_MappingMatches( Pga_Man_t * p, int Mode ) +{ + ProgressBar * pProgress; + Abc_Ntk_t * pNtk; + Abc_Obj_t * pObj; + Cut_Cut_t * pList; + int i, clk; + + assert( Mode >= 0 && Mode <= 2 ); + + // match LUTs with nodes in the topological order + pNtk = p->pParams->pNtk; + pProgress = Extra_ProgressBarStart( stdout, Abc_NtkObjNumMax(pNtk) ); + Abc_NtkForEachObj( pNtk, pObj, i ) + { + // skip the CIs + if ( Abc_ObjIsCi(pObj) ) + continue; + // when we reached a CO, it is time to deallocate the cuts + if ( Abc_ObjIsCo(pObj) ) + { + if ( p->pParams->fDropCuts ) + Cut_NodeTryDroppingCuts( p->pManCut, Abc_ObjFaninId0(pObj) ); + continue; + } + // skip constant node, it has no cuts + if ( Abc_NodeIsConst(pObj) ) + continue; + // get the cuts +clk = clock(); + pList = Abc_NodeGetCutsRecursive( p->pManCut, pObj ); +p->timeCuts += clock() - clk; + // match the node + Pga_MappingMatchNode( p, pObj->Id, pList, Mode ); + Extra_ProgressBarUpdate( pProgress, i, s_Modes[Mode] ); + } + Extra_ProgressBarStop( pProgress ); +} + + + + +/**Function************************************************************* + + Synopsis [Computes the match of the cut.] + + Description [Returns 1 if feasible.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline float Pga_CutGetArrival( Pga_Man_t * p, Cut_Cut_t * pCut ) +{ + float DelayCur, DelayWorst; + unsigned i; + assert( pCut->nLeaves > 1 ); + DelayWorst = -ABC_INFINITY; + for ( i = 0; i < pCut->nLeaves; i++ ) + { + DelayCur = Pga_Node(p, pCut->pLeaves[i])->Match.Delay; + if ( DelayWorst < DelayCur ) + DelayWorst = DelayCur; + } + DelayWorst += p->pLutDelays[pCut->nLeaves]; + return DelayWorst; +} + +/**Function************************************************************* + + Synopsis [Computes the match of the cut.] + + Description [Returns 1 if feasible.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline float Pga_CutGetAreaFlow( Pga_Man_t * p, Cut_Cut_t * pCut ) +{ + float Flow; + Pga_Node_t * pNode; + unsigned i; + assert( pCut->nLeaves > 1 ); + Flow = p->pLutAreas[pCut->nLeaves]; + for ( i = 0; i < pCut->nLeaves; i++ ) + { + pNode = Pga_Node(p, pCut->pLeaves[i]); + assert( pNode->EstRefs > 0 ); + Flow += pNode->Match.Area / pNode->EstRefs; + } + return Flow; +} + +/**function************************************************************* + + synopsis [References the cut.] + + description [This procedure is similar to the procedure NodeReclaim.] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Pga_CutRef( Pga_Man_t * p, Pga_Node_t * pNode, Cut_Cut_t * pCut ) +{ + Pga_Node_t * pFanin; + float aArea; + unsigned i; + // start the area of this cut + aArea = p->pLutAreas[pCut->nLeaves]; + // go through the children + for ( i = 0; i < pCut->nLeaves; i++ ) + { + pFanin = Pga_Node(p, pCut->pLeaves[i]); + assert( pFanin->nRefs >= 0 ); + if ( pFanin->nRefs++ > 0 ) + continue; + if ( pFanin->Match.pCut == NULL ) + continue; + aArea += Pga_CutRef( p, pFanin, pFanin->Match.pCut ); + } + return aArea; +} + +/**function************************************************************* + + synopsis [Dereferences the cut.] + + description [This procedure is similar to the procedure NodeRecusiveDeref.] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Pga_CutDeref( Pga_Man_t * p, Pga_Node_t * pNode, Cut_Cut_t * pCut ) +{ + Pga_Node_t * pFanin; + float aArea; + unsigned i; + // start the area of this cut + aArea = p->pLutAreas[pCut->nLeaves]; + // go through the children + for ( i = 0; i < pCut->nLeaves; i++ ) + { + pFanin = Pga_Node(p, pCut->pLeaves[i]); + assert( pFanin->nRefs > 0 ); + if ( --pFanin->nRefs > 0 ) + continue; + if ( pFanin->Match.pCut == NULL ) + continue; + aArea += Pga_CutDeref( p, pFanin, pFanin->Match.pCut ); + } + return aArea; +} + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [Assumes that the cut is deferenced.] + + sideeffects [] + + seealso [] + +***********************************************************************/ +static inline float Pga_CutGetAreaDerefed( Pga_Man_t * p, Pga_Node_t * pNode, Cut_Cut_t * pCut ) +{ + float aResult, aResult2; + assert( pCut->nLeaves > 1 ); + aResult2 = Pga_CutRef( p, pNode, pCut ); + aResult = Pga_CutDeref( p, pNode, pCut ); + assert( aResult == aResult2 ); + return aResult; +} + + + +/**Function************************************************************* + + Synopsis [Computes the match of the cut.] + + Description [Returns 1 if feasible.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Pga_MappingMatchCut( Pga_Man_t * p, Pga_Node_t * pNode, Cut_Cut_t * pCut, int Mode, Pga_Match_t * pMatch ) +{ + // compute the arrival time of the cut and its area flow + pMatch->Delay = Pga_CutGetArrival( p, pCut ); + // drop the cut if it does not meet the required times + if ( pMatch->Delay > pNode->Required + p->Epsilon ) + return 0; + // get the second parameter + if ( Mode == 0 || Mode == 1 ) + pMatch->Area = Pga_CutGetAreaFlow( p, pCut ); + else if ( Mode == 2 ) + pMatch->Area = Pga_CutGetAreaDerefed( p, pNode, pCut ); +// else if ( Mode == 3 ) +// pMatch->Area = Pga_CutGetSwitching( p, pNode, pCut ); + // if no cut is assigned, use the current one + pMatch->pCut = pCut; + return 1; +} + +/**Function************************************************************* + + Synopsis [Compares two matches.] + + Description [Returns 1 if the second match is better.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Pga_MappingCompareMatches( Pga_Man_t * p, Pga_Match_t * pMatchBest, Pga_Match_t * pMatchCur, int Mode ) +{ + if ( pMatchBest->pCut == NULL ) + return 1; + if ( Mode == 0 ) + { + // compare delays + if ( pMatchBest->Delay < pMatchCur->Delay - p->Epsilon ) + return 0; + if ( pMatchBest->Delay > pMatchCur->Delay + p->Epsilon ) + return 1; + // compare areas + if ( pMatchBest->Area < pMatchCur->Area - p->Epsilon ) + return 0; + if ( pMatchBest->Area > pMatchCur->Area + p->Epsilon ) + return 1; + // if equal, do not update + return 0; + } + else + { + // compare areas + if ( pMatchBest->Area < pMatchCur->Area - p->Epsilon ) + return 0; + if ( pMatchBest->Area > pMatchCur->Area + p->Epsilon ) + return 1; + // compare delays + if ( pMatchBest->Delay < pMatchCur->Delay - p->Epsilon ) + return 0; + if ( pMatchBest->Delay > pMatchCur->Delay + p->Epsilon ) + return 1; + // if equal, do not update + return 0; + } +} + + +/**Function************************************************************* + + Synopsis [Computes the best matching for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Pga_MappingMatchNode( Pga_Man_t * p, int NodeId, Cut_Cut_t * pList, int Mode ) +{ + Pga_Match_t MatchCur, * pMatchCur = &MatchCur; + Pga_Match_t MatchBest, * pMatchBest = &MatchBest; + Pga_Node_t * pNode; + Cut_Cut_t * pCut; + + // get the mapping node + pNode = Pga_Node( p, NodeId ); + + // prepare for mapping + if ( Mode == 0 ) + pNode->EstRefs = (float)pNode->nRefs; + else if ( Mode == 1 ) + pNode->EstRefs = (float)((2.0 * pNode->EstRefs + pNode->nRefs) / 3.0); + else if ( Mode == 2 && pNode->nRefs > 0 ) + Pga_CutDeref( p, pNode, pNode->Match.pCut ); +// else if ( Mode == 3 && pNode->nRefs > 0 ) +// Pga_CutDerefSwitch( p, pNode, pNode->Match.pCut ); + + // start the best match + pMatchBest->pCut = NULL; + + // go through the other cuts + assert( pList->pNext ); + for ( pCut = pList->pNext; pCut; pCut = pCut->pNext ) + { + // compute match for this cut + if ( !Pga_MappingMatchCut( p, pNode, pCut, Mode, pMatchCur ) ) + continue; + // compare matches + if ( !Pga_MappingCompareMatches( p, pMatchBest, pMatchCur, Mode ) ) + continue; + // the best match should be updated + *pMatchBest = *pMatchCur; + } + + // make sure the match is found + if ( pMatchBest->pCut != NULL ) + pNode->Match = *pMatchBest; + else + { + assert( 0 ); +// Pga_MappingMatchCut( p, pNode, pCut, Mode, pNode->Match ); + } + + // reference the best cut + if ( Mode == 2 && pNode->nRefs > 0 ) + Pga_CutRef( p, pNode, pNode->Match.pCut ); +// else if ( Mode == 3 && pNode->nRefs > 0 ) +// Pga_CutRefSwitch( p, pNode, pNode->Match.pCut ); + return 1; +} + + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/pga/pgaUtil.c b/src/map/pga/pgaUtil.c new file mode 100644 index 00000000..73f3d381 --- /dev/null +++ b/src/map/pga/pgaUtil.c @@ -0,0 +1,320 @@ +/**CFile**************************************************************** + + FileName [pgaUtil.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [FPGA mapper.] + + Synopsis [Verious utilities.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: pgaUtil.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "pgaInt.h" + +#define PGA_CO_LIST_SIZE 5 + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Returns the results of mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * Pga_MappingResults( Pga_Man_t * p ) +{ + Vec_Ptr_t * vResult; + Pga_Node_t * pNode; + int i; + vResult = Vec_PtrAlloc( 1000 ); + Pga_ManForEachObjDirect( p, pNode, i ) + { + // skip the CIs and nodes not used in the mapping + if ( !pNode->Match.pCut || !pNode->nRefs ) + continue; + pNode->Match.pCut->uSign = pNode->Id; + Vec_PtrPush( vResult, pNode->Match.pCut ); + } + return vResult; +} + +/**Function************************************************************* + + Synopsis [Computes the maximum arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Pga_TimeComputeArrivalMax( Pga_Man_t * p ) +{ + Pga_Node_t * pNode; + float ArrivalMax; + int i; + ArrivalMax = -ABC_INFINITY; + Pga_ManForEachCoDriver( p, pNode, i ) + ArrivalMax = ABC_MAX( ArrivalMax, pNode->Match.Delay ); + return ArrivalMax; +} + + +/**Function************************************************************* + + Synopsis [Computes required times of all nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Pga_MappingComputeRequired( Pga_Man_t * p ) +{ + Pga_Node_t * pNode, * pFanin; + Cut_Cut_t * pCutBest; + float RequiredNew; + int i, k; + // clean the required times of all nodes + Pga_ManForEachObjDirect( p, pNode, i ) + pNode->Required = ABC_INFINITY; + // get the global required times + p->AreaGlobal = Pga_TimeComputeArrivalMax( p ); + p->RequiredGlobal = ABC_MAX( p->AreaGlobal, p->RequiredUser ); + // set the global required times of the CO drivers + Pga_ManForEachCoDriver( p, pNode, i ) + pNode->Required = p->RequiredGlobal; + // propagate the required times in the reverse topological order + Pga_ManForEachObjReverse( p, pNode, i ) + { + // skip the CIs and nodes not used in the mapping + if ( !pNode->Match.pCut || !pNode->nRefs ) + continue; + // get the required time for children + pCutBest = pNode->Match.pCut; + RequiredNew = pNode->Required - p->pLutDelays[pCutBest->nLeaves]; + // update the required time of the children + for ( k = 0; k < (int)pCutBest->nLeaves; k++ ) + { + pFanin = Pga_Node( p, pCutBest->pLeaves[k] ); + pFanin->Required = ABC_MIN( pFanin->Required, RequiredNew ); + } + } + // check that the required times does not contradict the arrival times + Pga_ManForEachObjDirect( p, pNode, i ) + assert( !pNode->Match.pCut || pNode->Match.Delay < pNode->Required + p->Epsilon ); + +} + +/**Function************************************************************* + + Synopsis [Sets references and computes area for the current mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Pga_MappingSetRefsAndArea( Pga_Man_t * p ) +{ + Pga_Node_t * pNode, * pFanin; + Cut_Cut_t * pCutBest; + float AreaTotal; + int i, k; + // clean all the references + Pga_ManForEachObjDirect( p, pNode, i ) + pNode->nRefs = 0; + // set the references of the CO drivers + Pga_ManForEachCoDriver( p, pNode, i ) + pNode->nRefs++; + // go through the nodes in the reverse order + AreaTotal = 0.0; + Pga_ManForEachObjReverse( p, pNode, i ) + { + // skip the CIs and nodes not used in the mapping + if ( !pNode->Match.pCut || !pNode->nRefs ) + continue; + // increate the reference count of the children + pCutBest = pNode->Match.pCut; + AreaTotal += p->pLutAreas[pCutBest->nLeaves]; + // update the required time of the children + for ( k = 0; k < (int)pCutBest->nLeaves; k++ ) + { + pFanin = Pga_Node( p, pCutBest->pLeaves[k] ); + pFanin->nRefs++; + } + } + return AreaTotal; +} + +/**Function************************************************************* + + Synopsis [Computes switching activity of the mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Pga_MappingGetSwitching( Pga_Man_t * p ) +{ + float Switching; + Pga_Node_t * pNode; + int i; + Switching = 0; + Pga_ManForEachObjDirect( p, pNode, i ) + { + // skip the CIs and nodes not used in the mapping + if ( !pNode->Match.pCut || !pNode->nRefs ) + continue; + Switching += pNode->Switching; + } + return Switching; +} + +/**Function************************************************************* + + Synopsis [Compares the outputs by their arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Pga_MappingCompareOutputDelay( Pga_Node_t ** ppNode1, Pga_Node_t ** ppNode2 ) +{ + Pga_Node_t * pNode1 = *ppNode1; + Pga_Node_t * pNode2 = *ppNode2; + float Arrival1 = pNode1->Match.Delay; + float Arrival2 = pNode2->Match.Delay; + 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 Pga_MappingFindLatest( Pga_Man_t * p, int * pNodes, int nNodesMax ) +{ + Pga_Node_t * pNodeI, * pNodeK; + Abc_Obj_t * pObjCo; + int nNodes, i, k, v; + assert( Abc_NtkCoNum(p->pParams->pNtk) >= nNodesMax ); + pNodes[0] = 0; + nNodes = 1; +// for ( i = 1; i < p->nOutputs; i++ ) + Pga_ManForEachCoDriver( p, pNodeI, i ) + { + for ( k = nNodes - 1; k >= 0; k-- ) + { + pObjCo = Abc_NtkCo( p->pParams->pNtk, pNodes[k] ); + pNodeK = Pga_Node( p, Abc_ObjFaninId0(pObjCo) ); + if ( Pga_MappingCompareOutputDelay( &pNodeK, &pNodeI ) >= 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 Pga_MappingPrintOutputArrivals( Pga_Man_t * p ) +{ + int pSorted[PGA_CO_LIST_SIZE]; + Abc_Ntk_t * pNtk = p->pParams->pNtk; + Abc_Obj_t * pObjCo; + Pga_Node_t * pNode; + int Limit, MaxNameSize, i; + + // determine the number of nodes to print + Limit = (Abc_NtkCoNum(pNtk) < PGA_CO_LIST_SIZE)? Abc_NtkCoNum(pNtk) : PGA_CO_LIST_SIZE; + + // determine the order + Pga_MappingFindLatest( p, pSorted, Limit ); + + // determine max size of the node's name + MaxNameSize = 0; + for ( i = 0; i < Limit; i++ ) + { + pObjCo = Abc_NtkCo( pNtk, pSorted[i] ); + if ( MaxNameSize < (int)strlen( Abc_ObjName(pObjCo) ) ) + MaxNameSize = strlen( Abc_ObjName(pObjCo) ); + } + + // print the latest outputs + for ( i = 0; i < Limit; i++ ) + { + // get the i-th latest output + pObjCo = Abc_NtkCo( pNtk, pSorted[i] ); + pNode = Pga_Node( p, pObjCo->Id ); + // print out the best arrival time + printf( "Output %-*s : ", MaxNameSize + 3, Abc_ObjName(pObjCo) ); + printf( "Delay = %8.2f ", (double)pNode->Match.Delay ); + if ( Abc_ObjFaninC0(pObjCo) ) + printf( "NEG" ); + else + printf( "POS" ); + printf( "\n" ); + } +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/misc/extra/extra.h b/src/misc/extra/extra.h index f36b113f..904d550f 100644 --- a/src/misc/extra/extra.h +++ b/src/misc/extra/extra.h @@ -63,6 +63,15 @@ /* Macro declarations */ /*---------------------------------------------------------------------------*/ +typedef unsigned char uint8; +typedef unsigned short uint16; +typedef unsigned int uint32; +#ifdef WIN32 +typedef unsigned __int64 uint64; +#else +typedef unsigned long long uint64; +#endif + /* constants of the manager */ #define b0 Cudd_Not((dd)->one) #define b1 (dd)->one diff --git a/src/misc/vec/vecPtr.h b/src/misc/vec/vecPtr.h index b1776441..f29d5f35 100644 --- a/src/misc/vec/vecPtr.h +++ b/src/misc/vec/vecPtr.h @@ -53,6 +53,10 @@ struct Vec_Ptr_t_ for ( i = 0; (i < Vec_PtrSize(vVec)) && (((pEntry) = Vec_PtrEntry(vVec, i)), 1); i++ ) #define Vec_PtrForEachEntryStart( vVec, pEntry, i, Start ) \ for ( i = Start; (i < Vec_PtrSize(vVec)) && (((pEntry) = Vec_PtrEntry(vVec, i)), 1); i++ ) +#define Vec_PtrForEachEntryStop( vVec, pEntry, i, Stop ) \ + for ( i = 0; (i < Stop) && (((pEntry) = Vec_PtrEntry(vVec, i)), 1); i++ ) +#define Vec_PtrForEachEntryStartStop( vVec, pEntry, i, Start, Stop ) \ + for ( i = Start; (i < Stop) && (((pEntry) = Vec_PtrEntry(vVec, i)), 1); i++ ) #define Vec_PtrForEachEntryReverse( vVec, pEntry, i ) \ for ( i = Vec_PtrSize(vVec) - 1; (i >= 0) && (((pEntry) = Vec_PtrEntry(vVec, i)), 1); i-- ) diff --git a/src/opt/cut/cut.h b/src/opt/cut/cut.h index 6719ed4d..49dde875 100644 --- a/src/opt/cut/cut.h +++ b/src/opt/cut/cut.h @@ -43,7 +43,6 @@ struct Cut_ParamsStruct_t_ int nKeepMax; // the max number of cuts kept at a node int nIdsMax; // the max number of IDs of cut objects int fTruth; // compute truth tables - int fHash; // hash cuts to detect unique int fFilter; // filter dominated cuts int fSeq; // compute sequential cuts int fDrop; // drop cuts on the fly @@ -53,28 +52,25 @@ struct Cut_ParamsStruct_t_ struct Cut_CutStruct_t_ { unsigned uTruth : 16; // truth table for 4-input cuts - unsigned uPhase : 7; // the phase when mapping into a canonical form + unsigned uPhase : 8; // the phase when mapping into a canonical form unsigned fSimul : 1; // the value of cut's output at 000.. pattern unsigned fCompl : 1; // the cut is complemented - unsigned fSeq : 1; // the cut is sequential unsigned nVarsMax : 3; // the max number of vars [4-6] unsigned nLeaves : 3; // the number of leaves [4-6] + unsigned uSign; // the signature Cut_Cut_t * pNext; // the next cut in the list - void * pData; // the user data int pLeaves[0]; // the array of leaves }; -static inline unsigned * Cut_CutReadTruth( Cut_Cut_t * p ) { if ( p->nVarsMax == 4 ) return (unsigned *)p; return (unsigned *)(p->pLeaves + p->nVarsMax + p->fSeq); } +static inline unsigned * Cut_CutReadTruth( Cut_Cut_t * p ) { if ( p->nVarsMax == 4 ) return (unsigned *)p; return (unsigned *)(p->pLeaves + p->nVarsMax); } static inline unsigned Cut_CutReadPhase( Cut_Cut_t * p ) { return p->uPhase; } static inline int Cut_CutReadLeaveNum( Cut_Cut_t * p ) { return p->nLeaves; } static inline int * Cut_CutReadLeaves( Cut_Cut_t * p ) { return p->pLeaves; } -static inline void * Cut_CutReadData( Cut_Cut_t * p ) { return p->pData; } -static inline void Cut_CutWriteData( Cut_Cut_t * p, void * pData ) { p->pData = pData; } static inline void Cut_CutWriteTruth( Cut_Cut_t * p, unsigned * puTruth ) { if ( p->nVarsMax == 4 ) { p->uTruth = *puTruth; return; } - p->pLeaves[p->nVarsMax + p->fSeq] = (int)puTruth[0]; - if ( p->nVarsMax == 6 ) p->pLeaves[p->nVarsMax + p->fSeq + 1] = (int)puTruth[1]; + p->pLeaves[p->nVarsMax] = (int)puTruth[0]; + if ( p->nVarsMax == 6 ) p->pLeaves[p->nVarsMax + 1] = (int)puTruth[1]; } //////////////////////////////////////////////////////////////////////// @@ -85,21 +81,23 @@ static inline void Cut_CutWriteTruth( Cut_Cut_t * p, unsigned * puTruth ) /// FUNCTION DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +/*=== cutApi.c ==========================================================*/ +extern Cut_Cut_t * Cut_NodeReadCuts( Cut_Man_t * p, int Node ); +extern void Cut_NodeWriteCuts( Cut_Man_t * p, int Node, Cut_Cut_t * pList ); +extern void Cut_NodeSetTriv( Cut_Man_t * p, int Node ); +extern void Cut_NodeTryDroppingCuts( Cut_Man_t * p, int Node ); +extern void Cut_NodeFreeCuts( Cut_Man_t * p, int Node ); +/*=== cutCut.c ==========================================================*/ +extern void Cut_CutPrint( Cut_Cut_t * pCut ); /*=== cutMan.c ==========================================================*/ extern Cut_Man_t * Cut_ManStart( Cut_Params_t * pParams ); extern void Cut_ManStop( Cut_Man_t * p ); extern void Cut_ManPrintStats( Cut_Man_t * p ); extern void Cut_ManSetFanoutCounts( Cut_Man_t * p, Vec_Int_t * vFanCounts ); +extern int Cut_ManReadVarsMax( Cut_Man_t * p ); /*=== cutNode.c ==========================================================*/ -extern void Cut_NodeSetTriv( Cut_Man_t * p, int Node ); extern Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1 ); extern Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ); -extern Cut_Cut_t * Cut_NodeReadCuts( Cut_Man_t * p, int Node ); -extern void Cut_NodeWriteCuts( Cut_Man_t * p, int Node, Cut_Cut_t * pList ); -extern void Cut_NodeFreeCuts( Cut_Man_t * p, int Node ); -extern void Cut_NodeSetComputedAsNew( Cut_Man_t * p, int Node ); -extern void Cut_NodeTryDroppingCuts( Cut_Man_t * p, int Node ); -extern void Cut_CutPrint( Cut_Cut_t * pCut ); //////////////////////////////////////////////////////////////////////// /// END OF FILE /// diff --git a/src/opt/cut/cutApi.c b/src/opt/cut/cutApi.c new file mode 100644 index 00000000..0e7c2506 --- /dev/null +++ b/src/opt/cut/cutApi.c @@ -0,0 +1,131 @@ +/**CFile**************************************************************** + + FileName [cutNode.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [K-feasible cut computation package.] + + Synopsis [Procedures to compute cuts for a node.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: cutNode.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "cutInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Returns the pointer to the linked list of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Cut_t * Cut_NodeReadCuts( Cut_Man_t * p, int Node ) +{ + if ( Node >= p->vCuts->nSize ) + return NULL; + return Vec_PtrEntry( p->vCuts, Node ); +} + +/**Function************************************************************* + + Synopsis [Returns the pointer to the linked list of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeWriteCuts( Cut_Man_t * p, int Node, Cut_Cut_t * pList ) +{ + Vec_PtrWriteEntry( p->vCuts, Node, pList ); +} + +/**Function************************************************************* + + Synopsis [Sets the trivial cut for the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeSetTriv( Cut_Man_t * p, int Node ) +{ + assert( Cut_NodeReadCuts(p, Node) == NULL ); + Cut_NodeWriteCuts( p, Node, Cut_CutCreateTriv(p, Node) ); +} + +/**Function************************************************************* + + Synopsis [Consider dropping cuts if they are useless by now.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeTryDroppingCuts( Cut_Man_t * p, int Node ) +{ + int nFanouts; + assert( p->vFanCounts ); + nFanouts = Vec_IntEntry( p->vFanCounts, Node ); + assert( nFanouts > 0 ); + if ( --nFanouts == 0 ) + Cut_NodeFreeCuts( p, Node ); + Vec_IntWriteEntry( p->vFanCounts, Node, nFanouts ); +} + +/**Function************************************************************* + + Synopsis [Deallocates the cuts at the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeFreeCuts( Cut_Man_t * p, int Node ) +{ + Cut_Cut_t * pList, * pCut, * pCut2; + pList = Cut_NodeReadCuts( p, Node ); + if ( pList == NULL ) + return; + Cut_ListForEachCutSafe( pList, pCut, pCut2 ) + Cut_CutRecycle( p, pCut ); + Cut_NodeWriteCuts( p, Node, NULL ); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/cut/cutCut.c b/src/opt/cut/cutCut.c new file mode 100644 index 00000000..d2cce61f --- /dev/null +++ b/src/opt/cut/cutCut.c @@ -0,0 +1,171 @@ +/**CFile**************************************************************** + + FileName [cutNode.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [K-feasible cut computation package.] + + Synopsis [Procedures to compute cuts for a node.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: cutNode.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "cutInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Start the cut computation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Cut_t * Cut_CutAlloc( Cut_Man_t * p ) +{ + Cut_Cut_t * pCut; + // cut allocation + pCut = (Cut_Cut_t *)Extra_MmFixedEntryFetch( p->pMmCuts ); + memset( pCut, 0, sizeof(Cut_Cut_t) ); + pCut->nVarsMax = p->pParams->nVarsMax; + pCut->fSimul = p->fSimul; + // statistics + p->nCutsAlloc++; + p->nCutsCur++; + if ( p->nCutsPeak < p->nCutsAlloc - p->nCutsDealloc ) + p->nCutsPeak = p->nCutsAlloc - p->nCutsDealloc; + return pCut; +} + +/**Function************************************************************* + + Synopsis [Start the cut computation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Cut_t * Cut_CutCreateTriv( Cut_Man_t * p, int Node ) +{ + Cut_Cut_t * pCut; + pCut = Cut_CutAlloc( p ); + pCut->nLeaves = 1; + pCut->pLeaves[0] = Node; + pCut->uSign = (1 << (Node % 32)); + if ( p->pParams->fTruth ) + Cut_CutWriteTruth( pCut, p->uTruthVars[0] ); + p->nCutsTriv++; + return pCut; +} + +/**Function************************************************************* + + Synopsis [Start the cut computation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CutRecycle( Cut_Man_t * p, Cut_Cut_t * pCut ) +{ + p->nCutsDealloc++; + p->nCutsCur--; + if ( pCut->nLeaves == 1 ) + p->nCutsTriv--; + Extra_MmFixedEntryRecycle( p->pMmCuts, (char *)pCut ); +} + + +/**Function************************************************************* + + Synopsis [Print the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CutPrint( Cut_Cut_t * pCut ) +{ + int i; + assert( pCut->nLeaves > 0 ); + printf( "%d : {", pCut->nLeaves ); + for ( i = 0; i < (int)pCut->nLeaves; i++ ) + printf( " %d", pCut->pLeaves[i] ); + printf( " }" ); +} + +/**Function************************************************************* + + Synopsis [Consider dropping cuts if they are useless by now.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CutPrintMerge( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) +{ + printf( "\n" ); + printf( "%d : %5d %5d %5d %5d %5d\n", + pCut0->nLeaves, + pCut0->nLeaves > 0 ? pCut0->pLeaves[0] : -1, + pCut0->nLeaves > 1 ? pCut0->pLeaves[1] : -1, + pCut0->nLeaves > 2 ? pCut0->pLeaves[2] : -1, + pCut0->nLeaves > 3 ? pCut0->pLeaves[3] : -1, + pCut0->nLeaves > 4 ? pCut0->pLeaves[4] : -1 + ); + printf( "%d : %5d %5d %5d %5d %5d\n", + pCut1->nLeaves, + pCut1->nLeaves > 0 ? pCut1->pLeaves[0] : -1, + pCut1->nLeaves > 1 ? pCut1->pLeaves[1] : -1, + pCut1->nLeaves > 2 ? pCut1->pLeaves[2] : -1, + pCut1->nLeaves > 3 ? pCut1->pLeaves[3] : -1, + pCut1->nLeaves > 4 ? pCut1->pLeaves[4] : -1 + ); + if ( pCut == NULL ) + printf( "Cannot merge\n" ); + else + printf( "%d : %5d %5d %5d %5d %5d\n", + pCut->nLeaves, + pCut->nLeaves > 0 ? pCut->pLeaves[0] : -1, + pCut->nLeaves > 1 ? pCut->pLeaves[1] : -1, + pCut->nLeaves > 2 ? pCut->pLeaves[2] : -1, + pCut->nLeaves > 3 ? pCut->pLeaves[3] : -1, + pCut->nLeaves > 4 ? pCut->pLeaves[4] : -1 + ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/cut/cutInt.h b/src/opt/cut/cutInt.h index fe5080b4..2d4443f1 100644 --- a/src/opt/cut/cutInt.h +++ b/src/opt/cut/cutInt.h @@ -48,7 +48,6 @@ struct Cut_ManStruct_t_ // storage for cuts Vec_Ptr_t * vCuts; // cuts by ID Vec_Ptr_t * vCutsNew; // cuts by ID - Cut_HashTable_t * tTable; // cuts by their leaves (and root) // memory management Extra_MmFixed_t * pMmCuts; int EntrySize; @@ -58,6 +57,7 @@ struct Cut_ManStruct_t_ int fCompl0; int fCompl1; int fSimul; + int nNodeCuts; // precomputations unsigned uTruthVars[6][2]; unsigned short ** pPerms43; @@ -69,7 +69,8 @@ struct Cut_ManStruct_t_ int nCutsDealloc; int nCutsPeak; int nCutsTriv; - int nCutsNode; + int nCutsFilter; + int nCutsLimit; int nNodes; // runtime int timeMerge; @@ -79,6 +80,22 @@ struct Cut_ManStruct_t_ int timeHash; }; +// iterator through all the cuts of the list +#define Cut_ListForEachCut( pList, pCut ) \ + for ( pCut = pList; \ + pCut; \ + pCut = pCut->pNext ) +#define Cut_ListForEachCutStop( pList, pCut, pStop ) \ + for ( pCut = pList; \ + pCut != pStop; \ + pCut = pCut->pNext ) +#define Cut_ListForEachCutSafe( pList, pCut, pCut2 ) \ + for ( pCut = pList, \ + pCut2 = pCut? pCut->pNext: NULL; \ + pCut; \ + pCut = pCut2, \ + pCut2 = pCut? pCut->pNext: NULL ) + //////////////////////////////////////////////////////////////////////// /// MACRO DEFITIONS /// //////////////////////////////////////////////////////////////////////// @@ -87,10 +104,14 @@ struct Cut_ManStruct_t_ /// FUNCTION DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +/*=== cutCut.c ==========================================================*/ +extern Cut_Cut_t * Cut_CutAlloc( Cut_Man_t * p ); +extern Cut_Cut_t * Cut_CutCreateTriv( Cut_Man_t * p, int Node ); +extern void Cut_CutRecycle( Cut_Man_t * p, Cut_Cut_t * pCut ); +extern void Cut_CutPrint( Cut_Cut_t * pCut ); +extern void Cut_CutPrintMerge( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); /*=== cutMerge.c ==========================================================*/ extern Cut_Cut_t * Cut_CutMergeTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); -/*=== cutNode.c ==========================================================*/ -extern Cut_Cut_t * Cut_CutAlloc( Cut_Man_t * p ); /*=== cutTable.c ==========================================================*/ extern Cut_HashTable_t * Cut_TableStart( int Size ); extern void Cut_TableStop( Cut_HashTable_t * pTable ); diff --git a/src/opt/cut/cutMan.c b/src/opt/cut/cutMan.c index 4ad3a66a..31e003cf 100644 --- a/src/opt/cut/cutMan.c +++ b/src/opt/cut/cutMan.c @@ -49,7 +49,7 @@ Cut_Man_t * Cut_ManStart( Cut_Params_t * pParams ) // set and correct parameters p->pParams = pParams; if ( p->pParams->fSeq ) - p->pParams->fHash = 1; + p->pParams->fFilter = 1; // space for cuts p->vCuts = Vec_PtrAlloc( pParams->nIdsMax ); Vec_PtrFill( p->vCuts, pParams->nIdsMax, NULL ); @@ -58,25 +58,17 @@ Cut_Man_t * Cut_ManStart( Cut_Params_t * pParams ) p->vCutsNew = Vec_PtrAlloc( pParams->nIdsMax ); Vec_PtrFill( p->vCuts, pParams->nIdsMax, NULL ); } - // hash tables - if ( pParams->fHash ) - p->tTable = Cut_TableStart( p->pParams->nKeepMax ); // entry size p->EntrySize = sizeof(Cut_Cut_t) + (pParams->nVarsMax + pParams->fSeq) * sizeof(int); - if ( pParams->nVarsMax == 5 ) - p->EntrySize += sizeof(unsigned); - else if ( pParams->nVarsMax == 6 ) - p->EntrySize += 2 * sizeof(unsigned); + if ( pParams->fTruth ) + { + if ( pParams->nVarsMax == 5 ) + p->EntrySize += sizeof(unsigned); + else if ( pParams->nVarsMax == 6 ) + p->EntrySize += 2 * sizeof(unsigned); + } // memory for cuts p->pMmCuts = Extra_MmFixedStart( p->EntrySize ); - // precomputations -// if ( pParams->fTruth && pParams->nVarsMax == 4 ) -// p->pPerms43 = Extra_TruthPerm43(); -// else if ( pParams->fTruth ) -// { -// p->pPerms53 = Extra_TruthPerm53(); -// p->pPerms54 = Extra_TruthPerm54(); -// } p->uTruthVars[0][1] = p->uTruthVars[0][0] = 0xAAAAAAAA; // 1010 1010 1010 1010 1010 1010 1010 1010 p->uTruthVars[1][1] = p->uTruthVars[1][0] = 0xCCCCCCCC; // 1010 1010 1010 1010 1010 1010 1010 1010 p->uTruthVars[2][1] = p->uTruthVars[2][0] = 0xF0F0F0F0; // 1111 0000 1111 0000 1111 0000 1111 0000 @@ -104,13 +96,10 @@ void Cut_ManStop( Cut_Man_t * p ) Cut_Cut_t * pCut; int i; Vec_PtrForEachEntry( p->vCuts, pCut, i ) - { if ( pCut != NULL ) { int k = 0; } - } - if ( p->vCutsNew ) Vec_PtrFree( p->vCutsNew ); if ( p->vCuts ) Vec_PtrFree( p->vCuts ); if ( p->vFanCounts ) Vec_IntFree( p->vFanCounts ); @@ -118,7 +107,6 @@ void Cut_ManStop( Cut_Man_t * p ) if ( p->pPerms53 ) free( p->pPerms53 ); if ( p->pPerms54 ) free( p->pPerms54 ); if ( p->vTemp ) Vec_PtrFree( p->vTemp ); - if ( p->tTable ) Cut_TableStop( p->tTable ); Extra_MmFixedStop( p->pMmCuts, 0 ); free( p ); } @@ -141,12 +129,13 @@ void Cut_ManPrintStats( Cut_Man_t * p ) printf( "Peak cuts = %8d.\n", p->nCutsPeak ); printf( "Total allocated = %8d.\n", p->nCutsAlloc ); printf( "Total deallocated = %8d.\n", p->nCutsDealloc ); + printf( "Cuts filtered = %8d.\n", p->nCutsFilter ); + printf( "Nodes with limit = %8d.\n", p->nCutsLimit ); printf( "Cuts per node = %8.1f\n", ((float)(p->nCutsCur-p->nCutsTriv))/p->nNodes ); printf( "The cut size = %8d bytes.\n", p->EntrySize ); printf( "Peak memory = %8.2f Mb.\n", (float)p->nCutsPeak * p->EntrySize / (1<<20) ); PRT( "Merge ", p->timeMerge ); PRT( "Union ", p->timeUnion ); - PRT( "Hash ", Cut_TableReadTime(p->tTable) ); PRT( "Filter", p->timeFilter ); PRT( "Truth ", p->timeTruth ); } @@ -168,6 +157,22 @@ void Cut_ManSetFanoutCounts( Cut_Man_t * p, Vec_Int_t * vFanCounts ) p->vFanCounts = vFanCounts; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Cut_ManReadVarsMax( Cut_Man_t * p ) +{ + return p->pParams->nVarsMax; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/opt/cut/cutNode.c b/src/opt/cut/cutNode.c index 8d16ac8a..e8a0bc87 100644 --- a/src/opt/cut/cutNode.c +++ b/src/opt/cut/cutNode.c @@ -25,36 +25,13 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static inline Cut_Cut_t * Cut_CutCreateTriv( Cut_Man_t * p, int Node ); -static inline void Cut_CutRecycle( Cut_Man_t * p, Cut_Cut_t * pCut ); -static inline int Cut_CutProcessTwo( Cut_Man_t * p, int Root, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, Cut_List_t * pSuperList ); - -static void Cut_CutPrintMerge( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); -static void Cut_CutFilter( Cut_Man_t * p, Cut_Cut_t * pList ); - -// iterator through all the cuts of the list -#define Cut_ListForEachCut( pList, pCut ) \ - for ( pCut = pList; \ - pCut; \ - pCut = pCut->pNext ) -#define Cut_ListForEachCutStop( pList, pCut, pStop ) \ - for ( pCut = pList; \ - pCut != pStop; \ - pCut = pCut->pNext ) -#define Cut_ListForEachCutSafe( pList, pCut, pCut2 ) \ - for ( pCut = pList, \ - pCut2 = pCut? pCut->pNext: NULL; \ - pCut; \ - pCut = pCut2, \ - pCut2 = pCut? pCut->pNext: NULL ) - //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* - Synopsis [Returns the pointer to the linked list of cuts.] + Synopsis [Returns 1 if pDom is contained in pCut.] Description [] @@ -63,49 +40,96 @@ static void Cut_CutFilter( Cut_Man_t * p, Cut_Cut_t * pList ); SeeAlso [] ***********************************************************************/ -Cut_Cut_t * Cut_NodeReadCuts( Cut_Man_t * p, int Node ) +static inline int Cut_CutCheckDominance( Cut_Cut_t * pDom, Cut_Cut_t * pCut ) { - if ( Node >= p->vCuts->nSize ) - return NULL; - return Vec_PtrEntry( p->vCuts, Node ); + int i, k; + for ( i = 0; i < (int)pDom->nLeaves; i++ ) + { + for ( k = 0; k < (int)pCut->nLeaves; k++ ) + if ( pDom->pLeaves[i] == pCut->pLeaves[k] ) + break; + if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut + return 0; + } + // every node in pDom is contained in pCut + return 1; } /**Function************************************************************* - Synopsis [Returns the pointer to the linked list of cuts.] + Synopsis [Checks containment for one cut.] - Description [] + Description [Returns 1 if the cut is removed.] - SideEffects [] + SideEffects [May remove other cuts in the set.] SeeAlso [] ***********************************************************************/ -void Cut_NodeWriteCuts( Cut_Man_t * p, int Node, Cut_Cut_t * pList ) +static inline int Cut_CutFilterOne( Cut_Man_t * p, Cut_List_t * pSuperList, Cut_Cut_t * pCut ) { - Vec_PtrWriteEntry( p->vCuts, Node, pList ); -} + Cut_Cut_t * pTemp, * pTemp2, ** ppTail; + int a; -/**Function************************************************************* - - Synopsis [Sets the trivial cut for the node.] - - Description [] - - SideEffects [] + // check if this cut is filtered out by smaller cuts + for ( a = 2; a <= (int)pCut->nLeaves; a++ ) + { + Cut_ListForEachCut( pSuperList->pHead[a], pTemp ) + { + // skip the non-contained cuts + if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign ) + continue; + // check containment seriously + if ( Cut_CutCheckDominance( pTemp, pCut ) ) + { + p->nCutsFilter++; + Cut_CutRecycle( p, pCut ); + return 1; + } + } + } - SeeAlso [] + // filter out other cuts using this one + for ( a = pCut->nLeaves + 1; a <= (int)pCut->nVarsMax; a++ ) + { + ppTail = pSuperList->pHead + a; + Cut_ListForEachCutSafe( pSuperList->pHead[a], pTemp, pTemp2 ) + { + // skip the non-contained cuts + if ( (pTemp->uSign & pCut->uSign) != pCut->uSign ) + { + ppTail = &pTemp->pNext; + continue; + } + // check containment seriously + if ( Cut_CutCheckDominance( pCut, pTemp ) ) + { + p->nCutsFilter++; + p->nNodeCuts--; + // move the head + if ( pSuperList->pHead[a] == pTemp ) + pSuperList->pHead[a] = pTemp->pNext; + // move the tail + if ( pSuperList->ppTail[a] == &pTemp->pNext ) + pSuperList->ppTail[a] = ppTail; + // skip the given cut in the list + *ppTail = pTemp->pNext; + // recycle pTemp + Cut_CutRecycle( p, pTemp ); + } + else + ppTail = &pTemp->pNext; + } + assert( ppTail == pSuperList->ppTail[a] ); + assert( *ppTail == NULL ); + } -***********************************************************************/ -void Cut_NodeSetTriv( Cut_Man_t * p, int Node ) -{ - assert( Cut_NodeReadCuts(p, Node) == NULL ); - Cut_NodeWriteCuts( p, Node, Cut_CutCreateTriv(p, Node) ); + return 0; } /**Function************************************************************* - Synopsis [Deallocates the cuts at the node.] + Synopsis [Filters cuts using dominance.] Description [] @@ -114,31 +138,79 @@ void Cut_NodeSetTriv( Cut_Man_t * p, int Node ) SeeAlso [] ***********************************************************************/ -void Cut_NodeFreeCuts( Cut_Man_t * p, int Node ) -{ - Cut_Cut_t * pList, * pCut, * pCut2; - pList = Cut_NodeReadCuts( p, Node ); - if ( pList == NULL ) - return; - Cut_ListForEachCutSafe( pList, pCut, pCut2 ) - Cut_CutRecycle( p, pCut ); - Cut_NodeWriteCuts( p, Node, NULL ); +static inline void Cut_CutFilter( Cut_Man_t * p, Cut_Cut_t * pList ) +{ + Cut_Cut_t * pListR, ** ppListR = &pListR; + Cut_Cut_t * pCut, * pCut2, * pDom, * pPrev; + // save the first cut + *ppListR = pList, ppListR = &pList->pNext; + // try to filter out other cuts + pPrev = pList; + Cut_ListForEachCutSafe( pList->pNext, pCut, pCut2 ) + { + assert( pCut->nLeaves > 1 ); + // go through all the previous cuts up to pCut + Cut_ListForEachCutStop( pList->pNext, pDom, pCut ) + { + if ( pDom->nLeaves > pCut->nLeaves ) + continue; + if ( (pDom->uSign & pCut->uSign) != pDom->uSign ) + continue; + if ( Cut_CutCheckDominance( pDom, pCut ) ) + break; + } + if ( pDom != pCut ) // pDom is contained in pCut - recycle pCut + { + // make sure cuts are connected after removing + pPrev->pNext = pCut->pNext; + // recycle the cut + Cut_CutRecycle( p, pCut ); + } + else // pDom is NOT contained in pCut - save pCut + { + *ppListR = pCut, ppListR = &pCut->pNext; + pPrev = pCut; + } + } + *ppListR = NULL; } - /**Function************************************************************* - Synopsis [] + Synopsis [Processes two cuts.] - Description [] + Description [Returns 1 if the limit has been reached.] SideEffects [] SeeAlso [] ***********************************************************************/ -void Cut_NodeSetComputedAsNew( Cut_Man_t * p, int Node ) +static inline int Cut_CutProcessTwo( Cut_Man_t * p, int Root, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, Cut_List_t * pSuperList ) { + Cut_Cut_t * pCut; + int RetValue; + // merge the cuts + if ( pCut0->nLeaves >= pCut1->nLeaves ) + pCut = Cut_CutMergeTwo( p, pCut0, pCut1 ); + else + pCut = Cut_CutMergeTwo( p, pCut1, pCut0 ); + if ( pCut == NULL ) + return 0; + assert( pCut->nLeaves > 1 ); + // set the signature + pCut->uSign = pCut0->uSign | pCut1->uSign; + // check containment + RetValue = p->pParams->fFilter && Cut_CutFilterOne( p, pSuperList, pCut ); + if ( RetValue ) + return 0; + // compute the truth table + if ( p->pParams->fTruth ) + Cut_TruthCompute( p, pCut, pCut0, pCut1 ); + // add to the list + Cut_ListAdd( pSuperList, pCut ); + // return status (0 if okay; 1 if exceeded the limit) + return ++p->nNodeCuts == p->pParams->nKeepMax; } /**Function************************************************************* @@ -159,6 +231,7 @@ Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, int i, Limit = p->pParams->nVarsMax; int clk = clock(); assert( p->pParams->nVarsMax <= 6 ); + // start the new list Cut_ListStart( &SuperList ); // get the cut lists of children @@ -180,27 +253,37 @@ Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, // start with the elementary cut pTemp0 = Cut_CutCreateTriv( p, Node ); Cut_ListAdd( &SuperList, pTemp0 ); - p->nCutsNode = 1; + p->nNodeCuts = 1; // small by small Cut_ListForEachCutStop( pList0, pTemp0, pStop0 ) Cut_ListForEachCutStop( pList1, pTemp1, pStop1 ) if ( Cut_CutProcessTwo( p, Node, pTemp0, pTemp1, &SuperList ) ) goto finish; - // all by large - Cut_ListForEachCut( pList0, pTemp0 ) + // small by large + Cut_ListForEachCutStop( pList0, pTemp0, pStop0 ) Cut_ListForEachCut( pStop1, pTemp1 ) + { + if ( (pTemp0->uSign & pTemp1->uSign) != pTemp0->uSign ) + continue; if ( Cut_CutProcessTwo( p, Node, pTemp0, pTemp1, &SuperList ) ) goto finish; - // all by large - Cut_ListForEachCut( pList1, pTemp1 ) + } + // small by large + Cut_ListForEachCutStop( pList1, pTemp1, pStop1 ) Cut_ListForEachCut( pStop0, pTemp0 ) + { + if ( (pTemp0->uSign & pTemp1->uSign) != pTemp1->uSign ) + continue; if ( Cut_CutProcessTwo( p, Node, pTemp0, pTemp1, &SuperList ) ) goto finish; + } // large by large Cut_ListForEachCut( pStop0, pTemp0 ) Cut_ListForEachCut( pStop1, pTemp1 ) { assert( pTemp0->nLeaves == (unsigned)Limit && pTemp1->nLeaves == (unsigned)Limit ); + if ( pTemp0->uSign != pTemp1->uSign ) + continue; for ( i = 0; i < Limit; i++ ) if ( pTemp0->pLeaves[i] != pTemp1->pLeaves[i] ) break; @@ -210,14 +293,13 @@ Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, goto finish; } finish : + if ( p->nNodeCuts == p->pParams->nKeepMax ) + p->nCutsLimit++; // set the list at the node Vec_PtrFillExtra( p->vCuts, Node + 1, NULL ); assert( Cut_NodeReadCuts(p, Node) == NULL ); pList0 = Cut_ListFinish( &SuperList ); Cut_NodeWriteCuts( p, Node, pList0 ); - // clear the hash table - if ( p->pParams->fHash && !p->pParams->fSeq ) - Cut_TableClear( p->tTable ); // consider dropping the fanins cuts if ( p->pParams->fDrop ) { @@ -227,8 +309,8 @@ finish : p->timeMerge += clock() - clk; // filter the cuts clk = clock(); - if ( p->pParams->fFilter ) - Cut_CutFilter( p, pList0 ); +// if ( p->pParams->fFilter ) +// Cut_CutFilter( p, pList0 ); p->timeFilter += clock() - clk; p->nNodes++; return pList0; @@ -236,46 +318,6 @@ p->timeFilter += clock() - clk; /**Function************************************************************* - Synopsis [Processes two cuts.] - - Description [Returns 1 if the limit has been reached.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Cut_CutProcessTwo( Cut_Man_t * p, int Root, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, Cut_List_t * pSuperList ) -{ - Cut_Cut_t * pCut; - // merge the cuts - if ( pCut0->nLeaves >= pCut1->nLeaves ) - pCut = Cut_CutMergeTwo( p, pCut0, pCut1 ); - else - pCut = Cut_CutMergeTwo( p, pCut1, pCut0 ); - if ( pCut == NULL ) - return 0; - assert( pCut->nLeaves > 1 ); - // add the root if sequential - if ( p->pParams->fSeq ) - pCut->pLeaves[pCut->nLeaves] = Root; - // check the lookup table - if ( p->pParams->fHash && Cut_TableLookup( p->tTable, pCut, !p->pParams->fSeq ) ) - { - Cut_CutRecycle( p, pCut ); - return 0; - } - // compute the truth table - if ( p->pParams->fTruth ) - Cut_TruthCompute( p, pCut, pCut0, pCut1 ); - // add to the list - Cut_ListAdd( pSuperList, pCut ); - // return status (0 if okay; 1 if exceeded the limit) - return ++p->nCutsNode == p->pParams->nKeepMax; -} - -/**Function************************************************************* - Synopsis [Computes the cuts by unioning cuts at a choice node.] Description [] @@ -299,7 +341,7 @@ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) // remember the root node to save the resulting cuts Root = Vec_IntEntry( vNodes, 0 ); - p->nCutsNode = 1; + p->nNodeCuts = 1; // collect small cuts first Vec_PtrClear( p->vTemp ); @@ -311,6 +353,7 @@ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) assert( pList ); // remember the starting point pListStart = pList->pNext; + pList->pNext = NULL; // save or recycle the elementary cut if ( i == 0 ) Cut_ListAdd( &SuperList, pList ), pTop = pList; @@ -324,20 +367,19 @@ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) Vec_PtrPush( p->vTemp, pCut ); break; } - // check hash tables - if ( p->pParams->fHash && Cut_TableLookup( p->tTable, pCut, !p->pParams->fSeq ) ) - { - Cut_CutRecycle( p, pCut ); + // check containment + if ( p->pParams->fFilter && Cut_CutFilterOne( p, &SuperList, pCut ) ) continue; - } // set the complemented bit by comparing the first cut with the current cut pCut->fCompl = pTop->fSimul ^ pCut->fSimul; + pListStart = pCut->pNext; + pCut->pNext = NULL; // add to the list Cut_ListAdd( &SuperList, pCut ); - if ( ++p->nCutsNode == p->pParams->nKeepMax ) + if ( ++p->nNodeCuts == p->pParams->nKeepMax ) { // recycle the rest of the cuts of this node - Cut_ListForEachCutSafe( pCut->pNext, pCut, pCut2 ) + Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); // recycle all cuts of other nodes Vec_IntForEachEntryStart( vNodes, Node, k, i+1 ) @@ -349,25 +391,25 @@ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) goto finish; } } - } + } // collect larger cuts next Vec_PtrForEachEntry( p->vTemp, pList, i ) { Cut_ListForEachCutSafe( pList, pCut, pCut2 ) { - if ( p->pParams->fHash && Cut_TableLookup( p->tTable, pCut, !p->pParams->fSeq ) ) - { - Cut_CutRecycle( p, pCut ); + // check containment + if ( p->pParams->fFilter && Cut_CutFilterOne( p, &SuperList, pCut ) ) continue; - } // set the complemented bit pCut->fCompl = pTop->fSimul ^ pCut->fSimul; + pListStart = pCut->pNext; + pCut->pNext = NULL; // add to the list Cut_ListAdd( &SuperList, pCut ); - if ( ++p->nCutsNode == p->pParams->nKeepMax ) + if ( ++p->nNodeCuts == p->pParams->nKeepMax ) { // recycle the rest of the cuts - Cut_ListForEachCutSafe( pCut->pNext, pCut, pCut2 ) + Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); // recycle the saved cuts of other nodes Vec_PtrForEachEntryStart( p->vTemp, pList, k, i+1 ) @@ -382,244 +424,16 @@ finish : assert( Cut_NodeReadCuts(p, Root) == NULL ); pList = Cut_ListFinish( &SuperList ); Cut_NodeWriteCuts( p, Root, pList ); - // clear the hash table - if ( p->pParams->fHash && !p->pParams->fSeq ) - Cut_TableClear( p->tTable ); p->timeUnion += clock() - clk; // filter the cuts clk = clock(); - if ( p->pParams->fFilter ) - Cut_CutFilter( p, pList ); +// if ( p->pParams->fFilter ) +// Cut_CutFilter( p, pList ); p->timeFilter += clock() - clk; p->nNodes -= vNodes->nSize - 1; return pList; } -/**Function************************************************************* - - Synopsis [Start the cut computation.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Cut_Cut_t * Cut_CutAlloc( Cut_Man_t * p ) -{ - Cut_Cut_t * pCut; - // cut allocation - pCut = (Cut_Cut_t *)Extra_MmFixedEntryFetch( p->pMmCuts ); - memset( pCut, 0, sizeof(Cut_Cut_t) ); - pCut->nVarsMax = p->pParams->nVarsMax; - pCut->fSeq = p->pParams->fSeq; - pCut->fSimul = p->fSimul; - // statistics - p->nCutsAlloc++; - p->nCutsCur++; - if ( p->nCutsPeak < p->nCutsAlloc - p->nCutsDealloc ) - p->nCutsPeak = p->nCutsAlloc - p->nCutsDealloc; - return pCut; -} - -/**Function************************************************************* - - Synopsis [Start the cut computation.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Cut_Cut_t * Cut_CutCreateTriv( Cut_Man_t * p, int Node ) -{ - Cut_Cut_t * pCut; - pCut = Cut_CutAlloc( p ); - pCut->nLeaves = 1; - pCut->pLeaves[0] = Node; - if ( p->pParams->fTruth ) - Cut_CutWriteTruth( pCut, p->uTruthVars[0] ); - p->nCutsTriv++; - return pCut; -} - -/**Function************************************************************* - - Synopsis [Start the cut computation.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_CutRecycle( Cut_Man_t * p, Cut_Cut_t * pCut ) -{ - p->nCutsDealloc++; - p->nCutsCur--; - if ( pCut->nLeaves == 1 ) - p->nCutsTriv--; - Extra_MmFixedEntryRecycle( p->pMmCuts, (char *)pCut ); -} - - -/**Function************************************************************* - - Synopsis [Consider dropping cuts if they are useless by now.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_NodeTryDroppingCuts( Cut_Man_t * p, int Node ) -{ - int nFanouts; - assert( p->vFanCounts ); - nFanouts = Vec_IntEntry( p->vFanCounts, Node ); - assert( nFanouts > 0 ); - if ( --nFanouts == 0 ) - Cut_NodeFreeCuts( p, Node ); - Vec_IntWriteEntry( p->vFanCounts, Node, nFanouts ); -} - -/**Function************************************************************* - - Synopsis [Print the cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_CutPrint( Cut_Cut_t * pCut ) -{ - int i; - assert( pCut->nLeaves > 0 ); - printf( "%d : {", pCut->nLeaves ); - for ( i = 0; i < (int)pCut->nLeaves; i++ ) - printf( " %d", pCut->pLeaves[i] ); - printf( " }" ); -} - -/**Function************************************************************* - - Synopsis [Consider dropping cuts if they are useless by now.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_CutPrintMerge( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) -{ - printf( "\n" ); - printf( "%d : %5d %5d %5d %5d %5d\n", - pCut0->nLeaves, - pCut0->nLeaves > 0 ? pCut0->pLeaves[0] : -1, - pCut0->nLeaves > 1 ? pCut0->pLeaves[1] : -1, - pCut0->nLeaves > 2 ? pCut0->pLeaves[2] : -1, - pCut0->nLeaves > 3 ? pCut0->pLeaves[3] : -1, - pCut0->nLeaves > 4 ? pCut0->pLeaves[4] : -1 - ); - printf( "%d : %5d %5d %5d %5d %5d\n", - pCut1->nLeaves, - pCut1->nLeaves > 0 ? pCut1->pLeaves[0] : -1, - pCut1->nLeaves > 1 ? pCut1->pLeaves[1] : -1, - pCut1->nLeaves > 2 ? pCut1->pLeaves[2] : -1, - pCut1->nLeaves > 3 ? pCut1->pLeaves[3] : -1, - pCut1->nLeaves > 4 ? pCut1->pLeaves[4] : -1 - ); - if ( pCut == NULL ) - printf( "Cannot merge\n" ); - else - printf( "%d : %5d %5d %5d %5d %5d\n", - pCut->nLeaves, - pCut->nLeaves > 0 ? pCut->pLeaves[0] : -1, - pCut->nLeaves > 1 ? pCut->pLeaves[1] : -1, - pCut->nLeaves > 2 ? pCut->pLeaves[2] : -1, - pCut->nLeaves > 3 ? pCut->pLeaves[3] : -1, - pCut->nLeaves > 4 ? pCut->pLeaves[4] : -1 - ); -} - - -/**Function************************************************************* - - Synopsis [Filter the cuts using dominance.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_CutFilter( Cut_Man_t * p, Cut_Cut_t * pList ) -{ - Cut_Cut_t * pListR, ** ppListR = &pListR; - Cut_Cut_t * pCut, * pCut2, * pDom, * pPrev; - int i, k; - // save the first cut - *ppListR = pList, ppListR = &pList->pNext; - // try to filter out other cuts - pPrev = pList; - Cut_ListForEachCutSafe( pList->pNext, pCut, pCut2 ) - { - assert( pCut->nLeaves > 1 ); - // go through all the previous cuts up to pCut - Cut_ListForEachCutStop( pList->pNext, pDom, pCut ) - { - if ( pDom->nLeaves >= pCut->nLeaves ) - continue; - // check if every node in pDom is contained in pCut - for ( i = 0; i < (int)pDom->nLeaves; i++ ) - { - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - if ( pDom->pLeaves[i] == pCut->pLeaves[k] ) - break; - if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut - break; - } - if ( i == (int)pDom->nLeaves ) // every node in pDom is contained in pCut - break; - } - if ( pDom != pCut ) // pDom is contained in pCut - recycle pCut - { - // make sure cuts are connected after removing - pPrev->pNext = pCut->pNext; -/* - // report - printf( "Recycling cut: " ); - Cut_CutPrint( pCut ); - printf( "\n" ); - printf( "As contained in: " ); - Cut_CutPrint( pDom ); - printf( "\n" ); -*/ - // recycle the cut - Cut_CutRecycle( p, pCut ); - } - else // pDom is NOT contained in pCut - save pCut - { - *ppListR = pCut, ppListR = &pCut->pNext; - pPrev = pCut; - } - } - *ppListR = NULL; -} - - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// diff --git a/src/opt/cut/cutTable.c b/src/opt/cut/cutTable.c deleted file mode 100644 index 5dfaca7b..00000000 --- a/src/opt/cut/cutTable.c +++ /dev/null @@ -1,253 +0,0 @@ -/**CFile**************************************************************** - - FileName [cutTable.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [K-feasible cut computation package.] - - Synopsis [Hashing cuts to prevent duplication.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: cutTable.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "cutInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -struct Cut_HashTableStruct_t_ -{ - int nBins; - Cut_Cut_t ** pBins; - int nEntries; - int * pPlaces; - int nPlaces; - int timeLookup; -}; - -// iterator through all the cuts of the list -#define Cut_TableListForEachCut( pList, pCut ) \ - for ( pCut = pList; \ - pCut; \ - pCut = pCut->pData ) -#define Cut_TableListForEachCutSafe( pList, pCut, pCut2 ) \ - for ( pCut = pList, \ - pCut2 = pCut? pCut->pData: NULL; \ - pCut; \ - pCut = pCut2, \ - pCut2 = pCut? pCut->pData: NULL ) - -// primes used to compute the hash key -static int s_HashPrimes[10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 }; - -// hashing function -static inline unsigned Cut_HashKey( Cut_Cut_t * pCut ) -{ - unsigned i, uRes = pCut->nLeaves * s_HashPrimes[9]; - for ( i = 0; i < pCut->nLeaves + pCut->fSeq; i++ ) - uRes += s_HashPrimes[i] * pCut->pLeaves[i]; - return uRes; -} - -// hashing function -static inline int Cut_CompareTwo( Cut_Cut_t * pCut1, Cut_Cut_t * pCut2 ) -{ - unsigned i; - if ( pCut1->nLeaves != pCut2->nLeaves ) - return 1; - for ( i = 0; i < pCut1->nLeaves; i++ ) - if ( pCut1->pLeaves[i] != pCut2->pLeaves[i] ) - return 1; - return 0; -} - -static void Cut_TableResize( Cut_HashTable_t * pTable ); - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Starts the hash table.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Cut_HashTable_t * Cut_TableStart( int Size ) -{ - Cut_HashTable_t * pTable; - pTable = ALLOC( Cut_HashTable_t, 1 ); - memset( pTable, 0, sizeof(Cut_HashTable_t) ); - // allocate the table - pTable->nBins = Cudd_PrimeCopy( Size ); - pTable->pBins = ALLOC( Cut_Cut_t *, pTable->nBins ); - memset( pTable->pBins, 0, sizeof(Cut_Cut_t *) * pTable->nBins ); - pTable->pPlaces = ALLOC( int, pTable->nBins ); - return pTable; -} - -/**Function************************************************************* - - Synopsis [Stops the hash table.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_TableStop( Cut_HashTable_t * pTable ) -{ - FREE( pTable->pPlaces ); - free( pTable->pBins ); - free( pTable ); -} - -/**Function************************************************************* - - Synopsis [Check the existence of a cut in the lookup table] - - Description [Returns 1 if the entry is found.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Cut_TableLookup( Cut_HashTable_t * pTable, Cut_Cut_t * pCut, int fStore ) -{ - Cut_Cut_t * pEnt; - unsigned Key; - int clk = clock(); - - Key = Cut_HashKey(pCut) % pTable->nBins; - Cut_TableListForEachCut( pTable->pBins[Key], pEnt ) - { - if ( !Cut_CompareTwo( pEnt, pCut ) ) - { -pTable->timeLookup += clock() - clk; - return 1; - } - } - if ( pTable->nEntries > 2 * pTable->nBins ) - { - Cut_TableResize( pTable ); - Key = Cut_HashKey(pCut) % pTable->nBins; - } - // remember the place - if ( fStore && pTable->pBins[Key] == NULL ) - pTable->pPlaces[ pTable->nPlaces++ ] = Key; - // add the cut to the table - pCut->pData = pTable->pBins[Key]; - pTable->pBins[Key] = pCut; - pTable->nEntries++; -pTable->timeLookup += clock() - clk; - return 0; -} - - -/**Function************************************************************* - - Synopsis [Stops the hash table.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_TableClear( Cut_HashTable_t * pTable ) -{ - int i; - assert( pTable->nPlaces <= pTable->nBins ); - for ( i = 0; i < pTable->nPlaces; i++ ) - { - assert( pTable->pBins[ pTable->pPlaces[i] ] ); - pTable->pBins[ pTable->pPlaces[i] ] = NULL; - } - pTable->nPlaces = 0; - pTable->nEntries = 0; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_TableResize( Cut_HashTable_t * pTable ) -{ - Cut_Cut_t ** pBinsNew; - Cut_Cut_t * pEnt, * pEnt2; - int nBinsNew, Counter, i, clk; - unsigned Key; - -clk = clock(); - // get the new table size - nBinsNew = Cudd_PrimeCopy( 3 * pTable->nBins ); - // allocate a new array - pBinsNew = ALLOC( Cut_Cut_t *, nBinsNew ); - memset( pBinsNew, 0, sizeof(Cut_Cut_t *) * nBinsNew ); - // rehash the entries from the old table - Counter = 0; - for ( i = 0; i < pTable->nBins; i++ ) - Cut_TableListForEachCutSafe( pTable->pBins[i], pEnt, pEnt2 ) - { - Key = Cut_HashKey(pEnt) % nBinsNew; - pEnt->pData = pBinsNew[Key]; - pBinsNew[Key] = pEnt; - Counter++; - } - assert( Counter == pTable->nEntries ); -// printf( "Increasing the structural table size from %6d to %6d. ", pMan->nBins, nBinsNew ); -// PRT( "Time", clock() - clk ); - // replace the table and the parameters - free( pTable->pBins ); - pTable->pBins = pBinsNew; - pTable->nBins = nBinsNew; -} - -/**Function************************************************************* - - Synopsis [Stops the hash table.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Cut_TableReadTime( Cut_HashTable_t * pTable ) -{ - if ( pTable == NULL ) - return 0; - return pTable->timeLookup; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/cut/cutTruth.c b/src/opt/cut/cutTruth.c index efacd456..cc115042 100644 --- a/src/opt/cut/cutTruth.c +++ b/src/opt/cut/cutTruth.c @@ -315,6 +315,7 @@ void Cut_TruthComputeOld( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cu p->timeTruth += clock() - clk; } + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/opt/cut/module.make b/src/opt/cut/module.make index 1175b3f2..2e7519d1 100644 --- a/src/opt/cut/module.make +++ b/src/opt/cut/module.make @@ -1,6 +1,7 @@ -SRC += src/opt/cut/cutMan.c \ +SRC += src/opt/cut/cutApi.c \ + src/opt/cut/cutCut.c \ + src/opt/cut/cutMan.c \ src/opt/cut/cutMerge.c \ src/opt/cut/cutNode.c \ src/opt/cut/cutSeq.c \ - src/opt/cut/cutTable.c \ src/opt/cut/cutTruth.c diff --git a/src/opt/dec/decFactor.c b/src/opt/dec/decFactor.c index f6654476..ed7e94c8 100644 --- a/src/opt/dec/decFactor.c +++ b/src/opt/dec/decFactor.c @@ -183,7 +183,7 @@ Dec_Edge_t Dec_Factor_rec( Dec_Graph_t * pFForm, Mvc_Cover_t * pCover ) ***********************************************************************/ Dec_Edge_t Dec_FactorLF_rec( Dec_Graph_t * pFForm, Mvc_Cover_t * pCover, Mvc_Cover_t * pSimple ) { - Dec_Man_t * pManDec = Abc_FrameReadManDec(Abc_FrameGetGlobalFrame()); + Dec_Man_t * pManDec = Abc_FrameReadManDec(); Vec_Int_t * vEdgeLits = pManDec->vLits; Mvc_Cover_t * pDiv, * pQuo, * pRem; Dec_Edge_t eNodeDiv, eNodeQuo, eNodeRem; @@ -228,7 +228,7 @@ Dec_Edge_t Dec_FactorLF_rec( Dec_Graph_t * pFForm, Mvc_Cover_t * pCover, Mvc_Cov ***********************************************************************/ Dec_Edge_t Dec_FactorTrivial( Dec_Graph_t * pFForm, Mvc_Cover_t * pCover ) { - Dec_Man_t * pManDec = Abc_FrameReadManDec(Abc_FrameGetGlobalFrame()); + Dec_Man_t * pManDec = Abc_FrameReadManDec(); Vec_Int_t * vEdgeCubes = pManDec->vCubes; Vec_Int_t * vEdgeLits = pManDec->vLits; Mvc_Manager_t * pMem = pManDec->pMvcMem; @@ -323,7 +323,7 @@ Dec_Edge_t Dec_FactorTrivialTree_rec( Dec_Graph_t * pFForm, Dec_Edge_t * peNodes ***********************************************************************/ Mvc_Cover_t * Dec_ConvertSopToMvc( char * pSop ) { - Dec_Man_t * pManDec = Abc_FrameReadManDec(Abc_FrameGetGlobalFrame()); + Dec_Man_t * pManDec = Abc_FrameReadManDec(); Mvc_Manager_t * pMem = pManDec->pMvcMem; Mvc_Cover_t * pMvc; Mvc_Cube_t * pMvcCube; @@ -365,7 +365,7 @@ Mvc_Cover_t * Dec_ConvertSopToMvc( char * pSop ) ***********************************************************************/ int Dec_FactorVerify( char * pSop, Dec_Graph_t * pFForm ) { - DdManager * dd = Abc_FrameReadManDd( Abc_FrameGetGlobalFrame() ); + DdManager * dd = Abc_FrameReadManDd(); DdNode * bFunc1, * bFunc2; int RetValue; bFunc1 = Abc_ConvertSopToBdd( dd, pSop ); Cudd_Ref( bFunc1 ); diff --git a/src/opt/rwr/rwrMan.c b/src/opt/rwr/rwrMan.c index bfeaa273..6bf1fdbe 100644 --- a/src/opt/rwr/rwrMan.c +++ b/src/opt/rwr/rwrMan.c @@ -50,7 +50,7 @@ clk = clock(); p = ALLOC( Rwr_Man_t, 1 ); memset( p, 0, sizeof(Rwr_Man_t) ); p->nFuncs = (1<<16); - pManDec = Abc_FrameReadManDec(Abc_FrameGetGlobalFrame()); + pManDec = Abc_FrameReadManDec(); p->puCanons = pManDec->puCanons; p->pPhases = pManDec->pPhases; p->pPerms = pManDec->pPerms; diff --git a/src/sat/asat/solver.h b/src/sat/asat/solver.h index f328fad5..8e981198 100644 --- a/src/sat/asat/solver.h +++ b/src/sat/asat/solver.h @@ -43,9 +43,9 @@ typedef int lit; typedef char lbool; #ifdef _WIN32 -typedef signed __int64 uint64; // compatible with MS VS 6.0 +typedef signed __int64 sint64; // compatible with MS VS 6.0 #else -typedef unsigned long long uint64; +typedef long long sint64; #endif static const int var_Undef = -1; @@ -80,8 +80,8 @@ extern void Asat_SolverWriteDimacs( solver * pSat, char * pFileName ); struct stats_t { - uint64 starts, decisions, propagations, inspects, conflicts; - uint64 clauses, clauses_literals, learnts, learnts_literals, max_literals, tot_literals; + sint64 starts, decisions, propagations, inspects, conflicts; + sint64 clauses, clauses_literals, learnts, learnts_literals, max_literals, tot_literals; }; typedef struct stats_t stats; |