From c5277d3334e3dbca556fbf82bbe1c0cacdc85cb1 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 12 Jul 2007 08:01:00 -0700 Subject: Version abc70712 --- src/aig/csw/csw.h | 2 +- src/aig/csw/cswCore.c | 40 +++++--- src/aig/csw/cswCut.c | 269 ++++++++++++++++++++++++++++++++++++++++++++----- src/aig/csw/cswInt.h | 62 +++++++----- src/aig/csw/cswMan.c | 47 ++++++--- src/aig/csw/cswTable.c | 55 ++++------ 6 files changed, 363 insertions(+), 112 deletions(-) (limited to 'src/aig/csw') diff --git a/src/aig/csw/csw.h b/src/aig/csw/csw.h index 4a326414..1443f4d9 100644 --- a/src/aig/csw/csw.h +++ b/src/aig/csw/csw.h @@ -51,7 +51,7 @@ extern "C" { //////////////////////////////////////////////////////////////////////// /*=== cnfCore.c ========================================================*/ -extern Dar_Man_t * Csw_Sweep( Dar_Man_t * pAig, int nCutsMax, int nLeafMax, int fVerbose ); +extern Aig_Man_t * Csw_Sweep( Aig_Man_t * pAig, int nCutsMax, int nLeafMax, int fVerbose ); #ifdef __cplusplus } diff --git a/src/aig/csw/cswCore.c b/src/aig/csw/cswCore.c index ddf37035..20893058 100644 --- a/src/aig/csw/cswCore.c +++ b/src/aig/csw/cswCore.c @@ -39,34 +39,48 @@ SeeAlso [] ***********************************************************************/ -Dar_Man_t * Csw_Sweep( Dar_Man_t * pAig, int nCutsMax, int nLeafMax, int fVerbose ) +Aig_Man_t * Csw_Sweep( Aig_Man_t * pAig, int nCutsMax, int nLeafMax, int fVerbose ) { Csw_Man_t * p; - Dar_Man_t * pRes; - Dar_Obj_t * pObj, * pObjNew, * pObjRes; - int i; + Aig_Man_t * pRes; + Aig_Obj_t * pObj, * pObjNew, * pObjRes; + int i, clk; +clk = clock(); // start the manager p = Csw_ManStart( pAig, nCutsMax, nLeafMax, fVerbose ); // set elementary cuts at the PIs - Dar_ManForEachPi( p->pManRes, pObj, i ) + Aig_ManForEachPi( p->pManRes, pObj, i ) + { Csw_ObjPrepareCuts( p, pObj, 1 ); + Csw_ObjAddRefs( p, pObj, Aig_ManPi(p->pManAig,i)->nRefs ); + } // process the nodes - Dar_ManForEachNode( pAig, pObj, i ) + Aig_ManForEachNode( pAig, pObj, i ) { // create the new node - pObjNew = Dar_And( p->pManRes, Csw_ObjChild0Equiv(p, pObj), Csw_ObjChild1Equiv(p, pObj) ); + pObjNew = Aig_And( p->pManRes, Csw_ObjChild0Equiv(p, pObj), Csw_ObjChild1Equiv(p, pObj) ); // check if this node can be represented using another node - pObjRes = Csw_ObjSweep( p, Dar_Regular(pObjNew), pObj->nRefs > 1 ); - pObjRes = Dar_NotCond( pObjRes, Dar_IsComplement(pObjNew) ); - // set the resulting node +// pObjRes = Csw_ObjSweep( p, Aig_Regular(pObjNew), pObj->nRefs > 1 ); +// pObjRes = Aig_NotCond( pObjRes, Aig_IsComplement(pObjNew) ); + // try recursively if resubsitution is used + do { + pObjRes = Csw_ObjSweep( p, Aig_Regular(pObjNew), pObj->nRefs > 1 ); + pObjRes = Aig_NotCond( pObjRes, Aig_IsComplement(pObjNew) ); + pObjNew = pObjRes; + } while ( Csw_ObjCuts(p, Aig_Regular(pObjNew)) == NULL && !Aig_ObjIsConst1(Aig_Regular(pObjNew)) ); + // save the resulting node Csw_ObjSetEquiv( p, pObj, pObjRes ); + // add to the reference counter + Csw_ObjAddRefs( p, Aig_Regular(pObjRes), pObj->nRefs ); } // add the POs - Dar_ManForEachPo( pAig, pObj, i ) - Dar_ObjCreatePo( p->pManRes, Csw_ObjChild0Equiv(p, pObj) ); + Aig_ManForEachPo( pAig, pObj, i ) + Aig_ObjCreatePo( p->pManRes, Csw_ObjChild0Equiv(p, pObj) ); // remove dangling nodes - Dar_ManCleanup( p->pManRes ); + Aig_ManCleanup( p->pManRes ); // return the resulting manager +p->timeTotal = clock() - clk; +p->timeOther = p->timeTotal - p->timeCuts - p->timeHash; pRes = p->pManRes; Csw_ManStop( p ); return pRes; diff --git a/src/aig/csw/cswCut.c b/src/aig/csw/cswCut.c index f1cb1fde..b3b7152b 100644 --- a/src/aig/csw/cswCut.c +++ b/src/aig/csw/cswCut.c @@ -41,13 +41,41 @@ ***********************************************************************/ static inline int Csw_CutFindCost( Csw_Man_t * p, Csw_Cut_t * pCut ) { - Dar_Obj_t * pObj; + Aig_Obj_t * pLeaf; int i, Cost = 0; - Csw_CutForEachLeaf( p->pManRes, pCut, pObj, i ) - Cost += pObj->nRefs; + 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.] @@ -59,7 +87,7 @@ static inline int Csw_CutFindCost( Csw_Man_t * p, Csw_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -static inline Csw_Cut_t * Csw_CutFindFree( Csw_Man_t * p, Dar_Obj_t * pObj ) +static inline Csw_Cut_t * Csw_CutFindFree( Csw_Man_t * p, Aig_Obj_t * pObj ) { Csw_Cut_t * pCut, * pCutMax; int i; @@ -131,9 +159,124 @@ unsigned * Csw_CutComputeTruth( Csw_Man_t * p, Csw_Cut_t * pCut, Csw_Cut_t * pCu 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.] @@ -249,6 +392,50 @@ int Csw_CutMerge( Csw_Man_t * p, Csw_Cut_t * pCut0, Csw_Cut_t * pCut1, Csw_Cut_t 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 [] @@ -260,17 +447,19 @@ int Csw_CutMerge( Csw_Man_t * p, Csw_Cut_t * pCut0, Csw_Cut_t * pCut1, Csw_Cut_t SeeAlso [] ***********************************************************************/ -Csw_Cut_t * Csw_ObjPrepareCuts( Csw_Man_t * p, Dar_Obj_t * pObj, int fTriv ) +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 *)Dar_MmFixedEntryFetch( p->pMemCuts ); + 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 ) @@ -280,7 +469,7 @@ Csw_Cut_t * Csw_ObjPrepareCuts( Csw_Man_t * p, Dar_Obj_t * pObj, int fTriv ) pCut->iNode = pObj->Id; pCut->nFanins = 1; pCut->pFanins[0] = pObj->Id; - pCut->uSign = Csw_ObjCutSign( pObj->Id ); + pCut->uSign = Aig_ObjCutSign( pObj->Id ); memset( Csw_CutTruth(pCut), 0xAA, sizeof(unsigned) * p->nTruthWords ); } return pCutSet; @@ -288,7 +477,7 @@ Csw_Cut_t * Csw_ObjPrepareCuts( Csw_Man_t * p, Dar_Obj_t * pObj, int fTriv ) /**Function************************************************************* - Synopsis [] + Synopsis [Derives cuts for one node and sweeps this node.] Description [] @@ -297,23 +486,24 @@ Csw_Cut_t * Csw_ObjPrepareCuts( Csw_Man_t * p, Dar_Obj_t * pObj, int fTriv ) SeeAlso [] ***********************************************************************/ -Dar_Obj_t * Csw_ObjSweep( Csw_Man_t * p, Dar_Obj_t * pObj, int fTriv ) +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; - Dar_Obj_t * pFanin0 = Dar_ObjFanin0(pObj); - Dar_Obj_t * pFanin1 = Dar_ObjFanin1(pObj); - Dar_Obj_t * pObjNew; + Aig_Obj_t * pFanin0 = Aig_ObjFanin0(pObj); + Aig_Obj_t * pFanin1 = Aig_ObjFanin1(pObj); + Aig_Obj_t * pObjNew; unsigned * pTruth; - int i, k, nVars, iVar; + int i, k, nVars, nFanins, iVar, clk; - assert( !Dar_IsComplement(pObj) ); - if ( !Dar_ObjIsNode(pObj) ) + 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( Dar_ObjIsNode(pObj) ); + assert( Aig_ObjIsNode(pObj) ); // set up the first cut pCutSet = Csw_ObjPrepareCuts( p, pObj, fTriv ); @@ -329,48 +519,77 @@ Dar_Obj_t * Csw_ObjSweep( Csw_Man_t * p, Dar_Obj_t * pObj, int fTriv ) 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, pCutSet, pCut ) ) + if ( Csw_CutFilter( p, pObj, pCut ) ) { - pCut->nFanins = 0; + assert( pCut->nFanins == 0 ); continue; } -*/ // create its truth table - pTruth = Csw_CutComputeTruth( p, pCut, pCut0, pCut1, Dar_ObjFaninC0(pObj), Dar_ObjFaninC1(pObj) ); - // check for trivial 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 ) - return Dar_NotCond( Dar_ManConst1(p->pManRes), !(pTruth[0] & 1) ); + { + 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 Dar_NotCond( Dar_ManObj(p->pManRes, pCut->pFanins[iVar]), (pTruth[0] & 1) ); + 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 - if ( pObjNew = Csw_TableCutLookup( p, pCut ) ) +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; diff --git a/src/aig/csw/cswInt.h b/src/aig/csw/cswInt.h index 74fa417b..37efe9b4 100644 --- a/src/aig/csw/cswInt.h +++ b/src/aig/csw/cswInt.h @@ -35,6 +35,7 @@ extern "C" { #include #include +#include "aig.h" #include "dar.h" #include "kit.h" #include "csw.h" @@ -55,9 +56,12 @@ struct Csw_Cut_t_ { Csw_Cut_t * pNext; // the next cut in the table int Cost; // the cost of the cut +// float Cost; // the cost of the cut unsigned uSign; // cut signature int iNode; // the node, for which it is the cut - int nFanins; // the number of words in truth table + short nCutSize; // the number of bytes in the cut + char nLeafMax; // the maximum number of fanins + char nFanins; // the current number of fanins int pFanins[0]; // the fanins (followed by the truth table) }; @@ -65,10 +69,11 @@ struct Csw_Cut_t_ struct Csw_Man_t_ { // AIG manager - Dar_Man_t * pManAig; // the input AIG manager - Dar_Man_t * pManRes; // the output AIG manager - Dar_Obj_t ** pEquiv; // the equivalent nodes in the resulting manager + Aig_Man_t * pManAig; // the input AIG manager + Aig_Man_t * pManRes; // the output AIG manager + Aig_Obj_t ** pEquiv; // the equivalent nodes in the resulting manager Csw_Cut_t ** pCuts; // the cuts for each node in the output manager + int * pnRefs; // the number of references of each new node // hash table for cuts Csw_Cut_t ** pTable; // the table composed of cuts int nTableSize; // the size of hash table @@ -79,25 +84,36 @@ struct Csw_Man_t_ // internal variables int nCutSize; // the number of bytes needed to store one cut int nTruthWords; // the number of truth table words - Dar_MmFixed_t * pMemCuts; // memory manager for cuts + Aig_MmFixed_t * pMemCuts; // memory manager for cuts unsigned * puTemp[4]; // used for the truth table computation + // statistics + int nNodesTriv0; // the number of trivial nodes + int nNodesTriv1; // the number of trivial nodes + int nNodesTriv2; // the number of trivial nodes + int nNodesCuts; // the number of rewritten nodes + int nNodesTried; // the number of nodes tried + int timeCuts; // time to compute the cut and its truth table + int timeHash; // time for hashing cuts + int timeOther; // other time + int timeTotal; // total time }; -static inline unsigned Csw_ObjCutSign( unsigned ObjId ) { return (1 << (ObjId % 31)); } +static inline int Csw_CutLeaveNum( Csw_Cut_t * pCut ) { return pCut->nFanins; } +static inline int * Csw_CutLeaves( Csw_Cut_t * pCut ) { return pCut->pFanins; } +static inline unsigned * Csw_CutTruth( Csw_Cut_t * pCut ) { return (unsigned *)(pCut->pFanins + pCut->nLeafMax); } +static inline Csw_Cut_t * Csw_CutNext( Csw_Cut_t * pCut ) { return (Csw_Cut_t *)(((char *)pCut) + pCut->nCutSize); } -static inline int Csw_CutLeaveNum( Csw_Cut_t * pCut ) { return pCut->nFanins; } -static inline int * Csw_CutLeaves( Csw_Cut_t * pCut ) { return pCut->pFanins; } -static inline unsigned * Csw_CutTruth( Csw_Cut_t * pCut ) { return (unsigned *)(pCut->pFanins + pCut->nFanins); } -static inline Csw_Cut_t * Csw_CutNext( Csw_Man_t * p, Csw_Cut_t * pCut ) { return (Csw_Cut_t *)(((char *)pCut) + p->nCutSize); } +static inline int Csw_ObjRefs( Csw_Man_t * p, Aig_Obj_t * pObj ) { return p->pnRefs[pObj->Id]; } +static inline void Csw_ObjAddRefs( Csw_Man_t * p, Aig_Obj_t * pObj, int nRefs ) { p->pnRefs[pObj->Id] += nRefs; } -static inline Csw_Cut_t * Csw_ObjCuts( Csw_Man_t * p, Dar_Obj_t * pObj ) { return p->pCuts[pObj->Id]; } -static inline void Csw_ObjSetCuts( Csw_Man_t * p, Dar_Obj_t * pObj, Csw_Cut_t * pCuts ) { p->pCuts[pObj->Id] = pCuts; } +static inline Csw_Cut_t * Csw_ObjCuts( Csw_Man_t * p, Aig_Obj_t * pObj ) { return p->pCuts[pObj->Id]; } +static inline void Csw_ObjSetCuts( Csw_Man_t * p, Aig_Obj_t * pObj, Csw_Cut_t * pCuts ) { p->pCuts[pObj->Id] = pCuts; } -static inline Dar_Obj_t * Csw_ObjEquiv( Csw_Man_t * p, Dar_Obj_t * pObj ) { return p->pEquiv[pObj->Id]; } -static inline void Csw_ObjSetEquiv( Csw_Man_t * p, Dar_Obj_t * pObj, Dar_Obj_t * pEquiv ) { p->pEquiv[pObj->Id] = pEquiv; } +static inline Aig_Obj_t * Csw_ObjEquiv( Csw_Man_t * p, Aig_Obj_t * pObj ) { return p->pEquiv[pObj->Id]; } +static inline void Csw_ObjSetEquiv( Csw_Man_t * p, Aig_Obj_t * pObj, Aig_Obj_t * pEquiv ) { p->pEquiv[pObj->Id] = pEquiv; } -static inline Dar_Obj_t * Csw_ObjChild0Equiv( Csw_Man_t * p, Dar_Obj_t * pObj ) { assert( !Dar_IsComplement(pObj) ); return Dar_ObjFanin0(pObj)? Dar_NotCond(Csw_ObjEquiv(p, Dar_ObjFanin0(pObj)), Dar_ObjFaninC0(pObj)) : NULL; } -static inline Dar_Obj_t * Csw_ObjChild1Equiv( Csw_Man_t * p, Dar_Obj_t * pObj ) { assert( !Dar_IsComplement(pObj) ); return Dar_ObjFanin1(pObj)? Dar_NotCond(Csw_ObjEquiv(p, Dar_ObjFanin1(pObj)), Dar_ObjFaninC1(pObj)) : NULL; } +static inline Aig_Obj_t * Csw_ObjChild0Equiv( Csw_Man_t * p, Aig_Obj_t * pObj ) { assert( !Aig_IsComplement(pObj) ); return Aig_ObjFanin0(pObj)? Aig_NotCond(Csw_ObjEquiv(p, Aig_ObjFanin0(pObj)), Aig_ObjFaninC0(pObj)) : NULL; } +static inline Aig_Obj_t * Csw_ObjChild1Equiv( Csw_Man_t * p, Aig_Obj_t * pObj ) { assert( !Aig_IsComplement(pObj) ); return Aig_ObjFanin1(pObj)? Aig_NotCond(Csw_ObjEquiv(p, Aig_ObjFanin1(pObj)), Aig_ObjFaninC1(pObj)) : NULL; } //////////////////////////////////////////////////////////////////////// /// MACRO DEFINITIONS /// @@ -109,25 +125,25 @@ static inline Dar_Obj_t * Csw_ObjChild1Equiv( Csw_Man_t * p, Dar_Obj_t * pObj ) // iterator over cuts of the node #define Csw_ObjForEachCut( p, pObj, pCut, i ) \ - for ( i = 0, pCut = Csw_ObjCuts(p, pObj); i < p->nCutsMax; i++, pCut = Csw_CutNext(p, pCut) ) + for ( i = 0, pCut = Csw_ObjCuts(p, pObj); i < p->nCutsMax; i++, pCut = Csw_CutNext(pCut) ) // iterator over leaves of the cut #define Csw_CutForEachLeaf( p, pCut, pLeaf, i ) \ - for ( i = 0; (i < (int)(pCut)->nFanins) && ((pLeaf) = Dar_ManObj(p, (pCut)->pFanins[i])); i++ ) + for ( i = 0; (i < (int)(pCut)->nFanins) && ((pLeaf) = Aig_ManObj(p, (pCut)->pFanins[i])); i++ ) //////////////////////////////////////////////////////////////////////// /// FUNCTION DECLARATIONS /// //////////////////////////////////////////////////////////////////////// /*=== cnfCut.c ========================================================*/ -extern Csw_Cut_t * Csw_ObjPrepareCuts( Csw_Man_t * p, Dar_Obj_t * pObj, int fTriv ); -extern Dar_Obj_t * Csw_ObjSweep( Csw_Man_t * p, Dar_Obj_t * pObj, int fTriv ); +extern Csw_Cut_t * Csw_ObjPrepareCuts( Csw_Man_t * p, Aig_Obj_t * pObj, int fTriv ); +extern Aig_Obj_t * Csw_ObjSweep( Csw_Man_t * p, Aig_Obj_t * pObj, int fTriv ); /*=== cnfMan.c ========================================================*/ -extern Csw_Man_t * Csw_ManStart( Dar_Man_t * pMan, int nCutsMax, int nLeafMax, int fVerbose ); +extern Csw_Man_t * Csw_ManStart( Aig_Man_t * pMan, int nCutsMax, int nLeafMax, int fVerbose ); extern void Csw_ManStop( Csw_Man_t * p ); /*=== cnfTable.c ========================================================*/ +extern int Csw_TableCountCuts( Csw_Man_t * p ); extern void Csw_TableCutInsert( Csw_Man_t * p, Csw_Cut_t * pCut ); -extern Dar_Obj_t * Csw_TableCutLookup( Csw_Man_t * p, Csw_Cut_t * pCut ); -extern unsigned int Cudd_PrimeCws( unsigned int p ); +extern Aig_Obj_t * Csw_TableCutLookup( Csw_Man_t * p, Csw_Cut_t * pCut ); #ifdef __cplusplus } diff --git a/src/aig/csw/cswMan.c b/src/aig/csw/cswMan.c index 180fecef..2af1a844 100644 --- a/src/aig/csw/cswMan.c +++ b/src/aig/csw/cswMan.c @@ -39,10 +39,10 @@ SeeAlso [] ***********************************************************************/ -Csw_Man_t * Csw_ManStart( Dar_Man_t * pMan, int nCutsMax, int nLeafMax, int fVerbose ) +Csw_Man_t * Csw_ManStart( Aig_Man_t * pMan, int nCutsMax, int nLeafMax, int fVerbose ) { Csw_Man_t * p; - Dar_Obj_t * pObj; + Aig_Obj_t * pObj; int i; assert( nCutsMax >= 2 ); assert( nLeafMax <= 16 ); @@ -54,24 +54,26 @@ Csw_Man_t * Csw_ManStart( Dar_Man_t * pMan, int nCutsMax, int nLeafMax, int fVer p->fVerbose = fVerbose; p->pManAig = pMan; // create the new manager - p->pManRes = Dar_ManStartFrom( pMan ); - assert( Dar_ManPiNum(p->pManAig) == Dar_ManPiNum(p->pManRes) ); + p->pManRes = Aig_ManStartFrom( pMan ); + assert( Aig_ManPiNum(p->pManAig) == Aig_ManPiNum(p->pManRes) ); // allocate room for cuts and equivalent nodes - p->pEquiv = ALLOC( Dar_Obj_t *, Dar_ManObjIdMax(pMan) + 1 ); - p->pCuts = ALLOC( Csw_Cut_t *, Dar_ManObjIdMax(pMan) + 1 ); - memset( p->pCuts, 0, sizeof(Dar_Obj_t *) * (Dar_ManObjIdMax(pMan) + 1) ); + p->pnRefs = ALLOC( int, Aig_ManObjIdMax(pMan) + 1 ); + p->pEquiv = ALLOC( Aig_Obj_t *, Aig_ManObjIdMax(pMan) + 1 ); + p->pCuts = ALLOC( Csw_Cut_t *, Aig_ManObjIdMax(pMan) + 1 ); + memset( p->pCuts, 0, sizeof(Aig_Obj_t *) * (Aig_ManObjIdMax(pMan) + 1) ); + memset( p->pnRefs, 0, sizeof(int) * (Aig_ManObjIdMax(pMan) + 1) ); // allocate memory manager - p->nTruthWords = Dar_TruthWordNum(nLeafMax); + p->nTruthWords = Aig_TruthWordNum(nLeafMax); p->nCutSize = sizeof(Csw_Cut_t) + sizeof(int) * nLeafMax + sizeof(unsigned) * p->nTruthWords; - p->pMemCuts = Dar_MmFixedStart( p->nCutSize * p->nCutsMax, 512 ); + p->pMemCuts = Aig_MmFixedStart( p->nCutSize * p->nCutsMax, 512 ); // allocate hash table for cuts - p->nTableSize = Cudd_PrimeCws( Dar_ManNodeNum(pMan) * p->nCutsMax / 2 ); + p->nTableSize = Aig_PrimeCudd( Aig_ManNodeNum(pMan) * p->nCutsMax / 2 ); p->pTable = ALLOC( Csw_Cut_t *, p->nTableSize ); - memset( p->pTable, 0, sizeof(Dar_Obj_t *) * p->nTableSize ); + memset( p->pTable, 0, sizeof(Aig_Obj_t *) * p->nTableSize ); // set the pointers to the available fraig nodes - Csw_ObjSetEquiv( p, Dar_ManConst1(p->pManAig), Dar_ManConst1(p->pManRes) ); - Dar_ManForEachPi( p->pManAig, pObj, i ) - Csw_ObjSetEquiv( p, pObj, Dar_ManPi(p->pManRes, i) ); + Csw_ObjSetEquiv( p, Aig_ManConst1(p->pManAig), Aig_ManConst1(p->pManRes) ); + Aig_ManForEachPi( p->pManAig, pObj, i ) + Csw_ObjSetEquiv( p, pObj, Aig_ManPi(p->pManRes, i) ); // room for temporary truth tables p->puTemp[0] = ALLOC( unsigned, 4 * p->nTruthWords ); p->puTemp[1] = p->puTemp[0] + p->nTruthWords; @@ -93,8 +95,23 @@ Csw_Man_t * Csw_ManStart( Dar_Man_t * pMan, int nCutsMax, int nLeafMax, int fVer ***********************************************************************/ void Csw_ManStop( Csw_Man_t * p ) { + if ( p->fVerbose ) + { + int nNodesBeg = Aig_ManNodeNum(p->pManAig); + int nNodesEnd = Aig_ManNodeNum(p->pManRes); + printf( "Beg = %7d. End = %7d. (%6.2f %%) Try = %7d. Cuts = %8d.\n", + nNodesBeg, nNodesEnd, 100.0*(nNodesBeg-nNodesEnd)/nNodesBeg, + p->nNodesTried, Csw_TableCountCuts( p ) ); + printf( "Triv0 = %6d. Triv1 = %6d. Triv2 = %6d. Cut-replace = %6d.\n", + p->nNodesTriv0, p->nNodesTriv1, p->nNodesTriv2, p->nNodesCuts ); + PRTP( "Cuts ", p->timeCuts, p->timeTotal ); + PRTP( "Hashing ", p->timeHash, p->timeTotal ); + PRTP( "Other ", p->timeOther, p->timeTotal ); + PRTP( "TOTAL ", p->timeTotal, p->timeTotal ); + } free( p->puTemp[0] ); - Dar_MmFixedStop( p->pMemCuts, 0 ); + Aig_MmFixedStop( p->pMemCuts, 0 ); + free( p->pnRefs ); free( p->pEquiv ); free( p->pCuts ); free( p->pTable ); diff --git a/src/aig/csw/cswTable.c b/src/aig/csw/cswTable.c index 82f09d01..87e36ae1 100644 --- a/src/aig/csw/cswTable.c +++ b/src/aig/csw/cswTable.c @@ -65,41 +65,26 @@ unsigned Csw_CutHash( Csw_Cut_t * pCut ) return uHash; } -/**Function******************************************************************** - - Synopsis [Returns the next prime >= p.] +/**Function************************************************************* - Description [Copied from CUDD, for stand-aloneness.] + Synopsis [Returns the total number of cuts in the table.] - SideEffects [None] + Description [] + + SideEffects [] SeeAlso [] -******************************************************************************/ -unsigned int Cudd_PrimeCws( unsigned int p ) +***********************************************************************/ +int Csw_TableCountCuts( Csw_Man_t * p ) { - int i,pn; - - p--; - do { - p++; - if (p&1) { - pn = 1; - i = 3; - while ((unsigned) (i * i) <= p) { - if (p % i == 0) { - pn = 0; - break; - } - i += 2; - } - } else { - pn = 0; - } - } while (!pn); - return(p); - -} /* end of Cudd_Prime */ + Csw_Cut_t * pEnt; + int i, Counter = 0; + for ( i = 0; i < p->nTableSize; i++ ) + for ( pEnt = p->pTable[i]; pEnt; pEnt = pEnt->pNext ) + Counter++; + return Counter; +} /**Function************************************************************* @@ -130,9 +115,9 @@ void Csw_TableCutInsert( Csw_Man_t * p, Csw_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -Dar_Obj_t * Csw_TableCutLookup( Csw_Man_t * p, Csw_Cut_t * pCut ) +Aig_Obj_t * Csw_TableCutLookup( Csw_Man_t * p, Csw_Cut_t * pCut ) { - Dar_Obj_t * pRes = NULL; + Aig_Obj_t * pRes = NULL; Csw_Cut_t * pEnt; unsigned * pTruthNew, * pTruthOld; int iEntry = Csw_CutHash(pCut) % p->nTableSize; @@ -150,8 +135,8 @@ Dar_Obj_t * Csw_TableCutLookup( Csw_Man_t * p, Csw_Cut_t * pCut ) { if ( Kit_TruthIsEqual( pTruthOld, pTruthNew, pCut->nFanins ) ) { - pRes = Dar_ManObj( p->pManRes, pEnt->iNode ); - assert( pRes->fPhase == Dar_ManObj( p->pManRes, pCut->iNode )->fPhase ); + pRes = Aig_ManObj( p->pManRes, pEnt->iNode ); + assert( pRes->fPhase == Aig_ManObj( p->pManRes, pCut->iNode )->fPhase ); break; } } @@ -159,8 +144,8 @@ Dar_Obj_t * Csw_TableCutLookup( Csw_Man_t * p, Csw_Cut_t * pCut ) { if ( Kit_TruthIsOpposite( pTruthOld, pTruthNew, pCut->nFanins ) ) { - pRes = Dar_Not( Dar_ManObj( p->pManRes, pEnt->iNode ) ); - assert( Dar_Regular(pRes)->fPhase != Dar_ManObj( p->pManRes, pCut->iNode )->fPhase ); + pRes = Aig_Not( Aig_ManObj( p->pManRes, pEnt->iNode ) ); + assert( Aig_Regular(pRes)->fPhase != Aig_ManObj( p->pManRes, pCut->iNode )->fPhase ); break; } } -- cgit v1.2.3