/**CFile**************************************************************** FileName [abcMfs.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [Network and node package.] Synopsis [Optimization with don't-cares.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - June 20, 2005.] Revision [$Id: abcMfs.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] ***********************************************************************/ #include "base/abc/abc.h" #include "bool/kit/kit.h" #include "opt/sfm/sfm.h" #include "base/io/ioAbc.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Abc_NtkAssignIDs( Abc_Ntk_t * pNtk ) { Vec_Ptr_t * vNodes; Abc_Obj_t * pObj; int i; vNodes = Abc_NtkDfs( pNtk, 0 ); Abc_NtkCleanCopy( pNtk ); Abc_NtkForEachCi( pNtk, pObj, i ) pObj->iTemp = i; Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) pObj->iTemp = Abc_NtkCiNum(pNtk) + i; Abc_NtkForEachCo( pNtk, pObj, i ) pObj->iTemp = Abc_NtkCiNum(pNtk) + Vec_PtrSize(vNodes) + i; return vNodes; } Vec_Ptr_t * Abc_NtkAssignIDs2( Abc_Ntk_t * pNtk ) { Vec_Ptr_t * vNodes; Abc_Obj_t * pObj; int i; Abc_NtkCleanCopy( pNtk ); Abc_NtkForEachCi( pNtk, pObj, i ) pObj->iTemp = i; vNodes = Vec_PtrAlloc( Abc_NtkNodeNum(pNtk) ); Abc_NtkForEachNode( pNtk, pObj, i ) { pObj->iTemp = Abc_NtkCiNum(pNtk) + Vec_PtrSize(vNodes); Vec_PtrPush( vNodes, pObj ); } assert( Vec_PtrSize(vNodes) == Abc_NtkNodeNum(pNtk) ); Abc_NtkForEachCo( pNtk, pObj, i ) pObj->iTemp = Abc_NtkCiNum(pNtk) + Vec_PtrSize(vNodes) + i; return vNodes; } /**Function************************************************************* Synopsis [Assign truth table sizes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Int_t * Abc_NtkAssignStarts( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, int * pnTotal ) { Abc_Obj_t * pObj; int i, Counter = 0; Vec_Int_t * vStarts = Vec_IntStart( Abc_NtkObjNum(pNtk) ); Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) { Vec_IntWriteEntry( vStarts, pObj->iTemp, Counter ); Counter += Abc_Truth6WordNum( Abc_ObjFaninNum(pObj) ); } *pnTotal = Counter; return vStarts; } void Abc_NtkFillTruthStore( word TruthStore[16][1<<10] ) { if ( TruthStore[0][0] == 0 ) { static word Truth6[6] = { 0xAAAAAAAAAAAAAAAA, 0xCCCCCCCCCCCCCCCC, 0xF0F0F0F0F0F0F0F0, 0xFF00FF00FF00FF00, 0xFFFF0000FFFF0000, 0xFFFFFFFF00000000 }; int nVarsMax = 16; int nWordsMax = (1 << 10); int i, k; assert( nVarsMax <= 16 ); for ( i = 0; i < 6; i++ ) for ( k = 0; k < nWordsMax; k++ ) TruthStore[i][k] = Truth6[i]; for ( i = 6; i < nVarsMax; i++ ) for ( k = 0; k < nWordsMax; k++ ) TruthStore[i][k] = ((k >> (i-6)) & 1) ? ~(word)0 : 0; } } /**Function************************************************************* Synopsis [Extracts information about the network.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Sfm_Ntk_t * Abc_NtkExtractMfs( Abc_Ntk_t * pNtk, int nFirstFixed ) { word TruthStore[16][1<<10] = {{0}}, * pTruths[16] = {NULL}, pCube[1<<10] = {0}; Vec_Ptr_t * vNodes; Vec_Wec_t * vFanins; Vec_Str_t * vFixed; Vec_Wrd_t * vTruths; Vec_Int_t * vArray; Vec_Int_t * vStarts; Vec_Wrd_t * vTruths2; Abc_Obj_t * pObj, * pFanin; int i, k, nObjs, nTotal = 0; vNodes = nFirstFixed ? Abc_NtkAssignIDs2(pNtk) : Abc_NtkAssignIDs(pNtk); nObjs = Abc_NtkCiNum(pNtk) + Vec_PtrSize(vNodes) + Abc_NtkCoNum(pNtk); vFanins = Vec_WecStart( nObjs ); vFixed = Vec_StrStart( nObjs ); vTruths = Vec_WrdStart( nObjs ); vStarts = Abc_NtkAssignStarts( pNtk, vNodes, &nTotal ); vTruths2= Vec_WrdStart( nTotal ); Abc_NtkFillTruthStore( TruthStore ); for ( i = 0; i < 16; i++ ) pTruths[i] = TruthStore[i]; Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) { if ( Abc_ObjFaninNum(pObj) <= 6 ) { word uTruth = Abc_SopToTruth((char *)pObj->pData, Abc_ObjFaninNum(pObj)); Vec_WrdWriteEntry( vTruths, pObj->iTemp, uTruth ); if ( uTruth == 0 || ~uTruth == 0 ) continue; } else { int nWords = Abc_Truth6WordNum( Abc_ObjFaninNum(pObj) ); int Offset = Vec_IntEntry( vStarts, pObj->iTemp ); word * pRes = Vec_WrdEntryP( vTruths2, Offset ); Abc_SopToTruthBig( (char *)pObj->pData, Abc_ObjFaninNum(pObj), pTruths, pCube, pRes ); // check const0 for ( k = 0; k < nWords; k++ ) if ( pRes[k] ) break; if ( k == nWords ) continue; // check const1 for ( k = 0; k < nWords; k++ ) if ( ~pRes[k] ) break; if ( k == nWords ) continue; } vArray = Vec_WecEntry( vFanins, pObj->iTemp ); Vec_IntGrow( vArray, Abc_ObjFaninNum(pObj) ); Abc_ObjForEachFanin( pObj, pFanin, k ) Vec_IntPush( vArray, pFanin->iTemp ); //Vec_IntPrint( vArray ); } Abc_NtkForEachCo( pNtk, pObj, i ) { vArray = Vec_WecEntry( vFanins, pObj->iTemp ); Vec_IntGrow( vArray, Abc_ObjFaninNum(pObj) ); Abc_ObjForEachFanin( pObj, pFanin, k ) Vec_IntPush( vArray, pFanin->iTemp ); } Vec_PtrFree( vNodes ); for ( i = Abc_NtkCiNum(pNtk); i < Abc_NtkCiNum(pNtk) + nFirstFixed; i++ ) Vec_StrWriteEntry( vFixed, i, (char)1 ); // update fixed assert( nFirstFixed >= 0 && nFirstFixed < Abc_NtkNodeNum(pNtk) ); // for ( i = Abc_NtkCiNum(pNtk); i + Abc_NtkCoNum(pNtk) < Abc_NtkObjNum(pNtk); i++ ) // if ( rand() % 10 == 0 ) // Vec_StrWriteEntry( vFixed, i, (char)1 ); return Sfm_NtkConstruct( vFanins, Abc_NtkCiNum(pNtk), Abc_NtkCoNum(pNtk), vFixed, NULL, vTruths, vStarts, vTruths2 ); } Sfm_Ntk_t * Abc_NtkExtractMfs2( Abc_Ntk_t * pNtk, int iPivot ) { word TruthStore[16][1<<10] = {{0}}, * pTruths[16] = {NULL}, pCube[1<<10] = {0}; Vec_Ptr_t * vNodes; Vec_Wec_t * vFanins; Vec_Str_t * vFixed; Vec_Wrd_t * vTruths; Vec_Int_t * vArray; Vec_Int_t * vStarts; Vec_Wrd_t * vTruths2; Abc_Obj_t * pObj, * pFanin; int i, k, nObjs, nTotal = 0; vNodes = Abc_NtkAssignIDs2(pNtk); nObjs = Abc_NtkCiNum(pNtk) + Vec_PtrSize(vNodes) + Abc_NtkCoNum(pNtk); vFanins = Vec_WecStart( nObjs ); vFixed = Vec_StrStart( nObjs ); vTruths = Vec_WrdStart( nObjs ); vStarts = Abc_NtkAssignStarts( pNtk, vNodes, &nTotal ); vTruths2= Vec_WrdAlloc( nTotal ); Abc_NtkFillTruthStore( TruthStore ); for ( i = 0; i < 16; i++ ) pTruths[i] = TruthStore[i]; Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) { if ( Abc_ObjFaninNum(pObj) <= 6 ) { word uTruth = Abc_SopToTruth((char *)pObj->pData, Abc_ObjFaninNum(pObj)); Vec_WrdWriteEntry( vTruths, pObj->iTemp, uTruth ); if ( uTruth == 0 || ~uTruth == 0 ) continue; } else { int nWords = Abc_Truth6WordNum( Abc_ObjFaninNum(pObj) ); int Offset = Vec_IntEntry( vStarts, pObj->iTemp ); word * pRes = Vec_WrdEntryP( vTruths2, Offset ); Abc_SopToTruthBig( (char *)pObj->pData, Abc_ObjFaninNum(pObj), pTruths, pCube, pRes ); // check const0 for ( k = 0; k < nWords; k++ ) if ( pRes[k] ) break; if ( k == nWords ) continue; // check const1 for ( k = 0; k < nWords; k++ ) if ( ~pRes[k] ) break; if ( k == nWords ) continue; } vArray = Vec_WecEntry( vFanins, pObj->iTemp ); Vec_IntGrow( vArray, Abc_ObjFaninNum(pObj) ); Abc_ObjForEachFanin( pObj, pFanin, k ) Vec_IntPush( vArray, pFanin->iTemp ); } Abc_NtkForEachCo( pNtk, pObj, i ) { vArray = Vec_WecEntry( vFanins, pObj->iTemp ); Vec_IntGrow( vArray, Abc_ObjFaninNum(pObj) ); Abc_ObjForEachFanin( pObj, pFanin, k ) Vec_IntPush( vArray, pFanin->iTemp ); } Vec_PtrFree( vNodes ); // set fixed attributes Abc_NtkForEachNode( pNtk, pObj, i ) if ( i >= iPivot ) Vec_StrWriteEntry( vFixed, pObj->iTemp, (char)1 ); return Sfm_NtkConstruct( vFanins, Abc_NtkCiNum(pNtk), Abc_NtkCoNum(pNtk), vFixed, NULL, vTruths, vStarts, vTruths2 ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NtkInsertMfs( Abc_Ntk_t * pNtk, Sfm_Ntk_t * p ) { Vec_Int_t * vCover, * vMap, * vArray; Abc_Obj_t * pNode; word * pTruth; int i, k, Fanin; // map new IDs into old nodes vMap = Vec_IntStart( Abc_NtkObjNumMax(pNtk) ); Abc_NtkForEachCi( pNtk, pNode, i ) Vec_IntWriteEntry( vMap, pNode->iTemp, Abc_ObjId(pNode) ); Abc_NtkForEachNode( pNtk, pNode, i ) if ( pNode->iTemp > 0 ) Vec_IntWriteEntry( vMap, pNode->iTemp, Abc_ObjId(pNode) ); // remove old fanins Abc_NtkForEachNode( pNtk, pNode, i ) if ( !Sfm_NodeReadFixed(p, pNode->iTemp) ) Abc_ObjRemoveFanins( pNode ); // create new fanins vCover = Vec_IntAlloc( 1 << 16 ); Abc_NtkForEachNode( pNtk, pNode, i ) { if ( pNode->iTemp == 0 || Sfm_NodeReadFixed(p, pNode->iTemp) ) continue; if ( !Sfm_NodeReadUsed(p, pNode->iTemp) ) { Abc_NtkDeleteObj( pNode ); continue; } // update fanins vArray = Sfm_NodeReadFanins( p, pNode->iTemp ); Vec_IntForEachEntry( vArray, Fanin, k ) Abc_ObjAddFanin( pNode, Abc_NtkObj(pNtk, Vec_IntEntry(vMap, Fanin)) ); pTruth = Sfm_NodeReadTruth( p, pNode->iTemp ); pNode->pData = Abc_SopCreateFromTruthIsop( (Mem_Flex_t *)pNtk->pManFunc, Vec_IntSize(vArray), pTruth, vCover ); assert( Abc_SopGetVarNum((char *)pNode->pData) == Vec_IntSize(vArray) ); } Vec_IntFree( vCover ); Vec_IntFree( vMap ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NtkPerformMfs( Abc_Ntk_t * pNtk, Sfm_Par_t * pPars ) { Sfm_Ntk_t * p; int nFaninMax, nNodes; assert( Abc_NtkIsLogic(pNtk) ); Abc_NtkSweep( pNtk, 0 ); // count fanouts nFaninMax = Abc_NtkGetFaninMax( pNtk ); if ( nFaninMax > 15 ) { Abc_Print( 1, "Currently \"mfs\" cannot process the network containing nodes with more than 15 fanins.\n" ); return 1; } if ( !Abc_NtkHasSop(pNtk) ) if ( !Abc_NtkToSop( pNtk, -1, ABC_INFINITY ) ) { printf( "Conversion to SOP has failed due to low resource limit.\n" ); return 0; } // collect information p = Abc_NtkExtractMfs( pNtk, pPars->nFirstFixed ); // perform optimization nNodes = Sfm_NtkPerform( p, pPars ); if ( nNodes == 0 ) { // Abc_Print( 1, "The network is not changed by \"mfs\".\n" ); } else { Abc_NtkInsertMfs( pNtk, p ); if( pPars->fVerbose ) Abc_Print( 1, "The network has %d nodes changed by \"mfs\".\n", nNodes ); } Sfm_NtkFree( p ); return 1; } /**Function************************************************************* Synopsis [Unrolls logic network while dropping some next-state functions.] Description [Returns the unrolled network.] SideEffects [] SeeAlso [] ***********************************************************************/ Abc_Ntk_t * Abc_NtkUnrollAndDrop( Abc_Ntk_t * p, int nFrames, int nFramesAdd, Vec_Int_t * vFlops, int * piPivot ) { Abc_Ntk_t * pNtk; Abc_Obj_t * pFanin, * pNode; Vec_Ptr_t * vNodes; int i, k, f, Value; assert( nFramesAdd >= 0 ); assert( Abc_NtkIsLogic(p) ); assert( Vec_IntSize(vFlops) == Abc_NtkLatchNum(p) ); *piPivot = -1; // start the network pNtk = Abc_NtkAlloc( p->ntkType, p->ntkFunc, 1 ); pNtk->pName = Extra_UtilStrsav(Abc_NtkName(p)); // add CIs for the new network Abc_NtkForEachCi( p, pNode, i ) pNode->pCopy = Abc_NtkCreatePi( pNtk ); // iterate unrolling vNodes = Abc_NtkDfs( p, 0 ); for ( f = 0; f <= nFrames + nFramesAdd; f++ ) { if ( f > 0 ) { Abc_NtkForEachPi( p, pNode, i ) pNode->pCopy = Abc_NtkCreatePi( pNtk ); } Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i ) { Abc_NtkDupObj( pNtk, pNode, 0 ); Abc_ObjForEachFanin( pNode, pFanin, k ) Abc_ObjAddFanin( pNode->pCopy, pFanin->pCopy ); } Abc_NtkForEachCo( p, pNode, i ) pNode->pCopy = Abc_ObjFanin0(pNode)->pCopy; Abc_NtkForEachPo( p, pNode, i ) Abc_ObjAddFanin( Abc_NtkCreatePo(pNtk), pNode->pCopy ); // add buffers if ( f == 0 ) { *piPivot = Abc_NtkObjNum(pNtk); // Abc_NtkForEachLatchInput( p, pNode, i ) // pNode->pCopy = Abc_NtkCreateNodeBuf( pNtk, pNode->pCopy ); } // transfer to flop outputs Abc_NtkForEachLatch( p, pNode, i ) Abc_ObjFanout0(pNode)->pCopy = Abc_ObjFanin0(pNode)->pCopy; // add final POs if ( f > nFramesAdd ) { Vec_IntForEachEntry( vFlops, Value, i ) { if ( Value == 0 ) continue; pNode = Abc_NtkCo( p, Abc_NtkPoNum(p) + i ); Abc_ObjAddFanin( Abc_NtkCreatePo(pNtk), pNode->pCopy ); } } } Vec_PtrFree( vNodes ); Abc_NtkAddDummyPiNames( pNtk ); Abc_NtkAddDummyPoNames( pNtk ); // perform combinational cleanup Abc_NtkCleanup( pNtk, 0 ); if ( !Abc_NtkCheck( pNtk ) ) fprintf( stdout, "Abc_NtkCreateFromNode(): Network check has failed.\n" ); return pNtk; } /**Function************************************************************* Synopsis [Updates the original network to include optimized nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NtkReinsertNodes( Abc_Ntk_t * p, Abc_Ntk_t * pNtk, int iPivot ) { Abc_Obj_t * pNode, * pNodeNew, * pFaninNew; Vec_Ptr_t * vNodes; int i, k; assert( Abc_NtkIsLogic(p) ); assert( Abc_NtkCiNum(p) <= Abc_NtkCiNum(pNtk) ); vNodes = Abc_NtkDfs( p, 0 ); // clean old network Abc_NtkCleanCopy( p ); Abc_NtkForEachNode( p, pNode, i ) { Abc_ObjRemoveFanins( pNode ); pNode->pData = Abc_SopRegister( (Mem_Flex_t *)p->pManFunc, (char *)" 0\n" ); } // map CIs Abc_NtkForEachCi( p, pNode, i ) Abc_NtkCi(pNtk, i)->pCopy = pNode; // map internal nodes assert( Vec_PtrSize(vNodes) + Abc_NtkCiNum(p) + Abc_NtkPoNum(p) == iPivot ); Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i ) { pNodeNew = Abc_NtkObj( pNtk, Abc_NtkCiNum(p) + i + 1 ); if ( pNodeNew == NULL ) continue; pNodeNew->pCopy = pNode; } // connect internal nodes Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i ) { pNodeNew = Abc_NtkObj( pNtk, Abc_NtkCiNum(p) + i + 1 ); if ( pNodeNew == NULL ) continue; assert( pNodeNew->pCopy == pNode ); Abc_ObjForEachFanin( pNodeNew, pFaninNew, k ) Abc_ObjAddFanin( pNodeNew->pCopy, pFaninNew->pCopy ); pNode->pData = Abc_SopRegister( (Mem_Flex_t *)p->pManFunc, (char *)pNodeNew->pData ); } Vec_PtrFree( vNodes ); } /**Function************************************************************* Synopsis [Performs MFS for the unrolled network.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NtkMfsAfterICheck( Abc_Ntk_t * p, int nFrames, int nFramesAdd, Vec_Int_t * vFlops, Sfm_Par_t * pPars ) { Sfm_Ntk_t * pp; int nFaninMax, nNodes; Abc_Ntk_t * pNtk; int iPivot; assert( Abc_NtkIsLogic(p) ); // count fanouts nFaninMax = Abc_NtkGetFaninMax( p ); if ( nFaninMax > 15 ) { Abc_Print( 1, "Currently \"mfs\" cannot process the network containing nodes with more than 15 fanins.\n" ); return 0; } if ( !Abc_NtkHasSop(p) ) Abc_NtkToSop( p, -1, ABC_INFINITY ); // derive unfolded network pNtk = Abc_NtkUnrollAndDrop( p, nFrames, nFramesAdd, vFlops, &iPivot ); Io_WriteBlifLogic( pNtk, "unroll_dump.blif", 0 ); // collect information pp = Abc_NtkExtractMfs2( pNtk, iPivot ); // perform optimization nNodes = Sfm_NtkPerform( pp, pPars ); if ( nNodes == 0 ) { // Abc_Print( 1, "The network is not changed by \"mfs\".\n" ); } else { Abc_NtkInsertMfs( pNtk, pp ); if( pPars->fVerbose ) Abc_Print( 1, "The network has %d nodes changed by \"mfs\".\n", nNodes ); Abc_NtkReinsertNodes( p, pNtk, iPivot ); } Abc_NtkDelete( pNtk ); Sfm_NtkFree( pp ); // perform final sweep Abc_NtkSweep( p, 0 ); if ( !Abc_NtkHasSop(p) ) Abc_NtkToSop( p, -1, ABC_INFINITY ); return 1; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END