/**CFile**************************************************************** FileName [abcRewrite.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [Network and node package.] Synopsis [Technology-independent resynthesis of the AIG based on DAG aware rewriting.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - June 20, 2005.] Revision [$Id: abcRewrite.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] ***********************************************************************/ #include "base/abc/abc.h" #include "opt/rwr/rwr.h" #include "bool/dec/dec.h" ABC_NAMESPACE_IMPL_START /* The ideas realized in this package are inspired by the paper: Per Bjesse, Arne Boralv, "DAG-aware circuit compression for formal verification", Proc. ICCAD 2004, pp. 42-49. */ //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// static Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk ); static void Abc_NodePrintCuts( Abc_Obj_t * pNode ); static void Abc_ManShowCutCone( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves ); extern void Abc_PlaceBegin( Abc_Ntk_t * pNtk ); extern void Abc_PlaceEnd( Abc_Ntk_t * pNtk ); extern void Abc_PlaceUpdate( Vec_Ptr_t * vAddedCells, Vec_Ptr_t * vUpdatedNets ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Performs incremental rewriting of the AIG.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NtkRewrite( Abc_Ntk_t * pNtk, int fUpdateLevel, int fUseZeros, int fVerbose, int fVeryVerbose, int fPlaceEnable ) { extern void Dec_GraphUpdateNetwork( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int fUpdateLevel, int nGain ); ProgressBar * pProgress; Cut_Man_t * pManCut; Rwr_Man_t * pManRwr; Abc_Obj_t * pNode; // Vec_Ptr_t * vAddedCells = NULL, * vUpdatedNets = NULL; Dec_Graph_t * pGraph; int i, nNodes, nGain, fCompl; abctime clk, clkStart = Abc_Clock(); assert( Abc_NtkIsStrash(pNtk) ); // cleanup the AIG Abc_AigCleanup((Abc_Aig_t *)pNtk->pManFunc); /* { Vec_Vec_t * vParts; vParts = Abc_NtkPartitionSmart( pNtk, 50, 1 ); Vec_VecFree( vParts ); } */ // start placement package // if ( fPlaceEnable ) // { // Abc_PlaceBegin( pNtk ); // vAddedCells = Abc_AigUpdateStart( pNtk->pManFunc, &vUpdatedNets ); // } // start the rewriting manager pManRwr = Rwr_ManStart( 0 ); if ( pManRwr == NULL ) return 0; // compute the reverse levels if level update is requested if ( fUpdateLevel ) Abc_NtkStartReverseLevels( pNtk, 0 ); // start the cut manager clk = Abc_Clock(); pManCut = Abc_NtkStartCutManForRewrite( pNtk ); Rwr_ManAddTimeCuts( pManRwr, Abc_Clock() - clk ); pNtk->pManCut = pManCut; if ( fVeryVerbose ) Rwr_ScoresClean( pManRwr ); // resynthesize each node once pManRwr->nNodesBeg = Abc_NtkNodeNum(pNtk); nNodes = Abc_NtkObjNumMax(pNtk); pProgress = Extra_ProgressBarStart( stdout, nNodes ); Abc_NtkForEachNode( pNtk, pNode, i ) { Extra_ProgressBarUpdate( pProgress, i, NULL ); // stop if all nodes have been tried once if ( i >= nNodes ) break; // skip persistant nodes if ( Abc_NodeIsPersistant(pNode) ) continue; // skip the nodes with many fanouts if ( Abc_ObjFanoutNum(pNode) > 1000 ) continue; // for each cut, try to resynthesize it nGain = Rwr_NodeRewrite( pManRwr, pManCut, pNode, fUpdateLevel, fUseZeros, fPlaceEnable ); if ( !(nGain > 0 || (nGain == 0 && fUseZeros)) ) continue; // if we end up here, a rewriting step is accepted // get hold of the new subgraph to be added to the AIG pGraph = (Dec_Graph_t *)Rwr_ManReadDecs(pManRwr); fCompl = Rwr_ManReadCompl(pManRwr); // reset the array of the changed nodes if ( fPlaceEnable ) Abc_AigUpdateReset( (Abc_Aig_t *)pNtk->pManFunc ); // complement the FF if needed if ( fCompl ) Dec_GraphComplement( pGraph ); clk = Abc_Clock(); Dec_GraphUpdateNetwork( pNode, pGraph, fUpdateLevel, nGain ); Rwr_ManAddTimeUpdate( pManRwr, Abc_Clock() - clk ); if ( fCompl ) Dec_GraphComplement( pGraph ); // use the array of changed nodes to update placement // if ( fPlaceEnable ) // Abc_PlaceUpdate( vAddedCells, vUpdatedNets ); } Extra_ProgressBarStop( pProgress ); Rwr_ManAddTimeTotal( pManRwr, Abc_Clock() - clkStart ); // print stats pManRwr->nNodesEnd = Abc_NtkNodeNum(pNtk); if ( fVerbose ) Rwr_ManPrintStats( pManRwr ); // Rwr_ManPrintStatsFile( pManRwr ); if ( fVeryVerbose ) Rwr_ScoresReport( pManRwr ); // delete the managers Rwr_ManStop( pManRwr ); Cut_ManStop( pManCut ); pNtk->pManCut = NULL; // start placement package // if ( fPlaceEnable ) // { // Abc_PlaceEnd( pNtk ); // Abc_AigUpdateStop( pNtk->pManFunc ); // } // put the nodes into the DFS order and reassign their IDs { // abctime clk = Abc_Clock(); Abc_NtkReassignIds( pNtk ); // ABC_PRT( "time", Abc_Clock() - clk ); } // Abc_AigCheckFaninOrder( pNtk->pManFunc ); // fix the levels if ( fUpdateLevel ) Abc_NtkStopReverseLevels( pNtk ); else Abc_NtkLevel( pNtk ); // check if ( !Abc_NtkCheck( pNtk ) ) { printf( "Abc_NtkRewrite: The network check has failed.\n" ); return 0; } return 1; } /**Function************************************************************* Synopsis [Starts the cut manager for rewriting.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk ) { static Cut_Params_t Params, * pParams = &Params; Cut_Man_t * pManCut; Abc_Obj_t * pObj; int i; // start the cut manager memset( pParams, 0, sizeof(Cut_Params_t) ); pParams->nVarsMax = 4; // the max cut size ("k" of the k-feasible cuts) pParams->nKeepMax = 250; // the max number of cuts kept at a node pParams->fTruth = 1; // compute truth tables pParams->fFilter = 1; // filter dominated cuts pParams->fSeq = 0; // compute sequential cuts pParams->fDrop = 0; // drop cuts on the fly pParams->fVerbose = 0; // the verbosiness flag pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); pManCut = Cut_ManStart( pParams ); if ( pParams->fDrop ) Cut_ManSetFanoutCounts( pManCut, Abc_NtkFanoutCounts(pNtk) ); // set cuts for PIs Abc_NtkForEachCi( pNtk, pObj, i ) if ( Abc_ObjFanoutNum(pObj) > 0 ) Cut_NodeSetTriv( pManCut, pObj->Id ); return pManCut; } /**Function************************************************************* Synopsis [Prints the cuts at the nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NodePrintCuts( Abc_Obj_t * pNode ) { Vec_Ptr_t * vCuts; Cut_Cut_t * pCut; int k; printf( "\nNode %s\n", Abc_ObjName(pNode) ); vCuts = (Vec_Ptr_t *)pNode->pCopy; Vec_PtrForEachEntry( Cut_Cut_t *, vCuts, pCut, k ) { Extra_PrintBinary( stdout, (unsigned *)&pCut->uSign, 16 ); printf( " " ); Cut_CutPrint( pCut, 0 ); printf( "\n" ); } } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_ManRewritePrintDivs( Vec_Ptr_t * vDivs, int nLeaves ) { Abc_Obj_t * pFanin, * pNode, * pRoot; int i, k; pRoot = (Abc_Obj_t *)Vec_PtrEntryLast(vDivs); // print the nodes Vec_PtrForEachEntry( Abc_Obj_t *, vDivs, pNode, i ) { if ( i < nLeaves ) { printf( "%6d : %c\n", pNode->Id, 'a'+i ); continue; } printf( "%6d : %2d = ", pNode->Id, i ); // find the first fanin Vec_PtrForEachEntry( Abc_Obj_t *, vDivs, pFanin, k ) if ( Abc_ObjFanin0(pNode) == pFanin ) break; if ( k < nLeaves ) printf( "%c", 'a' + k ); else printf( "%d", k ); printf( "%s ", Abc_ObjFaninC0(pNode)? "\'" : "" ); // find the second fanin Vec_PtrForEachEntry( Abc_Obj_t *, vDivs, pFanin, k ) if ( Abc_ObjFanin1(pNode) == pFanin ) break; if ( k < nLeaves ) printf( "%c", 'a' + k ); else printf( "%d", k ); printf( "%s ", Abc_ObjFaninC1(pNode)? "\'" : "" ); if ( pNode == pRoot ) printf( " root" ); printf( "\n" ); } printf( "\n" ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_ManShowCutCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vDivs ) { if ( Abc_NodeIsTravIdCurrent(pNode) ) return; Abc_NodeSetTravIdCurrent(pNode); Abc_ManShowCutCone_rec( Abc_ObjFanin0(pNode), vDivs ); Abc_ManShowCutCone_rec( Abc_ObjFanin1(pNode), vDivs ); Vec_PtrPush( vDivs, pNode ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_ManShowCutCone( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves ) { Abc_Ntk_t * pNtk = pNode->pNtk; Abc_Obj_t * pObj; Vec_Ptr_t * vDivs; int i; vDivs = Vec_PtrAlloc( 100 ); Abc_NtkIncrementTravId( pNtk ); Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i ) { Abc_NodeSetTravIdCurrent( Abc_ObjRegular(pObj) ); Vec_PtrPush( vDivs, Abc_ObjRegular(pObj) ); } Abc_ManShowCutCone_rec( pNode, vDivs ); Abc_ManRewritePrintDivs( vDivs, Vec_PtrSize(vLeaves) ); Vec_PtrFree( vDivs ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_RwrExpWithCut_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, int fUseA ) { if ( Vec_PtrFind(vLeaves, pNode) >= 0 || Vec_PtrFind(vLeaves, Abc_ObjNot(pNode)) >= 0 ) { if ( fUseA ) Abc_ObjRegular(pNode)->fMarkA = 1; else Abc_ObjRegular(pNode)->fMarkB = 1; return; } assert( Abc_ObjIsNode(pNode) ); Abc_RwrExpWithCut_rec( Abc_ObjFanin0(pNode), vLeaves, fUseA ); Abc_RwrExpWithCut_rec( Abc_ObjFanin1(pNode), vLeaves, fUseA ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_RwrExpWithCut( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves ) { Abc_Obj_t * pObj; int i, CountA, CountB; Abc_RwrExpWithCut_rec( Abc_ObjFanin0(pNode), vLeaves, 1 ); Abc_RwrExpWithCut_rec( Abc_ObjFanin1(pNode), vLeaves, 0 ); CountA = CountB = 0; Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i ) { CountA += Abc_ObjRegular(pObj)->fMarkA; CountB += Abc_ObjRegular(pObj)->fMarkB; Abc_ObjRegular(pObj)->fMarkA = 0; Abc_ObjRegular(pObj)->fMarkB = 0; } printf( "(%d,%d:%d) ", CountA, CountB, CountA+CountB-Vec_PtrSize(vLeaves) ); } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END