| /**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 = -1, 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<<i)) > 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 |
| |
