src/base/abci/abcSweep.c File Reference

#include "abc.h"
#include "fraig.h"
Include dependency graph for abcSweep.c:

Go to the source code of this file.

Functions

static void Abc_NtkFraigSweepUsingExdc (Fraig_Man_t *pMan, Abc_Ntk_t *pNtk)
static stmm_table * Abc_NtkFraigEquiv (Abc_Ntk_t *pNtk, int fUseInv, int fVerbose, int fVeryVerbose)
static void Abc_NtkFraigTransform (Abc_Ntk_t *pNtk, stmm_table *tEquiv, int fUseInv, bool fVerbose)
static void Abc_NtkFraigMergeClassMapped (Abc_Ntk_t *pNtk, Abc_Obj_t *pChain, int fUseInv, int fVerbose)
static void Abc_NtkFraigMergeClass (Abc_Ntk_t *pNtk, Abc_Obj_t *pChain, int fUseInv, int fVerbose)
static int Abc_NodeDroppingCost (Abc_Obj_t *pNode)
static int Abc_NtkReduceNodes (Abc_Ntk_t *pNtk, Vec_Ptr_t *vNodes)
static void Abc_NodeSweep (Abc_Obj_t *pNode, int fVerbose)
static void Abc_NodeConstantInput (Abc_Obj_t *pNode, Abc_Obj_t *pFanin, bool fConst0)
static void Abc_NodeComplementInput (Abc_Obj_t *pNode, Abc_Obj_t *pFanin)
bool Abc_NtkFraigSweep (Abc_Ntk_t *pNtk, int fUseInv, int fExdc, int fVerbose, int fVeryVerbose)
int Abc_NtkCleanup (Abc_Ntk_t *pNtk, int fVerbose)
int Abc_NtkSweep (Abc_Ntk_t *pNtk, int fVerbose)
int Abc_NodeRemoveNonCurrentObjects (Abc_Ntk_t *pNtk)
void Abc_NtkSetTravId_rec (Abc_Obj_t *pObj)
int Abc_NtkCheckConstant_rec (Abc_Obj_t *pObj)
int Abc_NtkLatchSweep (Abc_Ntk_t *pNtk)
int Abc_NtkReplaceAutonomousLogic (Abc_Ntk_t *pNtk)
int Abc_NtkCleanupSeq (Abc_Ntk_t *pNtk, int fLatchSweep, int fAutoSweep, int fVerbose)

Function Documentation

void Abc_NodeComplementInput ( Abc_Obj_t *  pNode,
Abc_Obj_t *  pFanin 
) [static]

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

Synopsis [Changes the polarity of one fanin.]

Description []

SideEffects []

SeeAlso []

Definition at line 659 of file abcSweep.c.

00660 {
00661     DdManager * dd = pNode->pNtk->pManFunc;
00662     DdNode * bVar, * bCof0, * bCof1;
00663     int iFanin;
00664     assert( Abc_NtkIsBddLogic(pNode->pNtk) ); 
00665     if ( (iFanin = Vec_IntFind( &pNode->vFanins, pFanin->Id )) == -1 )
00666     {
00667         printf( "Node %s should be among", Abc_ObjName(pFanin) );
00668         printf( " the fanins of node %s...\n", Abc_ObjName(pNode) );
00669         return;
00670     }
00671     bVar = Cudd_bddIthVar( dd, iFanin );
00672     bCof0 = Cudd_Cofactor( dd, pNode->pData, Cudd_Not(bVar) );   Cudd_Ref( bCof0 );
00673     bCof1 = Cudd_Cofactor( dd, pNode->pData, bVar );             Cudd_Ref( bCof1 );
00674     Cudd_RecursiveDeref( dd, pNode->pData );
00675     pNode->pData = Cudd_bddIte( dd, bVar, bCof0, bCof1 );        Cudd_Ref( pNode->pData );
00676     Cudd_RecursiveDeref( dd, bCof0 );
00677     Cudd_RecursiveDeref( dd, bCof1 );
00678 }

void Abc_NodeConstantInput ( Abc_Obj_t *  pNode,
Abc_Obj_t *  pFanin,
bool  fConst0 
) [static]

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

Synopsis [Replaces the local function by its cofactor.]

Description []

SideEffects []

SeeAlso []

Definition at line 631 of file abcSweep.c.

00632 {
00633     DdManager * dd = pNode->pNtk->pManFunc;
00634     DdNode * bVar, * bTemp;
00635     int iFanin;
00636     assert( Abc_NtkIsBddLogic(pNode->pNtk) ); 
00637     if ( (iFanin = Vec_IntFind( &pNode->vFanins, pFanin->Id )) == -1 )
00638     {
00639         printf( "Node %s should be among", Abc_ObjName(pFanin) );
00640         printf( " the fanins of node %s...\n", Abc_ObjName(pNode) );
00641         return;
00642     }
00643     bVar = Cudd_NotCond( Cudd_bddIthVar(dd, iFanin), fConst0 );
00644     pNode->pData = Cudd_Cofactor( dd, bTemp = pNode->pData, bVar );   Cudd_Ref( pNode->pData );
00645     Cudd_RecursiveDeref( dd, bTemp );
00646 }

