aigPartReg.c File Reference

#include "aig.h"

Go to the source code of this file.

Data Structures
struct	Aig_ManPre_t_

Typedefs
typedef typedefABC_NAMESPACE_IMPL_START struct Aig_ManPre_t_	Aig_ManPre_t
	DECLARATIONS ///. More...

Functions
Aig_ManPre_t *	Aig_ManRegManStart (Aig_Man_t *pAig, int nPartSize)
	FUNCTION DEFINITIONS ///. More...
void	Aig_ManRegManStop (Aig_ManPre_t *p)
int	Aig_ManRegFindSeed (Aig_ManPre_t *p)
int	Aig_ManRegFindBestVar (Aig_ManPre_t *p)
void	Aig_ManRegPartitionAdd (Aig_ManPre_t *p, int iReg)
Vec_Ptr_t *	Aig_ManRegProjectOnehots (Aig_Man_t *pAig, Aig_Man_t *pPart, Vec_Ptr_t *vOnehots, int fVerbose)
Aig_Man_t *	Aig_ManRegCreatePart (Aig_Man_t *pAig, Vec_Int_t *vPart, int *pnCountPis, int *pnCountRegs, int **ppMapBack)
Vec_Ptr_t *	Aig_ManRegPartitionSmart (Aig_Man_t *pAig, int nPartSize)
Vec_Ptr_t *	Aig_ManRegPartitionSimple (Aig_Man_t *pAig, int nPartSize, int nOverSize)
void	Aig_ManPartDivide (Vec_Ptr_t *vResult, Vec_Int_t *vDomain, int nPartSize, int nOverSize)
void	Aig_ManRegPartitionTraverse_rec (Aig_Man_t *p, Aig_Obj_t *pObj, Vec_Ptr_t *vLos)
Vec_Ptr_t *	Aig_ManRegPartitionTraverse (Aig_Man_t *p)
Vec_Ptr_t *	Aig_ManRegPartitionLinear (Aig_Man_t *pAig, int nPartSize)

Typedef Documentation

typedef typedefABC_NAMESPACE_IMPL_START struct Aig_ManPre_t_ Aig_ManPre_t

DECLARATIONS ///.

CFile****************************************************************

