abcRefactor.c 13.7 KB
Newer Older
Alan Mishchenko committed
1 2
/**CFile****************************************************************

Alan Mishchenko committed
3
  FileName    [abcRefactor.c]
Alan Mishchenko committed
4 5 6 7 8

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Network and node package.]

Alan Mishchenko committed
9
  Synopsis    [Resynthesis based on collapsing and refactoring.]
Alan Mishchenko committed
10 11 12 13 14 15 16

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "abc.h"
Alan Mishchenko committed
22
#include "dec.h"
23
#include "extra.h"
Alan Mishchenko committed
24

25 26 27
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
28 29 30 31 32 33 34 35
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////
 
typedef struct Abc_ManRef_t_   Abc_ManRef_t;
struct Abc_ManRef_t_
{
    // user specified parameters
Alan Mishchenko committed
36 37 38 39 40 41 42 43 44 45 46 47 48 49
    int              nNodeSizeMax;      // the limit on the size of the supernode
    int              nConeSizeMax;      // the limit on the size of the containing cone
    int              fVerbose;          // the verbosity flag
    // internal data structures
    DdManager *      dd;                // the BDD manager
    Vec_Str_t *      vCube;             // temporary
    Vec_Int_t *      vForm;             // temporary
    Vec_Ptr_t *      vVisited;          // temporary
    Vec_Ptr_t *      vLeaves;           // temporary
    // node statistics
    int              nLastGain;
    int              nNodesConsidered;
    int              nNodesRefactored;
    int              nNodesGained;
Alan Mishchenko committed
50 51
    int              nNodesBeg;
    int              nNodesEnd;
Alan Mishchenko committed
52
    // runtime statistics
Alan Mishchenko committed
53 54 55 56 57
    int              timeCut;
    int              timeBdd;
    int              timeDcs;
    int              timeSop;
    int              timeFact;
Alan Mishchenko committed
58
    int              timeEval;
Alan Mishchenko committed
59 60 61
    int              timeRes;
    int              timeNtk;
    int              timeTotal;
Alan Mishchenko committed
62
};
Alan Mishchenko committed
63 64
 
static void           Abc_NtkManRefPrintStats( Abc_ManRef_t * p );
65
static Abc_ManRef_t * Abc_NtkManRefStart( int nNodeSizeMax, int nConeSizeMax, int fUseDcs, int fVerbose );
Alan Mishchenko committed
66
static void           Abc_NtkManRefStop( Abc_ManRef_t * p );
67
static Dec_Graph_t *  Abc_NodeRefactor( Abc_ManRef_t * p, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, int fUpdateLevel, int fUseZeros, int fUseDcs, int fVerbose );
Alan Mishchenko committed
68 69

////////////////////////////////////////////////////////////////////////
Alan Mishchenko committed
70
///                     FUNCTION DEFINITIONS                         ///
Alan Mishchenko committed
71 72 73 74 75 76 77
////////////////////////////////////////////////////////////////////////

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

  Synopsis    [Performs incremental resynthesis of the AIG.]

  Description [Starting from each node, computes a reconvergence-driven cut, 
Alan Mishchenko committed
78 79 80 81
  derives BDD of the cut function, constructs ISOP, factors the ISOP, 
  and replaces the current implementation of the MFFC of the node by the 
  new factored form, if the number of AIG nodes is reduced and the total
  number of levels of the AIG network is not increated. Returns the
Alan Mishchenko committed
82 83 84 85 86 87 88
  number of AIG nodes saved.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
89
int Abc_NtkRefactor( Abc_Ntk_t * pNtk, int nNodeSizeMax, int nConeSizeMax, int fUpdateLevel, int fUseZeros, int fUseDcs, int fVerbose )
Alan Mishchenko committed
90
{
91
    extern void           Dec_GraphUpdateNetwork( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int fUpdateLevel, int nGain );
Alan Mishchenko committed
92 93 94
    ProgressBar * pProgress;
    Abc_ManRef_t * pManRef;
    Abc_ManCut_t * pManCut;
Alan Mishchenko committed
95
    Dec_Graph_t * pFForm;
Alan Mishchenko committed
96 97
    Vec_Ptr_t * vFanins;
    Abc_Obj_t * pNode;
Alan Mishchenko committed
98
    int clk, clkStart = clock();
Alan Mishchenko committed
99
    int i, nNodes;
Alan Mishchenko committed
100

Alan Mishchenko committed
101
    assert( Abc_NtkIsStrash(pNtk) );
Alan Mishchenko committed
102
    // cleanup the AIG
103
    Abc_AigCleanup((Abc_Aig_t *)pNtk->pManFunc);
Alan Mishchenko committed
104
    // start the managers
Alan Mishchenko committed
105
    pManCut = Abc_NtkManCutStart( nNodeSizeMax, nConeSizeMax, 2, 1000 );
Alan Mishchenko committed
106
    pManRef = Abc_NtkManRefStart( nNodeSizeMax, nConeSizeMax, fUseDcs, fVerbose );
Alan Mishchenko committed
107
    pManRef->vLeaves   = Abc_NtkManCutReadCutLarge( pManCut );
Alan Mishchenko committed
108 109 110
    // compute the reverse levels if level update is requested
    if ( fUpdateLevel )
        Abc_NtkStartReverseLevels( pNtk, 0 );
Alan Mishchenko committed
111 112

    // resynthesize each node once
Alan Mishchenko committed
113
    pManRef->nNodesBeg = Abc_NtkNodeNum(pNtk);
Alan Mishchenko committed
114 115 116 117
    nNodes = Abc_NtkObjNumMax(pNtk);
    pProgress = Extra_ProgressBarStart( stdout, nNodes );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
Alan Mishchenko committed
118 119
        Extra_ProgressBarUpdate( pProgress, i, NULL );
        // skip the constant node
Alan Mishchenko committed
120 121 122 123
//        if ( Abc_NodeIsConst(pNode) )
//            continue;
        // skip persistant nodes
        if ( Abc_NodeIsPersistant(pNode) )
Alan Mishchenko committed
124
            continue;
Alan Mishchenko committed
125 126 127
        // skip the nodes with many fanouts
        if ( Abc_ObjFanoutNum(pNode) > 1000 )
            continue;
Alan Mishchenko committed
128 129 130
        // stop if all nodes have been tried once
        if ( i >= nNodes )
            break;
Alan Mishchenko committed
131
        // compute a reconvergence-driven cut
Alan Mishchenko committed
132 133 134
clk = clock();
        vFanins = Abc_NodeFindCut( pManCut, pNode, fUseDcs );
pManRef->timeCut += clock() - clk;
Alan Mishchenko committed
135
        // evaluate this cut
Alan Mishchenko committed
136
clk = clock();
Alan Mishchenko committed
137
        pFForm = Abc_NodeRefactor( pManRef, pNode, vFanins, fUpdateLevel, fUseZeros, fUseDcs, fVerbose );
Alan Mishchenko committed
138
pManRef->timeRes += clock() - clk;
Alan Mishchenko committed
139
        if ( pFForm == NULL )
Alan Mishchenko committed
140 141 142
            continue;
        // acceptable replacement found, update the graph
clk = clock();
Alan Mishchenko committed
143
        Dec_GraphUpdateNetwork( pNode, pFForm, fUpdateLevel, pManRef->nLastGain );
Alan Mishchenko committed
144
pManRef->timeNtk += clock() - clk;
Alan Mishchenko committed
145
        Dec_GraphFree( pFForm );
Alan Mishchenko committed
146 147 148 149
//    {
//        extern int s_TotalChanges;
//        s_TotalChanges++;
//    }
Alan Mishchenko committed
150 151
    }
    Extra_ProgressBarStop( pProgress );
Alan Mishchenko committed
152
pManRef->timeTotal = clock() - clkStart;
Alan Mishchenko committed
153
    pManRef->nNodesEnd = Abc_NtkNodeNum(pNtk);
Alan Mishchenko committed
154

Alan Mishchenko committed
155 156 157
    // print statistics of the manager
    if ( fVerbose )
        Abc_NtkManRefPrintStats( pManRef );
Alan Mishchenko committed
158 159 160
    // delete the managers
    Abc_NtkManCutStop( pManCut );
    Abc_NtkManRefStop( pManRef );
Alan Mishchenko committed
161 162 163 164 165 166 167 168
    // put the nodes into the DFS order and reassign their IDs
    Abc_NtkReassignIds( pNtk );
//    Abc_AigCheckFaninOrder( pNtk->pManFunc );
    // fix the levels
    if ( fUpdateLevel )
        Abc_NtkStopReverseLevels( pNtk );
    else
        Abc_NtkLevel( pNtk );
Alan Mishchenko committed
169
    // check
Alan Mishchenko committed
170
    if ( !Abc_NtkCheck( pNtk ) )
Alan Mishchenko committed
171
    {
Alan Mishchenko committed
172
        printf( "Abc_NtkRefactor: The network check has failed.\n" );
Alan Mishchenko committed
173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188
        return 0;
    }
    return 1;
}

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

  Synopsis    [Resynthesizes the node using refactoring.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
189
Dec_Graph_t * Abc_NodeRefactor( Abc_ManRef_t * p, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, int fUpdateLevel, int fUseZeros, int fUseDcs, int fVerbose )
Alan Mishchenko committed
190
{
191 192 193 194
    extern DdNode * Abc_NodeConeBdd( DdManager * dd, DdNode ** pbVars, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, Vec_Ptr_t * vVisited );
    extern DdNode * Abc_NodeConeDcs( DdManager * dd, DdNode ** pbVarsX, DdNode ** pbVarsY, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots, Vec_Ptr_t * vVisited );
    extern char * Abc_ConvertBddToSop( Mem_Flex_t * pMan, DdManager * dd, DdNode * bFuncOn, DdNode * bFuncOnDc, int nFanins, int fAllPrimes, Vec_Str_t * vCube, int fMode );
    extern int    Dec_GraphToNetworkCount( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int NodeMax, int LevelMax );
Alan Mishchenko committed
195 196
    int fVeryVerbose = 0;
    Abc_Obj_t * pFanin;
Alan Mishchenko committed
197 198 199
    Dec_Graph_t * pFForm;
    DdNode * bNodeFunc;
    int nNodesSaved, nNodesAdded, i, clk;
Alan Mishchenko committed
200
    char * pSop;
Alan Mishchenko committed
201 202 203
    int Required;

    Required = fUpdateLevel? Abc_ObjRequiredLevel(pNode) : ABC_INFINITY;
Alan Mishchenko committed
204 205

    p->nNodesConsidered++;
Alan Mishchenko committed
206

Alan Mishchenko committed
207 208 209 210 211 212 213 214
    // get the function of the cut
clk = clock();
    bNodeFunc = Abc_NodeConeBdd( p->dd, p->dd->vars, pNode, vFanins, p->vVisited );  Cudd_Ref( bNodeFunc );
p->timeBdd += clock() - clk;

    // if don't-care are used, transform the function into ISOP
    if ( fUseDcs )
    {
Alan Mishchenko committed
215
        DdNode * bNodeDc, * bNodeOn, * bNodeOnDc;
Alan Mishchenko committed
216 217 218 219 220 221
        int nMints, nMintsDc;
clk = clock();
        // get the don't-cares
        bNodeDc = Abc_NodeConeDcs( p->dd, p->dd->vars + vFanins->nSize, p->dd->vars, p->vLeaves, vFanins, p->vVisited ); Cudd_Ref( bNodeDc );
        nMints = (1 << vFanins->nSize);
        nMintsDc = (int)Cudd_CountMinterm( p->dd, bNodeDc, vFanins->nSize );
Alan Mishchenko committed
222
//        printf( "Percentage of minterms = %5.2f.\n", 100.0 * nMintsDc / nMints );
Alan Mishchenko committed
223 224 225 226 227 228 229 230 231 232 233 234 235 236 237
        // get the ISF
        bNodeOn   = Cudd_bddAnd( p->dd, bNodeFunc, Cudd_Not(bNodeDc) );   Cudd_Ref( bNodeOn );
        bNodeOnDc = Cudd_bddOr ( p->dd, bNodeFunc, bNodeDc );             Cudd_Ref( bNodeOnDc );
        Cudd_RecursiveDeref( p->dd, bNodeFunc );
        Cudd_RecursiveDeref( p->dd, bNodeDc );
        // get the ISOP
        bNodeFunc = Cudd_bddIsop( p->dd, bNodeOn, bNodeOnDc );            Cudd_Ref( bNodeFunc );
        Cudd_RecursiveDeref( p->dd, bNodeOn );
        Cudd_RecursiveDeref( p->dd, bNodeOnDc );
p->timeDcs += clock() - clk;
    }

    // always accept the case of constant node
    if ( Cudd_IsConstant(bNodeFunc) )
    {
Alan Mishchenko committed
238 239
        p->nLastGain = Abc_NodeMffcSize( pNode );
        p->nNodesGained += p->nLastGain;
Alan Mishchenko committed
240 241
        p->nNodesRefactored++;
        Cudd_RecursiveDeref( p->dd, bNodeFunc );
Alan Mishchenko committed
242 243 244
        if ( Cudd_IsComplement(bNodeFunc) )
            return Dec_GraphCreateConst0();
        return Dec_GraphCreateConst1();
Alan Mishchenko committed
245 246 247 248
    }

    // get the SOP of the cut
clk = clock();
Alan Mishchenko committed
249
    pSop = Abc_ConvertBddToSop( NULL, p->dd, bNodeFunc, bNodeFunc, vFanins->nSize, 0, p->vCube, -1 );
Alan Mishchenko committed
250 251 252 253
p->timeSop += clock() - clk;

    // get the factored form
clk = clock();
Alan Mishchenko committed
254
    pFForm = Dec_Factor( pSop );
Alan Mishchenko committed
255
    ABC_FREE( pSop );
Alan Mishchenko committed
256
p->timeFact += clock() - clk;
Alan Mishchenko committed
257

Alan Mishchenko committed
258
    // mark the fanin boundary 
Alan Mishchenko committed
259
    // (can mark only essential fanins, belonging to bNodeFunc!)
260
    Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pFanin, i )
Alan Mishchenko committed
261 262 263
        pFanin->vFanouts.nSize++;
    // label MFFC with current traversal ID
    Abc_NtkIncrementTravId( pNode->pNtk );
Alan Mishchenko committed
264
    nNodesSaved = Abc_NodeMffcLabelAig( pNode );
Alan Mishchenko committed
265
    // unmark the fanin boundary and set the fanins as leaves in the form
266
    Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pFanin, i )
Alan Mishchenko committed
267
    {
Alan Mishchenko committed
268
        pFanin->vFanouts.nSize--;
Alan Mishchenko committed
269 270
        Dec_GraphNode(pFForm, i)->pFunc = pFanin;
    }
Alan Mishchenko committed
271 272

    // detect how many new nodes will be added (while taking into account reused nodes)
Alan Mishchenko committed
273
clk = clock();
Alan Mishchenko committed
274
    nNodesAdded = Dec_GraphToNetworkCount( pNode, pFForm, nNodesSaved, Required );
Alan Mishchenko committed
275
p->timeEval += clock() - clk;
Alan Mishchenko committed
276
    // quit if there is no improvement
Alan Mishchenko committed
277
    if ( nNodesAdded == -1 || (nNodesAdded == nNodesSaved && !fUseZeros) )
Alan Mishchenko committed
278
    {
Alan Mishchenko committed
279 280
        Cudd_RecursiveDeref( p->dd, bNodeFunc );
        Dec_GraphFree( pFForm );
Alan Mishchenko committed
281 282 283 284 285 286 287 288 289 290 291 292 293
        return NULL;
    }

    // compute the total gain in the number of nodes
    p->nLastGain = nNodesSaved - nNodesAdded;
    p->nNodesGained += p->nLastGain;
    p->nNodesRefactored++;

    // report the progress
    if ( fVeryVerbose )
    {
        printf( "Node %6s : ",  Abc_ObjName(pNode) );
        printf( "Cone = %2d. ", vFanins->nSize );
Alan Mishchenko committed
294 295
        printf( "BDD = %2d. ",  Cudd_DagSize(bNodeFunc) );
        printf( "FF = %2d. ",   1 + Dec_GraphNodeNum(pFForm) );
Alan Mishchenko committed
296 297 298 299 300
        printf( "MFFC = %2d. ", nNodesSaved );
        printf( "Add = %2d. ",  nNodesAdded );
        printf( "GAIN = %2d. ", p->nLastGain );
        printf( "\n" );
    }
Alan Mishchenko committed
301 302
    Cudd_RecursiveDeref( p->dd, bNodeFunc );
    return pFForm;
Alan Mishchenko committed
303 304
}

Alan Mishchenko committed
305

Alan Mishchenko committed
306 307 308 309 310 311 312 313 314 315 316
/**Function*************************************************************

  Synopsis    [Starts the resynthesis manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
317
Abc_ManRef_t * Abc_NtkManRefStart( int nNodeSizeMax, int nConeSizeMax, int fUseDcs, int fVerbose )
Alan Mishchenko committed
318 319
{
    Abc_ManRef_t * p;
Alan Mishchenko committed
320
    p = ABC_ALLOC( Abc_ManRef_t, 1 );
Alan Mishchenko committed
321
    memset( p, 0, sizeof(Abc_ManRef_t) );
Alan Mishchenko committed
322 323
    p->vCube        = Vec_StrAlloc( 100 );
    p->vVisited     = Vec_PtrAlloc( 100 );
Alan Mishchenko committed
324 325 326 327
    p->nNodeSizeMax = nNodeSizeMax;
    p->nConeSizeMax = nConeSizeMax;
    p->fVerbose     = fVerbose;
    // start the BDD manager
Alan Mishchenko committed
328 329 330 331
    if ( fUseDcs )
        p->dd = Cudd_Init( p->nNodeSizeMax + p->nConeSizeMax, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 );
    else
        p->dd = Cudd_Init( p->nNodeSizeMax, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 );
Alan Mishchenko committed
332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351
    Cudd_zddVarsFromBddVars( p->dd, 2 );
    return p;
}

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

  Synopsis    [Stops the resynthesis manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkManRefStop( Abc_ManRef_t * p )
{
    Extra_StopManager( p->dd );
    Vec_PtrFree( p->vVisited );
    Vec_StrFree( p->vCube    );
Alan Mishchenko committed
352
    ABC_FREE( p );
Alan Mishchenko committed
353 354
}

Alan Mishchenko committed
355 356 357 358 359 360 361 362 363 364 365 366 367 368
/**Function*************************************************************

  Synopsis    [Stops the resynthesis manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkManRefPrintStats( Abc_ManRef_t * p )
{
    printf( "Refactoring statistics:\n" );
Alan Mishchenko committed
369 370
    printf( "Nodes considered  = %8d.\n", p->nNodesConsidered );
    printf( "Nodes refactored  = %8d.\n", p->nNodesRefactored );
Alan Mishchenko committed
371
    printf( "Gain              = %8d. (%6.2f %%).\n", p->nNodesBeg-p->nNodesEnd, 100.0*(p->nNodesBeg-p->nNodesEnd)/p->nNodesBeg );
Alan Mishchenko committed
372 373 374 375 376 377 378 379 380
    ABC_PRT( "Cuts       ", p->timeCut );
    ABC_PRT( "Resynthesis", p->timeRes );
    ABC_PRT( "    BDD    ", p->timeBdd );
    ABC_PRT( "    DCs    ", p->timeDcs );
    ABC_PRT( "    SOP    ", p->timeSop );
    ABC_PRT( "    FF     ", p->timeFact );
    ABC_PRT( "    Eval   ", p->timeEval );
    ABC_PRT( "AIG update ", p->timeNtk );
    ABC_PRT( "TOTAL      ", p->timeTotal );
Alan Mishchenko committed
381 382 383
}


Alan Mishchenko committed
384 385 386 387 388
////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


389 390
ABC_NAMESPACE_IMPL_END