cgtAig.c

Go to the documentation of this file.

 
#include "cgtInt.h"
 
ABC_NAMESPACE_IMPL_START
 



void Cgt_ManDetectCandidates_rec( Aig_Man_t * pAig, Vec_Int_t * vUseful, Aig_Obj_t * pObj, int nLevelMax, Vec_Ptr_t * vCands )
{
    if ( Aig_ObjIsTravIdCurrent(pAig, pObj) )
        return;
    Aig_ObjSetTravIdCurrent(pAig, pObj);
    if ( Aig_ObjIsNode(pObj) )
    {
        Cgt_ManDetectCandidates_rec( pAig, vUseful, Aig_ObjFanin0(pObj), nLevelMax, vCands );
        Cgt_ManDetectCandidates_rec( pAig, vUseful, Aig_ObjFanin1(pObj), nLevelMax, vCands );
    }
    if ( Aig_ObjLevel(pObj) <= nLevelMax && (vUseful == NULL || Vec_IntEntry(vUseful, Aig_ObjId(pObj))) )
        Vec_PtrPush( vCands, pObj );
}

void Cgt_ManDetectCandidates( Aig_Man_t * pAig, Vec_Int_t * vUseful, Aig_Obj_t * pObj, int nLevelMax, Vec_Ptr_t * vCands )
{
    Vec_PtrClear( vCands );
    if ( !Aig_ObjIsNode(pObj) )
        return;
    Aig_ManIncrementTravId( pAig );
    Cgt_ManDetectCandidates_rec( pAig, vUseful, pObj, nLevelMax, vCands );
}

void Cgt_ManDetectFanout_rec( Aig_Man_t * pAig, Aig_Obj_t * pObj, int nOdcMax, Vec_Ptr_t * vFanout )
{
    Aig_Obj_t * pFanout;
    int f, iFanout = -1;
    if ( Aig_ObjIsCo(pObj) || Aig_ObjLevel(pObj) > nOdcMax )
        return;
    if ( Aig_ObjIsTravIdCurrent(pAig, pObj) )
        return;
    Aig_ObjSetTravIdCurrent(pAig, pObj);
    Vec_PtrPush( vFanout, pObj );
    Aig_ObjForEachFanout( pAig, pObj, pFanout, iFanout, f )
        Cgt_ManDetectFanout_rec( pAig, pFanout, nOdcMax, vFanout );
}

void Cgt_ManDetectFanout( Aig_Man_t * pAig, Aig_Obj_t * pObj, int nOdcMax, Vec_Ptr_t * vFanout )
{
    Aig_Obj_t * pFanout;
    int i, k, f, iFanout = -1;
    // collect visited nodes
    Vec_PtrClear( vFanout );
    Aig_ManIncrementTravId( pAig );
    Cgt_ManDetectFanout_rec( pAig, pObj, nOdcMax, vFanout );
    // remove those nodes whose fanout is included
    k = 0;
    Vec_PtrForEachEntry( Aig_Obj_t *, vFanout, pObj, i )
    {
        // go through the fanouts of this node
        Aig_ObjForEachFanout( pAig, pObj, pFanout, iFanout, f )
            if ( !Aig_ObjIsTravIdCurrent(pAig, pFanout) )
                break;
        if ( f == Aig_ObjRefs(pObj) ) // all fanouts are included
            continue;
        Vec_PtrWriteEntry( vFanout, k++, pObj );
    }
    Vec_PtrShrink( vFanout, k );
    Vec_PtrSort( vFanout, (int (*)(const void *, const void *))Aig_ObjCompareIdIncrease );
    assert( Vec_PtrSize(vFanout) > 0 );
}

void Cgt_ManCollectVisited_rec( Aig_Man_t * pAig, Aig_Obj_t * pObj, Vec_Ptr_t * vVisited )
{
    if ( Aig_ObjIsCi(pObj) )
        return;
    if ( Aig_ObjIsTravIdCurrent(pAig, pObj) )
        return;
    Aig_ObjSetTravIdCurrent(pAig, pObj);
    assert( Aig_ObjIsNode(pObj) );
    Cgt_ManCollectVisited_rec( pAig, Aig_ObjFanin0(pObj), vVisited );
    Cgt_ManCollectVisited_rec( pAig, Aig_ObjFanin1(pObj), vVisited );
    Vec_PtrPush( vVisited, pObj );
}

void Cgt_ManCollectVisited( Aig_Man_t * pAig, Vec_Ptr_t * vFanout, Vec_Ptr_t * vVisited )
{
    Aig_Obj_t * pObj;
    int i;
    Vec_PtrClear( vVisited );
    Aig_ManIncrementTravId( pAig );
    Vec_PtrForEachEntry( Aig_Obj_t *, vFanout, pObj, i )
        Cgt_ManCollectVisited_rec( pAig, pObj, vVisited );
}

static inline Aig_Obj_t *  Aig_ObjChild0CopyVec( Vec_Ptr_t * vCopy, Aig_Obj_t * pObj )  
{ return Aig_NotCond((Aig_Obj_t *)Vec_PtrEntry(vCopy, Aig_ObjFaninId0(pObj)), Aig_ObjFaninC0(pObj));  }
static inline Aig_Obj_t *  Aig_ObjChild1CopyVec( Vec_Ptr_t * vCopy, Aig_Obj_t * pObj )  
{ return Aig_NotCond((Aig_Obj_t *)Vec_PtrEntry(vCopy, Aig_ObjFaninId1(pObj)), Aig_ObjFaninC1(pObj));  }

Aig_Obj_t * Cgt_ManConstructCareCondition( Cgt_Man_t * p, Aig_Man_t * pNew, Aig_Obj_t * pObjLo, Vec_Ptr_t * vCopy0, Vec_Ptr_t * vCopy1 )
{
    Aig_Obj_t * pMiter, * pObj, * pTemp;
    int i;
    assert( Aig_ObjIsCi(pObjLo) );
    // detect nodes and their cone
    Cgt_ManDetectFanout( p->pAig, pObjLo, p->pPars->nOdcMax, p->vFanout );
    Cgt_ManCollectVisited( p->pAig, p->vFanout, p->vVisited );
    // add new variables if the observability condition depends on PI variables
    Vec_PtrForEachEntry( Aig_Obj_t *, p->vVisited, pObj, i )
    {
        assert( Aig_ObjIsNode(pObj) );
        if ( Saig_ObjIsPi(p->pAig, Aig_ObjFanin0(pObj)) && Vec_PtrEntry(vCopy0, Aig_ObjFaninId0(pObj)) == NULL )
        {
            pTemp = Aig_ObjCreateCi( pNew );
            Vec_PtrWriteEntry( vCopy0, Aig_ObjFaninId0(pObj), pTemp );
            Vec_PtrWriteEntry( vCopy1, Aig_ObjFaninId0(pObj), pTemp );
        }
        if ( Saig_ObjIsPi(p->pAig, Aig_ObjFanin1(pObj)) && Vec_PtrEntry(vCopy0, Aig_ObjFaninId1(pObj)) == NULL )
        {
            pTemp = Aig_ObjCreateCi( pNew );
            Vec_PtrWriteEntry( vCopy0, Aig_ObjFaninId1(pObj), pTemp );
            Vec_PtrWriteEntry( vCopy1, Aig_ObjFaninId1(pObj), pTemp );
        }
    }
    // construct AIGs for the nodes
    Vec_PtrForEachEntry( Aig_Obj_t *, p->vVisited, pObj, i )
    {
        pTemp = Aig_And( pNew, Aig_ObjChild0CopyVec(vCopy0, pObj), Aig_ObjChild1CopyVec(vCopy0, pObj) );
        Vec_PtrWriteEntry( vCopy0, Aig_ObjId(pObj), pTemp );
        pTemp = Aig_And( pNew, Aig_ObjChild0CopyVec(vCopy1, pObj), Aig_ObjChild1CopyVec(vCopy1, pObj) );
        Vec_PtrWriteEntry( vCopy1, Aig_ObjId(pObj), pTemp );
    }
    // construct the care miter
    pMiter = Aig_ManConst0( pNew );
    Vec_PtrForEachEntry( Aig_Obj_t *, p->vFanout, pObj, i )
    {
        pTemp = Aig_Exor( pNew, (Aig_Obj_t *)Vec_PtrEntry(vCopy0, Aig_ObjId(pObj)), (Aig_Obj_t *)Vec_PtrEntry(vCopy1, Aig_ObjId(pObj)) );
        pMiter = Aig_Or( pNew, pMiter, pTemp );
    }
    return pMiter;
}

Aig_Man_t * Cgt_ManDeriveAigForGating( Cgt_Man_t * p )
{
    Aig_Man_t * pNew;
    Aig_Obj_t * pObj, * pObjLi, * pObjLo, * pCare, * pMiter;
    Vec_Ptr_t * vCopy0, * vCopy1;
    int i;
    assert( Aig_ManRegNum(p->pAig) );
    pNew = Aig_ManStart( Aig_ManObjNumMax(p->pAig) );
    pNew->pName = Abc_UtilStrsav( "CG_miter" );
    // build the first frame
    Aig_ManConst1(p->pAig)->pData = Aig_ManConst1(pNew);
    Aig_ManForEachCi( p->pAig, pObj, i )
        pObj->pData = Aig_ObjCreateCi( pNew );
    Aig_ManForEachNode( p->pAig, pObj, i )
        pObj->pData = Aig_And( pNew, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) );
//    Saig_ManForEachPo( p->pAig, pObj, i )
//        pObj->pData = Aig_ObjCreateCo( pNew, Aig_ObjChild0Copy(pObj) );
    if ( p->pPars->nOdcMax > 0 )
    {
        // create storage for observability conditions
        vCopy0 = Vec_PtrStart( Aig_ManObjNumMax(p->pAig) );
        vCopy1 = Vec_PtrStart( Aig_ManObjNumMax(p->pAig) );
        // initialize register outputs
        Saig_ManForEachLiLo( p->pAig, pObjLi, pObjLo, i )
        {
            Vec_PtrWriteEntry( vCopy0, Aig_ObjId(pObjLo), Aig_ObjChild0Copy(pObjLi) );
            Vec_PtrWriteEntry( vCopy1, Aig_ObjId(pObjLo), Aig_ObjChild0Copy(pObjLi) );
        }
        // compute observability condition for each latch output
        Saig_ManForEachLiLo( p->pAig, pObjLi, pObjLo, i )
        {
            // set the constants
            Vec_PtrWriteEntry( vCopy0, Aig_ObjId(pObjLo), Aig_ManConst0(pNew) );
            Vec_PtrWriteEntry( vCopy1, Aig_ObjId(pObjLo), Aig_ManConst1(pNew) );
            // compute condition
            pCare = Cgt_ManConstructCareCondition( p, pNew, pObjLo, vCopy0, vCopy1 );
            // restore the values
            Vec_PtrWriteEntry( vCopy0, Aig_ObjId(pObjLo), Aig_ObjChild0Copy(pObjLi) );
            Vec_PtrWriteEntry( vCopy1, Aig_ObjId(pObjLo), Aig_ObjChild0Copy(pObjLi) );
            // compute the miter
            pMiter = Aig_Exor( pNew, (Aig_Obj_t *)pObjLo->pData, Aig_ObjChild0Copy(pObjLi) );
            pMiter = Aig_And( pNew, pMiter, pCare );
            pObjLi->pData = Aig_ObjCreateCo( pNew, pMiter );
        }
        Vec_PtrFree( vCopy0 );
        Vec_PtrFree( vCopy1 );
    }
    else
    {
        // construct clock-gating miters for each register input
        Saig_ManForEachLiLo( p->pAig, pObjLi, pObjLo, i )
        {
            pMiter = Aig_Exor( pNew, (Aig_Obj_t *)pObjLo->pData, Aig_ObjChild0Copy(pObjLi) );
            pObjLi->pData = Aig_ObjCreateCo( pNew, pMiter );
        }
    }
    Aig_ManCleanup( pNew );
    Aig_ManSetCioIds( pNew );
    return pNew;
}

Aig_Obj_t * Cgt_ManConstructCare_rec( Aig_Man_t * pCare, Aig_Obj_t * pObj, Aig_Man_t * pNew )
{
    Aig_Obj_t * pObj0, * pObj1;
    if ( Aig_ObjIsTravIdCurrent( pCare, pObj ) )
        return (Aig_Obj_t *)pObj->pData;
    Aig_ObjSetTravIdCurrent( pCare, pObj );
    if ( Aig_ObjIsCi(pObj) )
        return (Aig_Obj_t *)(pObj->pData = NULL);
    pObj0 = Cgt_ManConstructCare_rec( pCare, Aig_ObjFanin0(pObj), pNew );
    if ( pObj0 == NULL )
        return (Aig_Obj_t *)(pObj->pData = NULL);
    pObj1 = Cgt_ManConstructCare_rec( pCare, Aig_ObjFanin1(pObj), pNew );
    if ( pObj1 == NULL )
        return (Aig_Obj_t *)(pObj->pData = NULL);
    pObj0 = Aig_NotCond( pObj0, Aig_ObjFaninC0(pObj) );
    pObj1 = Aig_NotCond( pObj1, Aig_ObjFaninC1(pObj) );
    return (Aig_Obj_t *)(pObj->pData = Aig_And( pNew, pObj0, pObj1 ));
}

void Cgt_ManConstructCare( Aig_Man_t * pNew, Aig_Man_t * pCare, Vec_Vec_t * vSuppsInv, Vec_Ptr_t * vLeaves )
{
    Vec_Int_t * vOuts;
    Aig_Obj_t * pLeaf, * pPi, * pPo, * pObjAig;
    int i, k, iOut;
    // go through the PIs of the partition
    // label the corresponding PIs of the care set
    Aig_ManIncrementTravId( pCare );
    Vec_PtrForEachEntry( Aig_Obj_t *, vLeaves, pLeaf, i )
    {
        pPi = Aig_ManCi( pCare, Aig_ObjCioId(pLeaf) );
        Aig_ObjSetTravIdCurrent( pCare, pPi );
        pPi->pData = pLeaf->pData;
    }
    // construct the constraints
    Vec_PtrForEachEntry( Aig_Obj_t *, vLeaves, pLeaf, i )
    {
        vOuts = Vec_VecEntryInt( vSuppsInv, Aig_ObjCioId(pLeaf) );
        Vec_IntForEachEntry( vOuts, iOut, k )
        {
            pPo = Aig_ManCo( pCare, iOut );
            if ( Aig_ObjIsTravIdCurrent( pCare, pPo ) )
                continue;
            Aig_ObjSetTravIdCurrent( pCare, pPo );
            if ( Aig_ObjFanin0(pPo) == Aig_ManConst1(pCare) )
                continue;
            pObjAig = Cgt_ManConstructCare_rec( pCare, Aig_ObjFanin0(pPo), pNew );
            if ( pObjAig == NULL )
                continue;
            pObjAig = Aig_NotCond( pObjAig, Aig_ObjFaninC0(pPo) );
            Aig_ObjCreateCo( pNew, pObjAig );
        }
    }
}

