src/aig/ivy/ivyFastMap.c File Reference

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

Go to the source code of this file.

Data Structures

struct  Ivy_SuppMan_t_
struct  Ivy_Supp_t_

Defines

#define IVY_INFINITY   10000

Typedefs

typedef struct Ivy_SuppMan_t_ Ivy_SuppMan_t
typedef struct Ivy_Supp_t_ Ivy_Supp_t

Functions

static Ivy_Supp_t * Ivy_ObjSupp (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static Ivy_Supp_t * Ivy_ObjSuppStart (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static void Ivy_FastMapPrint (Ivy_Man_t *pAig, int Delay, int Area, int Time, char *pStr)
static int Ivy_FastMapDelay (Ivy_Man_t *pAig)
static int Ivy_FastMapArea (Ivy_Man_t *pAig)
static void Ivy_FastMapNode (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit)
static void Ivy_FastMapNodeArea (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit)
static int Ivy_FastMapMerge (Ivy_Supp_t *pSupp0, Ivy_Supp_t *pSupp1, Ivy_Supp_t *pSupp, int nLimit)
static void Ivy_FastMapRequired (Ivy_Man_t *pAig, int Delay, int fSetInter)
static void Ivy_FastMapRecover (Ivy_Man_t *pAig, int nLimit)
static int Ivy_FastMapNodeDelay (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static int Ivy_FastMapNodeAreaRefed (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static int Ivy_FastMapNodeAreaDerefed (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static void Ivy_FastMapNodeRecover (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld)
static int Ivy_FastMapNodeRef (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static int Ivy_FastMapNodeDeref (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
void Ivy_FastMapPerform (Ivy_Man_t *pAig, int nLimit, int fRecovery, int fVerbose)
void Ivy_FastMapStop (Ivy_Man_t *pAig)
int Ivy_FastMapArea_rec (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Vec_t *vLuts)
static Ivy_ObjIsNodeInt1 (Ivy_Obj_t *pObj)
static Ivy_ObjIsNodeInt2 (Ivy_Obj_t *pObj)
static void Vec_IntSelectSort (int *pArray, int nSize)
static int Vec_IntRemoveDup (int *pArray, int nSize)
void Ivy_FastMapNodeArea2 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit)
void Ivy_FastMapReadSupp (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Int_t *vLeaves)
void Ivy_FastMapRequired_rec (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Ivy_Obj_t *pRoot, int DelayR)
int Ivy_FastMapCutCost (Ivy_Man_t *pAig, Vec_Ptr_t *vFront)
void Ivy_FastMapMark_rec (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
int Ivy_FastMapNodeWillGrow (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
int Ivy_FastMapNodeFaninCost (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
void Ivy_FastMapNodeFaninUpdate (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Ptr_t *vFront)
int Ivy_FastMapNodeFaninCompact0 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
int Ivy_FastMapNodeFaninCompact1 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
int Ivy_FastMapNodeFaninCompact2 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
int Ivy_FastMapNodeFaninCompact_int (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
void Ivy_FastMapNodeFaninCompact (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
void Ivy_FastMapNodePrepare (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld)
void Ivy_FastMapNodeUpdate (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Ptr_t *vFront)
void Ivy_FastMapNodeRecover2 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld)
void Ivy_FastMapNodeRecover4 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld)

Variables

int s_MappingTime
int s_MappingMem

Define Documentation

#define IVY_INFINITY   10000

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

FileName [ivyFastMap.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [And-Inverter Graph package.]

Synopsis [Fast FPGA mapping.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

] DECLARATIONS ///

Definition at line 27 of file ivyFastMap.c.

Typedef Documentation

typedef struct Ivy_Supp_t_ Ivy_Supp_t

Definition at line 39 of file ivyFastMap.c.

typedef struct Ivy_SuppMan_t_ Ivy_SuppMan_t

Definition at line 29 of file ivyFastMap.c.

Function Documentation

int Ivy_FastMapArea ( Ivy_Man_t *  pAig  )  [static]

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

Synopsis [Computes area after mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 284 of file ivyFastMap.c.

00285 {
00286     Vec_Vec_t * vLuts;
00287     Ivy_Obj_t * pObj;
00288     int i, Counter = 0;
00289     // get the array to store the nodes
00290     vLuts = ((Ivy_SuppMan_t *)pAig->pData)->vLuts;
00291     Vec_VecClear( vLuts );
00292     // explore starting from each node
00293     Ivy_ManForEachPo( pAig, pObj, i )
00294         Counter += Ivy_FastMapArea_rec( pAig, Ivy_ObjFanin0(pObj), vLuts );
00295     // clean the marks
00296     Ivy_ManForEachNode( pAig, pObj, i )
00297         Ivy_ObjSupp( pAig, pObj )->fMark = 0;
00298     return Counter;
00299 }

int Ivy_FastMapArea_rec ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
Vec_Vec_t *  vLuts 
)

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

Synopsis [Computes area after mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 255 of file ivyFastMap.c.

00256 {
00257     Ivy_Supp_t * pSupp;
00258     int i, Counter;
00259     pSupp = Ivy_ObjSupp( pAig, pObj );
00260     // skip visited nodes and PIs
00261     if ( pSupp->fMark || pSupp->nSize == 1 )
00262         return 0;
00263     pSupp->fMark = 1;
00264     // compute the area of this node
00265     Counter = 0;
00266     for ( i = 0; i < pSupp->nSize; i++ )
00267         Counter += Ivy_FastMapArea_rec( pAig, Ivy_ManObj(pAig, pSupp->pArray[i]), vLuts );
00268     // add the node to the array of LUTs
00269     Vec_VecPush( vLuts, pSupp->Delay, pObj );
00270     return 1 + Counter;
00271 }

int Ivy_FastMapCutCost ( Ivy_Man_t *  pAig,
Vec_Ptr_t *  vFront 
)

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

Synopsis [Counts the number of nodes with no external fanout.]

Description []

SideEffects []

SeeAlso []

Definition at line 1115 of file ivyFastMap.c.

01116 {
01117     Ivy_Supp_t * pSuppF;
01118     Ivy_Obj_t * pFanin;
01119     int i, Counter = 0;
01120     Vec_PtrForEachEntry( vFront, pFanin, i )
01121     {
01122         pSuppF = Ivy_ObjSupp( pAig, pFanin );
01123         if ( pSuppF->nRefs == 0 )
01124             Counter++;
01125     }
01126     return Counter;
01127 }

int Ivy_FastMapDelay ( Ivy_Man_t *  pAig  )  [static]

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

Synopsis [Computes delay after LUT mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 227 of file ivyFastMap.c.

00228 {
00229     Ivy_Supp_t * pSupp;
00230     Ivy_Obj_t * pObj;
00231     int i, DelayMax = 0;
00232     Ivy_ManForEachPo( pAig, pObj, i )
00233     {
00234         pObj = Ivy_ObjFanin0(pObj);
00235         if ( !Ivy_ObjIsNode(pObj) )
00236             continue;
00237         pSupp = Ivy_ObjSupp( pAig, pObj );
00238         if ( DelayMax < pSupp->Delay )
00239             DelayMax = pSupp->Delay;
00240     }
00241     return DelayMax;
00242 }

void Ivy_FastMapMark_rec ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj 
)

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 1140 of file ivyFastMap.c.

01141 {
01142     if ( Ivy_ObjIsTravIdCurrent(pAig, pObj) )
01143         return;
01144     assert( Ivy_ObjIsNode(pObj) );
01145     Ivy_FastMapMark_rec( pAig, Ivy_ObjFanin0(pObj) );
01146     Ivy_FastMapMark_rec( pAig, Ivy_ObjFanin1(pObj) );
01147     Ivy_ObjSetTravIdCurrent(pAig, pObj);
01148 }

int Ivy_FastMapMerge ( Ivy_Supp_t *  pSupp0,
Ivy_Supp_t *  pSupp1,
Ivy_Supp_t *  pSupp,
int  nLimit 
) [static]

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

Synopsis [Merges two supports]

Description []

SideEffects []

SeeAlso []

Definition at line 729 of file ivyFastMap.c.

00730 { 
00731     int i, k, c;
00732     assert( pSupp0->nSize >= pSupp1->nSize );
00733     // the case of the largest cut sizes
00734     if ( pSupp0->nSize == nLimit && pSupp1->nSize == nLimit )
00735     {
00736         for ( i = 0; i < pSupp0->nSize; i++ )
00737             if ( pSupp0->pArray[i] != pSupp1->pArray[i] )
00738                 return 0;
00739         for ( i = 0; i < pSupp0->nSize; i++ )
00740             pSupp->pArray[i] = pSupp0->pArray[i];
00741         pSupp->nSize = pSupp0->nSize;
00742         return 1;
00743     }
00744     // the case when one of the cuts is the largest
00745     if ( pSupp0->nSize == nLimit )
00746     {
00747         for ( i = 0; i < pSupp1->nSize; i++ )
00748         {
00749             for ( k = pSupp0->nSize - 1; k >= 0; k-- )
00750                 if ( pSupp0->pArray[k] == pSupp1->pArray[i] )
00751                     break;
00752             if ( k == -1 ) // did not find
00753                 return 0;
00754         }
00755         for ( i = 0; i < pSupp0->nSize; i++ )
00756             pSupp->pArray[i] = pSupp0->pArray[i];
00757         pSupp->nSize = pSupp0->nSize;
00758         return 1;
00759     }
00760 
00761     // compare two cuts with different numbers
00762     i = k = 0;
00763     for ( c = 0; c < nLimit; c++ )
00764     {
00765         if ( k == pSupp1->nSize )
00766         {
00767             if ( i == pSupp0->nSize )
00768             {
00769                 pSupp->nSize = c;
00770                 return 1;
00771             }
00772             pSupp->pArray[c] = pSupp0->pArray[i++];
00773             continue;
00774         }
00775         if ( i == pSupp0->nSize )
00776         {
00777             if ( k == pSupp1->nSize )
00778             {
00779                 pSupp->nSize = c;
00780                 return 1;
00781             }
00782             pSupp->pArray[c] = pSupp1->pArray[k++];
00783             continue;
00784         }
00785         if ( pSupp0->pArray[i] < pSupp1->pArray[k] )
00786         {
00787             pSupp->pArray[c] = pSupp0->pArray[i++];
00788             continue;
00789         }
00790         if ( pSupp0->pArray[i] > pSupp1->pArray[k] )
00791         {
00792             pSupp->pArray[c] = pSupp1->pArray[k++];
00793             continue;
00794         }
00795         pSupp->pArray[c] = pSupp0->pArray[i++]; 
00796         k++;
00797     }
00798     if ( i < pSupp0->nSize || k < pSupp1->nSize )
00799         return 0;
00800     pSupp->nSize = c;
00801     return 1;
00802 }

void Ivy_FastMapNode ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit 
) [static]

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 563 of file ivyFastMap.c.

00564 {
00565     Ivy_Supp_t * pSupp0, * pSupp1, * pSupp;
00566     int fFaninParam = 2;
00567     int RetValue;
00568     assert( Ivy_ObjIsNode(pObj) );
00569     // get the supports
00570     pSupp0 = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) );
00571     pSupp1 = Ivy_ObjSupp( pAig, Ivy_ObjFanin1(pObj) );
00572     pSupp  = Ivy_ObjSupp( pAig, pObj );
00573     pSupp->fMark = 0;
00574     // get the delays
00575     if ( pSupp0->Delay == pSupp1->Delay )
00576         pSupp->Delay = (pSupp0->Delay == 0) ? pSupp0->Delay + 1: pSupp0->Delay;
00577     else if ( pSupp0->Delay > pSupp1->Delay )
00578     {
00579         pSupp->Delay = pSupp0->Delay;
00580         pSupp1 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
00581         pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj);
00582     }
00583     else // if ( pSupp0->Delay < pSupp1->Delay )
00584     {
00585         pSupp->Delay = pSupp1->Delay;
00586         pSupp0 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
00587         pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj);
00588     }
00589     // merge the cuts
00590     if ( pSupp0->nSize < pSupp1->nSize )
00591         RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
00592     else
00593         RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
00594     if ( !RetValue )
00595     {
00596         pSupp->Delay++;
00597         if ( fFaninParam == 2 )
00598         {
00599             pSupp->nSize = 2;
00600             pSupp->pArray[0] = Ivy_ObjFaninId0(pObj);
00601             pSupp->pArray[1] = Ivy_ObjFaninId1(pObj);
00602         }
00603         else if ( fFaninParam == 3 )
00604         {
00605             Ivy_Obj_t * pFanin0, * pFanin1, * pFaninA, * pFaninB;
00606             pFanin0 = Ivy_ObjFanin0(pObj);
00607             pFanin1 = Ivy_ObjFanin1(pObj);
00608             pSupp->nSize = 0;
00609             // process the first fanin
00610             if ( Ivy_ObjIsNodeInt1(pFanin0) )
00611             {
00612                 pFaninA = Ivy_ObjFanin0(pFanin0);
00613                 pFaninB = Ivy_ObjFanin1(pFanin0);
00614                 if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
00615                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFanin0);
00616                 else
00617                 {
00618                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninA);
00619                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninB);
00620                 }
00621             }
00622             else
00623                 pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFanin0);
00624             // process the second fanin
00625             if ( Ivy_ObjIsNodeInt1(pFanin1) )
00626             {
00627                 pFaninA = Ivy_ObjFanin0(pFanin1);
00628                 pFaninB = Ivy_ObjFanin1(pFanin1);
00629                 if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
00630                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFanin1);
00631                 else
00632                 {
00633                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninA);
00634                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninB);
00635                 }
00636             }
00637             else
00638                 pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFanin1);
00639             // sort the fanins
00640             Vec_IntSelectSort( pSupp->pArray, pSupp->nSize );
00641             pSupp->nSize = Vec_IntRemoveDup( pSupp->pArray, pSupp->nSize );
00642             assert( pSupp->pArray[0] < pSupp->pArray[1] );
00643         }
00644         else if ( fFaninParam == 4 )
00645         {
00646             Ivy_Obj_t * pFanin0, * pFanin1, * pFaninA, * pFaninB;
00647             pFanin0 = Ivy_ObjFanin0(pObj);
00648             pFanin1 = Ivy_ObjFanin1(pObj);
00649             pSupp->nSize = 0;
00650             // consider the case when exactly one of them is internal
00651             if ( Ivy_ObjIsNodeInt1(pFanin0) ^ Ivy_ObjIsNodeInt1(pFanin1) )
00652             {
00653                 pSupp0 = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) );
00654                 pSupp1 = Ivy_ObjSupp( pAig, Ivy_ObjFanin1(pObj) );
00655                 if ( Ivy_ObjIsNodeInt1(pFanin0) && pSupp0->nSize < nLimit )
00656                 {
00657                     pSupp->Delay = IVY_MAX( pSupp0->Delay, pSupp1->Delay + 1 );
00658                     pSupp1 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
00659                     pSupp1->pArray[0] = Ivy_ObjId(pFanin1);
00660                     // merge the cuts
00661                     RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
00662                     assert( RetValue );
00663                     assert( pSupp->nSize > 1 );
00664                     return;
00665                 }
00666                 if ( Ivy_ObjIsNodeInt1(pFanin1) && pSupp1->nSize < nLimit )
00667                 {
00668                     pSupp->Delay = IVY_MAX( pSupp1->Delay, pSupp0->Delay + 1 );
00669                     pSupp0 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
00670                     pSupp0->pArray[0] = Ivy_ObjId(pFanin0);
00671                     // merge the cuts
00672                     RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
00673                     assert( RetValue );
00674                     assert( pSupp->nSize > 1 );
00675                     return;
00676                 }
00677             }
00678             // process the first fanin
00679             if ( Ivy_ObjIsNodeInt1(pFanin0) )
00680             {
00681                 pFaninA = Ivy_ObjFanin0(pFanin0);
00682                 pFaninB = Ivy_ObjFanin1(pFanin0);
00683                 if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
00684                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFanin0);
00685                 else
00686                 {
00687                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninA);
00688                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninB);
00689                 }
00690             }
00691             else
00692                 pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFanin0);
00693             // process the second fanin
00694             if ( Ivy_ObjIsNodeInt1(pFanin1) )
00695             {
00696                 pFaninA = Ivy_ObjFanin0(pFanin1);
00697                 pFaninB = Ivy_ObjFanin1(pFanin1);
00698                 if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
00699                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFanin1);
00700                 else
00701                 {
00702                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninA);
00703                     pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFaninB);
00704                 }
00705             }
00706             else
00707                 pSupp->pArray[pSupp->nSize++] = Ivy_ObjId(pFanin1);
00708             // sort the fanins
00709             Vec_IntSelectSort( pSupp->pArray, pSupp->nSize );
00710             pSupp->nSize = Vec_IntRemoveDup( pSupp->pArray, pSupp->nSize );
00711             assert( pSupp->pArray[0] < pSupp->pArray[1] );
00712             assert( pSupp->nSize > 1 );
00713         }
00714     }
00715     assert( pSupp->Delay > 0 );
00716 }

