diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2007-04-28 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2007-04-28 08:01:00 -0700 |
commit | feb8fb692e09a2fc7c1da4f2fcf605d398e940f2 (patch) | |
tree | 9a1cc7b8e64719e109bbdb99b1e8d49dcb34715c /src/aig/hop | |
parent | c09d4d499cee70f02e3e9a18226554b8d1d34488 (diff) | |
download | abc-feb8fb692e09a2fc7c1da4f2fcf605d398e940f2.tar.gz abc-feb8fb692e09a2fc7c1da4f2fcf605d398e940f2.tar.bz2 abc-feb8fb692e09a2fc7c1da4f2fcf605d398e940f2.zip |
Version abc70428
Diffstat (limited to 'src/aig/hop')
-rw-r--r-- | src/aig/hop/hop.h | 18 | ||||
-rw-r--r-- | src/aig/hop/hopCheck.c | 2 | ||||
-rw-r--r-- | src/aig/hop/hopMan.c | 1 | ||||
-rw-r--r-- | src/aig/hop/hopTable.c | 84 |
4 files changed, 55 insertions, 50 deletions
diff --git a/src/aig/hop/hop.h b/src/aig/hop/hop.h index 8413fb02..37096473 100644 --- a/src/aig/hop/hop.h +++ b/src/aig/hop/hop.h @@ -149,7 +149,7 @@ static inline int Hop_ManNodeNum( Hop_Man_t * p ) { return p->nO static inline int Hop_ManGetCost( Hop_Man_t * p ) { return p->nObjs[AIG_AND]+3*p->nObjs[AIG_EXOR]; } static inline int Hop_ManObjNum( Hop_Man_t * p ) { return p->nCreated - p->nDeleted; } -static inline Hop_Type_t Hop_ObjType( Hop_Obj_t * pObj ) { return pObj->Type; } +static inline Hop_Type_t Hop_ObjType( Hop_Obj_t * pObj ) { return (Hop_Type_t)pObj->Type; } static inline int Hop_ObjIsNone( Hop_Obj_t * pObj ) { return pObj->Type == AIG_NONE; } static inline int Hop_ObjIsConst1( Hop_Obj_t * pObj ) { assert(!Hop_IsComplement(pObj)); return pObj->Type == AIG_CONST1; } static inline int Hop_ObjIsPi( Hop_Obj_t * pObj ) { return pObj->Type == AIG_PI; } @@ -182,8 +182,8 @@ static inline Hop_Obj_t * Hop_ObjFanin0( Hop_Obj_t * pObj ) { return Hop_R static inline Hop_Obj_t * Hop_ObjFanin1( Hop_Obj_t * pObj ) { return Hop_Regular(pObj->pFanin1); } static inline Hop_Obj_t * Hop_ObjChild0( Hop_Obj_t * pObj ) { return pObj->pFanin0; } static inline Hop_Obj_t * Hop_ObjChild1( Hop_Obj_t * pObj ) { return pObj->pFanin1; } -static inline Hop_Obj_t * Hop_ObjChild0Copy( Hop_Obj_t * pObj ) { assert( !Hop_IsComplement(pObj) ); return Hop_ObjFanin0(pObj)? Hop_NotCond(Hop_ObjFanin0(pObj)->pData, Hop_ObjFaninC0(pObj)) : NULL; } -static inline Hop_Obj_t * Hop_ObjChild1Copy( Hop_Obj_t * pObj ) { assert( !Hop_IsComplement(pObj) ); return Hop_ObjFanin1(pObj)? Hop_NotCond(Hop_ObjFanin1(pObj)->pData, Hop_ObjFaninC1(pObj)) : NULL; } +static inline Hop_Obj_t * Hop_ObjChild0Copy( Hop_Obj_t * pObj ) { assert( !Hop_IsComplement(pObj) ); return Hop_ObjFanin0(pObj)? Hop_NotCond((Hop_Obj_t *)Hop_ObjFanin0(pObj)->pData, Hop_ObjFaninC0(pObj)) : NULL; } +static inline Hop_Obj_t * Hop_ObjChild1Copy( Hop_Obj_t * pObj ) { assert( !Hop_IsComplement(pObj) ); return Hop_ObjFanin1(pObj)? Hop_NotCond((Hop_Obj_t *)Hop_ObjFanin1(pObj)->pData, Hop_ObjFaninC1(pObj)) : NULL; } static inline int Hop_ObjLevel( Hop_Obj_t * pObj ) { return pObj->nRefs; } static inline int Hop_ObjLevelNew( Hop_Obj_t * pObj ) { return 1 + Hop_ObjIsExor(pObj) + AIG_MAX(Hop_ObjFanin0(pObj)->nRefs, Hop_ObjFanin1(pObj)->nRefs); } static inline int Hop_ObjFaninPhase( Hop_Obj_t * pObj ) { return Hop_IsComplement(pObj)? !Hop_Regular(pObj)->fPhase : pObj->fPhase; } @@ -210,8 +210,16 @@ static inline Hop_Obj_t * Hop_ObjCreateGhost( Hop_Man_t * p, Hop_Obj_t * p0, Ho assert( Type == AIG_PI || Hop_Regular(p0) != Hop_Regular(p1) ); pGhost = Hop_ManGhost(p); pGhost->Type = Type; - pGhost->pFanin0 = p0 < p1? p0 : p1; - pGhost->pFanin1 = p0 < p1? p1 : p0; + if ( Hop_Regular(p0)->Id < Hop_Regular(p1)->Id ) + { + pGhost->pFanin0 = p0; + pGhost->pFanin1 = p1; + } + else + { + pGhost->pFanin0 = p1; + pGhost->pFanin1 = p0; + } return pGhost; } diff --git a/src/aig/hop/hopCheck.c b/src/aig/hop/hopCheck.c index 44bac2d7..9120906f 100644 --- a/src/aig/hop/hopCheck.c +++ b/src/aig/hop/hopCheck.c @@ -74,7 +74,7 @@ int Hop_ManCheck( Hop_Man_t * p ) printf( "Hop_ManCheck: The AIG has internal node \"%p\" with a NULL fanin.\n", pObj ); return 0; } - if ( Hop_ObjFanin0(pObj) >= Hop_ObjFanin1(pObj) ) + if ( Hop_ObjFanin0(pObj)->Id >= Hop_ObjFanin1(pObj)->Id ) { printf( "Hop_ManCheck: The AIG has node \"%p\" with a wrong ordering of fanins.\n", pObj ); return 0; diff --git a/src/aig/hop/hopMan.c b/src/aig/hop/hopMan.c index b7858564..99f5d316 100644 --- a/src/aig/hop/hopMan.c +++ b/src/aig/hop/hopMan.c @@ -60,6 +60,7 @@ Hop_Man_t * Hop_ManStart() p->pConst1->fPhase = 1; p->nCreated = 1; // start the table +// p->nTableSize = 107; p->nTableSize = 10007; p->pTable = ALLOC( Hop_Obj_t *, p->nTableSize ); memset( p->pTable, 0, sizeof(Hop_Obj_t *) * p->nTableSize ); diff --git a/src/aig/hop/hopTable.c b/src/aig/hop/hopTable.c index 4ce81982..8e61ef36 100644 --- a/src/aig/hop/hopTable.c +++ b/src/aig/hop/hopTable.c @@ -38,13 +38,14 @@ static unsigned long Hop_Hash( Hop_Obj_t * pObj, int TableSize ) // returns the place where this node is stored (or should be stored) static Hop_Obj_t ** Hop_TableFind( Hop_Man_t * p, Hop_Obj_t * pObj ) { - int i; + Hop_Obj_t ** ppEntry; assert( Hop_ObjChild0(pObj) && Hop_ObjChild1(pObj) ); - assert( Hop_ObjChild0(pObj) < Hop_ObjChild1(pObj) ); - for ( i = Hop_Hash(pObj, p->nTableSize); p->pTable[i]; i = (i+1) % p->nTableSize ) - if ( p->pTable[i] == pObj ) - break; - return p->pTable + i; + assert( Hop_ObjFanin0(pObj)->Id < Hop_ObjFanin1(pObj)->Id ); + for ( ppEntry = p->pTable + Hop_Hash(pObj, p->nTableSize); *ppEntry; ppEntry = &(*ppEntry)->pNext ) + if ( *ppEntry == pObj ) + return ppEntry; + assert( *ppEntry == NULL ); + return ppEntry; } static void Hop_TableResize( Hop_Man_t * p ); @@ -56,7 +57,7 @@ static unsigned int Cudd_PrimeAig( unsigned int p ); /**Function************************************************************* - Synopsis [Checks if node with the given attributes is in the hash table.] + Synopsis [Checks if a node with the given attributes is in the hash table.] Description [] @@ -67,18 +68,18 @@ static unsigned int Cudd_PrimeAig( unsigned int p ); ***********************************************************************/ Hop_Obj_t * Hop_TableLookup( Hop_Man_t * p, Hop_Obj_t * pGhost ) { - int i; + Hop_Obj_t * pEntry; assert( !Hop_IsComplement(pGhost) ); assert( Hop_ObjChild0(pGhost) && Hop_ObjChild1(pGhost) ); - assert( Hop_ObjChild0(pGhost) < Hop_ObjChild1(pGhost) ); + assert( Hop_ObjFanin0(pGhost)->Id < Hop_ObjFanin1(pGhost)->Id ); if ( p->fRefCount && (!Hop_ObjRefs(Hop_ObjFanin0(pGhost)) || !Hop_ObjRefs(Hop_ObjFanin1(pGhost))) ) return NULL; - for ( i = Hop_Hash(pGhost, p->nTableSize); p->pTable[i]; i = (i+1) % p->nTableSize ) + for ( pEntry = p->pTable[Hop_Hash(pGhost, p->nTableSize)]; pEntry; pEntry = pEntry->pNext ) { - if ( Hop_ObjChild0(p->pTable[i]) == Hop_ObjChild0(pGhost) && - Hop_ObjChild1(p->pTable[i]) == Hop_ObjChild1(pGhost) && - Hop_ObjType(p->pTable[i]) == Hop_ObjType(pGhost) ) - return p->pTable[i]; + if ( Hop_ObjChild0(pEntry) == Hop_ObjChild0(pGhost) && + Hop_ObjChild1(pEntry) == Hop_ObjChild1(pGhost) && + Hop_ObjType(pEntry) == Hop_ObjType(pGhost) ) + return pEntry; } return NULL; } @@ -99,7 +100,7 @@ void Hop_TableInsert( Hop_Man_t * p, Hop_Obj_t * pObj ) Hop_Obj_t ** ppPlace; assert( !Hop_IsComplement(pObj) ); assert( Hop_TableLookup(p, pObj) == NULL ); - if ( p->nTableSize < 2 * Hop_ManNodeNum(p) ) + if ( (pObj->Id & 0xFF) == 0 && 2 * p->nTableSize < Hop_ManNodeNum(p) ) Hop_TableResize( p ); ppPlace = Hop_TableFind( p, pObj ); assert( *ppPlace == NULL ); @@ -119,20 +120,13 @@ void Hop_TableInsert( Hop_Man_t * p, Hop_Obj_t * pObj ) ***********************************************************************/ void Hop_TableDelete( Hop_Man_t * p, Hop_Obj_t * pObj ) { - Hop_Obj_t * pEntry, ** ppPlace; - int i; + Hop_Obj_t ** ppPlace; assert( !Hop_IsComplement(pObj) ); ppPlace = Hop_TableFind( p, pObj ); assert( *ppPlace == pObj ); // node should be in the table - *ppPlace = NULL; - // rehash the adjacent entries - i = ppPlace - p->pTable; - for ( i = (i+1) % p->nTableSize; p->pTable[i]; i = (i+1) % p->nTableSize ) - { - pEntry = p->pTable[i]; - p->pTable[i] = 0; - Hop_TableInsert( p, pEntry ); - } + // remove the node + *ppPlace = pObj->pNext; + pObj->pNext = NULL; } /**Function************************************************************* @@ -148,9 +142,11 @@ void Hop_TableDelete( Hop_Man_t * p, Hop_Obj_t * pObj ) ***********************************************************************/ int Hop_TableCountEntries( Hop_Man_t * p ) { + Hop_Obj_t * pEntry; int i, Counter = 0; for ( i = 0; i < p->nTableSize; i++ ) - Counter += (p->pTable[i] != NULL); + for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext ) + Counter++; return Counter; } @@ -167,30 +163,32 @@ int Hop_TableCountEntries( Hop_Man_t * p ) ***********************************************************************/ void Hop_TableResize( Hop_Man_t * p ) { + Hop_Obj_t * pEntry, * pNext; Hop_Obj_t ** pTableOld, ** ppPlace; - int nTableSizeOld, Counter, nEntries, e, clk; + int nTableSizeOld, Counter, nEntries, i, clk; clk = clock(); // save the old table pTableOld = p->pTable; nTableSizeOld = p->nTableSize; // get the new table - p->nTableSize = Cudd_PrimeAig( 5 * Hop_ManNodeNum(p) ); + p->nTableSize = Cudd_PrimeAig( 2 * Hop_ManNodeNum(p) ); p->pTable = ALLOC( Hop_Obj_t *, p->nTableSize ); memset( p->pTable, 0, sizeof(Hop_Obj_t *) * p->nTableSize ); // rehash the entries from the old table Counter = 0; - for ( e = 0; e < nTableSizeOld; e++ ) + for ( i = 0; i < nTableSizeOld; i++ ) + for ( pEntry = pTableOld[i], pNext = pEntry? pEntry->pNext : NULL; pEntry; pEntry = pNext, pNext = pEntry? pEntry->pNext : NULL ) { - if ( pTableOld[e] == 0 ) - continue; + // get the place where this entry goes in the table + ppPlace = Hop_TableFind( p, pEntry ); + assert( *ppPlace == NULL ); // should not be there + // add the entry to the list + *ppPlace = pEntry; + pEntry->pNext = NULL; Counter++; - // get the place where this entry goes in the table table - ppPlace = Hop_TableFind( p, pTableOld[e] ); - assert( *ppPlace == NULL ); // should not be in the table - *ppPlace = pTableOld[e]; } nEntries = Hop_ManNodeNum(p); -// assert( Counter == nEntries ); + assert( Counter == nEntries ); // printf( "Increasing the structural table size from %6d to %6d. ", nTableSizeOld, p->nTableSize ); // PRT( "Time", clock() - clk ); // replace the table and the parameters @@ -210,16 +208,15 @@ clk = clock(); ******************************************************************************/ void Hop_TableProfile( Hop_Man_t * p ) { - int i, Counter = 0; + Hop_Obj_t * pEntry; + int i, Counter; for ( i = 0; i < p->nTableSize; i++ ) { - if ( p->pTable[i] ) + Counter = 0; + for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext ) Counter++; - else if ( Counter ) - { + if ( Counter ) printf( "%d ", Counter ); - Counter = 0; - } } } @@ -237,7 +234,6 @@ void Hop_TableProfile( Hop_Man_t * p ) unsigned int Cudd_PrimeAig( unsigned int p) { int i,pn; - p--; do { p++; |