src/aig/ivy/ivyMan.c File Reference

#include "ivy.h"
Include dependency graph for ivyMan.c:

Go to the source code of this file.

Functions

Ivy_Man_t * Ivy_ManStart ()
Ivy_Man_t * Ivy_ManStartFrom (Ivy_Man_t *p)
Ivy_Man_t * Ivy_ManDup (Ivy_Man_t *p)
Ivy_Man_t * Ivy_ManFrames (Ivy_Man_t *pMan, int nLatches, int nFrames, int fInit, Vec_Ptr_t **pvMapping)
void Ivy_ManStop (Ivy_Man_t *p)
int Ivy_ManCleanup (Ivy_Man_t *p)
void Ivy_ManCleanupSeq_rec (Ivy_Obj_t *pObj)
int Ivy_ManCleanupSeq (Ivy_Man_t *p)
int Ivy_ManLatchIsSelfFeed_rec (Ivy_Obj_t *pLatch, Ivy_Obj_t *pLatchRoot)
int Ivy_ManLatchIsSelfFeed (Ivy_Obj_t *pLatch)
int Ivy_ManPropagateBuffers (Ivy_Man_t *p, int fUpdateLevel)
void Ivy_ManPrintStats (Ivy_Man_t *p)
void Ivy_ManMakeSeq (Ivy_Man_t *p, int nLatches, int *pInits)

Function Documentation

int Ivy_ManCleanup ( Ivy_Man_t *  p  ) 

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

Synopsis [Removes nodes without fanout.]

Description [Returns the number of dangling nodes removed.]

SideEffects []

SeeAlso []

Definition at line 262 of file ivyMan.c.

00263 {
00264     Ivy_Obj_t * pNode;
00265     int i, nNodesOld;
00266     nNodesOld = Ivy_ManNodeNum(p);
00267     Ivy_ManForEachObj( p, pNode, i )
00268         if ( Ivy_ObjIsNode(pNode) || Ivy_ObjIsLatch(pNode) || Ivy_ObjIsBuf(pNode) )
00269             if ( Ivy_ObjRefs(pNode) == 0 )
00270                 Ivy_ObjDelete_rec( p, pNode, 1 );
00271 //printf( "Cleanup removed %d nodes.\n", nNodesOld - Ivy_ManNodeNum(p) );
00272     return nNodesOld - Ivy_ManNodeNum(p);
00273 }

int Ivy_ManCleanupSeq ( Ivy_Man_t *  p  ) 

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

Synopsis [Removes logic that does not feed into POs.]

Description [Returns the number of dangling nodes removed.]

SideEffects []

SeeAlso []

Definition at line 308 of file ivyMan.c.

00309 {
00310     Vec_Ptr_t * vNodes;
00311     Ivy_Obj_t * pObj;
00312     int i, RetValue;
00313     // mark the constant and PIs
00314     Ivy_ObjSetMarkA( Ivy_ManConst1(p) );
00315     Ivy_ManForEachPi( p, pObj, i )
00316         Ivy_ObjSetMarkA( pObj );
00317     // mark nodes visited from POs
00318     Ivy_ManForEachPo( p, pObj, i )
00319         Ivy_ManCleanupSeq_rec( pObj );
00320     // collect unmarked nodes
00321     vNodes = Vec_PtrAlloc( 100 );
00322     Ivy_ManForEachObj( p, pObj, i )
00323     {
00324         if ( Ivy_ObjIsMarkA(pObj) )
00325             Ivy_ObjClearMarkA(pObj);
00326         else
00327             Vec_PtrPush( vNodes, pObj );
00328     }
00329     if ( Vec_PtrSize(vNodes) == 0 )
00330     {
00331         Vec_PtrFree( vNodes );
00332 //printf( "Sequential sweep cleaned out %d nodes.\n", 0 );
00333         return 0;
00334     }
00335     // disconnect the marked objects
00336     Vec_PtrForEachEntry( vNodes, pObj, i )
00337         Ivy_ObjDisconnect( p, pObj );
00338     // remove the dangling objects
00339     Vec_PtrForEachEntry( vNodes, pObj, i )
00340     {
00341         assert( Ivy_ObjIsNode(pObj) || Ivy_ObjIsLatch(pObj) || Ivy_ObjIsBuf(pObj) );
00342         assert( Ivy_ObjRefs(pObj) == 0 );
00343         // update node counters of the manager
00344         p->nObjs[pObj->Type]--;
00345         p->nDeleted++;
00346         // delete buffer from the array of buffers
00347         if ( p->fFanout && Ivy_ObjIsBuf(pObj) )
00348             Vec_PtrRemove( p->vBufs, pObj );
00349         // free the node
00350         Vec_PtrWriteEntry( p->vObjs, pObj->Id, NULL );
00351         Ivy_ManRecycleMemory( p, pObj );
00352     }
00353     // return the number of nodes freed
00354     RetValue = Vec_PtrSize(vNodes);
00355     Vec_PtrFree( vNodes );
00356 //printf( "Sequential sweep cleaned out %d nodes.\n", RetValue );
00357     return RetValue;
00358 }

void Ivy_ManCleanupSeq_rec ( Ivy_Obj_t *  pObj  ) 

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

Synopsis [Marks nodes reachable from the given one.]

Description [Returns the number of dangling nodes removed.]

SideEffects []

SeeAlso []

Definition at line 286 of file ivyMan.c.

00287 {
00288     if ( Ivy_ObjIsMarkA(pObj) )
00289         return;
00290     Ivy_ObjSetMarkA(pObj);
00291     if ( pObj->pFanin0 != NULL )
00292         Ivy_ManCleanupSeq_rec( Ivy_ObjFanin0(pObj) );
00293     if ( pObj->pFanin1 != NULL )
00294         Ivy_ManCleanupSeq_rec( Ivy_ObjFanin1(pObj) );
00295 }

Ivy_Man_t* Ivy_ManDup ( Ivy_Man_t *  p  ) 

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

Synopsis [Duplicates the AIG manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 107 of file ivyMan.c.

00108 {
00109     Vec_Int_t * vNodes, * vLatches;
00110     Ivy_Man_t * pNew;
00111     Ivy_Obj_t * pObj;
00112     int i;
00113     // collect latches and nodes in the DFS order
00114     vNodes = Ivy_ManDfsSeq( p, &vLatches );
00115     // create the new manager
00116     pNew = Ivy_ManStart();
00117     // create the PIs
00118     Ivy_ManConst1(p)->pEquiv = Ivy_ManConst1(pNew);
00119     Ivy_ManForEachPi( p, pObj, i )
00120         pObj->pEquiv = Ivy_ObjCreatePi(pNew);
00121     // create the fake PIs for latches
00122     Ivy_ManForEachNodeVec( p, vLatches, pObj, i )
00123         pObj->pEquiv = Ivy_ObjCreatePi(pNew);
00124     // duplicate internal nodes
00125     Ivy_ManForEachNodeVec( p, vNodes, pObj, i )
00126         if ( Ivy_ObjIsBuf(pObj) )
00127             pObj->pEquiv = Ivy_ObjChild0Equiv(pObj);
00128         else
00129             pObj->pEquiv = Ivy_And( pNew, Ivy_ObjChild0Equiv(pObj), Ivy_ObjChild1Equiv(pObj) );
00130     // add the POs
00131     Ivy_ManForEachPo( p, pObj, i )
00132         Ivy_ObjCreatePo( pNew, Ivy_ObjChild0Equiv(pObj) );
00133     // transform additional PI nodes into latches and connect them
00134     Ivy_ManForEachNodeVec( p, vLatches, pObj, i )
00135     {
00136         assert( !Ivy_ObjFaninC0(pObj) );
00137         pObj->pEquiv->Type = IVY_LATCH;
00138         pObj->pEquiv->Init = pObj->Init;
00139         Ivy_ObjConnect( pNew, pObj->pEquiv, Ivy_ObjChild0Equiv(pObj), NULL );
00140     }
00141     // shrink the arrays
00142     Vec_PtrShrink( pNew->vPis, Ivy_ManPiNum(p) );
00143     // update the counters of different objects
00144     pNew->nObjs[IVY_PI] -= Ivy_ManLatchNum(p);
00145     pNew->nObjs[IVY_LATCH] += Ivy_ManLatchNum(p);
00146     // free arrays
00147     Vec_IntFree( vNodes );
00148     Vec_IntFree( vLatches );
00149     // make sure structural hashing did not change anything
00150     assert( Ivy_ManNodeNum(p)  == Ivy_ManNodeNum(pNew) );
00151     assert( Ivy_ManLatchNum(p) == Ivy_ManLatchNum(pNew) );
00152     // check the resulting network
00153     if ( !Ivy_ManCheck(pNew) )
00154         printf( "Ivy_ManMakeSeq(): The check has failed.\n" );
00155     return pNew;
00156 }

Ivy_Man_t* Ivy_ManFrames ( Ivy_Man_t *  pMan,
int  nLatches,
int  nFrames,
int  fInit,
Vec_Ptr_t **  pvMapping 
)

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

Synopsis [Stops the AIG manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 169 of file ivyMan.c.

00170 {
00171     Vec_Ptr_t * vMapping;
00172     Ivy_Man_t * pNew;
00173     Ivy_Obj_t * pObj;
00174     int i, f, nPis, nPos, nIdMax;
00175     assert( Ivy_ManLatchNum(pMan) == 0 );
00176     assert( nFrames > 0 );
00177     // prepare the mapping
00178     nPis = Ivy_ManPiNum(pMan) - nLatches;
00179     nPos = Ivy_ManPoNum(pMan) - nLatches;
00180     nIdMax = Ivy_ManObjIdMax(pMan);
00181     // create the new manager
00182     pNew = Ivy_ManStart();
00183     // set the starting values of latch inputs
00184     for ( i = 0; i < nLatches; i++ )
00185         Ivy_ManPo(pMan, nPos+i)->pEquiv = fInit? Ivy_Not(Ivy_ManConst1(pNew)) : Ivy_ObjCreatePi(pNew);
00186     // add timeframes
00187     vMapping = Vec_PtrStart( nIdMax * nFrames + 1 );
00188     for ( f = 0; f < nFrames; f++ )
00189     {
00190         // create PIs
00191         Ivy_ManConst1(pMan)->pEquiv = Ivy_ManConst1(pNew);
00192         for ( i = 0; i < nPis; i++ )
00193             Ivy_ManPi(pMan, i)->pEquiv = Ivy_ObjCreatePi(pNew);
00194         // transfer values to latch outputs
00195         for ( i = 0; i < nLatches; i++ )
00196             Ivy_ManPi(pMan, nPis+i)->pEquiv = Ivy_ManPo(pMan, nPos+i)->pEquiv;
00197         // perform strashing
00198         Ivy_ManForEachNode( pMan, pObj, i )
00199             pObj->pEquiv = Ivy_And( pNew, Ivy_ObjChild0Equiv(pObj), Ivy_ObjChild1Equiv(pObj) );
00200         // create POs
00201         for ( i = 0; i < nPos; i++ )
00202             Ivy_ManPo(pMan, i)->pEquiv = Ivy_ObjCreatePo( pNew, Ivy_ObjChild0Equiv(Ivy_ManPo(pMan, i)) );
00203         // set the results of latch inputs
00204         for ( i = 0; i < nLatches; i++ )
00205             Ivy_ManPo(pMan, nPos+i)->pEquiv = Ivy_ObjChild0Equiv(Ivy_ManPo(pMan, nPos+i));
00206         // save the pointers in this frame
00207         Ivy_ManForEachObj( pMan, pObj, i )
00208             Vec_PtrWriteEntry( vMapping, f * nIdMax + i, pObj->pEquiv );
00209     }
00210     // connect latches
00211     if ( !fInit )
00212         for ( i = 0; i < nLatches; i++ )
00213             Ivy_ObjCreatePo( pNew, Ivy_ManPo(pMan, nPos+i)->pEquiv );
00214     // remove dangling nodes
00215     Ivy_ManCleanup(pNew);
00216     *pvMapping = vMapping;
00217     // check the resulting network
00218     if ( !Ivy_ManCheck(pNew) )
00219         printf( "Ivy_ManFrames(): The check has failed.\n" );
00220     return pNew;
00221 }

int Ivy_ManLatchIsSelfFeed ( Ivy_Obj_t *  pLatch  ) 

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

Synopsis [Checks if latches form self-loop.]

Description []

SideEffects []

SeeAlso []

Definition at line 392 of file ivyMan.c.

00393 {
00394     if ( !Ivy_ObjIsLatch(pLatch) )
00395         return 0;
00396     return Ivy_ManLatchIsSelfFeed_rec( Ivy_ObjFanin0(pLatch), pLatch );
00397 }

int Ivy_ManLatchIsSelfFeed_rec ( Ivy_Obj_t *  pLatch,
Ivy_Obj_t *  pLatchRoot 
)

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

Synopsis [Checks if latches form self-loop.]

Description []

SideEffects []

SeeAlso []

Definition at line 372 of file ivyMan.c.

00373 {
00374     if ( !Ivy_ObjIsLatch(pLatch) && !Ivy_ObjIsBuf(pLatch) )
00375         return 0;
00376     if ( pLatch == pLatchRoot )
00377         return 1;
00378     return Ivy_ManLatchIsSelfFeed_rec( Ivy_ObjFanin0(pLatch), pLatchRoot );
00379 }

void Ivy_ManMakeSeq ( Ivy_Man_t *  p,
int  nLatches,
int *  pInits 
)

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

Synopsis [Converts a combinational AIG manager into a sequential one.]

Description []

SideEffects []

SeeAlso []

Definition at line 478 of file ivyMan.c.

00479 {
00480     Ivy_Obj_t * pObj, * pLatch;
00481     Ivy_Init_t Init;
00482     int i;
00483     if ( nLatches == 0 )
00484         return;
00485     assert( nLatches < Ivy_ManPiNum(p) && nLatches < Ivy_ManPoNum(p) );
00486     assert( Ivy_ManPiNum(p) == Vec_PtrSize(p->vPis) );
00487     assert( Ivy_ManPoNum(p) == Vec_PtrSize(p->vPos) );
00488     assert( Vec_PtrSize( p->vBufs ) == 0 );
00489     // create fanouts
00490     if ( p->fFanout == 0 )
00491         Ivy_ManStartFanout( p );
00492     // collect the POs to be converted into latches
00493     for ( i = 0; i < nLatches; i++ )
00494     {
00495         // get the latch value
00496         Init = pInits? pInits[i] : IVY_INIT_0;
00497         // create latch
00498         pObj = Ivy_ManPo( p, Ivy_ManPoNum(p) - nLatches + i );
00499         pLatch = Ivy_Latch( p, Ivy_ObjChild0(pObj), Init );
00500         Ivy_ObjDisconnect( p, pObj );
00501         // recycle the old PO object
00502         Vec_PtrWriteEntry( p->vObjs, pObj->Id, NULL );
00503         Ivy_ManRecycleMemory( p, pObj );
00504         // convert the corresponding PI to a buffer and connect it to the latch
00505         pObj = Ivy_ManPi( p, Ivy_ManPiNum(p) - nLatches + i );
00506         pObj->Type = IVY_BUF;
00507         Ivy_ObjConnect( p, pObj, pLatch, NULL );
00508         // save the buffer
00509         Vec_PtrPush( p->vBufs, pObj );
00510     }
00511     // shrink the arrays
00512     Vec_PtrShrink( p->vPis, Ivy_ManPiNum(p) - nLatches );
00513     Vec_PtrShrink( p->vPos, Ivy_ManPoNum(p) - nLatches );
00514     // update the counters of different objects
00515     p->nObjs[IVY_PI] -= nLatches;
00516     p->nObjs[IVY_PO] -= nLatches;
00517     p->nObjs[IVY_BUF] += nLatches;
00518     p->nDeleted -= 2 * nLatches;
00519     // remove dangling nodes
00520     Ivy_ManCleanup(p);
00521     Ivy_ManCleanupSeq(p);
00522 /* 
00523     // check for dangling nodes
00524     Ivy_ManForEachObj( p, pObj, i )
00525         if ( !Ivy_ObjIsPi(pObj) && !Ivy_ObjIsPo(pObj) && !Ivy_ObjIsConst1(pObj) )
00526         {
00527             assert( Ivy_ObjRefs(pObj) > 0 );
00528             assert( Ivy_ObjRefs(pObj) == Ivy_ObjFanoutNum(p, pObj) );
00529         }
00530 */
00531     // perform hashing by propagating the buffers
00532     Ivy_ManPropagateBuffers( p, 0 );
00533     if ( Ivy_ManBufNum(p) )
00534         printf( "The number of remaining buffers is %d.\n", Ivy_ManBufNum(p) );
00535     // fix the levels
00536     Ivy_ManResetLevels( p );
00537     // check the resulting network
00538     if ( !Ivy_ManCheck(p) )
00539         printf( "Ivy_ManMakeSeq(): The check has failed.\n" );
00540 }

void Ivy_ManPrintStats ( Ivy_Man_t *  p  ) 

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

Synopsis [Stops the AIG manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 453 of file ivyMan.c.

00454 {
00455     printf( "PI/PO = %d/%d ", Ivy_ManPiNum(p), Ivy_ManPoNum(p) );
00456     printf( "A = %7d. ",       Ivy_ManAndNum(p) );
00457     printf( "L = %5d. ",       Ivy_ManLatchNum(p) );
00458 //    printf( "X = %d. ",       Ivy_ManExorNum(p) );
00459 //    printf( "B = %3d. ",       Ivy_ManBufNum(p) );
00460     printf( "MaxID = %7d. ",   Ivy_ManObjIdMax(p) );
00461 //    printf( "Cre = %d. ",     p->nCreated );
00462 //    printf( "Del = %d. ",     p->nDeleted );
00463     printf( "Lev = %3d. ",     Ivy_ManLatchNum(p)? -1 : Ivy_ManLevels(p) );
00464     printf( "\n" );
00465 }

int Ivy_ManPropagateBuffers ( Ivy_Man_t *  p,
int  fUpdateLevel 
)

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

Synopsis [Returns the number of dangling nodes removed.]

Description []

SideEffects []

SeeAlso []

Definition at line 411 of file ivyMan.c.

00412 {
00413     Ivy_Obj_t * pNode;
00414     int LimitFactor = 100;
00415     int NodeBeg = Ivy_ManNodeNum(p);
00416     int nSteps;
00417     for ( nSteps = 0; Vec_PtrSize(p->vBufs) > 0; nSteps++ )
00418     {
00419         pNode = Vec_PtrEntryLast(p->vBufs);
00420         while ( Ivy_ObjIsBuf(pNode) )
00421             pNode = Ivy_ObjReadFirstFanout( p, pNode );
00422         // check if this buffer should remain
00423         if ( Ivy_ManLatchIsSelfFeed(pNode) )
00424         {
00425             Vec_PtrPop(p->vBufs);
00426             continue;
00427         }
00428 //printf( "Propagating buffer %d with input %d and output %d\n", Ivy_ObjFaninId0(pNode), Ivy_ObjFaninId0(Ivy_ObjFanin0(pNode)), pNode->Id );
00429 //printf( "Latch num %d\n", Ivy_ManLatchNum(p) );
00430         Ivy_NodeFixBufferFanins( p, pNode, fUpdateLevel );
00431         if ( nSteps > NodeBeg * LimitFactor )
00432         {
00433             printf( "Structural hashing is not finished after %d forward latch moves.\n", NodeBeg * LimitFactor );
00434             printf( "This circuit cannot be forward-retimed completely. Quitting.\n" );
00435             break;
00436         }
00437     }
00438 //    printf( "Number of steps = %d. Nodes beg = %d. Nodes end = %d.\n", nSteps, NodeBeg, Ivy_ManNodeNum(p) );
00439     return nSteps;
00440 }

Ivy_Man_t* Ivy_ManStart (  ) 

CFile****************************************************************

FileName [ivyMan.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [And-Inverter Graph package.]

Synopsis [AIG manager.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - May 11, 2006.]

Revision [

Id
ivy_.c,v 1.00 2006/05/11 00:00:00 alanmi Exp

] DECLARATIONS /// FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Starts the AIG manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 42 of file ivyMan.c.

00043 {
00044     Ivy_Man_t * p;
00045     // start the manager
00046     p = ALLOC( Ivy_Man_t, 1 );
00047     memset( p, 0, sizeof(Ivy_Man_t) );
00048     // perform initializations
00049     p->Ghost.Id   = -1;
00050     p->nTravIds   =  1;
00051     p->fCatchExor =  1;
00052     // allocate arrays for nodes
00053     p->vPis = Vec_PtrAlloc( 100 );
00054     p->vPos = Vec_PtrAlloc( 100 );
00055     p->vBufs = Vec_PtrAlloc( 100 );
00056     p->vObjs = Vec_PtrAlloc( 100 );
00057     // prepare the internal memory manager
00058     Ivy_ManStartMemory( p );
00059     // create the constant node
00060     p->pConst1 = Ivy_ManFetchMemory( p );
00061     p->pConst1->fPhase = 1;
00062     Vec_PtrPush( p->vObjs, p->pConst1 );
00063     p->nCreated = 1;
00064     // start the table
00065     p->nTableSize = 10007;
00066     p->pTable = ALLOC( int, p->nTableSize );
00067     memset( p->pTable, 0, sizeof(int) * p->nTableSize );
00068     return p;
00069 }

Ivy_Man_t* Ivy_ManStartFrom ( Ivy_Man_t *  p  ) 

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

Synopsis [Duplicates the AIG manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 82 of file ivyMan.c.

00083 {
00084     Ivy_Man_t * pNew;
00085     Ivy_Obj_t * pObj;
00086     int i;
00087     // create the new manager
00088     pNew = Ivy_ManStart();
00089     // create the PIs
00090     Ivy_ManConst1(p)->pEquiv = Ivy_ManConst1(pNew);
00091     Ivy_ManForEachPi( p, pObj, i )
00092         pObj->pEquiv = Ivy_ObjCreatePi(pNew);
00093     return pNew;
00094 }

void Ivy_ManStop ( Ivy_Man_t *  p  ) 

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

Synopsis [Stops the AIG manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 235 of file ivyMan.c.

00236 {
00237     if ( p->time1 ) { PRT( "Update lev  ", p->time1 ); }
00238     if ( p->time2 ) { PRT( "Update levR ", p->time2 ); }
00239 //    Ivy_TableProfile( p );
00240 //    if ( p->vFanouts )  Ivy_ManStopFanout( p );
00241     if ( p->vChunks )   Ivy_ManStopMemory( p );
00242     if ( p->vRequired ) Vec_IntFree( p->vRequired );
00243     if ( p->vPis )      Vec_PtrFree( p->vPis );
00244     if ( p->vPos )      Vec_PtrFree( p->vPos );
00245     if ( p->vBufs )     Vec_PtrFree( p->vBufs );
00246     if ( p->vObjs )     Vec_PtrFree( p->vObjs );
00247     free( p->pTable );
00248     free( p );
00249 }

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