Version abc80130_2

1 files changed, 1134 insertions, 0 deletions

diff --git a/src/aig/ivy/ivySeq.c b/src/aig/ivy/ivySeq.c
new file mode 100644
index 00000000..0ee29fee
--- /dev/null
+++ b/src/aig/ivy/ivySeq.c
@@ -0,0 +1,1134 @@
+/**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 "deco.h"
+#include "rwt.h"
+
+////////////////////////////////////////////////////////////////////////
+///                        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;
+    int clk, clkStart = 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 = Rwt_ManReadDecs(pManRwt);
+            int fCompl           = Rwt_ManReadCompl(pManRwt);
+            // complement the FF if needed
+clk = clock();
+            if ( fCompl ) Dec_GraphComplement( pGraph );
+            Ivy_GraphUpdateNetworkSeq( p, pNode, pGraph, nGain );
+            if ( fCompl ) Dec_GraphComplement( pGraph );
+Rwt_ManAddTimeUpdate( pManRwt, clock() - clk );
+        }
+    }
+Rwt_ManAddTimeTotal( pManRwt, 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, uTruthBest, uTruth;//, nNewClauses;
+    char * pPerm;
+    int nNodesSaved, nNodesSaveCur;
+    int i, c, GainCur, GainBest = -1;
+    int clk, clk2;//, clk3;
+
+    p->nNodesConsidered++;
+    // get the node's cuts
+clk = clock();
+    pStore = Ivy_CutComputeForNode( pMan, pNode, 5 );
+p->timeCut += clock() - clk;
+
+    // go through the cuts
+clk = 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 = clock();
+        uTruth = 0xFFFF & Ivy_CutGetTruth( pMan, pNode, pCut->pArray, pCut->nSize );  // truth table
+p->timeTruth += clock() - clk2;
+        pPerm = p->pPerms4[ 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[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 = clock();
+        // mark the fanin boundary 
+        Vec_PtrForEachEntry( 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( p->vFaninsCur, pFanin, i )
+            Ivy_ObjRefsDec( Ivy_Regular(pFanin) );
+p->timeMffc += clock() - clk2;
+
+        // evaluate the cut
+clk2 = clock();
+        pGraph = Rwt_CutEvaluateSeq( pMan, p, pNode, pCut, pPerm, p->vFaninsCur, nNodesSaved, &GainCur, uTruth );
+p->timeEval += 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( p->vFaninsCur, pFanin, i )
+                Vec_PtrPush( p->vFanins, pFanin );
+        }
+    }
+    Vec_PtrFree( vFanout );
+p->timeRes += 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 = clock();
+//nNewClauses = Ivy_CutTruthPrint( pMan, p->pCut, uTruth );
+//timeInv += clock() - clk;
+
+//    nClauses += nNewClauses;
+//    nMoves++;
+//    if ( nNewClauses > 0 )
+//        nMovesS++;
+
+    // copy the leaves
+    Ivy_GraphPrepare( p->pGraph, 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(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, * 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( 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( 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[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 = pNode0->pFunc; 
+        pAnd1 = 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;
+    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, pNode->pFunc, IVY_INIT_DC );
+        return Ivy_NotCond( 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( Dec_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc, pNode->eEdge0.fCompl ); 
+        pAnd1 = Ivy_NotCond( 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, pNode->pFunc, IVY_INIT_DC );
+    // complement the result if necessary
+    return Ivy_NotCond( 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_Man_t * pMan = p;
+    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;
+    int clk = 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 );
+    PRT( "Time", clock() - clk );
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+