void Ivy_FastMapNodeArea ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit 
) [static]

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 463 of file ivyFastMap.c.

00464 {
00465     static int Store[32], StoreSize;
00466     static char Supp0[16], Supp1[16];
00467     static Ivy_Supp_t * pTemp0 = (Ivy_Supp_t *)Supp0;
00468     static Ivy_Supp_t * pTemp1 = (Ivy_Supp_t *)Supp1;
00469     Ivy_Obj_t * pFanin0, * pFanin1;
00470     Ivy_Supp_t * pSupp0, * pSupp1, * pSupp;
00471     int RetValue, DelayOld, RefsOld;
00472     int AreaBef, AreaAft;
00473     assert( nLimit <= 32 );
00474     assert( Ivy_ObjIsNode(pObj) );
00475     // get the fanins
00476     pFanin0 = Ivy_ObjFanin0(pObj);
00477     pFanin1 = Ivy_ObjFanin1(pObj);
00478     // get the supports
00479     pSupp0 = Ivy_ObjSupp( pAig, pFanin0 );
00480     pSupp1 = Ivy_ObjSupp( pAig, pFanin1 );
00481     pSupp  = Ivy_ObjSupp( pAig, pObj );
00482     assert( pSupp->fMark == 0 );
00483 
00484     // get the area
00485     if ( pSupp->nRefs == 0 )
00486         AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
00487     else
00488         AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
00489 //    if ( AreaBef == 1 )
00490 //        return;
00491 
00492     // deref the cut if the node is refed
00493     if ( pSupp->nRefs != 0 )
00494         Ivy_FastMapNodeDeref( pAig, pObj );
00495 
00496     // get the old delay of the node
00497     DelayOld = Ivy_FastMapNodeDelay(pAig, pObj);
00498     assert( DelayOld <= pSupp->DelayR );
00499     // copy the current cut
00500     memcpy( Store, pSupp->pArray, sizeof(int) * pSupp->nSize );
00501     StoreSize = pSupp->nSize;
00502     // get the fanin support
00503     if ( Ivy_ObjRefs(pFanin0) > 2 && pSupp0->Delay < pSupp->DelayR )
00504 //    if ( pSupp0->nRefs > 0 && pSupp0->Delay < pSupp->DelayR ) // this leads to 2% worse results
00505     {
00506         pSupp0 = pTemp0;
00507         pSupp0->nSize = 1;
00508         pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj);
00509     }
00510     // get the fanin support
00511     if ( Ivy_ObjRefs(pFanin1) > 2 && pSupp1->Delay < pSupp->DelayR )
00512 //    if ( pSupp1->nRefs > 0 && pSupp1->Delay < pSupp->DelayR )
00513     {
00514         pSupp1 = pTemp1;
00515         pSupp1->nSize = 1;
00516         pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj);
00517     }
00518     // merge the cuts
00519     if ( pSupp0->nSize < pSupp1->nSize )
00520         RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
00521     else
00522         RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
00523     if ( !RetValue )
00524     {
00525         pSupp->nSize = 2;
00526         pSupp->pArray[0] = Ivy_ObjFaninId0(pObj);
00527         pSupp->pArray[1] = Ivy_ObjFaninId1(pObj);
00528     }
00529 
00530     // check the resulting delay
00531     pSupp->Delay = Ivy_FastMapNodeDelay(pAig, pObj);
00532 
00533     RefsOld = pSupp->nRefs; pSupp->nRefs = 0;
00534     AreaAft = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
00535     pSupp->nRefs = RefsOld;
00536 
00537     if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR )
00538 //    if ( pSupp->Delay > pSupp->DelayR )
00539     {
00540         pSupp->nSize = StoreSize;
00541         memcpy( pSupp->pArray, Store, sizeof(int) * pSupp->nSize );
00542         pSupp->Delay = DelayOld;
00543 //        printf( "-" );
00544     }
00545 //    else
00546 //        printf( "+" );
00547 
00548     if ( pSupp->nRefs != 0 )
00549         Ivy_FastMapNodeRef( pAig, pObj );
00550 }

