1 /**CFile****************************************************************
2 
3   FileName    [wlcUif.c]
4 
5   SystemName  [ABC: Logic synthesis and verification system.]
6 
7   PackageName [Verilog parser.]
8 
9   Synopsis    [Abstraction for word-level networks.]
10 
11   Author      [Alan Mishchenko]
12 
13   Affiliation [UC Berkeley]
14 
15   Date        [Ver. 1.0. Started - August 22, 2014.]
16 
17   Revision    [$Id: wlcUif.c,v 1.00 2014/09/12 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "wlc.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 ////////////////////////////////////////////////////////////////////////
26 ///                        DECLARATIONS                              ///
27 ////////////////////////////////////////////////////////////////////////
28 
29 ////////////////////////////////////////////////////////////////////////
30 ///                     FUNCTION DEFINITIONS                         ///
31 ////////////////////////////////////////////////////////////////////////
32 
33 /**Function*************************************************************
34 
35   Synopsis    [Collect adds and mults.]
36 
37   Description []
38 
39   SideEffects []
40 
41   SeeAlso     []
42 
43 ***********************************************************************/
Wlc_NtkCollectBoxes(Wlc_Ntk_t * p,Vec_Int_t * vBoxIds)44 void Wlc_NtkCollectBoxes( Wlc_Ntk_t * p, Vec_Int_t * vBoxIds )
45 {
46     int i, iObj;
47     Vec_Int_t * vBoxes = Vec_IntAlloc( Vec_IntSize(vBoxIds) + 1 );
48     Vec_IntPush( vBoxes, Vec_IntSize(vBoxIds) );
49     Vec_IntForEachEntry( vBoxIds, iObj, i )
50         Vec_IntPush( vBoxes, Wlc_ObjNameId(p, iObj) );
51     Abc_FrameSetBoxes( Vec_IntReleaseArray(vBoxes) );
52     Vec_IntFree( vBoxes );
53 }
Wlc_NtkCollectAddMult(Wlc_Ntk_t * p,Wlc_BstPar_t * pPar,int * pCountA,int * pCountM)54 Vec_Int_t * Wlc_NtkCollectAddMult( Wlc_Ntk_t * p, Wlc_BstPar_t * pPar, int * pCountA, int * pCountM )
55 {
56     Vec_Int_t * vBoxIds;
57     Wlc_Obj_t * pObj;  int i;
58     *pCountA = *pCountM = 0;
59     if ( pPar->nAdderLimit == 0 && pPar->nMultLimit == 0 )
60         return NULL;
61     vBoxIds = Vec_IntAlloc( 100 );
62     Wlc_NtkForEachObj( p, pObj, i )
63     {
64         if ( pObj->Type == WLC_OBJ_ARI_ADD && pPar->nAdderLimit && Wlc_ObjRange(pObj) >= pPar->nAdderLimit )
65             Vec_IntPush( vBoxIds, i ), (*pCountA)++;
66         else if ( pObj->Type == WLC_OBJ_ARI_MULTI && pPar->nMultLimit && Wlc_ObjRange(pObj) >= pPar->nMultLimit )
67             Vec_IntPush( vBoxIds, i ), (*pCountM)++;
68     }
69     if ( Vec_IntSize( vBoxIds ) > 0 )
70     {
71         Wlc_NtkCollectBoxes( p, vBoxIds );
72         return vBoxIds;
73     }
74     Vec_IntFree( vBoxIds );
75     return NULL;
76 }
77 
78 /**Function*************************************************************
79 
80   Synopsis    [Check if two objects have the same input/output signatures.]
81 
82   Description []
83 
84   SideEffects []
85 
86   SeeAlso     []
87 
88 ***********************************************************************/
Wlc_NtkPairIsUifable(Wlc_Ntk_t * p,Wlc_Obj_t * pObj,Wlc_Obj_t * pObj2)89 int Wlc_NtkPairIsUifable( Wlc_Ntk_t * p, Wlc_Obj_t * pObj, Wlc_Obj_t * pObj2 )
90 {
91     Wlc_Obj_t * pFanin, * pFanin2;  int k;
92     if ( Wlc_ObjRange(pObj) != Wlc_ObjRange(pObj2) )
93         return 0;
94     if ( Wlc_ObjIsSigned(pObj) != Wlc_ObjIsSigned(pObj2) )
95         return 0;
96     if ( Wlc_ObjFaninNum(pObj) != Wlc_ObjFaninNum(pObj2) )
97         return 0;
98     for ( k = 0; k < Wlc_ObjFaninNum(pObj); k++ )
99     {
100         pFanin = Wlc_ObjFanin(p, pObj, k);
101         pFanin2 = Wlc_ObjFanin(p, pObj2, k);
102         if ( Wlc_ObjRange(pFanin) != Wlc_ObjRange(pFanin2) )
103             return 0;
104         if ( Wlc_ObjIsSigned(pFanin) != Wlc_ObjIsSigned(pFanin2) )
105             return 0;
106     }
107     return 1;
108 }
109 
110 /**Function*************************************************************
111 
112   Synopsis    [Collect IDs of the multipliers.]
113 
114   Description []
115 
116   SideEffects []
117 
118   SeeAlso     []
119 
120 ***********************************************************************/
Wlc_NtkCollectMultipliers(Wlc_Ntk_t * p)121 Vec_Int_t * Wlc_NtkCollectMultipliers( Wlc_Ntk_t * p )
122 {
123     Wlc_Obj_t * pObj;  int i;
124     Vec_Int_t * vBoxIds = Vec_IntAlloc( 100 );
125     Wlc_NtkForEachObj( p, pObj, i )
126         if ( pObj->Type == WLC_OBJ_ARI_MULTI )
127             Vec_IntPush( vBoxIds, i );
128     if ( Vec_IntSize( vBoxIds ) > 0 )
129         return vBoxIds;
130     Vec_IntFree( vBoxIds );
131     return NULL;
132 }
133 
134 /**Function*************************************************************
135 
136   Synopsis    [Returns all pairs of uifable multipliers.]
137 
138   Description []
139 
140   SideEffects []
141 
142   SeeAlso     []
143 
144 ***********************************************************************/
Wlc_NtkFindUifableMultiplierPairs(Wlc_Ntk_t * p)145 Vec_Int_t * Wlc_NtkFindUifableMultiplierPairs( Wlc_Ntk_t * p )
146 {
147     Vec_Int_t * vMultis = Wlc_NtkCollectMultipliers( p );
148     Vec_Int_t * vPairs = Vec_IntAlloc( 2 );
149     Wlc_Obj_t * pObj, * pObj2;  int i, k;
150     // iterate through unique pairs
151     Wlc_NtkForEachObjVec( vMultis, p, pObj, i )
152         Wlc_NtkForEachObjVec( vMultis, p, pObj2, k )
153         {
154             if ( k == i )
155                 break;
156             if ( Wlc_NtkPairIsUifable( p, pObj, pObj2 ) )
157             {
158                 Vec_IntPush( vPairs, Wlc_ObjId(p, pObj) );
159                 Vec_IntPush( vPairs, Wlc_ObjId(p, pObj2) );
160             }
161         }
162     Vec_IntFree( vMultis );
163     if ( Vec_IntSize( vPairs ) > 0 )
164         return vPairs;
165     Vec_IntFree( vPairs );
166     return NULL;
167 }
168 
169 
170 
171 /**Function*************************************************************
172 
173   Synopsis    [Abstracts nodes by replacing their outputs with new PIs.]
174 
175   Description [If array is NULL, abstract all multipliers.]
176 
177   SideEffects []
178 
179   SeeAlso     []
180 
181 ***********************************************************************/
Wlc_NtkAbstractNodes(Wlc_Ntk_t * p,Vec_Int_t * vNodesInit)182 Wlc_Ntk_t * Wlc_NtkAbstractNodes( Wlc_Ntk_t * p, Vec_Int_t * vNodesInit )
183 {
184     Vec_Int_t * vNodes = vNodesInit;
185     Wlc_Ntk_t * pNew;
186     Wlc_Obj_t * pObj;
187     int i, k, iObj, iFanin;
188     // get multipliers if not given
189     if ( vNodes == NULL )
190         vNodes = Wlc_NtkCollectMultipliers( p );
191     if ( vNodes == NULL )
192         return NULL;
193     // mark nodes
194     Wlc_NtkForEachObjVec( vNodes, p, pObj, i )
195         pObj->Mark = 1;
196     // iterate through the nodes in the DFS order
197     Wlc_NtkCleanCopy( p );
198     Wlc_NtkForEachObj( p, pObj, i )
199     {
200         if ( i == Vec_IntSize(&p->vCopies) )
201             break;
202         if ( pObj->Mark ) {
203             // clean
204             pObj->Mark = 0;
205             // add fresh PI with the same number of bits
206             iObj = Wlc_ObjAlloc( p, WLC_OBJ_PI, Wlc_ObjIsSigned(pObj), Wlc_ObjRange(pObj) - 1, 0 );
207         }
208         else {
209             // update fanins
210             Wlc_ObjForEachFanin( pObj, iFanin, k )
211                 Wlc_ObjFanins(pObj)[k] = Wlc_ObjCopy(p, iFanin);
212             // node to remain
213             iObj = i;
214         }
215         Wlc_ObjSetCopy( p, i, iObj );
216     }
217     // POs do not change in this procedure
218     if ( vNodes != vNodesInit )
219         Vec_IntFree( vNodes );
220     // reconstruct topological order
221     pNew = Wlc_NtkDupDfs( p, 0, 1 );
222     return pNew;
223 }
224 
225 /**Function*************************************************************
226 
227   Synopsis    [Adds UIF constraints to node pairs and updates POs.]
228 
229   Description []
230 
231   SideEffects []
232 
233   SeeAlso     []
234 
235 ***********************************************************************/
Wlc_NtkUifNodePairs(Wlc_Ntk_t * p,Vec_Int_t * vPairsInit)236 Wlc_Ntk_t * Wlc_NtkUifNodePairs( Wlc_Ntk_t * p, Vec_Int_t * vPairsInit )
237 {
238     Vec_Int_t * vPairs = vPairsInit;
239     Wlc_Ntk_t * pNew;
240     Wlc_Obj_t * pObj, * pObj2;
241     Vec_Int_t * vUifConstrs, * vCompares, * vFanins;
242     int i, k, iObj, iObj2, iObjNew, iObjNew2;
243     int iFanin, iFanin2, iFaninNew;
244     // get multiplier pairs if not given
245     if ( vPairs == NULL )
246         vPairs = Wlc_NtkFindUifableMultiplierPairs( p );
247     if ( vPairs == NULL )
248         return NULL;
249     // sanity checks
250     assert( Vec_IntSize(vPairs) > 0 && Vec_IntSize(vPairs) % 2 == 0 );
251     // iterate through node pairs
252     vFanins = Vec_IntAlloc( 100 );
253     vCompares = Vec_IntAlloc( 100 );
254     vUifConstrs = Vec_IntAlloc( 100 );
255     Vec_IntForEachEntryDouble( vPairs, iObj, iObj2, i )
256     {
257         // get two nodes
258         pObj  = Wlc_NtkObj( p, iObj );
259         pObj2 = Wlc_NtkObj( p, iObj2 );
260         assert( Wlc_NtkPairIsUifable(p, pObj, pObj2) );
261         // create fanin comparator nodes
262         Vec_IntClear( vCompares );
263         Wlc_ObjForEachFanin( pObj, iFanin, k )
264         {
265             iFanin2 = Wlc_ObjFaninId( pObj2, k );
266             Vec_IntFillTwo( vFanins, 2, iFanin, iFanin2 );
267             iFaninNew = Wlc_ObjCreate( p, WLC_OBJ_COMP_NOTEQU, 0, 0, 0, vFanins );
268             Vec_IntPush( vCompares, iFaninNew );
269             // note that a pointer to Wlc_Obj_t (for example, pObj) can be invalidated after a call to
270             // Wlc_ObjCreate() due to a possible realloc of the internal array of objects...
271             pObj = Wlc_NtkObj( p, iObj );
272         }
273         // concatenate fanin comparators
274         iObjNew = Wlc_ObjCreate( p, WLC_OBJ_BIT_CONCAT, 0, Vec_IntSize(vCompares) - 1, 0, vCompares );
275         // create reduction-OR node
276         Vec_IntFill( vFanins, 1, iObjNew );
277         iObjNew = Wlc_ObjCreate( p, WLC_OBJ_REDUCT_OR, 0, 0, 0, vFanins );
278         // craete output comparator node
279         Vec_IntFillTwo( vFanins, 2, iObj, iObj2 );
280         iObjNew2 = Wlc_ObjCreate( p, WLC_OBJ_COMP_EQU, 0, 0, 0, vFanins );
281         // create implication node (iObjNew is already complemented above)
282         Vec_IntFillTwo( vFanins, 2, iObjNew, iObjNew2 );
283         iObjNew = Wlc_ObjCreate( p, WLC_OBJ_LOGIC_OR, 0, 0, 0, vFanins );
284         // save the constraint
285         Vec_IntPush( vUifConstrs, iObjNew );
286     }
287     // derive the AND of the UIF contraints
288     assert( Vec_IntSize(vUifConstrs) > 0 );
289     if ( Vec_IntSize(vUifConstrs) == 1 )
290         iObjNew = Vec_IntEntry( vUifConstrs, 0 );
291     else
292     {
293         // concatenate
294         iObjNew = Wlc_ObjCreate( p, WLC_OBJ_BIT_CONCAT, 0, Vec_IntSize(vUifConstrs) - 1, 0, vUifConstrs );
295         // create reduction-AND node
296         Vec_IntFill( vFanins, 1, iObjNew );
297         iObjNew = Wlc_ObjCreate( p, WLC_OBJ_REDUCT_AND, 0, 0, 0, vFanins );
298     }
299     // update each PO to point to the new node
300     Wlc_NtkForEachPo( p, pObj, i )
301     {
302         iObj = Wlc_ObjId(p, pObj);
303         Vec_IntFillTwo( vFanins, 2, iObj, iObjNew );
304         iObjNew = Wlc_ObjCreate( p, WLC_OBJ_LOGIC_AND, 0, 0, 0, vFanins );
305         // note that a pointer to Wlc_Obj_t (for example, pObj) can be invalidated after a call to
306         // Wlc_ObjCreate() due to a possible realloc of the internal array of objects...
307         pObj = Wlc_NtkObj( p, iObj );
308         // update PO/CO arrays
309         assert( Vec_IntEntry(&p->vPos, i) == iObj );
310         assert( Vec_IntEntry(&p->vCos, i) == iObj );
311         Vec_IntWriteEntry( &p->vPos, i, iObjNew );
312         Vec_IntWriteEntry( &p->vCos, i, iObjNew );
313         // transfer the PO attribute
314         Wlc_NtkObj(p, iObjNew)->fIsPo = 1;
315         assert( pObj->fIsPo );
316         pObj->fIsPo = 0;
317     }
318     // cleanup
319     Vec_IntFree( vUifConstrs );
320     Vec_IntFree( vCompares );
321     Vec_IntFree( vFanins );
322     if ( vPairs != vPairsInit )
323         Vec_IntFree( vPairs );
324     // reconstruct topological order
325     pNew = Wlc_NtkDupDfs( p, 0, 1 );
326     return pNew;
327 }
328 
329 ////////////////////////////////////////////////////////////////////////
330 ///                       END OF FILE                                ///
331 ////////////////////////////////////////////////////////////////////////
332 
333 
334 ABC_NAMESPACE_IMPL_END
335 
336