From 8014f25f6db719fa62336f997963532a14c568f6 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 21 Jan 2012 04:30:10 -0800 Subject: Major restructuring of the code. --- src/opt/csw/cswCut.c | 607 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 607 insertions(+) create mode 100644 src/opt/csw/cswCut.c (limited to 'src/opt/csw/cswCut.c') 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<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 + -- cgit v1.2.3