Version abc70930

1 files changed, 0 insertions, 602 deletions

diff --git a/src/aig/csw/cswCut.c b/src/aig/csw/cswCut.c
deleted file mode 100644
index b3b7152b..00000000
--- a/src/aig/csw/cswCut.c
+++ /dev/null
@@ -1,602 +0,0 @@
-/**CFile****************************************************************
-
-  FileName    [cswCut.c]
-
-  SystemName  [ABC: Logic synthesis and verification system.]
-
-  PackageName [Cut sweeping.]
-
-  Synopsis    []
-
-  Author      [Alan Mishchenko]
-  
-  Affiliation [UC Berkeley]
-
-  Date        [Ver. 1.0. Started - July 11, 2007.]
-
-  Revision    [$Id: cswCut.c,v 1.00 2007/07/11 00:00:00 alanmi Exp $]
-
-***********************************************************************/
-
-#include "cswInt.h"
-
-////////////////////////////////////////////////////////////////////////
-///                        DECLARATIONS                              ///
-////////////////////////////////////////////////////////////////////////
-
-////////////////////////////////////////////////////////////////////////
-///                     FUNCTION DEFINITIONS                         ///
-////////////////////////////////////////////////////////////////////////
-
-/**Function*************************************************************
-
-  Synopsis    [Compute the cost of the cut.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-static inline int Csw_CutFindCost( Csw_Man_t * p, Csw_Cut_t * pCut )
-{
-    Aig_Obj_t * pLeaf;
-    int i, Cost = 0;
-    assert( pCut->nFanins > 0 );
-    Csw_CutForEachLeaf( p->pManRes, pCut, pLeaf, i )
-    {
-//        Cost += pLeaf->nRefs;
-        Cost += Csw_ObjRefs( p, pLeaf );
-//        printf( "%d ", pLeaf->nRefs );
-    }
-//printf( "\n" );
-    return Cost * 100 / pCut->nFanins;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Compute the cost of the cut.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-static inline float Csw_CutFindCost2( Csw_Man_t * p, Csw_Cut_t * pCut )
-{
-    Aig_Obj_t * pLeaf;
-    float Cost = 0.0;
-    int i;
-    assert( pCut->nFanins > 0 );
-    Csw_CutForEachLeaf( p->pManRes, pCut, pLeaf, i )
-        Cost += (float)1.0/pLeaf->nRefs;
-    return 1/Cost;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Returns the next free cut to use.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-static inline Csw_Cut_t * Csw_CutFindFree( Csw_Man_t * p, Aig_Obj_t * pObj )
-{
-    Csw_Cut_t * pCut, * pCutMax;
-    int i;
-    pCutMax = NULL;
-    Csw_ObjForEachCut( p, pObj, pCut, i )
-    {
-        if ( pCut->nFanins == 0 )
-            return pCut;
-        if ( pCutMax == NULL || pCutMax->Cost < pCut->Cost )
-            pCutMax = pCut;
-    }
-    assert( pCutMax != NULL );
-    pCutMax->nFanins = 0;
-    return pCutMax;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Computes the stretching phase of the cut w.r.t. the merged cut.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-static inline unsigned Cut_TruthPhase( Csw_Cut_t * pCut, Csw_Cut_t * pCut1 )
-{
-    unsigned uPhase = 0;
-    int i, k;
-    for ( i = k = 0; i < pCut->nFanins; i++ )
-    {
-        if ( k == pCut1->nFanins )
-            break;
-        if ( pCut->pFanins[i] < pCut1->pFanins[k] )
-            continue;
-        assert( pCut->pFanins[i] == pCut1->pFanins[k] );
-        uPhase |= (1 << i);
-        k++;
-    }
-    return uPhase;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Performs truth table computation.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-unsigned * Csw_CutComputeTruth( Csw_Man_t * p, Csw_Cut_t * pCut, Csw_Cut_t * pCut0, Csw_Cut_t * pCut1, int fCompl0, int fCompl1 )
-{
-    // permute the first table
-    if ( fCompl0 ) 
-        Kit_TruthNot( p->puTemp[0], Csw_CutTruth(pCut0), p->nLeafMax );
-    else
-        Kit_TruthCopy( p->puTemp[0], Csw_CutTruth(pCut0), p->nLeafMax );
-    Kit_TruthStretch( p->puTemp[2], p->puTemp[0], pCut0->nFanins, p->nLeafMax, Cut_TruthPhase(pCut, pCut0), 0 );
-    // permute the second table
-    if ( fCompl1 ) 
-        Kit_TruthNot( p->puTemp[1], Csw_CutTruth(pCut1), p->nLeafMax );
-    else
-        Kit_TruthCopy( p->puTemp[1], Csw_CutTruth(pCut1), p->nLeafMax );
-    Kit_TruthStretch( p->puTemp[3], p->puTemp[1], pCut1->nFanins, p->nLeafMax, Cut_TruthPhase(pCut, pCut1), 0 );
-    // produce the resulting table
-    Kit_TruthAnd( Csw_CutTruth(pCut), p->puTemp[2], p->puTemp[3], p->nLeafMax );
-//    assert( pCut->nFanins >= Kit_TruthSupportSize( Csw_CutTruth(pCut), p->nLeafMax ) );
-    return Csw_CutTruth(pCut);
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Performs support minimization for the truth table.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-int Csw_CutSupportMinimize( Csw_Man_t * p, Csw_Cut_t * pCut )
-{
-    unsigned * pTruth;
-    int uSupp, nFansNew, i, k;
-    // get truth table
-    pTruth = Csw_CutTruth( pCut );
-    // get support 
-    uSupp = Kit_TruthSupport( pTruth, p->nLeafMax );
-    // get the new support size
-    nFansNew = Kit_WordCountOnes( uSupp );
-    // check if there are redundant variables
-    if ( nFansNew == pCut->nFanins )
-        return nFansNew;
-    assert( nFansNew < pCut->nFanins );
-    // minimize support
-    Kit_TruthShrink( p->puTemp[0], pTruth, nFansNew, p->nLeafMax, uSupp, 1 );
-    for ( i = k = 0; i < pCut->nFanins; i++ )
-        if ( uSupp & (1 << i) )
-            pCut->pFanins[k++] = pCut->pFanins[i];
-    assert( k == nFansNew );
-    pCut->nFanins = nFansNew;
-//    assert( nFansNew == Kit_TruthSupportSize( pTruth, p->nLeafMax ) );
-//Extra_PrintBinary( stdout, pTruth, (1<<p->nLeafMax) ); printf( "\n" );
-    return nFansNew;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Returns 1 if pDom is contained in pCut.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-static inline int Csw_CutCheckDominance( Csw_Cut_t * pDom, Csw_Cut_t * pCut )
-{
-    int i, k;
-    for ( i = 0; i < (int)pDom->nFanins; i++ )
-    {
-        for ( k = 0; k < (int)pCut->nFanins; k++ )
-            if ( pDom->pFanins[i] == pCut->pFanins[k] )
-                break;
-        if ( k == (int)pCut->nFanins ) // node i in pDom is not contained in pCut
-            return 0;
-    }
-    // every node in pDom is contained in pCut
-    return 1;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Returns 1 if the cut is contained.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-int Csw_CutFilter( Csw_Man_t * p, Aig_Obj_t * pObj, Csw_Cut_t * pCut )
-{ 
-    Csw_Cut_t * pTemp;
-    int i;
-    // go through the cuts of the node
-    Csw_ObjForEachCut( p, pObj, pTemp, i )
-    {
-        if ( pTemp->nFanins < 2 )
-            continue;
-        if ( pTemp == pCut )
-            continue;
-        if ( pTemp->nFanins > pCut->nFanins )
-        {
-            // skip the non-contained cuts
-            if ( (pTemp->uSign & pCut->uSign) != pCut->uSign )
-                continue;
-            // check containment seriously
-            if ( Csw_CutCheckDominance( pCut, pTemp ) )
-            {
-                // remove contained cut
-                pTemp->nFanins = 0;
-            }
-         }
-        else
-        {
-            // skip the non-contained cuts
-            if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign )
-                continue;
-            // check containment seriously
-            if ( Csw_CutCheckDominance( pTemp, pCut ) )
-            {
-                // remove the given
-                pCut->nFanins = 0;
-                return 1;
-            }
-        }
-    }
-    return 0;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Merges two cuts.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-static inline int Csw_CutMergeOrdered( Csw_Man_t * p, Csw_Cut_t * pC0, Csw_Cut_t * pC1, Csw_Cut_t * pC )
-{ 
-    int i, k, c;
-    assert( pC0->nFanins >= pC1->nFanins );
-    // the case of the largest cut sizes
-    if ( pC0->nFanins == p->nLeafMax && pC1->nFanins == p->nLeafMax )
-    {
-        for ( i = 0; i < pC0->nFanins; i++ )
-            if ( pC0->pFanins[i] != pC1->pFanins[i] )
-                return 0;
-        for ( i = 0; i < pC0->nFanins; i++ )
-            pC->pFanins[i] = pC0->pFanins[i];
-        pC->nFanins = pC0->nFanins;
-        return 1;
-    }
-    // the case when one of the cuts is the largest
-    if ( pC0->nFanins == p->nLeafMax )
-    {
-        for ( i = 0; i < pC1->nFanins; i++ )
-        {
-            for ( k = pC0->nFanins - 1; k >= 0; k-- )
-                if ( pC0->pFanins[k] == pC1->pFanins[i] )
-                    break;
-            if ( k == -1 ) // did not find
-                return 0;
-        }
-        for ( i = 0; i < pC0->nFanins; i++ )
-            pC->pFanins[i] = pC0->pFanins[i];
-        pC->nFanins = pC0->nFanins;
-        return 1;
-    }
-
-    // compare two cuts with different numbers
-    i = k = 0;
-    for ( c = 0; c < p->nLeafMax; c++ )
-    {
-        if ( k == pC1->nFanins )
-        {
-            if ( i == pC0->nFanins )
-            {
-                pC->nFanins = c;
-                return 1;
-            }
-            pC->pFanins[c] = pC0->pFanins[i++];
-            continue;
-        }
-        if ( i == pC0->nFanins )
-        {
-            if ( k == pC1->nFanins )
-            {
-                pC->nFanins = c;
-                return 1;
-            }
-            pC->pFanins[c] = pC1->pFanins[k++];
-            continue;
-        }
-        if ( pC0->pFanins[i] < pC1->pFanins[k] )
-        {
-            pC->pFanins[c] = pC0->pFanins[i++];
-            continue;
-        }
-        if ( pC0->pFanins[i] > pC1->pFanins[k] )
-        {
-            pC->pFanins[c] = pC1->pFanins[k++];
-            continue;
-        }
-        pC->pFanins[c] = pC0->pFanins[i++]; 
-        k++;
-    }
-    if ( i < pC0->nFanins || k < pC1->nFanins )
-        return 0;
-    pC->nFanins = c;
-    return 1;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Prepares the object for FPGA mapping.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-int Csw_CutMerge( Csw_Man_t * p, Csw_Cut_t * pCut0, Csw_Cut_t * pCut1, Csw_Cut_t * pCut )
-{ 
-    assert( p->nLeafMax > 0 );
-    // merge the nodes
-    if ( pCut0->nFanins < pCut1->nFanins )
-    {
-        if ( !Csw_CutMergeOrdered( p, pCut1, pCut0, pCut ) )
-            return 0;
-    }
-    else
-    {
-        if ( !Csw_CutMergeOrdered( p, pCut0, pCut1, pCut ) )
-            return 0;
-    }
-    pCut->uSign = pCut0->uSign | pCut1->uSign;
-    return 1;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Consider cut with more than 2 fanins having 2 true variables.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-Aig_Obj_t * Csw_ObjTwoVarCut( Csw_Man_t * p, Csw_Cut_t * pCut )
-{
-    Aig_Obj_t * pRes, * pIn0, * pIn1;
-    int nVars, uTruth, fCompl = 0;
-    assert( pCut->nFanins > 2 );
-    // minimize support of this cut
-    nVars = Csw_CutSupportMinimize( p, pCut );
-    assert( nVars == 2 );
-    // get the fanins
-    pIn0 = Aig_ManObj( p->pManRes, pCut->pFanins[0] );
-    pIn1 = Aig_ManObj( p->pManRes, pCut->pFanins[1] );
-    // derive the truth table
-    uTruth = 0xF & *Csw_CutTruth(pCut);
-    if ( uTruth == 14 || uTruth == 13 || uTruth == 11 || uTruth == 7 )
-    {
-        uTruth = 0xF & ~uTruth;
-        fCompl = 1;
-    }
-    // compute the result
-    pRes = NULL;
-    if ( uTruth == 1  )  // 0001  // 1110  14
-        pRes = Aig_And( p->pManRes, Aig_Not(pIn0), Aig_Not(pIn1) );
-    if ( uTruth == 2  )  // 0010  // 1101  13 
-        pRes = Aig_And( p->pManRes,         pIn0 , Aig_Not(pIn1) );
-    if ( uTruth == 4  )  // 0100  // 1011  11
-        pRes = Aig_And( p->pManRes, Aig_Not(pIn0),         pIn1  );
-    if ( uTruth == 8  )  // 1000  // 0111   7
-        pRes = Aig_And( p->pManRes,         pIn0 ,         pIn1  );
-    if ( pRes )
-        pRes = Aig_NotCond( pRes, fCompl );
-    return pRes;
-}
-
-/**Function*************************************************************
-
-  Synopsis    []
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-Csw_Cut_t * Csw_ObjPrepareCuts( Csw_Man_t * p, Aig_Obj_t * pObj, int fTriv )
-{
-    Csw_Cut_t * pCutSet, * pCut;
-    int i;
-    // create the cutset of the node
-    pCutSet = (Csw_Cut_t *)Aig_MmFixedEntryFetch( p->pMemCuts );
-    Csw_ObjSetCuts( p, pObj, pCutSet );
-    Csw_ObjForEachCut( p, pObj, pCut, i )
-    {
-        pCut->nFanins = 0;
-        pCut->iNode = pObj->Id;
-        pCut->nCutSize = p->nCutSize;
-        pCut->nLeafMax = p->nLeafMax;
-    }
-    // add unit cut if needed
-    if ( fTriv )
-    {
-        pCut = pCutSet;
-        pCut->Cost = 0;
-        pCut->iNode = pObj->Id;
-        pCut->nFanins = 1;
-        pCut->pFanins[0] = pObj->Id;
-        pCut->uSign = Aig_ObjCutSign( pObj->Id );
-        memset( Csw_CutTruth(pCut), 0xAA, sizeof(unsigned) * p->nTruthWords );
-    }
-    return pCutSet;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Derives cuts for one node and sweeps this node.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-Aig_Obj_t * Csw_ObjSweep( Csw_Man_t * p, Aig_Obj_t * pObj, int fTriv )
-{
-    int fUseResub = 1;
-    Csw_Cut_t * pCut0, * pCut1, * pCut, * pCutSet;
-    Aig_Obj_t * pFanin0 = Aig_ObjFanin0(pObj);
-    Aig_Obj_t * pFanin1 = Aig_ObjFanin1(pObj);
-    Aig_Obj_t * pObjNew;
-    unsigned * pTruth;
-    int i, k, nVars, nFanins, iVar, clk;
-
-    assert( !Aig_IsComplement(pObj) );
-    if ( !Aig_ObjIsNode(pObj) )
-        return pObj;
-    if ( Csw_ObjCuts(p, pObj) )
-        return pObj;
-    // the node is not processed yet
-    assert( Csw_ObjCuts(p, pObj) == NULL );
-    assert( Aig_ObjIsNode(pObj) );
-
-    // set up the first cut
-    pCutSet = Csw_ObjPrepareCuts( p, pObj, fTriv );
-
-    // compute pair-wise cut combinations while checking table
-    Csw_ObjForEachCut( p, pFanin0, pCut0, i )
-    if ( pCut0->nFanins > 0 )
-    Csw_ObjForEachCut( p, pFanin1, pCut1, k )
-    if ( pCut1->nFanins > 0 )
-    {
-        // make sure K-feasible cut exists
-        if ( Kit_WordCountOnes(pCut0->uSign | pCut1->uSign) > p->nLeafMax )
-            continue;
-        // get the next cut of this node
-        pCut = Csw_CutFindFree( p, pObj );
-clk = clock();
-        // assemble the new cut
-        if ( !Csw_CutMerge( p, pCut0, pCut1, pCut ) )
-        {
-            assert( pCut->nFanins == 0 );
-            continue;
-        }
-        // check containment
-        if ( Csw_CutFilter( p, pObj, pCut ) )
-        {
-            assert( pCut->nFanins == 0 );
-            continue;
-        }
-        // create its truth table
-        pTruth = Csw_CutComputeTruth( p, pCut, pCut0, pCut1, Aig_ObjFaninC0(pObj), Aig_ObjFaninC1(pObj) );
-        // support minimize the truth table
-        nFanins = pCut->nFanins;
-//        nVars = Csw_CutSupportMinimize( p, pCut ); // leads to quality degradation
-        nVars = Kit_TruthSupportSize( pTruth, p->nLeafMax );
-p->timeCuts += clock() - clk;
-
-        // check for trivial truth tables
-        if ( nVars == 0 )
-        {
-            p->nNodesTriv0++;
-            return Aig_NotCond( Aig_ManConst1(p->pManRes), !(pTruth[0] & 1) );
-        }
-        if ( nVars == 1 )
-        {
-            p->nNodesTriv1++;
-            iVar = Kit_WordFindFirstBit( Kit_TruthSupport(pTruth, p->nLeafMax) );
-            assert( iVar < pCut->nFanins );
-            return Aig_NotCond( Aig_ManObj(p->pManRes, pCut->pFanins[iVar]), (pTruth[0] & 1) );
-        }
-        if ( nVars == 2 && nFanins > 2 && fUseResub )
-        {
-            if ( pObjNew = Csw_ObjTwoVarCut( p, pCut ) )
-            {
-                p->nNodesTriv2++;
-                return pObjNew;
-            }
-        }
-
-        // check if an equivalent node with the same cut exists
-clk = clock();
-        pObjNew = pCut->nFanins > 2 ? Csw_TableCutLookup( p, pCut ) : NULL;
-p->timeHash += clock() - clk;
-        if ( pObjNew )
-        {
-            p->nNodesCuts++;
-            return pObjNew;
-        }
-
-        // assign the cost
-        pCut->Cost = Csw_CutFindCost( p, pCut );
-        assert( pCut->nFanins > 0 );
-        assert( pCut->Cost > 0 );
-    }
-    p->nNodesTried++;
-
-    // load the resulting cuts into the table
-clk = clock();
-    Csw_ObjForEachCut( p, pObj, pCut, i )
-    {
-        if ( pCut->nFanins > 2 )
-        {
-            assert( pCut->Cost > 0 );
-            Csw_TableCutInsert( p, pCut );
-        }
-    }
-p->timeHash += clock() - clk;
-
-    // return the node if could not replace it
-    return pObj;
-}
-
-////////////////////////////////////////////////////////////////////////
-///                       END OF FILE                                ///
-////////////////////////////////////////////////////////////////////////
-
-