int Abc_NodeDroppingCost ( Abc_Obj_t *  pNode  )  [static]

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

Synopsis [Returns the number of literals saved if this node becomes useless.]

Description []

SideEffects []

SeeAlso []

Definition at line 452 of file abcSweep.c.

00453 { 
00454     return 1;
00455 }

int Abc_NodeRemoveNonCurrentObjects ( Abc_Ntk_t *  pNtk  ) 

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

Synopsis [Removes all objects whose trav ID is not current.]

Description []

SideEffects []

SeeAlso []

Definition at line 693 of file abcSweep.c.

00694 {
00695     Abc_Obj_t * pObj;
00696     int Counter, i;
00697     int fVerbose = 0;
00698 
00699     // report on the nodes to be deleted
00700     if ( fVerbose )
00701     {
00702         printf( "These nodes will be deleted: \n" );
00703         Abc_NtkForEachObj( pNtk, pObj, i )
00704             if ( !Abc_NodeIsTravIdCurrent( pObj ) )
00705             {
00706                 printf( "    " );
00707                 Abc_ObjPrint( stdout, pObj );
00708             }
00709     }
00710     
00711     // delete the nodes    
00712     Counter = 0;
00713     Abc_NtkForEachObj( pNtk, pObj, i )
00714         if ( !Abc_NodeIsTravIdCurrent( pObj ) )
00715         {
00716             Abc_NtkDeleteObj( pObj );
00717             Counter++;
00718         }
00719     return Counter;
00720 }

static void Abc_NodeSweep ( Abc_Obj_t *  pNode,
int  fVerbose 
) [static]
int Abc_NtkCheckConstant_rec ( Abc_Obj_t *  pObj  ) 

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

Synopsis [Check if the fanin of this latch is a constant.]

Description [Returns 0/1 if constant; -1 if not a constant.]

SideEffects []

SeeAlso []

Definition at line 753 of file abcSweep.c.

00754 {
00755     if ( Abc_ObjFaninNum(pObj) == 0 )
00756     {
00757         if ( !Abc_ObjIsNode(pObj) )
00758             return -1;
00759         if ( Abc_NodeIsConst0(pObj) )
00760             return 0;
00761         if ( Abc_NodeIsConst1(pObj) )
00762             return 1;
00763         assert( 0 );
00764         return -1;
00765     }
00766     if ( Abc_ObjIsLatch(pObj) || Abc_ObjFaninNum(pObj) > 1 )
00767         return -1;
00768     if ( !Abc_ObjIsNode(pObj) || Abc_NodeIsBuf(pObj) )
00769         return Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pObj) );
00770     if ( Abc_NodeIsInv(pObj) )
00771     {
00772         int RetValue = Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pObj) );
00773         if ( RetValue == 0 )
00774             return 1;
00775         if ( RetValue == 1 )
00776             return 0;
00777         return RetValue;
00778     }
00779     assert( 0 );
00780     return -1;
00781 }

int Abc_NtkCleanup ( Abc_Ntk_t *  pNtk,
int  fVerbose 
)

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

Synopsis [Removes dangling nodes.]

Description [Returns the number of nodes removed.]

SideEffects []

SeeAlso []

Definition at line 472 of file abcSweep.c.

00473 {
00474     Vec_Ptr_t * vNodes;
00475     int Counter;
00476     assert( Abc_NtkIsLogic(pNtk) );
00477     // mark the nodes reachable from the POs
00478     vNodes = Abc_NtkDfs( pNtk, 0 );
00479     Counter = Abc_NtkReduceNodes( pNtk, vNodes );
00480     if ( fVerbose )
00481         printf( "Cleanup removed %d dangling nodes.\n", Counter );
00482     Vec_PtrFree( vNodes );
00483     return Counter;
00484 }

int Abc_NtkCleanupSeq ( Abc_Ntk_t *  pNtk,
int  fLatchSweep,
int  fAutoSweep,
int  fVerbose 
)

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

Synopsis [Sequential cleanup.]

Description [Performs three tasks:

  • Removes logic that does not feed into POs.
  • Removes latches driven by constant values equal to the initial state.
  • Replaces the autonomous components by additional PI variables.]

SideEffects []

SeeAlso []

Definition at line 904 of file abcSweep.c.

