src/map/mapper/mapperRefs.c File Reference

#include "mapperInt.h"
Include dependency graph for mapperRefs.c:

Go to the source code of this file.

Functions

static int Map_NodeIncRefPhaseAct (Map_Node_t *pNode, int fPhase)
static int Map_NodeDecRefPhaseAct (Map_Node_t *pNode, int fPhase)
static float Map_CutRefDeref (Map_Cut_t *pCut, int fPhase, int fReference)
static void Map_MappingSetRefs_rec (Map_Man_t *pMan, Map_Node_t *pNode, Map_Node_t **ppStore)
int Map_NodeReadRefPhaseAct (Map_Node_t *pNode, int fPhase)
float Map_NodeReadRefPhaseEst (Map_Node_t *pNode, int fPhase)
void Map_MappingEstimateRefsInit (Map_Man_t *p)
void Map_MappingEstimateRefs (Map_Man_t *p)
float Map_CutGetAreaFlow (Map_Cut_t *pCut, int fPhase)
float Map_CutGetAreaRefed (Map_Cut_t *pCut, int fPhase)
float Map_CutGetAreaDerefed (Map_Cut_t *pCut, int fPhase)
float Map_CutRef (Map_Cut_t *pCut, int fPhase)
float Map_CutDeref (Map_Cut_t *pCut, int fPhase)
void Map_MappingSetRefs (Map_Man_t *pMan)
float Map_MappingGetArea (Map_Man_t *pMan, Map_NodeVec_t *vMapping)

Function Documentation

float Map_CutDeref ( Map_Cut_t *  pCut,
int  fPhase 
)

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

synopsis [Dereferences the cut.]

description []

sideeffects []

seealso []

Definition at line 291 of file mapperRefs.c.

00292 {
00293     return Map_CutRefDeref( pCut, fPhase, 0 ); // dereference
00294 }

float Map_CutGetAreaDerefed ( Map_Cut_t *  pCut,
int  fPhase 
)

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

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

description []

sideeffects []

seealso []

Definition at line 255 of file mapperRefs.c.

00256 {
00257     float aResult, aResult2;
00258     aResult2 = Map_CutRefDeref( pCut, fPhase, 1 ); // reference
00259     aResult  = Map_CutRefDeref( pCut, fPhase, 0 ); // dereference
00260 //    assert( aResult == aResult2 );
00261     return aResult;
00262 }

float Map_CutGetAreaFlow ( Map_Cut_t *  pCut,
int  fPhase 
)

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

synopsis [Computes the area flow of the cut.]

description [Computes the area flow of the cut if it is implemented using the best supergate with the best phase.]

sideeffects []

seealso []

Definition at line 185 of file mapperRefs.c.

00186 {
00187     Map_Match_t * pM = pCut->M + fPhase;
00188     Map_Super_t * pSuper = pM->pSuperBest;
00189     unsigned uPhaseTot = pM->uPhaseBest;
00190     Map_Cut_t * pCutFanin;
00191     float aFlowRes, aFlowFanin, nRefs;
00192     int i, fPinPhasePos;
00193 
00194     // start the resulting area flow
00195     aFlowRes = pSuper->Area;
00196     // iterate through the leaves
00197     for ( i = 0; i < pCut->nLeaves; i++ )
00198     {
00199         // get the phase of this fanin
00200         fPinPhasePos = ((uPhaseTot & (1 << i)) == 0);
00201         // get the cut implementing this phase of the fanin
00202         pCutFanin = pCut->ppLeaves[i]->pCutBest[fPinPhasePos];
00203         // if the cut is not available, we have to use the opposite phase
00204         if ( pCutFanin == NULL )
00205         {
00206             fPinPhasePos = !fPinPhasePos;
00207             pCutFanin = pCut->ppLeaves[i]->pCutBest[fPinPhasePos];
00208         }
00209         aFlowFanin = pCutFanin->M[fPinPhasePos].AreaFlow; // ignores the area of the interter
00210         // get the fanout count of the cut in the given phase
00211         nRefs = Map_NodeReadRefPhaseEst( pCut->ppLeaves[i], fPinPhasePos );
00212         // if the node does no fanout, assume fanout count equal to 1
00213         if ( nRefs == (float)0.0 )
00214             nRefs = (float)1.0;
00215         // add the area flow due to the fanin
00216         aFlowRes += aFlowFanin / nRefs;
00217     }
00218     pM->AreaFlow = aFlowRes;
00219     return aFlowRes;
00220 }

