| /**CFile**************************************************************** |
| |
| FileName [ivyCut.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [And-Inverter Graph package.] |
| |
| Synopsis [Computes reconvergence driven sequential cut.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - May 11, 2006.] |
| |
| Revision [$Id: ivyCut.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "ivy.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| static inline int Ivy_NodeCutHashValue( int NodeId ) { return 1 << (NodeId % 31); } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Evaluate the cost of removing the node from the set of leaves.] |
| |
| Description [Returns the number of new leaves that will be brought in. |
| Returns large number if the node cannot be removed from the set of leaves.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Ivy_NodeGetLeafCostOne( Ivy_Man_t * p, int Leaf, Vec_Int_t * vInside ) |
| { |
| Ivy_Obj_t * pNode; |
| int nLatches, FaninLeaf, Cost; |
| // make sure leaf is not a contant node |
| assert( Leaf > 0 ); |
| // get the node |
| pNode = Ivy_ManObj( p, Ivy_LeafId(Leaf) ); |
| // cannot expand over the PI node |
| if ( Ivy_ObjIsPi(pNode) || Ivy_ObjIsConst1(pNode) ) |
| return 999; |
| // get the number of latches |
| nLatches = Ivy_LeafLat(Leaf) + Ivy_ObjIsLatch(pNode); |
| if ( nLatches > 15 ) |
| return 999; |
| // get the first fanin |
| FaninLeaf = Ivy_LeafCreate( Ivy_ObjFaninId0(pNode), nLatches ); |
| Cost = FaninLeaf && (Vec_IntFind(vInside, FaninLeaf) == -1); |
| // quit if this is the one fanin node |
| if ( Ivy_ObjIsLatch(pNode) || Ivy_ObjIsBuf(pNode) ) |
| return Cost; |
| assert( Ivy_ObjIsNode(pNode) ); |
| // get the second fanin |
| FaninLeaf = Ivy_LeafCreate( Ivy_ObjFaninId1(pNode), nLatches ); |
| Cost += FaninLeaf && (Vec_IntFind(vInside, FaninLeaf) == -1); |
| return Cost; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Builds reconvergence-driven cut by changing one leaf at a time.] |
| |
| Description [This procedure looks at the current leaves and tries to change |
| one leaf at a time in such a way that the cut grows as little as possible. |
| In evaluating the fanins, this procedure looks only at their immediate |
| predecessors (this is why it is called a one-level construction procedure).] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_ManSeqFindCut_int( Ivy_Man_t * p, Vec_Int_t * vFront, Vec_Int_t * vInside, int nSizeLimit ) |
| { |
| Ivy_Obj_t * pNode; |
| int CostBest, CostCur, Leaf, LeafBest, Next, nLatches, i; |
| int LeavesBest[10]; |
| int Counter; |
| |
| // add random selection of the best fanin!!! |
| |
| // find the best fanin |
| CostBest = 99; |
| LeafBest = -1; |
| Counter = -1; |
| //printf( "Evaluating fanins of the cut:\n" ); |
| Vec_IntForEachEntry( vFront, Leaf, i ) |
| { |
| CostCur = Ivy_NodeGetLeafCostOne( p, Leaf, vInside ); |
| //printf( " Fanin %s has cost %d.\n", Ivy_ObjName(pNode), CostCur ); |
| if ( CostBest > CostCur ) |
| { |
| CostBest = CostCur; |
| LeafBest = Leaf; |
| LeavesBest[0] = Leaf; |
| Counter = 1; |
| } |
| else if ( CostBest == CostCur ) |
| LeavesBest[Counter++] = Leaf; |
| |
| if ( CostBest <= 1 ) // can be if ( CostBest <= 1 ) |
| break; |
| } |
| if ( CostBest == 99 ) |
| return 0; |
| // return Ivy_NodeBuildCutLevelTwo_int( vInside, vFront, nFaninLimit ); |
| |
| assert( CostBest < 3 ); |
| if ( Vec_IntSize(vFront) - 1 + CostBest > nSizeLimit ) |
| return 0; |
| // return Ivy_NodeBuildCutLevelTwo_int( vInside, vFront, nFaninLimit ); |
| |
| assert( Counter > 0 ); |
| printf( "%d", Counter ); |
| |
| LeafBest = LeavesBest[rand() % Counter]; |
| |
| // remove the node from the array |
| assert( LeafBest >= 0 ); |
| Vec_IntRemove( vFront, LeafBest ); |
| //printf( "Removing fanin %s.\n", Ivy_ObjName(pNode) ); |
| |
| // get the node and its latches |
| pNode = Ivy_ManObj( p, Ivy_LeafId(LeafBest) ); |
| nLatches = Ivy_LeafLat(LeafBest) + Ivy_ObjIsLatch(pNode); |
| assert( Ivy_ObjIsNode(pNode) || Ivy_ObjIsLatch(pNode) || Ivy_ObjIsBuf(pNode) ); |
| |
| // add the left child to the fanins |
| Next = Ivy_LeafCreate( Ivy_ObjFaninId0(pNode), nLatches ); |
| if ( Next && Vec_IntFind(vInside, Next) == -1 ) |
| { |
| //printf( "Adding fanin %s.\n", Ivy_ObjName(pNext) ); |
| Vec_IntPush( vFront, Next ); |
| Vec_IntPush( vInside, Next ); |
| } |
| |
| // quit if this is the one fanin node |
| if ( Ivy_ObjIsLatch(pNode) || Ivy_ObjIsBuf(pNode) ) |
| return 1; |
| assert( Ivy_ObjIsNode(pNode) ); |
| |
| // add the right child to the fanins |
| Next = Ivy_LeafCreate( Ivy_ObjFaninId1(pNode), nLatches ); |
| if ( Next && Vec_IntFind(vInside, Next) == -1 ) |
| { |
| //printf( "Adding fanin %s.\n", Ivy_ObjName(pNext) ); |
| Vec_IntPush( vFront, Next ); |
| Vec_IntPush( vInside, Next ); |
| } |
| assert( Vec_IntSize(vFront) <= nSizeLimit ); |
| // keep doing this |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes one sequential cut of the given size.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_ManSeqFindCut( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Vec_Int_t * vFront, Vec_Int_t * vInside, int nSize ) |
| { |
| assert( !Ivy_IsComplement(pRoot) ); |
| assert( Ivy_ObjIsNode(pRoot) ); |
| assert( Ivy_ObjFaninId0(pRoot) ); |
| assert( Ivy_ObjFaninId1(pRoot) ); |
| |
| // start the cut |
| Vec_IntClear( vFront ); |
| Vec_IntPush( vFront, Ivy_LeafCreate(Ivy_ObjFaninId0(pRoot), 0) ); |
| Vec_IntPush( vFront, Ivy_LeafCreate(Ivy_ObjFaninId1(pRoot), 0) ); |
| |
| // start the visited nodes |
| Vec_IntClear( vInside ); |
| Vec_IntPush( vInside, Ivy_LeafCreate(pRoot->Id, 0) ); |
| Vec_IntPush( vInside, Ivy_LeafCreate(Ivy_ObjFaninId0(pRoot), 0) ); |
| Vec_IntPush( vInside, Ivy_LeafCreate(Ivy_ObjFaninId1(pRoot), 0) ); |
| |
| // compute the cut |
| while ( Ivy_ManSeqFindCut_int( p, vFront, vInside, nSize ) ); |
| assert( Vec_IntSize(vFront) <= nSize ); |
| } |
| |
| |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computing Boolean cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_ManFindBoolCut_rec( Ivy_Man_t * p, Ivy_Obj_t * pObj, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVolume, Ivy_Obj_t * pPivot ) |
| { |
| int RetValue0, RetValue1; |
| if ( pObj == pPivot ) |
| { |
| Vec_PtrPushUnique( vLeaves, pObj ); |
| Vec_PtrPushUnique( vVolume, pObj ); |
| return 1; |
| } |
| if ( pObj->fMarkA ) |
| return 0; |
| |
| // assert( !Ivy_ObjIsCi(pObj) ); |
| if ( Ivy_ObjIsCi(pObj) ) |
| return 0; |
| |
| if ( Ivy_ObjIsBuf(pObj) ) |
| { |
| RetValue0 = Ivy_ManFindBoolCut_rec( p, Ivy_ObjFanin0(pObj), vLeaves, vVolume, pPivot ); |
| if ( !RetValue0 ) |
| return 0; |
| Vec_PtrPushUnique( vVolume, pObj ); |
| return 1; |
| } |
| assert( Ivy_ObjIsNode(pObj) ); |
| RetValue0 = Ivy_ManFindBoolCut_rec( p, Ivy_ObjFanin0(pObj), vLeaves, vVolume, pPivot ); |
| RetValue1 = Ivy_ManFindBoolCut_rec( p, Ivy_ObjFanin1(pObj), vLeaves, vVolume, pPivot ); |
| if ( !RetValue0 && !RetValue1 ) |
| return 0; |
| // add new leaves |
| if ( !RetValue0 ) |
| { |
| Vec_PtrPushUnique( vLeaves, Ivy_ObjFanin0(pObj) ); |
| Vec_PtrPushUnique( vVolume, Ivy_ObjFanin0(pObj) ); |
| } |
| if ( !RetValue1 ) |
| { |
| Vec_PtrPushUnique( vLeaves, Ivy_ObjFanin1(pObj) ); |
| Vec_PtrPushUnique( vVolume, Ivy_ObjFanin1(pObj) ); |
| } |
| Vec_PtrPushUnique( vVolume, pObj ); |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns the cost of one node (how many new nodes are added.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_ManFindBoolCutCost( Ivy_Obj_t * pObj ) |
| { |
| int Cost; |
| // make sure the node is in the construction zone |
| assert( pObj->fMarkA == 1 ); |
| // cannot expand over the PI node |
| if ( Ivy_ObjIsCi(pObj) ) |
| return 999; |
| // always expand over the buffer |
| if ( Ivy_ObjIsBuf(pObj) ) |
| return !Ivy_ObjFanin0(pObj)->fMarkA; |
| // get the cost of the cone |
| Cost = (!Ivy_ObjFanin0(pObj)->fMarkA) + (!Ivy_ObjFanin1(pObj)->fMarkA); |
| // return the number of nodes to be added to the leaves if this node is removed |
| return Cost; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computing Boolean cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_ManFindBoolCut( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Vec_Ptr_t * vFront, Vec_Ptr_t * vVolume, Vec_Ptr_t * vLeaves ) |
| { |
| Ivy_Obj_t * pObj = NULL; // Suppress "might be used uninitialized" |
| Ivy_Obj_t * pFaninC, * pFanin0, * pFanin1, * pPivot; |
| int RetValue, LevelLimit, Lev, k; |
| assert( !Ivy_IsComplement(pRoot) ); |
| // clear the frontier and collect the nodes |
| Vec_PtrClear( vFront ); |
| Vec_PtrClear( vVolume ); |
| if ( Ivy_ObjIsMuxType(pRoot) ) |
| pFaninC = Ivy_ObjRecognizeMux( pRoot, &pFanin0, &pFanin1 ); |
| else |
| { |
| pFaninC = NULL; |
| pFanin0 = Ivy_ObjFanin0(pRoot); |
| pFanin1 = Ivy_ObjFanin1(pRoot); |
| } |
| // start cone A |
| pFanin0->fMarkA = 1; |
| Vec_PtrPush( vFront, pFanin0 ); |
| Vec_PtrPush( vVolume, pFanin0 ); |
| // start cone B |
| pFanin1->fMarkB = 1; |
| Vec_PtrPush( vFront, pFanin1 ); |
| Vec_PtrPush( vVolume, pFanin1 ); |
| // iteratively expand until the common node (pPivot) is found or limit is reached |
| assert( Ivy_ObjLevel(pRoot) == Ivy_ObjLevelNew(pRoot) ); |
| pPivot = NULL; |
| LevelLimit = IVY_MAX( Ivy_ObjLevel(pRoot) - 10, 1 ); |
| for ( Lev = Ivy_ObjLevel(pRoot) - 1; Lev >= LevelLimit; Lev-- ) |
| { |
| while ( 1 ) |
| { |
| // find the next node to expand on this level |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pObj, k ) |
| if ( (int)pObj->Level == Lev ) |
| break; |
| if ( k == Vec_PtrSize(vFront) ) |
| break; |
| assert( (int)pObj->Level <= Lev ); |
| assert( pObj->fMarkA ^ pObj->fMarkB ); |
| // remove the old node |
| Vec_PtrRemove( vFront, pObj ); |
| |
| // expand this node |
| pFanin0 = Ivy_ObjFanin0(pObj); |
| if ( !pFanin0->fMarkA && !pFanin0->fMarkB ) |
| { |
| Vec_PtrPush( vFront, pFanin0 ); |
| Vec_PtrPush( vVolume, pFanin0 ); |
| } |
| // mark the new nodes |
| if ( pObj->fMarkA ) |
| pFanin0->fMarkA = 1; |
| if ( pObj->fMarkB ) |
| pFanin0->fMarkB = 1; |
| |
| if ( Ivy_ObjIsBuf(pObj) ) |
| { |
| if ( pFanin0->fMarkA && pFanin0->fMarkB ) |
| { |
| pPivot = pFanin0; |
| break; |
| } |
| continue; |
| } |
| |
| // expand this node |
| pFanin1 = Ivy_ObjFanin1(pObj); |
| if ( !pFanin1->fMarkA && !pFanin1->fMarkB ) |
| { |
| Vec_PtrPush( vFront, pFanin1 ); |
| Vec_PtrPush( vVolume, pFanin1 ); |
| } |
| // mark the new nodes |
| if ( pObj->fMarkA ) |
| pFanin1->fMarkA = 1; |
| if ( pObj->fMarkB ) |
| pFanin1->fMarkB = 1; |
| |
| // consider if it is time to quit |
| if ( pFanin0->fMarkA && pFanin0->fMarkB ) |
| { |
| pPivot = pFanin0; |
| break; |
| } |
| if ( pFanin1->fMarkA && pFanin1->fMarkB ) |
| { |
| pPivot = pFanin1; |
| break; |
| } |
| } |
| if ( pPivot != NULL ) |
| break; |
| } |
| if ( pPivot == NULL ) |
| return 0; |
| // if the MUX control is defined, it should not be |
| if ( pFaninC && !pFaninC->fMarkA && !pFaninC->fMarkB ) |
| Vec_PtrPush( vFront, pFaninC ); |
| // clean the markings |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vVolume, pObj, k ) |
| pObj->fMarkA = pObj->fMarkB = 0; |
| |
| // mark the nodes on the frontier (including the pivot) |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pObj, k ) |
| pObj->fMarkA = 1; |
| // cut exists, collect all the nodes on the shortest path to the pivot |
| Vec_PtrClear( vLeaves ); |
| Vec_PtrClear( vVolume ); |
| RetValue = Ivy_ManFindBoolCut_rec( p, pRoot, vLeaves, vVolume, pPivot ); |
| assert( RetValue == 1 ); |
| // unmark the nodes on the frontier (including the pivot) |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pObj, k ) |
| pObj->fMarkA = 0; |
| |
| // mark the nodes in the volume |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vVolume, pObj, k ) |
| pObj->fMarkA = 1; |
| // expand the cut without increasing its size |
| while ( 1 ) |
| { |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vLeaves, pObj, k ) |
| if ( Ivy_ManFindBoolCutCost(pObj) < 2 ) |
| break; |
| if ( k == Vec_PtrSize(vLeaves) ) |
| break; |
| // the node can be expanded |
| // remove the old node |
| Vec_PtrRemove( vLeaves, pObj ); |
| // expand this node |
| pFanin0 = Ivy_ObjFanin0(pObj); |
| if ( !pFanin0->fMarkA ) |
| { |
| pFanin0->fMarkA = 1; |
| Vec_PtrPush( vVolume, pFanin0 ); |
| Vec_PtrPush( vLeaves, pFanin0 ); |
| } |
| if ( Ivy_ObjIsBuf(pObj) ) |
| continue; |
| // expand this node |
| pFanin1 = Ivy_ObjFanin1(pObj); |
| if ( !pFanin1->fMarkA ) |
| { |
| pFanin1->fMarkA = 1; |
| Vec_PtrPush( vVolume, pFanin1 ); |
| Vec_PtrPush( vLeaves, pFanin1 ); |
| } |
| } |
| // unmark the nodes in the volume |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vVolume, pObj, k ) |
| pObj->fMarkA = 0; |
| return 1; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_ManTestCutsBool( Ivy_Man_t * p ) |
| { |
| Vec_Ptr_t * vFront, * vVolume, * vLeaves; |
| Ivy_Obj_t * pObj;//, * pTemp; |
| int i, RetValue;//, k; |
| vFront = Vec_PtrAlloc( 100 ); |
| vVolume = Vec_PtrAlloc( 100 ); |
| vLeaves = Vec_PtrAlloc( 100 ); |
| Ivy_ManForEachObj( p, pObj, i ) |
| { |
| if ( !Ivy_ObjIsNode(pObj) ) |
| continue; |
| if ( Ivy_ObjIsMuxType(pObj) ) |
| { |
| printf( "m" ); |
| continue; |
| } |
| if ( Ivy_ObjIsExor(pObj) ) |
| printf( "x" ); |
| RetValue = Ivy_ManFindBoolCut( p, pObj, vFront, vVolume, vLeaves ); |
| if ( RetValue == 0 ) |
| printf( "- " ); |
| else |
| printf( "%d ", Vec_PtrSize(vLeaves) ); |
| /* |
| printf( "( " ); |
| Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pTemp, k ) |
| printf( "%d ", Ivy_ObjRefs(Ivy_Regular(pTemp)) ); |
| printf( ")\n" ); |
| */ |
| } |
| printf( "\n" ); |
| Vec_PtrFree( vFront ); |
| Vec_PtrFree( vVolume ); |
| Vec_PtrFree( vLeaves ); |
| } |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Find the hash value of the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline unsigned Ivy_NodeCutHash( Ivy_Cut_t * pCut ) |
| { |
| int i; |
| // for ( i = 1; i < pCut->nSize; i++ ) |
| // assert( pCut->pArray[i-1] < pCut->pArray[i] ); |
| pCut->uHash = 0; |
| for ( i = 0; i < pCut->nSize; i++ ) |
| pCut->uHash |= (1 << (pCut->pArray[i] % 31)); |
| return pCut->uHash; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Removes one node to the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline void Ivy_NodeCutShrink( Ivy_Cut_t * pCut, int iOld ) |
| { |
| int i, k; |
| for ( i = k = 0; i < pCut->nSize; i++ ) |
| if ( pCut->pArray[i] != iOld ) |
| pCut->pArray[k++] = pCut->pArray[i]; |
| assert( k == pCut->nSize - 1 ); |
| pCut->nSize--; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Adds one node to the cut.] |
| |
| Description [Returns 1 if the cuts is still okay.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Ivy_NodeCutExtend( Ivy_Cut_t * pCut, int iNew ) |
| { |
| int i; |
| for ( i = 0; i < pCut->nSize; i++ ) |
| if ( pCut->pArray[i] == iNew ) |
| return 1; |
| // check if there is room |
| if ( pCut->nSize == pCut->nSizeMax ) |
| return 0; |
| // add the new one |
| for ( i = pCut->nSize - 1; i >= 0; i-- ) |
| if ( pCut->pArray[i] > iNew ) |
| pCut->pArray[i+1] = pCut->pArray[i]; |
| else |
| { |
| assert( pCut->pArray[i] < iNew ); |
| break; |
| } |
| pCut->pArray[i+1] = iNew; |
| pCut->nSize++; |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns 1 if the cut can be constructed; 0 otherwise.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Ivy_NodeCutPrescreen( Ivy_Cut_t * pCut, int Id0, int Id1 ) |
| { |
| int i; |
| if ( pCut->nSize < pCut->nSizeMax ) |
| return 1; |
| for ( i = 0; i < pCut->nSize; i++ ) |
| if ( pCut->pArray[i] == Id0 || pCut->pArray[i] == Id1 ) |
| return 1; |
| return 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Derives new cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Ivy_NodeCutDeriveNew( Ivy_Cut_t * pCut, Ivy_Cut_t * pCutNew, int IdOld, int IdNew0, int IdNew1 ) |
| { |
| unsigned uHash = 0; |
| int i, k; |
| assert( pCut->nSize > 0 ); |
| assert( IdNew0 < IdNew1 ); |
| for ( i = k = 0; i < pCut->nSize; i++ ) |
| { |
| if ( pCut->pArray[i] == IdOld ) |
| continue; |
| if ( IdNew0 <= pCut->pArray[i] ) |
| { |
| if ( IdNew0 < pCut->pArray[i] ) |
| { |
| pCutNew->pArray[ k++ ] = IdNew0; |
| uHash |= Ivy_NodeCutHashValue( IdNew0 ); |
| } |
| IdNew0 = 0x7FFFFFFF; |
| } |
| if ( IdNew1 <= pCut->pArray[i] ) |
| { |
| if ( IdNew1 < pCut->pArray[i] ) |
| { |
| pCutNew->pArray[ k++ ] = IdNew1; |
| uHash |= Ivy_NodeCutHashValue( IdNew1 ); |
| } |
| IdNew1 = 0x7FFFFFFF; |
| } |
| pCutNew->pArray[ k++ ] = pCut->pArray[i]; |
| uHash |= Ivy_NodeCutHashValue( pCut->pArray[i] ); |
| } |
| if ( IdNew0 < 0x7FFFFFFF ) |
| { |
| pCutNew->pArray[ k++ ] = IdNew0; |
| uHash |= Ivy_NodeCutHashValue( IdNew0 ); |
| } |
| if ( IdNew1 < 0x7FFFFFFF ) |
| { |
| pCutNew->pArray[ k++ ] = IdNew1; |
| uHash |= Ivy_NodeCutHashValue( IdNew1 ); |
| } |
| pCutNew->nSize = k; |
| pCutNew->uHash = uHash; |
| assert( pCutNew->nSize <= pCut->nSizeMax ); |
| // for ( i = 1; i < pCutNew->nSize; i++ ) |
| // assert( pCutNew->pArray[i-1] < pCutNew->pArray[i] ); |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Check if the cut exists.] |
| |
| Description [Returns 1 if the cut exists.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_NodeCutFindOrAdd( Ivy_Store_t * pCutStore, Ivy_Cut_t * pCutNew ) |
| { |
| Ivy_Cut_t * pCut; |
| int i, k; |
| assert( pCutNew->uHash ); |
| // try to find the cut |
| for ( i = 0; i < pCutStore->nCuts; i++ ) |
| { |
| pCut = pCutStore->pCuts + i; |
| if ( pCut->uHash == pCutNew->uHash && pCut->nSize == pCutNew->nSize ) |
| { |
| for ( k = 0; k < pCutNew->nSize; k++ ) |
| if ( pCut->pArray[k] != pCutNew->pArray[k] ) |
| break; |
| if ( k == pCutNew->nSize ) |
| return 1; |
| } |
| } |
| assert( pCutStore->nCuts < pCutStore->nCutsMax ); |
| // add the cut |
| pCut = pCutStore->pCuts + pCutStore->nCuts++; |
| *pCut = *pCutNew; |
| return 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns 1 if pDom is contained in pCut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Ivy_CutCheckDominance( Ivy_Cut_t * pDom, Ivy_Cut_t * pCut ) |
| { |
| int i, k; |
| for ( i = 0; i < pDom->nSize; i++ ) |
| { |
| for ( k = 0; k < pCut->nSize; k++ ) |
| if ( pDom->pArray[i] == pCut->pArray[k] ) |
| break; |
| if ( k == pCut->nSize ) // node i in pDom is not contained in pCut |
| return 0; |
| } |
| // every node in pDom is contained in pCut |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Check if the cut exists.] |
| |
| Description [Returns 1 if the cut exists.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Ivy_NodeCutFindOrAddFilter( Ivy_Store_t * pCutStore, Ivy_Cut_t * pCutNew ) |
| { |
| Ivy_Cut_t * pCut; |
| int i, k; |
| assert( pCutNew->uHash ); |
| // try to find the cut |
| for ( i = 0; i < pCutStore->nCuts; i++ ) |
| { |
| pCut = pCutStore->pCuts + i; |
| if ( pCut->nSize == 0 ) |
| continue; |
| if ( pCut->nSize == pCutNew->nSize ) |
| { |
| if ( pCut->uHash == pCutNew->uHash ) |
| { |
| for ( k = 0; k < pCutNew->nSize; k++ ) |
| if ( pCut->pArray[k] != pCutNew->pArray[k] ) |
| break; |
| if ( k == pCutNew->nSize ) |
| return 1; |
| } |
| continue; |
| } |
| if ( pCut->nSize < pCutNew->nSize ) |
| { |
| // skip the non-contained cuts |
| if ( (pCut->uHash & pCutNew->uHash) != pCut->uHash ) |
| continue; |
| // check containment seriously |
| if ( Ivy_CutCheckDominance( pCut, pCutNew ) ) |
| return 1; |
| continue; |
| } |
| // check potential containment of other cut |
| |
| // skip the non-contained cuts |
| if ( (pCut->uHash & pCutNew->uHash) != pCutNew->uHash ) |
| continue; |
| // check containment seriously |
| if ( Ivy_CutCheckDominance( pCutNew, pCut ) ) |
| { |
| // remove the current cut |
| // --pCutStore->nCuts; |
| // for ( k = i; k < pCutStore->nCuts; k++ ) |
| // pCutStore->pCuts[k] = pCutStore->pCuts[k+1]; |
| // i--; |
| pCut->nSize = 0; |
| } |
| } |
| assert( pCutStore->nCuts < pCutStore->nCutsMax ); |
| // add the cut |
| pCut = pCutStore->pCuts + pCutStore->nCuts++; |
| *pCut = *pCutNew; |
| return 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Print the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_NodeCompactCuts( Ivy_Store_t * pCutStore ) |
| { |
| Ivy_Cut_t * pCut; |
| int i, k; |
| for ( i = k = 0; i < pCutStore->nCuts; i++ ) |
| { |
| pCut = pCutStore->pCuts + i; |
| if ( pCut->nSize == 0 ) |
| continue; |
| pCutStore->pCuts[k++] = *pCut; |
| } |
| pCutStore->nCuts = k; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Print the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_NodePrintCut( Ivy_Cut_t * pCut ) |
| { |
| int i; |
| assert( pCut->nSize > 0 ); |
| printf( "%d : {", pCut->nSize ); |
| for ( i = 0; i < pCut->nSize; i++ ) |
| printf( " %d", pCut->pArray[i] ); |
| printf( " }\n" ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_NodePrintCuts( Ivy_Store_t * pCutStore ) |
| { |
| int i; |
| printf( "Node %d\n", pCutStore->pCuts[0].pArray[0] ); |
| for ( i = 0; i < pCutStore->nCuts; i++ ) |
| Ivy_NodePrintCut( pCutStore->pCuts + i ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline Ivy_Obj_t * Ivy_ObjRealFanin( Ivy_Obj_t * pObj ) |
| { |
| if ( !Ivy_ObjIsBuf(pObj) ) |
| return pObj; |
| return Ivy_ObjRealFanin( Ivy_ObjFanin0(pObj) ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Ivy_Store_t * Ivy_NodeFindCutsAll( Ivy_Man_t * p, Ivy_Obj_t * pObj, int nLeaves ) |
| { |
| static Ivy_Store_t CutStore, * pCutStore = &CutStore; |
| Ivy_Cut_t CutNew, * pCutNew = &CutNew, * pCut; |
| Ivy_Obj_t * pLeaf; |
| int i, k, iLeaf0, iLeaf1; |
| |
| assert( nLeaves <= IVY_CUT_INPUT ); |
| |
| // start the structure |
| pCutStore->nCuts = 0; |
| pCutStore->nCutsMax = IVY_CUT_LIMIT; |
| // start the trivial cut |
| pCutNew->uHash = 0; |
| pCutNew->nSize = 1; |
| pCutNew->nSizeMax = nLeaves; |
| pCutNew->pArray[0] = pObj->Id; |
| Ivy_NodeCutHash( pCutNew ); |
| // add the trivial cut |
| Ivy_NodeCutFindOrAdd( pCutStore, pCutNew ); |
| assert( pCutStore->nCuts == 1 ); |
| |
| // explore the cuts |
| for ( i = 0; i < pCutStore->nCuts; i++ ) |
| { |
| // expand this cut |
| pCut = pCutStore->pCuts + i; |
| if ( pCut->nSize == 0 ) |
| continue; |
| for ( k = 0; k < pCut->nSize; k++ ) |
| { |
| pLeaf = Ivy_ManObj( p, pCut->pArray[k] ); |
| if ( Ivy_ObjIsCi(pLeaf) ) |
| continue; |
| /* |
| *pCutNew = *pCut; |
| Ivy_NodeCutShrink( pCutNew, pLeaf->Id ); |
| if ( !Ivy_NodeCutExtend( pCutNew, Ivy_ObjFaninId0(pLeaf) ) ) |
| continue; |
| if ( Ivy_ObjIsNode(pLeaf) && !Ivy_NodeCutExtend( pCutNew, Ivy_ObjFaninId1(pLeaf) ) ) |
| continue; |
| Ivy_NodeCutHash( pCutNew ); |
| */ |
| iLeaf0 = Ivy_ObjId( Ivy_ObjRealFanin(Ivy_ObjFanin0(pLeaf)) ); |
| iLeaf1 = Ivy_ObjId( Ivy_ObjRealFanin(Ivy_ObjFanin1(pLeaf)) ); |
| // if ( iLeaf0 == iLeaf1 ) // strange situation observed on Jan 18, 2007 |
| // continue; |
| if ( !Ivy_NodeCutPrescreen( pCut, iLeaf0, iLeaf1 ) ) |
| continue; |
| if ( iLeaf0 > iLeaf1 ) |
| Ivy_NodeCutDeriveNew( pCut, pCutNew, pCut->pArray[k], iLeaf1, iLeaf0 ); |
| else |
| Ivy_NodeCutDeriveNew( pCut, pCutNew, pCut->pArray[k], iLeaf0, iLeaf1 ); |
| Ivy_NodeCutFindOrAddFilter( pCutStore, pCutNew ); |
| if ( pCutStore->nCuts == IVY_CUT_LIMIT ) |
| break; |
| } |
| if ( pCutStore->nCuts == IVY_CUT_LIMIT ) |
| break; |
| } |
| Ivy_NodeCompactCuts( pCutStore ); |
| // Ivy_NodePrintCuts( pCutStore ); |
| return pCutStore; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Ivy_ManTestCutsAll( Ivy_Man_t * p ) |
| { |
| Ivy_Obj_t * pObj; |
| int i, nCutsCut, nCutsTotal, nNodeTotal, nNodeOver; |
| abctime clk = Abc_Clock(); |
| nNodeTotal = nNodeOver = 0; |
| nCutsTotal = -Ivy_ManNodeNum(p); |
| Ivy_ManForEachObj( p, pObj, i ) |
| { |
| if ( !Ivy_ObjIsNode(pObj) ) |
| continue; |
| nCutsCut = Ivy_NodeFindCutsAll( p, pObj, 5 )->nCuts; |
| nCutsTotal += nCutsCut; |
| nNodeOver += (nCutsCut == IVY_CUT_LIMIT); |
| nNodeTotal++; |
| } |
| printf( "Total cuts = %6d. Trivial = %6d. Nodes = %6d. Satur = %6d. ", |
| nCutsTotal, Ivy_ManPiNum(p) + Ivy_ManNodeNum(p), nNodeTotal, nNodeOver ); |
| ABC_PRT( "Time", Abc_Clock() - clk ); |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