00905 {
00906     Vec_Ptr_t * vNodes;
00907     int Counter;
00908     assert( Abc_NtkIsLogic(pNtk) );
00909     // mark the nodes reachable from the POs
00910     vNodes = Abc_NtkDfsSeq( pNtk );
00911     Vec_PtrFree( vNodes );
00912     // remove the non-marked nodes
00913     Counter = Abc_NodeRemoveNonCurrentObjects( pNtk );
00914     if ( fVerbose )
00915         printf( "Cleanup removed %4d dangling objects.\n", Counter );
00916     // check if some of the latches can be removed
00917     if ( fLatchSweep )
00918     {
00919         Counter = Abc_NtkLatchSweep( pNtk );
00920         if ( fVerbose )
00921             printf( "Cleanup removed %4d redundant latches.\n", Counter );
00922     }
00923     // detect the autonomous components
00924     if ( fAutoSweep )
00925     {
00926         vNodes = Abc_NtkDfsSeqReverse( pNtk );
00927         Vec_PtrFree( vNodes );
00928         // replace them by PIs
00929         Counter = Abc_NtkReplaceAutonomousLogic( pNtk );
00930         if ( fVerbose )
00931             printf( "Cleanup added   %4d additional PIs.\n", Counter );
00932         // remove the non-marked nodes
00933         Counter = Abc_NodeRemoveNonCurrentObjects( pNtk );
00934         if ( fVerbose )
00935             printf( "Cleanup removed %4d autonomous objects.\n", Counter );
00936     }
00937     // check
00938     if ( !Abc_NtkCheck( pNtk ) )
00939         printf( "Abc_NtkCleanupSeq: The network check has failed.\n" );
00940     return 1;
00941 }

stmm_table * Abc_NtkFraigEquiv ( Abc_Ntk_t *  pNtk,
int  fUseInv,
int  fVerbose,
int  fVeryVerbose 
) [static]

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

Synopsis [Collects equivalence classses of node in the network.]

Description []

SideEffects []

SeeAlso []

Definition at line 184 of file abcSweep.c.

00185 {
00186     Abc_Obj_t * pList, * pNode, * pNodeAig;
00187     Fraig_Node_t * gNode;
00188     Abc_Obj_t ** ppSlot;
00189     stmm_table * tStrash2Net;
00190     stmm_table * tResult;
00191     stmm_generator * gen;
00192     int c, Counter;
00193 
00194     // create mapping of strashed nodes into the corresponding network nodes
00195     tStrash2Net = stmm_init_table(stmm_ptrcmp,stmm_ptrhash);
00196     Abc_NtkForEachNode( pNtk, pNode, c )
00197     {
00198         // skip the constant input nodes
00199         if ( Abc_ObjFaninNum(pNode) == 0 )
00200             continue;
00201         // get the strashed node
00202         pNodeAig = pNode->pCopy;
00203         // skip the dangling nodes
00204         if ( pNodeAig == NULL )
00205             continue;
00206         // skip the nodes that fanout into COs
00207         if ( Abc_NodeFindCoFanout(pNode) )
00208             continue;
00209         // get the FRAIG node
00210         gNode = Fraig_NotCond( Abc_ObjRegular(pNodeAig)->pCopy, Abc_ObjIsComplement(pNodeAig) );
00211         if ( !stmm_find_or_add( tStrash2Net, (char *)Fraig_Regular(gNode), (char ***)&ppSlot ) )
00212             *ppSlot = NULL;
00213         // add the node to the list
00214         pNode->pNext = *ppSlot;
00215         *ppSlot = pNode;
00216         // mark the node if it is complemented
00217         pNode->fPhase = Fraig_IsComplement(gNode);
00218     }
00219 
00220     // print the classes
00221     c = 0;
00222     Counter = 0;
00223     tResult = stmm_init_table(stmm_ptrcmp,stmm_ptrhash);
00224     stmm_foreach_item( tStrash2Net, gen, (char **)&gNode, (char **)&pList )
00225     {
00226         // skip the trival classes
00227         if ( pList == NULL || pList->pNext == NULL )
00228             continue;
00229         // add the non-trival class
00230         stmm_insert( tResult, (char *)pList, NULL );
00231         // count nodes in the non-trival classes
00232         for ( pNode = pList; pNode; pNode = pNode->pNext )
00233             Counter++;
00234 
00235         if ( fVeryVerbose )
00236         {
00237             printf( "Class %2d : {", c );
00238             for ( pNode = pList; pNode; pNode = pNode->pNext )
00239             {
00240                 pNode->pCopy = NULL;
00241                 printf( " %s", Abc_ObjName(pNode) );
00242                 printf( "(%c)", pNode->fPhase? '-' : '+' );
00243                 printf( "(%d)", pNode->Level );
00244             }
00245             printf( " }\n" );
00246             c++;
00247         }
00248     }
00249     if ( fVerbose || fVeryVerbose )
00250     {
00251         printf( "Sweeping stats for network \"%s\":\n", pNtk->pName );
00252         printf( "Internal nodes = %d. Different functions (up to compl) = %d.\n", Abc_NtkNodeNum(pNtk), stmm_count(tStrash2Net) );
00253         printf( "Non-trivial classes = %d. Nodes in non-trivial classes = %d.\n", stmm_count(tResult), Counter );
00254     }
00255     stmm_free_table( tStrash2Net );
00256     return tResult;
00257 }

