acecCo.c

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

  FileName    [acecCo.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [CEC for arithmetic circuits.]

  Synopsis    [Core procedures.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: acecCo.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

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

#include "acecInt.h"
#include "misc/vec/vecWec.h"

ABC_NAMESPACE_IMPL_START

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

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

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

  Synopsis    [Collect non-XOR inputs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_PolynCoreNonXors_rec( Gia_Man_t * pGia, Gia_Obj_t * pObj, Vec_Int_t * vXorPairs )
{
    extern int Gia_ManSuppSizeOne( Gia_Man_t * p, Gia_Obj_t * pObj );
    Gia_Obj_t * pFan0, * pFan1;
    if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
        return;
    Gia_PolynCoreNonXors_rec( pGia, Gia_Regular(pFan0), vXorPairs );
    Gia_PolynCoreNonXors_rec( pGia, Gia_Regular(pFan1), vXorPairs );
    //if ( Gia_ManSuppSizeOne(pGia, pObj) > 4 )
    //if ( Gia_ObjId(pGia, pObj) >= 73 )
    Vec_IntPushTwo( vXorPairs, Gia_ObjId(pGia, Gia_Regular(pFan0)), Gia_ObjId(pGia, Gia_Regular(pFan1)) );
}
Vec_Int_t * Gia_PolynAddHaRoots( Gia_Man_t * pGia )
{
    int i, iFan0, iFan1;
    Vec_Int_t * vNewOuts = Vec_IntAlloc( 100 );
    Vec_Int_t * vXorPairs = Vec_IntAlloc( 100 );
    Gia_Obj_t * pObj = Gia_ManCo( pGia, Gia_ManCoNum(pGia)-1 );
    Gia_PolynCoreNonXors_rec( pGia, Gia_ObjFanin0(pObj), vXorPairs );
    // add new outputs
    Gia_ManSetPhase( pGia );
    Vec_IntForEachEntryDouble( vXorPairs, iFan0, iFan1, i )
    {
        Gia_Obj_t * pFan0 = Gia_ManObj( pGia, iFan0 );
        Gia_Obj_t * pFan1 = Gia_ManObj( pGia, iFan1 );
        int iLit0 = Abc_Var2Lit( iFan0, pFan0->fPhase );
        int iLit1 = Abc_Var2Lit( iFan1, pFan1->fPhase );
        int iRoot = Gia_ManAppendAnd( pGia, iLit0, iLit1 );
        Vec_IntPush( vNewOuts, Abc_Lit2Var(iRoot) );
    }
    Vec_IntFree( vXorPairs );
    Vec_IntReverseOrder( vNewOuts );
//    Vec_IntPop( vNewOuts );
    return vNewOuts;
}


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

  Synopsis    [Detects the order of adders.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Wec_t * Gia_PolynComputeMap( Vec_Int_t * vAdds, int nObjs )
{
    // map nodes driven by adders into adder indexes
    Vec_Wec_t * vMap = Vec_WecStart( nObjs );  int i;
    for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ )
    {
        int Entry1 = Vec_IntEntry( vAdds, 6*i + 3 );
        int Entry2 = Vec_IntEntry( vAdds, 6*i + 4 );
        Vec_WecPush( vMap, Entry1, i );
        Vec_WecPush( vMap, Entry1, Entry2 );
        Vec_WecPush( vMap, Entry2, i );
        Vec_WecPush( vMap, Entry2, Entry1 );
    }
    return vMap;
}
Vec_Int_t * Gia_PolynCoreOrder_int( Gia_Man_t * pGia, Vec_Int_t * vAdds, Vec_Wec_t * vMap, Vec_Int_t * vRoots, Vec_Int_t ** pvIns )
{
    Vec_Int_t * vOrder  = Vec_IntAlloc( 1000 );
    Vec_Bit_t * vIsRoot = Vec_BitStart( Gia_ManObjNum(pGia) );
    int i, k, Index = -1, Driver, Entry1, Entry2 = -1;
    // mark roots
    Vec_IntForEachEntry( vRoots, Driver, i )
        Vec_BitWriteEntry( vIsRoot, Driver, 1 );
    // collect boxes
    while ( 1 )
    {
        // iterate through boxes driving this one
        Vec_IntForEachEntry( vRoots, Entry1, i )
        {
            Vec_Int_t * vLevel = Vec_WecEntry( vMap, Entry1 );
            Vec_IntForEachEntryDouble( vLevel, Index, Entry2, k )
                if ( Vec_BitEntry(vIsRoot, Entry2) )
                    break;
            if ( k == Vec_IntSize(vLevel) )
                continue;
            assert( Vec_BitEntry(vIsRoot, Entry1) );
            assert( Vec_BitEntry(vIsRoot, Entry2) );
            // collect adder
            Vec_IntPush( vOrder, Index );
            // clean marks
            Vec_BitWriteEntry( vIsRoot, Entry1, 0 );
            Vec_BitWriteEntry( vIsRoot, Entry2, 0 );
            Vec_IntRemove( vRoots, Entry1 );
            Vec_IntRemove( vRoots, Entry2 );
            // set new marks
            Entry1 = Vec_IntEntry( vAdds, 6*Index + 0 );
            Entry2 = Vec_IntEntry( vAdds, 6*Index + 1 );
            Driver = Vec_IntEntry( vAdds, 6*Index + 2 );
            Vec_BitWriteEntry( vIsRoot, Entry1, 1 );
            Vec_BitWriteEntry( vIsRoot, Entry2, 1 );
            Vec_BitWriteEntry( vIsRoot, Driver, 1 );
            Vec_IntPushUnique( vRoots, Entry1 );
            Vec_IntPushUnique( vRoots, Entry2 );
            Vec_IntPushUnique( vRoots, Driver );
            break;
        }
        if ( i == Vec_IntSize(vRoots) )
            break;
    }
    // collect remaining leaves
    if ( pvIns )
    {
        *pvIns = Vec_IntAlloc( Vec_BitSize(vIsRoot) );
        Vec_BitForEachEntryStart( vIsRoot, Driver, i, 1 )
            if ( Driver )
                Vec_IntPush( *pvIns, i );
    }
    Vec_BitFree( vIsRoot );
    return vOrder;
}
Vec_Int_t * Gia_PolynCoreOrder( Gia_Man_t * pGia, Vec_Int_t * vAdds, Vec_Int_t * vAddCos, Vec_Int_t ** pvIns, Vec_Int_t ** pvOuts )
{
    Vec_Int_t * vOrder;
    Vec_Wec_t * vMap = Gia_PolynComputeMap( vAdds, Gia_ManObjNum(pGia) );
    Vec_Int_t * vRoots = Vec_IntAlloc( Gia_ManCoNum(pGia) );
    int i, Driver;
    // collect roots
    Gia_ManForEachCoDriverId( pGia, Driver, i )
        Vec_IntPush( vRoots, Driver );
    // collect additional outputs
    if ( vAddCos )
        Vec_IntForEachEntry( vAddCos, Driver, i )
            Vec_IntPush( vRoots, Driver );
    // remember roots
    if ( pvOuts )
        *pvOuts = Vec_IntDup( vRoots );
    // create order
    vOrder = Gia_PolynCoreOrder_int( pGia, vAdds, vMap, vRoots, pvIns );
    Vec_IntFree( vRoots );
    Vec_WecFree( vMap );
    printf( "Collected %d boxes.\n", Vec_IntSize(vOrder) );
    return vOrder;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_PolyCollectRoots_rec( Vec_Int_t * vAdds, Vec_Wec_t * vMap, Vec_Bit_t * vMarks, int iBox, Vec_Int_t * vRoots )
{
    int k;
    for ( k = 0; k < 3; k++ )
    {
        int i, Index, Sum, Carry = Vec_IntEntry( vAdds, 6*iBox+k );
        Vec_Int_t * vLevel = Vec_WecEntry( vMap, Carry );
        if ( Carry == 0 )
            continue;
        Vec_IntForEachEntryDouble( vLevel, Index, Sum, i )
            if ( Vec_IntEntry(vAdds, 6*Index+4) == Carry && !Vec_BitEntry(vMarks, Sum) )
            {
                Vec_IntPush( vRoots, Sum );
                Gia_PolyCollectRoots_rec( vAdds, vMap, vMarks, Index, vRoots );
            }
    }
}
void Gia_PolyCollectRoots( Vec_Int_t * vAdds, Vec_Wec_t * vMap, Vec_Bit_t * vMarks, int iBox, Vec_Int_t * vRoots )
{
    Vec_IntClear( vRoots );
    Vec_IntPush( vRoots, Vec_IntEntry(vAdds, 6*iBox+3) );
    Vec_IntPush( vRoots, Vec_IntEntry(vAdds, 6*iBox+4) );
    Gia_PolyCollectRoots_rec( vAdds, vMap, vMarks, iBox, vRoots );
}
Vec_Wec_t * Gia_PolynCoreOrderArray( Gia_Man_t * pGia, Vec_Int_t * vAdds, Vec_Int_t * vRootBoxes )
{
    extern Vec_Bit_t * Acec_ManPoolGetPointed( Gia_Man_t * p, Vec_Int_t * vAdds );
    Vec_Bit_t * vMarks = Acec_ManPoolGetPointed( pGia, vAdds );
    Vec_Wec_t * vMap   = Gia_PolynComputeMap( vAdds, Gia_ManObjNum(pGia) );
    Vec_Wec_t * vRes   = Vec_WecStart( Vec_IntSize(vRootBoxes) );
    Vec_Int_t * vRoots = Vec_IntAlloc( 64 );
    Vec_Int_t * vOrder;
    int i, iBox;
    Vec_IntForEachEntry( vRootBoxes, iBox, i )
    {
        Gia_PolyCollectRoots( vAdds, vMap, vMarks, iBox, vRoots );
        vOrder = Gia_PolynCoreOrder_int( pGia, vAdds, vMap, vRoots, NULL );
        Vec_IntAppend( Vec_WecEntry(vRes, i), vOrder );
        Vec_IntFree( vOrder );
    }
    Vec_BitFree( vMarks );
    Vec_IntFree( vRoots );
    Vec_WecFree( vMap );
    return vRes;
}

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

  Synopsis    [Collect internal node order.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_PolynCoreCollect_rec( Gia_Man_t * pGia, int iObj, Vec_Int_t * vNodes, Vec_Bit_t * vVisited )
{
    if ( Vec_BitEntry(vVisited, iObj) )
        return;
    Vec_BitSetEntry( vVisited, iObj, 1 );
    Gia_PolynCoreCollect_rec( pGia, Gia_ObjFaninId0p(pGia, Gia_ManObj(pGia, iObj)), vNodes, vVisited );
    Gia_PolynCoreCollect_rec( pGia, Gia_ObjFaninId1p(pGia, Gia_ManObj(pGia, iObj)), vNodes, vVisited );
    Vec_IntPush( vNodes, iObj );
}
Vec_Int_t * Gia_PolynCoreCollect( Gia_Man_t * pGia, Vec_Int_t * vAdds, Vec_Int_t * vOrder )
{
    Vec_Int_t * vNodes = Vec_IntAlloc( 1000 );
    Vec_Bit_t * vVisited = Vec_BitStart( Gia_ManObjNum(pGia) );
    int i, Index, Entry1, Entry2, Entry3;
    Vec_IntForEachEntryReverse( vOrder, Index, i )
    {
        // mark inputs
        Entry1 = Vec_IntEntry( vAdds, 6*Index + 0 );
        Entry2 = Vec_IntEntry( vAdds, 6*Index + 1 );
        Entry3 = Vec_IntEntry( vAdds, 6*Index + 2 );
        Vec_BitWriteEntry( vVisited, Entry1, 1 );
        Vec_BitWriteEntry( vVisited, Entry2, 1 );
        Vec_BitWriteEntry( vVisited, Entry3, 1 );
        // traverse from outputs
        Entry1 = Vec_IntEntry( vAdds, 6*Index + 3 );
        Entry2 = Vec_IntEntry( vAdds, 6*Index + 4 );
        Gia_PolynCoreCollect_rec( pGia, Entry1, vNodes, vVisited );
        Gia_PolynCoreCollect_rec( pGia, Entry2, vNodes, vVisited );
    }
    Vec_BitFree( vVisited );
    return vNodes;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_PolynCorePrintCones( Gia_Man_t * pGia, Vec_Int_t * vLeaves, int fVerbose )
{
    int i, iObj;
    if ( fVerbose )
    {
        Vec_IntForEachEntry( vLeaves, iObj, i )
        {
            printf( "%4d : ", i );
            printf( "Supp = %3d  ", Gia_ManSuppSize(pGia, &iObj, 1) );
            printf( "Cone = %3d  ", Gia_ManConeSize(pGia, &iObj, 1) );
            printf( "\n" );
        }
    }
    else
    {
        int SuppMax = 0, ConeMax = 0;
        Vec_IntForEachEntry( vLeaves, iObj, i )
        {
            SuppMax = Abc_MaxInt( SuppMax, Gia_ManSuppSize(pGia, &iObj, 1) );
            ConeMax = Abc_MaxInt( ConeMax, Gia_ManConeSize(pGia, &iObj, 1) );
        }
        printf( "Remaining cones:  Count = %d.  SuppMax = %d.  ConeMax = %d.\n", Vec_IntSize(vLeaves), SuppMax, ConeMax );
    }
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Gia_PolynCoreDupTreePlus_rec( Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj )
{
    if ( ~pObj->Value )
        return pObj->Value;
    assert( Gia_ObjIsAnd(pObj) );
    Gia_PolynCoreDupTreePlus_rec( pNew, p, Gia_ObjFanin0(pObj) );
    Gia_PolynCoreDupTreePlus_rec( pNew, p, Gia_ObjFanin1(pObj) );
    return pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
} 
Gia_Man_t * Gia_PolynCoreDupTree( Gia_Man_t * p, Vec_Int_t * vAddCos, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, int fAddCones )
{
    Gia_Man_t * pNew;
    Gia_Obj_t * pObj;
    int i;
    assert( Gia_ManRegNum(p) == 0 );
    Gia_ManFillValue( p );
    pNew = Gia_ManStart( Gia_ManObjNum(p) );
    pNew->pName = Abc_UtilStrsav( p->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
    Gia_ManConst0(p)->Value = 0;
    if ( fAddCones )
    {
        Gia_ManForEachPi( p, pObj, i )
            pObj->Value = Gia_ManAppendCi(pNew);
        Gia_ManForEachObjVec( vLeaves, p, pObj, i )
            pObj->Value = Gia_PolynCoreDupTreePlus_rec( pNew, p, pObj );
    }
    else
    {
        Gia_ManForEachObjVec( vLeaves, p, pObj, i )
            pObj->Value = Gia_ManAppendCi(pNew);
    }
    Gia_ManForEachObjVec( vNodes, p, pObj, i )
        pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    Gia_ManForEachCo( p, pObj, i )
        Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
    Gia_ManForEachObjVec( vAddCos, p, pObj, i )
        Gia_ManAppendCo( pNew, pObj->Value );
    return pNew;

}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_PolynCoreDetectTest_int( Gia_Man_t * pGia, Vec_Int_t * vAddCos, int fAddCones, int fVerbose )
{
    extern Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, Vec_Int_t ** pvXors, int fVerbose );
    abctime clk = Abc_Clock();
    Gia_Man_t * pNew;
    Vec_Int_t * vAdds = Ree_ManComputeCuts( pGia, NULL, 1 );
    Vec_Int_t * vLeaves, * vRoots, * vOrder = Gia_PolynCoreOrder( pGia, vAdds, vAddCos, &vLeaves, &vRoots );
    Vec_Int_t * vNodes = Gia_PolynCoreCollect( pGia, vAdds, vOrder );

    //Gia_ManShow( pGia, vNodes, 0 );
    
    printf( "Detected %d FAs/HAs. Roots = %d. Leaves = %d. Nodes = %d. Adds = %d. ", 
        Vec_IntSize(vAdds)/6, Vec_IntSize(vLeaves), Vec_IntSize(vRoots), Vec_IntSize(vNodes), Vec_IntSize(vOrder) );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );

    Gia_PolynCorePrintCones( pGia, vLeaves, fVerbose );

    pNew = Gia_PolynCoreDupTree( pGia, vAddCos, vLeaves, vNodes, fAddCones );

    Vec_IntFree( vAdds );
    Vec_IntFree( vLeaves );
    Vec_IntFree( vRoots );
    Vec_IntFree( vOrder );
    Vec_IntFree( vNodes );
    return pNew;
}
Gia_Man_t * Gia_PolynCoreDetectTest( Gia_Man_t * pGia, int fAddExtra, int fAddCones, int fVerbose )
{
    Vec_Int_t * vAddCos = fAddExtra ? Gia_PolynAddHaRoots( pGia ) : Vec_IntAlloc(0);
    Gia_Man_t * pNew = Gia_PolynCoreDetectTest_int( pGia, vAddCos, fAddCones, fVerbose );
    printf( "On top of %d COs, created %d new adder outputs.\n", Gia_ManCoNum(pGia), Vec_IntSize(vAddCos) );
    Vec_IntFree( vAddCos );
    return pNew;
}

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


ABC_NAMESPACE_IMPL_END