src/map/if/ifReduce.c File Reference

#include "if.h"
Include dependency graph for ifReduce.c:

Go to the source code of this file.

Functions

static void If_ManImproveReduce (If_Man_t *p, int nLimit)
static void If_ManImproveExpand (If_Man_t *p, int nLimit)
static void If_ManImproveNodeExpand (If_Man_t *p, If_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld, Vec_Ptr_t *vVisited)
static void If_ManImproveNodePrepare (If_Man_t *p, If_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld, Vec_Ptr_t *vVisited)
static void If_ManImproveNodeUpdate (If_Man_t *p, If_Obj_t *pObj, Vec_Ptr_t *vFront)
static void If_ManImproveNodeFaninCompact (If_Man_t *p, If_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vVisited)
void If_ManImproveMapping (If_Man_t *p)
int If_ManImproveCutCost (If_Man_t *p, Vec_Ptr_t *vFront)
void If_ManImproveMark_rec (If_Man_t *p, If_Obj_t *pObj, Vec_Ptr_t *vVisited)
int If_ManImproveNodeWillGrow (If_Man_t *p, If_Obj_t *pObj)
int If_ManImproveNodeFaninCost (If_Man_t *p, If_Obj_t *pObj)
void If_ManImproveNodeFaninUpdate (If_Man_t *p, If_Obj_t *pObj, Vec_Ptr_t *vFront, Vec_Ptr_t *vVisited)
int If_ManImproveNodeFaninCompact0 (If_Man_t *p, If_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vVisited)
int If_ManImproveNodeFaninCompact1 (If_Man_t *p, If_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vVisited)
int If_ManImproveNodeFaninCompact2 (If_Man_t *p, If_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vVisited)
int If_ManImproveNodeFaninCompact_int (If_Man_t *p, If_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vVisited)
void If_ManImproveNodeReduce (If_Man_t *p, If_Obj_t *pObj, int nLimit)

Function Documentation

int If_ManImproveCutCost ( If_Man_t *  p,
Vec_Ptr_t *  vFront 
)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 125 of file ifReduce.c.

00126 {
00127     If_Obj_t * pFanin;
00128     int i, Counter = 0;
00129     Vec_PtrForEachEntry( vFront, pFanin, i )
00130         if ( pFanin->nRefs == 0 )
00131             Counter++;
00132     return Counter;
00133 }

void If_ManImproveExpand ( If_Man_t *  p,
int  nLimit 
) [static]

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 98 of file ifReduce.c.

00099 {
00100     Vec_Ptr_t * vFront, * vFrontOld, * vVisited;
00101     If_Obj_t * pObj;
00102     int i;
00103     vFront    = Vec_PtrAlloc( nLimit );
00104     vFrontOld = Vec_PtrAlloc( nLimit );
00105     vVisited  = Vec_PtrAlloc( 100 );
00106     // iterate through all nodes in the topological order
00107     If_ManForEachNode( p, pObj, i )
00108         If_ManImproveNodeExpand( p, pObj, nLimit, vFront, vFrontOld, vVisited );
00109     Vec_PtrFree( vFront );
00110     Vec_PtrFree( vFrontOld );
00111     Vec_PtrFree( vVisited );
00112 }

void If_ManImproveMapping ( If_Man_t *  p  ) 

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

Synopsis [Improves current mapping using expand/Expand of one cut.]

Description [Assumes current mapping assigned and required times computed.]

SideEffects []

SeeAlso []

Definition at line 49 of file ifReduce.c.

00050 {
00051     int clk;
00052 
00053     clk = clock();
00054     If_ManImproveExpand( p, p->pPars->nLutSize );
00055     If_ManComputeRequired( p );
00056     if ( p->pPars->fVerbose )
00057     {
00058         printf( "E: Del = %7.2f. Ar = %9.1f. Edge = %8d. Cut = %8d. ", 
00059             p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged );
00060         PRT( "T", clock() - clk );
00061     }
00062  
00063 /*
00064     clk = clock();
00065     If_ManImproveReduce( p, p->pPars->nLutSize );
00066     If_ManComputeRequired( p, 0 );
00067     if ( p->pPars->fVerbose )
00068     {
00069         printf( "R:  Del = %6.2f. Area = %8.2f. Nets = %6d. Cuts = %8d. Lim = %2d. Ave = %5.2f. ", 
00070             p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
00071         PRT( "T", clock() - clk );
00072     }
00073 */
00074 /*
00075     clk = clock();
00076     If_ManImproveExpand( p, p->pPars->nLutSize );
00077     If_ManComputeRequired( p, 0 );
00078     if ( p->pPars->fVerbose )
00079     {
00080         printf( "E:  Del = %6.2f. Area = %8.2f. Nets = %6d. Cuts = %8d. Lim = %2d. Ave = %5.2f. ", 
00081             p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
00082         PRT( "T", clock() - clk );
00083     }
00084 */
00085 }

