darCore.c 11.2 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
/**CFile****************************************************************

  FileName    [darCore.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [DAG-aware AIG rewriting.]

  Synopsis    [Core of the rewriting package.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - April 28, 2007.]

  Revision    [$Id: darCore.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]

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

Alan Mishchenko committed
21
#include "darInt.h"
Alan Mishchenko committed
22

23 24 25
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
26 27 28 29
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

30 31 32 33 34 35
// iterator over the nodes in the topological order
#define Aig_ManForEachNodeInOrder( p, pObj )                                    \
    for ( assert(p->pOrderData), p->iPrev = 0, p->iNext = p->pOrderData[1];     \
          p->iNext && (((pObj) = Aig_ManObj(p, p->iNext)), 1);                  \
          p->iNext = p->pOrderData[2*p->iPrev+1] )

Alan Mishchenko committed
36 37 38 39 40 41
////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

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

Alan Mishchenko committed
42 43 44 45 46 47 48 49 50
  Synopsis    [Returns the structure with default assignment of parameters.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
51
void Dar_ManDefaultRwrParams( Dar_RwrPar_t * pPars )
Alan Mishchenko committed
52
{
Alan Mishchenko committed
53
    memset( pPars, 0, sizeof(Dar_RwrPar_t) );
Alan Mishchenko committed
54
    pPars->nCutsMax     =  8; // 8
Alan Mishchenko committed
55
    pPars->nSubgMax     =  5; // 5 is a "magic number"
Alan Mishchenko committed
56
    pPars->fFanout      =  1;
Alan Mishchenko committed
57 58
    pPars->fUpdateLevel =  0;
    pPars->fUseZeros    =  0;
Alan Mishchenko committed
59
    pPars->fPower       =  0;
Alan Mishchenko committed
60
    pPars->fRecycle     =  1;
Alan Mishchenko committed
61 62
    pPars->fVerbose     =  0;
    pPars->fVeryVerbose =  0;
Alan Mishchenko committed
63 64
}

65 66
#define MAX_VAL 10

Alan Mishchenko committed
67 68
/**Function*************************************************************

Alan Mishchenko committed
69 70 71 72 73 74 75 76 77
  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
78
int Dar_ManRewrite( Aig_Man_t * pAig, Dar_RwrPar_t * pPars )
Alan Mishchenko committed
79
{
Alan Mishchenko committed
80
    extern Vec_Int_t * Saig_ManComputeSwitchProbs( Aig_Man_t * p, int nFrames, int nPref, int fProbOne );
Alan Mishchenko committed
81
    Dar_Man_t * p;
Alan Mishchenko committed
82
//    Bar_Progress_t * pProgress;
Alan Mishchenko committed
83 84
    Dar_Cut_t * pCut;
    Aig_Obj_t * pObj, * pObjNew;
Alan Mishchenko committed
85
    int i, k, nNodesOld, nNodeBefore, nNodeAfter, Required;
86 87
    clock_t clk = 0, clkStart;
    int Counter = 0;
88
    int nMffcSize;//, nMffcGains[MAX_VAL+1][MAX_VAL+1] = {{0}};
Alan Mishchenko committed
89 90
    // prepare the library
    Dar_LibPrepare( pPars->nSubgMax ); 
Alan Mishchenko committed
91 92
    // create rewriting manager
    p = Dar_ManStart( pAig, pPars );
Alan Mishchenko committed
93 94
    if ( pPars->fPower )
        pAig->vProbs = Saig_ManComputeSwitchProbs( pAig, 48, 16, 1 );
Alan Mishchenko committed
95
    // remove dangling nodes
Alan Mishchenko committed
96
    Aig_ManCleanup( pAig );
Alan Mishchenko committed
97
    // if updating levels is requested, start fanout and timing
Alan Mishchenko committed
98 99
    if ( p->pPars->fFanout )
        Aig_ManFanoutStart( pAig );
Alan Mishchenko committed
100 101
    if ( p->pPars->fUpdateLevel )
        Aig_ManStartReverseLevels( pAig, 0 );
Alan Mishchenko committed
102
    // set elementary cuts for the PIs
Alan Mishchenko committed
103
//    Dar_ManCutsStart( p );
Alan Mishchenko committed
104
    // resynthesize each node once
Alan Mishchenko committed
105
    clkStart = clock();
Alan Mishchenko committed
106 107
    p->nNodesInit = Aig_ManNodeNum(pAig);
    nNodesOld = Vec_PtrSize( pAig->vObjs );
Alan Mishchenko committed
108

Alan Mishchenko committed
109
//    pProgress = Bar_ProgressStart( stdout, nNodesOld );
Alan Mishchenko committed
110
    Aig_ManForEachObj( pAig, pObj, i )
Alan Mishchenko committed
111
//    pProgress = Bar_ProgressStart( stdout, 100 );
Alan Mishchenko committed
112 113
//    Aig_ManOrderStart( pAig );
//    Aig_ManForEachNodeInOrder( pAig, pObj )
Alan Mishchenko committed
114
    {
Alan Mishchenko committed
115
//        Bar_ProgressUpdate( pProgress, 100*pAig->nAndPrev/pAig->nAndTotal, NULL );
Alan Mishchenko committed
116
//        Bar_ProgressUpdate( pProgress, i, NULL );
Alan Mishchenko committed
117
        if ( !Aig_ObjIsNode(pObj) )
Alan Mishchenko committed
118 119
            continue;
        if ( i > nNodesOld )
Alan Mishchenko committed
120
//        if ( p->pPars->fUseZeros && i > nNodesOld )
Alan Mishchenko committed
121
            break;
Alan Mishchenko committed
122 123 124 125 126 127 128
        if ( pPars->fRecycle && ++Counter % 50000 == 0 && Aig_DagSize(pObj) < Vec_PtrSize(p->vCutNodes)/100 )
        {
//            printf( "Counter = %7d.  Node = %7d.  Dag = %5d. Vec = %5d.\n", 
//                Counter, i, Aig_DagSize(pObj), Vec_PtrSize(p->vCutNodes) );
//            fflush( stdout );
            Dar_ManCutsRestart( p, pObj );
        }
Alan Mishchenko committed
129

Alan Mishchenko committed
130 131 132 133
        // consider freeing the cuts
//        if ( (i & 0xFFF) == 0 && Aig_MmFixedReadMemUsage(p->pMemCuts)/(1<<20) > 100 )
//            Dar_ManCutsStart( p );

Alan Mishchenko committed
134
        // compute cuts for the node
Alan Mishchenko committed
135
        p->nNodesTried++;
Alan Mishchenko committed
136
clk = clock();
Alan Mishchenko committed
137
        Dar_ObjSetCuts( pObj, NULL );
Alan Mishchenko committed
138
        Dar_ObjComputeCuts_rec( p, pObj );
Alan Mishchenko committed
139
p->timeCuts += clock() - clk;
Alan Mishchenko committed
140 141 142

        // check if there is a trivial cut
        Dar_ObjForEachCut( pObj, pCut, k )
Alan Mishchenko committed
143
            if ( pCut->nLeaves == 0 || (pCut->nLeaves == 1 && pCut->pLeaves[0] != pObj->Id && Aig_ManObj(p->pAig, pCut->pLeaves[0])) )
Alan Mishchenko committed
144 145
                break;
        if ( k < (int)pObj->nCuts )
Alan Mishchenko committed
146
        {
Alan Mishchenko committed
147 148
            assert( pCut->nLeaves < 2 );
            if ( pCut->nLeaves == 0 ) // replace by constant
Alan Mishchenko committed
149
            {
Alan Mishchenko committed
150 151
                assert( pCut->uTruth == 0 || pCut->uTruth == 0xFFFF );
                pObjNew = Aig_NotCond( Aig_ManConst1(p->pAig), pCut->uTruth==0 );
Alan Mishchenko committed
152
            }
Alan Mishchenko committed
153 154 155 156 157 158 159
            else
            {
                assert( pCut->uTruth == 0xAAAA || pCut->uTruth == 0x5555 );
                pObjNew = Aig_NotCond( Aig_ManObj(p->pAig, pCut->pLeaves[0]), pCut->uTruth==0x5555 );
            }
            // remove the old cuts
            Dar_ObjSetCuts( pObj, NULL );
Alan Mishchenko committed
160
            // replace the node
Alan Mishchenko committed
161
            Aig_ObjReplace( pAig, pObj, pObjNew, p->pPars->fUpdateLevel );
Alan Mishchenko committed
162
            continue;
Alan Mishchenko committed
163
        }
Alan Mishchenko committed
164 165 166

        // evaluate the cuts
        p->GainBest = -1;
167 168
        nMffcSize   = -1;
        Required    = pAig->vLevelR? Aig_ObjRequiredLevel(pAig, pObj) : ABC_INFINITY;
Alan Mishchenko committed
169
        Dar_ObjForEachCut( pObj, pCut, k )
170 171 172 173
        {
            int nLeavesOld = pCut->nLeaves;
            if ( pCut->nLeaves == 3 )
                pCut->pLeaves[pCut->nLeaves++] = 0;
174
            Dar_LibEval( p, pObj, pCut, Required, &nMffcSize );
175 176
            pCut->nLeaves = nLeavesOld; 
        }
Alan Mishchenko committed
177
        // check the best gain
Alan Mishchenko committed
178
        if ( !(p->GainBest > 0 || (p->GainBest == 0 && p->pPars->fUseZeros)) )
Alan Mishchenko committed
179 180
        {
//            Aig_ObjOrderAdvance( pAig );
Alan Mishchenko committed
181
            continue;
Alan Mishchenko committed
182
        }
183
//        nMffcGains[p->GainBest < MAX_VAL ? p->GainBest : MAX_VAL][nMffcSize < MAX_VAL ? nMffcSize : MAX_VAL]++;
Alan Mishchenko committed
184 185
        // remove the old cuts
        Dar_ObjSetCuts( pObj, NULL );
Alan Mishchenko committed
186
        // if we end up here, a rewriting step is accepted
Alan Mishchenko committed
187
        nNodeBefore = Aig_ManNodeNum( pAig );
Alan Mishchenko committed
188 189
        pObjNew = Dar_LibBuildBest( p ); // pObjNew can be complemented!
        pObjNew = Aig_NotCond( pObjNew, Aig_ObjPhaseReal(pObjNew) ^ pObj->fPhase );
Alan Mishchenko committed
190
        assert( (int)Aig_Regular(pObjNew)->Level <= Required );
Alan Mishchenko committed
191
        // replace the node
Alan Mishchenko committed
192
        Aig_ObjReplace( pAig, pObj, pObjNew, p->pPars->fUpdateLevel );
Alan Mishchenko committed
193
        // compare the gains
Alan Mishchenko committed
194
        nNodeAfter = Aig_ManNodeNum( pAig );
Alan Mishchenko committed
195 196 197
        assert( p->GainBest <= nNodeBefore - nNodeAfter );
        // count gains of this class
        p->ClassGains[p->ClassBest] += nNodeBefore - nNodeAfter;
Alan Mishchenko committed
198
    }
Alan Mishchenko committed
199
//    Aig_ManOrderStop( pAig );
200 201 202 203 204 205 206 207 208 209 210 211
/*
    printf( "Distribution of gain (row) by MFFC size (column) %s 0-costs:\n", p->pPars->fUseZeros? "with":"without" );
    for ( k = 0; k <= MAX_VAL; k++ )
        printf( "<%4d> ", k );
    printf( "\n" );
    for ( i = 0; i <= MAX_VAL; i++ )
    {
        for ( k = 0; k <= MAX_VAL; k++ )
            printf( "%6d ", nMffcGains[i][k] );
        printf( "\n" );
    }
*/
Alan Mishchenko committed
212

