/**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 $]
***********************************************************************/
#include "ivy.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Starts the AIG manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Ivy_Man_t * Ivy_ManStart()
{
Ivy_Man_t * p;
// start the manager
p = ABC_ALLOC( Ivy_Man_t, 1 );
memset( p, 0, sizeof(Ivy_Man_t) );
// perform initializations
p->Ghost.Id = -1;
p->nTravIds = 1;
p->fCatchExor = 1;
// allocate arrays for nodes
p->vPis = Vec_PtrAlloc( 100 );
p->vPos = Vec_PtrAlloc( 100 );
p->vBufs = Vec_PtrAlloc( 100 );
p->vObjs = Vec_PtrAlloc( 100 );
// prepare the internal memory manager
Ivy_ManStartMemory( p );
// create the constant node
p->pConst1 = Ivy_ManFetchMemory( p );
p->pConst1->fPhase = 1;
Vec_PtrPush( p->vObjs, p->pConst1 );
p->nCreated = 1;
// start the table
p->nTableSize = 10007;
p->pTable = ABC_ALLOC( int, p->nTableSize );
memset( p->pTable, 0, sizeof(int) * p->nTableSize );
return p;
}
/**Function*************************************************************
Synopsis [Duplicates the AIG manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Ivy_Man_t * Ivy_ManStartFrom( Ivy_Man_t * p )
{
Ivy_Man_t * pNew;
Ivy_Obj_t * pObj;
int i;
// create the new manager
pNew = Ivy_ManStart();
// create the PIs
Ivy_ManConst1(p)->pEquiv = Ivy_ManConst1(pNew);
Ivy_ManForEachPi( p, pObj, i )
pObj->pEquiv = Ivy_ObjCreatePi(pNew);
return pNew;
}
/**Function*************************************************************
Synopsis [Duplicates the AIG manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Ivy_Man_t * Ivy_ManDup( Ivy_Man_t * p )
{
Vec_Int_t * vNodes, * vLatches;
Ivy_Man_t * pNew;
Ivy_Obj_t * pObj;
int i;
// collect latches and nodes in the DFS order
vNodes = Ivy_ManDfsSeq( p, &vLatches );
// create the new manager
pNew = Ivy_ManStart();
// create the PIs
Ivy_ManConst1(p)->pEquiv = Ivy_ManConst1(pNew);
Ivy_ManForEachPi( p, pObj, i )
pObj->pEquiv = Ivy_ObjCreatePi(pNew);
// create the fake PIs for latches
Ivy_ManForEachNodeVec( p, vLatches, pObj, i )
pObj->pEquiv = Ivy_ObjCreatePi(pNew);
// duplicate internal nodes
Ivy_ManForEachNodeVec( p, vNodes, pObj, i )
if ( Ivy_ObjIsBuf(pObj) )
pObj->pEquiv = Ivy_ObjChild0Equiv(pObj);
else
pObj->pEquiv = Ivy_And( pNew, Ivy_ObjChild0Equiv(pObj), Ivy_ObjChild1Equiv(pObj) );
// add the POs
Ivy_ManForEachPo( p, pObj, i )
Ivy_ObjCreatePo( pNew, Ivy_ObjChild0Equiv(pObj) );
// transform additional PI nodes into latches and connect them
Ivy_ManForEachNodeVec( p, vLatches, pObj, i )
{
assert( !Ivy_ObjFaninC0(pObj) );
pObj->pEquiv->Type = IVY_LATCH;
pObj->pEquiv->Init = pObj->Init;
Ivy_ObjConnect( pNew, pObj->pEquiv, Ivy_ObjChild0Equiv(pObj), NULL );
}
// shrink the arrays
Vec_PtrShrink( pNew->vPis, Ivy_ManPiNum(p) );
// update the counters of different objects
pNew->nObjs[IVY_PI] -= Ivy_ManLatchNum(p);
pNew->nObjs[IVY_LATCH] += Ivy_ManLatchNum(p);
// free arrays
Vec_IntFree( vNodes );
Vec_IntFree( vLatches );
// make sure structural hashing did not change anything
assert( Ivy_ManNodeNum(p) == Ivy_ManNodeNum(pNew) );
assert( Ivy_ManLatchNum(p) == Ivy_ManLatchNum(pNew) );
// check the resulting network
if ( !Ivy_ManCheck(pNew) )
printf( "Ivy_ManMakeSeq(): The check has failed.\n" );
return pNew;
}
/**Function*************************************************************
Synopsis [Stops the AIG manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Ivy_Man_t * Ivy_ManFrames( Ivy_Man_t * pMan, int nLatches, int nFrames, int fInit, Vec_Ptr_t ** pvMapping )
{
Vec_Ptr_t * vMapping;
Ivy_Man_t * pNew;
Ivy_Obj_t * pObj;
int i, f, nPis, nPos, nIdMax;
assert( Ivy_ManLatchNum(pMan) == 0 );
assert( nFrames > 0 );
// prepare the mapping
nPis = Ivy_ManPiNum(pMan) - nLatches;
nPos = Ivy_ManPoNum(pMan) - nLatches;
nIdMax = Ivy_ManObjIdMax(pMan);
// create the new manager
pNew = Ivy_ManStart();
// set the starting values of latch inputs
for ( i = 0; i < nLatches; i++ )
Ivy_ManPo(pMan, nPos+i)->pEquiv = fInit? Ivy_Not(Ivy_ManConst1(pNew)) : Ivy_ObjCreatePi(pNew);
// add timeframes
vMapping = Vec_PtrStart( nIdMax * nFrames + 1 );
for ( f = 0; f < nFrames; f++ )
{
// create PIs
Ivy_ManConst1(pMan)->pEquiv = Ivy_ManConst1(pNew);
for ( i = 0; i < nPis; i++ )
Ivy_ManPi(pMan, i)->pEquiv = Ivy_ObjCreatePi(pNew);
// transfer values to latch outputs
for ( i = 0; i < nLatches; i++ )
Ivy_ManPi(pMan, nPis+i)->pEquiv = Ivy_ManPo(pMan, nPos+i)->pEquiv;
// perform strashing
Ivy_ManForEachNode( pMan, pObj, i )
pObj->pEquiv = Ivy_And( pNew, Ivy_ObjChild0Equiv(pObj), Ivy_ObjChild1Equiv(pObj) );
// create POs
for ( i = 0; i < nPos; i++ )
Ivy_ManPo(pMan, i)->pEquiv = Ivy_ObjCreatePo( pNew, Ivy_ObjChild0Equiv(Ivy_ManPo(pMan, i)) );
// set the results of latch inputs
for ( i = 0; i < nLatches; i++ )
Ivy_ManPo(pMan, nPos+i)->pEquiv = Ivy_ObjChild0Equiv(Ivy_ManPo(pMan, nPos+i));
// save the pointers in this frame
Ivy_ManForEachObj( pMan, pObj, i )
Vec_PtrWriteEntry( vMapping, f * nIdMax + i, pObj->pEquiv );
}
// connect latches
if ( !fInit )
for ( i = 0; i < nLatches; i++ )
Ivy_ObjCreatePo( pNew, Ivy_ManPo(pMan, nPos+i)->pEquiv );
// remove dangling nodes
Ivy_ManCleanup(pNew);
*pvMapping = vMapping;
// check the resulting network
if ( !Ivy_ManCheck(pNew) )
printf( "Ivy_ManFrames(): The check has failed.\n" );
return pNew;
}
/**Function*************************************************************
Synopsis [Stops the AIG manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Ivy_ManStop( Ivy_Man_t * p )
{
if ( p->time1 ) { ABC_PRT( "Update lev ", p->time1 ); }
if ( p->time2 ) { ABC_PRT( "Update levR ", p->time2 ); }
// Ivy_TableProfile( p );
// if ( p->vFanouts ) Ivy_ManStopFanout( p );
if ( p->vChunks ) Ivy_ManStopMemory( p );
if ( p->vRequired ) Vec_IntFree( p->vRequired );
if ( p->vPis ) Vec_PtrFree( p->vPis );
if ( p->vPos ) Vec_PtrFree( p->vPos );
if ( p->vBufs ) Vec_PtrFree( p->vBufs );
if ( p->vObjs ) Vec_PtrFree( p->vObjs );
ABC_FREE( p->pTable );
ABC_FREE( p );
}
/**Function*************************************************************
Synopsis [Removes nodes without fanout.]
Description [Returns the number of dangling nodes removed.]
SideEffects []
SeeAlso []
***********************************************************************/
int Ivy_ManCleanup( Ivy_Man_t * p )
{
Ivy_Obj_t * pNode;
int i, nNodesOld;
nNodesOld = Ivy_ManNodeNum(p);
Ivy_ManForEachObj( p, pNode, i )
if ( Ivy_ObjIsNode(pNode) || Ivy_ObjIsLatch(pNode) || Ivy_ObjIsBuf(pNode) )
if ( Ivy_ObjRefs(pNode) == 0 )
Ivy_ObjDelete_rec( p, pNode, 1 );
//printf( "Cleanup removed %d nodes.\n", nNodesOld - Ivy_ManNodeNum(p) );
return nNodesOld - Ivy_ManNodeNum(p);
}
/**Function*************************************************************
Synopsis [Marks nodes reachable from the given one.]
Description [Returns the number of dangling nodes removed.]
SideEffects []
SeeAlso []
***********************************************************************/
void Ivy_ManCleanupSeq_rec( Ivy_Obj_t * pObj )
{
if ( Ivy_ObjIsMarkA(pObj) )
return;
Ivy_ObjSetMarkA(pObj);
if ( pObj->pFanin0 != NULL )
Ivy_ManCleanupSeq_rec( Ivy_ObjFanin0(pObj) );
if ( pObj->pFanin1 != NULL )
Ivy_ManCleanupSeq_rec( Ivy_ObjFanin1(pObj) );
}
/**Function*************************************************************
Synopsis [Removes logic that does not feed into POs.]
Description [Returns the number of dangling nodes removed.]
SideEffects []
SeeAlso []
***********************************************************************/
int Ivy_ManCleanupSeq( Ivy_Man_t * p )
{
Vec_Ptr_t * vNodes;
Ivy_Obj_t * pObj;
int i, RetValue;
// mark the constant and PIs
Ivy_ObjSetMarkA( Ivy_ManConst1(p) );
Ivy_ManForEachPi( p, pObj, i )
Ivy_ObjSetMarkA( pObj );
// mark nodes visited from POs
Ivy_ManForEachPo( p, pObj, i )
Ivy_ManCleanupSeq_rec( pObj );
// collect unmarked nodes
vNodes = Vec_PtrAlloc( 100 );
Ivy_ManForEachObj( p, pObj, i )
{
if ( Ivy_ObjIsMarkA(pObj) )
Ivy_ObjClearMarkA(pObj);
else
Vec_PtrPush( vNodes, pObj );
}
if ( Vec_PtrSize(vNodes) == 0 )
{
Vec_PtrFree( vNodes );
//printf( "Sequential sweep cleaned out %d nodes.\n", 0 );
return 0;
}
// disconnect the marked objects
Vec_PtrForEachEntry( Ivy_Obj_t *, vNodes, pObj, i )
Ivy_ObjDisconnect( p, pObj );
// remove the dangling objects
Vec_PtrForEachEntry( Ivy_Obj_t *, vNodes, pObj, i )
{
assert( Ivy_ObjIsNode(pObj) || Ivy_ObjIsLatch(pObj) || Ivy_ObjIsBuf(pObj) );
assert( Ivy_ObjRefs(pObj) == 0 );
// update node counters of the manager
p->nObjs[pObj->Type]--;
p->nDeleted++;
// delete buffer from the array of buffers
if ( p->fFanout && Ivy_ObjIsBuf(pObj) )
Vec_PtrRemove( p->vBufs, pObj );
// free the node
Vec_PtrWriteEntry( p->vObjs, pObj->Id, NULL );
Ivy_ManRecycleMemory( p, pObj );
}
// return the number of nodes freed
RetValue = Vec_PtrSize(vNodes);
Vec_PtrFree( vNodes );
//printf( "Sequential sweep cleaned out %d nodes.\n", RetValue );
return RetValue;
}
/**Function*************************************************************
Synopsis [Checks if latches form self-loop.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Ivy_ManLatchIsSelfFeed_rec( Ivy_Obj_t * pLatch, Ivy_Obj_t * pLatchRoot )
{
if ( !Ivy_ObjIsLatch(pLatch) && !Ivy_ObjIsBuf(pLatch) )
return 0;
if ( pLatch == pLatchRoot )
return 1;
return Ivy_ManLatchIsSelfFeed_rec( Ivy_ObjFanin0(pLatch), pLatchRoot );
}
/**Function*************************************************************
Synopsis [Checks if latches form self-loop.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Ivy_ManLatchIsSelfFeed( Ivy_Obj_t * pLatch )
{
if ( !Ivy_ObjIsLatch(pLatch) )
return 0;
return Ivy_ManLatchIsSelfFeed_rec( Ivy_ObjFanin0(pLatch), pLatch );
}
/**Function*************************************************************
Synopsis [Returns the number of dangling nodes removed.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Ivy_ManPropagateBuffers( Ivy_Man_t * p, int fUpdateLevel )
{
Ivy_Obj_t * pNode;
int LimitFactor = 100;
int NodeBeg = Ivy_ManNodeNum(p);
int nSteps;
for ( nSteps = 0; Vec_PtrSize(p->vBufs) > 0; nSteps++ )
{
pNode = (Ivy_Obj_t *)Vec_PtrEntryLast(p->vBufs);
while ( Ivy_ObjIsBuf(pNode) )
pNode = Ivy_ObjReadFirstFanout( p, pNode );
// check if this buffer should remain
if ( Ivy_ManLatchIsSelfFeed(pNode) )
{
Vec_PtrPop(p->vBufs);
continue;
}
//printf( "Propagating buffer %d with input %d and output %d\n", Ivy_ObjFaninId0(pNode), Ivy_ObjFaninId0(Ivy_ObjFanin0(pNode)), pNode->Id );
//printf( "Latch num %d\n", Ivy_ManLatchNum(p) );
Ivy_NodeFixBufferFanins( p, pNode, fUpdateLevel );
if ( nSteps > NodeBeg * LimitFactor )
{
printf( "Structural hashing is not finished after %d forward latch moves.\n", NodeBeg * LimitFactor );
printf( "This circuit cannot be forward-retimed completely. Quitting.\n" );
break;
}
}
// printf( "Number of steps = %d. Nodes beg = %d. Nodes end = %d.\n", nSteps, NodeBeg, Ivy_ManNodeNum(p) );
return nSteps;
}
/**Function*************************************************************
Synopsis [Stops the AIG manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Ivy_ManPrintStats( Ivy_Man_t * p )
{
printf( "PI/PO = %d/%d ", Ivy_ManPiNum(p), Ivy_ManPoNum(p) );
printf( "A = %7d. ", Ivy_ManAndNum(p) );
printf( "L = %5d. ", Ivy_ManLatchNum(p) );
// printf( "X = %d. ", Ivy_ManExorNum(p) );
// printf( "B = %3d. ", Ivy_ManBufNum(p) );
printf( "MaxID = %7d. ", Ivy_ManObjIdMax(p) );
// printf( "Cre = %d. ", p->nCreated );
// printf( "Del = %d. ", p->nDeleted );
printf( "Lev = %3d. ", Ivy_ManLatchNum(p)? -1 : Ivy_ManLevels(p) );
printf( "\n" );
fflush( stdout );
}
/**Function*************************************************************
Synopsis [Converts a combinational AIG manager into a sequential one.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Ivy_ManMakeSeq( Ivy_Man_t * p, int nLatches, int * pInits )
{
Ivy_Obj_t * pObj, * pLatch;
Ivy_Init_t Init;
int i;
if ( nLatches == 0 )
return;
assert( nLatches < Ivy_ManPiNum(p) && nLatches < Ivy_ManPoNum(p) );
assert( Ivy_ManPiNum(p) == Vec_PtrSize(p->vPis) );
assert( Ivy_ManPoNum(p) == Vec_PtrSize(p->vPos) );
assert( Vec_PtrSize( p->vBufs ) == 0 );
// create fanouts
if ( p->fFanout == 0 )
Ivy_ManStartFanout( p );
// collect the POs to be converted into latches
for ( i = 0; i < nLatches; i++ )
{
// get the latch value
Init = pInits? (Ivy_Init_t)pInits[i] : IVY_INIT_0;
// create latch
pObj = Ivy_ManPo( p, Ivy_ManPoNum(p) - nLatches + i );
pLatch = Ivy_Latch( p, Ivy_ObjChild0(pObj), Init );
Ivy_ObjDisconnect( p, pObj );
// recycle the old PO object
Vec_PtrWriteEntry( p->vObjs, pObj->Id, NULL );
Ivy_ManRecycleMemory( p, pObj );
// convert the corresponding PI to a buffer and connect it to the latch
pObj = Ivy_ManPi( p, Ivy_ManPiNum(p) - nLatches + i );
pObj->Type = IVY_BUF;
Ivy_ObjConnect( p, pObj, pLatch, NULL );
// save the buffer
Vec_PtrPush( p->vBufs, pObj );
}
// shrink the arrays
Vec_PtrShrink( p->vPis, Ivy_ManPiNum(p) - nLatches );
Vec_PtrShrink( p->vPos, Ivy_ManPoNum(p) - nLatches );
// update the counters of different objects
p->nObjs[IVY_PI] -= nLatches;
p->nObjs[IVY_PO] -= nLatches;
p->nObjs[IVY_BUF] += nLatches;
p->nDeleted -= 2 * nLatches;
// remove dangling nodes
Ivy_ManCleanup(p);
Ivy_ManCleanupSeq(p);
/*
// check for dangling nodes
Ivy_ManForEachObj( p, pObj, i )
if ( !Ivy_ObjIsPi(pObj) && !Ivy_ObjIsPo(pObj) && !Ivy_ObjIsConst1(pObj) )
{
assert( Ivy_ObjRefs(pObj) > 0 );
assert( Ivy_ObjRefs(pObj) == Ivy_ObjFanoutNum(p, pObj) );
}
*/
// perform hashing by propagating the buffers
Ivy_ManPropagateBuffers( p, 0 );
if ( Ivy_ManBufNum(p) )
printf( "The number of remaining buffers is %d.\n", Ivy_ManBufNum(p) );
// fix the levels
Ivy_ManResetLevels( p );
// check the resulting network
if ( !Ivy_ManCheck(p) )
printf( "Ivy_ManMakeSeq(): The check has failed.\n" );
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END