1 /**CFile****************************************************************
2
3 FileName [mapperRefs.c]
4
5 PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
6
7 Synopsis [Generic technology mapping engine.]
8
9 Author [MVSIS Group]
10
11 Affiliation [UC Berkeley]
12
13 Date [Ver. 2.0. Started - June 1, 2004.]
14
15 Revision [$Id: mapperRefs.h,v 1.0 2003/09/08 00:00:00 alanmi Exp $]
16
17 ***********************************************************************/
18
19 #include "mapperInt.h"
20
21 ABC_NAMESPACE_IMPL_START
22
23
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27
28 ////////////////////////////////////////////////////////////////////////
29 /// FUNCTION DEFINITIONS ///
30 ////////////////////////////////////////////////////////////////////////
31
32 /**Function*************************************************************
33
34 Synopsis [Reads the actual reference counter of a phase.]
35
36 Description []
37
38 SideEffects []
39
40 SeeAlso []
41
42 ***********************************************************************/
Map_NodeReadRefPhaseAct(Map_Node_t * pNode,int fPhase)43 int Map_NodeReadRefPhaseAct( Map_Node_t * pNode, int fPhase )
44 {
45 assert( !Map_IsComplement(pNode) );
46 if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned
47 return pNode->nRefAct[fPhase];
48 assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned
49 return pNode->nRefAct[2];
50 }
51
52 /**Function*************************************************************
53
54 Synopsis [Reads the estimated reference counter of a phase.]
55
56 Description []
57
58 SideEffects []
59
60 SeeAlso []
61
62 ***********************************************************************/
Map_NodeReadRefPhaseEst(Map_Node_t * pNode,int fPhase)63 float Map_NodeReadRefPhaseEst( Map_Node_t * pNode, int fPhase )
64 {
65 assert( !Map_IsComplement(pNode) );
66 if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned
67 return pNode->nRefEst[fPhase];
68 assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned
69 // return pNode->nRefEst[0] + pNode->nRefEst[1];
70 return pNode->nRefEst[2];
71 }
72
73
74 /**Function*************************************************************
75
76 Synopsis [Increments the actual reference counter of a phase.]
77
78 Description [Returns the old reference counter.]
79
80 SideEffects []
81
82 SeeAlso []
83
84 ***********************************************************************/
Map_NodeIncRefPhaseAct(Map_Node_t * pNode,int fPhase)85 int Map_NodeIncRefPhaseAct( Map_Node_t * pNode, int fPhase )
86 {
87 assert( !Map_IsComplement(pNode) );
88 if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned
89 return pNode->nRefAct[fPhase]++;
90 assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned
91 return pNode->nRefAct[2]++;
92 }
93
94 /**Function*************************************************************
95
96 Synopsis [Decrements the actual reference counter of a phase.]
97
98 Description [Returns the new reference counter.]
99
100 SideEffects []
101
102 SeeAlso []
103
104 ***********************************************************************/
Map_NodeDecRefPhaseAct(Map_Node_t * pNode,int fPhase)105 int Map_NodeDecRefPhaseAct( Map_Node_t * pNode, int fPhase )
106 {
107 assert( !Map_IsComplement(pNode) );
108 if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned
109 return --pNode->nRefAct[fPhase];
110 assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned
111 return --pNode->nRefAct[2];
112 }
113
114
115 /**Function*************************************************************
116
117 Synopsis [Sets the estimated reference counter for the PIs.]
118
119 Description []
120
121 SideEffects []
122
123 SeeAlso []
124
125 ***********************************************************************/
Map_MappingEstimateRefsInit(Map_Man_t * p)126 void Map_MappingEstimateRefsInit( Map_Man_t * p )
127 {
128 Map_Node_t * pNode;
129 int i;
130 for ( i = 0; i < p->vMapObjs->nSize; i++ )
131 {
132 pNode = p->vMapObjs->pArray[i];
133 // pNode->nRefEst[0] = pNode->nRefEst[1] = ((float)pNode->nRefs)*(float)2.0;
134 pNode->nRefEst[0] = pNode->nRefEst[1] = pNode->nRefEst[2] = ((float)pNode->nRefs);
135 }
136 }
137
138 /**Function*************************************************************
139
140 Synopsis [Sets the estimated reference counter.]
141
142 Description [When this procedure is called for the first time,
143 the reference counter is estimated from the AIG. Otherwise, it is
144 a linear combination of reference counters in the last two iterations.]
145
146 SideEffects []
147
148 SeeAlso []
149
150 ***********************************************************************/
Map_MappingEstimateRefs(Map_Man_t * p)151 void Map_MappingEstimateRefs( Map_Man_t * p )
152 {
153 Map_Node_t * pNode;
154 int i;
155 for ( i = 0; i < p->vMapObjs->nSize; i++ )
156 {
157 pNode = p->vMapObjs->pArray[i];
158 // pNode->nRefEst[0] = (float)((2.0 * pNode->nRefEst[0] + 1.0 * pNode->nRefAct[0]) / 3.0);
159 // pNode->nRefEst[1] = (float)((2.0 * pNode->nRefEst[1] + 1.0 * pNode->nRefAct[1]) / 3.0);
160 // pNode->nRefEst[2] = (float)((2.0 * pNode->nRefEst[2] + 1.0 * pNode->nRefAct[2]) / 3.0);
161 pNode->nRefEst[0] = (float)((3.0 * pNode->nRefEst[0] + 1.0 * pNode->nRefAct[0]) / 4.0);
162 pNode->nRefEst[1] = (float)((3.0 * pNode->nRefEst[1] + 1.0 * pNode->nRefAct[1]) / 4.0);
163 pNode->nRefEst[2] = (float)((3.0 * pNode->nRefEst[2] + 1.0 * pNode->nRefAct[2]) / 4.0);
164 }
165 }
166
167 /**function*************************************************************
168
169 synopsis [Computes the area flow of the cut.]
170
171 description [Computes the area flow of the cut if it is implemented using
172 the best supergate with the best phase.]
173
174 sideeffects []
175
176 seealso []
177
178 ***********************************************************************/
Map_CutGetAreaFlow(Map_Cut_t * pCut,int fPhase)179 float Map_CutGetAreaFlow( Map_Cut_t * pCut, int fPhase )
180 {
181 Map_Match_t * pM = pCut->M + fPhase;
182 Map_Super_t * pSuper = pM->pSuperBest;
183 unsigned uPhaseTot = pM->uPhaseBest;
184 Map_Cut_t * pCutFanin;
185 float aFlowRes, aFlowFanin, nRefs;
186 int i, fPinPhasePos;
187
188 // start the resulting area flow
189 aFlowRes = pSuper->Area;
190 // iterate through the leaves
191 for ( i = 0; i < pCut->nLeaves; i++ )
192 {
193 // get the phase of this fanin
194 fPinPhasePos = ((uPhaseTot & (1 << i)) == 0);
195 // get the cut implementing this phase of the fanin
196 pCutFanin = pCut->ppLeaves[i]->pCutBest[fPinPhasePos];
197 // if the cut is not available, we have to use the opposite phase
198 if ( pCutFanin == NULL )
199 {
200 fPinPhasePos = !fPinPhasePos;
201 pCutFanin = pCut->ppLeaves[i]->pCutBest[fPinPhasePos];
202 }
203 aFlowFanin = pCutFanin->M[fPinPhasePos].AreaFlow; // ignores the area of the interter
204 // get the fanout count of the cut in the given phase
205 nRefs = Map_NodeReadRefPhaseEst( pCut->ppLeaves[i], fPinPhasePos );
206 // if the node does no fanout, assume fanout count equal to 1
207 if ( nRefs == (float)0.0 )
208 nRefs = (float)1.0;
209 // add the area flow due to the fanin
210 aFlowRes += aFlowFanin / nRefs;
211 }
212 pM->AreaFlow = aFlowRes;
213 return aFlowRes;
214 }
215
216
217 /**function*************************************************************
218
219 synopsis [References or dereferences the cut.]
220
221 description [This reference part is similar to Cudd_NodeReclaim().
222 The dereference part is similar to Cudd_RecursiveDeref().]
223
224 sideeffects []
225
226 seealso []
227
228 ***********************************************************************/
Map_CutRefDeref(Map_Cut_t * pCut,int fPhase,int fReference,int fUpdateProf)229 float Map_CutRefDeref( Map_Cut_t * pCut, int fPhase, int fReference, int fUpdateProf )
230 {
231 Map_Node_t * pNodeChild;
232 Map_Cut_t * pCutChild;
233 float aArea;
234 int i, fPhaseChild;
235 // int nRefs;
236
237 // consider the elementary variable
238 if ( pCut->nLeaves == 1 )
239 return 0;
240 // start the area of this cut
241 aArea = Map_CutGetRootArea( pCut, fPhase );
242 if ( fUpdateProf )
243 {
244 if ( fReference )
245 Mio_GateIncProfile2( pCut->M[fPhase].pSuperBest->pRoot );
246 else
247 Mio_GateDecProfile2( pCut->M[fPhase].pSuperBest->pRoot );
248 }
249 // go through the children
250 for ( i = 0; i < pCut->nLeaves; i++ )
251 {
252 pNodeChild = pCut->ppLeaves[i];
253 fPhaseChild = Map_CutGetLeafPhase( pCut, fPhase, i );
254 // get the reference counter of the child
255 /*
256 // this code does not take inverters into account
257 // the quality of area recovery seems to always be a little worse
258 if ( fReference )
259 nRefs = Map_NodeIncRefPhaseAct( pNodeChild, fPhaseChild );
260 else
261 nRefs = Map_NodeDecRefPhaseAct( pNodeChild, fPhaseChild );
262 assert( nRefs >= 0 );
263 // skip if the child was already reference before
264 if ( nRefs > 0 )
265 continue;
266 */
267
268 if ( fReference )
269 {
270 if ( pNodeChild->pCutBest[0] && pNodeChild->pCutBest[1] ) // both phases are present
271 {
272 // if this phase of the node is referenced, there is no recursive call
273 pNodeChild->nRefAct[2]++;
274 if ( pNodeChild->nRefAct[fPhaseChild]++ > 0 )
275 continue;
276 }
277 else // only one phase is present
278 {
279 // inverter should be added if the phase
280 // (a) has no reference and (b) is implemented using other phase
281 if ( pNodeChild->nRefAct[fPhaseChild]++ == 0 && pNodeChild->pCutBest[fPhaseChild] == NULL )
282 aArea += pNodeChild->p->pSuperLib->AreaInv;
283 // if the node is referenced, there is no recursive call
284 if ( pNodeChild->nRefAct[2]++ > 0 )
285 continue;
286 }
287 }
288 else
289 {
290 if ( pNodeChild->pCutBest[0] && pNodeChild->pCutBest[1] ) // both phases are present
291 {
292 // if this phase of the node is referenced, there is no recursive call
293 --pNodeChild->nRefAct[2];
294 if ( --pNodeChild->nRefAct[fPhaseChild] > 0 )
295 continue;
296 }
297 else // only one phase is present
298 {
299 // inverter should be added if the phase
300 // (a) has no reference and (b) is implemented using other phase
301 if ( --pNodeChild->nRefAct[fPhaseChild] == 0 && pNodeChild->pCutBest[fPhaseChild] == NULL )
302 aArea += pNodeChild->p->pSuperLib->AreaInv;
303 // if the node is referenced, there is no recursive call
304 if ( --pNodeChild->nRefAct[2] > 0 )
305 continue;
306 }
307 assert( pNodeChild->nRefAct[fPhaseChild] >= 0 );
308 }
309
310 // get the child cut
311 pCutChild = pNodeChild->pCutBest[fPhaseChild];
312 // if the child does not have this phase mapped, take the opposite phase
313 if ( pCutChild == NULL )
314 {
315 fPhaseChild = !fPhaseChild;
316 pCutChild = pNodeChild->pCutBest[fPhaseChild];
317 }
318 // reference and compute area recursively
319 aArea += Map_CutRefDeref( pCutChild, fPhaseChild, fReference, fUpdateProf );
320 }
321 return aArea;
322 }
323
324 /**function*************************************************************
325
326 synopsis [Computes the exact area associated with the cut.]
327
328 description [Assumes that the cut is referenced.]
329
330 sideeffects []
331
332 seealso []
333
334 ***********************************************************************/
Map_CutGetAreaRefed(Map_Cut_t * pCut,int fPhase)335 float Map_CutGetAreaRefed( Map_Cut_t * pCut, int fPhase )
336 {
337 float aResult, aResult2;
338 aResult2 = Map_CutRefDeref( pCut, fPhase, 0, 0 ); // dereference
339 aResult = Map_CutRefDeref( pCut, fPhase, 1, 0 ); // reference
340 // assert( aResult == aResult2 );
341 return aResult;
342 }
343
344 /**function*************************************************************
345
346 synopsis [Computes the exact area associated with the cut.]
347
348 description []
349
350 sideeffects []
351
352 seealso []
353
354 ***********************************************************************/
Map_CutGetAreaDerefed(Map_Cut_t * pCut,int fPhase)355 float Map_CutGetAreaDerefed( Map_Cut_t * pCut, int fPhase )
356 {
357 float aResult, aResult2;
358 aResult2 = Map_CutRefDeref( pCut, fPhase, 1, 0 ); // reference
359 aResult = Map_CutRefDeref( pCut, fPhase, 0, 0 ); // dereference
360 // assert( aResult == aResult2 );
361 return aResult;
362 }
363
364 /**function*************************************************************
365
366 synopsis [References the cut.]
367
368 description []
369
370 sideeffects []
371
372 seealso []
373
374 ***********************************************************************/
Map_CutRef(Map_Cut_t * pCut,int fPhase,int fProfile)375 float Map_CutRef( Map_Cut_t * pCut, int fPhase, int fProfile )
376 {
377 return Map_CutRefDeref( pCut, fPhase, 1, fProfile ); // reference
378 }
379
380 /**function*************************************************************
381
382 synopsis [Dereferences the cut.]
383
384 description []
385
386 sideeffects []
387
388 seealso []
389
390 ***********************************************************************/
Map_CutDeref(Map_Cut_t * pCut,int fPhase,int fProfile)391 float Map_CutDeref( Map_Cut_t * pCut, int fPhase, int fProfile )
392 {
393 return Map_CutRefDeref( pCut, fPhase, 0, fProfile ); // dereference
394 }
395
396
397 /**Function*************************************************************
398
399 Synopsis [Computes actual reference counters.]
400
401 Description [Collects the nodes used in the mapping in array pMan->vMapping.
402 Nodes are collected in reverse topological order to facilitate the
403 computation of required times.]
404
405 SideEffects []
406
407 SeeAlso []
408
409 ***********************************************************************/
Map_MappingSetRefs_rec(Map_Man_t * pMan,Map_Node_t * pNode)410 void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode )
411 {
412 Map_Cut_t * pCut;
413 Map_Node_t * pNodeR;
414 unsigned uPhase;
415 int i, fPhase, fInvPin;
416 // get the regular node and its phase
417 pNodeR = Map_Regular(pNode);
418 fPhase = !Map_IsComplement(pNode);
419 pNodeR->nRefAct[2]++;
420 // quit if the node was already visited in this phase
421 if ( pNodeR->nRefAct[fPhase]++ )
422 return;
423 // quit if this is a PI node
424 if ( Map_NodeIsVar(pNodeR) )
425 return;
426 // propagate through buffer
427 if ( Map_NodeIsBuf(pNodeR) )
428 {
429 Map_MappingSetRefs_rec( pMan, Map_NotCond(pNodeR->p1, Map_IsComplement(pNode)) );
430 return;
431 }
432 assert( Map_NodeIsAnd(pNode) );
433 // get the cut implementing this or opposite polarity
434 pCut = pNodeR->pCutBest[fPhase];
435 if ( pCut == NULL )
436 {
437 fPhase = !fPhase;
438 pCut = pNodeR->pCutBest[fPhase];
439 }
440 if ( pMan->fUseProfile )
441 Mio_GateIncProfile2( pCut->M[fPhase].pSuperBest->pRoot );
442 // visit the transitive fanin
443 uPhase = pCut->M[fPhase].uPhaseBest;
444 for ( i = 0; i < pCut->nLeaves; i++ )
445 {
446 fInvPin = ((uPhase & (1 << i)) > 0);
447 Map_MappingSetRefs_rec( pMan, Map_NotCond(pCut->ppLeaves[i], fInvPin) );
448 }
449 }
Map_MappingSetRefs(Map_Man_t * pMan)450 void Map_MappingSetRefs( Map_Man_t * pMan )
451 {
452 Map_Node_t * pNode;
453 int i;
454 if ( pMan->fUseProfile )
455 Mio_LibraryCleanProfile2( pMan->pSuperLib->pGenlib );
456 // clean all references
457 for ( i = 0; i < pMan->vMapObjs->nSize; i++ )
458 {
459 pNode = pMan->vMapObjs->pArray[i];
460 pNode->nRefAct[0] = 0;
461 pNode->nRefAct[1] = 0;
462 pNode->nRefAct[2] = 0;
463 }
464 // visit nodes reachable from POs in the DFS order through the best cuts
465 for ( i = 0; i < pMan->nOutputs; i++ )
466 {
467 pNode = pMan->pOutputs[i];
468 if ( !Map_NodeIsConst(pNode) )
469 Map_MappingSetRefs_rec( pMan, pNode );
470 }
471 }
472
473
474 /**Function*************************************************************
475
476 Synopsis [Computes the array of mapping.]
477
478 Description []
479
480 SideEffects []
481
482 SeeAlso []
483
484 ***********************************************************************/
Map_MappingGetArea(Map_Man_t * pMan)485 float Map_MappingGetArea( Map_Man_t * pMan )
486 {
487 Map_Node_t * pNode;
488 float Area = 0.0;
489 int i;
490 if ( pMan->fUseProfile )
491 Mio_LibraryCleanProfile2( pMan->pSuperLib->pGenlib );
492 for ( i = 0; i < pMan->vMapObjs->nSize; i++ )
493 {
494 pNode = pMan->vMapObjs->pArray[i];
495 if ( pNode->nRefAct[2] == 0 )
496 continue;
497 if ( Map_NodeIsBuf(pNode) )
498 continue;
499 // at least one phase has the best cut assigned
500 assert( pNode->pCutBest[0] != NULL || pNode->pCutBest[1] != NULL );
501 // at least one phase is used in the mapping
502 assert( pNode->nRefAct[0] > 0 || pNode->nRefAct[1] > 0 );
503 // compute the array due to the supergate
504 if ( Map_NodeIsAnd(pNode) )
505 {
506 // count area of the negative phase
507 if ( pNode->pCutBest[0] && (pNode->nRefAct[0] > 0 || pNode->pCutBest[1] == NULL) )
508 {
509 Area += pNode->pCutBest[0]->M[0].pSuperBest->Area;
510 if ( pMan->fUseProfile )
511 Mio_GateIncProfile2( pNode->pCutBest[0]->M[0].pSuperBest->pRoot );
512 }
513 // count area of the positive phase
514 if ( pNode->pCutBest[1] && (pNode->nRefAct[1] > 0 || pNode->pCutBest[0] == NULL) )
515 {
516 Area += pNode->pCutBest[1]->M[1].pSuperBest->Area;
517 if ( pMan->fUseProfile )
518 Mio_GateIncProfile2( pNode->pCutBest[1]->M[1].pSuperBest->pRoot );
519 }
520 }
521 // count area of the interver if we need to implement one phase with another phase
522 if ( (pNode->pCutBest[0] == NULL && pNode->nRefAct[0] > 0) ||
523 (pNode->pCutBest[1] == NULL && pNode->nRefAct[1] > 0) )
524 Area += pMan->pSuperLib->AreaInv;
525 }
526 // add buffers for each CO driven by a CI
527 for ( i = 0; i < pMan->nOutputs; i++ )
528 if ( Map_NodeIsVar(pMan->pOutputs[i]) && !Map_IsComplement(pMan->pOutputs[i]) )
529 Area += pMan->pSuperLib->AreaBuf;
530 return Area;
531 }
532
533
534 ////////////////////////////////////////////////////////////////////////
535 /// END OF FILE ///
536 ////////////////////////////////////////////////////////////////////////
537
538
539 ABC_NAMESPACE_IMPL_END
540
541