| /**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 |
| |
