src/map/if/ifMap.c File Reference

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

Go to the source code of this file.

Functions

static int If_WordCountOnes (unsigned uWord)
void If_ObjPerformMappingAnd (If_Man_t *p, If_Obj_t *pObj, int Mode, int fPreprocess)
void If_ObjPerformMappingChoice (If_Man_t *p, If_Obj_t *pObj, int Mode, int fPreprocess)
int If_ManPerformMappingRound (If_Man_t *p, int nCutsUsed, int Mode, int fPreprocess, char *pLabel)

Function Documentation

int If_ManPerformMappingRound ( If_Man_t *  p,
int  nCutsUsed,
int  Mode,
int  fPreprocess,
char *  pLabel 
)

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

Synopsis [Performs one mapping pass over all nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 252 of file ifMap.c.

00253 {
00254 //    ProgressBar * pProgress;
00255     If_Obj_t * pObj;
00256     int i, clk = clock();
00257     assert( Mode >= 0 && Mode <= 2 );
00258     // set the sorting function
00259     if ( Mode || p->pPars->fArea ) // area
00260         p->SortMode = 1;
00261     else if ( p->pPars->fFancy )
00262         p->SortMode = 2;
00263     else
00264         p->SortMode = 0;
00265     // set the cut number
00266     p->nCutsUsed   = nCutsUsed;
00267     p->nCutsMerged = 0;
00268     // map the internal nodes
00269 //    pProgress = Extra_ProgressBarStart( stdout, If_ManObjNum(p) );
00270     If_ManForEachNode( p, pObj, i )
00271     {
00272 //        Extra_ProgressBarUpdate( pProgress, i, pLabel );
00273         If_ObjPerformMappingAnd( p, pObj, Mode, fPreprocess );
00274         if ( pObj->fRepr )
00275             If_ObjPerformMappingChoice( p, pObj, Mode, fPreprocess );
00276     }
00277 //    Extra_ProgressBarStop( pProgress );
00278     // make sure the visit counters are all zero
00279     If_ManForEachNode( p, pObj, i )
00280         assert( pObj->nVisits == 0 );
00281     // compute required times and stats
00282     If_ManComputeRequired( p );
00283     if ( p->pPars->fVerbose )
00284     {
00285         char Symb = fPreprocess? 'P' : ((Mode == 0)? 'D' : ((Mode == 1)? 'F' : 'A'));
00286         printf( "%c: Del = %7.2f. Ar = %9.1f. Edge = %8d. Cut = %8d. ", 
00287             Symb, p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged );
00288         PRT( "T", clock() - clk );
00289 //    printf( "Max number of cuts = %d. Average number of cuts = %5.2f.\n", 
00290 //        p->nCutsMax, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
00291     }
00292     return 1;
00293 }

void If_ObjPerformMappingAnd ( If_Man_t *  p,
If_Obj_t *  pObj,
int  Mode,
int  fPreprocess 
)

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

Synopsis [Finds the best cut for the given node.]

Description [Mapping modes: delay (0), area flow (1), area (2).]

SideEffects []

SeeAlso []

Definition at line 62 of file ifMap.c.

00063 {
00064     If_Set_t * pCutSet;
00065     If_Cut_t * pCut0, * pCut1, * pCut;
00066     int i, k;
00067 
00068     assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin0) || pObj->pFanin0->pCutSet->nCuts > 1 );
00069     assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin1) || pObj->pFanin1->pCutSet->nCuts > 1 );
00070 
00071     // prepare
00072     if ( !p->pPars->fSeqMap )
00073     {
00074         if ( Mode == 0 )
00075             pObj->EstRefs = (float)pObj->nRefs;
00076         else if ( Mode == 1 )
00077             pObj->EstRefs = (float)((2.0 * pObj->EstRefs + pObj->nRefs) / 3.0);
00078     }
00079     if ( Mode && pObj->nRefs > 0 )
00080         If_CutDeref( p, If_ObjCutBest(pObj), IF_INFINITY );
00081 
00082     // prepare the cutset
00083     pCutSet = If_ManSetupNodeCutSet( p, pObj );
00084 
00085     // get the current assigned best cut
00086     pCut = If_ObjCutBest(pObj);
00087     if ( pCut->nLeaves > 0 )
00088     {
00089         // recompute the parameters of the best cut
00090         pCut->Delay = If_CutDelay( p, pCut );
00091         assert( pCut->Delay <= pObj->Required + p->fEpsilon );
00092         pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, IF_INFINITY ) : If_CutFlow( p, pCut );
00093         // save the best cut from the previous iteration
00094         if ( !fPreprocess )
00095             If_CutCopy( p, pCutSet->ppCuts[pCutSet->nCuts++], pCut );
00096     }
00097 
00098     // generate cuts
00099     If_ObjForEachCut( pObj->pFanin0, pCut0, i )
00100     If_ObjForEachCut( pObj->pFanin1, pCut1, k )
00101     {
00102         // get the next free cut
00103         assert( pCutSet->nCuts <= pCutSet->nCutsMax );
00104         pCut = pCutSet->ppCuts[pCutSet->nCuts];
00105         // make sure K-feasible cut exists
00106         if ( If_WordCountOnes(pCut0->uSign | pCut1->uSign) > p->pPars->nLutSize )
00107             continue;
00108         // merge the nodes
00109         if ( !If_CutMerge( pCut0, pCut1, pCut ) )
00110             continue;
00111         assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
00112         p->nCutsMerged++;
00113         // check if this cut is contained in any of the available cuts
00114 //        if ( p->pPars->pFuncCost == NULL && If_CutFilter( p, pCut ) ) // do not filter functionality cuts
00115         if ( If_CutFilter( pCutSet, pCut ) )
00116             continue;
00117         // compute the truth table
00118         pCut->fCompl = 0;
00119         if ( p->pPars->fTruth )
00120             If_CutComputeTruth( p, pCut, pCut0, pCut1, pObj->fCompl0, pObj->fCompl1 );
00121         // compute the application-specific cost and depth
00122         pCut->fUser = (p->pPars->pFuncCost != NULL);
00123         pCut->Cost = p->pPars->pFuncCost? p->pPars->pFuncCost(pCut) : 0;
00124         if ( pCut->Cost == IF_COST_MAX )
00125             continue;
00126         // check if the cut satisfies the required times
00127         pCut->Delay = If_CutDelay( p, pCut );
00128 //        printf( "%.2f ", pCut->Delay );
00129         if ( Mode && pCut->Delay > pObj->Required + p->fEpsilon )
00130             continue;
00131         // compute area of the cut (this area may depend on the application specific cost)
00132         pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, IF_INFINITY ) : If_CutFlow( p, pCut );
00133         pCut->AveRefs = (Mode == 0)? (float)0.0 : If_CutAverageRefs( p, pCut );
00134         // insert the cut into storage
00135         If_CutSort( p, pCutSet, pCut );
00136     } 
00137     assert( pCutSet->nCuts > 0 );
00138 
00139     // add the trivial cut to the set
00140     If_ManSetupCutTriv( p, pCutSet->ppCuts[pCutSet->nCuts++], pObj->Id );
00141     assert( pCutSet->nCuts <= pCutSet->nCutsMax+1 );
00142 
00143     // update the best cut
00144     if ( !fPreprocess || pCutSet->ppCuts[0]->Delay <= pObj->Required + p->fEpsilon )
00145         If_CutCopy( p, If_ObjCutBest(pObj), pCutSet->ppCuts[0] );
00146     assert( p->pPars->fSeqMap || If_ObjCutBest(pObj)->nLeaves > 1 );
00147 
00148     // ref the selected cut
00149     if ( Mode && pObj->nRefs > 0 )
00150         If_CutRef( p, If_ObjCutBest(pObj), IF_INFINITY );
00151 
00152     // call the user specified function for each cut
00153     if ( p->pPars->pFuncUser )
00154         If_ObjForEachCut( pObj, pCut, i )
00155             p->pPars->pFuncUser( p, pObj, pCut );
00156 
00157     // free the cuts
00158     If_ManDerefNodeCutSet( p, pObj );
00159 }

void If_ObjPerformMappingChoice ( If_Man_t *  p,
If_Obj_t *  pObj,
int  Mode,
int  fPreprocess 
)

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

Synopsis [Finds the best cut for the choice node.]

Description []

SideEffects []

SeeAlso []

Definition at line 172 of file ifMap.c.

00173 {
00174     If_Set_t * pCutSet;
00175     If_Obj_t * pTemp;
00176     If_Cut_t * pCutTemp, * pCut;
00177     int i;
00178     assert( pObj->pEquiv != NULL );
00179 
00180     // prepare
00181     if ( Mode && pObj->nRefs > 0 )
00182         If_CutDeref( p, If_ObjCutBest(pObj), IF_INFINITY );
00183 
00184     // remove elementary cuts
00185     for ( pTemp = pObj; pTemp; pTemp = pTemp->pEquiv )
00186         pTemp->pCutSet->nCuts--;
00187 
00188     // update the cutset of the node
00189     pCutSet = pObj->pCutSet;
00190 
00191     // generate cuts
00192     for ( pTemp = pObj->pEquiv; pTemp; pTemp = pTemp->pEquiv )
00193     {
00194         assert( pTemp->nRefs == 0 );
00195         assert( p->pPars->fSeqMap || pTemp->pCutSet->nCuts > 0 );
00196         // go through the cuts of this node
00197         If_ObjForEachCut( pTemp, pCutTemp, i )
00198         {
00199             assert( p->pPars->fSeqMap || pCutTemp->nLeaves > 1 );
00200             // get the next free cut
00201             assert( pCutSet->nCuts <= pCutSet->nCutsMax );
00202             pCut = pCutSet->ppCuts[pCutSet->nCuts];
00203             // copy the cut into storage
00204             If_CutCopy( p, pCut, pCutTemp );
00205             // check if this cut is contained in any of the available cuts
00206             if ( If_CutFilter( pCutSet, pCut ) )
00207                 continue;
00208             // check if the cut satisfies the required times
00209             assert( pCut->Delay == If_CutDelay( p, pCut ) );
00210             if ( Mode && pCut->Delay > pObj->Required + p->fEpsilon )
00211                 continue;
00212             // set the phase attribute
00213             assert( pCut->fCompl == 0 );
00214             pCut->fCompl ^= (pObj->fPhase ^ pTemp->fPhase); // why ^= ?
00215             // compute area of the cut (this area may depend on the application specific cost)
00216             pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, IF_INFINITY ) : If_CutFlow( p, pCut );
00217             pCut->AveRefs = (Mode == 0)? (float)0.0 : If_CutAverageRefs( p, pCut );
00218             // insert the cut into storage
00219             If_CutSort( p, pCutSet, pCut );
00220         }
00221     }
00222     assert( pCutSet->nCuts > 0 );
00223 
00224     // add the trivial cut to the set
00225     If_ManSetupCutTriv( p, pCutSet->ppCuts[pCutSet->nCuts++], pObj->Id );
00226     assert( pCutSet->nCuts <= pCutSet->nCutsMax+1 );
00227 
00228     // update the best cut
00229     if ( !fPreprocess || pCutSet->ppCuts[0]->Delay <= pObj->Required + p->fEpsilon )
00230         If_CutCopy( p, If_ObjCutBest(pObj), pCutSet->ppCuts[0] );
00231     assert( p->pPars->fSeqMap || If_ObjCutBest(pObj)->nLeaves > 1 );
00232 
00233     // ref the selected cut
00234     if ( Mode && pObj->nRefs > 0 )
00235         If_CutRef( p, If_ObjCutBest(pObj), IF_INFINITY );
00236 
00237     // free the cuts
00238     If_ManDerefChoiceCutSet( p, pObj );
00239 }

static int If_WordCountOnes ( unsigned  uWord  )  [inline, static]

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

FileName [ifMap.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [FPGA mapping based on priority cuts.]

Synopsis [Mapping procedures.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

] DECLARATIONS /// FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Counts the number of 1s in the signature.]

Description []

SideEffects []

SeeAlso []

Definition at line 42 of file ifMap.c.

00043 {
00044     uWord = (uWord & 0x55555555) + ((uWord>>1) & 0x55555555);
00045     uWord = (uWord & 0x33333333) + ((uWord>>2) & 0x33333333);
00046     uWord = (uWord & 0x0F0F0F0F) + ((uWord>>4) & 0x0F0F0F0F);
00047     uWord = (uWord & 0x00FF00FF) + ((uWord>>8) & 0x00FF00FF);
00048     return  (uWord & 0x0000FFFF) + (uWord>>16);
00049 }

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