diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2005-09-04 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2005-09-04 08:01:00 -0700 |
commit | 33012d9530c40817e1fc5230b3e663f7690b2e94 (patch) | |
tree | 4b782c372b9647ad8490103ee98d0affa54a3952 /src/base/abci/abcBalance.c | |
parent | dce73ade2fa0c7a01b58d4a6c592e0e07cbb5499 (diff) | |
download | abc-33012d9530c40817e1fc5230b3e663f7690b2e94.tar.gz abc-33012d9530c40817e1fc5230b3e663f7690b2e94.tar.bz2 abc-33012d9530c40817e1fc5230b3e663f7690b2e94.zip |
Version abc50904
Diffstat (limited to 'src/base/abci/abcBalance.c')
-rw-r--r-- | src/base/abci/abcBalance.c | 239 |
1 files changed, 239 insertions, 0 deletions
diff --git a/src/base/abci/abcBalance.c b/src/base/abci/abcBalance.c new file mode 100644 index 00000000..5042d0d5 --- /dev/null +++ b/src/base/abci/abcBalance.c @@ -0,0 +1,239 @@ +/**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 [$Id: abcBalance.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "abc.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate ); +static Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, Vec_Vec_t * vStorage, bool fDuplicate ); +static Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vSuper, int fDuplicate ); +static int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, bool fDuplicate ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Balances the AIG network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * Abc_NtkBalance( Abc_Ntk_t * pNtk, bool fDuplicate ) +{ + int fCheck = 1; + Abc_Ntk_t * pNtkAig; + assert( Abc_NtkIsStrash(pNtk) ); + // perform balancing + pNtkAig = Abc_NtkStartFrom( pNtk, ABC_TYPE_STRASH, ABC_FUNC_AIG ); + Abc_NtkBalancePerform( pNtk, pNtkAig, fDuplicate ); + Abc_NtkFinalize( pNtk, pNtkAig ); + // make sure everything is okay + if ( fCheck && !Abc_NtkCheck( pNtkAig ) ) + { + printf( "Abc_NtkBalance: The network check has failed.\n" ); + Abc_NtkDelete( pNtkAig ); + return NULL; + } + return pNtkAig; +} + +/**Function************************************************************* + + Synopsis [Balances the AIG network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate ) +{ + int fCheck = 1; + ProgressBar * pProgress; + Vec_Vec_t * vStorage; + Abc_Obj_t * pNode, * pDriver; + int i; + + // copy the constant node + Abc_AigConst1(pNtk->pManFunc)->pCopy = Abc_AigConst1(pNtkAig->pManFunc); + // set the level of PIs of AIG according to the arrival times of the old network + Abc_NtkSetNodeLevelsArrival( pNtk ); + // allocate temporary storage for supergates + vStorage = Vec_VecStart( Abc_AigGetLevelNum(pNtk) + 1 ); + // perform balancing of POs + pProgress = Extra_ProgressBarStart( stdout, Abc_NtkCoNum(pNtk) ); + Abc_NtkForEachCo( pNtk, pNode, i ) + { + Extra_ProgressBarUpdate( pProgress, i, NULL ); + // strash the driver node + pDriver = Abc_ObjFanin0(pNode); + Abc_NodeBalance_rec( pNtkAig, pDriver, vStorage, fDuplicate ); + } + Extra_ProgressBarStop( pProgress ); + Vec_VecFree( vStorage ); +} + +/**Function************************************************************* + + Synopsis [Rebalances the multi-input node rooted at pNodeOld.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, Vec_Vec_t * vStorage, bool fDuplicate ) +{ + Abc_Aig_t * pMan = pNtkNew->pManFunc; + Abc_Obj_t * pNodeNew, * pNode1, * pNode2; + Vec_Ptr_t * vSuper; + int i; + assert( !Abc_ObjIsComplement(pNodeOld) ); + // return if the result if known + if ( pNodeOld->pCopy ) + return pNodeOld->pCopy; + assert( Abc_ObjIsNode(pNodeOld) ); + // get the implication supergate + vSuper = Abc_NodeBalanceCone( pNodeOld, vStorage, fDuplicate ); + if ( vSuper->nSize == 0 ) + { // it means that the supergate contains two nodes in the opposite polarity + pNodeOld->pCopy = Abc_ObjNot(Abc_AigConst1(pMan)); + return pNodeOld->pCopy; + } + // for each old node, derive the new well-balanced node + for ( i = 0; i < vSuper->nSize; i++ ) + { + pNodeNew = Abc_NodeBalance_rec( pNtkNew, Abc_ObjRegular(vSuper->pArray[i]), vStorage, fDuplicate ); + vSuper->pArray[i] = Abc_ObjNotCond( pNodeNew, Abc_ObjIsComplement(vSuper->pArray[i]) ); + } + // sort the new nodes by level in the decreasing order + Vec_PtrSort( vSuper, Abc_NodeCompareLevelsDecrease ); + // balance the nodes + assert( vSuper->nSize > 1 ); + while ( vSuper->nSize > 1 ) + { + pNode1 = Vec_PtrPop(vSuper); + pNode2 = Vec_PtrPop(vSuper); + Abc_VecObjPushUniqueOrderByLevel( vSuper, Abc_AigAnd(pMan, pNode1, pNode2) ); + } + // make sure the balanced node is not assigned + assert( pNodeOld->pCopy == NULL ); + // mark the old node with the new node + pNodeOld->pCopy = vSuper->pArray[0]; + return pNodeOld->pCopy; +} + +/**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 [] + +***********************************************************************/ +Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vStorage, int fDuplicate ) +{ + Vec_Ptr_t * vNodes; + int RetValue, i; + assert( !Abc_ObjIsComplement(pNode) ); + vNodes = Vec_VecEntry( vStorage, pNode->Level ); + Vec_PtrClear( vNodes ); + RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, fDuplicate ); + assert( vNodes->nSize > 0 ); + for ( i = 0; i < vNodes->nSize; i++ ) + Abc_ObjRegular((Abc_Obj_t *)vNodes->pArray[i])->fMarkB = 0; + if ( RetValue == -1 ) + vNodes->nSize = 0; + return vNodes; +} + + +/**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 [] + +***********************************************************************/ +int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, bool fDuplicate ) +{ + int RetValue1, RetValue2, i; + // check if the node is visited + if ( Abc_ObjRegular(pNode)->fMarkB ) + { + // check if the node occurs in the same polarity + for ( i = 0; i < vSuper->nSize; i++ ) + if ( vSuper->pArray[i] == pNode ) + return 1; + // check if the node is present in the opposite polarity + for ( i = 0; i < vSuper->nSize; i++ ) + if ( vSuper->pArray[i] == Abc_ObjNot(pNode) ) + return -1; + assert( 0 ); + return 0; + } + // if the new node is complemented or a PI, another gate begins + if ( !fFirst && (Abc_ObjIsComplement(pNode) || !Abc_ObjIsNode(pNode) || !fDuplicate && (Abc_ObjFanoutNum(pNode) > 1)) ) + { + Vec_PtrPush( vSuper, pNode ); + Abc_ObjRegular(pNode)->fMarkB = 1; + return 0; + } + assert( !Abc_ObjIsComplement(pNode) ); + assert( Abc_ObjIsNode(pNode) ); + // go through the branches + RetValue1 = Abc_NodeBalanceCone_rec( Abc_ObjChild0(pNode), vSuper, 0, fDuplicate ); + RetValue2 = Abc_NodeBalanceCone_rec( Abc_ObjChild1(pNode), vSuper, 0, fDuplicate ); + if ( RetValue1 == -1 || RetValue2 == -1 ) + return -1; + // return 1 if at least one branch has a duplicate + return RetValue1 || RetValue2; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |