/**CFile****************************************************************
FileName [retArea.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Retiming package.]
Synopsis [Min-area retiming.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - Oct 31, 2006.]
Revision [$Id: retArea.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $]
***********************************************************************/
#include "retInt.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
static Abc_Ntk_t * Abc_NtkRetimeMinAreaOne( Abc_Ntk_t * pNtk, int fForward, int fVerbose );
static void Abc_NtkRetimeMinAreaPrepare( Abc_Ntk_t * pNtk, int fForward );
static void Abc_NtkRetimeMinAreaInitValues( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut );
static Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut );
static void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
extern Abc_Ntk_t * Abc_NtkAttachBottom( Abc_Ntk_t * pNtkTop, Abc_Ntk_t * pNtkBottom );
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Performs min-area retiming.]
Description [Returns the number of latches reduced.]
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fForwardOnly, int fBackwardOnly, int fVerbose )
{
Abc_Ntk_t * pNtkTotal = NULL, * pNtkBottom;
Vec_Int_t * vValuesNew = NULL, * vValues;
int nLatches = Abc_NtkLatchNum(pNtk);
int fOneFrame = 0;
assert( !fForwardOnly || !fBackwardOnly );
// there should not be black boxes
assert( Abc_NtkIsSopLogic(pNtk) );
assert( Abc_NtkLatchNum(pNtk) == Vec_PtrSize(pNtk->vBoxes) );
// reorder CI/CO/latch inputs
Abc_NtkOrderCisCos( pNtk );
// perform forward retiming
if ( !fBackwardOnly )
{
if ( fOneFrame )
Abc_NtkRetimeMinAreaOne( pNtk, 1, fVerbose );
else
while ( Abc_NtkRetimeMinAreaOne( pNtk, 1, fVerbose ) );
}
// remember initial values
vValues = Abc_NtkCollectLatchValues( pNtk );
// perform backward retiming
if ( !fForwardOnly )
{
if ( fOneFrame )
pNtkTotal = Abc_NtkRetimeMinAreaOne( pNtk, 0, fVerbose );
else
while ( (pNtkBottom = Abc_NtkRetimeMinAreaOne( pNtk, 0, fVerbose )) )
pNtkTotal = Abc_NtkAttachBottom( pNtkTotal, pNtkBottom );
}
// compute initial values
vValuesNew = Abc_NtkRetimeInitialValues( pNtkTotal, vValues, fVerbose );
if ( pNtkTotal ) Abc_NtkDelete( pNtkTotal );
// insert new initial values
Abc_NtkInsertLatchValues( pNtk, vValuesNew );
if ( vValuesNew ) Vec_IntFree( vValuesNew );
if ( vValues ) Vec_IntFree( vValues );
// fix the COs (this changes the circuit structure)
// Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
// check for correctness
if ( !Abc_NtkCheck( pNtk ) )
fprintf( stdout, "Abc_NtkRetimeMinArea(): Network check has failed.\n" );
// return the number of latches saved
return nLatches - Abc_NtkLatchNum(pNtk);
}
/**Function*************************************************************
Synopsis [Performs min-area retiming backward.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Abc_Ntk_t * Abc_NtkRetimeMinAreaOne( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
{
Abc_Ntk_t * pNtkNew = NULL;
Vec_Ptr_t * vMinCut;
// mark current latches and TFI(POs)
Abc_NtkRetimeMinAreaPrepare( pNtk, fForward );
// run the maximum forward flow
vMinCut = Abc_NtkMaxFlow( pNtk, fForward, fVerbose );
// assert( Vec_PtrSize(vMinCut) <= Abc_NtkLatchNum(pNtk) );
// create new latch boundary if there is improvement
if ( Vec_PtrSize(vMinCut) < Abc_NtkLatchNum(pNtk) )
{
pNtkNew = (Abc_Ntk_t *)1;
if ( fForward )
Abc_NtkRetimeMinAreaInitValues( pNtk, vMinCut );
else
pNtkNew = Abc_NtkRetimeMinAreaConstructNtk( pNtk, vMinCut );
Abc_NtkRetimeMinAreaUpdateLatches( pNtk, vMinCut, fForward );
}
// clean up
Vec_PtrFree( vMinCut );
Abc_NtkCleanMarkA( pNtk );
return pNtkNew;
}
/**Function*************************************************************
Synopsis [Marks the cone with MarkA.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkMarkCone_rec( Abc_Obj_t * pObj, int fForward )
{
Abc_Obj_t * pNext;
int i;
if ( pObj->fMarkA )
return;
pObj->fMarkA = 1;
if ( fForward )
{
Abc_ObjForEachFanout( pObj, pNext, i )
Abc_NtkMarkCone_rec( pNext, fForward );
}
else
{
Abc_ObjForEachFanin( pObj, pNext, i )
Abc_NtkMarkCone_rec( pNext, fForward );
}
}
/**Function*************************************************************
Synopsis [Marks the cone with MarkA.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkUnmarkCone_rec( Abc_Obj_t * pObj, int fForward )
{
Abc_Obj_t * pNext;
int i;
if ( !pObj->fMarkA || Abc_ObjIsLatch(pObj) )
return;
pObj->fMarkA = 0;
if ( fForward )
{
Abc_ObjForEachFanout( pObj, pNext, i )
Abc_NtkUnmarkCone_rec( pNext, fForward );
}
else
{
Abc_ObjForEachFanin( pObj, pNext, i )
Abc_NtkUnmarkCone_rec( pNext, fForward );
}
}
/**Function*************************************************************
Synopsis [Prepares the network for running MaxFlow.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkRetimeMinAreaPrepare( Abc_Ntk_t * pNtk, int fForward )
{
Vec_Ptr_t * vNodes;
Abc_Obj_t * pObj, * pFanin;
int i, k;
if ( fForward )
{
// mark the frontier
Abc_NtkForEachPo( pNtk, pObj, i )
pObj->fMarkA = 1;
Abc_NtkForEachLatch( pNtk, pObj, i )
{
pObj->fMarkA = 1;
Abc_ObjFanin0(pObj)->fMarkA = 1;
}
// mark the nodes reachable from the PIs
Abc_NtkForEachPi( pNtk, pObj, i )
Abc_NtkMarkCone_rec( pObj, fForward );
// collect the unmarked fanins of the marked nodes
vNodes = Vec_PtrAlloc( 100 );
Abc_NtkForEachObj( pNtk, pObj, i )
if ( pObj->fMarkA )
Abc_ObjForEachFanin( pObj, pFanin, k )
if ( !pFanin->fMarkA )
Vec_PtrPush( vNodes, pFanin );
// mark these nodes
Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
pObj->fMarkA = 1;
Vec_PtrFree( vNodes );
}
else
{
// mark the frontier
Abc_NtkForEachPi( pNtk, pObj, i )
pObj->fMarkA = 1;
Abc_NtkForEachLatch( pNtk, pObj, i )
{
pObj->fMarkA = 1;
Abc_ObjFanout0(pObj)->fMarkA = 1;
}
// mark the nodes reachable from the POs
Abc_NtkForEachPo( pNtk, pObj, i )
Abc_NtkMarkCone_rec( pObj, fForward );
}
}
/**Function*************************************************************
Synopsis [Compute initial values.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRetimeMinAreaInitValues_rec( Abc_Obj_t * pObj )
{
Abc_Obj_t * pFanin;
int i;
// skip visited nodes
if ( Abc_NodeIsTravIdCurrent(pObj) )
return (int)(ABC_PTRUINT_T)pObj->pCopy;
Abc_NodeSetTravIdCurrent(pObj);
// consider the case of a latch output
if ( Abc_ObjIsBo(pObj) )
{
assert( Abc_ObjIsLatch(Abc_ObjFanin0(pObj)) );
pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)Abc_NtkRetimeMinAreaInitValues_rec( Abc_ObjFanin0(pObj) );
return (int)(ABC_PTRUINT_T)pObj->pCopy;
}
assert( Abc_ObjIsNode(pObj) );
// visit the fanins
Abc_ObjForEachFanin( pObj, pFanin, i )
Abc_NtkRetimeMinAreaInitValues_rec( pFanin );
// compute the value of the node
pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)Abc_ObjSopSimulate(pObj);
return (int)(ABC_PTRUINT_T)pObj->pCopy;
}
/**Function*************************************************************
Synopsis [Compute initial values.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkRetimeMinAreaInitValues( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut )
{
Abc_Obj_t * pObj;
int i;
// transfer initial values to pCopy and mark the latches
Abc_NtkIncrementTravId(pNtk);
Abc_NtkForEachLatch( pNtk, pObj, i )
{
pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)Abc_LatchIsInit1(pObj);
Abc_NodeSetTravIdCurrent( pObj );
}
// propagate initial values
Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
Abc_NtkRetimeMinAreaInitValues_rec( pObj );
// unmark the latches
Abc_NtkForEachLatch( pNtk, pObj, i )
Abc_NodeSetTravIdPrevious( pObj );
}
/**Function*************************************************************
Synopsis [Performs min-area retiming backward.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Abc_Obj_t * Abc_NtkRetimeMinAreaConstructNtk_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pObj )
{
Abc_Obj_t * pFanin;
int i;
// skip visited nodes
if ( Abc_NodeIsTravIdCurrent(pObj) )
return pObj->pCopy;
Abc_NodeSetTravIdCurrent(pObj);
// consider the case of a latch output
if ( Abc_ObjIsBi(pObj) )
{
pObj->pCopy = Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, Abc_ObjFanin0(pObj) );
return pObj->pCopy;
}
assert( Abc_ObjIsNode(pObj) );
// visit the fanins
Abc_ObjForEachFanin( pObj, pFanin, i )
Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, pFanin );
// compute the value of the node
Abc_NtkDupObj( pNtkNew, pObj, 0 );
Abc_ObjForEachFanin( pObj, pFanin, i )
Abc_ObjAddFanin( pObj->pCopy, pFanin->pCopy );
return pObj->pCopy;
}
/**Function*************************************************************
Synopsis [Creates the network from computing initial state.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut )
{
Abc_Ntk_t * pNtkNew;
Abc_Obj_t * pObj, * pObjNew;
int i;
// create new network
pNtkNew = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_SOP, 1 );
// map new latches into PIs of the new network
Abc_NtkIncrementTravId(pNtk);
Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
{
pObj->pCopy = Abc_NtkCreatePi(pNtkNew);
Abc_NodeSetTravIdCurrent( pObj );
}
// construct the network recursively
Abc_NtkForEachLatch( pNtk, pObj, i )
{
pObjNew = Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, Abc_ObjFanin0(pObj) );
Abc_ObjAddFanin( Abc_NtkCreatePo(pNtkNew), pObjNew );
}
// unmark the nodes in the cut
Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
Abc_NodeSetTravIdPrevious( pObj );
// unmark the latches
Abc_NtkForEachLatch( pNtk, pObj, i )
Abc_NodeSetTravIdPrevious( pObj );
// assign dummy node names
Abc_NtkAddDummyPiNames( pNtkNew );
Abc_NtkAddDummyPoNames( pNtkNew );
if ( !Abc_NtkCheck( pNtkNew ) )
fprintf( stdout, "Abc_NtkRetimeMinAreaConstructNtk(): Network check has failed.\n" );
return pNtkNew;
}
/**Function*************************************************************
Synopsis [Updates the network after backward retiming.]
Description [Assumes that fMarkA denotes all nodes reachabe from
the latches toward the cut.]
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward )
{
Vec_Ptr_t * vCis, * vCos, * vBoxes, * vBoxesNew, * vNodes, * vBuffers;
Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut, * pNext, * pBuffer;
int i, k;
// create new latches
Vec_PtrShrink( pNtk->vCis, Abc_NtkCiNum(pNtk) - Abc_NtkLatchNum(pNtk) );
Vec_PtrShrink( pNtk->vCos, Abc_NtkCoNum(pNtk) - Abc_NtkLatchNum(pNtk) );
vCis = pNtk->vCis; pNtk->vCis = NULL;
vCos = pNtk->vCos; pNtk->vCos = NULL;
vBoxes = pNtk->vBoxes; pNtk->vBoxes = NULL;
// transfer boxes
vBoxesNew = Vec_PtrAlloc(100);
Vec_PtrForEachEntry( Abc_Obj_t *, vBoxes, pObj, i )
if ( !Abc_ObjIsLatch(pObj) )
Vec_PtrPush( vBoxesNew, pObj );
// create or reuse latches
vNodes = Vec_PtrAlloc( 100 );
vBuffers = Vec_PtrAlloc( 100 );
Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
{
if ( Abc_ObjIsCi(pObj) && fForward )
{
pLatchOut = pObj;
pLatch = Abc_ObjFanin0(pLatchOut);
pLatchIn = Abc_ObjFanin0(pLatch);
assert( Abc_ObjIsBo(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBi(pLatchIn) );
// mark the latch as reused
Abc_NodeSetTravIdCurrent( pLatch );
// check if there are marked fanouts
// (these are fanouts to be connected to the latch input)
Abc_ObjForEachFanout( pObj, pNext, k )
if ( pNext->fMarkA )
break;
if ( k < Abc_ObjFanoutNum(pObj) )
{
// add the buffer
pBuffer = Abc_NtkCreateNodeBuf( pNtk, Abc_ObjFanin0(pLatchIn) );
Abc_ObjPatchFanin( pLatchIn, Abc_ObjFanin0(pLatchIn), pBuffer );
Vec_PtrPush( vBuffers, pBuffer );
// redirect edges to the unvisited fanouts of the node
Abc_NodeCollectFanouts( pObj, vNodes );
Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNext, k )
if ( pNext->fMarkA )
Abc_ObjPatchFanin( pNext, pObj, pBuffer );
}
assert( Abc_ObjFanoutNum(pObj) > 0 );
// if ( Abc_ObjFanoutNum(pObj) == 0 )
// Abc_NtkDeleteObj_rec( pObj, 0 );
}
else if ( Abc_ObjIsCo(pObj) && !fForward )
{
pLatchIn = pObj;
pLatch = Abc_ObjFanout0(pLatchIn);
pLatchOut = Abc_ObjFanout0(pLatch);
assert( Abc_ObjIsBo(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBi(pLatchIn) );
// mark the latch as reused
Abc_NodeSetTravIdCurrent( pLatch );
assert( !Abc_ObjFanin0(pLatchIn)->fMarkA );
}
else
{
pLatchOut = Abc_NtkCreateBo(pNtk);
pLatch = Abc_NtkCreateLatch(pNtk);
pLatchIn = Abc_NtkCreateBi(pNtk);
Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatch), "_out" );
Abc_ObjAssignName( pLatchIn, Abc_ObjName(pLatch), "_in" );
// connect
Abc_ObjAddFanin( pLatchOut, pLatch );
Abc_ObjAddFanin( pLatch, pLatchIn );
if ( fForward )
{
pLatch->pData = (void *)(ABC_PTRUINT_T)(pObj->pCopy? ABC_INIT_ONE : ABC_INIT_ZERO);
// redirect edges to the unvisited fanouts of the node
Abc_NodeCollectFanouts( pObj, vNodes );
Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNext, k )
if ( !pNext->fMarkA )
Abc_ObjPatchFanin( pNext, pObj, pLatchOut );
}
else
{
// redirect edges to the visited fanouts of the node
Abc_NodeCollectFanouts( pObj, vNodes );
Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNext, k )
if ( pNext->fMarkA )
Abc_ObjPatchFanin( pNext, pObj, pLatchOut );
}
// connect latch to the node
Abc_ObjAddFanin( pLatchIn, pObj );
}
Vec_PtrPush( vCis, pLatchOut );
Vec_PtrPush( vBoxesNew, pLatch );
Vec_PtrPush( vCos, pLatchIn );
}
Vec_PtrFree( vNodes );
// remove buffers
Vec_PtrForEachEntry( Abc_Obj_t *, vBuffers, pObj, i )
{
Abc_ObjTransferFanout( pObj, Abc_ObjFanin0(pObj) );
Abc_NtkDeleteObj( pObj );
}
Vec_PtrFree( vBuffers );
// remove useless latches
Vec_PtrForEachEntry( Abc_Obj_t *, vBoxes, pObj, i )
{
if ( !Abc_ObjIsLatch(pObj) )
continue;
if ( Abc_NodeIsTravIdCurrent(pObj) )
continue;
pLatchOut = Abc_ObjFanout0(pObj);
pLatch = pObj;
pLatchIn = Abc_ObjFanin0(pObj);
if ( Abc_ObjFanoutNum(pLatchOut) > 0 )
Abc_ObjTransferFanout( pLatchOut, Abc_ObjFanin0(pLatchIn) );
Abc_NtkDeleteObj( pLatchOut );
Abc_NtkDeleteObj( pObj );
Abc_NtkDeleteObj( pLatchIn );
}
// set the arrays
pNtk->vCis = vCis;
pNtk->vCos = vCos;
pNtk->vBoxes = vBoxesNew;
Vec_PtrFree( vBoxes );
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END