From 4d30a1e4f1edecff86d5066ce4653a370e59e5e1 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 30 Jan 2008 08:01:00 -0800 Subject: Version abc80130 --- src/opt/ret/retLvalue.c | 395 ------------------------------------------------ 1 file changed, 395 deletions(-) delete mode 100644 src/opt/ret/retLvalue.c (limited to 'src/opt/ret/retLvalue.c') diff --git a/src/opt/ret/retLvalue.c b/src/opt/ret/retLvalue.c deleted file mode 100644 index b4d9e946..00000000 --- a/src/opt/ret/retLvalue.c +++ /dev/null @@ -1,395 +0,0 @@ -/**CFile**************************************************************** - - FileName [retLvalue.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Retiming package.] - - Synopsis [Implementation of Pan's retiming algorithm.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - Oct 31, 2006.] - - Revision [$Id: retLvalue.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "retInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -// node status after updating its arrival time -enum { ABC_RET_UPDATE_FAIL, ABC_RET_UPDATE_NO, ABC_RET_UPDATE_YES }; - -// the internal procedures -static Vec_Int_t * Abc_NtkRetimeGetLags( Abc_Ntk_t * pNtk, int nIterLimit, int fVerbose ); -static int Abc_NtkRetimeSearch_rec( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int FiMin, int FiMax, int nMaxIters, int fVerbose ); -static int Abc_NtkRetimeForPeriod( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int Fi, int nMaxIters, int fVerbose ); -static int Abc_NtkRetimeUpdateLValue( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int Fi ); -static int Abc_NtkRetimePosOverLimit( Abc_Ntk_t * pNtk, int Fi ); -static Vec_Ptr_t * Abc_ManCollectLatches( Abc_Ntk_t * pNtk ); -static int Abc_NtkRetimeUsingLags( Abc_Ntk_t * pNtk, Vec_Int_t * vLags, int fVerbose ); - -static inline int Abc_NodeComputeLag( int LValue, int Fi ) { return (LValue + (1<<16)*Fi)/Fi - (1<<16) - (int)(LValue % Fi == 0); } -static inline int Abc_NodeGetLValue( Abc_Obj_t * pNode ) { return (int)pNode->pCopy; } -static inline void Abc_NodeSetLValue( Abc_Obj_t * pNode, int Value ) { pNode->pCopy = (void *)Value; } - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Implements Pan's retiming algorithm.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkRetimeLValue( Abc_Ntk_t * pNtk, int nIterLimit, int fVerbose ) -{ - Vec_Int_t * vLags; - int nLatches = Abc_NtkLatchNum(pNtk); - assert( Abc_NtkIsLogic( pNtk ) ); - // get the lags - vLags = Abc_NtkRetimeGetLags( pNtk, nIterLimit, fVerbose ); - // compute the retiming -// Abc_NtkRetimeUsingLags( pNtk, vLags, fVerbose ); - Vec_IntFree( vLags ); - // fix the COs -// Abc_NtkLogicMakeSimpleCos( pNtk, 0 ); - // check for correctness - if ( !Abc_NtkCheck( pNtk ) ) - fprintf( stdout, "Abc_NtkRetimeLValue(): Network check has failed.\n" ); - // return the number of latches saved - return nLatches - Abc_NtkLatchNum(pNtk); -} - -/**Function************************************************************* - - Synopsis [Computes the retiming lags.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Abc_NtkRetimeGetLags( Abc_Ntk_t * pNtk, int nIterLimit, int fVerbose ) -{ - Vec_Int_t * vLags; - Vec_Ptr_t * vNodes, * vLatches; - Abc_Obj_t * pNode; - int i, FiMax, FiBest, RetValue, clk, clkIter; - char NodeLag; - - // get the upper bound on the clock period - FiMax = Abc_NtkLevel(pNtk); - - // make sure this clock period is feasible - vNodes = Abc_NtkDfs( pNtk, 0 ); - vLatches = Abc_ManCollectLatches( pNtk ); - if ( !Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, FiMax, nIterLimit, fVerbose ) ) - { - Vec_PtrFree( vNodes ); - printf( "Abc_NtkRetimeGetLags() error: The upper bound on the clock period cannot be computed.\n" ); - return Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 ); - } - - // search for the optimal clock period between 0 and nLevelMax -clk = clock(); - FiBest = Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, 0, FiMax, nIterLimit, fVerbose ); -clkIter = clock() - clk; - - // recompute the best l-values - RetValue = Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, FiBest, nIterLimit, fVerbose ); - assert( RetValue ); - - // fix the problem with non-converged delays - Abc_NtkForEachNode( pNtk, pNode, i ) - if ( Abc_NodeGetLValue(pNode) < -ABC_INFINITY/2 ) - Abc_NodeSetLValue( pNode, 0 ); - - // write the retiming lags - vLags = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 ); - Abc_NtkForEachNode( pNtk, pNode, i ) - { - NodeLag = Abc_NodeComputeLag( Abc_NodeGetLValue(pNode), FiBest ); - Vec_IntWriteEntry( vLags, pNode->Id, NodeLag ); - } -/* - Abc_NtkForEachPo( pNtk, pNode, i ) - printf( "%d ", Abc_NodeGetLValue(Abc_ObjFanin0(pNode)) ); - printf( "\n" ); - Abc_NtkForEachLatch( pNtk, pNode, i ) - printf( "%d/%d ", Abc_NodeGetLValue(Abc_ObjFanout0(pNode)), Abc_NodeGetLValue(Abc_ObjFanout0(pNode)) + FiBest ); - printf( "\n" ); -*/ - - // print the result -// if ( fVerbose ) - printf( "The best clock period is %3d. (Currently, network is not modified.)\n", FiBest ); -/* - { - FILE * pTable; - pTable = fopen( "iscas/seqmap__stats2.txt", "a+" ); - fprintf( pTable, "%d ", FiBest ); - fprintf( pTable, "\n" ); - fclose( pTable ); - } -*/ - Vec_PtrFree( vNodes ); - Vec_PtrFree( vLatches ); - return vLags; -} - -/**Function************************************************************* - - Synopsis [Performs binary search for the optimal clock period.] - - Description [Assumes that FiMin is infeasible while FiMax is feasible.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkRetimeSearch_rec( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int FiMin, int FiMax, int nMaxIters, int fVerbose ) -{ - int Median; - assert( FiMin < FiMax ); - if ( FiMin + 1 == FiMax ) - return FiMax; - Median = FiMin + (FiMax - FiMin)/2; - if ( Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, Median, nMaxIters, fVerbose ) ) - return Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, FiMin, Median, nMaxIters, fVerbose ); // Median is feasible - else - return Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, Median, FiMax, nMaxIters, fVerbose ); // Median is infeasible -} - -/**Function************************************************************* - - Synopsis [Returns 1 if retiming with this clock period is feasible.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkRetimeForPeriod( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int Fi, int nMaxIters, int fVerbose ) -{ - Abc_Obj_t * pObj; - int c, i, fConverged; - // set l-values of all nodes to be minus infinity, except PIs and constants - Abc_NtkForEachObj( pNtk, pObj, i ) - if ( Abc_ObjFaninNum(pObj) == 0 ) - Abc_NodeSetLValue( pObj, 0 ); - else - Abc_NodeSetLValue( pObj, -ABC_INFINITY ); - // update all values iteratively - fConverged = 0; - for ( c = 1; c <= nMaxIters; c++ ) - { - if ( !Abc_NtkRetimeUpdateLValue( pNtk, vNodes, vLatches, Fi ) ) - { - fConverged = 1; - break; - } - if ( Abc_NtkRetimePosOverLimit(pNtk, Fi) ) - break; - } - // report the results - if ( fVerbose ) - { - if ( !fConverged ) - printf( "Period = %3d. Iterations = %3d. Infeasible %s\n", Fi, c, (c > nMaxIters)? "(timeout)" : "" ); - else - printf( "Period = %3d. Iterations = %3d. Feasible\n", Fi, c ); - } -/* - // check if any AND gates have infinite delay - Counter = 0; - Abc_NtkForEachNode( pNtk, pObj, i ) - Counter += (Abc_NodeGetLValue(pObj) < -ABC_INFINITY/2); - if ( Counter > 0 ) - printf( "Warning: %d internal nodes have wrong l-values!\n", Counter ); -*/ - return fConverged; -} - -/**Function************************************************************* - - Synopsis [Performs one iteration of l-value computation for the nodes.] - - Description [Experimentally it was found that checking POs changes - is not enough to detect the convergence of l-values in the network.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkRetimeUpdateLValue( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int Fi ) -{ - Abc_Obj_t * pObj, * pFanin; - int i, k, lValueNew, fChange; - // go through the nodes and detect change - fChange = 0; - Vec_PtrForEachEntry( vNodes, pObj, i ) - { - assert( Abc_ObjIsNode(pObj) ); - lValueNew = -ABC_INFINITY; - Abc_ObjForEachFanin( pObj, pFanin, k ) - { - if ( lValueNew < Abc_NodeGetLValue(pFanin) ) - lValueNew = Abc_NodeGetLValue(pFanin); - } - lValueNew++; - if ( Abc_NodeGetLValue(pObj) < lValueNew ) - { - Abc_NodeSetLValue( pObj, lValueNew ); - fChange = 1; - } - } - // propagate values through the latches - Vec_PtrForEachEntry( vLatches, pObj, i ) - Abc_NodeSetLValue( Abc_ObjFanout0(pObj), Abc_NodeGetLValue(Abc_ObjFanin0(Abc_ObjFanin0(pObj))) - Fi ); - return fChange; -} - -/**Function************************************************************* - - Synopsis [Detects the case when l-values exceeded the limit.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkRetimePosOverLimit( Abc_Ntk_t * pNtk, int Fi ) -{ - Abc_Obj_t * pObj; - int i; - Abc_NtkForEachPo( pNtk, pObj, i ) - if ( Abc_NodeGetLValue(Abc_ObjFanin0(pObj)) > Fi ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [Collects latches in the topological order.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_ManCollectLatches_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLatches ) -{ - Abc_Obj_t * pDriver; - if ( !Abc_ObjIsLatch(pObj) ) - return; - // skip already collected latches - if ( Abc_NodeIsTravIdCurrent(pObj) ) - return; - Abc_NodeSetTravIdCurrent(pObj); - // get the driver node feeding into the latch - pDriver = Abc_ObjFanin0(Abc_ObjFanin0(pObj)); - // call recursively if the driver looks like a latch output - if ( Abc_ObjIsBo(pDriver) ) - Abc_ManCollectLatches_rec( Abc_ObjFanin0(pDriver), vLatches ); - // collect the latch - Vec_PtrPush( vLatches, pObj ); -} - -/**Function************************************************************* - - Synopsis [Collects latches in the topological order.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Ptr_t * Abc_ManCollectLatches( Abc_Ntk_t * pNtk ) -{ - Vec_Ptr_t * vLatches; - Abc_Obj_t * pObj; - int i; - vLatches = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) ); - Abc_NtkIncrementTravId( pNtk ); - Abc_NtkForEachLatch( pNtk, pObj, i ) - Abc_ManCollectLatches_rec( pObj, vLatches ); - assert( Vec_PtrSize(vLatches) == Abc_NtkLatchNum(pNtk) ); - return vLatches; -} - -/**Function************************************************************* - - Synopsis [Implements the retiming given as the array of retiming lags.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkRetimeUsingLags( Abc_Ntk_t * pNtk, Vec_Int_t * vLags, int fVerbose ) -{ - Abc_Obj_t * pObj; - int fChanges, fForward, nTotalMoves, Lag, Counter, i; - // iterate over the nodes - nTotalMoves = 0; - do { - fChanges = 0; - Abc_NtkForEachNode( pNtk, pObj, i ) - { - Lag = Vec_IntEntry( vLags, pObj->Id ); - if ( !Lag ) - continue; - fForward = (Lag < 0); - if ( Abc_NtkRetimeNodeIsEnabled( pObj, fForward ) ) - { - Abc_NtkRetimeNode( pObj, fForward, 0 ); - fChanges = 1; - nTotalMoves++; - Vec_IntAddToEntry( vLags, pObj->Id, fForward? 1 : -1 ); - } - } - } while ( fChanges ); - if ( fVerbose ) - printf( "Total latch moves = %d.\n", nTotalMoves ); - // check if there are remaining lags - Counter = 0; - Abc_NtkForEachNode( pNtk, pObj, i ) - Counter += (Vec_IntEntry( vLags, pObj->Id ) != 0); - if ( Counter ) - printf( "Warning! The number of nodes with unrealized lag = %d.\n", Counter ); - return 1; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -- cgit v1.2.3