src/opt/res/resWin.c File Reference

#include "abc.h"
#include "resInt.h"
Include dependency graph for resWin.c:

Go to the source code of this file.

Functions

Res_Win_t * Res_WinAlloc ()
void Res_WinFree (Res_Win_t *p)
int Res_WinCollectLeavesAndNodes (Res_Win_t *p)
static int Res_WinComputeRootsCheck (Abc_Obj_t *pNode, int nLevelMax, int nFanoutLimit)
void Res_WinComputeRoots_rec (Abc_Obj_t *pNode, int nLevelMax, int nFanoutLimit, Vec_Ptr_t *vRoots)
int Res_WinComputeRoots (Res_Win_t *p)
int Res_WinMarkPaths_rec (Abc_Obj_t *pNode, Abc_Obj_t *pPivot, int nLevelMin)
void Res_WinMarkPaths (Res_Win_t *p)
void Res_WinFinalizeRoots_rec (Abc_Obj_t *pObj, Vec_Ptr_t *vRoots)
int Res_WinFinalizeRoots (Res_Win_t *p)
void Res_WinAddMissing_rec (Res_Win_t *p, Abc_Obj_t *pObj, int nLevTravMin)
void Res_WinAddMissing (Res_Win_t *p)
int Res_WinIsTrivial (Res_Win_t *p)
int Res_WinCompute (Abc_Obj_t *pNode, int nWinTfiMax, int nWinTfoMax, Res_Win_t *p)

Function Documentation

void Res_WinAddMissing ( Res_Win_t *  p  ) 

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

Synopsis [Adds to the window nodes and leaves in the TFI of the roots.]

Description []

SideEffects []

SeeAlso []

Definition at line 401 of file resWin.c.

00402 {
00403     Abc_Obj_t * pObj;
00404     int i;
00405     // mark the leaves
00406     Abc_NtkIncrementTravId( p->pNode->pNtk );
00407     Vec_PtrForEachEntry( p->vLeaves, pObj, i )
00408         Abc_NodeSetTravIdCurrent( pObj );        
00409     // mark the already collected nodes
00410     Vec_PtrForEachEntry( p->vNodes, pObj, i )
00411         Abc_NodeSetTravIdCurrent( pObj );        
00412     // explore from the roots
00413     Vec_PtrClear( p->vBranches );
00414     Vec_PtrForEachEntry( p->vRoots, pObj, i )
00415         Res_WinAddMissing_rec( p, pObj, p->nLevTravMin );
00416 }

void Res_WinAddMissing_rec ( Res_Win_t *  p,
Abc_Obj_t *  pObj,
int  nLevTravMin 
)

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

Synopsis [Recursively adds missing nodes and leaves.]

Description []

SideEffects []

SeeAlso []

Definition at line 366 of file resWin.c.

00367 {
00368     Abc_Obj_t * pFanin;
00369     int i;
00370     // skip the already collected leaves, nodes, and branches
00371     if ( Abc_NodeIsTravIdCurrent(pObj) )
00372         return;
00373     // if this is not an internal node - make it a new branch
00374     if ( !Abc_NodeIsTravIdPrevious(pObj) )
00375     {
00376         assert( Vec_PtrFind(p->vLeaves, pObj) == -1 );
00377         Abc_NodeSetTravIdCurrent( pObj );
00378         Vec_PtrPush( p->vBranches, pObj );
00379         return;
00380     }
00381     assert( Abc_ObjIsNode(pObj) ); // if this is a CI, then the window is incorrect!
00382     Abc_NodeSetTravIdCurrent( pObj );
00383     // visit the fanins of the node
00384     Abc_ObjForEachFanin( pObj, pFanin, i )
00385         Res_WinAddMissing_rec( p, pFanin, nLevTravMin );
00386     // collect the node
00387     Vec_PtrPush( p->vNodes, pObj );
00388 }

Res_Win_t* Res_WinAlloc (  ) 

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

FileName [resWin.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Resynthesis package.]

Synopsis [Windowing algorithm.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - January 15, 2007.]

