ivyRwrAlg.c

Go to the documentation of this file.

/**CFile****************************************************************

  FileName    [ivyRwrAlg.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [And-Inverter Graph package.]

  Synopsis    [Algebraic AIG rewriting.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - May 11, 2006.]

  Revision    [$Id: ivyRwrAlg.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $]

***********************************************************************/

#include "ivy.h"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

static int Ivy_ManFindAlgCut( Ivy_Obj_t * pRoot, Vec_Ptr_t * vFront, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone );
static Ivy_Obj_t * Ivy_NodeRewriteAlg( Ivy_Obj_t * pObj, Vec_Ptr_t * vFront, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone, Vec_Ptr_t * vSols, int LevelR, int fUseZeroCost );
static int Ivy_NodeCountMffc( Ivy_Obj_t * pNode );

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    [Algebraic AIG rewriting.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ivy_ManRewriteAlg( Ivy_Man_t * p, int fUpdateLevel, int fUseZeroCost )
{
    Vec_Int_t * vRequired;
    Vec_Ptr_t * vFront, * vLeaves, * vCone, * vSol;
    Ivy_Obj_t * pObj, * pResult;
    int i, RetValue, LevelR, nNodesOld;
    int CountUsed, CountUndo;
    vRequired = fUpdateLevel? Ivy_ManRequiredLevels( p ) : NULL;
    vFront    = Vec_PtrAlloc( 100 );
    vLeaves   = Vec_PtrAlloc( 100 );
    vCone     = Vec_PtrAlloc( 100 );
    vSol      = Vec_PtrAlloc( 100 );
    // go through the nodes in the topological order
    CountUsed = CountUndo = 0;
    nNodesOld = Ivy_ManObjIdNext(p);
    Ivy_ManForEachObj( p, pObj, i )
    {
        assert( !Ivy_ObjIsBuf(pObj) );
        if ( i >= nNodesOld )
            break;
        // skip no-nodes and MUX roots
        if ( !Ivy_ObjIsNode(pObj) || Ivy_ObjIsExor(pObj) || Ivy_ObjIsMuxType(pObj) )
            continue;
//        if ( pObj->Id > 297 ) // 296 --- 297 
//            break;
        if ( pObj->Id == 297 )
        {
            int x = 0;
        }
        // get the largest algebraic cut
        RetValue = Ivy_ManFindAlgCut( pObj, vFront, vLeaves, vCone );
        // the case of a trivial tree cut
        if ( RetValue == 1 )
            continue;
        // the case of constant 0 cone
        if ( RetValue == -1 )
        {
            Ivy_ObjReplace( pObj, Ivy_ManConst0(p), 1, 0, 1 ); 
            continue;
        }
        assert( Vec_PtrSize(vLeaves) > 2 );
        // get the required level for this node
        LevelR = vRequired? Vec_IntEntry(vRequired, pObj->Id) : 1000000;
        // create a new cone
        pResult = Ivy_NodeRewriteAlg( pObj, vFront, vLeaves, vCone, vSol, LevelR, fUseZeroCost );
        if ( pResult == NULL || pResult == pObj )
            continue;
        assert( Vec_PtrSize(vSol) == 1 || !Ivy_IsComplement(pResult) );
        if ( Ivy_ObjLevel(Ivy_Regular(pResult)) > LevelR && Ivy_ObjRefs(Ivy_Regular(pResult)) == 0 )
            Ivy_ObjDelete_rec(Ivy_Regular(pResult), 1), CountUndo++;
        else
            Ivy_ObjReplace( pObj, pResult, 1, 0, 1 ), CountUsed++; 
    }
    printf( "Used = %d. Undo = %d.\n", CountUsed, CountUndo );
    Vec_PtrFree( vFront );
    Vec_PtrFree( vCone );
    Vec_PtrFree( vSol );
    if ( vRequired ) Vec_IntFree( vRequired );
    if ( i = Ivy_ManCleanup(p) )
        printf( "Cleanup after rewriting removed %d dangling nodes.\n", i );
    if ( !Ivy_ManCheck(p) )
        printf( "Ivy_ManRewriteAlg(): The check has failed.\n" );
    return 1;
}

/**Function*************************************************************

  Synopsis    [Analizes one node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Ivy_Obj_t * Ivy_NodeRewriteAlg( Ivy_Obj_t * pObj, Vec_Ptr_t * vFront, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone, Vec_Ptr_t * vSols, int LevelR, int fUseZeroCost )
{
    int fVerbose = 0;
    Ivy_Obj_t * pTemp;
    int k, Counter, nMffc, RetValue;

    if ( fVerbose )
    {
        if ( Ivy_ObjIsExor(pObj) )
            printf( "x " );
        else
            printf( "  " );
    }

/*       
    printf( "%d ", Vec_PtrSize(vFront) );
    printf( "( " );
    Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pTemp, k )
        printf( "%d ", Ivy_ObjRefs(Ivy_Regular(pTemp)) );
    printf( ")\n" );
*/
    // collect nodes in the cone
    if ( Ivy_ObjIsExor(pObj) )
        Ivy_ManCollectCone( pObj, vFront, vCone );
    else
        Ivy_ManCollectCone( pObj, vLeaves, vCone );

    // deref nodes in the cone
    Vec_PtrForEachEntry( Ivy_Obj_t *, vCone, pTemp, k )
    {
        Ivy_ObjRefsDec( Ivy_ObjFanin0(pTemp) );
        Ivy_ObjRefsDec( Ivy_ObjFanin1(pTemp) );
        pTemp->fMarkB = 1;
    }

    // count the MFFC size
    Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pTemp, k )
        Ivy_Regular(pTemp)->fMarkA = 1;
    nMffc = Ivy_NodeCountMffc( pObj );
    Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pTemp, k )
        Ivy_Regular(pTemp)->fMarkA = 0;

    if ( fVerbose )
    {
    Counter = 0;
    Vec_PtrForEachEntry( Ivy_Obj_t *, vCone, pTemp, k )
        Counter += (Ivy_ObjRefs(pTemp) > 0);
    printf( "%5d : Leaves = %2d. Cone = %2d. ConeRef = %2d.   Mffc = %d.   Lev = %d.  LevR = %d.\n", 
        pObj->Id, Vec_PtrSize(vFront), Vec_PtrSize(vCone), Counter-1, nMffc, Ivy_ObjLevel(pObj), LevelR );
    }