FileName [aigPartReg.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [AIG package.]

Synopsis [Register partitioning algorithm.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id:

aigPartReg.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

]

Definition at line 31 of file aigPartReg.c.

Function Documentation

void Aig_ManPartDivide	(	Vec_Ptr_t *	vResult,
		Vec_Int_t *	vDomain,
		int	nPartSize,
		int	nOverSize
	)

Function*************************************************************

Synopsis [Divides a large partition into several ones.]

Description []

SideEffects []

SeeAlso []

Definition at line 513 of file aigPartReg.c.

{
    Vec_Int_t * vPart;
    int i, Counter;
    assert( nPartSize && Vec_IntSize(vDomain) > nPartSize );
    if ( nOverSize >= nPartSize )
    {
        printf( "Overlap size (%d) is more or equal than the partition size (%d).\n", nOverSize, nPartSize );
        printf( "Adjusting it to be equal to half of the partition size.\n" );
        nOverSize = nPartSize/2;
    }
    assert( nOverSize < nPartSize );
    for ( Counter = 0; Counter < Vec_IntSize(vDomain); Counter -= nOverSize )
    {
        vPart = Vec_IntAlloc( nPartSize );
        for ( i = 0; i < nPartSize; i++, Counter++ )
            if ( Counter < Vec_IntSize(vDomain) )
                Vec_IntPush( vPart, Vec_IntEntry(vDomain, Counter) );
        if ( Vec_IntSize(vPart) <= nOverSize )
            Vec_IntFree(vPart);
        else
            Vec_PtrPush( vResult, vPart );
    }
}

Aig_Man_t* Aig_ManRegCreatePart	(	Aig_Man_t *	pAig,
		Vec_Int_t *	vPart,
		int *	pnCountPis,
		int *	pnCountRegs,
		int **	ppMapBack
	)

Function*************************************************************

Synopsis [Computes partitioning of registers.]

Description []

SideEffects []

SeeAlso []

Definition at line 308 of file aigPartReg.c.

{
    Aig_Man_t * pNew;
    Aig_Obj_t * pObj, * pObjNew;
    Vec_Ptr_t * vNodes;
    Vec_Ptr_t * vRoots;
    int nOffset, iOut, i;
    int nCountPis, nCountRegs;
    int * pMapBack;
    // collect roots
    vRoots = Vec_PtrAlloc( Vec_IntSize(vPart) );
    nOffset = Aig_ManCoNum(pAig)-Aig_ManRegNum(pAig);
    Vec_IntForEachEntry( vPart, iOut, i )
    {
        pObj = Aig_ManCo(pAig, nOffset+iOut);
        Vec_PtrPush( vRoots, Aig_ObjFanin0(pObj) );
    }
    // collect/mark nodes/PIs in the DFS order
    vNodes = Aig_ManDfsNodes( pAig, (Aig_Obj_t **)Vec_PtrArray(vRoots), Vec_PtrSize(vRoots) );
    Vec_PtrFree( vRoots );
    // unmark register outputs
    nOffset = Aig_ManCiNum(pAig)-Aig_ManRegNum(pAig);
    Vec_IntForEachEntry( vPart, iOut, i )
    {
        pObj = Aig_ManCi(pAig, nOffset+iOut);
        Aig_ObjSetTravIdPrevious( pAig, pObj );
    }
    // count pure PIs
    nCountPis = nCountRegs = 0;
    Aig_ManForEachPiSeq( pAig, pObj, i )
        nCountPis += Aig_ObjIsTravIdCurrent(pAig, pObj);
    // count outputs of other registers
    Aig_ManForEachLoSeq( pAig, pObj, i )
        nCountRegs += Aig_ObjIsTravIdCurrent(pAig, pObj); 
    if ( pnCountPis )
        *pnCountPis = nCountPis;
    if ( pnCountRegs )
        *pnCountRegs = nCountRegs;
    // create the new manager
    pNew = Aig_ManStart( Vec_PtrSize(vNodes) );
    Aig_ManConst1(pAig)->pData = Aig_ManConst1(pNew);
    // create the PIs
    Aig_ManForEachCi( pAig, pObj, i )
        if ( Aig_ObjIsTravIdCurrent(pAig, pObj) )
            pObj->pData = Aig_ObjCreateCi(pNew);
    // add variables for the register outputs
    // create fake POs to hold the register outputs
    nOffset = Aig_ManCiNum(pAig)-Aig_ManRegNum(pAig);
    Vec_IntForEachEntry( vPart, iOut, i )
    {
        pObj = Aig_ManCi(pAig, nOffset+iOut);
        pObj->pData = Aig_ObjCreateCi(pNew);
        Aig_ObjCreateCo( pNew, (Aig_Obj_t *)pObj->pData );
        Aig_ObjSetTravIdCurrent( pAig, pObj ); // added
    }
    // create the nodes
    Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pObj, i )
        if ( Aig_ObjIsNode(pObj) )
            pObj->pData = Aig_And(pNew, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) );
    // add real POs for the registers
    nOffset = Aig_ManCoNum(pAig)-Aig_ManRegNum(pAig);
    Vec_IntForEachEntry( vPart, iOut, i )
    {
        pObj = Aig_ManCo( pAig, nOffset+iOut );
        Aig_ObjCreateCo( pNew, Aig_ObjChild0Copy(pObj) );
    }
    pNew->nRegs = Vec_IntSize(vPart);
    // create map
    if ( ppMapBack )
    {
        pMapBack = ABC_ALLOC( int, Aig_ManObjNumMax(pNew) );
        memset( pMapBack, 0xff, sizeof(int) * Aig_ManObjNumMax(pNew) );
        // map constant nodes
        pMapBack[0] = 0;
        // logic cones of register outputs
        Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pObj, i )
        {
            pObjNew = Aig_Regular((Aig_Obj_t *)pObj->pData);
            pMapBack[pObjNew->Id] = pObj->Id;
        }
        // map register outputs
        nOffset = Aig_ManCiNum(pAig)-Aig_ManRegNum(pAig);
        Vec_IntForEachEntry( vPart, iOut, i )
        {
            pObj = Aig_ManCi(pAig, nOffset+iOut);
            pObjNew = (Aig_Obj_t *)pObj->pData;
            pMapBack[pObjNew->Id] = pObj->Id;
        }
        *ppMapBack = pMapBack;
    }
    Vec_PtrFree( vNodes );
    return pNew;
}

int Aig_ManRegFindBestVar

(

Aig_ManPre_t *

p

)

Function*************************************************************

Synopsis [Computes the next register to be added to the set.]

Description []

SideEffects []

SeeAlso []

Definition at line 156 of file aigPartReg.c.

{
    Vec_Int_t * vSupp;
    int nNewVars, nNewVarsBest = ABC_INFINITY;
    int iVarFree, iVarSupp, iVarBest = -1, i, k;
    // go through the free variables
    Vec_IntForEachEntry( p->vFreeVars, iVarFree, i )
    {
//        if ( p->pfUsedRegs[iVarFree] )
//            continue;
        // get support of this variable
        vSupp = (Vec_Int_t *)Vec_PtrEntry( p->vMatrix, iVarFree );
        // count the number of new vars
        nNewVars = 0;
        Vec_IntForEachEntry( vSupp, iVarSupp, k )
        {
            if ( p->pfPartVars[iVarSupp] )
                continue;
            nNewVars += 1 + 3 * p->pfUsedRegs[iVarSupp];
        }
        // quit if there is no new variables
        if ( nNewVars == 0 )
            return iVarFree;
        // compare the cost of this
        if ( nNewVarsBest > nNewVars )
        {
            nNewVarsBest = nNewVars;
            iVarBest = iVarFree;
        }
    }
    return iVarBest;
}

int Aig_ManRegFindSeed

(

Aig_ManPre_t *

p

)

Function*************************************************************

Synopsis [Determines what register to use as the seed.]

Description [The register is selected as the one having the largest number of non-taken registers in its support.]

SideEffects []

SeeAlso []

Definition at line 122 of file aigPartReg.c.

{
    Vec_Int_t * vRegs;
    int i, k, iReg;
    int iMax = -1; // Suppress "might be used uninitialized"
    int nRegsCur, nRegsMax = -1;
    for ( i = 0; i < Aig_ManRegNum(p->pAig); i++ )
    {
        if ( p->pfUsedRegs[i] )
            continue;
        nRegsCur = 0;
        vRegs = (Vec_Int_t *)Vec_PtrEntry( p->vMatrix, i );
        Vec_IntForEachEntry( vRegs, iReg, k )
            nRegsCur += !p->pfUsedRegs[iReg];
        if ( nRegsMax < nRegsCur )
        {
            nRegsMax = nRegsCur;
            iMax = i;
        }
    }
    return iMax;
}

Aig_ManPre_t* Aig_ManRegManStart	(	Aig_Man_t *	pAig,
		int	nPartSize
	)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Computes partitioning of registers.]

Description []

SideEffects []

SeeAlso []

Definition at line 66 of file aigPartReg.c.

{
    Aig_ManPre_t * p;
    p = ABC_ALLOC( Aig_ManPre_t, 1 );
    memset( p, 0, sizeof(Aig_ManPre_t) );
    p->pAig      = pAig;
    p->vMatrix   = Aig_ManSupportsRegisters( pAig );
    p->nRegsMax  = nPartSize;
    p->vParts    = Vec_PtrAlloc(256);
    p->vRegs     = Vec_IntAlloc(256);
    p->vUniques  = Vec_IntAlloc(256);
    p->vFreeVars = Vec_IntAlloc(256);
    p->vPartCost = Vec_FltAlloc(256);
    p->pfUsedRegs = ABC_ALLOC( char, Aig_ManRegNum(p->pAig) );
    memset( p->pfUsedRegs, 0, sizeof(char) * Aig_ManRegNum(p->pAig) );
    p->pfPartVars  = ABC_ALLOC( char, Aig_ManRegNum(p->pAig) );
    return p;
}

