Version abc71001

1 files changed, 485 insertions, 0 deletions

diff --git a/src/opt/res/resWin.c b/src/opt/res/resWin.c
new file mode 100644
index 00000000..a3648925
--- /dev/null
+++ b/src/opt/res/resWin.c
@@ -0,0 +1,485 @@
+/**CFile****************************************************************
+
+  FileName    [resWin.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Resynthesis package.]
+
+  Synopsis    [Windowing algorithm.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - January 15, 2007.]
+
+  Revision    [$Id: resWin.c,v 1.00 2007/01/15 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "abc.h"
+#include "resInt.h"
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Allocates the window.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Res_Win_t * Res_WinAlloc()
+{
+    Res_Win_t * p;
+    // start the manager
+    p = ALLOC( Res_Win_t, 1 );
+    memset( p, 0, sizeof(Res_Win_t) );
+    // set internal parameters
+    p->nFanoutLimit = 10;
+    p->nLevTfiMinus =  3;
+    // allocate storage
+    p->vRoots    = Vec_PtrAlloc( 256 );
+    p->vLeaves   = Vec_PtrAlloc( 256 );
+    p->vBranches = Vec_PtrAlloc( 256 );
+    p->vNodes    = Vec_PtrAlloc( 256 );
+    p->vDivs     = Vec_PtrAlloc( 256 );
+    p->vMatrix   = Vec_VecStart( 128 );
+    return p;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Frees the window.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Res_WinFree( Res_Win_t * p )
+{
+    Vec_PtrFree( p->vRoots  );
+    Vec_PtrFree( p->vLeaves );
+    Vec_PtrFree( p->vBranches );
+    Vec_PtrFree( p->vNodes  );
+    Vec_PtrFree( p->vDivs   );
+    Vec_VecFree( p->vMatrix );
+    free( p );
+}
+
+
+
+/**Function*************************************************************
+
+  Synopsis    [Collect the limited TFI cone of the node.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Res_WinCollectLeavesAndNodes( Res_Win_t * p )
+{
+    Vec_Ptr_t * vFront;
+    Abc_Obj_t * pObj, * pTemp;
+    int i, k, m;
+
+    assert( p->nWinTfiMax > 0 );
+    assert( Vec_VecSize(p->vMatrix) > p->nWinTfiMax );
+
+    // start matrix with the node
+    Vec_VecClear( p->vMatrix );
+    Vec_VecPush( p->vMatrix, 0, p->pNode );
+    Abc_NtkIncrementTravId( p->pNode->pNtk );
+    Abc_NodeSetTravIdCurrent( p->pNode );
+
+    // collect the leaves (nodes pTemp such that "p->pNode->Level - pTemp->Level > p->nWinTfiMax")
+    Vec_PtrClear( p->vLeaves );
+    Vec_VecForEachLevelStartStop( p->vMatrix, vFront, i, 0, p->nWinTfiMax )
+    {
+        Vec_PtrForEachEntry( vFront, pObj, k )
+        {
+            Abc_ObjForEachFanin( pObj, pTemp, m )
+            {
+                if ( Abc_NodeIsTravIdCurrent( pTemp ) )
+                    continue;
+                Abc_NodeSetTravIdCurrent( pTemp );
+                if ( Abc_ObjIsCi(pTemp) || (int)(p->pNode->Level - pTemp->Level) > p->nWinTfiMax )                    
+                    Vec_PtrPush( p->vLeaves, pTemp );
+                else
+                    Vec_VecPush( p->vMatrix, p->pNode->Level - pTemp->Level, pTemp );
+            }
+        }
+    }
+    if ( Vec_PtrSize(p->vLeaves) == 0 )
+        return 0;
+
+    // collect the nodes in the reverse order
+    Vec_PtrClear( p->vNodes );
+    Vec_VecForEachLevelReverseStartStop( p->vMatrix, vFront, i, p->nWinTfiMax, 0 )
+    {
+        Vec_PtrForEachEntry( vFront, pObj, k )
+            Vec_PtrPush( p->vNodes, pObj );
+        Vec_PtrClear( vFront );
+    }
+
+    // get the lowest leaf level
+    p->nLevLeafMin = ABC_INFINITY;
+    Vec_PtrForEachEntry( p->vLeaves, pObj, k )
+        p->nLevLeafMin = ABC_MIN( p->nLevLeafMin, (int)pObj->Level );
+
+    // set minimum traversal level
+    p->nLevTravMin = ABC_MAX( ((int)p->pNode->Level) - p->nWinTfiMax - p->nLevTfiMinus, p->nLevLeafMin );
+    assert( p->nLevTravMin >= 0 );
+    return 1;
+}
+
+
+
+/**Function*************************************************************
+
+  Synopsis    [Returns 1 if the node should be a root.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline int Res_WinComputeRootsCheck( Abc_Obj_t * pNode, int nLevelMax, int nFanoutLimit )
+{
+    Abc_Obj_t * pFanout;
+    int i;
+    // the node is the root if one of the following is true:
+    // (1) the node has more than fanouts than the limit
+    if ( Abc_ObjFanoutNum(pNode) > nFanoutLimit )
+        return 1;
+    // (2) the node has CO fanouts
+    // (3) the node has fanouts above the cutoff level
+    Abc_ObjForEachFanout( pNode, pFanout, i )
+        if ( Abc_ObjIsCo(pFanout) || (int)pFanout->Level > nLevelMax )
+            return 1;
+    return 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Recursively collects the root candidates.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Res_WinComputeRoots_rec( Abc_Obj_t * pNode, int nLevelMax, int nFanoutLimit, Vec_Ptr_t * vRoots )
+{
+    Abc_Obj_t * pFanout;
+    int i;
+    assert( Abc_ObjIsNode(pNode) );
+    if ( Abc_NodeIsTravIdCurrent(pNode) )
+        return;
+    Abc_NodeSetTravIdCurrent( pNode );
+    // check if the node should be the root
+    if ( Res_WinComputeRootsCheck( pNode, nLevelMax, nFanoutLimit ) )
+        Vec_PtrPush( vRoots, pNode );
+    else // if not, explore its fanouts
+        Abc_ObjForEachFanout( pNode, pFanout, i )
+            Res_WinComputeRoots_rec( pFanout, nLevelMax, nFanoutLimit, vRoots );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Recursively collects the root candidates.]
+
+  Description [Returns 1 if the only root is this node.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Res_WinComputeRoots( Res_Win_t * p )
+{
+    Vec_PtrClear( p->vRoots );
+    Abc_NtkIncrementTravId( p->pNode->pNtk );
+    Res_WinComputeRoots_rec( p->pNode, p->pNode->Level + p->nWinTfoMax, p->nFanoutLimit, p->vRoots );
+    assert( Vec_PtrSize(p->vRoots) > 0 );
+    if ( Vec_PtrSize(p->vRoots) == 1 && Vec_PtrEntry(p->vRoots, 0) == p->pNode )
+        return 0;
+    return 1;
+}
+
+
+
+/**Function*************************************************************
+
+  Synopsis    [Marks the paths from the roots to the leaves.]
+
+  Description [Returns 1 if the the node can reach a leaf.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Res_WinMarkPaths_rec( Abc_Obj_t * pNode, Abc_Obj_t * pPivot, int nLevelMin )
+{
+    Abc_Obj_t * pFanin;
+    int i, RetValue;
+    // skip visited nodes
+    if ( Abc_NodeIsTravIdCurrent(pNode) )
+        return 1;
+    if ( Abc_NodeIsTravIdPrevious(pNode) )
+        return 0;
+    // assume that the node does not have access to the leaves
+    Abc_NodeSetTravIdPrevious( pNode );
+    // skip nodes below the given level
+    if ( pNode == pPivot || (int)pNode->Level <= nLevelMin )
+        return 0;
+    assert( Abc_ObjIsNode(pNode) );
+    // check if the fanins have access to the leaves
+    RetValue = 0;
+    Abc_ObjForEachFanin( pNode, pFanin, i )
+        RetValue |= Res_WinMarkPaths_rec( pFanin, pPivot, nLevelMin );
+    // relabel the node if it has access to the leaves
+    if ( RetValue )
+        Abc_NodeSetTravIdCurrent( pNode );
+    return RetValue;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Marks the paths from the roots to the leaves.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Res_WinMarkPaths( Res_Win_t * p )
+{
+    Abc_Obj_t * pObj;
+    int i;
+    // mark the leaves
+    Abc_NtkIncrementTravId( p->pNode->pNtk );
+    Abc_NtkIncrementTravId( p->pNode->pNtk );
+    Vec_PtrForEachEntry( p->vLeaves, pObj, i )
+        Abc_NodeSetTravIdCurrent( pObj );
+    // traverse from the roots and mark the nodes that can reach leaves
+    // the nodes that do not reach leaves have previous trav ID
+    // the nodes that reach leaves have current trav ID
+    Vec_PtrForEachEntry( p->vRoots, pObj, i )
+        Res_WinMarkPaths_rec( pObj, p->pNode, p->nLevTravMin );
+}
+
+
+
+
+/**Function*************************************************************
+
+  Synopsis    [Recursively collects the roots.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Res_WinFinalizeRoots_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vRoots )
+{
+    Abc_Obj_t * pFanout;
+    int i;
+    assert( Abc_ObjIsNode(pObj) );
+    assert( Abc_NodeIsTravIdCurrent(pObj) );
+    // check if the node has all fanouts marked
+    Abc_ObjForEachFanout( pObj, pFanout, i )
+        if ( !Abc_NodeIsTravIdCurrent(pFanout) )
+            break;
+    // if some of the fanouts are unmarked, add the node to the roots
+    if ( i < Abc_ObjFanoutNum(pObj) ) 
+        Vec_PtrPushUnique( vRoots, pObj );
+    else  // otherwise, call recursively
+        Abc_ObjForEachFanout( pObj, pFanout, i )
+            Res_WinFinalizeRoots_rec( pFanout, vRoots );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Finalizes the roots of the window.]
+
+  Description [Roots of the window are the nodes that have at least
+  one fanout that it not in the TFO of the leaves.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Res_WinFinalizeRoots( Res_Win_t * p )
+{
+    assert( !Abc_NodeIsTravIdCurrent(p->pNode) );
+    // mark the node with the old traversal ID
+    Abc_NodeSetTravIdCurrent( p->pNode ); 
+    // recollect the roots
+    Vec_PtrClear( p->vRoots );
+    Res_WinFinalizeRoots_rec( p->pNode, p->vRoots );
+    assert( Vec_PtrSize(p->vRoots) > 0 );
+    if ( Vec_PtrSize(p->vRoots) == 1 && Vec_PtrEntry(p->vRoots, 0) == p->pNode )
+        return 0;
+    return 1;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Recursively adds missing nodes and leaves.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Res_WinAddMissing_rec( Res_Win_t * p, Abc_Obj_t * pObj, int nLevTravMin )
+{
+    Abc_Obj_t * pFanin;
+    int i;
+    // skip the already collected leaves, nodes, and branches
+    if ( Abc_NodeIsTravIdCurrent(pObj) )
+        return;
+    // if this is not an internal node - make it a new branch
+    if ( !Abc_NodeIsTravIdPrevious(pObj) )
+    {
+        assert( Vec_PtrFind(p->vLeaves, pObj) == -1 );
+        Abc_NodeSetTravIdCurrent( pObj );
+        Vec_PtrPush( p->vBranches, pObj );
+        return;
+    }
+    assert( Abc_ObjIsNode(pObj) ); // if this is a CI, then the window is incorrect!
+    Abc_NodeSetTravIdCurrent( pObj );
+    // visit the fanins of the node
+    Abc_ObjForEachFanin( pObj, pFanin, i )
+        Res_WinAddMissing_rec( p, pFanin, nLevTravMin );
+    // collect the node
+    Vec_PtrPush( p->vNodes, pObj );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Adds to the window nodes and leaves in the TFI of the roots.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Res_WinAddMissing( Res_Win_t * p )
+{
+    Abc_Obj_t * pObj;
+    int i;
+    // mark the leaves
+    Abc_NtkIncrementTravId( p->pNode->pNtk );
+    Vec_PtrForEachEntry( p->vLeaves, pObj, i )
+        Abc_NodeSetTravIdCurrent( pObj );        
+    // mark the already collected nodes
+    Vec_PtrForEachEntry( p->vNodes, pObj, i )
+        Abc_NodeSetTravIdCurrent( pObj );        
+    // explore from the roots
+    Vec_PtrClear( p->vBranches );
+    Vec_PtrForEachEntry( p->vRoots, pObj, i )
+        Res_WinAddMissing_rec( p, pObj, p->nLevTravMin );
+}
+
+
+
+ 
+/**Function*************************************************************
+
+  Synopsis    [Returns 1 if the window is trivial (without TFO).]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Res_WinIsTrivial( Res_Win_t * p )
+{
+    return Vec_PtrSize(p->vRoots) == 1 && Vec_PtrEntry(p->vRoots, 0) == p->pNode;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Computes the window.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Res_WinCompute( Abc_Obj_t * pNode, int nWinTfiMax, int nWinTfoMax, Res_Win_t * p )
+{
+    assert( Abc_ObjIsNode(pNode) );
+    assert( nWinTfiMax > 0 && nWinTfiMax < 10 );
+    assert( nWinTfoMax >= 0 && nWinTfoMax < 10 );
+
+    // initialize the window
+    p->pNode      = pNode;
+    p->nWinTfiMax = nWinTfiMax;
+    p->nWinTfoMax = nWinTfoMax;
+
+    Vec_PtrClear( p->vBranches );
+    Vec_PtrClear( p->vDivs );
+    Vec_PtrClear( p->vRoots );
+    Vec_PtrPush( p->vRoots, pNode );
+
+    // compute the leaves
+    if ( !Res_WinCollectLeavesAndNodes( p ) )
+        return 0;
+
+    // compute the candidate roots
+    if ( p->nWinTfoMax > 0 && Res_WinComputeRoots(p) )
+    {
+        // mark the paths from the roots to the leaves
+        Res_WinMarkPaths( p );
+        // refine the roots and add branches and missing nodes
+        if ( Res_WinFinalizeRoots( p ) )
+            Res_WinAddMissing( p );
+    }
+
+    return 1;
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+