src/base/abci/abcRewrite.c File Reference

#include "abc.h"
#include "rwr.h"
#include "dec.h"
Include dependency graph for abcRewrite.c:

Go to the source code of this file.

Functions

static Cut_Man_t * Abc_NtkStartCutManForRewrite (Abc_Ntk_t *pNtk)
static void Abc_NodePrintCuts (Abc_Obj_t *pNode)
static void Abc_ManShowCutCone (Abc_Obj_t *pNode, Vec_Ptr_t *vLeaves)
void Abc_PlaceBegin (Abc_Ntk_t *pNtk)
void Abc_PlaceEnd (Abc_Ntk_t *pNtk)
void Abc_PlaceUpdate (Vec_Ptr_t *vAddedCells, Vec_Ptr_t *vUpdatedNets)
int Abc_NtkRewrite (Abc_Ntk_t *pNtk, int fUpdateLevel, int fUseZeros, int fVerbose, int fVeryVerbose, int fPlaceEnable)
void Abc_ManRewritePrintDivs (Vec_Ptr_t *vDivs, int nLeaves)
void Abc_ManShowCutCone_rec (Abc_Obj_t *pNode, Vec_Ptr_t *vDivs)
void Abc_RwrExpWithCut_rec (Abc_Obj_t *pNode, Vec_Ptr_t *vLeaves, int fUseA)
void Abc_RwrExpWithCut (Abc_Obj_t *pNode, Vec_Ptr_t *vLeaves)

Function Documentation

