/**CFile**************************************************************** FileName [ivySeq.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [And-Inverter Graph package.] Synopsis [] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - May 11, 2006.] Revision [$Id: ivySeq.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $] ***********************************************************************/ #include "ivy.h" #include "bool/deco/deco.h" #include "opt/rwt/rwt.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// static int Ivy_NodeRewriteSeq( Ivy_Man_t * pMan, Rwt_Man_t * p, Ivy_Obj_t * pNode, int fUseZeroCost ); static void Ivy_GraphPrepare( Dec_Graph_t * pGraph, Ivy_Cut_t * pCut, Vec_Ptr_t * vFanins, char * pPerm ); static unsigned Ivy_CutGetTruth( Ivy_Man_t * p, Ivy_Obj_t * pObj, int * pNums, int nNums ); static Dec_Graph_t * Rwt_CutEvaluateSeq( Ivy_Man_t * pMan, Rwt_Man_t * p, Ivy_Obj_t * pRoot, Ivy_Cut_t * pCut, char * pPerm, Vec_Ptr_t * vFaninsCur, int nNodesSaved, int * pGainBest, unsigned uTruth ); static int Ivy_GraphToNetworkSeqCountSeq( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Dec_Graph_t * pGraph, int NodeMax ); static Ivy_Obj_t * Ivy_GraphToNetworkSeq( Ivy_Man_t * p, Dec_Graph_t * pGraph ); static void Ivy_GraphUpdateNetworkSeq( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Dec_Graph_t * pGraph, int nGain ); static Ivy_Store_t * Ivy_CutComputeForNode( Ivy_Man_t * p, Ivy_Obj_t * pObj, int nLeaves ); static inline int Ivy_CutHashValue( int NodeId ) { return 1 << (NodeId % 31); } //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// //int nMoves; //int nMovesS; //int nClauses; //int timeInv; /**Function************************************************************* Synopsis [Performs incremental rewriting of the AIG.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Ivy_ManRewriteSeq( Ivy_Man_t * p, int fUseZeroCost, int fVerbose ) { Rwt_Man_t * pManRwt; Ivy_Obj_t * pNode; int i, nNodes, nGain; abctime clk, clkStart = Abc_Clock(); // set the DC latch values Ivy_ManForEachLatch( p, pNode, i ) pNode->Init = IVY_INIT_DC; // start the rewriting manager pManRwt = Rwt_ManStart( 0 ); p->pData = pManRwt; if ( pManRwt == NULL ) return 0; // create fanouts if ( p->fFanout == 0 ) Ivy_ManStartFanout( p ); // resynthesize each node once nNodes = Ivy_ManObjIdMax(p); Ivy_ManForEachNode( p, pNode, i ) { assert( !Ivy_ObjIsBuf(pNode) ); assert( !Ivy_ObjIsBuf(Ivy_ObjFanin0(pNode)) ); assert( !Ivy_ObjIsBuf(Ivy_ObjFanin1(pNode)) ); // fix the fanin buffer problem // Ivy_NodeFixBufferFanins( p, pNode ); // if ( Ivy_ObjIsBuf(pNode) ) // continue; // stop if all nodes have been tried once if ( i > nNodes ) break; // for each cut, try to resynthesize it nGain = Ivy_NodeRewriteSeq( p, pManRwt, pNode, fUseZeroCost ); if ( nGain > 0 || (nGain == 0 && fUseZeroCost) ) { Dec_Graph_t * pGraph = (Dec_Graph_t *)Rwt_ManReadDecs(pManRwt); int fCompl = Rwt_ManReadCompl(pManRwt); // complement the FF if needed clk = Abc_Clock(); if ( fCompl ) Dec_GraphComplement( pGraph ); Ivy_GraphUpdateNetworkSeq( p, pNode, pGraph, nGain ); if ( fCompl ) Dec_GraphComplement( pGraph ); Rwt_ManAddTimeUpdate( pManRwt, Abc_Clock() - clk ); } } Rwt_ManAddTimeTotal( pManRwt, Abc_Clock() - clkStart ); // print stats if ( fVerbose ) Rwt_ManPrintStats( pManRwt ); // delete the managers Rwt_ManStop( pManRwt ); p->pData = NULL; // fix the levels Ivy_ManResetLevels( p ); // if ( Ivy_ManCheckFanoutNums(p) ) // printf( "Ivy_ManRewritePre(): The check has failed.\n" ); // check if ( !Ivy_ManCheck(p) ) printf( "Ivy_ManRewritePre(): The check has failed.\n" ); return 1; } /**Function************************************************************* Synopsis [Performs rewriting for one node.] Description [This procedure considers all the cuts computed for the node and tries to rewrite each of them using the "forest" of different AIG structures precomputed and stored in the RWR manager. Determines the best rewriting and computes the gain in the number of AIG nodes in the final network. In the end, p->vFanins contains information about the best cut that can be used for rewriting, while p->pGraph gives the decomposition dag (represented using decomposition graph data structure). Returns gain in the number of nodes or -1 if node cannot be rewritten.] SideEffects [] SeeAlso [] ***********************************************************************/ int Ivy_NodeRewriteSeq( Ivy_Man_t * pMan, Rwt_Man_t * p, Ivy_Obj_t * pNode, int fUseZeroCost ) { int fVeryVerbose = 0; Dec_Graph_t * pGraph; Ivy_Store_t * pStore; Ivy_Cut_t * pCut; Ivy_Obj_t * pFanin;//, * pFanout; Vec_Ptr_t * vFanout; unsigned uPhase; unsigned uTruthBest = 0; // Suppress "might be used uninitialized" unsigned uTruth;//, nNewClauses; char * pPerm; int nNodesSaved; int nNodesSaveCur = -1; // Suppress "might be used uninitialized" int i, c, GainCur, GainBest = -1; abctime clk, clk2;//, clk3; p->nNodesConsidered++; // get the node's cuts clk = Abc_Clock(); pStore = Ivy_CutComputeForNode( pMan, pNode, 5 ); p->timeCut += Abc_Clock() - clk; // go through the cuts clk = Abc_Clock(); vFanout = Vec_PtrAlloc( 100 ); for ( c = 1; c < pStore->nCuts; c++ ) { pCut = pStore->pCuts + c; // consider only 4-input cuts if ( pCut->nSize != 4 ) continue; // skip the cuts with buffers for ( i = 0; i < (int)pCut->nSize; i++ ) if ( Ivy_ObjIsBuf( Ivy_ManObj(pMan, Ivy_LeafId(pCut->pArray[i])) ) ) break; if ( i != pCut->nSize ) { p->nCutsBad++; continue; } p->nCutsGood++; // get the fanin permutation clk2 = Abc_Clock(); uTruth = 0xFFFF & Ivy_CutGetTruth( pMan, pNode, pCut->pArray, pCut->nSize ); // truth table p->timeTruth += Abc_Clock() - clk2; pPerm = p->pPerms4[ (int)p->pPerms[uTruth] ]; uPhase = p->pPhases[uTruth]; // collect fanins with the corresponding permutation/phase Vec_PtrClear( p->vFaninsCur ); Vec_PtrFill( p->vFaninsCur, (int)pCut->nSize, 0 ); for ( i = 0; i < (int)pCut->nSize; i++ ) { pFanin = Ivy_ManObj( pMan, Ivy_LeafId( pCut->pArray[(int)pPerm[i]] ) ); assert( Ivy_ObjIsNode(pFanin) || Ivy_ObjIsCi(pFanin) || Ivy_ObjIsConst1(pFanin) ); pFanin = Ivy_NotCond(pFanin, ((uPhase & (1< 0) ); Vec_PtrWriteEntry( p->vFaninsCur, i, pFanin ); } clk2 = Abc_Clock(); // mark the fanin boundary Vec_PtrForEachEntry( Ivy_Obj_t *, p->vFaninsCur, pFanin, i ) Ivy_ObjRefsInc( Ivy_Regular(pFanin) ); // label MFFC with current ID Ivy_ManIncrementTravId( pMan ); nNodesSaved = Ivy_ObjMffcLabel( pMan, pNode ); // label fanouts with the current ID // Ivy_ObjForEachFanout( pMan, pNode, vFanout, pFanout, i ) // Ivy_ObjSetTravIdCurrent( pMan, pFanout ); // unmark the fanin boundary Vec_PtrForEachEntry( Ivy_Obj_t *, p->vFaninsCur, pFanin, i ) Ivy_ObjRefsDec( Ivy_Regular(pFanin) ); p->timeMffc += Abc_Clock() - clk2; // evaluate the cut clk2 = Abc_Clock(); pGraph = Rwt_CutEvaluateSeq( pMan, p, pNode, pCut, pPerm, p->vFaninsCur, nNodesSaved, &GainCur, uTruth ); p->timeEval += Abc_Clock() - clk2; // check if the cut is better than the current best one if ( pGraph != NULL && GainBest < GainCur ) { // save this form nNodesSaveCur = nNodesSaved; GainBest = GainCur; p->pGraph = pGraph; p->pCut = pCut; p->pPerm = pPerm; p->fCompl = ((uPhase & (1<<4)) > 0); uTruthBest = uTruth; // collect fanins in the Vec_PtrClear( p->vFanins ); Vec_PtrForEachEntry( Ivy_Obj_t *, p->vFaninsCur, pFanin, i ) Vec_PtrPush( p->vFanins, pFanin ); } } Vec_PtrFree( vFanout ); p->timeRes += Abc_Clock() - clk; if ( GainBest == -1 ) return -1; /* { Ivy_Cut_t * pCut = p->pCut; printf( "Node %5d. Using cut : {", Ivy_ObjId(pNode) ); for ( i = 0; i < pCut->nSize; i++ ) printf( " %d(%d)", Ivy_LeafId(pCut->pArray[i]), Ivy_LeafLat(pCut->pArray[i]) ); printf( " }\n" ); } */ //clk3 = Abc_Clock(); //nNewClauses = Ivy_CutTruthPrint( pMan, p->pCut, uTruth ); //timeInv += Abc_Clock() - clk; // nClauses += nNewClauses; // nMoves++; // if ( nNewClauses > 0 ) // nMovesS++; // copy the leaves Ivy_GraphPrepare( (Dec_Graph_t *)p->pGraph, (Ivy_Cut_t *)p->pCut, p->vFanins, p->pPerm ); p->nScores[p->pMap[uTruthBest]]++; p->nNodesGained += GainBest; if ( fUseZeroCost || GainBest > 0 ) p->nNodesRewritten++; /* if ( GainBest > 0 ) { Ivy_Cut_t * pCut = p->pCut; printf( "Node %5d. Using cut : {", Ivy_ObjId(pNode) ); for ( i = 0; i < pCut->nSize; i++ ) printf( " %5d(%2d)", Ivy_LeafId(pCut->pArray[i]), Ivy_LeafLat(pCut->pArray[i]) ); printf( " }\n" ); } */ // report the progress if ( fVeryVerbose && GainBest > 0 ) { printf( "Node %6d : ", Ivy_ObjId(pNode) ); printf( "Fanins = %d. ", p->vFanins->nSize ); printf( "Save = %d. ", nNodesSaveCur ); printf( "Add = %d. ", nNodesSaveCur-GainBest ); printf( "GAIN = %d. ", GainBest ); printf( "Cone = %d. ", p->pGraph? Dec_GraphNodeNum((Dec_Graph_t *)p->pGraph) : 0 ); printf( "Class = %d. ", p->pMap[uTruthBest] ); printf( "\n" ); } return GainBest; } /**Function************************************************************* Synopsis [Evaluates the cut.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Dec_Graph_t * Rwt_CutEvaluateSeq( Ivy_Man_t * pMan, Rwt_Man_t * p, Ivy_Obj_t * pRoot, Ivy_Cut_t * pCut, char * pPerm, Vec_Ptr_t * vFaninsCur, int nNodesSaved, int * pGainBest, unsigned uTruth ) { Vec_Ptr_t * vSubgraphs; Dec_Graph_t * pGraphBest = NULL; // Suppress "might be used uninitialized" Dec_Graph_t * pGraphCur; Rwt_Node_t * pNode; int nNodesAdded, GainBest, i; // find the matching class of subgraphs vSubgraphs = Vec_VecEntry( p->vClasses, p->pMap[uTruth] ); p->nSubgraphs += vSubgraphs->nSize; // determine the best subgraph GainBest = -1; Vec_PtrForEachEntry( Rwt_Node_t *, vSubgraphs, pNode, i ) { // get the current graph pGraphCur = (Dec_Graph_t *)pNode->pNext; // if ( pRoot->Id == 8648 ) // Dec_GraphPrint( stdout, pGraphCur, NULL, NULL ); // copy the leaves // Vec_PtrForEachEntry( Ivy_Obj_t *, vFaninsCur, pFanin, k ) // Dec_GraphNode(pGraphCur, k)->pFunc = pFanin; Ivy_GraphPrepare( pGraphCur, pCut, vFaninsCur, pPerm ); // detect how many unlabeled nodes will be reused nNodesAdded = Ivy_GraphToNetworkSeqCountSeq( pMan, pRoot, pGraphCur, nNodesSaved ); if ( nNodesAdded == -1 ) continue; assert( nNodesSaved >= nNodesAdded ); // count the gain at this node if ( GainBest < nNodesSaved - nNodesAdded ) { GainBest = nNodesSaved - nNodesAdded; pGraphBest = pGraphCur; } } if ( GainBest == -1 ) return NULL; *pGainBest = GainBest; return pGraphBest; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Ivy_GraphPrepare( Dec_Graph_t * pGraph, Ivy_Cut_t * pCut, Vec_Ptr_t * vFanins, char * pPerm ) { Dec_Node_t * pNode, * pNode0, * pNode1; int i; assert( Dec_GraphLeaveNum(pGraph) == pCut->nSize ); assert( Vec_PtrSize(vFanins) == pCut->nSize ); // label the leaves with latch numbers Dec_GraphForEachLeaf( pGraph, pNode, i ) { pNode->pFunc = Vec_PtrEntry( vFanins, i ); pNode->nLat2 = Ivy_LeafLat( pCut->pArray[(int)pPerm[i]] ); } // propagate latches through the nodes Dec_GraphForEachNode( pGraph, pNode, i ) { // get the children of this node pNode0 = Dec_GraphNode( pGraph, pNode->eEdge0.Node ); pNode1 = Dec_GraphNode( pGraph, pNode->eEdge1.Node ); // distribute the latches pNode->nLat2 = IVY_MIN( pNode0->nLat2, pNode1->nLat2 ); pNode->nLat0 = pNode0->nLat2 - pNode->nLat2; pNode->nLat1 = pNode1->nLat2 - pNode->nLat2; } } /**Function************************************************************* Synopsis [Counts the number of new nodes added when using this graph.] Description [AIG nodes for the fanins should be assigned to pNode->pFunc of the leaves of the graph before calling this procedure. Returns -1 if the number of nodes and levels exceeded the given limit or the number of levels exceeded the maximum allowed level.] SideEffects [] SeeAlso [] ***********************************************************************/ int Ivy_GraphToNetworkSeqCountSeq( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Dec_Graph_t * pGraph, int NodeMax ) { Dec_Node_t * pNode, * pNode0, * pNode1; Ivy_Obj_t * pAnd, * pAnd0, * pAnd1; int i, k, Counter, fCompl; // check for constant function or a literal if ( Dec_GraphIsConst(pGraph) || Dec_GraphIsVar(pGraph) ) return 0; // compute the AIG size after adding the internal nodes Counter = 0; Dec_GraphForEachNode( pGraph, pNode, i ) { // get the children of this node pNode0 = Dec_GraphNode( pGraph, pNode->eEdge0.Node ); pNode1 = Dec_GraphNode( pGraph, pNode->eEdge1.Node ); // get the AIG nodes corresponding to the children pAnd0 = (Ivy_Obj_t *)pNode0->pFunc; pAnd1 = (Ivy_Obj_t *)pNode1->pFunc; // skip the latches for ( k = 0; pAnd0 && k < (int)pNode->nLat0; k++ ) { fCompl = Ivy_IsComplement(pAnd0); pAnd0 = Ivy_TableLookup( p, Ivy_ObjCreateGhost(p, Ivy_Regular(pAnd0), NULL, IVY_LATCH, IVY_INIT_DC) ); if ( pAnd0 ) pAnd0 = Ivy_NotCond( pAnd0, fCompl ); } for ( k = 0; pAnd1 && k < (int)pNode->nLat1; k++ ) { fCompl = Ivy_IsComplement(pAnd1); pAnd1 = Ivy_TableLookup( p, Ivy_ObjCreateGhost(p, Ivy_Regular(pAnd1), NULL, IVY_LATCH, IVY_INIT_DC) ); if ( pAnd1 ) pAnd1 = Ivy_NotCond( pAnd1, fCompl ); } // get the new node if ( pAnd0 && pAnd1 ) { // if they are both present, find the resulting node pAnd0 = Ivy_NotCond( pAnd0, pNode->eEdge0.fCompl ); pAnd1 = Ivy_NotCond( pAnd1, pNode->eEdge1.fCompl ); assert( !Ivy_ObjIsLatch(Ivy_Regular(pAnd0)) || !Ivy_ObjIsLatch(Ivy_Regular(pAnd1)) ); if ( Ivy_Regular(pAnd0) == Ivy_Regular(pAnd1) || Ivy_ObjIsConst1(Ivy_Regular(pAnd0)) || Ivy_ObjIsConst1(Ivy_Regular(pAnd1)) ) pAnd = Ivy_And( p, pAnd0, pAnd1 ); else pAnd = Ivy_TableLookup( p, Ivy_ObjCreateGhost(p, pAnd0, pAnd1, IVY_AND, IVY_INIT_NONE) ); // return -1 if the node is the same as the original root if ( Ivy_Regular(pAnd) == pRoot ) return -1; } else pAnd = NULL; // count the number of added nodes if ( pAnd == NULL || Ivy_ObjIsTravIdCurrent(p, Ivy_Regular(pAnd)) ) { if ( ++Counter > NodeMax ) return -1; } pNode->pFunc = pAnd; } return Counter; } /**Function************************************************************* Synopsis [Transforms the decomposition graph into the AIG.] Description [AIG nodes for the fanins should be assigned to pNode->pFunc of the leaves of the graph before calling this procedure.] SideEffects [] SeeAlso [] ***********************************************************************/ Ivy_Obj_t * Ivy_GraphToNetworkSeq( Ivy_Man_t * p, Dec_Graph_t * pGraph ) { Ivy_Obj_t * pAnd0, * pAnd1; Dec_Node_t * pNode = NULL; // Suppress "might be used uninitialized" int i, k; // check for constant function if ( Dec_GraphIsConst(pGraph) ) return Ivy_NotCond( Ivy_ManConst1(p), Dec_GraphIsComplement(pGraph) ); // check for a literal if ( Dec_GraphIsVar(pGraph) ) { // get the variable node pNode = Dec_GraphVar(pGraph); // add the remaining latches for ( k = 0; k < (int)pNode->nLat2; k++ ) pNode->pFunc = Ivy_Latch( p, (Ivy_Obj_t *)pNode->pFunc, IVY_INIT_DC ); return Ivy_NotCond( (Ivy_Obj_t *)pNode->pFunc, Dec_GraphIsComplement(pGraph) ); } // build the AIG nodes corresponding to the AND gates of the graph Dec_GraphForEachNode( pGraph, pNode, i ) { pAnd0 = Ivy_NotCond( (Ivy_Obj_t *)Dec_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc, pNode->eEdge0.fCompl ); pAnd1 = Ivy_NotCond( (Ivy_Obj_t *)Dec_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc, pNode->eEdge1.fCompl ); // add the latches for ( k = 0; k < (int)pNode->nLat0; k++ ) pAnd0 = Ivy_Latch( p, pAnd0, IVY_INIT_DC ); for ( k = 0; k < (int)pNode->nLat1; k++ ) pAnd1 = Ivy_Latch( p, pAnd1, IVY_INIT_DC ); // create the node pNode->pFunc = Ivy_And( p, pAnd0, pAnd1 ); } // add the remaining latches for ( k = 0; k < (int)pNode->nLat2; k++ ) pNode->pFunc = Ivy_Latch( p, (Ivy_Obj_t *)pNode->pFunc, IVY_INIT_DC ); // complement the result if necessary return Ivy_NotCond( (Ivy_Obj_t *)pNode->pFunc, Dec_GraphIsComplement(pGraph) ); } /**Function************************************************************* Synopsis [Replaces MFFC of the node by the new factored form.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Ivy_GraphUpdateNetworkSeq( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Dec_Graph_t * pGraph, int nGain ) { Ivy_Obj_t * pRootNew; int nNodesNew, nNodesOld; nNodesOld = Ivy_ManNodeNum(p); // create the new structure of nodes pRootNew = Ivy_GraphToNetworkSeq( p, pGraph ); Ivy_ObjReplace( p, pRoot, pRootNew, 1, 0, 0 ); // compare the gains nNodesNew = Ivy_ManNodeNum(p); assert( nGain <= nNodesOld - nNodesNew ); // propagate the buffer Ivy_ManPropagateBuffers( p, 0 ); } /**Function************************************************************* Synopsis [Computes the truth table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ unsigned Ivy_CutGetTruth_rec( Ivy_Man_t * p, int Leaf, int * pNums, int nNums ) { static unsigned uMasks[5] = { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 }; unsigned uTruth0, uTruth1; Ivy_Obj_t * pObj; int i; for ( i = 0; i < nNums; i++ ) if ( Leaf == pNums[i] ) return uMasks[i]; pObj = Ivy_ManObj( p, Ivy_LeafId(Leaf) ); if ( Ivy_ObjIsLatch(pObj) ) { assert( !Ivy_ObjFaninC0(pObj) ); Leaf = Ivy_LeafCreate( Ivy_ObjFaninId0(pObj), Ivy_LeafLat(Leaf) + 1 ); return Ivy_CutGetTruth_rec( p, Leaf, pNums, nNums ); } assert( Ivy_ObjIsNode(pObj) || Ivy_ObjIsBuf(pObj) ); Leaf = Ivy_LeafCreate( Ivy_ObjFaninId0(pObj), Ivy_LeafLat(Leaf) ); uTruth0 = Ivy_CutGetTruth_rec( p, Leaf, pNums, nNums ); if ( Ivy_ObjFaninC0(pObj) ) uTruth0 = ~uTruth0; if ( Ivy_ObjIsBuf(pObj) ) return uTruth0; Leaf = Ivy_LeafCreate( Ivy_ObjFaninId1(pObj), Ivy_LeafLat(Leaf) ); uTruth1 = Ivy_CutGetTruth_rec( p, Leaf, pNums, nNums ); if ( Ivy_ObjFaninC1(pObj) ) uTruth1 = ~uTruth1; return uTruth0 & uTruth1; } /**Function************************************************************* Synopsis [Computes the truth table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ unsigned Ivy_CutGetTruth( Ivy_Man_t * p, Ivy_Obj_t * pObj, int * pNums, int nNums ) { assert( Ivy_ObjIsNode(pObj) ); assert( nNums < 6 ); return Ivy_CutGetTruth_rec( p, Ivy_LeafCreate(pObj->Id, 0), pNums, nNums ); } /**Function************************************************************* Synopsis [Returns 1 if the cut can be constructed; 0 otherwise.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Ivy_CutPrescreen( Ivy_Cut_t * pCut, int Id0, int Id1 ) { int i; if ( pCut->nSize < pCut->nSizeMax ) return 1; for ( i = 0; i < pCut->nSize; i++ ) if ( pCut->pArray[i] == Id0 || pCut->pArray[i] == Id1 ) return 1; return 0; } /**Function************************************************************* Synopsis [Derives new cut.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Ivy_CutDeriveNew2( Ivy_Cut_t * pCut, Ivy_Cut_t * pCutNew, int IdOld, int IdNew0, int IdNew1 ) { unsigned uHash = 0; int i, k; assert( pCut->nSize > 0 ); assert( IdNew0 < IdNew1 ); for ( i = k = 0; i < pCut->nSize; i++ ) { if ( pCut->pArray[i] == IdOld ) continue; if ( IdNew0 >= 0 ) { if ( IdNew0 <= pCut->pArray[i] ) { if ( IdNew0 < pCut->pArray[i] ) { if ( k == pCut->nSizeMax ) return 0; pCutNew->pArray[ k++ ] = IdNew0; uHash |= Ivy_CutHashValue( IdNew0 ); } IdNew0 = -1; } } if ( IdNew1 >= 0 ) { if ( IdNew1 <= pCut->pArray[i] ) { if ( IdNew1 < pCut->pArray[i] ) { if ( k == pCut->nSizeMax ) return 0; pCutNew->pArray[ k++ ] = IdNew1; uHash |= Ivy_CutHashValue( IdNew1 ); } IdNew1 = -1; } } if ( k == pCut->nSizeMax ) return 0; pCutNew->pArray[ k++ ] = pCut->pArray[i]; uHash |= Ivy_CutHashValue( pCut->pArray[i] ); } if ( IdNew0 >= 0 ) { if ( k == pCut->nSizeMax ) return 0; pCutNew->pArray[ k++ ] = IdNew0; uHash |= Ivy_CutHashValue( IdNew0 ); } if ( IdNew1 >= 0 ) { if ( k == pCut->nSizeMax ) return 0; pCutNew->pArray[ k++ ] = IdNew1; uHash |= Ivy_CutHashValue( IdNew1 ); } pCutNew->nSize = k; pCutNew->uHash = uHash; assert( pCutNew->nSize <= pCut->nSizeMax ); for ( i = 1; i < pCutNew->nSize; i++ ) assert( pCutNew->pArray[i-1] < pCutNew->pArray[i] ); return 1; } /**Function************************************************************* Synopsis [Derives new cut.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Ivy_CutDeriveNew( Ivy_Cut_t * pCut, Ivy_Cut_t * pCutNew, int IdOld, int IdNew0, int IdNew1 ) { unsigned uHash = 0; int i, k; assert( pCut->nSize > 0 ); assert( IdNew0 < IdNew1 ); for ( i = k = 0; i < pCut->nSize; i++ ) { if ( pCut->pArray[i] == IdOld ) continue; if ( IdNew0 <= pCut->pArray[i] ) { if ( IdNew0 < pCut->pArray[i] ) { pCutNew->pArray[ k++ ] = IdNew0; uHash |= Ivy_CutHashValue( IdNew0 ); } IdNew0 = 0x7FFFFFFF; } if ( IdNew1 <= pCut->pArray[i] ) { if ( IdNew1 < pCut->pArray[i] ) { pCutNew->pArray[ k++ ] = IdNew1; uHash |= Ivy_CutHashValue( IdNew1 ); } IdNew1 = 0x7FFFFFFF; } pCutNew->pArray[ k++ ] = pCut->pArray[i]; uHash |= Ivy_CutHashValue( pCut->pArray[i] ); } if ( IdNew0 < 0x7FFFFFFF ) { pCutNew->pArray[ k++ ] = IdNew0; uHash |= Ivy_CutHashValue( IdNew0 ); } if ( IdNew1 < 0x7FFFFFFF ) { pCutNew->pArray[ k++ ] = IdNew1; uHash |= Ivy_CutHashValue( IdNew1 ); } pCutNew->nSize = k; pCutNew->uHash = uHash; assert( pCutNew->nSize <= pCut->nSizeMax ); // for ( i = 1; i < pCutNew->nSize; i++ ) // assert( pCutNew->pArray[i-1] < pCutNew->pArray[i] ); return 1; } /**Function************************************************************* Synopsis [Find the hash value of the cut.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline unsigned Ivy_NodeCutHash( Ivy_Cut_t * pCut ) { int i; pCut->uHash = 0; for ( i = 0; i < pCut->nSize; i++ ) pCut->uHash |= (1 << (pCut->pArray[i] % 31)); return pCut->uHash; } /**Function************************************************************* Synopsis [Derives new cut.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Ivy_CutDeriveNew3( Ivy_Cut_t * pCut, Ivy_Cut_t * pCutNew, int IdOld, int IdNew0, int IdNew1 ) { int i, k; assert( pCut->nSize > 0 ); assert( IdNew0 < IdNew1 ); for ( i = k = 0; i < pCut->nSize; i++ ) { if ( pCut->pArray[i] == IdOld ) continue; if ( IdNew0 <= pCut->pArray[i] ) { if ( IdNew0 < pCut->pArray[i] ) pCutNew->pArray[ k++ ] = IdNew0; IdNew0 = 0x7FFFFFFF; } if ( IdNew1 <= pCut->pArray[i] ) { if ( IdNew1 < pCut->pArray[i] ) pCutNew->pArray[ k++ ] = IdNew1; IdNew1 = 0x7FFFFFFF; } pCutNew->pArray[ k++ ] = pCut->pArray[i]; } if ( IdNew0 < 0x7FFFFFFF ) pCutNew->pArray[ k++ ] = IdNew0; if ( IdNew1 < 0x7FFFFFFF ) pCutNew->pArray[ k++ ] = IdNew1; pCutNew->nSize = k; assert( pCutNew->nSize <= pCut->nSizeMax ); Ivy_NodeCutHash( pCutNew ); return 1; } /**Function************************************************************* Synopsis [Returns 1 if pDom is contained in pCut.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Ivy_CutCheckDominance( Ivy_Cut_t * pDom, Ivy_Cut_t * pCut ) { int i, k; for ( i = 0; i < pDom->nSize; i++ ) { assert( i==0 || pDom->pArray[i-1] < pDom->pArray[i] ); for ( k = 0; k < pCut->nSize; k++ ) if ( pDom->pArray[i] == pCut->pArray[k] ) break; if ( k == pCut->nSize ) // node i in pDom is not contained in pCut return 0; } // every node in pDom is contained in pCut return 1; } /**Function************************************************************* Synopsis [Check if the cut exists.] Description [Returns 1 if the cut exists.] SideEffects [] SeeAlso [] ***********************************************************************/ int Ivy_CutFindOrAddFilter( Ivy_Store_t * pCutStore, Ivy_Cut_t * pCutNew ) { Ivy_Cut_t * pCut; int i, k; assert( pCutNew->uHash ); // try to find the cut for ( i = 0; i < pCutStore->nCuts; i++ ) { pCut = pCutStore->pCuts + i; if ( pCut->nSize == 0 ) continue; if ( pCut->nSize == pCutNew->nSize ) { if ( pCut->uHash == pCutNew->uHash ) { for ( k = 0; k < pCutNew->nSize; k++ ) if ( pCut->pArray[k] != pCutNew->pArray[k] ) break; if ( k == pCutNew->nSize ) return 1; } continue; } if ( pCut->nSize < pCutNew->nSize ) { // skip the non-contained cuts if ( (pCut->uHash & pCutNew->uHash) != pCut->uHash ) continue; // check containment seriously if ( Ivy_CutCheckDominance( pCut, pCutNew ) ) return 1; continue; } // check potential containment of other cut // skip the non-contained cuts if ( (pCut->uHash & pCutNew->uHash) != pCutNew->uHash ) continue; // check containment seriously if ( Ivy_CutCheckDominance( pCutNew, pCut ) ) { // remove the current cut pCut->nSize = 0; } } assert( pCutStore->nCuts < pCutStore->nCutsMax ); // add the cut pCut = pCutStore->pCuts + pCutStore->nCuts++; *pCut = *pCutNew; return 0; } /**Function************************************************************* Synopsis [Compresses the cut representation.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Ivy_CutCompactAll( Ivy_Store_t * pCutStore ) { Ivy_Cut_t * pCut; int i, k; pCutStore->nCutsM = 0; for ( i = k = 0; i < pCutStore->nCuts; i++ ) { pCut = pCutStore->pCuts + i; if ( pCut->nSize == 0 ) continue; if ( pCut->nSize < pCut->nSizeMax ) pCutStore->nCutsM++; pCutStore->pCuts[k++] = *pCut; } pCutStore->nCuts = k; } /**Function************************************************************* Synopsis [Print the cut.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Ivy_CutPrintForNode( Ivy_Cut_t * pCut ) { int i; assert( pCut->nSize > 0 ); printf( "%d : {", pCut->nSize ); for ( i = 0; i < pCut->nSize; i++ ) printf( " %d", pCut->pArray[i] ); printf( " }\n" ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Ivy_CutPrintForNodes( Ivy_Store_t * pCutStore ) { int i; printf( "Node %d\n", pCutStore->pCuts[0].pArray[0] ); for ( i = 0; i < pCutStore->nCuts; i++ ) Ivy_CutPrintForNode( pCutStore->pCuts + i ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Ivy_CutReadLeaf( Ivy_Obj_t * pFanin ) { int nLats, iLeaf; assert( !Ivy_IsComplement(pFanin) ); if ( !Ivy_ObjIsLatch(pFanin) ) return Ivy_LeafCreate( pFanin->Id, 0 ); iLeaf = Ivy_CutReadLeaf(Ivy_ObjFanin0(pFanin)); nLats = Ivy_LeafLat(iLeaf); assert( nLats < IVY_LEAF_MASK ); return 1 + iLeaf; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Ivy_Store_t * Ivy_CutComputeForNode( Ivy_Man_t * p, Ivy_Obj_t * pObj, int nLeaves ) { static Ivy_Store_t CutStore, * pCutStore = &CutStore; Ivy_Cut_t CutNew, * pCutNew = &CutNew, * pCut; Ivy_Obj_t * pLeaf; int i, k, Temp, nLats, iLeaf0, iLeaf1; assert( nLeaves <= IVY_CUT_INPUT ); // start the structure pCutStore->nCuts = 0; pCutStore->nCutsMax = IVY_CUT_LIMIT; // start the trivial cut pCutNew->uHash = 0; pCutNew->nSize = 1; pCutNew->nSizeMax = nLeaves; pCutNew->pArray[0] = Ivy_LeafCreate( pObj->Id, 0 ); pCutNew->uHash = Ivy_CutHashValue( pCutNew->pArray[0] ); // add the trivial cut pCutStore->pCuts[pCutStore->nCuts++] = *pCutNew; assert( pCutStore->nCuts == 1 ); // explore the cuts for ( i = 0; i < pCutStore->nCuts; i++ ) { // expand this cut pCut = pCutStore->pCuts + i; if ( pCut->nSize == 0 ) continue; for ( k = 0; k < pCut->nSize; k++ ) { pLeaf = Ivy_ManObj( p, Ivy_LeafId(pCut->pArray[k]) ); if ( Ivy_ObjIsCi(pLeaf) || Ivy_ObjIsConst1(pLeaf) ) continue; assert( Ivy_ObjIsNode(pLeaf) ); nLats = Ivy_LeafLat(pCut->pArray[k]); // get the fanins fanins iLeaf0 = Ivy_CutReadLeaf( Ivy_ObjFanin0(pLeaf) ); iLeaf1 = Ivy_CutReadLeaf( Ivy_ObjFanin1(pLeaf) ); assert( nLats + Ivy_LeafLat(iLeaf0) < IVY_LEAF_MASK && nLats + Ivy_LeafLat(iLeaf1) < IVY_LEAF_MASK ); iLeaf0 = nLats + iLeaf0; iLeaf1 = nLats + iLeaf1; if ( !Ivy_CutPrescreen( pCut, iLeaf0, iLeaf1 ) ) continue; // the given cut exist if ( iLeaf0 > iLeaf1 ) Temp = iLeaf0, iLeaf0 = iLeaf1, iLeaf1 = Temp; // create the new cut if ( !Ivy_CutDeriveNew( pCut, pCutNew, pCut->pArray[k], iLeaf0, iLeaf1 ) ) continue; // add the cut Ivy_CutFindOrAddFilter( pCutStore, pCutNew ); if ( pCutStore->nCuts == IVY_CUT_LIMIT ) break; } if ( pCutStore->nCuts == IVY_CUT_LIMIT ) break; } if ( pCutStore->nCuts == IVY_CUT_LIMIT ) pCutStore->fSatur = 1; else pCutStore->fSatur = 0; // printf( "%d ", pCutStore->nCuts ); Ivy_CutCompactAll( pCutStore ); // printf( "%d \n", pCutStore->nCuts ); // Ivy_CutPrintForNodes( pCutStore ); return pCutStore; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Ivy_CutComputeAll( Ivy_Man_t * p, int nInputs ) { Ivy_Store_t * pStore; Ivy_Obj_t * pObj; int i, nCutsTotal, nCutsTotalM, nNodeTotal, nNodeOver; abctime clk = Abc_Clock(); if ( nInputs > IVY_CUT_INPUT ) { printf( "Cannot compute cuts for more than %d inputs.\n", IVY_CUT_INPUT ); return; } nNodeTotal = nNodeOver = 0; nCutsTotal = nCutsTotalM = -Ivy_ManNodeNum(p); Ivy_ManForEachObj( p, pObj, i ) { if ( !Ivy_ObjIsNode(pObj) ) continue; pStore = Ivy_CutComputeForNode( p, pObj, nInputs ); nCutsTotal += pStore->nCuts; nCutsTotalM += pStore->nCutsM; nNodeOver += pStore->fSatur; nNodeTotal++; } printf( "All = %6d. Minus = %6d. Triv = %6d. Node = %6d. Satur = %6d. ", nCutsTotal, nCutsTotalM, Ivy_ManPiNum(p) + Ivy_ManNodeNum(p), nNodeTotal, nNodeOver ); ABC_PRT( "Time", Abc_Clock() - clk ); } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END