float Map_CutGetAreaRefed ( Map_Cut_t *  pCut,
int  fPhase 
)

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

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

description [Assumes that the cut is referenced.]

sideeffects []

seealso []

Definition at line 235 of file mapperRefs.c.

00236 {
00237     float aResult, aResult2;
00238     aResult2 = Map_CutRefDeref( pCut, fPhase, 0 ); // dereference
00239     aResult  = Map_CutRefDeref( pCut, fPhase, 1 ); // reference
00240 //    assert( aResult == aResult2 );
00241     return aResult;
00242 }

float Map_CutRef ( Map_Cut_t *  pCut,
int  fPhase 
)

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

synopsis [References the cut.]

description []

sideeffects []

seealso []

Definition at line 275 of file mapperRefs.c.

00276 {
00277     return Map_CutRefDeref( pCut, fPhase, 1 ); // reference
00278 }

float Map_CutRefDeref ( Map_Cut_t *  pCut,
int  fPhase,
int  fReference 
) [static]

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

synopsis [References or dereferences the cut.]

description [This reference part is similar to Cudd_NodeReclaim(). The dereference part is similar to Cudd_RecursiveDeref().]

sideeffects []

seealso []

Definition at line 308 of file mapperRefs.c.

00309 {
00310     Map_Node_t * pNodeChild;
00311     Map_Cut_t * pCutChild;
00312     float aArea;
00313     int i, fPhaseChild;
00314 //    int nRefs;
00315 
00316     // consider the elementary variable
00317     if ( pCut->nLeaves == 1 )
00318         return 0;
00319     // start the area of this cut
00320     aArea = Map_CutGetRootArea( pCut, fPhase );
00321     // go through the children
00322     for ( i = 0; i < pCut->nLeaves; i++ )
00323     {
00324         pNodeChild  = pCut->ppLeaves[i];
00325         fPhaseChild = Map_CutGetLeafPhase( pCut, fPhase, i );
00326         // get the reference counter of the child
00327 /*
00328         // this code does not take inverters into account
00329         // the quality of area recovery seems to always be a little worse
00330         if ( fReference )
00331             nRefs = Map_NodeIncRefPhaseAct( pNodeChild, fPhaseChild );
00332         else
00333             nRefs = Map_NodeDecRefPhaseAct( pNodeChild, fPhaseChild );
00334         assert( nRefs >= 0 );
00335         // skip if the child was already reference before
00336         if ( nRefs > 0 )
00337             continue;
00338 */
00339 
00340         if ( fReference )
00341         {
00342             if ( pNodeChild->pCutBest[0] && pNodeChild->pCutBest[1] ) // both phases are present
00343             {
00344                 // if this phase of the node is referenced, there is no recursive call
00345                 pNodeChild->nRefAct[2]++;
00346                 if ( pNodeChild->nRefAct[fPhaseChild]++ > 0 )
00347                     continue;
00348             }
00349             else // only one phase is present
00350             {
00351                 // inverter should be added if the phase
00352                 // (a) has no reference and (b) is implemented using other phase
00353                 if ( pNodeChild->nRefAct[fPhaseChild]++ == 0 && pNodeChild->pCutBest[fPhaseChild] == NULL )
00354                     aArea += pNodeChild->p->pSuperLib->AreaInv;
00355                 // if the node is referenced, there is no recursive call
00356                 if ( pNodeChild->nRefAct[2]++ > 0 )
00357                     continue;
00358             }
00359         }
00360         else
00361         {
00362             if ( pNodeChild->pCutBest[0] && pNodeChild->pCutBest[1] ) // both phases are present
00363             {
00364                 // if this phase of the node is referenced, there is no recursive call
00365                 --pNodeChild->nRefAct[2];
00366                 if ( --pNodeChild->nRefAct[fPhaseChild] > 0 )
00367                     continue;
00368             }
00369             else // only one phase is present
00370             {
00371                 // inverter should be added if the phase
00372                 // (a) has no reference and (b) is implemented using other phase
00373                 if ( --pNodeChild->nRefAct[fPhaseChild] == 0 && pNodeChild->pCutBest[fPhaseChild] == NULL )
00374                     aArea += pNodeChild->p->pSuperLib->AreaInv;
00375                 // if the node is referenced, there is no recursive call
00376                 if ( --pNodeChild->nRefAct[2] > 0 )
00377                     continue;
00378             }
00379             assert( pNodeChild->nRefAct[fPhaseChild] >= 0 );
00380         }
00381 
00382         // get the child cut
00383         pCutChild = pNodeChild->pCutBest[fPhaseChild];
00384         // if the child does not have this phase mapped, take the opposite phase
00385         if ( pCutChild == NULL )
00386         {
00387             fPhaseChild = !fPhaseChild;
00388             pCutChild   = pNodeChild->pCutBest[fPhaseChild];
00389         }
00390         // reference and compute area recursively
00391         aArea += Map_CutRefDeref( pCutChild, fPhaseChild, fReference );
00392     }
00393     return aArea;
00394 }

