Version abc71001

1 files changed, 602 insertions, 0 deletions

diff --git a/src/aig/csw/cswCut.c b/src/aig/csw/cswCut.c
new file mode 100644
index 00000000..b3b7152b
--- /dev/null
+++ b/src/aig/csw/cswCut.c
@@ -0,0 +1,602 @@
+/**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                                ///
+////////////////////////////////////////////////////////////////////////
+
+