mpmMap.c 28 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
/**CFile****************************************************************

  FileName    [mpmMap.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Configurable technology mapper.]

  Synopsis    [Mapping algorithm.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 1, 2013.]

  Revision    [$Id: mpmMap.c,v 1.00 2013/06/01 00:00:00 alanmi Exp $]

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

#include "mpmInt.h"

ABC_NAMESPACE_IMPL_START

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

Alan Mishchenko committed
29
//#define MIG_RUNTIME
Alan Mishchenko committed
30

Alan Mishchenko committed
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

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

  Synopsis    [Cut manipulation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Mpm_CutAlloc( Mpm_Man_t * p, int nLeaves, Mpm_Cut_t ** ppCut )  
{ 
    int hHandle = Mmr_StepFetch( p->pManCuts, Mpm_CutWordNum(nLeaves) );
    *ppCut      = (Mpm_Cut_t *)Mmr_StepEntry( p->pManCuts, hHandle );
    (*ppCut)->nLeaves  = nLeaves;
    (*ppCut)->hNext    = 0;
    (*ppCut)->fUseless = 0;
Alan Mishchenko committed
53
    (*ppCut)->fCompl   = 0;
Alan Mishchenko committed
54 55 56 57 58 59 60 61 62 63 64 65 66
    return hHandle;
}
static inline int Mpm_CutCreateZero( Mpm_Man_t * p )  
{ 
    Mpm_Cut_t * pCut;
    int hCut = Mpm_CutAlloc( p, 0, &pCut );
    pCut->iFunc      = 0; // const0
    return hCut;
}
static inline int Mpm_CutCreateUnit( Mpm_Man_t * p, int Id )  
{ 
    Mpm_Cut_t * pCut;
    int hCut = Mpm_CutAlloc( p, 1, &pCut );
Alan Mishchenko committed
67
    pCut->iFunc      = Abc_Var2Lit( p->funcVar0, 0 ); // var
Alan Mishchenko committed
68 69 70
    pCut->pLeaves[0] = Abc_Var2Lit( Id, 0 );
    return hCut;
}
Alan Mishchenko committed
71
static inline int Mpm_CutCreate( Mpm_Man_t * p, Mpm_Cut_t * pUni, Mpm_Cut_t ** ppCut )  
Alan Mishchenko committed
72
{ 
Alan Mishchenko committed
73 74 75 76 77 78
    int hCutNew = Mpm_CutAlloc( p, pUni->nLeaves, ppCut );
    (*ppCut)->iFunc    = pUni->iFunc;
    (*ppCut)->fCompl   = pUni->fCompl;
    (*ppCut)->fUseless = pUni->fUseless;
    (*ppCut)->nLeaves  = pUni->nLeaves;
    memcpy( (*ppCut)->pLeaves, pUni->pLeaves, sizeof(int) * pUni->nLeaves );
Alan Mishchenko committed
79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
    return hCutNew;
}
static inline int Mpm_CutDup( Mpm_Man_t * p, Mpm_Cut_t * pCut, int fCompl )  
{ 
    Mpm_Cut_t * pCutNew;
    int hCutNew = Mpm_CutAlloc( p, pCut->nLeaves, &pCutNew );
    pCutNew->iFunc    = Abc_LitNotCond( pCut->iFunc, fCompl );
    pCutNew->fUseless = pCut->fUseless;
    pCutNew->nLeaves  = pCut->nLeaves;
    memcpy( pCutNew->pLeaves, pCut->pLeaves, sizeof(int) * pCut->nLeaves );
    return hCutNew;
}
static inline int Mpm_CutCopySet( Mpm_Man_t * p, Mig_Obj_t * pObj, int fCompl )  
{
    Mpm_Cut_t * pCut;
    int hCut, iList = 0, * pList = &iList;
    Mpm_ObjForEachCut( p, pObj, hCut, pCut )
    {
        *pList = Mpm_CutDup( p, pCut, fCompl );
        pList = &Mpm_CutFetch( p, *pList )->hNext;
    }
    *pList = 0;
    return iList;
}
Alan Mishchenko committed
103
void Mpm_CutPrint( Mpm_Cut_t * pCut )  
Alan Mishchenko committed
104 105
{ 
    int i;
Alan Mishchenko committed
106 107 108
    printf( "%d : { ", pCut->nLeaves );
    for ( i = 0; i < (int)pCut->nLeaves; i++ )
        printf( "%d ", pCut->pLeaves[i] );
Alan Mishchenko committed
109 110 111 112 113 114 115 116
    printf( "}\n" );
}
static inline void Mpm_CutPrintAll( Mpm_Man_t * p )  
{ 
    int i;
    for ( i = 0; i < p->nCutStore; i++ )
    {
        printf( "%2d : ", i );
Alan Mishchenko committed
117
        Mpm_CutPrint( &p->pCutStore[i]->pCut );
Alan Mishchenko committed
118 119
    }
}
Alan Mishchenko committed
120
static inline int Mpm_CutFindLeaf( Mpm_Cut_t * pNew, int iObj )
Alan Mishchenko committed
121 122 123 124 125
{
    int i;
    for ( i = 0; i < (int)pNew->nLeaves; i++ )
        if ( Abc_Lit2Var(pNew->pLeaves[i]) == iObj )
            return i;
Alan Mishchenko committed
126
    return i;
Alan Mishchenko committed
127
}
Alan Mishchenko committed
128
static inline int Mpm_CutIsContained( Mpm_Man_t * p, Mpm_Cut_t * pBase, Mpm_Cut_t * pCut ) // check if pCut is contained pBase
Alan Mishchenko committed
129
{
Alan Mishchenko committed
130
    int i;
Alan Mishchenko committed
131
    for ( i = 0; i < (int)pCut->nLeaves; i++ )
Alan Mishchenko committed
132
        if ( Mpm_CutFindLeaf( pBase, Abc_Lit2Var(pCut->pLeaves[i]) ) == (int)pBase->nLeaves )
Alan Mishchenko committed
133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
            return 0;
    return 1;
}

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

  Synopsis    [Cut attibutes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
148 149 150 151 152 153
static inline int Mpm_CutGetArea( Mpm_Man_t * p, Mpm_Cut_t * pCut )  
{
    if ( p->pPars->fMap4Cnf )
        return MPM_UNIT_AREA * p->pDsd6[Abc_Lit2Var(pCut->iFunc)].nClauses;
    if ( p->pPars->fMap4Aig )
        return MPM_UNIT_AREA * p->pDsd6[Abc_Lit2Var(pCut->iFunc)].nAnds;
Alan Mishchenko committed
154
    if ( p->pPars->fMap4Gates )
Alan Mishchenko committed
155
        return MPM_UNIT_AREA * 1;
Alan Mishchenko committed
156 157
    return p->pLibLut->pLutAreas[pCut->nLeaves];
}
Alan Mishchenko committed
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
static inline word Mpm_CutGetSign( Mpm_Cut_t * pCut )  
{
    int i, iLeaf;
    word uSign = 0;
    Mpm_CutForEachLeafId( pCut, iLeaf, i )
        uSign |= ((word)1 << (iLeaf & 0x3F));
    return uSign;
}
static inline int Mpm_CutGetArrTime( Mpm_Man_t * p, Mpm_Cut_t * pCut )  
{
    int * pmTimes = Vec_IntArray( &p->vTimes );
    int * pDelays = p->pLibLut->pLutDelays[pCut->nLeaves];
    int i, iLeaf, ArrTime = 0;
    Mpm_CutForEachLeafId( pCut, iLeaf, i )
        ArrTime = Abc_MaxInt( ArrTime, pmTimes[iLeaf] + pDelays[i] );
    return ArrTime;
}
Alan Mishchenko committed
175
static inline Mpm_Uni_t * Mpm_CutSetupInfo( Mpm_Man_t * p, Mpm_Cut_t * pCut, int ArrTime )  
Alan Mishchenko committed
176 177 178 179 180 181 182
{
    int * pMigRefs = Vec_IntArray( &p->vMigRefs );
    int * pMapRefs = Vec_IntArray( &p->vMapRefs );
    int * pEstRefs = Vec_IntArray( &p->vEstRefs );
    int * pmArea   = Vec_IntArray( &p->vAreas );
    int * pmEdge   = Vec_IntArray( &p->vEdges );
    int i, iLeaf;
Alan Mishchenko committed
183
    Mpm_Uni_t * pUnit = (Mpm_Uni_t *)Vec_PtrEntryLast(&p->vFreeUnits);
Alan Mishchenko committed
184
    assert( &pUnit->pCut == pCut );
Alan Mishchenko committed
185
    pUnit->mTime    = ArrTime;
Alan Mishchenko committed
186
    pUnit->mArea    = Mpm_CutGetArea( p, pCut );
Alan Mishchenko committed
187 188 189
    pUnit->mEdge    = MPM_UNIT_EDGE * pCut->nLeaves;
    pUnit->mAveRefs = 0;
    pUnit->Cost     = 0;
Alan Mishchenko committed
190
    pUnit->uSign    = 0;
Alan Mishchenko committed
191 192 193 194
    Mpm_CutForEachLeafId( pCut, iLeaf, i )
    {
        if ( p->fMainRun && pMapRefs[iLeaf] == 0 ) // not used in the mapping
        {
Alan Mishchenko committed
195 196
            pUnit->mArea += pmArea[iLeaf];
            pUnit->mEdge += pmEdge[iLeaf];
Alan Mishchenko committed
197 198 199 200
        }
        else
        {
            assert( pEstRefs[iLeaf] > 0 );
Alan Mishchenko committed
201 202 203
            pUnit->mArea += MPM_UNIT_REFS * pmArea[iLeaf] / pEstRefs[iLeaf];
            pUnit->mEdge += MPM_UNIT_REFS * pmEdge[iLeaf] / pEstRefs[iLeaf];
            pUnit->mAveRefs += p->fMainRun ? pMapRefs[iLeaf] : pMigRefs[iLeaf];
Alan Mishchenko committed
204
        }
Alan Mishchenko committed
205
        pUnit->uSign |= ((word)1 << (iLeaf & 0x3F));
Alan Mishchenko committed
206
    }
Alan Mishchenko committed
207
    pUnit->mAveRefs = pUnit->mAveRefs * MPM_UNIT_EDGE / Abc_MaxInt(pCut->nLeaves, 1);
Alan Mishchenko committed
208 209 210
    assert( pUnit->mTime <= 0x3FFFFFFF );
    assert( pUnit->mArea <= 0x3FFFFFFF );
    assert( pUnit->mEdge <= 0x3FFFFFFF );
Alan Mishchenko committed
211
    return pUnit;
Alan Mishchenko committed
212 213 214 215
}

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

Alan Mishchenko committed
216
  Synopsis    [Compares cut against those present in the store.]
Alan Mishchenko committed
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Mpm_ObjAddCutToStore( Mpm_Man_t * p, Mpm_Cut_t * pCut, int ArrTime )
{
    int fEnableContainment = 1;
    Mpm_Uni_t * pUnit, * pUnitNew;
    int k, iPivot, last;
    // create new unit
#ifdef MIG_RUNTIME
    abctime clk;
clk = Abc_Clock();
#endif
Alan Mishchenko committed
235
    pUnitNew = Mpm_CutSetupInfo( p, pCut, ArrTime );
Alan Mishchenko committed
236 237 238 239 240 241 242
#ifdef MIG_RUNTIME
p->timeEval += Abc_Clock() - clk;
#endif
    // special case when the cut store is empty
    if ( p->nCutStore == 0 )
    {
        p->pCutStore[p->nCutStore++] = pUnitNew;
Alan Mishchenko committed
243
        Vec_PtrPop( &p->vFreeUnits );
Alan Mishchenko committed
244 245 246
        return 1;
    }
    // special case when the cut store is full and last cut is better than new cut
Alan Mishchenko committed
247
    if ( p->nCutStore == p->nNumCuts-1 && p->pCutCmp(pUnitNew, p->pCutStore[p->nCutStore-1]) > 0 )
Alan Mishchenko committed
248
        return 0;
Alan Mishchenko committed
249

Alan Mishchenko committed
250 251 252
    // find place of the given cut in the store
    assert( p->nCutStore <= p->nNumCuts );
    for ( iPivot = p->nCutStore - 1; iPivot >= 0; iPivot-- )
Alan Mishchenko committed
253
        if ( p->pCutCmp(pUnitNew, p->pCutStore[iPivot]) > 0 ) // iPivot-th cut is better than new cut
Alan Mishchenko committed
254 255 256 257 258 259 260
            break;

    if ( fEnableContainment )
    {
#ifdef MIG_RUNTIME
clk = Abc_Clock();
#endif
Alan Mishchenko committed
261 262
        // filter this cut using other cuts
        for ( k = 0; k <= iPivot; k++ )
Alan Mishchenko committed
263
        {
Alan Mishchenko committed
264 265 266
            pUnit = p->pCutStore[k];
            if ( pUnitNew->pCut.nLeaves >= pUnit->pCut.nLeaves && 
                (pUnitNew->uSign & pUnit->uSign) == pUnit->uSign && 
Alan Mishchenko committed
267
                 Mpm_CutIsContained(p, &pUnitNew->pCut, &pUnit->pCut) )
Alan Mishchenko committed
268
            {
Alan Mishchenko committed
269 270 271
#ifdef MIG_RUNTIME
p->timeCompare += Abc_Clock() - clk;
#endif
Alan Mishchenko committed
272 273
                return 0;
            }
Alan Mishchenko committed
274 275 276 277
        }
    }

    // special case when the best cut is useless while the new cut is not
Alan Mishchenko committed
278
    if ( p->pCutStore[0]->pCut.fUseless && !pUnitNew->pCut.fUseless )
Alan Mishchenko committed
279
        iPivot = -1;
Alan Mishchenko committed
280 281

    // add the cut to storage
Alan Mishchenko committed
282
    assert( pUnitNew == (Mpm_Uni_t *)Vec_PtrEntryLast(&p->vFreeUnits) );
Alan Mishchenko committed
283 284
    Vec_PtrPop( &p->vFreeUnits );

Alan Mishchenko committed
285 286 287 288 289 290 291 292
    // insert this cut at location iPivot
    iPivot++;
    for ( k = p->nCutStore++; k > iPivot; k-- )
        p->pCutStore[k] = p->pCutStore[k-1];
    p->pCutStore[iPivot] = pUnitNew;

    if ( fEnableContainment )
    {
Alan Mishchenko committed
293 294
        // filter other cuts using this cut
        for ( k = last = iPivot+1; k < p->nCutStore; k++ )
Alan Mishchenko committed
295
        {
Alan Mishchenko committed
296 297 298
            pUnit = p->pCutStore[k];
            if ( pUnitNew->pCut.nLeaves <= pUnit->pCut.nLeaves && 
                (pUnitNew->uSign & pUnit->uSign) == pUnitNew->uSign && 
Alan Mishchenko committed
299
                 Mpm_CutIsContained(p, &pUnit->pCut, &pUnitNew->pCut) )
Alan Mishchenko committed
300 301 302 303 304
            {
                Vec_PtrPush( &p->vFreeUnits, pUnit );
                continue;
            }
            p->pCutStore[last++] = p->pCutStore[k];
Alan Mishchenko committed
305
        }
Alan Mishchenko committed
306
        p->nCutStore = last;
Alan Mishchenko committed
307 308 309 310 311 312 313
#ifdef MIG_RUNTIME
p->timeCompare += Abc_Clock() - clk;
#endif
    }

    // remove the last cut if too many
    if ( p->nCutStore == p->nNumCuts )
Alan Mishchenko committed
314
        Vec_PtrPush( &p->vFreeUnits, p->pCutStore[--p->nCutStore] );
Alan Mishchenko committed
315 316 317 318 319 320 321 322 323 324 325 326 327 328 329
    assert( p->nCutStore < p->nNumCuts );
    return 1;
}

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

  Synopsis    [Cut enumeration.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
330
static inline Mpm_Cut_t * Mpm_ManMergeCuts( Mpm_Man_t * p, Mpm_Cut_t * pCut0, Mpm_Cut_t * pCut1, Mpm_Cut_t * pCut2 )
Alan Mishchenko committed
331
{
Alan Mishchenko committed
332
    Mpm_Cut_t * pTemp, * pCut = &((Mpm_Uni_t *)Vec_PtrEntryLast(&p->vFreeUnits))->pCut;
Alan Mishchenko committed
333
    int i, c, iPlace;
Alan Mishchenko committed
334 335 336 337 338
    // base cut
    memcpy( pCut->pLeaves, pCut0->pLeaves, sizeof(int) * pCut0->nLeaves );
    pCut->nLeaves = pCut0->nLeaves;
    // remaining cuts
    if ( p->pPars->fUseDsd )
Alan Mishchenko committed
339
    {
Alan Mishchenko committed
340 341 342 343 344 345 346 347 348
        for ( c = 1; c < 3; c++ )
        {
            pTemp = (c == 1) ? pCut1 : pCut2;
            if ( pTemp == NULL )
                break;
            p->uPermMask[c] = 0x3FFFF; // 18 bits
            p->uComplMask[c] = 0;     
            for ( i = 0; i < (int)pTemp->nLeaves; i++ )
            {
Alan Mishchenko committed
349
                iPlace = Mpm_CutFindLeaf( pCut, Abc_Lit2Var(pTemp->pLeaves[i]) );
Alan Mishchenko committed
350
                if ( iPlace == (int)pCut->nLeaves )
Alan Mishchenko committed
351 352 353 354 355
                {
                    if ( (int)pCut->nLeaves == p->nLutSize )
                        return NULL;
                    pCut->pLeaves[pCut->nLeaves++] = pTemp->pLeaves[i];
                }
Alan Mishchenko committed
356 357 358
                p->uPermMask[c] ^= (((i & 7) ^ 7) << (3*iPlace));
                if ( pTemp->pLeaves[i] != pCut->pLeaves[iPlace] )
                    p->uComplMask[c] |= (1 << iPlace);
Alan Mishchenko committed
359 360
            }
        }
Alan Mishchenko committed
361
    }
Alan Mishchenko committed
362
    else
Alan Mishchenko committed
363
    {
Alan Mishchenko committed
364
        for ( c = 1; c < 3; c++ )
Alan Mishchenko committed
365
        {
Alan Mishchenko committed
366 367 368 369
            pTemp = (c == 1) ? pCut1 : pCut2;
            if ( pTemp == NULL )
                break;
            for ( i = 0; i < (int)pTemp->nLeaves; i++ )
Alan Mishchenko committed
370
            {
Alan Mishchenko committed
371
                iPlace = Mpm_CutFindLeaf( pCut, Abc_Lit2Var(pTemp->pLeaves[i]) );
Alan Mishchenko committed
372 373 374 375 376 377
                if ( iPlace == (int)pCut->nLeaves )
                {
                    if ( (int)pCut->nLeaves == p->nLutSize )
                        return NULL;
                    pCut->pLeaves[pCut->nLeaves++] = pTemp->pLeaves[i];
                }
Alan Mishchenko committed
378
            }
Alan Mishchenko committed
379 380
        }
    }
Alan Mishchenko committed
381 382 383 384 385 386 387 388 389 390 391 392 393 394
    if ( pCut1 == NULL )
    {
        pCut->hNext    = 0;
        pCut->iFunc    = pCut0->iFunc;
        pCut->fUseless = pCut0->fUseless;
        pCut->fCompl   = pCut0->fCompl;
    }
    else
    {
        pCut->hNext    = 0;
        pCut->iFunc    = 0;  pCut->iFunc = ~pCut->iFunc;
        pCut->fUseless = 0;
        pCut->fCompl   = 0;
    }
Alan Mishchenko committed
395
    p->nCutsMerged++;
Alan Mishchenko committed
396
    p->nCutsMergedAll++;
Alan Mishchenko committed
397 398
    if ( p->pPars->fUseTruth )
        Vec_IntSelectSort( pCut->pLeaves, pCut->nLeaves );
Alan Mishchenko committed
399
    return pCut;
Alan Mishchenko committed
400
}
Alan Mishchenko committed
401
static inline int Mpm_ManExploreNewCut( Mpm_Man_t * p, Mig_Obj_t * pObj, Mpm_Cut_t * pCut0, Mpm_Cut_t * pCut1, Mpm_Cut_t * pCut2, int Required )
Alan Mishchenko committed
402
{
Alan Mishchenko committed
403
    Mpm_Cut_t * pCut;
Alan Mishchenko committed
404 405 406 407
    int ArrTime;
#ifdef MIG_RUNTIME
abctime clk = clock();
#endif
Alan Mishchenko committed
408 409

    if ( pCut0->nLeaves >= pCut1->nLeaves )
Alan Mishchenko committed
410
    {
Alan Mishchenko committed
411
        pCut = Mpm_ManMergeCuts( p, pCut0, pCut1, pCut2 );
Alan Mishchenko committed
412 413 414
#ifdef MIG_RUNTIME
p->timeMerge += clock() - clk;
#endif
Alan Mishchenko committed
415 416 417 418 419 420 421 422 423
        if ( pCut == NULL )
            return 1;
        if ( p->pPars->fUseTruth )
            Mpm_CutComputeTruth( p, pCut, pCut0, pCut1, pCut2, Mig_ObjFaninC0(pObj), Mig_ObjFaninC1(pObj), Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ); 
        else if ( p->pPars->fUseDsd )
        {
            if ( !Mpm_CutComputeDsd6( p, pCut, pCut0, pCut1, pCut2, Mig_ObjFaninC0(pObj), Mig_ObjFaninC1(pObj), Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ) )
                return 1;
        }
Alan Mishchenko committed
424
    }
Alan Mishchenko committed
425
    else
Alan Mishchenko committed
426
    {
Alan Mishchenko committed
427 428 429 430 431
        pCut = Mpm_ManMergeCuts( p, pCut1, pCut0, pCut2 );
#ifdef MIG_RUNTIME
p->timeMerge += clock() - clk;
#endif
        if ( pCut == NULL )
Alan Mishchenko committed
432
            return 1;
Alan Mishchenko committed
433 434 435 436 437 438 439
        if ( p->pPars->fUseTruth )
            Mpm_CutComputeTruth( p, pCut, pCut1, pCut0, pCut2, Mig_ObjFaninC1(pObj), Mig_ObjFaninC0(pObj), 1 ^ Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ); 
        else if ( p->pPars->fUseDsd )
        {
            if ( !Mpm_CutComputeDsd6( p, pCut, pCut1, pCut0, pCut2, Mig_ObjFaninC1(pObj), Mig_ObjFaninC0(pObj), 1 ^ Mig_ObjFaninC2(pObj), Mig_ObjNodeType(pObj) ) )
                return 1;
        }
Alan Mishchenko committed
440
    }
Alan Mishchenko committed
441

Alan Mishchenko committed
442 443 444 445 446 447 448 449 450
#ifdef MIG_RUNTIME
clk = clock();
#endif
    ArrTime = Mpm_CutGetArrTime( p, pCut );
#ifdef MIG_RUNTIME
p->timeEval += clock() - clk;
#endif
    if ( p->fMainRun && ArrTime > Required )
        return 1;
Alan Mishchenko committed
451

Alan Mishchenko committed
452 453 454 455 456 457 458
#ifdef MIG_RUNTIME
clk = Abc_Clock();
#endif
    Mpm_ObjAddCutToStore( p, pCut, ArrTime );
#ifdef MIG_RUNTIME
p->timeStore += Abc_Clock() - clk;
#endif
Alan Mishchenko committed
459

Alan Mishchenko committed
460 461
/*
    // return 0 if const or buffer cut is derived - reset all cuts to contain only one --- does not work
Alan Mishchenko committed
462 463
//    if ( pCut->nLeaves < 2 && p->nCutStore == 1 )
//        return 0;
Alan Mishchenko committed
464
    if ( pCut->nLeaves < 2 ) 
Alan Mishchenko committed
465 466 467 468 469 470 471 472 473 474
    {
        int i;
        assert( p->nCutStore >= 1 );
        for ( i = 1; i < p->nCutStore; i++ )
            Vec_PtrPush( &p->vFreeUnits, p->pCutStore[i] );
        p->nCutStore = 1;
        return 0;
    }
*/
    return 1;
Alan Mishchenko committed
475
}
Alan Mishchenko committed
476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Mpm_ObjRecycleCuts( Mpm_Man_t * p, Mig_Obj_t * pObj )
{
    Mpm_Cut_t * pCut;
    int hCut, hNext;
    Mpm_ObjForEachCutSafe( p, pObj, hCut, pCut, hNext )
        Mmr_StepRecycle( p->pManCuts, hCut );
    Mpm_ObjSetCutList( p, pObj, 0 );
}
static inline void Mpm_ObjDerefFaninCuts( Mpm_Man_t * p, Mig_Obj_t * pObj )
{
    Mig_Obj_t * pFanin;
    int i;
    Mig_ObjForEachFanin( pObj, pFanin, i )
        if ( Mig_ObjIsNode(pFanin) && Mig_ObjMigRefDec(p, pFanin) == 0 )
            Mpm_ObjRecycleCuts( p, pFanin );
    pFanin = Mig_ObjSibl(pObj);
    if ( pFanin && Mig_ObjMigRefDec(p, pFanin) == 0 )
        Mpm_ObjRecycleCuts( p, pFanin );
    if ( Mig_ObjMigRefNum(p, pObj) == 0 )
        Mpm_ObjRecycleCuts( p, pObj );
}
static inline void Mpm_ObjCollectFaninsAndSigns( Mpm_Man_t * p, Mig_Obj_t * pObj, int i )
{
    Mpm_Cut_t * pCut;
    int hCut, nCuts = 0;
    Mpm_ObjForEachCut( p, pObj, hCut, pCut )
    {
        p->pCuts[i][nCuts] = pCut;
        p->pSigns[i][nCuts++] = Mpm_CutGetSign( pCut );
    }
    p->nCuts[i] = nCuts;
}
static inline void Mpm_ObjPrepareFanins( Mpm_Man_t * p, Mig_Obj_t * pObj )
{
    Mig_Obj_t * pFanin;
    int i;
    Mig_ObjForEachFanin( pObj, pFanin, i )
        Mpm_ObjCollectFaninsAndSigns( p, pFanin, i );
}
// create storage from cuts at the node
void Mpm_ObjAddChoiceCutsToStore( Mpm_Man_t * p, Mig_Obj_t * pRoot, Mig_Obj_t * pObj, int ReqTime )
{
    Mpm_Cut_t * pCut;
    int hCut, hNext, ArrTime;
    int fCompl = Mig_ObjPhase(pRoot) ^ Mig_ObjPhase(pObj);
    Mpm_ObjForEachCutSafe( p, pObj, hCut, pCut, hNext )
    {
        if ( Abc_Lit2Var(pCut->pLeaves[0]) == Mig_ObjId(pObj) )
            continue;
        ArrTime = Mpm_CutGetArrTime( p, pCut );
        if ( ArrTime > ReqTime )
            continue;
        pCut->fCompl ^= fCompl;
        pCut = Mpm_ManMergeCuts( p, pCut, NULL, NULL );
        Mpm_ObjAddCutToStore( p, pCut, ArrTime );
    }
}
// create cuts at the node from storage
void Mpm_ObjTranslateCutsFromStore( Mpm_Man_t * p, Mig_Obj_t * pObj )
{
    Mpm_Cut_t * pCut = NULL;
    Mpm_Uni_t * pUnit;
    int i, *pList = Mpm_ObjCutListP( p, pObj );
    assert( p->nCutStore > 0 && p->nCutStore <= p->nNumCuts );
    assert( *pList == 0 );
    // translate cuts
    for ( i = 0; i < p->nCutStore; i++ )
    {
        pUnit  = p->pCutStore[i];
        *pList = Mpm_CutCreate( p, &pUnit->pCut, &pCut );
        pList  = &pCut->hNext;
        Vec_PtrPush( &p->vFreeUnits, pUnit );
    }
    assert( Vec_PtrSize(&p->vFreeUnits) == p->nNumCuts + 1 );
    if ( p->nCutStore == 1 && pCut->nLeaves < 2 )
        *pList = 0;
    else
        *pList = Mpm_CutCreateUnit( p, Mig_ObjId(pObj) );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
580 581
int Mpm_ManDeriveCuts( Mpm_Man_t * p, Mig_Obj_t * pObj )
{
Alan Mishchenko committed
582
    Mpm_Cut_t * pCut0, * pCut1, * pCut2;
Alan Mishchenko committed
583 584 585 586
    int Required = Mpm_ObjRequired( p, pObj );
    int hCutBest = Mpm_ObjCutBest( p, pObj );
    int c0, c1, c2;
#ifdef MIG_RUNTIME
Alan Mishchenko committed
587
abctime clk;
Alan Mishchenko committed
588
#endif
Alan Mishchenko committed
589

Alan Mishchenko committed
590
    assert( Vec_PtrSize( &p->vFreeUnits ) == p->nNumCuts + 1 );
Alan Mishchenko committed
591
    assert( Mpm_ObjCutList(p, pObj) == 0 );
Alan Mishchenko committed
592
    p->nCutStore = 0;
Alan Mishchenko committed
593 594 595 596 597 598 599 600
    if ( hCutBest > 0 ) // cut list is assigned
    {
        Mpm_Cut_t * pCut = Mpm_ObjCutBestP( p, pObj ); 
        int Times = Mpm_CutGetArrTime( p, pCut );
        assert( pCut->hNext == 0 );
        if ( Times > Required )
            printf( "Arrival time (%d) exceeds required time (%d) at object %d.\n", Times, Required, Mig_ObjId(pObj) );
        if ( p->fMainRun )
Alan Mishchenko committed
601
            Mpm_ObjAddCutToStore( p, Mpm_ManMergeCuts(p, pCut, NULL, NULL), Times );
Alan Mishchenko committed
602 603 604 605
        else
            Mpm_ObjSetTime( p, pObj, Times );
    }
    // start storage with choice cuts
Alan Mishchenko committed
606 607 608
    if ( Mig_ManChoiceNum(p->pMig) && Mig_ObjSiblId(pObj) )
        Mpm_ObjAddChoiceCutsToStore( p, pObj, Mig_ObjSibl(pObj), Required );

Alan Mishchenko committed
609 610 611 612 613 614 615
#ifdef MIG_RUNTIME
clk = Abc_Clock();
#endif
    Mpm_ObjPrepareFanins( p, pObj );
    if ( Mig_ObjIsNode2(pObj) )
    {
        // go through cut pairs
Alan Mishchenko committed
616 617
        for ( c0 = 0; c0 < p->nCuts[0] && (pCut0 = p->pCuts[0][c0]); c0++ )
        for ( c1 = 0; c1 < p->nCuts[1] && (pCut1 = p->pCuts[1][c1]); c1++ )
Alan Mishchenko committed
618
            if ( Abc_TtCountOnes(p->pSigns[0][c0] | p->pSigns[1][c1]) <= p->nLutSize )
Alan Mishchenko committed
619
                if ( !Mpm_ManExploreNewCut( p, pObj, pCut0, pCut1, NULL, Required ) )
Alan Mishchenko committed
620 621 622 623 624
                    goto finish;
    }
    else if ( Mig_ObjIsNode3(pObj) )
    {
        // go through cut triples
Alan Mishchenko committed
625 626 627
        for ( c0 = 0; c0 < p->nCuts[0] && (pCut0 = p->pCuts[0][c0]); c0++ )
        for ( c1 = 0; c1 < p->nCuts[1] && (pCut1 = p->pCuts[1][c1]); c1++ )
        for ( c2 = 0; c2 < p->nCuts[2] && (pCut2 = p->pCuts[2][c2]); c2++ )
Alan Mishchenko committed
628
            if ( Abc_TtCountOnes(p->pSigns[0][c0] | p->pSigns[1][c1] | p->pSigns[2][c2]) <= p->nLutSize )
Alan Mishchenko committed
629
                if ( !Mpm_ManExploreNewCut( p, pObj, pCut0, pCut1, pCut2, Required ) )
Alan Mishchenko committed
630 631 632 633 634 635
                    goto finish;
    }
    else assert( 0 );
#ifdef MIG_RUNTIME
p->timeDerive += Abc_Clock() - clk;
#endif
Alan Mishchenko committed
636

Alan Mishchenko committed
637 638 639
finish:
    // save best cut
    assert( p->nCutStore > 0 );
Alan Mishchenko committed
640
    if ( p->pCutStore[0]->mTime <= Required )
Alan Mishchenko committed
641 642 643 644
    {
        Mpm_Cut_t * pCut;
        if ( hCutBest )
            Mmr_StepRecycle( p->pManCuts, hCutBest );
Alan Mishchenko committed
645
        hCutBest = Mpm_CutCreate( p, &p->pCutStore[0]->pCut, &pCut );
Alan Mishchenko committed
646
        Mpm_ObjSetCutBest( p, pObj, hCutBest );
Alan Mishchenko committed
647 648 649
        Mpm_ObjSetTime( p, pObj, p->pCutStore[0]->mTime );
        Mpm_ObjSetArea( p, pObj, p->pCutStore[0]->mArea );
        Mpm_ObjSetEdge( p, pObj, p->pCutStore[0]->mEdge );
Alan Mishchenko committed
650 651 652 653
    }
    else assert( !p->fMainRun );
    assert( hCutBest > 0 );
    // transform internal storage into regular cuts
Alan Mishchenko committed
654
    Mpm_ObjTranslateCutsFromStore( p, pObj );
Alan Mishchenko committed
655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691
    // dereference fanin cuts and reference node
    Mpm_ObjDerefFaninCuts( p, pObj );
    return 1;
}


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

  Synopsis    [Required times.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Mpm_ManFindArrivalMax( Mpm_Man_t * p )
{
    int * pmTimes = Vec_IntArray( &p->vTimes );
    Mig_Obj_t * pObj;
    int i, ArrMax = 0;
    Mig_ManForEachCo( p->pMig, pObj, i )
        ArrMax = Abc_MaxInt( ArrMax, pmTimes[ Mig_ObjFaninId0(pObj) ] );
    return ArrMax;
}
static inline void Mpm_ManFinalizeRound( Mpm_Man_t * p )
{
    int * pMapRefs  = Vec_IntArray( &p->vMapRefs );
    int * pRequired = Vec_IntArray( &p->vRequireds );
    Mig_Obj_t * pObj;
    Mpm_Cut_t * pCut;
    int * pDelays;
    int i, iLeaf;
    p->GloArea = 0;
    p->GloEdge = 0;
    p->GloRequired = Mpm_ManFindArrivalMax(p);
Alan Mishchenko committed
692 693
    if ( p->pPars->DelayTarget != -1 )
        p->GloRequired = Abc_MaxInt( p->GloRequired, p->pPars->DelayTarget );
Alan Mishchenko committed
694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715
    Mpm_ManCleanMapRefs( p );
    Mpm_ManCleanRequired( p );
    Mig_ManForEachObjReverse( p->pMig, pObj )
    {
        if ( Mig_ObjIsCo(pObj) )
        {
            pRequired[Mig_ObjFaninId0(pObj)] = p->GloRequired;
            pMapRefs [Mig_ObjFaninId0(pObj)]++;
        }
        else if ( Mig_ObjIsNode(pObj) )
        {
            int Required = pRequired[Mig_ObjId(pObj)];
            assert( Required > 0 );
            if ( pMapRefs[Mig_ObjId(pObj)] > 0 )
            {
                pCut = Mpm_ObjCutBestP( p, pObj );
                pDelays = p->pLibLut->pLutDelays[pCut->nLeaves];
                Mpm_CutForEachLeafId( pCut, iLeaf, i )
                {
                    pRequired[iLeaf] = Abc_MinInt( pRequired[iLeaf], Required - pDelays[i] );
                    pMapRefs [iLeaf]++;
                }
Alan Mishchenko committed
716
                p->GloArea += Mpm_CutGetArea( p, pCut );
Alan Mishchenko committed
717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747
                p->GloEdge += pCut->nLeaves;
            }
        }
        else if ( Mig_ObjIsBuf(pObj) )
        {
        }
    }
    p->GloArea /= MPM_UNIT_AREA;
}
static inline void Mpm_ManComputeEstRefs( Mpm_Man_t * p )
{
    int * pMapRefs  = Vec_IntArray( &p->vMapRefs );
    int * pEstRefs  = Vec_IntArray( &p->vEstRefs );
    int i;
    assert( p->fMainRun );
//  pObj->EstRefs = (float)((2.0 * pObj->EstRefs + pObj->nRefs) / 3.0);
    for ( i = 0; i < Mig_ManObjNum(p->pMig); i++ )
        pEstRefs[i] = (1 * pEstRefs[i] + MPM_UNIT_REFS * pMapRefs[i]) / 2;
}

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

  Synopsis    [Cut comparison.]

  Description [Returns positive number if new one is better than old one.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
748
int Mpm_CutCompareDelay( Mpm_Uni_t * pOld, Mpm_Uni_t * pNew )
Alan Mishchenko committed
749
{
Alan Mishchenko committed
750 751 752 753
    if ( pOld->mTime        != pNew->mTime         ) return pOld->mTime        - pNew->mTime;
    if ( pOld->pCut.nLeaves != pNew->pCut.nLeaves  ) return pOld->pCut.nLeaves - pNew->pCut.nLeaves;
    if ( pOld->mArea        != pNew->mArea         ) return pOld->mArea        - pNew->mArea;
    if ( pOld->mEdge        != pNew->mEdge         ) return pOld->mEdge        - pNew->mEdge;
Alan Mishchenko committed
754 755
    return 0;
}
Alan Mishchenko committed
756
int Mpm_CutCompareDelay2( Mpm_Uni_t * pOld, Mpm_Uni_t * pNew )
Alan Mishchenko committed
757
{
Alan Mishchenko committed
758 759 760 761
    if ( pOld->mTime        != pNew->mTime         ) return pOld->mTime        - pNew->mTime;
    if ( pOld->mArea        != pNew->mArea         ) return pOld->mArea        - pNew->mArea;
    if ( pOld->mEdge        != pNew->mEdge         ) return pOld->mEdge        - pNew->mEdge;
    if ( pOld->pCut.nLeaves != pNew->pCut.nLeaves  ) return pOld->pCut.nLeaves - pNew->pCut.nLeaves;
Alan Mishchenko committed
762 763
    return 0;
}
Alan Mishchenko committed
764
int Mpm_CutCompareArea( Mpm_Uni_t * pOld, Mpm_Uni_t * pNew )
Alan Mishchenko committed
765
{
Alan Mishchenko committed
766 767 768 769 770
    if ( pOld->mArea        != pNew->mArea         ) return pOld->mArea        - pNew->mArea;
    if ( pOld->pCut.nLeaves != pNew->pCut.nLeaves  ) return pOld->pCut.nLeaves - pNew->pCut.nLeaves;
    if ( pOld->mEdge        != pNew->mEdge         ) return pOld->mEdge        - pNew->mEdge;
    if ( pOld->mAveRefs     != pNew->mAveRefs      ) return pOld->mAveRefs     - pNew->mAveRefs;
    if ( pOld->mTime        != pNew->mTime         ) return pOld->mTime        - pNew->mTime;
Alan Mishchenko committed
771 772
    return 0;
}
Alan Mishchenko committed
773
int Mpm_CutCompareArea2( Mpm_Uni_t * pOld, Mpm_Uni_t * pNew )
Alan Mishchenko committed
774
{
Alan Mishchenko committed
775 776 777 778 779
    if ( pOld->mArea        != pNew->mArea         ) return pOld->mArea        - pNew->mArea;
    if ( pOld->mEdge        != pNew->mEdge         ) return pOld->mEdge        - pNew->mEdge;
    if ( pOld->mAveRefs     != pNew->mAveRefs      ) return pOld->mAveRefs     - pNew->mAveRefs;
    if ( pOld->pCut.nLeaves != pNew->pCut.nLeaves  ) return pOld->pCut.nLeaves - pNew->pCut.nLeaves;
    if ( pOld->mTime        != pNew->mTime         ) return pOld->mTime        - pNew->mTime;
Alan Mishchenko committed
780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810
    return 0;
}

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

  Synopsis    [Technology mapping experiment.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Mpm_ManPrepare( Mpm_Man_t * p )
{
    Mig_Obj_t * pObj;
    int i, hCut;
    Mig_ManForEachCi( p->pMig, pObj, i )
    {
        hCut = Mpm_CutCreateUnit( p, Mig_ObjId(pObj) );
        Mpm_ObjSetCutBest( p, pObj, hCut );
        Mpm_ObjSetCutList( p, pObj, hCut );
    }
    Mig_ManForEachCand( p->pMig, pObj )
        Mpm_ObjSetEstRef( p, pObj, MPM_UNIT_REFS * Mig_ObjRefNum(pObj) );
}
void Mpm_ManPerformRound( Mpm_Man_t * p )
{
    Mig_Obj_t * pObj;
    abctime clk = Abc_Clock();
Alan Mishchenko committed
811 812 813 814 815 816 817
    int i;
    // copy references
    assert( Vec_IntSize(&p->vMigRefs) == Vec_IntSize(&p->pMig->vRefs) );
    memcpy( Vec_IntArray(&p->vMigRefs), Vec_IntArray(&p->pMig->vRefs), sizeof(int) * Mig_ManObjNum(p->pMig) );
    Mig_ManForEachCo( p->pMig, pObj, i )
        Mig_ObjMigRefDec( p, Mig_ObjFanin0(pObj) );
    // derive cuts
Alan Mishchenko committed
818 819 820
    p->nCutsMerged = 0;
    Mig_ManForEachNode( p->pMig, pObj )
        Mpm_ManDeriveCuts( p, pObj );
Alan Mishchenko committed
821
    assert( Mig_ManCandNum(p->pMig) == p->pManCuts->nEntries );
Alan Mishchenko committed
822
    Mpm_ManFinalizeRound( p );
Alan Mishchenko committed
823 824 825
    // report results
    if ( p->pPars->fVerbose )
    {
Alan Mishchenko committed
826
    printf( "Del =%5d.  Ar =%8d.  Edge =%8d.  Cut =%10d. Max =%8d.  Tru =%8d. Small =%6d. ", 
Alan Mishchenko committed
827
        p->GloRequired, (int)p->GloArea, (int)p->GloEdge, 
Alan Mishchenko committed
828 829
        p->nCutsMerged, p->pManCuts->nEntriesMax, 
        p->vTtMem ? p->vTtMem->nEntries : 0, p->nSmallSupp );
Alan Mishchenko committed
830
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
Alan Mishchenko committed
831
    }
Alan Mishchenko committed
832 833 834
}
void Mpm_ManPerform( Mpm_Man_t * p )
{
Alan Mishchenko committed
835 836 837 838 839 840 841 842 843 844 845
    if ( p->pPars->fMap4Cnf )
    {
        p->pCutCmp = Mpm_CutCompareArea;
        Mpm_ManPerformRound( p );   
    }
    else
    {
        p->pCutCmp = Mpm_CutCompareDelay;
        Mpm_ManPerformRound( p );
        if ( p->pPars->fOneRound )
            return;
Alan Mishchenko committed
846
    
Alan Mishchenko committed
847 848
        p->pCutCmp = Mpm_CutCompareDelay2;
        Mpm_ManPerformRound( p );
Alan Mishchenko committed
849
    
Alan Mishchenko committed
850 851
        p->pCutCmp = Mpm_CutCompareArea;
        Mpm_ManPerformRound( p );   
Alan Mishchenko committed
852

Alan Mishchenko committed
853
        p->fMainRun = 1;
Alan Mishchenko committed
854

Alan Mishchenko committed
855 856 857
        p->pCutCmp = Mpm_CutCompareArea;
        Mpm_ManComputeEstRefs( p );
        Mpm_ManPerformRound( p );
Alan Mishchenko committed
858

Alan Mishchenko committed
859 860 861 862
        p->pCutCmp = Mpm_CutCompareArea2;
        Mpm_ManComputeEstRefs( p );
        Mpm_ManPerformRound( p );
    }
Alan Mishchenko committed
863 864 865 866 867 868 869 870 871 872
}


////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END