From 0c6505a26a537dc911b6566f82d759521e527c08 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 30 Jan 2008 20:01:00 -0800 Subject: Version abc80130_2 --- src/opt/res/resDivs.c | 285 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 285 insertions(+) create mode 100644 src/opt/res/resDivs.c (limited to 'src/opt/res/resDivs.c') diff --git a/src/opt/res/resDivs.c b/src/opt/res/resDivs.c new file mode 100644 index 00000000..cc75b90f --- /dev/null +++ b/src/opt/res/resDivs.c @@ -0,0 +1,285 @@ +/**CFile**************************************************************** + + FileName [resDivs.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Resynthesis package.] + + Synopsis [Collect divisors for the given window.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - January 15, 2007.] + + Revision [$Id: resDivs.c,v 1.00 2007/01/15 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "abc.h" +#include "resInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Res_WinMarkTfi( Res_Win_t * p ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Adds candidate divisors of the node to its window.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Res_WinDivisors( Res_Win_t * p, int nLevDivMax ) +{ + Abc_Obj_t * pObj, * pFanout, * pFanin; + int k, f, m; + + // set the maximum level of the divisors + p->nLevDivMax = nLevDivMax; + + // mark the TFI with the current trav ID + Abc_NtkIncrementTravId( p->pNode->pNtk ); + Res_WinMarkTfi( p ); + + // mark with the current trav ID those nodes that should not be divisors: + // (1) the node and its TFO + // (2) the MFFC of the node + // (3) the node's fanins (these are treated as a special case) + Abc_NtkIncrementTravId( p->pNode->pNtk ); + Res_WinSweepLeafTfo_rec( p->pNode, p->nLevDivMax ); + Res_WinVisitMffc( p->pNode ); + Abc_ObjForEachFanin( p->pNode, pObj, k ) + Abc_NodeSetTravIdCurrent( pObj ); + + // at this point the nodes are marked with two trav IDs: + // nodes to be collected as divisors are marked with previous trav ID + // nodes to be avoided as divisors are marked with current trav ID + + // start collecting the divisors + Vec_PtrClear( p->vDivs ); + Vec_PtrForEachEntry( p->vLeaves, pObj, k ) + { + assert( (int)pObj->Level >= p->nLevLeafMin ); + if ( !Abc_NodeIsTravIdPrevious(pObj) ) + continue; + if ( (int)pObj->Level > p->nLevDivMax ) + continue; + Vec_PtrPush( p->vDivs, pObj ); + } + // add the internal nodes to the data structure + Vec_PtrForEachEntry( p->vNodes, pObj, k ) + { + if ( !Abc_NodeIsTravIdPrevious(pObj) ) + continue; + if ( (int)pObj->Level > p->nLevDivMax ) + continue; + Vec_PtrPush( p->vDivs, pObj ); + } + + // explore the fanouts of already collected divisors + p->nDivsPlus = 0; + Vec_PtrForEachEntry( p->vDivs, pObj, k ) + { + // consider fanouts of this node + Abc_ObjForEachFanout( pObj, pFanout, f ) + { + // stop if there are too many fanouts + if ( f > 20 ) + break; + // skip nodes that are already added + if ( Abc_NodeIsTravIdPrevious(pFanout) ) + continue; + // skip nodes in the TFO or in the MFFC of node + if ( Abc_NodeIsTravIdCurrent(pFanout) ) + continue; + // skip COs + if ( !Abc_ObjIsNode(pFanout) ) + continue; + // skip nodes with large level + if ( (int)pFanout->Level >= p->nLevDivMax ) + continue; + // skip nodes whose fanins are not divisors + Abc_ObjForEachFanin( pFanout, pFanin, m ) + if ( !Abc_NodeIsTravIdPrevious(pFanin) ) + break; + if ( m < Abc_ObjFaninNum(pFanout) ) + continue; + // add the node to the divisors + Vec_PtrPush( p->vDivs, pFanout ); + Vec_PtrPush( p->vNodes, pFanout ); + Abc_NodeSetTravIdPrevious( pFanout ); + p->nDivsPlus++; + } + } +/* + printf( "Node level = %d. ", Abc_ObjLevel(p->pNode) ); + Vec_PtrForEachEntryStart( p->vDivs, pObj, k, Vec_PtrSize(p->vDivs)-p->nDivsPlus ) + printf( "%d ", Abc_ObjLevel(pObj) ); + printf( "\n" ); +*/ +//printf( "%d ", p->nDivsPlus ); +} + +/**Function************************************************************* + + Synopsis [Marks the TFI cone of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Res_WinMarkTfi_rec( Res_Win_t * p, Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanin; + int i; + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return; + Abc_NodeSetTravIdCurrent( pObj ); + assert( Abc_ObjIsNode(pObj) ); + // visit the fanins of the node + Abc_ObjForEachFanin( pObj, pFanin, i ) + Res_WinMarkTfi_rec( p, pFanin ); +} + +/**Function************************************************************* + + Synopsis [Marks the TFI cone of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Res_WinMarkTfi( Res_Win_t * p ) +{ + Abc_Obj_t * pObj; + int i; + // mark the leaves + Vec_PtrForEachEntry( p->vLeaves, pObj, i ) + Abc_NodeSetTravIdCurrent( pObj ); + // start from the node + Res_WinMarkTfi_rec( p, p->pNode ); +} + +/**Function************************************************************* + + Synopsis [Marks the TFO of the collected nodes up to the given level.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Res_WinSweepLeafTfo_rec( Abc_Obj_t * pObj, int nLevelLimit ) +{ + Abc_Obj_t * pFanout; + int i; + if ( Abc_ObjIsCo(pObj) || (int)pObj->Level > nLevelLimit ) + return; + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return; + Abc_NodeSetTravIdCurrent( pObj ); + Abc_ObjForEachFanout( pObj, pFanout, i ) + Res_WinSweepLeafTfo_rec( pFanout, nLevelLimit ); +} + +/**Function************************************************************* + + Synopsis [Dereferences the node's MFFC.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Res_NodeDeref_rec( Abc_Obj_t * pNode ) +{ + Abc_Obj_t * pFanin; + int i, Counter = 1; + if ( Abc_ObjIsCi(pNode) ) + return 0; + Abc_NodeSetTravIdCurrent( pNode ); + Abc_ObjForEachFanin( pNode, pFanin, i ) + { + assert( pFanin->vFanouts.nSize > 0 ); + if ( --pFanin->vFanouts.nSize == 0 ) + Counter += Res_NodeDeref_rec( pFanin ); + } + return Counter; +} + +/**Function************************************************************* + + Synopsis [References the node's MFFC.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Res_NodeRef_rec( Abc_Obj_t * pNode ) +{ + Abc_Obj_t * pFanin; + int i, Counter = 1; + if ( Abc_ObjIsCi(pNode) ) + return 0; + Abc_ObjForEachFanin( pNode, pFanin, i ) + { + if ( pFanin->vFanouts.nSize++ == 0 ) + Counter += Res_NodeRef_rec( pFanin ); + } + return Counter; +} + +/**Function************************************************************* + + Synopsis [Labels MFFC of the node with the current trav ID.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Res_WinVisitMffc( Abc_Obj_t * pNode ) +{ + int Count1, Count2; + assert( Abc_ObjIsNode(pNode) ); + // dereference the node (mark with the current trav ID) + Count1 = Res_NodeDeref_rec( pNode ); + // reference it back + Count2 = Res_NodeRef_rec( pNode ); + assert( Count1 == Count2 ); + return Count1; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + -- cgit v1.2.3