src/opt/cut/cutNode.c File Reference

#include "cutInt.h"
Include dependency graph for cutNode.c:

Go to the source code of this file.

Functions

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)
static int Cut_CutCheckDominance (Cut_Cut_t *pDom, Cut_Cut_t *pCut)
static void Cut_CutFilter (Cut_Man_t *p, Cut_Cut_t *pList)
static int Cut_CutFilterOneEqual (Cut_Man_t *p, Cut_List_t *pSuperList, Cut_Cut_t *pCut)
static int Cut_CutFilterOne (Cut_Man_t *p, Cut_List_t *pSuperList, Cut_Cut_t *pCut)
static int Cut_CutFilterGlobal (Cut_Man_t *p, Cut_Cut_t *pCut)
static int Cut_CutFilterOld (Cut_Man_t *p, Cut_Cut_t *pList, Cut_Cut_t *pCut)
static int Cut_CutProcessTwo (Cut_Man_t *p, Cut_Cut_t *pCut0, Cut_Cut_t *pCut1, Cut_List_t *pSuperList)
Cut_Cut_t * Cut_NodeComputeCuts (Cut_Man_t *p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int fTriv, int TreeCode)
int Cut_ManMappingArea_rec (Cut_Man_t *p, int Node)
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 * Cut_NodeUnionCuts (Cut_Man_t *p, Vec_Int_t *vNodes)
Cut_Cut_t * Cut_NodeUnionCutsSeq (Cut_Man_t *p, Vec_Int_t *vNodes, int CutSetNum, int fFirst)
int Cut_CutListVerify (Cut_Cut_t *pList)

Function Documentation

static int Cut_CutCheckDominance ( Cut_Cut_t *  pDom,
Cut_Cut_t *  pCut 
) [inline, static]

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Returns 1 if pDom is contained in pCut.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file cutNode.c.

00046 {
00047     int i, k;
00048     for ( i = 0; i < (int)pDom->nLeaves; i++ )
00049     {
00050         for ( k = 0; k < (int)pCut->nLeaves; k++ )
00051             if ( pDom->pLeaves[i] == pCut->pLeaves[k] )
00052                 break;
00053         if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut
00054             return 0;
00055     }
00056     // every node in pDom is contained in pCut
00057     return 1;
00058 }

static void Cut_CutFilter ( Cut_Man_t *  p,
Cut_Cut_t *  pList 
) [inline, static]

Function*************************************************************

Synopsis [Filters cuts using dominance.]

Description []

SideEffects []

SeeAlso []

Definition at line 71 of file cutNode.c.

00072 { 
00073     Cut_Cut_t * pListR, ** ppListR = &pListR;
00074     Cut_Cut_t * pCut, * pCut2, * pDom, * pPrev;
00075     // save the first cut
00076     *ppListR = pList, ppListR = &pList->pNext;
00077     // try to filter out other cuts
00078     pPrev = pList;
00079     Cut_ListForEachCutSafe( pList->pNext, pCut, pCut2 )
00080     {
00081         assert( pCut->nLeaves > 1 );
00082         // go through all the previous cuts up to pCut
00083         Cut_ListForEachCutStop( pList->pNext, pDom, pCut )
00084         {
00085             if ( pDom->nLeaves > pCut->nLeaves )
00086                 continue;
00087             if ( (pDom->uSign & pCut->uSign) != pDom->uSign )
00088                 continue;
00089             if ( Cut_CutCheckDominance( pDom, pCut ) )
00090                 break;
00091         }
00092         if ( pDom != pCut ) // pDom is contained in pCut - recycle pCut
00093         {
00094             // make sure cuts are connected after removing
00095             pPrev->pNext = pCut->pNext;
00096             // recycle the cut
00097             Cut_CutRecycle( p, pCut );
00098         }
00099         else // pDom is NOT contained in pCut - save pCut
00100         {
00101             *ppListR = pCut, ppListR = &pCut->pNext;
00102             pPrev = pCut;
00103         }
00104     }
00105     *ppListR = NULL;
00106 }

static int Cut_CutFilterGlobal ( Cut_Man_t *  p,
Cut_Cut_t *  pCut 
) [inline, static]

Function*************************************************************

Synopsis [Checks if the cut is local and can be removed.]

Description [Returns 1 if the cut is removed.]

SideEffects []

SeeAlso []

Definition at line 221 of file cutNode.c.

00222 {
00223     int a;
00224     if ( pCut->nLeaves == 1 )
00225         return 0;
00226     for ( a = 0; a < (int)pCut->nLeaves; a++ )
00227         if ( Vec_IntEntry( p->vNodeAttrs, pCut->pLeaves[a] ) ) // global
00228             return 0;
00229     // there is no global nodes, the cut should be removed
00230     p->nCutsFilter++;
00231     Cut_CutRecycle( p, pCut );
00232     return 1;
00233 }