/*
    printf( "Leaves:" );
    Vec_PtrForEachEntry( Ivy_Obj_t *, vLeaves, pTemp, k )
        printf( " %d%s", Ivy_Regular(pTemp)->Id, Ivy_IsComplement(pTemp)? "\'" : "" );
    printf( "\n" );
    printf( "Cone:\n" );
    Vec_PtrForEachEntry( Ivy_Obj_t *, vCone, pTemp, k )
        printf( " %5d = %d%s %d%s\n", pTemp->Id,
            Ivy_ObjFaninId0(pTemp), Ivy_ObjFaninC0(pTemp)? "\'" : "",
            Ivy_ObjFaninId1(pTemp), Ivy_ObjFaninC1(pTemp)? "\'" : "" );
*/

    RetValue = Ivy_MultiPlus( vLeaves, vCone, Ivy_ObjType(pObj), nMffc + fUseZeroCost, vSols );

    // ref nodes in the cone
    Vec_PtrForEachEntry( Ivy_Obj_t *, vCone, pTemp, k )
    {
        Ivy_ObjRefsInc( Ivy_ObjFanin0(pTemp) );
        Ivy_ObjRefsInc( Ivy_ObjFanin1(pTemp) );
        pTemp->fMarkA = 0;
        pTemp->fMarkB = 0;
    }

    if ( !RetValue )
        return NULL;

    if ( Vec_PtrSize( vSols ) == 1 )
        return Vec_PtrEntry( vSols, 0 );
    return Ivy_NodeBalanceBuildSuper( vSols, Ivy_ObjType(pObj), 1 );
}

