abcFanOrder.c File Reference

#include "abc.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START void	Abc_NtkOrderFaninsById (Abc_Ntk_t *pNtk)
	DECLARATIONS ///. More...
void	Abc_NtkOrderFaninsByLitCount (Abc_Ntk_t *pNtk)
void	Abc_NtkOrderFaninsByLitCountAndCubeCount (Abc_Ntk_t *pNtk)
void	Abc_NodeSplitLarge (Abc_Obj_t *pNode)
void	Abc_NtkSplitLarge (Abc_Ntk_t *pNtk, int nFaninsMax, int nCubesMax)
int	Abc_NodeCompareCubes (char **pp1, char **pp2)
void	Abc_NodeSortCubes (Abc_Obj_t *pNode, Vec_Ptr_t *vCubes, Vec_Str_t *vStore)
void	Abc_NtkSortCubes (Abc_Ntk_t *pNtk)
void	Abc_NtkSortSops (Abc_Ntk_t *pNtk)
static int	Abc_CubeContain (char *pCube1, char *pCube2, int nVars)
int	Abc_NodeMakeSCCFree (Abc_Obj_t *pNode)
void	Abc_NodeMakeDist1Free (Abc_Obj_t *pNode)
void	Abc_NodeCheckDist1Free (Abc_Obj_t *pNode)
int	Abc_NodeMakeLegit (Abc_Obj_t *pNode)
int	Abc_NtkMakeLegit (Abc_Ntk_t *pNtk)

Function Documentation

static int Abc_CubeContain ( char *  pCube1, char *  pCube2, int  nVars  )

inlinestatic

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

Synopsis [Makes cover legitimate for "fast_extract".]

Description [Iteratively removes distance-1 and contained cubes.]

SideEffects []

SeeAlso []

Definition at line 367 of file abcFanOrder.c.

{
    int v, fCont12 = 1, fCont21 = 1;
    for ( v = 0; v < nVars; v++ )
    {
        if ( pCube1[v] == pCube2[v] )
            continue;
        if ( pCube1[v] == '-' )
            fCont21 = 0;
        else if ( pCube2[v] == '-' )
            fCont12 = 0;
        else
            return 0;
        if ( !fCont21 && !fCont21 )
            return 0;
    }
    assert( fCont21 || fCont12 );
    return (fCont21 << 1) | fCont12;
}

void Abc_NodeCheckDist1Free

(

Abc_Obj_t *

pNode

)

Definition at line 433 of file abcFanOrder.c.

{
    char * pSop = (char *)pNode->pData;
    char * pCube, * pCube2;
    int i, nVars = Abc_ObjFaninNum(pNode);
    Abc_SopForEachCube( pSop, nVars, pCube )
    Abc_SopForEachCube( pSop, nVars, pCube2 )
    {
        int Counter = 0;
        if ( pCube == pCube2 )
            continue;
        for ( i = 0; i < nVars; i++ )
            if ( pCube[i] != pCube2[i] )
                Counter++;
        assert( Counter > 1 );
    }
}

int Abc_NodeCompareCubes	(	char **	pp1,
		char **	pp2
	)

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

Synopsis [Sorts the cubes in a topological order.]

Description []

SideEffects []

SeeAlso []

Definition at line 294 of file abcFanOrder.c.

{
    return strcmp( *pp1, *pp2 );
}

void Abc_NodeMakeDist1Free

(

Abc_Obj_t *

pNode

)

Definition at line 417 of file abcFanOrder.c.

{
    char * pSop = (char *)pNode->pData;
    char * pCube, * pCube2;
    int i, nVars = Abc_ObjFaninNum(pNode);
    Abc_SopForEachCube( pSop, nVars, pCube )
    Abc_SopForEachCube( pCube + nVars + 3, nVars, pCube2 )
    {
        int Counter = 0, iDiff = -1;
        for ( i = 0; i < nVars; i++ )
            if ( pCube[i] != pCube2[i] )
                Counter++, iDiff = i;
        if ( Counter == 1 && ((pCube[iDiff] == '0' && pCube2[iDiff] == '1') || (pCube[iDiff] == '1' && pCube2[iDiff] == '0')) )
            pCube[iDiff] = pCube2[iDiff] = '-';
    }
}

