abcRewrite.c 12.4 KB
Newer Older
Alan Mishchenko committed
1 2
/**CFile****************************************************************

Alan Mishchenko committed
3
  FileName    [abcRewrite.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    [Technology-independent resynthesis of the AIG based on DAG aware rewriting.]
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: abcRewrite.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
Alan Mishchenko committed
18 19 20

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

21 22 23
#include "base/abc/abc.h"
#include "opt/rwr/rwr.h"
#include "bool/dec/dec.h"
Alan Mishchenko committed
24

25 26 27
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
28 29 30 31 32 33
/*
    The ideas realized in this package are inspired by the paper:
    Per Bjesse, Arne Boralv, "DAG-aware circuit compression for 
    formal verification", Proc. ICCAD 2004, pp. 42-49.
*/

Alan Mishchenko committed
34 35 36 37
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

Alan Mishchenko committed
38
static Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk );
Alan Mishchenko committed
39
static void        Abc_NodePrintCuts( Abc_Obj_t * pNode );
Alan Mishchenko committed
40 41 42 43 44
static void        Abc_ManShowCutCone( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves );

extern void  Abc_PlaceBegin( Abc_Ntk_t * pNtk );
extern void  Abc_PlaceEnd( Abc_Ntk_t * pNtk );
extern void  Abc_PlaceUpdate( Vec_Ptr_t * vAddedCells, Vec_Ptr_t * vUpdatedNets );
Alan Mishchenko committed
45

Alan Mishchenko committed
46
////////////////////////////////////////////////////////////////////////
Alan Mishchenko committed
47
///                     FUNCTION DEFINITIONS                         ///
Alan Mishchenko committed
48 49 50 51
////////////////////////////////////////////////////////////////////////

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

Alan Mishchenko committed
52
  Synopsis    [Performs incremental rewriting of the AIG.]
Alan Mishchenko committed
53

Alan Mishchenko committed
54
  Description []