void If_ManImproveMark_rec ( If_Man_t *  p,
If_Obj_t *  pObj,
Vec_Ptr_t *  vVisited 
)

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 199 of file ifReduce.c.

00200 {
00201     if ( pObj->fMark )
00202         return;
00203     assert( If_ObjIsAnd(pObj) );
00204     If_ManImproveMark_rec( p, If_ObjFanin0(pObj), vVisited );
00205     If_ManImproveMark_rec( p, If_ObjFanin1(pObj), vVisited );
00206     Vec_PtrPush( vVisited, pObj );
00207     pObj->fMark = 1;
00208 }

void If_ManImproveNodeExpand ( If_Man_t *  p,
If_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vFrontOld,
Vec_Ptr_t *  vVisited 
) [static]

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 146 of file ifReduce.c.

00147 {
00148     If_Obj_t * pFanin;
00149     If_Cut_t * pCut;
00150     int CostBef, CostAft, i;
00151     float DelayOld, AreaBef, AreaAft;
00152     pCut = If_ObjCutBest(pObj);
00153     assert( pCut->Delay <= pObj->Required + p->fEpsilon );
00154     if ( pObj->nRefs == 0 )
00155         return;
00156     // get the delay
00157     DelayOld = pCut->Delay;
00158     // get the area
00159     AreaBef = If_CutAreaRefed( p, pCut, IF_INFINITY );
00160 //    if ( AreaBef == 1 )
00161 //        return;
00162     // the cut is non-trivial
00163     If_ManImproveNodePrepare( p, pObj, nLimit, vFront, vFrontOld, vVisited );
00164     // iteratively modify the cut
00165     If_CutDeref( p, pCut, IF_INFINITY );
00166     CostBef = If_ManImproveCutCost( p, vFront );
00167     If_ManImproveNodeFaninCompact( p, pObj, nLimit, vFront, vVisited );
00168     CostAft = If_ManImproveCutCost( p, vFront );
00169     If_CutRef( p, pCut, IF_INFINITY );
00170     assert( CostBef >= CostAft );
00171     // clean up
00172     Vec_PtrForEachEntry( vVisited, pFanin, i )
00173         pFanin->fMark = 0;
00174     // update the node
00175     If_ManImproveNodeUpdate( p, pObj, vFront );
00176     pCut->Delay = If_CutDelay( p, pCut );
00177     // get the new area
00178     AreaAft = If_CutAreaRefed( p, pCut, IF_INFINITY );
00179     if ( AreaAft > AreaBef || pCut->Delay > pObj->Required + p->fEpsilon )
00180     {
00181         If_ManImproveNodeUpdate( p, pObj, vFrontOld );
00182         AreaAft = If_CutAreaRefed( p, pCut, IF_INFINITY );
00183         assert( AreaAft == AreaBef );
00184         pCut->Delay = DelayOld;
00185     }
00186 }

void If_ManImproveNodeFaninCompact ( If_Man_t *  p,
If_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vVisited 
) [static]

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 469 of file ifReduce.c.

00470 {
00471     while ( If_ManImproveNodeFaninCompact_int( p, pObj, nLimit, vFront, vVisited ) );
00472 }

int If_ManImproveNodeFaninCompact0 ( If_Man_t *  p,
If_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vVisited 
)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 360 of file ifReduce.c.

00361 {
00362     If_Obj_t * pFanin;
00363     int i;
00364     Vec_PtrForEachEntry( vFront, pFanin, i )
00365     {
00366         if ( If_ObjIsCi(pFanin) )
00367             continue;
00368         if ( If_ManImproveNodeWillGrow(p, pFanin) )
00369             continue;
00370         if ( If_ManImproveNodeFaninCost(p, pFanin) <= 0 )
00371         {
00372             If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited );
00373             return 1;
00374         }
00375     }
00376     return 0;
00377 }

int If_ManImproveNodeFaninCompact1 ( If_Man_t *  p,
If_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vVisited 
)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 390 of file ifReduce.c.

00391 {
00392     If_Obj_t * pFanin;
00393     int i;
00394     Vec_PtrForEachEntry( vFront, pFanin, i )
00395     {
00396         if ( If_ObjIsCi(pFanin) )
00397             continue;
00398         if ( If_ManImproveNodeFaninCost(p, pFanin) < 0 )
00399         {
00400             If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited );
00401             return 1;
00402         }
00403     }
00404     return 0;
00405 }

int If_ManImproveNodeFaninCompact2 ( If_Man_t *  p,
If_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vVisited 
)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 418 of file ifReduce.c.

