1 /**CFile****************************************************************
2
3 FileName [ivyCut.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [And-Inverter Graph package.]
8
9 Synopsis [Computes reconvergence driven sequential cut.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - May 11, 2006.]
16
17 Revision [$Id: ivyCut.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "ivy.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
Ivy_NodeCutHashValue(int NodeId)30 static inline int Ivy_NodeCutHashValue( int NodeId ) { return 1 << (NodeId % 31); }
31
32 ////////////////////////////////////////////////////////////////////////
33 /// FUNCTION DEFINITIONS ///
34 ////////////////////////////////////////////////////////////////////////
35
36 /**Function*************************************************************
37
38 Synopsis [Evaluate the cost of removing the node from the set of leaves.]
39
40 Description [Returns the number of new leaves that will be brought in.
41 Returns large number if the node cannot be removed from the set of leaves.]
42
43 SideEffects []
44
45 SeeAlso []
46
47 ***********************************************************************/
Ivy_NodeGetLeafCostOne(Ivy_Man_t * p,int Leaf,Vec_Int_t * vInside)48 static inline int Ivy_NodeGetLeafCostOne( Ivy_Man_t * p, int Leaf, Vec_Int_t * vInside )
49 {
50 Ivy_Obj_t * pNode;
51 int nLatches, FaninLeaf, Cost;
52 // make sure leaf is not a contant node
53 assert( Leaf > 0 );
54 // get the node
55 pNode = Ivy_ManObj( p, Ivy_LeafId(Leaf) );
56 // cannot expand over the PI node
57 if ( Ivy_ObjIsPi(pNode) || Ivy_ObjIsConst1(pNode) )
58 return 999;
59 // get the number of latches
60 nLatches = Ivy_LeafLat(Leaf) + Ivy_ObjIsLatch(pNode);
61 if ( nLatches > 15 )
62 return 999;
63 // get the first fanin
64 FaninLeaf = Ivy_LeafCreate( Ivy_ObjFaninId0(pNode), nLatches );
65 Cost = FaninLeaf && (Vec_IntFind(vInside, FaninLeaf) == -1);
66 // quit if this is the one fanin node
67 if ( Ivy_ObjIsLatch(pNode) || Ivy_ObjIsBuf(pNode) )
68 return Cost;
69 assert( Ivy_ObjIsNode(pNode) );
70 // get the second fanin
71 FaninLeaf = Ivy_LeafCreate( Ivy_ObjFaninId1(pNode), nLatches );
72 Cost += FaninLeaf && (Vec_IntFind(vInside, FaninLeaf) == -1);
73 return Cost;
74 }
75
76 /**Function*************************************************************
77
78 Synopsis [Builds reconvergence-driven cut by changing one leaf at a time.]
79
80 Description [This procedure looks at the current leaves and tries to change
81 one leaf at a time in such a way that the cut grows as little as possible.
82 In evaluating the fanins, this procedure looks only at their immediate
83 predecessors (this is why it is called a one-level construction procedure).]
84
85 SideEffects []
86
87 SeeAlso []
88
89 ***********************************************************************/
Ivy_ManSeqFindCut_int(Ivy_Man_t * p,Vec_Int_t * vFront,Vec_Int_t * vInside,int nSizeLimit)90 int Ivy_ManSeqFindCut_int( Ivy_Man_t * p, Vec_Int_t * vFront, Vec_Int_t * vInside, int nSizeLimit )
91 {
92 Ivy_Obj_t * pNode;
93 int CostBest, CostCur, Leaf, LeafBest, Next, nLatches, i;
94 int LeavesBest[10];
95 int Counter;
96
97 // add random selection of the best fanin!!!
98
99 // find the best fanin
100 CostBest = 99;
101 LeafBest = -1;
102 Counter = -1;
103 //printf( "Evaluating fanins of the cut:\n" );
104 Vec_IntForEachEntry( vFront, Leaf, i )
105 {
106 CostCur = Ivy_NodeGetLeafCostOne( p, Leaf, vInside );
107 //printf( " Fanin %s has cost %d.\n", Ivy_ObjName(pNode), CostCur );
108 if ( CostBest > CostCur )
109 {
110 CostBest = CostCur;
111 LeafBest = Leaf;
112 LeavesBest[0] = Leaf;
113 Counter = 1;
114 }
115 else if ( CostBest == CostCur )
116 LeavesBest[Counter++] = Leaf;
117
118 if ( CostBest <= 1 ) // can be if ( CostBest <= 1 )
119 break;
120 }
121 if ( CostBest == 99 )
122 return 0;
123 // return Ivy_NodeBuildCutLevelTwo_int( vInside, vFront, nFaninLimit );
124
125 assert( CostBest < 3 );
126 if ( Vec_IntSize(vFront) - 1 + CostBest > nSizeLimit )
127 return 0;
128 // return Ivy_NodeBuildCutLevelTwo_int( vInside, vFront, nFaninLimit );
129
130 assert( Counter > 0 );
131 printf( "%d", Counter );
132
133 LeafBest = LeavesBest[rand() % Counter];
134
135 // remove the node from the array
136 assert( LeafBest >= 0 );
137 Vec_IntRemove( vFront, LeafBest );
138 //printf( "Removing fanin %s.\n", Ivy_ObjName(pNode) );
139
140 // get the node and its latches
141 pNode = Ivy_ManObj( p, Ivy_LeafId(LeafBest) );
142 nLatches = Ivy_LeafLat(LeafBest) + Ivy_ObjIsLatch(pNode);
143 assert( Ivy_ObjIsNode(pNode) || Ivy_ObjIsLatch(pNode) || Ivy_ObjIsBuf(pNode) );
144
145 // add the left child to the fanins
146 Next = Ivy_LeafCreate( Ivy_ObjFaninId0(pNode), nLatches );
147 if ( Next && Vec_IntFind(vInside, Next) == -1 )
148 {
149 //printf( "Adding fanin %s.\n", Ivy_ObjName(pNext) );
150 Vec_IntPush( vFront, Next );
151 Vec_IntPush( vInside, Next );
152 }
153
154 // quit if this is the one fanin node
155 if ( Ivy_ObjIsLatch(pNode) || Ivy_ObjIsBuf(pNode) )
156 return 1;
157 assert( Ivy_ObjIsNode(pNode) );
158
159 // add the right child to the fanins
160 Next = Ivy_LeafCreate( Ivy_ObjFaninId1(pNode), nLatches );
161 if ( Next && Vec_IntFind(vInside, Next) == -1 )
162 {
163 //printf( "Adding fanin %s.\n", Ivy_ObjName(pNext) );
164 Vec_IntPush( vFront, Next );
165 Vec_IntPush( vInside, Next );
166 }
167 assert( Vec_IntSize(vFront) <= nSizeLimit );
168 // keep doing this
169 return 1;
170 }
171
172 /**Function*************************************************************
173
174 Synopsis [Computes one sequential cut of the given size.]
175
176 Description []
177
178 SideEffects []
179
180 SeeAlso []
181
182 ***********************************************************************/
Ivy_ManSeqFindCut(Ivy_Man_t * p,Ivy_Obj_t * pRoot,Vec_Int_t * vFront,Vec_Int_t * vInside,int nSize)183 void Ivy_ManSeqFindCut( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Vec_Int_t * vFront, Vec_Int_t * vInside, int nSize )
184 {
185 assert( !Ivy_IsComplement(pRoot) );
186 assert( Ivy_ObjIsNode(pRoot) );
187 assert( Ivy_ObjFaninId0(pRoot) );
188 assert( Ivy_ObjFaninId1(pRoot) );
189
190 // start the cut
191 Vec_IntClear( vFront );
192 Vec_IntPush( vFront, Ivy_LeafCreate(Ivy_ObjFaninId0(pRoot), 0) );
193 Vec_IntPush( vFront, Ivy_LeafCreate(Ivy_ObjFaninId1(pRoot), 0) );
194
195 // start the visited nodes
196 Vec_IntClear( vInside );
197 Vec_IntPush( vInside, Ivy_LeafCreate(pRoot->Id, 0) );
198 Vec_IntPush( vInside, Ivy_LeafCreate(Ivy_ObjFaninId0(pRoot), 0) );
199 Vec_IntPush( vInside, Ivy_LeafCreate(Ivy_ObjFaninId1(pRoot), 0) );
200
201 // compute the cut
202 while ( Ivy_ManSeqFindCut_int( p, vFront, vInside, nSize ) );
203 assert( Vec_IntSize(vFront) <= nSize );
204 }
205
206
207
208
209
210 /**Function*************************************************************
211
212 Synopsis [Computing Boolean cut.]
213
214 Description []
215
216 SideEffects []
217
218 SeeAlso []
219
220 ***********************************************************************/
Ivy_ManFindBoolCut_rec(Ivy_Man_t * p,Ivy_Obj_t * pObj,Vec_Ptr_t * vLeaves,Vec_Ptr_t * vVolume,Ivy_Obj_t * pPivot)221 int Ivy_ManFindBoolCut_rec( Ivy_Man_t * p, Ivy_Obj_t * pObj, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVolume, Ivy_Obj_t * pPivot )
222 {
223 int RetValue0, RetValue1;
224 if ( pObj == pPivot )
225 {
226 Vec_PtrPushUnique( vLeaves, pObj );
227 Vec_PtrPushUnique( vVolume, pObj );
228 return 1;
229 }
230 if ( pObj->fMarkA )
231 return 0;
232
233 // assert( !Ivy_ObjIsCi(pObj) );
234 if ( Ivy_ObjIsCi(pObj) )
235 return 0;
236
237 if ( Ivy_ObjIsBuf(pObj) )
238 {
239 RetValue0 = Ivy_ManFindBoolCut_rec( p, Ivy_ObjFanin0(pObj), vLeaves, vVolume, pPivot );
240 if ( !RetValue0 )
241 return 0;
242 Vec_PtrPushUnique( vVolume, pObj );
243 return 1;
244 }
245 assert( Ivy_ObjIsNode(pObj) );
246 RetValue0 = Ivy_ManFindBoolCut_rec( p, Ivy_ObjFanin0(pObj), vLeaves, vVolume, pPivot );
247 RetValue1 = Ivy_ManFindBoolCut_rec( p, Ivy_ObjFanin1(pObj), vLeaves, vVolume, pPivot );
248 if ( !RetValue0 && !RetValue1 )
249 return 0;
250 // add new leaves
251 if ( !RetValue0 )
252 {
253 Vec_PtrPushUnique( vLeaves, Ivy_ObjFanin0(pObj) );
254 Vec_PtrPushUnique( vVolume, Ivy_ObjFanin0(pObj) );
255 }
256 if ( !RetValue1 )
257 {
258 Vec_PtrPushUnique( vLeaves, Ivy_ObjFanin1(pObj) );
259 Vec_PtrPushUnique( vVolume, Ivy_ObjFanin1(pObj) );
260 }
261 Vec_PtrPushUnique( vVolume, pObj );
262 return 1;
263 }
264
265 /**Function*************************************************************
266
267 Synopsis [Returns the cost of one node (how many new nodes are added.]
268
269 Description []
270
271 SideEffects []
272
273 SeeAlso []
274
275 ***********************************************************************/
Ivy_ManFindBoolCutCost(Ivy_Obj_t * pObj)276 int Ivy_ManFindBoolCutCost( Ivy_Obj_t * pObj )
277 {
278 int Cost;
279 // make sure the node is in the construction zone
280 assert( pObj->fMarkA == 1 );
281 // cannot expand over the PI node
282 if ( Ivy_ObjIsCi(pObj) )
283 return 999;
284 // always expand over the buffer
285 if ( Ivy_ObjIsBuf(pObj) )
286 return !Ivy_ObjFanin0(pObj)->fMarkA;
287 // get the cost of the cone
288 Cost = (!Ivy_ObjFanin0(pObj)->fMarkA) + (!Ivy_ObjFanin1(pObj)->fMarkA);
289 // return the number of nodes to be added to the leaves if this node is removed
290 return Cost;
291 }
292
293 /**Function*************************************************************
294
295 Synopsis [Computing Boolean cut.]
296
297 Description []
298
299 SideEffects []
300
301 SeeAlso []
302
303 ***********************************************************************/
Ivy_ManFindBoolCut(Ivy_Man_t * p,Ivy_Obj_t * pRoot,Vec_Ptr_t * vFront,Vec_Ptr_t * vVolume,Vec_Ptr_t * vLeaves)304 int Ivy_ManFindBoolCut( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Vec_Ptr_t * vFront, Vec_Ptr_t * vVolume, Vec_Ptr_t * vLeaves )
305 {
306 Ivy_Obj_t * pObj = NULL; // Suppress "might be used uninitialized"
307 Ivy_Obj_t * pFaninC, * pFanin0, * pFanin1, * pPivot;
308 int RetValue, LevelLimit, Lev, k;
309 assert( !Ivy_IsComplement(pRoot) );
310 // clear the frontier and collect the nodes
311 Vec_PtrClear( vFront );
312 Vec_PtrClear( vVolume );
313 if ( Ivy_ObjIsMuxType(pRoot) )
314 pFaninC = Ivy_ObjRecognizeMux( pRoot, &pFanin0, &pFanin1 );
315 else
316 {
317 pFaninC = NULL;
318 pFanin0 = Ivy_ObjFanin0(pRoot);
319 pFanin1 = Ivy_ObjFanin1(pRoot);
320 }
321 // start cone A
322 pFanin0->fMarkA = 1;
323 Vec_PtrPush( vFront, pFanin0 );
324 Vec_PtrPush( vVolume, pFanin0 );
325 // start cone B
326 pFanin1->fMarkB = 1;
327 Vec_PtrPush( vFront, pFanin1 );
328 Vec_PtrPush( vVolume, pFanin1 );
329 // iteratively expand until the common node (pPivot) is found or limit is reached
330 assert( Ivy_ObjLevel(pRoot) == Ivy_ObjLevelNew(pRoot) );
331 pPivot = NULL;
332 LevelLimit = IVY_MAX( Ivy_ObjLevel(pRoot) - 10, 1 );
333 for ( Lev = Ivy_ObjLevel(pRoot) - 1; Lev >= LevelLimit; Lev-- )
334 {
335 while ( 1 )
336 {
337 // find the next node to expand on this level
338 Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pObj, k )
339 if ( (int)pObj->Level == Lev )
340 break;
341 if ( k == Vec_PtrSize(vFront) )
342 break;
343 assert( (int)pObj->Level <= Lev );
344 assert( pObj->fMarkA ^ pObj->fMarkB );
345 // remove the old node
346 Vec_PtrRemove( vFront, pObj );
347
348 // expand this node
349 pFanin0 = Ivy_ObjFanin0(pObj);
350 if ( !pFanin0->fMarkA && !pFanin0->fMarkB )
351 {
352 Vec_PtrPush( vFront, pFanin0 );
353 Vec_PtrPush( vVolume, pFanin0 );
354 }
355 // mark the new nodes
356 if ( pObj->fMarkA )
357 pFanin0->fMarkA = 1;
358 if ( pObj->fMarkB )
359 pFanin0->fMarkB = 1;
360
361 if ( Ivy_ObjIsBuf(pObj) )
362 {
363 if ( pFanin0->fMarkA && pFanin0->fMarkB )
364 {
365 pPivot = pFanin0;
366 break;
367 }
368 continue;
369 }
370
371 // expand this node
372 pFanin1 = Ivy_ObjFanin1(pObj);
373 if ( !pFanin1->fMarkA && !pFanin1->fMarkB )
374 {
375 Vec_PtrPush( vFront, pFanin1 );
376 Vec_PtrPush( vVolume, pFanin1 );
377 }
378 // mark the new nodes
379 if ( pObj->fMarkA )
380 pFanin1->fMarkA = 1;
381 if ( pObj->fMarkB )
382 pFanin1->fMarkB = 1;
383
384 // consider if it is time to quit
385 if ( pFanin0->fMarkA && pFanin0->fMarkB )
386 {
387 pPivot = pFanin0;
388 break;
389 }
390 if ( pFanin1->fMarkA && pFanin1->fMarkB )
391 {
392 pPivot = pFanin1;
393 break;
394 }
395 }
396 if ( pPivot != NULL )
397 break;
398 }
399 if ( pPivot == NULL )
400 return 0;
401 // if the MUX control is defined, it should not be
402 if ( pFaninC && !pFaninC->fMarkA && !pFaninC->fMarkB )
403 Vec_PtrPush( vFront, pFaninC );
404 // clean the markings
405 Vec_PtrForEachEntry( Ivy_Obj_t *, vVolume, pObj, k )
406 pObj->fMarkA = pObj->fMarkB = 0;
407
408 // mark the nodes on the frontier (including the pivot)
409 Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pObj, k )
410 pObj->fMarkA = 1;
411 // cut exists, collect all the nodes on the shortest path to the pivot
412 Vec_PtrClear( vLeaves );
413 Vec_PtrClear( vVolume );
414 RetValue = Ivy_ManFindBoolCut_rec( p, pRoot, vLeaves, vVolume, pPivot );
415 assert( RetValue == 1 );
416 // unmark the nodes on the frontier (including the pivot)
417 Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pObj, k )
418 pObj->fMarkA = 0;
419
420 // mark the nodes in the volume
421 Vec_PtrForEachEntry( Ivy_Obj_t *, vVolume, pObj, k )
422 pObj->fMarkA = 1;
423 // expand the cut without increasing its size
424 while ( 1 )
425 {
426 Vec_PtrForEachEntry( Ivy_Obj_t *, vLeaves, pObj, k )
427 if ( Ivy_ManFindBoolCutCost(pObj) < 2 )
428 break;
429 if ( k == Vec_PtrSize(vLeaves) )
430 break;
431 // the node can be expanded
432 // remove the old node
433 Vec_PtrRemove( vLeaves, pObj );
434 // expand this node
435 pFanin0 = Ivy_ObjFanin0(pObj);
436 if ( !pFanin0->fMarkA )
437 {
438 pFanin0->fMarkA = 1;
439 Vec_PtrPush( vVolume, pFanin0 );
440 Vec_PtrPush( vLeaves, pFanin0 );
441 }
442 if ( Ivy_ObjIsBuf(pObj) )
443 continue;
444 // expand this node
445 pFanin1 = Ivy_ObjFanin1(pObj);
446 if ( !pFanin1->fMarkA )
447 {
448 pFanin1->fMarkA = 1;
449 Vec_PtrPush( vVolume, pFanin1 );
450 Vec_PtrPush( vLeaves, pFanin1 );
451 }
452 }
453 // unmark the nodes in the volume
454 Vec_PtrForEachEntry( Ivy_Obj_t *, vVolume, pObj, k )
455 pObj->fMarkA = 0;
456 return 1;
457 }
458
459
460 /**Function*************************************************************
461
462 Synopsis []
463
464 Description []
465
466 SideEffects []
467
468 SeeAlso []
469
470 ***********************************************************************/
Ivy_ManTestCutsBool(Ivy_Man_t * p)471 void Ivy_ManTestCutsBool( Ivy_Man_t * p )
472 {
473 Vec_Ptr_t * vFront, * vVolume, * vLeaves;
474 Ivy_Obj_t * pObj;//, * pTemp;
475 int i, RetValue;//, k;
476 vFront = Vec_PtrAlloc( 100 );
477 vVolume = Vec_PtrAlloc( 100 );
478 vLeaves = Vec_PtrAlloc( 100 );
479 Ivy_ManForEachObj( p, pObj, i )
480 {
481 if ( !Ivy_ObjIsNode(pObj) )
482 continue;
483 if ( Ivy_ObjIsMuxType(pObj) )
484 {
485 printf( "m" );
486 continue;
487 }
488 if ( Ivy_ObjIsExor(pObj) )
489 printf( "x" );
490 RetValue = Ivy_ManFindBoolCut( p, pObj, vFront, vVolume, vLeaves );
491 if ( RetValue == 0 )
492 printf( "- " );
493 else
494 printf( "%d ", Vec_PtrSize(vLeaves) );
495 /*
496 printf( "( " );
497 Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pTemp, k )
498 printf( "%d ", Ivy_ObjRefs(Ivy_Regular(pTemp)) );
499 printf( ")\n" );
500 */
501 }
502 printf( "\n" );
503 Vec_PtrFree( vFront );
504 Vec_PtrFree( vVolume );
505 Vec_PtrFree( vLeaves );
506 }
507
508
509
510 /**Function*************************************************************
511
512 Synopsis [Find the hash value of the cut.]
513
514 Description []
515
516 SideEffects []
517
518 SeeAlso []
519
520 ***********************************************************************/
Ivy_NodeCutHash(Ivy_Cut_t * pCut)521 static inline unsigned Ivy_NodeCutHash( Ivy_Cut_t * pCut )
522 {
523 int i;
524 // for ( i = 1; i < pCut->nSize; i++ )
525 // assert( pCut->pArray[i-1] < pCut->pArray[i] );
526 pCut->uHash = 0;
527 for ( i = 0; i < pCut->nSize; i++ )
528 pCut->uHash |= (1 << (pCut->pArray[i] % 31));
529 return pCut->uHash;
530 }
531
532 /**Function*************************************************************
533
534 Synopsis [Removes one node to the cut.]
535
536 Description []
537
538 SideEffects []
539
540 SeeAlso []
541
542 ***********************************************************************/
Ivy_NodeCutShrink(Ivy_Cut_t * pCut,int iOld)543 static inline void Ivy_NodeCutShrink( Ivy_Cut_t * pCut, int iOld )
544 {
545 int i, k;
546 for ( i = k = 0; i < pCut->nSize; i++ )
547 if ( pCut->pArray[i] != iOld )
548 pCut->pArray[k++] = pCut->pArray[i];
549 assert( k == pCut->nSize - 1 );
550 pCut->nSize--;
551 }
552
553 /**Function*************************************************************
554
555 Synopsis [Adds one node to the cut.]
556
557 Description [Returns 1 if the cuts is still okay.]
558
559 SideEffects []
560
561 SeeAlso []
562
563 ***********************************************************************/
Ivy_NodeCutExtend(Ivy_Cut_t * pCut,int iNew)564 static inline int Ivy_NodeCutExtend( Ivy_Cut_t * pCut, int iNew )
565 {
566 int i;
567 for ( i = 0; i < pCut->nSize; i++ )
568 if ( pCut->pArray[i] == iNew )
569 return 1;
570 // check if there is room
571 if ( pCut->nSize == pCut->nSizeMax )
572 return 0;
573 // add the new one
574 for ( i = pCut->nSize - 1; i >= 0; i-- )
575 if ( pCut->pArray[i] > iNew )
576 pCut->pArray[i+1] = pCut->pArray[i];
577 else
578 {
579 assert( pCut->pArray[i] < iNew );
580 break;
581 }
582 pCut->pArray[i+1] = iNew;
583 pCut->nSize++;
584 return 1;
585 }
586
587 /**Function*************************************************************
588
589 Synopsis [Returns 1 if the cut can be constructed; 0 otherwise.]
590
591 Description []
592
593 SideEffects []
594
595 SeeAlso []
596
597 ***********************************************************************/
Ivy_NodeCutPrescreen(Ivy_Cut_t * pCut,int Id0,int Id1)598 static inline int Ivy_NodeCutPrescreen( Ivy_Cut_t * pCut, int Id0, int Id1 )
599 {
600 int i;
601 if ( pCut->nSize < pCut->nSizeMax )
602 return 1;
603 for ( i = 0; i < pCut->nSize; i++ )
604 if ( pCut->pArray[i] == Id0 || pCut->pArray[i] == Id1 )
605 return 1;
606 return 0;
607 }
608
609 /**Function*************************************************************
610
611 Synopsis [Derives new cut.]
612
613 Description []
614
615 SideEffects []
616
617 SeeAlso []
618
619 ***********************************************************************/
Ivy_NodeCutDeriveNew(Ivy_Cut_t * pCut,Ivy_Cut_t * pCutNew,int IdOld,int IdNew0,int IdNew1)620 static inline int Ivy_NodeCutDeriveNew( Ivy_Cut_t * pCut, Ivy_Cut_t * pCutNew, int IdOld, int IdNew0, int IdNew1 )
621 {
622 unsigned uHash = 0;
623 int i, k;
624 assert( pCut->nSize > 0 );
625 assert( IdNew0 < IdNew1 );
626 for ( i = k = 0; i < pCut->nSize; i++ )
627 {
628 if ( pCut->pArray[i] == IdOld )
629 continue;
630 if ( IdNew0 <= pCut->pArray[i] )
631 {
632 if ( IdNew0 < pCut->pArray[i] )
633 {
634 pCutNew->pArray[ k++ ] = IdNew0;
635 uHash |= Ivy_NodeCutHashValue( IdNew0 );
636 }
637 IdNew0 = 0x7FFFFFFF;
638 }
639 if ( IdNew1 <= pCut->pArray[i] )
640 {
641 if ( IdNew1 < pCut->pArray[i] )
642 {
643 pCutNew->pArray[ k++ ] = IdNew1;
644 uHash |= Ivy_NodeCutHashValue( IdNew1 );
645 }
646 IdNew1 = 0x7FFFFFFF;
647 }
648 pCutNew->pArray[ k++ ] = pCut->pArray[i];
649 uHash |= Ivy_NodeCutHashValue( pCut->pArray[i] );
650 }
651 if ( IdNew0 < 0x7FFFFFFF )
652 {
653 pCutNew->pArray[ k++ ] = IdNew0;
654 uHash |= Ivy_NodeCutHashValue( IdNew0 );
655 }
656 if ( IdNew1 < 0x7FFFFFFF )
657 {
658 pCutNew->pArray[ k++ ] = IdNew1;
659 uHash |= Ivy_NodeCutHashValue( IdNew1 );
660 }
661 pCutNew->nSize = k;
662 pCutNew->uHash = uHash;
663 assert( pCutNew->nSize <= pCut->nSizeMax );
664 // for ( i = 1; i < pCutNew->nSize; i++ )
665 // assert( pCutNew->pArray[i-1] < pCutNew->pArray[i] );
666 return 1;
667 }
668
669 /**Function*************************************************************
670
671 Synopsis [Check if the cut exists.]
672
673 Description [Returns 1 if the cut exists.]
674
675 SideEffects []
676
677 SeeAlso []
678
679 ***********************************************************************/
Ivy_NodeCutFindOrAdd(Ivy_Store_t * pCutStore,Ivy_Cut_t * pCutNew)680 int Ivy_NodeCutFindOrAdd( Ivy_Store_t * pCutStore, Ivy_Cut_t * pCutNew )
681 {
682 Ivy_Cut_t * pCut;
683 int i, k;
684 assert( pCutNew->uHash );
685 // try to find the cut
686 for ( i = 0; i < pCutStore->nCuts; i++ )
687 {
688 pCut = pCutStore->pCuts + i;
689 if ( pCut->uHash == pCutNew->uHash && pCut->nSize == pCutNew->nSize )
690 {
691 for ( k = 0; k < pCutNew->nSize; k++ )
692 if ( pCut->pArray[k] != pCutNew->pArray[k] )
693 break;
694 if ( k == pCutNew->nSize )
695 return 1;
696 }
697 }
698 assert( pCutStore->nCuts < pCutStore->nCutsMax );
699 // add the cut
700 pCut = pCutStore->pCuts + pCutStore->nCuts++;
701 *pCut = *pCutNew;
702 return 0;
703 }
704
705 /**Function*************************************************************
706
707 Synopsis [Returns 1 if pDom is contained in pCut.]
708
709 Description []
710
711 SideEffects []
712
713 SeeAlso []
714
715 ***********************************************************************/
Ivy_CutCheckDominance(Ivy_Cut_t * pDom,Ivy_Cut_t * pCut)716 static inline int Ivy_CutCheckDominance( Ivy_Cut_t * pDom, Ivy_Cut_t * pCut )
717 {
718 int i, k;
719 for ( i = 0; i < pDom->nSize; i++ )
720 {
721 for ( k = 0; k < pCut->nSize; k++ )
722 if ( pDom->pArray[i] == pCut->pArray[k] )
723 break;
724 if ( k == pCut->nSize ) // node i in pDom is not contained in pCut
725 return 0;
726 }
727 // every node in pDom is contained in pCut
728 return 1;
729 }
730
731 /**Function*************************************************************
732
733 Synopsis [Check if the cut exists.]
734
735 Description [Returns 1 if the cut exists.]
736
737 SideEffects []
738
739 SeeAlso []
740
741 ***********************************************************************/
Ivy_NodeCutFindOrAddFilter(Ivy_Store_t * pCutStore,Ivy_Cut_t * pCutNew)742 int Ivy_NodeCutFindOrAddFilter( Ivy_Store_t * pCutStore, Ivy_Cut_t * pCutNew )
743 {
744 Ivy_Cut_t * pCut;
745 int i, k;
746 assert( pCutNew->uHash );
747 // try to find the cut
748 for ( i = 0; i < pCutStore->nCuts; i++ )
749 {
750 pCut = pCutStore->pCuts + i;
751 if ( pCut->nSize == 0 )
752 continue;
753 if ( pCut->nSize == pCutNew->nSize )
754 {
755 if ( pCut->uHash == pCutNew->uHash )
756 {
757 for ( k = 0; k < pCutNew->nSize; k++ )
758 if ( pCut->pArray[k] != pCutNew->pArray[k] )
759 break;
760 if ( k == pCutNew->nSize )
761 return 1;
762 }
763 continue;
764 }
765 if ( pCut->nSize < pCutNew->nSize )
766 {
767 // skip the non-contained cuts
768 if ( (pCut->uHash & pCutNew->uHash) != pCut->uHash )
769 continue;
770 // check containment seriously
771 if ( Ivy_CutCheckDominance( pCut, pCutNew ) )
772 return 1;
773 continue;
774 }
775 // check potential containment of other cut
776
777 // skip the non-contained cuts
778 if ( (pCut->uHash & pCutNew->uHash) != pCutNew->uHash )
779 continue;
780 // check containment seriously
781 if ( Ivy_CutCheckDominance( pCutNew, pCut ) )
782 {
783 // remove the current cut
784 // --pCutStore->nCuts;
785 // for ( k = i; k < pCutStore->nCuts; k++ )
786 // pCutStore->pCuts[k] = pCutStore->pCuts[k+1];
787 // i--;
788 pCut->nSize = 0;
789 }
790 }
791 assert( pCutStore->nCuts < pCutStore->nCutsMax );
792 // add the cut
793 pCut = pCutStore->pCuts + pCutStore->nCuts++;
794 *pCut = *pCutNew;
795 return 0;
796 }
797
798 /**Function*************************************************************
799
800 Synopsis [Print the cut.]
801
802 Description []
803
804 SideEffects []
805
806 SeeAlso []
807
808 ***********************************************************************/
Ivy_NodeCompactCuts(Ivy_Store_t * pCutStore)809 void Ivy_NodeCompactCuts( Ivy_Store_t * pCutStore )
810 {
811 Ivy_Cut_t * pCut;
812 int i, k;
813 for ( i = k = 0; i < pCutStore->nCuts; i++ )
814 {
815 pCut = pCutStore->pCuts + i;
816 if ( pCut->nSize == 0 )
817 continue;
818 pCutStore->pCuts[k++] = *pCut;
819 }
820 pCutStore->nCuts = k;
821 }
822
823 /**Function*************************************************************
824
825 Synopsis [Print the cut.]
826
827 Description []
828
829 SideEffects []
830
831 SeeAlso []
832
833 ***********************************************************************/
Ivy_NodePrintCut(Ivy_Cut_t * pCut)834 void Ivy_NodePrintCut( Ivy_Cut_t * pCut )
835 {
836 int i;
837 assert( pCut->nSize > 0 );
838 printf( "%d : {", pCut->nSize );
839 for ( i = 0; i < pCut->nSize; i++ )
840 printf( " %d", pCut->pArray[i] );
841 printf( " }\n" );
842 }
843
844 /**Function*************************************************************
845
846 Synopsis []
847
848 Description []
849
850 SideEffects []
851
852 SeeAlso []
853
854 ***********************************************************************/
Ivy_NodePrintCuts(Ivy_Store_t * pCutStore)855 void Ivy_NodePrintCuts( Ivy_Store_t * pCutStore )
856 {
857 int i;
858 printf( "Node %d\n", pCutStore->pCuts[0].pArray[0] );
859 for ( i = 0; i < pCutStore->nCuts; i++ )
860 Ivy_NodePrintCut( pCutStore->pCuts + i );
861 }
862
863 /**Function*************************************************************
864
865 Synopsis []
866
867 Description []
868
869 SideEffects []
870
871 SeeAlso []
872
873 ***********************************************************************/
Ivy_ObjRealFanin(Ivy_Obj_t * pObj)874 static inline Ivy_Obj_t * Ivy_ObjRealFanin( Ivy_Obj_t * pObj )
875 {
876 if ( !Ivy_ObjIsBuf(pObj) )
877 return pObj;
878 return Ivy_ObjRealFanin( Ivy_ObjFanin0(pObj) );
879 }
880
881 /**Function*************************************************************
882
883 Synopsis []
884
885 Description []
886
887 SideEffects []
888
889 SeeAlso []
890
891 ***********************************************************************/
Ivy_NodeFindCutsAll(Ivy_Man_t * p,Ivy_Obj_t * pObj,int nLeaves)892 Ivy_Store_t * Ivy_NodeFindCutsAll( Ivy_Man_t * p, Ivy_Obj_t * pObj, int nLeaves )
893 {
894 static Ivy_Store_t CutStore, * pCutStore = &CutStore;
895 Ivy_Cut_t CutNew, * pCutNew = &CutNew, * pCut;
896 Ivy_Obj_t * pLeaf;
897 int i, k, iLeaf0, iLeaf1;
898
899 assert( nLeaves <= IVY_CUT_INPUT );
900
901 // start the structure
902 pCutStore->nCuts = 0;
903 pCutStore->nCutsMax = IVY_CUT_LIMIT;
904 // start the trivial cut
905 pCutNew->uHash = 0;
906 pCutNew->nSize = 1;
907 pCutNew->nSizeMax = nLeaves;
908 pCutNew->pArray[0] = pObj->Id;
909 Ivy_NodeCutHash( pCutNew );
910 // add the trivial cut
911 Ivy_NodeCutFindOrAdd( pCutStore, pCutNew );
912 assert( pCutStore->nCuts == 1 );
913
914 // explore the cuts
915 for ( i = 0; i < pCutStore->nCuts; i++ )
916 {
917 // expand this cut
918 pCut = pCutStore->pCuts + i;
919 if ( pCut->nSize == 0 )
920 continue;
921 for ( k = 0; k < pCut->nSize; k++ )
922 {
923 pLeaf = Ivy_ManObj( p, pCut->pArray[k] );
924 if ( Ivy_ObjIsCi(pLeaf) )
925 continue;
926 /*
927 *pCutNew = *pCut;
928 Ivy_NodeCutShrink( pCutNew, pLeaf->Id );
929 if ( !Ivy_NodeCutExtend( pCutNew, Ivy_ObjFaninId0(pLeaf) ) )
930 continue;
931 if ( Ivy_ObjIsNode(pLeaf) && !Ivy_NodeCutExtend( pCutNew, Ivy_ObjFaninId1(pLeaf) ) )
932 continue;
933 Ivy_NodeCutHash( pCutNew );
934 */
935 iLeaf0 = Ivy_ObjId( Ivy_ObjRealFanin(Ivy_ObjFanin0(pLeaf)) );
936 iLeaf1 = Ivy_ObjId( Ivy_ObjRealFanin(Ivy_ObjFanin1(pLeaf)) );
937 // if ( iLeaf0 == iLeaf1 ) // strange situation observed on Jan 18, 2007
938 // continue;
939 if ( !Ivy_NodeCutPrescreen( pCut, iLeaf0, iLeaf1 ) )
940 continue;
941 if ( iLeaf0 > iLeaf1 )
942 Ivy_NodeCutDeriveNew( pCut, pCutNew, pCut->pArray[k], iLeaf1, iLeaf0 );
943 else
944 Ivy_NodeCutDeriveNew( pCut, pCutNew, pCut->pArray[k], iLeaf0, iLeaf1 );
945 Ivy_NodeCutFindOrAddFilter( pCutStore, pCutNew );
946 if ( pCutStore->nCuts == IVY_CUT_LIMIT )
947 break;
948 }
949 if ( pCutStore->nCuts == IVY_CUT_LIMIT )
950 break;
951 }
952 Ivy_NodeCompactCuts( pCutStore );
953 // Ivy_NodePrintCuts( pCutStore );
954 return pCutStore;
955 }
956
957 /**Function*************************************************************
958
959 Synopsis []
960
961 Description []
962
963 SideEffects []
964
965 SeeAlso []
966
967 ***********************************************************************/
Ivy_ManTestCutsAll(Ivy_Man_t * p)968 void Ivy_ManTestCutsAll( Ivy_Man_t * p )
969 {
970 Ivy_Obj_t * pObj;
971 int i, nCutsCut, nCutsTotal, nNodeTotal, nNodeOver;
972 abctime clk = Abc_Clock();
973 nNodeTotal = nNodeOver = 0;
974 nCutsTotal = -Ivy_ManNodeNum(p);
975 Ivy_ManForEachObj( p, pObj, i )
976 {
977 if ( !Ivy_ObjIsNode(pObj) )
978 continue;
979 nCutsCut = Ivy_NodeFindCutsAll( p, pObj, 5 )->nCuts;
980 nCutsTotal += nCutsCut;
981 nNodeOver += (nCutsCut == IVY_CUT_LIMIT);
982 nNodeTotal++;
983 }
984 printf( "Total cuts = %6d. Trivial = %6d. Nodes = %6d. Satur = %6d. ",
985 nCutsTotal, Ivy_ManPiNum(p) + Ivy_ManNodeNum(p), nNodeTotal, nNodeOver );
986 ABC_PRT( "Time", Abc_Clock() - clk );
987 }
988
989 ////////////////////////////////////////////////////////////////////////
990 /// END OF FILE ///
991 ////////////////////////////////////////////////////////////////////////
992
993
994 ABC_NAMESPACE_IMPL_END
995
996