void Ivy_FastMapNodeArea2 ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit 
)

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 392 of file ivyFastMap.c.

00393 {
00394     static int Store[32], StoreSize;
00395     static char Supp0[16], Supp1[16];
00396     static Ivy_Supp_t * pTemp0 = (Ivy_Supp_t *)Supp0;
00397     static Ivy_Supp_t * pTemp1 = (Ivy_Supp_t *)Supp1;
00398     Ivy_Obj_t * pFanin0, * pFanin1;
00399     Ivy_Supp_t * pSupp0, * pSupp1, * pSupp;
00400     int RetValue, DelayOld;
00401     assert( nLimit <= 32 );
00402     assert( Ivy_ObjIsNode(pObj) );
00403     // get the fanins
00404     pFanin0 = Ivy_ObjFanin0(pObj);
00405     pFanin1 = Ivy_ObjFanin1(pObj);
00406     // get the supports
00407     pSupp0 = Ivy_ObjSupp( pAig, pFanin0 );
00408     pSupp1 = Ivy_ObjSupp( pAig, pFanin1 );
00409     pSupp  = Ivy_ObjSupp( pAig, pObj );
00410     assert( pSupp->fMark == 0 );
00411     // get the old delay of the node
00412     DelayOld = Ivy_FastMapNodeDelay(pAig, pObj);
00413     assert( DelayOld <= pSupp->DelayR );
00414     // copy the current cut
00415     memcpy( Store, pSupp->pArray, sizeof(int) * pSupp->nSize );
00416     StoreSize = pSupp->nSize;
00417     // get the fanin support
00418     if ( Ivy_ObjRefs(pFanin0) > 1 && pSupp0->Delay < pSupp->DelayR )
00419     {
00420         pSupp0 = pTemp0;
00421         pSupp0->nSize = 1;
00422         pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj);
00423     }
00424     // get the fanin support
00425     if ( Ivy_ObjRefs(pFanin1) > 1 && pSupp1->Delay < pSupp->DelayR )
00426     {
00427         pSupp1 = pTemp1;
00428         pSupp1->nSize = 1;
00429         pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj);
00430     }
00431     // merge the cuts
00432     if ( pSupp0->nSize < pSupp1->nSize )
00433         RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
00434     else
00435         RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
00436     if ( !RetValue )
00437     {
00438         pSupp->nSize = 2;
00439         pSupp->pArray[0] = Ivy_ObjFaninId0(pObj);
00440         pSupp->pArray[1] = Ivy_ObjFaninId1(pObj);
00441     }
00442     // check the resulting delay
00443     pSupp->Delay = Ivy_FastMapNodeDelay(pAig, pObj);
00444     if ( pSupp->Delay > pSupp->DelayR )
00445     {
00446         pSupp->nSize = StoreSize;
00447         memcpy( pSupp->pArray, Store, sizeof(int) * pSupp->nSize );
00448         pSupp->Delay = DelayOld;
00449     }
00450 }

