acecCl.c

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

  FileName    [acecCl.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: acecCl.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

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

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

ABC_NAMESPACE_IMPL_START

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



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

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Acec_ManDerive_rec( Gia_Man_t * pNew, Gia_Man_t * p, int Node, Vec_Int_t * vMirrors )
{
    Gia_Obj_t * pObj;
    int Obj = Node;
    if ( Vec_IntEntry(vMirrors, Node) >= 0 )
        Obj = Abc_Lit2Var( Vec_IntEntry(vMirrors, Node) );
    pObj = Gia_ManObj( p, Obj );
    if ( !~pObj->Value )
    {
        assert( Gia_ObjIsAnd(pObj) );
        Acec_ManDerive_rec( pNew, p, Gia_ObjFaninId0(pObj, Obj), vMirrors );
        Acec_ManDerive_rec( pNew, p, Gia_ObjFaninId1(pObj, Obj), vMirrors );
        if ( Gia_ObjIsXor(pObj) )
            pObj->Value = Gia_ManAppendXorReal( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
        else
            pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    }
    // set the original node as well
    if ( Obj != Node )
        Gia_ManObj(p, Node)->Value = Abc_LitNotCond( pObj->Value, Abc_LitIsCompl(Vec_IntEntry(vMirrors, Node)) );
} 
Gia_Man_t * Acec_ManDerive( Gia_Man_t * p, Vec_Int_t * vMirrors )
{
    Gia_Man_t * pNew;
    Gia_Obj_t * pObj;
    int i;
    assert( p->pMuxes == NULL );
    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;
    Gia_ManHashAlloc( pNew );
    Gia_ManForEachCi( p, pObj, i )
        pObj->Value = Gia_ManAppendCi(pNew);
    Gia_ManForEachCo( p, pObj, i )
        Acec_ManDerive_rec( pNew, p, Gia_ObjFaninId0p(p, pObj), vMirrors );
    Gia_ManForEachCo( p, pObj, i )
        pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
    Gia_ManHashStop( pNew );
    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
    return pNew;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Acec_CollectXorTops( Gia_Man_t * p )
{
    Vec_Int_t * vRootXorSet = Vec_IntAlloc( Gia_ManCoNum(p) );
    Gia_Obj_t * pObj, * pFan0, * pFan1, * pFan00, * pFan01, * pFan10, * pFan11;
    int i, fXor0, fXor1, fFirstXor = 0;
    Gia_ManForEachCoDriver( p, pObj, i )
    {
        if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
        {
            if ( fFirstXor )
            {
                printf( "XORs do not form a continuous sequence\n" );
                Vec_IntFreeP( &vRootXorSet );
                break;
            }
            continue;
        }
        fFirstXor = 1;
        fXor0 = Gia_ObjRecognizeExor(Gia_Regular(pFan0), &pFan00, &pFan01);
        fXor1 = Gia_ObjRecognizeExor(Gia_Regular(pFan1), &pFan10, &pFan11);
        if ( fXor0 == fXor1 )
        {
            printf( "Both inputs of top level XOR have XOR/non-XOR\n" );
            Vec_IntFreeP( &vRootXorSet );
            break;
        }
        Vec_IntPush( vRootXorSet, Gia_ObjId(p, pObj) );
        Vec_IntPush( vRootXorSet, fXor1 ? Gia_ObjId(p, Gia_Regular(pFan0))  : Gia_ObjId(p, Gia_Regular(pFan1)) );
        Vec_IntPush( vRootXorSet, fXor1 ? Gia_ObjId(p, Gia_Regular(pFan10)) : Gia_ObjId(p, Gia_Regular(pFan00)) );
        Vec_IntPush( vRootXorSet, fXor1 ? Gia_ObjId(p, Gia_Regular(pFan11)) : Gia_ObjId(p, Gia_Regular(pFan01)) );
    }
    for ( i = 0; 4*i < Vec_IntSize(vRootXorSet); i++ )
    {
        printf( "%2d : ", i );
        printf( "%4d <- ", Vec_IntEntry(vRootXorSet, 4*i) );
        printf( "%4d ", Vec_IntEntry(vRootXorSet, 4*i+1) );
        printf( "%4d ", Vec_IntEntry(vRootXorSet, 4*i+2) );
        printf( "%4d ", Vec_IntEntry(vRootXorSet, 4*i+3) );
        printf( "\n" );
    }
    return vRootXorSet;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Acec_DetectLitPolarity( Gia_Man_t * p, int Node, int Leaf )
{
    Gia_Obj_t * pNode;
    int Lit0, Lit1;
    if ( Node < Leaf )
        return -1;
    if ( Node == Leaf )
        return Abc_Var2Lit(Node, 0);
    pNode = Gia_ManObj( p, Node );
    Lit0 = Acec_DetectLitPolarity( p, Gia_ObjFaninId0(pNode, Node), Leaf );
    Lit1 = Acec_DetectLitPolarity( p, Gia_ObjFaninId1(pNode, Node), Leaf );
    Lit0 = Lit0 == -1 ? Lit0 : Abc_LitNotCond( Lit0, Gia_ObjFaninC0(pNode) );
    Lit1 = Lit1 == -1 ? Lit1 : Abc_LitNotCond( Lit1, Gia_ObjFaninC1(pNode) );
    if ( Lit0 == -1 && Lit1 == -1 )
        return -1;
    assert( Lit0 != -1 || Lit1 != -1 );
    if ( Lit0 != -1 && Lit1 != -1 )
    {
        assert( Lit0 == Lit1 );
        printf( "Problem for leaf %d\n", Leaf );
        return Lit0;
    }
    return Lit0 != -1 ? Lit0 : Lit1;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Acec_DetectComputeSuppOne_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp, Vec_Int_t * vNods )
{
    if ( Gia_ObjIsTravIdCurrent(p, pObj) )
        return;
    Gia_ObjSetTravIdCurrent(p, pObj);
    if ( pObj->fMark0 )
    {
        Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
        return;
    }
    assert( Gia_ObjIsAnd(pObj) );
    Acec_DetectComputeSuppOne_rec( p, Gia_ObjFanin0(pObj), vSupp, vNods );
    Acec_DetectComputeSuppOne_rec( p, Gia_ObjFanin1(pObj), vSupp, vNods );
    Vec_IntPush( vNods, Gia_ObjId(p, pObj) );
}
void Acec_DetectComputeSupports( Gia_Man_t * p, Vec_Int_t * vRootXorSet )
{
    Vec_Int_t * vNods = Vec_IntAlloc( 100 ); 
    Vec_Int_t * vPols = Vec_IntAlloc( 100 ); 
    Vec_Int_t * vSupp = Vec_IntAlloc( 100 );  int i, k, Node, Pol;
    for ( i = 0; 4*i < Vec_IntSize(vRootXorSet); i++ )
    {
        Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 1;
        Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+2) )->fMark0 = 1;
        Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+3) )->fMark0 = 1;
    }
    for ( i = 1; 4*i < Vec_IntSize(vRootXorSet); i++ )
    {
        Vec_IntClear( vSupp );
        Gia_ManIncrementTravId( p );

        Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 0;
        Acec_DetectComputeSuppOne_rec( p, Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) ), vSupp, vNods );
        Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 1;

        Vec_IntSort( vSupp, 0 );

        printf( "Out %4d : %4d  \n", i, Vec_IntEntry(vRootXorSet, 4*i+1) );
        Vec_IntPrint( vSupp );

        printf( "Cone:\n" );
        Vec_IntForEachEntry( vNods, Node, k )
            Gia_ObjPrint( p, Gia_ManObj(p, Node) );


        Vec_IntClear( vPols );
        Vec_IntForEachEntry( vSupp, Node, k )
            Vec_IntPush( vPols, Acec_DetectLitPolarity(p, Vec_IntEntry(vRootXorSet, 4*i+1), Node) );

        Vec_IntForEachEntryTwo( vSupp, vPols, Node, Pol, k )
            printf( "%d(%d)  ", Node, Abc_LitIsCompl(Pol) );

        printf( "\n" );

        Vec_IntPrint( vSupp );
    }
    for ( i = 0; 4*i < Vec_IntSize(vRootXorSet); i++ )
    {
        Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 0;
        Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+2) )->fMark0 = 0;
        Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+3) )->fMark0 = 0;
    }
    Vec_IntFree( vSupp );
    Vec_IntFree( vPols );
    Vec_IntFree( vNods );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Acec_DetectXorBuildNew( Gia_Man_t * p, Vec_Int_t * vRootXorSet )
{
    Gia_Man_t * pNew;
    int i, k, iOr1, iAnd1, iAnd2, pLits[3]; // carry, in1, in2
    Vec_Int_t * vMirrors = Vec_IntStart( Gia_ManObjNum(p) );
    for ( i = 0; 4*i < Vec_IntSize(vRootXorSet); i++ )
    {
        pLits[0] = Acec_DetectLitPolarity( p, Vec_IntEntry(vRootXorSet, 4*i), Vec_IntEntry(vRootXorSet, 4*i+1) );
        // get polarity of two new ones
        for ( k = 1; k < 3; k++ )
            pLits[k] = Acec_DetectLitPolarity( p, Vec_IntEntry(vRootXorSet, 4*i), Vec_IntEntry(vRootXorSet, 4*i+k+1) );
        // create the gate
        iOr1  = Gia_ManAppendOr( p, pLits[1], pLits[2] );
        iAnd1 = Gia_ManAppendAnd( p, pLits[0], iOr1 );
        iAnd2 = Gia_ManAppendAnd( p, pLits[1], pLits[2] );
        pLits[0] = Gia_ManAppendOr( p, iAnd1, iAnd2 );
        Vec_IntWriteEntry( vMirrors, Vec_IntEntry(vRootXorSet, 4*i+1), pLits[0] );
    }
    // remap the AIG using map
    pNew = Acec_ManDerive( p, vMirrors );
    Vec_IntFree( vMirrors );
    return pNew;
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Acec_DetectAdditional( Gia_Man_t * p, int fVerbose )
{
    abctime clk = Abc_Clock();
    Gia_Man_t * pNew;
    Vec_Int_t * vRootXorSet;
//    Vec_Int_t * vXors, * vAdds = Ree_ManComputeCuts( p, &vXors, 0 );

    //Ree_ManPrintAdders( vAdds, 1 );
//    printf( "Detected %d full-adders and %d half-adders.  Found %d XOR-cuts.  ", Ree_ManCountFadds(vAdds), Vec_IntSize(vAdds)/6-Ree_ManCountFadds(vAdds), Vec_IntSize(vXors)/4 );
//    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );

    clk = Abc_Clock();
    vRootXorSet = Acec_CollectXorTops( p );
    if ( vRootXorSet )
    {
        Acec_DetectComputeSupports( p, vRootXorSet );

        pNew = Acec_DetectXorBuildNew( p, vRootXorSet );
        Vec_IntFree( vRootXorSet );
    }
    else
        pNew = Gia_ManDup( p );

    printf( "Detected %d top XORs.  ", Vec_IntSize(vRootXorSet)/4 );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );

//    Vec_IntFree( vXors );
//    Vec_IntFree( vAdds );
    return pNew;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Acec_RewriteTop( Gia_Man_t * p, Acec_Box_t * pBox )
{
    Vec_Int_t * vRes = Vec_IntAlloc( Gia_ManCoNum(p) + 1 );
    Vec_Int_t * vLevel;
    int i, k, iStart, iLit, Driver, Count = 0;
    // determine how much to shift
    Driver = Gia_ObjFaninId0p( p, Gia_ManCo(p, 0) );
    Vec_WecForEachLevel( pBox->vRootLits, vLevel, iStart )
        if ( Abc_Lit2Var(Vec_IntEntry(vLevel,0)) == Driver )
            break;
    assert( iStart < Gia_ManCoNum(p) );
    //Vec_WecPrintLits( pBox->vRootLits );
    Vec_WecForEachLevelStart( pBox->vRootLits, vLevel, i, iStart )
    {
        int In[3] = {0}, Out[2];
        assert( Vec_IntSize(vLevel) > 0 );
        assert( Vec_IntSize(vLevel) <= 3 );
        if ( Vec_IntSize(vLevel) == 1 )
        {
            Vec_IntPush( vRes, Vec_IntEntry(vLevel, 0) );
            continue;
        }
        Vec_IntForEachEntry( vLevel, iLit, k )
            In[k] = iLit;
        Acec_InsertFadd( p, In, Out );
        Vec_IntPush( vRes, Out[0] );
        if ( i+1 < Vec_WecSize(pBox->vRootLits) )
            Vec_IntPush( Vec_WecEntry(pBox->vRootLits, i+1), Out[1] );
        else
            Vec_IntPush( Vec_WecPushLevel(pBox->vRootLits), Out[1] );
        Count++;
    }
    assert( Vec_IntSize(vRes) >= Gia_ManCoNum(p) );
    Vec_IntShrink( vRes, Gia_ManCoNum(p) );
    printf( "Added %d adders for replace CLAs.  ", Count );
    return vRes;
}
Gia_Man_t * Acec_RewriteReplace( Gia_Man_t * p, Vec_Int_t * vRes )
{
    Gia_Man_t * pNew, * pTemp;
    Gia_Obj_t * pObj;  int i;
    assert( Gia_ManCoNum(p) == Vec_IntSize(vRes) );
    // create new manager
    pNew = Gia_ManStart( Gia_ManObjNum(p) );
    pNew->pName = Abc_UtilStrsav( p->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
    Gia_ManFillValue( p );
    Gia_ManConst0(p)->Value = 0;
    Gia_ManForEachCi( p, pObj, i )
        pObj->Value = Gia_ManAppendCi(pNew);
    Gia_ManForEachAnd( p, pObj, i )
        pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    Gia_ManForEachCo( p, pObj, i )
    {
        int iLit = Vec_IntEntry( vRes, i );
        Gia_Obj_t * pRepr = Gia_ManObj( p, Abc_Lit2Var(iLit) );
        pObj->Value = Gia_ManAppendCo( pNew, pRepr->Value );
    }
    // set correct phase
    Gia_ManSetPhase( p );
    Gia_ManSetPhase( pNew );
    Gia_ManForEachCo( pNew, pObj, i )
        if ( Gia_ObjPhase(pObj) != Gia_ObjPhase(Gia_ManCo(p, i)) )
            Gia_ObjFlipFaninC0( pObj );
    // remove dangling nodes
    pNew = Gia_ManCleanup( pTemp = pNew );
    Gia_ManStop( pTemp );
    return pNew;
}
Gia_Man_t * Acec_ManDecla( Gia_Man_t * pGia, int fBooth, int fVerbose )
{
    abctime clk = Abc_Clock();
    Gia_Man_t * pNew = NULL;
    Vec_Bit_t * vIgnore = fBooth ? Acec_BoothFindPPG(pGia) : NULL;
    Acec_Box_t * pBox = Acec_DeriveBox( pGia, vIgnore, 0, 0, fVerbose );
    Vec_Int_t * vResult;
    Vec_BitFreeP( &vIgnore );
    if ( pBox == NULL ) // cannot match
    {
        printf( "Cannot find arithmetic boxes.\n" );
        return Gia_ManDup( pGia );
    }
    vResult = Acec_RewriteTop( pGia, pBox );
    Acec_BoxFreeP( &pBox );
    pNew = Acec_RewriteReplace( pGia, vResult );
    Vec_IntFree( vResult );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    return pNew;
}

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


ABC_NAMESPACE_IMPL_END