darCore.c 10.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 30 31 32 33 34 35
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

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

Alan Mishchenko committed
36 37 38 39 40 41 42 43 44
  Synopsis    [Returns the structure with default assignment of parameters.]

  Description []
               
  SideEffects []

  SeeAlso     []

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

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

Alan Mishchenko committed
61 62 63 64 65 66 67 68 69
  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

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

Alan Mishchenko committed
99
//    pProgress = Bar_ProgressStart( stdout, nNodesOld );
Alan Mishchenko committed
100
    Aig_ManForEachObj( pAig, pObj, i )
Alan Mishchenko committed
101
//    pProgress = Bar_ProgressStart( stdout, 100 );
Alan Mishchenko committed
102 103
//    Aig_ManOrderStart( pAig );
//    Aig_ManForEachNodeInOrder( pAig, pObj )
Alan Mishchenko committed
104
    {
Alan Mishchenko committed
105
//        Bar_ProgressUpdate( pProgress, 100*pAig->nAndPrev/pAig->nAndTotal, NULL );
Alan Mishchenko committed
106
//        Bar_ProgressUpdate( pProgress, i, NULL );
Alan Mishchenko committed
107
        if ( !Aig_ObjIsNode(pObj) )
Alan Mishchenko committed
108 109
            continue;
        if ( i > nNodesOld )
Alan Mishchenko committed
110
//        if ( p->pPars->fUseZeros && i > nNodesOld )
Alan Mishchenko committed
111
            break;
Alan Mishchenko committed
112 113 114 115 116 117 118
        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
119

Alan Mishchenko committed
120 121 122 123
        // consider freeing the cuts
//        if ( (i & 0xFFF) == 0 && Aig_MmFixedReadMemUsage(p->pMemCuts)/(1<<20) > 100 )
//            Dar_ManCutsStart( p );

Alan Mishchenko committed
124
        // compute cuts for the node
Alan Mishchenko committed
125
        p->nNodesTried++;
Alan Mishchenko committed
126
clk = clock();
Alan Mishchenko committed
127
        Dar_ObjSetCuts( pObj, NULL );
Alan Mishchenko committed
128
        Dar_ObjComputeCuts_rec( p, pObj );
Alan Mishchenko committed
129
p->timeCuts += clock() - clk;
Alan Mishchenko committed
130 131 132

        // check if there is a trivial cut
        Dar_ObjForEachCut( pObj, pCut, k )
Alan Mishchenko committed
133
            if ( pCut->nLeaves == 0 || (pCut->nLeaves == 1 && pCut->pLeaves[0] != pObj->Id && Aig_ManObj(p->pAig, pCut->pLeaves[0])) )
Alan Mishchenko committed
134 135
                break;
        if ( k < (int)pObj->nCuts )
Alan Mishchenko committed
136
        {
Alan Mishchenko committed
137 138
            assert( pCut->nLeaves < 2 );
            if ( pCut->nLeaves == 0 ) // replace by constant
Alan Mishchenko committed
139
            {
Alan Mishchenko committed
140 141
                assert( pCut->uTruth == 0 || pCut->uTruth == 0xFFFF );
                pObjNew = Aig_NotCond( Aig_ManConst1(p->pAig), pCut->uTruth==0 );
Alan Mishchenko committed
142
            }
Alan Mishchenko committed
143 144 145 146 147 148 149
            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
150
            // replace the node
Alan Mishchenko committed
151
            Aig_ObjReplace( pAig, pObj, pObjNew, p->pPars->fUpdateLevel );
Alan Mishchenko committed
152
            continue;
Alan Mishchenko committed
153
        }
Alan Mishchenko committed
154 155 156

        // evaluate the cuts
        p->GainBest = -1;
Alan Mishchenko committed
157
        Required = pAig->vLevelR? Aig_ObjRequiredLevel(pAig, pObj) : ABC_INFINITY;
Alan Mishchenko committed
158
        Dar_ObjForEachCut( pObj, pCut, k )
159 160 161 162
        {
            int nLeavesOld = pCut->nLeaves;
            if ( pCut->nLeaves == 3 )
                pCut->pLeaves[pCut->nLeaves++] = 0;
Alan Mishchenko committed
163
            Dar_LibEval( p, pObj, pCut, Required );
164 165
            pCut->nLeaves = nLeavesOld; 
        }
Alan Mishchenko committed
166
        // check the best gain
Alan Mishchenko committed
167
        if ( !(p->GainBest > 0 || (p->GainBest == 0 && p->pPars->fUseZeros)) )
Alan Mishchenko committed
168 169
        {
//            Aig_ObjOrderAdvance( pAig );
Alan Mishchenko committed
170
            continue;
Alan Mishchenko committed
171
        }
Alan Mishchenko committed
172 173
        // remove the old cuts
        Dar_ObjSetCuts( pObj, NULL );
Alan Mishchenko committed
174
        // if we end up here, a rewriting step is accepted
Alan Mishchenko committed
175
        nNodeBefore = Aig_ManNodeNum( pAig );
Alan Mishchenko committed
176 177
        pObjNew = Dar_LibBuildBest( p ); // pObjNew can be complemented!
        pObjNew = Aig_NotCond( pObjNew, Aig_ObjPhaseReal(pObjNew) ^ pObj->fPhase );
Alan Mishchenko committed
178
        assert( (int)Aig_Regular(pObjNew)->Level <= Required );
Alan Mishchenko committed
179
        // replace the node
Alan Mishchenko committed
180
        Aig_ObjReplace( pAig, pObj, pObjNew, p->pPars->fUpdateLevel );
Alan Mishchenko committed
181
        // compare the gains
Alan Mishchenko committed
182
        nNodeAfter = Aig_ManNodeNum( pAig );
Alan Mishchenko committed
183 184 185
        assert( p->GainBest <= nNodeBefore - nNodeAfter );
        // count gains of this class
        p->ClassGains[p->ClassBest] += nNodeBefore - nNodeAfter;
Alan Mishchenko committed
186
    }
