src/aig/aig/aigTiming.c File Reference

#include "aig.h"
Include dependency graph for aigTiming.c:

Go to the source code of this file.

Functions

static int Aig_ObjReverseLevel (Aig_Man_t *p, Aig_Obj_t *pObj)
static void Aig_ObjSetReverseLevel (Aig_Man_t *p, Aig_Obj_t *pObj, int LevelR)
void Aig_ObjClearReverseLevel (Aig_Man_t *p, Aig_Obj_t *pObj)
int Aig_ObjRequiredLevel (Aig_Man_t *p, Aig_Obj_t *pObj)
int Aig_ObjReverseLevelNew (Aig_Man_t *p, Aig_Obj_t *pObj)
void Aig_ManStartReverseLevels (Aig_Man_t *p, int nMaxLevelIncrease)
void Aig_ManStopReverseLevels (Aig_Man_t *p)
void Aig_ManUpdateLevel (Aig_Man_t *p, Aig_Obj_t *pObjNew)
void Aig_ManUpdateReverseLevel (Aig_Man_t *p, Aig_Obj_t *pObjNew)
void Aig_ManVerifyLevel (Aig_Man_t *p)
void Aig_ManVerifyReverseLevel (Aig_Man_t *p)

Function Documentation

void Aig_ManStartReverseLevels ( Aig_Man_t *  p,
int  nMaxLevelIncrease 
)

Function*************************************************************

Synopsis [Prepares for the computation of required levels.]

Description [This procedure should be called before the required times are used. It starts internal data structures, which records the level from the COs of the network nodes in reverse topologogical order.]

SideEffects []

SeeAlso []

Definition at line 139 of file aigTiming.c.

00140 {
00141     Vec_Ptr_t * vNodes;
00142     Aig_Obj_t * pObj;
00143     int i;
00144     assert( p->pFanData != NULL );
00145     assert( p->vLevelR == NULL );
00146     // remember the maximum number of direct levels
00147     p->nLevelMax = Aig_ManLevels(p) + nMaxLevelIncrease;
00148     // start the reverse levels
00149     p->vLevelR = Vec_IntAlloc( 0 );
00150     Vec_IntFill( p->vLevelR, Aig_ManObjNumMax(p), 0 );
00151     // compute levels in reverse topological order
00152     vNodes = Aig_ManDfsReverse( p );
00153     Vec_PtrForEachEntry( vNodes, pObj, i )
00154     {
00155         assert( pObj->fMarkA == 0 );
00156         Aig_ObjSetReverseLevel( p, pObj, Aig_ObjReverseLevelNew(p, pObj) );
00157     }
00158     Vec_PtrFree( vNodes );
00159 }

void Aig_ManStopReverseLevels ( Aig_Man_t *  p  ) 

Function*************************************************************

Synopsis [Cleans the data structures used to compute required levels.]

Description []

SideEffects []

SeeAlso []

Definition at line 172 of file aigTiming.c.

00173 {
00174     assert( p->vLevelR != NULL );
00175     Vec_IntFree( p->vLevelR );
00176     p->vLevelR = NULL;
00177     p->nLevelMax = 0;
00178 
00179 }

void Aig_ManUpdateLevel ( Aig_Man_t *  p,
Aig_Obj_t *  pObjNew 
)

Function*************************************************************

Synopsis [Incrementally updates level of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 192 of file aigTiming.c.

00193 {
00194     Aig_Obj_t * pFanout, * pTemp;
00195     int iFanout = -1, LevelOld, Lev, k, m;
00196     assert( p->pFanData != NULL );
00197     assert( Aig_ObjIsNode(pObjNew) );
00198     // allocate level if needed
00199     if ( p->vLevels == NULL )
00200         p->vLevels = Vec_VecAlloc( Aig_ManLevels(p) + 8 );
00201     // check if level has changed
00202     LevelOld = Aig_ObjLevel(pObjNew);
00203     if ( LevelOld == Aig_ObjLevelNew(pObjNew) )
00204         return;
00205     // start the data structure for level update
00206     // we cannot fail to visit a node when using this structure because the 
00207     // nodes are stored by their _old_ levels, which are assumed to be correct
00208     Vec_VecClear( p->vLevels );
00209     Vec_VecPush( p->vLevels, LevelOld, pObjNew );
00210     pObjNew->fMarkA = 1;
00211     // recursively update level
00212     Vec_VecForEachEntryStart( p->vLevels, pTemp, Lev, k, LevelOld )
00213     {
00214         pTemp->fMarkA = 0;
00215         assert( Aig_ObjLevel(pTemp) == Lev );
00216         pTemp->Level = Aig_ObjLevelNew(pTemp);
00217         // if the level did not change, no need to check the fanout levels
00218         if ( Aig_ObjLevel(pTemp) == Lev )
00219             continue;
00220         // schedule fanout for level update
00221         Aig_ObjForEachFanout( p, pTemp, pFanout, iFanout, m )
00222         {
00223             if ( Aig_ObjIsNode(pFanout) && !pFanout->fMarkA )
00224             {
00225                 assert( Aig_ObjLevel(pFanout) >= Lev );
00226                 Vec_VecPush( p->vLevels, Aig_ObjLevel(pFanout), pFanout );
00227                 pFanout->fMarkA = 1;
00228             }
00229         }
00230     }
00231 }

void Aig_ManUpdateReverseLevel ( Aig_Man_t *  p,
Aig_Obj_t *  pObjNew 
)

Function*************************************************************

Synopsis [Incrementally updates level of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 244 of file aigTiming.c.

00245 {
00246     Aig_Obj_t * pFanin, * pTemp;
00247     int LevelOld, LevFanin, Lev, k;
00248     assert( p->vLevelR != NULL );
00249     assert( Aig_ObjIsNode(pObjNew) );
00250     // allocate level if needed
00251     if ( p->vLevels == NULL )
00252         p->vLevels = Vec_VecAlloc( Aig_ManLevels(p) + 8 );
00253     // check if level has changed
00254     LevelOld = Aig_ObjReverseLevel(p, pObjNew);
00255     if ( LevelOld == Aig_ObjReverseLevelNew(p, pObjNew) )
00256         return;
00257     // start the data structure for level update
00258     // we cannot fail to visit a node when using this structure because the 
00259     // nodes are stored by their _old_ levels, which are assumed to be correct
00260     Vec_VecClear( p->vLevels );
00261     Vec_VecPush( p->vLevels, LevelOld, pObjNew );
00262     pObjNew->fMarkA = 1;
00263     // recursively update level
00264     Vec_VecForEachEntryStart( p->vLevels, pTemp, Lev, k, LevelOld )
00265     {
00266         pTemp->fMarkA = 0;
00267         LevelOld = Aig_ObjReverseLevel(p, pTemp); 
00268         assert( LevelOld == Lev );
00269         Aig_ObjSetReverseLevel( p, pTemp, Aig_ObjReverseLevelNew(p, pTemp) );
00270         // if the level did not change, to need to check the fanout levels
00271         if ( Aig_ObjReverseLevel(p, pTemp) == Lev )
00272             continue;
00273         // schedule fanins for level update
00274         pFanin = Aig_ObjFanin0(pTemp);
00275         if ( Aig_ObjIsNode(pFanin) && !pFanin->fMarkA )
00276         {
00277             LevFanin = Aig_ObjReverseLevel( p, pFanin );
00278             assert( LevFanin >= Lev );
00279             Vec_VecPush( p->vLevels, LevFanin, pFanin );
00280             pFanin->fMarkA = 1;
00281         }
00282         pFanin = Aig_ObjFanin1(pTemp);
00283         if ( Aig_ObjIsNode(pFanin) && !pFanin->fMarkA )
00284         {
00285             LevFanin = Aig_ObjReverseLevel( p, pFanin );
00286             assert( LevFanin >= Lev );
00287             Vec_VecPush( p->vLevels, LevFanin, pFanin );
00288             pFanin->fMarkA = 1;
00289         }
00290     }
00291 }

void Aig_ManVerifyLevel ( Aig_Man_t *  p  ) 

Function*************************************************************

Synopsis [Verifies direct level of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 304 of file aigTiming.c.

00305 {
00306     Aig_Obj_t * pObj;
00307     int i, Counter = 0;
00308     assert( p->pFanData );
00309     Aig_ManForEachNode( p, pObj, i )
00310         if ( Aig_ObjLevel(pObj) != Aig_ObjLevelNew(pObj) )
00311         {
00312             printf( "Level of node %6d should be %4d instead of %4d.\n", 
00313                 pObj->Id, Aig_ObjLevelNew(pObj), Aig_ObjLevel(pObj) );
00314             Counter++;
00315         }
00316     if ( Counter )
00317     printf( "Levels of %d nodes are incorrect.\n", Counter );
00318 }

void Aig_ManVerifyReverseLevel ( Aig_Man_t *  p  ) 

Function*************************************************************

Synopsis [Verifies reverse level of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 331 of file aigTiming.c.

00332 {
00333     Aig_Obj_t * pObj;
00334     int i, Counter = 0;
00335     assert( p->vLevelR );
00336     Aig_ManForEachNode( p, pObj, i )
00337         if ( Aig_ObjLevel(pObj) != Aig_ObjLevelNew(pObj) )
00338         {
00339             printf( "Reverse level of node %6d should be %4d instead of %4d.\n", 
00340                 pObj->Id, Aig_ObjReverseLevelNew(p, pObj), Aig_ObjReverseLevel(p, pObj) );
00341             Counter++;
00342         }
00343     if ( Counter )
00344     printf( "Reverse levels of %d nodes are incorrect.\n", Counter );
00345 }

void Aig_ObjClearReverseLevel ( Aig_Man_t *  p,
Aig_Obj_t *  pObj 
)

Function*************************************************************

Synopsis [Resets reverse level of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 80 of file aigTiming.c.

00081 {
00082     Aig_ObjSetReverseLevel( p, pObj, 0 );
00083 }

int Aig_ObjRequiredLevel ( Aig_Man_t *  p,
Aig_Obj_t *  pObj 
)

Function*************************************************************

Synopsis [Returns required level of the node.]

Description [Converts the reverse levels of the node into its required level as follows: ReqLevel(Node) = MaxLevels(Ntk) + 1 - LevelR(Node).]

SideEffects []

SeeAlso []

Definition at line 97 of file aigTiming.c.

00098 {
00099     assert( p->vLevelR );
00100     return p->nLevelMax + 1 - Aig_ObjReverseLevel(p, pObj);
00101 }

static int Aig_ObjReverseLevel ( Aig_Man_t *  p,
Aig_Obj_t *  pObj 
) [inline, static]

CFile****************************************************************

FileName [aigTiming.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [AIG package.]

Synopsis [Incremental updating of direct/reverse AIG levels.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id
aigTiming.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

] DECLARATIONS /// FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Returns the reverse level of the node.]

Description [The reverse level is the level of the node in reverse topological order, starting from the COs.]

SideEffects []

SeeAlso []

Definition at line 43 of file aigTiming.c.

00044 {
00045     assert( p->vLevelR );
00046     Vec_IntFillExtra( p->vLevelR, pObj->Id + 1, 0 );
00047     return Vec_IntEntry(p->vLevelR, pObj->Id);
00048 }

int Aig_ObjReverseLevelNew ( Aig_Man_t *  p,
Aig_Obj_t *  pObj 
)

Function*************************************************************

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

Description []

SideEffects []

SeeAlso []

Definition at line 114 of file aigTiming.c.

00115 {
00116     Aig_Obj_t * pFanout;
00117     int i, iFanout = -1, LevelCur, Level = 0;
00118     Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, i )
00119     {
00120         LevelCur = Aig_ObjReverseLevel( p, pFanout );
00121         Level = AIG_MAX( Level, LevelCur );
00122     }
00123     return Level + 1;
00124 }

static void Aig_ObjSetReverseLevel ( Aig_Man_t *  p,
Aig_Obj_t *  pObj,
int  LevelR 
) [inline, static]

Function*************************************************************

Synopsis [Sets the reverse level of the node.]

Description [The reverse level is the level of the node in reverse topological order, starting from the COs.]

SideEffects []

SeeAlso []

Definition at line 62 of file aigTiming.c.

00063 {
00064     assert( p->vLevelR );
00065     Vec_IntFillExtra( p->vLevelR, pObj->Id + 1, 0 );
00066     Vec_IntWriteEntry( p->vLevelR, pObj->Id, LevelR );
00067 }

Generated on Tue Jan 5 12:18:12 2010 for abc70930 by  doxygen 1.6.1