void Abc_NtkFraigMergeClass ( Abc_Ntk_t *  pNtk,
Abc_Obj_t *  pChain,
int  fUseInv,
int  fVerbose 
) [static]

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

Synopsis [Process one equivalence class of nodes.]

Description [This function does not remove the nodes. It only switches around the connections.]

SideEffects []

SeeAlso []

Definition at line 385 of file abcSweep.c.

00386 {
00387     Abc_Obj_t * pListDir, * pListInv;
00388     Abc_Obj_t * pNodeMin, * pNodeMinInv;
00389     Abc_Obj_t * pNode, * pNext;
00390 
00391     assert( pChain );
00392     assert( pChain->pNext );
00393 
00394     // find the node with the smallest number of logic levels
00395     pNodeMin = pChain;
00396     for ( pNode = pChain->pNext; pNode; pNode = pNode->pNext )
00397         if (  pNodeMin->Level >  pNode->Level || 
00398             ( pNodeMin->Level == pNode->Level && 
00399               Abc_NodeDroppingCost(pNodeMin) < Abc_NodeDroppingCost(pNode) ) )
00400             pNodeMin = pNode;
00401 
00402     // divide the nodes into two parts: 
00403     // those that need the invertor and those that don't need
00404     pListDir = pListInv = NULL;
00405     for ( pNode = pChain, pNext = pChain->pNext; 
00406           pNode; 
00407           pNode = pNext, pNext = pNode? pNode->pNext : NULL )
00408     {
00409         if ( pNode == pNodeMin )
00410             continue;
00411         // check to which class the node belongs
00412         if ( pNodeMin->fPhase == pNode->fPhase )
00413         {
00414             pNode->pNext = pListDir;
00415             pListDir = pNode;
00416         }
00417         else
00418         {
00419             pNode->pNext = pListInv;
00420             pListInv = pNode;
00421         }
00422     }
00423 
00424     // move the fanouts of the direct nodes
00425     for ( pNode = pListDir; pNode; pNode = pNode->pNext )
00426         Abc_ObjTransferFanout( pNode, pNodeMin );
00427 
00428     // skip if there are no inverted nodes
00429     if ( pListInv == NULL )
00430         return;
00431 
00432     // add the invertor
00433     pNodeMinInv = Abc_NtkCreateNodeInv( pNtk, pNodeMin );
00434    
00435     // move the fanouts of the inverted nodes
00436     for ( pNode = pListInv; pNode; pNode = pNode->pNext )
00437         Abc_ObjTransferFanout( pNode, pNodeMinInv );
00438 }

void Abc_NtkFraigMergeClassMapped ( Abc_Ntk_t *  pNtk,
Abc_Obj_t *  pChain,
int  fUseInv,
int  fVerbose 
) [static]

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