int Ivy_FastMapNodeAreaDerefed ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj 
) [static]

function*************************************************************

synopsis [Computes the exact area associated with the cut.]

description []

sideeffects []

seealso []

Definition at line 1086 of file ivyFastMap.c.

01087 {
01088     Ivy_Supp_t * pSupp;
01089     int aResult, aResult2;
01090     if ( Ivy_ObjIsCi(pObj) )
01091         return 0;
01092     assert( Ivy_ObjIsNode(pObj) );
01093     pSupp = Ivy_ObjSupp( pAig, pObj );
01094     assert( pSupp->nRefs == 0 );
01095     aResult2 = Ivy_FastMapNodeRef( pAig, pObj );
01096     aResult  = Ivy_FastMapNodeDeref( pAig, pObj );
01097     assert( aResult == aResult2 );
01098     return aResult;
01099 }

int Ivy_FastMapNodeAreaRefed ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj 
) [static]

function*************************************************************

synopsis [Computes the exact area associated with the cut.]

description []

sideeffects []

seealso []

Definition at line 1060 of file ivyFastMap.c.

01061 {
01062     Ivy_Supp_t * pSupp;
01063     int aResult, aResult2;
01064     if ( Ivy_ObjIsCi(pObj) )
01065         return 0;
01066     assert( Ivy_ObjIsNode(pObj) );
01067     pSupp = Ivy_ObjSupp( pAig, pObj );
01068     assert( pSupp->nRefs > 0 );
01069     aResult  = Ivy_FastMapNodeDeref( pAig, pObj );
01070     aResult2 = Ivy_FastMapNodeRef( pAig, pObj );
01071     assert( aResult == aResult2 );
01072     return aResult;
01073 }

int Ivy_FastMapNodeDelay ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj 
) [static]

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

Synopsis [Computes the delay of the cut rooted at this node.]

Description []

SideEffects []

SeeAlso []

Definition at line 965 of file ivyFastMap.c.

00966 {
00967     Ivy_Supp_t * pSupp, * pSuppF;
00968     int c, Delay = 0;
00969     pSupp = Ivy_ObjSupp( pAig, pObj );
00970     for ( c = 0; c < pSupp->nSize; c++ )
00971     {
00972         pSuppF = Ivy_ObjSupp( pAig, Ivy_ManObj(pAig, pSupp->pArray[c]) );
00973         Delay = IVY_MAX( Delay, pSuppF->Delay );
00974     }
00975     return 1 + Delay;
00976 }

int Ivy_FastMapNodeDeref ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj 
) [static]

function*************************************************************

synopsis [Dereferences the cut.]

description [This procedure is similar to the procedure NodeRecusiveDeref.]

sideeffects []

seealso []

Definition at line 1025 of file ivyFastMap.c.

