abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
abcRestruct.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [abcRestruct.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Network and node package.]
8 
9  Synopsis []
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: abcRestruct.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "base/abc/abc.h"
22 #include "bool/dec/dec.h"
23 #include "opt/cut/cut.h"
24 #include "misc/extra/extraBdd.h"
25 #include "bdd/dsd/dsd.h"
26 
27 ABC_NAMESPACE_IMPL_START
28 
29 
30 ////////////////////////////////////////////////////////////////////////
31 /// DECLARATIONS ///
32 ////////////////////////////////////////////////////////////////////////
33 
34 #define RST_RANDOM_UNSIGNED ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand()))
35 
36 typedef struct Abc_ManRst_t_ Abc_ManRst_t;
37 struct Abc_ManRst_t_
38 {
39  // the network
40  Abc_Ntk_t * pNtk; // the network for restructuring
41  // user specified parameters
42  int nCutMax; // the limit on the size of the supernode
43  int fUpdateLevel; // turns on watching the number of levels
44  int fUseZeros; // turns on zero-cost replacements
45  int fVerbose; // the verbosity flag
46  // internal data structures
47  DdManager * dd; // the BDD manager
48  Dsd_Manager_t * pManDsd; // the DSD manager
49  Vec_Ptr_t * vVisited; // temporary
50  Vec_Ptr_t * vLeaves; // temporary
51  Vec_Ptr_t * vDecs; // temporary
52  Vec_Ptr_t * vTemp; // temporary
53  Vec_Int_t * vSims; // temporary
54  Vec_Int_t * vRands; // temporary
55  Vec_Int_t * vOnes; // temporary
56  Vec_Int_t * vBinate; // temporary
57  Vec_Int_t * vTwos; // temporary
58  // node statistics
59  int nLastGain;
60  int nCutsConsidered;
61  int nCutsExplored;
62  int nNodesConsidered;
63  int nNodesRestructured;
64  int nNodesGained;
65  // runtime statistics
66  int timeCut;
67  int timeBdd;
68  int timeDsd;
69  int timeEval;
70  int timeRes;
71  int timeNtk;
72  int timeTotal;
73 };
74 
75 static Dec_Graph_t * Abc_NodeResubstitute( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList );
76 
77 static Dec_Graph_t * Abc_NodeRestructure( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList );
78 static Dec_Graph_t * Abc_NodeRestructureCut( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCut );
79 static Dec_Graph_t * Abc_NodeEvaluateDsd( Abc_ManRst_t * pManRst, Dsd_Node_t * pNodeDsd, Abc_Obj_t * pRoot, int Required, int nNodesSaved, int * pnNodesAdded );
80 
81 static Cut_Man_t * Abc_NtkStartCutManForRestruct( Abc_Ntk_t * pNtk, int nCutMax, int fDag );
82 static Abc_ManRst_t * Abc_NtkManRstStart( int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose );
83 static void Abc_NtkManRstStop( Abc_ManRst_t * p );
84 static void Abc_NtkManRstPrintStats( Abc_ManRst_t * p );
85 
86 ////////////////////////////////////////////////////////////////////////
87 /// FUNCTION DEFINITIONS ///
88 ////////////////////////////////////////////////////////////////////////
89 
90 /**Function*************************************************************
91 
92  Synopsis [Implements AIG restructuring.]
93 
94  Description []
95 
96  SideEffects []
97 
98  SeeAlso []
99 
100 ***********************************************************************/
101 int Abc_NtkRestructure( Abc_Ntk_t * pNtk, int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose )
102 {
103  extern void Dec_GraphUpdateNetwork( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int fUpdateLevel, int nGain );
104  ProgressBar * pProgress;
105  Abc_ManRst_t * pManRst;
106  Cut_Man_t * pManCut;
107  Cut_Cut_t * pCutList;
108  Dec_Graph_t * pGraph;
109  Abc_Obj_t * pNode;
110  abctime clk, clkStart = Abc_Clock();
111  int fMulti = 1;
112  int fResub = 0;
113  int i, nNodes;
114 
115  assert( Abc_NtkIsStrash(pNtk) );
116  // cleanup the AIG
117  Abc_AigCleanup((Abc_Aig_t *)pNtk->pManFunc);
118  Abc_NtkCleanCopy(pNtk);
119 
120  // compute the reverse levels if level update is requested
121  if ( fUpdateLevel )
122  Abc_NtkStartReverseLevels( pNtk, 0 );
123 
124  // start the restructuring manager
125  pManRst = Abc_NtkManRstStart( nCutMax, fUpdateLevel, fUseZeros, fVerbose );
126  pManRst->pNtk = pNtk;
127  // start the cut manager
128 clk = Abc_Clock();
129  pManCut = Abc_NtkStartCutManForRestruct( pNtk, nCutMax, fMulti );
130 pManRst->timeCut += Abc_Clock() - clk;
131 // pNtk->pManCut = pManCut;
132 
133  // resynthesize each node once
134  nNodes = Abc_NtkObjNumMax(pNtk);
135  pProgress = Extra_ProgressBarStart( stdout, nNodes );
136  Abc_NtkForEachNode( pNtk, pNode, i )
137  {
138  Extra_ProgressBarUpdate( pProgress, i, NULL );
139  // skip the constant node
140 // if ( Abc_NodeIsConst(pNode) )
141 // continue;
142  // skip persistant nodes
143  if ( Abc_NodeIsPersistant(pNode) )
144  continue;
145  // skip the node if it is inside the tree
146 // if ( Abc_ObjFanoutNum(pNode) < 2 )
147 // continue;
148  // skip the nodes with too many fanouts
149  if ( Abc_ObjFanoutNum(pNode) > 1000 )
150  continue;
151  // stop if all nodes have been tried once
152  if ( i >= nNodes )
153  break;
154  // get the cuts for the given node
155 clk = Abc_Clock();
156  pCutList = (Cut_Cut_t *)Abc_NodeGetCutsRecursive( pManCut, pNode, fMulti, 0 );
157 pManRst->timeCut += Abc_Clock() - clk;
158 
159  // perform restructuring
160 clk = Abc_Clock();
161  if ( fResub )
162  pGraph = Abc_NodeResubstitute( pManRst, pNode, pCutList );
163  else
164  pGraph = Abc_NodeRestructure( pManRst, pNode, pCutList );
165 pManRst->timeRes += Abc_Clock() - clk;
166  if ( pGraph == NULL )
167  continue;
168 
169  // acceptable replacement found, update the graph
170 clk = Abc_Clock();
171  Dec_GraphUpdateNetwork( pNode, pGraph, fUpdateLevel, pManRst->nLastGain );
172 pManRst->timeNtk += Abc_Clock() - clk;
173  Dec_GraphFree( pGraph );
174  }
175  Extra_ProgressBarStop( pProgress );
176 pManRst->timeTotal = Abc_Clock() - clkStart;
177 
178  // print statistics of the manager
179 // if ( fVerbose )
180  Abc_NtkManRstPrintStats( pManRst );
181  // delete the managers
182  Cut_ManStop( pManCut );
183  Abc_NtkManRstStop( pManRst );
184  // put the nodes into the DFS order and reassign their IDs
185  Abc_NtkReassignIds( pNtk );
186 // Abc_AigCheckFaninOrder( pNtk->pManFunc );
187  // fix the levels
188  if ( fUpdateLevel )
189  Abc_NtkStopReverseLevels( pNtk );
190  else
191  Abc_NtkLevel( pNtk );
192  // check
193  if ( !Abc_NtkCheck( pNtk ) )
194  {
195  printf( "Abc_NtkRefactor: The network check has failed.\n" );
196  return 0;
197  }
198  return 1;
199 }
200 
201 /**Function*************************************************************
202 
203  Synopsis []
204 
205  Description []
206 
207  SideEffects []
208 
209  SeeAlso []
210 
211 ***********************************************************************/
212 void Abc_RestructNodeDivisors( Abc_ManRst_t * p, Abc_Obj_t * pRoot, int nNodesSaved )
213 {
214  Abc_Obj_t * pNode, * pFanout;//, * pFanin;
215  int i, k;
216  // start with the leaves
217  Vec_PtrClear( p->vDecs );
218  Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pNode, i )
219  {
220  Vec_PtrPush( p->vDecs, pNode );
221  assert( pNode->fMarkC == 0 );
222  pNode->fMarkC = 1;
223  }
224  // explore the fanouts
225  Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pNode, i )
226  {
227  // if the fanout has both fanins in the set, add it
228  Abc_ObjForEachFanout( pNode, pFanout, k )
229  {
230  if ( pFanout->fMarkC || Abc_ObjIsPo(pFanout) )
231  continue;
232  if ( Abc_ObjFanin0(pFanout)->fMarkC && Abc_ObjFanin1(pFanout)->fMarkC )
233  {
234  Vec_PtrPush( p->vDecs, pFanout );
235  pFanout->fMarkC = 1;
236  }
237  }
238  }
239  // unmark the nodes
240  Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pNode, i )
241  pNode->fMarkC = 0;
242 /*
243  // print the nodes
244  Vec_PtrForEachEntryStart( Abc_Obj_t *, p->vDecs, pNode, i, Vec_PtrSize(p->vLeaves) )
245  {
246  printf( "%2d %s = ", i, Abc_NodeIsTravIdCurrent(pNode)? "*" : " " );
247  // find the first fanin
248  Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pFanin, k )
249  if ( Abc_ObjFanin0(pNode) == pFanin )
250  break;
251  if ( k < Vec_PtrSize(p->vLeaves) )
252  printf( "%c", 'a' + k );
253  else
254  printf( "%d", k );
255  printf( "%s ", Abc_ObjFaninC0(pNode)? "\'" : "" );
256  // find the second fanin
257  Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pFanin, k )
258  if ( Abc_ObjFanin1(pNode) == pFanin )
259  break;
260  if ( k < Vec_PtrSize(p->vLeaves) )
261  printf( "%c", 'a' + k );
262  else
263  printf( "%d", k );
264  printf( "%s ", Abc_ObjFaninC1(pNode)? "\'" : "" );
265  printf( "\n" );
266  }
267 */
268  printf( "%d\n", Vec_PtrSize(p->vDecs)-nNodesSaved-Vec_PtrSize(p->vLeaves) );
269 }
270 
271 
272 /**Function*************************************************************
273 
274  Synopsis [Starts the cut manager for rewriting.]
275 
276  Description []
277 
278  SideEffects []
279 
280  SeeAlso []
281 
282 ***********************************************************************/
283 Dec_Graph_t * Abc_NodeRestructure( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList )
284 {
285  Dec_Graph_t * pGraph;
286  Cut_Cut_t * pCut;
287 // int nCuts;
288  p->nNodesConsidered++;
289 /*
290  // count the number of cuts with four inputs or more
291  nCuts = 0;
292  for ( pCut = pCutList; pCut; pCut = pCut->pNext )
293  nCuts += (int)(pCut->nLeaves > 3);
294  printf( "-----------------------------------\n" );
295  printf( "Node %6d : Factor-cuts = %5d.\n", pNode->Id, nCuts );
296 */
297  // go through the interesting cuts
298  for ( pCut = pCutList; pCut; pCut = pCut->pNext )
299  {
300  if ( pCut->nLeaves < 4 )
301  continue;
302  if ( (pGraph = Abc_NodeRestructureCut( p, pNode, pCut )) )
303  return pGraph;
304  }
305  return NULL;
306 }
307 
308 /**Function*************************************************************
309 
310  Synopsis [Starts the cut manager for rewriting.]
311 
312  Description []
313 
314  SideEffects []
315 
316  SeeAlso []
317 
318 ***********************************************************************/
319 Dec_Graph_t * Abc_NodeRestructureCut( Abc_ManRst_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut )
320 {
321  extern DdNode * Abc_NodeConeBdd( DdManager * dd, DdNode ** pbVars, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, Vec_Ptr_t * vVisited );
322  Dec_Graph_t * pGraph;
323  Dsd_Node_t * pNodeDsd;
324  Abc_Obj_t * pLeaf;
325  DdNode * bFunc;
326  int nNodesSaved, nNodesAdded;
327  int Required, nMaxSize, clk, i;
328  int fVeryVerbose = 0;
329 
330  p->nCutsConsidered++;
331 
332  // get the required time for the node
333  Required = p->fUpdateLevel? Abc_ObjRequiredLevel(pRoot) : ABC_INFINITY;
334 
335  // collect the leaves of the cut
336  Vec_PtrClear( p->vLeaves );
337  for ( i = 0; i < (int)pCut->nLeaves; i++ )
338  {
339  pLeaf = Abc_NtkObj(pRoot->pNtk, pCut->pLeaves[i]);
340  if ( pLeaf == NULL ) // the so-called "bad cut phenomenon" is due to removed nodes
341  return NULL;
342  Vec_PtrPush( p->vLeaves, pLeaf );
343  }
344 
345 clk = Abc_Clock();
346  // collect the internal nodes of the cut
347 // Abc_NodeConeCollect( &pRoot, 1, p->vLeaves, p->vVisited, 0 );
348  // derive the BDD of the cut
349  bFunc = Abc_NodeConeBdd( p->dd, p->dd->vars, pRoot, p->vLeaves, p->vVisited ); Cudd_Ref( bFunc );
350 p->timeBdd += Abc_Clock() - clk;
351 
352  // consider the special case, when the function is a constant
353  if ( Cudd_IsConstant(bFunc) )
354  {
355  p->nLastGain = Abc_NodeMffcSize( pRoot );
356  p->nNodesGained += p->nLastGain;
357  p->nNodesRestructured++;
358  Cudd_RecursiveDeref( p->dd, bFunc );
359  if ( Cudd_IsComplement(bFunc) )
360  return Dec_GraphCreateConst0();
361  return Dec_GraphCreateConst1();
362  }
363 
364 clk = Abc_Clock();
365  // try disjoint support decomposition
366  pNodeDsd = Dsd_DecomposeOne( p->pManDsd, bFunc );
367 p->timeDsd += Abc_Clock() - clk;
368 
369  // skip nodes with non-decomposable blocks
370  Dsd_TreeNodeGetInfoOne( pNodeDsd, NULL, &nMaxSize );
371  if ( nMaxSize > 3 )
372  {
373  Cudd_RecursiveDeref( p->dd, bFunc );
374  return NULL;
375  }
376 
377 
378 /*
379  // skip nodes that cannot be improved
380  if ( Vec_PtrSize(p->vVisited) <= Dsd_TreeGetAigCost(pNodeDsd) )
381  {
382  Cudd_RecursiveDeref( p->dd, bFunc );
383  return NULL;
384  }
385 */
386 
387  p->nCutsExplored++;
388 
389  // mark the fanin boundary
390  // (can mark only essential fanins, belonging to bNodeFunc!)
391  Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pLeaf, i )
392  pLeaf->vFanouts.nSize++;
393  // label MFFC with current traversal ID
394  Abc_NtkIncrementTravId( pRoot->pNtk );
395  nNodesSaved = Abc_NodeMffcLabelAig( pRoot );
396  // unmark the fanin boundary and set the fanins as leaves in the form
397  Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pLeaf, i )
398  pLeaf->vFanouts.nSize--;
399 /*
400  if ( nNodesSaved < 3 )
401  {
402  Cudd_RecursiveDeref( p->dd, bFunc );
403  return NULL;
404  }
405 */
406 
407 /*
408  printf( "%5d : Cut-size = %d. Old AIG = %2d. New AIG = %2d. Old MFFC = %2d.\n",
409  pRoot->Id, pCut->nLeaves, Vec_PtrSize(p->vVisited), Dsd_TreeGetAigCost(pNodeDsd),
410  nNodesSaved );
411  Dsd_NodePrint( stdout, pNodeDsd );
412 
413  Abc_RestructNodeDivisors( p, pRoot );
414 
415  if ( pRoot->Id == 433 )
416  {
417  int x = 0;
418  }
419 */
420 // Abc_RestructNodeDivisors( p, pRoot, nNodesSaved );
421 
422 
423  // detect how many new nodes will be added (while taking into account reused nodes)
424 clk = Abc_Clock();
425  if ( nMaxSize > 3 )
426  pGraph = NULL;
427  else
428  pGraph = Abc_NodeEvaluateDsd( p, pNodeDsd, pRoot, Required, nNodesSaved, &nNodesAdded );
429 // pGraph = NULL;
430 p->timeEval += Abc_Clock() - clk;
431 
432  // quit if there is no improvement
433  if ( pGraph == NULL || nNodesAdded == -1 || (nNodesAdded == nNodesSaved && !p->fUseZeros) )
434  {
435  Cudd_RecursiveDeref( p->dd, bFunc );
436  if ( pGraph ) Dec_GraphFree( pGraph );
437  return NULL;
438  }
439 
440 /*
441  // print stats
442  printf( "%5d : Cut-size = %d. Old AIG = %2d. New AIG = %2d. Old MFFC = %2d. New MFFC = %2d. Gain = %d.\n",
443  pRoot->Id, pCut->nLeaves, Vec_PtrSize(p->vVisited), Dsd_TreeGetAigCost(pNodeDsd),
444  nNodesSaved, nNodesAdded, (nNodesAdded == -1)? 0 : nNodesSaved-nNodesAdded );
445 // Dsd_NodePrint( stdout, pNodeDsd );
446 // Dec_GraphPrint( stdout, pGraph, NULL, NULL );
447 */
448 
449  // compute the total gain in the number of nodes
450  p->nLastGain = nNodesSaved - nNodesAdded;
451  p->nNodesGained += p->nLastGain;
452  p->nNodesRestructured++;
453 
454  // report the progress
455  if ( fVeryVerbose )
456  {
457  printf( "Node %6s : ", Abc_ObjName(pRoot) );
458  printf( "Cone = %2d. ", p->vLeaves->nSize );
459  printf( "BDD = %2d. ", Cudd_DagSize(bFunc) );
460  printf( "FF = %2d. ", 1 + Dec_GraphNodeNum(pGraph) );
461  printf( "MFFC = %2d. ", nNodesSaved );
462  printf( "Add = %2d. ", nNodesAdded );
463  printf( "GAIN = %2d. ", p->nLastGain );
464  printf( "\n" );
465  }
466  Cudd_RecursiveDeref( p->dd, bFunc );
467  return pGraph;
468 }
469 
470 
471 /**Function*************************************************************
472 
473  Synopsis [Moves closer to the end the node that is best for sharing.]
474 
475  Description [If the flag is set, tries to find an EXOR, otherwise, tries
476  to find an OR.]
477 
478  SideEffects []
479 
480  SeeAlso []
481 
482 ***********************************************************************/
483 void Abc_NodeEdgeDsdPermute( Dec_Graph_t * pGraph, Abc_ManRst_t * pManRst, Vec_Int_t * vEdges, int fExor )
484 {
485  Dec_Edge_t eNode1, eNode2, eNode3;
486  Abc_Obj_t * pNode1, * pNode2, * pNode3, * pTemp;
487  int LeftBound = 0, RightBound, i;
488  // get the right bound
489  RightBound = Vec_IntSize(vEdges) - 2;
490  assert( LeftBound <= RightBound );
491  if ( LeftBound == RightBound )
492  return;
493  // get the two last nodes
494  eNode1 = Dec_IntToEdge( Vec_IntEntry(vEdges, RightBound + 1) );
495  eNode2 = Dec_IntToEdge( Vec_IntEntry(vEdges, RightBound ) );
496  pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc;
497  pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc;
498  pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl );
499  pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl );
500  // quit if the last node does not exist
501  if ( pNode1 == NULL )
502  return;
503  // find the first node that can be shared
504  for ( i = RightBound; i >= LeftBound; i-- )
505  {
506  // get the third node
507  eNode3 = Dec_IntToEdge( Vec_IntEntry(vEdges, i) );
508  pNode3 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode3.Node )->pFunc;
509  pNode3 = !pNode3? NULL : Abc_ObjNotCond( pNode3, eNode3.fCompl );
510  if ( pNode3 == NULL )
511  continue;
512  // check if the node exists
513  if ( fExor )
514  {
515  if ( pNode1 && pNode3 )
516  {
517  pTemp = Abc_AigXorLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode3, NULL );
518  if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
519  continue;
520 
521  if ( pNode3 == pNode2 )
522  return;
523  Vec_IntWriteEntry( vEdges, i, Dec_EdgeToInt(eNode2) );
524  Vec_IntWriteEntry( vEdges, RightBound, Dec_EdgeToInt(eNode3) );
525  return;
526  }
527  }
528  else
529  {
530  if ( pNode1 && pNode3 )
531  {
532  pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode3) );
533  if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
534  continue;
535 
536  if ( eNode3.Node == eNode2.Node )
537  return;
538  Vec_IntWriteEntry( vEdges, i, Dec_EdgeToInt(eNode2) );
539  Vec_IntWriteEntry( vEdges, RightBound, Dec_EdgeToInt(eNode3) );
540  return;
541  }
542  }
543  }
544 }
545 
546 /**Function*************************************************************
547 
548  Synopsis [Adds the new edge in the given order.]
549 
550  Description [Similar to Vec_IntPushOrder, except in decreasing order.]
551 
552  SideEffects []
553 
554  SeeAlso []
555 
556 ***********************************************************************/
557 void Abc_NodeEdgeDsdPushOrdered( Dec_Graph_t * pGraph, Vec_Int_t * vEdges, int Edge )
558 {
559  int i, NodeOld, NodeNew;
560  vEdges->nSize++;
561  for ( i = vEdges->nSize-2; i >= 0; i-- )
562  {
563  NodeOld = Dec_IntToEdge(vEdges->pArray[i]).Node;
564  NodeNew = Dec_IntToEdge(Edge).Node;
565  // use <= because we are trying to push the new (non-existent) nodes as far as possible
566  if ( Dec_GraphNode(pGraph, NodeOld)->Level <= Dec_GraphNode(pGraph, NodeNew)->Level )
567  vEdges->pArray[i+1] = vEdges->pArray[i];
568  else
569  break;
570  }
571  vEdges->pArray[i+1] = Edge;
572 }
573 
574 /**Function*************************************************************
575 
576  Synopsis [Evaluation one DSD.]
577 
578  Description []
579 
580  SideEffects []
581 
582  SeeAlso []
583 
584 ***********************************************************************/
585 Dec_Edge_t Abc_NodeEvaluateDsd_rec( Dec_Graph_t * pGraph, Abc_ManRst_t * pManRst, Dsd_Node_t * pNodeDsd, int Required, int nNodesSaved, int * pnNodesAdded )
586 {
587  Dec_Edge_t eNode1, eNode2, eNode3, eResult, eQuit = { 0, 2006 };
588  Abc_Obj_t * pNode1, * pNode2, * pNode3, * pNode4, * pTemp;
589  Dsd_Node_t * pChildDsd;
590  Dsd_Type_t DecType;
591  Vec_Int_t * vEdges;
592  int Level1, Level2, Level3, Level4;
593  int i, Index, fCompl, Type;
594 
595  // remove the complemented attribute
596  fCompl = Dsd_IsComplement( pNodeDsd );
597  pNodeDsd = Dsd_Regular( pNodeDsd );
598 
599  // consider the trivial case
600  DecType = Dsd_NodeReadType( pNodeDsd );
601  if ( DecType == DSD_NODE_BUF )
602  {
603  Index = Dsd_NodeReadFunc(pNodeDsd)->index;
604  assert( Index < Dec_GraphLeaveNum(pGraph) );
605  eResult = Dec_EdgeCreate( Index, fCompl );
606  return eResult;
607  }
608  assert( DecType == DSD_NODE_OR || DecType == DSD_NODE_EXOR || DecType == DSD_NODE_PRIME );
609 
610  // solve the problem for the children
611  vEdges = Vec_IntAlloc( Dsd_NodeReadDecsNum(pNodeDsd) );
612  Dsd_NodeForEachChild( pNodeDsd, i, pChildDsd )
613  {
614  eResult = Abc_NodeEvaluateDsd_rec( pGraph, pManRst, pChildDsd, Required, nNodesSaved, pnNodesAdded );
615  if ( eResult.Node == eQuit.Node ) // infeasible
616  {
617  Vec_IntFree( vEdges );
618  return eQuit;
619  }
620  // order the inputs only if this is OR or EXOR
621  if ( DecType == DSD_NODE_PRIME )
622  Vec_IntPush( vEdges, Dec_EdgeToInt(eResult) );
623  else
624  Abc_NodeEdgeDsdPushOrdered( pGraph, vEdges, Dec_EdgeToInt(eResult) );
625  }
626  // the edges are sorted by the level of their nodes in decreasing order
627 
628 
629  // consider special cases
630  if ( DecType == DSD_NODE_OR )
631  {
632  // try to balance the nodes by delay
633  assert( Vec_IntSize(vEdges) > 1 );
634  while ( Vec_IntSize(vEdges) > 1 )
635  {
636  // permute the last two entries
637  if ( Vec_IntSize(vEdges) > 2 )
638  Abc_NodeEdgeDsdPermute( pGraph, pManRst, vEdges, 0 );
639  // get the two last nodes
640  eNode1 = Dec_IntToEdge( Vec_IntPop(vEdges) );
641  eNode2 = Dec_IntToEdge( Vec_IntPop(vEdges) );
642  pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc;
643  pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc;
644  pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl );
645  pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl );
646  // check if the new node exists
647  pNode3 = NULL;
648  if ( pNode1 && pNode2 )
649  {
650  pNode3 = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode2) );
651  pNode3 = !pNode3? NULL : Abc_ObjNot(pNode3);
652  }
653  // create the new node
654  eNode3 = Dec_GraphAddNodeOr( pGraph, eNode1, eNode2 );
655  // set level
656  Level1 = Dec_GraphNode( pGraph, eNode1.Node )->Level;
657  Level2 = Dec_GraphNode( pGraph, eNode2.Node )->Level;
658  Dec_GraphNode( pGraph, eNode3.Node )->Level = 1 + Abc_MaxInt(Level1, Level2);
659  // get the new node if possible
660  if ( pNode3 )
661  {
662  Dec_GraphNode( pGraph, eNode3.Node )->pFunc = Abc_ObjNotCond(pNode3, eNode3.fCompl);
663  Level3 = Dec_GraphNode( pGraph, eNode3.Node )->Level;
664  assert( Required == ABC_INFINITY || Level3 == (int)Abc_ObjRegular(pNode3)->Level );
665  }
666  if ( !pNode3 || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pNode3)) )
667  {
668  (*pnNodesAdded)++;
669  if ( *pnNodesAdded > nNodesSaved )
670  {
671  Vec_IntFree( vEdges );
672  return eQuit;
673  }
674  }
675  // add the resulting node to the form
676  Abc_NodeEdgeDsdPushOrdered( pGraph, vEdges, Dec_EdgeToInt(eNode3) );
677  }
678  // get the last node
679  eResult = Dec_IntToEdge( Vec_IntPop(vEdges) );
680  Vec_IntFree( vEdges );
681  // complement the graph if the node was complemented
682  eResult.fCompl ^= fCompl;
683  return eResult;
684  }
685  if ( DecType == DSD_NODE_EXOR )
686  {
687  // try to balance the nodes by delay
688  assert( Vec_IntSize(vEdges) > 1 );
689  while ( Vec_IntSize(vEdges) > 1 )
690  {
691  // permute the last two entries
692  if ( Vec_IntSize(vEdges) > 2 )
693  Abc_NodeEdgeDsdPermute( pGraph, pManRst, vEdges, 1 );
694  // get the two last nodes
695  eNode1 = Dec_IntToEdge( Vec_IntPop(vEdges) );
696  eNode2 = Dec_IntToEdge( Vec_IntPop(vEdges) );
697  pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc;
698  pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc;
699  pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl );
700  pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl );
701  // check if the new node exists
702  Type = 0;
703  pNode3 = NULL;
704  if ( pNode1 && pNode2 )
705  pNode3 = Abc_AigXorLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2, &Type );
706  // create the new node
707  eNode3 = Dec_GraphAddNodeXor( pGraph, eNode1, eNode2, Type ); // should have the same structure as in AIG
708  // set level
709  Level1 = Dec_GraphNode( pGraph, eNode1.Node )->Level;
710  Level2 = Dec_GraphNode( pGraph, eNode2.Node )->Level;
711  Dec_GraphNode( pGraph, eNode3.Node )->Level = 2 + Abc_MaxInt(Level1, Level2);
712  // get the new node if possible
713  if ( pNode3 )
714  {
715  Dec_GraphNode( pGraph, eNode3.Node )->pFunc = Abc_ObjNotCond(pNode3, eNode3.fCompl);
716  Level3 = Dec_GraphNode( pGraph, eNode3.Node )->Level;
717  assert( Required == ABC_INFINITY || Level3 == (int)Abc_ObjRegular(pNode3)->Level );
718  }
719  if ( !pNode3 || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pNode3)) )
720  {
721  (*pnNodesAdded)++;
722  if ( !pNode1 || !pNode2 )
723  (*pnNodesAdded) += 2;
724  else if ( Type == 0 )
725  {
726  pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, Abc_ObjNot(pNode2) );
727  if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
728  (*pnNodesAdded)++;
729  pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), pNode2 );
730  if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
731  (*pnNodesAdded)++;
732  }
733  else
734  {
735  pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode2) );
736  if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
737  (*pnNodesAdded)++;
738  pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2 );
739  if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
740  (*pnNodesAdded)++;
741  }
742  if ( *pnNodesAdded > nNodesSaved )
743  {
744  Vec_IntFree( vEdges );
745  return eQuit;
746  }
747  }
748  // add the resulting node to the form
749  Abc_NodeEdgeDsdPushOrdered( pGraph, vEdges, Dec_EdgeToInt(eNode3) );
750  }
751  // get the last node
752  eResult = Dec_IntToEdge( Vec_IntPop(vEdges) );
753  Vec_IntFree( vEdges );
754  // complement the graph if the node is complemented
755  eResult.fCompl ^= fCompl;
756  return eResult;
757  }
758  if ( DecType == DSD_NODE_PRIME )
759  {
760  DdNode * bLocal, * bVar, * bCofT, * bCofE;
761  bLocal = Dsd_TreeGetPrimeFunction( pManRst->dd, pNodeDsd ); Cudd_Ref( bLocal );
762 //Extra_bddPrint( pManRst->dd, bLocal );
763 
764  bVar = pManRst->dd->vars[0];
765  bCofE = Cudd_Cofactor( pManRst->dd, bLocal, Cudd_Not(bVar) ); Cudd_Ref( bCofE );
766  bCofT = Cudd_Cofactor( pManRst->dd, bLocal, bVar ); Cudd_Ref( bCofT );
767  if ( !Extra_bddIsVar(bCofE) || !Extra_bddIsVar(bCofT) )
768  {
769  Cudd_RecursiveDeref( pManRst->dd, bCofE );
770  Cudd_RecursiveDeref( pManRst->dd, bCofT );
771  bVar = pManRst->dd->vars[1];
772  bCofE = Cudd_Cofactor( pManRst->dd, bLocal, Cudd_Not(bVar) ); Cudd_Ref( bCofE );
773  bCofT = Cudd_Cofactor( pManRst->dd, bLocal, bVar ); Cudd_Ref( bCofT );
774  if ( !Extra_bddIsVar(bCofE) || !Extra_bddIsVar(bCofT) )
775  {
776  Cudd_RecursiveDeref( pManRst->dd, bCofE );
777  Cudd_RecursiveDeref( pManRst->dd, bCofT );
778  bVar = pManRst->dd->vars[2];
779  bCofE = Cudd_Cofactor( pManRst->dd, bLocal, Cudd_Not(bVar) ); Cudd_Ref( bCofE );
780  bCofT = Cudd_Cofactor( pManRst->dd, bLocal, bVar ); Cudd_Ref( bCofT );
781  if ( !Extra_bddIsVar(bCofE) || !Extra_bddIsVar(bCofT) )
782  {
783  Cudd_RecursiveDeref( pManRst->dd, bCofE );
784  Cudd_RecursiveDeref( pManRst->dd, bCofT );
785  Cudd_RecursiveDeref( pManRst->dd, bLocal );
786  Vec_IntFree( vEdges );
787  return eQuit;
788  }
789  }
790  }
791  Cudd_RecursiveDeref( pManRst->dd, bLocal );
792  // we found the control variable (bVar) and the var-cofactors (bCofT, bCofE)
793 
794  // find the graph nodes
795  eNode1 = Dec_IntToEdge( Vec_IntEntry(vEdges, bVar->index) );
796  eNode2 = Dec_IntToEdge( Vec_IntEntry(vEdges, Cudd_Regular(bCofT)->index) );
797  eNode3 = Dec_IntToEdge( Vec_IntEntry(vEdges, Cudd_Regular(bCofE)->index) );
798  // add the complements to the graph nodes
799  eNode2.fCompl ^= Cudd_IsComplement(bCofT);
800  eNode3.fCompl ^= Cudd_IsComplement(bCofE);
801 
802  // because the cofactors are vars, we can just as well deref them here
803  Cudd_RecursiveDeref( pManRst->dd, bCofE );
804  Cudd_RecursiveDeref( pManRst->dd, bCofT );
805 
806  // find the ABC nodes
807  pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc;
808  pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc;
809  pNode3 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode3.Node )->pFunc;
810  pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl );
811  pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl );
812  pNode3 = !pNode3? NULL : Abc_ObjNotCond( pNode3, eNode3.fCompl );
813 
814  // check if the new node exists
815  Type = 0;
816  pNode4 = NULL;
817  if ( pNode1 && pNode2 && pNode3 )
818  pNode4 = Abc_AigMuxLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2, pNode3, &Type );
819 
820  // create the new node
821  eResult = Dec_GraphAddNodeMux( pGraph, eNode1, eNode2, eNode3, Type ); // should have the same structure as AIG
822 
823  // set level
824  Level1 = Dec_GraphNode( pGraph, eNode1.Node )->Level;
825  Level2 = Dec_GraphNode( pGraph, eNode2.Node )->Level;
826  Level3 = Dec_GraphNode( pGraph, eNode3.Node )->Level;
827  Dec_GraphNode( pGraph, eResult.Node )->Level = 2 + Abc_MaxInt( Abc_MaxInt(Level1, Level2), Level3 );
828  // get the new node if possible
829  if ( pNode4 )
830  {
831  Dec_GraphNode( pGraph, eResult.Node )->pFunc = Abc_ObjNotCond(pNode4, eResult.fCompl);
832  Level4 = Dec_GraphNode( pGraph, eResult.Node )->Level;
833  assert( Required == ABC_INFINITY || Level4 == (int)Abc_ObjRegular(pNode4)->Level );
834  }
835  if ( !pNode4 || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pNode4)) )
836  {
837  (*pnNodesAdded)++;
838  if ( Type == 0 )
839  {
840  if ( !pNode1 || !pNode2 )
841  (*pnNodesAdded)++;
842  else
843  {
844  pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2 );
845  if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
846  (*pnNodesAdded)++;
847  }
848  if ( !pNode1 || !pNode3 )
849  (*pnNodesAdded)++;
850  else
851  {
852  pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), pNode3 );
853  if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
854  (*pnNodesAdded)++;
855  }
856  }
857  else
858  {
859  if ( !pNode1 || !pNode2 )
860  (*pnNodesAdded)++;
861  else
862  {
863  pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, Abc_ObjNot(pNode2) );
864  if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
865  (*pnNodesAdded)++;
866  }
867  if ( !pNode1 || !pNode3 )
868  (*pnNodesAdded)++;
869  else
870  {
871  pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode3) );
872  if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
873  (*pnNodesAdded)++;
874  }
875  }
876  if ( *pnNodesAdded > nNodesSaved )
877  {
878  Vec_IntFree( vEdges );
879  return eQuit;
880  }
881  }
882 
883  Vec_IntFree( vEdges );
884  // complement the graph if the node was complemented
885  eResult.fCompl ^= fCompl;
886  return eResult;
887  }
888  Vec_IntFree( vEdges );
889  return eQuit;
890 }
891 
892 /**Function*************************************************************
893 
894  Synopsis [Evaluation one DSD.]
895 
896  Description []
897 
898  SideEffects []
899 
900  SeeAlso []
901 
902 ***********************************************************************/
903 Dec_Graph_t * Abc_NodeEvaluateDsd( Abc_ManRst_t * pManRst, Dsd_Node_t * pNodeDsd, Abc_Obj_t * pRoot, int Required, int nNodesSaved, int * pnNodesAdded )
904 {
905  Dec_Graph_t * pGraph;
906  Dec_Edge_t gEdge;
907  Abc_Obj_t * pLeaf;
908  Dec_Node_t * pNode;
909  int i;
910 
911  // create the graph and set the leaves
912  pGraph = Dec_GraphCreate( Vec_PtrSize(pManRst->vLeaves) );
913  Dec_GraphForEachLeaf( pGraph, pNode, i )
914  {
915  pLeaf = (Abc_Obj_t *)Vec_PtrEntry( pManRst->vLeaves, i );
916  pNode->pFunc = pLeaf;
917  pNode->Level = pLeaf->Level;
918  }
919 
920  // create the decomposition structure from the DSD
921  *pnNodesAdded = 0;
922  gEdge = Abc_NodeEvaluateDsd_rec( pGraph, pManRst, pNodeDsd, Required, nNodesSaved, pnNodesAdded );
923  if ( gEdge.Node > 1000 ) // infeasible
924  {
925  *pnNodesAdded = -1;
926  Dec_GraphFree( pGraph );
927  return NULL;
928  }
929 
930  // quit if the root node is the same
931  pLeaf = (Abc_Obj_t *)Dec_GraphNode( pGraph, gEdge.Node )->pFunc;
932  if ( Abc_ObjRegular(pLeaf) == pRoot )
933  {
934  *pnNodesAdded = -1;
935  Dec_GraphFree( pGraph );
936  return NULL;
937  }
938 
939  Dec_GraphSetRoot( pGraph, gEdge );
940  return pGraph;
941 }
942 
943 
944 
945 /**Function*************************************************************
946 
947  Synopsis [Starts the cut manager for rewriting.]
948 
949  Description []
950 
951  SideEffects []
952 
953  SeeAlso []
954 
955 ***********************************************************************/
956 Cut_Man_t * Abc_NtkStartCutManForRestruct( Abc_Ntk_t * pNtk, int nCutMax, int fDag )
957 {
958  static Cut_Params_t Params, * pParams = &Params;
959  Cut_Man_t * pManCut;
960  Abc_Obj_t * pObj;
961  int i;
962  // start the cut manager
963  memset( pParams, 0, sizeof(Cut_Params_t) );
964  pParams->nVarsMax = nCutMax; // the max cut size ("k" of the k-feasible cuts)
965  pParams->nKeepMax = 250; // the max number of cuts kept at a node
966  pParams->fTruth = 0; // compute truth tables
967  pParams->fFilter = 1; // filter dominated cuts
968  pParams->fSeq = 0; // compute sequential cuts
969  pParams->fDrop = 0; // drop cuts on the fly
970  pParams->fDag = fDag; // compute DAG cuts
971  pParams->fTree = 0; // compute tree cuts
972  pParams->fVerbose = 0; // the verbosiness flag
973  pParams->nIdsMax = Abc_NtkObjNumMax( pNtk );
974  pManCut = Cut_ManStart( pParams );
975  if ( pParams->fDrop )
976  Cut_ManSetFanoutCounts( pManCut, Abc_NtkFanoutCounts(pNtk) );
977  // set cuts for PIs
978  Abc_NtkForEachCi( pNtk, pObj, i )
979  if ( Abc_ObjFanoutNum(pObj) > 0 )
980  Cut_NodeSetTriv( pManCut, pObj->Id );
981  return pManCut;
982 }
983 
984 /**Function*************************************************************
985 
986  Synopsis [Starts the resynthesis manager.]
987 
988  Description []
989 
990  SideEffects []
991 
992  SeeAlso []
993 
994 ***********************************************************************/
995 Abc_ManRst_t * Abc_NtkManRstStart( int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose )
996 {
997  Abc_ManRst_t * p;
998  p = ABC_ALLOC( Abc_ManRst_t, 1 );
999  memset( p, 0, sizeof(Abc_ManRst_t) );
1000  // set the parameters
1001  p->nCutMax = nCutMax;
1002  p->fUpdateLevel = fUpdateLevel;
1003  p->fUseZeros = fUseZeros;
1004  p->fVerbose = fVerbose;
1005  // start the BDD manager
1006  p->dd = Cudd_Init( p->nCutMax, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 );
1007  Cudd_zddVarsFromBddVars( p->dd, 2 );
1008  // start the DSD manager
1009  p->pManDsd = Dsd_ManagerStart( p->dd, p->dd->size, 0 );
1010  // other temp datastructures
1011  p->vVisited = Vec_PtrAlloc( 100 );
1012  p->vLeaves = Vec_PtrAlloc( 100 );
1013  p->vDecs = Vec_PtrAlloc( 100 );
1014  p->vTemp = Vec_PtrAlloc( 100 );
1015  p->vSims = Vec_IntAlloc( 100 );
1016  p->vOnes = Vec_IntAlloc( 100 );
1017  p->vBinate = Vec_IntAlloc( 100 );
1018  p->vTwos = Vec_IntAlloc( 100 );
1019  p->vRands = Vec_IntAlloc( 20 );
1020 
1021  {
1022  int i;
1023  for ( i = 0; i < 20; i++ )
1024  Vec_IntPush( p->vRands, (int)RST_RANDOM_UNSIGNED );
1025  }
1026  return p;
1027 }
1028 
1029 /**Function*************************************************************
1030 
1031  Synopsis [Stops the resynthesis manager.]
1032 
1033  Description []
1034 
1035  SideEffects []
1036 
1037  SeeAlso []
1038 
1039 ***********************************************************************/
1040 void Abc_NtkManRstStop( Abc_ManRst_t * p )
1041 {
1042  Dsd_ManagerStop( p->pManDsd );
1043  Extra_StopManager( p->dd );
1044  Vec_PtrFree( p->vDecs );
1045  Vec_PtrFree( p->vLeaves );
1046  Vec_PtrFree( p->vVisited );
1047  Vec_PtrFree( p->vTemp );
1048  Vec_IntFree( p->vSims );
1049  Vec_IntFree( p->vOnes );
1050  Vec_IntFree( p->vBinate );
1051  Vec_IntFree( p->vTwos );
1052  Vec_IntFree( p->vRands );
1053  ABC_FREE( p );
1054 }
1055 
1056 /**Function*************************************************************
1057 
1058  Synopsis [Stops the resynthesis manager.]
1059 
1060  Description []
1061 
1062  SideEffects []
1063 
1064  SeeAlso []
1065 
1066 ***********************************************************************/
1067 void Abc_NtkManRstPrintStats( Abc_ManRst_t * p )
1068 {
1069  printf( "Refactoring statistics:\n" );
1070  printf( "Nodes considered = %8d.\n", p->nNodesConsidered );
1071  printf( "Cuts considered = %8d.\n", p->nCutsConsidered );
1072  printf( "Cuts explored = %8d.\n", p->nCutsExplored );
1073  printf( "Nodes restructured = %8d.\n", p->nNodesRestructured );
1074  printf( "Calculated gain = %8d.\n", p->nNodesGained );
1075  ABC_PRT( "Cuts ", p->timeCut );
1076  ABC_PRT( "Resynthesis", p->timeRes );
1077  ABC_PRT( " BDD ", p->timeBdd );
1078  ABC_PRT( " DSD ", p->timeDsd );
1079  ABC_PRT( " Eval ", p->timeEval );
1080  ABC_PRT( "AIG update ", p->timeNtk );
1081  ABC_PRT( "TOTAL ", p->timeTotal );
1082 }
1083 
1084 
1085 /**Function*************************************************************
1086 
1087  Synopsis []
1088 
1089  Description []
1090 
1091  SideEffects []
1092 
1093  SeeAlso []
1094 
1095 ***********************************************************************/
1096 int Abc_Abc_NodeResubCollectDivs( Abc_ManRst_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut )
1097 {
1098  Abc_Obj_t * pNode, * pFanout;
1099  int i, k;
1100  // collect the leaves of the cut
1101  Vec_PtrClear( p->vDecs );
1102  Abc_NtkIncrementTravId( pRoot->pNtk );
1103  for ( i = 0; i < (int)pCut->nLeaves; i++ )
1104  {
1105  pNode = Abc_NtkObj(pRoot->pNtk, pCut->pLeaves[i]);
1106  if ( pNode == NULL ) // the so-called "bad cut phenomenon" is due to removed nodes
1107  return 0;
1108  Vec_PtrPush( p->vDecs, pNode );
1109  Abc_NodeSetTravIdCurrent( pNode );
1110  }
1111  // explore the fanouts
1112  Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pNode, i )
1113  {
1114  // if the fanout has both fanins in the set, add it
1115  Abc_ObjForEachFanout( pNode, pFanout, k )
1116  {
1117  if ( Abc_NodeIsTravIdCurrent(pFanout) || Abc_ObjIsPo(pFanout) )
1118  continue;
1119  if ( Abc_NodeIsTravIdCurrent(Abc_ObjFanin0(pFanout)) && Abc_NodeIsTravIdCurrent(Abc_ObjFanin1(pFanout)) )
1120  {
1121  Vec_PtrPush( p->vDecs, pFanout );
1122  Abc_NodeSetTravIdCurrent( pFanout );
1123  }
1124  }
1125  }
1126  return 1;
1127 }
1128 
1129 /**Function*************************************************************
1130 
1131  Synopsis []
1132 
1133  Description []
1134 
1135  SideEffects []
1136 
1137  SeeAlso []
1138 
1139 ***********************************************************************/
1140 int Abc_NodeResubMffc_rec( Abc_Obj_t * pNode )
1141 {
1142  if ( Abc_NodeIsTravIdCurrent(pNode) )
1143  return 0;
1144  Abc_NodeSetTravIdCurrent( pNode );
1145  return 1 + Abc_NodeResubMffc_rec( Abc_ObjFanin0(pNode) ) +
1146  Abc_NodeResubMffc_rec( Abc_ObjFanin1(pNode) );
1147 }
1148 
1149 /**Function*************************************************************
1150 
1151  Synopsis []
1152 
1153  Description []
1154 
1155  SideEffects []
1156 
1157  SeeAlso []
1158 
1159 ***********************************************************************/
1160 int Abc_NodeResubMffc( Abc_ManRst_t * p, Vec_Ptr_t * vDecs, int nLeaves, Abc_Obj_t * pRoot )
1161 {
1162  Abc_Obj_t * pObj;
1163  int Counter, i, k;
1164  // increment the traversal ID for the leaves
1165  Abc_NtkIncrementTravId( pRoot->pNtk );
1166  // label the leaves
1167  Vec_PtrForEachEntryStop( Abc_Obj_t *, vDecs, pObj, i, nLeaves )
1168  Abc_NodeSetTravIdCurrent( pObj );
1169  // make sure the node is in the cone and is no one of the leaves
1170  assert( Abc_NodeIsTravIdPrevious(pRoot) );
1171  Counter = Abc_NodeResubMffc_rec( pRoot );
1172  // move the labeled nodes to the end
1173  Vec_PtrClear( p->vTemp );
1174  k = 0;
1175  Vec_PtrForEachEntryStart( Abc_Obj_t *, vDecs, pObj, i, nLeaves )
1176  if ( Abc_NodeIsTravIdCurrent(pObj) )
1177  Vec_PtrPush( p->vTemp, pObj );
1178  else
1179  Vec_PtrWriteEntry( vDecs, k++, pObj );
1180  // add the labeled nodes
1181  Vec_PtrForEachEntry( Abc_Obj_t *, p->vTemp, pObj, i )
1182  Vec_PtrWriteEntry( vDecs, k++, pObj );
1183  assert( k == Vec_PtrSize(p->vDecs) );
1184  assert( pRoot == Vec_PtrEntryLast(p->vDecs) );
1185  return Counter;
1186 }
1187 
1188 /**Function*************************************************************
1189 
1190  Synopsis [Performs simulation.]
1191 
1192  Description []
1193 
1194  SideEffects []
1195 
1196  SeeAlso []
1197 
1198 ***********************************************************************/
1199 void Abc_NodeMffcSimulate( Vec_Ptr_t * vDecs, int nLeaves, Vec_Int_t * vRands, Vec_Int_t * vSims )
1200 {
1201  Abc_Obj_t * pObj;
1202  unsigned uData0, uData1, uData;
1203  int i;
1204  // initialize random simulation data
1205  Vec_IntClear( vSims );
1206  Vec_PtrForEachEntryStop( Abc_Obj_t *, vDecs, pObj, i, nLeaves )
1207  {
1208  uData = (unsigned)Vec_IntEntry( vRands, i );
1209  pObj->pData = (void *)(ABC_PTRUINT_T)uData;
1210  Vec_IntPush( vSims, uData );
1211  }
1212  // simulate
1213  Vec_PtrForEachEntryStart( Abc_Obj_t *, vDecs, pObj, i, nLeaves )
1214  {
1215  uData0 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pData;
1216  uData1 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin1(pObj)->pData;
1217  uData = (Abc_ObjFaninC0(pObj)? ~uData0 : uData0) & (Abc_ObjFaninC1(pObj)? ~uData1 : uData1);
1218  pObj->pData = (void *)(ABC_PTRUINT_T)uData;
1219  Vec_IntPush( vSims, uData );
1220  }
1221 }
1222 
1223 /**Function*************************************************************
1224 
1225  Synopsis [Full equality check.]
1226 
1227  Description []
1228 
1229  SideEffects []
1230 
1231  SeeAlso []
1232 
1233 ***********************************************************************/
1234 int Abc_NodeCheckFull( Abc_ManRst_t * p, Dec_Graph_t * pGraph )
1235 {
1236  return 1;
1237 }
1238 /**Function*************************************************************
1239 
1240  Synopsis [Detect contants.]
1241 
1242  Description []
1243 
1244  SideEffects []
1245 
1246  SeeAlso []
1247 
1248 ***********************************************************************/
1249 Dec_Graph_t * Abc_NodeMffcConstants( Abc_ManRst_t * p, Vec_Int_t * vSims )
1250 {
1251  Dec_Graph_t * pGraph = NULL;
1252  unsigned uRoot;
1253  // get the root node
1254  uRoot = (unsigned)Vec_IntEntryLast( vSims );
1255  // get the graph if the node looks constant
1256  if ( uRoot == 0 )
1257  pGraph = Dec_GraphCreateConst0();
1258  else if ( uRoot == ~(unsigned)0 )
1259  pGraph = Dec_GraphCreateConst1();
1260  // check the graph
1261  assert(pGraph);
1262  if ( Abc_NodeCheckFull( p, pGraph ) )
1263  return pGraph;
1264  Dec_GraphFree( pGraph );
1265  return NULL;
1266 }
1267 
1268 /**Function*************************************************************
1269 
1270  Synopsis [Detect single non-overlaps.]
1271 
1272  Description []
1273 
1274  SideEffects []
1275 
1276  SeeAlso []
1277 
1278 ***********************************************************************/
1279 Dec_Graph_t * Abc_NodeMffcSingleVar( Abc_ManRst_t * p, Vec_Int_t * vSims, int nNodes, Vec_Int_t * vOnes )
1280 {
1281  Dec_Graph_t * pGraph;
1282  unsigned uRoot, uNode;
1283  int i;
1284 
1285  Vec_IntClear( vOnes );
1286  Vec_IntClear( p->vBinate );
1287  uRoot = (unsigned)Vec_IntEntryLast( vSims );
1288  for ( i = 0; i < nNodes; i++ )
1289  {
1290  uNode = (unsigned)Vec_IntEntry( vSims, i );
1291  if ( uRoot == uNode || uRoot == ~uNode )
1292  {
1293  pGraph = Dec_GraphCreate( 1 );
1294  Dec_GraphNode( pGraph, 0 )->pFunc = Vec_PtrEntry( p->vDecs, i );
1295  Dec_GraphSetRoot( pGraph, Dec_IntToEdge( (int)(uRoot == ~uNode) ) );
1296  // check the graph
1297  if ( Abc_NodeCheckFull( p, pGraph ) )
1298  return pGraph;
1299  Dec_GraphFree( pGraph );
1300  }
1301  if ( (uRoot & uNode) == 0 )
1302  Vec_IntPush( vOnes, i << 1 );
1303  else if ( (uRoot & ~uNode) == 0 )
1304  Vec_IntPush( vOnes, (i << 1) + 1 );
1305  else
1306  Vec_IntPush( p->vBinate, i );
1307  }
1308  return NULL;
1309 }
1310 
1311 /**Function*************************************************************
1312 
1313  Synopsis [Detect single non-overlaps.]
1314 
1315  Description []
1316 
1317  SideEffects []
1318 
1319  SeeAlso []
1320 
1321 ***********************************************************************/
1322 Dec_Graph_t * Abc_NodeMffcSingleNode( Abc_ManRst_t * p, Vec_Int_t * vSims, int nNodes, Vec_Int_t * vOnes )
1323 {
1324  Dec_Graph_t * pGraph;
1325  Dec_Edge_t eNode0, eNode1, eRoot;
1326  unsigned uRoot;
1327  int i, k;
1328  uRoot = (unsigned)Vec_IntEntryLast( vSims );
1329  for ( i = 0; i < vOnes->nSize; i++ )
1330  for ( k = i+1; k < vOnes->nSize; k++ )
1331  if ( ~uRoot == ((unsigned)vOnes->pArray[i] | (unsigned)vOnes->pArray[k]) )
1332  {
1333  eNode0 = Dec_IntToEdge( vOnes->pArray[i] ^ 1 );
1334  eNode1 = Dec_IntToEdge( vOnes->pArray[k] ^ 1 );
1335  pGraph = Dec_GraphCreate( 2 );
1336  Dec_GraphNode( pGraph, 0 )->pFunc = Vec_PtrEntry( p->vDecs, eNode0.Node );
1337  Dec_GraphNode( pGraph, 1 )->pFunc = Vec_PtrEntry( p->vDecs, eNode1.Node );
1338  eRoot = Dec_GraphAddNodeAnd( pGraph, eNode0, eNode1 );
1339  Dec_GraphSetRoot( pGraph, eRoot );
1340  if ( Abc_NodeCheckFull( p, pGraph ) )
1341  return pGraph;
1342  Dec_GraphFree( pGraph );
1343  }
1344  return NULL;
1345 }
1346 
1347 /**Function*************************************************************
1348 
1349  Synopsis [Detect single non-overlaps.]
1350 
1351  Description []
1352 
1353  SideEffects []
1354 
1355  SeeAlso []
1356 
1357 ***********************************************************************/
1358 Dec_Graph_t * Abc_NodeMffcDoubleNode( Abc_ManRst_t * p, Vec_Int_t * vSims, int nNodes, Vec_Int_t * vOnes )
1359 {
1360 // Dec_Graph_t * pGraph;
1361 // unsigned uRoot, uNode;
1362 // int i;
1363 
1364 
1365  return NULL;
1366 }
1367 
1368 /**Function*************************************************************
1369 
1370  Synopsis [Evaluates resubstution of one cut.]
1371 
1372  Description [Returns the graph to add if any.]
1373 
1374  SideEffects []
1375 
1376  SeeAlso []
1377 
1378 ***********************************************************************/
1379 Dec_Graph_t * Abc_NodeResubEval( Abc_ManRst_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut )
1380 {
1381  Dec_Graph_t * pGraph;
1382  int nNodesSaved;
1383 
1384  // collect the nodes in the cut
1385  if ( !Abc_Abc_NodeResubCollectDivs( p, pRoot, pCut ) )
1386  return NULL;
1387 
1388  // label MFFC and count its size
1389  nNodesSaved = Abc_NodeResubMffc( p, p->vDecs, pCut->nLeaves, pRoot );
1390  assert( nNodesSaved > 0 );
1391 
1392  // simulate MFFC
1393  Abc_NodeMffcSimulate( p->vDecs, pCut->nLeaves, p->vRands, p->vSims );
1394 
1395  // check for constant output
1396  pGraph = Abc_NodeMffcConstants( p, p->vSims );
1397  if ( pGraph )
1398  {
1399  p->nNodesGained += nNodesSaved;
1400  p->nNodesRestructured++;
1401  return pGraph;
1402  }
1403 
1404  // check for one literal (fill up the ones array)
1405  pGraph = Abc_NodeMffcSingleVar( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved, p->vOnes );
1406  if ( pGraph )
1407  {
1408  p->nNodesGained += nNodesSaved;
1409  p->nNodesRestructured++;
1410  return pGraph;
1411  }
1412  if ( nNodesSaved == 1 )
1413  return NULL;
1414 
1415  // look for one node
1416  pGraph = Abc_NodeMffcSingleNode( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved, p->vOnes );
1417  if ( pGraph )
1418  {
1419  p->nNodesGained += nNodesSaved - 1;
1420  p->nNodesRestructured++;
1421  return pGraph;
1422  }
1423  if ( nNodesSaved == 2 )
1424  return NULL;
1425 
1426  // look for two nodes
1427  pGraph = Abc_NodeMffcDoubleNode( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved, p->vOnes );
1428  if ( pGraph )
1429  {
1430  p->nNodesGained += nNodesSaved - 2;
1431  p->nNodesRestructured++;
1432  return pGraph;
1433  }
1434  if ( nNodesSaved == 3 )
1435  return NULL;
1436 /*
1437  // look for MUX/EXOR
1438  pGraph = Abc_NodeMffcMuxNode( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved );
1439  if ( pGraph )
1440  {
1441  p->nNodesGained += nNodesSaved - 1;
1442  p->nNodesRestructured++;
1443  return pGraph;
1444  }
1445 */
1446  return NULL;
1447 }
1448 
1449 /**Function*************************************************************
1450 
1451  Synopsis [Performs resubstution.]
1452 
1453  Description []
1454 
1455  SideEffects []
1456 
1457  SeeAlso []
1458 
1459 ***********************************************************************/
1460 Dec_Graph_t * Abc_NodeResubstitute( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList )
1461 {
1462  Dec_Graph_t * pGraph, * pGraphBest = NULL;
1463  Cut_Cut_t * pCut;
1464  int nCuts;
1465  p->nNodesConsidered++;
1466 
1467  // count the number of cuts with four inputs or more
1468  nCuts = 0;
1469  for ( pCut = pCutList; pCut; pCut = pCut->pNext )
1470  nCuts += (int)(pCut->nLeaves > 3);
1471  printf( "-----------------------------------\n" );
1472  printf( "Node %6d : Factor-cuts = %5d.\n", pNode->Id, nCuts );
1473 
1474  // go through the interesting cuts
1475  for ( pCut = pCutList; pCut; pCut = pCut->pNext )
1476  {
1477  if ( pCut->nLeaves < 4 )
1478  continue;
1479  pGraph = Abc_NodeResubEval( p, pNode, pCut );
1480  if ( pGraph == NULL )
1481  continue;
1482  if ( !pGraphBest || Dec_GraphNodeNum(pGraph) < Dec_GraphNodeNum(pGraphBest) )
1483  {
1484  if ( pGraphBest )
1485  Dec_GraphFree(pGraphBest);
1486  pGraphBest = pGraph;
1487  }
1488  else
1489  Dec_GraphFree(pGraph);
1490  }
1491  return pGraphBest;
1492 }
1493 
1494 ////////////////////////////////////////////////////////////////////////
1495 /// END OF FILE ///
1496 ////////////////////////////////////////////////////////////////////////
1497 
1498 
1499 ABC_NAMESPACE_IMPL_END
1500 
memset
char * memset()
Cut_ParamsStruct_t_::nKeepMax
int nKeepMax
Definition: cut.h:56
Abc_NodeConeBdd
DdNode * Abc_NodeConeBdd(DdManager *dd, DdNode **pbVars, Abc_Obj_t *pRoot, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vVisited)
Definition: abcReconv.c:498
Abc_NtkIsStrash
static int Abc_NtkIsStrash(Abc_Ntk_t *pNtk)
Definition: abc.h:251
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Dec_EdgeToInt
static unsigned Dec_EdgeToInt(Dec_Edge_t eEdge)
Definition: dec.h:151
Abc_ObjFanin1
static Abc_Obj_t * Abc_ObjFanin1(Abc_Obj_t *pObj)
Definition: abc.h:374
CUDD_UNIQUE_SLOTS
#define CUDD_UNIQUE_SLOTS
Definition: cudd.h:97
Abc_ManRst_t_::dd
DdManager * dd
Definition: abcRestruct.c:47
Abc_AigAndLookup
ABC_DLL Abc_Obj_t * Abc_AigAndLookup(Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1)
Definition: abcAig.c:403
Abc_NodeMffcSingleVar
Dec_Graph_t * Abc_NodeMffcSingleVar(Abc_ManRst_t *p, Vec_Int_t *vSims, int nNodes, Vec_Int_t *vOnes)
Definition: abcRestruct.c:1279
Cudd_RecursiveDeref
void Cudd_RecursiveDeref(DdManager *table, DdNode *n)
Definition: cuddRef.c:154
Vec_PtrForEachEntryStart
#define Vec_PtrForEachEntryStart(Type, vVec, pEntry, i, Start)
Definition: vecPtr.h:57
Dec_GraphNodeNum
static int Dec_GraphNodeNum(Dec_Graph_t *pGraph)
Definition: dec.h:421
DdNode
Definition: cudd.h:278
Dsd_ManagerStop
void Dsd_ManagerStop(Dsd_Manager_t *dMan)
Definition: dsdMan.c:100
Cudd_Not
#define Cudd_Not(node)
Definition: cudd.h:367
Abc_NtkObjNumMax
static int Abc_NtkObjNumMax(Abc_Ntk_t *pNtk)
Definition: abc.h:284
Abc_ManRst_t_::vRands
Vec_Int_t * vRands
Definition: abcRestruct.c:54
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Dec_GraphAddNodeMux
static Dec_Edge_t Dec_GraphAddNodeMux(Dec_Graph_t *pGraph, Dec_Edge_t eEdgeC, Dec_Edge_t eEdgeT, Dec_Edge_t eEdgeE, int Type)
Definition: dec.h:684
Abc_ObjFaninC1
static int Abc_ObjFaninC1(Abc_Obj_t *pObj)
Definition: abc.h:378
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Abc_ManRst_t_::nLastGain
int nLastGain
Definition: abcRestruct.c:59
Abc_ManRst_t_::vLeaves
Vec_Ptr_t * vLeaves
Definition: abcRestruct.c:50
Abc_ManRst_t_::timeBdd
int timeBdd
Definition: abcRestruct.c:67
Cut_ParamsStruct_t_::nVarsMax
int nVarsMax
Definition: cut.h:55
Cut_ParamsStruct_t_::nIdsMax
int nIdsMax
Definition: cut.h:57
DdManager::size
int size
Definition: cuddInt.h:361
Abc_ManRst_t_::vSims
Vec_Int_t * vSims
Definition: abcRestruct.c:53
Abc_Ntk_t_
Definition: abc.h:153
Abc_ObjFanoutNum
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
Cudd_IsConstant
#define Cudd_IsConstant(node)
Definition: cudd.h:352
Abc_ManRst_t_::vOnes
Vec_Int_t * vOnes
Definition: abcRestruct.c:55
Cudd_Regular
#define Cudd_Regular(node)
Definition: cudd.h:397
Abc_ManRst_t_
Definition: abcRestruct.c:37
Abc_NtkManRstStart
static Abc_ManRst_t * Abc_NtkManRstStart(int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose)
Definition: abcRestruct.c:995
Abc_ManRst_t_::vTemp
Vec_Ptr_t * vTemp
Definition: abcRestruct.c:52
Abc_ManRst_t_::fVerbose
int fVerbose
Definition: abcRestruct.c:45
Dsd_NodeReadDecsNum
int Dsd_NodeReadDecsNum(Dsd_Node_t *p)
Definition: dsdApi.c:58
Abc_NodeCheckFull
int Abc_NodeCheckFull(Abc_ManRst_t *p, Dec_Graph_t *pGraph)
Definition: abcRestruct.c:1234
Dec_EdgeCreate
static Dec_Edge_t Dec_EdgeCreate(int Node, int fCompl)
FUNCTION DEFINITIONS ///.
Definition: dec.h:134
Cut_CutStruct_t_::pNext
Cut_Cut_t * pNext
Definition: cut.h:88
Dec_GraphUpdateNetwork
void Dec_GraphUpdateNetwork(Abc_Obj_t *pRoot, Dec_Graph_t *pGraph, int fUpdateLevel, int nGain)
Definition: decAbc.c:240
Abc_ObjFaninC0
static int Abc_ObjFaninC0(Abc_Obj_t *pObj)
Definition: abc.h:377
CUDD_CACHE_SLOTS
#define CUDD_CACHE_SLOTS
Definition: cudd.h:98
Abc_AigMuxLookup
ABC_DLL Abc_Obj_t * Abc_AigMuxLookup(Abc_Aig_t *pMan, Abc_Obj_t *pC, Abc_Obj_t *pT, Abc_Obj_t *pE, int *pType)
Definition: abcAig.c:508
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Dec_Edge_t
typedefABC_NAMESPACE_HEADER_START struct Dec_Edge_t_ Dec_Edge_t
INCLUDES ///.
Definition: dec.h:42
Abc_NodeRestructureCut
static Dec_Graph_t * Abc_NodeRestructureCut(Abc_ManRst_t *p, Abc_Obj_t *pNode, Cut_Cut_t *pCut)
Definition: abcRestruct.c:319
Abc_NodeMffcLabelAig
ABC_DLL int Abc_NodeMffcLabelAig(Abc_Obj_t *pNode)
Definition: abcRefs.c:100
Abc_NtkCheck
ABC_DLL int Abc_NtkCheck(Abc_Ntk_t *pNtk)
FUNCTION DEFINITIONS ///.
Definition: abcCheck.c:61
Cut_ParamsStruct_t_::fTruth
int fTruth
Definition: cut.h:60
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Abc_NodeIsTravIdPrevious
static int Abc_NodeIsTravIdPrevious(Abc_Obj_t *p)
Definition: abc.h:412
Extra_StopManager
void Extra_StopManager(DdManager *dd)
Definition: extraBddMisc.c:223
Cut_NodeSetTriv
void Cut_NodeSetTriv(Cut_Man_t *p, int Node)
Definition: cutApi.c:145
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
RST_RANDOM_UNSIGNED
#define RST_RANDOM_UNSIGNED
DECLARATIONS ///.
Definition: abcRestruct.c:34
Abc_NtkObj
static Abc_Obj_t * Abc_NtkObj(Abc_Ntk_t *pNtk, int i)
Definition: abc.h:314
Abc_NodeEdgeDsdPushOrdered
void Abc_NodeEdgeDsdPushOrdered(Dec_Graph_t *pGraph, Vec_Int_t *vEdges, int Edge)
Definition: abcRestruct.c:557
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Abc_NodeEdgeDsdPermute
void Abc_NodeEdgeDsdPermute(Dec_Graph_t *pGraph, Abc_ManRst_t *pManRst, Vec_Int_t *vEdges, int fExor)
Definition: abcRestruct.c:483
Abc_NodeResubMffc_rec
int Abc_NodeResubMffc_rec(Abc_Obj_t *pNode)
Definition: abcRestruct.c:1140
Abc_ObjFanin0
static Abc_Obj_t * Abc_ObjFanin0(Abc_Obj_t *pObj)
Definition: abc.h:373
Cut_ManSetFanoutCounts
void Cut_ManSetFanoutCounts(Cut_Man_t *p, Vec_Int_t *vFanCounts)
Definition: cutMan.c:229
Abc_ManRst_t_::nCutMax
int nCutMax
Definition: abcRestruct.c:42
Dec_IntToEdge
static Dec_Edge_t Dec_IntToEdge(unsigned Edge)
Definition: dec.h:167
Abc_Aig_t_
DECLARATIONS ///.
Definition: abcAig.c:52
Dec_GraphCreateConst1
static Dec_Graph_t * Dec_GraphCreateConst1()
Definition: dec.h:266
Abc_ManRst_t_::timeTotal
int timeTotal
Definition: abcRestruct.c:72
Abc_NtkStopReverseLevels
ABC_DLL void Abc_NtkStopReverseLevels(Abc_Ntk_t *pNtk)
Definition: abcTiming.c:1190
Abc_Obj_t_::Level
unsigned Level
Definition: abc.h:142
Abc_NodeRestructure
static Dec_Graph_t * Abc_NodeRestructure(Abc_ManRst_t *p, Abc_Obj_t *pNode, Cut_Cut_t *pCutList)
Definition: abcRestruct.c:283
Dec_GraphAddNodeAnd
static Dec_Edge_t Dec_GraphAddNodeAnd(Dec_Graph_t *pGraph, Dec_Edge_t eEdge0, Dec_Edge_t eEdge1)
Definition: dec.h:591
Dec_Node_t_
Definition: dec.h:50
Abc_NtkReassignIds
ABC_DLL void Abc_NtkReassignIds(Abc_Ntk_t *pNtk)
Definition: abcUtil.c:1769
Abc_Obj_t_
Definition: abc.h:128
Abc_ManRst_t_::nNodesGained
int nNodesGained
Definition: abcRestruct.c:64
Cut_ParamsStruct_t_::fSeq
int fSeq
Definition: cut.h:62
Cut_ParamsStruct_t_::fDag
int fDag
Definition: cut.h:64
Vec_IntWriteEntry
static void Vec_IntWriteEntry(Vec_Int_t *p, int i, int Entry)
Definition: bblif.c:285
Abc_ManRst_t_::vBinate
Vec_Int_t * vBinate
Definition: abcRestruct.c:56
Abc_Ntk_t_::pManFunc
void * pManFunc
Definition: abc.h:191
Cut_CutStruct_t_::pLeaves
int pLeaves[0]
Definition: cut.h:89
Abc_ManRst_t_::timeRes
int timeRes
Definition: abcRestruct.c:70
Cut_CutStruct_t_::nLeaves
unsigned nLeaves
Definition: cut.h:84
ProgressBarStruct
DECLARATIONS ///.
Definition: extraUtilProgress.c:32
Cudd_IsComplement
#define Cudd_IsComplement(node)
Definition: cudd.h:425
Cut_ParamsStruct_t_::fFilter
int fFilter
Definition: cut.h:61
Cudd_Cofactor
DdNode * Cudd_Cofactor(DdManager *dd, DdNode *f, DdNode *g)
Definition: cuddCof.c:123
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Abc_ManRst_t_::nCutsExplored
int nCutsExplored
Definition: abcRestruct.c:61
Abc_RestructNodeDivisors
void Abc_RestructNodeDivisors(Abc_ManRst_t *p, Abc_Obj_t *pRoot, int nNodesSaved)
Definition: abcRestruct.c:212
Abc_ObjRequiredLevel
ABC_DLL int Abc_ObjRequiredLevel(Abc_Obj_t *pObj)
Definition: abcTiming.c:1102
Vec_PtrEntryLast
static void * Vec_PtrEntryLast(Vec_Ptr_t *p)
Definition: vecPtr.h:413
Abc_AigCleanup
ABC_DLL int Abc_AigCleanup(Abc_Aig_t *pMan)
Definition: abcAig.c:194
Dec_Graph_t_
Definition: dec.h:69
Extra_bddIsVar
int Extra_bddIsVar(DdNode *bFunc)
Definition: extraBddMisc.c:839
Abc_Obj_t_::fMarkC
unsigned fMarkC
Definition: abc.h:136
Cut_ParamsStruct_t_::fDrop
int fDrop
Definition: cut.h:63
Cut_ManStop
void Cut_ManStop(Cut_Man_t *p)
Definition: cutMan.c:124
Vec_IntEntry
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
Dec_GraphCreateConst0
static Dec_Graph_t * Dec_GraphCreateConst0()
Definition: dec.h:245
Cut_ManStart
Cut_Man_t * Cut_ManStart(Cut_Params_t *pParams)
FUNCTION DEFINITIONS ///.
Definition: cutMan.c:47
Abc_NtkStartCutManForRestruct
static Cut_Man_t * Abc_NtkStartCutManForRestruct(Abc_Ntk_t *pNtk, int nCutMax, int fDag)
Definition: abcRestruct.c:956
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Abc_NodeMffcSize
ABC_DLL int Abc_NodeMffcSize(Abc_Obj_t *pNode)
FUNCTION DEFINITIONS ///.
Definition: abcRefs.c:48
Abc_NodeMffcConstants
Dec_Graph_t * Abc_NodeMffcConstants(Abc_ManRst_t *p, Vec_Int_t *vSims)
Definition: abcRestruct.c:1249
Cudd_Init
DdManager * Cudd_Init(unsigned int numVars, unsigned int numVarsZ, unsigned int numSlots, unsigned int cacheSize, unsigned long maxMemory)
Definition: cuddInit.c:125
Abc_NodeResubMffc
int Abc_NodeResubMffc(Abc_ManRst_t *p, Vec_Ptr_t *vDecs, int nLeaves, Abc_Obj_t *pRoot)
Definition: abcRestruct.c:1160
Vec_IntPop
static int Vec_IntPop(Vec_Int_t *p)
Definition: extraZddTrunc.c:110
Cut_CutStruct_t_
Definition: cut.h:77
Abc_NodeGetCutsRecursive
ABC_DLL void * Abc_NodeGetCutsRecursive(void *p, Abc_Obj_t *pObj, int fDag, int fTree)
Definition: base/abci/abcCut.c:412
Abc_ManRst_t_::vTwos
Vec_Int_t * vTwos
Definition: abcRestruct.c:57
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Dsd_Manager_t_
STRUCTURE DEFINITIONS ///.
Definition: dsdInt.h:40
Dec_GraphAddNodeXor
static Dec_Edge_t Dec_GraphAddNodeXor(Dec_Graph_t *pGraph, Dec_Edge_t eEdge0, Dec_Edge_t eEdge1, int Type)
Definition: dec.h:643
Counter
static int Counter
Definition: extraBddMisc.c:1877
Abc_ManRst_t_::vVisited
Vec_Ptr_t * vVisited
Definition: abcRestruct.c:49
Abc_NodeEvaluateDsd
static Dec_Graph_t * Abc_NodeEvaluateDsd(Abc_ManRst_t *pManRst, Dsd_Node_t *pNodeDsd, Abc_Obj_t *pRoot, int Required, int nNodesSaved, int *pnNodesAdded)
Definition: abcRestruct.c:903
Abc_ManRst_t_::nNodesConsidered
int nNodesConsidered
Definition: abcRestruct.c:62
Dsd_Node_t_
Definition: dsdInt.h:54
Abc_NtkStartReverseLevels
ABC_DLL void Abc_NtkStartReverseLevels(Abc_Ntk_t *pNtk, int nMaxLevelIncrease)
Definition: abcTiming.c:1162
Dsd_ManagerStart
Dsd_Manager_t * Dsd_ManagerStart(DdManager *dd, int nSuppMax, int fVerbose)
FUNCTION DECLARATIONS ///.
Definition: dsdMan.c:47
Extra_ProgressBarStop
void Extra_ProgressBarStop(ProgressBar *p)
Definition: extraUtilProgress.c:118
Dsd_Regular
#define Dsd_Regular(p)
Definition: dsd.h:69
Abc_NodeEvaluateDsd_rec
Dec_Edge_t Abc_NodeEvaluateDsd_rec(Dec_Graph_t *pGraph, Abc_ManRst_t *pManRst, Dsd_Node_t *pNodeDsd, int Required, int nNodesSaved, int *pnNodesAdded)
Definition: abcRestruct.c:585
Abc_NodeMffcSimulate
void Abc_NodeMffcSimulate(Vec_Ptr_t *vDecs, int nLeaves, Vec_Int_t *vRands, Vec_Int_t *vSims)
Definition: abcRestruct.c:1199
Vec_PtrWriteEntry
static void Vec_PtrWriteEntry(Vec_Ptr_t *p, int i, void *Entry)
Definition: vecPtr.h:396
Abc_NtkForEachNode
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition: abc.h:461
Abc_NodeResubEval
Dec_Graph_t * Abc_NodeResubEval(Abc_ManRst_t *p, Abc_Obj_t *pRoot, Cut_Cut_t *pCut)
Definition: abcRestruct.c:1379
Abc_NodeIsPersistant
static int Abc_NodeIsPersistant(Abc_Obj_t *pNode)
Definition: abc.h:401
Dec_GraphSetRoot
static void Dec_GraphSetRoot(Dec_Graph_t *pGraph, Dec_Edge_t eRoot)
Definition: dec.h:551
Abc_ManRst_t_::fUseZeros
int fUseZeros
Definition: abcRestruct.c:44
Dsd_IsComplement
#define Dsd_IsComplement(p)
MACRO DEFINITIONS ///.
Definition: dsd.h:68
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Abc_Obj_t_::vFanouts
Vec_Int_t vFanouts
Definition: abc.h:144
Dsd_TreeGetPrimeFunction
DdNode * Dsd_TreeGetPrimeFunction(DdManager *dd, Dsd_Node_t *pNode)
FUNCTION DEFINITIONS ///.
Definition: dsdLocal.c:54
Vec_PtrEntry
static void * Vec_PtrEntry(Vec_Ptr_t *p, int i)
Definition: vecPtr.h:362
Abc_NodeMffcSingleNode
Dec_Graph_t * Abc_NodeMffcSingleNode(Abc_ManRst_t *p, Vec_Int_t *vSims, int nNodes, Vec_Int_t *vOnes)
Definition: abcRestruct.c:1322
Dec_GraphCreate
static Dec_Graph_t * Dec_GraphCreate(int nLeaves)
Definition: dec.h:221
Dec_Node_t_::pFunc
void * pFunc
Definition: dec.h:56
Cut_ParamsStruct_t_::fVerbose
int fVerbose
Definition: cut.h:74
Dsd_NodeForEachChild
#define Dsd_NodeForEachChild(Node, Index, Child)
ITERATORS ///.
Definition: dsd.h:78
Dec_GraphAddNodeOr
static Dec_Edge_t Dec_GraphAddNodeOr(Dec_Graph_t *pGraph, Dec_Edge_t eEdge0, Dec_Edge_t eEdge1)
Definition: dec.h:615
Vec_IntEntryLast
static int Vec_IntEntryLast(Vec_Int_t *p)
Definition: bblif.c:319
Abc_NodeIsTravIdCurrent
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
Dsd_NodeReadFunc
DdNode * Dsd_NodeReadFunc(Dsd_Node_t *p)
Definition: dsdApi.c:54
Abc_ObjRegular
static Abc_Obj_t * Abc_ObjRegular(Abc_Obj_t *p)
Definition: abc.h:323
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Abc_NtkRestructure
int Abc_NtkRestructure(Abc_Ntk_t *pNtk, int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose)
FUNCTION DEFINITIONS ///.
Definition: abcRestruct.c:101
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Vec_PtrForEachEntryStop
#define Vec_PtrForEachEntryStop(Type, vVec, pEntry, i, Stop)
Definition: vecPtr.h:59
Abc_ManRst_t_::timeNtk
int timeNtk
Definition: abcRestruct.c:71
Abc_ObjForEachFanout
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
Abc_NtkForEachCi
#define Abc_NtkForEachCi(pNtk, pCi, i)
Definition: abc.h:515
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
Abc_ManRst_t_::nCutsConsidered
int nCutsConsidered
Definition: abcRestruct.c:60
Dec_GraphForEachLeaf
#define Dec_GraphForEachLeaf(pGraph, pLeaf, i)
ITERATORS ///.
Definition: dec.h:98
Abc_NodeMffcDoubleNode
Dec_Graph_t * Abc_NodeMffcDoubleNode(Abc_ManRst_t *p, Vec_Int_t *vSims, int nNodes, Vec_Int_t *vOnes)
Definition: abcRestruct.c:1358
Abc_ManRst_t_::timeEval
int timeEval
Definition: abcRestruct.c:69
Cut_ManStruct_t_
Definition: cutInt.h:48
DdNode::index
DdHalfWord index
Definition: cudd.h:279
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Abc_Obj_t_::Id
int Id
Definition: abc.h:132
Abc_ObjName
ABC_DLL char * Abc_ObjName(Abc_Obj_t *pNode)
DECLARATIONS ///.
Definition: abcNames.c:48
DdManager::vars
DdNode ** vars
Definition: cuddInt.h:390
ABC_PRT
#define ABC_PRT(a, t)
Definition: abc_global.h:220
Abc_NtkIncrementTravId
static void Abc_NtkIncrementTravId(Abc_Ntk_t *p)
Definition: abc.h:406
Extra_ProgressBarStart
ProgressBar * Extra_ProgressBarStart(FILE *pFile, int nItemsTotal)
FUNCTION DEFINITIONS ///.
Definition: extraUtilProgress.c:62
Dec_GraphLeaveNum
static int Dec_GraphLeaveNum(Dec_Graph_t *pGraph)
Definition: dec.h:405
Abc_ManRst_t_::vDecs
Vec_Ptr_t * vDecs
Definition: abcRestruct.c:51
Abc_ManRst_t_::nNodesRestructured
int nNodesRestructured
Definition: abcRestruct.c:63
Abc_ObjIsPo
static int Abc_ObjIsPo(Abc_Obj_t *pObj)
Definition: abc.h:348
Dec_GraphFree
static void Dec_GraphFree(Dec_Graph_t *pGraph)
Definition: dec.h:307
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition: abc_global.h:216
Abc_NtkCleanCopy
ABC_DLL void Abc_NtkCleanCopy(Abc_Ntk_t *pNtk)
Definition: abcUtil.c:507
Abc_NodeResubstitute
static Dec_Graph_t * Abc_NodeResubstitute(Abc_ManRst_t *p, Abc_Obj_t *pNode, Cut_Cut_t *pCutList)
Definition: abcRestruct.c:1460
Cut_ParamsStruct_t_
Definition: cut.h:53
Abc_NtkFanoutCounts
ABC_DLL Vec_Int_t * Abc_NtkFanoutCounts(Abc_Ntk_t *pNtk)
Definition: abcUtil.c:1701
Cudd_zddVarsFromBddVars
int Cudd_zddVarsFromBddVars(DdManager *dd, int multiplicity)
Definition: cuddAPI.c:519
Abc_ObjNotCond
static Abc_Obj_t * Abc_ObjNotCond(Abc_Obj_t *p, int c)
Definition: abc.h:325
assert
#define assert(ex)
Definition: util_old.h:213
Extra_ProgressBarUpdate
static void Extra_ProgressBarUpdate(ProgressBar *p, int nItemsCur, char *pString)
Definition: extra.h:243
Vec_PtrClear
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
Dec_GraphNode
static Dec_Node_t * Dec_GraphNode(Dec_Graph_t *pGraph, int i)
Definition: dec.h:437
Dsd_Type_t
enum Dsd_Type_t_ Dsd_Type_t
Definition: dsd.h:61
Abc_ObjNot
static Abc_Obj_t * Abc_ObjNot(Abc_Obj_t *p)
Definition: abc.h:324
Abc_ManRst_t_::timeDsd
int timeDsd
Definition: abcRestruct.c:68
Cut_ParamsStruct_t_::fTree
int fTree
Definition: cut.h:65
Abc_Obj_t_::pData
void * pData
Definition: abc.h:145
Cudd_Ref
void Cudd_Ref(DdNode *n)
Definition: cuddRef.c:129
Abc_AigXorLookup
ABC_DLL Abc_Obj_t * Abc_AigXorLookup(Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1, int *pType)
Definition: abcAig.c:474
Vec_IntFree
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Dsd_NodeReadType
Dsd_Type_t Dsd_NodeReadType(Dsd_Node_t *p)
FUNCTION DEFINITIONS ///.
Definition: dsdApi.c:53
Abc_ManRst_t_::fUpdateLevel
int fUpdateLevel
Definition: abcRestruct.c:43
Dsd_DecomposeOne
Dsd_Node_t * Dsd_DecomposeOne(Dsd_Manager_t *pDsdMan, DdNode *bFunc)
Definition: dsdProc.c:230
Vec_IntClear
static void Vec_IntClear(Vec_Int_t *p)
Definition: bblif.c:452
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
Abc_NtkLevel
ABC_DLL int Abc_NtkLevel(Abc_Ntk_t *pNtk)
Definition: abcDfs.c:1265
Abc_ManRst_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abcRestruct.c:40
Dsd_TreeNodeGetInfoOne
void Dsd_TreeNodeGetInfoOne(Dsd_Node_t *pNode, int *DepthMax, int *GateSizeMax)
Definition: dsdTree.c:183
Abc_NtkManRstPrintStats
static void Abc_NtkManRstPrintStats(Abc_ManRst_t *p)
Definition: abcRestruct.c:1067
Abc_ManRst_t_::timeCut
int timeCut
Definition: abcRestruct.c:66
Abc_Abc_NodeResubCollectDivs
int Abc_Abc_NodeResubCollectDivs(Abc_ManRst_t *p, Abc_Obj_t *pRoot, Cut_Cut_t *pCut)
Definition: abcRestruct.c:1096
Abc_NodeSetTravIdCurrent
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
Cudd_DagSize
int Cudd_DagSize(DdNode *node)
Definition: cuddUtil.c:442
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
Abc_NtkManRstStop
static void Abc_NtkManRstStop(Abc_ManRst_t *p)
Definition: abcRestruct.c:1040
Dec_Node_t_::Level
unsigned Level
Definition: dec.h:57
Abc_ManRst_t_::pManDsd
Dsd_Manager_t * pManDsd
Definition: abcRestruct.c:48