Alan Mishchenko committed
187 188
//    Aig_ManOrderStop( pAig );

Alan Mishchenko committed
189 190 191
p->timeTotal = clock() - clkStart;
p->timeOther = p->timeTotal - p->timeCuts - p->timeEval;

Alan Mishchenko committed
192
//    Bar_ProgressStop( pProgress );
Alan Mishchenko committed
193 194
    Dar_ManCutsFree( p );
    // put the nodes into the DFS order and reassign their IDs
Alan Mishchenko committed
195
//    Aig_NtkReassignIds( p );
Alan Mishchenko committed
196
    // fix the levels
Alan Mishchenko committed
197 198 199
//    Aig_ManVerifyLevel( pAig );
    if ( p->pPars->fFanout )
        Aig_ManFanoutStop( pAig );
Alan Mishchenko committed
200
    if ( p->pPars->fUpdateLevel )
Alan Mishchenko committed
201 202
    {
//        Aig_ManVerifyReverseLevel( pAig );
Alan Mishchenko committed
203
        Aig_ManStopReverseLevels( pAig );
Alan Mishchenko committed
204
    }
Alan Mishchenko committed
205 206 207 208 209
    if ( pAig->vProbs )
    {
        Vec_IntFree( pAig->vProbs );
        pAig->vProbs = NULL;
    }
Alan Mishchenko committed
210 211
    // stop the rewriting manager
    Dar_ManStop( p );
Alan Mishchenko committed
212
    Aig_ManCheckPhase( pAig );
Alan Mishchenko committed
213
    // check
Alan Mishchenko committed
214
    if ( !Aig_ManCheck( pAig ) )
Alan Mishchenko committed
215
    {
Alan Mishchenko committed
216
        printf( "Aig_ManRewrite: The network check has failed.\n" );
Alan Mishchenko committed
217 218 219 220 221
        return 0;
    }
    return 1;
}

Alan Mishchenko committed
222 223
/**Function*************************************************************

Alan Mishchenko committed
224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251
  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
252 253 254 255 256 257 258 259 260
  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
261
Aig_MmFixed_t * Dar_ManComputeCuts( Aig_Man_t * pAig, int nCutsMax, int fVerbose )
Alan Mishchenko committed
262
{
Alan Mishchenko committed
263
    Dar_Man_t * p;
Alan Mishchenko committed
264
    Dar_RwrPar_t Pars, * pPars = &Pars; 
Alan Mishchenko committed
265 266
    Aig_Obj_t * pObj;
    Aig_MmFixed_t * pMemCuts;
Alan Mishchenko committed
267
    int i, nNodes, clk = clock();
Alan Mishchenko committed
268
    // remove dangling nodes
Alan Mishchenko committed
269
    if ( (nNodes = Aig_ManCleanup( pAig )) )
Alan Mishchenko committed
270 271 272
    {
//        printf( "Removing %d nodes.\n", nNodes );
    }
Alan Mishchenko committed
273 274 275 276 277
    // create default parameters
    Dar_ManDefaultRwrParams( pPars );
    pPars->nCutsMax = nCutsMax;
    // create rewriting manager
    p = Dar_ManStart( pAig, pPars );
Alan Mishchenko committed
278
    // set elementary cuts for the PIs
Alan Mishchenko committed
279 280 281 282 283
//    Dar_ManCutsStart( p );
    Aig_MmFixedRestart( p->pMemCuts );
    Dar_ObjPrepareCuts( p, Aig_ManConst1(p->pAig) );
    Aig_ManForEachPi( pAig, pObj, i )
        Dar_ObjPrepareCuts( p, pObj );
Alan Mishchenko committed
284
    // compute cuts for each nodes in the topological order
Alan Mishchenko committed
285
    Aig_ManForEachNode( pAig, pObj, i )
Alan Mishchenko committed
286
        Dar_ObjComputeCuts( p, pObj );
Alan Mishchenko committed
287 288 289 290 291 292 293 294 295
    // 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 );
        printf( "Cut size = %2d. Truth size = %2d. Total mem = %5.2f Mb  ",
Alan Mishchenko committed
296
            (int)sizeof(Dar_Cut_t), (int)4, 1.0*Aig_MmFixedReadMemUsage(p->pMemCuts)/(1<<20) );
Alan Mishchenko committed
297
        ABC_PRT( "Runtime", clock() - clk );
Alan Mishchenko committed
298 299 300 301 302 303
/*
        Aig_ManForEachNode( pAig, pObj, i )
            if ( i % 300 == 0 )
                Dar_ObjCutPrint( pAig, pObj );
*/
    }
Alan Mishchenko committed
304
    // free the cuts
Alan Mishchenko committed
305 306
    pMemCuts = p->pMemCuts;
    p->pMemCuts = NULL;
Alan Mishchenko committed
307
//    Dar_ManCutsFree( p );
Alan Mishchenko committed
308 309 310
    // stop the rewriting manager
    Dar_ManStop( p );
    return pMemCuts;
Alan Mishchenko committed
311 312
}

Alan Mishchenko committed
313 314


Alan Mishchenko committed
315 316 317 318 319
////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


320 321
ABC_NAMESPACE_IMPL_END