01026 {
01027     Ivy_Supp_t * pSupp, * pSuppF;
01028     Ivy_Obj_t * pNodeChild;
01029     int aArea, i;
01030     // start the area of this cut
01031     aArea = 1;
01032     // go through the children
01033     pSupp = Ivy_ObjSupp( pAig, pObj );
01034     assert( pSupp->nSize > 1 );
01035     for ( i = 0; i < pSupp->nSize; i++ )
01036     {
01037         pNodeChild = Ivy_ManObj(pAig, pSupp->pArray[i]);
01038         pSuppF = Ivy_ObjSupp( pAig, pNodeChild );
01039         assert( pSuppF->nRefs > 0 );
01040         if ( --pSuppF->nRefs > 0 )  
01041             continue;
01042         if ( pSuppF->nSize == 1 ) 
01043             continue;
01044         aArea += Ivy_FastMapNodeDeref( pAig, pNodeChild );
01045     }
01046     return aArea;
01047 }

void Ivy_FastMapNodeFaninCompact ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront 
)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1354 of file ivyFastMap.c.

01355 {
01356     while ( Ivy_FastMapNodeFaninCompact_int( pAig, pObj, nLimit, vFront ) );
01357 }

int Ivy_FastMapNodeFaninCompact0 ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront 
)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1245 of file ivyFastMap.c.

01246 {
01247     Ivy_Obj_t * pFanin;
01248     int i;
01249     Vec_PtrForEachEntry( vFront, pFanin, i )
01250     {
01251         if ( Ivy_ObjIsCi(pFanin) )
01252             continue;
01253         if ( Ivy_FastMapNodeWillGrow(pAig, pFanin) )
01254             continue;
01255         if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) <= 0 )
01256         {
01257             Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront );
01258             return 1;
01259         }
01260     }
01261     return 0;
01262 }

int Ivy_FastMapNodeFaninCompact1 ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront 
)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1275 of file ivyFastMap.c.

01276 {
01277     Ivy_Obj_t * pFanin;
01278     int i;
01279     Vec_PtrForEachEntry( vFront, pFanin, i )
01280     {
01281         if ( Ivy_ObjIsCi(pFanin) )
01282             continue;
01283         if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) < 0 )
01284         {
01285             Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront );
01286             return 1;
01287         }
01288     }
01289     return 0;
01290 }

int Ivy_FastMapNodeFaninCompact2 ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront 
)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1303 of file ivyFastMap.c.

01304 {
01305     Ivy_Obj_t * pFanin;
01306     int i;
01307     Vec_PtrForEachEntry( vFront, pFanin, i )
01308     {
01309         if ( Ivy_ObjIsCi(pFanin) )
01310             continue;
01311         if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) <= 0 )
01312         {
01313             Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront );
01314             return 1;
01315         }
01316     }
01317     return 0;
01318 }

int Ivy_FastMapNodeFaninCompact_int ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront 
)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1331 of file ivyFastMap.c.

01332 {
01333     if ( Ivy_FastMapNodeFaninCompact0(pAig, pObj, nLimit, vFront) )
01334         return 1;
01335     if (  Vec_PtrSize(vFront) < nLimit && Ivy_FastMapNodeFaninCompact1(pAig, pObj, nLimit, vFront) )
01336         return 1;
01337     if ( Vec_PtrSize(vFront) < nLimit && Ivy_FastMapNodeFaninCompact2(pAig, pObj, nLimit, vFront) )
01338         return 1;
01339     assert( Vec_PtrSize(vFront) <= nLimit );
01340     return 0;
01341 }

int Ivy_FastMapNodeFaninCost ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj 
)

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

Synopsis [Returns the increase in the number of fanins with no external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1181 of file ivyFastMap.c.

01182 {
01183     Ivy_Supp_t * pSuppF;
01184     Ivy_Obj_t * pFanin;
01185     int Counter = 0;
01186     assert( Ivy_ObjIsNode(pObj) );
01187     // check if the node has external refs
01188     pSuppF = Ivy_ObjSupp( pAig, pObj );
01189     if ( pSuppF->nRefs == 0 )
01190         Counter--;
01191     // increment the number of fanins without external refs
01192     pFanin = Ivy_ObjFanin0(pObj);
01193     pSuppF = Ivy_ObjSupp( pAig, pFanin );
01194     if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) && pSuppF->nRefs == 0 )
01195         Counter++;
01196     // increment the number of fanins without external refs
01197     pFanin = Ivy_ObjFanin1(pObj);
01198     pSuppF = Ivy_ObjSupp( pAig, pFanin );
01199     if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) && pSuppF->nRefs == 0 )
01200         Counter++;
01201     return Counter;
01202 }

void Ivy_FastMapNodeFaninUpdate ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
Vec_Ptr_t *  vFront 
)

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

Synopsis [Updates the frontier.]

Description []

SideEffects []

SeeAlso []

Definition at line 1215 of file ivyFastMap.c.

01216 {
01217     Ivy_Obj_t * pFanin;
01218     assert( Ivy_ObjIsNode(pObj) );
01219     Vec_PtrRemove( vFront, pObj );
01220     pFanin = Ivy_ObjFanin0(pObj);
01221     if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) )
01222     {
01223         Ivy_ObjSetTravIdCurrent(pAig, pFanin);
01224         Vec_PtrPush( vFront, pFanin );
01225     }
01226     pFanin = Ivy_ObjFanin1(pObj);
01227     if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) )
01228     {
01229         Ivy_ObjSetTravIdCurrent(pAig, pFanin);
01230         Vec_PtrPush( vFront, pFanin );
01231     }
01232 }

void Ivy_FastMapNodePrepare ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vFrontOld 
)

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

Synopsis [Prepares node mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 1370 of file ivyFastMap.c.

01371 {
01372     Ivy_Supp_t * pSupp;
01373     Ivy_Obj_t * pFanin;
01374     int i;
01375     pSupp = Ivy_ObjSupp( pAig, pObj );
01376     // expand the cut downwards from the given place
01377     Vec_PtrClear( vFront );
01378     Vec_PtrClear( vFrontOld );
01379     Ivy_ManIncrementTravId( pAig );
01380     for ( i = 0; i < pSupp->nSize; i++ )
01381     {
01382         pFanin = Ivy_ManObj(pAig, pSupp->pArray[i]);
01383         Vec_PtrPush( vFront, pFanin );
01384         Vec_PtrPush( vFrontOld, pFanin );
01385         Ivy_ObjSetTravIdCurrent( pAig, pFanin );
01386     }
01387     // mark the nodes in the cone
01388     Ivy_FastMapMark_rec( pAig, pObj );
01389 }

void Ivy_FastMapNodeRecover ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vFrontOld 
) [static]

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 1485 of file ivyFastMap.c.

