/**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 $]
***********************************************************************/
#include "acecInt.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Acec_BoxFree( Acec_Box_t * pBox )
{
Vec_WecFreeP( &pBox->vAdds );
Vec_WecFreeP( &pBox->vLeafLits );
Vec_WecFreeP( &pBox->vRootLits );
Vec_WecFreeP( &pBox->vUnique );
Vec_WecFreeP( &pBox->vShared );
ABC_FREE( pBox );
}
void Acec_BoxFreeP( Acec_Box_t ** ppBox )
{
if ( *ppBox )
Acec_BoxFree( *ppBox );
*ppBox = NULL;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Acec_VerifyBoxLeaves( Acec_Box_t * pBox, Vec_Bit_t * vIgnore )
{
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 );
}
/**Function*************************************************************
Synopsis [Filters trees by removing TFO of roots.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Acec_TreeFilterOne( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vTree )
{
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 );
}
void Acec_TreeFilterTrees( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vTrees )
{
Vec_Int_t * vLevel;
int i;
Vec_WecForEachLevel( vTrees, vLevel, i )
Acec_TreeFilterOne( p, vAdds, vLevel );
}
/**Function*************************************************************
Synopsis [Filters trees by removing TFO of roots.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Acec_TreeMarkTFI_rec( Gia_Man_t * p, int Id, Vec_Bit_t * vMarked )
{
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 );
}
void Acec_TreeFilterOne2( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vTree )
{
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 );
}
void Acec_TreeFilterTrees2( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vTrees )
{
Vec_Int_t * vLevel;
int i;
Vec_WecForEachLevel( vTrees, vLevel, i )
Acec_TreeFilterOne2( p, vAdds, vLevel );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Acec_TreeVerifyPhaseOne_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
{
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);
}
void Acec_TreeVerifyPhaseOne( Gia_Man_t * p, Vec_Int_t * vAdds, int iBox )
{
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 ) );
}
}
void Acec_TreeVerifyPhases( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
{
Vec_Int_t * vLevel;
int i, k, Box;
Vec_WecForEachLevel( vBoxes, vLevel, i )
Vec_IntForEachEntry( vLevel, Box, k )
Acec_TreeVerifyPhaseOne( p, vAdds, Box );
}
void Acec_TreeVerifyPhases2( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
{
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 );
}
void Acec_TreeVerifyConnections( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
{
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 );
}
/**Function*************************************************************
Synopsis [Creates polarity.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Int_t * Acec_TreeCarryMap( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
{
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;
}
void Acec_TreePhases_rec( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vMap, int Node, int fPhase, Vec_Bit_t * vVisit )
{
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 );
}
/**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 []
***********************************************************************/
void Acec_TreeAddInOutPoint( Vec_Int_t * vMap, int iObj, int iAdd, int fOut )
{
int * pPlace = Vec_IntEntryP( vMap, Abc_Var2Lit(iObj, fOut) );
if ( *pPlace == -1 )
*pPlace = iAdd;
else if ( *pPlace >= 0 )
*pPlace = -2;
}
Vec_Int_t * Acec_TreeFindPoints( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Bit_t * vIgnore )
{
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;
}
/**Function*************************************************************
Synopsis [Find adder trees as groups of adders connected vis cut-points.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Acec_TreeWhichPoint( Vec_Int_t * vAdds, int iAdd, int iObj )
{
int k;
for ( k = 0; k < 5; k++ )
if ( Vec_IntEntry(vAdds, 6*iAdd+k) == iObj )
return k;
assert( 0 );
return -1;
}
void Acec_TreeFindTrees2_rec( Vec_Int_t * vAdds, Vec_Int_t * vMap, int iAdd, int Rank, Vec_Int_t * vTree, Vec_Bit_t * vFound )
{
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 );
}
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 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 );
}
Vec_Wec_t * Acec_TreeFindTrees( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Bit_t * vIgnore, int fFilterIn, int fFilterOut )
{
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;
}
void Acec_TreeFindTreesTest( Gia_Man_t * p )
{
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 );
}
/**Function*************************************************************
Synopsis [Derives one adder tree.]
Description []
SideEffects []
SeeAlso []
`
***********************************************************************/
void Acec_PrintAdders( Vec_Wec_t * vBoxes, Vec_Int_t * vAdds )
{
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" );
}
}
void Acec_TreePrintBox( Acec_Box_t * pBox, Vec_Int_t * vAdds )
{
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) );
}
int Acec_CreateBoxMaxRank( Vec_Int_t * vTree )
{
int k, Box, Rank, MaxRank = 0;
Vec_IntForEachEntryDouble( vTree, Box, Rank, k )
MaxRank = Abc_MaxInt( MaxRank, Rank );
return MaxRank;
}
Acec_Box_t * Acec_CreateBox( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vTree )
{
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;
}
void Acec_CreateBoxTest( Gia_Man_t * p )
{
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 );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Acec_Box_t * Acec_DeriveBox( Gia_Man_t * p, Vec_Bit_t * vIgnore, int fFilterIn, int fFilterOut, int fVerbose )
{
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;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END