Mffc-based structural decomposition of the network and bug fixes in reordering package.

2 files changed, 499 insertions, 3 deletions

diff --git a/src/base/abci/abcCascade.c b/src/base/abci/abcCascade.c
index 02858d97..7f952f14 100644
--- a/src/base/abci/abcCascade.c
+++ b/src/base/abci/abcCascade.c
@@ -126,9 +126,9 @@ DdNode * Abc_NtkBddToAdd( DdManager * dd, DdNode * bFunc, int nOuts )
     stmm_table * tTable;
     stmm_generator * gen;
     tTable = stmm_init_table( st_ptrcmp, st_ptrhash );
-    aFunc = Abc_NtkBddToAdd_rec( dd, Cudd_Regular(bFunc), nOuts, tTable, Cudd_IsComplement(bFunc) );  Cudd_Ref(aFunc);
+    aFunc = Abc_NtkBddToAdd_rec( dd, Cudd_Regular(bFunc), nOuts, tTable, Cudd_IsComplement(bFunc) );  
     stmm_foreach_item( tTable, gen, (char **)&bTemp, (char **)&aTemp )
-        Cudd_RecursiveDeref( dd, aFunc );
+        Cudd_RecursiveDeref( dd, aTemp );
     stmm_free_table( tTable );
     Cudd_Deref( aFunc );
     return aFunc;
