#include "abc.h"
Go to the source code of this file.
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 | |||
) | [static] |
Function*************************************************************
Synopsis [Rebalances the multi-input node rooted at pNodeOld.]
Description []
SideEffects []
SeeAlso []
Definition at line 224 of file abcBalance.c.
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 }
Vec_Ptr_t * Abc_NodeBalanceCone | ( | Abc_Obj_t * | pNode, | |
Vec_Vec_t * | vStorage, | |||
int | Level, | |||
int | fDuplicate, | |||
bool | fSelective | |||
) | [static] |
Function*************************************************************
Synopsis [Collects the nodes in the cone delimited by fMarkA==1.]
Description [Returns -1 if the AND-cone has the same node in both polarities. Returns 1 if the AND-cone has the same node in the same polarity. Returns 0 if the AND-cone has no repeated nodes.]
SideEffects []
SeeAlso []
Definition at line 293 of file abcBalance.c.
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 }
int Abc_NodeBalanceCone_rec | ( | Abc_Obj_t * | pNode, | |
Vec_Ptr_t * | vSuper, | |||
bool | fFirst, | |||
bool | fDuplicate, | |||
bool | fSelective | |||
) | [static] |
Function*************************************************************
Synopsis [Collects the nodes in the cone delimited by fMarkA==1.]
Description [Returns -1 if the AND-cone has the same node in both polarities. Returns 1 if the AND-cone has the same node in the same polarity. Returns 0 if the AND-cone has no repeated nodes.]
SideEffects []
SeeAlso []
Definition at line 331 of file abcBalance.c.
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 }
Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
Definition at line 414 of file abcBalance.c.
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 }
Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
Definition at line 378 of file abcBalance.c.
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 }
int Abc_NodeBalanceFindLeft | ( | Vec_Ptr_t * | vSuper | ) |
Function*************************************************************
Synopsis [Finds the left bound on the next candidate to be paired.]
Description [The nodes in the array are in the decreasing order of levels. The last node in the array has the smallest level. By default it would be paired with the next node on the left. However, it may be possible to pair it with some other node on the left, in such a way that the new node is shared. This procedure finds the index of the left-most node, which can be paired with the last node.]
SideEffects []
SeeAlso []
Definition at line 137 of file abcBalance.c.
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 }
Function*************************************************************
Synopsis [Moves closer to the end the node that is best for sharing.]
Description [If there is no node with sharing, randomly chooses one of the legal nodes.]
SideEffects []
SeeAlso []
Definition at line 175 of file abcBalance.c.
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 }
Function*************************************************************
Synopsis [Collects the nodes in the implication supergate.]
Description []
SideEffects []
SeeAlso []
Definition at line 439 of file abcBalance.c.
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 }
FUNCTION DEFINITIONS ///Function*************************************************************
Synopsis [Balances the AIG network.]
Description []
SideEffects []
SeeAlso []
Definition at line 50 of file abcBalance.c.
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 }
void Abc_NtkBalanceAttach | ( | Abc_Ntk_t * | pNtk | ) |
Function*************************************************************
Synopsis [Attaches the implication supergates to internal nodes.]
Description []
SideEffects []
SeeAlso []
Definition at line 492 of file abcBalance.c.
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 }
void Abc_NtkBalanceDetach | ( | Abc_Ntk_t * | pNtk | ) |
Function*************************************************************
Synopsis [Attaches the implication supergates to internal nodes.]
Description []
SideEffects []
SeeAlso []
Definition at line 517 of file abcBalance.c.
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 }
void Abc_NtkBalanceLevel | ( | Abc_Ntk_t * | pNtk | ) |
Function*************************************************************
Synopsis [Compute levels of implication supergates.]
Description []
SideEffects []
SeeAlso []
Definition at line 576 of file abcBalance.c.
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 }
int Abc_NtkBalanceLevel_rec | ( | Abc_Obj_t * | pNode | ) |
Function*************************************************************
Synopsis [Compute levels of implication supergates.]
Description []
SideEffects []
SeeAlso []
Definition at line 540 of file abcBalance.c.
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 }
void Abc_NtkBalancePerform | ( | Abc_Ntk_t * | pNtk, | |
Abc_Ntk_t * | pNtkAig, | |||
bool | fDuplicate, | |||
bool | fSelective, | |||
bool | fUpdateLevel | |||
) | [static] |
CFile****************************************************************
FileName [abcBalance.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Network and node package.]
Synopsis [Performs global balancing of the AIG by the number of levels.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [
] DECLARATIONS ///
Function*************************************************************
Synopsis [Balances the AIG network.]
Description []
SideEffects []
SeeAlso []
Definition at line 97 of file abcBalance.c.
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 }
void Abc_NtkMarkCriticalNodes | ( | Abc_Ntk_t * | pNtk | ) | [static] |
Function*************************************************************
Synopsis [Marks the nodes on the critical and near critical paths.]
Description []
SideEffects []
SeeAlso []
Definition at line 598 of file abcBalance.c.
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 }