From ac787628583903d3762c82e5aa12fa592cb65097 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 15 Jan 2008 08:01:00 -0800 Subject: Version abc80115 --- Makefile | 2 +- abc.dsp | 20 ++ src/aig/aig/aigUtil.c | 32 +- src/base/abci/abc.c | 139 +++++++- src/opt/fret/fretFlow.c | 640 +++++++++++++++++++++++++++++++++++ src/opt/fret/fretInit.c | 743 ++++++++++++++++++++++++++++++++++++++++ src/opt/fret/fretMain.c | 864 +++++++++++++++++++++++++++++++++++++++++++++++ src/opt/fret/fretime.h | 140 ++++++++ src/opt/fret/module.make | 4 + 9 files changed, 2565 insertions(+), 19 deletions(-) create mode 100644 src/opt/fret/fretFlow.c create mode 100644 src/opt/fret/fretInit.c create mode 100644 src/opt/fret/fretMain.c create mode 100644 src/opt/fret/fretime.h create mode 100644 src/opt/fret/module.make diff --git a/Makefile b/Makefile index fcbf0e44..3b680f92 100644 --- a/Makefile +++ b/Makefile @@ -14,7 +14,7 @@ MODULES := src/base/abc src/base/abci src/base/cmd \ src/misc/extra src/misc/mvc src/misc/st src/misc/util \ src/misc/espresso src/misc/nm src/misc/vec src/misc/hash \ src/opt/cut src/opt/dec src/opt/fxu src/opt/rwr \ - src/opt/sim src/opt/ret src/opt/res src/opt/lpk \ + src/opt/sim src/opt/ret src/opt/res src/opt/lpk src/opt/fret \ src/sat/bsat src/sat/csat src/sat/msat src/sat/fraig \ src/aig/ivy src/aig/hop src/aig/rwt src/aig/deco \ src/aig/mem src/aig/dar src/aig/fra src/aig/cnf \ diff --git a/abc.dsp b/abc.dsp index 1cbb582b..60827bb2 100644 --- a/abc.dsp +++ b/abc.dsp @@ -1585,6 +1585,26 @@ SOURCE=.\src\opt\lpk\lpkMux.c SOURCE=.\src\opt\lpk\lpkSets.c # End Source File # End Group +# Begin Group "fret" + +# PROP Default_Filter "" +# Begin Source File + +SOURCE=.\src\opt\fret\fretFlow.c +# End Source File +# Begin Source File + +SOURCE=.\src\opt\fret\fretime.h +# End Source File +# Begin Source File + +SOURCE=.\src\opt\fret\fretInit.c +# End Source File +# Begin Source File + +SOURCE=.\src\opt\fret\fretMain.c +# End Source File +# End Group # End Group # Begin Group "map" diff --git a/src/aig/aig/aigUtil.c b/src/aig/aig/aigUtil.c index 354d94db..f6f34de9 100644 --- a/src/aig/aig/aigUtil.c +++ b/src/aig/aig/aigUtil.c @@ -669,6 +669,10 @@ void Aig_ManDumpBlif( Aig_Man_t * p, char * pFileName ) printf( "Aig_ManDumpBlif(): AIG manager does not have POs.\n" ); return; } + // check if constant is used + Aig_ManForEachPo( p, pObj, i ) + if ( Aig_ObjIsConst1(Aig_ObjFanin0(pObj)) ) + pConst1 = Aig_ManConst1(p); // collect nodes in the DFS order vNodes = Aig_ManDfs( p ); // assign IDs to objects @@ -698,12 +702,14 @@ void Aig_ManDumpBlif( Aig_Man_t * p, char * pFileName ) // write latches if ( Aig_ManRegNum(p) ) { - fprintf( pFile, "\n" ); - Aig_ManForEachLiLoSeq( p, pObjLi, pObjLo, i ) - fprintf( pFile, ".latch n%0*d n%0*d 0\n", nDigits, pObjLi->iData, nDigits, pObjLo->iData ); - fprintf( pFile, "\n" ); + fprintf( pFile, "\n" ); + Aig_ManForEachLiLoSeq( p, pObjLi, pObjLo, i ) + fprintf( pFile, ".latch n%0*d n%0*d 0\n", nDigits, pObjLi->iData, nDigits, pObjLo->iData ); + fprintf( pFile, "\n" ); } // write nodes + if ( pConst1 ) + fprintf( pFile, ".names n%0*d\n 1\n", nDigits, pConst1->iData ); Vec_PtrForEachEntry( vNodes, pObj, i ) { fprintf( pFile, ".names n%0*d n%0*d n%0*d\n", @@ -719,11 +725,7 @@ void Aig_ManDumpBlif( Aig_Man_t * p, char * pFileName ) nDigits, Aig_ObjFanin0(pObj)->iData, nDigits, pObj->iData ); fprintf( pFile, "%d 1\n", !Aig_ObjFaninC0(pObj) ); - if ( Aig_ObjIsConst1(Aig_ObjFanin0(pObj)) ) - pConst1 = Aig_ManConst1(p); } - if ( pConst1 ) - fprintf( pFile, ".names n%0*d\n 1\n", nDigits, pConst1->iData ); fprintf( pFile, ".end\n\n" ); fclose( pFile ); Vec_PtrFree( vNodes ); @@ -751,6 +753,10 @@ void Aig_ManDumpVerilog( Aig_Man_t * p, char * pFileName ) printf( "Aig_ManDumpBlif(): AIG manager does not have POs.\n" ); return; } + // check if constant is used + Aig_ManForEachPo( p, pObj, i ) + if ( Aig_ObjIsConst1(Aig_ObjFanin0(pObj)) ) + pConst1 = Aig_ManConst1(p); // collect nodes in the DFS order vNodes = Aig_ManDfs( p ); // assign IDs to objects @@ -795,7 +801,11 @@ void Aig_ManDumpVerilog( Aig_Man_t * p, char * pFileName ) // write nodes Vec_PtrForEachEntry( vNodes, pObj, i ) fprintf( pFile, "wire n%0*d;\n", nDigits, pObj->iData ); + if ( pConst1 ) + fprintf( pFile, "wire n%0*d;\n", nDigits, pConst1->iData ); // write nodes + if ( pConst1 ) + fprintf( pFile, "assign n%0*d = 1\'b1;\n", nDigits, pConst1->iData ); Vec_PtrForEachEntry( vNodes, pObj, i ) { fprintf( pFile, "assign n%0*d = %sn%0*d & %sn%0*d;\n", @@ -810,8 +820,6 @@ void Aig_ManDumpVerilog( Aig_Man_t * p, char * pFileName ) fprintf( pFile, "assign n%0*d = %sn%0*d;\n", nDigits, pObj->iData, !Aig_ObjFaninC0(pObj) ? " " : "~", nDigits, Aig_ObjFanin0(pObj)->iData ); - if ( Aig_ObjIsConst1(Aig_ObjFanin0(pObj)) ) - pConst1 = Aig_ManConst1(p); } if ( Aig_ManRegNum(p) ) { @@ -820,12 +828,8 @@ void Aig_ManDumpVerilog( Aig_Man_t * p, char * pFileName ) fprintf( pFile, "assign n%0*d = %sn%0*d;\n", nDigits, pObjLi->iData, !Aig_ObjFaninC0(pObjLi) ? " " : "~", nDigits, Aig_ObjFanin0(pObjLi)->iData ); - if ( Aig_ObjIsConst1(Aig_ObjFanin0(pObjLi)) ) - pConst1 = Aig_ManConst1(p); } } - if ( pConst1 ) - fprintf( pFile, "assign n%0*d = 1\'b1;\n", nDigits, pConst1->iData ); // write initial state if ( Aig_ManRegNum(p) ) diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index da07a936..89eb80a6 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -166,6 +166,7 @@ static int Abc_CommandSeq ( Abc_Frame_t * pAbc, int argc, char ** arg static int Abc_CommandUnseq ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandRetime ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandDRetime ( Abc_Frame_t * pAbc, int argc, char ** argv ); +static int Abc_CommandFlowRetime ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandSeqFpga ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandSeqMap ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandSeqSweep ( Abc_Frame_t * pAbc, int argc, char ** argv ); @@ -339,6 +340,7 @@ void Abc_Init( Abc_Frame_t * pAbc ) // Cmd_CommandAdd( pAbc, "Sequential", "pipe", Abc_CommandPipe, 1 ); Cmd_CommandAdd( pAbc, "Sequential", "retime", Abc_CommandRetime, 1 ); Cmd_CommandAdd( pAbc, "Sequential", "dretime", Abc_CommandDRetime, 1 ); + Cmd_CommandAdd( pAbc, "Sequential", "fretime", Abc_CommandFlowRetime, 1 ); // Cmd_CommandAdd( pAbc, "Sequential", "sfpga", Abc_CommandSeqFpga, 1 ); // Cmd_CommandAdd( pAbc, "Sequential", "smap", Abc_CommandSeqMap, 1 ); Cmd_CommandAdd( pAbc, "Sequential", "ssweep", Abc_CommandSeqSweep, 1 ); @@ -6292,7 +6294,7 @@ usage: int Abc_CommandTest( Abc_Frame_t * pAbc, int argc, char ** argv ) { FILE * pOut, * pErr; - Abc_Ntk_t * pNtk;//, * pNtkRes; + Abc_Ntk_t * pNtk, * pNtkRes; int c; int fBmc; int nFrames; @@ -6309,7 +6311,7 @@ int Abc_CommandTest( Abc_Frame_t * pAbc, int argc, char ** argv ) extern Abc_Ntk_t * Abc_NtkDarToCnf( Abc_Ntk_t * pNtk, char * pFileName ); extern Abc_Ntk_t * Abc_NtkFilter( Abc_Ntk_t * pNtk ); // extern Abc_Ntk_t * Abc_NtkDarRetime( Abc_Ntk_t * pNtk, int nStepsMax, int fVerbose ); - extern Abc_Ntk_t * Abc_NtkPcmTest( Abc_Ntk_t * pNtk, int fVerbose ); +// extern Abc_Ntk_t * Abc_NtkPcmTest( Abc_Ntk_t * pNtk, int fVerbose ); extern Abc_NtkDarHaigRecord( Abc_Ntk_t * pNtk ); extern void Abc_NtkDarTestBlif( char * pFileName ); @@ -6471,8 +6473,8 @@ int Abc_CommandTest( Abc_Frame_t * pAbc, int argc, char ** argv ) // pNtkRes = Abc_NtkDar( pNtk ); // pNtkRes = Abc_NtkDarRetime( pNtk, nLevels, 1 ); -// pNtkRes = Abc_NtkPcmTest( pNtk, fVerbose ); - pNtkRes = NULL; + pNtkRes = Abc_NtkPcmTest( pNtk, fVerbose ); +// pNtkRes = NULL; if ( pNtkRes == NULL ) { fprintf( pErr, "Command has failed.\n" ); @@ -6481,6 +6483,7 @@ int Abc_CommandTest( Abc_Frame_t * pAbc, int argc, char ** argv ) // replace the current network Abc_FrameReplaceCurrentNetwork( pAbc, pNtkRes ); */ + // Abc_NtkDarHaigRecord( pNtk ); // Abc_NtkDarClau( pNtk, nFrames, nLevels, fBmc, fVerbose, fVeryVerbose ); @@ -10441,6 +10444,7 @@ int Abc_CommandInit( Abc_Frame_t * pAbc, int argc, char ** argv ) } else if ( fRandom ) { + srand( time(NULL) ); Abc_NtkForEachLatch( pNtk, pObj, i ) if ( rand() & 1 ) Abc_LatchSetInit1( pObj ); @@ -11068,6 +11072,133 @@ usage: fprintf( pErr, "\t-h : print the command usage\n"); return 1; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_CommandFlowRetime( Abc_Frame_t * pAbc, int argc, char ** argv ) +{ + FILE * pOut, * pErr; + Abc_Ntk_t * pNtk, * pNtkRes; + int c, nMaxIters; + int fForward; + int fBackward; + int fVerbose; + int fComputeInit; + int maxDelay; + + extern Abc_Ntk_t* Abc_FlowRetime_MinReg( Abc_Ntk_t * pNtk, int fVerbose, int fComputeInit, + int fForward, int fBackward, int nMaxIters, + int maxDelay); + + pNtk = Abc_FrameReadNtk(pAbc); + pOut = Abc_FrameReadOut(pAbc); + pErr = Abc_FrameReadErr(pAbc); + + // set defaults + fForward = 0; + fBackward = 0; + fComputeInit = 1; + fVerbose = 0; + nMaxIters = 999; + maxDelay = 0; + Extra_UtilGetoptReset(); + while ( ( c = Extra_UtilGetopt( argc, argv, "MDfbivh" ) ) != EOF ) + { + switch ( c ) + { + case 'M': + if ( globalUtilOptind >= argc ) + { + fprintf( pErr, "Command line switch \"-M\" should be followed by a positive integer.\n" ); + goto usage; + } + nMaxIters = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nMaxIters < 0 ) + goto usage; + break; + case 'D': + if ( globalUtilOptind >= argc ) + { + fprintf( pErr, "Command line switch \"-D\" should be followed by a positive integer.\n" ); + goto usage; + } + maxDelay = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( maxDelay < 0 ) + goto usage; + break; + case 'f': + fForward ^= 1; + break; + case 'i': + fComputeInit ^= 1; + break; + case 'b': + fBackward ^= 1; + break; + case 'v': + fVerbose ^= 1; + break; + case 'h': + goto usage; + default: + goto usage; + } + } + + if ( pNtk == NULL ) + { + fprintf( pErr, "Empty network.\n" ); + return 1; + } + + if ( fForward && fBackward ) + { + fprintf( pErr, "Only one switch \"-f\" or \"-b\" can be selected at a time.\n" ); + return 1; + } + + if ( !Abc_NtkLatchNum(pNtk) ) + { + fprintf( pErr, "The network has no latches. Retiming is not performed.\n" ); + return 0; + } + + if ( Abc_NtkGetChoiceNum(pNtk) ) + { + fprintf( pErr, "Retiming with choice nodes is not implemented.\n" ); + return 0; + } + + // perform the retiming + pNtkRes = Abc_FlowRetime_MinReg( pNtk, fVerbose, fComputeInit, fForward, fBackward, nMaxIters, maxDelay ); + + if (pNtkRes != pNtk) + Abc_FrameReplaceCurrentNetwork( pAbc, pNtkRes ); + + return 0; + +usage: + fprintf( pErr, "usage: fretime [-M num] [-D num] [-fbvih]\n" ); + fprintf( pErr, "\t retimes the current network using flow-based algorithm\n" ); + fprintf( pErr, "\t-M num : the maximum number of iterations [default = %d]\n", nMaxIters ); + fprintf( pErr, "\t-D num : the maximum delay [default = none]\n" ); + fprintf( pErr, "\t-i : enables init state computation [default = %s]\n", fComputeInit? "yes": "no" ); + fprintf( pErr, "\t-f : enables forward-only retiming [default = %s]\n", fForward? "yes": "no" ); + fprintf( pErr, "\t-b : enables backward-only retiming [default = %s]\n", fBackward? "yes": "no" ); + fprintf( pErr, "\t-v : enables verbose output [default = %s]\n", fVerbose? "yes": "no" ); + fprintf( pErr, "\t-h : print the command usage\n"); + return 1; +} /**Function************************************************************* diff --git a/src/opt/fret/fretFlow.c b/src/opt/fret/fretFlow.c new file mode 100644 index 00000000..599aa341 --- /dev/null +++ b/src/opt/fret/fretFlow.c @@ -0,0 +1,640 @@ +/**CFile**************************************************************** + + FileName [fretFlow.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Flow-based retiming package.] + + Synopsis [Max-flow computation.] + + Author [Aaron Hurst] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - January 1, 2008.] + + Revision [$Id: fretFlow.c,v 1.00 2008/01/01 00:00:00 ahurst Exp $] + +***********************************************************************/ + +#include "abc.h" +#include "vec.h" +#include "fretime.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void dfsfast_e_retreat( Abc_Obj_t *pObj ); +static void dfsfast_r_retreat( Abc_Obj_t *pObj ); + +#define FDIST(xn, xe, yn, ye) (FDATA(xn)->xe##_dist == (FDATA(yn)->ye##_dist + 1)) + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Fast DFS.] + + Description [Uses sink-distance-histogram heuristic. May not find all + flow paths: this occurs in a small number of cases where + the flow predecessor points to a non-adjacent node and + the distance ordering is perturbed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ + +void dfsfast_preorder( Abc_Ntk_t *pNtk ) { + Abc_Obj_t *pObj, *pNext; + Vec_Ptr_t *vTimeIn, *qn = Vec_PtrAlloc(Abc_NtkObjNum(pNtk)); + Vec_Int_t *qe = Vec_IntAlloc(Abc_NtkObjNum(pNtk)); + int i, j, d = 0, end; + int qpos = 0; + + // create reverse timing edges for backward traversal +#if !defined(IGNORE_TIMING) + if (maxDelayCon) + Abc_NtkForEachObj( pNtk, pObj, i ) { + Vec_PtrForEachEntry( FTIMEEDGES(pObj), pNext, j ) { + vTimeIn = FDATA(pNext)->vTimeInEdges; + if (!vTimeIn) { + vTimeIn = FDATA(pNext)->vTimeInEdges = Vec_PtrAlloc(2); + } + Vec_PtrPush(vTimeIn, pObj); + } + } +#endif + + // clear histogram + memset(Vec_IntArray(vSinkDistHist), 0, sizeof(int)*Vec_IntSize(vSinkDistHist)); + + // seed queue : latches, PIOs, and blocks + Abc_NtkForEachObj( pNtk, pObj, i ) + if (Abc_ObjIsPo(pObj) || + Abc_ObjIsLatch(pObj) || + (fIsForward && FTEST(pObj, BLOCK))) { + Vec_PtrPush(qn, pObj); + Vec_IntPush(qe, 'r'); + FDATA(pObj)->r_dist = 1; + } else if (Abc_ObjIsPi(pObj) || + (!fIsForward && FTEST(pObj, BLOCK))) { + Vec_PtrPush(qn, pObj); + Vec_IntPush(qe, 'e'); + FDATA(pObj)->e_dist = 1; + } + + // until queue is empty... + while(qpos < Vec_PtrSize(qn)) { + pObj = (Abc_Obj_t *)Vec_PtrEntry(qn, qpos); + assert(pObj); + end = Vec_IntEntry(qe, qpos); + qpos++; + + if (end == 'r') { + d = FDATA(pObj)->r_dist; + + // 1. structural edges + if (fIsForward) { + Abc_ObjForEachFanin( pObj, pNext, i ) + if (!FDATA(pNext)->e_dist) { + FDATA(pNext)->e_dist = d+1; + Vec_PtrPush(qn, pNext); + Vec_IntPush(qe, 'e'); + } + } else + Abc_ObjForEachFanout( pObj, pNext, i ) + if (!FDATA(pNext)->e_dist) { + FDATA(pNext)->e_dist = d+1; + Vec_PtrPush(qn, pNext); + Vec_IntPush(qe, 'e'); + } + + if (d == 1) continue; + + // 2. reverse edges (forward retiming only) + if (fIsForward) { + Abc_ObjForEachFanout( pObj, pNext, i ) + if (!FDATA(pNext)->r_dist && !Abc_ObjIsLatch(pNext)) { + FDATA(pNext)->r_dist = d+1; + Vec_PtrPush(qn, pNext); + Vec_IntPush(qe, 'r'); + } + } + + // 3. timimg edges (reverse) +#if !defined(IGNORE_TIMING) + if (maxDelayCon && FDATA(pObj)->vTimeInEdges) + Vec_PtrForEachEntry( FDATA(pObj)->vTimeInEdges, pNext, i ) { + if (!FDATA(pNext)->r_dist) { + FDATA(pNext)->r_dist = d+1; + Vec_PtrPush(qn, pNext); + Vec_IntPush(qe, 'r'); + } + } +#endif + + } else { // if 'e' + if (Abc_ObjIsLatch(pObj)) continue; + + d = FDATA(pObj)->e_dist; + + // 1. through node + if (!FDATA(pObj)->r_dist) { + FDATA(pObj)->r_dist = d+1; + Vec_PtrPush(qn, pObj); + Vec_IntPush(qe, 'r'); + } + + // 2. reverse edges (backward retiming only) + if (!fIsForward) { + Abc_ObjForEachFanin( pObj, pNext, i ) + if (!FDATA(pNext)->e_dist && !Abc_ObjIsLatch(pNext)) { + FDATA(pNext)->e_dist = d+1; + Vec_PtrPush(qn, pNext); + Vec_IntPush(qe, 'e'); + } + } + } + } + + // create reverse timing edges for backward traversal +#if !defined(IGNORE_TIMING) + if (maxDelayCon) + Abc_NtkForEachObj( pNtk, pObj, i ) { + vTimeIn = FDATA(pObj)->vTimeInEdges; + if (vTimeIn) { + Vec_PtrFree(vTimeIn); + FDATA(pObj)->vTimeInEdges = 0; + } + } +#endif + + Abc_NtkForEachObj( pNtk, pObj, i ) { + Vec_IntAddToEntry(vSinkDistHist, FDATA(pObj)->r_dist, 1); + Vec_IntAddToEntry(vSinkDistHist, FDATA(pObj)->e_dist, 1); + +#ifdef DEBUG_PREORDER + printf("node %d\t: r=%d\te=%d\n", Abc_ObjId(pObj), FDATA(pObj)->r_dist, FDATA(pObj)->e_dist); +#endif + } + + printf("\t\tpre-ordered (max depth=%d)\n", d+1); + + // deallocate + Vec_PtrFree( qn ); + Vec_IntFree( qe ); +} + +int dfsfast_e( Abc_Obj_t *pObj, Abc_Obj_t *pPred ) { + int i; + Abc_Obj_t *pNext; + + if (fSinkDistTerminate) return 0; + + if(FTEST(pObj, BLOCK) || + Abc_ObjIsPi(pObj)) { + assert(!fIsForward); + return 1; + } + + FSET(pObj, VISITED_E); + +#ifdef DEBUG_VISITED + printf("(%de=%d) ", Abc_ObjId(pObj), FDATA(pObj)->e_dist); +#endif + + // 1. structural edges + if (fIsForward) + Abc_ObjForEachFanout( pObj, pNext, i ) { + if (!FTEST(pNext, VISITED_R) && + FDIST(pObj, e, pNext, r) && + dfsfast_r(pNext, pPred)) { +#ifdef DEBUG_PRINT_FLOWS + printf("o"); +#endif + goto found; + } + } + else + Abc_ObjForEachFanin( pObj, pNext, i ) { + if (!FTEST(pNext, VISITED_R) && + FDIST(pObj, e, pNext, r) && + dfsfast_r(pNext, pPred)) { +#ifdef DEBUG_PRINT_FLOWS + printf("o"); +#endif + goto found; + } + } + + if (Abc_ObjIsLatch(pObj)) + goto not_found; + + // 2. reverse edges (backward retiming only) + if (!fIsForward) { + Abc_ObjForEachFanout( pObj, pNext, i ) { + if (!FTEST(pNext, VISITED_E) && + FDIST(pObj, e, pNext, e) && + dfsfast_e(pNext, pPred)) { +#ifdef DEBUG_PRINT_FLOWS + printf("i"); +#endif + goto found; + } + } + } + + // unwind + if (FTEST(pObj, FLOW) && + !FTEST(pObj, VISITED_R) && + FDIST(pObj, e, pObj, r) && + dfsfast_r(pObj, FGETPRED(pObj))) { + + FUNSET(pObj, FLOW); + FSETPRED(pObj, NULL); +#ifdef DEBUG_PRINT_FLOWS + printf("u"); +#endif + goto found; + } + + not_found: + FUNSET(pObj, VISITED_E); + dfsfast_e_retreat(pObj); + return 0; + + found: +#ifdef DEBUG_PRINT_FLOWS + printf("%d ", Abc_ObjId(pObj)); +#endif + FUNSET(pObj, VISITED_E); + return 1; +} + +int dfsfast_r( Abc_Obj_t *pObj, Abc_Obj_t *pPred ) { + int i; + Abc_Obj_t *pNext, *pOldPred; + + if (fSinkDistTerminate) return 0; + +#ifdef DEBUG_VISITED + printf("(%dr=%d) ", Abc_ObjId(pObj), FDATA(pObj)->r_dist); +#endif + + // have we reached the sink? + if (Abc_ObjIsLatch(pObj) || + Abc_ObjIsPo(pObj) || + (fIsForward && FTEST(pObj, BLOCK))) { + assert(pPred); + return 1; + } + + FSET(pObj, VISITED_R); + + if (FTEST(pObj, FLOW)) { + + pOldPred = FGETPRED(pObj); + if (pOldPred && + !FTEST(pOldPred, VISITED_E) && + FDIST(pObj, r, pOldPred, e) && + dfsfast_e(pOldPred, pOldPred)) { + + FSETPRED(pObj, pPred); + +#ifdef DEBUG_PRINT_FLOWS + printf("fr"); +#endif + goto found; + } + + } else { + + if (!FTEST(pObj, VISITED_E) && + FDIST(pObj, r, pObj, e) && + dfsfast_e(pObj, pObj)) { + + FSET(pObj, FLOW); + FSETPRED(pObj, pPred); + +#ifdef DEBUG_PRINT_FLOWS + printf("f"); +#endif + goto found; + } + } + + // 2. reverse edges (forward retiming only) + if (fIsForward) { + Abc_ObjForEachFanin( pObj, pNext, i ) { + if (!FTEST(pNext, VISITED_R) && + FDIST(pObj, r, pNext, r) && + !Abc_ObjIsLatch(pNext) && + dfsfast_r(pNext, pPred)) { +#ifdef DEBUG_PRINT_FLOWS + printf("i"); +#endif + goto found; + } + } + } + + // 3. timing edges +#if !defined(IGNORE_TIMING) + if (maxDelayCon) + Vec_PtrForEachEntry( FTIMEEDGES(pObj), pNext, i) { + if (!FTEST(pNext, VISITED_R) && + FDIST(pObj, r, pNext, r) && + dfsfast_r(pNext, pPred)) { +#ifdef DEBUG_PRINT_FLOWS + printf("o"); +#endif + goto found; + } + } +#endif + + FUNSET(pObj, VISITED_R); + dfsfast_r_retreat(pObj); + return 0; + + found: +#ifdef DEBUG_PRINT_FLOWS + printf("%d ", Abc_ObjId(pObj)); +#endif + FUNSET(pObj, VISITED_R); + return 1; +} + +void +dfsfast_e_retreat(Abc_Obj_t *pObj) { + Abc_Obj_t *pNext; + int i, *h; + int old_dist = FDATA(pObj)->e_dist; + int adj_dist, min_dist = MAX_DIST; + + // 1. structural edges + if (fIsForward) + Abc_ObjForEachFanout( pObj, pNext, i ) { + adj_dist = FDATA(pNext)->r_dist; + if (adj_dist) min_dist = MIN(min_dist, adj_dist); + } + else + Abc_ObjForEachFanin( pObj, pNext, i ) { + adj_dist = FDATA(pNext)->r_dist; + if (adj_dist) min_dist = MIN(min_dist, adj_dist); + } + + if (Abc_ObjIsLatch(pObj)) goto update; + + // 2. through + if (FTEST(pObj, FLOW)) { + adj_dist = FDATA(pObj)->r_dist; + if (adj_dist) min_dist = MIN(min_dist, adj_dist); + } + + // 3. reverse edges (backward retiming only) + if (!fIsForward) { + Abc_ObjForEachFanout( pObj, pNext, i ) { + adj_dist = FDATA(pNext)->e_dist; + if (adj_dist) min_dist = MIN(min_dist, adj_dist); + } + } + + update: + ++min_dist; + if (min_dist >= MAX_DIST) min_dist = 0; + // printf("[%de=%d->%d] ", Abc_ObjId(pObj), old_dist, min_dist+1); + FDATA(pObj)->e_dist = min_dist; + + assert(min_dist < Vec_IntSize(vSinkDistHist)); + h = Vec_IntArray(vSinkDistHist); + h[old_dist]--; + h[min_dist]++; + if (!h[old_dist]) { + fSinkDistTerminate = 1; + } +} + +void +dfsfast_r_retreat(Abc_Obj_t *pObj) { + Abc_Obj_t *pNext; + int i, *h; + int old_dist = FDATA(pObj)->r_dist; + int adj_dist, min_dist = MAX_DIST; + + // 1. through or pred + if (FTEST(pObj, FLOW)) { + if (FGETPRED(pObj)) { + adj_dist = FDATA(FGETPRED(pObj))->e_dist; + if (adj_dist) min_dist = MIN(min_dist, adj_dist); + } + } else { + adj_dist = FDATA(pObj)->e_dist; + if (adj_dist) min_dist = MIN(min_dist, adj_dist); + } + + // 2. reverse edges (forward retiming only) + if (fIsForward) { + Abc_ObjForEachFanin( pObj, pNext, i ) + if (!Abc_ObjIsLatch(pNext)) { + adj_dist = FDATA(pNext)->r_dist; + if (adj_dist) min_dist = MIN(min_dist, adj_dist); + } + } + + // 3. timing edges +#if !defined(IGNORE_TIMING) + if (maxDelayCon) + Vec_PtrForEachEntry( FTIMEEDGES(pObj), pNext, i) { + adj_dist = FDATA(pNext)->r_dist; + if (adj_dist) min_dist = MIN(min_dist, adj_dist); + } +#endif + + ++min_dist; + if (min_dist >= MAX_DIST) min_dist = 0; + //printf("[%dr=%d->%d] ", Abc_ObjId(pObj), old_dist, min_dist+1); + FDATA(pObj)->r_dist = min_dist; + + assert(min_dist < Vec_IntSize(vSinkDistHist)); + h = Vec_IntArray(vSinkDistHist); + h[old_dist]--; + h[min_dist]++; + if (!h[old_dist]) { + fSinkDistTerminate = 1; + } +} + +/**Function************************************************************* + + Synopsis [Plain DFS.] + + Description [Does not use sink-distance-histogram heuristic.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ + +int dfsplain_e( Abc_Obj_t *pObj, Abc_Obj_t *pPred ) { + int i; + Abc_Obj_t *pNext; + + if (FTEST(pObj, BLOCK) || Abc_ObjIsPi(pObj)) { + assert(!fIsForward); + return 1; + } + + FSET(pObj, VISITED_E); + + // printf(" %de\n", Abc_ObjId(pObj)); + + // 1. structural edges + if (fIsForward) + Abc_ObjForEachFanout( pObj, pNext, i ) { + if (!FTEST(pNext, VISITED_R) && + dfsplain_r(pNext, pPred)) { +#ifdef DEBUG_PRINT_FLOWS + printf("o"); +#endif + goto found; + } + } + else + Abc_ObjForEachFanin( pObj, pNext, i ) { + if (!FTEST(pNext, VISITED_R) && + dfsplain_r(pNext, pPred)) { +#ifdef DEBUG_PRINT_FLOWS + printf("o"); +#endif + goto found; + } + } + + if (Abc_ObjIsLatch(pObj)) + return 0; + + // 2. follow reverse edges + if (!fIsForward) { // reverse retiming only + Abc_ObjForEachFanout( pObj, pNext, i ) { + if (!FTEST(pNext, VISITED_E) && + dfsplain_e(pNext, pPred)) { +#ifdef DEBUG_PRINT_FLOWS + printf("i"); +#endif + goto found; + } + } + } + + // unwind + if (FTEST(pObj, FLOW) && + !FTEST(pObj, VISITED_R) && + dfsplain_r(pObj, FGETPRED(pObj))) { + FUNSET(pObj, FLOW); + FSETPRED(pObj, NULL); +#ifdef DEBUG_PRINT_FLOWS + printf("u"); +#endif + goto found; + } + + return 0; + + found: +#ifdef DEBUG_PRINT_FLOWS + printf("%d ", Abc_ObjId(pObj)); +#endif + + return 1; +} + +int dfsplain_r( Abc_Obj_t *pObj, Abc_Obj_t *pPred ) { + int i; + Abc_Obj_t *pNext, *pOldPred; + + // have we reached the sink? + if (Abc_ObjIsLatch(pObj) || + Abc_ObjIsPo(pObj) || + (fIsForward && FTEST(pObj, BLOCK))) { + assert(pPred); + return 1; + } + + FSET(pObj, VISITED_R); + + // printf(" %dr\n", Abc_ObjId(pObj)); + + if (FTEST(pObj, FLOW)) { + + pOldPred = FGETPRED(pObj); + if (pOldPred && + !FTEST(pOldPred, VISITED_E) && + dfsplain_e(pOldPred, pOldPred)) { + + FSETPRED(pObj, pPred); + +#ifdef DEBUG_PRINT_FLOWS + printf("fr"); +#endif + goto found; + } + + } else { + + if (!FTEST(pObj, VISITED_E) && + dfsplain_e(pObj, pObj)) { + + FSET(pObj, FLOW); + FSETPRED(pObj, pPred); + +#ifdef DEBUG_PRINT_FLOWS + printf("f"); +#endif + goto found; + } + } + + // 2. follow reverse edges + if (fIsForward) { // forward retiming only + Abc_ObjForEachFanin( pObj, pNext, i ) { + if (!FTEST(pNext, VISITED_R) && + !Abc_ObjIsLatch(pNext) && + dfsplain_r(pNext, pPred)) { +#ifdef DEBUG_PRINT_FLOWS + printf("i"); +#endif + goto found; + } + } + } + + // 3. follow timing constraints +#if !defined(IGNORE_TIMING) + if (maxDelayCon) + Vec_PtrForEachEntry( FTIMEEDGES(pObj), pNext, i) { + if (!FTEST(pNext, VISITED_R) && + dfsplain_r(pNext, pPred)) { +#ifdef DEBUG_PRINT_FLOWS + printf("o"); +#endif + goto found; + } + } +#endif + + return 0; + + found: +#ifdef DEBUG_PRINT_FLOWS + printf("%d ", Abc_ObjId(pObj)); +#endif + return 1; +} diff --git a/src/opt/fret/fretInit.c b/src/opt/fret/fretInit.c new file mode 100644 index 00000000..30d1c553 --- /dev/null +++ b/src/opt/fret/fretInit.c @@ -0,0 +1,743 @@ +/**CFile**************************************************************** + + FileName [fretInit.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Flow-based retiming package.] + + Synopsis [Initialization for retiming package.] + + Author [Aaron Hurst] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - January 1, 2008.] + + Revision [$Id: fretInit.c,v 1.00 2008/01/01 00:00:00 ahurst Exp $] + +***********************************************************************/ + +#include "abc.h" +#include "vec.h" +#include "io.h" +#include "fretime.h" + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION PROTOTYPES /// +//////////////////////////////////////////////////////////////////////// + +static void Abc_FlowRetime_UpdateForwardInit_rec( Abc_Obj_t * pObj ); +static void Abc_FlowRetime_VerifyBackwardInit( Abc_Ntk_t * pNtk ); +static void Abc_FlowRetime_VerifyBackwardInit_rec( Abc_Obj_t * pObj ); +static Abc_Obj_t* Abc_FlowRetime_UpdateBackwardInit_rec( Abc_Obj_t *pOrigObj, + Abc_Obj_t *pUseThisPi, Vec_Ptr_t *vOtherPis, + int recurse); +static void Abc_FlowRetime_SimulateNode( Abc_Obj_t * pObj ); +static void Abc_FlowRetime_SimulateSop( Abc_Obj_t * pObj, char *pSop ); + +Abc_Ntk_t *pInitNtk; +int fSolutionIsDc; + +extern void * Abc_FrameReadLibGen(); +extern Abc_Ntk_t * Abc_NtkRestrash( Abc_Ntk_t * pNtk, bool fCleanup ); + + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Updates initial state information.] + + Description [Assumes latch boxes in original position, latches in + new positions.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void +Abc_FlowRetime_InitState( Abc_Ntk_t * pNtk ) { + + if (!fComputeInitState) return; + + if (fIsForward) + Abc_FlowRetime_UpdateForwardInit( pNtk ); + else { + Abc_FlowRetime_UpdateBackwardInit( pNtk ); + } +} + + +/**Function************************************************************* + + Synopsis [Prints initial state information.] + + Description [Prints distribution of 0,1,and X initial states.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void +Abc_FlowRetime_PrintInitStateInfo( Abc_Ntk_t * pNtk ) { + int i, n0=0, n1=0, nDC=0, nOther=0; + Abc_Obj_t *pLatch; + + Abc_NtkForEachLatch( pNtk, pLatch, i ) { + if (Abc_LatchIsInit0(pLatch)) n0++; + else if (Abc_LatchIsInit1(pLatch)) n1++; + else if (Abc_LatchIsInitDc(pLatch)) nDC++; + else nOther++; + } + + printf("\tinitial states {0,1,x} = {%d, %d, %d}", n0, n1, nDC); + if (nOther) + printf(" + %d UNKNOWN", nOther); + printf("\n"); +} + + +/**Function************************************************************* + + Synopsis [Computes initial state after forward retiming.] + + Description [Assumes box outputs in old positions stored w/ init values. + Uses three-value simulation to preserve don't cares.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_FlowRetime_UpdateForwardInit( Abc_Ntk_t * pNtk ) { + Abc_Obj_t *pObj, *pFanin; + int i; + + printf("\t\tupdating init state\n"); + + Abc_NtkIncrementTravId( pNtk ); + + Abc_NtkForEachLatch( pNtk, pObj, i ) { + pFanin = Abc_ObjFanin0(pObj); + Abc_FlowRetime_UpdateForwardInit_rec( pFanin ); + + if (FTEST(pFanin, INIT_0)) + Abc_LatchSetInit0( pObj ); + else if (FTEST(pFanin, INIT_1)) + Abc_LatchSetInit1( pObj ); + else + Abc_LatchSetInitDc( pObj ); + } +} + +void Abc_FlowRetime_UpdateForwardInit_rec( Abc_Obj_t * pObj ) { + Abc_Obj_t *pNext; + int i; + + assert(!Abc_ObjIsPi(pObj)); // should never reach the inputs + + if (Abc_ObjIsBo(pObj)) return; + + // visited? + if (Abc_NodeIsTravIdCurrent(pObj)) return; + Abc_NodeSetTravIdCurrent(pObj); + + Abc_ObjForEachFanin( pObj, pNext, i ) { + Abc_FlowRetime_UpdateForwardInit_rec( pNext ); + } + + Abc_FlowRetime_SimulateNode( pObj ); +} + + +/**Function************************************************************* + + Synopsis [Sets initial value flags.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Abc_FlowRetime_SetInitValue( Abc_Obj_t * pObj, + int val, int dc ) { + + // store init value + FUNSET(pObj, INIT_CARE); + if (!dc){ + if (val) { + FSET(pObj, INIT_1); + } else { + FSET(pObj, INIT_0); + } + } +} + + +/**Function************************************************************* + + Synopsis [Propogates initial state through a logic node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_FlowRetime_SimulateNode( Abc_Obj_t * pObj ) { + Abc_Ntk_t *pNtk = Abc_ObjNtk(pObj); + Abc_Obj_t * pFanin; + int i, j, rAnd, rOr, rVar, dcAnd, dcOr, dcVar, v; + DdManager * dd = pNtk->pManFunc; + DdNode *pBdd = pObj->pData, *pVar; + + assert(!Abc_ObjIsLatch(pObj)); + + // (i) constant nodes + if (Abc_NtkHasAig(pNtk) && Abc_AigNodeIsConst(pObj)) { + Abc_FlowRetime_SetInitValue(pObj, 1, 0); + return; + } + if (!Abc_NtkIsStrash( pNtk )) + if (Abc_NodeIsConst0(pObj)) { + Abc_FlowRetime_SetInitValue(pObj, 0, 0); + return; + } else if (Abc_NodeIsConst1(pObj)) { + Abc_FlowRetime_SetInitValue(pObj, 1, 0); + return; + } + + // (ii) terminal nodes + if (!Abc_ObjIsNode(pObj)) { + pFanin = Abc_ObjFanin0(pObj); + + Abc_FlowRetime_SetInitValue(pObj, + (FTEST(pFanin, INIT_1) ? 1 : 0) ^ pObj->fCompl0, + !FTEST(pFanin, INIT_CARE)); + return; + } + + // (iii) logic nodes + + // ------ SOP network + if ( Abc_NtkHasSop( pNtk )) { + Abc_FlowRetime_SimulateSop( pObj, Abc_ObjData(pObj) ); + return; + } + + // ------ BDD network + else if ( Abc_NtkHasBdd( pNtk )) { + assert(dd); + assert(pBdd); + + // cofactor for 0,1 inputs + // do nothing for X values + Abc_ObjForEachFanin(pObj, pFanin, i) { + pVar = Cudd_bddIthVar( dd, i ); + if (FTEST(pFanin, INIT_CARE)) + if (FTEST(pFanin, INIT_0)) { + pBdd = Cudd_Cofactor( dd, pBdd, Cudd_Not(pVar) ); + } else { + pBdd = Cudd_Cofactor( dd, pBdd, pVar ); + } + } + + // if function has not been reduced to + // a constant, propagate an X + rVar = (pBdd == Cudd_ReadOne(dd)); + dcVar = !Cudd_IsConstant(pBdd); + + Abc_FlowRetime_SetInitValue(pObj, rVar, dcVar); + return; + } + + // ------ AIG network + else if ( Abc_NtkHasAig( pNtk )) { + + assert(Abc_AigNodeIsAnd(pObj)); + dcAnd = 0, rAnd = 1; + + pFanin = Abc_ObjFanin0(pObj); + dcAnd |= FTEST(pFanin, INIT_CARE) ? 0 : 1; + rVar = FTEST(pFanin, INIT_0) ? 0 : 1; + if (pObj->fCompl0) rVar ^= 1; // complimented? + rAnd &= rVar; + + pFanin = Abc_ObjFanin1(pObj); + dcAnd |= FTEST(pFanin, INIT_CARE) ? 0 : 1; + rVar = FTEST(pFanin, INIT_0) ? 0 : 1; + if (pObj->fCompl1) rVar ^= 1; // complimented? + rAnd &= rVar; + + if (!rAnd) dcAnd = 0; /* controlling value */ + + Abc_FlowRetime_SetInitValue(pObj, rAnd, dcAnd); + return; + } + + // ------ MAPPED network + else if ( Abc_NtkHasMapping( pNtk )) { + Abc_FlowRetime_SimulateSop( pObj, Mio_GateReadSop(pObj->pData) ); + return; + } + + assert(0); +} + + +/**Function************************************************************* + + Synopsis [Propogates initial state through a SOP node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_FlowRetime_SimulateSop( Abc_Obj_t * pObj, char *pSop ) { + Abc_Obj_t * pFanin; + char *pCube; + int i, j, rAnd, rOr, rVar, dcAnd, dcOr, dcVar, v; + + assert( pSop && !Abc_SopIsExorType(pSop) ); + + rOr = 0, dcOr = 0; + + i = Abc_SopGetVarNum(pSop); + Abc_SopForEachCube( pSop, i, pCube ) { + rAnd = 1, dcAnd = 0; + Abc_CubeForEachVar( pCube, v, j ) { + pFanin = Abc_ObjFanin(pObj, j); + if ( v == '0' ) + rVar = FTEST(pFanin, INIT_0) ? 1 : 0; + else if ( v == '1' ) + rVar = FTEST(pFanin, INIT_1) ? 1 : 0; + else + continue; + + if (FTEST(pFanin, INIT_CARE)) + rAnd &= rVar; + else + dcAnd = 1; + } + if (!rAnd) dcAnd = 0; /* controlling value */ + if (dcAnd) + dcOr = 1; + else + rOr |= rAnd; + } + if (rOr) dcOr = 0; /* controlling value */ + + // complement the result if necessary + if ( !Abc_SopGetPhase(pSop) ) + rOr ^= 1; + + Abc_FlowRetime_SetInitValue(pObj, rOr, dcOr); +} + +/**Function************************************************************* + + Synopsis [Sets up backward initial state computation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_FlowRetime_SetupBackwardInit( Abc_Ntk_t * pNtk ) { + Abc_Obj_t *pLatch, *pObj, *pPi; + int i; + Vec_Ptr_t *vObj = Vec_PtrAlloc(100); + + // create the network used for the initial state computation + if (Abc_NtkHasMapping(pNtk)) + pInitNtk = Abc_NtkAlloc( pNtk->ntkType, ABC_FUNC_SOP, 1 ); + else + pInitNtk = Abc_NtkAlloc( pNtk->ntkType, pNtk->ntkFunc, 1 ); + + // mitre inputs + Abc_NtkForEachLatch( pNtk, pLatch, i ) { + // map latch to initial state network + pPi = Abc_NtkCreatePi( pInitNtk ); + + // has initial state requirement? + if (Abc_LatchIsInit0(pLatch)) { + + if (Abc_NtkHasAig(pNtk)) + pObj = Abc_ObjNot( pPi ); + else + pObj = Abc_NtkCreateNodeInv( pInitNtk, pPi ); + + Vec_PtrPush(vObj, pObj); + } + else if (Abc_LatchIsInit1(pLatch)) { + Vec_PtrPush(vObj, pPi); + } + + Abc_ObjSetData( pLatch, pPi ); // if not verifying init state + // FDATA(pLatch)->pInitObj = pPi; // if verifying init state + } + + // are there any nodes not DC? + if (!Vec_PtrSize(vObj)) { + fSolutionIsDc = 1; + return; + } else + fSolutionIsDc = 0; + + // mitre output + if (Abc_NtkHasAig(pNtk)) { + // create AND-by-AND + pObj = Vec_PtrPop( vObj ); + while( Vec_PtrSize(vObj) ) + pObj = Abc_AigAnd( pInitNtk->pManFunc, pObj, Vec_PtrPop( vObj ) ); + } else + // create n-input AND gate + pObj = Abc_NtkCreateNodeAnd( pInitNtk, vObj ); + + Abc_ObjAddFanin( Abc_NtkCreatePo( pInitNtk ), pObj ); +} + + +/**Function************************************************************* + + Synopsis [Solves backward initial state computation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_FlowRetime_SolveBackwardInit( Abc_Ntk_t * pNtk ) { + int i; + Abc_Obj_t *pObj, *pInitObj; + Abc_Ntk_t *pRestrNtk; + Vec_Ptr_t *vDelete = Vec_PtrAlloc(0); + int result; + + assert(pInitNtk); + + // is the solution entirely DC's? + if (fSolutionIsDc) { + Abc_NtkDelete(pInitNtk); + Vec_PtrFree(vDelete); + Abc_NtkForEachLatch( pNtk, pObj, i ) Abc_LatchSetInitDc( pObj ); + printf("\tno init state computation: all-don't-care solution\n"); + return; + } + + // check that network is combinational + // mark superfluous BI nodes for deletion + Abc_NtkForEachObj( pInitNtk, pObj, i ) { + assert(!Abc_ObjIsLatch(pObj)); + assert(!Abc_ObjIsBo(pObj)); + + if (Abc_ObjIsBi(pObj)) { + Abc_ObjBetterTransferFanout( pObj, Abc_ObjFanin0(pObj), Abc_ObjFaninC0(pObj) ); + Vec_PtrPush( vDelete, pObj ); + } + } + + // delete superfluous nodes + while(Vec_PtrSize( vDelete )) { + pObj = (Abc_Obj_t *)Vec_PtrPop( vDelete ); + Abc_NtkDeleteObj( pObj ); + } + Vec_PtrFree(vDelete); + + // do some final cleanup on the network + Abc_NtkAddDummyPoNames(pInitNtk); + Abc_NtkAddDummyPiNames(pInitNtk); + if (Abc_NtkIsLogic(pInitNtk)) + Abc_NtkCleanup(pInitNtk, 0); + else if (Abc_NtkIsStrash(pInitNtk)) { + Abc_NtkReassignIds(pInitNtk); + } + + printf("\tsolving for init state (%d nodes)... ", Abc_NtkObjNum(pInitNtk)); + fflush(stdout); + + // convert SOPs to BDD + if (Abc_NtkHasSop(pInitNtk)) + Abc_NtkSopToBdd( pInitNtk ); + + // solve + result = Abc_NtkMiterSat( pInitNtk, (sint64)500000, (sint64)50000000, 0, NULL, NULL ); + + if (!result) printf("SUCCESS\n"); + else { + printf("FAILURE\n"); + printf("\tsetting all initial states to don't-care\n"); + Abc_NtkForEachLatch( pNtk, pObj, i ) Abc_LatchSetInitDc( pObj ); + return; + } + + // clear initial values, associate PIs to latches + Abc_NtkForEachPi( pInitNtk, pInitObj, i ) Abc_ObjSetCopy( pInitObj, NULL ); + Abc_NtkForEachLatch( pNtk, pObj, i ) { + pInitObj = Abc_ObjData( pObj ); + assert( Abc_ObjIsPi( pInitObj )); + Abc_ObjSetCopy( pInitObj, pObj ); + Abc_LatchSetInitNone( pObj ); + } + + // copy solution from PIs to latches + assert(pInitNtk->pModel); + Abc_NtkForEachPi( pInitNtk, pInitObj, i ) { + if ((pObj = Abc_ObjCopy( pInitObj ))) { + if ( pInitNtk->pModel[i] ) + Abc_LatchSetInit1( pObj ); + else + Abc_LatchSetInit0( pObj ); + } + } + +#if defined(DEBUG_CHECK) + // check that all latches have initial state + Abc_NtkForEachLatch( pNtk, pObj, i ) assert( !Abc_LatchIsInitNone( pObj ) ); +#endif + + // deallocate + Abc_NtkDelete( pInitNtk ); +} + + +/**Function************************************************************* + + Synopsis [Updates backward initial state computation problem.] + + Description [Assumes box outputs in old positions stored w/ init values.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_FlowRetime_UpdateBackwardInit( Abc_Ntk_t * pNtk ) { + Abc_Obj_t *pOrigObj, *pOrigFanin, *pInitObj, *pInitFanin; + Vec_Ptr_t *vBo = Vec_PtrAlloc(100); + Vec_Ptr_t *vOldPis = Vec_PtrAlloc(100); + void *pData; + int i, j; + + // remove PIs from network (from BOs) + Abc_NtkForEachObj( pNtk, pOrigObj, i ) + if (Abc_ObjIsBo(pOrigObj)) { + pInitObj = FDATA(pOrigObj)->pInitObj; + assert(Abc_ObjIsPi(pInitObj)); + Vec_PtrPush(vBo, pOrigObj); + + Abc_FlowRetime_UpdateBackwardInit_rec( Abc_ObjFanin0( pOrigObj ), pInitObj, vOldPis, 0 ); + } + + // add PIs to network (at latches) + Abc_NtkForEachLatch( pNtk, pOrigObj, i ) + Abc_FlowRetime_UpdateBackwardInit_rec( pOrigObj, NULL, vOldPis, 0 ); + + // connect nodes in init state network + Vec_PtrForEachEntry( vBo, pOrigObj, i ) + Abc_FlowRetime_UpdateBackwardInit_rec( Abc_ObjFanin0( pOrigObj ), NULL, NULL, 1 ); + + // clear flags + Abc_NtkForEachObj( pNtk, pOrigObj, i ) + pOrigObj->fMarkA = pOrigObj->fMarkB = 0; + + // deallocate + Vec_PtrFree( vBo ); + Vec_PtrFree( vOldPis ); +} + + +/**Function************************************************************* + + Synopsis [Updates backward initial state computation problem.] + + Description [Creates a duplicate node in the initial state network + corresponding to a node in the original circuit. If + fRecurse is set, the procedure recurses on and connects + the new node to its fan-ins. A latch in the original + circuit corresponds to a PI in the initial state network. + An existing PI may be supplied by pUseThisPi, and if the + node is a latch, it will be used; otherwise the PI is + saved in the list vOtherPis and subsequently used for + another latch.] + + SideEffects [Nodes that have a corresponding initial state node + are marked with fMarkA. Nodes that have been fully + connected in the initial state network are marked with + fMarkB.] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t* Abc_FlowRetime_UpdateBackwardInit_rec( Abc_Obj_t *pOrigObj, + Abc_Obj_t *pUseThisPi, Vec_Ptr_t *vOtherPis, + int fRecurse) { + Abc_Obj_t *pInitObj, *pOrigFanin, *pInitFanin; + void *pData; + int i; + Abc_Ntk_t *pNtk = Abc_ObjNtk( pOrigObj ); + + // should never reach primary IOs + assert(!Abc_ObjIsPi(pOrigObj)); + assert(!Abc_ObjIsPo(pOrigObj)); + + // if fanin is latch, it becomes a primary input + if (Abc_ObjIsLatch( pOrigObj )) { + if (pOrigObj->fMarkA) return FDATA(pOrigObj)->pInitObj; + + assert(vOtherPis); + + if (pUseThisPi) { + // reuse curent PI + pInitObj = pUseThisPi; } + else { + // reuse previous PI + pInitObj = (Abc_Obj_t*)Vec_PtrPop(vOtherPis); + } + + // remember link from original node to init ntk + Abc_ObjSetData( pOrigObj, pInitObj ); + + pOrigObj->fMarkA = 1; + return (FDATA(pOrigObj)->pInitObj = pInitObj); + } + + // does an init node already exist? + if(!pOrigObj->fMarkA) { + + if (Abc_NtkHasMapping( pNtk )) { + if (!pOrigObj->pData) { + // assume terminal... + assert(Abc_ObjFaninNum(pOrigObj) == 1); + pInitObj = Abc_NtkCreateNodeBuf( pInitNtk, NULL ); + } else { + pInitObj = Abc_NtkCreateObj( pInitNtk, Abc_ObjType(pOrigObj) ); + pData = Mio_GateReadSop(pOrigObj->pData); + assert( Abc_SopGetVarNum(pData) == Abc_ObjFaninNum(pOrigObj) ); + + pInitObj->pData = Abc_SopRegister( pInitNtk->pManFunc, pData ); + } + } else { + pData = Abc_ObjCopy( pOrigObj ); // save ptr to flow data + if (Abc_NtkIsStrash( pNtk ) && Abc_AigNodeIsConst( pOrigObj )) + pInitObj = Abc_AigConst1( pInitNtk ); + else + pInitObj = Abc_NtkDupObj( pInitNtk, pOrigObj, 0 ); + Abc_ObjSetCopy( pOrigObj, pData ); // restore ptr to flow data + + // copy complementation + pInitObj->fCompl0 = pOrigObj->fCompl0; + pInitObj->fCompl1 = pOrigObj->fCompl1; + pInitObj->fPhase = pOrigObj->fPhase; + } + + // if we didn't use given PI, immediately transfer fanouts + // and add to list for later reuse + if (pUseThisPi) { + Abc_ObjBetterTransferFanout( pUseThisPi, pInitObj, 0 ); + Vec_PtrPush( vOtherPis, pUseThisPi ); + } + + pOrigObj->fMarkA = 1; + FDATA(pOrigObj)->pInitObj = pInitObj; + } else { + pInitObj = FDATA(pOrigObj)->pInitObj; + } + + // have we already connected this object? + if (fRecurse && !pOrigObj->fMarkB) { + + // create and/or connect fanins + Abc_ObjForEachFanin( pOrigObj, pOrigFanin, i ) { + pInitFanin = Abc_FlowRetime_UpdateBackwardInit_rec( pOrigFanin, NULL, NULL, fRecurse ); + Abc_ObjAddFanin( pInitObj, pInitFanin ); + } + + pOrigObj->fMarkB = 1; + } + + return pInitObj; +} + + +/**Function************************************************************* + + Synopsis [Verifies backward init state computation.] + + Description [This procedure requires the BOs to store the original + latch values and the latches to store the new values: + both in the INIT_0 and INIT_1 flags in the Flow_Data + structure. (This is not currently the case in the rest + of the code.) Also, can not verify backward state + computations that span multiple combinational frames.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_FlowRetime_VerifyBackwardInit( Abc_Ntk_t * pNtk ) { + Abc_Obj_t *pObj, *pFanin; + int i; + + printf("\t\tupdating init state\n"); + + Abc_NtkIncrementTravId( pNtk ); + + Abc_NtkForEachObj( pNtk, pObj, i ) + if (Abc_ObjIsBo( pObj )) { + pFanin = Abc_ObjFanin0(pObj); + Abc_FlowRetime_VerifyBackwardInit_rec( pFanin ); + + if (FTEST(pObj, INIT_CARE)) { + if(FTEST(pObj, INIT_CARE) != FTEST(pFanin, INIT_CARE)) { + printf("ERROR: expected val=%d care=%d and got val=%d care=%d\n", + FTEST(pObj, INIT_1)?1:0, FTEST(pObj, INIT_CARE)?1:0, + FTEST(pFanin, INIT_1)?1:0, FTEST(pFanin, INIT_CARE)?1:0 ); + + } + } + } +} + +void Abc_FlowRetime_VerifyBackwardInit_rec( Abc_Obj_t * pObj ) { + Abc_Obj_t *pNext; + int i; + + assert(!Abc_ObjIsBo(pObj)); // should never reach the inputs + assert(!Abc_ObjIsPi(pObj)); // should never reach the inputs + + // visited? + if (Abc_NodeIsTravIdCurrent(pObj)) return; + Abc_NodeSetTravIdCurrent(pObj); + + if (Abc_ObjIsLatch(pObj)) { + FUNSET(pObj, INIT_CARE); + if (Abc_LatchIsInit0(pObj)) + FSET(pObj, INIT_0); + else if (Abc_LatchIsInit1(pObj)) + FSET(pObj, INIT_1); + return; + } + + Abc_ObjForEachFanin( pObj, pNext, i ) { + Abc_FlowRetime_VerifyBackwardInit_rec( pNext ); + } + + Abc_FlowRetime_SimulateNode( pObj ); +} diff --git a/src/opt/fret/fretMain.c b/src/opt/fret/fretMain.c new file mode 100644 index 00000000..4ce78a9b --- /dev/null +++ b/src/opt/fret/fretMain.c @@ -0,0 +1,864 @@ +/**CFile**************************************************************** + + FileName [fretMain.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Flow-based retiming package.] + + Synopsis [Main file for retiming package.] + + Author [Aaron Hurst] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - January 1, 2008.] + + Revision [$Id: fretMain.c,v 1.00 2008/01/01 00:00:00 ahurst Exp $] + +***********************************************************************/ + +#include "abc.h" +#include "vec.h" +#include "fretime.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Abc_FlowRetime_AddDummyFanin( Abc_Obj_t * pObj ); + +static void Abc_FlowRetime_MarkBlocks( Abc_Ntk_t * pNtk ); +static void Abc_FlowRetime_MarkReachable_rec( Abc_Obj_t * pObj, char end ); +static int Abc_FlowRetime_PushFlows( Abc_Ntk_t * pNtk ); +static int Abc_FlowRetime_ImplementCut( Abc_Ntk_t * pNtk ); +static void Abc_FlowRetime_RemoveLatchBubbles( Abc_Obj_t * pLatch ); + +static void Abc_FlowRetime_VerifyPathLatencies( Abc_Ntk_t * pNtk ); +static int Abc_FlowRetime_VerifyPathLatencies_rec( Abc_Obj_t * pObj, int markD ); + +extern void Abc_NtkMarkCone_rec( Abc_Obj_t * pObj, int fForward ); +extern Abc_Ntk_t * Abc_NtkRestrash( Abc_Ntk_t * pNtk, bool fCleanup ); + +int fIsForward, fComputeInitState; +int fSinkDistTerminate; +Vec_Int_t *vSinkDistHist; +int maxDelayCon; + +int fPathError = 0; + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Performs minimum-register retiming.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * +Abc_FlowRetime_MinReg( Abc_Ntk_t * pNtk, int fVerbose, int fComputeInitState_, + int fForwardOnly, int fBackwardOnly, int nMaxIters, + int maxDelay ) { + + int i, j, nNodes, nLatches, flow, last, cut; + int iteration = 0; + Flow_Data_t *pDataArray; + Abc_Obj_t *pObj, *pNext; + + fComputeInitState = fComputeInitState_; + + printf("Flow-based minimum-register retiming...\n"); + + if (!Abc_NtkHasOnlyLatchBoxes(pNtk)) { + printf("\tERROR: Can not retime with black/white boxes\n"); + return pNtk; + } + + maxDelayCon = maxDelay; + if (maxDelayCon) { + printf("\tmax delay constraint = %d\n", maxDelayCon); + if (maxDelayCon < (i = Abc_NtkLevel(pNtk))) { + printf("ERROR: max delay constraint must be > current max delay (%d)\n", i); + return pNtk; + } + } + + // print info about type of network + printf("\tnetlist type = "); + if (Abc_NtkIsNetlist( pNtk )) printf("netlist/"); + else if (Abc_NtkIsLogic( pNtk )) printf("logic/"); + else if (Abc_NtkIsStrash( pNtk )) printf("strash/"); + else printf("***unknown***/"); + if (Abc_NtkHasSop( pNtk )) printf("sop\n"); + else if (Abc_NtkHasBdd( pNtk )) printf("bdd\n"); + else if (Abc_NtkHasAig( pNtk )) printf("aig\n"); + else if (Abc_NtkHasMapping( pNtk )) printf("mapped\n"); + else printf("***unknown***\n"); + + printf("\tinitial reg count = %d\n", Abc_NtkLatchNum(pNtk)); + + // remove bubbles from latch boxes + Abc_FlowRetime_PrintInitStateInfo(pNtk); + printf("\tpushing bubbles out of latch boxes\n"); + Abc_NtkForEachLatch( pNtk, pObj, i ) + Abc_FlowRetime_RemoveLatchBubbles(pObj); + Abc_FlowRetime_PrintInitStateInfo(pNtk); + + // check for box inputs/outputs + Abc_NtkForEachLatch( pNtk, pObj, i ) { + assert(Abc_ObjFaninNum(pObj) == 1); + assert(Abc_ObjFanoutNum(pObj) == 1); + assert(!Abc_ObjFaninC0(pObj)); + + pNext = Abc_ObjFanin0(pObj); + assert(Abc_ObjIsBi(pNext)); + assert(Abc_ObjFaninNum(pNext) <= 1); + if(Abc_ObjFaninNum(pNext) == 0) // every Bi should have a fanin + Abc_FlowRetime_AddDummyFanin( pNext ); + + pNext = Abc_ObjFanout0(pObj); + assert(Abc_ObjIsBo(pNext)); + assert(Abc_ObjFaninNum(pNext) == 1); + assert(!Abc_ObjFaninC0(pNext)); + } + + nLatches = Abc_NtkLatchNum( pNtk ); + nNodes = Abc_NtkObjNumMax( pNtk )+1; + + // build histogram + vSinkDistHist = Vec_IntStart( nNodes*2+10 ); + + // create Flow_Data structure + pDataArray = (Flow_Data_t *)malloc(sizeof(Flow_Data_t)*nNodes); + memset(pDataArray, 0, sizeof(Flow_Data_t)*nNodes); + Abc_NtkForEachObj( pNtk, pObj, i ) + Abc_ObjSetCopy( pObj, (void *)(&pDataArray[i]) ); + + // (i) forward retiming loop + fIsForward = 1; + + if (!fBackwardOnly) do { + if (iteration == nMaxIters) break; + + printf("\tforward iteration %d\n", iteration); + last = Abc_NtkLatchNum( pNtk ); + + Abc_FlowRetime_MarkBlocks( pNtk ); + flow = Abc_FlowRetime_PushFlows( pNtk ); + cut = Abc_FlowRetime_ImplementCut( pNtk ); + + // clear all + memset(pDataArray, 0, sizeof(Flow_Data_t)*nNodes); + iteration++; + } while( flow != last ); + + // print info about initial states + if (fComputeInitState) + Abc_FlowRetime_PrintInitStateInfo( pNtk ); + + // (ii) backward retiming loop + fIsForward = 0; + iteration = 0; + + if (!fForwardOnly) { + if (fComputeInitState) { + Abc_FlowRetime_SetupBackwardInit( pNtk ); + } + + do { + if (iteration == nMaxIters) break; + + printf("\tbackward iteration %d\n", iteration); + last = Abc_NtkLatchNum( pNtk ); + + Abc_FlowRetime_MarkBlocks( pNtk ); + flow = Abc_FlowRetime_PushFlows( pNtk ); + cut = Abc_FlowRetime_ImplementCut( pNtk ); + + // clear all + memset(pDataArray, 0, sizeof(Flow_Data_t)*nNodes); + iteration++; + + } while( flow != last ); + + // compute initial states + if (fComputeInitState) { + Abc_FlowRetime_SolveBackwardInit( pNtk ); + Abc_FlowRetime_PrintInitStateInfo( pNtk ); + } + } + + // clear pCopy field + Abc_NtkForEachObj( pNtk, pObj, i ) { + Abc_ObjSetCopy( pObj, NULL ); + + // if not computing init state, set all latches to DC + if (!fComputeInitState && Abc_ObjIsLatch(pObj)) + Abc_LatchSetInitDc(pObj); + } + + // restrash if necessary + if (Abc_NtkIsStrash(pNtk)) { + Abc_NtkReassignIds( pNtk ); + pNtk = Abc_NtkRestrash( pNtk, 1 ); + } + +#if defined(DEBUG_CHECK) + Abc_NtkDoCheck( pNtk ); +#endif + + // deallocate space + free(pDataArray); + if (vSinkDistHist) Vec_IntFree(vSinkDistHist); + + printf("\tfinal reg count = %d\n", Abc_NtkLatchNum(pNtk)); + + return pNtk; +} + +/**Function************************************************************* + + Synopsis [Pushes latch bubbles outside of box.] + + Description [If network is an AIG, a fCompl0 is allowed to remain on + the BI node.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void +Abc_FlowRetime_RemoveLatchBubbles( Abc_Obj_t * pLatch ) { + int i, j, k, bubble = 0; + Abc_Ntk_t *pNtk = Abc_ObjNtk( pLatch ); + Abc_Obj_t *pBi, *pBo, *pInv; + + pBi = Abc_ObjFanin0(pLatch); + pBo = Abc_ObjFanout0(pLatch); + assert(!Abc_ObjIsComplement(pBi)); + assert(!Abc_ObjIsComplement(pBo)); + + // push bubbles on BO into latch box + if (Abc_ObjFaninC0(pBo) && Abc_ObjFanoutNum(pBo) > 0) { + bubble = 1; + if (Abc_LatchIsInit0(pLatch)) Abc_LatchSetInit1(pLatch); + else if (Abc_LatchIsInit1(pLatch)) Abc_LatchSetInit0(pLatch); + } + + // absorb bubbles on BI + pBi->fCompl0 ^= bubble ^ Abc_ObjFaninC0(pLatch); + + // convert bubble to INV if not AIG + if (!Abc_NtkHasAig( pNtk ) && Abc_ObjFaninC0(pBi)) { + pBi->fCompl0 = 0; + pInv = Abc_NtkCreateNodeInv( pNtk, Abc_ObjFanin0(pBi) ); + Abc_ObjPatchFanin( pBi, Abc_ObjFanin0(pBi), pInv ); + } + + pBo->fCompl0 = 0; + pLatch->fCompl0 = 0; +} + + +/**Function************************************************************* + + Synopsis [Marks nodes in TFO/TFI of PI/PO.] + + Description [Sets flow data flag BLOCK appropriately.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void +Abc_FlowRetime_MarkBlocks( Abc_Ntk_t * pNtk ) { + int i; + Abc_Obj_t *pObj; + + if (fIsForward){ + // mark the frontier + Abc_NtkForEachPo( pNtk, pObj, i ) + pObj->fMarkA = 1; + Abc_NtkForEachLatch( pNtk, pObj, i ) + { + pObj->fMarkA = 1; + } + // mark the nodes reachable from the PIs + Abc_NtkForEachPi( pNtk, pObj, i ) + Abc_NtkMarkCone_rec( pObj, fIsForward ); + } else { + // mark the frontier + Abc_NtkForEachPi( pNtk, pObj, i ) + pObj->fMarkA = 1; + Abc_NtkForEachLatch( pNtk, pObj, i ) + { + pObj->fMarkA = 1; + } + // mark the nodes reachable from the POs + Abc_NtkForEachPo( pNtk, pObj, i ) + Abc_NtkMarkCone_rec( pObj, fIsForward ); + } + + // copy marks + Abc_NtkForEachObj( pNtk, pObj, i ) { + if (pObj->fMarkA) { + pObj->fMarkA = 0; + if (!Abc_ObjIsLatch(pObj) && + !Abc_ObjIsPi(pObj)) + FSET(pObj, BLOCK); + } + } +} + + +/**Function************************************************************* + + Synopsis [Computes maximum flow.] + + Description [] + + SideEffects [Leaves VISITED flags on source-reachable nodes.] + + SeeAlso [] + +***********************************************************************/ +int +Abc_FlowRetime_PushFlows( Abc_Ntk_t * pNtk ) { + int i, j, flow = 0, last, srcDist = 0; + Abc_Obj_t *pObj, *pObj2; + + fSinkDistTerminate = 0; + dfsfast_preorder( pNtk ); + + // (i) fast max-flow computation + while(!fSinkDistTerminate && srcDist < MAX_DIST) { + srcDist = MAX_DIST; + Abc_NtkForEachLatch( pNtk, pObj, i ) + if (FDATA(pObj)->e_dist) + srcDist = MIN(srcDist, FDATA(pObj)->e_dist); + + Abc_NtkForEachLatch( pNtk, pObj, i ) { + if (srcDist == FDATA(pObj)->e_dist && + dfsfast_e( pObj, NULL )) { +#ifdef DEBUG_PRINT_FLOWS + printf("\n\n"); +#endif + flow++; + } + } + } + + printf("\t\tmax-flow1 = %d \t", flow); + + // (ii) complete max-flow computation + // also, marks source-reachable nodes + do { + last = flow; + Abc_NtkForEachLatch( pNtk, pObj, i ) { + if (dfsplain_e( pObj, NULL )) { +#ifdef DEBUG_PRINT_FLOWS + printf("\n\n"); +#endif + flow++; + Abc_NtkForEachObj( pNtk, pObj2, j ) + FUNSET( pObj2, VISITED ); + } + } + } while (flow > last); + + printf("max-flow2 = %d\n", flow); + + return flow; +} + + +/**Function************************************************************* + + Synopsis [Restores latch boxes.] + + Description [Latchless BI/BO nodes are removed. Latch boxes are + restored around remaining latches.] + + SideEffects [Deletes nodes as appropriate.] + + SeeAlso [] + +***********************************************************************/ +void +Abc_FlowRetime_FixLatchBoxes( Abc_Ntk_t *pNtk, Vec_Ptr_t *vBoxIns ) { + int i; + Abc_Obj_t *pObj, *pNext, *pBo = NULL, *pBi = NULL; + Vec_Ptr_t *vFreeBi = Vec_PtrAlloc( 100 ); + Vec_Ptr_t *vFreeBo = Vec_PtrAlloc( 100 ); + Vec_Ptr_t *vNodes; + + // 1. remove empty bi/bo pairs + while(Vec_PtrSize( vBoxIns )) { + pBi = (Abc_Obj_t *)Vec_PtrPop( vBoxIns ); + assert(Abc_ObjIsBi(pBi)); + assert(Abc_ObjFanoutNum(pBi) == 1); + assert(Abc_ObjFaninNum(pBi) == 1); + pBo = Abc_ObjFanout0(pBi); + assert(!Abc_ObjFaninC0(pBo)); + + if (Abc_ObjIsBo(pBo)) { + // an empty bi/bo pair + + Abc_ObjRemoveFanins( pBo ); + // transfer complement from BI, if present + assert(!Abc_ObjIsComplement(Abc_ObjFanin0(pBi))); + Abc_ObjBetterTransferFanout( pBo, Abc_ObjFanin0(pBi), Abc_ObjFaninC0(pBi) ); + + Abc_ObjRemoveFanins( pBi ); + pBi->fCompl0 = 0; + Vec_PtrPush( vFreeBi, pBi ); + Vec_PtrPush( vFreeBo, pBo ); + + // free names + // if (Nm_ManFindNameById(pNtk->pManName, Abc_ObjId(pBi))) + // Nm_ManDeleteIdName( pNtk->pManName, Abc_ObjId(pBi)); + //if (Nm_ManFindNameById(pNtk->pManName, Abc_ObjId(pBo))) + // Nm_ManDeleteIdName( pNtk->pManName, Abc_ObjId(pBo)); + + // check for complete detachment + assert(Abc_ObjFaninNum(pBi) == 0); + assert(Abc_ObjFanoutNum(pBi) == 0); + assert(Abc_ObjFaninNum(pBo) == 0); + assert(Abc_ObjFanoutNum(pBo) == 0); + } else assert(Abc_ObjIsLatch(pBo)); + } + + // 2. add bi/bos as necessary for latches + Abc_NtkForEachLatch( pNtk, pObj, i ) { + assert(Abc_ObjFaninNum(pObj) == 1); + if (Abc_ObjFanoutNum(pObj)) + pBo = Abc_ObjFanout0(pObj); + else pBo = NULL; + pBi = Abc_ObjFanin0(pObj); + + // add BO + if (!pBo || !Abc_ObjIsBo(pBo)) { + pBo = (Abc_Obj_t *)Vec_PtrPop( vFreeBo ); + if (Abc_ObjFanoutNum(pObj)) Abc_ObjTransferFanout( pObj, pBo ); + Abc_ObjAddFanin( pBo, pObj ); + } + // add BI + if (!Abc_ObjIsBi(pBi)) { + pBi = (Abc_Obj_t *)Vec_PtrPop( vFreeBi ); + assert(Abc_ObjFaninNum(pBi) == 0); + Abc_ObjAddFanin( pBi, Abc_ObjFanin0(pObj) ); + pBi->fCompl0 = pObj->fCompl0; + Abc_ObjRemoveFanins( pObj ); + Abc_ObjAddFanin( pObj, pBi ); + } + } + + // delete remaining BIs and BOs + while(Vec_PtrSize( vFreeBi )) { + pObj = (Abc_Obj_t *)Vec_PtrPop( vFreeBi ); + Abc_NtkDeleteObj( pObj ); + } + while(Vec_PtrSize( vFreeBo )) { + pObj = (Abc_Obj_t *)Vec_PtrPop( vFreeBo ); + Abc_NtkDeleteObj( pObj ); + } + +#if defined(DEBUG_CHECK) + Abc_NtkForEachObj( pNtk, pObj, i ) { + if (Abc_ObjIsBo(pObj)) { + assert(Abc_ObjFaninNum(pObj) == 1); + assert(Abc_ObjIsLatch(Abc_ObjFanin0(pObj))); + } + if (Abc_ObjIsBi(pObj)) { + assert(Abc_ObjFaninNum(pObj) == 1); + assert(Abc_ObjFanoutNum(pObj) == 1); + assert(Abc_ObjIsLatch(Abc_ObjFanout0(pObj))); + } + if (Abc_ObjIsLatch(pObj)) { + assert(Abc_ObjFanoutNum(pObj) == 1); + assert(Abc_ObjFaninNum(pObj) == 1); + } + } +#endif + + Vec_PtrFree( vFreeBi ); + Vec_PtrFree( vFreeBo ); +} + + +/**Function************************************************************* + + Synopsis [Checks register count along all combinational paths.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void +Abc_FlowRetime_VerifyPathLatencies( Abc_Ntk_t * pNtk ) { + int i; + Abc_Obj_t *pObj; + fPathError = 0; + + printf("\t\tVerifying latency along all paths..."); + + Abc_NtkForEachObj( pNtk, pObj, i ) { + if (Abc_ObjIsBo(pObj)) { + Abc_FlowRetime_VerifyPathLatencies_rec( pObj, 0 ); + } else if (!fIsForward && Abc_ObjIsPi(pObj)) { + Abc_FlowRetime_VerifyPathLatencies_rec( pObj, 0 ); + } + + if (fPathError) { + if (Abc_ObjFaninNum(pObj) > 0) { + printf("fanin "); + print_node(Abc_ObjFanin0(pObj)); + } + printf("\n"); + exit(0); + } + } + + printf(" ok\n"); + + Abc_NtkForEachObj( pNtk, pObj, i ) { + pObj->fMarkA = 0; + pObj->fMarkB = 0; + pObj->fMarkC = 0; + } +} + + +int +Abc_FlowRetime_VerifyPathLatencies_rec( Abc_Obj_t * pObj, int markD ) { + int i, j; + Abc_Obj_t *pNext; + int fCare = 0; + int markC = pObj->fMarkC; + + if (!pObj->fMarkB) { + pObj->fMarkB = 1; // visited + + if (Abc_ObjIsLatch(pObj)) + markC = 1; // latch in output + + if (!fIsForward && !Abc_ObjIsPo(pObj) && !Abc_ObjFanoutNum(pObj)) + return -1; // dangling non-PO outputs : don't care what happens + + Abc_ObjForEachFanout( pObj, pNext, i ) { + // reached end of cycle? + if ( Abc_ObjIsBo(pNext) || + (fIsForward && Abc_ObjIsPo(pNext)) ) { + if (!markD && !Abc_ObjIsLatch(pObj)) { + printf("\nERROR: no-latch path (end)\n"); + print_node(pNext); + printf("\n"); + fPathError = 1; + } + } else if (!fIsForward && Abc_ObjIsPo(pNext)) { + if (markD || Abc_ObjIsLatch(pObj)) { + printf("\nERROR: extra-latch path to outputs\n"); + print_node(pNext); + printf("\n"); + fPathError = 1; + } + } else { + j = Abc_FlowRetime_VerifyPathLatencies_rec( pNext, markD || Abc_ObjIsLatch(pObj) ); + if (j >= 0) { + markC |= j; + fCare = 1; + } + } + + if (fPathError) { + print_node(pObj); + printf("\n"); + return 0; + } + } + } + + if (!fCare) return -1; + + if (markC && markD) { + printf("\nERROR: mult-latch path\n"); + print_node(pObj); + printf("\n"); + fPathError = 1; + } + if (!markC && !markD) { + printf("\nERROR: no-latch path (inter)\n"); + print_node(pObj); + printf("\n"); + fPathError = 1; + } + + return (pObj->fMarkC = markC); +} + + +/**Function************************************************************* + + Synopsis [Copies initial state from latches to BO nodes.] + + Description [Initial states are marked on BO nodes with INIT_0 and + INIT_1 flags in their Flow_Data structures.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void +Abc_FlowRetime_CopyInitState( Abc_Obj_t * pSrc, Abc_Obj_t * pDest ) { + Abc_Obj_t *pObj; + + if (!fComputeInitState) return; + + assert(Abc_ObjIsLatch(pSrc)); + assert(Abc_ObjFanin0(pDest) == pSrc); + assert(!Abc_ObjFaninC0(pDest)); + + FUNSET(pDest, INIT_CARE); + if (Abc_LatchIsInit0(pSrc)) { + FSET(pDest, INIT_0); + } else if (Abc_LatchIsInit1(pSrc)) { + FSET(pDest, INIT_1); + } + + if (!fIsForward) { + pObj = Abc_ObjData(pSrc); + assert(Abc_ObjIsPi(pObj)); + FDATA(pDest)->pInitObj = pObj; + } +} + + +/**Function************************************************************* + + Synopsis [Implements min-cut.] + + Description [Requires source-reachable nodes to be marked VISITED.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int +Abc_FlowRetime_ImplementCut( Abc_Ntk_t * pNtk ) { + int i, j, cut = 0, unmoved = 0; + Abc_Obj_t *pObj, *pReg, *pNext, *pBo = NULL, *pBi = NULL; + Vec_Ptr_t *vFreeRegs = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) ); + Vec_Ptr_t *vBoxIns = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) ); + Vec_Ptr_t *vMove = Vec_PtrAlloc( 100 ); + + // remove latches from netlist + Abc_NtkForEachLatch( pNtk, pObj, i ) { + pBo = Abc_ObjFanout0(pObj); + pBi = Abc_ObjFanin0(pObj); + assert(Abc_ObjIsBo(pBo) && Abc_ObjIsBi(pBi)); + Vec_PtrPush( vBoxIns, pBi ); + + // copy initial state values to BO + Abc_FlowRetime_CopyInitState( pObj, pBo ); + + // re-use latch elsewhere + Vec_PtrPush( vFreeRegs, pObj ); + FSET(pBo, CROSS_BOUNDARY); + + // cut out of netlist + Abc_ObjPatchFanin( pBo, pObj, pBi ); + Abc_ObjRemoveFanins( pObj ); + + // free name + // if (Nm_ManFindNameById(pNtk->pManName, Abc_ObjId(pObj))) + // Nm_ManDeleteIdName( pNtk->pManName, Abc_ObjId(pObj)); + } + + // insert latches into netlist + Abc_NtkForEachObj( pNtk, pObj, i ) { + if (Abc_ObjIsLatch( pObj )) continue; + + // a latch is required on every node that lies across the min-cit + assert(!fIsForward || !FTEST(pObj, VISITED_E) || FTEST(pObj, VISITED_R)); + if (FTEST(pObj, VISITED_R) && !FTEST(pObj, VISITED_E)) { + assert(FTEST(pObj, FLOW)); + + // count size of cut + cut++; + if ((fIsForward && Abc_ObjIsBo(pObj)) || + (!fIsForward && Abc_ObjIsBi(pObj))) + unmoved++; + + // only insert latch between fanouts that lie across min-cut + // some fanout paths may be cut at deeper points + Abc_ObjForEachFanout( pObj, pNext, j ) + if (fIsForward) { + if (!FTEST(pNext, VISITED_R) || + FTEST(pNext, BLOCK) || + FTEST(pNext, CROSS_BOUNDARY) || + Abc_ObjIsLatch(pNext)) + Vec_PtrPush(vMove, pNext); + } else { + if (FTEST(pNext, VISITED_E) || + FTEST(pNext, CROSS_BOUNDARY)) + Vec_PtrPush(vMove, pNext); + } + if (Vec_PtrSize(vMove) == 0) + print_node(pObj); + + assert(Vec_PtrSize(vMove) > 0); + + // insert one of re-useable registers + assert(Vec_PtrSize( vFreeRegs )); + pReg = (Abc_Obj_t *)Vec_PtrPop( vFreeRegs ); + + Abc_ObjAddFanin(pReg, pObj); + while(Vec_PtrSize( vMove )) { + pNext = (Abc_Obj_t *)Vec_PtrPop( vMove ); + Abc_ObjPatchFanin( pNext, pObj, pReg ); + if (Abc_ObjIsBi(pNext)) assert(Abc_ObjFaninNum(pNext) == 1); + + } + if (Abc_ObjIsBi(pObj)) assert(Abc_ObjFaninNum(pObj) == 1); + } + } + +#if defined(DEBUG_CHECK) + Abc_FlowRetime_VerifyPathLatencies( pNtk ); +#endif + + // delete remaining latches + while(Vec_PtrSize( vFreeRegs )) { + pReg = (Abc_Obj_t *)Vec_PtrPop( vFreeRegs ); + Abc_NtkDeleteObj( pReg ); + } + + // update initial states + Abc_FlowRetime_InitState( pNtk ); + + // restore latch boxes + Abc_FlowRetime_FixLatchBoxes( pNtk, vBoxIns ); + + Vec_PtrFree( vFreeRegs ); + Vec_PtrFree( vMove ); + Vec_PtrFree( vBoxIns ); + + printf("\t\tmin-cut = %d (unmoved = %d)\n", cut, unmoved); + return cut; +} + +/**Function************************************************************* + + Synopsis [Adds dummy fanin.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void +Abc_FlowRetime_AddDummyFanin( Abc_Obj_t * pObj ) { + Abc_Ntk_t *pNtk = Abc_ObjNtk( pObj ); + + if (Abc_NtkHasAig(pNtk)) + Abc_ObjAddFanin(pObj, Abc_AigConst1( pNtk )); + else + Abc_ObjAddFanin(pObj, Abc_NtkCreateNodeConst0( pNtk )); +} + + +/**Function************************************************************* + + Synopsis [Prints information about a node.] + + Description [Debuging.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void +print_node(Abc_Obj_t *pObj) { + int i; + Abc_Obj_t * pNext; + char m[6]; + + m[0] = 0; + if (pObj->fMarkA) + strcat(m, "A"); + if (pObj->fMarkB) + strcat(m, "B"); + if (pObj->fMarkC) + strcat(m, "C"); + + printf("node %d type=%d (%x%s) fanouts {", Abc_ObjId(pObj), Abc_ObjType(pObj), FDATA(pObj)->mark, m); + Abc_ObjForEachFanout( pObj, pNext, i ) + printf("%d (%d),", Abc_ObjId(pNext), FDATA(pNext)->mark); + printf("} fanins {"); + Abc_ObjForEachFanin( pObj, pNext, i ) + printf("%d (%d),", Abc_ObjId(pNext), FDATA(pNext)->mark); + printf("} "); +} + +void +print_node2(Abc_Obj_t *pObj) { + int i; + Abc_Obj_t * pNext; + char m[6]; + + m[0] = 0; + if (pObj->fMarkA) + strcat(m, "A"); + if (pObj->fMarkB) + strcat(m, "B"); + if (pObj->fMarkC) + strcat(m, "C"); + + printf("node %d type=%d fanouts {", Abc_ObjId(pObj), Abc_ObjType(pObj), m); + Abc_ObjForEachFanout( pObj, pNext, i ) + printf("%d ,", Abc_ObjId(pNext)); + printf("} fanins {"); + Abc_ObjForEachFanin( pObj, pNext, i ) + printf("%d ,", Abc_ObjId(pNext)); + printf("} "); +} + + +/**Function************************************************************* + + Synopsis [Transfers fanout.] + + Description [Does not produce an error if there is no fanout. + Complements as necessary.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void +Abc_ObjBetterTransferFanout( Abc_Obj_t * pFrom, Abc_Obj_t * pTo, int compl ) { + Abc_Obj_t *pNext; + + while(Abc_ObjFanoutNum(pFrom) > 0) { + pNext = Abc_ObjFanout0(pFrom); + Abc_ObjPatchFanin( pNext, pFrom, Abc_ObjNotCond(pTo, compl) ); + } +} diff --git a/src/opt/fret/fretime.h b/src/opt/fret/fretime.h new file mode 100644 index 00000000..f12bd30b --- /dev/null +++ b/src/opt/fret/fretime.h @@ -0,0 +1,140 @@ +/**CFile**************************************************************** + + FileName [fretime.h] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Flow-based retiming package.] + + Synopsis [Header file for retiming package.] + + Author [Aaron Hurst] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - January 1, 2008.] + + Revision [$Id: fretime.h,v 1.00 2008/01/01 00:00:00 ahurst Exp $] + +***********************************************************************/ + +#if !defined(RETIME_H_) +#define RETIME_H_ + +#include "abc.h" + +#define IGNORE_TIMING +// #define DEBUG_PRINT_FLOWS +// #define DEBUG_VISITED +// #define DEBUG_PREORDER +// #define DEBUG_CHECK + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define MAX_DIST 30000 + +// flags in Flow_Data structure... +#define VISITED_E 0x01 +#define VISITED_R 0x02 +#define VISITED (VISITED_E | VISITED_R) +#define FLOW 0x04 +#define CROSS_BOUNDARY 0x08 +#define BLOCK 0x10 +#define INIT_0 0x20 +#define INIT_1 0x40 +#define INIT_CARE (INIT_0 | INIT_1) + +typedef struct Untimed_Flow_Data_t_ { + unsigned int mark : 8; + + union { + Abc_Obj_t *pred; + /* unsigned int var; */ + Abc_Obj_t *pInitObj; + }; + + unsigned int e_dist : 16; + unsigned int r_dist : 16; +} Untimed_Flow_Data_t; + +typedef struct Timed_Flow_Data_t_ { + unsigned int mark : 8; + + union { + Abc_Obj_t *pred; + Vec_Ptr_t *vTimeInEdges; + /* unsigned int var; */ + Abc_Obj_t *pInitObj; + }; + + unsigned int e_dist : 16; + unsigned int r_dist : 16; + + Vec_Ptr_t vTimeEdges; + +} Timed_Flow_Data_t; + +#if defined(IGNORE_TIMING) +typedef Untimed_Flow_Data_t Flow_Data_t; +#else +typedef Timed_Flow_Data_t Flow_Data_t; +#endif + +// useful macros for manipulating Flow_Data structure... +#define FDATA( x ) ((Flow_Data_t *)Abc_ObjCopy(x)) +#define FSET( x, y ) ((Flow_Data_t *)Abc_ObjCopy(x))->mark |= y +#define FUNSET( x, y ) ((Flow_Data_t *)Abc_ObjCopy(x))->mark &= ~y +#define FTEST( x, y ) (((Flow_Data_t *)Abc_ObjCopy(x))->mark & y) +#define FTIMEEDGES( x ) &(((Timed_Flow_Data_t *)Abc_ObjCopy(x))->vTimeEdges) + +static inline void FSETPRED(Abc_Obj_t *pObj, Abc_Obj_t *pPred) { + assert(!Abc_ObjIsLatch(pObj)); // must preserve field to maintain init state linkage + FDATA(pObj)->pred = pPred; +} +static inline Abc_Obj_t * FGETPRED(Abc_Obj_t *pObj) { + return FDATA(pObj)->pred; +} + +/*=== fretMain.c ==========================================================*/ + +Abc_Ntk_t * Abc_FlowRetime_MinReg( Abc_Ntk_t * pNtk, int fVerbose, int fComputeInitState, + int fForward, int fBackward, int nMaxIters, + int maxDelay); + +void print_node(Abc_Obj_t *pObj); + +void Abc_ObjBetterTransferFanout( Abc_Obj_t * pFrom, Abc_Obj_t * pTo, int compl ); + +extern int fIsForward; +extern int fSinkDistTerminate; +extern Vec_Int_t *vSinkDistHist; +extern int maxDelayCon; +extern int fComputeInitState; + +/*=== fretFlow.c ==========================================================*/ + +int dfsplain_e( Abc_Obj_t *pObj, Abc_Obj_t *pPred ); +int dfsplain_r( Abc_Obj_t *pObj, Abc_Obj_t *pPred ); + +void dfsfast_preorder( Abc_Ntk_t *pNtk ); +int dfsfast_e( Abc_Obj_t *pObj, Abc_Obj_t *pPred ); +int dfsfast_r( Abc_Obj_t *pObj, Abc_Obj_t *pPred ); + +/*=== fretInit.c ==========================================================*/ + +void Abc_FlowRetime_PrintInitStateInfo( Abc_Ntk_t * pNtk ); + +void Abc_FlowRetime_InitState( Abc_Ntk_t * pNtk ); + +void Abc_FlowRetime_UpdateForwardInit( Abc_Ntk_t * pNtk ); +void Abc_FlowRetime_UpdateBackwardInit( Abc_Ntk_t * pNtk ); + +void Abc_FlowRetime_SetupBackwardInit( Abc_Ntk_t * pNtk ); +void Abc_FlowRetime_SolveBackwardInit( Abc_Ntk_t * pNtk ); + +extern Abc_Ntk_t *pInitNtk; +extern int fSolutionIsDc; + +#endif diff --git a/src/opt/fret/module.make b/src/opt/fret/module.make new file mode 100644 index 00000000..72fdfec9 --- /dev/null +++ b/src/opt/fret/module.make @@ -0,0 +1,4 @@ +SRC += src/opt/fret/fretMain.c \ + src/opt/fret/fretFlow.c \ + src/opt/fret/fretInit.c + -- cgit v1.2.3