| /**CFile**************************************************************** |
| |
| FileName [acecStruct.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [CEC for arithmetic circuits.] |
| |
| Synopsis [Core procedures.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: acecStruct.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "acecInt.h" |
| #include "misc/vec/vecWec.h" |
| #include "misc/extra/extra.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Acec_StructDetectXorRoots( Gia_Man_t * p ) |
| { |
| Vec_Int_t * vXors = Vec_IntAlloc( 100 ); |
| Vec_Bit_t * vXorIns = Vec_BitStart( Gia_ManObjNum(p) ); |
| Gia_Obj_t * pFan0, * pFan1, * pObj; |
| int i, k = 0, Entry; |
| Gia_ManForEachAnd( p, pObj, i ) |
| { |
| if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) ) |
| continue; |
| Vec_IntPush( vXors, i ); |
| Vec_BitWriteEntry( vXorIns, Gia_ObjId(p, Gia_Regular(pFan0)), 1 ); |
| Vec_BitWriteEntry( vXorIns, Gia_ObjId(p, Gia_Regular(pFan1)), 1 ); |
| } |
| // collect XORs that not inputs of other XORs |
| Vec_IntForEachEntry( vXors, Entry, i ) |
| if ( !Vec_BitEntry(vXorIns, Entry) ) |
| Vec_IntWriteEntry( vXors, k++, Entry ); |
| Vec_IntShrink( vXors, k ); |
| Vec_BitFree( vXorIns ); |
| return vXors; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Acec_StructAssignRanks( Gia_Man_t * p, Vec_Int_t * vXorRoots ) |
| { |
| Vec_Int_t * vDoubles = Vec_IntAlloc( 100 ); |
| Gia_Obj_t * pFan0, * pFan1, * pObj; |
| int i, k, Fanins[2], Entry, Rank; |
| // map roots into their ranks |
| Vec_Int_t * vRanks = Vec_IntStartFull( Gia_ManObjNum(p) ); |
| Vec_IntForEachEntry( vXorRoots, Entry, i ) |
| Vec_IntWriteEntry( vRanks, Entry, i ); |
| // map nodes into their ranks |
| Gia_ManForEachAndReverse( p, pObj, i ) |
| { |
| if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) ) |
| continue; |
| Rank = Vec_IntEntry( vRanks, i ); |
| // skip XORs that are not part of any tree |
| if ( Rank == -1 ) |
| continue; |
| // iterate through XOR inputs |
| Fanins[0] = Gia_ObjId(p, Gia_Regular(pFan0)); |
| Fanins[1] = Gia_ObjId(p, Gia_Regular(pFan1)); |
| for ( k = 0; k < 2; k++ ) |
| { |
| Entry = Vec_IntEntry( vRanks, Fanins[k] ); |
| if ( Entry == Rank ) // the same tree -- allow fanout in this tree |
| continue; |
| if ( Entry == -1 ) |
| Vec_IntWriteEntry( vRanks, Fanins[k], Rank ); |
| else |
| Vec_IntPush( vDoubles, Fanins[k] ); |
| if ( Entry != -1 && Gia_ObjIsAnd(Gia_ManObj(p, Fanins[k]))) |
| printf( "Xor node %d belongs to Tree %d and Tree %d.\n", Fanins[k], Entry, Rank ); |
| } |
| } |
| // remove duplicated entries |
| Vec_IntForEachEntry( vDoubles, Entry, i ) |
| Vec_IntWriteEntry( vRanks, Entry, -1 ); |
| Vec_IntFree( vDoubles ); |
| return vRanks; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Wec_t * Acec_FindTreeLeaves( Gia_Man_t * p, Vec_Int_t * vXorRoots, Vec_Int_t * vRanks ) |
| { |
| Vec_Bit_t * vMapXors = Vec_BitStart( Gia_ManObjNum(p) ); |
| Vec_Wec_t * vTreeLeaves = Vec_WecStart( Vec_IntSize(vXorRoots) ); |
| Gia_Obj_t * pFan0, * pFan1, * pObj; |
| int i, k, Fanins[2], Rank; |
| Gia_ManForEachAnd( p, pObj, i ) |
| { |
| if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) ) |
| continue; |
| Vec_BitWriteEntry( vMapXors, i, 1 ); |
| Rank = Vec_IntEntry( vRanks, i ); |
| // skip XORs that are not part of any tree |
| if ( Rank == -1 ) |
| continue; |
| // iterate through XOR inputs |
| Fanins[0] = Gia_ObjId(p, Gia_Regular(pFan0)); |
| Fanins[1] = Gia_ObjId(p, Gia_Regular(pFan1)); |
| for ( k = 0; k < 2; k++ ) |
| { |
| if ( Vec_BitEntry(vMapXors, Fanins[k]) ) |
| { |
| assert( Rank == Vec_IntEntry(vRanks, Fanins[k]) ); |
| continue; |
| } |
| Vec_WecPush( vTreeLeaves, Rank, Fanins[k] ); |
| } |
| } |
| Vec_BitFree( vMapXors ); |
| return vTreeLeaves; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Acec_FindShadows( Gia_Man_t * p, Vec_Int_t * vRanks ) |
| { |
| Vec_Int_t * vShadows = Vec_IntDup( vRanks ); |
| Gia_Obj_t * pObj; int i, Shad0, Shad1; |
| Gia_ManForEachCi( p, pObj, i ) |
| Vec_IntWriteEntry( vShadows, Gia_ObjId(p, pObj), -1 ); |
| Gia_ManForEachAnd( p, pObj, i ) |
| { |
| if ( Vec_IntEntry(vShadows, i) >= 0 ) |
| continue; |
| Shad0 = Vec_IntEntry(vShadows, Gia_ObjFaninId0(pObj, i)); |
| Shad1 = Vec_IntEntry(vShadows, Gia_ObjFaninId1(pObj, i)); |
| if ( Shad0 == Shad1 && Shad0 != -1 ) |
| Vec_IntWriteEntry(vShadows, i, Shad0); |
| } |
| return vShadows; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Acec_CollectSupp_rec( Gia_Man_t * p, int iNode, int Rank, Vec_Int_t * vRanks ) |
| { |
| Gia_Obj_t * pObj; |
| int nSize; |
| if ( Gia_ObjIsTravIdCurrentId(p, iNode) ) |
| return 0; |
| Gia_ObjSetTravIdCurrentId(p, iNode); |
| pObj = Gia_ManObj(p, iNode); |
| assert( Gia_ObjIsAnd(pObj) ); |
| if ( Vec_IntEntry(vRanks, iNode) == Rank ) |
| return 1; |
| nSize = Acec_CollectSupp_rec( p, Gia_ObjFaninId0(pObj, iNode), Rank, vRanks ); |
| nSize += Acec_CollectSupp_rec( p, Gia_ObjFaninId1(pObj, iNode), Rank, vRanks ); |
| return nSize; |
| } |
| Vec_Wec_t * Acec_FindNexts( Gia_Man_t * p, Vec_Int_t * vRanks, Vec_Int_t * vShadows, Vec_Wec_t * vTreeLeaves ) |
| { |
| Vec_Wec_t * vNexts = Vec_WecStart( Vec_WecSize(vTreeLeaves) ); |
| Vec_Int_t * vTree; |
| int i, k, Node, Fanins[2], Shad0, Shad1, Rank, nSupp; |
| Vec_WecForEachLevel( vTreeLeaves, vTree, i ) |
| Vec_IntForEachEntry( vTree, Node, k ) |
| { |
| Gia_Obj_t * pObj = Gia_ManObj(p, Node); |
| if ( !Gia_ObjIsAnd(pObj) ) |
| continue; |
| Fanins[0] = Gia_ObjFaninId0(pObj, Node); |
| Fanins[1] = Gia_ObjFaninId1(pObj, Node); |
| Shad0 = Vec_IntEntry(vShadows, Fanins[0]); |
| Shad1 = Vec_IntEntry(vShadows, Fanins[1]); |
| if ( Shad0 != Shad1 || Shad0 == -1 ) |
| continue; |
| // check support size of Node in terms of the shadow of its fanins |
| Rank = Vec_IntEntry( vRanks, Node ); |
| assert( Rank != Shad0 ); |
| Gia_ManIncrementTravId( p ); |
| nSupp = Acec_CollectSupp_rec( p, Node, Shad0, vRanks ); |
| assert( nSupp > 1 ); |
| if ( nSupp > 3 ) |
| continue; |
| Vec_IntPushUniqueOrder( Vec_WecEntry(vNexts, Shad0), Rank ); |
| } |
| return vNexts; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Acec_StructTest( Gia_Man_t * p ) |
| { |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
