1 /**CFile****************************************************************
2 
3   FileName    [ivyMulti.c]
4 
5   SystemName  [ABC: Logic synthesis and verification system.]
6 
7   PackageName [And-Inverter Graph package.]
8 
9   Synopsis    [Constructing multi-input AND/EXOR gates.]
10 
11   Author      [Alan Mishchenko]
12 
13   Affiliation [UC Berkeley]
14 
15   Date        [Ver. 1.0. Started - May 11, 2006.]
16 
17   Revision    [$Id: ivyMulti.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 
30 #define IVY_EVAL_LIMIT    128
31 
32 typedef struct Ivy_Eva_t_ Ivy_Eva_t;
33 struct Ivy_Eva_t_
34 {
35     Ivy_Obj_t * pArg;     // the argument node
36     unsigned    Mask;     // the mask of covered nodes
37     int         Weight;   // the number of covered nodes
38 };
39 
40 static void Ivy_MultiPrint( Ivy_Man_t * p, Ivy_Eva_t * pEvals, int nLeaves, int nEvals );
41 static int Ivy_MultiCover( Ivy_Man_t * p, Ivy_Eva_t * pEvals, int nLeaves, int nEvals, int nLimit, Vec_Ptr_t * vSols );
42 
43 ////////////////////////////////////////////////////////////////////////
44 ///                     FUNCTION DEFINITIONS                         ///
45 ////////////////////////////////////////////////////////////////////////
46 
47 /**Function*************************************************************
48 
49   Synopsis    [Constructs a balanced tree while taking sharing into account.]
50 
51   Description [Returns 1 if the implementation exists.]
52 
53   SideEffects []
54 
55   SeeAlso     []
56 
57 ***********************************************************************/
Ivy_MultiPlus(Ivy_Man_t * p,Vec_Ptr_t * vLeaves,Vec_Ptr_t * vCone,Ivy_Type_t Type,int nLimit,Vec_Ptr_t * vSols)58 int Ivy_MultiPlus( Ivy_Man_t * p, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone, Ivy_Type_t Type, int nLimit, Vec_Ptr_t * vSols )
59 {
60     static Ivy_Eva_t pEvals[IVY_EVAL_LIMIT];
61     Ivy_Eva_t * pEval, * pFan0, * pFan1;
62     Ivy_Obj_t * pObj = NULL; // Suppress "might be used uninitialized"
63     Ivy_Obj_t * pTemp;
64     int nEvals, nEvalsOld, i, k, x, nLeaves;
65     unsigned uMaskAll;
66 
67     // consider special cases
68     nLeaves = Vec_PtrSize(vLeaves);
69     assert( nLeaves > 2 );
70     if ( nLeaves > 32 || nLeaves + Vec_PtrSize(vCone) > IVY_EVAL_LIMIT )
71         return 0;
72 //    if ( nLeaves == 1 )
73 //        return Vec_PtrEntry( vLeaves, 0 );
74 //    if ( nLeaves == 2 )
75 //        return Ivy_Oper( Vec_PtrEntry(vLeaves, 0), Vec_PtrEntry(vLeaves, 1), Type );
76 
77     // set the leaf entries
78     uMaskAll = ((1 << nLeaves) - 1);
79     nEvals = 0;
80     Vec_PtrForEachEntry( Ivy_Obj_t *, vLeaves, pObj, i )
81     {
82         pEval = pEvals + nEvals;
83         pEval->pArg   = pObj;
84         pEval->Mask   = (1 << nEvals);
85         pEval->Weight = 1;
86         // mark the leaf
87         Ivy_Regular(pObj)->TravId = nEvals;
88         nEvals++;
89     }
90 
91     // propagate masks through the cone
92     Vec_PtrForEachEntry( Ivy_Obj_t *, vCone, pObj, i )
93     {
94         pObj->TravId = nEvals + i;
95         if ( Ivy_ObjIsBuf(pObj) )
96             pEvals[pObj->TravId].Mask = pEvals[Ivy_ObjFanin0(pObj)->TravId].Mask;
97         else
98             pEvals[pObj->TravId].Mask = pEvals[Ivy_ObjFanin0(pObj)->TravId].Mask | pEvals[Ivy_ObjFanin1(pObj)->TravId].Mask;
99     }
100 
101     // set the internal entries
102     Vec_PtrForEachEntry( Ivy_Obj_t *, vCone, pObj, i )
103     {
104         if ( i == Vec_PtrSize(vCone) - 1 )
105             break;
106         // skip buffers
107         if ( Ivy_ObjIsBuf(pObj) )
108             continue;
109         // skip nodes without external fanout
110         if ( Ivy_ObjRefs(pObj) == 0 )
111             continue;
112         assert( !Ivy_IsComplement(pObj) );
113         pEval = pEvals + nEvals;
114         pEval->pArg   = pObj;
115         pEval->Mask   = pEvals[pObj->TravId].Mask;
116         pEval->Weight = Extra_WordCountOnes(pEval->Mask);
117         // mark the node
118         pObj->TravId = nEvals;
119         nEvals++;
120     }
121 
122     // find the available nodes
123     nEvalsOld = nEvals;
124     for ( i = 1; i < nEvals; i++ )
125     for ( k = 0; k < i; k++ )
126     {
127         pFan0 = pEvals + i;
128         pFan1 = pEvals + k;
129         pTemp = Ivy_TableLookup(p, Ivy_ObjCreateGhost(p, pFan0->pArg, pFan1->pArg, Type, IVY_INIT_NONE));
130         // skip nodes in the cone
131         if ( pTemp == NULL || pTemp->fMarkB )
132             continue;
133         // skip the leaves
134         for ( x = 0; x < nLeaves; x++ )
135             if ( pTemp == Ivy_Regular((Ivy_Obj_t *)vLeaves->pArray[x]) )
136                 break;
137         if ( x < nLeaves )
138             continue;
139         pEval = pEvals + nEvals;
140         pEval->pArg   = pTemp;
141         pEval->Mask   = pFan0->Mask | pFan1->Mask;
142         pEval->Weight = (pFan0->Mask & pFan1->Mask) ? Extra_WordCountOnes(pEval->Mask) : pFan0->Weight + pFan1->Weight;
143         // save the argument
144         pObj->TravId = nEvals;
145         nEvals++;
146         // quit if the number of entries exceeded the limit
147         if ( nEvals == IVY_EVAL_LIMIT )
148             goto Outside;
149         // quit if we found an acceptable implementation
150         if ( pEval->Mask == uMaskAll )
151             goto Outside;
152     }
153 Outside:
154 
155 //    Ivy_MultiPrint( pEvals, nLeaves, nEvals );
156     if ( !Ivy_MultiCover( p, pEvals, nLeaves, nEvals, nLimit, vSols ) )
157         return 0;
158     assert( Vec_PtrSize( vSols ) > 0 );
159     return 1;
160 }
161 
162 /**Function*************************************************************
163 
164   Synopsis    [Computes how many uncovered ones this one covers.]
165 
166   Description []
167 
168   SideEffects []
169 
170   SeeAlso     []
171 
172 ***********************************************************************/
Ivy_MultiPrint(Ivy_Man_t * p,Ivy_Eva_t * pEvals,int nLeaves,int nEvals)173 void Ivy_MultiPrint( Ivy_Man_t * p, Ivy_Eva_t * pEvals, int nLeaves, int nEvals )
174 {
175     Ivy_Eva_t * pEval;
176     int i, k;
177     for ( i = nLeaves; i < nEvals; i++ )
178     {
179         pEval = pEvals + i;
180         printf( "%2d  (id = %5d)  : |", i-nLeaves, Ivy_ObjId(pEval->pArg) );
181         for ( k = 0; k < nLeaves; k++ )
182         {
183             if ( pEval->Mask & (1 << k) )
184                 printf( "+" );
185             else
186                 printf( " " );
187         }
188         printf( "|  Lev = %d.\n", Ivy_ObjLevel(pEval->pArg) );
189     }
190 }
191 
192 /**Function*************************************************************
193 
194   Synopsis    [Computes how many uncovered ones this one covers.]
195 
196   Description []
197 
198   SideEffects []
199 
200   SeeAlso     []
201 
202 ***********************************************************************/
Ivy_MultiWeight(unsigned uMask,int nMaskOnes,unsigned uFound)203 static inline int Ivy_MultiWeight( unsigned uMask, int nMaskOnes, unsigned uFound )
204 {
205     assert( uMask & ~uFound );
206     if ( (uMask & uFound) == 0 )
207         return nMaskOnes;
208     return Extra_WordCountOnes( uMask & ~uFound );
209 }
210 
211 /**Function*************************************************************
212 
213   Synopsis    [Finds the cover.]
214 
215   Description [Returns 1 if the cover is found.]
216 
217   SideEffects []
218 
219   SeeAlso     []
220 
221 ***********************************************************************/
Ivy_MultiCover(Ivy_Man_t * p,Ivy_Eva_t * pEvals,int nLeaves,int nEvals,int nLimit,Vec_Ptr_t * vSols)222 int Ivy_MultiCover( Ivy_Man_t * p, Ivy_Eva_t * pEvals, int nLeaves, int nEvals, int nLimit, Vec_Ptr_t * vSols )
223 {
224     int fVerbose = 0;
225     Ivy_Eva_t * pEval;
226     Ivy_Eva_t * pEvalBest = NULL; // Suppress "might be used uninitialized"
227     unsigned uMaskAll, uFound, uTemp;
228     int i, k, BestK;
229     int WeightBest = -1; // Suppress "might be used uninitialized"
230     int WeightCur;
231     int LevelBest = -1; // Suppress "might be used uninitialized"
232     int LevelCur;
233     uMaskAll = (nLeaves == 32)? (~(unsigned)0) : ((1 << nLeaves) - 1);
234     uFound = 0;
235     // solve the covering problem
236     if ( fVerbose )
237     printf( "Solution:  " );
238     Vec_PtrClear( vSols );
239     for ( i = 0; i < nLimit; i++ )
240     {
241         BestK = -1;
242         for ( k = nEvals - 1; k >= 0; k-- )
243         {
244             pEval = pEvals + k;
245             if ( (pEval->Mask & ~uFound) == 0 )
246                 continue;
247             if ( BestK == -1 )
248             {
249                 BestK      = k;
250                 pEvalBest  = pEval;
251                 WeightBest = Ivy_MultiWeight( pEvalBest->Mask, pEvalBest->Weight, uFound );
252                 LevelBest  = Ivy_ObjLevel( Ivy_Regular(pEvalBest->pArg) );
253                 continue;
254             }
255             // compare BestK and the new one (k)
256             WeightCur = Ivy_MultiWeight( pEval->Mask, pEval->Weight, uFound );
257             LevelCur = Ivy_ObjLevel( Ivy_Regular(pEval->pArg) );
258             if ( WeightBest < WeightCur ||
259                 (WeightBest == WeightCur && LevelBest > LevelCur) )
260             {
261                 BestK      = k;
262                 pEvalBest  = pEval;
263                 WeightBest = WeightCur;
264                 LevelBest  = LevelCur;
265             }
266         }
267         assert( BestK != -1 );
268         // if the cost is only 1, take the leaf
269         if ( WeightBest == 1 && BestK >= nLeaves )
270         {
271             uTemp = (pEvalBest->Mask & ~uFound);
272             for ( k = 0; k < nLeaves; k++ )
273                 if ( uTemp & (1 << k) )
274                     break;
275             assert( k < nLeaves );
276             BestK     = k;
277             pEvalBest = pEvals + BestK;
278         }
279         if ( fVerbose )
280         {
281             if ( BestK < nLeaves )
282                 printf( "L(%d) ", BestK );
283             else
284                 printf( "%d ", BestK - nLeaves );
285         }
286         // update the found set
287         Vec_PtrPush( vSols, pEvalBest->pArg );
288         uFound |= pEvalBest->Mask;
289         if ( uFound == uMaskAll )
290             break;
291     }
292     if ( uFound == uMaskAll )
293     {
294         if ( fVerbose )
295             printf( "  Found \n\n" );
296         return 1;
297     }
298     else
299     {
300         if ( fVerbose )
301             printf( "  Not found \n\n" );
302         return 0;
303     }
304 }
305 
306 ////////////////////////////////////////////////////////////////////////
307 ///                       END OF FILE                                ///
308 ////////////////////////////////////////////////////////////////////////
309 
310 
311 ABC_NAMESPACE_IMPL_END
312 
313