acecTree.c File Reference

#include "acecInt.h"

Include dependency graph for acecTree.c:

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START void	Acec_BoxFree (Acec_Box_t *pBox)
	DECLARATIONS ///.
void	Acec_BoxFreeP (Acec_Box_t **ppBox)
void	Acec_VerifyBoxLeaves (Acec_Box_t *pBox, Vec_Bit_t *vIgnore)
void	Acec_TreeFilterOne (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Int_t *vTree)
void	Acec_TreeFilterTrees (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Wec_t *vTrees)
void	Acec_TreeMarkTFI_rec (Gia_Man_t *p, int Id, Vec_Bit_t *vMarked)
void	Acec_TreeFilterOne2 (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Int_t *vTree)
void	Acec_TreeFilterTrees2 (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Wec_t *vTrees)
int	Acec_TreeVerifyPhaseOne_rec (Gia_Man_t *p, Gia_Obj_t *pObj)
void	Acec_TreeVerifyPhaseOne (Gia_Man_t *p, Vec_Int_t *vAdds, int iBox)
void	Acec_TreeVerifyPhases (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Wec_t *vBoxes)
void	Acec_TreeVerifyPhases2 (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Wec_t *vBoxes)
void	Acec_TreeVerifyConnections (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Wec_t *vBoxes)
Vec_Int_t *	Acec_TreeCarryMap (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Wec_t *vBoxes)
void	Acec_TreePhases_rec (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Int_t *vMap, int Node, int fPhase, Vec_Bit_t *vVisit)
void	Acec_TreeAddInOutPoint (Vec_Int_t *vMap, int iObj, int iAdd, int fOut)
Vec_Int_t *	Acec_TreeFindPoints (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Bit_t *vIgnore)
int	Acec_TreeWhichPoint (Vec_Int_t *vAdds, int iAdd, int iObj)
void	Acec_TreeFindTrees2_rec (Vec_Int_t *vAdds, Vec_Int_t *vMap, int iAdd, int Rank, Vec_Int_t *vTree, Vec_Bit_t *vFound)
void	Acec_TreeFindTrees_rec (Vec_Int_t *vAdds, Vec_Int_t *vMap, int iObj, int Rank, Vec_Int_t *vTree, Vec_Bit_t *vFound)
Vec_Wec_t *	Acec_TreeFindTrees (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Bit_t *vIgnore, int fFilterIn, int fFilterOut)
void	Acec_TreeFindTreesTest (Gia_Man_t *p)
void	Acec_PrintAdders (Vec_Wec_t *vBoxes, Vec_Int_t *vAdds)
void	Acec_TreePrintBox (Acec_Box_t *pBox, Vec_Int_t *vAdds)
int	Acec_CreateBoxMaxRank (Vec_Int_t *vTree)
Acec_Box_t *	Acec_CreateBox (Gia_Man_t *p, Vec_Int_t *vAdds, Vec_Int_t *vTree)
void	Acec_CreateBoxTest (Gia_Man_t *p)
Acec_Box_t *	Acec_DeriveBox (Gia_Man_t *p, Vec_Bit_t *vIgnore, int fFilterIn, int fFilterOut, int fVerbose)

Function Documentation

Acec_BoxFree()

ABC_NAMESPACE_IMPL_START void Acec_BoxFree

(

Acec_Box_t *

pBox

)

DECLARATIONS ///.

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