@@ -189,10 +189,12 @@ void Abc_NtkBddDecTry( reo_man * pReo, DdManager * dd, DdNode ** pFuncs, int nOu
 //Abc_NodeShowBddOne( dd, aFunc );
     // perform reordering for BDD width
     aFuncNew = Extra_Reorder( pReo, dd, aFunc, NULL );                  Cudd_Ref( aFuncNew );
+printf( "Before = %d.  After = %d.\n", Cudd_DagSize(aFunc), Cudd_DagSize(aFuncNew) );
+//Abc_NodeShowBddOne( dd, aFuncNew );
     Cudd_RecursiveDeref( dd, aFuncNew );
     Cudd_RecursiveDeref( dd, aFunc );
     // print the result
-    reoProfileWidthPrint( pReo );
+//    reoProfileWidthPrint( pReo );
 }
 
 /**Function*************************************************************
@@ -268,6 +270,8 @@ void Abc_NtkBddDec( Abc_Ntk_t * pNtk, int fVerbose )
 
     pReo = Extra_ReorderInit( Abc_NtkCiNum(pNtk), 1000 );
     Extra_ReorderSetMinimizationType( pReo, REO_MINIMIZE_WIDTH );
+//    Extra_ReorderSetVerification( pReo, 1 );
+    Extra_ReorderSetVerbosity( pReo, 1 );
 
     Abc_NtkBddDecInt( pReo, dd, pFuncs, Abc_NtkCoNum(pNtk) );
     Extra_ReorderQuit( pReo );
diff --git a/src/base/abci/abcMffc.c b/src/base/abci/abcMffc.c
new file mode 100644
index 00000000..eb6def53
--- /dev/null
+++ b/src/base/abci/abcMffc.c
@@ -0,0 +1,492 @@
+/**CFile****************************************************************
+
+  FileName    [abcMffc.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Network and node package.]
+
+  Synopsis    [Computing multi-output maximum fanout-free cones.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - June 20, 2005.]
+
+  Revision    [$Id: abcMffc.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "abc.h"
+
+ABC_NAMESPACE_IMPL_START
+ 
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Dereferences and collects the nodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_MffcDeref_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
+{
+    Abc_Obj_t * pFanin;
+    int i;
+    if ( Abc_ObjIsCi(pNode) )
+        return;
+    Abc_ObjForEachFanin( pNode, pFanin, i )
+    {
+        assert( pFanin->vFanouts.nSize > 0 );
+        if ( --pFanin->vFanouts.nSize == 0 )
+            Abc_MffcDeref_rec( pFanin, vNodes );
+    }
+    if ( vNodes )
+        Vec_PtrPush( vNodes, pNode );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [References the nodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_MffcRef_rec( Abc_Obj_t * pNode )
+{
+    Abc_Obj_t * pFanin;
+    int i;
+    if ( Abc_ObjIsCi(pNode) )
+        return;
+    Abc_ObjForEachFanin( pNode, pFanin, i )
+    {
+        if ( pFanin->vFanouts.nSize++ == 0 )
+            Abc_MffcRef_rec( pFanin );
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Collects nodes belonging to the MFFC.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_MffcCollectNodes( Abc_Obj_t ** pNodes, int nNodes, Vec_Ptr_t * vNodes )
+{
+    int i;
+    Vec_PtrClear( vNodes );
+    for ( i = 0; i < nNodes; i++ )
+        Abc_MffcDeref_rec( pNodes[i], vNodes );
+    for ( i = 0; i < nNodes; i++ )
+        Abc_MffcRef_rec( pNodes[i] );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Collects leaves of the MFFC.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_MffcCollectLeaves( Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves )
+{
+    Abc_Obj_t * pNode, * pFanin;
+    int i, k;
+    assert( Vec_PtrSize(vNodes) > 0 );
+    pNode = (Abc_Obj_t *)Vec_PtrEntry( vNodes, 0 );
+    // label them
+    Abc_NtkIncrementTravId( pNode->pNtk );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
+        Abc_NodeSetTravIdCurrent( pNode );
+    // collect non-labeled fanins
+    Vec_PtrClear( vLeaves );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
+    Abc_ObjForEachFanin( pNode, pFanin, k )
+    {
+        if ( Abc_NodeIsTravIdCurrent(pFanin) )
+            continue;
+        Abc_NodeSetTravIdCurrent( pFanin );
+        Vec_PtrPush( vLeaves, pFanin );
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Collects internal nodes that are roots of MFFCs.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Ptr_t * Abc_NktMffcMarkRoots( Abc_Ntk_t * pNtk )
+{
+    Vec_Ptr_t * vRoots, * vNodes, * vLeaves;
+    Abc_Obj_t * pObj, * pLeaf;
+    int i, k;
+    Abc_NtkCleanMarkA( pNtk );
+    // mark the drivers of combinational outputs
+    vRoots  = Vec_PtrAlloc( 1000 );
+    Abc_NtkForEachCo( pNtk, pObj, i )
+    {
+        pObj = Abc_ObjFanin0( pObj );
+        if ( Abc_ObjIsCi(pObj) || pObj->fMarkA )
+            continue;
+        pObj->fMarkA = 1;
+        Vec_PtrPush( vRoots, pObj );
+    }
+    // explore starting from the drivers
+    vNodes  = Vec_PtrAlloc( 100 );
+    vLeaves = Vec_PtrAlloc( 100 );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        // collect internal nodes 
+        Abc_MffcCollectNodes( &pObj, 1, vNodes );
+        // collect leaves
+        Abc_MffcCollectLeaves( vNodes, vLeaves );
+        // add non-PI leaves
+        Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pLeaf, k )
+        {
+            if ( Abc_ObjIsCi(pLeaf) || pLeaf->fMarkA )
+                continue;
+            pLeaf->fMarkA = 1;
+            Vec_PtrPush( vRoots, pLeaf );
+        }
+    }
+    Vec_PtrFree( vLeaves );
+    Vec_PtrFree( vNodes );
+    Abc_NtkCleanMarkA( pNtk );
+    return vRoots;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Collect fanout reachable root nodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NktMffcCollectFanout_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vFanouts )
+{
+    Abc_Obj_t * pFanout;
+    int i;
+    if ( Abc_ObjIsCo(pObj) )
+        return;
+    if ( Abc_ObjFanoutNum(pObj) > 64 )
+        return;
+    if ( Abc_NodeIsTravIdCurrent(pObj) )
+        return;
+    Abc_NodeSetTravIdCurrent(pObj);
+    if ( pObj->fMarkA )
+    {
+        if ( pObj->vFanouts.nSize > 0 )
+            Vec_PtrPush( vFanouts, pObj );
+        return;
+    }
+    Abc_ObjForEachFanout( pObj, pFanout, i )
+        Abc_NktMffcCollectFanout_rec( pFanout, vFanouts );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Collect fanout reachable root nodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NktMffcCollectFanout( Abc_Obj_t ** pNodes, int nNodes, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vFanouts )
+{
+    Abc_Obj_t * pFanin, * pFanout;
+    int i, k;
+    // dereference nodes
+    for ( i = 0; i < nNodes; i++ )
+        Abc_MffcDeref_rec( pNodes[i], NULL );
+    // collect fanouts
+    Vec_PtrClear( vFanouts );
+    pFanin = (Abc_Obj_t *)Vec_PtrEntry( vLeaves, 0 );
+    Abc_NtkIncrementTravId( pFanin->pNtk );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, i )
+        Abc_ObjForEachFanout( pFanin, pFanout, k )
+            Abc_NktMffcCollectFanout_rec( pFanout, vFanouts );
+    // reference nodes
+    for ( i = 0; i < nNodes; i++ )
+        Abc_MffcRef_rec( pNodes[i] );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Grow one node.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Abc_Obj_t * Abc_NktMffcGrowOne( Abc_Ntk_t * pNtk, Abc_Obj_t ** ppObjs, int nObjs, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vFanouts )
+{
+    Abc_Obj_t * pFanout, * pFanoutBest = NULL;
+    double CostBest = 0.0;
+    int i, k;
+    Abc_MffcCollectNodes( ppObjs, nObjs, vNodes );
+    Abc_MffcCollectLeaves( vNodes, vLeaves );
+    // collect fanouts of all fanins
+    Abc_NktMffcCollectFanout( ppObjs, nObjs, vLeaves, vFanouts );
+    // try different fanouts
+    Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, i )
+    {
+        for ( k = 0; k < nObjs; k++ )
+            if ( pFanout == ppObjs[k] )
+                break;
+        if ( k < nObjs )
+            continue;
+        ppObjs[nObjs] = pFanout;
+        Abc_MffcCollectNodes( ppObjs, nObjs+1, vNodes );
+        Abc_MffcCollectLeaves( vNodes, vLeaves );
+        if ( pFanoutBest == NULL || CostBest < 1.0 * Vec_PtrSize(vNodes)/Vec_PtrSize(vLeaves) ) 
+        {
+            CostBest = 1.0 * Vec_PtrSize(vNodes)/Vec_PtrSize(vLeaves);
+            pFanoutBest = pFanout;
+        }
+    }
+    return pFanoutBest;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Procedure to increase MFF size by pairing nodes.]
+
+  Description [For each node in the array vRoots, find a matching node, 
+  so that the ratio of nodes inside to the leaf nodes is maximized.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Ptr_t * Abc_NktMffcGrowRoots( Abc_Ntk_t * pNtk, Vec_Ptr_t * vRoots )
+{
+    Vec_Ptr_t * vRoots1, * vNodes, * vLeaves, * vFanouts;
+    Abc_Obj_t * pObj, * pRoot2, * pNodes[2];
+    int i;
+    Abc_NtkCleanMarkA( pNtk );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+        pObj->fMarkA = 1;
+    vRoots1  = Vec_PtrAlloc( 100 );
+    vNodes   = Vec_PtrAlloc( 100 );
+    vLeaves  = Vec_PtrAlloc( 100 );
+    vFanouts = Vec_PtrAlloc( 100 );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        pNodes[0] = pObj;
+        pRoot2 = Abc_NktMffcGrowOne( pNtk, pNodes, 1, vNodes, vLeaves, vFanouts );
+        Vec_PtrPush( vRoots1, pRoot2 );
+    }
+    Vec_PtrFree( vNodes );
+    Vec_PtrFree( vLeaves );
+    Vec_PtrFree( vFanouts );
+    Abc_NtkCleanMarkA( pNtk );
+    return vRoots1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Procedure to increase MFF size by pairing nodes.]
+
+  Description [For each node in the array vRoots, find a matching node, 
+  so that the ratio of nodes inside to the leaf nodes is maximized.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Ptr_t * Abc_NktMffcGrowRootsAgain( Abc_Ntk_t * pNtk, Vec_Ptr_t * vRoots, Vec_Ptr_t * vRoots1 )
+{
+    Vec_Ptr_t * vRoots2, * vNodes, * vLeaves, * vFanouts;
+    Abc_Obj_t * pObj, * pRoot2, * ppObjs[3];
+    int i;
+    Abc_NtkCleanMarkA( pNtk );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+        pObj->fMarkA = 1;
+    vRoots2  = Vec_PtrAlloc( 100 );
+    vNodes   = Vec_PtrAlloc( 100 );
+    vLeaves  = Vec_PtrAlloc( 100 );
+    vFanouts = Vec_PtrAlloc( 100 );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        ppObjs[0] = pObj;
+        ppObjs[1] = (Abc_Obj_t *)Vec_PtrEntry( vRoots1, i );
+        if ( ppObjs[1] == NULL )
+        {
+            Vec_PtrPush( vRoots2, NULL );
+            continue;
+        }
+        pRoot2    = Abc_NktMffcGrowOne( pNtk, ppObjs, 2, vNodes, vLeaves, vFanouts );
+        Vec_PtrPush( vRoots2, pRoot2 );
+    }
+    Vec_PtrFree( vNodes );
+    Vec_PtrFree( vLeaves );
+    Vec_PtrFree( vFanouts );
+    Abc_NtkCleanMarkA( pNtk );
+    assert( Vec_PtrSize(vRoots) == Vec_PtrSize(vRoots2) );
+    return vRoots2;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Testbench.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NktMffcPrint( char * pFileName, Abc_Obj_t ** pNodes, int nNodes, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves )
+{
+    FILE * pFile;
+    Abc_Obj_t * pObj, * pFanin;
+    int i, k;
+    // convert the network
+    Abc_NtkToSop( pNodes[0]->pNtk, 0 );
+    // write the file
+    pFile = fopen( pFileName, "wb" );
+    fprintf( pFile, ".model %s_part\n", pNodes[0]->pNtk->pName );
+    fprintf( pFile, ".inputs" );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
+        fprintf( pFile, " %s", Abc_ObjName(pObj) );
+    fprintf( pFile, "\n" );
+    fprintf( pFile, ".outputs" );
+    for ( i = 0; i < nNodes; i++ )
+        fprintf( pFile, " %s", Abc_ObjName(pNodes[i]) );
+    fprintf( pFile, "\n" );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+    {
+        fprintf( pFile, ".names" );
+        Abc_ObjForEachFanin( pObj, pFanin, k )
+            fprintf( pFile, " %s", Abc_ObjName(pFanin) );
+        fprintf( pFile, " %s", Abc_ObjName(pObj) );
+        fprintf( pFile, "\n%s", (char *)pObj->pData );
+    }
+    fprintf( pFile, ".end\n" );
+    fclose( pFile );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Testbench.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NktMffcTest( Abc_Ntk_t * pNtk )
+{
+    char pFileName[1000];
+    Vec_Ptr_t * vRoots, * vRoots1, * vRoots2, * vNodes, * vLeaves;
+    Abc_Obj_t * pNodes[3], * pObj;
+    int i, nNodes = 0, nNodes2 = 0;
+    vRoots  = Abc_NktMffcMarkRoots( pNtk );
+    vRoots1 = Abc_NktMffcGrowRoots( pNtk, vRoots );
+    vRoots2 = Abc_NktMffcGrowRootsAgain( pNtk, vRoots, vRoots1 );
+    vNodes  = Vec_PtrAlloc( 100 );
+    vLeaves = Vec_PtrAlloc( 100 );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        printf( "%6d : ",      i );
+
+        Abc_MffcCollectNodes( &pObj, 1, vNodes );
+        Abc_MffcCollectLeaves( vNodes, vLeaves );
+        nNodes += Vec_PtrSize(vNodes);
+        printf( "%6d  ",      Abc_ObjId(pObj) );
+        printf( "Vol =%3d  ", Vec_PtrSize(vNodes) );
+        printf( "Cut =%3d  ", Vec_PtrSize(vLeaves) );
+        if ( Vec_PtrSize(vLeaves) < 2 )
+        {
+            printf( "\n" );
+            continue;
+        }
+
+        pNodes[0] = pObj;
+        pNodes[1] = (Abc_Obj_t *)Vec_PtrEntry( vRoots1, i );
+        pNodes[2] = (Abc_Obj_t *)Vec_PtrEntry( vRoots2, i );
+        if ( pNodes[1] == NULL || pNodes[2] == NULL )
+        {
+            printf( "\n" );
+            continue;
+        }
+        Abc_MffcCollectNodes( pNodes, 3, vNodes );
+        Abc_MffcCollectLeaves( vNodes, vLeaves );
+        nNodes2 += Vec_PtrSize(vNodes);
+        printf( "%6d  ",      Abc_ObjId(pNodes[1]) );
+        printf( "%6d  ",      Abc_ObjId(pNodes[2]) );
+        printf( "Vol =%3d  ", Vec_PtrSize(vNodes) );
+        printf( "Cut =%3d  ", Vec_PtrSize(vLeaves) );
+ 
+        printf( "%4.2f  ",    1.0 * Vec_PtrSize(vNodes)/Vec_PtrSize(vLeaves)  );
+        printf( "\n" );
+
+        // generate file
+        if ( Vec_PtrSize(vNodes) < 10 )
+            continue;
+        sprintf( pFileName, "%s_mffc%04d_%02d.blif", Abc_NtkName(pNtk), Abc_ObjId(pObj), Vec_PtrSize(vNodes) );
+        Abc_NktMffcPrint( pFileName, pNodes, 3, vNodes, vLeaves );
+    }
+    printf( "Total nodes = %d.  Root nodes = %d.  Mffc nodes = %d.  Mffc nodes2 = %d.\n", 
+        Abc_NtkNodeNum(pNtk), Vec_PtrSize(vRoots), nNodes, nNodes2 );
+    Vec_PtrFree( vNodes );
+    Vec_PtrFree( vLeaves );
+    Vec_PtrFree( vRoots );
+    Vec_PtrFree( vRoots1 );
+    Vec_PtrFree( vRoots2 );
+}
+
+
+ABC_NAMESPACE_IMPL_END
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+