static int Cut_CutFilterOld ( Cut_Man_t *  p,
Cut_Cut_t *  pList,
Cut_Cut_t *  pCut 
) [inline, static]

Function*************************************************************

Synopsis [Checks containment for one cut.]

Description [Returns 1 if the cut is removed.]

SideEffects [May remove other cuts in the set.]

SeeAlso []

Definition at line 247 of file cutNode.c.

00248 {
00249     Cut_Cut_t * pPrev, * pTemp, * pTemp2, ** ppTail;
00250 
00251     // check if this cut is filtered out by smaller cuts
00252     pPrev = NULL;
00253     Cut_ListForEachCut( pList, pTemp )
00254     {
00255         if ( pTemp->nLeaves > pCut->nLeaves )
00256             break;
00257         pPrev = pTemp;
00258         // skip the non-contained cuts
00259         if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign )
00260             continue;
00261         // check containment seriously
00262         if ( Cut_CutCheckDominance( pTemp, pCut ) )
00263         {
00264             p->nCutsFilter++;
00265             Cut_CutRecycle( p, pCut );
00266             return 1;
00267         }
00268     }
00269     assert( pPrev->pNext == pTemp );
00270 
00271     // filter out other cuts using this one
00272     ppTail = &pPrev->pNext;
00273     Cut_ListForEachCutSafe( pTemp, pTemp, pTemp2 )
00274     {
00275         // skip the non-contained cuts
00276         if ( (pTemp->uSign & pCut->uSign) != pCut->uSign )
00277         {
00278             ppTail = &pTemp->pNext;
00279             continue;
00280         }
00281         // check containment seriously
00282         if ( Cut_CutCheckDominance( pCut, pTemp ) )
00283         {
00284             p->nCutsFilter++;
00285             p->nNodeCuts--;
00286             // skip the given cut in the list
00287             *ppTail = pTemp->pNext;
00288             // recycle pTemp
00289             Cut_CutRecycle( p, pTemp );
00290         }
00291         else
00292             ppTail = &pTemp->pNext;
00293     }
00294     assert( *ppTail == NULL );
00295     return 0;
00296 }

static int Cut_CutFilterOne ( Cut_Man_t *  p,
Cut_List_t *  pSuperList,
Cut_Cut_t *  pCut 
) [inline, static]

Function*************************************************************

Synopsis [Checks containment for one cut.]

Description [Returns 1 if the cut is removed.]

SideEffects [May remove other cuts in the set.]

SeeAlso []

Definition at line 149 of file cutNode.c.

00150 {
00151     Cut_Cut_t * pTemp, * pTemp2, ** ppTail;
00152     int a;
00153 
00154     // check if this cut is filtered out by smaller cuts
00155     for ( a = 2; a <= (int)pCut->nLeaves; a++ )
00156     {
00157         Cut_ListForEachCut( pSuperList->pHead[a], pTemp )
00158         {
00159             // skip the non-contained cuts
00160             if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign )
00161                 continue;
00162             // check containment seriously
00163             if ( Cut_CutCheckDominance( pTemp, pCut ) )
00164             {
00165                 p->nCutsFilter++;
00166                 Cut_CutRecycle( p, pCut );
00167                 return 1;
00168             }
00169         }
00170     }
00171 
00172     // filter out other cuts using this one
00173     for ( a = pCut->nLeaves + 1; a <= (int)pCut->nVarsMax; a++ )
00174     {
00175         ppTail = pSuperList->pHead + a;
00176         Cut_ListForEachCutSafe( pSuperList->pHead[a], pTemp, pTemp2 )
00177         {
00178             // skip the non-contained cuts
00179             if ( (pTemp->uSign & pCut->uSign) != pCut->uSign )
00180             {
00181                 ppTail = &pTemp->pNext;
00182                 continue;
00183             }
00184             // check containment seriously
00185             if ( Cut_CutCheckDominance( pCut, pTemp ) )
00186             {
00187                 p->nCutsFilter++;
00188                 p->nNodeCuts--;
00189                 // move the head
00190                 if ( pSuperList->pHead[a] == pTemp )
00191                     pSuperList->pHead[a] = pTemp->pNext;
00192                 // move the tail
00193                 if ( pSuperList->ppTail[a] == &pTemp->pNext )
00194                     pSuperList->ppTail[a] = ppTail;
00195                 // skip the given cut in the list
00196                 *ppTail = pTemp->pNext;
00197                 // recycle pTemp
00198                 Cut_CutRecycle( p, pTemp );
00199             }
00200             else
00201                 ppTail = &pTemp->pNext;
00202         }
00203         assert( ppTail == pSuperList->ppTail[a] );
00204         assert( *ppTail == NULL );
00205     }
00206 
00207     return 0;
00208 }

