summaryrefslogtreecommitdiffstats
path: root/src/opt/dar/darCore.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/opt/dar/darCore.c')
-rw-r--r--src/opt/dar/darCore.c344
1 files changed, 344 insertions, 0 deletions
diff --git a/src/opt/dar/darCore.c b/src/opt/dar/darCore.c
new file mode 100644
index 00000000..6ca3082d
--- /dev/null
+++ b/src/opt/dar/darCore.c
@@ -0,0 +1,344 @@
+/**CFile****************************************************************
+
+ FileName [darCore.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [DAG-aware AIG rewriting.]
+
+ Synopsis [Core of the rewriting package.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - April 28, 2007.]
+
+ Revision [$Id: darCore.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "darInt.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+// iterator over the nodes in the topological order
+#define Aig_ManForEachNodeInOrder( p, pObj ) \
+ for ( assert(p->pOrderData), p->iPrev = 0, p->iNext = p->pOrderData[1]; \
+ p->iNext && (((pObj) = Aig_ManObj(p, p->iNext)), 1); \
+ p->iNext = p->pOrderData[2*p->iPrev+1] )
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Returns the structure with default assignment of parameters.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Dar_ManDefaultRwrParams( Dar_RwrPar_t * pPars )
+{
+ memset( pPars, 0, sizeof(Dar_RwrPar_t) );
+ pPars->nCutsMax = 8; // 8
+ pPars->nSubgMax = 5; // 5 is a "magic number"
+ pPars->fFanout = 1;
+ pPars->fUpdateLevel = 0;
+ pPars->fUseZeros = 0;
+ pPars->fPower = 0;
+ pPars->fRecycle = 1;
+ pPars->fVerbose = 0;
+ pPars->fVeryVerbose = 0;
+}
+
+#define MAX_VAL 10
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Dar_ManRewrite( Aig_Man_t * pAig, Dar_RwrPar_t * pPars )
+{
+ extern Vec_Int_t * Saig_ManComputeSwitchProbs( Aig_Man_t * p, int nFrames, int nPref, int fProbOne );
+ Dar_Man_t * p;
+// Bar_Progress_t * pProgress;
+ Dar_Cut_t * pCut;
+ Aig_Obj_t * pObj, * pObjNew;
+ int i, k, nNodesOld, nNodeBefore, nNodeAfter, Required;
+ int clk = 0, clkStart, Counter = 0;
+ int nMffcSize, nMffcGains[MAX_VAL+1][MAX_VAL+1] = {{0}};
+ // prepare the library
+ Dar_LibPrepare( pPars->nSubgMax );
+ // create rewriting manager
+ p = Dar_ManStart( pAig, pPars );
+ if ( pPars->fPower )
+ pAig->vProbs = Saig_ManComputeSwitchProbs( pAig, 48, 16, 1 );
+ // remove dangling nodes
+ Aig_ManCleanup( pAig );
+ // if updating levels is requested, start fanout and timing
+ if ( p->pPars->fFanout )
+ Aig_ManFanoutStart( pAig );
+ if ( p->pPars->fUpdateLevel )
+ Aig_ManStartReverseLevels( pAig, 0 );
+ // set elementary cuts for the PIs
+// Dar_ManCutsStart( p );
+ // resynthesize each node once
+ clkStart = clock();
+ p->nNodesInit = Aig_ManNodeNum(pAig);
+ nNodesOld = Vec_PtrSize( pAig->vObjs );
+
+// pProgress = Bar_ProgressStart( stdout, nNodesOld );
+ Aig_ManForEachObj( pAig, pObj, i )
+// pProgress = Bar_ProgressStart( stdout, 100 );
+// Aig_ManOrderStart( pAig );
+// Aig_ManForEachNodeInOrder( pAig, pObj )
+ {
+// Bar_ProgressUpdate( pProgress, 100*pAig->nAndPrev/pAig->nAndTotal, NULL );
+// Bar_ProgressUpdate( pProgress, i, NULL );
+ if ( !Aig_ObjIsNode(pObj) )
+ continue;
+ if ( i > nNodesOld )
+// if ( p->pPars->fUseZeros && i > nNodesOld )
+ break;
+ if ( pPars->fRecycle && ++Counter % 50000 == 0 && Aig_DagSize(pObj) < Vec_PtrSize(p->vCutNodes)/100 )
+ {
+// printf( "Counter = %7d. Node = %7d. Dag = %5d. Vec = %5d.\n",
+// Counter, i, Aig_DagSize(pObj), Vec_PtrSize(p->vCutNodes) );
+// fflush( stdout );
+ Dar_ManCutsRestart( p, pObj );
+ }
+
+ // consider freeing the cuts
+// if ( (i & 0xFFF) == 0 && Aig_MmFixedReadMemUsage(p->pMemCuts)/(1<<20) > 100 )
+// Dar_ManCutsStart( p );
+
+ // compute cuts for the node
+ p->nNodesTried++;
+clk = clock();
+ Dar_ObjSetCuts( pObj, NULL );
+ Dar_ObjComputeCuts_rec( p, pObj );
+p->timeCuts += clock() - clk;
+
+ // check if there is a trivial cut
+ Dar_ObjForEachCut( pObj, pCut, k )
+ if ( pCut->nLeaves == 0 || (pCut->nLeaves == 1 && pCut->pLeaves[0] != pObj->Id && Aig_ManObj(p->pAig, pCut->pLeaves[0])) )
+ break;
+ if ( k < (int)pObj->nCuts )
+ {
+ assert( pCut->nLeaves < 2 );
+ if ( pCut->nLeaves == 0 ) // replace by constant
+ {
+ assert( pCut->uTruth == 0 || pCut->uTruth == 0xFFFF );
+ pObjNew = Aig_NotCond( Aig_ManConst1(p->pAig), pCut->uTruth==0 );
+ }
+ else
+ {
+ assert( pCut->uTruth == 0xAAAA || pCut->uTruth == 0x5555 );
+ pObjNew = Aig_NotCond( Aig_ManObj(p->pAig, pCut->pLeaves[0]), pCut->uTruth==0x5555 );
+ }
+ // remove the old cuts
+ Dar_ObjSetCuts( pObj, NULL );
+ // replace the node
+ Aig_ObjReplace( pAig, pObj, pObjNew, p->pPars->fUpdateLevel );
+ continue;
+ }
+
+ // evaluate the cuts
+ p->GainBest = -1;
+ nMffcSize = -1;
+ Required = pAig->vLevelR? Aig_ObjRequiredLevel(pAig, pObj) : ABC_INFINITY;
+ Dar_ObjForEachCut( pObj, pCut, k )
+ {
+ int nLeavesOld = pCut->nLeaves;
+ if ( pCut->nLeaves == 3 )
+ pCut->pLeaves[pCut->nLeaves++] = 0;
+ Dar_LibEval( p, pObj, pCut, Required, &nMffcSize );
+ pCut->nLeaves = nLeavesOld;
+ }
+ // check the best gain
+ if ( !(p->GainBest > 0 || (p->GainBest == 0 && p->pPars->fUseZeros)) )
+ {
+// Aig_ObjOrderAdvance( pAig );
+ continue;
+ }
+// nMffcGains[p->GainBest < MAX_VAL ? p->GainBest : MAX_VAL][nMffcSize < MAX_VAL ? nMffcSize : MAX_VAL]++;
+ // remove the old cuts
+ Dar_ObjSetCuts( pObj, NULL );
+ // if we end up here, a rewriting step is accepted
+ nNodeBefore = Aig_ManNodeNum( pAig );
+ pObjNew = Dar_LibBuildBest( p ); // pObjNew can be complemented!
+ pObjNew = Aig_NotCond( pObjNew, Aig_ObjPhaseReal(pObjNew) ^ pObj->fPhase );
+ assert( (int)Aig_Regular(pObjNew)->Level <= Required );
+ // replace the node
+ Aig_ObjReplace( pAig, pObj, pObjNew, p->pPars->fUpdateLevel );
+ // compare the gains
+ nNodeAfter = Aig_ManNodeNum( pAig );
+ assert( p->GainBest <= nNodeBefore - nNodeAfter );
+ // count gains of this class
+ p->ClassGains[p->ClassBest] += nNodeBefore - nNodeAfter;
+ }
+// Aig_ManOrderStop( pAig );
+/*
+ printf( "Distribution of gain (row) by MFFC size (column) %s 0-costs:\n", p->pPars->fUseZeros? "with":"without" );
+ for ( k = 0; k <= MAX_VAL; k++ )
+ printf( "<%4d> ", k );
+ printf( "\n" );
+ for ( i = 0; i <= MAX_VAL; i++ )
+ {
+ for ( k = 0; k <= MAX_VAL; k++ )
+ printf( "%6d ", nMffcGains[i][k] );
+ printf( "\n" );
+ }
+*/
+
+p->timeTotal = clock() - clkStart;
+p->timeOther = p->timeTotal - p->timeCuts - p->timeEval;
+
+// Bar_ProgressStop( pProgress );
+ Dar_ManCutsFree( p );
+ // put the nodes into the DFS order and reassign their IDs
+// Aig_NtkReassignIds( p );
+ // fix the levels
+// Aig_ManVerifyLevel( pAig );
+ if ( p->pPars->fFanout )
+ Aig_ManFanoutStop( pAig );
+ if ( p->pPars->fUpdateLevel )
+ {
+// Aig_ManVerifyReverseLevel( pAig );
+ Aig_ManStopReverseLevels( pAig );
+ }
+ if ( pAig->vProbs )
+ {
+ Vec_IntFree( pAig->vProbs );
+ pAig->vProbs = NULL;
+ }
+ // stop the rewriting manager
+ Dar_ManStop( p );
+ Aig_ManCheckPhase( pAig );
+ // check
+ if ( !Aig_ManCheck( pAig ) )
+ {
+ printf( "Aig_ManRewrite: The network check has failed.\n" );
+ return 0;
+ }
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the total number of cuts.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Dar_ManCutCount( Aig_Man_t * pAig, int * pnCutsK )
+{
+ Dar_Cut_t * pCut;
+ Aig_Obj_t * pObj;
+ int i, k, nCuts = 0, nCutsK = 0;
+ Aig_ManForEachNode( pAig, pObj, i )
+ Dar_ObjForEachCut( pObj, pCut, k )
+ {
+ nCuts++;
+ if ( pCut->nLeaves == 4 )
+ nCutsK++;
+ }
+ if ( pnCutsK )
+ *pnCutsK = nCutsK;
+ return nCuts;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Aig_MmFixed_t * Dar_ManComputeCuts( Aig_Man_t * pAig, int nCutsMax, int fVerbose )
+{
+ Dar_Man_t * p;
+ Dar_RwrPar_t Pars, * pPars = &Pars;
+ Aig_Obj_t * pObj;
+ Aig_MmFixed_t * pMemCuts;
+ int i, nNodes, clk = clock();
+ // remove dangling nodes
+ if ( (nNodes = Aig_ManCleanup( pAig )) )
+ {
+// printf( "Removing %d nodes.\n", nNodes );
+ }
+ // create default parameters
+ Dar_ManDefaultRwrParams( pPars );
+ pPars->nCutsMax = nCutsMax;
+ // create rewriting manager
+ p = Dar_ManStart( pAig, pPars );
+ // set elementary cuts for the PIs
+// Dar_ManCutsStart( p );
+ Aig_MmFixedRestart( p->pMemCuts );
+ Dar_ObjPrepareCuts( p, Aig_ManConst1(p->pAig) );
+ Aig_ManForEachPi( pAig, pObj, i )
+ Dar_ObjPrepareCuts( p, pObj );
+ // compute cuts for each nodes in the topological order
+ Aig_ManForEachNode( pAig, pObj, i )
+ Dar_ObjComputeCuts( p, pObj );
+ // print verbose stats
+ if ( fVerbose )
+ {
+// Aig_Obj_t * pObj;
+ int nCuts, nCutsK;//, i;
+ nCuts = Dar_ManCutCount( pAig, &nCutsK );
+ printf( "Nodes = %6d. Total cuts = %6d. 4-input cuts = %6d.\n",
+ Aig_ManObjNum(pAig), nCuts, nCutsK );
+ printf( "Cut size = %2d. Truth size = %2d. Total mem = %5.2f Mb ",
+ (int)sizeof(Dar_Cut_t), (int)4, 1.0*Aig_MmFixedReadMemUsage(p->pMemCuts)/(1<<20) );
+ ABC_PRT( "Runtime", clock() - clk );
+/*
+ Aig_ManForEachNode( pAig, pObj, i )
+ if ( i % 300 == 0 )
+ Dar_ObjCutPrint( pAig, pObj );
+*/
+ }
+ // free the cuts
+ pMemCuts = p->pMemCuts;
+ p->pMemCuts = NULL;
+// Dar_ManCutsFree( p );
+ // stop the rewriting manager
+ Dar_ManStop( p );
+ return pMemCuts;
+}
+
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-30 18:32:42 +0000