Alan Mishchenko committed
213 214 215
p->timeTotal = clock() - clkStart;
p->timeOther = p->timeTotal - p->timeCuts - p->timeEval;

Alan Mishchenko committed
216
//    Bar_ProgressStop( pProgress );
Alan Mishchenko committed
217 218
    Dar_ManCutsFree( p );
    // put the nodes into the DFS order and reassign their IDs
Alan Mishchenko committed
219
//    Aig_NtkReassignIds( p );
Alan Mishchenko committed
220
    // fix the levels
Alan Mishchenko committed
221 222 223
//    Aig_ManVerifyLevel( pAig );
    if ( p->pPars->fFanout )
        Aig_ManFanoutStop( pAig );
Alan Mishchenko committed
224
    if ( p->pPars->fUpdateLevel )
Alan Mishchenko committed
225 226
    {
//        Aig_ManVerifyReverseLevel( pAig );
Alan Mishchenko committed
227
        Aig_ManStopReverseLevels( pAig );
Alan Mishchenko committed
228
    }
Alan Mishchenko committed
229 230 231 232 233
    if ( pAig->vProbs )
    {
        Vec_IntFree( pAig->vProbs );
        pAig->vProbs = NULL;
    }
Alan Mishchenko committed
234 235
    // stop the rewriting manager
    Dar_ManStop( p );
