diff options
Diffstat (limited to 'src/map/cov/covBuild.c')
| -rw-r--r-- | src/map/cov/covBuild.c | 539 |
1 files changed, 539 insertions, 0 deletions
diff --git a/src/map/cov/covBuild.c b/src/map/cov/covBuild.c new file mode 100644 index 00000000..560178be --- /dev/null +++ b/src/map/cov/covBuild.c @@ -0,0 +1,539 @@ +/**CFile**************************************************************** + + FileName [covBuild.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Mapping into network of SOPs/ESOPs.] + + Synopsis [Network construction procedures.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: covBuild.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "cov.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Derives the decomposed network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Abc_NtkCovDeriveCube( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pObj, Min_Cube_t * pCube, Vec_Int_t * vSupp, int fCompl ) +{ + Vec_Int_t * vLits; + Abc_Obj_t * pNodeNew, * pFanin; + int i, iFanin, Lit; + // create empty cube + if ( pCube->nLits == 0 ) + { + if ( fCompl ) + return Abc_NtkCreateNodeConst0(pNtkNew); + return Abc_NtkCreateNodeConst1(pNtkNew); + } + // get the literals of this cube + vLits = Vec_IntAlloc( 10 ); + Min_CubeGetLits( pCube, vLits ); + assert( pCube->nLits == (unsigned)vLits->nSize ); + // create special case when there is only one literal + if ( pCube->nLits == 1 ) + { + iFanin = Vec_IntEntry(vLits,0); + pFanin = Abc_NtkObj( pObj->pNtk, Vec_IntEntry(vSupp, iFanin) ); + Lit = Min_CubeGetVar(pCube, iFanin); + assert( Lit == 1 || Lit == 2 ); + Vec_IntFree( vLits ); + if ( (Lit == 1) ^ fCompl )// negative + return Abc_NtkCreateNodeInv( pNtkNew, pFanin->pCopy ); + return pFanin->pCopy; + } + assert( pCube->nLits > 1 ); + // create the AND cube + pNodeNew = Abc_NtkCreateNode( pNtkNew ); + for ( i = 0; i < vLits->nSize; i++ ) + { + iFanin = Vec_IntEntry(vLits,i); + pFanin = Abc_NtkObj( pObj->pNtk, Vec_IntEntry(vSupp, iFanin) ); + Lit = Min_CubeGetVar(pCube, iFanin); + assert( Lit == 1 || Lit == 2 ); + Vec_IntWriteEntry( vLits, i, Lit==1 ); + Abc_ObjAddFanin( pNodeNew, pFanin->pCopy ); + } + pNodeNew->pData = Abc_SopCreateAnd( pNtkNew->pManFunc, vLits->nSize, vLits->pArray ); + if ( fCompl ) + Abc_SopComplement( pNodeNew->pData ); + Vec_IntFree( vLits ); + return pNodeNew; +} + +/**Function************************************************************* + + Synopsis [Derives the decomposed network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Abc_NtkCovDeriveNode_rec( Cov_Man_t * p, Abc_Ntk_t * pNtkNew, Abc_Obj_t * pObj, int Level ) +{ + Min_Cube_t * pCover, * pCube; + Abc_Obj_t * pFaninNew, * pNodeNew, * pFanin; + Vec_Int_t * vSupp; + int Entry, nCubes, i; + + if ( Abc_ObjIsCi(pObj) ) + return pObj->pCopy; + assert( Abc_ObjIsNode(pObj) ); + // skip if already computed + if ( pObj->pCopy ) + return pObj->pCopy; + + // get the support and the cover + vSupp = Abc_ObjGetSupp( pObj ); + pCover = Abc_ObjGetCover2( pObj ); + assert( vSupp ); +/* + if ( pCover && pCover->nVars - Min_CoverSuppVarNum(p->pManMin, pCover) > 0 ) + { + printf( "%d\n ", pCover->nVars - Min_CoverSuppVarNum(p->pManMin, pCover) ); + Min_CoverWrite( stdout, pCover ); + } +*/ +/* + // print the support of this node + printf( "{ " ); + Vec_IntForEachEntry( vSupp, Entry, i ) + printf( "%d ", Entry ); + printf( "} cubes = %d\n", Min_CoverCountCubes( pCover ) ); +*/ + // process the fanins + Vec_IntForEachEntry( vSupp, Entry, i ) + { + pFanin = Abc_NtkObj(pObj->pNtk, Entry); + Abc_NtkCovDeriveNode_rec( p, pNtkNew, pFanin, Level+1 ); + } + + // for each cube, construct the node + nCubes = Min_CoverCountCubes( pCover ); + if ( nCubes == 0 ) + pNodeNew = Abc_NtkCreateNodeConst0(pNtkNew); + else if ( nCubes == 1 ) + pNodeNew = Abc_NtkCovDeriveCube( pNtkNew, pObj, pCover, vSupp, 0 ); + else + { + pNodeNew = Abc_NtkCreateNode( pNtkNew ); + Min_CoverForEachCube( pCover, pCube ) + { + pFaninNew = Abc_NtkCovDeriveCube( pNtkNew, pObj, pCube, vSupp, 0 ); + Abc_ObjAddFanin( pNodeNew, pFaninNew ); + } + pNodeNew->pData = Abc_SopCreateXorSpecial( pNtkNew->pManFunc, nCubes ); + } +/* + printf( "Created node %d(%d) at level %d: ", pNodeNew->Id, pObj->Id, Level ); + Vec_IntForEachEntry( vSupp, Entry, i ) + { + pFanin = Abc_NtkObj(pObj->pNtk, Entry); + printf( "%d(%d) ", pFanin->pCopy->Id, pFanin->Id ); + } + printf( "\n" ); + Min_CoverWrite( stdout, pCover ); +*/ + pObj->pCopy = pNodeNew; + return pNodeNew; +} + +/**Function************************************************************* + + Synopsis [Derives the decomposed network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * Abc_NtkCovDerive( Cov_Man_t * p, Abc_Ntk_t * pNtk ) +{ + Abc_Ntk_t * pNtkNew; + Abc_Obj_t * pObj; + int i; + assert( Abc_NtkIsStrash(pNtk) ); + // perform strashing + pNtkNew = Abc_NtkStartFrom( pNtk, ABC_NTK_LOGIC, ABC_FUNC_SOP ); + // reconstruct the network + Abc_NtkForEachCo( pNtk, pObj, i ) + { + Abc_NtkCovDeriveNode_rec( p, pNtkNew, Abc_ObjFanin0(pObj), 0 ); +// printf( "*** CO %s : %d -> %d \n", Abc_ObjName(pObj), pObj->pCopy->Id, Abc_ObjFanin0(pObj)->pCopy->Id ); + } + // add the COs + Abc_NtkFinalize( pNtk, pNtkNew ); + Abc_NtkLogicMakeSimpleCos( pNtkNew, 1 ); + // make sure everything is okay + if ( !Abc_NtkCheck( pNtkNew ) ) + { + printf( "Abc_NtkCovDerive: The network check has failed.\n" ); + Abc_NtkDelete( pNtkNew ); + return NULL; + } + return pNtkNew; +} + + + + +/**Function************************************************************* + + Synopsis [Derives the decomposed network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Abc_NtkCovDeriveInv( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pObj, int fCompl ) +{ + assert( pObj->pCopy ); + if ( !fCompl ) + return pObj->pCopy; + if ( pObj->pCopy->pCopy == NULL ) + pObj->pCopy->pCopy = Abc_NtkCreateNodeInv( pNtkNew, pObj->pCopy ); + return pObj->pCopy->pCopy; + } + +/**Function************************************************************* + + Synopsis [Derives the decomposed network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Abc_NtkCovDeriveCubeInv( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pObj, Min_Cube_t * pCube, Vec_Int_t * vSupp ) +{ + Vec_Int_t * vLits; + Abc_Obj_t * pNodeNew, * pFanin; + int i, iFanin, Lit; + // create empty cube + if ( pCube->nLits == 0 ) + return Abc_NtkCreateNodeConst1(pNtkNew); + // get the literals of this cube + vLits = Vec_IntAlloc( 10 ); + Min_CubeGetLits( pCube, vLits ); + assert( pCube->nLits == (unsigned)vLits->nSize ); + // create special case when there is only one literal + if ( pCube->nLits == 1 ) + { + iFanin = Vec_IntEntry(vLits,0); + pFanin = Abc_NtkObj( pObj->pNtk, Vec_IntEntry(vSupp, iFanin) ); + Lit = Min_CubeGetVar(pCube, iFanin); + assert( Lit == 1 || Lit == 2 ); + Vec_IntFree( vLits ); +// if ( Lit == 1 )// negative +// return Abc_NtkCreateNodeInv( pNtkNew, pFanin->pCopy ); +// return pFanin->pCopy; + return Abc_NtkCovDeriveInv( pNtkNew, pFanin, Lit==1 ); + } + assert( pCube->nLits > 1 ); + // create the AND cube + pNodeNew = Abc_NtkCreateNode( pNtkNew ); + for ( i = 0; i < vLits->nSize; i++ ) + { + iFanin = Vec_IntEntry(vLits,i); + pFanin = Abc_NtkObj( pObj->pNtk, Vec_IntEntry(vSupp, iFanin) ); + Lit = Min_CubeGetVar(pCube, iFanin); + assert( Lit == 1 || Lit == 2 ); + Vec_IntWriteEntry( vLits, i, Lit==1 ); +// Abc_ObjAddFanin( pNodeNew, pFanin->pCopy ); + Abc_ObjAddFanin( pNodeNew, Abc_NtkCovDeriveInv( pNtkNew, pFanin, Lit==1 ) ); + } +// pNodeNew->pData = Abc_SopCreateAnd( pNtkNew->pManFunc, vLits->nSize, vLits->pArray ); + pNodeNew->pData = Abc_SopCreateAnd( pNtkNew->pManFunc, vLits->nSize, NULL ); + Vec_IntFree( vLits ); + return pNodeNew; +} + +/**Function************************************************************* + + Synopsis [Derives the decomposed network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Abc_NtkCovDeriveNodeInv_rec( Cov_Man_t * p, Abc_Ntk_t * pNtkNew, Abc_Obj_t * pObj, int fCompl ) +{ + Min_Cube_t * pCover, * pCube; + Abc_Obj_t * pFaninNew, * pNodeNew, * pFanin; + Vec_Int_t * vSupp; + int Entry, nCubes, i; + + // skip if already computed + if ( pObj->pCopy ) + return Abc_NtkCovDeriveInv( pNtkNew, pObj, fCompl ); + assert( Abc_ObjIsNode(pObj) ); + + // get the support and the cover + vSupp = Abc_ObjGetSupp( pObj ); + pCover = Abc_ObjGetCover2( pObj ); + assert( vSupp ); + + // process the fanins + Vec_IntForEachEntry( vSupp, Entry, i ) + { + pFanin = Abc_NtkObj(pObj->pNtk, Entry); + Abc_NtkCovDeriveNodeInv_rec( p, pNtkNew, pFanin, 0 ); + } + + // for each cube, construct the node + nCubes = Min_CoverCountCubes( pCover ); + if ( nCubes == 0 ) + pNodeNew = Abc_NtkCreateNodeConst0(pNtkNew); + else if ( nCubes == 1 ) + pNodeNew = Abc_NtkCovDeriveCubeInv( pNtkNew, pObj, pCover, vSupp ); + else + { + pNodeNew = Abc_NtkCreateNode( pNtkNew ); + Min_CoverForEachCube( pCover, pCube ) + { + pFaninNew = Abc_NtkCovDeriveCubeInv( pNtkNew, pObj, pCube, vSupp ); + Abc_ObjAddFanin( pNodeNew, pFaninNew ); + } + pNodeNew->pData = Abc_SopCreateXorSpecial( pNtkNew->pManFunc, nCubes ); + } + + pObj->pCopy = pNodeNew; + return Abc_NtkCovDeriveInv( pNtkNew, pObj, fCompl ); +} + +/**Function************************************************************* + + Synopsis [Derives the decomposed network.] + + Description [The resulting network contains only pure AND/OR/EXOR gates + and inverters. This procedure is usedful to generate Verilog.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * Abc_NtkCovDeriveClean( Cov_Man_t * p, Abc_Ntk_t * pNtk ) +{ + Abc_Ntk_t * pNtkNew; + Abc_Obj_t * pObj, * pNodeNew; + int i; + assert( Abc_NtkIsStrash(pNtk) ); + // perform strashing + pNtkNew = Abc_NtkStartFrom( pNtk, ABC_NTK_LOGIC, ABC_FUNC_SOP ); + // reconstruct the network + Abc_NtkForEachCo( pNtk, pObj, i ) + { + pNodeNew = Abc_NtkCovDeriveNodeInv_rec( p, pNtkNew, Abc_ObjFanin0(pObj), Abc_ObjFaninC0(pObj) ); + Abc_ObjAddFanin( pObj->pCopy, pNodeNew ); + } + // add the COs + Abc_NtkLogicMakeSimpleCos( pNtkNew, 0 ); + // make sure everything is okay + if ( !Abc_NtkCheck( pNtkNew ) ) + { + printf( "Abc_NtkCovDeriveInv: The network check has failed.\n" ); + Abc_NtkDelete( pNtkNew ); + return NULL; + } + return pNtkNew; +} + + + +/**Function************************************************************* + + Synopsis [Derives the decomposed network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Abc_NtkCovDerive_rec( Cov_Man_t * p, Abc_Ntk_t * pNtkNew, Abc_Obj_t * pObj ) +{ + int fVerbose = 0; + Min_Cube_t * pCover, * pCovers[3]; + Abc_Obj_t * pNodeNew, * pFanin; + Vec_Int_t * vSupp; + Vec_Str_t * vCover; + int i, Entry, nCubes, Type; + // skip if already computed + if ( pObj->pCopy ) + return pObj->pCopy; + assert( Abc_ObjIsNode(pObj) ); + // get the support and the cover + vSupp = Abc_ObjGetSupp( pObj ); + assert( vSupp ); + // choose the cover to implement + pCovers[0] = Abc_ObjGetCover( pObj, 0 ); + pCovers[1] = Abc_ObjGetCover( pObj, 1 ); + pCovers[2] = Abc_ObjGetCover2( pObj ); + // use positive polarity + if ( pCovers[0] + && (!pCovers[1] || Min_CoverCountCubes(pCovers[0]) <= Min_CoverCountCubes(pCovers[1])) + && (!pCovers[2] || Min_CoverCountCubes(pCovers[0]) <= Min_CoverCountCubes(pCovers[2])) ) + { + pCover = pCovers[0]; + Type = '1'; + } + else + // use negative polarity + if ( pCovers[1] + && (!pCovers[0] || Min_CoverCountCubes(pCovers[1]) <= Min_CoverCountCubes(pCovers[0])) + && (!pCovers[2] || Min_CoverCountCubes(pCovers[1]) <= Min_CoverCountCubes(pCovers[2])) ) + { + pCover = pCovers[1]; + Type = '0'; + } + else + // use XOR polarity + if ( pCovers[2] + && (!pCovers[0] || Min_CoverCountCubes(pCovers[2]) < Min_CoverCountCubes(pCovers[0])) + && (!pCovers[1] || Min_CoverCountCubes(pCovers[2]) < Min_CoverCountCubes(pCovers[1])) ) + { + pCover = pCovers[2]; + Type = 'x'; + } + else + assert( 0 ); + // print the support of this node + if ( fVerbose ) + { + printf( "{ " ); + Vec_IntForEachEntry( vSupp, Entry, i ) + printf( "%d ", Entry ); + printf( "} cubes = %d\n", Min_CoverCountCubes( pCover ) ); + } + // process the fanins + Vec_IntForEachEntry( vSupp, Entry, i ) + { + pFanin = Abc_NtkObj(pObj->pNtk, Entry); + Abc_NtkCovDerive_rec( p, pNtkNew, pFanin ); + } + // for each cube, construct the node + nCubes = Min_CoverCountCubes( pCover ); + if ( nCubes == 0 ) + pNodeNew = Abc_NtkCreateNodeConst0(pNtkNew); + else if ( nCubes == 1 ) + pNodeNew = Abc_NtkCovDeriveCube( pNtkNew, pObj, pCover, vSupp, Type == '0' ); + else + { + // create the node + pNodeNew = Abc_NtkCreateNode( pNtkNew ); + Vec_IntForEachEntry( vSupp, Entry, i ) + { + pFanin = Abc_NtkObj(pObj->pNtk, Entry); + Abc_ObjAddFanin( pNodeNew, pFanin->pCopy ); + } + // derive the function + vCover = Vec_StrAlloc( 100 ); + Min_CoverCreate( vCover, pCover, (char)Type ); + pNodeNew->pData = Abc_SopRegister( pNtkNew->pManFunc, Vec_StrArray(vCover) ); + Vec_StrFree( vCover ); + } + +/* + printf( "Created node %d(%d) at level %d: ", pNodeNew->Id, pObj->Id, Level ); + Vec_IntForEachEntry( vSupp, Entry, i ) + { + pFanin = Abc_NtkObj(pObj->pNtk, Entry); + printf( "%d(%d) ", pFanin->pCopy->Id, pFanin->Id ); + } + printf( "\n" ); + Min_CoverWrite( stdout, pCover ); +*/ + return pObj->pCopy = pNodeNew; +} + +/**Function************************************************************* + + Synopsis [Derives the decomposed network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * Abc_NtkCovDeriveRegular( Cov_Man_t * p, Abc_Ntk_t * pNtk ) +{ + Abc_Ntk_t * pNtkNew; + Abc_Obj_t * pObj, * pNodeNew; + int i; + assert( Abc_NtkIsStrash(pNtk) ); + // perform strashing + pNtkNew = Abc_NtkStartFrom( pNtk, ABC_NTK_LOGIC, ABC_FUNC_SOP ); + // reconstruct the network + if ( Abc_ObjFanoutNum(Abc_AigConst1(pNtk)) > 0 ) + Abc_AigConst1(pNtk)->pCopy = Abc_NtkCreateNodeConst1(pNtkNew); + Abc_NtkForEachCo( pNtk, pObj, i ) + { + pNodeNew = Abc_NtkCovDerive_rec( p, pNtkNew, Abc_ObjFanin0(pObj) ); + if ( Abc_ObjFaninC0(pObj) ) + { + if ( pNodeNew->pData && Abc_ObjFanoutNum(Abc_ObjFanin0(pObj)) == 1 ) + Abc_SopComplement( pNodeNew->pData ); + else + pNodeNew = Abc_NtkCreateNodeInv( pNtkNew, pNodeNew ); + } + Abc_ObjAddFanin( pObj->pCopy, pNodeNew ); + } + // add the COs + Abc_NtkLogicMakeSimpleCos( pNtkNew, 0 ); + // make sure everything is okay + if ( !Abc_NtkCheck( pNtkNew ) ) + { + printf( "Abc_NtkCovDerive: The network check has failed.\n" ); + Abc_NtkDelete( pNtkNew ); + return NULL; + } + return pNtkNew; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |