summaryrefslogtreecommitdiffstats
path: root/src/opt/csw/cswCut.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/opt/csw/cswCut.c')
-rw-r--r--src/opt/csw/cswCut.c607
1 files changed, 607 insertions, 0 deletions
diff --git a/src/opt/csw/cswCut.c b/src/opt/csw/cswCut.c
new file mode 100644
index 00000000..bb6677c2
--- /dev/null
+++ b/src/opt/csw/cswCut.c
@@ -0,0 +1,607 @@
+/**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"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// 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 ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-30 18:37:18 +0000