Alan Mishchenko committed
55 56 57 58 59 60
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
61
int Abc_NtkRewrite( Abc_Ntk_t * pNtk, int fUpdateLevel, int fUseZeros, int fVerbose, int fVeryVerbose, int fPlaceEnable )
Alan Mishchenko committed
62
{
63
    extern void           Dec_GraphUpdateNetwork( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int fUpdateLevel, int nGain );
Alan Mishchenko committed
64
    ProgressBar * pProgress;
Alan Mishchenko committed
65 66
    Cut_Man_t * pManCut;
    Rwr_Man_t * pManRwr;
Alan Mishchenko committed
67
    Abc_Obj_t * pNode;
Alan Mishchenko committed
68
//    Vec_Ptr_t * vAddedCells = NULL, * vUpdatedNets = NULL;
Alan Mishchenko committed
69 70
    Dec_Graph_t * pGraph;
    int i, nNodes, nGain, fCompl;
71
    abctime clk, clkStart = Abc_Clock();
Alan Mishchenko committed
72

Alan Mishchenko committed
73
    assert( Abc_NtkIsStrash(pNtk) );
Alan Mishchenko committed
74
    // cleanup the AIG
75
    Abc_AigCleanup((Abc_Aig_t *)pNtk->pManFunc);
Alan Mishchenko committed
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
/*
    {
        Vec_Vec_t * vParts;
        vParts = Abc_NtkPartitionSmart( pNtk, 50, 1 );
        Vec_VecFree( vParts );
    }
*/

    // start placement package
//    if ( fPlaceEnable )
//    {
//        Abc_PlaceBegin( pNtk );
//        vAddedCells = Abc_AigUpdateStart( pNtk->pManFunc, &vUpdatedNets );
//    }

Alan Mishchenko committed
91
    // start the rewriting manager
Alan Mishchenko committed
92 93
    pManRwr = Rwr_ManStart( 0 );
    if ( pManRwr == NULL )
Alan Mishchenko committed
94
        return 0;
Alan Mishchenko committed
95 96 97
    // compute the reverse levels if level update is requested
    if ( fUpdateLevel )
        Abc_NtkStartReverseLevels( pNtk, 0 );
Alan Mishchenko committed
98
    // start the cut manager
99
clk = Abc_Clock();
Alan Mishchenko committed
100
    pManCut = Abc_NtkStartCutManForRewrite( pNtk );
101
Rwr_ManAddTimeCuts( pManRwr, Abc_Clock() - clk );
Alan Mishchenko committed
102
    pNtk->pManCut = pManCut;
Alan Mishchenko committed
103

Alan Mishchenko committed
104 105 106
    if ( fVeryVerbose )
        Rwr_ScoresClean( pManRwr );

Alan Mishchenko committed
107
    // resynthesize each node once
Alan Mishchenko committed
108
    pManRwr->nNodesBeg = Abc_NtkNodeNum(pNtk);
Alan Mishchenko committed
109 110
    nNodes = Abc_NtkObjNumMax(pNtk);
    pProgress = Extra_ProgressBarStart( stdout, nNodes );
Alan Mishchenko committed
111 112
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
Alan Mishchenko committed
113 114 115 116
        Extra_ProgressBarUpdate( pProgress, i, NULL );
        // stop if all nodes have been tried once
        if ( i >= nNodes )
            break;
Alan Mishchenko committed
117 118
        // skip persistant nodes
        if ( Abc_NodeIsPersistant(pNode) )
Alan Mishchenko committed
119
            continue;
Alan Mishchenko committed
120 121 122
        // skip the nodes with many fanouts
        if ( Abc_ObjFanoutNum(pNode) > 1000 )
            continue;
Alan Mishchenko committed
123

Alan Mishchenko committed
124
        // for each cut, try to resynthesize it
Alan Mishchenko committed
125
        nGain = Rwr_NodeRewrite( pManRwr, pManCut, pNode, fUpdateLevel, fUseZeros, fPlaceEnable );
Alan Mishchenko committed
126
        if ( !(nGain > 0 || (nGain == 0 && fUseZeros)) )
Alan Mishchenko committed
127 128 129 130
            continue;
        // if we end up here, a rewriting step is accepted

        // get hold of the new subgraph to be added to the AIG
131
        pGraph = (Dec_Graph_t *)Rwr_ManReadDecs(pManRwr);
Alan Mishchenko committed
132 133 134 135
        fCompl = Rwr_ManReadCompl(pManRwr);

        // reset the array of the changed nodes
        if ( fPlaceEnable )
136
            Abc_AigUpdateReset( (Abc_Aig_t *)pNtk->pManFunc );
Alan Mishchenko committed
137 138 139

        // complement the FF if needed
        if ( fCompl ) Dec_GraphComplement( pGraph );
140
clk = Abc_Clock();
Alan Mishchenko committed
141
        Dec_GraphUpdateNetwork( pNode, pGraph, fUpdateLevel, nGain );
142
Rwr_ManAddTimeUpdate( pManRwr, Abc_Clock() - clk );
Alan Mishchenko committed
143 144 145 146 147
        if ( fCompl ) Dec_GraphComplement( pGraph );

        // use the array of changed nodes to update placement
//        if ( fPlaceEnable )
//            Abc_PlaceUpdate( vAddedCells, vUpdatedNets );
Alan Mishchenko committed
148 149
    }
    Extra_ProgressBarStop( pProgress );
150
Rwr_ManAddTimeTotal( pManRwr, Abc_Clock() - clkStart );
Alan Mishchenko committed
151
    // print stats
Alan Mishchenko committed
152
    pManRwr->nNodesEnd = Abc_NtkNodeNum(pNtk);
Alan Mishchenko committed
153 154
    if ( fVerbose )
        Rwr_ManPrintStats( pManRwr );
Alan Mishchenko committed
155 156 157
//        Rwr_ManPrintStatsFile( pManRwr );
    if ( fVeryVerbose )
        Rwr_ScoresReport( pManRwr );
Alan Mishchenko committed
158 159 160 161
    // delete the managers
    Rwr_ManStop( pManRwr );
    Cut_ManStop( pManCut );
    pNtk->pManCut = NULL;
Alan Mishchenko committed
162 163 164 165 166 167 168 169 170 171

    // start placement package
