1 /**CFile****************************************************************
2
3 FileName [acecTree.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [CEC for arithmetic circuits.]
8
9 Synopsis [Adder tree construction.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: acecTree.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "acecInt.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 ////////////////////////////////////////////////////////////////////////
31 /// FUNCTION DEFINITIONS ///
32 ////////////////////////////////////////////////////////////////////////
33
34 /**Function*************************************************************
35
36 Synopsis []
37
38 Description []
39
40 SideEffects []
41
42 SeeAlso []
43
44 ***********************************************************************/
Acec_BoxFree(Acec_Box_t * pBox)45 void Acec_BoxFree( Acec_Box_t * pBox )
46 {
47 Vec_WecFreeP( &pBox->vAdds );
48 Vec_WecFreeP( &pBox->vLeafLits );
49 Vec_WecFreeP( &pBox->vRootLits );
50 Vec_WecFreeP( &pBox->vUnique );
51 Vec_WecFreeP( &pBox->vShared );
52 ABC_FREE( pBox );
53 }
Acec_BoxFreeP(Acec_Box_t ** ppBox)54 void Acec_BoxFreeP( Acec_Box_t ** ppBox )
55 {
56 if ( *ppBox )
57 Acec_BoxFree( *ppBox );
58 *ppBox = NULL;
59 }
60
61 /**Function*************************************************************
62
63 Synopsis []
64
65 Description []
66
67 SideEffects []
68
69 SeeAlso []
70
71 ***********************************************************************/
Acec_VerifyBoxLeaves(Acec_Box_t * pBox,Vec_Bit_t * vIgnore)72 void Acec_VerifyBoxLeaves( Acec_Box_t * pBox, Vec_Bit_t * vIgnore )
73 {
74 Vec_Int_t * vLevel;
75 int i, k, iLit, Count = 0;
76 if ( vIgnore == NULL )
77 return;
78 Vec_WecForEachLevel( pBox->vLeafLits, vLevel, i )
79 Vec_IntForEachEntry( vLevel, iLit, k )
80 if ( Gia_ObjIsAnd(Gia_ManObj(pBox->pGia, Abc_Lit2Var(iLit))) && !Vec_BitEntry(vIgnore, Abc_Lit2Var(iLit)) )
81 printf( "Internal node %d of rank %d is not part of PPG.\n", Abc_Lit2Var(iLit), i ), Count++;
82 printf( "Detected %d suspicious leaves.\n", Count );
83 }
84
85 /**Function*************************************************************
86
87 Synopsis [Filters trees by removing TFO of roots.]
88
89 Description []
90
91 SideEffects []
92
93 SeeAlso []
94
95 ***********************************************************************/
Acec_TreeFilterOne(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Int_t * vTree)96 void Acec_TreeFilterOne( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vTree )
97 {
98 Vec_Bit_t * vIsRoot = Vec_BitStart( Gia_ManObjNum(p) );
99 Vec_Bit_t * vMarked = Vec_BitStart( Gia_ManObjNum(p) ) ;
100 Gia_Obj_t * pObj;
101 int i, k = 0, Box, Rank;
102 // mark roots
103 Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
104 {
105 Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+3), 1 );
106 Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+4), 1 );
107 }
108 Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
109 {
110 Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+0), 0 );
111 Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+1), 0 );
112 Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+2), 0 );
113 }
114 // iterate through nodes to detect TFO of roots
115 Gia_ManForEachAnd( p, pObj, i )
116 {
117 if ( Vec_BitEntry(vIsRoot, Gia_ObjFaninId0(pObj,i)) || Vec_BitEntry(vIsRoot, Gia_ObjFaninId1(pObj,i)) ||
118 Vec_BitEntry(vMarked, Gia_ObjFaninId0(pObj,i)) || Vec_BitEntry(vMarked, Gia_ObjFaninId1(pObj,i)) )
119 Vec_BitWriteEntry( vMarked, i, 1 );
120 }
121 // remove those that overlap with roots
122 Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
123 {
124 // special case of the first bit
125 // if ( i == 0 )
126 // continue;
127
128 /*
129 if ( Vec_IntEntry(vAdds, 6*Box+3) == 24 && Vec_IntEntry(vAdds, 6*Box+4) == 22 )
130 {
131 printf( "**** removing special one \n" );
132 continue;
133 }
134 if ( Vec_IntEntry(vAdds, 6*Box+3) == 48 && Vec_IntEntry(vAdds, 6*Box+4) == 49 )
135 {
136 printf( "**** removing special one \n" );
137 continue;
138 }
139 */
140 if ( Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+3)) || Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+4)) )
141 {
142 printf( "Removing box %d=(%d,%d) of rank %d.\n", Box, Vec_IntEntry(vAdds, 6*Box+3), Vec_IntEntry(vAdds, 6*Box+4), Rank );
143 continue;
144 }
145 Vec_IntWriteEntry( vTree, k++, Box );
146 Vec_IntWriteEntry( vTree, k++, Rank );
147 }
148 Vec_IntShrink( vTree, k );
149 Vec_BitFree( vIsRoot );
150 Vec_BitFree( vMarked );
151 }
Acec_TreeFilterTrees(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Wec_t * vTrees)152 void Acec_TreeFilterTrees( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vTrees )
153 {
154 Vec_Int_t * vLevel;
155 int i;
156 Vec_WecForEachLevel( vTrees, vLevel, i )
157 Acec_TreeFilterOne( p, vAdds, vLevel );
158 }
159
160 /**Function*************************************************************
161
162 Synopsis [Filters trees by removing TFO of roots.]
163
164 Description []
165
166 SideEffects []
167
168 SeeAlso []
169
170 ***********************************************************************/
Acec_TreeMarkTFI_rec(Gia_Man_t * p,int Id,Vec_Bit_t * vMarked)171 void Acec_TreeMarkTFI_rec( Gia_Man_t * p, int Id, Vec_Bit_t * vMarked )
172 {
173 Gia_Obj_t * pObj = Gia_ManObj(p, Id);
174 if ( Vec_BitEntry(vMarked, Id) )
175 return;
176 Vec_BitWriteEntry( vMarked, Id, 1 );
177 if ( !Gia_ObjIsAnd(pObj) )
178 return;
179 Acec_TreeMarkTFI_rec( p, Gia_ObjFaninId0(pObj, Id), vMarked );
180 Acec_TreeMarkTFI_rec( p, Gia_ObjFaninId1(pObj, Id), vMarked );
181 }
Acec_TreeFilterOne2(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Int_t * vTree)182 void Acec_TreeFilterOne2( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vTree )
183 {
184 Vec_Bit_t * vIsLeaf = Vec_BitStart( Gia_ManObjNum(p) );
185 Vec_Bit_t * vMarked = Vec_BitStart( Gia_ManObjNum(p) ) ;
186 Gia_Obj_t * pObj;
187 int i, k = 0, Box, Rank;
188 // mark leaves
189 Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
190 {
191 Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+0), 1 );
192 Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+1), 1 );
193 Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+2), 1 );
194 }
195 Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
196 {
197 Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+3), 0 );
198 Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+4), 0 );
199 }
200 // mark TFI of leaves
201 Gia_ManForEachAnd( p, pObj, i )
202 if ( Vec_BitEntry(vIsLeaf, i) )
203 Acec_TreeMarkTFI_rec( p, i, vMarked );
204 // additional one
205 //if ( 10942 < Gia_ManObjNum(p) )
206 // Acec_TreeMarkTFI_rec( p, 10942, vMarked );
207 // remove those that overlap with the marked TFI
208 Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
209 {
210 if ( Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+3)) || Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+4)) )
211 {
212 printf( "Removing box %d=(%d,%d) of rank %d.\n", Box, Vec_IntEntry(vAdds, 6*Box+3), Vec_IntEntry(vAdds, 6*Box+4), Rank );
213 continue;
214 }
215 Vec_IntWriteEntry( vTree, k++, Box );
216 Vec_IntWriteEntry( vTree, k++, Rank );
217 }
218 Vec_IntShrink( vTree, k );
219 Vec_BitFree( vIsLeaf );
220 Vec_BitFree( vMarked );
221 }
Acec_TreeFilterTrees2(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Wec_t * vTrees)222 void Acec_TreeFilterTrees2( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vTrees )
223 {
224 Vec_Int_t * vLevel;
225 int i;
226 Vec_WecForEachLevel( vTrees, vLevel, i )
227 Acec_TreeFilterOne2( p, vAdds, vLevel );
228 }
229
230 /**Function*************************************************************
231
232 Synopsis []
233
234 Description []
235
236 SideEffects []
237
238 SeeAlso []
239
240 ***********************************************************************/
Acec_TreeVerifyPhaseOne_rec(Gia_Man_t * p,Gia_Obj_t * pObj)241 int Acec_TreeVerifyPhaseOne_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
242 {
243 int Truth0, Truth1;
244 if ( Gia_ObjIsTravIdCurrent(p, pObj) )
245 return pObj->Value;
246 Gia_ObjSetTravIdCurrent(p, pObj);
247 assert( Gia_ObjIsAnd(pObj) );
248 assert( !Gia_ObjIsXor(pObj) );
249 Truth0 = Acec_TreeVerifyPhaseOne_rec( p, Gia_ObjFanin0(pObj) );
250 Truth1 = Acec_TreeVerifyPhaseOne_rec( p, Gia_ObjFanin1(pObj) );
251 Truth0 = Gia_ObjFaninC0(pObj) ? 0xFF & ~Truth0 : Truth0;
252 Truth1 = Gia_ObjFaninC1(pObj) ? 0xFF & ~Truth1 : Truth1;
253 return (pObj->Value = Truth0 & Truth1);
254 }
Acec_TreeVerifyPhaseOne(Gia_Man_t * p,Vec_Int_t * vAdds,int iBox)255 void Acec_TreeVerifyPhaseOne( Gia_Man_t * p, Vec_Int_t * vAdds, int iBox )
256 {
257 Gia_Obj_t * pObj;
258 unsigned TruthXor, TruthMaj, Truths[3] = { 0xAA, 0xCC, 0xF0 };
259 int k, iObj, fFadd = Vec_IntEntry(vAdds, 6*iBox+2) > 0;
260 int fFlip = !fFadd && Acec_SignBit2(vAdds, iBox, 2);
261
262 Gia_ManIncrementTravId( p );
263 for ( k = 0; k < 3; k++ )
264 {
265 iObj = Vec_IntEntry( vAdds, 6*iBox+k );
266 if ( iObj == 0 )
267 continue;
268 pObj = Gia_ManObj( p, iObj );
269 pObj->Value = (Acec_SignBit2(vAdds, iBox, k) ^ fFlip) ? 0xFF & ~Truths[k] : Truths[k];
270 Gia_ObjSetTravIdCurrent( p, pObj );
271 }
272
273 iObj = Vec_IntEntry( vAdds, 6*iBox+3 );
274 TruthXor = Acec_TreeVerifyPhaseOne_rec( p, Gia_ManObj(p, iObj) );
275 TruthXor = (Acec_SignBit2(vAdds, iBox, 3) ^ fFlip) ? 0xFF & ~TruthXor : TruthXor;
276
277 iObj = Vec_IntEntry( vAdds, 6*iBox+4 );
278 TruthMaj = Acec_TreeVerifyPhaseOne_rec( p, Gia_ManObj(p, iObj) );
279 TruthMaj = (Acec_SignBit2(vAdds, iBox, 4) ^ fFlip) ? 0xFF & ~TruthMaj : TruthMaj;
280
281 if ( fFadd ) // FADD
282 {
283 if ( TruthXor != 0x96 )
284 printf( "Fadd %d sum %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+3 ) );
285 if ( TruthMaj != 0xE8 )
286 printf( "Fadd %d carry %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+4 ) );
287 }
288 else
289 {
290 //printf( "Sign1 = %d%d%d %d\n", Acec_SignBit(vAdds, iBox, 0), Acec_SignBit(vAdds, iBox, 1), Acec_SignBit(vAdds, iBox, 2), Acec_SignBit(vAdds, iBox, 3) );
291 //printf( "Sign2 = %d%d%d %d%d\n", Acec_SignBit2(vAdds, iBox, 0), Acec_SignBit2(vAdds, iBox, 1), Acec_SignBit2(vAdds, iBox, 2), Acec_SignBit2(vAdds, iBox, 3), Acec_SignBit2(vAdds, iBox, 4) );
292 if ( TruthXor != 0x66 )
293 printf( "Hadd %d sum %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+3 ) );
294 if ( TruthMaj != 0x88 )
295 printf( "Hadd %d carry %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+4 ) );
296 }
297 }
Acec_TreeVerifyPhases(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Wec_t * vBoxes)298 void Acec_TreeVerifyPhases( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
299 {
300 Vec_Int_t * vLevel;
301 int i, k, Box;
302 Vec_WecForEachLevel( vBoxes, vLevel, i )
303 Vec_IntForEachEntry( vLevel, Box, k )
304 Acec_TreeVerifyPhaseOne( p, vAdds, Box );
305 }
Acec_TreeVerifyPhases2(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Wec_t * vBoxes)306 void Acec_TreeVerifyPhases2( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
307 {
308 Vec_Bit_t * vPhase = Vec_BitStart( Gia_ManObjNum(p) );
309 Vec_Bit_t * vRoots = Vec_BitStart( Gia_ManObjNum(p) );
310 Vec_Int_t * vLevel;
311 int i, k, n, Box;
312 // mark all output points and their values
313 Vec_WecForEachLevel( vBoxes, vLevel, i )
314 Vec_IntForEachEntry( vLevel, Box, k )
315 {
316 Vec_BitWriteEntry( vRoots, Vec_IntEntry( vAdds, 6*Box+3 ), 1 );
317 Vec_BitWriteEntry( vRoots, Vec_IntEntry( vAdds, 6*Box+4 ), 1 );
318 Vec_BitWriteEntry( vPhase, Vec_IntEntry( vAdds, 6*Box+3 ), Acec_SignBit2(vAdds, Box, 3) );
319 Vec_BitWriteEntry( vPhase, Vec_IntEntry( vAdds, 6*Box+4 ), Acec_SignBit2(vAdds, Box, 4) );
320 }
321 // compare with input points
322 Vec_WecForEachLevel( vBoxes, vLevel, i )
323 Vec_IntForEachEntry( vLevel, Box, k )
324 for ( n = 0; n < 3; n++ )
325 {
326 if ( !Vec_BitEntry(vRoots, Vec_IntEntry(vAdds, 6*Box+n)) )
327 continue;
328 if ( Vec_BitEntry(vPhase, Vec_IntEntry(vAdds, 6*Box+n)) == Acec_SignBit2(vAdds, Box, n) )
329 continue;
330 printf( "Phase of input %d=%d is mismatched in box %d=(%d,%d).\n",
331 n, Vec_IntEntry(vAdds, 6*Box+n), Box, Vec_IntEntry(vAdds, 6*Box+3), Vec_IntEntry(vAdds, 6*Box+4) );
332 }
333 Vec_BitFree( vPhase );
334 Vec_BitFree( vRoots );
335 }
Acec_TreeVerifyConnections(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Wec_t * vBoxes)336 void Acec_TreeVerifyConnections( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
337 {
338 Vec_Int_t * vCounts = Vec_IntStartFull( Gia_ManObjNum(p) );
339 Vec_Int_t * vLevel;
340 int i, k, n, Box;
341 // mark outputs
342 Vec_WecForEachLevel( vBoxes, vLevel, i )
343 Vec_IntForEachEntry( vLevel, Box, k )
344 {
345 Vec_IntWriteEntry( vCounts, Vec_IntEntry( vAdds, 6*Box+3 ), 0 );
346 Vec_IntWriteEntry( vCounts, Vec_IntEntry( vAdds, 6*Box+4 ), 0 );
347 }
348 // count fanouts
349 Vec_WecForEachLevel( vBoxes, vLevel, i )
350 Vec_IntForEachEntry( vLevel, Box, k )
351 for ( n = 0; n < 3; n++ )
352 if ( Vec_IntEntry( vCounts, Vec_IntEntry(vAdds, 6*Box+n) ) != -1 )
353 Vec_IntAddToEntry( vCounts, Vec_IntEntry(vAdds, 6*Box+n), 1 );
354 // print out
355 printf( "The adder tree has %d internal cut points. ", Vec_IntCountLarger(vCounts, -1) );
356 if ( Vec_IntCountLarger(vCounts, 1) == 0 )
357 printf( "There is no internal fanouts.\n" );
358 else
359 {
360 printf( "These %d points have more than one fanout:\n", Vec_IntCountLarger(vCounts, 1) );
361 Vec_IntForEachEntry( vCounts, Box, i )
362 if ( Box > 1 )
363 printf( "Node %d(lev %d) has fanout %d.\n", i, Gia_ObjLevelId(p, i), Box );
364 }
365 Vec_IntFree( vCounts );
366 }
367
368 /**Function*************************************************************
369
370 Synopsis [Creates polarity.]
371
372 Description []
373
374 SideEffects []
375
376 SeeAlso []
377
378 ***********************************************************************/
Acec_TreeCarryMap(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Wec_t * vBoxes)379 Vec_Int_t * Acec_TreeCarryMap( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
380 {
381 Vec_Int_t * vMap = Vec_IntStartFull( Gia_ManObjNum(p) );
382 Vec_Int_t * vLevel;
383 int i, k, Box;
384 Vec_WecForEachLevel( vBoxes, vLevel, i )
385 Vec_IntForEachEntry( vLevel, Box, k )
386 Vec_IntWriteEntry( vMap, Vec_IntEntry(vAdds, 6*Box+4), Box );
387 return vMap;
388 }
Acec_TreePhases_rec(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Int_t * vMap,int Node,int fPhase,Vec_Bit_t * vVisit)389 void Acec_TreePhases_rec( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vMap, int Node, int fPhase, Vec_Bit_t * vVisit )
390 {
391 int k, iBox, iXor, fXorPhase, fPhaseThis;
392 assert( Node != 0 );
393 iBox = Vec_IntEntry( vMap, Node );
394 if ( iBox == -1 )
395 return;
396 assert( Node == Vec_IntEntry( vAdds, 6*iBox+4 ) );
397 if ( Vec_BitEntry(vVisit, iBox) )
398 return;
399 Vec_BitWriteEntry( vVisit, iBox, 1 );
400 iXor = Vec_IntEntry( vAdds, 6*iBox+3 );
401 fXorPhase = Acec_SignBit(vAdds, iBox, 3);
402 if ( Vec_IntEntry(vAdds, 6*iBox+2) == 0 )
403 {
404 //fPhaseThis = Acec_SignBit( vAdds, iBox, 2 ) ^ fPhase;
405 //fXorPhase ^= fPhaseThis;
406 //Acec_SignSetBit2( vAdds, iBox, 2, fPhaseThis ); // complemented HADD -- create const1 input
407 fPhase ^= Acec_SignBit( vAdds, iBox, 2 );
408 fXorPhase ^= fPhase;
409 Acec_SignSetBit2( vAdds, iBox, 2, fPhase ); // complemented HADD -- create const1 input
410 }
411 for ( k = 0; k < 3; k++ )
412 {
413 int iObj = Vec_IntEntry( vAdds, 6*iBox+k );
414 if ( iObj == 0 )
415 continue;
416 fPhaseThis = Acec_SignBit(vAdds, iBox, k) ^ fPhase;
417 fXorPhase ^= fPhaseThis;
418 Acec_TreePhases_rec( p, vAdds, vMap, iObj, fPhaseThis, vVisit );
419 Acec_SignSetBit2( vAdds, iBox, k, fPhaseThis );
420 }
421 Acec_SignSetBit2( vAdds, iBox, 3, fXorPhase );
422 Acec_SignSetBit2( vAdds, iBox, 4, fPhase );
423 }
424
425 /**Function*************************************************************
426
427 Synopsis [Find internal cut points with exactly one adder fanin/fanout.]
428
429 Description [Returns a map of point into its input/output adder.]
430
431 SideEffects []
432
433 SeeAlso []
434
435 ***********************************************************************/
Acec_TreeAddInOutPoint(Vec_Int_t * vMap,int iObj,int iAdd,int fOut)436 void Acec_TreeAddInOutPoint( Vec_Int_t * vMap, int iObj, int iAdd, int fOut )
437 {
438 int * pPlace = Vec_IntEntryP( vMap, Abc_Var2Lit(iObj, fOut) );
439 if ( *pPlace == -1 )
440 *pPlace = iAdd;
441 else if ( *pPlace >= 0 )
442 *pPlace = -2;
443 }
Acec_TreeFindPoints(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Bit_t * vIgnore)444 Vec_Int_t * Acec_TreeFindPoints( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Bit_t * vIgnore )
445 {
446 Vec_Int_t * vMap = Vec_IntStartFull( 2*Gia_ManObjNum(p) );
447 int i;
448 for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ )
449 {
450 if ( vIgnore && (Vec_BitEntry(vIgnore, Vec_IntEntry(vAdds, 6*i+3)) || Vec_BitEntry(vIgnore, Vec_IntEntry(vAdds, 6*i+4))) )
451 continue;
452 Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+0), i, 0 );
453 Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+1), i, 0 );
454 Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+2), i, 0 );
455 Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+3), i, 1 );
456 Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+4), i, 1 );
457 }
458 return vMap;
459 }
460
461 /**Function*************************************************************
462
463 Synopsis [Find adder trees as groups of adders connected vis cut-points.]
464
465 Description []
466
467 SideEffects []
468
469 SeeAlso []
470
471 ***********************************************************************/
Acec_TreeWhichPoint(Vec_Int_t * vAdds,int iAdd,int iObj)472 int Acec_TreeWhichPoint( Vec_Int_t * vAdds, int iAdd, int iObj )
473 {
474 int k;
475 for ( k = 0; k < 5; k++ )
476 if ( Vec_IntEntry(vAdds, 6*iAdd+k) == iObj )
477 return k;
478 assert( 0 );
479 return -1;
480 }
Acec_TreeFindTrees2_rec(Vec_Int_t * vAdds,Vec_Int_t * vMap,int iAdd,int Rank,Vec_Int_t * vTree,Vec_Bit_t * vFound)481 void Acec_TreeFindTrees2_rec( Vec_Int_t * vAdds, Vec_Int_t * vMap, int iAdd, int Rank, Vec_Int_t * vTree, Vec_Bit_t * vFound )
482 {
483 extern void Acec_TreeFindTrees_rec( Vec_Int_t * vAdds, Vec_Int_t * vMap, int iObj, int Rank, Vec_Int_t * vTree, Vec_Bit_t * vFound );
484 int k;
485 if ( Vec_BitEntry(vFound, iAdd) )
486 return;
487 Vec_BitWriteEntry( vFound, iAdd, 1 );
488 Vec_IntPush( vTree, iAdd );
489 Vec_IntPush( vTree, Rank );
490 //printf( "Assigning rank %d to (%d:%d).\n", Rank, Vec_IntEntry(vAdds, 6*iAdd+3), Vec_IntEntry(vAdds, 6*iAdd+4) );
491 for ( k = 0; k < 5; k++ )
492 Acec_TreeFindTrees_rec( vAdds, vMap, Vec_IntEntry(vAdds, 6*iAdd+k), k == 4 ? Rank + 1 : Rank, vTree, vFound );
493 }
Acec_TreeFindTrees_rec(Vec_Int_t * vAdds,Vec_Int_t * vMap,int iObj,int Rank,Vec_Int_t * vTree,Vec_Bit_t * vFound)494 void Acec_TreeFindTrees_rec( Vec_Int_t * vAdds, Vec_Int_t * vMap, int iObj, int Rank, Vec_Int_t * vTree, Vec_Bit_t * vFound )
495 {
496 int In = Vec_IntEntry( vMap, Abc_Var2Lit(iObj, 1) );
497 int Out = Vec_IntEntry( vMap, Abc_Var2Lit(iObj, 0) );
498 if ( In < 0 || Out < 0 )
499 return;
500 Acec_TreeFindTrees2_rec( vAdds, vMap, In, Acec_TreeWhichPoint(vAdds, In, iObj) == 4 ? Rank-1 : Rank, vTree, vFound );
501 Acec_TreeFindTrees2_rec( vAdds, vMap, Out, Rank, vTree, vFound );
502 }
Acec_TreeFindTrees(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Bit_t * vIgnore,int fFilterIn,int fFilterOut)503 Vec_Wec_t * Acec_TreeFindTrees( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Bit_t * vIgnore, int fFilterIn, int fFilterOut )
504 {
505 Vec_Wec_t * vTrees = Vec_WecAlloc( 10 );
506 Vec_Int_t * vMap = Acec_TreeFindPoints( p, vAdds, vIgnore );
507 Vec_Bit_t * vFound = Vec_BitStart( Vec_IntSize(vAdds)/6 );
508 Vec_Int_t * vTree;
509 int i, k, In, Out, Box, Rank, MinRank;
510 // go through the cut-points
511 Vec_IntForEachEntryDouble( vMap, In, Out, i )
512 {
513 if ( In < 0 || Out < 0 )
514 continue;
515 assert( Vec_BitEntry(vFound, In) == Vec_BitEntry(vFound, Out) );
516 if ( Vec_BitEntry(vFound, In) )
517 continue;
518 vTree = Vec_WecPushLevel( vTrees );
519 Acec_TreeFindTrees_rec( vAdds, vMap, i/2, 0, vTree, vFound );
520 // normalize rank
521 MinRank = ABC_INFINITY;
522 Vec_IntForEachEntryDouble( vTree, Box, Rank, k )
523 MinRank = Abc_MinInt( MinRank, Rank );
524 Vec_IntForEachEntryDouble( vTree, Box, Rank, k )
525 Vec_IntWriteEntry( vTree, k+1, Rank - MinRank );
526 }
527 Vec_BitFree( vFound );
528 Vec_IntFree( vMap );
529 // filter trees
530 if ( fFilterIn )
531 Acec_TreeFilterTrees2( p, vAdds, vTrees );
532 else if ( fFilterOut )
533 Acec_TreeFilterTrees( p, vAdds, vTrees );
534 // sort by size
535 Vec_WecSort( vTrees, 1 );
536 return vTrees;
537 }
Acec_TreeFindTreesTest(Gia_Man_t * p)538 void Acec_TreeFindTreesTest( Gia_Man_t * p )
539 {
540 Vec_Wec_t * vTrees;
541
542 abctime clk = Abc_Clock();
543 Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, 1 );
544 int nFadds = Ree_ManCountFadds( vAdds );
545 printf( "Detected %d adders (%d FAs and %d HAs). ", Vec_IntSize(vAdds)/6, nFadds, Vec_IntSize(vAdds)/6-nFadds );
546 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
547
548 clk = Abc_Clock();
549 vTrees = Acec_TreeFindTrees( p, vAdds, NULL, 0, 0 );
550 printf( "Collected %d trees with %d adders in them. ", Vec_WecSize(vTrees), Vec_WecSizeSize(vTrees)/2 );
551 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
552 Vec_WecPrint( vTrees, 0 );
553
554 Vec_WecFree( vTrees );
555 Vec_IntFree( vAdds );
556 }
557
558
559 /**Function*************************************************************
560
561 Synopsis [Derives one adder tree.]
562
563 Description []
564
565 SideEffects []
566
567 SeeAlso []
568 `
569 ***********************************************************************/
Acec_PrintAdders(Vec_Wec_t * vBoxes,Vec_Int_t * vAdds)570 void Acec_PrintAdders( Vec_Wec_t * vBoxes, Vec_Int_t * vAdds )
571 {
572 Vec_Int_t * vLevel;
573 int i, k, iBox;
574 Vec_WecForEachLevel( vBoxes, vLevel, i )
575 {
576 printf( " %4d : %2d {", i, Vec_IntSize(vLevel) );
577 Vec_IntForEachEntry( vLevel, iBox, k )
578 {
579 printf( " %s%d=(%d,%d)", Vec_IntEntry(vAdds, 6*iBox+2) == 0 ? "*":"", iBox,
580 Vec_IntEntry(vAdds, 6*iBox+3), Vec_IntEntry(vAdds, 6*iBox+4) );
581 //printf( "(%d,%d,%d)", Vec_IntEntry(vAdds, 6*iBox+0), Vec_IntEntry(vAdds, 6*iBox+1), Vec_IntEntry(vAdds, 6*iBox+2) );
582 }
583 printf( " }\n" );
584 }
585 }
Acec_TreePrintBox(Acec_Box_t * pBox,Vec_Int_t * vAdds)586 void Acec_TreePrintBox( Acec_Box_t * pBox, Vec_Int_t * vAdds )
587 {
588 printf( "Adders:\n" );
589 Acec_PrintAdders( pBox->vAdds, vAdds );
590 printf( "Inputs:\n" );
591 Vec_WecPrintLits( pBox->vLeafLits );
592 printf( "Outputs:\n" );
593 Vec_WecPrintLits( pBox->vRootLits );
594 // printf( "Node %d has level %d.\n", 3715, Gia_ObjLevelId(pBox->pGia, 3715) );
595 // printf( "Node %d has level %d.\n", 167, Gia_ObjLevelId(pBox->pGia, 167) );
596 // printf( "Node %d has level %d.\n", 278, Gia_ObjLevelId(pBox->pGia, 278) );
597 // printf( "Node %d has level %d.\n", 597, Gia_ObjLevelId(pBox->pGia, 597) );
598 }
599
Acec_CreateBoxMaxRank(Vec_Int_t * vTree)600 int Acec_CreateBoxMaxRank( Vec_Int_t * vTree )
601 {
602 int k, Box, Rank, MaxRank = 0;
603 Vec_IntForEachEntryDouble( vTree, Box, Rank, k )
604 MaxRank = Abc_MaxInt( MaxRank, Rank );
605 return MaxRank;
606 }
Acec_CreateBox(Gia_Man_t * p,Vec_Int_t * vAdds,Vec_Int_t * vTree)607 Acec_Box_t * Acec_CreateBox( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vTree )
608 {
609 int MaxRank = Acec_CreateBoxMaxRank(vTree);
610 Vec_Bit_t * vVisit = Vec_BitStart( Vec_IntSize(vAdds)/6 );
611 Vec_Bit_t * vIsLeaf = Vec_BitStart( Gia_ManObjNum(p) );
612 Vec_Bit_t * vIsRoot = Vec_BitStart( Gia_ManObjNum(p) );
613 Vec_Int_t * vLevel, * vMap;
614 int i, j, k, Box, Rank;//, Count = 0;
615
616 Acec_Box_t * pBox = ABC_CALLOC( Acec_Box_t, 1 );
617 pBox->pGia = p;
618 pBox->vAdds = Vec_WecStart( MaxRank + 1 );
619 pBox->vLeafLits = Vec_WecStart( MaxRank + 1 );
620 pBox->vRootLits = Vec_WecStart( MaxRank + 2 );
621
622 // collect boxes; mark inputs/outputs
623 Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
624 {
625 // if ( 37 == Box && 6 == Rank )
626 // {
627 // printf( "Skipping one adder...\n" );
628 // continue;
629 // }
630 Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+0), 1 );
631 Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+1), 1 );
632 Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+2), 1 );
633 Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+3), 1 );
634 Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+4), 1 );
635 Vec_WecPush( pBox->vAdds, Rank, Box );
636 }
637 // sort each level
638 Vec_WecForEachLevel( pBox->vAdds, vLevel, i )
639 Vec_IntSort( vLevel, 0 );
640
641 // set phases starting from roots
642 vMap = Acec_TreeCarryMap( p, vAdds, pBox->vAdds );
643 Vec_WecForEachLevelReverse( pBox->vAdds, vLevel, i )
644 Vec_IntForEachEntry( vLevel, Box, k )
645 if ( !Vec_BitEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+4) ) )
646 {
647 //printf( "Pushing phase of output %d of box %d\n", Vec_IntEntry(vAdds, 6*Box+4), Box );
648 Acec_TreePhases_rec( p, vAdds, vMap, Vec_IntEntry(vAdds, 6*Box+4), Vec_IntEntry(vAdds, 6*Box+2) != 0, vVisit );
649 }
650 Acec_TreeVerifyPhases( p, vAdds, pBox->vAdds );
651 Acec_TreeVerifyPhases2( p, vAdds, pBox->vAdds );
652 Vec_BitFree( vVisit );
653 Vec_IntFree( vMap );
654
655 // collect inputs/outputs
656 Vec_BitWriteEntry( vIsRoot, 0, 1 );
657 Vec_WecForEachLevel( pBox->vAdds, vLevel, i )
658 Vec_IntForEachEntry( vLevel, Box, j )
659 {
660 for ( k = 0; k < 3; k++ )
661 if ( !Vec_BitEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+k) ) )
662 Vec_WecPush( pBox->vLeafLits, i, Abc_Var2Lit(Vec_IntEntry(vAdds, 6*Box+k), Acec_SignBit2(vAdds, Box, k)) );
663 for ( k = 3; k < 5; k++ )
664 if ( !Vec_BitEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+k) ) )
665 {
666 //if ( Vec_IntEntry(vAdds, 6*Box+k) == 10942 )
667 //{
668 // printf( "++++++++++++ Skipping special\n" );
669 // continue;
670 //}
671 Vec_WecPush( pBox->vRootLits, k == 4 ? i + 1 : i, Abc_Var2Lit(Vec_IntEntry(vAdds, 6*Box+k), Acec_SignBit2(vAdds, Box, k)) );
672 }
673 if ( Vec_IntEntry(vAdds, 6*Box+2) == 0 && Acec_SignBit2(vAdds, Box, 2) )
674 Vec_WecPush( pBox->vLeafLits, i, 1 );
675 }
676 Vec_BitFree( vIsLeaf );
677 Vec_BitFree( vIsRoot );
678 // sort each level
679 Vec_WecForEachLevel( pBox->vLeafLits, vLevel, i )
680 Vec_IntSort( vLevel, 0 );
681 Vec_WecForEachLevel( pBox->vRootLits, vLevel, i )
682 Vec_IntSort( vLevel, 1 );
683 //return pBox;
684 /*
685 // push literals forward
686 //Vec_WecPrint( pBox->vLeafLits, 0 );
687 Vec_WecForEachLevel( pBox->vLeafLits, vLevel, i )
688 {
689 int This, Prev = Vec_IntEntry(vLevel, 0);
690 Vec_IntForEachEntryStart( vLevel, This, j, 1 )
691 {
692 if ( Prev != This )
693 {
694 Prev = This;
695 continue;
696 }
697 if ( i+1 >= Vec_WecSize(pBox->vLeafLits) )
698 continue;
699 Vec_IntPushOrder( Vec_WecEntry(pBox->vLeafLits, i+1), This );
700 Vec_IntDrop( vLevel, j-- );
701 Vec_IntDrop( vLevel, j-- );
702 Prev = -1;
703 Count++;
704 }
705 }
706 printf( "Pushed forward %d input literals.\n", Count );
707 */
708 //Vec_WecPrint( pBox->vLeafLits, 0 );
709 return pBox;
710 }
Acec_CreateBoxTest(Gia_Man_t * p)711 void Acec_CreateBoxTest( Gia_Man_t * p )
712 {
713 Acec_Box_t * pBox;
714 Vec_Wec_t * vTrees;
715 Vec_Int_t * vTree;
716
717 abctime clk = Abc_Clock();
718 Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, 1 );
719 int i, nFadds = Ree_ManCountFadds( vAdds );
720 printf( "Detected %d adders (%d FAs and %d HAs). ", Vec_IntSize(vAdds)/6, nFadds, Vec_IntSize(vAdds)/6-nFadds );
721 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
722
723 clk = Abc_Clock();
724 vTrees = Acec_TreeFindTrees( p, vAdds, NULL, 0, 0 );
725 printf( "Collected %d trees with %d adders in them. ", Vec_WecSize(vTrees), Vec_WecSizeSize(vTrees)/2 );
726 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
727 //Vec_WecPrint( vTrees, 0 );
728
729 Vec_WecForEachLevel( vTrees, vTree, i )
730 {
731 pBox = Acec_CreateBox( p, vAdds, Vec_WecEntry(vTrees, i) );
732 printf( "Processing tree %d: Ranks = %d. Adders = %d. Leaves = %d. Roots = %d.\n",
733 i, Vec_WecSize(pBox->vAdds), Vec_WecSizeSize(pBox->vAdds),
734 Vec_WecSizeSize(pBox->vLeafLits), Vec_WecSizeSize(pBox->vRootLits) );
735 Acec_TreePrintBox( pBox, vAdds );
736 Acec_BoxFreeP( &pBox );
737 }
738
739 Vec_WecFree( vTrees );
740 Vec_IntFree( vAdds );
741 }
742
743 /**Function*************************************************************
744
745 Synopsis []
746
747 Description []
748
749 SideEffects []
750
751 SeeAlso []
752
753 ***********************************************************************/
Acec_DeriveBox(Gia_Man_t * p,Vec_Bit_t * vIgnore,int fFilterIn,int fFilterOut,int fVerbose)754 Acec_Box_t * Acec_DeriveBox( Gia_Man_t * p, Vec_Bit_t * vIgnore, int fFilterIn, int fFilterOut, int fVerbose )
755 {
756 Acec_Box_t * pBox = NULL;
757 Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, fVerbose );
758 Vec_Wec_t * vTrees = Acec_TreeFindTrees( p, vAdds, vIgnore, fFilterIn, fFilterOut );
759 if ( vTrees && Vec_WecSize(vTrees) > 0 )
760 {
761 pBox = Acec_CreateBox( p, vAdds, Vec_WecEntry(vTrees, 0) );
762 Acec_VerifyBoxLeaves( pBox, vIgnore );
763 }
764 if ( pBox )//&& fVerbose )
765 printf( "Processing tree %d: Ranks = %d. Adders = %d. Leaves = %d. Roots = %d.\n",
766 0, Vec_WecSize(pBox->vAdds), Vec_WecSizeSize(pBox->vAdds),
767 Vec_WecSizeSize(pBox->vLeafLits), Vec_WecSizeSize(pBox->vRootLits) );
768 if ( pBox && fVerbose )
769 Acec_TreePrintBox( pBox, vAdds );
770 //Acec_PrintAdders( pBox0->vAdds, vAdds );
771 //Acec_MultDetectInputs( p, pBox->vLeafLits, pBox->vRootLits );
772 Vec_WecFreeP( &vTrees );
773 Vec_IntFree( vAdds );
774 return pBox;
775 }
776
777 ////////////////////////////////////////////////////////////////////////
778 /// END OF FILE ///
779 ////////////////////////////////////////////////////////////////////////
780
781
782 ABC_NAMESPACE_IMPL_END
783
784