src/base/abc/abcAig.c File Reference

#include "abc.h"
Include dependency graph for abcAig.c:

Go to the source code of this file.

Data Structures

struct  Abc_Aig_t_

Defines

#define Abc_AigBinForEachEntry(pBin, pEnt)
#define Abc_AigBinForEachEntrySafe(pBin, pEnt, pEnt2)

Functions

static unsigned Abc_HashKey2 (Abc_Obj_t *p0, Abc_Obj_t *p1, int TableSize)
static Abc_Obj_t * Abc_AigAndCreate (Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1)
static Abc_Obj_t * Abc_AigAndCreateFrom (Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1, Abc_Obj_t *pAnd)
static void Abc_AigAndDelete (Abc_Aig_t *pMan, Abc_Obj_t *pThis)
static void Abc_AigResize (Abc_Aig_t *pMan)
static void Abc_AigReplace_int (Abc_Aig_t *pMan, Abc_Obj_t *pOld, Abc_Obj_t *pNew, int fUpdateLevel)
static void Abc_AigUpdateLevel_int (Abc_Aig_t *pMan)
static void Abc_AigUpdateLevelR_int (Abc_Aig_t *pMan)
static void Abc_AigRemoveFromLevelStructure (Vec_Vec_t *vStruct, Abc_Obj_t *pNode)
static void Abc_AigRemoveFromLevelStructureR (Vec_Vec_t *vStruct, Abc_Obj_t *pNode)
Abc_Aig_t * Abc_AigAlloc (Abc_Ntk_t *pNtkAig)
void Abc_AigFree (Abc_Aig_t *pMan)
int Abc_AigCleanup (Abc_Aig_t *pMan)
bool Abc_AigCheck (Abc_Aig_t *pMan)
int Abc_AigLevel (Abc_Ntk_t *pNtk)
Abc_Obj_t * Abc_AigAndLookup (Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1)
Abc_Obj_t * Abc_AigXorLookup (Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1, int *pType)
Abc_Obj_t * Abc_AigMuxLookup (Abc_Aig_t *pMan, Abc_Obj_t *pC, Abc_Obj_t *pT, Abc_Obj_t *pE, int *pType)
void Abc_AigRehash (Abc_Aig_t *pMan)
Abc_Obj_t * Abc_AigConst1 (Abc_Ntk_t *pNtk)
Abc_Obj_t * Abc_AigAnd (Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1)
Abc_Obj_t * Abc_AigOr (Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1)
Abc_Obj_t * Abc_AigXor (Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1)
Abc_Obj_t * Abc_AigMiter_rec (Abc_Aig_t *pMan, Abc_Obj_t **ppObjs, int nObjs)
Abc_Obj_t * Abc_AigMiter (Abc_Aig_t *pMan, Vec_Ptr_t *vPairs)
Abc_Obj_t * Abc_AigMiter2 (Abc_Aig_t *pMan, Vec_Ptr_t *vPairs)
void Abc_AigReplace (Abc_Aig_t *pMan, Abc_Obj_t *pOld, Abc_Obj_t *pNew, bool fUpdateLevel)
void Abc_AigDeleteNode (Abc_Aig_t *pMan, Abc_Obj_t *pNode)
bool Abc_AigNodeHasComplFanoutEdge (Abc_Obj_t *pNode)
bool Abc_AigNodeHasComplFanoutEdgeTrav (Abc_Obj_t *pNode)
void Abc_AigPrintNode (Abc_Obj_t *pNode)
bool Abc_AigNodeIsAcyclic (Abc_Obj_t *pNode, Abc_Obj_t *pRoot)
void Abc_AigCheckFaninOrder (Abc_Aig_t *pMan)
void Abc_AigSetNodePhases (Abc_Ntk_t *pNtk)
Vec_Ptr_t * Abc_AigUpdateStart (Abc_Aig_t *pMan, Vec_Ptr_t **pvUpdatedNets)
void Abc_AigUpdateStop (Abc_Aig_t *pMan)
void Abc_AigUpdateReset (Abc_Aig_t *pMan)
int Abc_AigCountNext (Abc_Aig_t *pMan)

Define Documentation

#define Abc_AigBinForEachEntry ( pBin,
pEnt   ) 
Value:
for ( pEnt = pBin;                                         \
          pEnt;                                                \
          pEnt = pEnt->pNext )

Definition at line 72 of file abcAig.c.

#define Abc_AigBinForEachEntrySafe ( pBin,
pEnt,
pEnt2   ) 
Value:
for ( pEnt = pBin,                                         \
          pEnt2 = pEnt? pEnt->pNext: NULL;                     \
          pEnt;                                                \
          pEnt = pEnt2,                                        \
          pEnt2 = pEnt? pEnt->pNext: NULL )

Definition at line 76 of file abcAig.c.

Function Documentation

Abc_Aig_t* Abc_AigAlloc ( Abc_Ntk_t *  pNtkAig  ) 

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Allocates the local AIG manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 125 of file abcAig.c.

00126 {
00127     Abc_Aig_t * pMan;
00128     // start the manager
00129     pMan = ALLOC( Abc_Aig_t, 1 );
00130     memset( pMan, 0, sizeof(Abc_Aig_t) );
00131     // allocate the table
00132     pMan->nBins    = Cudd_PrimeCopy( 10000 );
00133     pMan->pBins    = ALLOC( Abc_Obj_t *, pMan->nBins );
00134     memset( pMan->pBins, 0, sizeof(Abc_Obj_t *) * pMan->nBins );
00135     pMan->vNodes   = Vec_PtrAlloc( 100 );
00136     pMan->vLevels  = Vec_VecAlloc( 100 );
00137     pMan->vLevelsR = Vec_VecAlloc( 100 );
00138     pMan->vStackReplaceOld = Vec_PtrAlloc( 100 );
00139     pMan->vStackReplaceNew = Vec_PtrAlloc( 100 );
00140     // create the constant node
00141     assert( pNtkAig->vObjs->nSize == 0 );
00142     pMan->pConst1 = Abc_NtkCreateObj( pNtkAig, ABC_OBJ_NODE );
00143     pMan->pConst1->Type = ABC_OBJ_CONST1;
00144     pMan->pConst1->fPhase = 1;
00145     pNtkAig->nObjCounts[ABC_OBJ_NODE]--;
00146     // save the current network
00147     pMan->pNtkAig = pNtkAig;
00148     return pMan;
00149 }

Abc_Obj_t* Abc_AigAnd ( Abc_Aig_t *  pMan,
Abc_Obj_t *  p0,
Abc_Obj_t *  p1 
)

Function*************************************************************

Synopsis [Performs canonicization step.]

Description [The argument nodes can be complemented.]

SideEffects []

SeeAlso []

Definition at line 700 of file abcAig.c.

00701 {
00702     Abc_Obj_t * pAnd;
00703     if ( (pAnd = Abc_AigAndLookup( pMan, p0, p1 )) )
00704         return pAnd;
00705     return Abc_AigAndCreate( pMan, p0, p1 );
00706 }

Abc_Obj_t * Abc_AigAndCreate ( Abc_Aig_t *  pMan,
Abc_Obj_t *  p0,
Abc_Obj_t *  p1 
) [static]

Function*************************************************************

Synopsis [Performs canonicization step.]

Description [The argument nodes can be complemented.]

SideEffects []

SeeAlso []

Definition at line 314 of file abcAig.c.

