acecOrder.c

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

  FileName    [acecOrder.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [CEC for arithmetic circuits.]

  Synopsis    [Node ordering.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "acecInt.h"

ABC_NAMESPACE_IMPL_START


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

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

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Gia_PolynFindOrder( Gia_Man_t * pGia, Vec_Int_t * vFadds, Vec_Int_t * vHadds, int fVerbose, int fVeryVerbose )
{
    int fDumpLeftOver = 0;
    int i, iXor, iMaj, iAnd, Entry, Iter, fFound, fFoundAll = 1;
    Vec_Int_t * vRecord = Vec_IntAlloc( 100 ), * vLeft, * vRecord2;
    Vec_Int_t * vMap = Vec_IntStart( Gia_ManObjNum(pGia) );
    Gia_ManForEachCoDriverId( pGia, iAnd, i )
        Vec_IntWriteEntry( vMap, iAnd, 1 );

    // collect the last XOR
    Vec_IntFreeP( &pGia->vXors );
    pGia->vXors = Gia_PolynCollectLastXor( pGia, fVerbose );
    printf( "Collected %d topmost XORs\n", Vec_IntSize(pGia->vXors) );
    //Vec_IntPrint( p->vXors );
    Vec_IntForEachEntry( pGia->vXors, iAnd, i )
    {
        Gia_Obj_t * pAnd = Gia_ManObj( pGia, iAnd );
        assert( Vec_IntEntry(vMap, iAnd) );
        Vec_IntWriteEntry( vMap, iAnd, 0 );
        Vec_IntWriteEntry( vMap, Gia_ObjFaninId0(pAnd, iAnd), 1 );
        Vec_IntWriteEntry( vMap, Gia_ObjFaninId1(pAnd, iAnd), 1 );
        Vec_IntPush( vRecord, Abc_Var2Lit2(iAnd, 3) );
        if ( fVeryVerbose )
            printf( "Recognizing %d => XXXOR(%d %d)\n", iAnd, Gia_ObjFaninId0(pAnd, iAnd), Gia_ObjFaninId1(pAnd, iAnd) );
    }

    // detect FAs and HAs
    for ( Iter = 0; fFoundAll; Iter++ )
    {
        if ( fVeryVerbose )
            printf( "Iteration %d\n", Iter );

        // check if we can extract FADDs
        fFoundAll = 0;
        do {
            fFound = 0;
            for ( i = Vec_IntSize(vFadds)/5 - 1; i >= 0; i-- )
            {
                iXor = Vec_IntEntry(vFadds, 5*i+3);
                iMaj = Vec_IntEntry(vFadds, 5*i+4);
                if ( Vec_IntEntry(vMap, iXor) && Vec_IntEntry(vMap, iMaj) )
                {
                    Vec_IntWriteEntry( vMap, iXor, 0 );
                    Vec_IntWriteEntry( vMap, iMaj, 0 );
                    Vec_IntWriteEntry( vMap, Vec_IntEntry(vFadds, 5*i+0), 1 );
                    Vec_IntWriteEntry( vMap, Vec_IntEntry(vFadds, 5*i+1), 1 );
                    Vec_IntWriteEntry( vMap, Vec_IntEntry(vFadds, 5*i+2), 1 );
                    Vec_IntPush( vRecord, Abc_Var2Lit2(i, 2) );
                    fFound = 1;
                    fFoundAll = 1;
                    if ( fVeryVerbose )
                        printf( "Recognizing (%d %d) => FA(%d %d %d)\n", iXor, iMaj, Vec_IntEntry(vFadds, 5*i+0), Vec_IntEntry(vFadds, 5*i+1), Vec_IntEntry(vFadds, 5*i+2)  );
                }
            }
        } while ( fFound );
        // check if we can extract HADDs
        do {
            fFound = 0; 
            for ( i = Vec_IntSize(vHadds)/2 - 1; i >= 0; i-- )
            {
                iXor = Vec_IntEntry(vHadds, 2*i+0);
                iMaj = Vec_IntEntry(vHadds, 2*i+1);
                if ( Vec_IntEntry(vMap, iXor) && Vec_IntEntry(vMap, iMaj) )
                {
                    Gia_Obj_t * pAnd = Gia_ManObj( pGia, iMaj );
                    Vec_IntWriteEntry( vMap, iXor, 0 );
                    Vec_IntWriteEntry( vMap, iMaj, 0 );
                    Vec_IntWriteEntry( vMap, Gia_ObjFaninId0(pAnd, iMaj), 1 );
                    Vec_IntWriteEntry( vMap, Gia_ObjFaninId1(pAnd, iMaj), 1 );
                    Vec_IntPush( vRecord, Abc_Var2Lit2(i, 1) );
                    fFound = 1;
                    fFoundAll = 1;
                    if ( fVeryVerbose )
                        printf( "Recognizing (%d %d) => HA(%d %d)\n", iXor, iMaj, Gia_ObjFaninId0(pAnd, iMaj), Gia_ObjFaninId1(pAnd, iMaj) );
                }
            }
            break; // only one iter!
        } while ( fFound );
        if ( fFoundAll )
            continue;
/*
        // find the last one
        Vec_IntForEachEntryReverse( vMap, Entry, iAnd )
            if ( Entry && Gia_ObjIsAnd(Gia_ManObj(pGia, iAnd)) )//&& Vec_IntFind(vFadds, iAnd) == -1 )//&& Vec_IntFind(vHadds, iAnd) == -1 )
            {
                Gia_Obj_t * pFan0, * pFan1, * pAnd = Gia_ManObj( pGia, iAnd );
                if ( !Gia_ObjRecognizeExor(pAnd, &pFan0, &pFan1) )
                {
                    Vec_IntWriteEntry( vMap, iAnd, 0 );
                    Vec_IntWriteEntry( vMap, Gia_ObjFaninId0(pAnd, iAnd), 1 );
                    Vec_IntWriteEntry( vMap, Gia_ObjFaninId1(pAnd, iAnd), 1 );
                    Vec_IntPush( vRecord, Abc_Var2Lit2(iAnd, 0) );
                }
                else
                {
                    Vec_IntWriteEntry( vMap, iAnd, 0 );
                    Vec_IntWriteEntry( vMap, Gia_ObjId(pGia, pFan0), 1 );
                    Vec_IntWriteEntry( vMap, Gia_ObjId(pGia, pFan1), 1 );
                    Vec_IntPush( vRecord, Abc_Var2Lit2(iAnd, 0) );
                    Vec_IntPush( vRecord, Abc_Var2Lit2(Gia_ObjFaninId0(pAnd, iAnd), 0) );
                    Vec_IntPush( vRecord, Abc_Var2Lit2(Gia_ObjFaninId1(pAnd, iAnd), 0) );
                    printf( "Recognizing %d => XOR(%d %d)\n", iAnd, Gia_ObjId(pGia, pFan0), Gia_ObjId(pGia, pFan1) );
                }
                fFoundAll = 1;
                if ( fVeryVerbose )
                    printf( "Recognizing %d => AND(%d %d)\n", iAnd, Gia_ObjFaninId0(pAnd, iAnd), Gia_ObjFaninId1(pAnd, iAnd) );
                break;
            }
*/
    }
    //Vec_IntPrint( vMap );

    // collect remaining ones
    vLeft = Vec_IntAlloc( 100 );
    Vec_IntForEachEntry( vMap, Entry, i )
        if ( Entry && Gia_ObjIsAnd(Gia_ManObj(pGia, i)) )
            Vec_IntPush( vLeft, i );
    Vec_IntFree( vMap );

    // collect them in the topo order
    vRecord2 = Vec_IntAlloc( 100 );
    Gia_ManIncrementTravId( pGia );
    Gia_ManCollectAnds( pGia, Vec_IntArray(vLeft), Vec_IntSize(vLeft), vRecord2, NULL );
    Vec_IntForEachEntry( vRecord2, iAnd, i )
        Vec_IntWriteEntry( vRecord2, i, Abc_Var2Lit2(iAnd, 0) );

    // dump remaining nodes as an AIG
    if ( fDumpLeftOver )
    {        
        Gia_Man_t * pNew;
        pNew = Gia_ManDupAndCones( pGia, Vec_IntArray(vLeft), Vec_IntSize(vLeft), 0 );
        Gia_AigerWrite( pNew, "leftover.aig", 0, 0 );
        printf( "Leftover AIG with %d nodes is dumped into file \"%s\".\n", Gia_ManAndNum(pNew), "leftover.aig" );
        Gia_ManStop( pNew );
    }
    Vec_IntFree( vLeft );

    Vec_IntReverseOrder( vRecord );
    Vec_IntAppend( vRecord2, vRecord );
    Vec_IntFree( vRecord );
    return vRecord2;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Gia_PolynReorder( Gia_Man_t * pGia, int fVerbose, int fVeryVerbose )
{
    Vec_Int_t * vFadds  = Gia_ManDetectFullAdders( pGia, fVeryVerbose, NULL );
    Vec_Int_t * vHadds  = Gia_ManDetectHalfAdders( pGia, fVeryVerbose );
    Vec_Int_t * vRecord = Gia_PolynFindOrder( pGia, vFadds, vHadds, fVerbose, fVeryVerbose );
    Vec_Int_t * vOrder  = Vec_IntAlloc( Gia_ManAndNum(pGia) );
    Vec_Int_t * vOrder2 = Vec_IntStart( Gia_ManObjNum(pGia) );
    int i, k, Entry;

    // collect nodes
    Gia_ManIncrementTravId( pGia );
    Vec_IntForEachEntry( vRecord, Entry, i )
    {
        int Node = Abc_Lit2Var2(Entry);
        int Attr = Abc_Lit2Att2(Entry);
        if ( Attr == 2 )
        {
            int * pFanins = Vec_IntEntryP( vFadds, 5*Node );
            for ( k = 3; k < 5; k++ )
                Gia_ManCollectAnds_rec( pGia, pFanins[k], vOrder );
        }
        else if ( Attr == 1 )
        {
            int * pFanins = Vec_IntEntryP( vHadds, 2*Node );
            for ( k = 0; k < 2; k++ )
                Gia_ManCollectAnds_rec( pGia, pFanins[k], vOrder );
        }
        else
            Gia_ManCollectAnds_rec( pGia, Node, vOrder );
        //printf( "Order = %d.  Node = %d.  Size = %d ", i, Node, Vec_IntSize(vOrder) );
    }
    //printf( "\n" );
    //assert( Vec_IntSize(vOrder) == Gia_ManAndNum(pGia) );

    // remap order
    Gia_ManForEachCiId( pGia, Entry, i )
        Vec_IntWriteEntry( vOrder2, Entry, 1+i );
    Vec_IntForEachEntry( vOrder, Entry, i )
        Vec_IntWriteEntry( vOrder2, Entry, 1+Gia_ManCiNum(pGia)+i );
    //Vec_IntPrint( vOrder );

    Vec_IntFree( vRecord );
    Vec_IntFree( vFadds );
    Vec_IntFree( vHadds );
    Vec_IntFree( vOrder );
    return vOrder2;
}


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


ABC_NAMESPACE_IMPL_END