FileName [acecTree.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [CEC for arithmetic circuits.]

Synopsis [Adder tree construction.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id

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

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file acecTree.c.

{
    Vec_WecFreeP( &pBox->vAdds );
    Vec_WecFreeP( &pBox->vLeafLits );
    Vec_WecFreeP( &pBox->vRootLits );
    Vec_WecFreeP( &pBox->vUnique );
    Vec_WecFreeP( &pBox->vShared );
    ABC_FREE( pBox );
}

Here is the caller graph for this function:

Acec_BoxFreeP()

void Acec_BoxFreeP

(

Acec_Box_t **

ppBox

)

Definition at line 54 of file acecTree.c.

{
    if ( *ppBox )
        Acec_BoxFree( *ppBox );
    *ppBox = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_CreateBox()

Acec_Box_t * Acec_CreateBox	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Int_t *	vTree )

Definition at line 607 of file acecTree.c.

{
    int MaxRank = Acec_CreateBoxMaxRank(vTree);
    Vec_Bit_t * vVisit  = Vec_BitStart( Vec_IntSize(vAdds)/6 );
    Vec_Bit_t * vIsLeaf = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Bit_t * vIsRoot = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Int_t * vLevel, * vMap;
    int i, j, k, Box, Rank;//, Count = 0;
 
    Acec_Box_t * pBox = ABC_CALLOC( Acec_Box_t, 1 );
    pBox->pGia        = p;
    pBox->vAdds       = Vec_WecStart( MaxRank + 1 );
    pBox->vLeafLits   = Vec_WecStart( MaxRank + 1 );
    pBox->vRootLits   = Vec_WecStart( MaxRank + 2 );
 
    // collect boxes; mark inputs/outputs
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
//        if ( 37 == Box && 6 == Rank )
//        {
//            printf( "Skipping one adder...\n" );
//            continue;
//        }
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+0), 1 );
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+1), 1 );
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+2), 1 );
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+3), 1 );
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+4), 1 );
        Vec_WecPush( pBox->vAdds, Rank, Box );
    }
    // sort each level
    Vec_WecForEachLevel( pBox->vAdds, vLevel, i )
        Vec_IntSort( vLevel, 0 );
 
    // set phases starting from roots
    vMap = Acec_TreeCarryMap( p, vAdds, pBox->vAdds );
    Vec_WecForEachLevelReverse( pBox->vAdds, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
            if ( !Vec_BitEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+4) ) )
            {
                //printf( "Pushing phase of output %d of box %d\n", Vec_IntEntry(vAdds, 6*Box+4), Box );
                Acec_TreePhases_rec( p, vAdds, vMap, Vec_IntEntry(vAdds, 6*Box+4), Vec_IntEntry(vAdds, 6*Box+2) != 0, vVisit );
            }
    Acec_TreeVerifyPhases( p, vAdds, pBox->vAdds );
    Acec_TreeVerifyPhases2( p, vAdds, pBox->vAdds );
    Vec_BitFree( vVisit );
    Vec_IntFree( vMap );
 
    // collect inputs/outputs
    Vec_BitWriteEntry( vIsRoot, 0, 1 );
    Vec_WecForEachLevel( pBox->vAdds, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, j )
        {
            for ( k = 0; k < 3; k++ )
                if ( !Vec_BitEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+k) ) )
                    Vec_WecPush( pBox->vLeafLits, i, Abc_Var2Lit(Vec_IntEntry(vAdds, 6*Box+k), Acec_SignBit2(vAdds, Box, k)) );
            for ( k = 3; k < 5; k++ )
                if ( !Vec_BitEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+k) ) )
                {
                    //if ( Vec_IntEntry(vAdds, 6*Box+k) == 10942 )
                    //{
                    //    printf( "++++++++++++ Skipping special\n" );
                    //    continue;
                    //}
                    Vec_WecPush( pBox->vRootLits, k == 4 ? i + 1 : i, Abc_Var2Lit(Vec_IntEntry(vAdds, 6*Box+k), Acec_SignBit2(vAdds, Box, k)) );
                }
            if ( Vec_IntEntry(vAdds, 6*Box+2) == 0 && Acec_SignBit2(vAdds, Box, 2) )
                Vec_WecPush( pBox->vLeafLits, i, 1 );
        }
    Vec_BitFree( vIsLeaf );
    Vec_BitFree( vIsRoot );
    // sort each level
    Vec_WecForEachLevel( pBox->vLeafLits, vLevel, i )
        Vec_IntSort( vLevel, 0 );
    Vec_WecForEachLevel( pBox->vRootLits, vLevel, i )
        Vec_IntSort( vLevel, 1 );
    //return pBox;
/*
    // push literals forward
    //Vec_WecPrint( pBox->vLeafLits, 0 );
    Vec_WecForEachLevel( pBox->vLeafLits, vLevel, i )
    {
        int This, Prev = Vec_IntEntry(vLevel, 0);
        Vec_IntForEachEntryStart( vLevel, This, j, 1 )
        {
            if ( Prev != This )
            {
                Prev = This;
                continue;
            }
            if ( i+1 >= Vec_WecSize(pBox->vLeafLits) )
                continue;
            Vec_IntPushOrder( Vec_WecEntry(pBox->vLeafLits, i+1), This );
            Vec_IntDrop( vLevel, j-- );
            Vec_IntDrop( vLevel, j-- );
            Prev = -1;
            Count++;
        }
    }
    printf( "Pushed forward %d input literals.\n", Count );
*/
    //Vec_WecPrint( pBox->vLeafLits, 0 );
    return pBox;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_CreateBoxMaxRank()

int Acec_CreateBoxMaxRank

(

Vec_Int_t *

vTree

)

Definition at line 600 of file acecTree.c.

{
    int k, Box, Rank, MaxRank = 0;
    Vec_IntForEachEntryDouble( vTree, Box, Rank, k )
        MaxRank = Abc_MaxInt( MaxRank, Rank );
    return MaxRank;
}

Here is the caller graph for this function:

Acec_CreateBoxTest()

void Acec_CreateBoxTest

(

Gia_Man_t *

p

)

Definition at line 711 of file acecTree.c.

{
    Acec_Box_t * pBox;
    Vec_Wec_t * vTrees;
    Vec_Int_t * vTree;
 
    abctime clk = Abc_Clock();
    Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, 1 );
    int i, nFadds = Ree_ManCountFadds( vAdds );
    printf( "Detected %d adders (%d FAs and %d HAs).  ", Vec_IntSize(vAdds)/6, nFadds, Vec_IntSize(vAdds)/6-nFadds );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
 
    clk = Abc_Clock();
    vTrees = Acec_TreeFindTrees( p, vAdds, NULL, 0, 0 );
    printf( "Collected %d trees with %d adders in them.  ", Vec_WecSize(vTrees), Vec_WecSizeSize(vTrees)/2 );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    //Vec_WecPrint( vTrees, 0 );
 
    Vec_WecForEachLevel( vTrees, vTree, i )
    {
        pBox = Acec_CreateBox( p, vAdds, Vec_WecEntry(vTrees, i) );
        printf( "Processing tree %d:  Ranks = %d.  Adders = %d.  Leaves = %d.  Roots = %d.\n", 
            i, Vec_WecSize(pBox->vAdds), Vec_WecSizeSize(pBox->vAdds), 
            Vec_WecSizeSize(pBox->vLeafLits), Vec_WecSizeSize(pBox->vRootLits)  );
        Acec_TreePrintBox( pBox, vAdds );
        Acec_BoxFreeP( &pBox );
    }
 
    Vec_WecFree( vTrees );
    Vec_IntFree( vAdds );
}

Here is the call graph for this function:

Acec_DeriveBox()

Acec_Box_t * Acec_DeriveBox	(	Gia_Man_t *	p,
		Vec_Bit_t *	vIgnore,
		int	fFilterIn,
		int	fFilterOut,
		int	fVerbose )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 754 of file acecTree.c.

{
    Acec_Box_t * pBox = NULL;
    Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, fVerbose );
    Vec_Wec_t * vTrees = Acec_TreeFindTrees( p, vAdds, vIgnore, fFilterIn, fFilterOut );
    if ( vTrees && Vec_WecSize(vTrees) > 0 )
    {
        pBox = Acec_CreateBox( p, vAdds, Vec_WecEntry(vTrees, 0) );
        Acec_VerifyBoxLeaves( pBox, vIgnore );
    }
    if ( pBox )//&& fVerbose )
        printf( "Processing tree %d:  Ranks = %d.  Adders = %d.  Leaves = %d.  Roots = %d.\n", 
            0, Vec_WecSize(pBox->vAdds), Vec_WecSizeSize(pBox->vAdds), 
            Vec_WecSizeSize(pBox->vLeafLits), Vec_WecSizeSize(pBox->vRootLits)  );
    if ( pBox && fVerbose )
        Acec_TreePrintBox( pBox, vAdds );
    //Acec_PrintAdders( pBox0->vAdds, vAdds );
    //Acec_MultDetectInputs( p, pBox->vLeafLits, pBox->vRootLits );
    Vec_WecFreeP( &vTrees );
    Vec_IntFree( vAdds );
    return pBox;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_PrintAdders()

void Acec_PrintAdders	(	Vec_Wec_t *	vBoxes,
		Vec_Int_t *	vAdds )

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

Synopsis [Derives one adder tree.]

Description []

SideEffects []

SeeAlso [] `

Definition at line 570 of file acecTree.c.

{
    Vec_Int_t * vLevel;
    int i, k, iBox;
    Vec_WecForEachLevel( vBoxes, vLevel, i )
    {
        printf( " %4d : %2d  {", i, Vec_IntSize(vLevel) );
        Vec_IntForEachEntry( vLevel, iBox, k )
        {
            printf( " %s%d=(%d,%d)", Vec_IntEntry(vAdds, 6*iBox+2) == 0 ? "*":"", iBox, 
                                     Vec_IntEntry(vAdds, 6*iBox+3), Vec_IntEntry(vAdds, 6*iBox+4) );
            //printf( "(%d,%d,%d)", Vec_IntEntry(vAdds, 6*iBox+0), Vec_IntEntry(vAdds, 6*iBox+1), Vec_IntEntry(vAdds, 6*iBox+2) );
        }
        printf( " }\n" );
    }
}

Here is the caller graph for this function:

Acec_TreeAddInOutPoint()

void Acec_TreeAddInOutPoint	(	Vec_Int_t *	vMap,
		int	iObj,
		int	iAdd,
		int	fOut )

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

Synopsis [Find internal cut points with exactly one adder fanin/fanout.]

Description [Returns a map of point into its input/output adder.]

SideEffects []

SeeAlso []

Definition at line 436 of file acecTree.c.

{
    int * pPlace = Vec_IntEntryP( vMap, Abc_Var2Lit(iObj, fOut) );
    if ( *pPlace == -1 )
        *pPlace = iAdd;
    else if ( *pPlace >= 0 )
        *pPlace = -2;
}

Here is the caller graph for this function:

Acec_TreeCarryMap()

Vec_Int_t * Acec_TreeCarryMap	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Wec_t *	vBoxes )

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

Synopsis [Creates polarity.]

Description []

SideEffects []

SeeAlso []

Definition at line 379 of file acecTree.c.

{
    Vec_Int_t * vMap = Vec_IntStartFull( Gia_ManObjNum(p) );
    Vec_Int_t * vLevel;
    int i, k, Box;
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
            Vec_IntWriteEntry( vMap, Vec_IntEntry(vAdds, 6*Box+4), Box );
    return vMap;
}

Here is the caller graph for this function:

Acec_TreeFilterOne()

void Acec_TreeFilterOne	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Int_t *	vTree )

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

Synopsis [Filters trees by removing TFO of roots.]

Description []

SideEffects []

SeeAlso []

Definition at line 96 of file acecTree.c.

{
    Vec_Bit_t * vIsRoot = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Bit_t * vMarked = Vec_BitStart( Gia_ManObjNum(p) ) ;
    Gia_Obj_t * pObj;
    int i, k = 0, Box, Rank;
    // mark roots
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+3), 1 );
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+4), 1 );
    }
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+0), 0 );
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+1), 0 );
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+2), 0 );
    }
    // iterate through nodes to detect TFO of roots
    Gia_ManForEachAnd( p, pObj, i )
    {
        if ( Vec_BitEntry(vIsRoot, Gia_ObjFaninId0(pObj,i)) || Vec_BitEntry(vIsRoot, Gia_ObjFaninId1(pObj,i)) ||
             Vec_BitEntry(vMarked, Gia_ObjFaninId0(pObj,i)) || Vec_BitEntry(vMarked, Gia_ObjFaninId1(pObj,i)) )
            Vec_BitWriteEntry( vMarked, i, 1 );
    }
    // remove those that overlap with roots
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
        // special case of the first bit
//        if ( i == 0 )
//            continue;
 
/*
        if ( Vec_IntEntry(vAdds, 6*Box+3) == 24 && Vec_IntEntry(vAdds, 6*Box+4) == 22 )
        {
            printf( "**** removing special one \n" );
            continue;
        }
        if ( Vec_IntEntry(vAdds, 6*Box+3) == 48 && Vec_IntEntry(vAdds, 6*Box+4) == 49 )
        {
            printf( "**** removing special one \n" );
            continue;
        }
*/
        if ( Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+3)) || Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+4)) )
        {
            printf( "Removing box %d=(%d,%d) of rank %d.\n", Box, Vec_IntEntry(vAdds, 6*Box+3), Vec_IntEntry(vAdds, 6*Box+4), Rank ); 
            continue;
        }
        Vec_IntWriteEntry( vTree, k++, Box );
        Vec_IntWriteEntry( vTree, k++, Rank );
    }
    Vec_IntShrink( vTree, k );
    Vec_BitFree( vIsRoot );
    Vec_BitFree( vMarked );
}

Here is the caller graph for this function:

Acec_TreeFilterOne2()

void Acec_TreeFilterOne2	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Int_t *	vTree )

Definition at line 182 of file acecTree.c.

{
    Vec_Bit_t * vIsLeaf = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Bit_t * vMarked = Vec_BitStart( Gia_ManObjNum(p) ) ;
    Gia_Obj_t * pObj;
    int i, k = 0, Box, Rank;
    // mark leaves
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+0), 1 );
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+1), 1 );
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+2), 1 );
    }
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+3), 0 );
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+4), 0 );
    }
    // mark TFI of leaves
    Gia_ManForEachAnd( p, pObj, i )
        if ( Vec_BitEntry(vIsLeaf, i) )
            Acec_TreeMarkTFI_rec( p, i, vMarked );
    // additional one
//if ( 10942 < Gia_ManObjNum(p) )
//    Acec_TreeMarkTFI_rec( p, 10942, vMarked );
    // remove those that overlap with the marked TFI
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
        if ( Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+3)) || Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+4)) )
        {
            printf( "Removing box %d=(%d,%d) of rank %d.\n", Box, Vec_IntEntry(vAdds, 6*Box+3), Vec_IntEntry(vAdds, 6*Box+4), Rank ); 
            continue;
        }
        Vec_IntWriteEntry( vTree, k++, Box );
        Vec_IntWriteEntry( vTree, k++, Rank );
    }
    Vec_IntShrink( vTree, k );
    Vec_BitFree( vIsLeaf );
    Vec_BitFree( vMarked );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreeFilterTrees()

void Acec_TreeFilterTrees	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Wec_t *	vTrees )

Definition at line 152 of file acecTree.c.

{
    Vec_Int_t * vLevel;
    int i;
    Vec_WecForEachLevel( vTrees, vLevel, i )
        Acec_TreeFilterOne( p, vAdds, vLevel );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreeFilterTrees2()

void Acec_TreeFilterTrees2	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Wec_t *	vTrees )

Definition at line 222 of file acecTree.c.

{
    Vec_Int_t * vLevel;
    int i;
    Vec_WecForEachLevel( vTrees, vLevel, i )
        Acec_TreeFilterOne2( p, vAdds, vLevel );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreeFindPoints()

Vec_Int_t * Acec_TreeFindPoints	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Bit_t *	vIgnore )

Definition at line 444 of file acecTree.c.

{
    Vec_Int_t * vMap = Vec_IntStartFull( 2*Gia_ManObjNum(p) );
    int i;
    for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ )
    {
        if ( vIgnore && (Vec_BitEntry(vIgnore, Vec_IntEntry(vAdds, 6*i+3)) || Vec_BitEntry(vIgnore, Vec_IntEntry(vAdds, 6*i+4))) )
            continue;
        Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+0), i, 0 );
        Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+1), i, 0 );
        Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+2), i, 0 );
        Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+3), i, 1 );
        Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+4), i, 1 );
    }
    return vMap;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreeFindTrees()

Vec_Wec_t * Acec_TreeFindTrees	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Bit_t *	vIgnore,
		int	fFilterIn,
		int	fFilterOut )

Definition at line 503 of file acecTree.c.

{
    Vec_Wec_t * vTrees = Vec_WecAlloc( 10 );
    Vec_Int_t * vMap   = Acec_TreeFindPoints( p, vAdds, vIgnore );
    Vec_Bit_t * vFound = Vec_BitStart( Vec_IntSize(vAdds)/6 );
    Vec_Int_t * vTree;
    int i, k, In, Out, Box, Rank, MinRank;
    // go through the cut-points
    Vec_IntForEachEntryDouble( vMap, In, Out, i )
    {
        if ( In < 0 || Out < 0 )
            continue;
        assert( Vec_BitEntry(vFound, In) == Vec_BitEntry(vFound, Out) );
        if ( Vec_BitEntry(vFound, In) )
            continue;
        vTree = Vec_WecPushLevel( vTrees );
        Acec_TreeFindTrees_rec( vAdds, vMap, i/2, 0, vTree, vFound );
        // normalize rank
        MinRank = ABC_INFINITY;
        Vec_IntForEachEntryDouble( vTree, Box, Rank, k )
            MinRank = Abc_MinInt( MinRank, Rank );
        Vec_IntForEachEntryDouble( vTree, Box, Rank, k )
            Vec_IntWriteEntry( vTree, k+1, Rank - MinRank );
    }
    Vec_BitFree( vFound );
    Vec_IntFree( vMap );
    // filter trees
    if ( fFilterIn )
        Acec_TreeFilterTrees2( p, vAdds, vTrees );
    else if ( fFilterOut )
        Acec_TreeFilterTrees( p, vAdds, vTrees );
    // sort by size
    Vec_WecSort( vTrees, 1 );
    return vTrees;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreeFindTrees2_rec()

void Acec_TreeFindTrees2_rec	(	Vec_Int_t *	vAdds,
		Vec_Int_t *	vMap,
		int	iAdd,
		int	Rank,
		Vec_Int_t *	vTree,
		Vec_Bit_t *	vFound )

Definition at line 481 of file acecTree.c.

{
    extern void Acec_TreeFindTrees_rec( Vec_Int_t * vAdds, Vec_Int_t * vMap, int iObj, int Rank, Vec_Int_t * vTree, Vec_Bit_t * vFound );
    int k;
    if ( Vec_BitEntry(vFound, iAdd) )
        return;
    Vec_BitWriteEntry( vFound, iAdd, 1 );
    Vec_IntPush( vTree, iAdd );
    Vec_IntPush( vTree, Rank );
    //printf( "Assigning rank %d to (%d:%d).\n", Rank, Vec_IntEntry(vAdds, 6*iAdd+3), Vec_IntEntry(vAdds, 6*iAdd+4) );
    for ( k = 0; k < 5; k++ )
        Acec_TreeFindTrees_rec( vAdds, vMap, Vec_IntEntry(vAdds, 6*iAdd+k), k == 4 ? Rank + 1 : Rank, vTree, vFound );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreeFindTrees_rec()

void Acec_TreeFindTrees_rec	(	Vec_Int_t *	vAdds,
		Vec_Int_t *	vMap,
		int	iObj,
		int	Rank,
		Vec_Int_t *	vTree,
		Vec_Bit_t *	vFound )

Definition at line 494 of file acecTree.c.

{
    int In  = Vec_IntEntry( vMap, Abc_Var2Lit(iObj, 1) );
    int Out = Vec_IntEntry( vMap, Abc_Var2Lit(iObj, 0) );
    if ( In < 0 || Out < 0 )
        return;
    Acec_TreeFindTrees2_rec( vAdds, vMap, In,  Acec_TreeWhichPoint(vAdds, In, iObj) == 4 ? Rank-1 : Rank, vTree, vFound );
    Acec_TreeFindTrees2_rec( vAdds, vMap, Out, Rank, vTree, vFound );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreeFindTreesTest()

void Acec_TreeFindTreesTest

(

Gia_Man_t *

p

)

Definition at line 538 of file acecTree.c.

{
    Vec_Wec_t * vTrees;
 
    abctime clk = Abc_Clock();
    Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, 1 );
    int nFadds = Ree_ManCountFadds( vAdds );
    printf( "Detected %d adders (%d FAs and %d HAs).  ", Vec_IntSize(vAdds)/6, nFadds, Vec_IntSize(vAdds)/6-nFadds );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
 
    clk = Abc_Clock();
    vTrees = Acec_TreeFindTrees( p, vAdds, NULL, 0, 0 );
    printf( "Collected %d trees with %d adders in them.  ", Vec_WecSize(vTrees), Vec_WecSizeSize(vTrees)/2 );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    Vec_WecPrint( vTrees, 0 );
 
    Vec_WecFree( vTrees );
    Vec_IntFree( vAdds );
}

Here is the call graph for this function:

Acec_TreeMarkTFI_rec()

void Acec_TreeMarkTFI_rec	(	Gia_Man_t *	p,
		int	Id,
		Vec_Bit_t *	vMarked )

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

Synopsis [Filters trees by removing TFO of roots.]

Description []

SideEffects []

SeeAlso []

Definition at line 171 of file acecTree.c.

{
    Gia_Obj_t * pObj = Gia_ManObj(p, Id);
    if ( Vec_BitEntry(vMarked, Id) )
        return;
    Vec_BitWriteEntry( vMarked, Id, 1 );
    if ( !Gia_ObjIsAnd(pObj) )
        return;
    Acec_TreeMarkTFI_rec( p, Gia_ObjFaninId0(pObj, Id), vMarked );
    Acec_TreeMarkTFI_rec( p, Gia_ObjFaninId1(pObj, Id), vMarked );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreePhases_rec()

void Acec_TreePhases_rec	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Int_t *	vMap,
		int	Node,
		int	fPhase,
		Vec_Bit_t *	vVisit )

Definition at line 389 of file acecTree.c.

{
    int k, iBox, iXor, fXorPhase, fPhaseThis;
    assert( Node != 0 );
    iBox = Vec_IntEntry( vMap, Node );
    if ( iBox == -1 )
        return;
    assert( Node == Vec_IntEntry( vAdds, 6*iBox+4 ) );
    if ( Vec_BitEntry(vVisit, iBox) )
        return;
    Vec_BitWriteEntry( vVisit, iBox, 1 );
    iXor = Vec_IntEntry( vAdds, 6*iBox+3 );
    fXorPhase = Acec_SignBit(vAdds, iBox, 3);
    if ( Vec_IntEntry(vAdds, 6*iBox+2) == 0 )
    {
        //fPhaseThis = Acec_SignBit( vAdds, iBox, 2 ) ^ fPhase;
        //fXorPhase ^= fPhaseThis;
        //Acec_SignSetBit2( vAdds, iBox, 2, fPhaseThis ); // complemented HADD -- create const1 input
        fPhase ^= Acec_SignBit( vAdds, iBox, 2 );
        fXorPhase ^= fPhase;
        Acec_SignSetBit2( vAdds, iBox, 2, fPhase ); // complemented HADD -- create const1 input
    }
    for ( k = 0; k < 3; k++ )
    {
        int iObj = Vec_IntEntry( vAdds, 6*iBox+k );
        if ( iObj == 0 )
            continue;
        fPhaseThis = Acec_SignBit(vAdds, iBox, k) ^ fPhase;
        fXorPhase ^= fPhaseThis;
        Acec_TreePhases_rec( p, vAdds, vMap, iObj, fPhaseThis, vVisit );
        Acec_SignSetBit2( vAdds, iBox, k, fPhaseThis );
    }
    Acec_SignSetBit2( vAdds, iBox, 3, fXorPhase );
    Acec_SignSetBit2( vAdds, iBox, 4, fPhase );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreePrintBox()

void Acec_TreePrintBox	(	Acec_Box_t *	pBox,
		Vec_Int_t *	vAdds )

Definition at line 586 of file acecTree.c.

{
    printf( "Adders:\n" );
    Acec_PrintAdders( pBox->vAdds, vAdds );
    printf( "Inputs:\n" );
    Vec_WecPrintLits( pBox->vLeafLits );
    printf( "Outputs:\n" );
    Vec_WecPrintLits( pBox->vRootLits );
//    printf( "Node %d has level %d.\n", 3715, Gia_ObjLevelId(pBox->pGia, 3715) );
//    printf( "Node %d has level %d.\n", 167, Gia_ObjLevelId(pBox->pGia, 167) );
//    printf( "Node %d has level %d.\n", 278, Gia_ObjLevelId(pBox->pGia, 278) );
//    printf( "Node %d has level %d.\n", 597, Gia_ObjLevelId(pBox->pGia, 597) );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreeVerifyConnections()

void Acec_TreeVerifyConnections	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Wec_t *	vBoxes )

Definition at line 336 of file acecTree.c.

{
    Vec_Int_t * vCounts = Vec_IntStartFull( Gia_ManObjNum(p) );
    Vec_Int_t * vLevel;
    int i, k, n, Box;
    // mark outputs
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
        {
            Vec_IntWriteEntry( vCounts, Vec_IntEntry( vAdds, 6*Box+3 ), 0 );
            Vec_IntWriteEntry( vCounts, Vec_IntEntry( vAdds, 6*Box+4 ), 0 );
        }
    // count fanouts
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
            for ( n = 0; n < 3; n++ )
                if ( Vec_IntEntry( vCounts, Vec_IntEntry(vAdds, 6*Box+n) ) != -1 )
                    Vec_IntAddToEntry( vCounts, Vec_IntEntry(vAdds, 6*Box+n), 1 );
    // print out
    printf( "The adder tree has %d internal cut points. ", Vec_IntCountLarger(vCounts, -1) );
    if ( Vec_IntCountLarger(vCounts, 1) == 0 )
        printf( "There is no internal fanouts.\n" );
    else
    {
        printf( "These %d points have more than one fanout:\n", Vec_IntCountLarger(vCounts, 1) );
        Vec_IntForEachEntry( vCounts, Box, i )
            if ( Box > 1 )
                printf( "Node %d(lev %d) has fanout %d.\n", i, Gia_ObjLevelId(p, i), Box );
    }
    Vec_IntFree( vCounts );
}

Here is the caller graph for this function:

Acec_TreeVerifyPhaseOne()

void Acec_TreeVerifyPhaseOne	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		int	iBox )

Definition at line 255 of file acecTree.c.

{
    Gia_Obj_t * pObj;
    unsigned TruthXor, TruthMaj, Truths[3] = { 0xAA, 0xCC, 0xF0 };
    int k, iObj, fFadd = Vec_IntEntry(vAdds, 6*iBox+2) > 0;
    int fFlip = !fFadd && Acec_SignBit2(vAdds, iBox, 2);
 
    Gia_ManIncrementTravId( p );
    for ( k = 0; k < 3; k++ )
    {
        iObj = Vec_IntEntry( vAdds, 6*iBox+k );
        if ( iObj == 0 )
            continue;
        pObj = Gia_ManObj( p, iObj );
        pObj->Value = (Acec_SignBit2(vAdds, iBox, k) ^ fFlip) ? 0xFF & ~Truths[k] : Truths[k];
        Gia_ObjSetTravIdCurrent( p, pObj );
    }
 
    iObj = Vec_IntEntry( vAdds, 6*iBox+3 );
    TruthXor = Acec_TreeVerifyPhaseOne_rec( p, Gia_ManObj(p, iObj) );
    TruthXor = (Acec_SignBit2(vAdds, iBox, 3) ^ fFlip) ? 0xFF & ~TruthXor : TruthXor;
 
    iObj = Vec_IntEntry( vAdds, 6*iBox+4 );
    TruthMaj = Acec_TreeVerifyPhaseOne_rec( p, Gia_ManObj(p, iObj) );
    TruthMaj = (Acec_SignBit2(vAdds, iBox, 4) ^ fFlip) ? 0xFF & ~TruthMaj : TruthMaj;
 
    if ( fFadd ) // FADD
    {
        if ( TruthXor != 0x96 )
            printf( "Fadd %d sum %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+3 ) );
        if ( TruthMaj != 0xE8 )
            printf( "Fadd %d carry %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+4 ) );
    }
    else
    {
        //printf( "Sign1 = %d%d%d %d\n", Acec_SignBit(vAdds, iBox, 0), Acec_SignBit(vAdds, iBox, 1), Acec_SignBit(vAdds, iBox, 2), Acec_SignBit(vAdds, iBox, 3) );
        //printf( "Sign2 = %d%d%d %d%d\n", Acec_SignBit2(vAdds, iBox, 0), Acec_SignBit2(vAdds, iBox, 1), Acec_SignBit2(vAdds, iBox, 2), Acec_SignBit2(vAdds, iBox, 3), Acec_SignBit2(vAdds, iBox, 4) );
        if ( TruthXor != 0x66 )
            printf( "Hadd %d sum %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+3 ) );
        if ( TruthMaj != 0x88 )
            printf( "Hadd %d carry %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+4 ) );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreeVerifyPhaseOne_rec()

int Acec_TreeVerifyPhaseOne_rec	(	Gia_Man_t *	p,
		Gia_Obj_t *	pObj )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 241 of file acecTree.c.

{
    int Truth0, Truth1;
    if ( Gia_ObjIsTravIdCurrent(p, pObj) )
        return pObj->Value;
    Gia_ObjSetTravIdCurrent(p, pObj);
    assert( Gia_ObjIsAnd(pObj) );
    assert( !Gia_ObjIsXor(pObj) );
    Truth0 = Acec_TreeVerifyPhaseOne_rec( p, Gia_ObjFanin0(pObj) );
    Truth1 = Acec_TreeVerifyPhaseOne_rec( p, Gia_ObjFanin1(pObj) );
    Truth0 = Gia_ObjFaninC0(pObj) ? 0xFF & ~Truth0 : Truth0;
    Truth1 = Gia_ObjFaninC1(pObj) ? 0xFF & ~Truth1 : Truth1;
    return (pObj->Value = Truth0 & Truth1);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreeVerifyPhases()

void Acec_TreeVerifyPhases	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Wec_t *	vBoxes )

Definition at line 298 of file acecTree.c.

{
    Vec_Int_t * vLevel;
    int i, k, Box;
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
            Acec_TreeVerifyPhaseOne( p, vAdds, Box );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Acec_TreeVerifyPhases2()

void Acec_TreeVerifyPhases2	(	Gia_Man_t *	p,
		Vec_Int_t *	vAdds,
		Vec_Wec_t *	vBoxes )

Definition at line 306 of file acecTree.c.

{
    Vec_Bit_t * vPhase = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Bit_t * vRoots = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Int_t * vLevel;
    int i, k, n, Box;
    // mark all output points and their values
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
        {
            Vec_BitWriteEntry( vRoots, Vec_IntEntry( vAdds, 6*Box+3 ), 1 );
            Vec_BitWriteEntry( vRoots, Vec_IntEntry( vAdds, 6*Box+4 ), 1 );
            Vec_BitWriteEntry( vPhase, Vec_IntEntry( vAdds, 6*Box+3 ), Acec_SignBit2(vAdds, Box, 3) );
            Vec_BitWriteEntry( vPhase, Vec_IntEntry( vAdds, 6*Box+4 ), Acec_SignBit2(vAdds, Box, 4) );
        }
    // compare with input points
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
            for ( n = 0; n < 3; n++ )
            {
                if ( !Vec_BitEntry(vRoots, Vec_IntEntry(vAdds, 6*Box+n)) )
                    continue;
                if ( Vec_BitEntry(vPhase, Vec_IntEntry(vAdds, 6*Box+n)) == Acec_SignBit2(vAdds, Box, n) )
                    continue;
                printf( "Phase of input %d=%d is mismatched in box %d=(%d,%d).\n",
                    n, Vec_IntEntry(vAdds, 6*Box+n), Box, Vec_IntEntry(vAdds, 6*Box+3), Vec_IntEntry(vAdds, 6*Box+4) );
            }
    Vec_BitFree( vPhase );
    Vec_BitFree( vRoots );
}

Here is the caller graph for this function:

Acec_TreeWhichPoint()

int Acec_TreeWhichPoint	(	Vec_Int_t *	vAdds,
		int	iAdd,
		int	iObj )

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

Synopsis [Find adder trees as groups of adders connected vis cut-points.]

Description []

SideEffects []

SeeAlso []

Definition at line 472 of file acecTree.c.

{
    int k;
    for ( k = 0; k < 5; k++ )
        if ( Vec_IntEntry(vAdds, 6*iAdd+k) == iObj )
            return k;
    assert( 0 );
    return -1;
}

Here is the caller graph for this function:

Acec_VerifyBoxLeaves()

void Acec_VerifyBoxLeaves	(	Acec_Box_t *	pBox,
		Vec_Bit_t *	vIgnore )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 72 of file acecTree.c.

{
    Vec_Int_t * vLevel;
    int i, k, iLit, Count = 0;
    if ( vIgnore == NULL )
        return;
    Vec_WecForEachLevel( pBox->vLeafLits, vLevel, i )
        Vec_IntForEachEntry( vLevel, iLit, k )
            if ( Gia_ObjIsAnd(Gia_ManObj(pBox->pGia, Abc_Lit2Var(iLit))) && !Vec_BitEntry(vIgnore, Abc_Lit2Var(iLit)) )
                printf( "Internal node %d of rank %d is not part of PPG.\n", Abc_Lit2Var(iLit), i ), Count++;
    printf( "Detected %d suspicious leaves.\n", Count );
}

Here is the caller graph for this function: