abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
aigTiming.c File Reference
#include "aig.h"

Go to the source code of this file.

Functions

static ABC_NAMESPACE_IMPL_START int Aig_ObjReverseLevel (Aig_Man_t *p, Aig_Obj_t *pObj)
 DECLARATIONS ///. More...
 
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 142 of file aigTiming.c.

143 {
144  Vec_Ptr_t * vNodes;
145  Aig_Obj_t * pObj;
146  int i;
147  assert( p->pFanData != NULL );
148  assert( p->vLevelR == NULL );
149  // remember the maximum number of direct levels
150  p->nLevelMax = Aig_ManLevels(p) + nMaxLevelIncrease;
151  // start the reverse levels
152  p->vLevelR = Vec_IntAlloc( 0 );
153  Vec_IntFill( p->vLevelR, Aig_ManObjNumMax(p), 0 );
154  // compute levels in reverse topological order
155  vNodes = Aig_ManDfsReverse( p );
156  Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pObj, i )
157  {
158  assert( pObj->fMarkA == 0 );
159  Aig_ObjSetReverseLevel( p, pObj, Aig_ObjReverseLevelNew(p, pObj) );
160  }
161  Vec_PtrFree( vNodes );
162 }
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_Obj_t_::fMarkA
unsigned int fMarkA
Definition: aig.h:79
Aig_ObjReverseLevelNew
int Aig_ObjReverseLevelNew(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: aigTiming.c:117
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Vec_IntFill
static void Vec_IntFill(Vec_Int_t *p, int nSize, int Fill)
Definition: bblif.c:356
Aig_Obj_t_
Definition: aig.h:69
Aig_ManObjNumMax
static int Aig_ManObjNumMax(Aig_Man_t *p)
Definition: aig.h:259
Aig_ManDfsReverse
Vec_Ptr_t * Aig_ManDfsReverse(Aig_Man_t *p)
Definition: aigDfs.c:458
Aig_ObjSetReverseLevel
static void Aig_ObjSetReverseLevel(Aig_Man_t *p, Aig_Obj_t *pObj, int LevelR)
Definition: aigTiming.c:65
assert
#define assert(ex)
Definition: util_old.h:213
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Aig_ManLevels
int Aig_ManLevels(Aig_Man_t *p)
Definition: aigUtil.c:102
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
void Aig_ManStopReverseLevels ( Aig_Man_t *  p)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 175 of file aigTiming.c.

176 {
177  assert( p->vLevelR != NULL );
178  Vec_IntFree( p->vLevelR );
179  p->vLevelR = NULL;
180  p->nLevelMax = 0;
181 
182 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
assert
#define assert(ex)
Definition: util_old.h:213
Vec_IntFree
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
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 195 of file aigTiming.c.

196 {
197  Aig_Obj_t * pFanout, * pTemp;
198  int iFanout = -1, LevelOld, Lev, k, m;
199  assert( p->pFanData != NULL );
200  assert( Aig_ObjIsNode(pObjNew) );
201  // allocate level if needed
202  if ( p->vLevels == NULL )
203  p->vLevels = Vec_VecAlloc( Aig_ManLevels(p) + 8 );
204  // check if level has changed
205  LevelOld = Aig_ObjLevel(pObjNew);
206  if ( LevelOld == Aig_ObjLevelNew(pObjNew) )
207  return;
208  // start the data structure for level update
209  // we cannot fail to visit a node when using this structure because the
210  // nodes are stored by their _old_ levels, which are assumed to be correct
211  Vec_VecClear( p->vLevels );
212  Vec_VecPush( p->vLevels, LevelOld, pObjNew );
213  pObjNew->fMarkA = 1;
214  // recursively update level
215  Vec_VecForEachEntryStart( Aig_Obj_t *, p->vLevels, pTemp, Lev, k, LevelOld )
216  {
217  pTemp->fMarkA = 0;
218  assert( Aig_ObjLevel(pTemp) == Lev );
219  pTemp->Level = Aig_ObjLevelNew(pTemp);
220  // if the level did not change, no need to check the fanout levels
221  if ( Aig_ObjLevel(pTemp) == Lev )
222  continue;
223  // schedule fanout for level update
224  Aig_ObjForEachFanout( p, pTemp, pFanout, iFanout, m )
225  {
226  if ( Aig_ObjIsNode(pFanout) && !pFanout->fMarkA )
227  {
228  assert( Aig_ObjLevel(pFanout) >= Lev );
229  Vec_VecPush( p->vLevels, Aig_ObjLevel(pFanout), pFanout );
230  pFanout->fMarkA = 1;
231  }
232  }
233  }
234 }
Aig_ObjForEachFanout
#define Aig_ObjForEachFanout(p, pObj, pFanout, iFan, i)
Definition: aig.h:427
Aig_ObjLevelNew
static int Aig_ObjLevelNew(Aig_Obj_t *pObj)
Definition: aig.h:324
Aig_Obj_t_::Level
unsigned Level
Definition: aig.h:82
Vec_VecPush
static void Vec_VecPush(Vec_Vec_t *p, int Level, void *Entry)
Definition: vecVec.h:456
Vec_VecAlloc
static Vec_Vec_t * Vec_VecAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecVec.h:145
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_Obj_t_::fMarkA
unsigned int fMarkA
Definition: aig.h:79
Vec_VecClear
static void Vec_VecClear(Vec_Vec_t *p)
Definition: vecVec.h:437
Aig_ObjIsNode
static int Aig_ObjIsNode(Aig_Obj_t *pObj)
Definition: aig.h:280
Aig_Obj_t_
Definition: aig.h:69
Vec_VecForEachEntryStart
#define Vec_VecForEachEntryStart(Type, vGlob, pEntry, i, k, LevelStart)
Definition: vecVec.h:92
Aig_ObjLevel
static int Aig_ObjLevel(Aig_Obj_t *pObj)
Definition: aig.h:323
assert
#define assert(ex)
Definition: util_old.h:213
Aig_ManLevels
int Aig_ManLevels(Aig_Man_t *p)
Definition: aigUtil.c:102
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 247 of file aigTiming.c.

248 {
249  Aig_Obj_t * pFanin, * pTemp;
250  int LevelOld, LevFanin, Lev, k;
251  assert( p->vLevelR != NULL );
252  assert( Aig_ObjIsNode(pObjNew) );
253  // allocate level if needed
254  if ( p->vLevels == NULL )
255  p->vLevels = Vec_VecAlloc( Aig_ManLevels(p) + 8 );
256  // check if level has changed
257  LevelOld = Aig_ObjReverseLevel(p, pObjNew);
258  if ( LevelOld == Aig_ObjReverseLevelNew(p, pObjNew) )
259  return;
260  // start the data structure for level update
261  // we cannot fail to visit a node when using this structure because the
262  // nodes are stored by their _old_ levels, which are assumed to be correct
263  Vec_VecClear( p->vLevels );
264  Vec_VecPush( p->vLevels, LevelOld, pObjNew );
265  pObjNew->fMarkA = 1;
266  // recursively update level
267  Vec_VecForEachEntryStart( Aig_Obj_t *, p->vLevels, pTemp, Lev, k, LevelOld )
268  {
269  pTemp->fMarkA = 0;
270  LevelOld = Aig_ObjReverseLevel(p, pTemp);
271  assert( LevelOld == Lev );
272  Aig_ObjSetReverseLevel( p, pTemp, Aig_ObjReverseLevelNew(p, pTemp) );
273  // if the level did not change, to need to check the fanout levels
274  if ( Aig_ObjReverseLevel(p, pTemp) == Lev )
275  continue;
276  // schedule fanins for level update
277  pFanin = Aig_ObjFanin0(pTemp);
278  if ( Aig_ObjIsNode(pFanin) && !pFanin->fMarkA )
279  {
280  LevFanin = Aig_ObjReverseLevel( p, pFanin );
281  assert( LevFanin >= Lev );
282  Vec_VecPush( p->vLevels, LevFanin, pFanin );
283  pFanin->fMarkA = 1;
284  }
285  pFanin = Aig_ObjFanin1(pTemp);
286  if ( Aig_ObjIsNode(pFanin) && !pFanin->fMarkA )
287  {
288  LevFanin = Aig_ObjReverseLevel( p, pFanin );
289  assert( LevFanin >= Lev );
290  Vec_VecPush( p->vLevels, LevFanin, pFanin );
291  pFanin->fMarkA = 1;
292  }
293  }
294 }
Vec_VecPush
static void Vec_VecPush(Vec_Vec_t *p, int Level, void *Entry)
Definition: vecVec.h:456
Vec_VecAlloc
static Vec_Vec_t * Vec_VecAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecVec.h:145
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_ObjFanin0
static Aig_Obj_t * Aig_ObjFanin0(Aig_Obj_t *pObj)
Definition: aig.h:308
Aig_Obj_t_::fMarkA
unsigned int fMarkA
Definition: aig.h:79
Aig_ObjFanin1
static Aig_Obj_t * Aig_ObjFanin1(Aig_Obj_t *pObj)
Definition: aig.h:309
Vec_VecClear
static void Vec_VecClear(Vec_Vec_t *p)
Definition: vecVec.h:437
Aig_ObjIsNode
static int Aig_ObjIsNode(Aig_Obj_t *pObj)
Definition: aig.h:280
Aig_ObjReverseLevelNew
int Aig_ObjReverseLevelNew(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: aigTiming.c:117
Aig_ObjReverseLevel
static ABC_NAMESPACE_IMPL_START int Aig_ObjReverseLevel(Aig_Man_t *p, Aig_Obj_t *pObj)
DECLARATIONS ///.
Definition: aigTiming.c:46
Aig_Obj_t_
Definition: aig.h:69
Vec_VecForEachEntryStart
#define Vec_VecForEachEntryStart(Type, vGlob, pEntry, i, k, LevelStart)
Definition: vecVec.h:92
Aig_ObjSetReverseLevel
static void Aig_ObjSetReverseLevel(Aig_Man_t *p, Aig_Obj_t *pObj, int LevelR)
Definition: aigTiming.c:65
assert
#define assert(ex)
Definition: util_old.h:213
Aig_ManLevels
int Aig_ManLevels(Aig_Man_t *p)
Definition: aigUtil.c:102
void Aig_ManVerifyLevel ( Aig_Man_t *  p)

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

Synopsis [Verifies direct level of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 307 of file aigTiming.c.

308 {
309  Aig_Obj_t * pObj;
310  int i, Counter = 0;
311  assert( p->pFanData );
312  Aig_ManForEachNode( p, pObj, i )
313  if ( Aig_ObjLevel(pObj) != Aig_ObjLevelNew(pObj) )
314  {
315  printf( "Level of node %6d should be %4d instead of %4d.\n",
316  pObj->Id, Aig_ObjLevelNew(pObj), Aig_ObjLevel(pObj) );
317  Counter++;
318  }
319  if ( Counter )
320  printf( "Levels of %d nodes are incorrect.\n", Counter );
321 }
Aig_ObjLevelNew
static int Aig_ObjLevelNew(Aig_Obj_t *pObj)
Definition: aig.h:324
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_ManForEachNode
#define Aig_ManForEachNode(p, pObj, i)
Definition: aig.h:413
if
if(last==0)
Definition: sparse_int.h:34
Aig_Obj_t_
Definition: aig.h:69
Counter
static int Counter
Definition: extraBddMisc.c:1877
Aig_ObjLevel
static int Aig_ObjLevel(Aig_Obj_t *pObj)
Definition: aig.h:323
assert
#define assert(ex)
Definition: util_old.h:213
void Aig_ManVerifyReverseLevel ( Aig_Man_t *  p)

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

Synopsis [Verifies reverse level of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 334 of file aigTiming.c.

335 {
336  Aig_Obj_t * pObj;
337  int i, Counter = 0;
338  assert( p->vLevelR );
339  Aig_ManForEachNode( p, pObj, i )
340  if ( Aig_ObjLevel(pObj) != Aig_ObjLevelNew(pObj) )
341  {
342  printf( "Reverse level of node %6d should be %4d instead of %4d.\n",
343  pObj->Id, Aig_ObjReverseLevelNew(p, pObj), Aig_ObjReverseLevel(p, pObj) );
344  Counter++;
345  }
346  if ( Counter )
347  printf( "Reverse levels of %d nodes are incorrect.\n", Counter );
348 }
Aig_ObjLevelNew
static int Aig_ObjLevelNew(Aig_Obj_t *pObj)
Definition: aig.h:324
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_ObjReverseLevelNew
int Aig_ObjReverseLevelNew(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: aigTiming.c:117
Aig_ManForEachNode
#define Aig_ManForEachNode(p, pObj, i)
Definition: aig.h:413
if
if(last==0)
Definition: sparse_int.h:34
Aig_ObjReverseLevel
static ABC_NAMESPACE_IMPL_START int Aig_ObjReverseLevel(Aig_Man_t *p, Aig_Obj_t *pObj)
DECLARATIONS ///.
Definition: aigTiming.c:46
Aig_Obj_t_
Definition: aig.h:69
Counter
static int Counter
Definition: extraBddMisc.c:1877
Aig_ObjLevel
static int Aig_ObjLevel(Aig_Obj_t *pObj)
Definition: aig.h:323
assert
#define assert(ex)
Definition: util_old.h:213
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 83 of file aigTiming.c.

84 {
85  Aig_ObjSetReverseLevel( p, pObj, 0 );
86 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_ObjSetReverseLevel
static void Aig_ObjSetReverseLevel(Aig_Man_t *p, Aig_Obj_t *pObj, int LevelR)
Definition: aigTiming.c:65
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 100 of file aigTiming.c.

101 {
102  assert( p->vLevelR );
103  return p->nLevelMax + 1 - Aig_ObjReverseLevel(p, pObj);
104 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Aig_ObjReverseLevel
static ABC_NAMESPACE_IMPL_START int Aig_ObjReverseLevel(Aig_Man_t *p, Aig_Obj_t *pObj)
DECLARATIONS ///.
Definition: aigTiming.c:46
assert
#define assert(ex)
Definition: util_old.h:213
static ABC_NAMESPACE_IMPL_START int Aig_ObjReverseLevel ( Aig_Man_t *  p,
Aig_Obj_t *  pObj 
)
inlinestatic

DECLARATIONS ///.

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

]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 46 of file aigTiming.c.

47 {
48  assert( p->vLevelR );
49  Vec_IntFillExtra( p->vLevelR, pObj->Id + 1, 0 );
50  return Vec_IntEntry(p->vLevelR, pObj->Id);
51 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_IntFillExtra
static void Vec_IntFillExtra(Vec_Int_t *p, int nSize, int Fill)
Definition: bblif.c:376
Vec_IntEntry
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
assert
#define assert(ex)
Definition: util_old.h:213
Aig_Obj_t_::Id
int Id
Definition: aig.h:85
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 117 of file aigTiming.c.

118 {
119  Aig_Obj_t * pFanout;
120  int i, iFanout = -1, LevelCur, Level = 0;
121  Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, i )
122  {
123  LevelCur = Aig_ObjReverseLevel( p, pFanout );
124  Level = Abc_MaxInt( Level, LevelCur );
125  }
126  return Level + 1;
127 }
Aig_ObjForEachFanout
#define Aig_ObjForEachFanout(p, pObj, pFanout, iFan, i)
Definition: aig.h:427
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
Aig_ObjReverseLevel
static ABC_NAMESPACE_IMPL_START int Aig_ObjReverseLevel(Aig_Man_t *p, Aig_Obj_t *pObj)
DECLARATIONS ///.
Definition: aigTiming.c:46
Aig_Obj_t_
Definition: aig.h:69
static void Aig_ObjSetReverseLevel ( Aig_Man_t *  p,
Aig_Obj_t *  pObj,
int  LevelR 
)
inlinestatic

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 65 of file aigTiming.c.

66 {
67  assert( p->vLevelR );
68  Vec_IntFillExtra( p->vLevelR, pObj->Id + 1, 0 );
69  Vec_IntWriteEntry( p->vLevelR, pObj->Id, LevelR );
70 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_IntFillExtra
static void Vec_IntFillExtra(Vec_Int_t *p, int nSize, int Fill)
Definition: bblif.c:376
Vec_IntWriteEntry
static void Vec_IntWriteEntry(Vec_Int_t *p, int i, int Entry)
Definition: bblif.c:285
assert
#define assert(ex)
Definition: util_old.h:213
Aig_Obj_t_::Id
int Id
Definition: aig.h:85