void Aig_ManRegManStop

(

Aig_ManPre_t *

p

)

Function*************************************************************

Synopsis [Computes partitioning of registers.]

Description []

SideEffects []

SeeAlso []

Definition at line 96 of file aigPartReg.c.

{
    Vec_VecFree( (Vec_Vec_t *)p->vMatrix );
    if ( p->vParts )
        Vec_VecFree( (Vec_Vec_t *)p->vParts );
    Vec_IntFree( p->vRegs );
    Vec_IntFree( p->vUniques );
    Vec_IntFree( p->vFreeVars );
    Vec_FltFree( p->vPartCost );
    ABC_FREE( p->pfUsedRegs );
    ABC_FREE( p->pfPartVars );
    ABC_FREE( p );
}

void Aig_ManRegPartitionAdd	(	Aig_ManPre_t *	p,
		int	iReg
	)

Function*************************************************************

Synopsis [Computes partitioning of registers.]

Description []

SideEffects []

SeeAlso []

Definition at line 200 of file aigPartReg.c.

{
    Vec_Int_t * vSupp;
    int RetValue, iVar, i;
    // make sure this is a new variable
//    assert( !p->pfUsedRegs[iReg] );
    if ( !p->pfUsedRegs[iReg] )
    {
        p->pfUsedRegs[iReg] = 1;
        Vec_IntPush( p->vUniques, iReg );
    }
    // remove it from the free variables
    if ( Vec_IntSize(p->vFreeVars) > 0 )
    {
        assert( p->pfPartVars[iReg] );
        RetValue = Vec_IntRemove( p->vFreeVars, iReg );
        assert( RetValue );
    }
    else
        assert( !p->pfPartVars[iReg] );
    // add it to the partition
    p->pfPartVars[iReg] = 1;
    Vec_IntPush( p->vRegs, iReg );
    // add new variables
    vSupp = (Vec_Int_t *)Vec_PtrEntry( p->vMatrix, iReg );
    Vec_IntForEachEntry( vSupp, iVar, i )
    {
        if ( p->pfPartVars[iVar] )
            continue;
        p->pfPartVars[iVar] = 1;
        Vec_IntPush( p->vFreeVars, iVar );
    }
    // add it to the cost
    Vec_FltPush( p->vPartCost, 1.0*Vec_IntSize(p->vFreeVars)/Vec_IntSize(p->vRegs) );
}

Vec_Ptr_t* Aig_ManRegPartitionLinear	(	Aig_Man_t *	pAig,
		int	nPartSize
	)

Function*************************************************************

Synopsis [Computes partitioning of registers.]

Description []

SideEffects []

SeeAlso []

Definition at line 614 of file aigPartReg.c.

{
    Vec_Ptr_t * vLos;
    vLos = Aig_ManRegPartitionTraverse( pAig );
    Vec_PtrFree( vLos );
    return NULL;
}

Vec_Ptr_t* Aig_ManRegPartitionSimple	(	Aig_Man_t *	pAig,
		int	nPartSize,
		int	nOverSize
	)

Function*************************************************************

Synopsis [Computes partitioning of registers.]

Description []

SideEffects []

SeeAlso []

Definition at line 474 of file aigPartReg.c.

{
    Vec_Ptr_t * vResult;
    Vec_Int_t * vPart;
    int i, Counter;
    if ( nOverSize >= nPartSize )
    {
        printf( "Overlap size (%d) is more or equal than the partition size (%d).\n", nOverSize, nPartSize );
        printf( "Adjusting it to be equal to half of the partition size.\n" );
        nOverSize = nPartSize/2;
    }
    assert( nOverSize < nPartSize );
    vResult = Vec_PtrAlloc( 100 );
    for ( Counter = 0; Counter < Aig_ManRegNum(pAig); Counter -= nOverSize )
    {
        vPart = Vec_IntAlloc( nPartSize );
        for ( i = 0; i < nPartSize; i++, Counter++ )
            if ( Counter < Aig_ManRegNum(pAig) )
                Vec_IntPush( vPart, Counter );
        if ( Vec_IntSize(vPart) <= nOverSize )
            Vec_IntFree(vPart);
        else
            Vec_PtrPush( vResult, vPart );
    }
    return vResult;
}