01486 {
01487     Ivy_Supp_t * pSupp;
01488     int CostBef, CostAft;
01489     int AreaBef, AreaAft;
01490     int DelayOld;
01491     pSupp = Ivy_ObjSupp( pAig, pObj );
01492     DelayOld = pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
01493     assert( pSupp->Delay <= pSupp->DelayR );
01494     if ( pSupp->nRefs == 0 )
01495         return;
01496     // get the area
01497     AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
01498 //    if ( AreaBef == 1 )
01499 //        return;
01500     if ( pObj->Id == 102 )
01501     {
01502         int x = 0;
01503     }
01504     // the cut is non-trivial
01505     Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld );
01506     // iteratively modify the cut
01507     Ivy_FastMapNodeDeref( pAig, pObj );
01508     CostBef = Ivy_FastMapCutCost( pAig, vFront );
01509     Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront );
01510     CostAft = Ivy_FastMapCutCost( pAig, vFront );
01511     Ivy_FastMapNodeRef( pAig, pObj );
01512     assert( CostBef >= CostAft );
01513     // update the node
01514     Ivy_FastMapNodeUpdate( pAig, pObj, vFront );
01515     pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
01516     // get the new area
01517     AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
01518     if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR )
01519     {
01520         Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld );
01521         AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
01522         assert( AreaAft == AreaBef );
01523         pSupp->Delay = DelayOld;
01524     }
01525 }

void Ivy_FastMapNodeRecover2 ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vFrontOld 
)

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 1429 of file ivyFastMap.c.

01430 {
01431     Ivy_Supp_t * pSupp;
01432     int CostBef, CostAft;
01433     int AreaBef, AreaAft;
01434     pSupp = Ivy_ObjSupp( pAig, pObj );
01435 //    if ( pSupp->nRefs == 0 )
01436 //        return;
01437     if ( pSupp->nRefs == 0 )
01438         AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
01439     else
01440         AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
01441     // get the area
01442     if ( AreaBef == 1 )
01443         return;
01444 
01445     if ( pSupp->nRefs == 0 )
01446     {
01447         pSupp->nRefs = 1000000;
01448         Ivy_FastMapNodeRef( pAig, pObj );
01449     }
01450     // the cut is non-trivial
01451     Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld );
01452     // iteratively modify the cut
01453     CostBef = Ivy_FastMapCutCost( pAig, vFront );
01454     Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront );
01455     CostAft = Ivy_FastMapCutCost( pAig, vFront );
01456     assert( CostBef >= CostAft );
01457     // update the node
01458     Ivy_FastMapNodeUpdate( pAig, pObj, vFront );
01459     // get the new area
01460     AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
01461     if ( AreaAft > AreaBef )
01462     {
01463         Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld );
01464         AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
01465         assert( AreaAft == AreaBef );
01466     }
01467     if ( pSupp->nRefs == 1000000 )
01468     {
01469         pSupp->nRefs = 0;
01470         Ivy_FastMapNodeDeref( pAig, pObj );
01471     }
01472 }

void Ivy_FastMapNodeRecover4 ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vFrontOld 
)

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 1538 of file ivyFastMap.c.

01539 {
01540     Ivy_Supp_t * pSupp;
01541     int CostBef, CostAft;
01542     int AreaBef, AreaAft;
01543     int DelayOld;
01544     pSupp = Ivy_ObjSupp( pAig, pObj );
01545     DelayOld = pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
01546     assert( pSupp->Delay <= pSupp->DelayR );
01547 //    if ( pSupp->nRefs == 0 )
01548 //        return;
01549 //    AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
01550     // get the area
01551     if ( pSupp->nRefs == 0 )
01552         AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
01553     else
01554         AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
01555     if ( AreaBef == 1 )
01556         return;
01557 
01558     if ( pSupp->nRefs == 0 )
01559     {
01560         pSupp->nRefs = 1000000;
01561         Ivy_FastMapNodeRef( pAig, pObj );
01562     }
01563     // the cut is non-trivial
01564     Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld );
01565     // iteratively modify the cut
01566     CostBef = Ivy_FastMapCutCost( pAig, vFront );
01567     Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront );
01568     CostAft = Ivy_FastMapCutCost( pAig, vFront );
01569     assert( CostBef >= CostAft );
01570     // update the node
01571     Ivy_FastMapNodeUpdate( pAig, pObj, vFront );
01572     pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
01573     // get the new area
01574     AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
01575     if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR )
01576     {
01577         Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld );
01578         AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
01579         assert( AreaAft == AreaBef );
01580         pSupp->Delay = DelayOld;
01581     }
01582     if ( pSupp->nRefs == 1000000 )
01583     {
01584         pSupp->nRefs = 0;
01585         Ivy_FastMapNodeDeref( pAig, pObj );
01586     }
01587 }

int Ivy_FastMapNodeRef ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj 
) [static]

function*************************************************************

synopsis [References the cut.]

description [This procedure is similar to the procedure NodeReclaim.]

sideeffects []

seealso []

Definition at line 990 of file ivyFastMap.c.

00991 {
00992     Ivy_Supp_t * pSupp, * pSuppF;
00993     Ivy_Obj_t * pNodeChild;
00994     int aArea, i;
00995     // start the area of this cut
00996     aArea = 1;
00997     // go through the children
00998     pSupp = Ivy_ObjSupp( pAig, pObj );
00999     assert( pSupp->nSize > 1 );
01000     for ( i = 0; i < pSupp->nSize; i++ )
01001     {
01002         pNodeChild = Ivy_ManObj(pAig, pSupp->pArray[i]);
01003         pSuppF = Ivy_ObjSupp( pAig, pNodeChild );
01004         assert( pSuppF->nRefs >= 0 );
01005         if ( pSuppF->nRefs++ > 0 )  
01006             continue;
01007         if ( pSuppF->nSize == 1 ) 
01008             continue;
01009         aArea += Ivy_FastMapNodeRef( pAig, pNodeChild );
01010     }
01011     return aArea;
01012 }

void Ivy_FastMapNodeUpdate ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
Vec_Ptr_t *  vFront 
)

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

Synopsis [Updates the frontier.]

Description []

SideEffects []

SeeAlso []

Definition at line 1402 of file ivyFastMap.c.

01403 {
01404     Ivy_Supp_t * pSupp;
01405     Ivy_Obj_t * pFanin;
01406     int i;
01407     pSupp = Ivy_ObjSupp( pAig, pObj );
01408     // deref node's cut
01409     Ivy_FastMapNodeDeref( pAig, pObj );
01410     // update the node's cut
01411     pSupp->nSize = Vec_PtrSize(vFront);
01412     Vec_PtrForEachEntry( vFront, pFanin, i )
01413         pSupp->pArray[i] = pFanin->Id;
01414     // ref the new cut
01415     Ivy_FastMapNodeRef( pAig, pObj );
01416 }

int Ivy_FastMapNodeWillGrow ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj 
)

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

Synopsis [Returns 1 if the number of fanins will grow.]

Description []

SideEffects []

SeeAlso []

Definition at line 1161 of file ivyFastMap.c.

