sfmLib.c 26.7 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
/**CFile****************************************************************

  FileName    [sfmLib.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [SAT-based optimization using internal don't-cares.]

  Synopsis    [Preprocessing genlib library.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: sfmLib.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

***********************************************************************/

#include "sfmInt.h"
#include "misc/st/st.h"
#include "map/mio/mio.h"
24 25 26 27 28
#include "misc/vec/vecMem.h"
#include "misc/util/utilTruth.h"
#include "misc/extra/extra.h"
#include "map/mio/exp.h"
#include "opt/dau/dau.h"
29
#include "base/main/main.h"
30 31 32 33 34 35 36 37

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

38 39 40 41
struct Sfm_Fun_t_
{
    int             Next;          // next function in the list
    int             Area;          // area of this function
42 43
    char            pFansT[SFM_SUPP_MAX+1];     // top gate ID, followed by fanin perm
    char            pFansB[SFM_SUPP_MAX+1];     // bottom gate ID, followed by fanin perm
44 45 46
};
struct Sfm_Lib_t_
{
47
    int             nVars;         // variable count
48
    int             nWords;        // truth table words
49
    int             fVerbose;      // verbose statistics
50 51
    Mio_Cell2_t *   pCells;        // library gates
    int             nCells;        // library gate count
52
    int             fDelay;        // uses delay profile
53 54 55 56 57 58
    int             nObjs;         // object count
    int             nObjsAlloc;    // object count
    Sfm_Fun_t *     pObjs;         // objects  
    Vec_Mem_t *     vTtMem;        // truth tables
    Vec_Int_t       vLists;        // lists of funcs for each truth table
    Vec_Int_t       vCounts;       // counters of functions for each truth table
59
    Vec_Int_t       vHits;         // the number of times this function was used
60 61 62 63 64
    Vec_Int_t       vProfs;        // area/delay profiles
    Vec_Int_t       vStore;        // storage for area/delay profiles
    Vec_Int_t       vTemp;         // temporary storage for candidates
    int             nObjSkipped;
    int             nObjRemoved;
65 66
};

67 68
static inline Sfm_Fun_t * Sfm_LibFun( Sfm_Lib_t * p, int i )              { return i == -1 ? NULL : p->pObjs + i; }
static inline int         Sfm_LibFunId( Sfm_Lib_t * p, Sfm_Fun_t * pFun ) { return pFun - p->pObjs;               }
69 70 71 72 73

#define Sfm_LibForEachSuper( p, pObj, Func ) \
    for ( pObj = Sfm_LibFun(p, Vec_IntEntry(&p->vLists, Func)); pObj; pObj = Sfm_LibFun(p, pObj->Next) )


Alan Mishchenko committed
74 75 76 77 78 79 80 81 82 83 84
static word s_Truth8[8][4] = {
    { ABC_CONST(0xAAAAAAAAAAAAAAAA),ABC_CONST(0xAAAAAAAAAAAAAAAA),ABC_CONST(0xAAAAAAAAAAAAAAAA),ABC_CONST(0xAAAAAAAAAAAAAAAA) },
    { ABC_CONST(0xCCCCCCCCCCCCCCCC),ABC_CONST(0xCCCCCCCCCCCCCCCC),ABC_CONST(0xCCCCCCCCCCCCCCCC),ABC_CONST(0xCCCCCCCCCCCCCCCC) },
    { ABC_CONST(0xF0F0F0F0F0F0F0F0),ABC_CONST(0xF0F0F0F0F0F0F0F0),ABC_CONST(0xF0F0F0F0F0F0F0F0),ABC_CONST(0xF0F0F0F0F0F0F0F0) },
    { ABC_CONST(0xFF00FF00FF00FF00),ABC_CONST(0xFF00FF00FF00FF00),ABC_CONST(0xFF00FF00FF00FF00),ABC_CONST(0xFF00FF00FF00FF00) },
    { ABC_CONST(0xFFFF0000FFFF0000),ABC_CONST(0xFFFF0000FFFF0000),ABC_CONST(0xFFFF0000FFFF0000),ABC_CONST(0xFFFF0000FFFF0000) },
    { ABC_CONST(0xFFFFFFFF00000000),ABC_CONST(0xFFFFFFFF00000000),ABC_CONST(0xFFFFFFFF00000000),ABC_CONST(0xFFFFFFFF00000000) },
    { ABC_CONST(0x0000000000000000),ABC_CONST(0xFFFFFFFFFFFFFFFF),ABC_CONST(0x0000000000000000),ABC_CONST(0xFFFFFFFFFFFFFFFF) },
    { ABC_CONST(0x0000000000000000),ABC_CONST(0x0000000000000000),ABC_CONST(0xFFFFFFFFFFFFFFFF),ABC_CONST(0xFFFFFFFFFFFFFFFF) }
};

85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sfm_DecCreateCnf( Vec_Int_t * vGateSizes, Vec_Wrd_t * vGateFuncs, Vec_Wec_t * vGateCnfs )
{
    Vec_Str_t * vCnf, * vCnfBase;
    Vec_Int_t * vCover;
    word uTruth;
    int i, nCubes;
    vCnf = Vec_StrAlloc( 100 );
    vCover = Vec_IntAlloc( 100 );
    Vec_WrdForEachEntry( vGateFuncs, uTruth, i )
    {
        nCubes = Sfm_TruthToCnf( uTruth, Vec_IntEntry(vGateSizes, i), vCover, vCnf );
        vCnfBase = (Vec_Str_t *)Vec_WecEntry( vGateCnfs, i );
        Vec_StrGrow( vCnfBase, Vec_StrSize(vCnf) );
        memcpy( Vec_StrArray(vCnfBase), Vec_StrArray(vCnf), Vec_StrSize(vCnf) );
        vCnfBase->nSize = Vec_StrSize(vCnf);
    }
    Vec_IntFree( vCover );
    Vec_StrFree( vCnf );
}

/**Function*************************************************************

  Synopsis    [Preprocess the library.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sfm_LibPreprocess( Mio_Library_t * pLib, Vec_Int_t * vGateSizes, Vec_Wrd_t * vGateFuncs, Vec_Wec_t * vGateCnfs, Vec_Ptr_t * vGateHands )
{
    Mio_Gate_t * pGate;
    int nGates = Mio_LibraryReadGateNum(pLib);
    Vec_IntGrow( vGateSizes, nGates );
    Vec_WrdGrow( vGateFuncs, nGates );
    Vec_WecInit( vGateCnfs,  nGates );
    Vec_PtrGrow( vGateHands, nGates );
    Mio_LibraryForEachGate( pLib, pGate )
    {
        Vec_IntPush( vGateSizes, Mio_GateReadPinNum(pGate) );
        Vec_WrdPush( vGateFuncs, Mio_GateReadTruth(pGate) );
        Mio_GateSetValue( pGate, Vec_PtrSize(vGateHands) );
        Vec_PtrPush( vGateHands, pGate );
    }
    Sfm_DecCreateCnf( vGateSizes, vGateFuncs, vGateCnfs );
}

149

150 151 152 153 154 155 156 157 158 159 160 161 162
/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sfm_LibFindComplInputGate( Vec_Wrd_t * vFuncs, int iGate, int nFanins, int iFanin, int * piFaninNew )
{
163 164 165
    word uTruthGate = Vec_WrdEntry( vFuncs, iGate );
    word uTruthFlip = Abc_Tt6Flip( uTruthGate, iFanin ); 
    word uTruth, uTruthSwap;  int i;
166 167 168
    assert( iFanin >= 0 && iFanin < nFanins );
    if ( piFaninNew ) *piFaninNew = iFanin;
    Vec_WrdForEachEntry( vFuncs, uTruth, i )
169
        if ( uTruth == uTruthFlip )
170
            return i;
171
    if ( iFanin-1 >= 0 )
172 173
    {
        if ( piFaninNew ) *piFaninNew = iFanin-1;
174
        uTruthSwap = Abc_Tt6SwapAdjacent( uTruthFlip, iFanin-1 );
175
        Vec_WrdForEachEntry( vFuncs, uTruth, i )
176
            if ( uTruth == uTruthSwap )
177 178
                return i;
    }
179
    if ( iFanin+1 < nFanins )
180 181
    {
        if ( piFaninNew ) *piFaninNew = iFanin+1;
182
        uTruthSwap = Abc_Tt6SwapAdjacent( uTruthFlip, iFanin );
183
        Vec_WrdForEachEntry( vFuncs, uTruth, i )
184
            if ( uTruth == uTruthSwap )
185 186
                return i;
    }
187
    // add checking for complemeting control input of a MUX
188 189 190 191
    if ( piFaninNew ) *piFaninNew = -1;
    return -1;
}

192 193 194 195 196 197 198 199 200 201 202 203

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
204
Sfm_Lib_t * Sfm_LibStart( int nVars, int fDelay, int fVerbose )
205 206
{
    Sfm_Lib_t * p = ABC_CALLOC( Sfm_Lib_t, 1 );
207
    assert( nVars <= SFM_SUPP_MAX );
208 209 210
    p->vTtMem = Vec_MemAllocForTT( nVars, 0 );   
    Vec_IntGrow( &p->vLists,  (1 << 16) );
    Vec_IntGrow( &p->vCounts, (1 << 16) );
211
    Vec_IntGrow( &p->vHits,   (1 << 16) );
212 213
    Vec_IntFill( &p->vLists,  2, -1 );
    Vec_IntFill( &p->vCounts, 2, -1 );
214
    Vec_IntFill( &p->vHits,   2, -1 );
215 216
    p->nObjsAlloc = (1 << 16);
    p->pObjs = ABC_CALLOC( Sfm_Fun_t, p->nObjsAlloc );
217 218 219 220
    p->fDelay = fDelay;
    if ( fDelay ) Vec_IntGrow( &p->vProfs,  (1 << 16) );
    if ( fDelay ) Vec_IntGrow( &p->vStore,  (1 << 18) );
    Vec_IntGrow( &p->vTemp, 16 );
221
    p->nVars = nVars;
222
    p->nWords = Abc_TtWordNum( nVars );
223
    p->fVerbose = fVerbose;
224 225 226 227 228 229 230 231
    return p;
}
void Sfm_LibStop( Sfm_Lib_t * p )
{
    Vec_MemHashFree( p->vTtMem );
    Vec_MemFree( p->vTtMem );
    Vec_IntErase( &p->vLists );
    Vec_IntErase( &p->vCounts );
232
    Vec_IntErase( &p->vHits );
233 234 235
    Vec_IntErase( &p->vProfs );
    Vec_IntErase( &p->vStore );
    Vec_IntErase( &p->vTemp );
236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251
    ABC_FREE( p->pCells );
    ABC_FREE( p->pObjs );
    ABC_FREE( p );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
252
word Sfm_LibTruth6Two( Mio_Cell2_t * pCellBot, Mio_Cell2_t * pCellTop, int InTop )
253
{
254
    word uFanins[SFM_SUPP_MAX]; int i, k;
255 256 257
    word uTruthBot = Exp_Truth6( pCellBot->nFanins, pCellBot->vExpr, NULL );
    assert( InTop >= 0 && InTop < (int)pCellTop->nFanins );
    for ( i = 0, k = pCellBot->nFanins; i < (int)pCellTop->nFanins; i++ )
258 259 260 261
        if ( i == InTop )
            uFanins[i] = uTruthBot;
        else
            uFanins[i] = s_Truths6[k++];
262 263 264 265
    assert( (int)pCellBot->nFanins + (int)pCellTop->nFanins == k + 1 );
    uTruthBot = Exp_Truth6( pCellTop->nFanins, pCellTop->vExpr, uFanins );
    return uTruthBot;
}
266 267 268 269 270 271 272 273 274 275 276 277 278
void Sfm_LibTruth8Two( Mio_Cell2_t * pCellBot, Mio_Cell2_t * pCellTop, int InTop, word * pRes )
{
    word uTruthBot[4], * puFanins[SFM_SUPP_MAX]; int i, k;
    Exp_Truth8( pCellBot->nFanins, pCellBot->vExpr, NULL, uTruthBot );
    assert( InTop >= 0 && InTop < (int)pCellTop->nFanins );
    for ( i = 0, k = pCellBot->nFanins; i < (int)pCellTop->nFanins; i++ )
        if ( i == InTop )
            puFanins[i] = uTruthBot;
        else
            puFanins[i] = s_Truth8[k++];
    assert( (int)pCellBot->nFanins + (int)pCellTop->nFanins == k + 1 );
    Exp_Truth8( pCellTop->nFanins, pCellTop->vExpr, puFanins, pRes );
}
279 280 281 282 283 284 285 286 287 288 289 290

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
291
void Sfm_LibCellProfile( Mio_Cell2_t * pCellBot, Mio_Cell2_t * pCellTop, int InTop, int nFanins, int * Perm, int * pProf )
292
{
293
    int i, DelayAdd = pCellTop ? pCellTop->iDelays[InTop] : 0;
294 295
    for ( i = 0; i < nFanins; i++ )
        if ( Perm[i] < (int)pCellBot->nFanins )
296
            pProf[i] = pCellBot->iDelays[Perm[i]] + DelayAdd;
297
        else if ( Perm[i] < (int)pCellBot->nFanins + InTop )
298
            pProf[i] = pCellTop->iDelays[Perm[i] - (int)pCellBot->nFanins];
299
        else // if ( Perm[i] >= (int)pCellBot->nFanins + InTop )
300
            pProf[i] = pCellTop->iDelays[Perm[i] - (int)pCellBot->nFanins + 1];
301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321
}
static inline int Sfm_LibNewIsContained( Sfm_Fun_t * pObj, int * pProf, int Area, int * pProfNew, int nFanins )
{
    int k;
    if ( Area < pObj->Area )
        return 0;
    for ( k = 0; k < nFanins; k++ )
        if ( pProfNew[k] < pProf[k] )
            return 0;
    return 1;
}
static inline int Sfm_LibNewContains( Sfm_Fun_t * pObj, int * pProf, int Area, int * pProfNew, int nFanins )
{
    int k;
    if ( Area > pObj->Area )
        return 0;
    for ( k = 0; k < nFanins; k++ )
        if ( pProfNew[k] > pProf[k] )
            return 0;
    return 1;
}
322
void Sfm_LibPrepareAdd( Sfm_Lib_t * p, word * pTruth, int * Perm, int nFanins, Mio_Cell2_t * pCellBot, Mio_Cell2_t * pCellTop, int InTop )
323 324
{
    Sfm_Fun_t * pObj;
325
    int InvPerm[SFM_SUPP_MAX], Profile[SFM_SUPP_MAX];
326
    int Area = (int)pCellBot->AreaW + (pCellTop ? (int)pCellTop->AreaW : 0);
327
    int i, k, Id, Prev, Offset, * pProf, iFunc = Vec_MemHashInsert( p->vTtMem, pTruth );
328 329 330 331
    if ( iFunc == Vec_IntSize(&p->vLists) )
    {
        Vec_IntPush( &p->vLists, -1 );
        Vec_IntPush( &p->vCounts, 0 );
332
        Vec_IntPush( &p->vHits,   0 );
333 334 335
    }
    assert( pCellBot != NULL );
    // iterate through the supergates of this truth table
336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382
    if ( p->fDelay )
    {
        assert( Vec_IntSize(&p->vProfs) == p->nObjs );
        Sfm_LibCellProfile( pCellBot, pCellTop, InTop, nFanins, Perm, Profile );
        // check if new one is contained in old ones
        Vec_IntClear( &p->vTemp );
        Sfm_LibForEachSuper( p, pObj, iFunc )
        {
            Vec_IntPush( &p->vTemp, Sfm_LibFunId(p, pObj) );
            Offset = Vec_IntEntry( &p->vProfs, Sfm_LibFunId(p, pObj) );
            pProf  = Vec_IntEntryP( &p->vStore, Offset );
            if ( Sfm_LibNewIsContained(pObj, pProf, Area, Profile, nFanins) )
            {
                p->nObjSkipped++;
                return;
            }
        }
        // check if old ones are contained in new one
        k = 0;
        Vec_IntForEachEntry( &p->vTemp, Id, i )
        {
            Offset = Vec_IntEntry( &p->vProfs, Id );
            pProf  = Vec_IntEntryP( &p->vStore, Offset );
            if ( !Sfm_LibNewContains(Sfm_LibFun(p, Id), pProf, Area, Profile, nFanins) )
                Vec_IntWriteEntry( &p->vTemp, k++, Id );
            else
                p->nObjRemoved++;
        }
        if ( k < i ) // change
        {
            if ( k == 0 )
                Vec_IntWriteEntry( &p->vLists, iFunc, -1 );
            else
            {
                Vec_IntShrink( &p->vTemp, k );
                Prev = Vec_IntEntry(&p->vTemp, 0);
                Vec_IntWriteEntry( &p->vLists, iFunc, Prev );
                Vec_IntForEachEntryStart( &p->vTemp, Id, i, 1 )
                {
                    Sfm_LibFun(p, Prev)->Next = Id;
                    Prev = Id;
                }
                Sfm_LibFun(p, Prev)->Next = -1;
            }
        }
    }
    else
383
    {
384 385 386 387 388
        Sfm_LibForEachSuper( p, pObj, iFunc )
        {
            if ( Area >= pObj->Area )
                return;
        }
389
    }
390 391
    for ( k = 0; k < nFanins; k++ )
        InvPerm[Perm[k]] = k;
392 393 394 395 396 397 398
    // create delay profile
    if ( p->fDelay )
    {
        Vec_IntPush( &p->vProfs, Vec_IntSize(&p->vStore) );
        for ( k = 0; k < nFanins; k++ )
            Vec_IntPush( &p->vStore, Profile[k] );
    }
399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415
    // create new object
    if ( p->nObjs == p->nObjsAlloc )
    {
        int nObjsAlloc = 2 * p->nObjsAlloc;
        p->pObjs = ABC_REALLOC( Sfm_Fun_t, p->pObjs, nObjsAlloc );
        memset( p->pObjs + p->nObjsAlloc, 0, sizeof(Sfm_Fun_t) * p->nObjsAlloc );
        p->nObjsAlloc = nObjsAlloc;
    }
    pObj = p->pObjs + p->nObjs;
    pObj->Area = Area;
    pObj->Next = Vec_IntEntry(&p->vLists, iFunc);
    Vec_IntWriteEntry( &p->vLists, iFunc, p->nObjs++ );
    Vec_IntAddToEntry( &p->vCounts, iFunc, 1 );
    // create gate
    assert( pCellBot->Id < 128 );
    pObj->pFansB[0] = (char)pCellBot->Id;
    for ( k = 0; k < (int)pCellBot->nFanins; k++ )
416
        pObj->pFansB[k+1] = InvPerm[k];
417 418 419 420 421
    if ( pCellTop == NULL )
        return;
    assert( pCellTop->Id < 128 );
    pObj->pFansT[0] = (char)pCellTop->Id;
    for ( i = 0; i < (int)pCellTop->nFanins; i++ )
422
        pObj->pFansT[i+1] = (char)(i == InTop ? 16 : InvPerm[k++]);
423 424
    assert( k == nFanins );
}
425
Sfm_Lib_t * Sfm_LibPrepare( int nVars, int fTwo, int fDelay, int fVerbose, int fLibVerbose )
426 427
{
    abctime clk = Abc_Clock();
428
    Sfm_Lib_t * p = Sfm_LibStart( nVars, fDelay, fLibVerbose );
429
    Mio_Cell2_t * pCell1, * pCell2, * pLimit;
430 431 432
    int * pPerm[SFM_SUPP_MAX+1], * Perm1, * Perm2, Perm[SFM_SUPP_MAX];
    int nPerms[SFM_SUPP_MAX+1], i, f, n;
    word tTemp1[4], tCur[4];
433
    char pRes[1000];
434
    assert( nVars <= SFM_SUPP_MAX );
435
    // precompute gates
436
    p->pCells = Mio_CollectRootsNewDefault2( Abc_MinInt(6, nVars), &p->nCells, 0 );
437 438 439 440 441
    pLimit = p->pCells + p->nCells;
    // find useful ones
    for ( pCell1 = p->pCells + 4; pCell1 < pLimit; pCell1++ )
    {
        word uTruth = pCell1->uTruth;
442 443 444 445 446
        pCell1->Type = 0;
        if ( Abc_Tt6IsAndType(uTruth, pCell1->nFanins) || Abc_Tt6IsOrType(uTruth, pCell1->nFanins) )
            pCell1->Type = 1;
        else if ( Dau_DsdDecompose(&uTruth, pCell1->nFanins, 0, 0, pRes) <= 3 )
            pCell1->Type = 2;
447
        else if ( fLibVerbose )
448 449 450 451 452 453 454 455
            printf( "Skipping gate \"%s\" with non-DSD function %s\n", pCell1->pName, pRes );
    }
    // generate permutations
    for ( i = 2; i <= nVars; i++ )
        pPerm[i] = Extra_PermSchedule( i );
    for ( i = 2; i <= nVars; i++ )
        nPerms[i] = Extra_Factorial( i );
    // add single cells
456
    for ( pCell1 = p->pCells + 4; pCell1 < pLimit; pCell1++ ) 
457 458
    {
        int nFanins = pCell1->nFanins;
459
        assert( nFanins >= 2 && nFanins <= nVars );
460 461 462
        for ( i = 0; i < nFanins; i++ )
            Perm[i] = i;
        // permute truth table
463 464 465
        tCur[0] = tTemp1[0] = pCell1->uTruth;
        if ( p->nVars > 6 )
            tTemp1[1] = tTemp1[2] = tTemp1[3] = tCur[1] = tCur[2] = tCur[3] = tCur[0];
466 467 468 469
        for ( n = 0; n < nPerms[nFanins]; n++ )
        {
            Sfm_LibPrepareAdd( p, tCur, Perm, nFanins, pCell1, NULL, -1 );
            // update
470
            Abc_TtSwapAdjacent( tCur, p->nWords, pPerm[nFanins][n] );
471 472 473 474
            Perm1 = Perm + pPerm[nFanins][n];
            Perm2 = Perm1 + 1;
            ABC_SWAP( int, *Perm1, *Perm2 );
        }
475
        assert( Abc_TtEqual(tTemp1, tCur, p->nWords) );
476 477 478
    }
    // add double cells
    if ( fTwo )
479
    for ( pCell1 = p->pCells + 4; pCell1 < pLimit; pCell1++ ) // Bot
480
    if ( pCell1->Type > 0 )
481 482
    for ( pCell2 = p->pCells + 4; pCell2 < pLimit; pCell2++ ) // Top
    if ( pCell2->Type > 0 )//&& pCell1->Type + pCell2->Type <= 2 )
483 484 485 486 487 488 489 490
    if ( (int)pCell1->nFanins + (int)pCell2->nFanins <= nVars + 1 )
    for ( f = 0; f < (int)pCell2->nFanins; f++ )
    {
        int nFanins = pCell1->nFanins + pCell2->nFanins - 1;
        assert( nFanins >= 2 && nFanins <= nVars );
        for ( i = 0; i < nFanins; i++ )
            Perm[i] = i;
        // permute truth table
491 492 493 494 495 496 497
        if ( p->nVars > 6 )
        {
            Sfm_LibTruth8Two( pCell1, pCell2, f, tCur );
            Abc_TtCopy( tTemp1, tCur, p->nWords, 0 );
        }
        else
            tCur[0] = tTemp1[0] = Sfm_LibTruth6Two( pCell1, pCell2, f );
498 499 500
        for ( n = 0; n < nPerms[nFanins]; n++ )
        {
            Sfm_LibPrepareAdd( p, tCur, Perm, nFanins, pCell1, pCell2, f );
501 502
            if ( nFanins > 5 )
                break;
503
            // update
504
            Abc_TtSwapAdjacent( tCur, p->nWords, pPerm[nFanins][n] );
505 506 507 508
            Perm1 = Perm + pPerm[nFanins][n];
            Perm2 = Perm1 + 1;
            ABC_SWAP( int, *Perm1, *Perm2 );
        }
509
        assert( Abc_TtEqual(tTemp1, tCur, p->nWords) );
510 511 512 513 514 515
    }
    // cleanup
    for ( i = 2; i <= nVars; i++ )
        ABC_FREE( pPerm[i] );
    if ( fVerbose )
    {
516 517 518 519
        printf( "Library processing: Var = %d. Cell = %d.  Fun = %d. Obj = %d. Ave = %.2f.  Skip = %d. Rem = %d.  ", 
            nVars, p->nCells, Vec_MemEntryNum(p->vTtMem)-2, 
            p->nObjs-p->nObjRemoved, 1.0*(p->nObjs-p->nObjRemoved)/(Vec_MemEntryNum(p->vTtMem)-2), 
            p->nObjSkipped, p->nObjRemoved );
520 521 522 523 524 525 526
        Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    }
    return p;
}
void Sfm_LibPrintGate( Mio_Cell2_t * pCell, char * pFanins, Mio_Cell2_t * pCell2, char * pFanins2 )
{
    int k;
527
    printf( " %-20s(", pCell->pName );
528 529 530 531 532 533 534 535 536 537 538
    for ( k = 0; k < (int)pCell->nFanins; k++ )
        if ( pFanins[k] == (char)16 )
            Sfm_LibPrintGate( pCell2, pFanins2, NULL, NULL );
        else
            printf( " %c", 'a' + pFanins[k] );
    printf( " )" );
}
void Sfm_LibPrintObj( Sfm_Lib_t * p, Sfm_Fun_t * pObj )
{
    Mio_Cell2_t * pCellB = p->pCells + (int)pObj->pFansB[0];
    Mio_Cell2_t * pCellT = p->pCells + (int)pObj->pFansT[0];
539
    int i, nFanins = pCellB->nFanins + (pCellT == p->pCells ? 0 : pCellT->nFanins - 1);
540
    printf( "F = %d  A =%6.2f  ", nFanins, MIO_NUMINV*pObj->Area );
541 542 543 544
    if ( pCellT == p->pCells )
        Sfm_LibPrintGate( pCellB, pObj->pFansB + 1, NULL, NULL );
    else
        Sfm_LibPrintGate( pCellT, pObj->pFansT + 1, pCellB, pObj->pFansB + 1 );
545 546 547 548 549 550 551 552
    // get hold of delay info
    if ( p->fDelay )
    {
        int Offset  = Vec_IntEntry( &p->vProfs, Sfm_LibFunId(p, pObj) );
        int * pProf = Vec_IntEntryP( &p->vStore, Offset );
        for ( i = 0; i < nFanins; i++ )
            printf( "%6.2f ", MIO_NUMINV*pProf[i] );
    }
553 554 555
}
void Sfm_LibPrint( Sfm_Lib_t * p )
{
556 557
    Sfm_Fun_t * pObj; word * pTruth; int i, nFanins;   
    Vec_MemForEachEntry( p->vTtMem, pTruth, i )
558
    {
559
        if ( i < 2 || Vec_IntEntry(&p->vHits, i) == 0 )
560
            continue;
561 562 563 564 565
        nFanins = Abc_TtSupportSize(pTruth, p->nVars);
        printf( "%8d : ", i );
        printf( "Num =%5d  ", Vec_IntEntry(&p->vCounts, i) );
        printf( "Hit =%4d  ", Vec_IntEntry(&p->vHits, i) );
        Sfm_LibForEachSuper( p, pObj, i )
566
        {
567
            Sfm_LibPrintObj( p, pObj );
568
            break;
569
        }
570 571
        printf( "    " );
        Dau_DsdPrintFromTruth( pTruth, nFanins );
572 573
    }
}
574
void Sfm_LibTest()
575
{
576 577 578 579 580 581 582
    Sfm_Lib_t * p;
    int fVerbose = 1;
    if ( Abc_FrameReadLibGen() == NULL )
    {
        printf( "There is no current library.\n" );
        return;
    }
583
    p = Sfm_LibPrepare( 7, 1, 1, 1, fVerbose );
584 585
    if ( fVerbose )
        Sfm_LibPrint( p );
586 587 588 589 590 591 592 593 594 595 596 597 598 599
    Sfm_LibStop( p );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
600 601 602 603 604 605 606 607
int Sfm_LibFindAreaMatch( Sfm_Lib_t * p, word * pTruth, int nFanins, int * piObj )
{
    Sfm_Fun_t * pObj = NULL;
    int iFunc = *Vec_MemHashLookup( p->vTtMem,  pTruth );
    if ( iFunc == -1 )
        return -1;
    Sfm_LibForEachSuper( p, pObj, iFunc )
        break;
608 609
    if ( piObj )
        *piObj = pObj - p->pObjs;
610 611 612
    return pObj->Area;
}
int Sfm_LibFindDelayMatches( Sfm_Lib_t * p, word * pTruth, int * pFanins, int nFanins, Vec_Ptr_t * vGates, Vec_Ptr_t * vFans )
613 614
{
    Sfm_Fun_t * pObj;
615
    Mio_Cell2_t * pCellB, * pCellT;
616
    int iFunc;
617 618 619 620 621 622
    if ( nFanins > 6 )
    {
        word pCopy[4];
        Abc_TtCopy( pCopy, pTruth, 4, 0 );
        Dau_DsdPrintFromTruth( pCopy, p->nVars );
    }
623 624 625
    Vec_PtrClear( vGates );
    Vec_PtrClear( vFans );
    // look for gate
626 627 628 629 630
    assert( !Abc_TtIsConst0(pTruth, p->nWords) && 
            !Abc_TtIsConst1(pTruth, p->nWords) && 
            !Abc_TtEqual(pTruth, s_Truth8[0], p->nWords) && 
            !Abc_TtOpposite(pTruth, s_Truth8[0], p->nWords) );
    iFunc = *Vec_MemHashLookup( p->vTtMem,  pTruth );
631
    if ( iFunc == -1 )
632 633
    {
        // print functions not found in the library
634 635 636 637 638
        if ( p->fVerbose || nFanins > 6 )
        {
            printf( "Not found in the precomputed library: " );
            Dau_DsdPrintFromTruth( pTruth, nFanins );
        }
639
        return 0;
640 641
    }
    Vec_IntAddToEntry( &p->vHits, iFunc, 1 );
642 643 644 645 646
    // collect matches
    Sfm_LibForEachSuper( p, pObj, iFunc )
    {
        pCellB = p->pCells + (int)pObj->pFansB[0];
        pCellT = p->pCells + (int)pObj->pFansT[0];
647 648
        Vec_PtrPush( vGates, pCellB->pMioGate );
        Vec_PtrPush( vGates, pCellT == p->pCells ? NULL : pCellT->pMioGate );
649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665
        Vec_PtrPush( vFans, pObj->pFansB + 1 );
        Vec_PtrPush( vFans, pCellT == p->pCells ? NULL : pObj->pFansT + 1 );
    }
    return Vec_PtrSize(vGates) / 2;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
666
int Sfm_LibImplementSimple( Sfm_Lib_t * p, word * pTruth, int * pFanins, int nFanins, Vec_Int_t * vGates, Vec_Wec_t * vFanins )
667
{
668 669 670
    Mio_Library_t * pLib = (Mio_Library_t *)Abc_FrameReadLibGen();
    Mio_Gate_t * pGate;
    Vec_Int_t * vLevel;
671
    if ( Abc_TtIsConst0(pTruth, p->nWords) || Abc_TtIsConst1(pTruth, p->nWords) )
672 673
    {
        assert( nFanins == 0 );
674
        pGate = Abc_TtIsConst1(pTruth, p->nWords) ? Mio_LibraryReadConst1(pLib) : Mio_LibraryReadConst0(pLib);
675 676 677 678
        Vec_IntPush( vGates, Mio_GateReadValue(pGate) );
        vLevel = Vec_WecPushLevel( vFanins );
        return 1;
    }
679
    if ( Abc_TtEqual(pTruth, s_Truth8[0], p->nWords) || Abc_TtOpposite(pTruth, s_Truth8[0], p->nWords) )
680 681
    {
        assert( nFanins == 1 );
682
        pGate = Abc_TtEqual(pTruth, s_Truth8[0], p->nWords) ? Mio_LibraryReadBuf(pLib) : Mio_LibraryReadInv(pLib);
683 684 685 686 687
        Vec_IntPush( vGates, Mio_GateReadValue(pGate) );
        vLevel = Vec_WecPushLevel( vFanins );
        Vec_IntPush( vLevel, pFanins[0] );
        return 1;
    }
688 689 690 691 692 693 694 695 696 697 698
    assert( 0 );
    return -1;
}
int Sfm_LibImplementGatesArea( Sfm_Lib_t * p, int * pFanins, int nFanins, int iObj, Vec_Int_t * vGates, Vec_Wec_t * vFanins )
{
    Mio_Library_t * pLib = (Mio_Library_t *)Abc_FrameReadLibGen();
    Sfm_Fun_t * pObjMin = p->pObjs + iObj;
    Mio_Cell2_t * pCellB, * pCellT;
    Mio_Gate_t * pGate;
    Vec_Int_t * vLevel;
    int i;
699 700 701 702 703
    // get the gates
    pCellB = p->pCells + (int)pObjMin->pFansB[0];
    pCellT = p->pCells + (int)pObjMin->pFansT[0];
    // create bottom gate
    pGate = Mio_LibraryReadGateByName( pLib, pCellB->pName, NULL );
704
    assert( pGate == pCellB->pMioGate );
705 706 707 708 709 710 711 712
    Vec_IntPush( vGates, Mio_GateReadValue(pGate) );
    vLevel = Vec_WecPushLevel( vFanins );
    for ( i = 0; i < (int)pCellB->nFanins; i++ )
        Vec_IntPush( vLevel, pFanins[(int)pObjMin->pFansB[i+1]] );
    if ( pCellT == p->pCells )
        return 1;
    // create top gate
    pGate = Mio_LibraryReadGateByName( pLib, pCellT->pName, NULL );
713
    assert( pGate == pCellT->pMioGate );
714 715 716 717 718 719 720 721
    Vec_IntPush( vGates, Mio_GateReadValue(pGate) );
    vLevel = Vec_WecPushLevel( vFanins );
    for ( i = 0; i < (int)pCellT->nFanins; i++ )
        if ( pObjMin->pFansT[i+1] == (char)16 )
            Vec_IntPush( vLevel, Vec_WecSize(vFanins)-2 );
        else
            Vec_IntPush( vLevel, pFanins[(int)pObjMin->pFansT[i+1]] );
    return 2;
722
}
723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745
int Sfm_LibImplementGatesDelay( Sfm_Lib_t * p, int * pFanins, Mio_Gate_t * pGateB, Mio_Gate_t * pGateT, char * pFansB, char * pFansT, Vec_Int_t * vGates, Vec_Wec_t * vFanins )
{
    Vec_Int_t * vLevel;
    int i, nFanins;
    // create bottom gate
    Vec_IntPush( vGates, Mio_GateReadValue(pGateB) );
    vLevel  = Vec_WecPushLevel( vFanins );
    nFanins = Mio_GateReadPinNum( pGateB );
    for ( i = 0; i < nFanins; i++ )
        Vec_IntPush( vLevel, pFanins[(int)pFansB[i]] );
    if ( pGateT == NULL )
        return 1;
    // create top gate
    Vec_IntPush( vGates, Mio_GateReadValue(pGateT) );
    vLevel  = Vec_WecPushLevel( vFanins );
    nFanins = Mio_GateReadPinNum( pGateT );
    for ( i = 0; i < nFanins; i++ )
        if ( pFansT[i] == (char)16 )
            Vec_IntPush( vLevel, Vec_WecSize(vFanins)-2 );
        else
            Vec_IntPush( vLevel, pFanins[(int)pFansT[i]] );
    return 2;
}
746

747 748 749 750 751 752 753
////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END