Vec_Ptr_t* Aig_ManRegPartitionSmart	(	Aig_Man_t *	pAig,
		int	nPartSize
	)

Function*************************************************************

Synopsis [Computes partitioning of registers.]

Description []

SideEffects []

SeeAlso []

Definition at line 413 of file aigPartReg.c.

{
    extern void Ioa_WriteAiger( Aig_Man_t * pMan, char * pFileName, int fWriteSymbols, int fCompact );

    Aig_ManPre_t * p;
    Vec_Ptr_t * vResult;
    int iSeed, iNext, i, k;
    // create the manager
    p = Aig_ManRegManStart( pAig, nPartSize );
    // add partitions as long as registers remain
    for ( i = 0; (iSeed = Aig_ManRegFindSeed(p)) >= 0; i++ )
    {
//printf( "Seed variable = %d.\n", iSeed );
        // clean the current partition information
        Vec_IntClear( p->vRegs );
        Vec_IntClear( p->vUniques );
        Vec_IntClear( p->vFreeVars );
        Vec_FltClear( p->vPartCost );
        memset( p->pfPartVars, 0, sizeof(char) * Aig_ManRegNum(p->pAig) );
        // add the register and its partition support
        Aig_ManRegPartitionAdd( p, iSeed );
        // select the best var to add
        for ( k = 0; Vec_IntSize(p->vRegs) < p->nRegsMax; k++ )
        {
            // get the next best variable
            iNext = Aig_ManRegFindBestVar( p );
            if ( iNext == -1 )
                break;
            // add the register to the support of the partition
            Aig_ManRegPartitionAdd( p, iNext );
            // report the result
//printf( "Part %3d  Reg %3d : Free = %4d. Total = %4d. Ratio = %6.2f. Unique = %4d.\n", i, k, 
//                Vec_IntSize(p->vFreeVars), Vec_IntSize(p->vRegs), 
//                1.0*Vec_IntSize(p->vFreeVars)/Vec_IntSize(p->vRegs), Vec_IntSize(p->vUniques) );
            // quit if there are not free variables
            if ( Vec_IntSize(p->vFreeVars) == 0 )
                break;
        }
        // add this partition to the set
        Vec_PtrPush( p->vParts, Vec_IntDup(p->vRegs) );        
printf( "Part %3d  SUMMARY:  Free = %4d. Total = %4d. Ratio = %6.2f. Unique = %4d.\n", i,
                Vec_IntSize(p->vFreeVars), Vec_IntSize(p->vRegs), 
                1.0*Vec_IntSize(p->vFreeVars)/Vec_IntSize(p->vRegs), Vec_IntSize(p->vUniques) );
//printf( "\n" ); 
    }
    vResult = p->vParts; p->vParts = NULL;
    Aig_ManRegManStop( p );
    return vResult;
}

Vec_Ptr_t* Aig_ManRegPartitionTraverse

(

Aig_Man_t *

p

)

Function*************************************************************

Synopsis [Computes partitioning of registers.]

Description []

SideEffects []

SeeAlso []

Definition at line 578 of file aigPartReg.c.

{
    Vec_Ptr_t * vLos;
    Aig_Obj_t * pObj;
    int i, nPrev, Counter;
    // mark the registers
    Aig_ManForEachCi( p, pObj, i )
       pObj->iData = i; 
    // collect registers
    vLos = Vec_PtrAlloc( Aig_ManRegNum(p) );
    nPrev = 0;
    Counter = 0;
    Aig_ManIncrementTravId( p );
    Aig_ManForEachLiSeq( p, pObj, i )
    {
        ++Counter;
        printf( "Latch %d: ", Counter );
        Aig_ManRegPartitionTraverse_rec( p, Aig_ObjFanin0(pObj), vLos );
printf( "%d=%d \n", Counter, Vec_PtrSize(vLos)-nPrev );
        nPrev = Vec_PtrSize(vLos);
    }
    printf( "Total collected = %d. Total regs = %d.\n", Vec_PtrSize(vLos), Aig_ManRegNum(p) );
    return vLos;
}

