diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/base/abc/abc.c | 26 | ||||
| -rw-r--r-- | src/base/abc/abc.h | 15 | ||||
| -rw-r--r-- | src/base/abc/abcAig.c | 141 | ||||
| -rw-r--r-- | src/base/abc/abcBalance.c | 236 | ||||
| -rw-r--r-- | src/base/abc/abcCreate.c | 4 | ||||
| -rw-r--r-- | src/base/abc/abcFunc.c | 7 | ||||
| -rw-r--r-- | src/base/abc/abcNames.c | 6 | ||||
| -rw-r--r-- | src/base/abc/abcReconv.c | 342 | ||||
| -rw-r--r-- | src/base/abc/abcRefactor.c | 249 | ||||
| -rw-r--r-- | src/base/abc/abcRefs.c | 62 | ||||
| -rw-r--r-- | src/base/abc/abcRewrite.c | 11 | ||||
| -rw-r--r-- | src/base/abc/abcSop.c | 131 | ||||
| -rw-r--r-- | src/base/abc/abcStrash.c | 439 | ||||
| -rw-r--r-- | src/base/io/ioReadPla.c | 17 | ||||
| -rw-r--r-- | src/map/fpga/fpgaUtils.c | 102 | ||||
| -rw-r--r-- | src/map/mapper/mapperUtils.c | 114 | ||||
| -rw-r--r-- | src/opt/rwr/rwrEva.c | 2 | ||||
| -rw-r--r-- | src/sop/ft/ftFactor.c | 4 |
18 files changed, 1183 insertions, 725 deletions
diff --git a/src/base/abc/abc.c b/src/base/abc/abc.c index 7f4ee12f..7d9f9725 100644 --- a/src/base/abc/abc.c +++ b/src/base/abc/abc.c @@ -1414,9 +1414,10 @@ int Abc_CommandRefactor( Abc_Frame_t * pAbc, int argc, char ** argv ) int c; int nNodeSizeMax; int nConeSizeMax; + bool fUseZeros; bool fUseDcs; bool fVerbose; - extern int Abc_NtkRefactor( Abc_Ntk_t * pNtk, int nNodeSizeMax, int nConeSizeMax, bool fUseDcs, bool fVerbose ); + extern int Abc_NtkRefactor( Abc_Ntk_t * pNtk, int nNodeSizeMax, int nConeSizeMax, bool fUseZeros, bool fUseDcs, bool fVerbose ); pNtk = Abc_FrameReadNet(pAbc); pOut = Abc_FrameReadOut(pAbc); @@ -1424,11 +1425,12 @@ int Abc_CommandRefactor( Abc_Frame_t * pAbc, int argc, char ** argv ) // set defaults nNodeSizeMax = 10; - nConeSizeMax = 10; + nConeSizeMax = 16; + fUseZeros = 0; fUseDcs = 0; - fVerbose = 0; + fVerbose = 1; util_getopt_reset(); - while ( ( c = util_getopt( argc, argv, "NCdvh" ) ) != EOF ) + while ( ( c = util_getopt( argc, argv, "NCzdvh" ) ) != EOF ) { switch ( c ) { @@ -1454,6 +1456,9 @@ int Abc_CommandRefactor( Abc_Frame_t * pAbc, int argc, char ** argv ) if ( nConeSizeMax < 0 ) goto usage; break; + case 'z': + fUseZeros ^= 1; + break; case 'd': fUseDcs ^= 1; break; @@ -1483,8 +1488,14 @@ int Abc_CommandRefactor( Abc_Frame_t * pAbc, int argc, char ** argv ) return 1; } + if ( fUseDcs && nNodeSizeMax >= nConeSizeMax ) + { + fprintf( pErr, "For don't-care to work, containing cone should be larger than collapsed node.\n" ); + return 1; + } + // modify the current network - if ( !Abc_NtkRefactor( pNtk, nNodeSizeMax, nConeSizeMax, fUseDcs, fVerbose ) ) + if ( !Abc_NtkRefactor( pNtk, nNodeSizeMax, nConeSizeMax, fUseZeros, fUseDcs, fVerbose ) ) { fprintf( pErr, "Refactoring has failed.\n" ); return 1; @@ -1492,11 +1503,12 @@ int Abc_CommandRefactor( Abc_Frame_t * pAbc, int argc, char ** argv ) return 0; usage: - fprintf( pErr, "usage: refactor [-N num] [-C num] [-dvh]\n" ); + fprintf( pErr, "usage: refactor [-N num] [-C num] [-zdvh]\n" ); fprintf( pErr, "\t performs technology-independent refactoring of the AIG\n" ); fprintf( pErr, "\t-N num : the max support of the collapsed node [default = %d]\n", nNodeSizeMax ); fprintf( pErr, "\t-C num : the max support of the containing cone [default = %d]\n", nConeSizeMax ); - fprintf( pErr, "\t-d : toggle use of don't-cares [default = %s]\n", fUseDcs? "yes": "no" ); + fprintf( pErr, "\t-z : toggle using zero-cost replacements [default = %s]\n", fUseZeros? "yes": "no" ); + fprintf( pErr, "\t-d : toggle using don't-cares [default = %s]\n", fUseDcs? "yes": "no" ); fprintf( pErr, "\t-v : toggle verbose printout [default = %s]\n", fVerbose? "yes": "no" ); fprintf( pErr, "\t-h : print the command usage\n"); return 1; diff --git a/src/base/abc/abc.h b/src/base/abc/abc.h index 3bf419c5..ff1252c1 100644 --- a/src/base/abc/abc.h +++ b/src/base/abc/abc.h @@ -101,6 +101,7 @@ struct Abc_Time_t_ struct Abc_Obj_t_ // 12 words { // high-level information + Abc_Ntk_t * pNtk; // the host network unsigned Type : 4; // the object type unsigned fExor : 1; // marks AIG node that is a root of EXOR unsigned Id : 27; // the ID of the object @@ -115,7 +116,6 @@ struct Abc_Obj_t_ // 12 words Vec_Fan_t vFanins; // the array of fanins Vec_Fan_t vFanouts; // the array of fanouts // miscellaneous - Abc_Ntk_t * pNtk; // the host network void * pData; // the network specific data (SOP, BDD, gate, equiv class, etc) Abc_Obj_t * pNext; // the next pointer in the hash table Abc_Obj_t * pCopy; // the copy of this object @@ -381,6 +381,7 @@ extern void Abc_AigReplace( Abc_Aig_t * pMan, Abc_Obj_t * pOld, Ab extern void Abc_AigDeleteNode( Abc_Aig_t * pMan, Abc_Obj_t * pOld ); extern bool Abc_AigNodeHasComplFanoutEdge( Abc_Obj_t * pNode ); extern bool Abc_AigNodeHasComplFanoutEdgeTrav( Abc_Obj_t * pNode ); +extern void Abc_AigPrintNode( Abc_Obj_t * pNode ); /*=== abcAttach.c ==========================================================*/ extern int Abc_NtkAttach( Abc_Ntk_t * pNtk ); /*=== abcCheck.c ==========================================================*/ @@ -495,12 +496,15 @@ extern void Abc_NodePrintLevel( FILE * pFile, Abc_Obj_t * pNode ); /*=== abcReconv.c ==========================================================*/ extern Abc_ManCut_t * Abc_NtkManCutStart( int nNodeSizeMax, int nConeSizeMax ); extern void Abc_NtkManCutStop( Abc_ManCut_t * p ); -extern Vec_Ptr_t * Abc_NodeFindCut( Abc_ManCut_t * p, Abc_Obj_t * pRoot ); +extern Vec_Ptr_t * Abc_NtkManCutReadLeaves( Abc_ManCut_t * p ); +extern Vec_Ptr_t * Abc_NodeFindCut( Abc_ManCut_t * p, Abc_Obj_t * pRoot, bool fContain ); extern DdNode * Abc_NodeConeBdd( DdManager * dd, DdNode ** pbVars, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, Vec_Ptr_t * vVisited ); +extern DdNode * Abc_NodeConeDcs( DdManager * dd, DdNode ** pbVarsX, DdNode ** pbVarsY, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots, Vec_Ptr_t * vVisited ); extern void Abc_NodeCollectTfoCands( Abc_Ntk_t * pNtk, Abc_Obj_t * pRoot, Vec_Ptr_t * vFanins, int LevelMax, Vec_Vec_t * vLevels, Vec_Ptr_t * vResult ); /*=== abcRefs.c ==========================================================*/ extern int Abc_NodeMffcSize( Abc_Obj_t * pNode ); extern int Abc_NodeMffcLabel( Abc_Obj_t * pNode ); +extern Vec_Ptr_t * Abc_NodeMffcCollect( Abc_Obj_t * pNode ); extern void Abc_NodeUpdate( Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, Vec_Int_t * vForm, int nGain ); /*=== abcRenode.c ==========================================================*/ extern Abc_Ntk_t * Abc_NtkRenode( Abc_Ntk_t * pNtk, int nThresh, int nFaninMax, int fCnf, int fMulti, int fSimple ); @@ -531,21 +535,22 @@ extern int Abc_SopGetCubeNum( char * pSop ); extern int Abc_SopGetLitNum( char * pSop ); extern int Abc_SopGetVarNum( char * pSop ); extern int Abc_SopGetPhase( char * pSop ); +extern int Abc_SopGetIthCareLit( char * pSop, int i ); +extern void Abc_SopComplement( char * pSop ); +extern bool Abc_SopIsComplement( char * pSop ); extern bool Abc_SopIsConst0( char * pSop ); extern bool Abc_SopIsConst1( char * pSop ); extern bool Abc_SopIsBuf( char * pSop ); extern bool Abc_SopIsInv( char * pSop ); extern bool Abc_SopIsAndType( char * pSop ); extern bool Abc_SopIsOrType( char * pSop ); -extern int Abc_SopGetIthCareLit( char * pSop, int i ); -extern void Abc_SopComplement( char * pSop ); extern bool Abc_SopCheck( char * pSop, int nFanins ); extern void Abc_SopWriteCnf( FILE * pFile, char * pClauses, Vec_Int_t * vVars ); extern void Abc_SopAddCnfToSolver( solver * pSat, char * pClauses, Vec_Int_t * vVars, Vec_Int_t * vTemp ); /*=== abcStrash.c ==========================================================*/ extern Abc_Ntk_t * Abc_NtkStrash( Abc_Ntk_t * pNtk, bool fAllNodes ); extern Abc_Obj_t * Abc_NodeStrashDec( Abc_Aig_t * pMan, Vec_Ptr_t * vFanins, Vec_Int_t * vForm ); -extern int Abc_NodeStrashDecCount( Abc_Aig_t * pMan, Vec_Ptr_t * vFanins, Vec_Int_t * vForm, Vec_Int_t * vLevels, int NodeMax, int LevelMax ); +extern int Abc_NodeStrashDecCount( Abc_Aig_t * pMan, Abc_Obj_t * pRoot, Vec_Ptr_t * vFanins, Vec_Int_t * vForm, Vec_Int_t * vLevels, int NodeMax, int LevelMax ); extern int Abc_NtkAppend( Abc_Ntk_t * pNtk1, Abc_Ntk_t * pNtk2 ); extern Abc_Ntk_t * Abc_NtkBalance( Abc_Ntk_t * pNtk, bool fDuplicate ); /*=== abcSweep.c ==========================================================*/ diff --git a/src/base/abc/abcAig.c b/src/base/abc/abcAig.c index b7bcde83..883c544f 100644 --- a/src/base/abc/abcAig.c +++ b/src/base/abc/abcAig.c @@ -26,15 +26,16 @@ - for each AND gate, there are no other AND gates with the same children - the constants are propagated - there is no single-input nodes (inverters/buffers) + Additionally the following invariants are satisfied: - there are no dangling nodes (the nodes without fanout) - the level of each AND gate reflects the levels of this fanins - the EXOR-status of each node is up-to-date - The operations that are performed on AIG: + The operations that are performed on AIGs: - building new nodes (Abc_AigAnd) - performing elementary Boolean operations (Abc_AigOr, Abc_AigXor, etc) - replacing one node by another (Abc_AigReplace) - propagating constants (Abc_AigReplace) - When AIG is duplicated, the new graph is struturally hashed too. + When AIG is duplicated, the new graph is structurally hashed too. If this repeated hashing leads to fewer nodes, it means the original AIG was not strictly hashed (one of the conditions above is violated). */ @@ -226,10 +227,7 @@ int Abc_AigCleanup( Abc_Aig_t * pMan ) for ( i = 0; i < pMan->nBins; i++ ) Abc_AigBinForEachEntry( pMan->pBins[i], pAnd ) if ( Abc_ObjFanoutNum(pAnd) == 0 ) - { Vec_PtrPush( pMan->vStackDelete, pAnd ); - pAnd->fMarkA = 1; - } // process the dangling nodes and their MFFCs for ( Counter = 0; Vec_PtrSize(pMan->vStackDelete) > 0; Counter++ ) Abc_AigDelete_int( pMan ); @@ -409,6 +407,7 @@ Abc_Obj_t * Abc_AigAndCreateFrom( Abc_Aig_t * pMan, Abc_Obj_t * p0, Abc_Obj_t * Abc_ObjAddFanin( pAnd, p1 ); // set the level of the new node pAnd->Level = 1 + ABC_MAX( Abc_ObjRegular(p0)->Level, Abc_ObjRegular(p1)->Level ); + pAnd->fExor = Abc_NodeIsExorType(pAnd); // add the node to the corresponding linked list in the table Key = Abc_HashKey2( p0, p1, pMan->nBins ); pAnd->pNext = pMan->pBins[Key]; @@ -453,7 +452,7 @@ Abc_Obj_t * Abc_AigAndLookup( Abc_Aig_t * pMan, Abc_Obj_t * p0, Abc_Obj_t * p1 ) pAnd = p0, p0 = p1, p1 = pAnd; // get the hash key for these two nodes Key = Abc_HashKey2( p0, p1, pMan->nBins ); - // find the mataching node in the table + // find the matching node in the table Abc_AigBinForEachEntry( pMan->pBins[Key], pAnd ) if ( p0 == Abc_ObjChild0(pAnd) && p1 == Abc_ObjChild1(pAnd) ) return pAnd; @@ -476,25 +475,30 @@ void Abc_AigAndDelete( Abc_Aig_t * pMan, Abc_Obj_t * pThis ) Abc_Obj_t * pAnd, ** ppPlace; unsigned Key; assert( !Abc_ObjIsComplement(pThis) ); + assert( Abc_ObjIsNode(pThis) ); + assert( Abc_ObjFaninNum(pThis) == 2 ); assert( pMan->pNtkAig == pThis->pNtk ); // get the hash key for these two nodes Key = Abc_HashKey2( Abc_ObjChild0(pThis), Abc_ObjChild1(pThis), pMan->nBins ); - // find the mataching node in the table + // find the matching node in the table ppPlace = pMan->pBins + Key; Abc_AigBinForEachEntry( pMan->pBins[Key], pAnd ) + { if ( pAnd != pThis ) - ppPlace = &pAnd->pNext; - else { - *ppPlace = pAnd->pNext; - break; + ppPlace = &pAnd->pNext; + continue; } + *ppPlace = pAnd->pNext; + break; + } assert( pAnd == pThis ); + pMan->nEntries--; } /**Function************************************************************* - Synopsis [] + Synopsis [Resizes the hash table of AIG nodes.] Description [] @@ -512,7 +516,7 @@ void Abc_AigResize( Abc_Aig_t * pMan ) clk = clock(); // get the new table size - nBinsNew = Cudd_PrimeCopy(2 * pMan->nBins); + nBinsNew = Cudd_PrimeCopy( 3 * pMan->nBins ); // allocate a new array pBinsNew = ALLOC( Abc_Obj_t *, nBinsNew ); memset( pBinsNew, 0, sizeof(Abc_Obj_t *) * nBinsNew ); @@ -560,7 +564,7 @@ Abc_Obj_t * Abc_AigAnd( Abc_Aig_t * pMan, Abc_Obj_t * p0, Abc_Obj_t * p1 ) /**Function************************************************************* - Synopsis [Implements Boolean AND.] + Synopsis [Implements Boolean OR.] Description [] @@ -576,7 +580,7 @@ Abc_Obj_t * Abc_AigOr( Abc_Aig_t * pMan, Abc_Obj_t * p0, Abc_Obj_t * p1 ) /**Function************************************************************* - Synopsis [Implements Boolean AND.] + Synopsis [Implements Boolean XOR.] Description [] @@ -619,6 +623,7 @@ Abc_Obj_t * Abc_AigMiter( Abc_Aig_t * pMan, Vec_Ptr_t * vPairs ) + /**Function************************************************************* Synopsis [Replaces one AIG node by the other.] @@ -639,8 +644,8 @@ void Abc_AigReplace( Abc_Aig_t * pMan, Abc_Obj_t * pOld, Abc_Obj_t * pNew ) Vec_PtrPush( pMan->vStackReplaceNew, pNew ); while ( Vec_PtrSize(pMan->vStackReplaceOld) ) Abc_AigReplace_int( pMan ); - while ( Vec_PtrSize(pMan->vStackDelete) ) - Abc_AigDelete_int( pMan ); +// while ( Vec_PtrSize(pMan->vStackDelete) ) +// Abc_AigDelete_int( pMan ); Abc_AigUpdateLevel_int( pMan ); } @@ -664,7 +669,7 @@ void Abc_AigReplace_int( Abc_Aig_t * pMan ) pOld = Vec_PtrPop( pMan->vStackReplaceOld ); pNew = Vec_PtrPop( pMan->vStackReplaceNew ); // make sure the old node is regular and has fanouts - // the new node can be complemented and can have fanouts + // (the new node can be complemented and can have fanouts) assert( !Abc_ObjIsComplement(pOld) ); assert( Abc_ObjFanoutNum(pOld) > 0 ); // look at the fanouts of old node @@ -691,26 +696,25 @@ void Abc_AigReplace_int( Abc_Aig_t * pMan ) Vec_PtrPush( pMan->vStackReplaceNew, pFanoutNew ); continue; } - // such node does not exist - modify the old fanout - // remove the old fanout from the table + // such node does not exist - modify the old fanout node + // (this way the change will not propagate all the way to the COs) + assert( Abc_ObjRegular(pFanin1) != Abc_ObjRegular(pFanin2) ); + // remove the old fanout node from the structural hashing table Abc_AigAndDelete( pMan, pFanout ); - // remove its old fanins + // remove the fanins of the old fanout Abc_ObjRemoveFanins( pFanout ); - // update the old fanout with new fanins and add it to the table + // recreate the old fanout with new fanins and add it to the table Abc_AigAndCreateFrom( pMan, pFanin1, pFanin2, pFanout ); - // schedule the updated node for updating level + // schedule the updated fanout for updating level Vec_VecPush( pMan->vLevels, pFanout->Level, pFanout ); - // the node has changed, update EXOR status of the fanouts + // the fanout has changed, update EXOR status of its fanouts Abc_ObjForEachFanout( pFanout, pFanoutFanout, v ) if ( Abc_NodeIsAigAnd(pFanoutFanout) ) pFanoutFanout->fExor = Abc_NodeIsExorType(pFanoutFanout); } - // schedule deletion of the old node - if ( Abc_NodeIsAigAnd(pOld) && pOld->fMarkA == 0 ) - { - Vec_PtrPush( pMan->vStackDelete, pOld ); - pOld->fMarkA = 1; - } + // if the node has no fanouts left, remove its MFFC + if ( Abc_ObjFanoutNum(pOld) == 0 ) + Abc_AigDeleteNode( pMan, pOld ); } /**Function************************************************************* @@ -745,31 +749,33 @@ void Abc_AigDeleteNode( Abc_Aig_t * pMan, Abc_Obj_t * pOld ) ***********************************************************************/ void Abc_AigDelete_int( Abc_Aig_t * pMan ) { - Abc_Obj_t * pNode, * pFanin; + Vec_Ptr_t * vNodes; + Abc_Obj_t * pRoot, * pObj; int k; // get the node to delete assert( Vec_PtrSize(pMan->vStackDelete) > 0 ); - pNode = Vec_PtrPop( pMan->vStackDelete ); + pRoot = Vec_PtrPop( pMan->vStackDelete ); // make sure the node is regular and dangling - assert( !Abc_ObjIsComplement(pNode) ); - assert( Abc_ObjFanoutNum(pNode) == 0 ); - assert( pNode != pMan->pConst1 ); - // schedule fanins for deletion if they dangle - Abc_ObjForEachFanin( pNode, pFanin, k ) + assert( !Abc_ObjIsComplement(pRoot) ); + assert( Abc_ObjIsNode(pRoot) ); + assert( Abc_ObjFaninNum(pRoot) == 2 ); + assert( Abc_ObjFanoutNum(pRoot) == 0 ); + + // collect the MFFC + vNodes = Abc_NodeMffcCollect( pRoot ); + Vec_PtrForEachEntry( vNodes, pObj, k ) { - assert( Abc_ObjFanoutNum(pFanin) > 0 ); - if ( Abc_ObjFanoutNum(pFanin) == 1 ) - if ( Abc_NodeIsAigAnd(pFanin) && pFanin->fMarkA == 0 ) - { - Vec_PtrPush( pMan->vStackDelete, pFanin ); - pFanin->fMarkA = 1; - } + if ( Abc_ObjIsCi(pObj) ) + continue; + assert( pObj->fMarkA == 0 ); + // remove the node from the table + Abc_AigAndDelete( pMan, pObj ); + // remove the node from the network +//printf( "Removing " ); Abc_AigPrintNode( pObj ); + Abc_NtkDeleteObj( pObj ); } - // remove the node from the table - Abc_AigAndDelete( pMan, pNode ); - // remove the node fro the network - Abc_NtkDeleteObj( pNode ); + Vec_PtrFree( vNodes ); } /**Function************************************************************* @@ -797,7 +803,11 @@ void Abc_AigUpdateLevel_int( Abc_Aig_t * pMan ) continue; Vec_PtrForEachEntry( vVec, pNode, k ) { - assert( Abc_ObjIsNode(pNode) ); +// assert( Abc_ObjIsNode(pNode) ); + // for some reason, deleted nodes are encountered here!!! + if ( !Abc_ObjIsNode(pNode) ) + continue; + // iterate through the fanouts Abc_ObjForEachFanout( pNode, pFanout, v ) { if ( Abc_ObjIsCo(pFanout) ) @@ -877,6 +887,39 @@ bool Abc_AigNodeHasComplFanoutEdgeTrav( Abc_Obj_t * pNode ) } +/**Function************************************************************* + + Synopsis [Prints the AIG node for debugging purposes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_AigPrintNode( Abc_Obj_t * pNode ) +{ + Abc_Obj_t * pNodeR = Abc_ObjRegular(pNode); + if ( Abc_ObjIsCi(pNodeR) ) + { + printf( "CI %4s%s.\n", Abc_ObjName(pNodeR), Abc_ObjIsComplement(pNode)? "\'" : "" ); + return; + } + if ( Abc_NodeIsConst(pNodeR) ) + { + printf( "Constant 1 %s.\n", Abc_ObjIsComplement(pNode)? "(complemented)" : "" ); + return; + } + // print the node's function + printf( "%7s%s", Abc_ObjName(pNodeR), Abc_ObjIsComplement(pNode)? "\'" : "" ); + printf( " = " ); + printf( "%7s%s", Abc_ObjName(Abc_ObjFanin0(pNodeR)), Abc_ObjFaninC0(pNodeR)? "\'" : "" ); + printf( " * " ); + printf( "%7s%s", Abc_ObjName(Abc_ObjFanin1(pNodeR)), Abc_ObjFaninC1(pNodeR)? "\'" : "" ); + printf( "\n" ); +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/base/abc/abcBalance.c b/src/base/abc/abcBalance.c new file mode 100644 index 00000000..bcf1032b --- /dev/null +++ b/src/base/abc/abcBalance.c @@ -0,0 +1,236 @@ +/**CFile**************************************************************** + + FileName [abcBalance.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Network and node package.] + + Synopsis [Performs global balancing of the AIG by the number of levels.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: abcBalance.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "abc.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate ); +static Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, bool fDuplicate ); +static Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, int fDuplicate ); +static int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, bool fDuplicate ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Balances the AIG network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * Abc_NtkBalance( Abc_Ntk_t * pNtk, bool fDuplicate ) +{ + int fCheck = 1; + Abc_Ntk_t * pNtkAig; + assert( Abc_NtkIsAig(pNtk) ); + // perform balancing + pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_AIG ); + Abc_NtkBalancePerform( pNtk, pNtkAig, fDuplicate ); + Abc_NtkFinalize( pNtk, pNtkAig ); + // make sure everything is okay + if ( fCheck && !Abc_NtkCheck( pNtkAig ) ) + { + printf( "Abc_NtkBalance: The network check has failed.\n" ); + Abc_NtkDelete( pNtkAig ); + return NULL; + } + return pNtkAig; +} + +/**Function************************************************************* + + Synopsis [Balances the AIG network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate ) +{ + int fCheck = 1; + ProgressBar * pProgress; + Abc_Obj_t * pNode, * pDriver; + int i; + + // copy the constant node + Abc_AigConst1(pNtk->pManFunc)->pCopy = Abc_AigConst1(pNtkAig->pManFunc); + // set the level of PIs of AIG according to the arrival times of the old network + Abc_NtkSetNodeLevelsArrival( pNtk ); + // perform balancing of POs + pProgress = Extra_ProgressBarStart( stdout, Abc_NtkCoNum(pNtk) ); + Abc_NtkForEachCo( pNtk, pNode, i ) + { + Extra_ProgressBarUpdate( pProgress, i, NULL ); + // strash the driver node + pDriver = Abc_ObjFanin0(pNode); + Abc_NodeBalance_rec( pNtkAig, pDriver, fDuplicate ); + } + Extra_ProgressBarStop( pProgress ); +} + +/**Function************************************************************* + + Synopsis [Rebalances the multi-input node rooted at pNodeOld.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, bool fDuplicate ) +{ + Abc_Aig_t * pMan = pNtkNew->pManFunc; + Abc_Obj_t * pNodeNew, * pNode1, * pNode2; + Vec_Ptr_t * vSuper; + int i; + assert( !Abc_ObjIsComplement(pNodeOld) ); + // return if the result if known + if ( pNodeOld->pCopy ) + return pNodeOld->pCopy; + assert( Abc_ObjIsNode(pNodeOld) ); + // get the implication supergate + vSuper = Abc_NodeBalanceCone( pNodeOld, fDuplicate ); + if ( vSuper->nSize == 0 ) + { // it means that the supergate contains two nodes in the opposite polarity + Vec_PtrFree( vSuper ); + pNodeOld->pCopy = Abc_ObjNot(Abc_AigConst1(pMan)); + return pNodeOld->pCopy; + } + // for each old node, derive the new well-balanced node + for ( i = 0; i < vSuper->nSize; i++ ) + { + pNodeNew = Abc_NodeBalance_rec( pNtkNew, Abc_ObjRegular(vSuper->pArray[i]), fDuplicate ); + vSuper->pArray[i] = Abc_ObjNotCond( pNodeNew, Abc_ObjIsComplement(vSuper->pArray[i]) ); + } + // sort the new nodes by level in the decreasing order + Vec_PtrSort( vSuper, Abc_NodeCompareLevelsDecrease ); + // balance the nodes + assert( vSuper->nSize > 1 ); + while ( vSuper->nSize > 1 ) + { + pNode1 = Vec_PtrPop(vSuper); + pNode2 = Vec_PtrPop(vSuper); + Abc_VecObjPushUniqueOrderByLevel( vSuper, Abc_AigAnd(pMan, pNode1, pNode2) ); + } + // make sure the balanced node is not assigned + assert( pNodeOld->pCopy == NULL ); + // mark the old node with the new node + pNodeOld->pCopy = vSuper->pArray[0]; + Vec_PtrFree( vSuper ); + return pNodeOld->pCopy; +} + +/**Function************************************************************* + + Synopsis [Collects the nodes in the cone delimited by fMarkA==1.] + + Description [Returns -1 if the AND-cone has the same node in both polarities. + Returns 1 if the AND-cone has the same node in the same polarity. Returns 0 + if the AND-cone has no repeated nodes.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, int fDuplicate ) +{ + Vec_Ptr_t * vNodes; + int RetValue, i; + assert( !Abc_ObjIsComplement(pNode) ); + vNodes = Vec_PtrAlloc( 4 ); + RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, fDuplicate ); + assert( vNodes->nSize > 0 ); + for ( i = 0; i < vNodes->nSize; i++ ) + Abc_ObjRegular((Abc_Obj_t *)vNodes->pArray[i])->fMarkB = 0; + if ( RetValue == -1 ) + vNodes->nSize = 0; + return vNodes; +} + + +/**Function************************************************************* + + Synopsis [Collects the nodes in the cone delimited by fMarkA==1.] + + Description [Returns -1 if the AND-cone has the same node in both polarities. + Returns 1 if the AND-cone has the same node in the same polarity. Returns 0 + if the AND-cone has no repeated nodes.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, bool fDuplicate ) +{ + int RetValue1, RetValue2, i; + // check if the node is visited + if ( Abc_ObjRegular(pNode)->fMarkB ) + { + // check if the node occurs in the same polarity + for ( i = 0; i < vSuper->nSize; i++ ) + if ( vSuper->pArray[i] == pNode ) + return 1; + // check if the node is present in the opposite polarity + for ( i = 0; i < vSuper->nSize; i++ ) + if ( vSuper->pArray[i] == Abc_ObjNot(pNode) ) + return -1; + assert( 0 ); + return 0; + } + // if the new node is complemented or a PI, another gate begins + if ( !fFirst && (Abc_ObjIsComplement(pNode) || !Abc_ObjIsNode(pNode) || !fDuplicate && (Abc_ObjFanoutNum(pNode) > 1)) ) + { + Vec_PtrPush( vSuper, pNode ); + Abc_ObjRegular(pNode)->fMarkB = 1; + return 0; + } + assert( !Abc_ObjIsComplement(pNode) ); + assert( Abc_ObjIsNode(pNode) ); + // go through the branches + RetValue1 = Abc_NodeBalanceCone_rec( Abc_ObjChild0(pNode), vSuper, 0, fDuplicate ); + RetValue2 = Abc_NodeBalanceCone_rec( Abc_ObjChild1(pNode), vSuper, 0, fDuplicate ); + if ( RetValue1 == -1 || RetValue2 == -1 ) + return -1; + // return 1 if at least one branch has a duplicate + return RetValue1 || RetValue2; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/base/abc/abcCreate.c b/src/base/abc/abcCreate.c index 47ad5aea..9f192979 100644 --- a/src/base/abc/abcCreate.c +++ b/src/base/abc/abcCreate.c @@ -504,7 +504,9 @@ Abc_Obj_t * Abc_ObjAlloc( Abc_Ntk_t * pNtk, Abc_ObjType_t Type ) ***********************************************************************/ void Abc_ObjRecycle( Abc_Obj_t * pObj ) { - Extra_MmFixedEntryRecycle( pObj->pNtk->pMmObj, (char *)pObj ); + Abc_Ntk_t * pNtk = pObj->pNtk; + memset( pObj, 0, sizeof(Abc_Obj_t) ); + Extra_MmFixedEntryRecycle( pNtk->pMmObj, (char *)pObj ); } /**Function************************************************************* diff --git a/src/base/abc/abcFunc.c b/src/base/abc/abcFunc.c index dd3fa033..8ecbd343 100644 --- a/src/base/abc/abcFunc.c +++ b/src/base/abc/abcFunc.c @@ -205,7 +205,10 @@ char * Abc_ConvertBddToSop( Extra_MmFlex_t * pMan, DdManager * dd, DdNode * bFun { Vec_StrFill( vCube, nFanins, '-' ); Vec_StrPush( vCube, '\0' ); - pSop = Extra_MmFlexEntryFetch( pMan, nFanins + 4 ); + if ( pMan ) + pSop = Extra_MmFlexEntryFetch( pMan, nFanins + 4 ); + else + pSop = ALLOC( char, nFanins + 4 ); if ( bFuncOn == Cudd_ReadLogicZero(dd) ) sprintf( pSop, "%s 0\n", vCube->pArray ); else @@ -249,7 +252,7 @@ char * Abc_ConvertBddToSop( Extra_MmFlex_t * pMan, DdManager * dd, DdNode * bFun } else if ( fMode == 0 ) { - // get the ZDD of the positive polarity + // get the ZDD of the negative polarity bCover = Cudd_zddIsop( dd, Cudd_Not(bFuncOnDc), Cudd_Not(bFuncOn), &zCover ); Cudd_Ref( zCover ); Cudd_Ref( bCover ); diff --git a/src/base/abc/abcNames.c b/src/base/abc/abcNames.c index 07c64712..088dc855 100644 --- a/src/base/abc/abcNames.c +++ b/src/base/abc/abcNames.c @@ -73,9 +73,11 @@ char * Abc_NtkRegisterNamePlus( Abc_Ntk_t * pNtk, char * pName, char * pSuffix ) /**Function************************************************************* - Synopsis [Gets the long name of the node.] + Synopsis [Gets the long name of the object.] - Description [This name is the output net's name.] + Description [The temporary name is stored in a static buffer inside this + procedure. It is important that the name is used before the function is + called again!] SideEffects [] diff --git a/src/base/abc/abcReconv.c b/src/base/abc/abcReconv.c index 82adc92c..89a4d871 100644 --- a/src/base/abc/abcReconv.c +++ b/src/base/abc/abcReconv.c @@ -32,17 +32,12 @@ struct Abc_ManCut_t_ int nConeSizeMax; // the limit on the size of the containing cone // internal parameters Vec_Ptr_t * vFaninsNode; // fanins of the supernode - Vec_Ptr_t * vInsideNode; // inside of the supernode Vec_Ptr_t * vFaninsCone; // fanins of the containing cone - Vec_Ptr_t * vInsideCone; // inside of the containing cone Vec_Ptr_t * vVisited; // the visited nodes }; -static int Abc_NodeFindCut_int( Vec_Ptr_t * vInside, Vec_Ptr_t * vFanins, int nSizeLimit ); -static int Abc_NodeGetFaninCost( Abc_Obj_t * pNode ); -static void Abc_NodeConeMarkCollect_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vVisited ); -static void Abc_NodeConeMark( Vec_Ptr_t * vVisited ); -static void Abc_NodeConeUnmark( Vec_Ptr_t * vVisited ); +static int Abc_NodeFindCut_int( Vec_Ptr_t * vFanins, int nSizeLimit ); +static void Abc_NodesMarkCollect_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vVisited ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// @@ -50,7 +45,98 @@ static void Abc_NodeConeUnmark( Vec_Ptr_t * vVisited ); /**Function************************************************************* - Synopsis [Finds a reconvergence-driven cut.] + Synopsis [Unmarks the TFI cone.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Abc_NodesMark( Vec_Ptr_t * vVisited ) +{ + Abc_Obj_t * pNode; + int i; + Vec_PtrForEachEntry( vVisited, pNode, i ) + pNode->fMarkA = 1; +} + +/**Function************************************************************* + + Synopsis [Unmarks the TFI cone.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Abc_NodesUnmark( Vec_Ptr_t * vVisited ) +{ + Abc_Obj_t * pNode; + int i; + Vec_PtrForEachEntry( vVisited, pNode, i ) + pNode->fMarkA = 0; +} + +/**Function************************************************************* + + Synopsis [Unmarks the TFI cone.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Abc_NodesUnmarkBoth( Vec_Ptr_t * vVisited ) +{ + Abc_Obj_t * pNode; + int i; + Vec_PtrForEachEntry( vVisited, pNode, i ) + pNode->fMarkA = pNode->fMarkB = 0; +} + +/**Function************************************************************* + + Synopsis [Evaluate the fanin cost.] + + Description [Returns the number of fanins that will be brought in. + Returns large number if the node cannot be added.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Abc_NodeGetFaninCost( Abc_Obj_t * pNode ) +{ + Abc_Obj_t * pFanout; + int i; + assert( pNode->fMarkA == 1 ); // this node is in the TFI + assert( pNode->fMarkB == 1 ); // this node is in the constructed cone + // check the PI node + if ( Abc_ObjIsCi(pNode) ) + return 999; + // skip nodes with many fanouts + if ( Abc_ObjFanoutNum(pNode) > 5 ) + return 999; + // check the fanouts + Abc_ObjForEachFanout( pNode, pFanout, i ) + if ( pFanout->fMarkA && pFanout->fMarkB == 0 ) // the fanout is in the TFI but not in the cone + return 999; + // the fanouts are in the TFI and inside the constructed cone + // return the number of fanins that will be on the boundary if this node is added + return (!Abc_ObjFanin0(pNode)->fMarkB) + (!Abc_ObjFanin1(pNode)->fMarkB); +} + + +/**Function************************************************************* + + Synopsis [Finds a fanin-limited, reconvergence-driven cut for the node.] Description [] @@ -59,53 +145,49 @@ static void Abc_NodeConeUnmark( Vec_Ptr_t * vVisited ); SeeAlso [] ***********************************************************************/ -Vec_Ptr_t * Abc_NodeFindCut( Abc_ManCut_t * p, Abc_Obj_t * pRoot ) +Vec_Ptr_t * Abc_NodeFindCut( Abc_ManCut_t * p, Abc_Obj_t * pRoot, bool fContain ) { Abc_Obj_t * pNode; int i; + assert( !Abc_ObjIsComplement(pRoot) ); + assert( Abc_ObjIsNode(pRoot) ); + // mark TFI using fMarkA Vec_PtrClear( p->vVisited ); - Abc_NodeConeMarkCollect_rec( pRoot, p->vVisited ); + Abc_NodesMarkCollect_rec( pRoot, p->vVisited ); - // start the reconvergence-driven node - Vec_PtrClear( p->vInsideNode ); + // start the cut Vec_PtrClear( p->vFaninsNode ); - Vec_PtrPush( p->vFaninsNode, pRoot ); + Vec_PtrPush( p->vFaninsNode, Abc_ObjFanin0(pRoot) ); + Vec_PtrPush( p->vFaninsNode, Abc_ObjFanin1(pRoot) ); pRoot->fMarkB = 1; + Abc_ObjFanin0(pRoot)->fMarkB = 1; + Abc_ObjFanin1(pRoot)->fMarkB = 1; - // compute reconvergence-driven node - while ( Abc_NodeFindCut_int( p->vInsideNode, p->vFaninsNode, p->nNodeSizeMax ) ); + // compute the cut + while ( Abc_NodeFindCut_int( p->vFaninsNode, p->nNodeSizeMax ) ); + assert( Vec_PtrSize(p->vFaninsNode) <= p->nNodeSizeMax ); - // compute reconvergence-driven cone - Vec_PtrClear( p->vInsideCone ); - Vec_PtrClear( p->vFaninsCone ); - if ( p->nConeSizeMax > p->nNodeSizeMax ) - { - // copy the node into the cone - Vec_PtrForEachEntry( p->vInsideNode, pNode, i ) - Vec_PtrPush( p->vInsideCone, pNode ); - Vec_PtrForEachEntry( p->vFaninsNode, pNode, i ) - Vec_PtrPush( p->vFaninsCone, pNode ); - // compute reconvergence-driven cone - while ( Abc_NodeFindCut_int( p->vInsideCone, p->vFaninsCone, p->nConeSizeMax ) ); - // unmark the nodes of the sets - Vec_PtrForEachEntry( p->vInsideCone, pNode, i ) - pNode->fMarkB = 0; - Vec_PtrForEachEntry( p->vFaninsCone, pNode, i ) - pNode->fMarkB = 0; - } - else + // return if containing cut is not requested + if ( !fContain ) { - // unmark the nodes of the sets - Vec_PtrForEachEntry( p->vInsideNode, pNode, i ) - pNode->fMarkB = 0; - Vec_PtrForEachEntry( p->vFaninsNode, pNode, i ) - pNode->fMarkB = 0; + // unmark TFI using fMarkA and fMarkB + Abc_NodesUnmarkBoth( p->vVisited ); + return p->vFaninsNode; } - // unmark TFI using fMarkA - Abc_NodeConeUnmark( p->vVisited ); + // compute the containing cut + assert( p->nNodeSizeMax < p->nConeSizeMax ); + // copy the current boundary + Vec_PtrClear( p->vFaninsCone ); + Vec_PtrForEachEntry( p->vFaninsNode, pNode, i ) + Vec_PtrPush( p->vFaninsCone, pNode ); + // compute the containing cut + while ( Abc_NodeFindCut_int( p->vFaninsCone, p->nConeSizeMax ) ); + assert( Vec_PtrSize(p->vFaninsCone) <= p->nConeSizeMax ); + // unmark TFI using fMarkA and fMarkB + Abc_NodesUnmarkBoth( p->vVisited ); return p->vFaninsNode; } @@ -120,20 +202,37 @@ Vec_Ptr_t * Abc_NodeFindCut( Abc_ManCut_t * p, Abc_Obj_t * pRoot ) SeeAlso [] ***********************************************************************/ -int Abc_NodeFindCut_int( Vec_Ptr_t * vInside, Vec_Ptr_t * vFanins, int nSizeLimit ) +int Abc_NodeFindCut_int( Vec_Ptr_t * vFanins, int nSizeLimit ) { Abc_Obj_t * pNode, * pFaninBest, * pNext; int CostBest, CostCur, i; +// int fFlagProb = (rand() & 1); + int fFlagProb = 1; // find the best fanin CostBest = 100; pFaninBest = NULL; - Vec_PtrForEachEntry( vFanins, pNode, i ) + if ( fFlagProb ) + { + Vec_PtrForEachEntry( vFanins, pNode, i ) + { + CostCur = Abc_NodeGetFaninCost( pNode ); + if ( CostBest > CostCur ) + { + CostBest = CostCur; + pFaninBest = pNode; + } + } + } + else { - CostCur = Abc_NodeGetFaninCost( pNode ); - if ( CostBest > CostCur ) + Vec_PtrForEachEntry( vFanins, pNode, i ) { - CostBest = CostCur; - pFaninBest = pNode; + CostCur = Abc_NodeGetFaninCost( pNode ); + if ( CostBest >= CostCur ) + { + CostBest = CostCur; + pFaninBest = pNode; + } } } if ( pFaninBest == NULL ) @@ -144,8 +243,6 @@ int Abc_NodeFindCut_int( Vec_Ptr_t * vInside, Vec_Ptr_t * vFanins, int nSizeLimi assert( Abc_ObjIsNode(pFaninBest) ); // remove the node from the array Vec_PtrRemove( vFanins, pFaninBest ); - // add the node to the set - Vec_PtrPush( vInside, pFaninBest ); // add the left child to the fanins pNext = Abc_ObjFanin0(pFaninBest); if ( !pNext->fMarkB ) @@ -167,36 +264,6 @@ int Abc_NodeFindCut_int( Vec_Ptr_t * vInside, Vec_Ptr_t * vFanins, int nSizeLimi /**Function************************************************************* - Synopsis [Evaluate the fanin cost.] - - Description [Returns the number of fanins that will be brought in. - Returns large number if the node cannot be added.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NodeGetFaninCost( Abc_Obj_t * pNode ) -{ - Abc_Obj_t * pFanout; - int i; - assert( pNode->fMarkA == 1 ); // this node is in the TFI - assert( pNode->fMarkB == 1 ); // this node is in the constructed cone - // check the PI node - if ( !Abc_ObjIsNode(pNode) ) - return 999; - // check the fanouts - Abc_ObjForEachFanout( pNode, pFanout, i ) - if ( pFanout->fMarkA && pFanout->fMarkB == 0 ) // in the cone but not in the set - return 999; - // the fanouts are in the TFI and inside the constructed cone - // return the number of fanins that will be on the boundary if this node is added - return (!Abc_ObjFanin0(pNode)->fMarkB) + (!Abc_ObjFanin1(pNode)->fMarkB); -} - -/**Function************************************************************* - Synopsis [Marks the TFI cone.] Description [] @@ -206,42 +273,25 @@ int Abc_NodeGetFaninCost( Abc_Obj_t * pNode ) SeeAlso [] ***********************************************************************/ -void Abc_NodeConeMarkCollect_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vVisited ) +void Abc_NodesMarkCollect_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vVisited ) { if ( pNode->fMarkA == 1 ) return; // visit transitive fanin if ( Abc_ObjIsNode(pNode) ) { - Abc_NodeConeMarkCollect_rec( Abc_ObjFanin0(pNode), vVisited ); - Abc_NodeConeMarkCollect_rec( Abc_ObjFanin1(pNode), vVisited ); + Abc_NodesMarkCollect_rec( Abc_ObjFanin0(pNode), vVisited ); + Abc_NodesMarkCollect_rec( Abc_ObjFanin1(pNode), vVisited ); } assert( pNode->fMarkA == 0 ); pNode->fMarkA = 1; Vec_PtrPush( vVisited, pNode ); } -/**Function************************************************************* - - Synopsis [Unmarks the TFI cone.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NodeConeMark( Vec_Ptr_t * vVisited ) -{ - int i; - for ( i = 0; i < vVisited->nSize; i++ ) - ((Abc_Obj_t *)vVisited->pArray)->fMarkA = 1; -} /**Function************************************************************* - Synopsis [Unmarks the TFI cone.] + Synopsis [Returns BDD representing the logic function of the cone.] Description [] @@ -250,17 +300,40 @@ void Abc_NodeConeMark( Vec_Ptr_t * vVisited ) SeeAlso [] ***********************************************************************/ -void Abc_NodeConeUnmark( Vec_Ptr_t * vVisited ) +DdNode * Abc_NodeConeBdd( DdManager * dd, DdNode ** pbVars, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, Vec_Ptr_t * vVisited ) { + DdNode * bFunc0, * bFunc1, * bFunc; int i; - for ( i = 0; i < vVisited->nSize; i++ ) - ((Abc_Obj_t *)vVisited->pArray)->fMarkA = 0; + // mark the fanins of the cone + Abc_NodesMark( vFanins ); + // collect the nodes in the DFS order + Vec_PtrClear( vVisited ); + Abc_NodesMarkCollect_rec( pNode, vVisited ); + // unmark both sets + Abc_NodesUnmark( vFanins ); + Abc_NodesUnmark( vVisited ); + // set the elementary BDDs + Vec_PtrForEachEntry( vFanins, pNode, i ) + pNode->pCopy = (Abc_Obj_t *)pbVars[i]; + // compute the BDDs for the collected nodes + Vec_PtrForEachEntry( vVisited, pNode, i ) + { + bFunc0 = Cudd_NotCond( Abc_ObjFanin0(pNode)->pCopy, Abc_ObjFaninC0(pNode) ); + bFunc1 = Cudd_NotCond( Abc_ObjFanin1(pNode)->pCopy, Abc_ObjFaninC1(pNode) ); + bFunc = Cudd_bddAnd( dd, bFunc0, bFunc1 ); Cudd_Ref( bFunc ); + pNode->pCopy = (Abc_Obj_t *)bFunc; + } + Cudd_Ref( bFunc ); + // dereference the intermediate ones + Vec_PtrForEachEntry( vVisited, pNode, i ) + Cudd_RecursiveDeref( dd, (DdNode *)pNode->pCopy ); + Cudd_Deref( bFunc ); + return bFunc; } - /**Function************************************************************* - Synopsis [Returns BDD representing the logic function of the cone.] + Synopsis [Returns BDD representing the transition relation of the cone.] Description [] @@ -269,21 +342,23 @@ void Abc_NodeConeUnmark( Vec_Ptr_t * vVisited ) SeeAlso [] ***********************************************************************/ -DdNode * Abc_NodeConeBdd( DdManager * dd, DdNode ** pbVars, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, Vec_Ptr_t * vVisited ) +DdNode * Abc_NodeConeDcs( DdManager * dd, DdNode ** pbVarsX, DdNode ** pbVarsY, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots, Vec_Ptr_t * vVisited ) { - DdNode * bFunc0, * bFunc1, * bFunc; + DdNode * bFunc0, * bFunc1, * bFunc, * bTrans, * bTemp, * bCube, * bResult; + Abc_Obj_t * pNode; int i; // mark the fanins of the cone - Abc_NodeConeMark( vFanins ); + Abc_NodesMark( vLeaves ); // collect the nodes in the DFS order Vec_PtrClear( vVisited ); - Abc_NodeConeMarkCollect_rec( pNode, vVisited ); + Vec_PtrForEachEntry( vRoots, pNode, i ) + Abc_NodesMarkCollect_rec( pNode, vVisited ); // unmark both sets - Abc_NodeConeUnmark( vFanins ); - Abc_NodeConeUnmark( vVisited ); + Abc_NodesUnmark( vLeaves ); + Abc_NodesUnmark( vVisited ); // set the elementary BDDs - Vec_PtrForEachEntry( vFanins, pNode, i ) - pNode->pCopy = (Abc_Obj_t *)pbVars[i]; + Vec_PtrForEachEntry( vLeaves, pNode, i ) + pNode->pCopy = (Abc_Obj_t *)pbVarsX[i]; // compute the BDDs for the collected nodes Vec_PtrForEachEntry( vVisited, pNode, i ) { @@ -292,14 +367,28 @@ DdNode * Abc_NodeConeBdd( DdManager * dd, DdNode ** pbVars, Abc_Obj_t * pNode, V bFunc = Cudd_bddAnd( dd, bFunc0, bFunc1 ); Cudd_Ref( bFunc ); pNode->pCopy = (Abc_Obj_t *)bFunc; } - Cudd_Ref( bFunc ); + // compute the transition relation of the cone + bTrans = b1; Cudd_Ref( bTrans ); + Vec_PtrForEachEntry( vRoots, pNode, i ) + { + bFunc = Cudd_bddXnor( dd, (DdNode *)pNode->pCopy, pbVarsY[i] ); Cudd_Ref( bFunc ); + bTrans = Cudd_bddAnd( dd, bTemp = bTrans, bFunc ); Cudd_Ref( bTrans ); + Cudd_RecursiveDeref( dd, bTemp ); + Cudd_RecursiveDeref( dd, bFunc ); + } // dereference the intermediate ones Vec_PtrForEachEntry( vVisited, pNode, i ) Cudd_RecursiveDeref( dd, (DdNode *)pNode->pCopy ); - Cudd_Deref( bFunc ); - return bFunc; + // compute don't-cares + bCube = Extra_bddComputeRangeCube( dd, vRoots->nSize, vRoots->nSize + vLeaves->nSize ); Cudd_Ref( bCube ); + bResult = Cudd_bddExistAbstract( dd, bTrans, bCube ); Cudd_Ref( bResult ); + bResult = Cudd_Not( bResult ); + Cudd_RecursiveDeref( dd, bCube ); + Cudd_RecursiveDeref( dd, bTrans ); + Cudd_Deref( bResult ); + return bResult; } - + /**Function************************************************************* Synopsis [Starts the resynthesis manager.] @@ -317,9 +406,7 @@ Abc_ManCut_t * Abc_NtkManCutStart( int nNodeSizeMax, int nConeSizeMax ) p = ALLOC( Abc_ManCut_t, 1 ); memset( p, 0, sizeof(Abc_ManCut_t) ); p->vFaninsNode = Vec_PtrAlloc( 100 ); - p->vInsideNode = Vec_PtrAlloc( 100 ); p->vFaninsCone = Vec_PtrAlloc( 100 ); - p->vInsideCone = Vec_PtrAlloc( 100 ); p->vVisited = Vec_PtrAlloc( 100 ); p->nNodeSizeMax = nNodeSizeMax; p->nConeSizeMax = nConeSizeMax; @@ -340,13 +427,26 @@ Abc_ManCut_t * Abc_NtkManCutStart( int nNodeSizeMax, int nConeSizeMax ) void Abc_NtkManCutStop( Abc_ManCut_t * p ) { Vec_PtrFree( p->vFaninsNode ); - Vec_PtrFree( p->vInsideNode ); Vec_PtrFree( p->vFaninsCone ); - Vec_PtrFree( p->vInsideCone ); Vec_PtrFree( p->vVisited ); free( p ); } +/**Function************************************************************* + + Synopsis [Returns the leaves of the cone.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * Abc_NtkManCutReadLeaves( Abc_ManCut_t * p ) +{ + return p->vFaninsCone; +} diff --git a/src/base/abc/abcRefactor.c b/src/base/abc/abcRefactor.c index b60b0969..2667cba5 100644 --- a/src/base/abc/abcRefactor.c +++ b/src/base/abc/abcRefactor.c @@ -29,25 +29,37 @@ typedef struct Abc_ManRef_t_ Abc_ManRef_t; struct Abc_ManRef_t_ { // user specified parameters - int nNodeSizeMax; // the limit on the size of the supernode - int nConeSizeMax; // the limit on the size of the containing cone - int fVerbose; // the verbosity flag - // internal parameters - DdManager * dd; // the BDD manager - Vec_Int_t * vReqTimes; // required times for each node - Vec_Str_t * vCube; // temporary - Vec_Int_t * vForm; // temporary - Vec_Int_t * vLevNums; // temporary - Vec_Ptr_t * vVisited; // temporary + int nNodeSizeMax; // the limit on the size of the supernode + int nConeSizeMax; // the limit on the size of the containing cone + int fVerbose; // the verbosity flag + // internal data structures + DdManager * dd; // the BDD manager + Vec_Int_t * vReqTimes; // required times for each node + Vec_Str_t * vCube; // temporary + Vec_Int_t * vForm; // temporary + Vec_Int_t * vLevNums; // temporary + Vec_Ptr_t * vVisited; // temporary + Vec_Ptr_t * vLeaves; // temporary + // node statistics + int nLastGain; + int nNodesConsidered; + int nNodesRefactored; + int nNodesGained; // runtime statistics - int time1; - int time2; - int time3; + int timeCut; + int timeBdd; + int timeDcs; + int timeSop; + int timeFact; + int timeRes; + int timeNtk; + int timeTotal; }; - -static Abc_ManRef_t * Abc_NtkManRefStart( int nNodeSizeMax, int nConeSizeMax, int fVerbose ); + +static void Abc_NtkManRefPrintStats( Abc_ManRef_t * p ); +static Abc_ManRef_t * Abc_NtkManRefStart( int nNodeSizeMax, int nConeSizeMax, bool fUseDcs, bool fVerbose ); static void Abc_NtkManRefStop( Abc_ManRef_t * p ); -static Vec_Int_t * Abc_NodeRefactor( Abc_ManRef_t * p, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins ); +static Vec_Int_t * Abc_NodeRefactor( Abc_ManRef_t * p, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, bool fUseZeros, bool fUseDcs, bool fVerbose ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// @@ -58,9 +70,10 @@ static Vec_Int_t * Abc_NodeRefactor( Abc_ManRef_t * p, Abc_Obj_t * pNode, Vec Synopsis [Performs incremental resynthesis of the AIG.] Description [Starting from each node, computes a reconvergence-driven cut, - derives BDD of the cut function, constructs ISOP, factors the cover, - and replaces the current implementation of the MFFC of the cut by the - new factored form if the number of AIG nodes is reduced. Returns the + derives BDD of the cut function, constructs ISOP, factors the ISOP, + and replaces the current implementation of the MFFC of the node by the + new factored form, if the number of AIG nodes is reduced and the total + number of levels of the AIG network is not increated. Returns the number of AIG nodes saved.] SideEffects [] @@ -68,7 +81,7 @@ static Vec_Int_t * Abc_NodeRefactor( Abc_ManRef_t * p, Abc_Obj_t * pNode, Vec SeeAlso [] ***********************************************************************/ -int Abc_NtkRefactor( Abc_Ntk_t * pNtk, int nNodeSizeMax, int nConeSizeMax, bool fUseDcs, bool fVerbose ) +int Abc_NtkRefactor( Abc_Ntk_t * pNtk, int nNodeSizeMax, int nConeSizeMax, bool fUseZeros, bool fUseDcs, bool fVerbose ) { int fCheck = 1; ProgressBar * pProgress; @@ -78,11 +91,13 @@ int Abc_NtkRefactor( Abc_Ntk_t * pNtk, int nNodeSizeMax, int nConeSizeMax, bool Vec_Int_t * vForm; Abc_Obj_t * pNode; int i, nNodes; + int clk, clkStart = clock(); assert( Abc_NtkIsAig(pNtk) ); // start the managers pManCut = Abc_NtkManCutStart( nNodeSizeMax, nConeSizeMax ); - pManRef = Abc_NtkManRefStart( nNodeSizeMax, nConeSizeMax, fVerbose ); + pManRef = Abc_NtkManRefStart( nNodeSizeMax, nConeSizeMax, fUseDcs, fVerbose ); + pManRef->vLeaves = Abc_NtkManCutReadLeaves( pManCut ); pManRef->vReqTimes = Abc_NtkGetRequiredLevels( pNtk ); // resynthesize each node once @@ -90,27 +105,42 @@ int Abc_NtkRefactor( Abc_Ntk_t * pNtk, int nNodeSizeMax, int nConeSizeMax, bool pProgress = Extra_ProgressBarStart( stdout, nNodes ); Abc_NtkForEachNode( pNtk, pNode, i ) { - Extra_ProgressBarUpdate( pProgress, nNodes, NULL ); + Extra_ProgressBarUpdate( pProgress, i, NULL ); + // stop if all nodes have been tried once + if ( i >= nNodes ) + break; + // skip the constant node + if ( Abc_NodeIsConst(pNode) ) + continue; // compute a reconvergence-driven cut - vFanins = Abc_NodeFindCut( pManCut, pNode ); +clk = clock(); + vFanins = Abc_NodeFindCut( pManCut, pNode, fUseDcs ); +pManRef->timeCut += clock() - clk; // evaluate this cut - vForm = Abc_NodeRefactor( pManRef, pNode, vFanins ); - // if acceptable replacement found, update the graph - if ( vForm ) - Abc_NodeUpdate( pNode, vFanins, vForm, 0 ); - // check the improvement - if ( i == nNodes ) - break; +clk = clock(); + vForm = Abc_NodeRefactor( pManRef, pNode, vFanins, fUseZeros, fUseDcs, fVerbose ); +pManRef->timeRes += clock() - clk; + if ( vForm == NULL ) + continue; + // acceptable replacement found, update the graph +clk = clock(); + Abc_NodeUpdate( pNode, vFanins, vForm, pManRef->nLastGain ); +pManRef->timeNtk += clock() - clk; + Vec_IntFree( vForm ); } Extra_ProgressBarStop( pProgress ); +pManRef->timeTotal = clock() - clkStart; + // print statistics of the manager + if ( fVerbose ) + Abc_NtkManRefPrintStats( pManRef ); // delete the managers Abc_NtkManCutStop( pManCut ); Abc_NtkManRefStop( pManRef ); // check if ( fCheck && !Abc_NtkCheck( pNtk ) ) { - printf( "Abc_NtkRewrite: The network check has failed.\n" ); + printf( "Abc_NtkRefactor: The network check has failed.\n" ); return 0; } return 1; @@ -127,32 +157,120 @@ int Abc_NtkRefactor( Abc_Ntk_t * pNtk, int nNodeSizeMax, int nConeSizeMax, bool SeeAlso [] ***********************************************************************/ -Vec_Int_t * Abc_NodeRefactor( Abc_ManRef_t * p, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins ) +Vec_Int_t * Abc_NodeRefactor( Abc_ManRef_t * p, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, bool fUseZeros, bool fUseDcs, bool fVerbose ) { + int fVeryVerbose = 0; + Abc_Obj_t * pFanin; Vec_Int_t * vForm; - DdNode * bFuncNode; - int nNodesSaved, RetValue; + DdNode * bNodeFunc, * bNodeDc, * bNodeOn, * bNodeOnDc; char * pSop; + int nBddNodes, nFtNodes, nNodesSaved, nNodesAdded; + int i, clk; + + p->nNodesConsidered++; - // get the cover - bFuncNode = Abc_NodeConeBdd( p->dd, p->dd->vars, pNode, vFanins, p->vVisited ); Cudd_Ref( bFuncNode ); - pSop = Abc_ConvertBddToSop( NULL, p->dd, bFuncNode, bFuncNode, vFanins->nSize, p->vCube, -1 ); - Cudd_RecursiveDeref( p->dd, bFuncNode ); - // derive the factored form + // get the function of the cut +clk = clock(); + bNodeFunc = Abc_NodeConeBdd( p->dd, p->dd->vars, pNode, vFanins, p->vVisited ); Cudd_Ref( bNodeFunc ); +p->timeBdd += clock() - clk; + nBddNodes = Cudd_DagSize(bNodeFunc); + + // if don't-care are used, transform the function into ISOP + if ( fUseDcs ) + { + int nMints, nMintsDc; + +clk = clock(); + // get the don't-cares + bNodeDc = Abc_NodeConeDcs( p->dd, p->dd->vars + vFanins->nSize, p->dd->vars, p->vLeaves, vFanins, p->vVisited ); Cudd_Ref( bNodeDc ); + + nMints = (1 << vFanins->nSize); + nMintsDc = (int)Cudd_CountMinterm( p->dd, bNodeDc, vFanins->nSize ); + printf( "Percentage of minterms = %5.2f.\n", 100.0 * nMintsDc / nMints ); + + // get the ISF + bNodeOn = Cudd_bddAnd( p->dd, bNodeFunc, Cudd_Not(bNodeDc) ); Cudd_Ref( bNodeOn ); + bNodeOnDc = Cudd_bddOr ( p->dd, bNodeFunc, bNodeDc ); Cudd_Ref( bNodeOnDc ); + Cudd_RecursiveDeref( p->dd, bNodeFunc ); + Cudd_RecursiveDeref( p->dd, bNodeDc ); + // get the ISOP + bNodeFunc = Cudd_bddIsop( p->dd, bNodeOn, bNodeOnDc ); Cudd_Ref( bNodeFunc ); + Cudd_RecursiveDeref( p->dd, bNodeOn ); + Cudd_RecursiveDeref( p->dd, bNodeOnDc ); +p->timeDcs += clock() - clk; + } + +//Extra_bddPrint( p->dd, bNodeFunc ); printf( "\n" ); + // always accept the case of constant node + if ( Cudd_IsConstant(bNodeFunc) ) + { + p->nNodesGained += Abc_NodeMffcSize( pNode ); + p->nNodesRefactored++; + // get the costant node + pFanin = Abc_ObjNotCond( Abc_AigConst1(pNode->pNtk->pManFunc), Cudd_IsComplement(bNodeFunc) ); + Abc_AigReplace( pNode->pNtk->pManFunc, pNode, pFanin ); + Cudd_RecursiveDeref( p->dd, bNodeFunc ); + return NULL; + } + + // get the SOP of the cut +clk = clock(); + pSop = Abc_ConvertBddToSop( NULL, p->dd, bNodeFunc, bNodeFunc, vFanins->nSize, p->vCube, -1 ); +p->timeSop += clock() - clk; + Cudd_RecursiveDeref( p->dd, bNodeFunc ); + + // get the factored form +clk = clock(); vForm = Ft_Factor( pSop ); +p->timeFact += clock() - clk; + nFtNodes = Ft_FactorGetNumNodes( vForm ); free( pSop ); +//Ft_FactorPrint( stdout, vForm, NULL, NULL ); - // label MFFC with current ID + // mark the fanin boundary + // (can mark only essential fanins, belonging to bNodeFunc!!!) + Vec_PtrForEachEntry( vFanins, pFanin, i ) + pFanin->vFanouts.nSize++; + + // label MFFC with current traversal ID + Abc_NtkIncrementTravId( pNode->pNtk ); nNodesSaved = Abc_NodeMffcLabel( pNode ); - // detect how many unlabeled nodes will be reused - RetValue = Abc_NodeStrashDecCount( pNode->pNtk->pManFunc, vFanins, vForm, + + // unmark the fanin boundary + Vec_PtrForEachEntry( vFanins, pFanin, i ) + pFanin->vFanouts.nSize--; + + // detect how many new nodes will be added (while taking into account reused nodes) + nNodesAdded = Abc_NodeStrashDecCount( pNode->pNtk->pManFunc, pNode, vFanins, vForm, p->vLevNums, nNodesSaved, Vec_IntEntry( p->vReqTimes, pNode->Id ) ); - if ( RetValue >= 0 ) - return vForm; - Vec_IntFree( vForm ); + // quit if there is no improvement + if ( nNodesAdded == -1 || nNodesAdded == nNodesSaved && !fUseZeros ) + { + Vec_IntFree( vForm ); + return NULL; + } + + // compute the total gain in the number of nodes + p->nLastGain = nNodesSaved - nNodesAdded; + p->nNodesGained += p->nLastGain; + p->nNodesRefactored++; + + // report the progress + if ( fVeryVerbose ) + { + printf( "Node %6s : ", Abc_ObjName(pNode) ); + printf( "Cone = %2d. ", vFanins->nSize ); + printf( "BDD = %2d. ", nBddNodes ); + printf( "FF = %2d. ", nFtNodes ); + printf( "MFFC = %2d. ", nNodesSaved ); + printf( "Add = %2d. ", nNodesAdded ); + printf( "GAIN = %2d. ", p->nLastGain ); + printf( "\n" ); + } return vForm; } + /**Function************************************************************* Synopsis [Starts the resynthesis manager.] @@ -164,19 +282,22 @@ Vec_Int_t * Abc_NodeRefactor( Abc_ManRef_t * p, Abc_Obj_t * pNode, Vec_Ptr_t * v SeeAlso [] ***********************************************************************/ -Abc_ManRef_t * Abc_NtkManRefStart( int nNodeSizeMax, int nConeSizeMax, int fVerbose ) +Abc_ManRef_t * Abc_NtkManRefStart( int nNodeSizeMax, int nConeSizeMax, bool fUseDcs, bool fVerbose ) { Abc_ManRef_t * p; p = ALLOC( Abc_ManRef_t, 1 ); memset( p, 0, sizeof(Abc_ManRef_t) ); - p->vCube = Vec_StrAlloc( 100 ); - p->vLevNums = Vec_IntAlloc( 100 ); - p->vVisited = Vec_PtrAlloc( 100 ); + p->vCube = Vec_StrAlloc( 100 ); + p->vLevNums = Vec_IntAlloc( 100 ); + p->vVisited = Vec_PtrAlloc( 100 ); p->nNodeSizeMax = nNodeSizeMax; p->nConeSizeMax = nConeSizeMax; p->fVerbose = fVerbose; // start the BDD manager - p->dd = Cudd_Init( p->nNodeSizeMax + p->nConeSizeMax, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 ); + if ( fUseDcs ) + p->dd = Cudd_Init( p->nNodeSizeMax + p->nConeSizeMax, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 ); + else + p->dd = Cudd_Init( p->nNodeSizeMax, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 ); Cudd_zddVarsFromBddVars( p->dd, 2 ); return p; } @@ -202,6 +323,34 @@ void Abc_NtkManRefStop( Abc_ManRef_t * p ) free( p ); } +/**Function************************************************************* + + Synopsis [Stops the resynthesis manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkManRefPrintStats( Abc_ManRef_t * p ) +{ + printf( "Refactoring statistics:\n" ); + printf( "Nodes considered = %6d.\n", p->nNodesConsidered ); + printf( "Nodes refactored = %6d.\n", p->nNodesRefactored ); + printf( "Calculated gain = %6d.\n", p->nNodesGained ); + PRT( "Cuts ", p->timeCut ); + PRT( "Resynthesis", p->timeRes ); + PRT( " BDD ", p->timeBdd ); + PRT( " DCs ", p->timeDcs ); + PRT( " SOP ", p->timeSop ); + PRT( " FF ", p->timeFact ); + PRT( "AIG update ", p->timeNtk ); + PRT( "TOTAL ", p->timeTotal ); +} + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/base/abc/abcRefs.c b/src/base/abc/abcRefs.c index c3561028..ea7aeff4 100644 --- a/src/base/abc/abcRefs.c +++ b/src/base/abc/abcRefs.c @@ -24,7 +24,7 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static int Abc_NodeRefDeref( Abc_Obj_t * pNode, bool fReference, bool fLabel ); +static int Abc_NodeRefDeref( Abc_Obj_t * pNode, bool fReference, bool fLabel, Vec_Ptr_t * vNodes ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// @@ -48,8 +48,8 @@ int Abc_NodeMffcSize( Abc_Obj_t * pNode ) assert( Abc_ObjIsNode( pNode ) ); if ( Abc_ObjFaninNum(pNode) == 0 ) return 0; - nConeSize1 = Abc_NodeRefDeref( pNode, 0, 0 ); // dereference - nConeSize2 = Abc_NodeRefDeref( pNode, 1, 0 ); // reference + nConeSize1 = Abc_NodeRefDeref( pNode, 0, 0, NULL ); // dereference + nConeSize2 = Abc_NodeRefDeref( pNode, 1, 0, NULL ); // reference assert( nConeSize1 == nConeSize2 ); assert( nConeSize1 > 0 ); return nConeSize1; @@ -57,7 +57,7 @@ int Abc_NodeMffcSize( Abc_Obj_t * pNode ) /**Function************************************************************* - Synopsis [Lavels MFFC with the current traversal ID.] + Synopsis [Labels MFFC with the current traversal ID.] Description [] @@ -73,8 +73,8 @@ int Abc_NodeMffcLabel( Abc_Obj_t * pNode ) assert( Abc_ObjIsNode( pNode ) ); if ( Abc_ObjFaninNum(pNode) == 0 ) return 0; - nConeSize1 = Abc_NodeRefDeref( pNode, 0, 0 ); // dereference - nConeSize2 = Abc_NodeRefDeref( pNode, 1, 1 ); // reference + nConeSize1 = Abc_NodeRefDeref( pNode, 0, 1, NULL ); // dereference + nConeSize2 = Abc_NodeRefDeref( pNode, 1, 0, NULL ); // reference assert( nConeSize1 == nConeSize2 ); assert( nConeSize1 > 0 ); return nConeSize1; @@ -82,6 +82,33 @@ int Abc_NodeMffcLabel( Abc_Obj_t * pNode ) /**Function************************************************************* + Synopsis [Collects the nodes in MFFC in the topological order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * Abc_NodeMffcCollect( Abc_Obj_t * pNode ) +{ + Vec_Ptr_t * vNodes; + int nConeSize1, nConeSize2; + assert( !Abc_ObjIsComplement( pNode ) ); + assert( Abc_ObjIsNode( pNode ) ); + vNodes = Vec_PtrAlloc( 8 ); + if ( Abc_ObjFaninNum(pNode) == 0 ) + return vNodes; + nConeSize1 = Abc_NodeRefDeref( pNode, 0, 0, vNodes ); // dereference + nConeSize2 = Abc_NodeRefDeref( pNode, 1, 0, NULL ); // reference + assert( nConeSize1 == nConeSize2 ); + assert( nConeSize1 > 0 ); + return vNodes; +} + +/**Function************************************************************* + Synopsis [References/references the node and returns MFFC size.] Description [] @@ -91,39 +118,48 @@ int Abc_NodeMffcLabel( Abc_Obj_t * pNode ) SeeAlso [] ***********************************************************************/ -int Abc_NodeRefDeref( Abc_Obj_t * pNode, bool fReference, bool fLabel ) +int Abc_NodeRefDeref( Abc_Obj_t * pNode, bool fReference, bool fLabel, Vec_Ptr_t * vNodes ) { Abc_Obj_t * pNode0, * pNode1; int Counter; + // label visited nodes if ( fLabel ) + { Abc_NodeSetTravIdCurrent( pNode ); +//printf( "Labeling " ); Abc_AigPrintNode( pNode ); + } + // collect visited nodes + if ( vNodes ) + Vec_PtrPush( vNodes, pNode ); + // skip the CI if ( Abc_ObjIsCi(pNode) ) return 0; + // process the internal node pNode0 = Abc_ObjFanin( pNode, 0 ); pNode1 = Abc_ObjFanin( pNode, 1 ); Counter = 1; if ( fReference ) { if ( pNode0->vFanouts.nSize++ == 0 ) - Counter += Abc_NodeRefDeref( pNode0, fReference, fLabel ); + Counter += Abc_NodeRefDeref( pNode0, fReference, fLabel, vNodes ); if ( pNode1->vFanouts.nSize++ == 0 ) - Counter += Abc_NodeRefDeref( pNode1, fReference, fLabel ); + Counter += Abc_NodeRefDeref( pNode1, fReference, fLabel, vNodes ); } else { assert( pNode0->vFanouts.nSize > 0 ); assert( pNode1->vFanouts.nSize > 0 ); if ( --pNode0->vFanouts.nSize == 0 ) - Counter += Abc_NodeRefDeref( pNode0, fReference, fLabel ); + Counter += Abc_NodeRefDeref( pNode0, fReference, fLabel, vNodes ); if ( --pNode1->vFanouts.nSize == 0 ) - Counter += Abc_NodeRefDeref( pNode1, fReference, fLabel ); + Counter += Abc_NodeRefDeref( pNode1, fReference, fLabel, vNodes ); } return Counter; } /**Function************************************************************* - Synopsis [Replaces MFFC of the node by the new factored.] + Synopsis [Replaces MFFC of the node by the new factored form.] Description [] @@ -138,7 +174,7 @@ void Abc_NodeUpdate( Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, Vec_Int_t * vForm, int nNodesNew, nNodesOld; nNodesOld = Abc_NtkNodeNum(pNode->pNtk); // create the new structure of nodes - assert( Vec_PtrSize(vFanins) < Vec_IntSize(vForm) ); + assert( vForm->nSize == 1 || Vec_PtrSize(vFanins) < Vec_IntSize(vForm) ); pNodeNew = Abc_NodeStrashDec( pNode->pNtk->pManFunc, vFanins, vForm ); // remove the old nodes Abc_AigReplace( pNode->pNtk->pManFunc, pNode, pNodeNew ); diff --git a/src/base/abc/abcRewrite.c b/src/base/abc/abcRewrite.c index 2c4c8c55..0cd56349 100644 --- a/src/base/abc/abcRewrite.c +++ b/src/base/abc/abcRewrite.c @@ -60,13 +60,16 @@ int Abc_NtkRewrite( Abc_Ntk_t * pNtk ) pProgress = Extra_ProgressBarStart( stdout, nNodes ); Abc_NtkForEachNode( pNtk, pNode, i ) { - Extra_ProgressBarUpdate( pProgress, nNodes, NULL ); + Extra_ProgressBarUpdate( pProgress, i, NULL ); + // stop if all nodes have been tried once + if ( i >= nNodes ) + break; + // skip the constant node + if ( Abc_NodeIsConst(pNode) ) + continue; // for each cut, try to resynthesize it if ( (nGain = Rwr_NodeRewrite( p, pNode )) >= 0 ) Abc_NodeUpdate( pNode, Rwr_ManReadFanins(p), Rwr_ManReadDecs(p), nGain ); - // check the improvement - if ( i == nNodes ) - break; } Extra_ProgressBarStop( pProgress ); // delete the manager diff --git a/src/base/abc/abcSop.c b/src/base/abc/abcSop.c index b72b48ee..b6972d58 100644 --- a/src/base/abc/abcSop.c +++ b/src/base/abc/abcSop.c @@ -355,6 +355,82 @@ int Abc_SopGetPhase( char * pSop ) /**Function************************************************************* + Synopsis [Returns the i-th literal of the cover.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_SopGetIthCareLit( char * pSop, int i ) +{ + char * pCube; + int nVars, c; + nVars = Abc_SopGetVarNum( pSop ); + for ( c = 0; ; c++ ) + { + // get the cube + pCube = pSop + c * (nVars + 3); + if ( *pCube == 0 ) + break; + // get the literal + if ( pCube[i] != '-' ) + return pCube[i] - '0'; + } + return -1; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SopComplement( char * pSop ) +{ + char * pCur; + for ( pCur = pSop; *pCur; pCur++ ) + if ( *pCur == '\n' ) + { + if ( *(pCur - 1) == '0' ) + *(pCur - 1) = '1'; + else if ( *(pCur - 1) == '1' ) + *(pCur - 1) = '0'; + else + assert( 0 ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +bool Abc_SopIsComplement( char * pSop ) +{ + char * pCur; + for ( pCur = pSop; *pCur; pCur++ ) + if ( *pCur == '\n' ) + return (int)(*(pCur - 1) == '0'); + assert( 0 ); + return 0; +} + +/**Function************************************************************* + Synopsis [Checks if the cover is constant 0.] Description [] @@ -481,61 +557,6 @@ bool Abc_SopIsOrType( char * pSop ) /**Function************************************************************* - Synopsis [Returns the i-th literal of the cover.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_SopGetIthCareLit( char * pSop, int i ) -{ - char * pCube; - int nVars, c; - nVars = Abc_SopGetVarNum( pSop ); - for ( c = 0; ; c++ ) - { - // get the cube - pCube = pSop + c * (nVars + 3); - if ( *pCube == 0 ) - break; - // get the literal - if ( pCube[i] != '-' ) - return pCube[i] - '0'; - } - return -1; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_SopComplement( char * pSop ) -{ - char * pCur; - for ( pCur = pSop; *pCur; pCur++ ) - if ( *pCur == '\n' ) - { - if ( *(pCur - 1) == '0' ) - *(pCur - 1) = '1'; - else if ( *(pCur - 1) == '1' ) - *(pCur - 1) = '0'; - else - assert( 0 ); - } -} - -/**Function************************************************************* - Synopsis [] Description [] diff --git a/src/base/abc/abcStrash.c b/src/base/abc/abcStrash.c index 403b5be3..1c4134d0 100644 --- a/src/base/abc/abcStrash.c +++ b/src/base/abc/abcStrash.c @@ -31,11 +31,6 @@ static void Abc_NtkStrashPerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, static Abc_Obj_t * Abc_NodeStrash( Abc_Aig_t * pMan, Abc_Obj_t * pNode ); static Abc_Obj_t * Abc_NodeStrashSop( Abc_Aig_t * pMan, Abc_Obj_t * pNode, char * pSop ); static Abc_Obj_t * Abc_NodeStrashFactor( Abc_Aig_t * pMan, Abc_Obj_t * pNode, char * pSop ); -static Abc_Obj_t * Abc_NodeStrashFactor2( Abc_Aig_t * pMan, Abc_Obj_t * pNode, char * pSop ); - -static void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate ); -static Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, bool fDuplicate ); -static Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, int fDuplicate ); extern char * Mio_GateReadSop( void * pGate ); @@ -47,7 +42,8 @@ extern char * Mio_GateReadSop( void * pGate ); Synopsis [Creates the strashed AIG network.] - Description [] + Description [Converts the logic network or the AIG into a + structurally hashed AIG.] SideEffects [] @@ -93,6 +89,53 @@ Abc_Ntk_t * Abc_NtkStrash( Abc_Ntk_t * pNtk, bool fAllNodes ) /**Function************************************************************* + Synopsis [Appends the second network to the first.] + + Description [Modifies the first network by adding the logic of the second. + Performs structural hashing while appending the networks. Does not add + the COs of the second. Does not change the second network. Returns 0 + if the appending failed, 1 otherise.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkAppend( Abc_Ntk_t * pNtk1, Abc_Ntk_t * pNtk2 ) +{ + int fCheck = 1; + Abc_Obj_t * pObj; + int i; + // the first network should be an AIG + assert( Abc_NtkIsAig(pNtk1) ); + assert( Abc_NtkIsLogic(pNtk2) || Abc_NtkIsAig(pNtk2) ); + if ( Abc_NtkIsLogicBdd(pNtk2) ) + { +// printf( "Converting node functions from BDD to SOP.\n" ); + Abc_NtkBddToSop(pNtk2); + } + // check that the networks have the same PIs + // reorder PIs of pNtk2 according to pNtk1 + if ( !Abc_NtkCompareSignals( pNtk1, pNtk2, 1 ) ) + return 0; + // perform strashing + Abc_NtkCleanCopy( pNtk2 ); + Abc_NtkForEachCi( pNtk2, pObj, i ) + pObj->pCopy = Abc_NtkCi(pNtk1, i); + // add pNtk2 to pNtk1 while strashing + Abc_NtkStrashPerform( pNtk2, pNtk1, 1 ); + // make sure that everything is okay + if ( fCheck && !Abc_NtkCheck( pNtk1 ) ) + { + printf( "Abc_NtkAppend: The network check has failed.\n" ); + return 0; + } + return 1; +} + + +/**Function************************************************************* + Synopsis [Prepares the network for strashing.] Description [] @@ -121,10 +164,7 @@ void Abc_NtkStrashPerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew, bool fAllNodes // strash the node pNodeNew = Abc_NodeStrash( pMan, pNode ); // get the old object - if ( Abc_NtkIsNetlist(pNtk) ) - pObj = Abc_ObjFanout0( pNode ); // the fanout net - else - pObj = vNodes->pArray[i]; // the node itself + pObj = Abc_ObjFanout0Ntk( pNode ); // make sure the node is not yet strashed assert( pObj->pCopy == NULL ); // mark the old object with the new AIG node @@ -180,7 +220,7 @@ Abc_Obj_t * Abc_NodeStrash( Abc_Aig_t * pMan, Abc_Obj_t * pNode ) // decide when to use factoring if ( fUseFactor && Abc_ObjFaninNum(pNode) > 2 && Abc_SopGetCubeNum(pSop) > 1 ) - return Abc_NodeStrashFactor2( pMan, pNode, pSop ); + return Abc_NodeStrashFactor( pMan, pNode, pSop ); return Abc_NodeStrashSop( pMan, pNode, pSop ); } @@ -222,8 +262,7 @@ Abc_Obj_t * Abc_NodeStrashSop( Abc_Aig_t * pMan, Abc_Obj_t * pNode, char * pSop pSum = Abc_AigOr( pMan, pSum, pAnd ); } // decide whether to complement the result - pCube = pSop; - if ( pCube[nFanins + 1] == '0' ) + if ( Abc_SopIsComplement(pSop) ) pSum = Abc_ObjNot(pSum); return pSum; } @@ -243,66 +282,6 @@ Abc_Obj_t * Abc_NodeStrashFactor( Abc_Aig_t * pMan, Abc_Obj_t * pRoot, char * pS { Vec_Int_t * vForm; Vec_Ptr_t * vAnds; - Abc_Obj_t * pAnd, * pAnd0, * pAnd1, * pFanin; - Ft_Node_t * pFtNode; - int i, nVars; - - // derive the factored form - vForm = Ft_Factor( pSop ); - - // sanity checks - nVars = Ft_FactorGetNumVars( vForm ); - assert( nVars >= 0 ); - assert( vForm->nSize > nVars ); - assert( nVars == Abc_ObjFaninNum(pRoot) ); - - // check for constant function - pFtNode = Ft_NodeRead( vForm, 0 ); - if ( pFtNode->fConst ) - { - Vec_IntFree( vForm ); - return Abc_ObjNotCond( Abc_AigConst1(pMan), pFtNode->fCompl ); - } - - // start the array of elementary variables - vAnds = Vec_PtrAlloc( 20 ); - Abc_ObjForEachFanin( pRoot, pFanin, i ) - Vec_PtrPush( vAnds, pFanin->pCopy ); - - // compute the function of other nodes - for ( i = nVars; i < vForm->nSize; i++ ) - { - pFtNode = Ft_NodeRead( vForm, i ); - pAnd0 = Abc_ObjNotCond( vAnds->pArray[pFtNode->iFanin0], pFtNode->fCompl0 ); - pAnd1 = Abc_ObjNotCond( vAnds->pArray[pFtNode->iFanin1], pFtNode->fCompl1 ); - pAnd = Abc_AigAnd( pMan, pAnd0, pAnd1 ); - Vec_PtrPush( vAnds, pAnd ); - } - assert( vForm->nSize = vAnds->nSize ); - Vec_PtrFree( vAnds ); - - // complement the result if necessary - pFtNode = Ft_NodeReadLast( vForm ); - pAnd = Abc_ObjNotCond( pAnd, pFtNode->fCompl ); - Vec_IntFree( vForm ); - return pAnd; -} - -/**Function************************************************************* - - Synopsis [Strashes one logic node using its SOP.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Obj_t * Abc_NodeStrashFactor2( Abc_Aig_t * pMan, Abc_Obj_t * pRoot, char * pSop ) -{ - Vec_Int_t * vForm; - Vec_Ptr_t * vAnds; Abc_Obj_t * pAnd, * pFanin; int i; // derive the factored form @@ -354,6 +333,7 @@ Abc_Obj_t * Abc_NodeStrashDec( Abc_Aig_t * pMan, Vec_Ptr_t * vFanins, Vec_Int_t pAnd1 = Abc_ObjNotCond( vFanins->pArray[pFtNode->iFanin1], pFtNode->fCompl1 ); pAnd = Abc_AigAnd( pMan, pAnd0, pAnd1 ); Vec_PtrPush( vFanins, pAnd ); +//printf( "Adding " ); Abc_AigPrintNode( pAnd ); } assert( vForm->nSize = vFanins->nSize ); @@ -367,24 +347,25 @@ Abc_Obj_t * Abc_NodeStrashDec( Abc_Aig_t * pMan, Vec_Ptr_t * vFanins, Vec_Int_t Synopsis [Counts the number of new nodes added when using this factored form,] - Description [Returns -1 if the number of nodes and levels exceeded the given limit.] + Description [Returns NodeMax + 1 if the number of nodes and levels exceeded + the given limit or the number of levels exceeded the maximum allowed level.] SideEffects [] SeeAlso [] ***********************************************************************/ -int Abc_NodeStrashDecCount( Abc_Aig_t * pMan, Vec_Ptr_t * vFanins, Vec_Int_t * vForm, Vec_Int_t * vLevels, int NodeMax, int LevelMax ) +int Abc_NodeStrashDecCount( Abc_Aig_t * pMan, Abc_Obj_t * pRoot, Vec_Ptr_t * vFanins, Vec_Int_t * vForm, Vec_Int_t * vLevels, int NodeMax, int LevelMax ) { - Abc_Obj_t * pAnd, * pAnd0, * pAnd1; + Abc_Obj_t * pAnd, * pAnd0, * pAnd1, * pTop; Ft_Node_t * pFtNode; - int i, nVars, Counter, LevelNew; + int i, nVars, LevelNew, LevelOld, Counter; // sanity checks nVars = Ft_FactorGetNumVars( vForm ); assert( nVars >= 0 ); assert( vForm->nSize > nVars ); - assert( nVars == vFanins->nSize ); + assert( nVars == vFanins->nSize ); // set the fanin number to nVars??? // check for constant function pFtNode = Ft_NodeRead( vForm, 0 ); @@ -401,275 +382,83 @@ int Abc_NodeStrashDecCount( Abc_Aig_t * pMan, Vec_Ptr_t * vFanins, Vec_Int_t * v for ( i = nVars; i < vForm->nSize; i++ ) { pFtNode = Ft_NodeRead( vForm, i ); - pAnd0 = Abc_ObjNotCond( Vec_PtrEntry(vFanins, pFtNode->iFanin0), pFtNode->fCompl0 ); - if ( pAnd0 ) + // check for buffer/inverter + if ( pFtNode->iFanin0 == pFtNode->iFanin1 ) + { + assert( vForm->nSize == nVars + 1 ); + pAnd = Vec_PtrEntry(vFanins, pFtNode->iFanin0); + pAnd = Abc_ObjNotCond( pAnd, pFtNode->fCompl ); + Vec_PtrPush( vFanins, pAnd ); + break; + } + + pAnd0 = Vec_PtrEntry(vFanins, pFtNode->iFanin0); + pAnd1 = Vec_PtrEntry(vFanins, pFtNode->iFanin1); + if ( pAnd0 && pAnd1 ) { - pAnd1 = Abc_ObjNotCond( Vec_PtrEntry(vFanins, pFtNode->iFanin1), pFtNode->fCompl1 ); - pAnd = pAnd1? Abc_AigAndLookup( pMan, pAnd0, pAnd1 ) : NULL; + pAnd0 = Abc_ObjNotCond( pAnd0, pFtNode->fCompl0 ); + pAnd1 = Abc_ObjNotCond( pAnd1, pFtNode->fCompl1 ); + pAnd = Abc_AigAndLookup( pMan, pAnd0, pAnd1 ); } else pAnd = NULL; // count the number of added nodes - if ( pAnd == NULL || Abc_NodeIsTravIdCurrent(pAnd) ) + if ( pAnd == NULL || Abc_NodeIsTravIdCurrent( Abc_ObjRegular(pAnd) ) ) { + if ( pAnd ) + { +//printf( "Reusing labeled " ); Abc_AigPrintNode( pAnd ); + } Counter++; if ( Counter > NodeMax ) + { + Vec_PtrShrink( vFanins, nVars ); return -1; + } + } + else + { +//printf( "Reusing " ); Abc_AigPrintNode( pAnd ); } + // count the number of new levels - LevelNew = 1 + ABC_MAX( Vec_IntEntry(vLevels, pFtNode->iFanin0), Vec_IntEntry(vLevels, pFtNode->iFanin1) ); - assert( pAnd == NULL || LevelNew == (int)Abc_ObjRegular(pAnd)->Level ); + if ( pAnd && Abc_ObjRegular(pAnd) == Abc_AigConst1(pMan) ) + LevelNew = 0; + else + LevelNew = 1 + ABC_MAX( Vec_IntEntry(vLevels, pFtNode->iFanin0), Vec_IntEntry(vLevels, pFtNode->iFanin1) ); + +// assert( pAnd == NULL || LevelNew == LevelOld ); + if ( pAnd ) + { + LevelOld = (int)Abc_ObjRegular(pAnd)->Level; + if ( LevelNew != LevelOld ) + { + int x = 0; + } + } + if ( LevelNew > LevelMax ) + { + Vec_PtrShrink( vFanins, nVars ); return -1; + } Vec_PtrPush( vFanins, pAnd ); Vec_IntPush( vLevels, LevelNew ); } assert( vForm->nSize = vFanins->nSize ); - return Counter; -} - -/**Function************************************************************* - - Synopsis [Appends the second network to the first.] - - Description [Modifies the first network by adding the logic of the second. - Does not add the COs of the second. Does not change the second network. - Returns 0 if the appending failed, 1 otherise.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkAppend( Abc_Ntk_t * pNtk1, Abc_Ntk_t * pNtk2 ) -{ - int fCheck = 1; - Abc_Obj_t * pObj; - int i; - // the first network should be an AIG - assert( Abc_NtkIsAig(pNtk1) ); - assert( Abc_NtkIsLogic(pNtk2) || Abc_NtkIsAig(pNtk2) ); - if ( Abc_NtkIsLogicBdd(pNtk2) ) - { -// printf( "Converting node functions from BDD to SOP.\n" ); - Abc_NtkBddToSop(pNtk2); - } - // check that the networks have the same PIs - // reorder PIs of pNtk2 according to pNtk1 - if ( !Abc_NtkCompareSignals( pNtk1, pNtk2, 1 ) ) - return 0; - // perform strashing - Abc_NtkCleanCopy( pNtk2 ); - Abc_NtkForEachCi( pNtk2, pObj, i ) - pObj->pCopy = Abc_NtkCi(pNtk1, i); - // add pNtk2 to pNtk1 while strashing - Abc_NtkStrashPerform( pNtk2, pNtk1, 1 ); - // make sure that everything is okay - if ( fCheck && !Abc_NtkCheck( pNtk1 ) ) - { - printf( "Abc_NtkAppend: The network check has failed.\n" ); - return 0; - } - return 1; -} - - - -/**Function************************************************************* - - Synopsis [Balances the AIG network.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Ntk_t * Abc_NtkBalance( Abc_Ntk_t * pNtk, bool fDuplicate ) -{ - int fCheck = 1; - Abc_Ntk_t * pNtkAig; - assert( Abc_NtkIsAig(pNtk) ); - // perform balancing - pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_AIG ); - Abc_NtkBalancePerform( pNtk, pNtkAig, fDuplicate ); - Abc_NtkFinalize( pNtk, pNtkAig ); - // make sure everything is okay - if ( fCheck && !Abc_NtkCheck( pNtkAig ) ) + // check if this is the same form + pTop = Vec_PtrEntryLast(vFanins); + if ( Abc_ObjRegular(pTop) == pRoot ) { - printf( "Abc_NtkBalance: The network check has failed.\n" ); - Abc_NtkDelete( pNtkAig ); - return NULL; - } - return pNtkAig; -} - -/**Function************************************************************* - - Synopsis [Balances the AIG network.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate ) -{ - int fCheck = 1; - ProgressBar * pProgress; - Abc_Obj_t * pNode, * pDriver; - int i; - - // copy the constant node - Abc_AigConst1(pNtk->pManFunc)->pCopy = Abc_AigConst1(pNtkAig->pManFunc); - // set the level of PIs of AIG according to the arrival times of the old network - Abc_NtkSetNodeLevelsArrival( pNtk ); - // perform balancing of POs - pProgress = Extra_ProgressBarStart( stdout, Abc_NtkCoNum(pNtk) ); - Abc_NtkForEachCo( pNtk, pNode, i ) - { - Extra_ProgressBarUpdate( pProgress, i, NULL ); - // strash the driver node - pDriver = Abc_ObjFanin0(pNode); - Abc_NodeBalance_rec( pNtkAig, pDriver, fDuplicate ); - } - Extra_ProgressBarStop( pProgress ); -} - -/**Function************************************************************* - - Synopsis [Rebalances the multi-input node rooted at pNodeOld.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, bool fDuplicate ) -{ - Abc_Aig_t * pMan = pNtkNew->pManFunc; - Abc_Obj_t * pNodeNew, * pNode1, * pNode2; - Vec_Ptr_t * vSuper; - int i; - assert( !Abc_ObjIsComplement(pNodeOld) ); - // return if the result if known - if ( pNodeOld->pCopy ) - return pNodeOld->pCopy; - assert( Abc_ObjIsNode(pNodeOld) ); - // get the implication supergate - vSuper = Abc_NodeBalanceCone( pNodeOld, fDuplicate ); - if ( vSuper->nSize == 0 ) - { // it means that the supergate contains two nodes in the opposite polarity - Vec_PtrFree( vSuper ); - pNodeOld->pCopy = Abc_ObjNot(Abc_AigConst1(pMan)); - return pNodeOld->pCopy; - } - // for each old node, derive the new well-balanced node - for ( i = 0; i < vSuper->nSize; i++ ) - { - pNodeNew = Abc_NodeBalance_rec( pNtkNew, Abc_ObjRegular(vSuper->pArray[i]), fDuplicate ); - vSuper->pArray[i] = Abc_ObjNotCond( pNodeNew, Abc_ObjIsComplement(vSuper->pArray[i]) ); - } - // sort the new nodes by level in the decreasing order - Vec_PtrSort( vSuper, Abc_NodeCompareLevelsDecrease ); - // balance the nodes - assert( vSuper->nSize > 1 ); - while ( vSuper->nSize > 1 ) - { - pNode1 = Vec_PtrPop(vSuper); - pNode2 = Vec_PtrPop(vSuper); - Abc_VecObjPushUniqueOrderByLevel( vSuper, Abc_AigAnd(pMan, pNode1, pNode2) ); - } - // make sure the balanced node is not assigned - assert( pNodeOld->pCopy == NULL ); - // mark the old node with the new node - pNodeOld->pCopy = vSuper->pArray[0]; - Vec_PtrFree( vSuper ); - return pNodeOld->pCopy; -} - - -/**Function************************************************************* - - Synopsis [Collects the nodes in the cone delimited by fMarkA==1.] - - Description [Returns -1 if the AND-cone has the same node in both polarities. - Returns 1 if the AND-cone has the same node in the same polarity. Returns 0 - if the AND-cone has no repeated nodes.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, bool fDuplicate ) -{ - int RetValue1, RetValue2, i; - // check if the node is visited - if ( Abc_ObjRegular(pNode)->fMarkB ) - { - // check if the node occurs in the same polarity - for ( i = 0; i < vSuper->nSize; i++ ) - if ( vSuper->pArray[i] == pNode ) - return 1; - // check if the node is present in the opposite polarity - for ( i = 0; i < vSuper->nSize; i++ ) - if ( vSuper->pArray[i] == Abc_ObjNot(pNode) ) - return -1; - assert( 0 ); - return 0; - } - // if the new node is complemented or a PI, another gate begins - if ( !fFirst && (Abc_ObjIsComplement(pNode) || !Abc_ObjIsNode(pNode) || !fDuplicate && (Abc_ObjFanoutNum(pNode) > 1)) ) - { - Vec_PtrPush( vSuper, pNode ); - Abc_ObjRegular(pNode)->fMarkB = 1; - return 0; - } - assert( !Abc_ObjIsComplement(pNode) ); - assert( Abc_ObjIsNode(pNode) ); - // go through the branches - RetValue1 = Abc_NodeBalanceCone_rec( Abc_ObjChild0(pNode), vSuper, 0, fDuplicate ); - RetValue2 = Abc_NodeBalanceCone_rec( Abc_ObjChild1(pNode), vSuper, 0, fDuplicate ); - if ( RetValue1 == -1 || RetValue2 == -1 ) + assert( !Abc_ObjIsComplement(pTop) ); + Vec_PtrShrink( vFanins, nVars ); return -1; - // return 1 if at least one branch has a duplicate - return RetValue1 || RetValue2; + } + Vec_PtrShrink( vFanins, nVars ); + return Counter; } -/**Function************************************************************* - - Synopsis [Collects the nodes in the cone delimited by fMarkA==1.] - - Description [Returns -1 if the AND-cone has the same node in both polarities. - Returns 1 if the AND-cone has the same node in the same polarity. Returns 0 - if the AND-cone has no repeated nodes.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, int fDuplicate ) -{ - Vec_Ptr_t * vNodes; - int RetValue, i; - assert( !Abc_ObjIsComplement(pNode) ); - vNodes = Vec_PtrAlloc( 4 ); - RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, fDuplicate ); - assert( vNodes->nSize > 0 ); - for ( i = 0; i < vNodes->nSize; i++ ) - Abc_ObjRegular((Abc_Obj_t *)vNodes->pArray[i])->fMarkB = 0; - if ( RetValue == -1 ) - vNodes->nSize = 0; - return vNodes; -} //////////////////////////////////////////////////////////////////////// diff --git a/src/base/io/ioReadPla.c b/src/base/io/ioReadPla.c index a334ded0..c4b4084c 100644 --- a/src/base/io/ioReadPla.c +++ b/src/base/io/ioReadPla.c @@ -82,7 +82,7 @@ Abc_Ntk_t * Io_ReadPlaNetwork( Extra_FileReader_t * p ) ProgressBar * pProgress; Vec_Ptr_t * vTokens; Abc_Ntk_t * pNtk; - Abc_Obj_t * pTerm, * pNode; + Abc_Obj_t * pTermPi, * pTermPo, * pNode; Vec_Str_t ** ppSops; char Buffer[100]; int nInputs = -1, nOutputs = -1, nProducts = -1; @@ -169,13 +169,16 @@ Abc_Ntk_t * Io_ReadPlaNetwork( Extra_FileReader_t * p ) // create the PO drivers and add them // start the SOP covers ppSops = ALLOC( Vec_Str_t *, nOutputs ); - Abc_NtkForEachPo( pNtk, pTerm, i ) + Abc_NtkForEachPo( pNtk, pTermPo, i ) { ppSops[i] = Vec_StrAlloc( 100 ); + // create the node pNode = Abc_NtkCreateNode(pNtk); - for ( k = 0; k < nInputs; k++ ) - Abc_ObjAddFanin( pNode, Abc_NtkPi(pNtk,k) ); - Abc_ObjAddFanin( Abc_ObjFanout0(pTerm), pNode ); + // connect the node to the PO net + Abc_ObjAddFanin( Abc_ObjFanin0Ntk(pTermPo), pNode ); + // connect the node to the PI nets + Abc_NtkForEachPi( pNtk, pTermPi, k ) + Abc_ObjAddFanin( pNode, Abc_ObjFanout0Ntk(pTermPi) ); } } // read the cubes @@ -219,9 +222,9 @@ Abc_Ntk_t * Io_ReadPlaNetwork( Extra_FileReader_t * p ) nCubes, nProducts ); // add the SOP covers - Abc_NtkForEachPo( pNtk, pTerm, i ) + Abc_NtkForEachPo( pNtk, pTermPo, i ) { - pNode = Abc_ObjFanin0Ntk(pTerm); + pNode = Abc_ObjFanin0Ntk( Abc_ObjFanin0(pTermPo) ); if ( ppSops[i]->nSize == 0 ) { Abc_ObjRemoveFanins(pNode); diff --git a/src/map/fpga/fpgaUtils.c b/src/map/fpga/fpgaUtils.c index bf334afa..89ef13dc 100644 --- a/src/map/fpga/fpgaUtils.c +++ b/src/map/fpga/fpgaUtils.c @@ -22,9 +22,12 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +#define FPGA_CO_LIST_SIZE 5 + static void Fpga_MappingDfs_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes, int fCollectEquiv ); static void Fpga_MappingDfsCuts_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes ); -static int Fpga_MappingCompareOutputDelay( int * pOut1, int * pOut2 ); +static int Fpga_MappingCompareOutputDelay( Fpga_Node_t ** ppNode1, Fpga_Node_t ** ppNode2 ); +static void Fpga_MappingFindLatest( Fpga_Man_t * p, int * pNodes, int nNodesMax ); static void Fpga_DfsLim_rec( Fpga_Node_t * pNode, int Level, Fpga_NodeVec_t * vNodes ); static int Fpga_CollectNodeTfo_rec( Fpga_Node_t * pNode, Fpga_Node_t * pPivot, Fpga_NodeVec_t * vVisited, Fpga_NodeVec_t * vTfo ); static Fpga_Man_t * s_pMan = NULL; @@ -321,6 +324,62 @@ float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ) /**Function************************************************************* + Synopsis [Compares the outputs by their arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MappingCompareOutputDelay( Fpga_Node_t ** ppNode1, Fpga_Node_t ** ppNode2 ) +{ + Fpga_Node_t * pNode1 = Fpga_Regular(*ppNode1); + Fpga_Node_t * pNode2 = Fpga_Regular(*ppNode2); + float Arrival1 = pNode1->pCutBest? pNode1->pCutBest->tArrival : 0; + float Arrival2 = pNode2->pCutBest? pNode2->pCutBest->tArrival : 0; + if ( Arrival1 < Arrival2 ) + return -1; + if ( Arrival1 > Arrival2 ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Finds given number of latest arriving COs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingFindLatest( Fpga_Man_t * p, int * pNodes, int nNodesMax ) +{ + int nNodes, i, k, v; + assert( p->nOutputs >= nNodesMax ); + pNodes[0] = 0; + nNodes = 1; + for ( i = 1; i < p->nOutputs; i++ ) + { + for ( k = nNodes - 1; k >= 0; k-- ) + if ( Fpga_MappingCompareOutputDelay( &p->pOutputs[pNodes[k]], &p->pOutputs[i] ) >= 0 ) + break; + if ( k == nNodesMax - 1 ) + continue; + if ( nNodes < nNodesMax ) + nNodes++; + for ( v = nNodes - 1; v > k+1; v-- ) + pNodes[v] = pNodes[v-1]; + pNodes[k+1] = i; + } +} + +/**Function************************************************************* + Synopsis [Prints a bunch of latest arriving outputs.] Description [] @@ -333,22 +392,17 @@ float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ) void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p ) { Fpga_Node_t * pNode; + int pSorted[FPGA_CO_LIST_SIZE]; int fCompl, Limit, MaxNameSize, i; - int * pSorted; - // sort outputs by arrival time - s_pMan = p; - pSorted = ALLOC( int, p->nOutputs ); - for ( i = 0; i < p->nOutputs; i++ ) - pSorted[i] = i; - qsort( (void *)pSorted, p->nOutputs, sizeof(int), - (int (*)(const void *, const void *)) Fpga_MappingCompareOutputDelay ); - assert( Fpga_MappingCompareOutputDelay( pSorted, pSorted + p->nOutputs - 1 ) <= 0 ); - s_pMan = NULL; + // determine the number of nodes to print + Limit = (p->nOutputs > FPGA_CO_LIST_SIZE)? FPGA_CO_LIST_SIZE : p->nOutputs; + + // determine the order + Fpga_MappingFindLatest( p, pSorted, Limit ); // determine max size of the node's name MaxNameSize = 0; - Limit = (p->nOutputs > 5)? 5 : p->nOutputs; for ( i = 0; i < Limit; i++ ) if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) ) MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]); @@ -368,32 +422,8 @@ void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p ) printf( "POS" ); printf( "\n" ); } - free( pSorted ); } -/**Function************************************************************* - - Synopsis [Compares the outputs by their arrival times.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MappingCompareOutputDelay( int * pOut1, int * pOut2 ) -{ - Fpga_Node_t * pNode1 = Fpga_Regular(s_pMan->pOutputs[*pOut1]); - Fpga_Node_t * pNode2 = Fpga_Regular(s_pMan->pOutputs[*pOut2]); - float pTime1 = pNode1->pCutBest? pNode1->pCutBest->tArrival : 0; - float pTime2 = pNode2->pCutBest? pNode2->pCutBest->tArrival : 0; - if ( pTime1 > pTime2 ) - return -1; - if ( pTime1 < pTime2 ) - return 1; - return 0; -} /**Function************************************************************* diff --git a/src/map/mapper/mapperUtils.c b/src/map/mapper/mapperUtils.c index 78885729..00f1b85b 100644 --- a/src/map/mapper/mapperUtils.c +++ b/src/map/mapper/mapperUtils.c @@ -22,6 +22,8 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +#define MAP_CO_LIST_SIZE 5 + static void Map_MappingDfs_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes, int fCollectEquiv ); static int Map_MappingCountLevels_rec( Map_Node_t * pNode ); static float Map_MappingSetRefsAndArea_rec( Map_Man_t * pMan, Map_Node_t * pNode ); @@ -29,7 +31,8 @@ static float Map_MappingSetRefsAndSwitch_rec( Map_Man_t * pMan, Map_Node_t * pNo static float Map_MappingSetRefsAndWire_rec( Map_Man_t * pMan, Map_Node_t * pNode ); static void Map_MappingDfsCuts_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes ); static float Map_MappingArea_rec( Map_Man_t * pMan, Map_Node_t * pNode, Map_NodeVec_t * vNodes ); -static int Map_MappingCompareOutputDelay( int * pOut1, int * pOut2 ); +static int Map_MappingCompareOutputDelay( Map_Node_t ** ppNode1, Map_Node_t ** ppNode2 ); +static void Map_MappingFindLatest( Map_Man_t * p, int * pNodes, int nNodesMax ); static unsigned Map_MappingExpandTruth_rec( unsigned uTruth, int nVars ); static void Map_MappingGetChoiceLevels( Map_Man_t * pMan, Map_Node_t * p1, Map_Node_t * p2, int * pMin, int * pMax ); static float Map_MappingGetChoiceVolumes( Map_Man_t * pMan, Map_Node_t * p1, Map_Node_t * p2 ); @@ -391,6 +394,64 @@ void Map_MappingMark_rec( Map_Node_t * pNode ) /**Function************************************************************* + Synopsis [Compares the outputs by their arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingCompareOutputDelay( Map_Node_t ** ppNode1, Map_Node_t ** ppNode2 ) +{ + Map_Node_t * pNode1 = Map_Regular(*ppNode1); + Map_Node_t * pNode2 = Map_Regular(*ppNode2); + int fPhase1 = !Map_IsComplement(*ppNode1); + int fPhase2 = !Map_IsComplement(*ppNode2); + float Arrival1 = pNode1->tArrival[fPhase1].Worst; + float Arrival2 = pNode2->tArrival[fPhase2].Worst; + 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 Map_MappingFindLatest( Map_Man_t * p, int * pNodes, int nNodesMax ) +{ + int nNodes, i, k, v; + assert( p->nOutputs >= nNodesMax ); + pNodes[0] = 0; + nNodes = 1; + for ( i = 1; i < p->nOutputs; i++ ) + { + for ( k = nNodes - 1; k >= 0; k-- ) + if ( Map_MappingCompareOutputDelay( &p->pOutputs[pNodes[k]], &p->pOutputs[i] ) >= 0 ) + break; + if ( k == nNodesMax - 1 ) + continue; + if ( nNodes < nNodesMax ) + nNodes++; + for ( v = nNodes - 1; v > k+1; v-- ) + pNodes[v] = pNodes[v-1]; + pNodes[k+1] = i; + } +} + +/**Function************************************************************* + Synopsis [Prints a bunch of latest arriving outputs.] Description [] @@ -402,30 +463,20 @@ void Map_MappingMark_rec( Map_Node_t * pNode ) ***********************************************************************/ void Map_MappingPrintOutputArrivals( Map_Man_t * p ) { + int pSorted[MAP_CO_LIST_SIZE]; Map_Time_t * pTimes; Map_Node_t * pNode; int fPhase, Limit, i; - int nOutputs, MaxNameSize; - int * pSorted; + int MaxNameSize; - // sort outputs by arrival time - s_pMan = p; - pSorted = ALLOC( int, p->nOutputs ); - nOutputs = 0; - for ( i = 0; i < p->nOutputs; i++ ) - { - if ( Map_NodeIsConst(p->pOutputs[i]) ) - continue; - pSorted[nOutputs++] = i; - } - qsort( (void *)pSorted, nOutputs, sizeof(int), - (int (*)(const void *, const void *)) Map_MappingCompareOutputDelay ); - assert( Map_MappingCompareOutputDelay( pSorted, pSorted + nOutputs - 1 ) <= 0 ); - s_pMan = NULL; + // determine the number of nodes to print + Limit = (p->nOutputs > MAP_CO_LIST_SIZE)? MAP_CO_LIST_SIZE : p->nOutputs; + + // determine the order + Map_MappingFindLatest( p, pSorted, Limit ); // determine max size of the node's name MaxNameSize = 0; - Limit = (nOutputs > 5)? 5 : nOutputs; for ( i = 0; i < Limit; i++ ) if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) ) MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]); @@ -443,33 +494,6 @@ void Map_MappingPrintOutputArrivals( Map_Man_t * p ) printf( "%s", fPhase? "POS" : "NEG" ); printf( "\n" ); } - free( pSorted ); -} - -/**Function************************************************************* - - Synopsis [Compares the outputs by their arrival times.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Map_MappingCompareOutputDelay( int * pOut1, int * pOut2 ) -{ - Map_Node_t * pNode1 = Map_Regular(s_pMan->pOutputs[*pOut1]); - Map_Node_t * pNode2 = Map_Regular(s_pMan->pOutputs[*pOut2]); - int fPhase1 = (pNode1 == s_pMan->pOutputs[*pOut1]); - int fPhase2 = (pNode2 == s_pMan->pOutputs[*pOut2]); - float Arrival1 = pNode1->tArrival[fPhase1].Worst; - float Arrival2 = pNode2->tArrival[fPhase2].Worst; - if ( Arrival1 > Arrival2 ) - return -1; - if ( Arrival1 < Arrival2 ) - return 1; - return 0; } /**Function************************************************************* diff --git a/src/opt/rwr/rwrEva.c b/src/opt/rwr/rwrEva.c index ddc9d742..b486785f 100644 --- a/src/opt/rwr/rwrEva.c +++ b/src/opt/rwr/rwrEva.c @@ -109,7 +109,7 @@ Vec_Int_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut, vFanins->nSize = pCut->nLeaves; vFanins->pArray = pCut->ppLeaves; // detect how many unlabeled nodes will be reused - GainCur = Abc_NodeStrashDecCount( pRoot->pNtk->pManFunc, vFanins, (Vec_Int_t *)pNode->pNext, + GainCur = Abc_NodeStrashDecCount( pRoot->pNtk->pManFunc, pRoot, vFanins, (Vec_Int_t *)pNode->pNext, p->vLevNums, NodeMax, LevelMax ); if ( GainBest < GainCur ) { diff --git a/src/sop/ft/ftFactor.c b/src/sop/ft/ftFactor.c index 43f9e3ce..1654973f 100644 --- a/src/sop/ft/ftFactor.c +++ b/src/sop/ft/ftFactor.c @@ -320,8 +320,8 @@ Ft_Node_t * Ft_FactorTrivialTree_rec( Vec_Int_t * vForm, Ft_Node_t ** ppNodes, i return ppNodes[0]; // split the nodes into two parts - nNodes1 = nNodes/2; - nNodes2 = nNodes - nNodes1; + nNodes2 = nNodes/2; + nNodes1 = nNodes - nNodes2; // recursively construct the tree for the parts pNode1 = Ft_FactorTrivialTree_rec( vForm, ppNodes, nNodes1, fAnd ); |