Revision [

Id
resWin.c,v 1.00 2007/01/15 00:00:00 alanmi Exp

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

Synopsis [Allocates the window.]

Description []

SideEffects []

SeeAlso []

Definition at line 43 of file resWin.c.

00044 {
00045     Res_Win_t * p;
00046     // start the manager
00047     p = ALLOC( Res_Win_t, 1 );
00048     memset( p, 0, sizeof(Res_Win_t) );
00049     // set internal parameters
00050     p->nFanoutLimit = 10;
00051     p->nLevTfiMinus =  3;
00052     // allocate storage
00053     p->vRoots    = Vec_PtrAlloc( 256 );
00054     p->vLeaves   = Vec_PtrAlloc( 256 );
00055     p->vBranches = Vec_PtrAlloc( 256 );
00056     p->vNodes    = Vec_PtrAlloc( 256 );
00057     p->vDivs     = Vec_PtrAlloc( 256 );
00058     p->vMatrix   = Vec_VecStart( 128 );
00059     return p;
00060 }

int Res_WinCollectLeavesAndNodes ( Res_Win_t *  p  ) 

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

Synopsis [Collect the limited TFI cone of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 97 of file resWin.c.

00098 {
00099     Vec_Ptr_t * vFront;
00100     Abc_Obj_t * pObj, * pTemp;
00101     int i, k, m;
00102 
00103     assert( p->nWinTfiMax > 0 );
00104     assert( Vec_VecSize(p->vMatrix) > p->nWinTfiMax );
00105 
00106     // start matrix with the node
00107     Vec_VecClear( p->vMatrix );
00108     Vec_VecPush( p->vMatrix, 0, p->pNode );
00109     Abc_NtkIncrementTravId( p->pNode->pNtk );
00110     Abc_NodeSetTravIdCurrent( p->pNode );
00111 
00112     // collect the leaves (nodes pTemp such that "p->pNode->Level - pTemp->Level > p->nWinTfiMax")
00113     Vec_PtrClear( p->vLeaves );
00114     Vec_VecForEachLevelStartStop( p->vMatrix, vFront, i, 0, p->nWinTfiMax )
00115     {
00116         Vec_PtrForEachEntry( vFront, pObj, k )
00117         {
00118             Abc_ObjForEachFanin( pObj, pTemp, m )
00119             {
00120                 if ( Abc_NodeIsTravIdCurrent( pTemp ) )
00121                     continue;
00122                 Abc_NodeSetTravIdCurrent( pTemp );
00123                 if ( Abc_ObjIsCi(pTemp) || (int)(p->pNode->Level - pTemp->Level) > p->nWinTfiMax )                    
00124                     Vec_PtrPush( p->vLeaves, pTemp );
00125                 else
00126                     Vec_VecPush( p->vMatrix, p->pNode->Level - pTemp->Level, pTemp );
00127             }
00128         }
00129     }
00130     if ( Vec_PtrSize(p->vLeaves) == 0 )
00131         return 0;
00132 
00133     // collect the nodes in the reverse order
00134     Vec_PtrClear( p->vNodes );
00135     Vec_VecForEachLevelReverseStartStop( p->vMatrix, vFront, i, p->nWinTfiMax, 0 )
00136     {
00137         Vec_PtrForEachEntry( vFront, pObj, k )
00138             Vec_PtrPush( p->vNodes, pObj );
00139         Vec_PtrClear( vFront );
00140     }
00141 
00142     // get the lowest leaf level
00143     p->nLevLeafMin = ABC_INFINITY;
00144     Vec_PtrForEachEntry( p->vLeaves, pObj, k )
00145         p->nLevLeafMin = ABC_MIN( p->nLevLeafMin, (int)pObj->Level );
00146 
00147     // set minimum traversal level
00148     p->nLevTravMin = ABC_MAX( ((int)p->pNode->Level) - p->nWinTfiMax - p->nLevTfiMinus, p->nLevLeafMin );
00149     assert( p->nLevTravMin >= 0 );
00150     return 1;
00151 }

int Res_WinCompute ( Abc_Obj_t *  pNode,
int  nWinTfiMax,
int  nWinTfoMax,
Res_Win_t *  p 
)

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

Synopsis [Computes the window.]

Description []

SideEffects []

SeeAlso []

Definition at line 448 of file resWin.c.

00449 {
00450     assert( Abc_ObjIsNode(pNode) );
00451     assert( nWinTfiMax > 0 && nWinTfiMax < 10 );
00452     assert( nWinTfoMax >= 0 && nWinTfoMax < 10 );
00453 
00454     // initialize the window
00455     p->pNode      = pNode;
00456     p->nWinTfiMax = nWinTfiMax;
00457     p->nWinTfoMax = nWinTfoMax;
00458 
00459     Vec_PtrClear( p->vBranches );
00460     Vec_PtrClear( p->vDivs );
00461     Vec_PtrClear( p->vRoots );
00462     Vec_PtrPush( p->vRoots, pNode );
00463 
00464     // compute the leaves
00465     if ( !Res_WinCollectLeavesAndNodes( p ) )
00466         return 0;
00467 
00468     // compute the candidate roots
00469     if ( p->nWinTfoMax > 0 && Res_WinComputeRoots(p) )
00470     {
00471         // mark the paths from the roots to the leaves
00472         Res_WinMarkPaths( p );
00473         // refine the roots and add branches and missing nodes
00474         if ( Res_WinFinalizeRoots( p ) )
00475             Res_WinAddMissing( p );
00476     }
00477 
00478     return 1;
00479 }

int Res_WinComputeRoots ( Res_Win_t *  p  ) 

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

Synopsis [Recursively collects the root candidates.]

Description [Returns 1 if the only root is this node.]

SideEffects []

SeeAlso []

Definition at line 220 of file resWin.c.

00221 {
00222     Vec_PtrClear( p->vRoots );
00223     Abc_NtkIncrementTravId( p->pNode->pNtk );
00224     Res_WinComputeRoots_rec( p->pNode, p->pNode->Level + p->nWinTfoMax, p->nFanoutLimit, p->vRoots );
00225     assert( Vec_PtrSize(p->vRoots) > 0 );
00226     if ( Vec_PtrSize(p->vRoots) == 1 && Vec_PtrEntry(p->vRoots, 0) == p->pNode )
00227         return 0;
00228     return 1;
00229 }

void Res_WinComputeRoots_rec ( Abc_Obj_t *  pNode,
int  nLevelMax,
int  nFanoutLimit,
Vec_Ptr_t *  vRoots 
)

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

Synopsis [Recursively collects the root candidates.]

Description []

SideEffects []

SeeAlso []

Definition at line 193 of file resWin.c.

00194 {
00195     Abc_Obj_t * pFanout;
00196     int i;
00197     assert( Abc_ObjIsNode(pNode) );
00198     if ( Abc_NodeIsTravIdCurrent(pNode) )
00199         return;
00200     Abc_NodeSetTravIdCurrent( pNode );
00201     // check if the node should be the root
00202     if ( Res_WinComputeRootsCheck( pNode, nLevelMax, nFanoutLimit ) )
00203         Vec_PtrPush( vRoots, pNode );
00204     else // if not, explore its fanouts
00205         Abc_ObjForEachFanout( pNode, pFanout, i )
00206             Res_WinComputeRoots_rec( pFanout, nLevelMax, nFanoutLimit, vRoots );
00207 }

static int Res_WinComputeRootsCheck ( Abc_Obj_t *  pNode,
int  nLevelMax,
int  nFanoutLimit 
) [inline, static]

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

Synopsis [Returns 1 if the node should be a root.]

Description []

SideEffects []

SeeAlso []

Definition at line 166 of file resWin.c.

00167 {
00168     Abc_Obj_t * pFanout;
00169     int i;
00170     // the node is the root if one of the following is true:
00171     // (1) the node has more than fanouts than the limit
00172     if ( Abc_ObjFanoutNum(pNode) > nFanoutLimit )
00173         return 1;
00174     // (2) the node has CO fanouts
00175     // (3) the node has fanouts above the cutoff level
00176     Abc_ObjForEachFanout( pNode, pFanout, i )
00177         if ( Abc_ObjIsCo(pFanout) || (int)pFanout->Level > nLevelMax )
00178             return 1;
00179     return 0;
00180 }

int Res_WinFinalizeRoots ( Res_Win_t *  p  ) 

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

Synopsis [Finalizes the roots of the window.]

Description [Roots of the window are the nodes that have at least one fanout that it not in the TFO of the leaves.]

SideEffects []

SeeAlso []

Definition at line 340 of file resWin.c.

00341 {
00342     assert( !Abc_NodeIsTravIdCurrent(p->pNode) );
00343     // mark the node with the old traversal ID
00344     Abc_NodeSetTravIdCurrent( p->pNode ); 
00345     // recollect the roots
00346     Vec_PtrClear( p->vRoots );
00347     Res_WinFinalizeRoots_rec( p->pNode, p->vRoots );
00348     assert( Vec_PtrSize(p->vRoots) > 0 );
00349     if ( Vec_PtrSize(p->vRoots) == 1 && Vec_PtrEntry(p->vRoots, 0) == p->pNode )
00350         return 0;
00351     return 1;
00352 }

void Res_WinFinalizeRoots_rec ( Abc_Obj_t *  pObj,
Vec_Ptr_t *  vRoots 
)

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

Synopsis [Recursively collects the roots.]

Description []

SideEffects []

SeeAlso []

Definition at line 310 of file resWin.c.

00311 {
00312     Abc_Obj_t * pFanout;
00313     int i;
00314     assert( Abc_ObjIsNode(pObj) );
00315     assert( Abc_NodeIsTravIdCurrent(pObj) );
00316     // check if the node has all fanouts marked
00317     Abc_ObjForEachFanout( pObj, pFanout, i )
00318         if ( !Abc_NodeIsTravIdCurrent(pFanout) )
00319             break;
00320     // if some of the fanouts are unmarked, add the node to the roots
00321     if ( i < Abc_ObjFanoutNum(pObj) ) 
00322         Vec_PtrPushUnique( vRoots, pObj );
00323     else  // otherwise, call recursively
00324         Abc_ObjForEachFanout( pObj, pFanout, i )
00325             Res_WinFinalizeRoots_rec( pFanout, vRoots );
00326 }

void Res_WinFree ( Res_Win_t *  p  ) 

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

Synopsis [Frees the window.]

Description []

SideEffects []

SeeAlso []

Definition at line 73 of file resWin.c.

00074 {
00075     Vec_PtrFree( p->vRoots  );
00076     Vec_PtrFree( p->vLeaves );
00077     Vec_PtrFree( p->vBranches );
00078     Vec_PtrFree( p->vNodes  );
00079     Vec_PtrFree( p->vDivs   );
00080     Vec_VecFree( p->vMatrix );
00081     free( p );
00082 }

int Res_WinIsTrivial ( Res_Win_t *  p  ) 

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

Synopsis [Returns 1 if the window is trivial (without TFO).]

Description []

SideEffects []

SeeAlso []

Definition at line 432 of file resWin.c.

00433 {
00434     return Vec_PtrSize(p->vRoots) == 1 && Vec_PtrEntry(p->vRoots, 0) == p->pNode;
00435 }

void Res_WinMarkPaths ( Res_Win_t *  p  ) 

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

Synopsis [Marks the paths from the roots to the leaves.]

Description []

SideEffects []

SeeAlso []

Definition at line 280 of file resWin.c.

00281 {
00282     Abc_Obj_t * pObj;
00283     int i;
00284     // mark the leaves
00285     Abc_NtkIncrementTravId( p->pNode->pNtk );
00286     Abc_NtkIncrementTravId( p->pNode->pNtk );
00287     Vec_PtrForEachEntry( p->vLeaves, pObj, i )
00288         Abc_NodeSetTravIdCurrent( pObj );
00289     // traverse from the roots and mark the nodes that can reach leaves
00290     // the nodes that do not reach leaves have previous trav ID
00291     // the nodes that reach leaves have current trav ID
00292     Vec_PtrForEachEntry( p->vRoots, pObj, i )
00293         Res_WinMarkPaths_rec( pObj, p->pNode, p->nLevTravMin );
00294 }

int Res_WinMarkPaths_rec ( Abc_Obj_t *  pNode,
Abc_Obj_t *  pPivot,
int  nLevelMin 
)

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

Synopsis [Marks the paths from the roots to the leaves.]

Description [Returns 1 if the the node can reach a leaf.]

SideEffects []

SeeAlso []

Definition at line 244 of file resWin.c.

00245 {
00246     Abc_Obj_t * pFanin;
00247     int i, RetValue;
00248     // skip visited nodes
00249     if ( Abc_NodeIsTravIdCurrent(pNode) )
00250         return 1;
00251     if ( Abc_NodeIsTravIdPrevious(pNode) )
00252         return 0;
00253     // assume that the node does not have access to the leaves
00254     Abc_NodeSetTravIdPrevious( pNode );
00255     // skip nodes below the given level
00256     if ( pNode == pPivot || (int)pNode->Level <= nLevelMin )
00257         return 0;
00258     assert( Abc_ObjIsNode(pNode) );
00259     // check if the fanins have access to the leaves
00260     RetValue = 0;
00261     Abc_ObjForEachFanin( pNode, pFanin, i )
00262         RetValue |= Res_WinMarkPaths_rec( pFanin, pPivot, nLevelMin );
00263     // relabel the node if it has access to the leaves
00264     if ( RetValue )
00265         Abc_NodeSetTravIdCurrent( pNode );
00266     return RetValue;
00267 }

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