//    if ( fPlaceEnable )
//    {
//        Abc_PlaceEnd( pNtk );
//        Abc_AigUpdateStop( pNtk->pManFunc );
//    }

    // put the nodes into the DFS order and reassign their IDs
    {
172
//        abctime clk = Abc_Clock();
Alan Mishchenko committed
173
    Abc_NtkReassignIds( pNtk );
174
//        ABC_PRT( "time", Abc_Clock() - clk );
Alan Mishchenko committed
175 176 177 178 179 180 181
    }
//    Abc_AigCheckFaninOrder( pNtk->pManFunc );
    // fix the levels
    if ( fUpdateLevel )
        Abc_NtkStopReverseLevels( pNtk );
    else
        Abc_NtkLevel( pNtk );
Alan Mishchenko committed
182
    // check
Alan Mishchenko committed
183
    if ( !Abc_NtkCheck( pNtk ) )
Alan Mishchenko committed
184
    {
Alan Mishchenko committed
185
        printf( "Abc_NtkRewrite: The network check has failed.\n" );
Alan Mishchenko committed
186 187 188 189 190 191
        return 0;
    }
    return 1;
}


Alan Mishchenko committed
192 193 194 195 196 197 198 199 200 201 202
/**Function*************************************************************

  Synopsis    [Starts the cut manager for rewriting.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
203
Cut_Man_t * Abc_NtkStartCutManForRewrite( Abc_Ntk_t * pNtk )
Alan Mishchenko committed
204 205 206 207 208 209 210 211 212 213
{
    static Cut_Params_t Params, * pParams = &Params;
    Cut_Man_t * pManCut;
    Abc_Obj_t * pObj;
    int i;
    // start the cut manager
    memset( pParams, 0, sizeof(Cut_Params_t) );
    pParams->nVarsMax  = 4;     // the max cut size ("k" of the k-feasible cuts)
    pParams->nKeepMax  = 250;   // the max number of cuts kept at a node
    pParams->fTruth    = 1;     // compute truth tables
Alan Mishchenko committed
214
    pParams->fFilter   = 1;     // filter dominated cuts
Alan Mishchenko committed
215
    pParams->fSeq      = 0;     // compute sequential cuts
Alan Mishchenko committed
216
    pParams->fDrop     = 0;     // drop cuts on the fly
Alan Mishchenko committed
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241
    pParams->fVerbose  = 0;     // the verbosiness flag
    pParams->nIdsMax   = Abc_NtkObjNumMax( pNtk );
    pManCut = Cut_ManStart( pParams );
    if ( pParams->fDrop )
        Cut_ManSetFanoutCounts( pManCut, Abc_NtkFanoutCounts(pNtk) );
    // set cuts for PIs
    Abc_NtkForEachCi( pNtk, pObj, i )
        if ( Abc_ObjFanoutNum(pObj) > 0 )
            Cut_NodeSetTriv( pManCut, pObj->Id );
    return pManCut;
}

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

  Synopsis    [Prints the cuts at the nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NodePrintCuts( Abc_Obj_t * pNode )
{
Alan Mishchenko committed
242
    Vec_Ptr_t * vCuts;
Alan Mishchenko committed
243
    Cut_Cut_t * pCut;
Alan Mishchenko committed
244 245
    int k;

Alan Mishchenko committed
246
    printf( "\nNode %s\n", Abc_ObjName(pNode) );
Alan Mishchenko committed
247
    vCuts = (Vec_Ptr_t *)pNode->pCopy;
248
    Vec_PtrForEachEntry( Cut_Cut_t *, vCuts, pCut, k )
Alan Mishchenko committed
249
    {
Alan Mishchenko committed
250
        Extra_PrintBinary( stdout, (unsigned *)&pCut->uSign, 16 ); 
Alan Mishchenko committed
251
        printf( "   " );
Alan Mishchenko committed
252
        Cut_CutPrint( pCut, 0 );   
Alan Mishchenko committed
253 254 255 256
        printf( "\n" );
    }
}

Alan Mishchenko committed
257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_ManRewritePrintDivs( Vec_Ptr_t * vDivs, int nLeaves )
{
    Abc_Obj_t * pFanin, * pNode, * pRoot;
    int i, k;
273
    pRoot = (Abc_Obj_t *)Vec_PtrEntryLast(vDivs);
Alan Mishchenko committed
274
    // print the nodes
275
    Vec_PtrForEachEntry( Abc_Obj_t *, vDivs, pNode, i )
Alan Mishchenko committed
276 277 278 279 280 281 282 283
    {
        if ( i < nLeaves )
        {
            printf( "%6d : %c\n", pNode->Id, 'a'+i );
            continue;
        }
        printf( "%6d : %2d = ", pNode->Id, i );
        // find the first fanin
284
        Vec_PtrForEachEntry( Abc_Obj_t *, vDivs, pFanin, k )
Alan Mishchenko committed
285 286 287 288 289 290 291 292
            if ( Abc_ObjFanin0(pNode) == pFanin )
                break;
        if ( k < nLeaves )
            printf( "%c", 'a' + k );
        else
            printf( "%d", k );
        printf( "%s ", Abc_ObjFaninC0(pNode)? "\'" : "" );
        // find the second fanin
293
        Vec_PtrForEachEntry( Abc_Obj_t *, vDivs, pFanin, k )
Alan Mishchenko committed
294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347
            if ( Abc_ObjFanin1(pNode) == pFanin )
                break;
        if ( k < nLeaves )
            printf( "%c", 'a' + k );
        else
            printf( "%d", k );
        printf( "%s ", Abc_ObjFaninC1(pNode)? "\'" : "" );
        if ( pNode == pRoot )
            printf( " root" );
        printf( "\n" );
    }
    printf( "\n" );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_ManShowCutCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vDivs )
{
    if ( Abc_NodeIsTravIdCurrent(pNode) )
        return;
    Abc_NodeSetTravIdCurrent(pNode);
    Abc_ManShowCutCone_rec( Abc_ObjFanin0(pNode), vDivs );
    Abc_ManShowCutCone_rec( Abc_ObjFanin1(pNode), vDivs );
    Vec_PtrPush( vDivs, pNode );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_ManShowCutCone( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves )
{
    Abc_Ntk_t * pNtk = pNode->pNtk;
    Abc_Obj_t * pObj;
    Vec_Ptr_t * vDivs;
    int i;
    vDivs = Vec_PtrAlloc( 100 );
    Abc_NtkIncrementTravId( pNtk );
348
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
Alan Mishchenko committed
349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402
    {
        Abc_NodeSetTravIdCurrent( Abc_ObjRegular(pObj) );
        Vec_PtrPush( vDivs, Abc_ObjRegular(pObj) );
    }
    Abc_ManShowCutCone_rec( pNode, vDivs );
    Abc_ManRewritePrintDivs( vDivs, Vec_PtrSize(vLeaves) );
    Vec_PtrFree( vDivs );
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_RwrExpWithCut_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, int fUseA )
{
    if ( Vec_PtrFind(vLeaves, pNode) >= 0 || Vec_PtrFind(vLeaves, Abc_ObjNot(pNode)) >= 0 )
    {
        if ( fUseA )
            Abc_ObjRegular(pNode)->fMarkA = 1;
        else
            Abc_ObjRegular(pNode)->fMarkB = 1;
        return;
    }
    assert( Abc_ObjIsNode(pNode) );
    Abc_RwrExpWithCut_rec( Abc_ObjFanin0(pNode), vLeaves, fUseA );
    Abc_RwrExpWithCut_rec( Abc_ObjFanin1(pNode), vLeaves, fUseA );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_RwrExpWithCut( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves )
{
    Abc_Obj_t * pObj;
    int i, CountA, CountB;
    Abc_RwrExpWithCut_rec( Abc_ObjFanin0(pNode), vLeaves, 1 );
    Abc_RwrExpWithCut_rec( Abc_ObjFanin1(pNode), vLeaves, 0 );
    CountA = CountB = 0;
403
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
Alan Mishchenko committed
404 405 406 407 408 409 410 411 412 413
    {
        CountA += Abc_ObjRegular(pObj)->fMarkA;
        CountB += Abc_ObjRegular(pObj)->fMarkB;
        Abc_ObjRegular(pObj)->fMarkA = 0;
        Abc_ObjRegular(pObj)->fMarkB = 0;
    }
    printf( "(%d,%d:%d) ", CountA, CountB, CountA+CountB-Vec_PtrSize(vLeaves) );
}


Alan Mishchenko committed
414 415 416 417 418
////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


419 420
ABC_NAMESPACE_IMPL_END