int Abc_NodeMakeLegit

(

Abc_Obj_t *

pNode

)

Definition at line 450 of file abcFanOrder.c.

{
    int i, fChanges = 1;
    for ( i = 0; fChanges; i++ )
    {
        Abc_NodeMakeDist1Free( pNode );
        fChanges = Abc_NodeMakeSCCFree( pNode );
    }
//    Abc_NodeCheckDist1Free( pNode );
    return i > 1;
}

int Abc_NodeMakeSCCFree

(

Abc_Obj_t *

pNode

)

Definition at line 386 of file abcFanOrder.c.

{
    char * pSop = (char *)pNode->pData;
    char * pCube, * pCube2, * pSopNew;
    int nVars = Abc_ObjFaninNum(pNode);
    int Status, nCount = 0;
    Abc_SopForEachCubePair( pSop, nVars, pCube, pCube2 )
    {
        if ( pCube[0] == 'z' || pCube2[0] == 'z' )
            continue;
        Status = Abc_CubeContain( pCube, pCube2, nVars );
        nCount += (int)(Status > 0);
        if ( Status & 1 )
            pCube2[0] = 'z';
        else if ( Status & 2 )
            pCube[0] = 'z';
    }
    if ( nCount == 0 )
        return 0;
    // create new cover
    pSopNew = (char *)pNode->pData;
    Abc_SopForEachCube( pSop, nVars, pCube )
    {
        if ( pCube[0] == 'z' )
            continue;
        memcpy( pSopNew, pCube, nVars + 3 );
        pSopNew += nVars + 3;
    }
    *pSopNew = 0;
    return 1;
}

void Abc_NodeSortCubes	(	Abc_Obj_t *	pNode,
		Vec_Ptr_t *	vCubes,
		Vec_Str_t *	vStore
	)

Definition at line 298 of file abcFanOrder.c.

{
    char * pCube, * pPivot;
    char * pSop = (char *)pNode->pData;
    int i, nVars = Abc_ObjFaninNum(pNode);
    Vec_PtrClear( vCubes );
    Abc_SopForEachCube( pSop, nVars, pCube )
    {
        assert( pCube[nVars] == ' ' );
        pCube[nVars] = 0;
        Vec_PtrPush( vCubes, pCube );
    }
    Vec_PtrSort( vCubes, (int (*)())Abc_NodeCompareCubes );
    Vec_StrGrow( vStore, Vec_PtrSize(vCubes) * (nVars + 3) );
    pPivot = Vec_StrArray( vStore );
    Vec_PtrForEachEntry( char *, vCubes, pCube, i )
    {
        assert( pCube[nVars] == 0 );
        pCube[nVars] = ' ';
        memcpy( pPivot, pCube, nVars + 3 );
        pPivot += nVars + 3;
    }
    memcpy( pSop, Vec_StrArray(vStore), Vec_PtrSize(vCubes) * (nVars + 3) );
}

void Abc_NodeSplitLarge

(

Abc_Obj_t *

pNode

)

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

Synopsis [Split large nodes by dividing their SOPs in half.]

Description []

SideEffects []

SeeAlso []

Definition at line 245 of file abcFanOrder.c.

{
    Abc_Obj_t * pNode1, * pNode2, * pFanin;
    int CutPoint, nVars = Abc_ObjFaninNum(pNode);
    int i, nCubes = Abc_SopGetCubeNum((char *)pNode->pData);
    pNode1 = Abc_NtkDupObj( pNode->pNtk, pNode, 0 );
    pNode2 = Abc_NtkDupObj( pNode->pNtk, pNode, 0 );
    Abc_ObjForEachFanin( pNode, pFanin, i )
        Abc_ObjAddFanin( pNode1, pFanin );
    Abc_ObjForEachFanin( pNode, pFanin, i )
        Abc_ObjAddFanin( pNode2, pFanin );    
    // update the node
    Abc_ObjRemoveFanins( pNode );
    Abc_ObjAddFanin( pNode, pNode1 );
    Abc_ObjAddFanin( pNode, pNode2 );
    pNode->pData = Abc_SopCreateOr( (Mem_Flex_t *)pNode->pNtk->pManFunc, 2, NULL );
    // update covers of the nodes
    assert( nCubes > 1 );
    CutPoint = (nCubes / 2) * (nVars + 3);
    ((char *)pNode1->pData)[CutPoint] = 0;
    pNode2->pData = (char *)pNode2->pData + CutPoint;
}

