abc70930: src/base/abci/abcBalance.c Source File

00001 
00021 #include "abc.h"
00022 
00026  
00027 static void        Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate, bool fSelective, bool fUpdateLevel );
00028 static Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, Vec_Vec_t * vStorage, int Level, bool fDuplicate, bool fSelective, bool fUpdateLevel );
00029 static Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vSuper, int Level, int fDuplicate, bool fSelective );
00030 static int         Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, bool fDuplicate, bool fSelective );
00031 static void        Abc_NtkMarkCriticalNodes( Abc_Ntk_t * pNtk );
00032 static Vec_Ptr_t * Abc_NodeBalanceConeExor( Abc_Obj_t * pNode );
00033 
00034 
00038 
00050 Abc_Ntk_t * Abc_NtkBalance( Abc_Ntk_t * pNtk, bool fDuplicate, bool fSelective, bool fUpdateLevel )
00051 {
00052     extern void Abc_NtkHaigTranfer( Abc_Ntk_t * pNtkOld, Abc_Ntk_t * pNtkNew );
00053     Abc_Ntk_t * pNtkAig;
00054     assert( Abc_NtkIsStrash(pNtk) );
00055     // compute the required times
00056     if ( fSelective )
00057     {
00058         Abc_NtkStartReverseLevels( pNtk, 0 );
00059         Abc_NtkMarkCriticalNodes( pNtk );
00060     }
00061     // perform balancing
00062     pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );
00063     // transfer HAIG
00064     Abc_NtkHaigTranfer( pNtk, pNtkAig );
00065     // perform balancing
00066     Abc_NtkBalancePerform( pNtk, pNtkAig, fDuplicate, fSelective, fUpdateLevel );
00067     Abc_NtkFinalize( pNtk, pNtkAig );
00068     // undo the required times
00069     if ( fSelective )
00070     {
00071         Abc_NtkStopReverseLevels( pNtk );
00072         Abc_NtkCleanMarkA( pNtk );
00073     }
00074     if ( pNtk->pExdc )
00075         pNtkAig->pExdc = Abc_NtkDup( pNtk->pExdc );
00076     // make sure everything is okay
00077     if ( !Abc_NtkCheck( pNtkAig ) )
00078     {
00079         printf( "Abc_NtkBalance: The network check has failed.\n" );
00080         Abc_NtkDelete( pNtkAig );
00081         return NULL;
00082     }
00083     return pNtkAig;
00084 }
00085 
00097 void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate, bool fSelective, bool fUpdateLevel )
00098 {
00099     int fCheck = 1;
00100     ProgressBar * pProgress;
00101     Vec_Vec_t * vStorage;
00102     Abc_Obj_t * pNode, * pDriver;
00103     int i;
00104 
00105     // set the level of PIs of AIG according to the arrival times of the old network
00106     Abc_NtkSetNodeLevelsArrival( pNtk );
00107     // allocate temporary storage for supergates
00108     vStorage = Vec_VecStart( 10 );
00109     // perform balancing of POs
00110     pProgress = Extra_ProgressBarStart( stdout, Abc_NtkCoNum(pNtk) );
00111     Abc_NtkForEachCo( pNtk, pNode, i )
00112     {
00113         Extra_ProgressBarUpdate( pProgress, i, NULL );
00114         // strash the driver node
00115         pDriver = Abc_ObjFanin0(pNode);
00116         Abc_NodeBalance_rec( pNtkAig, pDriver, vStorage, 0, fDuplicate, fSelective, fUpdateLevel );
00117     }
00118     Extra_ProgressBarStop( pProgress );
00119     Vec_VecFree( vStorage );
00120 }
00121 
00137 int Abc_NodeBalanceFindLeft( Vec_Ptr_t * vSuper )
00138 {
00139     Abc_Obj_t * pNodeRight, * pNodeLeft;
00140     int Current;
00141     // if two or less nodes, pair with the first
00142     if ( Vec_PtrSize(vSuper) < 3 )
00143         return 0;
00144     // set the pointer to the one before the last
00145     Current = Vec_PtrSize(vSuper) - 2;
00146     pNodeRight = Vec_PtrEntry( vSuper, Current );
00147     // go through the nodes to the left of this one
00148     for ( Current--; Current >= 0; Current-- )
00149     {
00150         // get the next node on the left
00151         pNodeLeft = Vec_PtrEntry( vSuper, Current );
00152         // if the level of this node is different, quit the loop
00153         if ( Abc_ObjRegular(pNodeLeft)->Level != Abc_ObjRegular(pNodeRight)->Level )
00154             break;
00155     }
00156     Current++;    
00157     // get the node, for which the equality holds
00158     pNodeLeft = Vec_PtrEntry( vSuper, Current );
00159     assert( Abc_ObjRegular(pNodeLeft)->Level == Abc_ObjRegular(pNodeRight)->Level );
00160     return Current;
00161 }
00162 
00175 void Abc_NodeBalancePermute( Abc_Ntk_t * pNtkNew, Vec_Ptr_t * vSuper, int LeftBound )
00176 {
00177     Abc_Obj_t * pNode1, * pNode2, * pNode3;
00178     int RightBound, i;
00179     // get the right bound
00180     RightBound = Vec_PtrSize(vSuper) - 2;
00181     assert( LeftBound <= RightBound );
00182     if ( LeftBound == RightBound )
00183         return;
00184     // get the two last nodes
00185     pNode1 = Vec_PtrEntry( vSuper, RightBound + 1 );
00186     pNode2 = Vec_PtrEntry( vSuper, RightBound     );
00187     // find the first node that can be shared
00188     for ( i = RightBound; i >= LeftBound; i-- )
00189     {
00190         pNode3 = Vec_PtrEntry( vSuper, i );
00191         if ( Abc_AigAndLookup( pNtkNew->pManFunc, pNode1, pNode3 ) )
00192         {
00193             if ( pNode3 == pNode2 )
00194                 return;
00195             Vec_PtrWriteEntry( vSuper, i,          pNode2 );
00196             Vec_PtrWriteEntry( vSuper, RightBound, pNode3 );
00197             return;
00198         }
00199     }
00200 /*
00201     // we did not find the node to share, randomize choice
00202     {
00203         int Choice = rand() % (RightBound - LeftBound + 1);
00204         pNode3 = Vec_PtrEntry( vSuper, LeftBound + Choice );
00205         if ( pNode3 == pNode2 )
00206             return;
00207         Vec_PtrWriteEntry( vSuper, LeftBound + Choice, pNode2 );
00208         Vec_PtrWriteEntry( vSuper, RightBound,         pNode3 );
00209     }
00210 */
00211 }
00212 
00224 Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, Vec_Vec_t * vStorage, int Level, bool fDuplicate, bool fSelective, bool fUpdateLevel )
00225 {
00226     Abc_Aig_t * pMan = pNtkNew->pManFunc;
00227     Abc_Obj_t * pNodeNew, * pNode1, * pNode2;
00228     Vec_Ptr_t * vSuper;
00229     int i, LeftBound;
00230     assert( !Abc_ObjIsComplement(pNodeOld) );
00231     // return if the result if known
00232     if ( pNodeOld->pCopy )
00233         return pNodeOld->pCopy;
00234     assert( Abc_ObjIsNode(pNodeOld) );
00235     // get the implication supergate
00236 //    Abc_NodeBalanceConeExor( pNodeOld );
00237     vSuper = Abc_NodeBalanceCone( pNodeOld, vStorage, Level, fDuplicate, fSelective );
00238     if ( vSuper->nSize == 0 )
00239     { // it means that the supergate contains two nodes in the opposite polarity
00240         pNodeOld->pCopy = Abc_ObjNot(Abc_AigConst1(pNtkNew));
00241         return pNodeOld->pCopy;
00242     }
00243     // for each old node, derive the new well-balanced node
00244     for ( i = 0; i < vSuper->nSize; i++ )
00245     {
00246         pNodeNew = Abc_NodeBalance_rec( pNtkNew, Abc_ObjRegular(vSuper->pArray[i]), vStorage, Level + 1, fDuplicate, fSelective, fUpdateLevel );
00247         vSuper->pArray[i] = Abc_ObjNotCond( pNodeNew, Abc_ObjIsComplement(vSuper->pArray[i]) );
00248     }
00249     if ( vSuper->nSize < 2 )
00250         printf( "BUG!\n" );
00251     // sort the new nodes by level in the decreasing order
00252     Vec_PtrSort( vSuper, Abc_NodeCompareLevelsDecrease );
00253     // balance the nodes
00254     assert( vSuper->nSize > 1 );
00255     while ( vSuper->nSize > 1 )
00256     {
00257         // find the left bound on the node to be paired
00258         LeftBound = (!fUpdateLevel)? 0 : Abc_NodeBalanceFindLeft( vSuper );
00259         // find the node that can be shared (if no such node, randomize choice)
00260         Abc_NodeBalancePermute( pNtkNew, vSuper, LeftBound );
00261         // pull out the last two nodes
00262         pNode1 = Vec_PtrPop(vSuper);
00263         pNode2 = Vec_PtrPop(vSuper);
00264         Abc_VecObjPushUniqueOrderByLevel( vSuper, Abc_AigAnd(pMan, pNode1, pNode2) );
00265     }
00266     // make sure the balanced node is not assigned
00267     assert( pNodeOld->pCopy == NULL );
00268     // mark the old node with the new node
00269     pNodeOld->pCopy = vSuper->pArray[0];
00270     vSuper->nSize = 0;
00271 //    if ( Abc_ObjRegular(pNodeOld->pCopy) == Abc_AigConst1(pNtkNew) )
00272 //        printf( "Constant node\n" );
00273 //    assert( pNodeOld->Level >= Abc_ObjRegular(pNodeOld->pCopy)->Level );
00274     // update HAIG
00275     if ( Abc_ObjRegular(pNodeOld->pCopy)->pNtk->pHaig )
00276         Hop_ObjCreateChoice( pNodeOld->pEquiv, Abc_ObjRegular(pNodeOld->pCopy)->pEquiv );
00277     return pNodeOld->pCopy;
00278 }
00279 
00293 Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vStorage, int Level, int fDuplicate, bool fSelective )
00294 {
00295     Vec_Ptr_t * vNodes;
00296     int RetValue, i;
00297     assert( !Abc_ObjIsComplement(pNode) );
00298     // extend the storage
00299     if ( Vec_VecSize( vStorage ) <= Level )
00300         Vec_VecPush( vStorage, Level, 0 );
00301     // get the temporary array of nodes
00302     vNodes = Vec_VecEntry( vStorage, Level );
00303     Vec_PtrClear( vNodes );
00304     // collect the nodes in the implication supergate
00305     RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, fDuplicate, fSelective );
00306     assert( vNodes->nSize > 1 );
00307     // unmark the visited nodes
00308     for ( i = 0; i < vNodes->nSize; i++ )
00309         Abc_ObjRegular((Abc_Obj_t *)vNodes->pArray[i])->fMarkB = 0;
00310     // if we found the node and its complement in the same implication supergate, 
00311     // return empty set of nodes (meaning that we should use constant-0 node)
00312     if ( RetValue == -1 )
00313         vNodes->nSize = 0;
00314     return vNodes;
00315 }
00316 
00317 
00331 int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, bool fDuplicate, bool fSelective )
00332 {
00333     int RetValue1, RetValue2, i;
00334     // check if the node is visited
00335     if ( Abc_ObjRegular(pNode)->fMarkB )
00336     {
00337         // check if the node occurs in the same polarity
00338         for ( i = 0; i < vSuper->nSize; i++ )
00339             if ( vSuper->pArray[i] == pNode )
00340                 return 1;
00341         // check if the node is present in the opposite polarity
00342         for ( i = 0; i < vSuper->nSize; i++ )
00343             if ( vSuper->pArray[i] == Abc_ObjNot(pNode) )
00344                 return -1;
00345         assert( 0 );
00346         return 0;
00347     }
00348     // if the new node is complemented or a PI, another gate begins
00349     if ( !fFirst && (Abc_ObjIsComplement(pNode) || !Abc_ObjIsNode(pNode) || !fDuplicate && !fSelective && (Abc_ObjFanoutNum(pNode) > 1)) )
00350     {
00351         Vec_PtrPush( vSuper, pNode );
00352         Abc_ObjRegular(pNode)->fMarkB = 1;
00353         return 0;
00354     }
00355     assert( !Abc_ObjIsComplement(pNode) );
00356     assert( Abc_ObjIsNode(pNode) );
00357     // go through the branches
00358     RetValue1 = Abc_NodeBalanceCone_rec( Abc_ObjChild0(pNode), vSuper, 0, fDuplicate, fSelective );
00359     RetValue2 = Abc_NodeBalanceCone_rec( Abc_ObjChild1(pNode), vSuper, 0, fDuplicate, fSelective );
00360     if ( RetValue1 == -1 || RetValue2 == -1 )
00361         return -1;
00362     // return 1 if at least one branch has a duplicate
00363     return RetValue1 || RetValue2;
00364 }
00365 
00366 
00378 int Abc_NodeBalanceConeExor_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst )
00379 {
00380     int RetValue1, RetValue2, i;
00381     // check if the node occurs in the same polarity
00382     for ( i = 0; i < vSuper->nSize; i++ )
00383         if ( vSuper->pArray[i] == pNode )
00384             return 1;
00385     // if the new node is complemented or a PI, another gate begins
00386     if ( !fFirst && (!pNode->fExor || !Abc_ObjIsNode(pNode)) )
00387     {
00388         Vec_PtrPush( vSuper, pNode );
00389         return 0;
00390     }
00391     assert( !Abc_ObjIsComplement(pNode) );
00392     assert( Abc_ObjIsNode(pNode) );
00393     assert( pNode->fExor );
00394     // go through the branches
00395     RetValue1 = Abc_NodeBalanceConeExor_rec( Abc_ObjFanin0(Abc_ObjFanin0(pNode)), vSuper, 0 );
00396     RetValue2 = Abc_NodeBalanceConeExor_rec( Abc_ObjFanin1(Abc_ObjFanin0(pNode)), vSuper, 0 );
00397     if ( RetValue1 == -1 || RetValue2 == -1 )
00398         return -1;
00399     // return 1 if at least one branch has a duplicate
00400     return RetValue1 || RetValue2;
00401 }
00402 
00414 Vec_Ptr_t * Abc_NodeBalanceConeExor( Abc_Obj_t * pNode )
00415 {
00416     Vec_Ptr_t * vSuper;
00417     if ( !pNode->fExor )
00418         return NULL;
00419     vSuper = Vec_PtrAlloc( 10 );
00420     Abc_NodeBalanceConeExor_rec( pNode, vSuper, 1 );
00421     printf( "%d ", Vec_PtrSize(vSuper) );
00422     Vec_PtrFree( vSuper );
00423     return NULL;
00424 }
00425 
00426 
00427 
00439 Vec_Ptr_t * Abc_NodeFindCone_rec( Abc_Obj_t * pNode )
00440 {
00441     Vec_Ptr_t * vNodes;
00442     Abc_Obj_t * pNodeC, * pNodeT, * pNodeE;
00443     int RetValue, i;
00444     assert( !Abc_ObjIsComplement(pNode) );
00445     if ( Abc_ObjIsCi(pNode) )
00446         return NULL;
00447     // start the new array
00448     vNodes = Vec_PtrAlloc( 4 );
00449     // if the node is the MUX collect its fanins
00450     if ( Abc_NodeIsMuxType(pNode) )
00451     {
00452         pNodeC = Abc_NodeRecognizeMux( pNode, &pNodeT, &pNodeE );
00453         Vec_PtrPush( vNodes, Abc_ObjRegular(pNodeC) );
00454         Vec_PtrPushUnique( vNodes, Abc_ObjRegular(pNodeT) );
00455         Vec_PtrPushUnique( vNodes, Abc_ObjRegular(pNodeE) );
00456     }
00457     else
00458     {
00459         // collect the nodes in the implication supergate
00460         RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, 1, 0 );
00461         assert( vNodes->nSize > 1 );
00462         // unmark the visited nodes
00463         Vec_PtrForEachEntry( vNodes, pNode, i )
00464             Abc_ObjRegular(pNode)->fMarkB = 0;
00465         // if we found the node and its complement in the same implication supergate, 
00466         // return empty set of nodes (meaning that we should use constant-0 node)
00467         if ( RetValue == -1 )
00468             vNodes->nSize = 0;
00469     }
00470     // call for the fanin
00471     Vec_PtrForEachEntry( vNodes, pNode, i )
00472     {
00473         pNode = Abc_ObjRegular(pNode);
00474         if ( pNode->pCopy )
00475             continue;
00476         pNode->pCopy = (Abc_Obj_t *)Abc_NodeFindCone_rec( pNode );
00477     }
00478     return vNodes;
00479 }
00480 
00492 void Abc_NtkBalanceAttach( Abc_Ntk_t * pNtk )
00493 {
00494     Abc_Obj_t * pNode;
00495     int i;
00496     Abc_NtkCleanCopy( pNtk );
00497     Abc_NtkForEachCo( pNtk, pNode, i )
00498     {
00499         pNode = Abc_ObjFanin0(pNode);
00500         if ( pNode->pCopy )
00501             continue;
00502         pNode->pCopy = (Abc_Obj_t *)Abc_NodeFindCone_rec( pNode );
00503     }
00504 }
00505 
00517 void Abc_NtkBalanceDetach( Abc_Ntk_t * pNtk )
00518 {
00519     Abc_Obj_t * pNode;
00520     int i;
00521     Abc_NtkForEachNode( pNtk, pNode, i )
00522         if ( pNode->pCopy )
00523         {
00524             Vec_PtrFree( (Vec_Ptr_t *)pNode->pCopy );
00525             pNode->pCopy = NULL;
00526         }
00527 }
00528 
00540 int Abc_NtkBalanceLevel_rec( Abc_Obj_t * pNode )
00541 {
00542     Vec_Ptr_t * vSuper;
00543     Abc_Obj_t * pFanin;
00544     int i, LevelMax;
00545     assert( !Abc_ObjIsComplement(pNode) );
00546     if ( pNode->Level > 0 )
00547         return pNode->Level;
00548     if ( Abc_ObjIsCi(pNode) )
00549         return 0;
00550     vSuper = (Vec_Ptr_t *)pNode->pCopy;
00551     assert( vSuper != NULL );
00552     LevelMax = 0;
00553     Vec_PtrForEachEntry( vSuper, pFanin, i )
00554     {
00555         pFanin = Abc_ObjRegular(pFanin);
00556         Abc_NtkBalanceLevel_rec(pFanin);
00557         if ( LevelMax < (int)pFanin->Level )
00558             LevelMax = pFanin->Level;
00559     }
00560     pNode->Level = LevelMax + 1;
00561     return pNode->Level;
00562 }
00563 
00564 
00576 void Abc_NtkBalanceLevel( Abc_Ntk_t * pNtk )
00577 {
00578     Abc_Obj_t * pNode;
00579     int i;
00580     Abc_NtkForEachObj( pNtk, pNode, i )
00581         pNode->Level = 0;
00582     Abc_NtkForEachCo( pNtk, pNode, i )
00583         Abc_NtkBalanceLevel_rec( Abc_ObjFanin0(pNode) );
00584 }
00585 
00586 
00598 void Abc_NtkMarkCriticalNodes( Abc_Ntk_t * pNtk )
00599 {
00600     Abc_Obj_t * pNode;
00601     int i, Counter = 0;
00602     Abc_NtkForEachNode( pNtk, pNode, i )
00603         if ( Abc_ObjRequiredLevel(pNode) - pNode->Level <= 1 )
00604             pNode->fMarkA = 1, Counter++;
00605     printf( "The number of nodes on the critical paths = %6d  (%5.2f %%)\n", Counter, 100.0 * Counter / Abc_NtkNodeNum(pNtk) );
00606 }
00607 
00608 
00612 
00613