00419 {
00420     If_Obj_t * pFanin;
00421     int i;
00422     Vec_PtrForEachEntry( vFront, pFanin, i )
00423     {
00424         if ( If_ObjIsCi(pFanin) )
00425             continue;
00426         if ( If_ManImproveNodeFaninCost(p, pFanin) <= 0 )
00427         {
00428             If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited );
00429             return 1;
00430         }
00431     }
00432     return 0;
00433 }

int If_ManImproveNodeFaninCompact_int ( If_Man_t *  p,
If_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vVisited 
)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 446 of file ifReduce.c.

00447 {
00448     if ( If_ManImproveNodeFaninCompact0(p, pObj, nLimit, vFront, vVisited) )
00449         return 1;
00450     if (  Vec_PtrSize(vFront) < nLimit && If_ManImproveNodeFaninCompact1(p, pObj, nLimit, vFront, vVisited) )
00451         return 1;
00452     if ( Vec_PtrSize(vFront) < nLimit && If_ManImproveNodeFaninCompact2(p, pObj, nLimit, vFront, vVisited) )
00453         return 1;
00454     assert( Vec_PtrSize(vFront) <= nLimit );
00455     return 0;
00456 }

int If_ManImproveNodeFaninCost ( If_Man_t *  p,
If_Obj_t *  pObj 
)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 301 of file ifReduce.c.

00302 {
00303     int Counter = 0;
00304     assert( If_ObjIsAnd(pObj) );
00305     // check if the node has external refs
00306     if ( pObj->nRefs == 0 )
00307         Counter--;
00308     // increment the number of fanins without external refs
00309     if ( !If_ObjFanin0(pObj)->fMark && If_ObjFanin0(pObj)->nRefs == 0 )
00310         Counter++;
00311     // increment the number of fanins without external refs
00312     if ( !If_ObjFanin1(pObj)->fMark && If_ObjFanin1(pObj)->nRefs == 0 )
00313         Counter++;
00314     return Counter;
00315 }

void If_ManImproveNodeFaninUpdate ( If_Man_t *  p,
If_Obj_t *  pObj,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vVisited 
)

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

Synopsis [Updates the frontier.]

Description []

SideEffects []

SeeAlso []

Definition at line 328 of file ifReduce.c.

00329 {
00330     If_Obj_t * pFanin;
00331     assert( If_ObjIsAnd(pObj) );
00332     Vec_PtrRemove( vFront, pObj );
00333     pFanin = If_ObjFanin0(pObj);
00334     if ( !pFanin->fMark )
00335     {
00336         Vec_PtrPush( vFront, pFanin );
00337         Vec_PtrPush( vVisited, pFanin );
00338         pFanin->fMark = 1;
00339     }
00340     pFanin = If_ObjFanin1(pObj);
00341     if ( !pFanin->fMark )
00342     {
00343         Vec_PtrPush( vFront, pFanin );
00344         Vec_PtrPush( vVisited, pFanin );
00345         pFanin->fMark = 1;
00346     }
00347 }

void If_ManImproveNodePrepare ( If_Man_t *  p,
If_Obj_t *  pObj,
int  nLimit,
Vec_Ptr_t *  vFront,
Vec_Ptr_t *  vFrontOld,
Vec_Ptr_t *  vVisited 
) [static]

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

