1 /**CFile****************************************************************
2
3 FileName [abcDsd.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Network and node package.]
8
9 Synopsis [Technology dependent sweep.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: abcDsd.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "base/abc/abc.h"
22 #include "base/main/main.h"
23 #include "proof/fraig/fraig.h"
24
25 #ifdef ABC_USE_CUDD
26 #include "bdd/extrab/extraBdd.h"
27 #endif
28
29 ABC_NAMESPACE_IMPL_START
30
31 ////////////////////////////////////////////////////////////////////////
32 /// DECLARATIONS ///
33 ////////////////////////////////////////////////////////////////////////
34
35 static void Abc_NtkFraigSweepUsingExdc( Fraig_Man_t * pMan, Abc_Ntk_t * pNtk );
36 static stmm_table * Abc_NtkFraigEquiv( Abc_Ntk_t * pNtk, int fUseInv, int fVerbose, int fVeryVerbose );
37 static void Abc_NtkFraigTransform( Abc_Ntk_t * pNtk, stmm_table * tEquiv, int fUseInv, int fVerbose );
38 static void Abc_NtkFraigMergeClassMapped( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUseInv, int fVerbose );
39 static void Abc_NtkFraigMergeClass( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUseInv, int fVerbose );
40 static int Abc_NodeDroppingCost( Abc_Obj_t * pNode );
41
42 static int Abc_NtkReduceNodes( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes );
43 static void Abc_NodeSweep( Abc_Obj_t * pNode, int fVerbose );
44
45 ////////////////////////////////////////////////////////////////////////
46 /// FUNCTION DEFINITIONS ///
47 ////////////////////////////////////////////////////////////////////////
48
49 /**Function*************************************************************
50
51 Synopsis [Sweping functionally equivalence nodes.]
52
53 Description [Removes gates with equivalent functionality. Works for
54 both technology-independent and mapped networks. If the flag is set,
55 allows adding inverters at the gate outputs.]
56
57 SideEffects []
58
59 SeeAlso []
60
61 ***********************************************************************/
Abc_NtkFraigSweep(Abc_Ntk_t * pNtk,int fUseInv,int fExdc,int fVerbose,int fVeryVerbose)62 int Abc_NtkFraigSweep( Abc_Ntk_t * pNtk, int fUseInv, int fExdc, int fVerbose, int fVeryVerbose )
63 {
64 Fraig_Params_t Params;
65 Abc_Ntk_t * pNtkAig;
66 Fraig_Man_t * pMan;
67 stmm_table * tEquiv;
68 Abc_Obj_t * pObj;
69 int i, fUseTrick;
70
71 assert( !Abc_NtkIsStrash(pNtk) );
72
73 // save gate assignments
74 fUseTrick = 0;
75 if ( Abc_NtkIsMappedLogic(pNtk) )
76 {
77 fUseTrick = 1;
78 Abc_NtkForEachNode( pNtk, pObj, i )
79 pObj->pNext = (Abc_Obj_t *)pObj->pData;
80 }
81 // derive the AIG
82 pNtkAig = Abc_NtkStrash( pNtk, 0, 1, 0 );
83 // reconstruct gate assignments
84 if ( fUseTrick )
85 {
86 // extern void * Abc_FrameReadLibGen();
87 Hop_ManStop( (Hop_Man_t *)pNtk->pManFunc );
88 pNtk->pManFunc = Abc_FrameReadLibGen();
89 pNtk->ntkFunc = ABC_FUNC_MAP;
90 Abc_NtkForEachNode( pNtk, pObj, i )
91 pObj->pData = pObj->pNext, pObj->pNext = NULL;
92 }
93
94 // perform fraiging of the AIG
95 Fraig_ParamsSetDefault( &Params );
96 Params.fInternal = 1;
97 pMan = (Fraig_Man_t *)Abc_NtkToFraig( pNtkAig, &Params, 0, 0 );
98 // cannot use EXDC with FRAIG because it can create classes of equivalent FRAIG nodes
99 // with representative nodes that do not correspond to the nodes with the current network
100
101 // update FRAIG using EXDC
102 if ( fExdc )
103 {
104 if ( pNtk->pExdc == NULL )
105 printf( "Warning: Networks has no EXDC.\n" );
106 else
107 Abc_NtkFraigSweepUsingExdc( pMan, pNtk );
108 }
109 // assign levels to the nodes of the network
110 Abc_NtkLevel( pNtk );
111
112 // collect the classes of equivalent nets
113 tEquiv = Abc_NtkFraigEquiv( pNtk, fUseInv, fVerbose, fVeryVerbose );
114
115 // transform the network into the equivalent one
116 Abc_NtkFraigTransform( pNtk, tEquiv, fUseInv, fVerbose );
117 stmm_free_table( tEquiv );
118
119 // free the manager
120 Fraig_ManFree( pMan );
121 Abc_NtkDelete( pNtkAig );
122
123 // cleanup the dangling nodes
124 if ( Abc_NtkHasMapping(pNtk) )
125 Abc_NtkCleanup( pNtk, fVerbose );
126 else
127 Abc_NtkSweep( pNtk, fVerbose );
128
129 // check
130 if ( !Abc_NtkCheck( pNtk ) )
131 {
132 printf( "Abc_NtkFraigSweep: The network check has failed.\n" );
133 return 0;
134 }
135 return 1;
136 }
137
138 /**Function*************************************************************
139
140 Synopsis [Sweep the network using EXDC.]
141
142 Description []
143
144 SideEffects []
145
146 SeeAlso []
147
148 ***********************************************************************/
Abc_NtkFraigSweepUsingExdc(Fraig_Man_t * pMan,Abc_Ntk_t * pNtk)149 void Abc_NtkFraigSweepUsingExdc( Fraig_Man_t * pMan, Abc_Ntk_t * pNtk )
150 {
151 Fraig_Node_t * gNodeExdc, * gNode, * gNodeRes;
152 Abc_Obj_t * pNode, * pNodeAig;
153 int i;
154 extern Fraig_Node_t * Abc_NtkToFraigExdc( Fraig_Man_t * pMan, Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkExdc );
155
156 assert( pNtk->pExdc );
157 // derive FRAIG node representing don't-cares in the EXDC network
158 gNodeExdc = Abc_NtkToFraigExdc( pMan, pNtk, pNtk->pExdc );
159 // update the node pointers
160 Abc_NtkForEachNode( pNtk, pNode, i )
161 {
162 // skip the constant input nodes
163 if ( Abc_ObjFaninNum(pNode) == 0 )
164 continue;
165 // get the strashed node
166 pNodeAig = pNode->pCopy;
167 // skip the dangling nodes
168 if ( pNodeAig == NULL )
169 continue;
170 // get the FRAIG node
171 gNode = Fraig_NotCond( Abc_ObjRegular(pNodeAig)->pCopy, (int)Abc_ObjIsComplement(pNodeAig) );
172 // perform ANDing with EXDC
173 gNodeRes = Fraig_NodeAnd( pMan, gNode, Fraig_Not(gNodeExdc) );
174 // write the node back
175 Abc_ObjRegular(pNodeAig)->pCopy = (Abc_Obj_t *)Fraig_NotCond( gNodeRes, (int)Abc_ObjIsComplement(pNodeAig) );
176 }
177 }
178
179 /**Function*************************************************************
180
181 Synopsis [Collects equivalence classes of node in the network.]
182
183 Description []
184
185 SideEffects []
186
187 SeeAlso []
188
189 ***********************************************************************/
Abc_NtkFraigEquiv(Abc_Ntk_t * pNtk,int fUseInv,int fVerbose,int fVeryVerbose)190 stmm_table * Abc_NtkFraigEquiv( Abc_Ntk_t * pNtk, int fUseInv, int fVerbose, int fVeryVerbose )
191 {
192 Abc_Obj_t * pList, * pNode, * pNodeAig;
193 Fraig_Node_t * gNode;
194 Abc_Obj_t ** ppSlot;
195 stmm_table * tStrash2Net;
196 stmm_table * tResult;
197 stmm_generator * gen;
198 int c, Counter;
199
200 // create mapping of strashed nodes into the corresponding network nodes
201 tStrash2Net = stmm_init_table(stmm_ptrcmp,stmm_ptrhash);
202 Abc_NtkForEachNode( pNtk, pNode, c )
203 {
204 // skip the constant input nodes
205 if ( Abc_ObjFaninNum(pNode) == 0 )
206 continue;
207 // get the strashed node
208 pNodeAig = pNode->pCopy;
209 // skip the dangling nodes
210 if ( pNodeAig == NULL )
211 continue;
212 // skip the nodes that fanout into COs
213 if ( Abc_NodeFindCoFanout(pNode) )
214 continue;
215 // get the FRAIG node
216 gNode = Fraig_NotCond( Abc_ObjRegular(pNodeAig)->pCopy, (int)Abc_ObjIsComplement(pNodeAig) );
217 if ( !stmm_find_or_add( tStrash2Net, (char *)Fraig_Regular(gNode), (char ***)&ppSlot ) )
218 *ppSlot = NULL;
219 // add the node to the list
220 pNode->pNext = *ppSlot;
221 *ppSlot = pNode;
222 // mark the node if it is complemented
223 pNode->fPhase = Fraig_IsComplement(gNode);
224 }
225
226 // print the classes
227 c = 0;
228 Counter = 0;
229 tResult = stmm_init_table(stmm_ptrcmp,stmm_ptrhash);
230 stmm_foreach_item( tStrash2Net, gen, (char **)&gNode, (char **)&pList )
231 {
232 // skip the trival classes
233 if ( pList == NULL || pList->pNext == NULL )
234 continue;
235 // add the non-trival class
236 stmm_insert( tResult, (char *)pList, NULL );
237 // count nodes in the non-trival classes
238 for ( pNode = pList; pNode; pNode = pNode->pNext )
239 Counter++;
240
241 if ( fVeryVerbose )
242 {
243 printf( "Class %2d : {", c );
244 for ( pNode = pList; pNode; pNode = pNode->pNext )
245 {
246 pNode->pCopy = NULL;
247 printf( " %s", Abc_ObjName(pNode) );
248 printf( "(%c)", pNode->fPhase? '-' : '+' );
249 printf( "(%d)", pNode->Level );
250 }
251 printf( " }\n" );
252 c++;
253 }
254 }
255 if ( fVerbose || fVeryVerbose )
256 {
257 printf( "Sweeping stats for network \"%s\":\n", pNtk->pName );
258 printf( "Internal nodes = %d. Different functions (up to compl) = %d.\n", Abc_NtkNodeNum(pNtk), stmm_count(tStrash2Net) );
259 printf( "Non-trivial classes = %d. Nodes in non-trivial classes = %d.\n", stmm_count(tResult), Counter );
260 }
261 stmm_free_table( tStrash2Net );
262 return tResult;
263 }
264
265
266 /**Function*************************************************************
267
268 Synopsis [Transforms the network using the equivalence relation on nodes.]
269
270 Description []
271
272 SideEffects []
273
274 SeeAlso []
275
276 ***********************************************************************/
Abc_NtkFraigTransform(Abc_Ntk_t * pNtk,stmm_table * tEquiv,int fUseInv,int fVerbose)277 void Abc_NtkFraigTransform( Abc_Ntk_t * pNtk, stmm_table * tEquiv, int fUseInv, int fVerbose )
278 {
279 stmm_generator * gen;
280 Abc_Obj_t * pList;
281 if ( stmm_count(tEquiv) == 0 )
282 return;
283 // merge nodes in the classes
284 if ( Abc_NtkHasMapping( pNtk ) )
285 {
286 Abc_NtkDelayTrace( pNtk, NULL, NULL, 0 );
287 stmm_foreach_item( tEquiv, gen, (char **)&pList, NULL )
288 Abc_NtkFraigMergeClassMapped( pNtk, pList, fUseInv, fVerbose );
289 }
290 else
291 {
292 stmm_foreach_item( tEquiv, gen, (char **)&pList, NULL )
293 Abc_NtkFraigMergeClass( pNtk, pList, fUseInv, fVerbose );
294 }
295 }
296
297
298 /**Function*************************************************************
299
300 Synopsis [Transforms the list of one-phase equivalent nodes.]
301
302 Description []
303
304 SideEffects []
305
306 SeeAlso []
307
308 ***********************************************************************/
Abc_NtkFraigMergeClassMapped(Abc_Ntk_t * pNtk,Abc_Obj_t * pChain,int fUseInv,int fVerbose)309 void Abc_NtkFraigMergeClassMapped( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUseInv, int fVerbose )
310 {
311 Abc_Obj_t * pListDir, * pListInv;
312 Abc_Obj_t * pNodeMin, * pNode, * pNext;
313 float Arrival1, Arrival2;
314
315 assert( pChain );
316 assert( pChain->pNext );
317
318 // divide the nodes into two parts:
319 // those that need the invertor and those that don't need
320 pListDir = pListInv = NULL;
321 for ( pNode = pChain, pNext = pChain->pNext;
322 pNode;
323 pNode = pNext, pNext = pNode? pNode->pNext : NULL )
324 {
325 // check to which class the node belongs
326 if ( pNode->fPhase == 1 )
327 {
328 pNode->pNext = pListDir;
329 pListDir = pNode;
330 }
331 else
332 {
333 pNode->pNext = pListInv;
334 pListInv = pNode;
335 }
336 }
337
338 // find the node with the smallest number of logic levels
339 pNodeMin = pListDir;
340 for ( pNode = pListDir; pNode; pNode = pNode->pNext )
341 {
342 Arrival1 = Abc_NodeReadArrivalWorst(pNodeMin);
343 Arrival2 = Abc_NodeReadArrivalWorst(pNode );
344 // assert( Abc_ObjIsCi(pNodeMin) || Arrival1 > 0 );
345 // assert( Abc_ObjIsCi(pNode) || Arrival2 > 0 );
346 if ( Arrival1 > Arrival2 ||
347 (Arrival1 == Arrival2 && pNodeMin->Level > pNode->Level) ||
348 (Arrival1 == Arrival2 && pNodeMin->Level == pNode->Level &&
349 Abc_NodeDroppingCost(pNodeMin) < Abc_NodeDroppingCost(pNode)) )
350 pNodeMin = pNode;
351 }
352
353 // move the fanouts of the direct nodes
354 for ( pNode = pListDir; pNode; pNode = pNode->pNext )
355 if ( pNode != pNodeMin )
356 Abc_ObjTransferFanout( pNode, pNodeMin );
357
358 // find the node with the smallest number of logic levels
359 pNodeMin = pListInv;
360 for ( pNode = pListInv; pNode; pNode = pNode->pNext )
361 {
362 Arrival1 = Abc_NodeReadArrivalWorst(pNodeMin);
363 Arrival2 = Abc_NodeReadArrivalWorst(pNode );
364 // assert( Abc_ObjIsCi(pNodeMin) || Arrival1 > 0 );
365 // assert( Abc_ObjIsCi(pNode) || Arrival2 > 0 );
366 if ( Arrival1 > Arrival2 ||
367 (Arrival1 == Arrival2 && pNodeMin->Level > pNode->Level) ||
368 (Arrival1 == Arrival2 && pNodeMin->Level == pNode->Level &&
369 Abc_NodeDroppingCost(pNodeMin) < Abc_NodeDroppingCost(pNode)) )
370 pNodeMin = pNode;
371 }
372
373 // move the fanouts of the direct nodes
374 for ( pNode = pListInv; pNode; pNode = pNode->pNext )
375 if ( pNode != pNodeMin )
376 Abc_ObjTransferFanout( pNode, pNodeMin );
377 }
378
379 /**Function*************************************************************
380
381 Synopsis [Process one equivalence class of nodes.]
382
383 Description [This function does not remove the nodes. It only switches
384 around the connections.]
385
386 SideEffects []
387
388 SeeAlso []
389
390 ***********************************************************************/
Abc_NtkFraigMergeClass(Abc_Ntk_t * pNtk,Abc_Obj_t * pChain,int fUseInv,int fVerbose)391 void Abc_NtkFraigMergeClass( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUseInv, int fVerbose )
392 {
393 Abc_Obj_t * pListDir, * pListInv;
394 Abc_Obj_t * pNodeMin, * pNodeMinInv;
395 Abc_Obj_t * pNode, * pNext;
396
397 assert( pChain );
398 assert( pChain->pNext );
399
400 // find the node with the smallest number of logic levels
401 pNodeMin = pChain;
402 for ( pNode = pChain->pNext; pNode; pNode = pNode->pNext )
403 if ( pNodeMin->Level > pNode->Level ||
404 ( pNodeMin->Level == pNode->Level &&
405 Abc_NodeDroppingCost(pNodeMin) < Abc_NodeDroppingCost(pNode) ) )
406 pNodeMin = pNode;
407
408 // divide the nodes into two parts:
409 // those that need the invertor and those that don't need
410 pListDir = pListInv = NULL;
411 for ( pNode = pChain, pNext = pChain->pNext;
412 pNode;
413 pNode = pNext, pNext = pNode? pNode->pNext : NULL )
414 {
415 if ( pNode == pNodeMin )
416 continue;
417 // check to which class the node belongs
418 if ( pNodeMin->fPhase == pNode->fPhase )
419 {
420 pNode->pNext = pListDir;
421 pListDir = pNode;
422 }
423 else
424 {
425 pNode->pNext = pListInv;
426 pListInv = pNode;
427 }
428 }
429
430 // move the fanouts of the direct nodes
431 for ( pNode = pListDir; pNode; pNode = pNode->pNext )
432 Abc_ObjTransferFanout( pNode, pNodeMin );
433
434 // skip if there are no inverted nodes
435 if ( pListInv == NULL )
436 return;
437
438 // add the invertor
439 pNodeMinInv = Abc_NtkCreateNodeInv( pNtk, pNodeMin );
440
441 // move the fanouts of the inverted nodes
442 for ( pNode = pListInv; pNode; pNode = pNode->pNext )
443 Abc_ObjTransferFanout( pNode, pNodeMinInv );
444 }
445
446
447 /**Function*************************************************************
448
449 Synopsis [Returns the number of literals saved if this node becomes useless.]
450
451 Description []
452
453 SideEffects []
454
455 SeeAlso []
456
457 ***********************************************************************/
Abc_NodeDroppingCost(Abc_Obj_t * pNode)458 int Abc_NodeDroppingCost( Abc_Obj_t * pNode )
459 {
460 return 1;
461 }
462
463
464
465
466
467 /**Function*************************************************************
468
469 Synopsis [Removes dangling nodes.]
470
471 Description [Returns the number of nodes removed.]
472
473 SideEffects []
474
475 SeeAlso []
476
477 ***********************************************************************/
Abc_NtkCleanup(Abc_Ntk_t * pNtk,int fVerbose)478 int Abc_NtkCleanup( Abc_Ntk_t * pNtk, int fVerbose )
479 {
480 Vec_Ptr_t * vNodes;
481 int Counter;
482 assert( Abc_NtkIsLogic(pNtk) );
483 // mark the nodes reachable from the POs
484 vNodes = Abc_NtkDfs( pNtk, 0 );
485 Counter = Abc_NtkReduceNodes( pNtk, vNodes );
486 if ( fVerbose )
487 printf( "Cleanup removed %d dangling nodes.\n", Counter );
488 Vec_PtrFree( vNodes );
489 return Counter;
490 }
491
492 /**Function*************************************************************
493
494 Synopsis [Removes dangling nodes.]
495
496 Description [Returns the number of nodes removed.]
497
498 SideEffects []
499
500 SeeAlso []
501
502 ***********************************************************************/
Abc_NtkCleanupNodes(Abc_Ntk_t * pNtk,Vec_Ptr_t * vRoots,int fVerbose)503 int Abc_NtkCleanupNodes( Abc_Ntk_t * pNtk, Vec_Ptr_t * vRoots, int fVerbose )
504 {
505 Vec_Ptr_t * vNodes, * vStarts;
506 Abc_Obj_t * pObj;
507 int i, Counter;
508 assert( Abc_NtkIsLogic(pNtk) );
509 // collect starting nodes into one array
510 vStarts = Vec_PtrAlloc( 1000 );
511 Abc_NtkForEachCo( pNtk, pObj, i )
512 Vec_PtrPush( vStarts, pObj );
513 Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
514 if ( pObj )
515 Vec_PtrPush( vStarts, pObj );
516 // mark the nodes reachable from the POs
517 vNodes = Abc_NtkDfsNodes( pNtk, (Abc_Obj_t **)Vec_PtrArray(vStarts), Vec_PtrSize(vStarts) );
518 Vec_PtrFree( vStarts );
519 Counter = Abc_NtkReduceNodes( pNtk, vNodes );
520 if ( fVerbose )
521 printf( "Cleanup removed %d dangling nodes.\n", Counter );
522 Vec_PtrFree( vNodes );
523 return Counter;
524 }
525
526 /**Function*************************************************************
527
528 Synopsis [Preserves the nodes collected in the array.]
529
530 Description [Returns the number of nodes removed.]
531
532 SideEffects []
533
534 SeeAlso []
535
536 ***********************************************************************/
Abc_NtkReduceNodes(Abc_Ntk_t * pNtk,Vec_Ptr_t * vNodes)537 int Abc_NtkReduceNodes( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes )
538 {
539 Abc_Obj_t * pNode;
540 int i, Counter;
541 assert( Abc_NtkIsLogic(pNtk) );
542 // mark the nodes reachable from the POs
543 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
544 pNode->fMarkA = 1;
545 // remove the non-marked nodes
546 Counter = 0;
547 Abc_NtkForEachNode( pNtk, pNode, i )
548 if ( pNode->fMarkA == 0 )
549 {
550 Abc_NtkDeleteObj( pNode );
551 Counter++;
552 }
553 // unmark the remaining nodes
554 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
555 pNode->fMarkA = 0;
556 // check
557 if ( !Abc_NtkCheck( pNtk ) )
558 printf( "Abc_NtkCleanup: The network check has failed.\n" );
559 return Counter;
560 }
561
562
563
564
565 #ifdef ABC_USE_CUDD
566
567 /**Function*************************************************************
568
569 Synopsis [Replaces the local function by its cofactor.]
570
571 Description []
572
573 SideEffects []
574
575 SeeAlso []
576
577 ***********************************************************************/
Abc_NodeConstantInput(Abc_Obj_t * pNode,Abc_Obj_t * pFanin,int fConst0)578 void Abc_NodeConstantInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin, int fConst0 )
579 {
580 DdManager * dd = (DdManager *)pNode->pNtk->pManFunc;
581 DdNode * bVar, * bTemp;
582 int iFanin;
583 assert( Abc_NtkIsBddLogic(pNode->pNtk) );
584 if ( (iFanin = Vec_IntFind( &pNode->vFanins, pFanin->Id )) == -1 )
585 {
586 printf( "Node %s should be among", Abc_ObjName(pFanin) );
587 printf( " the fanins of node %s...\n", Abc_ObjName(pNode) );
588 return;
589 }
590 bVar = Cudd_NotCond( Cudd_bddIthVar(dd, iFanin), fConst0 );
591 pNode->pData = Cudd_Cofactor( dd, bTemp = (DdNode *)pNode->pData, bVar ); Cudd_Ref( (DdNode *)pNode->pData );
592 Cudd_RecursiveDeref( dd, bTemp );
593 }
594
595 /**Function*************************************************************
596
597 Synopsis [Tranditional sweep of the network.]
598
599 Description [Propagates constant and single-input node, removes dangling nodes.]
600
601 SideEffects []
602
603 SeeAlso []
604
605 ***********************************************************************/
Abc_NtkSweep(Abc_Ntk_t * pNtk,int fVerbose)606 int Abc_NtkSweep( Abc_Ntk_t * pNtk, int fVerbose )
607 {
608 Vec_Ptr_t * vNodes;
609 Abc_Obj_t * pNode, * pFanout, * pDriver;
610 int i, nNodesOld;
611 assert( Abc_NtkIsLogic(pNtk) );
612 // convert network to BDD representation
613 if ( !Abc_NtkToBdd(pNtk) )
614 {
615 fprintf( stdout, "Converting to BDD has failed.\n" );
616 return 1;
617 }
618 // perform cleanup
619 nNodesOld = Abc_NtkNodeNum(pNtk);
620 Abc_NtkCleanup( pNtk, 0 );
621 // prepare nodes for sweeping
622 Abc_NtkRemoveDupFanins(pNtk);
623 Abc_NtkMinimumBase(pNtk);
624 // collect sweepable nodes
625 vNodes = Vec_PtrAlloc( 100 );
626 Abc_NtkForEachNode( pNtk, pNode, i )
627 if ( Abc_ObjFaninNum(pNode) < 2 )
628 Vec_PtrPush( vNodes, pNode );
629 // sweep the nodes
630 while ( Vec_PtrSize(vNodes) > 0 )
631 {
632 // get any sweepable node
633 pNode = (Abc_Obj_t *)Vec_PtrPop(vNodes);
634 if ( !Abc_ObjIsNode(pNode) )
635 continue;
636 // get any non-CO fanout of this node
637 pFanout = Abc_NodeFindNonCoFanout(pNode);
638 if ( pFanout == NULL )
639 continue;
640 assert( Abc_ObjIsNode(pFanout) );
641 // transform the function of the fanout
642 if ( Abc_ObjFaninNum(pNode) == 0 )
643 Abc_NodeConstantInput( pFanout, pNode, Abc_NodeIsConst0(pNode) );
644 else
645 {
646 assert( Abc_ObjFaninNum(pNode) == 1 );
647 pDriver = Abc_ObjFanin0(pNode);
648 if ( Abc_NodeIsInv(pNode) )
649 Abc_NodeComplementInput( pFanout, pNode );
650 Abc_ObjPatchFanin( pFanout, pNode, pDriver );
651 }
652 Abc_NodeRemoveDupFanins( pFanout );
653 Abc_NodeMinimumBase( pFanout );
654 // check if the fanout should be added
655 if ( Abc_ObjFaninNum(pFanout) < 2 )
656 Vec_PtrPush( vNodes, pFanout );
657 // check if the node has other fanouts
658 if ( Abc_ObjFanoutNum(pNode) > 0 )
659 Vec_PtrPush( vNodes, pNode );
660 else
661 Abc_NtkDeleteObj_rec( pNode, 1 );
662 }
663 Vec_PtrFree( vNodes );
664 // sweep a node into its CO fanout if all of this is true:
665 // (a) this node is a single-input node
666 // (b) the driver of the node has only one fanout (this node)
667 // (c) the driver is a node
668 Abc_NtkForEachCo( pNtk, pFanout, i )
669 {
670 pNode = Abc_ObjFanin0(pFanout);
671 if ( Abc_ObjFaninNum(pNode) != 1 )
672 continue;
673 pDriver = Abc_ObjFanin0(pNode);
674 if ( !(Abc_ObjFanoutNum(pDriver) == 1 && Abc_ObjIsNode(pDriver)) )
675 continue;
676 // trasform this CO
677 if ( Abc_NodeIsInv(pNode) )
678 pDriver->pData = Cudd_Not(pDriver->pData);
679 Abc_ObjPatchFanin( pFanout, pNode, pDriver );
680 }
681 // perform cleanup
682 Abc_NtkCleanup( pNtk, 0 );
683 // report
684 if ( fVerbose )
685 printf( "Sweep removed %d nodes.\n", nNodesOld - Abc_NtkNodeNum(pNtk) );
686 return nNodesOld - Abc_NtkNodeNum(pNtk);
687 }
688
689
690 #else
691
Abc_NtkSweep(Abc_Ntk_t * pNtk,int fVerbose)692 int Abc_NtkSweep( Abc_Ntk_t * pNtk, int fVerbose ) { return 1; }
693
694 #endif
695
696
697 /**Function*************************************************************
698
699 Synopsis [Removes all objects whose trav ID is not current.]
700
701 Description []
702
703 SideEffects []
704
705 SeeAlso []
706
707 ***********************************************************************/
Abc_NodeRemoveNonCurrentObjects(Abc_Ntk_t * pNtk)708 int Abc_NodeRemoveNonCurrentObjects( Abc_Ntk_t * pNtk )
709 {
710 Abc_Obj_t * pObj;
711 int Counter, i;
712 int fVerbose = 0;
713
714 // report on the nodes to be deleted
715 if ( fVerbose )
716 {
717 printf( "These nodes will be deleted: \n" );
718 Abc_NtkForEachObj( pNtk, pObj, i )
719 if ( !Abc_NodeIsTravIdCurrent( pObj ) )
720 {
721 printf( " " );
722 Abc_ObjPrint( stdout, pObj );
723 }
724 }
725
726 // delete the nodes
727 Counter = 0;
728 Abc_NtkForEachObj( pNtk, pObj, i )
729 if ( !Abc_NodeIsTravIdCurrent( pObj ) )
730 {
731 Abc_NtkDeleteObj( pObj );
732 Counter++;
733 }
734 return Counter;
735 }
736
737 /**Function*************************************************************
738
739 Synopsis [Check if the fanin of this latch is a constant.]
740
741 Description [Returns 0/1 if constant; -1 if not a constant.]
742
743 SideEffects []
744
745 SeeAlso []
746
747 ***********************************************************************/
Abc_NtkSetTravId_rec(Abc_Obj_t * pObj)748 void Abc_NtkSetTravId_rec( Abc_Obj_t * pObj )
749 {
750 Abc_NodeSetTravIdCurrent(pObj);
751 if ( Abc_ObjFaninNum(pObj) == 0 )
752 return;
753 assert( Abc_ObjFaninNum(pObj) == 1 );
754 Abc_NtkSetTravId_rec( Abc_ObjFanin0(pObj) );
755 }
756
757 /**Function*************************************************************
758
759 Synopsis [Check if the fanin of this latch is a constant.]
760
761 Description [Returns 0/1 if constant; -1 if not a constant.]
762
763 SideEffects []
764
765 SeeAlso []
766
767 ***********************************************************************/
Abc_NtkCheckConstant_rec(Abc_Obj_t * pObj)768 int Abc_NtkCheckConstant_rec( Abc_Obj_t * pObj )
769 {
770 if ( Abc_ObjFaninNum(pObj) == 0 )
771 {
772 if ( !Abc_ObjIsNode(pObj) )
773 return -1;
774 if ( Abc_NodeIsConst0(pObj) )
775 return 0;
776 if ( Abc_NodeIsConst1(pObj) )
777 return 1;
778 assert( 0 );
779 return -1;
780 }
781 if ( Abc_ObjIsLatch(pObj) || Abc_ObjFaninNum(pObj) > 1 )
782 return -1;
783 if ( !Abc_ObjIsNode(pObj) || Abc_NodeIsBuf(pObj) )
784 return Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pObj) );
785 if ( Abc_NodeIsInv(pObj) )
786 {
787 int RetValue = Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pObj) );
788 if ( RetValue == 0 )
789 return 1;
790 if ( RetValue == 1 )
791 return 0;
792 return RetValue;
793 }
794 assert( 0 );
795 return -1;
796 }
797
798 /**Function*************************************************************
799
800 Synopsis [Removes redundant latches.]
801
802 Description [The redundant latches are of two types:
803 - Latches fed by a constant which matches the init value of the latch.
804 - Latches fed by a constant which does not match the init value of the latch
805 can be all replaced by one latch.]
806
807 SideEffects []
808
809 SeeAlso []
810
811 ***********************************************************************/
Abc_NtkLatchSweep(Abc_Ntk_t * pNtk)812 int Abc_NtkLatchSweep( Abc_Ntk_t * pNtk )
813 {
814 Abc_Obj_t * pFanin, * pLatch, * pLatchPivot = NULL;
815 int Counter, RetValue, i;
816 Counter = 0;
817 // go through the latches
818 Abc_NtkForEachLatch( pNtk, pLatch, i )
819 {
820 // check if the latch has constant input
821 RetValue = Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pLatch) );
822 if ( RetValue == -1 )
823 continue;
824 // found a latch with constant fanin
825 if ( (RetValue == 1 && Abc_LatchIsInit0(pLatch)) ||
826 (RetValue == 0 && Abc_LatchIsInit1(pLatch)) )
827 {
828 // fanin constant differs from the latch init value
829 if ( pLatchPivot == NULL )
830 {
831 pLatchPivot = pLatch;
832 continue;
833 }
834 if ( Abc_LatchInit(pLatch) != Abc_LatchInit(pLatchPivot) ) // add inverter
835 pFanin = Abc_NtkCreateNodeInv( pNtk, Abc_ObjFanout0(pLatchPivot) );
836 else
837 pFanin = Abc_ObjFanout0(pLatchPivot);
838 }
839 else
840 pFanin = Abc_ObjFanin0(Abc_ObjFanin0(pLatch));
841 // replace latch
842 Abc_ObjTransferFanout( Abc_ObjFanout0(pLatch), pFanin );
843 // delete the extra nodes
844 Abc_NtkDeleteObj_rec( Abc_ObjFanout0(pLatch), 0 );
845 Counter++;
846 }
847 return Counter;
848 }
849
850 /**Function*************************************************************
851
852 Synopsis [Replaces autonumnous logic by free inputs.]
853
854 Description [Assumes that non-autonomous logic is marked with
855 the current ID.]
856
857 SideEffects []
858
859 SeeAlso []
860
861 ***********************************************************************/
Abc_NtkReplaceAutonomousLogic(Abc_Ntk_t * pNtk)862 int Abc_NtkReplaceAutonomousLogic( Abc_Ntk_t * pNtk )
863 {
864 Abc_Obj_t * pNode, * pFanin;
865 Vec_Ptr_t * vNodes;
866 int i, k, Counter;
867 // collect the nodes that feed into the reachable logic
868 vNodes = Vec_PtrAlloc( 100 );
869 Abc_NtkForEachObj( pNtk, pNode, i )
870 {
871 // skip non-visited fanins
872 if ( !Abc_NodeIsTravIdCurrent(pNode) )
873 continue;
874 // look for non-visited fanins
875 Abc_ObjForEachFanin( pNode, pFanin, k )
876 {
877 // skip visited fanins
878 if ( Abc_NodeIsTravIdCurrent(pFanin) )
879 continue;
880 // skip constants and latches fed by constants
881 if ( Abc_NtkCheckConstant_rec(pFanin) != -1 ||
882 (Abc_ObjIsBo(pFanin) && Abc_NtkCheckConstant_rec(Abc_ObjFanin0(Abc_ObjFanin0(pFanin))) != -1) )
883 {
884 Abc_NtkSetTravId_rec( pFanin );
885 continue;
886 }
887 assert( !Abc_ObjIsLatch(pFanin) );
888 Vec_PtrPush( vNodes, pFanin );
889 }
890 }
891 Vec_PtrUniqify( vNodes, (int (*)(void))Abc_ObjPointerCompare );
892 // replace these nodes by the PIs
893 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
894 {
895 pFanin = Abc_NtkCreatePi(pNtk);
896 Abc_ObjAssignName( pFanin, Abc_ObjName(pFanin), NULL );
897 Abc_NodeSetTravIdCurrent( pFanin );
898 Abc_ObjTransferFanout( pNode, pFanin );
899 }
900 Counter = Vec_PtrSize(vNodes);
901 Vec_PtrFree( vNodes );
902 return Counter;
903 }
904
905 /**Function*************************************************************
906
907 Synopsis [Sequential cleanup.]
908
909 Description [Performs three tasks:
910 - Removes logic that does not feed into POs.
911 - Removes latches driven by constant values equal to the initial state.
912 - Replaces the autonomous components by additional PI variables.]
913
914 SideEffects []
915
916 SeeAlso []
917
918 ***********************************************************************/
Abc_NtkCleanupSeq(Abc_Ntk_t * pNtk,int fLatchSweep,int fAutoSweep,int fVerbose)919 int Abc_NtkCleanupSeq( Abc_Ntk_t * pNtk, int fLatchSweep, int fAutoSweep, int fVerbose )
920 {
921 Vec_Ptr_t * vNodes;
922 int Counter;
923 assert( Abc_NtkIsLogic(pNtk) );
924 // mark the nodes reachable from the POs
925 vNodes = Abc_NtkDfsSeq( pNtk );
926 Vec_PtrFree( vNodes );
927 // remove the non-marked nodes
928 Counter = Abc_NodeRemoveNonCurrentObjects( pNtk );
929 if ( fVerbose )
930 printf( "Cleanup removed %4d dangling objects.\n", Counter );
931 // check if some of the latches can be removed
932 if ( fLatchSweep )
933 {
934 Counter = Abc_NtkLatchSweep( pNtk );
935 if ( fVerbose )
936 printf( "Cleanup removed %4d redundant latches.\n", Counter );
937 }
938 // detect the autonomous components
939 if ( fAutoSweep )
940 {
941 vNodes = Abc_NtkDfsSeqReverse( pNtk );
942 Vec_PtrFree( vNodes );
943 // replace them by PIs
944 Counter = Abc_NtkReplaceAutonomousLogic( pNtk );
945 if ( fVerbose )
946 printf( "Cleanup added %4d additional PIs.\n", Counter );
947 // remove the non-marked nodes
948 Counter = Abc_NodeRemoveNonCurrentObjects( pNtk );
949 if ( fVerbose )
950 printf( "Cleanup removed %4d autonomous objects.\n", Counter );
951 }
952 // check
953 if ( !Abc_NtkCheck( pNtk ) )
954 printf( "Abc_NtkCleanupSeq: The network check has failed.\n" );
955 return 1;
956 }
957
958 /**Function*************************************************************
959
960 Synopsis [Sweep to remove buffers and inverters.]
961
962 Description []
963
964 SideEffects []
965
966 SeeAlso []
967
968 ***********************************************************************/
Abc_NtkSweepBufsInvs(Abc_Ntk_t * pNtk,int fVerbose)969 int Abc_NtkSweepBufsInvs( Abc_Ntk_t * pNtk, int fVerbose )
970 {
971 Hop_Man_t * pMan;
972 Abc_Obj_t * pObj, * pFanin;
973 int i, k, fChanges = 1, Counter = 0;
974 assert( Abc_NtkIsLogic(pNtk) );
975 // convert network to BDD representation
976 if ( !Abc_NtkToAig(pNtk) )
977 {
978 fprintf( stdout, "Converting to SOP has failed.\n" );
979 return 1;
980 }
981 // get AIG manager
982 pMan = (Hop_Man_t *)pNtk->pManFunc;
983 // label selected nodes
984 Abc_NtkIncrementTravId( pNtk );
985 // iterate till no improvement
986 while ( fChanges )
987 {
988 fChanges = 0;
989 Abc_NtkForEachObj( pNtk, pObj, i )
990 {
991 Abc_ObjForEachFanin( pObj, pFanin, k )
992 {
993 // do not eliminate marked fanins
994 if ( Abc_NodeIsTravIdCurrent(pFanin) )
995 continue;
996 // do not eliminate constant nodes
997 if ( !Abc_ObjIsNode(pFanin) || Abc_ObjFaninNum(pFanin) != 1 )
998 continue;
999 // do not eliminate inverters into COs
1000 if ( Abc_ObjIsCo(pObj) && Abc_NodeIsInv(pFanin) )
1001 continue;
1002 // do not eliminate buffers connecting PIs and POs
1003 // if ( Abc_ObjIsCo(pObj) && Abc_ObjIsCi(Abc_ObjFanin0(pFanin)) )
1004 // continue;
1005 fChanges = 1;
1006 Counter++;
1007 // update function of the node
1008 if ( Abc_NodeIsInv(pFanin) )
1009 pObj->pData = Hop_Compose( pMan, (Hop_Obj_t *)pObj->pData, Hop_Not(Hop_IthVar(pMan, k)), k );
1010 // update the fanin
1011 Abc_ObjPatchFanin( pObj, pFanin, Abc_ObjFanin0(pFanin) );
1012 if ( Abc_ObjFanoutNum(pFanin) == 0 )
1013 Abc_NtkDeleteObj(pFanin);
1014 }
1015 }
1016 }
1017 if ( fVerbose )
1018 printf( "Removed %d single input nodes.\n", Counter );
1019 return Counter;
1020 }
1021
1022
1023
1024 ////////////////////////////////////////////////////////////////////////
1025 /// END OF FILE ///
1026 ////////////////////////////////////////////////////////////////////////
1027
1028
1029 ABC_NAMESPACE_IMPL_END
1030
1031