/**CFile****************************************************************
FileName [abcRec2.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Network and node package.]
Synopsis [Record of semi-canonical AIG subgraphs.]
Author [Allan Yang, Alan Mishchenko]
Affiliation [Fudan University in Shanghai, UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: abcRec.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "base/abc/abc.h"
#include "map/if/if.h"
#include "bool/kit/kit.h"
#include "aig/gia/giaAig.h"
#include "misc/vec/vecMem.h"
#include "opt/dau/dau.h"
#include "misc/util/utilTruth.h"
ABC_NAMESPACE_IMPL_START
#define LMS_VAR_MAX 16 // LMS_VAR_MAX >= 6
#define LMS_MAX_WORD (1<<(LMS_VAR_MAX-6))
//#define LMS_USE_OLD_FORM
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
/*
This LMS manager can be used in two modes:
- library constuction
- AIG level minimization
To switch from library construction to AIG level minimization
LSM manager should be restarted by dumping GIA (rec_dump3 <file>.aig)
and starting LMS manager again (rec_start3 <file>.aig).
*/
typedef struct Lms_Man_t_ Lms_Man_t;
struct Lms_Man_t_
{
// parameters
int nVars; // the number of variables
int nWords; // the number of TT words
int nCuts; // the max number of cuts to use
int fFuncOnly; // record only functions
int fLibConstr; // this manager is used for library construction
// internal data for library construction
Gia_Man_t * pGia; // the record
Vec_Mem_t * vTtMem; // truth table memory and hash table
// Vec_Mem_t * vTtMem2; // truth table memory and hash table
Vec_Int_t * vTruthIds; // truth table IDs of each PO
// internal data for AIG level minimization (allocated the first time it is called)
Vec_Int_t * vTruthPo; // first PO where this canonicized truth table was seen
Vec_Wrd_t * vDelays; // pin-to-pin delays of each PO
Vec_Str_t * vAreas; // number of AND gates in each PO
Vec_Int_t * vFreqs; // subgraph usage frequencies
Vec_Int_t * vTruthFreqs; // truth table usage frequencies
// temporaries
Vec_Ptr_t * vNodes; // the temporary nodes
Vec_Ptr_t * vLabelsP; // temporary storage for HOP node labels
Vec_Int_t * vLabels; // temporary storage for AIG node labels
Vec_Str_t * vSupps; // used temporarily by TT dumping
word pTemp1[LMS_MAX_WORD]; // copy of the truth table
word pTemp2[LMS_MAX_WORD]; // copy of the truth table
// statistics
int nTried;
int nFilterSize;
int nFilterRedund;
int nFilterVolume;
int nFilterTruth;
int nFilterError;
int nFilterSame;
int nAdded;
int nAddedFuncs;
int nHoleInTheWall;
// runtime
clock_t timeTruth;
clock_t timeCanon;
clock_t timeBuild;
clock_t timeCheck;
clock_t timeInsert;
clock_t timeOther;
clock_t timeTotal;
};
static Lms_Man_t * s_pMan3 = NULL;
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Compute delay/area profiles of POs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Lms_DelayGet( word D, int v ) { assert(v >= 0 && v < LMS_VAR_MAX); return (int)((D >> (v << 2)) & 0xF); }
static inline void Lms_DelaySet( word * pD, int v, int d ) { assert(v >= 0 && v < LMS_VAR_MAX); assert(d >= 0 && d < LMS_VAR_MAX); *pD |= ((word)d << (v << 2)); }
static inline word Lms_DelayInit( int v ) { assert(v >= 0 && v < LMS_VAR_MAX); return (word)1 << (v << 2); }
static inline word Lms_DelayMax( word D1, word D2, int nVars )
{
int v, Max;
word D = 0;
for ( v = 0; v < nVars; v++ )
if ( (Max = Abc_MaxInt(Lms_DelayGet(D1, v), Lms_DelayGet(D2, v))) )
Lms_DelaySet( &D, v, Abc_MinInt(Max + 1, 15) );
return D;
}
static inline word Lms_DelayDecrement( word D1, int nVars )
{
int v;
word D = 0;
for ( v = 0; v < nVars; v++ )
if ( Lms_DelayGet(D1, v) )
Lms_DelaySet( &D, v, Lms_DelayGet(D1, v) - 1 );
return D;
}
static inline int Lms_DelayEqual( word D1, word D2, int nVars ) // returns 1 if D1 has the same delays than D2
{
int v;
for ( v = 0; v < nVars; v++ )
if ( Lms_DelayGet(D1, v) != Lms_DelayGet(D2, v) )
return 0;
return 1;
}
static inline int Lms_DelayDom( word D1, word D2, int nVars ) // returns 1 if D1 has the same or smaller delays than D2
{
int v;
for ( v = 0; v < nVars; v++ )
if ( Lms_DelayGet(D1, v) > Lms_DelayGet(D2, v) )
return 0;
return 1;
}
static inline void Lms_DelayPrint( word D, int nVars )
{
int v;
printf( "Delay profile = {" );
for ( v = 0; v < nVars; v++ )
printf( " %d", Lms_DelayGet(D, v) );
printf( " }\n" );
}
Vec_Wrd_t * Lms_GiaDelays( Gia_Man_t * p )
{
Vec_Wrd_t * vDelays, * vResult;
Gia_Obj_t * pObj;
int i;
// compute delay profiles of all objects
vDelays = Vec_WrdAlloc( Gia_ManObjNum(p) );
Vec_WrdPush( vDelays, 0 ); // const 0
Gia_ManForEachObj1( p, pObj, i )
{
if ( Gia_ObjIsAnd(pObj) )
Vec_WrdPush( vDelays, Lms_DelayMax( Vec_WrdEntry(vDelays, Gia_ObjFaninId0(pObj, i)), Vec_WrdEntry(vDelays, Gia_ObjFaninId1(pObj, i)), Gia_ManCiNum(p) ) );
else if ( Gia_ObjIsCo(pObj) )
Vec_WrdPush( vDelays, Lms_DelayDecrement( Vec_WrdEntry(vDelays, Gia_ObjFaninId0(pObj, i)), Gia_ManCiNum(p) ) );
else if ( Gia_ObjIsCi(pObj) )
Vec_WrdPush( vDelays, Lms_DelayInit( Gia_ObjCioId(pObj) ) );
else assert( 0 );
}
// collect delay profiles of COs only
vResult = Vec_WrdAlloc( Gia_ManCoNum(p) );
Gia_ManForEachCo( p, pObj, i )
Vec_WrdPush( vResult, Vec_WrdEntry(vDelays, Gia_ObjId(p, pObj)) );
Vec_WrdFree( vDelays );
return vResult;
}
void Lms_ObjAreaMark_rec( Gia_Obj_t * pObj )
{
if ( pObj->fMark0 || Gia_ObjIsCi(pObj) )
return;
pObj->fMark0 = 1;
Lms_ObjAreaMark_rec( Gia_ObjFanin0(pObj) );
Lms_ObjAreaMark_rec( Gia_ObjFanin1(pObj) );
}
int Lms_ObjAreaUnmark_rec( Gia_Obj_t * pObj )
{
if ( !pObj->fMark0 || Gia_ObjIsCi(pObj) )
return 0;
pObj->fMark0 = 0;
return 1 + Lms_ObjAreaUnmark_rec( Gia_ObjFanin0(pObj) )
+ Lms_ObjAreaUnmark_rec( Gia_ObjFanin1(pObj) );
}
int Lms_ObjArea( Gia_Obj_t * pObj )
{
assert( Gia_ObjIsAnd(pObj) );
Lms_ObjAreaMark_rec( pObj );
return Lms_ObjAreaUnmark_rec( pObj );
}
Vec_Str_t * Lms_GiaAreas( Gia_Man_t * p )
{
Vec_Str_t * vAreas;
Gia_Obj_t * pObj;
int i;
vAreas = Vec_StrAlloc( Gia_ManCoNum(p) );
Gia_ManForEachCo( p, pObj, i )
Vec_StrPush( vAreas, (char)(Gia_ObjIsAnd(Gia_ObjFanin0(pObj)) ? Lms_ObjArea(Gia_ObjFanin0(pObj)) : 0) );
return vAreas;
}
Vec_Str_t * Lms_GiaSuppSizes( Gia_Man_t * p )
{
Vec_Str_t * vResult;
Vec_Str_t * vSupps;
Gia_Obj_t * pObj;
int i;
vSupps = Vec_StrAlloc( Gia_ManObjNum(p) );
Vec_StrPush( vSupps, 0 );
Gia_ManForEachObj1( p, pObj, i )
{
if ( Gia_ObjIsAnd(pObj) )
Vec_StrPush( vSupps, (char)Abc_MaxInt( Vec_StrEntry(vSupps, Gia_ObjFaninId0(pObj, i)), Vec_StrEntry(vSupps, Gia_ObjFaninId1(pObj, i)) ) );
else if ( Gia_ObjIsCo(pObj) )
Vec_StrPush( vSupps, Vec_StrEntry(vSupps, Gia_ObjFaninId0(pObj, i)) );
else if ( Gia_ObjIsCi(pObj) )
Vec_StrPush( vSupps, (char)(Gia_ObjCioId(pObj)+1) );
else assert( 0 );
}
assert( Vec_StrSize(vSupps) == Gia_ManObjNum(p) );
vResult = Vec_StrAlloc( Gia_ManCoNum(p) );
Gia_ManForEachCo( p, pObj, i )
Vec_StrPush( vResult, Vec_StrEntry(vSupps, Gia_ObjId(p, pObj)) );
Vec_StrFree( vSupps );
return vResult;
}
void Lms_GiaProfilesPrint( Gia_Man_t * p )
{
Gia_Obj_t * pObj;
int i;
Vec_Wrd_t * vDelays;
Vec_Str_t * vAreas;
vDelays = Lms_GiaDelays( p );
vAreas = Lms_GiaAreas( p );
Gia_ManForEachPo( p, pObj, i )
{
printf( "%6d : ", i );
printf( "A = %2d ", Vec_StrEntry(vAreas, i) );
Lms_DelayPrint( Vec_WrdEntry(vDelays, i), Gia_ManPiNum(p) );
// Lms_GiaPrintSubgraph( p, pObj );
// printf( "\n" );
}
Vec_WrdFree( vDelays );
Vec_StrFree( vAreas );
}
/**Function*************************************************************
Synopsis [Prints one GIA subgraph.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Lms_GiaPrintSubgraph_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
{
if ( !pObj->fMark0 || Gia_ObjIsCi(pObj) )
return;
pObj->fMark0 = 0;
assert( Gia_ObjIsAnd(pObj) );
Lms_GiaPrintSubgraph_rec( p, Gia_ObjFanin0(pObj) );
Lms_GiaPrintSubgraph_rec( p, Gia_ObjFanin1(pObj) );
Gia_ObjPrint( p, pObj );
}
void Lms_GiaPrintSubgraph( Gia_Man_t * p, Gia_Obj_t * pObj )
{
assert( Gia_ObjIsCo(pObj) );
if ( Gia_ObjIsAnd(Gia_ObjFanin0(pObj)) )
{
Lms_ObjAreaMark_rec( Gia_ObjFanin0(pObj) );
Lms_GiaPrintSubgraph_rec( p, Gia_ObjFanin0(pObj) );
}
else
Gia_ObjPrint( p, Gia_ObjFanin0(pObj) );
Gia_ObjPrint( p, pObj );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Lms_Man_t * Lms_ManStart( Gia_Man_t * pGia, int nVars, int nCuts, int fFuncOnly, int fVerbose )
{
Lms_Man_t * p;
clock_t clk, clk2 = clock();
// if GIA is given, use the number of variables from GIA
nVars = pGia ? Gia_ManCiNum(pGia) : nVars;
assert( nVars >= 6 && nVars <= LMS_VAR_MAX );
// allocate manager
p = ABC_CALLOC( Lms_Man_t, 1 );
// parameters
p->nVars = nVars;
p->nCuts = nCuts;
p->nWords = Abc_Truth6WordNum( nVars );
p->fFuncOnly = fFuncOnly;
// internal data for library construction
p->vTtMem = Vec_MemAlloc( p->nWords, 12 ); // 32 KB/page for 6-var functions
// p->vTtMem2 = Vec_MemAlloc( p->nWords, 12 ); // 32 KB/page for 6-var functions
Vec_MemHashAlloc( p->vTtMem, 10000 );
// Vec_MemHashAlloc( p->vTtMem2, 10000 );
if ( fFuncOnly )
return p;
p->vTruthIds = Vec_IntAlloc( 10000 );
if ( pGia == NULL )
{
int i;
p->pGia = Gia_ManStart( 10000 );
p->pGia->pName = Abc_UtilStrsav( "record" );
for ( i = 0; i < nVars; i++ )
Gia_ManAppendCi( p->pGia );
}
else
{
Gia_Obj_t * pObj;
word * pTruth;
int i, Index, Prev = -1;
p->pGia = pGia;
// populate the manager with subgraphs present in GIA
p->nAdded = Gia_ManCoNum( p->pGia );
Gia_ManForEachCo( p->pGia, pObj, i )
{
clk = clock();
pTruth = Gia_ObjComputeTruthTable( p->pGia, pObj );
p->timeTruth += clock() - clk;
clk = clock();
Index = Vec_MemHashInsert( p->vTtMem, pTruth );
p->timeInsert += clock() - clk;
assert( Index == Prev || Index == Prev + 1 ); // GIA subgraphs should be ordered
Vec_IntPush( p->vTruthIds, Index );
Prev = Index;
}
}
// temporaries
p->vNodes = Vec_PtrAlloc( 1000 );
p->vLabelsP = Vec_PtrAlloc( 1000 );
p->vLabels = Vec_IntAlloc( 1000 );
p->timeTotal += clock() - clk2;
return p;
}
void Lms_ManStop( Lms_Man_t * p )
{
// temporaries
Vec_IntFreeP( &p->vLabels );
Vec_PtrFreeP( &p->vLabelsP );
Vec_PtrFreeP( &p->vNodes );
// internal data for AIG level minimization
Vec_IntFreeP( &p->vTruthPo );
Vec_WrdFreeP( &p->vDelays );
Vec_StrFreeP( &p->vAreas );
Vec_IntFreeP( &p->vFreqs );
Vec_IntFreeP( &p->vTruthFreqs );
// internal data for library construction
Vec_IntFreeP( &p->vTruthIds );
Vec_MemHashFree( p->vTtMem );
// Vec_MemHashFree( p->vTtMem2 );
Vec_MemFree( p->vTtMem );
// Vec_MemFree( p->vTtMem2 );
Gia_ManStopP( &p->pGia );
ABC_FREE( p );
}
void Lms_ManPrepare( Lms_Man_t * p )
{
// compute the first PO for each semi-canonical form
int i, Entry;
assert( !p->fLibConstr );
assert( p->vTruthPo == NULL );
p->vTruthPo = Vec_IntStartFull( Vec_MemEntryNum(p->vTtMem)+1 );
assert( Vec_IntFindMin(p->vTruthIds) >= 0 );
assert( Vec_IntFindMax(p->vTruthIds) < Vec_MemEntryNum(p->vTtMem) );
Vec_IntForEachEntry( p->vTruthIds, Entry, i )
if ( Vec_IntEntry(p->vTruthPo, Entry) == -1 )
Vec_IntWriteEntry( p->vTruthPo, Entry, i );
Vec_IntWriteEntry( p->vTruthPo, Vec_MemEntryNum(p->vTtMem), Gia_ManCoNum(p->pGia) );
// compute delay/area and init frequency
assert( p->vDelays == NULL );
assert( p->vAreas == NULL );
assert( p->vFreqs == NULL );
p->vDelays = Lms_GiaDelays( p->pGia );
p->vAreas = Lms_GiaAreas( p->pGia );
p->vFreqs = Vec_IntStart( Gia_ManCoNum(p->pGia) );
}
void Lms_ManPrintFuncStats( Lms_Man_t * p )
{
Vec_Str_t * vSupps;
int Counters[LMS_VAR_MAX+1] = {0}, CountersS[LMS_VAR_MAX+1] = {0};
int i, Entry, Next;
if ( p->pGia == NULL )
return;
if ( p->fLibConstr )
return;
if ( p->vTruthPo == NULL )
Lms_ManPrepare( p );
vSupps = Lms_GiaSuppSizes( p->pGia );
Vec_IntForEachEntry( p->vTruthPo, Entry, i )
{
if ( i == Vec_IntSize(p->vTruthPo) - 1 )
break;
Next = Vec_IntEntry( p->vTruthPo, i+1 );
Counters[(int)Vec_StrEntry(vSupps, Entry)]++;
CountersS[(int)Vec_StrEntry(vSupps, Entry)] += Next - Entry;
}
for ( i = 0; i <= LMS_VAR_MAX; i++ )
if ( Counters[i] )
printf( "Inputs = %2d. Funcs = %8d. Subgrs = %8d. Ratio = %6.2f.\n", i, Counters[i], CountersS[i], 1.0*CountersS[i]/Counters[i] );
Vec_StrFree( vSupps );
}
void Lms_ManPrintFreqStats( Lms_Man_t * p )
{
int CountDsdNpn[3] = {0}; // full/part/none
int CountDsdAll[3] = {0}; // full/part/none
int CountStepNpn[3] = {0}; // full/1step/complex
int CountStepAll[3] = {0}; // full/1step/complex
char pBuffer[1000];
int nSuppSize;
int nNonDecSize;
word * pTruth;
int i, Freq, Status;
printf( "Cuts = %10d. ", p->nTried );
// printf( "Funcs = %10d (%6.2f %%). ", Vec_MemEntryNum(p->vTtMem2), 100.0*Vec_MemEntryNum(p->vTtMem2)/p->nTried );
printf( "Class = %10d (%6.2f %%). ", Vec_MemEntryNum(p->vTtMem), 100.0*Vec_MemEntryNum(p->vTtMem)/p->nTried );
printf( "\n" );
// return;
Vec_IntForEachEntry( p->vTruthFreqs, Freq, i )
{
pTruth = Vec_MemReadEntry(p->vTtMem, i);
/*
printf( "%6d -- %6d : ", i, Freq );
Kit_DsdWriteFromTruth( pBuffer, (unsigned *)pTruth, p->nVars );
printf( "%s\n", pBuffer );
*/
nSuppSize = Abc_TtSupportSize( pTruth, p->nVars );
nNonDecSize = Dau_DsdDecompose( pTruth, p->nVars, 0, 0, pBuffer );
if ( nNonDecSize == 0 )
{
CountDsdNpn[0]++;
CountDsdAll[0] += Freq;
}
else if ( nNonDecSize < nSuppSize )
{
CountDsdNpn[1]++;
CountDsdAll[1] += Freq;
}
else // non-dec
{
CountDsdNpn[2]++;
CountDsdAll[2] += Freq;
}
if ( nNonDecSize == 0 )
{
CountStepNpn[0]++;
CountStepAll[0] += Freq;
continue;
}
// check the non dec core
Status = Dau_DsdCheck1Step( pTruth, nNonDecSize );
if ( Status >= 0 )
{
CountStepNpn[1]++;
CountStepAll[1] += Freq;
}
else
{
assert( Status == -2 );
CountStepNpn[2]++;
CountStepAll[2] += Freq;
}
}
// print the results
printf( "NPN: " );
printf( "Full = %6.2f %% ", 100.0 * CountDsdNpn[0] / Vec_MemEntryNum(p->vTtMem) );
printf( "Part = %6.2f %% ", 100.0 * CountDsdNpn[1] / Vec_MemEntryNum(p->vTtMem) );
printf( "None = %6.2f %% ", 100.0 * CountDsdNpn[2] / Vec_MemEntryNum(p->vTtMem) );
// printf( "\n" );
printf( " " );
// print the results
printf( "All: " );
printf( "Full = %6.2f %% ", 100.0 * CountDsdAll[0] / p->nTried );
printf( "Part = %6.2f %% ", 100.0 * CountDsdAll[1] / p->nTried );
printf( "None = %6.2f %% ", 100.0 * CountDsdAll[2] / p->nTried );
printf( "\n" );
// print the results
printf( "NPN: " );
printf( "Full = %6.2f %% ", 100.0 * CountStepNpn[0] / Vec_MemEntryNum(p->vTtMem) );
printf( "1stp = %6.2f %% ", 100.0 * CountStepNpn[1] / Vec_MemEntryNum(p->vTtMem) );
printf( "Comp = %6.2f %% ", 100.0 * CountStepNpn[2] / Vec_MemEntryNum(p->vTtMem) );
// printf( "\n" );
printf( " " );
// print the results
printf( "All: " );
printf( "Full = %6.2f %% ", 100.0 * CountStepAll[0] / p->nTried );
printf( "1stp = %6.2f %% ", 100.0 * CountStepAll[1] / p->nTried );
printf( "Comp = %6.2f %% ", 100.0 * CountStepAll[2] / p->nTried );
printf( "\n" );
}
void Lms_ManPrint( Lms_Man_t * p )
{
// Gia_ManPrintStats( p->pGia, 0, 0 );
printf( "Library with %d vars has %d classes and %d AIG subgraphs with %d AND nodes.\n",
p->nVars, Vec_MemEntryNum(p->vTtMem), p->nAdded, p->pGia ? Gia_ManAndNum(p->pGia) : 0 );
// Lms_ManPrintFreqStats( p );
Lms_ManPrintFuncStats( p );
p->nAddedFuncs = Vec_MemEntryNum(p->vTtMem);
printf( "Subgraphs tried = %10d. (%6.2f %%)\n", p->nTried, !p->nTried? 0 : 100.0*p->nTried/p->nTried );
printf( "Subgraphs filtered by support size = %10d. (%6.2f %%)\n", p->nFilterSize, !p->nTried? 0 : 100.0*p->nFilterSize/p->nTried );
printf( "Subgraphs filtered by structural redundancy = %10d. (%6.2f %%)\n", p->nFilterRedund, !p->nTried? 0 : 100.0*p->nFilterRedund/p->nTried );
printf( "Subgraphs filtered by volume = %10d. (%6.2f %%)\n", p->nFilterVolume, !p->nTried? 0 : 100.0*p->nFilterVolume/p->nTried );
printf( "Subgraphs filtered by TT redundancy = %10d. (%6.2f %%)\n", p->nFilterTruth, !p->nTried? 0 : 100.0*p->nFilterTruth/p->nTried );
printf( "Subgraphs filtered by error = %10d. (%6.2f %%)\n", p->nFilterError, !p->nTried? 0 : 100.0*p->nFilterError/p->nTried );
printf( "Subgraphs filtered by isomorphism = %10d. (%6.2f %%)\n", p->nFilterSame, !p->nTried? 0 : 100.0*p->nFilterSame/p->nTried );
printf( "Subgraphs added = %10d. (%6.2f %%)\n", p->nAdded, !p->nTried? 0 : 100.0*p->nAdded/p->nTried );
printf( "Functions added = %10d. (%6.2f %%)\n", p->nAddedFuncs, !p->nTried? 0 : 100.0*p->nAddedFuncs/p->nTried );
if ( p->nHoleInTheWall )
printf( "Cuts whose logic structure has a hole = %10d. (%6.2f %%)\n", p->nHoleInTheWall, !p->nTried? 0 : 100.0*p->nHoleInTheWall/p->nTried );
p->timeOther = p->timeTotal - p->timeTruth - p->timeCanon - p->timeBuild - p->timeCheck - p->timeInsert;
ABC_PRTP( "Runtime: Truth ", p->timeTruth, p->timeTotal );
ABC_PRTP( "Runtime: Canon ", p->timeCanon, p->timeTotal );
ABC_PRTP( "Runtime: Build ", p->timeBuild, p->timeTotal );
ABC_PRTP( "Runtime: Check ", p->timeCheck, p->timeTotal );
ABC_PRTP( "Runtime: Insert", p->timeInsert, p->timeTotal );
ABC_PRTP( "Runtime: Other ", p->timeOther, p->timeTotal );
ABC_PRTP( "Runtime: TOTAL ", p->timeTotal, p->timeTotal );
}
/**Function*************************************************************
Synopsis [Recanonicizes the library and add it to the current library.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkRecLibMerge3( Gia_Man_t * pLib )
{
int fCheck = 0;
Lms_Man_t * p = s_pMan3;
Gia_Man_t * pGia = p->pGia;
Vec_Str_t * vSupps;
char pCanonPerm[LMS_VAR_MAX];
unsigned uCanonPhase;
word * pTruth;
int i, k, Index, iFanin0, iFanin1, nLeaves;
Gia_Obj_t * pObjPo, * pDriver, * pTemp = NULL;
clock_t clk, clk2 = clock();
if ( Gia_ManCiNum(pLib) != Gia_ManCiNum(pGia) )
{
printf( "The number of Library inputs (%d) differs from the number of Gia inputs (%d).\n", Gia_ManCiNum(pLib), Gia_ManCiNum(pGia) );
return;
}
assert( Gia_ManCiNum(pLib) == Gia_ManCiNum(pGia) );
// create hash table if not available
if ( pGia->pHTable == NULL )
Gia_ManHashStart( pGia );
// add AIG subgraphs
vSupps = Lms_GiaSuppSizes( pLib );
Gia_ManForEachCo( pLib, pObjPo, k )
{
// get support size
nLeaves = Vec_StrEntry(vSupps, k);
assert( nLeaves > 1 );
// compute the truth table
clk = clock();
pTruth = Gia_ObjComputeTruthTable( pLib, Gia_ObjFanin0(pObjPo) );
p->timeTruth += clock() - clk;
// semi-canonicize
clk = clock();
memcpy( p->pTemp1, pTruth, p->nWords * sizeof(word) );
#ifdef LMS_USE_OLD_FORM
uCanonPhase = Kit_TruthSemiCanonicize( (unsigned *)p->pTemp1, (unsigned *)p->pTemp2, nLeaves, pCanonPerm );
#else
uCanonPhase = Abc_TtCanonicize( p->pTemp1, nLeaves, pCanonPerm );
#endif
Abc_TtStretch5( (unsigned *)p->pTemp1, nLeaves, p->nVars );
p->timeCanon += clock() - clk;
// pCanonPerm and uCanonPhase show what was the variable corresponding to each var in the current truth
if ( nLeaves == 2 && Abc_TtSupportSize(pTruth, 2) != 2 )
continue;
clk = clock();
// map cut leaves into elementary variables of GIA
for ( i = 0; i < nLeaves; i++ )
Gia_ManCi( pLib, pCanonPerm[i] )->Value = Abc_Var2Lit( Gia_ObjId(pGia, Gia_ManPi(pGia, i)), (uCanonPhase >> i) & 1 );
// build internal nodes
assert( Vec_IntSize(pLib->vTtNodes) > 0 );
Gia_ManForEachObjVec( pLib->vTtNodes, pLib, pTemp, i )
{
iFanin0 = Abc_LitNotCond( Gia_ObjFanin0(pTemp)->Value, Gia_ObjFaninC0(pTemp) );
iFanin1 = Abc_LitNotCond( Gia_ObjFanin1(pTemp)->Value, Gia_ObjFaninC1(pTemp) );
pTemp->Value = Gia_ManHashAnd( pGia, iFanin0, iFanin1 );
}
p->timeBuild += clock() - clk;
// check if this node is already driving a PO
assert( Gia_ObjIsAnd(pTemp) );
pDriver = Gia_ManObj(pGia, Abc_Lit2Var(pTemp->Value));
if ( pDriver->fMark1 )
{
p->nFilterSame++;
continue;
}
pDriver->fMark1 = 1;
// create output
Gia_ManAppendCo( pGia, Abc_LitNotCond( pTemp->Value, (uCanonPhase >> nLeaves) & 1 ) );
// verify truth table
if ( fCheck )
{
clk = clock();
pTemp = Gia_ManCo(pGia, Gia_ManCoNum(pGia)-1);
pTruth = Gia_ObjComputeTruthTable( pGia, Gia_ManCo(pGia, Gia_ManCoNum(pGia)-1) );
p->timeCheck += clock() - clk;
if ( memcmp( p->pTemp1, pTruth, p->nWords * sizeof(word) ) != 0 )
{
Kit_DsdPrintFromTruth( (unsigned *)pTruth, nLeaves ); printf( "\n" );
Kit_DsdPrintFromTruth( (unsigned *)p->pTemp1, nLeaves ); printf( "\n" );
printf( "Truth table verification has failed.\n" );
// drive PO with constant
Gia_ManPatchCoDriver( pGia, Gia_ManCoNum(pGia)-1, 0 );
// save truth table ID
Vec_IntPush( p->vTruthIds, -1 );
p->nFilterTruth++;
continue;
}
}
clk = clock();
// add the resulting truth table to the hash table
Index = Vec_MemHashInsert( p->vTtMem, p->pTemp1 );
// save truth table ID
Vec_IntPush( p->vTruthIds, Index );
assert( Gia_ManCoNum(pGia) == Vec_IntSize(p->vTruthIds) );
p->nAdded++;
p->timeInsert += clock() - clk;
}
Vec_StrFree( vSupps );
p->timeTotal += clock() - clk2;
}
/**Function*************************************************************
Synopsis [Evaluates one cut during library construction.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRecAddCut3( If_Man_t * pIfMan, If_Obj_t * pRoot, If_Cut_t * pCut )
{
Lms_Man_t * p = s_pMan3;
char pCanonPerm[LMS_VAR_MAX];
unsigned uCanonPhase;
int i, Index, iFanin0, iFanin1, fHole;
int nLeaves = If_CutLeaveNum(pCut);
Vec_Ptr_t * vNodes = p->vNodes;
Gia_Man_t * pGia = p->pGia;
Gia_Obj_t * pDriver;
If_Obj_t * pIfObj = NULL;
word * pTruth;
clock_t clk;
p->nTried++;
// skip small cuts
assert( p->nVars == (int)pCut->nLimit );
if ( nLeaves < 2 || (nLeaves == 2 && Abc_TtSupportSize(If_CutTruthW(pCut), 2) != 2) )
{
p->nFilterSize++;
return 1;
}
// if ( p->vTtMem2 )
// Vec_MemHashInsert( p->vTtMem2, If_CutTruthW(pCut) );
// semi-canonicize truth table
clk = clock();
memcpy( p->pTemp1, If_CutTruthW(pCut), p->nWords * sizeof(word) );
#ifdef LMS_USE_OLD_FORM
uCanonPhase = Kit_TruthSemiCanonicize( (unsigned *)p->pTemp1, (unsigned *)p->pTemp2, nLeaves, pCanonPerm );
#else
uCanonPhase = Abc_TtCanonicize( p->pTemp1, nLeaves, pCanonPerm );
#endif
Abc_TtStretch5( (unsigned *)p->pTemp1, nLeaves, p->nVars );
p->timeCanon += clock() - clk;
// pCanonPerm and uCanonPhase show what was the variable corresponding to each var in the current truth
if ( p->pGia == NULL )
{
clk = clock();
// add the resulting truth table to the hash table
Index = Vec_MemHashInsert( p->vTtMem, p->pTemp1 );
/*
if ( p->vTruthFreqs == NULL )
p->vTruthFreqs = Vec_IntAlloc( 1000 );
assert( Index <= Vec_IntSize(p->vTruthFreqs) );
if ( Index < Vec_IntSize(p->vTruthFreqs) )
Vec_IntAddToEntry( p->vTruthFreqs, Index, 1 );
else
Vec_IntPush( p->vTruthFreqs, 1 );
*/
p->nAdded++;
p->timeInsert += clock() - clk;
return 1;
}
// collect internal nodes and skip redundant cuts
clk = clock();
If_CutTraverse( pIfMan, pRoot, pCut, vNodes );
p->timeTruth += clock() - clk;
if ( Vec_PtrSize(vNodes) > 253 )
{
p->nFilterSize++;
return 1;
}
clk = clock();
// map cut leaves into elementary variables of GIA
for ( i = 0; i < nLeaves; i++ )
If_ManObj( pIfMan, pCut->pLeaves[(int)pCanonPerm[i]] )->iCopy = Abc_Var2Lit( Gia_ObjId(pGia, Gia_ManPi(pGia, i)), (uCanonPhase >> i) & 1 );
// build internal nodes
fHole = 0;
assert( Vec_PtrSize(vNodes) > 0 );
Vec_PtrForEachEntryStart( If_Obj_t *, vNodes, pIfObj, i, nLeaves )
{
if ( If_ObjIsCi(pIfObj) )
{
pIfObj->iCopy = 0;
fHole = 1;
continue;
}
iFanin0 = Abc_LitNotCond( If_ObjFanin0(pIfObj)->iCopy, If_ObjFaninC0(pIfObj) );
iFanin1 = Abc_LitNotCond( If_ObjFanin1(pIfObj)->iCopy, If_ObjFaninC1(pIfObj) );
pIfObj->iCopy = Gia_ManHashAnd( pGia, iFanin0, iFanin1 );
}
p->nHoleInTheWall += fHole;
p->timeBuild += clock() - clk;
// check if this node is already driving a PO
assert( If_ObjIsAnd(pIfObj) );
pDriver = Gia_ManObj(pGia, Abc_Lit2Var(pIfObj->iCopy));
if ( pDriver->fMark1 )
{
p->nFilterSame++;
return 1;
}
pDriver->fMark1 = 1;
// create output
Gia_ManAppendCo( pGia, Abc_LitNotCond( pIfObj->iCopy, (uCanonPhase >> nLeaves) & 1 ) );
// verify truth table
clk = clock();
pTruth = Gia_ObjComputeTruthTable( pGia, Gia_ManCo(pGia, Gia_ManCoNum(pGia)-1) );
p->timeCheck += clock() - clk;
if ( memcmp( p->pTemp1, pTruth, p->nWords * sizeof(word) ) != 0 )
{
/*
Kit_DsdPrintFromTruth( pTruth, nLeaves ); printf( "\n" );
Kit_DsdPrintFromTruth( (unsigned *)p->pTemp1, nLeaves ); printf( "\n" );
printf( "Truth table verification has failed.\n" );
*/
// drive PO with constant
Gia_ManPatchCoDriver( pGia, Gia_ManCoNum(pGia)-1, 0 );
// save truth table ID
Vec_IntPush( p->vTruthIds, -1 );
p->nFilterTruth++;
return 1;
}
clk = clock();
// add the resulting truth table to the hash table
Index = Vec_MemHashInsert( p->vTtMem, p->pTemp1 );
// save truth table ID
Vec_IntPush( p->vTruthIds, Index );
assert( Gia_ManCoNum(pGia) == Vec_IntSize(p->vTruthIds) );
p->nAdded++;
p->timeInsert += clock() - clk;
return 1;
}
/**Function*************************************************************
Synopsis [Top level procedure for library construction.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkRecAdd3( Abc_Ntk_t * pNtk, int fUseSOPB )
{
extern Abc_Ntk_t * Abc_NtkIf( Abc_Ntk_t * pNtk, If_Par_t * pPars );
If_Par_t Pars, * pPars = &Pars;
Abc_Ntk_t * pNtkNew;
int clk = clock();
if ( Abc_NtkGetChoiceNum( pNtk ) )
printf( "Performing recoding structures with choices.\n" );
// remember that the manager was used for library construction
s_pMan3->fLibConstr = 1;
// create hash table if not available
if ( s_pMan3->pGia && s_pMan3->pGia->pHTable == NULL )
Gia_ManHashStart( s_pMan3->pGia );
// set defaults
memset( pPars, 0, sizeof(If_Par_t) );
// user-controlable paramters
pPars->nLutSize = s_pMan3->nVars;
pPars->nCutsMax = s_pMan3->nCuts;
pPars->DelayTarget = -1;
pPars->Epsilon = (float)0.005;
pPars->fArea = 1;
// internal parameters
if ( fUseSOPB )
{
pPars->fTruth = 1;
pPars->fCutMin = 0;
pPars->fUsePerm = 1;
pPars->fDelayOpt = 1;
}
else
{
pPars->fTruth = 1;
pPars->fCutMin = 1;
pPars->fUsePerm = 0;
pPars->fDelayOpt = 0;
}
pPars->fSkipCutFilter = 0;
pPars->pFuncCost = NULL;
pPars->pFuncUser = Abc_NtkRecAddCut3;
// perform recording
pNtkNew = Abc_NtkIf( pNtk, pPars );
Abc_NtkDelete( pNtkNew );
s_pMan3->timeTotal += clock() - clk;
}
/**Function*************************************************************
Synopsis [Returns min AIG level at the output fo the cut using the library.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int If_CutComputeDelay( If_Man_t * p, If_Cut_t * pCut, char * pCanonPerm, word DelayProfile )
{
If_Obj_t* pLeaf;
int nLeaves = If_CutLeaveNum(pCut);
int i, delayTemp, delayMax = -ABC_INFINITY;
for ( i = 0; i < nLeaves; i++ )
{
pLeaf = If_ManObj(p, (pCut)->pLeaves[(int)pCanonPerm[i]]);
delayTemp = If_ObjCutBest(pLeaf)->Delay + Lms_DelayGet(DelayProfile, i);
delayMax = Abc_MaxInt( delayMax, delayTemp );
}
return delayMax;
}
static inline int If_CutFindBestStruct( If_Man_t * pIfMan, If_Cut_t * pCut, char * pCanonPerm, unsigned * puCanonPhase, int * pBestPo )
{
Lms_Man_t * p = s_pMan3;
int i, * pTruthId, iFirstPo, iFirstPoNext, iBestPo;
int BestDelay = ABC_INFINITY, BestArea = ABC_INFINITY, Delay, Area;
int uSupport, nLeaves = If_CutLeaveNum( pCut );
word DelayProfile;
clock_t clk;
assert( nLeaves > 1 );
pCut->fUser = 1;
// compute support
uSupport = Abc_TtSupport( If_CutTruthW(pCut), nLeaves );
if ( uSupport == 0 )
{
pCut->Cost = 1;
for ( i = 0; i < nLeaves; i++ )
pCut->pPerm[i] = IF_BIG_CHAR;
return 0;
}
if ( !Abc_TtSuppIsMinBase(uSupport) || uSupport == 1 )
{
assert( Abc_TtSuppOnlyOne(uSupport) );
pCut->Cost = 1;
for ( i = 0; i < nLeaves; i++ )
pCut->pPerm[i] = IF_BIG_CHAR;
pCut->pPerm[Abc_TtSuppFindFirst(uSupport)] = 0;
return If_ObjCutBest(If_ManObj(pIfMan, pCut->pLeaves[Abc_TtSuppFindFirst(uSupport)]))->Delay;
}
assert( Gia_WordCountOnes(uSupport) == nLeaves );
// semicanonicize the function
clk = clock();
memcpy( p->pTemp1, If_CutTruthW(pCut), p->nWords * sizeof(word) );
#ifdef LMS_USE_OLD_FORM
*puCanonPhase = Kit_TruthSemiCanonicize( (unsigned *)p->pTemp1, (unsigned *)p->pTemp2, nLeaves, pCanonPerm );
#else
*puCanonPhase = Abc_TtCanonicize( p->pTemp1, nLeaves, pCanonPerm );
#endif
Abc_TtStretch5( (unsigned *)p->pTemp1, nLeaves, p->nVars );
p->timeCanon += clock() - clk;
// get TT ID for the given class
pTruthId = Vec_MemHashLookup( p->vTtMem, p->pTemp1 );
if ( *pTruthId == -1 )
{
pCut->Cost = IF_COST_MAX;
pCut->fUseless = 1;
return ABC_INFINITY;
}
// note that array p->vTruthPo contains the first PO for the given truth table
// other POs belonging to the same equivalence class follow immediately after this one
// to iterate through the POs, we need to perform the following steps
// find the first PO of this class
iFirstPo = Vec_IntEntry( p->vTruthPo, *pTruthId );
// find the first PO of the next class
iFirstPoNext = Vec_IntEntry( p->vTruthPo, *pTruthId+1 );
// iterate through the subgraphs of this class
iBestPo = -1;
for ( i = iFirstPo; i < iFirstPoNext; i++ )
{
Delay = If_CutComputeDelay( pIfMan, pCut, pCanonPerm, Vec_WrdEntry(p->vDelays, i) );
Area = Vec_StrEntry(p->vAreas, i);
if ( iBestPo == -1 || BestDelay > Delay || (BestDelay == Delay && BestArea > Area) )
{
iBestPo = i;
BestDelay = Delay;
BestArea = Area;
}
}
if ( pBestPo )
*pBestPo = iBestPo;
// mark as user cut.
DelayProfile = Vec_WrdEntry(p->vDelays, iBestPo);
pCut->Cost = Vec_StrEntry(p->vAreas, iBestPo);
for ( i = 0; i < nLeaves; i++ )
pCut->pPerm[(int)pCanonPerm[i]] = Lms_DelayGet(DelayProfile, i);
return BestDelay;
}
int If_CutDelayRecCost3( If_Man_t * pIfMan, If_Cut_t * pCut, If_Obj_t * pObj )
{
Lms_Man_t * p = s_pMan3;
char pCanonPerm[LMS_VAR_MAX];
unsigned uCanonPhase;
// make sure the cut functions match the library
assert( p->nVars == (int)pCut->nLimit );
// if this assertion fires, it means that LMS manager was used for library construction
// in this case, GIA has to be written out and the manager restarted as described above
assert( !p->fLibConstr );
if ( p->vTruthPo == NULL )
Lms_ManPrepare( p );
// return the delay of the best structure
return If_CutFindBestStruct( pIfMan, pCut, pCanonPerm, &uCanonPhase, NULL );
}
/**Function*************************************************************
Synopsis [Reexpresses the best structure of the cut in the HOP manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Hop_Obj_t * Abc_RecToHop3( Hop_Man_t * pMan, If_Man_t * pIfMan, If_Cut_t * pCut, If_Obj_t * pIfObj )
{
Lms_Man_t * p = s_pMan3;
char pCanonPerm[LMS_VAR_MAX];
unsigned uCanonPhase;
Hop_Obj_t * pFan0, * pFan1, * pHopObj;
Gia_Man_t * pGia = p->pGia;
Gia_Obj_t * pGiaPo, * pGiaTemp = NULL;
int i, uSupport, BestPo = -1, nLeaves = If_CutLeaveNum(pCut);
assert( pIfMan->pPars->fCutMin == 1 );
assert( nLeaves > 1 );
// compute support
uSupport = Abc_TtSupport( If_CutTruthW(pCut), nLeaves );
if ( uSupport == 0 )
return Hop_NotCond( Hop_ManConst0(pMan), (int)(*If_CutTruthW(pCut) & 1) );
if ( !Abc_TtSuppIsMinBase(uSupport) || uSupport == 1 )
{
assert( Abc_TtSuppOnlyOne(uSupport) );
return Hop_NotCond( Hop_IthVar(pMan, Abc_TtSuppFindFirst(uSupport)), (int)(*If_CutTruthW(pCut) & 1) );
}
assert( Gia_WordCountOnes(uSupport) == nLeaves );
// get the best output for this node
If_CutFindBestStruct( pIfMan, pCut, pCanonPerm, &uCanonPhase, &BestPo );
assert( BestPo >= 0 );
pGiaPo = Gia_ManCo( pGia, BestPo );
// collect internal nodes into pGia->vTtNodes
if ( pGia->vTtNodes == NULL )
pGia->vTtNodes = Vec_IntAlloc( 256 );
assert( Gia_ObjIsAnd( Gia_ObjFanin0(pGiaPo) ) );
Gia_ObjCollectInternal( pGia, Gia_ObjFanin0(pGiaPo) );
assert( Vec_IntSize(pGia->vTtNodes) > 0 );
// collect HOP nodes for leaves
Vec_PtrClear( p->vLabelsP );
for ( i = 0; i < nLeaves; i++ )
Vec_PtrPush( p->vLabelsP, Hop_NotCond(Hop_IthVar(pMan, pCanonPerm[i]), (uCanonPhase >> i) & 1) );
// compute HOP nodes for internal nodes
Gia_ManForEachObjVec( pGia->vTtNodes, pGia, pGiaTemp, i )
{
pGiaTemp->fMark0 = 0; // unmark node marked by Gia_ObjCollectInternal()
if ( Gia_ObjIsAnd(Gia_ObjFanin0(pGiaTemp)) )
pFan0 = (Hop_Obj_t *)Vec_PtrEntry(p->vLabelsP, Gia_ObjNum(pGia, Gia_ObjFanin0(pGiaTemp)) + nLeaves);
else
pFan0 = (Hop_Obj_t *)Vec_PtrEntry(p->vLabelsP, Gia_ObjCioId(Gia_ObjFanin0(pGiaTemp)));
pFan0 = Hop_NotCond(pFan0, Gia_ObjFaninC0(pGiaTemp));
if ( Gia_ObjIsAnd(Gia_ObjFanin1(pGiaTemp)) )
pFan1 = (Hop_Obj_t *)Vec_PtrEntry(p->vLabelsP, Gia_ObjNum(pGia, Gia_ObjFanin1(pGiaTemp)) + nLeaves);
else
pFan1 = (Hop_Obj_t *)Vec_PtrEntry(p->vLabelsP, Gia_ObjCioId(Gia_ObjFanin1(pGiaTemp)));
pFan1 = Hop_NotCond(pFan1, Gia_ObjFaninC1(pGiaTemp));
pHopObj = Hop_And(pMan, pFan0, pFan1);
Vec_PtrPush(p->vLabelsP, pHopObj);
}
// get the final result
assert( Gia_ObjIsAnd(pGiaTemp) );
pHopObj = (Hop_Obj_t *)Vec_PtrEntry(p->vLabelsP, Gia_ObjNum(pGia, pGiaTemp) + nLeaves);
// complement the result if needed
return Hop_NotCond( pHopObj, Gia_ObjFaninC0(pGiaPo) ^ ((uCanonPhase >> nLeaves) & 1) );
}
/**Function*************************************************************
Synopsis [Reexpresses the best structure of the cut in the GIA manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_RecToGia3( Gia_Man_t * pMan, If_Man_t * pIfMan, If_Cut_t * pCut, Vec_Int_t * vLeaves, int fHash )
{
Lms_Man_t * p = s_pMan3;
char pCanonPerm[LMS_VAR_MAX];
unsigned uCanonPhase;
int iFan0, iFan1, iGiaObj;
Gia_Man_t * pGia = p->pGia;
Gia_Obj_t * pGiaPo, * pGiaTemp = NULL;
int i, uSupport, BestPo = -1, nLeaves = If_CutLeaveNum(pCut);
assert( pIfMan->pPars->fCutMin == 1 );
assert( nLeaves > 1 );
assert( nLeaves == Vec_IntSize(vLeaves) );
// compute support
uSupport = Abc_TtSupport( If_CutTruthW(pCut), nLeaves );
if ( uSupport == 0 )
return Abc_LitNotCond( 0, (int)(*If_CutTruthW(pCut) & 1) );
if ( !Abc_TtSuppIsMinBase(uSupport) || uSupport == 1 )
{
assert( Abc_TtSuppOnlyOne(uSupport) );
return Abc_LitNotCond( Vec_IntEntry(vLeaves, Abc_TtSuppFindFirst(uSupport)), (int)(*If_CutTruthW(pCut) & 1) );
}
assert( Gia_WordCountOnes(uSupport) == nLeaves );
// get the best output for this node
If_CutFindBestStruct( pIfMan, pCut, pCanonPerm, &uCanonPhase, &BestPo );
assert( BestPo >= 0 );
pGiaPo = Gia_ManCo( pGia, BestPo );
// collect internal nodes into pGia->vTtNodes
if ( pGia->vTtNodes == NULL )
pGia->vTtNodes = Vec_IntAlloc( 256 );
assert( Gia_ObjIsAnd( Gia_ObjFanin0(pGiaPo) ) );
Gia_ObjCollectInternal( pGia, Gia_ObjFanin0(pGiaPo) );
assert( Vec_IntSize(pGia->vTtNodes) > 0 );
// collect GIA nodes for leaves
Vec_IntClear( p->vLabels );
for (i = 0; i < nLeaves; i++)
Vec_IntPush( p->vLabels, Abc_LitNotCond(Vec_IntEntry(vLeaves, pCanonPerm[i]), (uCanonPhase >> i) & 1) );
// compute HOP nodes for internal nodes
Gia_ManForEachObjVec( pGia->vTtNodes, pGia, pGiaTemp, i )
{
pGiaTemp->fMark0 = 0; // unmark node marked by Gia_ObjCollectInternal()
if ( Gia_ObjIsAnd(Gia_ObjFanin0(pGiaTemp)) )
iFan0 = Vec_IntEntry(p->vLabels, Gia_ObjNum(pGia, Gia_ObjFanin0(pGiaTemp)) + nLeaves);
else
iFan0 = Vec_IntEntry(p->vLabels, Gia_ObjCioId(Gia_ObjFanin0(pGiaTemp)));
iFan0 = Abc_LitNotCond(iFan0, Gia_ObjFaninC0(pGiaTemp));
if ( Gia_ObjIsAnd(Gia_ObjFanin1(pGiaTemp)) )
iFan1 = Vec_IntEntry(p->vLabels, Gia_ObjNum(pGia, Gia_ObjFanin1(pGiaTemp)) + nLeaves);
else
iFan1 = Vec_IntEntry(p->vLabels, Gia_ObjCioId(Gia_ObjFanin1(pGiaTemp)));
iFan1 = Abc_LitNotCond(iFan1, Gia_ObjFaninC1(pGiaTemp));
if ( fHash )
iGiaObj = Gia_ManHashAnd(pMan, iFan0, iFan1);
else
iGiaObj = Gia_ManAppendAnd(pMan, iFan0, iFan1);
Vec_IntPush(p->vLabels, iGiaObj);
}
// get the final result
assert( Gia_ObjIsAnd(pGiaTemp) );
iGiaObj = Vec_IntEntry(p->vLabels, Gia_ObjNum(pGia, pGiaTemp) + nLeaves);
// complement the result if needed
return Abc_LitNotCond( iGiaObj, Gia_ObjFaninC0(pGiaPo) ^ ((uCanonPhase >> nLeaves) & 1) );
}
/**Function*************************************************************
Synopsis [Reduces GIA to contain only useful COs and internal nodes.]
Description [During library construction, redundant nodes are added.
Some COs are found to be useless because their TT does not match the
(semi-canonicized TT) of the cut, etc. This procedure reduces GIA
to contains only useful (non-redundant, non-dominated) COs and the
corresponding internal nodes. This procedure replaces GIA by a new GIA
and creates new vTruthIds. The COs with the same truth table have
adjacent IDs. This procedure does not change the truth tables.]
SideEffects []
SeeAlso []
***********************************************************************/
// count how many times TT occurs
Vec_Int_t * Lms_GiaCountTruths( Lms_Man_t * p )
{
Vec_Int_t * vCounts = Vec_IntStart( Vec_MemEntryNum(p->vTtMem) );
int i, Entry;
Vec_IntForEachEntry( p->vTruthIds, Entry, i )
if ( Entry >= 0 )
Vec_IntAddToEntry( vCounts, Entry, 1 );
return vCounts;
}
// collect PO indexes worth visiting
Vec_Int_t * Lms_GiaCollectUsefulCos( Lms_Man_t * p )
{
Vec_Int_t * vBegins = Vec_IntAlloc( Vec_MemEntryNum(p->vTtMem) );
Vec_Int_t * vUseful = Vec_IntStartFull( Gia_ManCoNum(p->pGia) + Vec_MemEntryNum(p->vTtMem) );
Vec_Int_t * vCounts = Lms_GiaCountTruths( p );
int i, Entry, * pPlace, SumTotal = 0;
// mark up the place for POs
Vec_IntForEachEntry( vCounts, Entry, i )
{
assert( Entry > 0 );
Vec_IntPush( vBegins, SumTotal );
SumTotal += Entry + 1;
// printf( "%d ", Entry );
}
Vec_IntPush( vBegins, SumTotal );
// fill out POs in their places
Vec_IntFill( vCounts, Vec_IntSize(vCounts), 0 );
Vec_IntForEachEntry( p->vTruthIds, Entry, i )
{
if ( Entry < 0 )
continue;
pPlace = Vec_IntEntryP( vUseful, Vec_IntEntry(vBegins, Entry) + Vec_IntEntry(vCounts, Entry) );
assert( *pPlace == -1 );
*pPlace = i;
Vec_IntAddToEntry( vCounts, Entry, 1 );
}
Vec_IntFree( vBegins );
Vec_IntFree( vCounts );
return vUseful;
}
// collect non-dominated COs
Vec_Int_t * Lms_GiaFindNonRedundantCos( Lms_Man_t * p )
{
Vec_Int_t * vRemain;
Vec_Int_t * vUseful;
Vec_Wrd_t * vDelays;
int i, k, EntryI, EntryK;
word D1, D2;
vDelays = Lms_GiaDelays( p->pGia );
vUseful = Lms_GiaCollectUsefulCos( p );
Vec_IntForEachEntry( vUseful, EntryI, i )
{
if ( EntryI < 0 )
continue;
D1 = Vec_WrdEntry(vDelays, EntryI);
assert( D1 > 0 );
Vec_IntForEachEntryStart( vUseful, EntryK, k, i+1 )
{
if ( EntryK == -1 )
break;
if ( EntryK == -2 )
continue;
D2 = Vec_WrdEntry(vDelays, EntryK);
assert( D2 > 0 );
if ( Lms_DelayDom(D1, D2, Gia_ManCiNum(p->pGia)) ) // D1 dominate D2
{
Vec_IntWriteEntry( vUseful, k, -2 );
continue;
}
if ( Lms_DelayDom(D2, D1, Gia_ManCiNum(p->pGia)) ) // D2 dominate D1
{
Vec_IntWriteEntry( vUseful, i, -2 );
break;
}
}
}
vRemain = Vec_IntAlloc( 1000 );
Vec_IntForEachEntry( vUseful, EntryI, i )
if ( EntryI >= 0 )
Vec_IntPush( vRemain, EntryI );
Vec_IntFree( vUseful );
Vec_WrdFree( vDelays );
return vRemain;
}
// replace GIA and vTruthIds by filtered ones
void Lms_GiaNormalize( Lms_Man_t * p )
{
Gia_Man_t * pGiaNew;
Gia_Obj_t * pObj;
Vec_Int_t * vRemain;
Vec_Int_t * vTruthIdsNew;
int i, Entry, Prev = -1, Next;
// collect non-redundant COs
vRemain = Lms_GiaFindNonRedundantCos( p );
// change these to be useful literals
vTruthIdsNew = Vec_IntAlloc( Vec_IntSize(vRemain) );
Vec_IntForEachEntry( vRemain, Entry, i )
{
pObj = Gia_ManCo(p->pGia, Entry);
assert( Gia_ObjIsAnd(Gia_ObjFanin0(pObj)) );
Vec_IntWriteEntry( vRemain, i, Gia_ObjFaninLit0p(p->pGia, pObj) );
// create new truth IDs
Next = Vec_IntEntry(p->vTruthIds, Gia_ObjCioId(pObj));
assert( Prev <= Next );
Vec_IntPush( vTruthIdsNew, Next );
Prev = Next;
}
// create a new GIA
Gia_ManForEachObj( p->pGia, pObj, i )
assert( pObj->fMark0 == 0 );
for ( i = 0; i < Gia_ManCoNum(p->pGia); i++ )
Gia_ManPatchCoDriver( p->pGia, i, 0 );
Vec_IntForEachEntry( vRemain, Entry, i )
Gia_ManAppendCo( p->pGia, Entry );
// pGiaNew = Gia_ManCleanup( p->pGia );
pGiaNew = Gia_ManCleanupOutputs( p->pGia, Gia_ManCoNum(p->pGia) - Vec_IntSize(vRemain) );
Gia_ManStop( p->pGia );
p->pGia = pGiaNew;
Vec_IntFree( vRemain );
// update truth IDs
Vec_IntFree( p->vTruthIds );
p->vTruthIds = vTruthIdsNew;
// Vec_IntPrint( vTruthIdsNew );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRecTruthCompare( int * p1, int * p2 )
{
int Diff = Vec_StrEntry( s_pMan3->vSupps, *p1 ) - Vec_StrEntry( s_pMan3->vSupps, *p2 );
if ( Diff )
return Diff;
return memcmp( Vec_MemReadEntry(s_pMan3->vTtMem, *p1), Vec_MemReadEntry(s_pMan3->vTtMem, *p2), sizeof(word) * s_pMan3->nWords );
}
void Abc_NtkRecDumpTt3( char * pFileName, int fBinary )
{
FILE * pFile;
char pBuffer[1000];
Lms_Man_t * p = s_pMan3;
Vec_Int_t * vEntries;
word * pTruth;
int i, Entry, nVars = p->nVars;
int nEntries = Vec_MemEntryNum(p->vTtMem);
if ( nEntries == 0 )
{
printf( "There is not truth tables.\n" );
return;
}
pFile = fopen( pFileName, "wb" );
if ( pFile == NULL )
{
printf( "The file cannot be opened.\n" );
return;
}
p->vSupps = Vec_StrAlloc( nEntries );
Vec_MemForEachEntry( p->vTtMem, pTruth, i )
Vec_StrPush( p->vSupps, (char)Abc_TtSupportSize(pTruth, nVars) );
vEntries = Vec_IntStartNatural( nEntries );
qsort( (void *)Vec_IntArray(vEntries), nEntries, sizeof(int), (int(*)(const void *,const void *))Abc_NtkRecTruthCompare );
Vec_StrFreeP( &p->vSupps );
// write the file
Vec_IntForEachEntry( vEntries, Entry, i )
{
pTruth = Vec_MemReadEntry(p->vTtMem, Entry);
if ( fBinary )
{
fwrite( pTruth, 1, sizeof(word) * p->nWords, pFile );
continue;
}
Extra_PrintHex( pFile, (unsigned *)pTruth, nVars );
fprintf( pFile, " " );
// Kit_DsdWriteFromTruth( pBuffer, (unsigned *)pTruth, nVars );
Dau_DsdDecompose( pTruth, p->nVars, 0, (int)(nVars <= 10), pBuffer );
fprintf( pFile, "%s\n", pBuffer );
}
fclose( pFile );
Vec_IntFree( vEntries );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRecInputNum3()
{
return Gia_ManCiNum(s_pMan3->pGia);
}
int Abc_NtkRecIsRunning3()
{
return s_pMan3 != NULL;
}
Gia_Man_t * Abc_NtkRecGetGia3()
{
clock_t clk = clock();
printf( "Before normalizing: Library has %d classes and %d AIG subgraphs with %d AND nodes.\n",
Vec_MemEntryNum(s_pMan3->vTtMem), Gia_ManPoNum(s_pMan3->pGia), Gia_ManAndNum(s_pMan3->pGia) );
Lms_GiaNormalize( s_pMan3 );
printf( "After normalizing: Library has %d classes and %d AIG subgraphs with %d AND nodes.\n",
Vec_MemEntryNum(s_pMan3->vTtMem), Gia_ManPoNum(s_pMan3->pGia), Gia_ManAndNum(s_pMan3->pGia) );
Abc_PrintTime( 1, "Normalization runtime", clock() - clk );
s_pMan3->fLibConstr = 0;
return s_pMan3->pGia;
}
void Abc_NtkRecPs3(int fPrintLib)
{
Lms_ManPrint( s_pMan3 );
}
void Abc_NtkRecStart3( Gia_Man_t * p, int nVars, int nCuts, int fFuncOnly, int fVerbose )
{
assert( s_pMan3 == NULL );
s_pMan3 = Lms_ManStart( p, nVars, nCuts, fFuncOnly, fVerbose );
}
void Abc_NtkRecStop3()
{
assert( s_pMan3 != NULL );
Lms_ManStop( s_pMan3 );
s_pMan3 = NULL;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END