01162 {
01163     Ivy_Obj_t * pFanin0, * pFanin1;
01164     assert( Ivy_ObjIsNode(pObj) );
01165     pFanin0 = Ivy_ObjFanin0(pObj);
01166     pFanin1 = Ivy_ObjFanin1(pObj);
01167     return !Ivy_ObjIsTravIdCurrent(pAig, pFanin0) && !Ivy_ObjIsTravIdCurrent(pAig, pFanin1);
01168 }

void Ivy_FastMapPerform ( Ivy_Man_t *  pAig,
int  nLimit,
int  fRecovery,
int  fVerbose 
)

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

Synopsis [Performs fast K-LUT mapping of the AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 102 of file ivyFastMap.c.

00103 {
00104     Ivy_SuppMan_t * pMan;
00105     Ivy_Obj_t * pObj;
00106     int i, Delay, Area, clk, clkTotal = clock();
00107     // start the memory for supports
00108     pMan = ALLOC( Ivy_SuppMan_t, 1 );
00109     memset( pMan, 0, sizeof(Ivy_SuppMan_t) );
00110     pMan->nLimit = nLimit;
00111     pMan->nObjs  = Ivy_ManObjIdMax(pAig) + 1;
00112     pMan->nSize  = sizeof(Ivy_Supp_t) + nLimit * sizeof(int);
00113     pMan->pMem   = (char *)malloc( pMan->nObjs * pMan->nSize );
00114     memset( pMan->pMem, 0, pMan->nObjs * pMan->nSize );
00115     pMan->vLuts  = Vec_VecAlloc( 100 );
00116     pAig->pData  = pMan;
00117 clk = clock();
00118     // set the PI mapping
00119     Ivy_ObjSuppStart( pAig, Ivy_ManConst1(pAig) );
00120     Ivy_ManForEachPi( pAig, pObj, i )
00121         Ivy_ObjSuppStart( pAig, pObj );
00122     // iterate through all nodes in the topological order
00123     Ivy_ManForEachNode( pAig, pObj, i )
00124         Ivy_FastMapNode( pAig, pObj, nLimit );
00125     // find the best arrival time and area
00126     Delay = Ivy_FastMapDelay( pAig );
00127     Area = Ivy_FastMapArea(pAig);
00128     if ( fVerbose )
00129         Ivy_FastMapPrint( pAig, Delay, Area, clock() - clk, "Delay oriented mapping: " );
00130 
00131 // 2-1-2 (doing 2-1-2-1-2 improves 0.5%)
00132 
00133     if ( fRecovery )
00134     {
00135 clk = clock();
00136     Ivy_FastMapRequired( pAig, Delay, 0 );
00137     // remap the nodes
00138     Ivy_FastMapRecover( pAig, nLimit );
00139     Delay = Ivy_FastMapDelay( pAig );
00140     Area = Ivy_FastMapArea(pAig);
00141     if ( fVerbose )
00142         Ivy_FastMapPrint( pAig, Delay, Area, clock() - clk, "Area recovery 2       : " );
00143 
00144 clk = clock();
00145     Ivy_FastMapRequired( pAig, Delay, 0 );
00146     // iterate through all nodes in the topological order
00147     Ivy_ManForEachNode( pAig, pObj, i )
00148         Ivy_FastMapNodeArea( pAig, pObj, nLimit );
00149     Delay = Ivy_FastMapDelay( pAig );
00150     Area = Ivy_FastMapArea(pAig);
00151     if ( fVerbose )
00152         Ivy_FastMapPrint( pAig, Delay, Area, clock() - clk, "Area recovery 1       : " );
00153 
00154 clk = clock();
00155     Ivy_FastMapRequired( pAig, Delay, 0 );
00156     // remap the nodes
00157     Ivy_FastMapRecover( pAig, nLimit );
00158     Delay = Ivy_FastMapDelay( pAig );
00159     Area = Ivy_FastMapArea(pAig);
00160     if ( fVerbose )
00161         Ivy_FastMapPrint( pAig, Delay, Area, clock() - clk, "Area recovery 2       : " );
00162     }
00163 
00164 
00165     s_MappingTime = clock() - clkTotal;
00166     s_MappingMem = pMan->nObjs * pMan->nSize;
00167 /*
00168     {
00169         Vec_Ptr_t * vNodes;
00170         vNodes = Vec_PtrAlloc( 100 );
00171         Vec_VecForEachEntry( pMan->vLuts, pObj, i, k )
00172             Vec_PtrPush( vNodes, pObj );
00173         Ivy_ManShow( pAig, 0, vNodes );
00174         Vec_PtrFree( vNodes );
00175     }
00176 */
00177 }

void Ivy_FastMapPrint ( Ivy_Man_t *  pAig,
int  Delay,
int  Area,
int  Time,
char *  pStr 
) [static]

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

Synopsis [Prints statistics.]

Description []

SideEffects []

SeeAlso []

Definition at line 210 of file ivyFastMap.c.

00211 {
00212     printf( "%s : Delay = %3d. Area = %6d. ", pStr, Delay, Area );
00213     PRT( "Time", Time );
00214 }

void Ivy_FastMapReadSupp ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
Vec_Int_t *  vLeaves 
)

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