int Abc_NtkMakeLegit

(

Abc_Ntk_t *

pNtk

)

Definition at line 461 of file abcFanOrder.c.

{
    Abc_Obj_t * pNode;
    int i, Counter = 0;
    assert( Abc_NtkHasSop(pNtk) );
    Abc_NtkForEachNode( pNtk, pNode, i )
        Counter += Abc_NodeMakeLegit( pNode );
    if ( Counter )
        Abc_Print( 0, "%d nodes were made dist1-cube-free and/or single-cube-containment-free.\n", Counter );
    return 1;
}

ABC_NAMESPACE_IMPL_START void Abc_NtkOrderFaninsById

(

Abc_Ntk_t *

pNtk

)

DECLARATIONS ///.

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

FileName [abcFanOrder.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Fanin ordering procedures.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

abcFanOrder.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Reorder fanins of the network.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file abcFanOrder.c.

{
    Vec_Int_t * vOrder;
    Vec_Str_t * vStore;
    Abc_Obj_t * pNode;
    char * pSop, * pSopNew;
    char * pCube, * pCubeNew;
    int nVars, i, v, * pOrder;
    assert( Abc_NtkHasSop(pNtk) );
    vOrder = Vec_IntAlloc( 100 );
    vStore = Vec_StrAlloc( 100 );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        pSop = (char *)pNode->pData;
        nVars = Abc_SopGetVarNum(pSop);
        assert( nVars == Abc_ObjFaninNum(pNode) );
        Vec_IntClear( vOrder );
        for ( v = 0; v < nVars; v++ )
            Vec_IntPush( vOrder, v );
        pOrder = Vec_IntArray(vOrder);
        Vec_IntSelectSortCost( pOrder, nVars, &pNode->vFanins );
        // copy the cover
        Vec_StrGrow( vStore, Abc_SopGetCubeNum(pSop) * (nVars + 3) + 1 );
        memcpy( Vec_StrArray(vStore), pSop, Abc_SopGetCubeNum(pSop) * (nVars + 3) + 1 );
        pSopNew = pCubeNew = pSop;
        pSop = Vec_StrArray(vStore);
        // generate permuted one
        Abc_SopForEachCube( pSop, nVars, pCube )
        {
            for ( v = 0; v < nVars; v++ )
                pCubeNew[v] = '-';
            for ( v = 0; v < nVars; v++ )
                if ( pCube[pOrder[v]] == '0' )
                    pCubeNew[v] = '0';
                else if ( pCube[pOrder[v]] == '1' )
                    pCubeNew[v] = '1';
            pCubeNew += nVars + 3;
        }
        pNode->pData = pSopNew;
        Vec_IntSort( &pNode->vFanins, 0 );
//        Vec_IntPrint( vOrder );
    }
    Vec_IntFree( vOrder );
    Vec_StrFree( vStore );
}

void Abc_NtkOrderFaninsByLitCount

(

Abc_Ntk_t *

pNtk

)

Definition at line 90 of file abcFanOrder.c.

