From 65b10c0327ce232ba999d51d00a52db53d52bea0 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 4 Dec 2018 23:04:13 -0800 Subject: Experiments with retiming. --- src/base/abci/abc.c | 8 ++--- src/base/wlc/wlcNtk.c | 33 +++++++++++++++++++- src/base/wlc/wlcShow.c | 18 ++++++----- src/base/wln/wlnNdr.c | 15 +++++++-- src/base/wln/wlnRetime.c | 80 +++++++++++++++++++++++++++++++++++++++--------- 5 files changed, 125 insertions(+), 29 deletions(-) diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 3a3ccac6..5546aec9 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -30073,7 +30073,7 @@ int Abc_CommandAbc9Write( Abc_Frame_t * pAbc, int argc, char ** argv ) int fWriteNewLine = 0; int fVerbose = 0; Extra_UtilGetoptReset(); - while ( ( c = Extra_UtilGetopt( argc, argv, "upmlcvh" ) ) != EOF ) + while ( ( c = Extra_UtilGetopt( argc, argv, "upmlnvh" ) ) != EOF ) { switch ( c ) { @@ -30089,7 +30089,7 @@ int Abc_CommandAbc9Write( Abc_Frame_t * pAbc, int argc, char ** argv ) case 'l': fMiniLut ^= 1; break; - case 'c': + case 'n': fWriteNewLine ^= 1; break; case 'v': @@ -30131,13 +30131,13 @@ int Abc_CommandAbc9Write( Abc_Frame_t * pAbc, int argc, char ** argv ) return 0; usage: - Abc_Print( -2, "usage: &w [-upmlcvh] \n" ); + Abc_Print( -2, "usage: &w [-upmlnvh] \n" ); Abc_Print( -2, "\t writes the current AIG into the AIGER file\n" ); Abc_Print( -2, "\t-u : toggle writing canonical AIG structure [default = %s]\n", fUnique? "yes" : "no" ); Abc_Print( -2, "\t-p : toggle writing Verilog with 'and' and 'not' [default = %s]\n", fVerilog? "yes" : "no" ); Abc_Print( -2, "\t-m : toggle writing MiniAIG rather than AIGER [default = %s]\n", fMiniAig? "yes" : "no" ); Abc_Print( -2, "\t-l : toggle writing MiniLUT rather than AIGER [default = %s]\n", fMiniLut? "yes" : "no" ); - Abc_Print( -2, "\t-c : toggle writing \'\\n\' after \'c\' in the AIGER file [default = %s]\n", fWriteNewLine? "yes": "no" ); + Abc_Print( -2, "\t-n : toggle writing \'\\n\' after \'c\' in the AIGER file [default = %s]\n", fWriteNewLine? "yes": "no" ); Abc_Print( -2, "\t-v : toggle verbose output [default = %s]\n", fVerbose? "yes": "no" ); Abc_Print( -2, "\t-h : print the command usage\n"); Abc_Print( -2, "\t : the file name\n"); diff --git a/src/base/wlc/wlcNtk.c b/src/base/wlc/wlcNtk.c index 4ac0c66c..52e2d9a1 100644 --- a/src/base/wlc/wlcNtk.c +++ b/src/base/wlc/wlcNtk.c @@ -305,7 +305,7 @@ int Wlc_NtkMemUsage( Wlc_Ntk_t * p ) SeeAlso [] ***********************************************************************/ -int Wlc_NtkCreateLevels( Wlc_Ntk_t * p ) +int Wlc_NtkCreateLevels_( Wlc_Ntk_t * p ) { Wlc_Obj_t * pObj; int i, k, iFanin, Level, LevelMax = 0; @@ -344,6 +344,37 @@ int Wlc_NtkCreateLevelsRev( Wlc_Ntk_t * p ) return LevelMax; } +/**Function************************************************************* + + Synopsis [Assigns object levels.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Wlc_NtkCreateLevels_rec( Wlc_Ntk_t * p, Wlc_Obj_t * pObj ) +{ + int k, iFanin, Level = 0; + if ( Vec_IntEntry(&p->vLevels, Wlc_ObjId(p, pObj)) > 0 ) + return; + Wlc_ObjForEachFanin( pObj, iFanin, k ) if ( iFanin ) + Wlc_NtkCreateLevels_rec( p, Wlc_NtkObj(p, iFanin) ); + Wlc_ObjForEachFanin( pObj, iFanin, k ) if ( iFanin ) + Level = Abc_MaxInt( Level, Wlc_ObjLevelId(p, iFanin) ); + Vec_IntWriteEntry( &p->vLevels, Wlc_ObjId(p, pObj), Level + 1 ); +} +int Wlc_NtkCreateLevels( Wlc_Ntk_t * p ) +{ + Wlc_Obj_t * pObj; int i; + Vec_IntFill( &p->vLevels, Wlc_NtkObjNumMax(p), 0 ); + Wlc_NtkForEachCo( p, pObj, i ) + Wlc_NtkCreateLevels_rec( p, pObj ); + return Vec_IntFindMax( &p->vLevels ); +} + /**Function************************************************************* Synopsis [Collects statistics for each side of the miter.] diff --git a/src/base/wlc/wlcShow.c b/src/base/wlc/wlcShow.c index dcd98ebc..6257fb6e 100644 --- a/src/base/wlc/wlcShow.c +++ b/src/base/wlc/wlcShow.c @@ -66,7 +66,11 @@ void Wlc_NtkDumpDot( Wlc_Ntk_t * p, char * pFileName, Vec_Int_t * vBold ) pNode->Mark = 1; // compute levels - LevelMax = 1 + Wlc_NtkCreateLevelsRev( p ); + LevelMax = 1 + Wlc_NtkCreateLevels( p ); + +// Wlc_NtkForEachObj( p, pNode, i ) +// printf( "Obj=%d Lev=%d\n", i, Wlc_ObjLevel(p, pNode) ); +// printf( "\n" ); // write the DOT header fprintf( pFile, "# %s\n", "WLC structure generated by ABC" ); @@ -188,7 +192,7 @@ void Wlc_NtkDumpDot( Wlc_Ntk_t * p, char * pFileName, Vec_Int_t * vBold ) if ( pNode->Type == WLC_OBJ_CONST ) { //char * pName = Wlc_ObjName(p, i); - fprintf( pFile, " Node%d [label = \"%d\'h", i, Wlc_ObjRange(pNode) ); + fprintf( pFile, " Node%d [label = \"%d:%d\'h", i, i, Wlc_ObjRange(pNode) ); if ( Wlc_ObjRange(pNode) > 64 ) { Abc_TtPrintHexArrayRev( pFile, (word *)Wlc_ObjConstValue(pNode), 16 ); @@ -201,15 +205,15 @@ void Wlc_NtkDumpDot( Wlc_Ntk_t * p, char * pFileName, Vec_Int_t * vBold ) else if ( pNode->Type == WLC_OBJ_BUF || pNode->Type == WLC_OBJ_MUX ) fprintf( pFile, " Node%d [label = \"%d\"", i, Wlc_ObjRange(pNode) ); else if ( pNode->Type >= WLC_OBJ_LOGIC_NOT && pNode->Type <= WLC_OBJ_COMP_MOREEQU ) - fprintf( pFile, " Node%d [label = \"%s\"", i, Wlc_ObjTypeName(pNode) ); + fprintf( pFile, " Node%d [label = \"%d:%s\"", i, i, Wlc_ObjTypeName(pNode) ); else - fprintf( pFile, " Node%d [label = \"%s %d\"", i, Wlc_ObjTypeName(pNode), Wlc_ObjRange(pNode) ); + fprintf( pFile, " Node%d [label = \"%d:%s %d\"", i, i, Wlc_ObjTypeName(pNode), Wlc_ObjRange(pNode) ); if ( pNode->Type == WLC_OBJ_ARI_MULTI ) fprintf( pFile, ", shape = doublecircle" ); else if ( pNode->Type >= WLC_OBJ_COMP_EQU && pNode->Type <= WLC_OBJ_COMP_MOREEQU ) fprintf( pFile, ", shape = diamond" ); - else if ( pNode->Type == WLC_OBJ_BIT_SELECT || pNode->Type == WLC_OBJ_BIT_CONCAT ) + else if ( pNode->Type == WLC_OBJ_BIT_SELECT || pNode->Type == WLC_OBJ_BIT_CONCAT || pNode->Type == WLC_OBJ_FF ) fprintf( pFile, ", shape = box" ); else if ( pNode->Type == WLC_OBJ_BUF || pNode->Type == WLC_OBJ_BIT_ZEROPAD || pNode->Type == WLC_OBJ_BIT_SIGNEXT ) fprintf( pFile, ", shape = triangle" ); @@ -237,7 +241,7 @@ void Wlc_NtkDumpDot( Wlc_Ntk_t * p, char * pFileName, Vec_Int_t * vBold ) { if ( vBold && !pNode->Mark ) continue; - fprintf( pFile, " Node%d [label = \"%s %d\"", Wlc_ObjId(p, pNode), Wlc_ObjName(p, Wlc_ObjId(p, pNode)), Wlc_ObjRange(pNode) ); + fprintf( pFile, " Node%d [label = \"%d:%s %d\"", Wlc_ObjId(p, pNode), Wlc_ObjId(p, pNode), Wlc_ObjName(p, Wlc_ObjId(p, pNode)), Wlc_ObjRange(pNode) ); fprintf( pFile, ", shape = %s", i < Wlc_NtkPiNum(p) ? "triangle" : "box" ); fprintf( pFile, ", color = coral, fillcolor = coral" ); fprintf( pFile, "];\n" ); @@ -298,7 +302,7 @@ void Wlc_NtkDumpDot( Wlc_Ntk_t * p, char * pFileName, Vec_Int_t * vBold ) if ( vBold && !pNode->Mark ) continue; // generate the edge from this node to the next - Wlc_ObjForEachFanin( pNode, iFanin, k ) + Wlc_ObjForEachFanin( pNode, iFanin, k ) if ( iFanin ) { fprintf( pFile, "Node%d", i ); fprintf( pFile, " -> " ); diff --git a/src/base/wln/wlnNdr.c b/src/base/wln/wlnNdr.c index c87100a2..5daee6a7 100644 --- a/src/base/wln/wlnNdr.c +++ b/src/base/wln/wlnNdr.c @@ -268,7 +268,8 @@ Wln_Ntk_t * Wln_NtkFromNdr( void * pData ) assert( i == Vec_PtrSize(vConstStrings) ); Vec_PtrFree( vConstStrings ); //Ndr_NtkPrintObjects( pNtk ); - //Wln_WriteVer( pNtk, "temp_ndr.v", 0, 0 ); + Wln_WriteVer( pNtk, "temp_ndr.v" ); + printf( "Dumped design \"%s\" into file \"temp_ndr.v\".\n", pNtk->pName ); // derive topological order pNtk = Wln_NtkDupDfs( pTemp = pNtk ); Wln_NtkFree( pTemp ); @@ -313,8 +314,18 @@ void Wln_NtkRetimeTest( char * pFileName ) Wln_Ntk_t * pNtk = Wln_NtkFromNdr( pData ); Ndr_Delete( pData ); if ( !Wln_NtkHasInstId(pNtk) ) + { + int iObj; printf( "The design has no delay information.\n" ); - else + Wln_NtkCleanInstId(pNtk); + Wln_NtkForEachObj( pNtk, iObj ) + if ( Wln_ObjIsFf(pNtk, iObj) ) + Wln_ObjSetInstId( pNtk, iObj, 1 ); + else if ( !Wln_ObjIsCio(pNtk, iObj) && Wln_ObjFaninNum(pNtk, iObj) > 0 ) + Wln_ObjSetInstId( pNtk, iObj, 10 ); + printf( "Assuming user-specified delays for internal nodes.\n" ); + } + //else { Vec_Int_t * vMoves = Wln_NtkRetime( pNtk ); Vec_IntPrint( vMoves ); diff --git a/src/base/wln/wlnRetime.c b/src/base/wln/wlnRetime.c index 459af2d9..711e8db1 100644 --- a/src/base/wln/wlnRetime.c +++ b/src/base/wln/wlnRetime.c @@ -62,6 +62,41 @@ static inline int * Wln_RetFanouts( Wln_Ret_t * p, int i ) { return Vec_IntEnt /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// +/**Function************************************************************* + + Synopsis [Printing procedure.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Wln_RetPrintObj( Wln_Ret_t * p, int iObj ) +{ + int k, iFanin, Type = Wln_ObjType(p->pNtk, iObj), * pLink; + printf( "Obj %6d : Type = %6s Fanins = %d : ", iObj, Abc_OperName(Type), Wln_ObjFaninNum(p->pNtk, iObj) ); + Wln_RetForEachFanin( p, iObj, iFanin, pLink, k ) + { + printf( "%5d ", iFanin ); + if ( !pLink[0] ) + continue; + printf( "(%d : %d %d) ", pLink[0], + Vec_IntEntry(&p->vEdgeLinks, pLink[0]), + Vec_IntEntry(&p->vEdgeLinks, pLink[0]+1) ); + } + printf( "\n" ); +} +void Wln_RetPrint( Wln_Ret_t * p ) +{ + int iObj; + printf( "Printing %d objects of network \"%s\":\n", Wln_NtkObjNum(p->pNtk), p->pNtk->pName ); + Wln_NtkForEachObj( p->pNtk, iObj ) + Wln_RetPrintObj( p, iObj ); + printf( "\n" ); +} + /**Function************************************************************* Synopsis [Retiming manager.] @@ -187,6 +222,7 @@ int Wln_RetPropDelay_rec( Wln_Ret_t * p, int iObj ) int k, iFanin, * pLink, * pDelay = Vec_IntEntryP( &p->vPathDelays, iObj ); if ( *pDelay >= 0 ) return *pDelay; + *pDelay = 0; Wln_RetForEachFanin( p, iObj, iFanin, pLink, k ) if ( pLink[0] ) *pDelay = Abc_MaxInt(*pDelay, 0); @@ -211,7 +247,7 @@ int Wln_RetPropDelay( Wln_Ret_t * p, Vec_Int_t * vFront ) } Vec_IntClear( &p->vSinks ); Wln_NtkForEachObj( p->pNtk, iObj ) - if ( !Wln_ObjIsCo(p->pNtk, iObj) ) + if ( !Wln_ObjIsCio(p->pNtk, iObj) ) { int Delay = Wln_RetPropDelay_rec(p, iObj); if ( DelayMax == Delay ) @@ -222,24 +258,27 @@ int Wln_RetPropDelay( Wln_Ret_t * p, Vec_Int_t * vFront ) Vec_IntFill( &p->vSinks, 1, iObj ); } } + +// Vec_IntForEachEntry( &p->vPathDelays, iObj, i ) +// printf( "Obj = %d. Delay = %d.\n", i, iObj ); +// printf( "\n" ); + +// printf( "Sinks: " ); +// Vec_IntPrint( &p->vSinks ); + return DelayMax; } void Wln_RetFindSources_rec( Wln_Ret_t * p, int iObj ) { - int k, iFanin, * pLink, FaninDelay, fTerm = 1; + int k, iFanin, * pLink, FaninDelay; if ( Wln_ObjIsCi(p->pNtk, iObj) || Wln_ObjCheckTravId(p->pNtk, iObj) ) return; FaninDelay = Vec_IntEntry( &p->vPathDelays, iObj ) - Vec_IntEntry( &p->vNodeDelays, iObj ); Wln_RetForEachFanin( p, iObj, iFanin, pLink, k ) - { - if ( !pLink[0] ) - continue; - fTerm = 0; - if ( Vec_IntEntry(&p->vPathDelays, iFanin) == FaninDelay ) + if ( !pLink[0] && Vec_IntEntry(&p->vPathDelays, iFanin) == FaninDelay ) Wln_RetFindSources_rec( p, iFanin ); - } - if ( fTerm ) + if ( FaninDelay == 0 ) Vec_IntPush( &p->vSources, iObj ); } void Wln_RetFindSources( Wln_Ret_t * p ) @@ -249,6 +288,9 @@ void Wln_RetFindSources( Wln_Ret_t * p ) Wln_NtkIncrementTravId( p->pNtk ); Vec_IntForEachEntry( &p->vSinks, iObj, i ) Wln_RetFindSources_rec( p, iObj ); + +// printf( "Sources: " ); +// Vec_IntPrint( &p->vSources ); } /**Function************************************************************* @@ -342,8 +384,8 @@ int Wln_RetRemoveOneFanin( Wln_Ret_t * p, int iObj ) Wln_RetForEachFanin( p, iObj, iFanin, pLink, k ) { assert( pLink[0] ); - pFanins[2*k+1] = Vec_IntEntry( &p->vEdgeLinks, pLink[0] ); iFlop = Vec_IntEntry( &p->vEdgeLinks, pLink[0] + 1 ); + pFanins[2*k+1] = Vec_IntEntry( &p->vEdgeLinks, pLink[0] ); assert( Wln_ObjIsFf( p->pNtk, iFlop ) ); if ( iFlop1 == -1 ) iFlop1 = iFlop; @@ -368,12 +410,14 @@ int Wln_RetRemoveOneFanout( Wln_Ret_t * p, int iObj ) } void Wln_RetInsertOneFanin( Wln_Ret_t * p, int iObj, int iFlop ) { - int k, iFanin, * pLink; + int k, iHead, iFanin, * pLink; int * pFanins = Wln_RetFanins( p, iObj ); assert( Wln_ObjIsFf( p->pNtk, iFlop ) ); Wln_RetForEachFanin( p, iObj, iFanin, pLink, k ) { - int iHead = pFanins[2*k+1]; + if ( Wln_ObjIsFf(p->pNtk, iObj) && k > 0 ) + continue; + iHead = pFanins[2*k+1]; pFanins[2*k+1] = Vec_IntSize(&p->vEdgeLinks); Vec_IntPushTwo( &p->vEdgeLinks, iHead, iFlop ); } @@ -386,7 +430,6 @@ void Wln_RetInsertOneFanout( Wln_Ret_t * p, int iObj, int iFlop ) { if ( pLink[0] ) pLink = Wln_RetHeadToTail( p, pLink ); - pLink = Vec_IntEntryP( &p->vEdgeLinks, pLink[0] ); assert( pLink[0] == 0 ); pLink[0] = Vec_IntSize(&p->vEdgeLinks); Vec_IntPushTwo( &p->vEdgeLinks, 0, iFlop ); @@ -415,13 +458,15 @@ void Wln_RetAddToMoves( Wln_Ret_t * p, Vec_Int_t * vSet, int Delay, int fForward int i, iObj; if ( vSet == NULL ) { + printf( "*** Recording initial move (0, %d)\n", Delay ); Vec_IntPushTwo( &p->vMoves, 0, Delay ); return; } Vec_IntForEachEntry( vSet, iObj, i ) { int NameId = Vec_IntEntry( &p->pNtk->vNameIds, iObj ); - Vec_IntPushTwo( &p->vMoves, fForward ? NameId : -NameId, Delay ); + printf( "*** Recording new move (%d, %d)\n", fForward ? -NameId : NameId, Delay ); + Vec_IntPushTwo( &p->vMoves, fForward ? -NameId : NameId, Delay ); } } @@ -443,11 +488,13 @@ Vec_Int_t * Wln_NtkRetime( Wln_Ntk_t * pNtk ) Vec_Int_t * vSinks = &p->vSinks; Vec_Int_t * vFront = &p->vFront; Vec_Int_t * vMoves = Vec_IntAlloc(0); + //Wln_RetPrint( p ); p->DelayMax = Wln_RetPropDelay( p, NULL ); Wln_RetFindSources( p ); Wln_RetAddToMoves( p, NULL, p->DelayMax, 0 ); while ( Vec_IntSize(vSources) || Vec_IntSize(vSinks) ) { + int DelayMaxPrev = p->DelayMax; int fForward = Vec_IntSize(vSources) && Wln_RetCheckForward( p, vSources ); int fBackward = Vec_IntSize(vSinks) && Wln_RetCheckBackward( p, vSinks ); if ( !fForward && !fBackward ) @@ -466,9 +513,12 @@ Vec_Int_t * Wln_NtkRetime( Wln_Ntk_t * pNtk ) if ( (fForward && !fBackward) || (fForward && fBackward && Vec_IntSize(vSources) < Vec_IntSize(vSinks)) ) Wln_RetRetimeForward( p, vSources ), Vec_IntAppend( vFront, vSources ), fForward = 1, fBackward = 0; else - Wln_RetRetimeBackward( p, vSinks ), Vec_IntAppend( vFront, vSources ), fForward = 0, fBackward = 1; + Wln_RetRetimeBackward( p, vSinks ), Vec_IntAppend( vFront, vSinks ), fForward = 0, fBackward = 1; + //Wln_RetPrint( p ); p->DelayMax = Wln_RetPropDelay( p, vFront ); Wln_RetAddToMoves( p, vFront, p->DelayMax, fForward ); + if ( p->DelayMax > DelayMaxPrev ) + break; Wln_RetFindSources( p ); if ( 2*Vec_IntSize(&p->vEdgeLinks) > Vec_IntCap(&p->vEdgeLinks) ) Vec_IntGrow( &p->vEdgeLinks, 4*Vec_IntSize(&p->vEdgeLinks) ); -- cgit v1.2.3