static int Cut_CutFilterOneEqual ( Cut_Man_t *  p,
Cut_List_t *  pSuperList,
Cut_Cut_t *  pCut 
) [inline, static]

Function*************************************************************

Synopsis [Checks equality of one cut.]

Description [Returns 1 if the cut is removed.]

SideEffects []

SeeAlso []

Definition at line 119 of file cutNode.c.

00120 {
00121     Cut_Cut_t * pTemp;
00122     Cut_ListForEachCut( pSuperList->pHead[pCut->nLeaves], pTemp )
00123     {
00124         // skip the non-contained cuts
00125         if ( pCut->uSign != pTemp->uSign )
00126             continue;
00127         // check containment seriously
00128         if ( Cut_CutCheckDominance( pTemp, pCut ) )
00129         {
00130             p->nCutsFilter++;
00131             Cut_CutRecycle( p, pCut );
00132             return 1;
00133         }
00134     }
00135     return 0;
00136 }

int Cut_CutListVerify ( Cut_Cut_t *  pList  ) 

Function*************************************************************

Synopsis [Verifies that the list contains only non-dominated cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 967 of file cutNode.c.

00968 { 
00969     Cut_Cut_t * pCut, * pDom;
00970     Cut_ListForEachCut( pList, pCut )
00971     {
00972         Cut_ListForEachCutStop( pList, pDom, pCut )
00973         {
00974             if ( Cut_CutCheckDominance( pDom, pCut ) )
00975             {
00976                 int x = 0;
00977                 printf( "******************* These are contained cuts:\n" );
00978                 Cut_CutPrint( pDom, 1 );
00979                 Cut_CutPrint( pDom, 1 );
00980                 
00981                 return 0;
00982             }
00983         }
00984     }
00985     return 1;
00986 }

static int Cut_CutProcessTwo ( Cut_Man_t *  p,
Cut_Cut_t *  pCut0,
Cut_Cut_t *  pCut1,
Cut_List_t *  pSuperList 
) [inline, static]

Function*************************************************************

Synopsis [Processes two cuts.]

Description [Returns 1 if the limit has been reached.]

SideEffects []

SeeAlso []

Definition at line 309 of file cutNode.c.

00310 {
00311     Cut_Cut_t * pCut;
00312     // merge the cuts
00313     if ( pCut0->nLeaves >= pCut1->nLeaves )
00314         pCut = Cut_CutMergeTwo( p, pCut0, pCut1 );
00315     else
00316         pCut = Cut_CutMergeTwo( p, pCut1, pCut0 );
00317     if ( pCut == NULL )
00318         return 0;
00319     assert( p->pParams->fSeq || pCut->nLeaves > 1 );
00320     // set the signature
00321     pCut->uSign = pCut0->uSign | pCut1->uSign;
00322     if ( p->pParams->fRecord )
00323         pCut->Num0 = pCut0->Num0, pCut->Num1 = pCut1->Num0;
00324     // check containment
00325     if ( p->pParams->fFilter )
00326     {
00327         if ( Cut_CutFilterOne(p, pSuperList, pCut) )
00328 //        if ( Cut_CutFilterOneEqual(p, pSuperList, pCut) )
00329             return 0;
00330         if ( p->pParams->fSeq )
00331         {
00332             if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) )
00333                 return 0;
00334             if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) )
00335                 return 0;
00336         }
00337     }
00338 
00339     if ( p->pParams->fGlobal )
00340     {
00341         assert( p->vNodeAttrs != NULL );
00342         if ( Cut_CutFilterGlobal( p, pCut ) )
00343             return 0;
00344     }
00345 
00346     // compute the truth table
00347     if ( p->pParams->fTruth )
00348         Cut_TruthCompute( p, pCut, pCut0, pCut1, p->fCompl0, p->fCompl1 );
00349     // add to the list
00350     Cut_ListAdd( pSuperList, pCut );
00351     // return status (0 if okay; 1 if exceeded the limit)
00352     return ++p->nNodeCuts == p->pParams->nKeepMax;
00353 }

int Cut_ManMappingArea_rec ( Cut_Man_t *  p,
int  Node 
)

Function*************************************************************