Synopsis [Creates integer vector with the support of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 815 of file ivyFastMap.c.

00816 {
00817     Ivy_Supp_t * pSupp;
00818     pSupp = Ivy_ObjSupp( pAig, pObj );
00819     vLeaves->nCap   = 8;
00820     vLeaves->nSize  = pSupp->nSize;
00821     vLeaves->pArray = pSupp->pArray;
00822 }

void Ivy_FastMapRecover ( Ivy_Man_t *  pAig,
int  nLimit 
) [static]

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 939 of file ivyFastMap.c.

00940 {
00941     Vec_Ptr_t * vFront, * vFrontOld;
00942     Ivy_Obj_t * pObj;
00943     int i;
00944     vFront = Vec_PtrAlloc( nLimit );
00945     vFrontOld = Vec_PtrAlloc( nLimit );
00946     Ivy_ManCleanTravId( pAig );
00947     // iterate through all nodes in the topological order
00948     Ivy_ManForEachNode( pAig, pObj, i )
00949         Ivy_FastMapNodeRecover( pAig, pObj, nLimit, vFront, vFrontOld );
00950     Vec_PtrFree( vFrontOld );
00951     Vec_PtrFree( vFront );
00952 }

void Ivy_FastMapRequired ( Ivy_Man_t *  pAig,
int  Delay,
int  fSetInter 
) [static]

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

Synopsis [Computes the required times for each node.]

Description [Sets reference counters for each node.]

SideEffects []

SeeAlso []

Definition at line 858 of file ivyFastMap.c.

00859 {
00860     Vec_Vec_t * vLuts;
00861     Vec_Ptr_t * vNodes;
00862     Ivy_Obj_t * pObj;
00863     Ivy_Supp_t * pSupp, * pSuppF;
00864     int i, k, c;
00865     // clean the required times
00866     Ivy_ManForEachPi( pAig, pObj, i )
00867     {
00868         pSupp = Ivy_ObjSupp( pAig, pObj );
00869         pSupp->DelayR = IVY_INFINITY;
00870         pSupp->nRefs = 0;
00871     }
00872     Ivy_ManForEachNode( pAig, pObj, i )
00873     {
00874         pSupp = Ivy_ObjSupp( pAig, pObj );
00875         pSupp->DelayR = IVY_INFINITY;
00876         pSupp->nRefs = 0;
00877     }
00878     // set the required times of the POs
00879     Ivy_ManForEachPo( pAig, pObj, i )
00880     {
00881         pSupp = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) );
00882         pSupp->DelayR = Delay;
00883         pSupp->nRefs++;
00884     }
00885     // get the levelized nodes used in the mapping
00886     vLuts = ((Ivy_SuppMan_t *)pAig->pData)->vLuts;
00887     // propagate the required times
00888     Vec_VecForEachLevelReverse( vLuts, vNodes, i )
00889     Vec_PtrForEachEntry( vNodes, pObj, k )
00890     {
00891         pSupp = Ivy_ObjSupp( pAig, pObj );
00892         assert( pSupp->nRefs > 0 );
00893         for ( c = 0; c < pSupp->nSize; c++ )
00894         {
00895             pSuppF = Ivy_ObjSupp( pAig, Ivy_ManObj(pAig, pSupp->pArray[c]) );
00896             pSuppF->DelayR = IVY_MIN( pSuppF->DelayR, pSupp->DelayR - 1 );
00897             pSuppF->nRefs++;
00898         }
00899     }
00900 /*
00901     // print out some of the required times
00902     Ivy_ManForEachPi( pAig, pObj, i )
00903     {
00904         pSupp = Ivy_ObjSupp( pAig, pObj );
00905         printf( "%d ", pSupp->DelayR );
00906     }
00907     printf( "\n" );    
00908 */
00909 
00910     if ( fSetInter )
00911     {
00912         // set the required times of the intermediate nodes
00913         Vec_VecForEachLevelReverse( vLuts, vNodes, i )
00914         Vec_PtrForEachEntry( vNodes, pObj, k )
00915         {
00916             pSupp = Ivy_ObjSupp( pAig, pObj );
00917             Ivy_FastMapRequired_rec( pAig, pObj, pObj, pSupp->DelayR ); 
00918         }
00919         // make sure that all required times are assigned
00920         Ivy_ManForEachNode( pAig, pObj, i )
00921         {
00922             pSupp = Ivy_ObjSupp( pAig, pObj );
00923             assert( pSupp->DelayR < IVY_INFINITY );
00924         }
00925     }
00926 }

void Ivy_FastMapRequired_rec ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj,
Ivy_Obj_t *  pRoot,
int  DelayR 
)

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

Synopsis [Sets the required times of the intermediate nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 835 of file ivyFastMap.c.

00836 {
00837     Ivy_Supp_t * pSupp;
00838     pSupp = Ivy_ObjSupp( pAig, pObj );
00839     if ( pObj != pRoot && (pSupp->nRefs > 0 || Ivy_ObjIsCi(pObj)) )
00840         return;
00841     Ivy_FastMapRequired_rec( pAig, Ivy_ObjFanin0(pObj), pRoot, DelayR );
00842     Ivy_FastMapRequired_rec( pAig, Ivy_ObjFanin1(pObj), pRoot, DelayR );
00843 //    assert( pObj == pRoot || pSupp->DelayR == IVY_INFINITY );
00844     pSupp->DelayR = DelayR;
00845 }

void Ivy_FastMapStop ( Ivy_Man_t *  pAig  ) 

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

Synopsis [Cleans memory used for decomposition.]

Description []

SideEffects []

SeeAlso []

Definition at line 190 of file ivyFastMap.c.

00191 {
00192     Ivy_SuppMan_t * p = pAig->pData;
00193     Vec_VecFree( p->vLuts );
00194     free( p->pMem );
00195     free( p );
00196     pAig->pData = NULL;
00197 }

static Ivy_ObjIsNodeInt1 ( Ivy_Obj_t *  pObj  )  [inline, static]

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 312 of file ivyFastMap.c.

00313 {
00314     return Ivy_ObjIsNode(pObj) && Ivy_ObjRefs(pObj) == 1;
00315 }

static Ivy_ObjIsNodeInt2 ( Ivy_Obj_t *  pObj  )  [inline, static]

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 328 of file ivyFastMap.c.

00329 {
00330     return Ivy_ObjIsNode(pObj) && Ivy_ObjRefs(pObj) <= 2;
00331 }

static Ivy_Supp_t* Ivy_ObjSupp ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj 
) [inline, static]

Definition at line 52 of file ivyFastMap.c.

00053 { 
00054     return (Ivy_Supp_t *)(((Ivy_SuppMan_t*)pAig->pData)->pMem + pObj->Id * ((Ivy_SuppMan_t*)pAig->pData)->nSize); 
00055 }

static Ivy_Supp_t* Ivy_ObjSuppStart ( Ivy_Man_t *  pAig,
Ivy_Obj_t *  pObj 
) [inline, static]

Definition at line 56 of file ivyFastMap.c.

00057 { 
00058     Ivy_Supp_t * pSupp;
00059     pSupp = Ivy_ObjSupp( pAig, pObj );
00060     pSupp->fMark = 0;
00061     pSupp->Delay = 0;
00062     pSupp->nSize = 1;
00063     pSupp->pArray[0] = pObj->Id;
00064     return pSupp;
00065 }

static int Vec_IntRemoveDup ( int *  pArray,
int  nSize 
) [inline, static]

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 370 of file ivyFastMap.c.

00371 {
00372     int i, k;
00373     if ( nSize < 2 )
00374         return nSize;
00375     for ( i = k = 1; i < nSize; i++ )
00376         if ( pArray[i] != pArray[i-1] )
00377             pArray[k++] = pArray[i];
00378     return k;
00379 }

static void Vec_IntSelectSort ( int *  pArray,
int  nSize 
) [inline, static]

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 344 of file ivyFastMap.c.

00345 {
00346     int temp, i, j, best_i;
00347     for ( i = 0; i < nSize-1; i++ )
00348     {
00349         best_i = i;
00350         for ( j = i+1; j < nSize; j++ )
00351             if ( pArray[j] < pArray[best_i] )
00352                 best_i = j;
00353         temp = pArray[i]; 
00354         pArray[i] = pArray[best_i]; 
00355         pArray[best_i] = temp;
00356     }
00357 }

Variable Documentation

int s_MappingMem

Definition at line 35 of file abcPrint.c.

int s_MappingTime

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

FileName [abcPrint.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Printing statistics.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

] DECLARATIONS ///

Definition at line 34 of file abcPrint.c.

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