src/aig/ivy/ivyRwrAlg.c File Reference

#include "ivy.h"
Include dependency graph for ivyRwrAlg.c:

Go to the source code of this file.

Functions

static int Ivy_ManFindAlgCut (Ivy_Obj_t *pRoot, Vec_Ptr_t *vFront, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vCone)
static Ivy_Obj_t * Ivy_NodeRewriteAlg (Ivy_Obj_t *pObj, Vec_Ptr_t *vFront, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vCone, Vec_Ptr_t *vSols, int LevelR, int fUseZeroCost)
static int Ivy_NodeCountMffc (Ivy_Obj_t *pNode)
int Ivy_ManRewriteAlg (Ivy_Man_t *p, int fUpdateLevel, int fUseZeroCost)
int Ivy_NodeCountMffc_rec (Ivy_Obj_t *pNode)
int Ivy_ManFindAlgCutCompare (Ivy_Obj_t **pp1, Ivy_Obj_t **pp2)
int Ivy_ManFindAlgCut_rec (Ivy_Obj_t *pObj, Ivy_Type_t Type, Vec_Ptr_t *vFront, Vec_Ptr_t *vCone)

Function Documentation

int Ivy_ManFindAlgCut ( Ivy_Obj_t *  pRoot,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vLeaves,
Vec_Ptr_t *  vCone 
) [static]

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

