/**CFile****************************************************************
FileName [giaEdge.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Scalable AIG package.]
Synopsis [Edge-related procedures.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: giaEdge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "gia.h"
#include "misc/tim/tim.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
static inline int Gia_ObjEdgeCount( int iObj, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
{
return (Vec_IntEntry(vEdge1, iObj) > 0) + (Vec_IntEntry(vEdge2, iObj) > 0);
}
static inline int Gia_ObjEdgeAdd( int iObj, int iNext, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
{
int RetValue = 0;
if ( Vec_IntEntry(vEdge1, iObj) == 0 )
Vec_IntWriteEntry(vEdge1, iObj, iNext);
else if ( Vec_IntEntry(vEdge2, iObj) == 0 )
Vec_IntWriteEntry(vEdge2, iObj, iNext);
else RetValue = 1;
return RetValue;
}
static inline void Gia_ObjEdgeRemove( int iObj, int iNext, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
{
assert( Vec_IntEntry(vEdge1, iObj) == iNext || Vec_IntEntry(vEdge2, iObj) == iNext );
if ( Vec_IntEntry(vEdge1, iObj) == iNext )
Vec_IntWriteEntry( vEdge1, iObj, Vec_IntEntry(vEdge2, iObj) );
Vec_IntWriteEntry( vEdge2, iObj, 0 );
}
static inline void Gia_ObjEdgeClean( int iObj, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
{
Vec_IntWriteEntry( vEdge1, iObj, 0 );
Vec_IntWriteEntry( vEdge2, iObj, 0 );
}
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Transforms edge assignment.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Gia_ManEdgeFromArray( Gia_Man_t * p, Vec_Int_t * vArray )
{
int i, iObj1, iObj2, Count = 0;
Vec_IntFreeP( &p->vEdge1 );
Vec_IntFreeP( &p->vEdge2 );
p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
Vec_IntForEachEntryDouble( vArray, iObj1, iObj2, i )
{
assert( iObj1 < iObj2 );
Count += Gia_ObjEdgeAdd( iObj1, iObj2, p->vEdge1, p->vEdge2 );
Count += Gia_ObjEdgeAdd( iObj2, iObj1, p->vEdge1, p->vEdge2 );
}
if ( Count )
printf( "Found %d violations during edge conversion.\n", Count );
}
Vec_Int_t * Gia_ManEdgeToArray( Gia_Man_t * p )
{
int iObj, iFanin;
Vec_Int_t * vArray = Vec_IntAlloc( 1000 );
assert( p->vEdge1 && p->vEdge2 );
assert( Vec_IntSize(p->vEdge1) == Gia_ManObjNum(p) );
assert( Vec_IntSize(p->vEdge2) == Gia_ManObjNum(p) );
for ( iObj = 0; iObj < Gia_ManObjNum(p); iObj++ )
{
iFanin = Vec_IntEntry( p->vEdge1, iObj );
if ( iFanin && iFanin < iObj )
Vec_IntPushTwo( vArray, iFanin, iObj );
iFanin = Vec_IntEntry( p->vEdge2, iObj );
if ( iFanin && iFanin < iObj )
Vec_IntPushTwo( vArray, iFanin, iObj );
}
return vArray;
}
/**Function*************************************************************
Synopsis [Prints mapping statistics.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Gia_ManConvertPackingToEdges( Gia_Man_t * p )
{
int i, k, Entry, nEntries, nEntries2, nNodes[4], Count = 0;
if ( p->vPacking == NULL )
return;
Vec_IntFreeP( &p->vEdge1 );
Vec_IntFreeP( &p->vEdge2 );
p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
// iterate through structures
nEntries = Vec_IntEntry( p->vPacking, 0 );
nEntries2 = 0;
Vec_IntForEachEntryStart( p->vPacking, Entry, i, 1 )
{
assert( Entry > 0 && Entry < 4 );
i++;
for ( k = 0; k < Entry; k++, i++ )
nNodes[k] = Vec_IntEntry(p->vPacking, i);
i--;
nEntries2++;
// create edges
if ( Entry == 2 )
{
Count += Gia_ObjEdgeAdd( nNodes[0], nNodes[1], p->vEdge1, p->vEdge2 );
Count += Gia_ObjEdgeAdd( nNodes[1], nNodes[0], p->vEdge1, p->vEdge2 );
}
else if ( Entry == 3 )
{
Count += Gia_ObjEdgeAdd( nNodes[0], nNodes[2], p->vEdge1, p->vEdge2 );
Count += Gia_ObjEdgeAdd( nNodes[2], nNodes[0], p->vEdge1, p->vEdge2 );
Count += Gia_ObjEdgeAdd( nNodes[1], nNodes[2], p->vEdge1, p->vEdge2 );
Count += Gia_ObjEdgeAdd( nNodes[2], nNodes[1], p->vEdge1, p->vEdge2 );
}
}
assert( nEntries == nEntries2 );
if ( Count )
printf( "Skipped %d illegal edges.\n", Count );
}
/**Function*************************************************************
Synopsis [Evaluates given edge assignment.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Gia_ObjHaveEdge( Gia_Man_t * p, int iObj, int iNext )
{
return Vec_IntEntry(p->vEdge1, iObj) == iNext || Vec_IntEntry(p->vEdge2, iObj) == iNext;
}
int Gia_ObjCheckEdge( Gia_Man_t * p, int iObj, int iNext )
{
return Gia_ObjHaveEdge( p, iObj, iNext );
}
static inline int Gia_ObjEvalEdgeDelay( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay )
{
int nEdgeDelay = 2;
int i, iFan, Delay, DelayMax = 0;
if ( Gia_ManHasMapping(p) && Gia_ObjIsLut(p, iObj) )
{
assert( Gia_ObjLutSize(p, iObj) <= 4 );
Gia_LutForEachFanin( p, iObj, iFan, i )
{
Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? nEdgeDelay : 10);
DelayMax = Abc_MaxInt( DelayMax, Delay );
}
}
else if ( Gia_ObjIsLut2(p, iObj) )
{
assert( Gia_ObjLutSize2(p, iObj) <= 4 );
Gia_LutForEachFanin2( p, iObj, iFan, i )
{
Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? nEdgeDelay : 10);
DelayMax = Abc_MaxInt( DelayMax, Delay );
}
}
else assert( 0 );
return DelayMax;
}
int Gia_ManEvalEdgeDelay( Gia_Man_t * p )
{
int k, iLut, DelayMax = 0;
assert( p->vEdge1 && p->vEdge2 );
Vec_IntFreeP( &p->vEdgeDelay );
p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
if ( Gia_ManHasMapping(p) )
{
if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
{
Gia_Obj_t * pObj;
Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
Gia_ManForEachObjVec( vNodes, p, pObj, k )
{
iLut = Gia_ObjId( p, pObj );
if ( Gia_ObjIsAnd(pObj) )
{
if ( Gia_ObjIsLut(p, iLut) )
Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
}
else if ( Gia_ObjIsCi(pObj) )
{
int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
Vec_IntWriteEntry( p->vEdgeDelay, iLut, arrTime );
}
else if ( Gia_ObjIsCo(pObj) )
{
int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
}
else if ( !Gia_ObjIsConst0(pObj) )
assert( 0 );
}
Vec_IntFree( vNodes );
}
else
{
Gia_ManForEachLut( p, iLut )
Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
}
}
else if ( Gia_ManHasMapping2(p) )
{
if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
{
Gia_Obj_t * pObj;
Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
Gia_ManForEachObjVec( vNodes, p, pObj, k )
{
iLut = Gia_ObjId( p, pObj );
if ( Gia_ObjIsAnd(pObj) )
{
if ( Gia_ObjIsLut2(p, iLut) )
Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
}
else if ( Gia_ObjIsCi(pObj) )
{
int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
Vec_IntWriteEntry( p->vEdgeDelay, iLut, arrTime );
}
else if ( Gia_ObjIsCo(pObj) )
{
int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
}
else if ( !Gia_ObjIsConst0(pObj) )
assert( 0 );
}
Vec_IntFree( vNodes );
}
else
{
Gia_ManForEachLut2( p, iLut )
Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
}
}
else assert( 0 );
Gia_ManForEachCoDriverId( p, iLut, k )
DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(p->vEdgeDelay, iLut) );
return DelayMax;
}
int Gia_ManEvalEdgeCount( Gia_Man_t * p )
{
return (Vec_IntCountPositive(p->vEdge1) + Vec_IntCountPositive(p->vEdge2))/2;
}
/**Function*************************************************************
Synopsis [Finds edge assignment.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Gia_ObjComputeEdgeDelay( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2, int fUseTwo )
{
int i, iFan, Delay, Status1, Status2;
int DelayMax = 0, DelayMax2 = 0, nCountMax = 0;
int iFanMax1 = -1, iFanMax2 = -1;
Vec_IntWriteEntry(vEdge1, iObj, 0);
Vec_IntWriteEntry(vEdge2, iObj, 0);
if ( Gia_ManHasMapping(p) && Gia_ObjIsLut(p, iObj) )
{
assert( Gia_ObjLutSize(p, iObj) <= 4 );
Gia_LutForEachFanin( p, iObj, iFan, i )
{
Delay = Vec_IntEntry( vDelay, iFan ) + 10;
if ( DelayMax < Delay )
{
DelayMax2 = DelayMax;
DelayMax = Delay;
iFanMax1 = iFan;
nCountMax = 1;
}
else if ( DelayMax == Delay )
{
iFanMax2 = iFan;
nCountMax++;
if ( !fUseTwo )
DelayMax2 = DelayMax;
}
else
DelayMax2 = Abc_MaxInt( DelayMax2, Delay );
}
}
else if ( Gia_ObjIsLut2(p, iObj) )
{
assert( Gia_ObjLutSize2(p, iObj) <= 4 );
Gia_LutForEachFanin2( p, iObj, iFan, i )
{
Delay = Vec_IntEntry( vDelay, iFan ) + 10;
if ( DelayMax < Delay )
{
DelayMax2 = DelayMax;
DelayMax = Delay;
iFanMax1 = iFan;
nCountMax = 1;
}
else if ( DelayMax == Delay )
{
iFanMax2 = iFan;
nCountMax++;
if ( !fUseTwo )
DelayMax2 = DelayMax;
}
else
DelayMax2 = Abc_MaxInt( DelayMax2, Delay );
}
}
else assert( 0 );
assert( nCountMax > 0 );
if ( DelayMax <= 10 )
{} // skip first level
else if ( nCountMax == 1 )
{
Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
if ( Status1 <= 1 )
{
Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
DelayMax = Abc_MaxInt( DelayMax2, DelayMax - 8 );
Vec_IntWriteEntry( vDelay, iObj, DelayMax );
return DelayMax;
}
}
else if ( fUseTwo && nCountMax == 2 )
{
Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
Status2 = Gia_ObjEdgeCount( iFanMax2, vEdge1, vEdge2 );
if ( Status1 <= 1 && Status2 <= 1 )
{
Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
Gia_ObjEdgeAdd( iFanMax2, iObj, vEdge1, vEdge2 );
Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
Gia_ObjEdgeAdd( iObj, iFanMax2, vEdge1, vEdge2 );
DelayMax = Abc_MaxInt( DelayMax2, DelayMax - 8 );
Vec_IntWriteEntry( vDelay, iObj, DelayMax );
return DelayMax;
}
}
Vec_IntWriteEntry( vDelay, iObj, DelayMax );
return DelayMax;
}
int Gia_ManComputeEdgeDelay( Gia_Man_t * p, int fUseTwo )
{
int k, iLut, DelayMax = 0;
Vec_IntFreeP( &p->vEdgeDelay );
Vec_IntFreeP( &p->vEdge1 );
Vec_IntFreeP( &p->vEdge2 );
p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
if ( Gia_ManHasMapping(p) )
{
if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
{
Gia_Obj_t * pObj;
Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
Gia_ManForEachObjVec( vNodes, p, pObj, k )
{
iLut = Gia_ObjId( p, pObj );
if ( Gia_ObjIsAnd(pObj) )
{
if ( Gia_ObjIsLut(p, iLut) )
Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
}
else if ( Gia_ObjIsCi(pObj) )
{
int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
Vec_IntWriteEntry( p->vEdgeDelay, iLut, arrTime );
}
else if ( Gia_ObjIsCo(pObj) )
{
int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
}
else if ( !Gia_ObjIsConst0(pObj) )
assert( 0 );
}
Vec_IntFree( vNodes );
}
else
{
Gia_ManForEachLut( p, iLut )
Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
}
}
else if ( Gia_ManHasMapping2(p) )
{
if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
{
Gia_Obj_t * pObj;
Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
Gia_ManForEachObjVec( vNodes, p, pObj, k )
{
iLut = Gia_ObjId( p, pObj );
if ( Gia_ObjIsAnd(pObj) )
{
if ( Gia_ObjIsLut2(p, iLut) )
Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
}
else if ( Gia_ObjIsCi(pObj) )
{
int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
Vec_IntWriteEntry( p->vEdgeDelay, iLut, arrTime );
}
else if ( Gia_ObjIsCo(pObj) )
{
int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
}
else if ( !Gia_ObjIsConst0(pObj) )
assert( 0 );
}
Vec_IntFree( vNodes );
}
else
{
Gia_ManForEachLut2( p, iLut )
Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
}
}
else assert( 0 );
Gia_ManForEachCoDriverId( p, iLut, k )
DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(p->vEdgeDelay, iLut) );
//printf( "The number of edges = %d. Delay = %d.\n", Gia_ManEvalEdgeCount(p), DelayMax );
return DelayMax;
}
/**Function*************************************************************
Synopsis [Finds edge assignment.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Gia_ObjComputeEdgeDelay2( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2, Vec_Int_t * vFanMax1, Vec_Int_t * vFanMax2, Vec_Int_t * vCountMax )
{
int i, iFan, DelayFanin, Status1, Status2;
int DelayMax = 0, nCountMax = 0;
int iFanMax1 = -1, iFanMax2 = -1;
Vec_IntWriteEntry(vEdge1, iObj, 0);
Vec_IntWriteEntry(vEdge2, iObj, 0);
// analyze this node
DelayMax = Vec_IntEntry( vDelay, iObj );
nCountMax = Vec_IntEntry( vCountMax, iObj );
if ( DelayMax == 0 )
{}
else if ( nCountMax == 1 )
{
iFanMax1 = Vec_IntEntry( vFanMax1, iObj );
Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
if ( Status1 <= 1 )
{
Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
DelayMax--;
}
}
else if ( nCountMax == 2 )
{
iFanMax1 = Vec_IntEntry( vFanMax1, iObj );
iFanMax2 = Vec_IntEntry( vFanMax2, iObj );
Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
Status2 = Gia_ObjEdgeCount( iFanMax2, vEdge1, vEdge2 );
if ( Status1 <= 1 && Status2 <= 1 )
{
Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
Gia_ObjEdgeAdd( iFanMax2, iObj, vEdge1, vEdge2 );
Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
Gia_ObjEdgeAdd( iObj, iFanMax2, vEdge1, vEdge2 );
DelayMax--;
}
}
Vec_IntWriteEntry( vDelay, iObj, DelayMax );
// computed DelayMax at this point
if ( Gia_ManHasMapping(p) && Gia_ObjIsLut(p, iObj) )
{
Gia_LutForEachFanin( p, iObj, iFan, i )
{
DelayFanin = Vec_IntEntry( vDelay, iFan );
if ( DelayFanin < DelayMax + 1 )
{
Vec_IntWriteEntry( vDelay, iFan, DelayMax + 1 );
Vec_IntWriteEntry( vFanMax1, iFan, iObj );
Vec_IntWriteEntry( vCountMax, iFan, 1 );
}
else if ( DelayFanin == DelayMax + 1 )
{
Vec_IntWriteEntry( vFanMax2, iFan, iObj );
Vec_IntAddToEntry( vCountMax, iFan, 1 );
}
}
}
else if ( Gia_ObjIsLut2(p, iObj) )
{
Gia_LutForEachFanin2( p, iObj, iFan, i )
{
DelayFanin = Vec_IntEntry( vDelay, iFan );
if ( DelayFanin < DelayMax + 1 )
{
Vec_IntWriteEntry( vDelay, iFan, DelayMax + 1 );
Vec_IntWriteEntry( vFanMax1, iFan, iObj );
Vec_IntWriteEntry( vCountMax, iFan, 1 );
}
else if ( DelayFanin == DelayMax + 1 )
{
Vec_IntWriteEntry( vFanMax2, iFan, iObj );
Vec_IntAddToEntry( vCountMax, iFan, 1 );
}
}
}
else assert( 0 );
return DelayMax;
}
int Gia_ManComputeEdgeDelay2( Gia_Man_t * p )
{
int k, iLut, DelayMax = 0;
Vec_Int_t * vFanMax1 = Vec_IntStart( Gia_ManObjNum(p) );
Vec_Int_t * vFanMax2 = Vec_IntStart( Gia_ManObjNum(p) );
Vec_Int_t * vCountMax = Vec_IntStart( Gia_ManObjNum(p) );
assert( p->pManTime == NULL );
Vec_IntFreeP( &p->vEdgeDelay );
Vec_IntFreeP( &p->vEdge1 );
Vec_IntFreeP( &p->vEdge2 );
p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
// Gia_ManForEachCoDriverId( p, iLut, k )
// Vec_IntWriteEntry( p->vEdgeDelay, iLut, 1 );
if ( Gia_ManHasMapping(p) )
Gia_ManForEachLutReverse( p, iLut )
Gia_ObjComputeEdgeDelay2( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, vFanMax1, vFanMax2, vCountMax );
else if ( Gia_ManHasMapping2(p) )
Gia_ManForEachLut2Reverse( p, iLut )
Gia_ObjComputeEdgeDelay2( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, vFanMax1, vFanMax2, vCountMax );
else assert( 0 );
Gia_ManForEachCiId( p, iLut, k )
DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(p->vEdgeDelay, iLut) );
Vec_IntFree( vFanMax1 );
Vec_IntFree( vFanMax2 );
Vec_IntFree( vCountMax );
//printf( "The number of edges = %d. Delay = %d.\n", Gia_ManEvalEdgeCount(p), DelayMax );
return DelayMax;
}
/**Function*************************************************************
Synopsis [Finds edge assignment.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Gia_ManUpdateMapping( Gia_Man_t * p, Vec_Int_t * vNodes, Vec_Wec_t * vWin )
{
int i, iNode;
Vec_IntForEachEntry( vNodes, iNode, i )
ABC_SWAP( Vec_Int_t, *Vec_WecEntry(p->vMapping2, iNode), *Vec_WecEntry(vWin, i) );
}
int Gia_ManEvalWindowInc( Gia_Man_t * p, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, Vec_Wec_t * vWin, Vec_Int_t * vTemp, int fUseTwo )
{
int i, iLut, Delay, DelayMax = 0;
assert( Vec_IntSize(vNodes) == Vec_WecSize(vWin) );
Gia_ManUpdateMapping( p, vNodes, vWin );
Gia_ManCollectTfo( p, vLeaves, vTemp );
Vec_IntReverseOrder( vTemp );
Vec_IntForEachEntry( vTemp, iLut, i )
{
if ( !Gia_ObjIsLut(p, iLut) )
continue;
Delay = Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
DelayMax = Abc_MaxInt( DelayMax, Delay );
}
Gia_ManUpdateMapping( p, vNodes, vWin );
return DelayMax;
}
int Gia_ManEvalWindow( Gia_Man_t * p, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, Vec_Wec_t * vWin, Vec_Int_t * vTemp, int fUseTwo )
{
int DelayMax;
assert( Vec_IntSize(vNodes) == Vec_WecSize(vWin) );
Gia_ManUpdateMapping( p, vNodes, vWin );
DelayMax = Gia_ManComputeEdgeDelay( p, fUseTwo );
Gia_ManUpdateMapping( p, vNodes, vWin );
return DelayMax;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Edg_ManToMapping( Gia_Man_t * p )
{
int iObj, iFanin, k;
assert( Gia_ManHasMapping(p) );
Vec_WecFreeP( &p->vMapping2 );
Vec_WecFreeP( &p->vFanouts2 );
p->vMapping2 = Vec_WecStart( Gia_ManObjNum(p) );
p->vFanouts2 = Vec_WecStart( Gia_ManObjNum(p) );
Gia_ManForEachLut( p, iObj )
{
assert( Gia_ObjLutSize(p, iObj) <= 4 );
Gia_LutForEachFanin( p, iObj, iFanin, k )
{
Vec_WecPush( p->vMapping2, iObj, iFanin );
Vec_WecPush( p->vFanouts2, iFanin, iObj );
}
}
}
/**Function*************************************************************
Synopsis [Computes delay for the given edge assignment.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Edg_ObjEvalEdgeDelay( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay )
{
int DelayEdge = 0; // 2;
int DelayNoEdge = 1;
int i, iFan, Delay, DelayMax = 0;
assert( Gia_ObjIsLut2(p, iObj) );
Gia_LutForEachFanin2( p, iObj, iFan, i )
{
Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? DelayEdge : DelayNoEdge);
DelayMax = Abc_MaxInt( DelayMax, Delay );
}
//printf( "Obj %d - Level %d\n", iObj, DelayMax );
return DelayMax;
}
int Edg_ManEvalEdgeDelay( Gia_Man_t * p )
{
int iLut, Delay, DelayMax = 0;
assert( p->vEdge1 && p->vEdge2 );
if ( p->vEdgeDelay == NULL )
p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
else
Vec_IntFill( p->vEdgeDelay, Gia_ManObjNum(p), 0 );
Gia_ManForEachLut2( p, iLut )
{
Delay = Edg_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay);
Vec_IntWriteEntry( p->vEdgeDelay, iLut, Delay );
DelayMax = Abc_MaxInt( DelayMax, Delay );
}
return DelayMax;
}
static inline int Edg_ObjEvalEdgeDelayR( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay )
{
int DelayEdge = 0; // 2;
int DelayNoEdge = 1;
int i, iFan, Delay, DelayMax = 0;
assert( Gia_ObjIsLut2(p, iObj) );
Gia_LutForEachFanout2( p, iObj, iFan, i )
{
Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? DelayEdge : DelayNoEdge);
DelayMax = Abc_MaxInt( DelayMax, Delay );
}
//printf( "Obj %d - LevelR %d\n", iObj, DelayMax );
return DelayMax;
}
int Edg_ManEvalEdgeDelayR( Gia_Man_t * p )
{
// int k, DelayNoEdge = 1;
int iLut, Delay, DelayMax = 0;
assert( p->vEdge1 && p->vEdge2 );
if ( p->vEdgeDelayR == NULL )
p->vEdgeDelayR = Vec_IntStart( Gia_ManObjNum(p) );
else
Vec_IntFill( p->vEdgeDelayR, Gia_ManObjNum(p), 0 );
// Gia_ManForEachCoDriverId( p, iLut, k )
// Vec_IntWriteEntry( p->vEdgeDelayR, iLut, DelayNoEdge );
Gia_ManForEachLut2Reverse( p, iLut )
{
Delay = Edg_ObjEvalEdgeDelayR(p, iLut, p->vEdgeDelayR);
Vec_IntWriteEntry( p->vEdgeDelayR, iLut, Delay );
DelayMax = Abc_MaxInt( DelayMax, Delay );
}
return DelayMax;
}
void Edg_ManCollectCritEdges( Gia_Man_t * p, Vec_Wec_t * vEdges, int DelayMax )
{
Vec_Int_t * vLevel;
int k, iLut, Delay1, Delay2;
assert( p->vEdge1 && p->vEdge2 );
Vec_WecClear( vEdges );
Vec_WecInit( vEdges, DelayMax + 1 );
Gia_ManForEachLut2( p, iLut )
{
Delay1 = Vec_IntEntry( p->vEdgeDelay, iLut );
Delay2 = Vec_IntEntry( p->vEdgeDelayR, iLut );
assert( Delay1 + Delay2 <= DelayMax );
if ( Delay1 + Delay2 == DelayMax )
Vec_WecPush( vEdges, Delay1, iLut );
}
// every level should have critical nodes, except the first one
//Vec_WecPrint( vEdges, 0 );
Vec_WecForEachLevelStart( vEdges, vLevel, k, 1 )
assert( Vec_IntSize(vLevel) > 0 );
}
/**Function*************************************************************
Synopsis [Update one node.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Edg_ObjImprove( Gia_Man_t * p, int iObj, int nEdgeLimit, int DelayMax, int fVerbose )
{
int nFaninsC = 0, nFanoutsC = 0; // critical
int nFaninsEC = 0, nFanoutsEC = 0; // edge-critical
int nFaninsENC = 0, nFanoutsENC = 0; // edge-non-critial
int pFanins[4], pFanouts[4];
int nEdgeDiff, nEdges = 0, Count = 0;
int i, iNext, Delay1, Delay2;
// count how many fanins have critical edge
Delay1 = Vec_IntEntry( p->vEdgeDelayR, iObj );
//if ( Delay1 > 1 )
Gia_LutForEachFanin2( p, iObj, iNext, i )
{
if ( !Gia_ObjIsAnd(Gia_ManObj(p, iNext)) )
continue;
Delay2 = Vec_IntEntry( p->vEdgeDelay, iNext );
if ( Gia_ObjHaveEdge(p, iObj, iNext) )
{
nEdges++;
assert( Delay1 + Delay2 <= DelayMax );
if ( Delay1 + Delay2 == DelayMax )
nFaninsEC++;
else
nFaninsENC++;
}
else
{
assert( Delay1 + Delay2 + 1 <= DelayMax );
if ( Delay1 + Delay2 + 1 == DelayMax )
pFanins[nFaninsC++] = iNext;
}
}
// count how many fanouts have critical edge
Delay1 = Vec_IntEntry( p->vEdgeDelay, iObj );
//if ( Delay2 < DelayMax - 1 )
Gia_LutForEachFanout2( p, iObj, iNext, i )
{
//if ( !Gia_ObjIsAnd(Gia_ManObj(p, iNext)) )
// continue;
assert( Gia_ObjIsAnd(Gia_ManObj(p, iNext)) );
Delay2 = Vec_IntEntry( p->vEdgeDelayR, iNext );
if ( Gia_ObjHaveEdge(p, iObj, iNext) )
{
nEdges++;
assert( Delay1 + Delay2 <= DelayMax );
if ( Delay1 + Delay2 == DelayMax )
nFanoutsEC++;
else
nFanoutsENC++;
}
else
{
assert( Delay1 + Delay2 + 1 <= DelayMax );
if ( Delay1 + Delay2 + 1 == DelayMax )
{
if ( nFanoutsC < nEdgeLimit )
pFanouts[nFanoutsC] = iNext;
nFanoutsC++;
}
}
}
if ( fVerbose )
{
printf( "%8d : ", iObj );
printf( "Edges = %d ", nEdges );
printf( "Fanins (all %d EC %d ENC %d C %d) ",
Gia_ObjLutSize2(p, iObj), nFaninsEC, nFaninsENC, nFaninsC );
printf( "Fanouts (all %d EC %d ENC %d C %d) ",
Gia_ObjLutFanoutNum2(p, iObj), nFanoutsEC, nFanoutsENC, nFanoutsC );
}
// consider simple cases
assert( nEdges <= nEdgeLimit );
if ( nEdges == nEdgeLimit )
{
if ( fVerbose )
printf( "Full\n" );
return 0;
}
nEdgeDiff = nEdgeLimit - nEdges;
// check if fanins or fanouts could be improved
if ( nFaninsEC == 0 && nFaninsC && nFaninsC <= nEdgeDiff )
{
for ( i = 0; i < nFaninsC; i++ )
if ( Gia_ObjEdgeCount(pFanins[i], p->vEdge1, p->vEdge2) == nEdgeLimit )
break;
if ( i == nFaninsC )
{
for ( i = 0; i < nFaninsC; i++ )
{
Count += Gia_ObjEdgeAdd( iObj, pFanins[i], p->vEdge1, p->vEdge2 );
Count += Gia_ObjEdgeAdd( pFanins[i], iObj, p->vEdge1, p->vEdge2 );
}
if ( Count )
printf( "Wrong number of edges.\n" );
if ( fVerbose )
printf( "Fixed %d critical fanins\n", nFaninsC );
return 1;
}
}
if ( nFanoutsEC == 0 && nFanoutsC && nFanoutsC <= nEdgeDiff )
{
for ( i = 0; i < nFanoutsC; i++ )
if ( Gia_ObjEdgeCount(pFanouts[i], p->vEdge1, p->vEdge2) == nEdgeLimit )
break;
if ( i == nFanoutsC )
{
for ( i = 0; i < nFanoutsC; i++ )
{
Count += Gia_ObjEdgeAdd( iObj, pFanouts[i], p->vEdge1, p->vEdge2 );
Count += Gia_ObjEdgeAdd( pFanouts[i], iObj, p->vEdge1, p->vEdge2 );
}
if ( Count )
printf( "Wrong number of edges.\n" );
if ( fVerbose )
printf( "Fixed %d critical fanouts\n", nFanoutsC );
return 1;
}
}
if ( fVerbose )
printf( "Cannot fix\n" );
return 0;
}
/**Function*************************************************************
Synopsis [Finds edge assignment.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Edg_ManAssignEdgeNew( Gia_Man_t * p, int nEdges, int fVerbose )
{
int DelayNoEdge = 1;
int fLevelVerbose = 0;
Vec_Int_t * vLevel;
Vec_Wec_t * vEdges = Vec_WecStart(0);
Vec_Int_t * vEdge1 = NULL, * vEdge2 = NULL;
int DelayD = 0, DelayR = 0, DelayPrev = ABC_INFINITY;
int k, j, i, iLast = -1, iObj;
if ( fVerbose )
printf( "Running edge assignment with E = %d.\n", nEdges );
// create fanouts
Edg_ManToMapping( p );
// create empty assignment
Vec_IntFreeP( &p->vEdge1 );
Vec_IntFreeP( &p->vEdge2 );
p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
// perform optimization
for ( i = 0; i < 10000; i++ )
{
// if there is no improvement after 10 iterations, quit
if ( i > iLast + 50 )
break;
// create delay information
DelayD = Edg_ManEvalEdgeDelay( p );
DelayR = Edg_ManEvalEdgeDelayR( p );
assert( DelayD == DelayR + DelayNoEdge );
if ( DelayPrev > DelayD )
{
//printf( "Saving backup point at %d levels.\n", DelayD );
Vec_IntFreeP( &vEdge1 ); vEdge1 = Vec_IntDup( p->vEdge1 );
Vec_IntFreeP( &vEdge2 ); vEdge2 = Vec_IntDup( p->vEdge2 );
DelayPrev = DelayD;
iLast = i;
}
if ( fVerbose )
printf( "\nIter %4d : Delay = %4d\n", i, DelayD );
// collect critical nodes (nodes with critical edges)
Edg_ManCollectCritEdges( p, vEdges, DelayD );
// sort levels according to the number of critical edges
if ( fLevelVerbose )
{
Vec_WecForEachLevel( vEdges, vLevel, k )
Vec_IntPush( vLevel, k );
}
Vec_WecSort( vEdges, 0 );
if ( fLevelVerbose )
{
Vec_WecForEachLevel( vEdges, vLevel, k )
{
int Level = Vec_IntPop( vLevel );
printf( "%d: Level %2d : ", k, Level );
Vec_IntPrint( vLevel );
}
}
Vec_WecForEachLevel( vEdges, vLevel, k )
{
Vec_IntForEachEntry( vLevel, iObj, j )
if ( Edg_ObjImprove(p, iObj, nEdges, DelayD, fVerbose) ) // improved
break;
if ( j < Vec_IntSize(vLevel) )
break;
}
if ( k == Vec_WecSize(vEdges) ) // if we could not improve anything, quit
break;
}
Vec_WecFree( vEdges );
// update to the saved version
Vec_IntFreeP( &p->vEdge1 ); p->vEdge1 = vEdge1;
Vec_IntFreeP( &p->vEdge2 ); p->vEdge2 = vEdge2;
return DelayD;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END