/**CFile**************************************************************** FileName [abcRestruct.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [Network and node package.] Synopsis [] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - June 20, 2005.] Revision [$Id: abcRestruct.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] ***********************************************************************/ #include "base/abc/abc.h" #include "bool/dec/dec.h" #include "opt/cut/cut.h" #include "misc/extra/extraBdd.h" #include "bdd/dsd/dsd.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// #define RST_RANDOM_UNSIGNED ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand())) typedef struct Abc_ManRst_t_ Abc_ManRst_t; struct Abc_ManRst_t_ { // the network Abc_Ntk_t * pNtk; // the network for restructuring // user specified parameters int nCutMax; // the limit on the size of the supernode int fUpdateLevel; // turns on watching the number of levels int fUseZeros; // turns on zero-cost replacements int fVerbose; // the verbosity flag // internal data structures DdManager * dd; // the BDD manager Dsd_Manager_t * pManDsd; // the DSD manager Vec_Ptr_t * vVisited; // temporary Vec_Ptr_t * vLeaves; // temporary Vec_Ptr_t * vDecs; // temporary Vec_Ptr_t * vTemp; // temporary Vec_Int_t * vSims; // temporary Vec_Int_t * vRands; // temporary Vec_Int_t * vOnes; // temporary Vec_Int_t * vBinate; // temporary Vec_Int_t * vTwos; // temporary // node statistics int nLastGain; int nCutsConsidered; int nCutsExplored; int nNodesConsidered; int nNodesRestructured; int nNodesGained; // runtime statistics int timeCut; int timeBdd; int timeDsd; int timeEval; int timeRes; int timeNtk; int timeTotal; }; static Dec_Graph_t * Abc_NodeResubstitute( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList ); static Dec_Graph_t * Abc_NodeRestructure( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList ); static Dec_Graph_t * Abc_NodeRestructureCut( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCut ); static Dec_Graph_t * Abc_NodeEvaluateDsd( Abc_ManRst_t * pManRst, Dsd_Node_t * pNodeDsd, Abc_Obj_t * pRoot, int Required, int nNodesSaved, int * pnNodesAdded ); static Cut_Man_t * Abc_NtkStartCutManForRestruct( Abc_Ntk_t * pNtk, int nCutMax, int fDag ); static Abc_ManRst_t * Abc_NtkManRstStart( int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose ); static void Abc_NtkManRstStop( Abc_ManRst_t * p ); static void Abc_NtkManRstPrintStats( Abc_ManRst_t * p ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Implements AIG restructuring.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NtkRestructure( Abc_Ntk_t * pNtk, int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose ) { extern void Dec_GraphUpdateNetwork( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int fUpdateLevel, int nGain ); ProgressBar * pProgress; Abc_ManRst_t * pManRst; Cut_Man_t * pManCut; Cut_Cut_t * pCutList; Dec_Graph_t * pGraph; Abc_Obj_t * pNode; abctime clk, clkStart = Abc_Clock(); int fMulti = 1; int fResub = 0; int i, nNodes; assert( Abc_NtkIsStrash(pNtk) ); // cleanup the AIG Abc_AigCleanup((Abc_Aig_t *)pNtk->pManFunc); Abc_NtkCleanCopy(pNtk); // compute the reverse levels if level update is requested if ( fUpdateLevel ) Abc_NtkStartReverseLevels( pNtk, 0 ); // start the restructuring manager pManRst = Abc_NtkManRstStart( nCutMax, fUpdateLevel, fUseZeros, fVerbose ); pManRst->pNtk = pNtk; // start the cut manager clk = Abc_Clock(); pManCut = Abc_NtkStartCutManForRestruct( pNtk, nCutMax, fMulti ); pManRst->timeCut += Abc_Clock() - clk; // pNtk->pManCut = pManCut; // resynthesize each node once nNodes = Abc_NtkObjNumMax(pNtk); pProgress = Extra_ProgressBarStart( stdout, nNodes ); Abc_NtkForEachNode( pNtk, pNode, i ) { Extra_ProgressBarUpdate( pProgress, i, NULL ); // skip the constant node // if ( Abc_NodeIsConst(pNode) ) // continue; // skip persistant nodes if ( Abc_NodeIsPersistant(pNode) ) continue; // skip the node if it is inside the tree // if ( Abc_ObjFanoutNum(pNode) < 2 ) // continue; // skip the nodes with too many fanouts if ( Abc_ObjFanoutNum(pNode) > 1000 ) continue; // stop if all nodes have been tried once if ( i >= nNodes ) break; // get the cuts for the given node clk = Abc_Clock(); pCutList = (Cut_Cut_t *)Abc_NodeGetCutsRecursive( pManCut, pNode, fMulti, 0 ); pManRst->timeCut += Abc_Clock() - clk; // perform restructuring clk = Abc_Clock(); if ( fResub ) pGraph = Abc_NodeResubstitute( pManRst, pNode, pCutList ); else pGraph = Abc_NodeRestructure( pManRst, pNode, pCutList ); pManRst->timeRes += Abc_Clock() - clk; if ( pGraph == NULL ) continue; // acceptable replacement found, update the graph clk = Abc_Clock(); Dec_GraphUpdateNetwork( pNode, pGraph, fUpdateLevel, pManRst->nLastGain ); pManRst->timeNtk += Abc_Clock() - clk; Dec_GraphFree( pGraph ); } Extra_ProgressBarStop( pProgress ); pManRst->timeTotal = Abc_Clock() - clkStart; // print statistics of the manager // if ( fVerbose ) Abc_NtkManRstPrintStats( pManRst ); // delete the managers Cut_ManStop( pManCut ); Abc_NtkManRstStop( pManRst ); // put the nodes into the DFS order and reassign their IDs Abc_NtkReassignIds( pNtk ); // Abc_AigCheckFaninOrder( pNtk->pManFunc ); // fix the levels if ( fUpdateLevel ) Abc_NtkStopReverseLevels( pNtk ); else Abc_NtkLevel( pNtk ); // check if ( !Abc_NtkCheck( pNtk ) ) { printf( "Abc_NtkRefactor: The network check has failed.\n" ); return 0; } return 1; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_RestructNodeDivisors( Abc_ManRst_t * p, Abc_Obj_t * pRoot, int nNodesSaved ) { Abc_Obj_t * pNode, * pFanout;//, * pFanin; int i, k; // start with the leaves Vec_PtrClear( p->vDecs ); Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pNode, i ) { Vec_PtrPush( p->vDecs, pNode ); assert( pNode->fMarkC == 0 ); pNode->fMarkC = 1; } // explore the fanouts Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pNode, i ) { // if the fanout has both fanins in the set, add it Abc_ObjForEachFanout( pNode, pFanout, k ) { if ( pFanout->fMarkC || Abc_ObjIsPo(pFanout) ) continue; if ( Abc_ObjFanin0(pFanout)->fMarkC && Abc_ObjFanin1(pFanout)->fMarkC ) { Vec_PtrPush( p->vDecs, pFanout ); pFanout->fMarkC = 1; } } } // unmark the nodes Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pNode, i ) pNode->fMarkC = 0; /* // print the nodes Vec_PtrForEachEntryStart( Abc_Obj_t *, p->vDecs, pNode, i, Vec_PtrSize(p->vLeaves) ) { printf( "%2d %s = ", i, Abc_NodeIsTravIdCurrent(pNode)? "*" : " " ); // find the first fanin Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pFanin, k ) if ( Abc_ObjFanin0(pNode) == pFanin ) break; if ( k < Vec_PtrSize(p->vLeaves) ) printf( "%c", 'a' + k ); else printf( "%d", k ); printf( "%s ", Abc_ObjFaninC0(pNode)? "\'" : "" ); // find the second fanin Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pFanin, k ) if ( Abc_ObjFanin1(pNode) == pFanin ) break; if ( k < Vec_PtrSize(p->vLeaves) ) printf( "%c", 'a' + k ); else printf( "%d", k ); printf( "%s ", Abc_ObjFaninC1(pNode)? "\'" : "" ); printf( "\n" ); } */ printf( "%d\n", Vec_PtrSize(p->vDecs)-nNodesSaved-Vec_PtrSize(p->vLeaves) ); } /**Function************************************************************* Synopsis [Starts the cut manager for rewriting.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Dec_Graph_t * Abc_NodeRestructure( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList ) { Dec_Graph_t * pGraph; Cut_Cut_t * pCut; // int nCuts; p->nNodesConsidered++; /* // count the number of cuts with four inputs or more nCuts = 0; for ( pCut = pCutList; pCut; pCut = pCut->pNext ) nCuts += (int)(pCut->nLeaves > 3); printf( "-----------------------------------\n" ); printf( "Node %6d : Factor-cuts = %5d.\n", pNode->Id, nCuts ); */ // go through the interesting cuts for ( pCut = pCutList; pCut; pCut = pCut->pNext ) { if ( pCut->nLeaves < 4 ) continue; if ( (pGraph = Abc_NodeRestructureCut( p, pNode, pCut )) ) return pGraph; } return NULL; } /**Function************************************************************* Synopsis [Starts the cut manager for rewriting.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Dec_Graph_t * Abc_NodeRestructureCut( Abc_ManRst_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut ) { extern DdNode * Abc_NodeConeBdd( DdManager * dd, DdNode ** pbVars, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, Vec_Ptr_t * vVisited ); Dec_Graph_t * pGraph; Dsd_Node_t * pNodeDsd; Abc_Obj_t * pLeaf; DdNode * bFunc; int nNodesSaved, nNodesAdded; int Required, nMaxSize, clk, i; int fVeryVerbose = 0; p->nCutsConsidered++; // get the required time for the node Required = p->fUpdateLevel? Abc_ObjRequiredLevel(pRoot) : ABC_INFINITY; // collect the leaves of the cut Vec_PtrClear( p->vLeaves ); for ( i = 0; i < (int)pCut->nLeaves; i++ ) { pLeaf = Abc_NtkObj(pRoot->pNtk, pCut->pLeaves[i]); if ( pLeaf == NULL ) // the so-called "bad cut phenomenon" is due to removed nodes return NULL; Vec_PtrPush( p->vLeaves, pLeaf ); } clk = Abc_Clock(); // collect the internal nodes of the cut // Abc_NodeConeCollect( &pRoot, 1, p->vLeaves, p->vVisited, 0 ); // derive the BDD of the cut bFunc = Abc_NodeConeBdd( p->dd, p->dd->vars, pRoot, p->vLeaves, p->vVisited ); Cudd_Ref( bFunc ); p->timeBdd += Abc_Clock() - clk; // consider the special case, when the function is a constant if ( Cudd_IsConstant(bFunc) ) { p->nLastGain = Abc_NodeMffcSize( pRoot ); p->nNodesGained += p->nLastGain; p->nNodesRestructured++; Cudd_RecursiveDeref( p->dd, bFunc ); if ( Cudd_IsComplement(bFunc) ) return Dec_GraphCreateConst0(); return Dec_GraphCreateConst1(); } clk = Abc_Clock(); // try disjoint support decomposition pNodeDsd = Dsd_DecomposeOne( p->pManDsd, bFunc ); p->timeDsd += Abc_Clock() - clk; // skip nodes with non-decomposable blocks Dsd_TreeNodeGetInfoOne( pNodeDsd, NULL, &nMaxSize ); if ( nMaxSize > 3 ) { Cudd_RecursiveDeref( p->dd, bFunc ); return NULL; } /* // skip nodes that cannot be improved if ( Vec_PtrSize(p->vVisited) <= Dsd_TreeGetAigCost(pNodeDsd) ) { Cudd_RecursiveDeref( p->dd, bFunc ); return NULL; } */ p->nCutsExplored++; // mark the fanin boundary // (can mark only essential fanins, belonging to bNodeFunc!) Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pLeaf, i ) pLeaf->vFanouts.nSize++; // label MFFC with current traversal ID Abc_NtkIncrementTravId( pRoot->pNtk ); nNodesSaved = Abc_NodeMffcLabelAig( pRoot ); // unmark the fanin boundary and set the fanins as leaves in the form Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pLeaf, i ) pLeaf->vFanouts.nSize--; /* if ( nNodesSaved < 3 ) { Cudd_RecursiveDeref( p->dd, bFunc ); return NULL; } */ /* printf( "%5d : Cut-size = %d. Old AIG = %2d. New AIG = %2d. Old MFFC = %2d.\n", pRoot->Id, pCut->nLeaves, Vec_PtrSize(p->vVisited), Dsd_TreeGetAigCost(pNodeDsd), nNodesSaved ); Dsd_NodePrint( stdout, pNodeDsd ); Abc_RestructNodeDivisors( p, pRoot ); if ( pRoot->Id == 433 ) { int x = 0; } */ // Abc_RestructNodeDivisors( p, pRoot, nNodesSaved ); // detect how many new nodes will be added (while taking into account reused nodes) clk = Abc_Clock(); if ( nMaxSize > 3 ) pGraph = NULL; else pGraph = Abc_NodeEvaluateDsd( p, pNodeDsd, pRoot, Required, nNodesSaved, &nNodesAdded ); // pGraph = NULL; p->timeEval += Abc_Clock() - clk; // quit if there is no improvement if ( pGraph == NULL || nNodesAdded == -1 || (nNodesAdded == nNodesSaved && !p->fUseZeros) ) { Cudd_RecursiveDeref( p->dd, bFunc ); if ( pGraph ) Dec_GraphFree( pGraph ); return NULL; } /* // print stats printf( "%5d : Cut-size = %d. Old AIG = %2d. New AIG = %2d. Old MFFC = %2d. New MFFC = %2d. Gain = %d.\n", pRoot->Id, pCut->nLeaves, Vec_PtrSize(p->vVisited), Dsd_TreeGetAigCost(pNodeDsd), nNodesSaved, nNodesAdded, (nNodesAdded == -1)? 0 : nNodesSaved-nNodesAdded ); // Dsd_NodePrint( stdout, pNodeDsd ); // Dec_GraphPrint( stdout, pGraph, NULL, NULL ); */ // compute the total gain in the number of nodes p->nLastGain = nNodesSaved - nNodesAdded; p->nNodesGained += p->nLastGain; p->nNodesRestructured++; // report the progress if ( fVeryVerbose ) { printf( "Node %6s : ", Abc_ObjName(pRoot) ); printf( "Cone = %2d. ", p->vLeaves->nSize ); printf( "BDD = %2d. ", Cudd_DagSize(bFunc) ); printf( "FF = %2d. ", 1 + Dec_GraphNodeNum(pGraph) ); printf( "MFFC = %2d. ", nNodesSaved ); printf( "Add = %2d. ", nNodesAdded ); printf( "GAIN = %2d. ", p->nLastGain ); printf( "\n" ); } Cudd_RecursiveDeref( p->dd, bFunc ); return pGraph; } /**Function************************************************************* Synopsis [Moves closer to the end the node that is best for sharing.] Description [If the flag is set, tries to find an EXOR, otherwise, tries to find an OR.] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NodeEdgeDsdPermute( Dec_Graph_t * pGraph, Abc_ManRst_t * pManRst, Vec_Int_t * vEdges, int fExor ) { Dec_Edge_t eNode1, eNode2, eNode3; Abc_Obj_t * pNode1, * pNode2, * pNode3, * pTemp; int LeftBound = 0, RightBound, i; // get the right bound RightBound = Vec_IntSize(vEdges) - 2; assert( LeftBound <= RightBound ); if ( LeftBound == RightBound ) return; // get the two last nodes eNode1 = Dec_IntToEdge( Vec_IntEntry(vEdges, RightBound + 1) ); eNode2 = Dec_IntToEdge( Vec_IntEntry(vEdges, RightBound ) ); pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc; pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc; pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl ); pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl ); // quit if the last node does not exist if ( pNode1 == NULL ) return; // find the first node that can be shared for ( i = RightBound; i >= LeftBound; i-- ) { // get the third node eNode3 = Dec_IntToEdge( Vec_IntEntry(vEdges, i) ); pNode3 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode3.Node )->pFunc; pNode3 = !pNode3? NULL : Abc_ObjNotCond( pNode3, eNode3.fCompl ); if ( pNode3 == NULL ) continue; // check if the node exists if ( fExor ) { if ( pNode1 && pNode3 ) { pTemp = Abc_AigXorLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode3, NULL ); if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) ) continue; if ( pNode3 == pNode2 ) return; Vec_IntWriteEntry( vEdges, i, Dec_EdgeToInt(eNode2) ); Vec_IntWriteEntry( vEdges, RightBound, Dec_EdgeToInt(eNode3) ); return; } } else { if ( pNode1 && pNode3 ) { pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode3) ); if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) ) continue; if ( eNode3.Node == eNode2.Node ) return; Vec_IntWriteEntry( vEdges, i, Dec_EdgeToInt(eNode2) ); Vec_IntWriteEntry( vEdges, RightBound, Dec_EdgeToInt(eNode3) ); return; } } } } /**Function************************************************************* Synopsis [Adds the new edge in the given order.] Description [Similar to Vec_IntPushOrder, except in decreasing order.] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NodeEdgeDsdPushOrdered( Dec_Graph_t * pGraph, Vec_Int_t * vEdges, int Edge ) { int i, NodeOld, NodeNew; vEdges->nSize++; for ( i = vEdges->nSize-2; i >= 0; i-- ) { NodeOld = Dec_IntToEdge(vEdges->pArray[i]).Node; NodeNew = Dec_IntToEdge(Edge).Node; // use <= because we are trying to push the new (non-existent) nodes as far as possible if ( Dec_GraphNode(pGraph, NodeOld)->Level <= Dec_GraphNode(pGraph, NodeNew)->Level ) vEdges->pArray[i+1] = vEdges->pArray[i]; else break; } vEdges->pArray[i+1] = Edge; } /**Function************************************************************* Synopsis [Evaluation one DSD.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Dec_Edge_t Abc_NodeEvaluateDsd_rec( Dec_Graph_t * pGraph, Abc_ManRst_t * pManRst, Dsd_Node_t * pNodeDsd, int Required, int nNodesSaved, int * pnNodesAdded ) { Dec_Edge_t eNode1, eNode2, eNode3, eResult, eQuit = { 0, 2006 }; Abc_Obj_t * pNode1, * pNode2, * pNode3, * pNode4, * pTemp; Dsd_Node_t * pChildDsd; Dsd_Type_t DecType; Vec_Int_t * vEdges; int Level1, Level2, Level3, Level4; int i, Index, fCompl, Type; // remove the complemented attribute fCompl = Dsd_IsComplement( pNodeDsd ); pNodeDsd = Dsd_Regular( pNodeDsd ); // consider the trivial case DecType = Dsd_NodeReadType( pNodeDsd ); if ( DecType == DSD_NODE_BUF ) { Index = Dsd_NodeReadFunc(pNodeDsd)->index; assert( Index < Dec_GraphLeaveNum(pGraph) ); eResult = Dec_EdgeCreate( Index, fCompl ); return eResult; } assert( DecType == DSD_NODE_OR || DecType == DSD_NODE_EXOR || DecType == DSD_NODE_PRIME ); // solve the problem for the children vEdges = Vec_IntAlloc( Dsd_NodeReadDecsNum(pNodeDsd) ); Dsd_NodeForEachChild( pNodeDsd, i, pChildDsd ) { eResult = Abc_NodeEvaluateDsd_rec( pGraph, pManRst, pChildDsd, Required, nNodesSaved, pnNodesAdded ); if ( eResult.Node == eQuit.Node ) // infeasible { Vec_IntFree( vEdges ); return eQuit; } // order the inputs only if this is OR or EXOR if ( DecType == DSD_NODE_PRIME ) Vec_IntPush( vEdges, Dec_EdgeToInt(eResult) ); else Abc_NodeEdgeDsdPushOrdered( pGraph, vEdges, Dec_EdgeToInt(eResult) ); } // the edges are sorted by the level of their nodes in decreasing order // consider special cases if ( DecType == DSD_NODE_OR ) { // try to balance the nodes by delay assert( Vec_IntSize(vEdges) > 1 ); while ( Vec_IntSize(vEdges) > 1 ) { // permute the last two entries if ( Vec_IntSize(vEdges) > 2 ) Abc_NodeEdgeDsdPermute( pGraph, pManRst, vEdges, 0 ); // get the two last nodes eNode1 = Dec_IntToEdge( Vec_IntPop(vEdges) ); eNode2 = Dec_IntToEdge( Vec_IntPop(vEdges) ); pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc; pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc; pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl ); pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl ); // check if the new node exists pNode3 = NULL; if ( pNode1 && pNode2 ) { pNode3 = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode2) ); pNode3 = !pNode3? NULL : Abc_ObjNot(pNode3); } // create the new node eNode3 = Dec_GraphAddNodeOr( pGraph, eNode1, eNode2 ); // set level Level1 = Dec_GraphNode( pGraph, eNode1.Node )->Level; Level2 = Dec_GraphNode( pGraph, eNode2.Node )->Level; Dec_GraphNode( pGraph, eNode3.Node )->Level = 1 + Abc_MaxInt(Level1, Level2); // get the new node if possible if ( pNode3 ) { Dec_GraphNode( pGraph, eNode3.Node )->pFunc = Abc_ObjNotCond(pNode3, eNode3.fCompl); Level3 = Dec_GraphNode( pGraph, eNode3.Node )->Level; assert( Required == ABC_INFINITY || Level3 == (int)Abc_ObjRegular(pNode3)->Level ); } if ( !pNode3 || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pNode3)) ) { (*pnNodesAdded)++; if ( *pnNodesAdded > nNodesSaved ) { Vec_IntFree( vEdges ); return eQuit; } } // add the resulting node to the form Abc_NodeEdgeDsdPushOrdered( pGraph, vEdges, Dec_EdgeToInt(eNode3) ); } // get the last node eResult = Dec_IntToEdge( Vec_IntPop(vEdges) ); Vec_IntFree( vEdges ); // complement the graph if the node was complemented eResult.fCompl ^= fCompl; return eResult; } if ( DecType == DSD_NODE_EXOR ) { // try to balance the nodes by delay assert( Vec_IntSize(vEdges) > 1 ); while ( Vec_IntSize(vEdges) > 1 ) { // permute the last two entries if ( Vec_IntSize(vEdges) > 2 ) Abc_NodeEdgeDsdPermute( pGraph, pManRst, vEdges, 1 ); // get the two last nodes eNode1 = Dec_IntToEdge( Vec_IntPop(vEdges) ); eNode2 = Dec_IntToEdge( Vec_IntPop(vEdges) ); pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc; pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc; pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl ); pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl ); // check if the new node exists Type = 0; pNode3 = NULL; if ( pNode1 && pNode2 ) pNode3 = Abc_AigXorLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2, &Type ); // create the new node eNode3 = Dec_GraphAddNodeXor( pGraph, eNode1, eNode2, Type ); // should have the same structure as in AIG // set level Level1 = Dec_GraphNode( pGraph, eNode1.Node )->Level; Level2 = Dec_GraphNode( pGraph, eNode2.Node )->Level; Dec_GraphNode( pGraph, eNode3.Node )->Level = 2 + Abc_MaxInt(Level1, Level2); // get the new node if possible if ( pNode3 ) { Dec_GraphNode( pGraph, eNode3.Node )->pFunc = Abc_ObjNotCond(pNode3, eNode3.fCompl); Level3 = Dec_GraphNode( pGraph, eNode3.Node )->Level; assert( Required == ABC_INFINITY || Level3 == (int)Abc_ObjRegular(pNode3)->Level ); } if ( !pNode3 || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pNode3)) ) { (*pnNodesAdded)++; if ( !pNode1 || !pNode2 ) (*pnNodesAdded) += 2; else if ( Type == 0 ) { pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, Abc_ObjNot(pNode2) ); if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) ) (*pnNodesAdded)++; pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), pNode2 ); if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) ) (*pnNodesAdded)++; } else { pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode2) ); if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) ) (*pnNodesAdded)++; pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2 ); if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) ) (*pnNodesAdded)++; } if ( *pnNodesAdded > nNodesSaved ) { Vec_IntFree( vEdges ); return eQuit; } } // add the resulting node to the form Abc_NodeEdgeDsdPushOrdered( pGraph, vEdges, Dec_EdgeToInt(eNode3) ); } // get the last node eResult = Dec_IntToEdge( Vec_IntPop(vEdges) ); Vec_IntFree( vEdges ); // complement the graph if the node is complemented eResult.fCompl ^= fCompl; return eResult; } if ( DecType == DSD_NODE_PRIME ) { DdNode * bLocal, * bVar, * bCofT, * bCofE; bLocal = Dsd_TreeGetPrimeFunction( pManRst->dd, pNodeDsd ); Cudd_Ref( bLocal ); //Extra_bddPrint( pManRst->dd, bLocal ); bVar = pManRst->dd->vars[0]; bCofE = Cudd_Cofactor( pManRst->dd, bLocal, Cudd_Not(bVar) ); Cudd_Ref( bCofE ); bCofT = Cudd_Cofactor( pManRst->dd, bLocal, bVar ); Cudd_Ref( bCofT ); if ( !Extra_bddIsVar(bCofE) || !Extra_bddIsVar(bCofT) ) { Cudd_RecursiveDeref( pManRst->dd, bCofE ); Cudd_RecursiveDeref( pManRst->dd, bCofT ); bVar = pManRst->dd->vars[1]; bCofE = Cudd_Cofactor( pManRst->dd, bLocal, Cudd_Not(bVar) ); Cudd_Ref( bCofE ); bCofT = Cudd_Cofactor( pManRst->dd, bLocal, bVar ); Cudd_Ref( bCofT ); if ( !Extra_bddIsVar(bCofE) || !Extra_bddIsVar(bCofT) ) { Cudd_RecursiveDeref( pManRst->dd, bCofE ); Cudd_RecursiveDeref( pManRst->dd, bCofT ); bVar = pManRst->dd->vars[2]; bCofE = Cudd_Cofactor( pManRst->dd, bLocal, Cudd_Not(bVar) ); Cudd_Ref( bCofE ); bCofT = Cudd_Cofactor( pManRst->dd, bLocal, bVar ); Cudd_Ref( bCofT ); if ( !Extra_bddIsVar(bCofE) || !Extra_bddIsVar(bCofT) ) { Cudd_RecursiveDeref( pManRst->dd, bCofE ); Cudd_RecursiveDeref( pManRst->dd, bCofT ); Cudd_RecursiveDeref( pManRst->dd, bLocal ); Vec_IntFree( vEdges ); return eQuit; } } } Cudd_RecursiveDeref( pManRst->dd, bLocal ); // we found the control variable (bVar) and the var-cofactors (bCofT, bCofE) // find the graph nodes eNode1 = Dec_IntToEdge( Vec_IntEntry(vEdges, bVar->index) ); eNode2 = Dec_IntToEdge( Vec_IntEntry(vEdges, Cudd_Regular(bCofT)->index) ); eNode3 = Dec_IntToEdge( Vec_IntEntry(vEdges, Cudd_Regular(bCofE)->index) ); // add the complements to the graph nodes eNode2.fCompl ^= Cudd_IsComplement(bCofT); eNode3.fCompl ^= Cudd_IsComplement(bCofE); // because the cofactors are vars, we can just as well deref them here Cudd_RecursiveDeref( pManRst->dd, bCofE ); Cudd_RecursiveDeref( pManRst->dd, bCofT ); // find the ABC nodes pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc; pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc; pNode3 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode3.Node )->pFunc; pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl ); pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl ); pNode3 = !pNode3? NULL : Abc_ObjNotCond( pNode3, eNode3.fCompl ); // check if the new node exists Type = 0; pNode4 = NULL; if ( pNode1 && pNode2 && pNode3 ) pNode4 = Abc_AigMuxLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2, pNode3, &Type ); // create the new node eResult = Dec_GraphAddNodeMux( pGraph, eNode1, eNode2, eNode3, Type ); // should have the same structure as AIG // set level Level1 = Dec_GraphNode( pGraph, eNode1.Node )->Level; Level2 = Dec_GraphNode( pGraph, eNode2.Node )->Level; Level3 = Dec_GraphNode( pGraph, eNode3.Node )->Level; Dec_GraphNode( pGraph, eResult.Node )->Level = 2 + Abc_MaxInt( Abc_MaxInt(Level1, Level2), Level3 ); // get the new node if possible if ( pNode4 ) { Dec_GraphNode( pGraph, eResult.Node )->pFunc = Abc_ObjNotCond(pNode4, eResult.fCompl); Level4 = Dec_GraphNode( pGraph, eResult.Node )->Level; assert( Required == ABC_INFINITY || Level4 == (int)Abc_ObjRegular(pNode4)->Level ); } if ( !pNode4 || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pNode4)) ) { (*pnNodesAdded)++; if ( Type == 0 ) { if ( !pNode1 || !pNode2 ) (*pnNodesAdded)++; else { pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2 ); if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) ) (*pnNodesAdded)++; } if ( !pNode1 || !pNode3 ) (*pnNodesAdded)++; else { pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), pNode3 ); if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) ) (*pnNodesAdded)++; } } else { if ( !pNode1 || !pNode2 ) (*pnNodesAdded)++; else { pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, Abc_ObjNot(pNode2) ); if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) ) (*pnNodesAdded)++; } if ( !pNode1 || !pNode3 ) (*pnNodesAdded)++; else { pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode3) ); if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) ) (*pnNodesAdded)++; } } if ( *pnNodesAdded > nNodesSaved ) { Vec_IntFree( vEdges ); return eQuit; } } Vec_IntFree( vEdges ); // complement the graph if the node was complemented eResult.fCompl ^= fCompl; return eResult; } Vec_IntFree( vEdges ); return eQuit; } /**Function************************************************************* Synopsis [Evaluation one DSD.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Dec_Graph_t * Abc_NodeEvaluateDsd( Abc_ManRst_t * pManRst, Dsd_Node_t * pNodeDsd, Abc_Obj_t * pRoot, int Required, int nNodesSaved, int * pnNodesAdded ) { Dec_Graph_t * pGraph; Dec_Edge_t gEdge; Abc_Obj_t * pLeaf; Dec_Node_t * pNode; int i; // create the graph and set the leaves pGraph = Dec_GraphCreate( Vec_PtrSize(pManRst->vLeaves) ); Dec_GraphForEachLeaf( pGraph, pNode, i ) { pLeaf = (Abc_Obj_t *)Vec_PtrEntry( pManRst->vLeaves, i ); pNode->pFunc = pLeaf; pNode->Level = pLeaf->Level; } // create the decomposition structure from the DSD *pnNodesAdded = 0; gEdge = Abc_NodeEvaluateDsd_rec( pGraph, pManRst, pNodeDsd, Required, nNodesSaved, pnNodesAdded ); if ( gEdge.Node > 1000 ) // infeasible { *pnNodesAdded = -1; Dec_GraphFree( pGraph ); return NULL; } // quit if the root node is the same pLeaf = (Abc_Obj_t *)Dec_GraphNode( pGraph, gEdge.Node )->pFunc; if ( Abc_ObjRegular(pLeaf) == pRoot ) { *pnNodesAdded = -1; Dec_GraphFree( pGraph ); return NULL; } Dec_GraphSetRoot( pGraph, gEdge ); return pGraph; } /**Function************************************************************* Synopsis [Starts the cut manager for rewriting.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Cut_Man_t * Abc_NtkStartCutManForRestruct( Abc_Ntk_t * pNtk, int nCutMax, int fDag ) { static Cut_Params_t Params, * pParams = &Params; Cut_Man_t * pManCut; Abc_Obj_t * pObj; int i; // start the cut manager memset( pParams, 0, sizeof(Cut_Params_t) ); pParams->nVarsMax = nCutMax; // the max cut size ("k" of the k-feasible cuts) pParams->nKeepMax = 250; // the max number of cuts kept at a node pParams->fTruth = 0; // compute truth tables pParams->fFilter = 1; // filter dominated cuts pParams->fSeq = 0; // compute sequential cuts pParams->fDrop = 0; // drop cuts on the fly pParams->fDag = fDag; // compute DAG cuts pParams->fTree = 0; // compute tree cuts pParams->fVerbose = 0; // the verbosiness flag pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); pManCut = Cut_ManStart( pParams ); if ( pParams->fDrop ) Cut_ManSetFanoutCounts( pManCut, Abc_NtkFanoutCounts(pNtk) ); // set cuts for PIs Abc_NtkForEachCi( pNtk, pObj, i ) if ( Abc_ObjFanoutNum(pObj) > 0 ) Cut_NodeSetTriv( pManCut, pObj->Id ); return pManCut; } /**Function************************************************************* Synopsis [Starts the resynthesis manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Abc_ManRst_t * Abc_NtkManRstStart( int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose ) { Abc_ManRst_t * p; p = ABC_ALLOC( Abc_ManRst_t, 1 ); memset( p, 0, sizeof(Abc_ManRst_t) ); // set the parameters p->nCutMax = nCutMax; p->fUpdateLevel = fUpdateLevel; p->fUseZeros = fUseZeros; p->fVerbose = fVerbose; // start the BDD manager p->dd = Cudd_Init( p->nCutMax, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 ); Cudd_zddVarsFromBddVars( p->dd, 2 ); // start the DSD manager p->pManDsd = Dsd_ManagerStart( p->dd, p->dd->size, 0 ); // other temp datastructures p->vVisited = Vec_PtrAlloc( 100 ); p->vLeaves = Vec_PtrAlloc( 100 ); p->vDecs = Vec_PtrAlloc( 100 ); p->vTemp = Vec_PtrAlloc( 100 ); p->vSims = Vec_IntAlloc( 100 ); p->vOnes = Vec_IntAlloc( 100 ); p->vBinate = Vec_IntAlloc( 100 ); p->vTwos = Vec_IntAlloc( 100 ); p->vRands = Vec_IntAlloc( 20 ); { int i; for ( i = 0; i < 20; i++ ) Vec_IntPush( p->vRands, (int)RST_RANDOM_UNSIGNED ); } return p; } /**Function************************************************************* Synopsis [Stops the resynthesis manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NtkManRstStop( Abc_ManRst_t * p ) { Dsd_ManagerStop( p->pManDsd ); Extra_StopManager( p->dd ); Vec_PtrFree( p->vDecs ); Vec_PtrFree( p->vLeaves ); Vec_PtrFree( p->vVisited ); Vec_PtrFree( p->vTemp ); Vec_IntFree( p->vSims ); Vec_IntFree( p->vOnes ); Vec_IntFree( p->vBinate ); Vec_IntFree( p->vTwos ); Vec_IntFree( p->vRands ); ABC_FREE( p ); } /**Function************************************************************* Synopsis [Stops the resynthesis manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NtkManRstPrintStats( Abc_ManRst_t * p ) { printf( "Refactoring statistics:\n" ); printf( "Nodes considered = %8d.\n", p->nNodesConsidered ); printf( "Cuts considered = %8d.\n", p->nCutsConsidered ); printf( "Cuts explored = %8d.\n", p->nCutsExplored ); printf( "Nodes restructured = %8d.\n", p->nNodesRestructured ); printf( "Calculated gain = %8d.\n", p->nNodesGained ); ABC_PRT( "Cuts ", p->timeCut ); ABC_PRT( "Resynthesis", p->timeRes ); ABC_PRT( " BDD ", p->timeBdd ); ABC_PRT( " DSD ", p->timeDsd ); ABC_PRT( " Eval ", p->timeEval ); ABC_PRT( "AIG update ", p->timeNtk ); ABC_PRT( "TOTAL ", p->timeTotal ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_Abc_NodeResubCollectDivs( Abc_ManRst_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut ) { Abc_Obj_t * pNode, * pFanout; int i, k; // collect the leaves of the cut Vec_PtrClear( p->vDecs ); Abc_NtkIncrementTravId( pRoot->pNtk ); for ( i = 0; i < (int)pCut->nLeaves; i++ ) { pNode = Abc_NtkObj(pRoot->pNtk, pCut->pLeaves[i]); if ( pNode == NULL ) // the so-called "bad cut phenomenon" is due to removed nodes return 0; Vec_PtrPush( p->vDecs, pNode ); Abc_NodeSetTravIdCurrent( pNode ); } // explore the fanouts Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pNode, i ) { // if the fanout has both fanins in the set, add it Abc_ObjForEachFanout( pNode, pFanout, k ) { if ( Abc_NodeIsTravIdCurrent(pFanout) || Abc_ObjIsPo(pFanout) ) continue; if ( Abc_NodeIsTravIdCurrent(Abc_ObjFanin0(pFanout)) && Abc_NodeIsTravIdCurrent(Abc_ObjFanin1(pFanout)) ) { Vec_PtrPush( p->vDecs, pFanout ); Abc_NodeSetTravIdCurrent( pFanout ); } } } return 1; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NodeResubMffc_rec( Abc_Obj_t * pNode ) { if ( Abc_NodeIsTravIdCurrent(pNode) ) return 0; Abc_NodeSetTravIdCurrent( pNode ); return 1 + Abc_NodeResubMffc_rec( Abc_ObjFanin0(pNode) ) + Abc_NodeResubMffc_rec( Abc_ObjFanin1(pNode) ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NodeResubMffc( Abc_ManRst_t * p, Vec_Ptr_t * vDecs, int nLeaves, Abc_Obj_t * pRoot ) { Abc_Obj_t * pObj; int Counter, i, k; // increment the traversal ID for the leaves Abc_NtkIncrementTravId( pRoot->pNtk ); // label the leaves Vec_PtrForEachEntryStop( Abc_Obj_t *, vDecs, pObj, i, nLeaves ) Abc_NodeSetTravIdCurrent( pObj ); // make sure the node is in the cone and is no one of the leaves assert( Abc_NodeIsTravIdPrevious(pRoot) ); Counter = Abc_NodeResubMffc_rec( pRoot ); // move the labeled nodes to the end Vec_PtrClear( p->vTemp ); k = 0; Vec_PtrForEachEntryStart( Abc_Obj_t *, vDecs, pObj, i, nLeaves ) if ( Abc_NodeIsTravIdCurrent(pObj) ) Vec_PtrPush( p->vTemp, pObj ); else Vec_PtrWriteEntry( vDecs, k++, pObj ); // add the labeled nodes Vec_PtrForEachEntry( Abc_Obj_t *, p->vTemp, pObj, i ) Vec_PtrWriteEntry( vDecs, k++, pObj ); assert( k == Vec_PtrSize(p->vDecs) ); assert( pRoot == Vec_PtrEntryLast(p->vDecs) ); return Counter; } /**Function************************************************************* Synopsis [Performs simulation.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NodeMffcSimulate( Vec_Ptr_t * vDecs, int nLeaves, Vec_Int_t * vRands, Vec_Int_t * vSims ) { Abc_Obj_t * pObj; unsigned uData0, uData1, uData; int i; // initialize random simulation data Vec_IntClear( vSims ); Vec_PtrForEachEntryStop( Abc_Obj_t *, vDecs, pObj, i, nLeaves ) { uData = (unsigned)Vec_IntEntry( vRands, i ); pObj->pData = (void *)(ABC_PTRUINT_T)uData; Vec_IntPush( vSims, uData ); } // simulate Vec_PtrForEachEntryStart( Abc_Obj_t *, vDecs, pObj, i, nLeaves ) { uData0 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pData; uData1 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin1(pObj)->pData; uData = (Abc_ObjFaninC0(pObj)? ~uData0 : uData0) & (Abc_ObjFaninC1(pObj)? ~uData1 : uData1); pObj->pData = (void *)(ABC_PTRUINT_T)uData; Vec_IntPush( vSims, uData ); } } /**Function************************************************************* Synopsis [Full equality check.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NodeCheckFull( Abc_ManRst_t * p, Dec_Graph_t * pGraph ) { return 1; } /**Function************************************************************* Synopsis [Detect contants.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Dec_Graph_t * Abc_NodeMffcConstants( Abc_ManRst_t * p, Vec_Int_t * vSims ) { Dec_Graph_t * pGraph = NULL; unsigned uRoot; // get the root node uRoot = (unsigned)Vec_IntEntryLast( vSims ); // get the graph if the node looks constant if ( uRoot == 0 ) pGraph = Dec_GraphCreateConst0(); else if ( uRoot == ~(unsigned)0 ) pGraph = Dec_GraphCreateConst1(); // check the graph assert(pGraph); if ( Abc_NodeCheckFull( p, pGraph ) ) return pGraph; Dec_GraphFree( pGraph ); return NULL; } /**Function************************************************************* Synopsis [Detect single non-overlaps.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Dec_Graph_t * Abc_NodeMffcSingleVar( Abc_ManRst_t * p, Vec_Int_t * vSims, int nNodes, Vec_Int_t * vOnes ) { Dec_Graph_t * pGraph; unsigned uRoot, uNode; int i; Vec_IntClear( vOnes ); Vec_IntClear( p->vBinate ); uRoot = (unsigned)Vec_IntEntryLast( vSims ); for ( i = 0; i < nNodes; i++ ) { uNode = (unsigned)Vec_IntEntry( vSims, i ); if ( uRoot == uNode || uRoot == ~uNode ) { pGraph = Dec_GraphCreate( 1 ); Dec_GraphNode( pGraph, 0 )->pFunc = Vec_PtrEntry( p->vDecs, i ); Dec_GraphSetRoot( pGraph, Dec_IntToEdge( (int)(uRoot == ~uNode) ) ); // check the graph if ( Abc_NodeCheckFull( p, pGraph ) ) return pGraph; Dec_GraphFree( pGraph ); } if ( (uRoot & uNode) == 0 ) Vec_IntPush( vOnes, i << 1 ); else if ( (uRoot & ~uNode) == 0 ) Vec_IntPush( vOnes, (i << 1) + 1 ); else Vec_IntPush( p->vBinate, i ); } return NULL; } /**Function************************************************************* Synopsis [Detect single non-overlaps.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Dec_Graph_t * Abc_NodeMffcSingleNode( Abc_ManRst_t * p, Vec_Int_t * vSims, int nNodes, Vec_Int_t * vOnes ) { Dec_Graph_t * pGraph; Dec_Edge_t eNode0, eNode1, eRoot; unsigned uRoot; int i, k; uRoot = (unsigned)Vec_IntEntryLast( vSims ); for ( i = 0; i < vOnes->nSize; i++ ) for ( k = i+1; k < vOnes->nSize; k++ ) if ( ~uRoot == ((unsigned)vOnes->pArray[i] | (unsigned)vOnes->pArray[k]) ) { eNode0 = Dec_IntToEdge( vOnes->pArray[i] ^ 1 ); eNode1 = Dec_IntToEdge( vOnes->pArray[k] ^ 1 ); pGraph = Dec_GraphCreate( 2 ); Dec_GraphNode( pGraph, 0 )->pFunc = Vec_PtrEntry( p->vDecs, eNode0.Node ); Dec_GraphNode( pGraph, 1 )->pFunc = Vec_PtrEntry( p->vDecs, eNode1.Node ); eRoot = Dec_GraphAddNodeAnd( pGraph, eNode0, eNode1 ); Dec_GraphSetRoot( pGraph, eRoot ); if ( Abc_NodeCheckFull( p, pGraph ) ) return pGraph; Dec_GraphFree( pGraph ); } return NULL; } /**Function************************************************************* Synopsis [Detect single non-overlaps.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Dec_Graph_t * Abc_NodeMffcDoubleNode( Abc_ManRst_t * p, Vec_Int_t * vSims, int nNodes, Vec_Int_t * vOnes ) { // Dec_Graph_t * pGraph; // unsigned uRoot, uNode; // int i; return NULL; } /**Function************************************************************* Synopsis [Evaluates resubstution of one cut.] Description [Returns the graph to add if any.] SideEffects [] SeeAlso [] ***********************************************************************/ Dec_Graph_t * Abc_NodeResubEval( Abc_ManRst_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut ) { Dec_Graph_t * pGraph; int nNodesSaved; // collect the nodes in the cut if ( !Abc_Abc_NodeResubCollectDivs( p, pRoot, pCut ) ) return NULL; // label MFFC and count its size nNodesSaved = Abc_NodeResubMffc( p, p->vDecs, pCut->nLeaves, pRoot ); assert( nNodesSaved > 0 ); // simulate MFFC Abc_NodeMffcSimulate( p->vDecs, pCut->nLeaves, p->vRands, p->vSims ); // check for constant output pGraph = Abc_NodeMffcConstants( p, p->vSims ); if ( pGraph ) { p->nNodesGained += nNodesSaved; p->nNodesRestructured++; return pGraph; } // check for one literal (fill up the ones array) pGraph = Abc_NodeMffcSingleVar( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved, p->vOnes ); if ( pGraph ) { p->nNodesGained += nNodesSaved; p->nNodesRestructured++; return pGraph; } if ( nNodesSaved == 1 ) return NULL; // look for one node pGraph = Abc_NodeMffcSingleNode( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved, p->vOnes ); if ( pGraph ) { p->nNodesGained += nNodesSaved - 1; p->nNodesRestructured++; return pGraph; } if ( nNodesSaved == 2 ) return NULL; // look for two nodes pGraph = Abc_NodeMffcDoubleNode( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved, p->vOnes ); if ( pGraph ) { p->nNodesGained += nNodesSaved - 2; p->nNodesRestructured++; return pGraph; } if ( nNodesSaved == 3 ) return NULL; /* // look for MUX/EXOR pGraph = Abc_NodeMffcMuxNode( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved ); if ( pGraph ) { p->nNodesGained += nNodesSaved - 1; p->nNodesRestructured++; return pGraph; } */ return NULL; } /**Function************************************************************* Synopsis [Performs resubstution.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Dec_Graph_t * Abc_NodeResubstitute( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList ) { Dec_Graph_t * pGraph, * pGraphBest = NULL; Cut_Cut_t * pCut; int nCuts; p->nNodesConsidered++; // count the number of cuts with four inputs or more nCuts = 0; for ( pCut = pCutList; pCut; pCut = pCut->pNext ) nCuts += (int)(pCut->nLeaves > 3); printf( "-----------------------------------\n" ); printf( "Node %6d : Factor-cuts = %5d.\n", pNode->Id, nCuts ); // go through the interesting cuts for ( pCut = pCutList; pCut; pCut = pCut->pNext ) { if ( pCut->nLeaves < 4 ) continue; pGraph = Abc_NodeResubEval( p, pNode, pCut ); if ( pGraph == NULL ) continue; if ( !pGraphBest || Dec_GraphNodeNum(pGraph) < Dec_GraphNodeNum(pGraphBest) ) { if ( pGraphBest ) Dec_GraphFree(pGraphBest); pGraphBest = pGraph; } else Dec_GraphFree(pGraph); } return pGraphBest; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END