Synopsis [Prepares node mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 221 of file ifReduce.c.

00222 {
00223     If_Cut_t * pCut;
00224     If_Obj_t * pLeaf;
00225     int i;
00226     Vec_PtrClear( vFront );
00227     Vec_PtrClear( vFrontOld );
00228     Vec_PtrClear( vVisited );
00229     // expand the cut downwards from the given place
00230     pCut = If_ObjCutBest(pObj);
00231     If_CutForEachLeaf( p, pCut, pLeaf, i )
00232     {
00233         Vec_PtrPush( vFront, pLeaf );
00234         Vec_PtrPush( vFrontOld, pLeaf );
00235         Vec_PtrPush( vVisited, pLeaf );
00236         pLeaf->fMark = 1;
00237     }
00238     // mark the nodes in the cone
00239     If_ManImproveMark_rec( p, pObj, vVisited );
00240 }

void If_ManImproveNodeReduce ( If_Man_t *  p,
If_Obj_t *  pObj,
int  nLimit 
)

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 489 of file ifReduce.c.

00490 {
00491 /*
00492     If_Cut_t * pCut, * pCut0, * pCut1, * pCutR;
00493     If_Obj_t * pFanin0, * pFanin1;
00494     float AreaBef, AreaAft;
00495     int RetValue;
00496 
00497     assert( nLimit <= 32 );
00498     assert( If_ObjIsAnd(pObj) );
00499     // get the fanins
00500     pFanin0 = If_ObjFanin0(pObj);
00501     pFanin1 = If_ObjFanin1(pObj);
00502     // get the cuts
00503     pCut  = If_ObjCutBest(pObj);
00504     pCut0 = If_ObjIsCi(pFanin0) ? If_ObjCutTriv(pFanin0) : If_ObjCutBest(pFanin0);
00505     pCut1 = If_ObjIsCi(pFanin1) ? If_ObjCutTriv(pFanin1) : If_ObjCutBest(pFanin1);
00506     assert( pCut->Delay <= pObj->Required + p->fEpsilon );
00507 
00508     // deref the cut if the node is refed
00509     if ( pObj->nRefs > 0 )
00510         If_CutDeref( p, pCut, IF_INFINITY );
00511     // get the area
00512     AreaBef = If_CutAreaDerefed( p, pCut, IF_INFINITY );
00513     // get the fanin support
00514     if ( pFanin0->nRefs > 2 && pCut0->Delay < pObj->Required + p->fEpsilon )
00515 //    if ( pSupp0->nRefs > 0 && pSupp0->Delay < pSupp->DelayR ) // this leads to 2% worse results
00516     {
00517         pCut0 = If_ObjCutTriv(pFanin0);
00518     }
00519     // get the fanin support
00520     if ( pFanin1->nRefs > 2 && pCut1->Delay < pObj->Required + p->fEpsilon )
00521 //    if ( pSupp1->nRefs > 0 && pSupp1->Delay < pSupp->DelayR )
00522     {
00523         pCut1 = If_ObjCutTriv(pFanin1);
00524     }
00525 
00526     // merge the cuts
00527     pCutR = p->ppCuts[0];
00528     RetValue = If_CutMerge( pCut0, pCut1, pCutR );
00529     // try very simple cut
00530     if ( !RetValue )
00531     {
00532         RetValue = If_CutMerge( If_ObjCutTriv(pFanin0), If_ObjCutTriv(pFanin1), pCutR );
00533         assert( RetValue == 1 );
00534     }
00535     if ( RetValue )
00536     {
00537         pCutR->Delay = If_CutDelay( p, pCutR );
00538         AreaAft = If_CutAreaDerefed( p, pCutR, IF_INFINITY );
00539         // update the best cut
00540         if ( AreaAft < AreaBef - p->fEpsilon && pCutR->Delay < pObj->Required + p->fEpsilon )
00541             If_CutCopy( p, pCut, pCutR );
00542     }
00543     // recompute the delay of the best cut
00544     pCut->Delay = If_CutDelay( p, pCut );
00545     // ref the cut if the node is refed
00546     if ( pObj->nRefs > 0 )
00547         If_CutRef( p, pCut, IF_INFINITY );
00548 */
00549 }

void If_ManImproveNodeUpdate ( If_Man_t *  p,
If_Obj_t *  pObj,
Vec_Ptr_t *  vFront 
) [static]

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

Synopsis [Updates the frontier.]

Description []

SideEffects []

SeeAlso []

Definition at line 253 of file ifReduce.c.

00254 {
00255     If_Cut_t * pCut;
00256     If_Obj_t * pFanin;
00257     int i;
00258     pCut = If_ObjCutBest(pObj);
00259     // deref node's cut
00260     If_CutDeref( p, pCut, IF_INFINITY );
00261     // update the node's cut
00262     pCut->nLeaves = Vec_PtrSize(vFront);
00263     Vec_PtrForEachEntry( vFront, pFanin, i )
00264         pCut->pLeaves[i] = pFanin->Id;
00265     // ref the new cut
00266     If_CutRef( p, pCut, IF_INFINITY );
00267 }

int If_ManImproveNodeWillGrow ( If_Man_t *  p,
If_Obj_t *  pObj 
)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 281 of file ifReduce.c.

00282 {
00283     If_Obj_t * pFanin0, * pFanin1;
00284     assert( If_ObjIsAnd(pObj) );
00285     pFanin0 = If_ObjFanin0(pObj);
00286     pFanin1 = If_ObjFanin1(pObj);
00287     return !pFanin0->fMark && !pFanin1->fMark;
00288 }

void If_ManImproveReduce ( If_Man_t *  p,
int  nLimit 
) [static]

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

FileName [ifExpand.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [FPGA mapping based on priority cuts.]

Synopsis [Incremental improvement of current mapping.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - November 21, 2006.]

Revision [

Id
ifExpand.c,v 1.00 2006/11/21 00:00:00 alanmi Exp

] DECLARATIONS ///

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 562 of file ifReduce.c.

00563 {
00564     If_Obj_t * pObj;
00565     int i;
00566     If_ManForEachNode( p, pObj, i )
00567         If_ManImproveNodeReduce( p, pObj, nLimit );
00568 }

Generated on Tue Jan 5 12:19:04 2010 for abc70930 by  doxygen 1.6.1