{
    Vec_Int_t * vOrder;
    Vec_Int_t * vCounts;
    Vec_Int_t * vFanins;
    Vec_Str_t * vStore;
    Abc_Obj_t * pNode;
    char * pSop, * pSopNew;
    char * pCube, * pCubeNew;
    int nVars, i, v, * pOrder;
    assert( Abc_NtkHasSop(pNtk) );
    vOrder = Vec_IntAlloc( 100 );
    vStore = Vec_StrAlloc( 100 );
    vCounts = Vec_IntAlloc( 100 );
    vFanins = Vec_IntAlloc( 100 );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        pSop = (char *)pNode->pData;
        nVars = Abc_SopGetVarNum(pSop);
        assert( nVars == Abc_ObjFaninNum(pNode) );
        // count literals
        Vec_IntFill( vCounts, nVars, 0 );
        Abc_SopForEachCube( pSop, nVars, pCube )
            for ( v = 0; v < nVars; v++ )
                if ( pCube[v] != '-' )
                    Vec_IntAddToEntry( vCounts, v, 1 );
        // find good order
        Vec_IntClear( vOrder );
        for ( v = 0; v < nVars; v++ )
            Vec_IntPush( vOrder, v );
        pOrder = Vec_IntArray(vOrder);
        Vec_IntSelectSortCost( pOrder, nVars, vCounts );
        // copy the cover
        Vec_StrGrow( vStore, Abc_SopGetCubeNum(pSop) * (nVars + 3) + 1 );
        memcpy( Vec_StrArray(vStore), pSop, Abc_SopGetCubeNum(pSop) * (nVars + 3) + 1 );
        pSopNew = pCubeNew = pSop;
        pSop = Vec_StrArray(vStore);
        // generate permuted one
        Abc_SopForEachCube( pSop, nVars, pCube )
        {
            for ( v = 0; v < nVars; v++ )
                pCubeNew[v] = '-';
            for ( v = 0; v < nVars; v++ )
                if ( pCube[pOrder[v]] == '0' )
                    pCubeNew[v] = '0';
                else if ( pCube[pOrder[v]] == '1' )
                    pCubeNew[v] = '1';
            pCubeNew += nVars + 3;
        }
        pNode->pData = pSopNew;
        // generate the fanin order
        Vec_IntClear( vFanins );
        for ( v = 0; v < nVars; v++ )
            Vec_IntPush( vFanins, Abc_ObjFaninId( pNode, pOrder[v] ) );
        Vec_IntClear( &pNode->vFanins );
        Vec_IntAppend( &pNode->vFanins, vFanins );
    }
    Vec_IntFree( vFanins );
    Vec_IntFree( vCounts );
    Vec_IntFree( vOrder );
    Vec_StrFree( vStore );
}

void Abc_NtkOrderFaninsByLitCountAndCubeCount

(

Abc_Ntk_t *

pNtk

)

Definition at line 152 of file abcFanOrder.c.