void Map_MappingEstimateRefs ( Map_Man_t *  p  ) 

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

Synopsis [Sets the estimated reference counter.]

Description [When this procedure is called for the first time, the reference counter is estimated from the AIG. Otherwise, it is a linear combination of reference counters in the last two iterations.]

SideEffects []

SeeAlso []

Definition at line 153 of file mapperRefs.c.

00154 {
00155     Map_Node_t * pNode;
00156     int i;
00157     for ( i = 0; i < p->vAnds->nSize; i++ )
00158     {
00159         pNode = p->vAnds->pArray[i];
00160 //        pNode->nRefEst[0] = (float)((2.0 * pNode->nRefEst[0] + 1.0 * pNode->nRefAct[0]) / 3.0);
00161 //        pNode->nRefEst[1] = (float)((2.0 * pNode->nRefEst[1] + 1.0 * pNode->nRefAct[1]) / 3.0);
00162 //        pNode->nRefEst[2] = (float)((2.0 * pNode->nRefEst[2] + 1.0 * pNode->nRefAct[2]) / 3.0);
00163         pNode->nRefEst[0] = (float)((3.0 * pNode->nRefEst[0] + 1.0 * pNode->nRefAct[0]) / 4.0);
00164         pNode->nRefEst[1] = (float)((3.0 * pNode->nRefEst[1] + 1.0 * pNode->nRefAct[1]) / 4.0);
00165         pNode->nRefEst[2] = (float)((3.0 * pNode->nRefEst[2] + 1.0 * pNode->nRefAct[2]) / 4.0);
00166     }
00167 }

void Map_MappingEstimateRefsInit ( Map_Man_t *  p  ) 

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

Synopsis [Sets the estimated reference counter for the PIs.]

Description []

SideEffects []

SeeAlso []

Definition at line 128 of file mapperRefs.c.

00129 {
00130     Map_Node_t * pNode;
00131     int i;
00132     for ( i = 0; i < p->vAnds->nSize; i++ )
00133     {
00134         pNode = p->vAnds->pArray[i];
00135 //        pNode->nRefEst[0] = pNode->nRefEst[1] = ((float)pNode->nRefs)*(float)2.0;
00136         pNode->nRefEst[0] = pNode->nRefEst[1] = pNode->nRefEst[2] = ((float)pNode->nRefs);
00137     }
00138 }

float Map_MappingGetArea ( Map_Man_t *  pMan,
Map_NodeVec_t *  vMapping 
)

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