FileName [ivyRwrAlg.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [And-Inverter Graph package.]

Synopsis [Algebraic AIG rewriting.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - May 11, 2006.]

Revision [

Id
ivyRwrAlg.c,v 1.00 2006/05/11 00:00:00 alanmi Exp

] DECLARATIONS ///

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

Synopsis [Computing one algebraic cut.]

Description [Algebraic cut stops when we hit (a) CI, (b) complemented edge, (c) boundary of different gates. Returns 1 if this is a pure tree. Returns -1 if the contant 0 is detected. Return 0 if the array can be used.]

SideEffects []

SeeAlso []

Definition at line 347 of file ivyRwrAlg.c.

00348 {
00349     Ivy_Obj_t * pObj, * pPrev;
00350     int RetValue, i;
00351     assert( !Ivy_IsComplement(pRoot) );
00352     assert( Ivy_ObjIsNode(pRoot) );
00353     // clear the frontier and collect the nodes
00354     Vec_PtrClear( vCone );
00355     Vec_PtrClear( vFront );
00356     Vec_PtrClear( vLeaves );
00357     RetValue = Ivy_ManFindAlgCut_rec( pRoot, Ivy_ObjType(pRoot), vFront, vCone );
00358     // clean the marks
00359     Vec_PtrForEachEntry( vCone, pObj, i )
00360         pObj->fMarkA = pObj->fMarkB = 0;
00361     // quit if the same node is found in both polarities
00362     if ( RetValue == -1 )
00363         return -1;
00364     // return if the node is the root of a tree
00365     if ( RetValue == 1 )
00366         return 1;
00367     // return if the cut is composed of two nodes
00368     if ( Vec_PtrSize(vFront) <= 2 )
00369         return 1;
00370     // sort the entries in increasing order
00371     Vec_PtrSort( vFront, Ivy_ManFindAlgCutCompare );
00372     // remove duplicates from vFront and save the nodes in vLeaves
00373     pPrev = Vec_PtrEntry(vFront, 0);
00374     Vec_PtrPush( vLeaves, pPrev );
00375     Vec_PtrForEachEntryStart( vFront, pObj, i, 1 )
00376     {
00377         // compare current entry and the previous entry
00378         if ( pObj == pPrev )
00379         {
00380             if ( Ivy_ObjIsExor(pRoot) ) // A <+> A = 0
00381             {
00382                 // vLeaves are no longer structural support of pRoot!!!
00383                 Vec_PtrPop(vLeaves);  
00384                 pPrev = Vec_PtrSize(vLeaves) == 0 ? NULL : Vec_PtrEntryLast(vLeaves);
00385             }
00386             continue;
00387         }
00388         if ( pObj == Ivy_Not(pPrev) )
00389         {
00390             assert( Ivy_ObjIsAnd(pRoot) );
00391             return -1;
00392         }
00393         pPrev = pObj;
00394         Vec_PtrPush( vLeaves, pObj );
00395     }
00396     if ( Vec_PtrSize(vLeaves) == 0 )
00397         return -1;
00398     if ( Vec_PtrSize(vLeaves) <= 2 )
00399         return 1;
00400     return 0;
00401 }

int Ivy_ManFindAlgCut_rec ( Ivy_Obj_t *  pObj,
Ivy_Type_t  Type,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vCone 
)

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

Synopsis [Computing one algebraic cut.]

Description [Returns 1 if the tree-leaves of this node where traversed and found to have no external references (and have not been collected). Returns 0 if the tree-leaves have external references and are collected.]

SideEffects []

SeeAlso []

Definition at line 276 of file ivyRwrAlg.c.

00277 {
00278     int RetValue0, RetValue1;
00279     Ivy_Obj_t * pObjR = Ivy_Regular(pObj);
00280     assert( !Ivy_ObjIsBuf(pObjR) );
00281     assert( Type != IVY_EXOR || !Ivy_IsComplement(pObj) );
00282 
00283     // make sure the node is not visited twice in different polarities
00284     if ( Ivy_IsComplement(pObj) )
00285     { // if complemented, mark B
00286         if ( pObjR->fMarkA )
00287             return -1;
00288         pObjR->fMarkB = 1;
00289     }
00290     else
00291     { // if non-complicated, mark A
00292         if ( pObjR->fMarkB )
00293             return -1;
00294         pObjR->fMarkA = 1;
00295     }
00296     Vec_PtrPush( vCone, pObjR );
00297 
00298     // if the node is the end of the tree, return
00299     if ( Ivy_IsComplement(pObj) || Ivy_ObjType(pObj) != Type )
00300     {
00301         if ( Ivy_ObjRefs(pObjR) == 1 )
00302             return 1;
00303         assert( Ivy_ObjRefs(pObjR) > 1 );
00304         Vec_PtrPush( vFront, pObj );
00305         return 0;
00306     }
00307 
00308     // branch on the node
00309     assert( !Ivy_IsComplement(pObj) );
00310     assert( Ivy_ObjIsNode(pObj) );
00311     // what if buffer has more than one fanout???
00312     RetValue0 = Ivy_ManFindAlgCut_rec( Ivy_ObjReal( Ivy_ObjChild0(pObj) ), Type, vFront, vCone );
00313     RetValue1 = Ivy_ManFindAlgCut_rec( Ivy_ObjReal( Ivy_ObjChild1(pObj) ), Type, vFront, vCone );
00314     if ( RetValue0 == -1 || RetValue1 == -1 )
00315         return -1;
00316 
00317     // the case when both have no external references
00318     if ( RetValue0 && RetValue1 )
00319     {
00320         if ( Ivy_ObjRefs(pObj) == 1 )
00321             return 1;
00322         assert( Ivy_ObjRefs(pObj) > 1 );
00323         Vec_PtrPush( vFront, pObj );
00324         return 0;
00325     }
00326     // the case when one of them has external references
00327     if ( RetValue0 )
00328         Vec_PtrPush( vFront, Ivy_ObjReal( Ivy_ObjChild0(pObj) ) );
00329     if ( RetValue1 )
00330         Vec_PtrPush( vFront, Ivy_ObjReal( Ivy_ObjChild1(pObj) ) );
00331     return 0;
00332 }

int Ivy_ManFindAlgCutCompare ( Ivy_Obj_t **  pp1,
Ivy_Obj_t **  pp2 
)

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

Synopsis [Comparison for node pointers.]

Description []

SideEffects []

SeeAlso []

Definition at line 254 of file ivyRwrAlg.c.

00255 {
00256     if ( *pp1 < *pp2 )
00257         return -1;
00258     if ( *pp1 > *pp2 )
00259         return 1;
00260     return 0;
00261 }

int Ivy_ManRewriteAlg ( Ivy_Man_t *  p,
int  fUpdateLevel,
int  fUseZeroCost 
)

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

Synopsis [Algebraic AIG rewriting.]

Description []

SideEffects []

SeeAlso []

Definition at line 46 of file ivyRwrAlg.c.

00047 {
00048     Vec_Int_t * vRequired;
00049     Vec_Ptr_t * vFront, * vLeaves, * vCone, * vSol;
00050     Ivy_Obj_t * pObj, * pResult;
00051     int i, RetValue, LevelR, nNodesOld;
00052     int CountUsed, CountUndo;
00053     vRequired = fUpdateLevel? Ivy_ManRequiredLevels( p ) : NULL;
00054     vFront    = Vec_PtrAlloc( 100 );
00055     vLeaves   = Vec_PtrAlloc( 100 );
00056     vCone     = Vec_PtrAlloc( 100 );
00057     vSol      = Vec_PtrAlloc( 100 );
00058     // go through the nodes in the topological order
00059     CountUsed = CountUndo = 0;
00060     nNodesOld = Ivy_ManObjIdNext(p);
00061     Ivy_ManForEachObj( p, pObj, i )
00062     {
00063         assert( !Ivy_ObjIsBuf(pObj) );
00064         if ( i >= nNodesOld )
00065             break;
00066         // skip no-nodes and MUX roots
00067         if ( !Ivy_ObjIsNode(pObj) || Ivy_ObjIsExor(pObj) || Ivy_ObjIsMuxType(pObj) )
00068             continue;
00069 //        if ( pObj->Id > 297 ) // 296 --- 297 
00070 //            break;
00071         if ( pObj->Id == 297 )
00072         {
00073             int x = 0;
00074         }
00075         // get the largest algebraic cut
00076         RetValue = Ivy_ManFindAlgCut( pObj, vFront, vLeaves, vCone );
00077         // the case of a trivial tree cut
00078         if ( RetValue == 1 )
00079             continue;
00080         // the case of constant 0 cone
00081         if ( RetValue == -1 )
00082         {
00083             Ivy_ObjReplace( pObj, Ivy_ManConst0(p), 1, 0, 1 ); 
00084             continue;
00085         }
00086         assert( Vec_PtrSize(vLeaves) > 2 );
00087         // get the required level for this node
00088         LevelR = vRequired? Vec_IntEntry(vRequired, pObj->Id) : 1000000;
00089         // create a new cone
00090         pResult = Ivy_NodeRewriteAlg( pObj, vFront, vLeaves, vCone, vSol, LevelR, fUseZeroCost );
00091         if ( pResult == NULL || pResult == pObj )
00092             continue;
00093         assert( Vec_PtrSize(vSol) == 1 || !Ivy_IsComplement(pResult) );
00094         if ( Ivy_ObjLevel(Ivy_Regular(pResult)) > LevelR && Ivy_ObjRefs(Ivy_Regular(pResult)) == 0 )
00095             Ivy_ObjDelete_rec(Ivy_Regular(pResult), 1), CountUndo++;
00096         else
00097             Ivy_ObjReplace( pObj, pResult, 1, 0, 1 ), CountUsed++; 
00098     }
00099     printf( "Used = %d. Undo = %d.\n", CountUsed, CountUndo );
00100     Vec_PtrFree( vFront );
00101     Vec_PtrFree( vCone );
00102     Vec_PtrFree( vSol );
00103     if ( vRequired ) Vec_IntFree( vRequired );
00104     if ( i = Ivy_ManCleanup(p) )
00105         printf( "Cleanup after rewriting removed %d dangling nodes.\n", i );
00106     if ( !Ivy_ManCheck(p) )
00107         printf( "Ivy_ManRewriteAlg(): The check has failed.\n" );
00108     return 1;
00109 }

int Ivy_NodeCountMffc ( Ivy_Obj_t *  pNode  )  [static]

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

Synopsis [Comparison for node pointers.]

Description []

SideEffects []

SeeAlso []

Definition at line 237 of file ivyRwrAlg.c.

00238 {
00239     assert( pNode->fMarkB );
00240     return 1 + Ivy_NodeCountMffc_rec( Ivy_ObjFanin0(pNode) ) + Ivy_NodeCountMffc_rec( Ivy_ObjFanin1(pNode) );
00241 }

int Ivy_NodeCountMffc_rec ( Ivy_Obj_t *  pNode  ) 

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

Synopsis [Comparison for node pointers.]

Description []

SideEffects []

SeeAlso []

Definition at line 214 of file ivyRwrAlg.c.

00215 {
00216     if ( Ivy_ObjRefs(pNode) > 0 || Ivy_ObjIsCi(pNode) || pNode->fMarkA )
00217         return 0;
00218     assert( pNode->fMarkB );
00219     pNode->fMarkA = 1;
00220 //    printf( "%d ", pNode->Id );
00221     if ( Ivy_ObjIsBuf(pNode) )
00222         return Ivy_NodeCountMffc_rec( Ivy_ObjFanin0(pNode) );
00223     return 1 + Ivy_NodeCountMffc_rec( Ivy_ObjFanin0(pNode) ) + Ivy_NodeCountMffc_rec( Ivy_ObjFanin1(pNode) );
00224 }

Ivy_Obj_t * Ivy_NodeRewriteAlg ( Ivy_Obj_t *  pObj,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vLeaves,
Vec_Ptr_t *  vCone,
Vec_Ptr_t *  vSols,
int  LevelR,
int  fUseZeroCost 
) [static]

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

Synopsis [Analizes one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 122 of file ivyRwrAlg.c.

00123 {
00124     int fVerbose = 0;
00125     Ivy_Obj_t * pTemp;
00126     int k, Counter, nMffc, RetValue;
00127 
00128     if ( fVerbose )
00129     {
00130         if ( Ivy_ObjIsExor(pObj) )
00131             printf( "x " );
00132         else
00133             printf( "  " );
00134     }
00135 
00136 /*       
00137     printf( "%d ", Vec_PtrSize(vFront) );
00138     printf( "( " );
00139     Vec_PtrForEachEntry( vFront, pTemp, k )
00140         printf( "%d ", Ivy_ObjRefs(Ivy_Regular(pTemp)) );
00141     printf( ")\n" );
00142 */
00143     // collect nodes in the cone
00144     if ( Ivy_ObjIsExor(pObj) )
00145         Ivy_ManCollectCone( pObj, vFront, vCone );
00146     else
00147         Ivy_ManCollectCone( pObj, vLeaves, vCone );
00148 
00149     // deref nodes in the cone
00150     Vec_PtrForEachEntry( vCone, pTemp, k )
00151     {
00152         Ivy_ObjRefsDec( Ivy_ObjFanin0(pTemp) );
00153         Ivy_ObjRefsDec( Ivy_ObjFanin1(pTemp) );
00154         pTemp->fMarkB = 1;
00155     }
00156 
00157     // count the MFFC size
00158     Vec_PtrForEachEntry( vFront, pTemp, k )
00159         Ivy_Regular(pTemp)->fMarkA = 1;
00160     nMffc = Ivy_NodeCountMffc( pObj );
00161     Vec_PtrForEachEntry( vFront, pTemp, k )
00162         Ivy_Regular(pTemp)->fMarkA = 0;
00163 
00164     if ( fVerbose )
00165     {
00166     Counter = 0;
00167     Vec_PtrForEachEntry( vCone, pTemp, k )
00168         Counter += (Ivy_ObjRefs(pTemp) > 0);
00169     printf( "%5d : Leaves = %2d. Cone = %2d. ConeRef = %2d.   Mffc = %d.   Lev = %d.  LevR = %d.\n", 
00170         pObj->Id, Vec_PtrSize(vFront), Vec_PtrSize(vCone), Counter-1, nMffc, Ivy_ObjLevel(pObj), LevelR );
00171     }
00172 /*
00173     printf( "Leaves:" );
00174     Vec_PtrForEachEntry( vLeaves, pTemp, k )
00175         printf( " %d%s", Ivy_Regular(pTemp)->Id, Ivy_IsComplement(pTemp)? "\'" : "" );
00176     printf( "\n" );
00177     printf( "Cone:\n" );
00178     Vec_PtrForEachEntry( vCone, pTemp, k )
00179         printf( " %5d = %d%s %d%s\n", pTemp->Id,
00180             Ivy_ObjFaninId0(pTemp), Ivy_ObjFaninC0(pTemp)? "\'" : "",
00181             Ivy_ObjFaninId1(pTemp), Ivy_ObjFaninC1(pTemp)? "\'" : "" );
00182 */
00183 
00184     RetValue = Ivy_MultiPlus( vLeaves, vCone, Ivy_ObjType(pObj), nMffc + fUseZeroCost, vSols );
00185 
00186     // ref nodes in the cone
00187     Vec_PtrForEachEntry( vCone, pTemp, k )
00188     {
00189         Ivy_ObjRefsInc( Ivy_ObjFanin0(pTemp) );
00190         Ivy_ObjRefsInc( Ivy_ObjFanin1(pTemp) );
00191         pTemp->fMarkA = 0;
00192         pTemp->fMarkB = 0;
00193     }
00194 
00195     if ( !RetValue )
00196         return NULL;
00197 
00198     if ( Vec_PtrSize( vSols ) == 1 )
00199         return Vec_PtrEntry( vSols, 0 );
00200     return Ivy_NodeBalanceBuildSuper( vSols, Ivy_ObjType(pObj), 1 );
00201 }

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