{
    // assuming that the fanins are sorted by the number of literals in each cube
    // this procedure sorts the literals appearing only once by the number of their cube
    Vec_Int_t * vOrder;
    Vec_Int_t * vCounts;
    Vec_Int_t * vFanins;
    Vec_Int_t * vCubeNum;
    Vec_Str_t * vStore;
    Abc_Obj_t * pNode;
    char * pSop, * pSopNew;
    char * pCube, * pCubeNew;
    int nVars, i, v, iCube, * pOrder;
    assert( Abc_NtkHasSop(pNtk) );
    vStore = Vec_StrAlloc( 100 );
    vOrder = Vec_IntAlloc( 100 );
    vCounts = Vec_IntAlloc( 100 );
    vFanins = Vec_IntAlloc( 100 );
    vCubeNum = Vec_IntAlloc( 100 );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        pSop = (char *)pNode->pData;
        nVars = Abc_SopGetVarNum(pSop);
        assert( nVars == Abc_ObjFaninNum(pNode) );
        // count literals and remember the cube where each literal appears
        Vec_IntFill( vCounts, nVars, 0 );
        Vec_IntFill( vCubeNum, nVars, 0 );
        iCube = 0;
        Abc_SopForEachCube( pSop, nVars, pCube )
        {
            for ( v = 0; v < nVars; v++ )
                if ( pCube[v] != '-' )
                {
                    Vec_IntAddToEntry( vCounts, v, 1 );
                    Vec_IntWriteEntry( vCubeNum, v, iCube );
                }
            iCube++;
        }
        // create new order
        for ( v = 0; v < nVars; v++ )
            if ( Vec_IntEntry(vCounts, v) == 1 )
                Vec_IntWriteEntry( vCounts, v, Vec_IntEntry(vCubeNum, v) );
            else
                Vec_IntWriteEntry( vCounts, v, ABC_INFINITY );
        // find good order
        Vec_IntClear( vOrder );
        for ( v = 0; v < nVars; v++ )
            Vec_IntPush( vOrder, v );
        pOrder = Vec_IntArray(vOrder);
        Vec_IntSelectSortCost( pOrder, nVars, vCounts );
        // copy the cover
        Vec_StrGrow( vStore, Abc_SopGetCubeNum(pSop) * (nVars + 3) + 1 );
        memcpy( Vec_StrArray(vStore), pSop, Abc_SopGetCubeNum(pSop) * (nVars + 3) + 1 );
        pSopNew = pCubeNew = pSop;
        pSop = Vec_StrArray(vStore);
        // generate permuted one
        Abc_SopForEachCube( pSop, nVars, pCube )
        {
            for ( v = 0; v < nVars; v++ )
                pCubeNew[v] = '-';
            for ( v = 0; v < nVars; v++ )
                if ( pCube[pOrder[v]] == '0' )
                    pCubeNew[v] = '0';
                else if ( pCube[pOrder[v]] == '1' )
                    pCubeNew[v] = '1';
            pCubeNew += nVars + 3;
        }
        pNode->pData = pSopNew;
        // generate the fanin order
        Vec_IntClear( vFanins );
        for ( v = 0; v < nVars; v++ )
            Vec_IntPush( vFanins, Abc_ObjFaninId( pNode, pOrder[v] ) );
        Vec_IntClear( &pNode->vFanins );
        Vec_IntAppend( &pNode->vFanins, vFanins );
    }
    Vec_IntFree( vCubeNum );
    Vec_IntFree( vFanins );
    Vec_IntFree( vCounts );
    Vec_IntFree( vOrder );
    Vec_StrFree( vStore );
}

void Abc_NtkSortCubes

(

Abc_Ntk_t *

pNtk

)

Definition at line 322 of file abcFanOrder.c.

{
    Vec_Ptr_t * vCubes;
    Vec_Str_t * vStore;
    Abc_Obj_t * pNode;
    int i;
    assert( Abc_NtkHasSop(pNtk) );
    vCubes = Vec_PtrAlloc( 1000 );
    vStore = Vec_StrAlloc( 1000 );
    Abc_NtkForEachNode( pNtk, pNode, i )
        Abc_NodeSortCubes( pNode, vCubes, vStore );
    Vec_StrFree( vStore );
    Vec_PtrFree( vCubes );
}

void Abc_NtkSortSops

(

Abc_Ntk_t *

pNtk

)

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

Synopsis [Sorts fanins of each node to make SOPs more readable.]

Description []

SideEffects []

SeeAlso []

Definition at line 348 of file abcFanOrder.c.

{
    Abc_NtkOrderFaninsByLitCount( pNtk );
    Abc_NtkSortCubes( pNtk );
    Abc_NtkOrderFaninsByLitCountAndCubeCount( pNtk );
    Abc_NtkSortCubes( pNtk );
}

void Abc_NtkSplitLarge	(	Abc_Ntk_t *	pNtk,
		int	nFaninsMax,
		int	nCubesMax
	)

Definition at line 267 of file abcFanOrder.c.

{
    Abc_Obj_t * pNode;
    int nObjOld = Abc_NtkObjNumMax(pNtk);
    int i, nCubes;
    assert( Abc_NtkHasSop(pNtk) );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        if ( i == nObjOld )
            break;
        nCubes = Abc_SopGetCubeNum((char *)pNode->pData);
        if ( (Abc_ObjFaninNum(pNode) > nFaninsMax && nCubes > 1) || nCubes > nCubesMax )
            Abc_NodeSplitLarge( pNode );
    }
}