diff options
Diffstat (limited to 'src/base/abci')
-rw-r--r-- | src/base/abci/abc.c | 58 | ||||
-rw-r--r-- | src/base/abci/abcBalance.c | 161 | ||||
-rw-r--r-- | src/base/abci/abcCut.c | 164 | ||||
-rw-r--r-- | src/base/abci/abcRewrite.c | 2 |
4 files changed, 360 insertions, 25 deletions
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 38472a0c..4e2e14a2 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -932,20 +932,24 @@ int Abc_CommandShowAig( Abc_Frame_t * pAbc, int argc, char ** argv ) FILE * pOut, * pErr; Abc_Ntk_t * pNtk; int c; + int fMulti; extern void Abc_NtkShowAig( Abc_Ntk_t * pNtk ); + extern void Abc_NtkShowMulti( Abc_Ntk_t * pNtk ); pNtk = Abc_FrameReadNet(pAbc); pOut = Abc_FrameReadOut(pAbc); pErr = Abc_FrameReadErr(pAbc); // set defaults + fMulti = 0; util_getopt_reset(); - while ( ( c = util_getopt( argc, argv, "h" ) ) != EOF ) + while ( ( c = util_getopt( argc, argv, "mh" ) ) != EOF ) { switch ( c ) { - case 'h': - goto usage; + case 'm': + fMulti ^= 1; + break; default: goto usage; } @@ -962,7 +966,16 @@ int Abc_CommandShowAig( Abc_Frame_t * pAbc, int argc, char ** argv ) fprintf( pErr, "Visualizing AIG can only be done for AIGs (run \"strash\" or \"seq\").\n" ); return 1; } - Abc_NtkShowAig( pNtk ); + if ( fMulti && !Abc_NtkIsStrash(pNtk) ) + { + fprintf( pErr, "Visualizing multi-input ANDs cannot be done for sequential network (run \"unseq\").\n" ); + return 1; + } + + if ( !fMulti ) + Abc_NtkShowAig( pNtk ); + else + Abc_NtkShowMulti( pNtk ); return 0; usage: @@ -972,6 +985,7 @@ usage: fprintf( pErr, " \"dot.exe\" and \"gsview32.exe\" should be set in the paths\n" ); fprintf( pErr, " (\"gsview32.exe\" may be in \"C:\\Program Files\\Ghostgum\\gsview\\\")\n" ); #endif + fprintf( pErr, "\t-m : toggles visualization of multi-input ANDs [default = %s].\n", fMulti? "yes": "no" ); fprintf( pErr, "\t-h : print the command usage\n"); return 1; } @@ -1300,8 +1314,8 @@ usage: fprintf( pErr, "\t-F num : the maximum fanin size after renoding [default = %d]\n", nFaninMax ); fprintf( pErr, "\t-T num : the threshold for AIG node duplication [default = %d]\n", nThresh ); fprintf( pErr, "\t (an AIG node is the root of a new node after renoding\n" ); - fprintf( pErr, "\t if doing so prevents duplication of more than %d AIG nodes,\n", nThresh ); - fprintf( pErr, "\t that is, if [(numFanouts(Node)-1) * size(MFFC(Node))] > %d)\n", nThresh ); + fprintf( pErr, "\t if this leads to duplication of no more than %d AIG nodes,\n", nThresh ); + fprintf( pErr, "\t that is, if [(numFanouts(Node)-1) * size(MFFC(Node))] <= %d)\n", nThresh ); fprintf( pErr, "\t-m : creates multi-input AND graph [default = %s]\n", fMulti? "yes": "no" ); fprintf( pErr, "\t-s : creates a simple AIG (no renoding) [default = %s]\n", fSimple? "yes": "no" ); fprintf( pErr, "\t-c : performs renoding to derive the CNF [default = %s]\n", fCnf? "yes": "no" ); @@ -2733,13 +2747,14 @@ int Abc_CommandCut( Abc_Frame_t * pAbc, int argc, char ** argv ) // set defaults memset( pParams, 0, sizeof(Cut_Params_t) ); pParams->nVarsMax = 5; // the max cut size ("k" of the k-feasible cuts) - pParams->nKeepMax = 250; // the max number of cuts kept at a node + pParams->nKeepMax = 1000; // the max number of cuts kept at a node pParams->fTruth = 0; // compute truth tables pParams->fFilter = 1; // filter dominated cuts pParams->fDrop = 0; // drop cuts on the fly + pParams->fMulti = 0; // use multi-input AND-gates pParams->fVerbose = 0; // the verbosiness flag util_getopt_reset(); - while ( ( c = util_getopt( argc, argv, "KMtfdvh" ) ) != EOF ) + while ( ( c = util_getopt( argc, argv, "KMtfdmvh" ) ) != EOF ) { switch ( c ) { @@ -2774,6 +2789,9 @@ int Abc_CommandCut( Abc_Frame_t * pAbc, int argc, char ** argv ) case 'd': pParams->fDrop ^= 1; break; + case 'm': + pParams->fMulti ^= 1; + break; case 'v': pParams->fVerbose ^= 1; break; @@ -2800,13 +2818,14 @@ int Abc_CommandCut( Abc_Frame_t * pAbc, int argc, char ** argv ) return 0; usage: - fprintf( pErr, "usage: cut [-K num] [-M num] [-tfdvh]\n" ); + fprintf( pErr, "usage: cut [-K num] [-M num] [-tfdmvh]\n" ); fprintf( pErr, "\t computes k-feasible cuts for the AIG\n" ); fprintf( pErr, "\t-K num : max number of leaves (4 <= num <= 6) [default = %d]\n", pParams->nVarsMax ); fprintf( pErr, "\t-M num : max number of cuts stored at a node [default = %d]\n", pParams->nKeepMax ); fprintf( pErr, "\t-t : toggle truth table computation [default = %s]\n", pParams->fTruth? "yes": "no" ); fprintf( pErr, "\t-f : toggle filtering of duplicated/dominated [default = %s]\n", pParams->fFilter? "yes": "no" ); fprintf( pErr, "\t-d : toggle dropping when fanouts are done [default = %s]\n", pParams->fDrop? "yes": "no" ); + fprintf( pErr, "\t-m : toggle using multi-input AND-gates [default = %s]\n", pParams->fMulti? "yes": "no" ); fprintf( pErr, "\t-v : toggle printing verbose information [default = %s]\n", pParams->fVerbose? "yes": "no" ); fprintf( pErr, "\t-h : print the command usage\n"); return 1; @@ -2839,9 +2858,9 @@ int Abc_CommandScut( Abc_Frame_t * pAbc, int argc, char ** argv ) // set defaults memset( pParams, 0, sizeof(Cut_Params_t) ); pParams->nVarsMax = 5; // the max cut size ("k" of the k-feasible cuts) - pParams->nKeepMax = 250; // the max number of cuts kept at a node + pParams->nKeepMax = 1000; // the max number of cuts kept at a node pParams->fTruth = 0; // compute truth tables - pParams->fFilter = 0; // filter dominated cuts + pParams->fFilter = 1; // filter dominated cuts pParams->fSeq = 1; // compute sequential cuts pParams->fVerbose = 0; // the verbosiness flag util_getopt_reset(); @@ -4347,8 +4366,7 @@ int Abc_CommandRetime( Abc_Frame_t * pAbc, int argc, char ** argv ) int fForward; int fBackward; int fInitial; - - extern Abc_Ntk_t * Abc_NtkSuperChoice( Abc_Ntk_t * pNtk ); + int fVerbose; pNtk = Abc_FrameReadNet(pAbc); pOut = Abc_FrameReadOut(pAbc); @@ -4358,8 +4376,9 @@ int Abc_CommandRetime( Abc_Frame_t * pAbc, int argc, char ** argv ) fForward = 0; fBackward = 0; fInitial = 0; + fVerbose = 0; util_getopt_reset(); - while ( ( c = util_getopt( argc, argv, "fbih" ) ) != EOF ) + while ( ( c = util_getopt( argc, argv, "fbivh" ) ) != EOF ) { switch ( c ) { @@ -4372,6 +4391,9 @@ int Abc_CommandRetime( Abc_Frame_t * pAbc, int argc, char ** argv ) case 'i': fInitial ^= 1; break; + case 'v': + fVerbose ^= 1; + break; case 'h': goto usage; default: @@ -4393,13 +4415,13 @@ int Abc_CommandRetime( Abc_Frame_t * pAbc, int argc, char ** argv ) // get the new network if ( fForward ) - Abc_NtkSeqRetimeForward( pNtk ); + Abc_NtkSeqRetimeForward( pNtk, fVerbose ); else if ( fBackward ) - Abc_NtkSeqRetimeBackward( pNtk ); + Abc_NtkSeqRetimeBackward( pNtk, fVerbose ); else if ( fInitial ) - Abc_NtkSeqRetimeInitial( pNtk ); + Abc_NtkSeqRetimeInitial( pNtk, fVerbose ); else - Abc_NtkSeqRetimeDelay( pNtk ); + Abc_NtkSeqRetimeDelay( pNtk, fVerbose ); return 0; usage: diff --git a/src/base/abci/abcBalance.c b/src/base/abci/abcBalance.c index 035a2d1a..c612a1ce 100644 --- a/src/base/abci/abcBalance.c +++ b/src/base/abci/abcBalance.c @@ -242,6 +242,167 @@ int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, } + + +/**Function************************************************************* + + Synopsis [Collects the nodes in the implication supergate.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * Abc_NodeFindCone_rec( Abc_Obj_t * pNode ) +{ + Vec_Ptr_t * vNodes; + Abc_Obj_t * pNodeC, * pNodeT, * pNodeE; + int RetValue, i; + assert( !Abc_ObjIsComplement(pNode) ); + if ( Abc_ObjIsCi(pNode) ) + return NULL; + // start the new array + vNodes = Vec_PtrAlloc( 4 ); + // if the node is the MUX collect its fanins + if ( Abc_NodeIsMuxType(pNode) ) + { + pNodeC = Abc_NodeRecognizeMux( pNode, &pNodeT, &pNodeE ); + Vec_PtrPush( vNodes, Abc_ObjRegular(pNodeC) ); + Vec_PtrPushUnique( vNodes, Abc_ObjRegular(pNodeT) ); + Vec_PtrPushUnique( vNodes, Abc_ObjRegular(pNodeE) ); + } + else + { + // collect the nodes in the implication supergate + RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, 1 ); + assert( vNodes->nSize > 1 ); + // unmark the visited nodes + Vec_PtrForEachEntry( vNodes, pNode, i ) + Abc_ObjRegular(pNode)->fMarkB = 0; + // if we found the node and its complement in the same implication supergate, + // return empty set of nodes (meaning that we should use constant-0 node) + if ( RetValue == -1 ) + vNodes->nSize = 0; + } + // call for the fanin + Vec_PtrForEachEntry( vNodes, pNode, i ) + { + pNode = Abc_ObjRegular(pNode); + if ( pNode->pCopy ) + continue; + pNode->pCopy = (Abc_Obj_t *)Abc_NodeFindCone_rec( pNode ); + } + return vNodes; +} + +/**Function************************************************************* + + Synopsis [Attaches the implication supergates to internal nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkBalanceAttach( Abc_Ntk_t * pNtk ) +{ + Abc_Obj_t * pNode; + int i; + Abc_NtkCleanCopy( pNtk ); + Abc_NtkForEachCo( pNtk, pNode, i ) + { + pNode = Abc_ObjFanin0(pNode); + if ( pNode->pCopy ) + continue; + pNode->pCopy = (Abc_Obj_t *)Abc_NodeFindCone_rec( pNode ); + } +} + +/**Function************************************************************* + + Synopsis [Attaches the implication supergates to internal nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkBalanceDetach( Abc_Ntk_t * pNtk ) +{ + Abc_Obj_t * pNode; + int i; + Abc_NtkForEachNode( pNtk, pNode, i ) + if ( pNode->pCopy ) + { + Vec_PtrFree( (Vec_Ptr_t *)pNode->pCopy ); + pNode->pCopy = NULL; + } +} + +/**Function************************************************************* + + Synopsis [Compute levels of implication supergates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkBalanceLevel_rec( Abc_Obj_t * pNode ) +{ + Vec_Ptr_t * vSuper; + Abc_Obj_t * pFanin; + int i, LevelMax; + assert( !Abc_ObjIsComplement(pNode) ); + if ( pNode->Level > 0 ) + return pNode->Level; + if ( Abc_ObjIsCi(pNode) ) + return 0; + vSuper = (Vec_Ptr_t *)pNode->pCopy; + assert( vSuper != NULL ); + LevelMax = 0; + Vec_PtrForEachEntry( vSuper, pFanin, i ) + { + pFanin = Abc_ObjRegular(pFanin); + Abc_NtkBalanceLevel_rec(pFanin); + if ( LevelMax < (int)pFanin->Level ) + LevelMax = pFanin->Level; + } + pNode->Level = LevelMax + 1; + return pNode->Level; +} + + +/**Function************************************************************* + + Synopsis [Compute levels of implication supergates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkBalanceLevel( Abc_Ntk_t * pNtk ) +{ + Abc_Obj_t * pNode; + int i; + Abc_NtkForEachObj( pNtk, pNode, i ) + pNode->Level = 0; + Abc_NtkForEachCo( pNtk, pNode, i ) + Abc_NtkBalanceLevel_rec( Abc_ObjFanin0(pNode) ); +} + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/base/abci/abcCut.c b/src/base/abci/abcCut.c index 64dec4a4..7cc3d65b 100644 --- a/src/base/abci/abcCut.c +++ b/src/base/abci/abcCut.c @@ -25,6 +25,9 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +static void Abc_NtkPrintCuts( void * p, Abc_Ntk_t * pNtk, int fSeq ); +static void Abc_NtkPrintCuts_( void * p, Abc_Ntk_t * pNtk, int fSeq ); + //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// @@ -49,7 +52,12 @@ Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) int i; int clk = clock(); + extern void Abc_NtkBalanceAttach( Abc_Ntk_t * pNtk ); + extern void Abc_NtkBalanceDetach( Abc_Ntk_t * pNtk ); + assert( Abc_NtkIsStrash(pNtk) ); + if ( pParams->fMulti ) + Abc_NtkBalanceAttach(pNtk); // start the manager pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); @@ -76,7 +84,13 @@ Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) if ( Abc_NodeIsConst(pObj) ) continue; // compute the cuts to the internal node - Abc_NodeGetCuts( p, pObj ); + Abc_NodeGetCuts( p, pObj, pParams->fMulti ); + // consider dropping the fanins cuts + if ( pParams->fDrop ) + { + Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId0(pObj) ); + Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId1(pObj) ); + } // add cuts due to choices if ( Abc_NodeIsAigChoice(pObj) ) { @@ -88,7 +102,11 @@ Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) } Vec_PtrFree( vNodes ); Vec_IntFree( vChoices ); + if ( pParams->fMulti ) + Abc_NtkBalanceDetach(pNtk); PRT( "Total", clock() - clk ); +Abc_NtkPrintCuts_( p, pNtk, 0 ); +// Cut_ManPrintStatsToFile( p, pNtk->pSpec, clock() - clk ); return p; } @@ -105,7 +123,68 @@ PRT( "Total", clock() - clk ); ***********************************************************************/ Cut_Man_t * Abc_NtkSeqCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) { - return NULL; + Cut_Man_t * p; + Abc_Obj_t * pObj; + int i, nIters, fStatus; + int clk = clock(); + + assert( Abc_NtkIsSeq(pNtk) ); + assert( pParams->fSeq ); + + // start the manager + pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); + pParams->nCutSet = pNtk->vLats->nSize; + p = Cut_ManStart( pParams ); + + // set cuts for PIs + Abc_NtkForEachPi( pNtk, pObj, i ) + Cut_NodeSetTriv( p, pObj->Id ); + // label the cutset nodes and set their number in the array + // assign the elementary cuts to the cutset nodes + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + { + assert( pObj->fMarkC == 0 ); + pObj->fMarkC = 1; + pObj->pCopy = (Abc_Obj_t *)i; + Cut_NodeSetTriv( p, pObj->Id ); + } + + // process the nodes + for ( nIters = 0; nIters < 10; nIters++ ) + { +//printf( "ITERATION %d:\n", nIters ); + // compute the cuts for the internal nodes + Abc_AigForEachAnd( pNtk, pObj, i ) + Abc_NodeGetCutsSeq( p, pObj, nIters==0 ); +Abc_NtkPrintCuts( p, pNtk, 1 ); + // merge the new cuts with the old cuts + Abc_NtkForEachPi( pNtk, pObj, i ) + Cut_NodeNewMergeWithOld( p, pObj->Id ); + Abc_AigForEachAnd( pNtk, pObj, i ) + Cut_NodeNewMergeWithOld( p, pObj->Id ); + // for the cutset, merge temp with new + fStatus = 0; + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + fStatus |= Cut_NodeTempTransferToNew( p, pObj->Id, i ); + if ( fStatus == 0 ) + break; + } + + // if the status is not finished, transfer new to old for the cutset + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + Cut_NodeNewMergeWithOld( p, pObj->Id ); + + // transfer the old cuts to the new positions + Abc_NtkForEachObj( pNtk, pObj, i ) + Cut_NodeOldTransferToNew( p, pObj->Id ); + + // unlabel the cutset nodes + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + pObj->fMarkC = 0; +PRT( "Total", clock() - clk ); +printf( "Converged after %d iterations.\n", nIters ); +Abc_NtkPrintCuts( p, pNtk, 1 ); + return p; } /**Function************************************************************* @@ -126,7 +205,7 @@ void * Abc_NodeGetCutsRecursive( void * p, Abc_Obj_t * pObj ) return pList; Abc_NodeGetCutsRecursive( p, Abc_ObjFanin0(pObj) ); Abc_NodeGetCutsRecursive( p, Abc_ObjFanin1(pObj) ); - return Abc_NodeGetCuts( p, pObj ); + return Abc_NodeGetCuts( p, pObj, 0 ); } /**Function************************************************************* @@ -140,10 +219,35 @@ void * Abc_NodeGetCutsRecursive( void * p, Abc_Obj_t * pObj ) SeeAlso [] ***********************************************************************/ -void * Abc_NodeGetCuts( void * p, Abc_Obj_t * pObj ) +void * Abc_NodeGetCuts( void * p, Abc_Obj_t * pObj, int fMulti ) { + int fTriv = (!fMulti) || (pObj->pCopy != NULL); + assert( Abc_NtkIsStrash(pObj->pNtk) ); + assert( Abc_ObjFaninNum(pObj) == 2 ); return Cut_NodeComputeCuts( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj), - Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj) ); + Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj), 1, 1, fTriv ); +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NodeGetCutsSeq( void * p, Abc_Obj_t * pObj, int fTriv ) +{ + int CutSetNum; + assert( Abc_NtkIsSeq(pObj->pNtk) ); + assert( Abc_ObjFaninNum(pObj) == 2 ); +// fTriv = pObj->fMarkC ? 0 : fTriv; + CutSetNum = pObj->fMarkC ? (int)pObj->pCopy : -1; + Cut_NodeComputeCutsSeq( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj), + Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj), Abc_ObjFaninL0(pObj), Abc_ObjFaninL1(pObj), fTriv, CutSetNum ); } /**Function************************************************************* @@ -159,7 +263,7 @@ void * Abc_NodeGetCuts( void * p, Abc_Obj_t * pObj ) ***********************************************************************/ void * Abc_NodeReadCuts( void * p, Abc_Obj_t * pObj ) { - return Cut_NodeReadCuts( p, pObj->Id ); + return Cut_NodeReadCutsNew( p, pObj->Id ); } /**Function************************************************************* @@ -178,6 +282,54 @@ void Abc_NodeFreeCuts( void * p, Abc_Obj_t * pObj ) Cut_NodeFreeCuts( p, pObj->Id ); } +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkPrintCuts( void * p, Abc_Ntk_t * pNtk, int fSeq ) +{ + Cut_Man_t * pMan = p; + Cut_Cut_t * pList; + Abc_Obj_t * pObj; + int i; + printf( "Cuts of the network:\n" ); + Abc_NtkForEachObj( pNtk, pObj, i ) + { + pList = Abc_NodeReadCuts( p, pObj ); + printf( "Node %s:\n", Abc_ObjName(pObj) ); + Cut_CutPrintList( pList, fSeq ); + } +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkPrintCuts_( void * p, Abc_Ntk_t * pNtk, int fSeq ) +{ + Cut_Man_t * pMan = p; + Cut_Cut_t * pList; + Abc_Obj_t * pObj; + pObj = Abc_NtkObj( pNtk, 2 * Abc_NtkObjNum(pNtk) / 3 ); + pList = Abc_NodeReadCuts( p, pObj ); + printf( "Node %s:\n", Abc_ObjName(pObj) ); + Cut_CutPrintList( pList, fSeq ); +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/base/abci/abcRewrite.c b/src/base/abci/abcRewrite.c index b70d30e6..a14718c4 100644 --- a/src/base/abci/abcRewrite.c +++ b/src/base/abci/abcRewrite.c @@ -192,7 +192,7 @@ void Abc_NodePrintCuts( Abc_Obj_t * pNode ) { Extra_PrintBinary( stdout, (unsigned *)&pCut->uSign, 16 ); printf( " " ); - Cut_CutPrint( pCut ); + Cut_CutPrint( pCut, 0 ); printf( "\n" ); } } |