Synopsis [Transforms the list of one-phase equivalent nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 303 of file abcSweep.c.

00304 {
00305     Abc_Obj_t * pListDir, * pListInv;
00306     Abc_Obj_t * pNodeMin, * pNode, * pNext;
00307     float Arrival1, Arrival2;
00308 
00309     assert( pChain );
00310     assert( pChain->pNext );
00311 
00312     // divide the nodes into two parts: 
00313     // those that need the invertor and those that don't need
00314     pListDir = pListInv = NULL;
00315     for ( pNode = pChain, pNext = pChain->pNext; 
00316           pNode; 
00317           pNode = pNext, pNext = pNode? pNode->pNext : NULL )
00318     {
00319         // check to which class the node belongs
00320         if ( pNode->fPhase == 1 )
00321         {
00322             pNode->pNext = pListDir;
00323             pListDir = pNode;
00324         }
00325         else
00326         {
00327             pNode->pNext = pListInv;
00328             pListInv = pNode;
00329         }
00330     }
00331 
00332     // find the node with the smallest number of logic levels
00333     pNodeMin = pListDir;
00334     for ( pNode = pListDir; pNode; pNode = pNode->pNext )
00335     {
00336         Arrival1 = Abc_NodeReadArrival(pNodeMin)->Worst;
00337         Arrival2 = Abc_NodeReadArrival(pNode   )->Worst;
00338 //        assert( Abc_ObjIsCi(pNodeMin) || Arrival1 > 0 );
00339 //        assert( Abc_ObjIsCi(pNode)    || Arrival2 > 0 );
00340         if (  Arrival1 > Arrival2 ||
00341               Arrival1 == Arrival2 && pNodeMin->Level >  pNode->Level || 
00342               Arrival1 == Arrival2 && pNodeMin->Level == pNode->Level && 
00343               Abc_NodeDroppingCost(pNodeMin) < Abc_NodeDroppingCost(pNode)  )
00344             pNodeMin = pNode;
00345     }
00346 
00347     // move the fanouts of the direct nodes
00348     for ( pNode = pListDir; pNode; pNode = pNode->pNext )
00349         if ( pNode != pNodeMin )
00350             Abc_ObjTransferFanout( pNode, pNodeMin );
00351 
00352     // find the node with the smallest number of logic levels
00353     pNodeMin = pListInv;
00354     for ( pNode = pListInv; pNode; pNode = pNode->pNext )
00355     {
00356         Arrival1 = Abc_NodeReadArrival(pNodeMin)->Worst;
00357         Arrival2 = Abc_NodeReadArrival(pNode   )->Worst;
00358 //        assert( Abc_ObjIsCi(pNodeMin) || Arrival1 > 0 );
00359 //        assert( Abc_ObjIsCi(pNode)    || Arrival2 > 0 );
00360         if (  Arrival1 > Arrival2 ||
00361               Arrival1 == Arrival2 && pNodeMin->Level >  pNode->Level || 
00362               Arrival1 == Arrival2 && pNodeMin->Level == pNode->Level && 
00363               Abc_NodeDroppingCost(pNodeMin) < Abc_NodeDroppingCost(pNode)  )
00364             pNodeMin = pNode;
00365     }
00366 
00367     // move the fanouts of the direct nodes
00368     for ( pNode = pListInv; pNode; pNode = pNode->pNext )
00369         if ( pNode != pNodeMin )
00370             Abc_ObjTransferFanout( pNode, pNodeMin );
00371 }

bool Abc_NtkFraigSweep ( Abc_Ntk_t *  pNtk,
int  fUseInv,
int  fExdc,
int  fVerbose,
int  fVeryVerbose 
)

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

Synopsis [Sweping functionally equivalence nodes.]

Description [Removes gates with equivalent functionality. Works for both technology-independent and mapped networks. If the flag is set, allows adding inverters at the gate outputs.]

SideEffects []

SeeAlso []

Definition at line 57 of file abcSweep.c.

00058 {
00059     Fraig_Params_t Params;
00060     Abc_Ntk_t * pNtkAig;
00061     Fraig_Man_t * pMan;
00062     stmm_table * tEquiv;
00063     Abc_Obj_t * pObj;
00064     int i, fUseTrick;
00065 
00066     assert( !Abc_NtkIsStrash(pNtk) );
00067 
00068     // save gate assignments
00069     fUseTrick = 0;
00070     if ( Abc_NtkIsMappedLogic(pNtk) )
00071     {
00072         fUseTrick = 1;
00073         Abc_NtkForEachNode( pNtk, pObj, i )
00074             pObj->pNext = pObj->pData;
00075     }
00076     // derive the AIG
00077     pNtkAig = Abc_NtkStrash( pNtk, 0, 1, 0 );
00078     // reconstruct gate assignments
00079     if ( fUseTrick )
00080     {
00081         extern void * Abc_FrameReadLibGen(); 
00082         Hop_ManStop( pNtk->pManFunc );
00083         pNtk->pManFunc = Abc_FrameReadLibGen();
00084         pNtk->ntkFunc = ABC_FUNC_MAP;
00085         Abc_NtkForEachNode( pNtk, pObj, i )
00086             pObj->pData = pObj->pNext, pObj->pNext = NULL;
00087     }
00088 
00089     // perform fraiging of the AIG
00090     Fraig_ParamsSetDefault( &Params );
00091     pMan = Abc_NtkToFraig( pNtkAig, &Params, 0, 0 );   
00092     // cannot use EXDC with FRAIG because it can create classes of equivalent FRAIG nodes
00093     // with representative nodes that do not correspond to the nodes with the current network
00094 
00095     // update FRAIG using EXDC
00096     if ( fExdc )
00097     {
00098         if ( pNtk->pExdc == NULL )
00099             printf( "Warning: Networks has no EXDC.\n" );
00100         else
00101             Abc_NtkFraigSweepUsingExdc( pMan, pNtk );
00102     }
00103     // assign levels to the nodes of the network
00104     Abc_NtkLevel( pNtk );
00105 
00106     // collect the classes of equivalent nets
00107     tEquiv = Abc_NtkFraigEquiv( pNtk, fUseInv, fVerbose, fVeryVerbose );
00108 
00109     // transform the network into the equivalent one
00110     Abc_NtkFraigTransform( pNtk, tEquiv, fUseInv, fVerbose );
00111     stmm_free_table( tEquiv );
00112 
00113     // free the manager
00114     Fraig_ManFree( pMan );
00115     Abc_NtkDelete( pNtkAig );
00116 
00117     // cleanup the dangling nodes
00118     if ( Abc_NtkHasMapping(pNtk) )
00119         Abc_NtkCleanup( pNtk, fVerbose );
00120     else
00121         Abc_NtkSweep( pNtk, fVerbose );
00122 
00123     // check
00124     if ( !Abc_NtkCheck( pNtk ) )
00125     {
00126         printf( "Abc_NtkFraigSweep: The network check has failed.\n" );
00127         return 0;
00128     }
00129     return 1;
00130 }

void Abc_NtkFraigSweepUsingExdc ( Fraig_Man_t *  pMan,
Abc_Ntk_t *  pNtk 
) [static]

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

FileName [abcDsd.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Technology dependent sweep.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

] DECLARATIONS ///

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

Synopsis [Sweep the network using EXDC.]

Description []

SideEffects []

SeeAlso []

Definition at line 143 of file abcSweep.c.

00144 {
00145     Fraig_Node_t * gNodeExdc, * gNode, * gNodeRes;
00146     Abc_Obj_t * pNode, * pNodeAig;
00147     int i;
00148     extern Fraig_Node_t * Abc_NtkToFraigExdc( Fraig_Man_t * pMan, Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkExdc );
00149 
00150     assert( pNtk->pExdc );
00151     // derive FRAIG node representing don't-cares in the EXDC network
00152     gNodeExdc = Abc_NtkToFraigExdc( pMan, pNtk, pNtk->pExdc );
00153     // update the node pointers
00154     Abc_NtkForEachNode( pNtk, pNode, i )
00155     {
00156         // skip the constant input nodes
00157         if ( Abc_ObjFaninNum(pNode) == 0 )
00158             continue;
00159         // get the strashed node
00160         pNodeAig = pNode->pCopy;
00161         // skip the dangling nodes
00162         if ( pNodeAig == NULL )
00163             continue;
00164         // get the FRAIG node
00165         gNode = Fraig_NotCond( Abc_ObjRegular(pNodeAig)->pCopy, Abc_ObjIsComplement(pNodeAig) );
00166         // perform ANDing with EXDC
00167         gNodeRes = Fraig_NodeAnd( pMan, gNode, Fraig_Not(gNodeExdc) );
00168         // write the node back
00169         Abc_ObjRegular(pNodeAig)->pCopy = (Abc_Obj_t *)Fraig_NotCond( gNodeRes, Abc_ObjIsComplement(pNodeAig) );
00170     }
00171 }

void Abc_NtkFraigTransform ( Abc_Ntk_t *  pNtk,
stmm_table *  tEquiv,
int  fUseInv,
bool  fVerbose 
) [static]

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

Synopsis [Transforms the network using the equivalence relation on nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 271 of file abcSweep.c.

00272 {
00273     stmm_generator * gen;
00274     Abc_Obj_t * pList;
00275     if ( stmm_count(tEquiv) == 0 )
00276         return;
00277     // merge nodes in the classes
00278     if ( Abc_NtkHasMapping( pNtk ) )
00279     {
00280         Abc_NtkDelayTrace( pNtk );
00281         stmm_foreach_item( tEquiv, gen, (char **)&pList, NULL )
00282             Abc_NtkFraigMergeClassMapped( pNtk, pList, fUseInv, fVerbose );
00283     }
00284     else 
00285     {
00286         stmm_foreach_item( tEquiv, gen, (char **)&pList, NULL )
00287             Abc_NtkFraigMergeClass( pNtk, pList, fUseInv, fVerbose );
00288     }
00289 }

int Abc_NtkLatchSweep ( Abc_Ntk_t *  pNtk  ) 

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

Synopsis [Removes redundant latches.]

Description [The redundant latches are of two types:

  • Latches fed by a constant which matches the init value of the latch.
  • Latches fed by a constant which does not match the init value of the latch can be all replaced by one latch.]

SideEffects []

SeeAlso []

Definition at line 797 of file abcSweep.c.

00798 {
00799     Abc_Obj_t * pFanin, * pLatch, * pLatchPivot = NULL;
00800     int Counter, RetValue, i;
00801     Counter = 0;
00802     // go through the latches
00803     Abc_NtkForEachLatch( pNtk, pLatch, i )
00804     {
00805         // check if the latch has constant input
00806         RetValue = Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pLatch) );
00807         if ( RetValue == -1 )
00808             continue;
00809         // found a latch with constant fanin
00810         if ( (RetValue == 1 && Abc_LatchIsInit0(pLatch)) ||
00811              (RetValue == 0 && Abc_LatchIsInit1(pLatch)) )
00812         {
00813             // fanin constant differs from the latch init value
00814             if ( pLatchPivot == NULL )
00815             {
00816                 pLatchPivot = pLatch;
00817                 continue;
00818             }
00819             if ( Abc_LatchInit(pLatch) != Abc_LatchInit(pLatchPivot) ) // add inverter
00820                 pFanin = Abc_NtkCreateNodeInv( pNtk, Abc_ObjFanout0(pLatchPivot) );
00821             else
00822                 pFanin = Abc_ObjFanout0(pLatchPivot);
00823         }
00824         else
00825             pFanin = Abc_ObjFanin0(Abc_ObjFanin0(pLatch));
00826         // replace latch
00827         Abc_ObjTransferFanout( Abc_ObjFanout0(pLatch), pFanin );
00828         // delete the extra nodes
00829         Abc_NtkDeleteObj_rec( Abc_ObjFanout0(pLatch), 0 );
00830         Counter++;
00831     }
00832     return Counter;
00833 }

