abcTim.c

Go to the documentation of this file.

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

  FileName    [abcTim.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Network and node package.]

  Synopsis    [Testing hierarchy/timing manager.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "base/abc/abc.h"
#include "aig/gia/giaAig.h"
#include "misc/tim/tim.h"
#include "opt/dar/dar.h"
#include "proof/dch/dch.h"
#include "base/main/main.h"

ABC_NAMESPACE_IMPL_START

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

#define TIM_TEST_BOX_RATIO 200

// assume that every TIM_TEST_BOX_RATIO'th object is a white box
static inline int Abc_NodeIsWhiteBox( Abc_Obj_t * pObj )  { assert( Abc_ObjIsNode(pObj) ); return Abc_ObjId(pObj) % TIM_TEST_BOX_RATIO == 0 && Abc_ObjFaninNum(pObj) > 0 && Abc_ObjFaninNum(pObj) < 10; }

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

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

  Synopsis    [Derives GIA for the output of the local function of one node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkTestTimNodeStrash_rec( Gia_Man_t * pGia, Hop_Obj_t * pObj )
{
    assert( !Hop_IsComplement(pObj) );
    if ( !Hop_ObjIsNode(pObj) || Hop_ObjIsMarkA(pObj) )
        return;
    Abc_NtkTestTimNodeStrash_rec( pGia, Hop_ObjFanin0(pObj) ); 
    Abc_NtkTestTimNodeStrash_rec( pGia, Hop_ObjFanin1(pObj) );
    pObj->iData = Gia_ManHashAnd( pGia, Hop_ObjChild0CopyI(pObj), Hop_ObjChild1CopyI(pObj) );
    assert( !Hop_ObjIsMarkA(pObj) ); // loop detection
    Hop_ObjSetMarkA( pObj );
}
int Abc_NtkTestTimNodeStrash( Gia_Man_t * pGia, Abc_Obj_t * pNode )
{
    Hop_Man_t * pMan;
    Hop_Obj_t * pRoot;
    Abc_Obj_t * pFanin;
    int i;
    assert( Abc_ObjIsNode(pNode) );
    assert( Abc_NtkIsAigLogic(pNode->pNtk) );
    // get the local AIG manager and the local root node
    pMan = (Hop_Man_t *)pNode->pNtk->pManFunc;
    pRoot = (Hop_Obj_t *)pNode->pData;
    // check the constant case
    if ( Abc_NodeIsConst(pNode) || Hop_Regular(pRoot) == Hop_ManConst1(pMan) )
        return !Hop_IsComplement(pRoot);
    // set elementary variables
    Abc_ObjForEachFanin( pNode, pFanin, i )
        Hop_IthVar(pMan, i)->iData = pFanin->iTemp;
    // strash the AIG of this node
    Abc_NtkTestTimNodeStrash_rec( pGia, Hop_Regular(pRoot) );
    Hop_ConeUnmark_rec( Hop_Regular(pRoot) );
    // return the final node with complement if needed
    return Abc_LitNotCond( Hop_Regular(pRoot)->iData, Hop_IsComplement(pRoot) );
}


#if 0 

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

  Synopsis    [Derives GIA manager using special pins to denote box boundaries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Abc_NtkTestPinDeriveGia( Abc_Ntk_t * pNtk, int fWhiteBoxOnly, int fVerbose )
{
    Gia_Man_t * pTemp;
    Gia_Man_t * pGia = NULL;
    Vec_Ptr_t * vNodes;
    Abc_Obj_t * pObj, * pFanin;
    int i, k, iPinLit = 0;
    // prepare logic network
    assert( Abc_NtkIsLogic(pNtk) );
    Abc_NtkToAig( pNtk );
    // construct GIA
    Abc_NtkFillTemp( pNtk );
    pGia = Gia_ManStart( Abc_NtkObjNumMax(pNtk) );
    Gia_ManHashAlloc( pGia );
    // create primary inputs
    Abc_NtkForEachCi( pNtk, pObj, i )
        pObj->iTemp = Gia_ManAppendCi(pGia);
    // create internal nodes in a topologic order from white boxes
    vNodes = Abc_NtkDfs( pNtk, 0 );
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
    {
        // input side
        if ( !fWhiteBoxOnly || Abc_NodeIsWhiteBox(pObj) )
        {
            // create special pintype for this node
            iPinLit = Gia_ManAppendPinType( pGia, 1 );
            // create input pins
            Abc_ObjForEachFanin( pObj, pFanin, k )
                pFanin->iTemp = Gia_ManAppendAnd( pGia, pFanin->iTemp, iPinLit );
        }
        // perform GIA construction
        pObj->iTemp = Abc_NtkTestTimNodeStrash( pGia, pObj );
        // output side
        if ( !fWhiteBoxOnly || Abc_NodeIsWhiteBox(pObj) )
        {
            // create special pintype for this node
            iPinLit = Gia_ManAppendPinType( pGia, 1 );
            // create output pins
            pObj->iTemp = Gia_ManAppendAnd( pGia, pObj->iTemp, iPinLit );
        }
    }
    Vec_PtrFree( vNodes );
    // create primary outputs
    Abc_NtkForEachCo( pNtk, pObj, i )
        pObj->iTemp = Gia_ManAppendCo( pGia, Abc_ObjFanin0(pObj)->iTemp );
    // finalize GIA
    Gia_ManHashStop( pGia );
    Gia_ManSetRegNum( pGia, 0 );
    // clean up GIA
    pGia = Gia_ManCleanup( pTemp = pGia );
    Gia_ManStop( pTemp );
    return pGia;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkTestPinGia( Abc_Ntk_t * pNtk, int fWhiteBoxOnly, int fVerbose )
{
    Gia_Man_t * pGia;
    char * pFileName = "testpin.aig";
    pGia = Abc_NtkTestPinDeriveGia( pNtk, fWhiteBoxOnly, fVerbose );
    Gia_AigerWrite( pGia, pFileName, 0, 0 );
    Gia_ManStop( pGia );
    printf( "AIG with pins derived from mapped network \"%s\" was written into file \"%s\".\n", 
        Abc_NtkName(pNtk), pFileName );
}

#endif

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

  Synopsis    [Collect nodes reachable from this box.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkTestTimCollectCone_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vNodes )
{
    Abc_Obj_t * pFanin;
    int i;
    if ( Abc_NodeIsTravIdCurrent( pObj ) )
        return;
    Abc_NodeSetTravIdCurrent( pObj );
    if ( Abc_ObjIsCi(pObj) )
        return;
    assert( Abc_ObjIsNode( pObj ) );
    Abc_ObjForEachFanin( pObj, pFanin, i )
        Abc_NtkTestTimCollectCone_rec( pFanin, vNodes );
    Vec_PtrPush( vNodes, pObj );
}
Vec_Ptr_t * Abc_NtkTestTimCollectCone( Abc_Ntk_t * pNtk, Abc_Obj_t * pObj )
{
    Vec_Ptr_t * vCone = Vec_PtrAlloc( 1000 );
    if ( pObj != NULL )
    {
        // collect for one node
        assert( Abc_ObjIsNode(pObj) );
        assert( !Abc_NodeIsTravIdCurrent( pObj ) );
        Abc_NtkTestTimCollectCone_rec( pObj, vCone );
        // remove the node because it is a white box
        Vec_PtrPop( vCone );
    }
    else
    {
        // collect for all COs
        Abc_Obj_t * pObj;
        int i;
        Abc_NtkForEachCo( pNtk, pObj, i )
            Abc_NtkTestTimCollectCone_rec( Abc_ObjFanin0(pObj), vCone );
    }
    return vCone;

}

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

  Synopsis    [Create arrival times]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Flt_t * Abc_NtkTestCreateArrivals( int nInputs )
{
    Vec_Flt_t * p;
    int i;
    p = Vec_FltAlloc( nInputs );
    for ( i = 0; i < nInputs; i++ )
        Vec_FltPush( p, 1.0*(i % 10) );
    return p;
}
Vec_Flt_t * Abc_NtkTestCreateRequired( int nOutputs )
{
    Vec_Flt_t * p;
    int i;
    p = Vec_FltAlloc( nOutputs );
    for ( i = 0; i < nOutputs; i++ )
        Vec_FltPush( p, 100.0 + 1.0*i );
    return p;
}

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

  Synopsis    [Derives GIA manager together with the hierachy manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Abc_NtkTestTimDeriveGia( Abc_Ntk_t * pNtk, int fVerbose )
{
    Gia_Man_t * pTemp;
    Gia_Man_t * pGia = NULL;
    Gia_Man_t * pHoles = NULL;
    Tim_Man_t * pTim = NULL;
    Vec_Int_t * vGiaCoLits, * vGiaCoLits2;
    Vec_Flt_t * vArrTimes, * vReqTimes;
    Abc_Obj_t * pObj, * pFanin;
    int i, k, Entry, curPi, curPo, BoxUniqueId;
    int nBoxFaninMax = 0;
    assert( Abc_NtkIsTopo(pNtk) );
    Abc_NtkFillTemp( pNtk );

    // create white boxes
    curPi = Abc_NtkCiNum(pNtk);
    curPo = Abc_NtkCoNum(pNtk);
    Abc_NtkForEachNode( pNtk, pObj, i )
    {
        pObj->fMarkA = Abc_NodeIsWhiteBox( pObj );
        if ( !pObj->fMarkA )
            continue;
        nBoxFaninMax  = Abc_MaxInt( nBoxFaninMax, Abc_ObjFaninNum(pObj) );
        curPi++;
        curPo += Abc_ObjFaninNum(pObj);
        if ( fVerbose )
            printf( "Selecting node %6d as white boxes with %d inputs and %d output.\n", i, Abc_ObjFaninNum(pObj), 1 );
    }

    // construct GIA
    pGia = Gia_ManStart( Abc_NtkObjNumMax(pNtk) );
    pHoles = Gia_ManStart( 1000 );
    for ( i = 0; i < curPi; i++ )
        Gia_ManAppendCi(pGia);
    for ( i = 0; i < nBoxFaninMax; i++ )
        Gia_ManAppendCi(pHoles);
    Gia_ManHashAlloc( pGia );
    Gia_ManHashAlloc( pHoles );

    // construct the timing manager
    pTim = Tim_ManStart( curPi, curPo );

    // assign primary inputs
    curPi = 0;
    curPo = 0;
    Abc_NtkForEachCi( pNtk, pObj, i )
        pObj->iTemp = Abc_Var2Lit( Gia_ObjId(pGia, Gia_ManCi(pGia, curPi++)), 0 );
    // create internal nodes in a topologic order from white boxes
    vGiaCoLits = Vec_IntAlloc( 1000 );
    vGiaCoLits2 = Vec_IntAlloc( 1000 );
    Abc_NtkForEachNode( pNtk, pObj, i )
    {
        if ( !pObj->fMarkA ) // not a white box
        {
            pObj->iTemp = Abc_NtkTestTimNodeStrash( pGia, pObj );
            continue;
        }
        // create box
        BoxUniqueId = Abc_ObjFaninNum(pObj); // in this case, the node size is the ID of its delay table
        Tim_ManCreateBox( pTim, curPo, Abc_ObjFaninNum(pObj), curPi, 1, BoxUniqueId );
        curPo += Abc_ObjFaninNum(pObj);

        // handle box inputs
        Abc_ObjForEachFanin( pObj, pFanin, k )
        {
            // save CO drivers for the AIG
            Vec_IntPush( vGiaCoLits, pFanin->iTemp );
            // load CI nodes for the Holes
            pFanin->iTemp = Abc_Var2Lit( Gia_ObjId(pHoles, Gia_ManCi(pHoles, k)), 0 );
        }

        // handle logic of the box
        pObj->iTemp = Abc_NtkTestTimNodeStrash( pHoles, pObj );

        // handle box outputs
        // save CO drivers for the Holes
        Vec_IntPush( vGiaCoLits2, pObj->iTemp );
//        Gia_ManAppendCo( pHoles, pObj->iTemp );
        // load CO drivers for the AIG
        pObj->iTemp = Abc_Var2Lit( Gia_ObjId(pGia, Gia_ManCi(pGia, curPi++)), 0 );
    }
    Abc_NtkCleanMarkA( pNtk );
    // create COs of the AIG
    Abc_NtkForEachCo( pNtk, pObj, i )
        Gia_ManAppendCo( pGia, Abc_ObjFanin0(pObj)->iTemp );
    Vec_IntForEachEntry( vGiaCoLits, Entry, i )
        Gia_ManAppendCo( pGia, Entry );
    Vec_IntFree( vGiaCoLits );
    // second AIG
    Vec_IntForEachEntry( vGiaCoLits2, Entry, i )
        Gia_ManAppendCo( pHoles, Entry );
    Vec_IntFree( vGiaCoLits2 );
    // check parameters
    curPo += Abc_NtkPoNum( pNtk );
    assert( curPi == Gia_ManPiNum(pGia) );
    assert( curPo == Gia_ManPoNum(pGia) );
    // finalize GIA
    Gia_ManHashStop( pGia );
    Gia_ManSetRegNum( pGia, 0 );
    Gia_ManHashStop( pHoles );
    Gia_ManSetRegNum( pHoles, 0 );

    // clean up GIA
    pGia = Gia_ManCleanup( pTemp = pGia );
    Gia_ManStop( pTemp );
    pHoles = Gia_ManCleanup( pTemp = pHoles );
    Gia_ManStop( pTemp );

    // attach the timing manager
    assert( pGia->pManTime == NULL );
    pGia->pManTime = pTim;

    // derive hierarchy manager from box info and input/output arrival/required info
    vArrTimes = Abc_NtkTestCreateArrivals( Abc_NtkPiNum(pNtk) );
    vReqTimes = Abc_NtkTestCreateRequired( Abc_NtkPoNum(pNtk) );

    Tim_ManPrint( (Tim_Man_t *)pGia->pManTime );
    Tim_ManCreate( (Tim_Man_t *)pGia->pManTime, Abc_FrameReadLibBox(), vArrTimes, vReqTimes );
    Tim_ManPrint( (Tim_Man_t *)pGia->pManTime );

    Vec_FltFree( vArrTimes );
    Vec_FltFree( vReqTimes );

Gia_AigerWrite( pHoles, "holes00.aig", 0, 0 );

    // return 
    pGia->pAigExtra = pHoles;
    return pGia;
}


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

  Synopsis    [Performs synthesis with or without structural choices.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Abc_NtkTestTimPerformSynthesis( Gia_Man_t * p, int fChoices )
{
    Gia_Man_t * pGia;
    Aig_Man_t * pNew, * pTemp;
    Dch_Pars_t Pars, * pPars = &Pars;
    Dch_ManSetDefaultParams( pPars );
    pNew = Gia_ManToAig( p, 0 );
    if ( fChoices )
        pNew = Dar_ManChoiceNew( pNew, pPars );
    else
    {
        pNew = Dar_ManCompress2( pTemp = pNew, 1, 1, 1, 0, 0 );
        Aig_ManStop( pTemp );
    }
    pGia = Gia_ManFromAig( pNew );
    Aig_ManStop( pNew );
    return pGia;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManVerifyChoices( Gia_Man_t * p )
{
    Gia_Obj_t * pObj;
    int i, iRepr, iNode, fProb = 0;
    assert( p->pReprs );

    // mark nodes 
    Gia_ManCleanMark0(p);
    Gia_ManForEachClass( p, iRepr )
        Gia_ClassForEachObj1( p, iRepr, iNode )
        {
            if ( Gia_ObjIsHead(p, iNode) )
                printf( "Member %d of choice class %d is a representative.\n", iNode, iRepr ), fProb = 1;
            if ( Gia_ManObj( p, iNode )->fMark0 == 1 )
                printf( "Node %d participates in more than one choice node.\n", iNode ), fProb = 1;
            Gia_ManObj( p, iNode )->fMark0 = 1;
        }
    Gia_ManCleanMark0(p);

    Gia_ManForEachObj( p, pObj, i )
    {
        if ( Gia_ObjIsAnd(pObj) )
        {
            if ( Gia_ObjHasRepr(p, Gia_ObjFaninId0(pObj, i)) )
                printf( "Fanin 0 of AND node %d has a repr.\n", i ), fProb = 1;
            if ( Gia_ObjHasRepr(p, Gia_ObjFaninId1(pObj, i)) )
                printf( "Fanin 1 of AND node %d has a repr.\n", i ), fProb = 1;
        }
        else if ( Gia_ObjIsCo(pObj) )
        {
            if ( Gia_ObjHasRepr(p, Gia_ObjFaninId0(pObj, i)) )
                printf( "Fanin 0 of CO node %d has a repr.\n", i ), fProb = 1;
        }
    }
//    if ( !fProb )
//        printf( "GIA with choices is correct.\n" );
}

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

  Synopsis    [Reverse the order of nodes in equiv classes.]

  Description [If the flag is 1, assumed current increasing order ]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManReverseClasses( Gia_Man_t * p, int fNowIncreasing )
{
    Vec_Int_t * vCollected;
    Vec_Int_t * vClass;
    int i, k, iRepr, iNode, iPrev;
    // collect classes
    vCollected = Vec_IntAlloc( 100 );
    Gia_ManForEachClass( p, iRepr )
        Vec_IntPush( vCollected, iRepr );
    // correct each class
    vClass = Vec_IntAlloc( 100 );
    Vec_IntForEachEntry( vCollected, iRepr, i )
    {
        Vec_IntClear( vClass );
        Vec_IntPush( vClass, iRepr );
        Gia_ClassForEachObj1( p, iRepr, iNode )
        {
            if ( fNowIncreasing )
                assert( iRepr < iNode );
            else
                assert( iRepr > iNode );
            Vec_IntPush( vClass, iNode );
        }
//        if ( !fNowIncreasing )
//            Vec_IntSort( vClass, 1 );
        // reverse the class
        iPrev = 0;
        iRepr = Vec_IntEntryLast( vClass );
        Vec_IntForEachEntry( vClass, iNode, k )
        {
            if ( fNowIncreasing )
                Gia_ObjSetReprRev( p, iNode, iNode == iRepr ? GIA_VOID : iRepr );
            else
                Gia_ObjSetRepr( p, iNode, iNode == iRepr ? GIA_VOID : iRepr );
            Gia_ObjSetNext( p, iNode, iPrev );
            iPrev = iNode;
        }
    }
    Vec_IntFree( vCollected );
    Vec_IntFree( vClass );
    // verify
    Gia_ManForEachClass( p, iRepr )
        Gia_ClassForEachObj1( p, iRepr, iNode )
            if ( fNowIncreasing )
                assert( Gia_ObjRepr(p, iNode) == iRepr && iRepr > iNode );
            else
                assert( Gia_ObjRepr(p, iNode) == iRepr && iRepr < iNode );
}

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

  Synopsis    [Tests the hierarchy-timing manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkTestTimByWritingFile( Gia_Man_t * pGia, char * pFileName )
{
    Gia_Man_t * pGia2;

    // normalize choices
    if ( Gia_ManHasChoices(pGia) )
    {
        Gia_ManVerifyChoices( pGia );
        Gia_ManReverseClasses( pGia, 0 );
    }
    // write file
    Gia_AigerWrite( pGia, pFileName, 0, 0 );
    // unnormalize choices
    if ( Gia_ManHasChoices(pGia) )
        Gia_ManReverseClasses( pGia, 1 );

    // read file
    pGia2 = Gia_AigerRead( pFileName, 1, 1 );

    // normalize choices
    if ( Gia_ManHasChoices(pGia2) )
    {
        Gia_ManVerifyChoices( pGia2 );
        Gia_ManReverseClasses( pGia2, 1 );
    }

    // compare resulting managers
    if ( Gia_ManCompare( pGia, pGia2 ) )
        printf( "Verification suceessful.\n" );

    Gia_ManStop( pGia2 );
}

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

  Synopsis    [Tests construction and serialization.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkTestTim( Abc_Ntk_t * pNtk, int fVerbose )
{
    int fUseChoices = 0;
    Gia_Man_t * pGia, * pTemp;

    // this test only works for a logic network (for example, network with LUT mapping)
    assert( Abc_NtkIsLogic(pNtk) );
    // make sure local functions of the nodes are in the AIG form
    Abc_NtkToAig( pNtk );

    // create GIA manager (pGia) with hierarhy/timing manager attached (pGia->pManTime)
    // while assuming that some nodes are white boxes (see Abc_NodeIsWhiteBox)
    pGia = Abc_NtkTestTimDeriveGia( pNtk, fVerbose );
    printf( "Created GIA manager for network with %d white boxes.\n", Tim_ManBoxNum((Tim_Man_t *)pGia->pManTime) );

    // print the timing manager
    if ( fVerbose )
        Tim_ManPrint( (Tim_Man_t *)pGia->pManTime );

    // test writing both managers into a file and reading them back
    Abc_NtkTestTimByWritingFile( pGia, "test1.aig" );

    // perform synthesis
    pGia = Abc_NtkTestTimPerformSynthesis( pTemp = pGia, fUseChoices );
    Gia_ManStop( pTemp );

    // test writing both managers into a file and reading them back
    Abc_NtkTestTimByWritingFile( pGia, "test2.aig" );

    Gia_ManStop( pGia );
}




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


ABC_NAMESPACE_IMPL_END