acecStruct.c File Reference

#include "acecInt.h"
#include "misc/vec/vecWec.h"
#include "misc/extra/extra.h"

Include dependency graph for acecStruct.c:

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START Vec_Int_t *	Acec_StructDetectXorRoots (Gia_Man_t *p)
	DECLARATIONS ///.
Vec_Int_t *	Acec_StructAssignRanks (Gia_Man_t *p, Vec_Int_t *vXorRoots)
Vec_Wec_t *	Acec_FindTreeLeaves (Gia_Man_t *p, Vec_Int_t *vXorRoots, Vec_Int_t *vRanks)
Vec_Int_t *	Acec_FindShadows (Gia_Man_t *p, Vec_Int_t *vRanks)
int	Acec_CollectSupp_rec (Gia_Man_t *p, int iNode, int Rank, Vec_Int_t *vRanks)
Vec_Wec_t *	Acec_FindNexts (Gia_Man_t *p, Vec_Int_t *vRanks, Vec_Int_t *vShadows, Vec_Wec_t *vTreeLeaves)
void	Acec_StructTest (Gia_Man_t *p)

Function Documentation

Acec_CollectSupp_rec()

int Acec_CollectSupp_rec	(	Gia_Man_t *	p,
		int	iNode,
		int	Rank,
		Vec_Int_t *	vRanks )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 205 of file acecStruct.c.

