nwkTiming.c 29.2 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
/**CFile****************************************************************

  FileName    [nwkTiming.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Logic network representation.]

  Synopsis    [Manipulation of timing information.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: nwkTiming.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

***********************************************************************/
Alan Mishchenko committed
20
 
Alan Mishchenko committed
21 22
#include "nwk.h"

23 24 25
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    [Cleans timing information for all nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_ManCleanTiming( Nwk_Man_t * pNtk )
{
    Nwk_Obj_t * pObj;
    int i;
    Nwk_ManForEachObj( pNtk, pObj, i )
    {
        pObj->tArrival = pObj->tSlack = 0.0;
Alan Mishchenko committed
52
        pObj->tRequired = TIM_ETERNITY;
Alan Mishchenko committed
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
    }
}

/**Function*************************************************************

  Synopsis    [Sorts the pins in the decreasing order of delays.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_ManDelayTraceSortPins( Nwk_Obj_t * pNode, int * pPinPerm, float * pPinDelays )
{
    Nwk_Obj_t * pFanin;
    int i, j, best_i, temp;
    // start the trivial permutation and collect pin delays
    Nwk_ObjForEachFanin( pNode, pFanin, i )
    {
        pPinPerm[i] = i;
        pPinDelays[i] = Nwk_ObjArrival(pFanin);
    }
    // selection sort the pins in the decreasible order of delays
    // this order will match the increasing order of LUT input pins
    for ( i = 0; i < Nwk_ObjFaninNum(pNode)-1; i++ )
    {
        best_i = i;
        for ( j = i+1; j < Nwk_ObjFaninNum(pNode); j++ )
            if ( pPinDelays[pPinPerm[j]] > pPinDelays[pPinPerm[best_i]] )
                best_i = j;
        if ( best_i == i )
            continue;
        temp = pPinPerm[i]; 
        pPinPerm[i] = pPinPerm[best_i]; 
        pPinPerm[best_i] = temp;
    }
    // verify
    assert( Nwk_ObjFaninNum(pNode) == 0 || pPinPerm[0] < Nwk_ObjFaninNum(pNode) );
    for ( i = 1; i < Nwk_ObjFaninNum(pNode); i++ )
    {
        assert( pPinPerm[i] < Nwk_ObjFaninNum(pNode) );
        assert( pPinDelays[pPinPerm[i-1]] >= pPinDelays[pPinPerm[i]] );
    }
}

/**Function*************************************************************

Alan Mishchenko committed
102
  Synopsis    [Sorts the pins in the decreasing order of delays.]
Alan Mishchenko committed
103 104 105 106 107 108 109 110

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
111
int Nwk_ManWhereIsPin( Nwk_Obj_t * pFanout, Nwk_Obj_t * pFanin, int * pPinPerm )
Alan Mishchenko committed
112
{
Alan Mishchenko committed
113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
    int i;
    for ( i = 0; i < Nwk_ObjFaninNum(pFanout); i++ )
        if ( Nwk_ObjFanin(pFanout, pPinPerm[i]) == pFanin )
            return i;
    return -1;
}

/**Function*************************************************************

  Synopsis    [Computes the arrival times for the given object.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
float Nwk_NodeComputeArrival( Nwk_Obj_t * pObj, int fUseSorting )
{
    If_Lib_t * pLutLib = pObj->pMan->pLutLib;
Alan Mishchenko committed
134 135 136 137 138
    int pPinPerm[32];
    float pPinDelays[32];
    Nwk_Obj_t * pFanin;
    float tArrival, * pDelays;
    int k;
Alan Mishchenko committed
139 140 141 142 143
    assert( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCi(pObj) || Nwk_ObjIsCo(pObj) );
    if ( Nwk_ObjIsCi(pObj) )
        return Nwk_ObjArrival(pObj);
    if ( Nwk_ObjIsCo(pObj) )
        return Nwk_ObjArrival( Nwk_ObjFanin0(pObj) );
Alan Mishchenko committed
144
    tArrival = -TIM_ETERNITY;
Alan Mishchenko committed
145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
    if ( pLutLib == NULL )
    {
        Nwk_ObjForEachFanin( pObj, pFanin, k )
            if ( tArrival < Nwk_ObjArrival(pFanin) + 1.0 )
                tArrival = Nwk_ObjArrival(pFanin) + 1.0;
    }
    else if ( !pLutLib->fVarPinDelays )
    {
        pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)];
        Nwk_ObjForEachFanin( pObj, pFanin, k )
            if ( tArrival < Nwk_ObjArrival(pFanin) + pDelays[0] )
                tArrival = Nwk_ObjArrival(pFanin) + pDelays[0];
    }
    else
    {
        pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)];
        if ( fUseSorting )
        {
            Nwk_ManDelayTraceSortPins( pObj, pPinPerm, pPinDelays );
            Nwk_ObjForEachFanin( pObj, pFanin, k ) 
                if ( tArrival < Nwk_ObjArrival(Nwk_ObjFanin(pObj,pPinPerm[k])) + pDelays[k] )
                    tArrival = Nwk_ObjArrival(Nwk_ObjFanin(pObj,pPinPerm[k])) + pDelays[k];
        }
        else
        {
            Nwk_ObjForEachFanin( pObj, pFanin, k )
                if ( tArrival < Nwk_ObjArrival(pFanin) + pDelays[k] )
                    tArrival = Nwk_ObjArrival(pFanin) + pDelays[k];
        }
    }
    if ( Nwk_ObjFaninNum(pObj) == 0 )
        tArrival = 0.0;
    return tArrival;
}

/**Function*************************************************************

  Synopsis    [Computes the required times for the given node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
191
float Nwk_NodeComputeRequired( Nwk_Obj_t * pObj, int fUseSorting )
Alan Mishchenko committed
192
{
Alan Mishchenko committed
193
    If_Lib_t * pLutLib = pObj->pMan->pLutLib;
Alan Mishchenko committed
194 195 196
    int pPinPerm[32];
    float pPinDelays[32];
    Nwk_Obj_t * pFanout;
Alan Mishchenko committed
197 198 199 200 201
    float tRequired, tDelay, * pDelays;
    int k, iFanin;
    assert( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCi(pObj) || Nwk_ObjIsCo(pObj) );
    if ( Nwk_ObjIsCo(pObj) )
        return Nwk_ObjRequired(pObj);
Alan Mishchenko committed
202
    tRequired = TIM_ETERNITY;
Alan Mishchenko committed
203 204 205
    if ( pLutLib == NULL )
    {
        Nwk_ObjForEachFanout( pObj, pFanout, k )
Alan Mishchenko committed
206 207 208 209 210
        {
            tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : 1.0;
            if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay )
                tRequired = Nwk_ObjRequired(pFanout) - tDelay;
        }
Alan Mishchenko committed
211 212 213 214 215 216
    }
    else if ( !pLutLib->fVarPinDelays )
    {
        Nwk_ObjForEachFanout( pObj, pFanout, k )
        {
            pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pFanout)];
Alan Mishchenko committed
217 218 219
            tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : pDelays[0];
            if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay )
                tRequired = Nwk_ObjRequired(pFanout) - tDelay;
Alan Mishchenko committed
220 221 222 223 224 225 226 227 228 229
        }
    }
    else
    {
        if ( fUseSorting )
        {
            Nwk_ObjForEachFanout( pObj, pFanout, k ) 
            {
                pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pFanout)];
                Nwk_ManDelayTraceSortPins( pFanout, pPinPerm, pPinDelays );
Alan Mishchenko committed
230 231 232 233 234
                iFanin = Nwk_ManWhereIsPin( pFanout, pObj, pPinPerm );
                assert( Nwk_ObjFanin(pFanout,pPinPerm[iFanin]) == pObj );
                tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : pDelays[iFanin];
                if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay )
                    tRequired = Nwk_ObjRequired(pFanout) - tDelay;
Alan Mishchenko committed
235 236 237 238 239 240 241
            }
        }
        else
        {
            Nwk_ObjForEachFanout( pObj, pFanout, k )
            {
                pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pFanout)];
Alan Mishchenko committed
242 243 244 245 246
                iFanin = Nwk_ObjFindFanin( pFanout, pObj );
                assert( Nwk_ObjFanin(pFanout,iFanin) == pObj );
                tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : pDelays[iFanin];
                if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay )
                    tRequired = Nwk_ObjRequired(pFanout) - tDelay;
Alan Mishchenko committed
247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263
            }
        }
    }
    return tRequired;
}

/**Function*************************************************************

  Synopsis    [Propagates the required times through the given node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
264
float Nwk_NodePropagateRequired( Nwk_Obj_t * pObj, int fUseSorting )
Alan Mishchenko committed
265
{
Alan Mishchenko committed
266
    If_Lib_t * pLutLib = pObj->pMan->pLutLib;
Alan Mishchenko committed
267 268 269
    int pPinPerm[32];
    float pPinDelays[32];
    Nwk_Obj_t * pFanin;
Alan Mishchenko committed
270 271
    float tRequired = 0.0; // Suppress "might be used uninitialized"
    float * pDelays;
Alan Mishchenko committed
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325
    int k;
    assert( Nwk_ObjIsNode(pObj) );
    if ( pLutLib == NULL )
    {
        tRequired = Nwk_ObjRequired(pObj) - (float)1.0;
        Nwk_ObjForEachFanin( pObj, pFanin, k )
            if ( Nwk_ObjRequired(pFanin) > tRequired )
                Nwk_ObjSetRequired( pFanin, tRequired );
    }
    else if ( !pLutLib->fVarPinDelays )
    {
        pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)];
        tRequired = Nwk_ObjRequired(pObj) - pDelays[0];
        Nwk_ObjForEachFanin( pObj, pFanin, k )
            if ( Nwk_ObjRequired(pFanin) > tRequired )
                Nwk_ObjSetRequired( pFanin, tRequired );
    }
    else 
    {
        pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)];
        if ( fUseSorting )
        {
            Nwk_ManDelayTraceSortPins( pObj, pPinPerm, pPinDelays );
            Nwk_ObjForEachFanin( pObj, pFanin, k )
            {
                tRequired = Nwk_ObjRequired(pObj) - pDelays[k];
                if ( Nwk_ObjRequired(Nwk_ObjFanin(pObj,pPinPerm[k])) > tRequired )
                    Nwk_ObjSetRequired( Nwk_ObjFanin(pObj,pPinPerm[k]), tRequired );
            }
        }
        else
        {
            Nwk_ObjForEachFanin( pObj, pFanin, k )
            {
                tRequired = Nwk_ObjRequired(pObj) - pDelays[k];
                if ( Nwk_ObjRequired(pFanin) > tRequired )
                    Nwk_ObjSetRequired( pFanin, tRequired );
            }
        }
    }
    return tRequired;
}

/**Function*************************************************************

  Synopsis    [Computes the delay trace of the given network.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
326
float Nwk_ManDelayTraceLut( Nwk_Man_t * pNtk )
Alan Mishchenko committed
327
{
Alan Mishchenko committed
328
    Vec_Ptr_t * vObjs;
Alan Mishchenko committed
329
    int fUseSorting = 1;
Alan Mishchenko committed
330
    If_Lib_t * pLutLib = pNtk->pLutLib;
Alan Mishchenko committed
331 332 333 334 335 336 337 338 339 340
    Vec_Ptr_t * vNodes;
    Nwk_Obj_t * pObj;
    float tArrival, tRequired, tSlack;
    int i;

    // get the library
    if ( pLutLib && pLutLib->LutMax < Nwk_ManGetFaninMax(pNtk) )
    {
        printf( "The max LUT size (%d) is less than the max fanin count (%d).\n", 
            pLutLib->LutMax, Nwk_ManGetFaninMax(pNtk) );
Alan Mishchenko committed
341
        return -TIM_ETERNITY;
Alan Mishchenko committed
342 343 344 345 346 347 348 349 350 351 352
    }

    // compute the reverse order of all objects
    vNodes = Nwk_ManDfsReverse( pNtk );

    // initialize the arrival times
    Nwk_ManCleanTiming( pNtk );

    // propagate arrival times
    if ( pNtk->pManTime )
        Tim_ManIncrementTravId( pNtk->pManTime );
Alan Mishchenko committed
353 354
//    Nwk_ManForEachObj( pNtk, pObj, i )
    vObjs = Nwk_ManDfs( pNtk );
355
    Vec_PtrForEachEntry( Nwk_Obj_t *, vObjs, pObj, i )
Alan Mishchenko committed
356
    {
Alan Mishchenko committed
357 358
        tArrival = Nwk_NodeComputeArrival( pObj, fUseSorting );
        if ( Nwk_ObjIsCi(pObj) && pNtk->pManTime )
Alan Mishchenko committed
359
            tArrival = Tim_ManGetCiArrival( pNtk->pManTime, pObj->PioId );
360 361
        if ( Nwk_ObjIsCo(pObj) && pNtk->pManTime )
            Tim_ManSetCoArrival( pNtk->pManTime, pObj->PioId, tArrival );
Alan Mishchenko committed
362 363
        Nwk_ObjSetArrival( pObj, tArrival );
    }
Alan Mishchenko committed
364
    Vec_PtrFree( vObjs );
Alan Mishchenko committed
365 366

    // get the latest arrival times
Alan Mishchenko committed
367
    tArrival = -TIM_ETERNITY;
Alan Mishchenko committed
368 369 370 371 372 373 374 375
    Nwk_ManForEachPo( pNtk, pObj, i )
        if ( tArrival < Nwk_ObjArrival(pObj) )
            tArrival = Nwk_ObjArrival(pObj);

    // initialize the required times
    if ( pNtk->pManTime )
    {
        Tim_ManIncrementTravId( pNtk->pManTime );
Alan Mishchenko committed
376
        Tim_ManSetCoRequiredAll( pNtk->pManTime, tArrival );
Alan Mishchenko committed
377 378
    }
    else
Alan Mishchenko committed
379 380
    {
        Nwk_ManForEachCo( pNtk, pObj, i )
Alan Mishchenko committed
381
            Nwk_ObjSetRequired( pObj, tArrival );
Alan Mishchenko committed
382
    }
Alan Mishchenko committed
383 384

    // propagate the required times
385
    Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i )
Alan Mishchenko committed
386 387 388
    {
        if ( Nwk_ObjIsNode(pObj) )
        {
Alan Mishchenko committed
389
            Nwk_NodePropagateRequired( pObj, fUseSorting );
Alan Mishchenko committed
390 391 392 393
        }
        else if ( Nwk_ObjIsCi(pObj) )
        {
            if ( pNtk->pManTime )
Alan Mishchenko committed
394
                Tim_ManSetCiRequired( pNtk->pManTime, pObj->PioId, Nwk_ObjRequired(pObj) );
Alan Mishchenko committed
395 396 397 398
        }
        else if ( Nwk_ObjIsCo(pObj) )
        {
            if ( pNtk->pManTime )
Alan Mishchenko committed
399
            {
Alan Mishchenko committed
400
                tRequired = Tim_ManGetCoRequired( pNtk->pManTime, pObj->PioId );
Alan Mishchenko committed
401 402 403 404
                Nwk_ObjSetRequired( pObj, tRequired );
            }
            if ( Nwk_ObjRequired(Nwk_ObjFanin0(pObj)) > Nwk_ObjRequired(pObj) )
                Nwk_ObjSetRequired( Nwk_ObjFanin0(pObj), Nwk_ObjRequired(pObj) );
Alan Mishchenko committed
405 406 407 408
        }

        // set slack for this object
        tSlack = Nwk_ObjRequired(pObj) - Nwk_ObjArrival(pObj);
Alan Mishchenko committed
409
        assert( tSlack + 0.01 > 0.0 );
Alan Mishchenko committed
410 411 412 413 414 415 416 417
        Nwk_ObjSetSlack( pObj, tSlack < 0.0 ? 0.0 : tSlack );
    }
    Vec_PtrFree( vNodes );
    return tArrival;
}

/**Function*************************************************************

Alan Mishchenko committed
418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433
  Synopsis    [Computes the arrival times for the given node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Nwk_ManVerifyTiming(  Nwk_Man_t * pNtk )
{
    Nwk_Obj_t * pObj;
    float tArrival, tRequired;
    int i;
    Nwk_ManForEachObj( pNtk, pObj, i )
    {
Alan Mishchenko committed
434
        if ( Nwk_ObjIsCi(pObj) && Nwk_ObjFanoutNum(pObj) == 0 )
Alan Mishchenko committed
435
            continue;
Alan Mishchenko committed
436 437 438
        tArrival = Nwk_NodeComputeArrival( pObj, 1 );
        tRequired = Nwk_NodeComputeRequired( pObj, 1 );
        if ( !Nwk_ManTimeEqual( tArrival, Nwk_ObjArrival(pObj), (float)0.01 ) )
Alan Mishchenko committed
439 440
            printf( "Nwk_ManVerifyTiming(): Object %d has different arrival time (%.2f) from computed (%.2f).\n", 
                pObj->Id, Nwk_ObjArrival(pObj), tArrival );
Alan Mishchenko committed
441
        if ( !Nwk_ManTimeEqual( tRequired, Nwk_ObjRequired(pObj), (float)0.01 ) )
Alan Mishchenko committed
442 443
            printf( "Nwk_ManVerifyTiming(): Object %d has different required time (%.2f) from computed (%.2f).\n", 
                pObj->Id, Nwk_ObjRequired(pObj), tRequired );
Alan Mishchenko committed
444 445 446 447 448 449
    }
    return 1;
}

/**Function*************************************************************

Alan Mishchenko committed
450 451 452 453 454 455 456 457 458
  Synopsis    [Prints the delay trace for the given network.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
459
void Nwk_ManDelayTracePrint( Nwk_Man_t * pNtk )
Alan Mishchenko committed
460
{
Alan Mishchenko committed
461
    If_Lib_t * pLutLib = pNtk->pLutLib;
Alan Mishchenko committed
462 463 464 465 466 467 468 469 470 471 472
    Nwk_Obj_t * pNode;
    int i, Nodes, * pCounters;
    float tArrival, tDelta, nSteps, Num;
    // get the library
    if ( pLutLib && pLutLib->LutMax < Nwk_ManGetFaninMax(pNtk) )
    {
        printf( "The max LUT size (%d) is less than the max fanin count (%d).\n", 
            pLutLib->LutMax, Nwk_ManGetFaninMax(pNtk) );
        return;
    }
    // decide how many steps
Alan Mishchenko committed
473
    nSteps = pLutLib ? 20 : Nwk_ManLevelMax(pNtk);
Alan Mishchenko committed
474
    pCounters = ABC_ALLOC( int, nSteps + 1 );
Alan Mishchenko committed
475 476
    memset( pCounters, 0, sizeof(int)*(nSteps + 1) );
    // perform delay trace
Alan Mishchenko committed
477
    tArrival = Nwk_ManDelayTraceLut( pNtk );
Alan Mishchenko committed
478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498
    tDelta = tArrival / nSteps;
    // count how many nodes have slack in the corresponding intervals
    Nwk_ManForEachNode( pNtk, pNode, i )
    {
        if ( Nwk_ObjFaninNum(pNode) == 0 )
            continue;
        Num = Nwk_ObjSlack(pNode) / tDelta;
        if ( Num > nSteps )
            continue;
        assert( Num >=0 && Num <= nSteps );
        pCounters[(int)Num]++;
    }
    // print the results
    printf( "Max delay = %6.2f. Delay trace using %s model:\n", tArrival, pLutLib? "LUT library" : "unit-delay" );
    Nodes = 0;
    for ( i = 0; i < nSteps; i++ )
    {
        Nodes += pCounters[i];
        printf( "%3d %s : %5d  (%6.2f %%)\n", pLutLib? 5*(i+1) : i+1, 
            pLutLib? "%":"lev", Nodes, 100.0*Nodes/Nwk_ManNodeNum(pNtk) );
    }
Alan Mishchenko committed
499
    ABC_FREE( pCounters );
Alan Mishchenko committed
500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523
}


/**Function*************************************************************

  Synopsis    [Inserts node into the queue of nodes sorted by level.]

  Description [The inserted node should not go before the current position 
  given by iCurrent. If the arrival times are computed, the nodes are sorted
  in the increasing order of levels. If the required times are computed, 
  the nodes are sorted in the decreasing order of levels.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_NodeUpdateAddToQueue( Vec_Ptr_t * vQueue, Nwk_Obj_t * pObj, int iCurrent, int fArrival )
{
    Nwk_Obj_t * pTemp1, * pTemp2;
    int i;
    Vec_PtrPush( vQueue, pObj );
    for ( i = Vec_PtrSize(vQueue) - 1; i > iCurrent + 1; i-- )
    {
524 525
        pTemp1 = (Nwk_Obj_t *)vQueue->pArray[i];
        pTemp2 = (Nwk_Obj_t *)vQueue->pArray[i-1];
Alan Mishchenko committed
526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541
        if ( fArrival )
        {
            if ( Nwk_ObjLevel(pTemp2) <= Nwk_ObjLevel(pTemp1) )
                break;
        }
        else
        {
            if ( Nwk_ObjLevel(pTemp2) >= Nwk_ObjLevel(pTemp1) )
                break;
        }
        vQueue->pArray[i-1] = pTemp1;
        vQueue->pArray[i]   = pTemp2;
    }
    // verification
    for ( i = iCurrent + 1; i < Vec_PtrSize(vQueue) - 1; i++ )
    {
542 543
        pTemp1 = (Nwk_Obj_t *)vQueue->pArray[i];
        pTemp2 = (Nwk_Obj_t *)vQueue->pArray[i+1];
Alan Mishchenko committed
544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561
        if ( fArrival )
            assert( Nwk_ObjLevel(pTemp1) <= Nwk_ObjLevel(pTemp2) );
        else
            assert( Nwk_ObjLevel(pTemp1) >= Nwk_ObjLevel(pTemp2) );
    }
}

/**Function*************************************************************

  Synopsis    [Incrementally updates arrival times of the node.]

  Description [Supports variable-pin delay model and white-boxes.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
562
void Nwk_NodeUpdateArrival( Nwk_Obj_t * pObj )
Alan Mishchenko committed
563 564 565
{
    Tim_Man_t * pManTime = pObj->pMan->pManTime;
    Vec_Ptr_t * vQueue = pObj->pMan->vTemp;
Alan Mishchenko committed
566 567
    Nwk_Obj_t * pTemp;
    Nwk_Obj_t * pNext = NULL; // Suppress "might be used uninitialized"
Alan Mishchenko committed
568
    float tArrival;
Alan Mishchenko committed
569
    int iCur, k, iBox, iTerm1, nTerms;
Alan Mishchenko committed
570
    assert( Nwk_ObjIsNode(pObj) );
Alan Mishchenko committed
571 572 573
    // verify the arrival time
    tArrival = Nwk_NodeComputeArrival( pObj, 1 );
    assert( Nwk_ManTimeLess( tArrival, Nwk_ObjRequired(pObj), (float)0.01 ) );
Alan Mishchenko committed
574 575 576 577 578
    // initialize the queue with the node
    Vec_PtrClear( vQueue );
    Vec_PtrPush( vQueue, pObj );
    pObj->MarkA = 1;
    // process objects
Alan Mishchenko committed
579 580
    if ( pManTime )
        Tim_ManIncrementTravId( pManTime );
581
    Vec_PtrForEachEntry( Nwk_Obj_t *, vQueue, pTemp, iCur )
Alan Mishchenko committed
582 583
    {
        pTemp->MarkA = 0;
Alan Mishchenko committed
584 585
        tArrival = Nwk_NodeComputeArrival( pTemp, 1 );
        if ( Nwk_ObjIsCi(pTemp) && pManTime )
Alan Mishchenko committed
586
            tArrival = Tim_ManGetCiArrival( pManTime, pTemp->PioId );
Alan Mishchenko committed
587
        if ( Nwk_ManTimeEqual( tArrival, Nwk_ObjArrival(pTemp), (float)0.01 ) )
Alan Mishchenko committed
588 589 590
            continue;
        Nwk_ObjSetArrival( pTemp, tArrival );
        // add the fanouts to the queue
Alan Mishchenko committed
591 592 593 594
        if ( Nwk_ObjIsCo(pTemp) )
        {
            if ( pManTime )
            {
Alan Mishchenko committed
595 596
                iBox = Tim_ManBoxForCo( pManTime, pTemp->PioId );
                if ( iBox >= 0 ) // this CO is an input of the box
Alan Mishchenko committed
597
                {
Alan Mishchenko committed
598 599 600 601 602
                    // it may happen that a box-input (CO) was already marked as visited
                    // when some other box-input of the same box was visited - here we undo this
                    if ( Tim_ManIsCoTravIdCurrent( pManTime, pTemp->PioId ) )
                        Tim_ManSetPreviousTravIdBoxInputs( pManTime, iBox );
                    Tim_ManSetCoArrival( pManTime, pTemp->PioId, tArrival );
Alan Mishchenko committed
603
                    Tim_ManSetCurrentTravIdBoxInputs( pManTime, iBox );
Alan Mishchenko committed
604 605
                    iTerm1 = Tim_ManBoxOutputFirst( pManTime, iBox );
                    nTerms = Tim_ManBoxOutputNum( pManTime, iBox );
Alan Mishchenko committed
606
                    for ( k = 0; k < nTerms; k++ )
Alan Mishchenko committed
607
                    {
Alan Mishchenko committed
608
                        pNext = Nwk_ManCi(pNext->pMan, iTerm1 + k);
Alan Mishchenko committed
609 610
                        if ( pNext->MarkA )
                            continue;
Alan Mishchenko committed
611
                        Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 );
Alan Mishchenko committed
612 613 614 615 616 617
                        pNext->MarkA = 1;
                    }
                }
            }
        }
        else
Alan Mishchenko committed
618
        {
Alan Mishchenko committed
619
            Nwk_ObjForEachFanout( pTemp, pNext, k )
Alan Mishchenko committed
620
            {
Alan Mishchenko committed
621 622
                if ( pNext->MarkA )
                    continue;
Alan Mishchenko committed
623
                Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 );
Alan Mishchenko committed
624
                pNext->MarkA = 1;
Alan Mishchenko committed
625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640
            }
        }
    }
}

/**Function*************************************************************

  Synopsis    [Incrementally updates required times of the node.]

  Description [Supports variable-pin delay model and white-boxes.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
641
void Nwk_NodeUpdateRequired( Nwk_Obj_t * pObj )
Alan Mishchenko committed
642 643 644
{
    Tim_Man_t * pManTime = pObj->pMan->pManTime;
    Vec_Ptr_t * vQueue = pObj->pMan->vTemp;
Alan Mishchenko committed
645 646
    Nwk_Obj_t * pTemp;
    Nwk_Obj_t * pNext = NULL; // Suppress "might be used uninitialized"
Alan Mishchenko committed
647
    float tRequired;
Alan Mishchenko committed
648
    int iCur, k, iBox, iTerm1, nTerms;
Alan Mishchenko committed
649 650
    assert( Nwk_ObjIsNode(pObj) );
    // make sure the node's required time remained the same
Alan Mishchenko committed
651 652 653
    tRequired = Nwk_NodeComputeRequired( pObj, 1 );
    assert( Nwk_ManTimeEqual( tRequired, Nwk_ObjRequired(pObj), (float)0.01 ) );
    // initialize the queue with the node's faninsa and the old node's fanins
Alan Mishchenko committed
654 655 656 657 658 659 660 661 662
    Vec_PtrClear( vQueue );
    Nwk_ObjForEachFanin( pObj, pNext, k )
    {
        if ( pNext->MarkA )
            continue;
        Nwk_NodeUpdateAddToQueue( vQueue, pNext, -1, 0 );
        pNext->MarkA = 1;
    }
    // process objects
Alan Mishchenko committed
663 664
    if ( pManTime )
        Tim_ManIncrementTravId( pManTime );
665
    Vec_PtrForEachEntry( Nwk_Obj_t *, vQueue, pTemp, iCur )
Alan Mishchenko committed
666 667
    {
        pTemp->MarkA = 0;
Alan Mishchenko committed
668 669
        tRequired = Nwk_NodeComputeRequired( pTemp, 1 );
        if ( Nwk_ObjIsCo(pTemp) && pManTime )
Alan Mishchenko committed
670
            tRequired = Tim_ManGetCoRequired( pManTime, pTemp->PioId );
Alan Mishchenko committed
671
        if ( Nwk_ManTimeEqual( tRequired, Nwk_ObjRequired(pTemp), (float)0.01 ) )
Alan Mishchenko committed
672 673
            continue;
        Nwk_ObjSetRequired( pTemp, tRequired );
Alan Mishchenko committed
674
        // add the fanins to the queue
Alan Mishchenko committed
675
        if ( Nwk_ObjIsCi(pTemp) )
Alan Mishchenko committed
676
        {
Alan Mishchenko committed
677 678
            if ( pManTime )
            {
Alan Mishchenko committed
679 680
                iBox = Tim_ManBoxForCi( pManTime, pTemp->PioId );
                if ( iBox >= 0 ) // this CI is an output of the box
Alan Mishchenko committed
681
                {
Alan Mishchenko committed
682 683 684 685 686
                    // it may happen that a box-output (CI) was already marked as visited
                    // when some other box-output of the same box was visited - here we undo this
                    if ( Tim_ManIsCiTravIdCurrent( pManTime, pTemp->PioId ) )
                        Tim_ManSetPreviousTravIdBoxOutputs( pManTime, iBox );
                    Tim_ManSetCiRequired( pManTime, pTemp->PioId, tRequired );
Alan Mishchenko committed
687
                    Tim_ManSetCurrentTravIdBoxOutputs( pManTime, iBox );
Alan Mishchenko committed
688 689
                    iTerm1 = Tim_ManBoxInputFirst( pManTime, iBox );
                    nTerms = Tim_ManBoxInputNum( pManTime, iBox );
Alan Mishchenko committed
690
                    for ( k = 0; k < nTerms; k++ )
Alan Mishchenko committed
691
                    {
Alan Mishchenko committed
692
                        pNext = Nwk_ManCo(pNext->pMan, iTerm1 + k);
Alan Mishchenko committed
693 694
                        if ( pNext->MarkA )
                            continue;
Alan Mishchenko committed
695
                        Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 0 );
Alan Mishchenko committed
696 697 698 699 700 701 702 703 704 705 706
                        pNext->MarkA = 1;
                    }
                }
            }
        }
        else
        {
            Nwk_ObjForEachFanin( pTemp, pNext, k )
            {
                if ( pNext->MarkA )
                    continue;
Alan Mishchenko committed
707
                Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 0 );
Alan Mishchenko committed
708 709
                pNext->MarkA = 1;
            }
Alan Mishchenko committed
710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726
        }
    }
}

/**Function*************************************************************

  Synopsis    [Computes the level of the node using its fanin levels.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Nwk_ObjLevelNew( Nwk_Obj_t * pObj )
{
Alan Mishchenko committed
727
    Tim_Man_t * pManTime = pObj->pMan->pManTime;
Alan Mishchenko committed
728
    Nwk_Obj_t * pFanin;
Alan Mishchenko committed
729
    int i, iBox, iTerm1, nTerms, Level = 0;
Alan Mishchenko committed
730
    if ( Nwk_ObjIsCi(pObj) || Nwk_ObjIsLatch(pObj) )
Alan Mishchenko committed
731 732 733 734
    {
        if ( pManTime )
        {
            iBox = Tim_ManBoxForCi( pManTime, pObj->PioId );
Alan Mishchenko committed
735
            if ( iBox >= 0 ) // this CI is an output of the box
Alan Mishchenko committed
736 737 738 739 740 741
            {
                iTerm1 = Tim_ManBoxInputFirst( pManTime, iBox );
                nTerms = Tim_ManBoxInputNum( pManTime, iBox );
                for ( i = 0; i < nTerms; i++ )
                {
                    pFanin = Nwk_ManCo(pObj->pMan, iTerm1 + i);
742
                    Level = Abc_MaxInt( Level, Nwk_ObjLevel(pFanin) );
Alan Mishchenko committed
743 744 745 746 747 748
                }
                Level++;
            }
        }
        return Level;
    }
Alan Mishchenko committed
749 750
    assert( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCo(pObj) );
    Nwk_ObjForEachFanin( pObj, pFanin, i )
751
        Level = Abc_MaxInt( Level, Nwk_ObjLevel(pFanin) );
Alan Mishchenko committed
752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767
    return Level + (Nwk_ObjIsNode(pObj) && Nwk_ObjFaninNum(pObj) > 0);
}

/**Function*************************************************************

  Synopsis    [Incrementally updates level of the nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_ManUpdateLevel( Nwk_Obj_t * pObj )
{
Alan Mishchenko committed
768
    Tim_Man_t * pManTime = pObj->pMan->pManTime;
Alan Mishchenko committed
769
    Vec_Ptr_t * vQueue = pObj->pMan->vTemp;
Alan Mishchenko committed
770 771
    Nwk_Obj_t * pTemp;
    Nwk_Obj_t * pNext = NULL; // Suppress "might be used uninitialized"
Alan Mishchenko committed
772
    int LevelNew, iCur, k, iBox, iTerm1, nTerms;
Alan Mishchenko committed
773 774 775 776 777 778
    assert( Nwk_ObjIsNode(pObj) );
    // initialize the queue with the node
    Vec_PtrClear( vQueue );
    Vec_PtrPush( vQueue, pObj );
    pObj->MarkA = 1;
    // process objects
779
    Vec_PtrForEachEntry( Nwk_Obj_t *, vQueue, pTemp, iCur )
Alan Mishchenko committed
780 781 782 783 784 785 786
    {
        pTemp->MarkA = 0;
        LevelNew = Nwk_ObjLevelNew( pTemp );
        if ( LevelNew == Nwk_ObjLevel(pTemp) )
            continue;
        Nwk_ObjSetLevel( pTemp, LevelNew );
        // add the fanouts to the queue
Alan Mishchenko committed
787 788 789 790
        if ( Nwk_ObjIsCo(pTemp) )
        {
            if ( pManTime )
            {
Alan Mishchenko committed
791
                iBox = Tim_ManBoxForCo( pManTime, pTemp->PioId );
Alan Mishchenko committed
792 793
                if ( iBox >= 0 ) // this is not a true PO
                {
Alan Mishchenko committed
794
                    Tim_ManSetCurrentTravIdBoxInputs( pManTime, iBox );
Alan Mishchenko committed
795 796
                    iTerm1 = Tim_ManBoxOutputFirst( pManTime, iBox );
                    nTerms = Tim_ManBoxOutputNum( pManTime, iBox );
Alan Mishchenko committed
797
                    for ( k = 0; k < nTerms; k++ )
Alan Mishchenko committed
798
                    {
Alan Mishchenko committed
799
                        pNext = Nwk_ManCi(pNext->pMan, iTerm1 + k);
Alan Mishchenko committed
800 801
                        if ( pNext->MarkA )
                            continue;
Alan Mishchenko committed
802
                        Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 );
Alan Mishchenko committed
803 804 805 806 807 808
                        pNext->MarkA = 1;
                    }
                }
            }
        }
        else
Alan Mishchenko committed
809
        {
Alan Mishchenko committed
810
            Nwk_ObjForEachFanout( pTemp, pNext, k )
Alan Mishchenko committed
811
            {
Alan Mishchenko committed
812 813
                if ( pNext->MarkA )
                    continue;
Alan Mishchenko committed
814
                Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 );
Alan Mishchenko committed
815
                pNext->MarkA = 1;
Alan Mishchenko committed
816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831
            }
        }
    }
}

/**Function*************************************************************

  Synopsis    [Computes the level of the node using its fanin levels.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
832
int Nwk_ManVerifyLevel( Nwk_Man_t * pNtk )
Alan Mishchenko committed
833 834 835 836 837 838 839 840 841 842 843 844 845
{
    Nwk_Obj_t * pObj;
    int LevelNew, i;
    Nwk_ManForEachObj( pNtk, pObj, i )
    {
        assert( pObj->MarkA == 0 );
        LevelNew = Nwk_ObjLevelNew( pObj );
        if ( Nwk_ObjLevel(pObj) != LevelNew )
        {
            printf( "Object %6d: Mismatch betweeh levels: Actual = %d. Correct = %d.\n", 
                i, Nwk_ObjLevel(pObj), LevelNew );
        }
    }
Alan Mishchenko committed
846
    return 1;
Alan Mishchenko committed
847 848 849 850 851 852 853 854 855 856 857 858 859 860 861
}

/**Function*************************************************************

  Synopsis    [Replaces the node and incrementally updates levels.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_ManUpdate( Nwk_Obj_t * pObj, Nwk_Obj_t * pObjNew, Vec_Vec_t * vLevels )
{
Alan Mishchenko committed
862 863 864 865 866 867
    assert( pObj->pMan == pObjNew->pMan );
    assert( pObj != pObjNew );
    assert( Nwk_ObjFanoutNum(pObj) > 0 );
    assert( Nwk_ObjIsNode(pObj) && !Nwk_ObjIsCo(pObjNew) );
    // transfer fanouts to the old node
    Nwk_ObjTransferFanout( pObj, pObjNew );
Alan Mishchenko committed
868 869 870 871 872 873 874
    // transfer the timing information
    // (this is needed because updating level happens if the level has changed;
    // when we set the old level, it will be recomputed by the level updating
    // procedure, which will update level of other nodes if there is a difference)
    pObjNew->Level = pObj->Level;
    pObjNew->tArrival = pObj->tArrival;
    pObjNew->tRequired = pObj->tRequired;
Alan Mishchenko committed
875
    // update required times of the old fanins
Alan Mishchenko committed
876
    pObj->tRequired = TIM_ETERNITY;
Alan Mishchenko committed
877 878 879 880
    Nwk_NodeUpdateRequired( pObj );
    // remove the old node
    Nwk_ManDeleteNode_rec( pObj );
    // update the information of the new node
Alan Mishchenko committed
881
    Nwk_ManUpdateLevel( pObjNew );
Alan Mishchenko committed
882 883 884
    Nwk_NodeUpdateArrival( pObjNew );
    Nwk_NodeUpdateRequired( pObjNew );
//Nwk_ManVerifyTiming( pObjNew->pMan );
Alan Mishchenko committed
885 886 887 888 889 890 891 892
}


////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


893 894
ABC_NAMESPACE_IMPL_END