Alan Mishchenko committed
236
    Aig_ManCheckPhase( pAig );
Alan Mishchenko committed
237
    // check
Alan Mishchenko committed
238
    if ( !Aig_ManCheck( pAig ) )
Alan Mishchenko committed
239
    {
Alan Mishchenko committed
240
        printf( "Aig_ManRewrite: The network check has failed.\n" );
Alan Mishchenko committed
241 242 243 244 245
        return 0;
    }
    return 1;
}

Alan Mishchenko committed
246 247
/**Function*************************************************************

Alan Mishchenko committed
248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
  Synopsis    [Computes the total number of cuts.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Dar_ManCutCount( Aig_Man_t * pAig, int * pnCutsK )
{
    Dar_Cut_t * pCut;
    Aig_Obj_t * pObj;
    int i, k, nCuts = 0, nCutsK = 0;
    Aig_ManForEachNode( pAig, pObj, i )
        Dar_ObjForEachCut( pObj, pCut, k )
        {
            nCuts++;
            if ( pCut->nLeaves == 4 )
                nCutsK++;
        }
    if ( pnCutsK )
        *pnCutsK = nCutsK;
    return nCuts;
}

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

Alan Mishchenko committed
276 277 278 279 280 281 282 283 284
  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
285 286
Aig_MmFixed_t * Dar_ManComputeCuts( Aig_Man_t * pAig, int nCutsMax, int fSkipTtMin, int fVerbose )
{ 
Alan Mishchenko committed
287
    Dar_Man_t * p;
Alan Mishchenko committed
288
    Dar_RwrPar_t Pars, * pPars = &Pars; 
Alan Mishchenko committed
289 290
    Aig_Obj_t * pObj;
    Aig_MmFixed_t * pMemCuts;
291 292
    int i, nNodes;
    clock_t clk = clock();
Alan Mishchenko committed
293
    // remove dangling nodes
Alan Mishchenko committed
294
    if ( (nNodes = Aig_ManCleanup( pAig )) )
Alan Mishchenko committed
295 296 297
    {
//        printf( "Removing %d nodes.\n", nNodes );
    }
Alan Mishchenko committed
298 299 300 301 302
    // create default parameters
    Dar_ManDefaultRwrParams( pPars );
    pPars->nCutsMax = nCutsMax;
    // create rewriting manager
    p = Dar_ManStart( pAig, pPars );
Alan Mishchenko committed
303
    // set elementary cuts for the PIs
Alan Mishchenko committed
304 305 306
//    Dar_ManCutsStart( p );
    Aig_MmFixedRestart( p->pMemCuts );
    Dar_ObjPrepareCuts( p, Aig_ManConst1(p->pAig) );
307
    Aig_ManForEachCi( pAig, pObj, i )
Alan Mishchenko committed
308
        Dar_ObjPrepareCuts( p, pObj );
Alan Mishchenko committed
309
    // compute cuts for each nodes in the topological order
Alan Mishchenko committed
310
    Aig_ManForEachNode( pAig, pObj, i )
311
        Dar_ObjComputeCuts( p, pObj, fSkipTtMin );
Alan Mishchenko committed
312 313 314 315 316 317 318 319
    // print verbose stats
    if ( fVerbose )
    {
//        Aig_Obj_t * pObj;
        int nCuts, nCutsK;//, i;
        nCuts = Dar_ManCutCount( pAig, &nCutsK );
        printf( "Nodes = %6d. Total cuts = %6d. 4-input cuts = %6d.\n",
            Aig_ManObjNum(pAig), nCuts, nCutsK );
320
        printf( "Cut size = %2d. Truth size = %2d. Total mem = %5.2f MB  ",
Alan Mishchenko committed
321
            (int)sizeof(Dar_Cut_t), (int)4, 1.0*Aig_MmFixedReadMemUsage(p->pMemCuts)/(1<<20) );
Alan Mishchenko committed
322
        ABC_PRT( "Runtime", clock() - clk );
Alan Mishchenko committed
323 324 325 326 327 328
/*
        Aig_ManForEachNode( pAig, pObj, i )
            if ( i % 300 == 0 )
                Dar_ObjCutPrint( pAig, pObj );
*/
    }
Alan Mishchenko committed
329
    // free the cuts
Alan Mishchenko committed
330 331
    pMemCuts = p->pMemCuts;
    p->pMemCuts = NULL;
Alan Mishchenko committed
332
//    Dar_ManCutsFree( p );
Alan Mishchenko committed
333 334 335
    // stop the rewriting manager
    Dar_ManStop( p );
    return pMemCuts;
Alan Mishchenko committed
336 337
}

Alan Mishchenko committed
338 339


Alan Mishchenko committed
340 341 342 343 344
////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


345 346
ABC_NAMESPACE_IMPL_END