00315 {
00316     Abc_Obj_t * pAnd;
00317     unsigned Key;
00318     // check if it is a good time for table resizing
00319     if ( pMan->nEntries > 2 * pMan->nBins )
00320         Abc_AigResize( pMan );
00321     // order the arguments
00322     if ( Abc_ObjRegular(p0)->Id > Abc_ObjRegular(p1)->Id )
00323         pAnd = p0, p0 = p1, p1 = pAnd;
00324     // create the new node
00325     pAnd = Abc_NtkCreateNode( pMan->pNtkAig );
00326     Abc_ObjAddFanin( pAnd, p0 );
00327     Abc_ObjAddFanin( pAnd, p1 );
00328     // set the level of the new node
00329     pAnd->Level  = 1 + ABC_MAX( Abc_ObjRegular(p0)->Level, Abc_ObjRegular(p1)->Level ); 
00330     pAnd->fExor  = Abc_NodeIsExorType(pAnd);
00331     pAnd->fPhase = (Abc_ObjIsComplement(p0) ^ Abc_ObjRegular(p0)->fPhase) & (Abc_ObjIsComplement(p1) ^ Abc_ObjRegular(p1)->fPhase);
00332     // add the node to the corresponding linked list in the table
00333     Key = Abc_HashKey2( p0, p1, pMan->nBins );
00334     pAnd->pNext      = pMan->pBins[Key];
00335     pMan->pBins[Key] = pAnd;
00336     pMan->nEntries++;
00337     // create the cuts if defined
00338 //    if ( pAnd->pNtk->pManCut )
00339 //        Abc_NodeGetCuts( pAnd->pNtk->pManCut, pAnd );
00340     pAnd->pCopy = NULL;
00341     // add the node to the list of updated nodes
00342     if ( pMan->vAddedCells )
00343         Vec_PtrPush( pMan->vAddedCells, pAnd );
00344     // create HAIG
00345     if ( pAnd->pNtk->pHaig )
00346         pAnd->pEquiv = Hop_And( pAnd->pNtk->pHaig, Abc_ObjChild0Equiv(pAnd), Abc_ObjChild1Equiv(pAnd) );
00347     return pAnd;
00348 }

Abc_Obj_t * Abc_AigAndCreateFrom ( Abc_Aig_t *  pMan,
Abc_Obj_t *  p0,
Abc_Obj_t *  p1,
Abc_Obj_t *  pAnd 
) [static]

Function*************************************************************

Synopsis [Performs canonicization step.]

Description [The argument nodes can be complemented.]

SideEffects []

SeeAlso []

Definition at line 361 of file abcAig.c.

00362 {
00363     Abc_Obj_t * pTemp;
00364     unsigned Key;
00365     assert( !Abc_ObjIsComplement(pAnd) );
00366     // order the arguments
00367     if ( Abc_ObjRegular(p0)->Id > Abc_ObjRegular(p1)->Id )
00368         pTemp = p0, p0 = p1, p1 = pTemp;
00369     // create the new node
00370     Abc_ObjAddFanin( pAnd, p0 );
00371     Abc_ObjAddFanin( pAnd, p1 );
00372     // set the level of the new node
00373     pAnd->Level      = 1 + ABC_MAX( Abc_ObjRegular(p0)->Level, Abc_ObjRegular(p1)->Level ); 
00374     pAnd->fExor      = Abc_NodeIsExorType(pAnd);
00375     // add the node to the corresponding linked list in the table
00376     Key = Abc_HashKey2( p0, p1, pMan->nBins );
00377     pAnd->pNext      = pMan->pBins[Key];
00378     pMan->pBins[Key] = pAnd;
00379     pMan->nEntries++;
00380     // create the cuts if defined
00381 //    if ( pAnd->pNtk->pManCut )
00382 //        Abc_NodeGetCuts( pAnd->pNtk->pManCut, pAnd );
00383     pAnd->pCopy = NULL;
00384     // add the node to the list of updated nodes
00385 //    if ( pMan->vAddedCells )
00386 //        Vec_PtrPush( pMan->vAddedCells, pAnd );
00387     // create HAIG
00388     if ( pAnd->pNtk->pHaig )
00389         pAnd->pEquiv = Hop_And( pAnd->pNtk->pHaig, Abc_ObjChild0Equiv(pAnd), Abc_ObjChild1Equiv(pAnd) );
00390     return pAnd;
00391 }

void Abc_AigAndDelete ( Abc_Aig_t *  pMan,
Abc_Obj_t *  pThis 
) [static]

Function*************************************************************

