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