Synopsis [Computes the array of mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 517 of file mapperRefs.c.

00518 {
00519     Map_Node_t * pNode;
00520     float Area;
00521     int i;
00522     Area = 0.0;
00523     for ( i = 0; i < vMapping->nSize; i++ )
00524     {
00525         pNode = vMapping->pArray[i];
00526         // at least one phase has the best cut assigned
00527         assert( pNode->pCutBest[0] != NULL || pNode->pCutBest[1] != NULL );
00528         // at least one phase is used in the mapping
00529         assert( pNode->nRefAct[0] > 0 || pNode->nRefAct[1] > 0 );
00530         // compute the array due to the supergate
00531         if ( Map_NodeIsAnd(pNode) )
00532         {
00533             // count area of the negative phase
00534             if ( pNode->pCutBest[0] && (pNode->nRefAct[0] > 0 || pNode->pCutBest[1] == NULL) )
00535                 Area += pNode->pCutBest[0]->M[0].pSuperBest->Area;
00536             // count area of the positive phase
00537             if ( pNode->pCutBest[1] && (pNode->nRefAct[1] > 0 || pNode->pCutBest[0] == NULL) )
00538                 Area += pNode->pCutBest[1]->M[1].pSuperBest->Area;
00539         }
00540         // count area of the interver if we need to implement one phase with another phase
00541         if ( (pNode->pCutBest[0] == NULL && pNode->nRefAct[0] > 0) || 
00542              (pNode->pCutBest[1] == NULL && pNode->nRefAct[1] > 0) )
00543             Area += pMan->pSuperLib->AreaInv;
00544     }
00545     // add buffers for each CO driven by a CI
00546     for ( i = 0; i < pMan->nOutputs; i++ )
00547         if ( Map_NodeIsVar(pMan->pOutputs[i]) && !Map_IsComplement(pMan->pOutputs[i]) )
00548             Area += pMan->pSuperLib->AreaBuf;
00549     return Area;
00550 }

void Map_MappingSetRefs ( Map_Man_t *  pMan  ) 

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

Synopsis [Computes actual reference counters.]

Description [Collects the nodes used in the mapping in array pMan->vMapping. Nodes are collected in reverse topological order to facilitate the computation of required times.]

SideEffects []

SeeAlso []

Definition at line 412 of file mapperRefs.c.

00413 {
00414     Map_Node_t * pNode, ** ppStore;
00415     int i, fPhase, LevelMax;
00416 
00417     // clean all references
00418     for ( i = 0; i < pMan->vNodesAll->nSize; i++ )
00419     {
00420         pNode = pMan->vNodesAll->pArray[i];
00421         pNode->nRefAct[0] = 0;
00422         pNode->nRefAct[1] = 0;
00423         pNode->nRefAct[2] = 0;
00424     }
00425 
00426     // find the largest level of a node
00427     LevelMax = 0;
00428     for ( i = 0; i < pMan->nOutputs; i++ )
00429         if ( LevelMax < (int)Map_Regular(pMan->pOutputs[i])->Level )
00430             LevelMax = Map_Regular(pMan->pOutputs[i])->Level;
00431 
00432     // allocate place to store the nodes
00433     ppStore = ALLOC( Map_Node_t *, LevelMax + 1 );
00434     memset( ppStore, 0, sizeof(Map_Node_t *) * (LevelMax + 1) );
00435 
00436     // visit nodes reachable from POs in the DFS order through the best cuts
00437     for ( i = 0; i < pMan->nOutputs; i++ )
00438     {
00439         pNode  = pMan->pOutputs[i];
00440         fPhase = !Map_IsComplement(pNode);
00441         if ( !Map_NodeIsConst(pNode) )
00442             Map_MappingSetRefs_rec( pMan, pNode, ppStore );
00443     }
00444 
00445     // reconnect the nodes in reverse topological order
00446     pMan->vMapping->nSize = 0;
00447     for ( i = LevelMax; i >= 0; i-- )
00448         for ( pNode = ppStore[i]; pNode; pNode = (Map_Node_t *)pNode->pData0 )
00449             Map_NodeVecPush( pMan->vMapping, pNode );
00450     free( ppStore );
00451 }

void Map_MappingSetRefs_rec ( Map_Man_t *  pMan,
Map_Node_t *  pNode,
Map_Node_t **  ppStore 
) [static]

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

Synopsis [Recursively computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 464 of file mapperRefs.c.

00465 {
00466     Map_Cut_t * pCut;
00467     Map_Node_t * pNodeR;
00468     unsigned uPhase;
00469     int i, fPhase, fInvPin;
00470 
00471     // get the regular node and its phase
00472     pNodeR = Map_Regular(pNode);
00473     fPhase = !Map_IsComplement(pNode);
00474 
00475     // add the node to the list of all visited nodes
00476     if ( pNodeR->nRefAct[2]++ == 0 )
00477 //        Map_NodeVecPush( pMan->vMapping, pNodeR );
00478         pNodeR->pData0 = (char *)ppStore[pNodeR->Level], ppStore[pNodeR->Level] = pNodeR;
00479 
00480     // quit if the node was already visited in this phase
00481     if ( pNodeR->nRefAct[fPhase]++ )
00482         return;
00483 
00484     // quit if this is a PI node
00485     if ( Map_NodeIsVar(pNodeR) )
00486         return;
00487 
00488     // get the cut implementing this or opposite polarity
00489     pCut = pNodeR->pCutBest[fPhase];
00490     if ( pCut == NULL )
00491     {
00492         fPhase = !fPhase;
00493         pCut   = pNodeR->pCutBest[fPhase];
00494     }
00495 
00496     // visit the transitive fanin
00497     uPhase = pCut->M[fPhase].uPhaseBest;
00498     for ( i = 0; i < pCut->nLeaves; i++ )
00499     {
00500         fInvPin = ((uPhase & (1 << i)) > 0);
00501         Map_MappingSetRefs_rec( pMan, Map_NotCond(pCut->ppLeaves[i], fInvPin), ppStore );
00502     }
00503 }

int Map_NodeDecRefPhaseAct ( Map_Node_t *  pNode,
int  fPhase 
) [static]

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

Synopsis [Decrements the actual reference counter of a phase.]

Description [Returns the new reference counter.]

SideEffects []

SeeAlso []

Definition at line 107 of file mapperRefs.c.

00108 {
00109     assert( !Map_IsComplement(pNode) );
00110     if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned
00111         return --pNode->nRefAct[fPhase];
00112     assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned
00113     return --pNode->nRefAct[2];
00114 }

int Map_NodeIncRefPhaseAct ( Map_Node_t *  pNode,
int  fPhase 
) [static]

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

FileName [mapperRefs.c]

PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]

Synopsis [Generic technology mapping engine.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 2.0. Started - June 1, 2004.]

Revision [

Id
mapperRefs.h,v 1.0 2003/09/08 00:00:00 alanmi Exp

] DECLARATIONS ///

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

Synopsis [Increments the actual reference counter of a phase.]

Description [Returns the old reference counter.]

SideEffects []

SeeAlso []

Definition at line 87 of file mapperRefs.c.

00088 {
00089     assert( !Map_IsComplement(pNode) );
00090     if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned
00091         return pNode->nRefAct[fPhase]++;
00092     assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned
00093     return pNode->nRefAct[2]++;
00094 }

int Map_NodeReadRefPhaseAct ( Map_Node_t *  pNode,
int  fPhase 
)

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

Synopsis [Reads the actual reference counter of a phase.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file mapperRefs.c.

00046 {
00047     assert( !Map_IsComplement(pNode) );
00048     if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned
00049         return pNode->nRefAct[fPhase];
00050     assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned
00051     return pNode->nRefAct[2];
00052 }

float Map_NodeReadRefPhaseEst ( Map_Node_t *  pNode,
int  fPhase 
)

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

Synopsis [Reads the estimated reference counter of a phase.]

Description []

SideEffects []

SeeAlso []

Definition at line 65 of file mapperRefs.c.

00066 {
00067     assert( !Map_IsComplement(pNode) );
00068     if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned
00069         return pNode->nRefEst[fPhase];
00070     assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned
00071 //    return pNode->nRefEst[0] + pNode->nRefEst[1];
00072     return pNode->nRefEst[2];
00073 }

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