Aig_Obj_t * Cgt_ManDupPartition_rec( Aig_Man_t * pNew, Aig_Man_t * pAig, Aig_Obj_t * pObj, Vec_Ptr_t * vLeaves )
{
    if ( Aig_ObjIsTravIdCurrent(pAig, pObj) )
        return (Aig_Obj_t *)pObj->pData;
    Aig_ObjSetTravIdCurrent(pAig, pObj);
    if ( Aig_ObjIsCi(pObj) )
    {
        pObj->pData = Aig_ObjCreateCi( pNew );
        Vec_PtrPush( vLeaves, pObj );
        return (Aig_Obj_t *)pObj->pData;
    }
    Cgt_ManDupPartition_rec( pNew, pAig, Aig_ObjFanin0(pObj), vLeaves );
    Cgt_ManDupPartition_rec( pNew, pAig, Aig_ObjFanin1(pObj), vLeaves );
    return (Aig_Obj_t *)(pObj->pData = Aig_And( pNew, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) ));
}

Aig_Man_t * Cgt_ManDupPartition( Aig_Man_t * pFrame, int nVarsMin, int nFlopsMin, int iStart, Aig_Man_t * pCare, Vec_Vec_t * vSuppsInv, int * pnOutputs )
{
    Vec_Ptr_t * vRoots, * vLeaves, * vPos;
    Aig_Man_t * pNew;
    Aig_Obj_t * pObj;
    int i;
    assert( Aig_ManRegNum(pFrame) == 0 );
    vRoots = Vec_PtrAlloc( 100 );
    vLeaves = Vec_PtrAlloc( 100 ); 
    vPos = Vec_PtrAlloc( 100 );
    pNew = Aig_ManStart( nVarsMin );
    pNew->pName = Abc_UtilStrsav( "partition" );
    Aig_ManIncrementTravId( pFrame );
    Aig_ManConst1(pFrame)->pData = Aig_ManConst1(pNew);
    Aig_ObjSetTravIdCurrent( pFrame, Aig_ManConst1(pFrame) );
    for ( i = iStart; i < iStart + nFlopsMin && i < Aig_ManCoNum(pFrame); i++ )
    {
        pObj = Aig_ManCo( pFrame, i );
        Cgt_ManDupPartition_rec( pNew, pFrame, Aig_ObjFanin0(pObj), vLeaves );
        Vec_PtrPush( vRoots, Aig_ObjChild0Copy(pObj) );
        Vec_PtrPush( vPos, pObj );
    }
    for ( ; Aig_ManObjNum(pNew) < nVarsMin && i < Aig_ManCoNum(pFrame); i++ )
    {
        pObj = Aig_ManCo( pFrame, i );
        Cgt_ManDupPartition_rec( pNew, pFrame, Aig_ObjFanin0(pObj), vLeaves );
        Vec_PtrPush( vRoots, Aig_ObjChild0Copy(pObj) );
        Vec_PtrPush( vPos, pObj );
    }
    assert( nFlopsMin >= Vec_PtrSize(vRoots) || Vec_PtrSize(vRoots) >= nFlopsMin );
    // create constaints
    if ( pCare )
        Cgt_ManConstructCare( pNew, pCare, vSuppsInv, vLeaves );
    // create POs
    Vec_PtrForEachEntry( Aig_Obj_t *, vPos, pObj, i )
        pObj->pData = (Aig_Obj_t *)Aig_ObjCreateCo( pNew, (Aig_Obj_t *)Vec_PtrEntry(vRoots, i) );
    if ( pnOutputs != NULL )
        *pnOutputs = Vec_PtrSize( vPos );
    Vec_PtrFree( vRoots );
    Vec_PtrFree( vLeaves );
    Vec_PtrFree( vPos );
    return pNew;
}

