abc70930: src/opt/res/resFilter.c Source File

00001 
00021 #include "abc.h"
00022 #include "resInt.h"
00023 
00027 
00028 static unsigned * Res_FilterCollectFaninInfo( Res_Win_t * pWin, Res_Sim_t * pSim, unsigned uMask );
00029 static int        Res_FilterCriticalFanin( Abc_Obj_t * pNode );
00030 
00034 
00046 int Res_FilterCandidates( Res_Win_t * pWin, Abc_Ntk_t * pAig, Res_Sim_t * pSim, Vec_Vec_t * vResubs, Vec_Vec_t * vResubsW, int nFaninsMax, int fArea )
00047 {
00048     Abc_Obj_t * pFanin, * pFanin2, * pFaninTemp;
00049     unsigned * pInfo, * pInfoDiv, * pInfoDiv2;
00050     int Counter, RetValue, i, i2, d, d2, iDiv, iDiv2, k;
00051 
00052     // check that the info the node is one
00053     pInfo = Vec_PtrEntry( pSim->vOuts, 1 );
00054     RetValue = Abc_InfoIsOne( pInfo, pSim->nWordsOut );
00055     if ( RetValue == 0 )
00056     {
00057 //        printf( "Failed 1!\n" );
00058         return 0;
00059     }
00060 
00061     // collect the fanin info
00062     pInfo = Res_FilterCollectFaninInfo( pWin, pSim, ~0 );
00063     RetValue = Abc_InfoIsOne( pInfo, pSim->nWordsOut );
00064     if ( RetValue == 0 )
00065     {
00066 //        printf( "Failed 2!\n" );
00067         return 0;
00068     }
00069 
00070     // try removing each fanin
00071 //    printf( "Fanins: " );
00072     Counter = 0;
00073     Vec_VecClear( vResubs );
00074     Vec_VecClear( vResubsW );
00075     Abc_ObjForEachFanin( pWin->pNode, pFanin, i )
00076     {
00077         if ( fArea && Abc_ObjFanoutNum(pFanin) > 1 )
00078             continue;
00079         // get simulation info without this fanin
00080         pInfo = Res_FilterCollectFaninInfo( pWin, pSim, ~(1 << i) );
00081         RetValue = Abc_InfoIsOne( pInfo, pSim->nWordsOut );
00082         if ( RetValue )
00083         {
00084 //            printf( "Node %4d. Candidate fanin %4d.\n", pWin->pNode->Id, pFanin->Id );
00085             // collect the nodes
00086             Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,0) );
00087             Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,1) );
00088             Abc_ObjForEachFanin( pWin->pNode, pFaninTemp, k )
00089             {
00090                 if ( k != i )
00091                 {
00092                     Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,2+k) );
00093                     Vec_VecPush( vResubsW, Counter, pFaninTemp );
00094                 }
00095             }
00096             Counter++;
00097             if ( Counter == Vec_VecSize(vResubs) )
00098                 return Counter;    
00099         }
00100     }
00101 
00102     // try replacing each critical fanin by a non-critical fanin
00103     Abc_ObjForEachFanin( pWin->pNode, pFanin, i )
00104     {
00105         if ( Abc_ObjFanoutNum(pFanin) > 1 )
00106             continue;
00107         // get simulation info without this fanin
00108         pInfo = Res_FilterCollectFaninInfo( pWin, pSim, ~(1 << i) );
00109         // go over the set of divisors
00110         for ( d = Abc_ObjFaninNum(pWin->pNode) + 2; d < Abc_NtkPoNum(pAig); d++ )
00111         {
00112             pInfoDiv = Vec_PtrEntry( pSim->vOuts, d );
00113             iDiv = d - (Abc_ObjFaninNum(pWin->pNode) + 2);
00114             if ( !Abc_InfoIsOrOne( pInfo, pInfoDiv, pSim->nWordsOut ) )
00115                 continue;
00116             // collect the nodes
00117             Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,0) );
00118             Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,1) );
00119             // collect the remaning fanins and the divisor
00120             Abc_ObjForEachFanin( pWin->pNode, pFaninTemp, k )
00121             {
00122                 if ( k != i )
00123                 {
00124                     Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,2+k) );
00125                     Vec_VecPush( vResubsW, Counter, pFaninTemp );
00126                 }
00127             }
00128             // collect the divisor
00129             Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,d) );
00130             Vec_VecPush( vResubsW, Counter, Vec_PtrEntry(pWin->vDivs, iDiv) );
00131             Counter++;
00132             if ( Counter == Vec_VecSize(vResubs) )
00133                 return Counter;           
00134         }
00135     }
00136 
00137     // consider the case when two fanins can be added instead of one
00138     if ( Abc_ObjFaninNum(pWin->pNode) < nFaninsMax )
00139     {
00140         // try to replace each critical fanin by two non-critical fanins
00141         Abc_ObjForEachFanin( pWin->pNode, pFanin, i )
00142         {
00143             if ( Abc_ObjFanoutNum(pFanin) > 1 )
00144                 continue;
00145             // get simulation info without this fanin
00146             pInfo = Res_FilterCollectFaninInfo( pWin, pSim, ~(1 << i) );
00147             // go over the set of divisors
00148             for ( d = Abc_ObjFaninNum(pWin->pNode) + 2; d < Abc_NtkPoNum(pAig); d++ )
00149             {
00150                 pInfoDiv = Vec_PtrEntry( pSim->vOuts, d );
00151                 iDiv = d - (Abc_ObjFaninNum(pWin->pNode) + 2);
00152                 // go through the second divisor
00153                 for ( d2 = d + 1; d2 < Abc_NtkPoNum(pAig); d2++ )
00154                 {
00155                     pInfoDiv2 = Vec_PtrEntry( pSim->vOuts, d2 );
00156                     iDiv2 = d2 - (Abc_ObjFaninNum(pWin->pNode) + 2);
00157                     if ( !Abc_InfoIsOrOne3( pInfo, pInfoDiv, pInfoDiv2, pSim->nWordsOut ) )
00158                         continue;
00159                     // collect the nodes
00160                     Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,0) );
00161                     Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,1) );
00162                     // collect the remaning fanins and the divisor
00163                     Abc_ObjForEachFanin( pWin->pNode, pFaninTemp, k )
00164                     {
00165                         if ( k != i )
00166                         {
00167                             Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,2+k) );
00168                             Vec_VecPush( vResubsW, Counter, pFaninTemp );
00169                         }
00170                     }
00171                     // collect the divisor
00172                     Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,d) );
00173                     Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,d2) );
00174                     Vec_VecPush( vResubsW, Counter, Vec_PtrEntry(pWin->vDivs, iDiv) );
00175                     Vec_VecPush( vResubsW, Counter, Vec_PtrEntry(pWin->vDivs, iDiv2) );
00176                     Counter++;
00177                     if ( Counter == Vec_VecSize(vResubs) )
00178                         return Counter;           
00179                 }
00180             }
00181         }
00182     }
00183 
00184     // try to replace two nets by one
00185     if ( !fArea )
00186     {
00187         Abc_ObjForEachFanin( pWin->pNode, pFanin, i )
00188         {
00189             for ( i2 = i + 1; i2 < Abc_ObjFaninNum(pWin->pNode); i2++ )
00190             {
00191                 pFanin2 = Abc_ObjFanin(pWin->pNode, i2);
00192                 // get simulation info without these fanins
00193                 pInfo = Res_FilterCollectFaninInfo( pWin, pSim, (~(1 << i)) & (~(1 << i2)) );
00194                 // go over the set of divisors
00195                 for ( d = Abc_ObjFaninNum(pWin->pNode) + 2; d < Abc_NtkPoNum(pAig); d++ )
00196                 {
00197                     pInfoDiv = Vec_PtrEntry( pSim->vOuts, d );
00198                     iDiv = d - (Abc_ObjFaninNum(pWin->pNode) + 2);
00199                     if ( !Abc_InfoIsOrOne( pInfo, pInfoDiv, pSim->nWordsOut ) )
00200                         continue;
00201                     // collect the nodes
00202                     Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,0) );
00203                     Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,1) );
00204                     // collect the remaning fanins and the divisor
00205                     Abc_ObjForEachFanin( pWin->pNode, pFaninTemp, k )
00206                     {
00207                         if ( k != i && k != i2 )
00208                         {
00209                             Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,2+k) );
00210                             Vec_VecPush( vResubsW, Counter, pFaninTemp );
00211                         }
00212                     }
00213                     // collect the divisor
00214                     Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,d) );
00215                     Vec_VecPush( vResubsW, Counter, Vec_PtrEntry(pWin->vDivs, iDiv) );
00216                     Counter++;
00217                     if ( Counter == Vec_VecSize(vResubs) )
00218                         return Counter;           
00219                 }
00220             }
00221         }
00222     }
00223     return Counter;
00224 }
00225 
00226 
00238 int Res_FilterCandidatesArea( Res_Win_t * pWin, Abc_Ntk_t * pAig, Res_Sim_t * pSim, Vec_Vec_t * vResubs, Vec_Vec_t * vResubsW, int nFaninsMax )
00239 {
00240     Abc_Obj_t * pFanin;
00241     unsigned * pInfo, * pInfoDiv, * pInfoDiv2;
00242     int Counter, RetValue, d, d2, k, iDiv, iDiv2, iBest;
00243 
00244     // check that the info the node is one
00245     pInfo = Vec_PtrEntry( pSim->vOuts, 1 );
00246     RetValue = Abc_InfoIsOne( pInfo, pSim->nWordsOut );
00247     if ( RetValue == 0 )
00248     {
00249 //        printf( "Failed 1!\n" );
00250         return 0;
00251     }
00252 
00253     // collect the fanin info
00254     pInfo = Res_FilterCollectFaninInfo( pWin, pSim, ~0 );
00255     RetValue = Abc_InfoIsOne( pInfo, pSim->nWordsOut );
00256     if ( RetValue == 0 )
00257     {
00258 //        printf( "Failed 2!\n" );
00259         return 0;
00260     }
00261 
00262     // try removing fanins
00263 //    printf( "Fanins: " );
00264     Counter = 0;
00265     Vec_VecClear( vResubs );
00266     Vec_VecClear( vResubsW );
00267     // get the best fanins
00268     iBest = Res_FilterCriticalFanin( pWin->pNode );
00269     if ( iBest == -1 )
00270         return 0;
00271 
00272     // get the info without the critical fanin
00273     pInfo = Res_FilterCollectFaninInfo( pWin, pSim, ~(1 << iBest) );
00274     RetValue = Abc_InfoIsOne( pInfo, pSim->nWordsOut );
00275     if ( RetValue )
00276     {
00277 //        printf( "Can be done without one!\n" );
00278         // collect the nodes
00279         Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,0) );
00280         Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,1) );
00281         Abc_ObjForEachFanin( pWin->pNode, pFanin, k )
00282         {
00283             if ( k != iBest )
00284             {
00285                 Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,2+k) );
00286                 Vec_VecPush( vResubsW, Counter, pFanin );
00287             }
00288         }
00289         Counter++;
00290 //        printf( "*" );
00291         return Counter;
00292     }
00293 
00294     // go through the divisors
00295     for ( d = Abc_ObjFaninNum(pWin->pNode) + 2; d < Abc_NtkPoNum(pAig); d++ )
00296     {
00297         pInfoDiv = Vec_PtrEntry( pSim->vOuts, d );
00298         iDiv = d - (Abc_ObjFaninNum(pWin->pNode) + 2);
00299         if ( !Abc_InfoIsOrOne( pInfo, pInfoDiv, pSim->nWordsOut ) )
00300             continue;
00301 //if ( Abc_ObjLevel(pWin->pNode) <= Abc_ObjLevel( Vec_PtrEntry(pWin->vDivs, iDiv) ) )
00302 //    printf( "Node level = %d. Divisor level = %d.\n", Abc_ObjLevel(pWin->pNode), Abc_ObjLevel( Vec_PtrEntry(pWin->vDivs, iDiv) ) );
00303         // collect the nodes
00304         Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,0) );
00305         Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,1) );
00306         // collect the remaning fanins and the divisor
00307         Abc_ObjForEachFanin( pWin->pNode, pFanin, k )
00308         {
00309             if ( k != iBest )
00310             {
00311                 Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,2+k) );
00312                 Vec_VecPush( vResubsW, Counter, pFanin );
00313             }
00314         }
00315         // collect the divisor
00316         Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,d) );
00317         Vec_VecPush( vResubsW, Counter, Vec_PtrEntry(pWin->vDivs, iDiv) );
00318         Counter++;
00319 
00320         if ( Counter == Vec_VecSize(vResubs) )
00321             break;            
00322     }
00323 
00324     if ( Counter > 0 || Abc_ObjFaninNum(pWin->pNode) >= nFaninsMax )
00325         return Counter;
00326 
00327     // try to find the node pairs
00328     for ( d = Abc_ObjFaninNum(pWin->pNode) + 2; d < Abc_NtkPoNum(pAig); d++ )
00329     {
00330         pInfoDiv = Vec_PtrEntry( pSim->vOuts, d );
00331         iDiv = d - (Abc_ObjFaninNum(pWin->pNode) + 2);
00332         // go through the second divisor
00333         for ( d2 = d + 1; d2 < Abc_NtkPoNum(pAig); d2++ )
00334         {
00335             pInfoDiv2 = Vec_PtrEntry( pSim->vOuts, d2 );
00336             iDiv2 = d2 - (Abc_ObjFaninNum(pWin->pNode) + 2);
00337 
00338             if ( !Abc_InfoIsOrOne3( pInfo, pInfoDiv, pInfoDiv2, pSim->nWordsOut ) )
00339                 continue;
00340             // collect the nodes
00341             Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,0) );
00342             Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,1) );
00343             // collect the remaning fanins and the divisor
00344             Abc_ObjForEachFanin( pWin->pNode, pFanin, k )
00345             {
00346                 if ( k != iBest )
00347                 {
00348                     Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,2+k) );
00349                     Vec_VecPush( vResubsW, Counter, pFanin );
00350                 }
00351             }
00352             // collect the divisor
00353             Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,d) );
00354             Vec_VecPush( vResubs, Counter, Abc_NtkPo(pAig,d2) );
00355             Vec_VecPush( vResubsW, Counter, Vec_PtrEntry(pWin->vDivs, iDiv) );
00356             Vec_VecPush( vResubsW, Counter, Vec_PtrEntry(pWin->vDivs, iDiv2) );
00357             Counter++;
00358 
00359             if ( Counter == Vec_VecSize(vResubs) )
00360                 break;            
00361         }
00362         if ( Counter == Vec_VecSize(vResubs) )
00363             break;            
00364     }
00365     return Counter;
00366 }
00367 
00368 
00380 unsigned * Res_FilterCollectFaninInfo( Res_Win_t * pWin, Res_Sim_t * pSim, unsigned uMask )
00381 {
00382     Abc_Obj_t * pFanin;
00383     unsigned * pInfo;
00384     int i;
00385     pInfo = Vec_PtrEntry( pSim->vOuts, 0 );
00386     Abc_InfoClear( pInfo, pSim->nWordsOut );
00387     Abc_ObjForEachFanin( pWin->pNode, pFanin, i )
00388     {
00389         if ( uMask & (1 << i) )
00390             Abc_InfoOr( pInfo, Vec_PtrEntry(pSim->vOuts, 2+i), pSim->nWordsOut );
00391     }
00392     return pInfo;
00393 }
00394 
00395 
00407 int Res_FilterCriticalFanin( Abc_Obj_t * pNode )
00408 {
00409     Abc_Obj_t * pFanin;
00410     int i, iBest = -1, CostMax = 0, CostCur;
00411     Abc_ObjForEachFanin( pNode, pFanin, i )
00412     {
00413         if ( !Abc_ObjIsNode(pFanin) )
00414             continue;
00415         if ( Abc_ObjFanoutNum(pFanin) > 1 )
00416             continue;
00417         CostCur = Res_WinVisitMffc( pFanin );
00418         if ( CostMax < CostCur )
00419         {
00420             CostMax = CostCur;
00421             iBest = i;
00422         }
00423     }
00424 //    if ( CostMax > 0 )
00425 //        printf( "<%d>", CostMax );
00426     return iBest;
00427 }
00428 
00429 
00433 
00434