Synopsis [Computes area after mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 534 of file cutNode.c.

00535 {
00536     Cut_Cut_t * pCut;
00537     int i, Counter;
00538     if ( p->vCutsMax == NULL )
00539         return 0;
00540     pCut = Vec_PtrEntry( p->vCutsMax, Node );
00541     if ( pCut == NULL || pCut->nLeaves == 1 )
00542         return 0;
00543     Counter = 0;
00544     for ( i = 0; i < (int)pCut->nLeaves; i++ )
00545         Counter += Cut_ManMappingArea_rec( p, pCut->pLeaves[i] );
00546     Vec_PtrWriteEntry( p->vCutsMax, Node, NULL );
00547     return 1 + Counter;
00548 }

Cut_Cut_t* Cut_NodeComputeCuts ( Cut_Man_t *  p,
int  Node,
int  Node0,
int  Node1,
int  fCompl0,
int  fCompl1,
int  fTriv,
int  TreeCode 
)

Function*************************************************************

Synopsis [Computes the cuts by merging cuts at two nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 366 of file cutNode.c.

00367 {
00368     Cut_List_t Super, * pSuper = &Super;
00369     Cut_Cut_t * pList, * pCut;
00370     int clk;
00371     // start the number of cuts at the node
00372     p->nNodes++;
00373     p->nNodeCuts = 0;
00374     // prepare information for recording
00375     if ( p->pParams->fRecord )
00376     {
00377         Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node0) );
00378         Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node1) );
00379     }
00380     // compute the cuts
00381 clk = clock();
00382     Cut_ListStart( pSuper );
00383     Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, Cut_NodeReadCutsNew(p, Node0), Cut_NodeReadCutsNew(p, Node1), fTriv, TreeCode );
00384     pList = Cut_ListFinish( pSuper );
00385 p->timeMerge += clock() - clk;
00386     // verify the result of cut computation
00387 //    Cut_CutListVerify( pList );
00388     // performing the recording
00389     if ( p->pParams->fRecord )
00390     {
00391         Vec_IntWriteEntry( p->vNodeStarts, Node, Vec_IntSize(p->vCutPairs) );
00392         Cut_ListForEachCut( pList, pCut )
00393             Vec_IntPush( p->vCutPairs, ((pCut->Num1 << 16) | pCut->Num0) );
00394         Vec_IntWriteEntry( p->vNodeCuts, Node, Vec_IntSize(p->vCutPairs) - Vec_IntEntry(p->vNodeStarts, Node) );
00395     }
00396     // check if the node is over the list
00397     if ( p->nNodeCuts == p->pParams->nKeepMax )
00398         p->nCutsLimit++;
00399     // set the list at the node
00400     Vec_PtrFillExtra( p->vCutsNew, Node + 1, NULL );
00401     assert( Cut_NodeReadCutsNew(p, Node) == NULL );
00403 //    pList->pNext = NULL;
00405     Cut_NodeWriteCutsNew( p, Node, pList );
00406     // filter the cuts
00407 //clk = clock();
00408 //    if ( p->pParams->fFilter )
00409 //        Cut_CutFilter( p, pList0 );
00410 //p->timeFilter += clock() - clk;
00411     // perform mapping of this node with these cuts
00412 clk = clock();
00413     if ( p->pParams->fMap && !p->pParams->fSeq )
00414     {
00415 //        int Delay1, Delay2;
00416 //        Delay1 = Cut_NodeMapping( p, pList, Node, Node0, Node1 );    
00417 //        Delay2 = Cut_NodeMapping2( p, pList, Node, Node0, Node1 );   
00418 //        assert( Delay1 >= Delay2 );
00419         Cut_NodeMapping( p, pList, Node, Node0, Node1 );
00420     }
00421 p->timeMap += clock() - clk;
00422     return pList;
00423 }

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 
)

Function*************************************************************

