diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2005-08-19 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2005-08-19 08:01:00 -0700 |
commit | 0e4de190ff4e25f5904a571b79a225363d5fc369 (patch) | |
tree | a89075fbb01848568534265967c59289c77713a0 /src/opt/rwr/rwrEva.c | |
parent | dffcc93b8e8779f443762c71098796b01ea7d409 (diff) | |
download | abc-0e4de190ff4e25f5904a571b79a225363d5fc369.tar.gz abc-0e4de190ff4e25f5904a571b79a225363d5fc369.tar.bz2 abc-0e4de190ff4e25f5904a571b79a225363d5fc369.zip |
Version abc50819
Diffstat (limited to 'src/opt/rwr/rwrEva.c')
-rw-r--r-- | src/opt/rwr/rwrEva.c | 216 |
1 files changed, 154 insertions, 62 deletions
diff --git a/src/opt/rwr/rwrEva.c b/src/opt/rwr/rwrEva.c index 50e773f8..ddc9d742 100644 --- a/src/opt/rwr/rwrEva.c +++ b/src/opt/rwr/rwrEva.c @@ -19,13 +19,13 @@ ***********************************************************************/ #include "rwr.h" +#include "ft.h" //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static void Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pNode, Rwr_Cut_t * pCut ); -static void Rwr_CutDecompose( Rwr_Man_t * p, Abc_Obj_t * pNode, Rwr_Cut_t * pCut, Vec_Int_t * vForm ); +static Vec_Int_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut, int NodeMax, int LevelMax ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// @@ -51,43 +51,34 @@ static void Rwr_CutDecompose( Rwr_Man_t * p, Abc_Obj_t * pNode, Rwr_Cut_t * pCut ***********************************************************************/ int Rwr_NodeRewrite( Rwr_Man_t * p, Abc_Obj_t * pNode ) { - Vec_Ptr_t Vector = {0,0,0}, * vFanins = &Vector; - Rwr_Cut_t * pCut, * pCutBest; - int BestGain = -1; - int i, Required = Vec_IntEntry( p->vReqTimes, pNode->Id ); - - // compute the cuts of the node + Vec_Int_t * vForm; + Rwr_Cut_t * pCut; + int Required, nNodesSaved; + int i, BestGain = -1; + // compute the cuts for this node Rwr_NodeComputeCuts( p, pNode ); - + // get the required times + Required = Vec_IntEntry( p->vReqTimes, pNode->Id ); + // label MFFC with current ID + nNodesSaved = Abc_NodeMffcLabel( pNode ); // go through the cuts for ( pCut = (Rwr_Cut_t *)pNode->pCopy, pCut = pCut->pNext; pCut; pCut = pCut->pNext ) { - // collect the TFO - vFanins->nSize = pCut->nLeaves; - vFanins->pArray = pCut->ppLeaves; - Abc_NodeCollectTfoCands( pNode->pNtk, pNode, vFanins, Required, p->vLevels, p->vTfo ); // evaluate the cut - Rwr_CutEvaluate( p, pNode, pCut ); - // check if the cut is the best - if ( pCut->fTime && pCut->fGain ) + vForm = Rwr_CutEvaluate( p, pNode, pCut, nNodesSaved, Required ); + // check if the cut is better than the currently best one + if ( vForm != NULL && BestGain < (int)pCut->Volume ) { - pCutBest = pCut; - BestGain = pCut->Volume; + assert( pCut->Volume >= 0 ); + BestGain = pCut->Volume; + // save this form + p->vForm = vForm; + // collect fanins + Vec_PtrClear( p->vFanins ); + for ( i = 0; i < (int)pCut->nLeaves; i++ ) + Vec_PtrPush( p->vFanins, pCut->ppLeaves[i] ); } } - if ( BestGain == -1 ) - return -1; - // we found a good cut - - // prepare the fanins - Vec_PtrClear( p->vFanins ); - for ( i = 0; i < (int)pCutBest->nLeaves; i++ ) - Vec_PtrPush( p->vFanins, pCutBest->ppLeaves[i] ); - // collect the TFO again - Abc_NodeCollectTfoCands( pNode->pNtk, pNode, p->vFanins, Required, p->vLevels, p->vTfo ); - // perform the decomposition - Rwr_CutDecompose( p, pNode, pCutBest, p->vForm ); - // the best fanins are in p->vFanins, the result of decomposition is in p->vForm return BestGain; } @@ -102,46 +93,113 @@ int Rwr_NodeRewrite( Rwr_Man_t * p, Abc_Obj_t * pNode ) SeeAlso [] ***********************************************************************/ -void Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut ) +Vec_Int_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut, int NodeMax, int LevelMax ) { - Abc_Obj_t * pNode, * pFanin0, * pFanin1; - Rwr_Node_t * pNodeFor; - int i; - // mark forest PIs corresponding to cut leaves - Vec_PtrClear( p->vTfoFor ); - for ( i = 0; i < (int)pCut->nLeaves; i++ ) + Vec_Ptr_t Vector = {0,0,0}, * vFanins = &Vector; + Vec_Ptr_t * vSubgraphs; + Vec_Int_t * vFormBest; + Rwr_Node_t * pNode; + int GainCur, GainBest = -1, i; + // find the matching class of subgraphs + vSubgraphs = Vec_VecEntry( p->vClasses, p->pMap[pCut->uTruth] ); + // determine the best subgraph + Vec_PtrForEachEntry( vSubgraphs, pNode, i ) { - pNodeFor = p->vForest->pArray[i]; - Vec_PtrPush( p->vTfoFor, pNodeFor ); - pCut->ppLeaves[i]->pData = pNodeFor; - pNodeFor->fMark = 1; + // create the fanin array + vFanins->nSize = pCut->nLeaves; + vFanins->pArray = pCut->ppLeaves; + // detect how many unlabeled nodes will be reused + GainCur = Abc_NodeStrashDecCount( pRoot->pNtk->pManFunc, vFanins, (Vec_Int_t *)pNode->pNext, + p->vLevNums, NodeMax, LevelMax ); + if ( GainBest < GainCur ) + { + GainBest = GainCur; + vFormBest = (Vec_Int_t *)pNode->pNext; + } } - // detect forest nodes corresponding to TFO - Vec_PtrForEachEntry( p->vTfo, pNode, i ) - { - pFanin0 = Abc_ObjFanin0(pNode); - if ( pFanin0->pData == NULL ) - continue; - pFanin1 = Abc_ObjFanin1(pNode); - if ( pFanin1->pData == NULL ) - continue; + if ( GainBest == -1 ) + return NULL; + pCut->Volume = GainBest; + return vFormBest; +} - } - // find the best implementation of the root +/**Function************************************************************* + + Synopsis [Adds one node.] - // assign costs + Description [] + + SideEffects [] + + SeeAlso [] - // clean the nodes - for ( i = 0; i < (int)pCut->nLeaves; i++ ) - pCut->ppLeaves[i]->pData = NULL; - Vec_PtrForEachEntry( p->vTfo, pNode, i ) - pNode->pData = NULL; +***********************************************************************/ +int Rwr_TravCollect_rec( Rwr_Man_t * p, Rwr_Node_t * pNode, Vec_Int_t * vForm ) +{ + Ft_Node_t Node, NodeA, NodeB; + int Node0, Node1; + // elementary variable + if ( pNode->fUsed ) + return ((pNode->Id - 1) << 1); + // previously visited node + if ( pNode->TravId == p->nTravIds ) + return pNode->Volume; + pNode->TravId = p->nTravIds; + // solve for children + Node0 = Rwr_TravCollect_rec( p, Rwr_Regular(pNode->p0), vForm ); + Node1 = Rwr_TravCollect_rec( p, Rwr_Regular(pNode->p1), vForm ); + // create the decomposition node(s) + if ( pNode->fExor ) + { + assert( !Rwr_IsComplement(pNode->p0) ); + assert( !Rwr_IsComplement(pNode->p1) ); + NodeA.fIntern = 1; + NodeA.fConst = 0; + NodeA.fCompl = 0; + NodeA.fCompl0 = !(Node0 & 1); + NodeA.fCompl1 = (Node1 & 1); + NodeA.iFanin0 = (Node0 >> 1); + NodeA.iFanin1 = (Node1 >> 1); + Vec_IntPush( vForm, Ft_Node2Int(NodeA) ); + + NodeB.fIntern = 1; + NodeB.fConst = 0; + NodeB.fCompl = 0; + NodeB.fCompl0 = (Node0 & 1); + NodeB.fCompl1 = !(Node1 & 1); + NodeB.iFanin0 = (Node0 >> 1); + NodeB.iFanin1 = (Node1 >> 1); + Vec_IntPush( vForm, Ft_Node2Int(NodeB) ); + + Node.fIntern = 1; + Node.fConst = 0; + Node.fCompl = 0; + Node.fCompl0 = 1; + Node.fCompl1 = 1; + Node.iFanin0 = vForm->nSize - 2; + Node.iFanin1 = vForm->nSize - 1; + Vec_IntPush( vForm, Ft_Node2Int(Node) ); + } + else + { + Node.fIntern = 1; + Node.fConst = 0; + Node.fCompl = 0; + Node.fCompl0 = Rwr_IsComplement(pNode->p0) ^ (Node0 & 1); + Node.fCompl1 = Rwr_IsComplement(pNode->p1) ^ (Node1 & 1); + Node.iFanin0 = (Node0 >> 1); + Node.iFanin1 = (Node1 >> 1); + Vec_IntPush( vForm, Ft_Node2Int(Node) ); + } + // save the number of this node + pNode->Volume = ((vForm->nSize - 1) << 1) | pNode->fExor; + return pNode->Volume; } /**Function************************************************************* - Synopsis [Decomposes the cut.] + Synopsis [Preprocesses subgraphs rooted at this node.] Description [] @@ -150,11 +208,45 @@ void Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -void Rwr_CutDecompose( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut, Vec_Int_t * vForm ) +void Rwr_NodePreprocess( Rwr_Man_t * p, Rwr_Node_t * pNode ) { - + Vec_Int_t * vForm; + int i, Root; + vForm = Vec_IntAlloc( 10 ); + for ( i = 0; i < 5; i++ ) + Vec_IntPush( vForm, 0 ); + // collect the nodes + Rwr_ManIncTravId( p ); + Root = Rwr_TravCollect_rec( p, pNode, vForm ); + if ( Root & 1 ) + Ft_FactorComplement( vForm ); + pNode->pNext = (Rwr_Node_t *)vForm; } +/**Function************************************************************* + + Synopsis [Preprocesses computed library of subgraphs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_ManPreprocess( Rwr_Man_t * p ) +{ + Rwr_Node_t * pNode; + int i, k; + // put the nodes into the structure + p->vClasses = Vec_VecAlloc( 222 ); + for ( i = 0; i < p->nFuncs; i++ ) + for ( pNode = p->pTable[i]; pNode; pNode = pNode->pNext ) + Vec_VecPush( p->vClasses, p->pMap[pNode->uTruth], pNode ); + // compute decomposition forms for each node + Vec_VecForEachEntry( p->vClasses, pNode, i, k ) + Rwr_NodePreprocess( p, pNode ); +} //////////////////////////////////////////////////////////////////////// /// END OF FILE /// |