diff options
-rw-r--r-- | src/aig/gia/giaFadds.c | 249 | ||||
-rw-r--r-- | src/aig/gia/giaTim.c | 64 | ||||
-rw-r--r-- | src/base/abci/abc.c | 75 | ||||
-rw-r--r-- | src/bool/rpo/rpo.h | 6 |
4 files changed, 354 insertions, 40 deletions
diff --git a/src/aig/gia/giaFadds.c b/src/aig/gia/giaFadds.c index 7b463f42..08886088 100644 --- a/src/aig/gia/giaFadds.c +++ b/src/aig/gia/giaFadds.c @@ -648,14 +648,15 @@ void Gia_ManDupWithFaddBoxes_rec( Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * p Gia_ManDupWithFaddBoxes_rec( pNew, p, Gia_ObjFanin1(pObj), vFadds, vMap, vChains, vMap2Chain, vTruths ); pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); } -Gia_Man_t * Gia_ManDupWithFaddBoxes( Gia_Man_t * p, int nFaddMin, int fVerbose ) +Gia_Man_t * Gia_ManDupWithNaturalBoxes( Gia_Man_t * p, int nFaddMin, int fVerbose ) { abctime clk = Abc_Clock(); - Gia_Man_t * pNew, * pTemp; + Gia_Man_t * pNew;//, * pTemp; Vec_Int_t * vFadds, * vMap, * vMap2Chain, * vTruths, * vChain; Vec_Wec_t * vChains; Gia_Obj_t * pObj; int i, nBoxes; + assert( Gia_ManBoxNum(p) == 0 ); // detect FADDs vFadds = Gia_ManDetectFullAdders( p, fVerbose ); @@ -718,13 +719,13 @@ Gia_Man_t * Gia_ManDupWithFaddBoxes( Gia_Man_t * p, int nFaddMin, int fVerbose ) assert( nBoxes == (Gia_ManCoNum(pNew) - Gia_ManCoNum(p)) / 3 ); pNew->pManTime = Gia_ManGenerateTim( Gia_ManCiNum(p), Gia_ManCoNum(p), nBoxes, 3, 2 ); pNew->pAigExtra = Gia_ManGenerateExtraAig( nBoxes, 3, 2 ); - +/* // normalize pNew = Gia_ManDupNormalize( pTemp = pNew ); pNew->pManTime = pTemp->pManTime; pTemp->pManTime = NULL; pNew->pAigExtra = pTemp->pAigExtra; pTemp->pAigExtra = NULL; Gia_ManStop( pTemp ); - +*/ //pNew = Gia_ManDupCollapse( pTemp = pNew, pNew->pAigExtra, NULL ); //Gia_ManStop( pTemp ); @@ -734,6 +735,246 @@ Gia_Man_t * Gia_ManDupWithFaddBoxes( Gia_Man_t * p, int nFaddMin, int fVerbose ) return pNew; } +/**Function************************************************************* + + Synopsis [Converting AIG with annotated carry-chains into AIG with boxes.] + + Description [Assumes that annotations are pObj->fMark0 or pObj->fMark1. + Only one of these can be set to 1. If fMark0 (fMark1) is set to 1, + the first (second) input of an AND-gate is chained.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManDupWithArtificalFaddBoxes( Gia_Man_t * p ) +{ + Gia_Man_t * pNew; + Gia_Obj_t * pObj; + int i, nRealPis, nRealPos, nBoxes = Gia_ManBoxNum(p); + // if AIG already has (natural) FADD boxes, it should not un-normalized + Gia_ManFillValue( p ); + 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_ObjIsCi(pObj) ) + pObj->Value = Gia_ManAppendCi( pNew ); + else if ( Gia_ObjIsCo(pObj) ) + pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); + else if ( !pObj->fMark0 && !pObj->fMark1 ) // AND-gate + pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + else // AND-gate with chain + { + int iCiLit, iOtherLit, iLit0, iLit1, iLit2; + assert( pObj->fMark0 != pObj->fMark1 ); + iCiLit = pObj->fMark0 ? Gia_ObjFanin0Copy(pObj) : Gia_ObjFanin1Copy(pObj); + iOtherLit = pObj->fMark0 ? Gia_ObjFanin1Copy(pObj) : Gia_ObjFanin0Copy(pObj); + iLit0 = Abc_LitNotCond( iCiLit, Abc_LitIsCompl(iCiLit) ); + iLit1 = Abc_LitNotCond( iOtherLit, Abc_LitIsCompl(iCiLit) ); + iLit2 = Abc_LitNotCond( 0, Abc_LitIsCompl(iCiLit) ); + // add COs + Gia_ManAppendCo( pNew, iLit0 ); + Gia_ManAppendCo( pNew, iLit1 ); + Gia_ManAppendCo( pNew, iLit2 ); + // add CI (unused sum bit) + Gia_ManAppendCi(pNew); + // add CI (carry bit) + pObj->Value = Abc_LitNotCond( Gia_ManAppendCi(pNew), Abc_LitIsCompl(iCiLit) ); + nBoxes++; + } + } + // other information +// nBoxes += (Gia_ManCiNum(pNew) - Gia_ManCiNum(p)) / 2; +// assert( nBoxes == Gia_ManBoxNum(p) + (Gia_ManCoNum(pNew) - Gia_ManCoNum(p)) / 3 ); + nRealPis = Gia_ManBoxNum(p) ? Tim_ManPiNum((Tim_Man_t *)p->pManTime) : Gia_ManCiNum(p); + nRealPos = Gia_ManBoxNum(p) ? Tim_ManPoNum((Tim_Man_t *)p->pManTime) : Gia_ManCoNum(p); + pNew->pManTime = Gia_ManGenerateTim( nRealPis, nRealPos, nBoxes, 3, 2 ); + pNew->pAigExtra = Gia_ManGenerateExtraAig( nBoxes, 3, 2 ); + // optionally normalize the AIG + return pNew; +} +Gia_Man_t * Gia_ManDupWithArtificalFaddBoxesTest( Gia_Man_t * p ) +{ + Gia_Man_t * pNew; + Gia_Obj_t * pObj; + int i; + // label some and-gates + Gia_ManCleanMark01( p ); + Gia_ManForEachAnd( p, pObj, i ) + { + pObj->fMark0 = i % 5; + pObj->fMark1 = i % 7; + if ( pObj->fMark0 && pObj->fMark1 ) + pObj->fMark0 = pObj->fMark1 = 0; + } + + // output new AIG + pNew = Gia_ManDupWithArtificalFaddBoxes( p ); + Gia_ManCleanMark01( p ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [Computes AIG delay information when boxes are used.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Gia_ManFindAnnotatedDelay( Gia_Man_t * p, int DelayC, int * pnBoxes ) +{ + Gia_Obj_t * pObj; + int * pDelays = Vec_IntArray(p->vLevels); + int i, Delay, Delay0, Delay1, DelayMax = 0, nBoxes = 0; + Vec_IntFill( p->vLevels, Gia_ManObjNum(p), 0 ); + Gia_ManForEachObj1( p, pObj, i ) + { + if ( Gia_ObjIsCi(pObj) ) + continue; + if ( Gia_ObjIsCo(pObj) ) + { + pDelays[i] = pDelays[Gia_ObjFaninId0(pObj, i)]; + DelayMax = Abc_MaxInt( DelayMax, pDelays[i] ); + continue; + } + assert( !pObj->fMark0 || !pObj->fMark1 ); + Delay0 = pDelays[Gia_ObjFaninId0(pObj, i)]; + Delay1 = pDelays[Gia_ObjFaninId1(pObj, i)]; + if ( pObj->fMark0 ) + { + Delay = Abc_MaxInt( Delay0 + DelayC, Delay1 + 100 ); + nBoxes++; + } + else if ( pObj->fMark1 ) + { + Delay = Abc_MaxInt( Delay1 + DelayC, Delay0 + 100 ); + nBoxes++; + } + else + Delay = Abc_MaxInt( Delay0 + 100, Delay1 + 100 ); + pDelays[i] = Delay; + } + if ( pnBoxes ) + *pnBoxes = nBoxes; + return DelayMax; +} +int Gia_ManFindInternalNode( Gia_Man_t * p ) +{ + Gia_Obj_t * pObj; + int * pDelays = Vec_IntArray(p->vLevels); + int i, iMax = -1, DelayMax = 0; + Gia_ManForEachAnd( p, pObj, i ) + { + if ( pObj->fMark0 || pObj->fMark1 || pObj->fPhase ) + continue; + if ( DelayMax > pDelays[i] ) + continue; + DelayMax = pDelays[i]; + iMax = i; + } + return iMax; +} +int Gia_ManFindPath( Gia_Man_t * p, int DelayC, int nPathMin, int nPathMax, Vec_Int_t * vPath ) +{ + Gia_Obj_t * pObj, * pFanin0, * pFanin1; + int * pDelays = Vec_IntArray(p->vLevels); + int i, iLit, iMax = Gia_ManFindInternalNode( p ); + if ( iMax == -1 ) + return -1; + Vec_IntClear( vPath ); + pObj = Gia_ManObj(p, iMax); + assert( Gia_ObjIsAnd(pObj) ); + assert( !(pObj->fMark0 || pObj->fMark1 || pObj->fPhase) ); + while ( Gia_ObjIsAnd(pObj) ) + { + pFanin0 = Gia_ObjFanin0(pObj); + pFanin1 = Gia_ObjFanin1(pObj); + if ( (pFanin0->fMark0 || pFanin0->fMark1 || Gia_ObjIsCi(pFanin0)) && (pFanin1->fMark0 || pFanin1->fMark1 || Gia_ObjIsCi(pFanin1)) ) + break; + if ( pFanin0->fMark0 || pFanin0->fMark1 || Gia_ObjIsCi(pFanin0) ) + { + Vec_IntPush( vPath, Abc_Var2Lit(Gia_ObjId(p, pObj), 1) ); + pObj = pFanin1; + } + else if ( pFanin1->fMark0 || pFanin1->fMark1 || Gia_ObjIsCi(pFanin1) ) + { + Vec_IntPush( vPath, Abc_Var2Lit(Gia_ObjId(p, pObj), 0) ); + pObj = pFanin0; + } + else + { + if ( pDelays[Gia_ObjId(p, pFanin1)] > pDelays[Gia_ObjId(p, pFanin0)] ) + { + Vec_IntPush( vPath, Abc_Var2Lit(Gia_ObjId(p, pObj), 1) ); + pObj = pFanin1; + } + else + { + Vec_IntPush( vPath, Abc_Var2Lit(Gia_ObjId(p, pObj), 0) ); + pObj = pFanin0; + } + } + } + if ( Vec_IntSize(vPath) < nPathMin ) + { + Gia_ManObj(p, iMax)->fPhase = 1; + return 0; + } + // label nodes + if ( Vec_IntSize(vPath) > nPathMax ) + Vec_IntShrink( vPath, nPathMax ); + Vec_IntForEachEntry( vPath, iLit, i ) + if ( Abc_LitIsCompl(iLit) ) + Gia_ManObj(p, Abc_Lit2Var(iLit))->fMark1 = 1; + else + Gia_ManObj(p, Abc_Lit2Var(iLit))->fMark0 = 1; + return Vec_IntSize(vPath); +} +int Gia_ManIteratePaths( Gia_Man_t * p, int DelayC, int nPathMin, int nPathMax, int nPathLimit, int fVerbose ) +{ + Vec_Int_t * vPath = Vec_IntAlloc( 100 ); + int i, RetValue, nBoxes, MaxDelay, nPaths = 0; + assert( p->vLevels == NULL ); + p->vLevels = Vec_IntStart( Gia_ManObjNum(p) ); + Gia_ManCleanMark01( p ); + Gia_ManCleanPhase( p ); + if ( fVerbose ) + printf( "Running path detection: BoxDelay = %d, PathMin = %d, PathMax = %d, PathLimit = %d.\n", DelayC, nPathMin, nPathMax, nPathLimit ); + for ( i = 0; i < nPathLimit; i++ ) + { + MaxDelay = Gia_ManFindAnnotatedDelay( p, DelayC, &nBoxes ); + RetValue = Gia_ManFindPath( p, DelayC, nPathMin, nPathMax, vPath ); + if ( RetValue == -1 ) + break; + nPaths += (RetValue > 0); + if ( fVerbose ) + printf( "Iter %5d : Paths = %2d. Boxes = %2d. Total boxes = %6d. Max delay = %5d.\n", i, nPaths, RetValue, nBoxes, MaxDelay ); + } + Vec_IntFree( vPath ); + Vec_IntFreeP( &p->vLevels ); + return 1; +} +Gia_Man_t * Gia_ManDupWithArtificialBoxes( Gia_Man_t * p, int DelayC, int nPathMin, int nPathMax, int nPathLimit, int fUseFanout, int fVerbose ) +{ + Gia_Man_t * pNew; + if ( Gia_ManBoxNum(p) > 0 ) + { + printf( "Currently artifical carry-chains cannot be detected when natural ones are present.\n" ); + return NULL; + } + Gia_ManIteratePaths( p, DelayC, nPathMin, nPathMax, nPathLimit, fVerbose ); + pNew = Gia_ManDupWithArtificalFaddBoxes( p ); + return pNew; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/aig/gia/giaTim.c b/src/aig/gia/giaTim.c index 1d5a2f36..5640baa4 100644 --- a/src/aig/gia/giaTim.c +++ b/src/aig/gia/giaTim.c @@ -822,53 +822,59 @@ int Gia_ManVerifyWithBoxes( Gia_Man_t * pGia, void * pParsInit, char * pFileSpec printf( "Spec file is not given. Use standard flow.\n" ); return Status; } - if ( pGia->pManTime == NULL ) - { - printf( "Design has no tim manager. Use standard flow.\n" ); - return Status; - } - if ( pGia->pAigExtra == NULL ) + if ( Gia_ManBoxNum(pGia) && pGia->pAigExtra == NULL ) { printf( "Design has no box logic. Use standard flow.\n" ); return Status; } // read original AIG pSpec = Gia_AigerRead( pFileSpec ? pFileSpec : pGia->pSpec, 0, 0 ); - if ( pSpec->pManTime == NULL ) + if ( Gia_ManBoxNum(pSpec) && pSpec->pAigExtra == NULL ) { - printf( "Spec has no tim manager. Use standard flow.\n" ); + Gia_ManStop( pSpec ); + printf( "Spec has no box logic. Use standard flow.\n" ); return Status; } - if ( pSpec->pAigExtra == NULL ) + // prepare miter + if ( pGia->pManTime == NULL && pSpec->pManTime == NULL ) { - printf( "Spec has no box logic. Use standard flow.\n" ); - return Status; + pGia0 = Gia_ManDup( pSpec ); + pGia1 = Gia_ManDup( pGia ); } - // if timing managers have different number of black boxes, - // it is possible that some of the boxes are swept away - if ( Tim_ManBlackBoxNum( (Tim_Man_t *)pSpec->pManTime ) > 0 ) + else { - // specification cannot have fewer boxes than implementation - if ( Tim_ManBoxNum( (Tim_Man_t *)pSpec->pManTime ) < Tim_ManBoxNum( (Tim_Man_t *)pGia->pManTime ) ) + // if timing managers have different number of black boxes, + // it is possible that some of the boxes are swept away + if ( pSpec->pManTime && Tim_ManBlackBoxNum((Tim_Man_t *)pSpec->pManTime) > 0 && Gia_ManBoxNum(pGia) > 0 ) { - printf( "Spec has more boxes than the design. Cannot proceed.\n" ); - return Status; - } - // to align the boxes, find what boxes of pSpec are dropped in pGia - if ( Tim_ManBoxNum( (Tim_Man_t *)pSpec->pManTime ) != Tim_ManBoxNum( (Tim_Man_t *)pGia->pManTime ) ) - { - vBoxPres = Tim_ManAlignTwo( (Tim_Man_t *)pSpec->pManTime, (Tim_Man_t *)pGia->pManTime ); - if ( vBoxPres == NULL ) + // specification cannot have fewer boxes than implementation + if ( Gia_ManBoxNum(pSpec) < Gia_ManBoxNum(pGia) ) { - printf( "Boxes of spec and design cannot be aligned. Cannot proceed.\n" ); + printf( "Spec has less boxes than the design. Cannot proceed.\n" ); return Status; } + // to align the boxes, find what boxes of pSpec are dropped in pGia + if ( Gia_ManBoxNum(pSpec) > Gia_ManBoxNum(pGia) ) + { + vBoxPres = Tim_ManAlignTwo( (Tim_Man_t *)pSpec->pManTime, (Tim_Man_t *)pGia->pManTime ); + if ( vBoxPres == NULL ) + { + printf( "Boxes of spec and design cannot be aligned. Cannot proceed.\n" ); + return Status; + } + } } + // collapse two designs + if ( Gia_ManBoxNum(pSpec) > 0 ) + pGia0 = Gia_ManDupCollapse( pSpec, pSpec->pAigExtra, vBoxPres ); + else + pGia0 = Gia_ManDup( pSpec ); + if ( Gia_ManBoxNum(pGia) > 0 ) + pGia1 = Gia_ManDupCollapse( pGia, pGia->pAigExtra, NULL ); + else + pGia1 = Gia_ManDup( pGia ); + Vec_IntFreeP( &vBoxPres ); } - // collapse two designs - pGia0 = Gia_ManDupCollapse( pSpec, pSpec->pAigExtra, vBoxPres ); - pGia1 = Gia_ManDupCollapse( pGia, pGia->pAigExtra, NULL ); - Vec_IntFreeP( &vBoxPres ); // compute the miter pMiter = Gia_ManMiter( pGia0, pGia1, 0, 1, 0, 0, fVerbose ); if ( pMiter ) diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 7b08c564..a6091f59 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -36581,11 +36581,13 @@ usage: ***********************************************************************/ int Abc_CommandAbc9Fadds( Abc_Frame_t * pAbc, int argc, char ** argv ) { - extern Gia_Man_t * Gia_ManDupWithFaddBoxes( Gia_Man_t * p, int nFaddMin, int fVerbose ); + extern Gia_Man_t * Gia_ManDupWithNaturalBoxes( Gia_Man_t * p, int nFaddMin, int fVerbose ); + extern Gia_Man_t * Gia_ManDupWithArtificialBoxes( Gia_Man_t * p, int DelayC, int nPathMin, int nPathMax, int nPathLimit, int fUseFanout, int fVerbose ); Gia_Man_t * pTemp; - int c, nFaddMin = 3, fVerbose = 0; + int c, nFaddMin = 3, fUseArt = 0, fVerbose = 0; + int DelayC = 0, nPathMin = 3, nPathMax = 32, nPathLimit = 50, fUseFanout = 0; Extra_UtilGetoptReset(); - while ( ( c = Extra_UtilGetopt( argc, argv, "Nvh" ) ) != EOF ) + while ( ( c = Extra_UtilGetopt( argc, argv, "NBSLPafvh" ) ) != EOF ) { switch ( c ) { @@ -36600,6 +36602,56 @@ int Abc_CommandAbc9Fadds( Abc_Frame_t * pAbc, int argc, char ** argv ) if ( nFaddMin < 0 ) goto usage; break; + case 'B': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-B\" should be followed by an integer.\n" ); + goto usage; + } + DelayC = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( DelayC < 0 ) + goto usage; + break; + case 'S': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-S\" should be followed by an integer.\n" ); + goto usage; + } + nPathMin = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nPathMin < 0 ) + goto usage; + break; + case 'L': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-L\" should be followed by an integer.\n" ); + goto usage; + } + nPathMax = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nPathMax < 0 ) + goto usage; + break; + case 'P': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-P\" should be followed by an integer.\n" ); + goto usage; + } + nPathLimit = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nPathLimit < 0 ) + goto usage; + break; + case 'a': + fUseArt ^= 1; + break; + case 'f': + fUseFanout ^= 1; + break; case 'v': fVerbose ^= 1; break; @@ -36614,14 +36666,23 @@ int Abc_CommandAbc9Fadds( Abc_Frame_t * pAbc, int argc, char ** argv ) Abc_Print( -1, "Abc_CommandAbc9Fadds(): There is no AIG.\n" ); return 0; } - pTemp = Gia_ManDupWithFaddBoxes( pAbc->pGia, nFaddMin, fVerbose ); + if ( fUseArt ) + pTemp = Gia_ManDupWithArtificialBoxes( pAbc->pGia, DelayC, nPathMin, nPathMax, nPathLimit, fUseFanout, fVerbose ); + else + pTemp = Gia_ManDupWithNaturalBoxes( pAbc->pGia, nFaddMin, fVerbose ); Abc_FrameUpdateGia( pAbc, pTemp ); return 0; usage: - Abc_Print( -2, "usage: &fadds [-N num] [-vh]\n" ); + Abc_Print( -2, "usage: &fadds [-NBSLP num] [-afvh]\n" ); Abc_Print( -2, "\t detects full-adder chains and puts them into white boxes\n" ); - Abc_Print( -2, "\t-N num : the minimum length of full-adder chain to box [default = %d]\n", nFaddMin ); - Abc_Print( -2, "\t-v : toggles printing verbose information [default = %s]\n", fVerbose? "yes": "no" ); + Abc_Print( -2, "\t-N num : minimum length of a natural full-adder chain to detect [default = %d]\n", nFaddMin ); + Abc_Print( -2, "\t-a : toggles detecting artificial full-adder chains [default = %s]\n", fUseArt? "yes": "no" ); + Abc_Print( -2, "\t-B num : full-adder box delay (percentage of AND-gate delay) [default = %d]\n", DelayC ); + Abc_Print( -2, "\t-S num : minimum length of an artificial full-adder chain [default = %d]\n", nPathMin ); + Abc_Print( -2, "\t-L num : maximum length of an artificial full-adder chain [default = %d]\n", nPathMax ); + Abc_Print( -2, "\t-P num : maximum number of artificial full-adder chains to detect [default = %d]\n", nPathLimit ); + Abc_Print( -2, "\t-f : toggles using intermediate fanouts in artificial chains [default = %s]\n", fUseFanout? "yes": "no" ); + Abc_Print( -2, "\t-v : toggles printing verbose information [default = %s]\n", fVerbose? "yes": "no" ); Abc_Print( -2, "\t-h : print the command usage\n"); return 1; } diff --git a/src/bool/rpo/rpo.h b/src/bool/rpo/rpo.h index 8119bf27..38ad4068 100644 --- a/src/bool/rpo/rpo.h +++ b/src/bool/rpo/rpo.h @@ -55,5 +55,11 @@ ABC_NAMESPACE_HEADER_END #endif +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +
\ No newline at end of file |