diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2012-08-27 22:11:29 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2012-08-27 22:11:29 -0700 |
commit | 8a1d439cb12ca9b1ea7ceaaca1b744076b38156a (patch) | |
tree | 67679cf84ead3620d3d8926da5fff6fd75ca8df9 | |
parent | 7772a4af05db1b2b0f21f7461cb6778349e4500c (diff) | |
download | abc-8a1d439cb12ca9b1ea7ceaaca1b744076b38156a.tar.gz abc-8a1d439cb12ca9b1ea7ceaaca1b744076b38156a.tar.bz2 abc-8a1d439cb12ca9b1ea7ceaaca1b744076b38156a.zip |
Added precomputation of TFO ordering for incremental network updates.
-rw-r--r-- | src/base/abc/abc.h | 3 | ||||
-rw-r--r-- | src/base/abc/abcNtk.c | 1 | ||||
-rw-r--r-- | src/base/abc/abcUtil.c | 114 |
3 files changed, 118 insertions, 0 deletions
diff --git a/src/base/abc/abc.h b/src/base/abc/abc.h index 18ceca5a..9ed546e6 100644 --- a/src/base/abc/abc.h +++ b/src/base/abc/abc.h @@ -221,6 +221,7 @@ struct Abc_Ntk_t_ Vec_Int_t * vObjPerm; // permutation saved Vec_Vec_t * vRealPos; // additional PO info Vec_Int_t * vRealNodes; // additional PO info + Vec_Int_t * vTopo; // node attributes Vec_Ptr_t * vAttrs; // managers of various node attributes (node functionality, global BDDs, etc) }; @@ -959,6 +960,8 @@ extern ABC_DLL int Abc_ObjPointerCompare( void ** pp1, void ** pp extern ABC_DLL void Abc_NtkTransferCopy( Abc_Ntk_t * pNtk ); extern ABC_DLL void Abc_NtkInvertConstraints( Abc_Ntk_t * pNtk ); extern ABC_DLL void Abc_NtkPrintCiLevels( Abc_Ntk_t * pNtk ); +extern ABC_DLL void Abc_NtkReverseTopoOrder( Abc_Ntk_t * pNtk ); + /*=== abcVerify.c ==========================================================*/ diff --git a/src/base/abc/abcNtk.c b/src/base/abc/abcNtk.c index 74bdf125..2f28f54c 100644 --- a/src/base/abc/abcNtk.c +++ b/src/base/abc/abcNtk.c @@ -1143,6 +1143,7 @@ void Abc_NtkDelete( Abc_Ntk_t * pNtk ) Vec_IntFreeP( &pNtk->vObjPerm ); Vec_VecFreeP( &pNtk->vRealPos ); Vec_IntFreeP( &pNtk->vRealNodes ); + Vec_IntFreeP( &pNtk->vTopo ); ABC_FREE( pNtk ); } diff --git a/src/base/abc/abcUtil.c b/src/base/abc/abcUtil.c index bffbf40e..1a36ee01 100644 --- a/src/base/abc/abcUtil.c +++ b/src/base/abc/abcUtil.c @@ -2499,6 +2499,120 @@ Abc_Ntk_t * Abc_NtkSopToCubes( Abc_Ntk_t * pNtk ) return pNtkNew; } +/**Function************************************************************* + + Synopsis [Creates precomputed reverse topological order for each node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Abc_NtkTopoHasBeg( Abc_Obj_t * p ) { return Vec_IntEntry(p->pNtk->vTopo, 2*Abc_ObjId(p) ); } +static inline int Abc_NtkTopoHasEnd( Abc_Obj_t * p ) { return Vec_IntEntry(p->pNtk->vTopo, 2*Abc_ObjId(p)+1); } + +static inline void Abc_NtkTopoSetBeg( Abc_Obj_t * p ) { Vec_IntWriteEntry(p->pNtk->vTopo, 2*Abc_ObjId(p) , Vec_IntSize(p->pNtk->vTopo)); } +static inline void Abc_NtkTopoSetEnd( Abc_Obj_t * p ) { Vec_IntWriteEntry(p->pNtk->vTopo, 2*Abc_ObjId(p)+1, Vec_IntSize(p->pNtk->vTopo)); } + +void Abc_NtkReverseTopoOrder_rec( Abc_Obj_t * pObj, int fThisIsPivot ) +{ + Abc_Obj_t * pNext, * pPivot = NULL; + int i; + if ( Abc_NodeIsTravIdCurrent( pObj ) ) + return; + Abc_NodeSetTravIdCurrent( pObj ); + if ( Abc_ObjIsPo(pObj) ) + { + Vec_IntPush( pObj->pNtk->vTopo, Abc_ObjId(pObj) ); + return; + } + assert( Abc_ObjIsNode(pObj) ); + // mark begining + if ( fThisIsPivot ) + Abc_NtkTopoSetBeg( pObj ); + // find fanout without topo + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( !Abc_NtkTopoHasBeg(pNext) ) + { + assert( !Abc_NtkTopoHasEnd(pNext) ); + Abc_NtkReverseTopoOrder_rec( pNext, 1 ); + pPivot = pNext; + break; + } + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( pNext != pPivot ) + Abc_NtkReverseTopoOrder_rec( pNext, 0 ); + // mark end + if ( fThisIsPivot ) + Abc_NtkTopoSetEnd( pObj ); + // save current node + Vec_IntPush( pObj->pNtk->vTopo, Abc_ObjId(pObj) ); +} +void Abc_NtkReverseTopoOrder( Abc_Ntk_t * p ) +{ + Abc_Obj_t * pObj; + int i; + assert( p->vTopo == NULL ); + p->vTopo = Vec_IntAlloc( 10 * Abc_NtkObjNumMax(p) ); + Vec_IntFill( p->vTopo, 2 * Abc_NtkObjNumMax(p), 0 ); + Abc_NtkForEachNode( p, pObj, i ) + { + if ( Abc_NtkTopoHasBeg(pObj) ) + continue; + Abc_NtkIncrementTravId( p ); + Abc_NtkReverseTopoOrder_rec( pObj, 1 ); + } + printf( "Nodes = %d. Size = %d. Ratio = %f.\n", + Abc_NtkNodeNum(p), Vec_IntSize(p->vTopo), 1.0*Vec_IntSize(p->vTopo)/Abc_NtkNodeNum(p) ); +} + +void Abc_NtkReverse_rec( Abc_Obj_t * pObj, Vec_Int_t * vVisited ) +{ + Abc_Obj_t * pNext; + int i; + if ( Abc_NodeIsTravIdCurrent( pObj ) ) + return; + Abc_NodeSetTravIdCurrent( pObj ); + Abc_ObjForEachFanout( pObj, pNext, i ) + Abc_NtkReverse_rec( pNext, vVisited ); + Vec_IntPush( vVisited, Abc_ObjId(pObj) ); +} +void Abc_NtkReverseTopoOrderTest( Abc_Ntk_t * p ) +{ + Vec_Int_t * vVisited; + Abc_Obj_t * pObj; + int i;//, k, iBeg, iEnd; + clock_t clk = clock(); + Abc_NtkReverseTopoOrder( p ); +/* + printf( "Reverse topological order for nodes:\n" ); + Abc_NtkForEachNode( p, pObj, i ) + { + iBeg = Abc_NtkTopoHasBeg( pObj ); + iEnd = Abc_NtkTopoHasEnd( pObj ); + printf( "Node %4d : ", Abc_ObjId(pObj) ); + for ( k = iEnd - 1; k >= iBeg; k-- ) + printf( "%d ", Vec_IntEntry(p->vTopo, k) ); + printf( "\n" ); + } +*/ + Vec_IntFreeP( &p->vTopo ); + Abc_PrintTime( 1, "Time", clock() - clk ); + // compute regular fanout orders + clk = clock(); + vVisited = Vec_IntAlloc( 1000 ); + Abc_NtkForEachNode( p, pObj, i ) + { + Vec_IntClear( vVisited ); + Abc_NtkIncrementTravId( p ); + Abc_NtkReverse_rec( pObj, vVisited ); + } + Vec_IntFree( vVisited ); + Abc_PrintTime( 1, "Time", clock() - clk ); +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// |