ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
Functions
aigCuts.c File Reference
#include "aig.h"
#include "bool/kit/kit.h"
Include dependency graph for aigCuts.c:

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START Aig_ManCut_t * Aig_ManCutStart (Aig_Man_t *pMan, int nCutsMax, int nLeafMax, int fTruth, int fVerbose)
 DECLARATIONS ///.
 
void Aig_ManCutStop (Aig_ManCut_t *p)
 
void Aig_CutPrint (Aig_Cut_t *pCut)
 
void Aig_ObjCutPrint (Aig_ManCut_t *p, Aig_Obj_t *pObj)
 
int Aig_ManCutCount (Aig_ManCut_t *p, int *pnCutsK)
 
unsigned * Aig_CutComputeTruth (Aig_ManCut_t *p, Aig_Cut_t *pCut, Aig_Cut_t *pCut0, Aig_Cut_t *pCut1, int fCompl0, int fCompl1)
 
int Aig_CutSupportMinimize (Aig_ManCut_t *p, Aig_Cut_t *pCut)
 
int Aig_CutFilter (Aig_ManCut_t *p, Aig_Obj_t *pObj, Aig_Cut_t *pCut)
 
int Aig_CutMerge (Aig_ManCut_t *p, Aig_Cut_t *pCut0, Aig_Cut_t *pCut1, Aig_Cut_t *pCut)
 
Aig_Cut_t * Aig_ObjPrepareCuts (Aig_ManCut_t *p, Aig_Obj_t *pObj, int fTriv)
 
void Aig_ObjComputeCuts (Aig_ManCut_t *p, Aig_Obj_t *pObj, int fTriv)
 
Aig_ManCut_t * Aig_ComputeCuts (Aig_Man_t *pAig, int nCutsMax, int nLeafMax, int fTruth, int fVerbose)
 

Function Documentation

◆ Aig_ComputeCuts()

Aig_ManCut_t * Aig_ComputeCuts ( Aig_Man_t * pAig,
int nCutsMax,
int nLeafMax,
int fTruth,
int fVerbose )

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

