/**CFile****************************************************************
FileName [acecOrder.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [CEC for arithmetic circuits.]
Synopsis [Node ordering.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: acecOrder.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 []
***********************************************************************/
Vec_Int_t * Gia_PolynFindOrder( Gia_Man_t * pGia, Vec_Int_t * vFadds, Vec_Int_t * vHadds, int fVerbose, int fVeryVerbose )
{
int fDumpLeftOver = 0;
int i, iXor, iMaj, iAnd, Entry, Iter, fFound, fFoundAll = 1;
Vec_Int_t * vRecord = Vec_IntAlloc( 100 ), * vLeft, * vRecord2;
Vec_Int_t * vMap = Vec_IntStart( Gia_ManObjNum(pGia) );
Gia_ManForEachCoDriverId( pGia, iAnd, i )
Vec_IntWriteEntry( vMap, iAnd, 1 );
// collect the last XOR
Vec_IntFreeP( &pGia->vXors );
pGia->vXors = Gia_PolynCollectLastXor( pGia, fVerbose );
printf( "Collected %d topmost XORs\n", Vec_IntSize(pGia->vXors) );
//Vec_IntPrint( p->vXors );
Vec_IntForEachEntry( pGia->vXors, iAnd, i )
{
Gia_Obj_t * pAnd = Gia_ManObj( pGia, iAnd );
assert( Vec_IntEntry(vMap, iAnd) );
Vec_IntWriteEntry( vMap, iAnd, 0 );
Vec_IntWriteEntry( vMap, Gia_ObjFaninId0(pAnd, iAnd), 1 );
Vec_IntWriteEntry( vMap, Gia_ObjFaninId1(pAnd, iAnd), 1 );
Vec_IntPush( vRecord, Abc_Var2Lit2(iAnd, 3) );
if ( fVeryVerbose )
printf( "Recognizing %d => XXXOR(%d %d)\n", iAnd, Gia_ObjFaninId0(pAnd, iAnd), Gia_ObjFaninId1(pAnd, iAnd) );
}
// detect FAs and HAs
for ( Iter = 0; fFoundAll; Iter++ )
{
if ( fVeryVerbose )
printf( "Iteration %d\n", Iter );
// check if we can extract FADDs
fFoundAll = 0;
do {
fFound = 0;
for ( i = Vec_IntSize(vFadds)/5 - 1; i >= 0; i-- )
{
iXor = Vec_IntEntry(vFadds, 5*i+3);
iMaj = Vec_IntEntry(vFadds, 5*i+4);
if ( Vec_IntEntry(vMap, iXor) && Vec_IntEntry(vMap, iMaj) )
{
Vec_IntWriteEntry( vMap, iXor, 0 );
Vec_IntWriteEntry( vMap, iMaj, 0 );
Vec_IntWriteEntry( vMap, Vec_IntEntry(vFadds, 5*i+0), 1 );
Vec_IntWriteEntry( vMap, Vec_IntEntry(vFadds, 5*i+1), 1 );
Vec_IntWriteEntry( vMap, Vec_IntEntry(vFadds, 5*i+2), 1 );
Vec_IntPush( vRecord, Abc_Var2Lit2(i, 2) );
fFound = 1;
fFoundAll = 1;
if ( fVeryVerbose )
printf( "Recognizing (%d %d) => FA(%d %d %d)\n", iXor, iMaj, Vec_IntEntry(vFadds, 5*i+0), Vec_IntEntry(vFadds, 5*i+1), Vec_IntEntry(vFadds, 5*i+2) );
}
}
} while ( fFound );
// check if we can extract HADDs
do {
fFound = 0;
for ( i = Vec_IntSize(vHadds)/2 - 1; i >= 0; i-- )
{
iXor = Vec_IntEntry(vHadds, 2*i+0);
iMaj = Vec_IntEntry(vHadds, 2*i+1);
if ( Vec_IntEntry(vMap, iXor) && Vec_IntEntry(vMap, iMaj) )
{
Gia_Obj_t * pAnd = Gia_ManObj( pGia, iMaj );
Vec_IntWriteEntry( vMap, iXor, 0 );
Vec_IntWriteEntry( vMap, iMaj, 0 );
Vec_IntWriteEntry( vMap, Gia_ObjFaninId0(pAnd, iMaj), 1 );
Vec_IntWriteEntry( vMap, Gia_ObjFaninId1(pAnd, iMaj), 1 );
Vec_IntPush( vRecord, Abc_Var2Lit2(i, 1) );
fFound = 1;
fFoundAll = 1;
if ( fVeryVerbose )
printf( "Recognizing (%d %d) => HA(%d %d)\n", iXor, iMaj, Gia_ObjFaninId0(pAnd, iMaj), Gia_ObjFaninId1(pAnd, iMaj) );
}
}
break; // only one iter!
} while ( fFound );
if ( fFoundAll )
continue;
/*
// find the last one
Vec_IntForEachEntryReverse( vMap, Entry, iAnd )
if ( Entry && Gia_ObjIsAnd(Gia_ManObj(pGia, iAnd)) )//&& Vec_IntFind(vFadds, iAnd) == -1 )//&& Vec_IntFind(vHadds, iAnd) == -1 )
{
Gia_Obj_t * pFan0, * pFan1, * pAnd = Gia_ManObj( pGia, iAnd );
if ( !Gia_ObjRecognizeExor(pAnd, &pFan0, &pFan1) )
{
Vec_IntWriteEntry( vMap, iAnd, 0 );
Vec_IntWriteEntry( vMap, Gia_ObjFaninId0(pAnd, iAnd), 1 );
Vec_IntWriteEntry( vMap, Gia_ObjFaninId1(pAnd, iAnd), 1 );
Vec_IntPush( vRecord, Abc_Var2Lit2(iAnd, 0) );
}
else
{
Vec_IntWriteEntry( vMap, iAnd, 0 );
Vec_IntWriteEntry( vMap, Gia_ObjId(pGia, pFan0), 1 );
Vec_IntWriteEntry( vMap, Gia_ObjId(pGia, pFan1), 1 );
Vec_IntPush( vRecord, Abc_Var2Lit2(iAnd, 0) );
Vec_IntPush( vRecord, Abc_Var2Lit2(Gia_ObjFaninId0(pAnd, iAnd), 0) );
Vec_IntPush( vRecord, Abc_Var2Lit2(Gia_ObjFaninId1(pAnd, iAnd), 0) );
printf( "Recognizing %d => XOR(%d %d)\n", iAnd, Gia_ObjId(pGia, pFan0), Gia_ObjId(pGia, pFan1) );
}
fFoundAll = 1;
if ( fVeryVerbose )
printf( "Recognizing %d => AND(%d %d)\n", iAnd, Gia_ObjFaninId0(pAnd, iAnd), Gia_ObjFaninId1(pAnd, iAnd) );
break;
}
*/
}
//Vec_IntPrint( vMap );
// collect remaining ones
vLeft = Vec_IntAlloc( 100 );
Vec_IntForEachEntry( vMap, Entry, i )
if ( Entry && Gia_ObjIsAnd(Gia_ManObj(pGia, i)) )
Vec_IntPush( vLeft, i );
Vec_IntFree( vMap );
// collect them in the topo order
vRecord2 = Vec_IntAlloc( 100 );
Gia_ManIncrementTravId( pGia );
Gia_ManCollectAnds( pGia, Vec_IntArray(vLeft), Vec_IntSize(vLeft), vRecord2, NULL );
Vec_IntForEachEntry( vRecord2, iAnd, i )
Vec_IntWriteEntry( vRecord2, i, Abc_Var2Lit2(iAnd, 0) );
// dump remaining nodes as an AIG
if ( fDumpLeftOver )
{
Gia_Man_t * pNew;
pNew = Gia_ManDupAndCones( pGia, Vec_IntArray(vLeft), Vec_IntSize(vLeft), 0 );
Gia_AigerWrite( pNew, "leftover.aig", 0, 0 );
printf( "Leftover AIG with %d nodes is dumped into file \"%s\".\n", Gia_ManAndNum(pNew), "leftover.aig" );
Gia_ManStop( pNew );
}
Vec_IntFree( vLeft );
Vec_IntReverseOrder( vRecord );
Vec_IntAppend( vRecord2, vRecord );
Vec_IntFree( vRecord );
return vRecord2;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Int_t * Gia_PolynReorder( Gia_Man_t * pGia, int fVerbose, int fVeryVerbose )
{
Vec_Int_t * vFadds = Gia_ManDetectFullAdders( pGia, fVeryVerbose );
Vec_Int_t * vHadds = Gia_ManDetectHalfAdders( pGia, fVeryVerbose );
Vec_Int_t * vRecord = Gia_PolynFindOrder( pGia, vFadds, vHadds, fVerbose, fVeryVerbose );
Vec_Int_t * vOrder = Vec_IntAlloc( Gia_ManAndNum(pGia) );
Vec_Int_t * vOrder2 = Vec_IntStart( Gia_ManObjNum(pGia) );
int i, k, Entry;
// collect nodes
Gia_ManIncrementTravId( pGia );
Vec_IntForEachEntry( vRecord, Entry, i )
{
int Node = Abc_Lit2Var2(Entry);
int Attr = Abc_Lit2Att2(Entry);
if ( Attr == 2 )
{
int * pFanins = Vec_IntEntryP( vFadds, 5*Node );
for ( k = 3; k < 5; k++ )
Gia_ManCollectAnds_rec( pGia, pFanins[k], vOrder );
}
else if ( Attr == 1 )
{
int * pFanins = Vec_IntEntryP( vHadds, 2*Node );
for ( k = 0; k < 2; k++ )
Gia_ManCollectAnds_rec( pGia, pFanins[k], vOrder );
}
else
Gia_ManCollectAnds_rec( pGia, Node, vOrder );
//printf( "Order = %d. Node = %d. Size = %d ", i, Node, Vec_IntSize(vOrder) );
}
//printf( "\n" );
//assert( Vec_IntSize(vOrder) == Gia_ManAndNum(pGia) );
// remap order
Gia_ManForEachCiId( pGia, Entry, i )
Vec_IntWriteEntry( vOrder2, Entry, 1+i );
Vec_IntForEachEntry( vOrder, Entry, i )
Vec_IntWriteEntry( vOrder2, Entry, 1+Gia_ManCiNum(pGia)+i );
//Vec_IntPrint( vOrder );
Vec_IntFree( vRecord );
Vec_IntFree( vFadds );
Vec_IntFree( vHadds );
Vec_IntFree( vOrder );
return vOrder2;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END