abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
lpkCut.c File Reference
#include "lpkInt.h"
#include "bool/kit/cloud.h"

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START
CloudNode
Lpk_CutTruthBdd_rec (CloudManager *dd, Hop_Man_t *pMan, Hop_Obj_t *pObj, int nVars)
 DECLARATIONS ///. More...
 
CloudNodeLpk_CutTruthBdd (Lpk_Man_t *p, Lpk_Cut_t *pCut)
 
unsigned * Lpk_CutTruth_rec (Hop_Man_t *pMan, Hop_Obj_t *pObj, int nVars, Vec_Ptr_t *vTtNodes, int *piCount)
 
unsigned * Lpk_CutTruth (Lpk_Man_t *p, Lpk_Cut_t *pCut, int fInv)
 
void Lpk_NodeRecordImpact (Lpk_Man_t *p)
 
int Lpk_NodeCutsCheckDsd (Lpk_Man_t *p, Lpk_Cut_t *pCut)
 
static int Lpk_NodeCutsOneDominance (Lpk_Cut_t *pDom, Lpk_Cut_t *pCut)
 
int Lpk_NodeCutsOneFilter (Lpk_Cut_t *pCuts, int nCuts, Lpk_Cut_t *pCutNew)
 
void Lpk_NodePrintCut (Lpk_Man_t *p, Lpk_Cut_t *pCut, int fLeavesOnly)
 
void Lpk_NodeCutSignature (Lpk_Cut_t *pCut)
 
void Lpk_NodeCutsOne (Lpk_Man_t *p, Lpk_Cut_t *pCut, int Node)
 
int Lpk_NodeCuts (Lpk_Man_t *p)
 

Function Documentation

unsigned* Lpk_CutTruth ( Lpk_Man_t p,
Lpk_Cut_t pCut,
int  fInv 
)

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

Synopsis [Computes the truth able of one cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 175 of file lpkCut.c.

176 {
177  Hop_Man_t * pManHop = (Hop_Man_t *)p->pNtk->pManFunc;
178  Hop_Obj_t * pObjHop;
179  Abc_Obj_t * pObj = NULL; // Suppress "might be used uninitialized"
180  Abc_Obj_t * pFanin;
181  unsigned * pTruth = NULL; // Suppress "might be used uninitialized"
182  int i, k, iCount = 0;
183 // Lpk_NodePrintCut( p, pCut );
184  assert( pCut->nNodes > 0 );
185 
186  // initialize the leaves
187  Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i )
188  pObj->pCopy = (Abc_Obj_t *)Vec_PtrEntry( p->vTtElems, fInv? pCut->nLeaves-1-i : i );
189 
190  // construct truth table in the topological order
191  Lpk_CutForEachNodeReverse( p->pNtk, pCut, pObj, i )
192  {
193  // get the local AIG
194  pObjHop = Hop_Regular((Hop_Obj_t *)pObj->pData);
195  // clean the data field of the nodes in the AIG subgraph
196  Hop_ObjCleanData_rec( pObjHop );
197  // set the initial truth tables at the fanins
198  Abc_ObjForEachFanin( pObj, pFanin, k )
199  {
200  assert( ((unsigned)(ABC_PTRUINT_T)pFanin->pCopy) & 0xffff0000 );
201  Hop_ManPi( pManHop, k )->pData = pFanin->pCopy;
202  }
203  // compute the truth table of internal nodes
204  pTruth = Lpk_CutTruth_rec( pManHop, pObjHop, pCut->nLeaves, p->vTtNodes, &iCount );
205  if ( Hop_IsComplement((Hop_Obj_t *)pObj->pData) )
206  Kit_TruthNot( pTruth, pTruth, pCut->nLeaves );
207  // set the truth table at the node
208  pObj->pCopy = (Abc_Obj_t *)pTruth;
209  }
210 
211  // make sure direct truth table is stored elsewhere (assuming the first call for direct truth!!!)
212  if ( fInv == 0 )
213  {
214  pTruth = (unsigned *)Vec_PtrEntry( p->vTtNodes, iCount++ );
215  Kit_TruthCopy( pTruth, (unsigned *)(ABC_PTRUINT_T)pObj->pCopy, pCut->nLeaves );
216  }
217  assert( iCount <= Vec_PtrSize(p->vTtNodes) );
218  return pTruth;
219 }
unsigned * Lpk_CutTruth_rec(Hop_Man_t *pMan, Hop_Obj_t *pObj, int nVars, Vec_Ptr_t *vTtNodes, int *piCount)
Definition: lpkCut.c:138
#define Lpk_CutForEachNodeReverse(pNtk, pCut, pObj, i)
Definition: lpkInt.h:193
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Definition: hop.h:65
Vec_Ptr_t * vTtNodes
Definition: lpkInt.h:98
void Hop_ObjCleanData_rec(Hop_Obj_t *pObj)
Definition: hopUtil.c:88
static Hop_Obj_t * Hop_ManPi(Hop_Man_t *p, int i)
Definition: hop.h:134
Abc_Ntk_t * pNtk
Definition: lpkInt.h:74
void * pManFunc
Definition: abc.h:191
#define Lpk_CutForEachLeaf(pNtk, pCut, pObj, i)
MACRO DEFINITIONS ///.
Definition: lpkInt.h:189
static int Hop_IsComplement(Hop_Obj_t *p)
Definition: hop.h:129
unsigned nNodes
Definition: lpkInt.h:56
void * pData
Definition: hop.h:68
static void Kit_TruthNot(unsigned *pOut, unsigned *pIn, int nVars)
Definition: kit.h:373
static void * Vec_PtrEntry(Vec_Ptr_t *p, int i)
Definition: vecPtr.h:362
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
static void Kit_TruthCopy(unsigned *pOut, unsigned *pIn, int nVars)
Definition: kit.h:355
#define assert(ex)
Definition: util_old.h:213
static Hop_Obj_t * Hop_Regular(Hop_Obj_t *p)
Definition: hop.h:126
typedefABC_NAMESPACE_HEADER_START struct Hop_Man_t_ Hop_Man_t
INCLUDES ///.
Definition: hop.h:49
unsigned* Lpk_CutTruth_rec ( Hop_Man_t pMan,
Hop_Obj_t pObj,
int  nVars,
Vec_Ptr_t vTtNodes,
int *  piCount 
)

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