void Aig_ManRegPartitionTraverse_rec	(	Aig_Man_t *	p,
		Aig_Obj_t *	pObj,
		Vec_Ptr_t *	vLos
	)

Function*************************************************************

Synopsis [Computes partitioning of registers.]

Description []

SideEffects []

SeeAlso []

Definition at line 549 of file aigPartReg.c.

{
    if ( Aig_ObjIsTravIdCurrent(p, pObj) )
        return;
    Aig_ObjSetTravIdCurrent( p, pObj );
    if ( Aig_ObjIsCi(pObj) )
    {
        if ( pObj->iData >= Aig_ManCiNum(p) - Aig_ManRegNum(p) )
        {
            Vec_PtrPush( vLos, pObj );
            printf( "%d ", pObj->iData - (Aig_ManCiNum(p) - Aig_ManRegNum(p)) );
        }
        return;
    }
    Aig_ManRegPartitionTraverse_rec( p, Aig_ObjFanin0(pObj), vLos );
    Aig_ManRegPartitionTraverse_rec( p, Aig_ObjFanin1(pObj), vLos );
}

Vec_Ptr_t* Aig_ManRegProjectOnehots	(	Aig_Man_t *	pAig,
		Aig_Man_t *	pPart,
		Vec_Ptr_t *	vOnehots,
		int	fVerbose
	)

Function*************************************************************

Synopsis [Creates projection of 1-hot registers onto the given partition.]

Description [Assumes that the relevant register outputs are labeled with the current traversal ID.]

SideEffects []

SeeAlso []

Definition at line 248 of file aigPartReg.c.

{
    Vec_Ptr_t * vOnehotsPart = NULL;
    Vec_Int_t * vGroup, * vGroupNew;
    Aig_Obj_t * pObj, * pObjNew;
    int nOffset, iReg, i, k;
    // set the PI numbers
    Aig_ManForEachCi( pPart, pObj, i )
        pObj->iData = i;
    // go through each group and check if registers are involved in this one
    nOffset = Aig_ManCiNum(pAig)-Aig_ManRegNum(pAig);
    Vec_PtrForEachEntry( Vec_Int_t *, vOnehots, vGroup, i )
    {
        vGroupNew = NULL;
        Vec_IntForEachEntry( vGroup, iReg, k )
        {
            pObj = Aig_ManCi( pAig, nOffset+iReg );
            if ( !Aig_ObjIsTravIdCurrent(pAig, pObj) )
                continue;
            if ( vGroupNew == NULL )
                vGroupNew = Vec_IntAlloc( Vec_IntSize(vGroup) );
            pObjNew = (Aig_Obj_t *)pObj->pData;
            Vec_IntPush( vGroupNew, pObjNew->iData );
        }
        if ( vGroupNew == NULL )
            continue;
        if ( Vec_IntSize(vGroupNew) > 1 )
        {
            if ( vOnehotsPart == NULL )
                vOnehotsPart = Vec_PtrAlloc( 100 );
            Vec_PtrPush( vOnehotsPart, vGroupNew );
        }
        else
            Vec_IntFree( vGroupNew );
    }
    // clear the PI numbers
    Aig_ManForEachCi( pPart, pObj, i )
        pObj->iData = 0;
    // print out
    if ( vOnehotsPart && fVerbose )
    {
        printf( "Partition contains %d groups of 1-hot registers: { ", Vec_PtrSize(vOnehotsPart) );
        Vec_PtrForEachEntry( Vec_Int_t *, vOnehotsPart, vGroup, k )
            printf( "%d ", Vec_IntSize(vGroup) );
        printf( "}\n" );
    }
    return vOnehotsPart;
}