/**Function*************************************************************

  Synopsis    [Comparison for node pointers.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ivy_NodeCountMffc_rec( Ivy_Obj_t * pNode )
{
    if ( Ivy_ObjRefs(pNode) > 0 || Ivy_ObjIsCi(pNode) || pNode->fMarkA )
        return 0;
    assert( pNode->fMarkB );
    pNode->fMarkA = 1;
//    printf( "%d ", pNode->Id );
    if ( Ivy_ObjIsBuf(pNode) )
        return Ivy_NodeCountMffc_rec( Ivy_ObjFanin0(pNode) );
    return 1 + Ivy_NodeCountMffc_rec( Ivy_ObjFanin0(pNode) ) + Ivy_NodeCountMffc_rec( Ivy_ObjFanin1(pNode) );
}

/**Function*************************************************************

  Synopsis    [Comparison for node pointers.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ivy_NodeCountMffc( Ivy_Obj_t * pNode )
{
    assert( pNode->fMarkB );
    return 1 + Ivy_NodeCountMffc_rec( Ivy_ObjFanin0(pNode) ) + Ivy_NodeCountMffc_rec( Ivy_ObjFanin1(pNode) );
}

/**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 * pObj, Ivy_Type_t Type, Vec_Ptr_t * vFront, Vec_Ptr_t * vCone )
{
    int RetValue0, RetValue1;
    Ivy_Obj_t * pObjR = Ivy_Regular(pObj);
    assert( !Ivy_ObjIsBuf(pObjR) );
    assert( Type != IVY_EXOR || !Ivy_IsComplement(pObj) );

    // make sure the node is not visited twice in different polarities
    if ( Ivy_IsComplement(pObj) )
    { // if complemented, mark B
        if ( pObjR->fMarkA )
            return -1;
        pObjR->fMarkB = 1;
    }
    else
    { // if non-complicated, mark A
        if ( pObjR->fMarkB )
            return -1;
        pObjR->fMarkA = 1;
    }
    Vec_PtrPush( vCone, pObjR );

    // if the node is the end of the tree, return
    if ( Ivy_IsComplement(pObj) || Ivy_ObjType(pObj) != Type )
    {
        if ( Ivy_ObjRefs(pObjR) == 1 )
            return 1;
        assert( Ivy_ObjRefs(pObjR) > 1 );
        Vec_PtrPush( vFront, pObj );
        return 0;
    }

    // branch on the node
    assert( !Ivy_IsComplement(pObj) );
    assert( Ivy_ObjIsNode(pObj) );
    // what if buffer has more than one fanout???
    RetValue0 = Ivy_ManFindAlgCut_rec( Ivy_ObjReal( Ivy_ObjChild0(pObj) ), Type, vFront, vCone );
    RetValue1 = Ivy_ManFindAlgCut_rec( Ivy_ObjReal( Ivy_ObjChild1(pObj) ), Type, vFront, vCone );
    if ( RetValue0 == -1 || RetValue1 == -1 )
        return -1;

    // the case when both have no external references
    if ( RetValue0 && RetValue1 )
    {
        if ( Ivy_ObjRefs(pObj) == 1 )
            return 1;
        assert( Ivy_ObjRefs(pObj) > 1 );
        Vec_PtrPush( vFront, pObj );
        return 0;
    }
    // the case when one of them has external references
    if ( RetValue0 )
        Vec_PtrPush( vFront, Ivy_ObjReal( Ivy_ObjChild0(pObj) ) );
    if ( RetValue1 )
        Vec_PtrPush( vFront, Ivy_ObjReal( Ivy_ObjChild1(pObj) ) );
    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, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone )
{
    Ivy_Obj_t * pObj, * pPrev;
    int RetValue, i;
    assert( !Ivy_IsComplement(pRoot) );
    assert( Ivy_ObjIsNode(pRoot) );
    // clear the frontier and collect the nodes
    Vec_PtrClear( vCone );
    Vec_PtrClear( vFront );
    Vec_PtrClear( vLeaves );
    RetValue = Ivy_ManFindAlgCut_rec( pRoot, Ivy_ObjType(pRoot), vFront, vCone );
    // clean the marks
    Vec_PtrForEachEntry( Ivy_Obj_t *, vCone, pObj, i )
        pObj->fMarkA = pObj->fMarkB = 0;
    // quit if the same node is found in both polarities
    if ( RetValue == -1 )
        return -1;
    // return if the node is the root of a tree
    if ( RetValue == 1 )
        return 1;
    // return if the cut is composed of two nodes
    if ( Vec_PtrSize(vFront) <= 2 )
        return 1;
    // sort the entries in increasing order
    Vec_PtrSort( vFront, (int (*)(void))Ivy_ManFindAlgCutCompare );
    // remove duplicates from vFront and save the nodes in vLeaves
    pPrev = Vec_PtrEntry(vFront, 0);
    Vec_PtrPush( vLeaves, pPrev );
    Vec_PtrForEachEntryStart( Ivy_Obj_t *, vFront, pObj, i, 1 )
    {
        // compare current entry and the previous entry
        if ( pObj == pPrev )
        {
            if ( Ivy_ObjIsExor(pRoot) ) // A <+> A = 0
            {
                // vLeaves are no longer structural support of pRoot!!!
                Vec_PtrPop(vLeaves);  
                pPrev = Vec_PtrSize(vLeaves) == 0 ? NULL : Vec_PtrEntryLast(vLeaves);
            }
            continue;
        }
        if ( pObj == Ivy_Not(pPrev) )
        {
            assert( Ivy_ObjIsAnd(pRoot) );
            return -1;
        }
        pPrev = pObj;
        Vec_PtrPush( vLeaves, pObj );
    }
    if ( Vec_PtrSize(vLeaves) == 0 )
        return -1;
    if ( Vec_PtrSize(vLeaves) <= 2 )
        return 1;
    return 0;
}


////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END