int Abc_NtkReduceNodes ( Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vNodes 
) [static]

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

Synopsis [Preserves the nodes collected in the array.]

Description [Returns the number of nodes removed.]

SideEffects []

SeeAlso []

Definition at line 497 of file abcSweep.c.

00498 {
00499     Abc_Obj_t * pNode;
00500     int i, Counter;
00501     assert( Abc_NtkIsLogic(pNtk) );
00502     // mark the nodes reachable from the POs
00503     Vec_PtrForEachEntry( vNodes, pNode, i )
00504         pNode->fMarkA = 1;
00505     // remove the non-marked nodes
00506     Counter = 0;
00507     Abc_NtkForEachNode( pNtk, pNode, i )
00508         if ( pNode->fMarkA == 0 )
00509         {
00510             Abc_NtkDeleteObj( pNode );
00511             Counter++;
00512         }
00513     // unmark the remaining nodes
00514     Vec_PtrForEachEntry( vNodes, pNode, i )
00515         pNode->fMarkA = 0;
00516     // check
00517     if ( !Abc_NtkCheck( pNtk ) )
00518         printf( "Abc_NtkCleanup: The network check has failed.\n" );
00519     return Counter;
00520 }

int Abc_NtkReplaceAutonomousLogic ( Abc_Ntk_t *  pNtk  ) 

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

