diff options
Diffstat (limited to 'src/base/abci/abcCut.c')
-rw-r--r-- | src/base/abci/abcCut.c | 494 |
1 files changed, 32 insertions, 462 deletions
diff --git a/src/base/abci/abcCut.c b/src/base/abci/abcCut.c index d399ce5f..f487bd1b 100644 --- a/src/base/abci/abcCut.c +++ b/src/base/abci/abcCut.c @@ -25,16 +25,8 @@ /// 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 ); - -extern int nTotal, nGood, nEqual; - -static Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk ); -static int Abc_NtkComputeArea( Abc_Ntk_t * pNtk, Cut_Man_t * p ); - //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// +/// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -50,30 +42,18 @@ static int Abc_NtkComputeArea( Abc_Ntk_t * pNtk, Cut_Man_t * p ); ***********************************************************************/ Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) { - ProgressBar * pProgress; Cut_Man_t * p; - Abc_Obj_t * pObj, * pNode; + Abc_Obj_t * pObj, * pDriver, * pNode; Vec_Ptr_t * vNodes; Vec_Int_t * vChoices; int i; int clk = clock(); - extern void Abc_NtkBalanceAttach( Abc_Ntk_t * pNtk ); - extern void Abc_NtkBalanceDetach( Abc_Ntk_t * pNtk ); - - nTotal = nGood = nEqual = 0; - assert( Abc_NtkIsStrash(pNtk) ); + // start the manager pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); p = Cut_ManStart( pParams ); - // compute node attributes if local or global cuts are requested - if ( pParams->fGlobal || pParams->fLocal ) - { - extern Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk ); - Cut_ManSetNodeAttrs( p, Abc_NtkGetNodeAttributes(pNtk) ); - } - // prepare for cut dropping if ( pParams->fDrop ) Cut_ManSetFanoutCounts( p, Abc_NtkFanoutCounts(pNtk) ); // set cuts for PIs @@ -81,9 +61,8 @@ Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) if ( Abc_ObjFanoutNum(pObj) > 0 ) Cut_NodeSetTriv( p, pObj->Id ); // compute cuts for internal nodes - vNodes = Abc_AigDfs( pNtk, 0, 1 ); // collects POs + vNodes = Abc_AigDfs( pNtk, 0, 1 ); vChoices = Vec_IntAlloc( 100 ); - pProgress = Extra_ProgressBarStart( stdout, Vec_PtrSize(vNodes) ); Vec_PtrForEachEntry( vNodes, pObj, i ) { // when we reached a CO, it is time to deallocate the cuts @@ -94,19 +73,12 @@ Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) continue; } // skip constant node, it has no cuts -// if ( Abc_NodeIsConst(pObj) ) -// continue; - Extra_ProgressBarUpdate( pProgress, i, NULL ); + if ( Abc_NodeIsConst(pObj) ) + continue; // compute the cuts to the internal node - Abc_NodeGetCuts( p, pObj, pParams->fDag, pParams->fTree ); - // consider dropping the fanins cuts - if ( pParams->fDrop ) - { - Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId0(pObj) ); - Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId1(pObj) ); - } + Abc_NodeGetCuts( p, pObj ); // add cuts due to choices - if ( Abc_AigNodeIsChoice(pObj) ) + if ( Abc_NodeIsAigChoice(pObj) ) { Vec_IntClear( vChoices ); for ( pNode = pObj; pNode; pNode = pNode->pData ) @@ -114,203 +86,31 @@ Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) Cut_NodeUnionCuts( p, vChoices ); } } - Extra_ProgressBarStop( pProgress ); - Vec_PtrFree( vNodes ); - Vec_IntFree( vChoices ); - Cut_ManPrintStats( p ); -PRT( "TOTAL ", clock() - clk ); - printf( "Area = %d.\n", Abc_NtkComputeArea( pNtk, p ) ); -//Abc_NtkPrintCuts( p, pNtk, 0 ); -// Cut_ManPrintStatsToFile( p, pNtk->pSpec, clock() - clk ); - - // temporary printout of stats - if ( nTotal ) - printf( "Total cuts = %d. Good cuts = %d. Ratio = %5.2f\n", nTotal, nGood, ((double)nGood)/nTotal ); - return p; -} - -/**Function************************************************************* - - Synopsis [Cut computation using the oracle.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NtkCutsOracle( Abc_Ntk_t * pNtk, Cut_Oracle_t * p ) -{ - Abc_Obj_t * pObj; - Vec_Ptr_t * vNodes; - int i, clk = clock(); - int fDrop = Cut_OracleReadDrop(p); - - assert( Abc_NtkIsStrash(pNtk) ); - - // prepare cut droppping - if ( fDrop ) - Cut_OracleSetFanoutCounts( p, Abc_NtkFanoutCounts(pNtk) ); - - // set cuts for PIs - Abc_NtkForEachCi( pNtk, pObj, i ) - if ( Abc_ObjFanoutNum(pObj) > 0 ) - Cut_OracleNodeSetTriv( p, pObj->Id ); - - // compute cuts for internal nodes - vNodes = Abc_AigDfs( pNtk, 0, 1 ); // collects POs - Vec_PtrForEachEntry( vNodes, pObj, i ) + if ( !pParams->fSeq ) { - // when we reached a CO, it is time to deallocate the cuts - if ( Abc_ObjIsCo(pObj) ) - { - if ( fDrop ) - Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId0(pObj) ); - continue; - } - // skip constant node, it has no cuts -// if ( Abc_NodeIsConst(pObj) ) -// continue; - // compute the cuts to the internal node - Cut_OracleComputeCuts( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj), - Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj) ); - // consider dropping the fanins cuts - if ( fDrop ) - { - Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId0(pObj) ); - Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId1(pObj) ); - } + Vec_PtrFree( vNodes ); + Vec_IntFree( vChoices ); +PRT( "Total", clock() - clk ); + return p; } - Vec_PtrFree( vNodes ); -//PRT( "Total", clock() - clk ); -//Abc_NtkPrintCuts_( p, pNtk, 0 ); -} - + assert( 0 ); -/**Function************************************************************* - - Synopsis [Computes the cuts for the network.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Cut_Man_t * Abc_NtkSeqCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) -{ -/* - Cut_Man_t * p; - Abc_Obj_t * pObj, * pNode; - int i, nIters, fStatus; - Vec_Int_t * vChoices; - int clk = clock(); - - assert( Abc_NtkIsSeq(pNtk) ); - assert( pParams->fSeq ); -// assert( Abc_NtkIsDfsOrdered(pNtk) ); - - // start the manager - pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); - pParams->nCutSet = Abc_NtkCutSetNodeNum( pNtk ); - p = Cut_ManStart( pParams ); - - // set cuts for the constant node and the PIs - pObj = Abc_AigConst1(pNtk); - if ( Abc_ObjFanoutNum(pObj) > 0 ) - Cut_NodeSetTriv( p, pObj->Id ); - Abc_NtkForEachPi( pNtk, pObj, i ) - { -//printf( "Setting trivial cut %d.\n", pObj->Id ); - 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 ); -//printf( "Setting trivial cut %d.\n", pObj->Id ); - } - - // process the nodes - vChoices = Vec_IntAlloc( 100 ); - for ( nIters = 0; nIters < 10; nIters++ ) + // compute sequential cuts + Abc_NtkIncrementTravId( pNtk ); + Abc_NtkForEachLatch( pNtk, pObj, i ) { -//printf( "ITERATION %d:\n", nIters ); - // compute the cuts for the internal nodes - Abc_AigForEachAnd( pNtk, pObj, i ) - { - Abc_NodeGetCutsSeq( p, pObj, nIters==0 ); - // add cuts due to choices - if ( Abc_AigNodeIsChoice(pObj) ) - { - Vec_IntClear( vChoices ); - for ( pNode = pObj; pNode; pNode = pNode->pData ) - Vec_IntPush( vChoices, pNode->Id ); - Cut_NodeUnionCutsSeq( p, vChoices, (pObj->fMarkC ? (int)pObj->pCopy : -1), nIters==0 ); - } - } - // 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, transfer temp cuts to new cuts - fStatus = 0; - Abc_SeqForEachCutsetNode( pNtk, pObj, i ) - fStatus |= Cut_NodeTempTransferToNew( p, pObj->Id, i ); - if ( fStatus == 0 ) - break; + pDriver = Abc_ObjFanin0(pObj); + if ( !Abc_ObjIsNode(pDriver) ) + continue; + if ( Abc_NodeIsTravIdCurrent(pDriver) ) + continue; + Abc_NodeSetTravIdCurrent(pDriver); + Cut_NodeSetComputedAsNew( p, pDriver->Id ); } - Vec_IntFree( vChoices ); + // compute as long as new cuts appear - // 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; -if ( pParams->fVerbose ) -{ - Cut_ManPrintStats( p ); -PRT( "TOTAL ", clock() - clk ); -printf( "Converged after %d iterations.\n", nIters ); -} -//Abc_NtkPrintCuts( p, pNtk, 1 ); return p; -*/ - return NULL; -} - -/**Function************************************************************* - - Synopsis [Computes area.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkComputeArea( Abc_Ntk_t * pNtk, Cut_Man_t * p ) -{ - Abc_Obj_t * pObj; - int Counter, i; - Counter = 0; - Abc_NtkForEachCo( pNtk, pObj, i ) - Counter += Cut_ManMappingArea_rec( p, Abc_ObjFaninId0(pObj) ); - return Counter; } /**Function************************************************************* @@ -324,14 +124,14 @@ int Abc_NtkComputeArea( Abc_Ntk_t * pNtk, Cut_Man_t * p ) SeeAlso [] ***********************************************************************/ -void * Abc_NodeGetCutsRecursive( void * p, Abc_Obj_t * pObj, int fDag, int fTree ) +void * Abc_NodeGetCutsRecursive( void * p, Abc_Obj_t * pObj ) { void * pList; if ( pList = Abc_NodeReadCuts( p, pObj ) ) return pList; - Abc_NodeGetCutsRecursive( p, Abc_ObjFanin0(pObj), fDag, fTree ); - Abc_NodeGetCutsRecursive( p, Abc_ObjFanin1(pObj), fDag, fTree ); - return Abc_NodeGetCuts( p, pObj, fDag, fTree ); + Abc_NodeGetCutsRecursive( p, Abc_ObjFanin0(pObj) ); + Abc_NodeGetCutsRecursive( p, Abc_ObjFanin1(pObj) ); + return Abc_NodeGetCuts( p, pObj ); } /**Function************************************************************* @@ -345,73 +145,10 @@ void * Abc_NodeGetCutsRecursive( void * p, Abc_Obj_t * pObj, int fDag, int fTree SeeAlso [] ***********************************************************************/ -void * Abc_NodeGetCuts( void * p, Abc_Obj_t * pObj, int fDag, int fTree ) +void * Abc_NodeGetCuts( void * p, Abc_Obj_t * pObj ) { - Abc_Obj_t * pFanin; - int fDagNode, fTriv, TreeCode = 0; -// assert( Abc_NtkIsStrash(pObj->pNtk) ); - assert( Abc_ObjFaninNum(pObj) == 2 ); - - - // check if the node is a DAG node - fDagNode = (Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj)); - // increment the counter of DAG nodes - if ( fDagNode ) Cut_ManIncrementDagNodes( p ); - // add the trivial cut if the node is a DAG node, or if we compute all cuts - fTriv = fDagNode || !fDag; - // check if fanins are DAG nodes - if ( fTree ) - { - pFanin = Abc_ObjFanin0(pObj); - TreeCode |= (Abc_ObjFanoutNum(pFanin) > 1 && !Abc_NodeIsMuxControlType(pFanin)); - pFanin = Abc_ObjFanin1(pObj); - TreeCode |= ((Abc_ObjFanoutNum(pFanin) > 1 && !Abc_NodeIsMuxControlType(pFanin)) << 1); - } - - - // changes due to the global/local cut computation - { - Cut_Params_t * pParams = Cut_ManReadParams(p); - if ( pParams->fLocal ) - { - Vec_Int_t * vNodeAttrs = Cut_ManReadNodeAttrs(p); - fDagNode = Vec_IntEntry( vNodeAttrs, pObj->Id ); - if ( fDagNode ) Cut_ManIncrementDagNodes( p ); -// fTriv = fDagNode || !pParams->fGlobal; - fTriv = !Vec_IntEntry( vNodeAttrs, pObj->Id ); - TreeCode = 0; - pFanin = Abc_ObjFanin0(pObj); - TreeCode |= Vec_IntEntry( vNodeAttrs, pFanin->Id ); - pFanin = Abc_ObjFanin1(pObj); - TreeCode |= (Vec_IntEntry( vNodeAttrs, pFanin->Id ) << 1); - } - } return Cut_NodeComputeCuts( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj), - Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj), fTriv, TreeCode ); -} - -/**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), Seq_ObjFaninL0(pObj), Seq_ObjFaninL1(pObj), fTriv, CutSetNum ); -*/ + Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj) ); } /**Function************************************************************* @@ -427,7 +164,7 @@ void Abc_NodeGetCutsSeq( void * p, Abc_Obj_t * pObj, int fTriv ) ***********************************************************************/ void * Abc_NodeReadCuts( void * p, Abc_Obj_t * pObj ) { - return Cut_NodeReadCutsNew( p, pObj->Id ); + return Cut_NodeReadCuts( p, pObj->Id ); } /**Function************************************************************* @@ -446,173 +183,6 @@ 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 ); -} - - - - -/**Function************************************************************* - - Synopsis [Assigns global attributes randomly.] - - Description [Old code.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk ) -{ - Vec_Int_t * vAttrs; -// Vec_Ptr_t * vNodes; - Abc_Obj_t * pObj;//, * pTemp; - int i;//, k; - int nNodesTotal = 0, nMffcsTotal = 0; - extern Vec_Ptr_t * Abc_NodeMffsInsideCollect( Abc_Obj_t * pNode ); - - vAttrs = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 ); -// Abc_NtkForEachCi( pNtk, pObj, i ) -// Vec_IntWriteEntry( vAttrs, pObj->Id, 1 ); - - Abc_NtkForEachObj( pNtk, pObj, i ) - { - if ( Abc_ObjIsNode(pObj) ) - nNodesTotal++; - if ( Abc_ObjIsCo(pObj) && Abc_ObjIsNode(Abc_ObjFanin0(pObj)) ) - nMffcsTotal += Abc_NodeMffcSize( Abc_ObjFanin0(pObj) ); -// if ( Abc_ObjIsNode(pObj) && (rand() % 4 == 0) ) -// if ( Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj) && (rand() % 3 == 0) ) - if ( Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj) ) - { - int nMffc = Abc_NodeMffcSize(pObj); - nMffcsTotal += Abc_NodeMffcSize(pObj); -// printf( "%d ", nMffc ); - - if ( nMffc > 2 || Abc_ObjFanoutNum(pObj) > 8 ) - Vec_IntWriteEntry( vAttrs, pObj->Id, 1 ); - } - } -/* - Abc_NtkForEachObj( pNtk, pObj, i ) - { - if ( Vec_IntEntry( vAttrs, pObj->Id ) ) - { - vNodes = Abc_NodeMffsInsideCollect( pObj ); - Vec_PtrForEachEntry( vNodes, pTemp, k ) - if ( pTemp != pObj ) - Vec_IntWriteEntry( vAttrs, pTemp->Id, 0 ); - Vec_PtrFree( vNodes ); - } - } -*/ - printf( "Total nodes = %d. Total MFFC nodes = %d.\n", nNodesTotal, nMffcsTotal ); - return vAttrs; -} - -/**Function************************************************************* - - Synopsis [Assigns global attributes randomly.] - - Description [Old code.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkSubDagSize_rec( Abc_Obj_t * pObj, Vec_Int_t * vAttrs ) -{ - if ( Abc_NodeIsTravIdCurrent(pObj) ) - return 0; - Abc_NodeSetTravIdCurrent(pObj); - if ( Vec_IntEntry( vAttrs, pObj->Id ) ) - return 0; - if ( Abc_ObjIsCi(pObj) ) - return 1; - assert( Abc_ObjFaninNum(pObj) == 2 ); - return 1 + Abc_NtkSubDagSize_rec(Abc_ObjFanin0(pObj), vAttrs) + - Abc_NtkSubDagSize_rec(Abc_ObjFanin1(pObj), vAttrs); -} - -/**Function************************************************************* - - Synopsis [Assigns global attributes randomly.] - - Description [Old code.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Abc_NtkGetNodeAttributes2( Abc_Ntk_t * pNtk ) -{ - Vec_Int_t * vAttrs; - Abc_Obj_t * pObj; - int i, nSize; - assert( Abc_NtkIsDfsOrdered(pNtk) ); - vAttrs = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 ); - Abc_NtkForEachObj( pNtk, pObj, i ) - { - // skip no-nodes and nodes without fanouts - if ( pObj->Id == 0 || !(Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj)) ) - continue; - // the node has more than one fanout - count its sub-DAG size - Abc_NtkIncrementTravId( pNtk ); - nSize = Abc_NtkSubDagSize_rec( pObj, vAttrs ); - if ( nSize > 15 ) - Vec_IntWriteEntry( vAttrs, pObj->Id, 1 ); - } - return vAttrs; -} - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// |