sbdCore.c 81 KB
Newer Older
1 2
/**CFile****************************************************************

3
  FileName    [sbdCore.c]
4 5 6 7 8

  SystemName  [ABC: Logic synthesis and verification system.]

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

9
  Synopsis    [Core procedures.]
10 11 12 13 14 15 16

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

17
  Revision    [$Id: sbdCore.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 19 20 21

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

#include "sbdInt.h"
22
#include "opt/dau/dau.h"
23
#include "misc/tim/tim.h"
24 25 26 27 28 29 30

ABC_NAMESPACE_IMPL_START

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

31 32 33 34 35 36 37 38 39 40
#define SBD_MAX_LUTSIZE 6

typedef struct Sbd_Man_t_ Sbd_Man_t;
struct Sbd_Man_t_
{
    Sbd_Par_t *     pPars;       // user's parameters
    Gia_Man_t *     pGia;        // user's AIG manager (will be modified by adding nodes)
    Vec_Wec_t *     vTfos;       // TFO for each node (roots are marked) (windowing)
    Vec_Int_t *     vLutLevs;    // LUT level for each node after resynthesis
    Vec_Int_t *     vLutCuts;    // LUT cut for each nodes after resynthesis
41
    Vec_Int_t *     vLutCuts2;   // LUT cut for each nodes after resynthesis
42
    Vec_Int_t *     vMirrors;    // alternative node
43
    Vec_Wrd_t *     vSims[4];    // simulation information (main, backup, controlability)
44
    Vec_Int_t *     vCover;      // temporary
45
    Vec_Int_t *     vLits;       // temporary
46
    Vec_Int_t *     vLits2;      // temporary
47 48 49
    int             nLuts[6];    // 0=const, 1=1lut, 2=2lut, 3=3lut
    int             nTried;  
    int             nUsed;  
50
    abctime         timeWin;
51 52
    abctime         timeCut;
    abctime         timeCov;
53 54
    abctime         timeCnf;
    abctime         timeSat;
55
    abctime         timeQbf;
56
    abctime         timeNew;
57 58
    abctime         timeOther;
    abctime         timeTotal;
59
    Sbd_Sto_t *     pSto;
60
    Sbd_Srv_t *     pSrv;
61 62
    // target node
    int             Pivot;       // target node
63
    int             DivCutoff;   // the place where D-2 divisors begin
64 65 66 67
    Vec_Int_t *     vTfo;        // TFO (excludes node, includes roots) - precomputed
    Vec_Int_t *     vRoots;      // TFO root nodes
    Vec_Int_t *     vWinObjs;    // TFI + Pivot + sideTFI + TFO (including roots)
    Vec_Int_t *     vObj2Var;    // SAT variables for the window (indexes of objects in vWinObjs)
68
    Vec_Int_t *     vDivSet;     // divisor variables
69 70 71
    Vec_Int_t *     vDivVars;    // divisor variables
    Vec_Int_t *     vDivValues;  // SAT variables values for the divisor variables
    Vec_Wec_t *     vDivLevels;  // divisors collected by levels
72
    Vec_Int_t *     vCounts[2];  // counters of zeros and ones
73 74
    Vec_Wrd_t *     vMatrix;     // covering matrix
    sat_solver *    pSat;        // SAT solver
75 76
};

77 78
static inline int *  Sbd_ObjCut( Sbd_Man_t * p, int i )  { return Vec_IntEntryP( p->vLutCuts,  (p->pPars->nLutSize + 1) * i ); }
static inline int *  Sbd_ObjCut2( Sbd_Man_t * p, int i ) { return Vec_IntEntryP( p->vLutCuts2, (p->pPars->nLutSize + 1) * i ); }
79 80 81 82

static inline word * Sbd_ObjSim0( Sbd_Man_t * p, int i ) { return Vec_WrdEntryP( p->vSims[0], p->pPars->nWords * i );         }
static inline word * Sbd_ObjSim1( Sbd_Man_t * p, int i ) { return Vec_WrdEntryP( p->vSims[1], p->pPars->nWords * i );         }
static inline word * Sbd_ObjSim2( Sbd_Man_t * p, int i ) { return Vec_WrdEntryP( p->vSims[2], p->pPars->nWords * i );         }
83
static inline word * Sbd_ObjSim3( Sbd_Man_t * p, int i ) { return Vec_WrdEntryP( p->vSims[3], p->pPars->nWords * i );         }
84

85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
100 101 102
void Sbd_ParSetDefault( Sbd_Par_t * pPars )
{
    memset( pPars, 0, sizeof(Sbd_Par_t) );
103 104 105 106 107 108 109 110 111
    pPars->nLutSize     = 4;    // target LUT size
    pPars->nLutNum      = 3;    // target LUT count
    pPars->nCutSize     = (pPars->nLutSize - 1) * pPars->nLutNum + 1;  // target cut size
    pPars->nCutNum      = 128;  // target cut count
    pPars->nTfoLevels   = 5;    // the number of TFO levels (windowing)
    pPars->nTfoFanMax   = 4;    // the max number of fanouts (windowing)
    pPars->nWinSizeMax  = 2000; // maximum window size (windowing)
    pPars->nBTLimit     = 0;    // maximum number of SAT conflicts 
    pPars->nWords       = 1;    // simulation word count
112 113 114 115
    pPars->fMapping     = 1;    // generate mapping
    pPars->fMoreCuts    = 0;    // use several cuts
    pPars->fFindDivs    = 0;    // perform divisor search
    pPars->fUsePath     = 0;    // optimize only critical path
116 117 118 119
    pPars->fArea        = 0;    // area-oriented optimization
    pPars->fCover       = 0;    // use complete cover procedure
    pPars->fVerbose     = 0;    // verbose flag
    pPars->fVeryVerbose = 0;    // verbose flag
120 121 122 123
}

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

124
  Synopsis    [Computes TFO and window roots for all nodes.]
125

126 127 128
  Description [TFO does not include the node itself. If TFO is empty,
  it means that the node itself is its own root, which may happen if
  the node is pointed by a PO or if it has too many fanouts.]
129 130 131 132 133 134 135 136 137 138 139
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Wec_t * Sbd_ManWindowRoots( Gia_Man_t * p, int nTfoLevels, int nTfoFanMax )
{
    Vec_Wec_t * vTfos = Vec_WecStart( Gia_ManObjNum(p) ); // TFO nodes with roots marked
    Vec_Wec_t * vTemp = Vec_WecStart( Gia_ManObjNum(p) ); // storage
    Vec_Int_t * vNodes, * vNodes0, * vNodes1;
140
    Vec_Bit_t * vPoDrivers = Vec_BitStart( Gia_ManObjNum(p) );
141 142 143 144 145 146 147 148 149 150
    int i, k, k2, Id, Fan;
    Gia_ManLevelNum( p );
    Gia_ManCreateRefs( p );
    Gia_ManCleanMark0( p );
    Gia_ManForEachCiId( p, Id, i )
    {
        vNodes = Vec_WecEntry( vTemp, Id );
        Vec_IntGrow( vNodes, 1 );
        Vec_IntPush( vNodes, Id );
    }
151 152
    Gia_ManForEachCoDriverId( p, Id, i )
        Vec_BitWriteEntry( vPoDrivers, Id, 1 );
153 154
    Gia_ManForEachAndId( p, Id )
    {
155
        int fAlwaysRoot = Vec_BitEntry(vPoDrivers, Id) || (Gia_ObjRefNumId(p, Id) >= nTfoFanMax);
156 157 158
        vNodes0 = Vec_WecEntry( vTemp, Gia_ObjFaninId0(Gia_ManObj(p, Id), Id) );
        vNodes1 = Vec_WecEntry( vTemp, Gia_ObjFaninId1(Gia_ManObj(p, Id), Id) );
        vNodes = Vec_WecEntry( vTemp, Id );
159
        Vec_IntTwoMerge2( vNodes0, vNodes1, vNodes );
160 161 162 163 164 165 166 167
        k2 = 0;
        Vec_IntForEachEntry( vNodes, Fan, k )
        {
            int fRoot = fAlwaysRoot || (Gia_ObjLevelId(p, Id) - Gia_ObjLevelId(p, Fan) >= nTfoLevels);
            Vec_WecPush( vTfos, Fan, Abc_Var2Lit(Id, fRoot) );
            if ( !fRoot ) Vec_IntWriteEntry( vNodes, k2++, Fan );
        }
        Vec_IntShrink( vNodes, k2 );
168
        if ( !fAlwaysRoot )
169
            Vec_IntPush( vNodes, Id );
170 171
    }
    Vec_WecFree( vTemp );
172 173
    Vec_BitFree( vPoDrivers );

174
    // print the results
175
    if ( 0 )
176 177 178 179 180 181 182 183 184
    Vec_WecForEachLevel( vTfos, vNodes, i )
    {
        if ( !Gia_ObjIsAnd(Gia_ManObj(p, i)) )
            continue;
        printf( "Node %3d : ", i );
        Vec_IntForEachEntry( vNodes, Fan, k )
            printf( "%d%s ", Abc_Lit2Var(Fan), Abc_LitIsCompl(Fan)? "*":"" );
        printf( "\n" );
    }
185

186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203
    return vTfos;
}

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

  Synopsis    [Manager manipulation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Sbd_Man_t * Sbd_ManStart( Gia_Man_t * pGia, Sbd_Par_t * pPars )
{
    int i, w, Id;
    Sbd_Man_t * p = ABC_CALLOC( Sbd_Man_t, 1 );  
204
    p->timeTotal  = Abc_Clock();
205 206 207 208 209 210
    p->pPars      = pPars;
    p->pGia       = pGia;
    p->vTfos      = Sbd_ManWindowRoots( pGia, pPars->nTfoLevels, pPars->nTfoFanMax );
    p->vLutLevs   = Vec_IntStart( Gia_ManObjNum(pGia) );
    p->vLutCuts   = Vec_IntStart( Gia_ManObjNum(pGia) * (p->pPars->nLutSize + 1) );
    p->vMirrors   = Vec_IntStartFull( Gia_ManObjNum(pGia) );
211
    for ( i = 0; i < 4; i++ )
212 213
        p->vSims[i] = Vec_WrdStart( Gia_ManObjNum(pGia) * p->pPars->nWords );
    // target node
214 215
    p->vCover     = Vec_IntAlloc( 100 );
    p->vLits      = Vec_IntAlloc( 100 );
216
    p->vLits2     = Vec_IntAlloc( 100 );
217 218 219
    p->vRoots     = Vec_IntAlloc( 100 );
    p->vWinObjs   = Vec_IntAlloc( Gia_ManObjNum(pGia) );
    p->vObj2Var   = Vec_IntStart( Gia_ManObjNum(pGia) );
220
    p->vDivSet    = Vec_IntAlloc( 100 );
221 222 223
    p->vDivVars   = Vec_IntAlloc( 100 );
    p->vDivValues = Vec_IntAlloc( 100 );
    p->vDivLevels = Vec_WecAlloc( 100 );
224 225
    p->vCounts[0] = Vec_IntAlloc( 100 );
    p->vCounts[1] = Vec_IntAlloc( 100 );
226
    p->vMatrix    = Vec_WrdAlloc( 100 );
227 228 229 230 231 232 233 234 235 236 237
    // start input cuts
    Gia_ManForEachCiId( pGia, Id, i )
    {
        int * pCut = Sbd_ObjCut( p, Id );
        pCut[0] = 1;
        pCut[1] = Id;
    }
    // generate random input
    Gia_ManRandom( 1 );
    Gia_ManForEachCiId( pGia, Id, i )
        for ( w = 0; w < p->pPars->nWords; w++ )
238
            Sbd_ObjSim0(p, Id)[w] = Gia_ManRandomW( 0 );     
239
    // cut enumeration
240 241 242 243 244 245 246
    if ( pPars->fMoreCuts )
        p->pSto = Sbd_StoAlloc( pGia, p->vMirrors, pPars->nLutSize, pPars->nCutSize, pPars->nCutNum, !pPars->fMapping, 1 );
    else
    {
        p->pSto = Sbd_StoAlloc( pGia, p->vMirrors, pPars->nLutSize, pPars->nLutSize, pPars->nCutNum, !pPars->fMapping, 1 );
        p->pSrv = Sbd_ManCutServerStart( pGia, p->vMirrors, p->vLutLevs, NULL, NULL, pPars->nLutSize, pPars->nCutSize, pPars->nCutNum, 0 );
    }
247 248 249 250 251 252 253 254 255
    return p;
}
void Sbd_ManStop( Sbd_Man_t * p )
{
    int i;
    Vec_WecFree( p->vTfos );
    Vec_IntFree( p->vLutLevs );
    Vec_IntFree( p->vLutCuts );
    Vec_IntFree( p->vMirrors );
256
    for ( i = 0; i < 4; i++ )
257
        Vec_WrdFree( p->vSims[i] );
258 259
    Vec_IntFree( p->vCover );
    Vec_IntFree( p->vLits );
260
    Vec_IntFree( p->vLits2 );
261 262 263
    Vec_IntFree( p->vRoots );
    Vec_IntFree( p->vWinObjs );
    Vec_IntFree( p->vObj2Var );
264
    Vec_IntFree( p->vDivSet );
265 266 267
    Vec_IntFree( p->vDivVars );
    Vec_IntFree( p->vDivValues );
    Vec_WecFree( p->vDivLevels );
268 269
    Vec_IntFree( p->vCounts[0] );
    Vec_IntFree( p->vCounts[1] );
270
    Vec_WrdFree( p->vMatrix );
271
    sat_solver_delete_p( &p->pSat );
272 273
    if ( p->pSto ) Sbd_StoFree( p->pSto );
    if ( p->pSrv ) Sbd_ManCutServerStop( p->pSrv );
274
    ABC_FREE( p );
275 276 277 278 279 280 281 282 283 284 285 286 287 288
}


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

  Synopsis    [Constructing window.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
289
void Sbd_ManPropagateControlOne( Sbd_Man_t * p, int Node )
290
{
291
    Gia_Obj_t * pNode = Gia_ManObj(p->pGia, Node);  int w;
292 293
    int iObj0 = Gia_ObjFaninId0(pNode, Node);
    int iObj1 = Gia_ObjFaninId1(pNode, Node);
294

295 296 297
//    word * pSims  = Sbd_ObjSim0(p, Node);
//    word * pSims0 = Sbd_ObjSim0(p, iObj0);
//    word * pSims1 = Sbd_ObjSim0(p, iObj1);
298 299 300 301 302 303 304 305 306

    word * pCtrl  = Sbd_ObjSim2(p, Node);
    word * pCtrl0 = Sbd_ObjSim2(p, iObj0);
    word * pCtrl1 = Sbd_ObjSim2(p, iObj1);

    word * pDtrl  = Sbd_ObjSim3(p, Node);
    word * pDtrl0 = Sbd_ObjSim3(p, iObj0);
    word * pDtrl1 = Sbd_ObjSim3(p, iObj1);

307 308 309
//    Gia_ObjPrint( p->pGia, pNode );
//    printf( "Node %2d : %d %d\n\n", Node, (int)(pSims[0] & 1), (int)(pCtrl[0] & 1) );

310 311
    for ( w = 0; w < p->pPars->nWords; w++ )
    {
312 313
//        word Sim0 = Gia_ObjFaninC0(pNode) ? ~pSims0[w] : pSims0[w];
//        word Sim1 = Gia_ObjFaninC1(pNode) ? ~pSims1[w] : pSims1[w];
314

315 316
        pCtrl0[w] |= pCtrl[w];// & (pSims[w] | Sim1 | (~Sim0 & ~Sim1));
        pCtrl1[w] |= pCtrl[w];// & (pSims[w] | Sim0 | (~Sim0 & ~Sim1));
317

318 319
        pDtrl0[w] |= pDtrl[w];// & (pSims[w] | Sim1 | (~Sim0 & ~Sim1));
        pDtrl1[w] |= pDtrl[w];// & (pSims[w] | Sim0 | (~Sim0 & ~Sim1));
320 321
    }
}
322 323
void Sbd_ManPropagateControl( Sbd_Man_t * p, int Pivot )
{
324
    abctime clk = Abc_Clock();
325 326 327 328 329 330 331 332 333 334 335 336 337
    int i, Node;
    Abc_TtCopy( Sbd_ObjSim3(p, Pivot), Sbd_ObjSim2(p, Pivot), p->pPars->nWords, 0 );
    // clean controlability
    for ( i = 0; i < Vec_IntEntry(p->vObj2Var, Pivot) && ((Node = Vec_IntEntry(p->vWinObjs, i)), 1); i++ )
    {
        Abc_TtClear( Sbd_ObjSim2(p, Node), p->pPars->nWords );
        Abc_TtClear( Sbd_ObjSim3(p, Node), p->pPars->nWords );
        //printf( "Clearing node %d.\n", Node );
    }
    // propagate controlability to fanins for the TFI nodes starting from the pivot
    for ( i = Vec_IntEntry(p->vObj2Var, Pivot); i >= 0 && ((Node = Vec_IntEntry(p->vWinObjs, i)), 1); i-- )
        if ( Gia_ObjIsAnd(Gia_ManObj(p->pGia, Node)) )
            Sbd_ManPropagateControlOne( p, Node );
338
    p->timeWin += Abc_Clock() - clk;
339
}
340 341 342 343
void Sbd_ManUpdateOrder( Sbd_Man_t * p, int Pivot )
{
    int i, k, Node;
    Vec_Int_t * vLevel;
344
    int nTimeValidDivs = 0;
345 346 347 348 349 350 351 352 353 354
    // collect divisors by logic level
    int LevelMax = Vec_IntEntry(p->vLutLevs, Pivot);
    Vec_WecClear( p->vDivLevels );
    Vec_WecInit( p->vDivLevels, LevelMax + 1 );
    Vec_IntForEachEntry( p->vWinObjs, Node, i )
        Vec_WecPush( p->vDivLevels, Vec_IntEntry(p->vLutLevs, Node), Node );
    // reload divisors
    Vec_IntClear( p->vWinObjs );
    Vec_WecForEachLevel( p->vDivLevels, vLevel, i )
    {
355
        Vec_IntSort( vLevel, 0 );
356 357 358 359 360
        Vec_IntForEachEntry( vLevel, Node, k )
        {
            Vec_IntWriteEntry( p->vObj2Var, Node, Vec_IntSize(p->vWinObjs) );
            Vec_IntPush( p->vWinObjs, Node );
        }
361
        // remember divisor cutoff
362
        if ( i == LevelMax - 2 )
363
            nTimeValidDivs = Vec_IntSize(p->vWinObjs);
364
    }
365
    assert( nTimeValidDivs > 0 );
366 367 368 369 370 371 372 373 374 375 376
    Vec_IntClear( p->vDivVars );
    p->DivCutoff = -1;
    Vec_IntForEachEntryStartStop( p->vWinObjs, Node, i, Abc_MaxInt(0, nTimeValidDivs-63), nTimeValidDivs )
    {
        if ( p->DivCutoff == -1 && Vec_IntEntry(p->vLutLevs, Node) == LevelMax - 2 )
            p->DivCutoff = Vec_IntSize(p->vDivVars);
        Vec_IntPush( p->vDivVars, i );
    }
    if ( p->DivCutoff == -1 )
        p->DivCutoff = 0;
    // verify
377
/*
378 379 380 381 382
    assert( Vec_IntSize(p->vDivVars) < 64 );
    Vec_IntForEachEntryStart( p->vDivVars, Node, i, p->DivCutoff )
        assert( Vec_IntEntry(p->vLutLevs, Vec_IntEntry(p->vWinObjs, Node)) == LevelMax - 2 );
    Vec_IntForEachEntryStop( p->vDivVars, Node, i, p->DivCutoff )
        assert( Vec_IntEntry(p->vLutLevs, Vec_IntEntry(p->vWinObjs, Node)) < LevelMax - 2 );
383
*/
384
    Vec_IntFill( p->vDivValues, Vec_IntSize(p->vDivVars), 0 );
385 386 387
    //printf( "%d ", Vec_IntSize(p->vDivVars) );
//    printf( "Node %4d :  Win = %5d.   Divs = %5d.    D1 = %5d.  D2 = %5d.\n",  
//        Pivot, Vec_IntSize(p->vWinObjs), Vec_IntSize(p->vDivVars), Vec_IntSize(p->vDivVars)-p->DivCutoff, p->DivCutoff );
388
}
389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444
void Sbd_ManWindowSim_rec( Sbd_Man_t * p, int NodeInit )
{
    Gia_Obj_t * pObj;
    int Node = NodeInit;
    if ( Vec_IntEntry(p->vMirrors, Node) >= 0 )
        Node = Abc_Lit2Var( Vec_IntEntry(p->vMirrors, Node) );
    if ( Gia_ObjIsTravIdCurrentId(p->pGia, Node) )
        return;
    Gia_ObjSetTravIdCurrentId(p->pGia, Node);
    pObj = Gia_ManObj( p->pGia, Node );
    if ( Gia_ObjIsAnd(pObj) )
    {
        Sbd_ManWindowSim_rec( p, Gia_ObjFaninId0(pObj, Node) );
        Sbd_ManWindowSim_rec( p, Gia_ObjFaninId1(pObj, Node) );
    }
    if ( !pObj->fMark0 )
    {
        Vec_IntWriteEntry( p->vObj2Var, Node, Vec_IntSize(p->vWinObjs) );
        Vec_IntPush( p->vWinObjs, Node );
    }
    if ( Gia_ObjIsCi(pObj) )
        return;
    // simulate
    assert( Gia_ObjIsAnd(pObj) );
    if ( Gia_ObjIsXor(pObj) )
    {
        Abc_TtXor( Sbd_ObjSim0(p, Node), 
            Sbd_ObjSim0(p, Gia_ObjFaninId0(pObj, Node)), 
            Sbd_ObjSim0(p, Gia_ObjFaninId1(pObj, Node)), 
            p->pPars->nWords, 
            Gia_ObjFaninC0(pObj) ^ Gia_ObjFaninC1(pObj) );

        if ( pObj->fMark0 )
            Abc_TtXor( Sbd_ObjSim1(p, Node), 
                Gia_ObjFanin0(pObj)->fMark0 ? Sbd_ObjSim1(p, Gia_ObjFaninId0(pObj, Node)) : Sbd_ObjSim0(p, Gia_ObjFaninId0(pObj, Node)), 
                Gia_ObjFanin1(pObj)->fMark0 ? Sbd_ObjSim1(p, Gia_ObjFaninId1(pObj, Node)) : Sbd_ObjSim0(p, Gia_ObjFaninId1(pObj, Node)), 
                p->pPars->nWords, 
                Gia_ObjFaninC0(pObj) ^ Gia_ObjFaninC1(pObj) );
    }
    else
    {
        Abc_TtAndCompl( Sbd_ObjSim0(p, Node), 
            Sbd_ObjSim0(p, Gia_ObjFaninId0(pObj, Node)), Gia_ObjFaninC0(pObj), 
            Sbd_ObjSim0(p, Gia_ObjFaninId1(pObj, Node)), Gia_ObjFaninC1(pObj), 
            p->pPars->nWords );

        if ( pObj->fMark0 )
            Abc_TtAndCompl( Sbd_ObjSim1(p, Node), 
                Gia_ObjFanin0(pObj)->fMark0 ? Sbd_ObjSim1(p, Gia_ObjFaninId0(pObj, Node)) : Sbd_ObjSim0(p, Gia_ObjFaninId0(pObj, Node)), Gia_ObjFaninC0(pObj), 
                Gia_ObjFanin1(pObj)->fMark0 ? Sbd_ObjSim1(p, Gia_ObjFaninId1(pObj, Node)) : Sbd_ObjSim0(p, Gia_ObjFaninId1(pObj, Node)), Gia_ObjFaninC1(pObj), 
                p->pPars->nWords );
    }
    if ( Node != NodeInit )
        Abc_TtCopy( Sbd_ObjSim0(p, NodeInit), Sbd_ObjSim0(p, Node), p->pPars->nWords, Abc_LitIsCompl(Vec_IntEntry(p->vMirrors, NodeInit)) );
}
int Sbd_ManWindow( Sbd_Man_t * p, int Pivot )
445
{
446
    abctime clk = Abc_Clock();
447 448 449 450
    int i, Node;
    // assign pivot and TFO (assume siminfo is assigned at the PIs)
    p->Pivot = Pivot;
    p->vTfo = Vec_WecEntry( p->vTfos, Pivot );
451
    // add constant node
452
    Vec_IntClear( p->vWinObjs );
453 454
    Vec_IntWriteEntry( p->vObj2Var, 0, Vec_IntSize(p->vWinObjs) );
    Vec_IntPush( p->vWinObjs, 0 );
455
    // simulate TFI cone
456
    Gia_ManIncrementTravId( p->pGia );
457
    Gia_ObjSetTravIdCurrentId(p->pGia, 0);
458
    Sbd_ManWindowSim_rec( p, Pivot );
459
    if ( p->pPars->nWinSizeMax && Vec_IntSize(p->vWinObjs) > p->pPars->nWinSizeMax )
460 461
    {
        p->timeWin += Abc_Clock() - clk;
462
        return 0;
463
    }
464
    Sbd_ManUpdateOrder( p, Pivot );
465 466
    assert( Vec_IntSize(p->vDivVars) == Vec_IntSize(p->vDivValues) );
    assert( Vec_IntSize(p->vDivVars) < Vec_IntSize(p->vWinObjs) );
467 468 469
    // simulate node
    Gia_ManObj(p->pGia, Pivot)->fMark0 = 1;
    Abc_TtCopy( Sbd_ObjSim1(p, Pivot), Sbd_ObjSim0(p, Pivot), p->pPars->nWords, 1 );
470 471
    // mark TFO and simulate extended TFI without adding TFO nodes
    Vec_IntClear( p->vRoots );
472 473 474
    Vec_IntForEachEntry( p->vTfo, Node, i )
    {
        Gia_ManObj(p->pGia, Abc_Lit2Var(Node))->fMark0 = 1;
475 476 477 478
        if ( !Abc_LitIsCompl(Node) ) 
            continue;
        Sbd_ManWindowSim_rec( p, Abc_Lit2Var(Node) );
        Vec_IntPush( p->vRoots, Abc_Lit2Var(Node) );
479
    }
480
    // add TFO nodes and remove marks
481 482
    Gia_ManObj(p->pGia, Pivot)->fMark0 = 0;
    Vec_IntForEachEntry( p->vTfo, Node, i )
483
    {
484
        Gia_ManObj(p->pGia, Abc_Lit2Var(Node))->fMark0 = 0;
485 486 487
        Vec_IntWriteEntry( p->vObj2Var, Abc_Lit2Var(Node), Vec_IntSize(p->vWinObjs) );
        Vec_IntPush( p->vWinObjs, Abc_Lit2Var(Node) );
    }
488
    if ( p->pPars->nWinSizeMax && Vec_IntSize(p->vWinObjs) > p->pPars->nWinSizeMax )
489 490
    {
        p->timeWin += Abc_Clock() - clk;
491
        return 0;
492
    }
493
    // compute controlability for node
494 495 496 497
    if ( Vec_IntSize(p->vTfo) == 0 )
        Abc_TtFill( Sbd_ObjSim2(p, Pivot), p->pPars->nWords );
    else
        Abc_TtClear( Sbd_ObjSim2(p, Pivot), p->pPars->nWords );
498 499
    Vec_IntForEachEntry( p->vTfo, Node, i )
        if ( Abc_LitIsCompl(Node) ) // root
500
            Abc_TtOrXor( Sbd_ObjSim2(p, Pivot), Sbd_ObjSim0(p, Abc_Lit2Var(Node)), Sbd_ObjSim1(p, Abc_Lit2Var(Node)), p->pPars->nWords );
501
    p->timeWin += Abc_Clock() - clk;
502
    // propagate controlability to fanins for the TFI nodes starting from the pivot
503
    Sbd_ManPropagateControl( p, Pivot );
504
    assert( Vec_IntSize(p->vDivValues) <= 64 );
505
    return (int)(Vec_IntSize(p->vDivValues) <= 64);
506 507 508 509 510 511 512 513 514 515 516 517 518 519 520
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sbd_ManCheckConst( Sbd_Man_t * p, int Pivot )
{
521
    int nMintCount = 1;
522 523 524 525 526
    Vec_Ptr_t * vSims;
    word * pSims = Sbd_ObjSim0( p, Pivot );
    word * pCtrl = Sbd_ObjSim2( p, Pivot );
    int PivotVar = Vec_IntEntry(p->vObj2Var, Pivot);
    int RetValue, i, iObj, Ind, fFindOnset, nCares[2] = {0};
527

528
    abctime clk = Abc_Clock();
529
    p->pSat = Sbd_ManSatSolver( p->pSat, p->pGia, p->vMirrors, Pivot, p->vWinObjs, p->vObj2Var, p->vTfo, p->vRoots, 0 );
530
    p->timeCnf += Abc_Clock() - clk;
531 532
    if ( p->pSat == NULL )
    {
533 534
        //if ( p->pPars->fVerbose )
        //    printf( "Found stuck-at-%d node %d.\n", 0, Pivot );
535
        Vec_IntWriteEntry( p->vLutLevs, Pivot, 0 );
536
        p->nLuts[0]++;
537 538
        return 0;
    }
539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555
    //return -1;
    //Sbd_ManPrintObj( p, Pivot );

    // count the number of on-set and off-set care-set minterms
    Vec_IntClear( p->vLits );
    for ( i = 0; i < 64; i++ )
        if ( Abc_TtGetBit(pCtrl, i) )
            nCares[Abc_TtGetBit(pSims, i)]++;
        else
            Vec_IntPush( p->vLits, i );
    fFindOnset = (int)(nCares[0] < nCares[1]);
    if ( nCares[0] >= nMintCount && nCares[1] >= nMintCount )
        return -1;
    // find how many do we need
    nCares[0] = nCares[0] < nMintCount ? nMintCount - nCares[0] : 0;
    nCares[1] = nCares[1] < nMintCount ? nMintCount - nCares[1] : 0;

556
    if ( p->pPars->fVeryVerbose )
557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594
        printf( "Computing %d offset and %d onset minterms for node %d.\n", nCares[0], nCares[1], Pivot );

    if ( Vec_IntSize(p->vLits) >= nCares[0] + nCares[1] )
        Vec_IntShrink( p->vLits, nCares[0] + nCares[1] );
    else
    {
        // collect places to insert new minterms
        for ( i = 0; i < 64 && Vec_IntSize(p->vLits) < nCares[0] + nCares[1]; i++ )
            if ( fFindOnset == Abc_TtGetBit(pSims, i) )
                Vec_IntPush( p->vLits, i );
    }
    // collect simulation pointers
    vSims = Vec_PtrAlloc( PivotVar + 1 );
    Vec_IntForEachEntry( p->vWinObjs, iObj, i )
    {
        Vec_PtrPush( vSims, Sbd_ObjSim0(p, iObj) );
        if ( iObj == Pivot )
            break;
    }
    assert( i == PivotVar );
    // compute patterns
    RetValue = Sbd_ManCollectConstants( p->pSat, nCares, PivotVar, (word **)Vec_PtrArray(vSims), p->vLits );
    // print computed miterms
    if ( 0 && RetValue < 0 )
    {
        Vec_Int_t * vPis = Vec_WecEntry(p->vDivLevels, 0);
        int i, k, Ind;
        printf( "Additional minterms:\n" );
        Vec_IntForEachEntry( p->vLits, Ind, k )
        {
            for ( i = 0; i < Vec_IntSize(vPis); i++ )
                printf( "%d", Abc_TtGetBit( (word *)Vec_PtrEntry(vSims, Vec_IntEntry(p->vWinObjs, i)), Ind ) );
            printf( "\n" );
        }
    }
    Vec_PtrFree( vSims );
    if ( RetValue >= 0 )
    {
595
        if ( p->pPars->fVeryVerbose )
596
            printf( "Found stuck-at-%d node %d.\n", RetValue, Pivot );
597
        Vec_IntWriteEntry( p->vLutLevs, Pivot, 0 );
598
        p->nLuts[0]++;
599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645
        return RetValue;
    }
    // set controlability of these minterms
    Vec_IntForEachEntry( p->vLits, Ind, i )
        Abc_TtSetBit( pCtrl, Ind );
    // propagate controlability to fanins for the TFI nodes starting from the pivot
    Sbd_ManPropagateControl( p, Pivot );
    // double check that we now have enough minterms
    for ( i = 0; i < 64; i++ )
        if ( Abc_TtGetBit(pCtrl, i) )
            nCares[Abc_TtGetBit(pSims, i)]++;
    assert( nCares[0] >= nMintCount && nCares[1] >= nMintCount );
    return -1;
}

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

  Synopsis    [Transposing 64-bit matrix.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Sbd_TransposeMatrix64( word A[64] )
{
    int j, k;
    word t, m = 0x00000000FFFFFFFF;
    for ( j = 32; j != 0; j = j >> 1, m = m ^ (m << j) )
    {
        for ( k = 0; k < 64; k = (k + j + 1) & ~j )
        {
            t = (A[k] ^ (A[k+j] >> j)) & m;
            A[k] = A[k] ^ t;
            A[k+j] = A[k+j] ^ (t << j);
        }
    }
}
static inline void Sbd_PrintMatrix64( word A[64] )
{
    int j, k;
    for ( j = 0; j < 64; j++, printf("\n") )
    for ( k = 0; k < 64; k++ )
        printf( "%d", (int)((A[j] >> k) & 1) );
    printf( "\n" );
646 647 648 649 650 651 652 653 654 655 656 657 658 659 660
}

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

  Synopsis    [Profiling divisor candidates.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sbd_ManPrintObj( Sbd_Man_t * p, int Pivot )
{
661
    int nDivs = Vec_IntEntry(p->vObj2Var, Pivot) + 1;
662
    int i, k, k0, k1, Id, Bit0, Bit1;
663 664

    Vec_IntForEachEntryStop( p->vWinObjs, Id, i, nDivs )
665
        printf( "%3d : ", Id ), Extra_PrintBinary( stdout, (unsigned *)Sbd_ObjSim0(p, Id), 64 ), printf( "\n" );
666

667 668 669
    assert( p->Pivot == Pivot );
    Vec_IntClear( p->vCounts[0] );
    Vec_IntClear( p->vCounts[1] );
670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716

    printf( "Node %d.  Useful divisors = %d.\n", Pivot, Vec_IntSize(p->vDivValues) );
    printf( "Lev : " );
    Vec_IntForEachEntryStop( p->vWinObjs, Id, i, nDivs )
    {
        if ( i == nDivs-1 )
            printf( " " );
        printf( "%d", Vec_IntEntry(p->vLutLevs, Id) );
    }
    printf( "\n" );
    printf( "\n" );

    if ( nDivs > 99 )
    {
        printf( "    : " );
        Vec_IntForEachEntryStop( p->vWinObjs, Id, i, nDivs )
        {
            if ( i == nDivs-1 )
                printf( " " );
            printf( "%d", Id / 100 );
        }
        printf( "\n" );
    }
    if ( nDivs > 9 )
    {
        printf( "    : " );
        Vec_IntForEachEntryStop( p->vWinObjs, Id, i, nDivs )
        {
            if ( i == nDivs-1 )
                printf( " " );
            printf( "%d", (Id % 100) / 10 );
        }
        printf( "\n" );
    }
    if ( nDivs > 0 )
    {
        printf( "    : " );
        Vec_IntForEachEntryStop( p->vWinObjs, Id, i, nDivs )
        {
            if ( i == nDivs-1 )
                printf( " " );
            printf( "%d", Id % 10 );
        }
        printf( "\n" );
        printf( "\n" );
    }

717 718 719
    // sampling matrix
    for ( k = 0; k < p->pPars->nWords * 64; k++ )
    {
720 721 722
        if ( !Abc_TtGetBit(Sbd_ObjSim2(p, Pivot), k) )
            continue;

723
        printf( "%3d : ", k );
724
        Vec_IntForEachEntryStop( p->vWinObjs, Id, i, nDivs )
725 726 727
        {
            word * pSims = Sbd_ObjSim0( p, Id );
            word * pCtrl = Sbd_ObjSim2( p, Id );
728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743
            if ( i == nDivs-1 )
            {
                if ( Abc_TtGetBit(pCtrl, k) )
                    Vec_IntPush( p->vCounts[Abc_TtGetBit(pSims, k)], k );
                printf( " " );
            }
            printf( "%c", Abc_TtGetBit(pCtrl, k) ? '0' + Abc_TtGetBit(pSims, k) : '.' );
        }
        printf( "\n" );

        printf( "%3d : ", k );
        Vec_IntForEachEntryStop( p->vWinObjs, Id, i, nDivs )
        {
            word * pSims = Sbd_ObjSim0( p, Id );
            word * pCtrl = Sbd_ObjSim3( p, Id );
            if ( i == nDivs-1 )
744 745 746 747 748 749 750 751
            {
                if ( Abc_TtGetBit(pCtrl, k) )
                    Vec_IntPush( p->vCounts[Abc_TtGetBit(pSims, k)], k );
                printf( " " );
            }
            printf( "%c", Abc_TtGetBit(pCtrl, k) ? '0' + Abc_TtGetBit(pSims, k) : '.' );
        }
        printf( "\n" );
752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776

        printf( "Sims: " );
        Vec_IntForEachEntryStop( p->vWinObjs, Id, i, nDivs )
        {
            word * pSims = Sbd_ObjSim0( p, Id );
            //word * pCtrl = Sbd_ObjSim2( p, Id );
            if ( i == nDivs-1 )
                printf( " " );
            printf( "%c", '0' + Abc_TtGetBit(pSims, k) );
        }
        printf( "\n" );

        printf( "Ctrl: " );
        Vec_IntForEachEntryStop( p->vWinObjs, Id, i, nDivs )
        {
            //word * pSims = Sbd_ObjSim0( p, Id );
            word * pCtrl = Sbd_ObjSim2( p, Id );
            if ( i == nDivs-1 )
                printf( " " );
            printf( "%c", '0' + Abc_TtGetBit(pCtrl, k) );
        }
        printf( "\n" );


        printf( "\n" );
777 778 779
    }
    // covering table
    printf( "Exploring %d x %d covering table.\n", Vec_IntSize(p->vCounts[0]), Vec_IntSize(p->vCounts[1]) );
780 781 782
/*
    Vec_IntForEachEntryStop( p->vCounts[0], Bit0, k0, Abc_MinInt(Vec_IntSize(p->vCounts[0]), 8) )
    Vec_IntForEachEntryStop( p->vCounts[1], Bit1, k1, Abc_MinInt(Vec_IntSize(p->vCounts[1]), 8) )
783 784
    {
        printf( "%3d %3d : ", Bit0, Bit1 );
785
        Vec_IntForEachEntryStop( p->vWinObjs, Id, i, nDivs )
786 787 788
        {
            word * pSims = Sbd_ObjSim0( p, Id );
            word * pCtrl = Sbd_ObjSim2( p, Id );
789
            if ( i == nDivs-1 )
790 791 792 793 794
                printf( " " );
            printf( "%c", (Abc_TtGetBit(pCtrl, Bit0) && Abc_TtGetBit(pCtrl, Bit1) && Abc_TtGetBit(pSims, Bit0) != Abc_TtGetBit(pSims, Bit1)) ? '1' : '.' );
        }
        printf( "\n" );
    }
795 796 797 798 799 800 801 802 803 804 805 806 807
*/
    Vec_WrdClear( p->vMatrix );
    Vec_IntForEachEntryStop( p->vCounts[0], Bit0, k0, Abc_MinInt(Vec_IntSize(p->vCounts[0]), 64) )
    Vec_IntForEachEntryStop( p->vCounts[1], Bit1, k1, Abc_MinInt(Vec_IntSize(p->vCounts[1]), 64) )
    {
        word Row = 0;
        Vec_IntForEachEntryStop( p->vWinObjs, Id, i, nDivs )
        {
            word * pSims = Sbd_ObjSim0( p, Id );
            word * pCtrl = Sbd_ObjSim2( p, Id );
            if ( Abc_TtGetBit(pCtrl, Bit0) && Abc_TtGetBit(pCtrl, Bit1) && Abc_TtGetBit(pSims, Bit0) != Abc_TtGetBit(pSims, Bit1) )
                Abc_TtXorBit( &Row, i );
        }
808 809 810 811 812
        if ( Vec_WrdPushUnique( p->vMatrix, Row ) )
            continue;
        for ( i = 0; i < nDivs; i++ )
            printf( "%d", (int)((Row >> i) & 1) );
        printf( "\n" );
813
    }
814
}
815

816
void Sbd_ManMatrPrint( Sbd_Man_t * p, word Cover[], int nCol, int nRows )
817 818 819 820 821
{
    int i, k;
    for ( i = 0; i <= nCol; i++ )
    {
        printf( "%2d : ", i );
822
        printf( "%d ", i == nCol ? Vec_IntEntry(p->vLutLevs, p->Pivot) : Vec_IntEntry(p->vLutLevs, Vec_IntEntry(p->vWinObjs, Vec_IntEntry(p->vDivVars, i))) );
823
        for ( k = 0; k < nRows; k++ )
824
            printf( "%d", (int)((Cover[i] >> k) & 1) );
825 826 827 828 829 830 831 832 833 834 835 836 837 838 839
        printf( "\n"); 
    }
    printf( "\n");
}
static inline void Sbd_ManCoverReverseOrder( word Cover[64] )
{
    int i;
    for ( i = 0; i < 32; i++ )
    {
        word Cube = Cover[i];
        Cover[i] = Cover[63-i]; 
        Cover[63-i] = Cube;
    }
}

840
static inline int Sbd_ManAddCube1( int nRowLimit, word Cover[], int nRows, word Cube )
841 842 843 844 845
{
    int n, m;
    if ( 0 )
    {
        printf( "Adding cube: " );
846
        for ( n = 0; n < nRowLimit; n++ )
847 848 849 850
            printf( "%d", (int)((Cube >> n) & 1) );
        printf( "\n" );
    }
    // do not add contained Cube
851
    assert( nRows <= nRowLimit );
852 853 854 855 856 857 858
    for ( n = 0; n < nRows; n++ )
        if ( (Cover[n] & Cube) == Cover[n] ) // Cube is contained
            return nRows;
    // remove rows contained by Cube
    for ( n = m = 0; n < nRows; n++ )
        if ( (Cover[n] & Cube) != Cube ) // Cover[n] is not contained
            Cover[m++] = Cover[n];
859
    if ( m < nRowLimit )
860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893
        Cover[m++] = Cube;
    for ( n = m; n < nRows; n++ )
        Cover[n] = 0;
    nRows = m;
    return nRows;
}
static inline int Sbd_ManAddCube2( word Cover[2][64], int nRows, word Cube[2] )
{
    int n, m;
    // do not add contained Cube
    assert( nRows <= 64 );
    for ( n = 0; n < nRows; n++ )
        if ( (Cover[0][n] & Cube[0]) == Cover[0][n] && (Cover[1][n] & Cube[1]) == Cover[1][n] ) // Cube is contained
            return nRows;
    // remove rows contained by Cube
    for ( n = m = 0; n < nRows; n++ )
        if ( (Cover[0][n] & Cube[0]) != Cube[0] || (Cover[1][n] & Cube[1]) != Cube[1] ) // Cover[n] is not contained
        {
            Cover[0][m] = Cover[0][n];
            Cover[1][m] = Cover[1][n];
            m++;
        }
    if ( m < 64 )
    {
        Cover[0][m] = Cube[0];
        Cover[1][m] = Cube[1];
        m++;
    }
    for ( n = m; n < nRows; n++ )
        Cover[0][n] = Cover[1][n] = 0;
    nRows = m;
    return nRows;
}

894
static inline int Sbd_ManFindCandsSimple( Sbd_Man_t * p, word Cover[], int nDivs )
895 896 897
{
    int c0, c1, c2, c3;
    word Target = Cover[nDivs];
898
    Vec_IntClear( p->vDivSet );
899 900 901
    for ( c0 = 0;    c0 < nDivs; c0++ )
        if ( Cover[c0] == Target )
        {
902
            Vec_IntPush( p->vDivSet, c0 );
903 904 905 906 907 908 909
            return 1;
        }

    for ( c0 = 0;    c0 < nDivs; c0++ )
    for ( c1 = c0+1; c1 < nDivs; c1++ )
        if ( (Cover[c0] | Cover[c1]) == Target )
        {
910 911
            Vec_IntPush( p->vDivSet, c0 );
            Vec_IntPush( p->vDivSet, c1 );
912 913 914 915 916 917 918 919
            return 1;
        }

    for ( c0 = 0;    c0 < nDivs; c0++ )
    for ( c1 = c0+1; c1 < nDivs; c1++ )
    for ( c2 = c1+1; c2 < nDivs; c2++ )
        if ( (Cover[c0] | Cover[c1] | Cover[c2]) == Target )
        {
920 921 922
            Vec_IntPush( p->vDivSet, c0 );
            Vec_IntPush( p->vDivSet, c1 );
            Vec_IntPush( p->vDivSet, c2 );
923 924 925 926 927 928 929 930 931 932
            return 1;
        }

    for ( c0 = 0;    c0 < nDivs; c0++ )
    for ( c1 = c0+1; c1 < nDivs; c1++ )
    for ( c2 = c1+1; c2 < nDivs; c2++ )
    for ( c3 = c2+1; c3 < nDivs; c3++ )
    {
        if ( (Cover[c0] | Cover[c1] | Cover[c2] | Cover[c3]) == Target )
        {
933 934 935 936
            Vec_IntPush( p->vDivSet, c0 );
            Vec_IntPush( p->vDivSet, c1 );
            Vec_IntPush( p->vDivSet, c2 );
            Vec_IntPush( p->vDivSet, c3 );
937 938 939 940 941
            return 1;
        }
    }
    return 0;
}
942

943 944 945 946 947 948 949 950 951 952
static inline int Sbd_ManFindCands( Sbd_Man_t * p, word Cover[64], int nDivs )
{
    int Ones[64], Order[64];
    int Limits[4] = { nDivs/4+1, nDivs/3+2, nDivs/2+3, nDivs };
    int c0, c1, c2, c3;
    word Target = Cover[nDivs];

    if ( nDivs < 8 || p->pPars->fCover )
        return Sbd_ManFindCandsSimple( p, Cover, nDivs );

953
    Vec_IntClear( p->vDivSet );
954 955 956
    for ( c0 = 0; c0 < nDivs; c0++ )
        if ( Cover[c0] == Target )
        {
957
            Vec_IntPush( p->vDivSet, c0 );
958 959 960 961 962 963 964
            return 1;
        }

    for ( c0 = 0;    c0 < nDivs; c0++ )
    for ( c1 = c0+1; c1 < nDivs; c1++ )
        if ( (Cover[c0] | Cover[c1]) == Target )
        {
965 966
            Vec_IntPush( p->vDivSet, c0 );
            Vec_IntPush( p->vDivSet, c1 );
967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984
            return 1;
        }

    // count ones
    for ( c0 = 0; c0 < nDivs; c0++ )
        Ones[c0] = Abc_TtCountOnes( Cover[c0] );

    // sort by the number of ones
    for ( c0 = 0; c0 < nDivs; c0++ )
        Order[c0] = c0;
    Vec_IntSelectSortCost2Reverse( Order, nDivs, Ones );

    // sort with limits
    for ( c0 = 0;    c0 < Limits[0]; c0++ )
    for ( c1 = c0+1; c1 < Limits[1]; c1++ )
    for ( c2 = c1+1; c2 < Limits[2]; c2++ )
        if ( (Cover[Order[c0]] | Cover[Order[c1]] | Cover[Order[c2]]) == Target )
        {
985 986 987
            Vec_IntPush( p->vDivSet, Order[c0] );
            Vec_IntPush( p->vDivSet, Order[c1] );
            Vec_IntPush( p->vDivSet, Order[c2] );
988 989 990 991 992 993 994 995 996 997
            return 1;
        }

    for ( c0 = 0;    c0 < Limits[0]; c0++ )
    for ( c1 = c0+1; c1 < Limits[1]; c1++ )
    for ( c2 = c1+1; c2 < Limits[2]; c2++ )
    for ( c3 = c2+1; c3 < Limits[3]; c3++ )
    {
        if ( (Cover[Order[c0]] | Cover[Order[c1]] | Cover[Order[c2]] | Cover[Order[c3]]) == Target )
        {
998 999 1000 1001
            Vec_IntPush( p->vDivSet, Order[c0] );
            Vec_IntPush( p->vDivSet, Order[c1] );
            Vec_IntPush( p->vDivSet, Order[c2] );
            Vec_IntPush( p->vDivSet, Order[c3] );
1002 1003 1004 1005 1006 1007 1008
            return 1;
        }
    }
    return 0;
}


1009
int Sbd_ManExplore( Sbd_Man_t * p, int Pivot, word * pTruth )
1010
{
1011
    int fVerbose = 0;
1012
    abctime clk;
1013
    int nIters, nItersMax = 32;
1014

1015
    word MatrS[64] = {0}, MatrC[2][64] = {{0}}, Cubes[2][2][64] = {{{0}}}, Cover[64] = {0}, Cube, CubeNew[2];
1016
    int i, k, n, Node, Index, nCubes[2] = {0}, nRows = 0, nRowsOld;
1017

1018
    int nDivs = Vec_IntSize(p->vDivValues);
1019 1020 1021 1022
    int PivotVar = Vec_IntEntry(p->vObj2Var, Pivot);
    int FreeVar = Vec_IntSize(p->vWinObjs) + Vec_IntSize(p->vTfo) + Vec_IntSize(p->vRoots);
    int RetValue = 0;

1023 1024 1025
    if ( p->pPars->fVerbose )
        printf( "Node %d.  Useful divisors = %d.\n", Pivot, nDivs );

1026 1027 1028 1029
    if ( fVerbose )
        Sbd_ManPrintObj( p, Pivot );

    // collect bit-matrices
1030
    Vec_IntForEachEntry( p->vDivVars, Node, i )
1031
    {
1032 1033 1034
        MatrS[63-i]    = *Sbd_ObjSim0( p, Vec_IntEntry(p->vWinObjs, Node) );
        MatrC[0][63-i] = *Sbd_ObjSim2( p, Vec_IntEntry(p->vWinObjs, Node) );
        MatrC[1][63-i] = *Sbd_ObjSim3( p, Vec_IntEntry(p->vWinObjs, Node) );
1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048
    }
    MatrS[63-i]    = *Sbd_ObjSim0( p, Pivot );
    MatrC[0][63-i] = *Sbd_ObjSim2( p, Pivot );
    MatrC[1][63-i] = *Sbd_ObjSim3( p, Pivot );

    //Sbd_PrintMatrix64( MatrS );
    Sbd_TransposeMatrix64( MatrS );
    Sbd_TransposeMatrix64( MatrC[0] );
    Sbd_TransposeMatrix64( MatrC[1] );
    //Sbd_PrintMatrix64( MatrS );

    // collect cubes
    for ( i = 0; i < 64; i++ )
    {
1049 1050
        assert( Abc_TtGetBit(&MatrC[0][i], nDivs) == Abc_TtGetBit(&MatrC[1][i], nDivs) );
        if ( !Abc_TtGetBit(&MatrC[0][i], nDivs) )
1051
            continue;
1052
        Index = Abc_TtGetBit(&MatrS[i], nDivs); // Index==0 offset; Index==1 onset
1053 1054 1055 1056 1057
        for ( n = 0; n < 2; n++ )
        {
            if ( n && MatrC[0][i] == MatrC[1][i] )
                continue;
            assert( MatrC[n][i] );
1058 1059 1060 1061
            CubeNew[0] = ~MatrS[i] & MatrC[n][i];
            CubeNew[1] =  MatrS[i] & MatrC[n][i];
            assert( CubeNew[0] || CubeNew[1] );
            nCubes[Index] = Sbd_ManAddCube2( Cubes[Index], nCubes[Index], CubeNew );
1062 1063 1064 1065 1066 1067
        }
    }

    if ( p->pPars->fVerbose )
        printf( "Generated matrix with %d x %d entries.\n", nCubes[0], nCubes[1] );

1068
    if ( p->pPars->fVerbose )
1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082
    for ( n = 0; n < 2; n++ )
    {
        printf( "%s:\n", n ? "Onset" : "Offset" );
        for ( i = 0; i < nCubes[n]; i++, printf( "\n" ) )
            for ( k = 0; k < 64; k++ )
                if ( Abc_TtGetBit(&Cubes[n][0][i], k) )
                    printf( "0" );
                else if ( Abc_TtGetBit(&Cubes[n][1][i], k) )
                    printf( "1" );
                else 
                    printf( "." );
        printf( "\n" );
    }

1083 1084 1085 1086
    // create covering table
    nRows = 0;
    for ( i = 0; i < nCubes[0] && nRows < 32; i++ )
    for ( k = 0; k < nCubes[1] && nRows < 32; k++ )
1087 1088 1089
    {
        Cube = (Cubes[0][1][i] & Cubes[1][0][k]) | (Cubes[0][0][i] & Cubes[1][1][k]);
        assert( Cube );
1090
        nRows = Sbd_ManAddCube1( 64, Cover, nRows, Cube );
1091 1092
    }

1093 1094
    Sbd_ManCoverReverseOrder( Cover );

1095 1096 1097
    if ( p->pPars->fVerbose )
        printf( "Generated cover with %d entries.\n", nRows );

1098
    //if ( p->pPars->fVerbose )
1099 1100
    //Sbd_PrintMatrix64( Cover );
    Sbd_TransposeMatrix64( Cover );
1101
    //if ( p->pPars->fVerbose )
1102 1103
    //Sbd_PrintMatrix64( Cover );

1104
    Sbd_ManCoverReverseOrder( Cover );
1105

1106 1107
    nRowsOld = nRows;
    for ( nIters = 0; nIters < nItersMax && nRows < 64; nIters++ )
1108 1109
    {
        if ( p->pPars->fVerbose )
1110
            Sbd_ManMatrPrint( p, Cover, nDivs, nRows );
1111

1112 1113 1114 1115 1116
        clk = Abc_Clock();
        if ( !Sbd_ManFindCands( p, Cover, nDivs ) )
        {
            if ( p->pPars->fVerbose )
                printf( "Cannot find a feasible cover.\n" );
1117
            p->timeCov += Abc_Clock() - clk;
1118 1119
            return RetValue;
        }
1120
        p->timeCov += Abc_Clock() - clk;
1121 1122
    
        if ( p->pPars->fVerbose )
1123
            printf( "Candidate support:  " ),
1124
            Vec_IntPrint( p->vDivSet );
1125 1126

        clk = Abc_Clock();
1127
        *pTruth = Sbd_ManSolve( p->pSat, PivotVar, FreeVar+nIters, p->vDivSet, p->vDivVars, p->vDivValues, p->vLits );
1128
        p->timeSat += Abc_Clock() - clk;
1129 1130 1131 1132

        if ( *pTruth == SBD_SAT_UNDEC )
            printf( "Node %d:  Undecided.\n", Pivot );
        else if ( *pTruth == SBD_SAT_SAT )
1133
        {
1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153
            if ( p->pPars->fVerbose )
            {
                int i;
                printf( "Node %d:  SAT.\n", Pivot );
                for ( i = 0; i < nDivs; i++ )
                    printf( "%d", i % 10 );
                printf( "\n" );
                for ( i = 0; i < nDivs; i++ )
                    printf( "%c", (Vec_IntEntry(p->vDivValues, i) & 0x4) ? '0' + (Vec_IntEntry(p->vDivValues, i) & 1) : 'x' );
                printf( "\n" );
                for ( i = 0; i < nDivs; i++ )
                    printf( "%c", (Vec_IntEntry(p->vDivValues, i) & 0x8) ? '0' + ((Vec_IntEntry(p->vDivValues, i) >> 1) & 1) : 'x' );
                printf( "\n" );
            }
            // add row to the covering table
            for ( i = 0; i < nDivs; i++ )
                if ( Vec_IntEntry(p->vDivValues, i) == 0xE || Vec_IntEntry(p->vDivValues, i) == 0xD )
                    Cover[i] |= ((word)1 << nRows);
            Cover[nDivs] |= ((word)1 << nRows);
            nRows++;
1154
        }
1155 1156 1157 1158 1159
        else
        {
            if ( p->pPars->fVerbose )
            {
                printf( "Node %d:  UNSAT.\n", Pivot );
1160
                Extra_PrintBinary( stdout, (unsigned *)pTruth, 1 << Vec_IntSize(p->vDivSet) ), printf( "\n" );
1161 1162 1163 1164 1165
            }
            RetValue = 1;
            break;
        }
        //break;
1166 1167
    }
    return RetValue;
1168 1169
}

1170
int Sbd_ManExplore2( Sbd_Man_t * p, int Pivot, word * pTruth )
1171
{
1172
    abctime clk;
1173
    word Onset[64] = {0}, Offset[64] = {0}, Cube;
1174
    word CoverRows[64] = {0}, CoverCols[64] = {0};
1175 1176 1177 1178 1179 1180 1181 1182 1183
    int nIters, nItersMax = 32;
    int i, k, nRows = 0;

    int PivotVar = Vec_IntEntry(p->vObj2Var, Pivot);
    int FreeVar = Vec_IntSize(p->vWinObjs) + Vec_IntSize(p->vTfo) + Vec_IntSize(p->vRoots);
    int nDivs = Vec_IntSize( p->vDivVars );
    int nConsts = 4;
    int RetValue;

1184 1185
    clk = Abc_Clock();
    //sat_solver_delete_p( &p->pSat );
1186 1187 1188 1189
    p->pSat = Sbd_ManSatSolver( p->pSat, p->pGia, p->vMirrors, Pivot, p->vWinObjs, p->vObj2Var, p->vTfo, p->vRoots, 0 );
    p->timeCnf += Abc_Clock() - clk;

    assert( nConsts <= 8 );
1190
    clk = Abc_Clock();
1191
    RetValue = Sbd_ManCollectConstantsNew( p->pSat, p->vDivVars, nConsts, PivotVar, Onset, Offset );
1192
    p->timeSat += Abc_Clock() - clk;
1193 1194
    if ( RetValue >= 0 )
    {
1195
        if ( p->pPars->fVeryVerbose )
1196 1197
            printf( "Found stuck-at-%d node %d.\n", RetValue, Pivot );
        Vec_IntWriteEntry( p->vLutLevs, Pivot, 0 );
1198
        p->nLuts[0]++;
1199 1200
        return RetValue;
    }
1201
    RetValue = 0;
1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222

    // create rows of the table
    nRows = 0;
    for ( i = 0; i < nConsts; i++ )
    for ( k = 0; k < nConsts; k++ )
    {
        Cube = Onset[i] ^ Offset[k];
        assert( Cube );
        nRows = Sbd_ManAddCube1( 256, CoverRows, nRows, Cube );
    }
    assert( nRows <= 64 );
    
    // create columns of the table
    for ( i = 0; i < nRows; i++ )
        for ( k = 0; k <= nDivs; k++ )
            if ( (CoverRows[i] >> k) & 1 )
                Abc_TtXorBit(&CoverCols[k], i);

    // solve the covering problem
    for ( nIters = 0; nIters < nItersMax && nRows < 64; nIters++ )
    {
1223
        if ( p->pPars->fVeryVerbose )
1224 1225 1226 1227 1228
            Sbd_ManMatrPrint( p, CoverCols, nDivs, nRows );

        clk = Abc_Clock();
        if ( !Sbd_ManFindCands( p, CoverCols, nDivs ) )
        {
1229
            if ( p->pPars->fVeryVerbose )
1230
                printf( "Cannot find a feasible cover.\n" );
1231
            p->timeCov += Abc_Clock() - clk;
1232 1233
            return 0;
        }
1234 1235
        p->timeCov += Abc_Clock() - clk;

1236
        if ( p->pPars->fVeryVerbose )
1237 1238 1239 1240 1241
            printf( "Candidate support:  " ),
            Vec_IntPrint( p->vDivSet );

        clk = Abc_Clock();
        *pTruth = Sbd_ManSolve( p->pSat, PivotVar, FreeVar+nIters, p->vDivSet, p->vDivVars, p->vDivValues, p->vLits );
1242
        p->timeSat += Abc_Clock() - clk;
1243 1244 1245 1246 1247

        if ( *pTruth == SBD_SAT_UNDEC )
            printf( "Node %d:  Undecided.\n", Pivot );
        else if ( *pTruth == SBD_SAT_SAT )
        {
1248
            if ( p->pPars->fVeryVerbose )
1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273
            {
                int i;
                printf( "Node %d:  SAT.\n", Pivot );
                for ( i = 0; i < nDivs; i++ )
                    printf( "%d", Vec_IntEntry(p->vLutLevs, Vec_IntEntry(p->vWinObjs, Vec_IntEntry(p->vDivVars, i))) );
                printf( "\n" );
                for ( i = 0; i < nDivs; i++ )
                    printf( "%d", i % 10 );
                printf( "\n" );
                for ( i = 0; i < nDivs; i++ )
                    printf( "%c", (Vec_IntEntry(p->vDivValues, i) & 0x4) ? '0' + (Vec_IntEntry(p->vDivValues, i) & 1) : 'x' );
                printf( "\n" );
                for ( i = 0; i < nDivs; i++ )
                    printf( "%c", (Vec_IntEntry(p->vDivValues, i) & 0x8) ? '0' + ((Vec_IntEntry(p->vDivValues, i) >> 1) & 1) : 'x' );
                printf( "\n" );
            }
            // add row to the covering table
            for ( i = 0; i < nDivs; i++ )
                if ( Vec_IntEntry(p->vDivValues, i) == 0xE || Vec_IntEntry(p->vDivValues, i) == 0xD )
                    CoverCols[i] |= ((word)1 << nRows);
            CoverCols[nDivs] |= ((word)1 << nRows);
            nRows++;
        }
        else
        {
1274
            if ( p->pPars->fVeryVerbose )
1275 1276 1277 1278
            {
                printf( "Node %d:  UNSAT.   ", Pivot );
                Extra_PrintBinary( stdout, (unsigned *)pTruth, 1 << Vec_IntSize(p->vDivSet) ), printf( "\n" );
            }
1279 1280 1281
            p->nLuts[1]++;
            RetValue = 1;
            break;
1282 1283
        }
    }
1284
    return RetValue;
1285 1286
}

1287
int Sbd_ManExploreCut( Sbd_Man_t * p, int Pivot, int nLeaves, int * pLeaves, int * pnStrs, Sbd_Str_t * Strs, int * pFreeVar )
1288 1289 1290 1291
{
    abctime clk = Abc_Clock();
    int PivotVar = Vec_IntEntry(p->vObj2Var, Pivot);
    int Delay = Vec_IntEntry( p->vLutLevs, Pivot );
1292 1293 1294
    int pNodesTop[SBD_DIV_MAX], pNodesBot[SBD_DIV_MAX], pNodesBot1[SBD_DIV_MAX], pNodesBot2[SBD_DIV_MAX];
    int nNodesTop = 0, nNodesBot = 0, nNodesBot1 = 0, nNodesBot2 = 0, nNodesDiff = 0, nNodesDiff1 = 0, nNodesDiff2 = 0;
    int i, k, iObj, nIters, RetValue = 0;
1295

1296
    // try to remove fanins
1297 1298
    for ( nIters = 0; nIters < nLeaves; nIters++ )
    {
1299
        word Truth;
1300 1301 1302
        // try to remove one variable from divisors
        Vec_IntClear( p->vDivSet );
        for ( i = 0; i < nLeaves; i++ )
1303
            if ( i != nLeaves-1-nIters && pLeaves[i] != -1 )
1304 1305
                Vec_IntPush( p->vDivSet, Vec_IntEntry(p->vObj2Var, pLeaves[i]) );
        assert( Vec_IntSize(p->vDivSet) < nLeaves );
1306 1307
        // compute truth table
        clk = Abc_Clock();
1308
        Truth = Sbd_ManSolve( p->pSat, PivotVar, (*pFreeVar)++, p->vDivSet, p->vDivVars, p->vDivValues, p->vLits );
1309
        p->timeSat += Abc_Clock() - clk;
1310 1311 1312
        if ( Truth == SBD_SAT_UNDEC )
            printf( "Node %d:  Undecided.\n", Pivot );
        else if ( Truth == SBD_SAT_SAT )
1313 1314 1315 1316 1317
        {
            int DelayDiff = Vec_IntEntry(p->vLutLevs, pLeaves[nLeaves-1-nIters]) - Delay;
            if ( DelayDiff > -2 )
                return 0;
        }
1318
        else
1319
            pLeaves[nLeaves-1-nIters] = -1;
1320 1321 1322 1323 1324
    }
    Vec_IntClear( p->vDivSet );
    for ( i = 0; i < nLeaves; i++ )
        if ( pLeaves[i] != -1 )
            Vec_IntPush( p->vDivSet, pLeaves[i] );
1325 1326 1327
    //printf( "Reduced %d -> %d\n", nLeaves, Vec_IntSize(p->vDivSet) );
    if ( Vec_IntSize(p->vDivSet) <= p->pPars->nLutSize )
    {
1328
        word Truth;
1329 1330 1331 1332 1333 1334
        *pnStrs = 1;
        // remap divisors
        Vec_IntForEachEntry( p->vDivSet, iObj, i )
            Vec_IntWriteEntry( p->vDivSet, i, Vec_IntEntry(p->vObj2Var, iObj) );
        // compute truth table
        clk = Abc_Clock();
1335
        Truth = Sbd_ManSolve( p->pSat, PivotVar, (*pFreeVar)++, p->vDivSet, p->vDivVars, p->vDivValues, p->vLits );
1336
        p->timeSat += Abc_Clock() - clk;
1337 1338 1339 1340 1341
        if ( Truth == SBD_SAT_SAT )
        {
            printf( "The cut at node %d is not topological.\n", p->Pivot );
            return 0;
        }
1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352
        assert( Truth != SBD_SAT_UNDEC && Truth != SBD_SAT_SAT );
        // create structure
        Strs->fLut = 1;
        Strs->nVarIns = Vec_IntSize( p->vDivSet );
        for ( i = 0; i < Strs->nVarIns; i++ )
            Strs->VarIns[i] = i;
        Strs->Res = Truth;
        p->nLuts[1]++;
        //Extra_PrintBinary( stdout, (unsigned *)&Truth, 1 << Strs->nVarIns ), printf( "\n" );
        return 1;
    }
1353 1354 1355
    assert( Vec_IntSize(p->vDivSet) > p->pPars->nLutSize );

    // count number of nodes on each level
1356
    nNodesTop = nNodesBot = nNodesBot1 = nNodesBot2 = 0;
1357 1358 1359 1360 1361 1362 1363 1364
    Vec_IntForEachEntry( p->vDivSet, iObj, i )
    {
        int DelayDiff = Vec_IntEntry(p->vLutLevs, iObj) - Delay;
        if ( DelayDiff > -2 )
            break;
        if ( DelayDiff == -2 )
            pNodesTop[nNodesTop++] = i;
        else // if ( DelayDiff < -2 )
1365
        {
1366
            pNodesBot[nNodesBot++] = i;
1367 1368 1369 1370 1371
            if ( DelayDiff == -3 )
                pNodesBot1[nNodesBot1++] = i;
            else // if ( DelayDiff < -3 )
                pNodesBot2[nNodesBot2++] = i;
        }
1372
        Vec_IntWriteEntry( p->vDivSet, i, Vec_IntEntry(p->vObj2Var, iObj) );
1373
    }
1374
    assert( nNodesBot == nNodesBot1 + nNodesBot2 );
1375 1376 1377 1378
    if ( i < Vec_IntSize(p->vDivSet) )
        return 0;
    if ( nNodesTop > p->pPars->nLutSize-1 )
        return 0;
1379 1380 1381

    // try 44
    if ( Vec_IntSize(p->vDivSet) <= 2*p->pPars->nLutSize-1 )
1382
    {
1383 1384 1385 1386 1387 1388 1389 1390
        int nMoved = 0;
        if ( nNodesBot > p->pPars->nLutSize ) // need to move bottom left-over to the top
        {
            while ( nNodesBot > p->pPars->nLutSize )
                pNodesTop[nNodesTop++] = pNodesBot[--nNodesBot], nMoved++;
            assert( nNodesBot == p->pPars->nLutSize );
        }
        assert( nNodesBot <= p->pPars->nLutSize );
1391
        assert( nNodesTop <= p->pPars->nLutSize-1 );
1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402

        Strs[0].fLut = 1;
        Strs[0].nVarIns = p->pPars->nLutSize;
        for ( i = 0; i < nNodesTop; i++ )
            Strs[0].VarIns[i] = pNodesTop[i];
        for ( ; i < p->pPars->nLutSize; i++ )
            Strs[0].VarIns[i] = Vec_IntSize(p->vDivSet)+1 + i-nNodesTop;
        Strs[0].Res = 0;

        Strs[1].fLut = 1;
        Strs[1].nVarIns = nNodesBot;
1403
        for ( i = 0; i < nNodesBot; i++ )
1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426
            Strs[1].VarIns[i] = pNodesBot[i];
        Strs[1].Res = 0;

        nNodesDiff = p->pPars->nLutSize-1 - nNodesTop;
        assert( nNodesDiff >= 0 && nNodesDiff <= 3 );
        for ( k = 0; k < nNodesDiff; k++ )
        {
            Strs[2+k].fLut = 0;
            Strs[2+k].nVarIns = nNodesBot;
            for ( i = 0; i < nNodesBot; i++ )
                Strs[2+k].VarIns[i] = pNodesBot[i];
            Strs[2+k].Res = 0;
        }

        *pnStrs = 2 + nNodesDiff;
        clk = Abc_Clock();
        RetValue = Sbd_ProblemSolve( p->pGia, p->vMirrors,   Pivot, p->vWinObjs, p->vObj2Var, p->vTfo, p->vRoots,   p->vDivSet, *pnStrs, Strs );
        p->timeQbf += Abc_Clock() - clk;
        if ( RetValue ) 
            p->nLuts[2]++;

        while ( nMoved-- )
            pNodesBot[nNodesBot++] = pNodesTop[--nNodesTop];
1427 1428
    }

1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553
    if ( RetValue )
        return RetValue;
    if ( p->pPars->nLutNum < 3 )
        return 0;
    if ( Vec_IntSize(p->vDivSet) < 2*p->pPars->nLutSize-1 )
        return 0;

    // try 444 -- LUT(LUT, LUT)
    if ( nNodesTop <= p->pPars->nLutSize-2 )
    {
        int nMoved = 0;
        if ( nNodesBot > 2*p->pPars->nLutSize ) // need to move bottom left-over to the top
        {
            while ( nNodesBot > 2*p->pPars->nLutSize )
                pNodesTop[nNodesTop++] = pNodesBot[--nNodesBot], nMoved++;
            assert( nNodesBot == 2*p->pPars->nLutSize );
        }
        assert( nNodesBot > p->pPars->nLutSize );
        assert( nNodesBot <= 2*p->pPars->nLutSize );
        assert( nNodesTop <= p->pPars->nLutSize-2 );

        Strs[0].fLut = 1;
        Strs[0].nVarIns = p->pPars->nLutSize;
        for ( i = 0; i < nNodesTop; i++ )
            Strs[0].VarIns[i] = pNodesTop[i];
        for ( ; i < p->pPars->nLutSize; i++ )
            Strs[0].VarIns[i] = Vec_IntSize(p->vDivSet)+1 + i-nNodesTop;
        Strs[0].Res = 0;

        Strs[1].fLut = 1;
        Strs[1].nVarIns = p->pPars->nLutSize;
        for ( i = 0; i < Strs[1].nVarIns; i++ )
            Strs[1].VarIns[i] = pNodesBot[i];
        Strs[1].Res = 0;

        Strs[2].fLut = 1;
        Strs[2].nVarIns = p->pPars->nLutSize;
        for ( i = 0; i < Strs[2].nVarIns; i++ )
            Strs[2].VarIns[i] = pNodesBot[nNodesBot-p->pPars->nLutSize+i];
        Strs[2].Res = 0;

        nNodesDiff = p->pPars->nLutSize-2 - nNodesTop;
        assert( nNodesDiff >= 0 && nNodesDiff <= 2 );
        for ( k = 0; k < nNodesDiff; k++ )
        {
            Strs[3+k].fLut = 0;
            Strs[3+k].nVarIns = nNodesBot;
            for ( i = 0; i < nNodesBot; i++ )
                Strs[3+k].VarIns[i] = pNodesBot[i];
            Strs[3+k].Res = 0;
        }

        *pnStrs = 3 + nNodesDiff;
        clk = Abc_Clock();
        RetValue = Sbd_ProblemSolve( p->pGia, p->vMirrors,   Pivot, p->vWinObjs, p->vObj2Var, p->vTfo, p->vRoots,   p->vDivSet, *pnStrs, Strs );
        p->timeQbf += Abc_Clock() - clk;
        if ( RetValue ) 
            p->nLuts[3]++;

        while ( nMoved-- )
            pNodesBot[nNodesBot++] = pNodesTop[--nNodesTop];
    }
    if ( RetValue )
        return RetValue;

    // try 444 -- LUT(LUT(LUT))
    if ( nNodesBot1 + nNodesTop <= 2*p->pPars->nLutSize-2 )
    {
        if ( nNodesBot2 > p->pPars->nLutSize ) // need to move bottom left-over to the top
        {
            while ( nNodesBot2 > p->pPars->nLutSize )
                pNodesBot1[nNodesBot1++] = pNodesBot2[--nNodesBot2];
            assert( nNodesBot2 == p->pPars->nLutSize );
        }
        if ( nNodesBot1 > p->pPars->nLutSize-1 ) // need to move bottom left-over to the top
        {
            while ( nNodesBot1 > p->pPars->nLutSize-1 )
                pNodesTop[nNodesTop++] = pNodesBot1[--nNodesBot1];
            assert( nNodesBot1 == p->pPars->nLutSize-1 );
        }
        assert( nNodesBot2 <= p->pPars->nLutSize );
        assert( nNodesBot1 <= p->pPars->nLutSize-1 );
        assert( nNodesTop <= p->pPars->nLutSize-1 );

        Strs[0].fLut = 1;
        Strs[0].nVarIns = p->pPars->nLutSize;
        for ( i = 0; i < nNodesTop; i++ )
            Strs[0].VarIns[i] = pNodesTop[i];
        Strs[0].VarIns[i++] = Vec_IntSize(p->vDivSet)+1;
        for ( ; i < p->pPars->nLutSize; i++ )
            Strs[0].VarIns[i] = Vec_IntSize(p->vDivSet)+2 + i-nNodesTop;
        Strs[0].Res = 0;
        nNodesDiff1 = p->pPars->nLutSize-1 - nNodesTop;

        Strs[1].fLut = 1;
        Strs[1].nVarIns = p->pPars->nLutSize;
        for ( i = 0; i < nNodesBot1; i++ )
            Strs[1].VarIns[i] = pNodesBot1[i];
        Strs[1].VarIns[i++] = Vec_IntSize(p->vDivSet)+2;
        for ( ; i < p->pPars->nLutSize; i++ )
            Strs[1].VarIns[i] = Vec_IntSize(p->vDivSet)+2+nNodesDiff1 + i-nNodesBot1;
        Strs[1].Res = 0;
        nNodesDiff2 = p->pPars->nLutSize-1 - nNodesBot1;

        Strs[2].fLut = 1;
        Strs[2].nVarIns = nNodesBot2;
        for ( i = 0; i < Strs[2].nVarIns; i++ )
            Strs[2].VarIns[i] = pNodesBot2[i];
        Strs[2].Res = 0;

        nNodesDiff = nNodesDiff1 + nNodesDiff2;
        assert( nNodesDiff >= 0 && nNodesDiff <= 3 );
        for ( k = 0; k < nNodesDiff; k++ )
        {
            Strs[3+k].fLut = 0;
            Strs[3+k].nVarIns = nNodesBot2;
            for ( i = 0; i < nNodesBot2; i++ )
                Strs[3+k].VarIns[i] = pNodesBot2[i];
            Strs[3+k].Res = 0;
            if ( k >= nNodesDiff1 )
                continue;
            Strs[3+k].nVarIns += nNodesBot1;
            for ( i = 0; i < nNodesBot1; i++ )
                Strs[3+k].VarIns[nNodesBot2 + i] = pNodesBot1[i];
        }
1554

1555 1556 1557 1558 1559 1560 1561
        *pnStrs = 3 + nNodesDiff;
        clk = Abc_Clock();
        RetValue = Sbd_ProblemSolve( p->pGia, p->vMirrors,   Pivot, p->vWinObjs, p->vObj2Var, p->vTfo, p->vRoots,   p->vDivSet, *pnStrs, Strs );
        p->timeQbf += Abc_Clock() - clk;
        if ( RetValue ) 
            p->nLuts[4]++;
    }
1562
    return RetValue;
1563
}
1564 1565 1566 1567 1568 1569 1570 1571 1572 1573
int Sbd_ManExplore3( Sbd_Man_t * p, int Pivot, int * pnStrs, Sbd_Str_t * Strs )
{
    int FreeVar = Vec_IntSize(p->vWinObjs) + Vec_IntSize(p->vTfo) + Vec_IntSize(p->vRoots);
    int FreeVarStart = FreeVar;
    int nSize, nLeaves, pLeaves[SBD_DIV_MAX];
    //sat_solver_delete_p( &p->pSat );
    abctime clk = Abc_Clock();
    p->pSat = Sbd_ManSatSolver( p->pSat, p->pGia, p->vMirrors, Pivot, p->vWinObjs, p->vObj2Var, p->vTfo, p->vRoots, 0 );
    p->timeCnf += Abc_Clock() - clk;
    // extract one cut
1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584
    if ( p->pSrv )
    {
        nLeaves = Sbd_ManCutServerFirst( p->pSrv, Pivot, pLeaves );
        if ( nLeaves == -1 )
            return 0;
        assert( nLeaves <= p->pPars->nCutSize );
        if ( Sbd_ManExploreCut( p, Pivot, nLeaves, pLeaves, pnStrs, Strs, &FreeVar ) )
            return 1;
        return 0;
    }
    // extract one cut
1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596
    for ( nSize = p->pPars->nLutSize + 1; nSize <= p->pPars->nCutSize; nSize++ )
    {
        nLeaves = Sbd_StoObjBestCut( p->pSto, Pivot, nSize, pLeaves );
        if ( nLeaves == -1 )
            continue;
        assert( nLeaves == nSize );
        if ( Sbd_ManExploreCut( p, Pivot, nLeaves, pLeaves, pnStrs, Strs, &FreeVar ) )
            return 1;
    }
    assert( FreeVar - FreeVarStart <= SBD_FVAR_MAX ); 
    return 0;
}
1597 1598


1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631
/**Function*************************************************************

  Synopsis    [Computes delay-oriented k-feasible cut at the node.]

  Description [Return 1 if node's LUT level does not exceed those of the fanins.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sbd_CutMergeSimple( Sbd_Man_t * p, int * pCut1, int * pCut2, int * pCut )
{
    int * pBeg  = pCut + 1;
    int * pBeg1 = pCut1 + 1;
    int * pBeg2 = pCut2 + 1;
    int * pEnd1 = pCut1 + 1 + pCut1[0];
    int * pEnd2 = pCut2 + 1 + pCut2[0];
    while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 )
    {
        if ( *pBeg1 == *pBeg2 )
            *pBeg++ = *pBeg1++, pBeg2++;
        else if ( *pBeg1 < *pBeg2 )
            *pBeg++ = *pBeg1++;
        else 
            *pBeg++ = *pBeg2++;
    }
    while ( pBeg1 < pEnd1 )
        *pBeg++ = *pBeg1++;
    while ( pBeg2 < pEnd2 )
        *pBeg++ = *pBeg2++;
    return (pCut[0] = pBeg - pCut - 1);
}
1632 1633
/*
int Sbd_ManMergeCuts( Sbd_Man_t * p, int Node )
1634
{
1635 1636
    int Result  = 1; // no need to resynthesize
    int pCut[2*SBD_MAX_LUTSIZE+1];     
1637 1638 1639 1640
    int iFan0   = Gia_ObjFaninId0( Gia_ManObj(p->pGia, Node), Node );
    int iFan1   = Gia_ObjFaninId1( Gia_ManObj(p->pGia, Node), Node );
    int Level0  = Vec_IntEntry( p->vLutLevs, iFan0 );
    int Level1  = Vec_IntEntry( p->vLutLevs, iFan1 );
1641
    int LevMax  = (Level0 || Level1) ? Abc_MaxInt(Level0, Level1) : 1;
1642 1643
    int * pCut0 = Sbd_ObjCut( p, iFan0 );
    int * pCut1 = Sbd_ObjCut( p, iFan1 );
1644
    int nSize   = Sbd_CutMergeSimple( p, pCut0, pCut1, pCut );
1645 1646
    if ( nSize > p->pPars->nLutSize )
    {
1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660
        if ( Level0 != Level1 )
        {
            int Cut0[2] = {1, iFan0}, * pCut0Temp = Level0 < LevMax ? Cut0 : pCut0; 
            int Cut1[2] = {1, iFan1}, * pCut1Temp = Level1 < LevMax ? Cut1 : pCut1; 
            nSize = Sbd_CutMergeSimple( p, pCut0Temp, pCut1Temp, pCut );
        }
        if ( nSize > p->pPars->nLutSize )
        {
            pCut[0] = 2;
            pCut[1] = iFan0 < iFan1 ? iFan0 : iFan1;
            pCut[2] = iFan0 < iFan1 ? iFan1 : iFan0;
            Result  = LevMax ? 0 : 1;
            LevMax++;
        }
1661
    }
1662
    assert( iFan0 != iFan1 );
1663 1664 1665
    assert( Vec_IntEntry(p->vLutLevs, Node) == 0 );
    Vec_IntWriteEntry( p->vLutLevs, Node, LevMax );
    memcpy( Sbd_ObjCut(p, Node), pCut, sizeof(int) * (pCut[0] + 1) );
1666
    //printf( "Setting node %d with delay %d (result = %d).\n", Node, LevMax, Result );
1667 1668
    return Result;
}
1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711
*/
int Sbd_ManMergeCuts( Sbd_Man_t * p, int Node )
{
    int pCut11[2*SBD_MAX_LUTSIZE+1];     
    int pCut01[2*SBD_MAX_LUTSIZE+1];     
    int pCut10[2*SBD_MAX_LUTSIZE+1];     
    int pCut00[2*SBD_MAX_LUTSIZE+1];     
    int iFan0   = Gia_ObjFaninId0( Gia_ManObj(p->pGia, Node), Node );
    int iFan1   = Gia_ObjFaninId1( Gia_ManObj(p->pGia, Node), Node );
    int Level0  = Vec_IntEntry( p->vLutLevs, iFan0 ) ? Vec_IntEntry( p->vLutLevs, iFan0 ) : 1;
    int Level1  = Vec_IntEntry( p->vLutLevs, iFan1 ) ? Vec_IntEntry( p->vLutLevs, iFan1 ) : 1;
    int * pCut0 = Sbd_ObjCut( p, iFan0 );
    int * pCut1 = Sbd_ObjCut( p, iFan1 );
    int Cut0[2] = {1, iFan0}; 
    int Cut1[2] = {1, iFan1}; 
    int nSize11 = Sbd_CutMergeSimple( p, pCut0, pCut1, pCut11 );
    int nSize01 = Sbd_CutMergeSimple( p,  Cut0, pCut1, pCut01 );
    int nSize10 = Sbd_CutMergeSimple( p, pCut0,  Cut1, pCut10 );
    int nSize00 = Sbd_CutMergeSimple( p,  Cut0,  Cut1, pCut00 );
    int Lev11   = nSize11 <= p->pPars->nLutSize ? Abc_MaxInt(Level0,   Level1)   : ABC_INFINITY;
    int Lev01   = nSize01 <= p->pPars->nLutSize ? Abc_MaxInt(Level0+1, Level1)   : ABC_INFINITY;
    int Lev10   = nSize10 <= p->pPars->nLutSize ? Abc_MaxInt(Level0,   Level1+1) : ABC_INFINITY;
    int Lev00   = nSize00 <= p->pPars->nLutSize ? Abc_MaxInt(Level0+1, Level1+1) : ABC_INFINITY;
    int * pCutRes = pCut11;
    int LevCur    = Lev11;
    if ( Lev01 < LevCur || (Lev01 == LevCur && pCut01[0] < pCutRes[0]) )
    {
        pCutRes = pCut01;
        LevCur  = Lev01;
    }
    if ( Lev10 < LevCur || (Lev10 == LevCur && pCut10[0] < pCutRes[0]) )
    {
        pCutRes = pCut10;
        LevCur  = Lev10;
    }
    if ( Lev00 < LevCur || (Lev00 == LevCur && pCut00[0] < pCutRes[0]) )
    {
        pCutRes = pCut00;
        LevCur  = Lev00;
    }
    assert( iFan0 != iFan1 );
    assert( Vec_IntEntry(p->vLutLevs, Node) == 0 );
    Vec_IntWriteEntry( p->vLutLevs, Node, LevCur );
1712
    //Vec_IntWriteEntry( p->vLevs, Node, 1+Abc_MaxInt(Vec_IntEntry(p->vLevs, iFan0), Vec_IntEntry(p->vLevs, iFan1)) );
1713 1714
    assert( pCutRes[0] <= p->pPars->nLutSize );
    memcpy( Sbd_ObjCut(p, Node), pCutRes, sizeof(int) * (pCutRes[0] + 1) );
1715
//printf( "Setting node %d with delay %d.\n", Node, LevCur );
1716
    return LevCur == 1; // LevCur == Abc_MaxInt(Level0, Level1);
1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775
}
int Sbd_ManDelay( Sbd_Man_t * p )
{
    int i, Id, Delay = 0;
    Gia_ManForEachCoDriverId( p->pGia, Id, i )
        Delay = Abc_MaxInt( Delay, Vec_IntEntry(p->vLutLevs, Id) );
    return Delay;
}
void Sbd_ManMergeTest( Sbd_Man_t * p )
{
    int Node;
    Gia_ManForEachAndId( p->pGia, Node )
        Sbd_ManMergeCuts( p, Node );
    printf( "Delay %d.\n", Sbd_ManDelay(p) );
}

void Sbd_ManFindCut_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
{
    if ( pObj->fMark1 )
        return;
    pObj->fMark1 = 1;
    if ( pObj->fMark0 )
        return;
    assert( Gia_ObjIsAnd(pObj) );
    Sbd_ManFindCut_rec( p, Gia_ObjFanin0(pObj) );
    Sbd_ManFindCut_rec( p, Gia_ObjFanin1(pObj) );
}
void Sbd_ManFindCutUnmark_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
{
    if ( !pObj->fMark1 )
        return;
    pObj->fMark1 = 0;
    if ( pObj->fMark0 )
        return;
    assert( Gia_ObjIsAnd(pObj) );
    Sbd_ManFindCutUnmark_rec( p, Gia_ObjFanin0(pObj) );
    Sbd_ManFindCutUnmark_rec( p, Gia_ObjFanin1(pObj) );
}
void Sbd_ManFindCut( Sbd_Man_t * p, int Node, Vec_Int_t * vCutLits )
{
    int pCut[SBD_MAX_LUTSIZE+1];     
    int i, LevelMax = 0;
    // label reachable nodes 
    Gia_Obj_t * pTemp, * pObj = Gia_ManObj(p->pGia, Node);
    Sbd_ManFindCut_rec( p->pGia, pObj );
    // collect 
    pCut[0] = 0;
    Gia_ManForEachObjVec( vCutLits, p->pGia, pTemp, i )
        if ( pTemp->fMark1 )
        {
            LevelMax = Abc_MaxInt( LevelMax, Vec_IntEntry(p->vLutLevs, Gia_ObjId(p->pGia, pTemp)) );
            pCut[1+pCut[0]++] = Gia_ObjId(p->pGia, pTemp);
        }
    assert( pCut[0] <= p->pPars->nLutSize );
    // unlabel reachable nodes
    Sbd_ManFindCutUnmark_rec( p->pGia, pObj );
    // create cut
    assert( Vec_IntEntry(p->vLutLevs, Node) == 0 );
    Vec_IntWriteEntry( p->vLutLevs, Node, LevelMax+1 );
1776
    //Vec_IntWriteEntry( p->vLevs, Node, 1+Abc_MaxInt(Vec_IntEntry(p->vLevs, Gia_ObjFaninId0(pObj, Node)), Vec_IntEntry(p->vLevs, Gia_ObjFaninId1(pObj, Node))) );
1777 1778 1779
    memcpy( Sbd_ObjCut(p, Node), pCut, sizeof(int) * (pCut[0] + 1) );
}

1780
int Sbd_ManImplement( Sbd_Man_t * p, int Pivot, word Truth )
1781
{
1782
    Gia_Obj_t * pObj;
1783
    int i, k, w, iLit, Entry, Node;
1784 1785
    int iObjLast = Gia_ManObjNum(p->pGia);
    int iCurLev = Vec_IntEntry(p->vLutLevs, Pivot);
1786
    int iNewLev;
1787 1788
    // collect leaf literals
    Vec_IntClear( p->vLits );
1789
    Vec_IntForEachEntry( p->vDivSet, Node, i )
1790 1791 1792 1793 1794 1795 1796 1797
    {
        Node = Vec_IntEntry( p->vWinObjs, Node );
        if ( Vec_IntEntry(p->vMirrors, Node) >= 0 )
            Vec_IntPush( p->vLits, Vec_IntEntry(p->vMirrors, Node) );
        else
            Vec_IntPush( p->vLits, Abc_Var2Lit(Node, 0) );
    }
    // pretend to have MUXes
1798 1799
//    assert( p->pGia->pMuxes == NULL );
    if ( p->pGia->nXors && p->pGia->pMuxes == NULL )
1800 1801 1802
        p->pGia->pMuxes = (unsigned *)p;
    // derive new function of the node
    iLit = Dsm_ManTruthToGia( p->pGia, &Truth, p->vLits, p->vCover );
1803 1804
    if ( p->pGia->pMuxes == (unsigned *)p )
        p->pGia->pMuxes = NULL;
1805
    // remember this function
1806 1807
    assert( Vec_IntEntry(p->vMirrors, Pivot) == -1 );
    Vec_IntWriteEntry( p->vMirrors, Pivot, iLit );
1808 1809
    if ( p->pPars->fVerbose )
        printf( "Replacing node %d by literal %d.\n", Pivot, iLit );
1810 1811 1812 1813 1814 1815 1816
    // translate literals into variables
    Vec_IntForEachEntry( p->vLits, Entry, i )
        Vec_IntWriteEntry( p->vLits, i, Abc_Lit2Var(Entry) );
    // label inputs
    Gia_ManForEachObjVec( p->vLits, p->pGia, pObj, i )
        pObj->fMark0 = 1;
    // extend data-structure to accommodate new nodes
1817 1818 1819 1820
    assert( Vec_IntSize(p->vLutLevs) == iObjLast );
    for ( i = iObjLast; i < Gia_ManObjNum(p->pGia); i++ )
    {
        Vec_IntPush( p->vLutLevs, 0 );
1821 1822
        Vec_IntPush( p->vObj2Var, 0 );
        Vec_IntPush( p->vMirrors, -1 );
1823
        Vec_IntFillExtra( p->vLutCuts, Vec_IntSize(p->vLutCuts) + p->pPars->nLutSize + 1, 0 );
1824
        Sbd_ManFindCut( p, i, p->vLits );
1825
        for ( k = 0; k < 4; k++ )
1826 1827 1828
            for ( w = 0; w < p->pPars->nWords; w++ )
                Vec_WrdPush( p->vSims[k], 0 );
    }
1829 1830 1831
    // unlabel inputs
    Gia_ManForEachObjVec( p->vLits, p->pGia, pObj, i )
        pObj->fMark0 = 0;
1832
    // make sure delay reduction is achieved
1833 1834 1835 1836 1837
    iNewLev = Vec_IntEntry( p->vLutLevs, Abc_Lit2Var(iLit) );
    assert( iNewLev < iCurLev );
    // update delay of the initial node
    assert( Vec_IntEntry(p->vLutLevs, Pivot) == iCurLev );
    Vec_IntWriteEntry( p->vLutLevs, Pivot, iNewLev );
1838
    //Vec_IntWriteEntry( p->vLevs, Pivot, 1+Abc_MaxInt(Vec_IntEntry(p->vLevs, Gia_ObjFaninId0(pObj, Pivot)), Vec_IntEntry(p->vLevs, Gia_ObjFaninId1(pObj, Pivot))) );
1839 1840 1841
    return 0;
}

1842 1843
int Sbd_ManImplement2( Sbd_Man_t * p, int Pivot, int nStrs, Sbd_Str_t * pStrs )
{
1844
    //Gia_Obj_t * pObj = NULL;
1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889
    int i, k, w, iLit, Node;
    int iObjLast = Gia_ManObjNum(p->pGia);
    int iCurLev = Vec_IntEntry(p->vLutLevs, Pivot);
    int iNewLev;
    // collect leaf literals
    Vec_IntClear( p->vLits );
    Vec_IntForEachEntry( p->vDivSet, Node, i )
    {
        Node = Vec_IntEntry( p->vWinObjs, Node );
        if ( Vec_IntEntry(p->vMirrors, Node) >= 0 )
            Vec_IntPush( p->vLits, Vec_IntEntry(p->vMirrors, Node) );
        else
            Vec_IntPush( p->vLits, Abc_Var2Lit(Node, 0) );
    }
    // collect structure nodes
    for ( i = 0; i < nStrs; i++ )
        Vec_IntPush( p->vLits, -1 );
    // implement structures
    for ( i = nStrs-1; i >= 0; i-- )
    {
        if ( pStrs[i].fLut )
        {
            // collect local literals
            Vec_IntClear( p->vLits2 );
            for ( k = 0; k < (int)pStrs[i].nVarIns; k++ )
                Vec_IntPush( p->vLits2, Vec_IntEntry(p->vLits, pStrs[i].VarIns[k]) );
            // pretend to have MUXes
        //    assert( p->pGia->pMuxes == NULL );
            if ( p->pGia->nXors && p->pGia->pMuxes == NULL )
                p->pGia->pMuxes = (unsigned *)p;
            // derive new function of the node
            iLit = Dsm_ManTruthToGia( p->pGia, &pStrs[i].Res, p->vLits2, p->vCover );
            if ( p->pGia->pMuxes == (unsigned *)p )
                p->pGia->pMuxes = NULL;
        }
        else
        {
            iLit = Vec_IntEntry( p->vLits, (int)pStrs[i].Res );
            assert( iLit > 0 );
        }
        // update literal
        assert( Vec_IntEntry(p->vLits, Vec_IntSize(p->vLits)-nStrs+i) == -1 );
        Vec_IntWriteEntry( p->vLits, Vec_IntSize(p->vLits)-nStrs+i, iLit );
    }
    iLit = Vec_IntEntry( p->vLits, Vec_IntSize(p->vDivSet) );
1890
    //assert( iObjLast == Gia_ManObjNum(p->pGia) || Abc_Lit2Var(iLit) == Gia_ManObjNum(p->pGia)-1 );
1891 1892 1893
    // remember this function
    assert( Vec_IntEntry(p->vMirrors, Pivot) == -1 );
    Vec_IntWriteEntry( p->vMirrors, Pivot, iLit );
1894
    if ( p->pPars->fVeryVerbose )
1895 1896 1897 1898 1899
        printf( "Replacing node %d by literal %d.\n", Pivot, iLit );

    // extend data-structure to accommodate new nodes
    assert( Vec_IntSize(p->vLutLevs) == iObjLast );
    for ( i = iObjLast; i < Gia_ManObjNum(p->pGia); i++ )
1900
    {
1901
        assert( i == Vec_IntSize(p->vMirrors) );
1902
        Vec_IntPush( p->vMirrors, -1 );
1903
        Sbd_StoRefObj( p->pSto, i, i == Gia_ManObjNum(p->pGia)-1 ? Pivot : -1 );
1904
    }
1905
    Sbd_StoDerefObj( p->pSto, Pivot );
1906 1907
    for ( i = iObjLast; i < Gia_ManObjNum(p->pGia); i++ )
    {
1908
        //Gia_Obj_t * pObjI = Gia_ManObj( p->pGia, i );
1909
        abctime clk = Abc_Clock();
1910
        int Delay = Sbd_StoComputeCutsNode( p->pSto, i );
1911
        p->timeCut += Abc_Clock() - clk;
1912 1913
        assert( i == Vec_IntSize(p->vLutLevs) );
        Vec_IntPush( p->vLutLevs, Delay );
1914
        //Vec_IntPush( p->vLevs, 1+Abc_MaxInt(Vec_IntEntry(p->vLevs, Gia_ObjFaninId0(pObjI, i)), Vec_IntEntry(p->vLevs, Gia_ObjFaninId1(pObjI, i))) );
1915 1916
        Vec_IntPush( p->vObj2Var, 0 );
        Vec_IntFillExtra( p->vLutCuts, Vec_IntSize(p->vLutCuts) + p->pPars->nLutSize + 1, 0 );
1917
        Sbd_StoSaveBestDelayCut( p->pSto, i, Sbd_ObjCut(p, i) );
1918 1919 1920 1921 1922 1923 1924
        //Sbd_ManFindCut( p, i, p->vLits );
        for ( k = 0; k < 4; k++ )
            for ( w = 0; w < p->pPars->nWords; w++ )
                Vec_WrdPush( p->vSims[k], 0 );
    }
    // make sure delay reduction is achieved
    iNewLev = Vec_IntEntry( p->vLutLevs, Abc_Lit2Var(iLit) );
1925
    assert( !iNewLev || iNewLev < iCurLev );
1926
    // update delay of the initial node
1927
    //pObj = Gia_ManObj( p->pGia, Pivot );
1928 1929
    assert( Vec_IntEntry(p->vLutLevs, Pivot) == iCurLev );
    Vec_IntWriteEntry( p->vLutLevs, Pivot, iNewLev );
1930
    //Vec_IntWriteEntry( p->vLevs, Pivot, Pivot ? 1+Abc_MaxInt(Vec_IntEntry(p->vLevs, Gia_ObjFaninId0(pObj, Pivot)), Vec_IntEntry(p->vLevs, Gia_ObjFaninId1(pObj, Pivot))) : 0 );
1931 1932 1933
    return 0;
}

1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944
/**Function*************************************************************

  Synopsis    [Derives new AIG after resynthesis.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
1945 1946 1947
void Sbd_ManDeriveMapping_rec( Sbd_Man_t * p, Gia_Man_t * pNew, int iObj )
{
    Gia_Obj_t * pObj; int k, * pCut;
1948
    if ( !iObj || Gia_ObjIsTravIdCurrentId(pNew, iObj) )
1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966
        return;
    Gia_ObjSetTravIdCurrentId(pNew, iObj);
    pObj = Gia_ManObj( pNew, iObj );
    if ( Gia_ObjIsCi(pObj) )
        return;
    assert( Gia_ObjIsAnd(pObj) );
    pCut = Sbd_ObjCut2( p, iObj );
    for ( k = 1; k <= pCut[0]; k++ )
        Sbd_ManDeriveMapping_rec( p, pNew, pCut[k] );
    // add mapping
    Vec_IntWriteEntry( pNew->vMapping, iObj, Vec_IntSize(pNew->vMapping) );
    for ( k = 0; k <= pCut[0]; k++ )
        Vec_IntPush( pNew->vMapping, pCut[k] );
    Vec_IntPush( pNew->vMapping, iObj );
}
void Sbd_ManDeriveMapping( Sbd_Man_t * p, Gia_Man_t * pNew )
{
    Gia_Obj_t * pObj, * pFan; 
1967
    int i, k, iFan, iObjNew, iFanNew, * pCut, * pCutNew;
1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988
    Vec_Int_t * vLeaves = Vec_IntAlloc( 100 );
    // derive cuts for the new manager
    p->vLutCuts2 = Vec_IntStart( Gia_ManObjNum(pNew) * (p->pPars->nLutSize + 1) );
    Gia_ManForEachAnd( p->pGia, pObj, i )
    {
        if ( Vec_IntEntry(p->vMirrors, i) >= 0 )
            continue;
        if ( pObj->Value == ~0 )
            continue;
        iObjNew = Abc_Lit2Var( pObj->Value );
        if ( !Gia_ObjIsAnd(Gia_ManObj(pNew, iObjNew)) )
            continue;
        pCutNew = Sbd_ObjCut2( p, iObjNew );
        pCut    = Sbd_ObjCut( p, i );
        Vec_IntClear( vLeaves );
        for ( k = 1; k <= pCut[0]; k++ )
        {
            iFan = Vec_IntEntry(p->vMirrors, pCut[k]) >= 0 ? Abc_Lit2Var(Vec_IntEntry(p->vMirrors, pCut[k])) : pCut[k];
            pFan = Gia_ManObj( p->pGia, iFan );
            if ( pFan->Value == ~0 )
                continue;
1989 1990
            iFanNew = Abc_Lit2Var( pFan->Value );
            if ( iFanNew == 0 || iFanNew == iObjNew )
1991
                continue;
1992
            Vec_IntPushUniqueOrder( vLeaves, iFanNew );
1993 1994
        }
        assert( Vec_IntSize(vLeaves) <= p->pPars->nLutSize );
1995
        //assert( Vec_IntSize(vLeaves) > 1 );
1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008
        pCutNew[0] = Vec_IntSize(vLeaves);
        memcpy( pCutNew+1, Vec_IntArray(vLeaves), sizeof(int) * Vec_IntSize(vLeaves) );
    }
    Vec_IntFree( vLeaves );
    // create new mapping
    Vec_IntFreeP( &pNew->vMapping );
    pNew->vMapping = Vec_IntAlloc( (p->pPars->nLutSize + 2) * Gia_ManObjNum(pNew) );
    Vec_IntFill( pNew->vMapping, Gia_ManObjNum(pNew), 0 );
    Gia_ManIncrementTravId( pNew );
    Gia_ManForEachCo( pNew, pObj, i )
        Sbd_ManDeriveMapping_rec( p, pNew, Gia_ObjFaninId0p(pNew, pObj) );
    Vec_IntFreeP( &p->vLutCuts2 );
}
2009 2010 2011 2012
void Sbd_ManDerive_rec( Gia_Man_t * pNew, Gia_Man_t * p, int Node, Vec_Int_t * vMirrors )
{
    Gia_Obj_t * pObj;
    int Obj = Node;
2013
    if ( Vec_IntEntry(vMirrors, Node) >= 0 )
2014 2015
        Obj = Abc_Lit2Var( Vec_IntEntry(vMirrors, Node) );
    pObj = Gia_ManObj( p, Obj );
2016 2017 2018 2019 2020 2021 2022 2023 2024 2025
    if ( !~pObj->Value )
    {
        assert( Gia_ObjIsAnd(pObj) );
        Sbd_ManDerive_rec( pNew, p, Gia_ObjFaninId0(pObj, Obj), vMirrors );
        Sbd_ManDerive_rec( pNew, p, Gia_ObjFaninId1(pObj, Obj), vMirrors );
        if ( Gia_ObjIsXor(pObj) )
            pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
        else
            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    }
2026 2027 2028 2029
    // set the original node as well
    if ( Obj != Node )
        Gia_ManObj(p, Node)->Value = Abc_LitNotCond( pObj->Value, Abc_LitIsCompl(Vec_IntEntry(vMirrors, Node)) );
} 
2030
Gia_Man_t * Sbd_ManDerive( Sbd_Man_t * pMan, Gia_Man_t * p, Vec_Int_t * vMirrors )
2031
{
2032
    Gia_Man_t * pNew, * pTemp;
2033 2034 2035 2036 2037 2038
    Gia_Obj_t * pObj;
    int i;
    Gia_ManFillValue( p );
    pNew = Gia_ManStart( Gia_ManObjNum(p) );
    pNew->pName = Abc_UtilStrsav( p->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
2039 2040
    if ( p->pMuxes )
        pNew->pMuxes = ABC_CALLOC( unsigned, Gia_ManObjNum(p) );
2041 2042 2043 2044
    Gia_ManConst0(p)->Value = 0;
    Gia_ManHashAlloc( pNew );
    Gia_ManForEachCi( p, pObj, i )
        pObj->Value = Gia_ManAppendCi(pNew);
2045 2046
    Gia_ManForEachCo( p, pObj, i )
        Sbd_ManDerive_rec( pNew, p, Gia_ObjFaninId0p(p, pObj), vMirrors );
2047 2048 2049 2050
    Gia_ManForEachCo( p, pObj, i )
        pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
    Gia_ManHashStop( pNew );
    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
2051
    Gia_ManTransferTiming( pNew, p );
2052 2053
    if ( pMan->pPars->fMapping )
        Sbd_ManDeriveMapping( pMan, pNew );
2054 2055 2056
    // remove dangling nodes
    pNew = Gia_ManCleanup( pTemp = pNew );
    Gia_ManTransferTiming( pNew, pTemp );
2057
    Gia_ManTransferMapping( pNew, pTemp );
2058
    Gia_ManStop( pTemp );
2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072
    return pNew;
}

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

  Synopsis    [Performs delay optimization for the given LUT size.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
2073 2074
void Sbd_NtkPerformOne( Sbd_Man_t * p, int Pivot )
{
2075
    Sbd_Str_t Strs[SBD_DIV_MAX]; word Truth = 0;
2076 2077
    int RetValue, nStrs = 0;
    if ( !p->pSto && Sbd_ManMergeCuts( p, Pivot ) )
2078
        return;
2079 2080 2081 2082 2083 2084
    if ( !Sbd_ManWindow( p, Pivot ) )
        return;
    //if ( Vec_IntSize(p->vWinObjs) > 100 )
    //    printf( "Obj %d : Win = %d   TFO = %d.  Roots = %d.\n", Pivot, Vec_IntSize(p->vWinObjs), Vec_IntSize(p->vTfo), Vec_IntSize(p->vRoots) );
    p->nTried++;
    p->nUsed++;
2085 2086
    RetValue = Sbd_ManCheckConst( p, Pivot );
    if ( RetValue >= 0 )
2087
    {
2088
        Vec_IntWriteEntry( p->vMirrors, Pivot, RetValue );
2089
        //if ( p->pPars->fVerbose ) printf( "Node %5d:  Detected constant %d.\n", Pivot, RetValue );
2090
    }
2091
    else if ( p->pPars->fFindDivs && p->pPars->nLutNum >= 1 && Sbd_ManExplore2( p, Pivot, &Truth ) )
2092
    {
2093
        int i;
2094 2095 2096 2097 2098 2099
        Strs->fLut = 1;
        Strs->nVarIns = Vec_IntSize( p->vDivSet );
        for ( i = 0; i < Strs->nVarIns; i++ )
            Strs->VarIns[i] = i;
        Strs->Res = Truth;
        Sbd_ManImplement2( p, Pivot, 1, Strs );
2100
        //if ( p->pPars->fVerbose ) printf( "Node %5d:  Detected LUT%d\n", Pivot, p->pPars->nLutSize );
2101
    }
2102
    else if ( p->pPars->nLutNum >= 2 && Sbd_ManExplore3( p, Pivot, &nStrs, Strs ) )
2103
    {
2104
        Sbd_ManImplement2( p, Pivot, nStrs, Strs );
2105 2106
        if ( !p->pPars->fVerbose ) 
            return;
2107 2108 2109 2110 2111 2112
        //if ( Vec_IntSize(p->vDivSet) <= 4 )
        //    printf( "Node %5d:  Detected %d\n", Pivot, p->pPars->nLutSize );
        //else if ( Vec_IntSize(p->vDivSet) <= 6 || (Vec_IntSize(p->vDivSet) == 7 && nStrs == 2) )
        //    printf( "Node %5d:  Detected %d%d\n", Pivot, p->pPars->nLutSize, p->pPars->nLutSize );
        //else 
        //    printf( "Node %5d:  Detected %d%d%d\n", Pivot, p->pPars->nLutSize, p->pPars->nLutSize, p->pPars->nLutSize );
2113
    }
2114 2115
    else
        p->nUsed--;
2116
}
2117 2118
Gia_Man_t * Sbd_NtkPerform( Gia_Man_t * pGia, Sbd_Par_t * pPars )
{
2119
    Gia_Man_t * pNew;  
2120
    Gia_Obj_t * pObj;
2121
    Vec_Bit_t * vPath;
2122
    Sbd_Man_t * p = Sbd_ManStart( pGia, pPars );
2123
    int nNodesOld = Gia_ManObjNum(pGia);
2124
    int k, Pivot;
2125
    assert( pPars->nLutSize <= 6 );
2126 2127 2128
    // prepare references
    Gia_ManForEachObj( p->pGia, pObj, Pivot )
        Sbd_StoRefObj( p->pSto, Pivot, -1 );
2129
    //return NULL;
2130
    vPath = (pPars->fUsePath && Gia_ManHasMapping(pGia)) ? Sbc_ManCriticalPath(pGia) : NULL;
2131
    if ( pGia->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)pGia->pManTime) )
2132
    {
2133 2134 2135
        Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( pGia );
        Tim_Man_t * pTimOld = (Tim_Man_t *)pGia->pManTime;
        pGia->pManTime = Tim_ManDup( pTimOld, 1 );
2136
        //Tim_ManPrint( pGia->pManTime );
2137 2138
        Tim_ManIncrementTravId( (Tim_Man_t *)pGia->pManTime );
        Gia_ManForEachObjVec( vNodes, pGia, pObj, k )
2139
        {
2140 2141
            Pivot = Gia_ObjId( pGia, pObj );
            if ( Pivot >= nNodesOld )
2142
                break;
2143
            if ( Gia_ObjIsAnd(pObj) )
2144
            {
2145
                abctime clk = Abc_Clock();
2146
                int Delay = Sbd_StoComputeCutsNode( p->pSto, Pivot );
2147
                Sbd_StoSaveBestDelayCut( p->pSto, Pivot, Sbd_ObjCut(p, Pivot) );
2148
                p->timeCut += Abc_Clock() - clk;
2149
                Vec_IntWriteEntry( p->vLutLevs, Pivot, Delay );
2150
                if ( Delay > 1 && (!vPath || Vec_BitEntry(vPath, Pivot)) )
2151 2152
                    Sbd_NtkPerformOne( p, Pivot );
            }
2153 2154 2155 2156
            else if ( Gia_ObjIsCi(pObj) )
            {
                int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)pGia->pManTime, Gia_ObjCioId(pObj) );
                Vec_IntWriteEntry( p->vLutLevs, Pivot, arrTime );
2157
                Sbd_StoComputeCutsCi( p->pSto, Pivot, arrTime, arrTime );
2158 2159 2160 2161 2162 2163
            }
            else if ( Gia_ObjIsCo(pObj) )
            {
                int arrTime = Vec_IntEntry( p->vLutLevs, Gia_ObjFaninId0(pObj, Pivot) );
                Tim_ManSetCoArrival( (Tim_Man_t*)pGia->pManTime, Gia_ObjCioId(pObj), arrTime );
            }
2164 2165 2166
            else if ( Gia_ObjIsConst0(pObj) )
                Sbd_StoComputeCutsConst0( p->pSto, 0 );
            else assert( 0 );
2167
        }
2168 2169 2170 2171 2172 2173
        Tim_ManStop( (Tim_Man_t *)pGia->pManTime );
        pGia->pManTime = pTimOld;
        Vec_IntFree( vNodes );
    }
    else
    {
2174
        Sbd_StoComputeCutsConst0( p->pSto, 0 );
2175
        Gia_ManForEachObj( pGia, pObj, Pivot )
2176
        {
2177
            if ( Pivot >= nNodesOld )
2178
                break;
2179 2180 2181
            if ( Gia_ObjIsCi(pObj) )
                Sbd_StoComputeCutsCi( p->pSto, Pivot, 0, 0 );
            else if ( Gia_ObjIsAnd(pObj) )
2182
            {
2183
                abctime clk = Abc_Clock();
2184
                int Delay = Sbd_StoComputeCutsNode( p->pSto, Pivot );
2185
                Sbd_StoSaveBestDelayCut( p->pSto, Pivot, Sbd_ObjCut(p, Pivot) );
2186
                p->timeCut += Abc_Clock() - clk;
2187
                Vec_IntWriteEntry( p->vLutLevs, Pivot, Delay );
2188
                if ( Delay > 1 && (!vPath || Vec_BitEntry(vPath, Pivot)) )
2189 2190
                    Sbd_NtkPerformOne( p, Pivot );
            }
2191 2192
            //if ( nNodesOld != Gia_ManObjNum(pGia) )
            //    break;
2193
        }
2194
    }
2195
    Vec_BitFreeP( &vPath );
2196
    p->timeTotal = Abc_Clock() - p->timeTotal;
2197 2198 2199 2200 2201 2202 2203 2204
    if ( p->pPars->fVerbose )
    {
        printf( "K = %d. S = %d. N = %d. P = %d.  ", 
            p->pPars->nLutSize, p->pPars->nLutNum, p->pPars->nCutSize, p->pPars->nCutNum );
        printf( "Try = %d. Use = %d.  C = %d. 1 = %d. 2 = %d. 3a = %d. 3b = %d.  Lev = %d.  ", 
            p->nTried, p->nUsed, p->nLuts[0], p->nLuts[1], p->nLuts[2], p->nLuts[3], p->nLuts[4], Sbd_ManDelay(p) );
        Abc_PrintTime( 1, "Time", p->timeTotal );
    }
2205
    pNew = Sbd_ManDerive( p, pGia, p->vMirrors );
2206
    // print runtime statistics
2207
    p->timeOther = p->timeTotal - p->timeWin - p->timeCut - p->timeCov - p->timeCnf - p->timeSat - p->timeQbf;
2208
    if ( p->pPars->fVerbose )
2209 2210
    {
        ABC_PRTP( "Win", p->timeWin  ,  p->timeTotal );
2211 2212
        ABC_PRTP( "Cut", p->timeCut  ,  p->timeTotal );
        ABC_PRTP( "Cov", p->timeCov  ,  p->timeTotal );
2213 2214
        ABC_PRTP( "Cnf", p->timeCnf  ,  p->timeTotal );
        ABC_PRTP( "Sat", p->timeSat  ,  p->timeTotal );
2215
        ABC_PRTP( "Qbf", p->timeQbf  ,  p->timeTotal );
2216 2217 2218
        ABC_PRTP( "Oth", p->timeOther,  p->timeTotal );
        ABC_PRTP( "ALL", p->timeTotal,  p->timeTotal );
    }
2219 2220 2221
    Sbd_ManStop( p );
    return pNew;
}
2222 2223 2224 2225 2226 2227 2228 2229

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


ABC_NAMESPACE_IMPL_END