void Abc_ManRewritePrintDivs ( Vec_Ptr_t *  vDivs,
int  nLeaves 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 265 of file abcRewrite.c.

00266 {
00267     Abc_Obj_t * pFanin, * pNode, * pRoot;
00268     int i, k;
00269     pRoot = Vec_PtrEntryLast(vDivs);
00270     // print the nodes
00271     Vec_PtrForEachEntry( vDivs, pNode, i )
00272     {
00273         if ( i < nLeaves )
00274         {
00275             printf( "%6d : %c\n", pNode->Id, 'a'+i );
00276             continue;
00277         }
00278         printf( "%6d : %2d = ", pNode->Id, i );
00279         // find the first fanin
00280         Vec_PtrForEachEntry( vDivs, pFanin, k )
00281             if ( Abc_ObjFanin0(pNode) == pFanin )
00282                 break;
00283         if ( k < nLeaves )
00284             printf( "%c", 'a' + k );
00285         else
00286             printf( "%d", k );
00287         printf( "%s ", Abc_ObjFaninC0(pNode)? "\'" : "" );
00288         // find the second fanin
00289         Vec_PtrForEachEntry( vDivs, pFanin, k )
00290             if ( Abc_ObjFanin1(pNode) == pFanin )
00291                 break;
00292         if ( k < nLeaves )
00293             printf( "%c", 'a' + k );
00294         else
00295             printf( "%d", k );
00296         printf( "%s ", Abc_ObjFaninC1(pNode)? "\'" : "" );
00297         if ( pNode == pRoot )
00298             printf( " root" );
00299         printf( "\n" );
00300     }
00301     printf( "\n" );
00302 }

void Abc_ManShowCutCone ( Abc_Obj_t *  pNode,
Vec_Ptr_t *  vLeaves 
) [static]

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 336 of file abcRewrite.c.

00337 {
00338     Abc_Ntk_t * pNtk = pNode->pNtk;
00339     Abc_Obj_t * pObj;
00340     Vec_Ptr_t * vDivs;
00341     int i;
00342     vDivs = Vec_PtrAlloc( 100 );
00343     Abc_NtkIncrementTravId( pNtk );
00344     Vec_PtrForEachEntry( vLeaves, pObj, i )
00345     {
00346         Abc_NodeSetTravIdCurrent( Abc_ObjRegular(pObj) );
00347         Vec_PtrPush( vDivs, Abc_ObjRegular(pObj) );
00348     }
00349     Abc_ManShowCutCone_rec( pNode, vDivs );
00350     Abc_ManRewritePrintDivs( vDivs, Vec_PtrSize(vLeaves) );
00351     Vec_PtrFree( vDivs );
00352 }

void Abc_ManShowCutCone_rec ( Abc_Obj_t *  pNode,
Vec_Ptr_t *  vDivs 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 315 of file abcRewrite.c.

00316 {
00317     if ( Abc_NodeIsTravIdCurrent(pNode) )
00318         return;
00319     Abc_NodeSetTravIdCurrent(pNode);
00320     Abc_ManShowCutCone_rec( Abc_ObjFanin0(pNode), vDivs );
00321     Abc_ManShowCutCone_rec( Abc_ObjFanin1(pNode), vDivs );
00322     Vec_PtrPush( vDivs, pNode );
00323 }

void Abc_NodePrintCuts ( Abc_Obj_t *  pNode  )  [static]

Function*************************************************************

Synopsis [Prints the cuts at the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 236 of file abcRewrite.c.

00237 {
00238     Vec_Ptr_t * vCuts;
00239     Cut_Cut_t * pCut;
00240     int k;
00241 
00242     printf( "\nNode %s\n", Abc_ObjName(pNode) );
00243     vCuts = (Vec_Ptr_t *)pNode->pCopy;
00244     Vec_PtrForEachEntry( vCuts, pCut, k )
00245     {
00246         Extra_PrintBinary( stdout, (unsigned *)&pCut->uSign, 16 ); 
00247         printf( "   " );
00248         Cut_CutPrint( pCut, 0 );   
00249         printf( "\n" );
00250     }
00251 }

int Abc_NtkRewrite ( Abc_Ntk_t *  pNtk,
int  fUpdateLevel,
int  fUseZeros,
int  fVerbose,
int  fVeryVerbose,
int  fPlaceEnable 
)

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Performs incremental rewriting of the AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 58 of file abcRewrite.c.

00059 {
00060     ProgressBar * pProgress;
00061     Cut_Man_t * pManCut;
00062     Rwr_Man_t * pManRwr;
00063     Abc_Obj_t * pNode;
00064     Vec_Ptr_t * vAddedCells = NULL, * vUpdatedNets = NULL;
00065     Dec_Graph_t * pGraph;
00066     int i, nNodes, nGain, fCompl;
00067     int clk, clkStart = clock();
00068 
00069     assert( Abc_NtkIsStrash(pNtk) );
00070     // cleanup the AIG
00071     Abc_AigCleanup(pNtk->pManFunc);
00072 /*
00073     {
00074         Vec_Vec_t * vParts;
00075         vParts = Abc_NtkPartitionSmart( pNtk, 50, 1 );
00076         Vec_VecFree( vParts );
00077     }
00078 */
00079 
00080     // start placement package
00081 //    if ( fPlaceEnable )
00082 //    {
00083 //        Abc_PlaceBegin( pNtk );
00084 //        vAddedCells = Abc_AigUpdateStart( pNtk->pManFunc, &vUpdatedNets );
00085 //    }
00086 
00087     // start the rewriting manager
00088     pManRwr = Rwr_ManStart( 0 );
00089     if ( pManRwr == NULL )
00090         return 0;
00091     // compute the reverse levels if level update is requested
00092     if ( fUpdateLevel )
00093         Abc_NtkStartReverseLevels( pNtk, 0 );
00094     // start the cut manager
00095 clk = clock();
00096     pManCut = Abc_NtkStartCutManForRewrite( pNtk );
00097 Rwr_ManAddTimeCuts( pManRwr, clock() - clk );
00098     pNtk->pManCut = pManCut;
00099 
00100     if ( fVeryVerbose )
00101         Rwr_ScoresClean( pManRwr );
00102 
00103     // resynthesize each node once
00104     pManRwr->nNodesBeg = Abc_NtkNodeNum(pNtk);
00105     nNodes = Abc_NtkObjNumMax(pNtk);
00106     pProgress = Extra_ProgressBarStart( stdout, nNodes );
00107     Abc_NtkForEachNode( pNtk, pNode, i )
00108     {
00109         Extra_ProgressBarUpdate( pProgress, i, NULL );
00110         // stop if all nodes have been tried once
00111         if ( i >= nNodes )
00112             break;
00113         // skip persistant nodes
00114         if ( Abc_NodeIsPersistant(pNode) )
00115             continue;
00116         // skip the nodes with many fanouts
00117         if ( Abc_ObjFanoutNum(pNode) > 1000 )
00118             continue;
00119 
00120         // for each cut, try to resynthesize it
00121         nGain = Rwr_NodeRewrite( pManRwr, pManCut, pNode, fUpdateLevel, fUseZeros, fPlaceEnable );
00122         if ( !(nGain > 0 || nGain == 0 && fUseZeros) )
00123             continue;
00124         // if we end up here, a rewriting step is accepted
00125 
00126         // get hold of the new subgraph to be added to the AIG
00127         pGraph = Rwr_ManReadDecs(pManRwr);
00128         fCompl = Rwr_ManReadCompl(pManRwr);
00129 
00130         // reset the array of the changed nodes
00131         if ( fPlaceEnable )
00132             Abc_AigUpdateReset( pNtk->pManFunc );
00133 
00134         // complement the FF if needed
00135         if ( fCompl ) Dec_GraphComplement( pGraph );
00136 clk = clock();
00137         Dec_GraphUpdateNetwork( pNode, pGraph, fUpdateLevel, nGain );
00138 Rwr_ManAddTimeUpdate( pManRwr, clock() - clk );
00139         if ( fCompl ) Dec_GraphComplement( pGraph );
00140 
00141         // use the array of changed nodes to update placement
00142 //        if ( fPlaceEnable )
00143 //            Abc_PlaceUpdate( vAddedCells, vUpdatedNets );
00144     }
00145     Extra_ProgressBarStop( pProgress );
00146 Rwr_ManAddTimeTotal( pManRwr, clock() - clkStart );
00147     // print stats
00148     pManRwr->nNodesEnd = Abc_NtkNodeNum(pNtk);
00149     if ( fVerbose )
00150         Rwr_ManPrintStats( pManRwr );
00151 //        Rwr_ManPrintStatsFile( pManRwr );
00152     if ( fVeryVerbose )
00153         Rwr_ScoresReport( pManRwr );
00154     // delete the managers
00155     Rwr_ManStop( pManRwr );
00156     Cut_ManStop( pManCut );
00157     pNtk->pManCut = NULL;
00158 
00159     // start placement package
00160 //    if ( fPlaceEnable )
00161 //    {
00162 //        Abc_PlaceEnd( pNtk );
00163 //        Abc_AigUpdateStop( pNtk->pManFunc );
00164 //    }
00165 
00166     // put the nodes into the DFS order and reassign their IDs
00167     {
00168 //        int clk = clock();
00169     Abc_NtkReassignIds( pNtk );
00170 //        PRT( "time", clock() - clk );
00171     }
00172 //    Abc_AigCheckFaninOrder( pNtk->pManFunc );
00173     // fix the levels
00174     if ( fUpdateLevel )
00175         Abc_NtkStopReverseLevels( pNtk );
00176     else
00177         Abc_NtkLevel( pNtk );
00178     // check
00179     if ( !Abc_NtkCheck( pNtk ) )
00180     {
00181         printf( "Abc_NtkRewrite: The network check has failed.\n" );
00182         return 0;
00183     }
00184     return 1;
00185 }

Cut_Man_t * Abc_NtkStartCutManForRewrite ( Abc_Ntk_t *  pNtk  )  [static]

CFile****************************************************************

FileName [abcRewrite.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Technology-independent resynthesis of the AIG based on DAG aware rewriting.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id
abcRewrite.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

] DECLARATIONS ///

Function*************************************************************

Synopsis [Starts the cut manager for rewriting.]

Description []

SideEffects []

SeeAlso []

Definition at line 199 of file abcRewrite.c.

00200 {
00201     static Cut_Params_t Params, * pParams = &Params;
00202     Cut_Man_t * pManCut;
00203     Abc_Obj_t * pObj;
00204     int i;
00205     // start the cut manager
00206     memset( pParams, 0, sizeof(Cut_Params_t) );
00207     pParams->nVarsMax  = 4;     // the max cut size ("k" of the k-feasible cuts)
00208     pParams->nKeepMax  = 250;   // the max number of cuts kept at a node
00209     pParams->fTruth    = 1;     // compute truth tables
00210     pParams->fFilter   = 1;     // filter dominated cuts
00211     pParams->fSeq      = 0;     // compute sequential cuts
00212     pParams->fDrop     = 0;     // drop cuts on the fly
00213     pParams->fVerbose  = 0;     // the verbosiness flag
00214     pParams->nIdsMax   = Abc_NtkObjNumMax( pNtk );
00215     pManCut = Cut_ManStart( pParams );
00216     if ( pParams->fDrop )
00217         Cut_ManSetFanoutCounts( pManCut, Abc_NtkFanoutCounts(pNtk) );
00218     // set cuts for PIs
00219     Abc_NtkForEachCi( pNtk, pObj, i )
00220         if ( Abc_ObjFanoutNum(pObj) > 0 )
00221             Cut_NodeSetTriv( pManCut, pObj->Id );
00222     return pManCut;
00223 }

void Abc_PlaceBegin ( Abc_Ntk_t *  pNtk  ) 

Function*************************************************************

Synopsis [This procedure is called before the writing start.]

Description []

SideEffects []

SeeAlso []

Definition at line 175 of file abcPlace.c.

00176 {
00177     Abc_Obj_t * pObj;
00178     int i;
00179 
00180     // allocate and clean internal storage
00181     nAllocSize = 5 * Abc_NtkObjNumMax(pNtk);
00182     cells = REALLOC(ConcreteCell, cells, nAllocSize);
00183     nets  = REALLOC(ConcreteNet, nets, nAllocSize);
00184     memset( cells, 0, sizeof(ConcreteCell) * nAllocSize );
00185     memset( nets, 0, sizeof(ConcreteNet) * nAllocSize );
00186 
00187     // create AbstractCells
00188     //   1: pad
00189     //   2: and
00190     if (!abstractCells)
00191         abstractCells = ALLOC(AbstractCell,2);
00192 
00193     abstractCells[0].m_height = 1.0;
00194     abstractCells[0].m_width = 1.0;
00195     abstractCells[0].m_label = "pio";
00196     abstractCells[0].m_pad = 1;
00197 
00198     abstractCells[1].m_height = 1.0;
00199     abstractCells[1].m_width = 1.0;
00200     abstractCells[1].m_label = "and";
00201     abstractCells[1].m_pad = 0;
00202 
00203     // input pads
00204     Abc_NtkForEachCi( pNtk, pObj, i )
00205         Abc_PlaceCreateCell( pObj, 0 );
00206 
00207     // ouput pads
00208     Abc_NtkForEachCo( pNtk, pObj, i )
00209         Abc_PlaceCreateCell( pObj, 0 );
00210 
00211     // AND nodes
00212     Abc_AigForEachAnd( pNtk, pObj, i )
00213         Abc_PlaceCreateCell( pObj, 1 );
00214 
00215     // all nets
00216     Abc_NtkForEachObj( pNtk, pObj, i )
00217     {
00218         if ( !Abc_ObjIsCi(pObj) && !Abc_ObjIsNode(pObj) )
00219             continue;
00220         Abc_PlaceUpdateNet( pObj );
00221     }
00222 
00223     globalPreplace((float)0.8);
00224     globalPlace();
00225 }

void Abc_PlaceEnd ( Abc_Ntk_t *  pNtk  ) 

Function*************************************************************

Synopsis [This procedure is called after the writing completes.]

Description []

SideEffects []

SeeAlso []

Definition at line 238 of file abcPlace.c.

00239 {
00240     int i;
00241 
00242 
00243     // clean up
00244     for ( i = 0; i < nAllocSize; i++ )
00245         FREE( nets[i].m_terms );
00246     FREE( abstractCells );
00247     FREE( cells );
00248     FREE( nets );
00249 }

void Abc_PlaceUpdate ( Vec_Ptr_t *  vAddedCells,
Vec_Ptr_t *  vUpdatedNets 
)

Function*************************************************************

Synopsis [Updates placement after one step of rewriting.]

Description []

SideEffects []

SeeAlso []

Definition at line 123 of file abcPlace.c.

00124 {
00125     Abc_Obj_t * pObj, * pFanin;
00126     int i, k;
00127     Vec_Ptr_t * vCells, * vNets;
00128 
00129     // start the arrays of new cells and nets
00130     vCells = Vec_PtrAlloc( 16 );
00131     vNets = Vec_PtrAlloc( 32 );
00132 
00133     // go through the new nodes
00134     Vec_PtrForEachEntry( vAddedCells, pObj, i )
00135     {
00136         assert( !Abc_ObjIsComplement(pObj) );
00137         Abc_PlaceCreateCell( pObj, 1 );
00138         Abc_PlaceUpdateNet( pObj );
00139 
00140         // add the new cell and its fanin nets to temporary storage
00141         Vec_PtrPush( vCells, &(cells[pObj->Id]) );
00142         Abc_ObjForEachFanin( pObj, pFanin, k )
00143             Vec_PtrPushUnique( vNets, &(nets[pFanin->Id]) );
00144     }
00145 
00146     // go through the modified nets
00147     Vec_PtrForEachEntry( vUpdatedNets, pObj, i )
00148     {
00149         assert( !Abc_ObjIsComplement(pObj) );
00150         if ( Abc_ObjType(pObj) == ABC_OBJ_NONE ) // dead node
00151             continue;
00152         Abc_PlaceUpdateNet( pObj );
00153     }
00154 
00155     // update the placement
00156 //    fastPlace( Vec_PtrSize(vCells), (ConcreteCell **)Vec_PtrArray(vCells), 
00157 //               Vec_PtrSize(vNets), (ConcreteNet **)Vec_PtrArray(vNets) );
00158 
00159     // clean up
00160     Vec_PtrFree( vCells );
00161     Vec_PtrFree( vNets );
00162 }

void Abc_RwrExpWithCut ( Abc_Obj_t *  pNode,
Vec_Ptr_t *  vLeaves 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 392 of file abcRewrite.c.

00393 {
00394     Abc_Obj_t * pObj;
00395     int i, CountA, CountB;
00396     Abc_RwrExpWithCut_rec( Abc_ObjFanin0(pNode), vLeaves, 1 );
00397     Abc_RwrExpWithCut_rec( Abc_ObjFanin1(pNode), vLeaves, 0 );
00398     CountA = CountB = 0;
00399     Vec_PtrForEachEntry( vLeaves, pObj, i )
00400     {
00401         CountA += Abc_ObjRegular(pObj)->fMarkA;
00402         CountB += Abc_ObjRegular(pObj)->fMarkB;
00403         Abc_ObjRegular(pObj)->fMarkA = 0;
00404         Abc_ObjRegular(pObj)->fMarkB = 0;
00405     }
00406     printf( "(%d,%d:%d) ", CountA, CountB, CountA+CountB-Vec_PtrSize(vLeaves) );
00407 }

void Abc_RwrExpWithCut_rec ( Abc_Obj_t *  pNode,
Vec_Ptr_t *  vLeaves,
int  fUseA 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 366 of file abcRewrite.c.

00367 {
00368     if ( Vec_PtrFind(vLeaves, pNode) >= 0 || Vec_PtrFind(vLeaves, Abc_ObjNot(pNode)) >= 0 )
00369     {
00370         if ( fUseA )
00371             Abc_ObjRegular(pNode)->fMarkA = 1;
00372         else
00373             Abc_ObjRegular(pNode)->fMarkB = 1;
00374         return;
00375     }
00376     assert( Abc_ObjIsNode(pNode) );
00377     Abc_RwrExpWithCut_rec( Abc_ObjFanin0(pNode), vLeaves, fUseA );
00378     Abc_RwrExpWithCut_rec( Abc_ObjFanin1(pNode), vLeaves, fUseA );
00379 }

Generated on Tue Jan 5 12:18:41 2010 for abc70930 by  doxygen 1.6.1