Synopsis [Replaces autonumnous logic by free inputs.]

Description [Assumes that non-autonomous logic is marked with the current ID.]

SideEffects []

SeeAlso []

Definition at line 847 of file abcSweep.c.

00848 {
00849     Abc_Obj_t * pNode, * pFanin;
00850     Vec_Ptr_t * vNodes;
00851     int i, k, Counter;
00852     // collect the nodes that feed into the reachable logic
00853     vNodes = Vec_PtrAlloc( 100 );
00854     Abc_NtkForEachObj( pNtk, pNode, i )
00855     {
00856         // skip non-visited fanins
00857         if ( !Abc_NodeIsTravIdCurrent(pNode) )
00858             continue;
00859         // look for non-visited fanins
00860         Abc_ObjForEachFanin( pNode, pFanin, k )
00861         {
00862             // skip visited fanins
00863             if ( Abc_NodeIsTravIdCurrent(pFanin) )
00864                 continue;
00865             // skip constants and latches fed by constants
00866             if ( Abc_NtkCheckConstant_rec(pFanin) != -1 ||
00867                  (Abc_ObjIsBo(pFanin) && Abc_NtkCheckConstant_rec(Abc_ObjFanin0(Abc_ObjFanin0(pFanin))) != -1) )
00868             {
00869                 Abc_NtkSetTravId_rec( pFanin );
00870                 continue;
00871             }
00872             assert( !Abc_ObjIsLatch(pFanin) );
00873             Vec_PtrPush( vNodes, pFanin );
00874         }
00875     }
00876     Vec_PtrUniqify( vNodes, Abc_ObjPointerCompare );
00877     // replace these nodes by the PIs
00878     Vec_PtrForEachEntry( vNodes, pNode, i )
00879     {
00880         pFanin = Abc_NtkCreatePi(pNtk);
00881         Abc_ObjAssignName( pFanin, Abc_ObjName(pFanin), NULL );
00882         Abc_NodeSetTravIdCurrent( pFanin );
00883         Abc_ObjTransferFanout( pNode, pFanin );
00884     }
00885     Counter = Vec_PtrSize(vNodes);
00886     Vec_PtrFree( vNodes );
00887     return Counter;
00888 }

void Abc_NtkSetTravId_rec ( Abc_Obj_t *  pObj  ) 

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

Synopsis [Check if the fanin of this latch is a constant.]

Description [Returns 0/1 if constant; -1 if not a constant.]

SideEffects []

SeeAlso []