{
    Gia_Obj_t * pObj;
    int nSize;
    if ( Gia_ObjIsTravIdCurrentId(p, iNode) )
        return 0;
    Gia_ObjSetTravIdCurrentId(p, iNode);
    pObj = Gia_ManObj(p, iNode);
    assert( Gia_ObjIsAnd(pObj) );
    if ( Vec_IntEntry(vRanks, iNode) == Rank )
        return 1;
    nSize = Acec_CollectSupp_rec( p, Gia_ObjFaninId0(pObj, iNode), Rank, vRanks );
    nSize += Acec_CollectSupp_rec( p, Gia_ObjFaninId1(pObj, iNode), Rank, vRanks );
    return nSize;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_FindNexts()

Vec_Wec_t * Acec_FindNexts	(	Gia_Man_t *	p,
		Vec_Int_t *	vRanks,
		Vec_Int_t *	vShadows,
		Vec_Wec_t *	vTreeLeaves )

Definition at line 220 of file acecStruct.c.

{
    Vec_Wec_t * vNexts = Vec_WecStart( Vec_WecSize(vTreeLeaves) );
    Vec_Int_t * vTree;
    int i, k, Node, Fanins[2], Shad0, Shad1, Rank, nSupp;
    Vec_WecForEachLevel( vTreeLeaves, vTree, i )
        Vec_IntForEachEntry( vTree, Node, k )
        {
            Gia_Obj_t * pObj = Gia_ManObj(p, Node);
            if ( !Gia_ObjIsAnd(pObj) )
                continue;
            Fanins[0] = Gia_ObjFaninId0(pObj, Node);
            Fanins[1] = Gia_ObjFaninId1(pObj, Node);
            Shad0 = Vec_IntEntry(vShadows, Fanins[0]);
            Shad1 = Vec_IntEntry(vShadows, Fanins[1]);
            if ( Shad0 != Shad1 || Shad0 == -1 )
                continue;
            // check support size of Node in terms of the shadow of its fanins
            Rank = Vec_IntEntry( vRanks, Node );
            assert( Rank != Shad0 );
            Gia_ManIncrementTravId( p );
            nSupp = Acec_CollectSupp_rec( p, Node, Shad0, vRanks );
            assert( nSupp > 1 );
            if ( nSupp > 3 )
                continue;
            Vec_IntPushUniqueOrder( Vec_WecEntry(vNexts, Shad0), Rank );
        }
    return vNexts;
}

Here is the call graph for this function:

Acec_FindShadows()

Vec_Int_t * Acec_FindShadows	(	Gia_Man_t *	p,
		Vec_Int_t *	vRanks )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 176 of file acecStruct.c.

{
    Vec_Int_t * vShadows = Vec_IntDup( vRanks );
    Gia_Obj_t * pObj; int i, Shad0, Shad1;
    Gia_ManForEachCi( p, pObj, i )
        Vec_IntWriteEntry( vShadows, Gia_ObjId(p, pObj), -1 );
    Gia_ManForEachAnd( p, pObj, i )
    {
        if ( Vec_IntEntry(vShadows, i) >= 0 )
            continue;
        Shad0 = Vec_IntEntry(vShadows, Gia_ObjFaninId0(pObj, i));
        Shad1 = Vec_IntEntry(vShadows, Gia_ObjFaninId1(pObj, i));
        if ( Shad0 == Shad1 && Shad0 != -1 )
            Vec_IntWriteEntry(vShadows, i, Shad0);
    }
    return vShadows;
}

Acec_FindTreeLeaves()

Vec_Wec_t * Acec_FindTreeLeaves	(	Gia_Man_t *	p,
		Vec_Int_t *	vXorRoots,
		Vec_Int_t *	vRanks )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 133 of file acecStruct.c.

{
    Vec_Bit_t * vMapXors = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Wec_t * vTreeLeaves = Vec_WecStart( Vec_IntSize(vXorRoots) );
    Gia_Obj_t * pFan0, * pFan1, * pObj; 
    int i, k, Fanins[2], Rank;
    Gia_ManForEachAnd( p, pObj, i )
    {
        if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
            continue;
        Vec_BitWriteEntry( vMapXors, i, 1 );
        Rank = Vec_IntEntry( vRanks, i );
        // skip XORs that are not part of any tree
        if ( Rank == -1 )
            continue;
        // iterate through XOR inputs
        Fanins[0] = Gia_ObjId(p, Gia_Regular(pFan0));
        Fanins[1] = Gia_ObjId(p, Gia_Regular(pFan1));
        for ( k = 0; k < 2; k++ )
        {
            if ( Vec_BitEntry(vMapXors, Fanins[k]) )
            {
                assert( Rank == Vec_IntEntry(vRanks, Fanins[k]) );
                continue;
            }
            Vec_WecPush( vTreeLeaves, Rank, Fanins[k] );
        }
    }
    Vec_BitFree( vMapXors );
    return vTreeLeaves;
}

Here is the call graph for this function:

Acec_StructAssignRanks()

Vec_Int_t * Acec_StructAssignRanks	(	Gia_Man_t *	p,
		Vec_Int_t *	vXorRoots )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 81 of file acecStruct.c.

{
    Vec_Int_t * vDoubles = Vec_IntAlloc( 100 );
    Gia_Obj_t * pFan0, * pFan1, * pObj; 
    int i, k, Fanins[2], Entry, Rank;
    // map roots into their ranks
    Vec_Int_t * vRanks = Vec_IntStartFull( Gia_ManObjNum(p) ); 
    Vec_IntForEachEntry( vXorRoots, Entry, i )
        Vec_IntWriteEntry( vRanks, Entry, i );
    // map nodes into their ranks
    Gia_ManForEachAndReverse( p, pObj, i )
    {
        if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
            continue;
        Rank = Vec_IntEntry( vRanks, i );
        // skip XORs that are not part of any tree
        if ( Rank == -1 )
            continue;
        // iterate through XOR inputs
        Fanins[0] = Gia_ObjId(p, Gia_Regular(pFan0));
        Fanins[1] = Gia_ObjId(p, Gia_Regular(pFan1));
        for ( k = 0; k < 2; k++ )
        {
            Entry = Vec_IntEntry( vRanks, Fanins[k] );
            if ( Entry == Rank ) // the same tree -- allow fanout in this tree
                continue;
            if ( Entry == -1 )
                Vec_IntWriteEntry( vRanks, Fanins[k], Rank );
            else
                Vec_IntPush( vDoubles, Fanins[k] );
            if ( Entry != -1 && Gia_ObjIsAnd(Gia_ManObj(p, Fanins[k])))
            printf( "Xor node %d belongs to Tree %d and Tree %d.\n", Fanins[k], Entry, Rank );
        }
    }
    // remove duplicated entries
    Vec_IntForEachEntry( vDoubles, Entry, i )
        Vec_IntWriteEntry( vRanks, Entry, -1 );
    Vec_IntFree( vDoubles );
    return vRanks;
}

Here is the call graph for this function:

Acec_StructDetectXorRoots()

ABC_NAMESPACE_IMPL_START Vec_Int_t * Acec_StructDetectXorRoots

(

Gia_Man_t *

p

)

DECLARATIONS ///.

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

FileName [acecStruct.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [CEC for arithmetic circuits.]

Synopsis [Core procedures.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id

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

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 47 of file acecStruct.c.

{
    Vec_Int_t * vXors = Vec_IntAlloc( 100 );
    Vec_Bit_t * vXorIns = Vec_BitStart( Gia_ManObjNum(p) );
    Gia_Obj_t * pFan0, * pFan1, * pObj; 
    int i, k = 0, Entry;
    Gia_ManForEachAnd( p, pObj, i )
    {
        if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
            continue;
        Vec_IntPush( vXors, i );
        Vec_BitWriteEntry( vXorIns, Gia_ObjId(p, Gia_Regular(pFan0)), 1 );
        Vec_BitWriteEntry( vXorIns, Gia_ObjId(p, Gia_Regular(pFan1)), 1 );
    }
    // collect XORs that not inputs of other XORs
    Vec_IntForEachEntry( vXors, Entry, i )
        if ( !Vec_BitEntry(vXorIns, Entry) )
            Vec_IntWriteEntry( vXors, k++, Entry );
    Vec_IntShrink( vXors, k );
    Vec_BitFree( vXorIns );
    return vXors;
}

Here is the call graph for this function:

Acec_StructTest()

void Acec_StructTest

(

Gia_Man_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 261 of file acecStruct.c.

{
}