diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/aig/gia/gia.h | 1 | ||||
-rw-r--r-- | src/aig/gia/giaMan.c | 2 | ||||
-rw-r--r-- | src/aig/gia/giaSweep.c | 325 | ||||
-rw-r--r-- | src/aig/gia/giaTim.c | 19 | ||||
-rw-r--r-- | src/aig/gia/module.make | 1 | ||||
-rw-r--r-- | src/misc/tim/tim.h | 1 | ||||
-rw-r--r-- | src/misc/tim/timMan.c | 141 |
7 files changed, 484 insertions, 6 deletions
diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index 6a1ce0bc..500096e1 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -976,6 +976,7 @@ extern Gia_Man_t * Gia_ManDupWithHierarchy( Gia_Man_t * p, Vec_Int_t ** extern Gia_Man_t * Gia_ManDupWithBoxes( Gia_Man_t * p, Gia_Man_t * pBoxes ); extern int Gia_ManLevelWithBoxes( Gia_Man_t * p ); extern int Gia_ManVerifyWithBoxes( Gia_Man_t * pGia, void * pParsInit ); +extern void * Gia_ManUpdateTimMan( Gia_Man_t * p, Vec_Int_t * vBoxPres ); /*=== giaTruth.c ===========================================================*/ extern word Gia_ObjComputeTruthTable6( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp, Vec_Wrd_t * vTruths ); extern int Gia_ObjCollectInternal( Gia_Man_t * p, Gia_Obj_t * pObj ); diff --git a/src/aig/gia/giaMan.c b/src/aig/gia/giaMan.c index 9e05bd40..493d3ed1 100644 --- a/src/aig/gia/giaMan.c +++ b/src/aig/gia/giaMan.c @@ -334,6 +334,8 @@ void Gia_ManPrintStats( Gia_Man_t * p, int fTents, int fSwitch, int fCut ) Gia_ManPrintPackingStats( p ); if ( p->pPlacement ) Gia_ManPrintPlacement( p ); + if ( p->pManTime ) + Tim_ManPrintStats( p->pManTime ); // print register classes Gia_ManPrintFlopClasses( p ); Gia_ManPrintGateClasses( p ); diff --git a/src/aig/gia/giaSweep.c b/src/aig/gia/giaSweep.c new file mode 100644 index 00000000..184bf91c --- /dev/null +++ b/src/aig/gia/giaSweep.c @@ -0,0 +1,325 @@ +/**CFile**************************************************************** + + FileName [giaSweep.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Scalable AIG package.] + + Synopsis [Sweeping of GIA manager.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: giaSweep.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "gia.h" +#include "giaAig.h" +#include "proof/dch/dch.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ + +/**Function************************************************************* + + Synopsis [Mark GIA nodes that feed into POs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Gia_ManFraigCheckCis( Gia_Man_t * p, Gia_Obj_t * pObj ) +{ + for ( assert( Gia_ObjIsCi(pObj) ); Gia_ObjIsCi(pObj); pObj-- ) + if ( Gia_ObjIsTravIdCurrent(p, pObj) ) + return 1; + return 0; +} +Gia_Obj_t * Gia_ManFraigMarkCis( Gia_Man_t * p, Gia_Obj_t * pObj, int fMark ) +{ + for ( assert( Gia_ObjIsCi(pObj) ); Gia_ObjIsCi(pObj); pObj-- ) + if ( fMark ) + Gia_ObjSetTravIdCurrent( p, pObj ); + return pObj; +} +Gia_Obj_t * Gia_ManFraigMarkCos( Gia_Man_t * p, Gia_Obj_t * pObj, int fMark ) +{ + for ( assert( Gia_ObjIsCo(pObj) ); Gia_ObjIsCo(pObj); pObj-- ) + if ( fMark ) + Gia_ObjSetTravIdCurrent( p, pObj ); + return pObj; +} +Gia_Obj_t * Gia_ManFraigMarkAnd( Gia_Man_t * p, Gia_Obj_t * pObj ) +{ + for ( assert( Gia_ObjIsAnd(pObj) ); Gia_ObjIsAnd(pObj); pObj-- ) + if ( Gia_ObjIsTravIdCurrent(p, pObj) ) + { + Gia_ObjSetTravIdCurrent( p, Gia_ObjFanin0(pObj) ); + Gia_ObjSetTravIdCurrent( p, Gia_ObjFanin1(pObj) ); + } + return pObj; +} +Gia_Man_t * Gia_ManFraigCreateGia( Gia_Man_t * p ) +{ + Vec_Int_t * vBoxPres; + Gia_Man_t * pNew; + Gia_Obj_t * pObj; + int i, fLabelPos; + assert( p->pManTime != NULL ); + // start marks + Gia_ManIncrementTravId( p ); + Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) ); + vBoxPres = Vec_IntAlloc( 1000 ); + // mark primary outputs + fLabelPos = 1; + pObj = Gia_ManObj( p, Gia_ManObjNum(p) - 1 ); + assert( Gia_ObjIsCo(pObj) ); + while ( Gia_ObjIsCo(pObj) ) + { + pObj = Gia_ManFraigMarkCos( p, pObj, fLabelPos ); + if ( Gia_ObjIsAnd(pObj) ) + pObj = Gia_ManFraigMarkAnd( p, pObj ); + assert( Gia_ObjIsCi(pObj) ); + fLabelPos = Gia_ManFraigCheckCis(p, pObj); + pObj = Gia_ManFraigMarkCis( p, pObj, fLabelPos ); + Vec_IntPush( vBoxPres, fLabelPos ); + } + Vec_IntPop( vBoxPres ); + Vec_IntReverseOrder( vBoxPres ); + assert( Gia_ObjIsConst0(pObj) ); + // mark primary inputs + Gia_ManForEachObj1( p, pObj, i ) + if ( Gia_ObjIsCi(pObj) ) + Gia_ObjSetTravIdCurrent( p, pObj ); + else + break; + // duplicate marked entries + pNew = Gia_ManStart( Gia_ManObjNum(p) ); + pNew->pName = Abc_UtilStrsav( p->pName ); + pNew->pSpec = Abc_UtilStrsav( p->pSpec ); + Gia_ManConst0(p)->Value = 0; + Gia_ManForEachObj1( p, pObj, i ) + { + if ( !Gia_ObjIsTravIdCurrent(p, pObj) ) + continue; + if ( Gia_ObjIsCi(pObj) ) + pObj->Value = Gia_ManAppendCi(pNew); + else if ( Gia_ObjIsAnd(pObj) ) + pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + else if ( Gia_ObjIsCo(pObj) ) + pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); + else assert( 0 ); + } + // update timing manager + pNew->pManTime = Gia_ManUpdateTimMan( p, vBoxPres ); + Vec_IntFree( vBoxPres ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManFraigExtractGia( Gia_Man_t * p, int * pReprs ) +{ + Gia_Man_t * pNew; + Gia_Obj_t * pObj; + int i; + assert( p->pSibls == NULL ); + assert( Gia_ManRegNum(p) == 0 ); + pNew = Gia_ManStart( Gia_ManObjNum(p) ); + pNew->pName = Abc_UtilStrsav( p->pName ); + pNew->pSpec = Abc_UtilStrsav( p->pSpec ); + Gia_ManHashAlloc( pNew ); + // copy const and real PIs + Gia_ManFillValue( p ); + Gia_ManForEachObj( p, pObj, i ) + { + if ( Gia_ObjIsAnd(pObj) ) + { + assert( pReprs[i] == -1 || Abc_Lit2Var(pReprs[i]) < i ); + if ( pReprs[i] == -1 ) + pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + else + pObj->Value = Abc_LitNotCond( Gia_ObjValue(Gia_ManObj(p, Abc_Lit2Var(pReprs[i]))), Abc_LitIsCompl(pReprs[i]) ); + } + else if ( Gia_ObjIsCi(pObj) ) + pObj->Value = Gia_ManAppendCi( pNew ); + else if ( Gia_ObjIsCo(pObj) ) + pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); + else if ( Gia_ObjIsConst0(pObj) ) + pObj->Value = 0; + else assert( 0 ); + } + Gia_ManHashStop( pNew ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [Computes representatives in terms of the original objects.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int * Gia_ManFraigSelectReprs( Gia_Man_t * p, Gia_Man_t * pGia, int fVerbose ) +{ + Gia_Obj_t * pObj; + int * pReprs = ABC_FALLOC( int, Gia_ManObjNum(p) ); + int * pGia2Abc = ABC_FALLOC( int, Gia_ManObjNum(pGia) ); + int i, iLitGia, iLitGia2, iReprGia, fCompl; + int nConsts = 0, nReprs = 0; + pGia2Abc[0] = 0; + Gia_ManSetPhase( pGia ); + Gia_ManForEachObj1( p, pObj, i ) + { + if ( Gia_ObjIsCo(pObj) ) + continue; + assert( Gia_ObjIsCi(pObj) || Gia_ObjIsAnd(pObj) ); + iLitGia = Gia_ObjValue(pObj); + if ( iLitGia == -1 ) + continue; + iReprGia = Gia_ObjReprSelf( pGia, Abc_Lit2Var(iLitGia) ); + if ( pGia2Abc[iReprGia] == -1 ) + pGia2Abc[iReprGia] = i; + else + { +// iLitGia2 = Abc2_ObjCopyId( p, pGia2Abc[iReprGia] ); + iLitGia2 = Gia_ObjValue( Gia_ManObj(p, pGia2Abc[iReprGia]) ); + assert( Gia_ObjReprSelf(pGia, Abc_Lit2Var(iLitGia)) == Gia_ObjReprSelf(pGia, Abc_Lit2Var(iLitGia2)) ); + fCompl = Abc_LitIsCompl(iLitGia) ^ Abc_LitIsCompl(iLitGia2); + fCompl ^= Gia_ManObj(pGia, Abc_Lit2Var(iLitGia))->fPhase; + fCompl ^= Gia_ManObj(pGia, Abc_Lit2Var(iLitGia2))->fPhase; + pReprs[i] = Abc_Var2Lit( pGia2Abc[iReprGia], fCompl ); + if ( pGia2Abc[iReprGia] == 0 ) + nConsts++; + else + nReprs++; + } + } + ABC_FREE( pGia2Abc ); + if ( fVerbose ) + printf( "Found %d const reprs and %d other reprs.\n", nConsts, nReprs ); + return pReprs; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManFraigSweepPerform( Gia_Man_t * p, void * pPars ) +{ + Aig_Man_t * pNew; + pNew = Gia_ManToAigSimple( p ); + assert( Gia_ManObjNum(p) == Aig_ManObjNum(pNew) ); + Dch_ComputeEquivalences( pNew, (Dch_Pars_t *)pPars ); + Gia_ManReprFromAigRepr( pNew, p ); + Aig_ManStop( pNew ); +} + +/**Function************************************************************* + + Synopsis [Reduces root model with scorr.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManFraigSweep( Gia_Man_t * p, void * pPars ) +{ + Gia_Man_t * pGia, * pNew, * pTemp; + int * pReprs; + assert( Gia_ManRegNum(p) == 0 ); + if ( p->pManTime == NULL ) + { + Gia_ManFraigSweepPerform( p, pPars ); + pNew = Gia_ManEquivReduce( p, 1, 0, 0 ); + if ( pNew == NULL ) + return Gia_ManDup(p); + return pNew; + } + if ( p->pAigExtra == NULL ) + { + printf( "Timing manager is given but there is no GIA of boxes.\n" ); + return NULL; + } + // find global equivalences + pGia = Gia_ManDupWithBoxes( p, p->pAigExtra ); + Gia_ManFraigSweepPerform( pGia, pPars ); + // transfer equivalences + pNew = Gia_ManDupWithHierarchy( p, NULL ); + pReprs = Gia_ManFraigSelectReprs( pNew, pGia, ((Dch_Pars_t *)pPars)->fVerbose ); + Gia_ManStop( pGia ); + // reduce AIG + pNew = Gia_ManFraigExtractGia( pTemp = pNew, pReprs ); + Gia_ManStop( pTemp ); + ABC_FREE( pReprs ); + // order reduced AIG + pNew->pManTime = p->pManTime; + pNew = Gia_ManDupWithHierarchy( pTemp = pNew, NULL ); + pTemp->pManTime = NULL; + Gia_ManStop( pTemp ); + // derive new AIG + assert( pTemp->pManTime == NULL ); + pNew = Gia_ManFraigCreateGia( pTemp = pNew ); + assert( pNew->pManTime != NULL ); + Gia_ManStop( pTemp ); + return pNew; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/aig/gia/giaTim.c b/src/aig/gia/giaTim.c index 03018513..d6b67d7c 100644 --- a/src/aig/gia/giaTim.c +++ b/src/aig/gia/giaTim.c @@ -559,6 +559,25 @@ int Gia_ManVerifyWithBoxes( Gia_Man_t * pGia, void * pParsInit ) return Status; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void * Gia_ManUpdateTimMan( Gia_Man_t * p, Vec_Int_t * vBoxPres ) +{ + assert( p->pManTime != NULL ); + assert( Tim_ManBoxNum(p->pManTime) == Vec_IntSize(vBoxPres) ); + return Tim_ManTrim( p->pManTime, vBoxPres ); + +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/aig/gia/module.make b/src/aig/gia/module.make index 169b71e7..1b31ff3d 100644 --- a/src/aig/gia/module.make +++ b/src/aig/gia/module.make @@ -36,6 +36,7 @@ SRC += src/aig/gia/gia.c \ src/aig/gia/giaSort.c \ src/aig/gia/giaSpeedup.c \ src/aig/gia/giaSupMin.c \ + src/aig/gia/giaSweep.c \ src/aig/gia/giaSwitch.c \ src/aig/gia/giaTest.c \ src/aig/gia/giaTim.c \ diff --git a/src/misc/tim/tim.h b/src/misc/tim/tim.h index 48bef93a..66181a9c 100644 --- a/src/misc/tim/tim.h +++ b/src/misc/tim/tim.h @@ -132,6 +132,7 @@ extern int Tim_ManGetArrsReqs( Tim_Man_t * p, Vec_Flt_t ** pvInArrs, extern void Tim_ManStop( Tim_Man_t * p ); extern void Tim_ManStopP( Tim_Man_t ** p ); extern void Tim_ManPrint( Tim_Man_t * p ); +extern void Tim_ManPrintStats( Tim_Man_t * p ); extern int Tim_ManCiNum( Tim_Man_t * p ); extern int Tim_ManCoNum( Tim_Man_t * p ); extern int Tim_ManPiNum( Tim_Man_t * p ); diff --git a/src/misc/tim/timMan.c b/src/misc/tim/timMan.c index f2245a6a..4c61bf1c 100644 --- a/src/misc/tim/timMan.c +++ b/src/misc/tim/timMan.c @@ -93,13 +93,13 @@ Tim_Man_t * Tim_ManDup( Tim_Man_t * p, int fUnitDelay ) // create new manager pNew = Tim_ManStart( p->nCis, p->nCos ); // copy box connectivity information - memcpy( pNew->pCis, p->pCis, sizeof(Tim_Obj_t) * p->nCis ); - memcpy( pNew->pCos, p->pCos, sizeof(Tim_Obj_t) * p->nCos ); + memcpy( pNew->pCis, p->pCis, sizeof(Tim_Obj_t) * p->nCis ); // why do we need this? + memcpy( pNew->pCos, p->pCos, sizeof(Tim_Obj_t) * p->nCos ); // why do we need this? // clear traversal IDs - Tim_ManForEachCi( p, pObj, i ) - pObj->TravId = 0; - Tim_ManForEachCo( p, pObj, i ) - pObj->TravId = 0; + Tim_ManForEachCi( p, pObj, i ) // why do we need this? + pObj->TravId = 0; // why do we need this? + Tim_ManForEachCo( p, pObj, i ) // why do we need this? + pObj->TravId = 0; // why do we need this? if ( fUnitDelay ) { // discretize PI arrival times @@ -148,6 +148,83 @@ Tim_Man_t * Tim_ManDup( Tim_Man_t * p, int fUnitDelay ) /**Function************************************************************* + Synopsis [Trims the timing manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Tim_Man_t * Tim_ManTrim( Tim_Man_t * p, Vec_Int_t * vBoxPres ) +{ + Tim_Man_t * pNew; + Tim_Box_t * pBox; + Tim_Obj_t * pObj; + float * pDelayTable, * pDelayTableNew; + int i, k, nInputs, nOutputs, nRemCis, nRemCos; + assert( Vec_IntSize(vBoxPres) == Tim_ManBoxNum(p) ); + // count the number of CIs and COs due to removed boxes + Tim_ManForEachBox( p, pBox, i ) + if ( Vec_IntEntry(vBoxPres, i) == 0 ) + { + nRemCis += pBox->nOutputs; + nRemCos += pBox->nInputs; + } + if ( nRemCos == 0 && nRemCis == 0 ) + return Tim_ManDup( p, 0 ); + assert( Tim_ManCiNum(p) - Tim_ManPiNum(p) >= nRemCis ); + assert( Tim_ManCoNum(p) - Tim_ManPoNum(p) >= nRemCos ); + // create new manager + pNew = Tim_ManStart( p->nCis - nRemCis, p->nCos - nRemCos ); + // copy box connectivity information + memcpy( pNew->pCis, p->pCis, sizeof(Tim_Obj_t) * p->nCis ); // why do we need this? + memcpy( pNew->pCos, p->pCos, sizeof(Tim_Obj_t) * p->nCos ); // why do we need this? + // clear traversal IDs + Tim_ManForEachCi( p, pObj, i ) // why do we need this? + pObj->TravId = 0; // why do we need this? + Tim_ManForEachCo( p, pObj, i ) // why do we need this? + pObj->TravId = 0; // why do we need this? + // duplicate delay tables + if ( Tim_ManDelayTableNum(p) > 0 ) + { + pNew->vDelayTables = Vec_PtrStart( Vec_PtrSize(p->vDelayTables) ); + Tim_ManForEachTable( p, pDelayTable, i ) + { + if ( pDelayTable == NULL ) + continue; + assert( i == (int)pDelayTable[0] ); + nInputs = (int)pDelayTable[1]; + nOutputs = (int)pDelayTable[2]; + pDelayTableNew = ABC_ALLOC( float, 3 + nInputs * nOutputs ); + pDelayTableNew[0] = (int)pDelayTable[0]; + pDelayTableNew[1] = (int)pDelayTable[1]; + pDelayTableNew[2] = (int)pDelayTable[2]; + for ( k = 0; k < nInputs * nOutputs; k++ ) + pDelayTableNew[3+k] = pDelayTable[3+k]; +// assert( (int)pDelayTableNew[0] == Vec_PtrSize(pNew->vDelayTables) ); + assert( Vec_PtrEntry(pNew->vDelayTables, i) == NULL ); + Vec_PtrWriteEntry( pNew->vDelayTables, i, pDelayTableNew ); +//printf( "Finished duplicating delay table %d.\n", i ); + } + } + // duplicate boxes + if ( Tim_ManBoxNum(p) > 0 ) + { + pNew->vBoxes = Vec_PtrAlloc( Tim_ManBoxNum(p) ); + Tim_ManForEachBox( p, pBox, i ) + if ( Vec_IntEntry(vBoxPres, i) ) + Tim_ManCreateBox( pNew, pBox->Inouts[0], pBox->nInputs, + pBox->Inouts[pBox->nInputs], pBox->nOutputs, pBox->iDelayTable ); + } + return pNew; + +} + + +/**Function************************************************************* + Synopsis [Stops the timing manager.] Description [] @@ -392,6 +469,58 @@ void Tim_ManPrint( Tim_Man_t * p ) /**Function************************************************************* + Synopsis [Prints statistics of the timing manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Tim_ManPrintStats( Tim_Man_t * p ) +{ + Tim_Box_t * pBox; + Vec_Int_t * vCounts; + Vec_Ptr_t * vBoxes; + int i, Count, IdMax; + if ( p == NULL ) + return; + Abc_Print( 1, "hierarchy : " ); + printf( "PI/CI = %d/%d PO/CO = %d/%d Box = %d", + Tim_ManPiNum(p), Tim_ManCiNum(p), + Tim_ManPoNum(p), Tim_ManCoNum(p), + Tim_ManBoxNum(p) ); + printf( "\n" ); + if ( Tim_ManBoxNum(p) == 0 ) + return; + IdMax = 0; + Tim_ManForEachBox( p, pBox, i ) + IdMax = Abc_MaxInt( IdMax, pBox->iDelayTable ); + vCounts = Vec_IntStart( IdMax+1 ); + vBoxes = Vec_PtrStart( IdMax+1 ); + Tim_ManForEachBox( p, pBox, i ) + { + Vec_IntAddToEntry( vCounts, pBox->iDelayTable, 1 ); + Vec_PtrWriteEntry( vBoxes, pBox->iDelayTable, pBox ); + } + // print statistics about boxes + Vec_IntForEachEntry( vCounts, Count, i ) + { + if ( Count == 0 ) continue; + pBox = (Tim_Box_t *)Vec_PtrEntry( vBoxes, i ); + printf( " Box %4d ", i ); + printf( "Num = %4d ", Count ); + printf( "Ins = %4d ", pBox->nInputs ); + printf( "Outs = %4d", pBox->nOutputs ); + printf( "\n" ); + } + Vec_IntFree( vCounts ); + Vec_PtrFree( vBoxes ); +} + +/**Function************************************************************* + Synopsis [Read parameters.] Description [] |