Synopsis [Computes the cuts for all nodes in the static AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 631 of file aigCuts.c.

632{
633 Aig_ManCut_t * p;
634 Aig_Obj_t * pObj;
635 int i;
636 abctime clk = Abc_Clock();
637 assert( pAig->pManCuts == NULL );
638 // start the manager
639 p = Aig_ManCutStart( pAig, nCutsMax, nLeafMax, fTruth, fVerbose );
640 // set elementary cuts at the PIs
641 Aig_ManForEachCi( pAig, pObj, i )
642 Aig_ObjPrepareCuts( p, pObj, 1 );
643 // process the nodes
644 Aig_ManForEachNode( pAig, pObj, i )
645 Aig_ObjComputeCuts( p, pObj, 1 );
646 // print stats
647 if ( fVerbose )
648 {
649 int nCuts, nCutsK;
650 nCuts = Aig_ManCutCount( p, &nCutsK );
651 printf( "Nodes = %6d. Total cuts = %6d. %d-input cuts = %6d.\n",
652 Aig_ManObjNum(pAig), nCuts, nLeafMax, nCutsK );
653 printf( "Cut size = %2d. Truth size = %2d. Total mem = %5.2f MB ",
654 p->nCutSize, 4*p->nTruthWords, 1.0*Aig_MmFixedReadMemUsage(p->pMemCuts)/(1<<20) );
655 ABC_PRT( "Runtime", Abc_Clock() - clk );
656/*
657 Aig_ManForEachNode( pAig, pObj, i )
658 if ( i % 300 == 0 )
659 Aig_ObjCutPrint( p, pObj );
660*/
661 }
662 // remember the cut manager
663 pAig->pManCuts = p;
664 return p;
665}
abctime
ABC_INT64_T abctime
Definition abc_global.h:332
ABC_PRT
#define ABC_PRT(a, t)
Definition abc_global.h:255
Aig_ObjComputeCuts
void Aig_ObjComputeCuts(Aig_ManCut_t *p, Aig_Obj_t *pObj, int fTriv)
Definition aigCuts.c:576
Aig_ManCutCount
int Aig_ManCutCount(Aig_ManCut_t *p, int *pnCutsK)
Definition aigCuts.c:147
Aig_ManCutStart
ABC_NAMESPACE_IMPL_START Aig_ManCut_t * Aig_ManCutStart(Aig_Man_t *pMan, int nCutsMax, int nLeafMax, int fTruth, int fVerbose)
DECLARATIONS ///.
Definition aigCuts.c:46
Aig_ObjPrepareCuts
Aig_Cut_t * Aig_ObjPrepareCuts(Aig_ManCut_t *p, Aig_Obj_t *pObj, int fTriv)
Definition aigCuts.c:536
Aig_MmFixedReadMemUsage
int Aig_MmFixedReadMemUsage(Aig_MmFixed_t *p)
Definition aigMem.c:271
Aig_ManForEachCi
#define Aig_ManForEachCi(p, pObj, i)
ITERATORS ///.
Definition aig.h:393
Aig_Obj_t
struct Aig_Obj_t_ Aig_Obj_t
Definition aig.h:51
Aig_ManForEachNode
#define Aig_ManForEachNode(p, pObj, i)
Definition aig.h:413
Aig_ManCut_t
struct Aig_ManCut_t_ Aig_ManCut_t
Definition aig.h:175
p
Cube * p
Definition exorList.c:222
assert
#define assert(ex)
Definition util_old.h:213
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Aig_CutComputeTruth()

unsigned * Aig_CutComputeTruth ( Aig_ManCut_t * p,
Aig_Cut_t * pCut,
Aig_Cut_t * pCut0,
Aig_Cut_t * pCut1,
int fCompl0,
int fCompl1 )

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

Synopsis [Performs truth table computation.]

Description []

SideEffects []

SeeAlso []

Definition at line 276 of file aigCuts.c.

277{
278 // permute the first table
279 if ( fCompl0 )
280 Kit_TruthNot( p->puTemp[0], Aig_CutTruth(pCut0), p->nLeafMax );
281 else
282 Kit_TruthCopy( p->puTemp[0], Aig_CutTruth(pCut0), p->nLeafMax );
283 Kit_TruthStretch( p->puTemp[2], p->puTemp[0], pCut0->nFanins, p->nLeafMax, Aig_CutTruthPhase(pCut, pCut0), 0 );
284 // permute the second table
285 if ( fCompl1 )
286 Kit_TruthNot( p->puTemp[1], Aig_CutTruth(pCut1), p->nLeafMax );
287 else
288 Kit_TruthCopy( p->puTemp[1], Aig_CutTruth(pCut1), p->nLeafMax );
289 Kit_TruthStretch( p->puTemp[3], p->puTemp[1], pCut1->nFanins, p->nLeafMax, Aig_CutTruthPhase(pCut, pCut1), 0 );
290 // produce the resulting table
291 Kit_TruthAnd( Aig_CutTruth(pCut), p->puTemp[2], p->puTemp[3], p->nLeafMax );
292// assert( pCut->nFanins >= Kit_TruthSupportSize( Aig_CutTruth(pCut), p->nLeafMax ) );
293 return Aig_CutTruth(pCut);
294}
Kit_TruthStretch
void Kit_TruthStretch(unsigned *pOut, unsigned *pIn, int nVars, int nVarsAll, unsigned Phase, int fReturnIn)
Definition kitTruth.c:166
Aig_Cut_t_::nFanins
char nFanins
Definition aig.h:187
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Aig_CutFilter()

int Aig_CutFilter ( Aig_ManCut_t * p,
Aig_Obj_t * pObj,
Aig_Cut_t * pCut )

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

Synopsis [Returns 1 if the cut is contained.]

Description []

SideEffects []

SeeAlso []

Definition at line 370 of file aigCuts.c.

371{
372 Aig_Cut_t * pTemp;
373 int i;
374 // go through the cuts of the node
375 Aig_ObjForEachCut( p, pObj, pTemp, i )
376 {
377 if ( pTemp->nFanins < 2 )
378 continue;
379 if ( pTemp == pCut )
380 continue;
381 if ( pTemp->nFanins > pCut->nFanins )
382 {
383 // skip the non-contained cuts
384 if ( (pTemp->uSign & pCut->uSign) != pCut->uSign )
385 continue;
386 // check containment seriously
387 if ( Aig_CutCheckDominance( pCut, pTemp ) )
388 {
389 // remove contained cut
390 pTemp->nFanins = 0;
391 }
392 }
393 else
394 {
395 // skip the non-contained cuts
396 if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign )
397 continue;
398 // check containment seriously
399 if ( Aig_CutCheckDominance( pTemp, pCut ) )
400 {
401 // remove the given
402 pCut->nFanins = 0;
403 return 1;
404 }
405 }
406 }
407 return 0;
408}
Aig_ObjForEachCut
#define Aig_ObjForEachCut(p, pObj, pCut, i)
Definition aig.h:218
Aig_Cut_t
struct Aig_Cut_t_ Aig_Cut_t
Definition aig.h:176
Aig_Cut_t_::uSign
unsigned uSign
Definition aig.h:183
Here is the caller graph for this function:

◆ Aig_CutMerge()

int Aig_CutMerge ( Aig_ManCut_t * p,
Aig_Cut_t * pCut0,
Aig_Cut_t * pCut1,
Aig_Cut_t * pCut )

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

Synopsis [Prepares the object for FPGA mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 507 of file aigCuts.c.

508{
509 assert( p->nLeafMax > 0 );
510 // merge the nodes
511 if ( pCut0->nFanins < pCut1->nFanins )
512 {
513 if ( !Aig_CutMergeOrdered( p, pCut1, pCut0, pCut ) )
514 return 0;
515 }
516 else
517 {
518 if ( !Aig_CutMergeOrdered( p, pCut0, pCut1, pCut ) )
519 return 0;
520 }
521 pCut->uSign = pCut0->uSign | pCut1->uSign;
522 return 1;
523}
Here is the caller graph for this function:

◆ Aig_CutPrint()

void Aig_CutPrint ( Aig_Cut_t * pCut)

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

Synopsis [Prints one cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 105 of file aigCuts.c.

106{
107 int i;
108 printf( "{" );
109 for ( i = 0; i < pCut->nFanins; i++ )
110 printf( " %d", pCut->pFanins[i] );
111 printf( " }\n" );
112}
Aig_Cut_t_::pFanins
int pFanins[0]
Definition aig.h:188
Here is the caller graph for this function:

◆ Aig_CutSupportMinimize()

int Aig_CutSupportMinimize ( Aig_ManCut_t * p,
Aig_Cut_t * pCut )

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

Synopsis [Performs support minimization for the truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 307 of file aigCuts.c.

308{
309 unsigned * pTruth;
310 int uSupp, nFansNew, i, k;
311 // get truth table
312 pTruth = Aig_CutTruth( pCut );
313 // get support
314 uSupp = Kit_TruthSupport( pTruth, p->nLeafMax );
315 // get the new support size
316 nFansNew = Kit_WordCountOnes( uSupp );
317 // check if there are redundant variables
318 if ( nFansNew == pCut->nFanins )
319 return nFansNew;
320 assert( nFansNew < pCut->nFanins );
321 // minimize support
322 Kit_TruthShrink( p->puTemp[0], pTruth, nFansNew, p->nLeafMax, uSupp, 1 );
323 for ( i = k = 0; i < pCut->nFanins; i++ )
324 if ( uSupp & (1 << i) )
325 pCut->pFanins[k++] = pCut->pFanins[i];
326 assert( k == nFansNew );
327 pCut->nFanins = nFansNew;
328// assert( nFansNew == Kit_TruthSupportSize( pTruth, p->nLeafMax ) );
329//Extra_PrintBinary( stdout, pTruth, (1<<p->nLeafMax) ); printf( "\n" );
330 return nFansNew;
331}
Kit_TruthSupport
unsigned Kit_TruthSupport(unsigned *pTruth, int nVars)
Definition kitTruth.c:346
Kit_TruthShrink
void Kit_TruthShrink(unsigned *pOut, unsigned *pIn, int nVars, int nVarsAll, unsigned Phase, int fReturnIn)
Definition kitTruth.c:200
Here is the call graph for this function:

◆ Aig_ManCutCount()

int Aig_ManCutCount ( Aig_ManCut_t * p,
int * pnCutsK )

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

Synopsis [Computes the total number of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 147 of file aigCuts.c.

148{
149 Aig_Cut_t * pCut;
150 Aig_Obj_t * pObj;
151 int i, k, nCuts = 0, nCutsK = 0;
152 Aig_ManForEachNode( p->pAig, pObj, i )
153 Aig_ObjForEachCut( p, pObj, pCut, k )
154 {
155 if ( pCut->nFanins == 0 )
156 continue;
157 nCuts++;
158 if ( pCut->nFanins == p->nLeafMax )
159 nCutsK++;
160 }
161 if ( pnCutsK )
162 *pnCutsK = nCutsK;
163 return nCuts;
164}
Here is the caller graph for this function:

◆ Aig_ManCutStart()

ABC_NAMESPACE_IMPL_START Aig_ManCut_t * Aig_ManCutStart ( Aig_Man_t * pMan,
int nCutsMax,
int nLeafMax,
int fTruth,
int fVerbose )

DECLARATIONS ///.

CFile****************************************************************

FileName [aigCuts.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [AIG package.]

Synopsis [Computation of K-feasible priority cuts.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id
aigCuts.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

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

Synopsis [Starts the cut sweeping manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 46 of file aigCuts.c.

47{
48 Aig_ManCut_t * p;
49 assert( nCutsMax >= 2 );
50 assert( nLeafMax <= 16 );
51 // allocate the fraiging manager
52 p = ABC_ALLOC( Aig_ManCut_t, 1 );
53 memset( p, 0, sizeof(Aig_ManCut_t) );
54 p->nCutsMax = nCutsMax;
55 p->nLeafMax = nLeafMax;
56 p->fTruth = fTruth;
57 p->fVerbose = fVerbose;
58 p->pAig = pMan;
59 p->pCuts = ABC_CALLOC( Aig_Cut_t *, Aig_ManObjNumMax(pMan) );
60 // allocate memory manager
61 p->nTruthWords = Abc_TruthWordNum(nLeafMax);
62 p->nCutSize = sizeof(Aig_Cut_t) + sizeof(int) * nLeafMax + fTruth * sizeof(unsigned) * p->nTruthWords;
63 p->pMemCuts = Aig_MmFixedStart( p->nCutSize * p->nCutsMax, 512 );
64 // room for temporary truth tables
65 if ( fTruth )
66 {
67 p->puTemp[0] = ABC_ALLOC( unsigned, 4 * p->nTruthWords );
68 p->puTemp[1] = p->puTemp[0] + p->nTruthWords;
69 p->puTemp[2] = p->puTemp[1] + p->nTruthWords;
70 p->puTemp[3] = p->puTemp[2] + p->nTruthWords;
71 }
72 return p;
73}
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition abc_global.h:264
ABC_CALLOC
#define ABC_CALLOC(type, num)
Definition abc_global.h:265
Aig_MmFixedStart
Aig_MmFixed_t * Aig_MmFixedStart(int nEntrySize, int nEntriesMax)
FUNCTION DEFINITIONS ///.
Definition aigMem.c:96
memset
char * memset()
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Aig_ManCutStop()

void Aig_ManCutStop ( Aig_ManCut_t * p)

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

Synopsis [Stops the fraiging manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 86 of file aigCuts.c.

87{
88 Aig_MmFixedStop( p->pMemCuts, 0 );
89 ABC_FREE( p->puTemp[0] );
90 ABC_FREE( p->pCuts );
91 ABC_FREE( p );
92}
ABC_FREE
#define ABC_FREE(obj)
Definition abc_global.h:267
Aig_MmFixedStop
void Aig_MmFixedStop(Aig_MmFixed_t *p, int fVerbose)
Definition aigMem.c:132
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Aig_ObjComputeCuts()

void Aig_ObjComputeCuts ( Aig_ManCut_t * p,
Aig_Obj_t * pObj,
int fTriv )

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

Synopsis [Derives cuts for one node and sweeps this node.]

Description []

SideEffects []

SeeAlso []

Definition at line 576 of file aigCuts.c.

577{
578 Aig_Cut_t * pCut0, * pCut1, * pCut, * pCutSet;
579 Aig_Obj_t * pFanin0 = Aig_ObjFanin0(pObj);
580 Aig_Obj_t * pFanin1 = Aig_ObjFanin1(pObj);
581 int i, k;
582 // the node is not processed yet
583 assert( Aig_ObjIsNode(pObj) );
584 assert( Aig_ObjCuts(p, pObj) == NULL );
585 // set up the first cut
586 pCutSet = Aig_ObjPrepareCuts( p, pObj, fTriv );
587 // compute pair-wise cut combinations while checking table
588 Aig_ObjForEachCut( p, pFanin0, pCut0, i )
589 if ( pCut0->nFanins > 0 )
590 Aig_ObjForEachCut( p, pFanin1, pCut1, k )
591 if ( pCut1->nFanins > 0 )
592 {
593 // make sure K-feasible cut exists
594 if ( Kit_WordCountOnes(pCut0->uSign | pCut1->uSign) > p->nLeafMax )
595 continue;
596 // get the next cut of this node
597 pCut = Aig_CutFindFree( p, pObj );
598 // assemble the new cut
599 if ( !Aig_CutMerge( p, pCut0, pCut1, pCut ) )
600 {
601 assert( pCut->nFanins == 0 );
602 continue;
603 }
604 // check containment
605 if ( Aig_CutFilter( p, pObj, pCut ) )
606 {
607 assert( pCut->nFanins == 0 );
608 continue;
609 }
610 // create its truth table
611 if ( p->fTruth )
612 Aig_CutComputeTruth( p, pCut, pCut0, pCut1, Aig_ObjFaninC0(pObj), Aig_ObjFaninC1(pObj) );
613 // assign the cost
614 pCut->Cost = Aig_CutFindCost( p, pCut );
615 assert( pCut->nFanins > 0 );
616 assert( pCut->Cost > 0 );
617 }
618}
Aig_CutMerge
int Aig_CutMerge(Aig_ManCut_t *p, Aig_Cut_t *pCut0, Aig_Cut_t *pCut1, Aig_Cut_t *pCut)
Definition aigCuts.c:507
Aig_CutComputeTruth
unsigned * Aig_CutComputeTruth(Aig_ManCut_t *p, Aig_Cut_t *pCut, Aig_Cut_t *pCut0, Aig_Cut_t *pCut1, int fCompl0, int fCompl1)
Definition aigCuts.c:276
Aig_CutFilter
int Aig_CutFilter(Aig_ManCut_t *p, Aig_Obj_t *pObj, Aig_Cut_t *pCut)
Definition aigCuts.c:370
Aig_Cut_t_::Cost
int Cost
Definition aig.h:182
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Aig_ObjCutPrint()

void Aig_ObjCutPrint ( Aig_ManCut_t * p,
Aig_Obj_t * pObj )

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

Synopsis [Prints one cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 125 of file aigCuts.c.

126{
127 Aig_Cut_t * pCut;
128 int i;
129 printf( "Cuts for node %d:\n", pObj->Id );
130 Aig_ObjForEachCut( p, pObj, pCut, i )
131 if ( pCut->nFanins )
132 Aig_CutPrint( pCut );
133// printf( "\n" );
134}
Aig_CutPrint
void Aig_CutPrint(Aig_Cut_t *pCut)
Definition aigCuts.c:105
Aig_Obj_t_::Id
int Id
Definition aig.h:85
Here is the call graph for this function:

◆ Aig_ObjPrepareCuts()

Aig_Cut_t * Aig_ObjPrepareCuts ( Aig_ManCut_t * p,
Aig_Obj_t * pObj,
int fTriv )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 536 of file aigCuts.c.

537{
538 Aig_Cut_t * pCutSet, * pCut;
539 int i;
540 // create the cutset of the node
541 pCutSet = (Aig_Cut_t *)Aig_MmFixedEntryFetch( p->pMemCuts );
542 Aig_ObjSetCuts( p, pObj, pCutSet );
543 Aig_ObjForEachCut( p, pObj, pCut, i )
544 {
545 pCut->nFanins = 0;
546 pCut->iNode = pObj->Id;
547 pCut->nCutSize = p->nCutSize;
548 pCut->nLeafMax = p->nLeafMax;
549 }
550 // add unit cut if needed
551 if ( fTriv )
552 {
553 pCut = pCutSet;
554 pCut->Cost = 0;
555 pCut->iNode = pObj->Id;
556 pCut->nFanins = 1;
557 pCut->pFanins[0] = pObj->Id;
558 pCut->uSign = Aig_ObjCutSign( pObj->Id );
559 if ( p->fTruth )
560 memset( Aig_CutTruth(pCut), 0xAA, sizeof(unsigned) * p->nTruthWords );
561 }
562 return pCutSet;
563}
Aig_MmFixedEntryFetch
char * Aig_MmFixedEntryFetch(Aig_MmFixed_t *p)
Definition aigMem.c:161
Aig_Cut_t_::nLeafMax
char nLeafMax
Definition aig.h:186
Aig_Cut_t_::iNode
int iNode
Definition aig.h:184
Aig_Cut_t_::nCutSize
short nCutSize
Definition aig.h:185
Here is the call graph for this function:
Here is the caller graph for this function: