diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 20:01:00 -0800 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 20:01:00 -0800 |
commit | 0c6505a26a537dc911b6566f82d759521e527c08 (patch) | |
tree | f2687995efd4943fe3b1307fce7ef5942d0a57b3 /src/base/abci/abcRewrite.c | |
parent | 4d30a1e4f1edecff86d5066ce4653a370e59e5e1 (diff) | |
download | abc-0c6505a26a537dc911b6566f82d759521e527c08.tar.gz abc-0c6505a26a537dc911b6566f82d759521e527c08.tar.bz2 abc-0c6505a26a537dc911b6566f82d759521e527c08.zip |
Version abc80130_2
Diffstat (limited to 'src/base/abci/abcRewrite.c')
-rw-r--r-- | src/base/abci/abcRewrite.c | 281 |
1 files changed, 252 insertions, 29 deletions
diff --git a/src/base/abci/abcRewrite.c b/src/base/abci/abcRewrite.c index ea221296..3b50107b 100644 --- a/src/base/abci/abcRewrite.c +++ b/src/base/abci/abcRewrite.c @@ -32,11 +32,16 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk, int fDrop ); +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 DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -50,31 +55,54 @@ static void Abc_NodePrintCuts( Abc_Obj_t * pNode ); SeeAlso [] ***********************************************************************/ -int Abc_NtkRewrite( Abc_Ntk_t * pNtk, int fUseZeros, int fVerbose ) +int Abc_NtkRewrite( Abc_Ntk_t * pNtk, int fUpdateLevel, int fUseZeros, int fVerbose, int fVeryVerbose, int fPlaceEnable ) { - int fDrop = 0; + extern void Dec_GraphUpdateNetwork( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, bool fUpdateLevel, int nGain ); ProgressBar * pProgress; Cut_Man_t * pManCut; Rwr_Man_t * pManRwr; Abc_Obj_t * pNode; - int i, nNodes, nGain; + Vec_Ptr_t * vAddedCells = NULL, * vUpdatedNets = NULL; + Dec_Graph_t * pGraph; + int i, nNodes, nGain, fCompl; int clk, clkStart = clock(); assert( Abc_NtkIsStrash(pNtk) ); // cleanup the AIG Abc_AigCleanup(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; - Abc_NtkStartReverseLevels( pNtk ); + // compute the reverse levels if level update is requested + if ( fUpdateLevel ) + Abc_NtkStartReverseLevels( pNtk, 0 ); // start the cut manager clk = clock(); - pManCut = Abc_NtkStartCutManForRewrite( pNtk, fDrop ); + pManCut = Abc_NtkStartCutManForRewrite( pNtk ); Rwr_ManAddTimeCuts( pManRwr, 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 ) @@ -83,34 +111,71 @@ Rwr_ManAddTimeCuts( pManRwr, clock() - clk ); // stop if all nodes have been tried once if ( i >= nNodes ) break; - // skip the constant node - if ( Abc_NodeIsConst(pNode) ) + // 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, fUseZeros ); - if ( nGain > 0 || nGain == 0 && fUseZeros ) - { - Dec_Graph_t * pGraph = Rwr_ManReadDecs(pManRwr); - int fCompl = Rwr_ManReadCompl(pManRwr); - // complement the FF if needed - if ( fCompl ) Dec_GraphComplement( pGraph ); - Dec_GraphUpdateNetwork( pNode, pGraph, nGain ); - if ( fCompl ) Dec_GraphComplement( pGraph ); - } + 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 = Rwr_ManReadDecs(pManRwr); + fCompl = Rwr_ManReadCompl(pManRwr); + + // reset the array of the changed nodes + if ( fPlaceEnable ) + Abc_AigUpdateReset( pNtk->pManFunc ); + + // complement the FF if needed + if ( fCompl ) Dec_GraphComplement( pGraph ); +clk = clock(); + Dec_GraphUpdateNetwork( pNode, pGraph, fUpdateLevel, nGain ); +Rwr_ManAddTimeUpdate( pManRwr, 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, 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; - Abc_NtkStopReverseLevels( pNtk ); + + // start placement package +// if ( fPlaceEnable ) +// { +// Abc_PlaceEnd( pNtk ); +// Abc_AigUpdateStop( pNtk->pManFunc ); +// } + + // put the nodes into the DFS order and reassign their IDs + { +// int clk = clock(); + Abc_NtkReassignIds( pNtk ); +// PRT( "time", clock() - clk ); + } +// Abc_AigCheckFaninOrder( pNtk->pManFunc ); + // fix the levels + if ( fUpdateLevel ) + Abc_NtkStopReverseLevels( pNtk ); + else + Abc_NtkLevel( pNtk ); // check if ( !Abc_NtkCheck( pNtk ) ) { @@ -132,7 +197,7 @@ Rwr_ManAddTimeTotal( pManRwr, clock() - clkStart ); SeeAlso [] ***********************************************************************/ -Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk, int fDrop ) +Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk ) { static Cut_Params_t Params, * pParams = &Params; Cut_Man_t * pManCut; @@ -143,10 +208,9 @@ Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk, int fDrop ) 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->fHash = 1; // hash cuts to detect unique - pParams->fFilter = 0; // filter dominated cuts + pParams->fFilter = 1; // filter dominated cuts pParams->fSeq = 0; // compute sequential cuts - pParams->fDrop = fDrop; // drop cuts on the fly + pParams->fDrop = 0; // drop cuts on the fly pParams->fVerbose = 0; // the verbosiness flag pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); pManCut = Cut_ManStart( pParams ); @@ -172,19 +236,178 @@ Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk, int fDrop ) ***********************************************************************/ void Abc_NodePrintCuts( Abc_Obj_t * pNode ) { + Vec_Ptr_t * vCuts; Cut_Cut_t * pCut; - unsigned uTruth; + int k; + printf( "\nNode %s\n", Abc_ObjName(pNode) ); - for ( pCut = (Cut_Cut_t *)pNode->pCopy; pCut; pCut = pCut->pNext ) + vCuts = (Vec_Ptr_t *)pNode->pCopy; + Vec_PtrForEachEntry( vCuts, pCut, k ) { - uTruth = pCut->uTruth; - Extra_PrintBinary( stdout, &uTruth, 16 ); + Extra_PrintBinary( stdout, (unsigned *)&pCut->uSign, 16 ); printf( " " ); - Cut_CutPrint( pCut ); + 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 = Vec_PtrEntryLast(vDivs); + // print the nodes + Vec_PtrForEachEntry( 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( 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( 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( 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( 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 /// //////////////////////////////////////////////////////////////////////// |