/**CFile**************************************************************** FileName [cutNode.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [K-feasible cut computation package.] Synopsis [Procedures to compute cuts for a node.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - June 20, 2005.] Revision [$Id: cutNode.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] ***********************************************************************/ #include "cutInt.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// static int Cut_NodeMapping( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 ); static int Cut_NodeMapping2( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Returns 1 if pDom is contained in pCut.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Cut_CutCheckDominance( Cut_Cut_t * pDom, Cut_Cut_t * pCut ) { int i, k; for ( i = 0; i < (int)pDom->nLeaves; i++ ) { for ( k = 0; k < (int)pCut->nLeaves; k++ ) if ( pDom->pLeaves[i] == pCut->pLeaves[k] ) break; if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut return 0; } // every node in pDom is contained in pCut return 1; } /**Function************************************************************* Synopsis [Filters cuts using dominance.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Cut_CutFilter( Cut_Man_t * p, Cut_Cut_t * pList ) { Cut_Cut_t * pListR, ** ppListR = &pListR; Cut_Cut_t * pCut, * pCut2, * pDom, * pPrev; // save the first cut *ppListR = pList, ppListR = &pList->pNext; // try to filter out other cuts pPrev = pList; Cut_ListForEachCutSafe( pList->pNext, pCut, pCut2 ) { assert( pCut->nLeaves > 1 ); // go through all the previous cuts up to pCut Cut_ListForEachCutStop( pList->pNext, pDom, pCut ) { if ( pDom->nLeaves > pCut->nLeaves ) continue; if ( (pDom->uSign & pCut->uSign) != pDom->uSign ) continue; if ( Cut_CutCheckDominance( pDom, pCut ) ) break; } if ( pDom != pCut ) // pDom is contained in pCut - recycle pCut { // make sure cuts are connected after removing pPrev->pNext = pCut->pNext; // recycle the cut Cut_CutRecycle( p, pCut ); } else // pDom is NOT contained in pCut - save pCut { *ppListR = pCut, ppListR = &pCut->pNext; pPrev = pCut; } } *ppListR = NULL; } /**Function************************************************************* Synopsis [Checks equality of one cut.] Description [Returns 1 if the cut is removed.] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Cut_CutFilterOneEqual( Cut_Man_t * p, Cut_List_t * pSuperList, Cut_Cut_t * pCut ) { Cut_Cut_t * pTemp; Cut_ListForEachCut( pSuperList->pHead[pCut->nLeaves], pTemp ) { // skip the non-contained cuts if ( pCut->uSign != pTemp->uSign ) continue; // check containment seriously if ( Cut_CutCheckDominance( pTemp, pCut ) ) { p->nCutsFilter++; Cut_CutRecycle( p, pCut ); return 1; } } return 0; } /**Function************************************************************* Synopsis [Checks containment for one cut.] Description [Returns 1 if the cut is removed.] SideEffects [May remove other cuts in the set.] SeeAlso [] ***********************************************************************/ static inline int Cut_CutFilterOne( Cut_Man_t * p, Cut_List_t * pSuperList, Cut_Cut_t * pCut ) { Cut_Cut_t * pTemp, * pTemp2, ** ppTail; int a; // check if this cut is filtered out by smaller cuts for ( a = 2; a <= (int)pCut->nLeaves; a++ ) { Cut_ListForEachCut( pSuperList->pHead[a], pTemp ) { // skip the non-contained cuts if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign ) continue; // check containment seriously if ( Cut_CutCheckDominance( pTemp, pCut ) ) { p->nCutsFilter++; Cut_CutRecycle( p, pCut ); return 1; } } } // filter out other cuts using this one for ( a = pCut->nLeaves + 1; a <= (int)pCut->nVarsMax; a++ ) { ppTail = pSuperList->pHead + a; Cut_ListForEachCutSafe( pSuperList->pHead[a], pTemp, pTemp2 ) { // skip the non-contained cuts if ( (pTemp->uSign & pCut->uSign) != pCut->uSign ) { ppTail = &pTemp->pNext; continue; } // check containment seriously if ( Cut_CutCheckDominance( pCut, pTemp ) ) { p->nCutsFilter++; p->nNodeCuts--; // move the head if ( pSuperList->pHead[a] == pTemp ) pSuperList->pHead[a] = pTemp->pNext; // move the tail if ( pSuperList->ppTail[a] == &pTemp->pNext ) pSuperList->ppTail[a] = ppTail; // skip the given cut in the list *ppTail = pTemp->pNext; // recycle pTemp Cut_CutRecycle( p, pTemp ); } else ppTail = &pTemp->pNext; } assert( ppTail == pSuperList->ppTail[a] ); assert( *ppTail == NULL ); } return 0; } /**Function************************************************************* Synopsis [Checks if the cut is local and can be removed.] Description [Returns 1 if the cut is removed.] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Cut_CutFilterGlobal( Cut_Man_t * p, Cut_Cut_t * pCut ) { int a; if ( pCut->nLeaves == 1 ) return 0; for ( a = 0; a < (int)pCut->nLeaves; a++ ) if ( Vec_IntEntry( p->vNodeAttrs, pCut->pLeaves[a] ) ) // global return 0; // there is no global nodes, the cut should be removed p->nCutsFilter++; Cut_CutRecycle( p, pCut ); return 1; } /**Function************************************************************* Synopsis [Checks containment for one cut.] Description [Returns 1 if the cut is removed.] SideEffects [May remove other cuts in the set.] SeeAlso [] ***********************************************************************/ static inline int Cut_CutFilterOld( Cut_Man_t * p, Cut_Cut_t * pList, Cut_Cut_t * pCut ) { Cut_Cut_t * pPrev, * pTemp, * pTemp2, ** ppTail; // check if this cut is filtered out by smaller cuts pPrev = NULL; Cut_ListForEachCut( pList, pTemp ) { if ( pTemp->nLeaves > pCut->nLeaves ) break; pPrev = pTemp; // skip the non-contained cuts if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign ) continue; // check containment seriously if ( Cut_CutCheckDominance( pTemp, pCut ) ) { p->nCutsFilter++; Cut_CutRecycle( p, pCut ); return 1; } } assert( pPrev->pNext == pTemp ); // filter out other cuts using this one ppTail = &pPrev->pNext; Cut_ListForEachCutSafe( pTemp, pTemp, pTemp2 ) { // skip the non-contained cuts if ( (pTemp->uSign & pCut->uSign) != pCut->uSign ) { ppTail = &pTemp->pNext; continue; } // check containment seriously if ( Cut_CutCheckDominance( pCut, pTemp ) ) { p->nCutsFilter++; p->nNodeCuts--; // skip the given cut in the list *ppTail = pTemp->pNext; // recycle pTemp Cut_CutRecycle( p, pTemp ); } else ppTail = &pTemp->pNext; } assert( *ppTail == NULL ); return 0; } /**Function************************************************************* Synopsis [Processes two cuts.] Description [Returns 1 if the limit has been reached.] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Cut_CutProcessTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, Cut_List_t * pSuperList ) { Cut_Cut_t * pCut; // merge the cuts if ( pCut0->nLeaves >= pCut1->nLeaves ) pCut = Cut_CutMergeTwo( p, pCut0, pCut1 ); else pCut = Cut_CutMergeTwo( p, pCut1, pCut0 ); if ( pCut == NULL ) return 0; assert( p->pParams->fSeq || pCut->nLeaves > 1 ); // set the signature pCut->uSign = pCut0->uSign | pCut1->uSign; if ( p->pParams->fRecord ) pCut->Num0 = pCut0->Num0, pCut->Num1 = pCut1->Num0; // check containment if ( p->pParams->fFilter ) { if ( Cut_CutFilterOne(p, pSuperList, pCut) ) // if ( Cut_CutFilterOneEqual(p, pSuperList, pCut) ) return 0; if ( p->pParams->fSeq ) { if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) ) return 0; if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) ) return 0; } } if ( p->pParams->fGlobal ) { assert( p->vNodeAttrs != NULL ); if ( Cut_CutFilterGlobal( p, pCut ) ) return 0; } // compute the truth table if ( p->pParams->fTruth ) Cut_TruthCompute( p, pCut, pCut0, pCut1, p->fCompl0, p->fCompl1 ); // add to the list Cut_ListAdd( pSuperList, pCut ); // return status (0 if okay; 1 if exceeded the limit) return ++p->nNodeCuts == p->pParams->nKeepMax; } /**Function************************************************************* Synopsis [Computes the cuts by merging cuts at two nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int fTriv, int TreeCode ) { Cut_List_t Super, * pSuper = &Super; Cut_Cut_t * pList, * pCut; int clk; // start the number of cuts at the node p->nNodes++; p->nNodeCuts = 0; // prepare information for recording if ( p->pParams->fRecord ) { Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node0) ); Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node1) ); } // compute the cuts clk = clock(); Cut_ListStart( pSuper ); Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, Cut_NodeReadCutsNew(p, Node0), Cut_NodeReadCutsNew(p, Node1), fTriv, TreeCode ); pList = Cut_ListFinish( pSuper ); p->timeMerge += clock() - clk; // verify the result of cut computation // Cut_CutListVerify( pList ); // performing the recordi
generated by cgit v1.2.3 (git 2.25.1) at >Num1 << 16) | pCut->Num0) ); Vec_IntWriteEntry( p->vNodeCuts, Node, Vec_IntSize(p->vCutPairs) - Vec_IntEntry(p->vNodeStarts, Node) ); } if ( p->pParams->fRecordAig ) { extern void Aig_RManRecord( unsigned * pTruth, int nVarsInit ); Cut_ListForEachCut( pList, pCut ) if ( Cut_CutReadLeaveNum(pCut) > 4 ) Aig_RManRecord( Cut_CutReadTruth(pCut), Cut_CutReadLeaveNum(pCut) ); } // check if the node is over the list if ( p->nNodeCuts == p->pParams->nKeepMax ) p->nCutsLimit++; // set the list at the node Vec_PtrFillExtra( p->vCutsNew, Node + 1, NULL ); assert( Cut_NodeReadCutsNew(p, Node) == NULL ); ///// // pList->pNext = NULL; ///// Cut_NodeWriteCutsNew( p, Node, pList ); // filter the cuts //clk = clock(); // if ( p->pParams->fFilter ) // Cut_CutFilter( p, pList0 ); //p->timeFilter += clock() - clk; // perform mapping of this node with these cuts clk = clock(); if ( p->pParams->fMap && !p->pParams->fSeq ) { // int Delay1, Delay2; // Delay1 = Cut_NodeMapping( p, pList, Node, Node0, Node1 ); // Delay2 = Cut_NodeMapping2( p, pList, Node, Node0, Node1 ); // assert( Delay1 >= Delay2 ); Cut_NodeMapping( p, pList, Node, Node0, Node1 ); } p->timeMap += clock() - clk; return pList; } /**Function************************************************************* Synopsis [Returns optimum delay mapping.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cut_NodeMapping2( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 ) { Cut_Cut_t * pCut; int DelayMin, DelayCur, i; if ( pCuts == NULL ) p->nDelayMin = -1; if ( p->nDelayMin == -1 ) return -1; DelayMin = 1000000; Cut_ListForEachCut( pCuts, pCut ) { if ( pCut->nLeaves == 1 ) continue; DelayCur = 0; for ( i = 0; i < (int)pCut->nLeaves; i++ ) if ( DelayCur < Vec_IntEntry(p->vDelays, pCut->pLeaves[i]) ) DelayCur = Vec_IntEntry(p->vDelays, pCut->pLeaves[i]); if ( DelayMin > DelayCur ) DelayMin = DelayCur; } if ( DelayMin == 1000000 ) { p->nDelayMin = -1; return -1; } DelayMin++; Vec_IntWriteEntry( p->vDelays, Node, DelayMin ); if ( p->nDelayMin < DelayMin ) p->nDelayMin = DelayMin; return DelayMin; } /**Function************************************************************* Synopsis [Returns optimum delay mapping using the largest cut.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cut_NodeMapping( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 ) { Cut_Cut_t * pCut0, * pCut1, * pCut; int Delay0, Delay1, Delay; // get the fanin cuts Delay0 = Vec_IntEntry( p->vDelays2, Node0 ); Delay1 = Vec_IntEntry( p->vDelays2, Node1 ); pCut0 = (Delay0 == 0) ? (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node0 ) : (Cut_Cut_t *)Vec_PtrEntry( p->vCutsMax, Node0 ); pCut1 = (Delay1 == 0) ? (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node1 ) : (Cut_Cut_t *)Vec_PtrEntry( p->vCutsMax, Node1 ); if ( Delay0 == Delay1 ) Delay = (Delay0 == 0) ? Delay0 + 1: Delay0; else if ( Delay0 > Delay1 ) { Delay = Delay0; pCut1 = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node1 ); assert( pCut1->nLeaves == 1 ); } else // if ( Delay0 < Delay1 ) { Delay = Delay1; pCut0 = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node0 ); assert( pCut0->nLeaves == 1 ); } // merge the cuts if ( pCut0->nLeaves < pCut1->nLeaves ) pCut = Cut_CutMergeTwo( p, pCut1, pCut0 ); else pCut = Cut_CutMergeTwo( p, pCut0, pCut1 ); if ( pCut == NULL ) { Delay++; pCut = Cut_CutAlloc( p ); pCut->nLeaves = 2; pCut->pLeaves[0] = Node0 < Node1 ? Node0 : Node1; pCut->pLeaves[1] = Node0 < Node1 ? Node1 : Node0; } assert( Delay > 0 ); Vec_IntWriteEntry( p->vDelays2, Node, Delay ); Vec_PtrWriteEntry( p->vCutsMax, Node, pCut ); if ( p->nDelayMin < Delay ) p->nDelayMin = Delay; return Delay; } /**Function************************************************************* Synopsis [Computes area after mapping.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cut_ManMappingArea_rec( Cut_Man_t * p, int Node ) { Cut_Cut_t * pCut; int i, Counter; if ( p->vCutsMax == NULL ) return 0; pCut = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsMax, Node ); if ( pCut == NULL || pCut->nLeaves == 1 ) return 0; Counter = 0; for ( i = 0; i < (int)pCut->nLeaves; i++ ) Counter += Cut_ManMappingArea_rec( p, pCut->pLeaves[i] ); Vec_PtrWriteEntry( p->vCutsMax, Node, NULL ); return 1 + Counter; } /**Function************************************************************* Synopsis [Computes the cuts by merging cuts at two nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cut_NodeDoComputeCuts( Cut_Man_t * p, Cut_List_t * pSuper, int Node, int fCompl0, int fCompl1, Cut_Cut_t * pList0, Cut_Cut_t * pList1, int fTriv, int TreeCode ) { Cut_Cut_t * pStop0, * pStop1, * pTemp0, * pTemp1; Cut_Cut_t * pStore0 = NULL, * pStore1 = NULL; // Suppress "might be used uninitialized" int i, nCutsOld, Limit; // start with the elementary cut if ( fTriv ) { // printf( "Creating trivial cut %d.\n", Node ); pTemp0 = Cut_CutCreateTriv( p, Node ); Cut_ListAdd( pSuper, pTemp0 ); p->nNodeCuts++; } // get the cut lists of children if ( pList0 == NULL || pList1 == NULL || (p->pParams->fLocal && TreeCode) ) return; // remember the old number of cuts nCutsOld = p->nCutsCur; Limit = p->pParams->nVarsMax; // get the simultation bit of the node p->fSimul = (fCompl0 ^ pList0->fSimul) & (fCompl1 ^ pList1->fSimul); // set temporary variables p->fCompl0 = fCompl0; p->fCompl1 = fCompl1; // if tree cuts are computed, make sure only the unit cuts propagate over the DAG nodes if ( TreeCode & 1 ) { assert( pList0->nLeaves == 1 ); pStore0 = pList0->pNext; pList0->pNext = NULL; } if ( TreeCode & 2 ) { assert( pList1->nLeaves == 1 ); pStore1 = pList1->pNext; pList1->pNext = NULL; } // find the point in the list where the max-var cuts begin Cut_ListForEachCut( pList0, pStop0 ) if ( pStop0->nLeaves == (unsigned)Limit ) break; Cut_ListForEachCut( pList1, pStop1 ) if ( pStop1->nLeaves == (unsigned)Limit ) break; // small by small Cut_ListForEachCutStop( pList0, pTemp0, pStop0 ) Cut_ListForEachCutStop( pList1, pTemp1, pStop1 ) { if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) ) goto Quits; } // small by large Cut_ListForEachCutStop( pList0, pTemp0, pStop0 ) Cut_ListForEachCut( pStop1, pTemp1 ) { if ( (pTemp0->uSign & pTemp1->uSign) != pTemp0->uSign ) continue; if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) ) goto Quits; } // small by large Cut_ListForEachCutStop( pList1, pTemp1, pStop1 ) Cut_ListForEachCut( pStop0, pTemp0 ) { if ( (pTemp0->uSign & pTemp1->uSign) != pTemp1->uSign ) continue; if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) ) goto Quits; } // large by large Cut_ListForEachCut( pStop0, pTemp0 ) Cut_ListForEachCut( pStop1, pTemp1 ) { assert( pTemp0->nLeaves == (unsigned)Limit && pTemp1->nLeaves == (unsigned)Limit ); if ( pTemp0->uSign != pTemp1->uSign ) continue; for ( i = 0; i < Limit; i++ ) if ( pTemp0->pLeaves[i] != pTemp1->pLeaves[i] ) break; if ( i < Limit ) continue; if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) ) goto Quits; } if ( p->nNodeCuts == 0 ) p->nNodesNoCuts++; Quits: if ( TreeCode & 1 ) pList0->pNext = pStore0; if ( TreeCode & 2 ) pList1->pNext = pStore1; } /**Function************************************************************* Synopsis [Computes the cuts by unioning cuts at a choice node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) { Cut_List_t Super, * pSuper = &Super; Cut_Cut_t * pList, * pListStart, * pCut, * pCut2; Cut_Cut_t * pTop = NULL; // Suppress "might be used uninitialized" int i, k, Node, Root, Limit = p->pParams->nVarsMax; int clk = clock(); // start the new list Cut_ListStart( pSuper ); // remember the root node to save the resulting cuts Root = Vec_IntEntry( vNodes, 0 ); p->nNodeCuts = 1; // collect small cuts first Vec_PtrClear( p->vTemp ); Vec_IntForEachEntry( vNodes, Node, i ) { // get the cuts of this node pList = Cut_NodeReadCutsNew( p, Node ); Cut_NodeWriteCutsNew( p, Node, NULL ); assert( pList ); // remember the starting point pListStart = pList->pNext; pList->pNext = NULL; // save or recycle the elementary cut if ( i == 0 ) Cut_ListAdd( pSuper, pList ), pTop = pList; else Cut_CutRecycle( p, pList ); // save all the cuts that are smaller than the limit Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) { if ( pCut->nLeaves == (unsigned)Limit ) { Vec_PtrPush( p->vTemp, pCut ); break; } // check containment if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) ) continue; // set the complemented bit by comparing the first cut with the current cut pCut->fCompl = pTop->fSimul ^ pCut->fSimul; pListStart = pCut->pNext; pCut->pNext = NULL; // add to the list Cut_ListAdd( pSuper, pCut ); if ( ++p->nNodeCuts == p->pParams->nKeepMax ) { // recycle the rest of the cuts of this node Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); // recycle all cuts of other nodes Vec_IntForEachEntryStart( vNodes, Node, k, i+1 ) Cut_NodeFreeCuts( p, Node ); // recycle the saved cuts of other nodes Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, k ) Cut_ListForEachCutSafe( pList, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); goto finish; } } } // collect larger cuts next Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, i ) { Cut_ListForEachCutSafe( pList, pCut, pCut2 ) { // check containment if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) ) continue; // set the complemented bit pCut->fCompl = pTop->fSimul ^ pCut->fSimul; pListStart = pCut->pNext; pCut->pNext = NULL; // add to the list Cut_ListAdd( pSuper, pCut ); if ( ++p->nNodeCuts == p->pParams->nKeepMax ) { // recycle the rest of the cuts Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); // recycle the saved cuts of other nodes Vec_PtrForEachEntryStart( Cut_Cut_t *, p->vTemp, pList, k, i+1 ) Cut_ListForEachCutSafe( pList, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); goto finish; } } } finish : // set the cuts at the node assert( Cut_NodeReadCutsNew(p, Root) == NULL ); pList = Cut_ListFinish( pSuper ); Cut_NodeWriteCutsNew( p, Root, pList ); p->timeUnion += clock() - clk; // filter the cuts //clk = clock(); // if ( p->pParams->fFilter ) // Cut_CutFilter( p, pList ); //p->timeFilter += clock() - clk; p->nNodes -= vNodes->nSize - 1; return pList; } /**Function************************************************************* Synopsis [Computes the cuts by unioning cuts at a choice node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Cut_Cut_t * Cut_NodeUnionCutsSeq( Cut_Man_t * p, Vec_Int_t * vNodes, int CutSetNum, int fFirst ) { Cut_List_t Super, * pSuper = &Super; Cut_Cut_t * pList, * pListStart, * pCut, * pCut2, * pTop; int i, k, Node, Root, Limit = p->pParams->nVarsMax; int clk = clock(); // start the new list Cut_ListStart( pSuper ); // remember the root node to save the resulting cuts Root = Vec_IntEntry( vNodes, 0 ); p->nNodeCuts = 1; // store the original lists for comparison p->pCompareOld = Cut_NodeReadCutsOld( p, Root ); p->pCompareNew = (CutSetNum >= 0)? Cut_NodeReadCutsNew( p, Root ) : NULL; // get the topmost cut pTop = NULL; if ( (pTop = Cut_NodeReadCutsOld( p, Root )) == NULL ) pTop = Cut_NodeReadCutsNew( p, Root ); assert( pTop != NULL ); // collect small cuts first Vec_PtrClear( p->vTemp ); Vec_IntForEachEntry( vNodes, Node, i ) { // get the cuts of this node if ( i == 0 && CutSetNum >= 0 ) { pList = Cut_NodeReadCutsTemp( p, CutSetNum ); Cut_NodeWriteCutsTemp( p, CutSetNum, NULL ); } else { pList = Cut_NodeReadCutsNew( p, Node ); Cut_NodeWriteCutsNew( p, Node, NULL ); } if ( pList == NULL ) continue; // process the cuts if ( fFirst ) { // remember the starting point pListStart = pList->pNext; pList->pNext = NULL; // save or recycle the elementary cut if ( i == 0 ) Cut_ListAdd( pSuper, pList ); else Cut_CutRecycle( p, pList ); } else pListStart = pList; // save all the cuts that are smaller than the limit Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) { if ( pCut->nLeaves == (unsigned)Limit ) { Vec_PtrPush( p->vTemp, pCut ); break; } // check containment // if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) ) // continue; if ( p->pParams->fFilter ) { if ( Cut_CutFilterOne(p, pSuper, pCut) ) continue; if ( p->pParams->fSeq ) { if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) ) continue; if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) ) continue; } } // set the complemented bit by comparing the first cut with the current cut pCut->fCompl = pTop->fSimul ^ pCut->fSimul; pListStart = pCut->pNext; pCut->pNext = NULL; // add to the list Cut_ListAdd( pSuper, pCut ); if ( ++p->nNodeCuts == p->pParams->nKeepMax ) { // recycle the rest of the cuts of this node Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); // recycle all cuts of other nodes Vec_IntForEachEntryStart( vNodes, Node, k, i+1 ) Cut_NodeFreeCuts( p, Node ); // recycle the saved cuts of other nodes Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, k ) Cut_ListForEachCutSafe( pList, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); goto finish; } } } // collect larger cuts next Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, i ) { Cut_ListForEachCutSafe( pList, pCut, pCut2 ) { // check containment // if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) ) // continue; if ( p->pParams->fFilter ) { if ( Cut_CutFilterOne(p, pSuper, pCut) ) continue; if ( p->pParams->fSeq ) { if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) ) continue; if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) ) continue; } } // set the complemented bit pCut->fCompl = pTop->fSimul ^ pCut->fSimul; pListStart = pCut->pNext; pCut->pNext = NULL; // add to the list Cut_ListAdd( pSuper, pCut ); if ( ++p->nNodeCuts == p->pParams->nKeepMax ) { // recycle the rest of the cuts Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); // recycle the saved cuts of other nodes Vec_PtrForEachEntryStart( Cut_Cut_t *, p->vTemp, pList, k, i+1 ) Cut_ListForEachCutSafe( pList, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); goto finish; } } } finish : // set the cuts at the node pList = Cut_ListFinish( pSuper ); // set the lists at the node // assert( Cut_NodeReadCutsNew(p, Root) == NULL ); // Cut_NodeWriteCutsNew( p, Root, pList ); if ( CutSetNum >= 0 ) { assert( Cut_NodeReadCutsTemp(p, CutSetNum) == NULL ); Cut_NodeWriteCutsTemp( p, CutSetNum, pList ); } else { assert( Cut_NodeReadCutsNew(p, Root) == NULL ); Cut_NodeWriteCutsNew( p, Root, pList ); } p->timeUnion += clock() - clk; // filter the cuts //clk = clock(); // if ( p->pParams->fFilter ) // Cut_CutFilter( p, pList ); //p->timeFilter += clock() - clk; // if ( fFirst ) // p->nNodes -= vNodes->nSize - 1; return pList; } /**Function************************************************************* Synopsis [Verifies that the list contains only non-dominated cuts.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cut_CutListVerify( Cut_Cut_t * pList ) { Cut_Cut_t * pCut, * pDom; Cut_ListForEachCut( pList, pCut ) { Cut_ListForEachCutStop( pList, pDom, pCut ) { if ( Cut_CutCheckDominance( pDom, pCut ) ) { printf( "******************* These are contained cuts:\n" ); Cut_CutPrint( pDom, 1 ); Cut_CutPrint( pDom, 1 ); return 0; } } } return 1; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END