Definition at line 733 of file abcSweep.c.

00734 {
00735     Abc_NodeSetTravIdCurrent(pObj);
00736     if ( Abc_ObjFaninNum(pObj) == 0 )
00737         return;
00738     assert( Abc_ObjFaninNum(pObj) == 1 );
00739     Abc_NtkSetTravId_rec( Abc_ObjFanin0(pObj) );    
00740 }

int Abc_NtkSweep ( Abc_Ntk_t *  pNtk,
int  fVerbose 
)

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

Synopsis [Tranditional sweep of the network.]

Description [Propagates constant and single-input node, removes dangling nodes.]

SideEffects []

SeeAlso []

Definition at line 536 of file abcSweep.c.

00537 {
00538     Vec_Ptr_t * vNodes;
00539     Abc_Obj_t * pNode, * pFanout, * pDriver;
00540     int i, nNodesOld;
00541     assert( Abc_NtkIsLogic(pNtk) ); 
00542     // convert network to BDD representation
00543     if ( !Abc_NtkToBdd(pNtk) )
00544     {
00545         fprintf( stdout, "Converting to BDD has failed.\n" );
00546         return 1;
00547     }
00548     // perform cleanup
00549     nNodesOld = Abc_NtkNodeNum(pNtk);
00550     Abc_NtkCleanup( pNtk, 0 );
00551     // prepare nodes for sweeping
00552     Abc_NtkRemoveDupFanins(pNtk);
00553     Abc_NtkMinimumBase(pNtk);
00554     // collect sweepable nodes
00555     vNodes = Vec_PtrAlloc( 100 );
00556     Abc_NtkForEachNode( pNtk, pNode, i )
00557         if ( Abc_ObjFaninNum(pNode) < 2 )
00558             Vec_PtrPush( vNodes, pNode );
00559     // sweep the nodes
00560     while ( Vec_PtrSize(vNodes) > 0 )
00561     {
00562         // get any sweepable node
00563         pNode = Vec_PtrPop(vNodes);
00564         if ( !Abc_ObjIsNode(pNode) )
00565             continue;
00566         // get any non-CO fanout of this node
00567         pFanout = Abc_NodeFindNonCoFanout(pNode);
00568         if ( pFanout == NULL )
00569             continue;
00570         assert( Abc_ObjIsNode(pFanout) );
00571         // transform the function of the fanout
00572         if ( Abc_ObjFaninNum(pNode) == 0 )
00573             Abc_NodeConstantInput( pFanout, pNode, Abc_NodeIsConst0(pNode) );
00574         else 
00575         {
00576             assert( Abc_ObjFaninNum(pNode) == 1 );
00577             pDriver = Abc_ObjFanin0(pNode);
00578             if ( Abc_NodeIsInv(pNode) )
00579                 Abc_NodeComplementInput( pFanout, pNode );
00580             Abc_ObjPatchFanin( pFanout, pNode, pDriver );
00581         }
00582         Abc_NodeRemoveDupFanins( pFanout );
00583         Abc_NodeMinimumBase( pFanout );
00584         // check if the fanout should be added
00585         if ( Abc_ObjFaninNum(pFanout) < 2 )
00586             Vec_PtrPush( vNodes, pFanout );
00587         // check if the node has other fanouts
00588         if ( Abc_ObjFanoutNum(pNode) > 0 )
00589             Vec_PtrPush( vNodes, pNode );
00590         else
00591             Abc_NtkDeleteObj_rec( pNode, 1 );
00592     }
00593     Vec_PtrFree( vNodes );
00594     // sweep a node into its CO fanout if all of this is true:
00595     // (a) this node is a single-input node
00596     // (b) the driver of the node has only one fanout (this node)
00597     // (c) the driver is a node
00598     Abc_NtkForEachCo( pNtk, pFanout, i )
00599     {
00600         pNode = Abc_ObjFanin0(pFanout);
00601         if ( Abc_ObjFaninNum(pNode) != 1 )
00602             continue;
00603         pDriver = Abc_ObjFanin0(pNode);
00604         if ( !(Abc_ObjFanoutNum(pDriver) == 1 && Abc_ObjIsNode(pDriver)) )
00605             continue;
00606         // trasform this CO
00607         if ( Abc_NodeIsInv(pNode) )
00608             pDriver->pData = Cudd_Not(pDriver->pData);
00609         Abc_ObjPatchFanin( pFanout, pNode, pDriver );
00610     }
00611     // perform cleanup
00612     Abc_NtkCleanup( pNtk, 0 );
00613     // report
00614     if ( fVerbose )
00615         printf( "Sweep removed %d nodes.\n", nNodesOld - Abc_NtkNodeNum(pNtk) );
00616     return nNodesOld - Abc_NtkNodeNum(pNtk);
00617 }

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