1 /**CFile****************************************************************
2
3 FileName [rwrDec.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [DAG-aware AIG rewriting package.]
8
9 Synopsis [Evaluation and decomposition procedures.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: rwrDec.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "rwr.h"
22 #include "bool/dec/dec.h"
23 #include "aig/ivy/ivy.h"
24
25 ABC_NAMESPACE_IMPL_START
26
27
28 ////////////////////////////////////////////////////////////////////////
29 /// DECLARATIONS ///
30 ////////////////////////////////////////////////////////////////////////
31
32 static Dec_Graph_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut, Vec_Ptr_t * vFaninsCur, int nNodesSaved, int LevelMax, int * pGainBest, int fPlaceEnable );
33 static int Rwr_CutIsBoolean( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves );
34 static int Rwr_CutCountNumNodes( Abc_Obj_t * pObj, Cut_Cut_t * pCut );
35 static int Rwr_NodeGetDepth_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves );
36
37 ////////////////////////////////////////////////////////////////////////
38 /// FUNCTION DEFINITIONS ///
39 ////////////////////////////////////////////////////////////////////////
40
41 /**Function*************************************************************
42
43 Synopsis [Performs rewriting for one node.]
44
45 Description [This procedure considers all the cuts computed for the node
46 and tries to rewrite each of them using the "forest" of different AIG
47 structures precomputed and stored in the RWR manager.
48 Determines the best rewriting and computes the gain in the number of AIG
49 nodes in the final network. In the end, p->vFanins contains information
50 about the best cut that can be used for rewriting, while p->pGraph gives
51 the decomposition dag (represented using decomposition graph data structure).
52 Returns gain in the number of nodes or -1 if node cannot be rewritten.]
53
54 SideEffects []
55
56 SeeAlso []
57
58 ***********************************************************************/
Rwr_NodeRewrite(Rwr_Man_t * p,Cut_Man_t * pManCut,Abc_Obj_t * pNode,int fUpdateLevel,int fUseZeros,int fPlaceEnable)59 int Rwr_NodeRewrite( Rwr_Man_t * p, Cut_Man_t * pManCut, Abc_Obj_t * pNode, int fUpdateLevel, int fUseZeros, int fPlaceEnable )
60 {
61 int fVeryVerbose = 0;
62 Dec_Graph_t * pGraph;
63 Cut_Cut_t * pCut;//, * pTemp;
64 Abc_Obj_t * pFanin;
65 unsigned uPhase;
66 unsigned uTruthBest = 0; // Suppress "might be used uninitialized"
67 unsigned uTruth;
68 char * pPerm;
69 int Required, nNodesSaved;
70 int nNodesSaveCur = -1; // Suppress "might be used uninitialized"
71 int i, GainCur = -1, GainBest = -1;
72 abctime clk, clk2;//, Counter;
73
74 p->nNodesConsidered++;
75 // get the required times
76 Required = fUpdateLevel? Abc_ObjRequiredLevel(pNode) : ABC_INFINITY;
77
78 // get the node's cuts
79 clk = Abc_Clock();
80 pCut = (Cut_Cut_t *)Abc_NodeGetCutsRecursive( pManCut, pNode, 0, 0 );
81 assert( pCut != NULL );
82 p->timeCut += Abc_Clock() - clk;
83
84 //printf( " %d", Rwr_CutCountNumNodes(pNode, pCut) );
85 /*
86 Counter = 0;
87 for ( pTemp = pCut->pNext; pTemp; pTemp = pTemp->pNext )
88 Counter++;
89 printf( "%d ", Counter );
90 */
91 // go through the cuts
92 clk = Abc_Clock();
93 for ( pCut = pCut->pNext; pCut; pCut = pCut->pNext )
94 {
95 // consider only 4-input cuts
96 if ( pCut->nLeaves < 4 )
97 continue;
98 // Cut_CutPrint( pCut, 0 ), printf( "\n" );
99
100 // get the fanin permutation
101 uTruth = 0xFFFF & *Cut_CutReadTruth(pCut);
102 pPerm = p->pPerms4[ (int)p->pPerms[uTruth] ];
103 uPhase = p->pPhases[uTruth];
104 // collect fanins with the corresponding permutation/phase
105 Vec_PtrClear( p->vFaninsCur );
106 Vec_PtrFill( p->vFaninsCur, (int)pCut->nLeaves, 0 );
107 for ( i = 0; i < (int)pCut->nLeaves; i++ )
108 {
109 pFanin = Abc_NtkObj( pNode->pNtk, pCut->pLeaves[(int)pPerm[i]] );
110 if ( pFanin == NULL )
111 break;
112 pFanin = Abc_ObjNotCond(pFanin, ((uPhase & (1<<i)) > 0) );
113 Vec_PtrWriteEntry( p->vFaninsCur, i, pFanin );
114 }
115 if ( i != (int)pCut->nLeaves )
116 {
117 p->nCutsBad++;
118 continue;
119 }
120 p->nCutsGood++;
121
122 {
123 int Counter = 0;
124 Vec_PtrForEachEntry( Abc_Obj_t *, p->vFaninsCur, pFanin, i )
125 if ( Abc_ObjFanoutNum(Abc_ObjRegular(pFanin)) == 1 )
126 Counter++;
127 if ( Counter > 2 )
128 continue;
129 }
130
131 clk2 = Abc_Clock();
132 /*
133 printf( "Considering: (" );
134 Vec_PtrForEachEntry( Abc_Obj_t *, p->vFaninsCur, pFanin, i )
135 printf( "%d ", Abc_ObjFanoutNum(Abc_ObjRegular(pFanin)) );
136 printf( ")\n" );
137 */
138 // mark the fanin boundary
139 Vec_PtrForEachEntry( Abc_Obj_t *, p->vFaninsCur, pFanin, i )
140 Abc_ObjRegular(pFanin)->vFanouts.nSize++;
141
142 // label MFFC with current ID
143 Abc_NtkIncrementTravId( pNode->pNtk );
144 nNodesSaved = Abc_NodeMffcLabelAig( pNode );
145 // unmark the fanin boundary
146 Vec_PtrForEachEntry( Abc_Obj_t *, p->vFaninsCur, pFanin, i )
147 Abc_ObjRegular(pFanin)->vFanouts.nSize--;
148 p->timeMffc += Abc_Clock() - clk2;
149
150 // evaluate the cut
151 clk2 = Abc_Clock();
152 pGraph = Rwr_CutEvaluate( p, pNode, pCut, p->vFaninsCur, nNodesSaved, Required, &GainCur, fPlaceEnable );
153 p->timeEval += Abc_Clock() - clk2;
154
155 // check if the cut is better than the current best one
156 if ( pGraph != NULL && GainBest < GainCur )
157 {
158 // save this form
159 nNodesSaveCur = nNodesSaved;
160 GainBest = GainCur;
161 p->pGraph = pGraph;
162 p->fCompl = ((uPhase & (1<<4)) > 0);
163 uTruthBest = 0xFFFF & *Cut_CutReadTruth(pCut);
164 // collect fanins in the
165 Vec_PtrClear( p->vFanins );
166 Vec_PtrForEachEntry( Abc_Obj_t *, p->vFaninsCur, pFanin, i )
167 Vec_PtrPush( p->vFanins, pFanin );
168 }
169 }
170 p->timeRes += Abc_Clock() - clk;
171
172 if ( GainBest == -1 )
173 return -1;
174 /*
175 if ( GainBest > 0 )
176 {
177 printf( "Class %d ", p->pMap[uTruthBest] );
178 printf( "Gain = %d. Node %d : ", GainBest, pNode->Id );
179 Vec_PtrForEachEntry( Abc_Obj_t *, p->vFanins, pFanin, i )
180 printf( "%d ", Abc_ObjRegular(pFanin)->Id );
181 Dec_GraphPrint( stdout, p->pGraph, NULL, NULL );
182 printf( "\n" );
183 }
184 */
185
186 // printf( "%d", nNodesSaveCur - GainBest );
187 /*
188 if ( GainBest > 0 )
189 {
190 if ( Rwr_CutIsBoolean( pNode, p->vFanins ) )
191 printf( "b" );
192 else
193 {
194 printf( "Node %d : ", pNode->Id );
195 Vec_PtrForEachEntry( Abc_Obj_t *, p->vFanins, pFanin, i )
196 printf( "%d ", Abc_ObjRegular(pFanin)->Id );
197 printf( "a" );
198 }
199 }
200 */
201 /*
202 if ( GainBest > 0 )
203 if ( p->fCompl )
204 printf( "c" );
205 else
206 printf( "." );
207 */
208
209 // copy the leaves
210 Vec_PtrForEachEntry( Abc_Obj_t *, p->vFanins, pFanin, i )
211 Dec_GraphNode((Dec_Graph_t *)p->pGraph, i)->pFunc = pFanin;
212 /*
213 printf( "(" );
214 Vec_PtrForEachEntry( Abc_Obj_t *, p->vFanins, pFanin, i )
215 printf( " %d", Abc_ObjRegular(pFanin)->vFanouts.nSize - 1 );
216 printf( " ) " );
217 */
218 // printf( "%d ", Rwr_NodeGetDepth_rec( pNode, p->vFanins ) );
219
220 p->nScores[p->pMap[uTruthBest]]++;
221 p->nNodesGained += GainBest;
222 if ( fUseZeros || GainBest > 0 )
223 {
224 p->nNodesRewritten++;
225 }
226
227 // report the progress
228 if ( fVeryVerbose && GainBest > 0 )
229 {
230 printf( "Node %6s : ", Abc_ObjName(pNode) );
231 printf( "Fanins = %d. ", p->vFanins->nSize );
232 printf( "Save = %d. ", nNodesSaveCur );
233 printf( "Add = %d. ", nNodesSaveCur-GainBest );
234 printf( "GAIN = %d. ", GainBest );
235 printf( "Cone = %d. ", p->pGraph? Dec_GraphNodeNum((Dec_Graph_t *)p->pGraph) : 0 );
236 printf( "Class = %d. ", p->pMap[uTruthBest] );
237 printf( "\n" );
238 }
239 return GainBest;
240 }
241
242 /**Function*************************************************************
243
244 Synopsis [Evaluates the cut.]
245
246 Description []
247
248 SideEffects []
249
250 SeeAlso []
251
252 ***********************************************************************/
Rwr_CutEvaluate(Rwr_Man_t * p,Abc_Obj_t * pRoot,Cut_Cut_t * pCut,Vec_Ptr_t * vFaninsCur,int nNodesSaved,int LevelMax,int * pGainBest,int fPlaceEnable)253 Dec_Graph_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut, Vec_Ptr_t * vFaninsCur, int nNodesSaved, int LevelMax, int * pGainBest, int fPlaceEnable )
254 {
255 extern int Dec_GraphToNetworkCount( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int NodeMax, int LevelMax );
256 Vec_Ptr_t * vSubgraphs;
257 Dec_Graph_t * pGraphBest = NULL; // Suppress "might be used uninitialized"
258 Dec_Graph_t * pGraphCur;
259 Rwr_Node_t * pNode, * pFanin;
260 int nNodesAdded, GainBest, i, k;
261 unsigned uTruth;
262 float CostBest;//, CostCur;
263 // find the matching class of subgraphs
264 uTruth = 0xFFFF & *Cut_CutReadTruth(pCut);
265 vSubgraphs = Vec_VecEntry( p->vClasses, p->pMap[uTruth] );
266 p->nSubgraphs += vSubgraphs->nSize;
267 // determine the best subgraph
268 GainBest = -1;
269 CostBest = ABC_INFINITY;
270 Vec_PtrForEachEntry( Rwr_Node_t *, vSubgraphs, pNode, i )
271 {
272 // get the current graph
273 pGraphCur = (Dec_Graph_t *)pNode->pNext;
274 // copy the leaves
275 Vec_PtrForEachEntry( Rwr_Node_t *, vFaninsCur, pFanin, k )
276 Dec_GraphNode(pGraphCur, k)->pFunc = pFanin;
277 // detect how many unlabeled nodes will be reused
278 nNodesAdded = Dec_GraphToNetworkCount( pRoot, pGraphCur, nNodesSaved, LevelMax );
279 if ( nNodesAdded == -1 )
280 continue;
281 assert( nNodesSaved >= nNodesAdded );
282 /*
283 // evaluate the cut
284 if ( fPlaceEnable )
285 {
286 extern float Abc_PlaceEvaluateCut( Abc_Obj_t * pRoot, Vec_Ptr_t * vFanins );
287
288 float Alpha = 0.5; // ???
289 float PlaceCost;
290
291 // get the placement cost of the cut
292 PlaceCost = Abc_PlaceEvaluateCut( pRoot, vFaninsCur );
293
294 // get the weigted cost of the cut
295 CostCur = nNodesSaved - nNodesAdded + Alpha * PlaceCost;
296
297 // do not allow uphill moves
298 if ( nNodesSaved - nNodesAdded < 0 )
299 continue;
300
301 // decide what cut to use
302 if ( CostBest > CostCur )
303 {
304 GainBest = nNodesSaved - nNodesAdded; // pure node cost
305 CostBest = CostCur; // cost with placement
306 pGraphBest = pGraphCur; // subgraph to be used for rewriting
307
308 // score the graph
309 if ( nNodesSaved - nNodesAdded > 0 )
310 {
311 pNode->nScore++;
312 pNode->nGain += GainBest;
313 pNode->nAdded += nNodesAdded;
314 }
315 }
316 }
317 else
318 */
319 {
320 // count the gain at this node
321 if ( GainBest < nNodesSaved - nNodesAdded )
322 {
323 GainBest = nNodesSaved - nNodesAdded;
324 pGraphBest = pGraphCur;
325
326 // score the graph
327 if ( nNodesSaved - nNodesAdded > 0 )
328 {
329 pNode->nScore++;
330 pNode->nGain += GainBest;
331 pNode->nAdded += nNodesAdded;
332 }
333 }
334 }
335 }
336 if ( GainBest == -1 )
337 return NULL;
338 *pGainBest = GainBest;
339 return pGraphBest;
340 }
341
342 /**Function*************************************************************
343
344 Synopsis [Checks the type of the cut.]
345
346 Description []
347
348 SideEffects []
349
350 SeeAlso []
351
352 ***********************************************************************/
Rwr_CutIsBoolean_rec(Abc_Obj_t * pObj,Vec_Ptr_t * vLeaves,int fMarkA)353 void Rwr_CutIsBoolean_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves, int fMarkA )
354 {
355 if ( Vec_PtrFind(vLeaves, pObj) >= 0 || Vec_PtrFind(vLeaves, Abc_ObjNot(pObj)) >= 0 )
356 {
357 if ( fMarkA )
358 pObj->fMarkA = 1;
359 else
360 pObj->fMarkB = 1;
361 return;
362 }
363 assert( !Abc_ObjIsCi(pObj) );
364 Rwr_CutIsBoolean_rec( Abc_ObjFanin0(pObj), vLeaves, fMarkA );
365 Rwr_CutIsBoolean_rec( Abc_ObjFanin1(pObj), vLeaves, fMarkA );
366 }
367
368 /**Function*************************************************************
369
370 Synopsis [Checks the type of the cut.]
371
372 Description [Returns 1(0) if the cut is Boolean (algebraic).]
373
374 SideEffects []
375
376 SeeAlso []
377
378 ***********************************************************************/
Rwr_CutIsBoolean(Abc_Obj_t * pObj,Vec_Ptr_t * vLeaves)379 int Rwr_CutIsBoolean( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves )
380 {
381 Abc_Obj_t * pTemp;
382 int i, RetValue;
383 Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pTemp, i )
384 {
385 pTemp = Abc_ObjRegular(pTemp);
386 assert( !pTemp->fMarkA && !pTemp->fMarkB );
387 }
388 Rwr_CutIsBoolean_rec( Abc_ObjFanin0(pObj), vLeaves, 1 );
389 Rwr_CutIsBoolean_rec( Abc_ObjFanin1(pObj), vLeaves, 0 );
390 RetValue = 0;
391 Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pTemp, i )
392 {
393 pTemp = Abc_ObjRegular(pTemp);
394 RetValue |= pTemp->fMarkA && pTemp->fMarkB;
395 pTemp->fMarkA = pTemp->fMarkB = 0;
396 }
397 return RetValue;
398 }
399
400
401 /**Function*************************************************************
402
403 Synopsis [Count the nodes in the cut space of a node.]
404
405 Description []
406
407 SideEffects []
408
409 SeeAlso []
410
411 ***********************************************************************/
Rwr_CutCountNumNodes_rec(Abc_Obj_t * pObj,Cut_Cut_t * pCut,Vec_Ptr_t * vNodes)412 void Rwr_CutCountNumNodes_rec( Abc_Obj_t * pObj, Cut_Cut_t * pCut, Vec_Ptr_t * vNodes )
413 {
414 int i;
415 for ( i = 0; i < (int)pCut->nLeaves; i++ )
416 if ( pCut->pLeaves[i] == pObj->Id )
417 {
418 // check if the node is collected
419 if ( pObj->fMarkC == 0 )
420 {
421 pObj->fMarkC = 1;
422 Vec_PtrPush( vNodes, pObj );
423 }
424 return;
425 }
426 assert( Abc_ObjIsNode(pObj) );
427 // check if the node is collected
428 if ( pObj->fMarkC == 0 )
429 {
430 pObj->fMarkC = 1;
431 Vec_PtrPush( vNodes, pObj );
432 }
433 // traverse the fanins
434 Rwr_CutCountNumNodes_rec( Abc_ObjFanin0(pObj), pCut, vNodes );
435 Rwr_CutCountNumNodes_rec( Abc_ObjFanin1(pObj), pCut, vNodes );
436 }
437
438 /**Function*************************************************************
439
440 Synopsis [Count the nodes in the cut space of a node.]
441
442 Description []
443
444 SideEffects []
445
446 SeeAlso []
447
448 ***********************************************************************/
Rwr_CutCountNumNodes(Abc_Obj_t * pObj,Cut_Cut_t * pCut)449 int Rwr_CutCountNumNodes( Abc_Obj_t * pObj, Cut_Cut_t * pCut )
450 {
451 Vec_Ptr_t * vNodes;
452 int i, Counter;
453 // collect all nodes
454 vNodes = Vec_PtrAlloc( 100 );
455 for ( pCut = pCut->pNext; pCut; pCut = pCut->pNext )
456 Rwr_CutCountNumNodes_rec( pObj, pCut, vNodes );
457 // clean all nodes
458 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
459 pObj->fMarkC = 0;
460 // delete and return
461 Counter = Vec_PtrSize(vNodes);
462 Vec_PtrFree( vNodes );
463 return Counter;
464 }
465
466
467 /**Function*************************************************************
468
469 Synopsis [Returns depth of the cut.]
470
471 Description []
472
473 SideEffects []
474
475 SeeAlso []
476
477 ***********************************************************************/
Rwr_NodeGetDepth_rec(Abc_Obj_t * pObj,Vec_Ptr_t * vLeaves)478 int Rwr_NodeGetDepth_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves )
479 {
480 Abc_Obj_t * pLeaf;
481 int i, Depth0, Depth1;
482 if ( Abc_ObjIsCi(pObj) )
483 return 0;
484 Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pLeaf, i )
485 if ( pObj == Abc_ObjRegular(pLeaf) )
486 return 0;
487 Depth0 = Rwr_NodeGetDepth_rec( Abc_ObjFanin0(pObj), vLeaves );
488 Depth1 = Rwr_NodeGetDepth_rec( Abc_ObjFanin1(pObj), vLeaves );
489 return 1 + Abc_MaxInt( Depth0, Depth1 );
490 }
491
492
493 /**Function*************************************************************
494
495 Synopsis []
496
497 Description []
498
499 SideEffects []
500
501 SeeAlso []
502
503 ***********************************************************************/
Rwr_ScoresClean(Rwr_Man_t * p)504 void Rwr_ScoresClean( Rwr_Man_t * p )
505 {
506 Vec_Ptr_t * vSubgraphs;
507 Rwr_Node_t * pNode;
508 int i, k;
509 for ( i = 0; i < p->vClasses->nSize; i++ )
510 {
511 vSubgraphs = Vec_VecEntry( p->vClasses, i );
512 Vec_PtrForEachEntry( Rwr_Node_t *, vSubgraphs, pNode, k )
513 pNode->nScore = pNode->nGain = pNode->nAdded = 0;
514 }
515 }
516
517 static int Gains[222];
518
519 /**Function*************************************************************
520
521 Synopsis []
522
523 Description []
524
525 SideEffects []
526
527 SeeAlso []
528
529 ***********************************************************************/
Rwr_ScoresCompare(int * pNum1,int * pNum2)530 int Rwr_ScoresCompare( int * pNum1, int * pNum2 )
531 {
532 if ( Gains[*pNum1] > Gains[*pNum2] )
533 return -1;
534 if ( Gains[*pNum1] < Gains[*pNum2] )
535 return 1;
536 return 0;
537 }
538
539 /**Function*************************************************************
540
541 Synopsis []
542
543 Description []
544
545 SideEffects []
546
547 SeeAlso []
548
549 ***********************************************************************/
Rwr_ScoresReport(Rwr_Man_t * p)550 void Rwr_ScoresReport( Rwr_Man_t * p )
551 {
552 extern void Ivy_TruthDsdComputePrint( unsigned uTruth );
553 int Perm[222];
554 Vec_Ptr_t * vSubgraphs;
555 Rwr_Node_t * pNode;
556 int i, iNew, k;
557 unsigned uTruth;
558 // collect total gains
559 assert( p->vClasses->nSize == 222 );
560 for ( i = 0; i < p->vClasses->nSize; i++ )
561 {
562 Perm[i] = i;
563 Gains[i] = 0;
564 vSubgraphs = Vec_VecEntry( p->vClasses, i );
565 Vec_PtrForEachEntry( Rwr_Node_t *, vSubgraphs, pNode, k )
566 Gains[i] += pNode->nGain;
567 }
568 // sort the gains
569 qsort( Perm, (size_t)222, sizeof(int), (int (*)(const void *, const void *))Rwr_ScoresCompare );
570
571 // print classes
572 for ( i = 0; i < p->vClasses->nSize; i++ )
573 {
574 iNew = Perm[i];
575 if ( Gains[iNew] == 0 )
576 break;
577 vSubgraphs = Vec_VecEntry( p->vClasses, iNew );
578 printf( "CLASS %3d: Subgr = %3d. Total gain = %6d. ", iNew, Vec_PtrSize(vSubgraphs), Gains[iNew] );
579 uTruth = (unsigned)p->pMapInv[iNew];
580 Extra_PrintBinary( stdout, &uTruth, 16 );
581 printf( " " );
582 Ivy_TruthDsdComputePrint( (unsigned)p->pMapInv[iNew] | ((unsigned)p->pMapInv[iNew] << 16) );
583 Vec_PtrForEachEntry( Rwr_Node_t *, vSubgraphs, pNode, k )
584 {
585 if ( pNode->nScore == 0 )
586 continue;
587 printf( " %2d: S=%5d. A=%5d. G=%6d. ", k, pNode->nScore, pNode->nAdded, pNode->nGain );
588 Dec_GraphPrint( stdout, (Dec_Graph_t *)pNode->pNext, NULL, NULL );
589 }
590 }
591 }
592
593 ////////////////////////////////////////////////////////////////////////
594 /// END OF FILE ///
595 ////////////////////////////////////////////////////////////////////////
596
597
598 ABC_NAMESPACE_IMPL_END
599
600