Synopsis [Computes the truth table of one cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 138 of file lpkCut.c.

139 {
140  unsigned * pTruth, * pTruth0, * pTruth1;
141  assert( !Hop_IsComplement(pObj) );
142  if ( pObj->pData )
143  {
144  assert( ((unsigned)(ABC_PTRUINT_T)pObj->pData) & 0xffff0000 );
145  return (unsigned *)pObj->pData;
146  }
147  // get the plan for a new truth table
148  pTruth = (unsigned *)Vec_PtrEntry( vTtNodes, (*piCount)++ );
149  if ( Hop_ObjIsConst1(pObj) )
150  Kit_TruthFill( pTruth, nVars );
151  else
152  {
153  assert( Hop_ObjIsAnd(pObj) );
154  // compute the truth tables of the fanins
155  pTruth0 = Lpk_CutTruth_rec( pMan, Hop_ObjFanin0(pObj), nVars, vTtNodes, piCount );
156  pTruth1 = Lpk_CutTruth_rec( pMan, Hop_ObjFanin1(pObj), nVars, vTtNodes, piCount );
157  // creat the truth table of the node
158  Kit_TruthAndPhase( pTruth, pTruth0, pTruth1, nVars, Hop_ObjFaninC0(pObj), Hop_ObjFaninC1(pObj) );
159  }
160  pObj->pData = pTruth;
161  return pTruth;
162 }
static void Kit_TruthAndPhase(unsigned *pOut, unsigned *pIn0, unsigned *pIn1, int nVars, int fCompl0, int fCompl1)
Definition: kit.h:409
static Hop_Obj_t * Hop_ObjFanin1(Hop_Obj_t *pObj)
Definition: hop.h:183
static void Kit_TruthFill(unsigned *pOut, int nVars)
Definition: kit.h:367
unsigned * Lpk_CutTruth_rec(Hop_Man_t *pMan, Hop_Obj_t *pObj, int nVars, Vec_Ptr_t *vTtNodes, int *piCount)
Definition: lpkCut.c:138
static int Hop_ObjFaninC1(Hop_Obj_t *pObj)
Definition: hop.h:181
static int Hop_ObjIsAnd(Hop_Obj_t *pObj)
Definition: hop.h:158
static int Hop_IsComplement(Hop_Obj_t *p)
Definition: hop.h:129
void * pData
Definition: hop.h:68
static Hop_Obj_t * Hop_ObjFanin0(Hop_Obj_t *pObj)
Definition: hop.h:182
static int Hop_ObjIsConst1(Hop_Obj_t *pObj)
Definition: hop.h:155
static void * Vec_PtrEntry(Vec_Ptr_t *p, int i)
Definition: vecPtr.h:362
static int Hop_ObjFaninC0(Hop_Obj_t *pObj)
Definition: hop.h:180
#define assert(ex)
Definition: util_old.h:213
CloudNode* Lpk_CutTruthBdd ( Lpk_Man_t p,
Lpk_Cut_t pCut 
)

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

Synopsis [Verifies that the factoring is correct.]

Description []

SideEffects []

SeeAlso []

Definition at line 84 of file lpkCut.c.

85 {
86  CloudManager * dd = p->pDsdMan->dd;
87  Hop_Man_t * pManHop = (Hop_Man_t *)p->pNtk->pManFunc;
88  Hop_Obj_t * pObjHop;
89  Abc_Obj_t * pObj, * pFanin;
90  CloudNode * pTruth = NULL; // Suppress "might be used uninitialized"
91  int i, k;
92 
93 // return NULL;
94 // Lpk_NodePrintCut( p, pCut );
95  // initialize the leaves
96  Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i )
97  pObj->pCopy = (Abc_Obj_t *)dd->vars[pCut->nLeaves-1-i];
98 
99  // construct truth table in the topological order
100  Lpk_CutForEachNodeReverse( p->pNtk, pCut, pObj, i )
101  {
102  // get the local AIG
103  pObjHop = Hop_Regular((Hop_Obj_t *)pObj->pData);
104  // clean the data field of the nodes in the AIG subgraph
105  Hop_ObjCleanData_rec( pObjHop );
106  // set the initial truth tables at the fanins
107  Abc_ObjForEachFanin( pObj, pFanin, k )
108  {
109  assert( ((unsigned)(ABC_PTRUINT_T)pFanin->pCopy) & 0xffff0000 );
110  Hop_ManPi( pManHop, k )->pData = pFanin->pCopy;
111  }
112  // compute the truth table of internal nodes
113  pTruth = Lpk_CutTruthBdd_rec( dd, pManHop, pObjHop, pCut->nLeaves );
114  if ( Hop_IsComplement((Hop_Obj_t *)pObj->pData) )
115  pTruth = Cloud_Not(pTruth);
116  // set the truth table at the node
117  pObj->pCopy = (Abc_Obj_t *)pTruth;
118 
119  }
120 
121 // Cloud_bddPrint( dd, pTruth );
122 // printf( "Bdd size = %d. Total nodes = %d.\n", Cloud_DagSize( dd, pTruth ), dd->nNodesCur-dd->nVars-1 );
123  return pTruth;
124 }
typedefABC_NAMESPACE_HEADER_START struct cloudManager CloudManager
Definition: cloud.h:52
unsigned nLeaves
Definition: lpkInt.h:55
#define Cloud_Not(p)
Definition: cloud.h:186
ABC_NAMESPACE_IMPL_START CloudNode * Lpk_CutTruthBdd_rec(CloudManager *dd, Hop_Man_t *pMan, Hop_Obj_t *pObj, int nVars)
DECLARATIONS ///.
Definition: lpkCut.c:46
#define Lpk_CutForEachNodeReverse(pNtk, pCut, pObj, i)
Definition: lpkInt.h:193
Definition: hop.h:65
void Hop_ObjCleanData_rec(Hop_Obj_t *pObj)
Definition: hopUtil.c:88
static Hop_Obj_t * Hop_ManPi(Hop_Man_t *p, int i)
Definition: hop.h:134
Abc_Ntk_t * pNtk
Definition: lpkInt.h:74
void * pManFunc
Definition: abc.h:191
#define Lpk_CutForEachLeaf(pNtk, pCut, pObj, i)
MACRO DEFINITIONS ///.
Definition: lpkInt.h:189
static int Hop_IsComplement(Hop_Obj_t *p)
Definition: hop.h:129
CloudManager * dd
Definition: kit.h:142
void * pData
Definition: hop.h:68
Kit_DsdMan_t * pDsdMan
Definition: lpkInt.h:106
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
#define assert(ex)
Definition: util_old.h:213
static Hop_Obj_t * Hop_Regular(Hop_Obj_t *p)
Definition: hop.h:126
typedefABC_NAMESPACE_HEADER_START struct Hop_Man_t_ Hop_Man_t
INCLUDES ///.
Definition: hop.h:49
ABC_NAMESPACE_IMPL_START CloudNode* Lpk_CutTruthBdd_rec ( CloudManager dd,
Hop_Man_t pMan,
Hop_Obj_t pObj,
int  nVars 
)

