Version abc71001

1 files changed, 395 insertions, 0 deletions

diff --git a/src/opt/ret/retLvalue.c b/src/opt/ret/retLvalue.c
new file mode 100644
index 00000000..b4d9e946
--- /dev/null
+++ b/src/opt/ret/retLvalue.c
@@ -0,0 +1,395 @@
+/**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                                ///
+////////////////////////////////////////////////////////////////////////
+
+