1 /**CFile****************************************************************
2
3 FileName [mapperMatch.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: mapperMatch.c,v 1.7 2004/09/30 21:18:10 satrajit Exp $]
16
17 ***********************************************************************/
18
19 #include "mapperInt.h"
20
21 #include "misc/util/utilNam.h"
22 #include "map/scl/sclCon.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26
27 /*
28 A potential improvement:
29 When an internal node is not used in the mapping, its required times
30 are set to be +infinity. So when we recover area, we try to find the
31 best match for area and completely disregard the delay for the nodes
32 that are not currently used in the mapping because any match whose
33 arrival times are less than the required times (+infinity) can be used.
34 It may be possible to develop a better approach to recover area for
35 the nodes that are not currently used in the mapping...
36 */
37
38 ////////////////////////////////////////////////////////////////////////
39 /// DECLARATIONS ///
40 ////////////////////////////////////////////////////////////////////////
41
42 ////////////////////////////////////////////////////////////////////////
43 /// FUNCTION DEFINITIONS ///
44 ////////////////////////////////////////////////////////////////////////
45
46 /**Function*************************************************************
47
48 Synopsis [Cleans the match.]
49
50 Description []
51
52 SideEffects []
53
54 SeeAlso []
55
56 ***********************************************************************/
Map_MatchClean(Map_Match_t * pMatch)57 void Map_MatchClean( Map_Match_t * pMatch )
58 {
59 memset( pMatch, 0, sizeof(Map_Match_t) );
60 pMatch->AreaFlow = MAP_FLOAT_LARGE; // unassigned
61 pMatch->tArrive.Rise = MAP_FLOAT_LARGE; // unassigned
62 pMatch->tArrive.Fall = MAP_FLOAT_LARGE; // unassigned
63 pMatch->tArrive.Worst = MAP_FLOAT_LARGE; // unassigned
64 }
65
66 /**Function*************************************************************
67
68 Synopsis [Compares two matches.]
69
70 Description [Returns 1 if the second match is better. Otherwise returns 0.]
71
72 SideEffects []
73
74 SeeAlso []
75
76 ***********************************************************************/
Map_MatchCompare(Map_Man_t * pMan,Map_Match_t * pM1,Map_Match_t * pM2,int fDoingArea)77 int Map_MatchCompare( Map_Man_t * pMan, Map_Match_t * pM1, Map_Match_t * pM2, int fDoingArea )
78 {
79 // if ( pM1->pSuperBest == pM2->pSuperBest )
80 // return 0;
81 if ( !fDoingArea )
82 {
83 // compare the arrival times
84 if ( pM1->tArrive.Worst < pM2->tArrive.Worst - pMan->fEpsilon )
85 return 0;
86 if ( pM1->tArrive.Worst > pM2->tArrive.Worst + pMan->fEpsilon )
87 return 1;
88 // compare the areas or area flows
89 if ( pM1->AreaFlow < pM2->AreaFlow - pMan->fEpsilon )
90 return 0;
91 if ( pM1->AreaFlow > pM2->AreaFlow + pMan->fEpsilon )
92 return 1;
93 // compare the fanout limits
94 if ( pM1->pSuperBest->nFanLimit > pM2->pSuperBest->nFanLimit )
95 return 0;
96 if ( pM1->pSuperBest->nFanLimit < pM2->pSuperBest->nFanLimit )
97 return 1;
98 // compare the number of leaves
99 if ( pM1->pSuperBest->nFanins < pM2->pSuperBest->nFanins )
100 return 0;
101 if ( pM1->pSuperBest->nFanins > pM2->pSuperBest->nFanins )
102 return 1;
103 // otherwise prefer the old cut
104 return 0;
105 }
106 else
107 {
108 // compare the areas or area flows
109 if ( pM1->AreaFlow < pM2->AreaFlow - pMan->fEpsilon )
110 return 0;
111 if ( pM1->AreaFlow > pM2->AreaFlow + pMan->fEpsilon )
112 return 1;
113
114 // make decision based on cell profile
115 if ( pMan->fUseProfile && pM1->pSuperBest && pM1->pSuperBest )
116 {
117 int M1req = Mio_GateReadProfile(pM1->pSuperBest->pRoot);
118 int M2req = Mio_GateReadProfile(pM2->pSuperBest->pRoot);
119 int M1act = Mio_GateReadProfile2(pM1->pSuperBest->pRoot);
120 int M2act = Mio_GateReadProfile2(pM2->pSuperBest->pRoot);
121 //printf( "%d %d ", M1req, M2req );
122 if ( M1act < M1req && M2act > M2req )
123 return 0;
124 if ( M2act < M2req && M1act > M1req )
125 return 1;
126 }
127
128 // compare the arrival times
129 if ( pM1->tArrive.Worst < pM2->tArrive.Worst - pMan->fEpsilon )
130 return 0;
131 if ( pM1->tArrive.Worst > pM2->tArrive.Worst + pMan->fEpsilon )
132 return 1;
133 // compare the fanout limits
134 if ( pM1->pSuperBest->nFanLimit > pM2->pSuperBest->nFanLimit )
135 return 0;
136 if ( pM1->pSuperBest->nFanLimit < pM2->pSuperBest->nFanLimit )
137 return 1;
138 // compare the number of leaves
139 if ( pM1->pSuperBest->nFanins < pM2->pSuperBest->nFanins )
140 return 0;
141 if ( pM1->pSuperBest->nFanins > pM2->pSuperBest->nFanins )
142 return 1;
143 // otherwise prefer the old cut
144 return 0;
145 }
146 }
147
148 /**Function*************************************************************
149
150 Synopsis [Find the best matching of the cut.]
151
152 Description [The parameters: the node (pNode), the cut (pCut), the phase to be matched
153 (fPhase), and the upper bound on the arrival times of the cut (fWorstLimit). This
154 procedure goes through the matching supergates up to the phase assignment, and selects the
155 best supergate, which will be used to map the cut. As a result of calling this procedure
156 the matching information is written into pMatch.]
157
158 SideEffects []
159
160 SeeAlso []
161
162 ***********************************************************************/
Map_MatchNodeCut(Map_Man_t * p,Map_Node_t * pNode,Map_Cut_t * pCut,int fPhase,float fWorstLimit)163 int Map_MatchNodeCut( Map_Man_t * p, Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase, float fWorstLimit )
164 {
165 Map_Match_t MatchBest, * pMatch = pCut->M + fPhase;
166 Map_Super_t * pSuper;
167 int i, Counter;
168
169 // save the current match of the cut
170 MatchBest = *pMatch;
171 // go through the supergates
172 for ( pSuper = pMatch->pSupers, Counter = 0; pSuper; pSuper = pSuper->pNext, Counter++ )
173 {
174 p->nMatches++;
175 // this is an attempt to reduce the runtime of matching and area
176 // at the cost of rare and very minor increase in delay
177 // (the supergates are sorted by increasing area)
178 if ( Counter == 30 )
179 break;
180
181 // go through different phases of the given match and supergate
182 pMatch->pSuperBest = pSuper;
183 for ( i = 0; i < (int)pSuper->nPhases; i++ )
184 {
185 p->nPhases++;
186 // find the overall phase of this match
187 pMatch->uPhaseBest = pMatch->uPhase ^ pSuper->uPhases[i];
188 if ( p->fMappingMode == 0 )
189 {
190 // get the arrival time
191 Map_TimeCutComputeArrival( pNode, pCut, fPhase, fWorstLimit );
192 // skip the cut if the arrival times exceed the required times
193 if ( pMatch->tArrive.Worst > fWorstLimit + p->fEpsilon )
194 continue;
195 // get the area (area flow)
196 pMatch->AreaFlow = Map_CutGetAreaFlow( pCut, fPhase );
197 }
198 else
199 {
200 // get the area (area flow)
201 if ( p->fMappingMode == 2 || p->fMappingMode == 3 )
202 pMatch->AreaFlow = Map_CutGetAreaDerefed( pCut, fPhase );
203 else if ( p->fMappingMode == 4 )
204 pMatch->AreaFlow = Map_SwitchCutGetDerefed( pNode, pCut, fPhase );
205 else
206 pMatch->AreaFlow = Map_CutGetAreaFlow( pCut, fPhase );
207 // skip if the cut is too large
208 if ( pMatch->AreaFlow > MatchBest.AreaFlow + p->fEpsilon )
209 continue;
210 // get the arrival time
211 Map_TimeCutComputeArrival( pNode, pCut, fPhase, fWorstLimit );
212 // skip the cut if the arrival times exceed the required times
213 if ( pMatch->tArrive.Worst > fWorstLimit + p->fEpsilon )
214 continue;
215 }
216
217 // if the cut is non-trivial, compare it
218 if ( Map_MatchCompare( p, &MatchBest, pMatch, p->fMappingMode ) )
219 {
220 MatchBest = *pMatch;
221 // if we are mapping for delay, the worst-case limit should be reduced
222 if ( p->fMappingMode == 0 )
223 fWorstLimit = MatchBest.tArrive.Worst;
224 }
225 }
226 }
227 // set the best match
228 *pMatch = MatchBest;
229
230 // recompute the arrival time and area (area flow) of this cut
231 if ( pMatch->pSuperBest )
232 {
233 Map_TimeCutComputeArrival( pNode, pCut, fPhase, MAP_FLOAT_LARGE );
234 if ( p->fMappingMode == 2 || p->fMappingMode == 3 )
235 pMatch->AreaFlow = Map_CutGetAreaDerefed( pCut, fPhase );
236 else if ( p->fMappingMode == 4 )
237 pMatch->AreaFlow = Map_SwitchCutGetDerefed( pNode, pCut, fPhase );
238 else
239 pMatch->AreaFlow = Map_CutGetAreaFlow( pCut, fPhase );
240 }
241 return 1;
242 }
243
244 /**Function*************************************************************
245
246 Synopsis [Find the matching of one polarity of the node.]
247
248 Description []
249
250 SideEffects []
251
252 SeeAlso []
253
254 ***********************************************************************/
Map_MatchNodePhase(Map_Man_t * p,Map_Node_t * pNode,int fPhase)255 int Map_MatchNodePhase( Map_Man_t * p, Map_Node_t * pNode, int fPhase )
256 {
257 Map_Match_t MatchBest, * pMatch;
258 Map_Cut_t * pCut, * pCutBest;
259 float Area1 = 0.0; // Suppress "might be used uninitialized
260 float Area2, fWorstLimit;
261
262 // skip the cuts that have been unassigned during area recovery
263 pCutBest = pNode->pCutBest[fPhase];
264 if ( p->fMappingMode != 0 && pCutBest == NULL )
265 return 1;
266
267 // recompute the arrival times of the current best match
268 // because the arrival times of the fanins may have changed
269 // as a result of remapping fanins in the topological order
270 if ( p->fMappingMode != 0 )
271 {
272 Map_TimeCutComputeArrival( pNode, pCutBest, fPhase, MAP_FLOAT_LARGE );
273 // make sure that the required times are met
274 // assert( pCutBest->M[fPhase].tArrive.Rise < pNode->tRequired[fPhase].Rise + p->fEpsilon );
275 // assert( pCutBest->M[fPhase].tArrive.Fall < pNode->tRequired[fPhase].Fall + p->fEpsilon );
276 }
277
278 // recompute the exact area of the current best match
279 // because the exact area of the fanins may have changed
280 // as a result of remapping fanins in the topological order
281 if ( p->fMappingMode == 2 || p->fMappingMode == 3 )
282 {
283 pMatch = pCutBest->M + fPhase;
284 if ( pNode->nRefAct[fPhase] > 0 ||
285 (pNode->pCutBest[!fPhase] == NULL && pNode->nRefAct[!fPhase] > 0) )
286 pMatch->AreaFlow = Area1 = Map_CutDeref( pCutBest, fPhase, p->fUseProfile );
287 else
288 pMatch->AreaFlow = Area1 = Map_CutGetAreaDerefed( pCutBest, fPhase );
289 }
290 else if ( p->fMappingMode == 4 )
291 {
292 pMatch = pCutBest->M + fPhase;
293 if ( pNode->nRefAct[fPhase] > 0 ||
294 (pNode->pCutBest[!fPhase] == NULL && pNode->nRefAct[!fPhase] > 0) )
295 pMatch->AreaFlow = Area1 = Map_SwitchCutDeref( pNode, pCutBest, fPhase );
296 else
297 pMatch->AreaFlow = Area1 = Map_SwitchCutGetDerefed( pNode, pCutBest, fPhase );
298 }
299
300 // save the old mapping
301 if ( pCutBest )
302 MatchBest = pCutBest->M[fPhase];
303 else
304 Map_MatchClean( &MatchBest );
305
306 // select the new best cut
307 fWorstLimit = pNode->tRequired[fPhase].Worst;
308 for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
309 {
310 // limit gate sizes based on fanout count
311 if ( p->fSkipFanout && ((pNode->nRefs > 3 && pCut->nLeaves > 2) || (pNode->nRefs > 1 && pCut->nLeaves > 3)) )
312 continue;
313 pMatch = pCut->M + fPhase;
314 if ( pMatch->pSupers == NULL )
315 continue;
316
317 // find the matches for the cut
318 Map_MatchNodeCut( p, pNode, pCut, fPhase, fWorstLimit );
319 if ( pMatch->pSuperBest == NULL || pMatch->tArrive.Worst > fWorstLimit + p->fEpsilon )
320 continue;
321
322 // if the cut can be matched compare the matchings
323 if ( Map_MatchCompare( p, &MatchBest, pMatch, p->fMappingMode ) )
324 {
325 pCutBest = pCut;
326 MatchBest = *pMatch;
327 // if we are mapping for delay, the worst-case limit should be tightened
328 if ( p->fMappingMode == 0 )
329 fWorstLimit = MatchBest.tArrive.Worst;
330 }
331 }
332
333 if ( pCutBest == NULL )
334 return 1;
335
336 // set the new mapping
337 pNode->pCutBest[fPhase] = pCutBest;
338 pCutBest->M[fPhase] = MatchBest;
339
340 // reference the new cut if it used
341 if ( p->fMappingMode >= 2 &&
342 (pNode->nRefAct[fPhase] > 0 ||
343 (pNode->pCutBest[!fPhase] == NULL && pNode->nRefAct[!fPhase] > 0)) )
344 {
345 if ( p->fMappingMode == 2 || p->fMappingMode == 3 )
346 Area2 = Map_CutRef( pNode->pCutBest[fPhase], fPhase, p->fUseProfile );
347 else if ( p->fMappingMode == 4 )
348 Area2 = Map_SwitchCutRef( pNode, pNode->pCutBest[fPhase], fPhase );
349 else
350 assert( 0 );
351 // assert( Area2 < Area1 + p->fEpsilon );
352 }
353
354 // make sure that the requited times are met
355 // assert( MatchBest.tArrive.Rise < pNode->tRequired[fPhase].Rise + p->fEpsilon );
356 // assert( MatchBest.tArrive.Fall < pNode->tRequired[fPhase].Fall + p->fEpsilon );
357 return 1;
358 }
359
360 /**Function*************************************************************
361
362 Synopsis [Sets the PI arrival times.]
363
364 Description []
365
366 SideEffects []
367
368 SeeAlso []
369
370 ***********************************************************************/
Map_MappingSetPiArrivalTimes(Map_Man_t * p)371 void Map_MappingSetPiArrivalTimes( Map_Man_t * p )
372 {
373 Map_Node_t * pNode;
374 int i;
375 for ( i = 0; i < p->nInputs; i++ )
376 {
377 pNode = p->pInputs[i];
378 // set the arrival time of the positive phase
379 if ( Scl_ConIsRunning() )
380 {
381 float Time = Scl_ConGetInArrFloat( i );
382 pNode->tArrival[1].Fall = Time;
383 pNode->tArrival[1].Rise = Time;
384 pNode->tArrival[1].Worst = Time;
385 }
386 else
387 pNode->tArrival[1] = p->pInputArrivals[i];
388 pNode->tArrival[1].Rise += p->pNodeDelays ? p->pNodeDelays[pNode->Num] : 0;
389 pNode->tArrival[1].Fall += p->pNodeDelays ? p->pNodeDelays[pNode->Num] : 0;
390 pNode->tArrival[1].Worst += p->pNodeDelays ? p->pNodeDelays[pNode->Num] : 0;
391 // set the arrival time of the negative phase
392 pNode->tArrival[0].Rise = pNode->tArrival[1].Fall + p->pSuperLib->tDelayInv.Rise;
393 pNode->tArrival[0].Fall = pNode->tArrival[1].Rise + p->pSuperLib->tDelayInv.Fall;
394 pNode->tArrival[0].Worst = MAP_MAX(pNode->tArrival[0].Rise, pNode->tArrival[0].Fall);
395 }
396 }
397
398 /**function*************************************************************
399
400 synopsis [Computes the exact area associated with the cut.]
401
402 description []
403
404 sideeffects []
405
406 seealso []
407
408 ***********************************************************************/
Map_TimeMatchWithInverter(Map_Man_t * p,Map_Match_t * pMatch)409 float Map_TimeMatchWithInverter( Map_Man_t * p, Map_Match_t * pMatch )
410 {
411 Map_Time_t tArrInv;
412 tArrInv.Fall = pMatch->tArrive.Rise + p->pSuperLib->tDelayInv.Fall;
413 tArrInv.Rise = pMatch->tArrive.Fall + p->pSuperLib->tDelayInv.Rise;
414 tArrInv.Worst = MAP_MAX( tArrInv.Rise, tArrInv.Fall );
415 return tArrInv.Worst;
416 }
417
418 /**Function*************************************************************
419
420 Synopsis [Attempts dropping one phase of the node.]
421
422 Description []
423
424 SideEffects []
425
426 SeeAlso []
427
428 ***********************************************************************/
Map_NodeTryDroppingOnePhase(Map_Man_t * p,Map_Node_t * pNode)429 void Map_NodeTryDroppingOnePhase( Map_Man_t * p, Map_Node_t * pNode )
430 {
431 Map_Match_t * pMatchBest0, * pMatchBest1;
432 float tWorst0Using1, tWorst1Using0;
433 int fUsePhase1, fUsePhase0;
434
435 // nothing to do if one of the phases is already dropped
436 if ( pNode->pCutBest[0] == NULL || pNode->pCutBest[1] == NULL )
437 return;
438
439 // do not drop while recovering area flow
440 if ( p->fMappingMode == 1 )//|| p->fMappingMode == 2 )
441 return;
442
443 // get the pointers to the matches of the best cuts
444 pMatchBest0 = pNode->pCutBest[0]->M + 0;
445 pMatchBest1 = pNode->pCutBest[1]->M + 1;
446
447 // get the worst arrival times of each phase
448 // implemented using the other phase with inverter added
449 tWorst0Using1 = Map_TimeMatchWithInverter( p, pMatchBest1 );
450 tWorst1Using0 = Map_TimeMatchWithInverter( p, pMatchBest0 );
451
452 // consider the case of mapping for delay
453 if ( p->fMappingMode == 0 && p->DelayTarget < ABC_INFINITY )
454 {
455 // if the arrival time of a phase is larger than the arrival time
456 // of the opposite phase plus the inverter, drop this phase
457 if ( pMatchBest0->tArrive.Worst > tWorst0Using1 + p->fEpsilon )
458 pNode->pCutBest[0] = NULL;
459 else if ( pMatchBest1->tArrive.Worst > tWorst1Using0 + p->fEpsilon )
460 pNode->pCutBest[1] = NULL;
461 return;
462 }
463
464 // do not perform replacement if one of the phases is unused
465 if ( pNode->nRefAct[0] == 0 || pNode->nRefAct[1] == 0 )
466 return;
467
468 // check if replacement of each phase is possible using required times
469 fUsePhase0 = fUsePhase1 = 0;
470 if ( p->fMappingMode == 2 )
471 {
472 fUsePhase0 = (pNode->tRequired[1].Worst > tWorst1Using0 + 3*p->pSuperLib->tDelayInv.Worst + p->fEpsilon);
473 fUsePhase1 = (pNode->tRequired[0].Worst > tWorst0Using1 + 3*p->pSuperLib->tDelayInv.Worst + p->fEpsilon);
474 }
475 else if ( p->fMappingMode == 3 || p->fMappingMode == 4 )
476 {
477 fUsePhase0 = (pNode->tRequired[1].Worst > tWorst1Using0 + p->fEpsilon);
478 fUsePhase1 = (pNode->tRequired[0].Worst > tWorst0Using1 + p->fEpsilon);
479 }
480 if ( !fUsePhase0 && !fUsePhase1 )
481 return;
482
483 // if replacement is possible both ways, use the one that works better
484 if ( fUsePhase0 && fUsePhase1 )
485 {
486 if ( pMatchBest0->AreaFlow < pMatchBest1->AreaFlow )
487 fUsePhase1 = 0;
488 else
489 fUsePhase0 = 0;
490 }
491 // only one phase should be used
492 assert( fUsePhase0 ^ fUsePhase1 );
493
494 // set the corresponding cut to NULL
495 if ( fUsePhase0 )
496 {
497 // deref phase 1 cut if necessary
498 if ( p->fMappingMode >= 2 && pNode->nRefAct[1] > 0 )
499 Map_CutDeref( pNode->pCutBest[1], 1, p->fUseProfile );
500 // get rid of the cut
501 pNode->pCutBest[1] = NULL;
502 // ref phase 0 cut if necessary
503 if ( p->fMappingMode >= 2 && pNode->nRefAct[0] == 0 )
504 Map_CutRef( pNode->pCutBest[0], 0, p->fUseProfile );
505 }
506 else
507 {
508 // deref phase 0 cut if necessary
509 if ( p->fMappingMode >= 2 && pNode->nRefAct[0] > 0 )
510 Map_CutDeref( pNode->pCutBest[0], 0, p->fUseProfile );
511 // get rid of the cut
512 pNode->pCutBest[0] = NULL;
513 // ref phase 1 cut if necessary
514 if ( p->fMappingMode >= 2 && pNode->nRefAct[1] == 0 )
515 Map_CutRef( pNode->pCutBest[1], 1, p->fUseProfile );
516 }
517 }
518
519
520 /**Function*************************************************************
521
522 Synopsis [Transfers the arrival times from the best cuts to the node.]
523
524 Description []
525
526 SideEffects []
527
528 SeeAlso []
529
530 ***********************************************************************/
Map_NodeTransferArrivalTimes(Map_Man_t * p,Map_Node_t * pNode)531 void Map_NodeTransferArrivalTimes( Map_Man_t * p, Map_Node_t * pNode )
532 {
533 // if both phases are available, set their arrival times
534 if ( pNode->pCutBest[0] && pNode->pCutBest[1] )
535 {
536 pNode->tArrival[0] = pNode->pCutBest[0]->M[0].tArrive;
537 pNode->tArrival[1] = pNode->pCutBest[1]->M[1].tArrive;
538 }
539 // if only one phase is available, compute the arrival time of other phase
540 else if ( pNode->pCutBest[0] )
541 {
542 pNode->tArrival[0] = pNode->pCutBest[0]->M[0].tArrive;
543 pNode->tArrival[1].Rise = pNode->tArrival[0].Fall + p->pSuperLib->tDelayInv.Rise;
544 pNode->tArrival[1].Fall = pNode->tArrival[0].Rise + p->pSuperLib->tDelayInv.Fall;
545 pNode->tArrival[1].Worst = MAP_MAX(pNode->tArrival[1].Rise, pNode->tArrival[1].Fall);
546 }
547 else if ( pNode->pCutBest[1] )
548 {
549 pNode->tArrival[1] = pNode->pCutBest[1]->M[1].tArrive;
550 pNode->tArrival[0].Rise = pNode->tArrival[1].Fall + p->pSuperLib->tDelayInv.Rise;
551 pNode->tArrival[0].Fall = pNode->tArrival[1].Rise + p->pSuperLib->tDelayInv.Fall;
552 pNode->tArrival[0].Worst = MAP_MAX(pNode->tArrival[0].Rise, pNode->tArrival[0].Fall);
553 }
554 else
555 {
556 assert( 0 );
557 }
558
559 // assert( pNode->tArrival[0].Rise < pNode->tRequired[0].Rise + p->fEpsilon );
560 // assert( pNode->tArrival[0].Fall < pNode->tRequired[0].Fall + p->fEpsilon );
561
562 // assert( pNode->tArrival[1].Rise < pNode->tRequired[1].Rise + p->fEpsilon );
563 // assert( pNode->tArrival[1].Fall < pNode->tRequired[1].Fall + p->fEpsilon );
564 }
565
566 /**Function*************************************************************
567
568 Synopsis [Computes the best matches of the nodes.]
569
570 Description [Uses parameter p->fMappingMode to decide how to assign
571 the matches for both polarities of the node. While the matches are
572 being assigned, one of them may turn out to be better than the other
573 (in terms of delay, for example). In this case, the worse match can
574 be permanently dropped, and the corresponding pointer set to NULL.]
575
576 SideEffects []
577
578 SeeAlso []
579
580 ***********************************************************************/
Map_MappingMatches(Map_Man_t * p)581 int Map_MappingMatches( Map_Man_t * p )
582 {
583 ProgressBar * pProgress;
584 Map_Node_t * pNode;
585 int i;
586
587 assert( p->fMappingMode >= 0 && p->fMappingMode <= 4 );
588
589 // use the externally given PI arrival times
590 if ( p->fMappingMode == 0 )
591 Map_MappingSetPiArrivalTimes( p );
592
593 // estimate the fanouts
594 if ( p->fMappingMode == 0 )
595 Map_MappingEstimateRefsInit( p );
596 else if ( p->fMappingMode == 1 )
597 Map_MappingEstimateRefs( p );
598
599 // the PI cuts are matched in the cut computation package
600 // in the loop below we match the internal nodes
601 pProgress = Extra_ProgressBarStart( stdout, p->vMapObjs->nSize );
602 for ( i = 0; i < p->vMapObjs->nSize; i++ )
603 {
604 pNode = p->vMapObjs->pArray[i];
605 if ( Map_NodeIsBuf(pNode) )
606 {
607 assert( pNode->p2 == NULL );
608 pNode->tArrival[0] = Map_Regular(pNode->p1)->tArrival[ Map_IsComplement(pNode->p1)];
609 pNode->tArrival[1] = Map_Regular(pNode->p1)->tArrival[!Map_IsComplement(pNode->p1)];
610 continue;
611 }
612
613 // skip primary inputs and secondary nodes if mapping with choices
614 if ( !Map_NodeIsAnd( pNode ) || pNode->pRepr )
615 continue;
616
617 // make sure that at least one non-trival cut is present
618 if ( pNode->pCuts->pNext == NULL )
619 {
620 Extra_ProgressBarStop( pProgress );
621 printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" );
622 return 0;
623 }
624
625 // match negative phase
626 if ( !Map_MatchNodePhase( p, pNode, 0 ) )
627 {
628 Extra_ProgressBarStop( pProgress );
629 return 0;
630 }
631 // match positive phase
632 if ( !Map_MatchNodePhase( p, pNode, 1 ) )
633 {
634 Extra_ProgressBarStop( pProgress );
635 return 0;
636 }
637
638 // make sure that at least one phase is mapped
639 if ( pNode->pCutBest[0] == NULL && pNode->pCutBest[1] == NULL )
640 {
641 printf( "\nError: Could not match both phases of AIG node %d.\n", pNode->Num );
642 printf( "Please make sure that the supergate library has equivalents of AND2 or NAND2.\n" );
643 printf( "If such supergates exist in the library, report a bug.\n" );
644 Extra_ProgressBarStop( pProgress );
645 return 0;
646 }
647
648 // if both phases are assigned, check if one of them can be dropped
649 Map_NodeTryDroppingOnePhase( p, pNode );
650 // set the arrival times of the node using the best cuts
651 Map_NodeTransferArrivalTimes( p, pNode );
652
653 // update the progress bar
654 Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
655 }
656 Extra_ProgressBarStop( pProgress );
657 return 1;
658 }
659
660 ////////////////////////////////////////////////////////////////////////
661 /// END OF FILE ///
662 ////////////////////////////////////////////////////////////////////////
663 ABC_NAMESPACE_IMPL_END
664
665