DECLARATIONS ///.

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

FileName [lpkCut.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Fast Boolean matching for LUT structures.]

Synopsis []

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

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

Synopsis [Computes the truth table of one cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 46 of file lpkCut.c.

47 {
48  CloudNode * pTruth, * pTruth0, * pTruth1;
49  assert( !Hop_IsComplement(pObj) );
50  if ( pObj->pData )
51  {
52  assert( ((unsigned)(ABC_PTRUINT_T)pObj->pData) & 0xffff0000 );
53  return (CloudNode *)pObj->pData;
54  }
55  // get the plan for a new truth table
56  if ( Hop_ObjIsConst1(pObj) )
57  pTruth = dd->one;
58  else
59  {
60  assert( Hop_ObjIsAnd(pObj) );
61  // compute the truth tables of the fanins
62  pTruth0 = Lpk_CutTruthBdd_rec( dd, pMan, Hop_ObjFanin0(pObj), nVars );
63  pTruth1 = Lpk_CutTruthBdd_rec( dd, pMan, Hop_ObjFanin1(pObj), nVars );
64  pTruth0 = Cloud_NotCond( pTruth0, Hop_ObjFaninC0(pObj) );
65  pTruth1 = Cloud_NotCond( pTruth1, Hop_ObjFaninC1(pObj) );
66  // creat the truth table of the node
67  pTruth = Cloud_bddAnd( dd, pTruth0, pTruth1 );
68  }
69  pObj->pData = pTruth;
70  return pTruth;
71 }
static Hop_Obj_t * Hop_ObjFanin1(Hop_Obj_t *pObj)
Definition: hop.h:183
#define Cloud_NotCond(p, c)
Definition: cloud.h:187
ABC_NAMESPACE_IMPL_START CloudNode * Lpk_CutTruthBdd_rec(CloudManager *dd, Hop_Man_t *pMan, Hop_Obj_t *pObj, int nVars)
DECLARATIONS ///.
Definition: lpkCut.c:46
static int Hop_ObjFaninC1(Hop_Obj_t *pObj)
Definition: hop.h:181
CloudNode * Cloud_bddAnd(CloudManager *dd, CloudNode *f, CloudNode *g)
Definition: cloud.c:489
static int Hop_ObjIsAnd(Hop_Obj_t *pObj)
Definition: hop.h:158
static int Hop_IsComplement(Hop_Obj_t *p)
Definition: hop.h:129
void * pData
Definition: hop.h:68
static Hop_Obj_t * Hop_ObjFanin0(Hop_Obj_t *pObj)
Definition: hop.h:182
static int Hop_ObjIsConst1(Hop_Obj_t *pObj)
Definition: hop.h:155
static int Hop_ObjFaninC0(Hop_Obj_t *pObj)
Definition: hop.h:180
#define assert(ex)
Definition: util_old.h:213
int Lpk_NodeCuts ( Lpk_Man_t p)

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

Synopsis [Computes the set of all cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 588 of file lpkCut.c.

589 {
590  Lpk_Cut_t * pCut, * pCut2;
591  int i, k, Temp, nMffc, fChanges;
592 
593  // mark the MFFC of the node with the current trav ID
594  nMffc = p->nMffc = Abc_NodeMffcLabel( p->pObj );
595  assert( nMffc > 0 );
596  if ( nMffc == 1 )
597  return 0;
598 
599  // initialize the first cut
600  pCut = p->pCuts; p->nCuts = 1;
601  pCut->nNodes = 0;
602  pCut->nNodesDup = 0;
603  pCut->nLeaves = 1;
604  pCut->pLeaves[0] = p->pObj->Id;
605  // assign the signature
606  Lpk_NodeCutSignature( pCut );
607 
608  // perform the cut computation
609  for ( i = 0; i < p->nCuts; i++ )
610  {
611  pCut = p->pCuts + i;
612  if ( pCut->nLeaves == 0 )
613  continue;
614 
615  // try to expand the fanins of this cut
616  for ( k = 0; k < (int)pCut->nLeaves; k++ )
617  {
618  // create a new cut
619  Lpk_NodeCutsOne( p, pCut, pCut->pLeaves[k] );
620  // quit if the number of cuts has exceeded the limit
621  if ( p->nCuts == LPK_CUTS_MAX )
622  break;
623  }
624  if ( p->nCuts == LPK_CUTS_MAX )
625  break;
626  }
627  if ( p->nCuts == LPK_CUTS_MAX )
628  p->nNodesOver++;
629 
630  // record the impact of this node
631  if ( p->pPars->fSatur )
633 
634  // compress the cuts by removing empty ones, those with negative Weight, and decomposable ones
635  p->nEvals = 0;
636  for ( i = 0; i < p->nCuts; i++ )
637  {
638  pCut = p->pCuts + i;
639  if ( pCut->nLeaves < 2 )
640  continue;
641  // compute the minimum number of LUTs needed to implement this cut
642  // V = N * (K-1) + 1 ~~~~~ N = Ceiling[(V-1)/(K-1)] = (V-1)/(K-1) + [(V-1)%(K-1) > 0]
643  pCut->nLuts = Lpk_LutNumLuts( pCut->nLeaves, p->pPars->nLutSize );
644 // pCut->Weight = (float)1.0 * (pCut->nNodes - pCut->nNodesDup - 1) / pCut->nLuts; //p->pPars->nLutsMax;
645  pCut->Weight = (float)1.0 * (pCut->nNodes - pCut->nNodesDup) / pCut->nLuts; //p->pPars->nLutsMax;
646  if ( pCut->Weight <= 1.001 )
647 // if ( pCut->Weight <= 0.999 )
648  continue;
649  pCut->fHasDsd = Lpk_NodeCutsCheckDsd( p, pCut );
650  if ( pCut->fHasDsd )
651  continue;
652  p->pEvals[p->nEvals++] = i;
653  }
654  if ( p->nEvals == 0 )
655  return 0;
656 
657  // sort the cuts by Weight
658  do {
659  fChanges = 0;
660  for ( i = 0; i < p->nEvals - 1; i++ )
661  {
662  pCut = p->pCuts + p->pEvals[i];
663  pCut2 = p->pCuts + p->pEvals[i+1];
664  if ( pCut->Weight >= pCut2->Weight - 0.001 )
665  continue;
666  Temp = p->pEvals[i];
667  p->pEvals[i] = p->pEvals[i+1];
668  p->pEvals[i+1] = Temp;
669  fChanges = 1;
670  }
671  } while ( fChanges );
672 /*
673  for ( i = 0; i < p->nEvals; i++ )
674  {
675  pCut = p->pCuts + p->pEvals[i];
676  printf( "Cut %3d : W = %5.2f.\n", i, pCut->Weight );
677  }
678  printf( "\n" );
679 */
680  return 1;
681 }
int pLeaves[LPK_SIZE_MAX]
Definition: lpkInt.h:65
Lpk_Par_t * pPars
Definition: lpkInt.h:72
float Weight
Definition: lpkInt.h:63
int nCuts
Definition: lpkInt.h:78
unsigned nLeaves
Definition: lpkInt.h:55
Abc_Obj_t * pObj
Definition: lpkInt.h:75
int nNodesOver
Definition: lpkInt.h:109
void Lpk_NodeCutSignature(Lpk_Cut_t *pCut)
Definition: lpkCut.c:453
Lpk_Cut_t pCuts[LPK_CUTS_MAX]
Definition: lpkInt.h:81
void Lpk_NodeCutsOne(Lpk_Man_t *p, Lpk_Cut_t *pCut, int Node)
Definition: lpkCut.c:477
unsigned fHasDsd
Definition: lpkInt.h:60
int pEvals[LPK_CUTS_MAX]
Definition: lpkInt.h:82
unsigned nNodes
Definition: lpkInt.h:56
ABC_DLL int Abc_NodeMffcLabel(Abc_Obj_t *pNode)
Definition: abcRefs.c:437
int nMffc
Definition: lpkInt.h:77
int nEvals
Definition: lpkInt.h:80
unsigned nNodesDup
Definition: lpkInt.h:57
int Id
Definition: abc.h:132
int Lpk_NodeCutsCheckDsd(Lpk_Man_t *p, Lpk_Cut_t *pCut)
Definition: lpkCut.c:275
unsigned nLuts
Definition: lpkInt.h:58
static int Lpk_LutNumLuts(int nVarsMax, int nLutK)
Definition: lpkInt.h:178
#define assert(ex)
Definition: util_old.h:213
#define LPK_CUTS_MAX
Definition: lpkInt.h:48
void Lpk_NodeRecordImpact(Lpk_Man_t *p)
Definition: lpkCut.c:233
int Lpk_NodeCutsCheckDsd ( Lpk_Man_t p,
Lpk_Cut_t pCut 
)

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

Synopsis [Returns 1 if the cut has structural DSD.]

Description []

SideEffects []

SeeAlso []

Definition at line 275 of file lpkCut.c.

276 {
277  Abc_Obj_t * pObj, * pFanin;
278  int i, k, nCands, fLeavesOnly, RetValue;
279  assert( pCut->nLeaves > 0 );
280  // clear ref counters
281  memset( p->pRefs, 0, sizeof(int) * pCut->nLeaves );
282  // mark cut leaves
283  Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i )
284  {
285  assert( pObj->fMarkA == 0 );
286  pObj->fMarkA = 1;
287  pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)i;
288  }
289  // ref leaves pointed from the internal nodes
290  nCands = 0;
291  Lpk_CutForEachNode( p->pNtk, pCut, pObj, i )
292  {
293  fLeavesOnly = 1;
294  Abc_ObjForEachFanin( pObj, pFanin, k )
295  if ( pFanin->fMarkA )
296  p->pRefs[(int)(ABC_PTRUINT_T)pFanin->pCopy]++;
297  else
298  fLeavesOnly = 0;
299  if ( fLeavesOnly )
300  p->pCands[nCands++] = pObj->Id;
301  }
302  // look at the nodes that only point to the leaves
303  RetValue = 0;
304  for ( i = 0; i < nCands; i++ )
305  {
306  pObj = Abc_NtkObj( p->pNtk, p->pCands[i] );
307  Abc_ObjForEachFanin( pObj, pFanin, k )
308  {
309  assert( pFanin->fMarkA == 1 );
310  if ( p->pRefs[(int)(ABC_PTRUINT_T)pFanin->pCopy] > 1 )
311  break;
312  }
313  if ( k == Abc_ObjFaninNum(pObj) )
314  {
315  RetValue = 1;
316  break;
317  }
318  }
319  // unmark cut leaves
320  Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i )
321  pObj->fMarkA = 0;
322  return RetValue;
323 }
char * memset()
unsigned fMarkA
Definition: abc.h:134
unsigned nLeaves
Definition: lpkInt.h:55
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
static Abc_Obj_t * Abc_NtkObj(Abc_Ntk_t *pNtk, int i)
Definition: abc.h:314
for(p=first;p->value< newval;p=p->next)
Abc_Ntk_t * pNtk
Definition: lpkInt.h:74
Abc_Obj_t * pCopy
Definition: abc.h:148
#define Lpk_CutForEachLeaf(pNtk, pCut, pObj, i)
MACRO DEFINITIONS ///.
Definition: lpkInt.h:189
if(last==0)
Definition: sparse_int.h:34
else
Definition: sparse_int.h:55
int pCands[LPK_SIZE_MAX]
Definition: lpkInt.h:94
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
int pRefs[LPK_SIZE_MAX]
Definition: lpkInt.h:93
#define Lpk_CutForEachNode(pNtk, pCut, pObj, i)
Definition: lpkInt.h:191
#define assert(ex)
Definition: util_old.h:213
void Lpk_NodeCutSignature ( Lpk_Cut_t pCut)

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

