From b31b6fec771ef4fd19ac64b4ce31b30fd7113e6d Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 6 Apr 2016 15:43:03 -0700 Subject: Supporting edge information during mapping. --- src/aig/gia/gia.h | 9 ++ src/aig/gia/giaAiger.c | 28 ++++++ src/aig/gia/giaEdge.c | 231 ++++++++++++++++++++++++++++++++++++++++++++++++ src/aig/gia/giaMan.c | 26 ++++++ src/aig/gia/module.make | 1 + 5 files changed, 295 insertions(+) create mode 100644 src/aig/gia/giaEdge.c (limited to 'src/aig/gia') diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index 47e856c8..274b9314 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -138,6 +138,9 @@ struct Gia_Man_t_ Vec_Int_t * vConfigs; // cell configurations char * pCellStr; // cell description Vec_Int_t * vLutConfigs; // LUT configurations + Vec_Int_t * vEdgeDelay; // special edge information + Vec_Int_t * vEdge1; // special edge information + Vec_Int_t * vEdge2; // special edge information Abc_Cex_t * pCexComb; // combinational counter-example Abc_Cex_t * pCexSeq; // sequential counter-example Vec_Ptr_t * vSeqModelVec; // sequential counter-examples @@ -1200,6 +1203,12 @@ extern Gia_Man_t * Gia_ManDupOneHot( Gia_Man_t * p ); extern Gia_Man_t * Gia_ManDupLevelized( Gia_Man_t * p ); extern Gia_Man_t * Gia_ManDupFromVecs( Gia_Man_t * p, Vec_Int_t * vCis, Vec_Int_t * vAnds, Vec_Int_t * vCos, int nRegs ); extern Gia_Man_t * Gia_ManDupSliced( Gia_Man_t * p, int nSuppMax ); +/*=== giaEdge.c ==========================================================*/ +extern void Gia_ManEdgeFromArray( Gia_Man_t * p, Vec_Int_t * vArray ); +extern Vec_Int_t * Gia_ManEdgeToArray( Gia_Man_t * p ); +extern int Gia_ManEvalEdgeDelay( Gia_Man_t * p ); +extern int Gia_ManComputeEdgeDelay( Gia_Man_t * p ); +extern int Gia_ManComputeEdgeDelay2( Gia_Man_t * p ); /*=== giaEnable.c ==========================================================*/ extern void Gia_ManDetectSeqSignals( Gia_Man_t * p, int fSetReset, int fVerbose ); extern Gia_Man_t * Gia_ManUnrollAndCofactor( Gia_Man_t * p, int nFrames, int nFanMax, int fVerbose ); diff --git a/src/aig/gia/giaAiger.c b/src/aig/gia/giaAiger.c index fb7717b4..504533e9 100644 --- a/src/aig/gia/giaAiger.c +++ b/src/aig/gia/giaAiger.c @@ -750,6 +750,22 @@ Gia_Man_t * Gia_AigerReadFromMemory( char * pContents, int nFileSize, int fSkipS pCur += 4*Vec_IntSize(pNew->vObjClasses); if ( fVerbose ) printf( "Finished reading extension \"v\".\n" ); } + // read edge information + else if ( *pCur == 'w' ) + { + Vec_Int_t * vPairs; + int i, nPairs; + pCur++; + pCurTemp = pCur + Gia_AigerReadInt(pCur) + 4; pCur += 4; + nPairs = Gia_AigerReadInt(pCur); pCur += 4; + vPairs = Vec_IntAlloc( 2*nPairs ); + for ( i = 0; i < 2*nPairs; i++ ) + Vec_IntPush( vPairs, Gia_AigerReadInt(pCur) ), pCur += 4; + assert( pCur == pCurTemp ); + if ( fVerbose ) printf( "Finished reading extension \"w\".\n" ); + Gia_ManEdgeFromArray( pNew, vPairs ); + Vec_IntFree( vPairs ); + } else break; } } @@ -1308,6 +1324,18 @@ void Gia_AigerWrite( Gia_Man_t * pInit, char * pFileName, int fWriteSymbols, int for ( i = 0; i < Vec_IntSize(p->vRegInits); i++ ) Gia_FileWriteBufferSize( pFile, Vec_IntEntry(p->vRegInits, i) ); } + // write register inits + if ( p->vEdge1 ) + { + Vec_Int_t * vPairs = Gia_ManEdgeToArray( p ); + int i; + fprintf( pFile, "w" ); + Gia_FileWriteBufferSize( pFile, 4*(Vec_IntSize(vPairs)+1) ); + Gia_FileWriteBufferSize( pFile, Vec_IntSize(vPairs)/2 ); + for ( i = 0; i < Vec_IntSize(vPairs); i++ ) + Gia_FileWriteBufferSize( pFile, Vec_IntEntry(vPairs, i) ); + Vec_IntFree( vPairs ); + } // write configuration data if ( p->vConfigs ) { diff --git a/src/aig/gia/giaEdge.c b/src/aig/gia/giaEdge.c new file mode 100644 index 00000000..93624fdf --- /dev/null +++ b/src/aig/gia/giaEdge.c @@ -0,0 +1,231 @@ +/**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" + +ABC_NAMESPACE_IMPL_START + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static inline int Sbm_ObjEdgeCount( int iObj, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 ) +{ + return (Vec_IntEntry(vEdge1, iObj) > 0) + (Vec_IntEntry(vEdge2, iObj) > 0); +} +static inline void Sbm_ObjEdgeAdd( int iObj, int iNext, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 ) +{ + if ( Vec_IntEntry(vEdge1, iObj) == 0 ) + Vec_IntWriteEntry(vEdge1, iObj, iNext); + else if ( Vec_IntEntry(vEdge2, iObj) == 0 ) + Vec_IntWriteEntry(vEdge2, iObj, iNext); + else assert( 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; + Vec_IntFreeP( &p->vEdge1 ); + Vec_IntFreeP( &p->vEdge1 ); + p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) ); + p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) ); + Vec_IntForEachEntryDouble( vArray, iObj1, iObj2, i ) + { + assert( iObj1 != iObj2 ); + Sbm_ObjEdgeAdd( iObj1, iObj2, p->vEdge1, p->vEdge2 ); + Sbm_ObjEdgeAdd( iObj2, iObj1, p->vEdge1, p->vEdge2 ); + } +} +Vec_Int_t * Gia_ManEdgeToArray( Gia_Man_t * p ) +{ + int i, Entry; + 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 ( i = 0; i < Gia_ManObjNum(p); i++ ) + { + Entry = Vec_IntEntry(p->vEdge1, i); + if ( Entry && Entry < i ) + Vec_IntPushTwo( vArray, Entry, i ); + Entry = Vec_IntEntry(p->vEdge2, i); + if ( Entry && Entry < i ) + Vec_IntPushTwo( vArray, Entry, i ); + } + return vArray; +} + +/**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; +} +static inline int Gia_ObjEvalEdgeDelay( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay ) +{ + int i, iFan, Delay, DelayMax = 0; + assert( 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); + DelayMax = Abc_MaxInt( DelayMax, Delay ); + } + 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) ); + Gia_ManForEachLut( p, iLut ) + Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) ); + Gia_ManForEachCoDriverId( p, iLut, k ) + DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(p->vEdgeDelay, iLut) ); + return DelayMax; +} + + +/**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 i, iFan, Status[4], Delay[4]; + int DelayMax = 0, nCountMax = 0; + int iFanMax1 = -1, iFanMax2 = -1; + int iMax1 = -1, iMax2 = -1; + assert( Gia_ObjIsLut(p, iObj) ); + assert( Gia_ObjLutSize(p, iObj) <= 4 ); + Vec_IntWriteEntry(vEdge1, iObj, 0); + Vec_IntWriteEntry(vEdge2, iObj, 0); + Gia_LutForEachFanin( p, iObj, iFan, i ) + { + Status[i] = Sbm_ObjEdgeCount( iFan, vEdge1, vEdge2 ); + Delay[i] = Vec_IntEntry( vDelay, iFan ) + 1; + if ( DelayMax < Delay[i] ) + { + DelayMax = Delay[i]; + iFanMax1 = iFan; + iMax1 = i; + nCountMax = 1; + } + else if ( DelayMax == Delay[i] ) + { + iFanMax2 = iFan; + iMax2 = i; + nCountMax++; + } + } + assert( nCountMax > 0 ); + if ( nCountMax == 1 && Status[iMax1] <= 1 ) + { + Sbm_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 ); + Sbm_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 ); + Vec_IntWriteEntry( vDelay, iObj, DelayMax-1 ); + return 1; + } + if ( nCountMax == 2 && Status[iMax1] <= 1 && Status[iMax2] <= 1 ) + { + Sbm_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 ); + Sbm_ObjEdgeAdd( iFanMax2, iObj, vEdge1, vEdge2 ); + Sbm_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 ); + Sbm_ObjEdgeAdd( iObj, iFanMax2, vEdge1, vEdge2 ); + Vec_IntWriteEntry( vDelay, iObj, DelayMax-1 ); + return 2; + } + Vec_IntWriteEntry( vDelay, iObj, DelayMax ); + return 0; +} +int Gia_ManComputeEdgeDelay( Gia_Man_t * p ) +{ + int k, iLut, DelayMax = 0, EdgeCount = 0; + Vec_IntFreeP( &p->vEdgeDelay ); + Vec_IntFreeP( &p->vEdge1 ); + Vec_IntFreeP( &p->vEdge1 ); + p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) ); + p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) ); + p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) ); + Gia_ManForEachLut( p, iLut ) + EdgeCount += Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2 ); + Gia_ManForEachCoDriverId( p, iLut, k ) + DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(p->vEdgeDelay, iLut) ); + assert( 2 * EdgeCount == Vec_IntCountPositive(p->vEdge1) + Vec_IntCountPositive(p->vEdge2) ); + printf( "The number of edges = %d. ", EdgeCount ); + printf( "Delay = %d.\n", DelayMax ); + return DelayMax; +} + +/**Function************************************************************* + + Synopsis [Finds edge assignment to reduce delay.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Gia_ManComputeEdgeDelay2( Gia_Man_t * p ) +{ + return 0; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/aig/gia/giaMan.c b/src/aig/gia/giaMan.c index ea25c4ab..cc93d4b8 100644 --- a/src/aig/gia/giaMan.c +++ b/src/aig/gia/giaMan.c @@ -94,6 +94,9 @@ void Gia_ManStop( Gia_Man_t * p ) Vec_VecFreeP( &p->vClockDoms ); Vec_IntFreeP( &p->vCofVars ); Vec_IntFreeP( &p->vLutConfigs ); + Vec_IntFreeP( &p->vEdgeDelay ); + Vec_IntFreeP( &p->vEdge1 ); + Vec_IntFreeP( &p->vEdge2 ); Vec_IntFreeP( &p->vUserPiIds ); Vec_IntFreeP( &p->vUserPoIds ); Vec_IntFreeP( &p->vUserFfIds ); @@ -387,6 +390,27 @@ void Gia_ManPrintChoiceStats( Gia_Man_t * p ) Gia_ManCleanMark0( p ); } + +/**Function************************************************************* + + Synopsis [Prints stats for the AIG.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Gia_ManPrintEdges( Gia_Man_t * p ) +{ + printf( "Edges (Q=2) : " ); + printf( "edge =%8d ", (Vec_IntCountPositive(p->vEdge1) + Vec_IntCountPositive(p->vEdge2))/2 ); + printf( "lut =%5d", Gia_ManEvalEdgeDelay(p) ); + printf( "\n" ); + return 0; +} + /**Function************************************************************* Synopsis [Prints stats for the AIG.] @@ -477,6 +501,8 @@ void Gia_ManPrintStats( Gia_Man_t * p, Gps_Par_t * pPars ) Gia_ManPrintNpnClasses( p ); if ( p->vPacking ) Gia_ManPrintPackingStats( p ); + if ( p->vEdge1 ) + Gia_ManPrintEdges( p ); if ( pPars && pPars->fLutProf && Gia_ManHasMapping(p) ) Gia_ManPrintLutStats( p ); if ( p->pPlacement ) diff --git a/src/aig/gia/module.make b/src/aig/gia/module.make index 157bf867..cebb73eb 100644 --- a/src/aig/gia/module.make +++ b/src/aig/gia/module.make @@ -16,6 +16,7 @@ SRC += src/aig/gia/giaAig.c \ src/aig/gia/giaCTas.c \ src/aig/gia/giaDfs.c \ src/aig/gia/giaDup.c \ + src/aig/gia/giaEdge.c \ src/aig/gia/giaEmbed.c \ src/aig/gia/giaEnable.c \ src/aig/gia/giaEquiv.c \ -- cgit v1.2.3