Version abc60614

2 files changed, 476 insertions, 0 deletions

diff --git a/src/temp/ivy/ivyCut.c b/src/temp/ivy/ivyCut.c
index a8fd148b..57720e17 100644
--- a/src/temp/ivy/ivyCut.c
+++ b/src/temp/ivy/ivyCut.c
@@ -198,6 +198,481 @@ void Ivy_ManSeqFindCut( Ivy_Obj_t * pRoot, Vec_Int_t * vFront, Vec_Int_t * vInsi
     assert( Vec_IntSize(vFront) <= nSize );
 }
 
+
+
+/**Function*************************************************************
+
+  Synopsis    [Comparison for node pointers.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Ivy_ManFindAlgCutCompare( Ivy_Obj_t ** pp1, Ivy_Obj_t ** pp2 )
+{
+    if ( *pp1 < *pp2 )
+        return -1;
+    if ( *pp1 > *pp2 )
+        return 1;
+    return 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Computing one algebraic cut.]
+
+  Description [Returns 1 if the tree-leaves of this node where traversed 
+  and found to have no external references (and have not been collected). 
+  Returns 0 if the tree-leaves have external references and are collected.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Ivy_ManFindAlgCut_rec( Ivy_Obj_t * pRoot, Ivy_Type_t Type, Vec_Ptr_t * vFront )
+{
+    int RetValue0, RetValue1;
+    Ivy_Obj_t * pRootR = Ivy_Regular(pRoot);
+    assert( Type != IVY_EXOR || !Ivy_IsComplement(pRoot) );
+    // if the node is a buffer skip through it
+    if ( Ivy_ObjIsBuf(pRootR) )
+        return Ivy_ManFindAlgCut_rec( Ivy_NotCond(Ivy_ObjChild0(pRootR), Ivy_IsComplement(pRoot)), Type, vFront );
+    // if the node is the end of the tree, return
+    if ( Ivy_IsComplement(pRoot) || Ivy_ObjIsCi(pRoot) || Ivy_ObjType(pRoot) != Type )
+    {
+        if ( Ivy_ObjRefs(pRootR) == 1 )
+            return 1;
+        assert( Ivy_ObjRefs(pRootR) > 1 );
+        Vec_PtrPush( vFront, pRoot );
+        return 0;
+    }
+    // branch on the node
+    assert( Ivy_ObjIsNode(pRoot) );
+    RetValue0 = Ivy_ManFindAlgCut_rec( Ivy_ObjChild0(pRoot), Type, vFront );
+    RetValue1 = Ivy_ManFindAlgCut_rec( Ivy_ObjChild1(pRoot), Type, vFront );
+    // the case when both have no external referenced
+    if ( RetValue0 && RetValue1 )
+    {
+        if ( Ivy_ObjRefs(pRoot) == 1 )
+            return 1;
+        assert( Ivy_ObjRefs(pRoot) > 1 );
+        Vec_PtrPush( vFront, pRoot );
+        return 0;
+    }
+    // the case when one of them has external references
+    if ( RetValue0 )
+        Vec_PtrPush( vFront, Ivy_ObjChild0(pRoot) );
+    if ( RetValue1 )
+        Vec_PtrPush( vFront, Ivy_ObjChild1(pRoot) );
+    return 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Computing one algebraic cut.]
+
+  Description [Algebraic cut stops when we hit (a) CI, (b) complemented edge,
+  (c) boundary of different gates. Returns 1 if this is a pure tree.
+  Returns -1 if the contant 0 is detected. Return 0 if the array can be used.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Ivy_ManFindAlgCut( Ivy_Obj_t * pRoot, Vec_Ptr_t * vFront )
+{
+    Ivy_Obj_t * pObj, * pPrev;
+    int RetValue, i, k;
+    assert( !Ivy_IsComplement(pRoot) );
+    // clear the frontier and collect the nodes
+    Vec_PtrClear( vFront );
+    RetValue = Ivy_ManFindAlgCut_rec( pRoot, Ivy_ObjType(pRoot), vFront );
+    // return if the node is the root of a tree
+    if ( RetValue == 1 )
+        return 1;
+    // sort the entries to in increasing order
+    Vec_PtrSort( vFront, Ivy_ManFindAlgCutCompare );
+    // remove duplicated
+    k = 1;
+    Vec_PtrForEachEntryStart( vFront, pObj, i, 1 )
+    {
+        pPrev = (k == 0 ? NULL : Vec_PtrEntry(vFront, k-1));
+        if ( pObj == pPrev )
+        {
+            if ( Ivy_ObjIsExor(pRoot) )
+                k--;
+            continue;
+        }
+        if ( pObj == Ivy_Not(pPrev) )
+            return -1;
+        Vec_PtrWriteEntry( vFront, k++, pObj );
+    }
+    if ( k == 0 )
+        return -1;
+    Vec_PtrShrink( vFront, k );
+    return 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Ivy_ManTestCutsAlg( Ivy_Man_t * p )
+{
+    Vec_Ptr_t * vFront;
+    Ivy_Obj_t * pObj, * pTemp;
+    int i, k, RetValue;
+    vFront = Vec_PtrAlloc( 100 );
+    Ivy_ManForEachObj( p, pObj, i )
+    {
+        if ( !Ivy_ObjIsNode(pObj) )
+            continue;
+        if ( Ivy_ObjIsMuxType(pObj) )
+        {
+            printf( "m " );
+            continue;
+        }
+        if ( pObj->Id == 509 )
+        {
+            int y = 0;
+        }
+
+        RetValue = Ivy_ManFindAlgCut( pObj, vFront );
+        if ( Ivy_ObjIsExor(pObj) )
+            printf( "x" );
+        if ( RetValue == -1 )
+            printf( "Const0 " );
+        else if ( RetValue == 1 || Vec_PtrSize(vFront) <= 2 )
+            printf( ". " );
+        else
+            printf( "%d ", Vec_PtrSize(vFront) );
+        
+        printf( "( " );
+        Vec_PtrForEachEntry( vFront, pTemp, k )
+            printf( "%d ", Ivy_ObjRefs(Ivy_Regular(pTemp)) );
+        printf( ")\n" );
+
+        if ( Vec_PtrSize(vFront) == 5 )
+        {
+            int x = 0;
+        }
+    }
+    printf( "\n" );
+    Vec_PtrFree( vFront );
+}
+
+
+
+
+/**Function*************************************************************
+
+  Synopsis    [Computing Boolean cut.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Ivy_ManFindBoolCut_rec( Ivy_Obj_t * pObj, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVolume, Ivy_Obj_t * pPivot )
+{
+    int RetValue0, RetValue1;
+    if ( pObj == pPivot )
+    {
+        Vec_PtrPushUnique( vLeaves, pObj );
+        Vec_PtrPushUnique( vVolume, pObj );
+        return 1;        
+    }
+    if ( pObj->fMarkA )
+        return 0;
+
+//    assert( !Ivy_ObjIsCi(pObj) );
+    if ( Ivy_ObjIsCi(pObj) )
+        return 0;
+
+    if ( Ivy_ObjIsBuf(pObj) )
+    {
+        RetValue0 = Ivy_ManFindBoolCut_rec( Ivy_ObjFanin0(pObj), vLeaves, vVolume, pPivot );
+        if ( !RetValue0 )
+            return 0;
+        Vec_PtrPushUnique( vVolume, pObj );
+        return 1;
+    }
+    assert( Ivy_ObjIsNode(pObj) );
+    RetValue0 = Ivy_ManFindBoolCut_rec( Ivy_ObjFanin0(pObj), vLeaves, vVolume, pPivot );
+    RetValue1 = Ivy_ManFindBoolCut_rec( Ivy_ObjFanin1(pObj), vLeaves, vVolume, pPivot );
+    if ( !RetValue0 && !RetValue1 )
+        return 0;
+    // add new leaves
+    if ( !RetValue0 )
+    {
+        Vec_PtrPushUnique( vLeaves, Ivy_ObjFanin0(pObj) );
+        Vec_PtrPushUnique( vVolume, Ivy_ObjFanin0(pObj) );
+    }
+    if ( !RetValue1 )
+    {
+        Vec_PtrPushUnique( vLeaves, Ivy_ObjFanin1(pObj) );
+        Vec_PtrPushUnique( vVolume, Ivy_ObjFanin1(pObj) );
+    }
+    Vec_PtrPushUnique( vVolume, pObj );
+    return 1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Returns the cost of one node (how many new nodes are added.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Ivy_ManFindBoolCutCost( Ivy_Obj_t * pObj )
+{
+    int Cost;
+    // make sure the node is in the construction zone
+    assert( pObj->fMarkA == 1 );  
+    // cannot expand over the PI node
+    if ( Ivy_ObjIsCi(pObj) )
+        return 999;
+    // always expand over the buffer
+    if ( Ivy_ObjIsBuf(pObj) )
+        return !Ivy_ObjFanin0(pObj)->fMarkA;
+    // get the cost of the cone
+    Cost = (!Ivy_ObjFanin0(pObj)->fMarkA) + (!Ivy_ObjFanin1(pObj)->fMarkA);
+    // return the number of nodes to be added to the leaves if this node is removed
+    return Cost;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Computing Boolean cut.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Ivy_ManFindBoolCut( Ivy_Obj_t * pRoot, Vec_Ptr_t * vFront, Vec_Ptr_t * vVolume, Vec_Ptr_t * vLeaves )
+{
+    Ivy_Obj_t * pObj, * pFaninC, * pFanin0, * pFanin1, * pPivot;
+    int RetValue, LevelLimit, Lev, k;
+    assert( !Ivy_IsComplement(pRoot) );
+    // clear the frontier and collect the nodes
+    Vec_PtrClear( vFront );
+    Vec_PtrClear( vVolume );
+    if ( Ivy_ObjIsMuxType(pRoot) )
+        pFaninC = Ivy_ObjRecognizeMux( pRoot, &pFanin0, &pFanin1 );
+    else
+    {
+        pFaninC = NULL;
+        pFanin0 = Ivy_ObjFanin0(pRoot);
+        pFanin1 = Ivy_ObjFanin1(pRoot); 
+    }
+    // start cone A
+    pFanin0->fMarkA = 1;
+    Vec_PtrPush( vFront, pFanin0 );
+    Vec_PtrPush( vVolume, pFanin0 );
+    // start cone B
+    pFanin1->fMarkB = 1;
+    Vec_PtrPush( vFront, pFanin1 );
+    Vec_PtrPush( vVolume, pFanin1 );
+    // iteratively expand until the common node (pPivot) is found or limit is reached
+    assert( Ivy_ObjLevel(pRoot) == Ivy_ObjLevelNew(pRoot) );
+    pPivot = NULL;
+    LevelLimit = IVY_MAX( Ivy_ObjLevel(pRoot) - 10, 1 );
+    for ( Lev = Ivy_ObjLevel(pRoot) - 1; Lev >= LevelLimit; Lev-- )
+    {
+        while ( 1 )
+        {
+            // find the next node to expand on this level
+            Vec_PtrForEachEntry( vFront, pObj, k )
+                if ( (int)pObj->Level == Lev )
+                    break;
+            if ( k == Vec_PtrSize(vFront) )
+                break;
+            assert( (int)pObj->Level <= Lev );
+            assert( pObj->fMarkA ^ pObj->fMarkB );
+            // remove the old node
+            Vec_PtrRemove( vFront, pObj );
+
+            // expand this node
+            pFanin0 = Ivy_ObjFanin0(pObj);
+            if ( !pFanin0->fMarkA && !pFanin0->fMarkB )
+            {
+                Vec_PtrPush( vFront, pFanin0 );
+                Vec_PtrPush( vVolume, pFanin0 );
+            }
+            // mark the new nodes
+            if ( pObj->fMarkA )
+                pFanin0->fMarkA = 1; 
+            if ( pObj->fMarkB )
+                pFanin0->fMarkB = 1; 
+
+            if ( Ivy_ObjIsBuf(pObj) )
+            {
+                if ( pFanin0->fMarkA && pFanin0->fMarkB )
+                {
+                    pPivot = pFanin0;
+                    break;
+                }
+                continue;
+            }
+
+            // expand this node
+            pFanin1 = Ivy_ObjFanin1(pObj); 
+            if ( !pFanin1->fMarkA && !pFanin1->fMarkB )
+            {
+                Vec_PtrPush( vFront, pFanin1 );
+                Vec_PtrPush( vVolume, pFanin1 );
+            }
+            // mark the new nodes
+            if ( pObj->fMarkA )
+                pFanin1->fMarkA = 1; 
+            if ( pObj->fMarkB )
+                pFanin1->fMarkB = 1; 
+
+            // consider if it is time to quit
+            if ( pFanin0->fMarkA && pFanin0->fMarkB )
+            {
+                pPivot = pFanin0;
+                break;
+            }
+            if ( pFanin1->fMarkA && pFanin1->fMarkB )
+            {
+                pPivot = pFanin1;
+                break;
+            }
+        }
+        if ( pPivot != NULL )
+            break;
+    }
+    if ( pPivot == NULL )
+        return 0;
+    // if the MUX control is defined, it should not be
+    if ( pFaninC && !pFaninC->fMarkA && !pFaninC->fMarkB )
+        Vec_PtrPush( vFront, pFaninC );
+    // clean the markings
+    Vec_PtrForEachEntry( vVolume, pObj, k )
+        pObj->fMarkA = pObj->fMarkB = 0;
+
+    // mark the nodes on the frontier (including the pivot)
+    Vec_PtrForEachEntry( vFront, pObj, k )
+        pObj->fMarkA = 1;
+    // cut exists, collect all the nodes on the shortest path to the pivot
+    Vec_PtrClear( vLeaves );
+    Vec_PtrClear( vVolume );
+    RetValue = Ivy_ManFindBoolCut_rec( pRoot, vLeaves, vVolume, pPivot );
+    assert( RetValue == 1 );
+    // unmark the nodes on the frontier (including the pivot)
+    Vec_PtrForEachEntry( vFront, pObj, k )
+        pObj->fMarkA = 0;
+
+    // mark the nodes in the volume
+    Vec_PtrForEachEntry( vVolume, pObj, k )
+        pObj->fMarkA = 1;
+    // expand the cut without increasing its size
+    while ( 1 )
+    {
+        Vec_PtrForEachEntry( vLeaves, pObj, k )
+            if ( Ivy_ManFindBoolCutCost(pObj) < 2 )
+                break;
+        if ( k == Vec_PtrSize(vLeaves) )
+            break;
+        // the node can be expanded
+        // remove the old node
+        Vec_PtrRemove( vLeaves, pObj );
+        // expand this node
+        pFanin0 = Ivy_ObjFanin0(pObj);
+        if ( !pFanin0->fMarkA )
+        {
+            pFanin0->fMarkA = 1;
+            Vec_PtrPush( vVolume, pFanin0 );
+            Vec_PtrPush( vLeaves, pFanin0 );
+        }
+        if ( Ivy_ObjIsBuf(pObj) )
+            continue;
+        // expand this node
+        pFanin1 = Ivy_ObjFanin1(pObj);
+        if ( !pFanin1->fMarkA )
+        {
+            pFanin1->fMarkA = 1;
+            Vec_PtrPush( vVolume, pFanin1 );
+            Vec_PtrPush( vLeaves, pFanin1 );
+        }        
+    }
+    // unmark the nodes in the volume
+    Vec_PtrForEachEntry( vVolume, pObj, k )
+        pObj->fMarkA = 0;
+    return 1;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Ivy_ManTestCutsBool( Ivy_Man_t * p )
+{
+    Vec_Ptr_t * vFront, * vVolume, * vLeaves;
+    Ivy_Obj_t * pObj, * pTemp;
+    int i, k, RetValue;
+    vFront = Vec_PtrAlloc( 100 );
+    vVolume = Vec_PtrAlloc( 100 );
+    vLeaves = Vec_PtrAlloc( 100 );
+    Ivy_ManForEachObj( p, pObj, i )
+    {
+        if ( !Ivy_ObjIsNode(pObj) )
+            continue;
+        if ( Ivy_ObjIsMuxType(pObj) )
+        {
+            printf( "m" );
+            continue;
+        }
+        if ( Ivy_ObjIsExor(pObj) )
+            printf( "x" );
+        RetValue = Ivy_ManFindBoolCut( pObj, vFront, vVolume, vLeaves );
+        if ( RetValue == 0 )
+            printf( "- " );
+        else
+            printf( "%d ", Vec_PtrSize(vLeaves) );
+/*        
+        printf( "( " );
+        Vec_PtrForEachEntry( vFront, pTemp, k )
+            printf( "%d ", Ivy_ObjRefs(Ivy_Regular(pTemp)) );
+        printf( ")\n" );
+*/
+    }
+    printf( "\n" );
+    Vec_PtrFree( vFront );
+    Vec_PtrFree( vVolume );
+    Vec_PtrFree( vLeaves );
+}
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////
diff --git a/src/temp/ivy/module.make b/src/temp/ivy/module.make
index d59a3fa3..beadb8b9 100644
--- a/src/temp/ivy/module.make
+++ b/src/temp/ivy/module.make
@@ -5,6 +5,7 @@ SRC +=    src/temp/ivy/ivyBalance.c \
     src/temp/ivy/ivyDfs.c \
     src/temp/ivy/ivyDsd.c \
     src/temp/ivy/ivyMan.c \
+    src/temp/ivy/ivyMulti.c \
     src/temp/ivy/ivyObj.c \
     src/temp/ivy/ivyOper.c \
     src/temp/ivy/ivyRewrite.c \