Synopsis [Computes the cuts by merging cuts at two nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 562 of file cutNode.c.

00563 {
00564     Cut_Cut_t * pStop0, * pStop1, * pTemp0, * pTemp1, * pStore0, * pStore1;
00565     int i, nCutsOld, Limit;
00566     // start with the elementary cut
00567     if ( fTriv ) 
00568     {
00569 //        printf( "Creating trivial cut %d.\n", Node );
00570         pTemp0 = Cut_CutCreateTriv( p, Node );
00571         Cut_ListAdd( pSuper, pTemp0 );
00572         p->nNodeCuts++;
00573     }
00574     // get the cut lists of children
00575     if ( pList0 == NULL || pList1 == NULL || (p->pParams->fLocal && TreeCode)  )
00576         return;
00577 
00578     // remember the old number of cuts
00579     nCutsOld = p->nCutsCur;
00580     Limit = p->pParams->nVarsMax;
00581     // get the simultation bit of the node
00582     p->fSimul = (fCompl0 ^ pList0->fSimul) & (fCompl1 ^ pList1->fSimul);
00583     // set temporary variables
00584     p->fCompl0 = fCompl0;
00585     p->fCompl1 = fCompl1;
00586     // if tree cuts are computed, make sure only the unit cuts propagate over the DAG nodes
00587     if ( TreeCode & 1 )
00588     {
00589         assert( pList0->nLeaves == 1 );
00590         pStore0 = pList0->pNext;
00591         pList0->pNext = NULL;
00592     }
00593     if ( TreeCode & 2 )
00594     {
00595         assert( pList1->nLeaves == 1 );
00596         pStore1 = pList1->pNext;
00597         pList1->pNext = NULL;
00598     }
00599     // find the point in the list where the max-var cuts begin
00600     Cut_ListForEachCut( pList0, pStop0 )
00601         if ( pStop0->nLeaves == (unsigned)Limit )
00602             break;
00603     Cut_ListForEachCut( pList1, pStop1 )
00604         if ( pStop1->nLeaves == (unsigned)Limit )
00605             break;
00606 
00607     // small by small
00608     Cut_ListForEachCutStop( pList0, pTemp0, pStop0 )
00609     Cut_ListForEachCutStop( pList1, pTemp1, pStop1 )
00610     {
00611         if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
00612             goto Quits;
00613     }
00614     // small by large
00615     Cut_ListForEachCutStop( pList0, pTemp0, pStop0 )
00616     Cut_ListForEachCut( pStop1, pTemp1 )
00617     {
00618         if ( (pTemp0->uSign & pTemp1->uSign) != pTemp0->uSign )
00619             continue;
00620         if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
00621             goto Quits;
00622     }
00623     // small by large
00624     Cut_ListForEachCutStop( pList1, pTemp1, pStop1 )
00625     Cut_ListForEachCut( pStop0, pTemp0 )
00626     {
00627         if ( (pTemp0->uSign & pTemp1->uSign) != pTemp1->uSign )
00628             continue;
00629         if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
00630             goto Quits;
00631     }
00632     // large by large
00633     Cut_ListForEachCut( pStop0, pTemp0 )
00634     Cut_ListForEachCut( pStop1, pTemp1 )
00635     {
00636         assert( pTemp0->nLeaves == (unsigned)Limit && pTemp1->nLeaves == (unsigned)Limit );
00637         if ( pTemp0->uSign != pTemp1->uSign )
00638             continue;
00639         for ( i = 0; i < Limit; i++ )
00640             if ( pTemp0->pLeaves[i] != pTemp1->pLeaves[i] )
00641                 break;
00642         if ( i < Limit )
00643             continue;
00644         if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
00645             goto Quits;
00646     } 
00647     if ( p->nNodeCuts == 0 )
00648         p->nNodesNoCuts++;
00649 Quits:
00650     if ( TreeCode & 1 )
00651         pList0->pNext = pStore0;
00652     if ( TreeCode & 2 )
00653         pList1->pNext = pStore1;
00654 }

int Cut_NodeMapping ( Cut_Man_t *  p,
Cut_Cut_t *  pCuts,
int  Node,
int  Node0,
int  Node1 
) [static]

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

] DECLARATIONS ///

Function*************************************************************