Aig_Obj_t * Cgt_ManBuildClockGate( Aig_Man_t * pNew, Vec_Ptr_t * vGates )
{
    Aig_Obj_t * pGate, * pTotal;
    int i;
    assert( Vec_PtrSize(vGates) > 0 );
    pTotal = Aig_ManConst0(pNew);
    Vec_PtrForEachEntry( Aig_Obj_t *, vGates, pGate, i )
    {
        if ( Aig_Regular(pGate)->pNext )
            pGate = Aig_NotCond( Aig_Regular(pGate)->pNext, Aig_IsComplement(pGate) );
        else
            pGate = Aig_NotCond( (Aig_Obj_t *)Aig_Regular(pGate)->pData, Aig_IsComplement(pGate) );
        pTotal = Aig_Or( pNew, pTotal, pGate );
    }
    return pTotal;
}

Aig_Man_t * Cgt_ManDeriveGatedAig( Aig_Man_t * pAig, Vec_Vec_t * vGates, int fReduce, int * pnUsedNodes )
{
    Aig_Man_t * pNew;
    Aig_Obj_t * pObj, * pObjNew, * pObjLi, * pObjLo, * pGateNew;
    Vec_Ptr_t * vOne;
    int i, k;
    Aig_ManCleanNext( pAig );
    // label nodes
    Vec_VecForEachEntry( Aig_Obj_t *, vGates, pObj, i, k )
    {
        if ( Aig_IsComplement(pObj) )
            Aig_Regular(pObj)->fMarkB = 1;
        else
            Aig_Regular(pObj)->fMarkA = 1;
    }
    // construct AIG
    assert( Aig_ManRegNum(pAig) );
    pNew = Aig_ManStart( Aig_ManObjNumMax(pAig) );
    pNew->pName = Abc_UtilStrsav( pAig->pName );
    pNew->pSpec = Abc_UtilStrsav( pAig->pSpec );
    Aig_ManConst1(pAig)->pData = Aig_ManConst1(pNew);
    Aig_ManForEachCi( pAig, pObj, i )
        pObj->pData = Aig_ObjCreateCi( pNew );
    if ( fReduce )
    {
        Aig_ManForEachNode( pAig, pObj, i )
        {
            assert( !(pObj->fMarkA && pObj->fMarkB) );
            pObj->pData = Aig_And( pNew, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) );
            if ( pObj->fMarkA )
            {
                pObj->pNext = (Aig_Obj_t *)pObj->pData;
                pObj->pData = Aig_ManConst0(pNew);
            }
            else if ( pObj->fMarkB )
            {
                pObj->pNext = (Aig_Obj_t *)pObj->pData;
                pObj->pData = Aig_ManConst1(pNew);
            }
        }
    }
    else
    {
        Aig_ManForEachNode( pAig, pObj, i )
            pObj->pData = Aig_And( pNew, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) );
    }
    if ( pnUsedNodes != NULL )
        *pnUsedNodes = Aig_ManNodeNum(pNew);
    Saig_ManForEachPo( pAig, pObj, i )
        pObj->pData = Aig_ObjCreateCo( pNew, Aig_ObjChild0Copy(pObj) );
    Saig_ManForEachLiLo( pAig, pObjLi, pObjLo, i )
    {
        vOne = Vec_VecEntry( vGates, i );
        if ( Vec_PtrSize(vOne) == 0 )
            pObjNew = Aig_ObjChild0Copy(pObjLi);
        else
        {
//            pGateNew = Aig_NotCond( Aig_Regular(pGate)->pData, Aig_IsComplement(pGate) );
            pGateNew = Cgt_ManBuildClockGate( pNew, vOne );
            pObjNew = Aig_Mux( pNew, pGateNew, (Aig_Obj_t *)pObjLo->pData, Aig_ObjChild0Copy(pObjLi) );
        }
        pObjLi->pData = Aig_ObjCreateCo( pNew, pObjNew );
    }
    Aig_ManCleanup( pNew );
    Aig_ManSetRegNum( pNew, Aig_ManRegNum(pAig) );
    // unlabel nodes
    Aig_ManCleanMarkAB( pAig );
    Aig_ManCleanNext( pAig );
    return pNew;
}

 
 
ABC_NAMESPACE_IMPL_END