Synopsis [Deletes an AIG node from the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 543 of file abcAig.c.

00544 {
00545     Abc_Obj_t * pAnd, * pAnd0, * pAnd1, ** ppPlace;
00546     unsigned Key;
00547     assert( !Abc_ObjIsComplement(pThis) );
00548     assert( Abc_ObjIsNode(pThis) );
00549     assert( Abc_ObjFaninNum(pThis) == 2 );
00550     assert( pMan->pNtkAig == pThis->pNtk );
00551     // get the hash key for these two nodes
00552     pAnd0 = Abc_ObjRegular( Abc_ObjChild0(pThis) );
00553     pAnd1 = Abc_ObjRegular( Abc_ObjChild1(pThis) );
00554     Key = Abc_HashKey2( Abc_ObjChild0(pThis), Abc_ObjChild1(pThis), pMan->nBins );
00555     // find the matching node in the table
00556     ppPlace = pMan->pBins + Key;
00557     Abc_AigBinForEachEntry( pMan->pBins[Key], pAnd )
00558     {
00559         if ( pAnd != pThis )
00560         {
00561             ppPlace = &pAnd->pNext;
00562             continue;
00563         }
00564         *ppPlace = pAnd->pNext;
00565         break;
00566     }
00567     assert( pAnd == pThis );
00568     pMan->nEntries--;
00569     // delete the cuts if defined
00570     if ( pThis->pNtk->pManCut )
00571         Abc_NodeFreeCuts( pThis->pNtk->pManCut, pThis );
00572 }

Abc_Obj_t* Abc_AigAndLookup ( Abc_Aig_t *  pMan,
Abc_Obj_t *  p0,
Abc_Obj_t *  p1 
)

Function*************************************************************

Synopsis [Performs canonicization step.]

Description [The argument nodes can be complemented.]

SideEffects []

SeeAlso []

Definition at line 404 of file abcAig.c.

00405 {
00406     Abc_Obj_t * pAnd, * pConst1;
00407     unsigned Key;
00408     assert( Abc_ObjRegular(p0)->pNtk->pManFunc == pMan );
00409     assert( Abc_ObjRegular(p1)->pNtk->pManFunc == pMan );
00410     // check for trivial cases
00411     pConst1 = Abc_AigConst1(pMan->pNtkAig);
00412     if ( p0 == p1 )
00413         return p0;
00414     if ( p0 == Abc_ObjNot(p1) )
00415         return Abc_ObjNot(pConst1);
00416     if ( Abc_ObjRegular(p0) == pConst1 )
00417     {
00418         if ( p0 == pConst1 )
00419             return p1;
00420         return Abc_ObjNot(pConst1);
00421     }
00422     if ( Abc_ObjRegular(p1) == pConst1 )
00423     {
00424         if ( p1 == pConst1 )
00425             return p0;
00426         return Abc_ObjNot(pConst1);
00427     }
00428 /*
00429     {
00430         int nFans0 = Abc_ObjFanoutNum( Abc_ObjRegular(p0) );
00431         int nFans1 = Abc_ObjFanoutNum( Abc_ObjRegular(p1) );
00432         if ( nFans0 == 0 || nFans1 == 0 )
00433             pMan->nStrash0++;
00434         else if ( nFans0 == 1 || nFans1 == 1 )
00435             pMan->nStrash1++;
00436         else if ( nFans0 <= 100 && nFans1 <= 100 )
00437             pMan->nStrash5++;
00438         else
00439             pMan->nStrash2++;
00440     }
00441 */
00442     {
00443         int nFans0 = Abc_ObjFanoutNum( Abc_ObjRegular(p0) );
00444         int nFans1 = Abc_ObjFanoutNum( Abc_ObjRegular(p1) );
00445         if ( nFans0 == 0 || nFans1 == 0 )
00446             return NULL;
00447     }
00448 
00449     // order the arguments
00450     if ( Abc_ObjRegular(p0)->Id > Abc_ObjRegular(p1)->Id )
00451         pAnd = p0, p0 = p1, p1 = pAnd;
00452     // get the hash key for these two nodes
00453     Key = Abc_HashKey2( p0, p1, pMan->nBins );
00454     // find the matching node in the table
00455     Abc_AigBinForEachEntry( pMan->pBins[Key], pAnd )
00456         if ( p0 == Abc_ObjChild0(pAnd) && p1 == Abc_ObjChild1(pAnd) )
00457         {
00458 //            assert( Abc_ObjFanoutNum(Abc_ObjRegular(p0)) && Abc_ObjFanoutNum(p1) );
00459              return pAnd;
00460         }
00461     return NULL;
00462 }

bool Abc_AigCheck ( Abc_Aig_t *  pMan  ) 

Function*************************************************************

Synopsis [Makes sure that every node in the table is in the network and vice versa.]

Description []

SideEffects []

SeeAlso []

Definition at line 223 of file abcAig.c.

00224 {
00225     Abc_Obj_t * pObj, * pAnd;
00226     int i, nFanins, Counter;
00227     Abc_NtkForEachNode( pMan->pNtkAig, pObj, i )
00228     {
00229         nFanins = Abc_ObjFaninNum(pObj);
00230         if ( nFanins == 0 )
00231         {
00232             if ( !Abc_AigNodeIsConst(pObj) )
00233             {
00234                 printf( "Abc_AigCheck: The AIG has non-standard constant nodes.\n" );
00235                 return 0;
00236             }
00237             continue;
00238         }
00239         if ( nFanins == 1 )
00240         {
00241             printf( "Abc_AigCheck: The AIG has single input nodes.\n" );
00242             return 0;
00243         }
00244         if ( nFanins > 2 )
00245         {
00246             printf( "Abc_AigCheck: The AIG has non-standard nodes.\n" );
00247             return 0;
00248         }
00249         if ( pObj->Level != 1 + ABC_MAX( Abc_ObjFanin0(pObj)->Level, Abc_ObjFanin1(pObj)->Level ) )
00250             printf( "Abc_AigCheck: Node \"%s\" has level that does not agree with the fanin levels.\n", Abc_ObjName(pObj) );
00251         pAnd = Abc_AigAndLookup( pMan, Abc_ObjChild0(pObj), Abc_ObjChild1(pObj) );
00252         if ( pAnd != pObj )
00253             printf( "Abc_AigCheck: Node \"%s\" is not in the structural hashing table.\n", Abc_ObjName(pObj) );
00254     }
00255     // count the number of nodes in the table
00256     Counter = 0;
00257     for ( i = 0; i < pMan->nBins; i++ )
00258         Abc_AigBinForEachEntry( pMan->pBins[i], pAnd )
00259             Counter++;
00260     if ( Counter != Abc_NtkNodeNum(pMan->pNtkAig) )
00261     {
00262         printf( "Abc_AigCheck: The number of nodes in the structural hashing table is wrong.\n" );
00263         return 0;
00264     }
00265     // if the node is a choice node, nodes in its class should not have fanouts
00266     Abc_NtkForEachNode( pMan->pNtkAig, pObj, i )
00267         if ( Abc_AigNodeIsChoice(pObj) )
00268             for ( pAnd = pObj->pData; pAnd; pAnd = pAnd->pData )
00269                 if ( Abc_ObjFanoutNum(pAnd) > 0 )
00270                 {
00271                     printf( "Abc_AigCheck: Representative %s", Abc_ObjName(pAnd) );
00272                     printf( " of choice node %s has %d fanouts.\n", Abc_ObjName(pObj), Abc_ObjFanoutNum(pAnd) );
00273                     return 0;
00274                 }
00275     return 1;
00276 }

void Abc_AigCheckFaninOrder ( Abc_Aig_t *  pMan  ) 

Function*************************************************************

Synopsis [Resizes the hash table of AIG nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 1341 of file abcAig.c.

01342 {
01343     Abc_Obj_t * pEnt;
01344     int i;
01345     for ( i = 0; i < pMan->nBins; i++ )
01346         Abc_AigBinForEachEntry( pMan->pBins[i], pEnt )
01347         {
01348             if ( Abc_ObjRegular(Abc_ObjChild0(pEnt))->Id > Abc_ObjRegular(Abc_ObjChild1(pEnt))->Id )
01349             {
01350 //                int i0 = Abc_ObjRegular(Abc_ObjChild0(pEnt))->Id;
01351 //                int i1 = Abc_ObjRegular(Abc_ObjChild1(pEnt))->Id;
01352                 printf( "Node %d has incorrect ordering of fanins.\n", pEnt->Id );
01353             }
01354         }
01355 }

int Abc_AigCleanup ( Abc_Aig_t *  pMan  ) 

Function*************************************************************

Synopsis [Returns the number of dangling nodes removed.]

Description []

SideEffects []

SeeAlso []

Definition at line 191 of file abcAig.c.

00192 {
00193     Vec_Ptr_t * vDangles;
00194     Abc_Obj_t * pAnd;
00195     int i, nNodesOld;
00196 //    printf( "Strash0 = %d.  Strash1 = %d.  Strash100 = %d.  StrashM = %d.\n", 
00197 //        pMan->nStrash0, pMan->nStrash1, pMan->nStrash5, pMan->nStrash2 );
00198     nNodesOld = pMan->nEntries;
00199     // collect the AND nodes that do not fanout
00200     vDangles = Vec_PtrAlloc( 100 );
00201     for ( i = 0; i < pMan->nBins; i++ )
00202         Abc_AigBinForEachEntry( pMan->pBins[i], pAnd )
00203             if ( Abc_ObjFanoutNum(pAnd) == 0 )
00204                 Vec_PtrPush( vDangles, pAnd );
00205     // process the dangling nodes and their MFFCs
00206     Vec_PtrForEachEntry( vDangles, pAnd, i )
00207         Abc_AigDeleteNode( pMan, pAnd );
00208     Vec_PtrFree( vDangles );
00209     return nNodesOld - pMan->nEntries;
00210 }

Abc_Obj_t* Abc_AigConst1 ( Abc_Ntk_t *  pNtk  ) 

Function*************************************************************

Synopsis [Performs canonicization step.]

Description [The argument nodes can be complemented.]

SideEffects []

SeeAlso []

Definition at line 683 of file abcAig.c.

00684 {
00685     assert( Abc_NtkIsStrash(pNtk) );
00686     return ((Abc_Aig_t *)pNtk->pManFunc)->pConst1;
00687 }

int Abc_AigCountNext ( Abc_Aig_t *  pMan  ) 

Function*************************************************************

Synopsis [Start the update list.]

Description []

SideEffects []

SeeAlso []

Definition at line 1457 of file abcAig.c.

01458 {
01459     Abc_Obj_t * pAnd;
01460     int i, Counter = 0, CounterTotal = 0;
01461     // count how many nodes have pNext set
01462     for ( i = 0; i < pMan->nBins; i++ )
01463         Abc_AigBinForEachEntry( pMan->pBins[i], pAnd )
01464         {
01465             Counter += (pAnd->pNext != NULL);
01466             CounterTotal++;
01467         }
01468     printf( "Counter = %d.  Nodes = %d.  Ave = %6.2f\n", Counter, CounterTotal, 1.0 * CounterTotal/pMan->nBins );
01469     return Counter;
01470 }

void Abc_AigDeleteNode ( Abc_Aig_t *  pMan,
Abc_Obj_t *  pNode 
)

Function*************************************************************

Synopsis [Performs internal deletion step.]

Description []

SideEffects []

SeeAlso []

Definition at line 951 of file abcAig.c.

00952 {
00953     Abc_Obj_t * pNode0, * pNode1, * pTemp;
00954     int i, k;
00955 
00956     // make sure the node is regular and dangling
00957     assert( !Abc_ObjIsComplement(pNode) );
00958     assert( Abc_ObjIsNode(pNode) );
00959     assert( Abc_ObjFaninNum(pNode) == 2 );
00960     assert( Abc_ObjFanoutNum(pNode) == 0 );
00961 
00962     // when deleting an old node that is scheduled for replacement, remove it from the replacement queue
00963     Vec_PtrForEachEntry( pMan->vStackReplaceOld, pTemp, i )
00964         if ( pNode == pTemp )
00965         {
00966             // remove the entry from the replacement array
00967             for ( k = i; k < pMan->vStackReplaceOld->nSize - 1; k++ )
00968             {
00969                 pMan->vStackReplaceOld->pArray[k] = pMan->vStackReplaceOld->pArray[k+1];
00970                 pMan->vStackReplaceNew->pArray[k] = pMan->vStackReplaceNew->pArray[k+1];
00971             }
00972             pMan->vStackReplaceOld->nSize--;
00973             pMan->vStackReplaceNew->nSize--;
00974         }
00975 
00976     // when deleting a new node that should replace another node, do not delete
00977     Vec_PtrForEachEntry( pMan->vStackReplaceNew, pTemp, i )
00978         if ( pNode == Abc_ObjRegular(pTemp) )
00979             return;
00980 
00981     // remember the node's fanins
00982     pNode0 = Abc_ObjFanin0( pNode );
00983     pNode1 = Abc_ObjFanin1( pNode );
00984 
00985     // add the node to the list of updated nodes
00986     if ( pMan->vUpdatedNets )
00987     {
00988         Vec_PtrPushUnique( pMan->vUpdatedNets, pNode0 );
00989         Vec_PtrPushUnique( pMan->vUpdatedNets, pNode1 );
00990     }
00991 
00992     // remove the node from the table
00993     Abc_AigAndDelete( pMan, pNode );
00994     // if the node is in the level structure, remove it
00995     if ( pNode->fMarkA )
00996         Abc_AigRemoveFromLevelStructure( pMan->vLevels, pNode );
00997     if ( pNode->fMarkB )
00998         Abc_AigRemoveFromLevelStructureR( pMan->vLevelsR, pNode );
00999     // remove the node from the network
01000     Abc_NtkDeleteObj( pNode );
01001 
01002     // call recursively for the fanins
01003     if ( Abc_ObjIsNode(pNode0) && pNode0->vFanouts.nSize == 0 )
01004         Abc_AigDeleteNode( pMan, pNode0 );
01005     if ( Abc_ObjIsNode(pNode1) && pNode1->vFanouts.nSize == 0 )
01006         Abc_AigDeleteNode( pMan, pNode1 );
01007 }

void Abc_AigFree ( Abc_Aig_t *  pMan  ) 

Function*************************************************************

Synopsis [Deallocates the local AIG manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 162 of file abcAig.c.

00163 {
00164     assert( Vec_PtrSize( pMan->vStackReplaceOld ) == 0 );
00165     assert( Vec_PtrSize( pMan->vStackReplaceNew ) == 0 );
00166     // free the table
00167     if ( pMan->vAddedCells )
00168         Vec_PtrFree( pMan->vAddedCells );
00169     if ( pMan->vUpdatedNets )
00170         Vec_PtrFree( pMan->vUpdatedNets );
00171     Vec_VecFree( pMan->vLevels );
00172     Vec_VecFree( pMan->vLevelsR );
00173     Vec_PtrFree( pMan->vStackReplaceOld );
00174     Vec_PtrFree( pMan->vStackReplaceNew );
00175     Vec_PtrFree( pMan->vNodes );
00176     free( pMan->pBins );
00177     free( pMan );
00178 }

int Abc_AigLevel ( Abc_Ntk_t *  pNtk  ) 

Function*************************************************************

Synopsis [Computes the number of logic levels not counting PIs/POs.]

Description []

SideEffects []

SeeAlso []

Definition at line 289 of file abcAig.c.

00290 {
00291     Abc_Obj_t * pNode;
00292     int i, LevelsMax;
00293     assert( Abc_NtkIsStrash(pNtk) );
00294     // perform the traversal
00295     LevelsMax = 0;
00296     Abc_NtkForEachCo( pNtk, pNode, i )
00297         if ( LevelsMax < (int)Abc_ObjFanin0(pNode)->Level )
00298             LevelsMax = (int)Abc_ObjFanin0(pNode)->Level;
00299     return LevelsMax;
00300 }

Abc_Obj_t* Abc_AigMiter ( Abc_Aig_t *  pMan,
Vec_Ptr_t *  vPairs 
)

Function*************************************************************

Synopsis [Implements the miter.]

Description []

SideEffects []

SeeAlso []

Definition at line 773 of file abcAig.c.

00774 {
00775     int i;
00776     if ( vPairs->nSize == 0 )
00777         return Abc_ObjNot( Abc_AigConst1(pMan->pNtkAig) );
00778     assert( vPairs->nSize % 2 == 0 );
00779     // go through the cubes of the node's SOP
00780     for ( i = 0; i < vPairs->nSize; i += 2 )
00781         vPairs->pArray[i/2] = Abc_AigXor( pMan, vPairs->pArray[i], vPairs->pArray[i+1] );
00782     vPairs->nSize = vPairs->nSize/2;
00783     return Abc_AigMiter_rec( pMan, (Abc_Obj_t **)vPairs->pArray, vPairs->nSize );
00784 }

Abc_Obj_t* Abc_AigMiter2 ( Abc_Aig_t *  pMan,
Vec_Ptr_t *  vPairs 
)

Function*************************************************************

Synopsis [Implements the miter.]

Description []

SideEffects []

SeeAlso []

Definition at line 797 of file abcAig.c.

00798 {
00799     Abc_Obj_t * pMiter, * pXor;
00800     int i;
00801     assert( vPairs->nSize % 2 == 0 );
00802     // go through the cubes of the node's SOP
00803     pMiter = Abc_ObjNot( Abc_AigConst1(pMan->pNtkAig) );
00804     for ( i = 0; i < vPairs->nSize; i += 2 )
00805     {
00806         pXor   = Abc_AigXor( pMan, vPairs->pArray[i], vPairs->pArray[i+1] );
00807         pMiter = Abc_AigOr( pMan, pMiter, pXor );
00808     }
00809     return pMiter;
00810 }

Abc_Obj_t* Abc_AigMiter_rec ( Abc_Aig_t *  pMan,
Abc_Obj_t **  ppObjs,
int  nObjs 
)

Function*************************************************************

Synopsis [Implements the miter.]

Description []

SideEffects []

SeeAlso []

Definition at line 752 of file abcAig.c.

00753 {
00754     Abc_Obj_t * pObj1, * pObj2;
00755     if ( nObjs == 1 )
00756         return ppObjs[0];
00757     pObj1 = Abc_AigMiter_rec( pMan, ppObjs,           nObjs/2 );
00758     pObj2 = Abc_AigMiter_rec( pMan, ppObjs + nObjs/2, nObjs - nObjs/2 );
00759     return Abc_AigOr( pMan, pObj1, pObj2 );
00760 }

Abc_Obj_t* Abc_AigMuxLookup ( Abc_Aig_t *  pMan,
Abc_Obj_t *  pC,
Abc_Obj_t *  pT,
Abc_Obj_t *  pE,
int *  pType 
)

Function*************************************************************

Synopsis [Returns the gate implementing EXOR of the two arguments if it exists.]

Description [The argument nodes can be complemented.]

SideEffects []

SeeAlso []

Definition at line 509 of file abcAig.c.

00510 {
00511     Abc_Obj_t * pNode1, * pNode2, * pNode;
00512     // set the flag to zero
00513     if ( pType ) *pType = 0;
00514     // check the case of MUX(c,t,e) = OR(ct', c'e')'
00515     if ( (pNode1 = Abc_AigAndLookup(pMan, pC, Abc_ObjNot(pT))) &&
00516          (pNode2 = Abc_AigAndLookup(pMan, Abc_ObjNot(pC), Abc_ObjNot(pE))) ) 
00517     {
00518         pNode = Abc_AigAndLookup( pMan, Abc_ObjNot(pNode1), Abc_ObjNot(pNode2) );
00519         if ( pNode && pType ) *pType = 1;
00520         return pNode;
00521     }
00522     // check the case of MUX(c,t,e) = OR(ct, c'e)
00523     if ( (pNode1 = Abc_AigAndLookup(pMan, pC, pT)) &&
00524          (pNode2 = Abc_AigAndLookup(pMan, Abc_ObjNot(pC), pE)) ) 
00525     {
00526         pNode = Abc_AigAndLookup( pMan, Abc_ObjNot(pNode1), Abc_ObjNot(pNode2) );
00527         return pNode? Abc_ObjNot(pNode) : NULL;
00528     }
00529     return NULL;
00530 }

bool Abc_AigNodeHasComplFanoutEdge ( Abc_Obj_t *  pNode  ) 

Function*************************************************************

Synopsis [Returns 1 if the node has at least one complemented fanout.]

Description [A fanout is complemented if the fanout's fanin edge pointing to the given node is complemented.]

SideEffects []

SeeAlso []

Definition at line 1203 of file abcAig.c.

01204 {
01205     Abc_Obj_t * pFanout;
01206     int i, iFanin;
01207     Abc_ObjForEachFanout( pNode, pFanout, i )
01208     {
01209         iFanin = Vec_IntFind( &pFanout->vFanins, pNode->Id );
01210         assert( iFanin >= 0 );
01211         if ( Abc_ObjFaninC( pFanout, iFanin ) )
01212             return 1;
01213     }
01214     return 0;
01215 }

bool Abc_AigNodeHasComplFanoutEdgeTrav ( Abc_Obj_t *  pNode  ) 

Function*************************************************************

Synopsis [Returns 1 if the node has at least one complemented fanout.]

Description [A fanout is complemented if the fanout's fanin edge pointing to the given node is complemented. Only the fanouts with current TravId are counted.]

SideEffects []

SeeAlso []

Definition at line 1230 of file abcAig.c.

01231 {
01232     Abc_Obj_t * pFanout;
01233     int i, iFanin;
01234     Abc_ObjForEachFanout( pNode, pFanout, i )
01235     {
01236         if ( !Abc_NodeIsTravIdCurrent(pFanout) )
01237             continue;
01238         iFanin = Vec_IntFind( &pFanout->vFanins, pNode->Id );
01239         assert( iFanin >= 0 );
01240         if ( Abc_ObjFaninC( pFanout, iFanin ) )
01241             return 1;
01242     }
01243     return 0;
01244 }

bool Abc_AigNodeIsAcyclic ( Abc_Obj_t *  pNode,
Abc_Obj_t *  pRoot 
)

Function*************************************************************

Synopsis [Check if the node has a combination loop of depth 1 or 2.]

Description []

SideEffects []

SeeAlso []

Definition at line 1292 of file abcAig.c.

01293 {
01294     Abc_Obj_t * pFanin0, * pFanin1;
01295     Abc_Obj_t * pChild00, * pChild01;
01296     Abc_Obj_t * pChild10, * pChild11;
01297     if ( !Abc_AigNodeIsAnd(pNode) )
01298         return 1;
01299     pFanin0 = Abc_ObjFanin0(pNode);
01300     pFanin1 = Abc_ObjFanin1(pNode);
01301     if ( pRoot == pFanin0 || pRoot == pFanin1 )
01302         return 0;
01303     if ( Abc_ObjIsCi(pFanin0) )
01304     {
01305         pChild00 = NULL;
01306         pChild01 = NULL;
01307     }
01308     else
01309     {
01310         pChild00 = Abc_ObjFanin0(pFanin0);
01311         pChild01 = Abc_ObjFanin1(pFanin0);
01312         if ( pRoot == pChild00 || pRoot == pChild01 )
01313             return 0;
01314     }
01315     if ( Abc_ObjIsCi(pFanin1) )
01316     {
01317         pChild10 = NULL;
01318         pChild11 = NULL;
01319     }
01320     else
01321     {
01322         pChild10 = Abc_ObjFanin0(pFanin1);
01323         pChild11 = Abc_ObjFanin1(pFanin1);
01324         if ( pRoot == pChild10 || pRoot == pChild11 )
01325             return 0;
01326     }
01327     return 1;
01328 }

Abc_Obj_t* Abc_AigOr ( Abc_Aig_t *  pMan,
Abc_Obj_t *  p0,
Abc_Obj_t *  p1 
)

Function*************************************************************

Synopsis [Implements Boolean OR.]

Description []

SideEffects []

SeeAlso []

Definition at line 719 of file abcAig.c.

00720 {
00721     return Abc_ObjNot( Abc_AigAnd( pMan, Abc_ObjNot(p0), Abc_ObjNot(p1) ) );
00722 }

void Abc_AigPrintNode ( Abc_Obj_t *  pNode  ) 

Function*************************************************************

Synopsis [Prints the AIG node for debugging purposes.]

Description []

SideEffects []

SeeAlso []

Definition at line 1258 of file abcAig.c.

01259 {
01260     Abc_Obj_t * pNodeR = Abc_ObjRegular(pNode);
01261     if ( Abc_ObjIsCi(pNodeR) )
01262     {
01263         printf( "CI %4s%s.\n", Abc_ObjName(pNodeR), Abc_ObjIsComplement(pNode)? "\'" : "" );
01264         return;
01265     }
01266     if ( Abc_AigNodeIsConst(pNodeR) )
01267     {
01268         printf( "Constant 1 %s.\n", Abc_ObjIsComplement(pNode)? "(complemented)" : ""  );
01269         return;
01270     }
01271     // print the node's function
01272     printf( "%7s%s", Abc_ObjName(pNodeR),                Abc_ObjIsComplement(pNode)? "\'" : "" );
01273     printf( " = " );
01274     printf( "%7s%s", Abc_ObjName(Abc_ObjFanin0(pNodeR)), Abc_ObjFaninC0(pNodeR)?     "\'" : "" );
01275     printf( " * " );
01276     printf( "%7s%s", Abc_ObjName(Abc_ObjFanin1(pNodeR)), Abc_ObjFaninC1(pNodeR)?     "\'" : "" );
01277     printf( "\n" );
01278 }

void Abc_AigRehash ( Abc_Aig_t *  pMan  ) 

Function*************************************************************

Synopsis [Resizes the hash table of AIG nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 628 of file abcAig.c.

00629 {
00630     Abc_Obj_t ** pBinsNew;
00631     Abc_Obj_t * pEnt, * pEnt2;
00632     int * pArray;
00633     unsigned Key;
00634     int Counter, Temp, i;
00635 
00636     // allocate a new array
00637     pBinsNew = ALLOC( Abc_Obj_t *, pMan->nBins );
00638     memset( pBinsNew, 0, sizeof(Abc_Obj_t *) * pMan->nBins );
00639     // rehash the entries from the old table
00640     Counter = 0;
00641     for ( i = 0; i < pMan->nBins; i++ )
00642         Abc_AigBinForEachEntrySafe( pMan->pBins[i], pEnt, pEnt2 )
00643         {
00644             // swap the fanins if needed
00645             pArray = pEnt->vFanins.pArray;
00646             if ( pArray[0] > pArray[1] )
00647             {
00648                 Temp = pArray[0];
00649                 pArray[0] = pArray[1];
00650                 pArray[1] = Temp;
00651                 Temp = pEnt->fCompl0;
00652                 pEnt->fCompl0 = pEnt->fCompl1;
00653                 pEnt->fCompl1 = Temp;
00654             }
00655             // rehash the node
00656             Key = Abc_HashKey2( Abc_ObjChild0(pEnt), Abc_ObjChild1(pEnt), pMan->nBins );
00657             pEnt->pNext   = pBinsNew[Key];
00658             pBinsNew[Key] = pEnt;
00659             Counter++;
00660         }
00661     assert( Counter == pMan->nEntries );
00662     // replace the table and the parameters
00663     free( pMan->pBins );
00664     pMan->pBins = pBinsNew;
00665 }

void Abc_AigRemoveFromLevelStructure ( Vec_Vec_t *  vStruct,
Abc_Obj_t *  pNode 
) [static]

Function*************************************************************

Synopsis [Removes the node from the level structure.]

Description []

SideEffects []

SeeAlso []

Definition at line 1141 of file abcAig.c.

01142 {
01143     Vec_Ptr_t * vVecTemp;
01144     Abc_Obj_t * pTemp;
01145     int m;
01146     assert( pNode->fMarkA );
01147     vVecTemp = Vec_VecEntry( vStruct, pNode->Level );
01148     Vec_PtrForEachEntry( vVecTemp, pTemp, m )
01149     {
01150         if ( pTemp != pNode )
01151             continue;
01152         Vec_PtrWriteEntry( vVecTemp, m, NULL );
01153         break;
01154     }
01155     assert( m < Vec_PtrSize(vVecTemp) ); // found
01156     pNode->fMarkA = 0;
01157 }

void Abc_AigRemoveFromLevelStructureR ( Vec_Vec_t *  vStruct,
Abc_Obj_t *  pNode 
) [static]

Function*************************************************************

Synopsis [Removes the node from the level structure.]

Description []

SideEffects []

SeeAlso []

Definition at line 1170 of file abcAig.c.

01171 {
01172     Vec_Ptr_t * vVecTemp;
01173     Abc_Obj_t * pTemp;
01174     int m;
01175     assert( pNode->fMarkB );
01176     vVecTemp = Vec_VecEntry( vStruct, Abc_ObjReverseLevel(pNode) );
01177     Vec_PtrForEachEntry( vVecTemp, pTemp, m )
01178     {
01179         if ( pTemp != pNode )
01180             continue;
01181         Vec_PtrWriteEntry( vVecTemp, m, NULL );
01182         break;
01183     }
01184     assert( m < Vec_PtrSize(vVecTemp) ); // found
01185     pNode->fMarkB = 0;
01186 }

void Abc_AigReplace ( Abc_Aig_t *  pMan,
Abc_Obj_t *  pOld,
Abc_Obj_t *  pNew,
bool  fUpdateLevel 
)

Function*************************************************************

Synopsis [Replaces one AIG node by the other.]

Description []

SideEffects []

SeeAlso []

Definition at line 826 of file abcAig.c.

00827 {
00828     assert( Vec_PtrSize(pMan->vStackReplaceOld) == 0 );
00829     assert( Vec_PtrSize(pMan->vStackReplaceNew) == 0 );
00830     Vec_PtrPush( pMan->vStackReplaceOld, pOld );
00831     Vec_PtrPush( pMan->vStackReplaceNew, pNew );
00832     assert( !Abc_ObjIsComplement(pOld) );
00833     // create HAIG
00834     if ( pOld->pNtk->pHaig )
00835         Hop_ObjCreateChoice( pOld->pEquiv, Abc_ObjRegular(pNew)->pEquiv );
00836     // process the replacements
00837     while ( Vec_PtrSize(pMan->vStackReplaceOld) )
00838     {
00839         pOld = Vec_PtrPop( pMan->vStackReplaceOld );
00840         pNew = Vec_PtrPop( pMan->vStackReplaceNew );
00841         Abc_AigReplace_int( pMan, pOld, pNew, fUpdateLevel );
00842     }
00843     if ( fUpdateLevel )
00844     {
00845         Abc_AigUpdateLevel_int( pMan );
00846         if ( pMan->pNtkAig->vLevelsR ) 
00847             Abc_AigUpdateLevelR_int( pMan );
00848     }
00849 }

void Abc_AigReplace_int ( Abc_Aig_t *  pMan,
Abc_Obj_t *  pOld,
Abc_Obj_t *  pNew,
int  fUpdateLevel 
) [static]

Function*************************************************************

Synopsis [Performs internal replacement step.]

Description []

SideEffects []

SeeAlso []

Definition at line 862 of file abcAig.c.

00863 {
00864     Abc_Obj_t * pFanin1, * pFanin2, * pFanout, * pFanoutNew, * pFanoutFanout;
00865     int k, v, iFanin; 
00866     // make sure the old node is regular and has fanouts
00867     // (the new node can be complemented and can have fanouts)
00868     assert( !Abc_ObjIsComplement(pOld) );
00869     assert( Abc_ObjFanoutNum(pOld) > 0 );
00870     // look at the fanouts of old node
00871     Abc_NodeCollectFanouts( pOld, pMan->vNodes );
00872     Vec_PtrForEachEntry( pMan->vNodes, pFanout, k )
00873     {
00874         if ( Abc_ObjIsCo(pFanout) )
00875         {
00876             Abc_ObjPatchFanin( pFanout, pOld, pNew );
00877             continue;
00878         }
00879         // find the old node as a fanin of this fanout
00880         iFanin = Vec_IntFind( &pFanout->vFanins, pOld->Id );
00881         assert( iFanin == 0 || iFanin == 1 );
00882         // get the new fanin
00883         pFanin1 = Abc_ObjNotCond( pNew, Abc_ObjFaninC(pFanout, iFanin) );
00884         assert( Abc_ObjRegular(pFanin1) != pFanout );
00885         // get another fanin
00886         pFanin2 = Abc_ObjChild( pFanout, iFanin ^ 1 );
00887         assert( Abc_ObjRegular(pFanin2) != pFanout );
00888         // check if the node with these fanins exists
00889         if ( (pFanoutNew = Abc_AigAndLookup( pMan, pFanin1, pFanin2 )) )
00890         { // such node exists (it may be a constant)
00891             // schedule replacement of the old fanout by the new fanout
00892             Vec_PtrPush( pMan->vStackReplaceOld, pFanout );
00893             Vec_PtrPush( pMan->vStackReplaceNew, pFanoutNew );
00894             continue;
00895         }
00896         // such node does not exist - modify the old fanout node 
00897         // (this way the change will not propagate all the way to the COs)
00898         assert( Abc_ObjRegular(pFanin1) != Abc_ObjRegular(pFanin2) );             
00899 
00900         // if the node is in the level structure, remove it
00901         if ( pFanout->fMarkA )
00902             Abc_AigRemoveFromLevelStructure( pMan->vLevels, pFanout );
00903         // if the node is in the level structure, remove it
00904         if ( pFanout->fMarkB )
00905             Abc_AigRemoveFromLevelStructureR( pMan->vLevelsR, pFanout );
00906 
00907         // remove the old fanout node from the structural hashing table
00908         Abc_AigAndDelete( pMan, pFanout );
00909         // remove the fanins of the old fanout
00910         Abc_ObjRemoveFanins( pFanout );
00911         // recreate the old fanout with new fanins and add it to the table
00912         Abc_AigAndCreateFrom( pMan, pFanin1, pFanin2, pFanout );
00913         assert( Abc_AigNodeIsAcyclic(pFanout, pFanout) );
00914 
00915         if ( fUpdateLevel )
00916         {
00917             // schedule the updated fanout for updating direct level
00918             assert( pFanout->fMarkA == 0 );
00919             pFanout->fMarkA = 1;
00920             Vec_VecPush( pMan->vLevels, pFanout->Level, pFanout );
00921             // schedule the updated fanout for updating reverse level
00922             if ( pMan->pNtkAig->vLevelsR ) 
00923             {
00924                 assert( pFanout->fMarkB == 0 );
00925                 pFanout->fMarkB = 1;
00926                 Vec_VecPush( pMan->vLevelsR, Abc_ObjReverseLevel(pFanout), pFanout );
00927             }
00928         }
00929 
00930         // the fanout has changed, update EXOR status of its fanouts
00931         Abc_ObjForEachFanout( pFanout, pFanoutFanout, v )
00932             if ( Abc_AigNodeIsAnd(pFanoutFanout) )
00933                 pFanoutFanout->fExor = Abc_NodeIsExorType(pFanoutFanout);
00934     }
00935     // if the node has no fanouts left, remove its MFFC
00936     if ( Abc_ObjFanoutNum(pOld) == 0 )
00937         Abc_AigDeleteNode( pMan, pOld );
00938 }

void Abc_AigResize ( Abc_Aig_t *  pMan  )  [static]

Function*************************************************************

Synopsis [Resizes the hash table of AIG nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 585 of file abcAig.c.

00586 {
00587     Abc_Obj_t ** pBinsNew;
00588     Abc_Obj_t * pEnt, * pEnt2;
00589     int nBinsNew, Counter, i, clk;
00590     unsigned Key;
00591 
00592 clk = clock();
00593     // get the new table size
00594     nBinsNew = Cudd_PrimeCopy( 3 * pMan->nBins ); 
00595     // allocate a new array
00596     pBinsNew = ALLOC( Abc_Obj_t *, nBinsNew );
00597     memset( pBinsNew, 0, sizeof(Abc_Obj_t *) * nBinsNew );
00598     // rehash the entries from the old table
00599     Counter = 0;
00600     for ( i = 0; i < pMan->nBins; i++ )
00601         Abc_AigBinForEachEntrySafe( pMan->pBins[i], pEnt, pEnt2 )
00602         {
00603             Key = Abc_HashKey2( Abc_ObjChild0(pEnt), Abc_ObjChild1(pEnt), nBinsNew );
00604             pEnt->pNext   = pBinsNew[Key];
00605             pBinsNew[Key] = pEnt;
00606             Counter++;
00607         }
00608     assert( Counter == pMan->nEntries );
00609 //    printf( "Increasing the structural table size from %6d to %6d. ", pMan->nBins, nBinsNew );
00610 //    PRT( "Time", clock() - clk );
00611     // replace the table and the parameters
00612     free( pMan->pBins );
00613     pMan->pBins = pBinsNew;
00614     pMan->nBins = nBinsNew;
00615 }

void Abc_AigSetNodePhases ( Abc_Ntk_t *  pNtk  ) 

Function*************************************************************

Synopsis [Sets the correct phase of the nodes.]

Description [The AIG nodes should be in the DFS order.]

SideEffects []

SeeAlso []

Definition at line 1368 of file abcAig.c.

01369 {
01370     Abc_Obj_t * pObj;
01371     int i;
01372     assert( Abc_NtkIsDfsOrdered(pNtk) );
01373     Abc_AigConst1(pNtk)->fPhase = 1;
01374     Abc_NtkForEachPi( pNtk, pObj, i )
01375         pObj->fPhase = 0;
01376     Abc_NtkForEachLatchOutput( pNtk, pObj, i )
01377         pObj->fPhase = Abc_LatchIsInit1(pObj);
01378     Abc_AigForEachAnd( pNtk, pObj, i )
01379         pObj->fPhase = (Abc_ObjFanin0(pObj)->fPhase ^ Abc_ObjFaninC0(pObj)) & (Abc_ObjFanin1(pObj)->fPhase ^ Abc_ObjFaninC1(pObj));
01380     Abc_NtkForEachPo( pNtk, pObj, i )
01381         pObj->fPhase = (Abc_ObjFanin0(pObj)->fPhase ^ Abc_ObjFaninC0(pObj));
01382     Abc_NtkForEachLatchInput( pNtk, pObj, i )
01383         pObj->fPhase = (Abc_ObjFanin0(pObj)->fPhase ^ Abc_ObjFaninC0(pObj));
01384 }

void Abc_AigUpdateLevel_int ( Abc_Aig_t *  pMan  )  [static]

Function*************************************************************

Synopsis [Updates the level of the node after it has changed.]

Description [This procedure is based on the observation that after the node's level has changed, the fanouts levels can change too, but the new fanout levels are always larger than the node's level. As a result, we can accumulate the nodes to be updated in the queue and process them in the increasing order of levels.]

SideEffects []

SeeAlso []

Definition at line 1025 of file abcAig.c.

01026 {
01027     Abc_Obj_t * pNode, * pFanout;
01028     Vec_Ptr_t * vVec;
01029     int LevelNew, i, k, v;
01030 
01031     // go through the nodes and update the level of their fanouts
01032     Vec_VecForEachLevel( pMan->vLevels, vVec, i )
01033     {
01034         if ( Vec_PtrSize(vVec) == 0 )
01035             continue;
01036         Vec_PtrForEachEntry( vVec, pNode, k )
01037         {
01038             if ( pNode == NULL )
01039                 continue;
01040             assert( Abc_ObjIsNode(pNode) );
01041             assert( (int)pNode->Level == i );
01042             // clean the mark
01043             assert( pNode->fMarkA == 1 );
01044             pNode->fMarkA = 0;
01045             // iterate through the fanouts
01046             Abc_ObjForEachFanout( pNode, pFanout, v )
01047             {
01048                 if ( Abc_ObjIsCo(pFanout) )
01049                     continue;
01050                 // get the new level of this fanout
01051                 LevelNew = 1 + ABC_MAX( Abc_ObjFanin0(pFanout)->Level, Abc_ObjFanin1(pFanout)->Level );
01052                 assert( LevelNew > i );
01053                 if ( (int)pFanout->Level == LevelNew ) // no change
01054                     continue;
01055                 // if the fanout is present in the data structure, pull it out
01056                 if ( pFanout->fMarkA )
01057                     Abc_AigRemoveFromLevelStructure( pMan->vLevels, pFanout );
01058                 // update the fanout level
01059                 pFanout->Level = LevelNew;
01060                 // add the fanout to the data structure to update its fanouts
01061                 assert( pFanout->fMarkA == 0 );
01062                 pFanout->fMarkA = 1;
01063                 Vec_VecPush( pMan->vLevels, pFanout->Level, pFanout );
01064             }
01065         }
01066         Vec_PtrClear( vVec );
01067     }
01068 }

void Abc_AigUpdateLevelR_int ( Abc_Aig_t *  pMan  )  [static]

Function*************************************************************

Synopsis [Updates the level of the node after it has changed.]

Description []

SideEffects []

SeeAlso []

Definition at line 1081 of file abcAig.c.

01082 {
01083     Abc_Obj_t * pNode, * pFanin, * pFanout;
01084     Vec_Ptr_t * vVec;
01085     int LevelNew, i, k, v, j;
01086 
01087     // go through the nodes and update the level of their fanouts
01088     Vec_VecForEachLevel( pMan->vLevelsR, vVec, i )
01089     {
01090         if ( Vec_PtrSize(vVec) == 0 )
01091             continue;
01092         Vec_PtrForEachEntry( vVec, pNode, k )
01093         {
01094             if ( pNode == NULL )
01095                 continue;
01096             assert( Abc_ObjIsNode(pNode) );
01097             assert( Abc_ObjReverseLevel(pNode) == i );
01098             // clean the mark
01099             assert( pNode->fMarkB == 1 );
01100             pNode->fMarkB = 0;
01101             // iterate through the fanins
01102             Abc_ObjForEachFanin( pNode, pFanin, v )
01103             {
01104                 if ( Abc_ObjIsCi(pFanin) )
01105                     continue;
01106                 // get the new reverse level of this fanin
01107                 LevelNew = 0;
01108                 Abc_ObjForEachFanout( pFanin, pFanout, j )
01109                     if ( LevelNew < Abc_ObjReverseLevel(pFanout) )
01110                         LevelNew = Abc_ObjReverseLevel(pFanout);
01111                 LevelNew += 1;
01112                 assert( LevelNew > i );
01113                 if ( Abc_ObjReverseLevel(pFanin) == LevelNew ) // no change
01114                     continue;
01115                 // if the fanin is present in the data structure, pull it out
01116                 if ( pFanin->fMarkB )
01117                     Abc_AigRemoveFromLevelStructureR( pMan->vLevelsR, pFanin );
01118                 // update the reverse level
01119                 Abc_ObjSetReverseLevel( pFanin, LevelNew );
01120                 // add the fanin to the data structure to update its fanins
01121                 assert( pFanin->fMarkB == 0 );
01122                 pFanin->fMarkB = 1;
01123                 Vec_VecPush( pMan->vLevelsR, LevelNew, pFanin );
01124             }
01125         }
01126         Vec_PtrClear( vVec );
01127     }
01128 }

void Abc_AigUpdateReset ( Abc_Aig_t *  pMan  ) 

Function*************************************************************

Synopsis [Start the update list.]

Description []

SideEffects []

SeeAlso []

Definition at line 1439 of file abcAig.c.

01440 {
01441     assert( pMan->vAddedCells != NULL );
01442     Vec_PtrClear( pMan->vAddedCells );
01443     Vec_PtrClear( pMan->vUpdatedNets );
01444 }

Vec_Ptr_t* Abc_AigUpdateStart ( Abc_Aig_t *  pMan,
Vec_Ptr_t **  pvUpdatedNets 
)

Function*************************************************************

Synopsis [Start the update list.]

Description []

SideEffects []

SeeAlso []

Definition at line 1399 of file abcAig.c.

01400 {
01401     assert( pMan->vAddedCells == NULL );
01402     pMan->vAddedCells  = Vec_PtrAlloc( 1000 );
01403     pMan->vUpdatedNets = Vec_PtrAlloc( 1000 );
01404     *pvUpdatedNets = pMan->vUpdatedNets;
01405     return pMan->vAddedCells;
01406 }

void Abc_AigUpdateStop ( Abc_Aig_t *  pMan  ) 

Function*************************************************************

Synopsis [Start the update list.]

Description []

SideEffects []

SeeAlso []

Definition at line 1419 of file abcAig.c.

01420 {
01421     assert( pMan->vAddedCells != NULL );
01422     Vec_PtrFree( pMan->vAddedCells );
01423     Vec_PtrFree( pMan->vUpdatedNets );
01424     pMan->vAddedCells = NULL;
01425     pMan->vUpdatedNets = NULL;
01426 }

Abc_Obj_t* Abc_AigXor ( Abc_Aig_t *  pMan,
Abc_Obj_t *  p0,
Abc_Obj_t *  p1 
)

Function*************************************************************

Synopsis [Implements Boolean XOR.]

Description []

SideEffects []

SeeAlso []

Definition at line 735 of file abcAig.c.

00736 {
00737     return Abc_AigOr( pMan, Abc_AigAnd(pMan, p0, Abc_ObjNot(p1)), 
00738                             Abc_AigAnd(pMan, p1, Abc_ObjNot(p0)) );
00739 }

Abc_Obj_t* Abc_AigXorLookup ( Abc_Aig_t *  pMan,
Abc_Obj_t *  p0,
Abc_Obj_t *  p1,
int *  pType 
)

Function*************************************************************

Synopsis [Returns the gate implementing EXOR of the two arguments if it exists.]

Description [The argument nodes can be complemented.]

SideEffects []

SeeAlso []

Definition at line 475 of file abcAig.c.

00476 {
00477     Abc_Obj_t * pNode1, * pNode2, * pNode;
00478     // set the flag to zero
00479     if ( pType ) *pType = 0;
00480     // check the case of XOR(a,b) = OR(ab, a'b')'
00481     if ( (pNode1 = Abc_AigAndLookup(pMan, Abc_ObjNot(p0), Abc_ObjNot(p1))) &&
00482          (pNode2 = Abc_AigAndLookup(pMan, p0, p1)) ) 
00483     {
00484         pNode = Abc_AigAndLookup( pMan, Abc_ObjNot(pNode1), Abc_ObjNot(pNode2) );
00485         if ( pNode && pType ) *pType = 1;
00486         return pNode;
00487     }
00488     // check the case of XOR(a,b) = OR(a'b, ab')
00489     if ( (pNode1 = Abc_AigAndLookup(pMan, p0, Abc_ObjNot(p1))) &&
00490          (pNode2 = Abc_AigAndLookup(pMan, Abc_ObjNot(p0), p1)) ) 
00491     {
00492         pNode = Abc_AigAndLookup( pMan, Abc_ObjNot(pNode1), Abc_ObjNot(pNode2) );
00493         return pNode? Abc_ObjNot(pNode) : NULL;
00494     }
00495     return NULL;
00496 }

static unsigned Abc_HashKey2 ( Abc_Obj_t *  p0,
Abc_Obj_t *  p1,
int  TableSize 
) [static]

Definition at line 88 of file abcAig.c.

00089 {
00090     unsigned Key = 0;
00091     Key ^= Abc_ObjRegular(p0)->Id * 7937;
00092     Key ^= Abc_ObjRegular(p1)->Id * 2971;
00093     Key ^= Abc_ObjIsComplement(p0) * 911;
00094     Key ^= Abc_ObjIsComplement(p1) * 353;
00095     return Key % TableSize;
00096 }

Generated on Tue Jan 5 12:18:30 2010 for abc70930 by  doxygen 1.6.1