Synopsis [Returns optimum delay mapping using the largest cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 479 of file cutNode.c.

00480 {
00481     Cut_Cut_t * pCut0, * pCut1, * pCut;
00482     int Delay0, Delay1, Delay;
00483     // get the fanin cuts
00484     Delay0 = Vec_IntEntry( p->vDelays2, Node0 );
00485     Delay1 = Vec_IntEntry( p->vDelays2, Node1 );
00486     pCut0 = (Delay0 == 0) ? Vec_PtrEntry( p->vCutsNew, Node0 ) : Vec_PtrEntry( p->vCutsMax, Node0 );
00487     pCut1 = (Delay1 == 0) ? Vec_PtrEntry( p->vCutsNew, Node1 ) : Vec_PtrEntry( p->vCutsMax, Node1 );
00488     if ( Delay0 == Delay1 )
00489         Delay = (Delay0 == 0) ? Delay0 + 1: Delay0;
00490     else if ( Delay0 > Delay1 )
00491     {
00492         Delay = Delay0;
00493         pCut1 = Vec_PtrEntry( p->vCutsNew, Node1 );
00494         assert( pCut1->nLeaves == 1 );
00495     }
00496     else // if ( Delay0 < Delay1 )
00497     {
00498         Delay = Delay1;
00499         pCut0 = Vec_PtrEntry( p->vCutsNew, Node0 );
00500         assert( pCut0->nLeaves == 1 );
00501     }
00502     // merge the cuts
00503     if ( pCut0->nLeaves < pCut1->nLeaves )
00504         pCut  = Cut_CutMergeTwo( p, pCut1, pCut0 );
00505     else
00506         pCut  = Cut_CutMergeTwo( p, pCut0, pCut1 );
00507     if ( pCut == NULL )
00508     {
00509         Delay++;
00510         pCut = Cut_CutAlloc( p );
00511         pCut->nLeaves = 2;
00512         pCut->pLeaves[0] = Node0 < Node1 ? Node0 : Node1;
00513         pCut->pLeaves[1] = Node0 < Node1 ? Node1 : Node0;
00514     }
00515     assert( Delay > 0 );
00516     Vec_IntWriteEntry( p->vDelays2, Node, Delay );
00517     Vec_PtrWriteEntry( p->vCutsMax, Node, pCut );
00518     if ( p->nDelayMin < Delay )
00519         p->nDelayMin = Delay;
00520     return Delay;
00521 }

int Cut_NodeMapping2 ( Cut_Man_t *  p,
Cut_Cut_t *  pCuts,
int  Node,
int  Node0,
int  Node1 
) [static]

Function*************************************************************

Synopsis [Returns optimum delay mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 436 of file cutNode.c.

00437 {
00438     Cut_Cut_t * pCut;
00439     int DelayMin, DelayCur, i;
00440     if ( pCuts == NULL )
00441         p->nDelayMin = -1;
00442     if ( p->nDelayMin == -1 )
00443         return -1;
00444     DelayMin = 1000000;
00445     Cut_ListForEachCut( pCuts, pCut )
00446     {
00447         if ( pCut->nLeaves == 1 )
00448             continue;
00449         DelayCur = 0;
00450         for ( i = 0; i < (int)pCut->nLeaves; i++ )
00451             if ( DelayCur < Vec_IntEntry(p->vDelays, pCut->pLeaves[i]) )
00452                 DelayCur = Vec_IntEntry(p->vDelays, pCut->pLeaves[i]);
00453         if ( DelayMin > DelayCur )
00454             DelayMin = DelayCur;
00455     }
00456     if ( DelayMin == 1000000 )
00457     {
00458          p->nDelayMin = -1;
00459          return -1;
00460     }
00461     DelayMin++;
00462     Vec_IntWriteEntry( p->vDelays, Node, DelayMin );
00463     if ( p->nDelayMin < DelayMin )
00464         p->nDelayMin = DelayMin;
00465     return DelayMin;
00466 }

Cut_Cut_t* Cut_NodeUnionCuts ( Cut_Man_t *  p,
Vec_Int_t *  vNodes 
)

Function*************************************************************

Synopsis [Computes the cuts by unioning cuts at a choice node.]

Description []

SideEffects []

SeeAlso []

Definition at line 667 of file cutNode.c.

00668 {
00669     Cut_List_t Super, * pSuper = &Super;
00670     Cut_Cut_t * pList, * pListStart, * pCut, * pCut2, * pTop;
00671     int i, k, Node, Root, Limit = p->pParams->nVarsMax;
00672     int clk = clock();
00673 
00674     // start the new list
00675     Cut_ListStart( pSuper );
00676 
00677     // remember the root node to save the resulting cuts
00678     Root = Vec_IntEntry( vNodes, 0 );
00679     p->nNodeCuts = 1;
00680 
00681     // collect small cuts first
00682     Vec_PtrClear( p->vTemp );
00683     Vec_IntForEachEntry( vNodes, Node, i )
00684     {
00685         // get the cuts of this node
00686         pList = Cut_NodeReadCutsNew( p, Node );
00687         Cut_NodeWriteCutsNew( p, Node, NULL );
00688         assert( pList );
00689         // remember the starting point
00690         pListStart = pList->pNext;
00691         pList->pNext = NULL;
00692         // save or recycle the elementary cut
00693         if ( i == 0 )
00694             Cut_ListAdd( pSuper, pList ), pTop = pList;
00695         else
00696             Cut_CutRecycle( p, pList );
00697         // save all the cuts that are smaller than the limit
00698         Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
00699         {
00700             if ( pCut->nLeaves == (unsigned)Limit )
00701             {
00702                 Vec_PtrPush( p->vTemp, pCut );
00703                 break;
00704             }
00705             // check containment
00706             if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
00707                 continue;
00708             // set the complemented bit by comparing the first cut with the current cut
00709             pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
00710             pListStart = pCut->pNext;
00711             pCut->pNext = NULL;
00712             // add to the list
00713             Cut_ListAdd( pSuper, pCut );
00714             if ( ++p->nNodeCuts == p->pParams->nKeepMax )
00715             {
00716                 // recycle the rest of the cuts of this node
00717                 Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
00718                     Cut_CutRecycle( p, pCut );
00719                 // recycle all cuts of other nodes
00720                 Vec_IntForEachEntryStart( vNodes, Node, k, i+1 )
00721                     Cut_NodeFreeCuts( p, Node );
00722                 // recycle the saved cuts of other nodes
00723                 Vec_PtrForEachEntry( p->vTemp, pList, k )
00724                     Cut_ListForEachCutSafe( pList, pCut, pCut2 )
00725                         Cut_CutRecycle( p, pCut );
00726                 goto finish;
00727             }
00728         }
00729     } 
00730     // collect larger cuts next
00731     Vec_PtrForEachEntry( p->vTemp, pList, i )
00732     {
00733         Cut_ListForEachCutSafe( pList, pCut, pCut2 )
00734         {
00735             // check containment
00736             if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
00737                 continue;
00738             // set the complemented bit
00739             pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
00740             pListStart = pCut->pNext;
00741             pCut->pNext = NULL;
00742             // add to the list
00743             Cut_ListAdd( pSuper, pCut );
00744             if ( ++p->nNodeCuts == p->pParams->nKeepMax )
00745             {
00746                 // recycle the rest of the cuts
00747                 Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
00748                     Cut_CutRecycle( p, pCut );
00749                 // recycle the saved cuts of other nodes
00750                 Vec_PtrForEachEntryStart( p->vTemp, pList, k, i+1 )
00751                     Cut_ListForEachCutSafe( pList, pCut, pCut2 )
00752                         Cut_CutRecycle( p, pCut );
00753                 goto finish;
00754             }
00755         }
00756     }
00757 finish :
00758     // set the cuts at the node
00759     assert( Cut_NodeReadCutsNew(p, Root) == NULL );
00760     pList = Cut_ListFinish( pSuper );
00761     Cut_NodeWriteCutsNew( p, Root, pList );
00762 p->timeUnion += clock() - clk;
00763     // filter the cuts
00764 //clk = clock();
00765 //    if ( p->pParams->fFilter )
00766 //        Cut_CutFilter( p, pList );
00767 //p->timeFilter += clock() - clk;
00768     p->nNodes -= vNodes->nSize - 1;
00769     return pList;
00770 }

Cut_Cut_t* Cut_NodeUnionCutsSeq ( Cut_Man_t *  p,
Vec_Int_t *  vNodes,
int  CutSetNum,
int  fFirst 
)

Function*************************************************************

Synopsis [Computes the cuts by unioning cuts at a choice node.]

Description []

SideEffects []

SeeAlso []

Definition at line 783 of file cutNode.c.

00784 {
00785     Cut_List_t Super, * pSuper = &Super;
00786     Cut_Cut_t * pList, * pListStart, * pCut, * pCut2, * pTop;
00787     int i, k, Node, Root, Limit = p->pParams->nVarsMax;
00788     int clk = clock();
00789 
00790     // start the new list
00791     Cut_ListStart( pSuper );
00792 
00793     // remember the root node to save the resulting cuts
00794     Root = Vec_IntEntry( vNodes, 0 );
00795     p->nNodeCuts = 1;
00796 
00797     // store the original lists for comparison
00798     p->pCompareOld = Cut_NodeReadCutsOld( p, Root );
00799     p->pCompareNew = (CutSetNum >= 0)? Cut_NodeReadCutsNew( p, Root ) : NULL;
00800 
00801     // get the topmost cut
00802     pTop = NULL;
00803     if ( (pTop = Cut_NodeReadCutsOld( p, Root )) == NULL )
00804         pTop = Cut_NodeReadCutsNew( p, Root );
00805     assert( pTop != NULL );
00806 
00807     // collect small cuts first
00808     Vec_PtrClear( p->vTemp );
00809     Vec_IntForEachEntry( vNodes, Node, i )
00810     {
00811         // get the cuts of this node
00812         if ( i == 0 && CutSetNum >= 0 )
00813         {
00814             pList = Cut_NodeReadCutsTemp( p, CutSetNum );
00815             Cut_NodeWriteCutsTemp( p, CutSetNum, NULL );
00816         }
00817         else
00818         {
00819             pList = Cut_NodeReadCutsNew( p, Node );
00820             Cut_NodeWriteCutsNew( p, Node, NULL );
00821         }
00822         if ( pList == NULL )
00823             continue;
00824 
00825         // process the cuts
00826         if ( fFirst )
00827         {
00828             // remember the starting point
00829             pListStart = pList->pNext;
00830             pList->pNext = NULL;
00831             // save or recycle the elementary cut
00832             if ( i == 0 )
00833                 Cut_ListAdd( pSuper, pList );
00834             else
00835                 Cut_CutRecycle( p, pList );
00836         }
00837         else
00838             pListStart = pList;
00839 
00840         // save all the cuts that are smaller than the limit
00841         Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
00842         {
00843             if ( pCut->nLeaves == (unsigned)Limit )
00844             {
00845                 Vec_PtrPush( p->vTemp, pCut );
00846                 break;
00847             }
00848             // check containment
00849 //            if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
00850 //                continue;
00851             if ( p->pParams->fFilter )
00852             {
00853                 if ( Cut_CutFilterOne(p, pSuper, pCut) )
00854                     continue;
00855                 if ( p->pParams->fSeq )
00856                 {
00857                     if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) )
00858                         continue;
00859                     if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) )
00860                         continue;
00861                 }
00862             }
00863 
00864             // set the complemented bit by comparing the first cut with the current cut
00865             pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
00866             pListStart = pCut->pNext;
00867             pCut->pNext = NULL;
00868             // add to the list
00869             Cut_ListAdd( pSuper, pCut );
00870             if ( ++p->nNodeCuts == p->pParams->nKeepMax )
00871             {
00872                 // recycle the rest of the cuts of this node
00873                 Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
00874                     Cut_CutRecycle( p, pCut );
00875                 // recycle all cuts of other nodes
00876                 Vec_IntForEachEntryStart( vNodes, Node, k, i+1 )
00877                     Cut_NodeFreeCuts( p, Node );
00878                 // recycle the saved cuts of other nodes
00879                 Vec_PtrForEachEntry( p->vTemp, pList, k )
00880                     Cut_ListForEachCutSafe( pList, pCut, pCut2 )
00881                         Cut_CutRecycle( p, pCut );
00882                 goto finish;
00883             }
00884         }
00885     } 
00886     // collect larger cuts next
00887     Vec_PtrForEachEntry( p->vTemp, pList, i )
00888     {
00889         Cut_ListForEachCutSafe( pList, pCut, pCut2 )
00890         {
00891             // check containment
00892 //            if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
00893 //                continue;
00894             if ( p->pParams->fFilter )
00895             {
00896                 if ( Cut_CutFilterOne(p, pSuper, pCut) )
00897                     continue;
00898                 if ( p->pParams->fSeq )
00899                 {
00900                     if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) )
00901                         continue;
00902                     if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) )
00903                         continue;
00904                 }
00905             }
00906 
00907             // set the complemented bit
00908             pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
00909             pListStart   = pCut->pNext;
00910             pCut->pNext  = NULL;
00911             // add to the list
00912             Cut_ListAdd( pSuper, pCut );
00913             if ( ++p->nNodeCuts == p->pParams->nKeepMax )
00914             {
00915                 // recycle the rest of the cuts
00916                 Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
00917                     Cut_CutRecycle( p, pCut );
00918                 // recycle the saved cuts of other nodes
00919                 Vec_PtrForEachEntryStart( p->vTemp, pList, k, i+1 )
00920                     Cut_ListForEachCutSafe( pList, pCut, pCut2 )
00921                         Cut_CutRecycle( p, pCut );
00922                 goto finish;
00923             }
00924         }
00925     }
00926 finish :
00927     // set the cuts at the node
00928     pList = Cut_ListFinish( pSuper );
00929 
00930     // set the lists at the node
00931 //    assert( Cut_NodeReadCutsNew(p, Root) == NULL );
00932 //    Cut_NodeWriteCutsNew( p, Root, pList );
00933     if ( CutSetNum >= 0 )
00934     {
00935         assert( Cut_NodeReadCutsTemp(p, CutSetNum) == NULL );
00936         Cut_NodeWriteCutsTemp( p, CutSetNum, pList );
00937     }
00938     else
00939     {
00940         assert( Cut_NodeReadCutsNew(p, Root) == NULL );
00941         Cut_NodeWriteCutsNew( p, Root, pList );
00942     }
00943 
00944 p->timeUnion += clock() - clk;
00945     // filter the cuts
00946 //clk = clock();
00947 //    if ( p->pParams->fFilter )
00948 //        Cut_CutFilter( p, pList );
00949 //p->timeFilter += clock() - clk;
00950 //    if ( fFirst )
00951 //        p->nNodes -= vNodes->nSize - 1;
00952     return pList;
00953 }

Generated on Tue Jan 5 12:19:24 2010 for abc70930 by  doxygen 1.6.1