abc70930: src/map/fpga/fpgaUtils.c Source File

00001 
00019 #include "fpgaInt.h"
00020 
00024 
00025 #define FPGA_CO_LIST_SIZE  5
00026 
00027 static void  Fpga_MappingDfs_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes, int fCollectEquiv );
00028 static void  Fpga_MappingDfsCuts_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes );
00029 static int   Fpga_MappingCompareOutputDelay( Fpga_Node_t ** ppNode1, Fpga_Node_t ** ppNode2 );
00030 static void  Fpga_MappingFindLatest( Fpga_Man_t * p, int * pNodes, int nNodesMax );
00031 static void  Fpga_DfsLim_rec( Fpga_Node_t * pNode, int Level, Fpga_NodeVec_t * vNodes );
00032 static int   Fpga_CollectNodeTfo_rec( Fpga_Node_t * pNode, Fpga_Node_t * pPivot, Fpga_NodeVec_t * vVisited, Fpga_NodeVec_t * vTfo );
00033 static Fpga_NodeVec_t * Fpga_MappingOrderCosByLevel( Fpga_Man_t * pMan );
00034 static Fpga_Man_t * s_pMan = NULL;
00035 
00039 
00040 
00052 Fpga_NodeVec_t * Fpga_MappingDfs( Fpga_Man_t * pMan, int fCollectEquiv )
00053 {
00054     Fpga_NodeVec_t * vNodes;//, * vNodesCo;
00055     Fpga_Node_t * pNode;
00056     int i;
00057     // collect the CO nodes by level
00058 //    vNodesCo = Fpga_MappingOrderCosByLevel( pMan );
00059     // start the array
00060     vNodes = Fpga_NodeVecAlloc( 100 );
00061     // collect the PIs
00062     for ( i = 0; i < pMan->nInputs; i++ )
00063     {
00064         pNode = pMan->pInputs[i];
00065         Fpga_NodeVecPush( vNodes, pNode );
00066         pNode->fMark0 = 1;
00067     }
00068     // perform the traversal
00069     for ( i = 0; i < pMan->nOutputs; i++ )
00070         Fpga_MappingDfs_rec( Fpga_Regular(pMan->pOutputs[i]), vNodes, fCollectEquiv );
00071 //    for ( i = vNodesCo->nSize - 1; i >= 0 ; i-- )
00072 //        for ( pNode = vNodesCo->pArray[i]; pNode; pNode = (Fpga_Node_t *)pNode->pData0 )
00073 //            Fpga_MappingDfs_rec( pNode, vNodes, fCollectEquiv );
00074     // clean the node marks
00075     for ( i = 0; i < vNodes->nSize; i++ )
00076         vNodes->pArray[i]->fMark0 = 0;
00077 //    for ( i = 0; i < pMan->nOutputs; i++ )
00078 //        Fpga_MappingUnmark_rec( Fpga_Regular(pMan->pOutputs[i]) );
00079 //    Fpga_NodeVecFree( vNodesCo );
00080     return vNodes;
00081 }
00082 
00094 void Fpga_MappingDfs_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes, int fCollectEquiv )
00095 {
00096     assert( !Fpga_IsComplement(pNode) );
00097     if ( pNode->fMark0 )
00098         return;
00099     // visit the transitive fanin
00100     if ( Fpga_NodeIsAnd(pNode) )
00101     {
00102         Fpga_MappingDfs_rec( Fpga_Regular(pNode->p1), vNodes, fCollectEquiv );
00103         Fpga_MappingDfs_rec( Fpga_Regular(pNode->p2), vNodes, fCollectEquiv );
00104     }
00105     // visit the equivalent nodes
00106     if ( fCollectEquiv && pNode->pNextE )
00107         Fpga_MappingDfs_rec( pNode->pNextE, vNodes, fCollectEquiv );
00108     // make sure the node is not visited through the equivalent nodes
00109     assert( pNode->fMark0 == 0 );
00110     // mark the node as visited
00111     pNode->fMark0 = 1;
00112     // add the node to the list
00113     Fpga_NodeVecPush( vNodes, pNode );
00114 }
00115 
00127 Fpga_NodeVec_t * Fpga_MappingDfsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes, int fEquiv )
00128 {
00129     Fpga_NodeVec_t * vNodes;
00130     int i;
00131     // perform the traversal
00132     vNodes = Fpga_NodeVecAlloc( 200 );
00133     for ( i = 0; i < nNodes; i++ )
00134         Fpga_MappingDfs_rec( ppNodes[i], vNodes, fEquiv );
00135     for ( i = 0; i < vNodes->nSize; i++ )
00136         vNodes->pArray[i]->fMark0 = 0;
00137     return vNodes;
00138 }
00139 
00151 float Fpga_MappingGetAreaFlow( Fpga_Man_t * p )
00152 {
00153     float aFlowFlowTotal = 0;
00154     int i;
00155     for ( i = 0; i < p->nOutputs; i++ )
00156     {
00157         if ( Fpga_NodeIsConst(p->pOutputs[i]) )
00158             continue;
00159         aFlowFlowTotal += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow;
00160     }
00161     return aFlowFlowTotal;
00162 }
00163 
00175 float Fpga_MappingArea( Fpga_Man_t * pMan )
00176 {
00177     Fpga_Node_t * pNode;
00178     float aTotal;
00179     int i;
00180     // perform the traversal
00181     aTotal = 0;
00182     for ( i = 0; i < pMan->vMapping->nSize; i++ )
00183     {
00184         pNode = pMan->vMapping->pArray[i];
00185         aTotal += pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves];
00186     }
00187     return aTotal;
00188 }
00189 
00201 float Fpga_MappingArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes )
00202 {
00203     float aArea;
00204     int i;
00205     assert( !Fpga_IsComplement(pNode) );
00206     if ( !Fpga_NodeIsAnd(pNode) )
00207         return 0;
00208     if ( pNode->fMark0 )
00209         return 0;
00210     assert( pNode->pCutBest != NULL );
00211     // visit the transitive fanin of the selected cut
00212     aArea = 0;
00213     for ( i = 0; i < pNode->pCutBest->nLeaves; i++ )
00214         aArea += Fpga_MappingArea_rec( pMan, pNode->pCutBest->ppLeaves[i], vNodes );
00215     // make sure the node is not visited through the fanin nodes
00216     assert( pNode->fMark0 == 0 );
00217     // mark the node as visited
00218     pNode->fMark0 = 1;
00219     // add the node to the list
00220     aArea += pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves];
00221     // add the node to the list
00222     Fpga_NodeVecPush( vNodes, pNode );
00223     return aArea;
00224 }
00225 
00237 float Fpga_MappingAreaTrav( Fpga_Man_t * pMan )
00238 {
00239     Fpga_NodeVec_t * vNodes;
00240     float aTotal;
00241     int i;
00242     // perform the traversal
00243     aTotal = 0;
00244     vNodes = Fpga_NodeVecAlloc( 100 );
00245     for ( i = 0; i < pMan->nOutputs; i++ )
00246         aTotal += Fpga_MappingArea_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), vNodes );
00247     for ( i = 0; i < vNodes->nSize; i++ )
00248         vNodes->pArray[i]->fMark0 = 0;
00249     Fpga_NodeVecFree( vNodes );
00250     return aTotal;
00251 }
00252 
00253 
00265 float Fpga_MappingSetRefsAndArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Node_t ** ppStore )
00266 {
00267     float aArea;
00268     int i;
00269     assert( !Fpga_IsComplement(pNode) );
00270     if ( pNode->nRefs++ )
00271         return 0;
00272     if ( !Fpga_NodeIsAnd(pNode) )
00273         return 0;
00274     assert( pNode->pCutBest != NULL );
00275     // store the node in the structure by level
00276     pNode->pData0 = (char *)ppStore[pNode->Level]; 
00277     ppStore[pNode->Level] = pNode;
00278     // visit the transitive fanin of the selected cut
00279     aArea = pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves];
00280     for ( i = 0; i < pNode->pCutBest->nLeaves; i++ )
00281         aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode->pCutBest->ppLeaves[i], ppStore );
00282     return aArea;
00283 }
00284 
00297 float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan )
00298 {
00299     Fpga_Node_t * pNode, ** ppStore;
00300     float aArea;
00301     int i, LevelMax;
00302 
00303     // clean all references
00304     for ( i = 0; i < pMan->vNodesAll->nSize; i++ )
00305         pMan->vNodesAll->pArray[i]->nRefs = 0;
00306 
00307     // allocate place to store the nodes
00308     LevelMax = Fpga_MappingMaxLevel( pMan );
00309     ppStore = ALLOC( Fpga_Node_t *, LevelMax + 1 );
00310     memset( ppStore, 0, sizeof(Fpga_Node_t *) * (LevelMax + 1) );
00311 
00312     // collect nodes reachable from POs in the DFS order through the best cuts
00313     aArea = 0;
00314     for ( i = 0; i < pMan->nOutputs; i++ )
00315     {
00316         pNode = Fpga_Regular(pMan->pOutputs[i]);
00317         if ( pNode == pMan->pConst1 )
00318             continue;
00319         aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode, ppStore );
00320         pNode->nRefs++;
00321     }
00322 
00323     // reconnect the nodes in reverse topological order
00324     pMan->vMapping->nSize = 0;
00325     for ( i = LevelMax; i >= 0; i-- )
00326         for ( pNode = ppStore[i]; pNode; pNode = (Fpga_Node_t *)pNode->pData0 )
00327             Fpga_NodeVecPush( pMan->vMapping, pNode );
00328     free( ppStore );
00329     return aArea;
00330 }
00331 
00332 
00344 int Fpga_MappingCompareOutputDelay( Fpga_Node_t ** ppNode1, Fpga_Node_t ** ppNode2 )
00345 {
00346     Fpga_Node_t * pNode1 = Fpga_Regular(*ppNode1);
00347     Fpga_Node_t * pNode2 = Fpga_Regular(*ppNode2);
00348     float Arrival1 = pNode1->pCutBest? pNode1->pCutBest->tArrival : 0;
00349     float Arrival2 = pNode2->pCutBest? pNode2->pCutBest->tArrival : 0;
00350     if ( Arrival1 < Arrival2 )
00351         return -1;
00352     if ( Arrival1 > Arrival2 )
00353         return 1;
00354     return 0;
00355 }
00356 
00368 void Fpga_MappingFindLatest( Fpga_Man_t * p, int * pNodes, int nNodesMax )
00369 {
00370     int nNodes, i, k, v;
00371     assert( p->nOutputs >= nNodesMax );
00372     pNodes[0] = 0;
00373     nNodes = 1;
00374     for ( i = 1; i < p->nOutputs; i++ )
00375     {
00376         for ( k = nNodes - 1; k >= 0; k-- )
00377             if ( Fpga_MappingCompareOutputDelay( &p->pOutputs[pNodes[k]], &p->pOutputs[i] ) >= 0 )
00378                 break;
00379         if ( k == nNodesMax - 1 )
00380             continue;
00381         if ( nNodes < nNodesMax )
00382             nNodes++;
00383         for ( v = nNodes - 1; v > k+1; v-- )
00384             pNodes[v] = pNodes[v-1];
00385         pNodes[k+1] = i;
00386     }
00387 }
00388 
00400 void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p )
00401 {
00402     Fpga_Node_t * pNode;
00403     int pSorted[FPGA_CO_LIST_SIZE];
00404     int fCompl, Limit, MaxNameSize, i;
00405 
00406     // determine the number of nodes to print
00407     Limit = (p->nOutputs > FPGA_CO_LIST_SIZE)? FPGA_CO_LIST_SIZE : p->nOutputs;
00408 
00409     // determine the order
00410     Fpga_MappingFindLatest( p, pSorted, Limit );
00411 
00412     // determine max size of the node's name
00413     MaxNameSize = 0;
00414     for ( i = 0; i < Limit; i++ )
00415         if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) )
00416             MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]);
00417 
00418     // print the latest outputs
00419     for ( i = 0; i < Limit; i++ )
00420     {
00421         // get the i-th latest output
00422         pNode  = Fpga_Regular(p->pOutputs[pSorted[i]]);
00423         fCompl = Fpga_IsComplement(p->pOutputs[pSorted[i]]);
00424         // print out the best arrival time
00425         printf( "Output  %-*s : ", MaxNameSize + 3, p->ppOutputNames[pSorted[i]] );
00426         printf( "Delay = %8.2f  ",     (double)pNode->pCutBest->tArrival );
00427         if ( fCompl )
00428             printf( "NEG" );
00429         else
00430             printf( "POS" );
00431         printf( "\n" );
00432     }
00433 }
00434 
00435 
00447 void Fpga_MappingSetupTruthTables( unsigned uTruths[][2] )
00448 {
00449     int m, v;
00450     // set up the truth tables
00451     for ( m = 0; m < 32; m++ )
00452         for ( v = 0; v < 5; v++ )
00453             if ( m & (1 << v) )
00454                 uTruths[v][0] |= (1 << m);
00455     // make adjustments for the case of 6 variables
00456     for ( v = 0; v < 5; v++ )
00457         uTruths[v][1] = uTruths[v][0];
00458     uTruths[5][0] = 0;
00459     uTruths[5][1] = FPGA_FULL;
00460 }
00461 
00473 void Fpga_MappingSetupMask( unsigned uMask[], int nVarsMax )
00474 {
00475     if ( nVarsMax == 6 )
00476         uMask[0] = uMask[1] = FPGA_FULL;
00477     else
00478     {
00479         uMask[0] = FPGA_MASK(1 << nVarsMax);
00480         uMask[1] = 0;
00481     }
00482 }
00483 
00498 int Fpga_ManCheckConsistency( Fpga_Man_t * p )
00499 {
00500     Fpga_Node_t * pNode;
00501     Fpga_NodeVec_t * pVec;
00502     int i;
00503     pVec = Fpga_MappingDfs( p, 0 );
00504     for ( i = 0; i < pVec->nSize; i++ )
00505     {
00506         pNode = pVec->pArray[i];
00507         if ( Fpga_NodeIsVar(pNode) )
00508         {
00509             if ( pNode->pRepr )
00510                 printf( "Primary input %d is a secondary node.\n", pNode->Num );
00511         }
00512         else if ( Fpga_NodeIsConst(pNode) )
00513         {
00514             if ( pNode->pRepr )
00515                 printf( "Constant 1 %d is a secondary node.\n", pNode->Num );
00516         }
00517         else
00518         {
00519             if ( pNode->pRepr )
00520                 printf( "Internal node %d is a secondary node.\n", pNode->Num );
00521             if ( Fpga_Regular(pNode->p1)->pRepr )
00522                 printf( "Internal node %d has first fanin that is a secondary node.\n", pNode->Num );
00523             if ( Fpga_Regular(pNode->p2)->pRepr )
00524                 printf( "Internal node %d has second fanin that is a secondary node.\n", pNode->Num );
00525         }
00526     }
00527     Fpga_NodeVecFree( pVec );
00528     return 1;
00529 }
00530 
00542 int Fpga_CompareNodesByLevelDecreasing( Fpga_Node_t ** ppS1, Fpga_Node_t ** ppS2 )
00543 {
00544     if ( Fpga_Regular(*ppS1)->Level > Fpga_Regular(*ppS2)->Level )
00545         return -1;
00546     if ( Fpga_Regular(*ppS1)->Level < Fpga_Regular(*ppS2)->Level )
00547         return 1;
00548     return 0;
00549 }
00550 
00562 int Fpga_CompareNodesByLevelIncreasing( Fpga_Node_t ** ppS1, Fpga_Node_t ** ppS2 )
00563 {
00564     if ( Fpga_Regular(*ppS1)->Level < Fpga_Regular(*ppS2)->Level )
00565         return -1;
00566     if ( Fpga_Regular(*ppS1)->Level > Fpga_Regular(*ppS2)->Level )
00567         return 1;
00568     return 0;
00569 }
00570 
00582 void Fpga_MappingSortByLevel( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes, int fIncreasing )
00583 {
00584     if ( fIncreasing )
00585         qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *), 
00586                 (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelIncreasing );
00587     else
00588         qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *), 
00589                 (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelDecreasing );
00590 //    assert( Fpga_CompareNodesByLevel( vNodes->pArray, vNodes->pArray + vNodes->nSize - 1 ) <= 0 );
00591 }
00592 
00604 Fpga_NodeVec_t * Fpga_DfsLim( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int nLevels )
00605 {
00606     Fpga_NodeVec_t * vNodes;
00607     int i;
00608     // perform the traversal
00609     vNodes = Fpga_NodeVecAlloc( 100 );
00610     Fpga_DfsLim_rec( pNode, nLevels, vNodes );
00611     for ( i = 0; i < vNodes->nSize; i++ )
00612         vNodes->pArray[i]->fMark0 = 0;
00613     return vNodes;
00614 }
00615 
00627 void Fpga_DfsLim_rec( Fpga_Node_t * pNode, int Level, Fpga_NodeVec_t * vNodes )
00628 {
00629     assert( !Fpga_IsComplement(pNode) );
00630     if ( pNode->fMark0 )
00631         return;
00632     pNode->fMark0 = 1;
00633     // visit the transitive fanin
00634     Level--;
00635     if ( Level > 0 && Fpga_NodeIsAnd(pNode) )
00636     {
00637         Fpga_DfsLim_rec( Fpga_Regular(pNode->p1), Level, vNodes );
00638         Fpga_DfsLim_rec( Fpga_Regular(pNode->p2), Level, vNodes );
00639     }
00640     // add the node to the list
00641     Fpga_NodeVecPush( vNodes, pNode );
00642 }
00643 
00655 void Fpga_ManCleanData0( Fpga_Man_t * pMan )
00656 {
00657     int i;
00658     for ( i = 0; i < pMan->vNodesAll->nSize; i++ )
00659         pMan->vNodesAll->pArray[i]->pData0 = 0;
00660 }
00661 
00673 Fpga_NodeVec_t * Fpga_CollectNodeTfo( Fpga_Man_t * pMan, Fpga_Node_t * pNode )
00674 {
00675     Fpga_NodeVec_t * vVisited, * vTfo;
00676     int i;
00677     // perform the traversal
00678     vVisited = Fpga_NodeVecAlloc( 100 );
00679     vTfo     = Fpga_NodeVecAlloc( 100 );
00680     for ( i = 0; i < pMan->nOutputs; i++ )
00681         Fpga_CollectNodeTfo_rec( Fpga_Regular(pMan->pOutputs[i]), pNode, vVisited, vTfo );
00682     for ( i = 0; i < vVisited->nSize; i++ )
00683         vVisited->pArray[i]->fMark0 = vVisited->pArray[i]->fMark1 = 0;
00684     Fpga_NodeVecFree( vVisited );
00685     return vTfo;
00686 }
00687 
00699 int Fpga_CollectNodeTfo_rec( Fpga_Node_t * pNode, Fpga_Node_t * pPivot, Fpga_NodeVec_t * vVisited, Fpga_NodeVec_t * vTfo )
00700 {
00701     int Ret1, Ret2;
00702     assert( !Fpga_IsComplement(pNode) );
00703     // skip visited nodes
00704     if ( pNode->fMark0 )
00705         return pNode->fMark1;
00706     pNode->fMark0 = 1;
00707     Fpga_NodeVecPush( vVisited, pNode );
00708 
00709     // return the pivot node
00710     if ( pNode == pPivot )
00711     {
00712         pNode->fMark1 = 1;
00713         return 1;
00714     }
00715     if ( pNode->Level < pPivot->Level )
00716     {
00717         pNode->fMark1 = 0;
00718         return 0;
00719     }
00720     // visit the transitive fanin
00721     assert( Fpga_NodeIsAnd(pNode) );
00722     Ret1 = Fpga_CollectNodeTfo_rec( Fpga_Regular(pNode->p1), pPivot, vVisited, vTfo );
00723     Ret2 = Fpga_CollectNodeTfo_rec( Fpga_Regular(pNode->p2), pPivot, vVisited, vTfo );
00724     if ( Ret1 || Ret2 )
00725     {
00726         pNode->fMark1 = 1;
00727         Fpga_NodeVecPush( vTfo, pNode );
00728     }
00729     else
00730         pNode->fMark1 = 0;
00731     return pNode->fMark1;
00732 }
00733 
00745 Fpga_NodeVec_t * Fpga_MappingLevelize( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes )
00746 {
00747     Fpga_NodeVec_t * vLevels;
00748     Fpga_Node_t ** ppNodes;
00749     Fpga_Node_t * pNode;
00750     int nNodes, nLevelsMax, i;
00751 
00752     // reassign the levels (this may be necessary for networks which choices)
00753     ppNodes = vNodes->pArray;
00754     nNodes  = vNodes->nSize;
00755     for ( i = 0; i < nNodes; i++ )
00756     {
00757         pNode = ppNodes[i];
00758         if ( !Fpga_NodeIsAnd(pNode) )
00759         {
00760             pNode->Level = 0;
00761             continue;
00762         }
00763         pNode->Level = 1 + FPGA_MAX( Fpga_Regular(pNode->p1)->Level, Fpga_Regular(pNode->p2)->Level );
00764     }
00765 
00766     // get the max levels
00767     nLevelsMax = 0;
00768     for ( i = 0; i < pMan->nOutputs; i++ )
00769         nLevelsMax = FPGA_MAX( nLevelsMax, (int)Fpga_Regular(pMan->pOutputs[i])->Level );
00770     nLevelsMax++;
00771 
00772     // allocate storage for levels
00773     vLevels = Fpga_NodeVecAlloc( nLevelsMax );
00774     for ( i = 0; i < nLevelsMax; i++ )
00775         Fpga_NodeVecPush( vLevels, NULL );
00776 
00777     // go through the nodes and add them to the levels
00778     for ( i = 0; i < nNodes; i++ )
00779     {
00780         pNode = ppNodes[i];
00781         pNode->pLevel = NULL;
00782         if ( !Fpga_NodeIsAnd(pNode) )
00783             continue;
00784         // attach the node to this level
00785         pNode->pLevel = Fpga_NodeVecReadEntry( vLevels, pNode->Level );
00786         Fpga_NodeVecWriteEntry( vLevels, pNode->Level, pNode );
00787     }
00788     return vLevels;
00789 }
00790 
00802 int Fpga_MappingMaxLevel( Fpga_Man_t * pMan )
00803 {
00804     int nLevelMax, i;
00805     nLevelMax = 0;
00806     for ( i = 0; i < pMan->nOutputs; i++ )
00807         nLevelMax = nLevelMax > (int)Fpga_Regular(pMan->pOutputs[i])->Level? 
00808                 nLevelMax : (int)Fpga_Regular(pMan->pOutputs[i])->Level;
00809     return nLevelMax;
00810 }
00811 
00812 
00824 int Fpga_MappingUpdateLevel_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int fMaximum )
00825 {
00826     Fpga_Node_t * pTemp;
00827     int Level1, Level2, LevelE;
00828     assert( !Fpga_IsComplement(pNode) );
00829     if ( !Fpga_NodeIsAnd(pNode) )
00830         return pNode->Level;
00831     // skip the visited node
00832     if ( pNode->TravId == pMan->nTravIds )
00833         return pNode->Level;
00834     pNode->TravId = pMan->nTravIds;
00835     // compute levels of the children nodes
00836     Level1 = Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pNode->p1), fMaximum );
00837     Level2 = Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pNode->p2), fMaximum );
00838     pNode->Level = 1 + FPGA_MAX( Level1, Level2 );
00839     if ( pNode->pNextE )
00840     {
00841         LevelE = Fpga_MappingUpdateLevel_rec( pMan, pNode->pNextE, fMaximum );
00842         if ( fMaximum )
00843         {
00844             if ( pNode->Level < (unsigned)LevelE )
00845                 pNode->Level = LevelE;
00846         }
00847         else
00848         {
00849             if ( pNode->Level > (unsigned)LevelE )
00850                 pNode->Level = LevelE;
00851         }
00852         // set the level of all equivalent nodes to be the same minimum
00853         if ( pNode->pRepr == NULL ) // the primary node
00854             for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE )
00855                 pTemp->Level = pNode->Level;
00856     }
00857     return pNode->Level;
00858 }
00859 
00874 void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan )
00875 {
00876     int i;
00877     pMan->nTravIds++;
00878     for ( i = 0; i < pMan->nOutputs; i++ )
00879         Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 1 );
00880 }
00881 
00895 void Fpga_ManReportChoices( Fpga_Man_t * pMan )
00896 {
00897     Fpga_Node_t * pNode, * pTemp;
00898     int nChoiceNodes, nChoices;
00899     int i, LevelMax1, LevelMax2;
00900 
00901     // report the number of levels
00902     LevelMax1 = Fpga_MappingMaxLevel( pMan );
00903     pMan->nTravIds++;
00904     for ( i = 0; i < pMan->nOutputs; i++ )
00905         Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 0 );
00906     LevelMax2 = Fpga_MappingMaxLevel( pMan );
00907 
00908     // report statistics about choices
00909     nChoiceNodes = nChoices = 0;
00910     for ( i = 0; i < pMan->vAnds->nSize; i++ )
00911     {
00912         pNode = pMan->vAnds->pArray[i];
00913         if ( pNode->pRepr == NULL && pNode->pNextE != NULL )
00914         { // this is a choice node = the primary node that has equivalent nodes
00915             nChoiceNodes++;
00916             for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE )
00917                 nChoices++;
00918         }
00919     }
00920     if ( pMan->fVerbose )
00921     {
00922     printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 );
00923     printf( "Choice stats:  Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices );
00924     }
00925 /*
00926     {
00927         FILE * pTable;
00928         pTable = fopen( "stats_choice.txt", "a+" );
00929         fprintf( pTable, "%s ", pMan->pFileName );
00930         fprintf( pTable, "%4d ", LevelMax1 );
00931         fprintf( pTable, "%4d ", pMan->vAnds->nSize - pMan->nInputs );
00932         fprintf( pTable, "%4d ", LevelMax2 );
00933         fprintf( pTable, "%7d ", nChoiceNodes );
00934         fprintf( pTable, "%7d ", nChoices + nChoiceNodes );
00935         fprintf( pTable, "\n" );
00936         fclose( pTable );
00937     }
00938 */
00939 }
00940 
00952 Fpga_NodeVec_t * Fpga_MappingOrderCosByLevel( Fpga_Man_t * pMan )
00953 {
00954     Fpga_Node_t * pNode;
00955     Fpga_NodeVec_t * vNodes;
00956     int i, nLevels;
00957     // get the largest level of a CO
00958     nLevels = Fpga_MappingMaxLevel( pMan );
00959     // allocate the array of nodes
00960     vNodes = Fpga_NodeVecAlloc( nLevels + 1 );
00961     for ( i = 0; i <= nLevels; i++ )
00962         Fpga_NodeVecPush( vNodes, NULL );
00963     // clean the marks
00964     for ( i = 0; i < pMan->nOutputs; i++ )
00965         Fpga_Regular(pMan->pOutputs[i])->fMark0 = 0;
00966     // put the nodes into the structure
00967     for ( i = 0; i < pMan->nOutputs; i++ )
00968     {
00969         pNode = Fpga_Regular(pMan->pOutputs[i]);
00970         if ( pNode->fMark0 )
00971             continue;
00972         pNode->fMark0 = 1;
00973         pNode->pData0 = (char *)Fpga_NodeVecReadEntry( vNodes, pNode->Level );
00974         Fpga_NodeVecWriteEntry( vNodes, pNode->Level, pNode );
00975     }
00976     for ( i = 0; i < pMan->nOutputs; i++ )
00977         Fpga_Regular(pMan->pOutputs[i])->fMark0 = 0;
00978     return vNodes;
00979 
00980 }
00981 
00985 
00986