diff options
Diffstat (limited to 'src/opt/rwr/rwrEva.c')
| -rw-r--r-- | src/opt/rwr/rwrEva.c | 431 |
1 files changed, 24 insertions, 407 deletions
diff --git a/src/opt/rwr/rwrEva.c b/src/opt/rwr/rwrEva.c index 396a659c..c934dfd8 100644 --- a/src/opt/rwr/rwrEva.c +++ b/src/opt/rwr/rwrEva.c @@ -25,13 +25,10 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static Dec_Graph_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut, Vec_Ptr_t * vFaninsCur, int nNodesSaved, int LevelMax, int * pGainBest, int fPlaceEnable ); -static int Rwr_CutIsBoolean( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves ); -static int Rwr_CutCountNumNodes( Abc_Obj_t * pObj, Cut_Cut_t * pCut ); -static int Rwr_NodeGetDepth_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves ); +static Dec_Graph_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut, Vec_Ptr_t * vFaninsCur, int nNodesSaved, int LevelMax, int * pGainBest ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// +/// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -52,35 +49,27 @@ static int Rwr_NodeGetDepth_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves ); SeeAlso [] ***********************************************************************/ -int Rwr_NodeRewrite( Rwr_Man_t * p, Cut_Man_t * pManCut, Abc_Obj_t * pNode, int fUpdateLevel, int fUseZeros, int fPlaceEnable ) +int Rwr_NodeRewrite( Rwr_Man_t * p, Cut_Man_t * pManCut, Abc_Obj_t * pNode, int fUseZeros ) { int fVeryVerbose = 0; Dec_Graph_t * pGraph; - Cut_Cut_t * pCut;//, * pTemp; + Cut_Cut_t * pCut; Abc_Obj_t * pFanin; - unsigned uPhase, uTruthBest, uTruth; + unsigned uPhase, uTruthBest; char * pPerm; - int Required, nNodesSaved, nNodesSaveCur; + int Required, nNodesSaved; int i, GainCur, GainBest = -1; - int clk, clk2;//, Counter; + int clk, clk2; p->nNodesConsidered++; // get the required times - Required = fUpdateLevel? Abc_ObjRequiredLevel(pNode) : ABC_INFINITY; - + Required = Abc_NodeReadRequiredLevel( pNode ); // get the node's cuts clk = clock(); - pCut = (Cut_Cut_t *)Abc_NodeGetCutsRecursive( pManCut, pNode, 0, 0 ); + pCut = (Cut_Cut_t *)Abc_NodeGetCutsRecursive( pManCut, pNode ); assert( pCut != NULL ); p->timeCut += clock() - clk; -//printf( " %d", Rwr_CutCountNumNodes(pNode, pCut) ); -/* - Counter = 0; - for ( pTemp = pCut->pNext; pTemp; pTemp = pTemp->pNext ) - Counter++; - printf( "%d ", Counter ); -*/ // go through the cuts clk = clock(); for ( pCut = pCut->pNext; pCut; pCut = pCut->pNext ) @@ -88,12 +77,9 @@ clk = clock(); // consider only 4-input cuts if ( pCut->nLeaves < 4 ) continue; -// Cut_CutPrint( pCut, 0 ), printf( "\n" ); - // get the fanin permutation - uTruth = 0xFFFF & *Cut_CutReadTruth(pCut); - pPerm = p->pPerms4[ p->pPerms[uTruth] ]; - uPhase = p->pPhases[uTruth]; + pPerm = p->pPerms4[ p->pPerms[pCut->uTruth] ]; + uPhase = p->pPhases[pCut->uTruth]; // collect fanins with the corresponding permutation/phase Vec_PtrClear( p->vFaninsCur ); Vec_PtrFill( p->vFaninsCur, (int)pCut->nLeaves, 0 ); @@ -112,48 +98,29 @@ clk = clock(); } p->nCutsGood++; - { - int Counter = 0; - Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i ) - if ( Abc_ObjFanoutNum(Abc_ObjRegular(pFanin)) == 1 ) - Counter++; - if ( Counter > 2 ) - continue; - } - -clk2 = clock(); -/* - printf( "Considering: (" ); - Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i ) - printf( "%d ", Abc_ObjFanoutNum(Abc_ObjRegular(pFanin)) ); - printf( ")\n" ); -*/ // mark the fanin boundary Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i ) Abc_ObjRegular(pFanin)->vFanouts.nSize++; - // label MFFC with current ID Abc_NtkIncrementTravId( pNode->pNtk ); - nNodesSaved = Abc_NodeMffcLabelAig( pNode ); + nNodesSaved = Abc_NodeMffcLabel( pNode ); // unmark the fanin boundary Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i ) Abc_ObjRegular(pFanin)->vFanouts.nSize--; -p->timeMffc += clock() - clk2; // evaluate the cut clk2 = clock(); - pGraph = Rwr_CutEvaluate( p, pNode, pCut, p->vFaninsCur, nNodesSaved, Required, &GainCur, fPlaceEnable ); + pGraph = Rwr_CutEvaluate( p, pNode, pCut, p->vFaninsCur, nNodesSaved, Required, &GainCur ); p->timeEval += clock() - clk2; // check if the cut is better than the current best one if ( pGraph != NULL && GainBest < GainCur ) { // save this form - nNodesSaveCur = nNodesSaved; GainBest = GainCur; p->pGraph = pGraph; p->fCompl = ((uPhase & (1<<4)) > 0); - uTruthBest = 0xFFFF & *Cut_CutReadTruth(pCut); + uTruthBest = pCut->uTruth; // collect fanins in the Vec_PtrClear( p->vFanins ); Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i ) @@ -164,69 +131,22 @@ p->timeRes += clock() - clk; if ( GainBest == -1 ) return -1; -/* - if ( GainBest > 0 ) - { - printf( "Class %d ", p->pMap[uTruthBest] ); - printf( "Gain = %d. Node %d : ", GainBest, pNode->Id ); - Vec_PtrForEachEntry( p->vFanins, pFanin, i ) - printf( "%d ", Abc_ObjRegular(pFanin)->Id ); - Dec_GraphPrint( stdout, p->pGraph, NULL, NULL ); - printf( "\n" ); - } -*/ - -// printf( "%d", nNodesSaveCur - GainBest ); -/* - if ( GainBest > 0 ) - { - if ( Rwr_CutIsBoolean( pNode, p->vFanins ) ) - printf( "b" ); - else - { - printf( "Node %d : ", pNode->Id ); - Vec_PtrForEachEntry( p->vFanins, pFanin, i ) - printf( "%d ", Abc_ObjRegular(pFanin)->Id ); - printf( "a" ); - } - } -*/ -/* - if ( GainBest > 0 ) - if ( p->fCompl ) - printf( "c" ); - else - printf( "." ); -*/ // copy the leaves Vec_PtrForEachEntry( p->vFanins, pFanin, i ) Dec_GraphNode(p->pGraph, i)->pFunc = pFanin; -/* - printf( "(" ); - Vec_PtrForEachEntry( p->vFanins, pFanin, i ) - printf( " %d", Abc_ObjRegular(pFanin)->vFanouts.nSize - 1 ); - printf( " ) " ); -*/ -// printf( "%d ", Rwr_NodeGetDepth_rec( pNode, p->vFanins ) ); p->nScores[p->pMap[uTruthBest]]++; + p->nNodesRewritten++; p->nNodesGained += GainBest; - if ( fUseZeros || GainBest > 0 ) - { - p->nNodesRewritten++; - } // report the progress - if ( fVeryVerbose && GainBest > 0 ) + if ( fVeryVerbose ) { printf( "Node %6s : ", Abc_ObjName(pNode) ); printf( "Fanins = %d. ", p->vFanins->nSize ); - printf( "Save = %d. ", nNodesSaveCur ); - printf( "Add = %d. ", nNodesSaveCur-GainBest ); - printf( "GAIN = %d. ", GainBest ); - printf( "Cone = %d. ", p->pGraph? Dec_GraphNodeNum(p->pGraph) : 0 ); - printf( "Class = %d. ", p->pMap[uTruthBest] ); + printf( "Cone = %2d. ", Dec_GraphNodeNum(p->pGraph) ); + printf( "GAIN = %2d. ", GainBest ); printf( "\n" ); } return GainBest; @@ -243,22 +163,17 @@ p->timeRes += clock() - clk; SeeAlso [] ***********************************************************************/ -Dec_Graph_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut, Vec_Ptr_t * vFaninsCur, int nNodesSaved, int LevelMax, int * pGainBest, int fPlaceEnable ) +Dec_Graph_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut, Vec_Ptr_t * vFaninsCur, int nNodesSaved, int LevelMax, int * pGainBest ) { - extern int Dec_GraphToNetworkCount( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int NodeMax, int LevelMax ); Vec_Ptr_t * vSubgraphs; Dec_Graph_t * pGraphBest, * pGraphCur; Rwr_Node_t * pNode, * pFanin; int nNodesAdded, GainBest, i, k; - unsigned uTruth; - float CostBest;//, CostCur; // find the matching class of subgraphs - uTruth = 0xFFFF & *Cut_CutReadTruth(pCut); - vSubgraphs = Vec_VecEntry( p->vClasses, p->pMap[uTruth] ); + vSubgraphs = Vec_VecEntry( p->vClasses, p->pMap[pCut->uTruth] ); p->nSubgraphs += vSubgraphs->nSize; // determine the best subgraph GainBest = -1; - CostBest = ABC_INFINITY; Vec_PtrForEachEntry( vSubgraphs, pNode, i ) { // get the current graph @@ -271,58 +186,11 @@ Dec_Graph_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCu if ( nNodesAdded == -1 ) continue; assert( nNodesSaved >= nNodesAdded ); -/* - // evaluate the cut - if ( fPlaceEnable ) - { - extern float Abc_PlaceEvaluateCut( Abc_Obj_t * pRoot, Vec_Ptr_t * vFanins ); - - float Alpha = 0.5; // ??? - float PlaceCost; - - // get the placement cost of the cut - PlaceCost = Abc_PlaceEvaluateCut( pRoot, vFaninsCur ); - - // get the weigted cost of the cut - CostCur = nNodesSaved - nNodesAdded + Alpha * PlaceCost; - - // do not allow uphill moves - if ( nNodesSaved - nNodesAdded < 0 ) - continue; - - // decide what cut to use - if ( CostBest > CostCur ) - { - GainBest = nNodesSaved - nNodesAdded; // pure node cost - CostBest = CostCur; // cost with placement - pGraphBest = pGraphCur; // subgraph to be used for rewriting - - // score the graph - if ( nNodesSaved - nNodesAdded > 0 ) - { - pNode->nScore++; - pNode->nGain += GainBest; - pNode->nAdded += nNodesAdded; - } - } - } - else -*/ + // count the gain at this node + if ( GainBest < nNodesSaved - nNodesAdded ) { - // count the gain at this node - if ( GainBest < nNodesSaved - nNodesAdded ) - { - GainBest = nNodesSaved - nNodesAdded; - pGraphBest = pGraphCur; - - // score the graph - if ( nNodesSaved - nNodesAdded > 0 ) - { - pNode->nScore++; - pNode->nGain += GainBest; - pNode->nAdded += nNodesAdded; - } - } + GainBest = nNodesSaved - nNodesAdded; + pGraphBest = pGraphCur; } } if ( GainBest == -1 ) @@ -331,257 +199,6 @@ Dec_Graph_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCu return pGraphBest; } -/**Function************************************************************* - - Synopsis [Checks the type of the cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Rwr_CutIsBoolean_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves, int fMarkA ) -{ - if ( Vec_PtrFind(vLeaves, pObj) >= 0 || Vec_PtrFind(vLeaves, Abc_ObjNot(pObj)) >= 0 ) - { - if ( fMarkA ) - pObj->fMarkA = 1; - else - pObj->fMarkB = 1; - return; - } - assert( !Abc_ObjIsCi(pObj) ); - Rwr_CutIsBoolean_rec( Abc_ObjFanin0(pObj), vLeaves, fMarkA ); - Rwr_CutIsBoolean_rec( Abc_ObjFanin1(pObj), vLeaves, fMarkA ); -} - -/**Function************************************************************* - - Synopsis [Checks the type of the cut.] - - Description [Returns 1(0) if the cut is Boolean (algebraic).] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Rwr_CutIsBoolean( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves ) -{ - Abc_Obj_t * pTemp; - int i, RetValue; - Vec_PtrForEachEntry( vLeaves, pTemp, i ) - { - pTemp = Abc_ObjRegular(pTemp); - assert( !pTemp->fMarkA && !pTemp->fMarkB ); - } - Rwr_CutIsBoolean_rec( Abc_ObjFanin0(pObj), vLeaves, 1 ); - Rwr_CutIsBoolean_rec( Abc_ObjFanin1(pObj), vLeaves, 0 ); - RetValue = 0; - Vec_PtrForEachEntry( vLeaves, pTemp, i ) - { - pTemp = Abc_ObjRegular(pTemp); - RetValue |= pTemp->fMarkA && pTemp->fMarkB; - pTemp->fMarkA = pTemp->fMarkB = 0; - } - return RetValue; -} - - -/**Function************************************************************* - - Synopsis [Count the nodes in the cut space of a node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Rwr_CutCountNumNodes_rec( Abc_Obj_t * pObj, Cut_Cut_t * pCut, Vec_Ptr_t * vNodes ) -{ - int i; - for ( i = 0; i < (int)pCut->nLeaves; i++ ) - if ( pCut->pLeaves[i] == pObj->Id ) - { - // check if the node is collected - if ( pObj->fMarkC == 0 ) - { - pObj->fMarkC = 1; - Vec_PtrPush( vNodes, pObj ); - } - return; - } - assert( Abc_ObjIsNode(pObj) ); - // check if the node is collected - if ( pObj->fMarkC == 0 ) - { - pObj->fMarkC = 1; - Vec_PtrPush( vNodes, pObj ); - } - // traverse the fanins - Rwr_CutCountNumNodes_rec( Abc_ObjFanin0(pObj), pCut, vNodes ); - Rwr_CutCountNumNodes_rec( Abc_ObjFanin1(pObj), pCut, vNodes ); -} - -/**Function************************************************************* - - Synopsis [Count the nodes in the cut space of a node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Rwr_CutCountNumNodes( Abc_Obj_t * pObj, Cut_Cut_t * pCut ) -{ - Vec_Ptr_t * vNodes; - int i, Counter; - // collect all nodes - vNodes = Vec_PtrAlloc( 100 ); - for ( pCut = pCut->pNext; pCut; pCut = pCut->pNext ) - Rwr_CutCountNumNodes_rec( pObj, pCut, vNodes ); - // clean all nodes - Vec_PtrForEachEntry( vNodes, pObj, i ) - pObj->fMarkC = 0; - // delete and return - Counter = Vec_PtrSize(vNodes); - Vec_PtrFree( vNodes ); - return Counter; -} - - -/**Function************************************************************* - - Synopsis [Returns depth of the cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Rwr_NodeGetDepth_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves ) -{ - Abc_Obj_t * pLeaf; - int i, Depth0, Depth1; - if ( Abc_ObjIsCi(pObj) ) - return 0; - Vec_PtrForEachEntry( vLeaves, pLeaf, i ) - if ( pObj == Abc_ObjRegular(pLeaf) ) - return 0; - Depth0 = Rwr_NodeGetDepth_rec( Abc_ObjFanin0(pObj), vLeaves ); - Depth1 = Rwr_NodeGetDepth_rec( Abc_ObjFanin1(pObj), vLeaves ); - return 1 + ABC_MAX( Depth0, Depth1 ); -} - - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Rwr_ScoresClean( Rwr_Man_t * p ) -{ - Vec_Ptr_t * vSubgraphs; - Rwr_Node_t * pNode; - int i, k; - for ( i = 0; i < p->vClasses->nSize; i++ ) - { - vSubgraphs = Vec_VecEntry( p->vClasses, i ); - Vec_PtrForEachEntry( vSubgraphs, pNode, k ) - pNode->nScore = pNode->nGain = pNode->nAdded = 0; - } -} - -static int Gains[222]; - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Rwr_ScoresCompare( int * pNum1, int * pNum2 ) -{ - if ( Gains[*pNum1] > Gains[*pNum2] ) - return -1; - if ( Gains[*pNum1] < Gains[*pNum2] ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Rwr_ScoresReport( Rwr_Man_t * p ) -{ - extern void Ivy_TruthDsdComputePrint( unsigned uTruth ); - int Perm[222]; - Vec_Ptr_t * vSubgraphs; - Rwr_Node_t * pNode; - int i, iNew, k; - unsigned uTruth; - // collect total gains - assert( p->vClasses->nSize == 222 ); - for ( i = 0; i < p->vClasses->nSize; i++ ) - { - Perm[i] = i; - Gains[i] = 0; - vSubgraphs = Vec_VecEntry( p->vClasses, i ); - Vec_PtrForEachEntry( vSubgraphs, pNode, k ) - Gains[i] += pNode->nGain; - } - // sort the gains - qsort( Perm, 222, sizeof(int), (int (*)(const void *, const void *))Rwr_ScoresCompare ); - - // print classes - for ( i = 0; i < p->vClasses->nSize; i++ ) - { - iNew = Perm[i]; - if ( Gains[iNew] == 0 ) - break; - vSubgraphs = Vec_VecEntry( p->vClasses, iNew ); - printf( "CLASS %3d: Subgr = %3d. Total gain = %6d. ", iNew, Vec_PtrSize(vSubgraphs), Gains[iNew] ); - uTruth = (unsigned)p->pMapInv[iNew]; - Extra_PrintBinary( stdout, &uTruth, 16 ); - printf( " " ); - Ivy_TruthDsdComputePrint( (unsigned)p->pMapInv[iNew] | ((unsigned)p->pMapInv[iNew] << 16) ); - Vec_PtrForEachEntry( vSubgraphs, pNode, k ) - { - if ( pNode->nScore == 0 ) - continue; - printf( " %2d: S=%5d. A=%5d. G=%6d. ", k, pNode->nScore, pNode->nAdded, pNode->nGain ); - Dec_GraphPrint( stdout, (Dec_Graph_t *)pNode->pNext, NULL, NULL ); - } - } -} - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// |