abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
lpkCore.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [lpkCore.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Fast Boolean matching for LUT structures.]
8 
9  Synopsis []
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - April 28, 2007.]
16 
17  Revision [$Id: lpkCore.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "lpkInt.h"
22 #include "bool/kit/cloud.h"
23 #include "base/main/main.h"
24 
26 
27 
28 ////////////////////////////////////////////////////////////////////////
29 /// DECLARATIONS ///
30 ////////////////////////////////////////////////////////////////////////
31 
32 ////////////////////////////////////////////////////////////////////////
33 /// FUNCTION DEFINITIONS ///
34 ////////////////////////////////////////////////////////////////////////
35 
36 /**Function*************************************************************
37 
38  Synopsis [Prepares the mapping manager.]
39 
40  Description []
41 
42  SideEffects []
43 
44  SeeAlso []
45 
46 ***********************************************************************/
48 {
49  If_Par_t * pPars;
50  assert( p->pIfMan == NULL );
51  // set defaults
52  pPars = ABC_ALLOC( If_Par_t, 1 );
53  memset( pPars, 0, sizeof(If_Par_t) );
54  // user-controlable paramters
55  pPars->nLutSize = p->pPars->nLutSize;
56  pPars->nCutsMax = 16;
57  pPars->nFlowIters = 0; // 1
58  pPars->nAreaIters = 0; // 1
59  pPars->DelayTarget = -1;
60  pPars->Epsilon = (float)0.005;
61  pPars->fPreprocess = 0;
62  pPars->fArea = 1;
63  pPars->fFancy = 0;
64  pPars->fExpRed = 0; //
65  pPars->fLatchPaths = 0;
66  pPars->fVerbose = 0;
67  // internal parameters
68  pPars->fTruth = 1;
69  pPars->fUsePerm = 0;
70  pPars->nLatchesCi = 0;
71  pPars->nLatchesCo = 0;
72  pPars->pLutLib = NULL; // Abc_FrameReadLibLut();
73  pPars->pTimesArr = NULL;
74  pPars->pTimesArr = NULL;
75  pPars->fUseBdds = 0;
76  pPars->fUseSops = 0;
77  pPars->fUseCnfs = 0;
78  pPars->fUseMv = 0;
79  // start the mapping manager and set its parameters
80  p->pIfMan = If_ManStart( pPars );
81  If_ManSetupSetAll( p->pIfMan, 1000 );
82  p->pIfMan->pPars->pTimesArr = ABC_ALLOC( float, 32 );
83 }
84 
85 /**Function*************************************************************
86 
87  Synopsis [Returns 1 if at least one entry has changed.]
88 
89  Description []
90 
91  SideEffects []
92 
93  SeeAlso []
94 
95 ***********************************************************************/
96 int Lpk_NodeHasChanged( Lpk_Man_t * p, int iNode )
97 {
98  Vec_Ptr_t * vNodes;
99  Abc_Obj_t * pTemp;
100  int i;
101  vNodes = Vec_VecEntry( p->vVisited, iNode );
102  if ( Vec_PtrSize(vNodes) == 0 )
103  return 1;
104  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pTemp, i )
105  {
106  // check if the node has changed
107  pTemp = Abc_NtkObj( p->pNtk, (int)(ABC_PTRUINT_T)pTemp );
108  if ( pTemp == NULL )
109  return 1;
110  // check if the number of fanouts has changed
111 // if ( Abc_ObjFanoutNum(pTemp) != (int)Vec_PtrEntry(vNodes, i+1) )
112 // return 1;
113  i++;
114  }
115  return 0;
116 }
117 
118 /**Function*************************************************************
119 
120  Synopsis [Prepares the mapping manager.]
121 
122  Description []
123 
124  SideEffects []
125 
126  SeeAlso []
127 
128 ***********************************************************************/
130 {
131  extern Abc_Obj_t * Abc_NodeFromIf_rec( Abc_Ntk_t * pNtkNew, If_Man_t * pIfMan, If_Obj_t * pIfObj, Vec_Int_t * vCover );
132  Kit_DsdObj_t * pRoot;
133  If_Obj_t * pDriver, * ppLeaves[16];
134  Abc_Obj_t * pLeaf, * pObjNew;
135  int nGain, i;
136  abctime clk;
137  int nNodesBef;
138 // int nOldShared;
139 
140  // check special cases
141  pRoot = Kit_DsdNtkRoot( pNtk );
142  if ( pRoot->Type == KIT_DSD_CONST1 )
143  {
144  if ( Abc_LitIsCompl(pNtk->Root) )
145  pObjNew = Abc_NtkCreateNodeConst0( p->pNtk );
146  else
147  pObjNew = Abc_NtkCreateNodeConst1( p->pNtk );
148  Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels );
149  p->nGainTotal += pCut->nNodes - pCut->nNodesDup;
150  return 1;
151  }
152  if ( pRoot->Type == KIT_DSD_VAR )
153  {
154  pObjNew = Abc_NtkObj( p->pNtk, pCut->pLeaves[ Abc_Lit2Var(pRoot->pFans[0]) ] );
155  if ( Abc_LitIsCompl(pNtk->Root) ^ Abc_LitIsCompl(pRoot->pFans[0]) )
156  pObjNew = Abc_NtkCreateNodeInv( p->pNtk, pObjNew );
157  Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels );
158  p->nGainTotal += pCut->nNodes - pCut->nNodesDup;
159  return 1;
160  }
161  assert( pRoot->Type == KIT_DSD_AND || pRoot->Type == KIT_DSD_XOR || pRoot->Type == KIT_DSD_PRIME );
162 
163  // start the mapping manager
164  if ( p->pIfMan == NULL )
165  Lpk_IfManStart( p );
166 
167  // prepare the mapping manager
168  If_ManRestart( p->pIfMan );
169  // create the PI variables
170  for ( i = 0; i < p->pPars->nVarsMax; i++ )
171  ppLeaves[i] = If_ManCreateCi( p->pIfMan );
172  // set the arrival times
173  Lpk_CutForEachLeaf( p->pNtk, pCut, pLeaf, i )
174  p->pIfMan->pPars->pTimesArr[i] = (float)pLeaf->Level;
175  // prepare the PI cuts
177  // create the internal nodes
178  p->fCalledOnce = 0;
179  p->nCalledSRed = 0;
180  pDriver = Lpk_MapTree_rec( p, pNtk, ppLeaves, pNtk->Root, NULL );
181  if ( pDriver == NULL )
182  return 0;
183  // create the PO node
184  If_ManCreateCo( p->pIfMan, If_Regular(pDriver) );
185 
186  // perform mapping
187  p->pIfMan->pPars->fAreaOnly = 1;
188 clk = Abc_Clock();
190 p->timeMap += Abc_Clock() - clk;
191 
192  // compute the gain in area
193  nGain = pCut->nNodes - pCut->nNodesDup - (int)p->pIfMan->AreaGlo;
194  if ( p->pPars->fVeryVerbose )
195  printf( " Mffc = %2d. Mapped = %2d. Gain = %3d. Depth increase = %d. SReds = %d.\n",
196  pCut->nNodes - pCut->nNodesDup, (int)p->pIfMan->AreaGlo, nGain, (int)p->pIfMan->RequiredGlo - (int)p->pObj->Level, p->nCalledSRed );
197 
198  // quit if there is no gain
199  if ( !(nGain > 0 || (p->pPars->fZeroCost && nGain == 0)) )
200  return 0;
201 
202  // quit if depth increases too much
203  if ( (int)p->pIfMan->RequiredGlo > Abc_ObjRequiredLevel(p->pObj) )
204  return 0;
205 
206  // perform replacement
207  p->nGainTotal += nGain;
208  p->nChanges++;
209  if ( p->nCalledSRed )
210  p->nBenefited++;
211 
212  nNodesBef = Abc_NtkNodeNum(p->pNtk);
213  // prepare the mapping manager
216  // set the PIs of the cut
217  Lpk_CutForEachLeaf( p->pNtk, pCut, pLeaf, i )
218  If_ObjSetCopy( If_ManCi(p->pIfMan, i), pLeaf );
219  // get the area of mapping
220  pObjNew = Abc_NodeFromIf_rec( p->pNtk, p->pIfMan, If_Regular(pDriver), p->vCover );
221  pObjNew->pData = Hop_NotCond( (Hop_Obj_t *)pObjNew->pData, If_IsComplement(pDriver) );
222  // perform replacement
223  Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels );
224 //printf( "%3d : %d-%d=%d(%d) \n", p->nChanges, nNodesBef, Abc_NtkNodeNum(p->pNtk), nNodesBef-Abc_NtkNodeNum(p->pNtk), nGain );
225  return 1;
226 }
227 
228 /**Function*************************************************************
229 
230  Synopsis [Performs resynthesis for one node.]
231 
232  Description []
233 
234  SideEffects []
235 
236  SeeAlso []
237 
238 ***********************************************************************/
240 {
241 // static int Count = 0;
242  Kit_DsdNtk_t * pDsdNtk;
243  Lpk_Cut_t * pCut;
244  unsigned * pTruth;
245  int i, k, nSuppSize, nCutNodes, RetValue;
246  abctime clk;
247 
248  // compute the cuts
249 clk = Abc_Clock();
250  if ( !Lpk_NodeCuts( p ) )
251  {
252 p->timeCuts += Abc_Clock() - clk;
253  return 0;
254  }
255 p->timeCuts += Abc_Clock() - clk;
256 
257 //return 0;
258 
259  if ( p->pPars->fVeryVerbose )
260  printf( "Node %5d : Mffc size = %5d. Cuts = %5d.\n", p->pObj->Id, p->nMffc, p->nEvals );
261  // try the good cuts
262  p->nCutsTotal += p->nCuts;
263  p->nCutsUseful += p->nEvals;
264  for ( i = 0; i < p->nEvals; i++ )
265  {
266  // get the cut
267  pCut = p->pCuts + p->pEvals[i];
268  if ( p->pPars->fFirst && i == 1 )
269  break;
270 
271  // skip bad cuts
272 // printf( "Mffc size = %d. ", Abc_NodeMffcLabel(p->pObj) );
273  for ( k = 0; k < (int)pCut->nLeaves; k++ )
274  Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize++;
275  nCutNodes = Abc_NodeMffcLabel(p->pObj);
276 // printf( "Mffc with cut = %d. ", nCutNodes );
277  for ( k = 0; k < (int)pCut->nLeaves; k++ )
278  Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize--;
279 // printf( "Mffc cut = %d. ", (int)pCut->nNodes - (int)pCut->nNodesDup );
280 // printf( "\n" );
281  if ( nCutNodes != (int)pCut->nNodes - (int)pCut->nNodesDup )
282  continue;
283 
284  // compute the truth table
285 clk = Abc_Clock();
286  pTruth = Lpk_CutTruth( p, pCut, 0 );
287  nSuppSize = Extra_TruthSupportSize(pTruth, pCut->nLeaves);
288 p->timeTruth += Abc_Clock() - clk;
289 
290  pDsdNtk = Kit_DsdDecompose( pTruth, pCut->nLeaves );
291 // Kit_DsdVerify( pDsdNtk, pTruth, pCut->nLeaves );
292  // skip 16-input non-DSD because ISOP will not work
293  if ( Kit_DsdNtkRoot(pDsdNtk)->nFans == 16 )
294  {
295  Kit_DsdNtkFree( pDsdNtk );
296  continue;
297  }
298 
299  // if DSD has nodes that require splitting to fit them into LUTs
300  // we can skip those cuts that cannot lead to improvement
301  // (a full DSD network requires V = Nmin * (K-1) + 1 for improvement)
302  if ( Kit_DsdNonDsdSizeMax(pDsdNtk) > p->pPars->nLutSize &&
303  nSuppSize >= ((int)pCut->nNodes - (int)pCut->nNodesDup - 1) * (p->pPars->nLutSize - 1) + 1 )
304  {
305  Kit_DsdNtkFree( pDsdNtk );
306  continue;
307  }
308 
309  if ( p->pPars->fVeryVerbose )
310  {
311 // char * pFileName;
312  printf( " C%02d: L= %2d/%2d V= %2d/%d N= %d W= %4.2f ",
313  i, pCut->nLeaves, nSuppSize, pCut->nNodes, pCut->nNodesDup, pCut->nLuts, pCut->Weight );
314  Kit_DsdPrint( stdout, pDsdNtk );
315  Kit_DsdPrintFromTruth( pTruth, pCut->nLeaves );
316 // pFileName = Kit_TruthDumpToFile( pTruth, pCut->nLeaves, Count++ );
317 // printf( "Saved truth table in file \"%s\".\n", pFileName );
318  }
319 
320  // update the network
321 clk = Abc_Clock();
322  RetValue = Lpk_ExploreCut( p, pCut, pDsdNtk );
323 p->timeEval += Abc_Clock() - clk;
324  Kit_DsdNtkFree( pDsdNtk );
325  if ( RetValue )
326  break;
327  }
328  return 1;
329 }
330 
331 
332 /**Function*************************************************************
333 
334  Synopsis [Computes supports of the cofactors of the function.]
335 
336  Description [This procedure should be called after Lpk_CutTruth(p,pCut,0)]
337 
338  SideEffects []
339 
340  SeeAlso []
341 
342 ***********************************************************************/
343 void Lpk_ComputeSupports( Lpk_Man_t * p, Lpk_Cut_t * pCut, unsigned * pTruth )
344 {
345  unsigned * pTruthInv;
346  int RetValue1, RetValue2;
347  pTruthInv = Lpk_CutTruth( p, pCut, 1 );
348  RetValue1 = Kit_CreateCloudFromTruth( p->pDsdMan->dd, pTruth, pCut->nLeaves, p->vBddDir );
349  RetValue2 = Kit_CreateCloudFromTruth( p->pDsdMan->dd, pTruthInv, pCut->nLeaves, p->vBddInv );
350  if ( RetValue1 && RetValue2 && Vec_IntSize(p->vBddDir) > 1 && Vec_IntSize(p->vBddInv) > 1 )
351  Kit_TruthCofSupports( p->vBddDir, p->vBddInv, pCut->nLeaves, p->vMemory, p->puSupps );
352  else
353  p->puSupps[0] = p->puSupps[1] = 0;
354 }
355 
356 
357 /**Function*************************************************************
358 
359  Synopsis [Performs resynthesis for one node.]
360 
361  Description []
362 
363  SideEffects []
364 
365  SeeAlso []
366 
367 ***********************************************************************/
369 {
370 // static int Count = 0;
371  Abc_Obj_t * pObjNew, * pLeaf;
372  Lpk_Cut_t * pCut;
373  unsigned * pTruth;
374  int nNodesBef, nNodesAft, nCutNodes;
375  int i, k;
376  abctime clk;
377  int Required = Abc_ObjRequiredLevel(p->pObj);
378 // CloudNode * pFun2;//, * pFun1;
379 
380  // compute the cuts
381 clk = Abc_Clock();
382  if ( !Lpk_NodeCuts( p ) )
383  {
384 p->timeCuts += Abc_Clock() - clk;
385  return 0;
386  }
387 p->timeCuts += Abc_Clock() - clk;
388 
389  if ( p->pPars->fVeryVerbose )
390  printf( "Node %5d : Mffc size = %5d. Cuts = %5d. Level = %2d. Req = %2d.\n",
391  p->pObj->Id, p->nMffc, p->nEvals, p->pObj->Level, Required );
392  // try the good cuts
393  p->nCutsTotal += p->nCuts;
394  p->nCutsUseful += p->nEvals;
395  for ( i = 0; i < p->nEvals; i++ )
396  {
397  // get the cut
398  pCut = p->pCuts + p->pEvals[i];
399  if ( p->pPars->fFirst && i == 1 )
400  break;
401 // if ( pCut->Weight < 1.05 )
402 // continue;
403 
404  // skip bad cuts
405 // printf( "Mffc size = %d. ", Abc_NodeMffcLabel(p->pObj) );
406  for ( k = 0; k < (int)pCut->nLeaves; k++ )
407  Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize++;
408  nCutNodes = Abc_NodeMffcLabel(p->pObj);
409 // printf( "Mffc with cut = %d. ", nCutNodes );
410  for ( k = 0; k < (int)pCut->nLeaves; k++ )
411  Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize--;
412 // printf( "Mffc cut = %d. ", (int)pCut->nNodes - (int)pCut->nNodesDup );
413 // printf( "\n" );
414  if ( nCutNodes != (int)pCut->nNodes - (int)pCut->nNodesDup )
415  continue;
416 
417  // collect nodes into the array
418  Vec_PtrClear( p->vLeaves );
419  for ( k = 0; k < (int)pCut->nLeaves; k++ )
420  Vec_PtrPush( p->vLeaves, Abc_NtkObj(p->pNtk, pCut->pLeaves[k]) );
421 
422  // compute the truth table
423 clk = Abc_Clock();
424  pTruth = Lpk_CutTruth( p, pCut, 0 );
425 p->timeTruth += Abc_Clock() - clk;
426 clk = Abc_Clock();
427  Lpk_ComputeSupports( p, pCut, pTruth );
428 p->timeSupps += Abc_Clock() - clk;
429 //clk = Abc_Clock();
430 // pFun1 = Lpk_CutTruthBdd( p, pCut );
431 //p->timeTruth2 += Abc_Clock() - clk;
432 /*
433 clk = Abc_Clock();
434  Cloud_Restart( p->pDsdMan->dd );
435  pFun2 = Kit_TruthToCloud( p->pDsdMan->dd, pTruth, pCut->nLeaves );
436  RetValue = Kit_CreateCloud( p->pDsdMan->dd, pFun2, p->vBddNodes );
437 p->timeTruth3 += Abc_Clock() - clk;
438 */
439 // if ( pFun1 != pFun2 )
440 // printf( "Truth tables do not agree!\n" );
441 // else
442 // printf( "Fine!\n" );
443 
444  if ( p->pPars->fVeryVerbose )
445  {
446 // char * pFileName;
447  int nSuppSize = Extra_TruthSupportSize( pTruth, pCut->nLeaves );
448  printf( " C%02d: L= %2d/%2d V= %2d/%d N= %d W= %4.2f ",
449  i, pCut->nLeaves, nSuppSize, pCut->nNodes, pCut->nNodesDup, pCut->nLuts, pCut->Weight );
450  Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pLeaf, k )
451  printf( "%c=%d ", 'a'+k, Abc_ObjLevel(pLeaf) );
452  printf( "\n" );
453  Kit_DsdPrintFromTruth( pTruth, pCut->nLeaves );
454 // pFileName = Kit_TruthDumpToFile( pTruth, pCut->nLeaves, Count++ );
455 // printf( "Saved truth table in file \"%s\".\n", pFileName );
456  }
457 
458  // update the network
459  nNodesBef = Abc_NtkNodeNum(p->pNtk);
460 clk = Abc_Clock();
461  pObjNew = Lpk_Decompose( p, p->pNtk, p->vLeaves, pTruth, p->puSupps, p->pPars->nLutSize,
462  (int)pCut->nNodes - (int)pCut->nNodesDup - 1 + (int)(p->pPars->fZeroCost > 0), Required );
463 p->timeEval += Abc_Clock() - clk;
464  nNodesAft = Abc_NtkNodeNum(p->pNtk);
465 
466  // perform replacement
467  if ( pObjNew )
468  {
469  int nGain = (int)pCut->nNodes - (int)pCut->nNodesDup - (nNodesAft - nNodesBef);
470  assert( nGain >= 1 - p->pPars->fZeroCost );
471  assert( Abc_ObjLevel(pObjNew) <= Required );
472 /*
473  if ( nGain <= 0 )
474  {
475  int x = 0;
476  }
477  if ( Abc_ObjLevel(pObjNew) > Required )
478  {
479  int x = 0;
480  }
481 */
482  p->nGainTotal += nGain;
483  p->nChanges++;
484  if ( p->pPars->fVeryVerbose )
485  printf( "Performed resynthesis: Gain = %2d. Level = %2d. Req = %2d.\n", nGain, Abc_ObjLevel(pObjNew), Required );
486  Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels );
487 //printf( "%3d : %d-%d=%d(%d) \n", p->nChanges, nNodesBef, Abc_NtkNodeNum(p->pNtk), nNodesBef-Abc_NtkNodeNum(p->pNtk), nGain );
488  break;
489  }
490  }
491  return 1;
492 }
493 
494 /**Function*************************************************************
495 
496  Synopsis [Performs resynthesis for one network.]
497 
498  Description []
499 
500  SideEffects []
501 
502  SeeAlso []
503 
504 ***********************************************************************/
505 int Lpk_Resynthesize( Abc_Ntk_t * pNtk, Lpk_Par_t * pPars )
506 {
507  ProgressBar * pProgress = NULL; // Suppress "might be used uninitialized"
508  Lpk_Man_t * p;
509  Abc_Obj_t * pObj;
510  double Delta;
511 // int * pnFanouts, nObjMax;
512  int i, Iter, nNodes, nNodesPrev;
513  abctime clk = Abc_Clock();
514  assert( Abc_NtkIsLogic(pNtk) );
515 
516  // sweep dangling nodes as a preprocessing step
517  Abc_NtkSweep( pNtk, 0 );
518 
519  // get the number of inputs
520  if ( Abc_FrameReadLibLut() )
521  pPars->nLutSize = ((If_LibLut_t *)Abc_FrameReadLibLut())->LutMax;
522  else
523  pPars->nLutSize = Abc_NtkGetFaninMax( pNtk );
524  if ( pPars->nLutSize > 6 )
525  pPars->nLutSize = 6;
526  if ( pPars->nLutSize < 3 )
527  pPars->nLutSize = 3;
528  // adjust the number of crossbars based on LUT size
529  if ( pPars->nVarsShared > pPars->nLutSize - 2 )
530  pPars->nVarsShared = pPars->nLutSize - 2;
531  // get the max number of LUTs tried
532  pPars->nVarsMax = pPars->nLutsMax * (pPars->nLutSize - 1) + 1; // V = N * (K-1) + 1
533  while ( pPars->nVarsMax > 16 )
534  {
535  pPars->nLutsMax--;
536  pPars->nVarsMax = pPars->nLutsMax * (pPars->nLutSize - 1) + 1;
537 
538  }
539  if ( pPars->fVerbose )
540  {
541  printf( "Resynthesis for %d %d-LUTs with %d non-MFFC LUTs, %d crossbars, and %d-input cuts.\n",
542  pPars->nLutsMax, pPars->nLutSize, pPars->nLutsOver, pPars->nVarsShared, pPars->nVarsMax );
543  }
544 
545 
546  // convert into the AIG
547  if ( !Abc_NtkToAig(pNtk) )
548  {
549  fprintf( stdout, "Converting to BDD has failed.\n" );
550  return 0;
551  }
552  assert( Abc_NtkHasAig(pNtk) );
553 
554  // set the number of levels
555  Abc_NtkLevel( pNtk );
556  Abc_NtkStartReverseLevels( pNtk, pPars->nGrowthLevel );
557 
558  // start the manager
559  p = Lpk_ManStart( pPars );
560  p->pNtk = pNtk;
561  p->nNodesTotal = Abc_NtkNodeNum(pNtk);
562  p->vLevels = Vec_VecStart( pNtk->LevelMax );
563  if ( p->pPars->fSatur )
564  p->vVisited = Vec_VecStart( 0 );
565  if ( pPars->fVerbose )
566  {
568  p->nTotalNodes = Abc_NtkNodeNum(pNtk);
569  }
570 /*
571  // save the number of fanouts of all objects
572  nObjMax = Abc_NtkObjNumMax( pNtk );
573  pnFanouts = ABC_ALLOC( int, nObjMax );
574  memset( pnFanouts, 0, sizeof(int) * nObjMax );
575  Abc_NtkForEachObj( pNtk, pObj, i )
576  pnFanouts[pObj->Id] = Abc_ObjFanoutNum(pObj);
577 */
578 
579  // iterate over the network
580  nNodesPrev = p->nNodesTotal;
581  for ( Iter = 1; ; Iter++ )
582  {
583  // expand storage for changed nodes
584  if ( p->pPars->fSatur )
585  Vec_VecExpand( p->vVisited, Abc_NtkObjNumMax(pNtk) + 1 );
586 
587  // consider all nodes
588  nNodes = Abc_NtkObjNumMax(pNtk);
589  if ( !pPars->fVeryVerbose )
590  pProgress = Extra_ProgressBarStart( stdout, nNodes );
591  Abc_NtkForEachNode( pNtk, pObj, i )
592  {
593  // skip all except the final node
594  if ( pPars->fFirst )
595  {
596  if ( !Abc_ObjIsCo(Abc_ObjFanout0(pObj)) )
597  continue;
598  }
599  if ( i >= nNodes )
600  break;
601  if ( !pPars->fVeryVerbose )
602  Extra_ProgressBarUpdate( pProgress, i, NULL );
603  // skip the nodes that did not change
604  if ( p->pPars->fSatur && !Lpk_NodeHasChanged(p, pObj->Id) )
605  continue;
606  // resynthesize
607  p->pObj = pObj;
608  if ( p->pPars->fOldAlgo )
610  else
612  }
613  if ( !pPars->fVeryVerbose )
614  Extra_ProgressBarStop( pProgress );
615 
616  // check the increase
617  Delta = 100.00 * (nNodesPrev - Abc_NtkNodeNum(pNtk)) / p->nNodesTotal;
618  if ( Delta < 0.05 )
619  break;
620  nNodesPrev = Abc_NtkNodeNum(pNtk);
621  if ( !p->pPars->fSatur )
622  break;
623 
624  if ( pPars->fFirst )
625  break;
626  }
627  Abc_NtkStopReverseLevels( pNtk );
628 /*
629  // report the fanout changes
630  Abc_NtkForEachObj( pNtk, pObj, i )
631  {
632  if ( i >= nObjMax )
633  continue;
634  if ( Abc_ObjFanoutNum(pObj) - pnFanouts[pObj->Id] == 0 )
635  continue;
636  printf( "%d ", Abc_ObjFanoutNum(pObj) - pnFanouts[pObj->Id] );
637  }
638  printf( "\n" );
639 */
640 
641  if ( pPars->fVerbose )
642  {
643 // Cloud_PrintInfo( p->pDsdMan->dd );
645  p->nTotalNodes2 = Abc_NtkNodeNum(pNtk);
646  printf( "Node gain = %5d. (%.2f %%) ",
647  p->nTotalNodes-p->nTotalNodes2, 100.0*(p->nTotalNodes-p->nTotalNodes2)/p->nTotalNodes );
648  printf( "Edge gain = %5d. (%.2f %%) ",
649  p->nTotalNets-p->nTotalNets2, 100.0*(p->nTotalNets-p->nTotalNets2)/p->nTotalNets );
650  printf( "Muxes = %4d. Dsds = %4d.", p->nMuxes, p->nDsds );
651  printf( "\n" );
652  printf( "Nodes = %5d (%3d) Cuts = %5d (%4d) Changes = %5d Iter = %2d Benefit = %d.\n",
653  p->nNodesTotal, p->nNodesOver, p->nCutsTotal, p->nCutsUseful, p->nChanges, Iter, p->nBenefited );
654 
655  printf( "Non-DSD:" );
656  for ( i = 3; i <= pPars->nVarsMax; i++ )
657  if ( p->nBlocks[i] )
658  printf( " %d=%d", i, p->nBlocks[i] );
659  printf( "\n" );
660 
661  p->timeTotal = Abc_Clock() - clk;
662  p->timeEval = p->timeEval - p->timeMap;
663  p->timeOther = p->timeTotal - p->timeCuts - p->timeTruth - p->timeEval - p->timeMap;
664  ABC_PRTP( "Cuts ", p->timeCuts, p->timeTotal );
665  ABC_PRTP( "Truth ", p->timeTruth, p->timeTotal );
666  ABC_PRTP( "CSupps", p->timeSupps, p->timeTotal );
667  ABC_PRTP( "Eval ", p->timeEval, p->timeTotal );
668  ABC_PRTP( " MuxAn", p->timeEvalMuxAn, p->timeEval );
669  ABC_PRTP( " MuxSp", p->timeEvalMuxSp, p->timeEval );
670  ABC_PRTP( " DsdAn", p->timeEvalDsdAn, p->timeEval );
671  ABC_PRTP( " DsdSp", p->timeEvalDsdSp, p->timeEval );
673  ABC_PRTP( "Map ", p->timeMap, p->timeTotal );
674  ABC_PRTP( "Other ", p->timeOther, p->timeTotal );
675  ABC_PRTP( "TOTAL ", p->timeTotal, p->timeTotal );
676  }
677 
678  Lpk_ManStop( p );
679  // check the resulting network
680  if ( !Abc_NtkCheck( pNtk ) )
681  {
682  printf( "Lpk_Resynthesize: The network check has failed.\n" );
683  return 0;
684  }
685  return 1;
686 }
687 
688 ////////////////////////////////////////////////////////////////////////
689 /// END OF FILE ///
690 ////////////////////////////////////////////////////////////////////////
691 
692 
694 
char * memset()
unsigned Type
Definition: kit.h:112
int nNodesTotal
Definition: lpkInt.h:108
int pLeaves[LPK_SIZE_MAX]
Definition: lpkInt.h:65
static int Abc_NtkIsLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:250
static Kit_DsdObj_t * Kit_DsdNtkRoot(Kit_DsdNtk_t *pNtk)
Definition: kit.h:151
Lpk_Par_t * pPars
Definition: lpkInt.h:72
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
int fUseMv
Definition: if.h:151
int nTotalNets2
Definition: lpkInt.h:118
int Kit_DsdNonDsdSizeMax(Kit_DsdNtk_t *pNtk)
Definition: kitDsd.c:1211
float Weight
Definition: lpkInt.h:63
int nLutSize
Definition: if.h:103
Vec_Vec_t * vVisited
Definition: lpkInt.h:84
static int Abc_NtkObjNumMax(Abc_Ntk_t *pNtk)
Definition: abc.h:284
int fUseCnfs
Definition: if.h:150
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Definition: if.h:100
int Lpk_NodeHasChanged(Lpk_Man_t *p, int iNode)
Definition: lpkCore.c:96
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
int LevelMax
Definition: abc.h:195
If_Man_t * If_ManStart(If_Par_t *pPars)
FUNCTION DEFINITIONS ///.
Definition: ifMan.c:50
int nCuts
Definition: lpkInt.h:78
abctime timeMap
Definition: lpkInt.h:130
Definition: if.h:303
int nChanges
Definition: lpkInt.h:113
int fVerbose
Definition: if.h:140
If_Obj_t * Lpk_MapTree_rec(Lpk_Man_t *p, Kit_DsdNtk_t *pNtk, If_Obj_t **ppLeaves, int iLit, If_Obj_t *pResult)
Definition: lpkMap.c:110
int Kit_CreateCloudFromTruth(CloudManager *dd, unsigned *pTruth, int nVars, Vec_Int_t *vNodes)
Definition: kitCloud.c:209
int Lpk_ResynthesizeNode(Lpk_Man_t *p)
Definition: lpkCore.c:239
abctime timeEvalMuxSp
Definition: lpkInt.h:135
Vec_Int_t * vBddDir
Definition: lpkInt.h:100
unsigned nLeaves
Definition: lpkInt.h:55
ABC_DLL int Abc_NtkGetFaninMax(Abc_Ntk_t *pNtk)
Definition: abcUtil.c:453
unsigned short Root
Definition: kit.h:127
ABC_DLL Abc_Obj_t * Abc_NtkCreateNodeConst1(Abc_Ntk_t *pNtk)
Definition: abcObj.c:633
Vec_Int_t * vCover
Definition: lpkInt.h:87
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
int nCutsUseful
Definition: lpkInt.h:111
int nBenefited
Definition: lpkInt.h:114
ABC_DLL int Abc_NtkCheck(Abc_Ntk_t *pNtk)
FUNCTION DEFINITIONS ///.
Definition: abcCheck.c:61
void Kit_DsdPrintFromTruth(unsigned *pTruth, int nVars)
Definition: kitDsd.c:490
Lpk_Man_t * Lpk_ManStart(Lpk_Par_t *pPars)
DECLARATIONS ///.
Definition: lpkMan.c:45
static abctime Abc_Clock()
Definition: abc_global.h:279
static Abc_Obj_t * Abc_NtkObj(Abc_Ntk_t *pNtk, int i)
Definition: abc.h:314
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
void Kit_TruthCofSupports(Vec_Int_t *vBddDir, Vec_Int_t *vBddInv, int nVars, Vec_Int_t *vMemory, unsigned *puSupps)
Definition: kitCloud.c:310
ABC_DLL int Abc_NtkGetTotalFanins(Abc_Ntk_t *pNtk)
Definition: abcUtil.c:487
Definition: hop.h:65
Abc_Obj_t * pObj
Definition: lpkInt.h:75
int nLatchesCi
Definition: if.h:152
ABC_DLL void Abc_NtkStopReverseLevels(Abc_Ntk_t *pNtk)
Definition: abcTiming.c:1190
Kit_DsdNtk_t * Kit_DsdDecompose(unsigned *pTruth, int nVars)
Definition: kitDsd.c:2314
unsigned Level
Definition: abc.h:142
static int Abc_ObjIsCo(Abc_Obj_t *pObj)
Definition: abc.h:352
If_Obj_t * If_ManCreateCo(If_Man_t *p, If_Obj_t *pDriver)
Definition: ifMan.c:338
int fExpRed
Definition: if.h:116
int nFlowIters
Definition: if.h:105
int Lpk_Resynthesize(Abc_Ntk_t *pNtk, Lpk_Par_t *pPars)
MACRO DEFINITIONS ///.
Definition: lpkCore.c:505
int Lpk_ExploreCut(Lpk_Man_t *p, Lpk_Cut_t *pCut, Kit_DsdNtk_t *pNtk)
Definition: lpkCore.c:129
int nNodesOver
Definition: lpkInt.h:109
#define ABC_PRTP(a, t, T)
Definition: abc_global.h:223
Abc_Ntk_t * pNtk
Definition: lpkInt.h:74
abctime timeEvalMuxAn
Definition: lpkInt.h:134
int nDsds
Definition: lpkInt.h:116
Lpk_Cut_t pCuts[LPK_CUTS_MAX]
Definition: lpkInt.h:81
static int Abc_NtkNodeNum(Abc_Ntk_t *pNtk)
Definition: abc.h:293
float AreaGlo
Definition: if.h:198
static int Abc_LitIsCompl(int Lit)
Definition: abc_global.h:265
int fUsePerm
Definition: if.h:147
void Kit_DsdPrint(FILE *pFile, Kit_DsdNtk_t *pNtk)
Definition: kitDsd.c:374
DECLARATIONS ///.
void If_ManSetupSetAll(If_Man_t *p, int nCrossCut)
Definition: ifMan.c:675
int fPreprocess
Definition: if.h:113
abctime timeEvalDsdSp
Definition: lpkInt.h:137
int fAreaOnly
Definition: if.h:145
ABC_DLL int Abc_ObjRequiredLevel(Abc_Obj_t *pObj)
Definition: abcTiming.c:1102
float RequiredGlo
Definition: if.h:196
ABC_DLL Abc_Obj_t * Abc_NtkCreateNodeInv(Abc_Ntk_t *pNtk, Abc_Obj_t *pFanin)
Definition: abcObj.c:662
int fTruth
Definition: if.h:146
int fLatchPaths
Definition: if.h:117
static int Abc_ObjLevel(Abc_Obj_t *pObj)
Definition: abc.h:330
int Lpk_NodeCuts(Lpk_Man_t *p)
Definition: lpkCut.c:588
#define Lpk_CutForEachLeaf(pNtk, pCut, pObj, i)
MACRO DEFINITIONS ///.
Definition: lpkInt.h:189
ABC_NAMESPACE_IMPL_START void Lpk_IfManStart(Lpk_Man_t *p)
DECLARATIONS ///.
Definition: lpkCore.c:47
Definition: if.h:180
int nCalledSRed
Definition: lpkInt.h:92
int Lpk_ResynthesizeNodeNew(Lpk_Man_t *p)
Definition: lpkCore.c:368
int Extra_TruthSupportSize(unsigned *pTruth, int nVars)
int If_ManPerformMappingComb(If_Man_t *p)
Definition: ifCore.c:104
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
static void If_ObjSetCopy(If_Obj_t *pObj, void *pCopy)
Definition: if.h:387
if(last==0)
Definition: sparse_int.h:34
int fCalledOnce
Definition: lpkInt.h:91
int pEvals[LPK_CUTS_MAX]
Definition: lpkInt.h:82
Vec_Vec_t * vLevels
Definition: lpkInt.h:88
float * pTimesArr
Definition: if.h:161
Abc_Obj_t * Abc_NodeFromIf_rec(Abc_Ntk_t *pNtkNew, If_Man_t *pIfMan, If_Obj_t *pIfObj, Vec_Int_t *vCover)
Definition: abcIf.c:415
abctime timeEval
Definition: lpkInt.h:129
static If_Obj_t * If_ManCi(If_Man_t *p, int i)
Definition: if.h:366
CloudManager * dd
Definition: kit.h:142
int nTotalNodes
Definition: lpkInt.h:119
unsigned nNodes
Definition: lpkInt.h:56
static Vec_Vec_t * Vec_VecStart(int nSize)
Definition: vecVec.h:168
ABC_DLL int Abc_NodeMffcLabel(Abc_Obj_t *pNode)
Definition: abcRefs.c:437
float Epsilon
Definition: if.h:110
unsigned short pFans[0]
Definition: kit.h:117
ABC_DLL void Abc_NtkStartReverseLevels(Abc_Ntk_t *pNtk, int nMaxLevelIncrease)
Definition: abcTiming.c:1162
void Extra_ProgressBarStop(ProgressBar *p)
int nCutsTotal
Definition: lpkInt.h:110
Vec_Int_t * vBddInv
Definition: lpkInt.h:101
abctime timeSupps
Definition: lpkInt.h:126
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition: abc.h:461
If_Man_t * pIfMan
Definition: lpkInt.h:86
Vec_Int_t * vMemory
Definition: lpkInt.h:99
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
int fFancy
Definition: if.h:115
abctime timeTruth
Definition: lpkInt.h:125
Vec_Int_t vFanouts
Definition: abc.h:144
void If_ManSetupCiCutSets(If_Man_t *p)
Definition: ifMan.c:548
abctime timeTotal
Definition: lpkInt.h:132
Vec_Ptr_t * vLeaves
Definition: lpkInt.h:95
static If_Obj_t * If_Regular(If_Obj_t *p)
Definition: if.h:355
Kit_DsdMan_t * pDsdMan
Definition: lpkInt.h:106
int nMffc
Definition: lpkInt.h:77
If_Par_t * pPars
Definition: if.h:184
int nEvals
Definition: lpkInt.h:80
float DelayTarget
Definition: if.h:109
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Abc_Obj_t * Lpk_Decompose(Lpk_Man_t *p, Abc_Ntk_t *pNtk, Vec_Ptr_t *vLeaves, unsigned *pTruth, unsigned *puSupps, int nLutK, int AreaLim, int DelayLim)
FUNCTION DECLARATIONS ///.
Definition: lpkAbcDec.c:258
void If_ManRestart(If_Man_t *p)
Definition: ifMan.c:178
int fUseBdds
Definition: if.h:148
int nLatchesCo
Definition: if.h:153
unsigned nNodesDup
Definition: lpkInt.h:57
ABC_DLL int Abc_NtkSweep(Abc_Ntk_t *pNtk, int fVerbose)
Definition: abcSweep.c:574
static void Vec_VecExpand(Vec_Vec_t *p, int Level)
Definition: vecVec.h:190
ABC_DLL void Abc_NtkUpdate(Abc_Obj_t *pObj, Abc_Obj_t *pObjNew, Vec_Vec_t *vLevels)
Definition: abcTiming.c:1311
static Hop_Obj_t * Hop_NotCond(Hop_Obj_t *p, int c)
Definition: hop.h:128
int nAreaIters
Definition: if.h:106
ABC_DLL Abc_Obj_t * Abc_NtkCreateNodeConst0(Abc_Ntk_t *pNtk)
Definition: abcObj.c:604
int Id
Definition: abc.h:132
void If_ManCleanCutData(If_Man_t *p)
Definition: ifUtil.c:64
void Lpk_ManStop(Lpk_Man_t *p)
Definition: lpkMan.c:94
If_Obj_t * If_ManCreateCi(If_Man_t *p)
Definition: ifMan.c:316
typedefABC_NAMESPACE_HEADER_START struct Lpk_Par_t_ Lpk_Par_t
INCLUDES ///.
Definition: lpk.h:42
unsigned puSupps[32]
Definition: lpkInt.h:102
ProgressBar * Extra_ProgressBarStart(FILE *pFile, int nItemsTotal)
FUNCTION DEFINITIONS ///.
abctime timeOther
Definition: lpkInt.h:131
static int Abc_Lit2Var(int Lit)
Definition: abc_global.h:264
unsigned * Lpk_CutTruth(Lpk_Man_t *p, Lpk_Cut_t *pCut, int fInv)
Definition: lpkCut.c:175
unsigned nLuts
Definition: lpkInt.h:58
ABC_DLL int Abc_NtkToAig(Abc_Ntk_t *pNtk)
Definition: abcFunc.c:1192
abctime timeEvalDsdAn
Definition: lpkInt.h:136
int fUseSops
Definition: if.h:149
void Kit_DsdNtkFree(Kit_DsdNtk_t *pNtk)
Definition: kitDsd.c:163
void If_ManCleanNodeCopy(If_Man_t *p)
DECLARATIONS ///.
Definition: ifUtil.c:45
#define assert(ex)
Definition: util_old.h:213
static void Extra_ProgressBarUpdate(ProgressBar *p, int nItemsCur, char *pString)
Definition: extra.h:243
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
static int Abc_NtkHasAig(Abc_Ntk_t *pNtk)
Definition: abc.h:255
int nCutsMax
Definition: if.h:104
int nBlocks[17]
Definition: lpkInt.h:122
int nGainTotal
Definition: lpkInt.h:112
void Lpk_ComputeSupports(Lpk_Man_t *p, Lpk_Cut_t *pCut, unsigned *pTruth)
Definition: lpkCore.c:343
int nTotalNets
Definition: lpkInt.h:117
static Vec_Ptr_t * Vec_VecEntry(Vec_Vec_t *p, int i)
Definition: vecVec.h:271
void * pData
Definition: abc.h:145
int nTotalNodes2
Definition: lpkInt.h:120
int fArea
Definition: if.h:114
int nMuxes
Definition: lpkInt.h:115
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
static int If_IsComplement(If_Obj_t *p)
Definition: if.h:358
ABC_INT64_T abctime
Definition: abc_global.h:278
ABC_DLL int Abc_NtkLevel(Abc_Ntk_t *pNtk)
Definition: abcDfs.c:1265
ABC_DLL void * Abc_FrameReadLibLut()
Definition: mainFrame.c:54
static Abc_Obj_t * Abc_ObjFanout0(Abc_Obj_t *pObj)
Definition: abc.h:371
abctime timeCuts
Definition: lpkInt.h:124
If_LibLut_t * pLutLib
Definition: if.h:160