Synopsis [Set the cut signature.]

Description []

SideEffects []

SeeAlso []

Definition at line 453 of file lpkCut.c.

454 {
455  unsigned i;
456  pCut->uSign[0] = pCut->uSign[1] = 0;
457  for ( i = 0; i < pCut->nLeaves; i++ )
458  {
459  pCut->uSign[(pCut->pLeaves[i] & 32) > 0] |= (1 << (pCut->pLeaves[i] & 31));
460  if ( i != pCut->nLeaves - 1 )
461  assert( pCut->pLeaves[i] < pCut->pLeaves[i+1] );
462  }
463 }
int pLeaves[LPK_SIZE_MAX]
Definition: lpkInt.h:65
unsigned uSign[2]
Definition: lpkInt.h:62
unsigned nLeaves
Definition: lpkInt.h:55
#define assert(ex)
Definition: util_old.h:213
void Lpk_NodeCutsOne ( Lpk_Man_t p,
Lpk_Cut_t pCut,
int  Node 
)

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

Synopsis [Computes the set of all cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 477 of file lpkCut.c.

478 {
479  Lpk_Cut_t * pCutNew;
480  Abc_Obj_t * pObj, * pFanin;
481  int i, k, j, nLeavesNew;
482 /*
483  printf( "Exploring cut " );
484  Lpk_NodePrintCut( p, pCut, 1 );
485  printf( "with node %d\n", Node );
486 */
487  // check if the cut can stand adding one more internal node
488  if ( pCut->nNodes == LPK_SIZE_MAX )
489  return;
490 
491  // if the node is a PI, quit
492  pObj = Abc_NtkObj( p->pNtk, Node );
493  if ( Abc_ObjIsCi(pObj) )
494  return;
495  assert( Abc_ObjIsNode(pObj) );
496 // assert( Abc_ObjFaninNum(pObj) <= p->pPars->nLutSize );
497 
498  // if the node is not in the MFFC, check the limit
499  if ( !Abc_NodeIsTravIdCurrent(pObj) )
500  {
501  if ( (int)pCut->nNodesDup == p->pPars->nLutsOver )
502  return;
503  assert( (int)pCut->nNodesDup < p->pPars->nLutsOver );
504  }
505 
506  // check the possibility of adding this node using the signature
507  nLeavesNew = pCut->nLeaves - 1;
508  Abc_ObjForEachFanin( pObj, pFanin, i )
509  {
510  if ( (pCut->uSign[(pFanin->Id & 32) > 0] & (1 << (pFanin->Id & 31))) )
511  continue;
512  if ( ++nLeavesNew > p->pPars->nVarsMax )
513  return;
514  }
515 
516  // initialize the set of leaves to the nodes in the cut
517  assert( p->nCuts < LPK_CUTS_MAX );
518  pCutNew = p->pCuts + p->nCuts;
519  pCutNew->nLeaves = 0;
520  for ( i = 0; i < (int)pCut->nLeaves; i++ )
521  if ( pCut->pLeaves[i] != Node )
522  pCutNew->pLeaves[pCutNew->nLeaves++] = pCut->pLeaves[i];
523 
524  // add new nodes
525  Abc_ObjForEachFanin( pObj, pFanin, i )
526  {
527  // find the place where this node belongs
528  for ( k = 0; k < (int)pCutNew->nLeaves; k++ )
529  if ( pCutNew->pLeaves[k] >= pFanin->Id )
530  break;
531  if ( k < (int)pCutNew->nLeaves && pCutNew->pLeaves[k] == pFanin->Id )
532  continue;
533  // check if there is room
534  if ( (int)pCutNew->nLeaves == p->pPars->nVarsMax )
535  return;
536  // move all the nodes
537  for ( j = pCutNew->nLeaves; j > k; j-- )
538  pCutNew->pLeaves[j] = pCutNew->pLeaves[j-1];
539  pCutNew->pLeaves[k] = pFanin->Id;
540  pCutNew->nLeaves++;
541  assert( pCutNew->nLeaves <= LPK_SIZE_MAX );
542 
543  }
544  // skip the contained cuts
545  Lpk_NodeCutSignature( pCutNew );
546  if ( Lpk_NodeCutsOneFilter( p->pCuts, p->nCuts, pCutNew ) )
547  return;
548 
549  // update the set of internal nodes
550  assert( pCut->nNodes < LPK_SIZE_MAX );
551  memcpy( pCutNew->pNodes, pCut->pNodes, pCut->nNodes * sizeof(int) );
552  pCutNew->nNodes = pCut->nNodes;
553  pCutNew->nNodesDup = pCut->nNodesDup;
554 
555  // check if the node is already there
556  // if so, move the node to be the last
557  for ( i = 0; i < (int)pCutNew->nNodes; i++ )
558  if ( pCutNew->pNodes[i] == Node )
559  {
560  for ( k = i; k < (int)pCutNew->nNodes - 1; k++ )
561  pCutNew->pNodes[k] = pCutNew->pNodes[k+1];
562  pCutNew->pNodes[k] = Node;
563  break;
564  }
565  if ( i == (int)pCutNew->nNodes ) // new node
566  {
567  pCutNew->pNodes[ pCutNew->nNodes++ ] = Node;
568  pCutNew->nNodesDup += !Abc_NodeIsTravIdCurrent(pObj);
569  }
570  // the number of nodes does not exceed MFFC plus duplications
571  assert( pCutNew->nNodes <= p->nMffc + pCutNew->nNodesDup );
572  // add the cut to storage
573  assert( p->nCuts < LPK_CUTS_MAX );
574  p->nCuts++;
575 }
int pLeaves[LPK_SIZE_MAX]
Definition: lpkInt.h:65
unsigned uSign[2]
Definition: lpkInt.h:62
Lpk_Par_t * pPars
Definition: lpkInt.h:72
static int Abc_ObjIsCi(Abc_Obj_t *pObj)
Definition: abc.h:351
int nCuts
Definition: lpkInt.h:78
unsigned nLeaves
Definition: lpkInt.h:55
char * memcpy()
static Abc_Obj_t * Abc_NtkObj(Abc_Ntk_t *pNtk, int i)
Definition: abc.h:314
void Lpk_NodeCutSignature(Lpk_Cut_t *pCut)
Definition: lpkCut.c:453
Abc_Ntk_t * pNtk
Definition: lpkInt.h:74
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Lpk_Cut_t pCuts[LPK_CUTS_MAX]
Definition: lpkInt.h:81
unsigned nNodes
Definition: lpkInt.h:56
int Lpk_NodeCutsOneFilter(Lpk_Cut_t *pCuts, int nCuts, Lpk_Cut_t *pCutNew)
Definition: lpkCut.c:362
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
int nMffc
Definition: lpkInt.h:77
unsigned nNodesDup
Definition: lpkInt.h:57
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
int Id
Definition: abc.h:132
int pNodes[LPK_SIZE_MAX]
Definition: lpkInt.h:66
#define assert(ex)
Definition: util_old.h:213
#define LPK_CUTS_MAX
Definition: lpkInt.h:48
#define LPK_SIZE_MAX
INCLUDES ///.
Definition: lpkInt.h:47
static int Lpk_NodeCutsOneDominance ( Lpk_Cut_t pDom,
Lpk_Cut_t pCut 
)
inlinestatic

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 336 of file lpkCut.c.

337 {
338  int i, k;
339  for ( i = 0; i < (int)pDom->nLeaves; i++ )
340  {
341  for ( k = 0; k < (int)pCut->nLeaves; k++ )
342  if ( pDom->pLeaves[i] == pCut->pLeaves[k] )
343  break;
344  if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut
345  return 0;
346  }
347  // every node in pDom is contained in pCut
348  return 1;
349 }
int pLeaves[LPK_SIZE_MAX]
Definition: lpkInt.h:65
unsigned nLeaves
Definition: lpkInt.h:55
int Lpk_NodeCutsOneFilter ( Lpk_Cut_t pCuts,
int  nCuts,
Lpk_Cut_t pCutNew 
)

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

Synopsis [Check if the cut exists.]

Description [Returns 1 if the cut exists.]

SideEffects []

SeeAlso []

Definition at line 362 of file lpkCut.c.

363 {
364  Lpk_Cut_t * pCut;
365  int i, k;
366  assert( pCutNew->uSign[0] || pCutNew->uSign[1] );
367  // try to find the cut
368  for ( i = 0; i < nCuts; i++ )
369  {
370  pCut = pCuts + i;
371  if ( pCut->nLeaves == 0 )
372  continue;
373  if ( pCut->nLeaves == pCutNew->nLeaves )
374  {
375  if ( pCut->uSign[0] == pCutNew->uSign[0] && pCut->uSign[1] == pCutNew->uSign[1] )
376  {
377  for ( k = 0; k < (int)pCutNew->nLeaves; k++ )
378  if ( pCut->pLeaves[k] != pCutNew->pLeaves[k] )
379  break;
380  if ( k == (int)pCutNew->nLeaves )
381  return 1;
382  }
383  continue;
384  }
385  if ( pCut->nLeaves < pCutNew->nLeaves )
386  {
387  // skip the non-contained cuts
388  if ( (pCut->uSign[0] & pCutNew->uSign[0]) != pCut->uSign[0] )
389  continue;
390  if ( (pCut->uSign[1] & pCutNew->uSign[1]) != pCut->uSign[1] )
391  continue;
392  // check containment seriously
393  if ( Lpk_NodeCutsOneDominance( pCut, pCutNew ) )
394  return 1;
395  continue;
396  }
397  // check potential containment of other cut
398 
399  // skip the non-contained cuts
400  if ( (pCut->uSign[0] & pCutNew->uSign[0]) != pCutNew->uSign[0] )
401  continue;
402  if ( (pCut->uSign[1] & pCutNew->uSign[1]) != pCutNew->uSign[1] )
403  continue;
404  // check containment seriously
405  if ( Lpk_NodeCutsOneDominance( pCutNew, pCut ) )
406  pCut->nLeaves = 0; // removed
407  }
408  return 0;
409 }
int pLeaves[LPK_SIZE_MAX]
Definition: lpkInt.h:65
unsigned uSign[2]
Definition: lpkInt.h:62
unsigned nLeaves
Definition: lpkInt.h:55
static int Lpk_NodeCutsOneDominance(Lpk_Cut_t *pDom, Lpk_Cut_t *pCut)
Definition: lpkCut.c:336
#define assert(ex)
Definition: util_old.h:213
void Lpk_NodePrintCut ( Lpk_Man_t p,
Lpk_Cut_t pCut,
int  fLeavesOnly 
)

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

Synopsis [Prints the given cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 422 of file lpkCut.c.

423 {
424  Abc_Obj_t * pObj;
425  int i;
426  if ( !fLeavesOnly )
427  printf( "LEAVES:\n" );
428  Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i )
429  printf( "%d,", pObj->Id );
430  if ( !fLeavesOnly )
431  {
432  printf( "\nNODES:\n" );
433  Lpk_CutForEachNode( p->pNtk, pCut, pObj, i )
434  {
435  printf( "%d,", pObj->Id );
436  assert( Abc_ObjIsNode(pObj) );
437  }
438  printf( "\n" );
439  }
440 }
Abc_Ntk_t * pNtk
Definition: lpkInt.h:74
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
#define Lpk_CutForEachLeaf(pNtk, pCut, pObj, i)
MACRO DEFINITIONS ///.
Definition: lpkInt.h:189
if(last==0)
Definition: sparse_int.h:34
int Id
Definition: abc.h:132
#define Lpk_CutForEachNode(pNtk, pCut, pObj, i)
Definition: lpkInt.h:191
#define assert(ex)
Definition: util_old.h:213
void Lpk_NodeRecordImpact ( Lpk_Man_t p)

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

Synopsis [Returns 1 if at least one entry has changed.]

Description []

SideEffects []

SeeAlso []

Definition at line 233 of file lpkCut.c.

234 {
235  Lpk_Cut_t * pCut;
236  Vec_Ptr_t * vNodes = Vec_VecEntry( p->vVisited, p->pObj->Id );
237  Abc_Obj_t * pNode;
238  int i, k;
239  // collect the nodes that impact the given node
240  Vec_PtrClear( vNodes );
241  for ( i = 0; i < p->nCuts; i++ )
242  {
243  pCut = p->pCuts + i;
244  for ( k = 0; k < (int)pCut->nLeaves; k++ )
245  {
246  pNode = Abc_NtkObj( p->pNtk, pCut->pLeaves[k] );
247  if ( pNode->fMarkC )
248  continue;
249  pNode->fMarkC = 1;
250  Vec_PtrPush( vNodes, (void *)(ABC_PTRUINT_T)pNode->Id );
251  Vec_PtrPush( vNodes, (void *)(ABC_PTRUINT_T)Abc_ObjFanoutNum(pNode) );
252  }
253  }
254  // clear the marks
255  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
256  {
257  pNode = Abc_NtkObj( p->pNtk, (int)(ABC_PTRUINT_T)pNode );
258  pNode->fMarkC = 0;
259  i++;
260  }
261 //printf( "%d ", Vec_PtrSize(vNodes) );
262 }
int pLeaves[LPK_SIZE_MAX]
Definition: lpkInt.h:65
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Vec_Vec_t * vVisited
Definition: lpkInt.h:84
int nCuts
Definition: lpkInt.h:78
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
unsigned nLeaves
Definition: lpkInt.h:55
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
static Abc_Obj_t * Abc_NtkObj(Abc_Ntk_t *pNtk, int i)
Definition: abc.h:314
Abc_Obj_t * pObj
Definition: lpkInt.h:75
Abc_Ntk_t * pNtk
Definition: lpkInt.h:74
Lpk_Cut_t pCuts[LPK_CUTS_MAX]
Definition: lpkInt.h:81
unsigned fMarkC
Definition: abc.h:136
int Id
Definition: abc.h:132
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
static Vec_Ptr_t * Vec_VecEntry(Vec_Vec_t *p, int i)
Definition: vecVec.h:271
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55